實用網(wǎng)絡(luò)編碼系統(tǒng)的可靠傳輸策略

王 偉，金明錄，曲 強(qiáng)②

0 引言

2000年香港中文大學(xué)的R. Ahlswede等人提出了網(wǎng)絡(luò)編碼這一概念。該理論以最大流最小割定理為基礎(chǔ)，通過分析證明，網(wǎng)絡(luò)中存在理論上的最大流。為了充分挖掘網(wǎng)絡(luò)潛在的能力，達(dá)到理論最大流，網(wǎng)絡(luò)編碼應(yīng)運而生[1]。Philip A.Chou,Yunnan Wu等人在前人工作的基礎(chǔ)上，提出了一種適用于真實網(wǎng)絡(luò)環(huán)境的實用網(wǎng)絡(luò)編碼系統(tǒng)。該系統(tǒng)成功的解決了真實網(wǎng)絡(luò)中傳輸延遲以及網(wǎng)絡(luò)拓?fù)鋸?fù)雜等問題，大大的推動了網(wǎng)絡(luò)編碼理論與實踐的發(fā)展[2]。

1 實用網(wǎng)絡(luò)編碼簡介

由于大部分確定性的網(wǎng)絡(luò)編碼算法只適用于單信源的無環(huán)無時延的多播網(wǎng)絡(luò)，對于更普遍的多信源有環(huán)和時延的多播網(wǎng)絡(luò)并不適用，文獻(xiàn)[3]提出了完全隨機(jī)選取線性編碼系數(shù)的分布式的網(wǎng)絡(luò)編碼方式[4]。對于隨機(jī)網(wǎng)絡(luò)編碼，每個接收節(jié)點只需要知道全局編碼向量，就可以完成網(wǎng)絡(luò)編碼的解碼過程了。在此基礎(chǔ)上，文獻(xiàn)[5-6]提出實用網(wǎng)絡(luò)編碼的概念。實用網(wǎng)絡(luò)編碼系統(tǒng)采用的編碼算法是隨機(jī)網(wǎng)絡(luò)編碼，在編碼形成的數(shù)據(jù)包的前面加入該節(jié)點的編碼向量的信息以及在節(jié)點中引入緩存池，這樣便解決了實際網(wǎng)絡(luò)中傳輸延遲大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜的問題。

以 4個信源節(jié)點 Sk，k=1,2,3,4,兩個中繼節(jié)點 rl，l=1,2以及若干個信宿D(zhuǎn)n，n=1,2,…,N為例,如下頁圖1所示。

如果對于所有信宿都要接收來自于 4個發(fā)送節(jié)點的信息，對于某信宿D(zhuǎn)n可與之通信的節(jié)點為S1，S2，r1，r2，則選擇的接收路徑是：S1Dn，S2Dn，r1Dn，r2Dn，對于 Di(i≠n)，與之通信的節(jié)點為S3，S4，r1，r2，選擇的接收路徑為：S3Di，S4Di，r1Di，r2Di。這樣對于中繼節(jié)點r1，r2則成為關(guān)鍵節(jié)點。Dn需要從r1，r2獲得信息m3，m4。而Di需要從r1與r2獲得信息m1，m2。這樣在r1，r2引入網(wǎng)絡(luò)編碼技術(shù)可以增加網(wǎng)絡(luò)的吞吐量。在r1與r2分別進(jìn)行網(wǎng)絡(luò)編碼操作得到：

圖1 網(wǎng)絡(luò)舉例

其中 gr1， gr2分別為 r1與 r2的編碼向量。引入實際網(wǎng)絡(luò)編碼的思想，在r1與r2編碼好的數(shù)據(jù)幀前面加入該節(jié)點的編碼向量組成新的數(shù)據(jù)幀，即[ gr1Mr1]和 gr1Mr1]發(fā)送出去。將信源 S1-S4發(fā)送出去的數(shù)據(jù)也視為進(jìn)行了網(wǎng)絡(luò)編碼操作的數(shù)據(jù),只是在其原始數(shù)據(jù)前面加入少量編碼向量信息 gr1=[1 0 0 0], gr2=[0 1 0 0]， gr3=[0 0 1 0]， gr4=[0 0 0 1]。這樣，對于接收節(jié)點 Dn無論接收到了哪個節(jié)點發(fā)送過來的信息，當(dāng)收到足夠多的數(shù)據(jù)包后都先提取編碼向量，再進(jìn)行網(wǎng)絡(luò)編碼的解碼操作即可[7]。

2 實用網(wǎng)絡(luò)編碼系統(tǒng)傳輸質(zhì)量穩(wěn)定性的研究

2.1 通信質(zhì)量不穩(wěn)定的原因

因為實用網(wǎng)絡(luò)編碼的系統(tǒng)中，整個的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)未知，因此在編碼節(jié)點要將其編碼向量放到分組交換的數(shù)據(jù)包的前面，便于接收節(jié)點解碼。若在無線信道中，數(shù)據(jù)在傳輸過程中會受到噪聲很大的干擾，而且對于一些能量有限的節(jié)點，如無線傳感器網(wǎng)絡(luò)節(jié)點，不能依靠提高發(fā)射功率的方法來提高信噪比，因此數(shù)據(jù)在傳輸過程中經(jīng)常出現(xiàn)錯誤。尤其是對于網(wǎng)絡(luò)編碼系統(tǒng)的數(shù)據(jù)分組，當(dāng)編碼向量出現(xiàn)錯誤，會導(dǎo)致接收端收到的信息解碼產(chǎn)生嚴(yán)重錯誤。如式（3）所示：

其中：

利用高斯消去法解該方程也即網(wǎng)絡(luò)編碼系統(tǒng)的解碼過程。其中系數(shù)矩陣為每個輸入鏈路上的編碼向量信息，xj為原始信，yj為編碼好的信息，n為編碼向量的維數(shù)，也即同時進(jìn)行編碼的數(shù)據(jù)分組的個數(shù)。因為方程右邊的取值為矩陣：

其中N為數(shù)據(jù)包的長度（除編碼向量之外），每次解碼只取出一列來參與解碼操作。因此，若某一個 ykj，k=1,2,…,n。在傳輸過程中出現(xiàn)錯誤，甚至是某一列有錯誤，其影響的最終解碼結(jié)果也只有對應(yīng)的一列數(shù)據(jù)。但是如果系數(shù)矩陣G某一位出現(xiàn)錯誤，每組數(shù)據(jù)的解碼都要用到該系數(shù)矩陣G，所以這樣便會導(dǎo)致解碼出現(xiàn)嚴(yán)重的錯誤使得通信質(zhì)量不穩(wěn)定，如下頁圖 3所示。表1中是對應(yīng)的不同信噪比下，仿真循環(huán)50次時，編碼向量錯誤的次數(shù)。由圖3和表1可見在信噪比為2.5 dB的時候，誤符號率之所以有一個突變的上升是因為編碼向量在 50次循環(huán)中出現(xiàn)了兩次錯誤。有時在信噪比較高的情況下，由于G出現(xiàn)錯誤誤碼率甚至?xí)哂谛旁氡容^低的信道，導(dǎo)致通信質(zhì)量不穩(wěn)定。另外，在當(dāng)G因為噪聲的干擾導(dǎo)致其不是滿秩矩陣時，會導(dǎo)致解碼失敗。

圖2 不對編碼向量進(jìn)行特殊保護(hù)的情況

表1 不同信噪比下編碼向量出錯的次數(shù)

2.2 實用網(wǎng)絡(luò)編碼系統(tǒng)提高傳輸穩(wěn)定性的策略

針對上面提到的實用網(wǎng)絡(luò)編碼系統(tǒng)中，由于編碼向量在傳輸過程中產(chǎn)生了錯誤而導(dǎo)致的通信質(zhì)量不穩(wěn)定甚至解碼失敗的問題。在不提高發(fā)送功率的同時降低誤碼率，只能采取各種信道編碼的手段，以期通過增加冗余犧牲傳輸?shù)挠行詠硖岣呖煽啃浴１疚奶岢隽巳N對于編碼向量保護(hù)的策略，這三種策略都是基于信道編碼的算法來對編碼向量進(jìn)行保護(hù)的。一種是在發(fā)送節(jié)點對編碼向量加入CRC循環(huán)冗余校驗碼來對編碼向量進(jìn)行保護(hù)；另外一種是利用協(xié)作編碼的思想，針對網(wǎng)絡(luò)編碼系統(tǒng)類似于一個 MIMO系統(tǒng)的特點，對所選定編碼節(jié)點的編碼向量進(jìn)行空時分組碼的編碼；第三種是在上述兩種保護(hù)策略之間做一個折中的選擇。三種保護(hù)方案的仿真均考慮在一個信宿節(jié)點所收到數(shù)據(jù)的誤碼率問題。

2.2.1 循環(huán)冗余校驗的策略

循環(huán)冗余校驗的策略，是在編碼端對所有數(shù)據(jù)進(jìn)行卷積碼保護(hù)之前，先單獨對編碼向量加入CRC校驗位，采用美國16-CRC標(biāo)準(zhǔn)，生成多項式為 x16+x12+x5+1。在解碼端先進(jìn)行卷積碼解碼，然后對編碼向量的冗余位進(jìn)行判斷。如果出現(xiàn)編碼向量的錯誤提示，則接收節(jié)點對于發(fā)送該數(shù)據(jù)分組的上游節(jié)點發(fā)出重傳該分組數(shù)據(jù)請求。在上游節(jié)點存有發(fā)送數(shù)據(jù)的備份，若得到接收節(jié)點發(fā)送的重傳請求，則重新發(fā)送該數(shù)據(jù)分組，直至在規(guī)定時間內(nèi)不再收到重傳的反饋信息為止。

2.2.2 空時編碼保護(hù)策略

我們知道,使用多根發(fā)射天線和多根接受天線可以使無線通信系統(tǒng)的信息容量得到顯著提高。空時編碼是一種用于多發(fā)射天線的編碼技術(shù)。該編碼在多根發(fā)射天線和各個時間周期的發(fā)射信號之間能夠產(chǎn)生空域和時域的相關(guān)性。這種空時相關(guān)性可以使接收機(jī)克服MIMO信道衰落和減少發(fā)射誤碼。對于空間未編碼系統(tǒng)，空時編碼可以在不犧牲帶寬的情況下起到了發(fā)射分集和功率增益作用。

空時編碼在編碼結(jié)構(gòu)上有多種方法，包括空時分組碼(STBC),空時網(wǎng)格碼(STTC),空時 turbo網(wǎng)格碼和分層空時碼(LSTC)。所有這些編碼方案的核心思想是使用多徑能力來獲得較高的頻譜利用率和性能增益的目的。雖然在無線網(wǎng)絡(luò)中，每一個移動終端要存在多條輸出天線是很難實現(xiàn)的,但是通過多個終端之間的相互通信，可以以協(xié)作編碼(Cooperative Coding)的思想來傳送數(shù)據(jù)。即終端A可以與終端B進(jìn)行協(xié)作式的空時編碼，互相利用彼此的天線來傳送數(shù)據(jù),構(gòu)成了MIMO系統(tǒng)。本文正是利用上游節(jié)點之間的協(xié)作編碼的思想，來組成一個MIMO系統(tǒng)，從而實現(xiàn)了空時編碼技術(shù)在實用網(wǎng)絡(luò)編碼系統(tǒng)中的應(yīng)用。本文所采用的是Alamouti空時分組碼方案來對網(wǎng)絡(luò)編碼中的編碼向量進(jìn)行保護(hù)。

對于圖2所示的網(wǎng)絡(luò)，我們只考慮接收節(jié)點Dn，該節(jié)點需要接收 S1，S2，r1，r2發(fā)送的實用網(wǎng)絡(luò)編碼系統(tǒng)的數(shù)據(jù)分組。若 Dn的這四個上游節(jié)點之間實現(xiàn)通信，成為一個協(xié)作通信機(jī)制。對于這樣的一個系統(tǒng)，實質(zhì)是一個 4發(fā)送，1接收的MIMO系統(tǒng)。因此S1，S2，r1，r2就可以使用上面提到的 Alamouti空時分組碼方案對數(shù)據(jù)分組中的編碼向量進(jìn)行STBC的編碼方式保護(hù)，從而提高通信的質(zhì)量。

2.2.3 模式切換保護(hù)策略

保護(hù)模式的切換方案，是指在上述兩種模式之間的一個折中策略。考慮到循環(huán)冗余校驗的模式需要大量的重傳次數(shù)而空時分組碼雖然對編碼向量加以保護(hù)，但是仍然無法完全消除編碼向量出現(xiàn)錯誤。因此提出了該方案，即在信噪比較低的情況下，采用空時分組碼的形式來代替循環(huán)冗余校驗；在信噪比較高時，采用循環(huán)冗余校驗的方案。本文所仿真的模式是在信噪比不大于 2 dB的時候采用空時分組碼的方式對編碼向量加以保護(hù)，在信噪比大于 2 dB的時候改為循環(huán)冗余校驗的模式。采用 2 dB作為模式切換的臨界點是根據(jù)蒙特卡羅多次仿真得出的結(jié)論。

3 仿真結(jié)果與分析

