孫建飛　高媛　王淑敏

摘 要：高移動(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)銷(xiāo)比率、平均延遲和緩存時(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ò)被稱(chēng)為機(jī)會(huì)網(wǎng)絡(luò)。在機(jī)會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)通常是由人或車(chē)輛攜帶的移動(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)”意味著生物體更容易與他們自己類(lèi)型的生物而不是別的生物相互交流。文獻(xiàn)[1]中依賴(lài)于網(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)銷(xiāo)在增加，這是因?yàn)楣?jié)點(diǎn)現(xiàn)在有更多的鄰居可以進(jìn)行消息的分發(fā)，但開(kāi)銷(xiāo)比率小于另外兩種協(xié)議，因?yàn)樗捎昧诵в枚攘俊Ｈ鐖D5所示，顯示OPNB的緩存延時(shí)最高，這是由于使用效用度量使消息選擇了更好的轉(zhuǎn)發(fā)節(jié)點(diǎn)。

在消息投遞數(shù)量上OPNB比epidemic高15.04%，比PRoPHET高10.95%。epidemic的開(kāi)銷(xiāo)比率比OPNB多113.44%，PRoPHET的開(kāi)銷(xiāo)比率比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.