不完美反馈下基于立即可解网络编码的多播重传机制

王 练, 朱朝辉, 吴海莲, 殷 豪

(重庆邮电大学计算机科学与技术学院, 重庆 400065)

0 引 言

无线网络数据传输过程存在反馈信息因干扰丢失的情况,反馈信息丢失将导致发送方无法对接收端的接收状态全面了解,导致对后续重传包的选择带来不确定性。网络编码(network coding,NC)由Ahlswede等人在2000年首次提出[1],网络编码允许网络中间节点按一定的规则对数据包进行编码后转发,该“编码-转发”模式有别于传统的“存储-转发”模式,中间结点的编码能力能有效提升传输链路带宽的利用率[2]。Katti等人提出机会式NC(opportunistic NC, ONC),其编解码运算采用异或(eXclusive OR,XOR)操作,XOR运算简单,能有效降低编解码计算复杂度[3]。立即可解NC(instantly decodable NC, IDNC)是ONC的子类[4],所生成的编码包须满足编解码条件,避免不可解编码包的产生,能有效降低完成时延[5-6]。

不完美反馈下,Valaee等人研究反馈丢失对基于IDNC广播方案完成时延的影响,并在反馈丢失和完成时延降低的情况下设计了3种即时可解码网络编码图更新算法[7]。Gao等人在单跳网络中解码延迟约束和不完美反馈情况下提出上三角网络编码方案,该方案能有效提高吞吐量[8]。Douik等人研究不完美反馈下持续删除信道上广义IDNC(generalized IDNC, G-IDNC)组播译码时延问题,并将该问题转换为G-IDNC图中求最大权团问题,在此基础上提出次优贪婪算法,以减小译码时延[9]。Sorour等人根据极大似然状态,在不完美反馈下根据接收端的接收状态推导出最小译码时延和完成时延的表达式[10]。Douik 等人在不完美反馈下提出有损G-IDNC图(lossy G-IDNC graph,LG-IDNC),使用基于LG-IDNC的权重值公式有效降低译码时延[11]。周志恒等人基于部分可观察马尔可夫链决策过程(partially observable Markov decision processes,POMDP)建立不完美反馈下系统模型,提出一种包含缓存反馈机制和一步前瞻的在线规划算法[12]。任志豪等人提出多中继协作网络中不完美反馈下的重传方案,通过缓存不可解数据包并优先发送丢失最多的数据包,以降低解码时延[13]。朱小燕等人根据IDNC和随机线性NC(random linear NC, RLNC)的不同特点提出基于子代划分的NC,并证明IDNC和RLNC只是该模型的两个特例[14]。Ahmad 等人将混合自动重传请求(hybrid automatic repeat request, HARQ)拓展到不完美反馈的场景,并给出在不完美反馈下系统吞吐量的精确表达[15]。

本文以最小化完成时延为目标,针对不完美反馈下无线组播网络中时延最小化问题,在现有研究基础上提出一种不完美反馈下基于IDNC的时延最小化重传方案(retransmission scheme to minimize delay under imperfect feedback,MDIF)。在重传阶段,发送端根据各接收端接收状态、丢包率以及时延等条件,利用POMDP理论建立系统模型,计算不完美反馈下接收端的置信状态。本文采用基于置信点的更新方法,通过选取特定的接收端构成优先发送集合,并在此集合上进行更新操作。其次,本文优化了传统最大权团搜索算法,提出的快速生成算法通过将丢失相同数据包的接收端进行整合,在降低计算复杂度的同时,能进一步降低系统时延。

1 系统模型和参数

1.1 系统模型

如图1所示,无线多播网络模型中发送端S将N个数据包发送给M个接收端,每个接收端需接收N个原包或N个原包的子集。定义原包集P={Pi|1≤i≤N},信宿节点集R={Ri|1≤i≤M}。

图1 无线多播网络模型Fig.1 Wireless multicast network model

