黃煜棟， 郝 平

(1.杭州科技職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 浙江 杭州 311402； 2.浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院， 浙江 杭州 310014)

0 引 言

從節(jié)點(diǎn)或鏈路失效中快速恢復(fù)路由(失效恢復(fù))是鏈路狀態(tài)路由算法的關(guān)鍵性能[1～4]。一些重要網(wǎng)絡(luò)常啟用冗余機(jī)制提升對(duì)失效節(jié)點(diǎn)的檢測(cè)速度。然而，對(duì)于一些自組織網(wǎng)絡(luò)，如移動(dòng)無(wú)線Mesh網(wǎng)絡(luò)，啟用冗余機(jī)制并不可能。因此，失效恢復(fù)仍取決于三層控制消息的交互。

雖然Dijkstra算法能夠計(jì)算最短路徑的權(quán)值[5]，但基于Dijkstra協(xié)議的收斂性(convergence)仍受到兩個(gè)因子的制約：1)失效恢復(fù)；2)新拓?fù)湫畔⒌膫鞑?。在多?shù)鏈路狀態(tài)路由中，這兩個(gè)因子交互都是利用不同的周期信息實(shí)現(xiàn)的：HELLO消息(HELLO message,H_M)以及鏈路狀態(tài)廣播消息(link state advertisement message,LSA_M)。在每個(gè)網(wǎng)絡(luò)接口、每個(gè)節(jié)點(diǎn)傳輸H_M，進(jìn)而發(fā)現(xiàn)鄰居節(jié)點(diǎn)；而每個(gè)節(jié)點(diǎn)傳輸LSA_M是為了更新路由。LSA_M在整個(gè)網(wǎng)絡(luò)內(nèi)傳播，允許每個(gè)節(jié)點(diǎn)建立并維護(hù)路由表。一旦節(jié)點(diǎn)失效，所有遍歷該節(jié)點(diǎn)的路由將失效，此外，在信息被正確地傳播至整個(gè)網(wǎng)絡(luò)之前，失效節(jié)點(diǎn)可能還會(huì)導(dǎo)致路由臨時(shí)性循環(huán)[6～8]。

本文對(duì)收斂性與網(wǎng)絡(luò)開銷的權(quán)衡問(wèn)題進(jìn)行了形式化表述，并進(jìn)行求解。利用節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械闹行亩?，?jì)算每個(gè)節(jié)點(diǎn)的廣播H_M和LSA_M的間隔，進(jìn)而最大化網(wǎng)絡(luò)性能。此外，為了驗(yàn)證模型的有效性，將該模型應(yīng)用于最優(yōu)鏈路狀態(tài)路由(optimized link state routing, OLSR)，并分析其路由性能。

1 網(wǎng)絡(luò)模型及問(wèn)題描述

1.1 問(wèn)題描述

考慮如圖1所示的網(wǎng)絡(luò)。假定節(jié)點(diǎn)n1利用節(jié)點(diǎn)n2作為連接目的節(jié)點(diǎn)n4的下一跳節(jié)點(diǎn)，n0～n4的最短路徑可表述為p0,4={n0,n1,n2,n3,n4}。本文引用pi,j={ni,…,nj}表示從節(jié)點(diǎn)ni至節(jié)點(diǎn)nj最短路徑。

圖1 網(wǎng)絡(luò)模型

節(jié)點(diǎn)n3在網(wǎng)絡(luò)內(nèi)的位置決定著其失效對(duì)整個(gè)網(wǎng)絡(luò)性能的影響：若處于網(wǎng)絡(luò)關(guān)鍵位置，則該節(jié)點(diǎn)一旦失效，將影響大量路由。如圖1所示，相比于節(jié)點(diǎn)n3，節(jié)點(diǎn)n0失效所產(chǎn)生的影響要小得多。

本文針對(duì)鏈路狀態(tài)路由的節(jié)點(diǎn)失效問(wèn)題，展開分析，先建立優(yōu)化模型，然后再利用拉格朗日乘子求解，最后將該模型應(yīng)用于OLSR協(xié)議，并分析改進(jìn)后的路由協(xié)議性能。

