楊明川 朱敬華,2 李元婧 奚赫然,2

1（黑龍江大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150006）

2（數(shù)據(jù)庫與并行計算重點實驗室（黑龍江大學(xué)）哈爾濱 150006）

（mrvincenty@163.com）

移動群智感知（mobile crowdsensing,MCS）是Ganti等人[1]提出的，是一種在用戶或社區(qū)之間感知和共享數(shù)據(jù)的新方法.Guo 等人[2]給MCS 更為明確的定義：“MCS 是一種新的感知范式，使普通公民能夠貢獻(xiàn)從移動設(shè)備感知或生成的數(shù)據(jù)，聚合和融合云中的數(shù)據(jù)，用于人群智能提取和以人為中心的服務(wù)交付.”[3]隨著高性能的便攜式移動設(shè)備與高速智能網(wǎng)絡(luò)的普及，移動群智感知技術(shù)快速發(fā)展并深入到智慧醫(yī)療、交通流量預(yù)測以及智慧城市等各個領(lǐng)域，需要采集處理的數(shù)據(jù)集也日漸龐大，MCS 系統(tǒng)需要大量用戶的參與和貢獻(xiàn)[4]，如何在數(shù)量龐大的參與者中選擇合適的參與者完成給定的感知計算任務(wù)，且最大化平臺和用戶的收益顯得格外重要.任務(wù)分配系統(tǒng)主要由3 部分組成：平臺（任務(wù)發(fā)布者）、工人（用戶，攜帶移動智能設(shè)備負(fù)責(zé)采集感知數(shù)據(jù)）和任務(wù)（如收集某地區(qū)的空氣質(zhì)量數(shù)據(jù)、監(jiān)測某路段的交通流量等）.如圖1 所示，任務(wù)由平臺基于一定的收益計算機制分配給工人，然后工人利用移動智能設(shè)備到指定任務(wù)點進(jìn)行相關(guān)感知數(shù)據(jù)的收集并上傳到平臺獲取相應(yīng)報酬.一方面，考慮到任務(wù)的時效性以及預(yù)算，任務(wù)應(yīng)當(dāng)被合理地分配給合適的工人，保證任務(wù)分配合理化的同時盡可能最大化平臺總收益；另一方面，工人上傳信息時通常無法避免暴露自身位置等隱私信息.因此，在MCS 系統(tǒng)中，合理的任務(wù)分配機制與工人信息的隱私保護(hù)問題尤為重要.傳統(tǒng)的任務(wù)分配算法，如螞蟻算法、貪婪算法，適合于小規(guī)模數(shù)據(jù)集，應(yīng)用于工人與任務(wù)信息固定的靜態(tài)系統(tǒng)，但實際問題中工人與任務(wù)的位置、狀態(tài)信息會不斷改變，因此，深度學(xué)習(xí)被越來越多的研究者引入到這樣的動態(tài)系統(tǒng)中來解決相應(yīng)的動態(tài)規(guī)劃問題.

Fig.1 Diagram of MCS task assignment system圖1 MCS 任務(wù)分配系統(tǒng)圖示

深度強化學(xué)習(xí)（deep reinforcement learning,DRL）可以基于過去的經(jīng)驗，通過智能體選擇動作與環(huán)境交互并獲得相應(yīng)的狀態(tài)和回報[5]，在每次進(jìn)行決策的過程中，智能體的策略選擇的概率分布不斷調(diào)整，最終達(dá)到最優(yōu)的全局策略.因此在動態(tài)的MCS 問題中，DRL 往往能發(fā)揮更好的性能.在DRL 的眾多方法中，DQN（deep Q-network）[6]和 A3C（asynchronous advantage actor-critic）[7]可以表現(xiàn)出良好性能，但僅限在離散的動作空間中；DDPG（deep deterministic policy gradient）[8]是一種離線的、確定性的方法，相對不適合需要實時控制解決方案的動態(tài)場景；TRPO（trust region policy optimization）[9]采用信任區(qū)域方法，其性能優(yōu)于許多隨機在線策略梯度方法，更適合于需要更多探索的場景；PPO（proximal policy optimization）[10]是一種無模型的、基于策略的、基于梯度的強化學(xué)習(xí)方法，它在連續(xù)控制問題的表現(xiàn)極其優(yōu)異，并具有TRPO 的相應(yīng)優(yōu)點且實現(xiàn)復(fù)雜性要低得多.本文的算法采用了PPO 框架，該框架可以更好地適配離散型和連續(xù)型的狀態(tài)/動作集合，甚至在復(fù)合型的狀態(tài)/動作集合的表現(xiàn)也較為良好，并且相對于其他的DRL方法，PPO 的表現(xiàn)也較為優(yōu)異，具有更快的收斂性.

