一种改进的基于飞鸟迁徙的Ad hoc 网络路由算法

刘永广

(1.广东轻工职业技术学院，广东广州 510300;2.中国电子科技集团第七研究所，广东广州 510310)

0 引言

Ad hoc网络是一种多跳、无中心的自组织网络，网络中的所有节点都是对等的。为了实现多跳寻址，源和目的节点需要借助其他节点进行分组转发。因此，一个高效的、适应性强的路由算法是保证Ad hoc网络性能的关键。

针对Ad hoc网络的特点，研究人员提出了多种Ad hoc网络路由协议。从这些协议的研究方向上来看，基本上可以分为两类:基于拓扑的路由算法和基于位置的路由算法，而大多数研究以拓扑为基础来进行，如Ad hoc按需距离矢量路由 (Ad hoc ondemand distance vector routing，AODV)，动态源路由(dynamic source routing，DSR)等［1］，关于这些协议的优缺点，在上述相关文献中已有详细的分析和对比，此处不再赘述。为了减少拓扑信息分发的开销，并能更好适应Ad hoc网络用于移动场景的特点，研究人员开始关注位置信息在Ad hoc网络路由算法中的应用，并提出了一些有代表性的算法［2－6］，这些算法的研究焦点均集中于中间节点根据位置信息采用什么策略转发数据包。一些算法采用了贪婪策略［3－4］，这些算法根据自己的标准在转发范围内选择一个最优中继节点，这种选择的好处是根据算法的侧重点可以有效地优化某一方面的性能，但是由于存在局部优化问题，如果遇到终结节点，算法陷入死锁，虽然采取了恢复措施，但是往往导致性能降低且无法找到最优路径。一些算法采用了定向洪泛策略［5］，虽然这种算法设计简单，但洪泛导致数据包被转发次数增加，网络额外开销增加，降低了网络吞吐量，增加了网络丢包率。此外，当节点移动速度较大时，算法的性能严重降低。

1 受飞鸟迁徙启发的路由协议(BFIRP)

文献［7］发现了上述问题，并受到飞鸟迁徙规律［8］的启发，提出了一种基于飞鸟迁徙规律的Ad hoc网络路由算法协议(bird flight－inspired routing protocol，BFIRP)，该算法利用了飞鸟迁徙过程路径选择的规律，发现飞鸟在沿球面迁徙过程中，经过连接球面上2点且以球心为圆心的大圆路径是最节省能量的。该算法根据获得的位置信息，设计了基于位置信息的确切性中继节点选择方法。该算法由于精确地选择转发节点、有效地减少了路由开销，使得网络吞吐量获得明显提高，丢包率减少，网络整体性能获得提高。但是，该算法在设计和基于实际应用上还存在缺陷:首先，该算法在实现上依靠一个有中心的位置服务来获得其他节点的位置信息，而Ad hoc网络本身是无中心网络，增加了中心选择过程;其次，对于一些应用场景，比如战场，提供位置服务的节点一旦被摧毁，该算法将不能正常计算;最后，由于该算法在后继节点的选择方向上是明确的，因此，会出现该方向(具有一定角度)上无中继节点存在的情况，对于这种情况，该算法采用了向源端发送失败错误(failure error，FERROR)消息的路由恢复方法，源端收到FERROR后，重新选择方向。这种处理增加了网络的额外开销，并且由于重新开始路由选择，导致部分报文延迟增大，甚至被丢弃。

针对以上所述飞鸟迁徙算法存在的问题，本文提出了一种改进的基于飞鸟迁徙的Ad hoc网络路由算法，新算法仅继承了原算法的方向选择策略，对原算法的关键技术进行了重新设计，增加了新的报文和数据结构，去掉了原来的FERROR报文，从而克服了原算法的缺陷，使网络性能得以有效提高。

2 新算法关键技术

2.1 信标报文的发送周期

针对该问题，本算法选择一个节点偏离原来位置的距离作为是否发送信标报文的度量，只有当该距离超过一定门限时，才发送信标报文，即

(1)式中:(Xc，Yc，Zc)为节点的当前坐标;(Xo，Yo，Zo)为节点移动前的坐标，节点通过一个定时器周期性计算Δ值，当Δ ＞Δmax时(Δmax为最大偏移门限)，节点发送信标报文，并用节点的当前坐标(Xc，Yc，Zc)来更新 (Xo，Yo，Zo)。

更进一步，如果仅考虑绝对移动距离也是不合理的，因为该门限其实和区域的大小及节点的密度有关系。在一个节点相对密集的区域，一个节点的移动会对其他节点路径选择发生重要的影响。如图1所示，图1a和图1b为2个同样大小的区域，在图1a中有3个节点，而在图1b中有4个节点，在节点S产生到目的节点D的路由，虚线圆标出了目的节点移动的2个位置。由图1a可以看到，节点D在d1距离内移动时，S的转发方位都是不用变化的，D节点也不用发送信标报文。在图1b中，由于节点变得密集，从图1b可以看出，当节点D在转发区域1移动了d2距离后进入转发区域2，此时，节点1已经无法做中继，节点D应该发送信标报文。由图1看出，d1显然大于d2，所以如果在上述2种应用模式中采用同一个门限值，则是不合理的，基于该问题，以下本文给出了新的信标报文发送度量。

