ＡｄＨｏｃ網(wǎng)絡(luò)路由技術(shù)

摘要：無線自組織網(wǎng)絡(luò)(Ad hoc)是一個(gè)復(fù)雜的系統(tǒng)，其中路由協(xié)議是該領(lǐng)域中的研究熱點(diǎn)。通過采用合理的路由技術(shù)，可使無線自組網(wǎng)具有更為靈活的組網(wǎng)方式，從而達(dá)到提升網(wǎng)絡(luò)性能、減少網(wǎng)絡(luò)開銷等目的。通過與認(rèn)知無線電(CR)技術(shù)、協(xié)同通信(CC)技術(shù)以及多輸入多輸出(MIMO)天線技術(shù)等物理層新技術(shù)的有效結(jié)合，可以大大改善Ad hoc路由協(xié)議的性能。

關(guān)鍵詞：自組織網(wǎng)絡(luò)；路由協(xié)議；無線通信

Abstract: Wireless Ad hoc network is a complicated communication system， and its routing technology is one of the most popular and active research topics. Efficient routing protocol enables wireless networks to be more flexibly organized， improving network performance and decreasing overheads. Combining novel technologies at the physical layer， such as Cognitive Radio (CR)， Cooperative Communication (CC)， and Multiple Input Multiple Output (MIMO)， can hugely enhance the performance of Ad hoc routing protocols.

Key words: Ad hoc network; routing protocol; wireless communication

未來移動(dòng)通信網(wǎng)絡(luò)除了以低成本達(dá)到高數(shù)據(jù)率外，還要求網(wǎng)絡(luò)組網(wǎng)靈活，具有適應(yīng)性和生存能力。無線自組織網(wǎng)絡(luò)(Ad hoc)[1-4]是一種沒有預(yù)定的基礎(chǔ)設(shè)施支撐的自組織可重構(gòu)的多跳無線網(wǎng)絡(luò)，可以作為蜂窩移動(dòng)網(wǎng)絡(luò)的有效加強(qiáng)。因此，移動(dòng)自組織網(wǎng)絡(luò)將因其靈活性而在未來移動(dòng)通信網(wǎng)絡(luò)中扮演重要作用。

1 Ad Hoc網(wǎng)絡(luò)路由協(xié)議

Ad hoc網(wǎng)絡(luò)中，由于通信半徑的限制，網(wǎng)絡(luò)節(jié)點(diǎn)之間是通過多跳數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制進(jìn)行數(shù)據(jù)交互的，需要路由協(xié)議完成分組轉(zhuǎn)發(fā)決策。與傳統(tǒng)路由協(xié)議相比，Ad hoc路由協(xié)議的設(shè)計(jì)面臨著網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化、帶寬受限、信道容量變化、移動(dòng)終端有限的可用資源等新的問題和挑戰(zhàn)。

早在1996年，因特網(wǎng)工程任務(wù)組(IETF)就成立了移動(dòng)Ad hoc網(wǎng)絡(luò)工作小組(MANET WG)，其核心任務(wù)就是研究無線自組織網(wǎng)絡(luò)環(huán)境下基于IP協(xié)議的路由協(xié)議規(guī)范和接口設(shè)計(jì)。IETF RFC2501詳細(xì)給出了無線Ad hoc網(wǎng)絡(luò)的應(yīng)用場合、特征和性能要求。目前，MANET WG已經(jīng)公布了一系列的有關(guān)Ad hoc路由的草案，如動(dòng)態(tài)源路由算法(DSR)、基于反向路徑轉(zhuǎn)發(fā)的拓?fù)浞职l(fā)協(xié)議(TBRPF)、優(yōu)化鏈路狀態(tài)路由算法(OLSR)、按需距離矢量路由算法(AODV)、臨時(shí)按序路由算法(TORA)、區(qū)域路由算法(ZRP)；此外，研究還提出了許多Ad hoc路由協(xié)議，如目的序列距離矢量路由算法(DSDV)、無線路由協(xié)議(WRP)、陸標(biāo)路由協(xié)議(LANMAR)、位置輔助路由(LAR)、魚眼狀態(tài)路由算法(FSR)。

這些路由協(xié)議根據(jù)所采用的基本路由機(jī)制的不同，可分為基于鏈路狀態(tài)的路由協(xié)議、基于距離矢量的路由協(xié)議、源路由協(xié)議及反向鏈路協(xié)議；按照網(wǎng)絡(luò)邏輯結(jié)構(gòu)的不同，可分為平面結(jié)構(gòu)的路由協(xié)議和分層結(jié)構(gòu)的路由協(xié)議；按照路由發(fā)現(xiàn)策略的不同，可分為表驅(qū)動(dòng)路由協(xié)議、按需路由協(xié)議以及混合路由協(xié)議。

2 大規(guī)模Ad Hoc網(wǎng)絡(luò)中的路由技術(shù)

Ad hoc網(wǎng)絡(luò)規(guī)模性[5]的研究可以廣義地定義為：研究當(dāng)網(wǎng)絡(luò)中有大量節(jié)點(diǎn)存在時(shí)，網(wǎng)絡(luò)能否為分組提供可以接受的服務(wù)，它與網(wǎng)絡(luò)大小、節(jié)點(diǎn)分布的密度、運(yùn)行的環(huán)境(傳播模型、地型環(huán)境等)及移動(dòng)性相關(guān)。

對(duì)于中小規(guī)模(通常為幾十個(gè)節(jié)點(diǎn))Ad hoc網(wǎng)絡(luò)路由協(xié)議的研究已取得了重要進(jìn)展，而大規(guī)模Ad hoc網(wǎng)絡(luò)的路由技術(shù)是Ad hoc網(wǎng)絡(luò)研究的一個(gè)難點(diǎn)，它是指可以支持?jǐn)?shù)百到數(shù)千個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的路由算法。國際上早期的一些初步研究結(jié)果[6]，如Santivanez等人提出的基于鏈路狀態(tài)法的模糊鏈路狀態(tài)(FSLS)算法，研究了節(jié)點(diǎn)數(shù)為100～400時(shí)的部分性能；Woo和Singh提出了一個(gè)基于位置修正的SLURP算法，研究了節(jié)點(diǎn)數(shù)為50～1 000時(shí)的算法性能；Jinying Li等提出了基于區(qū)域的網(wǎng)格(Grid)系統(tǒng)，研究了100～600個(gè)節(jié)點(diǎn)時(shí)的算法性能；Rahul Jain等人提出了基于地理位置的路由算法，研究10～1000個(gè)節(jié)點(diǎn)的算法性能。

現(xiàn)有的路由協(xié)議或者利用全網(wǎng)泛洪(Global flooding)或者利用分層的方法完成路由的發(fā)現(xiàn)。但是，前者由于開銷太大并不適合大規(guī)模的網(wǎng)絡(luò)；后者在分層的過程中需要交互大量信息，而且可能由于節(jié)點(diǎn)的移動(dòng)造成性能的急劇惡化。為了克服這些缺陷Nitin Nahata等人提出了一種基于連接(Contact)點(diǎn)的適用于大規(guī)模Ad hoc網(wǎng)絡(luò)的高效的路由發(fā)現(xiàn)策略[7]。它基于“小世界(Small world)”的概念，采用了一種混合的方式：在節(jié)點(diǎn)的R跳(通常是3～5跳)范圍內(nèi)采用先驗(yàn)式的路由算法，如DSDV，而在R跳以外通過Contact點(diǎn)進(jìn)行反應(yīng)式的路由發(fā)現(xiàn)。Contact點(diǎn)是一些捷徑點(diǎn)，它通過減小分割度來把網(wǎng)絡(luò)劃分成為一些“小世界”。圖1所示為這個(gè)過程的示例。

此外，Taejoon Park等人還提出了一種基于地理位置的適用于Ad hoc網(wǎng)絡(luò)的路由協(xié)議[8]，它在節(jié)點(diǎn)本地區(qū)域和分布區(qū)域中結(jié)合了位置更新機(jī)制，同時(shí)還根據(jù)位置更新門限得到一個(gè)最優(yōu)的配置，以此減小總的路由開銷。該協(xié)議具有可擴(kuò)展性，并且路由開銷較小，從而延長了節(jié)點(diǎn)的壽命。

3 基于新物理層技術(shù)的Ad Hoc路由

為了滿足人們?nèi)找嬖鲩L的通信需求，能夠提供更大帶寬的物理層傳輸技術(shù)層出不窮，如認(rèn)知無線電技術(shù)、協(xié)同通信技術(shù)以及多輸入多輸出(MIMO)天線技術(shù)等。它們的出現(xiàn)為Ad hoc網(wǎng)絡(luò)路由技術(shù)的進(jìn)一步發(fā)展帶來新的契機(jī)。

