基于Q 学习量子蚁群的微纳卫星路由算法

张 然，高莹雪，赵 钰，丁元明

（1.大连大学 信息工程学院，辽宁 大连 116622；2.大连大学 通信与网络重点实验室，辽宁 大连 116622）

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={ei，j|i，j∈V}表示微纳卫星网络中的相邻两节点的链路集合，如图1 所示。

图1 微纳卫星网络结构Fig.1 Structure of micro-nano-satellite network

1.1 信任机制的建立

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

1.1.1 直接信任值

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

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

其中：ψ为指数衰减程度；tc、tc-1分别为当前、上一次检测时间；为节点上一个攻击行为的信任值；d(t)L为当前行为评估后量化的值。

其中：r(t)L为节点当前行为正常时的评估值；n(t)L为节点当前行为异常时的评估值。

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

其中：TS为节点成功转发数据包的个数；TF为节点转发失败数据包的个数。

对节点的攻击行为信任值和转发行为信任值加权求和得到直接信任值TSE，如式（4）所示：

其中：ζ1、(1-ζ1)分别为转发行为信任值和攻击行为信任值的权重，取值范围为［0，1］。

设定一个恶意节点门限阈值Tlower，在获得某个节点的直接信任值后，一旦发现该节点的直接信任值低于门限阈值Tlower，则认为该节点为恶意节点，将该节点隔离，门限阈值Tlower具体大小根据具体情况取值。

1.1.2 间接信任值

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

图2 间接信任值计算示意图Fig.2 Schematic diagram of indirect trust value calculation

假设节点i的邻居节点mi连通域为YS，YS中共有n个邻居节点存储有节点j的直接信任值，则可得到i对j的间接信任值TRS计算公式如下：

对节点的直接信任值和间接信任值加权求和得到综合信任值TSS：

其中：ζ2、(1-ζ2)分别为直接信任值和间接信任值的权重，取值范围为（0，1］。

1.1.3 能量信任值

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

节点在一次数据转发的过程中所消耗的总能量Ecost，如式（7）所示：

其中：Eelec为节点在接收1 bit 数据所耗费的能量；N为节点收发数据分组的总比特数；Eamp为节点数据收发为满足信噪比耗费的能量；d为两节点之间的距离。

微纳卫星节点完成传输后剩余能量Ecurrent，如式（8）所示：

其中：Einital为节点未参与数据传输时的剩余能量。

微纳卫星节点当前剩余能量百分比Eper如下：

其中：Eentire为节点初始能量。

1.1.4 整体信任值

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

图3 整体信任值计算过程Fig.3 Calculation process of overall trust value

1.2 QoS 度量参数

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

1）时延。路径p处理时延delay(p)为该路径上链路的传输时延delay(ei，j)与节点处理时延delay(si)之和：

2）出错率。路径p的出错率loss(p)由该路径上所有链路的出错率loss(ei，j)共同决定：

3）跳数。路径p的跳数hops(p)为该路径上所有节点的数量之和：

4）带宽。路径p的带宽bandwidth(p)为该路径上所有链路中带宽最小的链路的带宽值：

1.3 节点负载情况

为避免网络中部分节点出现负载过高的问题，需要考虑节点的负载情况，定义节点i的负载为Li，假设节点i的通信范围内共有n个节点，则Lave为节点i通信范围内的平均负载。

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

1.4 链路持续时间

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

在路径p中存在相邻的节点i和节点j，节点i的空间坐标为(xi，yi，zi)，速度向 量vi=νix，νiy，νiz，节 点j的空间坐标为(xj，yj，zj)，速度向量vj=νjx，νjy，νjz，则两节点间距离d为：

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

则依据该路径p中最先断裂的链路，本次路由过程中可使用的存活时间talive为：

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

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

2.1 多目标函数的建立

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

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

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

其中：delaymax为业务可以容忍的最大时延；lossmax为业务能接受的最大出错率；hopsmax为业务可以接受的最大跳数限制；bandwidthmin为业务可以承受的最小带宽；delay(p)*、loss(p)*、hops(p)*分别为归一化处理后的QoS 参数；ω1、ω2、ω3、ω4分别为时延、出错率、跳数、带宽的加权因子。

2.2 量子计算

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

2.2.1 量子比特

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

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

2.2.2 量子旋转门

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

量子比特的旋转角度θij如下：

其中：Δθij为旋转角度的大小，表示量子比特从当前状态旋转至目标状态所需要的步长大小；s(αij，βij)为旋转角的方向。旋转角的大小和方向根据旋转角选择策略查询，如表1 所示［20］。在表1 中，xij=1 表示从节点i到节点j存在一条解路径，bestij表示记录运算过程中从节点i到节点j的最优解，f（x）为适应性函数，即建立路径的费用函数f2(p)。

表1 旋转角选择策略Table 1 Rotation angle selection strategy

2.3 改进的蚁群路由算法

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

2.3.1 状态转移规则

设共有m只蚂蚁随机的分布在不同的节点上，表示在t时刻蚂蚁k（k=1，2，…，m）从节点i移动到节点j的状态转移概率为：

其中：dij(t)为在t时刻节点i与节点j之间的距离；为路径（i，j）的平均信任值。

其中：|αij|2表示从节点i到节点j的路径上量子位的量子态坍缩到|0>的概率。

2.3.2 信息素更新规则

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

1）局部信息素更新规则

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

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

其中：κ为链路持续时间值的增强系数；talive为存活时间；f1(p)、f2(p)为目标函数；Ej-per为节点j剩余能量；Lj为节点j的负载；Lave为节点i通信范围内的平均负载。

2）全局信息素更新规则

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

其中：使用Q（s，a）为动作a的累积回报值；χ∈（0，1）；δ为学习因子；rt+1为t+1 时刻根据环境状态s选择动作a获得的收益。

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

其中：Q为释放的信息素浓度；Bdk为后向蚂蚁走过的节点个数。

2.3.3 算法步骤

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

图4 Q 学习量子蚁群路由算法流程Fig.4 Procedure of Q-learning quantum ant colony routing algorithm

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

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

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

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

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

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

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

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

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

步骤10判断是否满足结束条件t>tmax，若满足则输出最优解，根据算法计算出的最优路径传输数据，否则转向步骤2。

3 实验仿真与结果分析

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

表2 仿真参数Table 2 Simulation parameters

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

表3 不同业务的QoS 约束条件Table 3 QoS constraints for different services

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

1）路径的费用值

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

图5 迭代次数与路径费用的关系Fig.5 Relationship between iteration times and path cost

2）包投递率

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

图6 节点移动速度与包投递率的关系Fig.6 Relationship between node movement speed and packet delivery rate

3）平均端到端时延

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

图7 节点移动速度与平均端到端时延的关系Fig.7 Relationship between node moving speed and average end-to-end delay

4）节点平均能耗

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

图8 节点移动速度与节点平均能耗的关系Fig.8 Relationship between node moving speed and node average energy consumption

4 结束语

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