郭玉婷 李强

摘 要：为了降低移动自组织网络（MANET）中移动性对路由性能造成的影响，该文提出基于链路预测的可靠MPR选择算法，通过节点间距离和无线传输范围来预测节点与其相邻节点之间的剩余链路有效时间，并提出将剩余链路有效时间（RTTQ）作为OLSR路由协议选择多点中继（MPR）的新的度量方法。利用NS2进行了大量的网络仿真，结果显示采用RTTQ大于临界值的MPR节点，可以提高多项性能，如MPR生存时间、分组交付率（PDR）和平均吞吐量（ATT）。

关键词：移动自组织网络 多点中继 链路中断 NS2 MPR生存时间

中图分类号：TP393 文献标识码：A 文章编号：1674-098X（2015）08（c）-0054-03

Reliable MPR Selection Algorithm Based on Link Prediction

Guo Yuting1，2， Li Qiang2

（1.Wuhan Lingyun Building Decoration Engineering CO.LTD.，Wuhan Hubei，430040；2.Air Force Early Warning Inst.，Wuhan Hubei，430019，China）

Abstract：In order to reduce the effect of the mobility of mobile ad-hoc network（MANET）on routing performance， this paper proposed a reliable MPR selection algorithm based on link prediction. The valid time of remaining chain between this node and adjacent node was predicted by both the distance between nodes and the range of wireless transmission. The paper also proposed a new measuring method on selecting multi-point relay by applying the remaining link effective time（RTTQ）as OLSR routing protocol. A lot of NS2 network simulation were conducted in this paper.The results show that a number of properties，such as MPR survival time， packet delivery ratio （PDR） and average throughput（ATT），can be improved by using the MPR nodes，in which the RTTQ was greater than the critical value.

Key Words：MANET；Multi Point Relay；Link Interruption；NS2；MPR Survival Time

由于OLSR路由問题与MPR选择有关，即可以通过在MPR选择机制上增加度量，提高路由性能。关于OLSR路由优化的大部分文献都致力于寻找除了RFC3626中（路径质量通过跳数衡量）规定的默认度量之外的其他有效度量，如误比特率（BER）[1]或队列长度。QOLSR[2]是先应式路由的一个重大发展，其通过向OLSR增加QoS机制对带宽利用率或时延等实施限制从而寻找最短最宽的路径提供最佳路径选择。文献[3]还提出了期望传输数（ETX）度量作为MANET因特网草案，目前有望成为标准。文献[4]中提出了一种MPR选择法，该方法通过将传播包汇聚在MPR节点，进一步降低重新传输次数。但是鉴于无线环境的的不稳定性，减少重新传输次数不一定对可靠数据包传输有利。文献[5]提出了另一种方法，试图预测一定时间范围内的链路有效性以及两节点间给定初始距离的链路有效性。由于MPR节点在将广播包传输到下个MPR节点以及相邻节点中起到重要作用，如果不能从MPR接收到广播包，就会严重影响交付率。因此，根据链路生存时间预测选择可靠MPR为改善路由性能提出了很好的切入点。由于节点移动，有些无线链路可能在路径建立起来后立即中断。如果再次发现路由，就会产生大量的数据丢失和通信开销。

由此可见，现在路由的共同弱点是由于网络环境中节点的移动特性，依据过去或当前的链路状态信息确定的可靠链路可能随着时间推移而变得不可靠，即不能较好的适应未知的链路变化。同时以往的很多链路状态信息都是根据自组网的链路状态的进行统计分析，并不能代表现实链路环境。为了降低此类网络中移动性造成的影响，本文提出基于链路预测的可靠MPR选择算法，通过每次信息包中携带的节点间距离和时间信息并结合无线传输范围来预测节点与其相邻节点之间的剩余链路有效时间RTTQ，并利用RTTQ作为MPR选择的新的度量方法，从而选出链路更稳定，性能更优的MPR节点，进而提升路由性能。

1 OLSR协议概述

OLSR协议是针对MANET特点发展起来的表驱动路由协议，网络中的每个节点都保存有到网络中所有可达目的节点的路由，使用最小跳数来寻找出到达目的节点的最短路径。协议最突出的就是通过MPR（Multipoint Relays）机制减少网络控制信息的泛洪。网络中的每个节都在其一跳节点中选择出MPR节点，非MPR节点能够处理控制信息但不能转发控制信息，而且MPR集必须覆盖其所有的两条节点。协议通过HELLO信息周期性的广播一跳邻居节点的链路信息和地址来选择MPR集。通过节点周期性的发送TC（Topology Control）分组来发布 MPR Selector 信息，以帮助其他节点建立到它的路由，并通过周期性地交换信息来维护网络拓扑。因此，OLSR协议的核心功能包括以下几方面。

（1）链路感知：通过周期性（标准间隔为2s）交换HELLO信息获得，并更新本地链路表信息。

（2）发现邻近节点：像链路感知过程一样，邻近节点的检测也是通过HELLO信息完成的。

（3）MPR选择：每个 节点都在其一跳邻近节点中选择一个能到达所有两跳邻近节点的最小子集，该集合则为MPR节点节点集。

（4）TC信息广播：发布TC消息（拓扑控制信息）的目的在于为使每个网络节点获得全网的链路状态信息，用以选定路由和发送信息。TC消息也是周期性的更新（标准间隔为5秒），通过MPR节点范洪到全网。

（5）路由计算：网络中每个节点都可以根据链路状态信息的定期交换，重新计算路由表。

2 DIST-OLSR协议

2.1 剩余有效时间（RTTQ）

如图1所示，以其中一个节点（S）对邻居节点（N）链路有效时间进行估计并选择MPR选择为例，本节点根据两次连续接收到的消息期间，节点移动的距离（D1和D2），对应移动所历经时间（△t=T2–T1）和无线传输范围（RANGE）可以估计出邻居节点的链路有效时间。

其中，T1和T2分别指邻居节点在D1和D2的时间。△d指的是新老距离之间的差（△d=D2-D1），并记录在接收的消息中（包括HELLO，TC消息），△d的正负表示其邻居节点相对源节点的远离或靠近，这在MPR集运算过程中很重要。文中，RTTQ取最大的有效时间值，计算如式（1）：

（1）

2.2 受RTTQ临界值限制的MPR集计算

节点每接收一个消息都会调用图2的算法来对每个邻居节点s的RTTQ进行重新估计。因此，在选择MPR节点时，可能较早离开（或在离开边缘）的邻居节点将不能作为MPR候选节点，且只有当节点的RTTQ值大于给定的临界值时，MPR候选节点才会被纳入MPR集中。在此方法中，不仅考虑了标准OLSR协议（RFC3626）中的节点到达性和节点度，同时考虑了节点的链路状态。通过修改标准OLSR中的MPR选择方法，就获得了一个新版的OLSR协议（DIST-OLSR）。同样，如果节点达到性非零且具有最高的意愿度同样被选为MPR节点。在面临多个选择是，首先将到达性最大且RTTQ大于给定临界值的节点选为MPR。如果多个节点具有相同的到达性和RTTQ，我们将节点度最大的节点选为MPR。

3 仿真分析

文章采用NS2-2.34[6]进行网络仿真，并对标准版本的OLSR（UM-OLSR-0.8.8）[7]进行修改。仿真場景参数如表1，其中，每次模拟会随机选择10个节点作为固定比特率（CBR）业务的来源。

3.1 平均MPR节点数

如图3所示，给出了不同RTTQ临界值和节点移动速度，UM-OLSR协议和DIST-OLSR协议下的MPR平均数量。可以发现，在不同RTTQ临界值下，DIST-OLSR协议和标准OLSR几乎拥有相同的MPR数，基本上对于不同的RTTQ临界值，标准OLSR只是增加了约0.25%。然而，当节点移动速度提高时，两种版本OLSR（UM-OLSR和Dist-OLSR）协议产生的MPR平均数量均急剧减少。其主要是因为当速度增加时，节点间链路变化更快，节点的链路有效时间相对减少，这将大大影响网络的性能。

3.2 MPR平均生存时间

图4显示了不同临界值和速度时，UM-OLSR协议和DIST-OLSR协议下的MPR平均生存时间。

从图4和表2可以看出，DIST-OLSR协议下，有18次其MPR平均生存时间比标准OLSR协议长，相较而言，标准OLSR协议下只有10次的MPR平均生存时间较长。从整体看，DIST-OLSR协议下的MPR生存时间比标准OLSR协议下的生存时间提高了26.66%。另外，表2还说明：DIST-OLSR协议的最佳结果出现在当临界值为3 s或4 s时。此外，在高速下（20～25m/s），MPR平均生存时间趋向于平稳，约4.5 s，而且其值在所有临界值下都几乎一样。

3.3 分组交付率（PDR）

RTTQ临界值为3 s和4 s时，DIST-OLSR的MPR平均生存时间最长，那么有必要采用交付率来对网络的性能进行评价。节点采用RWP移动模型时，不同速度下两种协议的分组交付率（PDR）如图5所示。

由图5可知，不管临界值是3 s秒还是4 s，随着节点速度的增加，PDR都在下降。从图上我们还发现，临界值为3s时，两种OLSR协议的PDR值非常接近，DIST-OLSR协议下相对于标准OLSR协议的结果要稍微高一点。当临界值为4 s时，低速下情况下，标准OLSR协议要优于DIST-OLSR，而高速下情况下，DIST-OLSR结果优于标准OLSR协议。

3.4 平均吞吐量

图6显示了当临界值为3 s和4 s时，不同速度下，标准OLSR协议和DIST-OLSR的平均吞吐量仿真情况。临界值为3 s或4 s时，低速下情形下（5和10m/s）的DIST-OLSR协议的平均吞吐量较高。当临界值为3s，高速下情形下（20和25m/s）的DIST-OLSR协议的平均吞吐量也高于标准OLSR协议。当速度为15m/s时，标准OLSR协议的结果才优于DIST-OLSR协议结果。因此，总体上，在平均吞吐量方面，DIST-OLSR协议整体性能相对较好。

4 结语

该文的首要目标是将控制信息和数据包发送至目的地址的路径的生存时间延长，提高链路可靠性。基本思想是通过信息包携带的位置信息和无线传输距离预测链路有效时间，并引入MPR选择的新度量RTTQ，从而降低节点移动性的带来的不利影响。通过仿真分析发现，DIST-OLSR协议的MPR有效时间比标准OLSR协议（UM-OLSR）提高约25%。

參考文献

[1] M.Poussard，W. Hamidouche， R. Vauzelle， et al.Realistic SISO and MIMO physical layer implemented in two routing protocols for vehicular ad hoc network[C]//In 9th International Conference on Intelligent Transport Systems Tele-communications， 2009：393-397.

[2] H.Badis，K.Al Agha.QOLSR，QoS routing for ad hoc wireless networks using OLSR[J].European Transactions on Telecommunications，2005，16（5）：427-442.

[3] K.Yamada，T.Itokawa，T.Kitasuka，et al.Cooperative MPR selection to reduce topology control packets in OLSR[C]//TENCON 2010-2010 IEEE Region 10 Conference， 2010：293-298.

[4] Q.Han，Y.Bai，L.Gong，et al.Link availability prediction-based reliable routing for mobile ad hoc networks[J].IET Communications， 2011，5（16）：2291-2300.

[5] T.Clausen，P.Jacquet.Optimized Link State Routing protocol（OLSR）[C]//Internet Engeneering Task Force，RFC 3626，2003.

[6] N.Sadagopan，F.Bai，B.Krishnamachari，et al.PATHS：analysis of PATH duration statistics and their impact on reactive MANET routing protocols[C]//Proceedings of the 4th ACM international symposium on Mobile ad hoc networking and computing，2003：245-256.

[7] Shengming Jiang，Dajiang He，Jianqiang Rao. A prediction-based link availability estimation for routing metrics in MANETs[C]//IEEE/ACM Transactions on Networking，2005，13（6）：1302-1312.

[8] Shengming Jiang.An enhanced prediction-based link availability estimation for MANETs[J].IEEE Transactions on Communications，2004，52（2）：183.