2009 · 13 citations · 13 references
ComputingComputer ScienceElectrical EngineeringAlgorithmsComputer NetworksWireless CommunicationsDistributed Sensor NetworksSensor NetworksWireless NetworksWireless Sensor NetworksAnchor-free LocalizationCommunication RangeNode LocalizationSensor Node LocalizationSimulation StudiesWireless LocalizationWireless Sensor Network LocalizationWorst-case Complexity
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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> , 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.
13
Computational geometry. an introduction
Franco P. Preparata, Michael Ian Shamos · 1985 · 2.4K citations
On graphs and rigidity of plane skeletal structures
G. Laman · Journal of Engineering Mathematics · 1970 · 1.1K citations
Semidefinite programming for ad hoc wireless sensor network localization
Pratik K. Biswas, Yinyu Ye · 2004 · 572 citations