量子密鑰分發(fā)網(wǎng)絡(luò)組密鑰服務(wù)節(jié)點(diǎn)選址算法

石 磊 郭義喜 蘇錦海

(解放軍信息工程大學(xué) 河南 鄭州 450004)

量子密鑰分發(fā)網(wǎng)絡(luò)組密鑰服務(wù)節(jié)點(diǎn)選址算法

石 磊 郭義喜 蘇錦海

(解放軍信息工程大學(xué) 河南 鄭州 450004)

針對(duì)量子密鑰分發(fā)QKD(Quantum Key Distribution)網(wǎng)絡(luò)組密鑰協(xié)商中的組密鑰服務(wù)節(jié)點(diǎn)選址問(wèn)題，根據(jù)組密鑰服務(wù)節(jié)點(diǎn)數(shù)量確定和不確定兩種不同情況，構(gòu)建了常規(guī)的p-median選址模型和改進(jìn)的p-median選址模型，并就每種選址模型分別設(shè)計(jì)了枚舉法和貪婪算法兩種選址算法。通過(guò)仿真模擬實(shí)驗(yàn)比較了兩種算法的性能，并結(jié)合兩種算法的不同性能特點(diǎn)闡述了各自的應(yīng)用場(chǎng)景。結(jié)果表明，該算法步驟清晰，操作簡(jiǎn)單，易于掌握，具有一定的實(shí)際意義和參考價(jià)值。

量子密鑰分發(fā)(QKD)網(wǎng)絡(luò) 組密鑰服務(wù)節(jié)點(diǎn) 選址問(wèn)題 p-median 枚舉法 貪婪算法

0 引 言

組密鑰，即多個(gè)用戶設(shè)備可以共享同一個(gè)密鑰，用于組員之間的數(shù)據(jù)加密傳輸。隨著多方交互式游戲、在線股票交易、視頻會(huì)議等群組通信在當(dāng)今社會(huì)日益普及，組密鑰的安全性需求日益提高。基于計(jì)算安全的傳統(tǒng)組密鑰，其安全性已經(jīng)漸漸不能滿足高安全需求的群組通信需求?；谖锢戆踩牧孔用荑€分發(fā)QKD技術(shù)，由于其無(wú)條件安全性，給高安全群組通信領(lǐng)域帶來(lái)了新的契機(jī)。

目前，集中式組密鑰協(xié)商思想逐漸引起關(guān)注。基于服務(wù)節(jié)點(diǎn)的組密鑰協(xié)商方案是一種典型的集中式組密鑰協(xié)商方案。它的基本思想是：在一個(gè)QKD網(wǎng)絡(luò)中設(shè)定若干個(gè)具有密鑰管理權(quán)限的組密鑰服務(wù)節(jié)點(diǎn)，通過(guò)這些服務(wù)節(jié)點(diǎn)集中為組成員提供組密鑰服務(wù)。

組密鑰服務(wù)節(jié)點(diǎn)是整個(gè)網(wǎng)絡(luò)的服務(wù)支撐點(diǎn)和流量瓶頸，其帶寬和建設(shè)成本相對(duì)較高，其部署直接關(guān)系到網(wǎng)絡(luò)的性能和成本，其選址算法是整個(gè)組密鑰協(xié)商方案的核心。

組密鑰服務(wù)節(jié)點(diǎn)選址問(wèn)題是設(shè)施選址問(wèn)題中的一種，多數(shù)選址模型[1-2]均能應(yīng)用于組密鑰服務(wù)節(jié)點(diǎn)選址問(wèn)題中。p-median[3-5]是設(shè)施選址問(wèn)題中較為經(jīng)典的一種選址模型，其目標(biāo)是確定P個(gè)設(shè)施位置，使得網(wǎng)絡(luò)中所有需求點(diǎn)到設(shè)施的權(quán)重距離之和最短。

本文根據(jù)QKD網(wǎng)絡(luò)組密鑰協(xié)商的特點(diǎn)，基于p-median模型的適用性及組密鑰服務(wù)節(jié)點(diǎn)的選址需求，對(duì)組密鑰服務(wù)節(jié)點(diǎn)選址問(wèn)題進(jìn)行研究，分別針對(duì)組密鑰服務(wù)節(jié)點(diǎn)數(shù)量確定和不確定兩種情況，構(gòu)建不同選址模型，設(shè)計(jì)不同應(yīng)用場(chǎng)景下的實(shí)現(xiàn)算法。