传输过程分为初始传输阶段和重传恢复两个阶段。在初始传输阶段,发送端S将N个数据包广播给M个接收端,每个接收端需接收所有的数据包,包括未请求的数据包,并向发送端S反馈各包接收的确认信息。令pi为由发送端S到接收端Ri传输链路的丢包率,qi为接收端Ri反馈链路的丢包率。初始传输阶段后,接收端可能存在以下4种数据包集:① 已接收数据包集Hi(接收端Ri已经接收到数据包的集合);② 请求数据包集Wi(接收端Ri请求数据包的集合);③ 丢失数据包集Li(接收端Ri丢失的所有数据包的集合);④ 不确定数据包集Ui(反馈信息丢失的数据包的集合)。

定义 1状态反馈矩阵(state feedback matrix, SFM),发送端用来表示接收端的接收状态,矩阵中各状态反馈信息fij(∀i∈M,j∈N)定义为

(1)

在重传恢复阶段,发送端根据状态反馈矩阵生成编码包,直到所有接收端都接收到其所请求的数据包。编码包有3类:① 非再生包(编码包a*不包含接收端Ri请求集Wi中任何包,即|a*∩Wi|=0);② 立即可解包(编码包a*只包含接收端Ri请求集Wi中的一个包,即|a*∩Wi|=1);③ 非立即可解包(编码包a*包含接收端Ri请求集Wi中两个及以上包,即|a*∩Wi|≥2)。

(2)

定义 3完成时延(completion delay, CD),所有接收端接收到其请求数据包所需的传输次数。定义接收端Ri的完成时延为ci,则系统总的完成时延CD为

(3)

1.2 POMDP模型

为估计不完美反馈下接收端的真实接收状态,本文采用POMDP理论建立系统模型,POMDP由{S,A,Z,T,O,V}等参数构成,具体参数定义如下。

系统状态集S={s1,s2,…}:S中的元素表示目的接收端Ri在接收编码包a后可能的接收状态;

行动集合A={a1,a2,…}:A中的元素表示不同的数据包组合;

观测状态集Z={z1,z2,…}:Z中的元素表示发送端S通过反馈信息获得编码包的接收状态。由于反馈信息存在丢失,发送端S的观测状态不一定是编码包的真实接收状态。由此建立观测状态矩阵(observed state matrix,OSM)。

状态转移概率T(s,a,s′):T表示发送编码包a后,编码包接收状态由s转移到s′的概率：

(4)

观测转移概率O(s′,a,z):发送编码包a并进入接收状态s′后,发送端观测到接收状态为z的概率:

(5)

回报函数V:发送编码包a后,所有目的接收端恢复请求数据包的个数之和:

(6)

式中：f(si,a,Ri)表示接收端Ri收到编码包a后恢复请求编码包的个数。

基于上述POMDP模型,根据丢包率pi、反馈丢失率qi、观测转移概率O、状态转移概率T和置信状态b估计不同时隙置信状态的置信度[16]:

(7)

因此,选择最佳重传编码包a*即是选择具有最大回报函数值的编码包a:

(8)

1.3 IDNC图

IDNC图G(v,ε)用于表示所有可能的原始数据包组合。通过为数据包Pj(j∈Li)和接收端Ri(i∈M)生成图中的顶点vij来构造IDNC图。图中两个顶点vij和vkl能构成最大团需同时满足以下条件:①j=l即接收端Ri和Rk请求相同的数据包;②j∈Hk且l∈Hi,即对应顶点的请求数据包位于另一个顶点的请求集中。

因此,图中两个顶点vij和vkl之间的每条连线表示数据包Pj和Pl可组合成编码包。

根据接收端对不同数据包的请求,可根据顶点将IDNC图分为两类:主图Gp(主图由接收端Ri请求集Wi中的数据包构成);次图Gs(次图由接收端Ri丢失集Li且不在其请求集Wi中的数据包构成)。

3个接收端接收4个数据包的反馈状态及其IDNC图,如图2所示。当建立IDNC图后,分别在主图和次图执行最大权团搜索算法生成最佳重传编码包,重复该过程直到所有的接收端都接收到其所需的数据包。

图2 状态反馈矩阵及其对应的IDNC图Fig.2 SFM and IDNC graph

