基于壓縮感知解碼的網絡編碼技術

高 超， 李生紅， 唐俊華

（上海交通大學 電子信息與電氣工程學院，上海，200240）

0 引言

在 R. Alshwed等人提出了網絡編碼[1]的概念之后，網絡編碼吸引了眾多研究者的興趣。在文獻[1]中，作者證明了網絡編碼可以使網絡容量達到最大流-最小割定理的理論上界。在此之后，網絡編碼的容量和組網方法又成為了研究的焦點。文獻[2]中描述的無差錯網絡的線性編碼代數模型證明了多播網絡編碼的存在。隨機網絡編碼作為一種可行的分布式編碼方案，在文獻[3]中進行了詳細討論，證明了當所有的編碼系數是從一個有限域中按照均勻分布的概率隨機抽取時，可以以很高的概率得到一個可解碼的網絡編碼。當網絡編碼不可解碼時，其傳輸矩陣可視為一個欠定方程組的系數矩陣。借助壓縮感知的思想，網絡可解碼的概率可以進一步增加。

壓縮感知[4]是一種新的對稀疏信號的采樣重建方法。Candes和Donoho等人證明了對于稀疏信號，可以采樣部分信號，并利用采樣通過一定的方法重建[5-6]。壓縮感知的核心在于感知矩陣，也稱為測量矩陣。Candes和Tao等人證明了滿足有限等距性(RIP,Restricted Isometric Property)的矩陣可以用作感知矩陣。在隨機網絡編碼中，傳輸矩陣的子矩陣具有RIP性質。仿真結果表明，壓縮感知可以用于隨機網絡編碼的解碼。

1 系統模型

考慮單源單信宿的無誤差無環網絡。用一個有向圖G=(V, E)表示此網絡，V為頂點集，E為邊集。每條邊的容量為單位容量。如果兩個節點之間實際容量大于 1，則用多條邊表示。文獻[2]中描述了這種模型。每條邊用一個整數表示。可以用一個三元組e=(vi, vj, k )表示。如果一條邊e終止于定點v，定義：

用類似的定義，如果邊e從v出發，則定義：

用Y( e)表示邊e傳輸的信息。

在具有L條邊得線性網絡編碼中，網絡可以用一個L×L的鄰接矩陣表示。矩陣元素 fij∈Fq是有限域Fq中的元素。在每一個節點v處，每條邊ej∈Go(v)傳輸頂點v所收到信息的線性組合：

因此鄰接矩陣F表示了組合系數。假設信源節點s以恒定速率R生成離散的整數序列X(s)，序列中的整數也是有限域Fq的元素。在源節點s看來，所產生的信息序列可以看成來自一組虛擬邊ei∈ΓI(s), i=1,2,…,n 的輸入的線性組合，n為s和信宿節點d之間的最小割。對于每一條邊ej∈ΓO(s)，Y( ej)等于Y( ei),ei∈ΓI(s)的線性組合，即：

aij是組合系數，所有的系數組成一個n×L矩陣A。在信宿節點，定義一個L×n矩陣B，它的元素為信宿節點的所有輸入的線性組合系數：

最后，可以得到傳輸矩陣：

文獻[2]提出了隨機網絡編碼(RNC, Random Network Coding)。RNC中，矩陣A、F和B的元素都是獨立地從有限域Fq中隨機抽取的。文獻[3]證明了信宿節點能以概率(1d/q)h-成功解碼。其中d為信宿節點數，h是邊數。

在文獻[7]中，作者討論了一種實用的編碼方案。該方案中，每一條邊不僅傳輸線性組合，也同時傳輸組合系數，稱為全局向量。因此每條邊傳輸的實際上是一個方程yi=gix。在每個節點中，輸出的系數向量是所有入向量的線性組合，其組合系數與信息的組合系數相同。信宿節點把收到的所有輸入向量進行組合，可得到線性方程組y=Gx，G的每一行都是一個全局向量g。

在信宿節點d中，每一條輸入邊中傳輸矩陣G=(A( I-F)-1BT)T的一行，其中：

2 壓縮感知解碼

2.1 壓縮感知

當前的隨機網絡編碼不可解碼的概率為1-(1-d/q)h。在實際應用中[8]，如果信宿節點不能成功解碼，那么已經收到的信息會被丟棄，這樣會造成傳輸延時。

