移動(dòng)群智感知多任務(wù)參與者優(yōu)選方法研究

牛宏英，劉文菊，王 賾，孫士民

(天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300000)E-mail:2550633673@qq.com

1 引 言

物聯(lián)網(wǎng)技術(shù)的出現(xiàn)，使得物理世界與虛擬信息世界有機(jī)結(jié)合.它成為物理世界、虛擬信息世界連接的紐帶，其中感知網(wǎng)絡(luò)成為物聯(lián)網(wǎng)的核心.而群智感知是一種利用可移動(dòng)電子終端產(chǎn)品來收集數(shù)據(jù)、可以取締傳統(tǒng)的利用專業(yè)傳感器收集數(shù)據(jù)的一種新興模式.也就是說，群智感知的便利之處在于其收集數(shù)據(jù)之前無需刻意的安裝固定的傳感器網(wǎng)絡(luò)模塊，這樣便可以大大的減少了平臺(tái)為收集數(shù)據(jù)所花費(fèi)的資源成本.這里把基本感知節(jié)點(diǎn)設(shè)置為擁有移動(dòng)終端設(shè)備的目標(biāo)人群，而感知單元即為設(shè)備中所配置的各種傳感器，目標(biāo)人群便可將自己的設(shè)備置于附近的環(huán)境中進(jìn)行數(shù)據(jù)的收集與上傳.在這樣的環(huán)境中，不僅數(shù)據(jù)收集者可以通過收集數(shù)據(jù)謀取所需，還可以幫助公眾收集數(shù)據(jù)、分析數(shù)據(jù)、共享信息，實(shí)現(xiàn)互惠互利.群智感知網(wǎng)絡(luò)利用普通用戶現(xiàn)有的感知設(shè)備和已有的通訊網(wǎng)絡(luò)來構(gòu)建一種新興的網(wǎng)絡(luò).這種利用以人為中心利用移動(dòng)終端來收集數(shù)據(jù)的方式與參與者感知[2]、城市感知[3,4]、移動(dòng)感知[5,6]以及眾包[8]等與群智感知側(cè)重點(diǎn)不太相同的系統(tǒng)的概念非常相似.

群智感知系統(tǒng)的目的是收集有效的高質(zhì)量數(shù)據(jù)[1].現(xiàn)有的移動(dòng)群智感知平臺(tái)如Medusa[7]，主要用于任務(wù)發(fā)布和數(shù)據(jù)收集，可以發(fā)布不同的任務(wù)與不同數(shù)據(jù)收集的處理.由平臺(tái)中的參與者根據(jù)不同回報(bào)以及任務(wù)困難度[13，14]等自己決定完成某些任務(wù).沒有考慮到優(yōu)化目標(biāo)(比如最小化用戶信息的情況下最小化移動(dòng)距離).參與者選擇是群智感知一個(gè)重要的研究問題之一[10,11]，文獻(xiàn)[9]中提出利用參與者已知的地理位置，使目標(biāo)人群均勻分布在整個(gè)感知區(qū)域中，以達(dá)到數(shù)據(jù)收集更加完整的效果.文獻(xiàn)[12]提出了基于社區(qū)的任務(wù)分發(fā)算法，將用戶劃分為不同的社區(qū).文獻(xiàn)[15]提出用岡珀茨函數(shù)來更新參與者的信譽(yù)度，以此實(shí)現(xiàn)衡量參與者參與感知任務(wù)的意愿和提供的數(shù)據(jù)質(zhì)量.文獻(xiàn)[21]提出一種多任務(wù)參與者選擇方法，假設(shè)參與者信息不相同的情況下提供相同的數(shù)據(jù)質(zhì)量，考慮被選擇參與者提供數(shù)據(jù)的總質(zhì)量以及分布情況.文獻(xiàn)[23]部署了一個(gè)名叫‘CSP’的平臺(tái)，通過WiFi熱點(diǎn)的指紋結(jié)合其他信息推斷出參與者所在位置，進(jìn)而分配對(duì)應(yīng)位置的任務(wù).由于參與者的設(shè)備不同、移動(dòng)速度以及隱形位置等的限制，導(dǎo)致其收集到的數(shù)據(jù)質(zhì)量大不相同.所以平臺(tái)需要在預(yù)算限制下進(jìn)行參與者的選擇，并激勵(lì)參與者收集到高質(zhì)量數(shù)據(jù)是一個(gè)重要的研究問題.

