QKD网络存在两条信道，一条是经典信道，另一条是量子信道，两者相互配合实现量子保密通信。经典信道主要传输控制信息、路由信息、数据等。而量子信道则是传输量子载体，使得相邻的可信中继通过BB84^[17]协议产生量子安全密钥。由于量子加密通信的关键是解决量子密钥传输的安全性问题，因此本文只考虑量子信道。

基于可信中继的QKD网络是指由一组可信节点组成的网络，由用户发起安全通信的请求，可信节点负责传输安全密钥。基于可信中继的QKD网络只要保证节点是安全的、可以信任的，其网络的安全性就可以得到保证。因此本文只需考虑信道传输的安全性。

由于每条量子链路的剩余密钥量随着密钥生成量和密钥消耗量的变化而变化。因此，为确保剩余密钥量的充足性和选路的成功率，每次进行路由选择前需着重考虑密钥量的变化，优先选择剩余密钥量足够大的链路，而将路径长度放在相对次要的位置。因此，如何计算链路剩余密钥量的动态变化是关键。

在量子通信网络中，为保证所选链路密钥量的充足，本文采用节点对链路的贡献率${\lambda _{{e_{i,j}}}}$反映剩余密钥量的动态变化过程，优先选择贡献率最大，即一次密钥交换后，剩余密钥量增加最多的链路，使得每条链路中的密钥量保持一种均衡的状态。节点对链路的贡献率为：

式中，${\lambda _{{e_{i,j}}}}$表示节点对路由选择的贡献率；${G_{{e_{i,j}}}}$表示时间t内量子链路的密钥生成量；${C_{{e_{i,j}}}}$表示时间t内量子链路的密钥消耗量。当${\lambda _{{e_{i,j}}}} > 1$时，表示密钥交换后，该条量子链路的密钥生成量大于密钥消耗量，剩余密钥量增加；当${\lambda _{{e_{i,j}}}} < 1$时，表示该条量子链路的密钥生成量小于密钥消耗量，剩余密钥量减少。

在量子通信网络中，除了考虑节点的贡献率以外，还应考虑密钥池中密钥的新鲜度，因为密钥量是动态变化的，所以路由选择必须考虑每条链路当前的密钥量。本文通过密钥池的最大容量和剩余密钥量计算新鲜度：

式(2)表明，剩余密钥量越多，则${\theta _{{e_{i,j}}}}$的值越小，新生成的密钥越多，密钥的新鲜度越高。反之，剩余密钥量越少，则${\theta _{{e_{i,j}}}}$的值越大，新生成的密钥越少，密钥的新鲜度越低。

为了准确选择出负载均衡的最优多路由，本文综合考虑节点的贡献率和密钥的新鲜度，设计了一种能够充分反映剩余密钥量动态变化的链路成本函数：

式中，${e_{i,j}}$表示链路${e_{i,j}}$在前一次路由选择时是否被选择，初始化为0，被选择则置为1。以此保证每条链路都有相同的机会被选择，避免重复选择之前已经选择的链路。

整条路径的链路成本函数为：

与单路径路由算法在传输过程中密钥被窃听则需重新寻找安全路径不同的是，多路径路由算法通过多条路径传输信息，只有每条路径上的密钥都被窃听，才需重新寻找路径，因此提高了攻击者的窃听困难度，保证了网络传输的安全性。但是与经典网络的多路径路由算法不同的是，量子保密传输中的信息是通过量子密钥进行“一次一密”的形式加密传输的，因此，链路中的量子密钥的动态变化量是路由选择的关键因素。

本文为提高密钥交换的成功率，保证信息传输的安全性，提出了多路径路由算法(multi- routing algorithm)。其基本思想是，密文在进行传输选择路径时，除了考虑路径跳数，把链路中的剩余密钥量、每个路由节点的密钥生成量和传输需消耗的密钥量作为衡量指标，通过链路成本函数计算出每条链路的权重。然后采用基于堆优化的Dijkstra算法计算最优路径，删除该路径上的链路后继续计算次优路径，最后分析当路径总数$d$不足$n$条时，判断$d$条路径上的每条链路的剩余密钥量是否足量，若不足，则令$n$为$d$，重新进行路由选择；若足量，则无需重新进行路由选择。因此，可得到从源点到指定终点的多条最优路径。伪代码算法如下所示：

