Relation Between Gradients and Geographic Distances in Dense Sensor Networks with Greedy Message Forwarding

The distributed gradient protocol is a common building block to perform several tasks in a wireless sensor network.The gradient calculates the minimum hop-distances between each sensor and a specified set of anchor sensors. This calculation is performed using a distributed greedy forwarding of messages in the network. Several virtual localization protocols use gradients to compute the virtual coordinates of the sensors. The quality of these coordinate systems depend son the relation between the value of the gradient and the real geographic distances between sensors.In this paper a formal proof of such relation is provided in the case of dense sensor networks with homogeneous sensor communication range r. The minimum-hop distances between a sensor and an achor is bounded to be in a range defined by two geographic distances. The size of this range decreases with increasing density of the network and it is equal to the maximum resolution (the communication range r) when the density is high enough.