Scalable sensor localization via ball-decomposition algorithm

We consider a wireless sensor network localization problem, with range-free and anchor-free settings, i.e., each sensor can only detect which sensors are in the neighbor. We observe issues with existing algorithms that cause inaccurate localization, and propose a new decomposition-based algorithm for resolving these issues. The proposed algorithm consists of three parts: (1) decomposition of a sensor network into small networks that may have large overlap with other small networks by a randomized ball-decomposition algorithm; (2) localization of each network by MDS-MAP and physical simulation-based local refinement; (3) gluing of small networks by a divide-and-conquer algorithm. Intuitively, our algorithm finds a good localization because it finds almost optimal localization for each small graph, and moreover, it glues them together optimally. We conduct computational experiments in both synthetic and realistic setting. The proposed algorithm is more accurate, efficient, and memory-saving than existing algorithms. In fact, it accurately localizes 200,000 sensors on European region in 3 hours, whereas other existing algorithms scale only up to 10,000 sensors. Thus, the algorithm can handle problem sizes several dozen times as large as existing algorithms can.