A Topology Maintenance Algorithm Based on Shortest Path Tree for Wireless Ad hoc Networks

Shen Zhong; Chang Yi-lin; Cui Can; Zhang Xin

doi:10.3724/SP.J.1146.2005.00600

Volume 29 Issue 2

Jan. 2011

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2007 > 29(2): 323-327

Shen Zhong, Chang Yi-lin, Cui Can, Zhang Xin. A Topology Maintenance Algorithm Based on Shortest Path Tree for Wireless Ad hoc Networks[J]. Journal of Electronics & Information Technology, 2007, 29(2): 323-327. doi: 10.3724/SP.J.1146.2005.00600

Citation:

Shen Zhong, Chang Yi-lin, Cui Can, Zhang Xin. A Topology Maintenance Algorithm Based on Shortest Path Tree for Wireless Ad hoc Networks[J]. Journal of Electronics & Information Technology, 2007, 29(2): 323-327. doi: 10.3724/SP.J.1146.2005.00600

Citation:

PDF( 281 KB)

A Topology Maintenance Algorithm Based on Shortest Path Tree for Wireless Ad hoc Networks

doi: 10.3724/SP.J.1146.2005.00600

Received Date: 2005-05-30
Rev Recd Date: 2005-11-28
Publish Date: 2007-02-19

Abstract

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.

FullText(HTML)

References(1)

References

[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.

Relative Articles

Supplements(0)

Cited By

Proportional views