1 無線網(wǎng)絡中的編碼感知路由協(xié)議

　　當前的無線網(wǎng)絡中的網(wǎng)絡編碼協(xié)議，如COPE等方案多半被動的等待編碼機會的出現(xiàn)，這種被動的策略很大程度上限制了網(wǎng)絡編碼提高網(wǎng)絡吞吐量的能力。為了更大限度的提高網(wǎng)絡編碼的性能，需要更有效的方案來在無線節(jié)點上創(chuàng)造出更多的編碼機會以減少總的傳輸次數(shù)，以有效的提升網(wǎng)絡的吞吐量。

　　從COPE協(xié)議中可以看出，節(jié)點上的編碼機會多少主要是由節(jié)點附近的流模式所決定的。路由協(xié)議的主要功能就是完成網(wǎng)絡流的路由和尋址。因此如果將無線網(wǎng)絡路由機制與網(wǎng)絡編碼機制進行有效的結合，設計出編碼感知的無線自組織網(wǎng)絡路由協(xié)議，為節(jié)點創(chuàng)造出更多的編碼機會，就能有效的提高網(wǎng)絡的吞吐量。如圖2所示，有兩個網(wǎng)絡流，分別為從A到E以及從F到A。如果采用傳統(tǒng)的最短路徑路由機制，則兩個流的路徑分別為A→B→C→E以及F→D→B→A。網(wǎng)絡中沒有編碼機會。如果從F到A的路徑變?yōu)镕→E→C→B→A，雖然比最短路徑多了一跳。但是在節(jié)點C和B出創(chuàng)造出了編碼機會，從而有效的提升了網(wǎng)絡的吞吐量。

?

　　下面將分別介紹采用不同策略進行編碼感知路由的協(xié)議，著重介紹各協(xié)議的主要工作機制，并討論它們的優(yōu)缺點。

　　無線自組織網(wǎng)絡中的編碼感知路由主要可以分為兩大類：集中式和分布式。

　　1.1 集中式算法

　　Sengupta等人首次從理論分析的角度給出了COPE類型的網(wǎng)絡編碼機制在無線網(wǎng)絡中所能帶來的吞吐量提升。方案通過線性優(yōu)化的方式給出了如何計算任意無線多跳網(wǎng)絡拓撲以及任意多并發(fā)單播流量模式下的網(wǎng)絡吞吐量，同時研究了無線路由選擇與編碼機會多少的折中，即將網(wǎng)絡中并發(fā)的多個單播流以“靠近的路由方式”路由以獲得更多編碼機會，還是以“遠離的路由方式”方式路由以減少無線干擾。同時考慮節(jié)點間無線廣播傳輸?shù)恼{(diào)度，以適應無線發(fā)送/傳輸?shù)亩鄻有砸约版溌烽g的干擾。模擬結果顯示如果路由能夠感知編碼機會的存在，則網(wǎng)絡的吞吐量能夠比單純的應用COPE類型的網(wǎng)絡編碼得到顯著的提高。

　　Ni等人從另一個角度對編碼感知的路由協(xié)議對網(wǎng)絡的吞吐量所帶來的提升做出了理論上的分析。協(xié)議定義了期望的編碼傳輸數(shù)目（ECX）。與傳統(tǒng)無線網(wǎng)絡路由協(xié)議所采用的度量，如跳數(shù)、期望傳輸數(shù)目（ETX）等不同，ECX定義了兩個節(jié)點通過一個中間節(jié)點采用網(wǎng)絡編碼機制后成功交換報文所需的傳輸次數(shù)。在定義了ECX后，協(xié)議將編碼感知的路由問題轉化為一個線性優(yōu)化的問題。模擬結果同樣顯示編碼感知的路由可以有效提升網(wǎng)絡的吞吐量。

?

1.2 分布式算法

　　集中式算法能夠從全局對算法進行優(yōu)化，然而算法的復雜度較高、需要的網(wǎng)絡信息量大，不適用動態(tài)無線網(wǎng)絡（包括網(wǎng)絡動態(tài)和流量動態(tài)）。在分布式的編碼感知路由算法中，每個節(jié)點都獨立地根據(jù)自己保存的網(wǎng)絡狀態(tài)信息作出路由決定，因而具有較低的協(xié)議開銷以及復雜度，更適用于動態(tài)無線網(wǎng)絡。

　　（1）基于Markovian的路由度量

　　Wu[7]提出了基于Markovian的路由度量來進行編碼感知的路由。Markovian度量指出在某鏈路上發(fā)送報文的代價，可能會依賴于該報文的前一跳節(jié)點，因此能夠有效地衡量出使用網(wǎng)絡編碼的情況下某條路徑的路由代價。但是，Markovian度量的主要問題在于，它只能發(fā)現(xiàn)某條鏈路上是否存在編碼機會，而不能發(fā)現(xiàn)該鏈路上編碼機會的多少，因此可能無法找出編碼機會最多的路徑。

　　（2）分布式編碼感知路由協(xié)議

　　分布式編碼感知路由協(xié)議（DCAR）能夠找出源和目的節(jié)點間的潛在路徑，并能找出這些路徑上的所有潛在網(wǎng)絡編碼機會而不僅是兩跳拓撲內(nèi)的編碼機會。源節(jié)點首先發(fā)送路徑請求（RREQ）消息，RREQ消息所經(jīng)過的所有節(jié)點都將其一跳鄰居記錄在RREQ消息中的“誰能監(jiān)聽”節(jié)點列表中。目的節(jié)點接收到RREQ消息后，向源節(jié)點返回路徑回復（RREP）消息。中間節(jié)點接收到RREP消息后，根據(jù)“誰能監(jiān)聽”信息檢查此流能否與現(xiàn)有經(jīng)過該節(jié)點的流進行編碼。當RREP消息返回到源節(jié)點后，源節(jié)點根據(jù)RREP消息中包含的潛在編碼機會作出路由選擇，找出所有具有潛在網(wǎng)絡編碼機會的路徑。然而編碼機會最多的路徑不一定能夠帶來最好的性能，該路徑可能過長，或者已經(jīng)嚴重擁塞。某些不具備編碼機會的路徑可能反而具有較高的吞吐量。DCAR綜合考慮了編碼機會，擁塞等因素，定義了新的編碼感知度量（CRM）用于衡量某條路徑上期望的傳輸次數(shù)。將CRM與路由發(fā)現(xiàn)過程相結合，DCAR能夠找出能夠有效提升網(wǎng)絡吞吐量的路由。

　?。?）速率匹配的編碼感知多路徑路由協(xié)議

　　當前的大多數(shù)的網(wǎng)絡編碼方案都假定參與編碼不同的流之間的速率是一致的，而沒有考慮速率不同的流之間的網(wǎng)絡編碼問題。文獻提出了速率匹配的編碼感知多路徑路由協(xié)議（RCR）。該協(xié)議能夠將一個流分割成多個流以便于有效的實現(xiàn)流之間的速率匹配，從而有效地提升網(wǎng)絡編碼的效率。同時當前大多數(shù)無線網(wǎng)絡中的路由協(xié)議都選擇基于無線鏈路狀態(tài)的度量，但是對于網(wǎng)絡編碼來說，基于鏈路狀態(tài)的度量并不一定是最佳的選擇。因此，RCR定義了多個基于節(jié)點的路由度量，分別用于衡量某路徑的編碼機會的多少，路徑的匹配編碼速率以及該路徑的擁塞避免速率。

　　在路由發(fā)現(xiàn)階段，源節(jié)點向網(wǎng)絡中廣播RREQ消息，當RREQ經(jīng)過網(wǎng)絡中的中間節(jié)點時，節(jié)點將該節(jié)點的路由度量記錄在RREQ消息中。目的節(jié)點收到多個RREQ消息后，分別計算出不同路徑的所需傳輸數(shù)目，流量匹配速率以及擁塞避免速率。目的節(jié)點根據(jù)這些度量選擇路徑，并對不同的路徑分配速率，并沿著選擇的路徑返回RREP消息。源節(jié)點接收到RREP消息后，根據(jù)不同路徑分配的速率在多個路徑對流進行傳輸。

　?。?）編碼感知多路徑路由協(xié)議

　　編碼感知多路徑路由協(xié)議（CAMP）同樣利用多路徑以及分流來增大網(wǎng)絡中的編碼機會。CAMP協(xié)議提出了一種新的路徑轉換增益，用于衡量路由應該轉換至哪條路徑以帶來較多的增益。在路由發(fā)現(xiàn)階段，CAMP依據(jù)ETX信息，為源節(jié)點找出多個可用的路徑。每個路徑的中間節(jié)點都緩存多個可能的路由候選者，為將來的路徑轉換做好準備。在報文轉發(fā)的過程中，CAMP動態(tài)的將缺省路徑轉換至新的能夠最大化編碼增益以及路徑轉換增益的路徑上。CAMP的問題在于其所尋找的多路徑需要在一定范圍內(nèi)互相臨近，以便于中間節(jié)點能夠轉換路徑，因此不能完全利用多路徑的多樣性。