1.6 移动Ad Hoc网络中的广播

1.6.1 MANET广播的作用与特点

1.广播在MANET中的作用

广播定义为将分组发送给网络中所有移动节点的操作。广播是一种常用的网络操作，是很多应用的常用操作，用于解决很多问题，比如图表曲线问题和分布式计算问题。广播广泛用于解决许多网络层问题。尤其是在MANET中，由于节点移动，所以更为频繁地使用广播（例如，寻呼某个特定的节点、发送告警信号、寻找到达某个特定节点的路由）。例如，路由协议DSR、ZRP、AODV依靠广播一个叫做路由请求（Route_Request）的UDP分组来搜索从源节点到达目的节点的路由。当传播这种路由请求分组的时候，移动节点一般会将自己的识别码ID添加到该分组中，因此就能够收集到合适的路由信息。

广播也可以用于LAN仿真，或者作为最后一种手段为拓扑迅速变化的网络提供多目标服务。

考虑一个MANET，网中各个移动节点共享一个单一的公共信道，使用载波侦听多址访问（CSMA）协议，但是没有使用碰撞检测（CD）协议。这种移动网络的同步不太可靠，不能得到整个网络的拓扑信息，用来支持和帮助做出广播操作的时间安排。所以，一个直接和明显的解决办法就是通过泛洪进行广播。如果盲目地进行泛洪，那么就可能出现严重的多余重播、信道竞争、传输碰撞问题。首先，由于无线传播是全向的，一个物理空间区域可能同时受到若干个移动节点的无线电波发射信号的覆盖，所以，很多重播是多余的。第二，由于重播的移动节点很可能在空间位置上比较接近，所以很可能存在严重的信道竞争问题。第三，由于RTS/CTS控制分组交互不适用，各个重播的定时密切关联，所以，极有可能发生传输碰撞。

2.MANET广播的特点

一个MANET网络由一组移动节点组成，各个移动节点常常可以相互通信。MANET网络没有基站。在MANET网络环境中，一个移动节点可以直接或者间接地与其他移动节点进行通信。如果是间接通信，那么就要使用多跳方案，从源节点发出的分组经过若干个中间节点的中继转发，最终到达目的节点。

广播问题就是将一条消息发送到网络中的其他移动节点。假定广播问题具有如下特性：

（1）广播随时随处自然进行。任何一个移动节点可以在任何时候发送广播消息。由于移动节点移动、无需同步之类的原因，所以准备任何类型的整个网络拓扑信息都是不可能的（事实上，这至少与广播问题一样困难）。事先能够获得的本地连通性信息非常少，甚至完全不可能。

（2）广播是不可靠的。没有采用应答机制。IEEE 802.11MAC技术规范没有要求在接收到广播分组后做出应答。但是，应该以最低代价将广播消息分发到尽可能多的移动节点。做出这个假设的目的是：①一个移动节点由于没有连接在网上而可能丢失广播消息，该节点短暂地与网络发生分割，或者经历反复碰撞；②应答可能在发送方周围产生严重的媒介竞争（因此，产生另一个“分组暴”）；③在很多应用中（例如，在DSR、ZRP、AODV等路由协议的路由寻找中），100%的可靠广播是不必要的。

较为严格的广播是可靠广播。可靠广播的目的是确保每个移动节点均接收到广播消息。移动节点之间相互交换高层应答。可靠广播协议通常在应用层实现。

（3）为了防止无休止地广播同一条消息，有必要假定移动节点具有检测广播消息拷贝的能力（移动节点也应该具有这种能力）。例如在DSR、AODV协议中，防止接收广播消息拷贝的方法是为每条广播消息设置一个数组（源节点识别码ID，序列号）。

在MANET中广播一个分组将触发周围其他移动节点广播这个相同的（或者被修改过的）分组。若盲目使用泛洪，则会发送很多多余消息，以及会发生严重的竞争/碰撞。因此，应该高效解决广播问题。

1.6.2 典型的的MANET广播技术

