群組協作的移動群智感知任務分配方法

吳大鵬 管 芃 張普寧 楊志剛 王汝言

(重慶郵電大學通信與信息工程學院 重慶 400065)(先進網絡與智能互聯技術重慶市高校重點實驗室 重慶 400065)(泛在感知與互聯重慶市重點實驗室 重慶 400065)

1 引言

任務分配是移動群智感知面臨的主要問題之一，主要解決在特定的任務要求約束下以感知任務為導向的感知參與者的選擇問題，任務分配的結果將直接關乎感知任務的成敗。傳統的任務分配的研究主要針對單個參與者，在這些研究中單個感知任務由單個參與者完成。然而，在某些感知場景(例如智慧交通)中，參與者需要在特定區域感知足夠的時間。上述場景中的任務屬于時空覆蓋任務的范圍，需要來自足夠多的感知區域的有足夠時間的感知數據。通常，任務的覆蓋范圍相對較大，并且任務的持續時間很長。因此，單個參與者無法在整個時間段內覆蓋整個任務區域。在解決這類協作任務時，往往需要多個參與者合作完成[1]。因此，設計面向參與者群組的任務分配機制是執行時空覆蓋感知任務的關鍵。然而，當前大多數的移動群智感知任務分配的研究都是假設感知平臺擁有充足的感知參與者歷史信息[2-4]。對于新成立的感知平臺，感知平臺中存在新老參與者交替的情況，對于老參與者可以通過分析參與者的歷史數據進行任務分配，對于新參與者感知平臺由于沒有參與者的歷史信息，將會存在任務無法有效分發的“冷啟動”問題。當前，已有部分文獻研究了群組模式的群智感知[1,5,6]，它們都忽視了多個感知任務并行處理的情況。因此，在生成感知群組之后，需要進一步設計合理的任務-群組匹配機制來保證感知任務的成功完成。

隨著在線社交網站的蓬勃發展，每個用戶的興趣可能與其好友相似或受其好友影響。因此，用戶間的社交關系提供了有關用戶的額外信息，并且可以緩解“冷啟動”問題[7]。本文基于社交關系思想，設計群組協作的面向時空覆蓋類感知任務的分配方法，解決移動群智感知中的冷啟動及多任務有效并行分配問題，使其能夠更好地應用于普適計算以改善人們的日常生活。

本文的主要貢獻如下：

(1) 設計群組協作的任務分配框架。由云平臺對參與者進行屬性分析，選出群組領導節點與成員節點，以群組協作的方式代替單參與者進行任務分配，有效提升了群組任務的完成率。

(2) 提出偏好感知的社交群組生成方法。引入參與者間的社交關系生成社交群組，解決時空覆蓋感知任務分配的“冷啟動”問題。引入技能動態更新機制，動態更新參與者技能以更好地進行任務參與者選擇。

(3) 提出效用優化的任務群組匹配方法。將平臺效用優化問題抽象建模為多感知任務-多社交群組間的匹配問題，并利用網絡流模型進行任務-社交群組匹配決策，最大化感知平臺效用。

2 問題建模

2.1 系統模型

本文考慮到時空覆蓋類感知任務具有時間跨度大、空間范圍廣等特點，造成的單參與者感知模式不適用問題。首先基于社交網絡理論，綜合考慮時空覆蓋任務特征智能生成任務群組執行感知任務，以群組模式替代單參與者模式，提升感知任務完成率。

感知任務分配擬主要由任務發布、屬性分析、群組生成、群組任務分配和群組任務執行5個階段組成。在任務請求者上傳感知任務之后，平臺會對已注冊的新老參與者進行屬性分析。假定感知參與者在平臺注冊時會上傳自己的社交關系，因此感知平臺中會出現新老參與者相互交替的情況。由于老參與者的屬性維度比較齊全，可直接進行參與者的任務屬性分析。而新參與者屬性維度較欠缺，將會出現任務分發的問題。由于新老參與者之間普遍存在著社交關系，可以借助社交關系進行參與者的任務接收率分析，以解決參與者任務歷史信息不足的情況。

