基于节点位置信息的Ad Hoc空间覆盖广播算法

白乐强，田 野

（沈阳建筑大学 信息与控制工程学院，辽宁 沈阳 110168）

广播不仅是Ad Hoc中路由发现的基础，还可以向全网发布特殊消息，一直备受广大学者的关注.最简单的广播算法是泛洪方式，而传统的泛洪［1］（flooding）方式在实现广播的同时会产生大量的冗余转发，从而造成额外的冲突甚至网络拥塞，这 种 情 况 被 称 为 广 播 风 暴［2］（broadcast storm）.针对广播风暴问题，近年来提出了很多新的广播算法.现有的广播算法大体可以分成四大类：泛洪方式、基于概率方式［3－4］、基于邻节点信息方式［5－6］、基于面积方式［7］。基于面积方式不需要记录接收状态，无需维护邻节点信息，因此传输时延和存储开销很小.但是，由于使用预定义的门限值，在节点密度或网络负载变化时其性能会变差，并且转发节点之间由于不了解相互的位置关系，使得转发节点分布不合理，在某些非冗余节点出现错误时会导致丢包甚至无法继续转发.SCB算法［8］是一种基于面积方式的改进算法，SCB算法的优点在于保证高送达率的同时，降低了冗余转发次数，不足之处是传输时延过高.

针对SCB算法传输时延过高的问题，文章提出了一种基于节点位置的空间覆盖算法（Location Based Space－Covered Broadcast，简称LBSCB算法）.该算法通过节点位置信息来指定转发节点，优化转发节点数目，从而大量减少了转发节点个数，减少了冗余转发.由于该算法不使用预定义的门限值，在节点数目增大时，性能依然保持高效.该算法唯一需要的网络信息是节点的位置信息，这可以通过相对GPS（Global Positioning System）等技术来获取［9］.

1 理想模型下的节点分布和广播算法

1.1 理想模型下的节点分布

图1 理想覆盖模型Fig.1 Ideal cover model

假设网络中的节点是理想分布的，节点的发送半径相同均为R，引入理想覆盖模型.如图1所示，将平面划分为边长为R的正六边形，让这些正六边形彼此无缝相连，在每个正六边形的顶点处以R为半径做圆，这就是理想覆盖模型，在此称之为理想模型.每个正六边形的顶点就是理想模型的节点所在位置，这些圆就是每个节点的覆盖范围，每个转发节点与其他3个转发节点互相连接.这种理想模型可以实现利用很少数目的转发节点完成对整个网络的双重覆盖［8］，既可以保证广播的全网覆盖，又可以减少冗余转发.而且任意两个节点之间都有至少三条路径，即使一条路径失效，节点也可以通过其他路径来完成转发，这大大加强了网络的容错能力.

1.2 理想模型下的广播算法

节点分布理想的情况下，在每个正六边形的顶点处设置转发节点即可实现可靠、高效的广播.如图1所示，S是源节点，它以广播的方式向外发送数据包，数据包到达它的3个邻节点；然后这3个邻节点分别向各自的2个邻节点转发数据包；所有节点重复这个过程，直到整个网络中的所有节点都收到数据包.在这里需要注意的是，源节点要向传输范围内的3个节点转发；其他节点只向传输范围内的2个节点转发（如图1中的A）.

2 LBSCB算法

如图2所示，在实际网络中节点是随机分布的，通常会偏离理想模型下的节点分布位置，无法获得最优分布.在理想模型中转发节点能够双重覆盖网络，即使个别节点失效，广播依然可以覆盖网络.所以选择距离理想模型中节点所在位置最近的节点作为转发节点就可以最大程度地覆盖网络.这在保证算法送达率的同时，减少了大量的冗余转发.特别指出，当节点分布密度较大时，转发节点的分布近似于理想模型.

图2 实际网络中的节点分布Fig.2 The node distribution of actual network

2.1 LBSCB算法相关参数定义

本文称图1中转发节点所在的位置为理想位置，节点的传输半径相同均为R，每个节点的位置坐标均已知.LBSCB算法中定义了五种类型的节点，它们分别是普通节点、源节点、转发节点、上一跳节点和下一跳节点.节点类型定义和坐标表示如表1.当发送节点为源节点S时，通过公式（1）可以计算出S的3个理想位置S－Loc1、S－Loc2、S－Loc3，通过公式（3）可以计算出节点到3个理想位置的距离dS1、dS2、dS3；当发送节点为转发节点F（node）时，通过公式（2）可以计算出F（node）的2个理想位置Loc1、Loc2，通过公式（4）可以计算出节点到2个理想位置的距离d1、d2.

