Energy efficient multiple base stations deployment in wireless sensor networks

Wireless sensor network (WSN) is widely used in various applications rangingfrom area monitoring, health care monitoring, bush _re detection, to environmental monitoring, agricultural and structural monitoring. In WSNs, sensor nodes,typically battery powered, communicate with each other using radio signals andsend the sensed data to a designated base station. In some applications of WSN,several thousands of sensor nodes might be deployed over the monitored regionspanning several kilometres. Hence, it is very difficult to replace the batteries ofthe sensor nodes which are deployed over a large, remote and hostile area. Asa result, it is important to save the energy of each sensor node to increase thelifetime of a WSN. In a WSN, each sensor node spends most of its energy onrelaying the data of other sensor nodes. Multiple base stations can be deployedto reduce the amount of data, a sensor node needs to relay, thus increase the net-work lifetime. Furthermore, multiple base stations can also reduce the latencyof a packet delivery.This thesis studies multiple base stations deployment problems in WSNs,and presents a set of efficient techniques. Firstly, we present a quadratic-timealgorithm to optimally place a base station in a WSN so that the total energyconsumption of all the sensor nodes is minimized. Given a cluster of sensor nodem, the time complexity of the algorithm is O(m2). We also propose a heuristicalgorithm to evenly distribute energy consumptions of all the clusters of a WSN.Secondly, we propose a 2-approximation algorithm for minimizing the shortesthop distance from all the sensor nodes to the designated base stations in orderto deploy k base stations in a WSN. For a single base station, we present anoptimal algorithm for finding the optimal location of the base station. We alsopropose a modified version of our previous heuristics for balancing clusters ofsensors and show the simulation results of 2-approximation algorithm and theheuristics on 171 instances of different distributions. The simulation results showthat the cluster balancing heuristics performs significantly better than the 2-approximation algorithm.Lastly, we present two polynomial time heuristics for multiple base stationdeployment problems. In case of a single base station, we propose the firstpolynomial time algorithm for optimally placing a static base station in a clusterof sensor node to maximize the cluster's lifetime, and a heuristic for deploying amobile base station in a cluster of sensor node to increase the cluster's lifetime