徐 哲，李 卓,2，陳 昕

(1.北京信息科技大學 計算機學院，北京 100101； 2.網(wǎng)絡文化與數(shù)字傳播北京市重點實驗室(北京信息科技大學)，北京 100101)

(*通信作者電子郵箱lizhuo@bistu.edu.cn)

面向移動群智感知的多任務分發(fā)算法

徐 哲1，李 卓1,2*，陳 昕1

(1.北京信息科技大學 計算機學院，北京 100101； 2.網(wǎng)絡文化與數(shù)字傳播北京市重點實驗室(北京信息科技大學)，北京 100101)

(*通信作者電子郵箱lizhuo@bistu.edu.cn)

針對在移動群智感知中基于機會通信完成數(shù)據(jù)傳輸會消耗大量時間成本的問題，提出了一種基于中樞節(jié)點的多任務分發(fā)(HTA)算法。該算法利用節(jié)點在移動網(wǎng)絡中社交關(guān)系屬性不同的特點，通過中樞節(jié)點選擇算法將部分節(jié)點作為中樞節(jié)點，并將其用于協(xié)助任務請求節(jié)點分發(fā)任務。在任務請求節(jié)點與中樞節(jié)點相遇時，同時給中樞節(jié)點本身和它的從屬節(jié)點分配任務，并由中樞節(jié)點負責向從屬節(jié)點分發(fā)任務與回收任務結(jié)果?；赥he ONE模擬器進行實驗，與在線任務分配(NTA)算法相比，HTA算法時間成本平均降低了24.9%，同時任務完成率平均提高150%。實驗結(jié)果表明，HTA算法能夠提高任務的完成速度，降低時間成本消耗。

移動群智感知；機會通信；多任務分發(fā)；社交；中樞節(jié)點

0 引言

近年來，智能手機、平板電腦、可穿戴設備、車載感知設備等智能終端設備迅速發(fā)展普及。這些設備集成了越來越多的傳感器，擁有越來越強大的計算、感知、存儲和通信能力。隨之出現(xiàn)了一種新的物聯(lián)網(wǎng)感知方式——移動群智感知[1]。移動群智感知是將眾包的思想與移動感知相結(jié)合的產(chǎn)物，將普通用戶的移動設備作為基本感知單元，通過移動互聯(lián)網(wǎng)進行有意識或無意識的協(xié)作，形成群智感知網(wǎng)絡，實現(xiàn)感知任務分發(fā)與感知數(shù)據(jù)收集利用，最終完成大規(guī)模的、復雜的感知任務。

目前，移動群智感知已在環(huán)境監(jiān)測[2-3]、智能交通[4]、公共安全[5]、城市環(huán)境感知[6]等領(lǐng)域有很多應用。但許多群智感知應用需要將大量的感知數(shù)據(jù)傳輸?shù)綌?shù)據(jù)中心，采用移動蜂窩網(wǎng)絡將消耗大量的電量和流量成本。為節(jié)約數(shù)據(jù)傳輸成本，移動群智感知網(wǎng)絡中的各節(jié)點通過短距離通信技術(shù)使用“存儲-攜帶-轉(zhuǎn)發(fā)”的數(shù)據(jù)傳輸機制(如圖1)交換數(shù)據(jù)。這種數(shù)據(jù)傳輸機制是基于機會通信的傳輸機制[7]，通信機會的出現(xiàn)依賴于移動節(jié)點間的相遇。由于移動節(jié)點的位置會隨著時間動態(tài)變化，同時移動節(jié)點間的相遇時間間隔也有大范圍的波動，因此在數(shù)據(jù)傳輸階段會消耗大量時間開銷[8]，這將導致任務的整體時間成本巨大。要在最小化電量和流量成本的同時，實現(xiàn)較低的時間成本，則需要設計新的任務分發(fā)算法。

根據(jù)上述分析，由于移動節(jié)點間通信鏈路的間隙性等原因，如何快速有效地實現(xiàn)任務分發(fā)及數(shù)據(jù)收集是移動群智感知亟待解決的關(guān)鍵問題之一。由于移動節(jié)點的位置一直動態(tài)變化，難以準確對節(jié)點間的相遇機會進行建模和預測來優(yōu)化感知任務的分發(fā)和分配。因此，如何確定高效任務分發(fā)、分配策略，將感知任務低成本、高效地傳遞給移動節(jié)點，既克服移動節(jié)點的帶寬資源限制，同時保障數(shù)據(jù)收集效率是移動群智感知實用化的關(guān)鍵。

移動節(jié)點在現(xiàn)實環(huán)境中依據(jù)自身規(guī)律不停地移動，雖然存在隨機性，但又具有顯著的規(guī)律性[9]。同時移動機會網(wǎng)絡拓撲演化特性受移動節(jié)點社交屬性影響，因此移動節(jié)點間的相遇特性與其社交關(guān)系相關(guān)，兩移動節(jié)點間的社交關(guān)系的強弱決定了彼此相遇機會的高低。社交網(wǎng)絡分析(Social Network Analysis， SNA)[10]中有兩個關(guān)鍵概念：社區(qū)(Communities)和中心性(Centrality)，從整個網(wǎng)絡的角度抽象出節(jié)點間的社交關(guān)系，刻畫了不同移動節(jié)點在整個網(wǎng)絡中的影響力。如果兩個彼此相遇概率較低的節(jié)點在高影響力節(jié)點的影響范圍內(nèi)，則它們利用高影響力的節(jié)點作為中繼可提高節(jié)點間傳遞數(shù)據(jù)的效率，進而用于優(yōu)化感知任務的分發(fā)與分配。因此，本文擬利用各用戶節(jié)點的社會屬性，通過利用合適的中繼節(jié)點減少移動群智感知任務的時間成本。

圖1 機會網(wǎng)絡中的“存儲-攜帶-轉(zhuǎn)發(fā)”傳輸機制

本文主要研究移動節(jié)點的社交屬性對數(shù)據(jù)轉(zhuǎn)發(fā)性能及任務分配策略的影響。本文提出了一種面向移動群智感知的多任務分發(fā)算法——基于中樞節(jié)點的多任務分發(fā)(Hub-based multi-Task Assignment, HTA)算法，設計并實現(xiàn)了基于移動節(jié)點社交屬性的中樞節(jié)點發(fā)現(xiàn)算法。本文基于St Andrews大學的Andrews_sassy數(shù)據(jù)集[11]和人工合成數(shù)據(jù)集，利用The ONE機會網(wǎng)絡模擬器進行了實驗。結(jié)果表明，比使用直接等待策略的在線任務分配(oNline Task Assignment, NTA)算法[12]縮短24.9%的任務平均完成時間，同時任務完成率也有平均150%的提高。

1 相關(guān)工作

移動群智感知任務可分為三個階段：任務分發(fā)階段、任務執(zhí)行階段和任務結(jié)果返回階段。在任務分發(fā)階段和任務結(jié)果返回階段利用“存儲-攜帶-轉(zhuǎn)發(fā)”機制進行任務數(shù)據(jù)傳遞，需要解決數(shù)據(jù)傳遞時延高的問題，機會網(wǎng)絡中的路由策略相關(guān)研究對該問題進行了廣泛的研究。這方面代表性工作主要包括：洪泛[13]是最極端的一種數(shù)據(jù)路由策略，它的思想是節(jié)點將數(shù)據(jù)傳遞給每一個與自己接觸的節(jié)點，通過網(wǎng)絡中存在多份數(shù)據(jù)來提高數(shù)據(jù)的投遞成功率和速率。由于網(wǎng)絡中存在多份數(shù)據(jù)，使得網(wǎng)絡負載增加，對每個智能設備的存儲能力造成巨大壓力，存儲容量很快會被占滿并無法再接收新的數(shù)據(jù)，導致網(wǎng)絡性能降低。直接等待[14]是另一種極端的數(shù)據(jù)轉(zhuǎn)發(fā)策略，它當且僅當源節(jié)點遇到目的節(jié)點時才投遞數(shù)據(jù)，數(shù)據(jù)的投遞成功率最低、速率最慢。噴射-等待[15]是機會網(wǎng)絡中的一種典型數(shù)據(jù)轉(zhuǎn)發(fā)策略，通過限制網(wǎng)絡中消息的副本數(shù)，有效降低了網(wǎng)絡負載。但是在移動機會網(wǎng)絡中，節(jié)點由于社會關(guān)系的影響，轉(zhuǎn)發(fā)能力存在較大的差異，造成噴射等待效率較低。文獻[16]中提出的一種BUBBLE轉(zhuǎn)發(fā)策略利用了人的社會性，根據(jù)節(jié)點的移動軌跡計算出每個節(jié)點的活躍度，然后依據(jù)節(jié)點活躍度在系統(tǒng)和社區(qū)的排名，進行消息路由策略的選擇：源節(jié)點將消息傳輸給全局活躍度大于自己的節(jié)點，直到將消息傳輸?shù)脚c目標節(jié)點位于同一社區(qū)的中繼節(jié)點，然后中繼節(jié)點再將消息傳輸給社區(qū)活躍度大于自己的節(jié)點，直到消息達到目的節(jié)點。該算法考慮社會關(guān)系對數(shù)據(jù)傳輸機會的影響，利用了活躍度高的節(jié)點與其他節(jié)點接觸機會較多的特點，但要求機會網(wǎng)絡中的各節(jié)點清楚所有節(jié)點的社區(qū)劃分情況以及所有節(jié)點的活躍度，這使得該策略的應用環(huán)境受到限制，實用性面臨挑戰(zhàn)。

在任務執(zhí)行階段，節(jié)點處理在任務分發(fā)階段接收到的任務，這里涉及到任務處理順序的問題，目前最相關(guān)的研究在并行機調(diào)度領(lǐng)域。這方面代表性工作文獻[17-18]針對傳統(tǒng)并行機調(diào)度問題的研究進展作出了詳細的總結(jié)。此外，文獻[12]提出一種針對移動社交網(wǎng)絡(與移動機會網(wǎng)絡具有相似的用戶移動模型)環(huán)境下多任務分配問題的算法，以動態(tài)在線模式運行的情況下得到的實驗結(jié)果顯示時間性能優(yōu)于現(xiàn)有其他算法。

以上總結(jié)中，雖然有很多相關(guān)的研究成果可用于移動群智感知的任務分發(fā)問題中來，但是，各階段的理論又很難結(jié)合在一起，比如，數(shù)據(jù)路由問題的解決方案要求在作出決策前確定要傳輸?shù)臄?shù)據(jù)，而任務分配算法則需要在任務分發(fā)者和普通節(jié)點相遇時再確定任務分配策略(即待傳輸?shù)臄?shù)據(jù))。因此，為進一步減少感知任務的整體時間消耗，需要利用移動機會網(wǎng)絡中的社交屬性，提出新的算法，將任務分發(fā)與任務調(diào)度結(jié)合。

文獻[12]對于任務分發(fā)和結(jié)果返回的路由問題采用的是直接等待策略，并對這種情況下的多任務分配問題提出了解決方案。與文獻[12]不同的是，本文將任務分發(fā)與任務調(diào)度結(jié)合，使用單跳轉(zhuǎn)發(fā)策略，通過增加中樞節(jié)點輔助任務請求者分發(fā)感知任務，并提出了一種新的多任務分配與分發(fā)算法。

2 網(wǎng)絡模型與問題定義

在一個由n個用戶組成的移動機會網(wǎng)絡中，每個用戶節(jié)點均攜帶著一個具有一定計算、存儲、通信能力的智能設備，并按照各自的活動規(guī)律在地圖中移動。假設有一個被稱為任務分發(fā)者的特殊用戶，用v0表示，他有m個感知任務需要分發(fā)給網(wǎng)絡中的其他用戶。如果v0與其他用戶vi相遇，v0將分配若干手中的感知任務給vi。然后，vi將花費一定量的時間去完成分配給自己的任務。接著，vi在完成感知任務后，將一直等到自己與v0再次相遇時，將所得到的感知結(jié)果返回給v0。

本文假設：

1)近距離通信設備的傳輸性能滿足：分配任務和返回結(jié)果等數(shù)據(jù)能夠在節(jié)點間的一次機會連接斷開之前傳輸完成。

2)移動用戶i和j相遇間隔時間服從特征值為λi, j的指數(shù)分布。

3)每對用戶之間的關(guān)系參數(shù)λi, j代表了在單位時間內(nèi)，用戶i與用戶j之間的平均相遇次數(shù)。通過歷史相遇記錄或歷史連接記錄可以計算出參數(shù)λi, j。假設兩用戶在一段時間內(nèi)的接觸歷史記錄由集合C表示，每條記錄用ci表示，則：

(1)

定義1 任務完成時間(Makespan)。一個感知任務的完成時間等于t1+t2+t3，其中：t1為任務分發(fā)者開始分發(fā)任務到節(jié)點i接收到該任務的時長，t2為任務在節(jié)點i手中停留的時長，t3為節(jié)點i將任務結(jié)果傳遞回任務分發(fā)者的時長。對于任務j的Makespan，使用M(j)表示。

本文假設，任務分發(fā)者v0有m個獨立的感知任務，用J={j1,j2,…,jm}表示，這些任務可能屬于不同的任務類型。為了簡化問題，將任務的工作量(workload)統(tǒng)一為感知用時；使用t1,t2,…,tm表示且J中各任務的工作量大小,關(guān)系為t1≤t2≤…≤tm。假定v0將所有任務全部分配給其他用戶，且每個任務只會分配給一名用戶。

使用AM(Π)表示對于任務分配策略Π中的所有任務的AverageMakespan。公式表示為：

(2)

問題1 多任務分配問題。給定一個節(jié)點集合V={v0,v1,v2,…,vn-1}以及節(jié)點關(guān)系矩陣R[n][n]、一個感知任務集合J={J0,J1,J2,…,Jn-1}及其對應的任務工作量集合T={T1,T2,…,Tm}。其中R[n][n]表示節(jié)點i和節(jié)點j之間的單位時間內(nèi)的平均相遇次數(shù)，則多任務分配問題是如何確定一個任務分配策略Π={J1,J2,…,Jn}，使AM(Π)最小。

在任務分發(fā)階段之前，任務分發(fā)者需要確定任務的分配策略才能將任務分發(fā)給各節(jié)點，任務分發(fā)階段和任務結(jié)果返回階段的時間成本又是必須考慮的因素。但是由于節(jié)點的移動具有隨機性，難以準確預測節(jié)點彼此何時相遇，所以任務分配策略難以實現(xiàn)最優(yōu)。

定理1 多任務分配問題是NP-完全問題。

證明 首先，本文引入非相關(guān)并行機調(diào)度問題。該問題可描述為：任給m個工件，n臺機器，對每個i=1,2,…,n和每個j=1,2,…,m，第j個工件在第i臺機器上的加工時間為pij=ti+ti′+τj，對所有m個工件在n臺機器上安排加工時間表，使得在這些機器上最后加工完的平均任務完成時間最短。

在清楚所有節(jié)點間相遇時間的情況下，設任務分發(fā)者與節(jié)點v1,v2,…,vn的相遇時間為t1,t2,…,tn，距離下次相遇的時間間隔為t1′,t2′,…,tn′，對于m個任務，第j個任務的執(zhí)行時間為τj，則多任務分配問題與非相關(guān)并行機調(diào)度問題等價。

非相關(guān)并行機調(diào)度問題已被證明為NP-完全問題[19]，因此在清楚所有節(jié)點彼此相遇時間的情況下，多任務分配問題是NP-完全問題。清楚所有節(jié)點彼此相遇時間的是多任務分配問題的一個特例，因此多任務分配問題是NP-完全問題。

接下來將介紹利用移動節(jié)點社交屬性提出的一種多任務分配算法。

3 基于節(jié)點社交屬性的多任務分配算法

根據(jù)文獻[12]所述，為實現(xiàn)最優(yōu)任務分配策略，任務分發(fā)者應該在與某節(jié)點相遇時才確定對應需要分配的任務集。移動群智感知網(wǎng)絡中的任務分發(fā)節(jié)點在遇到其他節(jié)點之前并不確定要分配給每個節(jié)點的任務集，更無法確定接收任務數(shù)據(jù)的目標節(jié)點。因此，目前針對機會網(wǎng)絡的數(shù)據(jù)傳輸轉(zhuǎn)發(fā)策略[13-16]并不直接適用于移動群智感知環(huán)境，這些策略均需要在數(shù)據(jù)傳遞初始階段就確定要傳遞的數(shù)據(jù)。在群智感知的數(shù)據(jù)分發(fā)領(lǐng)域，目前廣泛使用的策略是直接交付型，相當于直接等待策略。因此，通過整合任務分配策略與數(shù)據(jù)分發(fā)策略的決策環(huán)節(jié)，優(yōu)化任務調(diào)度和數(shù)據(jù)分發(fā)流程，實現(xiàn)優(yōu)化AM。

