网络编码(network coding)^[1]是一种融合编码和路由的信息交换技术, 允许网络中间节点对传输的信息按照合适的方式进行编码处理而不仅仅完成存储和转发, 基于该方式的网络多播能够实现最大流最小割定理确定的最大理论传输容量。文献[2]进一步证明只需要线性网络编码就可以达到网络最大传输容量。线性网络编码中, 编码节点输出链接上的信息是其输入链接信息的线性组合。网络编码在提高网络吞吐量、改善负载均衡、降低无线节点能耗等方面具有明显的优势, 并逐渐在内容分发^[3]、分布式存储^[4]、无线网络^[5]、P2P网络^[6]等领域得到成功应用。

然而, 网络节点的编码操作引入了额外的计算开销和资源消耗, 增大了系统的复杂性^[7]。减少进行网络编码操作的中间节点数量具有实际的意义。事实上, 编码操作不需要在所有的中间节点都实施, 只要在部分节点上进行网络编码就可达到网络的最大理论传输容量^[8]。然而, 确定最小编码节点集被证明是一个NP难问题^[8-9]。

已有的研究工作都是通过减少参与编码的中间节点数量, 以降低网络编码开销, 优化编码效率。文献[7]指出了针对有环和无环拓扑的网络编码节点的上界, 并证明该界限仅决定于设计速率和接收节点的数量。文献[10]提出子树分解的方法, 得出在双源、d个接收节点的无环网络中, 编码节点数不超过d-1个。但上述两种方法依赖于信息传输的边序列, 不合适的序列会导致算法性能下降并带来更多的计算开销。文献[11]提出了用于网络编码的线性规划模型, 但优化算法过于复杂, 随着接收节点的增加, 复杂度呈指数级增长。文献[8-9]提出了基于遗传算法的网络编码优化算法, 实验结果表明效果优于上述非启发式算法, 但遗传算法本身存在的缺陷, 如早熟、收敛速度慢等可能导致该算法表现出较差的性能。最近, 量子进化算法^[12]被引入到网络编码优化问题的研究中, 由于该算法具有种群规模小、收敛速度快和全局寻优能力强等特点而大量应用于各种组合优化问题的求解中^[13-15]。文献[16]应用量子进化算法及其改进算法解决网络编码优化问题, 得到较经典遗传算法更好的性能, 但该算法仅仅考虑了量子进化算法本身的性能改进, 没有针对性地考虑网络编码优化问题的特殊性, 当网络规模扩大时, 该算法搜索能力会下降。

针对现有的网络编码优化算法存在的不足, 本文以量子进化算法作为研究工具, 对网络编码优化问题进行进一步的研究。提出了基于改进量子进化算法的网络编码优化算法IQEA-NC, 该算法充分利用了量子计算的并行性和量子染色体多状态表征能力, 同时考虑了网络编码优化的诸多约束条件, 对量子进化算法进行了有针对性的改进。

1 网络编码优化问题描述

本文讨论线性网络编码下的单源多接收节点的多播问题。多播网络可以表示为一个有向无环图G= (V, E), 其中, V表示节点的集合, E表示链路的集合。每个链接具有单位容量, 节点间具有较大容量的链接使用多个单位容量链接表示。单源多播场景可以用一个4元组(G, s, T, R)表示, 即在图G= (V, E)中, 将信息从单源s ∈V以速率R传输到接收节点集$T = \{ {t_1}, {t_2}, \cdots, {t_d}\} \subset V$, 如果存在一种传输策略使得所有d个接收节点都接收到了源节点s发出的数据信息, 那么称速率R是可达的。

很明显, 具有多个输入链接的节点才可能进行编码操作, 仅一个输入链接的节点只完成信息的存储和转发。既使是多输入链接的节点, 如果其输出链接的信息仅仅依赖于一个输入链接的信息, 该节点仍无需进行编码操作。事实上, 网络中间节点是否需要编码取决于其是否存在至少一条输出边需要传输编码信息, 所以编码链接能够比编码节点更精确地表示当前网络的编码计算开销^[7]。因此, 本文讨论的网络编码优化问题就是在保证网络多播速率R可达到的情况下, 最小化参与网络编码的编码链接数量。

