孫建飛　高媛　王淑敏

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

關(guān)鍵詞：機(jī)會(huì)網(wǎng)絡(luò)；路由協(xié)議；節(jié)點(diǎn)行為；消息確認(rèn)

1 簡(jiǎn)介

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

2 OPNB路由協(xié)議

協(xié)議分為3個(gè)階段：初始化起始位置，信息產(chǎn)生和下一跳確定，信息確認(rèn)。

2.1 初始化起始位置

每個(gè)節(jié)點(diǎn)有一個(gè)確定的位置可能訪問(wèn)頻繁，其它位置訪問(wèn)較少。據(jù)此，節(jié)點(diǎn)的起始位置被分配為節(jié)點(diǎn)頻繁訪問(wèn)的位置。在網(wǎng)絡(luò)運(yùn)作過(guò)程中，不同節(jié)點(diǎn)接觸分享他們的起始位置。每個(gè)節(jié)點(diǎn)包含一個(gè)表存儲(chǔ)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的初始位置。

2.2 信息的產(chǎn)生和下一跳的確定

分為兩部分：⑴產(chǎn)生新信息和目標(biāo)id，⑵是下一跳的選擇，用到3個(gè)參數(shù)。

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

a、節(jié)點(diǎn)當(dāng)前速度大于平均速度，如下：

Snew=Sold-Sold×Sint （1）

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

b、節(jié)點(diǎn)當(dāng)前速度小于平均速度，如下：

Snew=Sold+Sold×Sint （2）

（2）預(yù)測(cè)節(jié)點(diǎn)將來(lái)的運(yùn)動(dòng)方向。

（2.a）馬爾科夫預(yù)測(cè)節(jié)點(diǎn)的下一位置：這個(gè)模型用過(guò)去的幾個(gè)位置預(yù)測(cè)下一個(gè)位置。例如：如果節(jié)點(diǎn)過(guò)去的位置序列為

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

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

（2.b）預(yù)測(cè)運(yùn)動(dòng)方向：通過(guò)角度度量預(yù)測(cè)節(jié)點(diǎn)是接近還是遠(yuǎn)離目標(biāo)節(jié)點(diǎn)。

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

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

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

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

節(jié)點(diǎn)i的角度效用計(jì)算如下：

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

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

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

綜上，效用度量如下：

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

2.3 消息確認(rèn)

確認(rèn)機(jī)制據(jù)具有一定運(yùn)動(dòng)模式的節(jié)點(diǎn)很可能再次相遇，提出以下確認(rèn)方案。一旦消息到達(dá)目標(biāo)節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)將產(chǎn)生一個(gè)AckMsg消息，如表1所示。

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

3 模擬實(shí)驗(yàn)與性能評(píng)價(jià)

OPNB使用ONE作為仿真工具。采用Custom Human Mobility model作為移動(dòng)模型。節(jié)點(diǎn)被分為6組。節(jié)點(diǎn)的傳輸距離為10m，傳輸速度2Mbps。模擬范圍為4500m× 3400m，模擬時(shí)間43000s。每隔25-35s產(chǎn)生一個(gè)500kb-1MB的新消息。參數(shù)和變量設(shè)置為：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路由協(xié)議的比較結(jié)果。如圖3所示，可以看出OPNB比另外兩種協(xié)議有更高的消息交付數(shù)。如圖4所示，展示隨節(jié)點(diǎn)數(shù)的增加開(kāi)銷在增加，這是因?yàn)楣?jié)點(diǎn)現(xiàn)在有更多的鄰居可以進(jìn)行消息的分發(fā)，但開(kāi)銷比率小于另外兩種協(xié)議，因?yàn)樗捎昧诵в枚攘?。如圖5所示，顯示OPNB的緩存延時(shí)最高，這是由于使用效用度量使消息選擇了更好的轉(zhuǎn)發(fā)節(jié)點(diǎn)。

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

4 結(jié)語(yǔ)

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

[參考文獻(xià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.