多跳无线网络中无需邻节点信息的空间覆盖广播算法

刘靖永 李乐民 景小荣

①(电子科技大学通信与信息工程学院 成都 610054)②(重庆邮电大学信号与信息处理重庆市重点实验室 重庆 400065)

1 引言

在多跳无线网络中，用传统的洪泛(flooding)方法实现广播会产生大量不必要的冗余转发，从而引发额外的冲突甚至造成网络拥塞，称为广播风暴(broadcast storm)问题[1]。广播风暴问题加剧了网络带宽和节点能量的消耗，同时，大量的冲突和网络拥塞造成丢包，加上无线信道引发的传输错误，严重降低了传输的可靠性。因此，减少转发冗余、提高广播的传输效率不但可以提高节点能量和网络带宽的利用率，而且能够减少冲突造成的丢包，从而提高广播的可靠性。

针对多跳无线网络中的广播风暴问题，近年来提出了很多改善传输效率的广播方法。这些方法主要分为以下几类：基于概率的方法(probabilitybased methods)[2]，基于面积(或距离)的方法(areabased methods)[1−4]以及基于邻节点信息的方法(neighbor information-based methods)[5−11]等。基于概率的方法中节点使用预定义的概率p或接收次数C决定是否转发广播包；基于面积的方法选择附加覆盖面积较大的节点优先转发。这两类广播方法不需要记录接收状态，无需维护节点邻节点信息，但是，由于使用预定义的门限值，在节点密度或网络负载变化时其性能会变差；并且转发节点之间由于不了解相互的位置关系，使得转发节点分布不合理，在某些非冗余节点出现错误时会导致丢包甚至无法继续转发[6]。基于邻节点信息的方法又分为邻节点指派方法(neighbor-designated methods)和自剪枝方法(self-pruning methods)[12]。邻节点指派方法由发送节点指定部分节点作为转发节点，比较典型的协议包括文献[6,7]中提出的方法和MPR[13]，边缘转发协议[14]等。自剪枝方法则由接收节点判断其邻节点是否都收到了广播包来决定是否转发，主要包括FSP[12]协议和基于最小连通支配集(MCDS)的方法[9−11]。基于邻节点信息的广播协议其基本思想是在发送节点的所有邻节点中，选择部分节点作为转发节点，使得所有两跳邻节点能够被这个转发节点集合覆盖[1]，本文称为基于节点覆盖的方法。基于节点覆盖的方法会产生过多的传输范围重叠(transmission overlap)，影响了传输效率的提高；而且，基于邻节点信息的协议需要节点维护一跳或多跳邻节点信息，一般通过节点发送和接收hello消息来实现，会增加额外的带宽和存储消耗，并且在节点密度增大时使协议性能降低；此外，邻节点指派方法通常选择靠近传输范围边缘的节点作为转发节点以增加附加覆盖面积，在节点移动频繁或信道状况出现变化时可能会导致转发节点出现传输错误而使转发失败。

本文提出了一种无需邻节点信息的空间覆盖广播(Space-Covered Broadcast，SCB)算法，该算法基于最优空间覆盖的思想，即通过优化转发节点的空间分布达到利用最少数目的转发节点实现对网络的覆盖，从而减少了转发节点个数和转发节点传输范围之间的重叠面积。通过分析，每个发送节点只需3个转发节点即可实现对整个网络空间接近双重的覆盖，能够保证较高的传输可靠性。基于空间覆盖的思想也使得SCB算法对节点密度和拓扑变化不敏感，具有较好的可扩展性。而且，SCB算法在接收节点处分布式选择最优的转发节点，能够评估信道的状态，有效地避免无线信道不稳定和传输范围边缘的灰色区域(gray zone)[4]等问题造成的传输错误，因此对物理信道的变化具有自适应性。此外，由于不使用邻节点信息且无需了解网络拓扑结构，SCB算法不产生额外的带宽和存储开销，减小了计算量。算法所需的唯一网络信息是节点的位置信息，可以通过GPS，虚拟节点位置方法以及接收信号强度等方法很容易获得。

本文以下部分首先分析理想情况下发送节点的最优分布方式，给出相应的广播方法；然后对实际网络中的SCB算法进行详细描述；最后对协议性能进行仿真和数值结果分析。

2 理想情况下最优发送节点分布方式及空间覆盖广播方法

