流內編碼中考慮鏈路相關性的機會路由機制

陳朝輝，楊 湘，李 鵬，何 亨

武漢科技大學 計算機科學與技術學院，武漢430065

1 引言

傳統的路由機制中，轉發路徑是確定的。由于無線鏈路的廣播特性，非轉發節點也有可能監聽到數據包，但這些節點必須丟棄掉已收到的數據包，即使它們可能更“接近”目的節點。這顯然會導致網絡資源的浪費。對此，Biswas 和Morris 兩人提出了機會路由ExOR[1]，允許任何監聽到數據包并且更“接近”目的節點的中間節點參與數據包的轉發。由于要從多個候選節點中選取出最“接近”目的節點的那一個，機會路由在Mac層上引入了嚴格的調度機制，帶來了比傳統固定路徑的無線路由更高的傳輸可靠性和端到端的吞吐量[2]，但是這種嚴格的調度機制使得協議的設計與實現變得很復雜并且難以拓展到多播網絡中。Chachulski首次將隨機線性網絡編碼和機會路由相結合，提出一種節點間無需嚴格調度的路由機制MORE[3]，在引入網絡編碼后有效地解決了數據傳輸過程中節點協作難的問題，并且支持多播網絡。

目前，結合網絡編碼與機會路由的研究需要解決的問題是中間節點需要轉發多少數量的編碼包。因為理想數量的編碼包不僅能避免重復傳輸，也能保證目的節點成功解碼[4]。解決方案主要有兩種：第一種方法是基于平均鏈路丟包率計算期望轉發次數，在這種情況下，需要端到端地反饋來確認目的節點是否成功解碼。例如，針對MORE協議要求源節點只有在目的節點成功解碼出原數據包后才發送下一批編碼包的缺陷，CodeOR[5]（Coding in Opportunistic Routing）提出通過滑動窗口的機制讓源節點同時發送多批次的編碼包。PipelineOR[6]受MORE協議的啟發，提出讓中間節點代替源節點進行數據包的傳輸。SlideOR[7]中提出了一種每個batch中數據包的數目（即batch size）可調節的流內編碼機會路由機制，根據接收端的反饋信息自適應地調整batch size的大小。第二種方法要求中間節點實時檢測鏈路的質量并逐跳反饋在數據包上。例如CCACK[8]（Cumulative Coded ACKnowledgment）通過逐跳反饋的方式讓上游節點獲悉下游節點接收線性無關編碼包的情況，并及時停止當前“塊”編碼包的發送，以減少不必要的編碼包傳輸，提高網絡的吞吐量。這種通過下游節點逐跳反饋的方式，能夠幫助上游節點檢測鏈路質量并充分利用有限的網絡資源。但是，以上這些結合網絡編碼的機會路由機制均是在假設鏈路丟包相互獨立的基礎上進行設計的。

已有研究[9-11]表明無線網絡中的鏈路之間呈現相關性：無線網絡中相鄰的接收節點可能會受到相同干擾源的影響，因而鏈路的丟包是相關的。鏈路相關性會導致機會路由、網絡編碼、協作轉發等機制在計算相關指標時出現誤差，從而影響協議的性能。目前已有研究人員結合鏈路相關性對現有協議做出改進。文獻[12]分析了鏈路相關性對機會路由機制中節點轉發次數的影響，提出LCAOR 機制，通過選取低相關性鏈路的節點作為轉發節點以提高機會路由的性能。文獻[13]考慮鏈路相關性，結合網絡編碼提出一種機會路由中的分布式算法，可以適應無線信道中丟包率的變化以及鏈路相關性的影響，用來確定中間節點轉發編碼包的數量。文獻[14]提出LCOR 機制，在機會路由機制中考慮鏈路相關性，使用聯合丟包率衡量多條鏈路之間的相關性，同時提出子集質量指數（SQI）用來衡量無線mesh 網絡中節點集的質量，進而選取轉發節點。以上機制或是僅在路由機制中考慮鏈路相關性而未結合網絡編碼，或是僅僅考慮節點需要轉發多少編碼包而未說明如何選取轉發節點。

對此，本文提出了一種考慮鏈路相關性的網絡編碼機會路由機制：NCCLCOR（Network Coding based Opportunistic Routing Considering Link Correlation），在計算節點轉發次數與選取轉發節點集合時考慮鏈路丟包率與鏈路相關性。本文的主要研究工作分為以下三個部分：

（1）分析鏈路相關性對節點轉發次數以及轉發節點選取的影響。

（2）考慮鏈路相關性，提出更合理的節點轉發次數計算方法以及轉發節點選取算法。

（3）進行實驗分析改進后的算法性能。

2 鏈路相關性對節點轉發次數與轉發節點選取的影響

2.1 鏈路相關性

