郭 慧,程良倫

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510006)

0 概述

移動(dòng)互聯(lián)網(wǎng)業(yè)務(wù)正在迅速發(fā)展。感知區(qū)域的高覆蓋率是保證移動(dòng)感知任務(wù)成功執(zhí)行的基礎(chǔ)[1],不同的感知任務(wù)有其特定的時(shí)空限制,且參與節(jié)點(diǎn)也有自身的移動(dòng)特征[2]。大量移動(dòng)節(jié)點(diǎn)的參與會造成服務(wù)器數(shù)據(jù)冗余,且在節(jié)點(diǎn)達(dá)到一定數(shù)量之后,覆蓋率并不會隨其數(shù)量的增加而提高[3]。因此,選擇合適的移動(dòng)感知節(jié)點(diǎn)來執(zhí)行感知任務(wù)勢在必行[4]。

文獻(xiàn)[5]研究了機(jī)會感知中的用戶選擇:首先研究靜態(tài)節(jié)點(diǎn)選擇問題,之后將其推廣到具有不確定性移動(dòng)軌跡的用戶移動(dòng)模型中進(jìn)行研究。文獻(xiàn)[6]提出一種移動(dòng)群智感知(Mobile Crowdsensing,MCS)系統(tǒng),文獻(xiàn)[7]針對個(gè)人用戶的能源消耗及由數(shù)據(jù)傳輸引起的隱私問題,研究MCS系統(tǒng)中的任務(wù)分配問題。為了使選擇節(jié)點(diǎn)之后得到的覆蓋范圍最大,研究人員從任務(wù)組織者[8]、執(zhí)行者[9]以及不同的激勵(lì)代價(jià)[10]出發(fā),研究了移動(dòng)互聯(lián)網(wǎng)感知用戶選擇問題。此外,文獻(xiàn)[11]針對多節(jié)點(diǎn)少任務(wù)及多任務(wù)少節(jié)點(diǎn)2種情況來研究移動(dòng)互聯(lián)網(wǎng)感知節(jié)點(diǎn)選擇;文獻(xiàn)[12]在考慮不同的感知數(shù)據(jù)精度要求及節(jié)點(diǎn)的移動(dòng)性與任務(wù)的特定時(shí)空屬性要求的情況下,研究移動(dòng)感知中基于位置的近優(yōu)任務(wù)分配算法;文獻(xiàn)[13]針對移動(dòng)感知中基于位置的優(yōu)化分配算法,提出一種基于鏈路可靠性的AdHoe網(wǎng)絡(luò)路由協(xié)議(LRBA)分配算法,獲得的數(shù)據(jù)精度是傳統(tǒng)算法的5倍。但以上研究絕大多數(shù)未考慮任務(wù)的特殊時(shí)空屬性或未研究節(jié)點(diǎn)位置之間的關(guān)聯(lián)性。

文獻(xiàn)[14]基于聯(lián)盟的協(xié)同方法研究了一種交通信息采集傳感器網(wǎng)絡(luò)任務(wù)分配方法;文獻(xiàn)[15]提出用自適應(yīng)隨機(jī)閾值算法來研究空間眾包環(huán)境下的3類對象在線任務(wù)分配。前者只針對特定的應(yīng)用,不具有通用性,而后者任務(wù)分配時(shí),并未考慮節(jié)點(diǎn)冗余問題及覆蓋率問題。

本文針對國內(nèi)外對于移動(dòng)節(jié)點(diǎn)選擇忽略研究節(jié)點(diǎn)位置的關(guān)聯(lián)性問題,提出一種移動(dòng)互聯(lián)網(wǎng)基于時(shí)空關(guān)注的移動(dòng)感知節(jié)點(diǎn)選擇算法。該算法根據(jù)節(jié)點(diǎn)位置之間的關(guān)聯(lián)性及任務(wù)的時(shí)空要求來選擇移動(dòng)感知節(jié)點(diǎn)。

1 問題描述

假設(shè)在一個(gè)大區(qū)域內(nèi)有多個(gè)移動(dòng)感知節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)只能感知一個(gè)小區(qū)域的信息,且所有移動(dòng)感知節(jié)點(diǎn)的歷史軌跡已知但下一時(shí)刻的位置未知。根據(jù)移動(dòng)感知節(jié)點(diǎn)的感知范圍,將區(qū)域劃分成若干個(gè)子區(qū)域。如果在一個(gè)感知周期內(nèi)的某個(gè)時(shí)間段有移動(dòng)節(jié)點(diǎn)經(jīng)過一個(gè)子區(qū)域,則認(rèn)為該子區(qū)域在該感知周期內(nèi)被覆蓋。

本文的目標(biāo)就是在一定的感知周期內(nèi),通過研究節(jié)點(diǎn)位置之間的關(guān)聯(lián)性,在給定歷史軌跡的所有移動(dòng)節(jié)點(diǎn)中選擇一個(gè)最小數(shù)量的移動(dòng)節(jié)點(diǎn)參與者集合,使該集合節(jié)點(diǎn)的感知區(qū)域覆蓋率大于或等于一個(gè)提前定義的覆蓋閾值。

本文提出的移動(dòng)節(jié)點(diǎn)選擇問題可通過以下數(shù)學(xué)模型來描述:假設(shè)所有移動(dòng)節(jié)點(diǎn)的集合為U,U的歷史軌跡的集合為Track(U),感知目標(biāo)區(qū)域E;Tu表示從U中選出來的節(jié)點(diǎn)集合,Ci(Tu)表示在第i個(gè)感知周期,被Tu中的節(jié)點(diǎn)覆蓋的子區(qū)域集合。本文的目標(biāo)就是從U中選擇一個(gè)集合Tu,并且選出的集合Tu滿足以下的限制:

min|Tu|

(1)

(2)

其中,N表示碳檢測任務(wù)中的感知周期總數(shù),Rcover表示閾值覆蓋率。需要注意的是,提前并不知道節(jié)點(diǎn)將何時(shí)出現(xiàn)在某個(gè)感知區(qū)域。

針對上述問題,本文提出移動(dòng)互聯(lián)網(wǎng)時(shí)空關(guān)注的移動(dòng)感知節(jié)點(diǎn)選擇算法,其總體流程如圖1所示,主要分為3步:

圖1 移動(dòng)節(jié)點(diǎn)選擇算法總體流程

1)軌跡數(shù)據(jù)輸入。在數(shù)據(jù)輸入階段,輸入全部節(jié)點(diǎn)的歷史移動(dòng)軌跡數(shù)據(jù),為下一階段的數(shù)據(jù)處理做準(zhǔn)備。

2)移動(dòng)節(jié)點(diǎn)軌跡預(yù)測。在數(shù)據(jù)處理階段,將節(jié)點(diǎn)的軌跡數(shù)據(jù)進(jìn)行映射,通過計(jì)算得到每個(gè)節(jié)點(diǎn)在某個(gè)特定周期出現(xiàn)在各小區(qū)域范圍內(nèi)的概率,進(jìn)而預(yù)測感知節(jié)點(diǎn)的移動(dòng)概率。

3)移動(dòng)節(jié)點(diǎn)選擇。在節(jié)點(diǎn)選擇階段,根據(jù)數(shù)據(jù)處理階段的結(jié)果,利用本文的移動(dòng)互聯(lián)網(wǎng)時(shí)空關(guān)注的移動(dòng)感知節(jié)點(diǎn)選擇算法,對移動(dòng)感知節(jié)點(diǎn)進(jìn)行選擇。

4)選擇的結(jié)果輸出,并進(jìn)行性能分析。

2 移動(dòng)節(jié)點(diǎn)軌跡預(yù)測

假設(shè)所有的參與節(jié)點(diǎn)的歷史軌跡提前已知,本階段將利用歷史軌跡來計(jì)算每個(gè)節(jié)點(diǎn)的下一周期的移動(dòng)位置概率。

2.1 數(shù)據(jù)準(zhǔn)備及映射

映射移動(dòng)軌跡:將感知區(qū)域分為若干個(gè)固定的子區(qū)域,給定所有節(jié)點(diǎn)的歷史移動(dòng)軌跡,感知周期也為固定的時(shí)間間隔(例如1 h為一個(gè)周期),該步驟將每個(gè)節(jié)點(diǎn)的軌跡映射到N個(gè)感知周期。然后計(jì)算每個(gè)節(jié)點(diǎn)在每個(gè)感知區(qū)域的每個(gè)感知周期的平均出現(xiàn)次數(shù)λu,i,e(在第4節(jié)有具體闡述),本文假設(shè)感知節(jié)點(diǎn)的出現(xiàn)服從泊松分布[16],表達(dá)式如下:

(3)

