无线自组网广播通信方案综述

鲁顶柱 高静

（广东开放大学，广东广州，510091）

无线自组网广泛用于军事、灾害救援，以及车载网、无人驾驶、智能物流等重要领域。其自身的多跳性、节点移动且分布不均、拓扑变化快的特征使节点间通信变得困难，因而广播被广泛使用。无线自组网中的诸多应用都具有群组性通信特征，广播不仅被用来传递用户消息，还被用于进行资源调度、密钥分发、控制信息发布、路由查找。

除简单泛洪（ flooding）[1]方案外，无线自组网中的广播通信方案按其提供的可靠性保证情况可分为两类[2]：绝对可靠的方案（deterministic schemes）、提供某种概率可靠保证的方案（probabilistic schemes）。

泛洪是一种最简单的广播方案。在泛洪方案中，每个节点都把收到的广播数据向所有的邻居节点广播一次。由于无线信号传输在空间区域具有广播特性，因而那些在空间位置上接近的节点进行泛洪可能会引发大量的信道竞争。在无线自组网中，RTS/CTS控制分组交互不适用，简单的泛洪还可能造成大量传输碰撞，引发广播风暴[3]。绝对可靠的广播通信方案一般需要构建一种全局的拓扑结构（分发树、转发组）来分发广播数据，保证百分之百的分组投递率。但在节点频繁移动的动态网络环境中，数据转发所依赖的拓扑结构容易被破坏，因而需要使用大量的控制报文进行维护，浪费了网络带宽和节点的处理能力。提供某种概率可靠保证的方案只收集网络局部信息，而不需要维护全局的拓扑结构，受节点移动的影响小，对节点移动的敏感度低，能适应快速变化的网络环境。其缺点是无法保障绝对可靠，不适合可靠性要求高的应用。

以下对这两种类型的广播通信方案的基本原理进行阐述，并用NS2模拟器对典型方案进行仿真，对比各方案的可靠性、开销和端到端时延，分析各自的优缺点，归纳不同类型方案各自合适的应用场景。

一、绝对可靠的广播通信方案

绝对可靠的广播通信方案按其分发结构来的不同可以分为：（1）基于树结构的广播通信方案，（2）基于连通支配集的广播通信方案。

（一）基于树结构的广播通信方案

基于树结构的广播通信方案[4][5]一般包含三个过程：（1）节点获取网络的局部拓扑信息；（2）按某种原则构建广播数据的分发树；（3）优化并维护广播数据分发树。在分发树形成后，网络中的节点就分为两类：树干节点和叶子节点。在基于树结构的广播通信方案中，源节点的广播数据从树根沿着树干向整个网络传输，只有树干节点才需要转发广播数据，而叶子不参与转发。不同于传统有线网络集中式构建分发树，在无线自组网中的分发树构建需要所有节点分布式协作来完成。分发树的路径选择标准有多种：基于路径长度、基于链路稳定性、基于时延或带宽等。

MRT[5]算法构建广播树的主要思想是：选择邻居多的节点作为广播树上的树干节点，以减少转发次数和转发节点数目。算法首先选择邻居最多的节点作为树根，树根的邻居节点就变成了树叶加入树。然后在这些树叶中选择邻居节点（未加入树的节点）数最多的作为树的一级中间节点。接下来在所有树叶节点中用同样的方法迭代选出二级中间节点。中间节点的选择一直迭代下去，直到全网节点被完全覆盖。MRT构建的广播树易受节点移动影响而频繁重构，维护开销大。

（二） 基于连通支配集的广播通信方案

大部分绝对可靠的广播通信方案都是基于连通支配集方法的。在无线自组网中连通支配集构造方法主要有三种：自减裁（self-pruning）方法，极大独立集（maximum independent set）方法，邻居指派（neighbor-designating）方法。

1.自减裁方法

自减裁算法[6-8]的主要思想是：首先构造一个粗糙的连通支配集，然后减裁掉其中的冗余节点，最终形成较为精简的连通支配集。算法根据一个简单的启发式规则构造粗糙的连通支配集：如果节点v的任意两个邻居u，w之间都没有直接相邻，那节点v是支配节点。为了剔除粗糙的连通支配集中的大量冗余支配节点，文献[8]提出通用的冗余节点检测算法：若支配节点v的非支配节点邻居均可通过优先级更高的中间节点连接到其它支配节点，则v是冗余节点。

自减裁算法存在一些难以解决的缺点：

（1）计算复杂度与节点最大度的三次方成正比，当网络节点密度大时，计算复杂度高。

