AUTHORS: Athanasios Iliodromitis, George Pantazis, Vasileios Vescoukis

Download as PDF

ABSTRACT: In recent years, Wireless Sensor Networks (WSNs) have rapidly evolved and now comprise a powerful tool in monitoring and observation of the natural environment, among other fields. The use of WSNs is critical in early warning systems, which are of high importance today. In fact, WSNs are adopted more and more in various applications, e.g. for fire or deformation detection. The optimum deployment of sensors is a multi-dimensional problem, which has two main components; network and positioning approach. Although lots of work has dealt with the issue, most of it emphasizes on mere network approach (communication, energy consumption) and not on the topography (positioning) of the sensors in achieving ideal geometry. In some cases, it is hard or even impossible to achieve perfect geometry in nodes’ deployment. The ideal and desirable scenario of nodes arranged in square or hexagonal grid would raise extremely the cost of the network, especially in unfriendly or hostile environments. In such environments the positions of the sensors have to be chosen among a list of possible points, which in most cases are randomly distributed. This constraint has to be taken under consideration during the WSN planning. Full geographical coverage is in some applications of the same, if not of greater, importance than the network coverage. Cost is a crucial factor at network planning and given that resources are often limited, what matters, is to cover the whole area with the minimum number of sensors. This paper suggests a deployment method for nodes, in large scale and high density WSNs, based on Centroidal Voronoi Tessellation (CVT). It approximates the solution through the geometry of the random points and proposes a deployment plan, for the given characteristics of the study area, in order to achieve a deployment as near as possible to the ideal one.

KEYWORDS: WSN, Wireless Sensor Network, CVT, Centroidal Voronoi Tessellation, sensors, sensor deployment, spatial covarage

REFERENCES:

[1] A. Iliodromitis, 'Development of integrated methodology for coverage optimization and evaluation, of Wireless Sensor Networks for widerange applications', Ph.D. in Progress, Athens: National Technical University of Athens, 2016.

[2] S. Toumpis and L. Tassiulas, 'Optimal deployment of large wireless sensor networks,' IEEE Transactions on Information Theory, pp. 2935 - 2953, 05 July 2006.

[3] H. Zhou, M. Jin and H. Wu, 'A distributed delaunay triangulation algorithm based on centroidal voronoi tessellation for wireless sensor networks,' in 14th ACM international symposium on Mobile ad hoc networking and computing, New York, 2013.

[4] E. Kolega, Multi-criterial evaluation of high density Wireless Sensor Network Structures for enviromental purposes, Athens: Ph. D. Thesis, 2014.

[5] E. Kolega and V. Vescoukis, 'Efficient WSN infrastructures for large environmental,' in Intelligent Monitoring, Control and Security of Critical, Aachen, 2013.

[6] E. Kolega, V. Vescoukis and D. Douligeris, 'Forest Fire Sensing and Decision Support,' in International Congress on Environmental Modeling and Software (iEMSs), Ottawa, Ontario, 2010.

[7] Y.-C. Wang, C.-C. Hu and Y.-C. Tseng, 'Efficient deployment algorithms for ensuring coverage and connectivity of wireless sensor networks,' in First International Conference on Wireless Internet (WICON'05), 2005.

[8] J. Zhang and F. Zhou, 'Study on Optimal Regular Deployment Patterns of Wireless Sensor Network,' Research Journal of Applied Sciences, Engineering and Technology, pp. 2300-2303, 2012.

[9] M. A. Vieira, L. F. Vieira and et al., 'Scheduling nodes in wireless sensor networks: a Voronoi approach,' in Local Computer Networks, 2003. LCN '03. Proceedings. 28th Annual IEEE International Conference, 2003.

[10] A. Darag and V. Saroha, 'An Efficient Coverage Scheme for Wireless Sensor Network,' International Journal of Advanced Research in Computer Science and Software Engineering, 4 2013.

[11] J. Wang and S. Medidi, 'Energy Efficient Coverage with Variable Sensing Radii in Wireless Sensor Networks,' in Third IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob 2007), White Plains, NY, 2007.

[12] C. Vu and Y. Li, 'Delaunay-triangulation based complete coverage in wireless sensor networks,' in Pervasive Computing and Communications, 2009. PerCom 2009. IEEE International Conference, Galveston, TX, 2009.

[13] C.-S. Wu, K.-C. Lee and Y.-C. Chung, 'A Delaunay triangulation based method for wireless sensor network deployment,' in 12th International Conference on Parallel and Distributed Systems - (ICPADS'06), Minneapolis, MN, 2006.

[14] A. Devaraj, 'Mesh Simplification in Wireless Sensor Networks Using INRCDTS,' in 4th International Conference on Circuits, Systems, Kuala Lumpur, 2015.

[15] M. Argany, M. A. Mostafavi and et al., 'A GIS Based Wireless Sensor Network Coverage Estimation and Optimization: A Voronoi Approach,' in Transactions on Computational Science XIV, Springer Berlin Heidelberg, 2011, pp. 151-172.

[16] G. Song, Y. Zhou, F. Ding and A. Song, 'A mobile sensor network system for monitoring of unfriendly enviroments,' Sensors, pp. 7259-7274, 8 2008.

[17] Q. Du, V. Faber and M. Gunzburger, 'Centroidal Voronoi Tessellations: Applications and Algorithms,' SIAM Review, pp. 637-676, 1999.

[18] Q. Du and D. Wang, 'The Optimal Centroidal Voronoi Tessellations and the Gersho's Conjecture in the Three-Dimensional Space,' Computers and Mathematics with Applications, 2005.

[19] J. Burns, 'Centroidal voronoi tessellations,' 2009.

[20] M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry, Algorithms and Applications, Berlin: Springer, 2008.

[21] M. Joswig and T. Theobald, Polyhedral and algebraic methods in computational geometry, Wiesbaden: Springer, 1998.