大致有四种方法实现MANET中的广播：简单泛洪、概率广播法、区域广播法、邻区信息广播法。简单泛洪要求每个节点重播全部分组。基于概率的广播法使用对网络拓扑的某种基本了解来给节点分配重播的概率。基于区域的广播法假定各个节点具有共享传输距离，一个节点只有在重播达到足够大的新覆盖范围的条件下才会重播。邻区信息广播法采用“Hello”分组维护邻区状态，邻区状态用于重播决策。

1.简单泛洪（Simple Flooding）

简单泛洪算法从一个源节点给其所有相邻节点广播一个分组开始。每个相邻节点又将这个分组重播给自己的所有相邻节点（只重播一次）。这个过程依此持续进行下去，直到全部可达网络节点接收到这个分组后才停止。

2.概率广播法（Probability-Based Broadcast Method）

（1）概率广播法。概率广播法类似于泛洪，只是节点按照预先确定的概率进行重播。在节点密集网络中，多个节点共享类似的传输覆盖范围；因此，任意使若干个节点停止重播能够节省节点和网络资源，同时又不会危害分组交付有效性。在节点稀疏网络中，共享传输覆盖范围少得多；因此，如果概率参数不高，那么使用概率广播法则会导致节点接收不到所有广播分组。

（2）计数器广播法。一个节点接收到一个广播分组的次数反比于该节点重播该分组所能够覆盖的新区域大小。这就是计数器广播法的基础。一个节点接收到一个新分组后，用一个随机数（RAD）初始化计数器，随机选择的RAD位于（0，Tmax）秒之间。在RAD秒计数期间，每当接收到一个多余的广播分组，则将计数器加1。若RAD结束时计数器小于某个门限值，则重播该广播分组；否则，丢掉该广播分组。门限值大于6表示可达新区域非常小。

计数器广播法最具竞争力的特点是简单且具有适应本地拓扑的内在能力。也就是说，在网络的节点密集区域，有些节点无需重播；在网络的节点稀疏区域，所有节点应该重播。

3.区域广播法（Area-Based Broadcast Method）

如果一个节点接收到一个离自己一米远的发送节点发送的分组，那么接收节点决定重播该分组，则其提供的新覆盖范围非常小。又如果接收节点位于发送节点传输距离的边界上，那么接收节点分组重播提供的新覆盖范围相当大，高达61%。采用区域广播法的节点能够根据全部所收多余发送估算新的覆盖范围。区域广播法只考虑发送的覆盖范围，而没有考虑该区域内是否存在节点。

（1）距离广播法。一个使用距离广播法的节点比较自己与每个先前已经重播一个给定分组的相邻节点之间的距离。根据所接收到的一个还未接收过的广播分组，初始化一个随机数（RAD）并存储多余的分组。当RAD结束的时候，检查所有源节点位置，是否存在小于门限距离的较近节点，如果存在，该节点不重播。

（2）位置广播法。位置广播法使用较为精确的期望新覆盖区域估计来决策是否重播。位置广播法要求每个节点必须具有确定自己位置的能力（如采用内置的GPS）。

一个节点只要产生或者重播一个分组的时候，就将自己的位置信息添加到该分组的分组头中。一个节点初次接收到一个分组后，记录发送节点的位置，计算出自己重播该分组所能够达到的新覆盖区域；如果新覆盖区域小于门限值，则该节点不重播，并且对随后接收到的该分组拷贝也不予重播；否则（新覆盖区域大于门限值），该节点设置一个随机数（RAD），然后再重播该分组。如果该节点在RAD期间接收到一个多余分组，则重新计算出新覆盖区域，并将其与门限值比较。在没有到达该分组的预定发送时间之前、或者在没有丢掉该分组之前，对所接收到的所有冗余广播重新进行新覆盖区域计算和门限比较。

4.邻区信息广播法（Neighbor Knowledge Broadcast Method）

（1）自行精减泛洪法（Flooding with Self Pruning，FwSP）。FwSP是最简单的邻区信息广播法，要求每个节点知道其一跳相邻节点的信息，这通过周期性广播“Hello”分组来实现。

