李　昕　周劍剛　李　珂　李　玲

【摘要】路由技術(shù)是無線自組織網(wǎng)絡(luò)組網(wǎng)的基礎(chǔ)和關(guān)鍵環(huán)節(jié)。文章介紹了當(dāng)前無線自組織網(wǎng)絡(luò)路由技術(shù)研究的現(xiàn)狀,在此基礎(chǔ)上,詳述了無線自組織網(wǎng)絡(luò)中具有代表性的路由協(xié)議,并對這一領(lǐng)域未來的發(fā)展趨勢作了展望。

【關(guān)鍵詞】無線自組織網(wǎng)絡(luò) 路由技術(shù) 路由重建 路由修復(fù) CBRP

1 引言

無線自組織網(wǎng)絡(luò)具有無基礎(chǔ)設(shè)施依托、臨時(shí)組建、拓?fù)鋭討B(tài)變化、節(jié)點(diǎn)能力有限等特點(diǎn),用于為地理上相鄰但散布區(qū)域超過單個(gè)節(jié)點(diǎn)無線傳輸范圍的一組節(jié)點(diǎn)之間提供信息傳遞服務(wù)。這一需求首先來自軍事領(lǐng)域,以美國國防部相繼推出的PRNET(Packet Radio Network)、SURAN(Survivable Adaptive Radio Networks)以及全球移動信息系統(tǒng)(GloMo)計(jì)劃為代表。無線自組織網(wǎng)絡(luò)研究在民用領(lǐng)域的興起始于上世紀(jì)90年代,以無線通信技術(shù)的快速發(fā)展以及便攜、小型化的計(jì)算設(shè)備的迅速普及為契機(jī)。無論是在軍用還是民用領(lǐng)域,路由技術(shù)都是無線自組織網(wǎng)絡(luò)組網(wǎng)的基礎(chǔ)和關(guān)鍵環(huán)節(jié),因此受到長期的關(guān)注和研究。本文將對這一領(lǐng)域的研究現(xiàn)狀作較為深入的分析和介紹,并對其發(fā)展趨勢進(jìn)行展望。

2 無線自組織網(wǎng)絡(luò)路由技術(shù)研究現(xiàn)狀

路由協(xié)議開發(fā)是無線自組織網(wǎng)絡(luò)研究領(lǐng)域最具挑戰(zhàn)性的工作之一,除了必須適應(yīng)無線信道特性以外,還需面臨網(wǎng)絡(luò)環(huán)境與網(wǎng)絡(luò)拓?fù)渥兓療o常、節(jié)點(diǎn)資源有限等問題,并需要特別考慮無線通信物理層和MAC層特性對網(wǎng)絡(luò)層的影響。

早期的無線自組織網(wǎng)絡(luò)路由技術(shù)研究仍然承襲了來自固定網(wǎng)的基本思路,把路由查詢建立在對全網(wǎng)路由信息精確掌握的基礎(chǔ)之上,并將控制平面與數(shù)據(jù)平面分離。但由于無線自組織網(wǎng)絡(luò)穩(wěn)態(tài)持續(xù)時(shí)間很短,有時(shí)甚至在很長時(shí)間內(nèi)無法進(jìn)入穩(wěn)態(tài),因此早期的研究者不得不面對這樣一種困境:提高拓?fù)湫畔⒏碌乃俣缺厝灰鹁薮蟮木W(wǎng)絡(luò)開銷以及頻繁的路由震蕩,而要克服這兩個(gè)問題又必須以犧牲路由選擇的準(zhǔn)確性為代價(jià)。

針對無線自組織網(wǎng)絡(luò)的特性,目前在路由技術(shù)研究領(lǐng)域有兩種主流的解決方案:

(1)仍然將控制平面與數(shù)據(jù)平面分離,但不保證路由表具備100%的準(zhǔn)確性和實(shí)時(shí)性,這一類型的協(xié)議包括ZRP[1]、FSR[2]、CBRP[3]等;

(2)將控制平面與數(shù)據(jù)平面融合,以數(shù)據(jù)流觸發(fā)路由查找過程,以提高路由查詢開銷為代價(jià)換取路由信息的實(shí)時(shí)性,代表性的協(xié)議有AODV[4]、DSR[5]。

