節(jié)點-區(qū)域關(guān)聯(lián)度感知的區(qū)域數(shù)據(jù)分發(fā)算法

劉志鍇， 宋 暉， 潘達儒, 陳奮超

(華南師范大學(xué)物理與電信工程學(xué)院， 廣州 510006)

隨著大量具備短距離通信能力的智能移動終端的更新和普及，對通信多樣性和穩(wěn)定性的需求在不斷提升[1]. 在物聯(lián)網(wǎng)時代[2]，特定區(qū)域數(shù)據(jù)采集的實際應(yīng)用極為普遍，如局部空氣質(zhì)量檢測、圖書館區(qū)域熱度統(tǒng)計和野生動物遷徙追蹤等. 如今，越來越多的移動設(shè)備嵌入了功能類型豐富且具有計算、通訊能力的傳感器，對聲光速信息進行著全方位的感知[3]. 由這些智能終端作為節(jié)點構(gòu)成機會網(wǎng)絡(luò)[4]，可以有效地解決在頻繁的網(wǎng)絡(luò)分割狀態(tài)下的非實時連接的數(shù)據(jù)傳輸問題[5]，對區(qū)域數(shù)據(jù)的采集和轉(zhuǎn)發(fā)體現(xiàn)出更高的實時性和可靠性[6-7].

目前，關(guān)于機會網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)問題已有一些研究結(jié)果. 如:構(gòu)造了節(jié)點親密程度的評價模型，控制節(jié)點在相應(yīng)區(qū)域的數(shù)據(jù)轉(zhuǎn)發(fā)[8]；提出了一種考慮節(jié)點多社區(qū)屬性的機會網(wǎng)絡(luò)路由算法[9]；通過社區(qū)發(fā)現(xiàn)過程中的節(jié)點博弈收益，按重要度從大到小排列節(jié)點進行消息傳送[10]；計算節(jié)點間的余弦相似度，以選擇合適的鄰居節(jié)點進行消息傳遞[11]；將消息傳輸過程分為社區(qū)內(nèi)及社區(qū)間兩部分，采用“多拷貝+控制”的傳輸機制[12]；提出了將一個大范圍的傳輸分解成多個小范圍區(qū)域的機會分發(fā)過程的方案[13]. 然而，以上研究主要聚焦于借助社區(qū)(或區(qū)域)局部數(shù)據(jù)的轉(zhuǎn)發(fā)來尋求更佳的消息中繼節(jié)點優(yōu)化傳輸性能，本質(zhì)上都只是將消息傳送給目的節(jié)點，并沒有考慮區(qū)域數(shù)據(jù)共享的情況.

熊永平等[14]提出了一個將感知數(shù)據(jù)限制在有效區(qū)域內(nèi)擴散的傳播模型，但僅停留在理論階段，沒有具體的區(qū)域數(shù)據(jù)機會分發(fā)算法. 在時空敏感的地圖分區(qū)路由算法(SSMZ)[15]中，數(shù)據(jù)分發(fā)采用的是“同區(qū)即傳”的策略：對地圖范圍進行區(qū)域劃分，若判定處于相互通信范圍內(nèi)的任意2個節(jié)點在同一分區(qū)內(nèi)，則進行數(shù)據(jù)的轉(zhuǎn)發(fā). 在SSMZ算法中，數(shù)據(jù)采集轉(zhuǎn)發(fā)的判斷依據(jù)是節(jié)點的分區(qū)位置信息，沒有考慮該節(jié)點與其所在分區(qū)的關(guān)聯(lián)度.

本文使用區(qū)域關(guān)聯(lián)度提出了節(jié)點-區(qū)域關(guān)聯(lián)度感知的區(qū)域數(shù)據(jù)分發(fā)算法(Regional Data Acquisition Algorithm based on Relevance Perception，RDAA-RP):首先，通過將BM25模型[16]引入到社會屬性度量模型，將移動節(jié)點的區(qū)域關(guān)聯(lián)度映射到BM25模型的權(quán)值;然后，計算處理節(jié)點與區(qū)域間的關(guān)聯(lián)度權(quán)值并進行判斷;最后，將節(jié)點權(quán)值與設(shè)定的最低閾值作比較,若2個節(jié)點權(quán)值均高于設(shè)定的閾值則進行數(shù)據(jù)的交換分發(fā)，否則結(jié)束節(jié)點間的通信,從而實現(xiàn)區(qū)域內(nèi)數(shù)據(jù)依據(jù)關(guān)聯(lián)度的有效交換.

1 RDAA-RP算法

1.1 節(jié)點區(qū)域關(guān)聯(lián)度度量思想

在現(xiàn)實生活中，要求對特定時空的區(qū)域數(shù)據(jù)進行有效采集分發(fā)的應(yīng)用場景極為普遍，該場景的特點是區(qū)域類型各異、節(jié)點數(shù)量多且數(shù)據(jù)量大. 一般地，有效的采集要求絕大部分節(jié)點能夠共享(獲得)本區(qū)域的消息數(shù)據(jù)，并能夠減少重要性較低的區(qū)域數(shù)據(jù)的影響，屏蔽關(guān)聯(lián)度低或無關(guān)節(jié)點數(shù)據(jù)帶來的干擾. 為實現(xiàn)這一目的，算法必須準確量化節(jié)點與區(qū)域之間的關(guān)聯(lián)度.

在區(qū)域特定數(shù)據(jù)采集分發(fā)中，如何萃取節(jié)點的區(qū)域移動屬性并量化為可計算的關(guān)聯(lián)度是一個關(guān)鍵問題. 通過關(guān)聯(lián)度的量化，設(shè)置最低閾值為節(jié)點通信的限制條件，可以控制關(guān)聯(lián)程度不同的一定數(shù)量節(jié)點參與數(shù)據(jù)交換的過程，從而減少較低關(guān)聯(lián)性節(jié)點數(shù)據(jù)所帶來的影響.

節(jié)點對區(qū)域相關(guān)性的量化本質(zhì)上是一個匹配過程：首先，將所有節(jié)點循環(huán)與各個區(qū)域進行匹配比較；然后，借助某種數(shù)學(xué)模型得到匹配值. 在多個區(qū)域間匹配各個節(jié)點的過程，類似于在多份文本文檔中檢索相關(guān)詞的操作. 在區(qū)域數(shù)據(jù)采集中引入文本檢索模型，將節(jié)點當作關(guān)鍵詞，即可得到對多個可視為文本的區(qū)域的關(guān)聯(lián)度數(shù)值.

作為搜索引擎的核心組成部分，相關(guān)度對最終的算法性能起著關(guān)鍵性作用，不同的檢索模型得到的相關(guān)度有明顯差異. 其中，BM25模型所運用的算法是一種當前最流行使用的基于RSJ概率檢索模型的相關(guān)度計算算法，引入了查詢目標在整個查詢集合中的權(quán)值及查詢目標本身權(quán)值，并考慮了經(jīng)驗參數(shù). 本文將BM25模型應(yīng)用到區(qū)域數(shù)據(jù)采集中，可以有效地計算各節(jié)點對于不同區(qū)域的關(guān)聯(lián)度屬性，將移動節(jié)點的區(qū)域?qū)傩杂成涞紹M25模型中，從而得到節(jié)點i關(guān)于區(qū)域j的權(quán)值.

1.2 算法步驟

RDAA-RP算法的核心思想是：將移動節(jié)點與區(qū)域之間的關(guān)聯(lián)度映射到BM25模型[16]的權(quán)值上. 權(quán)值的計算綜合考慮了區(qū)域的相對重要性及節(jié)點在區(qū)域停留的時間片(即固定時間間隔)數(shù)量，有效地描述了節(jié)點所攜帶數(shù)據(jù)的必要性及重要性. 在算法的實現(xiàn)過程中，會以單個時間片的長度持續(xù)刷新節(jié)點的區(qū)域信息，并同步計算和更新所有節(jié)點與不同區(qū)域之間的對應(yīng)權(quán)值. 當2個相遇節(jié)點滿足一定條件，即位于同一區(qū)域且與該區(qū)域的關(guān)聯(lián)度均大于設(shè)定的閾值時，才能互相轉(zhuǎn)發(fā)數(shù)據(jù). 同時，該算法保留了地圖分區(qū)算法(SSMZ)[15]的邊緣檢測機制，對在區(qū)域邊緣徘徊移動的節(jié)點作出了有效的區(qū)域劃分判定.

1.2.1 記錄和更新節(jié)點的區(qū)域?qū)傩?對地圖進行區(qū)域劃分時可以采用不同的標準，如區(qū)域的功能定義、區(qū)域的距離范圍. 并且,劃分方式的不同將在一定程度上導(dǎo)致網(wǎng)絡(luò)性能的差異. 本文沿用SSMZ算法的劃分方式：

首先，在二維平面的層次上進行地圖分區(qū)，將地圖劃分為X2(X≥3N+)個面積相等的區(qū)域，并對各個區(qū)域按自左上至右下的順序依次賦予0～X2-1的編碼.

然后，以單個時間片的長度作為更新間隔(本算法將其設(shè)置為0.1 s)，持續(xù)刷新節(jié)點的地理位置，將從仿真器直接獲得的節(jié)點坐標轉(zhuǎn)換成對應(yīng)所在的區(qū)域值. 該過程具體為：將節(jié)點的橫縱向坐標分別與地圖區(qū)域的長寬進行對比，從而得到橫縱向所對應(yīng)區(qū)域的行列數(shù)，再以此行列數(shù)定位到對應(yīng)的區(qū)域編碼中. 例如，將一個長4 500 m、寬3 000 m的地圖劃分為9個區(qū)域，則坐標為(1 200，2 500)的節(jié)點對應(yīng)該地圖的第2行第0列，再根據(jù)區(qū)域自左上至右下的編碼規(guī)則，則可得到該節(jié)點的區(qū)域值為6.

以此編碼規(guī)則，可以建立一個全局的二維數(shù)組S，記錄移動節(jié)點對區(qū)域的訪問屬性. 數(shù)組每行對應(yīng)1個節(jié)點，每列對應(yīng)1個區(qū)域，則sij代表了第i個節(jié)點對第j個區(qū)域的訪問頻次. 在每次固定間隔的刷新后，所有節(jié)點對當前所屬區(qū)域的時間片數(shù)量加1并記錄保存在二維數(shù)組中，待下一過程計算權(quán)值時調(diào)用.

1.2.2 計算表征節(jié)點-區(qū)域關(guān)聯(lián)度的權(quán)值 計算權(quán)值時引入BM25模型[16]的思想，以節(jié)點在區(qū)域所停留的時間作為關(guān)聯(lián)度的基本度量單位. 設(shè)網(wǎng)絡(luò)中節(jié)點數(shù)量為n，地圖分成m個區(qū)域，定義每個節(jié)點的區(qū)域位置更新間隔(或稱為時間片長度)均為t，節(jié)點i(0≤i≤n)在區(qū)域j(0≤j≤m)停留的總時間為Tij，節(jié)點的時間片數(shù)量sij=Tij/t可以反映節(jié)點i對于區(qū)域j的訪問頻次,則n行m列的二維矩陣S表示所有節(jié)點對不同區(qū)域的訪問時間片數(shù)量. 顯然，時間片數(shù)量越大，節(jié)點對該區(qū)域的訪問頻次越高.

(1)

其中，k1和b均為經(jīng)驗參數(shù)，k1取值范圍通常為[1,2]，b用來調(diào)節(jié)節(jié)點i的時間片比例，取值范圍為[0,1].

首先，得到表示區(qū)域j在整個地圖所有區(qū)域中的相對重要性的區(qū)域平衡因子：

(2)

其中，n為節(jié)點總數(shù)；dj代表所有節(jié)點中訪問區(qū)域j的節(jié)點數(shù)，即區(qū)域j的節(jié)點密度.

然后，調(diào)用二維數(shù)組S所記錄的節(jié)點訪問時間片數(shù)值，計算得到節(jié)點平衡因子

(3)

最后，得到最終的權(quán)值，以反映各節(jié)點對不同區(qū)域的關(guān)聯(lián)度：

wij=Fij*Rj，

(4)

其中，權(quán)值wij代表移動節(jié)點i對于區(qū)域j的關(guān)聯(lián)度. 因為該區(qū)域j的節(jié)點密度dj較低，所以節(jié)點i對區(qū)域j的訪問時間片數(shù)量sij越大，計算得到的權(quán)值就越大，對應(yīng)的關(guān)聯(lián)度也越高；反之則關(guān)聯(lián)度越低.

1.2.3 數(shù)據(jù)分發(fā) 當網(wǎng)絡(luò)中任意2個節(jié)點進入相互的通信范圍內(nèi)時，首先調(diào)用2個節(jié)點對應(yīng)的區(qū)域值進行比較：若2個區(qū)域值相同，則說明2個節(jié)點處于同一區(qū)域，進入權(quán)值判斷環(huán)節(jié)；若2個區(qū)域值不同，則進入判斷是否修改所屬區(qū)域值的環(huán)節(jié).

在權(quán)值判斷環(huán)節(jié)，用2個節(jié)點對應(yīng)的區(qū)域值分別與設(shè)定的最低閾值作比較. 若2個節(jié)點權(quán)值均高于設(shè)定的閾值，則進行數(shù)據(jù)的交換分發(fā)，否則結(jié)束節(jié)點間的通信.

若進入通信范圍的2個節(jié)點被判斷為不屬于同一區(qū)域，則分別將對方節(jié)點當前的所屬區(qū)域分區(qū)屬性更新為自己的歷史區(qū)域分區(qū)屬性，并記錄在數(shù)組中. 當數(shù)組中循環(huán)存儲的3個歷史值均為同一值時，便將該值強制賦給該節(jié)點的當前所屬區(qū)域，表示該節(jié)點已經(jīng)進入最近遇到的節(jié)點所在的區(qū)域. 若數(shù)組中存儲的歷史值不完全相同，則說明該節(jié)點未進入新的區(qū)域，不修改自身所屬區(qū)域分區(qū)屬性，并因通信節(jié)點的所屬區(qū)域不同而結(jié)束通信.

節(jié)點間的通信自動結(jié)束發(fā)生在相遇節(jié)點完成消息交換分發(fā)后，或是在權(quán)值判斷不滿足限制條件后，或是在邊緣檢測中節(jié)點不修改所屬區(qū)域后.

具體的算法流程見圖1.

圖1 基于BM25模型的區(qū)域數(shù)據(jù)分發(fā)算法流程圖Figure 1 The flow chart of regional data distribution algorithm based on the BM25 model

2 仿真結(jié)果與討論

在不同經(jīng)驗參數(shù)、不同節(jié)點緩存大小和不同傳輸速度的情況下, 對比RDAA-RP算法、SSMZ算法和Epidemic算法[15]的性能. 同時，在保持環(huán)境參數(shù)設(shè)置相同的基礎(chǔ)上,對比RDAA-RP算法在不同的轉(zhuǎn)發(fā)閾值下的性能.

2.1 仿真場景與性能指標

采用機會網(wǎng)絡(luò)仿真平臺(ONE仿真器)對算法性能進行實驗仿真. 仿真實驗場景采用ONE自帶的典型城市地圖，地圖面積為4 500 m*3 400 m，場景更新間隔為0.1 s，仿真時間為43 200 s(即24 h). 每25～35 s產(chǎn)生1份消息，生存周期TTL=300 min，數(shù)據(jù)大小固定為100 kB. 節(jié)點類型包括了行人節(jié)點、汽車節(jié)點以及帶有高速接口的軌道列車節(jié)點，行人及汽車節(jié)點的移動模型為Shortest Path Map Based Movement(SPMBM)，軌道列車節(jié)點的移動模型為Map Route Movement(MPM)，節(jié)點參數(shù)設(shè)置如表1所示. 所有節(jié)點中，只有軌道列車節(jié)點包括1個藍牙接口與1個高速接口，其余節(jié)點均為藍牙接口. 藍牙接口的傳輸速度為250 KB/s，傳輸范圍為10 m;高速接口的傳輸速度為10 MB/s，傳輸范圍為1 000 m.

表1 仿真場景設(shè)置Table 1 The scene setting for the simulation

為了便于比較，本文采用網(wǎng)絡(luò)負荷量、平均緩存時間與SSMZ中定義的2個性能參數(shù)(消息采集率[15]和采集開銷比率[15])來描述區(qū)域數(shù)據(jù)采集的算法性能. 網(wǎng)絡(luò)負荷量和平均緩存時間的定義如下：

(1)網(wǎng)絡(luò)負荷量. 該指標表征的是單位時間內(nèi)，網(wǎng)絡(luò)上所需負荷的數(shù)據(jù)量大小:

(5)

在一定時間內(nèi)，消息數(shù)量越多，數(shù)據(jù)空間越大，則網(wǎng)絡(luò)所需承擔的流量越大，由此導(dǎo)致網(wǎng)絡(luò)擁塞的可能性也越高. 本算法對權(quán)值作出轉(zhuǎn)發(fā)的閾值限定，可以在一定程度上緩解網(wǎng)絡(luò)壓力.

(2)平均緩存時間. 該指標表征了消息在節(jié)點中的平均留存時間，在本文中節(jié)點緩存及消息數(shù)據(jù)大小均固定的條件下，平均緩存時間反映了節(jié)點攜帶消息的能力:

平均緩存時間=

(6)

平均緩存時間越大，消息留存越久，節(jié)點間完成數(shù)據(jù)互傳的概率就越高，區(qū)域數(shù)據(jù)采集的性能則更優(yōu).

2.2 經(jīng)驗參數(shù)確定

由于RDAA-RP算法引入了BM25模型作為節(jié)點區(qū)域關(guān)聯(lián)度的度量模型，其中包括了2個調(diào)節(jié)平衡的經(jīng)驗參數(shù)(k1和b). 不同經(jīng)驗參數(shù)的取值作用到節(jié)點平衡因子，將使最終得到的權(quán)值wij存在差異，一定程度上影響算法的性能指標. 因此，在對算法性能進行仿真測試前，需要先確定經(jīng)驗參數(shù)的值.

當k1[1,2]，b[0,1]時，選取k1、b的若干值進行組合，在所有參數(shù)設(shè)置保持相同的條件下，獲取大量數(shù)據(jù)并取平均值，觀察不同的經(jīng)驗參數(shù)取值對消息傳輸率及采集開銷比率的影響. 由圖2及圖3可知:當k1=1.75，b=0.75時，消息采集率最高，采集開銷比率則相應(yīng)地可以獲得最低值，BM25模型對區(qū)域數(shù)據(jù)分發(fā)算法具有最佳性能效果. 因此,本文仿真實驗中的經(jīng)驗參數(shù)采用k1=1.75，b=0.75.

圖2 不同經(jīng)驗參數(shù)對消息采集率的影響Figure 2 The effect of different empirical parameters on me-ssage collection ratio

圖3 不同經(jīng)驗參數(shù)對采集開銷比率的影響Figure 3 The effect of different empirical parameters on the acquisition overhead ratio

2.3 RDAA-RP與Epidemic、SSMZ算法的性能比較

2.3.1 不同緩存條件下算法性能對比 不同的節(jié)點緩存大小設(shè)置將導(dǎo)致算法性能的差異. 在保持其他環(huán)境參數(shù)設(shè)置均相同的基礎(chǔ)上，固定閾值為3，修改不同的節(jié)點緩存值進行仿真，得到各緩存情況下多種區(qū)域劃分方式的平均結(jié)果，然后對比緩存大小對不同算法性能的影響. 其中，區(qū)域數(shù)目按照自然數(shù)X的平方進行劃分，分別劃分為9、16、25、36分區(qū).

