基于跨層設(shè)計的多子網(wǎng)OLSR路由協(xié)議*

鄭 重，郭強勝，毛建兵

（中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引 言

無線移動Ad Hoc網(wǎng)絡(luò)[1]是一種無中心、分布式的多跳無線網(wǎng)絡(luò)，因其不依賴于任何固定基站，能快速部署，建立起一套完整、靈活、高抗毀的網(wǎng)絡(luò)通信系統(tǒng)，提供有效的數(shù)據(jù)和多媒體通信服務(wù)，在很多特殊場合有著廣泛的應(yīng)用。Ad Hoc網(wǎng)絡(luò)路由協(xié)議根據(jù)路由發(fā)現(xiàn)策略不同[2-3]，主要分為周期性更新拓撲信息的先應(yīng)式路由協(xié)議和根據(jù)傳輸需要來尋找路由的反應(yīng)式路由協(xié)議兩大類。

在現(xiàn)代移動網(wǎng)絡(luò)應(yīng)用中，為了應(yīng)對網(wǎng)絡(luò)節(jié)點迅速和不可預料的變化，以及傳輸實時性高的特點，必須采用先應(yīng)式路由協(xié)議，而面對網(wǎng)絡(luò)規(guī)模越來越大的現(xiàn)狀，單子網(wǎng)已經(jīng)不能滿足要求，多子網(wǎng)設(shè)計能夠在保證實時性的情況下，構(gòu)建大規(guī)模的移動網(wǎng)絡(luò)。本文將介紹一種基于跨層設(shè)計的多子網(wǎng)OLSR[4]路由協(xié)議，適用于高實時性大規(guī)模移動分布式組網(wǎng)。

1 OLSR路由協(xié)議原理

優(yōu)化鏈路狀態(tài)路由協(xié)議（Optimized Link State Routing，OLSR）是IETF MANET工作組確定為RFC[5]標準的一種先應(yīng)式路由協(xié)議[6]，它是在傳統(tǒng)的鏈路狀態(tài)路由協(xié)議的基礎(chǔ)上改進而成。OLSR路由協(xié)議與傳統(tǒng)的鏈路狀態(tài)路由算法最顯著的區(qū)別在于MPR[7]（Multipoint Relay）的引入。MPR選舉機制實現(xiàn)在全網(wǎng)有效地擴散拓撲信息的同時，大大降低了路由控制消息的洪泛規(guī)模。MPR節(jié)點的選舉原則是MPR為對稱鄰居節(jié)點，通過選出的MPR可以到達所有的兩跳鄰居節(jié)點，并且選出的MPR個 數(shù)盡可能少。網(wǎng)絡(luò)中的每個節(jié)點都獨立地在自己的對稱鄰居節(jié)點中選舉自己的MPR節(jié)點集。

圖1 MPR選舉機制

如圖1所示，通過MPR節(jié)點的選舉，節(jié)點3/4/6成為節(jié)點0的MPR節(jié)點，通過這3個節(jié)點的轉(zhuǎn)發(fā)，節(jié)點0的數(shù)據(jù)發(fā)送可到達其所有的兩跳鄰居節(jié)點。可見，MPR機制提供了洪泛過程的優(yōu)化轉(zhuǎn)發(fā)[8]。

OLSR特別適用于節(jié)點多且密集分布的網(wǎng)絡(luò)。當網(wǎng)絡(luò)節(jié)點越稀疏，該協(xié)議的優(yōu)化程度就越小。當每個節(jié)點的鄰居都是MPR節(jié)點時，該協(xié)議就退化成普通的鏈路狀態(tài)路由協(xié)議。OLSR協(xié)議是為了適應(yīng)Ad Hoc網(wǎng)絡(luò)的要求，對傳統(tǒng)鏈路狀態(tài)路由算法進行改進優(yōu)化而提出的。

2 CLOLSR路由協(xié)議

在大規(guī)模組網(wǎng)情況下，為了快速響應(yīng)拓撲變化，縮短鄰居節(jié)點發(fā)現(xiàn)時間，使路由更新時間和全網(wǎng)建立時間更加符合網(wǎng)絡(luò)使用需求，CLOLSR（Cross-layer Optimized Link State Routing）路由協(xié)議創(chuàng)新性的采用了網(wǎng)絡(luò)層和鏈路層聯(lián)合設(shè)計的方式，利用鏈路層已有的控制時隙信息交互來實現(xiàn)鄰居節(jié)點的快速發(fā)現(xiàn)和網(wǎng)關(guān)節(jié)點的選舉。

2.1 基于鏈路層的快速鄰居發(fā)現(xiàn)

OLSR設(shè)計通過Hello控制消息廣播實現(xiàn)鄰居節(jié)點的發(fā)現(xiàn)。Hello控制消息中的信息對于成功完成鏈路偵聽、鄰居探測和MPR節(jié)點選舉有著重要的作用，但Hello消息發(fā)送過于頻繁，對信道傳輸資源有不小的占用。鏈路層設(shè)計了基于鄰居節(jié)點控制時隙（NiB/CNiB）的交互過程，通過節(jié)點之間在每個鄰居節(jié)點控制時隙周期（NiB-Epoch/CNiBEpoch）內(nèi)周期性的交互，鏈路層可以快速實現(xiàn)鄰居發(fā)現(xiàn)。因此，由于鏈路層已經(jīng)可以實現(xiàn)對一跳和兩跳鄰居的發(fā)現(xiàn)，OLSR路由協(xié)議可以取消Hello控制消息，由鏈路層提供一跳和兩跳鄰居信息予以使用。本文采用跨層協(xié)同設(shè)計的方法，CLOLSR路由協(xié)議使用鏈路層上報的鄰居信息來替代Hello消息的功能。

鏈路層基于NiB/CNiB交互的鄰居發(fā)現(xiàn)過程如圖2所示?？梢钥闯?，節(jié)點可以在1個Epoch時間內(nèi)實現(xiàn)對一跳鄰居的發(fā)現(xiàn)，在2個Epoch時間內(nèi)實現(xiàn)對兩跳鄰居的發(fā)現(xiàn)。特別說明，這里的鄰居發(fā)現(xiàn)給出的是對稱鏈路鄰居。

鏈路層持續(xù)不斷地監(jiān)測鄰居狀態(tài)，在鄰居發(fā)生變化時報告給路由模塊。路由模塊基于鏈路層上報的鄰居發(fā)現(xiàn)信息，根據(jù)上報內(nèi)容完善自己的鏈路狀態(tài)（Link Set）表、鄰居（Neighbor Set）表、兩跳鄰居（2-hop Neighbor Set）表，并根據(jù)表的內(nèi)容和變化，進行MPR節(jié)點集、拓撲變化、路由表的計算和更新。

圖2 鏈路層基于NiB/CNiB的鄰居發(fā)現(xiàn)

OLSR路由的Hello消息涉及鏈路偵聽、鄰居探測和MPR節(jié)點選舉等三個方面的功能。Hello被取消后，鏈路偵聽和鄰居探測通過圖2所示的鄰居NiB/CNiB交互可以實現(xiàn)，而MPR節(jié)點選舉結(jié)果的通告則需要在鏈路層和網(wǎng)絡(luò)層之間協(xié)作，以保證更快的網(wǎng)絡(luò)拓撲響應(yīng)。鄰居及鄰居鏈路的變化將導致節(jié)點MPR選舉的變化，當節(jié)點MPR節(jié)點選舉結(jié)果（即MPR節(jié)點集）發(fā)生變化時，節(jié)點將必須在一個小于Hello消息發(fā)送間隔時間內(nèi)廣播發(fā)送一個額外的MPR節(jié)點集通告控制消息，甚至可以采取立即發(fā)送通告控制消息的方式，以加快路由對于鏈路失效的響應(yīng)處理。此后，原Hello消息中執(zhí)行MPR節(jié)點集周期性通告的功能將由鏈路層周期性的NiB/CNiB分組發(fā)送通過“MPR鄰居ID”字段攜帶相關(guān)信息進行通告。

2.2 子網(wǎng)間路由抽象