仿真采用本文第二部分提出的網(wǎng)絡(luò)模型，采用實用網(wǎng)絡(luò)編碼的分組格式，即該鏈路的編碼向量信息放入到網(wǎng)絡(luò)編碼完成的數(shù)據(jù)幀前面，然后對所有數(shù)據(jù)加入碼率為1/2的卷積碼保護(hù)，再進(jìn)行16QAM調(diào)制后發(fā)送數(shù)據(jù)。經(jīng)過高斯加性白噪聲的信道后，對于一個接收節(jié)點討論其誤碼率的情況。

3.1 三種方案傳輸質(zhì)量的比較

討論4組發(fā)送節(jié)點的信息，原始信息位的符號為GF(23)域，在上面提到的模塊基礎(chǔ)上，將分別采用CRC模式，STBC模式對編碼向量進(jìn)行保護(hù)的情況與只進(jìn)行卷積碼保護(hù)的模式進(jìn)行誤符號率的比較，如圖3所示。

圖3 三種保護(hù)模式的比較1

可見通信質(zhì)量最好的還是CRC模式，而用STBC模式保護(hù)編碼向量相對于只進(jìn)行卷積碼保護(hù)的模式誤符號率也有大幅的降低。但是STBC模式在信噪比較高的情況下由于仍然無法避免編碼向量錯誤所帶來影響，會產(chǎn)生通信質(zhì)量不穩(wěn)定的問題。但是在信噪比較低時，誤符號率與 CRC模式很接近，并且其避免了重傳所帶來的費用。因此又提出了保護(hù)模式切換的方案。

從下頁圖4可見，采用保護(hù)模式切換的實行在低信噪比（2 dB以下）的時候誤碼率可以與CRC模式相接近，在較高信噪比（2 dB以上）的情況下，又有效避免了編碼向量錯誤所產(chǎn)生的誤碼率突然升高的情況，保證了通信質(zhì)量隨著信噪比升高而提高。

3.2 CRC模式與切換模式的重傳次數(shù)比較

在運行 50次蒙特卡洛仿真時，兩種傳輸模式在不同信噪比下總的重傳次數(shù)如下頁表2所示。由表2可知，CRC模式在信噪比較低的時候，重傳的次數(shù)很多，雖然通信的質(zhì)量得以保證，但是效率很低。而采用保護(hù)模式切換的方案之后，因為在信噪比較低時采用的是 STBC的信道編碼模式，因此沒有重傳的代價，而在信噪比較高時，重傳次數(shù)也很少

圖4 三種保護(hù)模式的比較2

表2 兩種保護(hù)策略的重傳次數(shù)統(tǒng)計

4 結(jié)語

本文提出了在實際網(wǎng)絡(luò)編碼系統(tǒng)中，對于編碼向量進(jìn)行保護(hù)的三種不同的保護(hù)策略。仿真結(jié)果表明這三種保護(hù)策略有各自的優(yōu)勢與缺點。對于CRC模式，通信的質(zhì)量較高，但是需要大量的重傳，效率較低；利用協(xié)作通信機(jī)制，在發(fā)送節(jié)點采用空時編碼對編碼向量進(jìn)行保護(hù)，可以避免重傳所帶來的低效問題，但是同樣會產(chǎn)生由于編碼向量錯誤而帶來的通信質(zhì)量不穩(wěn)定的問題；第三種折中的方案，在信噪比較低的時候誤碼率只比CRC模式略高，而在信噪比較高時在較少的重傳次數(shù)的基礎(chǔ)上又避免了通信質(zhì)量不穩(wěn)定的問題。

[1] Ahlswede R, Cai N, Li S Y R,et al. Network information flow[J].Information Theory,2000,46(04)： 1204-1216.

[2] Chou P A, Wu Yunnan. Network Coding for the Internet and Wireless Networks[J]. IEEE Signal Processing Magazine, 2007,23(05)：77-85.

[3] Tracey Ho, Muriel Medard, Jun Shi. On Randomized Network Coding[C].USA：[s.n.],2003：65-70.

[4] Jaggi S, Sanders P, Chow P A. Polynomial Time Algorithms for Multicast Network Code Construction[J]. IEEE, 2005(51)：1973-1982.

[5] Chou P A, Wu Yunnan, Jain K. Practical Network Coding[C].US：[s.n.],2003：781-790.

[6] 王曉海，黃開枝.空時網(wǎng)絡(luò)編碼[M].北京：機(jī)械工業(yè)出版社，2004.

[7] Koetter R,Medard M.A Nalgebraic Approach to Network Coding[J].IEEE/ACMTrans. Networking,2003(11)：182-795.