基于壓縮感知解碼的網(wǎng)絡(luò)編碼技術(shù)

高 超， 李生紅， 唐俊華

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

0 引言

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

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

1 系統(tǒng)模型

考慮單源單信宿的無誤差無環(huán)網(wǎng)絡(luò)。用一個有向圖G=(V, E)表示此網(wǎng)絡(luò)，V為頂點集，E為邊集。每條邊的容量為單位容量。如果兩個節(jié)點之間實際容量大于 1，則用多條邊表示。文獻[2]中描述了這種模型。每條邊用一個整數(shù)表示?？梢杂靡粋€三元組e=(vi, vj, k )表示。如果一條邊e終止于定點v，定義：

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

用Y( e)表示邊e傳輸?shù)男畔ⅰ?/p>

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

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

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

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

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

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

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

2 壓縮感知解碼

2.1 壓縮感知

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

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

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

2.2 分析

在圖G=(V, E)中，按照信息傳輸?shù)捻樞驗槊恳粭l邊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個不相關(guān)行組成一個k×n矩陣H?？梢杂蒆計算誤碼率。一個稀疏度為s的向量nx的誤碼率由下式確定：

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

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

對于隨機網(wǎng)絡(luò)編碼，常規(guī)解碼與壓縮感知解碼是獨立的。由于只有當(dāng)常規(guī)解碼與壓縮感知解碼全部失敗時，網(wǎng)絡(luò)編碼才被視為不可解碼，因此誤碼率為：

3 仿真與結(jié)果

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

圖1 誤碼率與有限域大小的關(guān)系

4 結(jié)語

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

[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]. 通信技術(shù)，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] 王薊翔，張揚. 無線傳感器網(wǎng)絡(luò) MAC協(xié)議的研究與改進[J]. 通信技術(shù)，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.