Length-based anchor-free localization in a fully covered sensor network

Localization is an important issue for Wireless Sensor Networks (WSN). We consider a WSN consisting of identical sensors. All known distances between the sensors are assumed to be less than the communication range of the sensors and all unknown distances greater. We also assume that the communication range is at least twice as much as the sensing range. Every point in the field of interest is assumed to be within the sensing zone of some sensor. Under this model, we propose an anchor-free length-based localization algorithm. The worst case time complexity of the algorithm is O(|E|) (where E is the set of edges of the network graph). We carry out simulation studies to observe that under uniform distribution, the number of edges is actually much lower than n², if just about enough sensors are deployed to cover the total field. We prove that, under this model, the solution to the localization problem is unique. We also provide a simple technique for verifying the assumption that all points in the field are covered.