石 磊 郭义喜 苏锦海

(解放军信息工程大学 河南 郑州 450004)

量子密钥分发网络组密钥服务节点选址算法

石 磊 郭义喜 苏锦海

(解放军信息工程大学 河南 郑州 450004)

针对量子密钥分发QKD(Quantum Key Distribution)网络组密钥协商中的组密钥服务节点选址问题，根据组密钥服务节点数量确定和不确定两种不同情况，构建了常规的p-median选址模型和改进的p-median选址模型，并就每种选址模型分别设计了枚举法和贪婪算法两种选址算法。通过仿真模拟实验比较了两种算法的性能，并结合两种算法的不同性能特点阐述了各自的应用场景。结果表明，该算法步骤清晰，操作简单，易于掌握，具有一定的实际意义和参考价值。

量子密钥分发(QKD)网络 组密钥服务节点 选址问题 p-median 枚举法 贪婪算法

0 引 言

组密钥，即多个用户设备可以共享同一个密钥，用于组员之间的数据加密传输。随着多方交互式游戏、在线股票交易、视频会议等群组通信在当今社会日益普及，组密钥的安全性需求日益提高。基于计算安全的传统组密钥，其安全性已经渐渐不能满足高安全需求的群组通信需求。基于物理安全的量子密钥分发QKD技术，由于其无条件安全性，给高安全群组通信领域带来了新的契机。

目前，集中式组密钥协商思想逐渐引起关注。基于服务节点的组密钥协商方案是一种典型的集中式组密钥协商方案。它的基本思想是：在一个QKD网络中设定若干个具有密钥管理权限的组密钥服务节点，通过这些服务节点集中为组成员提供组密钥服务。

组密钥服务节点是整个网络的服务支撑点和流量瓶颈，其带宽和建设成本相对较高，其部署直接关系到网络的性能和成本，其选址算法是整个组密钥协商方案的核心。

组密钥服务节点选址问题是设施选址问题中的一种，多数选址模型[1-2]均能应用于组密钥服务节点选址问题中。p-median[3-5]是设施选址问题中较为经典的一种选址模型，其目标是确定P个设施位置，使得网络中所有需求点到设施的权重距离之和最短。

本文根据QKD网络组密钥协商的特点，基于p-median模型的适用性及组密钥服务节点的选址需求，对组密钥服务节点选址问题进行研究，分别针对组密钥服务节点数量确定和不确定两种情况，构建不同选址模型，设计不同应用场景下的实现算法。

1 QKD网络组密钥协商思想

QKD密钥网络由QKD节点以及QKD节点之间的密钥组成。图1为一种典型的格型QKD密钥网络结构，vi代表QKD节点，Rij代表节点vi与节点vj之间的共享密钥。

图1 典型的QKD密钥网络结构

QKD网络组密钥协商即解决QKD网络中若干个网络节点之间协商生成组密钥的问题。结合传统集中式组密钥管理思想，本文提出了一种基于分布式的集中式组密钥协商思想，其思想核心是：集中式生成，分布式分发。

集中式生成思想：将网络节点分为组密钥服务节点和普通网络节点，后者为前者提供组密钥服务。一个网络中设定若干个组密钥服务节点，组密钥由组密钥服务节点集中生成，而普通网络节点只负责申请组密钥。

分布式分发思想：网络中若干个组密钥服务节点各自独立地为其管辖下的组成员分发密钥，各个组密钥服务节点之间组密钥的一致性由集中式密钥生成方式保证。

由上述协商思想可知，组密钥服务节点是整个组密钥协商的核心。网络中组密钥服务节点位置及数量的不同，会引起网络密钥消耗、通信量等关乎整个网络服务性能方面的巨大差异。因此，组密钥服务节点的选址问题是整个组密钥协商的关键问题，本文将在下面对这一选址问题进行重点研究。

2 组密钥服务节点选址模型

2.1 常规p-median模型构建

为了更好地研究组密钥服务节点的选址问题，一些基本的假设条件如下：

1)QKD网络拓扑固定，候选服务节点集合中的每个组密钥服务节点具有相同的服务能力，建设成本也相同。

2) 一个组密钥服务节点被一个组密钥服务占用，若有其他组密钥服务请求到达同一组密钥服务节点，列入等待队列。

3) 不考虑需求规模，即网络各节点的组密钥服务需求都可以被相应的组密钥服务节点所满足。

优化目标：在固定的QKD网络拓扑下，根据给定的候选服务节点集合和最终的服务节点数量P，确定组密钥服务节点最优位置，使得网络中其他节点到组密钥服务节点的路径长度最小。

约束条件：

1) 组密钥服务节点的选择必须符合网络的拓扑结构。

2) 每一个网络需求节点都必须有一个组密钥服务节点为其提供组密钥服务(默认一个网络需求节点只能有一个组密钥服务节点为其提供服务)。

3) 组密钥服务节点的数量P明确，且只能从候选服务节点集合中进行选择。

为方便形式化描述，对以下变量进行定义。

N={v0,v1,…,vn-1}，其中N为网络节点集合，下标为网络节点标号。

集合I⊆N,其中集合I为网络需求节点集合；集合J⊆N，其中集合J为候选组密钥服务节点集合，其元素个数为k。

i为网络需求节点编号，vi∈I;j为候选组密钥服务节点编号，vj∈J。为了描述方便，本文规定vi与i等价，均可指网络需求节点；同理vj与j等价，均可指组密钥服务节点。

d(i,j)为网络需求节点i与候选组密钥服务节点j之间的最短路径长度。

ξj=1表示节点j为组密钥服务节点，若不是，则为0。

ξij=1表示网络需求节点i分配给组密钥服务节点j，否则，为0。

参考设施选址问题中p-median数学模型[6-9]，给出适用于组密钥服务节点选址的p-median模型：

优化目标：

(1)

约束条件：

(2)

(3)

ξij≤ξj∀i∈I,j∈J

(4)

ξij∈{0,1} ∀i∈I,j∈J

(5)

ξj∈{0,1} ∀j∈J

(6)

式(1)表示优化目标函数，使得网络需求节点到组密钥服务节点的路径长度最小；式(2)表示网络中任意一个节点i只能从一个组密钥服务节点j中得到服务；式(3)表示网络中需要建立的组密钥服务节点的数量；式(4)表示网络需求节点只能被组密钥服务节点所服务；式(5)、式(6)表明ξij与ξj为二进制变量。

2.2 改进的p-median模型构建

常规p-median模型假设一个网络中的组密钥服务节点数量是确定的，然而在实际应用中，大多数情况下无法准确地确定组密钥服务节点的个数，而是只有一个初步的候选服务节点集合，需要经过不断的计算，才能最终确定一个网络中的组密钥服务节点的最佳个数及位置。为了研究组密钥服务节点数量不确定情况下的选址问题，本文对常规p-median模型进行了改进，调整了其优化目标和约束条件。

改进的p-median数学模型：

优化目标：

(7)

约束条件：

(8)

ξij≤ξj∀i∈I,j∈J

(9)

ξij∈{0,1} ∀i∈I,j∈J

(10)

ξj∈{0,1} ∀j∈J

(11)

式(7)表示优化目标函数，有两个优化目标，需要同时确定组密钥服务节点的数量及位置，确保组密钥服务节点数量最少和网络需求节点到组密钥服务节点的路径长度最小；式(8)表示网络中任意一个节点i只能从一个组密钥服务节点j中得到服务；式(9)表示网络需求节点只能被组密钥服务节点所服务；式(10)、式(11)表明ξij与ξj为二进制变量。

3 组密钥服务节点选址算法

3.1 基于常规p-median模型的选址算法

3.1.1 枚举法

枚举法是一种常用的精确算法，其思想简单，易于理解和操作，因此本文首先采用枚举法解决p-median模型的选址问题。算法的基本步骤如下。

1) 根据QKD网络拓扑，构建邻接矩阵，运用Flyod算法求出网络的距离矩阵，并罗列出各个候选服务节点j(j∈J)到网络需求节点i(i∈I)的距离。

3.1.2 贪婪算法

贪婪算法[10-11]是一种应用较为广泛的算法，其算法策略符合人的日常思维习惯，易于理解掌握，且具有收敛速度快，易于工程实现等优势。因此本文采用贪婪算法来解决p-median模型的选址问题。

