作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (12): 107-09. doi: 10.3969/j.issn.1000-3428.2010.12.037

• 网络与通信 • 上一篇    下一篇

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

刘信新1,2,陈 鲲2   

  1. (1. 武汉大学计算机学院,武汉 430079;2. 武汉数字工程研究所,武汉 430074)
  • 出版日期:2010-06-20 发布日期:2010-06-20
  • 作者简介:刘信新(1974-),男,博士研究生,主研方向:无线传感器网络,嵌入式系统;陈 鲲,硕士
  • 基金资助:
    国家自然科学基金资助重点项目“可信移动互联网络的关键理论与应用研究”(60633020)

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

LIU Xin-xin1,2, CHEN Kun2   

  1. (1. School of Computer Science, Wuhan University, Wuhan 430079; 2. Wuhan Digital Engineering Institute, Wuhan 430074)
  • Online:2010-06-20 Published:2010-06-20

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

关键词: 多跳无线网络, 广播, 生成树, 分支限界

Abstract: 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.

Key words: multi-hop wireless networks, broadcast, spanning tree, branch and bound

中图分类号: