移動(dòng)群智感知中面向用戶區(qū)域的分布式多任務(wù)分配方法

韓俊櫻，張振宇，孔德仕

（1.新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊830046；2.新疆大學(xué)新疆多語(yǔ)種信息技術(shù)實(shí)驗(yàn)室，烏魯木齊830046；3.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

移動(dòng)群智感知（Mobile Crowd Sensing，MCS）是一種基于眾包思想的新型感知模式［1-3］，它利用普通用戶隨身攜帶的智能移動(dòng)設(shè)備（智能手機(jī)、可穿戴設(shè)備等）形成兼具實(shí)時(shí)性及靈活性的大規(guī)模感知系統(tǒng)，進(jìn)而完成傳統(tǒng)靜態(tài)感知設(shè)備無(wú)法解決的大規(guī)模感知任務(wù)［4-6］，如：實(shí)時(shí)交通信息監(jiān)測(cè)［7］、空氣質(zhì)量檢測(cè)［8］、突發(fā)事件感知［9］等。

任務(wù)分配是移動(dòng)群智感知中的關(guān)鍵問(wèn)題之一，它的合理性對(duì)感知數(shù)據(jù)質(zhì)量、用戶參與水平、感知成本等都具有十分重要的影響［10-14］。任務(wù)分配屬于組合優(yōu)化問(wèn)題，具有NP 難解性。Wang 等［15］引入任務(wù)的最小感知質(zhì)量閾值來(lái)重新定義多任務(wù)分配問(wèn)題，為每個(gè)工作者分配一組適當(dāng)?shù)娜蝿?wù)使得感知系統(tǒng)效用最大化；Hu等［16］利用動(dòng)態(tài)獲取的時(shí)空知識(shí)提出了在線啟發(fā)式算法，以提升空間眾包任務(wù)分配的效率；Liu 等［17］分別針對(duì)少參與者多任務(wù)以及多參與者少任務(wù)兩種場(chǎng)景設(shè)計(jì)了參與者選擇框架TaskMe；Azzam 等［18］提出了基于群組的招募系統(tǒng)，利用遺傳算法綜合用戶特征從而選擇合適的用戶群組執(zhí)行感知任務(wù)。

已有方法存在以下局限：

1）面向用戶實(shí)時(shí)位置的單一任務(wù)分配不利于隱私保護(hù)，且難以處理較大規(guī)模的實(shí)時(shí)多任務(wù)，因此需要將感知任務(wù)進(jìn)行合理組合，構(gòu)建彈性的任務(wù)分配模式，讓用戶去完成一個(gè)或多個(gè)任務(wù)。

2）沒(méi)有參考用戶意愿，將感知任務(wù)進(jìn)行合理組合，導(dǎo)致最終分配的感知任務(wù)可能與用戶期望執(zhí)行的任務(wù)相悖，不利于維護(hù)用戶的長(zhǎng)時(shí)參與水平，因此需要構(gòu)建一個(gè)定量分析激勵(lì)報(bào)酬、移動(dòng)距離與用戶執(zhí)行意愿之間關(guān)系的數(shù)學(xué)模型。

考慮到上述情況，本文提出了面向用戶區(qū)域的分布式多任務(wù)分配方法Crowd-Cluster 以解決實(shí)時(shí)并發(fā)的多任務(wù)分配問(wèn)題。

1 問(wèn)題模型

給定用戶區(qū)域集合A={A1，A2，…，Am}，用戶區(qū)域Ai={Ui，Pi}。其中：為該用戶區(qū)域的用戶集合；Pi為該區(qū)域的中心位置。面向用戶區(qū)域的任務(wù)分配中，由于不需要獲取用戶的實(shí)時(shí)位置，用戶模型簡(jiǎn)化為二元組ui={nti，nui}。其中：nti為用戶歷史接受感知任務(wù)總數(shù)；nui為用戶接受但最終未執(zhí)行的任務(wù)數(shù)量。地理位置因素是Crowd-Cluster 進(jìn)行任務(wù)組合及路徑優(yōu)化的主要變量，而信譽(yù)度只用于最后的參與者優(yōu)選。

