基于鏈路穩(wěn)定性估計的HELLO報文自適應(yīng)發(fā)送算法

王玥琪，張唯炯，郭世杰

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

0 引言

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

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

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

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

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

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

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

(1)

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

2.1 算法原理

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

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

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

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

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

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

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

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

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

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

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

(2)

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

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

(3)

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

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

(4)

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

2.2 HELLO報文修改方法

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

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

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

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

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

3 算法仿真驗證

3.1 仿真環(huán)境

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

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

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

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

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

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

3.2 仿真結(jié)果

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

(1)不同仿真時長下HELLO報文發(fā)送總量分析

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

圖2 不同仿真時長下HELLO報文發(fā)送數(shù)量對比

(2)不同運動速率下HELLO報文發(fā)送總量分析

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

圖3 不同最大運動速率下HELLO報文發(fā)送數(shù)量對比

(3)不同運動速率下吞吐量分析

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

圖4 不同最大運動速率下吞吐量結(jié)果對比

4 結(jié)束語

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