【正文】 基于綜合判據(jù)的無線Mesh網(wǎng)路由協(xié)議作者簡介：沈 呈（1982—），男，博士生，研究方向為移動通信與無線網(wǎng)絡技術(shù)。聯(lián)系方式：Email: snimmiey@， 基金項目：國家自然科學基金重大研究計劃項目(90604003)、國家自然科學基金項目(60603067)、高等學校博士學科專項科研基金資助課題(20090092120029)。沈呈1,2，陸一飛1,2，夏勤1,2（1．東南大學計算機網(wǎng)絡和信息集成教育部重點實驗室，江蘇南京 210096；2．東南大學計算機科學與工程學院，江蘇南京 210096）摘 要： 為用戶提供高質(zhì)量，高性能的通信鏈路是無線Mesh網(wǎng)路由協(xié)議所面臨的重要挑戰(zhàn)，而當前從Ad Hoc網(wǎng)絡沿襲下來的路由協(xié)議并不能夠滿足無線Mesh網(wǎng)的性能要求。本文以O(shè)LSR協(xié)議為原型，結(jié)合跨層優(yōu)化理論，為基礎(chǔ)設(shè)施架構(gòu)的無線Mesh網(wǎng)提出了一種新穎的、基于綜合判據(jù)的路由協(xié)議。該協(xié)議通過跨層操作機制綜合考慮無線鏈接的長度及通信效率對鏈接性能的影響，從而達到優(yōu)化路由選擇的效果。仿真結(jié)果表明，所提出的路由協(xié)議能夠有效地提高網(wǎng)絡中分組的遞交率，降低端到端的延時，并且能夠在一定程度上達到負載均衡的路由效果。關(guān)鍵詞： 無線Mesh網(wǎng)；路由協(xié)議；跨層設(shè)計；先驗式路由1． 引言無線Mesh網(wǎng)（Wireless Mesh Network，簡稱WMN）是一種新型的分布式寬帶無線網(wǎng)絡架構(gòu)，能夠?qū)崿F(xiàn)家庭寬帶個域網(wǎng)、樓宇自動化網(wǎng)絡、社區(qū)組網(wǎng)、交通醫(yī)療系統(tǒng)網(wǎng)絡、校園組網(wǎng)、企業(yè)組網(wǎng)以及城域組網(wǎng)等多層次、大范圍的無線應用。當前，國內(nèi)外的許多研究機構(gòu)和相關(guān)廠商都對無線Mesh網(wǎng)技術(shù)進行了廣泛的研究，相關(guān)的標準也在積極制定中[1]。通常來說，無線Mesh網(wǎng)有三種拓撲架構(gòu)，分別為基礎(chǔ)設(shè)施/骨干WMN架構(gòu)、客戶端WMN架構(gòu)和混合WMN架構(gòu)。其中，最常見的，也是應用最多的，是基礎(chǔ)設(shè)施/骨干WMN架構(gòu)，它被廣泛地應用在無線城域網(wǎng)的建設(shè)中，本文中所有的論述都是針對這種架構(gòu)進行的。圖1顯示了基礎(chǔ)設(shè)施/骨干WMN架構(gòu)的無線Mesh網(wǎng)的組成。從圖中可以看出，這種架構(gòu)被分為三層，最低一層為終端用戶層，各種終端用戶設(shè)備，如手機、筆記本電腦、PDA等通過各種標準接入技術(shù)接入到無線Mesh網(wǎng)；中間一層為無線Mesh層，由無線接入點（Mesh Access Point，MAP）和超網(wǎng)關(guān)節(jié)點（Super Gateway，SGW）組成，這些節(jié)點相互連接形成一個自組織、自配置的無線骨干網(wǎng)。終端用戶可以通過該層接入到核心網(wǎng)絡，也可以通過該層進行彼此間的通信。為了達到這個目標，需要為該層設(shè)計一個高效可靠的路由協(xié)議，這也正是本文所關(guān)注的問題；最上面一層是核心網(wǎng)絡層，主要提供各種網(wǎng)絡互聯(lián)服務[2]。圖1 基礎(chǔ)設(shè)施/骨干WMN網(wǎng)絡架構(gòu)如前面所述，基礎(chǔ)設(shè)施/骨干WMN架構(gòu)的無線Mesh網(wǎng)大多被運用在社區(qū)組網(wǎng)、城域組網(wǎng)等交互性強、普適性高、性能敏感的應用場合。而且隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡服務呈現(xiàn)多元化趨勢，特別是具有實時性要求的多媒體業(yè)務，如語音、視頻等近幾年得到了迅猛的發(fā)展。這樣復雜的應用場景和多樣的業(yè)務需求也就給無線Mesh網(wǎng)，特別是其中無線Mesh層的路由協(xié)議設(shè)計提出了更為苛刻的性能要求[3]。近年來的研究表明，傳統(tǒng)的網(wǎng)絡分層設(shè)計方法，對于無線Mesh網(wǎng)這樣的無線網(wǎng)絡來說，并不是有效的設(shè)計方法。這主要是由于無線信道的開放性和信道參數(shù)的時變性使得分層設(shè)計方法無法保證網(wǎng)絡資源的利用率和用戶業(yè)務的QoS需求。而且傳統(tǒng)的路由協(xié)議基于“最小跳數(shù)”的選路機制，存在許多不足之處，例如無法有效地控制擁塞現(xiàn)象、公平性很差、不能實現(xiàn)負載均衡等等。因此，利用跨層設(shè)計的思想來實現(xiàn)新的路由協(xié)議，改進上述不足之處，從而進一步提高無線Mesh網(wǎng)的性能，是本文的主要出發(fā)點。本文結(jié)合跨層優(yōu)化理論，提出了一種適用于無線Mesh環(huán)境的綜合判據(jù)，并以此為基礎(chǔ)，為無線Mesh網(wǎng)的無線Mesh層設(shè)計了基于綜合判據(jù)的自適應路由協(xié)議IMAR（Integrated Metrics based Adaptive Routing）。論文的后續(xù)部分安排如下：第2部分討論了相關(guān)的研究工作；第3部分給出了綜合判據(jù)的定義，并且詳細介紹了IMAR協(xié)議的實現(xiàn)；第4部分對協(xié)議進行了仿真實驗及結(jié)果分析；最后部分對全文的研究工作進行了總結(jié)。2． 相關(guān)工作 網(wǎng)絡層路由協(xié)議當前，無線Mesh網(wǎng)作為一種新興的網(wǎng)絡技術(shù)，其路由協(xié)議的研究和設(shè)計尚未形成統(tǒng)一的標準，大多數(shù)現(xiàn)有的無線Mesh網(wǎng)路由協(xié)議都是從Ad Hoc網(wǎng)絡的路由協(xié)議發(fā)展而來的。因此，和Ad Hoc類似，目前無線Mesh網(wǎng)的路由協(xié)議根據(jù)路由的生成時間可以分為先驗式和反應式兩大類，根據(jù)分組的轉(zhuǎn)發(fā)機制又可以分為逐跳（hopbyhop）和源路由兩大類。在無線Mesh網(wǎng)的無線Mesh層中，網(wǎng)絡節(jié)點相對固定，只有無線接入點的故障、加入和退出以及無線鏈路的一些不確定性會造成網(wǎng)絡拓撲的變化，網(wǎng)絡拓撲變化的速率要遠遠低于數(shù)據(jù)流的到達速率，并且無線Mesh網(wǎng)中的主流業(yè)務為存在一定延遲要求的Internet業(yè)務。基于這樣的網(wǎng)絡環(huán)境，Yaling Yang等人在文獻[4]中給出論證：先驗式的逐跳路由協(xié)議最適合無線Mesh網(wǎng)。OLSR[5]（Optimized Link State Routing）就是一種典型的先驗式逐跳路由協(xié)議，其融合多點轉(zhuǎn)播技術(shù)[6]，對傳統(tǒng)的鏈路狀態(tài)路由協(xié)議做了兩方面的改進：一是在節(jié)點構(gòu)造拓撲控制分組的時候，對所包含的局部拓撲信息進行有效的壓縮，可以減少傳輸拓撲控制分組所需的帶寬開銷；二是在拓撲控制分組的廣播過程中采用多點轉(zhuǎn)播技術(shù)來代替泛洪，能夠在達到相同廣播效果的同時，大大降低廣播操作所造成的開銷。這兩點改進都旨在減少路由維護操作給網(wǎng)絡帶來的額外開銷，能夠在很大程度上減少路由協(xié)議所占用的網(wǎng)絡資源。然而，OLSR路由協(xié)議在進行路由選擇時主要考慮“最小跳數(shù)”這個約束條件，卻忽略了無線鏈路的可靠程度以及路徑上節(jié)點的繁忙程度，這樣容易導致如下的問題：（1）協(xié)議傾向于選擇跳數(shù)少的路徑以減少其中的轉(zhuǎn)發(fā)次數(shù)，這樣容易導致每跳的距離相應增大，對于無線傳輸來說，對端節(jié)點間的距離一定程度上決定了單跳鏈接的質(zhì)量，過大的傳輸距離勢必會導致無線干擾增大，數(shù)據(jù)傳輸率降低，所以，好的路由判據(jù)需要在跳數(shù)和每跳距離間作出權(quán)衡；（2）網(wǎng)絡中的流量容易集中于某些鏈路，從而形成一些“熱區(qū)”，在這些“熱區(qū)”中容易出現(xiàn)網(wǎng)絡擁塞，導致經(jīng)過這些區(qū)域的數(shù)據(jù)包經(jīng)歷嚴重的延遲甚至被丟失，而與此同時，網(wǎng)絡中的其它一些節(jié)點和鏈路可能長期處于空閑狀態(tài)，這些潛在的網(wǎng)絡資源沒有得到有效的利用。因此，對于無線Mesh網(wǎng)來說，OLSR路由協(xié)議的性能還達不到理想的要求。近幾年，有不少學者對OLSR協(xié)議進行了深入的研究，并針對無線Mesh網(wǎng)絡的特點對其進行了優(yōu)化。例如：文獻[7]提出了一種新的路由判據(jù)，叫做信號噪音比，并將其運用于OLSR協(xié)議，實驗表明，和最小跳數(shù)相比，該判據(jù)能夠提高無線Mesh網(wǎng)的整體性能；文獻[8]設(shè)計了一種OLSR擴展路由協(xié)議，其中包含了一套節(jié)點信譽管理框架，協(xié)議采用節(jié)點信譽作為路由判據(jù)，能夠縮短網(wǎng)絡中的端到端延時；文獻[9]對OLSR協(xié)議進行了改進，使其支持多信道多收發(fā)器配置，并在路由選擇過程中融入了對路徑質(zhì)量的考量，從而提高了協(xié)議的綜合性能和可擴展性。上述的這些OLSR改進方案，大多已經(jīng)跳出了以最小跳數(shù)作為路由判據(jù)的傳統(tǒng)套路，且或多或少地引入了跨層設(shè)計的思想，但是也存在著一些不足之處，例如：路徑的評判標準相對單一；沒有考慮節(jié)點處理能力對路徑質(zhì)量的影響；缺乏對網(wǎng)絡負載平衡特性的關(guān)注等。因此，針對這些不足之處進行改進，從而進一步提高無線Mesh網(wǎng)路由協(xié)議的性能，成為下一步研究的一種可行思路。 跨層優(yōu)化設(shè)計網(wǎng)絡協(xié)議跨層設(shè)計的核心思想在于：維持層間分離準則的同時，放松對分層結(jié)構(gòu)的嚴格要求，允許不同層的算法共享網(wǎng)絡的狀態(tài)信息，這樣有利于層內(nèi)和層間操作的優(yōu)化，從而使得網(wǎng)絡的整體性能，如運行效率、資源利用、QoS保證、安全協(xié)作和能量管理等，有較大程度的促進（如圖2（a）所示）。 (a) 網(wǎng)絡協(xié)議的跨層設(shè)計 (b) IMAR協(xié)議中的跨層設(shè)計圖2 跨層設(shè)計示意圖至于跨層設(shè)計思想在網(wǎng)絡層路由協(xié)議中的應用，主要體現(xiàn)在網(wǎng)絡層與數(shù)據(jù)鏈路層之間的跨層設(shè)計上，映射到實際應用中，這種跨層設(shè)計又直接反映到跨層路由判據(jù)的設(shè)計上來。如前面所述，在無線Mesh網(wǎng)中，采用傳統(tǒng)的“最小跳數(shù)”作為路由判據(jù)，不足以達到良好的路由效果，即網(wǎng)絡吞吐量、端到端延時和可靠性等性能指標達不到理想的要求。原因在于“最小跳數(shù)”路由判據(jù)沒有考慮到物理層無線信道參數(shù)的變化對MAC層接入性能的影響，造成所選路徑無法適應鏈路質(zhì)量和節(jié)點狀態(tài)的變化，從而導致路由性能的衰減。而融合了跨層設(shè)計的路由判據(jù)，由于其收集了低層的鏈路質(zhì)量信息來作為路由決策時的依據(jù)，所以和“最小跳數(shù)”相比，有較為明顯的性能優(yōu)勢。例如：文獻[10]，節(jié)點建立路由時以物理層的數(shù)據(jù)傳輸速率作為判據(jù)，從而建立高速率、低延時的路由；文獻[11]通過減少干擾來找到高吞吐量的路徑，并通過最優(yōu)化傳輸功率的方法增加路徑的可靠性；文獻[12，13]綜合考慮節(jié)點的剩余帶寬，當前負載，以及緩沖隊列飽和度等因素，對無線Mesh網(wǎng)絡中的反應式路由協(xié)議進行優(yōu)化，從而提高網(wǎng)絡的吞吐率和負載均衡能力；文獻[14]將跨層設(shè)計的思想擴展到多信道無線Mesh網(wǎng)絡中。以上的方法有一個共同特點：它們在進行跨層設(shè)計時，都是從“節(jié)點”的角度出發(fā)，對單個節(jié)點的性能指標進行衡量和優(yōu)化。但是，在實際的數(shù)據(jù)傳輸過程中，單跳傳輸?shù)馁|(zhì)量和性能是由發(fā)送方和接收方兩者共同決定的，因此，從“鏈接”的角度來優(yōu)化跨層設(shè)計，是一個值得探索的研究方向。3． 基于綜合判據(jù)的自適應路由協(xié)議IMAR如前面所述，OLSR協(xié)議具有較高的運算效率，但是路由判據(jù)先天的不足使得其無法滿足無線Mesh網(wǎng)的性能需求，而跨層優(yōu)化機制在改進算法機理，提高協(xié)議性能方面有著顯著的效果。因此，本文基于OLSR協(xié)議的優(yōu)點，融合跨層設(shè)計思想，為無線Mesh網(wǎng)的無線Mesh層提出了一種易于實現(xiàn)、性能優(yōu)良并能夠動態(tài)處理網(wǎng)絡變化的基于綜合判據(jù)的自適應路由協(xié)議IMAR。首先給出網(wǎng)絡模型：考慮一個由N個無線接入點組成的無線Mesh層，在這里，為了簡化模型，討論路由問題時，將超網(wǎng)關(guān)節(jié)點（SGW）當作普通的無線接入點來對待，忽略其網(wǎng)關(guān)作用。同時，在路由計算過程中，只考慮具有雙向性的無線鏈接，忽略其它不對稱的單向鏈接。對應到圖論中，該無線Mesh層可以用二維平面內(nèi)的無向圖G（V，E）來表示，其中V為圖中的頂點集合，vV表示網(wǎng)絡中的一個無線接入點，E為圖中邊的集合，eE表示網(wǎng)絡中v和v之間的一條無線鏈接。我們假設(shè)網(wǎng)絡中的無線接入點均是同構(gòu)的，對于每個無線接入點都增加了兩個跨層模塊，如圖2（b）所示。參數(shù)采集模塊負責在數(shù)據(jù)鏈路層上收集無線接入點的狀態(tài)信