其中,λu,i,e是泊松密度,指在某感知周期i,感知節(jié)點(diǎn)u出現(xiàn)在子區(qū)域e的平均次數(shù),n指在特定子周期子區(qū)域節(jié)點(diǎn)u的出現(xiàn)次數(shù)。

2.2 移動(dòng)節(jié)點(diǎn)的預(yù)測概率

預(yù)測感知節(jié)點(diǎn)的移動(dòng)概率:利用之前得到的λu,i,e來估計(jì)節(jié)點(diǎn)概率Pi,e(U),節(jié)點(diǎn)在每個(gè)感知周期i(0≤i≤N)至少在每個(gè)目標(biāo)區(qū)域e(e∈E)出現(xiàn)一次的概率。

(4)

3 移動(dòng)節(jié)點(diǎn)選擇算法

本節(jié)利用第2節(jié)得到的各節(jié)點(diǎn)在各個(gè)周期的概率來選擇節(jié)點(diǎn)。定義處理過程中得到的全部節(jié)點(diǎn)在各周期的概率矩陣集合為元胞數(shù)據(jù)。一個(gè)元胞中包含全部移動(dòng)節(jié)點(diǎn)在對應(yīng)周期的概率矩陣,即元胞中的一個(gè)元素對應(yīng)一個(gè)節(jié)點(diǎn)在固定周期的概率矩陣,此處概率矩陣的元素對應(yīng)固定節(jié)點(diǎn)在固定子周期的子區(qū)域軌跡概率。其選擇算法流程見圖2。

圖2 移動(dòng)節(jié)點(diǎn)選擇算法流程

移動(dòng)節(jié)點(diǎn)選擇算法步驟描述如下:

步驟1計(jì)算每個(gè)節(jié)點(diǎn)在全部周期的有效性,得到有效性矩陣Zallturn。

步驟2將節(jié)點(diǎn)兩兩集合,選出有最大有效性的節(jié)點(diǎn),加入Tu。

步驟3將所有剩余的節(jié)點(diǎn)與Tu結(jié)合,即Tu∪Uremain{j},j∈(1,2,…,h),計(jì)算其有效性,選出擁有最大有效性的節(jié)點(diǎn)加入Tu。

步驟4循環(huán)步驟2,直到得到的覆蓋率不再增加,即為最終節(jié)點(diǎn)集合Tu。覆蓋率是指在特定周期選擇的節(jié)點(diǎn)對感知區(qū)域的覆蓋情況,即在感知周期移動(dòng)節(jié)點(diǎn)的移動(dòng)軌跡對子區(qū)的覆蓋范圍占整體感知區(qū)域的比例。

概率矩陣Zallturn計(jì)算公式如下:

(5)

E∈{[latmin,latmax][lonmin,lonmax]}

(6)

其中,lat表示維度,lon表示經(jīng)度。

給定全部相聯(lián)的集合Tu2∪Uremain{j},本小節(jié)計(jì)算這些相聯(lián)集合的Utility,此處每個(gè)聯(lián)合集合的Utility具體是指在全部的感知周期內(nèi),感知區(qū)域被該相聯(lián)集合的感知節(jié)點(diǎn)覆蓋的期望,計(jì)算公式如下:

(7)

其中,Qi,e(Tu2∪Uremain{j})指某個(gè)給定的區(qū)域在某個(gè)特定感知周期被集合Tu2∪Uremain{j}覆蓋的概率,計(jì)算公式如下:

(8)

在以上得到的眾多Utility中,選擇最大的一個(gè)集合,將其作為新的集合進(jìn)行下一輪的迭代,直到對應(yīng)的覆蓋率不再增加。

例如,假設(shè)已知若干節(jié)點(diǎn)的歷史移動(dòng)軌跡,首先將各個(gè)節(jié)點(diǎn)在對應(yīng)子周期的移動(dòng)軌跡映射在對應(yīng)的子區(qū)域內(nèi),統(tǒng)計(jì)一段時(shí)間內(nèi),節(jié)點(diǎn)在該子周期該子區(qū)域出現(xiàn)的次數(shù),從而求得平均出現(xiàn)次數(shù),并利用式(3)和式(4)求出節(jié)點(diǎn)出現(xiàn)在該區(qū)域的概率,再根據(jù)式(5)和式(6)求得概率矩陣。接著,先將節(jié)點(diǎn)兩兩結(jié)合,根據(jù)式(7)和式(8)求出節(jié)點(diǎn)關(guān)聯(lián)有效性,選出關(guān)聯(lián)有效性大的節(jié)點(diǎn)加入感知節(jié)點(diǎn)集合,之后繼續(xù)將感知節(jié)點(diǎn)集合中的節(jié)點(diǎn)與剩余節(jié)點(diǎn)分別結(jié)合,計(jì)算關(guān)聯(lián)有效性,直到得到的集合中的覆蓋率不再增加即為最終的感知節(jié)點(diǎn)集合。

