Localization Using Joint Distance And Bearing Information For Wireless Sensor Networks

Wireless sensor network (WSN) localization problem with given or measured data between enough neighboring pairs is to find precisely an assignment of coordinates to all sensor nodes in a distributed manner. In recent years WSN localization has been one of the hottest topics in WSN research. On one hand, position-awareness is a prerequisite for almost all monitoring or control tasks. On the other hand, node position information can also support diverse WSN protocols and algorithms. Despite a large number of approaches developed for2D localization, there are still many unsolved problems in this area. The challenges to be addressed are both in analyzing mathematically the characterizations of WSN unique localization and development of efficient3D localization algorithms under a variety of conditions. Besides, to the best of my knowledge, there is as yet no anchor-free method that is physical location available. Therefore, this thesis draws on powerful tool from graph rigidity theory, combinatorial optimization theory and graph transform therom to study WSN unique localization problem and to propose an anchor-free and computitionally simple distributed localization algorithm for WSN.First, the WSN unique localization problem is switched to verifying the global rigidity of corresponding frames and analyzing the localizability accordingly. Let G be the grounded graph of a WSN. Then the networks is uniquely localizable if and only if(G, p) is globally rigid, where p is the imbedding of G into Rd. Rigidity is less strict than global rigidity. Based on distance constraint, numerous rigidity and global rigidity theories are studied and illustrated by specific examples. Then bearing constraint based unique localization is introduced, especially for3D. Bearing information is dimension transparent, which leads to the good properties of parallel rigidity. Combining these two constrints may provide futher results. Therefor, based on fully combined constraints a proposition for global rigidity is presented for3D without proof. We also present a specific counterexample to show that Laman condition plus3-connection is only necessary but not sufficient condition for frame rigidity in3D.Secondly, motivated by fully combined constraint based global rigidity analsis, this thesis makes use of both distance and bearing information to propose a light weighted distributed2D localizatioin algorithm UAFL (unique anchor-free localization). UAFL is made up of four steps, including system initialization, local coordinate system setup, local position computation and global position computation. In the local coordinate system setup stage, the flip ambiguity (FA) problem is resolved in term of angle of arrival measurement. On local position computation, we consider all24different scenarios to require a position unaware node to be a neighbor of just one extra position awawe node to compute its position. Global position computation is the most important and difficult point. In order to be able to treat the translation and rotation in a consistent way so that they can be combined easily, we introduce homogeneous coordinates to express points. In this way global coordinates are calculated when we get the transform matrix between neighbors. When the data-sink is selected as a physical location reference to all the nodes, we can get the physical coordinate without any anchor node. UAFL is verified both by particular numerical instance and through simulation. The simulation results show that it outperforms some other congeneric algorithms in terms of localization coverage and localization error. The recommended deployment peremeter for WSN applications is node degree being9to12with respect to node localization.A direct extention of the2D method into3D is not stright forward. Up to now few true3D techniques have been designed. Following UAFL in2D, a three dimensional anchor-free localization algorithm (3D-AFL) is further proposed in terms of frame structure. Some sub algorithms include neighbor discovery and local coordinate system construction, where FA problem is also resolved by means of AoA information. Local position to global position transformation is the most essential and difficult point in3D. We perform an in-depth study to put the axe in the helve. The adjacency transformation matrix is also a lightly weighted computation technology that fits well with the WSN requirement. Simulation results demennstrate the effectiveness of3D-AFL. For node degree equals from11to13, the deployment wins best tradeoff among localization percentage, precision and economic cost. Meanwhile we find that3D localization, as localizability analysis in3D, leaves much room for further research and development. One possible work is to take the clusterring strategy to reduce transformation times during global coordinate calculation. In this way the WSN may scale well.Finally, the thesis proposed a route-localization co-design protocol based on cross layer design phylosophy. The sink node, which acts as the target point during sensor data gathering, is also the unique fixed destination node in the process of global coordinate transformation. Therefore, it is feasible to choose hop count as the evaluation parametre in optimizing the recursion route. The next hop binding table can built accordingly without initiating flooding storm. Not only3D-AFL is optimized but also an optional routing scheme is meanwhile produced. Simulation results verify that localization time, especially in3D, is reduced in this way.To summarize, this thesis first focuses on the fundamental mathematical analysis domain, which we deem a basis for specific algorithms. We studied in an in-depth way the graph rigidity theory revealing that the combination of both distance constraint and bearing constraint leads to necessar and sufficient condition. A counterexample for verifying3D rigidity is presented. A fully combined constraint based global rigidity proposition is given without proof. This also enlightens our proposing an anchor free and computationally simple ad hoc localization algorithm for both2D (UAFL) and3D (3D-AFL) WSN. A codesigned routing-localization protocol is proposed to optimize the localization method. Finally the thesis concludes through simulation results to verigy the algorithm performance as well as to recommend engineering parameter.