同時，考慮到工人在與平臺進(jìn)行數(shù)據(jù)交互時往往會暴露自己的移動軌跡信息，因而本文采用本地差分隱私在工人與平臺的交互中進(jìn)行隱私保護(hù).差分隱私的概念最早由Dwork[11]提出，建立在嚴(yán)格的數(shù)學(xué)理論基礎(chǔ)上，對隱私保護(hù)提供了量化的評估方法和嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明.本文方法在平臺與工人的信息交互中，利用本地差分隱私的方法，對其位置信息加入隨機噪聲，最大限度地保護(hù)工人的隱私信息.

本文是面向MCS 任務(wù)分配問題，使用DRL 與差分隱私方法在保護(hù)隱私的前提下獲得優(yōu)化的任務(wù)分配策略.將動態(tài)環(huán)境下的任務(wù)分配問題定義為一個基于離散型數(shù)據(jù)集來進(jìn)行動態(tài)規(guī)劃的優(yōu)化問題，并使用基于DRL 的算法來解決動態(tài)環(huán)境下的任務(wù)分配問題.具體來說，在每次迭代開始時，該算法觀察了之前迭代中平臺的分配策略、平臺收益、工人收益、現(xiàn)有任務(wù)信息以及工人信息.根據(jù)觀察結(jié)果，由基于DRL 的算法來決定工人分配到的任務(wù)以及任務(wù)的順序，在此過程中利用差分隱私來對工人相關(guān)隱私信息做了模糊化處理.本文的目標(biāo)是最大化平臺的總收益和工人收益，被定義為工人收益與平臺總收益的聯(lián)合約束問題，此外還考慮了隱私保護(hù)的相關(guān)問題.本文的主要貢獻(xiàn)總結(jié)為4 個方面：

1）將MCS 動態(tài)場景下的任務(wù)分配問題建模為一個多目標(biāo)優(yōu)化問題，并證明為NP-hard 問題.充分考慮了在MCS 的任務(wù)分配問題中，工人與任務(wù)狀態(tài)信息不斷變化的動態(tài)系統(tǒng)，以及工人與平臺進(jìn)行數(shù)據(jù)交互的隱私保護(hù)的必要性.

2）提出基于DRL 的PPO 方法求解該優(yōu)化問題.相比于傳統(tǒng)方法，DRL 在中大型數(shù)據(jù)集的MCS 問題中表現(xiàn)性能良好、收斂性好，能更快達(dá)到最優(yōu)解，同時考慮了真實的MCS 中工人和任務(wù)的動態(tài)性，利用DRL 方法更適用于解決此類動態(tài)的、非確定性的MCS 問題.

3）提出基于差分隱私的任務(wù)分配方法.在工人的智能移動設(shè)備與中央服務(wù)器交互中利用本地差分隱私的方法，對工人的位置信息加入隨機噪聲，模糊化工人位置信息，進(jìn)而解決中央服務(wù)器收集工人信息時存在的隱私泄露問題.

4）通過實驗評估本文方法的有效性和高性能.通過模擬數(shù)據(jù)集的實驗，對比了傳統(tǒng)方法與現(xiàn)有方法，驗證了本文的模型具有穩(wěn)定性能，且收斂效果較好；此外還進(jìn)行了消融實驗，證明了加入隱私保護(hù)方法的有效性.

1 相關(guān)工作

1.1 傳統(tǒng)任務(wù)分配方法

