陳啟航，馬大瑋，張世偉，肖玲娜，李成俊

（中國人民解放軍陸軍工程大學(xué)通信士官學(xué)校，重慶 400035）

0 引言

機(jī)會網(wǎng)絡(luò)是一種基于“存儲—攜帶—轉(zhuǎn)發(fā)”機(jī)制，通過中繼節(jié)點攜帶消息副本，等待與消息目的節(jié)點建立連接的機(jī)會，實現(xiàn)消息可靠傳輸?shù)囊环N自組織網(wǎng)絡(luò)[1]。相較于移動自組網(wǎng)（Mobile Ad hoc Network，MANET）[2]，機(jī)會路由不受限于在節(jié)點間時刻維護(hù)一條穩(wěn)定通信鏈路的條件，因此作為野生動物追蹤[3]、災(zāi)害后通信[4]、戰(zhàn)場通信[5]等挑戰(zhàn)性環(huán)境中的可靠通信方案被廣泛研究。

路由策略問題一直是機(jī)會網(wǎng)絡(luò)的研究熱點，較為經(jīng)典的路由策略有傳染?。‥pidemic）[6]、噴射等待（Spray and Wait，SAW）[7]等。上述方案通過多消息副本泛洪的方式來增加目的節(jié)點接收到消息的概率，但如何實現(xiàn)消息副本的有效分配，仍然是機(jī)會網(wǎng)絡(luò)領(lǐng)域中的一項研究熱點問題。

本文提出了一種基于地理位置信息的機(jī)會網(wǎng)絡(luò)消息副本分配方案（Geographic Location Message Copy Allocation，GLMCA）。本文的貢獻(xiàn)有：

（1）GLMCA 利用有限的地理位置信息，根據(jù)消息副本分配算法，使有限的消息副本在網(wǎng)絡(luò)中快速擴(kuò)散，并能夠有效減少消息轉(zhuǎn)發(fā)的盲目性；

（2）提出在當(dāng)節(jié)點僅能夠獲取自身路由信息時，通過周期性與事件性兩種路由維護(hù)模式與鄰居節(jié)點建立位置信息表；

（3）將GLMCA 與Epidemic 和SAW 協(xié)議進(jìn)行比較，GLMCA 算法在短時間內(nèi)（5 min 內(nèi)）具有較高的投遞率，在節(jié)點密度稀疏的情況下能發(fā)揮較好的性能。

在第1 節(jié)中，將介紹前期進(jìn)行的相關(guān)工作；第2 節(jié)將對GLMCA 的算法流程及細(xì)節(jié)設(shè)計進(jìn)行描述；第3 節(jié)通過MATLAB 仿真平臺進(jìn)行仿真分析；第4節(jié)進(jìn)行總結(jié)。

1 相關(guān)工作

在機(jī)會路由中，消息的源節(jié)點通過生成大量的消息副本交與中繼節(jié)點攜帶，以達(dá)到提升消息可靠性的目的，如Epidemic 策略中，消息源節(jié)點將消息副本交付給每一個能夠接觸到的中繼節(jié)點。這種消息副本的分配方式在理論上來說，若不考慮緩存因素，能夠在節(jié)點密度稀疏的場景下實現(xiàn)極高的消息交付率；但是在現(xiàn)實應(yīng)用場景中，這種理想化的節(jié)點緩存環(huán)境難以實現(xiàn)[8]。為了避免無效消息副本盲目泛洪造成的通信資源浪費，學(xué)者提出了限制消息副本生成數(shù)量的消息分配策略，其中，較為經(jīng)典的就是SAW 策略。在SAW 策略中，消息副本的分配分為噴射（Spray）和等待（Wait）兩個階段。在Spray 階段中，消息源節(jié)點間將生成L份（L＞1）消息副本，并將消息副本分配給其接觸到的其他節(jié)點；當(dāng)在Spray 階段中源節(jié)點未能將消息傳遞給目的節(jié)點，且所有接收到消息副本的中繼節(jié)點和源節(jié)點內(nèi)僅有一個消息副本時，進(jìn)入Wait 階段，此時含有消息副本的節(jié)點將不做任何操作，等待與目的節(jié)點接觸的機(jī)會進(jìn)行消息傳輸[9]。