1.2 網(wǎng)絡(luò)模型

考慮網(wǎng)絡(luò)圖G(φ,ε), 其中φ為頂點(diǎn)集，而ε為邊集，且‖φ‖=N,‖ε‖=E。圖G(φ,ε)代表一個(gè)多跳網(wǎng)絡(luò)，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，每條邊對(duì)應(yīng)一條鏈路。鏈路對(duì)應(yīng)于IP層的邏輯接口[9]，因此，在無(wú)線網(wǎng)絡(luò)中兩條或多條鏈路可能分享同一個(gè)物理資源。

假定節(jié)點(diǎn)ni廣播H_M和LSA_M的間隔分別表示為tH(i)和tA(i)。通過(guò)一跳廣播H_M消息發(fā)現(xiàn)并維持鄰居節(jié)點(diǎn)。每條H_M消息包含了一個(gè)時(shí)效區(qū)域。節(jié)點(diǎn)通過(guò)設(shè)置定時(shí)器檢測(cè)鏈路的時(shí)效性。當(dāng)節(jié)點(diǎn)ni的鄰居節(jié)點(diǎn)nj收到來(lái)自ni的H_M消息后，就設(shè)置定時(shí)器。若在定時(shí)器計(jì)時(shí)完畢后，節(jié)點(diǎn)nj沒(méi)有收到來(lái)自ni的新消息，則節(jié)點(diǎn)nj認(rèn)為其與ni的鏈路{ni,nj}已失效(斷裂)。

定時(shí)器的定時(shí)時(shí)間通常為tH(i)的倍數(shù)關(guān)系。因此，定時(shí)時(shí)間通常等于VHtH(i),VH為常數(shù)。此外，節(jié)點(diǎn)ni以周期為tA(i)廣播LSA_M消息，通常tH(i)

2 基于拉格朗日乘子優(yōu)化傳輸控制消息間隔模型

建立基于拉格朗日乘子優(yōu)化傳輸控制消息間隔模型(Lagrange multiplier-based optimal control message timers model,LMM)模型的目的在于優(yōu)化節(jié)點(diǎn)傳輸H_M和LSA_M消息的間隔[10]，進(jìn)而在維持一定的網(wǎng)絡(luò)開銷時(shí)，保證數(shù)據(jù)傳輸?shù)牧鲿承浴Ｕ麄€(gè)LMM模型框圖如圖2所示。

圖2 LMM模型框圖

2.1 目標(biāo)函數(shù)建立

2.1.1 基于H_M消息的目標(biāo)函數(shù)

以圖1為例，若節(jié)點(diǎn)n3在時(shí)刻T0失效，節(jié)點(diǎn)n2和n4在定時(shí)時(shí)間VHtH(i)結(jié)束后，就能發(fā)現(xiàn)節(jié)點(diǎn)n3的失效。節(jié)點(diǎn)n2和n4需重新構(gòu)建路由?？紤]到最糟糕的情況：節(jié)點(diǎn)n3一廣播H_M消息，就失效,導(dǎo)致節(jié)點(diǎn)n2和n4需要經(jīng)歷Td=T0+VHtH(3)才能檢測(cè)到節(jié)點(diǎn)n3失效。

1)給定網(wǎng)絡(luò)內(nèi)最短路徑pi,j={ni,…,nj}，定義節(jié)點(diǎn)nk的最短路徑中間性(the shortest path betweenness)bk

(1)

式中bk為通用的基于圖論變量[11]，被廣泛使用。當(dāng)圖表示一個(gè)IP網(wǎng)絡(luò)，在每一個(gè)瞬間，從節(jié)點(diǎn)ni至節(jié)點(diǎn)nj間只有1條最短路徑，即‖{pi,j}‖=1。