在對新老參與者進行屬性分析之后，每次針對特定的感知任務都會生成特定的感知社交群組。平臺會采用所提社交群組生成方法，進行特定的領導節點與群組成員節點選取。在生成特定的感知社交群組之后，考慮到在城市感知等場景中，需要同時對多個區域進行感知。加之，大多數用戶在社交網絡中只有相對稀疏的社交關系[8]，特別是對于那些與其他用戶的社交關系很弱的新參與者，無法保證總能找到具有足夠候選參與者的社交群組，需要設計相應的任務-社交群組匹配機制。平臺采用所提任務群組匹配方法，根據任務及社交群組在參與者人數和預算方面的需求對社交群組進行整合生成任務群組。在生成任務群組之后，會將任務進行下發，任務群組在執行完感知任務之后，會上傳感知數據到云平臺。最后，由云平臺下發相應的任務獎勵。

2.2 問題建模

在移動群智感知系統中主要有3個部分即任務、平臺和感知參與者。

本文的優化目標為最大化平臺效用，如式(1)所示，平臺效用表現為任務完成的回報與完成任務的工人成本之差，第1個約束表示對于每個感知任務ti需要的參與者人數超過人數閾值ri，Mj表示群組j的人數，第2個約束表示參與每個感知任務ti的人員成本不能超過任務預算Bi。

3 偏好感知的社交群組生成方法

本部分基于參與者間的社交關系提出偏好感知的社交群組生成方法。任務發起者將任務上傳感知平臺之后到任務正式發布之前，感知平臺會充分分析任務與參與者的屬性，再針對特定的感知任務進行社交群組的生成。社交群組主要由領導節點與成員節點組成。感知平臺會選擇感知群組的領導節點，在選出領導節點之后，再進行群組成員節點的選取。群組領導節點主要在老參與者中進行選擇，原因在于老參與者的任務完成歷史更加豐富。

3.1 領導節點選取

使用 dis(xi,xj) 表示數據xi與數據xj的差異，簇心數據即為任務真值xr，在任務真值為xr的條件下，參與者ui的數據質量[10]為qi=1/(dis(xi,xj)+1)。當參與者的能力達到閾值λ就不再對其進行更新，平臺將會將參與者判定為老參與者。對于老參與者，由于其自身的能力水平比較固定，主要為感知參與者完成特定的感知任務占所有完成任務的比例。表示參與者對某一種任務的完成次數，表示參與者完成歷史任務的總集合。

在完成上述屬性值的計算之后，再利用等級效用函數進行參與者排名評估

Rank函數表示候選參與者在相關屬性的排名，分數越高的參與者排名越高。對上述3種因素采用乘法融合的方法[11]選出領導節點，并利用Top-K搜索選取領導節點，再根據領導節點的社交以及地理位置進行群組生成。

3.2 社交群組生成

感知平臺在選出領導節點之后，以領導節點為源節點，通過領導節點的社交關系進行進一步的群組成員的選取。主要通過將領導節點建模為根節點，在其社交好友中進行進一步的感知參與者搜索。領導節點的好友中既有新參與者也會有老參與者，分別建模新老參與者的偏好來進行社交群組成員的選取，進一步，根據任務預算約束來招募群組感知參與者。

定義8 (老參與者任務接受率)：對于老參與者而言，特定任務的任務接受率可以表示為

主要由3部分組成：I(prtuj,I1max)表示參與者對任務類型的偏好，I(prduj,I2max)表示參與者對任務距離的偏好，感知任務的獎勵激勵則由I(prruj,I3√max) 表 示。本 文 采 用I(x,Imax)=(Imax-1)1-(1-x)2+1的方式來聚合任務類型以及距離偏好對參與者任務接收的影響[12]。P1為一個超參數，Imax表示預定義的概率遞增上限。任務類型偏好與任務距離偏好定義為

式(7)中任務類型偏好主要反映當前任務與參與者歷史任務之間的相似度。利用Jaccard相似度來進行計算，如果當前任務更加貼合參與者的任務偏好，則相應的任務接受率會更高。在任務距離偏好方面則主要考慮任務距離對參與者的任務接收的影響。dist(uj,loci)表示當前任務與參與者之間的距離，loci表示參與者的歷史簽到經緯度的均值，α為一個距離超參數。由于參與者往往傾向于就近進行任務感知，因此，通過量化任務與參與者活躍位置之間的距離可以更好地反映老參與者的任務接受率[13]。

式(9)中，f(·)為sigmoid函數，參與者在完成任務的過程中會有一個特定的初始任務成本θ，只有當任務回報大于任務成本時，參與者才會參與到感知任務中[14]。

定義9 (新參與者任務接受率)：新參與者接收任務的概率可以表示為