节点在每个广播分组的分组头中列出自己已知的相邻节点。一个节点接收到一个广播分组后，比较自己的相邻节点列表和发送节点的相邻节点列表。接收节点若是没有需要到达的任何其他节点，则停止重播；否则，接收节点重播该分组。

（2）可扩展广播算法（Scalable Broadcast Algorithm，SBA）。SBA要求所有节点知道其两跳范围内相邻节点的信息。接收节点根据邻区信息和发送节点身份决定其重播是否能够到达新节点。通过周期性发送“Hello”分组来获取两跳范围内相邻区域信息。每个“Hello”分组包含本节点识别码（IP地址）以及已知相邻节点列表。一个节点接收到其所有相邻节点发送的“Hello”分组后，就获得以自己为中心的两跳拓扑信息。

假设节点B接收到节点A发送的一个广播数据分组。因为节点A是节点B的一个相邻节点，所以节点B知道节点A的所有相邻节点，节点A的所有相邻节点也接收到节点A发送的这个广播数据分组。如果节点B存在节点A广播还未到达的相邻节点，那么节点B使用一个随机数（RAD）来安排该分组的交付时间。如果节点B接收到另一个相邻节点发送的多余广播分组，那么节点B又重新决定其重播是否能够到达新节点。这个过程持续进行，直到RAD结束和分组被发送、或者将分组丢掉时才停止。

1.6.3 泛洪产生的广播暴

广播的直接转发法是通过泛洪来进行的。一个移动节点第一次接收到一条广播消息后必须而且应该重播这条消息。显然，网络中如果有 n 个移动节点，那么就需要将同一条广播消息广播n次。在CSMA/CA网络中，泛洪的缺点如下：

（1）多余的重播。当一个移动节点决定将一条广播消息重播给自己相邻节点的时候，所有这些相邻节点却已经有了该条广播消息。

（2）竞争。在一个移动节点广播一条消息后，如果其多个相邻节点决定重播该条消息，那么这些发送（全部离开附近的移动节点）可能产生严重的相互竞争。

（3）碰撞。由于没有采用退避机制，缺乏RTS/CTS控制分组交互，以及没有碰撞检测（CD），所以很可能发生碰撞，导致更严重的损害。

概括起来，把跟泛洪有关的这些问题称为广播暴问题（Broadcast Storm Problem）。下面说明广播暴问题的严重性。

1.多余重播分析

首先使用例子来说明重播的多余程度。在图1-5中，用链表示移动节点之间的连接，白色节点为源节点，灰暗节点为中继转发节点。在图1-5（a）中，白色节点只需要2 次发送就能够将一条消息广播完毕，但是，如果不减少多余广播的话，则需要进行4 次发送才能够完成一条消息的广播。图1-5（b）表示一个更加严重的情形：只需要2次发送就能够完成一个广播，但是，如果采用泛洪的话，则需要7次发送才能够完成一个广播。

产生这种多余广播的原因是：从不同天线发出的无线信号很可能相互重叠在一起。若一副天线覆盖的范围为一个圆，则使用图1-5（c）表明图1-5（b）的信号重叠问题。图中灰暗程度表示信号重叠程度。正如从图中所看到的，很多区域被同一个广播分组覆盖多次。在最坏情况下，一个区域被同一个广播分组覆盖多达7次。

下面通过分析说明重播的代价是非常高的，因此应该仔细采用重播。首先考虑图1-5（d）所示的情况：移动节点A发送一条广播消息，移动节点B决定重播这条消息。设SA表示移动节点A的无线电波覆盖范围，SB表示移动节点B的无线电波覆盖范围。移动节点B重播覆盖的其他区域为图中阴影区域，用SB−A表示。设r表示移动节点A和B的无线电波覆盖范围的半径，d表示移动节点A和B之间的距离。可以推导出|SB−A|=|SB|−|SA∩B|=πr2−INTC(d)，INTC(d)为中心点相距d的两个圆的交叉区域，

当d=r时，覆盖区域| B AS − |最大，等于

这说明了一个重要的事实：一次重播只能够提供0～61%的新覆盖范围（与前一次广播覆盖范围比较）。