參照表1的仿真環(huán)境設(shè)置(除了固定緩存)，得到Epidemic、SSMZ、RDAA-RP算法的消息采集率及采集開銷比率(圖4、圖5).

圖4 不同緩存下的3種算法的消息采集率Figure 4 The message collection rates of three algorithms under different caches

圖5 不同緩存下的3種算法的采集開銷比率Figure 5 The acquisition overhead ratios of three algorithms under different caches

由圖4可知：當節(jié)點緩存大小低于50 MB時，3種算法的消息采集率隨著緩存的增大而提升，在緩存大小增加到50 MB之后趨于平穩(wěn)，且RDAA-RP算法的消息采集率與SSMZ、Epidemic算法基本相當. 由圖5可知：(1)3種算法的采集開銷比率隨著緩存的增大而降低，在緩存大小增加到50 MB之后也同樣趨于平穩(wěn). (2)RDAA-RP算法的采集開銷比率近似于SSMZ算法與Epidemic算法. 這是由于節(jié)點緩存的增大，導(dǎo)致因緩存溢出而丟棄的數(shù)據(jù)包數(shù)量減少，成功交換的數(shù)據(jù)包數(shù)量增加，從而提升消息的采集率. 當消息大小固定，節(jié)點的緩存空間越小，其所能攜帶的數(shù)據(jù)包數(shù)量就越少，對“存儲-攜帶”過程的限制程度就越高. 當緩存小于50 MB時，隨著緩存的增大，節(jié)點攜帶消息在數(shù)量方面的能力增強，整個網(wǎng)絡(luò)的交付能力提升，因而消息采集率隨之增大；綜上所述，適當?shù)卦龃蠊?jié)點緩存能夠有效提升消息的采集率，但當超過50 MB之后，緩存的增大已經(jīng)不能帶來更好的作用.

參照表1的仿真環(huán)境設(shè)置(除了固定緩存)，得到Epidemic、SSMZ、RDAA-RP算法的網(wǎng)絡(luò)負荷量和平均緩存時間(圖6、圖7).

圖6 不同緩存下的網(wǎng)絡(luò)負荷量差異Figure 6 The network load differences under different caches

圖7 不同緩存下的平均緩存時間差異Figure 7 The average cache time differences under different caches

由圖6可知：(1)隨著節(jié)點緩存的增大， 3種算法的網(wǎng)絡(luò)負荷量與緩存大小呈正相關(guān)關(guān)系；而當緩存超過50 MB并增大到一定程度時，網(wǎng)絡(luò)負荷量趨于平穩(wěn). (2)RDAA算法的網(wǎng)絡(luò)負荷量始終低于SSMZ算法和Epidemic算法，體現(xiàn)了RDAA算法的優(yōu)越性. RDAA-RP算法的曲線變化原因為：(1)在一定程度內(nèi)，節(jié)點緩存增大，將增強節(jié)點在攜帶數(shù)據(jù)包數(shù)量方面的能力，從而提升單位時間內(nèi)網(wǎng)絡(luò)的交付能力. (2)數(shù)據(jù)交換頻次總數(shù)越大，導(dǎo)致網(wǎng)絡(luò)的負荷量越高. 而在超過了一定值后，由于節(jié)點緩存空間充足，攜帶了網(wǎng)絡(luò)中一定數(shù)量的數(shù)據(jù)包，則對未擁有的消息的交換要求降低，單位時間內(nèi)數(shù)據(jù)流總量趨于不變，網(wǎng)絡(luò)所負荷的比特數(shù)也會持續(xù)不變. 因此，RDAA-RP算法在涉及節(jié)點緩存時，需要考慮參數(shù)設(shè)置對于網(wǎng)絡(luò)壓力的影響，在消息采集率、網(wǎng)絡(luò)負荷量和平均緩存時間等性能指標綜合下選擇符合實際應(yīng)用場景的緩存參數(shù)設(shè)置.

由圖7可知：(1)在緩存小于50 MB時，隨著節(jié)點緩存的增大，3種算法的消息的平均緩存時間均明顯提高；而當緩存增大至50 MB時，平均緩存時間均趨于平穩(wěn)值. 這是因為在固定消息大小的前提下，消息的平均緩存時間與節(jié)點緩存大小呈正相關(guān)性：緩存越大，節(jié)點所能攜帶的消息數(shù)量越多，舊數(shù)據(jù)包被更新替換的頻率變低，因此消息的平均緩存時間更長. 而當緩存增大到一定程度時，充足的空間保證了節(jié)點攜帶了網(wǎng)絡(luò)中絕大部分消息，數(shù)據(jù)交換更新頻率變得極低，消息的平均緩存時間也趨向于一個平穩(wěn)值. (2)RDAA-RP算法的平均緩存時間始終略低于其他2種算法，體現(xiàn)了RDAA-RP算法的優(yōu)越性.

