石 磊 郭義喜 蘇錦海

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

量子密鑰分發(fā)網絡組密鑰服務節(jié)點選址算法

石 磊 郭義喜 蘇錦海

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

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

量子密鑰分發(fā)(QKD)網絡 組密鑰服務節(jié)點 選址問題 p-median 枚舉法 貪婪算法

0 引 言

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

目前，集中式組密鑰協商思想逐漸引起關注?；诜展?jié)點的組密鑰協商方案是一種典型的集中式組密鑰協商方案。它的基本思想是：在一個QKD網絡中設定若干個具有密鑰管理權限的組密鑰服務節(jié)點，通過這些服務節(jié)點集中為組成員提供組密鑰服務。

組密鑰服務節(jié)點是整個網絡的服務支撐點和流量瓶頸，其帶寬和建設成本相對較高，其部署直接關系到網絡的性能和成本，其選址算法是整個組密鑰協商方案的核心。

組密鑰服務節(jié)點選址問題是設施選址問題中的一種，多數選址模型[1-2]均能應用于組密鑰服務節(jié)點選址問題中。p-median[3-5]是設施選址問題中較為經典的一種選址模型，其目標是確定P個設施位置，使得網絡中所有需求點到設施的權重距離之和最短。

本文根據QKD網絡組密鑰協商的特點，基于p-median模型的適用性及組密鑰服務節(jié)點的選址需求，對組密鑰服務節(jié)點選址問題進行研究，分別針對組密鑰服務節(jié)點數量確定和不確定兩種情況，構建不同選址模型，設計不同應用場景下的實現算法。

1 QKD網絡組密鑰協商思想

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

圖1 典型的QKD密鑰網絡結構

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

集中式生成思想：將網絡節(jié)點分為組密鑰服務節(jié)點和普通網絡節(jié)點，后者為前者提供組密鑰服務。一個網絡中設定若干個組密鑰服務節(jié)點，組密鑰由組密鑰服務節(jié)點集中生成，而普通網絡節(jié)點只負責申請組密鑰。

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

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

2 組密鑰服務節(jié)點選址模型

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

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

1)QKD網絡拓撲固定，候選服務節(jié)點集合中的每個組密鑰服務節(jié)點具有相同的服務能力，建設成本也相同。

2) 一個組密鑰服務節(jié)點被一個組密鑰服務占用，若有其他組密鑰服務請求到達同一組密鑰服務節(jié)點，列入等待隊列。

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

優(yōu)化目標：在固定的QKD網絡拓撲下，根據給定的候選服務節(jié)點集合和最終的服務節(jié)點數量P，確定組密鑰服務節(jié)點最優(yōu)位置，使得網絡中其他節(jié)點到組密鑰服務節(jié)點的路徑長度最小。

約束條件：

1) 組密鑰服務節(jié)點的選擇必須符合網絡的拓撲結構。

2) 每一個網絡需求節(jié)點都必須有一個組密鑰服務節(jié)點為其提供組密鑰服務(默認一個網絡需求節(jié)點只能有一個組密鑰服務節(jié)點為其提供服務)。

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

為方便形式化描述，對以下變量進行定義。

N={v0,v1,…,vn-1}，其中N為網絡節(jié)點集合，下標為網絡節(jié)點標號。

集合I?N,其中集合I為網絡需求節(jié)點集合；集合J?N，其中集合J為候選組密鑰服務節(jié)點集合，其元素個數為k。

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

d(i,j)為網絡需求節(jié)點i與候選組密鑰服務節(jié)點j之間的最短路徑長度。

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

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

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

優(yōu)化目標：

(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)化目標函數，使得網絡需求節(jié)點到組密鑰服務節(jié)點的路徑長度最??；式(2)表示網絡中任意一個節(jié)點i只能從一個組密鑰服務節(jié)點j中得到服務；式(3)表示網絡中需要建立的組密鑰服務節(jié)點的數量；式(4)表示網絡需求節(jié)點只能被組密鑰服務節(jié)點所服務；式(5)、式(6)表明ξij與ξj為二進制變量。

