Modeling and Optimization of Rechargeable Sensor Networks
MetadataShow full item record
Over the past fifteen years, advances in Micro-Electro-Mechanical Systems (MEMS) technology have enabled rapid development of wireless sensor networks (WSNs). A WSN consists of a large number of sensor nodes that are typically powered by batteries. Each sensor node collects useful information from its environment, and forwards this data to a base station through wireless communications. Applications of WSNs include environmental monitoring, industrial monitoring, agriculture, smart home monitoring, military surveillance, to name a few. Due to battery constraint at each sensor node, a fundamental challenge for a WSN is its limited operational lifetime -- the amount of time that the network can remain operational before some or all of the sensor nodes run out of battery. To conserve energy and prolong the lifetime of a WSN, there have been active research efforts across all network layers. Although these efforts help conserve energy usage and prolong network lifetime to some extent, energy and lifetime remain fundamental bottlenecks and are the key factors that hinder the wide-scale deployment of WSNs. This dissertation addresses the energy problem of a WSN by exploiting a recent breakthrough in wireless energy transfer (WET) technology. This breakthrough WET technology is based on the so-called magnetic resonant coupling (MRC), which allows electric energy to be transferred from a source coil to a receive coil without any plugs or wires. The advantages of MRC are high energy transfer efficiency even under omni-direction, not requiring line-of-sight (LOS), and being robust against environmental conditions. Inspired by this enabling WET technology, this dissertation focuses on applying MRC to a WSN and on studying how to optimally use this technology to address lifetime problem for a WSN. The goal is to fundamentally remove lifetime bottleneck for a WSN. The main contributions of this dissertation are summarized as follows: 1. Single-node Charging for a Sparse WSN. We first investigate how MRC can be applied to a WSN so as to remove the lifetime performance bottleneck in a WSN, i.e., allowing a WSN to remain operational forever. We consider the scenario of a mobile wireless charging vehicle (WCV) periodically traveling inside the sensor network and charging each sensor node's battery wirelessly. We introduce the concept of renewable energy cycle and offer both necessary and sufficient conditions for a sensor node to maintain its renewable energy cycle. We study an optimization problem, with the objective of maximizing the ratio of the WCV's vacation time over the cycle time. For this problem, we prove that the optimal traveling path for the WCV is the shortest Hamiltonian cycle and uncover a number of important properties. Subsequently, we develop a near-optimal solution by a piecewise linear approximation technique and prove its performance guarantee. This first study shows that network lifetime bottleneck can be fundamentally resolved by WET. 2. Multi-node Charging for a Dense WSN. We next exploit recent advances in MRC that allows multiple sensor nodes to be charged at the same time, and show how MRC with multi-node charging capability can address the scalability problem associated with the single-node charging technology. We consider a WCV that periodically travels inside a WSN and can charge multiple sensor nodes simultaneously. Based on the charging range of the WCV, we propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. We pursue a formal optimization framework by jointly optimizing the traveling path of the WCV, flow routing among the sensor nodes, and the charging time with each hexagonal cell. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy. Through numerical results, we demonstrate that our solution can indeed address the scalability problem for WET in a dense WSN. 3. Bundling Mobile Base Station and Wireless Energy Transfer: The Pre-planned Path Case. Our aforementioned work is based on the assumption that the location of base station is fixed and known in the WSN. On the other hand, it has been recognized that a mobile base station (MBS) can offer significant advantages over a fixed one. But employing two separate vehicles, one for WET and one for MBS, could be expensive and hard to manage. So a natural question to ask is: can we bundle WET and MBS on the same vehicle? This is the focus of this study. Here, our goal is to minimize energy consumption of the entire system while ensuring that none of the sensor nodes runs out of energy. To simplify the problem, we assume that the path for the vehicle is given a priori. We develop a mathematical model for this problem. Instead of studying the general problem formulation (called CoP-t), which is time-dependent, we show that it is sufficient to study a special subproblem (called CoP-s), which only involves space-dependent variables. Subsequently, we develop a provable near-optimal solution to CoP-s with the development of several novel techniques including discretizing a continuous path into a finite number of segments and representing each segment with worst-case energy bounds. 4. Bundling Mobile Base Station and Wireless Energy Transfer: The Unconstrained Path Case. Based on our experience for the pre-planned path case, we further study the problem where the traveling path of the WCV (also carrying the MBS) can be unconstrained. That is, we study an optimization problem that jointly optimizes the traveling path, stopping points, charging schedule, and flow routing. For this problem, we propose a two-step solution. First, we study an idealized problem that assumes zero traveling time, and develop a provably near-optimal solution to this idealized problem. In the second step, we show how to develop a practical solution with non-zero traveling time and quantify the performance gap between this solution and the unknown optimal solution to the original problem. This dissertation offers the first systematic investigation on how WET (in particular, the MRC technology) can be exploited to address lifetime bottleneck of a WSN. It lays the foundation of exploring WET for WSNs and other energy-constrained wireless networks. On the mathematical side, we have developed or applied a number of powerful techniques such as piecewise linear approximation, RLT, time-space transformation, discretization, and logical point representation that may be applicable to address a broad class of optimization problems in wireless networks. We expect that this dissertation will open up new research directions on many interesting networking problems that can take advantage of the WET technology.
- Doctoral Dissertations