Cheung 等人[12]研究了時間敏感和位置依賴的感知任務(wù)的分配問題.考慮到具有不同初始位置、移動成本和速度以及聲譽級別的異構(gòu)用戶，提出了一種貪婪算法來計算該問題的近似解.該算法要求每個用戶專注于自己的收益，并向用戶提供一個異步的分布式算法來計算用戶的移動性計劃.該算法的設(shè)計目標(biāo)是最大化用戶收益，但無法適用于工人狀態(tài)信息變化的動態(tài)系統(tǒng).在文獻(xiàn)[13]中，Li 等人提出了基于蟻群算法ACO（ant colony optimization）的啟發(fā)式多任務(wù)調(diào)度算法來確定任務(wù)調(diào)度策略，對工人福利的計算模型進(jìn)行理論分析，利用基于ACO 的啟發(fā)式多任務(wù)調(diào)度算法來確定任務(wù)調(diào)度策略，以最大限度地提高工人的利益.但該方法同樣僅適用于靜態(tài)系統(tǒng)，對于動態(tài)系統(tǒng)，越來越多的研究者傾向于基于DRL 的算法[14-15].

1.2 基于DRL 的算法

2013 年谷歌的DeepMind 團(tuán)隊發(fā)表了利用強化學(xué)習(xí)玩Atari 游戲的文章[16]，DRL 開始炙手可熱，相關(guān)算法被更多的研究者引入到各個領(lǐng)域.Kim 等人[17]將DRL 的方法應(yīng)用于無人機的任務(wù)分配問題上，用基于Q 值的深度強化學(xué)習(xí)算法 DQN 來實現(xiàn)快速策略收斂，從而有可能適用于更大規(guī)模的系統(tǒng)，進(jìn)而解決難以量化的由隨機環(huán)境引起的無人機移動性的隨機性問題.Tao 等人[18]使用雙深度Q 網(wǎng)絡(luò)（double deep Q-network,DDQN）來解決任務(wù)分配問題，作為一個具有時間窗的路徑規(guī)劃問題，考慮了感知任務(wù)的位置依賴性和時間敏感性，以及工人在最大旅行距離方面的資源限制.在文獻(xiàn)[19]中，Patel 等人針對聯(lián)邦環(huán)境下計算資源分配問題，提出了一個旨在使系統(tǒng)總成本最小化的優(yōu)化問題，并將其定義為訓(xùn)練時間和能量消耗的加權(quán)和.考慮到非線性約束的難度和網(wǎng)絡(luò)質(zhì)量的不穩(wěn)定，該團(tuán)隊設(shè)計了一種基于DRL的經(jīng)驗驅(qū)動算法，該算法可以在不了解網(wǎng)絡(luò)質(zhì)量的情況下收斂到接近最優(yōu)解.

1.3 差分隱私

在文獻(xiàn)[11]中，差分隱私的概念被Dwork 首次提出，該文章通過嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明，可以保證數(shù)據(jù)變化時用戶隱私不受攻擊者所知的背景知識的影響.之后Dwork 對原有差分隱私的概念進(jìn)行改進(jìn)，提出本地化差分隱私[20]，將信息的隱私處理工作轉(zhuǎn)移到用戶端，對差分隱私進(jìn)行量化，每個用戶單獨對敏感數(shù)據(jù)進(jìn)行處理，使得隱私保護(hù)更為徹底.Chen 等人[21]將本地差分隱私應(yīng)用于位置數(shù)據(jù)保護(hù)，通過對位置數(shù)據(jù)加入拉普拉斯噪聲，實現(xiàn)對位置數(shù)據(jù)的隱私保護(hù).Wang 等人[22]提出了一種基于差分隱私以及Hilbert曲線的位置保護(hù)方法，將位置映射到一維空間中，通過拉普拉斯噪聲對位置信息進(jìn)行擾動，將處理后的位置信息發(fā)送給平臺來實現(xiàn)位置信息保護(hù).

2 問題定義

假設(shè)在該系統(tǒng)中有n個攜帶智能移動設(shè)備的工人W={w1,w2,…,wn}，m個任務(wù)V={v1,v2,…,vm}.進(jìn)而工人的智能移動設(shè)備可用Dev={Dev1,Dev2,…,Devn}表示，并定義第i個工人由表示，第j個任務(wù)由表示，其中（xi,yi）和（xj,yj）表示坐標(biāo)，Pwi是第i個工人該時刻所有任務(wù)的開銷集合，是該工人當(dāng)前被分配到的任務(wù)隊列，表示第j個任務(wù)所需時間，表示該任務(wù)的獎勵，表示完成該任務(wù)平臺可獲取的收益.該系統(tǒng)是動態(tài)的，即工人與任務(wù)狀態(tài)位置信息不斷改變，在不同時刻下工人完成已有任務(wù)后會有“閑置狀態(tài)”，此時需要在每次迭代時將“閑置”的工人重新放入在“待分配”工人的隊列里，同時每個工人可接受的任務(wù)也是有限的，這需要根據(jù)工人的報酬以及任務(wù)對于工人的收益進(jìn)行約束，例如距離較遠(yuǎn)的任務(wù)的開銷大于收益則不會分配給工人，進(jìn)而間接限制了工人所接受任務(wù)的數(shù)量，這就避免了任務(wù)分配不均的問題.

