分布式无标度LT码*

李腾飞,苏伟伟,文 红

(电子科技大学通信抗干扰国家级重点实验室,四川成都611731)

分布式无标度LT码*

李腾飞,苏伟伟,文 红

(电子科技大学通信抗干扰国家级重点实验室,四川成都611731)

LT码是喷泉码的一种,在删除信道中性能优越,分布式喷泉码多信源多中继的特性适合用于深空通信中。无标度网络(SF network)具有平均路径(APL)长最小的特性,非常适合喷泉码的度分布设计需求。首先介绍了LT码的编译码算法,然后对无标度网络和基于无标度网络的SF-LT码度分布设计进行了详细分析和优化,最后在删除信道条件下,选取码长较短、删除概率较小的情形对分布式二信源SF-LT码进行仿真分析,仿真结果表明,与LT码相比,分布式SF-LT码具有更好的性能。

喷泉码 LT码 分布式SF-LT码

0 引 言

LT码[1]是喷泉码[2-3]的一种,度分布是其构造的关键,LT码节点间平均路径(APL)长度越短代表其译码效率越高,无标度网络平均路径长最小的特性,非常适合LT码节点度分度设计的需求,对于固定的节点数和平均路径长,无标度网络可以提供最小的连线数目。本文将复杂网络的无标度特性应用在LT码的度分布设计中,设计一类网络结构具有无标度特性的SF-LT码,然后根据深空通信载体资源受限的特性,设计更具实用性的分布式SF-LT码,最后在码长500,删除概率0.05的删除信道条件下对SF-LT码和分布式二信源SF-LT码的译码性能进行仿真验证,证明了分布式SF-LT码比LT码具有更好的性能。

LT码是一种由K个源数据包根据自身的度分布进行编码而生成的,而接收端只要接收到N(N稍大于K)个编码数据包就可以高概率地译码,LT码自身的度分布决定了其译码性能,度是指与该编码包相连的源数据包数目,LT码度分布用S(d)表示,其意义在于:对于所有的度d,编码分组出现度为d的概率为S(d)。

LT码的编码就是根据度分布函数S(d),从k个数据包中随机地选取d个源数据包,然后将这d个源数据包进行模二加,生成一个编码数据包。

LT码的译码过程为:找到一个度为1的编码符号tn,令与之相连的源数据包sk=tn,然后将sk与所有和sk有联系的编码数据包进行异或,最后删除所有与sk相连的编码数据包。不断重复上述过程,直到找不到度为1的编码数据包。如果存在这样的数据包,表明没有全部译码。

1 LT码无标度网络

1.1 无标度网络

网络可以表示为G=(V,E),其中V表示给定点集,E表示边集。点集中的元素称为节点,节点间的连接称为边[4]。节点i的度ki定义为与节点i相连的边数。定义网络的平均路径(APL)长度L为网络中任意两个节点间距离的平均值,也称为网络的特征路径长度,

式中,N为网络节点数,dij为网络中节点i与节点j之间连通的最小边数,也称为节点对(i,j)之间的距离。

无标度网络是目前较为常见的网络结构之一,具有特殊拓扑结构,它的度分布服从幂方律分布,在给定规模的通信网络中,无标度网络的平均路径长最小[5],典型的BA(Barabási-Albert)无标度网络模型的构造算法如下[6]:

1)初始:开始给定一个有m0个节点的网络。

2)增长:在每个时间步重复增加一个带有m条边的新节点,并且按照步骤3)中的择优概率选择m个节点与新节点相连,其中m＜m0。

3)择优连接:按照择优概率:

选择旧节点i与新节点相连,其中ki是旧节点i的度。

经过t个时间步后,生成一个有t+m0个节点和mt条边的BA无标度网络。

1.2 LT码无标度网络模型

首先从一个简单的译码例子出发,图1为LT码的编码tanner图。

图1 输入数据包为10的LT码的编码Tanner图Fig.1 Tanner graph of LT code which the input data packet is 10

si代表源数据包,ci代表编码数据包。LT码的译码过程是一个消息传递的过程。信息的传输依赖于Tanner图中的节点连线。用一个网络模型表示图1,网络节点表示编码数据包ci,节点之间的连线遵循以下规则:如果两个编码数据包在Tanner图中与同一个源数据包si相连,在网络模型中这两个节点之间相连。图2为图1匹配的网络模型。

图2 图1所生成的将原始数据包节点移除的复杂网络Fig.2 Complex network figure 1 generation which the original packet removed

在译码端,译码“信息”从度为1的节点开始,沿着图2中的连线将信息传输给与之相邻的节点,然后从图2网络中去除与之关联的边,不断重复上述过程,直到网络中不存在度为1的节点。如果图2中的网络节点关联了所有源数据包,在译码端可以成功译码。

图2中,两个节点间的路径长度代表着“译码信息”从一个节点更新到另一个节点的更新操作的次数。在一个给定规模的网络中,节点间平均路径(APL)越短,译码成功的概率越高,同时译码效率越高,基于无标度网络的平均路径长最小的特性,可以将无标度网络引入LT码度分布的设计中,构造一类网络结构具有无标度特性的LT码——SF-LT码,同时根据深空通信载体资源受限的特性,可以将SF-LT码引入分布式系统中,设计更具实用性的分布式SF-LT码。无标度网络的度分布有着幂方律特性,节点的度分布是λ(d)=Ad-γ,其中d是节点的度,λ是幂指数参数,A是使得∑dλ(d)=1的归一化参数。由于图2映射到的编码数据包和原始数据tanner图并不是唯一的,所以要对度分布进行一定的改进。定义修正后的幂律分度为[7-8]:

式中,参数P1为度为1的编码数据包概率,r为衰减因子,A为归一化因子。

考虑到由式(3)构造的度分布,度高的编码数据包的数量很少,会导致在接收编码数据包较多的情况下译码性能降低,鲁棒孤波分布(RSD)在接收编码数据包较多的情况下可以高概率地译码[1],可以考虑将二者进行有效的结合,由此定义SF-LT码的度分布,采用将无标度分布与鲁棒分布相结合的方法,具体实现方法如下:

理想的孤波度分布ρ(·):

体现其鲁棒性的分布τ(·):

式中,参数R=c·ln(k/σ)·,R则代表度为1编码数据包在整个编码数据包中的平均个数,参数σ表示接收到n个编码数据包后译码失败的概率。参数0＜c＜1,SF-LT码度分布μ(·)是理想孤波分布ρ(·)、子分布τ(·)和无标度分布λ(i)和的概率归一化结果,这样的结合使得其既有无标度特性又对实际信道有良好的适应性,最后SF-LT码度分布μ(i)定义为:

虽然SF-LT码子分布τ(i)在形式上与LT码的RSD子分布相同,但由于受无标度网络幂律分布影响,子分布参数选择可能需要调整。不同信道条件下,μ(i)子分布对于译码性能的影响程度不同,例如在低删除概率条件下,接近于理想信道,子分布ρ(·)对译码性能的影响程度最高,因为在理想信道条件下,ρ(·)的译码性能最好[1],因此,根据实际信道状况可以通过仿真测试对ρ(i)、τ(i)、λ(i)选取适当的权重系数x1、x2、x3对μ(i)进行优化,相应的,,通过这种方法使其译码性能达到较好的效果。

2 两信源分布式SF-LT码

深空通信中,通信实体距离遥远,资源受限,传播损耗较大,为了保证通信质量,在设计通信设备时有更高的要求,分布式喷泉码多信源多中继的特性,非常适合用于深空通信中,两信源单中继分布式通信系统模型如图3所示。

图3 两信源单中继分布式通信系统模型Fig.3 Model of two source and single relay communication system

2.1 分布式两信源SF-LT码度分布

考虑分布式两信源情况,如图3所示,信源s1和信源s2分别独立发送k/2个数据包,我们的目标是选择度分布p(·)使得中继R到目的节点D的数据传送服从SF-LT码度分布μ(i)。

为了求出p(·)需要进行解卷积运算,若k≥2,求SF-LT码度分布的解卷积按如下进行[9]:直接解卷积很复杂,而且还存在很多问题,例如,解出的p(k/s)可能为负值,类似于分布式LT码的度分布构造方法[9],把μ(·)分布分解并做标准化处理,首先把μ(·)分解为两个分布μ′(·)和μ″(·)的线性组合:

现在,定义新的函数:

可以计算出:

