基于重要信息反饋的BATS 碼優化設計

楊 娟，史治平，嵇建波

(1. 電子科技大學通信抗干擾技術國家級重點實驗室 成都 611731；2. 桂林航天工業學院電子信息與自動化學院 桂林 541004)

在無線通信網絡中，一個重要且基礎的工作就是文件分發，將文件數據包從源節點經中繼節點發送至目的節點。數據包在無線通信網絡中進行傳輸時，可能由于信道噪聲、衰落、接入沖突等原因而造成數據丟失現象[1]。

文獻[2]提出的數字噴泉碼作為一種前向糾錯碼能很好地解決這一問題。噴泉碼是一種發送端可源源不斷地發送編碼包直至接收端能夠成功譯碼的糾錯編碼技術。將原始文件劃分為k個數據塊，隨機對這k個數據塊進行編碼，可以得到任意n個編碼數據包，因此噴泉碼是任意碼率或無碼率的。將噴泉碼應用于含中繼節點的無線通信網絡中，在中繼節點采用的是存儲轉發操作，而該操作并不是中繼節點可采用的最優操作。在多播網絡中，只有在中繼節點應用網絡編碼才能達到網絡最大吞吐率[3]。以兩跳的單播刪除網絡為例，假設每一條鏈路的刪除概率為0.2，如果中繼節點對接收數據進行存儲轉發操作，網絡吞吐率最高為每使用一次網絡傳輸0.64 包；而如果中繼節點允許對接收數據進行網絡編碼，則吞吐率最高可達到每使用一次網絡傳輸0.80 包。BATS 碼作為一種適用于多跳刪除網絡的新型網絡編碼方案[4-7]，結合了噴泉碼和網絡編碼算法，將二者分別作為其外碼和內碼。BATS 碼的外碼是LT 碼的矩陣形式，因此BATS 碼也是一種無速率碼，由發送端不斷向接收端發送編碼的批次碼，直到接收端譯碼成功。當批次碼的大小M等于1 時，BATS 碼的外碼即為LT碼。BATS 碼的內碼采用隨機線性網絡編碼算法，BATS 碼將二者結合起來能保證數據在無線通信網絡中可靠傳輸，同時漸近最大網絡容量。

傳統的BATS 碼編譯碼方案是不依賴于反饋的，但反饋信道在BATS 碼的應用場景中是可用的，用于接收端在譯碼成功后反饋一個ACK(acknowledge character)確認信號使發送端不再繼續發送編碼數據包，且無論使用與否，反饋信道都被占用著，因此應當考慮如何將反饋信道有效利用起來。文獻[8]針對LT 碼提出當接收端譯碼過程停止時，利用反饋信道反饋所有未譯碼的原始輸入數據包包號，在發送端將它們重新發送以重啟接收端譯碼過程。文獻[9]在文獻[8]的基礎上提出了一種改進方案，接收端反饋未譯碼輸入數據包的包號及譯碼后更新的生成矩陣，按照未譯碼數據包的度值從大到小進行重傳。然而，這兩種方案都需要反饋大量的信息包，頻帶利用率較低，且會導致反饋擁塞等問題。文獻[10]針對LT 碼提出了一種基于重要信息反饋的編譯碼方案，接收端只反饋度值最大的未譯碼輸入數據包的包號，發送端接收到后對該數據包進行重傳，在中繼節點對其采用轉發操作。這種方案在有效減少反饋數據量的同時，也能使譯碼性能得到提升。然而，當網絡跳數較多或通信質量較差時，重要數據包在重傳過程中丟失的可能性較大，從而將影響接收端數據包的恢復。

基于上述原因，本文方案不僅考慮了如何確保重要信息能夠有效傳輸到接收端，還研究了譯碼過程中輸入數據包較難完全譯碼成功的主要原因，并據此改進了對重要輸入數據包的選擇方案，使其能有效增加譯碼成功次數。在仿真結果中，本文對比了傳統BATS 碼，基于重要信息反饋的BATS碼以及本文優化方案，在結果中論證了本方案的優越性。

1 BATS 碼的編譯碼算法

BATS 碼通常應用于包括中繼節點的刪除網絡中，如圖1 所示為一個多跳的刪除網絡，s為源節點，d為目的節點，a1,a2,···,an為中繼節點。BATS碼包括內碼和外碼，在多跳刪除信道中應用BATS碼，外碼在源節點也即發送端完成，內碼在中繼節點進行。具體編碼過程描述如下，發送端對K個長度為L的原始數據包進行編碼，產生n個大小為M的批次碼。產生第i個批次碼時，首先根據預先優化的編碼度分布 Ψ進行采樣得到一個度di，在K個原始數據包中隨機選取di個數據包組成一個L×di維的矩陣Bi，然后經外碼編碼產生一個包含M個編碼包的批次碼Xi，其數學表達形式為：

