基于節(jié)點行為的機會網絡路由協議

孫建飛　高媛　王淑敏

摘 要：高移動性、頻繁中斷、稀疏鏈接、沒有基礎設施和有限的資源被認為是機會網絡的特點。在這樣的網絡中路由是最大的挑戰(zhàn)，在此提出了一個新的基于節(jié)點行為的機會網絡路由協議（OPNB），用節(jié)點的行為信息預測節(jié)點在網絡中的移動，為消息路由到目標節(jié)點發(fā)現和選擇更好的下一跳節(jié)點。協議還集成了對接收消息的確認，有助于中間節(jié)點的緩存管理。通過與epidemic路由協議和Probabilistic路由協議比較，OPNB協議在消息的交付數量、開銷比率、平均延遲和緩存時間方面的表現相當不錯。

關鍵詞：機會網絡；路由協議；節(jié)點行為；消息確認

1 簡介

存在著稀疏性鏈接和間歇性鏈接的網絡被稱為機會網絡。在機會網絡的節(jié)點通常是由人或車輛攜帶的移動設備。因此在某個時間段內它們存在某種移動方式。它們可能屬于或放置在經常訪問的社區(qū)。了解節(jié)點的運動，社區(qū)與社區(qū)成員可以幫助我們在網絡中構造網絡的結構，因為根據社會學的“相關互動”意味著生物體更容易與他們自己類型的生物而不是別的生物相互交流。文獻[1]中依賴于網絡的洪泛能力最終將消息交付給目標節(jié)點，但這樣網絡中就存在同一消息的許多副本。文獻[2]中使用歷史相遇和傳遞概率來分發(fā)消息，可用于快速有效的分發(fā)消息。PRoPHET使用FIFO作為緩存管理機制，可能致使中心節(jié)點丟包且沒有包含任何的消息確認機制。

2 OPNB路由協議

協議分為3個階段：初始化起始位置，信息產生和下一跳確定，信息確認。

2.1 初始化起始位置

每個節(jié)點有一個確定的位置可能訪問頻繁，其它位置訪問較少。據此，節(jié)點的起始位置被分配為節(jié)點頻繁訪問的位置。在網絡運作過程中，不同節(jié)點接觸分享他們的起始位置。每個節(jié)點包含一個表存儲網絡中其他節(jié)點的初始位置。

2.2 信息的產生和下一跳的確定

分為兩部分：⑴產生新信息和目標id，⑵是下一跳的選擇，用到3個參數。

（1）節(jié)點的穩(wěn)定性，有下面兩種情況：

a、節(jié)點當前速度大于平均速度，如下：

Snew=Sold-Sold×Sint （1）

其中Sint 是初始化常量，屬于（0，1]。如果穩(wěn)定值已經為0，則不再減少。

b、節(jié)點當前速度小于平均速度，如下：

Snew=Sold+Sold×Sint （2）

（2）預測節(jié)點將來的運動方向。

（2.a）馬爾科夫預測節(jié)點的下一位置：這個模型用過去的幾個位置預測下一個位置。例如：如果節(jié)點過去的位置序列為

22→2→11→78→5→60→10→3→45→78→5→60→2→12→55→66→78→5→90→91→98→97→23→22→78→5→60→90

據規(guī)則為2的馬爾科夫模型，節(jié)點的下一位置為60。

（2.b）預測運動方向：通過角度度量預測節(jié)點是接近還是遠離目標節(jié)點。

（2.b.1）計算鄰居與目標節(jié)點的位置：鄰居的位置取決于笛卡爾平面的象限找到，如圖1所示，所有向原點（目標節(jié)點）移動的節(jié)點被選擇。以下方程用于轉換：

X=（x-dd）×cos（α）-（y-yd）×sin（α）

Y=（x-dd）×sin（α）+（y-yd）×cos（α）

（2.b.2）檢查鄰居節(jié)點位置相對于方程y=+/-y的角度值：如圖2所示，D代表目標節(jié)點、矢量代表節(jié)點的移動。

節(jié)點i的角度效用計算如下：

Angle_metric（i）=Aint×cos（anglei） （3）

其中，Aint是一個恒定的倍增因子，遠離目標節(jié)點的節(jié)點的角度效用值為0，確保遠離目標的節(jié)點不被選擇。

（3）從SD線到鄰居節(jié)點的垂直距離d：

綜上，效用度量如下：

W（j）（j=1，2，3）分別代表上面3個參數的常量因子，V（j）（j=1，2，3）分別代表上面3個參數的值。鄰居的效用值大于閾值T的節(jié)點作為消息的轉發(fā)節(jié)點。

2.3 消息確認

確認機制據具有一定運動模式的節(jié)點很可能再次相遇，提出以下確認方案。一旦消息到達目標節(jié)點，目標節(jié)點將產生一個AckMsg消息，如表1所示。

目的節(jié)點用Binary Spray and Wait方式的確認。每當目的節(jié)點遇到存在于AckMsg中的副本，則從鄰居中刪除，更改AckMsg并傳給該節(jié)點。修改后的AckMsg包含1/2的節(jié)點的ID數、一個新的生存時間。目標節(jié)點保持剩余的n/2的節(jié)點ID列表在修改后的AckMsg中。這個過程不斷重復，直到AckMsg僅有一個節(jié)點的ID。

3 模擬實驗與性能評價

OPNB使用ONE作為仿真工具。采用Custom Human Mobility model作為移動模型。節(jié)點被分為6組。節(jié)點的傳輸距離為10m，傳輸速度2Mbps。模擬范圍為4500m× 3400m，模擬時間43000s。每隔25-35s產生一個500kb-1MB的新消息。參數和變量設置為：tin=50，m=100，z=10，Sint=0.2，Aint=10，W（1）=0.4，W（2）=0.4，W（3）=0.2。

在圖3a-d是OPNB的性能與epidemic和PRoPHET路由協議的比較結果。如圖3所示，可以看出OPNB比另外兩種協議有更高的消息交付數。如圖4所示，展示隨節(jié)點數的增加開銷在增加，這是因為節(jié)點現在有更多的鄰居可以進行消息的分發(fā)，但開銷比率小于另外兩種協議，因為它采用了效用度量。如圖5所示，顯示OPNB的緩存延時最高，這是由于使用效用度量使消息選擇了更好的轉發(fā)節(jié)點。

在消息投遞數量上OPNB比epidemic高15.04%，比PRoPHET高10.95%。epidemic的開銷比率比OPNB多113.44%，PRoPHET的開銷比率比OPNB多54.55%。平均緩存時間比epidemic多21.27%，比PRoPHET多13.62%。

4 結語

文中提出算法據節(jié)點行為和節(jié)點的穩(wěn)定性選擇最佳的下一跳。這種方式更適合于人的移動性場景。與epidemic和PRoPHET比較，OPNB的消息交付性能很顯著，因為它選擇了更好、更可靠的下一跳節(jié)點，OPNB的平均緩存時間明顯高于另外兩種協議。今后，OPNB協議會與網絡編碼相結合實現更好的路由性能。我們還計劃研究OPNB的實際使用環(huán)境下的性能。

[參考文獻]

[1]Amin Vahdat，David Becker.Epidemic routing for partially connected ad hoc networks[R].Technical Report CS-2000-06，Department of Computer Science，Duke University，2000.

[2]Anders Lindgren，Avri Doria，Olov Schelen.Probabilistic routing in intermittently connected networks[M].In Springer-Verlag Berlin Heidelberg 2004，239-254.