文獻(xiàn)[20]提出一種基于組的參與者選擇方法.任務(wù)分配分為在線場(chǎng)景和離線場(chǎng)景兩種.離線場(chǎng)景下參與者選擇是以物理空間位置為依據(jù)，文獻(xiàn)[17]提出使組織者能夠根據(jù)地理和時(shí)間的可用性，以及確定適合收集數(shù)據(jù)的參與者.文獻(xiàn)[18,19]提出人群的活動(dòng)行為在空間領(lǐng)域是有規(guī)律的，這一理論為預(yù)測(cè)參與者的運(yùn)動(dòng)軌跡提供了根據(jù).文獻(xiàn)[16]提出在多任務(wù)參與者優(yōu)選的背景下實(shí)現(xiàn)參與者人數(shù)以及參與者移動(dòng)距離的最小化研究方法，但是沒有考慮到參與者速度對(duì)算法的影響.文獻(xiàn)[21]提出了一種基于優(yōu)選速度和方向的用戶移動(dòng)模型.這使得使用者的動(dòng)作具有目的性和隨機(jī)性.針對(duì)參與者選擇問題，本文提出了VT-MOST一個(gè)以任務(wù)為中心的參與者選擇和VPT-MOST一個(gè)以參與者為中心的優(yōu)選方法.不同于T-MOST和PT-MOST中假設(shè)各參與者速度相同(70m/min)，這里VT-MOST和VPT-MOST使用以往參與者的速度平均值作為參考值.一方面，對(duì)于平臺(tái)而言，最小化參與者信息管理的同時(shí)最小化平臺(tái)成本.另一方面，對(duì)于系統(tǒng)選中的參與者而言，可以實(shí)現(xiàn)參與者獎(jiǎng)勵(lì)的最大化.在此基礎(chǔ)上，采用數(shù)據(jù)集對(duì)四種算法進(jìn)行實(shí)驗(yàn)，對(duì)比并分析了四種算法所選擇出的參與者人數(shù)、平均每個(gè)人完成的任務(wù)數(shù)、完成任務(wù)所移動(dòng)的距離以及參與者人數(shù)與移動(dòng)距離的乘積等實(shí)驗(yàn)結(jié)果的對(duì)比，根據(jù)不同的情況選擇出性能最好的算法.

2 參與者優(yōu)選模型

2.1 相關(guān)工作

群智感知激勵(lì)模型即通過鼓勵(lì)參與者使其積極的參與到數(shù)據(jù)收集的任務(wù)中來，以此確保服務(wù)器平臺(tái)可以收集到高數(shù)量、高質(zhì)量的數(shù)據(jù)，提高其系統(tǒng)的準(zhǔn)確性、可靠性.文獻(xiàn)[14]提出了邊界效用密度，當(dāng)參與者的邊界效用密度大于密度閾值，參與者將會(huì)被感知平臺(tái)選中.文獻(xiàn)[13]中，感知平臺(tái)利用參與者信譽(yù)度值選擇參與者，而參與者根據(jù)完成任務(wù)的難易程度、利潤(rùn)值決定執(zhí)行哪項(xiàng)任務(wù).上述方法都沒有考慮到平臺(tái)信息管理資源最大化.文獻(xiàn)[16]中，平臺(tái)通過比較參與者所完成的任務(wù)個(gè)數(shù)選擇參與者，既最小化用戶資源管理又最小化移動(dòng)距離.群智感知模型面向各式各樣的生活場(chǎng)景，針對(duì)不同的場(chǎng)景提供不一樣的激勵(lì)機(jī)制.文獻(xiàn)[16]提出的MultiTasker方法中，激勵(lì)機(jī)制包括兩部分：一部分是完成任務(wù)的獎(jiǎng)勵(lì)激勵(lì)，與其完成任務(wù)個(gè)數(shù)成正比；另一部分是動(dòng)態(tài)激勵(lì)，根據(jù)參與者移動(dòng)的總距離而動(dòng)態(tài)變化，與其成正比.

