移動群智感知多任務參與者優選方法研究

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

(天津工業大學 計算機科學與技術學院，天津 300000)E-mail:2550633673@qq.com

1 引 言

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

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

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

2 參與者優選模型

2.1 相關工作

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

本文提出的VT-MOST、VPT-MOST算法中各用戶的速度不一樣，由此在一定時間限制內所完成的任務個數也不一定，所以相對于T-MOST和PT-MOST，獎勵激勵就會有所變化.速度大的用戶在一定時間限制內(比如1小時)完成的任務個數多，總距離也大，隨之獎勵激勵、動態激勵也會較大.

2.2 總體架構

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

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

3 算法設計

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

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

(1)

(2)

(3)

min|P|

(4)

3.1 VT-MOST

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

算法1.VT-MOST

輸入：用戶集合U，任務集合T

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

Begin

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

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

Step 3.循環執行Step 2直到參與者uij完成這些任務的時間大于h*60分鐘.

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

Step 5.循環執行Step 1-Step 4，選擇出的每個候選者uij在h*60分鐘內完成的任務集合TUij.

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

Step 7.循環執行Step 1-Step 7，確定參與者完成的任務集合.

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

End

3.2 VPT-MOST

文獻[16]提出的PT-MOST算法是以參與者為中心的，由于算法運算的時間復雜度過高.當平臺中候選參與者較多時，運算成本過高.本文提出的VPT-MOST采用文獻[13]提出的一種將感知區域劃分為一組子區域或者格子的方法.有效的降低了其運算的時間復雜度.本文中由于參與者的移動速度不同，在選擇候選參與者的時候不再比較每個候選者的任務集合，而是根據各個子區域，在每個子區域中存在一個速度值最大的候選者計算其任務集合.這樣通過比較候選者的任務集合確定參與者.

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

算法2.VPT-MOST

輸入：任務集合T，用戶集合U

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

Begin

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

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

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

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

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

Step 6.循環執行步驟1-5，選擇出每個候選者uij在h*60分鐘內完成的任務集合TUij.

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

循環執行步驟1-步驟7，確定參與者完成的任務集合直到任務執行完畢.

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

End

4 實驗與結果分析

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

4.1 N值的選定

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

圖1 N值變化對VT-MOST的影響

4.2 任務個數變化

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

圖2 任務個數變化對算法的影響

圖3比較了PT-MOST算法與VPT-MOST算法隨著任務個數變化的各種變化.PT-MOST算法選擇的參與者較VPT-MOST多一點，完成人數數目較少，移動距離較小或接近于PT-MOST算法.

圖3 任務個數變化對算法的影響

4.3 候選人數變化

在感知系統參與者優選方法中，候選者、任務影響著任務分配的結果.候選人數越多，選擇出的參與者也更加優異.任務個數越多，選擇的參與者更多，移動距離越大.如圖4、圖5所示，隨著候選者人數增加，選擇出的參與者人數會減小，移動距離減小，移動距離與參與者人數的積減小.以參與者為中心的算法所需參與者人數較多，移動距離最短.以任務為中心的算法則相反，參與者人數較少移動距離較大一點.

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

圖4 候選者變化對算法影響

圖5比較了PT-MOST算法與VPT-MOST算法關于候選者人數變化的對比圖，隨著候選者人數的增加，VPT-MOST算法中選擇出的參與者人數較少，平均每個人完成的任務數較大，與PT-MOST相比VPT-MOST移動距離較大一點或幾乎接近.

圖5 候選者變化對算法影響

4.4 時間限制不同

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

圖6 時間限制變化對算法影響

4.5 時間復雜度

如圖7所示，隨著任務個數的增加，PT-MOST的運算時間增幅很大，而VPT-MOST則緩緩上升.并且任務個數越大時PT-MOST與VPT-MOST的運行時間差值越大.

圖7 任務個數對運行時間的影響

5 總 結

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