算法1　多路径路由算法

输入：多路径的条数$n$，每条链路的剩余密钥量${R_{{e_{i,j}}}}$，密钥生成量${G_{{e_{i,j}}}}$，全局密钥的总量$p$

输出：$n$条最优路径的详细信息。

1)　遍历$G$中的每条量子链路${e_{i,j}}$

2) ${p_n} \leftarrow p/n$

3)　　if $ {R_{{e_{i,j}}}} < {p_n} $:

4)　　　delete 链路${e_{i,j}}$

5)　　$ w \leftarrow 1/\cos {\rm t}$

6)　$ d \leftarrow 0 $

7)　while $ d < n $ do

8)　　将与源点相连的点加入堆，并调整堆

9)　　选堆顶元素$u$($w$最小)，从堆中删除，并调整堆

10)　　while $v$与$u$相邻，未被访问且${\rm {dist}}[u] + \cos {\rm t}$$[e] < {\rm {dist}}[v]$ do

11)　　　if $v$在堆中

12)　　　　更新${\rm {dist}}[u]$，并调整$v$在堆的位置

13)　　　else

14)　　　　堆中添加$v$，并更新堆

15)　　　end if

16)　　end while

17)　　if $ u = = $终点

18)　　　$ d \leftarrow d + 1 $

19)　　　output最优路径

20)　　　$G$中删除最优路径的每条链路，更新$G$

21)　　else

22)　　　重复步骤9)、10)

23)　　end if

24)　end while

25)　if $ d < n$

26)　　遍历$G$中的每条量子链路${e_{i,j}}$

27)　　$ {p_n} \leftarrow p/d $

28) if $ {R_{{e_{i,j}}}} < {p_n} $:

29)　　　$n \leftarrow d $

30)　　　继续从步骤3)开始执行

31)　　end if

32) end if

本算法理论上的运行时间为$O(n(\log |V|(|V| + |E|)))$，相对于经典的Dijkstra算法访问所有节点的时间复杂度为$O(n(|V||V|))$，大大减少了计算次数与比较次数，在一定程度上提高了运算速度。

在数据存储方面，multi-routing算法采用图论中的邻接表的链式存储结构，对于一个无向图来说，其存储量为$O(|E| + 2|V|)$。此外，还使用了两个数组，第一个数组$C[V]$表示求得的从源点到其他所有节点的最短路径值。第二个数组用来暂存待选择的链路。所以，总的空间复杂度为$O(2|E| + 3|V|)$。而采用邻接矩阵存储方法的经典Dijkstra算法的空间复杂度为$O(|V||E|)$。相比较而言，明显节省了空间，提高了存储效率。

在量子保密通信过程中需要两种类型的量子密钥，分别是量子局部密钥和量子全局密钥。量子局部密钥是由两个可信中继节点通过BB84协议产生并分别存储在双方的密钥池，主要是对量子全局密钥的加密和解密，实现全局密钥在相邻节点间的传输。量子全局密钥是由不相邻的可信中继节点通过一系列相邻节点的密钥交换得到的无条件安全的量子密钥，主要是为通信双方提供安全的密钥。

为了保证量子全局密钥在多路径上传输的安全性，以及避免使用过多的量子密钥，提出了量子密钥分块的思想，如图1所示。

图  1  密钥分块示意图

首先，根据一次密文传输的长度确定量子全局密钥的长度L，根据传输的多路径条数确定等分的次数$n$；然后，将量子全局密钥$n$等分，分别分配给$n$条最优路径，并标记分配顺序；将分配的顺序通过经典网络转发给接收端，同时分别将$1/n$份的全局密钥传输到接收端；最后，接收端按照密钥分配的顺序将$n$条路径传输的密钥组合成全局密钥。

在单条路径上使用量子密钥加密时，当利用诱饵状态^[18]检测到一段中继链路被窃听者攻击，则全局密钥被泄露，需重新生成全局密钥，浪费宝贵的密钥资源；而在多条路径上使用量子密钥加密密文，除非每条路径上全部检测到窃听者的攻击，则全局密钥被泄露，需重新传输，否则，经过路径传输的密钥都是安全的，无需重新传输。但每次传输需要占用多条量子信道，使用的密钥量较多。为了实现传输的高效性，同时充分利用链路资源，并保证密钥的安全性，本文提出了基于多路径的密钥传输算法，算法步骤如下：

算法2　基于多路径的密钥传输算法

输入：$n$条路径的链路信息

输出：接收端共享的全局密钥。

1) 发送端获取$n$条路径的链路信息，将全局密钥$n$等分给$n$条路径，并记录分配顺序Order。

2) 每条路径接收到发送端分配的密钥key后，路径中的可信中继节点A制备量子序列SA发送给相邻节点B，B制备随机的二进制比特作为测量基，将对SA测量后的结果制备量子序列SB。B通过经典信道告知A所选取的对应每个量子的测量基。双方进行比对后，若误码率超过阈值，则表示存在窃听，此次通信终止，否则，A和B将用于检测而剩下的量子序列作为安全的局部密钥。

3) A和B利用局部密钥对key进行“加密−解密”的密钥交换方法，将key传递给路径中的下一对相邻节点，节点对继续按照步骤2)生成局部密钥，按步骤3)传输$1/n$份的全局密钥key。

4) 如果接受端接收到$n$条路径传输的密钥key，则算法停止，否则，继续重复步骤2)～3)。

5) 接收端按照密钥分配的顺序Order，将$n$个密钥key组合成完成的全局密钥Key。

根据2.2节提出的基于多路径的密钥传输算法，以3条路径为例，进一步说明基于可信中继的多路径密钥传输的过程。如图2所示，3条路径分别为：${\rm {Alice}} \to {R1} \to {R2} \to {\rm {Bob}}$；${\rm {Alice}} \to {R3} \to {\rm {Bob}}$；${\rm {Alice}} \to {R4} \to {R5} \to{\rm { Bob}}$。

安全的多路径密钥传输步骤为：

1) Alice方将全局密钥三等分，确定等分密钥的长度L；

2) Alice方与中继$R1$，Alice方与中继$R3$，Alice方与中继$R4$，中继$R1$与中继$R2$，中继$R2$与Bob方，中继$R3$与Bob方，中继$R4$与中继$R5$，中继$R5$与Bob方，分别产生一对局部密钥$K1$,$K2$,$K3$,$K4$,$K5$,$K6$,$K7$,$K8$，将$K1$+$K2$+$K3$组合作为全局密钥。

图  2  多路径密钥传输过程

3) 将密钥$K1$，$K2$，$K3$分别沿着3条路径进行密钥交换。例如，密钥$K1$在可信中继$R1$中使用局部密钥$K2$进行加密，并将结果发送给可信中继$R2$。$R2$使用局部密钥进行解密得到密钥$K1$。按照上述加密解密操作，分别将密钥$K1$，$K2$，$K3$传送给Bob。

4) Bob按照路径传输顺序将密钥$K1$，$K2$，$K3$组合成安全的全局密钥。

本文采用的基于可信中继的量子通信网络的拓扑结构是由25个中继节点组成的$5 \times 5$经典格型拓扑^[19]，如图3所示。

图  3  量子网络格型拓扑结构

设密钥池中密钥的最大容量为$10\;{\rm {Mb}}$；密钥池中的密钥量定期更新，密钥生成量为$10\sim 20\;{\rm {Kb/s}}$；设置密钥池初始密钥量为$600\;{\rm {Kb}}$，第一次密钥交换时，密钥池的剩余密钥量等于初始密钥量。在所有实验过程中，假定两个用户之间进行通信所需密钥量为$768\;{\rm {Kb}}$，那么在选择出3条路径的情况下，每条路径上的中继节点的密钥量不少于$256\;{\rm {Kb}}$；在选择两条路径的情况下，每条路径上的中继节点的密钥量不少于$384\;{\rm {Kb}}$。

多路径路由算法首先需要确定最佳路由的条数。为了确定最佳路径条数($n$)的取值，在选定的格型拓扑中进行了600次实验，统计选出的路径条数$n$，实验结果如表1所示。

