龍浩，張書奎，張洋，張力

（1.蘇州大學計算機科學與技術學院，江蘇 蘇州 215006；2.徐州工業(yè)職業(yè)技術學院信息與電氣工程學院，江蘇 徐州 221002）

1 引言

移動群智感知（MCS,mobile crowd sensing）通過移動終端攜帶者實現(xiàn)對現(xiàn)實世界的實時感知，利用用戶的移動性和社會性等特性完成感知任務，并保證了感知服務的實時性和可靠性[1]。在目前的應用中，MCS 管理系統(tǒng)通過分析用戶之間的移動性、社會性和信任關系，按照一定的約束機制將感知任務進行合理分發(fā)，以此實現(xiàn)感知任務的有效分發(fā)，并最終提高感知數(shù)據(jù)質量和服務效率。MCS 系統(tǒng)結構如圖1 所示。

圖1 MCS 系統(tǒng)結構

目前，人們已經(jīng)開發(fā)了許多群智感知技術的應用，成為實時監(jiān)測城市環(huán)境（如空氣質量[2]、噪聲水平[3]、交通狀況[4]等）的有效手段。在這些應用中，感知任務分配方法主要是基于基礎網(wǎng)絡的集中式分發(fā)，系統(tǒng)中的移動終端大多是通過蜂窩網(wǎng)絡連接到互聯(lián)網(wǎng)，將感知任務分發(fā)到參與者的手機中。該方式一方面將耗費用戶較多的網(wǎng)絡流量，導致收集成本高，降低用戶參與熱情，影響系統(tǒng)可用性；另一方面也給蜂窩網(wǎng)絡帶來較大的負載壓力[5]。

當前的移動終端基本都具備短距離無線通信技術如BlueTooth 或Wi-Fi，當設備進入彼此通信范圍時，可以利用短距離無線技術交換數(shù)據(jù)，即支持機會計算模式。將機會網(wǎng)絡的特性應用到群智感知中，形成機會群智感知網(wǎng)絡，該方式實現(xiàn)的核心是眾包數(shù)據(jù)，任務的分發(fā)和數(shù)據(jù)的收集通過眾包來實現(xiàn)，目前的眾包技術通過激勵機制進行任務分發(fā)，一般包括集中式或分布式2 種模式，主要的焦點集中在任務自身，而任務自身融合多維環(huán)境信息和社會屬性，卻很少考慮到用戶的社會化信息，忽略了任務與節(jié)點的匹配度。由于人們的參與，使MCS具有強烈的社會屬性，且已經(jīng)成為MCS 的首要屬性。另外由于人們之間社會關系相對穩(wěn)定且具有一定的依賴性，網(wǎng)絡中會出現(xiàn)節(jié)點的聚集現(xiàn)象，從而形成不同的社區(qū)。在社區(qū)內(nèi)部，節(jié)點密度較高，相遇頻繁，移動緩慢，而處于不同社區(qū)的節(jié)點相遇概率較低。因此，針對MCS 系統(tǒng)這一屬性，以移動節(jié)點社區(qū)劃分、節(jié)點社會屬性、節(jié)點行為模式為基礎，研究基于可信交互的服務眾包方法，提出了一種基于社區(qū)的任務分發(fā)算法，該方法通過計算移動節(jié)點間的最小生成樹、連接參量、社區(qū)融合度等參數(shù)，將節(jié)點劃分成不同的社區(qū)，然后通過節(jié)點行為模式和感知任務匹配度選取符合任務需求的社區(qū)，最后選取一個社區(qū)中心節(jié)點完成感知任務的分發(fā)與數(shù)據(jù)的回收。本文主要的貢獻包括以下3 個方面。

1)針對現(xiàn)有MCS 應用中社區(qū)劃分算法存在劃分社區(qū)的特征因子單一以及缺乏對社會關系的具體量化等問題，本文通過計算移動節(jié)點間的最小生成樹、連接參量、社區(qū)融合度，抽象和識別出節(jié)點的行為模式，將用戶合理劃分成不同的社區(qū)，該方法能有效地滿足MCS 系統(tǒng)任務分發(fā)需求。

2)設計了社區(qū)行為模式特征值與任務特征值的匹配方法，并選取社區(qū)中心節(jié)點通過改進的自適應層次噴射等待路由算法完成感知任務的分發(fā)。

3)通過大量的實驗，首先驗證了社區(qū)劃分算法的效果，與現(xiàn)有算法相比，所提的方法能夠更加準確地檢測到網(wǎng)絡中具有相似行為特征的社區(qū)結構；然后對比現(xiàn)有的任務分配算法，驗證了所提的方法在任務平均完成時間、任務匹配率和任務分配總效用值等方面都要優(yōu)于對比算法。

2 相關工作

當前隨著嵌入大量傳感器的移動智能終端設備的技術進步，MCS 應用得到快速發(fā)展。在MCS研究中，任務分配是研究的核心點之一。根據(jù)考慮角度和研究內(nèi)容的不同，任務分配方法主要分為2類：以平臺為中心的優(yōu)化算法和以用戶為中心的激勵機制。安健等[6]提出了一種基于公交系統(tǒng)的任務差異化分發(fā)方法，采用覆蓋差異和擴散差異的方法分發(fā)任務，然而該方法在任務分發(fā)準確性和節(jié)點移動距離方面還有待改進。劉琰等[7]提出了一種多任務參與者優(yōu)選方法，選出最佳的參與者集合，使參與者完成任務所移動的總距離最短以降低成本，然而該方法中任務平均完成時間有待進一步提高。Xiao 等[8]根據(jù)用戶的歷史移動數(shù)據(jù)預測用戶的移動軌跡，設計了平均完成時間敏感的在線任務分配算法，然而該方法中等待用戶加入的時間過長，從而拉長了完成任務的平均時間。Yu 等[9]提出了一種多任務多用戶分配的解決方案，以用戶的活動時間為分組依據(jù)，將用戶劃分為多個協(xié)作組。然后，利用匈牙利算法從每個任務的協(xié)作組中選擇每個模塊的最優(yōu)工作者分配任務。然而該方法中用戶劃分的特征過于單一，另外任務分配的匹配方式缺乏依據(jù)。徐哲等[10]提出了一種基于中樞節(jié)點的多任務分發(fā)（HTA,hub-based multi-task assignment）算法，該算法利用節(jié)點在移動網(wǎng)絡中社交關系屬性不同的特點，通過中樞節(jié)點選擇算法將部分節(jié)點作為中樞節(jié)點，并將其用于協(xié)助任務請求節(jié)點分發(fā)任務，然而該方法并未考慮節(jié)點的社交屬性與任務屬性的匹配度。楊玉仁等[11]提出一種基于社交屬性和有效用戶計算的群智感知應用任務分發(fā)算法，針對感知數(shù)據(jù)質量較低和參與者不足等問題，通過社交網(wǎng)絡的有效傳遞，動態(tài)調整實時有效用戶完成任務分發(fā)。該方法在數(shù)據(jù)質量和任務分發(fā)效率方面有較大提高，然而該方法采用貪婪算法選取可信度較高用戶轉發(fā)任務，存在一定的局限性，可能導致任務擴散較慢，從而降低任務分發(fā)效率。Wang 等[12]提出了一種基于時空相關性的群智感知多任務分配方法，利用任務間的隱式時空相關性，采用兩階段任務分配方法，根據(jù)用戶的偏好搜索對應的用戶分發(fā)任務。然而該方法任務匹配搜索對應的用戶需要花費較大的時間成本。張君濤等[13]提出了一種漸進式的任務分發(fā)方法，該方法將任務綁定到任務點，當移動節(jié)點到達任務點時自動接收任務，并漸進式地增加任務點的任務數(shù)量。該方法雖然提高了任務分發(fā)成功率，但是數(shù)據(jù)收集的質量有待提高。目前機會網(wǎng)絡路由算法的提出為MCS 網(wǎng)絡中任務的分發(fā)和數(shù)據(jù)的收集提供了途徑，本文針對MCS 網(wǎng)絡特點設計一種基于層次的噴霧等待路由算法來實現(xiàn)任務的分發(fā)。

3 社區(qū)劃分

現(xiàn)有社區(qū)劃分算法存在劃分社區(qū)的特征因子單一以及缺乏對社會關系的具體量化等問題。針對這些問題，本文提出了一種基于多維社會關系特征的社區(qū)劃分算法。通過量化節(jié)點之間的多維社會關系，將節(jié)點聚類成具有真實社會關系的社區(qū)網(wǎng)絡。針對網(wǎng)絡中的各個節(jié)點，首先構造出節(jié)點的最小生成樹，形成初始社區(qū)，然后計算相鄰節(jié)點間的連接參量，通過連接參量來判斷節(jié)點是否處于同一社區(qū)，完成最小生成樹的合并，形成明顯的社區(qū)結構，最后用社區(qū)融合度來檢驗社區(qū)劃分的緊密度，衡量社區(qū)結構劃分效果，并進行適當調整，從而完成網(wǎng)絡中社區(qū)的最佳劃分，實現(xiàn)用戶接受任務的最佳優(yōu)化。該方法量化了節(jié)點間的多維社會關系和行為特征，并衡量了節(jié)點間的社會關聯(lián)度，考慮了節(jié)點間的實際位置關系，通過社區(qū)融合度有效地處理了重疊社區(qū)的節(jié)點劃分問題。所提的方法主要適用于MCS 系統(tǒng)中任務與用戶群的匹配分發(fā)問題。具體社區(qū)劃分過程如圖2 所示。

3.1 最小生成樹

假設G(V,E)是無向加權網(wǎng)絡，節(jié)點集合V包含了n個節(jié)點，邊集合E包含了e條邊，每一條邊有2 個頂點(vi,vj)在V中。社區(qū)劃分的目標就是要將G劃分成k個社區(qū)：C={c1,c2,…,ck}，其中ci≠?,ci∩cj=?,(i=1:k,j=1:k),

定義1從網(wǎng)絡G中的節(jié)點vi開始，直到包含所有的節(jié)點集合V截止，以任意節(jié)點vi為開始的最小生成樹路徑值的計算式為

圖2 社區(qū)劃分過程

其中，j、x、y為中間相鄰節(jié)點，MST 的構造是通過所有相鄰節(jié)點的權值φ最大值求和[14]，φ(i,j)為計算兩相鄰節(jié)點的權重值，稱作兩節(jié)點的社會關系值，具體計算式為

其中，Γ(vi)表示節(jié)點i的鄰居集。

MST 的建立過程類似最小生成樹算法Prim 的原理，是以網(wǎng)絡中的任意節(jié)點v i∈V作為根節(jié)點，將各連接路徑上最大權值相加。網(wǎng)絡G(V,E)的一棵最小生成樹設為MST(V’,E’),V’=V,|V’|=|V|,E’?E,E’=V-1。在MST 中，本文選擇邊權值最大的條邊，設為集合E*，然后將MST 中在集合E*中的邊移除，得到了個相互獨立的部分，本文把它稱為初始社區(qū)，記為C={c1,c2,…,ch}，

3.2 連接參量

目前大多數(shù)社區(qū)劃分算法通過計算節(jié)點間的相似度和多特征值[15]來實現(xiàn)，然而由于聚類方法的不同，節(jié)點間相似度和特征的定義在不同的算法中各不相同?？紤]到MCS 的應用場景，劃分的最終目標是根據(jù)節(jié)點區(qū)域來分發(fā)不同的任務，因此社區(qū)的劃分主要是根據(jù)節(jié)點間的社會關系和位置聚類形成的，本文社區(qū)劃分方法提出節(jié)點連接參量的定義，將節(jié)點的連接參量定義為節(jié)點間社會關聯(lián)度和位置特征，通過連接參量來實現(xiàn)初始社區(qū)的合并，形成明顯的社區(qū)結構。本文將連接參量量化為2 個值：第一個值是根據(jù)節(jié)點歷史相遇記錄引入的社會壓力度量值（SPM,social pressure metric），用來探測節(jié)點間連接質量，衡量節(jié)點間的社會關聯(lián)度；第二個值是通過GPS 獲取移動用戶的位置特征（經(jīng)度和緯度）并采用歐氏距離公式計算兩節(jié)點的距離作為節(jié)點位置特征。社區(qū)的合并需要根據(jù)節(jié)點間的聯(lián)系緊密度來計算，一般來說2 個節(jié)點屬于朋友或者鄰居，可以認為這2 個節(jié)點聯(lián)系緊密，具有較高的連接質量。然而，存在朋友關系的節(jié)點對可能會處在距離比較遠的2 個區(qū)域，根據(jù)感知任務區(qū)域劃分的特點，這2 個節(jié)點不能劃分到同一社區(qū)，因此，本文需要考慮采用節(jié)點的位置特征值來進行校驗。下面具體對連接參量進行定義。

定義2連接參量包括節(jié)點間社會關聯(lián)度和位置特征，節(jié)點之間的社會關聯(lián)度定義為SPM 的倒數(shù)。節(jié)點間的位置特征值由歐氏距離公式[17]計算獲得。

其中，T為任務執(zhí)行周期，tinter為節(jié)點相遇間隔時間，r為間隔次數(shù)。下面介紹具體合并過程。首先計算初始社區(qū)中任意2 個社區(qū)節(jié)點對的連接質量是否大于閾值ψ，如果大于閾值則計算節(jié)點間距離是否小于閾值ε，2 個條件都滿足則建立2 個節(jié)點的連接，并將2 個節(jié)點保存到同一社區(qū)ci中，直到所有的社區(qū)不能再合并，形成的{c1,c2,…,ck}即為合并的社區(qū)劃分。為了降低節(jié)點間連接參量的計算和判別，本文考慮如果2 個初始社區(qū)中任意節(jié)點對之間的連接質量和距離滿足閾值，則將2 個社區(qū)進行合并。

在社區(qū)合并過程中，可能會有以下問題。首先，假設節(jié)點在一定時間內(nèi)處于有限的遷移場景中。事實上，節(jié)點的活動具有一定的特點，在某個時間段，節(jié)點的活動范圍一般并不會超出所屬社區(qū)的范圍，尤其在接收感知任務期間。第二個問題是有部分節(jié)點移動到別的區(qū)域或者有新的節(jié)點加入。首先可以根據(jù)移動節(jié)點的歷史信息計算是否可以加入對應社區(qū)，如果不滿足條件，本文計算移動節(jié)點或新節(jié)點與鄰居節(jié)點的距離，如果小于閾值ε則加入鄰居節(jié)點社區(qū)。第三個問題是在某個時間段后，大部分節(jié)點進行了移動，社區(qū)需要進行重新劃分。社區(qū)的變化特征超出了本文的范圍，本文將其作為未來的工作。

3.3 社區(qū)融合度

考慮到在實際網(wǎng)絡中社區(qū)結構是自然形成的，社區(qū)內(nèi)部各個節(jié)點的連接比社區(qū)間節(jié)點的連接要緊密得多，然而這只是一個定性的指標。本文提出了社區(qū)融合度的概念，從定量角度來衡量社區(qū)劃分的質量，對一些社區(qū)間的重疊節(jié)點做進一步優(yōu)化，重疊節(jié)點即節(jié)點i∈uk，同時i∈cj，優(yōu)化的目的是將重疊節(jié)點i劃分到對應社區(qū)中。

定義3社區(qū)融合度通過任意節(jié)點i的度來衡量社區(qū)劃分質量。如果?i∈ck，社區(qū)ck應滿足其中，表示節(jié)點i與社區(qū)ck內(nèi)中其他節(jié)點連接邊的條數(shù)，表示節(jié)點i與社區(qū)c外其他節(jié)點連接的邊數(shù)。如果社區(qū)內(nèi)任意節(jié)點與社區(qū)外部節(jié)點的連接，比它與社區(qū)內(nèi)部節(jié)點的連接更緊密，那么就將該節(jié)點調節(jié)到對應社區(qū)。

3.4 社區(qū)劃分算法

社區(qū)劃分算法實現(xiàn)過程主要包括3 個步驟：1)根據(jù)式(2)計算各節(jié)點的權值，構造一棵最小生成樹，然后刪除最小生成樹中集合*E中的邊，將最小生成樹分裂成h個初始社區(qū)；2)根據(jù)式(3)計算相鄰節(jié)點對的連接參量，判斷連接參量是否滿足閾值，將初始社區(qū)進行合并，重復該步驟，直到所有的初始社區(qū)全部合并；3)判斷社區(qū)融合度指標，衡量社區(qū)劃分質量，調節(jié)不滿足定義3 的相關節(jié)點到對應社區(qū)。

算法1社區(qū)劃分算法

輸入網(wǎng)絡G(V,E)，相鄰節(jié)點連接參量閾值ψ和ε

輸出劃分完整的社區(qū)結構集合C={c1,c2,…,ck}

算法1 中節(jié)點對的連接質量判斷閾值ψ需要根據(jù)任務的時間周期來決定，連接距離判定閾值ε需要根據(jù)感知任務區(qū)域的半徑來決定，一般ε∈(50,250)m[18]。算法復雜度分析，首先最小生成樹的建立類似于 Prim 算法，其運行時間是O(|E|+|V|log|V|)=O(m+nlogn)，然后將初始社區(qū)合并時間復雜度為O(n2)，社區(qū)融合度檢驗時間復雜度為k。因此整個社區(qū)劃分算法的時間復雜度為O(n2+nlogn+m)。

4 社區(qū)中心節(jié)點選取與任務分發(fā)

MCS 系統(tǒng)中，感知任務的執(zhí)行主要由移動終端的攜帶者——人來完成，盡管人的移動性是不可控的，但也不是隨機的。大部分人都有自己的活動范圍，比如家、公司、商場等。因此感知系統(tǒng)能夠提前根據(jù)參與者歷史數(shù)據(jù)信息將參與者劃分到某個社區(qū)。一個感知任務可以定義成一個元組（任務內(nèi)容、說明、位置、時間），其中任務內(nèi)容指的是各種感知操作，比如感知噪音，拍一張照片，拍一段視頻等；說明指的是感知任務的要求和參數(shù)，比如錄音時長、照片的像素、視頻格式等；位置包括感知任務區(qū)域的中心坐標和感知半徑；時間指的是感知任務執(zhí)行的時效性。本文考慮根據(jù)感知任務的位置屬性來決定感知任務的分發(fā)，具體方法是將感知任務位置屬性與劃分好的社區(qū)節(jié)點位置進行匹配，判斷是否在感知半徑范圍內(nèi)，如果位于感知半徑范圍內(nèi)的節(jié)點數(shù)達到了任務需求的節(jié)點數(shù)，則將該任務分發(fā)給該社區(qū)中節(jié)點。當新到達的參與者想要參與感知任務時，社區(qū)節(jié)點也可以將感知任務轉發(fā)給他，實現(xiàn)新參與者的動態(tài)加入。

本文方法中將MCS 任務分配給對應的社區(qū)，從而節(jié)省網(wǎng)絡開銷，保證感知任務完成的質量。為了進一步加快任務的分發(fā)速度，需要選取一個社區(qū)的中心節(jié)點來實現(xiàn)社區(qū)任務的分發(fā)。具體流程如圖3 所示。

4.1 社區(qū)中心節(jié)點的選取

圖3 眾包任務節(jié)點選取與任務分發(fā)流程

感知任務的分發(fā)主要分2 個步驟：首先計算社區(qū)行為模式特征值與任務的匹配度，然后確定社區(qū)的中心節(jié)點，將感知任務傳遞給中心節(jié)點。利用機會網(wǎng)絡自適應層次噴射等待路由算法，中心節(jié)點將任務分發(fā)給社區(qū)其他節(jié)點。為了實現(xiàn)任務分發(fā)首先進行如下定義。

定義4社區(qū)行為模式特征值O(ci)主要體現(xiàn)社區(qū)內(nèi)部節(jié)點的個體特征，通過計算社區(qū)節(jié)點對連接參量CP(vi,vj)的平均值來獲得，計算式為

定義5感知任務在選擇社區(qū)的過程中根據(jù)任務自身的特征值和需求，尋找匹配的社區(qū)行為模式，應滿足社區(qū)行為模式特征值O(ci)與任務特征值匹配度不小于K，即滿足以下條件

其中，K為感知任務自身特征值，理想情況下，等于K也能滿足任務的需求，但是感知任務自身的特征以及社區(qū)行為模式特征存在一定的隨機性和不確定性，因此要求O(ci)大于K，以維持一定的冗余和錯誤容忍性。

定義6社區(qū)中心節(jié)點是通過各節(jié)點與社區(qū)其他節(jié)點的邊的條數(shù)來確定的，社區(qū)中某節(jié)點與其他節(jié)點的邊的條數(shù)越多，說明其與其他節(jié)點的連接越緊密。具體計算式為

4.2 感知任務分發(fā)

社區(qū)中心節(jié)點負責將感知任務分發(fā)給社區(qū)內(nèi)的其他節(jié)點，由于節(jié)點的相遇是隨機的，通信的鏈路時常中斷，因此節(jié)點間任務分發(fā)以“存儲-攜帶-轉發(fā)”的路由模式實現(xiàn)相互通信。不同于機會網(wǎng)絡，MCS 網(wǎng)絡并不需要知道感知任務分發(fā)的目的節(jié)點，其目標可以是任意一個或多個移動節(jié)點。本文任務分發(fā)提出了一種新的自適應層次噴射等待路由算法，具體實現(xiàn)步驟如下。

噴霧過程。社區(qū)網(wǎng)絡ci設定社區(qū)中心節(jié)點為網(wǎng)絡的第一層，擁有感知任務副本的中心節(jié)點v1將副本傳遞給第二層沒有獲得任務副本的節(jié)點，直到整個社區(qū)全部擁有任務副本。噴霧過程如圖4 所示。

圖4 節(jié)點噴霧過程

等待過程。進入等待過程的節(jié)點有2 類：一類是在節(jié)點所處的那層其他節(jié)點還沒有獲得任務副本；另一類是該節(jié)點已經(jīng)完成將任務副本傳遞給它的下一層。

層次噴霧等待算法與機會網(wǎng)絡噴霧等待算法不同的地方在于，后者在尋找到目的節(jié)點的過程中，需要考慮增加消息副本數(shù)量、緩存容量、路由代價、傳遞時延。而MCS 網(wǎng)絡中，目的是將任務副本傳遞給社區(qū)所有節(jié)點，在傳遞副本時通過層次傳遞的方法，路由開支已達到最低。因此層次噴霧等待路由算法的性能評估主要是傳遞時延，傳遞時延主要由兩部分組成：相遇時間和等待時間。具體通過以下定義來計算。

定義7社區(qū)網(wǎng)絡中由于人的社會屬性和行為特征基本類似，節(jié)點間的相遇比較有規(guī)律，因此節(jié)點間相遇間隔時間可以根據(jù)歷史的多次相遇間隔時間的平均來計算。圖5 展示了節(jié)點與鄰居的歷史相遇間隔時間。具體的計算式為

其中，Taverage為平均相遇間隔時間，n為平均相遇次數(shù)，為i節(jié)點鄰居節(jié)點的個數(shù)。

圖5 節(jié)點與鄰居節(jié)點相遇間隔歷史

當節(jié)點與鄰居節(jié)點的平均相遇間隔時間與節(jié)點等待時間的總和大于或等于感知任務目標時延時，上層節(jié)點需要考慮重傳感知任務，具體判定式為

其中，Twait為節(jié)點等待同一層鄰居節(jié)點獲得任務副本的等待時間，Tdelay為感知任務自帶的目標時延。

4.3 算法實現(xiàn)

感知節(jié)點發(fā)現(xiàn)與任務分發(fā)算法主要包括3 個步驟：1)根據(jù)社區(qū)行為模式特征值O(ci)與任務特征值匹配度來確定符合感知任務需求的社區(qū)；2)根據(jù)式(5)確定社區(qū)中心節(jié)點，由中心節(jié)點負責整個社區(qū)任務分發(fā)；3)由于社區(qū)內(nèi)部節(jié)點相遇符合機會網(wǎng)絡特征，但是MCS 網(wǎng)絡與機會網(wǎng)絡在很多方面又存在不同，因此提出一種層次噴霧等待路由算法，以中心節(jié)點為起始節(jié)點，逐層往外進行噴霧任務，直到社區(qū)所有節(jié)點全部獲得任務副本。

算法2任務分發(fā)算法

輸入劃分好的社區(qū)網(wǎng)絡C={c1,c2,c3,…,cn}

輸出完成子社區(qū)內(nèi)全部節(jié)點的任務分發(fā)

算法時間和空間復雜度分析，步驟1)～步驟9)計算每個子社區(qū)的平均特征值，并與感知任務特征進行比較，時間復雜度為O(n2+n)，空間復雜度為O(n)；步驟10)～步驟12)獲取社區(qū)中心節(jié)點計算，運行時間為O(n)，空間復雜度為O(1)；步驟13)～步驟23)為層次噴霧等待路由算法，按層次將感知任務傳遞給社區(qū)其他節(jié)點，時間復雜度為O(n2)，空間復雜度為O(n)。因此整個算法的時間復雜度為O(n2+n)，空間復雜度為O(n)。

5 仿真實驗結果與分析

仿真實驗分成2 個部分，第一部分驗證社區(qū)劃分算法的效果；第二部驗證基于社區(qū)的任務分發(fā)算法的性能。所有實驗結果至少進行1 000 輪后取平均值。

5.1 社區(qū)劃分算法性能分析

5.1.1實驗參數(shù)設置

為了驗證社區(qū)劃分算法的劃分效果，本文采用LFR 作為測試網(wǎng)絡進行社區(qū)發(fā)現(xiàn)實驗，LFR 是目前社區(qū)發(fā)現(xiàn)算法實驗的基準測試網(wǎng)絡，也是最為常用的模擬數(shù)據(jù)集，它模擬了真實網(wǎng)絡中節(jié)點度和社區(qū)大小的無標度性質，用來評價算法發(fā)現(xiàn)社區(qū)的質量。通過設置不同的混合參數(shù)，能夠生成不同類型的模擬網(wǎng)絡，節(jié)點間的權重隨機生成。使用Java 語言在myclipse 編程實現(xiàn)。本文算法與常見典型社區(qū)發(fā)現(xiàn)算法進行了對比實驗，采用的對比算法主要包括：基于增量密度的社區(qū)發(fā)現(xiàn)算法（IncOrder）[19]，基于最優(yōu)生成樹和模塊的社區(qū)劃分算法（CDMSTD）[14]。采用歸一化互信息（NMI,normalized mutual information）、調整蘭德系數(shù)（ARI,adjusted rand index）和模塊度量Q值這3 種評價方法評價社區(qū)發(fā)現(xiàn)算法的效果，驗證社區(qū)結構的有效性、合理性和正確性。歸一化互信息用來度量通過算法劃分社區(qū)和真實社區(qū)之間的差異程度。當算法劃分的社區(qū)與原始社區(qū)完全一致時，NMI=1；當完全不一致時，NMI=0。調整蘭德系數(shù)[19]可以用來評價社區(qū)發(fā)現(xiàn)算法的效率和劃分社區(qū)與真實社區(qū)的吻合程度。ARI 越接近于1，表示社區(qū)之間的關系越獨立；ARI 越接近于0，表示社區(qū)之間的關系越緊密。實驗中LFR 基準網(wǎng)絡設置參數(shù)如表1 所示。

表1 LFR 基準測試網(wǎng)絡參數(shù)設置

在表1 中，本文列出a 和b 這2 種綜合網(wǎng)絡的參數(shù)，其中a 代表網(wǎng)絡劃分的社區(qū)數(shù)相對較少，b 代表網(wǎng)絡劃分的社區(qū)數(shù)相對較多。n表示節(jié)點的總數(shù)；m表示節(jié)點之間邊的總數(shù)；k表示網(wǎng)絡中節(jié)點間平均權重；minc表示最小社區(qū)包含的節(jié)點的數(shù)量；maxc表示最大社區(qū)包含的節(jié)點的數(shù)量；mu 表示節(jié)點與社區(qū)外部連接的概率，定義為重疊參數(shù)。LFR 基準網(wǎng)絡中，mu 的值越大，社區(qū)發(fā)現(xiàn)的難度就越大。

在社會網(wǎng)絡社區(qū)劃分算法研究中，模塊度量Q值是目前常用的一種衡量社區(qū)結構穩(wěn)定度的方法，社區(qū)內(nèi)部的節(jié)點連接緊密，社區(qū)之間的節(jié)點連接稀疏。在社區(qū)中，同一社區(qū)內(nèi)的節(jié)點交互相對社區(qū)之間的節(jié)點交互比較頻繁，各個社區(qū)均是相對穩(wěn)定的結構，社區(qū)結構越穩(wěn)定表明社區(qū)劃分結果越好。因此，本文用模塊度量Q值作為社區(qū)劃分好壞的衡量標準。模塊度量Q值本是用于衡量無權社會網(wǎng)絡結構的劃分結果，由于考慮到連接強度Si,j，本文采用改進的模塊度量值，具體計算式為

5.1.2性能評價與分析

在LFR 基準網(wǎng)絡中，針對每個重疊參數(shù)mu 值，在實驗中隨機生成20 個模擬網(wǎng)絡，首先針對3 個算法分別在20 個模擬網(wǎng)絡上運行，分別得到它們的NMI和ARI 的平均值。算法對比分別如圖6 和圖7 所示。

圖6 LFR 基準網(wǎng)絡中NMI 值的算法對比

圖7 LFR 基準網(wǎng)絡中ARI 值的算法對比

從圖6(a)和圖7(a)中可以觀察到本文算法相比其他2 種算法具有較優(yōu)的社區(qū)檢測結果。尤其當mu＜0.4 時，本文算法的NMI 和ARI 值接近于1，此時的網(wǎng)絡社區(qū)結構比較清晰，能夠很準確地檢測到網(wǎng)絡中的社區(qū)結構，得到的劃分結果幾乎完全接近正確的劃分結果，而檢測結果最差的是CDMSTD。當0.4＜mu＜0.8 時，各個算法的NMI 和ARI 值都隨著mu 的增大迅速下降，此時的網(wǎng)絡結構中，社區(qū)劃分比較混雜，社區(qū)結構內(nèi)部的緊密度較小，而社區(qū)之間的聯(lián)系反而較大，社區(qū)劃分效果都較差，然而，總體來看本文的算法得到的社區(qū)劃分結果相比其他2 種算法都較優(yōu)。在圖6(b)和7(b)中，同樣可以觀察到本文的算法能夠取得較優(yōu)的社區(qū)劃分結果。特別地，當mu＜0.3 時，本文算法的NMI和ARI 值接近于1，得到的劃分結果也都是幾乎接近完全正確的劃分結果。當0.4＜mu＜0.8 時，本文的算法得到的劃分結果相比其他2 個算法也都較優(yōu)。針對a 網(wǎng)絡中0＜mu＜0.6 計算平均ARI，本文的算法準確性平均達到97.3%，平均高于其他2 種算法15.2%。

接下來，通過網(wǎng)頁抓取百度地圖獲取某個城市各個社區(qū)節(jié)點的基本屬性以及節(jié)點之間的實際地理位置距離，作為劃分算法的數(shù)據(jù)依據(jù)來驗證社區(qū)劃分的模塊度量Q值。由于實驗數(shù)據(jù)是從真實的城市社區(qū)獲取，為驗證所提算法的準確性，可以將實驗結果與某城市結構進行比較。已知真實社區(qū)的模塊度量值為0.616 5，采用遍歷社會關系影響因子α的方法得到當α=0.252 3時，本文算法所得模塊度量值與真實社區(qū)的模塊度量值很接近，具體如圖8所示。且當參數(shù)在區(qū)間[0.252,0.542]時，本文算法不僅能達到真實的社區(qū)結構，并且優(yōu)于現(xiàn)有實際社區(qū)結構的模塊度量Q值。

