Article

k-fault resistance in wireless ad-hoc networks

Authors:

Hanan Shpungin,

Michael SegalAuthors Info & Claims

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

Pages 89 - 96

https://doi.org/10.1145/1080810.1080826

Published: 02 September 2005 Publication History

Abstract

Given a wireless network, we want to assign each node a transmission power, which will enable transmission between any two nodes (via other nodes). Moreover, due to possible faults, we want to have at least k vertex-disjoint paths from any node to any other, where k is some fixed integer, depending on the reliability of the nodes. The goal is to achieve this directed k-connectivity with a minimal overall power assignment. The problem is NP-Hard for any k ≥ 1 already for planar networks. Here we first present an optimal power assignment for uniformly spaced nodes on a line for any k ≥ 1. Based on it, we design an approximation algorithm for linear radio networks with factor min(2,(Δ/δ)^α), where Δ and δ are the maximal and minimal distances between adjacent nodes respectively and parameter α ≥ 1 being the distance-power gradient. We then extend it to the weighted version. Finally, we develop an approximation algorithm with factor O(k²), for planar case, which is, to the best of our knowledge, the first non-trivial result for this problem.

References

[1]

E. Althaus, G. Calinescu, I. Mandoiu, S. Prasad, N. Tchervenski and A. Zelikovsly, "Power Efficient Range Assignment in Ad-Hoc Wireless Networks", IEEE Wireless Communications and Networking Conference (WCNC03), 2003]]

[2]

C. Ambuhl, A. Clementi, M. Ianni, G. Rossi, A. Monti, R. Silvestri, "The Range Assignment Problem in Non-Homogeneous Static Ad-Hoc Networks, 2nd International Conference on AD-HOC Networks and Wireless (AdHoc-Now 03), 2004]]

[3]

C.Ambuhl. A. Clementi, P. Penna, G. Rossi and R. Silvestri, "Energy Consumption in Radio Networks: Selfish Agents and Rewarding Mechanisms", Proceedings of the 10th International Colloquium on Structural Information & Communication Complexity (SIROCCO)}, pp. 1--16, 2003]]

[4]

M. A. Bender and C. Chekuri, "Performance Guarantees for the TSP with a Parameterized Triangle Inequality", Information Processing Letters, Vol. 73(1-2), pp. 17--21, 2000]]

Digital Library

[5]

D. Blough, M. Leoncini, G. Resta, and P. Santi, "On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks", Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science (TCS), pp. 71--82, 2002]]

Digital Library

[6]

G. Calinescu, I. Mandoiu and A. Zelikovsly, "Symmetric Connectivity with Minimum Power Consumption in Radio Networks", Proc. 2nd IFIP International Conference on Theoretical Computer Science, pp. 119--130, 2002]]

Digital Library

[7]

G. Calinescu and P. J. Wan, "Range assignment for High Connectivitity in Wireless Ad Hoc Networks", 2nd International Conference on AD-HOC Networks and Wireless (AdHoc-Now 03), pp. 235--246, 2003]]

[8]

V. Chvatal and P. Erdos, "A Note on Hamiltonian Circuits", Discrete Math, Vol. 2, pp. 111--113, 1972]]

Digital Library

[9]

J. Cheriyan, S. Vempala and A. Vetta, "Approximation algorithms for minimum-cost k-vertex connected subgraphs", Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 306--312, 2002]]

Digital Library

[10]

A. E. F. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca, "On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs", 18th Annual Symposium on Theoretical Aspects of Computer Science, pp. 121--131, 2001]]

Digital Library

[11]

A. E. F. Clementi, A. Ferreira, P. Penna, S. Perennes, and R. Silvestri, "The minimum range assignment problem on linear radio networks", European Symposium on Algorithms, pp. 143--154, 2000]]

Digital Library

[12]

A. E. F. Clementi, G. Huiban, P. Penna, G. Rossi and Y. C. Verhoeven, "Some Recent Theoretical Advances and Open Questions on Energy Consumption in Ad-Hoc Wireless Networks", 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, 2003]]

[13]

A. E. F. Clementi, P. Penna and R. Silvestri, "Hardness Results for the Power Range Assignment Problem in Packet Radio Networks", Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 197--208, 1999]]

Digital Library

[14]

A. E. F. Clementi, P. Penna and R. Silvestri, "On the Power Assignment Problem in Radio Networks", Electronic Colloquium on Computational Complexity (ECCC), 2000]]

[15]

A. E. F. Clementi, P. Penna and R. Silvestri, "The Power Range Assignment Problem in Radio Networks on the Plane", Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, pp. 651--660, 2000]]

Digital Library

[16]

X. Jia, D. Kim, P. Wan and C. Yi, "Power Assignment for k-Connectivity in Wireless Ad Hoc Networks", Proceedings of the IEEE INFOCOM, 2005]]

[17]

M. T. Hajiaghayi, N. Immorlica and V. S. Mirrokni, "Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-Hop Networks", Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, pp. 300--312, 2003]]

Digital Library

[18]

M. T. Hajiaghayi, G. Kortsarz, V. S. Mirrokni and Z. Nutov, "Power Optimization for Connectivity Problems", Proceedings of IPCO, 2005]]

Digital Library

[19]

G. Huiban and Y. C. Verhoeven, "A Self-Stabilized Distributed Algorithm for the Range Assignment in Ad-Hoc Wireless Networks", Soumis Parallel Processing Letters, 2004]]

[20]

L. M. Kirousis, E. Kranakis, D. Krizanc and A. Pelc, "Power Consumption in Packet Radio Networks" Theoretical Computer Science, Vol. 243(1-2), pp. 289--305, 2000]]

Digital Library

[21]

S. O. Krumke, R. Liu, E. L. Lloyd, M. V. Marathe, R. Ramanathan and S. S. Ravi, "Topology Control Problems under Symmetric and Asymmetric Power Thresholds" ADHOC-NOW 2003, pp. 187--198, 2003]]

[22]

E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan and S. S. Ravi, "Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks", MONET 10(1-2), pp. 19--34, 2005]]

Digital Library

[23]

K. Pahlavan and A. Levesque, "Wireless Information Networks", Wiley-Interscience, 1995]]

Digital Library

[24]

M. Segal and K. Kedem, "Geometric Applications Of Posets", WADS, pp. 402--417, 1997]]

Digital Library

[25]

A. Srinivas and E. Modiano, "Minimum Energy Disjoint Path Routing in Wireless Ad-hoc," Proceedings of the 9th annual international conference on Mobile computing and networking, pp. 122--133, 2003]]

Digital Library

[26]

P. J. Wan, G. Calinescu, X. Y. Li and O. Frieder, "Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks", ACM Wireless Networks, 2002]]

Digital Library

[27]

J. Wieselthier, G. Nguyen and A. Ephremides, "On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks", Proceedings of the IEEE INFOCOM, pp. 586--594, 2000]]

Cited By

Burt CChan YSonenberg N(2010)Exact Models for the k-Connected Minimum Energy ProblemAd Hoc Networks10.1007/978-3-642-11723-7_26(392-406)Online publication date: 2010
https://doi.org/10.1007/978-3-642-11723-7_26
Moraes RRibeiro CDuhamel C(2009)Optimal solutions for fault-tolerant topology control in wireless ad hoc networksIEEE Transactions on Wireless Communications10.1109/TWC.2009.12.0815668:12(5970-5981)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TWC.2009.12.081566
Shpungin HSegal M(2009)Low-energy fault-tolerant bounded-hop broadcast in wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2009.201465317:2(582-590)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/TNET.2009.2014653
Show More Cited By

Index Terms

k-fault resistance in wireless ad-hoc networks

Recommendations

A reliable node-disjoint multipath routing with low overhead in wireless ad hoc networks
MSWiM '04: Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems

Wireless ad hoc networks are characterized by the use of wireless links with limited bandwidth, dynamically varying network topology and multi-hop connectivity. AODV and DSR are the two most widely studied on-demand ad hoc routing protocols. Previous ...
Reliable Routing in Wireless Ad Hoc Networks: The Virtual Routing Protocol

A novel routing protocol for wireless, mobile ad hoc networks is presented. This protocol incorporates features that enhance routing reliability, defined as the ability to provide almost 100% packet delivery rate. The protocol is based on a virtual ...
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

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

September 2005

120 pages

ISBN:1595930922

DOI:10.1145/1080810

Program Chairs:
Suman Banerjee
University of Wisconsin-Madison
,
Samrat Ganguly
NEC Laboratories America

Copyright © 2005 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: 02 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

Dial M - POMC 05

Sponsor:

Dial M - POMC 05: Joint Workshop on Foundations of Mobile Computing 2005

September 2, 2005

Cologne, Germany

Acceptance Rates

Overall Acceptance Rate 21 of 68 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
336
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Burt CChan YSonenberg N(2010)Exact Models for the k-Connected Minimum Energy ProblemAd Hoc Networks10.1007/978-3-642-11723-7_26(392-406)Online publication date: 2010
https://doi.org/10.1007/978-3-642-11723-7_26
Moraes RRibeiro CDuhamel C(2009)Optimal solutions for fault-tolerant topology control in wireless ad hoc networksIEEE Transactions on Wireless Communications10.1109/TWC.2009.12.0815668:12(5970-5981)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TWC.2009.12.081566
Shpungin HSegal M(2009)Low-energy fault-tolerant bounded-hop broadcast in wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2009.201465317:2(582-590)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1109/TNET.2009.2014653
Segal MShpungin H(2009)On construction of minimum energy k-fault resistant topologiesAd Hoc Networks10.1016/j.adhoc.2008.03.0087:2(363-373)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.adhoc.2008.03.008
Berend DSegal MShpungin HLi XWang Y(2008)Power efficient resilience and lifetime in wireless ad-hoc networksProceedings of the 1st ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing10.1145/1374718.1374722(17-24)Online publication date: 26-May-2008
https://dl.acm.org/doi/10.1145/1374718.1374722
Carmi PSegal MKatz MShpungi H(2006)Fault-Tolerant Power Assignment and Backbone in Wireless NetworksProceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops10.1109/PERCOMW.2006.55Online publication date: 13-Mar-2006
https://dl.acm.org/doi/10.1109/PERCOMW.2006.55
Zhao XChou CGuo JJha S(2006)Protecting Multicast Sessions in Wireless Mesh NetworksProceedings. 2006 31st IEEE Conference on Local Computer Networks10.1109/LCN.2006.322141(467-474)Online publication date: Nov-2006
https://doi.org/10.1109/LCN.2006.322141

View Options

Get Access

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