Research On Regional Approximate Convexity Method Based On Connectivity In 3D Wireless Sensor Networks

Wireless sensor network shows a great of natural advantages in long time monitoring where people can’t reach generally. With the application developments of large-scale monitoring (such as real-time monitoring for animals in large-scale wild or underwater), the large-scale WSNs for the3D space emerge at the same time. Compared with the traditional small-scale networks, the number of nodes in large-scale networks increases, and the actual distance between nodes are very hard to measure. Also the increment of network deployment dimension from2to3brings up a great challenge for the localization, routing and coverage in accuracy. How to realize the accurate localization and routing with the connectivity information between nodes in irregular3D networks is the main problem in our WSN study. The simple and efficient localization, routing and coverage algorithms in WSN tend to assume that the shape of network is regular and without hole. However this requirement in large-scale WSN is hard to meet. In order to deal with the routing, localization in the complex large scale WSN in which the simple adaption can’t meet all the cases, this paper proposes a new method ACDC (Approximate Convex Decomposition based on Connectivity) to decompose the whole network into some subnetworks with regular shape and no holes. Convex decomposition is dividing the complex irregular network into a plurality of subnetworks with simple shapes or no concave network boundary (approximate spherical or ellipsoidal subnetworks). The efficient localization routing and coverage algorithms can perform well in these subnetworks. It is of great significance for routing, localization, coverage, data collection and many other applications. The main steps of the algorithm ACDC and specific research work are below.1) Concave node identification based on connectivity information between nodes. We define concavity to indentify the concave node resulting in the valley and holes in the entire3D boundary nodes.2) ACDC based on concave node clustering. With clustering algorithm DBSCAN, the cluster heads which derive the network segmentation plane are found in each cluster.3) The establishment of subnetworks. We find the ideal segmentation plane which can partition the network into parts and not increase concavity of the two subnetworks associated with the plane.Compared with previous work:(1) it really realizes the convex decomposition for complex3D WSNs with holes essentially;(2) our segmentation algorithm does not require too much sensor’s locations and only uses network connectivity information;(3) just aiming at the topology of the3D field, an optimal result meeting requirements is provided after the balance between network concavity and the number of subnetworks. Extensive simulations show that ACDC works well in the presence of holes and shape variation, always yielding appropriate segmentation results.