Research and Design of QKD Network Random Routing Algorithm Based on Backtracking

图1是基于信任中继的QKD网络结构^[5]，网络由用户、信任中继节点和链路3部分组成，信任中继节点之间通过链路连接在一起。由用户发起通信请求，各信任中继节点负责转发密文和密钥，在网络中起中继交换的作用。

信任中继QKD网络中有两条信道，一条是用于传输密钥的量子信道，另一条是用于传输路由信息和加密信息的经典信道。在图1中，实线表示量子信道，是两节点间的直通信道；虚线表示经典信道，可以是两节点间的直连信道，也可以是经由其他节点转接的信道。由于两个信道的传输内容和传输方式都不同，因此量子信道的路由方式不能直接使用经典网络中成熟的路由技术。本文所提及的QKD网络特指由量子信道组成的网络。

信任中继密钥传输原理如图2，假定用户A要和用户B进行密钥传递，中继节点1和中继节点2共享密钥K1，中继节点2和中继节点3共享密钥K2，中继节点3与用户B共享密钥K3。用户A和中继节点1协商出全局密钥K后(通信密钥)，通过中继节点1、2和3传递给用户B。传递过程中，中继节点先解密后加密，如中继节点2从中继节点1接收到K⊕K1，先用与中继节点1共享的K1解密得到K，再用与中继节点3共享的密钥K2加密得到K⊕K2，然后发送给中继节点3。

由于相邻中继节点共享的密钥是通过密钥分发产生的，具有无条件安全性，因而节点之间进行密钥传输时，可以保证密钥不被泄露；又由于中继节点是可以信任的，所以基于信任中继的密钥传递在理论上是安全的。

文献[16]提出一种基于RIP协议的随机路由算法，该算法通过改进基于距离矢量的路由算法扩展路由表，为到达某一目的地址的中继节点添加多个下一跳，进而得到源中继节点到目的中继节点的多条最短路径；在选路时，将链路上的剩余密钥量考虑在内，在存在多个密钥量充足的下一跳中继节点的情况下，在其中随机地选择一个，然后逐跳转发，直到转发至目的中继节点。

虽然该方法路径最短且安全性较高，但仍然存在以下不足：1) 只适用于源节点和目的节点之间有多条最短路径的情况，如果源、目的节点之间只有一条最短路径，该算法就会失效；2) 在选中密钥量不足的下一跳节点时就将中断传输，按新的最短路径从头开始密钥协商，浪费资源且成功率较低。

针对该随机路由算法的不足，本文将路由算法进行改进，并提出一种基于回溯的QKD网络随机路由选择方案。

针对文献[16]不适用于源、目的节点之间只有一条最短路径的问题，本文提出一种寻找两个节点之间多条路径的方法：1) 采用文献[6]改进的Dijkstra算法找到源节点到目的节点的所有最短路径；2) 判断最短路径的条数：如果路径条数少于3，就在网络中删除当前的最短路径，继续找最短路径，直到找到3条最短路径；如果路径条数不少于3，就从中随机选择3条最短路径；3) 将选出的3条路径加入路由表中。

本文提出的随机路由算法的思想是：从源节点开始进行寻路，在当前节点与目的节点存在多条传输路径时，查看链路上的剩余密钥量，在剩余密钥量足够的所有链路中随机选择一条，逐跳选择中继节点来转发密钥。当选择的节点不存在密钥量足够的链路时，判断该节点是否存在可回溯的中继节点。如果存在，就回溯；如果不存在，结束通信，重新开始协商密钥。

为了找到可回溯的中继节点，本文设计一种标记回溯点的方法。在路由表中添加一个新项——回溯点，用于标记该节点的回溯点。即，如果所选路径中某节点的链路密钥量不足，此节点就查找其回溯点。如果存在，就回溯到该点；如果不存在，就结束此次密钥协商。标记回溯点的算法步骤如下：

1) 初始情况下，路由表中每一项的回溯点均为空；2) 从源中继节点开始，判断当前节点到目的节点的下一跳个数：如果个数为1，将下一跳的回溯点标记为当前节点的回溯点的值；如果个数大于1，将多个下一跳的回溯点标记为当前节点。

图3是一个简单的例子，如果Alice要与Bob通信，计算得到3条最短路径：P1：1→2→3→4；P2：1→2→5→4；P3：1→8→6→4。所以，节点2,8的回溯点为1；节点3,5的回溯点为2。

各节点的路由表如表1～表6所示。

本文提出的随机路由选择的算法步骤为：

1) 找到源中继节点到目的中继节点的3条最短路径，并将下一跳信息添加到路由表；

2) 相邻中继节点利用量子密钥分发协议协商出量子密钥K，并存储；

3) 源量子通信终端与其相连的中继节点(源节点)协商出本次通信的通信密钥Kc；

4) 从源节点出发，首先对收到的密文进行解密，然后根据目的地址查找路由表，判断路由表中到此次协商的目的地址的下一跳个数N(如果是回溯到此节点，则去掉选路失败的下一跳)：