贪婪算法基本思想：以局部最优解得到整体的最优解，即为求得整体最优解，依据某种贪婪策略，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪婪选择，最终得出整个问题的最优解的方法。

定义1 (QKD网络最短传输距离)：QKD网络中所有网络需求节点到服务节点的最短传输距离。

定理1QKD网络最短传输距离与服务节点个数的函数f*(k)是一个非增函数。

证明：令f(k)为传输距离函数，而f*(k)为最短传输距离函数，两者因网络需求节点的分配不同而存在差异。显然，f(k)≤f*(k)。

又因为f*(k+1)≤f(k+1)成立，所以对于k∈{1,2,…,m}，f*(k+1)≤f*(k)成立，即定理1得证。

定理1表明随着网络中服务节点的增多，网络需求节点到服务节点的传输距离只可能有两种情况：传输距离保持不变或者减少。

基于定理1，本文采用的贪婪策略是：依据某一剔除原则，每次从候选服务节点集合中剔除一个服务节点，直到最后剩下p个服务节点。

剔除原则是：若从候选服务节点集合中剔除该服务节点，并将原属于它的网络需求节点分配给其他候选服务节点后，整个网络的传输距离增加量最小。

利用贪婪算法解决常规p-median模型选址问题的基本步骤：

1) 根据QKD网络拓扑，构建邻接矩阵，运用Flyod算法求出网络的距离矩阵，并罗列出各个候选服务节点j(j∈J)到网络需求节点i(i∈I)的距离。

2) 假设服务节点集S=J，即将所有候选服务节点均选中，依据就近原则，将所有网络需求节点分配给相应的候选服务节点。

3) 检查集合S的元素个数，若|S|=p，其中|S|表示集合S的元素个数，则输出集合S的元素及其个数，同时输出网络需求节点的分配结果，结束；若|S|>p，则执行步骤4)。

4) 依据剔除原则，从集合S中确定并剔除该被剔除的元素，并转3)。

3.2 基于改进的p-median模型的选址算法

3.2.1 枚举法

算法基本步骤如下：

1) 根据QKD网络拓扑，构建邻接矩阵，运用Flyod算法求出网络的距离矩阵，并罗列出各个候选服务节点j(j∈J)到网络需求节点i(i∈I)的距离。

3) 若minZp≤minZp+1，则输出服务节点个数为p时Zp取得最小值时服务节点的位置及网络需求节点的分配结果，并结束算法。

4) 若minZp≥minZp+1，则令p=p+1，执行步骤2)。

3.2.2 贪婪算法

贪婪算法的基本思想是每一次贪婪都是当前状态下的局部最优，以局部最优解逐渐逼近整体最优解。即在3.1.2节中服务节点集合S始终是贪婪算法选择出的当前状态下使得Z最小的最优组密钥服务节点组合。因此，解决常规p-median模型选址问题与改进的p-median模型选址问题，本质上是一样的，其算法的基本步骤如下：

1) 根据QKD网络拓扑，构建邻接矩阵，运用Flyod算法求出网络的距离矩阵，并罗列出各个候选服务节点j(j∈J)到网络需求节点i(i∈I)的距离。

2) 假设服务节点集S=J，即将所有候选服务节点均选中，依据就近原则，将所有网络需求节点分配给相应的候选服务节点。

4) 若minZp≥minZp-1，则输出p个服务节点的位置及网络需求节点的分配结果，并结束算法。

5) 若minZp≤minZp-1，则令p=p-1。且依据剔除原则，从集合S中确定并剔除该被剔除的元素，并转步骤3)。剔除原则同3.1.2节所述。

4 两种算法的性能分析

4.1 算 例

本文以求解质量与求解耗两个指标来衡量算法性能。求解质量指利用算法求得所得解与最优解的比值。求解耗时指利用算法求解所需时间。为分析枚举算法与贪婪算法的性能，选择候选服务节点数量样本N=10，12，15，20，25，30。

实验环境为：Windows7系统，CPU为Inter(R)Core(TM)i5-3570，主频为3.40GHz，内存为8GB，MatlabR2009a软件。

由第3节可知，不确定数量p-median选址问题的解决算法是基于确定数量p-median选址问题，因此本文以确定数量p-median选址问题为例，选定服务节点样本为p=2，试验次数为50次。

4.2 算例结果与分析

