基于规则变量节点度LT码的协作传输

祝开艳, 王洪玉, 孙文珠, 宋维波

(1. 大连理工大学电子信息与电气工程学部, 辽宁 大连 116024;

2. 大连海洋大学信息工程学院, 辽宁 大连 116023;

3. 山东理工大学计算机科学与技术学院, 山东 淄博255049)



基于规则变量节点度LT码的协作传输

祝开艳1,2, 王洪玉1, 孙文珠3, 宋维波2

(1. 大连理工大学电子信息与电气工程学部, 辽宁 大连 116024;

2. 大连海洋大学信息工程学院, 辽宁 大连 116023;

3. 山东理工大学计算机科学与技术学院, 山东 淄博255049)

摘要：规则变量节点度Luby变换(Luby transform, LT)码能够改善传统LT码编码过程中随机选取邻居节点方式导致的差错平台现象。提出一种新的实现规则变量节点度LT的编码方法,利用数组的赋值和清空操作来实现信息符号度值规则化,降低了现有方法的编码复杂度,并利用对度分布的修正来改善解码瀑布区;将该编码方法应用到协作通信系统中,并分析了误符号率性能。实验结果表明,此方法能节省系统编解码时间,有效降低误符号率差错平台,减少成功解码所需的平均传输开销。

关键词：协作通信; 喷泉码; 规则变量节点度Luby变换码; 差错平台; 度分布

0引言

喷泉码又称为无码率码,信源根据信息符号(又称输入符号或变量节点),可以源源不断地编码出无穷多个编码符号(又称输出符号或校验节点),解码端只要接收到足够多的编码符号就能成功还原信息符号[1]。与固定码率编码方法相比,喷泉码的无码率特性使得喷泉码更能适应时变信道。因此,喷泉码非常适合应用到具有多条传输链路的协作通信系统中。近几年不断有学者将数字喷泉码应用到无线协作通信网络中[2-4]。

2002年Luby提出了第1种可以实用的喷泉码——Luby变换(Luby transform, LT)码,并给出了理想孤波分布(ideal soliton distribution, ISD)和鲁棒孤波分布(robust soliton distribution, RSD)2种度分布[5]。随着研究的深入,对数字喷泉码的研究主要集中在编译码算法、度数分布函数、码长设计、网络容量等方面[6-8],而且随着工程类实际应用的推广,近年来更加集中于数字喷泉码的应用研究[9-11]。

在大多数数字喷泉码的编码过程中,对信息符号的选取均为随机选取。文献[12-14]首次提出了规则变量节点度分布LT码(regular variable-node degree LT codes,RLT)的概念和编码方法[12-14],基本思想是在编码端使得信息符号参与编码的次数相同,即度值规则化。RLT码被分别应用于删除信道和噪声信道中,显著降低了传统LT码的差错平台,但该RLT码编码方法需要维护一个信息符号度值查找表,编码过程中需要对该表进行排序和查找操作,这在一定程度上增加了编码的复杂度,且复杂度随着信息符号数增大而快速增加;此外,该RLT编码方法会导致解码瀑布区域(雪崩区域)延后,相比于传统LT码增加了成功解码所需的传输开销。

针对上述问题,本文提出一种新的RLT码编码方法,省去了对信息符号度值查找表的排序、查找和更新过程,降低了编码复杂度,并将其应用于协作通信系统。与现有方法相比,本文方法能节省系统编解码时间,有效降低误符号率差错平台的同时不会增加信源平均传输次数。

1LT码

LT码可由2个参数(k,q(x))简单表示,k为信息符号的数目,q(x)为集合Nk={1,2,…,k}上的离散概率分布,称为编码符号度分布(degree distribution,DD)。LT码编码过程首先根据度分布q(x)随机产生一个度值d(d称为编码符号的度),然后从k个信息符号中选取d个信息符号进行异或来产生编码符号,参与编码的信息符号称为编码符号的邻居节点(neighbor node,NN)。

LT码中度分布分为节点度分布和边度分布,前文中度分布q(x)指编码符号节点度分布。编码符号节点度分布q(x)和信息符号节点度分布v(x)为

(1)