隨著衛(wèi)星導(dǎo)航定位系統(tǒng)民用的廣泛應(yīng)用，用戶能夠通過手持終端（智能手機(jī)、智能手表、平板電腦等）或車載終端（車載導(dǎo)航系統(tǒng)）獲取自身甚至其他節(jié)點的位置信息，在此基礎(chǔ)上，基于地理位置信息輔助的移動自組網(wǎng)路由策略相繼被提出，如位置輔助路由（Location Aided Routing，LAR）[10]、貪婪周邊無狀態(tài)路由（Greedy Perimeter Stateless Routing，GPSR）[11]等。許多學(xué)者嘗試在機(jī)會網(wǎng)絡(luò)的消息副本分配策略上引入地理位置信息，實現(xiàn)消息副本能夠盡可能分配到更有機(jī)會與目的節(jié)點接觸的高效節(jié)點，提升消息交付的成功率。在文獻(xiàn)[12]中，作者將GPSR 策略與機(jī)會路由相融合，當(dāng)消息在傳輸過程中遭遇路由空洞[13]時，作者認(rèn)為按傳統(tǒng)GPSR 通過“右手法則”重新選擇的中繼節(jié)點并不是最優(yōu)的中繼節(jié)點；因此在面臨路由空洞時，距離目的節(jié)點直線距離最近的節(jié)點將保存消息等待與目的節(jié)點建立最短連接的機(jī)會。相較于傳統(tǒng)GPSR 和機(jī)會路由策略，上述方案的提出雖然進(jìn)行了一定程度的優(yōu)化，但在挑戰(zhàn)性環(huán)境下，消息源節(jié)點極有可能無法獲得目的節(jié)點的地理位置信息或出現(xiàn)目的節(jié)點地理位置信息過期失效的情況，這種單消息副本轉(zhuǎn)發(fā)的模式的性能會受到極大的限制。文獻(xiàn)[14]提出了一種基于地理位置信息輔助的多副本SAW 策略，該策略在SAW 的Wait 階段中加入消息轉(zhuǎn)發(fā)機(jī)制，處于Wait 階段的中繼節(jié)點將與接觸到的其他節(jié)點交換比較位置信息，中繼節(jié)點將消息副本轉(zhuǎn)發(fā)給不攜帶副本的高效節(jié)點，形成新的中繼節(jié)點。這種副本轉(zhuǎn)發(fā)策略使得消息副本不斷向高效轉(zhuǎn)發(fā)節(jié)點靠攏，避免了副本盲目分配至孤僻節(jié)點的問題，但也給高效節(jié)點增加了更多的消息負(fù)載。在文獻(xiàn)[15]中，作者在源節(jié)點副本分配策略上參考I.CEpidemic[16]策略中根據(jù)鄰居節(jié)點選擇最大張角的知識，通過位置信息選擇張角最大的兩個鄰居節(jié)點作為分配副本的中繼節(jié)點。

基于上述研究，本文提出了一種基于地理位置信息的機(jī)會網(wǎng)絡(luò)消息副本分配策略（GLMCA）。該策略的特點有：

（1）鄰居節(jié)點間互相交換自身位置信息，源節(jié)點產(chǎn)生的消息副本能夠按最短距離擴(kuò)散至指定位置；

（2）限制源節(jié)點生成消息副本的數(shù)量；

（3）根據(jù)節(jié)點位置信息，按劃分角度方向分配副本。

2 GLMCA 模型設(shè)計

假設(shè)在間歇性連接網(wǎng)絡(luò)[17]中各節(jié)點能夠獲取到自身位置信息，當(dāng)不考慮節(jié)點能量消耗及緩存資源時，GLMCA 策略將進(jìn)行下述操作。

GLMCA 策略分為3 個階段：鄰接節(jié)點信息維護(hù)階段、消息副本分配階段和虛擬源節(jié)點消息轉(zhuǎn)發(fā)階段。各階段間關(guān)系如圖1 所示。

圖1 GLMCA 階段關(guān)系

2.1 鄰接節(jié)點信息維護(hù)階段

在鄰接節(jié)點信息維護(hù)階段中，網(wǎng)絡(luò)中各節(jié)點與鄰居節(jié)點交換控制信息記為控制消息（Control Message，CM），并根據(jù)接收到的控制信息在節(jié)點自身建立并維護(hù)一個鄰接節(jié)點位置信息表。

如表1 所示，鄰接節(jié)點位置信息表內(nèi)包含有鄰接節(jié)點的標(biāo)識ID、X和Y坐標(biāo)以及一個位置信息剩余保留時間記為TTL_g。當(dāng)表內(nèi)位置信息存儲的時間到達(dá)TTL_g時，該條位置信息將被丟棄以減少冗余信息。

表1 鄰接節(jié)點位置信息

鄰接節(jié)點信息維護(hù)階段的觸發(fā)方式分為周期性觸發(fā)和事件性觸發(fā)兩種模式，在不同觸發(fā)模式下，具有不同的發(fā)送控制信息的節(jié)點與控制信息字段。

（1）周期性觸發(fā)：該模式下，相鄰的一跳節(jié)點間將交換控制信息CM_p，CM_p字段如圖2所示。

圖2 CM_ p 字段

接收到CM_p的節(jié)點根據(jù)字段內(nèi)容更新維護(hù)鄰接節(jié)點位置信息表。

與自組網(wǎng)協(xié)議中的路由收斂機(jī)制不同的是，CM_p屬于彈性信息，即不需要對位置信息表進(jìn)行實時的維護(hù)，不同節(jié)點可以根據(jù)自身能耗狀態(tài)合理設(shè)置CM_p的發(fā)送周期。

（2）事件性觸發(fā)：該模式下，虛擬源節(jié)點向相鄰的一跳節(jié)點發(fā)送控制信息CM_i，CM_i字段如圖3所示。

圖3 CM_i 字段

CM_i信息中加入了一個征詢信息，使節(jié)點在接收到CM_i時，將回復(fù)自身位置信息表信息。

2.2 消息副本分配階段

當(dāng)消息源節(jié)點產(chǎn)生消息時，源節(jié)點將在自身鄰接節(jié)點位置信息表內(nèi)檢查是否存在目的節(jié)點的位置信息，若存在則將消息直接轉(zhuǎn)發(fā)給目的節(jié)點，否則將生成N個消息副本，并按算法分配的方向矢量選擇鄰接節(jié)點作為轉(zhuǎn)發(fā)的中繼節(jié)點，如圖4 所示。

圖4 源節(jié)點副本分配流程

在這里本文加入了方向矢量的概念，如圖5所示，方向矢量的作用是作為選擇中繼節(jié)點的一個指針，消息副本只會轉(zhuǎn)發(fā)給方向矢量范圍內(nèi)的中繼節(jié)點。

如圖5 所示，消息源節(jié)點S 一跳通信范圍內(nèi)有A、B、C、D，4 個節(jié)點，當(dāng)源節(jié)點需要轉(zhuǎn)發(fā)消息副本時，則根據(jù)方向矢量V的方向，選擇節(jié)點A 作為轉(zhuǎn)發(fā)消息的中繼節(jié)點。

方向矢量分配算法：假設(shè)消息節(jié)點位置坐標(biāo)為(X0,Y0)，其周圍n個鄰接節(jié)點的坐標(biāo)集為{(X1,Y1),(X2,Y2),…,(Xn,Yn)}，并根據(jù)式（1）得出矢量方向集合{V1,V2,…,Vn}，則有：

式中：Vi為第i個鄰接節(jié)點的矢量方向；(Xi,Yi)為第i個鄰接節(jié)點的位置坐標(biāo)，i∈[1,n]。

記消息源節(jié)點生成N個副本，建立參考集合求得矢量方向距離集合{|V|}，取最大值|Vmax|對應(yīng)的方向為參考方向，若存在多個最大值，則在其中隨機(jī)選取一個為參考方向。根據(jù)式（2）得出矢量方向與參考方向夾角集合{?1,?2,…,?n}，n為一跳內(nèi)鄰居節(jié)點數(shù)量。

式中：i∈[1,n]。

選擇與參考集合中最為接近且差值在區(qū)間[-θ,θ]內(nèi)的夾角的方向矢量為消息副本的轉(zhuǎn)發(fā)方向。

如圖6 所示，當(dāng)消息源節(jié)點產(chǎn)生4個消息副本時，參考方向為一跳范圍內(nèi)最遠(yuǎn)距離節(jié)點的方向（圖中為節(jié)點A 的方向），而后根據(jù)分配算法，將副本分配給節(jié)點A、B、C、E 作為中繼節(jié)點。