工人完成任務(wù)是有時效性的，因此在每個工人與任務(wù)里加入了時間戳，記錄工人完成任務(wù)的時間，并標(biāo)注出每個任務(wù)的完成時間限制.此外，考慮到工人開銷的差異性，即任務(wù)對于每個工人的開銷應(yīng)該是不一樣的，因而加入了笛卡兒坐標(biāo)系，為每個工人和任務(wù)設(shè)置了位置坐標(biāo)，每個工人依據(jù)距離和自己未完成的任務(wù)量計算任務(wù)開銷.例如對于第i個工人，計算第m個任務(wù)開銷時，距離越遠(yuǎn)，任務(wù)開銷越大，自身未完成任務(wù)量（加權(quán)后的任務(wù)數(shù)量）越多，任務(wù)開銷越大，反之亦然.這里，定義第i個工人對于第j個任務(wù)的開銷為:

其中θi表示該工人的完成任務(wù)所需總時間，ξ表示第i個工人到第j個任務(wù)點的歐氏距離權(quán)重，α為時間權(quán)重，這里體現(xiàn)出了每個工人的任務(wù)開銷的差異性.

可定義第i個工人的收益以及平臺總收益為

其中ri表示第i個工人的收益，Rp表示此時平臺總收益，Vout表示此時所有被分配出去的任務(wù)集合.

最終，將這一個基于離散型數(shù)據(jù)集的動態(tài)策略優(yōu)化問題定義為

其中式（5）代表最大化平臺總收益同時也要最大化當(dāng)前第i個工人的收益，λ1與λ2為兩者的收益權(quán)重，在式（6）中的約束代表第i個工人完成第j個任務(wù)時的報酬要保證不小于最小值Pmin，且Pmin是一個大于0 的常量.

從式（3）（4）中可以看出平臺總收益與工人的收益是負(fù)相關(guān)的，而在本文的問題中，更希望兩者都能達(dá)到最大化，因此采用聯(lián)合優(yōu)化方式，通過調(diào)節(jié)權(quán)重值來平衡雙方利益，實現(xiàn)雙方的納什均衡.

由上述的問題定義可證明MCS 的任務(wù)分配問題是一個NP-hard 問題.首先假設(shè)一個特殊情況，即只有一個工人，任務(wù)集合不變.然后，該工人有一個設(shè)定的最大旅行距離，且支付給工人的報酬設(shè)置為0.最后，平臺的總利潤等于該工人完成任務(wù)的報酬，這也映射到定向運動問題，且該問題已被證明為NP-hard問題[23]，則可推論本文的問題同樣是NP-hard 問題.

3 系統(tǒng)模型及算法

3.1 系統(tǒng)模型概述

本文的系統(tǒng)模型如圖2 所示，任務(wù)發(fā)布者在模型中作為中央服務(wù)器，每個工人的智能移動設(shè)備可看作分布式的小型處理器.在整個系統(tǒng)中，中央服務(wù)器與各個工人的移動設(shè)備在隱私保護(hù)的環(huán)境中進(jìn)行信息交互.首先，每個工人智能移動設(shè)備將相關(guān)信息經(jīng)過差分隱私的處理后傳至中央服務(wù)器.之后，中央服務(wù)器獲取該時刻全局的工人與任務(wù)的狀態(tài)信息，經(jīng)過基于DRL 的動態(tài)策略優(yōu)化算法，制定相應(yīng)的分配策略，最終傳給各工人智能移動設(shè)備.同時在交互過程中，中央服務(wù)器中采用PPO 的算法進(jìn)行訓(xùn)練并決策，在每輪訓(xùn)練時考慮了系統(tǒng)的動態(tài)性與差異性問題，即不同工人對于相同的任務(wù)會受到距離以及未完成的任務(wù)量影響，進(jìn)而每個任務(wù)對不同工人的開銷應(yīng)是不一樣的，且在每輪迭代時可能會產(chǎn)生完成了當(dāng)前任務(wù)的“空閑”工人，在模型定義中考慮了以上問題，在每輪迭代會動態(tài)更新全局信息，最終得到全局最優(yōu)的策略.