以O(shè)LSR為代表的先應(yīng)式路由協(xié)議非常適合應(yīng)對網(wǎng)絡(luò)中節(jié)點位置的迅速變化和傳輸實時性高的要求，但當網(wǎng)絡(luò)規(guī)模越來越大時，OLSR采用的廣播方式擴散路由控制報文就會占用太多的開銷，為了控制網(wǎng)絡(luò)開銷，需要將OLSR路由控制報文的廣播擴散限制在一個子網(wǎng)范圍內(nèi)，子網(wǎng)與子網(wǎng)之間的路由信息通過網(wǎng)關(guān)節(jié)點拓撲抽象進行網(wǎng)間擴散。網(wǎng)關(guān)節(jié)點將抽象后的子網(wǎng)路由表發(fā)送給相鄰子網(wǎng)的網(wǎng)關(guān)節(jié)點，通過子網(wǎng)間路由抽象，實現(xiàn)了復雜拓撲的簡化，避免了局部網(wǎng)絡(luò)的拓撲變化波及全網(wǎng)，提高了網(wǎng)絡(luò)的機動性能。拓撲抽象示意如圖3所示。

子網(wǎng)之間互聯(lián)允許存在多個網(wǎng)關(guān)節(jié)點，但不允許無限增加。否則，當兩個子網(wǎng)所處地域覆蓋重疊時，每個節(jié)點都有可能成為網(wǎng)關(guān)，不合理地消耗子網(wǎng)間數(shù)據(jù)時隙資源，阻塞子網(wǎng)內(nèi)數(shù)據(jù)時隙分配和數(shù)據(jù)通信。子網(wǎng)之間互聯(lián)保持2～3個網(wǎng)關(guān)節(jié)點比較合理，并且這些網(wǎng)關(guān)節(jié)點間隔至少2跳遠，避免相互競爭資源，利于信道的空間復用。兩個子網(wǎng)之間的網(wǎng)關(guān)節(jié)點是一一對應(yīng)的，不能存在一對多的情況，否則容易出現(xiàn)網(wǎng)關(guān)節(jié)點擁塞現(xiàn)象。抽象網(wǎng)絡(luò)拓撲將子網(wǎng)內(nèi)所有節(jié)點都抽象為距離網(wǎng)關(guān)節(jié)點一跳距離。抽象網(wǎng)絡(luò)拓撲表達的跳數(shù)“距離”信息與子網(wǎng)內(nèi)路由的跳數(shù)“距離”不對等，不能合并等同在一起計算路由，否則可能產(chǎn)生路由環(huán)路?？梢哉J為，子網(wǎng)間通信的代價遠高于子網(wǎng)內(nèi)通信。

2.3 網(wǎng)關(guān)節(jié)點選舉

網(wǎng)關(guān)節(jié)點選取遵循的原則如下：

（1）為了避免擁塞，同一個節(jié)點通常情況下只能作為特定兩個子網(wǎng)之間的網(wǎng)關(guān)，而不能同時作為三個或是更多個子網(wǎng)之間的網(wǎng)關(guān)。

（2）兩個子網(wǎng)之間保持一定合理數(shù)量的網(wǎng)關(guān)節(jié)點，并且網(wǎng)關(guān)節(jié)點之間最好間隔2跳距離，利于信道的空間復用。

（3）網(wǎng)關(guān)節(jié)點選取采取分布式設(shè)計，通過啟發(fā)式算法決定一個節(jié)點在普通節(jié)點與網(wǎng)關(guān)節(jié)點之間動態(tài)轉(zhuǎn)換身份。

（4）在快速拓撲變換條件下，網(wǎng)關(guān)節(jié)點選取需要盡量選擇能夠提供穩(wěn)定的子網(wǎng)間鏈路的節(jié)點，否則不利于網(wǎng)絡(luò)的收斂和可靠通信。

網(wǎng)絡(luò)中每個節(jié)點都有機會在NiB時隙（子網(wǎng)間鄰居節(jié)點控制時隙）中廣播發(fā)送控制消息。通過偵聽接收NiB消息，節(jié)點可以獲得周圍一跳可達范圍內(nèi)其他子網(wǎng)的存在情況。當節(jié)點發(fā)現(xiàn)周圍有穩(wěn)定的其他子網(wǎng)節(jié)點存在時，則節(jié)點具備成為網(wǎng)關(guān)節(jié)點的前提條件。這時，節(jié)點需要判斷當前子網(wǎng)中是否存在多個連接該子網(wǎng)的網(wǎng)關(guān)。由于子網(wǎng)中已經(jīng)運行了先應(yīng)式路由協(xié)議，因此節(jié)點自然掌握了所在子網(wǎng)的完整網(wǎng)絡(luò)拓撲信息?；谒莆盏耐負湫畔⒁约熬W(wǎng)關(guān)在子網(wǎng)內(nèi)的通告，節(jié)點可以準確獲知當前網(wǎng)絡(luò)中有多少個網(wǎng)關(guān)節(jié)點，以及這些網(wǎng)關(guān)節(jié)點距離自己的跳數(shù)等。

