王玥琪，張唯炯，郭世杰

(上海航天技術(shù)研究院，上海 201109)

0 引言

與傳統(tǒng)蜂窩網(wǎng)絡(luò)相比，Ad Hoc網(wǎng)絡(luò)中所有節(jié)點(diǎn)地位平等，兼具移動(dòng)終端和無(wú)線路由器的功能，并具有自組織、多點(diǎn)中繼及支持動(dòng)態(tài)拓?fù)涞葍?yōu)點(diǎn)[1]，因此在軍用和民用領(lǐng)域都有較高的應(yīng)用前景[2]。根據(jù)路由檢測(cè)方法的差異[3-4]，Ad Hoc路由協(xié)議通常分為表驅(qū)動(dòng)路由協(xié)議、按需路由協(xié)議以及混合路由協(xié)議。表驅(qū)動(dòng)路由協(xié)議的路由發(fā)現(xiàn)是節(jié)點(diǎn)通過(guò)周期性廣播交換路由信息，每個(gè)節(jié)點(diǎn)維護(hù)一張或多張包含到達(dá)網(wǎng)絡(luò)中所有節(jié)點(diǎn)路由信息的路由表[5]。優(yōu)點(diǎn)在于,當(dāng)節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)分組時(shí)，只要路由表中存在去往目的節(jié)點(diǎn)的路由，所需的延時(shí)就很??；缺點(diǎn)在于,需要花費(fèi)較大的開銷才能使節(jié)點(diǎn)路由表中的路由信息及時(shí)與當(dāng)前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)保持一致[6]。因此，合理降低網(wǎng)絡(luò)控制報(bào)文開銷是表驅(qū)動(dòng)路由協(xié)議優(yōu)化的重要方向之一。

標(biāo)準(zhǔn)OLSR路由協(xié)議采用HELLO控制分組與TC控制分組進(jìn)行全網(wǎng)拓?fù)湫畔⒌墨@取[7]。其中，HELLO控制分組用于對(duì)鄰居節(jié)點(diǎn)的探測(cè)，獲取本節(jié)點(diǎn)的一跳與兩跳鄰居信息[8]。HELLO分組的發(fā)送間隔是固定的，但這樣會(huì)帶來(lái)路由信息無(wú)法及時(shí)更新或網(wǎng)絡(luò)資源浪費(fèi)的問(wèn)題。因此，依據(jù)網(wǎng)絡(luò)拓?fù)鋵?shí)時(shí)狀態(tài)動(dòng)態(tài)調(diào)整HELLO報(bào)文發(fā)送間隔是十分有必要的，目前已有較多文獻(xiàn)對(duì)自適應(yīng)調(diào)整HELLO間隔進(jìn)行了研究。文獻(xiàn)[9]提出了一種基于差分進(jìn)化(Differential Evolution，DE)的自適應(yīng)調(diào)節(jié)HELLO報(bào)文發(fā)送間隔的算法。仿真結(jié)果表明,在不影響數(shù)據(jù)包傳輸率和平均端到端延遲的情況下，該算法可以有效地改善控制報(bào)文流量開銷，但由于DE算法需要對(duì)相鄰節(jié)點(diǎn)HELLO報(bào)文發(fā)送間隔進(jìn)行長(zhǎng)時(shí)間觀察后才能得到最優(yōu)解，因此該算法缺乏實(shí)時(shí)性，無(wú)法根據(jù)當(dāng)前網(wǎng)絡(luò)狀況及時(shí)更新HELLO發(fā)送間隔。文獻(xiàn)[10-11]依據(jù)節(jié)點(diǎn)鄰居表的變化情況與鏈路的狀態(tài)，計(jì)算得到節(jié)點(diǎn)移動(dòng)性得分與鏈路不穩(wěn)定度，使HELLO報(bào)文發(fā)送間隔在一定時(shí)間范圍內(nèi)動(dòng)態(tài)變化，但該算法中HELLO報(bào)文發(fā)送周期浮動(dòng)范圍較小，對(duì)網(wǎng)絡(luò)開銷優(yōu)化效果不明顯。文獻(xiàn)[12]通過(guò)統(tǒng)計(jì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)已發(fā)送，但還沒(méi)有得到接收方確認(rèn)的分組個(gè)數(shù)，來(lái)判斷當(dāng)前網(wǎng)絡(luò)性能的優(yōu)劣并進(jìn)行HELLO報(bào)文發(fā)送間隔的調(diào)節(jié)，但該算法要求無(wú)線信道必須具有理想的對(duì)稱性，因此限制了算法的適用范圍。

針對(duì)以上算法存在的問(wèn)題，本文提出了一種基于當(dāng)前鏈路連接穩(wěn)定性度量的HELLO報(bào)文發(fā)送間隔自適應(yīng)調(diào)節(jié)算法。該算法通過(guò)計(jì)算節(jié)點(diǎn)與鄰居點(diǎn)之間的鏈路維持概率[13]，判斷當(dāng)前鏈路的穩(wěn)定狀態(tài)，進(jìn)而實(shí)時(shí)地對(duì)HELLO報(bào)文發(fā)送間隔實(shí)施自適應(yīng)調(diào)節(jié)，即鏈路越穩(wěn)定，發(fā)送間隔越長(zhǎng)，反之縮短發(fā)送間隔。仿真結(jié)果表明，與標(biāo)準(zhǔn)OLSR路由協(xié)議及文獻(xiàn)[10]所提出的算法相比，該算法擴(kuò)大了HELLO報(bào)文發(fā)送間隔的浮動(dòng)范圍，進(jìn)一步降低了不必要的HELLO報(bào)文發(fā)送量，節(jié)省了網(wǎng)絡(luò)資源。

1 相鄰節(jié)點(diǎn)間鏈路維持概率

相鄰節(jié)點(diǎn)間鏈路維持概率的定義是：對(duì)于任意一對(duì)相鄰節(jié)點(diǎn)M和N，給定時(shí)間t，則節(jié)點(diǎn)M和節(jié)點(diǎn)N在經(jīng)過(guò)時(shí)間t之后仍然保持連接的概率[14]。相鄰節(jié)點(diǎn)間鏈路維持概率越大，說(shuō)明2節(jié)點(diǎn)間鏈路越穩(wěn)固，反之，相鄰節(jié)點(diǎn)間鏈路維持概率越小，說(shuō)明2節(jié)點(diǎn)間鏈路越不穩(wěn)定，例如節(jié)點(diǎn)可能處于鄰節(jié)點(diǎn)的通信范圍邊緣等。

通常，節(jié)點(diǎn)的運(yùn)動(dòng)遵從一定的運(yùn)動(dòng)規(guī)律，Ad Hoc無(wú)線自組網(wǎng)中有如下常見的實(shí)體移動(dòng)模型：隨機(jī)行走移動(dòng)模型、隨機(jī)方向移動(dòng)模型、隨機(jī)路點(diǎn)移動(dòng)模型(Random Waypoint Model，RWP)與高斯-馬爾可夫移動(dòng)模型[15]。本文選擇RWP對(duì)節(jié)點(diǎn)運(yùn)動(dòng)進(jìn)行近似，這是一種較為實(shí)際且應(yīng)用最廣泛的移動(dòng)模型[16-17]。

因此，當(dāng)節(jié)點(diǎn)m與鄰居節(jié)點(diǎn)n的當(dāng)前距離為d，節(jié)點(diǎn)的通信半徑為Rt，節(jié)點(diǎn)相對(duì)移動(dòng)參數(shù)為αm,n，相鄰節(jié)點(diǎn)在時(shí)間t內(nèi)保持連接的概率可以通過(guò)判斷兩點(diǎn)的相對(duì)移動(dòng)向量在時(shí)間t內(nèi)未越過(guò)通信范圍邊界的概率計(jì)算[13]。即：

(1)

2 HELLO報(bào)文發(fā)送間隔自適應(yīng)調(diào)節(jié)算法

2.1 算法原理

在OLSR路由協(xié)議中，各節(jié)點(diǎn)通過(guò)HELLO報(bào)文實(shí)現(xiàn)對(duì)鄰居節(jié)點(diǎn)的探測(cè)，并獲取本節(jié)點(diǎn)的一跳與兩跳鄰居信息。然而，標(biāo)準(zhǔn)OLSR協(xié)議的HELLO報(bào)文發(fā)送間隔是固定的，因此在網(wǎng)絡(luò)拓?fù)湎鄬?duì)穩(wěn)定的情況下，仍然發(fā)送大量的HELLO報(bào)文會(huì)造成網(wǎng)絡(luò)資源的浪費(fèi)。反之，在網(wǎng)絡(luò)拓?fù)淇焖僮兓那闆r下，需要縮短HELLO報(bào)文發(fā)送間隔，及時(shí)識(shí)別鄰居狀態(tài)變化，及時(shí)更新網(wǎng)絡(luò)拓?fù)湫畔?。針?duì)上述問(wèn)題，本文提出一種基于當(dāng)前鏈路連接穩(wěn)定性度量，實(shí)時(shí)更新HELLO報(bào)文發(fā)送間隔的自適應(yīng)算法，通過(guò)加大或縮短HELLO報(bào)文發(fā)送間隔，增強(qiáng)路由協(xié)議對(duì)節(jié)點(diǎn)鄰居狀態(tài)變化的及時(shí)識(shí)別能力，降低HELLO報(bào)文發(fā)送量，提高收斂速度，節(jié)省網(wǎng)絡(luò)資源。在該算法中，本文假設(shè)所有節(jié)點(diǎn)的收發(fā)天線均為全向波束，各節(jié)點(diǎn)通過(guò)廣播的方式發(fā)送HELLO報(bào)文。

本算法的工作主要包括以下3部分：

① 以鏈路維持概率表征相鄰節(jié)點(diǎn)間鏈路穩(wěn)定程度，通過(guò)對(duì)節(jié)點(diǎn)位置坐標(biāo)的實(shí)時(shí)跟蹤獲取當(dāng)前鏈路維持概率值，并結(jié)合上一次鏈路維持概率測(cè)量值進(jìn)行平滑處理；

② 根據(jù)平滑處理后的鏈路維持概率，調(diào)整HELLO報(bào)文發(fā)送間隔；

③ 根據(jù)鏈路維持概率的計(jì)算需要，修改OLSR控制報(bào)文格式。具體而言，即根據(jù)算法需要，在HELLO控制分組中增加節(jié)點(diǎn)位置坐標(biāo)字段。

以節(jié)點(diǎn)M為例，本算法的具體步驟如下：

① 節(jié)點(diǎn)M以等時(shí)間間隔廣播發(fā)送HELLO報(bào)文進(jìn)行鄰居感知與初始化；

② 當(dāng)節(jié)點(diǎn)M與網(wǎng)內(nèi)一跳范圍內(nèi)部分節(jié)點(diǎn)建立鄰居關(guān)系后，啟動(dòng)HELLO報(bào)文發(fā)送間隔自適應(yīng)調(diào)節(jié)算法；

③ 當(dāng)節(jié)點(diǎn)M在當(dāng)前HELLO間隔內(nèi)接收到其他節(jié)點(diǎn)發(fā)來(lái)的嵌有其位置坐標(biāo)的HELLO報(bào)文后，計(jì)算當(dāng)前時(shí)刻這些鏈路的維持概率；

④ 節(jié)點(diǎn)M計(jì)算連續(xù)2次鏈路維持概率的加權(quán)和，即

Pm,i=α*pn(m,i)+β*pn-1(m,i) (α+β=1,α>β)，

(2)

式中，pn(m,i)為當(dāng)前所得的鏈路維持概率；pn-1(m,i)為上一次報(bào)文所得的鏈路維持概率;

⑤ 根據(jù)標(biāo)準(zhǔn)OLSR路由協(xié)議[18]以及文獻(xiàn)[10-11]對(duì)HELLO報(bào)文發(fā)送間隔的設(shè)置方法，將HELLO報(bào)文發(fā)送間隔設(shè)置為如下形式：

(3)

式中，Pmin為在當(dāng)前HELLO報(bào)文發(fā)送間隔內(nèi)，節(jié)點(diǎn)已知的所有鏈路維持概率的最小值，即：

Pmin=min{Pm,1,Pm,2,Pm,3,…,Pm,i,…,Pm,n};

(4)

