面向異構效用的移動群智感知多目標任務分配

傅彥銘 陸盛林 祁康恒 許勵強 陳嘉元

摘 要：當前移動群智感知（MCS）任務分配往往只考慮工人或平臺單方面的效用，并且效用的構成也不夠全面。因此基于工人信譽指數和任務熟練指數，設計了工人和平臺兩方面的異構效用機制，并提出一種雙種群競爭的多目標進化算法（DCMEA）來獲得最優的工人和平臺異構效用。該算法首先通過隨機貪婪初始化種群，然后使用二元競標賽算法將種群劃分為勝者種群和敗者種群，并針對每個種群采用不同的進化策略。最后，通過修復算子使進化過程中的無效個體滿足約束條件。在真實場景的數據集上進行實驗表明，與基線算法相比，DCMEA收斂速度更快，能夠找到精度更優、穩定性更好的任務分配解集，同時在更為復雜的場景中依然能夠保持其性能。

關鍵詞：移動群智感知；多任務分配；多目標優化；雙種群競爭進化；信譽指數；任務熟練指數

中圖分類號：TP393.01?? 文獻標志碼：A?? 文章編號：1001-3695（2024）01-023-0159-06

doi：10.19734/j.issn.1001-3695.2023.04.0186

Multi-objective task assignment towards heterogeneous utilities in mobile crowdsensing

Abstract：Most of the existing MCS task allocation methods often only consider the unilateral utility of workers or platforms，and the composition of utility is not comprehensive enough.Therefore，this paper designed a heterogeneous utility mechanism for both workers and platforms based on the worker reputation index and task proficiency index.It proposed a dual-population competitive multi-objective evolutionary algorithm （DCMEA） to obtain the optimal worker and platform heterogeneous utilities.The algorithm firstly initialized the population using a stochastic greedy algorithm，then divided the population into a winner population and a loser population using a binary bidding tournament algorithm，and employed different evolutionary strategies for each population.Finally，this paper proposed the repair operator to make the invalid individuals in the evolution process satisfy the constraint.Experiments on real-world datasets show that DCMEA converges faster than the baseline algorithm，and can find more accurate and stable task allocation solution sets，while maintaining its performance in more complex scenarios.

Key words：mobile crowdsensing；multi-task allocation；multi-objective optimization；competitive evolution of two populations；reputation index；task proficiency index

0 引言

移動群智感知（MCS）來源于“眾包”，通過參與者持有移動設備相互合作完成眾多的任務，是一種新的感知范式［1，2］。移動互聯網、5G等技術的發展使任何具有微型傳感器的移動設備（如智能手機和平板電腦）攜帶者都可以成為MCS中的數據源。由于在收集感知數據方面具有高效性和擴展性，MCS在不同的領域中具有廣泛應用，例如：環境監測［3］、交通規劃［4］、公共安全［5］、醫療保健［6］。MCS包含任務發布、任務分配、任務執行和數據收集四個階段。其中，任務分配是MCS的核心問題［7］。

從給每個工人分配的任務數角度，MCS任務分配可以分為單任務分配和多任務分配。單任務分配是每次只給可用工人分配單項任務。文獻［8］提出了一種沖突感知參與者招募機制，能夠有效提高平臺效用，同時保證在完成感知任務時無沖突。文獻［9］提出一種強大的隱私保護MCS方案，支持基于地理信息和移動用戶信用點的精確任務分配。然而，隨著MCS任務數量的增加，任務之間相互關聯，在有限的資源下，單任務分配會使工人完成任務的效率變低，MCS平臺無法獲得較好的整體效用。因此，多任務分配給一個工人同時分配多個任務來優化平臺的整體效用。文獻［10，11］采用多任務分配方案，在任務共享有限的激勵預算時，使系統的整體效用最大化。文獻［12］提出了一個具有時間約束和平臺效用最大化的多任務分配問題，并設計了兩種遺傳算法來求解該問題。文獻［13］提出了一種以最大化平均感知質量為目標的綜合空間覆蓋和感知精度的多任務分配方法，并引入改進的遺傳算法求解。

上述任務分配只考慮優化一個目標［14，15］，屬于單目標優化問題，而在分配過程中往往需要同時考慮優化多個目標，以獲得符合多方利益的任務分配方案。文獻［16］設計了一種基于粒子群優化的多目標任務分配算法，最大化感知質量和預算的比值，同時最小化響應時間。文獻［17］對單任務分配提出了一種改進的進化算法，通過平衡因子來選擇用戶，最大化參與者的總回報和感知質量。文獻［18］同時考慮了最大化感知質量和最小化激勵支付，通過帕累托最優粒子群算法解決多目標多任務分配。文獻［19］建立了一種基于變速多任務分配的多目標優化模型，并提出了一種三階段多目標洗牌蛙跳算法解決該模型。然而，在這些多目標分配模型中只考慮了工人的異質性，例如工人的執行意愿、信譽度、旅行速度等因素，而忽略了任務的異質性。在實際分配中，不同類型的任務需要的感知數據并不相同，因此平臺需要匹配合適的工人以提高效用。

本文綜合考慮了工人和任務的異質性，引入工人信譽指數和任務熟練指數，提出了一種優化工人和平臺兩方面異構效用的MCS多任務雙目標優化任務分配方案。結合問題的特點，設計了一種雙種群競爭的多目標進化算法（DCMEA）來求解該問題。此外，在真實場景數據集上驗證了DCMEA求解本文的MCS任務分配方案能夠獲得優于對比算法的精度和穩定性。

1 異構效用MCS多目標任務分配模型

1.1 模型描述

MCS包括一個中心平臺、多個任務發布者及參與工人，其工作流程可用圖1描述。首先，發布者將任務需求上傳到平臺，平臺在獲得任務信息后使用相關的任務分配算法將任務分配給工人。接著，工人完成任務后，將任務完成的結果或感知數據上傳到平臺。最后，平臺收到感知數據后將結果反饋給任務發布者，并獲得相應報酬，同時給工人支付報酬。

若在MCS任務分配中有m名工人參與，W={w1，…，wi，…，wm}。工人wi包含以下信息：wi={lati， lngi，wnummaxi，Ri}。其中lati，lngi表示工人的經緯度坐標；wnummaxi表示工人的最大完成任務數，工人不能重復完成相同的任務；Ri為工人的信譽值，表示工人歷史完成任務的質量和性價比［20］。其中Ls≤Ri≤Lm，Lm為最大信譽值，Ls為最小信譽值。

任務發布者發布了n個任務T={t1，…，tj，…，tn}，任務tj包含以下信息：tj={latj，lngj，tnummaxj，bj，wrj，Skj}。其中：latj和lngj表示任務的經緯度坐標；tnummaxj表示任務最多可以由多少名不同工人完成；bj為工人每次完成任務tj平臺所獲得的報酬。wrj為完成任務tj工人獲得的固定報酬。Skj={sk1j，…，skij，…，skmj}，skij表示工人wi對任務tj的熟練度，其中-1≤skij≤1，skij值越大說明工人對任務越熟悉。

wtij表示一個任務分配，若平臺將任務tj分配給了工人wi，則wtij=1，否則wtij=0。當wtij=1時，工人在完成任務后，分別產生相應的工人異構效用uwij和平臺異構效用upij。當wtij=0時，uwij和upij的值為0。

1.2 異構效用機制

為了充分考慮MCS中工人和任務的異質性，從工人信譽和工人對任務的熟練程度兩個角度出發，定義了工人信譽指數和任務熟練指數兩個指標。

1）工人信譽指數 工人wi的信譽指數Hi用來描述工人信譽的良好程度。指數越高，其完成任務的質量越高，反之亦然。Hi可用式（1）計算［20］。

2）任務熟練指數

任務熟練指數Tij用來描述工人wi對任務tj的熟悉程度。任務熟練指數越高，工人對任務越熟悉，完成任務的質量越高且感知的數據也越準確。Tij可以用Gompertz函數來計算，如式（2）。Gompertz函數描述了事物的發生、發展和成熟三個階段，并已應用于任務分配建模中［21］。

