Network Localization

In the context of distributed algorithms for network management, the objective of network localization is to compute geographical locations of communicating nodes from their adjacency relationship. It is closely related to the graph embedding (embedding a graph in high dimensional Euclidean space) and graph drawing (drawing graph nicely in a plane or 3D space) problems. When the localization solutions are good enough for mission needs, network localization can eliminate or reduce the need for Global Position System (GPS) to determine the network topology. The spring algorithm in the graph drawing literature is considered the state of the art solution. The spring algorithm is a nonlinear optimization algorithm where imaginary springs are installed between node pairs for them to bounce (search) toward the true network topology. The following graphs illusteate the intial state of nodes, and the topology generated by spring after a few hundre iterations.

It is clear from hundreds of runs of simulations that the spring algorithm faces three major issues: (1) convergence speed, (2) concavity of the topology, and (3) oscillating behaviors. A deterministic approach based on worst case design may not be suitable for solving this problem because no known asymptotic convergence condition exists. Currently we are developing an adaptive search technique which has led to some interesting results shown below. The new method is much faster than traditional techniques, and it can converge to complex network topologies correctly. Thorough analysis is being made to prove correctness of our algorithm.

[1]. Drawing Graphs : Methods and Models (Paperback), by Michael Kaufmann (Editor), Dorothea Wagner (Editor)