3.1 基于認(rèn)知無線電的路由協(xié)議

眾所周知，頻譜資源十分有限，一些非授權(quán)頻段占用擁擠，而那些授權(quán)頻段卻經(jīng)常空閑，因此，可以考慮在授權(quán)用戶不用自己的頻率資源時(shí)，讓一些非授權(quán)用戶去暫時(shí)性地有效利用該空閑頻譜，認(rèn)知無線電[9]就是基于這種想法提出來的一種更智能的頻譜共享技術(shù)，它可以感知無線通信環(huán)境，依據(jù)一定的學(xué)習(xí)和決策算法，動(dòng)態(tài)地檢測和有效地利用空閑頻譜，大大降低了頻譜和帶寬對(duì)無線技術(shù)發(fā)展的束縛。它要求非授權(quán)用戶和授權(quán)用戶在對(duì)頻譜資源利用時(shí)達(dá)到一個(gè)平衡，使得非授權(quán)用戶能在不影響授權(quán)用戶的前提下進(jìn)行一些自己的通信。

認(rèn)知無線電技術(shù)的特點(diǎn)使得節(jié)點(diǎn)間的鏈路可能經(jīng)常發(fā)生變化，因此，這樣的路由協(xié)議首先應(yīng)該是魯棒的(Robustness)，這種魯棒性是基于多路徑分析的。多一條備選的路由可以大大降低一條路徑失效對(duì)網(wǎng)絡(luò)造成的影響，使得網(wǎng)絡(luò)具備魯棒性。此外，這樣的路由協(xié)議還應(yīng)滿足3點(diǎn)要求[10]：

(1)路由協(xié)議應(yīng)該是先驗(yàn)式的

如果采用了反應(yīng)式的路由協(xié)議，更新路由表太浪費(fèi)時(shí)間，分組若要以最小的時(shí)延傳輸就需要采用先驗(yàn)式的路由算法。但是，先驗(yàn)式路由協(xié)議會(huì)引入更多的控制分組數(shù)，而且路由信息的不斷更新反而會(huì)縮短節(jié)點(diǎn)能量的持續(xù)時(shí)間。

(2)路由協(xié)議應(yīng)該是基于鏈路狀態(tài)的

由于物理層的參數(shù)經(jīng)常變化，節(jié)點(diǎn)的移動(dòng)性及傳輸半徑也可能改變，節(jié)點(diǎn)的認(rèn)知能力也有所差異，因此，節(jié)點(diǎn)間的鏈路可以通過計(jì)算鏈路的可靠性來進(jìn)行選擇。

(3)路由協(xié)議應(yīng)該是分級(jí)的

分級(jí)的路由協(xié)議支持不同的移動(dòng)組。目前認(rèn)知無線電環(huán)境下，以信道的切換次數(shù)以及信道的切換頻率為衡量標(biāo)準(zhǔn)，已經(jīng)有基于控制信道的路由算法以及基于空時(shí)分組碼的路由算法。

3.2 基于協(xié)同通信的路由協(xié)議

協(xié)同通信[11-13]利用節(jié)點(diǎn)間的相互協(xié)作進(jìn)行數(shù)據(jù)通信。它充分利用了無線電波的全向傳播特性，使無線網(wǎng)絡(luò)中的節(jié)點(diǎn)相互協(xié)作形成了虛擬的天線陣列來獲得傳統(tǒng)多輸入多輸出天線技術(shù)的空間分集增益，當(dāng)前協(xié)同通信的主要方式有：編碼協(xié)同，放大中繼，解碼中繼等方式。相對(duì)于其他協(xié)同方式，編碼協(xié)同方式將協(xié)同通信技術(shù)和信道編碼技術(shù)相結(jié)合，在不消耗更多系統(tǒng)資源(帶寬等)的前提下獲得完全的分集增益。圖2所示為協(xié)同路由和一般多跳路由的區(qū)別。

當(dāng)有從S節(jié)點(diǎn)到D節(jié)點(diǎn)的數(shù)據(jù)要發(fā)送時(shí)，數(shù)據(jù)依靠中間節(jié)點(diǎn)的中繼就會(huì)到達(dá)目的節(jié)點(diǎn)，而對(duì)于協(xié)同路由來說，數(shù)據(jù)可以經(jīng)過S→1→D完成傳輸，同時(shí)，位于節(jié)點(diǎn)S覆蓋范圍內(nèi)的節(jié)點(diǎn)2、3也可以聽到這樣的信息，它們可以不用付出額外的能量去傳輸數(shù)據(jù)，這樣，就可以消耗更小的能量。