本文設計了異構效用機制。工人在完成一個任務后會有一個固定的獎勵報酬RF，并通過信譽指數和任務熟練指數產生一個獎勵指數ηij，獎勵報酬和獎勵指數相乘得到工人完成任務后獲得的激勵報酬。將激勵報酬加入到工人效用和平臺效用中，更全面地反映了不同任務分配間的效用差異。

3）工人異構效用

工人wi完成任務tj所產生的工人異構效用由式（3）計算。由固定報酬wrj、激勵報酬ηij×RF和花費crij三部分組成。

uwij=wrj+ηij×RF-crij（3）

其中：ηij為獎勵指數，由信譽指數Hi和任務熟練指數Tij計算，如式（4）所示。

crij=p×dsij為工人到任務地點的旅行消耗，其中p為每米花費系數，dsij由Haversine formula計算得出：

4）平臺異構效用

工人wi完成任務tj產生的平臺異構效用upij由式（6）計算。由平臺報酬bj、固定報酬wrj和激勵報酬ηij×RF組成。

upij=bj-wrj-ηij×RF（6）

1.3 基于異構效用的多目標任務分配模型

基于異構效用的多目標任務分配即要尋找最優任務分配方案，使得完成任務能夠獲得最大化的工人效用和平臺效用。該問題可以表示為如下的約束雙目標優化模型。

其中：式（7）（8）分別表示最大化工人和平臺獲得的異構效用；式（9）～（11）為任務分配的約束，分別表示每個工人wi完成的任務數不能超過wnummaxi、任務tj分配給不同工人的數量不能超過tnummaxj，wtij的取值為0或1表示同一個任務最多只能分配給同一工人一次。

2 異構效用MCS多目標任務分配模型求解

MCS多任務分配的解集空間較大，是一個NP-hard問題，無法在多項式時間內求解，因此考慮使用啟發式算法來解決。進化算法已應用于MCS任務分配領域［12，13，17］，其特性也適合于本文的多任務分配問題。本文根據問題的特點設計了雙種群競爭的多目標進化算法（DCMEA）來求解模型，如算法1所示。

算法1根據工人集W和任務集T的信息，對個體進行序列編碼，并采用隨機加權貪婪策略生成初始化種群SP。接著，通過二元錦標賽算法將SP劃分為勝者種群WP和敗者種群LP。對這兩個種群執行不同的交叉和變異操作，使WP注重局部搜索、LP注重全局搜索，實現競爭進化。之后，設計了修復算子對不滿足約束的無效解修復，以保留無效解中的有用信息。最后，將SP、WP和LP種群合并，根據任務分配解的UW和UP值，采用精英保留策略生成下一代種群SP。循環執行上述雙種群進化過程，直至最大迭代次數，得到最優的MCS任務分配方案集。

算法1 DCMEA

輸入：工人集W；任務集T；種群大小N；最大迭代次數times。

輸出：迭代后任務分配解集。

根據算法2初始化任務分配解集種群SP

for i=1：times do

根據算法3將種群SP劃分為勝者種群WP和敗者種群LP，并更新WP和LP使其朝著不同方向進化

根據算法4修復WP和LP中更新后產生的無效解

合并SP、WP、LP生成新的種群NewP

采用精英保留策略在NewP中選取前N個解生成子代種群NP

SP=NP

i=i+1

end for

return SP

2.1 個體編碼方式

通常MCS任務分配會采用0-1編碼的方式，用大小為m×n的數組表示種群個體［13］。行標為工人，列標為任務。數組元素為1表示分配給工人對應的任務，否則為0。隨著任務和用戶數量的增加，0-1編碼會使矩陣包含大量元素“0”，變得稀疏。本文采用基于工人路徑的序列編碼，用一維數組表示一個可行的任務分配方案（種群個體Ci），如圖2所示。Ci由m個片段組成，每個片段的大小不超過工人可完成的最大任務數wnummaxi。每個片段中的數字表示任務的編號，工人根據編號按序完成任務，若沒有分配任務則用0表示。

2.2 隨機加權貪婪初始化

用隨機化的方式初始化種群容易生成無效解，也缺乏較優的解來引導種群朝優化的方向搜索。在多目標問題的求解中，線性加權法是一種常用的方法。對多個目標函數加權重，將多目標問題轉換為單目標問題，本文的兩個優化目標可以轉換為

