Topology Control And Connection Restoration Of Wireless Ad Hoc Networks In Harsh Environment

With the rapid development of electronic technology, ad hoc networks have been widely used in our daily life and work, especially in the harsh environment where the network infrastructure is unavailable, such as mine monitoring, environment monitoring, battlefield reconnaissance, underwater monitoring, coastal and border protection, target tracking, and so on. Delay/Disruption Tolerant Networks (DTNs), Intermittently Connected Ad Hoc Networks and Opportunistic Networks are the examples of this kind of network. Howerer, due to node mobility, limited resource, vulnerability in harsh environment, the network connections intermittently exist and vary along the time, and the network may get splitted into several isolated partitions. Topology control that can make data transmission efficiently and connectivity restoration that can reconnect the separated partitions are fundamental to the fuctional operation of such kind of network.This dissertation mainly focuses on topology control and connectivity restoration of wireless ad hoc networks in harsh environments. A mesh topology is constructed for data routing and a tree topology is constructed for data collecting. For the seriously damaged networks a connection restoration method through deploying the least number of additional nodes to connect disjoint patitions is proposed. The major contributions are summarized as follows:(1) A topology control method based on probability is proposed to construct a mesh topology for data routing. It can balance the energy consuming and connectivity quality for the predictable delay/disruption tolerant networks. The connection probability between each pair of node is maximized or above a given threshold with the minimum energy cost. The predictable delay tolerant networks are modeled as a three dimensional space time weighted directed graph which includes spatial, temporal and connection probability information. The topology control problem is formulated as finding a sub graph from the three dimensional space time weighted directed graph that satisfies the following conditions: the connection probability between each pair of noeds is maximized or above a given threshold and the energy cost is minimum. This problem is proved to be NP-complete, and two heuristic algorithms are proposed to solve the problem. The performance such as average connection probability, ratio of energy cost and ratio of edges are compared with the existing methods under different link density and connection probability threshold. The results show that the proposed methods can balance the connection probability and energy cost.(2) A tree based topology control method is proposed to balance the time delay and energy cost in data collection. The goal is to find the spanning tree that satisfy the time delay threshold with minimum energy cost, which ensure all nodes in the networks can transmit data to the sink node. The predictable delay tolerant networks are modeled as a three dimensional space time weighted directed graph, and further simplified as a reduced aggregated directed graph. Topology control problem is defined as a tree construction problem, which is finding the spanning tree(ST) of three dimensional space time weighted directed graph/reduced aggregated directed graph model, such that1)include all nodes of the network;2)the total energy cost of the ST is minimized; and3)satisfy the performance requirement such as the time delay. Time dealy can be obtained through calculating the total number of time edges in the deepest path of the final ST. This problem is also NP-complete, and three heuristic algorithms are proposed. The experiment is done on random dataset and real dataset respectively. Ratio of energy cost and time delay are compared under different link density and time delay threshold. The results demonstrate that the proposed algorithms can reduce the network energy consumption significantly, while satisfying the time delay constraint.(3) A quadrilateral steiner tree based connectivity restoration method is proposed for massively damaged network. In the harsh environment, wireless sensor networks may suffer from a significant damage that causes many nodes/links to fail simultaneously and the network to get splitted into multiple disjoint partitions. Therefore, linking the separated partitions by placing the least number of relay nodes to re-establish a strongly connected network topology is necessary to maintain the functional network operations. However, the problem of finding the minimum relay nodes is NP-hard and hence heuristics methods are preferred. First, the disjointed partitions are detected and their locations are determined. Then the appropriate quadrilaterals are selected to connect the separated partitions and the Steiner nodes of these quadrilaterals are found. The disjoint islands which are not connected by these selected quadrilaterals are connected with the triangle Steiner tree or minimum spanning tree method. Finally, relay nodes are placed to the appropriate position according to the edges of Steiner tree to restore network connectivity. It is compared with the other algorithms in terms of the number of the realy nodes and the average node degree. Extensive simulation experiments demonstrate the beneficial aspects of the resulting topology with respect to number of relaying nodes, degree of connectivity and fault resilience.