Fig.2 Illustration of the system model圖2 系統(tǒng)模型圖示

3.2 PPO 模型

中央服務(wù)器中應(yīng)用了基于DRL 的動態(tài)策略優(yōu)化算法PPO 進(jìn)行決策推演.傳統(tǒng)的PPO 算法源于A-C網(wǎng)絡(luò)[24]的思想，如圖3 所示，該算法由actor 網(wǎng)絡(luò)和critic 網(wǎng)絡(luò)構(gòu)成，每一次迭代時，actor 網(wǎng)絡(luò)會根據(jù)一定的動作決策概率分布進(jìn)行動作選擇，并與環(huán)境進(jìn)行交互，獲得該時刻的狀態(tài)和相應(yīng)的回報，此時critic 網(wǎng)絡(luò)將根據(jù)動作、狀態(tài)和回報的集合計算相應(yīng)的收益函數(shù)（有時是TD-error，用于評價actor 網(wǎng)絡(luò)的動作），并傳給actor 網(wǎng)絡(luò)和環(huán)境，actor 網(wǎng)絡(luò)基于此調(diào)整動作的決策概率分布，并進(jìn)行下一步動作選擇，最終獲得最優(yōu)策略.

Fig.3 Block diagram of A-C network圖3 A-C 網(wǎng)絡(luò)的框架圖

在本文的算法中，將傳統(tǒng)PPO 框架做了調(diào)整，即在收益函數(shù)的定義上采用了雙約束.動作空間、狀態(tài)空間以及回報約束定義為：

1）動作空間.動作集中包含了工人與任務(wù)的匹配信息，并采用2 維向量表來表示，其中定義第i個工人在第k次迭代時被分配的任務(wù)集合為同時，每個工人設(shè)備中將存儲任務(wù)分配記錄以及任務(wù)完成順序.每次迭代時由中央服務(wù)器決策進(jìn)行分配，中央服務(wù)器依據(jù)上一輪交互所得到的全局信息（工人和任務(wù)數(shù)量、工人報酬、任務(wù)收益等），計算平臺總收益，并進(jìn)行匹配.其定義為

2）狀態(tài)空間.狀態(tài)集合中，記錄了工人與任務(wù)的相關(guān)信息（工人的任務(wù)時序、各任務(wù)的收益、雇傭工人的開銷、可用工人數(shù)量和剩余任務(wù)數(shù)量等），這里由第k個狀態(tài)可用工人集合Wk與可用任務(wù)集合Vk來表示.每次迭代開始，每個工人根據(jù)中央服務(wù)器傳遞的數(shù)據(jù)，計算各個任務(wù)對于自己的開銷與收益，并于中央服務(wù)器進(jìn)行交互，更新此時的本地信息以及中央服務(wù)器的全局信息.綜上所述，將狀態(tài)集合定義為

3）回報約束.參照式（5）的聯(lián)合約束，力求保證平臺收益最大化的同時，盡可能增加工人的累積收益.將該問題視為平臺與工人間非合作性競爭的納什均衡問題.將平臺總收益的計算定義為平臺整體收益減去所有工人開銷，而單個工人的收益定義為工人獲得報酬減去完成任務(wù)的開銷.回報約束中的平臺總收益的優(yōu)先級高于單個工人優(yōu)先級，此處根據(jù)收益權(quán)重進(jìn)行調(diào)整.這里回報約束定義為

其中Wout為已分配任務(wù)的工人集合，Wk為未分配的任務(wù)集合.

在PPO 模型的訓(xùn)練過程中，critic 網(wǎng)絡(luò)根據(jù)回報rk以及動作/狀態(tài)集合{a,s}計算其Value值以及優(yōu)勢函數(shù)Ak，進(jìn)而對于下一次actor 網(wǎng)絡(luò)中動作選擇的策略π進(jìn)行調(diào)整，相關(guān)定義為：