求πr2−INTC(d)的平均值。假设移动节点B可以处于移动节点A的传输范围内任意位置；对上述求积分，积分区间为中心点在移动节点A的半径x的圆周[0，r]，得到平均值如下：

因此，经过前一次广播之后，一次重播平均只能够提供41%的新覆盖范围。

现在考虑一条广播消息被接收到2次的情况：假定移动节点C决定在接收到移动节点A和移动节点B的广播之后进行重播。移动节点C重播的覆盖范围为SC-(A∪B)。仿真研究指出，在移动节点C传输覆盖范围内随机地产生移动节点A和移动节点B，发现平均|SC-(A∪B)|≈0.19πr2（注意到：在仿真中，不能从积分得到覆盖范围的计算值，而是通过离散估计得到覆盖范围的计算值，离散估计将覆盖区域划分成一个一个的细微栅格进行近似计算）。这表明将一条消息重播到新的移动节点的概率是很小的。

一个移动节点在接收到同一条消息k次后再重播该消息的效果是：通过仿真，在移动节点X的覆盖范围内随机地产生k个移动节点，计算出移动节点X覆盖范围与另外k个移动节点覆盖范围总和之差。用期望新覆盖范围EAC(k)表示这个值（Expected Additional Coverage，EAC）。图1-6（a）表示仿真结果（仍然是通过细微栅格估计得到的）。从图1-6（a）中可以看到，当k≥4时，期望新覆盖范围EAC(k)低于5%。

2.竞争分析

为了研究竞争问题，考虑这样的情况：移动节点A发送一条广播消息，同时有n个移动节点在接收这条消息。如果所有这些移动节点都打算重播该条消息，那么由于在移动节点A周围的两个或者更多的移动节点很可能位置比较靠近而相互竞争无线媒介，因此可能发生竞争。

分析n=2的较简单情况。设移动节点B和C是两个接收节点，移动节点B可以处于移动节点A的传输范围内的任意位置。C为了完成与B的竞争，必须处在区域SA∩B内。所以，竞争概率等于|SA∩B|/(πr2)。设A和B之间的距离为x。对该概率积分，积分区间等于中心点在A的半径x的圆周[0，r]，得到竞争的期望概率为

显然，随着n的增大，竞争概率越高。在移动节点A的传输范围内任意产生n个移动节点，开始仿真试验。观测概率cf(n, k)，即这 n 个移动节点中有 k 个移动节点无竞争重播的概率（Contention-Free，CF）。仿真结果如图1-6（b）所示。从图中可以看到：全部n个移动节点有竞争的概率在n≥6的时候迅速大于0.8。所以，一个区域越拥挤（节点数越多），该区域内的竞争越严重。另一方面，有一个无竞争移动节点的概率[即，cf(n, 1)]随着n的增大而急速下降。而且，不大可能有更多的无竞争移动节点[即，cf(n, k)，k≥2]。注意：有k=n−1个无竞争移动节点意味着有n个这种无竞争移动节点，所以cf(n, n−1)=0。

3.碰撞分析

MANET网络没有基站和访问点（Access Point，AP）。因此，这里主要研究在IEEE 802.11分布式协调功能（DCF）作用下的性能。

CSMA/CA机制要求移动节点在以下情况正确启动退避进程：①刚好在该移动节点发送完一条消息之后；②当一个移动节点需要发送的时候，但是此时媒介却正处在忙状态，并且该节点正在执行前面已经启动的退避进程。在执行退避进程之前，必须首先从当前退避窗口中随机选择一个定时数值来设置退避定时计数器的值。如果该节点的干净信道评价（Clear Channel Assessment，CCA）机制检测到信道在过去的那个时隙（一段固定长度的时间）处于空闲状态，那么退避定时计数器减一。当退避定时计数器减到零的时候，则完成本次退避进程。