U=ε×UP+（1-ε）×UW（12）

算法2 隨機加權貪婪初始化

輸入：任務集合T，工人集合W。

輸出：初始種群SP

while i≤N do

生成沒有任務序號的個體Ci

創建候選工人集CWW

創建候選任務集CTT

隨機生成加權權重ε

repeat

從CW中隨機選擇一名工人wr

while j≤wnummaxr do

從CT中貪婪地選擇U值最大的任務ts

將任務ts的序號添加到Ci中wr的片段中

tnummaxs=tnummaxs-1

if tnummaxs≤0 do

CTCT-{ts}

end if

j=j+1

end while

CWCW-{wr}

until CW= or CT=

SP=SPU{Ci}

end while

return SP

上述初始化算法具有以下優勢：a）基于實際問題約束的初始化方法可以避免生成無效初始解；b）基于貪婪策略的線性加權法獲得的解作為種群的初始化解可以引導種群朝優化方向進化；c）通過隨機生成加權權重ε和工人的任務分配順序，可以保證初始種群的多樣性。

2.3 雙種群競爭進化

用二元錦標賽算法將種群劃分為勝者種群和敗者種群，并對兩個種群采用不同的更新策略，使兩個種群沿著不同方向進化。因此在進化過程中能夠增加種群的多樣性和隨機性，使得算法能夠跳出局部最優，提升算法的收斂精度和速度。

1）二元錦標賽劃分種群

首先對種群的個體進行非支配排序、計算擁擠度距離。之后隨機選擇兩個個體，根據Pareto排序等級進行比較，等級高的為勝者，低的為敗者。若Pareto等級相同，進行擁擠度距離比較，擁擠度距離大的為勝者，小的為敗者。在進行N次比較后，將前N/2次比較的勝者構成WP種群，后N/2次比較的敗者構成LP種群。

2）勝者種群進化策略 WP種群在進化時注重局部搜索。首先采用多點交叉策略，選擇種群中C1和C2兩個個體，生成3～5個交叉點，交換C1和C2交叉點上的元素。如圖3所示，假設C1和C2有兩個工人，每個工人有三個任務，在個體C1和C2上生成三個交叉點，由豎線表示。將交叉點上的任務（2，1），（3，2），（9，8）交換后生成新的個體。

多點交叉后對新產生的個體采用兩點交換操作，在新個體上隨機生成兩個變異點，交換兩點上的任務生成新的個體。如圖4所示，將個體C1中虛線方框的任務（5，2）交換后生成新的個體。

勝者種群利用小范圍內的交叉變異操作，保留原有個體的優秀屬性，側重于在局部范圍內搜索更優解。

3）敗者種群進化策略

LP種群進化時注重全局搜索。選擇種群中個體C1和C2，采用順序交叉策略生成兩個新個體。如圖5所示，在個體C1和C2上生成兩個交叉點，由虛線表示。兩條虛線間的任務，即C1中的任務（5，6，3），C2中的任務（7，6，2）固定不變。在C1中去掉在C2固定部分（7，6，2）中出現的任務得到替換序列（5，3，1，9）。用該序列順序替換C2可變部分（1，10，8），更新C2得到（5，7，6，2，3，1）。在C2中去掉在C1固定部分（5，6，3）中出現的任務得到替換序列（1，7，2，10，8）。用該序列順序替換C1可變部分（2，1，9），更新C1得到（1，5，6，3，7，2）。

順序交叉后對新生成的個體采用Scramble變異的策略，在新個體上隨機生成3～5個變異點，將元素按新的順序隨機重新排列生成新的個體。如圖6所示，將個體C1中虛線方框內的任務（5，3，7）隨機排序生成（3，7，5），交換任務后生成新的個體。

順序交叉和Scramble變異增大了個體中元素的改變幅度，擴大了種群的搜索空間，有利于生成新的優秀個體。

雙種群競爭進化如算法3所示。由于選擇的概率導致雙種群中存在少量的相同解。在進化過程中，優勢解局部搜索，劣勢解全局搜索，相同解則同時朝著兩個方向進化。種群沿著多個方向進化，增強了種群的多樣性和隨機性，能夠提高算法的尋優能力。

