基于機會的網(wǎng)絡(luò)編碼方法(COPE)研究網(wǎng)絡(luò)編碼在無線環(huán)境中的協(xié)議層面上具體實現(xiàn)的問題,但COPE被動地等待編碼機會的出現(xiàn)。為了更大限度的提高網(wǎng)絡(luò)編碼的性能,需要將網(wǎng)絡(luò)編碼與無線路由協(xié)議相結(jié)合來在無線節(jié)點上創(chuàng)造出更多的編碼機會以減少總的傳輸次數(shù),以有效的提升網(wǎng)絡(luò)的吞吐量。當前的編碼感知路由算法主要包括基于Markovian路由度量的路由協(xié)議、編碼感知機會路由協(xié)議(CORE)、分布式編碼感知路由協(xié)議(DCAR)、速率匹配的編碼感知多路徑路由協(xié)議(RCR)、編碼感知多路徑路由協(xié)議(CAMP)等。無線網(wǎng)絡(luò)內(nèi)的編碼感知路由領(lǐng)域中新型路由度量和跨層設(shè)計等問題還需要進一步研究。
網(wǎng)絡(luò)編碼(NC)使得網(wǎng)絡(luò)節(jié)點既實現(xiàn)路由功能又實現(xiàn)編碼功能,已被證明是可以逼近網(wǎng)絡(luò)容量理論傳輸極限的有效方法。2000年,R.Ahlswede等人發(fā)表了文章“Network informatiON flow”證明了組播網(wǎng)絡(luò)在網(wǎng)絡(luò)編碼傳輸模式下可以達到極大流容量理論上限。網(wǎng)絡(luò)編碼剛提出的幾年,研究工作主要集中在網(wǎng)絡(luò)編碼的理論以及構(gòu)造和應(yīng)用等方面。從2005年后,許多國外學者開始研究無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼,然而網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)(包括無線自組織網(wǎng)絡(luò)、無線Mesh網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò))的研究和應(yīng)用還處于起步的階段。
無線網(wǎng)絡(luò)與有線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼的理論和應(yīng)用有著顯著的差別,這主要是由無線網(wǎng)絡(luò)的結(jié)構(gòu)特征決定的。同時無線網(wǎng)絡(luò)環(huán)境也是網(wǎng)絡(luò)編碼非常適宜的一個應(yīng)用領(lǐng)域。因為無線鏈路的不可靠性和物理層廣播特性非常適合使用編碼的方法。相對于傳統(tǒng)網(wǎng)絡(luò)編碼機制來說,無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼尤其能夠增加單播流的吞吐量,這也是無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼與傳統(tǒng)網(wǎng)絡(luò)編碼主要區(qū)別之一,這同樣得益于無線介質(zhì)的廣播特性。圖1所示為一無線網(wǎng)絡(luò)中3節(jié)點使用網(wǎng)絡(luò)編碼進行通信的例子:節(jié)點A、節(jié)點B相互傳遞信息p1、p2。圖1中的箭頭代表無線鏈路。圖1(a)采用傳統(tǒng)的無線通信方式,這樣需要4次傳輸來完成報文的交換。但是如果利用無線介質(zhì)的廣播特性,將p1和p2作異或運算后直接轉(zhuǎn)發(fā)出去,則在節(jié)點B處,根據(jù)接收到的信息可恢復(fù)出p1來;同理,在節(jié)點A處也可以恢復(fù)出信息p2來。因此采用了網(wǎng)絡(luò)編碼技術(shù)后(見圖1(b)),只需要使用3次傳輸就可以實現(xiàn)傳統(tǒng)方式的所有通信要求。
?
基于上述思想,Katti等提出基于機會的網(wǎng)絡(luò)編碼方法(COPE),COPE是首次研究網(wǎng)絡(luò)編碼在無線環(huán)境中的協(xié)議層面上具體實現(xiàn)的問題。COPE協(xié)議使用機會監(jiān)聽以及接收報告來獲取鄰居節(jié)點所存儲的報文信息。在得到所有鄰居節(jié)點所存儲的報文信息后,每個節(jié)點獨立的利用本地信息決定哪些數(shù)據(jù)包需要進行編碼以及如何進行編碼,以最大化一次傳輸中所能夠發(fā)送的報文數(shù)量。通過COPE,無線網(wǎng)絡(luò)的吞吐量可以得到有效的提高。
1 無線網(wǎng)絡(luò)中的編碼感知路由協(xié)議
當前的無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼協(xié)議,如COPE等方案多半被動的等待編碼機會的出現(xiàn),這種被動的策略很大程度上限制了網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)吞吐量的能力。為了更大限度的提高網(wǎng)絡(luò)編碼的性能,需要更有效的方案來在無線節(jié)點上創(chuàng)造出更多的編碼機會以減少總的傳輸次數(shù),以有效的提升網(wǎng)絡(luò)的吞吐量。
從COPE協(xié)議中可以看出,節(jié)點上的編碼機會多少主要是由節(jié)點附近的流模式所決定的。路由協(xié)議的主要功能就是完成網(wǎng)絡(luò)流的路由和尋址。因此如果將無線網(wǎng)絡(luò)路由機制與網(wǎng)絡(luò)編碼機制進行有效的結(jié)合,設(shè)計出編碼感知的無線自組織網(wǎng)絡(luò)路由協(xié)議,為節(jié)點創(chuàng)造出更多的編碼機會,就能有效的提高網(wǎng)絡(luò)的吞吐量。如圖2所示,有兩個網(wǎng)絡(luò)流,分別為從A到E以及從F到A。如果采用傳統(tǒng)的最短路徑路由機制,則兩個流的路徑分別為A→B→C→E以及F→D→B→A。網(wǎng)絡(luò)中沒有編碼機會。如果從F到A的路徑變?yōu)镕→E→C→B→A,雖然比最短路徑多了一跳。但是在節(jié)點C和B出創(chuàng)造出了編碼機會,從而有效的提升了網(wǎng)絡(luò)的吞吐量。
?
下面將分別介紹采用不同策略進行編碼感知路由的協(xié)議,著重介紹各協(xié)議的主要工作機制,并討論它們的優(yōu)缺點。
無線自組織網(wǎng)絡(luò)中的編碼感知路由主要可以分為兩大類:集中式和分布式。
1.1 集中式算法
Sengupta等人首次從理論分析的角度給出了COPE類型的網(wǎng)絡(luò)編碼機制在無線網(wǎng)絡(luò)中所能帶來的吞吐量提升。方案通過線性優(yōu)化的方式給出了如何計算任意無線多跳網(wǎng)絡(luò)拓撲以及任意多并發(fā)單播流量模式下的網(wǎng)絡(luò)吞吐量,同時研究了無線路由選擇與編碼機會多少的折中,即將網(wǎng)絡(luò)中并發(fā)的多個單播流以“靠近的路由方式”路由以獲得更多編碼機會,還是以“遠離的路由方式”方式路由以減少無線干擾。同時考慮節(jié)點間無線廣播傳輸?shù)恼{(diào)度,以適應(yīng)無線發(fā)送/傳輸?shù)亩鄻有砸约版溌烽g的干擾。模擬結(jié)果顯示如果路由能夠感知編碼機會的存在,則網(wǎng)絡(luò)的吞吐量能夠比單純的應(yīng)用COPE類型的網(wǎng)絡(luò)編碼得到顯著的提高。
Ni等人從另一個角度對編碼感知的路由協(xié)議對網(wǎng)絡(luò)的吞吐量所帶來的提升做出了理論上的分析。協(xié)議定義了期望的編碼傳輸數(shù)目(ECX)。與傳統(tǒng)無線網(wǎng)絡(luò)路由協(xié)議所采用的度量,如跳數(shù)、期望傳輸數(shù)目(ETX)等不同,ECX定義了兩個節(jié)點通過一個中間節(jié)點采用網(wǎng)絡(luò)編碼機制后成功交換報文所需的傳輸次數(shù)。在定義了ECX后,協(xié)議將編碼感知的路由問題轉(zhuǎn)化為一個線性優(yōu)化的問題。模擬結(jié)果同樣顯示編碼感知的路由可以有效提升網(wǎng)絡(luò)的吞吐量。
?
1.2 分布式算法
集中式算法能夠從全局對算法進行優(yōu)化,然而算法的復(fù)雜度較高、需要的網(wǎng)絡(luò)信息量大,不適用動態(tài)無線網(wǎng)絡(luò)(包括網(wǎng)絡(luò)動態(tài)和流量動態(tài))。在分布式的編碼感知路由算法中,每個節(jié)點都獨立地根據(jù)自己保存的網(wǎng)絡(luò)狀態(tài)信息作出路由決定,因而具有較低的協(xié)議開銷以及復(fù)雜度,更適用于動態(tài)無線網(wǎng)絡(luò)。
(1)基于Markovian的路由度量
Wu[7]提出了基于Markovian的路由度量來進行編碼感知的路由。Markovian度量指出在某鏈路上發(fā)送報文的代價,可能會依賴于該報文的前一跳節(jié)點,因此能夠有效地衡量出使用網(wǎng)絡(luò)編碼的情況下某條路徑的路由代價。但是,Markovian度量的主要問題在于,它只能發(fā)現(xiàn)某條鏈路上是否存在編碼機會,而不能發(fā)現(xiàn)該鏈路上編碼機會的多少,因此可能無法找出編碼機會最多的路徑。
?。?)分布式編碼感知路由協(xié)議
分布式編碼感知路由協(xié)議(DCAR)能夠找出源和目的節(jié)點間的潛在路徑,并能找出這些路徑上的所有潛在網(wǎng)絡(luò)編碼機會而不僅是兩跳拓撲內(nèi)的編碼機會。源節(jié)點首先發(fā)送路徑請求(RREQ)消息,RREQ消息所經(jīng)過的所有節(jié)點都將其一跳鄰居記錄在RREQ消息中的“誰能監(jiān)聽”節(jié)點列表中。目的節(jié)點接收到RREQ消息后,向源節(jié)點返回路徑回復(fù)(RREP)消息。中間節(jié)點接收到RREP消息后,根據(jù)“誰能監(jiān)聽”信息檢查此流能否與現(xiàn)有經(jīng)過該節(jié)點的流進行編碼。當RREP消息返回到源節(jié)點后,源節(jié)點根據(jù)RREP消息中包含的潛在編碼機會作出路由選擇,找出所有具有潛在網(wǎng)絡(luò)編碼機會的路徑。然而編碼機會最多的路徑不一定能夠帶來最好的性能,該路徑可能過長,或者已經(jīng)嚴重擁塞。某些不具備編碼機會的路徑可能反而具有較高的吞吐量。DCAR綜合考慮了編碼機會,擁塞等因素,定義了新的編碼感知度量(CRM)用于衡量某條路徑上期望的傳輸次數(shù)。將CRM與路由發(fā)現(xiàn)過程相結(jié)合,DCAR能夠找出能夠有效提升網(wǎng)絡(luò)吞吐量的路由。
?。?)速率匹配的編碼感知多路徑路由協(xié)議
當前的大多數(shù)的網(wǎng)絡(luò)編碼方案都假定參與編碼不同的流之間的速率是一致的,而沒有考慮速率不同的流之間的網(wǎng)絡(luò)編碼問題。文獻提出了速率匹配的編碼感知多路徑路由協(xié)議(RCR)。該協(xié)議能夠?qū)⒁粋€流分割成多個流以便于有效的實現(xiàn)流之間的速率匹配,從而有效地提升網(wǎng)絡(luò)編碼的效率。同時當前大多數(shù)無線網(wǎng)絡(luò)中的路由協(xié)議都選擇基于無線鏈路狀態(tài)的度量,但是對于網(wǎng)絡(luò)編碼來說,基于鏈路狀態(tài)的度量并不一定是最佳的選擇。因此,RCR定義了多個基于節(jié)點的路由度量,分別用于衡量某路徑的編碼機會的多少,路徑的匹配編碼速率以及該路徑的擁塞避免速率。
在路由發(fā)現(xiàn)階段,源節(jié)點向網(wǎng)絡(luò)中廣播RREQ消息,當RREQ經(jīng)過網(wǎng)絡(luò)中的中間節(jié)點時,節(jié)點將該節(jié)點的路由度量記錄在RREQ消息中。目的節(jié)點收到多個RREQ消息后,分別計算出不同路徑的所需傳輸數(shù)目,流量匹配速率以及擁塞避免速率。目的節(jié)點根據(jù)這些度量選擇路徑,并對不同的路徑分配速率,并沿著選擇的路徑返回RREP消息。源節(jié)點接收到RREP消息后,根據(jù)不同路徑分配的速率在多個路徑對流進行傳輸。
?。?)編碼感知多路徑路由協(xié)議
編碼感知多路徑路由協(xié)議(CAMP)同樣利用多路徑以及分流來增大網(wǎng)絡(luò)中的編碼機會。CAMP協(xié)議提出了一種新的路徑轉(zhuǎn)換增益,用于衡量路由應(yīng)該轉(zhuǎn)換至哪條路徑以帶來較多的增益。在路由發(fā)現(xiàn)階段,CAMP依據(jù)ETX信息,為源節(jié)點找出多個可用的路徑。每個路徑的中間節(jié)點都緩存多個可能的路由候選者,為將來的路徑轉(zhuǎn)換做好準備。在報文轉(zhuǎn)發(fā)的過程中,CAMP動態(tài)的將缺省路徑轉(zhuǎn)換至新的能夠最大化編碼增益以及路徑轉(zhuǎn)換增益的路徑上。CAMP的問題在于其所尋找的多路徑需要在一定范圍內(nèi)互相臨近,以便于中間節(jié)點能夠轉(zhuǎn)換路徑,因此不能完全利用多路徑的多樣性。
?。?)編碼感知機會路由協(xié)議
雖然上述協(xié)議都不同程度地實現(xiàn)了編碼感知的路由,但是,上述協(xié)議都基于傳統(tǒng)的最短路徑路由,每個節(jié)點的下一跳都是預(yù)先確定的,這對于信道并不可靠的無線網(wǎng)絡(luò)來說可能會導(dǎo)致報文的多次重傳。
機會路由作為新的研究熱點,已經(jīng)被證明能夠有效地提高無線網(wǎng)絡(luò)的吞吐量。機會路由同樣利用了無線傳輸媒介的廣播特性,每個節(jié)點維護一個轉(zhuǎn)發(fā)節(jié)點集合作為可能的下一跳,具有最優(yōu)路由的節(jié)點的成為實際的下一跳節(jié)點。機會路由大大降低了報文丟失和重傳的機率,同時利用那些離目的節(jié)點較近但是信道情況較差的無線鏈路,能夠有效地降低傳輸次數(shù)。
編碼感知機會路由(CORE)協(xié)議有效的結(jié)合了流間網(wǎng)絡(luò)編碼與機會路由。在某個節(jié)點發(fā)出報文之前,節(jié)點首先選擇轉(zhuǎn)發(fā)集作為可能的下一跳。轉(zhuǎn)發(fā)集中的所有節(jié)點都獨立計算本次傳輸?shù)木幋a機會,并根據(jù)其編碼機會的多少來進行衡量其發(fā)送的優(yōu)先級。每個節(jié)點維護一個定時器,編碼機會較多的節(jié)點定時器觸發(fā)較早。當定時器觸發(fā)時,節(jié)點進行傳輸。如果節(jié)點監(jiān)聽到了該報文被其他節(jié)點傳輸,則取消定時器。CORE可以同時得到網(wǎng)絡(luò)編碼和機會路由對無線網(wǎng)絡(luò)所帶來的增益。試驗結(jié)果顯示,CORE可以有效提升網(wǎng)絡(luò)的吞吐量。
(6)MAC無關(guān)機會路由
MAC無關(guān)機會路由(MORE)將流內(nèi)隨機網(wǎng)絡(luò)編碼與機會路由相結(jié)合。當源節(jié)點發(fā)送數(shù)據(jù)時,將所要發(fā)送的原始數(shù)據(jù)分成批,例如把每K個包作為一批。源節(jié)點將每一批數(shù)據(jù)包做隨機線性編碼后,不停地廣播出去,每個分組攜帶其編碼向量。中間轉(zhuǎn)發(fā)節(jié)點只接受創(chuàng)新數(shù)據(jù)包(Innovative數(shù)據(jù)包),即:收到一個包后,首先判斷它與本地已經(jīng)收到的屬于該批的數(shù)據(jù)包是否線性獨立,如果線性獨立則將新數(shù)據(jù)包存入緩存,否則丟棄該包。當收到屬于同一批次的K個Innovative數(shù)據(jù)包后,目的節(jié)點就可以恢復(fù)出原始K個數(shù)據(jù)包,并向源節(jié)點回送ACK包。源節(jié)點收到ACK后,進行下一批數(shù)據(jù)包的發(fā)送。試驗結(jié)果顯示,與ExOR相比,MORE可以大大提高分組成功投遞率。
?。?)最優(yōu)化多路徑網(wǎng)絡(luò)編碼協(xié)議
最優(yōu)化多路徑網(wǎng)絡(luò)編碼協(xié)議(OMNC)將線性隨機編碼,速率控制與機會路由協(xié)議相結(jié)合以增大網(wǎng)絡(luò)中的編碼增益。OMNC以基于優(yōu)化的方式控制編碼報文在易丟失的無線環(huán)境中的傳輸。利用媒體訪問控制(MAC)協(xié)議的廣播特性,使得一次傳輸能夠被多個下游節(jié)點所監(jiān)聽。利用隨機網(wǎng)絡(luò)編碼的特性,OMNC能夠保證單播傳輸?shù)目煽啃远恍枰溌穼拥闹貍鳈C制。
與MORE協(xié)議相似,在OMNC中,端到端的傳輸是由編碼報文在多個機會的路徑上所完成的。然而與MORE不同,OMNC將每個節(jié)點的編碼以及廣播速率與其信道狀態(tài)相匹配,以有效的避免擁塞,更好利用路徑的多樣性,減少冗余報文的傳輸。只要網(wǎng)絡(luò)中的節(jié)點能夠進行線性編解碼操作,OMNC就能很好的提升易丟失無線網(wǎng)絡(luò)的吞吐量。
(8)區(qū)域聯(lián)合編碼與傳輸調(diào)度算法
傳統(tǒng)網(wǎng)絡(luò)編碼機制著眼于最大化單次傳輸內(nèi)所包含的報文個數(shù)來最大化無線網(wǎng)絡(luò)的吞吐量。然而,這種從單個節(jié)點的角度來最大化網(wǎng)絡(luò)編碼增益的做法,實際上卻有可能損害整個網(wǎng)絡(luò)的編碼增益。如果每個節(jié)點能夠考慮到鄰居節(jié)點的編碼增益進行編碼傳輸?shù)脑?,整個網(wǎng)絡(luò)的編碼增益有可能得到進一步提升。在區(qū)域聯(lián)合編碼與傳輸調(diào)度算法(PACE)中,節(jié)點每次轉(zhuǎn)發(fā)都著眼于提升節(jié)點附近區(qū)域中的整體編碼增益,同時使用編碼感知的傳輸調(diào)度來保證編碼機會的實現(xiàn)。PACE使用區(qū)域編碼增益作為節(jié)點傳輸?shù)膬?yōu)先級,以此為優(yōu)先級來對傳輸進行調(diào)度,保證臨近節(jié)點的最佳傳輸順序以最大化區(qū)域的網(wǎng)絡(luò)編碼增益,同時有效的減輕碰撞的發(fā)生,有效的提升網(wǎng)絡(luò)性能。
2 結(jié)束語
本文綜述了已有編碼感知路由協(xié)議的基本思想和主要協(xié)議。已有工作顯示,網(wǎng)絡(luò)編碼感知的路由協(xié)議能夠顯著提高包括Ad Hoc網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)和無線Mesh網(wǎng)絡(luò)等在內(nèi)的無線多跳網(wǎng)絡(luò)的性能。但作為一個無線網(wǎng)絡(luò)領(lǐng)域的新技術(shù),無線網(wǎng)絡(luò)內(nèi)的編碼感知路由領(lǐng)域還有很多問題需要進一步研究。
(1)新型路由度量
路由度量對路由協(xié)議的性能具有重要影響。已有編碼感知路由協(xié)議主要以編碼機會的多少、ETX、地理距離、擁塞程度等作為主要度量來設(shè)計編碼感知的路由協(xié)議。引入新的路由度量有可能提出更有效的編碼感知路由協(xié)議。
?。?)跨層設(shè)計
現(xiàn)有的編碼感知路由協(xié)議主要著重于路由層的協(xié)議設(shè)計。除此之外,MAC層的接入,高丟失無線信道所帶來的重傳等也是影響網(wǎng)絡(luò)編碼性能的重要因素。綜合考慮上述因素以及應(yīng)用的特點,進行編碼感知跨層研究,對無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼性能將起到較好的促進作用。結(jié)合編碼感知鏈路調(diào)度的網(wǎng)絡(luò)編碼感知路由能夠極大地提高網(wǎng)絡(luò)性能,值得進一步深入研究。
評論
查看更多