本文提出的VT-MOST、VPT-MOST算法中各用戶的速度不一樣，由此在一定時(shí)間限制內(nèi)所完成的任務(wù)個(gè)數(shù)也不一定，所以相對(duì)于T-MOST和PT-MOST，獎(jiǎng)勵(lì)激勵(lì)就會(huì)有所變化.速度大的用戶在一定時(shí)間限制內(nèi)(比如1小時(shí))完成的任務(wù)個(gè)數(shù)多，總距離也大，隨之獎(jiǎng)勵(lì)激勵(lì)、動(dòng)態(tài)激勵(lì)也會(huì)較大.

2.2 總體架構(gòu)

移動(dòng)群智感知系統(tǒng)由三部分構(gòu)成：任務(wù)發(fā)布、任務(wù)分配和數(shù)據(jù)收集.在云端的服務(wù)器接收到數(shù)據(jù)使用者的信息請(qǐng)求時(shí)發(fā)送感知任務(wù)給任務(wù)參與者，處理收集的感知任務(wù)并進(jìn)行其他的管理任務(wù).參與者接收到感知任務(wù)后，進(jìn)行所需數(shù)據(jù)的感知，然后將數(shù)據(jù)返回給服務(wù)器，服務(wù)器將數(shù)據(jù)處理后返回給數(shù)據(jù)使用者，通過整個(gè)流程實(shí)現(xiàn)數(shù)據(jù)感知、數(shù)據(jù)收集、信息服務(wù)等功能.任務(wù)分配與任務(wù)執(zhí)行需要考慮多種因素[22]，參與者針對(duì)不同任務(wù)的意愿程度以及收集數(shù)據(jù)對(duì)于參與者正?；顒?dòng)的影響都不盡相同，不同參與者由于硬件設(shè)備以及自身專業(yè)性導(dǎo)致收集數(shù)據(jù)的可靠性也不相同……等因素造成平臺(tái)收集數(shù)據(jù)的不可控性.在感知系統(tǒng)中，參與者時(shí)常利用空間隱形來模糊他們的位置，實(shí)現(xiàn)位置隱私保護(hù)，這種方法已廣泛應(yīng)用于基于位置的服務(wù)[23].文獻(xiàn)[23]設(shè)計(jì)了一種新的兩階段優(yōu)化方法，包括使用隱形位置進(jìn)行全局優(yōu)化，然后在不侵犯隱私的情況下使用參與者的精確位置進(jìn)行局部?jī)?yōu)化.這種使用隱形位置實(shí)現(xiàn)高傳感覆蓋率的方法，大大減小了平臺(tái)的支出.

在任務(wù)分配時(shí)，平臺(tái)通過獲取用戶與任務(wù)的位置，進(jìn)而根據(jù)算法設(shè)計(jì)選擇出合適的參與者，最后將任務(wù)分配給具體的參與者[16].在該感知系統(tǒng)中，參與者并不是主動(dòng)選擇任務(wù)而是被動(dòng)的執(zhí)行已分配的任務(wù)，按照既定路線來完成任務(wù).參與者接收到感知平臺(tái)的任務(wù)發(fā)布后使用自己的移動(dòng)設(shè)備完成數(shù)據(jù)的采集和上傳.由于平臺(tái)發(fā)布的任務(wù)是緊急任務(wù)，那么參與者就要在一定時(shí)間范圍內(nèi)完成選定的任務(wù)集合，這就要求參與者必須有意識(shí)的去訪問每一個(gè)任務(wù)點(diǎn).由于任務(wù)的性質(zhì)不同，可能需要參與者按照不同的形式去完成任務(wù)，同時(shí)平臺(tái)為了得到高質(zhì)量的數(shù)據(jù)，一個(gè)任務(wù)會(huì)進(jìn)行多人多個(gè)數(shù)據(jù)的采取.參與者完成任務(wù)集合后，進(jìn)行簡(jiǎn)單的計(jì)算與處理，最后統(tǒng)一將收集到的數(shù)據(jù)上傳給系統(tǒng).

3 算法設(shè)計(jì)