现在考虑多个相邻节点接收同一个节点X的一条广播消息的情况。有几种原因将引起碰撞。首先，如果节点X周围媒介空闲时间足够长，那么节点X的所有相邻节点均可能执行完其退避进程。因此，节点X的所有相邻节点在接收到一条广播消息（并且经过了DIFS周期）后，就可能全部在同一时刻开始重播。由于诸如RF时延和传输时延之类的原因而没有立即检测到载波，那么就极有可能出现碰撞。第二，由于在广播传输中没有预先采用RTS/CTS控制分组交互，所以碰撞损伤更加严重。第三，一旦发生了碰撞，由于没有碰撞检测机制，即使一个正在被发送的分组的前面已发送部分已经被碰撞损坏，但是节点仍将继续发送该分组。分组越长，信道资源浪费越多。

在通常的IEEE 802.11 MAC操作规范中没有注意上述问题，这或许是因为在这种场合下不需要考虑一点对多点通信。由于上述所有原因，所以MANET网络环境中的广播暴问题值得去深入和认真地研究。

1.6.4 广播暴问题的减轻方法

下面介绍的减轻广播暴问题的方法是禁止某些节点重播，以便降低重播的冗余度，从而减轻竞争和碰撞。下面介绍5 种减轻广播暴问题的策略。这些策略的不同之处在于：移动节点估计冗余的方法不同，如何收集信息以便帮助做出决策的方法不同。除了最后一种策略需要依靠一些本地连通性信息，其他所有策略都是全分布式操作。

1.概率方案

减少重播的一种直观方法就是使用概率统计重播方法。一个移动节点第一次接收到一条广播消息后，以概率p重播该条广播消息。显然，当p=1时，概率统计重播法就等效于泛洪法。

为了处理前面描述的竞争问题和碰撞问题，在重播该条广播消息之前应该等待一小段随机时延（若干个时隙），这样各个重播的定时就能够互不相同。

2.计数器方案

当一个移动节点在试图重播一条消息的时候，该条广播消息可能由于下述原因而受阻：媒介忙、退避进程运行，以及其他已排队等待发送的消息。因此，该移动节点在真正开始发送该条消息之前有机会多次接收到其他移动节点发送来的这条广播消息。

前面已经指出：一条消息被接收到k次后的期望新覆盖范围EAC(k)随着k的增大而迅速减小。当一个移动节点重播的期望新覆盖范围EAC(k)变得太小的时候，就可以防止该移动节点重播。这就是计数器方案的基础。特别是，使用一个计数器 c 来连续跟踪一条广播消息被接收到的次数，选择好计数门限值C。当c≥C时，禁止重播。该方案的详细描述如下：

第一步：当第一次接收到一条广播消息msg的时候，将计数器初始化为 c=1。在第二步中如果再次接收到该条广播消息msg，那么中断等待进程而执行第四步。

第二步：等待一段时间，该段时间等于随机的若干个时隙的长度。然后递交该条广播消息msg等待进行广播发送，一直等到真正开始广播发送该条消息msg为止。

第三步：该条广播消息msg在空中传输，结束进程。

第四步：计数器c加1。若c＜C，则重新进入第二步被中断了的等待进程。否则，若c=C，则继续执行第五步。

第五步：如果在第二步中递交该条广播消息msg等待进行广播，则取消该条消息msg的发送。禁止该移动节点随后重播该条消息msg。然后结束进程。

注意：第四步中的“重新进入第二步被中断了的等待进程”的意思是：该移动节点应该返回到第二步，等待一段时间，其长度等于该移动节点应该继续完成从中断点开始之后剩余进程所需的剩余时间。

3.距离方案

在计数器方案中，使用计数器来决定一个重播是结束，还是继续进行。而在距离方案中，使用移动节点之间的相对距离来决定一个重播是结束，还是继续进行。

例如，假定移动节点H第一次接收到移动节点S的一条广播消息。如果H和S之间的距离d非常短，那么H重播能够提供的新覆盖范围就非常少。如果d比较大，那么H重播能够提供的新覆盖范围就比较大。在极端情况下，即d=0，新覆盖范围也等于0。前面已经分析了距离d和新覆盖范围πr2−INTC(d)之间的关系。因此，可以将距离d作为一种参数，移动节点H使用这个参数来决定是否需要重播。

