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

【摘要】：隨著智能手機(jī)應(yīng)用的普及,移動(dòng)感知技術(shù)已被認(rèn)為是一種高效且成本低廉的環(huán)境數(shù)據(jù)收集方式.移動(dòng)感知系統(tǒng)中地理位置相關(guān)的最優(yōu)任務(wù)分配問題是一個(gè)NP難問題.為了解決該問題,提出了一種多項(xiàng)式時(shí)間的近似最優(yōu)的任務(wù)分配算法.該算法首先引入了單位圓盤模型中移動(dòng)劃分的思想,將整個(gè)監(jiān)測(cè)地理空間劃分為若干個(gè)子區(qū)間,并使得子區(qū)間內(nèi)的最優(yōu)分配方案的集合是劃分前最優(yōu)解的1/1+ε,這表明所設(shè)計(jì)的近似算法是一個(gè)多項(xiàng)式時(shí)間近似機(jī)制.隨后,證明了最優(yōu)任務(wù)分配問題在每個(gè)子區(qū)間內(nèi)是多項(xiàng)式時(shí)間可解的,并設(shè)計(jì)了枚舉算法求出該問題的最優(yōu)解.最后,仿真實(shí)驗(yàn)結(jié)果表明所設(shè)計(jì)的近似最優(yōu)任務(wù)分配算法的實(shí)際性能與理論分析相吻合.
[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.
【作者單位】： 蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;蘇州大學(xué)城市軌道交通學(xué)院;中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;中國科學(xué)技術(shù)大學(xué)蘇州研究院;
【基金】：國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2011CB302905) 國家自然科學(xué)基金項(xiàng)目(61202028,61303206) 教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目(20123201120010) 廣東省普及型高性能計(jì)算機(jī)重點(diǎn)實(shí)驗(yàn)室開放課題(SZU-GDPHPCL-2012-01)
【分類號(hào)】：TN929.53

【參考文獻(xiàn)】

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

1 安健;桂小林;張文東;蔣精華;張進(jìn);;物聯(lián)網(wǎng)移動(dòng)感知中的社會(huì)關(guān)系認(rèn)知模型[J];計(jì)算機(jī)學(xué)報(bào);2012年06期

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

【共引文獻(xiàn)】

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

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

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

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

本文編號(hào)：1878940