More Web Proxy on the site http://driver.im/

Article

FLSS: a fault-tolerant topology control algorithm for wireless networks

Authors:

Jennifer C. HouAuthors Info & Claims

MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networking

Pages 275 - 286

https://doi.org/10.1145/1023720.1023747

Published: 26 September 2004 Publication History

Abstract

Topology control algorithms usually reduce the number of links in a wireless network, which in turn decreases the degree of connectivity. The resulting network topology is more susceptible to system faults such as node failures and departures. In this paper, we consider k-vertex connectivity of a wireless network. We first present a centralized algorithm, Fault-tolerant Global Spanning Subgraph (FGSS_k), which preserves k-vertex connectivity. FGSS_k is min-max optimal, i.e., FGSS_k minimizes the maximum transmission power used in the network, among all algorithms that preserve k-vertex connectivity. Based on FGSS_k, we propose a localized algorithm, Fault-tolerant Local Spanning Subgraph (FLSS_k). It is proved that FLSS_k preserves k-vertex connectivity while maintaining bi-directionality of the network, and FLSS_k is min-max optimal among all strictly localized algorithms. We then relax several widely used assumptions for topology control to enhance the practicality of FGSS_k and FLSS_k. Simulation results show that FLSS_k is more power-efficient than other existing distributed/localized topology control algorithms.

References

[1]

M. Bahramgiri, M. Hajiaghayi, and V. S. Mirrokni. Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. In Proc. Eleventh International Conference on Computer Communications and Networks (ICCCN), pages 392--397, Oct. 2002.

[2]

G. D. Battista, R. Tamassia, and L. Vismara. Output-sensitive reporting of disjoint paths. Algorithmica, 23(4):302--340, 1999.

[3]

C. Bettstetter. On the minimum node degree and connectivity of a wireless multihop network. In Proc. ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 80--91, Lausanne, Switzerland, June 2002.

Digital Library

[4]

