Multi-hop network localization in unit disk graph model under noisy measurement using tree-search algorithm with graph-properties-assist traversing selection

Abstract

This paper proposes a heuristic approach to efficiently traverse through search space in wireless localization in unit disk graph model. The main idea is to accommodate graph characteristics as metrics for branch selection. Selecting appropriate branching order eliminates infeasible branches quicker than random selection. We show that graph properties such as connectivity, measured distances, and shortest paths to anchor nodes (nodes with known-locations), can drastically reduce the number of iterations (branching) required to traverse thru the possible realization of the wireless network. A normalized weight-sum function of those parameters is used as an evaluation function in selecting branching direction. We extensively perform experiments to find good weights for evaluation function of those graph characteristics.  Additionally, we apply this algorithm in a more realistic environment where noise is observed during the measurement of distances. We use a modified version of our algorithm by relaxing feasible constraints to tolerate more discrepancy allowing error within a threshold. A tradeoff between complexity and the probability of finding the feasible solution is shown. The results show that the adding error does increase the complexity while maintaining the ability to find solution within a timely manner.