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

被引:37
作者
Dai, Haipeng [1 ]
Jiang, Lintong [1 ]
Wu, Xiaobing [1 ]
Yau, David K. Y. [2 ]
Chen, Guihai [1 ,3 ]
Tang, ShaoJie [4 ]
机构
[1] Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210023, Jiangsu, Peoples R China
[2] Purdue Univ, Dept Comp Sci, W Lafayette, IN USA
[3] Shanghai Jiao Tong Univ, Dept Comp Sci & Engn, Shanghai 200240, Peoples R China
[4] Temple Univ, Dept Informat & Comp Sci, Philadelphia, PA USA
来源
2013 IEEE 10TH INTERNATIONAL CONFERENCE ON MOBILE AD-HOC AND SENSOR SYSTEMS (MASS 2013) | 2013年
关键词
QUALITY;
D O I
10.1109/MASS.2013.60
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
080201 [机械制造及其自动化];
摘要
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.
引用
收藏
页码:10 / 18
页数:9
相关论文
共 32 条
[1]
[Anonymous], 2008, P 7 ACM WORKSH HOT T
[2]
[Anonymous], WCNC
[3]
[Anonymous], 2005, P IPSN 2005 4 INT S
[4]
[Anonymous], 2003, COMBINATORIAL OPTIMI
[5]
[Anonymous], [No title captured]
[6]
Buettner M., 2009, Ubicomp
[7]
On multidimensional packing problems [J].
Chekuri, C ;
Khanna, S .
SIAM JOURNAL ON COMPUTING, 2004, 33 (04) :837-851
[8]
Chulsung Park, 2006, 2006 3rd Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (IEEE Cat. No. 06EX1523), P168
[9]
Dai H., 2013, ICCCN
[10]
SURESENSE: SUSTAINABLE WIRELESS RECHARGEABLE SENSOR NETWORKS FOR THE SMART GRID [J].
Erol-Kantarci, Melike ;
Mouftah, Hussein T. .
IEEE WIRELESS COMMUNICATIONS, 2012, 19 (03) :30-36