由于無線網絡自身通信信道易變的特性以及外界環境的干擾等因素，無線網絡中的鏈路丟包率可能會發生改變。ExOR協議以及后來結合網絡編碼的機會路由協議卻都是在忽略鏈路相關性的前提下進行設計的，而ExOR 的作者在文獻[1]中的5.6 節也提到：如果所有的丟包都是由低信噪比與多徑衰落引起的，那么鏈路丟包相互獨立的假設是合理的。但是實際上多個接收節點的丟包率可能存在相關性，因為它們可能受到同一個干擾源影響造成同時丟包。相關性指不同鏈路之間丟包相關的程度，分為正相關和負相關。產生鏈路相關性的原因主要來自兩方面，共享頻段中的交叉網絡干擾（cross-network interference）和動態環境中的相關性衰減（correlated fading）[15]。交叉網絡干擾指的是：由于當前許多無線技術共享了一些非授權頻段，在這些頻段上多條數據流同時傳輸會相互干擾，導致數據包在相鄰的鏈路上同時丟失。而相關性衰減則是指由于障礙物等因素的存在，無線電波會出現屏蔽衰減（shadow fading），從而使得局部網絡中的數據丟失呈現相關性。

交叉網絡干擾如圖1（a）所示，當干擾源出現時，圖中兩個終端同時丟失數據包。當干擾源消失時，兩個終端又同時接收到數據包。這種兩個接收終端要么同時收到、要么同時丟失數據包的情況稱為正相關。相關性衰減如圖1（b）所示，左邊終端正常接收數據包，右邊由于出現移動障礙物而丟失數據包。當障礙物移動到左邊時，又導致左邊丟失而右邊能正常接收，這種情況稱為負相關。

圖1 正負相關示例

2.2 鏈路相關性對節點轉發次數的影響

流內網絡編碼中，中間節點并沒有特定的下一跳節點。因此如何確定節點的轉發次數，使得轉發節點既不會轉發重復的數據包，又能確保下一跳節點收到足夠的數據包是流內編碼機制中的重點。而鏈路相關性對轉發次數的計算有很大程度的影響。

下面以圖2 為例詳細說明鏈路相關性對轉發次數計算的影響。

圖2 鏈路相關性對節點轉發次數影響示例

如圖2所示，節點S為節點A和B的上游節點，節點C為節點A和B的下游節點?，F假設節點A和B丟失節點S發送的數據包的概率均為0.2。在S→A與S→B兩條鏈路丟包相互獨立、正相關和負相關的三種情況下分別計算節點S成功發送數據包到節點A和B的期望轉發次數。

（1）當S→A與S→B兩條鏈路丟包相互獨立時，即節點A和B接收數據包互不影響，則節點A和B同時丟包的概率為0.2×0.2，那么節點A和B中任一節點成功接收到節點S發送的數據包的概率為1-0.2×0.2,故節點S所需的平均轉發次數為1/(1-0.2×0.2)=1.04。

（2）當S→A與S→B兩條鏈路丟包呈正相關時，由于節點A和B收到的數據包是相同的，則兩個節點同時丟掉S發送的數據包的概率為0.2那么節點A和B中任一節點成功接收到節點S發送的數據包的概率為1-0.2，故節點S所需的平均轉發次數為1/(1-0.2)=1.25。

（3）當S→A與S→B兩條鏈路丟包呈負相關時，即節點A和B中任一節點收到數據包而另一個未收到，則節點A和B同時丟包的概率將小于0.2×0.2，那么節點A和B成功接收到節點S發送的數據包的概率將大于1-0.2×0.2，故節點C平均發送次數將小于1/(1-0.2×0.2)=1.04。

對比鏈路獨立與鏈路相關的兩種計算結果不難發現，基于鏈路獨立的計算結果與基于鏈路相關的計算結果相比存在誤差，這種誤差勢必會導致網絡吞吐量下降。原因在于，若某些鏈路接收數據包呈正相關，鏈路獨立的假設會使得中間節點轉發的線性無關的數據包個數不夠，進而導致目的節點無法解碼出原數據包。這時源節點不得不再發送同批次的數據包，這些數據包再經過中間節點的轉發才能最終到達目的節點，導致網絡吞吐量下降。若鏈路接收數據包呈負相關，中間節點會轉發多余的數據包給下游節點，這同樣會導致網絡吞吐量下降。

2.3 鏈路相關性對轉發節點選取的影響

鏈路相關性不僅會影響轉發節點轉發次數的計算，還會影響轉發節點的選取。下面以圖3 為例詳細解釋鏈路相關性對轉發節點選取的影響。

圖3 鏈路相關性對轉發節點選取影響示例

假設源節點s要將一個數據包發送給目的節點d，需要從f1、f2、f3三個節點中選取兩個節點作為轉發節點。圖中兩個節點連線上的數字表示兩個節點之間成功轉發數據包的概率，例如Ps,f1=0.5 表示節點f1成功接收到節點s發送的數據包的概率為0.5。在鏈路獨立與鏈路相關的兩種情況下分別計算節點s和選取的轉發節點所需的轉發次數之和。

（1）鏈路獨立：首先選擇第一個轉發節點。分別選擇f1、f2、f3作為轉發節點，計算得到各自的期望轉發次數分別為：αf1=1/0.5+1/0.6=3.67，αf2=1/0.5+1/0.6=3.67，αf3=1/0.4+1/0.6=3.89，因此選擇f1或f2中的一個節點作為第一個轉發節點。這里選擇節點f1作為第一個轉發節點。

接著選擇第二個轉發節點。若選擇節點f2，因為要保證節點f1和f2中至少有一個節點能接收到節點s發出的數據包，則節點s的期望轉發次數為：αs=1/(1-(1-Ps,f1)(1-Ps,f2))=4/3 ≈1.33，其中1-Ps,f1和1-Ps,f2分別表示鏈路s→f1和s→f2的丟包率，因為這兩條鏈路丟包相互獨立，所以公式中(1-Ps,f1)(1-Ps,f2)表示節點f1和f2都沒有接收到節點s發出的數據包的概率。節點f2收到的數據包個數為αsPs,f2，則它將這些數據包轉發給節點d的期望轉發次數為αf2=(αsPs,f2)/Pf2,d≈1.11；由于s→f1與s→f2兩條鏈路丟包率相同，可直接得到節點f1期望轉發次數為αf1=1.11；因此選擇節點f1和f2作為轉發節點集合的期望轉發次數之和為αs+αf1+αf2=3.55。

若選擇節點f3作為第二個轉發節點，同理可得αs=1.43,αf1=1.19,αf3=0.95,因此選擇節點f1和f3作為轉發節點集合的期望轉發次數之和為αs+αf1+αf3=3.57。

顯然，鏈路獨立的情況下選擇節點f1和f2作為轉發節點所需的轉發次數更少。

