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

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

0 引言

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

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

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

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

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

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

1.1 節(jié)點(diǎn)移動(dòng)范圍

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

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

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

1.2 移動(dòng)范圍相似度分析

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

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

1.3 感知覆蓋范圍分析

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

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

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

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

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

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

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

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

2.1 基于移動(dòng)范圍的分簇

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與分析

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

3.1 性能對(duì)比

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

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

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

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

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

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

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

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

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

4 結(jié)論

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