Top

Published in:

2020 | OriginalPaper | Chapter

Distributed Localization of Wireless Sensor Network Using Communication Wheel

Authors : Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, Buddhadeb Sau

Published in: Algorithms for Sensor Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study the network localization problem, i.e., the problem of determining node positions of a wireless sensor network modeled as a unit disk graph. In an arbitrarily deployed network, positions of all nodes of the network may not be uniquely determined. It is known that even if the network corresponds to a unique solution, no polynomial-time algorithm can solve this problem in the worst case, unless RP = NP. So we are interested in algorithms that efficiently localize the network partially. A widely used technique that can efficiently localize a uniquely localizable portion of the network is trilateration: starting from three anchors (nodes with known positions), nodes having at least three localized neighbors are sequentially localized. However, the performance of trilateration can substantially differ for different choices of the initial three anchors. In this paper, we propose a distributed localization scheme with a theoretical characterization of nodes that are guaranteed to be localized. In particular, our proposed distributed algorithm starts localization from a strongly interior node and provided that the subgraph induced by the strongly interior nodes is connected, it localizes all nodes of the network except some boundary nodes and isolated weakly interior nodes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Minimizing Total Interference in Asymmetric Sensor Networks

next chapter Covering Users by a Connected Swarm Efficiently

Albowicz, J., Chen, A., Zhang, L.: Recursive position estimation in sensor networks. In: 9th International Conference on Network Protocols (ICNP 2001), Riverside, CA, USA, 11–14 November 2001, pp. 35–43. IEEE Computer Society (2001). https://doi.org/10.1109/ICNP.2001.992758

Aspnes, J., Goldenberg, D., Yang, Y.R.: On the computational complexity of sensor network localization. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 32–44. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27820-7_5CrossRefMATH

Baggio, A., Langendoen, K.: Monte Carlo localization for mobile wireless sensor networks. Ad Hoc Netw. 6(5), 718–733 (2008). https://doi.org/10.1016/j.adhoc.2007.06.004CrossRef

Biswas, P., Liang, T.-C., Wang, T.-C., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sens. Netw. 2(2), 188–220 (2006). https://doi.org/10.1145/1149283.1149286CrossRef

Biswas, P., Toh, K.-C., Ye, Y.: A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM J. Sci. Comput. 30(3), 1251–1277 (2008). https://doi.org/10.1137/05062754XMathSciNetCrossRefMATH

Bose, K., Kundu, M.K., Adhikary, R., Sau, B.: Distributed localization of wireless sensor network using communication wheel. CoRR, abs/2008.00739 (2020). https://arxiv.org/abs/2008.00739

Bulusu, N., Heidemann, J.S., Estrin, D.: GPS-less low-cost outdoor localization for very small devices. IEEE Wirel. Commun. 7(5), 28–34 (2000). https://doi.org/10.1109/98.878533CrossRef

Chowdhury, T.J.S., Elkin, C., Devabhaktuni, V., Rawat, D.B., Oluoch, J.: Advances on localization techniques for wireless sensor networks: a survey. Comput. Netw. 110, 284–305 (2016). https://doi.org/10.1016/j.comnet.2016.10.006CrossRef

Eren, T., et al.: Rigidity, computation, and randomization in network localization. In: Proceedings IEEE INFOCOM 2004, the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, 7–11 March 2004, pp. 2673–2684. IEEE (2004). https://doi.org/10.1109/INFCOM.2004.1354686

10.

Fang, J., Cao, M., Morse, A.S., Anderson, B.D.O.: Sequential localization of sensor networks. SIAM J. Control. Optim. 48(1), 321–350 (2009). https://doi.org/10.1137/070679144MathSciNetCrossRefMATH

11.

Goldenberg, D.K., et al.: Localization in sparse networks using sweeps. In: Gerla, M., Petrioli, C., Ramjee, R. (eds.) Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, MOBICOM 2006, Los Angeles, CA, USA, 23–29 September 2006, pp. 110–121. ACM (2006). https://doi.org/10.1145/1161089.1161103

12.

Goldenberg, D.K., et al.: Network localization in partially localizable networks. In: INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, FL, USA, 13–17 March 2005, pp. 313–326. IEEE (2005). https://doi.org/10.1109/INFCOM.2005.1497902

13.

He, T., Huang, C., Blum, B.M., Stankovic, J.A., Abdelzaher, T.: Range-free localization schemes for large scale sensor networks. In: Johnson, D.B., Joseph, A.D., Vaidya, N.H. (eds.) Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking, MOBICOM 2003, San Diego, CA, USA, 14–19 September 2003, pp. 81–95. ACM (2003). https://doi.org/10.1145/938985.938995

14.

Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21(1), 65–84 (1992). https://doi.org/10.1137/0221008MathSciNetCrossRefMATH

15.

Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory Ser. B 94(1), 1–29 (2005). https://doi.org/10.1016/j.jctb.2004.11.002MathSciNetCrossRefMATH

