Research On Topology Compression In Wireless Sensor Networks

Topology compression is an important issue in wireless sensor networks(WSNs).Topology provides necessary infrastructures for many basic network operations, e.g. data gathering, in-network processing and communication. Topology compression techniques focus on extracting specific structures from network topology, which can be further utilized to improve efficiency of various protocols. Most existing studies on topology issues depend on rigorous network assumptions, e.g. accurate location information of nodes,uniformly and densely deployed networks, etc. Such assumptions significantly limit the applicability of those methods.Recently, location-free methods are proposed to relax the limitations of locationbased methods and receive great attentions. When location information is missing, uncertain or only partially available, we have to exploit connectivity information and face with great challenges to construct high-quality topological structures that can maximally preserving the geometrical features of global network topology. Aiming at relaxing the limitations of existing work and providing better applicability and robustness, this dissertation systematically investigates several important topology compression issues, and manages to extract network structures with high geometrical fidelity. The main contents and contributions of this thesis are as follows.First, location-free skeleton extraction problem is investigated, which is crucial and critical for many fundamental network functions. Most existing algorithms either depend on rigorous assumptions, or cannot guarantee to extract deterministic skeleton that exactly preserve the geometrical shape of the network field. We relax the limitations of previous methods, and propose a robust skeleton extraction algorithm by exploiting only local connectivity. Our algorithm is built upon several novel techniques, including an efficient graph theoretical tool called HPT, a method to construct skeleton bands, a MDSbased boundary recognition algorithm, and a flexible mechanism to detect leaf skeleton nodes. We conduct extensive simulations and verify that our algorithm is able to extract well-connected skeleton from networks with various shapes, and is robust to some critical network parameters.Second, we further investigate the abnormal topological features caused by wormhole attack that is a severe threat to WSNs. Most existing wormhole countermeasures heavily depend on special hardware devices or ideal network assumptions, which significantly limit their applicability. Recently, some connectivity-based solutions are proposed.These solutions either capture local wormhole symptoms directly in discrete domain, or analyze global wormhole features in continuous domain. In this thesis, we exploit the essential topological changes caused by wormholes, and make the first successful attempt to propose a wormhole detection algorithm that is able to capture global wormhole symptoms directly in discrete domain. This design, called Worm Planar, novelly leverages network planarization mechanism, and is able to accurately identify wormholes under various network conditions, including multiple wormholes that cannot be handled by previous connectivity-based methods.Third, route path tracing is a crucial issue that is of great benefit to fine-grained network diagnosis and management. However, it is difficult, if not impossible, to integrate into each packet with its full path information in large-scale resource-constrained WSNs. All previous work fails to fully record the path information of every packet. To our best knowledge, this thesis is the first work that formally proposes and systematically investigates route path tracing problem in WSNs. We propose a lightweight path tracing scheme, called Path Zip, which shifts major cost from sensor nodes to sink by leveraging a novel hash-based path compression and reconstruction mechanism. Furthermore,topology-aware and geometry-assistant techniques are adopted to exploit different network knowledge and to reduce the complexity of proposed algorithm. Path Zip is able to record the full packet path in real time, and outperforms the state-of-the-art methods by inducing less computation and storage overhead.Finally, we investigate greedy geographic routing under uncertain locations. Greedy geographic routing is widely studied due to its simplicity. However, greedy geographic routing alone cannot guarantee delivery of messages due to suffering the local minimum problem. A number of effective solutions have been proposed to address this issue under specific network assumptions. In this thesis, we combine advantages of solutions in various categories, and present an efficient routing scheme, called FLYER, which is based on a macroscopic variant of geographic greedy routing and a planarization of the macroscopic landmark graph. FLYER does not depend on exact node locations or global state information, and is able to guarantee the delivery of messages when an upper bound on the location error is available. FLYER outperforms previous methods by providing higher success rate of greedy forwarding, shorter path length and better load-balancing property.In summary, this thesis proposes solutions to several important topology compression issues. Theoretical analysis and extensive simulations demonstrate the great applicability and performance of proposed algorithms. Thus, the design of this thesis is of great theoretical significance, hopefully advances the development of location-free topology compression methods, and can be potentially applied to practical WSNs and internet of things.