徐雅斌，張梅舒，李艷平

(1. 北京信息科技大學網絡文化與數(shù)字傳播北京市重點實驗室 北京 朝陽區(qū) 100101；2. 北京信息科技大學計算機學院 北京 朝陽區(qū) 100101)

量子密鑰分發(fā)(quantum key distribution, QKD)技術利用量子密鑰進行量子編碼并傳遞，可以為通信雙方提供理論上無條件安全的共享密鑰[1]。將多個點到點QKD網絡連接起來組成的量子密鑰分發(fā)網絡可以提供多用戶、長距離的密鑰服務。

目前，國內外提出的QKD網絡主要有3種[2-3]：光學中繼QKD網絡、量子中繼QKD網絡及信任中繼QKD網絡。其中，基于信任中繼的QKD網絡技術由于不受覆蓋范圍和用戶數(shù)量的限制，是目前建設大規(guī)模、實用化保密通信網絡的首選方案。但是，基于信任中繼的QKD網絡在進行端到端密鑰協(xié)商時，可能存在多條傳輸密鑰的路徑，這就需要進行選路。

在當前密鑰生成量難以滿足需求的情況下，相對最近路徑的選擇，網絡中密鑰的消耗量和密鑰傳輸?shù)陌踩燥@得更為重要。即在信任中繼QKD網絡中，路由選擇的關注點發(fā)生了根本變化，需要與之相適應的路由選擇算法。因此，研究和設計適合大規(guī)模QKD網路的高效路由算法對于促進量子通信網絡的發(fā)展具有重要意義。

當前，針對信任中繼QKD網絡路由問題的研究主要有單路徑和多路徑兩種設計方式[4-5]。對于現(xiàn)有的單路徑路由方案[3-6]，密文轉發(fā)總是在同一條路徑上進行，在網絡拓撲等信息已知的情況下，各中間節(jié)點是可預測的，易受到竊聽而威脅通信安全。多路徑路由方案[7-10]通過提供多條不同路徑同時傳輸信息，提高了網絡服務質量，增強了網絡安全性，但消耗的本地密鑰量較多，傳輸效率較低。

為了解決單路徑路由安全性不足的問題和多路徑路由的密鑰浪費問題，文獻[11]提出一種將當前節(jié)點的所有鄰居節(jié)點作為下一跳的候選，以一定概率隨機選擇下一跳的自適應路由算法。文獻[12]在此基礎上通過添加一種帶標簽的隨機路徑策略，以減少公共節(jié)點的數(shù)量，避免產生環(huán)路。文獻[13]基于寬帶利用率分別提出了針對單路徑和多路徑的路由算法，其中單路徑路由算法主要考慮網絡的服務質量和密鑰管理，而多路徑路由算法則著重考慮提高網絡的安全性，從而減少量子密鑰分配網絡的密鑰消耗，提高密鑰服務效率。

針對多路徑解決方案，文獻[14]設計了基于格型拓撲結構的量子密鑰分發(fā)網絡方案，提出了一種適合量子密鑰分發(fā)網絡的冗余路由算法，并對其呼損性能進行分析。文獻[15]提出了多隨機路徑方案，有效解決了部分受信任的中繼網絡的致命安全性問題。文獻[16]在選路中考慮到了密鑰量，提出了一種基于RIP協(xié)議的隨機路由算法。具體做法是：首先根據(jù)改進的RIP協(xié)議找到所有最短路徑，然后選路時在多個密鑰充足的下一跳中隨機選擇一個，直至到達目的節(jié)點。

為了進一步提高多路徑解決方案的質量和效率，文獻[17]提出了基于光交換機的量子保密通信網絡路由算法，保證了較高的安全成碼率，提高了通信質量，然后在考慮鏈路剩余密鑰量和最短路徑的基礎上提出了基于可信中繼的量子保密通信網絡隨機路由算法。文獻[18]提出了一種基于距離矢量和剩余密鑰的隨機路由算法，在獲得所有最短路徑后，通信密鑰位可以在剩余密鑰位足夠多的任意路徑上隨機傳輸，提供更高的安全性。

通過分析發(fā)現(xiàn)，在已提出的針對信任中繼的QKD網絡隨機路由算法中，有些忽略了密鑰量對信任中繼網絡路由的影響，有些雖然在一定程度上解決了單路徑路由的安全性低和多路徑路由的密鑰浪費問題，但在遇到密鑰量不足的情況下，就要中斷通信，重新開始進行密鑰傳遞，從而造成密鑰的浪費和成功率的降低。因而，在選路失敗后，應考慮如何充分利用已經進行的密鑰傳遞過程，以提高傳輸效率和密鑰傳遞成功率，節(jié)約密鑰。

因此，本文提出一種改進的多路徑隨機路由算法。該算法找到源節(jié)點到目的節(jié)點的3條最短路徑，在選路時隨機選擇其中1條，使竊聽者無從獲知確切的密鑰傳輸路徑，從而提高密鑰傳輸?shù)陌踩浴４送?，在選路過程中加入回溯策略，當選路出現(xiàn)密鑰量不足而無法推進時，通過最短路徑的回溯，找到新的可用路徑，從而提高選路的成功率，并最大程度地減少選路時間和密鑰消耗量。

1 基于信任中繼的QKD網絡

1.1 信任中繼QKD網絡結構

圖1是基于信任中繼的QKD網絡結構[5]，網絡由用戶、信任中繼節(jié)點和鏈路3部分組成，信任中繼節(jié)點之間通過鏈路連接在一起。由用戶發(fā)起通信請求，各信任中繼節(jié)點負責轉發(fā)密文和密鑰，在網絡中起中繼交換的作用。

圖1 信任中繼QKD網絡結構

信任中繼QKD網絡中有兩條信道，一條是用于傳輸密鑰的量子信道，另一條是用于傳輸路由信息和加密信息的經典信道。在圖1中，實線表示量子信道，是兩節(jié)點間的直通信道；虛線表示經典信道，可以是兩節(jié)點間的直連信道，也可以是經由其他節(jié)點轉接的信道。由于兩個信道的傳輸內容和傳輸方式都不同，因此量子信道的路由方式不能直接使用經典網絡中成熟的路由技術。本文所提及的QKD網絡特指由量子信道組成的網絡。

1.2 信任中繼密鑰傳輸原理

信任中繼密鑰傳輸原理如圖2，假定用戶A要和用戶B進行密鑰傳遞，中繼節(jié)點1和中繼節(jié)點2共享密鑰K1，中繼節(jié)點2和中繼節(jié)點3共享密鑰K2，中繼節(jié)點3與用戶B共享密鑰K3。用戶A和中繼節(jié)點1協(xié)商出全局密鑰K后(通信密鑰)，通過中繼節(jié)點1、2和3傳遞給用戶B。傳遞過程中，中繼節(jié)點先解密后加密，如中繼節(jié)點2從中繼節(jié)點1接收到K⊕K1，先用與中繼節(jié)點1共享的K1解密得到K，再用與中繼節(jié)點3共享的密鑰K2加密得到K⊕K2，然后發(fā)送給中繼節(jié)點3。

圖2 信任中繼密鑰傳輸原理

由于相鄰中繼節(jié)點共享的密鑰是通過密鑰分發(fā)產生的，具有無條件安全性，因而節(jié)點之間進行密鑰傳輸時，可以保證密鑰不被泄露；又由于中繼節(jié)點是可以信任的，所以基于信任中繼的密鑰傳遞在理論上是安全的。

2 隨機路由算法

2.1 問題分析

文獻[16]提出一種基于RIP協(xié)議的隨機路由算法，該算法通過改進基于距離矢量的路由算法擴展路由表，為到達某一目的地址的中繼節(jié)點添加多個下一跳，進而得到源中繼節(jié)點到目的中繼節(jié)點的多條最短路徑；在選路時，將鏈路上的剩余密鑰量考慮在內，在存在多個密鑰量充足的下一跳中繼節(jié)點的情況下，在其中隨機地選擇一個，然后逐跳轉發(fā)，直到轉發(fā)至目的中繼節(jié)點。

雖然該方法路徑最短且安全性較高，但仍然存在以下不足：1) 只適用于源節(jié)點和目的節(jié)點之間有多條最短路徑的情況，如果源、目的節(jié)點之間只有一條最短路徑，該算法就會失效；2) 在選中密鑰量不足的下一跳節(jié)點時就將中斷傳輸，按新的最短路徑從頭開始密鑰協(xié)商，浪費資源且成功率較低。

針對該隨機路由算法的不足，本文將路由算法進行改進，并提出一種基于回溯的QKD網絡隨機路由選擇方案。

2.2 改進的隨機路由算法