⑥ 節(jié)點(diǎn)M按調(diào)整后的發(fā)送間隔向所有鄰居節(jié)點(diǎn)發(fā)送HELLO報(bào)文。

2.2 HELLO報(bào)文修改方法

假定節(jié)點(diǎn)均配有GPS或北斗等導(dǎo)航系統(tǒng)，因此,節(jié)點(diǎn)可以實(shí)時(shí)獲取自身所處位置的橫縱坐標(biāo)，同時(shí)假定所有節(jié)點(diǎn)最大通信范圍固定且一致。上述節(jié)點(diǎn)實(shí)時(shí)位置信息被封裝在HELLO控制分組中以便于鄰居節(jié)點(diǎn)計(jì)算鏈路維持概率。

為實(shí)現(xiàn)本文提出的改進(jìn)算法，參照RFC3626標(biāo)準(zhǔn)文檔[18]中規(guī)定的OLSR數(shù)據(jù)結(jié)構(gòu)，對(duì)標(biāo)準(zhǔn)OLSR路由協(xié)議的HELLO控制分組進(jìn)行修改。

具體而言，相比于標(biāo)準(zhǔn)HELLO控制分組，如圖1(a)所示，改進(jìn)的HELLO控制分組中增加了節(jié)點(diǎn)的橫縱坐標(biāo)字段，其基本格式如圖1(b)所示。

(a)標(biāo)準(zhǔn)HELLO控制分組

(b)改進(jìn)后的HELLO控制分組

3 算法仿真驗(yàn)證

3.1 仿真環(huán)境

通過(guò)仿真，對(duì)本文改進(jìn)算法與文獻(xiàn)[10]所提出算法以及標(biāo)準(zhǔn)OLSR路由協(xié)議在不同仿真時(shí)長(zhǎng)與節(jié)點(diǎn)運(yùn)動(dòng)速率下的HELLO報(bào)文發(fā)送總量以及吞吐量方面進(jìn)行比較與分析。上述性能指標(biāo)的定義分別為：

① HELLO報(bào)文發(fā)送總量(HELLO Traffic Sent)：所有節(jié)點(diǎn)發(fā)送的HELLO報(bào)文量之和，單位為bits/s。

② 吞吐量(Throughput)：所有目的節(jié)點(diǎn)在單位時(shí)間內(nèi)接收到的報(bào)文量，單位為bits/s。該參數(shù)反映了網(wǎng)絡(luò)對(duì)數(shù)據(jù)業(yè)務(wù)的承載能力。

本仿真實(shí)驗(yàn)采用OPnet14.5作為網(wǎng)絡(luò)仿真實(shí)驗(yàn)平臺(tái)。仿真場(chǎng)景設(shè)置20個(gè)節(jié)點(diǎn)隨機(jī)分布在5 km×5 km的矩形區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)的無(wú)線傳輸半徑為2.5 km。仿真選擇隨機(jī)路點(diǎn)移動(dòng)模型作為節(jié)點(diǎn)的移動(dòng)模型。單個(gè)直線運(yùn)動(dòng)的速率服從(0,vmax)(m/s)的均勻分布，其中，vmax分別取5，10，15，20，25，30 m/s；單個(gè)直線運(yùn)動(dòng)的持續(xù)時(shí)間服從參數(shù)為10 s的指數(shù)分布；單個(gè)直線運(yùn)動(dòng)的方向角服從(0,2π)的均勻分布；仿真時(shí)間為500 s；自適應(yīng)算法中，取α=0.7，β=0.3。具體仿真環(huán)境參數(shù)如表1所示。

表1 網(wǎng)絡(luò)仿真參數(shù)

參數(shù)值仿真平臺(tái)版本OPnet14.5節(jié)點(diǎn)運(yùn)動(dòng)模型RWP仿真范圍/km25? 5最大通信范圍/km2.5仿真時(shí)間/s500節(jié)點(diǎn)停留時(shí)間/s0λi(節(jié)點(diǎn)運(yùn)動(dòng)時(shí)間分布)/s10

3.2 仿真結(jié)果

采用新的HELLO報(bào)文發(fā)送機(jī)制后，組網(wǎng)通信正常，與文獻(xiàn)[10]所提出算法以及標(biāo)準(zhǔn)OLSR路由協(xié)議在HELLO報(bào)文發(fā)送總量與吞吐量方面的仿真比較如圖2～圖4所示。

