基于Ａｄ ｈｏｃ網(wǎng)絡的ＱｏＳ路由協(xié)議研究
2006-12-31 00:00:00肖小玲李臘元張翔
計算機應用研究 2006年9期
摘要：首先闡述Ad hoc 網(wǎng)絡的特點及應用；接著對當前Ad hoc 網(wǎng)絡的QoS 主要路由協(xié)議進行了詳細的分析與研究，并從路由機制、單向鏈路的支持、多播功能、QoS 參數(shù)選擇以及節(jié)能幾個方面進行了比較和分析；最后指出了今后的研究方向。
關鍵詞：Ad hoc網(wǎng)絡; 路由協(xié)議; QoS
中圖法分類號：TP393文獻標識碼：A
文章編號：1001－3695(2006)09－0216－03
移動Adhoc網(wǎng)絡(MobileAdhocNetwork)是由一組具有路由和轉發(fā)功能的移動節(jié)點組成的一個多跳的臨時性自治系統(tǒng)，是一種無中心的無線網(wǎng)絡[1～6]。在Adhoc網(wǎng)絡中，節(jié)點間的通信不需要固定基站的轉接，所有節(jié)點作為同等實體相互連接。
隨著移動Adhoc網(wǎng)絡應用領域的日益擴大，要求移動Adhoc網(wǎng)絡支持QoS。所謂服務質(zhì)量(QoS)是指網(wǎng)絡在傳輸數(shù)據(jù)流時要求滿足的一組服務請求，強調(diào)端到端(EndtoEnd)或網(wǎng)絡邊界到邊界的整體性，具體可以量化為帶寬、延遲、延遲抖動、丟失率、吞吐量等性能指標。通常將這種根據(jù)網(wǎng)絡上可利用的資源和數(shù)據(jù)流的QoS需求來決定的路由機制稱為QoS路由[1]。
QoS路由就是將傳統(tǒng)的最短路徑變?yōu)橐粭l更好的路徑，其主要目標包括以下兩點[1]:
(1)所選擇的路徑必須是滿足QoS約束的可行路徑。
(2)所選擇的路徑必須盡量有效地使用網(wǎng)絡并使網(wǎng)絡的資源利用率最大。
AdHoc網(wǎng)絡以其靈活、健壯、投資少等特性，現(xiàn)已廣泛用于軍事領域、自然災害應急處理、緊急通信、移動會議等領域。移動Adhoc網(wǎng)絡QoS路由的設計理論與方法的研究，已成為網(wǎng)絡領域中的一個重要研究方向。
1Adhoc網(wǎng)絡的特點及應用
1．1Adhoc網(wǎng)絡的特點
與普通的移動網(wǎng)絡和固定網(wǎng)絡相比，Adhoc網(wǎng)絡主要具有以下特點:
(1)無中心。Adhoc網(wǎng)絡沒有嚴格的控制中心。所有節(jié)點的地位平等，是一個對等式網(wǎng)絡；節(jié)點可以隨時加入和離開。
(2)有限的傳輸帶寬。移動Adhoc網(wǎng)絡采用無線傳輸技術作為通信手段，其相對于有線信道具有較低的容量，并且由于多路訪問、多徑衰減、噪聲和信號干擾等多種因素的影響，移動終端實際可得到的有效帶寬將遠遠小于理論上的最大帶寬值。
(3)自組織。網(wǎng)絡的布設無須依賴于任何預設的固定設施。節(jié)點通過分層協(xié)議和分布式算法協(xié)調(diào)各自的行為。節(jié)點開機后就可以快速、自動地組成一個獨立的網(wǎng)絡。
(4)動態(tài)的網(wǎng)絡拓撲結構。Adhoc網(wǎng)絡是一個動態(tài)的移動網(wǎng)絡。網(wǎng)絡節(jié)點可以隨處移動，也可以隨時開機和關機。這些均會使網(wǎng)絡的拓撲結構隨時發(fā)生變化。
(5)多跳路由。當節(jié)點要與其覆蓋范圍之外的節(jié)點進行通信時，需要中間節(jié)點的多跳轉發(fā)。這種多跳轉發(fā)是由普通的網(wǎng)絡節(jié)點，而不是專門的路由設備完成的。
(6)安全性差。Adhoc網(wǎng)絡是一種特殊的無線移動網(wǎng)絡，更容易受到被動竊聽、主動入侵、拒絕服務、剝奪睡眠等網(wǎng)絡攻擊，使得Adhoc網(wǎng)絡安全性問題比傳統(tǒng)網(wǎng)絡復雜得多。
1．2Adhoc網(wǎng)絡的應用
由于Adhoc網(wǎng)絡的特殊性，其應用領域與普通的通信網(wǎng)絡有著明顯的差別，可分為以下幾類:
(1)軍事應用。在現(xiàn)代化戰(zhàn)場上，各種軍事車輛之間、士兵之間、士兵與軍事車輛之間均需要保持密切的聯(lián)系，以完成集中統(tǒng)一指揮，協(xié)調(diào)作戰(zhàn)。這樣的通信網(wǎng)絡是一種典型的Adhoc網(wǎng)絡。
(2)移動會議。在室外臨時環(huán)境中，工作團體的所有成員可以通過Adhoc方式組成一個臨時網(wǎng)絡來協(xié)同完成一項大的任務，或協(xié)同完成某個計算任務；在室內(nèi)辦公環(huán)境中，辦公人員也可以通過無線方式自動從臺式機上下載電子郵件，更新工作日程表等。
(3)家庭聯(lián)網(wǎng)。通過移動聯(lián)網(wǎng)的方式將辦公室的辦公環(huán)境延伸到家庭，必要時在家庭辦公；或者利用我們隨身攜帶的個人無線Adhoc設備與裝備了Adhoc收發(fā)器的家庭電器通信，自動完成開燈、打開娛樂設備、調(diào)節(jié)空調(diào)等操作。
(4)緊急服務。由于停電或其他災害出現(xiàn)，網(wǎng)絡基礎設施遭到破壞時，組建一個Adhoc網(wǎng)絡幫助緊急救援人員完成必要的通信工作。
(5)傳感器網(wǎng)絡。傳感器可以工作在危險的環(huán)境，如化學有害物質(zhì)泄漏現(xiàn)場。通過在傳感器上裝備位置指示器、Adhoc收發(fā)器等，將傳感器所在現(xiàn)場的信息傳送到危險現(xiàn)場以外，代替救援人員進入現(xiàn)場，收集和辨別事故信息。傳感器網(wǎng)絡還可用于環(huán)境污染監(jiān)測、地震和海嘯的早期預報、生產(chǎn)車間監(jiān)控等許多領域。
2Adhoc網(wǎng)絡QoS路由協(xié)議
根據(jù)路由發(fā)現(xiàn)策略的不同，Adhoc網(wǎng)絡QoS路由協(xié)議可分為先應式和反應式兩種類型。
先應式路由協(xié)議也被稱為表驅(qū)動路由協(xié)議、主動路由協(xié)議。它們有一個共同的特點：不管有無通信需求，都要進行路由信息交換。反應式路由協(xié)議也被稱為按需路由協(xié)議、源啟動按需路由協(xié)議。它僅在需要路由時才由源節(jié)點來創(chuàng)建，因而拓撲結構和路由表內(nèi)容是按需建立的。通信過程中維護路由，通信完畢后便不再進行維護。
2．1Q_AODV(AdhocOnDemandDistanceVector)
AODV協(xié)議是在DSDV(DestinationSequencedDistanceVector)協(xié)議的基礎上，結合類似DSR（DynamicSourceRouting）中的按需路由機制進行改進后提出的一種經(jīng)典的Adhoc路由協(xié)議。它按需地建立和維護路由，采用目的節(jié)點排序的方式有效避免路由環(huán)路。ChenxiZhu等人在AODV協(xié)議的基礎上設計了一種QoS路由協(xié)議[7]，稱之為Q_AODV。
該算法為每個路由條目定義五種狀態(tài):空閑(NONE)、接收路由請求(REQ)、已經(jīng)預約(RESV)、上游斷路(BRK_U)和下游斷路(BRK_D)。采用軟狀態(tài)方便地保證了QoS的有效性，即為每個狀態(tài)設置計時器，當計時器超時或者收到路由控制消息，節(jié)點轉移到另外一個狀態(tài)。
Q_AODV的實現(xiàn)分成兩步，即節(jié)點按需進行路由發(fā)現(xiàn)和協(xié)議按需進行路由維護。
協(xié)議分析如下：
(1)Q_AODV協(xié)議是一種按需的路由協(xié)議。
(2)在路由選擇中通過最小帶寬的路徑來進行路由選擇，具有QoS的支持。
(3)采用軟狀態(tài)的方法保證QoS路由的有效性，每個狀態(tài)設置生存時間，計時器超時而沒有被更新則認為失效，觸發(fā)路由維護。這些作法減少了路由控制開銷。而另一方面，也增加了路由建立和修復的時間。
(4)可有效避免路由環(huán)路。
(5)只適用于規(guī)模較小的低移動性網(wǎng)絡，并且不支持單向信道。
2．2LSQoS(LinkStatebaseQoSRouting)
LSQoS[8]協(xié)議采用平均錯誤分組率和生存時間作為路由指標。節(jié)點i到節(jié)點j的有向鏈路的信號質(zhì)量可以用平均錯誤分組率Pke[i，j]進行描述。Pke[i，j]是一個加權平均值，可以根據(jù)最新采樣進行動態(tài)調(diào)整，其相應加權公式為
式中，B為加權因子(1>B≥0)，它決定了平均錯誤分組率的歷史統(tǒng)計值與新采樣的平均錯誤分組率值的權重關系，即平均錯誤分組率值對接收信號質(zhì)量的敏感程度。
節(jié)點j是節(jié)點i的相鄰節(jié)點，在采樣時刻K節(jié)點i到節(jié)點j的有向鏈路的生存時間為LTK[i，j]，并且(Max_Living_Time≥LTK[i，j]≥0)，Max_Living_Time表示最大生存時間。對于某無線鏈路，其生存時間越長，說明其繼續(xù)存在的可能性越大，即其可信度越大。
協(xié)議分析如下：
(1)LSQoS協(xié)議采用平均錯誤分組率和生存時間作為路由指標來尋找信號接收質(zhì)量和信道穩(wěn)定性最好的路由，保證了所尋路由的穩(wěn)定性和可靠性，從而達到對QoS的控制。
(2)需要實時收集并計算平均錯誤分組率和鏈路生存時間，同時需要周期性廣播鏈路狀態(tài)數(shù)據(jù)庫，增加了電能消耗和路由開銷，加重了節(jié)點的負載。
(3)需要保存錯誤分組率和鏈路生存時間的列表，占用一定的存儲空間。
2．3CEDAR(CoreExtractionDistributedAdhocRouting)
CEDAR[9]核心提取的QoS路由協(xié)議是一種分級的路由協(xié)議。其基本思想是選取網(wǎng)絡中若干節(jié)點構成核心，在這些節(jié)點間進行鏈路狀態(tài)信息交換，并由這些核心節(jié)點按需實現(xiàn)QoS路由的計算。CEDAR的實現(xiàn)包含三個主要部分，即網(wǎng)絡核心的建立與維護、鏈路狀態(tài)信息在核心的傳播以及QoS路由的發(fā)現(xiàn)和維護。
協(xié)議分析如下：
(1)CEDAR將鏈路狀態(tài)信息更新和QoS路由計算局限在網(wǎng)絡核心，從而在一定程度上減小了QoS路由協(xié)議的開銷。
(2)CEDAR的性能在很大程度上取決于網(wǎng)絡核心的穩(wěn)定程度和有效性。當網(wǎng)絡拓撲變化比較劇烈時，核心路徑頻繁中斷，網(wǎng)絡核心的收斂需要一段時間，而在此之前建立的QoS路由均是無效的。
(3)CEDAR的不足是需要實現(xiàn)較復雜的網(wǎng)絡核心的建立和維護算法，而查找網(wǎng)絡核心是NP完全的。
(4)適用于中小規(guī)模的移動Adhoc網(wǎng)絡。
2．4STARA(SystemandTrafficDependentAdaptiveRoutingAlgorithm)
STARA[10]協(xié)議在路由選擇中采用最短路徑法，但是最短路由度量采用了平均延時，所以使其具有QoS的支持。STARA在進行分組路由時，考慮了無線鏈路的容量和排隊延時等因素，每個節(jié)點i采用改進的端到端確認協(xié)議為每一對節(jié)點(i，d)計算平均延時D，方法如式(2)所示：
式中，C∈[0，1]為遺忘因子，用于調(diào)整歷史延遲值和當前延遲值的權重關系;k∈N，N表示節(jié)點i每跳包含的所有相鄰節(jié)點。然后根據(jù)式(3)將經(jīng)過的流量分配給不同的相鄰節(jié)點，從而使得所有可用的路徑具有相同的延時。
Pdik(t)=Pdik(t-1)+A(t)(Ddi(t)-Ddik(t))(3)
協(xié)議分析如下:
(1)STARA是一種主動路由協(xié)議。
(2)考慮了無線鏈路的帶寬和排隊時延等因素，它采用路徑平均延時作為路由計算指標，并盡可能將業(yè)務量平均分配給所有的可用路徑，具有QoS的支持。
(3)由于STARA是一種主動路由協(xié)議，每個節(jié)點均要周期性計算平均延時并更新路由表，所以此協(xié)議開銷較大。
2．5TBP
Adhoc網(wǎng)絡拓撲變化頻繁，獲得和維護準確的鏈路狀態(tài)信息十分困難。常規(guī)的思路是增加鏈路狀態(tài)信息的更新頻率，而另外一種解決的策略則是允許鏈路狀態(tài)信息的不準確性，在路由算法中消除它的影響。其中十分著名的是由S.Chen等人提出的基于標簽探測的路由協(xié)議TBP[11](TicketBasedProbing)。TBP假設網(wǎng)絡中的每個節(jié)點均保存有輸出鏈路狀態(tài)和本節(jié)點到網(wǎng)絡中其他節(jié)點的端到端路徑狀態(tài)的最新信息。TBP建立QoS路由的過程如下：
源節(jié)點根據(jù)業(yè)務流的QoS要求發(fā)放一定數(shù)量的標簽，這些標簽由探索包攜帶，探索包由源節(jié)點向目的節(jié)點轉發(fā)，當中間節(jié)點收到探索包后，根據(jù)輸出鏈路的狀態(tài)信息和相鄰節(jié)點到目的節(jié)點的端到端路徑狀態(tài)信息決定是否應該分離收到的探索包，每個探索包應攜帶的標簽數(shù)量以及應該將探索包轉發(fā)到哪些相鄰節(jié)點。如果有探索包最終到達目的節(jié)點，則找到一條源節(jié)點到目的節(jié)點滿足QoS的路徑，由目的節(jié)點沿該路徑的相反方向發(fā)送資源預留包，實現(xiàn)資源預留；如果源節(jié)點在規(guī)定的時間內(nèi)未收到來自目的節(jié)點的資源預留包，則表明建立QoS路由的嘗試失敗，由源節(jié)點根據(jù)需要進行重試或放棄。
協(xié)議分析如下:
(1)該協(xié)議是一種按需的路由協(xié)議。
(2)TBP的主要優(yōu)點是不需要完全準確的鏈路狀態(tài)信息，同時通過有限數(shù)量的標簽和在轉發(fā)路由請求包時的智能逐跳選擇來減少開銷。
(3)若發(fā)現(xiàn)滿足QoS要求路由的概率越小，那么探測分組攜帶的標簽越多。
(4)TBP的代價是減小了找到滿足QoS要求的路徑的概率；同時，它需要對狀態(tài)信息進行周期更新，這會帶來較大的帶寬開銷。
2．6ABGR(AdvancedBandwidthGuaranteedRouting)
ABGR[12，13]協(xié)議采用了多種限制擴散的機制來解決Adhoc網(wǎng)絡中盲目擴散而導致的帶寬損耗問題，并充分考慮了節(jié)點的電能受限問題，試圖在路由選擇的過程中延長網(wǎng)絡的完整性，避免由于部分節(jié)點過早地耗盡電能而使得網(wǎng)絡被分割。
ABGR中源節(jié)點根據(jù)目的節(jié)點的物理方位、相鄰節(jié)點的移動速度、相鄰節(jié)點的電能剩余來進行有限制的擴散，其有限擴散條件如式(4):
其中，x代表從源節(jié)點到目的節(jié)點進行路由選擇過程中的中間節(jié)點;Di代表指向目的節(jié)點的方向;B(x，nj)代表鏈路x→nj上的空閑帶寬;Vnj代表節(jié)點nj的移動速度;Cnj代表節(jié)點nj上的電源剩余量。
在路由請求過程中，源節(jié)點S只是向滿足條件Cxs→t的相鄰節(jié)點發(fā)送探測信息，從而保證了基于帶寬和電能受限的QoS請求。
協(xié)議分析如下:
(1)協(xié)議將電能剩余作為QoS的條件，一定程度上控制了由于電能變化而引起的網(wǎng)絡拓撲變化的問題。
(2)可提高被選擇路徑的穩(wěn)定性，并有效控制了路由建立中引起的開銷。
(3)每個節(jié)點需要周期性地與相鄰節(jié)點交換移動速度、電能剩余等信息，需要消耗一定的電能及網(wǎng)絡帶寬。
(4)系統(tǒng)需要GPS等硬件的支持。
(5)可有效避免路由環(huán)路。
3基于Adhoc網(wǎng)絡的QoS路由協(xié)議比較
一個理想的Adhoc網(wǎng)絡的QoS路由協(xié)議，應充分滿足網(wǎng)絡的分布式運行、按需進行協(xié)議操作、單向鏈路的支持、節(jié)能、可擴展性、安全性、無環(huán)路由和多播應用的需求。表1從路由機制、支持多播功能、QoS參數(shù)選擇等角度對以上幾種Adhoc網(wǎng)絡QoS路由協(xié)議作了比較分析。
表1基于Adhoc網(wǎng)絡的QoS路由協(xié)議比較
4結束語
Adhoc網(wǎng)絡作為一種自創(chuàng)造、自組織和自管理的網(wǎng)絡，因其組網(wǎng)快速、靈活、節(jié)點分布等諸多的優(yōu)點，在戰(zhàn)爭、搶險救災以及應付突發(fā)事件等特殊領域有著不可替代的作用。
盡管目前已有很多的文獻從不同的角度研究了移動Adhoc網(wǎng)絡的QoS問題，但目前還沒有真正切實可行的移動Adhoc網(wǎng)絡支持QoS的方案，還需要在QoS體系結構、QoS路由、支持業(yè)務區(qū)分、資源預留的MAC協(xié)議、QoS機制的可擴展性和通信安全等方面作進一步的研究。
參考文獻：
［1］李臘元，李春林.計算機網(wǎng)絡技術\\[M\\].北京:國防工業(yè)出版社，2001.287292.
［2］李臘元，李春林. 動態(tài)QoS 多播路由協(xié)議\\[J\\]. 電子學報， 2003，31 (9):13451350.
［3］Li LaYuan， Li ChunLin. A Multicast Routing Protocol with Multiple QoS Constraints\\[C\\]. Montreal， Canada： Proceedings of WCC， 2002.181198.
［4］王海濤，鄭少仁，宋麗華. Ad hoc網(wǎng)絡中QoS 保障機制的研究\\[J\\]. 通信學報， 2002， 23(10):114120.［5］沈暉，石冰心， 鄒玲，等. Ad hoc網(wǎng)中基于位置信息的QoS路由算法\\[J\\]. 通信學報， 2003， 24(9):2734.
［6］Royer E M， Perkins C E. Multicast Operation of the Ad hoc Ondemand Distance Vector Routing Protocol\\[J\\]. ACM Mobicom，1999， (8):207218.
［7］Chenxi Zhu， M ScottCorson. QoS Routing for Mobile Ad hoc Networks\\[J\\]. INFOCOM，2002，6 (2):958967.
［8］英春， 史美林. 自組網(wǎng)環(huán)境下基于QoS 的路由協(xié)議\\[J\\]. 計算機學報， 2001，24(10):10261033.
［9］Sivakumar R， Sinha P， Bharghavan V. CEDAR: A Coreextraction Distributed Ad hoc Routing Algorithm\\[J\\]. IEEE Journal of Selected Areas in Communications， Special Issue on Ad hoc Networks， 1999，17(8):14541465.
［10］Gupta P， Kumar P R. A System and Traffic Dependent Adaptive Routing Algorithm for Ad hoc Networks\\[C\\]. San Diego，California:The 36th Conference on Decision and Control，1997. 23752380.［11］Chen S， Nahrstedt K. Distributed Quality of Service Routing in Ad hoc Networks\\[J\\]. IEEE Journal of Selected Areas in Communications，1999，17(8):14881505.
［12］Toh C K. Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad hoc Networks\\[J\\]. IEEE Communication Magazine，2001，(6):138147.
［13］吳小兵， 黃傳河，等. 一種新的移動Ad hoc網(wǎng)絡中帶寬保證的路由算法\\[J\\]. 計算機工程與應用， 2003，39(2):177180
作者簡介：
肖小玲（1973），女，湖南邵陽人，副教授，博士研究生，主要研究方向為高性能網(wǎng)絡技術與路由算法；李臘元（1946），男，湖北新洲人，教授，博導，主要研究方向為高性能網(wǎng)絡技術與通信協(xié)議；張翔（1969），男，湖北蘄春人，副教授，博士，博士后，主要研究方向為圖像處理、計算機視覺、模式識別。