針對文獻[16]不適用于源、目的節(jié)點之間只有一條最短路徑的問題，本文提出一種尋找兩個節(jié)點之間多條路徑的方法：1) 采用文獻[6]改進的Dijkstra算法找到源節(jié)點到目的節(jié)點的所有最短路徑；2) 判斷最短路徑的條數(shù)：如果路徑條數(shù)少于3，就在網絡中刪除當前的最短路徑，繼續(xù)找最短路徑，直到找到3條最短路徑；如果路徑條數(shù)不少于3，就從中隨機選擇3條最短路徑；3) 將選出的3條路徑加入路由表中。

本文提出的隨機路由算法的思想是：從源節(jié)點開始進行尋路，在當前節(jié)點與目的節(jié)點存在多條傳輸路徑時，查看鏈路上的剩余密鑰量，在剩余密鑰量足夠的所有鏈路中隨機選擇一條，逐跳選擇中繼節(jié)點來轉發(fā)密鑰。當選擇的節(jié)點不存在密鑰量足夠的鏈路時，判斷該節(jié)點是否存在可回溯的中繼節(jié)點。如果存在，就回溯；如果不存在，結束通信，重新開始協(xié)商密鑰。

為了找到可回溯的中繼節(jié)點，本文設計一種標記回溯點的方法。在路由表中添加一個新項——回溯點，用于標記該節(jié)點的回溯點。即，如果所選路徑中某節(jié)點的鏈路密鑰量不足，此節(jié)點就查找其回溯點。如果存在，就回溯到該點；如果不存在，就結束此次密鑰協(xié)商。標記回溯點的算法步驟如下：

1) 初始情況下，路由表中每一項的回溯點均為空；2) 從源中繼節(jié)點開始，判斷當前節(jié)點到目的節(jié)點的下一跳個數(shù)：如果個數(shù)為1，將下一跳的回溯點標記為當前節(jié)點的回溯點的值；如果個數(shù)大于1，將多個下一跳的回溯點標記為當前節(jié)點。

圖3是一個簡單的例子，如果Alice要與Bob通信，計算得到3條最短路徑：P1：1→2→3→4；P2：1→2→5→4；P3：1→8→6→4。所以，節(jié)點2,8的回溯點為1；節(jié)點3,5的回溯點為2。

圖3 標記回溯點的例子

各節(jié)點的路由表如表1～表6所示。

表1 節(jié)點1的路由表

表6 節(jié)點6的路由表

表2 節(jié)點2的路由表

表3 節(jié)點3的路由表

表5 節(jié)點8的路由表

本文提出的隨機路由選擇的算法步驟為：

1) 找到源中繼節(jié)點到目的中繼節(jié)點的3條最短路徑，并將下一跳信息添加到路由表；

2) 相鄰中繼節(jié)點利用量子密鑰分發(fā)協(xié)議協(xié)商出量子密鑰K，并存儲；

3) 源量子通信終端與其相連的中繼節(jié)點(源節(jié)點)協(xié)商出本次通信的通信密鑰Kc；

4) 從源節(jié)點出發(fā)，首先對收到的密文進行解密，然后根據(jù)目的地址查找路由表，判斷路由表中到此次協(xié)商的目的地址的下一跳個數(shù)N(如果是回溯到此節(jié)點，則去掉選路失敗的下一跳)：

① 如果N=1，執(zhí)行步驟②；如果N＞1，執(zhí)行步驟③；

② 判斷下一跳相鄰中繼節(jié)點中存儲的量子密鑰的比特數(shù)是否大于通信密鑰的比特數(shù)。若是，將通信密鑰加密后轉發(fā)至下一跳相鄰中繼節(jié)點，執(zhí)行步驟④，否則，執(zhí)行步驟5)；

③ 將收到的密鑰存儲，然后在N個下一跳相鄰中繼節(jié)點中選出量子密鑰的比特數(shù)大于通信密鑰的比特數(shù)的中繼節(jié)點，并在其中隨機地選取一個，然后將通信密鑰加密后轉發(fā)至該相鄰中繼節(jié)點，執(zhí)行步驟④；對于多個下一跳相鄰中繼節(jié)點中存儲的量子密鑰的比特數(shù)均小于通信密鑰的比特數(shù)的情況，執(zhí)行步驟5)；

④ 對選取的相鄰節(jié)點標記回溯點，該節(jié)點收到加密后的通信密鑰，利用存儲的量子密鑰對其進行解密，并判斷當前中繼節(jié)點是否為目的中繼節(jié)點。若是，則源中繼節(jié)點與目的中繼節(jié)點端到端的通信密鑰建立成功，源中繼節(jié)點利用該通信密鑰Kc對數(shù)據(jù)加密進行傳輸；否則，根據(jù)目的地址查找路由表，返回步驟①；