其中第k輪迭代時的價值函數(shù)為Valueπ（sk），γ為折扣率，為狀態(tài)轉(zhuǎn)換概率，Ak為此時的優(yōu)勢函數(shù)，λ為優(yōu)勢函數(shù)權(quán)重，最終損失函數(shù)可用Loss表示.

3.3 本地差分隱私

這里引入地理不可區(qū)分性的概念，即存在2 個位置點x和x′∈X，Z是X通過映射機制D的輸出結(jié)果，若D滿足地理不可區(qū)分性，則對所有歐幾里得距離d(x,x′) ≤r，其中r為該映射機制保護(hù)的范圍，報告位置點z∈Z，則有

式（14）（15）輸入為x和x′ 時，根據(jù)該映射機制D的查詢函數(shù)D（x）（z），將得到相同輸出z的概率.位置信息中應(yīng)用差分隱私是為了使真實位置點信息與其近似位置點信息擁有地理不可區(qū)分性，從而達(dá)到隱私保護(hù)的目的.

本文采用本地差分隱私的算法.首先，工人的移動設(shè)備定位當(dāng)前位置信息（xreal,yreal）.其次，根據(jù)當(dāng)前位置坐標(biāo)劃定模糊位置范圍，該范圍是一個以R為模糊半徑的圓形區(qū)域.在該范圍內(nèi)指定ε∈R2，根據(jù)機制D確定候選的位置坐標(biāo)集合，并根據(jù)拉普拉斯機制隨機噪聲，敏感度設(shè)為Δf，該噪聲服從（0,Δf/ε）的拉普拉斯分布.最后在候選坐標(biāo)集合中隨機選取模糊化后的位置坐標(biāo)（x,y），并作為位置信息上傳至平臺.

3.4 基于PPO 的任務(wù)分配算法

基于A-C 網(wǎng)絡(luò)的思想，利用PPO 模型訓(xùn)練并學(xué)習(xí)任務(wù)分配策略，該方法與本文的問題非常匹配，并已成功地應(yīng)用于許多其他領(lǐng)域.在DRL 的眾多策略優(yōu)化方法中，PPO 在易于實現(xiàn)樣本復(fù)雜性和易于調(diào)優(yōu)之間取得了平衡，以最小化目標(biāo)函數(shù)進(jìn)行計算和更新，同時確保與以前策略的偏差相對較小.因此，在本文算法中的策略優(yōu)化過程采用了PPO 算法.

在本文的模型里包括了一個歷史策略緩沖區(qū)Cache、策略π、actor 網(wǎng)絡(luò)與critic 網(wǎng)絡(luò)，在算法1 中展示了該模型算法的偽代碼.首先，初始化PPO 框架，隨機賦予actor 網(wǎng)絡(luò)與critic 網(wǎng)絡(luò)的相關(guān)參數(shù)相應(yīng)的初始值θa和θv，將θa作為初始的策略參數(shù)（行①）.隨后迭代開始，最大迭代次數(shù)為K（行②）.在環(huán)境中獲取當(dāng)前的可用工人集合Wk以及可用任務(wù)集合Vk的信息，其中工人的位置信息根據(jù)本地差分隱私已做模糊化處理，最終得到第k次迭代的狀態(tài)（行③～⑧）.然后，基于狀態(tài)sk根據(jù)當(dāng)前策略在actor 網(wǎng)絡(luò)中進(jìn)行動作選擇（行⑨），將此時的動作集合ak輸入到環(huán)境中計算相應(yīng)的回報rk以及下一輪的狀態(tài)集合sk+1（行⑩）.critic 網(wǎng)絡(luò)中計算Ak以及Valuek，并將集合{sk+1,sk,ak,rk,Ak,Valuek}存儲到歷史策略緩沖區(qū)Cache中（行?～?）.當(dāng)Cache裝滿時計算偏導(dǎo)數(shù)，并基于根據(jù)梯度上升策略更新策略參數(shù)θa（行?～?）.在從Cache中學(xué)習(xí)信息后，actor 網(wǎng)絡(luò)的新參數(shù)θa分配給策略進(jìn)行下一次采樣.同時，歷史策略緩沖區(qū)被清空（行?）.

算法1.基于PPO 的動態(tài)策略優(yōu)化算法.