然而，如果信息序列x是稀疏的，根據文獻[5]，可以利用壓縮感知來嘗試解碼。如果傳輸矩陣G的秩是m，可以取出G中線性不相關的m行以及對應的信宿節點收到的m個信息y'，組成一個欠定方程組y'=Φx，Φ是一個m×n矩陣。壓縮感知求解的問題可以如下描述：

研究表明Φ具有文獻[5]所定義的有限等距性，因此可以進行壓縮感知。信宿節點首先執行一般的解碼，即直接求解方程組y=Φx。如果G不可逆(不滿秩)，則構造Φ并執行壓縮感知解碼算法。有多種算法可以用于壓縮感知的解碼[9-10]。

2.2 分析

在圖G=(V, E)中，按照信息傳輸的順序為每一條邊e編號。因此A和B可以寫成:

鄰接矩陣F是一個對角線元素全零的上三角矩陣。因此(I-F)-1可以寫成I+F+F2+…+Fn，定義F(m)=Fm,m∈?+，有：

為了得到感知矩陣Φ，定義Ψ=(I-F)-1，并且有：

由于B有n個非零行，每個非零行只含有一個 1，因此G由Φ得最后n列組成。令ai，φj分別表示A的第i行和Ψ的第j列，可得到：

在壓縮感知解碼中，從G中隨機選取k個不相關行組成一個k×n矩陣H。可以由H計算誤碼率。一個稀疏度為s的向量nx的誤碼率由下式確定：

現在考慮yk=Hzn的概率。令m=||xn||0，文獻[11]證明了該事件的概率為：

定義PCS fails=P(err|xn)，其含義為壓縮感知解碼失敗的概率。

對于隨機網絡編碼，常規解碼與壓縮感知解碼是獨立的。由于只有當常規解碼與壓縮感知解碼全部失敗時，網絡編碼才被視為不可解碼，因此誤碼率為：

3 仿真與結果

仿真結果重點在與觀察有限域大小和稀疏度對壓縮感知解碼的影響。圖1表明，誤碼率隨著有限域增大而降低，而CS-RNC比單純的RNC誤碼率性能較優。

圖1 誤碼率與有限域大小的關系

4 結語

隨機網絡編碼的傳輸矩陣滿足RIP條件，對于稀疏的信號，可以采用壓縮感知的方法進行解碼。對于單播情況，信宿可以同時采用一般的網絡編碼解碼和壓縮感知解碼結合，以提高解碼成功率。當隨機網絡編碼的編碼系數所在的有限域較小時，壓縮感知解碼可以明顯提高成功率。當有限域擴大時，其成功率下降，但一般的網絡編碼解碼成功率反而會增加，而且增加的更快。因此總的成功率也會增加。下一步的研究方向是尋找更適合壓縮感知的隨機網絡編碼方法。

[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network Information Flow[J]. Inform. Theory, 2000, 46(04):1204-1216.

[2] KOETTER R, MEDARD M. An Algebraic Approach to Network Coding[J]. Proc. IEEE Int Information Theory Symp, 2001, 16(04):204-216.

[3] HO T, MEDARD M, SHI J, et al. On Randomized Network Coding[J]. In Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing, 2003, 12(05):689-709.

[4] 李暉，郭長順，常全成. 基于矩陣分解的壓縮感知算法研究[J]. 通信技術，2011,44(09):108-110.

[5] CANDES E J, ROMBERG J, TAO T. Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information[J].Inform. Theory, 2006, 52(02):489-509.

[6] TSAIG Y, DONOHO D L. Compressed Sensing[J]. IEEE Trans. Inform. Theory, 2006, 52(04): 1289-1306.

[7] YUNNAN P C, CHOU P A, WU Y, et al. Practical Network Coding[J]. Inform. Theory, 2003, 12(01):419-439.

[8] 王薊翔，張揚. 無線傳感器網絡 MAC協議的研究與改進[J]. 通信技術，2011,44(06):138-143.

[9] CANDES E J,TAO T. Decoding by Linear Programming[J].Inform. Theory, 2005, 51(12):4203-4215.

[10] DONOHO D J, TANNER J. Thresholds for the Recovery of Sparse Solutions via l1 Minimization[J]. Proc.40th Annual Conf. Information Sciences and Systems,2006, 11(05): 202-206.

[11] DRAPER S C, MALEKPOUR S. Compressed Sensing over Finite Fields[J].Proc. IEEE Int. Symp. Information Theory 2009, 21(13): 669-673.