A Set of Topological Graphs for 2-D Sensor Ad Hoc Networks

Recently, different types of sensors have been developed to detect environmental changes (e.g., instability of the earth´s crust) and to reduce the associated damage. For an efficient usage of the sensor technology, several design factors (e.g., topology and sensing coverage) should be taken into account. In this paper, we focus on the underlying topology of sensor networks in two-dimensional environments and propose a new set of graphs referred to as the Derived Circles (DC^alpha) graphs. We show that DC^alpha graphs are locally constructed, connected, power efficient, and orientation-invariant. We also show that DC^alpha graphs have a minimum degree of one and an Euclidean dilation of one. Furthermore, via simulations, we demonstrate that DC^alpha graphs outperform the half space proximal (HSP) graph in terms of the network dilation, Euclidean dilation, and power dilation. This, in turn, reduces the energy consumption of nodes and accordingly prolongs the network lifetime.