（2）节点在构造连通支配集的过程中需要收集邻居节点的中间状态信息，产生大量通信开销。

（3）算法得到的连通支配集冗余度大，容易形成环路。

2.极大独立集方法

I.stojmenovic算法[9]的主要思想是：先构造极大独立集，再将构造的极大独立集连接为连通支配集。算法将网络中所有的节点划分为支配节点和边界节点，在边界节点中，其两跳范围内的邻节点至少有两个支配节点。这样，算法可以挑选一个或两个边界节点将已选的支配节点连接起来，组成连通支配集。算法中分布式独立集构造过程如下：在算法开始时，节点将自己的优先级同邻居节点的优先级进行比较，若其邻居节点优先级均低于自己的优先级，则该节点确定自己为簇头，并通知邻居节点。节点优先级确定可以根据节点唯一的ID或节点度等不易重复、便于排序的数值大小来进行。邻居节点在接收到来自簇头的通知后，向自己的邻居节点发送广播，宣布自己为非簇头节点。一旦节点收到所有优先级比自己低的邻居节点广播的非簇头节点消息，则正式成为簇头，并向邻居节点转发广播数据。

通过以上过程可以分布式的将网络划分为多个极大独立集，再利用加权边法、支配区扩展法或其它的生成树算法将这些极大独立集连接起来，最终构成连通支配集。

3.邻居指派方法

LBA算法[10]的主要思想是：每个节点最多指定一个邻居节点来转发广播数据，被指定的节点必须转发接收到的广播数据；其他没有被指定的节点则根据自己的邻居剪枝状况（广播数据覆盖状况）自行决定是否转发。为了评估邻居节点被广播数据覆盖的状况，每个节点都需要为每个广播数据m维护一个列表。当节点u第一次接收到广播数据m时，初始化列表，将所有邻居节点ID添加到列表，并设置一个转发时延来收集邻居覆盖信息。在转发时延结束之前，节点u根据接收到的两跳邻居信息来更新列表，将已接收到广播数据的邻居节点从列表中剔除。如果在转发时延结束时，列表还不为空，那么节点u就转发广播数据m，并指派列表中的一个节点作为下一个转发节点；如果在转发时延结束时，列表为空，节点u将不再转发广播数据m。显而易见，在节点快速频繁移动的情况下，LBA算法很难让节点u正确判断自己的邻居是否被广播数据m完全覆盖，因此会转发大量冗余广播数据。

不论利用哪种方法产生连通支配集，算法复杂度都相当高，而且通信开销大。相对于树结构方案，基于连通过支配集的广播通信方案对节点移动的适应性更强。但网络拓扑快速频繁改变也会导致连通支配集的破坏，维护开销大，因而在节点高速移动的环境中性能受限。

二、提供某种概率可靠保证的广播通信方案

提供某种概率可靠保证的广播通信方案分四种：基于概率的方案（probability-based scheme），基于计数的方案（counter-based scheme），基于距离的方案（distance-based scheme），基于位置的方案（location-based scheme）。

（一）基于概率的方案

在基于概率的gossip[11]方案中，根据一些基本的拓扑信息，每个节点以固定的概率将接收到广播数据向自己的所有邻居节点广播一次。不同于简单泛洪中每个节点都转发广播数据，在gossip方案中，只有部分节点随机地参与广播数据的转发，节约了带宽，减少了冲突。但在异构的变化的网络环境中，固定的转发概率不能适应变化的网络状况，方案性能表现不佳。在DPA[12]，NKVB[13]方案中，节点的转发概率会根据网络环境动态改变，性能显著优于固定概率的方案。

NKVB方案通过hello报文收集一跳内的邻居信息，并据此实时计算节点的未覆盖邻居集合U(ni)，密度系数d(ni)、邻居节点未覆盖率Ru(ni)、未覆盖邻居数影响因子Fu(ni)等参数，利用所获参数动态实时调整节点的多播数据转发时延Td(ni)、基于邻居覆盖信息的转发概率pk(ni)，基于节点速度的转发概率pv(ni)。

其中N(nj)为节点nj的邻居节点集合，β和（1-β）分别是邻居节点未覆盖率和未覆盖邻居数影响因子对广播数据转发概率的影响系数。

其中Δ是一个较小的时延常数，N(r)、N(ni)分别为节点r（r为ni的上游节点）和ni的邻居节点集合，Rc(nri)为节点r和ni的公共邻居比率。

其中vi为节点ni的移动速度，为ni的邻居节点的平均移动速度，σ(ni)为ni的邻居节点移动速度的标准差，vmax(ni)为ni的邻居节点的最大移动速度。

