Top > JACIII > Metric Dimension of Generalized Möbius Ladder and its App ...

single-jc.php

JACIII Vol.24 No.1 pp. 3-11
doi: 10.20965/jaciii.2020.p0003
(2020)

Paper:

Views over last 60 days: 888

Metric Dimension of Generalized Möbius Ladder and its Application to WSN Localization

Muhammad Idrees*, Hongbin Ma*,†, Mei Wu*, Abdul Rauf Nizami**, Mobeen Munir**, and Sajid Ali***

*School of Automation, Beijing Institute of Technology
No.5 South Zhongguancun Street, Haidian District, Beijing 100081, China

**Abdus Salam School of Mathematical Sciences, Government College University Lahore
68-B, New Muslim Town, Lahore, Punjab 54600, Pakistan

***Department of Computer Science, University of Education
DG Khan Campus, Kangan Road, DG Khan, Punjab, Pakistan

†Corresponding author

Received:
February 20, 2018
Accepted:
June 11, 2018
Published:
January 20, 2020
Creative Commons License
Keywords:
wireless sensor network localization, metric dimension, resolving set, generalized Möbius ladder
Abstract

Localization is one of the key techniques in wireless sensor network. While the global positioning system (GPS) is one of the most popular positioning technologies, the weakness of high cost and energy consuming makes it difficult to install in every node. In order to reduce the cost and energy consumption only a few nodes, called beacon nodes, are equipped with GPS modules. The remaining nodes obtain their locations through localization. In order to find the minimum positions of beacons, a resolving set with minimal cardinality has been obtained in the network which is called metric basis. Simultaneous local metric basis of the network is also given in which each pair of adjacent vertices of the network is distinguished by some element of simultaneous local metric basis which makes the network design more reasonable. In this paper a new network, the generalized Möbius ladder Mm,n, has been introduced and its metric dimension and simultaneous local metric dimension of its two subfamilies have been calculated.

