移动自组网中一种网络生存时间最优的广播算法  

A Maximum Network Lifetime Broadcast Algorithm for Mobile Ad Hoc Networks

作　　者：焦贤龙[1] 王晓东[1] 周兴铭[1] 

机构地区：[1]并行与分布处理国家重点实验室,湖南长沙410073

出　　处：《计算机工程与科学》2011年第1期12-19,共8页Computer Engineering & Science

基　　金：国家973计划资助项目(2006CB303000)

摘　　要：移动自组网中广播操作的网络生存时间问题一直是备受关注的热点研究问题。现有的研究已经证明,基于最小生成树算法的广播算法能够最优地解决网络生存时间问题。但是,这些研究工作都是基于静止的网络拓扑,从而不适用于一些实际的网络拓扑动态变化的应用场景,如军事通信应用等。因此,针对节点移动导致的网络拓扑变化的场景,本文提出了一种移动自组网中网络生存时间最优的广播算法LONG。该广播算法基于移动预测和最小生成树算法的基本思想,并使用菲波那契堆来实现。通过理论分析,LONG广播算法获得最优的网络生存时间,并且其时间复杂性为O(n2),其中n表示网络中的节点数。最后,NS-2模拟实验结果表明,LONG广播算法在移动场景中的报文成功接收率和网络生存时间比其他广播算法更优。The network lifetime problem of broadcast for mobile ad hoc networks has always been an interesting and hot research topic.The？ existing research has proved that the broadcast algorithm based on the minimum spanning tree can optimally solve the network lifetime problem. However,these research activities are all based on static network topology,which is not suitable for some practical scenarios with changeable network topologies,such as the military communications. Therefore,for these scenarios,this paper proposes a maximum network lifetime broadcast algorithm called LONG for mobile ad hoc networks. This broadcast algorithm is based on motion prediction and the basic idea of the minimum spanning tree algorithm,and is implemented using the Fibonacci heap.A theoretical analysis shows LONG achieves the maximum network lifetime,and its time complexity is O（n2）,where？ n？ denotes the number of nodes in the networks. Finally,the results of the extensive simulation implemented by NS2 show that,the packet delivery ratio and the？ network lifetime of LONG are better than those of other broadcast algorithms.

关 键 词：移动自组网 广播算法 网络生存时间 最小生成树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]