k-冗余结构无线自组网广播算法研究  

k-Resilient Algorithm of Mobile Ad Hoc Network Broadcasting

作　　者：杨盘隆[1,2] 陈贵海[1] 史春丽 田畅[2] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,计算机科学与技术系,江苏南京210093 [2]解放军理工大学通信工程学院电信工程系,江苏南京210007 [3]总参通信工程设计研究院,辽宁沈阳110005

出　　处：《系统仿真学报》2008年第5期1353-1356,共4页Journal of System Simulation

基　　金：国家863高技术研究发展计划(2006AA01Z199);国家973重点基础研究发展计划(2006CB303004);国家自然科学基金(60673154);江苏省自然科学基金(BK2005411);江苏省高技术研究计划(BG2007391)

摘　　要：针对k-冗余连接路由算法的特点,对最优广播树的生成算法进行了研究。首先根据最优广播树的数学模型,证明了它是一个NP难题(NP-Complete)。然后针对网络拓扑的特点提出了启发式广播树生成算法。针对算法的特点,分析了算法复杂度和算法的效率。结合GlomoSim仿真平台,在无线网络环境下对算法的效率进行了仿真,将协议的性能与简单广播算法进行了比较。仿真结果表明,启发式广播算法能够减小网络开销和节点的转发次数,提高网络的传输效率。Characteristic of k -resilient mechanism are seriously considered with the problem of optimum broadcast tree generation. An analytical mathematical model is provided at first, and according to this model, we prove that the optimum multicast tree generation problem is NP-Complete. Considering the characteristics of the network topology, we propose a heuristic algorithm in dealing with them. The complexity and efficiency of the heuristic algorithm is analyzed. With the GlomoSim simulation platform, the algorithm is implemented and applied in the wireless network scenario. Simulation results show that the heuristic algorithm can effectively reduces the network overhead and the forwarding times of nodes in the network, and the efficiency of the network is achieved.

关 键 词：无线通信网络 自组织网络 广播路由算法 NP完全问题 启发式算法 

分 类 号：TN925.93[电子电信—通信与信息系统] TP391.9[电子电信—信息与通信工程]