2.2 改進的p-median模型構建

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

改進的p-median數學模型：

優(yōu)化目標：

(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)化目標函數，有兩個優(yōu)化目標，需要同時確定組密鑰服務節(jié)點的數量及位置，確保組密鑰服務節(jié)點數量最少和網絡需求節(jié)點到組密鑰服務節(jié)點的路徑長度最??；式(8)表示網絡中任意一個節(jié)點i只能從一個組密鑰服務節(jié)點j中得到服務；式(9)表示網絡需求節(jié)點只能被組密鑰服務節(jié)點所服務；式(10)、式(11)表明ξij與ξj為二進制變量。

3 組密鑰服務節(jié)點選址算法

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

3.1.1 枚舉法

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

1) 根據QKD網絡拓撲，構建鄰接矩陣，運用Flyod算法求出網絡的距離矩陣，并羅列出各個候選服務節(jié)點j(j∈J)到網絡需求節(jié)點i(i∈I)的距離。

3.1.2 貪婪算法

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

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

定義1 (QKD網絡最短傳輸距離)：QKD網絡中所有網絡需求節(jié)點到服務節(jié)點的最短傳輸距離。

定理1QKD網絡最短傳輸距離與服務節(jié)點個數的函數f*(k)是一個非增函數。

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

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

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

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

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

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

1) 根據QKD網絡拓撲，構建鄰接矩陣，運用Flyod算法求出網絡的距離矩陣，并羅列出各個候選服務節(jié)點j(j∈J)到網絡需求節(jié)點i(i∈I)的距離。

2) 假設服務節(jié)點集S=J，即將所有候選服務節(jié)點均選中，依據就近原則，將所有網絡需求節(jié)點分配給相應的候選服務節(jié)點。

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

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

3.2 基于改進的p-median模型的選址算法

3.2.1 枚舉法

算法基本步驟如下：

1) 根據QKD網絡拓撲，構建鄰接矩陣，運用Flyod算法求出網絡的距離矩陣，并羅列出各個候選服務節(jié)點j(j∈J)到網絡需求節(jié)點i(i∈I)的距離。

3) 若minZp≤minZp+1，則輸出服務節(jié)點個數為p時Zp取得最小值時服務節(jié)點的位置及網絡需求節(jié)點的分配結果，并結束算法。

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

3.2.2 貪婪算法

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

1) 根據QKD網絡拓撲，構建鄰接矩陣，運用Flyod算法求出網絡的距離矩陣，并羅列出各個候選服務節(jié)點j(j∈J)到網絡需求節(jié)點i(i∈I)的距離。

2) 假設服務節(jié)點集S=J，即將所有候選服務節(jié)點均選中，依據就近原則，將所有網絡需求節(jié)點分配給相應的候選服務節(jié)點。

4) 若minZp≥minZp-1，則輸出p個服務節(jié)點的位置及網絡需求節(jié)點的分配結果，并結束算法。

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

4 兩種算法的性能分析

4.1 算 例

本文以求解質量與求解耗兩個指標來衡量算法性能。求解質量指利用算法求得所得解與最優(yōu)解的比值。求解耗時指利用算法求解所需時間。為分析枚舉算法與貪婪算法的性能，選擇候選服務節(jié)點數量樣本N=10，12，15，20，25，30。

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

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

4.2 算例結果與分析

表1與表2分別為求解質量與求解耗時的實驗數據。

表1 求解質量實驗數據

表2 求解耗時實驗數據 秒

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

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

表3 兩種算法的性能比較

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

5 結 語

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

[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].工業(yè)工程與管理,2013,18(6):1-6.

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

[11] 張彩慶,趙璐.基于P-中值模型的電網檢修公司分部選址模型[J].系統(tǒng)管理學報,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