2.3.2 不同傳輸速率條件下算法性能對比 在無線網(wǎng)絡(luò)中運用不同的傳輸技術(shù)將得到不同的消息傳輸速率，從而體現(xiàn)算法的性能差異. 在保持其他環(huán)境參數(shù)設(shè)置均相同的基礎(chǔ)上，固定閾值為3，節(jié)點緩存大小設(shè)置為60 MB，選擇不同的節(jié)點傳輸速率進行仿真，得到各傳輸速率情況下多種區(qū)域劃分方式得出的平均結(jié)果，然后對比傳輸速率大小設(shè)置對RDAA-RP算法性能的作用效果. 其中，區(qū)域數(shù)目按照自然數(shù)X的平方進行劃分，本文采用了9、16、25、36分區(qū). 設(shè)置傳輸速率為：采用ZigBee通信協(xié)議的250 KB/s，采用3G通信協(xié)議的350 KB/s與450 KB/s，采用藍牙2.0或3.0/4.0通信的1 MB/s與3 MB/s，以及采用4G通信協(xié)議的6.25 MB/s與12.5 MB/s. 其中3G通信速度為300～1 024 KB/s，4G通信速度為10～100 MB/s.

參照表1的仿真環(huán)境設(shè)置(除了固定傳輸速率)，得到Epidemic、SSMZ、RDAA-RP算法的消息采集率及采集開銷比率(圖8、圖9).

圖8 不同傳輸速率下的消息采集率Figure 8 The message collection rates at different transmission rates

圖9 不同傳輸速率下的采集開銷比率Figure 9 The acquisition overhead ratios at transmission rates

由圖8可知：(1)當傳輸速率低于1 000 KB/s時，3種算法的消息采集率隨著傳輸速率的增大而提升，在傳輸速率增加到1 000 KB/s之后趨于平穩(wěn)，且RDAA-RP算法的消息采集率與SSMZ、Epidemic算法基本相當. (2)消息采集率并不是隨著每一個單獨的傳輸速率的改變而改變，而是以分段區(qū)間的形式進行階段式變化，同屬一個區(qū)間的傳輸速率改變并不會帶來影響. 比如，圖中350 KB/s和450 KB/s是同一個變化區(qū)間，1 000 KB/s之后屬于另一個變化區(qū)間. 而由圖9可以看出采集開銷比率的變化趨勢與圖8的消息采集率走向完全相反.

產(chǎn)生以上差異的主要原因為：(1)傳輸速率的增大，使得消息數(shù)據(jù)以更短的時長、更高的效率完成了轉(zhuǎn)發(fā). 在小于1 000 KB/s之前，隨著速率的增大，消息采集率不斷提高，說明在理論上，可以盡可能地提高傳輸速率以得到更佳的RDAA-RP算法采集率. 但是在1 000 KB/s之后，消息采集率已經(jīng)高達99%，區(qū)域內(nèi)部節(jié)點的數(shù)據(jù)采集已達到較為飽和的程度，這時繼續(xù)提高傳輸速率已經(jīng)無法對消息采集率產(chǎn)生有效的優(yōu)化作用. (2)RDAA-RP算法引入了節(jié)點和區(qū)域間的關(guān)聯(lián)度，并設(shè)置了最低轉(zhuǎn)發(fā)閾值，以此控制了參與數(shù)據(jù)采集過程的節(jié)點數(shù)量. 在仿真過程中采用了閾值的中間值3, 將相當一部分的節(jié)點排除在消息交換的范圍之外. 網(wǎng)絡(luò)中的節(jié)點總數(shù)得到了限制，傳輸速率的改變所帶來的影響將減小，所以消息采集率和采集開銷比率在區(qū)間范圍內(nèi)產(chǎn)生階段式的變化.

因此，在實際中使用RDAA-RP算法進行區(qū)域數(shù)據(jù)采集時，為了保證較好的算法性能，應(yīng)該在成本允許的條件下盡可能選擇更高的傳輸速率.

參照表1的仿真環(huán)境設(shè)置(除了固定傳輸速率)，得到Epidemic、SSMZ、RDAA-RP算法的網(wǎng)絡(luò)負荷量和平均緩存時間(圖10、圖11).

圖10 不同傳輸速率下的網(wǎng)絡(luò)負荷量差異Figure 10 The network load differences at different transmission rates

圖11 不同傳輸速率下的平均緩存時間差異Figure 11 The average cache time differences at different transmission rates

由圖10可以發(fā)現(xiàn)：(1)RDAA-RP算法的網(wǎng)絡(luò)負荷量與傳輸速率正相關(guān)，但不隨著速率的增長而單調(diào)增長，而是階段式增長. 比如，圖中350～450 KB/s是一個變化階段，1 000 KB/s之后是另一個變化階段. (2)RDAA-RP算法的網(wǎng)絡(luò)負荷量遠低于SSMZ算法和Epidemic算法，體現(xiàn)了該算法的優(yōu)越性. 這是因為在消息數(shù)據(jù)包大小及節(jié)點緩存固定的前提下，傳輸速率越快，則完成一次消息交換的時長越短，單位時間內(nèi)網(wǎng)絡(luò)所需承載的消息傳輸數(shù)據(jù)總流量就越大，表現(xiàn)為網(wǎng)絡(luò)負荷量的增大. 因此，在具體使用場合中，傳輸速率的選擇也一定程度上受到了網(wǎng)絡(luò)負荷量的限制，在選擇RDAA-RP算法的消息傳輸速率時，需要考慮所在網(wǎng)絡(luò)的最大負荷能力，避免發(fā)生網(wǎng)絡(luò)擁堵，影響區(qū)域數(shù)據(jù)采集的過程.