目前，基于協(xié)同技術(shù)的路由可大致分為兩類，分別是基于能量的路由策略和基于帶寬的路由策略。基于能量的路由策略[12-13]主要針對(duì)單個(gè)源和目的節(jié)點(diǎn)的應(yīng)用環(huán)境，在保證源節(jié)點(diǎn)發(fā)射信號(hào)在接收節(jié)點(diǎn)處能達(dá)到接收信噪比門限的基礎(chǔ)上，通過為協(xié)同節(jié)點(diǎn)最優(yōu)化地分配功率，從而達(dá)到降低網(wǎng)絡(luò)總能量開銷的目的。基于帶寬[11]的路由策略主要是通過引入?yún)f(xié)同通信技術(shù)，以最大化源節(jié)點(diǎn)到目的節(jié)點(diǎn)間路徑的帶寬為目標(biāo)完成路由決策。協(xié)同技術(shù)在該種路由機(jī)制中主要有兩種應(yīng)用方式[11]。一種是在選擇好一條源到目的節(jié)點(diǎn)路由的基礎(chǔ)上，通過在每一跳節(jié)點(diǎn)間根據(jù)對(duì)帶寬的改善程度有選擇地進(jìn)行協(xié)同，達(dá)到提升路由傳輸能力的目的。這種方式可稱為基于協(xié)同的路由。另一種方式是在路由選擇的同時(shí)就考慮到協(xié)同技術(shù)對(duì)每跳傳輸帶寬的影響，從而決定每跳傳輸是否采用協(xié)同通信技術(shù)，并選擇該情況下帶寬最大的路由進(jìn)行數(shù)據(jù)傳輸。該方式稱為動(dòng)態(tài)協(xié)同路由。

3.3 基于MIMO的路由協(xié)議

MIMO系統(tǒng)利用空分復(fù)用和分集，在不增加額外功率和帶寬的前提下提供高的頻譜利用率，作為智能天線技術(shù)中一個(gè)最復(fù)雜的技術(shù)，MIMO鏈路現(xiàn)在被普遍應(yīng)用，并且已經(jīng)進(jìn)入了無線局域網(wǎng)(WLAN)、WiMAX及Ad hoc領(lǐng)域，與其相關(guān)的路由技術(shù)也是現(xiàn)在研究的一個(gè)熱點(diǎn)問題。

