基于网络编码的无线多播速率选择机制

蒋友辉 卢汉成 洪佩琳 薛开平

(中国科学技术大学电子工程与信息科学系 合肥 230027)

1 引言

多播业务可以节省宝贵的带宽资源，应用广泛，例如视频会议、传感器网络和军事应用等。但是无线网络中应用多播通信业务面临艰巨挑战，尤其是在数据可靠传输的多播业务中。在可靠多播通信中，源节点需要重传接收节点丢失的数据，由于不同节点丢失的数据可能不同，接收节点可能已经接收到当前重传的数据，这不仅造成了接收节点对数据的冗余接收，而且直接增加了源节点的重传的数据量。另外，每个接收节点与源节点之间的信道状态可能是不同的，源节点以较低速率发送数据虽然可以减少数据丢失，减少数据重传，但是会导致很低的吞吐量和很大的延迟。而以较高速率发送数据则会导致信道状态差的节点丢失数据，源节点需要重传大量数据，无论是以过高速率还是以过低速率发送数据，都将导致较大的系统延迟。

数据可靠传输和延迟在一些如救灾和军事应用的业务中有重要意义。混合自动请求重传(HARQ)[1,2]可以保证数据的可靠传输，但是会带来接收节点重复冗余接收数据等问题，本文结合网络编码(NC)[3-5]提高数据重传效率，源节点每次重传所有数据包经过随机线性组合的编码包，每个编码包包含所有数据信息，当接收节点接收到足够多的线性独立编码包后解码出自己丢失的数据包，这样就能避免接收节点对数据包的重复接收，直接减少源节点的数据发送量。

接收节点信道状态决定了它的数据接收能力，在多播通信中，每个接收节点的信道状态是不同的，信道状态较好的节点可以以较高速率接收数据，信道较差节点只能以较低速率接收数据。在移动环境下，接收节点的信道状态随节点的移动而变化，当前信道最差的节点不再是制约系统性能的主要因素，系统延迟取决于最后一个完成数据接收的节点，传统的基于信道最差节点的速率选择将不能达到很好的系统性能。多播系统延迟不仅和节点当前信道状态有关，还和节点已经接收到的数据量、节点的信道变化以及源节点的速率选择有关，本文无线信道采用有限状态马尔科夫信道(FSMC)模型，根据当前节点的信道状态，以一定概率预测节点信道的变化，并结合节点当前数据状态信息(DSI)，提出了一种基于信道预测多播速率选择算法(MDCP)。仿真结果表明，MDCP速率算法比仅根据节点CSI的基于当前最差信道状态节点(WCSN)的速率选择算法和没有信道预测的基于最大延迟节点的多播速率选择算法有10%-20%的延迟增益。

本文的结构如下。第 2节介绍本文系统模型；第 3节介绍无线有限状态马尔科夫信道(FSMC)模型，并提出根据节点CSI和DSI的基于信道预测的最小化延迟速率选择算法；第 4节对不同速率选择算法做性能仿真；最后是结束语。

2 系统模型

如图1所示，源节点(基站：BS)经过瑞利衰落无线信道发送数据给N个接收节点(移动用户)，每个数据块(文件)包含G个数据包，每个数据包包含Lbit。源节点每次发送一个数据帧，每帧时间周期为Tc。假设节点间的信道状态在Tc内不变，接收节点通过可靠上行链路信道向源节点反馈信道状态信息(CSI)和数据状态信息(DSI)[6]。每个接收节点都可以自由移动，假设在完成当前文件发送之前没有新的接收节点加入系统。

图1 系统模型

本文采用M-QAM[7]调制技术，将待发送的数据按照不同的调制方式调制来改变数据发送速率，码元是承载信息量的基本信号单位，码元在不同调制方式下包含的比特数不同。M-QAM的误码率为

式(2)和式(3)分别表示M阶调制下节点误比特率和丢包率，这里假设没有前向校验纠错(FEC)。在不同调制方式下节点的数据接收如图2所示。

图2 节点在不同数据调制方式下的数据接收

从图2中可以看出，当节点的信道状态确定时，源节点选择调制方式即数据发送速率决定节点的数据接收，本文目标是在多播通信中如何自适应调整发送速率最小化系统延迟。

3 多播速率选择和数据传输

3.1 有限状态马尔科夫信道(FSMC)模型

