计算机工程 ›› 2010, Vol. 36 ›› Issue (2): 108-109.doi: 10.3969/j.issn.1000-3428.2010.02.038

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

Ad hoc网络中基于标号的组播路由算法

刘 涛,林 琳,周贤伟,彭 莱   

  1. (北京科技大学信息工程学院通信工程系,北京 100083)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-01-20 发布日期:2010-01-20

Multicast Routing Algorithm Based on Label in Ad hoc Network

LIU Tao, LIN Lin, ZHOU Xian-wei, PENG Lai   

  1. (Department of Communication Engineering, School of Information Engineering, University of Science and Technology Beijing, Beijing 100083)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-01-20 Published:2010-01-20

摘要: 针对Ad hoc网络中最小带宽消耗组播路由问题,给出一个基于标号优化的启发式算法(LOHA),介绍标号规则及修改节点间邻接关系规则,通过修改组播树中节点的标号来减少树中的转发节点数,从而最小化带宽消耗。该算法的时间复杂度为O(n3),从转发节点个数和平均跳数2个方面比较LOHA及广度优先搜索算法所生成的组播树。实验结果表明,LOHA得到的组播树带宽消耗较少。

关键词: Ad hoc网络, 组播树, 启发式算法, 带宽消耗

Abstract: Aiming at the problem of multicast routing with minimum bandwidth consumption, a Label Optimization based Heuristic Algorithm(LOHA) is proposed, including labeling rule and the modified rule of adjacent relationship between nodes. It minimizes bandwidth consumption by modifying the labels of the nodes in the multicast tree. The time complexity of LOHA is O(n3). The multicast trees obtained by LOHA is compared with Breadth-First-Search(BFS) algorithm from two aspects such as the average forwarding node number and the average hop number. Experimental results show the multicast tree obtained by LOHA consumes less bandwidth.

Key words: Ad hoc network, multicast tree, heuristic algorithm, bandwidth consumption

中图分类号: