楊桂松 白高磊 何杏宇 賈明權(quán)

摘 要：現(xiàn)有移動(dòng)群智感知中，大多研究將每個(gè)任務(wù)作為獨(dú)立個(gè)體進(jìn)行處理，對(duì)任務(wù)間約束關(guān)系缺乏研究，為此，提出了基于感知質(zhì)量優(yōu)先級(jí)的在線任務(wù)協(xié)作方法（online task collaboration method based on sensing quality priority，TCSP）。該方法首先使用貪婪算法計(jì)算感知質(zhì)量優(yōu)先級(jí)，對(duì)全部任務(wù)進(jìn)行篩選以保證任務(wù)完成率；然后將選出任務(wù)中存在時(shí)間先后或執(zhí)行邏輯前后關(guān)系的多個(gè)子任務(wù)構(gòu)建為任務(wù)協(xié)作圖，并將其協(xié)作過程建模為有約束的馬爾可夫決策過程，通過強(qiáng)化學(xué)習(xí)算法求出最優(yōu)協(xié)作策略。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有基線方法相比，所提出的任務(wù)協(xié)作方法能夠減少依賴任務(wù)的平均完成時(shí)間，有效降低平臺(tái)的平均感知成本。

關(guān)鍵詞：移動(dòng)群智感知； 依賴關(guān)系； 感知質(zhì)量優(yōu)先級(jí)； 在線任務(wù)協(xié)作； 強(qiáng)化學(xué)習(xí)

中圖分類號(hào)：TP393?? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2023）09-009-0000-00

doi：10.19734/j.issn.1001-3695.2023.02.0048

Dependency constraint oriented task collaboration in mobile crowd sensing

Yang Guisong1a， Bai Gaolei1a， He Xingyu1a，1b， Jia Mingquan2

（1.a.School of Optical-Electrical & Computer Engineering， b.College of Communication & Art Design， University of Shanghai for Science & Technology， Shanghai 200093， China; 2.Southwest China Institute of Electronic Technology， Chengdu 610036， China）

Abstract：In the existing mobile crowd sensing， most studies treat each task as an independent individual， and lack of research on the constraint relationship between tasks. In view of this， this paper proposed an online task collaboration method based on sensing quality priority （TCSP）. Firstly， this method used greedy algorithm to calculate the sensing quality priority， screened all tasks to ensure the task completion rate. Then it constructed a task cooperation graph for multiple subtasks that had time sequence or execution logic relationship in the selected tasks and modelled cooperation process as a constrained Markov decision process， obtained the optimal cooperation strategy through reinforcement learning algorithm. Experimental results verify that compared with the existing baseline methods， the proposed TCSP method can reduce the average completion time of dependent tasks and reduce the average sensing cost of the platform.

Key words：mobile crowd sensing; dependency; sensing quality priority; online task collaboration; reinforcement learning

0 引言

移動(dòng)群智感知（mobile crowd sensing，MCS）［1］是一種利用大量移動(dòng)終端隨時(shí)隨地進(jìn)行感知活動(dòng)的重要感知范式，已經(jīng)廣泛應(yīng)用于不同領(lǐng)域，如環(huán)境質(zhì)量監(jiān)測(cè)［2］、交通管理［3］、健康信息搜集［4］、智慧城市監(jiān)控［5］等。MCS通常由任務(wù)請(qǐng)求者、MCS平臺(tái)和移動(dòng)工人三個(gè)部分組成。具體來說，任務(wù)請(qǐng)求者通過MCS平臺(tái)發(fā)布感知需求，MCS平臺(tái)根據(jù)算法將任務(wù)分配給合適的工人，工人將感知任務(wù)結(jié)果提交給平臺(tái)并得到相應(yīng)的報(bào)酬。在這個(gè)過程中，平臺(tái)需要通過匯聚大量的工人信息和任務(wù)信息進(jìn)行任務(wù)與工人之間的匹配以完成感知活動(dòng)，因此在滿足任務(wù)約束（時(shí)空需求、任務(wù)預(yù)算）和工人約束（時(shí)空特性，感知能力）的條件下，將任務(wù)分配給合適的工人是一個(gè)關(guān)鍵問題。平臺(tái)的任務(wù)分配能力不僅影響任務(wù)的完成速度和成本，而且對(duì)于實(shí)效性要求較高的任務(wù)（城市環(huán)境變化情況的持續(xù)監(jiān)測(cè)，實(shí)時(shí)交通情況預(yù)測(cè)）而言，其直接決定了感知任務(wù)是否能夠被有效完成。

根據(jù)MCS中任務(wù)分配時(shí)效性的不同可以分為離線任務(wù)分配和在線任務(wù)分配。對(duì)于離線任務(wù)分配而言，平臺(tái)具有全部的工人和感知任務(wù)信息，在任務(wù)開始執(zhí)行前就做好所有分配的決策，所有工人根據(jù)這個(gè)決策來執(zhí)行。例如工人、任務(wù)信息都已知的條件下，文獻(xiàn)［6］設(shè)計(jì)了一種討價(jià)還價(jià)的定價(jià)機(jī)制為所有任務(wù)分配工人；文獻(xiàn)［7］提出了一種參與者選擇框架，最大化地完成任務(wù)總數(shù)；文獻(xiàn)［8］是在成本約束的條件下選擇參與者子集，最大化任務(wù)滿意度。對(duì)于在線任務(wù)分配而言，平臺(tái)只具有當(dāng)前已經(jīng)到達(dá)的任務(wù)和參與者的信息，MCS平臺(tái)需要根據(jù)當(dāng)前的任務(wù)和工人情況進(jìn)行任務(wù)分配。例如，文獻(xiàn)［9］將在線任務(wù)分配視為多輪虛擬離線任務(wù)分配，假設(shè)某段時(shí)間內(nèi)任務(wù)和工人情況不發(fā)生改變，解決移動(dòng)社交網(wǎng)絡(luò)中人群感知的制造跨度敏感問題；文獻(xiàn)［10］提出了一個(gè)概率模型來衡量任務(wù)的質(zhì)量，進(jìn)而可以實(shí)時(shí)為當(dāng)前工人分配適當(dāng)?shù)娜蝿?wù)；文獻(xiàn)［11～13］通過研究機(jī)會(huì)傳輸、時(shí)間和空間相關(guān)性設(shè)計(jì)在線任務(wù)分配方法，提升平臺(tái)執(zhí)行效能。離線任務(wù)分配掌握著更多的信息，可以獲得更好的性能，但時(shí)效性不強(qiáng)；在線方案可以實(shí)時(shí)作出決策，更加靈活，適合動(dòng)態(tài)實(shí)時(shí)場(chǎng)景，但是由于在線任務(wù)分配缺乏全局信息，很可能導(dǎo)致任務(wù)分配失敗，這就需要通過有效的方法確保在線任務(wù)完成率。

由于工人移動(dòng)帶來的不確定和不可控性，感知質(zhì)量的優(yōu)劣是在線任務(wù)能否有效完成的關(guān)鍵。文獻(xiàn)［14］通過引入特定于任務(wù)的最小傳感質(zhì)量閾值重新定義問題，以保證單個(gè)任務(wù)感知質(zhì)量的多任務(wù)分配；文獻(xiàn)［15］利用參與者積累的聲譽(yù)和意愿來構(gòu)建服務(wù)質(zhì)量模型，在最大化服務(wù)質(zhì)量的基礎(chǔ)上選擇最合適的一組參與者，盡可能提高平臺(tái)的最終收入和參與者的利益；文獻(xiàn)［16］定義了一種新的質(zhì)量覆蓋率度量，考慮了傳感器讀數(shù)覆蓋的子區(qū)域的比例以及每個(gè)覆蓋子區(qū)域中傳感數(shù)據(jù)的質(zhì)量，以實(shí)現(xiàn)基于位置的多樣化MCS任務(wù)。對(duì)于實(shí)效性較強(qiáng)的任務(wù)，感知質(zhì)量的好壞是影響任務(wù)能否完成的關(guān)鍵環(huán)節(jié)，因此如何評(píng)估感知質(zhì)量來保證在線任務(wù)完成率是一大挑戰(zhàn)。