16.

Ji, X.: Sensor positioning in wireless ad-hoc sensor networks with multidimensional scaling. In: Proceedings IEEE INFOCOM 2004, the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, 7–11 March 2004, pp. 2652–2661. IEEE (2004). https://doi.org/10.1109/INFCOM.2004.1354684

17.

Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad hoc networks beyond unit disk graphs. Wirel. Netw. 14(5), 715–729 (2008). https://doi.org/10.1007/s11276-007-0045-6CrossRef

18.

Lederer, S., Wang, Y., Gao, J.: Connectivity-based localization of large-scale sensor networks with complex shape. ACM Trans. Sens. Netw. 5(4), 31:1–31:32 (2009). https://doi.org/10.1145/1614379.1614383CrossRef

19.

Liu, Y., Yang, Z., Wang, X., Jian, L.: Location, localization, and localizability. J. Comput. Sci. Technol. 25(2), 274–297 (2010). https://doi.org/10.1007/s11390-010-9324-2CrossRef

20.

Lynch, N.A.: Distributed Algorithms. Elsevier, Amsterdam (1996)MATH

21.

Mao, G., Fidan, B., Anderson, B.D.O.: Wireless sensor network localization techniques. Comput. Netw. 51(10), 2529–2553 (2007). https://doi.org/10.1016/j.comnet.2006.11.018CrossRefMATH

22.

Moore, D.C., Leonard, J.J., Rus, D., Teller, S.J.: Robust distributed network localization with noisy range measurements. In: Stankovic, J.A., Arora, A., Govindan, R (eds.) Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, SenSys 2004, Baltimore, MD, USA, 3–5 November 2004, pp. 50–61. ACM (2004). https://doi.org/10.1145/1031495.1031502

23.

Peng, R., Sichitiu, M.L.: Angle of arrival localization for wireless sensor networks. In: Proceedings of the Third Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2006, Reston, VA, USA, 25–28 September 2006, pp. 374–382. IEEE (2006). https://doi.org/10.1109/SAHCN.2006.288442

24.

Sau, B., Mukhopadhyaya, K.: Length-based anchor-free localization in a fully covered sensor network. In: 2009 First International Communication Systems and Networks and Workshops, pp. 1–10, January 2009. https://doi.org/10.1109/COMSNETS.2009.4808851

25.

Savvides, A., Han, C.C., Strivastava, M.B.: Dynamic fine-grained localization in ad-hoc networks of sensors. In: Rose, C. (ed.) MOBICOM 2001, Proceedings of the Seventh Annual International Conference on Mobile Computing and Networking, Rome, Italy, 16–21 July 2001, pp. 166–179. ACM (2001). https://doi.org/10.1145/381677.381693

26.

Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, Monticello, IL, pp. 480–489 (1979)

27.

Shang, Y., Ruml, W.: Improved MDS-based localization. In: Proceedings IEEE INFOCOM 2004, The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, 7–11 March 2004, pp. 2640–2651. IEEE (2004). https://doi.org/10.1109/INFCOM.2004.1354683

28.

Shang, Y., Ruml, W., Zhang, Y., Fromherz, M.P.: Localization from mere connectivity. In: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2003, Annapolis, Maryland, USA, 1–3 June 2003, pp. 201–212. ACM (2003). https://doi.org/10.1145/778415.778439

29.

Sorbelli, F.B., Das, S.K., Pinotti, C.M., Silvestri, S.: Range based algorithms for precise localization of terrestrial objects using a drone. Pervasive Mob. Comput. 48, 20–42 (2018). https://doi.org/10.1016/j.pmcj.2018.05.007CrossRef

30.

Tutte, W.T.: Graph Theory. Cambridge Mathematical Library. Cambridge University Press, Cambridge (2001)

31.

Wang, J., Ghosh, R.K., Das, S.K.: A survey on sensor localization. J. Control Theory Appl. 8(1), 2–11 (2010). https://doi.org/10.1007/s11768-010-9187-7CrossRefMATH

32.

Whiteley, W.: Some matroids from discrete applied geometry. Contemp. Math. 197, 171–312 (1996)MathSciNetCrossRef

33.

Yang, Z., Liu, Y., Li, X.-Y.: Beyond trilateration: on the localizability of wireless ad hoc networks. IEEE/ACM Trans. Netw. 18(6), 1806–1814 (2010). https://doi.org/10.1109/TNET.2010.2049578CrossRef

Title: Distributed Localization of Wireless Sensor Network Using Communication Wheel
Authors: Kaustav Bose
Manash Kumar Kundu
Ranendu Adhikary
Buddhadeb Sau
Publisher: Springer International Publishing
Book: Algorithms for Sensor Systems
Print ISBN: 978-3-030-62400-2

Electronic ISBN: 978-3-030-62401-9

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62401-9_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner