林潇，吴怡，徐哲鑫

（1.福建师范大学医学光电科学与技术教育部重点实验室，福州 350007；2.福建师范大学光子技术重点实验室，福州 350007）

基于概率和网络编码的蜂窝中继选择机制

林潇1，2，吴怡1，2，徐哲鑫1，2

（1.福建师范大学医学光电科学与技术教育部重点实验室，福州 350007；2.福建师范大学光子技术重点实验室，福州 350007）

针对蜂窝中继系统中单一应用网络编码技术无法提升系统性能的问题，提出基于概率与网络编码的蜂窝中继选择机制CRS-PNC。在该机制中，数据的交互基于ARQ模式进行，中继节点对侦听到的待中继的数据报文会结合编码机会和本身的负载情况来计算转发概率，并构造概率转发函数来设计自适应的发送时延，以实现数据报文网络编码后的竞争时延发送。仿真表明，CRS-PNC与经典的几种蜂窝中继机制相比，在系统吞吐量上具有较好的性能。

中继选择；概率；网络编码；竞争时延

0 引言

未来移动通信系统需要支持更高的数据传输速率和更大的覆盖范围。而传统的蜂窝宽带技术无法满足日益增长的数据速率、覆盖范围、新型业务和用户数量等要求。因此，在蜂窝系统中引入中继技术提供协作分集成了比较经济的解决方法，它可以带来扩大小区覆盖范围、提升系统容量、消除信号盲区和降低成本等诸多方面的好处。

网络编码[1]是一种可以替代传统路由算法的编码方法。在网络编码中，中间节点对接收到的多个源节点的信息进行编码、压缩等处理后，再传输给下一个节点或目标节点，使其特别适用于具有广播特性的无线网络，在减少传输时间、节省发射功率和提高系统吞吐量方面具有无可比拟的优势[2]，因此，基于网络编码的无线中继技术，将会给现有的蜂窝系统带来革命性的变化，是移动通信技术的一个新的发展方向。

近年来，蜂窝中继系统的中继选择算法也成为了热点研究问题。文献[3]分析了三种经典的中继选择算法：（1）基于距离的中继选择算法。该算法将小区划分为若干子区域，移动站基于距离和信号功率的关系与子区域的指定中继节点进行通信，其实现起来最简单，是一个相对静态的中继选择算法；（2）基于路径损耗的中继选择算法，移动站可以根据路径损耗的变化选择最佳的中继节点进行转发，优于基于距离的中继选择算法；（3）基于SINR的中继选择算法，不仅考了信号衰减的因素，还考虑了噪声和干扰的影响，在三者中最优。文献[4]提出了一种正交混合空时网络编码的中继选择算法，即根据节点的发送出错率所反映的信道效益情况，来计算节点需要中继的概率，由中继节点对其发送的信号进行中继。文献[5]研究了Nakagami信道中联合网络编码和双向协作中继的中断与平均误码率的性能，基于网络编码提出了一种最小化较差用户误码率的协作中继选择策略，该策略通过增加协作中继数目的方式，来降低误码率对网络编码的影响。

上述的中继选择算法，一般都以不同的物理层参数（信噪比、距离、路径损耗等）来作为最佳中继节点的选择依据，或者由移动站分析信息来进行中继选择，以及在网络编码的中继方案中也只是尽量减少误码对网络编码的影响。而实际情况中，无线中继蜂窝系统的吞吐量除了取决于当前物理层的信道质量外，还与中继节点的当前负载有关，中继节点的负载需要通过流量相关的参数进行反映，例如，发送队列的利用率等。此外，移动站基于反馈信息进行中继选择或多或少会增加系统的流量，给算法带来一定的复杂度。为了解决上述问题，本文提出了基于概率与网络编码的蜂窝中继选择机制CRS-PNC（Cellular Relay Selection based on Probability and Network Coding），它采用ARQ模式保证数据报文的可靠交付以避免误码对网络编码的影响，并综合考虑待中继数据报文的编码机会和中继节点自身的负载情况，由中继节点实现数据报文的竞争时延发送。

1 CRS-PNC的概述及总体流程

CRS-PNC为了减少通信时隙，采用广播的方式对编码后的数据报文进行转发，其整体上分为三大模块：（1）中继节点结合自身的负载情况以及收到的数据报文的编码机会计算出待中继节点针对该数据报文的综合加权的转发概率；（2）为降低数据报文冗余、竞争与冲突，采用转发概率为中继节点计算出待中继数据报文的自适应的发送时延，以确保最少的中继节点数目达到最大消息覆盖范围；（3）为最大程度的确保数据报文的可靠性和健壮性，采用拥有超时重传机制的ARQ模式实现数据报文的准确可达。