3 現(xiàn)有解決方案

3.1 改進(jìn)的傳統(tǒng)路由協(xié)議

在無線自組織網(wǎng)絡(luò)路由協(xié)議研究的早期,通過改進(jìn)傳統(tǒng)路由協(xié)議以滿足無線自組織網(wǎng)絡(luò)組網(wǎng)的需求受到極高的關(guān)注。盡管此類研究的最終結(jié)果并不理想,但卻有助于人們認(rèn)識無線自組織網(wǎng)絡(luò)中路由查詢所面臨的主要問題。

此類協(xié)議包括目的端賦序的距離矢量路由協(xié)議[6](DSDV,Destination-Sequenced Distance-Vector Routing)、群首網(wǎng)關(guān)交換路由協(xié)議[3](CGSR,Clusterhead Gateway Switch Routing)以及魚眼路由協(xié)議(FSR,Fisheye State Routing Protocol)。前兩種協(xié)議以距離矢量路由算法為核心,采用比水平分割毒性逆轉(zhuǎn)更為有效的環(huán)路避免機(jī)制,并通過控制路由控制信息的數(shù)量來減少開銷,兩者的區(qū)別僅僅在于廣播拓?fù)渥兏畔⒌姆绞揭约斑\(yùn)行協(xié)議所需路由表的數(shù)量有所不同。FSR則屬于鏈路狀態(tài)路由協(xié)議,采用Dijkstra算法進(jìn)行選路。

采用距離矢量路由算法的協(xié)議通過維護(hù)和使用全網(wǎng)一致的路由表,在網(wǎng)絡(luò)拓?fù)渥兓徛?、?jié)點(diǎn)數(shù)量不大的情況下,通常能夠獲得較高的路由轉(zhuǎn)發(fā)效率;但仍然存在開銷過大和可擴(kuò)展性差的問題,不能適應(yīng)動態(tài)性較強(qiáng)的網(wǎng)絡(luò)環(huán)境。FSR協(xié)議的工作原理與OSPF較為相似,不同之處在于FSR通過在鏈路狀態(tài)信息廣播的范圍(以廣播源為圓心,若干跳為半徑)與廣播的周期之間建立正比的關(guān)系來限制網(wǎng)絡(luò)中鏈路狀態(tài)信息的數(shù)量,其代價(jià)則是使距離較遠(yuǎn)的節(jié)點(diǎn)之間交換鏈路狀態(tài)信息的頻率很低,無法保證全網(wǎng)路由信息的一致性。

3.2 按需驅(qū)動的路由協(xié)議

脫胎于固定網(wǎng)絡(luò)的設(shè)計(jì)思想最終沒有成為主流,更多的研究者徹底放棄了傳統(tǒng)的設(shè)計(jì)原則,將控制平面與數(shù)據(jù)平面融合,采用按需驅(qū)動路由查找方式[4,5]。源端發(fā)起按需驅(qū)動路由協(xié)議與表驅(qū)動路由協(xié)議最重要的差異就在于前者從不主動發(fā)布和收集網(wǎng)絡(luò)拓?fù)湫畔?也不維護(hù)全網(wǎng)一致的路由表作為轉(zhuǎn)發(fā)依據(jù)。只有在有數(shù)據(jù)需要傳輸?shù)臅r(shí)候,路由器才主動發(fā)起到目的地的路由查找過程,以較長的(相對于固定網(wǎng)絡(luò)中表驅(qū)動的路由協(xié)議而言)路由搜尋時(shí)間為代價(jià),換取在特定時(shí)間和特定場景下較為精確的局部路由信息。