1 QKD網(wǎng)絡(luò)組密鑰協(xié)商思想

QKD密鑰網(wǎng)絡(luò)由QKD節(jié)點(diǎn)以及QKD節(jié)點(diǎn)之間的密鑰組成。圖1為一種典型的格型QKD密鑰網(wǎng)絡(luò)結(jié)構(gòu)，vi代表QKD節(jié)點(diǎn)，Rij代表節(jié)點(diǎn)vi與節(jié)點(diǎn)vj之間的共享密鑰。

圖1 典型的QKD密鑰網(wǎng)絡(luò)結(jié)構(gòu)

QKD網(wǎng)絡(luò)組密鑰協(xié)商即解決QKD網(wǎng)絡(luò)中若干個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間協(xié)商生成組密鑰的問(wèn)題。結(jié)合傳統(tǒng)集中式組密鑰管理思想，本文提出了一種基于分布式的集中式組密鑰協(xié)商思想，其思想核心是：集中式生成，分布式分發(fā)。

集中式生成思想：將網(wǎng)絡(luò)節(jié)點(diǎn)分為組密鑰服務(wù)節(jié)點(diǎn)和普通網(wǎng)絡(luò)節(jié)點(diǎn)，后者為前者提供組密鑰服務(wù)。一個(gè)網(wǎng)絡(luò)中設(shè)定若干個(gè)組密鑰服務(wù)節(jié)點(diǎn)，組密鑰由組密鑰服務(wù)節(jié)點(diǎn)集中生成，而普通網(wǎng)絡(luò)節(jié)點(diǎn)只負(fù)責(zé)申請(qǐng)組密鑰。

分布式分發(fā)思想：網(wǎng)絡(luò)中若干個(gè)組密鑰服務(wù)節(jié)點(diǎn)各自獨(dú)立地為其管轄下的組成員分發(fā)密鑰，各個(gè)組密鑰服務(wù)節(jié)點(diǎn)之間組密鑰的一致性由集中式密鑰生成方式保證。

由上述協(xié)商思想可知，組密鑰服務(wù)節(jié)點(diǎn)是整個(gè)組密鑰協(xié)商的核心。網(wǎng)絡(luò)中組密鑰服務(wù)節(jié)點(diǎn)位置及數(shù)量的不同，會(huì)引起網(wǎng)絡(luò)密鑰消耗、通信量等關(guān)乎整個(gè)網(wǎng)絡(luò)服務(wù)性能方面的巨大差異。因此，組密鑰服務(wù)節(jié)點(diǎn)的選址問(wèn)題是整個(gè)組密鑰協(xié)商的關(guān)鍵問(wèn)題，本文將在下面對(duì)這一選址問(wèn)題進(jìn)行重點(diǎn)研究。

2 組密鑰服務(wù)節(jié)點(diǎn)選址模型

2.1 常規(guī)p-median模型構(gòu)建

為了更好地研究組密鑰服務(wù)節(jié)點(diǎn)的選址問(wèn)題，一些基本的假設(shè)條件如下：

1)QKD網(wǎng)絡(luò)拓?fù)涔潭?，候選服務(wù)節(jié)點(diǎn)集合中的每個(gè)組密鑰服務(wù)節(jié)點(diǎn)具有相同的服務(wù)能力，建設(shè)成本也相同。

2) 一個(gè)組密鑰服務(wù)節(jié)點(diǎn)被一個(gè)組密鑰服務(wù)占用，若有其他組密鑰服務(wù)請(qǐng)求到達(dá)同一組密鑰服務(wù)節(jié)點(diǎn)，列入等待隊(duì)列。

3) 不考慮需求規(guī)模，即網(wǎng)絡(luò)各節(jié)點(diǎn)的組密鑰服務(wù)需求都可以被相應(yīng)的組密鑰服務(wù)節(jié)點(diǎn)所滿足。

優(yōu)化目標(biāo)：在固定的QKD網(wǎng)絡(luò)拓?fù)湎拢鶕?jù)給定的候選服務(wù)節(jié)點(diǎn)集合和最終的服務(wù)節(jié)點(diǎn)數(shù)量P，確定組密鑰服務(wù)節(jié)點(diǎn)最優(yōu)位置，使得網(wǎng)絡(luò)中其他節(jié)點(diǎn)到組密鑰服務(wù)節(jié)點(diǎn)的路徑長(zhǎng)度最小。

約束條件：

1) 組密鑰服務(wù)節(jié)點(diǎn)的選擇必須符合網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

2) 每一個(gè)網(wǎng)絡(luò)需求節(jié)點(diǎn)都必須有一個(gè)組密鑰服務(wù)節(jié)點(diǎn)為其提供組密鑰服務(wù)(默認(rèn)一個(gè)網(wǎng)絡(luò)需求節(jié)點(diǎn)只能有一個(gè)組密鑰服務(wù)節(jié)點(diǎn)為其提供服務(wù))。

3) 組密鑰服務(wù)節(jié)點(diǎn)的數(shù)量P明確，且只能從候選服務(wù)節(jié)點(diǎn)集合中進(jìn)行選擇。

為方便形式化描述，對(duì)以下變量進(jìn)行定義。

N={v0,v1,…,vn-1}，其中N為網(wǎng)絡(luò)節(jié)點(diǎn)集合，下標(biāo)為網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)號(hào)。

集合I?N,其中集合I為網(wǎng)絡(luò)需求節(jié)點(diǎn)集合；集合J?N，其中集合J為候選組密鑰服務(wù)節(jié)點(diǎn)集合，其元素個(gè)數(shù)為k。

i為網(wǎng)絡(luò)需求節(jié)點(diǎn)編號(hào)，vi∈I;j為候選組密鑰服務(wù)節(jié)點(diǎn)編號(hào)，vj∈J。為了描述方便，本文規(guī)定vi與i等價(jià)，均可指網(wǎng)絡(luò)需求節(jié)點(diǎn)；同理vj與j等價(jià)，均可指組密鑰服務(wù)節(jié)點(diǎn)。

d(i,j)為網(wǎng)絡(luò)需求節(jié)點(diǎn)i與候選組密鑰服務(wù)節(jié)點(diǎn)j之間的最短路徑長(zhǎng)度。

ξj=1表示節(jié)點(diǎn)j為組密鑰服務(wù)節(jié)點(diǎn)，若不是，則為0。

ξij=1表示網(wǎng)絡(luò)需求節(jié)點(diǎn)i分配給組密鑰服務(wù)節(jié)點(diǎn)j，否則，為0。

參考設(shè)施選址問(wèn)題中p-median數(shù)學(xué)模型[6-9]，給出適用于組密鑰服務(wù)節(jié)點(diǎn)選址的p-median模型：

優(yōu)化目標(biāo)：

(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)表示優(yōu)化目標(biāo)函數(shù)，使得網(wǎng)絡(luò)需求節(jié)點(diǎn)到組密鑰服務(wù)節(jié)點(diǎn)的路徑長(zhǎng)度最??；式(2)表示網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)i只能從一個(gè)組密鑰服務(wù)節(jié)點(diǎn)j中得到服務(wù)；式(3)表示網(wǎng)絡(luò)中需要建立的組密鑰服務(wù)節(jié)點(diǎn)的數(shù)量；式(4)表示網(wǎng)絡(luò)需求節(jié)點(diǎn)只能被組密鑰服務(wù)節(jié)點(diǎn)所服務(wù)；式(5)、式(6)表明ξij與ξj為二進(jìn)制變量。

2.2 改進(jìn)的p-median模型構(gòu)建

常規(guī)p-median模型假設(shè)一個(gè)網(wǎng)絡(luò)中的組密鑰服務(wù)節(jié)點(diǎn)數(shù)量是確定的，然而在實(shí)際應(yīng)用中，大多數(shù)情況下無(wú)法準(zhǔn)確地確定組密鑰服務(wù)節(jié)點(diǎn)的個(gè)數(shù)，而是只有一個(gè)初步的候選服務(wù)節(jié)點(diǎn)集合，需要經(jīng)過(guò)不斷的計(jì)算，才能最終確定一個(gè)網(wǎng)絡(luò)中的組密鑰服務(wù)節(jié)點(diǎn)的最佳個(gè)數(shù)及位置。為了研究組密鑰服務(wù)節(jié)點(diǎn)數(shù)量不確定情況下的選址問(wèn)題，本文對(duì)常規(guī)p-median模型進(jìn)行了改進(jìn)，調(diào)整了其優(yōu)化目標(biāo)和約束條件。