中继节点应用CRS-PNC算法的流程如图1所示。中继节点侦听到待中继移动站发送的数据报文时，首先计算出与数据报文的编码机会相关的概率P1和节点负载相关的概率P2，接着采用综合加权的方法计算出中继节点的转发概率P。然后，构造概率转发函数为每个数据报文设计自适应竞争的时延定时器T1，概率越大，发送时延越小，并启动T1进行倒计时。当T1倒计到0时，中继节点若没有收到竞争时延的数据报文的应答，则基于超时重传机制发送该报文，否则停止转发。

图1 中继节点的数据报文的一般转发流程图

2 综合加权的中继节点的转发概率

CRS-PNC算法中影响中继节点转发数据报文的概率的因素两个：数据报文在节点的编码机会和节点本身的负载。网络编码技术的应用提高了一次传输数据的信息量，减少了传输时间，使系统的吞吐率从整体上得到。基于网络编码的中继机制中一般都会选择编码机会多的节点作为转发节点，但忽略了节点本身业务量的闲忙状态。当一个节点的业务量大时，其发送队列中等待转发的数据报文增多，队列占用率高，表明该节点已处于超重负载状态。虽然较高的队列占用率会增加编码机会，但是存在编码机会的先入队的数据报文一直无法被转发的话，反而会大大增加系统的通信时延，造成系统性能的降低，因此，一个数据报文最优的中继节点，应选择存在较多的编码机会且节点本身负载较小的节点。

一个数据报文是否存在编码机会，就是在中继节点的网络层发送队列中查找：目的地址与其源地址相同并且源地址也与其目的地址相同的数据报文，若找到的数据报文越多，则表明存在的编码机会也越多。因此，与编码机会相关的概率P1为：

其中n代表数据报文存在的编码机会的次数，而Qmax代表中继节点用于缓存待转发数据报文的发送队列的极限长度，且n≤Qmax。

作为中继节点既应考虑数据报文的编码机会，又必须考虑影响网络性能的通信因子——节点本身的负载，减少数据报文在MAC层的竞争时延。因此本报告中的算法引入了基于所有业务量（包括MAC层和网络层）的发送缓存的使用情况来评估节点本身的负载大小。发送缓存的占用率越高，其中等待转发的数据就越多，表明节点本身负载越大，在选择数据报文的中继节点时应尽量避免节点负载较大的节点，尤其是需要转发的其他业务量数据达到节点最大负载时，节点队列作出丢包处理，使数据报文无法发送到目标区域。设中继节点的业务量总发送缓存的占用率用P2表示，则P2表达式为：

其中C代表中继节点中已存储的待转发的业务数据的字节数，而Cmax代表节点的业务量总发送缓存的极限长度，即发送缓存所允许的最大字节数。由（4）可知，P2越大，节点本身的负载越大，反之则越小。

综合加权上述2个因素获得中继节点针对某一数据报文的转发概率P为：

其中ω1和ω2为归一化的综合加权因子，0≤ω1≤1，0≤ω2≤1且ω1+ω2=1。编码机会受发送队列中已存储的数据报文的个数约束，待转发的业务量越多，节点的负载越重，为避免高负载的节点做出丢包处理或数据报文一直堆积在发送队列中增加额外的发送时延，节点负载大小将起决定性作用，此时ω2大于ω1；而当节点负载较小时，为时数据报文能够低时延、低冗余度、有效地转发出去，应选择编码机会较多的节点作为中继节点，此时ω2小于ω1。简而言之，中继节点转发概率的综合加权因子受到节点本身负载的制约，CRS-PNC算法中ω1和ω2的值是关于负载P2的函数[6]，ω1和ω2表达式如下：

可证明，当k=1，b=0时，概率P、P1和P2均分布在0~1之间，因此该种设计是合理的，进而中继节点的转发概率P的表达式变为：

3 自适应竞争的时延定时器

中继节点计算出待中继的数据报文的转发概率后不是立即转发数据报文，而是运用转发概率设计自适应竞争的发送时延，节点的转发概率越大，该数据报文的发送时延就越小，该中继节点就越有可能成为该数据报文的转发节点。当其他的中继节点在各自的时延定时器倒计时内收到某节点广播的数据报文，了解到数据报文已经被成功转发，它们将取消定时器倒计时停止转发。

自适应竞争时延方案利用中继节点的转发概率来构造数据报文发送时延，时延T3的表达式为：

式（7）中τ为一跳传输时延，包括信道接入时延和传播时延，其中信道接入时延包括数据报文在发送队列中的等待时延和数据帧在MAC层接入时延，信息在空气中以电磁波的速度进行传输，因此传播时延可忽略不计。

4 系统仿真及结果分析

4.1 仿真场景及参数设定

为了能够实现机制的动态交互过程，CRS-PNC机制采用NS3进行仿真，并把获得的数据用MATLAB画图分析。系统的仿真场景是一个工作在2.6 GHz频段的LTE蜂窝小区，小区中均匀布设6个中继节点，小区半径为1 km，中继节点位于小区半径2/3处。由于NS3的LTE模块没有包含中继节点，仿真中选用6个处在固定位置的LTE节点运行中继算法来执行中继节点的功能，而LTE移动站则绑定UDP Agent在1s内向除自己以外的其他移动站发送1个的数据报文来产生网络流量，以增加网络编码的机会。同时为了增加系统的中继机会，LTE移动站随机均匀地分布在基站半径的0.6 ~1之间。为了分析CRS-PNC机制的性能，仿真中还对比了基于距离的中继选择算法（Shortest Distance based Relay Selection，SD-RS）、基于SINR的中继选择算法（Maximum SINR based Relay Selection，MSINR-RS）的性能，通过多次测量取平均值的方法分析了几种机制的系统吞吐率和传输时延。表1为CRS-PNC机制的具体参数设计。

表1 CRS-PNC机制仿真参数值

4.2 仿真结果分析

系统的吞吐量由仿真周期内基站成功转发的数据报文的数量来计算，基站和中继节点的竞争窗口限制了它们的吞吐率，当收到的数据报文个数达到竞争窗口大小时，后续到达的数据报文将被丢弃。图2给出了随着小区用户数目的增加，系统吞吐量的变化情况。从仿真结果中可以看到，当用户数据较少时（小于20），3种算法的性能差别不大，都能负荷网络的最大流量。但是，随着用户数量的增加，产生的网络流量逐渐超过中继节点的吞吐率时，CRS-PNC具有网络编码并通过竞争发送在中继节点间进行均衡负载的效果就显现出来，而SD-RD表现最差，它使流量逐渐趋向某个中继节点导致丢包影响了系统的整体吞吐量。

图2 用户数目与系统吞吐量的关系图

5 结语

从无线中继蜂窝系统的研究现状出现，以提高固定中继的蜂窝系统的吞吐量为目标，提出了基于概率与网络编码的蜂窝中继选择机制CRS-PNC。该机制针对网络编码技术在不可靠的无线传输中面临的局限性，采用ARQ模式保证数据报文的可靠交付，同时采用接收者机制来降低系统实现的复杂度。系统中的中继节点侦听到待中继的数据报文时，首先进行编码机会的查找，对符合编码条件的数据报文进行网络编码并竞争发送时延后广播扩散，以减少通信时隙。数据报文的发送时延由转发概率计算得到，而转发概率综合考虑了节点的负载情况以及待中继的数据报文的编码机会，以最真实反映中继节点中继效率。最后通过NS3仿真表明，CRS-PNC在系统吞吐率上与经典的机制相比均有一定的优势。

[1]R.Ahlswede，N.Cai，S.-Y.R.Li，R.W.Yeung.Network Information Flow[J].IEEE Transactions on Information Theory，2000，46（4）：1204-1216.

[2]Z.Lin，B.Vucetic.Power and Rate Adaptation for Wireless Network Coding with Opportunistic Scheduling[C].Proceedings of IEEE International Symposium on Information Theory，2008：21-25.

[3]HU H.Performance Analysis of Cellular Networks with Digital Fixed Relays[D].Ottawa:Carleton University，2003.

[4]刘艳，王子荣，朱性伟.一种正交混合空时网络编码的中继通信算法[J].计算机科学，2014，41（11）：192-194.

[5]冀保峰，宋康，王毅，等.联合网络编码和中继选择的协作传输方案及其性能分析[J].通信学报，2015，36（3）：1-11.

[6]徐哲鑫，彭杏云，林潇，吴怡.基于概率及退避等待的车辆安全消息广播机制[J].计算机系统应用，2016，25(8):211-219.

Cellular Relay Selection Based on Probability and Network Coding

LIN Xiao1，2，WU Yi1，2，XU Zhen-xin1，2

（1.Key Laboratory of Medical Optoelectronic Science and Technology of Ministry of Education;Fujian Normal University，Fuzhou 350007；2.Key Laboratory of Photonic Technology,Fujian Normal University，Fuzhou 350007）

In cellar relay system,system performance will not be improved just through network coding.To solve this problem,proposes a cellular relay selection based on probability and network coding(CRS-PNC).The mechanism uses ARQ for transferring data reliably.After relay node catches the data that will be relayed,it will both consider the data load of relay nodes and the coding chance of data to calculate the forward probability of each relay.A function of forward probability is constructed combined with an adaptive back-off mechanism,by which the data is relayed.The simulation results show that the performance of CRS-PNC is superior to several traditional mechanisms in terms of system throughput.

Relay Selection;Probability;Network Coding;Backoff

1007-1423（2017）01-0003-05

10.3969/j.issn.1007-1423.2017.01.001

林潇（1981-），男，福建福州人，助理研究员，硕士研究生，研究方向为无线通信技术

吴怡（1970-），女，辽宁葫芦岛人，教授，博士生导师，研究方向为无线网络通信

徐哲鑫（1985-），男，福建福州人，讲师，博士研究生，研究方向为无线网络通信

2016-12-24

2017-01-04

福建省自然科学基金（No.2013J01224）