Article

On computing conditional fault-tolerance measures for k-covered wireless sensor networks

Authors:

MSWiM '06: Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems

Pages 309 - 316

https://doi.org/10.1145/1164717.1164770

Published: 07 October 2006 Publication History

Get Access

Abstract

Traditional connectivity is a graph-theoretic concept that has been widely used as a measure of the fault tolerance in wireless sensor networks. The classical connectivity, however, assumes that any subset of nodes can potentially fail at the same time, including the entire neighbor set of any node. In this paper, we propose a new measure of fault tolerance, called conditional fault-tolerance, for a class of wireless sensor networks, named k-covered wireless sensor networks (kcwsn), using the concept of forbidden faulty set. Our forbidden faulty set analysis of conditional fault-tolerance prohibits having a simultaneous failure of all the neighbors of any node. We characterize kcwsn with either homogeneous or non-homogeneous sensors based on the assumptions of random uniform distribution of the sensors and circular model of their transmission and sensing ranges. In particular, we compute the minimum node degree of kcwsn. We also prove that in general, the relationship between transmission and sensing ranges (R≥2r) does not always imply network connectivity even if sensing coverage is guaranteed. Moreover, we propose two conditional fault-tolerance measures for kcwsn: one based on the concept of conditional connectivity, the other using a new concept that is called conditional coverage. Our results prove that kcwsn can sustain a large number of sensor failures provided that the faulty set does not include the forbidden faulty set.

References

[1]

J. Chen, I. Kanj, and G. Wang, "Hypercube network fault tolerance: A probabilistic approach," Proc. Int. Conf. on Parallel Processing (ICPP), pp. 65--72, Aug. 2002.

Digital Library

Google Scholar

[2]

A. Esfahanian, "Generalized measures of fault tolerance with application to n-cube networks," IEEE Transactions on Computers, 38(11), pp. 1586--1591, Nov. 1989.

Digital Library

Google Scholar

[3]

A. Ghosh and S. K. Das, "Coverage and connectivity issues in wireless sensor networks," Mobile, Wireless and Sensor Networks: Technology, Applications and Future Directions, (Eds. R. Shorey, et al.), Wiley-IEEE Press, Mar. 2006.

Google Scholar

[4]

F. Harary, "Conditional connectivity," Networks, 13, pp. 347--357, 1983.

Crossref

Google Scholar

[5]

S. Latifi, M. Hegde, and M. Naraghi-Pour, "Conditional connectivity measures for large multiprocessor systems," IEEE Transactions on Computers, 43(2), pp. 218--222, Feb. 1994.

Digital Library

Google Scholar

[6]

N. Li and J. Hou, "FLSS: A fault-tolerant topology control algorithm for wireless networks," Proc. 10th Annual Int. Conf. on Mobile Computing and Networking (MobiCom), Pennsylvania USA, pp. 275--286, Sep. - Oct. 2004

Digital Library

Google Scholar

[7]

S. Megerian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Worst and best-case coverage in sensor networks," IEEE Transactions on Mobile Computing, 4(1), Jan. - Feb. 2005.

Digital Library

Google Scholar

[8]

O. Oellermann, "Conditional graph connectivity relative to hereditary properties," Networks, (21), pp. 245--255, 1991.

Crossref

Google Scholar

[9]

S. Shakkottai, R. Srikant, and N. Shroff, "Unreliable sensor grids: coverage, connectivity and diameter," Proc. 24th Annual Conf. IEEE Communications Societies (INFOCOM), San Fransisco, USA, Mar. - Apr. 2003.

Crossref

Google Scholar

[10]

D. Tian and N. Georganas, "Connectivity maintenance and coverage preservation in wireless sensor networks," Ad Hoc Networks, 3, pp. 744--761, 2005.

Digital Library

Google Scholar

[11]

J. Wu and G. Guo, "Fault tolerance measures for m-ary n-dimensional hypercubes based on forbidden faulty sets," IEEE Transactions on Computers, 47(8), Aug. 1998.

Digital Library

Google Scholar

[12]

G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill, "Integrated coverage and connectivity configuration for energy conservation in sensor networks," ACM Transactions on Sensor Networks, 1(1), pp. 36--72, Aug. 2005.

Digital Library

Google Scholar

[13]

M. Yarvis, N. Kushalnagar, H. Singh, A. Rangarajan, Y. Liu, and S. Singh, "Exploiting heterogeneity in sensor networks," in Proc. 24th Annual Conf. IEEE Communications Societies (INFOCOM ), Florida, USA, Mar. 2005.

Google Scholar

[14]