算法3 雙種群競爭進化

輸入：種群SP。

輸出：進化后新種群WP、LP。

對SP采用二元錦標賽算法生成勝者種群WP和敗者種群LP

for i=1：（N/4」） do

在WP中選擇個體Cwi，Cw（i+N/4」）

采用多點交叉生成兩個新個體替換原有個體

在LP中選擇個體Cli，Cl（i+N/4」）

采用順序交叉生成兩個新個體替換原有個體

i=i+1

end for

for j=1：（N/2） do

對WP中個體Cwj采用兩點交換生成新個體替換原有個體

對LP中個體Clj采用Scramble變異生成新個體替換原有個體

j=j+1

end for

return WP，LP

2.4 修復算子

由于實際問題約束的特殊性，在進化過程中可能會產生無效的任務分配解。本文結合任務分配模型設計了修復算子，將無效解修復成有效解，并保留其中有用的信息。圖7展示了個體C1的修復過程。假設個體C1有三個工人，每個工人有三個任務，2號任務的最大分配數為2。首先將個體C1中工人w11中的2號任務替換成小于最大分配數的3號任務，使任務2不超過最大分配數。接著檢查每個工人是否有重復任務，并將工人w13中的5號任務替換成小于最大分配數的4號任務。

算法4是修復算子，首先統計個體中每個任務已分配的個數，計算每個任務剩余可分配的數量avnumj。接著將avnumj>0的任務替換掉avnumj<0的任務，使每個任務的avnumj≥0。最后對每個工人進行檢查，用avnumj>0的任務替換片段中重復任務。

算法4 修復算子

輸入：無效任務分配解Cinv。

輸出：有效任務分配解Cv。

統計無效解Cinv中每個任務tj分配給工人的個數

將最大分配數減去已分配數，計算出每個任務tj剩余可分配數avnumj

找出avnumj<0的任務tinv

按序號用 avnumj>0的任務tv替換解中的任務tinv

更新每個任務tj的avnumj，使所有的avnumj≥0

對每個工人wi的任務分配片段進行檢查，并記錄有重復分配的任務

按序號選擇avnumj>0的任務替換掉重復任務

return Cv

3 實驗分析

實驗在Windows 10操作系統、Intel Core i5-10200H 2.40 GHz CPU、16.0 GB內存的機器上運行，用MATLAB R2020b編寫算法。本文選取三種多目標進化算法，分別為MOEADUR［22］、GFMMOEA［23］、DEAGNG［24］，來驗證DCMEA算法的性能。其中MOEADUR和DEAGNG是基于分解的多目標進化算法，類似算法已經應用于MCS任務分配領域中［17］，GFMMOEA是近年來提出的較為先進的多目標進化算法。算法參數按照原文獻設置，并添加了修復算子處理約束。

3.1 實驗數據集及參數設置

實驗采用Foursquare數據集［25］中紐約市9：00～12：00的簽到數據進行任務分配的測試。Foursquare數據集包含了大約十個月從紐約市和東京市收集的簽到記錄，每次簽到都包含以下記錄：user ID、venue ID 、venue category ID、venue category name、latitude、longitude、timezone offset in minutes、UTC time。由于紐約市中簽到地點存在較明顯的冷熱區，由此截取了經緯度范圍為［-74.02，-73.92］、［40.68，40.8］，約15 km×10 km的長方形區域，并將數據集中簽到記錄的經緯度視為MCS中任務集的地點，為每個任務生成隨機不同的tnummaxj數及skij值。此外選取不同ID工人初始簽到的地點作為工人的初始時間地點進行任務分配測試，根據文獻［20］隨機生成信譽值Ri，同時將Gompertz函數的參數分別設為a=e/2、b=-1、c=-1，使工人信譽指數和任務熟練指數取值范圍相近。為探尋在不同規模下算法的性能，選取了三組不同數量的工人任務實例集進行模擬，分別為data1：m=10，n=50；data2：m=20，n=100；data3：m=30，n=150。具體實驗參數的值和范圍見表1。

3.2 實驗結果分析

1）解集分布

