基于時空關注的移動感知節點選擇算法

郭 慧,程良倫

(廣東工業大學 計算機學院,廣州 510006)

0 概述

移動互聯網業務正在迅速發展。感知區域的高覆蓋率是保證移動感知任務成功執行的基礎[1],不同的感知任務有其特定的時空限制,且參與節點也有自身的移動特征[2]。大量移動節點的參與會造成服務器數據冗余,且在節點達到一定數量之后,覆蓋率并不會隨其數量的增加而提高[3]。因此,選擇合適的移動感知節點來執行感知任務勢在必行[4]。

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

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

本文針對國內外對于移動節點選擇忽略研究節點位置的關聯性問題,提出一種移動互聯網基于時空關注的移動感知節點選擇算法。該算法根據節點位置之間的關聯性及任務的時空要求來選擇移動感知節點。

1 問題描述

假設在一個大區域內有多個移動感知節點,每個節點只能感知一個小區域的信息,且所有移動感知節點的歷史軌跡已知但下一時刻的位置未知。根據移動感知節點的感知范圍,將區域劃分成若干個子區域。如果在一個感知周期內的某個時間段有移動節點經過一個子區域,則認為該子區域在該感知周期內被覆蓋。

本文的目標就是在一定的感知周期內,通過研究節點位置之間的關聯性,在給定歷史軌跡的所有移動節點中選擇一個最小數量的移動節點參與者集合,使該集合節點的感知區域覆蓋率大于或等于一個提前定義的覆蓋閾值。

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

min|Tu|

(1)

(2)

其中,N表示碳檢測任務中的感知周期總數,Rcover表示閾值覆蓋率。需要注意的是,提前并不知道節點將何時出現在某個感知區域。

針對上述問題,本文提出移動互聯網時空關注的移動感知節點選擇算法,其總體流程如圖1所示,主要分為3步:

圖1 移動節點選擇算法總體流程

1)軌跡數據輸入。在數據輸入階段,輸入全部節點的歷史移動軌跡數據,為下一階段的數據處理做準備。

2)移動節點軌跡預測。在數據處理階段,將節點的軌跡數據進行映射,通過計算得到每個節點在某個特定周期出現在各小區域范圍內的概率,進而預測感知節點的移動概率。

3)移動節點選擇。在節點選擇階段,根據數據處理階段的結果,利用本文的移動互聯網時空關注的移動感知節點選擇算法,對移動感知節點進行選擇。

4)選擇的結果輸出,并進行性能分析。

2 移動節點軌跡預測

假設所有的參與節點的歷史軌跡提前已知,本階段將利用歷史軌跡來計算每個節點的下一周期的移動位置概率。

2.1 數據準備及映射

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

(3)

其中,λu,i,e是泊松密度,指在某感知周期i,感知節點u出現在子區域e的平均次數,n指在特定子周期子區域節點u的出現次數。

2.2 移動節點的預測概率

預測感知節點的移動概率:利用之前得到的λu,i,e來估計節點概率Pi,e(U),節點在每個感知周期i(0≤i≤N)至少在每個目標區域e(e∈E)出現一次的概率。

(4)

3 移動節點選擇算法

本節利用第2節得到的各節點在各個周期的概率來選擇節點。定義處理過程中得到的全部節點在各周期的概率矩陣集合為元胞數據。一個元胞中包含全部移動節點在對應周期的概率矩陣,即元胞中的一個元素對應一個節點在固定周期的概率矩陣,此處概率矩陣的元素對應固定節點在固定子周期的子區域軌跡概率。其選擇算法流程見圖2。

圖2 移動節點選擇算法流程

移動節點選擇算法步驟描述如下:

步驟1計算每個節點在全部周期的有效性,得到有效性矩陣Zallturn。

步驟2將節點兩兩集合,選出有最大有效性的節點,加入Tu。

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

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

概率矩陣Zallturn計算公式如下:

(5)

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

(6)

其中,lat表示維度,lon表示經度。

給定全部相聯的集合Tu2∪Uremain{j},本小節計算這些相聯集合的Utility,此處每個聯合集合的Utility具體是指在全部的感知周期內,感知區域被該相聯集合的感知節點覆蓋的期望,計算公式如下:

(7)

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

(8)

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

例如,假設已知若干節點的歷史移動軌跡,首先將各個節點在對應子周期的移動軌跡映射在對應的子區域內,統計一段時間內,節點在該子周期該子區域出現的次數,從而求得平均出現次數,并利用式(3)和式(4)求出節點出現在該區域的概率,再根據式(5)和式(6)求得概率矩陣。接著,先將節點兩兩結合,根據式(7)和式(8)求出節點關聯有效性,選出關聯有效性大的節點加入感知節點集合,之后繼續將感知節點集合中的節點與剩余節點分別結合,計算關聯有效性,直到得到的集合中的覆蓋率不再增加即為最終的感知節點集合。

4 仿真與結果分析

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

首先,輸入出租車10 d的移動軌跡數據,并且對數據進行處理,得到節點在8:00—18:00時間段的位置坐標軌跡數據。然后,映射節點的軌跡數據到對應的目標子區,并對覆蓋子區進行統計。圖3是8:00—9:00的全部節點在目標區域的映射圖。

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

處理10 d的全部周期的移動軌跡數據,求得每個節點在每個周期每個子區的平均出現次數,即泊松密度λu,i,e,并根據式(3)和式(4)計算每個節點在每個周期的每個子區的概率。此處得到的概率即為移動節點的移動預測概率。

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

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

圖4 本文算法覆蓋情況

在圖4中,不同的顏色表示不同id的節點在各子區域內的覆蓋情況。同種顏色的子區域被相同節點覆蓋,但是如果有兩個或多個節點都覆蓋同一子區,就顯示為顏色深的節點顏色。

為了評價節點選擇算法的有效性,本文利用其他算法對移動節點進行選擇,并對比計算結果。

算法1移動節點部分周期參與感知選擇算法,被選擇節點只在部分周期參與感知。

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

圖5 算法1中id=287節點在8:00—9:00目標區域覆蓋情況

算法2隨機選擇算法,被選擇的節點在整個周期都進行感知。

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

圖6 算法2覆蓋情況

與圖4相同,圖6中不同的顏色表示不同id的節點在各子區域內的覆蓋情況。同種顏色的子區域被相同節點覆蓋,但是如果有兩個或多個節點都覆蓋同一子區,就顯示為顏色深的節點顏色。

為了使得實驗結果更可靠,本文繼續處理數據集中的數據,將剩余數據分為5 d的周期和13 d的周期對本文算法及對比算法進行了進一步的測試,得到的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種算法的平均覆蓋率 %

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

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

5 結束語

本文針對節點位置的關聯性問題,提出一種移動互聯網時空關注的移動感知節點選擇算法,并將其應用于碳檢測領域。該算法根據檢測節點的歷史移動軌跡,預測其未來在該周期內的移動軌跡,并依據移動檢測節點軌跡關聯有效性選擇最優的參與者集合。仿真結果證明,本文算法能使用較小數量的感知節點達到較大的覆蓋率。下一步,將本文算法應用于實際碳檢測領域,驗證其有效性。