基于聚類分析的群智感知任務(wù)分配

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

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

0 引言

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

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

本文發(fā)現(xiàn)，集中式感知的特點是可以根據(jù)預(yù)定的感知成本來選擇合適的節(jié)點執(zhí)行任務(wù)，通過優(yōu)化節(jié)點的篩選機(jī)制來優(yōu)化全局覆蓋率，有利于保障感知質(zhì)量和成本的全局可控性，但是難以根據(jù)不同區(qū)域節(jié)點覆蓋率的差異性來調(diào)整感知成本在不同區(qū)域的分配情況。而機(jī)會式感知的特點是較難保障感知質(zhì)量和成本的全局控制，但可以根據(jù)節(jié)點局部的實際覆蓋質(zhì)量來調(diào)整局部任務(wù)參與節(jié)點的個數(shù)，從而調(diào)節(jié)局部感知成本的分配情況。

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

1 問題描述與網(wǎng)絡(luò)模型

在本文的群智感知網(wǎng)絡(luò)模型中，節(jié)點是移動的，群智感知任務(wù)將分配給兩類節(jié)點：集中式參與節(jié)點和機(jī)會式參與節(jié)點。通過移動群智感知平臺直接進(jìn)行選擇和分配獲得感知任務(wù)的節(jié)點稱為集中式參與節(jié)點，通過集中式參與節(jié)點的機(jī)會式接觸來獲得感知任務(wù)的節(jié)點稱為機(jī)會式參與節(jié)點。網(wǎng)絡(luò)中感知任務(wù)是由這兩類節(jié)點來協(xié)同完成的，首先由網(wǎng)絡(luò)平臺將任務(wù)發(fā)布給選中的集中式參與節(jié)點，集中式參與節(jié)點獲得任務(wù)后會在其移動范圍內(nèi)執(zhí)行感知任務(wù)，并在其遇到機(jī)會式參與節(jié)點之后將任務(wù)復(fù)制并傳遞給機(jī)會式參與節(jié)點。

1.1 節(jié)點移動范圍

為了能夠?qū)θ褐歉兄W(wǎng)絡(luò)中節(jié)點的移動范圍進(jìn)行描述和分析，本文將網(wǎng)絡(luò)分成多個互不重疊的分區(qū)，然后將每個分區(qū)按順序進(jìn)行標(biāo)號(A1,A2,A3,…,Ai)，如圖1所示。

圖1 網(wǎng)絡(luò)分區(qū)示意圖Fig.1 ne twork partition

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

1.2 移動范圍相似度分析

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

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

1.3 感知覆蓋范圍分析

在任務(wù)分配中，本文通過局部的覆蓋率差異性來調(diào)節(jié)局部的成本分配情況。根據(jù)網(wǎng)絡(luò)中節(jié)點的移動范圍相似度將節(jié)點分成多個簇。假設(shè)預(yù)設(shè)總?cè)蝿?wù)參與節(jié)點個數(shù)為Q，形成的簇總數(shù)為T，且節(jié)點個數(shù)和成本在這T個簇中平均分布，那么每個簇都可以均衡選擇Q/T個任務(wù)參與節(jié)點。實際上由于節(jié)點個數(shù)和感知質(zhì)量的局部差異性，每個簇選擇的機(jī)會式參與節(jié)點個數(shù)也可能不均勻，其值等于[Q×n/m]，其中n為簇內(nèi)節(jié)點個數(shù)，m為網(wǎng)絡(luò)總節(jié)點個數(shù)。

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

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

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

2 算法設(shè)計與分析

算法 1所示，為了使集中式參與節(jié)點之間具有較大的移動范圍相異性，并且保障集中式參與節(jié)點與機(jī)會式參與節(jié)點之間的相遇機(jī)會。本文利用聚類分析對網(wǎng)絡(luò)中節(jié)點的移動范圍進(jìn)行分析，并對其進(jìn)行分簇，使同一簇內(nèi)節(jié)點具有相似的移動范圍，不同簇的節(jié)點之間的移動范圍具有較大相異性。

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

在每個簇中，簇頭應(yīng)該具有較廣的移動范圍，它將被選擇作為集中式參與節(jié)點接受集中平臺分配的感知任務(wù)，并負(fù)責(zé)其簇內(nèi)的機(jī)會式任務(wù)分配，簇中除了簇頭以外的節(jié)點被稱為簇成員，它們中的一些節(jié)點將會被選擇為機(jī)會式參與節(jié)點。

2.1 基于移動范圍的分簇

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

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

2.2 任務(wù)參與節(jié)點選擇

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

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

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

3 實驗設(shè)計與分析

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

3.1 性能對比

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

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

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

3.2 參數(shù)K和Q對本文算法的影響

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

圖3 覆蓋率與閾值K的關(guān)系Fig.3 Relation between coverage ratio and K

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

圖4 覆蓋率與節(jié)點數(shù)上限的關(guān)系Fig.4 Relation between coverage ratio and K and the number threshold of nodes

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

4 結(jié)論

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