改進(jìn)的p-median數(shù)學(xué)模型：

優(yōu)化目標(biāo)：

(7)

約束條件：

(8)

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

(9)

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

(10)

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

(11)

式(7)表示優(yōu)化目標(biāo)函數(shù)，有兩個(gè)優(yōu)化目標(biāo)，需要同時(shí)確定組密鑰服務(wù)節(jié)點(diǎn)的數(shù)量及位置，確保組密鑰服務(wù)節(jié)點(diǎn)數(shù)量最少和網(wǎng)絡(luò)需求節(jié)點(diǎn)到組密鑰服務(wù)節(jié)點(diǎn)的路徑長(zhǎng)度最??；式(8)表示網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)i只能從一個(gè)組密鑰服務(wù)節(jié)點(diǎn)j中得到服務(wù)；式(9)表示網(wǎng)絡(luò)需求節(jié)點(diǎn)只能被組密鑰服務(wù)節(jié)點(diǎn)所服務(wù)；式(10)、式(11)表明ξij與ξj為二進(jìn)制變量。

3 組密鑰服務(wù)節(jié)點(diǎn)選址算法

3.1 基于常規(guī)p-median模型的選址算法

3.1.1 枚舉法

枚舉法是一種常用的精確算法，其思想簡(jiǎn)單，易于理解和操作，因此本文首先采用枚舉法解決p-median模型的選址問(wèn)題。算法的基本步驟如下。

1) 根據(jù)QKD網(wǎng)絡(luò)拓?fù)?，?gòu)建鄰接矩陣，運(yùn)用Flyod算法求出網(wǎng)絡(luò)的距離矩陣，并羅列出各個(gè)候選服務(wù)節(jié)點(diǎn)j(j∈J)到網(wǎng)絡(luò)需求節(jié)點(diǎn)i(i∈I)的距離。

3.1.2 貪婪算法

貪婪算法[10-11]是一種應(yīng)用較為廣泛的算法，其算法策略符合人的日常思維習(xí)慣，易于理解掌握，且具有收斂速度快，易于工程實(shí)現(xiàn)等優(yōu)勢(shì)。因此本文采用貪婪算法來(lái)解決p-median模型的選址問(wèn)題。

貪婪算法基本思想：以局部最優(yōu)解得到整體的最優(yōu)解，即為求得整體最優(yōu)解，依據(jù)某種貪婪策略，從問(wèn)題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過(guò)若干次的貪婪選擇，最終得出整個(gè)問(wèn)題的最優(yōu)解的方法。

定義1 (QKD網(wǎng)絡(luò)最短傳輸距離)：QKD網(wǎng)絡(luò)中所有網(wǎng)絡(luò)需求節(jié)點(diǎn)到服務(wù)節(jié)點(diǎn)的最短傳輸距離。

定理1QKD網(wǎng)絡(luò)最短傳輸距離與服務(wù)節(jié)點(diǎn)個(gè)數(shù)的函數(shù)f*(k)是一個(gè)非增函數(shù)。

證明：令f(k)為傳輸距離函數(shù)，而f*(k)為最短傳輸距離函數(shù)，兩者因網(wǎng)絡(luò)需求節(jié)點(diǎn)的分配不同而存在差異。顯然，f(k)≤f*(k)。

又因?yàn)閒*(k+1)≤f(k+1)成立，所以對(duì)于k∈{1,2,…,m}，f*(k+1)≤f*(k)成立，即定理1得證。

定理1表明隨著網(wǎng)絡(luò)中服務(wù)節(jié)點(diǎn)的增多，網(wǎng)絡(luò)需求節(jié)點(diǎn)到服務(wù)節(jié)點(diǎn)的傳輸距離只可能有兩種情況：傳輸距離保持不變或者減少。

基于定理1，本文采用的貪婪策略是：依據(jù)某一剔除原則，每次從候選服務(wù)節(jié)點(diǎn)集合中剔除一個(gè)服務(wù)節(jié)點(diǎn)，直到最后剩下p個(gè)服務(wù)節(jié)點(diǎn)。

剔除原則是：若從候選服務(wù)節(jié)點(diǎn)集合中剔除該服務(wù)節(jié)點(diǎn)，并將原屬于它的網(wǎng)絡(luò)需求節(jié)點(diǎn)分配給其他候選服務(wù)節(jié)點(diǎn)后，整個(gè)網(wǎng)絡(luò)的傳輸距離增加量最小。

