DocumentCode :
2445777
Title :
Multi-hop network localization in multi-radius unit disk graph model
Author :
Kaewprapha, P. ; Jing Li ; Puttarak, Nattakan
Author_Institution :
Dept. of ECE, Lehigh Univ., Bethlehem, PA, USA
fYear :
2012
fDate :
25-27 Oct. 2012
Firstpage :
1
Lastpage :
6
Abstract :
Consider localizing a large number of wireless nodes, none of which has direct connectivity to 3 or more reference terminals. Since no node has enough distance measures to perform trilateration, they cannot determine their locations individually, but must rely on multihop network localization approaches and graph rigidity to get localized altogether. Previous work has modeled this problem as a unit disk graph, where the radius r sets a clear cut on node connectivity - within r two nodes have absolute connection and hence reliable distance measure, and beyond r they have none. Such a black-and-white model is idealistic, and this paper considers a more practical scenario where two nodes, in addition to being absolutely connected or disconnected, may fall in a gray area of random connectivity, and subsequently their distance measure may be available or reliable with some probability p. We propose a network localization scheme that captures this situation via a tree-search algorithm based on a multi-radius unit graph model. Leveraging an interesting philosophy of "no news is good news," the implicit but useful knowledge that two nodes have no connectivity is also exploited to substantially reduce the search space and expedite the localization speed. Although the general problem of network localization is NP-Hard, extensive simulations on randomly-generated graph geometry show that the proposed search algorithm has a very fast average computation time, far less than the worst-case (if the solution exists).
Keywords :
computational complexity; graph theory; radio networks; tree searching; NP-hard problem; black-and-white model; distance measurement; graph rigidity; multihop network localization approach; multiradius unit disk graph model; randomly-generated graph geometry; reference terminals; search space reduction; tree-search algorithm; wireless nodes;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Wireless Communications & Signal Processing (WCSP), 2012 International Conference on
Conference_Location :
Huangshan
Print_ISBN :
978-1-4673-5830-9
Electronic_ISBN :
978-1-4673-5829-3
Type :
conf
DOI :
10.1109/WCSP.2012.6542944
Filename :
6542944
Link To Document :
بازگشت