An Online Distributed Boundary Detection and Classification Algorithm for Mobile Sensor Networks

Pham Duy Hung, Tran Quang Vinh, Trung Dung Ngo


We present a novel online distributed boundary detection and classification algorithm in order to improve accuracy of boundary detection and classification for mobile sensor networks. This algorithm is developed by incorporating a boundary detection algorithm and our newly proposed boundary error correction algorithm. It is a fully distributed algorithm based on the geometric approach allowing to remove boundary errors without recursive process and global synchronization. Moreover, the algorithm allows mobile nodes to identify their states corresponding to their positions in network topologies, leading to self-classification of interior and exterior boundaries of network topologies. We have demonstrated effectiveness of
this algorithm in both simulation and real-world experiments and proved that the accuracy of the ratio of correctly identified nodes over the total number of nodes is 100%.

Full Text:



S. K. Lee and J. McLurkin, “Distributed cohesive configuration control for swarm robots with boundary information and network sensing,” in Intelligent Robots and Systems (IROS 2014), 2014 IEEE/RSJ International Conference on. IEEE, 2014, pp. 1161–1167.

Y. Keung, B. Li, and Q. Zhang, “The intrusion detection in mobile sensor network,” in Proceedings of the eleventh ACM international symposium on Mobile ad hoc networking and computing. ACM, 2010, pp. 11–20.

S. P. Fekete, A. Kr¨oller, D. Pfisterer, S. Fischer, and C. Buschmann, Neighborhood-Based Topology Recognition in Sensor Networks. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 123–136.

A. Kr¨oller, S. P. Fekete, D. Pfisterer, and S. Fischer, “Deterministic boundary recognition and topology extraction for large sensor networks,” in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. Society for Industrial and Applied Mathematics, 2006, pp. 1000–1009.

Y. Wang, J. Gao, and J. S. Mitchell, “Boundary recognition in sensor networks by topological methods,” in Proceedings of the 12th annual international conference on Mobile computing and networking. ACM, 2006, pp. 122–133.

O. Saukh, R. Sauter, M. Gauger, and P. J. Marr´on, “On boundary recognition without location information in wireless sensor networks,” ACM Transactions on Sensor Networks (TOSN), vol. 6, no. 3, p. 20, 2010.

W.-C. Chu and K.-F. Ssu, “Decentralized boundary detection without location information in wireless sensor networks,” in 2012 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2012, pp. 1720–1724.

A. Dabba and R. Beghdad, “Bcp: A border coverage protocol for

wireless sensor networks,” in Science and Information Conference (SAI), 2014. IEEE, 2014, pp. 632–640.

R. Beghdad and A. Lamraoui, “Boundary and holes recognition in wireless sensor networks,” Journal of Innovation in Digital Ecosystems, vol. 3, no. 1, pp. 1–14, 2016.

L.-H. Zhao, W. Liu, H. Lei, R. Zhang, and Q. Tan, “The detection of boundary nodes and coverage holes in wireless sensor networks,” Mobile Information Systems, vol. 2016, 2016.

J. McLurkin and E. D. Demaine, “A distributed boundary detection algorithm for multi-robot systems,” in 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct 2009, pp. 4791–4798.

W.-C. Chu and K.-F. Ssu, “Location-free boundary detection in mobile wireless sensor networks with a distributed approach,” Computer Networks, vol. 70, pp. 96 – 112, 2014.

B. Huang, W. Wu, G. Gao, and T. Zhang, “Recognizing boundaries in wireless sensor networks based on local connectivity information,” International Journal of Distributed Sensor Networks, 2014.

P. D. Hung, T. Q. Vinh, and T. D. Ngo, “An online local boundary detection and classification algorithm for networked multi-robot systems,” in 2016 International Conference on Advanced Technologies for Communications (ATC), Oct 2016, pp. 253–258.

P. D. Hung, T. Q. Vinh, and T. D. Ngo, “A scalable, decentralised large-scale network of mobile robots for multi-target tracking,” in Intelligent Autonomous Systems 13. Springer, 2014, pp. 621–637.


Copyright (c) 2017 REV Journal on Electronics and Communications

Copyright © 2011-2021
Radio and Electronics Association of Vietnam
All rights reserved