Near Optimal Charging and Scheduling Scheme for Stochastic Event Capture with Rechargeable Sensors
Authors:
- Haipeng DaiHDHaipeng Dai
- Lintong JiangLJLintong Jiang
- Xiaobing WuXWXiaobing Wu
- David K.Y. YauDYDavid K.Y. Yau
- Guihai ChenGCGuihai Chen
- Shaojie TangSTShaojie Tang
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 42 (21556806) , 10-18
Abstract
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 sub modular 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.Keywords
This publication has 23 references indexed in Scilit:
- Dynamic Activation Policies for Event Capture with Rechargeable Sensors2012
- Morello: A quality-of-monitoring oriented sensing scheduling protocol in Sensor Networks2012
- J-RoC: A Joint Routing and Charging scheme to prolong sensor network lifetime2011
- On Optimal Scheduling in Wireless Rechargeable Sensor Networks for Stochastic Event Capture2011
- On renewable sensor networks with wireless energy transfer2011
- Multicast video delivery with switched beamforming antennas in indoor wireless networks2011
- Quality of monitoring of stochastic events by periodic and proportional-share scheduling of sensor coverageACM Transactions on Sensor Networks, 2010
- Recognizing daily activities with RFID-based sensors2009
- Energy-efficient capture of stochastic events by global- and local-periodic network coverage2009
- On Multidimensional Packing ProblemsSIAM Journal on Computing, 2004