假設(shè)平臺(tái)有任務(wù)T={t1,t2,t3,…,tn}，為了保證收集的數(shù)據(jù)具有高效性與全面性，且考慮到實(shí)際情形，任務(wù)請(qǐng)求者要求的數(shù)據(jù)量不會(huì)不約而同的相等.所以這里假設(shè)任務(wù)請(qǐng)求者要求任務(wù)ti由si(si為3-8個(gè)不等)個(gè)人來完成.為了便于分析，假設(shè)參與者采集一個(gè)數(shù)據(jù)的時(shí)間為5分鐘.平臺(tái)中有m個(gè)候選參與者U={u1,u2,u3,…,um}，則要求從m個(gè)候選者中選擇若干個(gè)參與者在h小時(shí)內(nèi)完成所有任務(wù).n個(gè)任務(wù)的參與者集合表示為P={P1,P2,P3,…,Px}.x表示最終選擇出的參與者人數(shù).TUj={ti1,ti2,…}是指參與者uj完成的任務(wù)集合，UTi={ui1,ui2,ui3,…}指完成任務(wù)ti的參與者集合.完成這些任務(wù)所移動(dòng)的總距離為D(TUj).在約束條件式(1)、式(2)下實(shí)現(xiàn)目標(biāo)函數(shù)式(3)、式(4).

|UTi|=Si，i∈(1,n)

(1)

(2)

(3)

min|P|

(4)

3.1 VT-MOST

VT-MOST是一種以任務(wù)為中心的參與者選擇算法，由于參與者的移動(dòng)速度不同，選擇候選參與者的時(shí)候不再只是根據(jù)距離最短，而是在一定距離范圍內(nèi)的時(shí)間最短.將最小化參與者人數(shù)作為最主要的優(yōu)化目標(biāo)，同時(shí)適當(dāng)?shù)目紤]最小化參與者的移動(dòng)總距離.先選擇一個(gè)所需任務(wù)個(gè)數(shù)最多的任務(wù)作為初始任務(wù)，然后選擇離該任務(wù)最近的N(N>1)位參與者作為候選參與者去完成該任務(wù)，接下來選擇離初始任務(wù)最近的任務(wù)作為下一個(gè)任務(wù)(已選擇過的任務(wù)或者已被完成了的任務(wù)不再被選擇)……以此類推，直到得到候選參與者在指定時(shí)間內(nèi)完成的任務(wù)集合.按任務(wù)個(gè)數(shù)大小比較各候選參與者所得到的任務(wù)集合，選擇個(gè)數(shù)最大的那個(gè)參與者作為第一個(gè)參與者，在個(gè)數(shù)相同的情況下選擇移動(dòng)距離最小的那個(gè)候選參與者.已經(jīng)被選擇的參與者則需剔除掉，該參與者完成的任務(wù)集合相應(yīng)的減少其完成任務(wù)需要的人數(shù).以此類推，依次選出參與者完成的任務(wù)集合，直到所有任務(wù)都完成.

算法1.VT-MOST

輸入：用戶集合U，任務(wù)集合T

輸出：參與者集合P及其完成的任務(wù)集合TU

Begin

