Near Optimal Charging and Scheduling Scheme for Stochastic Event Capture with Rechargeable Sensors

Though much existing work exploits wireless power charging to enhance sensor network performance such as routing and data aggregation, few efforts focus on issues of stochastic event capture. In this paper, we consider the scenario in which a mobile charger (MC) periodically travels within a sensor network to recharge the sensors wirelessly, to maximize the Quality of Monitoring (QoM) for stochastic events. Towards this goal, two closely related research issues need to be addressed. One is how to choose the sensors for charging and decide the charging time for each of them; the other is how to best schedule the sensors' activation schedules according to their received energy. In this paper, we jointly design the charging scheme and sensor schedules to maximize the QoM. We formulate our problem formally as the maximum QoM charging and scheduling problem (MQCSP). Obtaining an exact solution of MQCSP is challenging. Thus we first ignore the MC's travel time and study the resulting relaxed version of MQCSP, R-MQCSP. We show both MQCSP and R-MQCSP are NP-hard. For R-MQCSP, however, under a special condition, we prove that it can be formulated as a submodular function maximization problem. This formulation allows a 1/6-approximation algorithm for the general case, and a unified algorithm with a series of approximation factors (up to 1-1/e) for a special case. Then, for MQCSP, we propose approximation algorithms by extending our R-MQCSP results. Finally, we conduct extensive trace-driven simulations to validate our algorithm design. The empirical results corroborate our theoretical analysis.