2)定義因節(jié)點(diǎn)nk失效而引起的路由損失L(k),即因節(jié)點(diǎn)失效導(dǎo)致斷裂路由數(shù)和對(duì)數(shù)據(jù)傳輸時(shí)延的影響，L(k)=VHtH(k)N(N-1)bk。可知，實(shí)際上，L(k)是因節(jié)點(diǎn)nk失效所導(dǎo)致斷裂路徑的條數(shù)與路徑斷裂時(shí)間的乘積。

可知，重建路由所需的時(shí)間與H_M消息間隔呈線性關(guān)系。因此，平均損失L也隨tH(k)增加。此外，節(jié)點(diǎn)中心度越高，其失效所引起的斷裂路徑條數(shù)越多。

為了提高路由的收斂性，應(yīng)減少tH(k)值。但將因此增加開銷。節(jié)點(diǎn)ni因H_M消息所產(chǎn)生的開銷等于H_M消息條數(shù)與H_M消息的尺寸乘積。LMM模型不修改H_M和LSA_M消息尺寸，只是通過(guò)控制消息條數(shù)實(shí)現(xiàn)減少開銷目的。

在ni參與的所有鏈路中，ni均廣播H_M消息。因此，每秒所產(chǎn)生的H_M消息數(shù)可簡(jiǎn)化Oi=ci/tH(i),ci為ni的中心度。由文獻(xiàn)[12]，ni的中心度定義為

(2)

式中N為網(wǎng)絡(luò)內(nèi)總的節(jié)點(diǎn)數(shù)，λij為節(jié)點(diǎn)i與j間相遇率,T為觀察時(shí)間?？芍?，節(jié)點(diǎn)i的中心度Ci表示在特定時(shí)間T內(nèi)節(jié)點(diǎn)i與網(wǎng)絡(luò)內(nèi)其他節(jié)點(diǎn)相遇的平均概率。

利用L和OH建立目標(biāo)函數(shù)。開銷一定情況下，最小化路由損失，分別實(shí)現(xiàn)最小化網(wǎng)絡(luò)損失和約束開銷

(3)

2.1.2 基于LSA_M消息的目標(biāo)函數(shù)

類似地，在開銷一定情況下，最小化損失

(4)

2.2 基于 拉格朗日乘子優(yōu)化算法

首先，考慮到H_M消息的定時(shí)器，在這種情況下，x=[tH(1),tH(2),…,tH(N)],f(x),g(x)由式(3)計(jì)算,有

(5)

3 基于LMM-OLSR路由

OLSR鄰居節(jié)點(diǎn)感知過(guò)程如圖3所示。節(jié)點(diǎn)n1廣播H_M消息，若節(jié)點(diǎn)n2接收后，建立鄰居表，并將節(jié)點(diǎn)n1地址加入其H_M消息中，再向節(jié)點(diǎn)n1傳輸。節(jié)點(diǎn)n1接收了消息后，表明節(jié)點(diǎn)n2是自己一跳鄰居節(jié)點(diǎn)，再建立鄰居表。

圖3 鄰居節(jié)點(diǎn)感知過(guò)程

在傳統(tǒng)的OLSR協(xié)議中，所有節(jié)點(diǎn)采用固定時(shí)間間隔傳輸H_M消息，并未依據(jù)節(jié)點(diǎn)個(gè)體特性,此外，該協(xié)議在傳輸LSA_M消息時(shí)也是采用固定周期。為此，本文先引用LMM模型優(yōu)化tH(i)和tA(i)，進(jìn)而改進(jìn)OLSR路由協(xié)議的性能，且將此路由記為L(zhǎng)MM-OLSR。

4 性能分析

4.1 實(shí)驗(yàn)環(huán)境

考慮300 m×300 m移動(dòng)網(wǎng)絡(luò)場(chǎng)景。總節(jié)點(diǎn)數(shù)32個(gè)，其中移動(dòng)節(jié)點(diǎn)數(shù)10個(gè)，其余22個(gè)節(jié)點(diǎn)靜止。10個(gè)移動(dòng)節(jié)點(diǎn)隨機(jī)移動(dòng)，且移動(dòng)速度服從正態(tài)分布[V-2.5,V+2.5],其中V表示數(shù)值仿真圖的橫軸。節(jié)點(diǎn)傳輸半徑為250 m，IEEE 802.11速率為4 Mbit/s，控制包類型為CBR，且數(shù)據(jù)包尺寸為512 B，數(shù)據(jù)包傳輸速率為50 packets/s。

