隨著智能移動(dòng)設(shè)備的廣泛使用,一種新的眾包形式-空間眾包應(yīng)運(yùn)而生。空間眾包要求工作者到達(dá)指定任務(wù)位置才能執(zhí)行任務(wù)。本文提出了一種新的空間眾包形式,稱為時(shí)間連續(xù)型空間眾包。時(shí)間連續(xù)型空間眾包與以往空間眾包的不同在于,時(shí)間連續(xù)型空間眾包任務(wù)需要長(zhǎng)時(shí)間的任務(wù)周期才能完成任務(wù)。時(shí)間連續(xù)型空間眾包在實(shí)際生活中存在廣泛應(yīng)用,包括環(huán)境監(jiān)測(cè)、交通檢測(cè)等。由于任務(wù)預(yù)算和可分配工作者數(shù)量有限,時(shí)間連續(xù)型空間眾包任務(wù)無法在任務(wù)周期內(nèi)被全部執(zhí)行,使得所獲得的結(jié)果數(shù)據(jù)往往不完整,出現(xiàn)數(shù)據(jù)缺失的問題。為了解決數(shù)據(jù)缺失問題,本文采用插值技術(shù)對(duì)缺失值進(jìn)行估計(jì),但同樣會(huì)影響數(shù)據(jù)的準(zhǔn)確性。因此對(duì)于時(shí)間連續(xù)型空間眾包任務(wù)來說,任務(wù)質(zhì)量是非常重要的衡量指標(biāo)�；诖�,本文提出一種基于熵的任務(wù)質(zhì)量函數(shù)。在此基礎(chǔ)上,本文分別研究了單任務(wù)場(chǎng)景和多任務(wù)場(chǎng)景下的時(shí)間連續(xù)型空間眾包任務(wù)分配問題,具體研究?jī)?nèi)容如下:（1）本文提出時(shí)間連續(xù)型空間眾包模式及相關(guān)定義,提出時(shí)間連續(xù)型空間眾包任務(wù)質(zhì)量函數(shù),并研究以任務(wù)質(zhì)量為優(yōu)化目標(biāo)的任務(wù)分配算法。（2）在單任務(wù)分配場(chǎng)景下,本文提出最大化單任務(wù)質(zhì)量問題,并分析該問題的時(shí)間復(fù)雜度。接著,本文證明最大化單任... 

【文章來源】：中國(guó)科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

【文章頁(yè)數(shù)】：74 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖２．１任務(wù)分配狀態(tài)圖??

?第２章基礎(chǔ)理論???ｆ（２）?ｉ（３）?ｔ（４）?ｉ＊（５）?ｔ（６）??ｒ⑴?ｒ（２＞?ｒ（３）?ｉ＜４）?ｆ（ｓ）?ｔ（６）?ｗｘ?１?０?０?＼?＼?＼??麵，２?０?！?！?０?＼?＼??＼／?Ｉ?Ｉ??１?Ｘ／?■?■?ｗ３?０?０?＼?＼?１?０??Ｗ２?ｗ２?ｗ３?ｗ４?＇?＇??Ｗ４?ｏ?ｏ?＼?＼?＼?１??（ａ）任務(wù)分配圖?（ｂ）矩陣ｊｃ??圖２．１任務(wù)分配狀態(tài)圖??者到任務(wù)位置的距離成正比。任務(wù)成本可以表示ｃ（ｔｒ）?＝?２＾＝１??如果將旅行成本看作任務(wù)成本［２８］［２９］，那么為了減少執(zhí)行子任務(wù)的成本，通??常選擇將子任務(wù)分配給距離任務(wù)位置最近的工作者（本文采取該方式）。如果最??近工作者因?yàn)槟承┰驘o法分配，那么則將子任務(wù)分配給次近鄰（比如在多任務(wù)??分配場(chǎng)景下，可能會(huì)出現(xiàn)兩個(gè)任務(wù)中某一相等時(shí)間片的最近鄰相同，詳細(xì)情況可??參照４．１節(jié)）。??２．２任務(wù)質(zhì)量函數(shù)??（ａ）埋想狀態(tài)下的任務(wù)分配??Ｉ?＿?＿?Ｉ?＿如丨??（叫實(shí)際＿盾：；兄下的任務(wù)分配??圖２．２任務(wù)分配圖??理想情況下，時(shí)間連續(xù)型空間眾包的所有子任務(wù)都可以分配給工作者完成。??如圖２．２?（ａ）所示，本文用斜線來表示被分配的子任務(wù)。但實(shí)際情況下，由于任務(wù)??預(yù)算和可分配的工作者有限，使得時(shí)間連續(xù)型空間眾包任務(wù)不能被全部分配，導(dǎo)??致時(shí)間連續(xù)型空間眾包任務(wù)獲得的數(shù)據(jù)出現(xiàn)缺失問題，如圖２．２?（ｂ）所示。為了??解決數(shù)據(jù)缺失問題，可以采用插值方法對(duì)數(shù)據(jù)進(jìn)行填充。因此，對(duì)于時(shí)間連續(xù)型??空間眾包任務(wù)中的每一個(gè)子任務(wù)，有兩種完成狀態(tài)，“被分配”和“被插值”�！氨�??分配”子任務(wù)指子任務(wù)由工作者完成，本

