基于增量信息最小化控制開銷的OLSR 路由協(xié)議

◆崔忠林 王衡 胡春

（1.中國電子科技集團(tuán)公司第三十八研究所 安徽 230000；2.空裝駐合肥地區(qū)第一軍事代表室 安徽 230000；3.重慶郵電大學(xué) 通信與信息工程學(xué)院 重慶 400065）

隨著近年來軍事朝著無人化，智能化方向發(fā)展，傳統(tǒng)的移動自組織網(wǎng)絡(luò)越來越受到重視[1]。其中高效組網(wǎng)協(xié)議是研究的重點部分，移動自組網(wǎng)網(wǎng)絡(luò)層路由協(xié)議分為先驗式路由和反應(yīng)式路由[2]，OLSR 路由協(xié)議是先驗式路由協(xié)議的代表。由于先驗式路由在本地具有全局拓?fù)湫畔ⅲ虼薕LSR 路由協(xié)議具有時延低，適用于節(jié)點密度高的場景[3]。由于OLSR 路由協(xié)議需要依靠廣播控制消息來維持全網(wǎng)的拓?fù)湫畔ⅲ渲忻總€節(jié)點都定期廣播HELLO 消息，部分節(jié)點全網(wǎng)洪泛TC 消息，隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大和節(jié)點密度的增加，網(wǎng)絡(luò)的控制開銷會快速增加，信道利用率快速減小[4-8]。對于減少OLSR 協(xié)議的控制開銷，針對這個問題，文獻(xiàn)[9]提出了將OLSR 將應(yīng)用在無線網(wǎng)格網(wǎng)絡(luò)中，通過自適應(yīng)地最大化廣播消息間隔，最小化路由開銷，但是該協(xié)議只適用于低動態(tài)網(wǎng)絡(luò)。文獻(xiàn)[10]提出了利用博弈論減小OLSR 控制開銷，發(fā)送和接受控制消息時，每個節(jié)點都策略性的更新消息，但是該協(xié)議只能保證平均吞吐量不變。文獻(xiàn)[11]提出了在計算MPR 時，將三跳鄰居信息加入MPR 計算決策，但是該協(xié)議，沒有保證MPR集最小。文獻(xiàn)[12]提出了通過動態(tài)地調(diào)整刷新間隔的值，但是該機制在高動態(tài)環(huán)境下性能不如預(yù)期。

針對OLSR 路由協(xié)議控制開銷大，本文提出一種基于增量信息機制的OLSR 協(xié)議（incremental information OLSR，II-OLSR）。

1 OLSR 路由協(xié)議的問題

目前OLSR 協(xié)議定期發(fā)送的HELLO 和TC 消息中，含有大量冗余信息，下面詳細(xì)介紹這個問題。

1.1 控制包冗余信息

由于OLSR 路由協(xié)議的網(wǎng)絡(luò)拓?fù)涞臉?gòu)建需要依靠HELLO 消息定期廣播和TC 消息定期洪泛。如圖 1 所示，以1 號節(jié)點為例，廣播的控制消息包含一跳鄰居信息，當(dāng)5 號節(jié)點新加入網(wǎng)絡(luò)時，控制消息內(nèi)容中增加5 號節(jié)點信息，當(dāng)5 號節(jié)點脫離網(wǎng)絡(luò)時，控制消息內(nèi)容中去除5 號節(jié)點信息。由于1 號節(jié)點一跳鄰居都廣播控制消息，導(dǎo)致信道被大量控制消息占用。由于廣播的控制信息中含有大量冗余消息，如果1 號節(jié)點一跳鄰居沒有發(fā)生變化，定期發(fā)送的控制消息都是相同的，嚴(yán)重增加控制開銷。

圖1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

1.2 廣播包丟失

OLSR 路由協(xié)議的HELLO 消息和TC 消息主要是以廣播傳輸?shù)模捎趶V播包沒有ACK 機制，無線信道的傳輸特性較差，廣播包大小影響接收成功率。由于OLSR 協(xié)議存在大量冗余信息導(dǎo)致控制包接收成功率較低。

2 改進(jìn)協(xié)議II-OLSR 介紹

針對OLSR 協(xié)議控制包存在冗余信息和廣播包發(fā)送成功率低，提出一種基于增量信息的控制包發(fā)送機制。

2.1 機制一：增量HELLO 消息

HELLO 消息發(fā)送間隔為THELLO，由于接收節(jié)點對HELLO 消息內(nèi)容的保存時間為3THELLO，當(dāng)網(wǎng)絡(luò)拓?fù)溟L時間不發(fā)生變化時，發(fā)送空包表示一跳鄰居沒有發(fā)生變化。

當(dāng)一跳鄰居發(fā)生變化，如圖 2 所示，4 號節(jié)點為新加入節(jié)點，1號節(jié)點發(fā)現(xiàn)一跳鄰居節(jié)點有新節(jié)點，發(fā)送正常的HELLO 消息進(jìn)行鄰居感知，當(dāng)1 號節(jié)點完成鄰居感知，在后面連續(xù)3 個HELLO 消息發(fā)送只發(fā)送增量信息4，告知2 號和3 號節(jié)點一跳鄰居變化。

