参与式感知系统中面象节能的公平感知任务分配方法研究-计算机技术专业论文.docxVIP

万方数据 万方数据 Submitted in total ful?lment of the requirements for the degree of Master in Computer Technology Fair Energy-e?cent Sensing Task Allocation in Participatory Sensing with Smartphones Q?????? Z??? Supervisor Prof. Y????? Z?? S????? ?? C??????? S?????? ??? E?????????? S??????? J??? T??? U????????? S???????, P.R.C???? Jan. 15th, 2015 上海交通大学硕士学位论文 摘要 参与式感知系统中面象节能的公平感知任务分配方 法研究 摘 要 随着智能手机的广泛使用，参与式感知系统给大量数据收集提供了前所未 有的机会。利用智能手机的感知功能，系统可以收集到大量感知数据，从而给 用户提供有用的信息。在这样的参与式感知中，有两个重要的需求：公平的任 务分配和智能手机的高能效。同时满足这两个需求具有很大的挑战性。首先， 任务和手机的公平匹配带来的高计算复杂度；其次，高能效与公平性之间权 衡；最后，任务到来的不可预测性。如何获得公平性和高能效之间的平衡是一 个重要的问题。本课题着重研究参与式感任知系统中感知任务的分配问题。 m本课题提出一种新颖的公平的感知任务分配框架，优化目标是最小化最 大融合感知时间。通过严谨的理论证明，我们发现最小化最大融合感知时间 是 NP 难问题，即使假设任务事先都知道。本课题考虑两种任务分配模型：一 种是离线模型，就是任务是事先给定的；另一种是在线模型，任务动态到达系 统，系统并不知道未到达任务的信息。在离线模型里，我们设计了一种高效 的近似算法，近似比为 2 ? 1 , 其中 m 表示系统中成员智能手机的个数。在在 线模型中，我们提出两种有效的在线分配算法：贪心算法和 Robin-Hood 算法， 获得的竞争比最大分别为 m 和 √m + 1. 仿真结果显示我们的算法在 min-max fairness 方面或者总的能耗节省方面均比对比算法好很多。 m 关键词： 感知任务分配方法, 参与式感知, min-max Fairness — i — 上海交通大学硕士学位论文 ABSTRACT Fair Energy-e?cent Sensing Task Allocation in Participatory Sensing with Smartphones ABSTRACT 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 e?- ciency, which are particularly challenging given high combinatorial complexity, trade- o? between energy e?ciency and fairness, and dynamic and unpredictable task arrival- mIn this paper, we present a novel fair energy-e?cient 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: o?ine allocation and on- line allocation. For the o?ine allocation model, we design an e?cient approximation algorithm with the approximation ra