值得注意的是，現(xiàn)有任務(wù)分配研究中，無論是針對(duì)單任務(wù)還是多任務(wù)的分配方法，大多將每個(gè)任務(wù)視為一個(gè)相互獨(dú)立的整體，然而隨著移動(dòng)群智感知中任務(wù)數(shù)量和復(fù)雜程度的增加，任務(wù)不再獨(dú)立，多個(gè)任務(wù)之間存在相互依存的關(guān)系［17，18］。在單任務(wù)分配研究中，每個(gè)任務(wù)根據(jù)參與者的特點(diǎn)，在滿足特定約束的條件下獨(dú)立地進(jìn)行分配。文獻(xiàn)［19］提出成本公平任務(wù)分配算法，將傳感任務(wù)分配給不同用戶，以便所有用戶承擔(dān)的傳感成本盡可能平衡，同時(shí)可以滿足請(qǐng)求者對(duì)數(shù)據(jù)可靠性的要求；文獻(xiàn)［20］考慮參與者的異質(zhì)性導(dǎo)致傳感數(shù)據(jù)可靠性差的問題，提出優(yōu)化算法以最大限度地提高完成任務(wù)的數(shù)量。在多任務(wù)分配研究中，雖然對(duì)任務(wù)間的移動(dòng)關(guān)系、需求差異等有所考慮，但每個(gè)任務(wù)執(zhí)行過程中仍然是相互獨(dú)立地進(jìn)行分配。例如，文獻(xiàn)［21］將現(xiàn)有任務(wù)序列與用戶的移動(dòng)規(guī)律性盡可能地保持一致，基于移動(dòng)性重復(fù)模式發(fā)現(xiàn)過程將原有的任務(wù)分配問題轉(zhuǎn)換為模式匹配問題；文獻(xiàn)［22］根據(jù)參與者的任務(wù)難度、任務(wù)歷史、感知能力和感知積極性對(duì)參與者的服務(wù)效益進(jìn)行建模，以滿足不同任務(wù)類型的差異化需求。

現(xiàn)有的多任務(wù)分配方法中，每個(gè)任務(wù)作為獨(dú)立個(gè)體，不能對(duì)任務(wù)間的約束關(guān)系進(jìn)行有效處理，提升MCS平臺(tái)對(duì)任務(wù)間的時(shí)間先后或執(zhí)行邏輯前后等約束關(guān)系的處理能力是處理具有依賴關(guān)系任務(wù)的關(guān)鍵。流式任務(wù)的調(diào)度和分配問題的研究是分析和處理這種任務(wù)間依賴關(guān)系的重要途徑［23］，例如對(duì)于城市環(huán)境變化情況持續(xù)監(jiān)測(cè)任務(wù)，如果要知道當(dāng)前環(huán)境情況，不僅需要獲得當(dāng)前時(shí)刻任務(wù)的感知數(shù)據(jù)（溫度數(shù)據(jù)、濕度數(shù)據(jù)、風(fēng)速數(shù)據(jù)等），而且還需要上一時(shí)刻任務(wù)對(duì)歷史數(shù)據(jù)的計(jì)算結(jié)果，才能對(duì)當(dāng)前任務(wù)作出有效預(yù)測(cè)或計(jì)算。因此，針對(duì)有時(shí)間先后或執(zhí)行邏輯前后依賴關(guān)系約束的任務(wù)，如何設(shè)計(jì)有效的任務(wù)協(xié)作機(jī)制以提升平臺(tái)的在線任務(wù)處理能力是另一個(gè)挑戰(zhàn)。

一方面，時(shí)空覆蓋率和數(shù)據(jù)質(zhì)量是影響感知任務(wù)能否完成的關(guān)鍵因素，時(shí)空覆蓋率越高參與執(zhí)行任務(wù)的工人越多，數(shù)據(jù)質(zhì)量越高參與的工人能力越能滿足任務(wù)需要。因此在特定時(shí)空范圍內(nèi)，對(duì)當(dāng)前平臺(tái)中不同任務(wù)的感知質(zhì)量（時(shí)空覆蓋率和數(shù)據(jù)質(zhì)量）進(jìn)行評(píng)估并優(yōu)先執(zhí)行感知質(zhì)量最高的任務(wù)，可以保證多個(gè)子任務(wù)執(zhí)行的有效性、及時(shí)性和平臺(tái)任務(wù)完成率等。另一方面，對(duì)具有時(shí)間先后或執(zhí)行邏輯前后依賴關(guān)系約束的子任務(wù)建立有效的任務(wù)協(xié)作模型是平臺(tái)能夠進(jìn)行實(shí)時(shí)計(jì)算或預(yù)測(cè)分析的關(guān)鍵。圖結(jié)構(gòu)可以有效地表示這種依賴關(guān)系，子任務(wù)表示為節(jié)點(diǎn)，子任務(wù)間的依賴關(guān)系表示為邊，可以將根據(jù)子任務(wù)間的依賴關(guān)系為每個(gè)子任務(wù)選擇最合適的工人的過程映射為有約束的馬爾可夫決策過程，最終通過強(qiáng)化學(xué)習(xí)方法學(xué)習(xí)可以得到最優(yōu)協(xié)作策略。

綜上所述，針對(duì)挑戰(zhàn)本文提出了基于感知質(zhì)量優(yōu)先級(jí)的在線任務(wù)協(xié)作方法（TCSP）。主要貢獻(xiàn)如下：a）使用貪婪算法計(jì)算感知質(zhì)量優(yōu)先級(jí)，對(duì)全部任務(wù)進(jìn)行篩選以保證任務(wù)完成率，同時(shí)也將原問題分解成為多個(gè)子問題，減小了任務(wù)協(xié)作模型的可行域，提高了模型的收斂速度；b）將有時(shí)間先后或執(zhí)行邏輯前后關(guān)系的子任務(wù)構(gòu)建為任務(wù)協(xié)作圖，然后將此任務(wù)協(xié)作過程建模為有約束的馬爾可夫決策過程，并通過Q學(xué)習(xí)算法得到最優(yōu)協(xié)作策略。

1 系統(tǒng)模型

本文考慮一個(gè)實(shí)際場(chǎng)景，該場(chǎng)景中包括一個(gè)平臺(tái)，多個(gè)任務(wù)請(qǐng)求方以及多個(gè)工人，其中每個(gè)任務(wù)包含有多個(gè)具有依賴關(guān)系的子任務(wù)，平臺(tái)可以獲取特定時(shí)空范圍內(nèi)工人和現(xiàn)有任務(wù)的信息。在這種條件下，平臺(tái)計(jì)算出當(dāng)前時(shí)空區(qū)域內(nèi)每個(gè)任務(wù)與工人的感知質(zhì)量，并選出感知質(zhì)量最高的任務(wù)作為當(dāng)前待執(zhí)行任務(wù)。在任務(wù)執(zhí)行過程中，平臺(tái)根據(jù)上一個(gè)子任務(wù)分配工人后的狀態(tài)來確定下一個(gè)子任務(wù)的工人分配策略。任務(wù)執(zhí)行過程如圖1所示，a）MCS平臺(tái)處于等待狀態(tài)，當(dāng)有任務(wù)發(fā)布者把任務(wù)需求發(fā)送至平臺(tái)時(shí)將喚醒平臺(tái)進(jìn)行任務(wù)處理；b）平臺(tái)根據(jù)任務(wù)信息和激勵(lì)政策向特定時(shí)空區(qū)域發(fā)送招募需求，收到信息的工人根據(jù)招募信息決定是否參與感知活動(dòng)，如果參與感知活動(dòng)就上傳自身感知能力和位置等工人信息至平臺(tái)；c）平臺(tái)先根據(jù)工人的感知能力和任務(wù)需求計(jì)算出當(dāng)前感知質(zhì)量最高的任務(wù)，然后根據(jù)子任務(wù)間的依賴關(guān)系、子任務(wù)執(zhí)行時(shí)產(chǎn)生的激勵(lì)成本和時(shí)間成本為每個(gè)子任務(wù)選擇最合適的工人，循環(huán)執(zhí)行此步驟直到所有子任務(wù)協(xié)作完成整個(gè)任務(wù)。工人將感知結(jié)果上傳至平臺(tái)并獲得相應(yīng)的報(bào)酬，平臺(tái)持續(xù)檢查是否還有任務(wù)等待執(zhí)行，如果有就重復(fù)此過程，如果沒有就進(jìn)入等待狀態(tài)。