本文引用了代数方法^[17]对网络编码优化问题进行描述。给定一个有向无环图G= (V, E), 如果满足条件head(e) tail(e'), 则称边e=(u, v)连入边$e' = (v, u')$。以图G= (V, E)为参照, 生成一个有向标线图$G' = (V', E')$, 其中, $V' = E$, $E' = \{ (e, e') \in {E^2}:{\rm{head}}(e) = {\rm{tail}}(e')\} $, 图中的每一条边$e = (e, e') \in E'$被标记上对应的链路系数ζ_i, ζ_i在有限域GF(2^m)上随机选取。按文献[17]的方法, 为d个接收节点中的每一个节点都建立一个R×R的系统传递矩阵以描述源节点和每个接收节点间的关系。p(ζ)表示这d个系统传递矩阵所对应行列式的乘积, 是一个关于ζ_i的多项式, 当p(ζ)≠0时, 网络可以达到给定的多播速率^[17]。

通过$G \to G'$的转换, 在图G中节点的每个输出链接被映射为图G'中的节点。仅仅需要观测G'中具有多输入链接的节点编码情况, 这种观测实际上体现了对图G中的编码链接的判断。给定G'中一个具有多输入链接的节点v, 如果其链路系数向量中除了一个系数, 其余所有系数均为0, 且生成的p(ζ)≠0, 那么可以断定在其他节点均进行编码操作的前提下该节点v不需要进行编码操作^[8]。但是网络编码作为所有中间节点都可能参与的整体行为, 上述针对单个节点的判断方式无法用于验证所有节点的编码状况, 网络编码在某一个节点是否发生取决于其他节点是否需要编码。如果图G'中具有多输入链接的节点共有k个链路系数, 那么寻找编码节点工作将在k维二进制空间中进行。

2 量子进化算法

进化算法是一类模拟生物进化过程的随机搜索及优化方法, 把量子计算的原理和特性融入到进化计算中产生的量子进化算法(QEA)^[12], 可以充分利用量子计算的并行性和随机性解决普通进化计算在损失种群多样性时引起的早熟收敛。

2.1 量子比特

在量子进化算法中, 最小的信息单元为一个量子比特(qutbit), 它的定义是在一个二维复向量空间中的一个单位向量。一个量子比特的状态可取0(记为$\left| 0 \right\rangle $), 或者1(记为$\left| 1 \right\rangle $), 或者状态0和1的不同叠加态。一个量子比特记为$\left| \rm{\psi} \right\rangle $, 可以表示为:

$ \left| \psi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle $

(1)

且满足归一化条件:

$ {\left| \alpha \right|^2} + {\left| \beta \right|^2} = 1 $

(2)

式中, α和β为复数, 分别表示$\left| 0 \right\rangle $和$\left| 1 \right\rangle $出现的概率幅值; |α|²和|β|²分别表示量子比特处于状态0和状态1的概率。符号d=α×β代表该量子比特在复平面坐标中所处的象限。

2.2 量子编码

量子进化算法采用了基于量子比特的编码方式, 即用实数定义一个量子比特位。一个具有m个量子比特位的系统可以描述为: $\left[{\begin{array}{*{20}{c}} {{\alpha _1}}\\ {{\beta _1}} \end{array}{\rm{ }}\begin{array}{*{20}{c}} {\alpha 2}\\ {{\beta _{\rm{2}}}} \end{array}{\rm{ }}\begin{array}{*{20}{c}} \cdots \\ \cdots \end{array}{\rm{ }}\begin{array}{*{20}{c}} {{\alpha _m}}\\ {{\beta _m}} \end{array}} \right]$, 其中, ${\left| {{\alpha _i}} \right|^2} + {\left| {{\beta _i}} \right|^2} = 1{\rm{ }}(i = 1, 2, \cdots, m)$。该表示方法可以表征任意的线性叠加态。

如一个具有如下概率幅值的3量子比特系统: $\left[\begin{array}{l} \frac{1}{{\sqrt 2 }}{\rm{ }}\frac{1}{{\sqrt 2 }}{\rm{ }}\frac{1}{2}\\ \frac{1}{{\sqrt 2 }}{\rm{ }}\frac{1}{{\sqrt 2 }}{\rm{ }}\frac{{\sqrt 3 }}{2} \end{array} \right]$, 则系统的状态可表示为:

$ \begin{array}{c} \frac{1}{4}\left| {000} \right\rangle-\frac{{\sqrt 3 }}{4}\left| {001} \right\rangle + \frac{1}{4}\left| {010} \right\rangle-\frac{{\sqrt 3 }}{4}\left| {011} \right\rangle + \\ \frac{1}{4}\left| {100} \right\rangle-\frac{{\sqrt 3 }}{4}\left| {101} \right\rangle + \frac{1}{4}\left| {110} \right\rangle - \frac{{\sqrt 3 }}{4}\left| {111} \right\rangle \end{array} $

即该量子编码转化为|000|、|001|、|010|、|011|、|100|、|101|、|110|、|111|的概率分别为1/16、3/16、1/16、3/16、1/16、3/16、1/16、3/16。可见, 3量子比特系统可以表示8个二进制编码的信息, 使得按照量子编码生成的种群具有更好的多样性, 且随着|α|²和|β|²趋于0或者1, 编码将收敛于一个单一态。

3 基于量子进化算法的网络编码优化

本文将量子进化算法用于网络编码优化问题, 提出了基于改进的量子进化算法的网络编码优化算法(IQEA-NC)。针对网络编码优化问题的特点, 对量子种群的初始化、观测算子及量子旋转门修正等方面进行了改进, 提高量子进化算法的多样性保持能力, 并降低算法搜索空间、增强全局搜索能力, 同时避免陷入局部最优。

3.1 网络编码优化问题的量子比特表示

考虑图G'中具有多输入链接的节点, 如果此类节点的输入链接的个数之和为k, 定义一个长度为k的量子染色体对应于链路系数ζ_i, 其编码形式为:

$ \boldsymbol{q}_1^t = \left[{\begin{array}{*{20}{c}} {{{\alpha '}_1}}\\ {{{\beta '}_1}} \end{array}{\rm{ }}\begin{array}{*{20}{c}} {{{\alpha '}_2}}\\ {{{\beta '}_2}} \end{array}{\rm{ }}\begin{array}{*{20}{c}} \cdots \\ \cdots \end{array}{\rm{ }}\begin{array}{*{20}{c}} {{{\alpha '}_k}}\\ {{{\beta '}_k}} \end{array}} \right]{\rm{ }}i = 1, 2, \cdots n$

(3)

$Q(t) = \{ \boldsymbol{q}_1^t, \boldsymbol{q}_2^t, {\rm{ }} \cdots, {\rm{ }}\boldsymbol{q}_n^t\} $表示种群大小为n的对应问题的量子种群, 经量子观测后, 生成一个二进制编码的普通种群$P(t) = \{ p_1^t, p_2^t, {\rm{ }} \cdots, {\rm{ }}p_n^t\} $, 种群中每个个体$p_i^t = \{ b_{i1}^t, b_{i2}^t, \cdots, b_{ik}^t\} $是长度为k的二进制编码串。针对普通种群中的个体p_i, 如果个体的第j位b_ij=0, 则对应的ζ_j设为0;否则保持ζ_j不变。可见, 每一个普通种群中的个体可以确定对应的链路系数方案, 如果当前链路系数的设置可以满足$p(\zeta ) \ne 0$, 即达到给定的组播速率, 则当前的编码方案可行。如果编码方案可行, 则依次检查图G'中具有多输入链路的节点, 如果某节点具有两个及以上的非0的链路系数, 则该节点是图G'中的编码节点。图G中所有的编码节点的数目对应了图G中编码链路的数目。

在网络编码优化问题中, 本文取适应度函数为满足网络多播速率要求的前提下, 参与网络编码的链接数的倒数, 即:

$ f = \frac{1}{N}\;\;\;\;{\rm{ s}}{\rm{.t}}{\rm{. }}p{\rm{(}}\xi {\rm{)}} \ne 0 $

(4)

式中, N为编码链接的个数。量子进化的目的就是寻找最大适应度函数值所对应的链路系数方案。

3.2 初始化种群

在通常的量子进化算法中, 量子比特都被初始化为$\left( {1/\sqrt 2 ,1/\sqrt 2 } \right) $, 以保证可能的线性叠加态以相同的概率出现。但在网络编码优化的问题中, 实际参与网络编码的节点数量远小于中间节点的数量, 即链路系数中0的个数远大于非0的个数。利用这一先验知识, 调整量子比特中状态0和状态1的概率幅值, 使得算法的搜索空间降低, 候选解更靠近最优值, 可以提高搜索效率。本文将种群中所有的α和β分别初始化为$\sqrt {0.65} $和$\sqrt {0.35} $。

3.3 观测算子的改进

对量子种群Q(t)的所有个体进行一次观测, 可以得到一个包含所有候选解的普通种群P(t)。观测过程中, 对于量子种群中个体q_i的每一个量子比特, 随机产生一个数r ∈[0, 1], 如果$r \le {\left| {{\alpha _i}} \right|^2}$, 则普通解p_i中对应的二进制位取0, 否则取1。通常情况下, 观测的操作只发生一次。但一次观测过程具有较大的随机性, 本文采用多次观测法实现对量子观测算子的改进。

算法对当前量子种群Q(t)进行m次观测, 得到m个普通种群${P_i}(t) = \{ p_{i1}^t, p_{i2}^t, {\rm{ }} \cdots, {\rm{ }}p_{in}^t\}, {\rm{ }}1 \le i \le m$, 随后的适应度评价在m个普通种群中的所有普通个体上实施。由于候选个体数量的增大, 使得在每一代内获得可行解甚至是最优解的概率提高了, 多次观测法实现了量子进化过程中代内的局部优化方法, 有助于提高候选种群的多样性和解的质量。但当量子比特逐渐向单一态收敛时, 多次观测所得到的普通种群具有极大的相似性, 对提高解的质量作用有限。所以在进化过程早期多次观测法才具有较好的效果, 经过多次尝试, 设定在前50代进化过程中使用多次观测法。

3.4 量子旋转门修正

量子进化算法中, 采用量子旋转门操作对量子比特进行改变从而更新量子种群, 促进每个量子比特的概率幅值收敛到0或者1, 直到搜索到最优解。量子旋转门的定义为:

$\boldsymbol{U}({\theta _i}) = \left[\begin{array}{l} \cos ({\theta _i}){\rm{ }}\;\;-{\rm{sin(}}{\theta _i}{\rm{) }}\\ \sin ({\theta _i})\;\;\;\;{\rm{ cos(}}{\theta _i}{\rm{) }} \end{array} \right]$

(5)

式中, ${\theta _i} = \delta \times s({\alpha _i}, {\beta _i})$是具有方向的旋转角, δ是用于确定收敛速度的系数, 如果δ的值太小会降低收敛速度, 而δ的值太大进化容易出现早熟现象。s(α_i, β_i)用于确定旋转方向, 以保证算法的收敛。量子旋转门的更新策略如表 1所示。

表 1中, x_i为当前染色体的第i位, b_i为当前最优染色体的第i位, f(x)为适应度函数。

量子旋转门操作定义为:

${\left[{{{\alpha '}_i}{{\beta '}_i}} \right]^\rm{T}} = \boldsymbol{U}({\theta _i}){\left[{{\alpha _i}{\rm{ }}{\beta _i}} \right]^\rm{T}}$

(6)

为了降低计算的复杂性, 本文将旋转角系数δ固定为0.01π, 采用表 1的固定旋转角的量子旋转门调整策略。但量子旋转门调整存在一定的缺陷, 如果量子比特的α和β过早地收敛到0或者1附近, 则对该量子比特的观测结果只能为0或者1, 此时量子旋转门会进一步加速量子比特的收敛, 容易陷入局部最优。本文采用H_ε门^[18]对旋转后的概率幅值进行修正。H_ε门操作定义为:

$ {\left[{{{\alpha '}_i}{\rm{ }}{{\beta '}_i}} \right]^\rm{T}} = {H_\varepsilon }({\alpha _i}, {\beta _i}, {\theta _i}) $

(7)

对${\left[{{{\alpha ''}_i}{{\beta ''}_i}} \right]^{\rm{T}}} = \boldsymbol{U}({\theta _i}){\left[{{\alpha _i}{\rm{ }}{\beta _i}} \right]^\rm{T}}$ :

1) 如果${\left| {{{\alpha ''}_i}{\rm{ }}} \right|^2} \le \varepsilon \;{\rm{ and }}\;{\left| {{{\beta ''}_{\rm{i}}}{\rm{ }}} \right|^\rm{2}} \ge 1-\varepsilon $, 则${\left[{{{\alpha '}_i}{\rm{ }}{{\beta '}_i}} \right]^{\rm{T}}} = {\left[{\sqrt \varepsilon, \sqrt {1-\varepsilon } } \right]^\rm{T}}$;

2) 如果${\left| {{{\alpha ''}_i}{\rm{ }}} \right|^2} \ge 1-\varepsilon \; {\rm{ and }} \; {\left| {{{\beta ''}_{\rm{i}}}{\rm{ }}} \right|^2} \le \varepsilon $, 则${\left[{{{\alpha '}_i}{\rm{ }}{{\beta '}_i}} \right]^{\rm{T}}} = {\left[{\sqrt {1-\varepsilon }, \sqrt \varepsilon } \right]^\rm{T}}$;

3) 否则, ${\left[{{{\alpha '}_i}{{\beta '}_i}} \right]^\rm{T}} = {\left[{{{\alpha ''}_i}{\rm{ }}{{\beta ''}_i}} \right]^\rm{T}}$。

