鄭 重,郭強(qiáng)勝,毛建兵
(中國電子科技集團(tuán)公司第三十研究所,四川 成都 610041)
無線移動(dòng)Ad Hoc網(wǎng)絡(luò)[1]是一種無中心、分布式的多跳無線網(wǎng)絡(luò),因其不依賴于任何固定基站,能快速部署,建立起一套完整、靈活、高抗毀的網(wǎng)絡(luò)通信系統(tǒng),提供有效的數(shù)據(jù)和多媒體通信服務(wù),在很多特殊場(chǎng)合有著廣泛的應(yīng)用。Ad Hoc網(wǎng)絡(luò)路由協(xié)議根據(jù)路由發(fā)現(xiàn)策略不同[2-3],主要分為周期性更新拓?fù)湫畔⒌南葢?yīng)式路由協(xié)議和根據(jù)傳輸需要來尋找路由的反應(yīng)式路由協(xié)議兩大類。
在現(xiàn)代移動(dòng)網(wǎng)絡(luò)應(yīng)用中,為了應(yīng)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)迅速和不可預(yù)料的變化,以及傳輸實(shí)時(shí)性高的特點(diǎn),必須采用先應(yīng)式路由協(xié)議,而面對(duì)網(wǎng)絡(luò)規(guī)模越來越大的現(xiàn)狀,單子網(wǎng)已經(jīng)不能滿足要求,多子網(wǎng)設(shè)計(jì)能夠在保證實(shí)時(shí)性的情況下,構(gòu)建大規(guī)模的移動(dòng)網(wǎng)絡(luò)。本文將介紹一種基于跨層設(shè)計(jì)的多子網(wǎng)OLSR[4]路由協(xié)議,適用于高實(shí)時(shí)性大規(guī)模移動(dòng)分布式組網(wǎng)。
優(yōu)化鏈路狀態(tài)路由協(xié)議(Optimized Link State Routing,OLSR)是IETF MANET工作組確定為RFC[5]標(biāo)準(zhǔn)的一種先應(yīng)式路由協(xié)議[6],它是在傳統(tǒng)的鏈路狀態(tài)路由協(xié)議的基礎(chǔ)上改進(jìn)而成。OLSR路由協(xié)議與傳統(tǒng)的鏈路狀態(tài)路由算法最顯著的區(qū)別在于MPR[7](Multipoint Relay)的引入。MPR選舉機(jī)制實(shí)現(xiàn)在全網(wǎng)有效地?cái)U(kuò)散拓?fù)湫畔⒌耐瑫r(shí),大大降低了路由控制消息的洪泛規(guī)模。MPR節(jié)點(diǎn)的選舉原則是MPR為對(duì)稱鄰居節(jié)點(diǎn),通過選出的MPR可以到達(dá)所有的兩跳鄰居節(jié)點(diǎn),并且選出的MPR個(gè) 數(shù)盡可能少。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都獨(dú)立地在自己的對(duì)稱鄰居節(jié)點(diǎn)中選舉自己的MPR節(jié)點(diǎn)集。
圖1 MPR選舉機(jī)制
如圖1所示,通過MPR節(jié)點(diǎn)的選舉,節(jié)點(diǎn)3/4/6成為節(jié)點(diǎn)0的MPR節(jié)點(diǎn),通過這3個(gè)節(jié)點(diǎn)的轉(zhuǎn)發(fā),節(jié)點(diǎn)0的數(shù)據(jù)發(fā)送可到達(dá)其所有的兩跳鄰居節(jié)點(diǎn)??梢姡琈PR機(jī)制提供了洪泛過程的優(yōu)化轉(zhuǎn)發(fā)[8]。
OLSR特別適用于節(jié)點(diǎn)多且密集分布的網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)越稀疏,該協(xié)議的優(yōu)化程度就越小。當(dāng)每個(gè)節(jié)點(diǎn)的鄰居都是MPR節(jié)點(diǎn)時(shí),該協(xié)議就退化成普通的鏈路狀態(tài)路由協(xié)議。OLSR協(xié)議是為了適應(yīng)Ad Hoc網(wǎng)絡(luò)的要求,對(duì)傳統(tǒng)鏈路狀態(tài)路由算法進(jìn)行改進(jìn)優(yōu)化而提出的。
在大規(guī)模組網(wǎng)情況下,為了快速響應(yīng)拓?fù)渥兓?,縮短鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間,使路由更新時(shí)間和全網(wǎng)建立時(shí)間更加符合網(wǎng)絡(luò)使用需求,CLOLSR(Cross-layer Optimized Link State Routing)路由協(xié)議創(chuàng)新性的采用了網(wǎng)絡(luò)層和鏈路層聯(lián)合設(shè)計(jì)的方式,利用鏈路層已有的控制時(shí)隙信息交互來實(shí)現(xiàn)鄰居節(jié)點(diǎn)的快速發(fā)現(xiàn)和網(wǎng)關(guān)節(jié)點(diǎn)的選舉。
OLSR設(shè)計(jì)通過Hello控制消息廣播實(shí)現(xiàn)鄰居節(jié)點(diǎn)的發(fā)現(xiàn)。Hello控制消息中的信息對(duì)于成功完成鏈路偵聽、鄰居探測(cè)和MPR節(jié)點(diǎn)選舉有著重要的作用,但Hello消息發(fā)送過于頻繁,對(duì)信道傳輸資源有不小的占用。鏈路層設(shè)計(jì)了基于鄰居節(jié)點(diǎn)控制時(shí)隙(NiB/CNiB)的交互過程,通過節(jié)點(diǎn)之間在每個(gè)鄰居節(jié)點(diǎn)控制時(shí)隙周期(NiB-Epoch/CNiBEpoch)內(nèi)周期性的交互,鏈路層可以快速實(shí)現(xiàn)鄰居發(fā)現(xiàn)。因此,由于鏈路層已經(jīng)可以實(shí)現(xiàn)對(duì)一跳和兩跳鄰居的發(fā)現(xiàn),OLSR路由協(xié)議可以取消Hello控制消息,由鏈路層提供一跳和兩跳鄰居信息予以使用。本文采用跨層協(xié)同設(shè)計(jì)的方法,CLOLSR路由協(xié)議使用鏈路層上報(bào)的鄰居信息來替代Hello消息的功能。
鏈路層基于NiB/CNiB交互的鄰居發(fā)現(xiàn)過程如圖2所示??梢钥闯?,節(jié)點(diǎn)可以在1個(gè)Epoch時(shí)間內(nèi)實(shí)現(xiàn)對(duì)一跳鄰居的發(fā)現(xiàn),在2個(gè)Epoch時(shí)間內(nèi)實(shí)現(xiàn)對(duì)兩跳鄰居的發(fā)現(xiàn)。特別說明,這里的鄰居發(fā)現(xiàn)給出的是對(duì)稱鏈路鄰居。
鏈路層持續(xù)不斷地監(jiān)測(cè)鄰居狀態(tài),在鄰居發(fā)生變化時(shí)報(bào)告給路由模塊。路由模塊基于鏈路層上報(bào)的鄰居發(fā)現(xiàn)信息,根據(jù)上報(bào)內(nèi)容完善自己的鏈路狀態(tài)(Link Set)表、鄰居(Neighbor Set)表、兩跳鄰居(2-hop Neighbor Set)表,并根據(jù)表的內(nèi)容和變化,進(jìn)行MPR節(jié)點(diǎn)集、拓?fù)渥兓⒙酚杀淼挠?jì)算和更新。
圖2 鏈路層基于NiB/CNiB的鄰居發(fā)現(xiàn)
OLSR路由的Hello消息涉及鏈路偵聽、鄰居探測(cè)和MPR節(jié)點(diǎn)選舉等三個(gè)方面的功能。Hello被取消后,鏈路偵聽和鄰居探測(cè)通過圖2所示的鄰居NiB/CNiB交互可以實(shí)現(xiàn),而MPR節(jié)點(diǎn)選舉結(jié)果的通告則需要在鏈路層和網(wǎng)絡(luò)層之間協(xié)作,以保證更快的網(wǎng)絡(luò)拓?fù)漤憫?yīng)。鄰居及鄰居鏈路的變化將導(dǎo)致節(jié)點(diǎn)MPR選舉的變化,當(dāng)節(jié)點(diǎn)MPR節(jié)點(diǎn)選舉結(jié)果(即MPR節(jié)點(diǎn)集)發(fā)生變化時(shí),節(jié)點(diǎn)將必須在一個(gè)小于Hello消息發(fā)送間隔時(shí)間內(nèi)廣播發(fā)送一個(gè)額外的MPR節(jié)點(diǎn)集通告控制消息,甚至可以采取立即發(fā)送通告控制消息的方式,以加快路由對(duì)于鏈路失效的響應(yīng)處理。此后,原Hello消息中執(zhí)行MPR節(jié)點(diǎn)集周期性通告的功能將由鏈路層周期性的NiB/CNiB分組發(fā)送通過“MPR鄰居ID”字段攜帶相關(guān)信息進(jìn)行通告。
以O(shè)LSR為代表的先應(yīng)式路由協(xié)議非常適合應(yīng)對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)位置的迅速變化和傳輸實(shí)時(shí)性高的要求,但當(dāng)網(wǎng)絡(luò)規(guī)模越來越大時(shí),OLSR采用的廣播方式擴(kuò)散路由控制報(bào)文就會(huì)占用太多的開銷,為了控制網(wǎng)絡(luò)開銷,需要將OLSR路由控制報(bào)文的廣播擴(kuò)散限制在一個(gè)子網(wǎng)范圍內(nèi),子網(wǎng)與子網(wǎng)之間的路由信息通過網(wǎng)關(guān)節(jié)點(diǎn)拓?fù)涑橄筮M(jìn)行網(wǎng)間擴(kuò)散。網(wǎng)關(guān)節(jié)點(diǎn)將抽象后的子網(wǎng)路由表發(fā)送給相鄰子網(wǎng)的網(wǎng)關(guān)節(jié)點(diǎn),通過子網(wǎng)間路由抽象,實(shí)現(xiàn)了復(fù)雜拓?fù)涞暮?jiǎn)化,避免了局部網(wǎng)絡(luò)的拓?fù)渥兓叭W(wǎng),提高了網(wǎng)絡(luò)的機(jī)動(dòng)性能。拓?fù)涑橄笫疽馊鐖D3所示。
子網(wǎng)之間互聯(lián)允許存在多個(gè)網(wǎng)關(guān)節(jié)點(diǎn),但不允許無限增加。否則,當(dāng)兩個(gè)子網(wǎng)所處地域覆蓋重疊時(shí),每個(gè)節(jié)點(diǎn)都有可能成為網(wǎng)關(guān),不合理地消耗子網(wǎng)間數(shù)據(jù)時(shí)隙資源,阻塞子網(wǎng)內(nèi)數(shù)據(jù)時(shí)隙分配和數(shù)據(jù)通信。子網(wǎng)之間互聯(lián)保持2~3個(gè)網(wǎng)關(guān)節(jié)點(diǎn)比較合理,并且這些網(wǎng)關(guān)節(jié)點(diǎn)間隔至少2跳遠(yuǎn),避免相互競(jìng)爭(zhēng)資源,利于信道的空間復(fù)用。兩個(gè)子網(wǎng)之間的網(wǎng)關(guān)節(jié)點(diǎn)是一一對(duì)應(yīng)的,不能存在一對(duì)多的情況,否則容易出現(xiàn)網(wǎng)關(guān)節(jié)點(diǎn)擁塞現(xiàn)象。抽象網(wǎng)絡(luò)拓?fù)鋵⒆泳W(wǎng)內(nèi)所有節(jié)點(diǎn)都抽象為距離網(wǎng)關(guān)節(jié)點(diǎn)一跳距離。抽象網(wǎng)絡(luò)拓?fù)浔磉_(dá)的跳數(shù)“距離”信息與子網(wǎng)內(nèi)路由的跳數(shù)“距離”不對(duì)等,不能合并等同在一起計(jì)算路由,否則可能產(chǎn)生路由環(huán)路??梢哉J(rèn)為,子網(wǎng)間通信的代價(jià)遠(yuǎn)高于子網(wǎng)內(nèi)通信。
網(wǎng)關(guān)節(jié)點(diǎn)選取遵循的原則如下:
(1)為了避免擁塞,同一個(gè)節(jié)點(diǎn)通常情況下只能作為特定兩個(gè)子網(wǎng)之間的網(wǎng)關(guān),而不能同時(shí)作為三個(gè)或是更多個(gè)子網(wǎng)之間的網(wǎng)關(guān)。
(2)兩個(gè)子網(wǎng)之間保持一定合理數(shù)量的網(wǎng)關(guān)節(jié)點(diǎn),并且網(wǎng)關(guān)節(jié)點(diǎn)之間最好間隔2跳距離,利于信道的空間復(fù)用。
(3)網(wǎng)關(guān)節(jié)點(diǎn)選取采取分布式設(shè)計(jì),通過啟發(fā)式算法決定一個(gè)節(jié)點(diǎn)在普通節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)之間動(dòng)態(tài)轉(zhuǎn)換身份。
(4)在快速拓?fù)渥儞Q條件下,網(wǎng)關(guān)節(jié)點(diǎn)選取需要盡量選擇能夠提供穩(wěn)定的子網(wǎng)間鏈路的節(jié)點(diǎn),否則不利于網(wǎng)絡(luò)的收斂和可靠通信。
網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有機(jī)會(huì)在NiB時(shí)隙(子網(wǎng)間鄰居節(jié)點(diǎn)控制時(shí)隙)中廣播發(fā)送控制消息。通過偵聽接收NiB消息,節(jié)點(diǎn)可以獲得周圍一跳可達(dá)范圍內(nèi)其他子網(wǎng)的存在情況。當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)周圍有穩(wěn)定的其他子網(wǎng)節(jié)點(diǎn)存在時(shí),則節(jié)點(diǎn)具備成為網(wǎng)關(guān)節(jié)點(diǎn)的前提條件。這時(shí),節(jié)點(diǎn)需要判斷當(dāng)前子網(wǎng)中是否存在多個(gè)連接該子網(wǎng)的網(wǎng)關(guān)。由于子網(wǎng)中已經(jīng)運(yùn)行了先應(yīng)式路由協(xié)議,因此節(jié)點(diǎn)自然掌握了所在子網(wǎng)的完整網(wǎng)絡(luò)拓?fù)湫畔??;谒莆盏耐負(fù)湫畔⒁约熬W(wǎng)關(guān)在子網(wǎng)內(nèi)的通告,節(jié)點(diǎn)可以準(zhǔn)確獲知當(dāng)前網(wǎng)絡(luò)中有多少個(gè)網(wǎng)關(guān)節(jié)點(diǎn),以及這些網(wǎng)關(guān)節(jié)點(diǎn)距離自己的跳數(shù)等。
網(wǎng)關(guān)節(jié)點(diǎn)選取的算法過程設(shè)計(jì)如圖4所示。其中,持續(xù)監(jiān)測(cè)時(shí)間Tstab目的在于保證網(wǎng)關(guān)跨子網(wǎng)通信鏈路的穩(wěn)定性。
圖4 網(wǎng)關(guān)節(jié)點(diǎn)選取算法
如果具備成為網(wǎng)關(guān)節(jié)點(diǎn)條件的普通節(jié)點(diǎn)發(fā)現(xiàn)子網(wǎng)內(nèi)網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量不足,且自身所處網(wǎng)絡(luò)位置與現(xiàn)有網(wǎng)關(guān)節(jié)點(diǎn)的距離跳數(shù)大于2跳,則節(jié)點(diǎn)從普通節(jié)點(diǎn)身份轉(zhuǎn)換為網(wǎng)關(guān)節(jié)點(diǎn),并向網(wǎng)絡(luò)中通報(bào)連接可達(dá)的子網(wǎng)的抽象鏈路狀態(tài)更新信息。
本文使用OPNET Modeler 14.5.A仿真軟件建立網(wǎng)絡(luò)模型,仿真場(chǎng)景為20 km×20 km的區(qū)域內(nèi)放置32~128個(gè)節(jié)點(diǎn),假定所有節(jié)點(diǎn)都已完成外同步,節(jié)點(diǎn)間隨機(jī)形成最大跳數(shù)為8的網(wǎng)絡(luò)。
仿真中,各節(jié)點(diǎn)的仿真模型均相同,物理層采用自由空間模型[9],鏈路層采用TDMA(Time Division Multiple Access)分時(shí)復(fù)用傳輸機(jī)制,信道被劃分為子幀和時(shí)幀,連續(xù)的3個(gè)子幀聯(lián)合并在一起構(gòu)成一個(gè)時(shí)幀,一個(gè)子幀的時(shí)間為46.875 ms,子幀中每個(gè)時(shí)隙的長度約0.937 5 ms,每個(gè)子幀共計(jì)劃分50個(gè)時(shí)隙,包括控制時(shí)隙和數(shù)據(jù)時(shí)隙。根據(jù)控制時(shí)隙具體用途的不同,控制時(shí)隙具體又分為:NiB時(shí)隙、CNiB時(shí)隙。根據(jù)鏈路層時(shí)幀結(jié)構(gòu)設(shè)計(jì),仿真中TDMA參數(shù)配置如表1所示。
表1 鏈路層參數(shù)配置
網(wǎng)絡(luò)層路由協(xié)議基本參數(shù)配置如表2所示。
表2 路由協(xié)議基本參數(shù)配置
為了對(duì)CLOLSR協(xié)議進(jìn)行性能評(píng)估,在完全相同的參數(shù)配置情況下,本文將CLOLSR協(xié)議與傳統(tǒng)OLSR協(xié)議從初始建網(wǎng)時(shí)間、鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間、網(wǎng)絡(luò)局部變化收斂時(shí)間、平均路由開銷和平均一跳端到端時(shí)延五個(gè)方面進(jìn)行仿真對(duì)比。
圖5是兩種協(xié)議128節(jié)點(diǎn)初始建網(wǎng)時(shí)間對(duì)比圖,為了研究網(wǎng)絡(luò)收斂情況,配置網(wǎng)絡(luò)中所有節(jié)點(diǎn)位于初始位置不動(dòng)。從圖5中可以看出,CLOLSR路由協(xié)議的初始建網(wǎng)時(shí)間遠(yuǎn)小于OLSR路由協(xié)議,只有后者的二分之一左右,這主要是因?yàn)镃LOLSR路由協(xié)議采用了劃分多子網(wǎng)的方式,每個(gè)子網(wǎng)可以迅速完成收斂,且利用子網(wǎng)間的路由抽象完成整個(gè)網(wǎng)絡(luò)的建立,相對(duì)于OLSR路由協(xié)議需要等到探測(cè)消息擴(kuò)散至全網(wǎng)才能完成網(wǎng)絡(luò)的收斂,CLOLSR路由協(xié)議的初始建網(wǎng)時(shí)間要快很多。
圖5 128節(jié)點(diǎn)初始建網(wǎng)時(shí)間
圖6 是兩種協(xié)議的鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間對(duì)比圖,從圖6中可以看出,在同樣的條件下,CLOLSR路由協(xié)議的鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間小于OLSR路由協(xié)議,這是由于CLOLSR協(xié)議利用了鏈路層設(shè)計(jì)的基于鄰居節(jié)點(diǎn)控制時(shí)隙(NiB/CNiB)的交互,通過節(jié)點(diǎn)之間在每個(gè)鄰居節(jié)點(diǎn)控制時(shí)隙周期內(nèi)周期性的交互,可以快速實(shí)現(xiàn)鄰居發(fā)現(xiàn),而OLSR路由協(xié)議則只能通過自身發(fā)送Hello消息,通過底層傳輸?shù)竭_(dá)對(duì)端,再收到回復(fù)后才能實(shí)現(xiàn)鄰居發(fā)現(xiàn),因此鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間要慢一些。
圖6 鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間
為了測(cè)試網(wǎng)絡(luò)局部變化收斂時(shí)間,設(shè)定拓?fù)渥兓鐖D7中拓?fù)?變?yōu)橥負(fù)?,通過觀察路由表變化,測(cè)量子網(wǎng)收斂時(shí)間大小。
圖7 網(wǎng)絡(luò)局部變化示意圖
兩種協(xié)議的測(cè)量結(jié)果如圖8所示,從圖8中可以看出,對(duì)于圖7所示的網(wǎng)絡(luò)局部變化,CLOLSR路由協(xié)議基本可以將收斂時(shí)間控制在1 s左右,OLSR路由協(xié)議則普遍需要2.5 s以上,這是因?yàn)镃LOLSR協(xié)議利用鏈路層的快速鄰居發(fā)現(xiàn)機(jī)制迅速的完成了一跳和兩跳鄰居的探測(cè),對(duì)于距離兩跳以上的節(jié)點(diǎn),只需要收到TC消息即可建立路由,對(duì)于OLSR協(xié)議,則需要首先利用Hello消息獲知一跳和兩跳鄰居信息,然后通過選舉出的MPR節(jié)點(diǎn)發(fā)送TC消息獲知到達(dá)兩跳以外節(jié)點(diǎn)的路由。因此,網(wǎng)絡(luò)局部變化收斂時(shí)間較長。
圖8 網(wǎng)絡(luò)局部變化收斂時(shí)間
圖9 是兩種協(xié)議的32節(jié)點(diǎn)網(wǎng)絡(luò)平均路由開銷對(duì)比圖。從圖9中可以看出,網(wǎng)絡(luò)建立伊始,由于網(wǎng)絡(luò)尋路需求較大,控制開銷發(fā)送頻繁,平均路由開銷較高,但隨著通信鏈路的陸續(xù)建立,控制消息的發(fā)送需求也隨之下降,因此平均路由開銷逐漸降低,此后平均路由開銷只在有限范圍內(nèi)波動(dòng)。CLOLSR協(xié)議平均路由開銷始終要低于OLSR協(xié)議,這是因?yàn)镃LOLSR協(xié)議取消了Hello消息,而使用鏈路層上報(bào)的鄰居信息來替代,從而降低了平均路由開銷,節(jié)省了帶寬資源。
圖10是兩種協(xié)議的平均一跳數(shù)據(jù)端到端延時(shí)對(duì)比圖,測(cè)試數(shù)據(jù)包長度為512字節(jié)。從圖10中可以看出,兩者的延時(shí)相差不大,基本保持一致,說明CLOLSR路由協(xié)議在協(xié)議本身的性能和開銷上有優(yōu)化,在一定程度上緩解了網(wǎng)絡(luò)擁塞,但是在網(wǎng)絡(luò)整體業(yè)務(wù)流量較低的情況下,鏈路建立之后,對(duì)于業(yè)務(wù)數(shù)據(jù)的傳輸延時(shí)改善不大。
圖9 32節(jié)點(diǎn)網(wǎng)絡(luò)平均路由開銷
圖10 平均一跳數(shù)據(jù)端到端延時(shí)
本文為了提升OLSR 協(xié)議在高實(shí)時(shí)性大規(guī)模組網(wǎng)條件下網(wǎng)絡(luò)的整體性能,提出了基于鏈路層的快速鄰居發(fā)現(xiàn)和網(wǎng)管節(jié)點(diǎn)選舉、子網(wǎng)間路由抽象兩點(diǎn)改進(jìn)意見。并將CLOLSR協(xié)議與OLSR協(xié)議進(jìn)行了仿真對(duì)比,結(jié)果表明:CLOLSR協(xié)議不僅在初始建網(wǎng)時(shí)間、鄰居節(jié)點(diǎn)發(fā)現(xiàn)時(shí)間、網(wǎng)絡(luò)局部變化收斂時(shí)間等網(wǎng)絡(luò)性能指標(biāo)上有較大提升,還降低了網(wǎng)絡(luò)平均路由開銷,在大規(guī)模自組織網(wǎng)絡(luò)中具有一定的應(yīng)用前景。