H. Zhang and J. Hou, "Maintaining sensing coverage and connectivity in large sensor networks," Ad Hoc & Sensor Wireless Networks, 1(1-2), pp. 89--124, Mar. 2005.

Google Scholar

Cited By

View all

Molnár MSimon GGönczy L(2013)Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networksInternational Journal of Ad Hoc and Ubiquitous Computing10.5555/2543890.254389514:2(109-122)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.5555/2543890.2543895
Liu LMa H(2012)On Coverage of Wireless Sensor Networks for Rolling TerrainsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.6923:1(118-125)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.69
Ammari HDas S(2009)Fault tolerance measures for large-scale wireless sensor networksACM Transactions on Autonomous and Adaptive Systems10.1145/1462187.14621894:1(1-28)Online publication date: 9-Feb-2009
https://dl.acm.org/doi/10.1145/1462187.1462189
Show More Cited By

Index Terms

On computing conditional fault-tolerance measures for k-covered wireless sensor networks
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
2. General and reference
  1. Cross-computing tools and techniques

Recommendations

Fault tolerance measures for large-scale wireless sensor networks

Connectivity, primarily a graph-theoretic concept, helps define the fault tolerance of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, ...
Coverage, connectivity, and fault tolerance measures of wireless sensor networks
SSS'06: Proceedings of the 8th international conference on Stabilization, safety, and security of distributed systems

Connectivity and sensing coverage are two fundamental concepts in the design of wireless sensor networks (WSNs). In this paper, we investigate the relationship between coverage and connectivity for k-covered WSNs (kCWSN), where every point in a field of ...
Quality of Surveillance Measures in K-Covered Heterogeneous Wireless Sensor Networks
ICPPW '10: Proceedings of the 2010 39th International Conference on Parallel Processing Workshops

Heterogeneous Wireless Sensor Networks, in which the deployed sensors have different capacities, are gradually used to perform critical surveillance in real world. For conserving energy, powerful sensors are usually activated only when an event is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MSWiM '06: Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems

October 2006

406 pages

ISBN:1595934774

DOI:10.1145/1164717

General Chairs:
Enrique Alba
University of Malaga, Spain
,
Carla-Fabiana Chiasserini
Politecnico di Torino, Italy
,
Program Chairs:
Nael Abu-Ghazaleh
Binghamton University, USA
,
Renato Lo Cigno
University of Trento, Italy

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MSWiM06

Sponsor:

MSWiM06: 9th International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems 2006

October 2 - 6, 2006

Terromolinos, Spain

Acceptance Rates

MSWiM '06 Paper Acceptance Rate 39 of 160 submissions, 24%;

Overall Acceptance Rate 398 of 1,577 submissions, 25%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
532
Total Downloads

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

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Molnár MSimon GGönczy L(2013)Quasi-optimal scheduling algorithm for area coverage in multi-functional sensor networksInternational Journal of Ad Hoc and Ubiquitous Computing10.5555/2543890.254389514:2(109-122)Online publication date: 1-Nov-2013
https://dl.acm.org/doi/10.5555/2543890.2543895
Liu LMa H(2012)On Coverage of Wireless Sensor Networks for Rolling TerrainsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.6923:1(118-125)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.69
Ammari HDas S(2009)Fault tolerance measures for large-scale wireless sensor networksACM Transactions on Autonomous and Adaptive Systems10.1145/1462187.14621894:1(1-28)Online publication date: 9-Feb-2009
https://dl.acm.org/doi/10.1145/1462187.1462189
Molnár MSimon GGönczy LNi LCao J(2008)Robustness and performance analysis of a dynamic sensor network scheduling algorithmProceedings of the 5th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness10.5555/1535571.1535642(1-6)Online publication date: 28-Jul-2008
https://dl.acm.org/doi/10.5555/1535571.1535642
Ammari HDas S(2006)Coverage, connectivity, and fault tolerance measures of wireless sensor networksProceedings of the 8th international conference on Stabilization, safety, and security of distributed systems10.5555/1759076.1759081(35-49)Online publication date: 17-Nov-2006
https://dl.acm.org/doi/10.5555/1759076.1759081
Ammari HDas S(2006)Coverage, Connectivity, and Fault Tolerance Measures of Wireless Sensor NetworksStabilization, Safety, and Security of Distributed Systems10.1007/978-3-540-49823-0_3(35-49)Online publication date: 2006
https://doi.org/10.1007/978-3-540-49823-0_3

View Options

Login options

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

Cited By

Index Terms

Recommendations

Fault tolerance measures for large-scale wireless sensor networks

Coverage, connectivity, and fault tolerance measures of wireless sensor networks

Quality of Surveillance Measures in K-Covered Heterogeneous Wireless Sensor Networks