圖1 多跳刪除網絡

式中，Gi為生成矩陣，是有限域上的一個完全隨機矩陣。發送端將批次碼一個接一個按順序發送至中繼節點。中繼節點對接收到的批次碼在同一個批次內進行內碼編碼，編碼方式采用隨機線性網絡編碼。接收端接收到的第i個批次碼Yi表示為：

式中，Hi為第i個批次碼的轉移矩陣，由內碼編碼過程與信道情況共同決定。

由于計算復雜度低，接收端通常采用BP 譯碼算法進行譯碼。接收到給定數量的批次碼后，接收端開始譯碼，譯碼時需要計算每一個批次碼的度是否等于它的秩，如果第i個批次碼的度di等于它的秩rk(GiHi)，則采用高斯消元算法對該批次碼進行求解，得到與之關聯的di個原始輸入數據包信息，并利用di個輸入包的信息對與之關聯的批次碼進行替換和更新，去除它們對這些批次碼的影響。重復上述過程直至找不到滿足度與秩相等條件的批次碼，BP 譯碼過程停止。

在傳統的BATS 碼編譯碼方案中，發送端在第一輪編碼時首先發送N1個批次碼，接收端接收到后開始譯碼，如譯碼成功則反饋一個ACK 譯碼成功確認信號，否則不返回反饋信號。在第i輪編碼前，發送端先確認是否接收到ACK 信號，接收到則停止編碼傳輸，未接收到則繼續對原始數據包進行編碼，產生并發送Ni個批次碼，固定編碼輪數或重復上述編碼過程直至發送端接收到譯碼成功的ACK信號，編譯碼過程停止。

2 BATS 碼的優化方案設計

2.1 重要信息的選擇

由于BATS 碼具有無碼率特性，在未收到ACK反饋信號前，發送端將不斷發送批次碼，BP 譯碼器在接收到一定數量的批次碼后即可開始譯碼。批次碼的編碼包在傳輸過程中由于信道噪聲、衰落等原因會發生丟失現象，因此在接收端一些批次碼由于不滿足譯碼條件而無法進行譯碼，當接收端不存在滿足譯碼條件的批次碼時，譯碼過程停止。要重啟譯碼過程，需要獲得更多的原始輸入數據包信息，將其替換進未譯碼的批次碼中消除更多的關聯，從而產生新的可譯批次碼。采用傳統BATS 碼編碼方案，編碼器在進入下一輪編碼時，將隨機選取輸入數據包進行編碼，如果利用反饋信道獲取反饋信息，編碼器可以優先對一些更重要的輸入數據包進行編碼，從而加快譯碼進程。

接收端根據譯碼后各個未譯出的批次碼的包頭信息可以統計出與之關聯的輸入數據包的度，從而找出具有最大度值且未譯碼成功的輸入數據包。由圖2 所示，圓代表未譯出的輸入數據包，它的集合用B={b1,b2,b3,b4,b5,b6}來表示，方塊代表不可譯的批次碼，它的集合為{Y1,Y2,Y3,Y4}。由圖中可以看出，各個未譯出的輸入數據包的度分別為{1,0,4,0,3,2}，如果能將度為4 的原始數據包b3譯出，那么Y1,Y2,Y3,Y4的度值都會降低1，從而增大了產生可譯批次碼的概率。

文獻[10] 指出，對于噴泉碼，如果能將度值最大的原始數據包譯出，在有限的反饋信息條件下，能最大程度地增加各批次碼的可譯概率。因此本文將未譯出且具有最大度值的原始數據包作為重要信息包的一部分，譯碼器反饋一個數據包給編碼器，該數據包中包含這個重要信息包的包號。

由圖2 可知，在未譯出的輸入數據包中，b2和b4未譯出的原因是它們并未參與編碼，因此無論是否所有的批次碼被譯出，b2和b4都不能被譯出。文獻[11] 指出BATS 碼特別是對于有限碼長BATS碼來說，輸入數據包完全譯碼成功概率較低，而造成這個現象的主要原因是由于BATS 碼的編碼算法采用的是隨機選取輸入數據包來進行編碼的策略，有的輸入數據包在編碼過程中始終沒有被選取。基于上述原因，本文將未參與編碼的輸入數據包也作為重要信息包的一部分參與下一輪的編碼。這一部分輸入數據包的包號可以在發送端進行分析和統計，不需要接收端進行反饋，因此也不會由于增大反饋數據量而產生額外代價。所以，本文將重要信息定義為兩部分，一部分為接收端未譯出且具有最大度值的原始數據包，另一部分為發送端未參與編碼的原始數據包，并將二者作為下一輪編碼的重要信息包。