4 仿真與結(jié)果分析

本文采用羅馬市2014年2月的368輛出租車真實(shí)移動(dòng)軌跡[17]作為仿真數(shù)據(jù)集,利用仿真軟件MatlabR2014b,在Window10平臺中仿真本文的節(jié)點(diǎn)選擇算法。因此,根據(jù)羅馬市的實(shí)際地理位置,本文設(shè)定的感知區(qū)域?yàn)榻?jīng)度坐標(biāo)區(qū)間為[41.65°,42.15°],緯度坐標(biāo)區(qū)間為[12.04°,12.84°]的區(qū)域。將目標(biāo)區(qū)域劃分成5×8個(gè)感知子區(qū)域(每個(gè)區(qū)域的大小為0.1緯度×0.1經(jīng)度)。感知時(shí)間設(shè)為8:00—18:00,每個(gè)感知子周期設(shè)定為1 h,即將整個(gè)感知時(shí)間劃分成10個(gè)子區(qū)間。選取100個(gè)出租車作為移動(dòng)感知節(jié)點(diǎn),其上均載有CO2傳感器。

首先,輸入出租車10 d的移動(dòng)軌跡數(shù)據(jù),并且對數(shù)據(jù)進(jìn)行處理,得到節(jié)點(diǎn)在8:00—18:00時(shí)間段的位置坐標(biāo)軌跡數(shù)據(jù)。然后,映射節(jié)點(diǎn)的軌跡數(shù)據(jù)到對應(yīng)的目標(biāo)子區(qū),并對覆蓋子區(qū)進(jìn)行統(tǒng)計(jì)。圖3是8:00—9:00的全部節(jié)點(diǎn)在目標(biāo)區(qū)域的映射圖。

圖3 8:00—9:00時(shí)間段的出租車軌跡

處理10 d的全部周期的移動(dòng)軌跡數(shù)據(jù),求得每個(gè)節(jié)點(diǎn)在每個(gè)周期每個(gè)子區(qū)的平均出現(xiàn)次數(shù),即泊松密度λu,i,e,并根據(jù)式(3)和式(4)計(jì)算每個(gè)節(jié)點(diǎn)在每個(gè)周期的每個(gè)子區(qū)的概率。此處得到的概率即為移動(dòng)節(jié)點(diǎn)的移動(dòng)預(yù)測概率。

經(jīng)過上述計(jì)算,對于每個(gè)周期都得到一個(gè)對應(yīng)的元胞概率數(shù)據(jù)。因此,10個(gè)周期共可得到10個(gè)元胞數(shù)據(jù),分別對應(yīng)感知周期的10個(gè)子周期的軌跡概率情況;利用式(5)和式(6)計(jì)算每個(gè)節(jié)點(diǎn)在整個(gè)感知周期對應(yīng)的軌跡概率矩陣Zallturn。

利用上述處理得到的元胞矩陣,根據(jù)式(7)和式(8)計(jì)算有效性Utility,對本文提出的節(jié)點(diǎn)選擇算法進(jìn)行仿真。本文的移動(dòng)節(jié)點(diǎn)選擇算法選擇的節(jié)點(diǎn),在全部感知周期都參與感知活動(dòng)。即一旦節(jié)點(diǎn)被選擇,其就參加全部的感知周期。仿真得到的最終節(jié)點(diǎn)集合為Tu1={14,335,363,345,99,205,48,260,347,291,340},集合中的數(shù)據(jù)代表被選擇節(jié)點(diǎn)的id值。即這11個(gè)節(jié)點(diǎn)被選擇在8:00—18:00的周期進(jìn)行感知,且要求在每個(gè)子周期,每個(gè)節(jié)點(diǎn)必須要進(jìn)行感知活動(dòng),其得到的最終覆蓋率為75%。本算法選擇的最終覆蓋情況如圖4所示。

圖4 本文算法覆蓋情況

