一种基于最短路径树的无线Ad hoc网络拓扑维护算法
doi: 10.3724/SP.J.1146.2005.00600
A Topology Maintenance Algorithm Based on Shortest Path Tree for Wireless Ad hoc Networks
-
摘要: 该文主要研究了无线Ad hoc网络中节点失效的情况下，如何维护网络的连通性和拓扑的性能，并且尽可能地降低拓扑维护的开销。提出了基于最短路径树的拓扑维护算法。该算法在拓扑变化时首先触发失效节点的邻节点响应(即重新运行拓扑控制算法)，在不增加额外通信开销的情况下，响应的节点根据相互发送的Hello分组来判断网络是否连通；如果不能确定网络是连通的，再触发失效节点的其它可达邻近节点响应。仿真研究表明，算法显著地减少了拓扑维护的开销，维护后的拓扑结构在功率有效性和功率扩展因子等方面也取得了好的性能。
-
关键词:
- 无线Ad hoc网络;拓扑维护;拓扑控制
Abstract: This paper focuses on how to maintain the wireless network connectivity and performance while reducing the maintenance overhead as some nodes fail. A topology maintenance algorithm based on the shortest path tree is proposed. In this algorithm, the neighbors of a faulty node are first triggered to respond (i.e., rerun the topology control algorithm). Without extra communication overhead, each responding node determines the network connectivity by the contents of Hello messages sent by its neighbors. If the responding nodes could not ensure that the network is connected, the other reachable nodes from the fault node are further triggered. Simulation results show that the proposed scheme can efficiently maintain the network connectivity with low overhead and achieve acceptable performance in terms of both power efficiency and power stretch factor. -
[1] Goldsmith A J and Wicker S B. Design challenges for energy- constrained Ad hoc wireless networks. IEEE Wireless Communications, 2002, 9(4): 8-27. [2] Shen C C, Srisathapornphat C, and Liu R, et al.. CLTC: A cluster-based topology control framework for ad hoc networks[J].IEEE Trans. on Mobile Computing.2004, 3(1):18-32 [3] Li N, Hou J C, and Sha L. Design and analysis of an MST-Based topology control algorithm. Proc. INFOCOM 2003, San Franciso, 2003: 1702-1712. [4] Rodoplu V and Meng T H. Minimum energy mobile wireless networks[J].IEEE J. on Select. Areas Commun.1999, 17(8):1333-1344 [5] Li X Y and Wan P J. Constructing minimum energy mobile wireless networks. Proc. ACM MOBIHOC, Florence, 2001: 283-286. [6] Li L and Halpern J Y. A minimum-energy path-preserving topology-control algorithm[J].IEEE Trans. on Wireless Communications.2004, 3(3):910-921 [7] Liu J and Li B. Distributed topology control in wireless sensor networks with asymmetric links. GLOBECOM, San Francisco, 2003: 1257-1262. Ogier R, Lewis M, and Templin F. Topology dissemination based on reverse-path forwarding (TBRPF). MANET Internet Draft, 2003. Wang S C, Wei D S L, and Kuo S Y. A topology control algorithm for constructing power efficient wireless Ad hoc networks. GLOBECOM, San Francisco, 2003: 1290-1295. Sedgewick R. Algorithm in C Parts 5: Graph Algorithms (Third Edition). Boston, Addison-Wesley Publishing Company, 2003: 280-300. [8] Liu J. Topology control in wireless sensor and mobile Ad hoc networks. [Master thesis], University of Toronto, 2002: 42-44. -
计量
- 文章访问数: 2986
- HTML全文浏览量: 88
- PDF下载量: 1036
- 被引次数: 0
下载:
