research-article

Critical sensor density for partial connectivity in large area wireless sensor networks

Authors:

Mo ShaAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 7, Issue 4

Article No.: 35, Pages 1 - 23

https://doi.org/10.1145/1921621.1921629

Published: 04 February 2011 Publication History

Abstract

In this article, we study the critical sensor density for partial connectivity of a large area sensor network. We assume that sensor deployment follows the Poisson distribution. For a given partial connectivity requirement ρ, 0.5 < ρ < 1, we prove that there exists a critical sensor density λ₀, around which the probability that at least a fraction ρ of sensors are connected in the network increases sharply from ε to 1-ε within a short interval of sensor density λ. The length of this interval is in the order of O(-log ε/log A) as A → ∞, where A is the area of the sensor field, and the location of λ₀ is at the sensor density where the aforesaid probability is about 1/2. We prove the preceding theoretical results in the hexagonal model. We also extend our results to the disk model that models transmission range of sensors as disks. Simulations are performed to confirm the analytical results.

References

[1]

Bai, X., Kumar, S., Xuan, D., Yun, Z., and Lai, T. 2006. Deploying wireless sensors to achieve both coverage and connectivity. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc). ACM.

Digital Library

[2]

Bai, X., Zhang, C., Xuan, D., and Jia, W. 2009. Full-Coverage and k-connectivity (k = 14, 6) three dimensional networks. In Proceedings of the 28th IEEE Conference on Computer Communications (InfoCom). IEEE.

[3]

Balister, P., Bollobas, B., Sarkar, A., and Walters, M. 2009. A critical constant for the k-nearest-neighbour model. Adv. Appl. Probab. 41, 1--12.

[4]

Bettstetter, C. 2002. On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc). ACM.

Digital Library

[5]

Bourgain, J., Kahn, J., Kalai, G., Katznelson, Y., and Linial, N. 1992. The influence of variables in product spaces. Israel J. Math. 77, 1-2, 55--64.

[6]

Cai, H., jia, X., and Sha, M. 2010. Critical sensor density for partial connectivity in large area wireless sensor networks. In Proceedings of the 29th IEEE Conference on Computer Communications (InfoCom) Mini-Conference. IEEE.

Digital Library

[7]

Dousse, O., Franceschetti, M., and Thiran, P. 2006. A case for partial connectivity in large wireless multi-hop networks. In Proceedings of the Information Theory and Applications Workshop (UCSD-ITA).

[8]

Durrett, R. 1991. The Probability: Theory and Examples. Duxbury.

[9]

Friedgut, E. and Kalai, G. 1996. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124, 10, 2993--3002.

[10]

Gilbert, E. 1961. Random plane networks. J. Soc. Indust. Appl. Math. 9, 4, 533--543.

[11]

Graham, B. and Grimmett, G. 2006. Influence and sharp-threshold theorems for monotonic measures. The Ann. Probab. 34, 5, 1726--1745.

[12]

Grimmett, G. 1999. The Percolation. Springer.

[13]

Hou, T. and Li, V. 1986. Transmission range control in multihop packet radio networks. IEEE Trans. Comm. 34, 1, 38--44.

[14]

Kesten, H. 1982. The Percolation Theory for Mathematicians. Birkhauser.

[15]

Kleinrock, L. and Silvester, J. 1978. Optimal transmission radii for packet radio networks or why six is a magic number. In Proceedings of the National Telecommunications Conference (NTC).

[16]

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

[17]

Ni, J. and Chandler, S. 1994. Connectivity properties of a random radio network. IEE Proc. Comm. 141, 4, 289--296.

[18]

Osher, Y. 2007. From local search to global behavior: Ad hoc network example. Coop. Inf. Agents XI, 196--208.

Digital Library

[19]

Penrose, M. and Pisztora, A. 1996. Large deviations for discrete and continuous percolation. Adv. Appl. Probab. 28, 29--52.

[20]

Philips, T., Panwar, S., and Tantawi, A. 1989. Connectivity properties of a packet radio network model. IEEE Trans. Inf. Theory 35, 5, 1044--1047.

Digital Library

[21]

Piret, P. 1991. On the connectivity of radio networks. IEEE Trans. Inf. Theory 37, 5, 1490--1492.

Digital Library

[22]

Santi, P. and Blough, D. 2003. The critical transmitting range for connectivity in sparse wireless ad hoc networks. IEEE Trans. Mobile Comput. 2, 1, 25--39.

Digital Library

[23]

Santi, P., Blough, D., and Vainstein, F. 2001. A probabilistic analysis for the radio range assignment problem in ad hoc networks. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc). ACM.

Digital Library

[24]

Takagi, H. and Kleinrock, L. 1984. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Comm. 32, 3, 246--257.

[25]