① 如果N=1，执行步骤②；如果N>1，执行步骤③；

② 判断下一跳相邻中继节点中存储的量子密钥的比特数是否大于通信密钥的比特数。若是，将通信密钥加密后转发至下一跳相邻中继节点，执行步骤④，否则，执行步骤5)；

③ 将收到的密钥存储，然后在N个下一跳相邻中继节点中选出量子密钥的比特数大于通信密钥的比特数的中继节点，并在其中随机地选取一个，然后将通信密钥加密后转发至该相邻中继节点，执行步骤④；对于多个下一跳相邻中继节点中存储的量子密钥的比特数均小于通信密钥的比特数的情况，执行步骤5)；

④ 对选取的相邻节点标记回溯点，该节点收到加密后的通信密钥，利用存储的量子密钥对其进行解密，并判断当前中继节点是否为目的中继节点。若是，则源中继节点与目的中继节点端到端的通信密钥建立成功，源中继节点利用该通信密钥Kc对数据加密进行传输；否则，根据目的地址查找路由表，返回步骤①；

5) 查找该节点的回溯点，判断回溯点是否存在：

① 如果存在，通知回溯点本路径通信失败，回溯点执行步骤4)；② 如果不存在，此次密钥协商失败，执行步骤6)；

6) 释放源量子通信终端与目的量子通信终端间的连接。

以图4为例，假设此次通信所需密钥为10，图中链路上的数字代表路径上剩余密钥量。首先，寻找节点1到节点5之间的所有最短路径，找到1条最短为：1-2-6-5。由于当前路径条数少于3，继续寻找节点1到节点5之间的所有最短路径，找到的结果为：1-10-3-4-5，1-2-3-4-5和1-9-8-7-5，至此，获得3条最短路径。随机选择其中的2条，假定选择的结果为：1-2-3-4-5，1-9-8-7-5。再加上之前选择的1条最短路径：1-2-6-5，则获得3条最短路径：1-2-6-5，1-2-3-4-5，1-9-8-7-5。

路由选择过程如下：

1) 从源节点1开始，查找路由表，得到的到达节点5的路径有两条，由于两条链路的密钥量都充足，因而随机选择下一跳，假设选择节点2；

2) 由于从节点1经节点2到节点5有多条路径，因而将节点2的回溯点标记为1；

3) 从节点2开始，进一步查找路由表，得到的到达节点5的路径有两条，分别为节点3和节点6，由于两条链路的密钥量都充足，因而随机选择下一跳节点，假定选择节点6；

4) 由于从节点2经节点6到节点5有多条路径，因而将节点6的回溯点标记为节点2；

5) 从节点6开始进一步查找路由表，得到的到达节点5的下一跳节点即为节点5。但链路6-5的密钥量不足，因而回到它的回溯点，即节点2；

6) 从节点2开始，去掉选路失败的下一跳节点6，进一步查找路由表，得到到达节点5的唯一一个下一跳节点为节点3，且密钥量充足，因此确定下一跳节点为节点3；

7) 由于从节点2经节点3到节点5有多条路径，因而将节点3的回溯点标记为节点2；

8) 从节点3开始，进一步查找路由表，得到到达节点5的唯一的下一跳节点为节点4，且密钥量充足，因此确定下一跳节点为节点4；

9) 但由于从节点3经节点4到节点5只有一条路径，因此将节点4的回溯点仍然标记为节点2；

10) 从节点4开始，进一步查找路由表，发现可直接到达节点5，且链路的密钥量充足，因而可直接将密钥转发给节点5。

至此，算法结束。

由此算法可以看出，当发现密钥量不足的链路后，本算法就回溯到存在其他最短路径的节点，由此以最小的代价沿着新的最短路径进行路由选择。

本文对图3的网络拓扑做进一步的扩展，采用图5所示的网络拓扑图，对使用单路径路由算法、多路径路由算法、文献[16]提出的随机单路径路由算法以及本文提出的算法来实现Alice和Bob之间的密钥传递情况进行仿真实验。

本实验的硬件环境是Intel(R) Core(TM) i7-4790 CPU @ 3.60 GHz，8.0 GB RAM，Windows 7专业版操作系统，Visual Studio 2015，算法的实现语言为C++。

本文采用以下3个性能指标进行评价和分析：1)选路成功率。选择路径成功与否是路由算法可行与否的关键，该指标用来评价路由算法的可行性。2) 密钥消耗量。充足的密钥量是信任中继量子网络密钥传递的必要条件，密钥消耗的多少直接影响到接下来的密钥通信，该指标用来评价路由算法的效率。3) 选路时间。一次密钥传递的时间对路由的效率影响很大，该指标用来评价路由算法的效率。

针对图5所示的网络拓扑结构，Alice到Bob之间的路径有很多条，通过路由算法选择3条最短路径：A-B-C-D-E；A-I-M-F-E；A-H-G-F-E。