目前基于MIMO的適應(yīng)于無線自組織網(wǎng)絡(luò)的路由協(xié)議并不多見。K.Sundaresan等人在2005年的IEEE 的國際會(huì)議(ICNP)上，發(fā)表了論文《Routing in Ad-Hoc Networks with MIMO Links》[14]。該文給出了一種適應(yīng)于MIMO信道條件的自適應(yīng)路由協(xié)議。該協(xié)議通過利用MIMO系統(tǒng)兩種不同的工作模式：空間復(fù)用和空間分集來實(shí)現(xiàn)路由的自適應(yīng)選擇。在空間復(fù)用模式中，節(jié)點(diǎn)通過每個(gè)天線發(fā)射不同的數(shù)據(jù)流，能夠獲得復(fù)用增益，提高鏈路以及整個(gè)路由的傳輸容量。在空間分集模式中，節(jié)點(diǎn)在每根天線上發(fā)送相同的數(shù)據(jù)流，以獲得分集增益。這種分集技術(shù)能夠有效地提高通信系統(tǒng)的抗干擾能力，降低系統(tǒng)傳輸?shù)恼`比特率，提高鏈路及路由傳輸?shù)目煽啃裕軌驖M足無線信道條件較差環(huán)境的應(yīng)用要求。

4 結(jié)束語

本文綜述了無線Ad hoc網(wǎng)絡(luò)中的主要路由協(xié)議，著重介紹了能夠適應(yīng)大規(guī)模網(wǎng)絡(luò)環(huán)境的Ad hoc網(wǎng)絡(luò)路由協(xié)議及基于新物理層技術(shù)的Ad hoc網(wǎng)絡(luò)路由協(xié)議。這些方法在一定程度上可在不同層面滿足Ad hoc網(wǎng)絡(luò)的路由需求。隨著人們需求的不斷提高，網(wǎng)絡(luò)的規(guī)模化發(fā)展是一個(gè)必然趨勢。如何在大規(guī)模的網(wǎng)絡(luò)中提出更能符合實(shí)際應(yīng)用的路由協(xié)議，并結(jié)合新的物理層技術(shù)實(shí)現(xiàn)網(wǎng)絡(luò)中多種路由協(xié)議的平滑過渡是今后Ad hoc網(wǎng)絡(luò)路由技術(shù)研究的重要方向。

5 參考文獻(xiàn)

[1] Hass Z J， Deng J， Liang B， et al. Wireless Ad hoc networks [M]//Encyclopedia of Telecommunications. New York NY， USA: John Wiley Sons， 2002.

[2] 蘇靜， 郭偉. 無線移動(dòng)自組織網(wǎng)路由協(xié)議綜述 [J]. 中國測試技術(shù)， 2005，31(2):91-93.

[3] 高云全， 孔婷， 鄔家煒. 移動(dòng)Ad hoc網(wǎng)路由協(xié)議綜述 [J]. 科技廣場， 2005(5):40-43.

[4] 史美林， 英春. 自組網(wǎng)路由協(xié)議綜述 [J]. 通信學(xué)報(bào)， 2001，22(11):93-103.

[5] 李建東. 大規(guī)模無線移動(dòng)Ad hoc網(wǎng)絡(luò) [J]. 深圳大學(xué)學(xué)報(bào): 理工版， 2004，21(4):283-286.

[6] LI J. Overview on scalability of routing protocols for mobile Ad hoc networks [D]. New York， NY， USA: Cornell University， 2003.

[7] Nahata N， Pamu P， et al. Efficient resource discovery for large scale Ad hoc networks using contacts [EB/OL]. http://nile.usc.edu/ee499/contacts.

[8] Park T， Shin K G. Optimal tradeoffs for location-based routing in large-scale Ad hoc networks [J]. IEEE/ACM Transmissions on Networking， 2005，13(2):398-410.

[9] 郭彩麗， 張?zhí)炜? 認(rèn)知無線電關(guān)鍵技術(shù)及應(yīng)用的研究現(xiàn)狀 [J]. 現(xiàn)代電信科技， 2006(6):29-34.

[10] Pawecza P. Protocol requirements for cognitive radio networks [EB/OL]. 2005-07-20. https://doc.freeband.nl/dscgi/ds.py/Get/File-60831.

[11] Beres E， Adve R S. Cooperation and routing in multi-hop networks [C]// Proceedings IEEE International Conference on Communications， Jun 24-27， 2007， Scotland， UK.

[12] Xie Fang， Tian Hui， Zhang Ping， et al. Cooperative routing strategies in Ad hoc networks [C]// Proceedings of 61st Vehicular Technology Conference: Vol 4， May 30-Jun 1，2005， Stockholm， Sweden. Piscataway， NJ， USA: IEEE，2005:2509-2512.

[13] Khandani A， Abounadi J， Modiano e， et al. Cooperative routing in wireless networks [C]// Proceedings of Allerton Conference on Communications， Control and Computing， Oct 1-3，2003， Monticello， IL，USA. Boston， MA，USA: Kluwer Academic Publisher， 2003:1270-1279.

[14] Sundaresan K， Sivakumar R. Routing in ad-hoc networks with MIMO links [C]// Proceedings of 13th IEEE International Conference on Network Protocol， Nov 6-9，Boston，MA， USA. Los Alamitos: IEEE Computer Society，2005:85-95.

收稿日期：2007-05-22

作者簡介

盛敏，博士，西安電子科技大學(xué)副教授，中國電子學(xué)會(huì)會(huì)員，陜西省通信學(xué)會(huì)青年委員會(huì)委員。主要研究方向包括移動(dòng)Ad hoc網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)、QoS技術(shù)、個(gè)人通信網(wǎng)絡(luò)等。

田野，西安電子科技大學(xué)在讀博士研究生，主要研究方向是分布式無線Ad hoc網(wǎng)絡(luò)。

李建東，西安電子科技大學(xué)教授、博導(dǎo)，中國通信學(xué)會(huì)會(huì)士，IEEE高級(jí)會(huì)員，中國電子學(xué)會(huì)高級(jí)會(huì)員，第1屆和第4屆國家“863”計(jì)劃內(nèi)個(gè)人通信技術(shù)專業(yè)專家組成員。主要從事移動(dòng)通信、個(gè)人通信、軟件無線電、分組無線網(wǎng)、自組織網(wǎng)絡(luò)、寬帶無線IP技術(shù)等方面的研究。