基于聚類分析的群智感知任務分配

何杏宇，董一鵬，王 靜，何 姝，陶 凝，楊桂松

(1.上海理工大學 出版印刷與藝術設計學院，上海 200093；2.上海理工大學 光電信息與計算機工程學院，上海 200093)

0 引言

群智感知（Crowd Sensing）是結合眾包思想和移動設備感知能力的一種數據獲取方式，通過在移動設備之間形成交互式的、參與式的感知網絡，并將感知任務分配給網絡中的個體或群體來完成，任務參與者通過分工合作實現感知任務的協同與感知數據的收集。當前，群智感知已應用于臨床和心理實驗的研究[1]、評估暴力人群[2]、道路異常檢測[3]、空氣質量監測[4]等多方領域中。

群智感知中任務分配方法具有兩種模式：集中式感知和機會式感知。集中式感知是利用集中的蜂窩網平臺來分配感知任務，支持實時感知數據的上傳[5-8]。機會式感知是利用節點的機會式接觸進行感知，在這種模式下感知數據可以延時傳輸[9-12]。群智感知具有部署靈活、感知數據多源異構、覆蓋范圍廣泛均勻和高擴展多功能等特點，其中，提高感知覆蓋范圍，有助于獲得較高的感知數據質量。雖然已有很多對感知覆蓋度的研究[13-17]，但較少從結合集中式感知和機會式感知的特點角度來研究的。

本文發現，集中式感知的特點是可以根據預定的感知成本來選擇合適的節點執行任務，通過優化節點的篩選機制來優化全局覆蓋率，有利于保障感知質量和成本的全局可控性，但是難以根據不同區域節點覆蓋率的差異性來調整感知成本在不同區域的分配情況。而機會式感知的特點是較難保障感知質量和成本的全局控制，但可以根據節點局部的實際覆蓋質量來調整局部任務參與節點的個數，從而調節局部感知成本的分配情況。

因此，本文將結合上述兩種感知模式，提出一種兼顧感知質量和成本的局部差異性及全局可控性的任務分配方法，并在該方法中引入聚類分析算法來對節點的移動范圍進行分析。根據分析結果進行任務參與節點的選擇，并通過實驗對本文提出方法的性能進行評估和分析。

1 問題描述與網絡模型

在本文的群智感知網絡模型中，節點是移動的，群智感知任務將分配給兩類節點：集中式參與節點和機會式參與節點。通過移動群智感知平臺直接進行選擇和分配獲得感知任務的節點稱為集中式參與節點，通過集中式參與節點的機會式接觸來獲得感知任務的節點稱為機會式參與節點。網絡中感知任務是由這兩類節點來協同完成的，首先由網絡平臺將任務發布給選中的集中式參與節點，集中式參與節點獲得任務后會在其移動范圍內執行感知任務，并在其遇到機會式參與節點之后將任務復制并傳遞給機會式參與節點。

1.1 節點移動范圍

為了能夠對群智感知網絡中節點的移動范圍進行描述和分析，本文將網絡分成多個互不重疊的分區，然后將每個分區按順序進行標號(A1,A2,A3,…,Ai)，如圖1所示。

圖1 網絡分區示意圖Fig.1 ne twork partition

假設網絡中共有m個節點，節點用Ni表示，這m個節點的集合表示為N={N1,N2,N3,…,Nm}。網絡中每個節點的移動范圍與其工作模式和社會屬性相關，因此具有固定模式。如圖1所示，圓點表示任意節點Ni，三角形所在分區表示此節點的移動范圍，則節點Ni的移動范圍可以表示為分區集合Mi={A2,A5,A6}。如果一個節點被選為參與節點，它可貢獻的感知覆蓋范圍為該節點的移動范圍。本文的目標是在控制參與節點數量的前提下最大化兩類節點所貢獻的總感知覆蓋范圍。

1.2 移動范圍相似度分析

由于集中式參與節點和機會式參與節點之間需進行任務傳遞，要求這兩者具有接觸機會，也就是說需要節點之間有重疊的移動范圍。為了對此進行判斷，本文定義了節點之間的移動范圍相似度，用Si,j來表示節點Ni與Nj的移動范圍相似度，其計算方法為：

其中Si,j∈[0,1]。需要注意的是，當Si，j=0時，Ni與Nj移動范圍不存在重合部分，此時任務無法在Ni與Nj之間傳遞；當Si,j≠0 ，Ni與Nj移動范圍有重合，則它們互相成為親密節點。用Fi表示節點Ni的所有親密節點集合。對于節點Ni與Nj，本文使用num(Fi∩Fj)表示他們之間的共同親密節點數，并且設置了一個共同親密節點數量閾值K。本文將在后續算法中通過判斷num(Fi∩Fj)與K的關系對節點進行分簇。

1.3 感知覆蓋范圍分析

在任務分配中，本文通過局部的覆蓋率差異性來調節局部的成本分配情況。根據網絡中節點的移動范圍相似度將節點分成多個簇。假設預設總任務參與節點個數為Q，形成的簇總數為T，且節點個數和成本在這T個簇中平均分布，那么每個簇都可以均衡選擇Q/T個任務參與節點。實際上由于節點個數和感知質量的局部差異性，每個簇選擇的機會式參與節點個數也可能不均勻，其值等于[Q×n/m]，其中n為簇內節點個數，m為網絡總節點個數。

用V={C1,C2, …,CT}表示簇的集合，簇Ct貢獻的感知覆蓋范圍與其簇頭的選擇有關。也就是說，Ct的簇頭不同，其感知覆蓋范圍也將有所不同。例如，當Ni作為Ct的簇頭時其貢獻的感知覆蓋范圍可以用表示，它是Ni的移動范圍以及Ni選擇的機會式參與節點的移動范圍的并集。假設根據Ni選擇的機會式參與節點為N1,N2,…,Nh，則的計算公式為：

若所有任務參與節點存放在集合Ω中，那么所有的任務參與節點所貢獻的總感知覆蓋范圍用R表示，其計算公式為：

從（3）可以看出，如果想要在控制參與節點數量（成本）的情況下使總感知覆蓋范圍達到最大，既需要單個任務參與節點的移動范圍盡可能大，又需要節點間移動范圍的重合度盡可能小。

2 算法設計與分析

算法 1所示，為了使集中式參與節點之間具有較大的移動范圍相異性，并且保障集中式參與節點與機會式參與節點之間的相遇機會。本文利用聚類分析對網絡中節點的移動范圍進行分析，并對其進行分簇，使同一簇內節點具有相似的移動范圍，不同簇的節點之間的移動范圍具有較大相異性。

算法 1在進行集中式參與節點選擇的同時進行機會式參與節點選擇，在機會式參與節點選擇時，兼顧它們與同簇集中式參與節點之間的移動范圍相似性和相異性。

在每個簇中，簇頭應該具有較廣的移動范圍，它將被選擇作為集中式參與節點接受集中平臺分配的感知任務，并負責其簇內的機會式任務分配，簇中除了簇頭以外的節點被稱為簇成員，它們中的一些節點將會被選擇為機會式參與節點。

2.1 基于移動范圍的分簇

算法1依次選擇節點集合N中的節點，對所選節點之間的共同親密節點數量進行分析。本文以Ni和Nj為例，如果num(Fi∩Fj)大于K，則存在三種分簇處理情況：如果Ni和Nj目前都未并入任何簇，則生成一個包含Ni和Nj的新簇；如果Ni或Nj已經屬于一個已有簇，則將Ni和Nj并入該已有簇；如果Ni和Nj分別屬于兩個已有簇，則將兩個簇合并。當該算法對N中的所有節點都執行了上述與親密節點有關的聚簇分析，則該算法的分簇過程結束。

當上述算法的分簇過程結束，將會形成多個簇，這多個簇的集合用V來表示，N中的節點分別歸屬這些形成的簇。上述算法將從每個簇中選擇能使得該簇的感知覆蓋范圍最大的節點作為簇頭。

2.2 任務參與節點選擇

算法1中，每個簇的簇頭為集中式參與節點，在選取簇頭的過程中也同時進行了機會式參與節點的選擇。例如，當Np作為Ct的簇頭時該簇的感知覆蓋范圍為，給定Up表示Np和根據Np選擇的機會式參與節點的集合。表1所示算法首先將Np并入Up，然后依次選擇機會式參與節點并入Up，且它每次選擇機會式參與節點需要滿足三個基本條件。1）此節點應該位于Ct中；2）此節點需要使實現最大化增加且使局部覆蓋質低于預設值w（該預設值等于總網絡范圍除以總節點個數）；3）最大個數少于[Q*nt/m]。例如，假設選擇的機會式參與節點為Nq，在滿足上述條件的基礎上還應滿足Nq的移動范圍與的交集最小，將Nq并入Up中，并更新當選擇的機會式參與節點總個數為[Q×nt/m]或局部覆蓋率質量高于預設值w，以Np為Ct簇頭時的機會式參與節點選擇完畢。值得注意的是，如果機會式參與節點選擇過程中被選擇節點的所有移動范圍都已被覆蓋，則不應選擇該節點作為機會式參與節點。

上述在選擇集中式參與節點的同時選擇機會式參與節點只是預選方案，而被選擇的集中式參與節點將攜帶預分配的成本移動，當其遇到預選擇的移動式參與節點時將任務分配出去（實際也有可能沒有遇到預選擇的移動式參與節點）。