现在假定：在真正开始发送一条重播消息之前，该条消息已经被移动节点H接收到若干次。设H与发送该条消息的最近移动节点之间的距离为dmin。那么，H重播的新覆盖范围不会大于πr2−INTC(dmin)。可以使用dmin作为评估是否需要重播的一个参数依据。假设dmin的门限距离值为D，那么：当dmin<D的时候，移动节点H停止重播发送。该方案详细描述如下：

第一步：当第一次接收到一条广播消息msg的时候，dmin初始设置为到达该条广播消息msg的广播移动节点的距离。若 dmin<D，则跳到第五步继续进行。在第二步中，如果又接收到该条广播消息msg，那么中断等待进程，跳到第四步继续进行。

第二步：等待一段时间，该段时间等于随机的若干个时隙的长度。递交该条广播消息msg等待进行广播发送，一直等到真正开始广播发送该条消息msg为止。

第三步：该条广播消息msg在空中传输，结束进程。

第四步：如果离发送该条广播消息msg的移动节点的距离小于 dmin，则更新 dmin。如果新dmin<D，则进入第五步继续进行；否则，重新进入第二步被中断了的等待进程。

第五步：如果在第二步中递交该条广播消息msg等待进行广播，则取消该条消息msg的发送。禁止该移动节点随后重播该条消息msg。然后结束进程。

下面说明如何获取距离信息。一种可能的方法是根据所收消息的信号强度来估计。特别地，设消息的发送功率为 Pt、接收功率为 Pr。Pr=Pt(c1/d)nc2，n、c1、c2分别表示与物理环境、载波波长、天线增益有关的常数。因为Pr和Pt可以测量得到，所以可以根据这个公式估计出距离d。

因为知道距离和功率之间的关系，那么通过设置信号强度门限值，甚至可以用信号强度来直接代替距离。

4.位置方案

前面已经介绍了使用广播消息接收次数或者到达广播移动节点的距离作为重播决策的参数依据。如果能够获得广播移动节点的位置，那么就可以精确估算出新覆盖范围。这种方法可能需要定位装置（例如全球定位系统GPS接收机）的支持。

为了不失一般性，设一个移动节点的位置为（0，0）（这里仅采用二维位置来阐述；事实上，诸如GPS接收机之类的装置能够提供经度、纬度、海拔高度的三维位置）。假定一个移动节点从分别位于（x1, y1），（x2, y2），…，（xk, yk）的k个移动节点接收到k条相同的广播消息。可以计算出该移动节点重播该条消息所能够提供的新覆盖范围。设AC[（x1, y1），（x2, y2），…，（xk, yk）]表示被πr2除后得到的新覆盖范围，然后将其与预先定义的覆盖范围门限值A(0<A<0.61)进行比较，据此决定该接收移动节点是否需要重播。该方案详细描述如下。

第一步：当第一次接收到一条广播消息msg的时候，AC初始设置为该移动节点重播所能够提供的新覆盖范围。若AC<SA，跳到第五步继续进行。在第二步中，如果又接收到该条广播消息msg，那么中断等待进程，跳到第四步继续进行。

第二步：等待一段时间，该段时间等于随机的若干个时隙的长度。递交该条广播消息msg等待进行广播发送，一直等到真正开始广播发送该条消息msg为止。

第三步：该条广播消息msg在空中传输，结束进程。

第四步：更新AC。如果新AC<SA，则进入第五步继续进行；否则，重新进入第二步被中断了的等待进程。

第五步：如果在第二步中递交该条广播消息msg等待进行广播，则取消该条消息msg的发送。禁止该移动节点随后重播该条消息msg。然后结束进程。

使用上述方案的一个困难是计算AC的代价，这跟计算若干个覆盖圆范围之间的很多交叉区域有关。当有4 个覆盖圆范围的时候，这个问题就已经很困难了。一种可能的方法是使用栅格填充近似（Grid-Filling Approxomation）法进行估计。

