Fault Diagnosis And Recovery In Wireless Sensor Networks

Wireless Sensor Networks (WSNs), which consist of a large amount of self-organizing sensor nodes, are considered as channels to connect physical worlds, in-formation worlds and human worlds. Since sensor nodes are error-prone and a large scale of failure nodes will cause the connectivity loss in WSNs, it is a core issue and major challenge to locate the faulty nodes and restore the connectivity to ensure the data collection and aggregation in a damaged network. Technically, fault diagnosis and connectivity restoration can offer solutions to the above problems such that the availability of data transmission in WSNs is guaranteed. On the other hand, the energy capacity of a sensor node that brings another challenge to both solutions mentioned above, which implies the energy conservation should be taken into ac-count in both solutions to prolong the lifetime of a WSN. In this thesis, several fault diagnosis and connectivity restoration strategies are proposed to satisfy the needs in different design purposes and the application demands under the constrain that the energy capacity of a sensor node is limited. The main achievements of research works in this thesis are summarized as follows:Firstly, in the field of fault diagnosis, a Fault Identification Code is adopted as an efficient way to detect and locate faulty nodes. Due to the good properties of the Resolving Set, an algorithm of fault identification code construction A-SRS based on the resolving set is proposed. And the upper bound of fault identification code generated by A-SRS is theoretical proved. Furthermore, the simulation anal-ysis indicates that the fault identification code generated by A-SRS requires less checking nodes and such code based faulty nodes localization can efficiently reduce communication for energy conservation. Since the Fault-tolerant Resolving Set can locate faulty nodes in the presence of some malfunctioned resoling nodes, a fault-tolerant resolving set based fault diagnosis and recovery algorithm FDRFIC is proposed. Both theoretical and simulation analyses indicate that FDRFIC is built with high diagnosis accuracy and low communication cost.Secondly, connectivity restoration provides availability of data transmission in WSNs. In this thesis, two restoration strategies are presented for two different application environments respectively. For the purpose of 1-connected network es-tablishment with least resources employed, a 3-Star and Center of Mass (CoM) based algorithm ORNP is designed. And the theoretical analysis proves that the approximation ratio of ORNP is 3. Furthermore, the simulation analysis indicates that the network repaired by ORNP has topology advantages in node degree and transmission latency with least relay nodes required. In addition, for the purpose of minimizing the terrain influences on connectivity restoration, a random terrain based restoration strategy HRSRT is devised to achieve the establishment of a 2- connected network under the constrain that the number of relay nodes and mo-bile data collectors is limited. The theoretical analysis proves that the approximation ratio of HRSRT is 1.5. And the simulation analysis indicates that HRSRT can greatly reduce the energy consumption during the connectivity restoration as well as the data collection and aggregation.