4 實驗

4.1 實驗參數(shù)設(shè)置

本文選用Gowalla 和TaskMe 這2 個數(shù)據(jù)集進(jìn)行模擬實驗，從中提取部分?jǐn)?shù)據(jù)的位置以及時間信息，并將添加在一定范圍內(nèi)隨機生成的數(shù)據(jù)作為任務(wù)獎勵等其他信息，最終生成擁有2 000 個任務(wù)和1 000個工人的模擬數(shù)據(jù)集合.其中，每個任務(wù)的獎勵設(shè)置在8～20 的范圍內(nèi)并按照N～（12,4）的正態(tài)分布進(jìn)行隨機生成，任務(wù)的時間則設(shè)置在10～60 的范圍內(nèi)隨機生成.最后，根據(jù)實驗的不同要求，選用該數(shù)據(jù)集中部分任務(wù)以及工人的數(shù)據(jù)信息在一個200×200 的正方形傳感區(qū)域空間內(nèi)進(jìn)行模擬實驗.

首先，設(shè)置了不同的工人與任務(wù)數(shù)量下?lián)p失函數(shù)的對比實驗，目的是驗證工人與任務(wù)數(shù)量對損失函數(shù)的收斂性的影響.在一個200×200 的正方形傳感區(qū)域空間內(nèi)，分別測試了80 個任務(wù)和5 個工人、300個任務(wù)和15 個工人、800 個任務(wù)和30 個工人這3 種不同情境下的損失函數(shù).其次，與現(xiàn)有的傳統(tǒng)方法（貪婪算法、螞蟻算法）以及其他DRL 方法（DDQN）針對收斂速度、最大收益以及任務(wù)覆蓋率的對比實驗.該部分將螞蟻算法中螞蟻數(shù)、迭代次數(shù)和隨機選擇的概率分別設(shè)置為10，30 000，0.1，對于基于DDQN的算法將其重播內(nèi)存容量設(shè)為10 000 次，迭代次數(shù)設(shè)為30 000 次，隨機選擇的概率從0.9 開始，然后逐漸衰減到0.1.最后，通過消融實驗來驗證隱私保護(hù)的有效性.在該實驗中將本文算法與DDQN 的算法以及去除掉差分隱私時的算法進(jìn)行比較，實驗設(shè)置參數(shù)與對比實驗相同.

4.2 模型損失

本節(jié)進(jìn)行了不同工人數(shù)量以及任務(wù)數(shù)量的模擬實驗，圖4（a）中迭代次數(shù)在100 次以內(nèi)，大約在第70次時達(dá)到收斂；圖4（b）中模型在迭代次數(shù)約120 次時達(dá)到收斂；圖4（c）中在迭代280 次時達(dá)到收斂.可以看出，該算法收斂效果主要受到工人與任務(wù)的數(shù)量影響，隨著其數(shù)量的增多，收斂速度將變慢.

Fig.4 System loss for different numbers of tasks and workers圖4 任務(wù)與工人不同數(shù)量下的系統(tǒng)損失

4.3 對比實驗

本節(jié)實驗不僅針對傳統(tǒng)MCS 任務(wù)分配方法（即螞蟻算法和貪婪算法的對比），而且加入了同為基于DRL 的任務(wù)分配算法（即基于DDQN 的算法），在任務(wù)覆蓋率、性能、收斂性以及最大收益上做了相應(yīng)對比實驗.在圖5 中，可以看到基于DDQN 以及基于PPO 的2 種DRL 算法在系統(tǒng)平均開銷的收斂情況，結(jié)果表示基于DDQN 的算法雖然可以比本文算法能更快收斂，但本文算法可以達(dá)到更小的平均系統(tǒng)開銷.圖6 展示了4 種算法的平臺收益情況，貪婪算法和蟻群算法由于是靜態(tài)的算法，因而不需要多輪迭代，但其平臺收益與基于DRL 的算法相比差距甚遠(yuǎn)；而基于DDQN 的算法同樣有更快的收斂性，但本文的基于PPO 的算法可以最終達(dá)到最大收益.

Fig.5 Comparison of average system costs圖5 平均系統(tǒng)開銷的比較

Fig.6 Comparison of maximum profits圖6 最大收益的比較