其中, $0 < \varepsilon < < 1$, 当量子旋转门操作使得量子比特的α和β过于接近于1或者0时, H_ε门对其进行修正, 该操作避免了算法陷入早熟收敛。

3.5 IQEA-NC算法描述

IQEA-NC算法具体步骤如下:

1) 令进化代数t=1, 种群大小为n, 个体长度为k, 初始化量子种群$Q(t) = \{ \boldsymbol{q}_1^t, \boldsymbol{q}_2^t, \cdots, {\rm{ }}\boldsymbol{q}_n^t\} $, 将种群中所有的α和β分别进行初始化。

2) 采用多次观测法对当前量子种群Q(t)进行观测, 得到普通种群P(t)。

3) 对普通种群P(t)进行评价, 计算种群中每个个体的适应度, 得到评价值数组${\rm{fit}}({f_1}, {f_2}, \cdots, {f_n})$, 保留适应度最大的个体best。

4) 判断终止条件是否满足, 即是否满足预定义的结束条件或者最大进化代数(MAX_GEN), 若满足, 则算法终止; 否则, 继续向下执行。

5) 根据表 1查找量子旋转门的旋转角, 用式(6)和式(7)对Q(t)采用量子门旋转操作并进行修正, 得到更新的量子种群。

6) t=t+1, 算法转至步骤2)继续执行。

