article

Unreliable sensor grids: coverage, connectivity and diameter

Authors:

Sanjay Shakkottai,

Ness B. ShroffAuthors Info & Claims

Ad Hoc Networks, Volume 3, Issue 6

Pages 702 - 716

https://doi.org/10.1016/j.adhoc.2004.02.001

Published: 01 November 2005 Publication History

Abstract

We consider an unreliable wireless sensor grid network with n nodes placed in a square of unit area. We are interested in the coverage of the region and the connectivity of the network. We first show that the necessary and sufficient conditions for the random grid network to cover the unit square region as well as ensure that the active nodes are connected are of the form p(n)r^2(n)~log(n)/n, where r(n) is the transmission radius of each node and p(n) is the probability that a node is ''active'' (not failed). This result indicates that, when n is large, even if each node is highly unreliable and the transmission power is small, we can still maintain connectivity with coverage. We also show that the diameter of the random grid (i.e., the maximum number of hops required to travel from any active node to another) is of the order n/log(n). Finally, we derive a sufficient condition for connectivity of the active nodes (without necessarily having coverage). If the node success probability p(n) is small enough, we show that connectivity does not imply coverage.

References

[1]

J.M. Kahn, R.H. Katz, K.S.J. Pister, Mobile networking for smart dust, in: Proceedings of MobiCom 99, Seattle, WA, August 1999.

Digital Library

[2]

Sohrabi, K., Gao, J., Ailawadhi, V. and Pottie, G., Protocols for self-organization of a wireless sensor network. IEEE Personal Communications. v7 i5. 16-27.

[3]

Gupta, P. and Kumar, P.R., Critical power for asymptotic connectivity in wireless networks. In: McEneany, W.M., Yin, G., Zhang, Q. (Eds.), Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, Birkhauser, Boston. pp. 547-566.

[4]

Gupta, P. and Kumar, P.R., The capacity of wireless networks. IEEE Transactions on Information Theory. vIT-46 i2. 388-404.

Digital Library

[5]

M. Grossgluauser, D. Tse, Mobility increases the capacity of ad-hoc wireless networks, in: Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.

[6]

Johnson, D., Maltz, D. and Broch, J., DSR: the dynamic source routing protocol for multi-hop wireless ad hoc networks. In: Perkins, C.E. (Ed.), Ad Hoc Networking, Addison-Wesley, Reading, MA. pp. 139-172.

Digital Library

[7]

In: Perkins, C. (Ed.), Ad Hoc Networking, Addison-Wesley, Reading, MA.

[8]

S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. Srivastava, Coverage problems in wireless ad-hoc sensor networks, in: Proceedings of IEEE Infocom, Anchorage, AK, 2001.

[9]

D. Braginsky, D. Estrin, Rumor routing algorithm for sensor networks, 2001. Available from <http://lecs.cs.ucla.edu/~estrin/>.

[10]

W. Ye, J. Heidemann, D. Estrin, An energy-efficient MAC protocol for wireless sensor networks, in: Proceedings of IEEE Infocom, New York, June 2002.

[11]

L. Doherty, L.E. Ghaoui, K.S.J. Pister, Convex position estimation in wireless sensor networks, in: Proceedings of IEEE Infocom, Anchorage, AK, April 2001.

[12]

Meester, R. and Roy, R., Continuum Percolation. 1996. Cambridge University Press, Cambridge.

[13]

Hall, P., Introduction to the Theory of Coverage Processes. 1988. Wiley, New York.

[14]

US Discusses Giving India Ground Sensors, June 13 2002, News Item in Washington Post.

[15]

Jain, R., Puri, A. and Sengupta, R., Geographical routing using partial information for wireless ad hoc networks. IEEE Personal Communications. v8 i1. 48-57.

[16]

Bollobas, B., Random Graphs. 1985. Academic Press, New York.

[17]

A.-M. Kermarrec, L. Massoulie, A. Ganesh, Reliable probabilistic communication in large-scale information dissemination systems, Microsoft Research Tech Report MSR-TR-2000-105, October 2000.

[18]

A.-M. Kermarrec, L. Massoulie, A. Ganesh, Scamp: Peer-to-peer lightweight membership service for large-scale group communication, in: Proceedings of the Third International Workshop on Networked Group Communications (NGC 2001), London, UK, November 2001.

Digital Library

[19]

Rappaport, T., Wireless Communications: Principles and Practice. 2001. Prentice Hall, Englewood Cliffs, NJ.