表1 节点类型定义和坐标表示Table 1 The node type definition and coordinating representation

2.2 理想位置的计算方法

发送节点为源节点S时，由于节点随机分布，在任何方向上其分布概率相同，所以如图2所示，计算出3个理想位置的坐标如下：

由

发送节点为转发节点F（node）时，则上一跳转发节点F（node－1）的坐标即可看作一个理想位置，如图2所示.通过F（node－1）和F（node）的坐标、半径、两条向量之间的夹角来计算出另外两个理想位置.两个夹角分别为θ1＝120°和θ2＝240°，设两个下一跳转发节点的坐标分别为（X′，Y′）和（X″，Y″），计算过程如下：

分别得：

和

所以

2.3 计算节点到理想位置的距离d

发送节点为源节点S时，节点到3个理想位置的距离为

发送节点为转发节点F（node）时，节点到2个理想位置的距离为

2.4 LBSCB算法描述

（1）S向它的传输范围内的所有节点发送数据包，数据包中带有S的3个理想位置坐标SLoc1、S－Loc2、S－Loc3；

（2）收到数据包的节点N（node）分别计算出它到3个理想位置的距离dS1、dS2、dS3，并发送给S；

（3）S 比较dS1、dS2、dS3的大小，选出3个距离理想位置最近的节点作为转发节点F（node）；

（4）F（node）继续向下发送数据包，数据包中带有F（node）的2个理想位置坐标Loc1、Loc2；

（5）收到数据包的节点N（node）分别计算出它到2个理想位置的距离d1、d2，并发送给F（node）；

（6）F（node）比较d1、d2的大小，选出2个距离理想位置最近的节点作为它的下一跳转发节点F（node＋1）；

（7）所有节点重复（5）到（6）的过程，直至数据包覆盖整个网络.在此过程中节点收到重复数据包则丢弃.

3 数据仿真及分析

在 NS－2（版本2.35）平台上对 LBSCB算法和3种主流的广播算法（泛洪协议，基于1跳邻节点信息的边缘转发协议［10］和基于面积方式的SCB算法［8］）在不同节点数目下进行仿真比较.将仿真环境设为1 000m×1 000m的正方形区域，所有节点随机地分布在该矩形区域内.试验参数如表2所示.

表2 试验参数Table 2 Experimental parameter

性能评价参数如下：

（1）送达率（delivery ratio）：接收到广播数据包的节点数与网络节点总数的比值.送达率是衡量算法可靠性的重要指标，这个参数值越高说明广播算法越可靠，性能越好.

（2）转发率（forwarding ratio）：转发节点数与网络节点总数的比值.这个参数值越低说明广播算法的冗余转发越少，性能越好.

（3）传输时延（transmission delay）：所有接收节点的端到端时延的平均值.这个参数值越低说明广播算法性能越好.

每种算法分别在200、400、600、800、1 000五种数量规模的网络场景中仿真100次，统计100次仿真结果求取平均值.找出获得较好性能的节点数目，并对这几种算法的性能进行了比较.仿真结果如图3～图5所示.

图3 不同广播算法的送达率Fig.3 Delivery rate of different broadcasting algorithm

图4 不同广播算法的转发率Fig.4 Forwarding rate of different broadcasting algorithm

图3给出了4种广播算法在不同节点数目下的送达率.从图3中可以看出，泛洪协议和边缘转发协议在节点数目为200时，送达率最高，约为90%，之后随着节点数目的增加逐渐减小；在节点数为200时，LBSCB算法和SCB算法的送达率即可达到95%以上，随着节点数目的增加趋近于100%.实验结果表明，LBSCB算法的送达率明显优于泛洪协议和边缘转发协议，与SCB算法相当.这是由于LBSCB算法采用的圆盘覆盖模型对整个网络平面能够起到双重覆盖的效果，所以除了一些节点因链路问题外，LBSCB算法能够保证一个很高甚至接近100%的送达率.

图5 不同广播算法的传输时延Fig.5 Transmission delay of different broadcasting algorithm

