Network Localization on Unit Disk Graphs

Details Network Localization on Unit Disk Graphs Network Localization on Unit Disk Graphs

2011-08-04

arxiv.org/abs/1108.0972v1

Computer Science

Distributed, Parallel, and Cluster Computing

5 pages

Scientific paper

We study the problem of cooperative localization of a large network of nodes in integer-coordinated unit disk graphs, a simplified but useful version of general random graph. Exploiting the property that the radius $r$ sets clear cut on the connectivity of two nodes, we propose an essential philosophy that "no connectivity is also useful information just like the information being connected" in unit disk graphs. Exercising this philosophy, we show that the conventional network localization problem can be re-formulated to significantly reduce the search space, and that global rigidity, a necessary and sufficient condition for the existence of unique solution in general graphs, is no longer necessary. While the problem is still NP-hard, we show that a (depth-first) tree-search algorithm with memory O(N) ($N$ is the network size) can be developed, and for practical setups, the search complexity and speed is very manageable, and is magnitudes less than the conventional problem, especially when the graph is sparse or when only very limited anchor nodes are available.

Affiliated with

Also associated with

No associations

Rating

Network Localization on Unit Disk Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Network Localization on Unit Disk Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network Localization on Unit Disk Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-13708