T={t1，t2，…，tn}為某一時(shí)段并發(fā)的感知任務(wù)集合，感知任務(wù)，其中：tlj為感知任務(wù)位置，tnj為感知任務(wù)所需的用戶人數(shù)。面向用戶區(qū)域的多任務(wù)分配方法有兩個(gè)優(yōu)化目標(biāo)：最小化參與者人數(shù)和最小化用戶移動(dòng)距離。兩個(gè)優(yōu)化目標(biāo)之間并不沖突，可以一起進(jìn)行優(yōu)化，其形式化定義如下：

2 Crowd-Cluster方法

Crowd-Cluster方法流程如圖1所示。

圖1 Crowd-Cluster方法流程Fig.1 Flowchart of Crowd-Cluster method

2.1 全局分簇

Crowd-Cluster 采用貪心啟發(fā)式分簇算法將全局用戶區(qū)域和感知任務(wù)進(jìn)行分簇，使得每個(gè)感知任務(wù)能夠優(yōu)先分配給與之最近的用戶區(qū)域，以優(yōu)化用戶的移動(dòng)距離，具體操作見(jiàn)算法1。簇集合C={C1，C2，…，Cn}，每個(gè)簇包含一個(gè)簇頭和多個(gè)成員，形式化定義為，其中MTi為一個(gè)任務(wù)集合，該任務(wù)集合的任意感知任務(wù)與Ai的距離均小于與其他用戶區(qū)域的距離。簇頭對(duì)應(yīng)一個(gè)用戶區(qū)域，感知任務(wù)則為簇內(nèi)的普通成員。

算法1 貪心啟發(fā)式分簇算法。

輸入 任務(wù)集合T，用戶區(qū)域集合A；

輸出 簇集合C。

1）初始化簇集合C={C1，C2，…，Cn}，集合中的簇Ci={Ai，MTi}，MTi初始化為空；

2）選擇距離感知任務(wù)t最近的用戶區(qū)域Ai；

3）將感知任務(wù)t加入到MTi中；

4）對(duì)每一個(gè)感知任務(wù)t并行執(zhí)行2）、3）步，直至所有感知任務(wù)均加入合適的簇中；

5）輸出簇集合C；

6）結(jié)束。

2.2 任務(wù)組合

Crowd-Cluster 將簇內(nèi)的多個(gè)感知任務(wù)進(jìn)行組合，構(gòu)成多條不定長(zhǎng)任務(wù)路徑（序列）。不失一般性，與現(xiàn)實(shí)場(chǎng)景出租車(chē)接單流程類(lèi)似，用戶更傾向于移動(dòng)較短的距離去執(zhí)行更多的任務(wù)。因此Crowd-Cluster 用任務(wù)平均距離Dm(λ)作為任務(wù)組合是否合理的評(píng)判指標(biāo)，其形式化定義如下：

其中：numλ為任務(wù)路徑λ 的長(zhǎng)度（感知任務(wù)個(gè)數(shù)），totDλ為總移動(dòng)距離，Dm(λ)含義為執(zhí)行單個(gè)任務(wù)的平均距離。在獲取任務(wù)路徑的過(guò)程中，假設(shè)當(dāng)前任務(wù)路徑為λ，存在獨(dú)立感知任務(wù)ti。將ti加入到λ 中組合成新的任務(wù)路徑為λ*。若Dm（λ*）＞Dm(λ)，則任務(wù)路徑λ*不合理，不能將λ 與ti進(jìn)行組合，反之亦然。其次，任務(wù)組合最終獲取的是任務(wù)路徑，因此需要優(yōu)化序列，類(lèi)似于旅行商問(wèn)題（Traveling Salesman Problem，TSP），尋找最優(yōu)序列方案使得完成多個(gè)感知任務(wù)的總移動(dòng)距離最小，該問(wèn)題具有NP難解性。