本文將時(shí)空區(qū)域定義為由d個(gè)子單元組成的感知地圖M，集合表示為M={m1，m2，…，mi，…，md}，第i個(gè)地圖子單元表示為mi（1≤i≤d）。此時(shí)空范圍內(nèi)有c個(gè)工人參與感知活動(dòng)，集合表示為W={w1 ，w2，…，wj，…，wc}，第j個(gè)工人表示為wj（1≤j≤c）。

工人的感知特性包括感知范圍和感知能力兩個(gè)方面，工人wj的感知范圍表示工人在此時(shí)空區(qū)域內(nèi)可以感知到的地圖子單元，集合表示為Rwj={r1，…，r（k，R（wj）），…，rn}，工人wj第k個(gè)感知單元為r（k，R（wj）），1≤k≤n。工人感知能力的大小由感知設(shè)備特性決定，如設(shè)備計(jì)算能力、傳感器感知能力、網(wǎng)絡(luò)傳輸能力等因素，工人wj感知能力向量表示為P（wj）=|p1，p2…，p（l，P（wj）），…，pf|，工人第l維感知能力為p（l，P（wj）），1≤l≤f，其數(shù)值大小表示工人某一方面的能力情況。

在感知時(shí)空范圍內(nèi)MCS平臺(tái)收到多個(gè)發(fā)布者的任務(wù)請(qǐng)求，集合表示為TS={T1，T2，…，To，…，Tb}，其中第o個(gè)任務(wù)為To（1≤o≤b），其由g個(gè)前后依賴關(guān)系的子任務(wù)組成，集合表示為，To={t1，t2，…，t（u，T0），…，tg}，1≤u≤g，t（u，T0）表示To任務(wù)的第u個(gè)子任務(wù)。子任務(wù)的感知需求包括感知范圍需求和感知量需求，子任務(wù)t（u，To）執(zhí)行需求感知范圍集合表示為，E（tu，To）={e1，e2，…，e（v，t（u，To）），…，eh}，其中，第v個(gè)子任務(wù)的需求地圖子單元為e（v，t（u，To））（1≤v≤h）。子任務(wù)t（u，To）感知量需求向量為QTotu=|q1，q2…，q（x，t（u，To）），…，pf|，其中q（x，t（u，To））為子任務(wù)第x維感知質(zhì)量需求。

為了更清晰地說明多個(gè)子任務(wù)之間的約束關(guān)系，將任務(wù)To的所有子任務(wù)之間的關(guān)系用有向無環(huán)圖表示。如圖2所示，給出了子任務(wù)數(shù)量分別為4、6、10個(gè)且子任務(wù)間依賴關(guān)系為圖2中的類型1～3的任務(wù)模型。其中，以類型2為例，假設(shè)任務(wù)To由6個(gè)子任務(wù)t1～t6組成，節(jié)點(diǎn)表示子任務(wù)，邊表示子任務(wù)之間的時(shí)間先后或執(zhí)行邏輯前后關(guān)系，所有頂點(diǎn)構(gòu)成集合VTo，有向邊構(gòu)成集合ETo。如果某個(gè)子任務(wù)節(jié)點(diǎn)具有多個(gè)前驅(qū)節(jié)點(diǎn)，那么只有所有前驅(qū)節(jié)點(diǎn)執(zhí)行完后這個(gè)子任務(wù)節(jié)點(diǎn)才能執(zhí)行。例如圖2中類型2，t6的依賴關(guān)系為邊（t3，t6）、（t4，t6）、（t5，t6），只有當(dāng)t3、t4、t5任務(wù)執(zhí)行完t6后才可以執(zhí)行。

2 任務(wù)感知質(zhì)量優(yōu)先級(jí)

為了提高任務(wù)的有效性和及時(shí)性，保證平臺(tái)任務(wù)的完成率，要對(duì)當(dāng)前平臺(tái)中任務(wù)的感知質(zhì)量進(jìn)行評(píng)估。本文設(shè)計(jì)了融合貪婪算法的感知質(zhì)量優(yōu)先級(jí)任務(wù)調(diào)度模型，分別從時(shí)空覆蓋率和數(shù)據(jù)質(zhì)量兩個(gè)方面對(duì)每個(gè)任務(wù)的感知質(zhì)量進(jìn)行分析，以有效地評(píng)估感知質(zhì)量優(yōu)劣、提升在線任務(wù)的完成率。前者關(guān)注的是是否有足夠的工人執(zhí)行任務(wù)，后者關(guān)注的是工人能力是否滿足任務(wù)執(zhí)行的需要，如計(jì)算能力、傳感器感知能力等。

2.1 時(shí)空覆蓋率

對(duì)于某個(gè)任務(wù)而言，每個(gè)子任務(wù)需要的地圖子單元與工人的感知范圍是否重合決定了此子單元的覆蓋情況?；诖?，任務(wù)的時(shí)空覆蓋率計(jì)算可以用其每個(gè)子任務(wù)的地圖子單元是否有工人覆蓋作為計(jì)數(shù)依據(jù)。

對(duì)于任務(wù)To的任意子任務(wù)t（u，To），其工人覆蓋情況用二元變量H（e（v，t（u，To）），r（k，R（wj）））表示，當(dāng)值為1時(shí)表示子任務(wù)t（u，To）的感知需求地圖子單元可以被工人wj感知子單元r（k，R（wj））覆蓋到，為0則表示未被覆蓋。其中，H（·）為對(duì)比函數(shù)，兩變量相同時(shí)值為1，不同時(shí)值為0。在當(dāng)前時(shí)空范圍內(nèi)，子任務(wù)t（u，To）的需求地圖子單元被工人wj覆蓋到的數(shù)量計(jì)算如下：

MATt（u，To）（wj）=∑hv=1∑nk=1H（e（v，t（u，To）），r（k，R（wj）））（1）

任務(wù)TO的所有子任務(wù)可以被當(dāng)前時(shí)空范圍內(nèi)的工人覆蓋的數(shù)量計(jì)算如下：

FCTo=∑gu=1∑cj=1MATt（u，To）（wj）（2）

子任務(wù)t（u，To）的地圖子單元的需求數(shù)量union（Et（u，To））表示任務(wù)需求地圖中不同子單元的數(shù)量。其中union（·）為集合計(jì)數(shù)函數(shù)，累加不同子單元的個(gè)數(shù)。因此，任務(wù)To的所有子任務(wù)感知地圖子單元總數(shù)量計(jì)算如下：

QTo=∑gu=1union（Et（u，To））（3）

對(duì)于任務(wù)To，時(shí)空覆蓋率定義為感知范圍內(nèi)所有工人可以覆蓋此任務(wù)的地圖子單元的數(shù)量與任務(wù)執(zhí)行需要的所有地圖子單元數(shù)量的比值，計(jì)算如下：

coverTo=FCToQTo（4）

2.2 數(shù)據(jù)質(zhì)量

空間中向量之間的距離是兩個(gè)向量相似程度的反映，因此任務(wù)的感知質(zhì)量需求與工人感知能力之間的相似程度采用歐氏距離來度量。對(duì)于每個(gè)子任務(wù)t（u，To）的感知內(nèi)容需求向量QTotu與工人wj的感知能力向量P（wj）之間的相似程度可以用dis（P（wj），QTotu），其中函數(shù)dis（·）為歐式函數(shù)，計(jì)算兩個(gè)向量之間的空間距離。因此，任務(wù)To的所有子任務(wù)感知質(zhì)量需求與時(shí)空區(qū)域內(nèi)所有工人的感知能力之間的距離計(jì)算如下：

LenTo=∑gu=1∑cj=1dis（P（wj），QTotu）（5）

由上面計(jì)算可知，對(duì)于任務(wù)To，數(shù)據(jù)質(zhì)量定義為感知時(shí)空區(qū)域內(nèi)所有工人的感知能力與任務(wù)的感知質(zhì)量需求距離的倒數(shù)，計(jì)算如下：

DatTo=1LenTo（6）

根據(jù)得到的CoverTo和DatTo，每個(gè)任務(wù)To的感知質(zhì)量定義為覆蓋率和數(shù)據(jù)質(zhì)量的線性組合，計(jì)算如下：

QuaTo=σCoverTo+ξDatTo（7）

其中：σ、ξ為給定的常數(shù)。

2.3 任務(wù)優(yōu)先級(jí)調(diào)度算法

算法1是融合貪心算法的感知質(zhì)量優(yōu)先級(jí)任務(wù)調(diào)度模型的執(zhí)行過程。

算法1 任務(wù)優(yōu)先級(jí)調(diào)度算法

輸入：時(shí)空單元地圖M，工人集合W，每個(gè)工人感知范圍R和感知能力向量P，任務(wù)集合TS，每個(gè)任務(wù)的子任務(wù)集合T，子任務(wù)感知范圍E和感知質(zhì)量需求Q。

輸出：被選取的任務(wù)Tprior。

a）如果有新的任務(wù)請(qǐng)求，將此任務(wù)加入隊(duì)列；

b）從當(dāng)前任務(wù)隊(duì)列隊(duì)頭取出任務(wù)To；

c）根據(jù)式（4）計(jì)算出任務(wù)To時(shí)空覆蓋率；

d）根據(jù)式（6）計(jì)算出任務(wù)To數(shù)據(jù)質(zhì)量；

e）根據(jù)式（7）計(jì)算出任務(wù)To的感知質(zhì)量QuaTo；

f）如果隊(duì)列不為空，跳轉(zhuǎn)至步驟b）；

g）根據(jù)每個(gè)任務(wù)QuaTo的大小進(jìn)行排序；

h）按照QuaTo從大到小的順序?qū)⑷蝿?wù)重新加入隊(duì)列；

i）采用貪心策略，將隊(duì)頭任務(wù)出隊(duì)并賦值給Tprior。

3 子任務(wù)在線協(xié)作

3.1 子任務(wù)協(xié)作模型

3.1.1 子任務(wù)激勵(lì)成本

由于工人移動(dòng)帶來的不確定性，要激勵(lì)盡可能多的工人參與任務(wù)以提升感知質(zhì)量，需要考慮工人的執(zhí)行成本和補(bǔ)償成本。本文定義執(zhí)行成本為完成子任務(wù)t（u，To）需要平臺(tái)支付產(chǎn)生的成本，其由子任務(wù)的感知量QTotu以及平臺(tái)設(shè)定的價(jià)格決定，執(zhí)行成本計(jì)算如下：

Cos（tt（u，To））=QtuTopri（8）

其中：向量pri為平臺(tái)制定支付每類傳感器的單價(jià)。

執(zhí)行補(bǔ)償定義為設(shè)備損耗補(bǔ)償和移動(dòng)補(bǔ)償，其中，設(shè)備損耗補(bǔ)償PC為子任務(wù)t（u，To）完成后的補(bǔ)償；移動(dòng)補(bǔ)償為子任務(wù)所在地圖子單元e（v，t（u，To））與工人所在地圖子單元r（k，R（wj））之間的距離開銷，計(jì)算如下：

Com（wj，t（u，To））=PC（t（u，To））+τ|r（k，R（wj））－e（v，t（u，To））|（9）

其中：τ為一個(gè)常數(shù)系數(shù)。

根據(jù)得到的執(zhí)行成本和補(bǔ)償成本，總的激勵(lì)成本定義為兩者之和，計(jì)算如下：

pay（wj，t（u，To））=Cos（tt（u，To））+Com（wj，t（u，To））（10）

3.1.2 子任務(wù)執(zhí)行時(shí)間成本

對(duì)于在線任務(wù)，時(shí)效性也是需要關(guān)注的問題，任務(wù)的完成時(shí)間越短，性能越好。優(yōu)化任務(wù)執(zhí)行時(shí)間也是本文要優(yōu)化的目標(biāo)，因此，本文在設(shè)計(jì)子任務(wù)時(shí)間成本時(shí)，將執(zhí)行時(shí)間分為子任務(wù)執(zhí)行時(shí)間成本和子任務(wù)之間因約束關(guān)系而產(chǎn)生的同步時(shí)間成本。具體來說，工人wj執(zhí)行子任務(wù)t（u，To）的時(shí)間成本定義為子任務(wù)每一類工作需求q（x，t（u，To））與工人的對(duì)應(yīng)執(zhí)行能力p（l，P（wj））的比值之和，運(yùn)行時(shí)間成本計(jì)算如下：

run（wj，t（u，To））=δ∑l=x=fl=x=1q（x，t（u，To））p（l，P（wj））（11）

其中：其中δ為常數(shù)參數(shù)。

同步時(shí)間成本為子任務(wù)間相互約束關(guān)系而產(chǎn)生的收發(fā)同步消息時(shí)延，定義為子任務(wù)t（u，To）感知質(zhì)量需求QTotu成正比，同步時(shí)間計(jì)算如下：

syn（wj，t（u，To））=εQTotu（12）

其中：ε為常數(shù)參數(shù)。

子任務(wù)t（u，To），在選擇工人wj的情況下，執(zhí)行總時(shí)間成本定義為運(yùn)行時(shí)間與同步時(shí)間之和，計(jì)算如下：

time（wj，t（u，To））=run（wj，t（u，To））+syn（wj，t（u，To））（13）

3.1.3 優(yōu)化目標(biāo)

基于上述分析，任務(wù)分配模型的優(yōu)化目標(biāo)為：在（wj，tu）二元組構(gòu)成的離散決策空間中，在滿足約束的條件下，為被選擇任務(wù)的每個(gè)子任分配合適的工人，使激勵(lì)成本大小與任務(wù)完成時(shí)間最小化。

minF（To）=∑gu=1|θpay（wj，t（u，To））+μtime（wj，t（u，To））|（14）

s.t. To=Tprior（15）

q（x，t（u，To））≤p（l，P（wj））（16）

t（u，To），t（u+1，To）∈To且（t（u，To），t（u+1，To））∈ETo（17）

其中：（wj，tu）∈D，D為子任務(wù)與工人二元組的離散決策空間，wj為工人集合W中的任一元素 ，tu為任務(wù)To的子任務(wù)。約束式（15）表示任務(wù)To為算法1篩選出的任務(wù)；約束式（16）表示子任務(wù)t（u，To）的感知需求小于工人wj的感知能力p（l，P（wj））；約束式（17）表示任務(wù)t（u，To），t（u+1，To）為To的子任務(wù)，且其構(gòu)成的邊（t（u，To），t（u+1，To））滿足任務(wù)To子任務(wù)間的相互約束關(guān)系;θ、μ為給定的常數(shù)。