由表1可知，选出最佳路径条数为3条的情况所占比例最多。因而，为了减少重新选择路径的次数，可以确定$n$的取值为3。即在路径足够多的情况下，在两个用户之间选出3条最佳路由是最合理的。

密钥交换成功率越高，说明所选择的路由算法越好。因此，密钥交换的成功率是衡量路由选择算法的一个重要指标。在相同环境下，本文算法与文献[9]的单路径算法、随机路由算法的密钥交换成功率的对比实验结果如图4所示。本次实验采用节点M作为一次密钥交换的源节点，每次随机选择其他节点作为目的节点。因此，节点M需要记录密钥交换的次数和每次密钥交换的结果，并每隔$5\min $计算密钥交换的成功率。

从图4中可以看出，本文提出的multi-routing算法密钥交换成功率最高，是因为单路径算法对路径上的密钥量需求量大，随机路由算法随机选择路径，可能导致所需密钥量不足，而multi-routing算法却将对单条路径密钥量的需求均匀分配给多条路径。另外由于可信中继节点初始密钥的消耗和局部密钥的生成，导致密钥交换的成功率降低，故整体的密钥交换成功率随着网络运行时间的增加而逐渐降低。

图  4  密钥交换的成功率

量子通信链路中密钥交换过程的失败主要是由于链路中密钥量不足。但也并不是说，链路剩余密钥量越多越好，因为剩余密钥量越多，造成的浪费也越严重，而应该是分布的越均匀越好。因此，QKD链路中剩余密钥量的分布均匀性也是一个衡量密钥分发网络的重要指标。

图  5  链路平均剩余密钥量

在量子密钥分发网络中，每条链路都记录每次密钥交换后的剩余密钥量，并在全部密钥交换结束之后计算平均剩余密钥量。本文提出的multi-routing算法与文献[9]的单路径算法、随机路由算法的实验结果分别如图5a、5b和5c所示。

由于multi-routing算法是将全局密钥均分给多条路径进行传输，总体上来说平均剩余密钥量较少，而且分布差异较小，这样将明显减少密钥的浪费情况。而对于文献[9]提出的单路径算法来说，由于只选择一条路径传输全局密钥，故导致其平均剩余密钥量较多，分布出现明显的差异，说明密钥浪费现象比较严重。由于随机路径算法随机选择路径，选择出剩余密钥量不足的链路，导致实验终止，平均之后每条链路的平均剩余密钥量偏低。

通过记录每条链路中的剩余密钥量，并比较每条链路中剩余密钥量的变化趋势，更能直观的反映量子链路的负载变化情况。为此，选择$A - B$,$I - J$, $M - N$这3条量子链路对剩余密钥量的变化趋势进行对比。

由于multi-routing算法综合密钥生成量、消耗量和剩余量计算链路权重，选择多条路径进行传输，保证链路密钥量负载平衡，所以图6a中3条链路的剩余密钥量变化趋势相对平均。但是对于文献[9]的单路径路由算法来说，没有考虑链路的贡献率以及密钥的新鲜度，出现链路间密钥总量相差很大的现象。图6c所示的随机路由算法在800 s时因密钥量不足而使得实验终止，剩余密钥量也不再发生变化。显然，这不是一种好现象，也由此表明，随机路由算法存在弊端。相比较而言，本文提出的multi-routing algorithm更能权衡量子链路中的密钥消耗量和密钥生成量。

图  6  链路平均剩余密钥量

为了建立安全、高效的量子通信网络，本文针对量子通信网络特有的量子密钥安全传输的问题，提出了基于可信中继的多路径密钥分块传输方法。将全局密钥沿3条不同路径进行分块传输，不仅减少了密钥传输的时延，而且提高了基于可信中继长距离通信的安全性。

本文提出的multi-routing算法能够有效提高密钥交换的成功率，并且能够充分权衡密钥生成量和密钥消耗量之间的关系。在选择多条路径时可有效保证网络的负载平衡。除此之外，本文提出的multi-routing算法能保证更高的安全性，对于保密性要求较高的信息传输来说，具有突出的效果。