（2）鏈路相關：首先選擇第一個轉發節點，這里選擇節點f2。同鏈路獨立的情況類似，接著考慮節點s的期望轉發次數。由于考慮了鏈路相關性的存在，這里假設s→f1，s→f2兩條鏈路丟包呈正相關，s→f2和s→f3兩條鏈路丟包依然相互獨立。若第二個節點選擇f1則節點s的期望轉發次數為：αs=1/(1-P(。

其中Ei,j表示節點j成功接收到節點i發出數據包的事件，由于s→f1和s→f2兩條鏈路丟包呈正相關，即節點f1和f2要么同時丟包要么都未丟包，故節點f1和f2同時丟包的概率為P(=0.5 ，所以αs=2 ，αf1=αf2=(αsPs,f1)/Pf1,d≈1.66。因此選擇節點f1和f2作為轉發節點集合的期望轉發次數之和為αs+αf1+αf2=5.32。同理可得選擇節點f2和f3作為轉發節點集合的期望轉發次數之和為αs+αf2+αf3=3.57。

顯然，鏈路相關的情況下選擇節點f2和f3作為轉發節點所需的轉發次數更少。

對比上述兩種情況下選取的轉發節點不難發現，鏈路獨立的假設會影響轉發節點的選取，使得選取的轉發節點的總轉發次數更多。

3 考慮鏈路相關性的節點轉發次數計算與轉發節點選取

通過前文的分析，可以明確的是在計算節點轉發次數以及選取轉發節點時不能假設鏈路丟包相互獨立，應該考慮鏈路相關性的影響。下面將討論在考慮鏈路相關性的基礎上，如何準確地計算節點期望轉發次數以及選取轉發節點集合，并在此基礎上提出鏈路相關性指標的計算公式。

3.1 考慮鏈路相關性的節點轉發次數計算

在傳統的基于網絡編碼的機會路由機制中，普遍依據ETX（the expected transmission count metric）來進行節點轉發次數的計算以及轉發節點的選取。ETX 由DeCouto等人提出，用于在無線多跳網絡中衡量鏈路質量，定義為在無線鏈路上傳輸一個數據包到目的節點所需要的期望傳輸次數[16]。具體來說，某條傳輸路徑的ETX 值就是在該路徑上每跳的ETX 值的總和，某一跳的ETX 在數值上等于該跳的鏈路丟包率的倒數。某個節點的ETX 值即經由該節點到目的節點的路徑上所有跳的ETX 之和。以圖3 為例，節點f1的ETX 值為1/(1-0.6)=2.5。

單純依靠ETX值無法準確計算節點的期望轉發次數，下面介紹考慮鏈路相關性的節點轉發次數計算方法。

假設網絡中存在N個節點，源節點為s，目的節點為d。對于任意兩個節點i和j，i ＜j表示i比j更靠近目的節點，或者說節點i的ETX值比j小。Pi,j表示節點i和j之間的丟包率。Zi表示節點i為了將一個數據包成功從節點s發送到節點d所需的期望轉發次數?？疾煸垂濣cs發送一個數據包到目的節點d的情形，計算節點j的期望轉發次數。容易得到節點j從ETX 值比它大的節點i處收到的數據包個數為(1-Pi,j)。對于節點j收到的每個數據包而言，僅當ETX 值比它小的節點都沒有接收到該數據包時，節點j才轉發。

由于考慮到鏈路相關性，這里定義事件Ei,j，表示節點j成功接收到節點i發送的數據包的事件。節點集合φj表示ETX值比j小的集合。這樣節點j需要轉發的數據包個數Lj（或者說節點j收到的數據包個數）為：

其中，概率P表示節點j成功接收到節點i的數據包，而所有ETX 值比j小的節點k未收到這個數據包的概率。在計算出節點j收到的數據包個數后，便可以得到節點j所需的總傳輸次數為：

其中，概率P表示所有ETX 值比j小的節點k均未收到節點j發出的數據包的概率。

公式（3）中的TX_credit值為節點j從ETX值大于它的節點處收到一個線性獨立的數據包時所需的轉發次數均值。

3.2 考慮鏈路相關性的轉發節點選取

由于通過窮舉的算法得到所有可能鏈路集合的轉發次數算法復雜程度過高，所以本文采用的思路為：先找到發送次數最少的單個轉發節點，然后再循環往節點集合中加入轉發次數更少的轉發節點，最終便可得到總轉發送次數最少的轉發節點集合，或者轉發節點集合的大小達到預定值。

首先引入文獻[17]中的EAX（expected number of any-path transmissions）值這個概念。EAX 用來衡量傳輸開銷，它的含義是源節點到目的節點的多條路徑上所有節點總的傳輸次數。EAX(Fs,s,d)的定義為：考慮給定的具有鏈路相關性的轉發節點集合Fs，從源節點s成功傳輸一個數據包到目的節點d，整條路徑上所有節點總的期望轉發次數。EAX 的意義與ETX 類似，不同的是ETX 反映的是單條路徑的傳輸開銷，而EAX 值則反映了源節點到目的節點具的多條路徑同時傳輸數據時所有傳輸路徑總的傳輸開銷。EAX(Fs,s,d)的計算公式為：

公式（4）中α為轉發節點集合{ }1,2,…,N中至少有一個節點接收到節點s發出的一個數據包所需的轉發次數，β為轉發節點集合中的所有節點把數據包轉發給目的節點所需的轉發次數。α與β的計算公式如下：

公式（5）中Es,i為轉發節點i成功收到節點s發出的數據包的事件，公式（5）、（6）中N為轉發節點集合Fs中的節點個數，公式（7）中Ps,i為節點s到轉發節點i的成功接收概率。

以圖4為例介紹EAX值的計算。在圖4中，源節點s有數據包要發往目的節點d，Fs={ }1,2,…,N為源節點s的一個轉發節點集合。

圖4 EAX值計算示例

網絡中節點s周期性收集其所有下游節點成功收到數據包的信息，將此信息發送給各下游節點，所有下游節點根據此信息計算包含自己在內的節點集合{ }1,2,…,N中節點均未能收到某個數據包的概率P()。

EAX值的計算從目的節點d開始。顯然d的EAX值為0，由此可以計算出節點d的上一跳節點的EAX值，并由此依次循環計算出所有節點的EAX 值。此外在EAX(Fs,s,d)的計算中，對于相同的節點s和d，由于轉發節點集合F的選取不同，會存在多個不同的EAX值，因此選取其中的最小值作為這個節點的EAX值。

在計算出某個節點i的所有轉發節點集合Fi的EAX 值后，便可以選擇轉發節點集合。具體過程為先找到EAX值最小的轉發節點集合EAXmin以及EAX值小于等于1.1 ?EAXmin的所有轉發節點集合，再統計這些轉發節點集合中兩兩節點互不為鄰居的個數Nneighbor，最后選取Nneighbor值最大的轉發節點集合作為節點s的轉發節點，若Nneighbor值相同，則選擇EAX 值較小的轉發節點集合。

3.3 鏈路相關性指標的計算

在3.1 節與3.2 節中已給出轉發節點的期望轉發計算公式以及基于EAX 值選取轉發節點集合的方法，然而其中關于鏈路相關性的部分并未給出具體計算方法。因為在考慮了鏈路相關性之后，公式（1）、（2）、（5）、（7）中的幾個概率無法僅僅通過鏈路丟包率計算得到，需要進一步收集鏈路信息才能得到鏈路相關性指標。

關于鏈路相關性指標的衡量方式，現有的研究有如下幾種。文獻[9]中提出條件包接受率（Conditional Packet Reception Probability，CPRP），定義為低接收率的節點在收到來自發送節點的數據包的情形下，高接受率的節點也收到發送節點的數據包概率。文獻[10]定義漢明距離用來衡量鏈路相關性。通過位圖（bitmap）記錄兩個鏈路對同一個發送者發送的廣播包的接收情況，對比對應位是否相同，對應位相同則漢明距離加1，漢明距離即為兩個位圖不相同的位數和。漢明距離越大表示兩條鏈路間相關性越小。文獻[11]中作者提出用相關系數衡量鏈路相關程度，并利用其分布準確地估計了機會路由協議的性能，同時指出文獻[9]中利用條件概率估計鏈路相關度存在偏見問題。因為CPRP 會受到鏈路不穩定性和鏈路突發性等因素的影響。作者此外還定義了相關性指標ρ用于表示兩條鏈路間的相關程度。針對相關性指標ρ的取值范圍不嚴密的缺點，作者又提出了歸一化的相關性衡量指標K用于表示兩條鏈路接收數據包的線性相關程度。K的取值范圍為嚴密的[-1,1]，不同的K值反應鏈路對的不同相關程度，K=0 表示兩條鏈路相互獨立，K＞0 表示兩條鏈路正相關，K＜0 表示兩條鏈路負相關。遺憾的是，上述指標只能衡量兩條鏈路之間的相關性，并且候選轉發節集合中節點個數不超過2。實際上在真實的無線網絡場景中，在一定范圍內多個轉發節點接受數據包會受到同一個干擾源的影響。

在本文提出的機制中，為了衡量多條鏈路之間的相關性，轉發節點會周期性地發送接收報告（reception report），每條接收報告記錄了某個鄰居節點發出的多個數據包在本節點的接收狀態。例如，[f,50,11001001]表示某個節點最近收到的鄰居節點f發出的數據包編號為50，接收到編號為43、44 和47 的數據包，而丟失編號為45、46、48和49的數據包，“11001001”稱為“位串”。

在此基礎上，鏈路相關性指標計算過程如下：設φi為ETX 值小于i的節點集合，Bij(ε)為上述位串中第ε位的值，表示節點j是否收到節點i發出的某個數據包。于是節點i和節點j之間的鏈路丟包率為：

其中，m為節點i發出的數據包個數，即位串的位數。為了計算節點j成功接收到節點i的數據包，而ETX值比j小的節點未收到這個數據包的概率，假設Aij(ε)=1表示節點j成功接收到節點i的第ε個探測包，同時ETX比j小的節點都沒有接收到的情況，則有：

再計算ETX 值比j小的節點未收到節點j發出的數據包的概率，假設Ci(ε)=1 表示ETX 比節點i更小的節點都沒有收到第ε個數據包的情況，則有：

下面以一個具體的例子使用上述公式計算鏈路相關指標。

如圖5所示，節點s為節點i,j,k的上游節點，節點s發送8個數據包，節點i,j,k分別發送確認數據包。位串初始狀態各位均為0，節點i,j,k每收到一個數據包就將位串中相應的位置1，最后將包含位串的接收報告進行廣播。當節點s接收到這些接收報告后，便能根據公式（8）以及圖中各個節點的位串計算得到Ps,i、Ps,j、Ps,k分別為0.5、0.625、0.375。假設ETXi＞ETXj＞ETXk，針對節點i，根據公式（9）和（10）計算得到其鏈路相關性指標如下：

同理可得其他鏈路之間的相關信息。利用這些鏈路相關性指標，便可計算出各個節點每收到一個數據包所需的轉發次數TX_credit。

圖5 鏈路相關性指標計算示例

4 算法實現

4.1 考慮鏈路相關性的節點轉發次數計算方法的實現

源節點在開始發送數據包前發送一個泛洪請求，每個接收到這個請求的中間節點將與本節點相關鏈路的丟包率Pi,j發回給源節點。源節點收集到各條鏈路的丟包率Pi,j之后，計算出各節點到目的節點的ETX 值，以此確定轉發節點，并將選取的所有轉發節點記錄在數據包頭部的轉發節點列表當中。此外，將每個轉發節點按ETX值非降序排列，并依次編號為n,n-1,n-2,…,1,0，顯然源節點編號為n，目的節點編號為0。

接下來設置源節點Ln=1，除源節點以外所有節點所需的發送次數Zi設置為0，源節點根據收集到的接收報告計算出Zn，并將其攜帶在需要發送的數據包中，然后將數據包發送出去。

對于每一個轉發節點k，當收到一個新批次的編碼包時，查看該數據包中的轉發節點列表，找出它的所有的上游節點，并向它所有的上游節點請求鏈路相關性指標，收到之后利用公式（1）～（3）計算自己的TX_credit值和Z值。同時，節點k還會維護并更新所有上游節點Z值記錄，并向Z值發生變化的上游節點請求新的鏈路相關性指標和鏈路丟包率等信息，以重新計算本節點的TX_credit值和Z值。當收到ACK數據包時，則清空當前的Z值記錄、鏈路相關性指標以及各鏈路丟包率信息，并重新找出新批次的上游節點集合，開始計算新的TX_credit值和Z值。

另外，為了將本節點所需的轉發次數Z值通知給下游節點，需要修改數據包編碼層的頭部格式，修改后如圖6 所示，在每個TX_credit值后面加入一個字段用于存放Z值，其他字段的詳細解釋見文獻[3]。

圖6 修改后的數據包編碼層頭部格式

4.2 考慮鏈路相關性的轉發節點選取算法

算法的核心思想是在多個轉發節點集合中選取出一個具有最小EAX值的集合。由于EAX值的計算考慮了鏈路相關性，因此使用該算法選取的轉發節點集合理論上具有更少的傳輸次數。轉發節點集合選取算法如下所示，其中set_size表示假設的轉發節點集合大小。N(s)為節點s的鄰居節點，Fresult為選取出的轉發節點集合。

算法1 轉發節點集合選取算法FN_Select(s,d,set_size)

1. Fresult=?;Finitial=?;eax_min=∞;eax_temp=∞;

2. for all v ∈N(s) do

3. if ETX(v,d)＜ETX(s,d) then

4. Finitial=Finitial∪v；

5. end if

6. end for

7. while| |

Fresult＜set_size do

8. C_temp=arg minc∈Finitial{EAX(Fresult∪c,s,d)}

9. eax_temp=EAX(Fresult∪c_temp,s,d)；

10. if eax_temp ＜eax_min then

11. Fresult=Fresult∪c_temp;Finitial=Finitialc_temp;

eax_min=eax_temp;

12. else

13. break；

14. end if

15. endwhile

算法1中1～6行在節點s的鄰居節點中找出比節點s具有更小ETX 值的鄰居節點并保存在集合Finitial中；在7～15行的循環中，每當尋找到具有更小EAX 值的轉發節點集合，就將這個EAX 值以及此時的候選轉發節點集合記錄下來，直到找不到具有更小EAX 值的候選轉發節點集合，或者轉發節點數目達到了預先設定好的set_size值。退出循環后，集合Fresult為算法所得的轉發節點集合。

考慮算法的開銷，沒有對轉發節點集合大小set_size進行限制，即當set_size=n時（其中n為所有備選的轉發節點的個數），由于c_temp=arg minc∈Finitial{EAX(Fresult?c,s,d)}暗含了一個循環結構，所以算法1的時間復雜度為O(n2)。顯然當n的取值較大即網絡中的節點分布緊密時，算法的時間復雜度會上升的很快，因此，為了降低轉發節點選取的計算開銷，取set_size=4。

4.3 算法開銷分析

本節將對算法的通信開銷進行分析，在NCCLCOR中引入的通信開銷分為兩部分：

（1）每個節點周期性地向鄰居節點發送探測包，并接收鄰居節點反饋的ACK 數據包，以計算與鄰居節點之間鏈路的丟包率以及多條鏈路之間的相關性。

（2）每個節點周期性地向上游節點發送本節點到某個目的節點的EAX 值，以便上游節點計算自己到對應目的節點的EAX值，并且選擇轉發節點。

需要指出的是，（1）中的開銷，其他協議（例如MORE、EXOR）也可能需要，而（2）中的開銷，是本文提出的NCCLCOR協議所特有的。

針對（1）中所述的開銷，分析如下：假設網絡中有n個節點，每個節點的平均鄰居節點個數為m，每次探測過程中節點都發送50個hello探測包，每個hello探測包及其ACK確認包的大小均為40 Byte。

因此在不考慮丟包以及沖突的情況下，通信開銷為n×50×40+n×m×50×40=200×n×(1+m)Byte。假設時間周期T為30 s，n為25，m為4，則探測過程消耗的平均帶寬為200×25×(1+4)×8/30 ≈6.67 kb/s。

針對（2）中的所述的開銷，分析如下：假設網絡中有l條流，所有流的平均跳數為h，每個節點的平均鄰居數為m，那么每個時間間隔T內傳輸這些相關性信息平均所需的轉發數據包個數為l?h?m個。

假設網絡中節點個數為25，l為100，h為3，m為4，T為30 s，則每個通知數據包大小上限為(40+25×2)Byte，用于傳遞這些EAX 值所消耗的帶寬約為100×3×4×(40+25×2)×8/30=28.8 kb/s。

為了驗證本章對通信開銷的分析，本文將在后續的仿真實驗中對算法的開銷進行驗證分析。

5 仿真實驗

對MORE[3]、LCAOR[12]以及本文提出的NCCLCOR進行仿真實驗，并比較它們在整體吞吐量方面的表現。之所以選取LCAOR 協議，是由于它在選取轉發節點時考慮了鏈路相關性的影響，實現了對機會路由機制的優化，但是并未引入網絡編碼，與之對比能看出在鏈路相關性感知的機會路由機制中引入網絡編碼技術所帶來的吞吐量提升的程度。

本文參考MORE以及LCAOR中使用CDF（累積分布函數）來對比不同協議的吞吐量表現。CDF定義為對于實隨機變量x，有F(x)=P(X≤x)。在仿真實驗中，x軸為流的吞吐量，F(x)即為吞吐量低于x的概率。直觀上來看，在CDF 中曲線越靠右意味著對應的協議中整體吞吐量更高。

同時，由于算法需要收集網絡中的信息，這會造成額外的通信開銷。為了分析并對比這種開銷，5.2.4小節對實驗過程中三種協議的額外帶寬開銷進行了對比分析。

5.1 實驗環境和參數設置

由于NS2中的丟包策略為隨機的，并且鏈路的丟包相互獨立，因此需要在NS2中加入干擾模型實使鏈路丟包呈現相關性。同現實中的干擾源一樣，在干擾源干擾半徑內的所有節點接收轉發數據包都會受到影響。離干擾源越近，受到的影響越大，如圖7所示。

圖7 干擾模型示例

為了考慮干擾源對丟包率Pi,j的影響，采用文獻[18]中的鏈路丟包率概率計算公式：公式（11）。當鏈路受到干擾源影響時，噪聲功率Nij會增加，其計算公式為公式（12）和（13）。

公式（11）中Pi,j為鏈路的丟包率，Rij表示節點i的發送速率（單位為Mb/s），dij表示鏈路i到j之間的距離，α表示鏈路丟失指數，Wi為發送節點的發送功率。

公式（13）中l1為干擾源到發送節點的距離，l2為干擾源到接收節點的距離，PIn為干擾源的功率。β為干擾系數。在后續的仿真實驗中，取Rij=11 Mb/s,Wi=10 dBm,PIn=16 dBm,N0=-102 dBm,其中α=4,β=1。

實驗環境和參數設置如下：在1 000×1 000 的區域內隨機部署25 個節點，隨機生成50 種拓撲結構。每個節點在數據鏈路層都運行802.11b 協議，轉發隊列緩沖區大小設為50 個數據包，鏈路帶寬設為5.5 Mb/s，丟包率隨機選取。隨機選擇源節點和目的節點，生成100條TCP流，每個數據包大小為1 500 Byte，每條流傳輸一個5 MB大小的文件。網絡中收集下游節點成功收取數據包信息的時間周期T設置為30 s。在NCCLCOR 中，batch size設為32。隨機生成50種拓撲結構，在每種拓撲中隨機選擇一對節點作為源節點和目的節點進行數據傳輸。

5.2 實驗結果分析

現實情況中干擾源無處不在。因此在實驗過程中考慮引入數量不等并且位置固定的干擾源，測試不同相關性程度下三種協議的表現。

5.2.1 單個干擾源

圖8展示了干擾源為一個的情況下三種協議的所有100條流的吞吐量分布情況。觀察圖8可知，NCCLCOR大約90%的流的吞吐量要大于1 Mb/s，在該比例下，MORE 和LCAOR 分別僅為0.4 Mb/s、0.75 Mb/s 左右。這說明NCCLCOR的整體吞吐量更高，即NCCLCOR表現優于MORE以及LCAOR。

圖8 100條流的吞吐量分布圖

眾所周知，無線mesh 網絡存在連續多跳的情況下網絡吞吐量下降會非常迅速。為了比較三種協議在多跳情形下的優劣，在所有100條流中選取出所有經過了4跳及以上且第一跳與最后一跳的傳輸互不干擾的流，再測試這些流的吞吐量分布情況，結果如圖9所示。

圖9 展示了干擾源為一個的情況下，上述100 條流中41條經過四跳以上的流的吞吐量分布情況?？梢钥吹?，與圖8 相比，三種協議因為跳數增加的緣故整體吞吐量都有所下降。但更為明顯的是，NCCLCOR所有流的吞吐量都大于1.3 Mb/s，而MORE 和LCAOR 僅大于0.1Mb/s以及0.6Mb/s。這說明在多跳的情形下，NCCLCOR的表現依舊優于MORE和LCAOR。

圖9 41條4-hops流的吞吐量分布圖

5.2.2 三個干擾源

圖10展示了干擾源為三個的情況下三種協議的所有100條流的吞吐量分布情況。和圖8中一個干擾源的情形相比，三種協議的整體吞吐量都有所下降。NCCLCOR超過90%的流吞吐量大于1 Mb/s，LCAOR 超過90%的流吞吐量大于0.6 Mb/s，MORE 超過90%的流吞吐量大于0.3 Mb/s。這說明，在多個干擾源存在的情況下，NCCLCOR表現優于MORE以及LCAOR。

圖10 三個干擾源情形下100條流的吞吐量分布圖

依舊從所有100 條流中選取出所有經過了四跳及以上且第一跳與最后一跳的傳輸互不干擾的流，再測試三個干擾源情形下這些流的吞吐量分布情況，結果如圖11所示。

圖11 三個干擾源情形下45條4-hops流的吞吐量分布圖

圖11展示了干擾源為三個的情況下，45條經過四跳以上的流的吞吐量分布情況。觀察圖11可知，NCCLCOR的45 條多跳流的吞吐量均大于1.3 Mb/s，LCAOR 僅大于0.6 Mb/s，而MORE 只大于0.125 Mb/s。這說明在多個干擾源存在并且經過多跳的情況下，NCCLCOR表現依舊優于MORE和LCAOR。

5.2.3 四個干擾源

圖12展示了干擾源為四個的情況下三種協議的所有100條流的吞吐量分布情況。觀察圖12可知，NCCLCOR所有流的吞吐量均大于1 Mb/s，高于LCAOR的0.5 Mb/s和MORE的0.1 Mb/s。結論與圖10所得一致。

圖12 四個干擾源情形下100條流的吞吐量分布圖

再從所有100條流中選取出所有經過了四跳及以上且第一跳與最后一跳的傳輸互不干擾的流，測試四個干擾源情形下這些流的吞吐量分布情況，結果如圖13所示。

圖13 四個干擾源情形下42條4-hops流的吞吐量分布圖

圖13 展示了干擾源為四個的情況下，42 條經過四跳以上的流的吞吐量分布情況。觀察圖13 不難發現，NCCLCOR 中所有流的整體吞吐量高于MORE 以及LCAOR，結論與圖11所得一致。

以上結果說明NCCLCOR 在多個干擾源存在的無線網絡中能夠提高網絡吞吐量。原因在于NCCLCOR能有效地降低節點的傳輸次數，由于采用了網絡編碼，下游節點收到足夠的編碼包時會通知上游節點停止發送，這樣上游節點便能更多地發送其他流的數據包，而又不影響下游節點對編碼包的解碼。

5.2.4 開銷結果及分析

在上述單個干擾源的仿真實驗中，測量了單個節點的平均額外帶寬開銷以及所有節點總的額外開銷，結果如表1所示。

表1 三種協議傳輸50 MB數據的開銷統計

從表1的數據可以看出，單位時間內的開銷，MORE協議最少。這是因為MORE 協議只需每隔一個時間間隔T傳輸50個hello探測數據包，然后根據返回的ACK信息統計各鏈路的成功傳輸概率，這部分開銷統計值和4.3 節中計算得到的6.67 kb/s 相近；而NCCLCOR 協議的單位時間開銷最大，這是因為在NCCLCOR中節點不僅需要定期發送hello 探測包，同時還需要定期傳輸各自到目的節點的EAX值。在NCCLCOR中，由于EAX值是攜帶在hello 探測包和ACK 包中進行傳輸的，因此額外通信開銷的統計值與4.3節中分析所得的值有偏差。

從傳輸定量數據的總開銷的角度來看，NCCLCOR協議所需的總通信開銷只比MORE 協議稍多一點。這是因為NCCLCOR 的整體網絡吞吐量相比MORE 協議高，故傳輸等量數據所需的時間比MORE協議少。

6 結束語

針對無線鏈路傳輸存在相關性的特點，本文首先分析了鏈路相關性對流內網絡編碼中機會路由機制中節點轉發次數和轉發節點選取的影響。接著在此基礎上提出一種流內編碼中考慮鏈路相關性的機會路由機制NCCLCOR。NCCLCOR在計算節點成功傳輸數據包所需的期望轉發次數時，考慮了鏈路相關性的影響。通過統計鏈路的相關性指標，并根據計算出的節點期望轉發次數選取出總轉發次數最少的轉發節點集合。理論上，NCCLCOR 能夠有效降低無線網絡中轉發節點的轉發次數，進而減少沖突發生的概率，最終提高網絡的吞吐量。NS2上的仿真實驗結果表明，NCCLCOR相比ETX機制以及LC 機制能有效降低節點轉發次數，降低發送冗余，提高網絡的整體吞吐量。