（二） 基于计数的方案

在基于计数的广播通信方案DCB[14]中，节点根据自已的邻居节点数目来推测自己所在区域的节点密度状况（节点密集、节点密度中等、节点稀疏），并根据节点密度状况来设置接收重复广播数据次数阈值。如果节点处于密集区域，其阈值设为Cmax；如果节点处于密度中等区域，其阈值设为Cmid；如果节点处于稀疏区域其阈值设为Cmin，其中，Cmax＞Cmid＞Cmid。DCB的核心思想是：当一个节点在随机时延内重复接收到某个广播数据的次数大于所设置的阈值，那就意味自己的邻居节点应该都收到该广播数据，将不再进行转发，以降低冗余；如果一个节点在随机时延内重复接收到某个广播数据的次数小于自己的阈值，那就意味着该节点的部分邻居节点还没有接收到该广播数据，需要为这部分邻居节点转发这个广播数据，以保证可靠性。节点的快速移动易导致节点密度状况变化，阈值因不能实时更新而变得不准确，影响方案的性能。

（三）基于距离的方案

在基于距离的广播通信方案[15]中，首先根据网络环境预定义两种阈值空间：消息计数阈值空间（C1，C2，…，Cn）和节点距离阈值空间（D1，D2，…，Dn），并初始化距离门限D=D1。节点的广播数据转发概率是由自己与上一跳发送节点之间的相对距离决定的。该方案执行过程如下：

（1）当节点u第一次接收到来自节点v的广播数据m时，初始化dmin为节点u、v之间距离，并将计数器count的值设为1。如果dmin＜D，执行步骤（5）；如果dmin≥D，节点v设置一个随机时间，启动计时器，执行步骤（2）。

（2）等待计时结束。如果在等待的过程中收到重复的广播数据m，执行步骤（3）。计时结束后提交广播数据m，等待广播数据m的传输真正开始。

（3）count的值加1。

如果count的值小于C1，那么D=D1；

如果count的值小于C2，那么D=D2；

……

如果count的值小于Cn，那么D=Dn；

如果dmin＜D，执行步骤（5）；如果dmin≥D，执行步骤（2）。

（4）广播数据m开始，过程结束。

（5）节点v放弃转发广播数据m。如果已开始计时，中断计时。退出。

基于距离的广播通信方案[16][17]同样会因为节点移动造成消息计数阈值和距离阈值不准确，最终导致做出错误的转发决定。

（四） 基于位置的方案

基于位置的广播通信方案[18-20]通过设置广播转发延时来收集足够的邻居节点广播数据覆盖信息，以获得精确的额外覆盖率。

NCPR[20]方案通过在邻居节点之间周期性的交换hello报文来收集邻居节点信息。另外它还通过RREQ报文来收集邻居节点信息：在转发时延结束前，节点每接收到一个重复的RREQ报文时都会通过报文中的邻居节点列表来更新自己的未覆盖邻居集合。在NCPR方案中，节点的转发时延与上下游节点的公共邻居数成反比。那么，拥有较多邻居的节点的转发时延通常较小，而这些节点的转发概率却相对较大，因此与邻居较少的节点相比，它们需要在更短的时间内承担更多的业务流量，信道竞争加强，易引起冲突。当业务负载加重时，冲突就表现得更加明显。NCPR定义了网络连通系数和额外覆盖率两个参数，通过这两个参数来计算节点的广播数据转发概率。当节点密集，额外覆盖率较小时，转发概率应该取较小值；当节点稀疏，额外覆盖率较大时，转发概率应该取较大值。也即，网络连通系数与转发概率成反比，额外覆盖率与转发概率成正比。

三、仿真实验与结果分析

本节采用NS-2（v2.35）对 flooding，NKVB及LBA、DCB、NCPR进行仿真。实验模拟了节点移动速度对各方案的开销、端到端时延、分组投递率的影响，通过分析模拟结果来比较各方案的性能优劣。方案的性能参数定义如下：

（1）归一化广播开销：每个节点转发的所有报文（包括广播数据报文与控制报文）的字节数与所转发的广播报文字节数之比。归一化广播开销综合反映了每个节点上广播数据传输开销和控制开销大小。

（2）端到端平均时延：广播数据从源节点发出到被所有节点接收的平均时间间隔。

（3）分组投递率：收到广播数据的节点数与网络中所有节点数之比。

表1 模拟参数表

仿真采用了随机路点移动模型（Random Waypoint Model）来模拟节点的移动，节点被固定在1,000 × 1,000 m2的正方形区域内移动。置信度设定为95%，详细的模拟参数如表1所示。