Step 1.選擇剩余任務(wù)中需要人數(shù)最多的任務(wù)作為初始任務(wù)，記為tik，選擇離任務(wù)tik的N-最近鄰候選者中一位用戶記為uij(j=

Step 2.選擇離任務(wù)tik最近的一個(gè)任務(wù)作為下一個(gè)任務(wù)記為ti(k+1)(k>=1).

Step 3.循環(huán)執(zhí)行Step 2直到參與者uij完成這些任務(wù)的時(shí)間大于h*60分鐘.

Step 4.輸出TUij=(ti1，ti2，…).

Step 5.循環(huán)執(zhí)行Step 1-Step 4，選擇出的每個(gè)候選者uij在h*60分鐘內(nèi)完成的任務(wù)集合TUij.

Step 6.選擇最大的TUij作為參與者uj完成的任務(wù)集合TUij.

Step 7.循環(huán)執(zhí)行Step 1-Step 7，確定參與者完成的任務(wù)集合.

Step 8.輸出參與者集合P={P1,P2,P3,…，Px}及其完成的任務(wù)集合TU={TU1,TU2,…,TUj}.

End

3.2 VPT-MOST

文獻(xiàn)[16]提出的PT-MOST算法是以參與者為中心的，由于算法運(yùn)算的時(shí)間復(fù)雜度過高.當(dāng)平臺(tái)中候選參與者較多時(shí)，運(yùn)算成本過高.本文提出的VPT-MOST采用文獻(xiàn)[13]提出的一種將感知區(qū)域劃分為一組子區(qū)域或者格子的方法.有效的降低了其運(yùn)算的時(shí)間復(fù)雜度.本文中由于參與者的移動(dòng)速度不同，在選擇候選參與者的時(shí)候不再比較每個(gè)候選者的任務(wù)集合，而是根據(jù)各個(gè)子區(qū)域，在每個(gè)子區(qū)域中存在一個(gè)速度值最大的候選者計(jì)算其任務(wù)集合.這樣通過比較候選者的任務(wù)集合確定參與者.

劃分子區(qū)域，選擇子區(qū)域中速度值最大的候選者，然后選擇距離已選候選者最近的任務(wù)作為初始任務(wù)，接下來選擇離初始任務(wù)最近的任務(wù)作為下一個(gè)任務(wù)(已選擇過的任務(wù)或者已被完成的任務(wù)不再被選擇)，……以此類推，直到得到候選參與者在一定時(shí)間內(nèi)完成的任務(wù)集合.按任務(wù)個(gè)數(shù)大小比較各個(gè)子區(qū)域中唯一的候選參與者所得到的任務(wù)集合，選擇完成任務(wù)個(gè)數(shù)最大的那個(gè)候選者作為第一個(gè)參與者，若任務(wù)個(gè)數(shù)相同時(shí)選擇移動(dòng)距離最小的那個(gè)候選參與者.根據(jù)已選參與者完成的任務(wù)集合，剔除該參與者且該參與者完成的任務(wù)集合相應(yīng)的減少其完成任務(wù)需要的人數(shù).以此類推，依次選出參與者完成的任務(wù)集合，直到所有任務(wù)都完成.

算法2.VPT-MOST

輸入：任務(wù)集合T，用戶集合U

輸出：參與者集合P及其完成的任務(wù)集合TU

Begin

Step 1.將整個(gè)感知區(qū)域劃分為一組子區(qū)域，標(biāo)記為tag(1-100)，確定各候選者所在子區(qū)域.確定各個(gè)子區(qū)域中速度值最大的那個(gè)候選者，記為uij.

Step 2.選擇距離各個(gè)候選者最近的那個(gè)任務(wù)作為初始任務(wù)，記為tik.

Step 3.選擇離任務(wù)tik最近的一個(gè)任務(wù)作為下一個(gè)任務(wù)，記為ti(k+1)(k>=1).

Step 4.直到候選參與者uij完成這些任務(wù)的時(shí)間大于h*60分鐘.

Step 5.輸出TUij=(ti1，ti2，…).

Step 6.循環(huán)執(zhí)行步驟1-5，選擇出每個(gè)候選者uij在h*60分鐘內(nèi)完成的任務(wù)集合TUij.

Step 7.選擇最大的|TUij|作為參與者uj完成的任務(wù)集合TUij.

循環(huán)執(zhí)行步驟1-步驟7，確定參與者完成的任務(wù)集合直到任務(wù)執(zhí)行完畢.

Step 8.輸出參與者集合P={P1,P2,P3,…,Px}及其完成的任務(wù)集合TU={TU1,TU2,TU3,…}.

End

4 實(shí)驗(yàn)與結(jié)果分析

本文通過真實(shí)數(shù)據(jù)來模擬參與者、任務(wù)所在位置.實(shí)驗(yàn)中假設(shè)完成每個(gè)任務(wù)的時(shí)間為5分鐘，假設(shè)用戶移動(dòng)的路線按照點(diǎn)到點(diǎn)直線進(jìn)行，由于是緊急任務(wù)，所以時(shí)間設(shè)置為1小時(shí).結(jié)合現(xiàn)實(shí)情況，一般人們習(xí)慣使用自己的交通工具出行，比如開車或者騎電動(dòng)車.由于共享單車的出現(xiàn)與盛行，一些類似于學(xué)生群體的人們騎自行車出行的概率也很普遍，除此之外還有個(gè)別不會(huì)騎車的人只能步行.在這種環(huán)境中，不同的用戶速度也會(huì)大不相同.考慮到這一點(diǎn)，本文提出利用用戶近期的速度計(jì)算其速度平均值作為該平臺(tái)中候選參與者的速度值.實(shí)驗(yàn)為了取得相對(duì)的準(zhǔn)確性，以下結(jié)果都是通過多次實(shí)驗(yàn)平均而來.

4.1 N值的選定

VT-MOST算法中選用的N值，考慮到距離、速度對(duì)于實(shí)驗(yàn)的綜合影響，以最小化速度與距離的乘積為目標(biāo)，經(jīng)過多次實(shí)驗(yàn)確定為5.如圖1所示，隨著N值的增加，選擇出的參與者人數(shù)與其移動(dòng)的總距離的乘積先下降后上升.本文中取N=5.

圖1 N值變化對(duì)VT-MOST的影響

4.2 任務(wù)個(gè)數(shù)變化

如圖2所示，參與者人數(shù)隨著任務(wù)個(gè)數(shù)的增加而增加，移動(dòng)距離也在不斷增加.每個(gè)人完成的任務(wù)數(shù)在上下波動(dòng)，呈增加趨勢(shì).圖2是任務(wù)個(gè)數(shù)的變化對(duì)T-MOST與VT-MOST算法的各項(xiàng)性能影響的實(shí)驗(yàn)結(jié)果，VT-MOST算法選擇出的參與者人數(shù)相對(duì)于T-MOST中的參與者人數(shù)較少，隨著任務(wù)個(gè)數(shù)的增加差距更大.VT-MOST中平均每個(gè)人完成的任務(wù)個(gè)數(shù)更多，移動(dòng)距離相對(duì)較遠(yuǎn)一點(diǎn)或者幾乎接近T-MOST.VT-MOST中總距離與人數(shù)的乘積較T-MOST算法更小.如果需要參與者人數(shù)最小化VT-MOST算法更好一點(diǎn).

圖2 任務(wù)個(gè)數(shù)變化對(duì)算法的影響

圖3比較了PT-MOST算法與VPT-MOST算法隨著任務(wù)個(gè)數(shù)變化的各種變化.PT-MOST算法選擇的參與者較VPT-MOST多一點(diǎn)，完成人數(shù)數(shù)目較少，移動(dòng)距離較小或接近于PT-MOST算法.

圖3 任務(wù)個(gè)數(shù)變化對(duì)算法的影響

4.3 候選人數(shù)變化

在感知系統(tǒng)參與者優(yōu)選方法中，候選者、任務(wù)影響著任務(wù)分配的結(jié)果.候選人數(shù)越多，選擇出的參與者也更加優(yōu)異.任務(wù)個(gè)數(shù)越多，選擇的參與者更多，移動(dòng)距離越大.如圖4、圖5所示，隨著候選者人數(shù)增加，選擇出的參與者人數(shù)會(huì)減小，移動(dòng)距離減小，移動(dòng)距離與參與者人數(shù)的積減小.以參與者為中心的算法所需參與者人數(shù)較多，移動(dòng)距離最短.以任務(wù)為中心的算法則相反，參與者人數(shù)較少移動(dòng)距離較大一點(diǎn).

圖4是T-MOST與VT-MOST算法的對(duì)比，隨著候選者人數(shù)的增加，VT-MOST算法中選擇出的參與者人數(shù)較少，平均每個(gè)人完成的任務(wù)數(shù)較大，與T-MOST相比VT-MOST移動(dòng)距離在其上下波動(dòng).

圖4 候選者變化對(duì)算法影響

圖5比較了PT-MOST算法與VPT-MOST算法關(guān)于候選者人數(shù)變化的對(duì)比圖，隨著候選者人數(shù)的增加，VPT-MOST算法中選擇出的參與者人數(shù)較少，平均每個(gè)人完成的任務(wù)數(shù)較大，與PT-MOST相比VPT-MOST移動(dòng)距離較大一點(diǎn)或幾乎接近.

圖5 候選者變化對(duì)算法影響

4.4 時(shí)間限制不同

本文針對(duì)的發(fā)布任務(wù)為緊急任務(wù)，所以對(duì)時(shí)間要求很嚴(yán)格.即時(shí)間h的選擇對(duì)于實(shí)驗(yàn)的情況會(huì)有很大的影響，當(dāng)時(shí)間為0.5小時(shí)、1小時(shí)、1.5小時(shí)時(shí)，對(duì)各種情況進(jìn)行分析.由圖6可知，當(dāng)時(shí)間限制增加時(shí)參與者人數(shù)在不斷下降，移動(dòng)距離略微增加，人數(shù)與距離的乘積呈下降趨勢(shì).在各種情況下，以任務(wù)為中心的算法所需的參與者人數(shù)較多，移動(dòng)距離較短.以用戶為中心的算法所需的參與者人數(shù)較少，移動(dòng)距離較長(zhǎng).四種算法的比較中，PT-MOST算法所需參與者人數(shù)最多，移動(dòng)距離較短.VT-MOST算法所需的參與者人數(shù)最少，移動(dòng)距離最大.VPT-MOST算法與PT-MOST參與者人數(shù)相比較少.

圖6 時(shí)間限制變化對(duì)算法影響

4.5 時(shí)間復(fù)雜度

如圖7所示，隨著任務(wù)個(gè)數(shù)的增加，PT-MOST的運(yùn)算時(shí)間增幅很大，而VPT-MOST則緩緩上升.并且任務(wù)個(gè)數(shù)越大時(shí)PT-MOST與VPT-MOST的運(yùn)行時(shí)間差值越大.

圖7 任務(wù)個(gè)數(shù)對(duì)運(yùn)行時(shí)間的影響

5 總 結(jié)

繼文獻(xiàn)[16]提出的3種參與者優(yōu)選算法，本文提出另一種解決方法：VT-MOST、VPT-MOST算法，其中VT-MOST針對(duì)T-MOST做出優(yōu)化.VPT-MOST針對(duì)PT-MOST做出優(yōu)化，主要體現(xiàn)在時(shí)間復(fù)雜度.本文提出取其速度的平均值作為其速度參考值相對(duì)而言更加接近于實(shí)際情況.當(dāng)候選者具有不一樣的速度值時(shí)，選擇參與者的時(shí)候比較的不再只是距離最近，也要考慮速度對(duì)于各候選者選擇的影響.VT-MOST算法在選擇用戶時(shí)比較距離初始任務(wù)最近的N位候選者，在時(shí)間h的限制條件下比較N位候選者的任務(wù)個(gè)數(shù).選擇完成任務(wù)個(gè)數(shù)最大的候選者作為參與者.而VPT-MOST算法中將感知區(qū)域劃分為若干個(gè)組(100個(gè)組)或者小格子，采用聚類的思想.將候選者劃分為不同的組，選擇各個(gè)組內(nèi)速度值最大的候選者然后計(jì)算其在時(shí)間h條件限制下的任務(wù)個(gè)數(shù)，選擇完成任務(wù)個(gè)數(shù)最大的候選者作為參與者.當(dāng)平臺(tái)中參與者人數(shù)大于小格子數(shù)時(shí)，可以減小算法迭代一次的運(yùn)算時(shí)間.這樣會(huì)更加優(yōu)化參與者選擇的過程.通過真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)?zāi)M，結(jié)果表明，在很多情況下，VT-MOST算法中的參與者優(yōu)選方法會(huì)使參與者人數(shù)最小化，不足之處是它的移動(dòng)距離有時(shí)會(huì)相對(duì)大一些.如果希望參與者人數(shù)最小化，VT-MOST算法的性能會(huì)更好一些.相對(duì)于PT-MOST算法VPT-MOST在很大程度的減少了運(yùn)算復(fù)雜度，其選擇出的參與者個(gè)數(shù)也較小.但是這里速度的值只是一個(gè)近似值.在實(shí)際任務(wù)執(zhí)行中，由于交通道路的堵塞、交通工具的選用等都會(huì)引起參與者的速度發(fā)生變化，具有不確定性.