Research On The Localizability Of Wireless Sensor Network Based On Graph Rigidity Theory

Wireless sensor networks, as a new type of wireless ad hoc network, have widely used in industry, agriculture, military, environmental observation and collecting information in disaster areas in recent years. Knowledge of nodes’ location is an essential requirement for many applications. Without location information of sensor nodes, the sensed data or the detection of events is nonsense. But we observe that almost all the time the network is not entirely localizable. However, a large portion, on average nearly 70%, of nodes is actually localizable. Specifically, 90% of network topologies have at least 50% of nodes localizable. Therefore, the concept of node localizability has been presented and studied. Based on the key characters of wireless sensor networks and the limitations of current research, this thesis focuses on the approaches of localizability testing and deployment adjustment. The research includes the following parts:(1) The graph rigidity theory which is the supporting theories for researching the node localizability is summarized.The theory includes the basic concepts, conclusions and high performance algorithms. Based on this theory, the new or improved algorithm about the localizability is proposed later.(2) A new method is proposed to improve the wheel algorithm in this paper. The wheel algorithm as a localizability testing algorithm with high performance, due to its distributed characteristic, has been widely used. But only a wheel graph contains at least three anchor nodes, can be recognized as localizable by the wheel algorithm. But this condition is not always satisfied, so the algorithm is hard to start and shut down early. In order to solve this problem, the definition of the simplest global rigid unit is proposed based on the rigidity theory. Any neighboring wheels, which contain the unit, are localizable according to the rigidity theory. The improved algorithm makes fully use of the anchor nodes with less computation complexity in identifying the rigid structure.(3) A new algorithm named MFA is proposed to adjust the non-localizable nodes in the network assisted by the mobile nodes. First, to ease the strict startup conditions of fine-grained adjustment approachs, pretreatment is performed by using the mobile anchor node in the MFA algorithm, so as to satisfying the conditions required by the fine-grained adjustment approachs. The improved algorithm is more adaptable. Second, MFA is not optimal, and some unnecessary edges are added into the network, so we propose a way to reduce the number of additional edges. The improved fine-grained adjustment approachs are proved to be optimal.(4) A software which can simulate the improved localization approach is designed. It contains four types of function: network deployment, localizability testing, localizability adjustment and localization. A case study is performed on the software. The rationality of the improved localization approach and the effectiveness of the algorithms are demonstrated by the simulation results.