利用貪婪算法解決常規(guī)p-median模型選址問(wèn)題的基本步驟：

1) 根據(jù)QKD網(wǎng)絡(luò)拓?fù)?，?gòu)建鄰接矩陣，運(yùn)用Flyod算法求出網(wǎng)絡(luò)的距離矩陣，并羅列出各個(gè)候選服務(wù)節(jié)點(diǎn)j(j∈J)到網(wǎng)絡(luò)需求節(jié)點(diǎn)i(i∈I)的距離。

2) 假設(shè)服務(wù)節(jié)點(diǎn)集S=J，即將所有候選服務(wù)節(jié)點(diǎn)均選中，依據(jù)就近原則，將所有網(wǎng)絡(luò)需求節(jié)點(diǎn)分配給相應(yīng)的候選服務(wù)節(jié)點(diǎn)。

3) 檢查集合S的元素個(gè)數(shù)，若|S|=p，其中|S|表示集合S的元素個(gè)數(shù)，則輸出集合S的元素及其個(gè)數(shù)，同時(shí)輸出網(wǎng)絡(luò)需求節(jié)點(diǎn)的分配結(jié)果，結(jié)束；若|S|>p，則執(zhí)行步驟4)。

4) 依據(jù)剔除原則，從集合S中確定并剔除該被剔除的元素，并轉(zhuǎn)3)。

3.2 基于改進(jìn)的p-median模型的選址算法

3.2.1 枚舉法

算法基本步驟如下：

1) 根據(jù)QKD網(wǎng)絡(luò)拓?fù)?，?gòu)建鄰接矩陣，運(yùn)用Flyod算法求出網(wǎng)絡(luò)的距離矩陣，并羅列出各個(gè)候選服務(wù)節(jié)點(diǎn)j(j∈J)到網(wǎng)絡(luò)需求節(jié)點(diǎn)i(i∈I)的距離。

3) 若minZp≤minZp+1，則輸出服務(wù)節(jié)點(diǎn)個(gè)數(shù)為p時(shí)Zp取得最小值時(shí)服務(wù)節(jié)點(diǎn)的位置及網(wǎng)絡(luò)需求節(jié)點(diǎn)的分配結(jié)果，并結(jié)束算法。

4) 若minZp≥minZp+1，則令p=p+1，執(zhí)行步驟2)。

3.2.2 貪婪算法

貪婪算法的基本思想是每一次貪婪都是當(dāng)前狀態(tài)下的局部最優(yōu)，以局部最優(yōu)解逐漸逼近整體最優(yōu)解。即在3.1.2節(jié)中服務(wù)節(jié)點(diǎn)集合S始終是貪婪算法選擇出的當(dāng)前狀態(tài)下使得Z最小的最優(yōu)組密鑰服務(wù)節(jié)點(diǎn)組合。因此，解決常規(guī)p-median模型選址問(wèn)題與改進(jìn)的p-median模型選址問(wèn)題，本質(zhì)上是一樣的，其算法的基本步驟如下：

1) 根據(jù)QKD網(wǎng)絡(luò)拓?fù)?，?gòu)建鄰接矩陣，運(yùn)用Flyod算法求出網(wǎng)絡(luò)的距離矩陣，并羅列出各個(gè)候選服務(wù)節(jié)點(diǎn)j(j∈J)到網(wǎng)絡(luò)需求節(jié)點(diǎn)i(i∈I)的距離。

2) 假設(shè)服務(wù)節(jié)點(diǎn)集S=J，即將所有候選服務(wù)節(jié)點(diǎn)均選中，依據(jù)就近原則，將所有網(wǎng)絡(luò)需求節(jié)點(diǎn)分配給相應(yīng)的候選服務(wù)節(jié)點(diǎn)。

4) 若minZp≥minZp-1，則輸出p個(gè)服務(wù)節(jié)點(diǎn)的位置及網(wǎng)絡(luò)需求節(jié)點(diǎn)的分配結(jié)果，并結(jié)束算法。

5) 若minZp≤minZp-1，則令p=p-1。且依據(jù)剔除原則，從集合S中確定并剔除該被剔除的元素，并轉(zhuǎn)步驟3)。剔除原則同3.1.2節(jié)所述。

4 兩種算法的性能分析

4.1 算 例