由圖11可以看出RDAA-RP算法的優(yōu)越性：(1)RDAA-RP算法的平均緩存時間隨著傳輸速率的增大呈現(xiàn)總體減小的趨勢，且同樣地是隨著傳輸速率的區(qū)間范圍變化而改變，而非跟著傳輸速率單點變動. 這是因為在固定消息大小及緩存空間的前提下，消息的平均緩存時間與傳輸速率負相關(guān). 傳輸速率越大，節(jié)點以更高效率完成了數(shù)據(jù)包轉(zhuǎn)發(fā)，節(jié)點內(nèi)緩存的內(nèi)容更新速度也變快，單個消息的停留時間變短，故平均緩存時間變小. (2)RDAA-RP算法的平均緩存時間始終略低于其他2種算法.

2.4 不同閾值限制下RDAA-RP算法的性能測試

本節(jié)在保持環(huán)境參數(shù)設(shè)置相同的基礎(chǔ)上，修改不同的閾值進行仿真，得到各閾值限制下多種區(qū)域劃分方式產(chǎn)生的平均結(jié)果，然后對比閾值大小的設(shè)置對RDAA-RP算法性能的作用效果. 其中，區(qū)域數(shù)目按照自然數(shù)X的平方進行劃分，本文采用了9、16、25、36分區(qū). 消息轉(zhuǎn)發(fā)的關(guān)聯(lián)度閾值范圍為[0,5.5]，本文設(shè)置閾值間隔為0.5.

參照表1的環(huán)境設(shè)置，得到消息采集率對比結(jié)果(圖12). 由圖可知：隨著閾值設(shè)置的增大，RDAA-RP算法的消息采集率呈現(xiàn)先減小再增大，然后繼續(xù)減小的變化趨勢. 當閾值小于4時，消息采集率與權(quán)值之間表現(xiàn)為負相關(guān)性；閾值在4～4.5時，采集率隨閾值增大而明顯提升，甚至達到了最高值，優(yōu)于圖4所示的Epidemic算法的結(jié)果；而當閾值在4.5之后，消息采集率減小.

圖12 不同閾值選擇的消息采集率Figure 12 The message collection rates for different threshold selections

由圖13可知：隨著閾值設(shè)置的增大，RDAA-RP算法的采集開銷比率呈現(xiàn)先增大再減小，然后繼續(xù)增大的變化趨勢. 當閾值小于4時，采集開銷比率與權(quán)值之間表現(xiàn)為正相關(guān)性；閾值在4～4.5時，采集開銷比率隨閾值增大而明顯降低，甚至達到了最低值；當閾值大于4.5后，采集開銷比率增大.

圖13 不同閾值選擇的采集開銷比率Figure 13 The collection overhead ratios for different threshold selections

產(chǎn)生以上差異的主要原因為：(1)當閾值低于4時，所有類型的節(jié)點(行人、汽車、軌道列車)均參與數(shù)據(jù)交換，而影響消息采集率大小的主要因素是節(jié)點數(shù)量. 閾值越高，則滿足限制條件的節(jié)點越少，單位時間內(nèi)網(wǎng)絡(luò)上所進行轉(zhuǎn)發(fā)的數(shù)據(jù)總量變少，表現(xiàn)為消息采集率的降低. (2)閾值在4～4.5時，節(jié)點的主要類型比例發(fā)生變化，在多個區(qū)域間游走移動的節(jié)點被摒棄，具備高關(guān)聯(lián)度、高緩存、高傳輸速率以及高通信范圍特質(zhì)的列車節(jié)點在符合通信要求的節(jié)點中占了更多的比例. 在一定程度上，緩存空間充足、傳輸速率快能夠保證消息成功轉(zhuǎn)發(fā)的概率更高，通信質(zhì)量更優(yōu). 因此，在閾值設(shè)置的這一小范圍區(qū)間內(nèi)，消息采集率呈現(xiàn)上升的趨勢，且取得最高值. (3)當閾值增大到4.5之后，消息采集率與權(quán)值閾值呈現(xiàn)負相關(guān)關(guān)系. 此現(xiàn)象的原因與閾值低于4時相同，是節(jié)點數(shù)量變化后產(chǎn)生的結(jié)果. 此時的閾值較高，滿足篩選條件的節(jié)點類型基本固定在少部分節(jié)點中間，消息中止或丟棄對最終的采集率削減的影響程度會更高.