定义 4持续剩余完成时延(persistent residual completion delay, PRCD),接收端Ri收到所有丢失数据包预期的传输次数,接收端Ri的持续剩余完成时延[7]定义为

(9)

定义 5权重值(weight value, WV),根据持续剩余完成时间和IDNC图中顶点之间的连线关系,赋予顶点权重值,顶点vij的权重值为

(10)

式中:aij,kl为vij和vkl的邻接指数,

(11)

2 不完美反馈下基于立即可解网络编码的重传方案

2.1 置信点更新算法

无线多播网络中,不同接收端对接收丢失数据包的迫切程度可能不一样,尤其是在实时应用中接收端可以容忍一定程度的数据包丢失,而数据包丢失较多的接收端则需要较长的重传时间。在重传阶段,本方案使用POMDP理论建立不完美反馈下系统模型。根据状态反馈矩阵、观测状态和状态转移概率等计算反馈信息丢失情况下接收端可能出现的置信状态。本方案采用基于置信点的更新方法,通过选取请求集大于平均请求集的接收端构成优先发送集合,并在此基础上构建置信状态子集。在后续的每一次重传中通过建立优先发送集合并在置信状态子集上进行置信状态更新操作,以减小完成时延降低重传次数。

算法 1 置信点更新算法输入:状态反馈矩阵SFM,观测状态矩阵OSM;最佳重传编码包a*输出:优先发送集合M',置信状态子集b',估计状态矩阵OEM,更新后的置信状态b步骤 1 初始化:M',OEM=OSM步骤 2 计算平均请求集W=1/M∑Mi=1Wi步骤 3 for i=1∶M步骤 4 if Wi≥Wthen步骤 5 将大于平均请求集的接收端加入:M'=M'∪Ri步骤 6 将接收端对应的置信点状态加入置信点状态子集:b'=b'∪bi步骤 7 end if步骤 8 end for步骤 9 for i=1∶M步骤 10 if发送端S接收到目的接收端Ri的反馈步骤 11 更新估计状态矩阵OEM步骤 12 else if目的接收端是优先发送集合的成员:Ri⊆M'步骤 13 由式(7)计算可能的置信度bi步骤 14 更新估计状态矩阵OEM步骤 15 end if步骤 16 end if步骤 17 end for

2.2 快速生成算法

使用最大权团搜索算法生成最佳重传编码包时,由于只考虑顶点的权重值并未充分考虑最大团生成与IDNC图中顶点和边连线数的关系,本方案创建优先发送集合,并采用置信点更新算法,在此基础上提出快速生成算法,将IDNC图中丢失相同数据包的接收端顶点整合,以减少IDNC图中顶点和边连线数。

算法 2 快速生成算法步骤 1 for ∀vij,vkl∈G(v,ε)步骤 2 if k=i then步骤 3 使用新的顶点替换原来两个顶点:Vmn=Vij步骤 4 新顶点边集为原顶点边集之和:εmn=εij+εkl步骤 5 新顶点的权重值为原顶点权重值之和:ωmn=ωij+ωkl步骤 6 end if步骤 7 end for

发送端根据观测状态矩阵OSM建立IDNC图模型,然后在主图中使用最大权团搜索算法选择权重值最大的顶点加入最大团Kp,并在与该顶点相连的顶点中再次选择权重值最大的顶点加入团Kp,直到找不到与团Kp中任意顶点直接相连的顶点为止,采用同样的算法在次图中找最大团Ks可得到重传编码包K=Kp∪Ks。发送端重传编码包K并更新状态反馈矩阵,直到所有的接收端都接收到其丢失的数据包。

算法 3 最佳重传编码包选择策略输入:估计状态矩阵OEM输出:系统重传编码包K,主图中最佳重传编码包Kp,次图中最佳重传编码包Ks步骤 1 初始化:K=⌀,Kp=⌀,Ks=⌀步骤 2 生成主IDNC图和次IDNC图Gp(v,ε),Gs(v',ε')步骤 3 while(ε≠⌀)步骤 4 找到主图中权重最大顶点对应的丢失数据包:Pmax=argmaxvi,j∈Gp{ωi,j}步骤 5 Kp=Kp∪Pmax步骤 6 end while步骤 7 while(ε'≠⌀)步骤 8 找到次图中权重值最大顶点对应的数据包:Pmax=argmaxvk,l∈Gs{ωk,l}步骤 9 Ks=Ks∪Pmax步骤 10 end while步骤 11 K=Kp∪Ks步骤 12 传输K步骤 13 重复以上步骤直到所有的接收端都接收到其请求包

3 算法复杂度分析

4 仿真实验

仿真实验在不完美反馈下对所提方案MDIF与全顶点消除方案(full vertex elimination,FVE)[7]、无顶点消除方案(no vertex elimination, NVE)[7]和最大似然网络编码(maximum likelihood network coding,MLNC)[10]进行对比分析,并将完美反馈(perfect feedback,PF)下的性能指标作对比。实验网络模型为无线组播网络,仿真实验以平均完成时延和平均解码时延为性能指标,通过多次仿真实验取平均值。

如图3所示,图3(a)和图3(b)分别表示平均完成时延和平均解码时延随数据包个数N变化的对比情况。参数设置为N∈[10,100],M=40,pi∈[0.2,0.3],qi∈[0.1,0.2]。

图3 数据包数变化对性能的影响Fig.3 Influence of packet number variation on performance

仿真结果表明,随着数据包数的增多,重传恢复阶段接收端成功接收丢包所需的重传次数在增加,同时接收端接收到的不可解数据包概率也在增加,导致接收端的总解码时延不断增大。如图3(a)所示,在请求数据包数较少时,MLNC性能优于FVE和NVE并接近于本方案。

随着请求数据包数的不断增加,本方案的优势逐渐显现并优于其他3种方案。由于NVE和FVE需要多次重传编码包才能判断反馈丢失下数据包的真实接收状态,因此其完成时延一直较高。而MLNC则根据最大似然状态确定置信状态,相比于NVE和FVE可降低重传次数。而本方案采用快速生成算法能有效减少完成时延。图3(b)所示,本方案采用置信点更新算法能有效判断在反馈信息丢失情况下数据包的真实状态,具有较低解码时延。MLNC方案仅根据丢包率p和反馈丢失率q判断反馈丢失下数据包的真实接收状态,未充分发挥POMDP的优势,因此对数据包的真实状态有较高的误判率,增加接收不可解数据包的数量,与本方案相比具有较高的解码时延。NVE和FVE多次重传编码包虽然能确定反馈状态,但会增加接收端接收不可解编码包的数量,解码时延也相应增加。

如图4所示,各方案的性能随着接收端个数M变化的性能对比。其中,M∈[10,100],N=30,pi∈[0.2,0.3],qi∈[0.1,0.2]。如图4(a)所示,由于本方案采用基于置信点的更新算法,即通过选取请求集大于平均请求集的接收端构造优先发送子集,并在此子集上执行更新操作,从而降低完成时延。在接收端数量较多时,MLNC、NVE及FVE需要多次重传才能完成整个重传恢复阶段,而FVE先传输反馈状态确定的接收端,而反馈状态不确定的接收端需要等待较长的时间,完成时延高。如图4(b)所示,由于MLNC、NVE与FVE采用相同的编码方案,因此在接收端数量较少时NVE的性能优于FVE并趋近于MLNC。随着接收端数量的增加,本方案因采用快速生成算法,所以其解码时延较低。

5 结 论

本文针对不完美反馈下多播网络模型,提出不完美反馈下基于IDNC的时延最小化重传方案MDIF。本方案在使用POMDP建立系统模型的基础上,创建优先发送集合,推导出置信点更新算法。之后,考虑接收端的接收状态,将丢失相同数据包的接收端整合以快速生成编码包。仿真结果表明,本文所提方案能综合考虑各种因素,有效降低系统的平均解码时延和平均完成时延,为降低无线多播网络时延提供了一种解决思路。