5) 查找該節(jié)點的回溯點，判斷回溯點是否存在：

① 如果存在，通知回溯點本路徑通信失敗，回溯點執(zhí)行步驟4)；② 如果不存在，此次密鑰協(xié)商失敗，執(zhí)行步驟6)；

6) 釋放源量子通信終端與目的量子通信終端間的連接。

2.3 實例分析

以圖4為例，假設此次通信所需密鑰為10，圖中鏈路上的數(shù)字代表路徑上剩余密鑰量。首先，尋找節(jié)點1到節(jié)點5之間的所有最短路徑，找到1條最短為：1-2-6-5。由于當前路徑條數(shù)少于3，繼續(xù)尋找節(jié)點1到節(jié)點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。

圖4 路由選擇實例

路由選擇過程如下：

1) 從源節(jié)點1開始，查找路由表，得到的到達節(jié)點5的路徑有兩條，由于兩條鏈路的密鑰量都充足，因而隨機選擇下一跳，假設選擇節(jié)點2；

2) 由于從節(jié)點1經節(jié)點2到節(jié)點5有多條路徑，因而將節(jié)點2的回溯點標記為1；

3) 從節(jié)點2開始，進一步查找路由表，得到的到達節(jié)點5的路徑有兩條，分別為節(jié)點3和節(jié)點6，由于兩條鏈路的密鑰量都充足，因而隨機選擇下一跳節(jié)點，假定選擇節(jié)點6；

4) 由于從節(jié)點2經節(jié)點6到節(jié)點5有多條路徑，因而將節(jié)點6的回溯點標記為節(jié)點2；

5) 從節(jié)點6開始進一步查找路由表，得到的到達節(jié)點5的下一跳節(jié)點即為節(jié)點5。但鏈路6-5的密鑰量不足，因而回到它的回溯點，即節(jié)點2；

6) 從節(jié)點2開始，去掉選路失敗的下一跳節(jié)點6，進一步查找路由表，得到到達節(jié)點5的唯一一個下一跳節(jié)點為節(jié)點3，且密鑰量充足，因此確定下一跳節(jié)點為節(jié)點3；

7) 由于從節(jié)點2經節(jié)點3到節(jié)點5有多條路徑，因而將節(jié)點3的回溯點標記為節(jié)點2；

8) 從節(jié)點3開始，進一步查找路由表，得到到達節(jié)點5的唯一的下一跳節(jié)點為節(jié)點4，且密鑰量充足，因此確定下一跳節(jié)點為節(jié)點4；

9) 但由于從節(jié)點3經節(jié)點4到節(jié)點5只有一條路徑，因此將節(jié)點4的回溯點仍然標記為節(jié)點2；

10) 從節(jié)點4開始，進一步查找路由表，發(fā)現(xiàn)可直接到達節(jié)點5，且鏈路的密鑰量充足，因而可直接將密鑰轉發(fā)給節(jié)點5。

至此，算法結束。

由此算法可以看出，當發(fā)現(xiàn)密鑰量不足的鏈路后，本算法就回溯到存在其他最短路徑的節(jié)點，由此以最小的代價沿著新的最短路徑進行路由選擇。

3 實驗及分析

本文對圖3的網絡拓撲做進一步的擴展，采用圖5所示的網絡拓撲圖，對使用單路徑路由算法、多路徑路由算法、文獻[16]提出的隨機單路徑路由算法以及本文提出的算法來實現(xiàn)Alice和Bob之間的密鑰傳遞情況進行仿真實驗。

圖5 實驗的網絡拓撲結構

3.1 實驗環(huán)境及性能指標

本實驗的硬件環(huán)境是Intel(R) Core(TM) i7-4790 CPU @ 3.60 GHz，8.0 GB RAM，Windows 7專業(yè)版操作系統(tǒng)，Visual Studio 2015，算法的實現(xiàn)語言為C++。

本文采用以下3個性能指標進行評價和分析：1)選路成功率。選擇路徑成功與否是路由算法可行與否的關鍵，該指標用來評價路由算法的可行性。2) 密鑰消耗量。充足的密鑰量是信任中繼量子網絡密鑰傳遞的必要條件，密鑰消耗的多少直接影響到接下來的密鑰通信，該指標用來評價路由算法的效率。3) 選路時間。一次密鑰傳遞的時間對路由的效率影響很大，該指標用來評價路由算法的效率。

3.2 選路成功率比較

