广播技术综述及解决广播风暴问题的方法

广播是无线传感器和Ad Hoc网络中的基本操作之一。它主要用于从一个节点（称为源节点），向网络中的其他节点传播消息。在传感器和执行器网络中，广播通常侧重于汇聚节点或执行器，它被转发给网络中所有的传感器或执行器。广播的应用包括寻呼特定主机或向网络中所有节点发送报警信号。通常情况下，无线传感器网络中的广播用于传播测量（如湿度和噪声水平）请求信息。当在协议中采用广播来传播诸如路由发现、路由维护、拓扑更新和同步等控制消息时，广播通常也称为洪泛。由于可以采用UDG对传感器网络和执行器网络进行建模，因而我们首先分别考虑传感器网络或执行器网络中的广播。然后我们将传感器和执行器网络作为单个异构网络来进行讨论。

由于节点能量有限导致无线传感器与执行器网络（WSAN）的传输范围受限，因而从源节点直接覆盖网络中所有接收方通常是不可能实现的。这样，许多节点只得充当路由器的角色，将广播消息中继给其邻居。广播消息逐跳进行传播，最终到达网络中的所有节点。广播的最简单实现方法是盲洪泛。在盲洪泛中，如果网络中的每个节点首次接收到广播消息，则它对洪泛消息进行重传。如果网络是连通的，且不考虑碰撞问题，盲洪泛能够保证网络中的所有节点能够接收到洪泛消息。但是，由于每个节点对洪泛消息进行重传，在密集网络中，可能会生成许多冗余数据包，导致严重的竞争和碰撞。参考文献（Ni et al.，1999）对该问题进行了研究，并将其称为广播风暴问题，如图2-10所示。假定节点A通过向节点B和C广播一条消息，发起一次广播过程。根据盲洪泛方案，如果节点B和C先前没有传送过洪泛消息，则它们重传该消息。需要注意的是，节点B和C必须竞争图2-10阴影区所示的广播媒体。节点D位于节点B和C的传输覆盖区域内。因此，如果节点B和C同时重传洪泛消息，则节点D无法准确接收该消息。同时，节点B和C会从节点A和对方收到消息的两个拷贝。这些冗余消息不仅会导致额外的能耗，而且会增加消息间的碰撞概率。事实上，无论节点B或节点C转播洪泛消息，都足以覆盖图2-10中的节点D。

图2-10 盲洪泛中的碰撞问题

为了解决广播风暴问题，研究文献中提出了诸多广播协议。实现高效广播的一种主要技术是骨干网广播（Stojmenovic et al.，2002）。通过使用任一建成的骨干网，可以实现这种广播技术。根据选择的算法不同，重传节点集可能是骨干网节点的一个子集，或者包含附加节点——网关，用于连接骨干网节点（如果这些节点尚未建立连接）。

根据中继节点选择方式，广播协议可以分为两类：基于发送方的协议和基于接收方的协议。在基于发送方的协议中，每个发送方推荐它的一个邻居子集作为下一跳中继节点。在基于接收方的协议中，洪泛消息的每个接收方独立决定是否应当转发消息。例如，邻居去除方案（Peng and Lu，2000；Stojmenovic and Seddigh，2000）和基于区域的无信标广播算法（Area-based Beaconless Broadcasting Algo-rithm，ABBA）（Ovalle-Martinez et al.，2006）是基于接收方的协议，而MPR协议（Qayyum et al.，2002）和高效洪泛协议（Liu et al.，2007）是基于发送方的协议。

基于每个节点保存的信息类型，广播协议又可以进一步分为三类：(www.xing528.com)

（1）不需要邻居信息；

（2）单跳邻居信息；

（3）两跳或更多跳邻居信息。

根据节点是否知道其绝对或相对地理坐标，邻居信息可进一步分为位置和拓扑信息。盲洪泛不需要任何邻居信息。基于区域的无信标广播算法（Ovalle-Martinez et al.，2006）也不需要邻居信息，但需要每个节点地理位置的可用性信息。高效洪泛协议（Liu et al.，2007）建立在单跳邻居信息基础之上。多点中继协议需要用到两跳拓扑邻居信息。邻居去除方案要么基于单跳信息（如果位置信息可用），要么基于两跳拓扑信息。

高效广播的一些技术预先不需要任何骨干网。但是，它们可以被看做是空中骨干网构建过程。它们使用节点的局部信息来消除冗余传输，从而降低能耗和碰撞概率。代表性成果是邻居去除方案、ABBA（Ovalle-Martinez et al.，2006）、高效洪泛方案（Liu et al.，2007）和基于树的广播（Ding et al.，2006）。下面将分别对其进行描述。