3.2 基于強(qiáng)化學(xué)習(xí)的子任務(wù)協(xié)作方法

3.2.1 強(qiáng)化學(xué)習(xí)進(jìn)行子任務(wù)協(xié)作

本文所要解決的問題為式（14）所示的組合優(yōu)化問題，考慮到子任務(wù)間依賴關(guān)系約束和任務(wù)工人二元組構(gòu)成的離散決策空間，將此組合優(yōu)化問題建模為有約束的馬爾可夫決策過程，并采用可以在序列決策過程中構(gòu)建解決方案的Q學(xué)習(xí)方法進(jìn)行問題求解。

具體而言，將MCS平臺(tái)作為智能體，根據(jù)當(dāng)前子任務(wù)和已經(jīng)被執(zhí)行的子任務(wù)的狀態(tài)，采取為當(dāng)前子任務(wù)選擇工人的動(dòng)作，然后通過計(jì)算目標(biāo)表達(dá)式的函數(shù)值獲得來自環(huán)境的獎(jiǎng)勵(lì)。重復(fù)此訓(xùn)練過程直到滿足算法的終止條件，此時(shí)智能體得到的所有狀態(tài)到動(dòng)作之間的映射概率關(guān)系即為策略，所有工人和任務(wù)組成的二元組集合構(gòu)成此組合優(yōu)化問題的最優(yōu)解。

3.2.2 依賴關(guān)系約束的狀態(tài)、動(dòng)作空間等

1）有約束的動(dòng)作空間

動(dòng)作是任意時(shí)刻的子任務(wù)工人匹配方式，即a=（wj，t（u，To）），a∈A，二元組（wj，t（u，To））表示為子任務(wù)t（u，To）分配工人wj，A為動(dòng)作空間。

約束動(dòng)作選擇空間采用鄰接矩陣A表示，假設(shè)對(duì)nn個(gè)子任務(wù)、mm個(gè)工人進(jìn)行匹配，那么其中任意一次組合可以用二元組（ii，jj）表示，當(dāng)為1時(shí)表示子任務(wù)ii可以分配給工人jj，當(dāng)為0時(shí)表示子任務(wù)ii不可以分配給工人jj。由于工人感知能力和子任務(wù)感知需求之間的約束關(guān)系以及任務(wù)協(xié)作圖中子任務(wù)的順序性約束關(guān)系，當(dāng)執(zhí)行到不同的子任務(wù)，下一步動(dòng)作的選擇必須滿足優(yōu)化目標(biāo)的約束關(guān)系，即滿足式（16）（17）的約束條件。

2）有約束狀態(tài)空間與馬爾可夫性

狀態(tài)空間S是智能體能夠選擇合理動(dòng)作的基礎(chǔ)， 本文將多個(gè)子任務(wù)tu分配不同工人的情況作為智能體狀態(tài)空間。對(duì)于任意時(shí)刻狀態(tài)用一個(gè)2m維變量的函數(shù)s（2m）表示，即 s（2m）∈S，前m個(gè)維度表示子任務(wù)的工人分配情況，后m個(gè)維度根據(jù)子任務(wù)協(xié)作圖的約束關(guān)系表示每個(gè)子任務(wù)執(zhí)行完后下一步可以被執(zhí)行的子任務(wù)。

具體來說，為子任務(wù)選擇工人的過程可以描述為：a）在當(dāng)前狀態(tài)下，通過判斷前m維變量的值隨機(jī)選擇任一子任務(wù)t（u，To），并按照ε貪心方法為其選擇滿足約束條件的工人wj，更新前m維變量的子任務(wù)的分配情況和鄰接矩陣A；b）根據(jù)由子任務(wù)間約束關(guān)系構(gòu)成的后m維變量，隨機(jī)選擇t（u，To）執(zhí)行完后可以執(zhí)行的下一個(gè)子任務(wù)；c）在滿足依賴約束的條件下為多個(gè)子任務(wù)選擇工人形成的隨機(jī)決策序列為S（2m），a，r（s（2m），a），s′（2m），a′，r′（s（2m），a），…。其中s′（2m）、a′、r′（s（2m），a）為下一時(shí)刻的子任務(wù)狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)。

在本文TCSP算法中，假設(shè)子任務(wù)和工人的隨機(jī)選擇過程滿足馬爾可夫特性，即子任務(wù)和工人的選擇概率只與當(dāng)前時(shí)刻的狀態(tài)s（2m）有關(guān)，公式表示如下：

P（（wj，t（u，To））|s（2m），s′（2m），…）=P（（wj，t（u，To））|s（2m））（18）

其中：s′（2m）為下一個(gè)時(shí)刻狀態(tài)。因此，本文將此隨機(jī)過程建模為有約束的馬爾可夫決策過程。

3）獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)

對(duì)于作為智能體的MCS平臺(tái)而言，一個(gè)子任務(wù)分配給某個(gè)工人的動(dòng)作，產(chǎn)生可以作為立即獎(jiǎng)勵(lì)的激勵(lì)成本和時(shí)間成本，即每執(zhí)行一個(gè)動(dòng)作就從環(huán)境中得到一個(gè)立即獎(jiǎng)勵(lì)。因此，立即獎(jiǎng)賞r（s（2m），a）計(jì)算如下：

r（s（2m），a）=θpay（wj，t（u，To））+μtime（wj，t（u，To））（19）

4）優(yōu)化策略及收斂性證明

子任務(wù)協(xié)作的目標(biāo)是為不同子任務(wù)tu分配工人wj使目標(biāo)函數(shù)F（To）最小化。平臺(tái)在為子任務(wù)分配工人的過程中通過Q學(xué)習(xí)算法進(jìn)行決策判斷。具體來說，智能體在為當(dāng)前子任務(wù)tu分配工人時(shí)，檢查Q表格中與此子任務(wù)對(duì)應(yīng)組合的Q值大小，選擇Q值最大組合中的工人分配給當(dāng)前子任務(wù)，并根據(jù)Q學(xué)習(xí)策略進(jìn)行模型更新，最終得到所有子任務(wù)的最優(yōu)協(xié)作策略。

Q學(xué)習(xí)算法是通過迭代訓(xùn)練更新Q表格，使最終狀態(tài)的Q值可以逼近目標(biāo)值。Q學(xué)習(xí)算法當(dāng)前狀態(tài)值更新規(guī)則，計(jì)算如下：

Q（s（2m），a）=Q（s（2m），a）+α［r（s′（2m），a′）+γmaxQ（s′（2m），a′）－Q（s（2m），a）］（20）

其中：r（s′（2m），a′）+γmaxQ（s′（2m），a′）是下一狀態(tài)目標(biāo)值，其為下一狀態(tài)值最大Q值和對(duì)應(yīng)的工人任務(wù)立即獎(jiǎng)勵(lì)之和； r（s′（2m），a′）+γmaxQ（s′（2m），a′）－Q（s（2m），a）為Q學(xué)習(xí)算法的時(shí)序差分誤差；Q（s（2m），a）的更新為當(dāng)前值與誤差值的和；γ為折扣因子，0≤γ≤1;α為學(xué)習(xí)率，0≤α≤1。

為了證明通過強(qiáng)化學(xué)習(xí)算法可以在有約束的馬爾可夫決策過程中求出最優(yōu)協(xié)作策略，設(shè)

ΔT（s（2m），a）=Q（s（2m），a）－Q*（s′（2m），a′）（21）

由文獻(xiàn)［24］中定理2可以證明，Q學(xué)習(xí)方法在滿足其三個(gè)約束條件時(shí)ΔT（s（2m），a）趨近于0，即該方法可以通過式（20）迭代收斂于最佳狀態(tài)動(dòng)作價(jià)值函數(shù)Q*（s′（2m），a′），進(jìn)而得到最佳協(xié)作策略。