在圖4中,不同的顏色表示不同id的節(jié)點(diǎn)在各子區(qū)域內(nèi)的覆蓋情況。同種顏色的子區(qū)域被相同節(jié)點(diǎn)覆蓋,但是如果有兩個(gè)或多個(gè)節(jié)點(diǎn)都覆蓋同一子區(qū),就顯示為顏色深的節(jié)點(diǎn)顏色。

為了評價(jià)節(jié)點(diǎn)選擇算法的有效性,本文利用其他算法對移動(dòng)節(jié)點(diǎn)進(jìn)行選擇,并對比計(jì)算結(jié)果。

算法1移動(dòng)節(jié)點(diǎn)部分周期參與感知選擇算法,被選擇節(jié)點(diǎn)只在部分周期參與感知。

仿真得到的最終節(jié)點(diǎn)集合為Tu2={287,71,254,287,79,48,340,308,132,22},集合中的數(shù)據(jù)代表選擇的節(jié)點(diǎn)id值。與本文提出的算法不同的是該集合中的節(jié)點(diǎn)只在固定的周期進(jìn)行感知。即id=287的節(jié)點(diǎn)在8:00—9:00的時(shí)間段進(jìn)行感知,id=71的節(jié)點(diǎn)在9:00—10:00的時(shí)間段進(jìn)行感知,以此類推。在一整天的感知結(jié)束之后,得到的最終覆蓋率為65%。算法1選擇的id=287的節(jié)點(diǎn)在8:00—9:00時(shí)間段的目標(biāo)區(qū)域覆蓋情況如圖5所示。

圖5 算法1中id=287節(jié)點(diǎn)在8:00—9:00目標(biāo)區(qū)域覆蓋情況

算法2隨機(jī)選擇算法,被選擇的節(jié)點(diǎn)在整個(gè)周期都進(jìn)行感知。

仿真得到的最終節(jié)點(diǎn)集合為Tu3={135,256,175,182,132,170,17,291,348,180,299},集合中的數(shù)據(jù)代表被選擇節(jié)點(diǎn)的id值。在選擇過程中得到的最大覆蓋率為57.5%。算法2的覆蓋情況如圖6所示。

圖6 算法2覆蓋情況

與圖4相同,圖6中不同的顏色表示不同id的節(jié)點(diǎn)在各子區(qū)域內(nèi)的覆蓋情況。同種顏色的子區(qū)域被相同節(jié)點(diǎn)覆蓋,但是如果有兩個(gè)或多個(gè)節(jié)點(diǎn)都覆蓋同一子區(qū),就顯示為顏色深的節(jié)點(diǎn)顏色。

為了使得實(shí)驗(yàn)結(jié)果更可靠,本文繼續(xù)處理數(shù)據(jù)集中的數(shù)據(jù),將剩余數(shù)據(jù)分為5 d的周期和13 d的周期對本文算法及對比算法進(jìn)行了進(jìn)一步的測試,得到的5 d周期的本文算法、算法1及算法2的最大覆蓋率分別是75.0%、65.0%及57.5%;13 d周期的本文算法、算法1及算法2的最大覆蓋率分別是77.5%、70.0%及40.0%。3種算法分別在3種處理周期得到的覆蓋率求平均值如表1所示。

表1 3種算法的平均覆蓋率 %

根據(jù)表1的數(shù)據(jù)繪制性能曲線如圖7所示。由圖7可以看出,本文算法由于被選擇的節(jié)點(diǎn)在整個(gè)周期都進(jìn)行感知,比算法1能獲得更高的覆蓋率,而算法2是覆蓋率最低的算法。

圖7 3種算法覆蓋率曲線圖

5 結(jié)束語

本文針對節(jié)點(diǎn)位置的關(guān)聯(lián)性問題,提出一種移動(dòng)互聯(lián)網(wǎng)時(shí)空關(guān)注的移動(dòng)感知節(jié)點(diǎn)選擇算法,并將其應(yīng)用于碳檢測領(lǐng)域。該算法根據(jù)檢測節(jié)點(diǎn)的歷史移動(dòng)軌跡,預(yù)測其未來在該周期內(nèi)的移動(dòng)軌跡,并依據(jù)移動(dòng)檢測節(jié)點(diǎn)軌跡關(guān)聯(lián)有效性選擇最優(yōu)的參與者集合。仿真結(jié)果證明,本文算法能使用較小數(shù)量的感知節(jié)點(diǎn)達(dá)到較大的覆蓋率。下一步,將本文算法應(yīng)用于實(shí)際碳檢測領(lǐng)域,驗(yàn)證其有效性。