Dynamic area coverage algorithms for static and mobile wireless sensor network environments using voronoi techniques

In recent years, Wireless Sensor Networks (WSNs) have gained significant research attention due to their prospects in various applications. In most application scenarios, good network coverage of the phenomenon of interest has to be maintained in order to transmit the required data to the sink node. In large and hostile environments where random deployment is usually the most feasible option, large regions may be left without coverage because some of the nodes missed their target locations. Even where an initial full coverage is ensured, energy depletion and abrupt malfunctioning eventually leave large areas in the network without coverage. This thesis focuses on developing Voronoi Tessellation-based Coverage Optimization Algorithms for Static and Mobile Wireless Sensor Networks, where a large number of static nodes are supported by few mobile nodes in carrying out the sensing task. Voronoi tessellation consists of a set of sites in a plane partitioned in such a way that the entire region within any one of the partitions is closest to only one site than to any other site in the plane. The sites are the static sensor nodes and the partitions, the voronoi polygons. Each voronoi polygon is bounded by edges and vertices. A voronoi edge is the line equidistant to two adjacent voronoi sites (static nodes). A voronoi vertex on the other hand is formed by the intersection of three or more voronoi edges. After deployment, static nodes communicate among themselves to form their Voronoi polygons, such that each polygon consists of only one static node. Since voronoi tessellation alone can only generate voronoi vertices inside the network, static nodes along the network boundaries discover their vertices along the boundary by using a Boundary Vertex Discovery Model, which is proposed in this thesis. Each static node then checks whether there exist a region in its polygon without coverage. If a coverage-hole is found, static nodes compute the size of the hole and request mobile nodes to target locations for optimal coverage. In order to ensure the shortest path movement of mobile nodes to target locations, a Matrix Row/Column Elimination model is proposed. The proposed Voronoi Tessellation-based Coverage Optimization Algorithms for Static and Mobile Wireless Sensor Networks provides up to 99% coverage at various number of mobile-static sensor node combination and up to 12% reduction in average moving distance. Moreover, energy consumption as well as the number of deployed nodes is minimized, while maintaining the same level of coverage compared to existing coverage models