开放科学(资源服务)标志码(OSID):

0 概述

微纳卫星是指质量为1~100 kg，具有实际使用功能的卫星，其主要特点是体积小、重量轻、功耗低、隐蔽性好、机动灵活、可组网完成任务^[1-2]。微纳卫星网络工作环境复杂，易遭受多种类的攻击且承载的业务量多，所以对路由的安全性和服务质量（Quality of Service，QoS）提出更高要求，而传统的卫星网络路由技术由于通常只考虑了跳数的问题^[3-5]，因此能同时保证数据传输的安全性和网络业务QoS的路由算法成为目前研究的热点。

文献[6-7]分别提出了基于信任机制的安全路由算法，但这两种算法在评估信任值时未考虑节点能量的影响。文献[8-9]提出的信任机制可以防御常见的攻击，但并不能均衡网络中的负载，在计算当前信任值时也没有考虑节点的历史行为。文献[10]提出一种多约束服务选择机制蚁群路由算法，该算法根据网络和用户约束条件的路径消耗指标评价路径的好坏，但初期的收敛速度过慢，容易陷入局部最优解。文献[11]提出的多目标蚁群路由算法减少了网络的平均能耗，但是牺牲了算法的全局搜索能力。文献[12-13]将量子计算与蚁群算法相结合，应用于求解QoS路由，以量子比特编码表示各条路径上的信息素，并通过量子旋转门实现对信息素的更新。

本文提出一种实现多目标优化的Q学习量子蚁群路由算法（Q-learning Quantum Ant Colony Routing Algorithm，QQARA）。该算法综合考虑路径平均信任值和路径费用两个优化目标，同时在路径费用函数中加入量子计算，并将蚁群算法中的信息素映射成Q学习中的Q值，以保证数据传输的安全性和网络业务服务质量。

1 相关机制及参数设计

在微纳卫星网络中，将网络拓扑的基本模型抽象为无向图G={V，E}，其中，V表示网络中所有微纳卫星节点的集合，$ E=\left\{{e}_{i, j}\right|i, j\in V\} $表示微纳卫星网络中的相邻两节点的链路集合，如图 1所示。

1.1 信任机制的建立

为解决微纳卫星网络中节点的恶意攻击行为，识别异常节点，提高网络的安全性，通过节点的直接信任值、间接信任值和能量信任值构成的整体信任值，建立节点信任机制。

1.1.1 直接信任值

直接信任值^[14]是通过自身行为直接检测计算得到的，包括攻击行为信任值和转发行为信任值。

攻击行为信任值用来评估节点的恶意攻击行为。当检测出节点有恶意攻击行为时，减少该节点的信任值，使节点获得较低的信任程度，其计算公式如式（1）所示：

$ {T}_{C}={\mathrm{e}}^{-\psi ({t}_{c}-{t}_{c-1})}\cdot {T}_{C}^{L-1}+d{\left(t\right)}^{L} $

(1)

其中：$ \psi $为指数衰减程度；$ {t}_{c} $、$ {t}_{c-1} $分别为当前、上一次检测时间；$ {T}_{C}^{L-1} $为节点上一个攻击行为的信任值；$ d{\left(t\right)}^{L} $为当前行为评估后量化的值。

$ d{\left(t\right)}^{L}=\left\{\begin{array}{l}r{\left(t\right)}^{L}\text{，}r{\left(t\right)}^{L}\in \left(\mathrm{0, 1}\right)\\ n{\left(t\right)}^{L}\text{，}n{\left(t\right)}^{L}\in (-\mathrm{1, 0})\end{array}\right. $

(2)

其中：$ r{\left(t\right)}^{L} $为节点当前行为正常时的评估值；$ n{\left(t\right)}^{L} $为节点当前行为异常时的评估值。

转发行为信任值用来评估微纳卫星网络中的自私攻击行为。当节点成功转发的数据包数量增加时，该节点的转发行为信任值增加；当节点转发失败次数增加时，该节点的转发行为信任值逐渐降低，其计算公式如式（3）所示：

$ {T}_{\mathrm{R}}=\frac{{T}_{\mathrm{S}}+1}{{T}_{\mathrm{S}}+{T}_{\mathrm{F}}+2}, {T}_{\mathrm{R}}\in \left[\mathrm{0, 1}\right] $

(3)

其中：$ {T}_{\mathrm{S}} $为节点成功转发数据包的个数；$ {T}_{\mathrm{F}} $为节点转发失败数据包的个数。

对节点的攻击行为信任值和转发行为信任值加权求和得到直接信任值$ {T}_{\mathrm{S}\mathrm{E}} $，如式（4）所示：

$ {T}_{\mathrm{S}\mathrm{E}}={\zeta }_{1}{T}_{\mathrm{R}}+(1-{\zeta }_{1}){T}_{\mathrm{C}} $

(4)

其中：$ {\zeta }_{1} $、$ (1-{\zeta }_{1}) $分别为转发行为信任值和攻击行为信任值的权重，取值范围为[0, 1]。

设定一个恶意节点门限阈值$ {T}_{\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}} $，在获得某个节点的直接信任值后，一旦发现该节点的直接信任值低于门限阈值$ {T}_{\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}} $，则认为该节点为恶意节点，将该节点隔离，门限阈值$ {T}_{\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}} $具体大小根据具体情况取值。

1.1.2 间接信任值

间接信任值^[15]是根据第三方节点的信任值得到，其计算示意图如图 2所示。

假设节点i的邻居节点$ {m}_{i} $连通域为$ {Y}_{\mathrm{S}} $，$ {Y}_{\mathrm{S}} $中共有n个邻居节点存储有节点j的直接信任值，则可得到i对j的间接信任值$ {T}_{\mathrm{R}\mathrm{S}} $计算公式如下：

$ \begin{array}{l}{T}_{\mathrm{R}\mathrm{S}}=\frac{\sum\limits_{{m}_{i}\in {Y}_{\mathrm{S}}, {m}_{i}\ne i}\left(\iota {T}_{\mathrm{S}\mathrm{E}}^{\left(i, {m}_{i}\right)}\times \left(1-\iota \right){T}_{\mathrm{S}\mathrm{E}}^{\left({m}_{i}, y\right)}\right)+{T}_{\mathrm{S}\mathrm{E}}}{n+1}, \\ \iota \in \left.\left(\mathrm{0.5, 1}\right.\right]\end{array} $

(5)

其中：$ {T}_{\mathrm{S}\mathrm{E}}^{(i, {m}_{i})} $为节点i对邻居节点$ {m}_{i} $的直接信任值；$ {T}_{\mathrm{S}\mathrm{E}}^{(i, {m}_{i}, y)} $为邻居节点$ {m}_{i} $对节点j的直接信任值；$ \iota $、$ (1-\iota ) $分别为$ {T}_{\mathrm{S}\mathrm{E}}^{(i, {m}_{i})} $和$ {T}_{\mathrm{S}\mathrm{E}}^{({m}_{i}, y)} $的权重因子，取值范围为[0, 1]。

对节点的直接信任值和间接信任值加权求和得到综合信任值$ {T}_{\mathrm{S}\mathrm{S}} $：

$ {T}_{\mathrm{S}\mathrm{S}}={\zeta }_{2}{T}_{\mathrm{S}\mathrm{E}}+(1-{\zeta }_{2}){T}_{\mathrm{R}\mathrm{S}} $

(6)

其中：$ {\zeta }_{2} $、$ (1-{\zeta }_{2}) $分别为直接信任值和间接信任值的权重，取值范围为（0，1]。

1.1.3 能量信任值

由于微纳卫星的能量有限，如果不考虑节点剩余能量依旧使其频繁工作，会导致综合信任值较高的节点因耗能过快提前失效，退出网络，因此在建立信任机制时还需要考虑节点的剩余能量。

节点在一次数据转发的过程中所消耗的总能量$ {E}_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}} $，如式（7）所示：

$ {E}_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}}=2{E}_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}\cdot N+{E}_{\mathrm{a}\mathrm{m}\mathrm{p}}\cdot N{d}^{2} $

(7)

其中：$ {E}_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}} $为节点在接收1 bit数据所耗费的能量；N为节点收发数据分组的总比特数；$ {E}_{\mathrm{a}\mathrm{m}\mathrm{p}} $为节点数据收发为满足信噪比耗费的能量；d为两节点之间的距离。

微纳卫星节点完成传输后剩余能量$ {E}_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}} $，如式（8）所示：

$ {E}_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}={E}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{a}\mathrm{l}}-{E}_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}} $

(8)

其中：$ {E}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{a}\mathrm{l}} $为节点未参与数据传输时的剩余能量。

微纳卫星节点当前剩余能量百分比$ {E}_{\mathrm{p}\mathrm{e}\mathrm{r}} $如下：

$ {E}_{\mathrm{p}\mathrm{e}\mathrm{r}}=\frac{{E}_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}}}{{E}_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{r}\mathrm{e}}}\times 100\mathrm{\%}, {E}_{\mathrm{p}\mathrm{e}\mathrm{r}}\in \left[\mathrm{0, 1}\right] $

(9)

其中：$ {E}_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{r}\mathrm{e}} $为节点初始能量。

1.1.4 整体信任值

整体信任值$ {T}_{\mathrm{T}} $是将综合信任值和能量信任值进行加权求和得到，其计算公式如式（10）所示。计算过程如图 3所示。

$ {T}_{\mathrm{T}}={T}_{\mathrm{S}\mathrm{S}}\times \left(1-{T}_{\mathrm{S}\mathrm{S}}\right)+{E}_{\mathrm{p}\mathrm{e}\mathrm{r}}\times {T}_{\mathrm{S}\mathrm{S}} $

(10)

1.2 QoS度量参数

假设p为一条从源节点o到目的节点r的路径，$ {e}_{i, j} $为路径p上的一条链路，s为路径p上的节点，则表示整个路径QoS的指标如下：

1）时延。路径p处理时延$ \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}\left(p\right) $为该路径上链路的传输时延$ \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}\left({e}_{i, j}\right) $与节点处理时延$ \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}\left({s}_{i}\right) $之和：

$ \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}\left(p\right)=\sum\limits_{{e}_{i, j}\in p}delay\left({e}_{i, j}\right)+\sum\limits_{{n}_{i}\in p}delay\left({s}_{i}\right) $

(11)

2）出错率。路径p的出错率$ \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left(p\right) $由该路径上所有链路的出错率$ \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left({e}_{i, j}\right) $共同决定：

$ \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left(p\right)=1-\prod _{{e}_{i, j}\in p}(1-\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left({e}_{i, j}\right)) $

(12)

3）跳数。路径p的跳数$ \mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}\left(p\right) $为该路径上所有节点的数量之和：

$ \mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}\left(p\right)=\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{s}\left({n}_{i}\right), {n}_{i}\in p $

(13)

4）带宽。路径p的带宽$ \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}\left(p\right) $为该路径上所有链路中带宽最小的链路的带宽值：

$ \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}\left(p\right)=\underset{{e}_{i, j}\in p}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}\right(e\left)\right\} $

(14)

1.3 节点负载情况

为避免网络中部分节点出现负载过高的问题，需要考虑节点的负载情况，定义节点i的负载为$ {L}_{i} $，假设节点i的通信范围内共有n个节点，则$ {L}_{\mathrm{a}\mathrm{v}\mathrm{e}} $为节点i通信范围内的平均负载。

$ {L}_{i}=\sum\limits_{x=1}^{m}q\left(x\right) $

(15)

$ {L}_{\mathrm{a}\mathrm{v}\mathrm{e}}=\frac{\sum\limits_{i=1}^{n}{L}_{i}}{n} $

(16)

其中：$ q\left(x\right) $为节点i在某时刻待发送的数据队列长度；m为节点i处共有m组数据包等待发送。

1.4 链路持续时间

由于微纳卫星具有一定的移动性，会出现链路中断的问题，因此在选择从源节点到目的节点的路径时，还需要考虑路径中链路的可持续时间，尽量选取链路持续时间长的路径，减少因数据传输过程中出现链路中断而造成数据丢失的现象。

在路径p中存在相邻的节点i和节点j，节点i的空间坐标为$ ({x}_{i}, {y}_{i}, {z}_{i}) $，速度向量$ {\mathit{v}}_{i}={v}_{ix}, {v}_{iy}, {v}_{iz} $，节点j的空间坐标为$ ({x}_{j}, {y}_{j}, {z}_{j}) $，速度向量$ {\mathit{v}}_{j}={v}_{jx}, {v}_{jy}, {v}_{jz} $，则两节点间距离d为：

$ d=\sqrt{({x}_{i}-{x}_{j}{)}^{2}+({y}_{i}-{y}_{j}{)}^{2}+({z}_{i}-{z}_{j}{)}^{2}} $

(17)

设置节点间的最大通信范围为R，当两节点之间的距离$ d\le R $时，两节点可以正常通信；当节点间的距离$ d > R $时，节点不在通信范围内，两节点之间的链路发生断裂。根据两节点之间的坐标位置和速度的移动方向，计算出路径p中链路$ {e}_{i, j} $的预计可存活时间$ t\left({e}_{i, j}\right) $：

$ \begin{array}{l} \varepsilon = \left\{ {{{[2({x_i} - {x_j})({v_{ix}} - {v_{jx}}) + 2({y_i} - {y_j})({v_{iy}} - {v_{jy}}) + 2({z_i} - {z_j})({v_{iz}} - {v_{jz}})]}^2} - } \right.\\ \;\;\;\;\;\;{\left. {4[{{({v_{ix}} - {v_{jx}})}^2} + {{({v_{iy}} - {v_{jy}})}^2} + {{({v_{iz}} - {v_{jz}})}^2}\left] {} \right[{d^2} - {R^2}]} \right\}^{\frac{1}{2}}} \end{array} $