同理，由社交關系、任務距離以及任務獎勵激勵3部分組成。P2為一個超參數，I4max～I6max表示預定義的概率遞增上限。對于新參與者而言，平臺沒有感知參與者的任務完成歷史。但是，參與者的感知行為在一定程度上受到其社交關系的影響，進而促使參與者參與特定的感知任務。因此，考慮參與者的社交關系對參與者感知行為的影響有利于提高感知任務的接收。同時，完成感知任務的回報也會影響參與者是否參與任務。由于參與者在完成感知任務的過程中，會付出一定量的勞動成本，如果完成任務所得的回報越高，那么參與者參與感知任務的概率也會相應的提高。相應的社交關系和獎勵激勵定義為

式(11)主要通過Jaccard相似度來衡量兩個參與者之間社交關系的強弱，本文通過分析好友的任務接受率來進一步推斷特定參與者的任務接收率，N(ui) 表示參與者ui的在線社交好友集合，如果參與者之間共享更多的相鄰節點，則社交關系會更強。同時，在進行新參與者的招募時也應考慮任務獎勵帶來的影響。通過3.1節選出的leader節點為源節點，在其好友中進行廣度優先遍歷。由于領導節點的好友關系中會出現新老參與者共存的現象，因此需要分別計算每個好友參與者接收感知任務的概率，選擇滿足超過特定概率值的參與者，直到招募到足夠的成員參與者。同時，在每次招募成員的過程中會動態地更新參與者成員的技能。

4 效用優化的任務群組匹配方法

感知平臺在劃分好社交群組之后，將會進行多感知任務并發的任務分配。因此，本文設計效用優化的任務群組匹配方法。

4.1 任務群組生成問題建模

定理1 TGM問題是NP-hard問題。

證明 本文將0-1背包問題轉化為任務-群組匹配(Task-Group Matching, TGM)問題的一個特殊實例。

本文證明TGM問題等價于背包問題。假設利用zji表示群組j完成任務i得到的獎勵，則獎勵函數可以簡化為zjixji。進一步，將群組的人數看成背包的重量，群組2元決策變量xji看成物品是否放入背包bi，則TGM問題可以退化為0-1背包問題[15]。即會有如等式(12)成立

由于已知0-1背包問題是非確定性多項式歸約難(Non-deterministic Polynomial-hard, NP-hard)問題，則TGM問題至少也具有與0-1背包問題相同的復雜性。因此，TGM問題是NP-hard問題。

給定由前面3.2節生成的社交群組，用集合G*={G1,G2,...,Gk}表示，假設每個社交群組都需要完成一系列的感知任務。第k個社交群組Gk可以完成的任務數量上限為gk。與此同時，任務請求者同時發布了多個同種類型的感知任務T={t1,t2,...,tm}，任意一個感知任務tm最多會被rm個參與者完成。在本文中，由于不同的社交群組有不同的任務參與者數量。因此，在任務匹配的過程中假設同一個群組可以參與多個感知任務，但是每個群組里面的參與者每次只能參與1個感知任務。本文利用GTm={gtm1,gtm2,...}來表示參與完成感知任務tm的社交群組集合。進一步，利用 TGk={tgk1,tgk2,...}來表示分配給社交群組Gk的任務集合，C(TGk)是Gk完成任務的成本。那么TGM問題可以進一步表示為

解決TGM問題主要有兩個挑戰：一是每個社交群組可以同時完成多項感知任務；另一個是TGM問題有兩個優化目標。對于挑戰1，社交群組與任務的匹配屬于多任務分配問題，存在著多個群組與多個任務進行匹配的情況。對于挑戰2，在兩個優化目標中，在式(13)中第1個優化目標主要體現為最大化任務的完成數，第2個優化目標為最小化任務的完成成本。兩個優化目標是相互矛盾的，不可能同時得到滿足兩個優化目標要求的最優解。然而，可以在完成的總任務數量和總任務成本之間進行權衡以達到目標。

4.2 任務群組生成

最小費用最大流(Minimum Cost Maximum Flow, MCMF)模型旨在找到一組成本最小、流量最大的最優路徑。MCMF模型的流網絡是有向圖，其中每條邊都有容量、流量和成本。邊的容量表示為可以通過邊的最大流量。為了對TGM問題進行求解，本文利用MCMF模型，將社交群組成員完成任務的花銷代表成本，完成任務的總數被建模為流。由于流網絡中不可能只有參與者節點和任務節點，以及需要在流網絡中表示參與者和任務的不同需求，本文對MCMF模型進行了改進，具體的方法模型如圖1所示。