3.2.3 子任務(wù)協(xié)作算法實(shí)現(xiàn)

算法2 子任務(wù)在線協(xié)作算法

輸入：時(shí)空單元地圖M，工人集合W，每個(gè)工人感知范圍R和感知能力向量P，任務(wù)集合TS，每個(gè)任務(wù)的子任務(wù)集合T，子任務(wù)感知范圍E和感知質(zhì)量需求Q，算法1的Tprior。

輸出：所有子任務(wù)工人二元組集合。

a）初始化Q表格；

b）初始化參數(shù)θ、μ、γ、α；

c）判斷是否需要循環(huán)進(jìn)行m輪模型訓(xùn)練，如果不需要直接轉(zhuǎn)至步驟j）；

d）工人、任務(wù)、時(shí)空單元參數(shù)隨機(jī)初始化；

e）為了防止模型陷入局部最優(yōu)，采用ε貪心策略進(jìn)行模型訓(xùn)練，即隨機(jī)生成概率prob，如果prob<ε，隨機(jī)選取一個(gè)動(dòng)作執(zhí)行，否則根據(jù)約束動(dòng)作空間A和當(dāng)前狀態(tài)s（2m）作出動(dòng)作選擇a；

f）根據(jù)式（17）得到智能體的立即獎(jiǎng)勵(lì)r（s（2m），a）；

g）更新為下一時(shí)刻狀態(tài)；

h）根據(jù)式（18）更新模型的Q表格；

i） 如果模型訓(xùn)練結(jié)束，保存模型參數(shù)；

j）讀取模型參數(shù)值至Q表；

k）根據(jù)Tprior的所有子任務(wù)情況，輸入當(dāng)前狀態(tài)s（2m）到Q學(xué)習(xí)算法中，計(jì)算出子任務(wù)工人二元組值；

l） 重復(fù)執(zhí)行步驟k）直到協(xié)作任務(wù)完成；

m）輸出所有子任務(wù)工人二元組集合。

4 實(shí)驗(yàn)及分析

進(jìn)一步，針對(duì)MCS中有依賴約束任務(wù)的在線協(xié)作問題，本文綜合考慮了工人、任務(wù)的時(shí)空特性，感知質(zhì)量特點(diǎn)和子任務(wù)之間的依賴約束等因素，以最小化系統(tǒng)激勵(lì)成本與時(shí)間成本為目標(biāo)，基于貪心和強(qiáng)化學(xué)習(xí)算法設(shè)計(jì)了一種在線任務(wù)協(xié)作算法。為了評(píng)估本文算法的性能，在Python實(shí)驗(yàn)環(huán)境中，首先對(duì)本文提出的TCSP算法的收斂特性、最優(yōu)協(xié)作策略和任務(wù)數(shù)量變化的影響進(jìn)行分析，然后通過對(duì)比實(shí)驗(yàn)進(jìn)行算法性能驗(yàn)證。實(shí)驗(yàn)的主要參數(shù)設(shè)置如表1所示。

4.1 TCSP算法特性分析

為評(píng)估TCSP算法，本文從工人數(shù)量和子任務(wù)數(shù)量兩個(gè)因素對(duì)算法模型的影響進(jìn)行實(shí)驗(yàn)分析。具體來說，首先對(duì)圖2中類型2任務(wù)進(jìn)行模型的收斂性和最優(yōu)協(xié)作策略分析；然后，固定工人數(shù)量為20個(gè)，增加子任務(wù)數(shù)量分別為4、6、10個(gè)且依賴關(guān)系為圖2中類型1～3時(shí)進(jìn)行模型的性能變化分析。在實(shí)驗(yàn)中每次對(duì)模型進(jìn)行1000輪訓(xùn)練，觀察并分析每一輪訓(xùn)練完成后平臺(tái)智能體獲得的獎(jiǎng)勵(lì)和的變化規(guī)律，基于此進(jìn)行模型特性分析。

圖3顯示了工人個(gè)數(shù)取不同值時(shí)模型獎(jiǎng)勵(lì)和的變化。從圖3中可以看出，工人數(shù)在不同情況下，隨著迭代輪數(shù)的增加模型的獎(jiǎng)勵(lì)和都在逐漸增大，最終趨于一個(gè)穩(wěn)定值。表明TCSP算法在針對(duì)有依賴的協(xié)作任務(wù)進(jìn)行訓(xùn)練時(shí)可以得到穩(wěn)定的算法模型，即可以得到穩(wěn)定的任務(wù)協(xié)作策略。另一方面，從圖3中還可以看出當(dāng)工人數(shù)從10個(gè)變化到20個(gè)時(shí)，模型的獎(jiǎng)勵(lì)和最終收斂值約有10%的提升；繼續(xù)將工人數(shù)從20個(gè)增加到30個(gè)時(shí)，模型的最終獎(jiǎng)勵(lì)和無明顯提升，表明在任務(wù)數(shù)量固定的情況下，當(dāng)20個(gè)工人時(shí)TCSP算法可以訓(xùn)練得到最優(yōu)任務(wù)協(xié)作策略。

圖4顯示工人數(shù)量固定為20個(gè)時(shí)，子任務(wù)數(shù)量取不同值且依賴關(guān)系為不同類型的情況下模型獎(jiǎng)勵(lì)和的變化。一方面從圖中可以看出，子任務(wù)數(shù)在不同情況下，隨著迭代輪數(shù)的增加模型的獎(jiǎng)勵(lì)和都在逐漸增大，最終趨于一個(gè)穩(wěn)定值。表明TCSP算法在針對(duì)有不同數(shù)量和依賴關(guān)系的協(xié)作子任務(wù)進(jìn)行訓(xùn)練時(shí)都可以得到穩(wěn)定的任務(wù)協(xié)作策略。另一方面，從圖4中可以看出當(dāng)子任務(wù)數(shù)量為4個(gè)且依賴關(guān)系為圖2中類型1時(shí)模型可以很快在80輪左右收斂；當(dāng)子任務(wù)數(shù)量為6個(gè)且依賴關(guān)系為圖2中類型2時(shí)模型可以在150輪左右收斂，比子任務(wù)數(shù)量為4個(gè)時(shí)收斂速度稍慢。值得注意的是，當(dāng)子任務(wù)數(shù)量為10個(gè)且依賴關(guān)系為圖2中類型3時(shí)模型在700輪左右才收斂且優(yōu)化能力下降約7%，表明此時(shí)工人數(shù)量不足導(dǎo)致算法的任務(wù)協(xié)作性能下降。如果工人數(shù)量固定數(shù)量為20個(gè)時(shí)，繼續(xù)增加子任務(wù)數(shù)量和依賴關(guān)系復(fù)雜度，模型的收斂性將會(huì)較難保證，即此時(shí)較難訓(xùn)練得到最佳協(xié)作策略。

4.2 對(duì)比算法

為了評(píng)估本文的TCSP算法性能，選取以下兩種算法作為基線進(jìn)行對(duì)比實(shí)驗(yàn)：

a）時(shí)間約束下多任務(wù)分配算法（MATC-GA）［25］。MATC-GA將有時(shí)間約束下的多任務(wù)分配構(gòu)建為組合優(yōu)化問題，采用基于GA的分配方案實(shí)現(xiàn)多任務(wù)協(xié)作分配，以最大化MCS平臺(tái)的效用。MATC-GA算法從時(shí)間約束角度分析任務(wù)間的依賴關(guān)系，是較典型的有約束任務(wù)協(xié)作方法。