為了提升效率將任務(wù)組合與路徑規(guī)劃同時(shí)完成，Crowd-Cluster 利用Q-learning 任務(wù)組合算法獲取最優(yōu)任務(wù)路徑集合Λ，具體操作見(jiàn)算法2。該算法所獲取的每一條任務(wù)路徑具有以下特性：1）基于Dm(λ)，任務(wù)路徑是合理的；2）總移動(dòng)距離是相同元素路徑集合中最短的。

Q-learning 屬于強(qiáng)化學(xué)習(xí)，其模式可以用四元組表示為(S，Act，P，r)。其中：S 為狀態(tài)空間，Act為智能體的動(dòng)作空間，P為狀態(tài)轉(zhuǎn)移概率，r為獎(jiǎng)勵(lì)。強(qiáng)化學(xué)習(xí)通過(guò)智能體與環(huán)境之間的交互，進(jìn)行試錯(cuò)學(xué)習(xí)，最終學(xué)習(xí)得到智能體的策略。Q-learning基于特定狀態(tài)下動(dòng)作所對(duì)應(yīng)的Q值進(jìn)行決策。Q值為所獲獎(jiǎng)勵(lì)的累積期望，智能體Agent 目標(biāo)學(xué)習(xí)某一策略使得累積報(bào)酬最大化。Q值更新公式如下：

其中：Q(s，a)為狀態(tài)s下執(zhí)行動(dòng)作a 所對(duì)應(yīng)的Q 值，而r(s，a)為獲得的獎(jiǎng)勵(lì)；α 為學(xué)習(xí)效率值；γ 為折扣參數(shù)。在構(gòu)造任務(wù)路徑時(shí)，將任意一個(gè)感知任務(wù)ta視作一個(gè)智能體Agent，其動(dòng)作空間Act 為當(dāng)前簇內(nèi)的所有感知任務(wù)集合MT（不包括ta本身）?？紤]到最終生成的任務(wù)路徑節(jié)點(diǎn)數(shù)不定，因此在動(dòng)作空間加入動(dòng)作t0，用以代表空任務(wù)（即不選擇任何鄰居感知任務(wù)進(jìn)行組合）。感知任務(wù)ta所對(duì)應(yīng)的智能體Agent的狀態(tài)可以表示為一個(gè)隊(duì)列信息Qta，初始化時(shí)隊(duì)列中只有ta一個(gè)元素。在每一個(gè)狀態(tài)下會(huì)從MT 中選擇一個(gè)任務(wù)加入到隊(duì)列中，若所選任務(wù)已存在隊(duì)列中，則不加入；同時(shí)將狀態(tài)更新為新的隊(duì)列，再進(jìn)行下一次動(dòng)作。每一次動(dòng)作的獎(jiǎng)勵(lì)r 為-Dm(ct)。不失一般性，在實(shí)際場(chǎng)景中，每個(gè)用戶其移動(dòng)設(shè)備電量、網(wǎng)絡(luò)流量、存儲(chǔ)空間等感知資源有限，因此能夠執(zhí)行的任務(wù)數(shù)量是有限的，設(shè)置thr為任務(wù)路徑的節(jié)點(diǎn)數(shù)量上限。

算法2 Q-learning任務(wù)組合算法。

輸入 簇內(nèi)任務(wù)集合MTi，簇頭Ai，迭代次數(shù)E，貪心參數(shù)ε，任務(wù)路徑節(jié)點(diǎn)數(shù)量上限thr；

輸出 路徑集合Λi。

1）初始化狀態(tài)st=s0，智能體Agent 為感知任務(wù)ta。如果是第一次循環(huán)，則初始化QTable中的Q值為0。

2）根據(jù)常量參數(shù)ε 選取動(dòng)作。以1-ε 的概率選取當(dāng)前狀態(tài)st下Q 值最大的動(dòng)作；否則以均勻概率隨機(jī)選取動(dòng)作，選取的動(dòng)作記為at。

3）根據(jù)動(dòng)作at計(jì)算當(dāng)前任務(wù)隊(duì)列的效益作為獎(jiǎng)勵(lì)rt。

4）根據(jù)式（5）更新上一個(gè)狀態(tài)st的Q值，同時(shí)更新隊(duì)列狀態(tài)st=st+1。

5）循環(huán)執(zhí)行2）～4）步直至序列長(zhǎng)度等于thr。

6）循環(huán)執(zhí)行1）～5）步直至已迭代次數(shù)等于E。

7）根據(jù)學(xué)習(xí)好的QTable，選取每個(gè)狀態(tài)下最大Q 值的動(dòng)作加入到隊(duì)列中，獲得任務(wù)路徑λa加入到路徑集合Λi中。

8）對(duì)MTi中的每一個(gè)感知任務(wù)并行執(zhí)行1）～7）步。

9）輸出Λi。

10）結(jié)束。

簇內(nèi)每個(gè)感知任務(wù)作為起點(diǎn)構(gòu)成的任務(wù)路徑集合Λi中可能會(huì)出現(xiàn)冗余，因此對(duì)于擁有相同感知任務(wù)的任務(wù)序列需要進(jìn)行比較優(yōu)選。Crowd-Cluster 通過(guò)任務(wù)路徑分解算法用以保留總移動(dòng)距離最短的任務(wù)序列，并將其余任務(wù)序列刪除，具體操作見(jiàn)算法3。

算法3 任務(wù)路徑分解算法。

輸入 路徑集合Λi；

2）選取任務(wù)序列λ，獲取λ 中感知任務(wù)的最少所需用戶人數(shù)Nmin，令λt=λ；

3）將λ t 中的所有感知任務(wù)所需人數(shù)減去Nmin，獲取λt中未被完成的感知任務(wù)，構(gòu)成新的任務(wù)序列λnew加入到Λi*中；

4）更新λt=λnew；

5）循環(huán)執(zhí)行3）、4）步直至λt中的任務(wù)都能夠被完成；

6）循環(huán)執(zhí)行2）～5）步直至Λi中的所有任務(wù)路徑都被分解完成；

8）結(jié)束。

2.3 動(dòng)態(tài)定價(jià)

Crowd-Cluster 利用基于用戶意愿的動(dòng)態(tài)定價(jià)算法對(duì)每一個(gè)感知任務(wù)進(jìn)行合理定價(jià)，以平衡任務(wù)與用戶之間的供需關(guān)系，具體操作見(jiàn)算法4。不失一般性，用戶是有限理性的，不一定完全基于最大化個(gè)人效益去選擇任務(wù)，簇內(nèi)的每一個(gè)感知任務(wù)都具有一定概率會(huì)被用戶主動(dòng)選擇。因此，Crowd-Cluster方法構(gòu)建了用戶意愿模型，其形式化定義如下：

約束條件為：

其中：P( λ |Ci)為在簇Ci內(nèi)，用戶主動(dòng)選擇執(zhí)行任務(wù)序列λ 的概率；Rλ為任務(wù)序列λ 的報(bào)酬定價(jià)；τ 為一個(gè)0 到1 之間的常量參數(shù)。式（6）基于Boltzmann 分布使得每個(gè)感知任務(wù)都有一定概率被選中，并且定價(jià)越高、移動(dòng)距離越小的任務(wù)序列有更高的概率被選中，反之亦然。

P*( |λ Ci)為能夠平衡感知任務(wù)與用戶間供需關(guān)系的任務(wù)序列λ 被用戶主動(dòng)選擇的概率，當(dāng)存在定價(jià)使得時(shí)，為λ的最終定價(jià)。

P*( λ |Ci)最小的任務(wù)路徑的定價(jià)為一個(gè)先驗(yàn)值，即能驅(qū)動(dòng)用戶的最低定價(jià)。

算法4 基于用戶意愿的動(dòng)態(tài)定價(jià)算法。

輸出 感知任務(wù)定價(jià)集合Ri。

1）初始化Ri為空；

2）選取任務(wù)序列λ，根據(jù)式（7）計(jì)算P*( λ |Ci)；

5）輸出Ri；

6）結(jié)束。

2.4 任務(wù)分配

Crowd-Cluster 利用基于信譽(yù)度的任務(wù)分配算法從簇內(nèi)的用戶區(qū)域Ai中選擇信譽(yù)度高的用戶執(zhí)行任務(wù)序列，進(jìn)而保障群智感知質(zhì)量，具體操作見(jiàn)算法5。

算法5 基于信譽(yù)度的任務(wù)分配算法。

輸出 感知任務(wù)分配方案Πi。

1）初始化Πi為空；

3）以P*( λ |Ci)為主要關(guān)鍵字，將中的任務(wù)序列進(jìn)行降序排序；

5）按序從Ai選取用戶ui加入到中，直至任務(wù)序列λ被完成，完成后將πλ加入到Πi中；

7）輸出Πi；

8）結(jié)束。

3 實(shí)驗(yàn)評(píng)估與分析

首先通過(guò)一個(gè)簡(jiǎn)單案例描述Crowd-Cluster的分簇及任務(wù)組合流程，其多任務(wù)并發(fā)場(chǎng)景下的感知任務(wù)與用戶區(qū)域分布如圖2所示。

圖2 感知任務(wù)及用戶區(qū)域分布Fig.2 Sensing tasks and user area distribution

Crowd-Cluster 將圖2 中的用戶區(qū)域及感知任務(wù)基于歐氏距離進(jìn)行貪心分簇，并采用Q-learning 進(jìn)行任務(wù)組合，其結(jié)果如表1所示。

表1 圖2的分簇及任務(wù)組合結(jié)果Tab.1 Clustering and task combination results of Fig.2

采用真實(shí)數(shù)據(jù)集mobility 進(jìn)行正式實(shí)驗(yàn)評(píng)估，mobility 數(shù)據(jù)集由CRAWDAD 提供，為2008 年美國(guó)舊金山30 天內(nèi)500 輛出租車(chē)的GPS 軌跡數(shù)據(jù)集。mobility 包括了車(chē)輛、緯度、經(jīng)度、占用情況（0 表示出租車(chē)未使用，1 表示使用中）、時(shí)間（UNIX時(shí)間戳格式）。將占用情況為0 的坐標(biāo)作為用戶位置，占用情況為1 的坐標(biāo)作為感知任務(wù)位置。將一個(gè)月內(nèi)上午7 點(diǎn)至10點(diǎn)間的用戶位置進(jìn)行聚類(lèi)，篩選人數(shù)最多的前10 個(gè)作為用戶區(qū)域，共9 380 名用戶。Crowd-Cluster 中的任務(wù)路徑長(zhǎng)度閾值設(shè)置為4，即最多只能將4個(gè)任務(wù)進(jìn)行組合分配。用戶的歷史任務(wù)執(zhí)行記錄為1～30的隨機(jī)數(shù)，用戶失信記錄比率為執(zhí)行記錄的1%～100%的隨機(jī)數(shù)。

最小化移動(dòng)距離、最小化參與者人數(shù)是兩個(gè)主要的優(yōu)化目標(biāo)。本文將分配給用戶單一任務(wù)的貪心算法Greedy-ONE作為基線算法。在不同的感知任務(wù)分布下，用移動(dòng)距離、參與者人數(shù)、任務(wù)完成度等指標(biāo)，評(píng)估比較Crowd-Cluster 與Greedy-ONE的性能差異。