(1)不同仿真時(shí)長(zhǎng)下HELLO報(bào)文發(fā)送總量分析

圖2給出了在節(jié)點(diǎn)最大運(yùn)動(dòng)速率為10 m/s時(shí)，本文改進(jìn)算法、標(biāo)準(zhǔn)OLSR路由協(xié)議以及文獻(xiàn)[10]所提出算法的HELLO報(bào)文發(fā)送總量隨仿真時(shí)長(zhǎng)變化的仿真結(jié)果。相比標(biāo)準(zhǔn)OLSR路由協(xié)議，本文改進(jìn)算法在HELLO報(bào)文發(fā)送總量方面平均下降10.27%；相比文獻(xiàn)[10]所提出算法，本文改進(jìn)算法在HELLO報(bào)文發(fā)送總量方面平均下降5.39%。

圖2 不同仿真時(shí)長(zhǎng)下HELLO報(bào)文發(fā)送數(shù)量對(duì)比

(2)不同運(yùn)動(dòng)速率下HELLO報(bào)文發(fā)送總量分析

圖3給出了本文改進(jìn)算法、標(biāo)準(zhǔn)OLSR路由協(xié)議以及文獻(xiàn)[10]所提出算法的HELLO報(bào)文發(fā)送總量隨節(jié)點(diǎn)不同最大運(yùn)動(dòng)速率變化的仿真結(jié)果。由圖3可以看出，節(jié)點(diǎn)最大運(yùn)動(dòng)速率的增加會(huì)帶來(lái)網(wǎng)絡(luò)拓?fù)涞目焖僮兓?，因?種算法均隨節(jié)點(diǎn)運(yùn)動(dòng)速率的提升而呈上升趨勢(shì)。同時(shí)，相比標(biāo)準(zhǔn)OLSR路由協(xié)議，本文改進(jìn)算法在HELLO報(bào)文發(fā)送總量方面平均下降13.08%；相比文獻(xiàn)[10]所提出算法，本文改進(jìn)算法在HELLO報(bào)文發(fā)送總量方面平均下降9.96%。

圖3 不同最大運(yùn)動(dòng)速率下HELLO報(bào)文發(fā)送數(shù)量對(duì)比

(3)不同運(yùn)動(dòng)速率下吞吐量分析

圖4給出了本文改進(jìn)算法、標(biāo)準(zhǔn)OLSR路由協(xié)議以及文獻(xiàn)[10]所提出算法的吞吐量隨節(jié)點(diǎn)不同最大運(yùn)動(dòng)速率變化的仿真結(jié)果。隨著節(jié)點(diǎn)最大速率的增加，網(wǎng)絡(luò)拓?fù)洳环€(wěn)定度提高，因此3種算法的吞吐量均呈下降趨勢(shì)。同時(shí)，相比標(biāo)準(zhǔn)OLSR路由協(xié)議，本文改進(jìn)算法在吞吐量方面平均提升32.83%；相比文獻(xiàn)[10]所提出算法，本文改進(jìn)算法在吞吐量方面平均提升14.07%。

圖4 不同最大運(yùn)動(dòng)速率下吞吐量結(jié)果對(duì)比

4 結(jié)束語(yǔ)

本文基于對(duì)相鄰節(jié)點(diǎn)間鏈路穩(wěn)定性的估計(jì)，提出了一種基于鏈路維持概率的HELLO報(bào)文自適應(yīng)發(fā)送機(jī)制。該機(jī)制通過(guò)HELLO報(bào)文探測(cè)得知鄰居節(jié)點(diǎn)的最新位置信息，并計(jì)算當(dāng)前鏈路維持概率，調(diào)整下一次HELLO報(bào)文發(fā)送間隔。仿真結(jié)果表明，相比于標(biāo)準(zhǔn)OLSR路由協(xié)議以及其他相關(guān)改進(jìn)算法，本文提出的改進(jìn)算法一定程度上降低了HELLO報(bào)文總發(fā)送量，節(jié)省了網(wǎng)控報(bào)文開銷，增大了吞吐量，提升了網(wǎng)絡(luò)性能。