Research On Topology Recognition And Construction In Wireless Sensor Networks

Topology recognition and construction are important issues in wireless ad hoc and sensor networks. Effectively organized structures in network topology provide necessary infrastructures for many basic network operations, i.e. data gathering, in-network processing and communication etc. Most existing studies on topology issues assume the knowledge of accurate location information of nodes. Such assumptions substantially limit the applicability of those methods because acquiring accurate location measurement is practically difficult for large scale sensor networks. Location-free methods can greatly enhance the applicability of network systems when location information is missing or only partially available. Aiming at relaxing the limitations of existing work and increasing the robustness and efficiency of methods under location uncertainty, this dissertation systematically investigates several important issues involving location-free topology recognition and construction in sensor networks. In the part of topology recognition, we focus on inferring geometric and topological features from network connectivity. In the part of topology construction, we study to construct effective connectivity substructures for important applications including sensing coverage and link monitoring. The main contents and contributions of this dissertation are indicated below.First, network boundary recognition is crucial and critical for many fundamental network functionalities in sensor networks. Previous location-free designs, however, mostly detect boundaries in a coarse grain manner. Those coarse-grained methods are not able to correctly answer many important queries, i.e. the total number and location of boundaries in the network, etc. To address this issue, we propose the first fine-grained and distributed boundary recognition approach using merely connectivity information. We formally define the network boundaries in a topological manner and present the distributed algorithm that can discover meaningful cycles to accurately locate all the boundaries.Second, we further explore the abnormal topological features, i.e. the holes in the high dimension (genus) caused by wormhole attacks. Wormhole attack is a severe threat to wireless ad hoc and sensor networks. Most existing wormhole countermeasures either require specialized hardware devices or make strong assumptions on the network. Those requirements and assumptions limit the applicability of previous approaches. This work analyzes the fundamental impact of wormhole on network connectivity, and uses the topology methodology to capture the inevitable symptom of wormholes and locate wormholes. To our best knowledge, this work presents the first distributed wormhole detection approach, which does not requires special hardware devices or any rigorous assumptions on network properties and relies solely on network connectivity information.Third, based on the result of boundary recognition, we further study to schedule inside nodes in the network to construct effective structure and achieve sensing coverage. Coverage topology construction is a fundamental issue in wireless ad hoc and sensor networks. Most previous techniques for coverage problem often require accurate location information or range measurements. A few works can only use connectivity information, however, they are limited by centralized computation and fixed coverage granularity. We establish the graph theoretical framework for location-free coverage, and propose a novel coverage criterion and scheduling method based on cycle partition. Our method is able to schedule a sparse coverage set in a distributed manner, using purely connectivity information. Our design has a particular advantage, which permits us to configure or adjust the quality of coverage by adequately exploiting diverse sensing ranges and specific requirements of different applications. To our best knowledge, this work makes the first successful attempt towards establishing a connectivity-based and distributed coverage scheme with configurable coverage granularity.Finally, we study topology construction tailored for requirements of new applications. We focus on constructing a connectivity structure integrated with self-monitoring capability, which ensures that every communication link can be monitored by nodes in the network. We make the first formal study on the problem of self-monitoring topology optimization, show that finding an optimal self-monitoring topology is NP-complete even by modeling the network as a unit disk graph with geometric representation, and give the upper bound on the approximation ratio in various graph models. We present the monitoring-set bounded graph model and utilize the model to design a location-free algorithm that provides the polynomial-time approximation scheme (PTAS) for optimal self-monitoring topology problem. We further design two localized polynomial algorithms with provable approximation ratio and time complexity.