全局范圍內(nèi)設(shè)置150 個(gè)感知任務(wù)，每個(gè)感知任務(wù)所需的用戶人數(shù)為10到100之間的隨機(jī)數(shù)。基于感知任務(wù)位置分布將分布情況分為三種類(lèi)型：密集型、散點(diǎn)型以及混合型。密集型感知任務(wù)分布較為密集，相對(duì)距離較?。簧Ⅻc(diǎn)型感知任務(wù)較為分散，相對(duì)距離較遠(yuǎn)；混合型為部分區(qū)域呈現(xiàn)密集型分布，其余區(qū)域呈現(xiàn)散點(diǎn)型分布。由表2可得，Crowd-Cluster方法在不同感知任務(wù)分布情況下，其最終的用戶參與人數(shù)均明顯小于Greedy-ONE方法，能有效減少平臺(tái)感知成本。

表2 不同任務(wù)分布下的參與者人數(shù)Tab.2 Participant number in different task distributions

由于Greedy-ONE 方法只分配單一任務(wù)，因此在任意的任務(wù)分布情況下，其最終所需用戶人數(shù)都相同。而Crowd-Cluster方法將感知任務(wù)進(jìn)行合理組合后，分配任務(wù)路徑，如果感知任務(wù)過(guò)于分散則能夠進(jìn)行組合的任務(wù)就減少了，因此Crowd-Cluster 在較為密集的任務(wù)分布情況下具有更好的效果。

Crowd-Cluster 通過(guò)分配多個(gè)任務(wù)減少參與者人數(shù)，并通過(guò)Q-learning 對(duì)路徑進(jìn)行優(yōu)化，因此在混合型感知任務(wù)分布下，隨著任務(wù)數(shù)量不斷增大，Crowd-Cluster 的用戶移動(dòng)距離小于Greedy-ONE，如圖3所示。

圖3 不同任務(wù)數(shù)量下的用戶移動(dòng)總距離Fig.3 User movement distance under different task numbers

從圖4 可以看出，在感知任務(wù)數(shù)量及分布不變的情況下，隨著用戶區(qū)域的用戶數(shù)量不斷減少，相比Greedy-ONE，Crowd-Cluster 能夠明顯降低用戶資源不足對(duì)任務(wù)完成度的影響，進(jìn)而保證感知質(zhì)量。

圖4 不同用戶人數(shù)下的感知任務(wù)完成度Fig.4 Sensing task completion degree under different user numbers

4 結(jié)語(yǔ)

本文面向用戶區(qū)域提出了Crowd-Cluster方法以解決實(shí)際場(chǎng)景中的多任務(wù)分配問(wèn)題。首先將全局的感知任務(wù)與用戶區(qū)域進(jìn)行合理分簇，每個(gè)簇內(nèi)分布式進(jìn)行任務(wù)分配。通過(guò)考慮移動(dòng)較短距離執(zhí)行更多任務(wù)的用戶意愿，將任務(wù)進(jìn)行組合構(gòu)成任務(wù)路徑。其次，通過(guò)構(gòu)建符合用戶有限理性的任務(wù)執(zhí)行意愿模型對(duì)感知任務(wù)路徑進(jìn)行動(dòng)態(tài)定價(jià)。最后，根據(jù)信譽(yù)度進(jìn)行用戶優(yōu)選，將效益大的任務(wù)優(yōu)先分配給信譽(yù)度高的用戶執(zhí)行。

Crowd-Cluster 僅考慮了感知任務(wù)的空間關(guān)聯(lián)性，下一步需要完備考慮任務(wù)的時(shí)間、內(nèi)容描述、數(shù)據(jù)類(lèi)型等因素，將線上或線下的感知任務(wù)進(jìn)行合理組合。其次，基于玻爾茲曼分布的意愿模型雖然能夠體現(xiàn)用戶的有限理性，但并不準(zhǔn)確，如何從用戶感知?dú)v史、移動(dòng)軌跡中分析挖掘用戶意圖，構(gòu)建準(zhǔn)確個(gè)性化的用戶意愿模型也是后續(xù)的重點(diǎn)研究方向之一。