4 仿真实验及结果分析

为了测试和比较算法的性能, 将本文算法与NCQEA^[16]和SGA^[8]进行性能比较, 仿真在两种类型的网络拓扑结构开展, 第一种是在文献[8]中使用人工生成的固定拓扑, 如图 1所示, 记为Network 1;第二种是由BRITE模拟生成的20个节点的随机拓扑, 记为Network 2, 具体参数为20 nodes, 54 links, 8 sinks, rate 3。仿真实验中涉及到的算法在Matlab 7.5环境下编程实现, 软件运行环境为Pentium Dual- Core CPU, 2.8 GHz主频, 4 GB内存。

为便于比较, 3种算法设置了相同的种群大小和最大进化代数。对于IQEA-NC算法的其他参数, 选取了经过多次实验尝试后的经验值, 具体设置如下:种群大小n=100, 最大进化代数MAX_GEN=300, 量子比特概率幅值初始值$\alpha = \sqrt {0.65} $, $\beta = \sqrt {0.35} $, 量子旋转门的旋转角大小δ=0.01π, H_ε门阈值ε=10^-5, 对量子种群的观测次数m=2。

NCQEA参数设置为:种群大小为100, 最大进化代数为300, 初始量子旋转角度为0.05π。

SGA参数设置为:种群大小为100, 最大进化代数为300, 交叉概率为0.8, 变异概率为0.01。

以上3种算法的终止条件为:如果连续50次相邻两代种群的最佳适应度都没有发生变化, 则算法结束, 否则达到最大进化代数算法结束。每种算法都运行60次, 获得算法的最优值和平均值。

4.1 算法效果比较

表 2给出了IQEA-NC、SGA、NCQEA在两种拓扑条件下进行60次试验后得到的编码链接数的平均结果。从测试结果看, 对Network 1网络, IQEA-NC总能够得到最小的编码链接数量, 同时具有较小的平均值; 对Network 2网络, IQEA-NC相对于SGA, 无论是最优值还是平均值, 都表现出较为明显的性能优势; 相对于NCQEA, 两者都可以得到较小的最优值, 但在平均值上, IQEA-NC比NCQEA具有更大的优势。

4.2 算法收敛性比较

为比较3种算法的收敛性, 本文修改了算法的终止条件, 不再判断连续50次相邻两代种群的最佳适应度的变化情况, 而是让算法运行到最大进化代数才结束, 实验在Network 2网络上进行。图 2给出了3种算法的收敛性比较。从图中可以看出, IQEA-NC的收敛速度最快, 性能优于NCQEA和SGA, 能够快速接近最优值; SGA进化速度缓慢, 且在算法后期陷入了局部最优。另外, 相对于同样基于量子进化算法的QEANC, IQEA-NC初次搜索就可以得到较优的解, 这是由于采用改进的种群初始化方法, 减小了算法搜索空间。采用多观测算子使算法在代内实现了局部种群优化, 提高了解的质量; 量子旋转门修正策略避免了算法陷入局部极值。正是这些改进, 使得IQEA-NC具有更好的性能优势。

5 结论

针对网络编码优化应用的实际特征, 本文在初始种群选择、观测算子设计和量子旋转门修正策略等方面对传统量子进化算法进行了有效的改进, 提出了基于改进量子进化算法的网络编码优化算法。相对于已有的基于进化算法的网络编码优化方法, 本文提出的方法在满足多播速率的情况下, 算法在准确性和收敛性上都有较大提高。