有限状态马尔科夫信道(FSMC)[9,10]是将信噪比的变化范围划分为有限个状态，ℜ={γ0,γ1,…,γK}为所有状态的集合，γk∈[Γk,Γk+1)(0≤k≤K),-∞＜Γm＜Γn＜∞,0≤m＜n≤K+1。假设信道为慢衰落，信道只在相邻的状态之间转变，如图3所示。

其中St=l表示t时刻信道的状态为l,Pl,n表示信道状态从l变化到n的概率。

在瑞利衰落信道下，节点i接收到数据的瞬时信噪比(SNR)γ的概率密度函数为[11]

图3 有限状态马尔科夫信道状态转移图

其中=E[γi]是平均信噪比，信道处于γk状态的稳态概率如式(6)所示。

信道只在相邻状态之间转变，节点i的信道转移概率为[9-11]

N(·)为交叉函数，是多普勒频移。文献[12]指出若发送数据的符号速率恒定时，Tc也恒定。节点i的信道状态转移矩阵为

其中

3.2 基于信道预测的最小化延迟速率选择算法

利用马尔科夫信道的性质，可以预测节点的信道变化。若节点i当前信道状态为γk，那么经过m次转移处于每个状态的概率向量为

其中

定义1 速率选择策略π(t)：源节点在t时刻选择的数据发送速率。(t)表示根据节点i的信道状态选择最优的速率。Π为所有速率选择的集合。

定义2 节点i延迟：节点i完成数据接收所需要的时间。

节点i在速率选择策略(t)下延迟期望为

其中τ为源节点发送一个数据帧所用时隙大小，σi为节点i完成数据接收所用时隙数的期望值，其满足约束

r(t)为第t个时隙源节点的发送速率，ξi(t,r)表示节点i在t时隙发送速率为r(t)时的丢包率，式(13)左边表示节点在σi个时隙内接收到的数据量，式(13)右边Ω为节点需要接收的数据量，采用网络编码技术避免节点的数据重复接收，故满足上述约束后，节点即可解码出所有数据。

当Ω充分大时，节点接收数据所需时间充分长，节点处于每个信道状态的概率趋于稳态，节点i的信道状态的稳态概率向量为表示节点i信道处于k状态的稳态概率，如式(6)。节点i一个时隙内接收到的数据量的期望值为

即节点在σi时隙内接收到的数据量要不少于Ω。

当节点信道状态不变时，设节点m的信道状态最差，那么节点m期望延迟即为系统期望延迟，源节点的速率选择策略为。但是当节点的信道状态变化时，当前信道最差节点延迟不一定最大，此时基于信道状态最差节点的速率选择会增大系统延迟。节点延迟由节点已经接收到的数据量和当前信道状态以及当前的速率选择决定。在有限状态马尔科夫信道下，根据节点当前的信道状态，以一定概率预测信道状态的变化，结合节点DSI预测节点在最优速率选择下的延迟。节点当前处于k信道状态，在下一个时隙接收到的数据量的期望值为τ(R*为节点i的信道状态转移矩阵，如式(11)。对于速率选择策略π(t)，当前速率选择为rπ(t)，那么当前时隙节点接收到的数据期望值为

其中ξ(k,rπ,t)是t时隙信道处于k状态速率为rπ时节点的丢包率，那么节点i在速率选择策略π(t)下的延迟期望是

其中θ(t)表示t时隙节点接收数据的已用时间，接收到的数据量为Ω'(t)，并且在σi个时隙内完成数据的接收。节点延迟包括两部分，其中θ(t)是已经完成的部分是确切知道的，σi是根据节点信道和数据接收量预测部分，是我们做出速率选择的重要参考依据。σi满足约束

结合式(14)-式(17)可以看出节点当前CSI和DSI已知时速率选择决定系统延迟。本文研究目标是选择合适的速率最小化系统延迟，即

为优化系统延迟，每次选择的速率使系统延迟，即延迟最大节点的延迟最小。根据式(17)可知系统延迟的大小主要取决于σ，所以目标优化可以转化为

表1 基于信道预测的最小化延迟速率选择算法

根据式(16)可知σi取决于节点当前CSI和DSI以及速率选择策略，本文根据节点CSI和DSI提出了一种基于信道预测多播速率选择算法(MDCP)，见表1。其中MAX为一个大于系统延迟的实数。源节点首先收集接收节点的CSI和DSI，并根据节点当点的信道状态利用FSMC特点根据式(11)预测节点信道的变化，然后根据节点DSI和式(15)计算节点延迟并根据公式(16)-式(18)预测系统延迟，最后选出使系统延迟最小的速率。算法的主要开销在于预测节点信道的变化，要将节点的信道状态向量与状态转移矩阵相乘，其复杂度为O(K2),K为节点的信道状态数(本文中K=10)，复杂度为O(mNnK2)，其中m为可选速率集合的元素个数(本文中m=6),N是节点的个数，表示节点完成数据接收所需时隙个数的期望值，如式(14)，在无线环境下源节点的覆盖范围有限，同一个源节点下的接收节点的数不会太大，又因为m和K是定值且很小，所以该算法是切实可行的。

源节点根据收集到的节点CSI和DSI计算系统延迟，并调整速率。本文数据发送分为两个阶段，数据发送阶段和数据重传阶段，如表2所示。首先在数据发送阶段，因为所有接收节点都没有接收到当前发送的数据，源节点发送数据的原始数据包，当源节点发送完当前文件数据，如果节点接收到当前文件的所有数据，则向源节点发送确认(ACK)，如果所有节点都完成数据接收，那么源节点开始发送下一个文件，否则进入数据重传阶段。在数据重传阶段，不同节点可能丢失不同的数据包，为了提高重传效率，源节点发送当前文件的编码包，即发送编码包，其中G表示文件中编码包的个数，iP是第i个数据包，ai是数据包iP的系数，cP是编码包。如果接收节点接收到足够多线性独立的编码包，则根据式(22)解码出自己丢失的数据，并向源节点发送确认(ACK)，当源节点收到所有接收节点的ACK则发送下一个文件。

表2 利用网络编码重传的可靠组播传输

4 仿真实验

这节对本文提出的算法做性能仿真。用户均匀分布于以源节点为中心半径为100 m的区域内，接收节点数为N，节点的平均信噪比均匀分布于[10,20]dB，信道初始状态随机分布于[5,25]dB，每个信道状态的信噪比区间大小为2 dB，即Γk+1-Γk=2 。节点可以自由移动，并且在当前文件完成发送之前没有节点移出多播系统，多普勒频移fd=10 Hz。每个文件包含100个数据包，每个数据包大小为 1000 bit。源节点发送每个帧的所用的时隙大小为1 ms，在同一个时隙内节点的信道状态不变。源节点发送数据的符号速率恒定为1 Msymbol/s，不同的调制方式决定不同的数据速率，当源节点选择高阶调制方式时发送速率高，选择低阶调制方式时其发送速率低。每个帧可以包含不同数目的数据包。节点周期性每隔 1 ms通过可靠上行链路信道向源节点反馈CSI和DSI信息。

网络编码技术可以有效减少接收节点数据冗余接收，减少源节点的重传数据量，进而降低系统延迟。图4显示了源节点发送100个数据包，分别采用网络编码重传和不采用网络编码重传时的系统延迟。从图中可以看出，采用网络编码重传具有很好的性能增益，而且当用户增加时系统的延迟也相对稳定。因为当接收节点数目增加时，其丢失不同的数据包的个数也在增加，若不采用网络编码重传数据，源节点重传的数据量也随之增加，所以不采用网络编码重传数据系统延时会随接收节点数目增加而快速增加。

然后基于网络编码重传数据，本文对比了3种速率选择算法的延迟性能。

WCSN：基于最差信道状态节点的速率选择算法。该算法根据所有接收节点中信道状态最差的节点选择速率，以保证每个接收节点都较少的丢失数据。

MDN：基于最大延迟节点的速率选择算法。该算法根据节点当前的CSI和DSI，计算节点的延迟，t时隙节点i的延迟为是t时刻节点i丢失的数据量，ri(t)是对应节点i,t时刻信道状态的最优速率。该算法没有信道预测，源节点根据延迟最大的节点选择速率，即当前延迟最大的节点尽可能多地传送数据以减小系统延迟。

图4 网络编码性能增益

MDCP：基于信道预测的最小化延迟的速率选择算法。该算法利用FSMC信道性质，预测节点信道的变化，并根据当前的速率选择计算平均系统延迟，选择速率使系统延迟最小。

图5显示了源节点发送100个文件3种速率选择算法下的延迟性能，从图中可以看出MDCP算法下的延迟比WCSN和MDN算法降低10%-20%。随着节点数目的增加系统延迟增大，当节点增大到一定数目时系统延迟趋于稳定。

MDCP算法增益主要来源于接收节点信道的变化。一方面，如果节点信道从较好状态转移到较差状态，虽然节点当前的信道状态较差，但是由于之前较好的信道状态可能已经接收到较多的数据，节点只需要再接收少量数据就可以完成当前文件接收，此时节点可以承受较高的速率，若根据WCSN根据信道最差的节点选择速率则会浪费带宽增大延迟。另一方面节点虽然当前处于信道状态较差的位置，但是如果能够变化到较好的状态，该节点同样可以承受较高的速率，MDN算法只是根据节点当前的CSI和DSI选择速率，若节点信道状态变好那么MDN算法也会浪费带宽。图6显示了当有N=10个接收节点时，源节点在发送一个文件时间内不同算法下的速率选择。图6(a),6(b)和 6(c)分别表示在MDCP和WCSN两种速率选择算法下的源节点每个帧选择的速率。通过对比可以看出，MDCP算法选择的平均速率要高于WCSN和MDN算法，MDN算法选择的速率略高于WCSN算法，源节点发送完一个文件，MDCP算法所用时间为 60 ms，而用MDN和WCSN算法选择速率则分别需要65 ms和70 ms。

图5 速率选择算法的延迟性能比较

图6 不同速率选择算法下的速率选择

5 结束语

本文主要研究无线多播的速率选择问题，并结合网络编码技术完成多播数据的可靠传输。利用FSCM信道特性根据接收节点当前CSI预测节点信道变化，结合节点DSI提出了MDCP速率选择算法，与传统WCSN速率选择算法和没有信道预测的MDN速率选择算法相比延迟降低10%-20%。本文考虑只有一个源节点时的速率选择，下一步我们将研究有多个源节点时的速率选择及源节点之间的协作。

[1]Papadopoulos G D,Koltsidas G,and Pavlidou F N.Two hybrid ARQ algorithms for reliable multicast communications in UMTS networks[J].IEEE Communications Letters,2006,10(4)：260-262.

[2]Ramis J and Femenias G.Cross-layer design of adaptive multirate wireless networks using truncated HARQ[J].IEEE Transactions on Vehicular Technology,2011,60(3)：944-954.

[3]Ahlswede R,Cai N,Li S Y R,et al..Network information flow[J].IEEE Transactions on Information Theory,2000,46(4)：1204-1216.

[4]Kumar R,Tati S,Mello F D,et al..Network coding aware rate selection in multi-rate IEEE 802.11[C].2010 18th IEEE International Conference on Network Protocols (ICNP),Kyoto,Japan,Oct.5-8,2010：92-102.

[5]Kim T S,Vural S,Broustis I,et al..A Framework for joint network coding and transmission rate control in wireless networks[C].INFOCOM,2010 Proceedings IEEE,San Diedo,USA,March 15-19,2010：1-9,14-19.

[6]张一衡,崔琪楣,陶小峰.多用户MIMO-OFDM系统低速率CSI反馈方法及信道容量分析[J].电子与信息学报,2009,31(9)：2188-2192.Zhang Yi-heng,Cui Qi-mei and Tao Xiao-feng.Low rate CSI feedback and capacity analysis in multiuser-MIMO-OFDM system[J].Journal of Electronics＆Information Technology,2009,31(9)：2188-2192.

[7]Goldsmith A.Wireless Communications[M].Kamblidge：Cambridge University Press,2005：159-168.

[8]Bernard S著,徐平平,宋铁成 译.数字通信——基础与应用[M](第 2 版).北京：电子工业出版社,2002：180-181.

[9]Zhang Q and Kassam S A.Finite-state Markov model for Rayleigh fading channels[J],IEEE Transactions on Communications,1999,47(11)：1688-1692.

[10]Wang H S and Moayeri N.Finite-state Markov channea useful model for radio communication channels[J].IEEE Transactions onVehicular Technology,1995,44(1)：163-171.

[11]Razavilar J,Liu K J R,and Marcus S I.Jointly optimized bit-rate/delay control policy for wireless packet networks with fading channels[J].IEEE Transactions on Communications,2002,50(3)：484-494.

[12]Doufexi A,Armour S,Butler M,et al..A comparison of the HIPERLAN/2 and IEEE 802.11a wireless LAN standards[J].IEEE Communications,Magazine,2002,40(5)：172-180.