军用无线自组网中链路感知的全网广播研究

王辛果

【摘要】 全网广播是一种非常重要的通信模式，可广泛应用于全网通告、寻呼、路由发现等。在军用无线自组网中，可靠传输非常重要，全网广播需要确保所有节点都能正确收到广播消息。然而，由于高速移动、强烈干扰等原因，实际的无线链路非常不可靠，有时需要多次重传，降低了传输效率。如何高效地实现全网可靠广播是军用无线自组网中需要亟待解决的问题。本文提出了一种高效的全网可靠广播协议，该协议采用基于链路感知的连通支配集选择算法，产生更高效的广播虚拟骨干网。

【关键词】 无线自组网 可靠广播 连通支配集 链路感知

The Research of Link-Aware Network-Wide Broadcast in Military Wireless Ad hoc Networks WANG Xin-guo （Southwest China Institute of Electronic Technology， Chengdu 10036）

Abstract： Network-wide broadcast is a very important pattern， and can be applied in network-wide notification， paging， routing discovery， and etc. In military wireless ad hoc networks， reliable transmission is very important and network-wide broadcast must ensure all nodes can receive the broadcasting message. However， due to high mobility and strong interference， the factual wireless links are not reliable， multiple retransmissions are sometimes needed and that decreases the efficiency. How to implement network-wide reliable efficiently is a key problem for military wireless ad hoc networks. This paper proposes a link-aware network-wide broadcast protocol （LANWB）， which uses a link-aware connected dominating set election algorithm to generate the more efficient broadcast backbone.

Keywords： Wireless ad hoc network； Reliable broadcast； Connected dominating set； Link-aware

一、引言

全网广播是单个节点向网络中所有节点发送消息的通信模式，可广泛应用于全网通告、寻呼、路由发现等。在军用无线自组网中，全网广播要保证所有节点都能够正确接收消息，即实现全网覆盖。然而，由于节点高速移动、强烈的敌方干扰等原因，实际的无线链路经常发生丢包。为了实现可靠传输，可能需要进行多次重传，这降低了传输效率。

全网广播协议大致可分为全网洪泛、概率转发、骨干转发等三类[1]。全网洪泛是让网络中所有节点都参与转发广播消息，虽能实现全网覆盖，但会引发广播风暴，传输效率太低。概率转发为每个节点分配参与转发的概率，虽能减少广播转发次数，但很难保证全网覆盖。在骨干转发的协议中，由于每个节点或者是骨干节点，或者至少与一个骨干节点直接相邻，且所有的骨干节点保持连通，每个骨干节点只转发一次就能实现全网覆盖。

二、单跳模型

发送节点重复广播发送消息，直到所有N个邻居节点R={r1， r2， …， rN}都正确收到该消息。接收节点采用ARQ（Auto Repeat Request）机制反馈消息的接收状态。假设发送节点到N个邻居节点的丢包率分别为e1， e2， …， eN。将节点ri成功接收消息时的传输次数记为随机变量Xi，则N个邻居节点都收到该消息时的传输次数记为随机变量Y=maxi∈{1，2，…N} Xi。

假设各条链路的丢包事件相互独立，则

PY≤m=Pmaxi∈1，2，…NXi≤m=i=1N（1-eim） （1）

因此，Y的平均值为

三、虚拟骨干网

已有的全网广播协议认为虚拟骨干网的规模越小，转发次数越少，广播效率越高，因而协议的重点是生成节点数最少的虚拟骨干网。文献[5]已经证明根据全网拓扑生成最小虚拟骨干网是NP难（Non-deterministic Polynomial）问题，只能寻找近似最优算法。此外，由于获取和维护全网拓扑的开销很大，通常只能使用基于局部拓扑的分布式算法，这增加了生成最小虚拟骨干网的难度。如果考虑无线链路存在丢包，最高效的虚拟骨干网不是成员数最少的虚拟骨干网，而是总传输次数最少的虚拟骨干网。下面将介绍一种基于链路感知的虚拟骨干网生成算法，减少总传输次数。与其他的分布式生成算法[4]类似，基于链路感知的虚拟骨干网生成算法分为初始阶段和剪枝阶段。在初始阶段，根据2跳邻居信息构建连通度较高的初始骨干网；在剪枝阶段，再根据链路状态，从支配集中删除不必要的低效骨干节点。为方便描述，将节点u的1跳邻居节点集记为。

