Disruption Tolerant And Energy Saving Routing Algorithms For Wireless Sensor Networks

Wireless sensor networks (WSNs) are prone to partitioning due to limited energy in sensor nodes and unreliable radio communications between them. Message ferrying (MF) schema has been proposed as an effective means to deliver data between separated parts of a partitioned WSN.This dissertation proposes a tree-based routing algorithm for connected networks, in which minimum-weight trees of each partition of the WSN are evaluated with different alternate root nodes. Appropriate choice of the weights allows overall energy consumption or delay to be minimized. Two kinds of tree-construeting algorithms respectively named Least Energy Tree (LET) and Minimum Hop Tree (MHT) based on the Dijkstra algorithm are presented and evaluated by deriving an energy model. And, Minimum Spanning Tree (MST) based on Prim algorithm at a single root node is considered. For comparison, The Learning-based Power Efficient Routing (LPER) algorithm is emphatically proposed. In the LPER, a fitness function, which balances network lifetime, energy consumption, and packet delay, is constructed and used in an ant colony system to establish the optimal route. In addition, reinforcement learning is applied in predicting the energy consumption of neighboring nodes. The LPER is able to optimize network lifetime of WSNs, while keeping energy consumption and packet delay in a relative low level. Numeric experiments show the LPER outperforms the MST and LET based routing algorithms in terms of network lifetime and packet delay, although energy consumption of LET is superior to one of LPER.An end-to-end route for data delivery from the source to the sink may not be reconstructed if the network is partitioned. In this situation, MF routing is a good choice to deliver data between network partitions. MF is a proactive routing scheme for disconnected networks, in which ferries move proactively into one network partition to collect messages and deliver them to other partitions when the network becomes partitioned. At first, this dissertation provides two kinds of cluster head selection. Three different selections are included in the first selection based on tree and OLT selection is based on the dominating set rule, which also determines each node's route path. How to get the distance-optimal ferry route is a Traveling Salesman Problem (TSP). In light of the combinatorial nature of the problem, genetic algorithms (GAs) are viable alternatives. Simulation experiments show that OLT outperforms MHT, MST, and LET when the energy consumption of the ferry is small or negligible. However, LET probably outperforms the other three methods when the energy consumption of the ferry is in the high level.