圖8展示了DCMEA與對比算法在三個實例集上獲得的MCS任務分配解集所對應的UW和UP值分布。結果顯示，DCMEA明顯優于對比算法，能夠獲得更高的求解精度。DCMEA的UW和UP值分布也更加均勻和廣泛，因此能夠為平臺提供更加多元化的MCS任務分配方案。

2）IGD和HV指標

算法在實例上獨立運行30次，得到反向世代距離（IGD）［26］和超體積（HV）［27］的平均值和標準差，如表2、3所示。表中括號的數字為標準差。IGD評價指標可以綜合評價算法的收斂性和多樣性，IGD指標越小，算法的收斂性和多樣性越好。HV指標表示所獲得的非支配解集在目標空間上的覆蓋范圍，HV值越大，說明算法的解集覆蓋面越寬、分布越均勻，越接近真實Pareto前沿。

表2中，DCMEA的IGD平均值和標準差均優于其他四種對比算法，表明DCMEA求解任務分配模型能夠獲得優于對比算法的精度，同時在30次運行中得到的任務分配結果波動不大，因此具有更好的穩定性。從數據集data1到data3，隨著實例復雜性增加，DCMEA的IGD值與其他算法的IGD差值越大。說明DCMEA隨著實例復雜增加能夠獲取比其他算法更優的任務分配解集。表3顯示DCMEA的HV平均值均優于對比算法，說明DCMEA得到的任務分配解集精度更高，且具有更好的多樣性。同樣，DCMEA隨著實例復雜增加能夠獲取比其他算法更優的任務分配解集。

3）運行時間

算法在實例上獨立運行30次，得到運行時間的平均值和標準差，如表4所示。DCMEA在較為復雜的實例data2和data3上運行時間為最短，在data1上的運行時間只比DEAGNG略長。說明DCMEA總體上運行時間短于對比算法，在解決復雜問題上更能顯示其優勢。

4）IGD和HV收斂曲線

圖9、10展示了算法在data1上迭代5萬次的IGD、HV的收斂曲線。DCMEA的收斂曲線在IGD上快速下降，并到達其他曲線下面，最終達到最小值。DCMEA的收斂曲線在HV上快速上升，并到達其他曲線上面，最終達到最大值。說明DCMEA的收斂速度明顯快于對比算法，在迭代早期能較快地找到優秀的任務分配解集，且在迭代后期也不易陷入局部最優，最終收斂精度也優于其他算法。

上述實驗驗證了DCMEA在求解異構效用MCS任務分配問題具有優于對比算法的收斂精度、收斂速度和解的多樣性。DCMEA表現更優的主要原因與算法設計所采用的技術有關。首先引入隨機加權貪婪初始化策略，生成優勢解來初始化種群，從而能夠引導種群朝著最優解的方向進化。此外，隨機的權重和任務分配順序保證了初始種群的多樣性。雙種群競爭機制把種群劃分為兩個子種群，每個子種群根據不同的策略更新種群個體。能夠在進化過程中保持種群的多樣性，使得種群不易陷入局部最優，增加了種群的收斂性精度和速度。最后，算法中所設計的修復算子使無效解滿足實際問題的約束條件，保留了其中的有用信息，進一步提升了種群的收斂性和多樣性。

3.3 策略有效性分析

DCMEA結合本章MCS任務分配模型的特點，在進化算法的基礎上設計了隨機加權貪婪初始化、雙種群競爭搜索以及修復算子等策略。其中修復算子使個體能夠滿足約束條件，隨機加權貪婪初始化、雙種群競爭搜索增強了算法的求解性能。為驗證隨機加權貪婪初始化策略和雙種群競爭搜索策略對算法性能提升的有效性，將DCMEA中初始化策略改為隨機初始化得到DCMEAR算法，同時將DCMEA改為在單種群上采用順序交叉和兩點交換得到SMEA算法，并與DCMEA進行對比。

1）解集分布

圖11展示了在三個不同數據實例集上DCMEAR、SMEA和DCMEA獲得的MCS任務分配解集所對應的UW和UP值分布。

結果顯示，DCMEA在迭代過程中可以找到更加優越的解集。SMEA的解集分布差于另外兩種算法，說明雙種群競爭進化策略有效地改進了傳統進化算法種群單一、容易陷入局部最優的問題。DCMEAR獲得解集的UW和UP值隨著數據實例集的增大越來越差，這表明隨著任務分配的復雜度的逐漸增加，較好的初始解能夠引導種群的搜索，增加算法的尋優性能。

2）IGD和HV指標

表5、6展示了三種算法IGD、HV指標的平均值和標準差，每個算法運行30次，優異的值加粗顯示。可以看出，DCMEA的IGD、HV值優于其他對比算法，進一步表明DCMEA的改進策略有效地提升了求解任務分配模型的精度和性能。

3.4 模型有效性分析

本文綜合考慮了工人的信譽異質性和不同工人對任務所需數據的熟練程度對任務分配的影響，結合信譽指數和任務熟練指數設計了異構效用機制。為說明異構效用機制對任務分配的影響，將本文模型與只考慮工人信譽和只考慮任務熟練程度的兩種模型進行對比。圖12展示了在data1上不同模型采用DCMEA算法生成的任務分配方案集的平均工人收益和平臺收益。由圖可知，本文模型能夠找到UW和UP平均值更為均衡的方案，同時UW與UP值的和也略高于其他模型，驗證了本文異構效用機制的有效性。

4 結束語

本文引入了信譽指數和任務熟練指數來描述工人和任務的異質性，構建了最大化工人異構效用和最大化平臺異構效用的MCS多目標異構效用任務分配模型。為了求解該模型，通過引入隨機貪婪初始化、雙種群競爭進化、修復算子等技術設計了一種雙種群競爭的多目標進化算法DCMEA。通過在解集分布、IGD和HV指標、運行時間上的實驗，證明DCMEA能夠在求解異構效用MCS多目標任務分配問題中獲得良好的收斂精度、速度和穩定性，并且在復雜的環境中依然能夠獲得較好的任務分配結果。在后面的工作中，可以考慮在任務分配中對工人的位置進行隱私保護，減少工人參與任務的顧慮、激發積極性，從而可以招募到更多優質的工人。

參考文獻：

［1］Guo Bin，Wang Zhu，Yu Zhiwen，et al.Mobile crowd sensing and computing：the review of an emerging human-powered sensing paradigm［J］.ACM Computing Surveys，2015，48（1）：1-31.

［2］Liu Yutong，Kong Linghe，Chen Guihai.Data-oriented mobile crowdsensing：a comprehensive survey［J］.IEEE Communications Surveys & Tutorials，2019，21（3）：2849-2885.

［3］Sun Wen，Li Qiang，Tham C K.Wireless deployed and participatory sensing system for environmental monitoring［C］//Proc of the 11th Annual IEEE International Conference on Sensing，Communication，and Networking.Piscataway，NJ：IEEE Press，2014：158-160.

［4］Coric V，Gruteser M.Crowdsensing maps of on-street parking spaces ［C］//Proc of IEEE International Conference on Distributed Computing in Sensor Systems.Piscataway，NJ：IEEE Press，2013：115-122.

［5］Guo Bin，Chen Huihui，Yu Zhiwen，et al.FlierMeet：a mobile crowdsensing system for cross-space public information reposting，tagging，and sharing［J］.IEEE Trans on Mobile Computing，2015，14（10）：2020-2033.

［6］Alemdar H，Ersoy C.Wireless sensor networks for healthcare：a survey［J］.Computer Networks，2010，54（15）：2688-2710.

［7］Capponi A，Fiandrino C，Kantarci B，et al.A survey on mobile crowdsensing systems：challenges，solutions and opportunities［J］.IEEE Communications Surveys & Tutorials，2019，21（3）：2419-2465.

［8］Zhang Lichen，Ding Yu，Wang Xiaoming，et al.Conflict-aware participant recruitment for mobile crowdsensing［J］.IEEE Trans on Computational Social Systems，2020，7（1）：192-204.

［9］Ni Jianbing，Zhang Kuan，Xia Qi，et al.Enabling strong privacy pre-servation and accurate task allocation for mobile crowdsensing［J］.IEEE Trans on Mobile Computing，2020，19（6）：1317-1331.