圖2 新增一跳鄰居節(jié)點

當(dāng)有一跳鄰居脫離，在之后發(fā)送的3 個HELLO 消息為正常的HELLO 消息，包含完整的一跳鄰居信息。

關(guān)于該機制一跳鄰居發(fā)生變化連續(xù)發(fā)送3 個周期HELLO 消息的說明：如果連續(xù)3 個周期鄰居節(jié)點收到廣播消息發(fā)生錯碼，導(dǎo)致接收失敗。則鄰居節(jié)點將從本地去除該節(jié)點的信息。再次進(jìn)入鄰居感知過程。

通過該機制保證在網(wǎng)絡(luò)拓?fù)渥兓徛龝r，只需交換增量信息，大幅減少HELLO 控制開銷。

2.2 機制二：新增TC 消息

由于TC 消息需要進(jìn)行全網(wǎng)泛洪，控制開銷隨著節(jié)點數(shù)增加，呈現(xiàn)指數(shù)增長，因次減少TC 消息包長能夠有效減小控制開銷。

TC 消息發(fā)送間隔為TTC，接收節(jié)點對TC 消息保存時間為3TTC。

當(dāng)網(wǎng)絡(luò)沒有新入網(wǎng)節(jié)點，且節(jié)點需要發(fā)送的TC 消息不變時，如圖 3 所示，在接下來發(fā)送的2 個空包TC 消息，表示拓?fù)錄]有變化，發(fā)送的第3 個 TC 消息為正常的TC 消息，包含完整的拓?fù)湫畔ⅰ?/p>

圖3 TC 消息維護(hù)階段

當(dāng)網(wǎng)絡(luò)有新入網(wǎng)節(jié)點或TC 消息的減少時，如圖4 所示，接下來發(fā)送2 個完整的TC 包，保證新入網(wǎng)節(jié)點能夠及時掌握全網(wǎng)拓?fù)洌筠D(zhuǎn)入正常的維護(hù)階段。

圖4 新入網(wǎng)節(jié)點或TC 內(nèi)容減少更新階段

當(dāng)TC 消息的內(nèi)容增加時，如圖5 所示。

圖5 本地TC 消息更新階段

3 理論性能分析

II-OLSR 協(xié)議是通過減小控制開銷，提高信道利用率，使改進(jìn)后的OLSR 協(xié)議在控制開銷，發(fā)包成功率，吞吐量和時延得到明顯改善，具體分析如下：

3.1 控制開銷分析

定義：M 為節(jié)點密度，V 為節(jié)點移動速度，P 為控制開銷，R 為網(wǎng)絡(luò)拓?fù)渥兓省?/p>

II-OLSR 協(xié)議發(fā)送控制包分為3 種種類：

（1）網(wǎng)絡(luò)拓?fù)湫畔⒃黾訒r，用發(fā)送增量信息代替發(fā)送完整信息，減小控制開銷。

（2）網(wǎng)絡(luò)拓?fù)洳蛔儠r，發(fā)送空包維持拓?fù)洳蛔儯瑴p少了控制開銷。

（3）網(wǎng)絡(luò)拓?fù)浒l(fā)生過期時，發(fā)送完整信息，通知周圍節(jié)點更新拓?fù)洌刂崎_銷保持不變。

改進(jìn)協(xié)議的控制開銷由上述3 類組成，如公式1 所示，

由于種類（1）、（2）控制開銷比原協(xié)議小，因此有PII-OLSR≤POLSR。

引理1：當(dāng)節(jié)點速度V 越小，網(wǎng)絡(luò)的拓?fù)渥兓蔙 越小。

當(dāng)節(jié)點密度M 越大，節(jié)點速度V 越小時，網(wǎng)絡(luò)開銷Pa和Pb越小，網(wǎng)絡(luò)總開銷越小。

3.2 發(fā)包成功率和吞吐量分析

定義：S 為發(fā)包成功率，L 為信道利用率，F(xiàn) 為網(wǎng)絡(luò)層數(shù)據(jù)量，H 為吞吐量，I 為業(yè)務(wù)數(shù)據(jù)量。

引理2：當(dāng)MAC 層和物理層保持不變時，信道利用率L 和網(wǎng)絡(luò)層向下發(fā)送的數(shù)據(jù)量F 成正向關(guān)系。

網(wǎng)絡(luò)層數(shù)據(jù)量F=P+I。

當(dāng)網(wǎng)絡(luò)層數(shù)據(jù)量保持不變時，由于II-OLSR 協(xié)議減少了控制開銷P，因此提高了業(yè)務(wù)數(shù)據(jù)量，增加了網(wǎng)絡(luò)的吞吐量。

當(dāng)業(yè)務(wù)數(shù)據(jù)量I 保持不變時，由于II-OLSR 協(xié)議減少了控制開銷P，減小了F，降低了信道利用率，由于信道擁塞減小，提高了發(fā)包成功率。

3.3 時延分析