通過上述分析可以看出，在不同采集關(guān)聯(lián)度要求的情況下， 應(yīng)該對閾值設(shè)置不同的參考值：需要采集區(qū)域中關(guān)聯(lián)度極高的節(jié)點數(shù)據(jù)時，閾值可設(shè)置為4.5；當關(guān)聯(lián)程度要求一般時，可以設(shè)置為2；對區(qū)域節(jié)點相關(guān)性要求不高的數(shù)據(jù)采集場景，閾值可設(shè)置為0.5. 在實際場景中采用RDAA-RP算法時，需要對區(qū)域節(jié)點類型和關(guān)聯(lián)度重要性進行事先調(diào)查與計劃，再綜合確定相關(guān)參數(shù)的設(shè)定，選擇恰當?shù)南⑥D(zhuǎn)發(fā)限定閾值.

參照仿真環(huán)境設(shè)置，得到RDAA-RP算法的網(wǎng)絡(luò)負荷量和平均緩存時間(圖14、圖15).

圖14 不同閾值選擇的網(wǎng)絡(luò)負荷量差異Figure 14 The network load differences for different threshold selections

圖15 不同閾值選擇的平均緩存時間差異Figure 15 The average cache time differences for different threshold selections

由圖14可知:(1)隨著權(quán)值閾值設(shè)定的增大，網(wǎng)絡(luò)負荷量逐漸降低，且在較高值和較低值間存在明顯差距. (2)由于權(quán)值的引入，所有節(jié)點對不同區(qū)域的關(guān)聯(lián)度有了度量標準，消息分發(fā)最低閾值的設(shè)置，將部分節(jié)點摒棄在區(qū)域數(shù)據(jù)采集的過程之外. 權(quán)值閾值越高，則要求關(guān)聯(lián)度越高，導(dǎo)致參與數(shù)據(jù)分發(fā)的節(jié)點數(shù)目越少. 節(jié)點緩存空間以及消息數(shù)據(jù)大小固定的前提下，節(jié)點數(shù)量將直接影響網(wǎng)絡(luò)負荷量的大小. 節(jié)點越少，則單位時間內(nèi)網(wǎng)絡(luò)上的數(shù)據(jù)流量越低，網(wǎng)絡(luò)所負荷的比特數(shù)也越少. 所以，RDAA-RP算法在選擇閾值時，應(yīng)選擇更高的參數(shù)，以使網(wǎng)絡(luò)的壓力相對緩和. 而當采集區(qū)域?qū)?jié)點關(guān)聯(lián)度要求不高時，需避免選擇了過低參數(shù)而使得網(wǎng)絡(luò)負荷量偏大、發(fā)生網(wǎng)絡(luò)擁堵的風(fēng)險系數(shù)過高. 實際應(yīng)用中，不同網(wǎng)絡(luò)的帶寬、負載能力和信噪比等多種因素會使網(wǎng)絡(luò)的最大負荷量有所不同，所以對閾值的設(shè)置也應(yīng)有所差異.

由圖15可知：權(quán)值閾值越大，消息的平均緩存時間也越大，兩者呈正相關(guān)性. 這是因為閾值的增大，使得參與消息轉(zhuǎn)發(fā)的節(jié)點數(shù)變少，節(jié)點所攜帶消息的更新丟棄頻率變低，故數(shù)據(jù)包在節(jié)點中的留存時間得到延長，即平均緩存時間增大.

綜上所述，作為一個為區(qū)域數(shù)據(jù)采集應(yīng)用場景服務(wù)的數(shù)據(jù)轉(zhuǎn)發(fā)策略，RDAA-RP策略可以在消息采集率性能與Epidemic、SSMZ算法基本相當?shù)那闆r下，較大程度地優(yōu)化網(wǎng)絡(luò)負荷量及消息平均緩存時間這2個性能指標， 提供可靠的區(qū)域數(shù)據(jù)共享分發(fā)功能，并能通過不同關(guān)聯(lián)度閾值設(shè)置滿足節(jié)點不同程度相關(guān)性的要求.

3 結(jié)語

本文圍繞區(qū)域數(shù)據(jù)采集分發(fā)的場景，并考慮節(jié)點所攜帶消息的相關(guān)性，引入BM25模型作為節(jié)點區(qū)域關(guān)聯(lián)度的度量模型，設(shè)計了基于該模型的區(qū)域數(shù)據(jù)分發(fā)算法(RDAA-RP). 該算法在轉(zhuǎn)發(fā)環(huán)節(jié)添加了區(qū)域?qū)傩约肮?jié)點關(guān)聯(lián)度最低閾值作為限制條件，能夠?qū)崿F(xiàn)區(qū)域數(shù)據(jù)的采集和共享，同時具備了節(jié)點相關(guān)性篩選控制功能. 仿真結(jié)果表明：與Epidemic、SSMZ算法相比，在消息采集率基本相當?shù)那闆r下，RDAA-RP算法能夠較大程度地優(yōu)化網(wǎng)絡(luò)負荷量及消息平均緩存時間這2個性能指標. 此外，該算法對不同的轉(zhuǎn)發(fā)關(guān)聯(lián)度閾值設(shè)置體現(xiàn)了性能上的差異，能夠滿足選擇控制節(jié)點不同程度相關(guān)性的要求.