圖1 TGM-MCMF算法模型圖

對于源節點和社交群組節點之間的每條邊的容量為gk，這反映了每個社交群組最多可以同時執行gk個任務。同時邊的成本為0，因為源節點和群組節點之間的邊僅用于流入流，沒有產生成本。此外，從群組節點和任務節點流入匯聚節點的流量應該反映任務的完成。對于匯聚節點而言，總的最大流量為，其中任務節點與匯聚節點之間的每條邊的容量為rm，邊的成本為0。本文首先枚舉所有可能的任務集合，將感知任務標號為1～m。任何一個任務都可以由來自多個群組的多個參與者執行。此外，群組節點和任務集節點之間的邊的成本是任務的完成成本。最后，任務節點和匯聚節點之間的邊的容量為rm，因為一個感知任務最多可以由rm個參與者同時執行。

TGM-MCMF算法包括兩部分：一是構建MCMF模型的流網絡；另一種是在流網絡中尋找最優解。首先，導入由3.2節生成的社交群組集合 {G*}以及任務集合T。接著，計算群組成員的任務參與成本ck，成本主要指群組成員完成任務的成本，主要為群組參與者的任務初始成本以及通信成本。通信成本主要為群組成員k與群組領導節點i之間的社交關系跳數與單位跳數成本之積，以及兩個群組領導節點之間的通信成本?，因此可得ck=diski×unitki+θk+?。然后，將流f初始化為0，在殘差網絡Gf中貪婪地選擇增廣路徑r*。沿r*用cf(r*)增廣流f，直到殘差網絡Gf中沒有增廣路徑。最后，輸出任務群組集合 {M*} 以及完成的任務集合T*。

感知平臺在選出任務群組之后，會將相應的感知任務分發給每個社交群組的領導節點，由領導節點進行感知任務的進一步分發。在領導節點將任務發布給群組成員后，群組成員節點會到相應的任務區域完成感知任務。在任務完成后將任務結果反饋給領導節點，由領導節點將感知數據上傳感知平臺。最后，在感知平臺將數據反饋給任務請求者之后，平臺會將任務獎勵下發給相應的群組成員節點。

5 仿真分析

5.1 數據集

本文主要在配備Intel Core i9-10900K以及Python 3.8語言的計算機上進行仿真實驗。所用數據集為一個同時包含好友關系以及位置簽到的Gowalla數據集。主要的仿真參數如表1所示。

表1 實驗參數

5.2 對比算法與評估指標

本文主要采用3個算法進行對比實驗，即面向群組的合作群智感知(Group-oriented Cooperative Crowdsensing, GoCC)[1]算法、合作眾包(Cooperative Crowdsourcing, C2)[16]算法和忽略感知技能更新的最小費用最大流群組-任務匹配(Task-GroupMatching-Minimum Cost Maximum Flow-without prefer, TGM-MCMF-wp)算法。其中GoCC是以參與者的任務成本為導向的參與者選擇算法，在算法中考慮參與者的任務成本以及社交偏好，忽略參與者的感知技能。C2則不考慮參與者的社交偏好，只考慮參與者的任務成本進行參與者選擇。最后，TGMMCMF-wp為不考慮參與者技能更新的算法變體。仿真指標主要有兩個即平臺效用與任務完成率。

(1) 平臺效用

平臺效用為已完成的所有感知任務的預算與成本的差值，本文的目標在于最大化感知平臺的效用。

(2) 任務完成率

任務完成率主要為已完成的感知任務數量與總的感知任務數量的比值。

5.3 結果分析

從圖2(a)可以看到隨著感知任務數量的增加，TGM-MCMF, TGM-MCMF-wp, GoCC以及C2 4個算法的平臺效用都呈上升趨勢。由于考慮了參與者技能的更新，隨著感知任務的不斷推進，相較于TGM-MCMF-wp算法，在TGM-MCMF中將會有更多的新參與者成為老參與者以及成為領導節點，感知平臺的效用也將會不斷得到提升。因此，本文算法相較于TGM-MCMF-wp算法平均提升了17.4%，相較于GoCC平均提升了22.1%，相較于C2平均提升了41.7%。從圖2(b)中可以看到隨著感知任務數量的增加，4個算法的任務完成率都比較穩定。由于TGM-MCMF算法綜合考慮了其他算法的因素，具有最高的任務完成率。因此，本文算法相較于TGM-MCMF-wp算法平均提升了8.2%，相較于GoCC平均提升了8.1%，相較于C2平均提升了18.4%。

