高 超， 李生紅， 唐俊華

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

0 引言

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

2 壓縮感知解碼

2.1 壓縮感知

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

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

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

2.2 分析

在圖G=(V, E)中，按照信息傳輸?shù)捻樞驗(yàn)槊恳粭l邊e編號(hào)。因此A和B可以寫成:

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

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

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

在壓縮感知解碼中，從G中隨機(jī)選取k個(gè)不相關(guān)行組成一個(gè)k×n矩陣H?？梢杂蒆計(jì)算誤碼率。一個(gè)稀疏度為s的向量nx的誤碼率由下式確定：

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

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

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

3 仿真與結(jié)果

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

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

4 結(jié)語

隨機(jī)網(wǎng)絡(luò)編碼的傳輸矩陣滿足RIP條件，對(duì)于稀疏的信號(hào)，可以采用壓縮感知的方法進(jìn)行解碼。對(duì)于單播情況，信宿可以同時(shí)采用一般的網(wǎng)絡(luò)編碼解碼和壓縮感知解碼結(jié)合，以提高解碼成功率。當(dāng)隨機(jī)網(wǎng)絡(luò)編碼的編碼系數(shù)所在的有限域較小時(shí)，壓縮感知解碼可以明顯提高成功率。當(dāng)有限域擴(kuò)大時(shí)，其成功率下降，但一般的網(wǎng)絡(luò)編碼解碼成功率反而會(huì)增加，而且增加的更快。因此總的成功率也會(huì)增加。下一步的研究方向是尋找更適合壓縮感知的隨機(jī)網(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] 王薊翔，張揚(yáng). 無線傳感器網(wǎng)絡(luò) MAC協(xié)議的研究與改進(jìn)[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.