Doctor of Philosophy
School of Electrical, Computer and Telecommunications Engineering
Yang, Changlin, Coverage problems in energy harvesting wireless sensor networks, Doctor of Philosophy thesis, School of Electrical, Computer and Telecommunications Engineering, University of Wollongong, 2015. http://ro.uow.edu.au/theses/4434
A Wireless Sensor Network (WSN), in general, contains many low-cost sensor nodes, each with the capability to monitor its surrounding environment. As conventional or non-rechargeable WSNs are restricted by the nite battery capacity of sensor nodes, researchers have sought the help of renewable energy techniques such as solar and wind. Consequently, each sensor node, in the resulting energy harvesting WSN, is able to harvest energy and recharge its battery from its environment. Assuming no other failures, WSNs are now able to operate perpectually if all nodes have energy neutral operation; i.e., they harvest more energy than what they spend.
A fundamental problem in energy harvesting WSNs is to maximize coverage, whereby the goal is to capture events of interest that occur in one or more target areas. In this respect, duty cycling for complete targets coverage is important. Its objective is to ensure all targets are monitored continuously by at least one sensor node, whilst other sensor nodes can be in a low power sleep state to conserve energy and to recharge their battery. To date, existing works only study the duty cycling for complete targets coverage problem in non-rechargeable WSNs where the sensor nodes have no ability to refresh their battery. Moreover, past works on energy harvesting WSNs focus on maximizing event detection probability and do not require all targets to be monitored at all times.
To this end, this thesis rst addresses the duty cycling for complete targets coverage problem in energy harvesting WSNs. Specifically, it is the first to propose the Maximum Lifetime Coverage with Energy Harvesting node (MLCEH) problem. Its objective is to determine the activation schedule of sensor nodes such that network lifetime is maximal whilst ensuring all targets are monitored by at least one sensor node at all times. To address the MLCEH problem, this thesis proposes two novel solutions, called LP-MLCEH and Maximum Utility Algorithm (MUA). The first uses Linear Programming (LP), and the other relies on a greedy selection policy. Simulation results show that LP-MLCEH doubles the network lifetime obtained by a similar algorithm developed for finite battery WSNs. Moreover, MUA achieves 3/4 of the network lifetime achieved by LP-MLCEH at a fraction of LP-MLCEH's computation time.
This thesis also considers a scenario where the information from sensor nodes may be staled, meaning the sink does not have an accurate knowledge of the battery level at each sensor node. To cope with this uncertainty, this thesis proposes a two stage Stochastic Programming (SP) based Uncertain Maximum Lifetime Coverage solution, called SP-UMLC, which achieves 80% of the theoretically achievable network lifetime.
After that, this thesis outlines a distributed algorithm called Maximum Energy Protection (MEP) to allow a sensor node to turn itself on/o using two-hops information. It compares MEP with two distributed algorithms developed for finite battery WSNs. Results show that MEP increases network lifetime by at least 30% and yields lower coverage redundancy.
This thesis then considers connectivity in the context of the Maximum Lifetime Coverage and Connectivity with Energy Harvesting nodes (MLCCEH) problem. The objective is to ensure all activated sensor nodes have at least one path to forward data to the base station/sink. It proposes two solutions: LP-MLCCEH and Energy Conservation for MLCCEH(EC-MLCCEH). Simulation results show that EC-MLCCEH is able to quickly compute results that is within 80% of the network lifetime acquired by LP-MLCCEH.
A key gap in the current state-of-the-art pertaining to coverage using energy harvesting WSNs is that they assume sensor nodes are already deployed, and thus, they do not guarantee a feasible number of sensor nodes around each target to satisfy energy neutral operation. To this end, this thesis studies the nodes placement problem. It first proposes three approximation algorithms, i.e., Greedy Round Node Placement (GRNP), Target Protection Node Placement (TPNP) and Energy Efficient Node Placement (EENP), to determine the locations to place the minimal number of sensor nodes such that the resulting network has energy neutral operation. The proposed algorithms have an approximation ratio of L + 1, |Z| + 1 and ½|Z| + 3⁄2 , respectively. Here, L is the number of cells and |Z| is the number of targets. In addition, they have a run time complexity of O(L), O(L+γ |Z|+2|Z|2) and O((L + ⌈ Ec⁄Rmin⌉(|Z| + L)), respectively; The symbol γ and Ec are, respectively, the sensing range and energy consumption rate of sensor nodes, and Rmin is the minimum recharging rate of cells in the sensing field. Stimulation results show that EENP is close to optimal with less than 1% gap in terms of the required number of sensor nodes.
Lastly, this thesis studies the problem of determining the set of locations to place the minimal number of sensor nodes for both sensing and relaying. The key constraints include complete targets coverage, energy neutral operation and connectivity to a sink. The problem is formulated as a Mixed Integer Linear Programming (MILP). A challenging issue with the formulated MILP is that it requires all the combinations of locations to place sensor nodes, which is computationally intractable. Consequently, a greedy heuristic called GMILP is proposed to reduce the number of decision variables considered by the MILP. This thesis further proposes two heuristics, i.e., DirectSearch and GreedySearch. Simulation results show that DirectSearch needs to place 20% more sensor nodes than MILP. On the other hand, both GreedySearch and GMILP require 10% more sensor nodes as compared to MILP. Moreover, the running time of DirectSearch and GreedySearch is an order faster than GMILP and four orders faster than MILP.