Approximate Convex Decomposition Based on Connectivity in Large-scale 3D Wireless Sensor Networks

摘要

Convex decomposition with concave boundaries is to partition network into a set of simpler components with no concave surface merely, which has great significance for routing, localization, coverage and data acquisition. With the development of a WSN application, researches on 3D convex segmentation will gain much attention and study. However, currently, it is a new research field, which has not yet been studied much. Toward that end, this paper proposes an Approximate Convex Decomposition based on Connectivity (ACDC) only to 3D WSNs with uniform random distribution deployment. We identify the concave nodes that have meet the need of concavity and the characteristics that differentiate saddle nodes from boundary nodes. Beginning with the concave nodes that lead to holes and concave valleys, we partition the irregular sensor network into nicely shaped pieces. Compared with previous work, our proposed algorithm actually realizes the essential convex decomposition for complex 3D WSNs with holes and does not require knowledge of sensor locations, using, instead, only network connectivity information; furthermore, finding a balance of network concavity and number of sub-networks leads to an near optimal topology of the 3D field, meeting all our requirements. Because ACDC focuses on the topology of the 3D field, an near optimal result that meets our requirements is provided by balancing network concavity with the number of sub-networks. Results form extensive simulations show that ACDC works well in the presence of holes and shape variations, always yielding appropriate segmentation results.