b）參與者密度約束下全局貪婪算法（GGA）［26］。GGA是一種采用全局貪婪機(jī)制對(duì)所有任務(wù)進(jìn)行分配的算法，其通過模糊邏輯控制方法得到不同時(shí)空的參與者密度，進(jìn)而獲得所有任務(wù)的效用以對(duì)所有任務(wù)進(jìn)行分配。GGA算法從參與者密度約束角度進(jìn)行全局貪婪任務(wù)分配，可以從全局解決多任務(wù)協(xié)作問題。

4.3 評(píng)估性能指標(biāo)

為了驗(yàn)證TCSP算法的有效性，分別從任務(wù)完成率、任務(wù)平均完成時(shí)間和平均感知成本三項(xiàng)指標(biāo)對(duì)算法進(jìn)行評(píng)估，分析工人數(shù)量變化對(duì)指標(biāo)的影響。

a）任務(wù)完成率。定義為完成任務(wù)數(shù)與平臺(tái)執(zhí)行總?cè)蝿?wù)數(shù)量的比值，其值介于［0，1］，用來衡量不同條件下平臺(tái)完成任務(wù)能力的大小，其中完成任務(wù)數(shù)為包含多個(gè)依賴子任務(wù)的任務(wù)數(shù)量。

任務(wù)完成率=完成任務(wù)數(shù)總?cè)蝿?wù)數(shù)

b）平均完成時(shí)間。定義為任務(wù)完成總時(shí)間與完成任務(wù)數(shù)的比值，用于評(píng)估平臺(tái)有效完成單個(gè)任務(wù)速度的快慢，其中任務(wù)完成總時(shí)間為成功任務(wù)的執(zhí)行時(shí)間和失敗任務(wù)的執(zhí)行時(shí)間之和。

平均完成時(shí)間=任務(wù)完成總時(shí)間完成任務(wù)數(shù)

c）平均感知成本。定義為完成協(xié)作任務(wù)所需要的激勵(lì)總成本和時(shí)間總成本之和與平臺(tái)總?cè)蝿?wù)數(shù)的比值，表示平均每個(gè)任務(wù)被完成所產(chǎn)生代價(jià)的大小，其中成本之和為平臺(tái)完成所有協(xié)作任務(wù)而產(chǎn)生的成本累加。

平均感知成本=激勵(lì)總成本+時(shí)間總成本總?cè)蝿?wù)數(shù)

4.4 對(duì)比實(shí)驗(yàn)結(jié)果與分析

為說明工人數(shù)量變化對(duì)實(shí)驗(yàn)結(jié)果的影響，本文固定平臺(tái)中任務(wù)數(shù)為20，每個(gè)任務(wù)的子任務(wù)數(shù)量為6，工人感知半徑為8。通過改變工人的數(shù)量從任務(wù)完成率、平均完成時(shí)間和平均感知成本三個(gè)方面對(duì)TCSP、MATC-GA和GGA算法進(jìn)行對(duì)比分析。為了避免隨機(jī)性因素產(chǎn)生的影響，實(shí)驗(yàn)結(jié)果均為多次重復(fù)實(shí)驗(yàn)產(chǎn)生結(jié)果的平均值。

圖5顯示了工人數(shù)量變化對(duì)任務(wù)完成率的影響?？梢钥闯?，TCSP算法具有更高的任務(wù)完成率，GGA算法完成率由低逐漸變高，MATC-GA算法完成率具有波動(dòng)性。其原因是，GGA在工人數(shù)量很少的條件下不能有效地在任務(wù)感知半徑內(nèi)尋找到合適的工人，當(dāng)工人數(shù)量增加到30個(gè)，其找到合適工人的可能性增加，因此任務(wù)完成率也開始增加。MATC-GA是通過基因的交叉變異來對(duì)任務(wù)協(xié)作目標(biāo)進(jìn)行優(yōu)化，但由于有約束的依賴任務(wù)每次完成的路徑存在多條，使算法的適應(yīng)度函數(shù)具有多個(gè)優(yōu)化目標(biāo)，進(jìn)而導(dǎo)致其分配結(jié)果存在多種可能，所以MATC-GA任務(wù)完成率的波動(dòng)性較其他算法大。隨著工人數(shù)量的增加，三個(gè)算法的任務(wù)完成率都在逐漸增加，其中TCSP在工人為30個(gè)的條件下很快趨于穩(wěn)定，GGA在工人數(shù)為80左右時(shí)與TCSP的任務(wù)完成率都逐漸穩(wěn)定到70%左右；MATC-GA的任務(wù)完成率具有波動(dòng)性，但當(dāng)工人數(shù)量增加時(shí)其平均完成率也在逐漸上升。

圖6顯示了工人數(shù)量變化對(duì)平均完成時(shí)間的影響。可以看出，TCSP算法的平均完成時(shí)間低于MATC-GA和GGA算法。其原因是GGA從全局的角度對(duì)所有的任務(wù)和工人進(jìn)行貪心匹配，容易使單個(gè)子任務(wù)陷入局部最優(yōu)。MATC-GA在面對(duì)依賴約束的任務(wù)時(shí)不能在模型的優(yōu)化迭代策略上進(jìn)行有效的改進(jìn)，只能在適應(yīng)度函數(shù)上進(jìn)行限制，雖然也可以進(jìn)行任務(wù)協(xié)作分配，但是這個(gè)約束不能在決策方法上體現(xiàn)，所以限制了算法的性能。本文算法一方面針對(duì)任務(wù)對(duì)工人進(jìn)行全局感知質(zhì)量評(píng)估，選取感知質(zhì)量最高的任務(wù)作為當(dāng)前執(zhí)行任務(wù)，這有效地提高了任務(wù)的完成率；另一方面，本文算法2強(qiáng)化學(xué)習(xí)模型在訓(xùn)練的過程中將任務(wù)的約束關(guān)系用狀態(tài)空間表示并進(jìn)行訓(xùn)練，使得TCSP得到的最優(yōu)任務(wù)協(xié)作策略可以較好地泛化到不同的工人和任務(wù)情況中。隨著工人數(shù)量的增加，三個(gè)算法的平均完成時(shí)間都在逐漸減小，其中TCSP和GGA的平均完成時(shí)間在工人數(shù)為30左右都開始下降，并且TCSP比GGA更快地趨于穩(wěn)定。

圖7顯示了工人數(shù)量變化對(duì)平均感知成本的影響?？梢钥闯鲈诠と藬?shù)量較少時(shí)，TCSP算法比GGA的平均感知成本更快地收斂。其原因是，GGA進(jìn)行全局貪心搜索，不能綜合考慮激勵(lì)成本和時(shí)間成本，容易陷入局部最優(yōu)，但當(dāng)工人數(shù)達(dá)到一定閾值之后，由于貪心算法而產(chǎn)生的局部性影響逐漸變小，所以其與TCSP的平均感知成本逐漸接近。隨著工人數(shù)量的增加，三個(gè)算法的平均感知成本都在逐漸減小。當(dāng)工人數(shù)量不足30個(gè)，GGA比TCSP的平均感知成本高18%左右，其原因是，TCSP中的任務(wù)協(xié)作策略綜合考慮了激勵(lì)成本和時(shí)間成本兩種因素進(jìn)行工人分配，而GGA只是簡(jiǎn)單地考慮感知范圍內(nèi)能夠完成任務(wù)的工人，導(dǎo)致此算法不能更好地綜合考慮激勵(lì)成本和時(shí)間成本兩種因素。當(dāng)工人數(shù)大于40個(gè)，TCSP和GGA的平均感知成本都能趨于一個(gè)較接近的穩(wěn)定值。

5 結(jié)束語