假设网络中的节点是理想分布的，所有节点具有相同的传输半径R，本节对实现可靠广播的最优发送节点分布方式进行分析，给出理想情况下的最优转发方法。

2.1 最优发送节点分布方式

首先引入平面空间的圆盘覆盖问题，即用最少个数半径为R的圆盘无缝地覆盖整个平面的问题。如图1所示，将平面划分为边长为R的正六边形空间，在每一个正六边形处做外接圆，则外接圆的半径为R，圆盘的这种排列方式是实现对平面空间覆盖的最有效方式[15]。

把圆盘看作节点的传输范围，则节点分别位于每个圆盘的圆心，此时节点间的距离大于R，不能互相通信。将图1 中所有圆盘圆心位置移动到对应六边形的同一方位的顶点，可以分别得到图2中所有实线圆盘或所有虚线圆盘所示的两种排列方式，这两种圆盘排列方式与图1中所示的方式是等价的。将这两组等价圆盘按照网格对齐叠加在一起，如图2 所示，得到双重覆盖空间的最有效圆盘排列方法，即用最小数目的圆盘实现了对空间的双重覆盖。

把每个圆盘看作一个发送节点的传输范围，此时发送节点分别位于每个正六边形的顶点处，每个发送节点与3个其它发送节点互相连接。这种发送节点分布方式利用数目最少的发送节点实现了对网络的双重覆盖，并且发送节点传输范围之间的重叠面积也最小。此外，任意两个发送节点之间都有至少3条路径相连接，因此该分布方式保证了必要的连接冗余，即使少数节点失效仍可实现网络的完全覆盖，有利于增强容错能力。

2.2 理想情况下的最优空间覆盖广播方法

在节点分布理想的情况下，设置每个正六边形顶点处的节点为发送节点即可实现可靠的广播传输。如图3所示，理想情况下的最优空间覆盖广播方法为：数据包从源节点S以广播方式发出，经最近的3个节点转发；在每个节点转发之后由另外两个节点继续转发，位于重合位置的节点只转发一次；所有转发节点重复此过程，直到数据包到达网络边缘。

3 实际网络中的SCB算法

称图3中转发节点所在的位置为理想位置，转发节点的分布方式为理想分布。在实际网络中，节点是随机分布的，转发节点的位置通常会偏离理想位置，因此无法获得理想的转发节点分布。而由于理想情况下转发节点能够双重覆盖网络，少量节点无效时仍然能够完成广播。因此，在实际的网络中只要选择最靠近理想位置的节点作为转发节点，就可以尽量完全地覆盖网络，如图4所示。当节点密度较大时，转发节点的分布接近理想分布。

SCB算法的思想为：源节点以广播方式发送数据包；接收节点收到包后进行处理并通过延时转发机制实现转发节点的选择：首先根据发送节点和自己的位置信息计算一个转发时延，在此时延内如果再次收到该转发包则取消发送，否则仍以广播方式进行转发。由于不同位置的节点转发时延不同，通过时延差使得距离理想位置较近的节点优先发送，而较远节点的转发受到抑制，从而选择出最优的转发节点。同时，延时转发机制实现了错开不同转发节点发送时间的功能，从而减小了节点之间的干扰。此外，转发节点的选择在成功收到包的接收节点处实现，使得SCB算法能够自动适应信道状况，有效地避免信道变化造成的传输错误。

3.1 SCB算法的工作过程

(1)源节点以广播方式发送数据包，数据包中携带发送节点(sender)和上一跳发送节点(pre_sender)的位置坐标。

(2)节点接收到数据包后，检查是否已收到过该包，如果是则丢弃；否则将该包转交上层协议并进行转发。

(3)接收节点根据自己的位置坐标和sender以及pre_sender的位置坐标计算理想转发位置和发送时延。首先判断发送节点为是否为源节点，如果是则转到(4a)；否则转到(4b)。

图3 理想情况下的最优空间覆盖广播方法

图4 实际网络中转 发节点的分布

(4a)按3.2节中式(1)计算3个理想位置，然后分别计算到3个理想位置的最短距离，设为d，计算发送时延为delay=(d/R)⋅SCB_delay，其中SCB_ delay为算法预设的时延值，d/R称为时延因数，用df表示。