時延D ∝（S ?K）其中K 為信道負(fù)載。由于改進(jìn)后的協(xié)議大幅度減小控制開銷的發(fā)送，使得信道負(fù)載K 得到減輕，同時由于發(fā)包成功率S 增加，改進(jìn)的協(xié)議減小了網(wǎng)絡(luò)時延特性。

4 仿真驗證

取II-OLSR 和OLSR 作為比較對象，通過仿真比較分析他們在發(fā)包成功率，時延，控制開銷，吞吐量等重要指標(biāo)。

4.1 仿真參數(shù)設(shè)置

使用Windows XP 平臺上的OPNET 仿真軟件對OLSR 和II-OLSR 協(xié)議進(jìn)行仿真。設(shè)置了在4 個仿真場景，分別為20，40，60，80 個節(jié)點在10km*10km 的矩形區(qū)域均勻分布，節(jié)點最大移動速度為50m/s，最大通信距離2km。仿真參數(shù)如表格 1 所示，MAC 層使用IEEE802.11a 標(biāo)準(zhǔn)。每個場景實驗做5 次，取平均值。

表1 仿真參數(shù)設(shè)置

4.2 仿真結(jié)果及分析

4.2.1 控制開銷

在20，40，60，80 個節(jié)點的場景中，控制開銷對比如圖 6，OLSR協(xié)議的控制開銷為：25.1Mb，99.3Mb，120.5Mb，175.7Mb，II-OLSR協(xié)議的控制開銷為：23.8Mb，91.8Mb，107.6Mb，150.7Mb，分別減少4.9%，7.2%，10.3%，14.2%；改進(jìn)協(xié)議相比原始協(xié)議控制開銷有較明顯的較少，而且在節(jié)點密度高的場景下，改善越明顯，符合理論分析。

圖6 控制開銷比較

4.2.2 時延

從圖 7 可以看出，在20，40，60，80 個節(jié)點的場景OLSR 協(xié)議的平均時延分別為：2.1ms，3.9ms，6.0ms，6.3ms，II-OLSR 協(xié)議的平均時延為：1.9ms，3.9ms，5.9ms，6.3ms。改進(jìn)協(xié)議相比原始協(xié)議時延有明顯改善，符合理論分析。

圖7 時延比較

4.2.3 發(fā)包成功率

從圖8 可以看出，在20，40，60，80 個節(jié)點的場景OLSR 協(xié)議的發(fā)包成功率為：0.94，0.89，0.85，0.81，II-OLSR 協(xié)議的發(fā)包成功率為：0.98，0.93，0.92，0.87。相較于原協(xié)議，II-OLSR 協(xié)議發(fā)包成功率分別提高了0.04，0.04，0.07，0.06，改進(jìn)后的協(xié)議在發(fā)包成功率得到明顯改善。

圖8 發(fā)包成功率比較

4.2.4 吞吐量

從圖 9 可以看出，在20，40，60，80 個節(jié)點的場景OLSR 協(xié)議的吞吐量為：2.00Mbps，1.95 Mbps，1.7 8Mbps，1.64 Mbps，II-OLSR協(xié)議的吞吐量為：2.15 Mbps，1.95 Mbps，1.84 Mbps，1.75 Mbps 。相較于原協(xié)議，II-OLSR 協(xié)議吞吐量分別提高了0.15 Mbps，0.11 Mbps，0.06 Mbps，0.11 Mbps。由于減少了控制開銷，改進(jìn)后的協(xié)議在吞吐量得到明顯改善。

圖9 吞吐量比較

4.2.5 移動速度對控制開銷的影響

分別統(tǒng)計節(jié)點在最大移動速度10m/s，20m/s，30m/s，40m/s，50m/s，在節(jié)點數(shù)為40 個時控制開銷情況，如圖 10 所示，當(dāng)節(jié)點速度越快，網(wǎng)絡(luò)拓?fù)渥兓絼×遥琁I-OLSR 協(xié)議減少的控制開銷越小，說明該協(xié)議在低動態(tài)網(wǎng)絡(luò)場景中更加適用。

圖10 節(jié)點速度對控制開銷的影響

5 結(jié)束語

本文提出來一種基于增量信息最小化控制開銷的OLSR 路由協(xié)議（II-OLSR 路由協(xié)議），通過去除控制開銷信息中的冗余信息，用發(fā)送增量信息代替發(fā)送完整信息，減少了控制開銷。由于控制開銷的減小，在相同的負(fù)載情況下，提高了信道的吞吐量。在相同網(wǎng)絡(luò)吞吐量的情況下，由于控制開銷減少，信道負(fù)載更加小，降低了發(fā)包時延，提高了發(fā)包成功率。經(jīng)仿真實驗表明：新提出的協(xié)議能夠減小控制開銷，提高發(fā)包成功率和網(wǎng)絡(luò)吞吐量，減小端到端時延，提高了OLSR路由協(xié)議性能。在未來工作中，將深入研究節(jié)點移動速度的問題，解決II-OLSR 路由協(xié)議在高動態(tài)場景的性能表現(xiàn)。