Research On Schedulability Of Charging Programming In Wireless Rechargeable Sensor Networks

Wireless Sensor Network (WSN) is one of the most important techniques for information acquisition in the 21th century. It constitutes the platform of a broad range of applications related to national security, surveillance, military, health care, and environmental monitoring. Due to size and cost limits of sensor nodes, energy problem becomes a first and foremost problem faced by many applications of WSNs. The energy hole phenomenon, which roots in data transmis-sion mode of WSNs, even exacerbates the issue. A promising solution is to deploy a charging system in a WSN, which is known as the Wireless Rechargeable Sensor Network (WRSN). The charging system in a WRSN includes one or several Mobile Chargers(MCs) with high volume batteries, as well as a service Station (S) where MCs can renew their batteries. The MCs can autonomously move to the sensor nodes to wirelessly replenish the nodes’ depleted energy. The charging behavior is hence highly controllable, highly predictable, and very effi-cient. Theoretically speaking, a WRSN can work perpetually under a well-designed charging programming. Therefore, charging programming in WRSNs has been gaining tremendous atten-tion from the research community in recent years. Moreover, the solutions can also be applied in other resource-constrained applications, such as service distribution, logistics transportation, etc.This dissertation is the first to exploit the schedulability decision problem of charging pro-grammings in WRSNs. Based on the proposed decision conditions, this dissertation develops the charging programmings in single-MC WRSNs and in multiple-MCs WRSNs. The target is to minimize the overall charging cost while ensuring that no sensor node will die. The main contributions of the dissertation is summarized as follows.(1) The dissertation proposes the schedulability decision problem in charging program-mings, and develops a sufficient condition and a necessary condition to address the problem. Schedulability of a charging programming decides whether a valid charging scheme exists in the deployed WRSN. A valid charging scheme can instruct the MCs to recharge the sensor nodes so that they will work continuously during a target lifetime. Therefore, deciding the schedulability of a charging programming goes before designing any charging scheme. Given a charging pro-gramming, if it satisfies the sufficient condition, it is schedulable, and a valid charging scheme can be efficiently constructed; if it dissatisfies the necessary condition, it is unschedulable, and no charging scheme can accomplish the charging mission. Deciding these two conditions re-quires very little information from the WRSN, and costs low computation complexity.(2) For WRSNs with single MC, the dissertation proposes the generalized formulation of valid charging schemes in a charging programming. By setting a proper objective in a particular WRSN, the formulation is transferred into an optimization form, which can be used to find the optimal charging scheme in the WRSN. Although the formulation is too complex to be solved, it can be reduced to a Periodic Greedy Charging (PGC) scheme. The PGC scheme can be constructed in linear time if the sufficient decision condition in the charging programming is satisfied.(3) For WRSNs with single MC, when the energy consumption is extremely imbalanced among the sensor nodes, the dissertation proposes a Charge-on-Demand (CoD) scheme, as well as a deploying method of the S. The CoD scheme works in rounds. In each round, it charges the sensor nodes under a certain threshold. By assigning proper values of the threshold and each round period, the CoD scheme not only can guarantee the liveness of all the sensor nodes, but also can significantly reduce the total moving distance of the MC. Numerical results show that, compared with a periodic charging scheme, the CoD scheme reduces 50% of the total moving distance. Since the charging frequencies of different sensor nodes vary greatly, the proposed deploying method deploys the S to the hot spot of energy consumption in the WRSN. In this way, the total moving distance of the MC can be further reduced by 20% according to the numerical results. Note that the CoD scheme is reduced to the PGC scheme when applied in WRSNs with balanced energy consumption.(4) For large-scale WRSNs with multiple MCs, the dissertation proposes a Tour-based Greedy Charging (TGC) scheme. The TGC scheme divides the minimum mobile chargers prob-lem into two tightly coupled sub-problems, which are NP-hard, and addresses them sequentially. First, based on a decision condition, the TGC constructs a set of schedulable tours, starting from and ending in the S, to cover the whole WRSN. Subsequently, it heuristically assigns the tours to minimum number of MCs, and designs the charging scheme of each MC as well. Numerical results show that, on average, the number of MCs obtained by the TGC scheme is less than 1.1 over a derived lower bound, and is only 0.2～0.4 over related work. Note that the TGC scheme is reduced to the PGC scheme when applied in WRSNs that can be charged by one MC within one tour.(5) The dissertation proposes a design pattern to cope with all kinds of information from WRSNs for quick design of charging programmings. To achieve this goal, related works on WRSNs are categorized and reviewed in 6 key dimensions. In each dimension, different schemes are analyzed and compared, so as to explore the pattern of designing charging pro-grammings in different WRSNs. The design pattern is applied in three real-deployed WSNs for validation.