计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2014年
11期
2374-2381
,共8页
杜扬%黄河%孙玉娥%李凡长%朱艳琴%黄刘生
杜颺%黃河%孫玉娥%李凡長%硃豔琴%黃劉生
두양%황하%손옥아%리범장%주염금%황류생
移动感知%任务分配%近似算法%多项式时间近似方案%划分
移動感知%任務分配%近似算法%多項式時間近似方案%劃分
이동감지%임무분배%근사산법%다항식시간근사방안%화분
mobile phone sensing%task assignment%approximation algorithm%PTAS%shifting
随着智能手机应用的普及,移动感知技术已被认为是一种高效且成本低廉的环境数据收集方式.移动感知系统中地理位置相关的最优任务分配问题是一个NP难问题.为了解决该问题,提出了一种多项式时间的近似最优的任务分配算法.该算法首先引入了单位圆盘模型中移动划分的思想,将整个监测地理空间划分为若干个子区间,并使得子区间内的最优分配方案的集合是划分前最优解的1/1+ε,这表明所设计的近似算法是一个多项式时间近似机制.随后,证明了最优任务分配问题在每个子区间内是多项式时间可解的,并设计了枚举算法求出该问题的最优解.最后,仿真实验结果表明所设计的近似最优任务分配算法的实际性能与理论分析相吻合.
隨著智能手機應用的普及,移動感知技術已被認為是一種高效且成本低廉的環境數據收集方式.移動感知繫統中地理位置相關的最優任務分配問題是一箇NP難問題.為瞭解決該問題,提齣瞭一種多項式時間的近似最優的任務分配算法.該算法首先引入瞭單位圓盤模型中移動劃分的思想,將整箇鑑測地理空間劃分為若榦箇子區間,併使得子區間內的最優分配方案的集閤是劃分前最優解的1/1+ε,這錶明所設計的近似算法是一箇多項式時間近似機製.隨後,證明瞭最優任務分配問題在每箇子區間內是多項式時間可解的,併設計瞭枚舉算法求齣該問題的最優解.最後,倣真實驗結果錶明所設計的近似最優任務分配算法的實際性能與理論分析相吻閤.
수착지능수궤응용적보급,이동감지기술이피인위시일충고효차성본저렴적배경수거수집방식.이동감지계통중지리위치상관적최우임무분배문제시일개NP난문제.위료해결해문제,제출료일충다항식시간적근사최우적임무분배산법.해산법수선인입료단위원반모형중이동화분적사상,장정개감측지리공간화분위약간개자구간,병사득자구간내적최우분배방안적집합시화분전최우해적1/1+ε,저표명소설계적근사산법시일개다항식시간근사궤제.수후,증명료최우임무분배문제재매개자구간내시다항식시간가해적,병설계료매거산법구출해문제적최우해.최후,방진실험결과표명소설계적근사최우임무분배산법적실제성능여이론분석상문합.
