认知无线电自组织网络^[1](CRAN)是采用认知无线电技术^[2]的无线多跳网络，能自动发现并在不影响授权用户的情况下利用空闲频谱，解决频谱资源紧张和利用率低问题.高效的信息多播及广播技术是CRAN的基础技术.

CRAN具有多信道特性、不同节点可用信道集合的差异性及各信道报文传输质量的变化性^[2].网络编码(network coding, NC)^[3]的出现则为此问题的研究提供了新思路和途径. NC融合编码和路由的概念，可更好地利用无线网络的通信广播性、数据冗余性、空间分布性等，显著提高无线网络的吞吐量、可靠性、负载均衡性等.随机网络编码(RNC)^[4]中编码系数在伽罗瓦域^[5]GF(2^q)中随机选定，从而使NC技术能应用于分布式应用中.

面向普通无线网络的NC技术，研究了NC应用于无线自组网组播技术^[6-7]，考虑时变的、链路容量受噪声干扰影响的无线网络模型^[7].在时变无线网络模型的基础上，使用动态的压力反馈算法来分别优化NC和路由^[8].用NC思想研究无线报文重传问题^{[9-12, 15]}等.

而关于在CRAN中应用NC技术的文献不多，如张波等^[14]通过分析NC技术的特点，得出应用NC技术可降低CRAN中授权用户和非授权用户的无线信道访问冲突概率；高振国等^[16]利用NC技术解决CRAN中的出错报文重传问题，可看作是链路层自动请求重传协议的改进和补充.

本文研究的CRAN报文多播或广播传输技术基于如下假设：首先，CRAN中所有节点都支持一个公共的无线控制信道(传输通信控制报文)及多个数据信道；其次，数据源节点通过公共控制信道上的信息交互，已经利用传统多播路由发现算法建立以源节点为根，以多播接收节点为叶的多播树，所有数据报文将沿多播树多播到各接收节点；第三，控制报文通过公共无线控制信道传输，而数据报文通过各数据信道传输.据此提出一种基于RNC的算法，该算法成批进行报文多播传输任务，且每批次中报文数量可变.该算法的核心是对多信道单跳无线报文多播问题MCSHWMP的求解.

1 多信道单跳无线广播问题

MCSHWMP的基本场景如下：在CRAN中，1个发送节点有一批报文要广播给多个接收节点，且这些接收节点都在发送节点的无线传输覆盖范围内.则MCSHWMP问题的目标是，考虑不同节点可用信道集合的差异性及各信道报文传输质量的变化性，在使各节点都能接收到各报文的前提下，寻求最优报文传输策略以尽量节省报文传输数量.

定义1  多信道单跳无线多播问题MCSHWMP.具有多个工作信道是CRAN等多信道通信网络相对于传统无线网络的一个显著特征，故把CRAN中的1跳无线广播称为多信道单跳无线多播问题.

一个MCSHWMP问题可用四元组描述为

$ {\rm{MCSHWMP}} = \left\{ {\boldsymbol{P}, {\rm{ }}\boldsymbol{R}, {\rm{ }}\boldsymbol{C}, {\rm{ }}\boldsymbol{B}} \right\}, $

式中：P={p_i|∀i∈{1, …, |P|}}为该问题中发送节点要传输给各接收节点的报文集合；R={r_i|∀i∈{1, 2, …, |R|}}为接收节点集合；C={c_i|∀i∈{1, …, |C|}}为可用信道集合；B= {b_{i, j}}_|R|×|C|为无线信道的报文传输成功概率矩阵，其基本元素b_{i, j}为发送节点与接收节点r_i之间的信道c_j的报文传输成功概率，对于某些不可用信道，b_{i, j}=0.

定义2  MCSHWMP问题的有效方案.如果MCSHWMP问题的一个报文传输方案能保证各接收节点能正确解码得到P中各报文，则称这样的方案为MCSHWMP问题的有效方案.

定义3  MCSHWMP问题的最优NC方案. MCSHWMP问题的主要目标是尽量减小传输的无线报文数量，故本文把报文传输数量最少的NC方案称为MCSHWMP问题的最优NC方案.

本文中不限制NC所使用的伽罗瓦域GF(2^q)，即不限定q的值.为简化，记n_R=|R|，n_C=|C|，n_P=|P|.

2 MCSHWMP问题的数据报文多播传输算法

基于NC的报文多播传输是成批进行报文多播传输任务的，且每批的报文数量是可变的.在进行多播数据传输前，数据源节点在公共控制信道上通过传统的多播路由发现算法建立以源节点为根、以多播接收节点为叶的多播树，然后源节点即开始向多播树广播报文，树内节点收到报文后，按本文所提方法进行处理并向下游节点转发，直到树叶节点收到该批次的所有报文.多播树内节点根据局部信息自主决定何时开始下一批次报文的传输任务.

2.1 组合报文结构

基于NC的报文多播传输中，除编码报文外，接收节点需要一些辅助信息才能进行解码.辅助信息一般与编码报文及其它信息封装在一个组合报文中，真正传输的是组合报文.算法中组合报文包括7个字段：ID_Src, ID_Batch, ID_Sender, PktNum_inBatch, List_Rcv, Info, Pkt.

字段ID_Src为多播源节点编号(记为I_S)；ID_Batch标识当前正在处理的报文批号(记为I_B)；ID_Sender指示报文的发送者(记为I_X)；PktNum_InBatch指示该批中报文数量(记为N_P)；List_Rcv指示发送节点的下游接收节点集合(记为L_R)；Pkt中保存一个编码报文，生成该编码报文时所使用的编码向量实际是由一个公共随机函数利用一个随机数作为种子生成的随机数序列，该序列长度为N_P.编码系数均看作是伽罗华域GF(2^q)上的元素，Info用于保存相应的随机数种子.

2.2 数据报文传输算法

基于RNC的CRAN报文多播传输算法分为报文发送算法和报文接收算法.每个节点均有发送算法和接收算法的无限循环工作线程，分别进行数据报文发送和接收任务.各节点的报文发送算法和接收算法协作完成报文多播传输任务.下面给出算法基本框架，调整部分步骤即可得到不同算法.

数据报文发送过程中包括2个阶段：初始集中报文发送和后续离散报文发送.仅有初始集中报文传输并不能保证所有节点都能收到足够信息来解码得到当前多播报文批次的所有报文，后续离散报文发送是为完成报文传输任务所必需的，每次只传输一个组合报文，传输该组合报文所用的信道按某后续离散报文信道选择策略确定.数据报文发送算法流程具体描述如下

1) 数据报文发送算法框架流程:

步骤1  若本节点有已经接收完成的、要向下游节点传输的新批次数据报文，且本节点有下游节点，则转到步骤2；否则继续等待.

步骤2  发送节点根据某种初始报文分配向量确定策略生成初始报文分配向量V_Init= {x₁, x₂, …, x_|C|}，该向量元素x_j表示发送节点在初始集中报文发送阶段需要在信道c_j上传输x_j个组合报文.

步骤3  根据初始报文分配向量依次在信道c_j上传输x_j个组合报文.

for (j=1, j < =n_C, j++)

若x_j=0，则继续下一循环；

若x_j>0，则做如下工作：

通过公共控制信息交换信道通知各接收节点r∈{r_i|b_{i, j}>0}把接收信道转移到信道c_j；

构造x_j个编码报文p_{Y, i}=m_i·P_X (i={1, 2, …, x_j})，其中编码系数向量m_i由随机数种子s_i生成；

构造组合报文P_{z, i}={I_S, I_B，I_X, N_P, L_R, s_i, P_{Z, i}}，其中L_R=R_R；

通过信道c_j广播所有x_j个组合报文p_{z, i}.

