王力軍，田靜，洪濤

基于帶寬和時(shí)延的改進(jìn)ZRP路由協(xié)議研究

王力軍，田靜，洪濤

在Ad Hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)變化較大，而ZRP協(xié)議預(yù)臵半徑的做法，不能有效利用網(wǎng)絡(luò)資源。針對(duì)此問題，提出了基于帶寬和延時(shí)的BD-ZRP協(xié)議。在定義節(jié)點(diǎn)半徑時(shí)，引入帶寬和時(shí)延參數(shù)，實(shí)時(shí)改變半徑大小，以適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)變化，從而提高路由性能。通過NS2仿真表明，改進(jìn)后的BD-ZRP協(xié)議在包投遞率和時(shí)延方面比傳統(tǒng)ZRP協(xié)議具有更好的性能。

帶寬；延時(shí)；區(qū)域半徑；ZRP

0 引言

移動(dòng)網(wǎng)絡(luò)是一種移動(dòng)通信和計(jì)算機(jī)網(wǎng)絡(luò)相結(jié)合的網(wǎng)絡(luò)[1]，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都兼有路由器和主機(jī)兩種功能，它具有動(dòng)態(tài)變化的拓?fù)浣Y(jié)構(gòu)、無中心和自組織等特性[2]。為了適應(yīng)Ad Hoc的動(dòng)態(tài)拓?fù)?、帶寬和能量受限等特性，研究者提出了許多Ad hoc網(wǎng)絡(luò)路由協(xié)議[3]。根據(jù)路由觸發(fā)原理，這些路由協(xié)議可以分為先驗(yàn)式路由協(xié)議、反應(yīng)式路由協(xié)議和混合式路由協(xié)議[4]。

先驗(yàn)式路由協(xié)議又稱表驅(qū)動(dòng)路由協(xié)議，每個(gè)節(jié)點(diǎn)周期性的路由廣播，維護(hù)一張包含到達(dá)節(jié)點(diǎn)的路由信息的路由表，并根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓S時(shí)更新路由表；源節(jié)點(diǎn)一旦要發(fā)送報(bào)文，可以立即獲得到達(dá)目的節(jié)點(diǎn)的路由。因此這種路由協(xié)議的時(shí)延較小，但是協(xié)議需要大量的路由控制報(bào)文路由，協(xié)議的開銷較大。反應(yīng)式路由協(xié)議又稱按需路由，是一種當(dāng)需要時(shí)才查找路由的路由選擇方式，節(jié)點(diǎn)不需要保存整個(gè)網(wǎng)絡(luò)及時(shí)準(zhǔn)確的路由信息，當(dāng)需要發(fā)送報(bào)文時(shí)才發(fā)起路由查找過程。與先驗(yàn)式路由協(xié)議相比，反應(yīng)式路由協(xié)議的開銷小，但是數(shù)據(jù)報(bào)傳送的時(shí)延較大，不適合實(shí)時(shí)性的應(yīng)用[5]。ZRP協(xié)議是一個(gè)先驗(yàn)式和反應(yīng)式路由協(xié)議的組合，網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)都有一個(gè)以自己為中心的虛擬區(qū)，區(qū)內(nèi)的節(jié)點(diǎn)數(shù)與設(shè)定的區(qū)半徑有關(guān)，因此區(qū)是重疊的，這是與分群路由的區(qū)別；在區(qū)內(nèi)使用先驗(yàn)式路由算法，中心節(jié)點(diǎn)使用區(qū)內(nèi)路由協(xié)議IARP維持一個(gè)區(qū)[6]。本文通過引入時(shí)延、帶寬確定ZRP協(xié)議的半徑，動(dòng)態(tài)改變半徑大小，從而提高路由利用率。

1 ZRP協(xié)議

在ZRP協(xié)議中，每個(gè)節(jié)點(diǎn)都定義了一個(gè)半徑為r的域，它是以該節(jié)點(diǎn)為中心，到該節(jié)點(diǎn)的距離不超過r跳的所有節(jié)點(diǎn)的集合。節(jié)點(diǎn)A的一個(gè)半徑為2跳的域如圖1所示：

圖1 節(jié)點(diǎn)分類情況

圖1為以A為中心，跳數(shù)為2的路由區(qū)域；節(jié)點(diǎn)H在區(qū)域外，其余節(jié)點(diǎn)在區(qū)域內(nèi)。

ZRP路由協(xié)議由3部分組成，如圖2所示[7]：

圖2 ZRP路由結(jié)構(gòu)示意圖