此外，為了更好地分析LMM-OLSR協(xié)議性能，選擇傳統(tǒng)的OLSR[13]和AFE-OLSR[14]進(jìn)行比較分析。主要分析數(shù)據(jù)包端到端傳輸時(shí)延、數(shù)據(jù)包丟失率以及路由開銷。每次仿真獨(dú)立重復(fù)100次，取平均值作為最終的仿真數(shù)據(jù)。

4.2 實(shí)驗(yàn)數(shù)據(jù)分析

1)端到端傳輸時(shí)延

首先分析數(shù)據(jù)包端到端傳輸時(shí)延隨節(jié)點(diǎn)移動(dòng)速度的變化曲線，節(jié)點(diǎn)移動(dòng)速度從0～30 m/s變化，實(shí)驗(yàn)數(shù)據(jù)如圖4所示。可知，LMM-OLSR的端到端傳輸時(shí)延最低。此外，在節(jié)點(diǎn)低速運(yùn)動(dòng)時(shí)，AFE-OLSR和OLSR協(xié)議的端到端傳輸時(shí)延性能相近，但隨著移動(dòng)速度的增加，且當(dāng)移動(dòng)速度大于5 m/s時(shí)，AFE-OLSR協(xié)議的端到端時(shí)延低于OLSR協(xié)議，這說(shuō)明：在節(jié)點(diǎn)高速移動(dòng)的環(huán)境下，AFE-OLSR協(xié)議更能快速地找到路由，縮短了端到端傳輸時(shí)延。

圖4 端到端傳輸時(shí)延隨節(jié)點(diǎn)移動(dòng)速度的變化情況

2) 數(shù)據(jù)包丟失率

數(shù)據(jù)包丟失率越大，路由性能越差。3個(gè)協(xié)議的數(shù)據(jù)包丟失率數(shù)據(jù)如圖5所示。

圖5 數(shù)據(jù)包丟失率隨節(jié)點(diǎn)移動(dòng)速度的影響

可知，數(shù)據(jù)包丟失率隨移動(dòng)速度的增加而下降，但下降速度變緩慢。這說(shuō)明：最初，隨著節(jié)點(diǎn)速度的增加，節(jié)點(diǎn)移動(dòng)活躍，為路由選擇提供了方便，進(jìn)而提高了選擇有效路由的概率。與OLSR和AFE-OLSR協(xié)議相比，提出的LMM-OLSR協(xié)議的數(shù)據(jù)包丟失率最低。說(shuō)明， LMM-OLSR協(xié)議能夠有效地提高數(shù)據(jù)包傳輸性能。

3)路由開銷

實(shí)驗(yàn)數(shù)據(jù)如圖6所示，可知，在移動(dòng)速度較小時(shí)，提出的LMM-OLSR協(xié)議的路由開銷小于OLSR和AFE-OLSR。但隨著移動(dòng)速度的增加，LMM-OLSR協(xié)議的路由開銷高于OLSR和AFE-OLSR協(xié)議。主要因?yàn)椋寒?dāng)移動(dòng)速度的增加，加劇網(wǎng)絡(luò)拓?fù)涞淖兓?，為了提高路由協(xié)議性能，需要縮短傳輸H_M和LSA_M消息的間隔，必然加大了路由開銷。

圖6 路由開銷

5 結(jié) 論

提出了基于拉格朗日乘子優(yōu)化傳輸控制消息間隔模型LMM，仿真結(jié)果表明，提出的LMM模型能夠有效地抑制路由開銷，降低因節(jié)點(diǎn)失效而產(chǎn)生的路由損失，進(jìn)而有效地提高數(shù)據(jù)傳輸效率，并降低了端到端傳輸時(shí)延。