图4给出了4种广播算法在不同节点数目下的转发率.从图4中可以看出泛洪协议的转发率始终为100%；边缘转发协议的转发率在节点数目为1 000时达到最小，约为50%；SCB算法的转发率在节点数为200时只有12%，并且随着节点数目的增加逐渐减小；LBSCB算法的转发率在节点数为200时最大，约为15%，随着节点数目的增加逐渐减小，在节点数目为700时，LBSCB算法的转发率和SCB算法相同，约为10%，之后随着节点数目的增加LBSCB算法的转发率比SCB算法更低.由于LBSCB算法采用了圆盘覆盖的空间分布，在理想情况下，从源节点开始每个转发节点只需最多指派3个节点作为下一跳转发节点即可，因此LBSCB算法在保证双重覆盖的前提下，实现了节点的最优空间分布，大大降低了转发率.而在实际网络中，随着节点数目的增加，转发节点的分布趋于最优分布，LBSCB算法的转发率也随之变小.

图5给出了4种广播算法在不同节点数目下的传输时延.泛洪协议的传输时延在节点数为200时最低，为0.01s，之后随节点数目的增加线性增长；边缘转发协议的传输时延在节点数为400时最低，约为0.025s；SCB算法的传输时延在节点数为400时最低，约为0.03s；对于LBSCB算法，节点数目的变化对传输时延的影响不大，始终保持为大约0.015s.实验结果表明，LBSCB算法的传输时延十分稳定，不随节点数目的增加而变化，在节点数目超过300时最低.这是由于LBSCB算法没有采用基于概率的等待时延机制，无需等待一段时间后再决定是否转发，每次完整的转发都是经过固定的三次数据包发送，所以传输时延很低并且稳定，不随节点数目的增加而变化.

4 结 论

本文提出了一种基于节点位置信息的LBSCB算法.该算法通过优化转发节点的空间分布来尽可能地减少转发节点数目，在保证送达率的同时有效地降低了冗余转发次数.由于没有设置节点转发的等待时延，节点收到数据包后，无需等待判断，降低了传输时延.并且该算法无需邻节点信息，减少了网络带宽.仿真结果表明该算法和SCB算法的送达率和转发率都明显优于其他广播协议（泛洪协议和边缘转发协议），但传输时延却远远小于SCB算法.LBSCB算法在节点数目较大时性能较好，适合应用在大规模网络环境.

［1］ Obraczka K， Viswanath K， Tsudik G. Flooding forReliable Multicast in Multi－hop Ad Hoc Networks［J］.Wireless Networks，2001，7（6）：627－634.

［2］ Tseng Y C，Ni S Y，Chen Y S，et al.TheBroadcast Storm Problem in a Mobile Ad Hoc Network［J］.Wireless Networks，2002，8（2／3）：153－167.

［3］ Khan I A，Javaid A，Qian H L.Distance－based Dynamically Adjusted Probabilistic Forwarding for Wireless Mobile Ad Hoc Networks［C］∥ Wireless and Optical Communications Networks，2008.WOCN＇08.5th IFIP International Conference on.IEEE，2008：1－6.

［4］ Yassein M B，Nimer S F，Al－Dubai A Y.ANew Dynamic Counter－based Broadcasting Scheme for Mobile Ad Hoc Networks［J］.Simulation Modelling Practice and Theory，2011，19（1）：553－563.

［5］ Liu H，Jia X H，Wan P J，et al.A Distributed and Efficient Flooding Scheme Using 1－hop Information in Mobile Ad Hoc Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2007，18（5）：658－671.

［6］ Zhang Lei，WangXuehui，Dou Wenhua.A Broadcast Algorithm Based on Primary－secondary Dominators for Wireless Ad Hoc Networks and its Optimization［J］.Chinese Journal of Computers，2006，11（29）：1920－1928.

［7］ Durresi A，Paruchuri V K，Iyengar S S，et al.Optimized Broadcast Protocol for Sensor Networks［J］.IEEE Transactions on Computers，2005，54（8）：1013－1024.

［8］ Liu Jingyong，Li Lemin，Jing Xiaorong.Space－covered Broadcast Algorithm without Neighbor Information in Multi－hop Wireless Networks［J］.Journal of Electronics＆Information Technology，2010，10（32）：2434－2439.

［9］ Khabbazian M，Bhargava V K.EfficientBroadcasting in Mobile Ad Hoc Networks［J］.IEEE Transactions on Mobile Computing，2009，8（2）：231－245.

［10］ Cai Y， Hua K A， Phillips A. Leveraging 1－hopNeighborhood Knowledge for Efficient Flooding in Wireless Ad Hoc Networks ［C］∥ Performance，Computing，and Communications Conference，2005.IPCCC 2005.24th IEEE International.IEEE，2005：347－354.