在區(qū)域內(nèi)部采用IARP（Intra-zone Routing Protocol）協(xié)議，是一種主動(dòng)路由協(xié)議；在區(qū)域間采用IERP（Inter-zone Routing Protocol）協(xié)議，是一種按需路由協(xié)議。當(dāng)r=1時(shí)，只有鄰節(jié)點(diǎn)間周期性交換信息，ZRP演變?yōu)榘葱杪酚蓞f(xié)議；當(dāng)r=DL時(shí)（DL為Ad Hoc網(wǎng)絡(luò)最大直徑），ZRP即成為純粹的主動(dòng)路由協(xié)議。

2 基于帶寬和時(shí)延的BD-ZRP協(xié)議

ZRP協(xié)議性能的優(yōu)化主要通過調(diào)整區(qū)域半徑實(shí)現(xiàn)先應(yīng)式和后應(yīng)式路由協(xié)議間的平衡。針對(duì)該協(xié)議的改進(jìn)大多數(shù)研究主要對(duì)節(jié)點(diǎn)速率、節(jié)點(diǎn)密度和網(wǎng)絡(luò)規(guī)模進(jìn)行考慮。本文提出基于帶寬和時(shí)延的區(qū)域有效性BD-ZRP，主要是以節(jié)點(diǎn)可用帶寬和訪問時(shí)間作為節(jié)點(diǎn)訪問的依據(jù)，在協(xié)議中動(dòng)態(tài)改變半徑r，提高ZRP路由性能。BD-ZRP協(xié)議結(jié)構(gòu)如圖3所示：

圖3 BD-ZRP路由結(jié)構(gòu)示意圖

通信服務(wù)過程中引入帶寬和延時(shí)。

相比ZRP協(xié)議，BD-ZRP協(xié)議增加了帶寬和延時(shí)服務(wù)，實(shí)現(xiàn)了動(dòng)態(tài)區(qū)域的半徑可變性，包括路由表的發(fā)現(xiàn)、更新、刪除。報(bào)文格式如表1所示：

表1 BD-ZRP報(bào)文格式

擴(kuò)展了節(jié)點(diǎn)的可用帶寬、鏈接時(shí)間和半徑更新。節(jié)點(diǎn)查詢與應(yīng)答與IARP、IERP結(jié)合，實(shí)現(xiàn)區(qū)域內(nèi)外路由更新、刪除。節(jié)點(diǎn)查詢過程如下：當(dāng)一個(gè)節(jié)點(diǎn)發(fā)送路由請(qǐng)求包RREQ到它的周邊節(jié)點(diǎn)，RREQ分組的內(nèi)容包含源節(jié)點(diǎn)序號(hào)、目的節(jié)點(diǎn)序號(hào)集、半徑r。等待反饋回來的RREP分組, 并啟動(dòng)計(jì)時(shí)器, 設(shè)置最大等待時(shí)間T（T與當(dāng)前r是反比關(guān)系）。RREP分組包含所有路由節(jié)點(diǎn)的序號(hào)和鏈路的帶寬、延遲。如果接收到路由請(qǐng)求包的節(jié)點(diǎn)知道目的節(jié)點(diǎn)的位置，它會(huì)發(fā)回給源節(jié)點(diǎn)一個(gè)RREP路由回復(fù)。源節(jié)點(diǎn)將所有T內(nèi)接收到的RREP信息記錄到自己的鄰節(jié)點(diǎn)鏈表中，如表2所示：

表2 鄰節(jié)點(diǎn)鏈表

如果在T時(shí)間內(nèi)沒有接到其相鄰節(jié)點(diǎn)的信息，則認(rèn)為該節(jié)點(diǎn)已丟失，從已建的鄰節(jié)點(diǎn)鏈表中將其刪除。如果接收到新的節(jié)點(diǎn)信息，則將其加入到鄰接表中。如果一個(gè)節(jié)點(diǎn)接收到幾個(gè)相同的路由請(qǐng)求副本，這些副本將被視為冗余的而被丟棄。

每個(gè)節(jié)點(diǎn)周期性的查詢鄰接點(diǎn)信息，如果所用帶寬大于可用帶寬，且用時(shí)大于平均用時(shí)，則網(wǎng)絡(luò)條件不足且節(jié)點(diǎn)移動(dòng)較頻繁，此時(shí)需適當(dāng)減小半徑，r=r-1(r>2)。刪除區(qū)域內(nèi)半徑大于r的鏈路信息。否則所用帶寬小于可用帶寬，且用時(shí)小于平均用時(shí)，則認(rèn)為此節(jié)點(diǎn)較穩(wěn)定，保持r不變。經(jīng)過若干個(gè)周期仍是如此，則增加跳數(shù)，r=r+1。增加鏈路信息。一個(gè)周期結(jié)束，重新計(jì)算路由表，更新鏈路信息，并將更新后的路由信息廣播給周圍的節(jié)點(diǎn)。