圖8 模塊度Q 值的比較

5.2 任務分發(fā)算法性能分析

5.2.1實驗參數(shù)設置

任務分發(fā)算法相關性能采用ONE 平臺對其進行仿真驗證[20]，選用基于中樞節(jié)點的多任務分發(fā)算法（HTA）[10]和在線任務分配算法（NTA,online task assignment）[21]進行對比實驗。使用現(xiàn)實世界數(shù)據(jù)集ParticipAct[22]和MDC Nokia[23]分別設計MCS 應用系統(tǒng)任務分發(fā)實驗，通過數(shù)據(jù)集中節(jié)點的歷史記錄信息，抽象出節(jié)點的行為特征，然后采用社區(qū)劃分算法將節(jié)點合理劃分成幾個社區(qū)，并根據(jù)感知任務的特征分配給節(jié)點任務，從而驗證社區(qū)劃分后對任務分發(fā)的相關影響。不同任務集的任務平均完成時間提升百分比如圖9 所示。

圖9 不同任務集的任務平均完成時間提升百分比（ParticipAct）

ParticipAct 數(shù)據(jù)集是一個關于MCS 系統(tǒng)的現(xiàn)實實驗數(shù)據(jù)集，涉及超過一年時間的博洛尼亞大學170 名學生彼此相遇記錄和社交關系網(wǎng)絡數(shù)據(jù)。本文使用869 725 個消息樣本進行抽象和識別出節(jié)點的行為模式，使用536 216 個消息樣本用于模擬實驗，將用戶節(jié)點的數(shù)量設置為L=170。MDC Nokia 數(shù)據(jù)集是從2009 年到2011 年3 月收集日內(nèi)瓦湖地區(qū)185 名用戶數(shù)據(jù)，在實驗中用戶攜帶了一個諾基亞N95 手機和應用程序定期收集數(shù)據(jù)，包括藍牙、GPS、電話呼叫、短信等傳感器數(shù)據(jù)。所有采集數(shù)據(jù)（包括GPS 和藍牙）的采樣周期為600 s。本文從MDC Nokia 數(shù)據(jù)集中選擇了1 120 000 個數(shù)據(jù)點的時間序列，然后根據(jù)32 122 個樣本進行抽象，識別出節(jié)點的行為模式，6 538 個樣本用于模擬實驗，用戶節(jié)點的數(shù)量設為L=185。本文將參與者分成不同的社區(qū)來分配任務，并將一些傳感信息混合到數(shù)據(jù)集中來實現(xiàn)本文的方法。這2 個數(shù)據(jù)集提供了用戶參與MCS 活動的真實結果，它具有4 個維度的特征：1)接觸頻率的遷移率較高；2)接觸的異質性較低；3)接觸時間連通性較低；4)可利用的傳感器數(shù)據(jù)豐富。這些數(shù)據(jù)集很好地捕捉到了人們在一個城市之間的偶遇，模擬用戶全天使用智能手機的情況。因此，本文使用不同的任務分配方法進行實驗，其中數(shù)據(jù)集混合了不同的信息源來評估本文提出的方法的性能。

為了充分驗證任務分發(fā)算法的性能，本文將每個數(shù)據(jù)集中的每個節(jié)點都分配一次感知任務集，利用節(jié)點所在不同的社區(qū)來展現(xiàn)算法的性能表現(xiàn)。另外，實驗中本文通過程序隨機生成任務集，分發(fā)的任務集由從小到大的工作量任務組成，任務集編號為1～10，其中任務數(shù)量設為10，對應平均任務工作量為500 s、600 s、…、1 000 s、2 000 s、…、5 000 s。為了簡化操作，任務工作量定義為感知時長。實驗的評價指標包括任務平均完成時間和平均任務完成率。一個感知任務的完成時間等于t1+t2+t3，其中，t1為任務分發(fā)者開始分發(fā)任務到用戶接收到該任務的時長，t2為用戶采集感知數(shù)據(jù)的時長，t3為用戶將感知數(shù)據(jù)提交給任務分發(fā)者的時長。實驗中每個用戶都會分配一個任務集，實驗的目的是分析哪種算法的分配策略可以使任務集中任務平均完成時間最小。本次實驗不考慮任務的時效性問題，即任務不會過期，只要任務的感知數(shù)據(jù)能夠傳回任務分發(fā)者即視為任務完成。平均任務完成率體現(xiàn)的是用戶接收任務集中的任務后，數(shù)據(jù)回收情況。另外本文還從任務匹配率和任務分配總效用這2 個方面對3 種算法進行實驗分析。任務匹配率定義為通過計算任務的位置與用戶所在的位置的匹配程度。任務分配總效用定義為用戶分配的任務集中任務回報值和用戶任務完成率的乘積，其中任務回報值為[0,100][24]，即用戶提交數(shù)據(jù)量與發(fā)布任務的說明中任務要求數(shù)據(jù)量的比值。

5.2.2性能評價與分析

首先本文給出3 種算法時間和空間復雜度的對比。HTA 分為2 個步驟，首先計算數(shù)據(jù)集中的中樞節(jié)點，算法中需要計算每一個節(jié)點是否為中樞節(jié)點，該步驟時間復雜度為O(n3)；然后進行任務分配，其時間復雜度為O(n2)，因此HTA 的整體時間復雜度為O(n3+n2)，空間復雜度為O(n)。NTA 分為3 個部分，計算任務分配時間為O(n)；計算任務的候選匹配集為O(n2)；更新分配結果集為O(n)。因此NTA 時間復雜度為O(n2+n)，空間復雜度也為O(n)。通過以上分析可以看出，HTA 的時間復雜度最大，本文算法和NTA 一樣都優(yōu)于HTA，空間復雜度3 個算法都相同。

本文從圖9 中可以觀察到，在ParticipAct 數(shù)據(jù)集在不同任務集下，本文的算法與HTA、NTA 在任務平均完成時間方面的性能比較結果?？偟膩碚f，由于t1和t3時長較短，本文算法任務完成的平均時間明顯優(yōu)于對比算法，完成任務所需的平均時間縮短了42.2%。與此同時，如圖10 所示，與其他2 個算法相比，由于用戶行為特征與任務特征的較高吻合，本文算法實現(xiàn)了任務完成率的顯著提高，整體而言，平均任務完成率提高了53.1%。從圖10 中可以觀察到，任務集的平均工作量越小,，本文的算法平均完成時間縮短的百分比越大，任務完成率所提高的百分比也越大。

圖10 不同任務集的任務完成率提升百分比（ParticipAct）

下面對MDC Nokia 數(shù)據(jù)集進行性能分析。在所有任務集下，使用本文算法相比其他2 種算法得到的任務平均完成時間平均縮短48.1%，詳細的任務平均完成時間性能比較如圖11 所示。同時任務完成率平均有119.3%的提高，詳細的任務完成率性能比較如圖12 所示。

圖11 不同任務集的任務平均完成時間提升百分比（MDC Nokia）

圖12 不同任務集的任務完成率提升百分比（MDC Nokia）

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

圖13 和圖14 分別為以ParticipAct 為例，不同任務集下3 種算法的任務匹配率和任務分配總效用的對比。由圖13 可知，本文算法由于將用戶根據(jù)其行為模式劃分成社區(qū)，并采用任務特征值與社區(qū)行為特征相匹配的方法分發(fā)任務，因此任務匹配度最高，且隨著任務集中工作量的增多，匹配度變化不大。而NTA 由于采用在線任務分發(fā)的方式，任務匹配度要高于HTA，并且2 種算法的任務匹配度隨著任務集中工作量的增多，任務匹配度下降比較明顯。由圖14 可知，隨著任務集中任務工作量的增加，3 種算法的任務分配總效用值都隨之降低了。本文算法的下降速度比較緩慢，總效用值明顯優(yōu)于對比算法。

圖13 不同任務集的任務匹配率對比

根據(jù)實驗結果分析發(fā)現(xiàn)，本文算法對任務平均完成時間性能的改進程度有差異，從數(shù)據(jù)集的具體特點分析得出：因為本文算法依賴于移動機會網(wǎng)絡中各節(jié)點之間的穩(wěn)定強關系，而作為任務分發(fā)者的節(jié)點遇到的其他節(jié)點在移動機會網(wǎng)絡中的活躍程度各不相同，在社區(qū)中心節(jié)點與其他普通節(jié)點的相遇次數(shù)較多時，不能體現(xiàn)本文路由算法的優(yōu)勢；另外，某些節(jié)點作為社區(qū)中心節(jié)點時，與其他節(jié)點的相遇次數(shù)過少或過于集中，不能滿足分配感知任務和接收感知任務結果的需要，換句話說，就是受限于采用的數(shù)據(jù)集。分析結果表明，當移動節(jié)點規(guī)模越大時，越能發(fā)揮本文算法在縮短任務分發(fā)時間消耗的優(yōu)勢。

圖14 不同任務集的任務分配總效用值對比

6 結束語

在MCS 的任務分發(fā)問題中，需要海量的用戶來完成復雜的感知任務。如何確定高效的任務分發(fā)與數(shù)據(jù)回收策略是MCS 數(shù)據(jù)收集的核心問題之一。本文分析移動終端攜帶者人的社會屬性和行為特點，將社區(qū)的概念與任務分配策略相結合，提出了基于社區(qū)的任務分發(fā)算法，通過計算移動節(jié)點間的最小生成樹、連接參量、社區(qū)融合度，抽象和識別出節(jié)點的行為模式，將節(jié)點劃分成不同的社區(qū)，并計算社區(qū)的中心錨點，由錨點輔助分發(fā)和收集任務數(shù)據(jù)，降低了任務在數(shù)據(jù)分發(fā)和收集上的時間消耗，也提高了MCS 任務用戶群的匹配度。實驗結果顯示，本文提出的算法與其他2 個算法相比任務平均完成時間縮短了45.1%，任務平均完成率提高了86.2%。進一步的實驗分析表明，尤其當任務數(shù)量多、用戶分布不均、任務涉及的位置更多時，本文算法更能體現(xiàn)其優(yōu)勢?？紤]到不同節(jié)點的活躍度和完成任務的經(jīng)驗，后續(xù)工作主要針對在保證完成任務的平均時間成本和完成率的同時，如何保證感知數(shù)據(jù)完成質量符合量化要求。