表1 基于聚簇分析的任務參與節點選擇算法（算法1）Tab.1 Task participation node selection algorithm based on cluster analysis (Algorithm 1)

3 實驗設計與分析

為了評估所提出算法的性能，本文利用文獻[18]中的數據集進行了仿真實驗，此數據集是由182個用戶在五年多的時間中收集到的，包括用戶的17 621條軌跡信息。本文將數據集的網絡劃分為25個分區，并隨機選擇網絡中100個用戶節點進行實驗。這些實驗中主要考慮4個不同的參數：1）網絡分區的數量；2）網絡中節點的數量；3）選擇的任務參與節點數上限Q；4）節點共同親密節點數量閾值K。通過設置任務參與節點數上限Q來控制實驗中最多可選擇的任務參與節點數，而閾值K則是分簇的關鍵條件。用P表示最終的覆蓋率，其等于總感知覆蓋范圍R中分區數量與總分區數25的比值。

3.1 性能對比

在機會網絡中進行機會式參與節點選擇的最基本算法為Epidemic算法[19]，即平臺將任務發布給一個集中式參與節點，然后此節點將任務復制給它接觸到的所有節點。為了驗證本文所提出算法的優勢，將其與Epidemic算法和文獻[20]中的集中式ILB算法進行對比。在比較這三種算法時，固定閾值K的值為0，調節任務參與節點數上限Q，比較三種算法最終的覆蓋率大小。為了避免實驗的偶然性和隨機因素帶來的影響，針對同一個參數進行一百組實驗，取平均值作為最后的結果，對比結果如圖2所示。

圖2 覆蓋率對比（K=0）Fig.2 Comparison of coverage ratio

由圖2可以看出在閾值K和節點數上限Q一定時，本文算法能達到的覆蓋率明顯高于其余兩種對比算法，說明本文的算法在有成本限制的情況下提高覆蓋率方面具有較為明顯的優勢。

3.2 參數K和Q對本文算法的影響

由于任務參與節點的選擇和分簇是密切相關的，而實驗中對分簇起關鍵性作用的是閾值K，K不同則分出的簇中包含的節點也不同，因此最后的覆蓋率也會存在差異。本文將閾值K和節點數上限Q分別設置為：K=[0, 1, 2,…, 10]、Q=[5, 10,15, 20, 25]，每組參數均進行100組實驗，通過多次實驗取平均值的方式，計算覆蓋率與閾值K的關系，如圖3所示。

圖3 覆蓋率與閾值K的關系Fig.3 Relation between coverage ratio and K

由圖3的實驗結果可以看出，在閾值K≤3時覆蓋率處于一個較高的水平，當K＞3時隨著K值的增大，曲線整體處于一個下降的趨勢，這是因為如果K值較大，會使得某些節點變成孤立節點。雖然孤立節點能夠擴大覆蓋率但是本文不會選擇其作為集中式參與節點，因為其不能將任務復制給機會式參與節點，因此當閾值K過大時會導致覆蓋率降低。同時本文發現當Q=15和Q=20時覆蓋率處于一個較高水平，而當Q=5時覆蓋率處于一個過低的水平，而Q=25時覆蓋率基本上不再增加。這說明如果選擇的節點過少，會導致覆蓋率無法達到一個較高水平，選擇的節點過多則會使成本增加但無法增加覆蓋率。據此本文通過固定K，改變Q的值進行多次實驗，結果如圖4所示。

圖4 覆蓋率與節點數上限的關系Fig.4 Relation between coverage ratio and K and the number threshold of nodes

由圖4可以看出，當閾值K不變時，在節點數Q＜12的情況下，隨著節點數Q的增大，覆蓋率會有較大幅度的增加，當Q≥13時覆蓋率的增加幅度變緩，這說明當選擇的節點數過小時覆蓋率無法達到一個較高水平，而如果選擇的節點數過多，則會導致成本不斷增加而覆蓋率幾乎不再增長。從實驗結果中可以看出當Q的值在13到19之間時，覆蓋率能夠增長到一個最高水平，此時不宜選擇更多的參與節點。

4 結論

本文研究了一種兼顧感知質量和成本的局部差異性和全局可控性的任務分配方法。本文首先對網絡中所有節點的移動范圍進行聚類分析以進行分簇，然后選擇使簇的感知覆蓋范圍最大的節點作為集中式參與節點，再從簇中選擇與集中式參與節點有相遇機會且能夠擴大簇的感知覆蓋范圍的節點作為機會式參與節點。通過實驗對比了本文算法、Epidemic算法和ILB算法的性能，發現在具有成本限制的情況下本文算法能達到的覆蓋率明顯優于其余兩種算法。此外，實驗結果還揭示了參數K和Q對本文算法產生的影響。本文下一步將利用除了移動范圍以外的更多特征來對節點進行聚類優化。