S. A. Borbash and E. H. Jennings. Distributed topology control algorithm for multihop wireless networks. In Proc. International Joint Conference on Neural Networks, (IJCNN '02), pages 355--360, Honolulu, HI, USA, May 2002.

[5]

S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing, 4:507--518, 1975.

Digital Library

[6]

M. Hajiaghayi, N. Immorlica, and V. S. Mirrokni. Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. In Proc. ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 300--312, San Diego, CA, USA, Sept. 2003.

Digital Library

[7]

T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-free localization schemes for large scale sensor networks. In Proc. ACM International Conference on Mobile Computing and Networking (MOBICOM), pages 81--95, San Diego, CA, USA, Sept. 2003.

Digital Library

[8]

V. Kawadia and P. Kumar. Power control and clustering in ad hoc networks. In Proc. IEEE INFOCOM 2003, volume~1, pages 459--469, San Francisco, CA, USA, Apr. 2003.

[9]

S. Khuller. Approximation algorithms for finding highly connected subgraphs. In D. S. Hochbaum, editor, Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston, MA, 1996.

Digital Library

[10]

J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48--50, 1956.

[11]

L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer. Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In Proc. ACM Symposium on Principles of Distributed Computing (PODC), pages 264--273, Newport, RI, USA, Aug. 2001.

Digital Library

[12]

N. Li and J. C. Hou. Topology control in heterogeneous wireless networks: problems and solutions. In Proc. IEEE INFOCOM 2004, Hong Kong, China, Mar. 2004 (the version in the conference proceedings has a technical error, and an updated version of the paper appears as a technical report at Department of Computer Science, University of Illinois at Urbana Champaign, Technical Report No. UIUCDCS-R-2004-2412, Mar 2004).

[13]

N. Li, J. C. Hou, and L. Sha. Design and analysis of an MST-based topology control algorithm. In Proc. IEEE INFOCOM 2003, volume~3, pages 1702--1712, San Francisco, CA, USA, Apr. 2003.

[14]

X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed construction of planar spanner and routing for ad hoc networks. In Proc. IEEE INFOCOM 2002, volume~3, pages 1268--1277, New York, NY, USA, June 2002.

[15]

X.-Y. Li, P.-J. Wan, Y. Wang, and C.-W. Yi. Fault tolerant deployment and topology control in wireless networks. In Proc. ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 117--128, Annapolis, MD, USA, June 2003.

Digital Library

[16]

S. McCanne and S. Floyd. ns Network Simulator. http://www.isi.edu/nsnam/ns/.

[17]

S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol. In Proc. European Wireless 2002, Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, pages 156--162, Florence, Italy, Feb. 2002.

[18]

M. D. Penrose. On k-connecitivity for a geometric random graph. Random Structures and Algorithms, 15(2):145--164, 1999.

Digital Library

[19]

R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In Proc. IEEE INFOCOM 2000, volume~2, pages 404--413, Tel Aviv, Israel, Mar. 2000.

[20]

V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE J. Select. Areas Commun., 17(8):1333--1344, Aug. 1999.

Digital Library

[21]

H.-Y. Tyan. Design, realization and evaluation of a component-based software architecture for network simulation. PhD thesis, The Ohio State University, Columbus, OH, USA, 2001. Also see http://www.j-sim.org.

Digital Library

Cited By

Liu HWang YXu XLi D(2024)Bottom-up k-Vertex Connected Component Enumeration by Multiple Expansion2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00233(3000-3012)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00233
Akram VDagdeviren OTavli B(2021)Distributed $k$-Connectivity Restoration for Fault Tolerant Wireless Sensor and Actuator Networks: Algorithm Design and Experimental EvaluationsIEEE Transactions on Reliability10.1109/TR.2020.297026870:3(1112-1125)Online publication date: Sep-2021
https://doi.org/10.1109/TR.2020.2970268
Cabuk UAkram VDagdeviren O(2021)Analysis of Movement-Based Connectivity Restoration Problem in Wireless Ad-Hoc and Sensor NetworksTrends in Data Engineering Methods for Intelligent Systems10.1007/978-3-030-79357-9_37(381-389)Online publication date: 6-Jul-2021
https://doi.org/10.1007/978-3-030-79357-9_37
Show More Cited By

Index Terms

FLSS: a fault-tolerant topology control algorithm for wireless networks

Recommendations

Fault tolerant deployment and topology control in wireless networks
MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing

This paper investigate fault tolerance for wireless ad hoc networks. We consider a large-scale of wireless networks whose nodes are distributed randomly in a unit-area square region. Given n wireless nodes V, each with transmission range r_n, the ...
Localized topology control algorithms for heterogeneous wireless networks

Most existing topology control algorithms assume homogeneous wireless networks with uniform maximal transmission power, and cannot be directly applied to heterogeneous wireless networks where the maximal transmission power of each node may be different. ...
Fault tolerant deployment and topology control in wireless ad hoc networks: Research Articles
Performance Evaluation of Wireless Networks

We consider a large-scale of wireless ad hoc networks whose nodes are distributed randomly in a two-dimensional region Ω (more specifically, a unit square). Given n wireless nodes V, each with transmission range r_n, the wireless networks are often ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networking

September 2004

384 pages

ISBN:1581138687

DOI:10.1145/1023720

General Chair:
Zygmunt J. Haas
Cornell University
,
Program Chairs:
Samir R. Das
Stony Brook University, SUNY
,
Ravi Jain
DoCoMo USA Labs

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MobiCom04

Sponsor:

MobiCom04: Tenth Annual International Conference on Mobile Computing and Networking

September 26 - October 1, 2004

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

110
Total Citations
View Citations
1,676
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu HWang YXu XLi D(2024)Bottom-up k-Vertex Connected Component Enumeration by Multiple Expansion2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00233(3000-3012)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00233
Akram VDagdeviren OTavli B(2021)Distributed $k$-Connectivity Restoration for Fault Tolerant Wireless Sensor and Actuator Networks: Algorithm Design and Experimental EvaluationsIEEE Transactions on Reliability10.1109/TR.2020.297026870:3(1112-1125)Online publication date: Sep-2021
https://doi.org/10.1109/TR.2020.2970268
Cabuk UAkram VDagdeviren O(2021)Analysis of Movement-Based Connectivity Restoration Problem in Wireless Ad-Hoc and Sensor NetworksTrends in Data Engineering Methods for Intelligent Systems10.1007/978-3-030-79357-9_37(381-389)Online publication date: 6-Jul-2021
https://doi.org/10.1007/978-3-030-79357-9_37
Hu YLi ZLi JChang ZXu YLiu J(2020)Incremental-Compensation based Robust Topology Control for Micro/Nano Satellite Network2020 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA51271.2020.00012(22-28)Online publication date: Dec-2020
https://doi.org/10.1109/NaNA51271.2020.00012
Ota MTakahashi RFukazawa Y(2020)Energy Efficient Fault Tolerant Topology Control for IoT Using Variable k-ConnectivitySustainability Awareness and Green Information Technologies10.1007/978-3-030-47975-6_13(321-333)Online publication date: 18-Sep-2020
https://doi.org/10.1007/978-3-030-47975-6_13
Dagdeviren OAkram V(2019)The Effect of Random Node Distribution and Transmission Ranges on Connectivity Robustness in Wireless Sensor Networks2019 International Symposium on Networks, Computers and Communications (ISNCC)10.1109/ISNCC.2019.8909162(1-5)Online publication date: Jun-2019
https://doi.org/10.1109/ISNCC.2019.8909162
Barsagade SPradhan PBhattacharjee S(2019)Energy Aware Fault Tolerant Topology Design for Energy Constraint Sensor Networks2019 25th Asia-Pacific Conference on Communications (APCC)10.1109/APCC47188.2019.9026492(443-448)Online publication date: Nov-2019
https://doi.org/10.1109/APCC47188.2019.9026492
Cheraghlou MKhadem-Zadeh AHaghparast M(2019)EFT: Novel Fault Tolerant Management Framework for Wireless Sensor NetworksWireless Personal Communications10.1007/s11277-019-06600-xOnline publication date: 29-May-2019
https://doi.org/10.1007/s11277-019-06600-x
Zhang ZDai F(2019)Construction of Distributed Virtual Backbone Network in Tactical Communication NetworkCommunications, Signal Processing, and Systems10.1007/978-981-13-6264-4_68(569-576)Online publication date: 4-May-2019
https://doi.org/10.1007/978-981-13-6264-4_68
Wang WMosse DCole DPickel JOuhammou YRidouard FGrolleau EJan MBehnam M(2018)Dynamic Wireless Network Reconfiguration for Control System applied to a Nuclear Reactor Case StudyProceedings of the 26th International Conference on Real-Time Networks and Systems10.1145/3273905.3273912(30-40)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3273905.3273912
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents