任務(wù)和參與者匹配意愿規(guī)則約束下的移動群智感知多任務(wù)分配

摘 要：當(dāng)前，大部分移動群智感知（MCS）多任務(wù)分配方法僅考慮時間約束，因忽略任務(wù)、參與者雙方匹配意愿，難以保證真實場景下的任務(wù)接受率，無法最大化平臺利潤。為解決上述問題，提出了一種引入任務(wù)、參與者雙方偏好的MCS任務(wù)分配算法，稱為免疫遺傳鯨優(yōu)算法（IGWOA）。該算法基于鯨魚優(yōu)化算法的智能搜索機制解決MCS任務(wù)分配的資源配置問題，并在搜索、包圍獵物階段分別引入免疫遺傳方法中的交叉、免疫思想，增加任務(wù)分配策略的多樣性、提高解集的質(zhì)量，在氣泡網(wǎng)捕食階段結(jié)合變異思想提升算法的局部搜索能力，實現(xiàn)了快速收斂和最優(yōu)任務(wù)分配策略生成。實驗結(jié)果表明，IGWOA在不同數(shù)據(jù)規(guī)模下的平臺利潤、任務(wù)分配率和參與者平均分配任務(wù)數(shù)量指標(biāo)上優(yōu)于基線方法，且在算法時間復(fù)雜度方面表現(xiàn)良好，證明其可有效解決時間和匹配意愿規(guī)則雙重約束的MCS多任務(wù)分配問題。

關(guān)鍵詞：移動群智感知；多任務(wù)分配；匹配意愿；鯨魚優(yōu)化算法

中圖分類號：TP393"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號：1001-3695（2025）04-011-1050-08

doi： 10.19734/j.issn.1001-3695.2024.08.0321

Multi-task allocation under task and participant matching willingness rules constraints in mobile crowdsensing

Yang Kaicheng， Zhang Xin， Hu Jiahao， Zhou Chaoran， Li Zerui

（College of Computer Science amp; Technology， Changchun University of Science amp; Technology， Changchun 130022， China）

Abstract：Currently， most mobile crowdsensing （MCS） multi-task allocation methods only consider time constraints， neglecting the matching willingness of tasks and participants. This makes it hard to guarantee the task acceptance rate in real scenarios and maximize the platform’s profit. To solve this， this paper proposed an MCS task assignment algorithm introducing task and participant preferences， called immune genetic whale optimization algorithm （IGWOA） . The algorithm used the intelligent search mechanism of whale optimization algorithms to solve the resource allocation problem in MCS task allocation. It introduced cross and immunity ideas from immune genetic methods in the search and encircling prey stages to increase strategy diversity and solution quality. In the bubble net predation stage， it combined the mutation idea to enhance local search ability. It achieved fast convergence and generated the optimal assignment strategy. The experimental results show that IGWOA outperforms the baseline method in terms of platform profits， task assignment rates， and average task assignment numbers for participants under various data scales. And it also has good algorithmic time complexity， which proves that it can effectively solve the MCS multi-task allocation problem with dual constraints of time and matching willingness rules.

Key words：mobile crowdsensing; multi-task allocation; matching willingness; whale optimization algorithm

0 引言

在智能移動終端日益普及的背景下，移動群智感知（MCS）作為一種新興的感知范式應(yīng)運而生，其以配備移動終端的流動人群為感知單元，以獲取大規(guī)模多模態(tài)數(shù)據(jù)。目前，MCS廣泛應(yīng)用在交通管理［1］、環(huán)境監(jiān)測［2］、公共安全［3］等場景，展現(xiàn)出低成本、高泛在、靈活便捷的性能優(yōu)勢［4］。MCS任務(wù)分配主要有任務(wù)請求者、MCS平臺和參與者三種角色。任務(wù)請求者負(fù)責(zé)向MCS平臺發(fā)布任務(wù)需求并支付相應(yīng)報酬；MCS平臺負(fù)責(zé)將任務(wù)需求合理分配給移動參與者；參與者執(zhí)行任務(wù)并通過平臺獲得報酬［5］。可以預(yù)見，隨著技術(shù)革新和需求擴展，未來任務(wù)、參與者數(shù)量將愈發(fā)增多，合理分配MCS任務(wù)以滿足各方期望效益是保證MCS平臺順利運營的關(guān)鍵。

針對MCS任務(wù)合理分配這一核心問題，研究人員已開展大量工作。早期工作主要關(guān)注于單任務(wù)分配，即每次只給參與者分配單項任務(wù)。例如，文獻(xiàn)［6］通過CrowdRecruiter框架減少激勵成本，文獻(xiàn)［7］通過離線與在線任務(wù)分配算法優(yōu)化感知成本。隨著任務(wù)數(shù)量不斷增加，單任務(wù)分配策略受限于平臺資源，難以保證任務(wù)執(zhí)行效率和期望效益。參與者若想獲取多個任務(wù)利潤，需在有限時間內(nèi)承擔(dān)較大累積行程的任務(wù)［8］。為緩解此低效影響，一些工作開始關(guān)注時間約束下的多任務(wù)分配，即生成策略同時分配給參與者多個任務(wù)。文獻(xiàn)［8～10］基于任務(wù)和參與者的時間有效性設(shè)計任務(wù)分配方法，提升分配效率。然而實際中的平臺、參與者是理性的，平臺不招募不符任務(wù)需求的參與者，參與者可拒絕接受不感興趣的任務(wù)。所以生成任務(wù)分配策略時，只考慮任務(wù)和參與者的時間，忽視雙方匹配意愿，會發(fā)生參與者不接受任務(wù)從而造成平臺資源浪費、利潤降低的情況［11］。針對此情況，為提高任務(wù)分配穩(wěn)定性，一些工作考慮任務(wù)需求和參與者偏好對分配策略的影響。文獻(xiàn)［12，13］分別通過延遲接受策略和多目標(biāo)進(jìn)化算法，優(yōu)化平臺與參與者效用，增強任務(wù)分配效能。此外，MCS多任務(wù)分配問題已被證實為NP-complete問題，隨著問題規(guī)模的擴大，無法在多項式時間內(nèi)求解［8］。因此，一些工作利用元啟發(fā)式優(yōu)化算法（如遺傳算法［14］、鯨魚優(yōu)化算法［15］等）生成任務(wù)分配策略。然而，在復(fù)雜的任務(wù)分配場景中，這些任務(wù)分配算法不具備兼顧全局和局部的尋優(yōu)能力，其探索問題最優(yōu)解集的能力仍具有提升空間。

