Fault tolerance measures for large-scale wireless sensor networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fault tolerance measures for large-scale wireless sensor networks

Full text

Pdf (786 KB)

Source

ACM Transactions on Autonomous and Adaptive Systems (TAAS) archive
Volume 4 , Issue 1 (January 2009) table of contents

Article No. 2

Year of Publication: 2009

ISSN:1556-4665

Authors

Habib M. Ammari	Hofstra University, Hempstead, NY
Sajal K. Das	University of Texas at Arlington, TX

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 61, Downloads (12 Months): 476, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1462187.1462189 What is a DOI?

ABSTRACT

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, sensing coverage, an intrinsic architectural feature of WSNs plays an important role in meeting application-specific requirements, for example, to reliably extract relevant data about a sensed field. Sensing coverage and network connectivity are not quite orthogonal concepts. In fact, it has been proven that connectivity strongly depends on coverage and hence considerable attention has been paid to establish tighter connection between them although only loose lower bound on network connectivity of WSNs is known. In this article, we investigate connectivity based on the degree of sensing coverage by studying k-covered WSNs, where every location in the field is simultaneously covered (or sensed) by at least k sensors (property known as k-coverage, where k is the degree of coverage). We observe that to derive network connectivity of k-covered WSNs, it is necessary to compute the sensor spatial density required to guarantee k-coverage. More precisely, we propose to use a model, called the Reuleaux Triangle, to characterize k-coverage with the help of Helly's Theorem and the analysis of the intersection of sensing disks of k sensors. Using a deterministic approach, we show that the sensor spatial density to guarantee k-coverage of a convex field is proportional to k and inversely proportional to the sensing range of the sensors. We also prove that network connectivity of k-covered WSNs is higher than their sensing coverage k. Furthermore, we propose a new measure of fault tolerance for k-covered WSNs, called conditional fault tolerance, based on the concepts of conditional connectivity and forbidden faulty sensor set that includes all the neighbors of a given sensor. We prove that k-covered WSNs can sustain a large number of sensor failures provided that the faulty sensor set does not include a forbidden faulty sensor set.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Adlakha, S., and Srivastava, M. 2003. Critical density threshold for coverage in wireless sensor networks. In Proceedings of the IEEE Wireless Communication Networking Conference, 3, 1615--1620.
	2	Ai, J., and Abouzeid, A. 2006. Coverage by directional sensors in randomly deployed wireless sensor networks. J. Combinat. Optimiz. 11, 1, 21--41.
	3	Ammari, H. M. and Das, S. K. 2008. Clustering-based minimum energy m-connected k-covered wireless sensor networks. TPC Best Paper Award, In Proceedings of the European Conference on Wireless Sensor Network, Lecture Notes in Computer Sciences, vol. 4913, 1--16.
	4	Ammari, H. M. and Das, S. K. 2006. Coverage, connectivity, and fault tolerance measures of wireless sensor networks. In Proceedings of the International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), A. K. Datta and M. Gradinariu Eds., Lecture Notes in Computer Sciences, vol. 4280, 35--49.
	5	Habib M. Ammari , Sajal K. Das, On computing conditional fault-tolerance measures for k-covered wireless sensor networks, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain [doi>10.1145/1164717.1164770]
	6	Xiaole Bai , Santosh Kumar , Dong Xuan , Ziqiu Yun , Ten H. Lai, Deploying wireless sensors to achieve both coverage and connectivity, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132921]
	7	Paul Balister , Béla Bollobas , Amites Sarkar , Santosh Kumar, Reliable density estimates for coverage and connectivity in thin strips of finite length, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287863]
	8	Bollobás, B. 2006. The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press.
	9	Jonathan L. Bredin , Erik D. Demaine , MohammadTaghi Hajiaghayi , Daniela Rus, Deploying sensor networks with guaranteed capacity and fault tolerance, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062729]
	10	Cardei, M. and Wu, J. 2006. Energy-efficient coverage problems in wireless ad-hoc sensor networks. Comput. Comm. 29, 4, 413--420.
	11	Jianer Chen , Iyad A. Kanj , Guojun Wang, Hypercube Network Fault Tolerance: A Probabilistic Approach, Proceedings of the 2002 International Conference on Parallel Processing, p.65, August 18-21, 2002
	12	Cortes, J., Martinez, S., Karatas, T. and Bullo, F. 2004. Coverage control for mobile sensing networks. IEEE Trans. Robot. Automat. 20, 2, 243--255.
	13	Ajoy K. Datta , Preethi Linga , Maria Gradinariu , Philippe Raipin-Parvedy, Self Distributed Query Region Covering in Sensor Networks, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.50-59, October 26-28, 2005 [doi>10.1109/RELDIS.2005.27]
	14	Drougas, Y. and Kalogeraki, V. 2007. Distributed, reliable restoration techniques using wireless sensor devices. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium, 1--10.
	15	Xiaojiang Du , Fengjing Lin, Maintaining differentiated coverage in heterogeneous sensor networks, EURASIP Journal on Wireless Communications and Networking, v.5 n.4, p.565-572, September 2005 [doi>10.1155/WCN.2005.565]
	16	A.-H. Esfahanian, Generalized Measures of Fault Tolerance with Application to N-Cube Networks, IEEE Transactions on Computers, v.38 n.11, p.1586-1591, November 1989 [doi>10.1109/12.42131]
	17	Abdol-Hossein Esfahanian , S. Louis Hakimi, On computing a conditional edge-connectivity of a graph, Information Processing Letters, v.27 n.4, p.195-199, April 8, 1988 [doi>10.1016/0020-0190(88)90025-7]
	18	Franceschetti, M., Cook, M. and Bruck, J. 2002. A geometric theorem for wireless network design optimization. Tech. rep. http://paradise.caltech.edu/papers/.
	19	Ghosh, A. and Das, S. K. 2006. Coverage and connectivity issues in wireless sensor networks. In Mobile, Wireless and Sensor Networks: Technology, Applications and Future Directions, R. Shorey, et al., Eds. Wiley-IEEE Press.
	20	Himanshu Gupta , Zongheng Zhou , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, IEEE/ACM Transactions on Networking (TON), v.14 n.1, p.55-67, February 2006 [doi>10.1109/TNET.2005.863478]
	21	Hall, P. 1988. Introduction to the Theory of Coverage Processes, John Wiley & Sons Inc., New York.
	22	Harary, F. 1983. Conditional connectivity. Netw. 13, 347--357.
	23	Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941367]
	24	Kershner, R. 1939. The number of circles covering a set. Amer. J. Math. 61, 3, 665--671.
	25	Kruskal, J. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. In Amer. Math. Soc. 7, 48--50.
	26	Santosh Kumar , Ten H. Lai , Anish Arora, Barrier coverage with wireless sensors, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080859]
	27	Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]
	28	S. Latifi , M. Hegde , M. Naraghi-Pour, Conditional Connectivity Measures for Large Multiprocessor Systems, IEEE Transactions on Computers, v.43 n.2, p.218-222, February 1994 [doi>10.1109/12.262126]
	29	Lazos, L. and Poovendran, R. 2006. Coverage in heterogeneous sensor networks. In Proceedings of the Workshop on Modeling Optimization in Mobile, Ad Hoc and Sensor Systems, 1--10.
	30	Ning Li , Jennifer C. Hou, FLSS: a fault-tolerant topology control algorithm for wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023747]
	31	Li, X.-Y. Wan, P.-J. and Frieder, O. 2003. Coverage in wireless ad-hoc sensor networks. IEEE Trans. Comput. 52, 753--763.
	32	Luo, J. and Hubaux, J.-P. 2005. Joint mobility and routing for lifetime elongation in wireless sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies, 1735--1746.
	33	Malde, P. and Oellermann, O. 1988. The F-connectivity of a graph. Scientia, Series A: Mathematical Sciences, 1, 65--71.
	34	Seapahn Megerian , Farinaz Koushanfar , Miodrag Potkonjak , Mani B. Srivastava, Worst and Best-Case Coverage in Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.1, p.84-92, January 2005 [doi>10.1109/TMC.2005.15]
	35	Megerian, S., Koushanfar, F., Potkonjak, M. and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies, 1380--1387.
	36	Oellermann, O. 1991. Conditional graph connectivity relative to hereditary properties. Netw. 21, 245--255.
	37	Vlady Ravelomanana, Extremal Properties of Three-Dimensional Sensor Networks with Applications, IEEE Transactions on Mobile Computing, v.3 n.3, p.246-257, July 2004 [doi>10.1109/TMC.2004.23]
	38	Shakkottai, S., Srikant, R. and Shroff, N. 2005. Unreliable sensor grids: coverage, connectivity and diameter. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies, 1073--1083.
	39	Tian, D. and Georganas, N. 2005. Connectivity maintenance and coverage preservation in wireless sensor networks. Ad Hoc Netw. 3, 744--761.
	40	Peng-Jun Wan , Chih-Wei Yi, Coverage by randomly deployed wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2658-2669, June 2006 [doi>10.1109/TIT.2005.862092]
	41	Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
	42	Jie Wu , Guanghui Guo, Fault Tolerance Measures for m-Ary n-Dimensional Hypercubes Based on Forbidden Faulty Sets, IEEE Transactions on Computers, v.47 n.8, p.888-893, August 1998 [doi>10.1109/12.707589]
	43	Guoliang Xing , Xiaorui Wang , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.36-72, August 2005 [doi>10.1145/1077391.1077394]
	44	Yarvis, M., Kushalnagar, N., Singh, H., Rangarajan, A., Liu, Y., and Singh, S. 2005. Exploiting heterogeneity in sensor networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies, 878--890.
	45	Zhang, H. and Hou, J. 2006. Is deterministic deployment worse than random deployment for wireless sensor networks? In Proceedings of the Annual Joint Conference of the IEEE Computer and Communication Societies, 1--13.
	46	Honghai Zhang , Jennifer C. Hou, On the upper bound of α-lifetime for large sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.2, p.272-300, November 2005 [doi>10.1145/1105688.1105693]
	47	Zhang, H. and Hou, J. 2005. Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sensor Wirel. Netw. 1, 1--2, 89--124.
	48	Honghai Zhang , Jennifer Hou, On deriving the upper bound of α-lifetime for large sensor networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989475]
	49	Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
	50	Zhou, Z., Das, S. and Gupta, H. 2005. Fault tolerant connected sensor cover with variable sensing and transmission ranges. In Proceedings of the IEEE International Conference on Sensor and Ad Hoc Communications and Networks, 594--604.
	51	Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]