圖6 N=4 時算法演示

當(dāng)中繼節(jié)點接收到副本時，將進(jìn)行以下判斷：

（1）中繼節(jié)點一跳內(nèi)鄰居節(jié)點是否存在消息目的節(jié)點；

（2）消息傳遞跳數(shù)是否達(dá)到傳遞閾值；

（3）矢量方向的差值區(qū)間內(nèi)是否存在鄰居節(jié)點。

當(dāng)鄰居節(jié)點內(nèi)存在目的節(jié)點時，由中繼節(jié)點將消息傳輸給目的節(jié)點，否則需要進(jìn)行下兩步判斷。在這里提出了一個傳遞閾值的概念，當(dāng)節(jié)點密度大時，隨著跳數(shù)的增加，副本轉(zhuǎn)發(fā)方向的誤差將無限增大，因此需要設(shè)計一個傳遞閾值。本文假設(shè)閾值為3 跳，當(dāng)副本轉(zhuǎn)發(fā)超過3 跳且仍未交付給目的節(jié)點時，消息副本的第3 跳中繼節(jié)點則轉(zhuǎn)為虛擬源節(jié)點，進(jìn)入虛擬源節(jié)點模式；若副本轉(zhuǎn)發(fā)次數(shù)未超過傳遞閾值，中繼節(jié)點需要判斷在分配的方向差值區(qū)間內(nèi)是否存在下一跳節(jié)點，若存在則向夾角最接近分配方向的節(jié)點轉(zhuǎn)發(fā)消息，否則中繼節(jié)點則轉(zhuǎn)為虛擬源節(jié)點，進(jìn)入虛擬源節(jié)點模式，流程如圖7 所示。

圖7 中繼節(jié)點副本分配流程

2.3 虛擬源節(jié)點消息轉(zhuǎn)發(fā)階段

當(dāng)進(jìn)入虛擬源節(jié)點消息轉(zhuǎn)發(fā)階段時，虛擬源節(jié)點每當(dāng)遇到新的鄰居節(jié)點時，將按鄰接節(jié)點信息維護(hù)階段中事件性觸發(fā)鄰接節(jié)點維護(hù)模式。虛擬源節(jié)點將檢查其鄰居節(jié)點是否為消息的目的節(jié)點，若為目的節(jié)點則進(jìn)行消息的發(fā)送，若不是目的節(jié)點，則檢查其位置信息表內(nèi)是否存在目的節(jié)點的位置信息，若存在，則將消息轉(zhuǎn)發(fā)給鄰居節(jié)點實現(xiàn)消息的傳遞，否則繼續(xù)等待新的事件觸發(fā)或者消息到達(dá)生存時間后被節(jié)點丟棄。

3 仿真分析

本文在MATLAB 平臺上實現(xiàn)了GLMCA 算法的仿真，相較于其他仿真平臺如NS、ONE 等，MATLAB 通過逐幀切換的方式能夠更好地模擬網(wǎng)絡(luò)中節(jié)點間拓?fù)渥兓?，其仿真結(jié)果在相對意義上與其他仿真平臺相同。仿真參數(shù)如表2 所示。

表2 仿真參數(shù)

當(dāng)不考慮節(jié)點緩存和節(jié)點能量時，假設(shè)SAW和GLMCA 消息產(chǎn)生副本數(shù)為4，GLMCA 傳遞閾值為3，在不同節(jié)點密度下，對Epidemic、SAW 和GLMCA 3 種策略的消息投遞率、平均時延和網(wǎng)絡(luò)開銷[18]進(jìn)行仿真分析。

3.1 消息投遞率

消息投遞率是成功投遞消息數(shù)和產(chǎn)生消息數(shù)的比值。消息投遞率的仿真結(jié)果如圖8 所示。

圖8 消息投遞率對比

