协同网络中AR码的度分布优化设计
2021-09-29黄加佳
黄加佳 雷 菁 黄 英
(国防科技大学电子科学学院, 湖南长沙 410073)
1 引言
无码率码(Rateless Code)又称喷泉码(Fountain Codes)[1],其发送端可以根据接收端译码情况而产生无限多的编码符号。无码率码的这一特性非常适用于广播及视频等应用场景,已经应用于3GPP的多媒体广播和多播服务标准[2],以及DVB的数据广播内容分发协议[3]中。
无码率码的研究发展以提高不同场景传输性能和减小复杂度为目标:Luby等人[4]在2002年提出第一款简单实用的LT码(Luby Transform Code),其在删除信道中拥有良好性能,但在噪声信道下存在明显错误平层;Shokrollahi等人[5]于2006年提出了在LT码基础上增加低密度奇偶校验码(low-density parity-check,LDPC)作为预编码的Raptor码,该码在改善错误平层的同时极大增加了编译码的复杂性;2008年Wu Kedi等人[6]针对加性高斯白噪声(Additive White Gaussian Noise, AWGN)信道,提出结构复杂度低、性能良好的累积无码率码(Accumulate Rateless Code,AR码),但其度分布的设计依赖信道质量的优劣;非规则重复码(Irregular Repeat-Accumulate,IRA)在2000年被提出,孙蓉等人[7]于2010年证明了该码的无码率特性,但该码的最小码率受到限制;2011年由Ma Xiao等人针对噪声信道,并引入p序列设计了Kite码,其缺陷在于与时间相关的p序列求取算法复杂;2012年Jonathan Perry等人[8]通过在编码结构中引入哈希函数,提出新型无码率码Spinal码,在安全性提高的同时也存在译码复杂度过高的问题;为提高不同场景的适应性,不断有新的无码率码(如网络喷泉码[9]等)被提出。相对于其他无码率码,AR码在复杂度和传输性能上有较好的折衷。Chen Shaolei等人[10]使用外信息转移(extrinsic information transfer,EXIT)图法对系统与非系统AR码进行分析研究,在优先选取度值较小信息节点的前提下使用逐步边缘增长算法和凸优化算法,求出其在不同信道噪声功率条件下的最佳度分布,并仿真得到与Raptor码相近传输性能。雷维嘉等人[11]以最小化译码迭代次数为约束条件,对非系统AR码的度分布进行优化设计,并给出在固定迭代次数下的最佳度分布。上述对AR码的研究主要集中在点对点通信上,并不能很好拓展到网络通信当中。
针对5G物联网[12-13]、无人机蜂群[14-15]等大规模网络,固定码率带来的时延和多反馈问题无法回避,将无码率码引入可很好地适应不同信道环境。Castura J等人[16]首先提出中继传输系统中的无码率码方案,使用Raptor码编码,在信道状态信息未知情况下表现得更加稳定高效。雷维嘉等人[17]针对无码率码在协作中继传输系统的应用,提出能量累积和信息累积两种方式以降低反馈,减小传输时间和功耗。文献[18-21]将无码率码结合分布式网络编码应用到无线传感器网络中,在源节点、中继节点和目的节点形成基于图码的传输结构。文献[22-23]则分析了多路并行的传感器中继网络中无码率码方案较自动重传请求(Automatic Repeat-reQuest,ARQ)方案时延更小。现有研究主要集中在LT码和Raptor码,而从性能与复杂度的折衷来考虑,探讨基于AR码的可行传输方案有着重要价值。本文将基于多中继模型探讨AR码的传输方案,设计联合度分布优化方法,开展性能分析与仿真。
2 信道模型
多中继模型是大规模网络中的典型模型,如图1所示。
图1 多中继网络模型Fig.1 Multi-relay network model
源节点S为数据采集节点,将收集到的数据向中继和目的节点广播发送,定义i时刻发送的信号向量为Xi。中继节点R1～Rn负责接收和转发数据,协助源节点通信,对应其转发信号向量分别为Ui1～Uin。目的节点D同时接收来自源节点和中继节点的数据,汇总处理后传入上级网络,定义其接收的总信号向量为Yi。考虑准静态瑞利衰落信道,即信号噪声在同一传输数据包内保持恒定,在包与包之间独立变化。同时假设直传信道S-D与所有中继信道Ri-D均具有相同的衰落特征,根据文献[15]可知:
(1)
3 基于AR码的协同传输方案
在中继传输中使用无码率码,能够降低反馈信息的传输量,并在多中继的情况下明显提高传输效率[17]。而LT码存在明显的错误平层,考虑性能和复杂度的折衷,我们采用结构简单的AR编码方案,以提高通信质量。
3.1 协同传输方案
以无线传感器网络(Wireless Sensor Network, WSN)为应用背景,其中源节点因资源受限而不进行数据编码,中继节点可进行简单编码转发,目的节点拥有足够的处理能力。通过中继节点选择机制选择两个最优节点R1和R2并采用AR编码转发,具体协同方案如图2所示。
图2 AR码协同传输方案Fig.2 Cooperative transmission scheme of AR code
广播阶段:假设源节点S需要发送的源数据为独立同分布的信息序列,我们将其按一定长度分成多个组别,每个组中数据按照802.15.4协议规定添加包头地址信息和尾部循环冗余校验(Cyclic Redundancy Check, CRC)封装成数据包,经过BPSK调制后不断向中继节点和目的节点广播发送。当收到中继节点全部正确接收数据的反馈后停止广播,进入监听状态以节约能量。
图3 中继节点数据包格式Fig.3 Packet format of relay node
译码阶段:目的节点D对接收数据解调后根据标识符信息进行分类存储,当总的存储数据量大于某一设定值时进行译码。译码后的数据可根据CRC信息判断正确性。当源数据全部正确译出时,向源节点和中继节点发送反馈信息,开始下一组数据传输;反之则继续接收更多数据包后再译。
相比传统ARQ方案的不断等待反馈确认,AR方案与其他无码率码(Raptor码和LT码)方案[21-22]一样,其数据具有独立性和无限性,使得中继节点与源节点能够很好协同传输而提高恶劣信道条件下的适应性,减少反馈次数。
3.2 等效编码结构
假设源节点需要发送的信息序列为(s1,s2,...,sK),根据3.1分析可知,每个编码数据校验节点都有一个度值d,对于节点S直接发送的数据可等效看成其度值为1,将节点D收到的所有数据对应到同一个码图上来,其等效编码结构如图4所示。
图4 整体编码结构等效图Fig.4 Overall coding structure
图4中虚线框将校验节点和编码节点分成了三部分,P0,1～P0,k为直传数据,P1,1～P1,∞为R1产生的任意数量编码数据,P2,1～P2,∞对应R2。校验节点C1,1～C1,∞的度分布(不包括与编码节点所连接的边)为Ω1(x),对应边分布为ρ1(x);C2,1～C2,∞对应为Ω2(x)和ρ2(x)。信息节点的度分布和边分布为Λ(x)和λ(x)(不包括与直传数据检验节点连接的边)。根据编码规则有:
Cq,i=sj1⊕sj2⊕...⊕sjn,(q=0,1,2)
(2)
式(2)中sj表示所有与校验节点Cq,i相连的信息节点。
(3)
我们使用优先选取度值较小信息节点的方式进行编码,以减小AR码Tanner图中小环的出现。这样信息节点的度数绝大部分将为ds,极小部分为(ds±1)或(ds±2)。若中继1对应信息节点度为d1s,中继2为d2s,有:ds≐d1s+d2s。假设信息节点长度为K,两个中继编码节点长度均为N,则该方案的近似瞬时码率为:
(4)
3.3 译码原理
我们在接收端使用对数似然比置信传播(Log Likelihood Ratio Based Belief Propagation, LLR-BP)算法进行迭代译码,AR码的译码迭代过程如图5所示。
图5 AR码译码软信息迭代示意图Fig.5 Diagram of AR code decoding whit soft information iteration
我们定义各参数如下:接收到的中继编码节点信息(y1,y2,...,yN);信息节点i传递给校验节点j的信息L(scij);校验节点j传给信息节点i的信息为L(csji);校验节点j传给编码节点k的信息为L(cpjk); 编码节点k传给校验节点j的信息为L(pckj);与信息节点i相连的校验节点j的集合Q1(i);与校验节点j相连的信息节点i的集合Q2(j);与校验节点j相连的编码节点k的集合Q3(j);与编码节点k相连的校验节点j的集合Q4(k)。
LLR-BP算法的译码基本步骤如下:
1)初始化
编码节点的初始信息概率的似然比为:
(5)
2)校验节点更新
对所有校验节点j和其相邻的信息节点i,第l次迭代时,计算校验节点传向信息节点的信息:
(6)
对所有校验节点j和其相邻的编码节点k,第l次迭代时,计算校验节点传向编码节点的信息:
(7)
3)信息节点更新
对所有的信息节点i和其相邻的校验节点j,第l次迭代时,计算信息节点传向校验节点的信息:
(8)
4)编码节点更新
对所有的编码节点k和其相邻的校验节点j,第l次迭代时,计算编码节点传向校验节点的信息:
(9)
5)译码判决
信息节点利用收集到的所有信息进行硬判决:
(10)
6)停止条件
设定门限值L0(s),当|L(si)|
3.4 度分布优化
接下来利用EXIT图分析AR方案译码的迭代过程,进而优化编码度分布。
该方案的EXIT图模型如图6所示,两中继校验节点C到编码节点P的输出平均互信息分别为IC1P1(zp1)和IC2P2(zp2),到信息节点S的输出平均互信息为IC1S(zs1)和IC2S(zs2),编码节点P到校验节点C的输出平均互信息为IP1C1(x1)和IP2C2(x2),信息节点S到校验节点C的输出平均互信息为ISC1(y1)和ISC2(y2)。
图6 AR方案EXIT图模型Fig.6 EXIT chart of AR scheme
根据迭代规则[10],可以拓展双中继AR方案在第l次迭代译码时的互信息转换式为:
(11)
(12)
(13)
(14)
(15)
J函数为发送端与接收端LLR信息间的互信息函数,在定义域[0,+∞)和值域[0,1)上单调递增,其具体表达式为:
(16)
(17)
其中:
(18)
(19)
g1与g2分别表示某一固定度值j时y1关于y2的软信息迭代译码曲线。
综上分析,以最大化码率为目标,保证译码的有效性,提出两个中继节点的AR码度分布联合优化方法如下:
(20)
由于式(20)不满足凸优化的要求而无法直接求解,我们提出以下三种优化策略。
策略一:
假设两个中继节点具有相同的度函数,则边函数和绝大部分信息节点度值也相同,即:
(21)
将式(20)转换为一个凸优化问题,我们可以使用Matlab的凸优化工具CVX进行求解。
策略二:
先只考虑一个中继节点,使用文献[10]中单个度分布优化方法求出该情况下的最优度分布,然后在R1度分布求出的情况下,对R2度分布进行联合优化求解,同样可以转换为一个凸优化问题。
策略三:
策略二中默认R1较R2传输信道信噪比低,将其中继优化顺序进行交换,其他参数设置均不变,使用同样的方法联合求解度分布。
3.5 理论分析
与相关文献不同的是,我们使用三维图来进行方案的EXIT理论分析。假设每个校验节点连接信息节点的边数为相同固定值,即:ρ1(j1)=ρ2(j2)=1。为有一个直观印象,假设各噪声方差σ0=2.266,σ1=0.7666,σ2=0.6770,信息节点平均度数d1s=2,d2s=3,校验节点连接边数固定值j1=j2=3,最大迭代次数为150。根据式(11)～(15)同时画出x1,x2与y1,y2的迭代关系曲面,如图7所示。
图7 迭代关系三维图Fig.7 3D diagram of iterative relationship
将图7中曲面交线投影到y1Oy2平面,并画出纵向曲面与y1Oy2平面交线,如图8所示。
图8 曲面交线投影及y1,y2迭代变化图Fig.8 Projection of surface intersecting line and iterative change of y1,y2
图8中曲线1表示图7(a)中纵向曲面与y1Oy2平面交线,曲线2对应图7(b)中交线;曲线3表示图7(a)中两曲面交线在y1Oy2平面投影,曲线4对应图7(b)中投影;红色圆圈表示点(y1,y2)在迭代过程中的变化情况,其收敛区域为所在曲线3与曲线4之间区域。根据前述定义及分析,两曲线对应y1关于y2表达式分别为:
(22)
(23)
由曲线位置关系得到成功译码的条件为:
(24)
将式(24)中固定j值拓展为所有可能j值的概率累加,即得到式(20)中的限制条件。通过以上分析,我们所提方案在所给约束条件下能够成功译码,降低译码错误平层。并且较文献[10]方法拓展为两个节点的联合优化,可获得更好性能。
4 性能仿真
根据WSN的实际情况,设置三组不同的信噪比,对所提三种优化策略分别求得度分布。同时也给出文献[10]中方法所求度分布进行对照,具体表达式如表1、表2和表3所示。
表1 不同方案下SNR0=-5 dB,SNR1=0 dB, SNR2=2 dB时的度分布表达式
表2 不同方案下SNR0=-5 dB,SNR1=1 dB, SNR2=2 dB时的度分布表达式
表3 不同方案下SNR0=-4 dB,SNR1=1 dB, SNR2=2 dB时的度分布表达式
对照LT码方案使用Shokrollahi的经典度分布如下:
Ω(x)=0.008x+0.494x2+0.166x3+0.073x4+ 0.083x5+0.056x8+0.037x9+0.056x19+ 0.025x65+0.003x66
(25)
我们对以上度分布方案进行蒙特卡洛仿真,采用BPSK调制方式,传输信道为AWGN信道,原始信息码长为10000,循环次数为1000,最大译码迭代次数为150。结果如图9所示。
从图9(a)中可以看到,LT方案在较低码率倒数时(1/R<3.1)误码率比AR方案低,但随着码率的减小其误码率缓慢降低而趋于同一层级;四种AR方案在仿真中并没有出现明显的错误平层,由于AR码在编码结构上较LT码级联了一个累加器,使得相邻的编码节点之间通过校验节点直接产生联系,错误的编码节点信息在译码迭代时能够被及时纠正,这也与式(17)的平均误码率分析结果相对应;文献[10]度分布方案比联合方案二在较高码率倒数时(1/R>3.3)的误码率相差近一个数量级,这说明联合度分布优化是有效的;联合方案一与方案三近乎重合,且明显优于方案二,分析原因为信道条件较好节点对成功译码的影响更大,对其优先进行度分布优化能够提高译码性能;在联合相同度的优化时,同时考虑了两个中继到目的节点的信道条件,整体上进行优化对性能也有一定提升。
图9 误码率性能仿真图Fig.9 Simulation performance of bit error rate
图9(b)和图9(c)中LT方案的变化并不明显,但是AR方案的误码曲线性能明显提升,因为信噪比增大使得数据在传输过程中产生错误的概率减小。方案一和方案三也拉开差距,这说明对不同信道条件的中继设置不同度分布更接近最优策略。图9综合显示我们所提方案三译码性能最优,较已有文献AR度分布方案在误码率达10-5数量级上,分别至少减小7.14%、8.75%和6.25%的码率倒数。本文所提方案是在已有文献方案基础上,充分考虑不同节点信道参数的相异性进行联合度分布优化所得结果,EXIT图分析中已经在迭代译码时考虑了两个节点的协同配合,使得所提方案的译码效率获得极大提升。
5 结论
本文探讨了协同网络中通信方案设计及度分布优化问题,针对“1-n-1”模型提出了AR码方案,利用其无码率特性有效解决了网络通信中信道变化带来的适应性问题;通过编码结构以及EXIT图分析,进行度分布联合优化设计,并对优化条件进行理论推导和验证。提出了三种优化策略,使用凸优化工具分别进行求解。仿真分析表明,我们所提的AR方案最优策略降低了LT方案的错误平层,在译码性能上较现有文献[10]度分布方案更优。下一步将考虑所有中继节点等效看成同一度分布进行整体分析研究,以减小复杂度和提高传输效率。
