Distributed Positioning Algorithms For Wireless Sensor Network

Many wireless sensor network protocols and applications assume the knowledge of geographic location of nodes. The absolute location of each networked node is an assumed fact by most sensor networks which can then present the sensed information on a geographical map. Finding location for all nodes in a network where only a limited fraction of nodes have self location capability is important since it is not practical to equip each node with GPS due to power, cost, form factor or line of sight condition. Wireless sensor networks, where the nodes are randomly deployed, resemble an ad-hoc network environment with high degrees of freedom and distributed composition, and thus pose significant challenges on positioning algorithms.There are two major classes of problems that make positioning within an wireless sensor network challenging: the range error problem, and the sparse anchor node problem. We can answer the range error problem with redundancy and over-determined systems of equations. The distributed algorithm, which works through collaborations between nodes and iterative delivery of message across the network, provides a clean solution to the sparse anchor node problem. The difficulty, however, is that neither solution works in the presence of both problems, because redundancy calls for high density. To answer the orthogonality of these two separate and conflicting solutions, a two-stage algorithm is proposed. At the starting phase, we compute the extended ranges to the anchor node so as to derive the initial estimated position; at the refinement phase, the constraints imposed by the distances to the direct (one-hop) neighbors of a node will force the new position towards the true position after a number of refinement iterations. To overcome the two important limitations of the pure refinement algorithm, we introduce the concept of confidence metrics and ill-connected nodes to improve the refinement process.First, the paper analyses and compares two typical distributed algorithms. To ensure the consistency of the algorithms, we developed a hop-based distributed positioning method for the starting phase based on the algorithm DV-hop. Then the paper explains in detail the design and implementation of the whole two-phase algorithm. Further, the paper also analyzes the cost for implementing the algorithm in terms of computation, power and time. Experimentation is then performed to verify the consistency and enhanced accuracy of the algorithms after introducing the refinement phase. In the end, we will discuss the algorithms on a more qualitative level, looking at the tradeoff between various algorithms, possible sources of error, and areas for improvement and future growth.