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

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

1 引言

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

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

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

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

（1）分析鏈路相關性對節(jié)點轉發(fā)次數(shù)以及轉發(fā)節(jié)點選取的影響。

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

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

2 鏈路相關性對節(jié)點轉發(fā)次數(shù)與轉發(fā)節(jié)點選取的影響

2.1 鏈路相關性

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

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

圖1 正負相關示例

2.2 鏈路相關性對節(jié)點轉發(fā)次數(shù)的影響

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

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

圖2 鏈路相關性對節(jié)點轉發(fā)次數(shù)影響示例

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

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

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

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

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

2.3 鏈路相關性對轉發(fā)節(jié)點選取的影響

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

圖3 鏈路相關性對轉發(fā)節(jié)點選取影響示例

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

（1）鏈路獨立：首先選擇第一個轉發(fā)節(jié)點。分別選擇f1、f2、f3作為轉發(fā)節(jié)點，計算得到各自的期望轉發(fā)次數(shù)分別為：α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中的一個節(jié)點作為第一個轉發(fā)節(jié)點。這里選擇節(jié)點f1作為第一個轉發(fā)節(jié)點。

接著選擇第二個轉發(fā)節(jié)點。若選擇節(jié)點f2，因為要保證節(jié)點f1和f2中至少有一個節(jié)點能接收到節(jié)點s發(fā)出的數(shù)據(jù)包，則節(jié)點s的期望轉發(fā)次數(shù)為：α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)表示節(jié)點f1和f2都沒有接收到節(jié)點s發(fā)出的數(shù)據(jù)包的概率。節(jié)點f2收到的數(shù)據(jù)包個數(shù)為αsPs,f2，則它將這些數(shù)據(jù)包轉發(fā)給節(jié)點d的期望轉發(fā)次數(shù)為αf2=(αsPs,f2)/Pf2,d≈1.11；由于s→f1與s→f2兩條鏈路丟包率相同，可直接得到節(jié)點f1期望轉發(fā)次數(shù)為αf1=1.11；因此選擇節(jié)點f1和f2作為轉發(fā)節(jié)點集合的期望轉發(fā)次數(shù)之和為αs+αf1+αf2=3.55。

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

顯然，鏈路獨立的情況下選擇節(jié)點f1和f2作為轉發(fā)節(jié)點所需的轉發(fā)次數(shù)更少。

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

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

顯然，鏈路相關的情況下選擇節(jié)點f2和f3作為轉發(fā)節(jié)點所需的轉發(fā)次數(shù)更少。

對比上述兩種情況下選取的轉發(fā)節(jié)點不難發(fā)現(xiàn)，鏈路獨立的假設會影響轉發(fā)節(jié)點的選取，使得選取的轉發(fā)節(jié)點的總轉發(fā)次數(shù)更多。

3 考慮鏈路相關性的節(jié)點轉發(fā)次數(shù)計算與轉發(fā)節(jié)點選取

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

3.1 考慮鏈路相關性的節(jié)點轉發(fā)次數(shù)計算

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

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

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

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

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

其中，概率P表示所有ETX 值比j小的節(jié)點k均未收到節(jié)點j發(fā)出的數(shù)據(jù)包的概率。

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

3.2 考慮鏈路相關性的轉發(fā)節(jié)點選取

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

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

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

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

以圖4為例介紹EAX值的計算。在圖4中，源節(jié)點s有數(shù)據(jù)包要發(fā)往目的節(jié)點d，F(xiàn)s={ }1,2,…,N為源節(jié)點s的一個轉發(fā)節(jié)點集合。

圖4 EAX值計算示例

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

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

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

3.3 鏈路相關性指標的計算

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

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

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

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

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

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

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

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

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

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

4 算法實現(xiàn)

4.1 考慮鏈路相關性的節(jié)點轉發(fā)次數(shù)計算方法的實現(xiàn)

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

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

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

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

圖6 修改后的數(shù)據(jù)包編碼層頭部格式

4.2 考慮鏈路相關性的轉發(fā)節(jié)點選取算法

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

算法1 轉發(fā)節(jié)點集合選取算法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行在節(jié)點s的鄰居節(jié)點中找出比節(jié)點s具有更小ETX 值的鄰居節(jié)點并保存在集合Finitial中；在7～15行的循環(huán)中，每當尋找到具有更小EAX 值的轉發(fā)節(jié)點集合，就將這個EAX 值以及此時的候選轉發(fā)節(jié)點集合記錄下來，直到找不到具有更小EAX 值的候選轉發(fā)節(jié)點集合，或者轉發(fā)節(jié)點數(shù)目達到了預先設定好的set_size值。退出循環(huán)后，集合Fresult為算法所得的轉發(fā)節(jié)點集合。

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

4.3 算法開銷分析

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

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

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

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

針對（1）中所述的開銷，分析如下：假設網(wǎng)絡中有n個節(jié)點，每個節(jié)點的平均鄰居節(jié)點個數(shù)為m，每次探測過程中節(jié)點都發(fā)送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）中的所述的開銷，分析如下：假設網(wǎng)絡中有l(wèi)條流，所有流的平均跳數(shù)為h，每個節(jié)點的平均鄰居數(shù)為m，那么每個時間間隔T內傳輸這些相關性信息平均所需的轉發(fā)數(shù)據(jù)包個數(shù)為l?h?m個。

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

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

5 仿真實驗

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

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

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

5.1 實驗環(huán)境和參數(shù)設置

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

圖7 干擾模型示例

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

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

公式（13）中l(wèi)1為干擾源到發(fā)送節(jié)點的距離，l2為干擾源到接收節(jié)點的距離，PIn為干擾源的功率。β為干擾系數(shù)。在后續(xù)的仿真實驗中，取Rij=11 Mb/s,Wi=10 dBm,PIn=16 dBm,N0=-102 dBm,其中α=4,β=1。

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

5.2 實驗結果分析

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

5.2.1 單個干擾源

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

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

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

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

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

5.2.2 三個干擾源

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

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

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

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

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

5.2.3 四個干擾源

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

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

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

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

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

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

5.2.4 開銷結果及分析

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

表1 三種協(xié)議傳輸50 MB數(shù)據(jù)的開銷統(tǒng)計

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

從傳輸定量數(shù)據(jù)的總開銷的角度來看，NCCLCOR協(xié)議所需的總通信開銷只比MORE 協(xié)議稍多一點。這是因為NCCLCOR 的整體網(wǎng)絡吞吐量相比MORE 協(xié)議高，故傳輸?shù)攘繑?shù)據(jù)所需的時間比MORE協(xié)議少。

6 結束語

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