Voronoi diagram modelling for wireless Ad-Hoc sensor network coverage

Abstract

This thesis aims at a basic geometrical understanding of Voronoi diagrams and Voronoi diagram modelling for Wireless Ad hoc Sensor coverage. What is known as the Fortune algorithm for constructing Voronoi diagrams is explained. Implementation of the Fortune algorithm is also shown as a part of this thesis. Several applications of Voronoi diagrams are explained with practical examples. Coverage problem in wireless ad hoc sensor networks is modelled with Voronoi diagram and its dual Delaunay triangulation. The problem of best and worst coverage for a wireless ad hoc sensor networks are discussed. Coverage paths like Best and worst paths are explained in detail. The algorithms for determining best coverage paths and worst coverage paths are described and implemented in MATLAB& C. Results for best coverage paths and worst coverage paths are shown for a given number of sensors placed in the sensor field.