1.   引言

无线网络多播通信由于其低能耗、高传输效率而变得越来越受欢迎。在多播通信过程中，由于发送端单次发送数据包能够同时满足多个接收者的需求，提高了网络的吞吐量。针对不同的接收者，接收消息的信道条件存在差异，因此，在有损信道中实现可靠多播传输是很具有挑战性的。为了有效减少包的丢失并提高传输效率，网络编码技术(NC)在2000年被Ahlswede等人^[1]提出后，引起了网络界的极高重视。

大多数学者在研究无线网络多播通信时，都是假设队列结构是稳定的，即队列长度是无限的^[2]。在通过利用队列结构模型提高网络吞吐量的过程中，通常都会使用反馈机制来判断发送的数据包是否被成功接收。文献[3]研究了这种反馈给队列长度以及解码时延带来的影响，结果表明结合反馈和编码在一定程度上能够提高网络的吞吐量。对于无线网络，文献[4]考虑到了多跳和多源的传输情形，分析了网络中的最大化吞吐量。在延时敏感的网络中，文献[5]分析了在有损信道的多播网络中应用网络编码方式的稳定性能，提出了一种虚拟队列结构并针对两个接收者的网络进行了详细的分析。然而，针对大于两个接收者的情形，这种虚拟队列模型变得比较复杂。文献[6]在两个接收者的广播条件下，就网络吞吐量这一指标分析了网络的性能。

在最近的网络多播研究中，文献[7]提出了一种NC-ARQ数据包重传策略，在某种程度上改善了传统的重传效率。文献[8]在Ad-hoc网络中提出了一种部分网络编码方式，该模型虽然改善了网络的吞吐量，但是忽略了队列的稳定性。此外，在不考虑队列稳定性的情况下，文献[9]推导出了速率最大化以及能量、延时最小化的公式。文献[10]应用李雅普诺夫优化模型最大化系统的能量效率以及网络的稳定性。

在两个接收者的情况下，文献[11]提出了一种无线多播虚拟队列模型，在该模型中，每个接收者在发送端都拥有一个队列，用来存放每次发送后没有被该接收者接收到的数据包。文献[12]采用这种队列思想，在3个接收者的条件下，分析出了网络中的最大输入率。紧接着，针对文献[11]给出的虚拟队列模型，文献[13]对该模型做了改进，根据发送数据包在接收端的接收情况设置虚拟队列数目，最后采用线性编程的方式来获取在队列稳定的情况下的编码调度策略。虽然文献[13]对虚拟队列模型做了改进并提出了Data-Flow算法，然而该算法以概率的形式来选取编码调度策略仍存在不足，导致部分队列的数据包被选择参与编码发送的概率过小(不足1%)，这些数据包可能会长时间停留在队列中。

针对Data-Flow算法存在的问题，本文做了相应的改进并提出了一种新的基于到达时间编码调度算法(Coding Scheduling strategy based on Arriving Time, CSAT)。该算法将不再以随机概率的形式来选取编码策略，而是优先考虑最先到的数据包；在编码发送的过程中，结合了编码和非编码的方式发送数据包。本文中，一方面考虑到队列长度带来的影响，为了保持队列的稳定性，按照一定的比例从主、次队列中选择数据包发送；另一方面为了尽可能地减少数据包在队列中停留的时间，在选择编码方案时优先考虑最先到达队列的数据包并采取更多的数据包参与编码的方式发送。仿真实验结果表明，和ARQ, Data-Flow算法相比较，CSAT能够表现出更高的传输效率；在网络吞吐量、传输时延上，CSAT均有很大的提高。

2.   系统模型

2.1   虚拟队列结构模型

本文研究的背景是在单跳无线多播网络中，源节点以多播的形式通过有损信道发送数据包到N个目的节点(R₁, R₂, ···, R_N)。假设数据包都是从源节点稳定产生的并以一定的输入率λ进入主队列等待发送。每一个接收者的接收信道都有独立的信道丢包率ε_i(i=1, 2, ···, N)。每一个数据包被接收者R_i成功接收的概率为β_i=1–ε_i(i=1, 2, ···, N)。假设：(1)数据包在传输过程中，信道的丢包率是固定的；(2)单位时隙内最多传输1个数据包；(3)在每一个数据包传输过后，每一个接收者反馈1 bit ACK/NACK给发送者，用来确认先前发送的数据包是否成功地被接收者接收。