图1 区域大小和节点数对发送周期的影响Fig.1 Influence of area size and node number on sending period

假设在长、宽、高分别为Lx，Ly，Lz的空间区域内有n个节点，且节点服从均匀分布，并定义在3个方向上的节点间平均间距为dx，dy，dz，节点D的移动方向为(α，β，γ)，则定义节点D发送信标的度量为

2.2 应急路由

如图2所示，在原算法中，源节点S需要向目的节点D发送数据，经过下一跳方向计算，并选择具有大概率值的节点2作为下一跳中继节点，节点2经过下一跳计算形成自己的转发区域，但该转发区域内并无中继节点存在。此时，节点2会向源端S发送FERROR报文，S收到该报文后会重新调整方向，在其邻居节点内选择6作为下一跳中继。这个过程显然是效率低下的，如果此时节点2能把报文直接转到6，则省略了回传FERROR报文和重新选路的过程，算法的效率会得以有效提高。

当转发区域无后继节点时，原算法通过向源节点发送FERROR报文来通知源节点重新选择新的方向和路由，这种方法增加了延迟。为克服算法这一弊端，我们利用信标报文的信息生成一个基于距离矢量的应急路由表，在一个节点知道其转发方向内的邻居消失时，可以选择另一可到达目的端的邻居进行转发，具体处理过程和用到的数据结构如下。

图2 转发区域无邻居的情况Fig.2 Condition of no neighbor in forwarding area

每个节点在位置变化达到阈值Δmax或者路由表中有邻居节点的位置更新时，均要发送携带变化信息的信标报文，类似于AODV，每个节点通过信标报文可以知道通过哪一个下一跳可以到达网络中的其他目的节点，从而形成一个基于距离矢量的路由表，该路由表中允许对同一目的地存在多个路径，以图2中节点2的路由表为例，可看到如表1所示的路由表项。

表1 节点2的应急路由表Tab.1 Emergency routing table of node 2

正常转发情况下，节点只需利用邻居节点的位置信息和目的节点的位置信息来计算转发区域［7］，并不会用到该表。但是当出现图2的情况，节点3因为移动出节点2的转发区域，此时利用表1选择一个下一跳转发给节点6，不需要通过FERROR报文通告源节点S做重新选择，节点6收到报文以后，继续按照方向性选择标准来计算转发区域进行转发。

2.3 转发中继节点选择

在本算法中，仅中继节点的转发策略，采用了原算法的思路，即

(4)式中:w1+w2+w3= 1;Ei为邻居节点的能量;Emax为所有节点的最大能量值;dnd为邻居节点和目的节点在大圆上的距离;did为本节点和目的节点在大圆上的距离;θ为邻居节点偏离本节点和目的节点形成的大圆的角度。

参照文献［7］，在下一节进行仿真实验有能量参数时，选择w1=w2=w3=1/3，其他选择w1=w2=0.5，w3=0 。

2.4 Hello报文

在本算法的设计中，由于信标报文不是周期性发送的，当节点静止或者移动缓慢的时候，就不会产生信标报文，而且，当一个节点移走以后，其原来的邻居收不到信标报文，它会以为该邻居处于静止状态，因此，仅采用信标报文来维持邻居关系是不可行的。针对该问题，设计中增加一个Hello报文，该Hello报文为周期性的，但如果在下一个心跳报文发送时间到来之前发送了信标报文，则会在当前时间基础上推迟一个周期作为下一次发送Hello报文的时间。该方法如图3所示，第1个时间轴的竖线表示Hello报文的发送周期，第2个时间轴的竖线表示信标报文的发送时间，由图3可以看到，只要在一个Hello报文的发送周期内发送了信标报文，Hello报文的发送时间就一直会被推迟。也就是说，在这种情况下，信标报文充当了Hello报文的角色，只有在一个T时间内没有发送信标报文的情况下，才由节点发送心跳报文，由图3可以看到，这种设计有效地减少了Hello的维护开销。

图3 信标报文对Hello报文发送时间的影响Fig.3 Influence of beacon packet on the time of sending Hello packet

3 性能评估

本节将通过仿真对算法的性能和参数进行分析，主要对本文的改进算法(I_BFIRP)和原算法BFIRP进行比较，并同时和一种基于拓扑的路由算法AODV［9］以及一种有代表性的基于位置信息的路由算法多跳转发路由(multihop forward routing，MFR)［10］进行比较。仿真在 NS2仿真环境下进行，仿真参数如表2所示，节点在场景内服从均匀分布，节点移动速度服从［10，20］的均匀分布，Δmax=1。

表2 仿真环境参数设置Tab.2 Settings of simulation environment parameters

