摘要
针对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.
出处
《系统仿真学报》
EI
CAS
CSCD
北大核心
2008年第5期1353-1356,共4页
Journal of System Simulation
基金
国家863高技术研究发展计划(2006AA01Z199)
国家973重点基础研究发展计划(2006CB303004)
国家自然科学基金(60673154)
江苏省自然科学基金(BK2005411)
江苏省高技术研究计划(BG2007391)
关键词
无线通信网络
自组织网络
广播路由算法
NP完全问题
启发式算法
wireless communication network
mobile ad hoc network
broadcast routing protoco
NP-Complete
heuristic algorithm
