Skip to main content

Advertisement

SpringerLink
Log in

Fault-Tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

The topology of a multi-hop wireless network can be controlled by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control algorithm for minimum energy consumption in multi-hop wireless networks. This algorithm is an extension of cone-based topology control algorithm [19, 12]. The main advantage of this algorithm is that each node decides on its power based on local information about the relative angle of its neighbors and as a result of these local decisions, a fault-tolerant connected network is formed on the nodes. It is done by preserving the connectivity of a network upon failing of, at most, k nodes (k is a constant) and simultaneously minimize the transmission power at each node to some extent. In addition, simulations are studied to support the effectiveness of this algorithm. Finally, it is shown how to extend this algorithm to 3-dimensions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I.F. Akyildiz, O.B. Akan, C. Chen, J. Fangand and W. Su, InterPlanetary Internet: State-of-the-art and research challenge, Computer Networks Journal 43 (2)(2003) 75–113.

    Article  MATH  Google Scholar 

  2. A. Chandrakasan, R. Amirtharajah, S.H. Cho, J. Goodman, G. Konduri, J. Kulik, W. Rabiner and A. Wang, Design considerations for distributed microsensor systems, in: Proc. IEEE Custom Integrated Circuits Conference (CICC) (May 1999) pp. 279–286.

  3. M.X. Goemans and D.P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing 24 (1995) 296–317.

    Article  MathSciNet  MATH  Google Scholar 

  4. M.T. Hajiaghayi, N. Immorlica and V.S. Mirrokni, Power optimization in topology control algorithms for wireless multihop networks, Annual International Conference on Mobile Computing and Networking (MOBICOM), pp. 300–312 (Sept. 2003).

  5. Y. Hassin and D. Peleg, Sparse communication networks and efficient routing, in: ACM Symp. on Principles of Distributed Computing (Aug. 2000) pp. 41–50.

  6. W.R. Heinzelman, A. Chandrakasan and H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in: IEEE Hawaii Int. Conf. on Systems Sciences (Jan. 2000) pp. 4–70.

  7. T.C. Hou and V.O.K. Li, Transmission range control in multi-hop radio networks, IEEE Trans. on Communications 34(1) (1986) 38–44.

    Google Scholar 

  8. L. Hu, Topology control for multihop packet radio networks, IEEE Trans. on Communications 41(10) (1993) 1482–1493.

    Article  Google Scholar 

  9. M. Keil and C.A. Gutwin, Classes of graphs which approximate the complete Euclidean graph, Discrete and Computational Geometry 7 (1992) 13–28.

    MathSciNet  MATH  Google Scholar 

  10. K. Krizman, T.E. Biedka and T.S. Rappaport, Wireless position location: fundamentals, implementation strategies, and source of error, in: IEEE 47th Vehicular Technology Conference (Sept. 1997) pp. 919–923.

  11. L. Li and J. Halpern, Minimum energy mobile wireless networks revisited, in: IEEE International Conference on Communications (ICC) (June 2001).

  12. L. Li, J. Halpern, V. Bahl, Y.M. Wang, R. Wattenhofer, Analysis of a cone-based distributed topology control algorithms for wireless multi-hop networks, in: ACM Symp. on Principle of Distributed Computing (PODC) (Aug. 2001).

  13. Xiang-Yang Li, Wen-Zhan Song and Yu Wang, Efficient topology control for wireless ad hoc networks with non-uniform transmission ranges, To appear in Wireless Networks (WINET).

  14. Xiang-Yang Li, Yu Wang, Peng-Jun Wan and Chih-Wei Yi, Robust deployment and fault tolerant topology control for wireless ad hoc networks, ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (June 2003).

  15. R. Ramanathan and R. Rosales-HainRodoplu, Topology control of multihop radio networks using transmit power adjustment, in: Proc. IEEE INFOCOM (March 2000) pp. 404–413.

  16. Volkan Rodoplu and Teresa H. Meng, Minimum energy mobile wireless networks, IEEE J. Selected Areas in Communications 17(8) (1999) 1633–1639.

    Google Scholar 

  17. H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Trans. on Communications 32(1) (1984) 38–44.

    Google Scholar 

  18. Godfried T. Toussaint, The relative neighborhood graph of a finite planar set, Pattern recognition 12 (4) (1980) 261–268

    Article  MATH  MathSciNet  Google Scholar 

  19. R. Wattenhofer, L. Li, V. Bahl and Y.M. Wang, Distributed topology control for power efficient operation in multihop wireless ad hoc networks, in: IEEE INFOCOM (April 2001).

  20. Douglas B. West, Introduction to graph theory (Prentice Hall Inc., Upper Saddle River, NJ, 1996).

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Massachusetts Institute of Technology, 550 Memorial Drive, Apt 18C, Cambridge, MA, 02139

    Mohsen Bahramgiri

  2. MIT Department of Mathematics, Computer Science and Artificial Intelligence Laboratory (CSAIL), 32 Vassar Street, Cambridge, 02139, USA

    MohammadTaghi Hajiaghayi & Vahab S. Mirrokni

Authors
  1. Mohsen Bahramgiri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. MohammadTaghi Hajiaghayi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vahab S. Mirrokni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohsen Bahramgiri.

Additional information

An extended abstract version of this paper appeared in the 11th IEEE International Conference on Computer Communications and Networks(ICCCN02).

Mohsen Bahramgiri born in 1979, recieved the Bachelor's degree in Mathematical Sciences from Sharif University of Technology, Tehran, Iran in 2000. He is now a PhD candidate in Mathematics Department at Massachusetts Institute of Technology. His research interests include Symplectic Hodge Theory on Higher dimentional Geometry, Kahler Geometry, Mathematical Physics and Geometric Analysis on one hand, and algorithmic Graph Theory and Combinatorics on the other hand.

MohammadTaghi Hajiaghayi received the Bachelor's degree in computer engineering from Sharif University of Technology in 2000. He received the Master's degree in Computer Science from the University of Waterloo in 2001. Since 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the IBM T.J. Watson Research Center (Department of Mathematical Sciences) and at the Microsoft Research (Theory group). His research interests are algorithmic graph theory, combinatorial optimizations, distributed and mobile computing, computational geometry and embeddings, game theory and combinatorial auctions, and random structures and algorithms.

Vahab S. Mirrokni received the Bachelor's degree in computer engineering from Sharif University of Technology, Tehran, Iran in 2001. Since 2001, he is a Ph.D. candidate in Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. During his Ph.D. studies, he also worked at the Bell-Laboratories (Networking Center and Department of Fundamental Mathematics). His research interests include approximation algorithms, combinatorial optimization, computational game theory, mobile computing, network mannagement, and algorithmic graph theory.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bahramgiri, M., Hajiaghayi, M. & Mirrokni, V.S. Fault-Tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks. Wireless Netw 12, 179–188 (2006). https://doi.org/10.1007/s11276-005-5265-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-005-5265-z

Keywords

Search

Navigation