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

韓俊櫻，張振宇，孔德仕

（1.新疆大學信息科學與工程學院，烏魯木齊830046；2.新疆大學新疆多語種信息技術實驗室，烏魯木齊830046；3.四川大學計算機學院，成都610065）

0 引言

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

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

已有方法存在以下局限：

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

2）沒有參考用戶意愿，將感知任務進行合理組合，導致最終分配的感知任務可能與用戶期望執(zhí)行的任務相悖，不利于維護用戶的長時參與水平，因此需要構建一個定量分析激勵報酬、移動距離與用戶執(zhí)行意愿之間關系的數(shù)學模型。

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

1 問題模型

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

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

2 Crowd-Cluster方法

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

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

2.1 全局分簇

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

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

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

輸出 簇集合C。

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

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

3）將感知任務t加入到MTi中；

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

5）輸出簇集合C；

6）結束。

2.2 任務組合

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

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

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

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

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

算法2 Q-learning任務組合算法。

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

輸出 路徑集合Λi。

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

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

3）根據(jù)動作at計算當前任務隊列的效益作為獎勵rt。

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

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

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

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

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

9）輸出Λi。

10）結束。

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

算法3 任務路徑分解算法。

輸入 路徑集合Λi；

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

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

4）更新λt=λnew；

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

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

8）結束。

2.3 動態(tài)定價

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

約束條件為：

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

P*( |λ Ci)為能夠平衡感知任務與用戶間供需關系的任務序列λ 被用戶主動選擇的概率，當存在定價使得時，為λ的最終定價。

P*( λ |Ci)最小的任務路徑的定價為一個先驗值，即能驅動用戶的最低定價。

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

輸出 感知任務定價集合Ri。

1）初始化Ri為空；

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

5）輸出Ri；

6）結束。

2.4 任務分配

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

算法5 基于信譽度的任務分配算法。

輸出 感知任務分配方案Πi。

1）初始化Πi為空；

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

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

7）輸出Πi；

8）結束。

3 實驗評估與分析

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

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

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

表1 圖2的分簇及任務組合結果Tab.1 Clustering and task combination results of Fig.2

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

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

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

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

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

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

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

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

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

4 結語

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

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