首先引入任務(wù)覆蓋率的概念：當(dāng)一個任務(wù)在其可接受的時間范圍內(nèi)被分配出去且完成，則可稱為該任務(wù)被覆蓋.因此任務(wù)覆蓋率可被定義為被分配掉的任務(wù)數(shù)與總?cè)蝿?wù)數(shù)的比值.如表1 所示，在平臺最大利潤和任務(wù)覆蓋率上，基于DDQN 和PPO 的2種DRL 算法均遠(yuǎn)高于貪婪算法和蟻群算法等傳統(tǒng)方法，且基于PPO 算法比基于DDQN 的算法表現(xiàn)更為優(yōu)異.圖7～9 展示了4 種算法在平均開銷、總開銷以及工人平均收益上的對比，結(jié)果表明本文的基于PPO 算法均優(yōu)于其他算法，而貪婪算法表現(xiàn)最差.

Table 1 Comparison of Maximum Profit and Coverage Ratio表1 最大利潤與覆蓋率的對比

Fig.7 Comparison of average costs圖7 平均開銷的對比

Fig.9 Comparison of average revenue of workers圖9 工人平均收益的對比

4.4 消融實驗

如圖10 所示，本文針對差分隱私的有效性做了消融實驗，實驗中對比了有差分隱私的性能以及沒有差分隱私的性能，并與基于DDQN 的算法模型進(jìn)行對比.實驗結(jié)果表明，去除差分隱私性能會有更好的效果，是因為模糊化的位置信息影響了模型的計算性能，但加入差分隱私的方法可以在不損失過多性能的前提下保護(hù)工人信息的隱私.此外，為了驗證該算法的性能隨差分隱私保護(hù)程度的變化，消融實驗中加入了不同的隱私保護(hù)機制覆蓋范圍下的算法性能的對比實驗，如圖11 所示，其中r表示本文3.3節(jié)所提到的差分隱私機制的保護(hù)范圍，當(dāng)保護(hù)范圍越大時，則需保證該范圍的地理不可區(qū)分性，故保護(hù)程度越高.由此可見，隨著保護(hù)范圍的增加算法性能所受影響較大，需選擇合適的保護(hù)強度，實現(xiàn)在保護(hù)隱私的前提下保證算法性能.

Fig.10 Ablation experiment圖10 消融實驗

Fig.11 Comparison under different protection levels圖11 不同保護(hù)程度下的對比

5 結(jié)論與展望

在本文中，針對MCS 的感知任務(wù)分配問題，在工人與任務(wù)的位置、狀態(tài)信息不斷改變的動態(tài)系統(tǒng)中，考慮了任務(wù)分配機制的合理性與工人信息的隱私保護(hù)等問題，將其定義為一個基于離散型數(shù)據(jù)集來進(jìn)行動態(tài)規(guī)劃的優(yōu)化問題，并利用差分隱私和深度強化學(xué)習(xí)的相關(guān)算法及模型去解決該問題.將PPO 模型作為決策模型訓(xùn)練和學(xué)習(xí)，在每次迭代中，考慮當(dāng)前狀態(tài)下的每個工人開銷的差異性以及完成任務(wù)的時序性等因素，利用聯(lián)合約束，在保證平臺收益最大化的同時，盡可能增加工人的累積收益，在這樣的動態(tài)系統(tǒng)中不斷優(yōu)化分配策略.此外，還在工人的移動設(shè)備與中央服務(wù)器的交互中加入了差分隱私的方法來保證工人的隱私.實驗結(jié)果也證明了本文方法的有效性.

在未來的工作中，將探索更多隱私保護(hù)的策略，并且在保證隱私的同時進(jìn)一步提升模型的性能.此外，也考慮在該模型中加入數(shù)據(jù)預(yù)測的機制，在收集處理感知數(shù)據(jù)的同時，基于歷史經(jīng)驗數(shù)據(jù)進(jìn)行某一范圍內(nèi)的數(shù)據(jù)預(yù)測，提升模型整體效率.

作者貢獻(xiàn)聲明：楊明川負(fù)責(zé)實驗及相關(guān)研究工作，并完成論文撰寫；朱敬華提出算法思路，設(shè)計論文整體框架；李元婧負(fù)責(zé)數(shù)據(jù)分析并協(xié)助撰寫論文；奚赫然提出修改意見并修改論文.