本文中使用的队列结构和文献[12]相同，如图1所示。每一个新产生的数据包首先进入主队列，记做队列Q₀。每一个从Q₀发出去的数据包有3种可能：(1)如果该数据包没有被任何接收者接收到，它将继续停留在主队列Q₀中；(2)如果该数据包被所有的接收者接收到，它将离开队列系统；(3)如果该数据包至少被1个接收者接收到但没有被所有的接收者接收到，它将进入次队列，即队列Q_i(i=1, 2, ···, M)。每一个队列Q_i(i=0, 1, ···, M)都关联1个索引集合I_i，该集合由那些没有成功接收到数据包的目标接收者组成。显然，队列的总个数，即索引集合的个数是${2^N} - 1$，次队列的个数为$M \!=\! {2^N} \!-\! 2$。每个队列中的数据包都会占据内存，总共的队列长度$|{Q_{\rm{T}}}| = \displaystyle\sum\nolimits_{i = 0}^M {|{Q_i}|}$。

图 1  虚拟队列结构模型

下载: 全尺寸图片 幻灯片

为了能够在虚拟队列模型系统中通过网络编码的方式减少数据包重传次数，提高网络的吞吐量。在每一个时隙内，发送端将通过网络编码的方式从一组队列中选取数据包以多播方式发送给所有的接收者。选取的每一组队列必须满足以下两个条件：

(1) 它们队列的索引集合必须互斥，目的是为了使发送的编码包能够被所有目标接收者解码

(2) 这些索引集合的并集是所有接收者的集合，目的是为了让每次发送的编码包给所有接收者提供新的数据包信息。

对于一个拥有3个接收者的多播网络，存在的编码策略如表1所示。

表 1  3个接收者时的网络编码策略

队列编号	Q0	Q1	Q2	Q3	Q4	Q5	Q6
索引集合	{1, 2, 3}	{1, 2}	{2, 3}	{1, 3}}	{1}	{2}	{3}
NC0	1	0	0	0	0	0	0
NC1	0	0	0	0	1	1	1
NC2	0	1	0	0	0	0	1
NC3	0	0	1	0	1	0	0
NC4	0	0	0	1	0	1	0

下载: 导出CSV 

| 显示表格

2.2   模型稳定性分析

考虑到模型的复杂度问题，本文将基于两个接收者的情形分析该队列模型的稳定性，该队列结构如图2所示^[11]。

图 2  两个接收者的虚拟队列模型

下载: 全尺寸图片 幻灯片

其中，ε₁, ε₂分别为发送端到接收端R₁, R₂的信道丢包率。此时，队列Q₀的服务率为1–ε₁ε₂, Q₀的输出率为

由于队列Q₁没有来自发送端T的直接输入，因此可以直接将其输出率表示为该队列上的输入加上其反馈(从队列Q_i发送出去的数据包如果没有被R_i接收到，将继续停留在队列Q_i中)。

由式(3)和式(4)，可以得出

对于队列Q₂，同样可以得出

其中，y₁和y₂分别为队列Q₁和队列Q₂的输出率。

为了保持队列系统的稳定性，在每个时隙内信道中最多存在一个数据包；此时，y₁和y₂将满足式(7)限制条件

将式(3)、式(5)以及式(6)代入式(7)即可得出

类似地，针对N个接收者，信道丢包率分别为ε₁, ε₂, ···, ε_N。在保持队列的稳定性的条件下有

3.   CSAT编码调度策略

基于上一节的虚拟队列结构模型，在队列中选取数据包进行发送时，以何种策略选择编码方式极其重要。如果按照Data-Flow算法以一种概率的形式选取编码方式，将编码方式NC₀, NC₁, NC₂, NC₃, NC₄的选择机会分别设置概率为P₀, P₁, P₂, P₃, P₄。通过分析其实验结果发现，当ε₁=0.1, ε₂=0.1, ε₃=0.1时，P₀的概率为0.9009009, P₁的概率为0.0745290008，而P₂, P₃, P₄的概率均为0.008190008。一旦有数据包停留在了队列Q₁, Q₂, Q₃中，它们会以很低的概率被选中(不到1%)。那么它们参与编码转发的机会就相对比较小，这样会给接收者带来非常不利的影响。Data-Flow算法在考虑队列稳定性下的最大输入率时，忽略了网络的吞吐量和等待时延，存在发包率低的不足。针对该算法的不足，本文提出了一种新的基于数据包到达时间的编码调度算法(CSAT)。

