Fair energy-efficient sensing task allocation in participatory sensing with smartphones
Fair energy-efficient sensing task allocation in participatory sensing with smartphones
复制标题
DOI：
10.1093/comjnl/bxx015
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Jia Peng;Yanmin Zhu;Qingwen Zhao;Hongzi Zhu;Jian Cao;Guangtao Xue;Bo Li
中科院分区：
文献类型：
--
作者：
Jia Peng;Yanmin Zhu;Qingwen Zhao;Hongzi Zhu;Jian Cao;Guangtao Xue;Bo Li
随着智能手机的普及，使用智能手机的参与式传感为收集大量传感数据提供了前所未有的机会。在参与式感知中有两个关键的要求，公平的任务分配和能源效率，这是特别具有挑战性的高组合复杂性，能源效率和公平性之间的权衡，以及动态和不可预测的任务到达。在本文中，我们提出了一种新的公平的能源有效的分配框架，其目标的特点是最小最大的总感知时间。我们严格证明，优化的最小-最大总感测时间是NP困难的，即使任务被假定为先验的。我们考虑两种分配模型：离线分配和在线分配。对于离线分配模型，我们设计了一个有效的近似算法，近似比为2 - 1/m，其中m是系统中的成员智能手机的数量。对于在线分配模型，我们提出了一个贪婪的在线算法，实现了最多m的竞争比。结果表明，近似算法减少了81%以上的总感知时间，贪婪在线算法减少了73%以上的总感知时间，两种算法的最小-最大公平性都提高了3倍以上。
With the proliferation of smartphones, participatory sensing using smartphones provides unprecedented opportunities for collecting enormous sensing data. There are two crucial requirements in participatory sensing, fair task allocation and energy efficiency, which are particularly challenging given high combinatorial complexity, tradeoff between energy efficiency and fairness, and dynamic and unpredictable task arrivals. In this paper, we present a novel fair energy-efficient allocation framework whose objective is characterized by min-max aggregate sensing time. We rigorously prove that optimizing the min-max aggregate sensing time is NP hard even when the tasks are assumed as a priori. We consider two allocation models: offline allocation and online allocation. For the offline allocation model, we design an efficient approximation algorithm with the approximation ratio of 2 - 1/m, where m is the number of member smartphones in the system. For the online allocation model, we propose a greedy online algorithm which achieves a competitive ratio of at most m. The results demonstrate that the approximation algorithm reduces over 81% total sensing time, the greedy online algorithm reduces more than 73% total sensing time, and both algorithms achieve over 3x better min-max fairness.