Cite this article as:
M. Idrees, H. Ma, M. Wu, A. Nizami, M. Munir, and S. Ali, “Metric Dimension of Generalized Möbius Ladder and its Application to WSN Localization,” J. Adv. Comput. Intell. Intell. Inform., Vol.24 No.1, pp. 3-11, 2020.
Data files:
References
  1. [1] J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. O. Anderson, and P. N. Belhumeur, “A theory of Network Localization,” IEEE Trans. on Mobile Computing, Vol.5, No.12, pp. 1663-1678, 2006.
  2. [2] G. Han, H. Xu, T. Q. Duong, J. Jiang, and T. Hara, “Localization algorithms of Wireless Sensor Networks: a survey,” Telecommunication Systems, Vol.52, Issue 4, pp. 2419-2436, 2013.
  3. [3] Z. Liu, X. Feng, J. Zhang, Y. Liu, J. Zhang, and X. Zhang, “An Improved Rumor Routing Protocol Based on Optimized Intersection Angle Theory and Localization Technologies in WSN,” J. Adv. Comput. Intell. Intell. Inform., Vol.21, No.7, pp. 1172-1179, 2017.
  4. [4] T. Camp, J. Boleng, and V. Davies, “A survey of mobility models for ad hoc network research,” Wireless Communications and Mobile Computing, Vol.2, Issue 5, pp. 483-502, 2002.
  5. [5] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: a survey,” Computer Networks, Vol.38, Issue 4, pp. 393-422, 2002.
  6. [6] L. Atzori, A. Iera, and G. Morabito, “The Internet of Things: A survey,” Computer Networks, Vol.54, Issue 15, pp. 2787-2805.
  7. [7] E. Heidari, A. Gladisch, B. Moshiri, and D. Tavangarian, “Survey on location information services for Vehicular Communication Networks,” Wireless Networks, Vol.20, Issue 5, pp. 1085-1105, 2014.
  8. [8] Y. Liu, Z. Yang, X. Wang, and L. Jian, “Location, Localization, and Localizability,” J. of Computer Science and Technology, Vol.25, Issue 2, pp. 274-297, 2010.
  9. [9] Z. Farid, R. Nordin, and M. Ismail, “Recent Advances in Wireless Indoor Localization Techniques and System,” J. of Computer Networks and Communications, Vol.2013, Article ID 185138, 12pp., doi: 10.1155/2013/185138, 2013.
  10. [10] J. Beutel, K. Römer, M. Ringwald, and M. Woehrle, “Deployment Techniques for Sensor Networks,” G. Ferrari (Ed.), “Sensor Networks: Where Theory Meets Practice,” pp. 219-248, Springer, 2009.
  11. [11] M. Esnaashari and M. R. Meybodi, “Deployment of a mobile wireless sensor network with k-coverage constraint: a cellular learning automata approach,” Wireless Networks, Vol.19, Issue 5, pp. 945-968, 2013.
  12. [12] Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz, “Localization from mere connectivity,” Proc. of the 4th ACM Int. Symp. on Mobile Ad Hoc Networking & Computing (MobiHoc’03), pp. 201-212, 2003.
  13. [13] I. Borg and P. J. F. Groenen, “Modern Multidimensional Scaling: Theory and Applications,” Springer, 2005.
  14. [14] Y. Shang and W. Ruml, “Improved MDS-based localization,” Proc. of the IEEE INFOCOM 2004, Vol.4, pp. 2640-2651, 2004.
  15. [15] L. Li and T. Kunz, “Cooperative node localization using nonlinear data projection,” ACM Trans. on Sensor Networks (TOSN), Vol.5, Issue 1, Article No.1, doi: 10.1145/1464420.1464421, 2009.
  16. [16] S. Alikhani, M. St-Hilaire, and T. Kunz, “iCCA-MAP: A New Mobile Node Localization Algorithm,” Proc. of the 2009 IEEE Int. Conf. on Wireless and Mobile Computing, Networking and Communications, pp. 382-387, 2009.
  17. [17] S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs,” Discrete Applied Mathematics, Vol.70, Issue 3, pp. 217-229, 1996.
  18. [18] B. Rajan, I. Rajasingh, M. C. Monica, and P. Manuel, “Metric Dimension of Enhanced Hypercube Networks,” J. of Combinatorial Mathematics and Combinatorial Computing, Vol.67, pp. 5-15, 2008.
  19. [19] F. S. Raj and A. George, “On the metric dimension of few network sheets,” Proc. of the 2015 Int. Conf. on Robotics, Automation, Control and Embedded Systems (RACE), pp. 1-6, 2015.
  20. [20] P. J. Slater, “Leaves of trees,” Proc. of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 549-559, 1975.
  21. [21] P. J. Slater, “Dominating and Reference Sets in a Graph,” J. of Mathematical and Physical Sciences, Vol.22, No.4, pp. 445-455, 1988.
  22. [22] F. Harary and R. A. Melter, “On the Metric Dimension of a Graph,” Ars Combinatoria, Vol.2, pp. 191-195, 1976.
  23. [23] C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Cáceres, and M. L. Puertas, “On the metric dimension of some families of graphs,” Electronic Notes in Discrete Mathematics, Vol.22, pp. 129-133, 2005.
  24. [24] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood, “On the Metric Dimension of Cartesian Products of Graphs,” SIAM J. on Discrete Mathematics, Vol.21, Issue 2, pp. 423-441, 2007.
  25. [25] I. Javaid, M. T. Rahim, and K. Ali, “Families of regular graphs with constant metric dimension,” Utilitas Mathematica, Vol.75, pp. 21-33, 2008.
  26. [26] C. Poisson and P. Zhang, “The metric dimension of unicyclic graphs,” J. of Combinatorial Mathematics and Combinatorial Computing, Vol.40, pp. 17-32, 2002.
  27. [27] I. Tomescu and I. Javaid, “On the metric dimension of the Jahangir graph,” Bulletin mathématique de la Société des Sciences mathématiques de Roumanie, Vol.50, No.4, pp. 371-376, 2007.
  28. [28] I. Tomescu and M. Imran, “On Metric and Partition Dimensions of Some Infinite Regular Graphs,” Bulletin mathématique de la Société des Sciences mathématiques de Roumanie, Vol.52, No.4, pp. 461-472, 2009.
  29. [29] S. Khuller, B. Raghavachari, and A. Rosenfeld, “Localization in Graphs,” University of Maryland at College Park, Technical Report CS-TR-3326, 1994.
  30. [30] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,” Discrete Applied Mathematics, Vol.105, Issue 1-3, pp. 99-113, 2000.
  31. [31] R. A. Melter and I. Tomescu, “Metric bases in digital geometry,” Computer Vision, Graphics, and Image Processing, Vol.25, Issue 1, pp. 113-121, 1984.
  32. [32] P. S. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang, “On k-dimensional graphs and their bases,” Periodica Mathematica Hungarica, Vol.46, Issue 1, pp. 9-15, 2003.
  33. [33] M. Imran, A. Q. Baig, S. A. Bokhary, and E. T. Baskoro, “New classes of convex polytopes with constant metric dimension,” Utilias Mathematica, Vol.95, pp. 97-111, 2014.
  34. [34] M. Imran, A. Q. Baig, M. K. Shafiq, and I. Tomecu, “On Metric Dimension of Generalized Petersen Graphs P(n,3),” Ars Combinatoria, Vol.117, pp. 113-130, 2014.
  35. [35] M. Imran, A. Q. Baig, and S. A. U. H. Bokhary, “On the metric dimension of rotationally-symmetric graphs,” Ars Combinatoria, Vol.124, pp. 111-128, 2016.
  36. [36] M. Ali, G. Ali, M. Imran, A. Q. Baig, and M. K. Shafiq, “On the metric dimension of Mobius ladders,” Ars Combinatoria, Vol.105, pp. 403-410, 2012.
  37. [37] M. Munir, A. R. Nizami, Z. Iqbal, and H. Saeed, “Metric Dimension of the Mobius Ladder,” Ars Combinatoria, Vol.135, pp. 249-256, 2017.
  38. [38] F. Okamoto, B. Phinezy, and Z. Ping, “The local metric dimension of a graph,” Mathematica Bohemica, Vol.135, No.3, pp. 239-255, 2010.
  39. [39] Y. Ramírez-Cruz, O. R. Oellermann, and J. A. Rodríguez-Velázquez, “The simultaneous metric dimension of graph families,” Discrete Applied Mathematics, Vol.198, pp. 241-250, 2016.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on May. 24, 2023