本文提出了一種借助中樞節(jié)點協(xié)助分發(fā)任務的任務分配(HTA)算法。該算法的主要思想是依據(jù)節(jié)點之間的社交屬性篩選出中樞節(jié)點和對應的從屬節(jié)點，任務分發(fā)者與中樞節(jié)點相遇時同時確定從屬節(jié)點的任務分配，然后借助該中樞節(jié)點協(xié)助分發(fā)從屬節(jié)點的任務。在完整介紹該算法前，先對中樞節(jié)點選擇算法進行完整闡述。

3.1 中樞節(jié)點選擇算法

給定一個節(jié)點集合V={v0,v1,v2,…,vn-1}以及節(jié)點關(guān)系矩陣λ[n][n]。其中λi, j表示節(jié)點i和節(jié)點j之間的單位時間內(nèi)的平均相遇次數(shù)。令ti, j表示節(jié)點i與節(jié)點j通信的時間成本，即節(jié)點i與節(jié)點j相遇的平均時間間隔。

問題2 中樞節(jié)點選擇問題。從除v0以外的其他節(jié)點中選擇一個節(jié)點子集A，使v0僅向節(jié)點集A中的節(jié)點發(fā)送消息，最多通過一次轉(zhuǎn)發(fā)就可使所有節(jié)點接收到消息，且t0,i+ti, j≤t0, j(i∈A,j?A)。

根據(jù)對本文要解決問題的分析，可以得出中樞節(jié)點在整個網(wǎng)絡中應該是影響力較大的節(jié)點。中樞節(jié)點選擇問題可以通過轉(zhuǎn)換為求Top-K問題[20]，然后使用相應的求解辦法求出結(jié)果，文獻[21]提出的算法能夠找出重要節(jié)點。但，針對本文問題的分析，發(fā)現(xiàn)得到重要節(jié)點集后，重要節(jié)點以外的其他節(jié)點的歸屬問題依然沒有解決。

通過分析，得出中樞節(jié)點應當具有以下屬性：某從屬節(jié)點vi與中樞節(jié)點的相遇概率應高于節(jié)點vi與任務分發(fā)節(jié)點v0之間的相遇概率。因此，本文提出了一種新的中樞節(jié)點選擇算法。直接根據(jù)節(jié)點間相遇概率的高低確定中樞節(jié)點。根據(jù)2.1節(jié)對移動社交網(wǎng)絡中的各節(jié)點的關(guān)系屬性λ的定義，每兩個節(jié)點之間的關(guān)系屬性λ代表了這兩個節(jié)點的相遇概率高低，λ的數(shù)值越大對應兩節(jié)點的相遇概率越高；另一方面它也反映了這兩個節(jié)點關(guān)系遠近程度。

中樞節(jié)點選擇算法的基本思路是：要判斷vj是否為中樞節(jié)點，只需遍歷關(guān)系矩陣的每一行，判斷第j列的每一個值在其對應的第i行中是否為最大值，如果為最大值則vj是vi的中樞節(jié)點。

具體實現(xiàn)方法是：若節(jié)點vj是另一節(jié)點vi的中樞節(jié)點，則在關(guān)系矩陣的第i行中，λi, j是最大值。要判斷vj是否為中樞節(jié)點，只需遍歷關(guān)系矩陣的每一行，求出其中的最大值，然后判斷該值是否在第j列。算法具體步驟見算法1。

在算法1第1)步中的result記錄了節(jié)點Vi的從屬節(jié)點，如果result為空集，則表示節(jié)點vi不作為中樞節(jié)點。

下面用一個簡單的例子對該算法進行解釋：首先，假設一個移動社交網(wǎng)絡(Mobile Social Network, MSN)中有5個節(jié)點，其中的關(guān)系矩陣為：

先判斷節(jié)點1是否為某些節(jié)點的中樞節(jié)點：首先，在第2行中尋找最大值，第2行的最大值在第3列，不在第1列，所以節(jié)點1不是節(jié)點2的中樞節(jié)點；然后繼續(xù)在第3行中選擇最大值，第3行中的最大值在第2列，也不在第1列，所以節(jié)點1不是節(jié)點3的中樞節(jié)點；一直掃描到第5行，發(fā)現(xiàn)第一列中的數(shù)值在對應的每一行里都不是最大值，所以，得到的計算結(jié)果是節(jié)點1不作為中樞節(jié)點。再來嘗試判斷節(jié)點2是否為某些節(jié)點的中樞節(jié)點，可以發(fā)現(xiàn)在第3行和第4行中，第2列的數(shù)值為所在行的最大值，說明節(jié)點3和節(jié)點4均與節(jié)點2的相遇頻率高于與其他節(jié)點的相遇頻率，所以節(jié)點2作為節(jié)點3和節(jié)點4的中樞節(jié)點。依次判斷節(jié)點3、4、5可以計算得，節(jié)點3是節(jié)點1、2的中樞節(jié)點，節(jié)點4是節(jié)點5的中樞節(jié)點，節(jié)點5不是中樞節(jié)點

算法1 中樞節(jié)點選擇算法。

輸入：節(jié)點集合V={v0,v1,v2,…,vn-1}；關(guān)系矩陣λ[n][n]。 輸出：每個節(jié)點對應的從屬節(jié)點集合，若某節(jié)點的從屬節(jié)點集為空，則其不作為中樞節(jié)點。

1)

result=[?,?,…,?],result初始狀態(tài)有n個空集

2)

fori← 1 ton-1:

3)

forj ← 1ton-1:

4)

max=λj,0

5)

indexmax=0

6)

fork ← 1ton-1:

7)

如果λj,k大于max

8)

max=λj,k

9)

indexmax=k

10)

endfor

11)

如果indexmax等于i，則將vj加入result[i]

12)

endfor

13)

endfor

14)

輸出result

通過分析，該算法的時間復雜度為O(n2)，且僅計算了一個節(jié)點是否為中樞節(jié)點，若要對所有節(jié)點均計算一遍，則時間復雜度為O(n3)。在實際應用中還可以采用另一種優(yōu)化后的實現(xiàn)，一次求出所有中樞節(jié)點及其從屬節(jié)點，時間復雜度為O(n2)。

算法的主要思路與算法1基本相同，主要區(qū)別在第7)～10)步上，具體步驟見算法2。

算法2 優(yōu)化后的中樞節(jié)點選擇算法。

輸入：節(jié)點集合V={v0,v1,v2,…,vn-1}；關(guān)系矩陣λ[n][n]。 輸出：每個節(jié)點對應的從屬節(jié)點集合，若某節(jié)點的從屬節(jié)點集為空，則其不作為中樞節(jié)點。

1)

result=[?,?,…,?],result初始狀態(tài)有n個空集

2)

forj← 1 ton-1:

3)

max=λj,0

4)

indexmax=0

5)

fork ← 1ton-1:

6)

如果λj,k大于max

7)

max=λj,k

8)

indexmax=k

9)

endfor

10)

result[indexmax]=result[indexmax]+{vj}

11)

end for

12)

輸出result

3.2 任務分配與分發(fā)算法

通過3.1節(jié)的介紹，清楚了如何對中樞節(jié)點進行選擇，本節(jié)將結(jié)合中樞節(jié)點選擇算法，計算感知任務集的分配策略并確定分發(fā)路徑。算法完整過程見算法3。

算法3 任務分配與分發(fā)算法。

輸入：待分配的任務集J={j1,j2,…,jm;t1≤t2≤…≤tm}；待分配任務的節(jié)點集V={v1,v2,…,vn}；關(guān)系矩陣λ[n][n]；任務分發(fā)者遇到的節(jié)點對應序號i。 輸出：任務集Ji及JF={Jj|j∈Fi}，F(xiàn)i是vi的從屬節(jié)點集。

當任務分發(fā)者v0與節(jié)點vi相遇，執(zhí)行以下步驟：

1)

在中樞節(jié)點選擇算法得到的所有從屬節(jié)點集中找出Fi

2)

如果Fi非空:

3)

將vi作為中樞節(jié)點，且Fi對應中樞節(jié)點vi的從屬節(jié)點集

4)

fork← 1 ton-1:

5)

IPTk=2/λ0,k

6)

endfor

7)

IPTi=1/λ0,i,IPTj=1/λ0,i+1/λi, j,j∈Fi

8)

m等于剩余未分配任務數(shù)量

9)

forp← 1 tom:

10)

找出IPT值最小的節(jié)點對應的序號indexmin

11)

Jindexmin=Jindexmin+{jp}

12)

IPTindexmin=IPTindexmin+tp

13)

如果indexmin等于i或indexmin對應節(jié)點在Fi集中，則：

14)

J=J-{jp}

15)

endfor

16)

輸出Ji及JF={Jj|j∈Fi}，其余節(jié)點得到的結(jié)果拋棄

每次執(zhí)行任務分配算法后，只將相遇節(jié)點及其從屬節(jié)點(如果相遇節(jié)點被作為中樞節(jié)點)分配到的任務分發(fā)出去，其余節(jié)點分配到的任務只是暫時的，不作為最終結(jié)果。

在中樞節(jié)點選擇算法中有可能會出現(xiàn)這樣的情況，兩個節(jié)點vi和vj互為中樞節(jié)點，則處理方案為，任務分發(fā)者v0先與節(jié)點vi相遇，就將vi作為vj的中樞節(jié)點。其次，消息準備從中樞節(jié)點傳遞給從屬節(jié)點前，從屬節(jié)點判斷消息的上一次傳遞路徑是否為從屬節(jié)點本身，避免循環(huán)傳遞消息，即浪費網(wǎng)絡資源，又有可能造成死循環(huán)。之所以可能出現(xiàn)上述問題，是因為從從屬節(jié)點的角度看，自身也是中樞節(jié)點，中樞節(jié)點也是從屬節(jié)點的從屬節(jié)點。

本文使用算法3將任務分配和分發(fā)收集的完整流程優(yōu)化為以下步驟：

1)在任務分發(fā)者v0，從開始分發(fā)感知任務起第一次遇到節(jié)點vi時，執(zhí)行任務分配和分發(fā)算法3，計算出節(jié)點vi及其從屬節(jié)點(若節(jié)點vi被確定為中樞節(jié)點)的任務分配策略。將vi及其從屬節(jié)點從節(jié)點集V中移除。

2)中樞節(jié)點vi接收到任務分配策略后，立即開始按照工作量從小到大的順序依次執(zhí)行分配給自己的感知任務；同時在之后的第一次遇到屬于自己的從屬節(jié)點時，將自己保存的從屬節(jié)點任務分配策略分發(fā)給從屬節(jié)點。當節(jié)點vi再一次遇到任務分發(fā)者時，將自己已經(jīng)完成的感知任務結(jié)果和來自從屬節(jié)點的感知任務結(jié)果傳遞給任務分發(fā)者。

3)從屬節(jié)點也開始按照工作量從小到大的順序依次執(zhí)行分配給自己的感知任務。等到再一次自己遇到自己的中樞節(jié)點時，將自己已經(jīng)完成的感知任務結(jié)果傳遞給中樞節(jié)點。

4)一直等到任務分發(fā)者接收到所有感知任務的執(zhí)行結(jié)果后，過程終止。

下面對該任務分配與分發(fā)算法的實際應用可行性進行分析。算法1至3將網(wǎng)絡全局信息即關(guān)系矩陣λ[n][n]作為輸入，且僅被任務分發(fā)者使用，而剩余其他節(jié)點在完成感知任務的整個流程中均不需要關(guān)系矩陣λ[n][n]。而在實際系統(tǒng)實現(xiàn)中可參與群智感知任務的移動節(jié)點會向系統(tǒng)提交注冊信息，可要求移動節(jié)點上報自己與整個網(wǎng)絡其他節(jié)點的接觸歷史用于計算出整個網(wǎng)絡各節(jié)點之間的關(guān)系。任務分發(fā)者通過系統(tǒng)獲取參與群智感知任務的節(jié)點集的同時，獲取關(guān)系矩陣λ[n][n]即可。因此，由于只有任務分發(fā)者一個節(jié)點需要了解移動機會網(wǎng)絡的全局信息，降低了系統(tǒng)實現(xiàn)難度，具有實際應用可行性。

4 實驗結(jié)果與分析

4.1 實驗環(huán)境

本文使用TheONE模擬器對HTA算法的性能進行驗證，另外將NTA作為對照算法。本次實驗所采用的現(xiàn)實環(huán)境數(shù)據(jù)集是來自StAndrews大學的Andrews_sassy數(shù)據(jù)集[11]。該數(shù)據(jù)集是由來自StAndrews大學的25名志愿者各自所攜帶的裝有傳感器的智能設備記錄的彼此相遇記錄和這些志愿者在Facebook上的社交網(wǎng)絡數(shù)據(jù)組成。另外本次實驗還使用了人工生成的用戶接觸記錄的虛擬數(shù)據(jù)集。用于生成數(shù)據(jù)所采用的用戶移動模型為工作日移動模型(WorkingDayMovementmodel,WDM)[22]，模擬了40位用戶持續(xù)1 944h的活動。各數(shù)據(jù)集的詳細參數(shù)如表1。本文將每個數(shù)據(jù)集中前三分之一時間的相遇記錄用于計算用戶節(jié)點彼此的社交網(wǎng)絡關(guān)系權(quán)重，后三分之二時間的相遇記錄用于模擬實驗。

表1 實驗所用數(shù)據(jù)集的統(tǒng)計信息

此外，針對存在的兩個中樞節(jié)點選擇算法1、2，本文實驗使用改進后的算法2。

為了提高實驗說服力，達到充分實驗的目的，將每個數(shù)據(jù)集中的各個節(jié)點分別作為任務分發(fā)者分配一次感知任務，通過節(jié)點在移動網(wǎng)絡中所具有的社交屬性不同來揭示算法在各種環(huán)境下的性能表現(xiàn)。此外，實驗中用到的感知任務集通過程序隨機生成，由多組具有不同任務數(shù)量和平均workload的數(shù)據(jù)組成，參數(shù)設置如表2。其中任務數(shù)量為100，200和300，平均workload為500,600,…,1 000,2 000,…,5 000s。此外，本次實驗不考慮任務的時效性問題，即任務不會過期，只要任務的結(jié)果能夠傳回任務分發(fā)者即視為任務完成。通過簡單計算，可以得出本次實驗在使用Andrews_sassy數(shù)據(jù)集時，一共進行了3×10×25=750次完整的模擬移動群智感知過程；在使用人工數(shù)據(jù)時，一共進行了3×10×27=810次完整的模擬移動群智感知過程。實驗的結(jié)果采用相同感知任務集下每個節(jié)點做一次任務分發(fā)者時的平均任務完成率和平均AM為評價指標。

4.2 實驗結(jié)果

先對真實數(shù)據(jù)集下的實驗進行分析。圖2顯示了在Andrew_sassy數(shù)據(jù)集和不同任務集下，HTA和NTA在AM方面的相對性能對比結(jié)果。整體而言，HTA大幅縮短了完成任務所需要的平均時間，平均縮短了24.9%。同時，如圖3所示，與NTA相比，HTA在絕大多數(shù)節(jié)點上還實現(xiàn)了任務完成率的大幅提高；對于所有節(jié)點，平均提高了150%。按任務集的平均工作量對實驗分組，結(jié)果顯示任務集數(shù)量越大，HTA算法對平均完成時間所縮短的百分比越大、任務抵達率所提高的百分比也越大。

表2 實驗所用任務集的參數(shù)配置

圖2 HTA相比NTA的AM提升百分比(Andrew_sassy數(shù)據(jù)集)

圖3 HTA相比NTA的消息抵達率提升百分比(Andrew_sassy數(shù)據(jù)集)

下面對人工生成的模擬數(shù)據(jù)集進行性能分析。在所有任務集下，使用HTA得到的AM比使用NTA得到的AM平均縮短34.9%，詳細的AM性能比較如圖4；同時消息抵達率平均有111.1%的提高，詳細的消息抵達率性能比較如圖5。

圖4 HTA相比NTA的AM提升百分比(人工合成數(shù)據(jù)集)

通過圖2和圖4，還可發(fā)現(xiàn)，按任務集的任務數(shù)量分組后，對不同平均工作量的任務集進行對比，結(jié)果顯示HTA算法對任務的AM所實現(xiàn)的改進百分比隨任務集平均工作量的增加而有所降低，但縮短的絕對時間長度是增加的。通過分析得出，這一改進百分比變小的現(xiàn)象是由于任務工作量增加，任務分發(fā)階段消耗的時間t1與任務結(jié)果收集階段消耗的時間t3所占比重減小、任務執(zhí)行階段消耗的時間t2所占比重增加的原因造成的。因此，可以得出結(jié)論，本文所提算法對工作量越小的感知任務集越適用。

圖5 HTA相比NTA的消息抵達率提升百分比(人工合成數(shù)據(jù)集)

根據(jù)性能分析，發(fā)現(xiàn)HTA算法對AM性能的改進程度有差異，根據(jù)數(shù)據(jù)集的具體特點進行分析得出：因為HTA算法依賴于移動機會網(wǎng)絡中各節(jié)點之間的穩(wěn)定強關(guān)系，而作為任務分發(fā)者的節(jié)點遇到的其他節(jié)點在移動機會網(wǎng)絡中的活躍程度各不相同，在任務分發(fā)者節(jié)點與其他普通節(jié)點的相遇次數(shù)較多時，并不能發(fā)揮中樞節(jié)點協(xié)助分發(fā)與收集任務的功效；另一個原因是，某些節(jié)點作為任務分發(fā)者時，與其他節(jié)點的相遇次數(shù)過少或過于集中，不能滿足分配感知任務和接收感知任務結(jié)果的需要，換句話說，就是受限于采用的數(shù)據(jù)集。那么這表明，移動機會網(wǎng)絡的規(guī)模越大，越能發(fā)揮HTA算法在縮短任務分發(fā)與收集階段時間消耗的優(yōu)勢。

5 結(jié)語

如何確定高效的任務分發(fā)與分配策略是移動群智感知數(shù)據(jù)收集的核心問題之一。本文將社交網(wǎng)絡分析中的中心性和社區(qū)概念與任務分配策略結(jié)合，提出一種最小化任務平均完成時間的基于中樞的多任務分配(HTA)算法。該算法的核心思想是經(jīng)過中樞節(jié)點選擇算法篩選出的部分節(jié)點被用于輔助分發(fā)和收集任務數(shù)據(jù)，并參與決策任務分配策略，以進一步降低移動群智感知任務在數(shù)據(jù)分發(fā)與收集上的時間消耗。實驗結(jié)果顯示，本文提出的HTA算法比NTA算法平均縮短了任務完成時間24.9%，同時任務抵達率平均提高了150%。經(jīng)過對實驗結(jié)果的進一步分析，得出該算法在工作量小于1 000s的任務集下更能發(fā)揮優(yōu)勢。

此外，本文所提算法假設感知任務分配給不同移動節(jié)點能夠得到相同結(jié)果?？紤]到不同節(jié)點的活躍度、任務完成能力等會影響感知任務的完成質(zhì)量，以及感知任務可能對地理位置有要求，在實現(xiàn)最小化平均完成時間的同時，如何保證最低數(shù)據(jù)完成質(zhì)量要求將是下一步的研究重點。

)

[1] 趙東,馬華東.群智感知網(wǎng)絡的發(fā)展及挑戰(zhàn)[J].信息通信技術(shù),2014(5):66-70.(ZHAOD,MAHD.Developmentandchallengesofcrowdsensingnetworks[J].InformationandCommunicationsTechnologies, 2014(5): 66-70.)

[2]DUTTAP,AOKIP,KUMARN,etal.Commonsense:participatoryurbansensingusinganetworkofhandheldairqualitymonitors[C]//SenSys’ 09:Proceedingsofthe7thACMConferenceonEmbeddedNetworkedSensorSystems.NewYork:ACM, 2009: 349-350.

[3]KIMS,ROBSONC,ZIMMERMANT,etal.Creekwatch:pairingusefulnessandusabilityforsuccessfulcitizenscience[C]//CHI’ 11:Proceedingsofthe2011SIGCHIConferenceonHumanFactorsinComputingSystems.NewYork:ACM, 2011: 2125-2134.

[4]GANTIR,PHAMN,AHMADIH,etal.GreenGPS:aparticipatorysensingfuel-efficientmapsapplication[C]//MobiSys’ 10:Proceedingsofthe8thInternationalConferenceonMobileSystems,Applications,andServices.NewYork:ACM, 2010: 151-164.

[5]SIMOENSP,XIAOY,PILLAIP,etal.Scalablecrowdsourcingofvideofrommobiledevices[C]//MobiSys’ 13:Proceedingsofthe11thAnnualInternationalConferenceonMobileSystems,Applications,andServices.NewYork:ACM, 2013: 139-152.

[6]RANARK,CHOUCT,KANHERESS,etal.Ear-phone:anend-to-endparticipatoryurbannoisemappingsystem[C]//Proceedingsofthe9thACM/IEEEInternationalConferenceonInformationProcessinginSensorNetworks.NewYork:ACM, 2010: 105-116.

[7] 陳翔,徐佳,吳敏,等.基于社會行為分析的群智感知數(shù)據(jù)收集研究[J].計算機應用研究,2015,32(12):3534-3541.(CHENX,XUJ,WUM,etal.Researchofdatacollectiontechnologyincrowdsensingbasedonsocialbehavioranalysis[J].ApplicationResearchofComputers, 2015, 32(12): 3534-3541.)

[8]PELUSIL,PASSARELLAA,CONTIM.Opportunisticnetwor-king:dataforwardingindisconnectedmobileAdHocnetworks[J].IEEECommunicationsMagazine, 2006, 44(11): 134-141.

[9]BULUTE,SZYMANSKIBK.Exploitingfriendshiprelationsforefficientroutinginmobilesocialnetworks[J].IEEETransactionsonParallelandDistributedSystems, 2012, 23(12): 2254-2265.

[10]SRINIVASANV,MOTANIM,OOIWT.Analysisandimplicationsofstudentcontactpatternsderivedfromcampusschedules[C]//Proceedingsofthe12thAnnualInternationalConferenceonMobileComputingandNetworking.NewYork:ACM, 2006: 86-97.

[11]BIGWOODG,HENDERSONT,REHUNATHAND,etal.CRAWDADdatasetst_andrews_sassy[DS/OL].[2011-06-03]http://crawdad.org/st_andrews/sassy/20110603.

[12]XIAOM,WUJ,HUANGL,etal.Multi-taskassignmentforcrowdsensinginmobilesocialnetworks[C]//INFOCOM2015:Proceedingsofthe2015IEEEConferenceonComputerCommunications.Piscataway,NJ:IEEE, 2015: 2227-2235.

[13]ZHANGX,NEGLIAG,KUROSEJ,etal.Performancemodelingofepidemicrouting[J].ComputerNetworks, 2007, 51(10): 2867-2891.

[14]FRENKIELRH,BADRINATHBR,BORRASJ,etal.Theinfostationschallenge:Balancingcostandubiquityindeliveringwirelessdata[J].IEEEPersonalCommunications, 2000, 7(2): 66-71.

[15]SPYROPOULOST,PSOUNISK,RAGHAVENDRACS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//Proceedingsofthe2005ACMSIGCOMMWorkshoponDelay-TolerantNetworking.NewYork:ACM, 2005: 252-259.

[16] HUI P, CROWCROFT J, YONEKI E.BUBBLE rap: social-based forwarding in delay tolerant networks [C]// Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York: ACM, 2008: 241-250.

[17] ALLAHVERDI A, NG C, CHENG T, et al.A survey of scheduling problems with setup times or costs [J].European Journal of Operational Research, 2008, 187(3): 985-1032.

[18] CHENG T, SIN C.A state-of-the-art review of parallel-machine scheduling research [J].European Journal of Operational Research, 1990, 47(3): 271-292.

[19] LENSTRA J K, SHMOYS D B, TARDOS é.Approximation algorithms for scheduling unrelated parallel machines [J].Mathematical Programming, 1990, 46(1/2/3): 259-271.

[20] KEMPE D, KLEINBERG J, TARDOS é.Maximizing the spread of influence through a social network [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2003: 137-146.

[21] WANG Y, CONG G, SONG G, et al.Community-based greedy algorithm for mining top-kinfluential nodes in mobile social networks [C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2010: 1039-1048.

This work is partially supported by the National Natural Science Foundation of China (61370065, 61502040), the Program for Excellent Talents in Beijing Municipality (2014000020124G099), the Open Program of the Beijing Key Laboratory of Internet Culture and Digital Dissemination (ICDD201406), the Program of Key Laboratory of Modern Measurement & Control Technology (Ministry of Education)/Beijing Key Laboratory of Electromechanical System Measurement and Control (KF20151123205).

XU Zhe, born in 1993, M.S.candidate.His research interests include crowdsensing.

LI Zhuo, born in 1983, Ph.D., lecturer.His research interests include mobile wireless networks, distributed computing.

CHEN Xin, born in 1965, Ph.D., professor.His research interests include network performance evaluation, network security.

Multi-task assignment algorithm for mobile crowdsensing

XU Zhe1, LI Zhuo1,2*, CHEN Xin1

(1.SchoolofComputerScience,BeijingInformationScienceandTechnologyUniversity,Beijing100101,China;2.BeijingKeyLaboratoryofInternetCultureandDigitalDissemination(BeijingInformationScienceandTechnologyUniversity),Beijing100101,China)

Data transmission based on opportunistic communication in mobile crowdsensing may take a long period of time.To address this issue, a new Hub-based multi-Task Assignment (HTA) algorithm was proposed.In this algorithm, some nodes were selected to perform as the hubs which could help the requester node to deliver the tasks, according to the different characteristics of the social relationship of the nodes in mobile networks.When the task requester encountered a hub node, the hub node itself and its slave nodes were assigned tasks.After that, the hub node would distribute the tasks to the salve nodes, and received the results from them.Simulations were conducted on The ONE simulator.Compared with the oNline Task Assignment (NTA) algorithm, HTA algorithm reduced the time cost by 24.9% on average and improved the task completion ratio by 150% on average.The experimental results demonstrate that HTA algorithm can accelerate the accomplishment speed of the task and reduce the time cost.

mobile crowdsensing; opportunistic communication; multi-task assignment; social relationship; hub node

2016-08-01;

2016-08-12。 基金項目:國家自然科學基金資助項目(61370065, 61502040)；北京市優(yōu)秀人才培養(yǎng)資助青年骨干個人項目(2014000020124G099)；網(wǎng)絡文化與數(shù)字傳播北京市重點實驗室資助項目(ICDD201406)；現(xiàn)代測控技術(shù)教育部重點實驗室/機電系統(tǒng)測控北京市重點實驗室資助項目(KF20151123205)。

徐哲(1993—)，男，山東陽谷人，碩士研究生，主要研究方向：移動群智感知； 李卓(1983—)，男，河南南陽人，講師，博士，CCF會員，主要研究方向：移動無線網(wǎng)絡、分布式計算； 陳昕(1965—)，男，江西南昌人，教授，博士，CCF會員，主要研究方向：網(wǎng)絡性能評價、網(wǎng)絡安全。

1001-9081(2017)01-0018-06

10.11772/j.issn.1001-9081.2017.01.0018

TP393.01

A