量子密钥分发网络端端密钥协商最优路径选择算法

量子密钥分发网络端端密钥协商最优路径选择算法作者：石磊苏锦海郭义喜来源：《计算机应用》2015年第12期摘要：针对量子密钥分发（QKD）网络端端密钥协商路径选择问题，设计了一种基于改进Dijkstra算法的端端密钥协商最优路径选择算法。

首先，基于有效路径策略，剔除网络中的失效链路；然后，基于最短路径策略，通过改进Dijkstra算法，得到密钥消耗最少的多条最短路径；最后，基于最优路径策略，从多条最短路径中选择一条网络服务效率最高的最优路径。

分析结果表明，该算法很好地解决了最优路径不唯一、最优路径非最短、最优路径非最优等问题，可以降低QKD网络端端密钥协商时密钥消耗量，提高网络服务效率。

关键词：量子密钥分发网络；端端密钥协商；路径选择；最短路径； Dijkstra算法；密钥消耗中图分类号：TP393.04文献标志码：A英文标题Abstract：Focusing on the routing selection of endtoend key agreement in Quantum Key Distribution （QKD） network， an optimal routing selection algorithm of endtoend key agreement based on the Dijkstra algorithm was designed. Firstly， the unavailable links in the QKD networks were eliminated based on the strategy of choosing the available paths. Secondly， based on the strategy of choosing the shortest paths， the Dijkstra algorithm was improved to find out all the shortest paths with the least key consumption. Finally， according to the strategy of choosing the optimal path， the optimal path with the highest network service efficiency was selected from the shortest paths. The analysis results show that， the proposed algorithm solves the problems such as the optimal path is not unique， the best path is not the shortest， the optimal path is not optimal， and so on.The proposed algorithm can reduce the key consumption of endtoend key agreement in QKD network， and improve the efficiency of network services.英文关键词Key words：Quantum Key Distribution （QKD） network； endtoend key agreement； routing selection；shortest path； Dijkstra algorithm； key consumption0引言量子密钥分发（Quantum Key Distribution， QKD）网络是由量子信道组成的量子网络和经典信道组成的经典网络层叠在一起，两个网络相互配合共同完成密钥分发[1]。

目前，QKD技术重点研究了具有量子信道的两端分发相邻端端共享密钥，而构建量子密钥分发网络，为密码设备提供密钥服务，在量子信道受限的情况下，必须要实现网络中任意QKD节点间（包括没有量子信道的节点间）任意端端共享密钥分发。

端端密钥协商就是QKD 网络中基于相邻端端共享密钥生成任意端端共享密钥这一难题的解决途径。

进行端端密钥协商时，可能存在多条协商路径，协商路径的不同直接影响QKD网络密钥消耗和密钥服务效率。

为减少QKD网络密钥消耗，提高网络密钥服务效率，文献[2]设计了一种以密钥生成速率和密钥池输出速率之和的倒数为带宽权重、基于Dijkstra算法的最优路径选择算法。

算法实质是将路径中各链路带宽倒数和相加，取相加值最小的路径为最优路径。

分析发现，以倒数和相加的方式确定能比较简单地使得所选路径中各链路带宽均最大，但是该方法在计算过程中屏蔽了许多链路信息，使得最后选择的路径无法达到最理想的效果：1）路径最短，使得密钥消耗最少；2）所选路径各链路带宽均最大，对网络密钥服务效率影响最小。

为了克服文献[2]算法的不足，实现最短和最优的选路目的，本文采取分步实现方式，基于Dijkstra算法设计了一种端端密钥协商路径选择算法。

算法的基本思想是：第一步，基于有效路径策略，剔除网络中的失效链路；第二步，基于最短路径策略，从所有有效路径中找出最短路径；第三步，基于最优路径策略，从多条最短路径中找出满足条件的最优路径。

1QKD网络端端密钥协商1.1QKD骨干网结构QKD网络经典网络层节点完全互联，不影响网络结构，而量子层节点互联关系直接决定了QKD网络结构，因此，QKD网络结构是在量子层面描述的。

根据目前常用的QKD组网方案[3-4]，将整个QKD网络划分为两种类型的网络，即骨干网与接入网。

目前的接入网多采用星型结构，结构简单，网络中任意两点之间一般均只有一条路径，不存在路径选择问题。

而骨干网目前普遍采用可信中继方式，网络中节点多，节点之间通常存在多条路径，路径选择较为复杂，本文重点研究骨干网的路径选择问题。

格型结构是目前国内外的一个研究热点[5-7]，如图1（a）所示。

格型网络可以通过多路径方式解决单路径无法解决的安全传输问题，同时相比星型和树型结构有更好的可靠性、稳定性、扩展性等，但其规则的网络结构极大地限制了其应用环境。

