一种多跳无线网络中的高效广播算法

刘靖永; 李乐民

doi:10.3724/SP.J.1146.2008.01556

一种多跳无线网络中的高效广播算法

doi: 10.3724/SP.J.1146.2008.01556

基金项目:

国家重点基础研究发展973计划(2007CB307104, 2007CB307100)资助课题

计量
- 文章访问数: 3155
- HTML全文浏览量: 79
- PDF下载量: 1020
- 被引次数: 0
出版历程
- 收稿日期: 2008-11-26
- 修回日期: 2009-05-07
- 刊出日期: 2009-12-19

An Efficient Broadcast Method in Multi-hop Wireless Networks

摘要

摘要: 广播是多跳无线网络中的一种基本操作。现有的广播算法中普遍存在转发冗余过多的问题。该文首先分析了覆盖网络所需的最少转发节点数目，然后以此为基础，提出了一种简单高效的广播算法。该算法中，每个节点最多只需选择3个转发节点，从而明显地减少了广播的转发次数，提高了节点能量和网络资源的利用率；同时，所有转发节点实现了对整个网络接近双重的覆盖，能够保证较高的传输可靠性；此外，对不同的网络规模和拓扑的动态变化，该算法具有较好的可扩展性。仿真结果显示，该算法在多种常见的网络环境下具有比现有方法更优越的性能。
- 无线网络; 多跳网络; 广播; 洪泛
Abstract: Broadcast is a common operation in multi-hop wireless networks. However, previous schemes either have much transmission redundancy or cost too much overhead. In this paper, the minimal number of forwarding nodes needed to cover a network is analyzed. On this basis, a simple broadcast method is proposed to increase significantly the transmission efficiency. In this method, each forwarding node only needs to select no more than three forwarding nodes. The set of forwarding nodes can provide nearly double coverage to all the network area thus provide high delivery ratio. In addition, it has excellent scalability in large scale networks and highly dynamic environment. Simulation results show that the method exhibits much better performance in variety of network conditions, compared with existing methods.

HTML全文

参考文献(1)

Ho C, Obraczka K, Tsudik G, and Viswanath K. Flooding forreliable multicast in multi-hop Ad hoc networks [C]. Proc. ofthe 3rd Int抣 Workshop on Discrete Algorithms and Methodsfor Mobile Computing and Communications (DiaLM),Seattle, USA, 1999: 64-71.[2]Ni S Y, Tseng Y C, Chen Y S, and Sheu J P. The broadcaststorm problem in a mobile Ad hoc network [C]. Proc. of the5th Annual ACM/IEEE International Conference on MobileComputing and Networking (MOBICOM ?9), Seattle, USA,Aug. 1999: 151-162.[3]Liu H, Jia X H, Wan P J, Liu X X, and Yao F. A distributedand efficient flooding scheme using 1-hop information inmobile Ad hoc networks [J].IEEE Transactions on Paralleland Distributed Systems.2007, 18(5):658-671[4]Heissenbl M, Braun T, Wchli M, and Bernoulli T.Optimized stateless broadcasting in wireless multi-hopnetworks [C]. Proc. IEEE INFOCOM2006, Barcelona,Spanish, April 23-29 2006: 1-12.[5]Lim H and Kim C. Multicast tree construction and floodingin wireless Ad hoc networks [C]. Proc. of the ACM IntlWorkshop on Modeling, Analysis and Simulation of Wirelessand Mobile System (MSWIM), Boston, USA, Aug. 2000:61-68.[6]Cai Y, Hua K A, and Phillips A. Leveraging 1-hopneighborhood knowledge for efficient flooding in wireless Adhoc networks [C]. Proc. IPCCC 2005, Phoenix, Arizona,April 7-9, 2005: 347-354.[7]Williams B and Camp T. Comparison of broadcastingtechniques for mobile ad hoc networks [C]. Proc. of the 3rdACM International Symposium on Mobile and Ad HocNetworking and Computing (Mobi-Hoc 02), Lausanne,Switzerland, June 2002: 194-202.Qayyum A, Viennot L, and Laouiti A. Multipoint relayingfor flooding broadcast messages in mobile wirelesssnetwork[C]. Proc. of the 35th Annual Hawaii InternationalEonference on System Sciences, Hawaii, USA, Jan. 7-10, 2002:3866-3875.[8]Wu J and Li H. On calculating connected dominating set forefficient routing in Ad hoc wireless networks [C]. Proc. of the3rd Intl Workshop on Discrete Algorithms and Methods forMobile Computing and Communications (DiaLM), Seattle,USA, 1999: 7-14.[9]Stojmenovic I, Seddigh M, and Zunic J. Dominating sets andneighbor elimination-based broadcasting algorithms inwireless networks [J].IEEE Transactions on Parallel andDistributed Systems.2002, 13(1):14-25[10]Thai M T, Wang F, Liu D, Zhu S, and Du D Z. Connecteddominating sets in wireless networks with differenttransmission ranges [J]. IEEE Transactions on MobileComputing, 2007, 6(7): 721-730.[11]Yang H Y, Lin C H, and Tsai M J. Distributed algorithm forefficient construction and maintenance of connected k-hopdominating sets in mobile Ad hoc networks [J].IEEETransactions on Mobile Computing.2008, 7(4):444-457[12]Lou Wei and Wu Jie. Toward broadcast reliability in mobileAd hoc networks with double coverage [J].IEEETransactions on Mobile Computing.2007, 6(2):148-163[13]Kershner R. The number of circles covering a set [J].American Journal of Mathematics.1939, 61(1):665-671

施引文献

资源附件(0)

访问统计