针对密钥量充足的情况，4种方法的选路成功率均为100%。因此，本实验只考虑存在密钥量不足链路的情况。本网络中可选择的链路有11条。本实验仿真一条链路密钥量不足时的选路成功率，分别用4种路由算法做了11组实验来仿真11条链路在密钥量不足情况下的选路情况，每组20次，统计其选路成功次数和选路成功率(选路成功率=选路成功次数/实验次数)。

4种不同算法的选路成功率情况如图6所示。可以看出，本算法在一条链路密钥量不足的时候，选路成功率都是100%，选路效果最好；而文献[16]提出的随机单路径路由算法，当存在链路密钥量不足时，成功率很难达到100%；对于单路径路由算法，当链路A-B、B-C、C-D和D-E密钥量不足时，选路成功率为0，其他情况选路成功率为100%；对于多路径路由算法，存在密钥量不足链路时，选路成功率为0。

分析原因如下：单路径路由算法在选路时选择一条路径，当选中的路径的链路密钥量不足时，就会宣告选路失败；多路径路由算法在选路时，虽然可选择多条路径(这里为3条路径)，但无论哪条路径的链路密钥量不足，都会宣告选路失败；文献[16]提出的随机单路径路由算法在选路时随机选择一条，可能会选中密钥量不足的链路，进而导致选路失败；而本文提出的算法，选路时会从3条最短路径中随机选择一条，当选中的最短链路密钥量不足时，就会回溯到有具有多条路径的节点，继续进行路由选择，而不是宣告选路失败，因而选路代价较低，成功率较高。因此，相对于已存在的针对QKD网络的路由算法来说，本文提出的路由选择算法的选路成功率更高，效果更好。

假设本次密钥传递需要的密钥量为10。用K1、K2、K3和K4分别代表4种算法的密钥消耗量，其中，K1表示单路径路由的密钥消耗量，K2表示多路径路由的密钥消耗量，K3表示文献[16]的随机单路径路由的密钥消耗量，K4表示本文算法的密钥消耗量。

密钥消耗量比较分以下4种情况：

1) 链路密钥量充足：4种算法都选路成功，密钥消耗量为：K1=K3=K4=40，K2=120。

2) 第二跳密钥量不足：单路径路由算法选路失败后从起点重新开始进行密钥传递，则K1=10+40n(n≥1)；多路径路由算法其中一条路径选路失败后该路径重新开始进行密钥传递，则K2=80+10+40n=90+40n(n≥1)；文献[16]的随机路由算法的密钥消耗量等同于单路径路由算法，则K3=10+40n(n≥1)；而当选中的链路密钥量不足时，本算法将回溯到回溯点继续进行密钥传递，直至选路成功，则K4=10+40=50。

3) 第三跳密钥量不足：K1=20+40n(n≥1)；K2=80+20+40n=100+40n(n≥1)；K3=20+40n(n≥1)；K4=20+40=60。

4) 第四跳密钥量不足：K1=30+40n(n≥1)；K2=80+30+40n=110+40n(n≥1)；K3=30+40n(n≥1)；K4=30+40=70。

密钥消耗量结果如表7所示：由表7可知，当存在链路密钥量不足的情况时，本算法的密钥消耗量明显小于或等于其他3种算法，效率更高。

由单路径路由、多路径路由和文献[16]提出的随机路由算法的选路原理可知，3种方法的选路时间相差无几。本实验只比较文献[16]算法与本算法的选路时间。

对于文献[16]的路由算法，当选择的路径密钥量不足时，就中断通信，重新开始进行密钥传递。为了比较两个算法的选路时间，本实验设定密钥产生速率为100单位/s，当文献[16]的算法失败后，更新密钥量，重新开始密钥传递，直到密钥传递成功。将每次的时间相加，即可得到选路时间。

本实验利用图5所示的网络，采用本文提出的算法进行多次实验，记录20次有回溯的选路时间；采用文献[16]的算法进行多次实验，记录20次选择路径失败后重新进行选路的选路时间。对比结果如图7所示。

由图7可知，本算法的选路时间为0.03～0.06 s，而算法[16]的选路时间为0.08～0.12 s。显而易见，本算法的选路时间较短，效率较高。

上述实验及分析结果表明：相对于已有的单路径路由算法、多路径路由算法和随机单路径路由算法，本算法在密钥量不足的网络中有更好的选路成功率、更少的密钥消耗量和更短的选路时间。

本文主要针对基于信任中继的量子密钥网络的路由问题展开研究，分析了现有路由方案存在的问题，提出了一种随机路由方案。该方案通过改进的路由算法找到两点之间的3条最短路径，从而保证有多条较短路径；在选路过程中，随机选择其中的一条，安全性较高；遇到密钥量不足的链路时，回溯到有其他路径的节点，节省密钥量并提高了密钥传输效率。实验及分析结果表明，本算法不仅适用范围广，并且在选路时间、密钥消耗量以及密钥传输效率方面有一定的优势。

本文工作得到网络文化与数字传播北京市重点实验室(ICDDXN004)的资助，在此表示感谢。