编码符号边度分布ω(x)与信息符号边度分布λ(x)定义为

(2)

式中，qi,vi,ωi,λi分别表示各节点度值和边度值为i的概率。

边度分布与节点度分布之间的关系为

(3)

定义α和β分别为信息符号节点平均度和编码符号节点平均度,其值为

(4)

设信息符号数目为k,接收端成功译码需要接收到的编码符号数为Nd,定义译码开销为ε=Nd/k,则α和β有如下关系:

(5)

(6)

2RLT码

2.1编码方法描述

在传统LT码的编码过程中,每个编码符号的邻居节点都是从信息符号中随机选取的,这种随机选取的方式会使得某些信息符号参与编码的次数很少或未参与编码的情况,从而导致了传统LT码的差错平台现象(erasure-floor)[12-14]。文献[12-14]在编码端引入一个信息符号度值表来记录编码过程中每个信息符号参与编码的次数,即信息符号的度值。每次编码之前对信息符号度值表进行排序;每次编码时在度值符号表中查找度值最小的信息符号进行编码;每次编码结束后,对信息符号度值表进行更新,以便下次编码使用。这种编码方式,在编码端能够确保信息符号参与编码的次数相同,即度值相同,因此也称为规则变量节点度LT码。这种编码方式能降低译码的差错平台,但是增加了编码的复杂度,且信息符号个数越大,编码过程越复杂;此外,采用RSD分布的规则变量节点度LT码应用在删除信道时,会导致解码瀑布区域(雪崩区域)延后,相比于传统LT码增加了成功解码所需的传输开销。

本文给出一种新的RLT码编码方法,该方法在编码端通过对3个数组的赋值和清空操作来实现信息符号度值规则化,不需要记录信息符号的度值,省去了对信息符号度值查找表的排序、查找和更新过程,从而降低了编码复杂度。表1给出了该方法的具体实现过程。其中数组c_set中元素表示待选信息符号序号,数组h_set中元素表示已参与当前编码的信息符号序号,temp_set数组中元素为临时符号序号。

2.2度分布修正

编码符号节点度分布q(x)是决定LT码性能的关键因素。文献[5]中设计了ISD分布,用ρ(i)表示ISD分布中编码符号度值为i的概率,ρ(·)定义为

(7)

表1　规则变量节点度LT codes编码方法

(8)

通过将τ(·)和ρ(·)叠加,并进行归一化,得到RSD分布。用μ(·)表示RSD分布中编码符号度值为i的概率,RSD分布表达式为

(9)

在编码符号节点度分布的设计中,较大的度值是为了使所有的信息符号都能够参与编码,而较小的度值是为了加快解码的开始和维持解码过程的连续性。解码瀑布区域主要由度分布中较小度值的概率决定。由于RLT码的编码方式保证了所有的信息符号都能够参与编码且参与编码的次数几乎相等,因此可以通过增加度分布中较小度值的概率来使解码瀑布区域提前。本文以最常见的RSD分布为例,通过对RSD分布的修正来提高较小度值在度分布中所占的比重。由于度值为1和2的概率对解码瀑布区域起非常关键的作用,本文考虑增加RSD分布中度值为1和2的概率。本文通过对式(8)中的τ(1)和τ(2)进行加权来增加RSD分布中度值为1和2概率,引入参数θ1和θ2,得到加权后的函数τ′(x):

(10)

将加权后的函数τ′(x)代入式 (9)得到修正后的RSD分布。文献[16]讨论了θ2与θ1之间的关系,通过多次实验得到两者之间的近似关系:θ2=2θ1;通过改变θ1的值,可以有效的改变规则变量节点度LT码解码瀑布区域的开始点;11≤θ1≤16时,解码瀑布区域开始点对应的传输开销值最小。

3基于RLT码的协作传输

图1　三端协作系统模型

下面分别对采用传统LT码和采用RLT码的三端协作通信系统的误符号率进行分析。设需要传输的数据包个数为k,信源发送符号总数目为Ns,中继发送符号总数目为Nr,目的端实际接收到的符号数目为Nd,则有

(11)

