多跳无线网络中基于分支限界法的广播算法

Broadcast Algorithm Based on Branch and Bound Method in Multi-hop Wireless Networks

现有的广播算法一般采用分层的方法构建近似的最多叶子最短生成树作为广播树。分析此类算法存在的不足,提出利用分支限界的思想建立最多叶子最短生成树引导广播操作的方法。分析和仿真结果表明,与基于分层的广播算法相比,基于分支限界法的广播算法具有更低的转发比且不增加广播树的深度,能更有效地节省带宽和能量资源。

The existed broadcast algorithms are based on the way of dividing the node into some layers. This paper discusses the drawbacks of the node layering algorithms, and proposes an efficient protocol of broadcast based on the branch and bound algorithm. With the branch and bound algorithm, the broadcast routing is determined on the basis of finding a maximum leaf shortest spanning tree. Analysis and simulation results show the algorithm can achieve a rather lower ratio of relaying node number to the whole node number compared with the layering node protocol, while keeping the layer number of the spanning tree on the same level, and save more energy and bandwidth resource.