為了對付隨時(shí)可能發(fā)生的路由中斷,按需驅(qū)動路由協(xié)議通常采用兩種路由維護(hù)方式:路由重建與路由修復(fù)。路由重建即當(dāng)路由中的某一條鏈路發(fā)生中斷時(shí),源端路由器重新通過全網(wǎng)廣播方式尋找路由。路由修復(fù)即在鏈路中斷發(fā)生時(shí),由中斷鏈路的上游節(jié)點(diǎn)發(fā)起尋找下游節(jié)點(diǎn)或目的節(jié)點(diǎn)。路由修復(fù)曾經(jīng)一度是無線自組織網(wǎng)絡(luò)路由協(xié)議研究領(lǐng)域的一個(gè)熱點(diǎn),但最終路由重建方式得到了廣泛的認(rèn)可。其中的原因在于,無線自組織網(wǎng)絡(luò)中,某一條路由的強(qiáng)壯性會隨著路由中鏈路數(shù)量的增加而出現(xiàn)指數(shù)級遞減,路由修復(fù)盡管能夠解決局部的路由重建問題,但卻有可能令路由強(qiáng)壯性下降。而且,路由修復(fù)方式僅適合于解決路由中的單鏈路失效問題,當(dāng)一條路由中的多條鏈路同時(shí)或相繼中斷時(shí),便無法發(fā)揮應(yīng)有效能。

按需驅(qū)動的路由協(xié)議種類較多,比較有代表性的包括Ad-Hoc按需距離矢量路由協(xié)議(AODV,Ad-Hoc On-Demand Distance Vector Routing)、動態(tài)源路由協(xié)議(DSR,Dynamic Source Routing)、基于相關(guān)性的路由協(xié)議(ABR,Associativity-Based Routing)、基于群組的路由協(xié)議[7](CBRP,Cluster-Based Routing Protocol)等。AODV采用與DSDV相同的選路和環(huán)路避免機(jī)制,其改進(jìn)之處在于完全按需搜索路由并只要求數(shù)據(jù)轉(zhuǎn)發(fā)路徑上的路由器保存和更新與該路徑有關(guān)的路由信息。DSR和AODV最大的區(qū)別就在于采用了源路由的方式,這使DSR可以使用單向無線鏈路構(gòu)成非對稱的往返路徑,具有比AODV更大的靈活性,但這樣做的代價(jià)則是增加了每個(gè)數(shù)據(jù)包的開銷。

ABR[8]的特別之處在于采用了與AODV和DSR完全不同的度量值——聯(lián)系穩(wěn)定度(degree of association stability)作為路由選擇的依據(jù)。聯(lián)系度的值越低,就表明相應(yīng)節(jié)點(diǎn)的移動性越強(qiáng),鏈路狀態(tài)越不穩(wěn)定。因此,ABR所選擇的路由穩(wěn)定性最好,但有可能不是跳數(shù)最少的。

前面提到的幾種路由協(xié)議都采用扁平結(jié)構(gòu),優(yōu)點(diǎn)是較為靈活,缺點(diǎn)則表現(xiàn)為不能在大規(guī)模的網(wǎng)絡(luò)中進(jìn)行擴(kuò)展。CBRP是一種分層式的路由協(xié)議,通過在網(wǎng)絡(luò)中建立自發(fā)的群組來克服這種不足。在運(yùn)行CBRP的網(wǎng)絡(luò)中,節(jié)點(diǎn)被劃分為三類:群組首節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)和普通節(jié)點(diǎn)。群組首節(jié)點(diǎn)通過某種機(jī)制(例如在一組相鄰節(jié)點(diǎn)中選舉路由器ID最大者或與其他路由器連接性最佳者為群組首節(jié)點(diǎn))在某一特定范圍內(nèi)(例如一跳或兩跳半徑范圍內(nèi))的相鄰節(jié)點(diǎn)中選舉產(chǎn)生,群組首節(jié)點(diǎn)ID即作為該群組的標(biāo)識符。為了維護(hù)群組的結(jié)構(gòu),每個(gè)節(jié)點(diǎn)定期向其鄰居廣播HELLO信息,其中包括本節(jié)點(diǎn)的狀態(tài)、鄰居列表以及與之相鄰的群組首節(jié)點(diǎn)列表。在路由查找的過程中,只有群組首節(jié)點(diǎn)執(zhí)行泛洪式搜索的功能,網(wǎng)關(guān)節(jié)點(diǎn)僅僅負(fù)責(zé)將收到的路由查詢信息轉(zhuǎn)發(fā)給鄰近的群組首節(jié)點(diǎn),不對外進(jìn)行廣播。在CBRP中,群組首節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)共同構(gòu)成了一個(gè)類似于骨干的網(wǎng)絡(luò),從而有效地降低了路由查找的復(fù)雜性。