在实际应用中，如图1（b）所示的不规则的网状结构更具实用价值。

图1（b）所示的不规则的网状结构具有以下一些基本特性：1）网络中不存在孤立的网络节点；2）任意网络节点之间至少有一条路径；3）不是任意两个网络节点之间均有直接相连的量子链路。

借用图论的概念，此网络结构形成的图是一个简单非完全连通图。

1.2密钥网络欧洲量子保密通信（SEcure COmmunication based on Quantum Cryptography， SECOQC）项目中提出了“network of secrets”的概念，这个网络的功能仅仅是存储、推送和管理由QKD产生的密钥，而与密钥的产生与应用无关[8]。

本文采用“network of secrets”的概念，并将之译为密钥网络。

密钥网络，由网络节点及网络节点之间的密钥共享关系构成。

网络节点之间的共享密钥，可分为相邻端端共享密钥和任意端端共享密钥。

本文中，相邻端端共享密钥用集合R表示，任意端端共享密钥用集合K表示。

为了阐明密钥网络的概念，本文以一个包含9个网络节点的网状骨干网相邻端端密钥网络为例，如图2所示。

图2中si代表网络节点i（i=0，1，…，9），实线代表节点之间的相邻端端密钥共享关系，字母Rij表示节点si与节点sj之间的相邻端端共享密钥。

如s1与s2之间的实线表示它们之间有相邻端端密钥关系，R1，2为s1与s2之间的相邻端端共享密钥。

1.3端端密钥协商技术在密钥网络中，相邻网络节点si与sj之间可以通过量子密钥分发技术，得到相邻端端共享密钥Rij；而非相邻网络节点之间共享密钥的生成需要通过端端密钥协商。

端端密钥协商，可看作是通过路径上的相邻端端共享密钥R协商生成路径端点间的任意端端共享密钥K的过程。

例如，在如图2所示的密钥网络中，网络节点s1与s8不相邻，其共享密钥R1，8的生成需要通过端端密钥协商。

而由图2可知，s1与s8之间的端端密钥协商路径不止一条，如路径s1→s2→s5→s6→s8和路径s1→s4→s7→s8等。

显然，在密钥网络的网络节点之间进行端端密钥协商时需要一个协商路径选择算法。

文献[2]基于提高QKD网络的密钥服务效率、减少密钥消耗的目的，给出了一个路由算法。

该路由算法原是出于保密通信应用需求，为密码应用选择一条最优的密码加密路径，虽与本文为密钥协商双方选择一条最优协商路径的应用目的不同，但经过深入分析发现，其实两者本质上是一致的。

本文中密钥协商是逐跳协商密钥，而后进行保密通信，文献[2]是逐跳进行数据加密，直接进行保密通信，两者虽方式不同，但是目的是相同的。

因此，在设计本文的路径选择算法时，可以借鉴文献[2]算法的设计思想，尤其是其最优路径的思想。

文献[2]设计的算法分为2个步骤：1）预处理阶段，删除带宽不满足需求的链路。

2）选路阶段，以密钥生成速率与密钥池输出速率之和的倒数作为权值，基于Dijkstra算法进行路由选择，选出一条最优路径。

步骤2）有两个目的：一是基于Dijkstra算法以密钥生成速率与密钥池输出速率之和为权值找到一条最短路径；二是找到一条各链路带宽均最大的最优路径。

对文献[2]算法深入分析发现，该算法能解决大部分路径选择难题，选出一条最优路径，但当遇到一些特殊情况时，选路效果不是特别理想。

具体情况分析如下：1）最优路径不唯一。

如图3所示，节点s1→s5之间有2条路径，分别为路径s1→s2→s5和路径s1→s3→s4→s5。

其中路径s1→s2→s5的总权值为1/2+1/2=1，而路径s1→s3→s4→s5的总权值为1/4+1/4+1/2=1。

因此，按照文献[2]算法选路，路径s1→s2→s5与路径s1→s3→s4→s5等效。

实际上，路径s1→s2→s5与路径s1→s3→s4→s5相比，长度短，密钥消耗少，对于网络服务效率的影响小，两者相比，路径s1→s2→s5优于路径s1→s3→s4→s5。

因此，按照文献[2]算法将它们简单处理为等效路径是不合适的。

2）最优路径非最短。

如图4所示，路径s1→s2→s5的总权值为1/10+1/10=18/90，而路径s1→s3→s4→s5的总权值为1/30+1/30+1/9=16/90。

因此，按照文献[2]算法选路，应选择路径s1→s3→s4→s5。

实际上，路径s1→s3→s4→s5与路径s1→s2→s5相比，路径长度更大，且存在瓶颈链路s4→s5，两者相比，路径s1→s2→s5优于路径s1→s3→s4→s5。