綜上所述，為優(yōu)化平臺利潤，生成MCS任務(wù)分配策略需著重考慮兩個關(guān)鍵點：a）關(guān)注任務(wù)、參與者的時間和匹配意愿；b）提高任務(wù)分配算法的尋優(yōu)能力。為此，本文開展任務(wù)和參與者匹配意愿規(guī)則約束下的MCS多任務(wù)分配研究工作，主要貢獻(xiàn)如下：

a）在時間約束下的多任務(wù)分配模型中，引入一種考慮任務(wù)和參與者雙方偏好的匹配意愿規(guī)則，旨在構(gòu)建最大化平臺利潤的模型。同時，基于量化加權(quán)分析法，明確了該規(guī)則下匹配意愿及參與者獲取任務(wù)報酬的計算方式，以評估任務(wù)和參與者的適配性，保證參與者間的公平性。

b）為解決上述雙重約束下的MCS任務(wù)分配問題，提出了一種引入任務(wù)、參與者雙方偏好的免疫遺傳鯨優(yōu)算法（immune genetic whale optimization algorithm， IGWOA）。其基于鯨魚優(yōu)化算法（whale optimization algorithm， WOA）的智能搜索機制，融合免疫遺傳方法中的交叉、免疫和變異思想，對WOA的搜索、包圍獵物和氣泡網(wǎng)捕食階段進(jìn)行系統(tǒng)性改進(jìn)，以兼顧算法的全局和局部尋優(yōu)能力，實現(xiàn)了最優(yōu)任務(wù)分配策略的生成。

1 匹配意愿規(guī)則約束下的多任務(wù)分配模型

本章在時間約束下的多任務(wù)分配模型中引入匹配意愿規(guī)則，建立了最大化平臺利潤的多任務(wù)分配模型。模型涉及主要符號見表1，其他符號詳見內(nèi)容。

1.1 模型描述

MCS包括了一個由服務(wù)器集群構(gòu)建的中心平臺、若干任務(wù)請求者和參與者，其多任務(wù)分配模型見圖1。任務(wù)分配前，平臺持續(xù)等待請求者發(fā)送的任務(wù)需求和參與者上傳的個人信息。任務(wù)分配過程中，平臺針對待分配任務(wù)和候選參與者信息進(jìn)行分析，并計算出雙方匹配意愿，通過匹配意愿閾值評估適配性。若匹配意愿達(dá)到或超過閾值且參與者可在預(yù)期時間內(nèi)/任務(wù)截止時間前完成任務(wù)，即判斷雙方彼此適配，可分配任務(wù)給參與者。任務(wù)執(zhí)行結(jié)束后，平臺根據(jù)參與者上傳的感測數(shù)據(jù)判斷任務(wù)完成情況，從請求者獲取平臺報酬，向參與者支付報酬，獲取利潤。

在此模型中，任務(wù)請求者發(fā)布的任務(wù)集合表示為T={t1，…，tj，…，tn}，其中n表示感測任務(wù)數(shù)量。第j個任務(wù)tj的信息簡檔表示為Prtj={tlj，tej，tdj，Ij}，其中tlj表示tj位置；tej表示tj在平臺的有效時長；tdj表示tj要求感測時長；Ij表示tj重要性。參與者集合表示為P={p1，…，pi，…，pm}，其中m表示參與者數(shù)量。第i名參與者pi的信息簡檔表示為Prpi={pli，pei，pari，pri，psi，pski，prbi，Ei，Qi}，其中pli表示pi的初始位置；pei表示pi的預(yù)期工作時長；pari表示pi以pli為圓心的理想活動半徑，pri表示pi的聲譽值；psi表示pi的社交能力；pski={pski1，…，pskij，…，pskin}表示pi各任務(wù)熟練度集合，pskij表示pi對任務(wù)tj的熟練度；prbi、Ei和Qi分別表示pi設(shè)備的剩余電量、計算資源和數(shù)據(jù)傳輸效率。

平臺分配給pi的任務(wù)數(shù)量為ki的有序集合表示為Tpi={t1，…，tj，…，tki}T。定義Timepi，tj，Tpi表示pi完成集合Tpi中tj后的累積消耗時長，其由pi從初始位置pli移動到任務(wù)位置tlj的移動時長和tj的所有前置任務(wù)（包括tj）的感測時長組成，見式（1）。

Time（pi，tj，Tpi）=Timei（pli，tlj）+tdjj=1Timei（pli，tl1）+∑jj′=2Timea（tlj′－1，tlj′）+∑jj′=1tdjjgt;1（1）

其中：Timea（a，b）表示參與者從位置a移動到位置b的時長。當(dāng)參與者pi和任務(wù)tj滿足時間約束，即Time（pi，tj，Tpi）≤pei且Time（pi，tj，Tpi）≤tej，表示參與者pi可以在pei時間內(nèi)完成任務(wù)tj，并且任務(wù)tj可以在tej時間內(nèi)被參與者pi完成。