Wan, P. and Yi, C. 2004. Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc). ACM.

Digital Library

[26]

Xing, G., Wang, X., Zhang, Y., Lu, C., Pless, R., and Gill, C. 2005. Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Trans. Sensor Netw. 1, 1, 36--72.

Digital Library

[27]

Xue, F. and Kumar, P. R. 2004. The number of neighbors needed for connectivity of wireless networks. Wirel. Netw. 10, 2, 169--181.

Digital Library

[28]

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.

Cited By

Pathak AAl-Anbagi IHamilton H(2022)An Adaptive QoS and Trust-Based Lightweight Secure Routing Algorithm for WSNsIEEE Internet of Things Journal10.1109/JIOT.2022.31898329:23(23826-23840)Online publication date: 1-Dec-2022
https://doi.org/10.1109/JIOT.2022.3189832
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
Fan TChen J(2020)A New Nonuniform Random Deployment Method to Minimize Cost for Large-Scale Wireless Sensor NetworksIEEE Access10.1109/ACCESS.2020.30352848(198532-198547)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3035284
Show More Cited By

Index Terms

Critical sensor density for partial connectivity in large area wireless sensor networks
1. Networks
  1. Network properties
    1. Network structure
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Integrated Connectivity and Coverage Techniques for Wireless Sensor Networks
MobiWac '16: Proceedings of the 14th ACM International Symposium on Mobility Management and Wireless Access

A wireless sensor network (WSN) consists of a group of energy-constrained sensor nodes with the ability of both sensing and communication, which can be deployed in a field of interesting (FoI) for detecting or monitoring some special events and then ...
Critical Density in Adjustable-Orientation Directional Sensor Networks Using Continuum Percolation

In this paper, we consider adjustable-orientation directional sensor networks (ADODSNs) in which nodes are deployed based on Poisson Point Process and the orientation of sensor nodes is distributed between 0 and 2 independently and uniformly. Despite of ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 7, Issue 4

February 2011

252 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1921621

Issue’s Table of Contents

Copyright © 2011 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 04 February 2011

Accepted: 01 October 2010

Revised: 01 October 2010

Received: 01 February 2010

Published in TOSN Volume 7, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
538
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

Pathak AAl-Anbagi IHamilton H(2022)An Adaptive QoS and Trust-Based Lightweight Secure Routing Algorithm for WSNsIEEE Internet of Things Journal10.1109/JIOT.2022.31898329:23(23826-23840)Online publication date: 1-Dec-2022
https://doi.org/10.1109/JIOT.2022.3189832
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
Fan TChen J(2020)A New Nonuniform Random Deployment Method to Minimize Cost for Large-Scale Wireless Sensor NetworksIEEE Access10.1109/ACCESS.2020.30352848(198532-198547)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3035284
Sadhukhan DRao S(2019)Minimum cost event driven WSN with spatial differentiated QoS requirementsWireless Networks10.1007/s11276-018-01926-z25:7(3899-3915)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s11276-018-01926-z
Cui WGong XLiu CXu DYin ZChen XFang D(2016)Watch Traffic in the Sky: A Method for Path Selection in Packet Transmission between V2V from Macro Perspective2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS.2016.0057(368-375)Online publication date: Dec-2016
https://doi.org/10.1109/ICPADS.2016.0057
Huang YMartínez JSendra JLópez L(2015)ResilientWireless Sensor Networks Using Topology Control: A ReviewSensors10.3390/s15102473515:10(24735-24770)Online publication date: 25-Sep-2015
https://doi.org/10.3390/s151024735
Wang Y(2015)Over provisioning rate in three-dimensional wireless sensor networks for partial sensing coverage2015 IEEE International Conference on Computational Intelligence and Virtual Environments for Measurement Systems and Applications (CIVEMSA)10.1109/CIVEMSA.2015.7158622(1-6)Online publication date: Jun-2015
https://doi.org/10.1109/CIVEMSA.2015.7158622
Wang HRoman HYuan LHuang YWang R(2014)Connectivity, coverage and power consumption in large-scale wireless sensor networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.5555/2949838.294994075:PA(212-225)Online publication date: 24-Dec-2014
https://dl.acm.org/doi/10.5555/2949838.2949940
(2014)Partial sensing coverage and deployment efficiency in wireless directional sensor networks2014 Wireless Telecommunications Symposium10.1109/WTS.2014.6835029(1-6)Online publication date: Apr-2014
https://doi.org/10.1109/WTS.2014.6835029
Mao GAnderson B(2014)Capacity of Large Wireless Networks with Generally Distributed NodesIEEE Transactions on Wireless Communications10.1109/TWC.2014.011614.13129013:3(1678-1691)Online publication date: Mar-2014
https://doi.org/10.1109/TWC.2014.011614.131290
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents