Abstract
Wireless sensor network (WSN) is widely used in various applications ranging
from 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 and
send the sensed data to a designated base station. In some applications of WSN,
several thousands of sensor nodes might be deployed over the monitored region
spanning several kilometres. Hence, it is very difficult to replace the batteries of
the sensor nodes which are deployed over a large, remote and hostile area. As
a result, it is important to save the energy of each sensor node to increase the
lifetime of a WSN. In a WSN, each sensor node spends most of its energy on
relaying the data of other sensor nodes. Multiple base stations can be deployed
to 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 latency
of 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-time
algorithm to optimally place a base station in a WSN so that the total energy
consumption of all the sensor nodes is minimized. Given a cluster of sensor node
m, the time complexity of the algorithm is O(m2). We also propose a heuristic
algorithm to evenly distribute energy consumptions of all the clusters of a WSN.
Secondly, we propose a 2-approximation algorithm for minimizing the shortest
hop distance from all the sensor nodes to the designated base stations in order
to deploy k base stations in a WSN. For a single base station, we present an
optimal algorithm for finding the optimal location of the base station. We also
propose a modified version of our previous heuristics for balancing clusters of
sensors and show the simulation results of 2-approximation algorithm and the
heuristics on 171 instances of different distributions. The simulation results show
that the cluster balancing heuristics performs significantly better than the 2-
approximation algorithm.
Lastly, we present two polynomial time heuristics for multiple base station
deployment problems. In case of a single base station, we propose the first
polynomial time algorithm for optimally placing a static base station in a cluster
of sensor node to maximize the cluster's lifetime, and a heuristic for deploying a
mobile base station in a cluster of sensor node to increase the cluster's lifetime.