Passive-Event-Assisted Approach for the Localizability of Large-Scale Randomly Deployed Wireless Sensor Network

Zhiguo Chen; Guifa Teng; Xiaolei Zhou; Tao Chen

doi:10.26599/TST.2018.9010070

Tsinghua Science and Technology 2019, 24(2): 134-146 https://doi.org/10.26599/TST.2018.9010070

Open Access | Issue | Published: 31 December 2018

Passive-Event-Assisted Approach for the Localizability of Large-Scale Randomly Deployed Wireless Sensor Network

Show Author's Information Hide Author's Information Zhiguo Chen, Guifa Teng(

), Xiaolei Zhou, Tao Chen

College of Information Science and Technology, Agricultural University of Hebei, Baoding 071000, China.

Nanjing Telecommunication Technology Research Institute, National University of Defense Technology, Nanjing 210089, China.

Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China.

Keywords:

network localizability, random deployment, Wireless Sensor Networks (WSNs), passive event

Cite this article:

Chen Z, Teng G, Zhou X, et al. Passive-Event-Assisted Approach for the Localizability of Large-Scale Randomly Deployed Wireless Sensor Network. Tsinghua Science and Technology, 2019, 24(2): 134-146. https://doi.org/10.26599/TST.2018.9010070

Download citation

EndNote(RIS)

BibTeX

387

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

Localizability in large-scale, randomly deployed Wireless Sensor Networks (WSNs) is a classic but challenging issue. To become localizable, WSNs normally require extensive adjustments or additional mobile nodes. To address this issue, we utilize occasional passive events to ease the burden of localization-oriented network adjustment. We prove the sufficient condition for node and network localizability and design corresponding algorithms to minimize the number of nodes for adjustment. The upper bound of the number of adjusted nodes is limited to the number of articulation nodes in a connected graph. The results of extensive simulations show that our approach greatly reduces the cost required for network adjustment and can thus provide better support for the localization of large-scale sparse networks than other approaches.

Full text

Abstract

Full text

Outline

About this article

Passive-Event-Assisted Approach for the Localizability of Large-Scale Randomly Deployed Wireless Sensor Network

Show Author's information Hide Author's Information Zhiguo Chen, Guifa Teng(

), Xiaolei Zhou, Tao Chen

College of Information Science and Technology, Agricultural University of Hebei, Baoding 071000, China.

Nanjing Telecommunication Technology Research Institute, National University of Defense Technology, Nanjing 210089, China.

Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China.

Abstract

Keywords: network localizability, random deployment, Wireless Sensor Networks (WSNs), passive event

References(34)

[1]

Priyantha N. B., Chakraborty A., and Balakrishnan H., The Cricket location-support system, in Proc. 6th Annu. Int. Conf. Mobile Computing and Networking, Boston, MA, USA, 2000, pp. 32-43.

DOI

[2]

Goldenberg D. K., Bihler P., Cao M., Fang J., Anderson B. D. O., Morse A. S., and Yang Y. R., Localization in sparse networks using sweeps, in Proc. 12th Annu. Int. Conf. Mobile Computing and Networking, Los Angeles, CA, USA, 2006, pp. 110-121.

DOI

[3]

Eren T., Graph invariants for unique localizability in cooperative localization of wireless sensor networks: Rigidity index and redundancy index, Ad Hoc Networks, vol. 44, pp. 32-45, 2016.

DOI Google Scholar

[4]

Eren T., Cooperative localization in wireless ad hoc and sensor networks using hybrid distance and bearing (angle of arrival) measurements, EURASIP Journal on Wireless Communications and Networking, vol. 2011, p. 72, 2011.

DOI Google Scholar

[5]

Liu Y. H., He Y., Li M., Wang J. L., Liu K. B., and Li X. Y., Does wireless sensor network scale? A measurement study on GreenOrbs, IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 10, pp. 1983-1993, 2013.

DOI Google Scholar

[6]

Bapat V., Kale P., Shinde V., Deshpande N., and Shaligram A., WSN application for crop protection to divert animal intrusions in the agricultural land, Computers and Electronics in Agriculture, vol. 133, pp. 88-96, 2017.

DOI Google Scholar

[7]

Eren T., Goldenberg O. K., Whiteley W., Yang Y. R., Morse A. S., Anderson B. D. O., and Belhumeur P. N., Rigidity, computation, and randomization in network localization, in Proc. 23th Annu. IEEE Conf. Computer Communications (INFOCOM), Hong Kong, China, 2004, pp. 2673-2684.

[8]

Pathirana P. N., Bulusu N., Savkin A. V., and Jha S., Node localization using mobile robots in delay-tolerant sensor networks, IEEE Transactions on Mobile Computing, vol. 4, no. 3, pp. 285-296, 2005.

DOI Google Scholar

[9]

Zhong Z. G., Wang D., and He T., Sensor node localization using uncontrolled events, in Proc. 28th Int. Conf. Distributed Computing Systems, Beijing, China, 2008, pp. 438-445.

DOI

[10]

Chen T., Yang Z., Liu Y. H., Guo D. K., and Luo X. S., Localization-oriented network adjustment in wireless ad hoc and sensor networks, IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 1, pp. 146-155, 2014.

DOI Google Scholar

[11]

Zhou X. L., Guo D. K., Chen T., and Luo X. S., Achieving network localizability in nonlocalizable WSN with moving passive event, International Journal of Distributed Sensor Networks, vol. 9, no. 10, p. 305410, 2013.

DOI Google Scholar

[12]

Bahl P. and Padmanabhan V. N., RADAR: An in-building RF-based user location and tracking system, in Proc. 19th Annu. Joint Conf. IEEE Computer and Communications Societies, Tel Aviv, Israel, 2000, pp. 775-784.

[13]