在以上条件下，首先对报文递交的成功率进行评估，如图4所示。由图4可以看出，随着节点数的增加，网络的动荡性加大，基于拓扑的AODV路由协议由于拓扑变换，路由表变化频繁，节点发送队列溢出，使部分数据报文被丢弃，从而导致报文丢包率降低。相反，基于位置的几个路由协议，不需要维护路由表，只要在转发方向上存在中继节点，就能获得准确转发，节点数的增加对这些算法的成功率影响不大。由图4还可以看出，在节点数较少的时候，本文的改进算法性能要明显优于原算法，这是因为在节点数稀疏时容易产生转发区域无中继节点的情况，由于本算法采用了应急路由，可以迅速找到下一跳路由，而不需要转发回源节点，所以成功率较高。当节点数较多时，转发方向上很少无中继节点，本算法的应急路由基本用不到，2个算法的性能趋于一致。另一方面，重新进行路径选择也增加了端到端的延迟，这一点从图5中可获得验证。图5是在移动速度15 m/s时给出的仿真结果，在节点较稀疏时，相比原算法，本文的算法有较大的性能提升，但当节点数增多时，优势就不再明显。

为针对性评估改进对算法的影响，图6对2种算法在路由开销方面的性能进行了比较，由图6可以看出，在350个节点情况下，由于移动速度的增加，2种算法发送信标报文的数量都明显增加，但由于本文的算法采用了只有超出一定区域门限才发送信标报文的策略，因此，信标报文的发送数量明显少于原算法，尽管增加了Hello报文，但绝大部分情况下，该报文被信标报文代替，即使有发送，也是几个字节来维持邻居关系，可以忽略不计。

图4 不同算法对成功率的影响Fig.4 Influence of different algorithms on success ratio

图5 不同算法对端到端时延的影响Fig.5 Influence of different algorithms on end－to－end delay

图6 2种算法的路由开销比较Fig.6 Comparison of routing cost between two algorithms

图7在350个节点、不同移动速度情况下对端到端平均延迟做了比较，可以看到，由于采用了应急路由策略，本算法的延迟要低于原算法，但随着速度增加，如在20 m/s或更高时，本算法采用的应急路由表由于拓扑变换太快而逐渐失去它的实用性，因此，当移动速度较大时，延迟方面的性能改进就不太明显，但是在拓扑变化不太剧烈的情况下，本算法采用的策略还是对网络性能的改进有非常明显的成效。图8在多个网络节点情况下对2个算法的能量消耗情况进行了比较。由图8可以看出，在绝大多数情况下，本文的算法由于节点减少报文发送数量，提高了路由恢复效率，从而能使节点获得更多的剩余能量。

图7 2种算法的端到端延迟比较Fig.7 Comparison of end－to－end delay between two algorithms

图8 2种算法剩余能量的比较Fig.8 Comparison of residual energy between two algorithms

4 结论

本文对一种基于飞鸟迁徙原理的Ad hoc网络组网算法进行了研究，发现了算法中的缺点和不足，并针对这些不足提出了改进算法，仿真结果表明，本文提出的改进策略有效地提高了网络的整体性能，而且，本文的部分研究结果也可适用于其他相关基于位置信息的路由算法性能改进。

［1］SIVAKUMAR S，SUSEELA B，VARADHARAJAN R.A survey of routing algorithms for manet［C］//IEEE.Proceedings of International Conference on Advances in Engineering，Science and Management(ICAESM－2012).Nagapattinam，Tamil Nadu:IEEE Press，2012:625－640.

［2］DAY K，ARAFEH B，TOUZENE A，et al.A 3D grid position－based routing protocol formobile ad hoc networks［C］//IEEE.Proceedings of the International Conference on Computer and Communication Engineering.Kuala Lumpur:IEEE Press，2008:151－156.

［3］QABAJEH LK，KIAH LM，QABAJEH M M.A qualitative comparison of position－based routing protocols for ad hoc networks［J］.International Journal of Computer Science and Network，2011，9(2):131－140.

［4］CAO Y，XIE S.A position based beaconless routing algorithm formobile ad hoc networks［C］//IEEE.Proceedings of the IEEE International Conference on Communications，Circuits and Systems.Guangzhou，China:IEEE Press，2005:303－307.

［5］CHAN C，WARTY C，YU RW.Position based directional Ad－Hoc routing with space time diversity［C］//IEEE.Proceedings of Global Humanitarian Technology Conference(GHTC).Seattle，WA:IEEE Press，2012:192－197.

［6］LIAOW H，SHEU JP，TSENG Y C.GRID:A fully location – aware routing protocol for mobile ad hoc networks［J］.Telecommunication Systems，2001，18(1－3):37－60.

［7］MISRA S，RAJESH G.Bird flight－inspired routing protocol formobile ad hoc networks［J］.ACM Transactions on Autonomous and Adaptive Systems，2011，6(4):25－44.

［8］QIU J.Ornithology:Flightof the navigators［J］.Nature，2005，437(7060):804－806.

［9］PERKINSC E，ROYER E M.Ad hoc On－Demand Distance Vector(AODV)Routing［EB/OL］.(2003－07－01)［2013－06－28］.http://www.ietf.org/rfc/rfc3561.txt.

［10］TAKAGIH，KLEINROCK L.Optimal transmission ranges for randomly distributed packet radio terminals［J］.IEEE Transactions on Communication，1984，32(3):246－257.

(编辑:王敏琦)