Convex Partitioning of Large-Scale Sensor Networks in Complex Fields
Guang Yu Tan, Hongbo Jiang, Jun Liu, Anne-Marie Kermarrec · ACM Transactions on Sensor Networks · 2014
When a sensor network grows large, or when its topology becomes complex (e.g., containing many holes), network algorithms designed with a smaller or simpler setting in mind may be rendered rather inefficient. We propose to address this problem using a divide and conquer approach: the network is divided into convex pieces by a distributed convex partitioning protocol, using connectivity information only. A convex network partition exhibits some desirable properties that allow traditional algorithms to work to their full advantage. Based on this, we can achieve relatively high performance for an algorithm by combining algorithmic actions within individual partitions. We consider two important applications: virtual-coordinate-based geographic routing and connectivity-based localization. The former benefits from convex partition's friendliness to network embedding, which is crucial to generating accurate virtual coordinates for the nodes, while the latter leverages the fact that shortest paths are largely straight for node pairs within a convex partition. Experimental results show that the convex partition approach can significantly improve the performance of both applications in comparison with state-of-the-art solutions.