本文以求解質(zhì)量與求解耗兩個(gè)指標(biāo)來(lái)衡量算法性能。求解質(zhì)量指利用算法求得所得解與最優(yōu)解的比值。求解耗時(shí)指利用算法求解所需時(shí)間。為分析枚舉算法與貪婪算法的性能，選擇候選服務(wù)節(jié)點(diǎn)數(shù)量樣本N=10，12，15，20，25，30。

實(shí)驗(yàn)環(huán)境為：Windows7系統(tǒng)，CPU為Inter(R)Core(TM)i5-3570，主頻為3.40GHz，內(nèi)存為8GB，MatlabR2009a軟件。

由第3節(jié)可知，不確定數(shù)量p-median選址問(wèn)題的解決算法是基于確定數(shù)量p-median選址問(wèn)題，因此本文以確定數(shù)量p-median選址問(wèn)題為例，選定服務(wù)節(jié)點(diǎn)樣本為p=2，試驗(yàn)次數(shù)為50次。

4.2 算例結(jié)果與分析

表1與表2分別為求解質(zhì)量與求解耗時(shí)的實(shí)驗(yàn)數(shù)據(jù)。

表1 求解質(zhì)量實(shí)驗(yàn)數(shù)據(jù)

表2 求解耗時(shí)實(shí)驗(yàn)數(shù)據(jù) 秒

實(shí)驗(yàn)結(jié)論：從表1可知，利用貪婪算法，其求解質(zhì)量基本保持不變，與最優(yōu)解存在一定偏離，但是偏離值在可接受范圍之內(nèi)。由表2可知，在區(qū)間[10,20]間枚舉算法與貪婪算法求解耗時(shí)差別不大，但是超過(guò)20個(gè)節(jié)點(diǎn)，枚舉算法的求解耗時(shí)顯著增加，而貪婪算法的增幅相對(duì)較小。

貪婪算法是一種近似算法，通過(guò)求解局部最優(yōu)，逐步逼近整體最優(yōu)，其求解結(jié)果與最優(yōu)值可能存在一定偏差。由于其局部最優(yōu)求解思想，不考慮各種可能的整體，因此大大簡(jiǎn)單了其每一步的求解規(guī)模，使得其求解耗時(shí)短，時(shí)間復(fù)雜度只有二次方級(jí)。兩種算法的性能比較如表3所示。

表3 兩種算法的性能比較

城域網(wǎng)大概需要十幾個(gè)QKD節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)量較少，由上面的分析結(jié)果可知，枚舉算法進(jìn)行選址比較合適；而城際網(wǎng)節(jié)點(diǎn)數(shù)量較多，可能成百上千，枚舉算法已經(jīng)失效，因此選擇貪婪算法進(jìn)行選址更為合適。

5 結(jié) 語(yǔ)

組密鑰服務(wù)節(jié)點(diǎn)的選址問(wèn)題直接關(guān)系到網(wǎng)絡(luò)服務(wù)性能，本文重點(diǎn)研究了其選址算法。針對(duì)組密鑰服務(wù)節(jié)點(diǎn)數(shù)量確定和不確定兩種情況，分別構(gòu)建了數(shù)學(xué)模型，并設(shè)計(jì)了枚舉與貪婪兩種算法，通過(guò)仿真模擬實(shí)驗(yàn)比較了兩種算法的性能，并分析了兩種算法各自不同的應(yīng)用場(chǎng)景。結(jié)果表明，本文設(shè)計(jì)的算法原理簡(jiǎn)單，步驟清晰，操作方便，易于掌握，具有一定的實(shí)際意義和參考價(jià)值。

[2] 徐大川,杜東雷,吳晨晨.設(shè)施選址問(wèn)題的近似算法綜述[J].數(shù)學(xué)進(jìn)展,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下對(duì)電動(dòng)出租車充電站的選址研究[J].工業(yè)工程與管理,2013,18(6):1-6.

[10] 饒衛(wèi)振,金淳,陸林濤.考慮邊位置信息的求解ETSP問(wèn)題改進(jìn)貪婪算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(4):836-850.

[11] 張彩慶,趙璐.基于P-中值模型的電網(wǎng)檢修公司分部選址模型[J].系統(tǒng)管理學(xué)報(bào),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。石磊，碩士生，主研領(lǐng)域：信息安全。郭義喜，副教授。蘇錦海，教授。

TP393.04

A

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