BD-ZRP協(xié)議根據(jù)網(wǎng)絡(luò)特點(diǎn)，適當(dāng)調(diào)節(jié)區(qū)域半徑。當(dāng)帶寬充足且節(jié)點(diǎn)移動(dòng)較慢，可適當(dāng)增加跳數(shù)以有效利用網(wǎng)絡(luò)資源。當(dāng)帶寬不能滿足當(dāng)前網(wǎng)絡(luò)需求或節(jié)點(diǎn)移動(dòng)較頻繁時(shí)，則需要減小跳數(shù)，從而保證信息的有效傳達(dá)。

3 模擬仿真

網(wǎng)絡(luò)環(huán)境的設(shè)置與參考文獻(xiàn)[8]一致，物理層選用Two-ray ground reflection 無線傳播模型，鏈路層采用802.11。MAC層協(xié)議的分布式協(xié)調(diào)功能DCF（Distributed Coordination Function）。50個(gè)節(jié)點(diǎn)以0-10m/s的速度在區(qū)域1000 ×1000m2內(nèi)移動(dòng)，節(jié)點(diǎn)的傳輸半徑設(shè)為250m，信道容量為2Mbps，包長(zhǎng)為512bytes。仿真時(shí)間為500s。ZRP協(xié)議初始半徑設(shè)置為2，BD-ZRP算法與ZRP路由算法進(jìn)行仿真比較，選取平均延時(shí)（delay）和包投遞率（Packet delivery ratio）2個(gè)性能指標(biāo)作為評(píng)估對(duì)象。

3.1 平均包延時(shí)

平均包延時(shí)是指在整個(gè)模擬過程中，源節(jié)點(diǎn)發(fā)送數(shù)據(jù)到目的節(jié)點(diǎn)接收該數(shù)據(jù)所需的平均時(shí)間。反映了路由協(xié)議的效率和網(wǎng)絡(luò)特性[9]。

公式為：

平均色延時(shí)比較如圖4所示：

圖4 平均包延時(shí)比較

由圖4可看出，平均包延時(shí)隨著節(jié)點(diǎn)移動(dòng)速度的增加而增大，節(jié)點(diǎn)速度較慢時(shí)，鏈路相對(duì)穩(wěn)定，平均端到端延時(shí)較小。隨著節(jié)點(diǎn)速度的增加，鏈路斷路較多，許多節(jié)點(diǎn)丟失，導(dǎo)致延時(shí)增加。BD-ZRP算法在確定區(qū)域半徑時(shí)根據(jù)接收到的返回信息即節(jié)點(diǎn)移動(dòng)速度，動(dòng)態(tài)調(diào)整半徑大小，提高路由效率，相對(duì)ZRP協(xié)議減少了網(wǎng)絡(luò)延時(shí)。

3.2 包投遞率

包投遞率是指在整個(gè)模擬過程中，數(shù)據(jù)在路由層成功傳送的比率[10]。

包投遞率越高，網(wǎng)絡(luò)質(zhì)量超好。隨著節(jié)點(diǎn)速度的增加，鏈路穩(wěn)定性降低，數(shù)據(jù)包丟失明顯增加，導(dǎo)致包投遞率降低如圖5所示：

Research on Improved ZRP Routing Protocol Based on Bandwidth and Delay

Wang Lijun, Tian Jing, Hong Tao
(China University of Petroleum (East China), Qingdao 266580, China)

The nodes change greatly in Ad Hoc network. That the ZRP protocol presets radius， can’t effectively use network resources. Aiming at the problem, BD-ZRP protocol based on bandwidth and delay is proposed in the paper. After defining the radius of nodes, the bandwidth and delay are introduced. The radius of the network is changed real-timly to adapt to the change of the network, and to improve the performance of the routing. The NS2 simulation results show that the improved BD-ZRP protocol has a good performance than the traditional ZRP protocol in terms of packet delivery ratio and delay.

Bandwidth; Delay; Region Radius; ZRP

TP311

A

1007-757X(2016)09-0075-02

王力軍（1978-），男，漢族，臨朐人，中國(guó)石油大學(xué)（華東）高級(jí)工程師，碩士，研究方向：工程技術(shù)管理，青島 266580田 靜（1981-），女，漢族，文登人，中國(guó)石油大學(xué)（華東）工程師，碩士，研究方向：網(wǎng)絡(luò)質(zhì)量管理，青島 266580洪 濤（1976-），男，漢族，潛江人，中國(guó)石油大學(xué)（華東）高級(jí)工程師，碩士，研究方向：工程技術(shù)管理，青島 266580