Digital Library

Cited By

Ammari H(2023)A Computational Geometry-based Approach for Planar k-Coverage in Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/356427219:2(1-42)Online publication date: 3-Feb-2023
https://dl.acm.org/doi/10.1145/3564272
Das SKapelko R(2021)On the Range Assignment in Wireless Sensor Networks for Minimizing the Coverage-Connectivity CostACM Transactions on Sensor Networks10.1145/345740817:4(1-48)Online publication date: 10-Aug-2021
https://dl.acm.org/doi/10.1145/3457408
(2018)A comparative analysis of quality parameters in wireless sensor network with different techniquesInternational Journal of Mobile Network Design and Innovation10.1504/IJMNDI.2018.0936988:3(141-156)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJMNDI.2018.093698
Show More Cited By

Index Terms

Unreliable sensor grids: coverage, connectivity and diameter
1. Networks
  1. Network types
    1. Mobile networks

Index terms have been assigned to the content through auto-classification.

Recommendations

Centralized and Clustered k-Coverage Protocols for Wireless Sensor Networks

Sensing coverage is an essential functionality of wireless sensor networks (WSNs). However, it is also well known that coverage alone in WSNs is not sufficient, and hence network connectivity should also be considered for the correct operation of WSNs. ...
Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks

Efficient network coverage and connectivity are the requisites for most Wireless Sensor Network (WSN) deployments, particularly those concerned with area monitoring. Due to the resource constraints of the sensor nodes, redundancy of coverage area must ...
On the lifetime of wireless sensor networks

Network lifetime has become the key characteristic for evaluating sensor networks in an application-specific way. Especially the availability of nodes, the sensor coverage, and the connectivity have been included in discussions on network lifetime. Even ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © © 2004.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 November 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ammari H(2023)A Computational Geometry-based Approach for Planar k-Coverage in Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/356427219:2(1-42)Online publication date: 3-Feb-2023
https://dl.acm.org/doi/10.1145/3564272
Das SKapelko R(2021)On the Range Assignment in Wireless Sensor Networks for Minimizing the Coverage-Connectivity CostACM Transactions on Sensor Networks10.1145/345740817:4(1-48)Online publication date: 10-Aug-2021
https://dl.acm.org/doi/10.1145/3457408
(2018)A comparative analysis of quality parameters in wireless sensor network with different techniquesInternational Journal of Mobile Network Design and Innovation10.1504/IJMNDI.2018.0936988:3(141-156)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJMNDI.2018.093698
Rebai MAfsar HSnoussi H(2016)Exact methods for sensor deployment problem with connectivity constraint in wireless sensor networksInternational Journal of Sensor Networks10.1504/IJSNET.2016.07832421:3(157-168)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJSNET.2016.078324
Sun PBoukerche ACuevas ÁChatzimisios PDe Grande R(2016)Integrated Connectivity and Coverage Techniques for Wireless Sensor NetworksProceedings of the 14th ACM International Symposium on Mobility Management and Wireless Access10.1145/2989250.2989272(75-82)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.1145/2989250.2989272
Zannat HAkter TTasnim MRahman A(2016)The coverage problem in visual sensor networksJournal of Network and Computer Applications10.1016/j.jnca.2016.08.01575:C(1-15)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.jnca.2016.08.015
Gao YZhang HQi KLi XTong Y(2016)Optimal periphery deployment of wireless base stations in swine facilities for 1-coverageComputers and Electronics in Agriculture10.1016/j.compag.2016.05.001125:C(173-183)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.compag.2016.05.001
Amine ABelhaj ASedra M(2016)The Hexagonal Geometrical Structure of the N-Coverage Networks in the G2-Lie Algebra FrameworkWireless Personal Communications: An International Journal10.1007/s11277-016-3267-z89:2(319-330)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s11277-016-3267-z
Wang YChu WZhang YLi X(2013)Partial sensing coverage with connectivity in lattice wireless sensor networksInternational Journal of Sensor Networks10.1504/IJSNET.2013.05908014:4(226-240)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1504/IJSNET.2013.059080
Sheu JChang GWu SChen Y(2013)Adaptive k-coverage contour evaluation and deployment in wireless sensor networksACM Transactions on Sensor Networks10.1145/2489253.24892579:4(1-31)Online publication date: 23-Jul-2013
https://dl.acm.org/doi/10.1145/2489253.2489257
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents