本文選題：移動感知 + 任務分配　； 參考：《計算機研究與發(fā)展》2014年11期

【摘要】：隨著智能手機應用的普及,移動感知技術已被認為是一種高效且成本低廉的環(huán)境數(shù)據(jù)收集方式.移動感知系統(tǒng)中地理位置相關的最優(yōu)任務分配問題是一個NP難問題.為了解決該問題,提出了一種多項式時間的近似最優(yōu)的任務分配算法.該算法首先引入了單位圓盤模型中移動劃分的思想,將整個監(jiān)測地理空間劃分為若干個子區(qū)間,并使得子區(qū)間內(nèi)的最優(yōu)分配方案的集合是劃分前最優(yōu)解的1/1+ε,這表明所設計的近似算法是一個多項式時間近似機制.隨后,證明了最優(yōu)任務分配問題在每個子區(qū)間內(nèi)是多項式時間可解的,并設計了枚舉算法求出該問題的最優(yōu)解.最后,仿真實驗結果表明所設計的近似最優(yōu)任務分配算法的實際性能與理論分析相吻合.
[Abstract]:With the popularity of smart phone applications, mobile sensing technology has been considered as an efficient and low-cost way to collect environmental data. The problem of geographic location-dependent optimal task assignment in mobile sensing systems is a NP-hard problem. In order to solve this problem, an approximate optimal task allocation algorithm with polynomial time is proposed. The algorithm firstly introduces the idea of moving partition in the unit disk model, and divides the whole monitoring geographic space into several sub-regions. The set of optimal allocation scheme in subinterval is 1 / 1 蔚 of the optimal solution before partition, which shows that the proposed approximation algorithm is a polynomial time approximation mechanism. Then, it is proved that the optimal task assignment problem is polynomial time solvable in each subinterval, and an enumeration algorithm is designed to find the optimal solution of the problem. Finally, the simulation results show that the performance of the proposed approximate optimal task assignment algorithm is in agreement with the theoretical analysis.
【作者單位】： 蘇州大學計算機科學與技術學院;蘇州大學城市軌道交通學院;中國科學技術大學計算機科學與技術學院;中國科學技術大學蘇州研究院;
【基金】：國家“九七三”重點基礎研究發(fā)展計劃基金項目(2011CB302905) 國家自然科學基金項目(61202028,61303206) 教育部高等學校博士學科點專項科研基金項目(20123201120010) 廣東省普及型高性能計算機重點實驗室開放課題(SZU-GDPHPCL-2012-01)
【分類號】：TN929.53

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前2條

1 安健;桂小林;張文東;蔣精華;張進;;物聯(lián)網(wǎng)移動感知中的社會關系認知模型[J];計算機學報;2012年06期

2 武建佳;趙偉;;WInternet:從物網(wǎng)到物聯(lián)網(wǎng)[J];計算機研究與發(fā)展;2013年06期

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 王明曉;;基于Android的物聯(lián)網(wǎng)移動感知服務平臺[J];電腦知識與技術;2013年04期

2 田偉;于嵐;殷淑娥;;物聯(lián)網(wǎng)技術在移動購物領域的應用[J];電子商務;2013年05期

3 夏開建;任曉剛;吳s，

本文編號：1878940