基于拉格朗日乘子優(yōu)化傳輸?shù)淖顑?yōu)鏈路狀態(tài)路由

基于拉格朗日乘子優(yōu)化傳輸?shù)淖顑?yōu)鏈路狀態(tài)路由

0算法的收斂性與網(wǎng)絡(luò)開放系統(tǒng)在節(jié)點或路徑失敗的情況下，快速恢復(fù)路徑（失效恢復(fù)）是路徑狀態(tài)算法的重要性能。雖然Dijkstra算法能夠計算最短路徑的權(quán)值本文對收斂性與網(wǎng)絡(luò)開銷的權(quán)衡問題進行了形式化表述,并進行求解。利用節(jié)點在網(wǎng)絡(luò)拓撲中的中心度,計算每個節(jié)點的廣播H_M和LSA_M的間隔,進而最大化網(wǎng)絡(luò)性能。此外,為了驗證模型的有效性,將該模型應(yīng)用于最優(yōu)鏈路狀態(tài)路由(optimizedlinkstaterouting,OLSR),并分析其路由性能。1網(wǎng)絡(luò)模型和問題描述1.1基于優(yōu)化模型的路由協(xié)議分析考慮如圖1所示的網(wǎng)絡(luò)。假定節(jié)點n節(jié)點n本文針對鏈路狀態(tài)路由的節(jié)點失效問題,展開分析,先建立優(yōu)化模型,然后再利用拉格朗日乘子求解,最后將該模型應(yīng)用于OLSR協(xié)議,并分析改進后的路由協(xié)議性能。1.2多個跳網(wǎng)絡(luò)考慮網(wǎng)絡(luò)圖G(Фue788,ε),其中ue788Ф為頂點集,而ε為邊集,且‖ue788Ф‖=N,‖ε‖=E。圖G(ue788Ф,ε)代表一個多跳網(wǎng)絡(luò),每個頂點對應(yīng)一個節(jié)點,每條邊對應(yīng)一條鏈路。鏈路對應(yīng)于IP層的邏輯接口假定節(jié)點n定時器的定時時間通常為t2lmm模型建立基于拉格朗日乘子優(yōu)化傳輸控制消息間隔模型(Lagrangemultiplier-basedoptimalcontrolmessagetimersmodel,LMM)模型的目的在于優(yōu)化節(jié)點傳輸H_M和LSA_M消息的間隔2.1目標函數(shù)的建立2.1.1重建路由所需時間與hm消息間隔關(guān)系以圖1為例,若節(jié)點n1)給定網(wǎng)絡(luò)內(nèi)最短路徑p式中b2)定義因節(jié)點n可知,重建路由所需的時間與H_M消息間隔呈線性關(guān)系。因此,平均損失L也隨t為了提高路由的收斂性,應(yīng)減少t在n式中N為網(wǎng)絡(luò)內(nèi)總的節(jié)點數(shù),λ利用L和O2.1.2延所產(chǎn)生的路由每個節(jié)點n為了估計因LSA_M消息時延所產(chǎn)生的路由斷裂,需要進一步分析路由協(xié)議。仍以圖1為例,節(jié)點n類似地,在開銷一定情況下,最小化損失2.2拉格朗日乘數(shù)優(yōu)化算法基于拉格朗日乘數(shù)設(shè)x=[x首先,考慮到H_M消息的定時器,在這種情況下,x=[t類似地,求解滿足式(4)的t3sr協(xié)議傳輸周期OLSR鄰居節(jié)點感知過程如圖3所示。節(jié)點n在傳統(tǒng)的OLSR協(xié)議中,所有節(jié)點采用固定時間間隔傳輸H_M消息,并未依據(jù)節(jié)點個體特性,此外,該協(xié)議在傳輸LSA_M消息時也是采用固定周期。為此,本文先引用LMM模型優(yōu)化t4性能分析4.1動節(jié)點隨機移動考慮300m×300m移動網(wǎng)絡(luò)場景?？偣?jié)點數(shù)32個,其中移動節(jié)點數(shù)10個,其余22個節(jié)點靜止。10個移動節(jié)點隨機移動,且移動速度服從正態(tài)分布[V-2.5,V+2.5],其中V表示數(shù)值仿真圖的橫軸。節(jié)點傳輸半徑為250m,IEEE802.11速率為4Mbit/s,控制包類型為CBR,且數(shù)據(jù)包尺寸為512B,數(shù)據(jù)包傳輸速率為50packets/s。此外,為了更好地分析LMM-OLSR協(xié)議性能,選擇傳統(tǒng)的OLSR4.2實驗2不同移動速度下,ae-olsr協(xié)議的性能測試1)端到端傳輸時延首先分析數(shù)據(jù)包端到端傳輸時延隨節(jié)點移動速度的變化曲線,節(jié)點移動速度從0~30m/s變化,實驗數(shù)據(jù)如圖4所示。可知,LMM-OLSR的端到端傳輸時延最低。此外,在節(jié)點低速運動時,AFE-OLSR和OLSR協(xié)議的端到端傳輸時延性能相近,但隨著移動速度的增加,且當移動速度大于5m/s時,AFE-OLSR協(xié)議的端到端時延低于OLSR協(xié)議,這說明:在節(jié)點高速移動的環(huán)境下,AFE-OLSR協(xié)議更能快速地找到路由,縮短了端到端傳輸時延。2)數(shù)據(jù)包丟失率數(shù)據(jù)包丟失率越大,路由性能越差。3個協(xié)議的數(shù)據(jù)包丟失率數(shù)據(jù)如圖5所示?？芍?數(shù)據(jù)包丟失率隨移動速度的增加而下降,但下降速度變緩慢。這說明:最初,隨著節(jié)點速度的增加,節(jié)點移動活躍,為路由選擇提供了方便,進而提高了選擇有效路由的概率。與OLSR和AFE-OLSR協(xié)議相比,提出的LMM-OLSR協(xié)議的數(shù)據(jù)包丟失率最低。說明,LMM-OLSR協(xié)議能夠有效地提高數(shù)據(jù)包傳輸性能。3)路由開銷實驗數(shù)據(jù)如圖6所示,可知,在移動速度較小時,提出的LMM-OLSR協(xié)議的路由開銷小于OLSR和AFE-OLSR。但隨著移動速度的增加,LMM-OLSR協(xié)議的路由開銷高于OLSR和AFE-OLSR協(xié)議。主要因為:當移動速度的增加,加劇網(wǎng)絡(luò)拓撲的變化,為了提高路由協(xié)議性能,需要縮短傳輸H_M和LSA_M消息的間隔,必然加大了路由開銷。5lmm模型的優(yōu)點提出了基于拉格朗日乘子優(yōu)化傳輸控制消息間隔模