3.1初始阶段

在初始阶段，每个节点周期性广播HELLO消息。其中，包含了本节点id以及本节点的邻居节点id。如果节点u存在两个邻居节点v， w彼此不相邻，则节点u成为初始骨干节点。不难证明，如果原来的网络连通，则初始骨干节点组成的子网也保持连通。如图1所示，节点p， v， w， z成为初始骨干节点。

3.2剪枝阶段

每个初始骨干节点通过统计HELLO消息的正确接收比例或信号强度估算本节点到所有邻居节点的丢包率，并计算得到本节点的广播效率：

η=NENY （3）

其中，N为邻居节点数，ENY为式（2）中计算得到的平均广播发送次数。η值越大，广播效率越高，在剪枝阶段成为最终骨干节点的优先级越高；η值相同时，id越大的节点的优先级越高。

如图2所示，c到d的丢包率较高导致c的广播效率较低，则c放弃成为最终的骨干节点。在文献[4，5]提出的算法的中，h不会成为骨干节点，但在本协议中h将成为骨干节点，这能避免因b到g的丢包率较高而造成大量重传。因此，节点b， f， h组成最终的连通支配集。由于链路层协议通常都会发送HELLO消息且包含上述两个阶段需要的信息，所以上述机制不会增加额外的开销。

四、全网广播协议

1、确认机制。广播消息由产生该消息的源节点id和序列号进行唯一性确定。在广播消息的帧头中，发送节点指明尚未确认收到该消息的邻居节点列表。由于每个节点可能与多个骨干节点相邻，节点以广播方式发送ACK消息进行统一确认。为了减少控制开销，骨干节点不发送ACK消息进行确认，而是通过转发该广播消息进行间接确认。因此，每个节点需要维护与其相邻的骨干节点列表以及邻居节点的接收状态表。

2、延时转发。由于每个节点可能与多个骨干节点相邻，从任一节点收到广播消息即可。骨干节点在转发广播消息前从[0，Tmax]中随机退避一段时间，其中Tmax与重发的次数呈指数关系，Tmax = Tw*2i-1。重传次数越多，重传前的退避时间越长。因此，延时转发能够自适应地利用虚拟骨干网的冗余性，减少冲突和转发次数。

五、仿真实验及结果分析

在边长为500m的正方形区域内，随机部署300个通信节点。每个节点的通信半径为50m。每条链路的丢包率为均匀随机分布，最小的的丢包率为0，最大的丢包率为0.05。图3中所示的是生成的虚拟骨干网示意图，大圆表示的是骨干节点，小圆表示的是非骨干节点。其中，骨干节点总数为144，骨干节点形成连通的虚拟骨干网，每个非骨干节点至少与1个骨干节点直接相邻。

接下来，比较LANWB协议与文献[3]提出的MI协议在全网可靠广播中的效率。网络区域为边长为200m，节点数在50到250之间。在不同网络规模下，两种协议广播每条消息至全网的总传输次数如下图所示。由于优先选择了效率更高的节点成为骨干节点和延时转发等，LANWB协议的总传输次数更少，因而广播效率更高。网络的节点密度越大，LANWB协议的优势越明显。

六、总结

本文提出了一种高效的无线自组网全网可靠广播协议，LAWNB协议。该协议采用了基于链路感知的连通支配集生成算法，选择广播效率更高的节点转发广播消息。仿真结果表明，在保证可靠传输的前提下，LAWNB比MI具有更高的广播效率。

参 考 文 献

[1] Wisitpongphan N， etc. Broadcast storm mitigation techniques in vehicular ad hoc wireless networks. [J] IEEE wireless communication. 2007， 14（6）： 84-94.

[2] Wan PJ， Wang L， and Yao F. Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. [C]// Proceedings of IEEE ICDCS conference， 2008， 337-344.

[3] Sakai K， etc. Timer-based CDS construction in wireless ad hoc networks. [J] IEEE transactions on mobile computing. 2011， 10（10）： 1388-1402.

[4] Dai F and Wu J. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. [J] IEEE transactions on parallel and distributed systems. 2004， 15（10）： 908-920.

[5] Hong J， etc. Minimum-transmission broadcast in uncoordinated duty-cycled wireless ad hoc networks. [J] IEEE transactions on vehicular technology. 2010， 59（1）： 307-318.