步骤4  启动定时器T_W，该定时器在时间t_W=|R_R|·T_R后结束(T_R为参数，其值大于接收一个回复报文所需的时间).在这段时间内等待接收各接收节点的回复报文.

步骤5  若接收到某节点r_i的对当前批次数据报文的回复报文，则表明该节点已经正确获得了自己所需所有报文.

步骤6  定时器T_W结束.若R_R=∅(空集)，则转到步骤1.

步骤7  构造1个编码报文p_Y=m·P_X(i={1, 2, …, x_j})，其中编码系数向量m由随机数种子s_i生成；其中P_X={p₁, p₂, …, p_n}.

步骤8  构造1个组合报文p_Z={I_S, I_B，I_X, N_P, L_R, s_i, p_Y}，并从信道$\mathop {\arg \; \max }\limits_{{c_j} \in C} (\sum\limits_{{r_i} \in {R_R}} {{b_{i, j}}})$上广播出去.组合报文传输完成后转到步骤4.

2) 数据报文接收算法框架流程:

步骤1  若收到属于新批次的数据报文，则转到步骤2；否则继续等候新批次报文.

步骤2  初始化新报文批次的解码矩阵M_D为空矩阵，初始化新报文批次的编码报文列向量P_Y为空向量.

步骤3  设收到的数据报文为p.用p中Info作为随机数种子，利用与生成编码矩阵时的相同方法恢复所用的编码向量并记作v；取出组合报文p中的报文Pkt并记作p_R，即p_R=Pkt.

步骤4  据式(1)把行向量v附加到解码矩阵M_D作为其尾行.

$ {\boldsymbol{M}_{\rm{D}}} = \left[\begin{array}{l} {\boldsymbol{M}_{\rm{D}}}\\ \boldsymbol{v} \end{array} \right]. $

(1)

步骤5  令p_R=Pkt根据式(2)把它添加到P_Y的尾部.

$ {\boldsymbol{P}_{\rm{Y}}} = \left[\begin{array}{l} {\boldsymbol{P}_{\rm{Y}}}\\ {p_{\rm{R}}} \end{array} \right]. $

(2)

步骤6  在域GF(2^q)上计算解码矩阵M_D的秩rank(M_D).

步骤7  若rank(M_D) < n，则等待接收到新的组合报文，转到步骤3.

步骤8  若rank(M_D)=n，则对式(3)利用高斯约旦消元法进行解码获得自己所需所有报文.

$ {\boldsymbol{M}_{\rm{D}}} \cdot {\boldsymbol{P}_{\rm{X}}}{\rm{ = }}{\boldsymbol{P}_{\rm{Y}}}. $

(3)

步骤9  若当前节点ID在报文的List_Rcv字段中，则向发送节点发送ACK回复报文以告知发送节点自己已经获得当前批次所有报文.

步骤10  转到步骤1.

2.3 初始集中报文发送向量确定策略

初始集中报文发送阶段需要根据初始报文分配向量发送组合报文.该分配向量对算法的时间延迟具有决定性影响，对报文传输数量也有较大影响.若报文分配向量中所确定的报文发送数量过多，虽然可降低1跳报文多播任务的完成时间，但有可能初始阶段发送的报文信息已经满足甚至超过了各节点的需要，导致较多的报文传输，增加了能量消耗；若初始阶段发送的报文信息过少，则可能需要在后续离散报文发送阶段传输较多的报文，增加了1跳报文多播任务的完成时间，而同时报文传输数总量也没有明显减少.

提出三种策略，分别标记为：RAND1，LINK100，LINKRATIO.显然，它们的初始阶段发送报文数量依次增多.

1) RAND1策略.该策略中初始报文分配向量随机确定，但须满足$\sum\limits_{j = 1}^{{n_{\rm{C}}}} {{x_j} = 1} $，即在随机选定的一个信道上发送一个组合报文.

2) LINKRATIO策略.求解MCSHWMP问题在期望状态下的最优NC方案，即在期望状态下使各节点都能获得足够信息解码得到各原始报文的前提下，传输报文数量最少的方案，并把该方案的解作为初始报文分配向量.分析得知，该策略中初始报文分配向量为式(4)所示的整数线性规划问题的解向量.

$ \begin{array}{l} \min \sum {{x_j}, } \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\sum\limits_{j = 1}^{{n_{\rm{C}}}} {({x_j} \cdot {b_{i, j}} \ge {n_{\rm{p}}}, } \;\;\;\forall i \in \{ i, 1, 2, \cdots, {n_{\rm{R}}}\} ;\\ \;\;\;\;\;\;{x_j} \in \{ 0, 1, 2, \cdots \}, \forall i \in \{ i, 1, 2, \cdots, {n_{\rm{C}}}\} . \end{array} $

(4)

式中整数规划变量为x_j，其表示发送节点需要在信道c_j发送x_j个编码报文.式中各个限制条件的意义为：第1个约束条件保证接收节点r_i从各个信道上正确接收到的编码报文数量期望值之和要≥其需要报文数量n_p=|P|；第2个约束限定x_j只能取非负整数.

3) LINK100策略.求解MCSHWMP问题在各可用链路(即满足b_{i, j}>0的链路)的报文传输成功率为100%情况下，在各节点都能获得足够信息解码得到各原始报文的前提下，寻找传输报文数量最少的最优网络编码方案，并把该方案的解作为初始报文分配向量.分析得知，该策略中初始报文分配向量为式(4)所示的整数线性规划问题的解向量，故只需将式(4)中的b_{i, j}用取整函数ceil(x)对b_{i, j}向上取整即可.

该策略获得的初始报文分配向量相当于理想状态下传输报文数量最少的方案.

3 仿真测试 3.1 待测试的算法

在Matlab中通过仿真测试MCSHWMP数据报文多播传输算法的性能.比较3种初始集中报文发送向量确定策略RAND1、LINK100和LINKRATIO(分别简记为R1、L100、LR)的性能特点.

另外，为了评价基于NC的算法相对于传统非NC算法的性能，对于一个MCSHWMP问题，期望状态下传统非NC算法最少报文传输方案可转化为整数线性规划问题，该规划问题的解可直接转化为MCSHWMP问题的非NC方案.把该算法记作NN，并把它作为评价各算法性能基准.

综上，仿真测试的算法包括4个：R1、L100、LR和NN.这些算法中需要求解一些整数线性规划问题，对之求解都采用了文献[12]所提出的渐进整定求解算法.

3.2 性能指标

1) 报文传输总数量.该指标为MCSHWMP问题中发送节点为传输完一批报文所需发送的组合报文总数量，包括初始集中报文传输阶段及后续离散报文传输阶段所发送的报文.它反映算法在节省报文数量方面性能.

2) 离散报文传输数量.该指标为MCSHWMP问题中发送节点在后续离散报文传输阶段所发送的报文.该指标可以部分表征算法的时间延迟.

3) 相对报文传输总数量.相对报文传输总数量代表不同算法中报文传输总数量之间的比值.例如，L100/NN表示L100法的报文传输总数量与NN法的报文传输数量的比值.

4) 相对离散报文传输数量.相对离散报文传输数量代表不同算法中离散报文传输数量之间的比值.例如，L100/NN表示L100法的离散报文传输数量与NN法的报文传输数量的比值.

5) 信道切换次数.信道切换会增加能耗、延迟等额外的开销.在某解决方案中，若节点需要在n个不同信道工作，则记信道切换n次.一个MCSHWMP问题的发送节点及其所有接收节点的平均信道切换次数作为方案的信道切换次数指标.

3.3 仿真配置

仿真MCSHWMP{P, R, C, B }问题时的仿真参数包括：报文数量|P|、接收节点数量|R|、信道数量|C|、信道分散度c_L，信道报文传输成功率基值L_sb.一个组合{|P|, |R|, |C|, c_L, L_sb}称为一个仿真配置.

针对一种仿真配置，重复生成100个问题实例.针对每个问题实例，依次使用各测试算法进行处理，记录相应指标.把100个实例的仿真结果平均值作为最终结果，并计算平均值的95%置信度区间.

每个问题实例由一个大小为|R|×|C|的信道报文传输成功率矩阵M_B表示. M_B的元素a_{i, j}如下确定：取(0, 1)区间内平均分布的随机数x=rand()，若x < c_L，则a_{i, j}=L_sb+(1-L_sb) rand()，表示发送节点和接收节点r_i间的信道c_j的报文传输成功率为a_{i, j}，否则若x≥c_L，则a_{i, j}=0. c_L只是用于在仿真中控制各节点可用信道的分布情况，其值越大节点可用信道越多.

3.4 仿真结果

通过大量仿真测试报文多播传输算法的性能.固定|P|=5、|R|=5、c_L=0.5、编码位数q=8，当|C|∈^{[2, 10]}且信道报文传输成功率基值L_sb∈[0.1, 1]时各算法性能指标的变化情况见图 1.

图 1(a)、(b)结果表明，信道数量对各算法相对NN法的性能影响不大，而L_sb对各算法性能均有较大影响.随着L_sb从1减小到0.1，相对报文传输数量先减小后增大，并在L_sb约为0.9时相对报文传输总数量指标最低，即此时基于NC的算法的优势最大.当L_sb=0.9时，L100、R1相对于NN节省的报文传输数量近50%.这种现象可解释如下：由于各规划变量只能取整数，且为了满足约束条件，各变量只能向上取整，当L_sb比较接近1时，相应的取消整数限制后的线性规划解可能稍大于整数，向上取整后导致该变量的增加幅度更大，而NC技术能综合各报文，降低这种向上取整的不利影响，从而使基于NC的算法相对于非NC算法的优势变大，导致L_sb约为0.9时优势达到最大. LR的相对报文传输总数量比L100和R1虽稍大，但当L_sb约为0.9时其节省报文量仍约45%，所以3种基于NC技术的算法均能大幅度降低报文传输数量，见图 2(其中，R1/NN为R1Max与NN之比，L100/NN为L100Max与NN之比，LR/NN为LRMax与NN之比).

对L_sb=0.9附近的进一步仿真结果表明，在L_sb=[0.9，1]区段，相对报文传输数量随L_sb的增大而减小，直到在L_sb=1时跃增到接近1，见图 2. 图 1(c)、图 1(d)均显示出LR算法的离散报文传输数量很少，表明集中报文传输数量较多.离散报文传输数量越多，算法完成所需的时间越长，即延迟越长.

图 1(e)中显示LR算法和NN的信道切换次数最少.分析算法的工作过程易知，在发送算法的每一个阶段内，工作信道切换后不会再切换到原工作信道，所以信道切换次数不超过|C|.而两个阶段的信道切换次数具有叠加效果，所发送报文在两个阶段的分配情况将对信道切换次数指标具有重要影响. L100算法中在两个阶段发送的报文均较多，所以其信道切换次数指标最大，而R1和LR的报文分别主要在第二阶段和第一阶段传输的，所以二者的信道切换次数较小. NN算法是求解整数线性规划得到的优化理想解，所以其该指标最低.

4 结论

本文研究了CRAN中的报文多播传输技术，基于网络编码构建了多播传输算法框架，并基于该框架提出了几种多播传输算法.该算法通过引入随机网络编码技术，充分利用无线信道的广播性质降低报文传输数量；充分考虑传输节点对不同信道的访问权限及报文传输质量，使上游节点的每次报文传输都最大化后续节点的报文收益，提高报文多播和广播的传输效果；该算法有效节省了封装了编码报文的组合报文中用于解码的附加信息，降低了传输的组合报文长度.