Niculescu D. and Nath B., DV based positioning in ad hoc networks, Telecommunication Systems, vol. 22, nos. 1–4, pp. 267-280, 2003.

DOI Google Scholar

[14]

Zhang Z. Y., Gou X., Li Y. P., and Huang S. S., DV-hop based self-adaptive positioning in wireless sensor networks, in Proc. 5th Int. Conf. Wireless Communications, Networking and Mobile Computing, Beijing, China, 2009, pp. 1-4.

DOI

[15]

He T., Huang C. D., Blum B. M., Stankovic J. A., and Abdelzaher T., Range-free localization schemes for large scale sensor networks, in Proc. 9th Annu. Int. Conf. Mobile Computing and Networking, San Diego, CA, USA, 2003, pp. 81-95.

DOI

[16]

Foy W. H., Position-location solutions by Taylor-series estimation, IEEE Transactions on Aerospace and Electronic Systems, vol. AES-12, no. 2, pp. 187-194, 1976.

DOI Google Scholar

[17]

Chan Y. T. and Ho K. C. S., A simple and efficient estimator for hyperbolic location, IEEE Transactions on Signal Processing, vol. 42, no. 8, pp. 1905-1915, 1994.

DOI Google Scholar

[18]

Shang Y., Ruml W., Zhang Y., and Fromherz M. P. J., Localization from mere connectivity, in Proc. 4th ACM Int. Symp. Mobile Ad Hoc Networking and Computing, Annapolis, MD, USA, 2003, pp. 201-212.

DOI

[19]

Jackson B. and Jordán T., Connected rigidity matroids and unique realizations of graphs, Journal of Combinatorial Theory, Series B, vol. 94, no. 1, pp. 1-29, 2005.

DOI Google Scholar

[20]

Aspnes J., Eren T., Goldenberg D. K., Morse A. S., Whiteley W., Yang Y. R., Anderson B. D. O., and Belhumeur P. N., A theory of network localization, IEEE Transactions on Mobile Computing, vol. 5, no. 12, pp. 1663-1678, 2006.

DOI Google Scholar

[21]

Goldenberg D. K., Krishnamurthy A., Maness W. C., Yang Y. R., Young A., Morse A. S., and Savvides A., Network localization in partially localizable networks, in Proc. 24th Annu. Joint Conf. IEEE Computer and Communications Societies, Miami, FL, USA, 2005, pp. 313-326.

[22]

Yang Z., Liu Y. H., and Li X. Y., Beyond trilateration: On the localizability of wireless ad-hoc networks, IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp. 1806-1814, 2010.

DOI Google Scholar

[23]

Wang X. P., Luo J., Li S. S., Dong D. Z., and Cheng W. F., Component based localization in sparse wireless ad hoc and sensor networks, in Proc. IEEE Int. Conf. Network Protocols, Orlando, FL, USA, 2008, pp. 288-297.

[24]

Priyantha N. B., Balakrishnan H., Demaine E. D., and Teller S., Mobile-assisted localization in wireless sensor networks, in Proc. 24th Annu. Joint Conf. IEEE Computer and Communications Societies, Miami, FL, USA, 2005, pp. 172-183.

[25]

Wu C. H., Zhang Y., Sheng W. H., and Kanchi S., Rigidity guided localisation for mobile robotic sensor networks, International Journal of Ad Hoc and Ubiquitous Computing, vol. 6, no. 2, pp. 114-128, 2010.

DOI Google Scholar

[26]

Anderson B. D. O., Belhumeur P. N., Eren T., Goldenberg D. K., Morse A. S., Whiteley W., and Yang Y. R., Graphical properties of easily localizable sensor networks, Wireless Networks, vol. 15, no. 2, pp. 177-191, 2009.

DOI Google Scholar

[27]

Hendrickson B., Conditions for unique graph realizations, SIAM Journal on Computing, vol. 21, no. 1, pp. 65-84, 1992.

DOI Google Scholar

[28]

Laman G., On graphs and rigidity of plane skeletal structures, Journal of Engineering Mathematics, vol. 4, no. 4, pp. 331-340, 1970.

DOI Google Scholar

[29]

Aranzazu-Suescun C. and Cardei M., Distributed algorithms for event reporting in mobile-sink WSNs for internet of things, Tsinghua Science and Technology, vol. 22, no. 4, pp. 413-426, 2017.

DOI Google Scholar

[30]

Zhou Z. M., Wu C. S., Yang Z., and Liu Y. H., Sensorless sensing with WiFi, Tsinghua Science and Technology, vol. 20, no. 1, pp. 1-6, 2015.

DOI Google Scholar

[31]

Abdulla Y. A., El-Hennawy H., and Mahrous S., The effect of base stations configurations on the accuracy of hyperbolic position location in macrocellular and microcellular GSM systems, in Proc. 18th National Radio Science Conf., Mansoura, Egypt, 2001, pp. 303-313.

[32]

Pemmaraju S. and Skiena S., Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. New York, NY, USA: Cambridge University Press, 2003.

DOI

[33]

Li D. and Hu Y. H., Energy-based collaborative source localization using acoustic microsensor array, EURASIP Journal on Applied Signal Processing, vol. 2003, pp. 321-337, 2003.

DOI Google Scholar

[34]

Tarjan R., Depth-first search and linear graph algorithms, SIAM Journal on Computing, vol. 1, no. 2, pp. 146-160, 1972.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 09 May 2017

Revised: 06 June 2017

Accepted: 07 June 2017

Published: 31 December 2018

Issue date: April 2019

Copyright

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments. This work was partly supported by the National Natural Science Foundation for Outstanding Excellent Young Scholars of China (No. 61422214), the National Key Basic Research and Development (973) Program of China (No. 2014CB347800), and the National Natural Science Foundation of China (No. 61371196).