(4b)按式(3)计算3个理想位置，其中loc1为上一跳发送节点靠近的理想位置，因此只需分别计算到loc2和loc3的距离并找出最小值d。如果d≥R则节点距离loc1较近，因此不转发；如果d＜R，则发送时延为delay=(d/R)⋅SCB_delay 。

(5)接收节点设置转发计时器的值为delay，将该包加入转发队列。计时器超时则以广播方式转发该包；如果在超时之前接收到其他节点转发的该数据包则取消发送。

所有节点重复(2)到(5)的过程，直到数据包到达网络边缘，由于节点收到两次以上同一序号的包不进行转发，算法自然收敛。

3.2 理想位置的计算方法

发送节点为源节点时，设源节点位置坐标为(X, Y)，由于节点随机分布，在任何方向上其分布概率都是相同的，因此按图3中的位置计算3个一跳理想位置，分别为

发送节点不是源节点时，设节点N1为发送节点，N1从上一跳发送节点N0收到数据包，N0和N1的位置坐标分别为(X0, Y0)和(X1, Y1)。理想位置按如下方法确定：首先以N1为坐标原点进行坐标转换，如图5所示，N0转换后的坐标为(X0−X1, Y0−Y1)，令x0=X0−X1，y0=Y0−Y1，N1到N0的距离为d0=，N1N0与x轴夹角∠xN1N0为α，则cosα=x0/d0，角度α为

3个理想位置分别为

3.3 转发节点选择方法的改进

节点延时转发机制使得接收节点可以选择出最优的节点进行转发而排除其他节点的发送。然而，如果多个节点到某个理想位置的距离相近，而使发送时延间隔小于转发包的接收时延，可能出现多个节点几乎同时转发的情况。这种情况会造成冲突，影响协议性能。为了改善此问题，本文提出两种改进的方法：(1)用代替d/R计算时延因数，称为平方根距离方法(相应地，3.1节中的方法称为线形距离方法)。这种方法在d较小时能够增大不同节点转发时延的间隔，因而增强了区分能力。(2)增加角度判断，其目的是在距离相近的节点中优先选择靠近理想方向的节点，从而减小传输范围的重叠面积。如图6所示，S为发送节点，设节点n到理想位置N的距离为d，夹角∠nSN等于α，其时延因数为

其中A为预设参数且0＜A≤1，称这种方法为线形距离加角度方法，当A=1时，与线形距离方法相同。此外，将方法(1)，(2)相结合得到平方根距离加角度方法，其时延因数为

图5 理想转发位置的确定

图6 距离加角度的转发节点选择方法

4 仿真及数值结果分析

基于ns-2平台(版本2.29)对SCB的性能进行了仿真分析。仿真参数设置如下：无线传播信道采用two-ray ground reflection 模型；MAC层采用IEEE 802.11协议；无线信道的带宽为缺省值2 Mbps；节点传输范围为250 m；数据包长度采用固定值256 byte；网络负载设置为10 pkt/s。每次仿真运行时间为150 s，结果为100次运行的平均值。性能评价参数为送达率(delivery ratio)，转发率(forwarding ratio)和传输时延(transmission delay)。送达率用来评价协议的传输可靠性，定义为成功接收到数据包的节点数与网络节点总数的比值，每次运行的结果为所有数据包的平均值。使用转发率来评价协议的转发效率，其定义为转发节点的平均个数对网络节点总数的比值。传输时延定义为所有接收节点的端到端时延的平均值，用来描述协议完成数据包广播的时延特性。

首先对转发节点选择方法进行仿真，分析各种转发时延计算方法在不同网络环境下对算法性能的影响，找出获得较好性能的选择方法和协议参数。然后，将SCB算法与3类广播方法的典型协议(分别为无状态的洪泛协议[16]，基于1跳邻节点信息的边缘转发协议[14]和基于2跳邻节点信息的CDS-based广播协议[9])进行仿真比较，对SCB算法的性能进行验证。

4.1 转发节点选择方法的性能比较

转发节点选择方法分别为线性距离方法(1.0 Linear)、平方根距离方法(1.0Sqrt)、线性距离加角度方法(0.5 Linear)和平方根距离加角度方法(0.5 Sqrt)。通过仿真分析各种方法在不同节点密度下的性能。网络环境为200到1000个节点随机分布在面积为1000 m×1000 m 的正方形区域内，节点最大速度为20 m/s，参数A设为0.5，SCB_delay取值为0.2 s。仿真结果分别示于图7，图8和图9。