圖2 未譯出的輸入數據包與不可譯批次碼之間的二分圖

2.2 基于重要信息反饋的BATS 碼優化設計

基于重要信息改進的BATS 碼編譯碼方案流程如圖3 所示。

圖3 基于重要信息反饋的BATS 碼優化設計框圖

在發送端，BATS 碼外碼編碼器首先根據信道情況確定各輪發送批次碼的數量，將第i輪編碼器發送的批次碼數量設為Ni。為方便分析，本文將發送批次碼的數量分為首輪發送和接收反饋后發送兩種情況，發送個數分別為{N1,N2}。在發送端進行的外碼編碼算法流程可以用下述偽代碼來進行描述。

基于反饋和發送端的統計得到的重要信息所改進的BATS 碼外碼編碼算法

接收端在接收到第i輪發送的批次碼后，將其與之前接收到且未譯出的批次碼及已譯出的輸入數據包進行聯合譯碼，譯碼后根據不可譯的批次碼的包頭信息統計出具有最大度值的輸入數據包，并將其包號反饋回發送端。

在編碼器的編碼過程中，文獻[10] 對發送端接收到反饋度值最大的數據包包號所對應的信息進行重傳后，中繼節點對重傳數據包采用的是存儲轉發操作。如果無線網絡的跳數較少或者信道條件較好時，采用這種方式，接收端能較好地接收到該數據包。然而，隨著網絡跳數的增加或信道環境較差時，接收端很有可能無法接收到該重要信息包的信息。如考慮一個刪除概率為0.2 的多跳刪除網絡，跳數為p時，一個數據包在接收端被接收到的概率為(0.8)p，跳數越高，接收到它的概率越低。對一個k跳的線性網絡的最大可達速率進行仿真分析，如圖4 所示，如果對重要信息包在中繼節點直接進行存儲轉發，隨著線性網絡跳數的增大，可達速率呈快速下降趨勢。如果在中繼節點對重要信息包采用隨機線性網絡編碼算法進行編碼再轉發至下一個節點，那么可達速率隨跳數的增加而下降的速度將變得緩慢。因此，在信道條件較差時，也能較好地保證重要信息在接收端具有較高的譯碼成功率。圖4 中，M代表批次碼的大小，q為有限域的大小。

圖4 最大可達速率隨跳數的變化趨勢

在改進的編譯碼方案中，編碼器在進行第i輪編碼時，N2個批次碼轉發至中繼節點后，需要采用隨機線性網絡編碼算法對所有批次碼進行內碼編碼，再由中繼節點轉發至下一個中繼節點或接收端。需要注意的是，由重要信息產生的批次碼和一般輸入數據包產生的批次碼在進行內碼編碼時，再編碼的批次碼長度可以不同[12-14]。由圖4 所示，再編碼的批次長度越大，碼字的最大可達速率越大，但同時編碼開銷也越大。

為減少開銷，提高編碼靈活度，重要信息包對應的批次碼長度可隨信道環境進行調整。如在信道條件較好時，由于重要信息包數量較少，內碼編碼的長度可采用較小值。改進的基于重要信息反饋的BATS 碼編譯碼方案的具體操作步驟如下。

1)編碼器進行第一輪BATS 碼外碼編碼，生成N1個長度為M1的批次碼并依次發送至中繼節點；

2)中繼節點接收到批次碼后，對所有接收到的批次碼在同一個批次碼內部采用隨機線性網絡編碼算法進行內碼編碼，其中，由重要信息包生成的批次碼，內碼編碼長度為M2，其余批次碼內碼編碼長度為M1。完成內碼編碼后，將這些批次碼按順序轉發至下一個中繼節點或接收端，如果轉發至中繼節點，編譯碼流程轉至步驟2)，如果轉發至接收端，編譯碼流程轉至步驟3)；

3)接收端接收到N1或N2個批次碼后，開始采用BP 譯碼算法進行譯碼，如果將所有的原始輸入數據包譯出則表示譯碼成功，返回一個ACK 信號。否則，譯碼器開始對所有不可譯的批次碼進行分析和統計，找出具有最大度值且未譯出的輸入數據包，并將其包號反饋回發送端，編譯碼流程轉至步驟4)；

4)編碼器在進行第i輪編碼前，首先分析反饋信息，如果是ACK 信號，編碼過程結束，如果為一個數據包包號，編碼器對所有輸入數據包進行分析和統計，找出未參與編碼的數據包，并將其與反饋包組成集合I，采用外碼編碼算法對I 進行編碼，產生第一個批次碼，隨后對所有原始數據包進行隨機編碼產生剩下所需的N2-1個批次碼，兩種類型的批次碼編碼長度均為M1，將它們發送至中繼節點，編譯碼流程轉至步驟2)。

3 方案性能仿真與分析

在仿真性能分析中，對傳統BATS 碼、基于重要信息反饋BATS 碼以及本文算法的譯碼性能分別進行了仿真和比較。在仿真模型中，假設存在理想反饋信道，反饋距離較短，反饋時延較小，且由于反饋包數較少，為方便分析，可忽略反饋開銷對系統性能造成的影響。仿真參數設置如下：在內外碼編碼中，編碼系數在有限域GF(256)中進行選擇。為方便分析，批次碼內外碼編碼尺寸統一選擇為M1=M2=8，數據包長度為L=2。外碼編碼度分布按照文獻[15] 中有限長BATS 碼度分布設計方法生成。3 種方案的譯碼算法均采用BP 譯碼算法，仿真次數設為100。編碼冗余定義為：

式中，f為反饋輪數。譯碼成功率指的是譯碼完成后，已恢復的包數占所有包數的比例。

不同碼長下改進方案性能仿真分析如下：在以上仿真參數的設置下，考慮一個兩跳的刪除信道，每一條鏈路的刪除概率設為 0.1，信道秩分布為h=[0,0,0,0.000 8,0.009 2,0.064 8,0.264 6,0.476 0,0.184 6]，設置不同的原始數據長度K=[500,1 000]，分別對3 種方案在不同碼長下的譯碼性能進行仿真，發送的批次碼數量設為N1=125，N2=7，仿真結果如圖5所示。3 種編譯碼方案的譯碼成功率隨著編碼冗余的增加都在上升，但改進的基于重要信息反饋BATS碼上升的速度相對其他方法更快。另外，碼長越長，在相同的編碼冗余下譯碼成功率越高。

圖5 不同碼長下BATS 碼優化方案的性能比較

不同反饋步長下改進方案性能仿真分析如下：固定碼長K=500，N1=125，設置不同的反饋步長N2=3,7,14，對本文改進的基于重要信息反饋的BATS 碼編譯碼方案進行了譯碼性能的仿真，仿真結果如圖6 所示，改進算法比傳統BATS 碼的性能更好。通過對比3 組不同反饋步長的譯碼成功率，可以發現隨步長的減小，譯碼成功率快速上升。步長越小，接收端獲得的反饋信息越多，對重要信息的編碼次數也就越多，譯碼性能越好。

圖6 不同反饋步長下BATS 碼優化方案的性能比較

不同信道條件下改進方案性能仿真分析如下：固定碼長K=500，發送的批次碼數量設為N1=125,N2=7，編碼冗余固定為ε=2.12，圖7 對3 種編譯碼方案在多跳刪除信道條件下的譯碼性能進行了仿真。將每一跳鏈路的刪除概率設為 0.1。仿真結果如圖7 所示，譯碼成功率隨信道跳數的增加在不斷下降，但本文的編譯碼方案譯碼成功率隨跳數的增加，下降的速度更為緩慢。

圖7 不同跳數下BATS 碼優化方案的性能比較

表1 對比了3 種方案的譯碼成功次數，每種方案總的仿真次數為100，由表1 可見，本文改進方案能夠獲得更多的譯碼成功次數。在本文方案中，每進行一次反饋，編碼器不僅將上一輪未參與編碼的輸入數據包與反饋數據包作為一個子集合進行外碼編碼，同時在經過中繼節點時，還對這部分產生的批次碼進行再編碼。這樣不僅能保證所有數據包都參與編碼，同時使重要信息包在傳輸過程中得到保護，因此本文方案能獲得更高的完全譯碼成功概率且隨跳數的增加下降的速度最為緩慢。

表1 3 種編譯碼方案譯碼成功次數

4 結 束 語

本文設計了一種改進型的基于重要信息反饋的BATS 碼編譯碼方案。與傳統基于重要信息反饋編譯碼方案相比，本文方案更新了重要信息包的內容，為提高完全譯碼成功概率，每次反饋后將之前未參與編碼的原始數據包與譯碼后具有最大度值的原始數據包共同作為重要信息包，參與到下一次的編碼中去。同時，為了保證重要信息包在多跳刪除信道或具有較差信道環境中進行傳輸時仍能在接收端具有較高的譯碼恢復率，本文方案考慮在中繼節點對重要信息包產生的批次碼采用網絡編碼算法進行再編碼。仿真結果表明，本文算法與傳統BATS碼以及基于重要信息反饋BATS 碼相比，具有更高的譯碼成功率，較好地實現了設計目標。