基于拉格朗日乘子優化傳輸控制消息間隔的OLSR協議*

2018-11-28 02:12:48黃煜棟

傳感器與微系統 2018年12期

黃煜棟，郝平

(1.杭州科技職業技術學院信息工程學院，浙江杭州 311402； 2.浙江工業大學計算機學院，浙江杭州 310014)

0 引言

從節點或鏈路失效中快速恢復路由(失效恢復)是鏈路狀態路由算法的關鍵性能[1～4]。一些重要網絡常啟用冗余機制提升對失效節點的檢測速度。然而，對于一些自組織網絡，如移動無線Mesh網絡，啟用冗余機制并不可能。因此，失效恢復仍取決于三層控制消息的交互。

雖然Dijkstra算法能夠計算最短路徑的權值[5]，但基于Dijkstra協議的收斂性(convergence)仍受到兩個因子的制約：1)失效恢復；2)新拓撲信息的傳播。在多數鏈路狀態路由中，這兩個因子交互都是利用不同的周期信息實現的：HELLO消息(HELLO message,H_M)以及鏈路狀態廣播消息(link state advertisement message,LSA_M)。在每個網絡接口、每個節點傳輸H_M，進而發現鄰居節點；而每個節點傳輸LSA_M是為了更新路由。LSA_M在整個網絡內傳播，允許每個節點建立并維護路由表。一旦節點失效，所有遍歷該節點的路由將失效，此外，在信息被正確地傳播至整個網絡之前，失效節點可能還會導致路由臨時性循環[6～8]。

本文對收斂性與網絡開銷的權衡問題進行了形式化表述，并進行求解。利用節點在網絡拓撲中的中心度，計算每個節點的廣播H_M和LSA_M的間隔，進而最大化網絡性能。此外，為了驗證模型的有效性，將該模型應用于最優鏈路狀態路由(optimized link state routing, OLSR)，并分析其路由性能。

1 網絡模型及問題描述

1.1 問題描述

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

圖1 網絡模型

節點n3在網絡內的位置決定著其失效對整個網絡性能的影響：若處于網絡關鍵位置，則該節點一旦失效，將影響大量路由。如圖1所示，相比于節點n3，節點n0失效所產生的影響要小得多。

本文針對鏈路狀態路由的節點失效問題，展開分析，先建立優化模型，然后再利用拉格朗日乘子求解，最后將該模型應用于OLSR協議，并分析改進后的路由協議性能。

1.2 網絡模型

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

假定節點ni廣播H_M和LSA_M的間隔分別表示為tH(i)和tA(i)。通過一跳廣播H_M消息發現并維持鄰居節點。每條H_M消息包含了一個時效區域。節點通過設置定時器檢測鏈路的時效性。當節點ni的鄰居節點nj收到來自ni的H_M消息后，就設置定時器。若在定時器計時完畢后，節點nj沒有收到來自ni的新消息，則節點nj認為其與ni的鏈路{ni,nj}已失效(斷裂)。

定時器的定時時間通常為tH(i)的倍數關系。因此，定時時間通常等于VHtH(i),VH為常數。此外，節點ni以周期為tA(i)廣播LSA_M消息，通常tH(i)

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

建立基于拉格朗日乘子優化傳輸控制消息間隔模型(Lagrange multiplier-based optimal control message timers model,LMM)模型的目的在于優化節點傳輸H_M和LSA_M消息的間隔[10]，進而在維持一定的網絡開銷時，保證數據傳輸的流暢性。整個LMM模型框圖如圖2所示。

圖2 LMM模型框圖

2.1 目標函數建立

2.1.1 基于H_M消息的目標函數

以圖1為例，若節點n3在時刻T0失效，節點n2和n4在定時時間VHtH(i)結束后，就能發現節點n3的失效。節點n2和n4需重新構建路由。考慮到最糟糕的情況：節點n3一廣播H_M消息，就失效,導致節點n2和n4需要經歷Td=T0+VHtH(3)才能檢測到節點n3失效。

1)給定網絡內最短路徑pi,j={ni,…,nj}，定義節點nk的最短路徑中間性(the shortest path betweenness)bk

(1)

式中bk為通用的基于圖論變量[11]，被廣泛使用。當圖表示一個IP網絡，在每一個瞬間，從節點ni至節點nj間只有1條最短路徑，即‖{pi,j}‖=1。

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

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

為了提高路由的收斂性，應減少tH(k)值。但將因此增加開銷。節點ni因H_M消息所產生的開銷等于H_M消息條數與H_M消息的尺寸乘積。LMM模型不修改H_M和LSA_M消息尺寸，只是通過控制消息條數實現減少開銷目的。

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

(2)

式中N為網絡內總的節點數，λij為節點i與j間相遇率,T為觀察時間?？芍?，節點i的中心度Ci表示在特定時間T內節點i與網絡內其他節點相遇的平均概率。

利用L和OH建立目標函數。開銷一定情況下，最小化路由損失，分別實現最小化網絡損失和約束開銷

(3)

2.1.2 基于LSA_M消息的目標函數

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

(4)

2.2 基于拉格朗日乘子優化算法

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

(5)

3 基于LMM-OLSR路由

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

圖3 鄰居節點感知過程

在傳統的OLSR協議中，所有節點采用固定時間間隔傳輸H_M消息，并未依據節點個體特性,此外，該協議在傳輸LSA_M消息時也是采用固定周期。為此，本文先引用LMM模型優化tH(i)和tA(i)，進而改進OLSR路由協議的性能，且將此路由記為LMM-OLSR。

4 性能分析

4.1 實驗環境

考慮300 m×300 m移動網絡場景。總節點數32個，其中移動節點數10個，其余22個節點靜止。10個移動節點隨機移動，且移動速度服從正態分布[V-2.5,V+2.5],其中V表示數值仿真圖的橫軸。節點傳輸半徑為250 m，IEEE 802.11速率為4 Mbit/s，控制包類型為CBR，且數據包尺寸為512 B，數據包傳輸速率為50 packets/s。

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

4.2 實驗數據分析

1)端到端傳輸時延

首先分析數據包端到端傳輸時延隨節點移動速度的變化曲線，節點移動速度從0～30 m/s變化，實驗數據如圖4所示?？芍?，LMM-OLSR的端到端傳輸時延最低。此外，在節點低速運動時，AFE-OLSR和OLSR協議的端到端傳輸時延性能相近，但隨著移動速度的增加，且當移動速度大于5 m/s時，AFE-OLSR協議的端到端時延低于OLSR協議，這說明：在節點高速移動的環境下，AFE-OLSR協議更能快速地找到路由，縮短了端到端傳輸時延。

圖4 端到端傳輸時延隨節點移動速度的變化情況

2) 數據包丟失率

數據包丟失率越大，路由性能越差。3個協議的數據包丟失率數據如圖5所示。

圖5 數據包丟失率隨節點移動速度的影響

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

3)路由開銷

實驗數據如圖6所示，可知，在移動速度較小時，提出的LMM-OLSR協議的路由開銷小于OLSR和AFE-OLSR。但隨著移動速度的增加，LMM-OLSR協議的路由開銷高于OLSR和AFE-OLSR協議。主要因為：當移動速度的增加，加劇網絡拓撲的變化，為了提高路由協議性能，需要縮短傳輸H_M和LSA_M消息的間隔，必然加大了路由開銷。