1.节点移动速度对归一化广播开销的影响

图1 节点移动速度对归一化广播开销的影响

图1展示了节点移动速度对归一化广播开销的影响。实验结果表明：除 flooding方案外，其他方案的开销都随节点移动速度的加快而增加。节点的移动速度加快会导致网络拓扑变化随之加快，链路的稳定性下降，因而需要更多的控制开销来维护网络拓扑结构，保证有效的转发路径。而且，网络拓扑变化所导致的链路断开还会引发数据的重传。

当节点移动速度低于5m/s时，网络拓扑结构稳定，LBA维护支配集所需的控制开销小，传输开销也小。但随着节点移动速度的增大，拓扑变化也逐渐加快，维护支配集的控制开销增加。LBA为保证绝对可靠而发送大量冗余数据，造成冲突，传输开销同时增大，因而其归一化广播开销远高于其他方案。 flooding方案中每个节点都需将收到的数据广播一次，并且无控制开销，所以归一化广播开销不受节点移动速度影响。但 flooding方案转发的冗余数据是所有方案中最多的一个，所以其开销最大。

节点移动使得DCB方案对接收到的重复数据包计数错误，广播阈值定义不准确，从而导致冗余的转发并产生冲突，开销增加。与LBA不同，DCB的控制开销受节点移动影响小，因为它同NCPR、NKVB一样不需要维护全局的拓扑结构。

NCPR、NKVB仅需少量Hello报文维持松散的邻居关系，受节点移动影响小，在节点移动速度小于15m/s时，它们的控制开销变化小。除了低速度环境，它们的开销均比LBA和DCB少。NCPR方案的转发时延和转发概率计算方法容易导致负载集中于一部分节点，造成这部分节点需要在短时间内转发较多的业务流量，信道竞争加强，冲突增加。NKVB方案转发时延计算方法更加合理，使各个节点的负载分布更合理，降低了排队等待时间，缓解了信道的竞争，减少了冲突，使广播数据的转发更为有效。相比NCPR方案，NKVB方案的传输开销小，因此归一化广播开销小。

2.节点移动速度对端到端平均时延的影响

图2展示了节点移动速度对端到端平均时延的影响。随着节点移动速度的增加，拓扑的改变引起了分组的丢失，导致重传，增加了端到端平均时延。相比其他方案，对拓扑信息要求最高的LBA方案时延最大，DCB其次。NKVB的端到端平均时延明显小于NCPR，因为NKVB的转发时延选择方法更能有效获取邻居覆盖信息，并且它还选取了高速度节点参与广播数据的转发，加速了数据的传播。广播数据传输冲突是造成 flooding方案的端到端平均时延增加的主要原因。 flooding方案受节点移动影响小，图中曲线基本保持水平，但其时延是所有方案中最长的。

图2 节点移动速度对端到端平均时延的影响

3.节点移动速度对分组投递率的影响

图3展示了节点移动速度对分组投递率的影响。实验结果表明所有方案的分组投递率都随着节点移动速度的加快而减小。节点移动速度的加快使网络拓扑变化更加频繁，链路更加不稳定，投递率因而下降。LBA方案在获知全部邻居节点都接收到广播数据的情况下才放弃转发，故节点的移动会导致其转发概率比实际所需的值大。在移动性强的网络环境中，LBA方案转发概率严重偏高，而冗余又导致了冲突，分组投递率下降。节点的移动使得DCB方案的重复接收广播数据次数阈值和实际接收到的重复广播数据次数都变得不准确，因而引起了冗余的广播数据转发，并导致冲突和开销的增加，端到端平均时延增长，分组投递率下降。NCPR、NKVB只需维持松散的邻居关系，分组投递率受节点移动影响小。Flooding方案的分组投递率曲线基本水平，它受节点移动的影响最小，冲突是造成其分组投递率低于NCPR、NKVB方案的主要原因。

图3 节点移动速度对分组投递率的影响

四、结论

在低速环境中，绝对可靠的广播通信方案能提供高可靠性，数据传输效率高，其性能要优于提供某种概率可靠的方案。随着节点移动速度增大，绝对可靠的方案开销和时延上升，可靠性下降，节点移动速度越快，方案的性能越差。在节点快速移动的网络环境中，提供某种概率可靠保证的方案的可靠性、端到端平均时延和开销均优于绝对可靠的方案，它对节点移动的适应性更好。 flooding方案基本不受节点移动影响，能保持高可靠性，但开销和时延都是最大的，它适用于高移动性、高可靠性要求的网络环境。