Topological Feature Extraction And Its Applications In Wireless Sensor Networks

Topology features extraction is a hot topic in wireless sensor networks; full usage ofnetwork topology features can benefit the designing network protocol with highperformance, improve network quality of service, and prolong network life time. Skeletonis the key technique of topology feature extraction in wireless sensor networks, and itplays an important role in the applications such as network routing, localization,segmentation and navigation, etc. Besides, most existing protocols explicitly or implicitlyrequire that the network be deployed in a regularly shaped field, otherwise there will be adegraded performance. As such, network decomposition is also an important topic inwireless sensor networks.The main work of this thesis focuses on the skeleton extraction and networkdecomposition. The thesis studies the skeleton extraction under different assumption aboutthe boundary information, such as the complete boundaries, incomplete boundaries andunknown boundaries; in addition, connectivity-based network decomposition and itsapplication in localization is also studied. More specifically, the main contributions are asfollows:First, for complete boundaries, the definition of boundary node’s curvature in sensornetwork is proposed. By identifying corner nodes on the boundaries, the networkboundaries are decomposed into a set of boundary branches, based on which the skeletonnodes are identified. An algorithm is proposed to connect these skeleton nodes toconstruct skeleton arcs, followed by building a meaningful skeleton. The boundary noisecan be controlled by setting threshold values for corner node, and multi-resolutionskeleton can be extracted accordingly. Extensively simulations show that the proposedalgorithm has low complexity and is robust to boundary noise.Second, when only incomplete boundaries are given, the distance transform of sensornetwork is built, based on which a new definition for skeleton is proposed, and adistributed algorithm for skeleton node identification is presented. To connect skeletonnodes into a meaningful representation of the network, an index is constructed to identifyconnecting nodes such that, on one hand, these nodes can connect the identified skeletonnodes and guarantee that the skeleton has the same connectivity as the original network,on the other hand, these connecting nodes are medially placed, and therefore are a goodapproximation of the real skeleton. Simulation results show that the proposed algorithm isof low complexity, distributed and scalable, and robust to boundary noise and boundaryincompleteness. At the same time, compared to the existing solutions with complete boundaries, the proposed algorithm can achieve comparable and even better results,disregard of its usage of only incomplete boundaries.Third, the relationship between a skeleton node and its number of neighboring nodesis studied, and a neighborhood-size based skeleton node identification algorithm ispresented. The impact of the parameters used for skeleton node identification is analyzed;two by-products, namely network boundaries and network decomposition, are obtainedduring the process of skeleton extraction. Extensive simulation results show that withoutany boundary information, the proposed algorithm can extract accurate skeleton for allkinds of complex networks; and it is robust to such factors as network density, networkcommunication model, and network node distribution, etc.Finally, another definition for curvature is presented, which can be used forconvex/concave node identification. The concept of approximate convex decomposition isgiven, and the correlation between network localization error and network concavity isanalyzed. The distributed algorithm of segment line construction and networkdecomposition is designed; and an improved multi-dimensional scaling based localizationalgorithm is also proposed. Simulation results show that approximate convexdecomposition based localization algorithm can achieve high localization accuracy for anyirregularly shaped network.