Graph Based Algorithms For Topology Control In Wireless Sensor Network

In recent years, graph algorithms have emerged as a powerful technique for topology control and as a solution to various problems related to wireless sensor networks. The goal of this thesis is to apply graph algorithms to satisfy topology control constraints in wireless sensor networks.This thesis provides a technical and theoretical technique which greatly reduces overheads and time complexity of topology control algorithm with respect to other aspects required in WSNs. Our result could be also useful for developing other topology control algorithms in3-dimensions and mobile WSNs. Previously such algorithms explicitly constructed topology control with more emphasis on energy consumption without pay any attention to time complexity which is a critical factor for small devices with limited computing capabilities.We present a Simple Fault-Tolerant Local Topology Control (SFL) algorithm, for reliable wireless multi-hop networks, that is an improvement over the LTRT algorithm, which gives a trade-off between different topology control design factors related to wireless sensor networks.Our algorithm encompasses all the constraints, such as:distributed algorithm, local information, location information, k-Connectivity, coverage, small node degree, link bi-directionality, simplicity, low message complexity, energy-efficiency, spanner, convergence time, and memory consumption.In SFL, each node builds its local SFL independently by applying LMST k times to achieve k-edge connectivity and to optimize its transmission power by maintaining network connectivity in a localized manner. We discuss several smoothness terms that we can be employed. Experimental results show that SFL has better performance than LTRT in term of low message complexity.The last chapter of the thesis addresses the issue of the efficiency in network design for k-vertex connectivity problem. We compare the running times of several standard min-cut/max-flow algorithms. We also benchmark these algorithms on a standard number of typical graphs. In most cases pseudo-flow algorithm works several tir...