由图7可见，几种选择方法都能获得较高的送达率；随着节点个数增加，由于转发节点分布趋于理想分布，具有更好的覆盖效果，送达率也随之提高；线性距离加角度方法性能较好，在节点个数大于400时送达率超过99%，节点个数为1000时接近100%。图8中，几种选择方法的转发率都随着节点密度的增大而减小，这是由于转发节点数目主要与网络面积有关，并且随节点密度增大而减少并趋于最小值；不同方法相比，线性距离加角度方法仍然是最优的。图9显示了几种选择方法下广播包的传输时延。对每种方法而言，节点密度对时延影响不大，说明协议的时延特性具有稳定性；而对于不同的选择方法，传输时延存在明显的差别，0.5 Linear方法具有较好的性能。综合以上分析，增加角度判断能够获得较好的转发节点分布，提高算法性能；而平方根距离方法在节点密度较小时未能提高性能，其原因是节点密度较小时节点到理想位置的距离偏大，而平方根距离方法在d较小时才能增加区分能力，而在d较大时与线性距离方法相比得到的时延因数df会增大。SCB_delay是协议预设的时延参数，SCB_delay取值较小时，转发时延较小，节点之间的时延间隔也较小，区分能力降低；SCB_delay取值较大时，不同节点之间的转发时延间隔也较大，具有较好的区分能力，但取值过大会增加转发时延且增加不同序号转发包冲突的机会。通过仿真，SCB_delay取值为0.1 s到0.2 s时算法的送达率，转发率和传输时延都能获得较好的值。

图7 不同节点选择方法下的送达率

图8 不同节点选择方法下的转发率

图9 不同节点选择方法下的传输时延

4.2 SCB与几种广播协议的性能比较

首先对SCB，洪泛协议，边缘转发协议和基于CDS的广播协议在不同节点密度的条件下进行仿真比较。200到1000个网络节点随机分布在面积为1000 m×1000 m 的正方形区域内，节点最大速度仍为20 m/s。仿真结果示于图10和图11。由于洪泛协议的转发率为100%，因此在图11和图13中省略。

图10显示，SCB的送达率明显优于其他对比协议，节点个数为200时即可获得99%的送达率，并且随节点数个增加而增大并趋于100%；而其他协议在节点个数为200时送达率最高且只有大约90%。这是由于当节点密度增大时，3种对比协议的转发次数增加，使得网络中出现较多的冲突，因此3种协议的送达率都随节点数目增加而降低；相反地，SCB算法基于空间覆盖的思想，随着节点密度增加，转发节点的分布趋于最优分布使得覆盖效果更好，因此其送达率也增大。图11中，SCB算法的转发率明显低于其他对比协议。节点数为200时，基于CDS的广播协议和边缘转发协议的转发率分别为大于70%和接近90%；而SCB的转发率只有11.7%，并且随着节点数增加而迅速降低。这是由于SCB优化了转发节点分布，明显减少了转发次数，因此具有更高的转发效率；并且随着节点密度增大，转发节点个数减少并趋于最小值。

在不同的网络规模和网络负载条件下对几种协议的性能进行了比较。图12显示了不同的网络规模下3种协议的转发率，其中节点密度设定为1000m2/节点，网络面积分别设置为200,000m2到1000,000m2，相应的节点个数分别为200到1000；节点最大速度为20 m/s。在各种网络规模下SCB的转发率明显低于另外两种对比协议。此外，由图12可以看出，SCB与边缘转发协议具有较好的可扩展性，当网络规模增大时，转发率呈现缓慢下降的趋势；而基于CDS的广播协议在网络规模增大时，转发率明显增加，因此其可扩展性较差。图13显示了网络负载不同时协议的送达率，其中网络负载分别为1 pkt/s到20 pkt/s，网络环境为1000个节点随机分布在1000 m×1000 m 的网络区域内。由图13可以看到，所有协议在负载较低时都能获得较高的送达率，随着网络负载增加，所有协议的送达率均降低，这是由于随着负载增大网络中出现了更多的冲突；网络负载较大时，SCB的送达率明显高于洪泛协议，边缘转发协议和基于CDS的广播协议。

图10 节点密度与协议送达率

图11 节点密度与协议转发率

图12 网络规模与协议转发率

图13 网络负载与协议送达率

5 结束语

无状态的广播协议由于不需要维护邻节点信息因而容易实现，但可能会造成转发节点分布不合理，导致节点丢包；基于邻节点信息的广播协议在节点密度较大时会增加冲突机会，使协议性能下降；邻节点指派方法在信道状况出现变化时可能导致转发节点出现传输错误而使转发失败。本文提出了一种不需邻节点信息的空间覆盖广播(SCB)算法，SCB通过优化转发节点的空间分布使转发节点的个数最小化，在保证较高送达率的前提下明显降低了转发次数；同时，SCB算法由于无需邻节点信息，减少了网络带宽和存储计算等开销；此外，转发节点选择过程在接收节点处分布式完成，能够自动适应信道状况，避免信道变化造成的传输错误，增强了算法的实用性。

[1] Heissenbüel M, Braun T, Wälchli M, and Bernoulli T.Optimized stateless broadcasting in wireless multi-hop networks [C]. Proc. IEEE INFOCOM2006, Barcelona,Spanish, April 23-29 2006: 1-12.

[2] Khan I A, Javaid A, and Qian H L. Distance-based dynamically adjusted probabilistic forwarding for wireless mobile Ad Hoc networks [C]. IEEE and IFIP WOCN’08,Surabaya, Indonesia, May 5-7, 2008: 1-6.

[3] Liarokapis D, Shahrabi A, and Komninos A. DibA: An adaptive broadcasting scheme in mobile Ad hoc networks [C].Communication Networks and Services Research Conference 2009, Moncton, Canada, May 11-13, 2009: 224-231.

[4] Durresi A, Paruchuri V K, Iyengar S S, and Kannan R.Optimized broadcast protocol for sensor networks [J]. IEEE Transactions on Computers, 2005, 54(8): 1013-1024.

[5] Liu H, Jia X H, Wan P J, Liu X X, and Yao F. 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] Khabbazian M and Bhargava V K. Efficient broadcasting in mobile Ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2009, 8(2): 231-245.

[7] al-Humoud S O, Mackenzie L M, and Abdulai J.Neighbourhood-aware counter-based broadcast scheme for wireless Ad hoc networks [C]. IEEE GLOBECOM 2008 Workshops, New Orleans, USA, Nov. 30-Dec. 4 2008: 1-6.

[8] Lee Y, Shim Y, Choi Y, and Kwon T. A reliability aware flooding algorithm (RAFA) in wireless multi-hop networks[C]. IEEE Symposium on Computers and Communications 2008, Marrakech, Morocco, July 6-9, 2008: 1070-1075.

[9] Stojmenovic I, Seddigh M, and Zunic J. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(1): 14-25.

[10] Thai M T, Wang F, Liu D, Zhu S, and Du D Z. Connected dominating sets in wireless networks with different transmission ranges [J]. IEEE Transactions on Mobile Computing, 2007, 6(7): 721-730.

[11] Yang H Y, Lin C H, and Tsai M J. Distributed algorithm for efficient construction and maintenance of connected k-hop dominating sets in mobile Ad hoc networks [J]. IEEE Transactions on Mobile Computing, 2008, 7(4): 444-457.

[12] Dai F and Wu J. Performance analysis of broadcast protocols in Ad hoc networks based on self-pruning [J]. IEEE Transactions on Parallel and Distributed Systems, 2004,15(11): 1-14.

[13] Kadi N and Al agha K. Optimized MPR-based flooding in wireless ad hoc network using network coding [C]. Wireless Days 2008 1st IFIP, Dubai, UAE, Nov 24-27, 2008: 1-5.

[14] Cai Y, Hua K A, and Phillips A. Leveraging 1-hop neighborhood knowledge for efficient flooding in wireless Ad hoc networks [C]. Proc. IPCCC 2005, Phoenix, Arizona,April 7-9, 2005: 347-354.

[15] Kershner R. The number of circles covering a set [J].American Journal of Mathematics, 1939, 61(1): 665-671.

[16] Ho C, Obraczka K, Tsudik G, and Viswanath K. Flooding for reliable multicast in multi-hop Ad hoc networks [C]. Proc.DiaLM99, Seattle, USA, 1999: 64-71.