陈明刚,张陆勇,刘 贺,陈 鹏

(北京邮电大学信息与通信工程学院,北京100876)

0 引言

无线网状网(WMN)中,每个节点都可以在其他节点协助下以多跳方式与网络中任何节点进行通信。由于WMN的多跳特性,传统的泛洪(Flooding)广播会占用大量的网络资源。在WMN中,带宽是宝贵的资源,有效利用带宽,对提升网络性能十分关键。文献[1]提出了一种高效的广播机制:多点中继广播。多点中继广播在保证全网节点都收到广播分组的前提下,通过减少参与转发广播分组的节点数目来降低广播对网络的影响。同时文献[1]证明多点中继集的选取是一个NP完全问题,研究人员提出了不同的启发式算法来解决这个问题。其中文献[1]使用了一种贪婪构造算法来选取多点中继集合。除了贪婪算法,一些现代的启发式算法也被积极运用到多点中继集的选取中来。文献[1]使用遗传算法来解决多点中继集的选取问题,文献[2]应用蚁群算法解决这个问题。

多点中继集是多点中继广播机制实现的关键。目前基于图论中最小控制集理论的多点中继集是包含有最少1跳邻居节点数目的集合。在WMN中,存在不同1跳邻居节点对相同2跳邻居节点的重叠覆盖现象,导致同一个2跳邻居节点会从不同的1跳邻居节点接收到相同的广播分组。这不但会造成带宽和节点能量的浪费,甚至会引起分组碰撞,导致消息接收失败,影响广播的质量。但包含节点数目最少的多点中继集并没有考虑重叠覆盖的影响。……