一种选择方法是使用凸多边形（Convex Polygon）来决定是否应该进行重播。例如，如图1-7所示，假设移动节点X从移动节点A、B、C接收到同一条广播消息。图1-7（a）表明：如果移动节点X位于三个发送移动节点A、B、C构成的凸三角形内部，那么移动节点X重播的新覆盖范围非常小，甚至等于0。但是，在图1-7（b）中，如果移动节点X位于多边形外面，那么X重播很可能提供更大的新覆盖范围（阴影区域）。这些观察结果暗示：只有移动节点处在多边形外面的时候，该移动节点才会被允许重播。

下面通过几何计算证明上述凸多边形近似法的正确性。如果多边形检验禁止移动节点X重播（X在多边形内部），那么最坏情况下丢失的覆盖范围最多22%。经观察，当X处在多边形边界上的时候，新覆盖范围最大。设A和B是该边界上的两个端点。如图1-7（c）所示，如果A和B离X的距离各自等于传输距离r，那么新覆盖范围最大。计算出如图1-7（c）所示的阴影部分的面积。

因此，有理由说：当一个移动节点处在由先前发送节点位置形成的凸多边形范围内的时候，该节点重播所能够提供的新覆盖范围低于22%。

5.分群方案

上述方案是根据统计模型和几何学模型来估计一条广播消息的新覆盖范围。下面，说明如何使用图形模型来开发一种方法。特地采用分群概念来推导广播暴解决方案。

假定每个移动节点周期性地发送分组来通知其他移动节点自己的存在。因此，任何移动节点都能够自行确定自己与其他移动节点的连通性。每个移动节点有一个唯一的身份识别码ID。按照如下方法构成各个群。具有本地最小ID的移动节点自行选为群首。群首移动节点与其相邻移动节点形成一个群，相邻移动节点叫着该群的成员。在一个群内，能够与其他群内移动节点通信的成员叫着网关。为了仔细考虑移动性问题，当两个群首碰到一起的时候，ID较大的那个群首放弃其群首身份。图1-8表示一个分群的MANET网络例子。

现在回到广播暴问题。假定通过低层分群协议形成一个MANET网络的各个分群，并且得到有规律的维护。在一个分群内，群首在没有碰撞的条件下，其重播能够覆盖其群内所有其他移动节点。网关移动节点应该负责将广播消息传播到其他群内的移动节点，但是同时不需要非网关成员移动节点重播该消息。基于上述观察，广播暴问题的分群解决方案详细描述如下。

第一步：当第一次接收到一条广播消息msg的时候，如果该接收移动节点不是网关成员移动节点，那么禁止重播，结束进程。否则，该接收移动节点或者是群首、或者是网关成员移动节点，跳到第二步继续进行。

第二步：使用概率方案、计数器方案、距离方案、或者位置方案来决定是否需要重播。

把前面介绍的方案合并起来就得到分群方案。第一步是防止非网关成员移动节点重播，然后第二步进一步利用其他信息（比如新覆盖范围）来减少重播。

6.五种解决方案的评估

可达性（REachability，RE）：接收到一条广播消息的移动节点数量与从该条广播消息源节点直接可达或者间接可达的移动节点总数量之比。考虑可达性时应该仔细考虑网络分割问题。

重播节省（Saved ReBroadcast，SRB）：SRB=(r−t)/r，r 是接收到某条广播消息的移动节点数量，t是实际发送该条广播消息的移动节点数量。

与基本的泛洪法比较，在移动节点分布较密集的时候，简单的计数器方案能够排除很多多余的重播。距离方案的可达性性能优于计数器方案，但是节省重播数量却让人不满意。在所有的五种方案中，位置方案在各种移动节点分布条件下能够排除的多余重播数量最多，而不必对可达性进行平衡折中考虑，所以是最佳选择。

1）载荷的影响

第一，载荷越重，概率方案、计数器方案、距离方案、位置方案的可达性越低。因为载荷较重实际上意味着广播分组之间的竞争和碰撞也较严重。在移动节点密度较高的区域这种效果比在移动节点密度较稀疏的区域更加严重。这说明了广播暴问题的严重性。

第二，较大的区域能够将广播消息分发到较大的物理空间，因此，重播造成的竞争和碰撞程度就较低。