为简化分析,假设中继接收到k个编码包就能成功解码,且不考虑中继解码和编码造成的时延(因为数字喷泉码采用信息累积方式解码,中继造成的时延主要会造成接收端解码的时延,而对接收端解码的成功率和误符号率影响不大),可得到Ns与Nr之间的关系为

(12)

根据式(11)和式(12)可得Nd与Ns之间的关系为

(13)

3.1基于传统LT码的协作传输误符号率分析

信源和中继编码端都采用传统LT码时,目的端接收到的信息符号的度分布服从泊松分布[16],其平均度为α=εβ=βNd/k。当编码长度k→∞时,信息符号节点度分布v(x)表示如下:

(14)

编码符号边度分布函数ω(x)和信息符号的边度分布函数λ(x)可根据式(3)和式(14)求出。将ω(x)和λ(x)带入式(9)可求得k→∞时基于LT码的协作传输误符号率。

(15)

3.2基于RLT码的协作传输误符号率分析

信源和中继编码端都采用RLT码时,目的端接收到的信息符号的度分布不再服从泊松分布,需要重新分析。设整个传输过程中系统的丢包数目为Ne,则

(16)

RLT码在编码过程中使得编码端所有的信息符号度相等。当信道丢包率为0时,接收端接收到的编码符号中信息符号度和发送端相同。信息符号的平均度为α,由于度值为正整数,因此每个信息符号的度为|α|或|α|-1,信息符号的度分布为

(17)

式中，h=|α|,vh-1和vh可根据式(18)计算:

(18)

当信道丢包率不为0时,由于规则变量节点度LT码各个编码符号之间存在一定的关联性,接收端信息符号的度分布不再服从式(17),接收端信息符号度分布可由定理1得出。

定理 1设信源发送符号数目为Ns,中继发送符号数目为Nr,信道丢包数目为Ne,接收端信息符号节点度分布为

(19)

式中

(20)

(21)

推广到更一般的情况,即编码端信息符号节点度分布如式(17)所示时,将式(21)推广即可得式(19)。

证毕

根据定理1得到的接收端信息符号节点度分布后,再利用式(3)求出对应的信息符号边度分布λ(x),代入式(9)即可求出基于RLT的协作传输误符号率。

图2　基于不同编码方法的协作传输方案的误符号率理论分析比较

4仿真结果及分析

本节分别从编解码时间,误符号率和目的端译码所需信源平均传输次数3个方面在k取有限值的条件下将本文方法(MRLT)与文献[16]中方法(RLT)以及传统LT码进行比较。度分布采用RSD分布,c=0.03,δ=0.5。

4.1编解码时间比较

传统LT码编码复杂度只要由编码符号的异或运算次数决定,即由编码符号平均节点度决定。文献[16]中的RLT和传统LT码均采用RSD分布,而本文采用的MRLT编码方法对RSD度分布进行了修正,增加了小度值编码符号的概率,因此本文采用的MRLT编码符号的平均度最小。另一方面,文献[16]中RLT编码过程中还需对信息符号度值表进行排序、查找和更新操作,在一定程度上增加了编码复杂度。本文编码方法省去了对信息符号度值表的排序和查找操作,只需对3个数组进行赋值和读取操作,因此与文献[16]中RLT相比降低了一定的复杂度。与传统的LT码相比,本文编码方法多了对3个数组的操作,因此复杂度稍高。表2比较了不同信息符号长度k时上述3种编码方法所需的编码时间。编码时间在配置为Intel(R)Core(TM)2CPU2.93GHz,内存为2GB的电脑上测得,编程语言环境为Matlab,编码符号的总数均为10 000。

由于RLT和LT解码过程都采用BP算法,其复杂度都主要由所有参与解码的编码符号的平均节点度决定,因此在编码端度分布相同的前提下,两者所需的解码时间相差不大。

表2　编码时间比较　s

4.2误符号率比较

图3给出了不同信道条件下基于传统LT码、RLT码和MRLT码的三端协作传输的误符号率仿真性能比较,其中传输的数据包数分别取k=1 000和k=5 000,蒙特卡罗仿真105次。从图中可以看出,采用本文编码方法MRLT的协作传输误符号率曲线收敛速度明显优于基于传统LT码和基于文献[16]中RLT编码的协作传输。另外,相同信道条件下,k值越大,译码所需的译码开销相对较小,这一点与传统的LT码的性质一致;k值相同时,信道条件的变化对误符号率曲线的影响不大。需要说明的是,图2中误符号率理论分析曲线中,在k趋于无穷大时基于RLT编码的方法改善了传统LT码带来的差错平台现象,但当k值较小时这一优势并不明显,另外其性能优势在误符号率数量级小于10-6时才能体现出来,因此从图3中并不能体现RLT方法比LT码的性能提升。

图3　基于不同编码方法的协作传输方案的误符号率仿真曲线

4.3信源平均传输次数比较

图4给出了分别采用传统LT码、RLT码和MRLT码编码方法时,三端协作传输系统中目的端成功译码时所需的信源平均传输次数与SD链路的丢包率之间的关系。对不同信道条件下k=1 000和k=5 000时信源平均传输次数进行了仿真,蒙特卡罗仿真次数为10 000次。从图中可以看出,随着信道丢包率的增加,目的端成功译码时所需的信源平均传输次数随之增加;在两种不同信道条件下,基于MRLT码编码方法所需信源传输次数最少,基于传统LT码其次,基于文献[16]中RLT码编码方法所需信源传输次数最多;另外信道条件的变化对这一性能影响不大。因此,采用本文提出的MRLT编码方法在有效改善差错平台现象的同时减少了译码所需信源平均传输次数。

图4　基于不同编码方法的协作传输中译码所需信源平均传输开销比较

5结论

数字喷泉码自适应的实现码率与时变信道容量的匹配特点使得它非常适合于无线中继网络中的协作通信。为了解决基于数字喷泉码的协作传输中的差错平台问题,本文提出了一种新的实现规则变量节点度LT的编码方法,降低了现有规则变量节点度LT码的编码复杂度,加快了误符号率曲线的收敛速度,并利用对度分布的修正来改善解码瀑布区域,在此基础上又提出了基于规则变量节点度LT码的协作传输方案并对误符号率进行了分析。理论分析和仿真结果表明,与现有方法相比,本文方法在有效改善差错平台现象的同时减少了译码所需信源平均传输次数。本文后续研究重点是进一步研究规则变量节点度LT码在多用户分布式协作通信中的应用,进一步提高无码率协作传输的有效性和可靠性。

参考文献：

[1] Byers J W, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliable multicast[J].IEEEJournalonSelectedAreasinCommunications, 2002, 20(8):1528-1540.

[2] Tran T, Anpalagan A, Hyung Y K. Multi-hop cooperative transmission using fountain codes over Rayleigh fading channels[J].JournalofCommunicationsandNetworks,2012,14(3):267-272.

[3] James A, Madhukumar A S, Kurniawan E, et al. Performance analysis of fountain codes in multihop relay networks[J].IEEETrans.onVehicularTechnology,2013,62(9):4379-4391.

[4] Zhu K Y, Wang H Y, Sun W Z. Rateless cooperative transmission based on network coding and relay selection[J].SystemsEngineeringandElectronics, 2013, 35(11):2439-2444.(祝开艳,王洪玉,孙文珠. 基于网络编码和中继选择的无码率协作传输[J]. 系统工程与电子技术, 2013, 35(11):2439-2444.)

[5] Luby M. LT codes[C]∥Proc.ofthe43rdAnnualIEEESymposiumonFoundationsofComputerScience, 2002:271-280.

[6] Yen K K, Liao Y C, Chen C L, et al. Modified robust soliton distribution(MRSD)with improved ripple size for LT codes[J].IEEECommunicationsLetters, 2013, 17(5):976-979.

[7] Khaled F H, Shahram Y. Improved systematic fountain codes in AWGN channel[C]∥Proc.ofthe13thCanadianWorkshoponInformationTheory, 2013:148-152.

[8] Sorensen J H, Popovski P, Ostergaard J. Design and analysis of LT codes with decreasing ripple size[J].IEEETrans.onCommunications, 2012, 60(11):3191-3197.

[9] Yue G S, Uppal M M, Wang X D. Doped LT decoding with application to wireless broadcast service[C]∥Proc.oftheIEEEInternationalConferenceonCommunications, 2011:1-5.

[10] Sorensen J H, Popovski P, Ostergaard J. UEP LT codes with intermediate feedback[J].IEEECommunicationsLetters, 2013, 17(8):1636-1639.

[11] Namjoo E, Aghagolzadeh A, Museviniya J. A new rateless code with unequal error protection property[J].ComputersandElectricalEngineering, 2013,(39):1980-1992.

[12] Hussanin I, Ming X, Rasmussen L K. Error floor analysis of LT codes over the additive white Gaussian noise channel[C]∥Proc.oftheIEEEGlobalTelecommunicationsConference,2011:1-5.

[13] Hussanin I, Ming X, Rasmussen L K, et al. Design of spatially-coupled rateless codes[C]∥Proc.oftheIEEE23rdInternationalSymposiumonPersonalIndoorandMobileRadioCommunications, 2012:1913-1918.

[14] Hussanin I, Ming X, Rasmussen L K. Design of LT codes with equal and unequal erasure protection over binary erasure channels[J].IEEECommunicationsLetters,2013,17(2):261-264.

[15] Luby M, Mitzenmacher M, Shokrollahi M A. Analysis of random processes via and-or tree evaluation[C]∥Proc.ofthe9thAnnualACM-SIAMSymposiumonDiscreteAlgorithms,1998:364-373.

[16] Sun W Z, Wang H Y, Zhu K Y, et al. A novel encoding scheme for regular variable-node degree LT codes[J].ActaElectronicaSinica,2014,42(10):1918-1924.(孙文珠,王洪玉,祝开艳,等. 一种规则变量节点度LT codes编码方案[J].电子学报,2014,42(10):1918-1924.)

祝开艳(1980-),女,讲师,博士研究生,主要研究方向为协作通信、网络编码技术、数字喷泉码编码技术。

E-mail:zkycat@126.com

王洪玉(1968-),男,教授,博士研究生导师,博士,主要研究方向为无线协作通信技术,自组织网络及无线传感器网络技术等。

E-mail:whyu@dlut.edu.cn

孙文珠(1982-),男,博士研究生,主要研究方向为信源信道联合编码技术、数字喷泉码。

E-mail:sunwenzhu@mail.dlut.edu.cn

宋维波(1981-),男,讲师,硕士，主要研究方向为机器人控制技术。

E-mail:swb@dlou.edu.cn

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141031.1029.005.html

Cooperative transmission with regular variable-node degree LT codes

ZHU Kai-yan1,2, WANG Hong-yu1, SUN Wen-zhu3, SONG Wei-bo2

(1.FacultyofElectronicsInformationandElectronicalEngineering,DalianUniversityofTechnology,

Dalian116024,China; 2.CollegeofInformationEngineering,DalianOceanUniversity,

Dalian116023,China; 3.CollegeofComputerScienceandTechnology,

ShangdongUniversityofTechnology,Zibo255049,China)

Abstract:Regular variable-node degree Luby transform (LT)codes can reduce the erasure floor of traditional LT codes, which are caused by choosing neighbor nodes randomly in the encoding process. A novel encoding scheme for regular variable-node degree LT codes is proposed. Compared with existing methods, the proposed scheme utilizes assignments and empty operation for arrays to realize the regulation of information symbol value, reducing the complexity of existing methods. Meanwhile, by modifying the degree distribution, the waterfall area(avalanche area)in decoding regular variable-node degree LT codes is improved. Finally, the proposed coding method is applied to the cooperative communication system, and the symbol error rate is analyzed. Experimental results show that this scheme can save system coding time, effectively reduce the symbol error rate erasure floor, and decrease the average transmission overhead required for the successful decoding.

Keywords:cooperative communications; fountain codes; regular variable-node degree Luby transform (LT) codes; erasure floor; degree distribution

作者简介：

中图分类号：TN 925

文献标志码：ADOI:10.3969/j.issn.1001-506X.2015.05.29

基金项目：国家自然科学基金(61172058)资助课题

收稿日期：2014-07-02；修回日期：2014-10-22；网络优先出版日期：2014-10-31。