(18)

$ t\left({e}_{i, j}\right)=\frac{-2({x}_{i}-{x}_{j})({v}_{ix}-{v}_{jx})-2({y}_{i}-{y}_{j})({v}_{iy}-{v}_{jy})-2({z}_{i}-{z}_{j})+\epsilon }{2\left[\right({v}_{ix}-{v}_{jx}{)}^{2}+({v}_{iy}-{v}_{jy}{)}^{2}+({v}_{iz}-{v}_{jz}{)}^{2}]} $

(19)

则依据该路径p中最先断裂的链路，本次路由过程中可使用的存活时间$ {t}_{\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{e}} $为：

$ {t}_{\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{e}}=\underset{{e}_{i, j}\in p}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{t\right({e}_{i, j}\left)\right\} $

(20)

2 Q学习量子蚁群路由算法

本文综合考虑路径平均信任值和路径费用两个优化目标，并将量子计算引入到蚁群算法的状态转移概率计算，同时将蚁群算法中的信息素映射成Q学习中的Q值，以提高路由的整体性能。

2.1 多目标函数的建立

为能够同时保证数据传输的安全性和网络业务服务质量，把路径的平均信任值和路径的费用作为两个优化目标，共同构成最优路径的节点性能指标。

路径的平均信任值是反映数据传输安全性的情况，路径的平均信任值越大，数据传输安全性越高。以路径上节点的信任值计算出路径平均信任值作为第一个目标函数$ {f}_{1}\left(p\right) $，则具有hops跳的路径平均信任值如式（21）所示：

$ {f}_{1}\left(p\right)=\frac{\sum\limits_{i=1}^{{h}_{\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}}}{T}_{\mathrm{T}}^{(i, j)}}{{h}_{\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}}} $

(21)

其中：$ {T}_{\mathrm{T}}^{(i, j)} $为路径（i，j）上各节点的整体信任值。

路径的费用函数是反映所建立的路径对于各项QoS参数的满足情况，费用值越小，所建立路径的QoS指标越好。在微纳卫星网络中，多QoS路由问题的设计目标就是找到一条或多条满足以下约束条件的路径，使得路径p的费用值$ f\left(p\right) $最小。本文以路径的费用作为第二个目标函数$ {f}_{2}\left(p\right) $，为了保证计算时各参数单位的统一性，对各项QoS参数进行归一化处理。

$ \left\{\begin{array}{l}\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}\left(p\right) < \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\\ \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left(p\right) < \mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\\ \mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}\left(p\right) < \mathrm{h}\mathrm{o}\mathrm{p}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\end{array}\\ \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}\left(p\right) > \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}}\end{array}\right. $

(22)

$ \left\{\begin{array}{l}\begin{array}{l}\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}{\left(p\right)}^{\mathrm{*}}=\frac{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}\left(p\right)}{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_{\mathrm{m}\mathrm{a}\mathrm{x}}}\\ \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}{\left(p\right)}^{\mathrm{*}}=\frac{\mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}\left(p\right)}{\mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}}}\\ \mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}{\left(p\right)}^{\mathrm{*}}=\frac{\mathrm{h}\mathrm{o}\mathrm{p}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}\left(p\right)}{\mathrm{h}\mathrm{o}\mathrm{p}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}}}\end{array}\\ \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}{\left(p\right)}^{\mathrm{*}}=\frac{\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}{\mathrm{h}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}\left(p\right)}{\mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\end{array}\right. $

(23)

$ {f}_{2}\left(p\right)= \\ \frac{{\omega }_{1}\times \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}{\left(p\right)}^{\mathrm{*}}+{\omega }_{2}\times \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}{\left(p\right)}^{\mathrm{*}}+{\omega }_{3}\times \mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}{\left(p\right)}^{\mathrm{*}}}{{\omega }_{4}\times \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}\mathrm{h}\left(p\right)} $

(24)

其中：$ \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}{\mathrm{y}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为业务可以容忍的最大时延；$ \mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为业务能接受的最大出错率；$ \mathrm{h}\mathrm{o}\mathrm{p}{\mathrm{s}}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为业务可以接受的最大跳数限制；$ \mathrm{b}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{w}\mathrm{i}\mathrm{d}\mathrm{t}{\mathrm{h}}_{\mathrm{m}\mathrm{i}\mathrm{n}} $为业务可以承受的最小带宽；$ \mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}{\left(p\right)}^{\mathrm{*}} $、$ \mathrm{l}\mathrm{o}\mathrm{s}\mathrm{s}{\left(p\right)}^{\mathrm{*}} $、$ \mathrm{h}\mathrm{o}\mathrm{p}\mathrm{s}{\left(p\right)}^{\mathrm{*}} $分别为归一化处理后的QoS参数；$ {\omega }_{1}\mathrm{、}{\omega }_{2}\mathrm{、}{\omega }_{3}\mathrm{、}{\omega }_{4} $分别为时延、出错率、跳数、带宽的加权因子。

2.2 量子计算

量子计算^[16-17]基本原理为：量子态由若干基本状态组成，这些基本状态可以进行叠加形成量子叠加态，当量子叠加态的相对位置和概率幅度方式变化时，就会使基本状态的出现概率也产生相应的变化，从而使原本形成的叠加态也产生对应的形态改变。量子计算具备叠加、并行和干涉的特性^[18]。

2.2.1 量子比特

量子比特^[19]是量子计算中存储信息的基本单元，使用$ |0 > $和$ |1 > $来表示微观粒子的两种基本状态，记号“$ |\mathrm{ } > $”为Dirac记号，在量子计算中抽象为形态。与经典的比特不同，量子比特还可以形成叠加态，可以表示两种状态之间的中间态，即$ |\phi > =\alpha |\mathrm{ }0 > +\beta |\mathrm{ }1 > $，其中$ \alpha $、$ \beta $为复数，表示两种状态的概率幅，且满足归一化条件$ {\left|\alpha \right|}^{2}+{\left|\beta \right|}^{2}=1 $，即量子态$ |\phi > $在测量时会以$ {\left|\alpha \right|}^{2} $的概率转换到$ |0 > $态或以$ {\left|\beta \right|}^{2} $的概率转换到$ |1 > $态。

一个量子比特可以同时存储$ |0 > $和$ |1 > $两种状态的概率幅，那么包含m个量子比特的个体$ {p}_{i} $能够存储$ {2}^{m} $种不同状态，$ {p}_{i} $的概率幅度如式（25）所示：

$ {p}_{i}=\left[\left.\begin{array}{c}{\alpha }_{1}\\ {\beta }_{1}\end{array}\right|\left.\begin{array}{c}{\alpha }_{2}\\ {\beta }_{2}\end{array}\right|\left.\begin{array}{c}\cdots \\ \cdots \end{array}\right|\begin{array}{c}{\alpha }_{m}\\ {\beta }_{m}\end{array}\right] $

(25)

2.2.2 量子旋转门

在量子计算中使用量子旋转门更新量子比特的概率幅，其更新方式如式（26）所示：

$ \left[\begin{array}{c}{\alpha }_{ij}^{t+1}\\ {\beta }_{ij}^{t+1}\end{array}\right]=\left[\begin{array}{c}\mathrm{c}\mathrm{o}\mathrm{s}{\theta }_{ij}\\ \mathrm{s}\mathrm{i}\mathrm{n}{\theta }_{ij}\end{array}\begin{array}{c}-\mathrm{s}\mathrm{i}\mathrm{n}{\theta }_{ij}\\ \mathrm{c}\mathrm{o}\mathrm{s}{\theta }_{ij}\end{array}\right]\left[\begin{array}{c}{\alpha }_{ij}^{t}\\ {\beta }_{ij}^{t}\end{array}\right] $

(26)

其中：$ [{\alpha }_{ij}^{t}, {\beta }_{ij}^{t}] $为第t次迭代中节点i到节点j之间路径上量子比特的概率幅；$ {\theta }_{ij} $为路径上节点i到节点j的量子比特的旋转角度。

量子比特的旋转角度$ {\theta }_{ij} $如下：

$ {\theta }_{ij}=\mathrm{\Delta }{\theta }_{ij}\times s({\alpha }_{ij}, {\beta }_{ij}) $

(27)

其中：$ \mathrm{\Delta }{\theta }_{ij} $为旋转角度的大小，表示量子比特从当前状态旋转至目标状态所需要的步长大小；$ s({\alpha }_{ij}, {\beta }_{ij}) $为旋转角的方向。旋转角的大小和方向根据旋转角选择策略查询，如表 1所示^[20]。在表 1中，$ {x}_{ij}=1 $表示从节点i到节点j存在一条解路径，$ \mathrm{b}\mathrm{e}\mathrm{s}{\mathrm{t}}_{ij} $表示记录运算过程中从节点i到节点j的最优解，f（x）为适应性函数，即建立路径的费用函数$ {f}_{2}\left(p\right) $。

2.3 改进的蚁群路由算法

在传统蚁群路由算法地基础上，本文算法将量子计算引入到状态转移概率计算中，以避免陷入局部最优解，而且把蚁群算法中的信息素映射成Q学习中的Q值，加快算法的收敛速度。

2.3.1 状态转移规则