在移動(dòng)群智感知研究中，隨著移動(dòng)群智感知中任務(wù)數(shù)量和復(fù)雜程度的增加，每個(gè)任務(wù)逐漸不再能獨(dú)立地完成，然而目前缺乏對(duì)任務(wù)間約束關(guān)系的研究。基于此，提出了基于感知質(zhì)量優(yōu)先級(jí)的在線任務(wù)協(xié)作方法，該方法首先使用貪婪算法計(jì)算感知質(zhì)量優(yōu)先級(jí)對(duì)全部任務(wù)進(jìn)行篩選以保證任務(wù)完成率，然后將選出任務(wù)中存在時(shí)間先后或執(zhí)行邏輯前后關(guān)系的多個(gè)子任務(wù)構(gòu)建為任務(wù)協(xié)作圖，并將其協(xié)作過程建模為有約束的馬爾可夫決策過程，通過強(qiáng)化學(xué)習(xí)算法求出最優(yōu)協(xié)作策略。仿真結(jié)果表明，提出的任務(wù)協(xié)作方法可以有效地對(duì)感知任務(wù)執(zhí)行過程進(jìn)行優(yōu)化并提升平臺(tái)效益。在未來的工作中應(yīng)考慮更多可能存在的約束關(guān)系對(duì)任務(wù)協(xié)作的影響，并探索新的優(yōu)化方法和理論基礎(chǔ)。

參考文獻(xiàn)：

[1]Ganti R K，Ye Fan，Lei Hui，et al.Mobile crowdsensing：current state and future challenges［J］.IEEE Communications Magazine，2011，49（11）：32-39.

［2]Dinh T A N，Nguyen A D，Nguyen T T，et al.Spatial-temporal coverage 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]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.

［4]Jovanovic＇ S，Jovanovic＇ M，koric＇ T，et al.A mobile crowd sensing application for hypertensive patients［J］.Sensors，2019，19（2）：https：//doi.org/10.3390/s19020400.

［5]A Sawafi Y，Touzene A，Day K，et al.Mobile Crowd Sensing RPL-based Routing Protocol for Smart City［J］.International Journal of Computer Networks and Communications，2020，12（2）：49-69.

［6]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.

［7]Yan Liu，Guo Bin，Wang Yang，et al.TaskMe：multi-task allocation in mobile crowd sensing［C］//Proc of ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York：ACM Press，2016：403-414.

［8]Song Zheng，Liu C H，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.

［9]Xiao Mingjun，Wu Jie，Huang Liusheng，et al.Online task assignment for crowdsensing in predictable mobile social networks［J］.IEEE Trans on Mobile Computing，2017，16（8）：2306-2320.

［10]Kang Yanrong，Miao Xin，Liu Kebin，et al.Quality-aware online task assignment in mobile crowdsourcing［C］//Proc of the 12th IEEE International Conference on Mobile Ad Hoc and Sensor Systems.Piscataway，NJ：IEEE Press，2015：127-135.

［11]Li Yanqiang，Zhu Bin，Huang Tao，et al.Mota：multi-stage multi-task online assignment algorithm based on opportunistic crowdsensing［C］//Proc of the 16th International Computer Conference on Wavelet Active Media Technology and Information Processing.Piscataway，NJ：IEEE Press，2019：345-348.

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

［13]Gong Wei，Zhang Baoxian，Li Cheng.Location-based online task scheduling in mobile crowdsensing［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2017：1-6.

［14]Wang Jiangtao，Wang Yasha，Zhang Daqing，et al.Multi-task allocation in mobile crowd sensing with individual task quality assurance［J］.IEEE Trans on Mobile Computing，2018，17（9）：2101-2113.

［15]Jiang Weijin，Chen Junpeng，Liu Xiaoliang，et al.Participant Recruitment Method Aiming at Service Quality in Mobile Crowd Sensing［J］.Wireless Communications and Mobile Computing，2021，2021：articleID 6621659.

［16]Wei Xiaohui，Wang Yongfang，Gao Shang，et al.Data quality aware task allocation with budget constraint in mobile crowdsensing［J］.IEEE Access，2018，6：48010-48020.

［17]李卓，徐哲，陳昕，等.面向移動(dòng)群智感知的位置相關(guān)在線多任務(wù)分配算法［J］.計(jì)算機(jī)科學(xué)，2019，46（6）：102-106.（Li Zhuo，Xu Zhe，Chen Xin，et al.Location-related online multi-task assignment algorithm for mobile crowd sensing［J］.Computer Science，2019，46（6）：102-106.）

［18]李卓，徐哲，陳昕，等.基于預(yù)測(cè)的機(jī)會(huì)群智感知多任務(wù)在線分配算法［J］.工程科學(xué)與技術(shù)，2018，50（5）：176-182.（Li Zhuo，Xu Zhe，Chen Xin，et al.Online multi-task assignment algorithm with prediction for opportunistic crowd sensing［J］.Advanced Engineering Sciences，2018，50（5）：176-182.）

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

［20]Zhu Weiping，Guo Wenzhong，Yu Zhiyong，et al.Multitask allocation to heterogeneous participants in mobile crowd sensing［J］.Wireless Communications & Mobile Computing，2018，2018：articleID 7218061.

［21]Wang Liang，Zhi Wenyu，Guo Bin.Mobile crowd sensing task optimal allocation：a mobility pattern matching perspective［J］.Frontiers of Computer Science，2018，12（2）：231-244.

［22]Li Zhidu，Liu Hailiang，Wang Ruyan.Service benefit aware multi-task assignment strategy for mobile crowd sensing［J］.Sensors，2019，19（21）：https：//doi.org/10.3390/s19214666.

［23]胡華，張強(qiáng)，胡海洋，等.基于Q-learning的移動(dòng)群智感知任務(wù)分配算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2018，24（7）：1774-1783.（Hu Hua，Zhang Qiang，Hu Haiyang，et al.Q-learning based sensing task assignment algorithm for mobile sensing system［J］.Computer Integrated Manufacturing Systems，2018，24（7）：1774-1783.）

［24]Melo F S.Convergence of Q-learning：a simple proof［EB/OL］.（2007-02-12）.http：//users.isr.ist.utl.pt/～mtjspaan/readingGroup/ProofQlearning.pdf.

［25]Li Xin，Zhang Xinglin.Multi-Task Allocation Under Time Constraints in Mobile Crowdsensing［J］.IEEE Transactions on Mobile Computing，1 April 2021，20（4）：1494-1510.

［26]楊桂松，張楊林，何杏宇.面向模糊邏輯控制的移動(dòng)群智感知多任務(wù)分配［J］.小型微型計(jì)算機(jī)系統(tǒng)，2020，41（10）：2068-2074.（Yang Guisong，Zhang Yanglin，He Xingyu.Multi-task allocation based on fuzzy logic controlin mobile crowd sensing［J］.Journal of Chinese Computer Systems，2020，41（10）：2068-2074.）

收稿日期：2023-02-24；

修回日期：2023-04-11

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61802257，61602305）；上海市自然科學(xué)基金資助項(xiàng)目（18ZR1426000，19ZR1477600）；南通市科技局社會(huì)民生計(jì)劃項(xiàng)目（MS12021060）；浦東新區(qū)科技發(fā)展基金產(chǎn)學(xué)研專項(xiàng)資助項(xiàng)目（PKX2021-D10）；敏捷智能計(jì)算四川省重點(diǎn)實(shí)驗(yàn)室開放式基金資助項(xiàng)目

作者簡(jiǎn)介：楊桂松（1982-），男，河南漯河人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)槲锫?lián)網(wǎng)與普適計(jì)算等；白高磊（1990-），男，河南禹州人，碩士研究生，主要研究方向?yàn)橐苿?dòng)群智感知和共識(shí)協(xié)同方法；何杏宇（1984-），女（通信作者），湖南岳陽人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)槲锫?lián)網(wǎng)和移動(dòng)群智計(jì)算（xy_he@usst.edu.cn）；賈明權(quán)（1982-），男，四川合江人，高級(jí)工程師，博士，主要研究方向?yàn)橄冗M(jìn)智能計(jì)算.