針對圖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次，統(tǒng)計其選路成功次數(shù)和選路成功率(選路成功率=選路成功次數(shù)/實驗次數(shù))。

4種不同算法的選路成功率情況如圖6所示?？梢钥闯?，本算法在一條鏈路密鑰量不足的時候，選路成功率都是100%，選路效果最好；而文獻[16]提出的隨機單路徑路由算法，當存在鏈路密鑰量不足時，成功率很難達到100%；對于單路徑路由算法，當鏈路A-B、B-C、C-D和D-E密鑰量不足時，選路成功率為0，其他情況選路成功率為100%；對于多路徑路由算法，存在密鑰量不足鏈路時，選路成功率為0。

圖6 4種不同算法的選路成功率對比圖

分析原因如下：單路徑路由算法在選路時選擇一條路徑，當選中的路徑的鏈路密鑰量不足時，就會宣告選路失??；多路徑路由算法在選路時，雖然可選擇多條路徑(這里為3條路徑)，但無論哪條路徑的鏈路密鑰量不足，都會宣告選路失敗；文獻[16]提出的隨機單路徑路由算法在選路時隨機選擇一條，可能會選中密鑰量不足的鏈路，進而導致選路失??；而本文提出的算法，選路時會從3條最短路徑中隨機選擇一條，當選中的最短鏈路密鑰量不足時，就會回溯到有具有多條路徑的節(jié)點，繼續(xù)進行路由選擇，而不是宣告選路失敗，因而選路代價較低，成功率較高。因此，相對于已存在的針對QKD網絡的路由算法來說，本文提出的路由選擇算法的選路成功率更高，效果更好。

3.3 密鑰消耗量比較

假設本次密鑰傳遞需要的密鑰量為10。用K1、K2、K3和K4分別代表4種算法的密鑰消耗量，其中，K1表示單路徑路由的密鑰消耗量，K2表示多路徑路由的密鑰消耗量，K3表示文獻[16]的隨機單路徑路由的密鑰消耗量，K4表示本文算法的密鑰消耗量。

表4 節(jié)點5的路由表

密鑰消耗量比較分以下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)；而當選中的鏈路密鑰量不足時，本算法將回溯到回溯點繼續(xù)進行密鑰傳遞，直至選路成功，則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種算法，效率更高。

表7 4種算法的密鑰消耗量的對比

3.4 選路時間比較

由單路徑路由、多路徑路由和文獻[16]提出的隨機路由算法的選路原理可知，3種方法的選路時間相差無幾。本實驗只比較文獻[16]算法與本算法的選路時間。

對于文獻[16]的路由算法，當選擇的路徑密鑰量不足時，就中斷通信，重新開始進行密鑰傳遞。為了比較兩個算法的選路時間，本實驗設定密鑰產生速率為100單位/s，當文獻[16]的算法失敗后，更新密鑰量，重新開始密鑰傳遞，直到密鑰傳遞成功。將每次的時間相加，即可得到選路時間。

本實驗利用圖5所示的網絡，采用本文提出的算法進行多次實驗，記錄20次有回溯的選路時間；采用文獻[16]的算法進行多次實驗，記錄20次選擇路徑失敗后重新進行選路的選路時間。對比結果如圖7所示。

圖7 選路時間的對比

由圖7可知，本算法的選路時間為0.03～0.06 s，而算法[16]的選路時間為0.08～0.12 s。顯而易見，本算法的選路時間較短，效率較高。

上述實驗及分析結果表明：相對于已有的單路徑路由算法、多路徑路由算法和隨機單路徑路由算法，本算法在密鑰量不足的網絡中有更好的選路成功率、更少的密鑰消耗量和更短的選路時間。

4 結 束 語

本文主要針對基于信任中繼的量子密鑰網絡的路由問題展開研究，分析了現(xiàn)有路由方案存在的問題，提出了一種隨機路由方案。該方案通過改進的路由算法找到兩點之間的3條最短路徑，從而保證有多條較短路徑；在選路過程中，隨機選擇其中的一條，安全性較高；遇到密鑰量不足的鏈路時，回溯到有其他路徑的節(jié)點，節(jié)省密鑰量并提高了密鑰傳輸效率。實驗及分析結果表明，本算法不僅適用范圍廣，并且在選路時間、密鑰消耗量以及密鑰傳輸效率方面有一定的優(yōu)勢。

本文工作得到網絡文化與數(shù)字傳播北京市重點實驗室(ICDDXN004)的資助，在此表示感謝。