［10］Song Zheng，Liu Chiharold，Wu Jie，et al.QoI-aware multitask-oriented dynamic participant selection with budget constraints［J］.IEEE Trans on Vehicular Technology，2014，63（9）：4618-4632.

［11］Wang Jiangtao，Wang Yasha，Zhang Daqing，et al.Fine-grained multi-task allocation for participatory sensing with a shared budget［J］.IEEE Internet of Things Journal，2016，3（6）：1395-1405.

［12］Li Xin，Zhang Xinglin.Multi-task allocation under time constraints in mobile crowdsensing［J］.IEEE Trans on Mobile Computing，2021，20（4）：1494-1510.

［13］Ji Jianjiao，Guo Yinan，Gong Dunwei，et al.Evolutionary multi-task allocation for mobile crowdsensing with limited resource［J］.Swarm and Evolutionary Computation，2021，63：100872.

［14］蔣偉進，張婉清，陳萍萍，等.基于IWOA群智感知中數量敏感的任務分配方法［J］.電子學報，2022，50（10）：2489-2502.（Jiang Weijin，Zhang Wanqing，Chen Pingping，et al.Quantity sensitive task allocation method based on IWOA in group intelligence perception［J］.Acta Electronica Sinica，2022，50（10）：2489-2502.）

［15］楊桂松，吳笑天，高麗，等.面向單任務質量保障的移動群智感知任務分配［J］.計算機工程，2022，48（9）：45-54.（Yang Guisong，Wu Xiaotian，Gao Li，et al.Task allocation towards individual task quality assurance in mobile crowd sensing［J］.Computer Enginee-ring，2022，48（9）：45-54.）

［16］Estrada R，Mizouni R，Otrok H，et al.A crowd-sensing framework for allocation of time-constrained and location-based tasks［J］.IEEE Trans on Services Computing，2020，13（5）：769-785.

［17］Ji Jianjiao，Guo Yinan，Gong Dunwei，et al.MOEA/D-based participant selection method for crowdsensing with social awareness［J］.Applied Soft Computing，2019，87：105981.

［18］Li Mingchu，Gao Yuan，Wang Mingliang，et al.Multi-objective optimization for multi-task allocation in mobile crowd sensing［J］.Procedia Computer Science，2019，155：360-368.（下轉第169頁）

（上接第164頁）

［19］Shen Xiaoning，Chen Qingzhou，Pan Hongli，et al.Variable speed multi-task allocation for mobile crowdsensing based on a multi-objective shuffled frog leaping algorithm［J］.Applied Soft Computing，2022，127：109330.

［20］Ren Ju，Zhang Yaoxue，Zhang Kuan，et al.SACRM：social aware crowdsourcing with reputation management in mobile sensing［J］.Computer Communications，2015，65：55-65

［21］Wu Shengnan，Wang Yingjie，Tong Xiangrong.Multi-objective task assignment for maximizing social welfare in spatio-temporal crowdsour-cing［J］.China Communications，2021，18（11）：11-15.

［22］De Farias L R C，Araújo A F R.A decomposition-based many-objective evolutionary algorithm updating weights when required［J］.Swarm and Evolutionary Computation，2022，68：100980.

［23］Tian Ye，Zhang Xingyi，Cheng Ran，et al.Guiding evolutionary multi-objective optimization with generic front modeling［J］.IEEE Trans on Cybernetics，2020，50（3）：1106-1119.

［24］Liu Yiping，Ishibuchi H，Masuyama N，et al.Adapting reference vectors and scalarizing functions by growing neural gas to handle irregular pareto fronts［J］.IEEE Trans on Evolutionary Computation，2020，24（3）：439-453.

［25］Yang Dingqi，Zhang Daqing，Zheng V W，et al.Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2015，45（1）：129-142.

［26］Bosman P，Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms［J］.IEEE Trans on Evolutionary Computation，2003，7（2）：174-188.

［27］Zitzler E，Thiele L.Multi-objective evolutionary algorithms：a comparative case study and the strength pareto approach［J］.IEEE Trans on Evolutionary Computation，1999，3（4）：257-271.