3.1   CSAT的描述

CSAT算法将不再以一种概率的形式来选取编码方式，而是动态地考虑到了队列里存在数据包的实际情况，算法的流程如表2所示。考虑到队列的稳定性，该算法将以一定的比例从主队列中选取数据包发送，接着从次队列以编码或者非编码的方式发送数据包。在选择编码方式的时候，为了尽可能让先到达队列的数据包优先参与编码发送出去，使用CSAT调度策略寻找编码方式。

表 2  CSAT调度策略流程

输入：　队列Qi(0 ≤ i ≤ 6), QT ={Qi|0 ≤ i ≤ 6}，主队列为Q0，次队列为Qi(1 ≤ i ≤ 6), $P_i^h$表示队列Qi的队首数据包，索引集合为I={Ri|1 ≤ i ≤ 3}, $I_i^h$表示Qi队首数据包的索引集合，Ri表示接收者i，编码方式表示为NCk(1 ≤ k ≤ 4)，主次队列发送比为m/n，令flag1= 0, flag2=0。
输出：  每个队列的最大长度max(Qi)，被所有接收者成功接收到的数据包的个数num，每个时隙发送数据包的个数的和sum。
步骤 1　若QT 不为空，执行步骤2；否则等待数据包的到达；
步骤 2　如果Q0不为空并且flag1<m，发送队列Q0的队首数据包$P_i^h$, flag1++，根据反馈消息更新该数据包的索引集合Ihi；否则跳转步骤4；
步骤 3　如果$I_i^h$集合为空，$P_i^h$数据包被成功接收，离开该队列系统；如果$I_i^h$={R1, R2, R3}, $P_i^h$数据包没有被任何接收者接收，继续停留 队列Qi，否则该数据包将根据其索引集合进入其他队列；
步骤 4　如果次队列非空并且flag2<n，选择最先到达队列的数据包$P_i^h$，寻找满足该数据包的编码方式集合{NCk|1 ≤ k ≤ 4}，否则跳转步骤1；
步骤 5　如果有3个数据包参与编码的编码方式存在并且其它队列与之编码的数据包均存在，则以该编码方式发送数据包$P_i^h$, flag2++；否 则执行步骤6；
步骤 6　若其它队列存在数据包与之编码发送，则以该编码方式发送数据包$P_i^h$, flag2++；否则，以非编码的方式发送数据包$P_i^h$, flag2++；
步骤 7　输出各个队列的最大长度max(Qi)，被所有接收者接收到的数据包个数num以及每个时隙发送的数据包个数和sum。

下载: 导出CSV 

| 显示表格

3.2   CSAT的扩展性分析

本文提出的CSAT算法能够被扩展至任意多个接收者的情形，关键是寻找满足2.1节中两个条件的所有编码可能。对于多个接收者，编码方案的个数等同于数学概念中的“贝尔数”^[14]，它计算出了包含n个元素的集合可以划分为不相交的非空子集的数量。第n个贝尔数定义为

式中的S(n, k)是第2类斯特林数，将n个元素划分为k个不同集合的方法数目

式(11)中C(i, j)是一个单行的符号组合。

证明 $S(n,k) = \dfrac{1}{{k!}}\displaystyle\sum\limits_{i = 0}^{k{\rm{ - }}1} {{{( - 1)}^i}} C_k^i{(k - i)^n}$。

令${x^n} = \displaystyle\sum\limits_{k = 0}^n {S(n,k)} x(x - 1)(x - 2) ··· (x - k + 1)$。

取x=1，得$1=S(n,1)$，则$S(n,1) = \dfrac{1}{{1!}} \times$$1 = 1$；

取x=2，得${2^n} = S(n,1) \times 2 + S(n,2) \times 2 \times 1$，则$S(n,2) = {2^{n + 1}} - 1 = \dfrac{1}{{2!}}[{2^n} - C_2^1]$；

取x=3，得${3^n} = S(n,1) \times 3 + S(n,2) \times 3 \times 2 +$$S(n,3) \times 3!$，则

用数学归纳法对k进行归纳证明，即可得出^[15]：

证毕

对于一个拥有N个接收者的多播网络，存在的编码策略的数量为${S_N} = B(N)$，表1将会变成一个${S_N} \times M$的矩阵“X”。

矩阵中的值为1或0，表示第i个编码策略NC_i、第j个队列是否被选中。针对多个接收者的情形，同样可以采用CSAT算法思想发送数据包。

4.   仿真性能与分析

本文使用了OMNet 4.4软件分别对网络输入率、吞吐量、等待时延进行了仿真实验，验证了CSAT算法的可行性和性能的优劣。

4.1   队列的稳定性分析

为了分析在不同的信道丢包率下，输入率、主次队列发送比对队列的稳定性和吞吐量造成的影响，做了如下实验：

当信道的丢包率分别为0.1, 0.2, 0.3时，在发送端发送了10000个时隙，统计被所有接收者接收到的数据包数量，计算出网络的吞吐量。从图3(a)中可以看出，当主次队列发送比固定为9:1, 8:2, 8:2时，针对不同的丢包率ε，网络中都存在一个临界输入率λ₀。当λ<λ₀时，网络能够保持较高的吞吐量；λ>λ₀时，网络中的吞吐量将会随着输入率的增加而不断的下降。图3(b)描述了当输入率固定时，总存在一个合适的主、次队列发送比，使得网络吞吐量达到最大值，即保持队列稳定。

图 3  不同条件下吞吐量的变化

下载: 全尺寸图片 幻灯片

在信道丢包率为0.1、主次队列发送比为9:1条件下，图4(a), 4(b), 4(c)分别表示当输入率为0.88, 0.89, 0.90时，发送10000, 20000, 30000, 40000, 50000个时隙时，每个队列的最大长度随着时间变化趋势。从图中可以看出，除了主、次队列发送比外，输入率对于队列的稳定性也有一定的影响。通过对比发现，在信道丢包率为0.1的条件下，当网络中的最大输入率为0.89时，该队列模型基本能够趋于稳定状态。

图 4  不同输入率下队列的最大长度

下载: 全尺寸图片 幻灯片

图5反映了在不同的信道丢包率下，模型的最大输入率随着丢包率的变化。和ARQ以及文献[5]相比较，本文算法在最大输入率上有很大的提高；从图中可以看出，本文的实验结果和文献[13]中的理论值很接近。表3记录了在不同的丢包率下的最大输入率，以及达到最大输入率时主次队列发送比。该表显示，对于不同的丢包率，总存在一个合适的主次队列发送比，使得在该丢包率下能够使输入率达到最大，并且在该条件下队列能够相对稳定。

表 3  在不同的丢包率下达到的最大输入率以及最优的主次队列发送比

信道丢包率ε	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
主次比(m/n)	9:1	8:2	8:2	7:3	6:4	5:5	7:3	7:3	7:3
最大输入率(λ)	0.89	0.79	0.69	0.59	0.49	0.39	0.3	0.2	0.1

下载: 导出CSV 

| 显示表格

图 5  比较不同算法的最大输入率随着信道丢包率的变化

下载: 全尺寸图片 幻灯片

通过综合分析上述实验结果发现，随着信道丢包率的增加，在保证队列模型稳定的前提下，模型的最大输入率呈现下降的趋势。针对不同的信道丢包率，总存在最优的主、次队列发送比，使得各个队列的最大长度随着发送时隙的增加而趋于稳定状态。基于虚拟队列模型，本文提出的CSAT算法在模型稳定性上性能最好。

4.2   CSAT调度策略传输效率分析

4.2.1   发包率、编码率的定义

基于上述的虚拟队列结构模型，为了验证CSAT算法的可行性，接下来在发包率、编码率、吞吐量以及平均等待时延方面做了仿真实验。通过和Data-Flow算法以及传统的ARQ作对比，来突出CSAT算法的优势。发包率、编码率定义如下：

(1) 发包率的定义：在每一个时隙T_i内，发送编码包的个数为C_i，发送非编码包的个数为S_i，由于每个时隙最多只能发送一个数据包，如果队列中没有数据包发送将会进入等待。即${C_i} \in \{ 0,1\}$, ${S_i} \in \{ 0,1\}$，并且${C_i} \cup {S_i} \in \{ 0,1\}$，即$0 \le {C_i}{\rm{ + }}{S_i} \le 1$。因此，n个时隙内的发包率η定义为

(2) 编码率的定义：在n个时隙内，在队列Q₁, Q₂, ···, Q_M中以非编码的方式发出的数据包的个数分别为N₁, N₂, ···, N_M，对于N个接收者时，M=2^N–2；以编码的方式发送的数据包个数为C，则n个时隙的编码率γ为

为了提高网络性能，在调度数据包发送的过程中，将选择编码和非编码相结合的方式。如果在次队列选择数据包发送的某个时隙内，次队列中有数据包存在但是没有编码机会发送出去，此时，我们将单独地将最先到达队列的数据包以非编码的方式发送出去。在信道丢包率为0.2时，图6(a)描述了本文算法中次队列中发送数据包的编码率随着输入率的变化。从图中可以看出，当输入率接近0.8时，编码率达到最大并且趋于稳定，该结论和图3的实验结果相一致。图6(b)表示单位时隙内发送数据包的个数随着输入率的变化。从图中可以看出，由于本文算法结合了编码和非编码的方式，在编码调度策略上改进了文献[13]算法存在的不足，因此在发包率上有明显的提高。

图 6  网络中的编码率和发包率与输入率的关系

下载: 全尺寸图片 幻灯片

图7(a)表示在信道丢包率为0.2时，网络中的吞吐量随着输入率的变化。对于本文算法、文献[13]算法及ARQ，当丢包率固定时，总会存在一个最大输入率，一旦输入率超过这个阈值时，网络吞吐量将会呈现迅速下降的趋势。图7(b)表示在输入率为0.79时，网络吞吐量随着信道丢包率的变化。和ARQ、文献[13]算法相比较，本文算法在网络吞吐量上有很大的提高。图7(c)表示在不同的丢包率下，在保证队列稳定的前提下达到最大输入率时，网络中的吞吐量随着信道丢包率的变化。从图中可以看出信道丢包率越大，吞吐量的提高幅度也就越大。图7(d)表示在输入率为0.89时，数据包的平均等待时延随着丢包率的变化。相比于ARQ、文献[13]算法，本文算法明显减少了网络中数据包传输的时延，提高了传输效率。

图 7  吞吐量、平均等待时延与输入率和丢包率的关系

下载: 全尺寸图片 幻灯片

结合网络性能分析结果发现，相较于传统的ARQ以及文献[13]算法，本文提出的CSAT调度算法结合了编码和非编码方式后在发包率上有一定的提高。除此之外，相较于ARQ, CSAT算法在吞吐量上提高了将近20%，并且网络的平均等待时延有所下降。本文提出的CSAT调度策略在网络性能上有很大的提高，对于提高多播网络的传输效率具有很大的意义。

5.   结束语

针对无线多播网络，本文提出了一种新的编码调度策略算法(CSAT)，该算法采用了编码和非编码相结合的方式。在编码重传的过程中，优先选择最先到达的数据包，同时尽可能地让更多的数据包参与编码发送；当队列中不存在编码机会时，单独将最先到达的数据包以非编码的发送出去。仿真结果显示，在保证队列稳定的前提下，本文算法能够维持较高的输入率。相比于文献[13]算法、ARQ算法，CSAT在网络吞吐量和传输时延上有很大的提高。本研究对于提高多播网络传输的效率以及推动网络编码的研究有着很大的意义。随着接收者数目的增加，虽然本文调度策略具有一定的扩展性；但是，在队列模型以及调度算法上也存在着不足。当接收者的数目增加到一定程度时，队列的数量会呈现一种指数的增长方式，将会过度地消耗资源；此时，该编码调度策略的时间复杂度较高。在以后的研究中，针对更多的接收者，我们将会研究如何减少队列的个数，并进一步优化编码调度策略，达到性能优化的目的。