Research On Disjoint Multipath Fault-tolerant Routing Schemes Of Wireless Sensor Networks

Due to the poor deployment environment, limited energy, and unreliable wireless channel of sensor nodes, wireless sensor networks (WSN) often encounter some system failures, such as node failure and communication interrupt. These failures make the efficiency of data transmission is very low, and it is difficult to meet the application demands. The fault-tolerant technology of traditional networks did not consider the characteristics of WSN. So it is not suitable for practical usage scenarios of WSN. The fault tolerance of WSN is defined as the recovery of data transmission or the self-healing of network structure when some nodes or links fail. Current researches on fault-tolerant technology for WSN mainly focus on following five ways:fault tolerance in hardware, fault tolerance in deployment, fault tolerance in routing, fault tolerance in event and fault tolerance in application. The fault tolerance in routing is regarded as the basis and key priority of fault tolerance for WSN.Multipath fault-tolerant routing schemes are the primarily way to achieve the fault tolerance in routing. In WSN, multipath routing schemes have better performance in terms of reliability and load balance than traditional single-path routing schemes. But in multipath routing schemes, the multiple paths from the source node to the destination node may contain shared nodes (or shared links). The failures of shared nodes (or shared links) may lead to the interrupts of multiple paths. So the disjoint multipath routing schemes which do not cause shared nodes (or shared links) have gotten immense research interest due to its capability of providing high reliability and fault tolerance.The significant challenges which the disjoint multipath routing faces include three aspects. The first is the avoidance of shared nodes (or shared links), which means how the routing schemes build paths to achieve the disjoint constraints of multiple paths. The second is the optimization of the disjoint paths, which means how the routing schemes optimize the path finding to reach the target of saving energy and improving fault tolerance under the disjoint constraints. The third is the path breakage caused by mobile nodes, which means how to restore the disjoint paths when the network topology changes. Aiming at above challenges, based on the data redundancy method and the path redundancy method, we study the disjoint multipath fault-tolerant routing schemes for WSN in this thesis. The content of this thesis includes five issues:(1) Disjoint-constrained mode of the network;(2) Disjoint multipath routing schemes based on centralized calculating;(3) Disjoint multipath routing schemes distributed calculating;(4) Disjoint multipath routing schemes for mobile wireless sensor networks;(5) Disjoint multipath routing schemes for wireless sensor networks with load-balancing requirements.The contributions of this thesis include:1. Centralized calculating based2-disjoint multipath fault-tolerant routing algorithm. Considering certain industrial monitoring applications (for example, mine safety monitoring) which have relatively stable network topologies, based on the global information, the algorithm first calculates near to optimize2-node (link) disjoint paths from a source to the destination (sink) using the number of hops and the path quality as metrics, and generates a tiny routing table which is merely composed of the <master node, secondary node> couple and the path bit series. Then the tiny routing tables are disseminated to each sensor node along the generated paths. In order to improve the resilience of route maintenance, the algorithm designs a centralized adaptive path maintenance mechanism. In the data routing phase, packets are transmitted according to the path bit series carried in their heads, without any control overhead.2. Multi-routing tree topology structure for disjoint multiple paths. We proposed a multi-routing tree topology structure which has a number of node-joint but link-disjoint subtrees. The subtrees of multi-routing tree meet the following constraints:(1) they are node-joint, which means the nodes of a subtree may also belong to the others;(2) They are link-disjoint, which means the edges of a subtree must only belong to itself;(3) The edges that connect a node to its child nodes must only belong to the same subtree. Depending on the nature of multi-routing tree, paths along different subtrees are node-disjoint.3. Disjoint multipath fault-tolerant routing algorithm based on multi-routing tree. Based on the multi-routing tree, we design two algorithms to construct the multi-routing tree in the network. One is centralized algorithm and another is distributed algorithm. For the two algorithms, we also present a customized redundancy scheme to improve the reliability of data transmission. The scheme provides individualized data redundancy for each sensor node.4. Node-disjoint multipath fault-tolerant routing algorithm for MWSN based on HSV color space. Based on the HSV color space model, the algorithm creates a numeric (h, s, v) tuple for each link in the network and distributes these tuples into six basic planes in the color space, then it can find multiple node-disjoint paths within different basic color planes. It designs disjoint multipath routing maintenance mechanism based on variable intervals for mobile nodes link Received Signal Strength Indicator (RSSI) value detection, which is without any geographic location information.5. Node-disjoint multipath fault-tolerant routing algorithm for MWSN based on area partition. In the algorithm, we first partition the deployed area of the network into a number of non-overlapping meta-area chains, and then find a path from the source node to the destination node in each chain separately. We also introduce a dynamic next hop selection method which has two modes:distance-first mode and direction-first mode.6. Load-balanced and link-disjoint multipath fault-tolerant routing algorithm based on the path deputies. According to the principle "one neighbor one deputy service, different neighbors different deputy services", we present a link-disjoint multipath routing scheme based on the path deputies. Depending on the path-deputy scheme, the paths from a source node to the sink node are link-disjoint, and the total cost of all the link-disjoint paths from a node is very small. Then we develop a load balancing model to distribute the traffic over the multiple paths. The load balancing model can effectively prolong the network lifetime.