擴(kuò)展性。??理想情況下，每個(gè)任務(wù)可以在不同的處理器核心上獨(dú)立運(yùn)行近似算法完成??任務(wù)分配。當(dāng)總?cè)蝿?wù)數(shù)量ｍ大于處理器核心數(shù)時(shí)，完成總?cè)蝿?wù)中的一個(gè)任務(wù)分??配所需要的時(shí)間開銷為完成單任務(wù)所需時(shí)間開銷的土倍。但是，在婦??配過程中本文發(fā)現(xiàn)，如果運(yùn)行在不同處理器核心上的兩個(gè)任務(wù)在某個(gè)時(shí)間段時(shí)??“競(jìng)爭(zhēng)”同一個(gè)工作者，那么不同任務(wù)之間就會(huì)出現(xiàn)相關(guān)性。這種情況發(fā)生的原??因在于，為了減少任務(wù)成本，兩個(gè)任務(wù)中的子任務(wù)在同一時(shí)間片選擇的成本最低??的工作者相同。本文將上述情況稱為任務(wù)分配沖突，如圖４．１?（ａ）所示，圖中共有??三個(gè)任務(wù)（Ｕｈｑ），以及兩個(gè)工作者（１４＾，？；２）。任務(wù)Ｔ２和任務(wù)Ｔ３之間存在任務(wù)??分配沖突，因?yàn)樗鼈儞碛邢嗤某杀咀畹偷墓ぷ髡撸眨??Ｗ２?？?ｚ－－－￣??〇ｔ．?ｙｔｉ＾ＮＮ?：－ｐＷｌ?：?〇?；ｖ??Ｔｚ?ｌ．ＮＮ?６ｂｕｎｄ乂??（ａ）?（ｂ）?（ｃ）??、、??／＾ＮＮｂｏｕｎｄ?謂ｂ一、、??／?＼?Ｘｉ?．．?＇’？、、＇?－…?＞??（讀ｆ樣ｙ??、、，＇、ｄ彳：，?上＾一：氣－彳??１￣ＮＮ?ｂｏｕｎｄ、＇、?＾?２￣ＮＮ?ｂｏｕｎｄ——’??（ｄ）?一?（ｅ）??圖４．１獨(dú)立任務(wù)組級(jí)并行化框架下的任務(wù)分配沖突問題說明（考慮以工作者與任務(wù)位置之??間的旅行距離作為任務(wù)成本）??由于任務(wù)間可能會(huì)出現(xiàn)任務(wù)分配沖突，任務(wù)并不能完全獨(dú)立地在不同處理??器上運(yùn)行分配算法。本文考慮對(duì)任務(wù)集進(jìn)行分組，使得各任務(wù)組之間不存在任務(wù)??分配沖突，以便于各任務(wù)組可以獨(dú)立地在不同處理器上完成任務(wù)分配。??４．１．３獨(dú)立任務(wù)組級(jí)并行化算法??為了更好地

【參考文獻(xiàn)】：
期刊論文
[1]空間眾包中在線路徑規(guī)劃算法[J]. 崔俊云,陳迪,袁野,馬玉亮,王國(guó)仁.  清華大學(xué)學(xué)報(bào)(自然科學(xué)版). 2020(08)
[2]空間眾包中的位置隱私保護(hù)技術(shù)綜述[J]. 安瑩,秦科,羅光春.  計(jì)算機(jī)應(yīng)用研究. 2018(08)
[3]基于眾包模式的地理信息采集開發(fā)與應(yīng)用研究[J]. 周源,鄭燦輝,劉禹鑫.  測(cè)繪與空間地理信息. 2016(12)
[4]空間眾包環(huán)境下的3類對(duì)象在線任務(wù)分配[J]. 宋天舒,童詠昕,王立斌,許可.  軟件學(xué)報(bào). 2017(03)



本文編號(hào)：3467160