朱朗 張寧

一、引言

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

二、網(wǎng)絡(luò)編碼和機會路由

網(wǎng)絡(luò)編碼起始于Ahlswede，Cai等的一篇開創(chuàng)性論文。該論文指出，傳統(tǒng)路由的基本作用是存儲和轉(zhuǎn)發(fā)，假設(shè)允許網(wǎng)絡(luò)中間節(jié)點對傳輸?shù)男畔⒖梢赃M(jìn)行簡單的編碼處理，那么基于新路由參與的網(wǎng)絡(luò)多播就能夠達(dá)到理論上的最大傳輸容量。這也引出了最大流最小割原理：一個網(wǎng)絡(luò)的最大多播吞吐量等于分割源節(jié)點和目的節(jié)點的最小割集容量。隨著研究的深入，研究者發(fā)現(xiàn)，網(wǎng)絡(luò)編碼不僅能改善網(wǎng)絡(luò)的吞吐量，在均衡網(wǎng)絡(luò)負(fù)載，降低節(jié)點能耗，提高網(wǎng)絡(luò)安全性等方面也有較好的表現(xiàn)。

機會路由（也稱機會轉(zhuǎn)發(fā)）的概念是2004年由麻省理工學(xué)院的Biswas等人提出。機會路由中每個節(jié)點都有自己的一個候選轉(zhuǎn)發(fā)節(jié)點集合，每次傳遞信息時，并沒有確定下一跳節(jié)點，而是根據(jù)廣播數(shù)據(jù)分組來選擇合適的候選節(jié)點，通過對比接收到分組數(shù)據(jù)的應(yīng)答順序給出候選節(jié)點的優(yōu)先級，從而選擇最佳的下一跳來轉(zhuǎn)發(fā)數(shù)據(jù)。機會路由的突出優(yōu)點是增加單跳傳輸?shù)目煽啃?，減少總的傳輸跳數(shù)來提高吞吐量。

三、主流協(xié)議

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

與之對應(yīng)的流間網(wǎng)絡(luò)編碼機會路由協(xié)議主要有CAOR，BEND和PACE。CAOR協(xié)議是在COPE協(xié)議的基礎(chǔ)上引入了機會路由策略。它可以提高多流無線網(wǎng)絡(luò)的吞吐量。具體做法是將編碼效率高的節(jié)點加入轉(zhuǎn)發(fā)節(jié)點集，通過排序選擇較高的編碼節(jié)點。這需要維護(hù)相鄰兩跳節(jié)點的信息。BEND協(xié)議相比較CAOR是實現(xiàn)在MAC層上的，PACE協(xié)議引入了區(qū)域聯(lián)合編碼與傳輸算法，它實行了網(wǎng)絡(luò)多點聯(lián)合編碼，以增益的大小來對轉(zhuǎn)發(fā)節(jié)點進(jìn)行排序。它的優(yōu)勢在于減少了碰撞，提高了系統(tǒng)的傳輸效率。

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

四、結(jié)語

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