網(wǎng)關(guān)節(jié)點選取的算法過程設(shè)計如圖4所示。其中，持續(xù)監(jiān)測時間Tstab目的在于保證網(wǎng)關(guān)跨子網(wǎng)通信鏈路的穩(wěn)定性。

圖4 網(wǎng)關(guān)節(jié)點選取算法

如果具備成為網(wǎng)關(guān)節(jié)點條件的普通節(jié)點發(fā)現(xiàn)子網(wǎng)內(nèi)網(wǎng)關(guān)節(jié)點數(shù)量不足，且自身所處網(wǎng)絡(luò)位置與現(xiàn)有網(wǎng)關(guān)節(jié)點的距離跳數(shù)大于2跳，則節(jié)點從普通節(jié)點身份轉(zhuǎn)換為網(wǎng)關(guān)節(jié)點，并向網(wǎng)絡(luò)中通報連接可達的子網(wǎng)的抽象鏈路狀態(tài)更新信息。

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

3.1 仿真條件和基本參數(shù)配置

本文使用OPNET Modeler 14.5.A仿真軟件建立網(wǎng)絡(luò)模型，仿真場景為20 km×20 km的區(qū)域內(nèi)放置32～128個節(jié)點，假定所有節(jié)點都已完成外同步，節(jié)點間隨機形成最大跳數(shù)為8的網(wǎng)絡(luò)。

仿真中，各節(jié)點的仿真模型均相同，物理層采用自由空間模型[9]，鏈路層采用TDMA（Time Division Multiple Access）分時復用傳輸機制，信道被劃分為子幀和時幀，連續(xù)的3個子幀聯(lián)合并在一起構(gòu)成一個時幀，一個子幀的時間為46.875 ms，子幀中每個時隙的長度約0.937 5 ms，每個子幀共計劃分50個時隙，包括控制時隙和數(shù)據(jù)時隙。根據(jù)控制時隙具體用途的不同，控制時隙具體又分為：NiB時隙、CNiB時隙。根據(jù)鏈路層時幀結(jié)構(gòu)設(shè)計，仿真中TDMA參數(shù)配置如表1所示。

表1 鏈路層參數(shù)配置

網(wǎng)絡(luò)層路由協(xié)議基本參數(shù)配置如表2所示。

表2 路由協(xié)議基本參數(shù)配置

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

為了對CLOLSR協(xié)議進行性能評估，在完全相同的參數(shù)配置情況下，本文將CLOLSR協(xié)議與傳統(tǒng)OLSR協(xié)議從初始建網(wǎng)時間、鄰居節(jié)點發(fā)現(xiàn)時間、網(wǎng)絡(luò)局部變化收斂時間、平均路由開銷和平均一跳端到端時延五個方面進行仿真對比。

圖5是兩種協(xié)議128節(jié)點初始建網(wǎng)時間對比圖，為了研究網(wǎng)絡(luò)收斂情況，配置網(wǎng)絡(luò)中所有節(jié)點位于初始位置不動。從圖5中可以看出，CLOLSR路由協(xié)議的初始建網(wǎng)時間遠小于OLSR路由協(xié)議，只有后者的二分之一左右，這主要是因為CLOLSR路由協(xié)議采用了劃分多子網(wǎng)的方式，每個子網(wǎng)可以迅速完成收斂，且利用子網(wǎng)間的路由抽象完成整個網(wǎng)絡(luò)的建立，相對于OLSR路由協(xié)議需要等到探測消息擴散至全網(wǎng)才能完成網(wǎng)絡(luò)的收斂，CLOLSR路由協(xié)議的初始建網(wǎng)時間要快很多。

圖5 128節(jié)點初始建網(wǎng)時間

