Grid emulation for managing random sensor networks

A common assumption in sensor networks is that sensors are located according to a uniform random distribution. In this paper, we show that uniform random points on the two dimensional unit square are almost a “grid”. In particular, for a synchronous geographic sensor network we show how to emulate any grid protocol on random sensor networks, with high probability. This suggests the following framework. In order to solve a problem on a random sensor network, we solve the same problem on a grid. Then we use our emulation to make the obtained solution suitable for random sensor network. We analyze the cost of the emulation in terms of consumed energy and time. Finally, we provide some examples that illustrate our method.