设共有m只蚂蚁随机的分布在不同的节点上，$ {p}_{i, j}^{k}\left(t\right) $表示在t时刻蚂蚁k（k=1，2，…，m）从节点i移动到节点j的状态转移概率为：

$ {p}_{i, j}^{k}\left(t\right)=\left\{\begin{array}{l}\frac{\left[{\tau }_{ij}^{1}{\left(t\right)]}^{\lambda \delta }\right[{\tau }_{ij}^{2}{\left(t\right)]}^{(1-\lambda )\delta }\left[{\eta }_{ij}^{1}{\left(t\right)]}^{\lambda \vartheta }\right[{\eta }_{ij}^{2}{\left(t\right)]}^{(1-\lambda )\vartheta }[{\mu }_{ij}{\left(t\right)]}^{\xi }}{\sum\limits_{s\in \mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}{\mathrm{d}}_{k}}[{\tau }_{is}^{1}{\left(t\right)]}^{\lambda \delta }\left[{\tau }_{is}^{2}{\left(t\right)]}^{(1-\lambda )\delta }\right[{\eta }_{is}^{1}{\left(t\right)]}^{\lambda \vartheta }\left[{\eta }_{is}^{2}{\left(t\right)]}^{(1-\lambda )\vartheta }\right[{\mu }_{is}{\left(t\right)]}^{\eta }}, j\in \mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}{\mathrm{d}}_{k}\\ 0, j\notin \mathrm{a}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}{\mathrm{d}}_{k}\end{array}\right. $

(28)

其中：$ {\tau }_{ij}^{1}\left(t\right) $、$ {\tau }_{ij}^{2}\left(t\right) $分别为2个目标函数时所得到对应边（i，j）的信息素浓度；$ {\eta }_{ij}^{1}\left(t\right) $、$ {\eta }_{ij}^{2}\left(t\right) $分别为2个目标函数时的启发函数，其计算如式（29）、式（30）所示；$ {\mu }_{ij}\left(t\right) $为路径（i，j）上量子信息强度，其计算如式（31）所示；$ \delta $、$ \vartheta $、$ \xi $分别为蚂蚁寻路过程中信息素浓度、启发式因子、量子信息浓度的相对重要程度；$ \lambda =(k-1)/(m-1) $，$ \lambda $为多目标蚁群算法中为不同目标所设置的权重值。

$ {\eta }_{ij}^{1}\left(t\right)={T}_{\mathrm{T}}^{(i, j)} $

(29)

$ {\eta }_{ij}^{2}\left(t\right)=\frac{1}{{d}_{ij}\left(t\right)} $

(30)

其中：$ {d}_{ij}\left(t\right) $为在t时刻节点i与节点j之间的距离；$ {T}_{T}^{(i, j)} $为路径（i，j）的平均信任值。

$ {\mu }_{ij}\left(t\right)=\frac{1}{{\left|{\alpha }_{ij}\right|}^{2}} $

(31)

其中：$ {\left|{\alpha }_{ij}\right|}^{2} $表示从节点i到节点j的路径上量子位的量子态坍缩到$ |0 > $的概率。

2.3.2 信息素更新规则

在全部的蚂蚁完成一次循环之后，蚂蚁路过某路径时信息素浓度会发生变化，路径的信息素浓度越高则越有可能成为最优路径，同时信息素浓度会按照一定的系数挥发。

1）局部信息素更新规则

当每只前向蚂蚁构建完一个可行路径后，对所构建可行路径上的各段链路进行各个目标的局部信息素更新，其计算如下：

$ {\tau }_{ij}^{n}（t+1）=（1-\rho ）{\tau }_{ij}^{n}（t）+{\mathrm{\Delta }}_{n}{\tau }_{ij} $

(32)

$ {\mathrm{\Delta }}_{n}{\tau }_{ij}=\sum\limits_{k=1}^{m}{\mathrm{\Delta }}_{n}{\tau }_{ij}^{k} $

(33)

其中：n为第n个目标函数（n=1，2）；$ 1-\rho (0 < \rho < 1) $为路径上信息素的持久性因子，信息素通过挥发因子$ \rho $持续挥发；$ {\mathrm{\Delta }}_{n}{\tau }_{ij} $为第n个优化目标的信息素浓度增量。计算如式（34）、式（35）所示：

$ {\mathrm{\Delta }}_{1}{\tau }_{ij}^{k}={}^{1}\!\!\diagup\!\!{}_{{{f}_{1}}\left( p \right)}\; $

(34)

