Nodes along the boundaries of a Wireless Sensor Network (WSN) play some other important roles in addition to their routine tasks. A prior knowledge of the WSN boundaries can effectively be utilized in numerous WSN aspects pertaining to mobile events, mobile nodes, geographic routing, shape and coverage maintenance, barrier coverage etc. In this paper, we present a localized method based on actual connectivity graph and nodes' locations to detect the boundaries of a WSN. The proposed scheme does not make any idealistic assumption like Unit Disk Graph (UDG) model, uniform node deployment, or specific node degrees. The method is based on the idea of alpha-shapes – geometric structures used to capture the shapes formed by a set of points in space. With an appropriate value of alpha, alpha-shapes capture the meaningful boundaries of a point cloud. The value for the parameter alpha is computed locally by each node as ?2/d where d is the distance between the node and its farthest neighbor. The analytical and simulated results show the robustness of the proposed scheme under dynamic network conditions.

1. Estrin, D. , Girod, L. , Pottie, G. and Srivastava, M. , 2001. Instrumenting the world with wireless sensor networks. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. Vol. 4, 2033-2036.
2. Rührup, S. and Stojmenovi, I. , 2010, April. Contention-based georouting with guaranteed delivery, minimal communication overhead, and shorter paths in wireless sensor networks. In Proceedings IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 1-9.
3. Shang, Y. , Ruml, W. , Zhang, Y. and Fromherz, M. P. , 2003. Localization from mere connectivity. In Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, 201-212.
4. Sahoo, P. K. , Sheu, J. P. and Hsieh, K. Y. , 2013. Target tracking and boundary node selection algorithms of wireless sensor networks for internet services. Information Sciences, 230, 21-38.
5. Fang, Q. , Gao, J. and Guibas, L. J. , 2006. Locating and bypassing holes in sensor networks. Mobile networks and Applications, 11(2), 187-200.
6. Kumar, S. , Lai, T. H. and Arora, A. , 2005, August. Barrier coverage with wireless sensors. In Proceedings of the 11th annual international conference on Mobile computing and networking, 284-298).
7. Akyildiz, I. F. , Su, W. , Sankarasubramaniam, Y. and Cayirci, E. , 2002. A survey on sensor networks. IEEE communications magazine, 40(8), 102-114.
8. Edelsbrunner, H. , Kirkpatrick, D. and Seidel, R. , 1983. On the shape of a set of points in the plane. IEEE Transactions on information theory, 29(4), 551-559.
9. Wang, Y. , Gao, J. and Mitchell, J. S. , 2006. Boundary recognition in sensor networks by topological methods. In Proceedings of the 12th ACM annual international conference on Mobile computing and networking, 122-133.
10. Fayed, M. and Mouftah, H. T. , 2009. Localised alpha-shape computations for boundary recognition in sensor networks. Ad Hoc Networks, 7(6), 1259-1269.
11. Liu, W. J. and Feng, K. T. , 2009. Greedy routing with anti-void traversal for wireless sensor networks. IEEE Transactions on Mobile Computing, 8(7), 910-922.
12. Kim, Y. J. , Govindan, R. , Karp, B. and Shenker, S. , 2005. Geographic routing made practical. In Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, 2, 217-230).
13. Kim, Y. J. , Govindan, R. , Karp, B. and Shenker, S. , 2005. On the pitfalls of geographic face routing. In Proceedings of the 2005 joint workshop on Foundations of mobile computing, 34-43.
14. Fekete, S. P. , Kröller, A. , Pfisterer, D. , Fischer, S. and Buschmann, C. , 2004. Neighborhood-based topology recognition in sensor networks. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, 123-136.
15. Fekete, S. P. , Kaufmann, M. , Kröller, A. and Lehmann, K. , 2005. A new approach for boundary recognition in geometric sensor networks. arXiv preprint cs/0508006.
16. Chen, Y. H. , Chung, W. H. , Ni, G. K. , Zhang, H. and Kuo, S. Y. , 2012. Optimal self boundary recognition with two-hop information for ad hoc networks. In 2012 IEEE Wireless Communications and Networking Conference (WCNC) 1910-1914.
17. Kröller, A. , Fekete, S. P. , Pfisterer, D. and Fischer, S. , 2006, January. Deterministic boundary recognition and topology extraction for large sensor networks. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm 1000-1009.
18. Ahmed, N. , Kanhere, S. S. and Jha, S. , 2005. The holes problem in wireless sensor networks: a survey. ACM SIGMOBILE Mobile Computing and Communications Review, 9(2), 4-18.
19. Luo, R. C. , Tu, L. C. and Chen, O. , 2005. Auto-deployment of mobile nodes in wireless sensor networks using grid method. In 2005 IEEE International Conference on Industrial Technology, 359-364).
20. Kuhn, F. , Wattenhofer, R. and Zollinger, A. , 2003. Ad-hoc networks beyond unit disk graphs. In Proceedings of the 2003 joint workshop on Foundations of mobile computing, 69-78.
21. Barriere, L. , Fraigniaud, P. , Narayanan, L. and Opatrny, J. , 2003. Robust position?based routing in wireless ad hoc networks with irregular transmission ranges. Wireless Communications and Mobile Computing, 3(2), pp. 141-153.

Wireless Sensor Network Alpha-shape Boundary Detection