楊桂松 白高磊 何杏宇 賈明權

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

關鍵詞：移動群智感知； 依賴關系； 感知質量優(yōu)先級； 在線任務協(xié)作； 強化學習

中圖分類號：TP393?? 文獻標志碼：A

文章編號：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 引言

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

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

2 任務感知質量優(yōu)先級

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

2.1 時空覆蓋率

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

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

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

任務TO的所有子任務可以被當前時空范圍內的工人覆蓋的數(shù)量計算如下：

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

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

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

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

coverTo=FCToQTo（4）

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

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

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

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

DatTo=1LenTo（6）

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

QuaTo=σCoverTo+ξDatTo（7）

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

2.3 任務優(yōu)先級調度算法

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

算法1 任務優(yōu)先級調度算法

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

輸出：被選取的任務Tprior。

a）如果有新的任務請求，將此任務加入隊列；

b）從當前任務隊列隊頭取出任務To；

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

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

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

f）如果隊列不為空，跳轉至步驟b）；

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

h）按照QuaTo從大到小的順序將任務重新加入隊列；

i）采用貪心策略，將隊頭任務出隊并賦值給Tprior。

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

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

3.1.1 子任務激勵成本

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

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

其中：向量pri為平臺制定支付每類傳感器的單價。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.3 優(yōu)化目標

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

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

3.2 基于強化學習的子任務協(xié)作方法

3.2.1 強化學習進行子任務協(xié)作

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

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

3.2.2 依賴關系約束的狀態(tài)、動作空間等

1）有約束的動作空間

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

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

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

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

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

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

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

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

3）獎勵函數(shù)的設計

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

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

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

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

Q學習算法是通過迭代訓練更新Q表格，使最終狀態(tài)的Q值可以逼近目標值。Q學習算法當前狀態(tài)值更新規(guī)則，計算如下：

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)目標值，其為下一狀態(tài)值最大Q值和對應的工人任務立即獎勵之和； r（s′（2m），a′）+γmaxQ（s′（2m），a′）－Q（s（2m），a）為Q學習算法的時序差分誤差；Q（s（2m），a）的更新為當前值與誤差值的和；γ為折扣因子，0≤γ≤1;α為學習率，0≤α≤1。

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

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

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

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

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

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

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

a）初始化Q表格；

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗及分析

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

4.1 TCSP算法特性分析

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

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

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

4.2 對比算法

為了評估本文的TCSP算法性能，選取以下兩種算法作為基線進行對比實驗：

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

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

4.3 評估性能指標

為了驗證TCSP算法的有效性，分別從任務完成率、任務平均完成時間和平均感知成本三項指標對算法進行評估，分析工人數(shù)量變化對指標的影響。

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

任務完成率=完成任務數(shù)總任務數(shù)

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

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

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

平均感知成本=激勵總成本+時間總成本總任務數(shù)

4.4 對比實驗結果與分析

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

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

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

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

5 結束語

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

參考文獻：

[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]李卓，徐哲，陳昕，等.面向移動群智感知的位置相關在線多任務分配算法［J］.計算機科學，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]李卓，徐哲，陳昕，等.基于預測的機會群智感知多任務在線分配算法［J］.工程科學與技術，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]胡華，張強，胡海洋，等.基于Q-learning的移動群智感知任務分配算法［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]楊桂松，張楊林，何杏宇.面向模糊邏輯控制的移動群智感知多任務分配［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

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

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