CONSEL: Connectivity-based Segmentation in Large-Scale 2D/3D Sensor Networks

A cardinal prerequisite for the system design of a sensor network, is to understand the geometric environment where sensor nodes are deployed. The global topology of a large-scale sensor network is often complex and irregular, possibly containing obstacles/holes. A convex network partition, so-called segmentation, is to divide a network into convex regions, such that traditional algorithms designed for a simple geometric region can be applied. Existing segmentation algorithms highly depend on concave node detection on the boundary or sink extraction on the medial axis, thus leading to quite sensitive performance to the boundary noise. More severely, since they exploit the network's 2D geometric properties, either explicitly or implicitly, so far there has been no general 3D segmentation solution. In this paper, we bring a new view to segmentation from a Morse function perspective, bridging the convex regions and the Reeb graph of a network. Accordingly, we propose a novel distributed and scalable algorithm, named CONSEL, for CONnectivity-based SEgmentation in Large-scale 2D/3D sensor networks. Specifically, several boundary nodes first perform flooding to construct the Reeb graph. The ordinary nodes then compute mutex pairs locally, thereby generating the coarse segmentation. Next the neighbor regions which are not mutex pair are merged together. Finally, by ignoring mutex pairs which leads to small concavity, we provide the constraints for approximately convex decomposition. CONSEL is more desirable compared with previous studies: (1) it works for both 2D and 3D sensor networks; (2) it only relies on network connectivity information; (3) it guarantees a bound for the regions' deviation from convexity. Extensive simulations show that CONSEL works well in the presence of holes and shape variation, always yielding appropriate segmentation results.