$ {\mathrm{\Delta }}_{2}{\tau }_{ij}^{k}=\left\{\begin{array}{l}\frac{\kappa \times {t}_{\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{e}}}{{f}_{2}\left(p\right)}, {E}_{j-\mathrm{p}\mathrm{e}\mathrm{r}} > 0.5\bigcap {L}_{j} < {L}_{\mathrm{a}\mathrm{v}\mathrm{e}}\\ 0.5\times \frac{\kappa \times {t}_{\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{e}}}{{f}_{2}\left(p\right)}, \mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\\ -\frac{\kappa \times {t}_{\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{e}}}{{f}_{2}\left(p\right)}, {E}_{j-\mathrm{p}\mathrm{e}\mathrm{r}} < 0.1\bigcup {L}_{j} > {L}_{\mathrm{a}\mathrm{v}\mathrm{e}}\end{array}\right. $

(35)

其中：$ \kappa $为链路持续时间值的增强系数；$ {t}_{\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{v}\mathrm{e}} $为存活时间；$ {f}_{1}\left(p\right) $、$ {f}_{2}\left(p\right) $为目标函数；$ {E}_{j-\mathrm{p}\mathrm{e}\mathrm{r}} $为节点j剩余能量；$ {L}_{j} $为节点j的负载；$ {L}_{\mathrm{a}\mathrm{v}\mathrm{e}} $为节点i通信范围内的平均负载。

$ {\mathrm{\Delta }}_{n}{\tau }_{ij}^{k} $表示为第n个优化目标的第k只蚂蚁在本轮迭代中遗留在路径（i，j）的信息素量，若蚂蚁k在本次循环中经过路径（i，j），则按式（35）计算，否则为0。

2）全局信息素更新规则

Q学习是一种不基于状态转化模型，使用时序差分求解强化学习问题的方法^[21-22]。本文引入Q学习的思想，强化算法在动态环境中的学习能力，Q值更新规则如式（36）所示：

$ \begin{array}{l}{Q}_{t+1}(s, a)=(1-\chi ){Q}_{t}(s, a)+\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \chi ({r}_{t+1}+\gamma \mathrm{m}\mathrm{a}\mathrm{x}Q({S}_{t+1}, a\left)\right)\end{array} $

(36)

其中：使用$ Q（s, a） $为动作a的累积回报值；$ \chi \in （\mathrm{0, 1}） $；$ \delta $为学习因子；$ {r}_{t+1} $为t+1时刻根据环境状态s选择动作a获得的收益。

将蚁群算法的信息素浓度映射为Q学习的Q值，则蚁群算法中信息素更新规则为：

$ {\tau }_{ij}^{n}(t+1)=(1-\rho ){\tau }_{ij}^{n}\left(t\right)+\rho ({\mathrm{\Delta }}_{n}{\tau }_{ij}（t）+\gamma \mathrm{m}\mathrm{a}\mathrm{x}({\tau }_{ij}^{n}\left(t\right)\left)\right) $

(37)

其中：$ \mathrm{m}\mathrm{a}\mathrm{x}（{\tau }_{ij}^{n}\left(t\right)） $为在t时刻信息素浓度的最大值；$ {\mathrm{\Delta }}_{n}{\tau }_{ij}\left(t\right) $为t时刻到（t+1）时刻后向蚂蚁的全局信息素增量。$ {\mathrm{\Delta }}_{n}{\tau }_{ij}^{k} $计算公式如下：

$ {\mathrm{\Delta }}_{n}{\tau }_{ij}^{k}=\left\{\begin{array}{l}\frac{Q\cdot {\left|{\alpha }_{ij}\right|}^{2}}{B{d}_{k}}\text{，}i, j\mathrm{在}\mathrm{最}\mathrm{优}\mathrm{路}\mathrm{径}\mathrm{上}\\ 0\text{，}\mathrm{其}\mathrm{他}\end{array}\right. $

(38)

其中：Q为释放的信息素浓度；$ B{d}_{k} $为后向蚂蚁走过的节点个数。

2.3.3 算法步骤

本文所提出的Q学习量子蚁群路由算法流程如图 4所示，具体步骤如下：

步骤1  初始化微纳卫星网络，设置源节点o和目的节点r，设定蚁群的蚂蚁数量m，算法的最大迭代次数$ {t}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，并设置算法中的各项参数。

步骤2  设置和初始化各前向蚂蚁的禁忌表，各前向蚂蚁的禁忌表中用于存储当前已经访问过的节点ID，令前向蚂蚁标记k=k+1。

步骤3  各个前向蚂蚁可访问的节点范围内，根据状态转移概率的计算公式选择下一跳邻居节点j。

步骤4  判断选择的邻居节点j的直接信任值是否大于恶意节点门限阈值$ {T}_{\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}} $，若节点j的直接信任值小于恶意节点门限阈值$ {T}_{\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{e}\mathrm{r}} $，则广播通知其他节点将节点j从微纳卫星网络中隔离，并转向步骤3重新选择邻居节点，否则转向步骤5。

步骤5  判断选择下一跳节点j后所形成的链路是否满足QoS需求，若不满足其中的某一项QoS指标则返回步骤3，否则转向步骤6。

步骤6  前向蚂蚁根据状态转移规则选择下一个移动位置后，通过量子旋转门完成自适应的更新。

步骤7  前向蚂蚁k根据不同的目标函数进行相应的局部信息素的更新，并把选择的邻居节点j放入到禁忌表中。

步骤8  循环执行步骤3~步骤7，直到所有的前向蚂蚁到达目的节点并转换为后向蚂蚁。

步骤9  后向蚂蚁进行全局的信息素更新，令迭代次数t=t+1。

步骤10  判断是否满足结束条件$ t > {t}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，若满足则输出最优解，根据算法计算出的最优路径传输数据，否则转向步骤2。

3 实验仿真与结果分析

本文用Matlab仿真验证所提出QQARA算法的性能。微纳卫星的初始拓扑采用铱星星座的分布方式，即共有66颗微纳卫星，6条轨道，并且每个轨道都均匀分布11颗微纳卫星，每颗卫星与其他4颗卫星直接相连接，其仿真参数如表 2所示。

为验证QQARA算法能否满足网络各种不同业务QoS需求，在网络中分别设置对带宽要求敏感的大文件传输业务，对时延要求敏感的实时传输业务和对丢包率要求敏感的下载业务，各种不同业务的QoS参数约束条件如表 3所示。

本文实验将QQARA算法与常见的蚁群优化（Ant Colony Optimization，ACO）算法、改进的QoS（QoS aware Service Selection，QSS）算法^[23]进行对比分析，分别从路径的费用值、包投递率、平均端到端时延、节点的平均能耗4个性能指标验证QQARA算法的有效性。

1）路径的费用值

图 5所示为不同算法随着迭代次数增加时的路径费用变化趋势。随着迭代次数的不断增加，3种算法的路径费用值$ {f}_{2}\left(p\right) $都呈现出不断下降的状态。由于ACO算法只考虑了寻找最短路径而没有QoS参数的问题，因此下降速度最慢且数值最高，而QSS算法和QQARA算法在寻找最优路径时考虑了路径的各项QoS参数，因此这2种算法路径费用值的下降速度和最小值都明显优于ACO算法。由于QQARA算法结合了Q学习的优点，因此QQARA算法的收敛速度最快。

2）包投递率

图 6所示为在不同的节点移动速度下3种算法的包投递率变化情况。随着节点移动速度的增大，3种算法的包投递率均出现了不同程度的下降趋势。由于QQARA算法加入了量子计算，能够很好地跳出局部最优解，具有更好的路径寻优能力，且在信息素浓度更新的过程中考虑了节点的状态以及链路的持续时间，即使在节点具有一定移动速度的情况下仍能保持一定程度的包投递率，因此，所寻找的最优路径更加稳定。

3）平均端到端时延

图 7所示为节点移动速度与平均端到端时延的关系。由图 7可知，随着节点移动速度的逐渐增加，3种算法的平均端到端时延也呈现出了不同程度的上升趋势。QSS算法和QQARA算法在选择下一跳节点时考虑到了节点的状态，减少了因节点失效而导致时延增加的问题。由于QQARA算法加入了对链路持续时间的考虑，减少了因链路中断和路由修复带来的延迟，因此随着节点移动速度的不断增加，QQARA算法的平均端到端时延明显优于QSS算法和ACO算法。

4）节点平均能耗

图 8所示为节点的移动速度与节点平均能耗的关系。随着节点移动速度的增加，3种算法的节点平均能耗均出现上升的趋势。由于ACO算法和QSS算法在选取数据传输路径时没有考虑链路的持续时间，在节点移动而导致链路断开的情况下会产生大量的数据重传，增大了节点的能量消耗，因此该算法的节点平均能耗随着节点移动速度上升而大幅增加。由于QQARA算法加入了对链路连接持续时间的考虑，能够有效减少因链路中断而造成数据重传产生的能耗。同时，在选择路径时考虑到了节点的剩余能量问题，起到了能量均衡的作用。

4 结束语

本文提出一种实现多目标优化的Q学习量子蚁群路由算法。该算法考虑路径平均信任值和路径费用，保证数据传输的安全性和网络业务服务质量，通过加入量子计算避免陷入局部最优解，将信息素映射成Q值，加快算法的收敛速度。仿真结果表明，该路由算法有效地改善了包投递率、平均端到端时延和节点平均能耗等性能指标。下一步将在优化目标中增加影响微纳卫星网络传输因素，提高路由算法对不同场景的适用性。