表1与表2分别为求解质量与求解耗时的实验数据。

表1 求解质量实验数据

表2 求解耗时实验数据 秒

实验结论：从表1可知，利用贪婪算法，其求解质量基本保持不变，与最优解存在一定偏离，但是偏离值在可接受范围之内。由表2可知，在区间[10,20]间枚举算法与贪婪算法求解耗时差别不大，但是超过20个节点，枚举算法的求解耗时显著增加，而贪婪算法的增幅相对较小。

贪婪算法是一种近似算法，通过求解局部最优，逐步逼近整体最优，其求解结果与最优值可能存在一定偏差。由于其局部最优求解思想，不考虑各种可能的整体，因此大大简单了其每一步的求解规模，使得其求解耗时短，时间复杂度只有二次方级。两种算法的性能比较如表3所示。

表3 两种算法的性能比较

城域网大概需要十几个QKD节点，节点数量较少，由上面的分析结果可知，枚举算法进行选址比较合适；而城际网节点数量较多，可能成百上千，枚举算法已经失效，因此选择贪婪算法进行选址更为合适。

5 结 语

组密钥服务节点的选址问题直接关系到网络服务性能，本文重点研究了其选址算法。针对组密钥服务节点数量确定和不确定两种情况，分别构建了数学模型，并设计了枚举与贪婪两种算法，通过仿真模拟实验比较了两种算法的性能，并分析了两种算法各自不同的应用场景。结果表明，本文设计的算法原理简单，步骤清晰，操作方便，易于掌握，具有一定的实际意义和参考价值。

[2] 徐大川,杜东雷,吴晨晨.设施选址问题的近似算法综述[J].数学进展,2014,43(6):801-816.

[4]AardalK,BergPLVD,GijswijtD,etal.Approximationalgorithmsforhardcapacitatedk-facilitylocationproblems[J].EuropeanJournalofOperationalResearch,2015,242(2):358-368.

[5]GuhaS,KhullerS.Greedystrikesback:improvedfacilitylocationalgorithms[J].JournalofAlgorithms,1999,31(1):228-248.

[6]DantrakulS,LikasiriC,PongvuthithumR.Appliedp-medianandp-centeralgorithmsforfacilitylocationproblems[J].ExpertSystemswithApplications,2014,41(8):3596-3604.

[7]GuoJ.Acostoptimizationmodelanditsheuristicalgorithmforacontentdistributionnetwork[J].ComputerModelling&NewTechnologies,2014,18(12B):369-374.

[8]ReeseJ.Methodsforsolvingthep-medianproblem:anannotatedbibliography[J].Networks,2006,48(3):125-142.

[9] 刘子先,李晓鹏.多因素P-median下对电动出租车充电站的选址研究[J].工业工程与管理,2013,18(6):1-6.

[10] 饶卫振,金淳,陆林涛.考虑边位置信息的求解ETSP问题改进贪婪算法[J].计算机学报,2013,36(4):836-850.

[11] 张彩庆,赵璐.基于P-中值模型的电网检修公司分部选址模型[J].系统管理学报,2014,23(4):501-506.

[12]WenH.Protocolsandmechanismsinthequantumkeydistributionnetworks[D].Hefei,Anhui,China:UniversityofScienceandTechnologyofChina,2008.

LOCATION ALGORITHMS FOR GROUP KEY SERVICE NODES IN QUANTUMKEY DISTRIBUTION NETWORKS

Shi Lei Guo Yixi Su Jinhai

(PLAUniversityofInformationEngineering,Zhengzhou450004,Henan,China)

To handle out the location problem for group key service nodes in quantum key distribution(QKD) networks, a normal p-median location model and a modified p-median location model are constructed separately in the light of whether the number of group key service nodes is decided or not. In each model, both enumeration algorithm and greedy algorithm are designed, and their different application scenarios are also presented. The results of simulation experiments show that the algorithms are clear and easy to practice, and the proposal will be reference to similar research.

Quantum key distribution (QKD) network Group key service nodes Location problem p-median enumeration algorithm Greedy algorithm

2015-11-29。石磊，硕士生，主研领域：信息安全。郭义喜，副教授。苏锦海，教授。

TP393.04

A

10.3969/j.issn.1000-386x.2017.03.044