任務(wù)tj和參與者pi的匹配意愿表示為mwij，平臺設(shè)置的匹配意愿閾值表示為mwt。當(dāng)任務(wù)tj和參與者pi滿足匹配意愿規(guī)則約束，即mwij≥mwt，表示雙方符合平臺匹配要求。參與者pi和任務(wù)tj的匹配狀態(tài)表示為xij，當(dāng)平臺將任務(wù)tj分配給參與者pi時，xij=1，否則xij=0。若平臺成功將pi執(zhí)行任務(wù)tj的感測數(shù)據(jù)反饋給請求者并獲得報酬trij，pi將獲得平臺給予的報酬prij，則平臺最終獲得的利潤可以表示為ppij=trij－prij。

1.2 匹配意愿和任務(wù)報酬計算方法

本小節(jié)采用量化加權(quán)分析方法，通過分析任務(wù)、參與者雙方偏好及任務(wù)執(zhí)行成本的影響因素，明確了在匹配意愿規(guī)則下如何計算匹配意愿和參與者完成任務(wù)所獲得的報酬。

1.2.1 匹配意愿計算方法

任務(wù)tj和參與者pi的匹配意愿mwij分為tj對pi的偏好mptij和pi對tj的偏好mppij兩部分，具體如式（2）所示。

其中：式（16）為目標(biāo)優(yōu)化函數(shù)，PP（x）表示平臺的任務(wù)分配利潤函數(shù)；式（17）（18）為時間約束；式（17）表示參與者pi需在工作時長pei內(nèi)完成平臺分配的任務(wù)集合Tpi，即pi完成集合Tpi中tki后的累積時長Time（pi，tki，Tpi）不能超過其工作時長pei；式（18）表示集合Tpi中的tj需在有效期內(nèi)被pi完成，即pi完成集合Tpi中tj后的累積時長Time（pi，tj，Tpi）不能超過任務(wù)有效時長tej；式（19）為匹配意愿規(guī)則約束，即tj和pi的匹配意愿mwij需達(dá)到或超過平臺預(yù)設(shè)的閾值mwt；式（20）表示tj只能由一個參與者完成；式（21）表示tj最多只能分配給pi一次。

2 MCS多任務(wù)分配模型求解算法

考慮在匹配意愿規(guī)則約束下的MCS多任務(wù)分配問題屬于NP-complete問題，并鑒于WOA具有收斂速度快、全局搜索能力強的特點［17］，本文基于WOA的智能搜索機制去解決任務(wù)分配中與任務(wù)、參與者偏好有關(guān)的資源配置問題。同時，為兼顧算法的全局和局部尋優(yōu)能力，在WOA的搜索、包圍獵物和氣泡網(wǎng)捕食階段融入了免疫遺傳方法中的交叉、免疫和變異思想，提出了名為免疫遺傳鯨優(yōu)算法（IGWOA），具體見算法1。

IGWOA基于任務(wù)集合T和參與者集合P，使用數(shù)組結(jié)構(gòu)對表示任務(wù)分配策略的鯨魚個體進(jìn)行編碼，并采用隨機貪婪策略生成表示初始任務(wù)分配策略的種群SP。接著，通過選擇合適個體制造疫苗Cv。之后，基于WOA中的特定策略（引入向量系數(shù)A）增強算法的全局搜索能力和局部搜索精度，見式（22）。

A=2a×r－a

（22）

其中：r為［0，1］均勻分布產(chǎn)生的隨機數(shù)；a表示隨迭代次數(shù)time從2線性減小到0的收斂因子，見式（23）。

a=2－2time/Iter

（23）

其中：Iter表示最大迭代次數(shù)。在每次迭代遍歷個體時，生成隨機數(shù)p。當(dāng)plt;0.4時，若|A|≥1，IGWOA處于搜索獵物階段，對個體進(jìn)行隨機交叉操作，以增加個體多樣性；若|A|lt;1，IGWOA處于包圍獵物階段，對個體注射疫苗，以提高解集的質(zhì)量。當(dāng)p≥0.4時，IGWOA處于氣泡網(wǎng)捕食階段，對個體執(zhí)行變異操作，以提升局部搜索能力，發(fā)現(xiàn)潛在更優(yōu)解。最后，利用修復(fù)算子修復(fù)不滿足約束的無效解，以保留有效信息。循環(huán)執(zhí)行上述種群進(jìn)化過程Iter次，輸出最優(yōu)個體。

算法1 IGWOA

輸入：參與者集合P；任務(wù)集合T；種群大小N；最大迭代次數(shù)Iter。

輸出：任務(wù)分配解集。

根據(jù)算法2初始化任務(wù)分配解集種群SP；

將種群SP中適應(yīng)度值最優(yōu)個體Cbest選定為疫苗Cv；

循環(huán)迭代次數(shù)Iter，操作；

將當(dāng)前種群SP中適應(yīng)度值最優(yōu)的個體Ctop1與適應(yīng)度值第二大的個體Ctop2交叉生成候選疫苗Cvc；

比較上一代疫苗C′v、個體Ctop1、候選疫苗Cvc的適應(yīng)度值，將適應(yīng)度值最高的個體作為當(dāng)前一代疫苗Cv；

依據(jù)式（23）更新收斂因子a；

循環(huán)種群SP中每一條個體，操作；

依據(jù)式（22）更新向量系數(shù)A；

如果隨機數(shù)plt;0.4，并且|A|≥1，則將當(dāng)前種群SP中第j個個體Cj與隨機個體進(jìn)行交叉，得到下一代種群NP中第j個個體Cj；

如果隨機數(shù)plt;0.4，并且|A|lt;1，則將當(dāng)前種群SP中第j個個體Cj與當(dāng)前一代疫苗Cv進(jìn)行交叉，得到下一代種群NP中第j個Cj；

如果隨機數(shù)p≥0.4，則將當(dāng)前種群SP中第j個個體Cj進(jìn)行變異操作，得到下一代種群NP中第j個個體Cj；

循環(huán)結(jié)束；

根據(jù)算法3將下一代種群NP中不滿足約束的無效解修復(fù)成有效解，并依據(jù)種群NP更新當(dāng)前代種群SP；

循環(huán)結(jié)束；

輸出種群SP中表示最優(yōu)任務(wù)分配策略的最優(yōu)個體Cbest。

2.1 鯨魚個體表示與適應(yīng)度評價

鯨魚個體的數(shù)組結(jié)構(gòu)如圖2所示。每條個體由代表m名參與者的基因片段組成。基因片段索引代表參與者ID，其由若干個基因組成。每個基因代表分配給參與者的任務(wù)ID。根據(jù)約束不等式（17）～（20），鯨魚個體分為滿足所有約束條件的有效個體和至少不滿足任何一個約束條件的無效個體。

個體適應(yīng)度的評估標(biāo)準(zhǔn)為平臺利潤，適應(yīng)度值越高，表示利潤越高。假定一個種群SP=（C1，…，Cl，…，Ck），其中第l個個體Cl適應(yīng)度函數(shù)f（Cl）見式（24）。

f（Cl）=∑nj=1ppjxj

（24）

其中：ppj表示完成任務(wù)tj平臺獲得的利潤；xj表示任務(wù)tj的分配狀態(tài)；xj=1表示任務(wù)tj被分配；xj=0表示任務(wù)tj未被分配。

2.2 種群初始化

為保證任務(wù)分配策略多樣性，采用隨機貪婪策略生成具有N條有效個體的初代種群，詳見算法2。首先，初始化一個長度為m的數(shù)組作為空個體，并創(chuàng)建候選參與者集合PS和任務(wù)集合TS。接著，隨機選取參與者和任務(wù)，以生成有效的基因片段，直至參與者集合為空。將過程循環(huán)迭代N次，完成種群初始化。

算法2 隨機貪婪策略生成初始任務(wù)分配解集種群

輸入：參與者集合P；任務(wù)集合T；種群大小N。

輸出：初始化任務(wù)分配解集種群SP。

a）循環(huán)迭代次數(shù)N，操作；

b）生成一個沒有任務(wù)序號的個體Cq；

c）依據(jù)參與者集合P與任務(wù)集合T分別創(chuàng)建候選參與者集合PS、未分配任務(wù)集合TS；

d）隨機從候選參與者集合PS中選取一個參與者pi；

e）隨機從未分配任務(wù)集合TS中選取一個任務(wù)tj；

f）將任務(wù)tj附加到表示參與者pi的基因片段Cpi的結(jié)尾；

g）如果基因片段Cpi有效，更新個體Cq，從集合TS刪除任務(wù)tj；

h）如果基因片段Cpi無效，則將任務(wù)tj從基因片段Cpi中刪除；

i）重復(fù)執(zhí)行步驟e）～h）直到集合TS中的任務(wù)不能使得基因片段Cpi有效；

j）將參與者pi從候選參與者集合PS中刪除；

k）重復(fù)執(zhí)行步驟d）～ j）直到候選參與者集合PS為空集；

l）循環(huán)結(jié)束；

m）輸出初始的任務(wù)分配解集種群SP。

2.3 交叉算子與變異算子

當(dāng)兩個個體執(zhí)行交叉操作時，IGWOA將選擇父本中適應(yīng)度較高的基因片段遺傳給新個體，如圖3所示。

當(dāng)一個個體執(zhí)行變異操作時，IGWOA將隨機選擇此個體中含有任務(wù)序號的兩個基因片段，并在兩個基因片段分別隨機選取一個基因進(jìn)行交換，以產(chǎn)生突變個體，如圖4所示。

2.4 免疫算子

IGWOA基于免疫原理和疫苗方法構(gòu)建免疫算子，以確保個體中攜帶的優(yōu)質(zhì)基因片段可穩(wěn)定遺傳給后代。IGWOA的免疫操作分為疫苗制作和疫苗注射兩個步驟，如圖5所示。首先，在每次迭代時將適應(yīng)度值最高的前兩個個體Ctop1和Ctop2執(zhí)行交叉和修復(fù)操作以構(gòu)建一個有效個體，并將其作為候選疫苗Cvc。然后，從最高適應(yīng)度個體Ctop1、候選疫苗Cvc和上一代疫苗C′v中選取適應(yīng)度值最高的個體作為新一代疫苗Cv，完成疫苗制作操作，以保留種群中的優(yōu)質(zhì)基因片段。最后，使新一代疫苗與被選擇的個體交叉，完成疫苗注射操作，以遺傳優(yōu)質(zhì)基因片段給下一代種群。

2.5 修復(fù)算子

IGWOA采用修復(fù)算子將無效個體轉(zhuǎn)換為有效個體，以解決在進(jìn)化過程中因問題約束而產(chǎn)生的無效個體問題，詳見算法3。首先，確認(rèn)個體C的每個基因片段Cpi的任務(wù)分配解集是否滿足約束條件。若基因片段Cpi不滿足約束條件，則將基因片段Cpi的任務(wù)序列中滿足約束條件并且任務(wù)不重復(fù)的最大任務(wù)子集作為新的基因片段Cpi。然后，引入適者生存思想，將任務(wù)tj保留在具有相同任務(wù)tj的基因片段集合CGS中適應(yīng)度最高的基因片段CGSbest中，并移除其他基因片段中的任務(wù)tj。最后，將未分配的任務(wù)tj隨機分配給有足夠時間執(zhí)行任務(wù)的參與者。

算法3 修復(fù)算子

輸入：一個無效個體C。

輸出：一個有效個體Cnew。

a）循環(huán)迭代個體C中每個基因片段Cpi，操作；

b）若基因片段Cpi中參與者pi與任務(wù)序列中任意任務(wù)的匹配不滿足約束條件或基因片段Cpi中重復(fù)出現(xiàn)一個任務(wù)，則將基因片段Cpi任務(wù)序列中滿足約束條件且任務(wù)不重復(fù)的最大任務(wù)子集作為新的基因片段Cpi；

c）循環(huán)結(jié)束；

d）循環(huán)迭代任務(wù)集合T中的每一個任務(wù)，操作；

e）將個體C中包含任務(wù)tj的所有基因片段組成基因片段集合CGS；

f）保留集合CGS中適應(yīng)度最高的基因片段CGSbest，將任務(wù)tj從其余基因片段中刪除，更新個體C；

g）循環(huán)結(jié)束；

h）循環(huán)迭代個體C中每個基因片段Cpi，操作；

i）依據(jù)個體C，將任務(wù)集合T中未分配的任務(wù)組成未分配任務(wù)集合Tc；

j）隨機在未分配任務(wù)集合Tc中選取任務(wù)tj；

k）如果任務(wù)tj附加到基因片段Cpi尾部后基因片段Cpi仍有效，則將任務(wù)tj附加到基因片段Cpi尾部，更新個體C；

l）從未分配任務(wù)集合Tc中刪除任務(wù)tj；

m）重復(fù)執(zhí)行步驟j）～l）直到未分配任務(wù)集合Tc為空；

n）循環(huán)結(jié)束；

o）輸出有效個體Cnew。

2.6 算法的時間復(fù)雜度

在IGWOA中，設(shè)定種群的個體數(shù)量N和最大迭代次數(shù)Iter為常數(shù)參數(shù)。假定任務(wù)集合T和參與者集合P分別有n個任務(wù)和m名參與者，則種群初始化、交叉算子、變異算子的時間復(fù)雜度分別約為O（N×m×n）、O（m）、O（1），免疫算子中疫苗制作和疫苗注射操作的時間復(fù)雜度均為O（m）。在修復(fù)算子中，首先遍歷任務(wù)有序集合Tpi的每個任務(wù)，以尋找滿足約束且不重復(fù)的最大有序子集，時間復(fù)雜度小于O（m×n）。其次，修復(fù)個體中多次分配的任務(wù)，時間復(fù)雜度約為O（n）。最后，在任務(wù)數(shù)量小于n的未分配任務(wù)集合中選擇任務(wù)并分配給可執(zhí)行參與者，時間復(fù)雜度小于O（m×n）。因此，修復(fù)算子總體時間復(fù)雜度約為 O（m×n）。綜上，IGWOA的時間復(fù)雜度可表示為O（m×n）。

3 實驗

3.1 實驗設(shè)置

3.1.1 實驗環(huán)境

實驗在配備Linux操作系統(tǒng)、Intel Xeon Gold 5218R CPU（@2.10 GHz，80核）、31.0 GiB RAM的機器上運行，采用Python作為開發(fā)語言，并使用PyCharm環(huán)境編寫算法。

3.1.2 實驗數(shù)據(jù)集及模型參數(shù)設(shè)置

本文以構(gòu)建仿真數(shù)據(jù)的方式，模擬真實場景下MCS多任務(wù)分配過程，并為提高研究的客觀性和可靠性，所有數(shù)據(jù)均以量化形式構(gòu)建。具體地，任務(wù)、參與者的感測區(qū)域位置坐標(biāo)（x軸和y軸）設(shè)置為［0，50］。隨機生成參與者集合P，均勻分布任務(wù)集合T于感測區(qū)域內(nèi)。對于參與者pi，其預(yù)期工作時長pei在［6，18］隨機生成，行駛速度為1個單位，且行駛距離等效于行駛時間。對于任務(wù)tj，其有效時長tej、感測要求時長tdj分別在［2，15］、［1，3］隨機生成。請求者向平臺的支付報酬trij在［5，30］隨機生成。基礎(chǔ)成本c0為0.5。其他量化數(shù)據(jù)的參數(shù)設(shè)置詳見表2。此外，為了簡化模型并聚焦匹配意愿規(guī)則對任務(wù)分配的影響，本文設(shè)定了各權(quán)重參數(shù)。具體而言，匹配意愿的兩權(quán)重mww1和mww2、成本水平的兩權(quán)重λ1和λ2以及人工執(zhí)行成本的兩權(quán)重κ1和κ2均設(shè)為0.5，以平衡各因素。對于資源消耗成本，根據(jù)實際重要性，ω1、ω2和ω3分別設(shè)為0.54、0.30和0.16。此設(shè)定不能完全反映實際復(fù)雜性，但為探索分析提供起點，未來研究可依更多數(shù)據(jù)優(yōu)化。

3.1.3 對比算法

本文選取WMTA-GA［14］、 WOA［17］、GA-SA ［18］以及普遍應(yīng)用的隨機分配算法（random allocation algorithm，RAA）與貪婪分配算法（greedy allocation algorithm，GAA）五種基線算法，通過實驗對比分析（50次實驗結(jié)果取平均值）的方式，評價IGWOA的有效性。其中WMTA-GA、GA-SA是近年來基于遺傳算法提出的解決任務(wù)分配問題的目標(biāo)優(yōu)化算法；WOA是適用于解決此類問題的經(jīng)典啟發(fā)式算法；RAA是隨機性任務(wù)分配算法，在滿足條件時隨機分配任務(wù)；而GAA則基于貪婪策略，優(yōu)先將任務(wù)分配給能為平臺帶來最大利潤的參與者。所有算法中均增添修復(fù)算子來處理約束。為公平評估算法性能，本文統(tǒng)一設(shè)定算法參數(shù)來兼顧算法特性與優(yōu)化問題的要求。具體而言，設(shè)置IGWOA、WMTA-GA、WOA、GA-SA的最大迭代次數(shù)為100，種群規(guī)模為50；設(shè)置WMTA-GA、GA-SA的交叉概率為09、變異概率為001；設(shè)置WOA的線性遞減控制參數(shù)為2、螺旋形狀半徑為1、隨機行為系數(shù)為2及螺旋更新常數(shù)為-1。

3.2 評估性能指標(biāo)

本文選取MCS平臺利潤、任務(wù)分配率、參與者平均任務(wù)分配數(shù)量來評價各算法性能表現(xiàn)。MCS平臺利潤反映算法求解效果，高利潤表明求解優(yōu)。任務(wù)分配率反映系統(tǒng)中資源的利用情況，高任務(wù)分配率表明資源利用佳。參與者平均分配任務(wù)數(shù)量反映參與者活躍度，值越高表明參與者參與任務(wù)的活躍性越強。

任務(wù)分配率=成功分配給參與者的任務(wù)數(shù)量總?cè)蝿?wù)數(shù)量

（25）

參與者平均分配任務(wù)數(shù)量=成功分配給參與者的任務(wù)數(shù)量參與者數(shù)量（26）

本文選取任務(wù)、參與者的平均偏好來評估模型有效性，其能反映平臺對雙方需求的關(guān)注程度。偏好值越高表明平臺越能滿足雙方需求，從而提升任務(wù)接受率與平臺利潤。

任務(wù)的平均偏好=所有已分配任務(wù)的偏好值總和成功分配給參與者的任務(wù)數(shù)量

（27）

參與者的平均偏好=被成功分配任務(wù)的參與者的偏好值總和被成功分配任務(wù)的參與者數(shù)量（28）

3.3 對比實驗結(jié)果分析

3.3.1 參與者數(shù)量對MCS任務(wù)分配算法性能影響

為分析參與者數(shù)量對各MCS分配算法性能的影響，設(shè)置實驗參數(shù)如下：任務(wù)數(shù)量n=200、平臺匹配意愿閾值mwt=037、參與者數(shù)量m={20，40，60，80，100，120，140，160，180，200}。圖6為參與者數(shù)量對各算法的平臺利潤、任務(wù)分配率性能影響。觀察發(fā)現(xiàn)，隨著參與者數(shù)量增加，各算法對平臺利潤和任務(wù)分配率的影響均呈現(xiàn)上升趨勢，當(dāng)參與者數(shù)量達(dá)到160時，各算法性能表現(xiàn)收斂趨勢。分析原因為，隨著參與者數(shù)量的增加，約束條件對算法性能的影響逐漸增強，促進(jìn)算法在特定條件下達(dá)到最優(yōu)解。當(dāng)參與者數(shù)量范圍為［20，140］時，相較于各基線算法，IGWOA在平臺利潤和任務(wù)分配率方面表現(xiàn)更好。原因是WMTA-GA、WOA、GA-SA三種算法在求解過程中比較依賴初始種群，并且WMTA-GA、GA-SA主要基于選擇、交叉、變異等操作尋找最優(yōu)解，WOA依據(jù)當(dāng)前最優(yōu)解的位置和鯨魚個體與最優(yōu)解之間的距離，對個體位置更新，從而逼近最優(yōu)解。與這三種算法不同，IGWOA將免疫遺傳方法中的交叉、免疫和變異思想融合在WOA的搜索、包圍獵物和氣泡網(wǎng)捕食階段以兼顧對算法全局和局部搜索能力的提升，因此IGWOA的全局搜索能力優(yōu)于WMTA-GA、WOA、GA-SA。RAA、GAA在任務(wù)規(guī)模較大時，容易陷入局部最優(yōu)解，因此算法性能指標(biāo)表現(xiàn)較差。當(dāng)參與者數(shù)量范圍為［160，180］時，IGWOA在利潤和任務(wù)分配率方面表現(xiàn)優(yōu)于除WMTA-GA的基線算法，與WMTA-GA無顯著差異，分析是因為數(shù)據(jù)集中部分任務(wù)的感測要求苛刻，沒有適合參與者執(zhí)行任務(wù)，IGWOA與WMTA-GA均已生成最優(yōu)分配策略。此外，觀察發(fā)現(xiàn)，相較于WMTA-GA，IGWOA在提升平臺利潤和任務(wù)分配率時具有更快的收斂速度。

隨著參與者數(shù)量逐漸增加到任務(wù)數(shù)量，參與者以更大概率被分配固定數(shù)量任務(wù)，各算法在參與者平均任務(wù)分配數(shù)量方面效果差異不明顯。因此觀察參與者數(shù)量小于任務(wù)數(shù)量時算法在參與者平均分配任務(wù)數(shù)量方面的表現(xiàn)，以評估性能。圖7為參與者數(shù)量m={20，40，60，80，100}時，各算法關(guān)于此性能指標(biāo)的實驗結(jié)果。觀察發(fā)現(xiàn)隨著參與者數(shù)量增加，各算法的參與者平均分配任務(wù)數(shù)量呈現(xiàn)減少趨勢，反映了參與者活躍度降低趨勢。分析是因為在任務(wù)數(shù)量固定時，隨著參與者數(shù)量增加，平臺擁有更多資源完成任務(wù)，算法將自動調(diào)整任務(wù)分配策略，確保每個參與者能承擔(dān)相對合理的任務(wù)數(shù)量以優(yōu)化平臺利潤。隨著參與者數(shù)量增加，IGWOA 全局搜索能力強，相比其他算法優(yōu)勢漸顯，參與者平均任務(wù)分配數(shù)量更高，參與者活躍性更強。

3.3.2 任務(wù)數(shù)量對MCS任務(wù)分配算法性能影響

為分析任務(wù)數(shù)量對各MCS任務(wù)分配算法性能的影響，設(shè)置實驗參數(shù)如下：參與者數(shù)量m=60，平臺匹配意愿閾值mwt=0.37，任務(wù)數(shù)量n={60，80，100，120，140，160，180，200}。圖8展示了任務(wù)數(shù)量對各算法的平臺利潤和任務(wù)分配率性能影響。觀察發(fā)現(xiàn)，隨著任務(wù)數(shù)量增加，各算法對平臺利潤的影響呈現(xiàn)上升趨勢，對任務(wù)分配率的影響呈現(xiàn)下降趨勢。這是因為隨著任務(wù)數(shù)量增加，各算法能夠充分發(fā)揮優(yōu)化作用，通過合理的任務(wù)分配提高平臺利潤。然而每個感知能力有限的參與者需要承擔(dān)的任務(wù)量相應(yīng)增加，當(dāng)任務(wù)數(shù)量超過其承受能力時，任務(wù)分配率下降。在任務(wù)數(shù)量變化時，IGWOA因較強的全局搜索能力使得其在平臺利潤和任務(wù)分配率方面優(yōu)于基線算法。

圖9展示了當(dāng)任務(wù)數(shù)量m={60，80，100，120，140}時，各算法在平臺分配給參與者的平均任務(wù)數(shù)量的情況。觀察發(fā)現(xiàn)，隨著任務(wù)數(shù)量增加，各算法對分配給參與者的平均任務(wù)數(shù)量呈現(xiàn)增加趨勢，側(cè)面呈現(xiàn)了參與者活躍性提高趨勢，且IGWOA的表現(xiàn)仍優(yōu)于基線算法。

3.3.3 數(shù)據(jù)規(guī)模對MCS任務(wù)分配算法性能影響

為排除IGWOA性能優(yōu)勢在上述實驗中的偶然性，本節(jié)實驗擴大了任務(wù)和參與者的數(shù)量。具體實驗參數(shù)如下：參與者數(shù)量m=200，平臺匹配意愿閾值mwt=0.37，任務(wù)數(shù)量n={250，300，350，400，450，500}。圖10展示了IGWOA與基線算法在大規(guī)模數(shù)據(jù)集中任務(wù)數(shù)量變化時MCS平臺利潤、任務(wù)分配率和參與者平均分配任務(wù)數(shù)量的變化情況。從圖10可以看出各算法性能與上述結(jié)果表現(xiàn)的一致，說明IGWOA的性能優(yōu)勢在不同規(guī)模的數(shù)據(jù)集下均保持穩(wěn)定，具有一定的魯棒性。

3.3.4 算法運行耗時分析

利用3.3.3節(jié)中的實驗參數(shù)，分析任務(wù)數(shù)量對算法運行耗時影響。圖11表明任務(wù)數(shù)量的增加會不同程度地增加各算法的運行耗時，其中IGWOA的耗時長于RAA與GAA、短于WMTA-GA、遠(yuǎn)短于WOA與GA-SA。因為IGWOA利用了免疫遺傳方法中的自我調(diào)節(jié)機制，加速算法了的收斂過程，減少不必要的迭代次數(shù)，并一定程度上緩解WOA對參數(shù)的敏感性，所以比WMTA-GA、WOA耗時更短。GA-SA的耗時多在模擬退火算法的退溫操作上，因此耗時更長。而對于RAA、GAA，其采用直接的策略來解決問題，無須在解集空間中進(jìn)行復(fù)雜的搜索和優(yōu)化，相較其他算法耗時更短。綜上，IGWOA在最大化平臺利潤的前提下，運行耗時相對較低，算法時間復(fù)雜度表現(xiàn)良好。

3.4 匹配意愿規(guī)則有效性分析

設(shè)計實驗觀察匹配意愿閾值對各算法性能的影響以及對比各模型性能，以驗證MCS任務(wù)分配模型引入匹配意愿規(guī)則的有效性。

針對匹配意愿閾值對各算法性能的影響，設(shè)置實驗參數(shù)如下：參與者數(shù)量m=60，任務(wù)數(shù)量n=200，匹配意愿閾值mwt={0.37，0.47，0.57，0.67，0.77，0.87}。圖12展示了IGWOA與基線算法隨匹配意愿閾值變化時MCS平臺利潤、任務(wù)分配率和參與者平均分配任務(wù)數(shù)量的變化情況。觀察發(fā)現(xiàn)，隨著匹配意愿閾值提高，各算法對三種性能的影響呈現(xiàn)下降趨勢。分析是隨著匹配意愿閾值增加，大于匹配意愿閾值的任務(wù)和參與者匹配組合的數(shù)量以更大概率減少，導(dǎo)致滿足任務(wù)需求和參與者偏好的參與者和任務(wù)匹配組合數(shù)量減少，任務(wù)不能分配給合適參與者。從整體上看，IGWOA的表現(xiàn)優(yōu)于基線算法。

針對同時考慮時間約束和匹配意愿規(guī)則約束的模型與只考慮時間約束的模型進(jìn)行性能對比實驗。本文將IGWOA應(yīng)用到不同模型中，觀察平臺匹配意愿閾值變化時各模型的任務(wù)、參與者的平均偏好的變化情況。圖13表明同時考慮時間和匹配意愿規(guī)則約束的模型的任務(wù)、參與者的平均偏好值隨著匹配意愿閾值增加而增加，且優(yōu)于只考慮時間約束的模型。說明隨著匹配意愿閾值增加，本文模型可更充分地考慮任務(wù)需求及參與者的偏好，使算法生成的MCS任務(wù)分配策略的穩(wěn)定性增強，提高參與者對任務(wù)的接受率，證明了在模型中引入匹配意愿規(guī)則的有效性。在實際MCS場景中，平臺可根據(jù)具體需求動態(tài)調(diào)整匹配意愿閾值，以控制平臺利潤和任務(wù)分配策略穩(wěn)定均衡。

4 結(jié)束語

針對目前MCS多任務(wù)分配方法忽略任務(wù)、參與者雙方匹配意愿，難以保證任務(wù)接受率，阻礙平臺利潤提高的缺陷，本文在任務(wù)、參與者匹配意愿規(guī)則約束下，建立平臺利潤最大化的任務(wù)分配模型。為生成最優(yōu)任務(wù)分配策略，提出了一種引入任務(wù)、參與者雙方偏好的MCS任務(wù)分配算法IGWOA，通過融入免疫遺傳方法的交叉、免疫和變異思想來強化WOA各搜索階段性能。其中在搜索獵物階段增加了分配策略的多樣性，提高了包圍獵物階段解集的質(zhì)量，并優(yōu)化了氣泡網(wǎng)捕食階段的局部搜索能力，以兼顧全局與局部尋優(yōu)能力。在任務(wù)分配場景不同數(shù)據(jù)規(guī)模下的仿真實驗，驗證了IGWOA在平臺利潤、任務(wù)分配率和參與者平均分配任務(wù)數(shù)量指標(biāo)上優(yōu)于基線方法以及在算法時間復(fù)雜度方面的良好表現(xiàn)。本文在任務(wù)分配中主要將參與者視為獨立個體，未來將進(jìn)一步探討社群因素對任務(wù)分配策略的影響，研究社群內(nèi)部知識共享與任務(wù)分配策略優(yōu)化問題。

參考文獻(xiàn)：

［1］Nandagopal C， Naveen V， Suriya M， et al. Traffic congestion monitoring based on cloud using crowd sensing［C］// Proc of International Conference on Sustainable Computing and Data Communication Systems. Piscataway， NJ： IEEE Press， 2022： 1307-1314.

［2］Dinh T A N， Nguyen A D， Nguyen T T，et al. Spatial-temporal cove-rage maximization in vehicle-based mobile crowdsensing for air quality monitoring［C］// Proc of IEEE Wireless Communications and Networking Conference. Piscataway， NJ： IEEE Press， 2022： 1449-1454.

［3］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.

［4］Guo Bin， Yu Zhiwen， Zhou Xingshe，et al. From participatory sen-sing to mobile crowd sensing［C］// Proc of IEEE International Conference on Pervasive Computing and Communication Workshops. Piscataway， NJ： IEEE Press， 2014： 593-598.

［5］Yang Dejun， Xue Guoliang， Fang Xi，et al. Crowdsourcing to smartphones： incentive mechanism design for mobile phone sensing［C］// Proc of the 18th Annual International Conference on Mobile Computing and Networking. New York： ACM Press， 2012： 173-184.

［6］Zhang Daqing， Xiong Haoyi， Wang Leye，et al. CrowdRecruiter： selecting participants for piggyback crowdsensing under probabilistic coverage constraint［C］// Proc of ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM Press， 2014： 703-714.

［7］Sun Guodong， Wang Yanan， Ding Xingjian， et al. Cost-fair task allocation in mobile crowd sensing with probabilistic users ［J］. IEEE Trans on Mobile Computing， 2019， 20（2）： 403-415.

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

［9］Huang Yang， Chen Honglong， Ma Guoqi，et al. OPAT： optimized allocation of time-dependent tasks for mobile crowdsensing ［J］. IEEE Trans on Industrial Informatics， 2022， 18（4）： 2476-2485.

［10］Wang Liang， Yu Zhiwen， Zhang Daqing，et al. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation ［J］. IEEE Trans on Mobile Computing， 2018， 18（1）： 84-97.

［11］Li Xiaolin， Zhang Lichen， Zhou Meng，et al. Task recommendation based on user preferences and user-task matching in mobile crowdsensing ［J］. Applied Intelligence， 2024， 54（1）： 131-146.

［12］楊桂松， 王不野， 何杏宇. 面向延遲接受的移動群智感知多任務(wù)分配 ［J］. 計算機應(yīng)用研究， 2021， 38（8）： 2440-2444. （Yang Guisong， Wang Buye， He Xingyu. Multi-task allocation based on de-ferred acceptance in mobile crowd sensing ［J］. Application Research of Computers， 2021， 38（8）： 2440-2444.）

［13］傅彥銘， 陸盛林， 祁康恒， 等. 面向異構(gòu)效用的移動群智感知多目標(biāo)任務(wù)分配 ［J］. 計算機應(yīng)用研究， 2024， 41（1）： 159-164， 169. （Fu Yanming， Lu Shenglin， Qi Kangheng， et al. Multi-objective task assignment towards heterogeneous utilities in mobile crowdsensing ［J］. Application Research of Computers， 2024， 41（1）： 159-164， 169.）

［14］Ipaye A A， Chen Zhigang， Asim M，et al. Location and time aware multitask allocation in mobile crowd-sensing based on genetic algorithm ［J］. Sensors， 2022， 22（8）： 3013.

［15］袁姝， 周朝榮， 楊正清， 等. 群智感知系統(tǒng)中基于鯨魚優(yōu)化算法的任務(wù)分配 ［J］. 計算機工程與設(shè)計， 2020， 41（7）： 2031-2037. （Yuan Shu， Zhou Zhaorong， Yang Zhengqing， et al. Task allocation based on whale optimization algorithm in crowdsensing systems ［J］. Computer Engineering and Design， 2020， 41（7）： 2031-2037.）

［16］He Shibo， Shin D H， Zhang Junshan， et al. Toward optimal allocation of location dependent tasks in crowdsensing［C］// Proc of IEEE Conference on Computer Communications. Piscataway， NJ： IEEE Press， 2014： 745-753.

［17］Mirjalili S， Lewis A. The whale optimization algorithm ［J］. Advances in Engineering Software， 2016， 95： 51-67.

［18］劉光才， 馬寅松. 城市物流無人機配送中心選址及任務(wù)分配研究 ［J］. 飛行力學(xué)， 2023， 41（3）： 88-94. （Liu Guangcai， Ma Yinsong. Research on location and task allocation of urban logistics UAV distribution center ［J］. Flight Dynamics， 2023， 41（3）： 88-94.）