圖2 感知任務數量帶來的影響

圖3為任務人數閾值ri帶來的影響。在圖3(a)中，由于感知任務的完成標準為招募到超過任務人數閾值的參與者，所以當任務人數閾值ri上升時，感知任務的完成難度也將不斷上升。TGM-MCMF,TGM-MCMF-wp, GoCC以及C2 4個算法的平臺效用都呈下降趨勢。由于TGM-MCMF算法綜合考慮了其他算法的因素，因此平臺效用下降最為緩慢。本文算法相較于TGM-MCMF-wp算法平均提升了51.7%，相較于GoCC平均提升了30.3%。在圖3(b)中，隨著任務人數閾值ri的增加，4個算法的任務完成率都呈下降趨勢。由于TGM-MCMF算法綜合考慮了其他算法的因素，因此任務完成率下降最為緩慢，本文算法相較于TGM-MCMF-wp算法平均提升了8.0%，相較于GoCC平均提升了7.6%，相較于C2平均提升了12.8%。

圖3 任務閾值帶來的影響

從圖4(a)可以看到隨著參與者初始成本的增加，達到任務的人數閾值也將越來越困難，由于TGM-MCMF算法綜合考慮了算法的相關因素。因此，相較于TGM-MCMF-wp算法平均提升了19.9%，相較于GoCC平均提升了16.9%，相較于C2平均提升了45.1%。從圖4(b)中可以看到隨著參與者初始成本的增加，任務的人數需求也將越來越難以滿足，由于TGM-MCMF算法綜合考慮了算法的相關因素。因此，本文算法相較于TGM-MCMF-wp算法平均提升了4.8%，相較于GoCC平均提升了4.9%，相較于C2平均提升了9.1%。

圖4 參與者初始成本帶來的影響

圖5 單位人數預算帶來的影響

圖6為4個算法的運行時間對比，主要考慮了感知任務數量和任務人數閾值ri帶來的影響。通過從簽到數據集中的密集區域隨機選取500～2 500個任務區域進行任務分配，1～25隨機生成任務閾值。從圖6(a)中可以看到隨著感知任務數量的不斷增加，4個算法的運行時間皆呈上升趨勢。相較于TGMMCMF-wp算法，TGM-MCMF通過進行參與者的技能更新，以更低的成本生成更多的社交群組。TGM-MCMF相較于GoCC通過對參與者感知技能的評估，保證更高的任務完成率。而C2僅以成本為導向，則花費了最低的算法運行時間。從圖6(b)中可以看到隨著任務閾值的不斷增加，4個算法的運行時間皆呈上升趨勢。TGM-MCMF相較于基線算法在參與者的技能偏好、社交偏好以及參與者技能更新方面進行綜合評估，因此在社交群組的生成過程中將會花費更多的計算時間以滿足感知任務的閾值需求，在更多計算開銷的情況下，得到了最高的平臺效用與任務完成率。

圖6 算法運行時間對比

在時間復雜度方面，對于參與者集合W，群組任務集合T，在群組領導節點的生成過程中，感知平臺需逐一對參與者進行屬性評估，相應的時間復雜度為O(|W|2)。在群組成員的生成過程中，這一過程需要搜索領導節點的社交好友，由于參與者群組的數量大于感知任務的數量，因此，在k個領導節點的情況下相應的時間復雜度為O(k·|T|·|W|·log2|W|)。在任務群組的生成過程中，由于圖的節點數量為m+k，算法的時間復雜度為O(k2(m+k))[2]。

6 結束語

本文研究了移動群智感知中的群組任務分配問題，在面對需要多個參與者的時空覆蓋類感知任務時，通過招募感知群組來完成感知任務。針對當前的大多數任務分配文獻在面對新參與者歷史信息不足時出現的任務分配問題，通過對新老參與者的社交關系進行評估生成社交群組。在社交群組生成之后，利用網絡流理論來進行社交群組-感知任務的2次匹配以最大化感知平臺的效用和任務完成率。至于未來的研究工作，將會進一步考慮參與者的激勵問題，例如針對新成立的感知平臺設計相應的參與者激勵機制以擴大參與者用戶池，以及在感知任務的完成過程中的參與者隱私保護問題。