如圖8 所示，在短時間（5 min）內(nèi)，機(jī)會路由消息投遞率普遍不高，這是由于短時間內(nèi)中繼節(jié)點移動性受限，無法將消息迅速攜帶或者擴(kuò)散，其中GLMCA 和SAW 算法在節(jié)點數(shù)量較低時相較于Epidemic 算法具有較好的消息投遞率表現(xiàn)，尤其是當(dāng)節(jié)點數(shù)量小于40 個時，CLMCA 算法的投遞率比SAW 算法高了60%，比Epidemic 算法高了100%。當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)量在（0,180）區(qū)間內(nèi)時，GLMCA算法的投遞率一直高于其他兩種算法，當(dāng)節(jié)點數(shù)高于200 時，Epidemic 算法憑借消息副本無限制泛洪的優(yōu)勢，其消息投遞率突變上升，此時GLMCA 算法投遞率仍高于SAW 算法。

3.2 平均時延

平均時延是消息成功交付所需要時間的平均值。平均時延的仿真結(jié)果如圖9 所示。

如圖9 所示，由于節(jié)點移動性的限制，絕大部分消息的交付時間在1 s 左右，即源節(jié)點直接交付。這是由于在有限的時間內(nèi)，消息的副本無法迅速擴(kuò)散。其中，表現(xiàn)最為突出的算法為SAW 算法，然而由于該算法限制了消息副本的數(shù)量，使得其無法像Epidemic 算法那樣隨著節(jié)點密度的增高將消息副本快速在網(wǎng)絡(luò)中擴(kuò)散，當(dāng)節(jié)點移動性低時，其副本轉(zhuǎn)發(fā)模式的盲目性使得中繼節(jié)點無法將副本快速攜帶“遠(yuǎn)離”源節(jié)點。而GLMCA 算法在消息副本轉(zhuǎn)發(fā)的設(shè)計上，使得消息副本在中繼節(jié)點中仍能夠進(jìn)行多次轉(zhuǎn)發(fā)，并根據(jù)位置信息避免了消息副本轉(zhuǎn)發(fā)的盲目性。

圖9 平均時延對比

3.3 網(wǎng)絡(luò)開銷

網(wǎng)絡(luò)開銷是冗余消息副本數(shù)與成功投遞消息數(shù)的比值，其仿真結(jié)果如圖10 所示。

圖10 網(wǎng)絡(luò)開銷對比

如圖10 所示，當(dāng)節(jié)點數(shù)較低時，3 種算法的網(wǎng)絡(luò)開銷相差不大。隨著節(jié)點數(shù)量的增加，Epidemic算法開銷逐漸上升，當(dāng)節(jié)點數(shù)量為240 時，其開銷是GLMCA 算法的1.82 倍。

由于限制了網(wǎng)絡(luò)中消息副本泛洪的數(shù)量，GLMCA 算法和SAW 算法的網(wǎng)絡(luò)開銷較為穩(wěn)定，并且由于GLMCA 算法的中繼節(jié)點依舊能夠進(jìn)行有限次的消息副本轉(zhuǎn)發(fā)，因此相較于SAW 算法，在短時間內(nèi)將消息副本擴(kuò)散的概率更大，而SAW 算法由于轉(zhuǎn)發(fā)的盲目性以及中繼節(jié)點無法轉(zhuǎn)發(fā)消息副本的局限性，使得其平均開銷低于GLMCA算法4.55%。

4 結(jié)語

本文提出了一種基于地理位置信息的機(jī)會網(wǎng)絡(luò)消息副本分配策略（GLMCA），并按鄰接信息維護(hù)模式、消息副本分配模式和虛擬源節(jié)點模式3 種模式對GLMCA 策略進(jìn)行設(shè)計。根據(jù)設(shè)計，GLMCA 策略能夠利用節(jié)點自身位置信息，將產(chǎn)生消息的副本按設(shè)計的消息副本分配算法短時間內(nèi)擴(kuò)散至網(wǎng)絡(luò)中生成的虛擬源節(jié)點，虛擬源節(jié)點根據(jù)拓?fù)渥兓鲃訖z測鄰接節(jié)點位置信息，進(jìn)一步擴(kuò)大了對目的節(jié)點的檢測范圍。通過與經(jīng)典機(jī)會路由策略Epidemic 和SAW 的仿真對比發(fā)現(xiàn)，GLMCA 算法在短時間內(nèi)具有較好的消息投遞率，當(dāng)節(jié)點密度稀疏時，能夠有效利用中繼節(jié)點轉(zhuǎn)發(fā)來提升通信可靠性，并在節(jié)點密度提升時，能夠保持較低的網(wǎng)絡(luò)開銷。