無線Mesh網絡下基于網絡編碼的機會路由協議的研究

朱朗 張寧

一、引言

現有的無線服務主要是基于蜂窩網和無線局域網。蜂窩網是在基于基站的基礎上為直徑幾公里范圍內的設備提供網絡服務。而無線局域網的設計是覆蓋百米左右的區域，然后通過有線網絡接入。公共的頻譜使用權雖然讓系統成本降低，但也對抗干擾能力提出了高要求。Mesh網絡與這兩者的架構是有本質的區別。未來Mesh可以作為蜂窩網和無線局域網的擴充，它可以彌補兩者的劣勢，甚至融合到蜂窩網和無線局域網中，形成無線網絡的統一。，Mesh網絡還可以獨立存在，用在特殊場景如車輛自組織網，無線傳感器網絡，戰時通信等。無線Mesh網絡技術的瓶頸之一就是路由協議的設計。網絡編碼和機會路由作為新興技術能夠有效地提高網絡系統的吞吐量和可靠性，已經成為研究的熱點。

二、網絡編碼和機會路由

網絡編碼起始于Ahlswede，Cai等的一篇開創性論文。該論文指出，傳統路由的基本作用是存儲和轉發，假設允許網絡中間節點對傳輸的信息可以進行簡單的編碼處理，那么基于新路由參與的網絡多播就能夠達到理論上的最大傳輸容量。這也引出了最大流最小割原理：一個網絡的最大多播吞吐量等于分割源節點和目的節點的最小割集容量。隨著研究的深入，研究者發現，網絡編碼不僅能改善網絡的吞吐量，在均衡網絡負載，降低節點能耗，提高網絡安全性等方面也有較好的表現。

機會路由（也稱機會轉發）的概念是2004年由麻省理工學院的Biswas等人提出。機會路由中每個節點都有自己的一個候選轉發節點集合，每次傳遞信息時，并沒有確定下一跳節點，而是根據廣播數據分組來選擇合適的候選節點，通過對比接收到分組數據的應答順序給出候選節點的優先級，從而選擇最佳的下一跳來轉發數據。機會路由的突出優點是增加單跳傳輸的可靠性，減少總的傳輸跳數來提高吞吐量。

三、主流協議

第一個把兩者相結合是2006年提出的獨立于MAC層的機會路由與編碼—MORE協議。簡單地說，MORE協議是把流內隨機網絡編碼與機會路由相結合。MORE的路由策略如下：源節點把需要傳送的文件以K個數據包分批，每批的K值不同。這些K個數據包叫做原生數據包。當MAC層準備發送時，源節點對K個數據包隨機線性編碼后廣播編碼包。源節點對每個數據包附加一個MORE層，用來說明這個數據包的編碼向量，批次，源節點，多個目的節點IP地址，以及轉發節點集。轉發節點以ETX值排序。源節點一直發送當前批次的數據包直到收到目的節點的確認包，然后發送下一批次數據包。中間節點監聽所有無線數據傳輸，當一個節點監聽到一個數據包時，先檢查自己是否屬于轉發節點集中，如果是，檢查是否為更新包，如果是儲存，否則丟棄。當中間節點屬于轉發節點時，這會觸發一個程序，將監聽到的數據包再次隨機線性編碼并廣播，這時的數據包可能為更新包，也可能不是更新包。目的節點在接收數據包時，首先檢查是否為當前批次的更新包，即檢查編碼向量是否線性相關。線性相關，則不是更新包，丟棄。只要目的節點收到K個更新包，在數學理論上就能證明可以正確解碼。此時目的節點會發送ACK確認包通過最佳路徑傳輸給源節點，以發送下一批次的數據。每個節點收到確認包之后相對于數據包會優先發送。最優化多路徑網絡編碼路由（OMNC）繼承了MORE協議的思想，也是通過機會路由來傳輸編碼后的數據。不僅如此，OMNC還考慮了節點的編碼能力、信道的通信質量、網絡的廣播速率等因素來設計路由度量以選擇最優路徑來提高吞吐量。OMNC也是流內網絡編碼機會路由協議。

與之對應的流間網絡編碼機會路由協議主要有CAOR，BEND和PACE。CAOR協議是在COPE協議的基礎上引入了機會路由策略。它可以提高多流無線網絡的吞吐量。具體做法是將編碼效率高的節點加入轉發節點集，通過排序選擇較高的編碼節點。這需要維護相鄰兩跳節點的信息。BEND協議相比較CAOR是實現在MAC層上的，PACE協議引入了區域聯合編碼與傳輸算法，它實行了網絡多點聯合編碼，以增益的大小來對轉發節點進行排序。它的優勢在于減少了碰撞，提高了系統的傳輸效率。

基于網絡編碼和機會路由協議的重點在于（1）如何選擇候選轉發節點。目前已經有很多路由度量作為選擇標準。經典的路由測度如跳數HOP，預期傳輸次數ETX，期望傳輸時間ETT等，近年來考慮較全面的路由測度如加權累計期望傳輸時間WCETT，接口和信道切換測度MIC，干擾感知路由測度iAWARE。任何路由度量都具有兩面性，因為真實環境的復雜性決定了路由度量趨向于模擬真實環境，但這無疑也會增加額外的計算負擔。研究的難點就是在實際網絡環境中如何取舍。（2）如何協調候選轉發節點。候選轉發節點的加入，退出和轉發會帶來數據重發、解碼、沖突、冗余等問題，從而降低系統性能。目前的協調機制有數據分組應答模式、控制包應答模式和無協調模式。對研究者來說，全面設計新地無線Mesh路由協議主要從多借口多信道、鏈路質量、QOS保障、跨層設計、結合調度等方面進行突破。

四、結語

無線Mesh網絡既能自組織、自愈合，又可與當前的蜂窩網和WLAN網絡相融合，提高現有的網絡服務，已成為未來寬帶接入技術的研究熱點。而其中基于網絡編碼和機會路由兩大技術的路由協議在吞吐量和可靠性方面有著巨大的優勢，但是還沒有統一的路由算法得到廣泛的認可。