SF-LT码的参数优化方案同样适用于分布式系统,针对实际的信道条件,可以考虑为μ(i)的子分布分配不同的权重系数,提升分布式SF-LT码的译码性能。

2.2 分布式两信源SF-LT码的编译码过程

编码的第一步:图3中的两信源发送的数据X1和X2按照度分布p(·)各自独立进行LT编码,由

式中,于p(·)是f(·)、μ″(·)和参数λ的组合,我们可以认为某个数据包的度d的产生是以概率λ按照度分布f(·)产生或者以概率1-λ按照度分布μ″(·)产生。编码的第二步:信源s1和s2编码后形成的数据包在中继需要进行处理操作,由于中继知道两个信源的度分布,处理方法如下:

1)如果两个信源发出的数据包的度d都是以概率λ按照度分布f(·)产生,则在中继进行异或后传输到目的节点。

2)如果某个信源发出的数据包的度d是以概率1-λ按照度分布μ″(·)产生,则中继将该信源的数据包传输到目的节点,丢弃另外一个信源的数据包。

3)如果某个信源发出的数据包的度d都是以概率1-λ按照度分布μ″(·)产生,则中继就随机选取某个信源发生的数据包传输到目的节点。

具体实现方法如下:中继按下式产生二元变量b1和b2:

式中,di表示d1和d2,分别是X1和X2的度,Ui表示U1和U2,是中继节点产生的两个独立随机变量,两变量U1,U2在区间[0,1]服从均匀分布。然后中继经过如下处理后发送到目的节点。

式中,flip(X1,X2)表示以相同的概率随机取X1或X2的值。

数据包从中继到目的节点的传送服从SF-LT码度分布,目的节点的数据包译码过程与LT码的译码一样。

3 分布式SF-LT码性能仿真

本文在删除信道模型下,选取删除概率q= 0.05,源数据包(LT码)长度K=1 000,以接收一定数目编码包条件下,译码端的译码成功率为评价准则,对分布式SF-LT码进行性能仿真,其中,LT码选用度分布参数为c=0.05,δ=0.5,受无标度特性幂律分布的影响,SF-LT码选用度分布参数为c= 0.02,δ=0.5。

LT码与3种不同系数SF-LT码的性能仿真结果比较如图4所示。3种SF-LT码均选择参数P1= 0.08,r=2.1,其中,SF-LT码选择系数x1=0、x2=0、x3=1,SF-LT码1选择系数x1=0、x2=1、x3=1,SFLT码2选择系数x1=1、x2=1、x3=1,由仿真结果可以看到:SF-LT码在接收数据包较少的情况下译码性能比LT码好很多,但随着译码端接收数据包的增多,SF-LT码的译码性能开始下降,译码成功率低于LT码,但此时SF-LT码1和SF-LT码2的译码性能依然高于LT码,这是因为经过优化后的度分布既有无标度特性又保证了度高编码包的数目,SF -LT码2的译码性能最好。

图4 码长为1 000的4种LT码的性能比较Fig.4 Performance comparison of four kinds of LT codes which length is 1 000

对SF-LT码进行参数优化,因为仿真选用的是低删除概率,对子分布ρ(·)分配较大的权重系数,参数选择如表1所示。仿真结果如图5所示,由仿真结果可以得知:通过适当的改变参数,可以得到性能较好的SF-LT码。

表1 不同种类SF-LT码参数选择Table 1 Parameters choice of different types of SF-LT code

图5 码长为1 000的4种SF-LT码的性能比较Fig.5 Performance comparison of four kinds of SF-LT codes which length is 1 000

在两信源情况下,4种编码性能仿真结果比较如图6所示。其中,两种SF-LT码均选择系数x1= 1、x2=1、x3=1,参数选择P1=0.08,r=2.1,由仿真结果看到:SF-LT码的译码性能优于LT码,分布式SF-LT码在接收数据包较少的情况下,译码性能最好,随着接收数据包数目的增多,与分布式LT码相比,译码性能虽然有所下降,但仍保持较高的译码成功率。整体而言,分布式SF-LT码的译码性能优于LT码,与LT码相比,在载体资源受限的深空通信系统中,分布式SF-LT码更具实用价值。

图6 码长为1 000的LT码、SF-LT码的性能比较Fig.6 Performance comparison of LT codes and SF-LT codes which length is 1 000

4 结 语

本文分析了SF-LT码和两信源分布式SF-LT码各自的度分布实现和编译码方法,并对删除概率较小、短码长的SF-LT码和两信源分布式SF-LT码进行了仿真分析,仿真结果表明,与LT码相比,分布式SF-LT码具有更好的性能,在深空通信中更具实用价值,本文的结果还为SF-LT码技术的应用提供了很好的参数选择依据。

[1] LUBY M.LT Codes[C]//Foundations of Computer Science.United States:IEEE press,2002:271-280.

[2] 杨玲,宋时立,刘国超,等.LT码的性能分析及仿真[J].通信技术,2012,45(05):1-3.

YANG ling,SONG Shi-li,LIU Guo-chao,et al.The Performance of LT Codes Analysis and Simulation[J].Communications Technology,2012,45(05):1-3.

[3] 刘国超,陈霄,苏伟伟,等.短长度分布式喷泉码的性能分析[J].通信技术,2012,45(08):5-8.

LIU Guo-chao,CHEN Xiao,SU Wei-wei,et al.The Performance of Short Length of Distributed LT Codes[J]. Communications Technology,2012,45(08):5-8.

[4] 汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:3-33.

WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Complex Network Theory and Its Application[M].Version 1.Beijing:Tsinghua University Press,2006:3-33.

[5] BOLLOBÁS B,RIORDAN O.Robustness and Vulnerability of Scale-free Random Graphs[J].Internet Math, 2003,1(01):1-35.

[6] BARABÁSI A.L,ALBERT R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.

[7] HYYTIÄ E,TIRRONEN T,VIRTAMO J.Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach[C]//6th International Workshop on Rare Event Simulation.Bamberg:RESIM press,2006:64-73.

[8] CHEN C M,CHEN Y,SHEN T C,et al.Optimizing Degree Distributions in LT Codes by Using the Multiobjective Evolutionary Algorithmbased on Decomposition [C]//Evolutionary Computation(CEC),2010 IEEE Congress on.Shanghai:IEEE press,2010:1-8.

[9] PUDUCHERI S,KLIEWER J,FUJA T E.Didtributed LT Codes[C]//2006 IEEE International Symposium on Information Theory.United States:IEEE press,2006:987-991.

LI Teng-fei(1988-),male,M.Sci., majoring in channel coding,image processing.

苏伟伟(1988—),男,硕士,主要研究方向为信道编码;

SU Wei-wei(1988-),male,M.Sci.,majoring in channel coding.

文 红(1969—),女,博士,教授,主要研究方向为编码原理与技术、密码学、信号处理、网络安全通信。

WEN Hong(1969-),female,Ph.D.,professor,mainly working at coding theory and technology,cryptography,signal processing and network communication security.

Distributed Scale-free LT Codes

LI Teng-fei,SU Wei-wei,WEN Hong
National Key Lab of Communication of UESTC,Chengdu Sichuan 611731,China;

LT code is one of the fountain codes which performs well in erasure channel.The characteristics of multi sources and multi relays make distributed fountain codes fit for deep space communications.Scale -free network has the characteristic of the minimum average path length which makes it perfect for the design requirement of degree distribution in fountain codes.The encoding and decoding algorithm of LT codes is introduced in this paper first,then the design of degree distribution in scale-free networks and SF-LT codes based on the scale-free network is analyzed and optimized.At last,under the condition of erasure channel,the simulation of SF-LT codes with distributed binary sources under shorter code length and lower erasure probability is done.The result shows that distributed SF-LT codes have better performance than LT codes.

fountain codes,LT codes,distributed SF-LT codes

TN911.22

A

1002-0802(2014)08-0854-06

10.3969/j.issn.1002-0802.2014.08.003

李腾飞(1988—),男,硕士,主要研究方向信道编码、图像处理;

2014-05-20;

2014-07-03 Received date：2014-05-20;Revised date：2014-07-03

国家自然科学基金项目(No.61032003,No.61271172);高等学校博士学科点专项科研基金(No.20120185110030, No.20130185130002)和四川省国际合作研究项目(No.2013HH0005)联合资助

Foundation Item:NSFC(No.61032003,61271172),RFDP(No.20120185110030,No.20130185130002),Sichuan International Corporation Project(No.2013HH0005)and SRF for ROCS,SEM.