圖6 是兩種協(xié)議的鄰居節(jié)點發(fā)現(xiàn)時間對比圖，從圖6中可以看出，在同樣的條件下，CLOLSR路由協(xié)議的鄰居節(jié)點發(fā)現(xiàn)時間小于OLSR路由協(xié)議，這是由于CLOLSR協(xié)議利用了鏈路層設(shè)計的基于鄰居節(jié)點控制時隙（NiB/CNiB）的交互，通過節(jié)點之間在每個鄰居節(jié)點控制時隙周期內(nèi)周期性的交互，可以快速實現(xiàn)鄰居發(fā)現(xiàn)，而OLSR路由協(xié)議則只能通過自身發(fā)送Hello消息，通過底層傳輸?shù)竭_對端，再收到回復后才能實現(xiàn)鄰居發(fā)現(xiàn)，因此鄰居節(jié)點發(fā)現(xiàn)時間要慢一些。

圖6 鄰居節(jié)點發(fā)現(xiàn)時間

為了測試網(wǎng)絡(luò)局部變化收斂時間，設(shè)定拓撲變化如圖7中拓撲1變?yōu)橥負?，通過觀察路由表變化，測量子網(wǎng)收斂時間大小。

圖7 網(wǎng)絡(luò)局部變化示意圖

兩種協(xié)議的測量結(jié)果如圖8所示，從圖8中可以看出，對于圖7所示的網(wǎng)絡(luò)局部變化，CLOLSR路由協(xié)議基本可以將收斂時間控制在1 s左右，OLSR路由協(xié)議則普遍需要2.5 s以上，這是因為CLOLSR協(xié)議利用鏈路層的快速鄰居發(fā)現(xiàn)機制迅速的完成了一跳和兩跳鄰居的探測，對于距離兩跳以上的節(jié)點，只需要收到TC消息即可建立路由，對于OLSR協(xié)議，則需要首先利用Hello消息獲知一跳和兩跳鄰居信息，然后通過選舉出的MPR節(jié)點發(fā)送TC消息獲知到達兩跳以外節(jié)點的路由。因此，網(wǎng)絡(luò)局部變化收斂時間較長。

圖8 網(wǎng)絡(luò)局部變化收斂時間

圖9 是兩種協(xié)議的32節(jié)點網(wǎng)絡(luò)平均路由開銷對比圖。從圖9中可以看出，網(wǎng)絡(luò)建立伊始，由于網(wǎng)絡(luò)尋路需求較大，控制開銷發(fā)送頻繁，平均路由開銷較高，但隨著通信鏈路的陸續(xù)建立，控制消息的發(fā)送需求也隨之下降，因此平均路由開銷逐漸降低，此后平均路由開銷只在有限范圍內(nèi)波動。CLOLSR協(xié)議平均路由開銷始終要低于OLSR協(xié)議，這是因為CLOLSR協(xié)議取消了Hello消息，而使用鏈路層上報的鄰居信息來替代，從而降低了平均路由開銷，節(jié)省了帶寬資源。

圖10是兩種協(xié)議的平均一跳數(shù)據(jù)端到端延時對比圖，測試數(shù)據(jù)包長度為512字節(jié)。從圖10中可以看出，兩者的延時相差不大，基本保持一致，說明CLOLSR路由協(xié)議在協(xié)議本身的性能和開銷上有優(yōu)化，在一定程度上緩解了網(wǎng)絡(luò)擁塞，但是在網(wǎng)絡(luò)整體業(yè)務(wù)流量較低的情況下，鏈路建立之后，對于業(yè)務(wù)數(shù)據(jù)的傳輸延時改善不大。

圖9 32節(jié)點網(wǎng)絡(luò)平均路由開銷

圖10 平均一跳數(shù)據(jù)端到端延時

4 結(jié) 語

本文為了提升OLSR 協(xié)議在高實時性大規(guī)模組網(wǎng)條件下網(wǎng)絡(luò)的整體性能，提出了基于鏈路層的快速鄰居發(fā)現(xiàn)和網(wǎng)管節(jié)點選舉、子網(wǎng)間路由抽象兩點改進意見。并將CLOLSR協(xié)議與OLSR協(xié)議進行了仿真對比，結(jié)果表明：CLOLSR協(xié)議不僅在初始建網(wǎng)時間、鄰居節(jié)點發(fā)現(xiàn)時間、網(wǎng)絡(luò)局部變化收斂時間等網(wǎng)絡(luò)性能指標上有較大提升，還降低了網(wǎng)絡(luò)平均路由開銷，在大規(guī)模自組織網(wǎng)絡(luò)中具有一定的應(yīng)用前景。