Distributed Algorithms for Complete Coverage in Ad hoc Wireless Network using Graph Theory

Most existing studies investigate the coverage problem by using of computational geometry methodology. Their algorithms assume accurate node coordinates are available, anddetermine the coverage by geometric tools, such as well-known Delaunay triangulations, Voronoi diagrams, and geometric diskgraphs, and etc. In this study, we will resolve the restrictions of previous methods and present an efficient design of distributedcoverage that provides the possibility of access to the partitionednetwork coverage as well as possesses minimum hardware costs and energy loss.Compared with existing methods, our design hasa particular advantage, which permits us to configure or adjust the quality of coverage by adequately exploiting diverse sensingranges and specific requirements of different applications. We formally prove the correctness and evaluate the effectiveness ofour approach through extensive simulations and comparisons with the stateof-the-art approaches.

Keywords:

wireless ad hoc and sensor networks , coverage , distributed , connectivity , topologic graph , cycle partition , mobile , graph(key words)