基于回溯的QKD網(wǎng)絡(luò)隨機(jī)路由選擇算法研究

徐雅斌，張梅舒，李艷平

(1. 北京信息科技大學(xué)網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室 北京 朝陽(yáng)區(qū) 100101；2. 北京信息科技大學(xué)計(jì)算機(jī)學(xué)院 北京 朝陽(yáng)區(qū) 100101)

量子密鑰分發(fā)(quantum key distribution, QKD)技術(shù)利用量子密鑰進(jìn)行量子編碼并傳遞，可以為通信雙方提供理論上無(wú)條件安全的共享密鑰[1]。將多個(gè)點(diǎn)到點(diǎn)QKD網(wǎng)絡(luò)連接起來(lái)組成的量子密鑰分發(fā)網(wǎng)絡(luò)可以提供多用戶、長(zhǎng)距離的密鑰服務(wù)。

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

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

當(dāng)前，針對(duì)信任中繼QKD網(wǎng)絡(luò)路由問(wèn)題的研究主要有單路徑和多路徑兩種設(shè)計(jì)方式[4-5]。對(duì)于現(xiàn)有的單路徑路由方案[3-6]，密文轉(zhuǎn)發(fā)總是在同一條路徑上進(jìn)行，在網(wǎng)絡(luò)拓?fù)涞刃畔⒁阎那闆r下，各中間節(jié)點(diǎn)是可預(yù)測(cè)的，易受到竊聽(tīng)而威脅通信安全。多路徑路由方案[7-10]通過(guò)提供多條不同路徑同時(shí)傳輸信息，提高了網(wǎng)絡(luò)服務(wù)質(zhì)量，增強(qiáng)了網(wǎng)絡(luò)安全性，但消耗的本地密鑰量較多，傳輸效率較低。

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

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

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

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

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

1 基于信任中繼的QKD網(wǎng)絡(luò)

1.1 信任中繼QKD網(wǎng)絡(luò)結(jié)構(gòu)

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

圖1 信任中繼QKD網(wǎng)絡(luò)結(jié)構(gòu)

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

1.2 信任中繼密鑰傳輸原理

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

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

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

2 隨機(jī)路由算法

2.1 問(wèn)題分析

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

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

針對(duì)該隨機(jī)路由算法的不足，本文將路由算法進(jìn)行改進(jìn)，并提出一種基于回溯的QKD網(wǎng)絡(luò)隨機(jī)路由選擇方案。

2.2 改進(jìn)的隨機(jī)路由算法

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

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

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

1) 初始情況下，路由表中每一項(xiàng)的回溯點(diǎn)均為空；2) 從源中繼節(jié)點(diǎn)開(kāi)始，判斷當(dāng)前節(jié)點(diǎn)到目的節(jié)點(diǎn)的下一跳個(gè)數(shù)：如果個(gè)數(shù)為1，將下一跳的回溯點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)的回溯點(diǎn)的值；如果個(gè)數(shù)大于1，將多個(gè)下一跳的回溯點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)。

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

圖3 標(biāo)記回溯點(diǎn)的例子

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

表1 節(jié)點(diǎn)1的路由表

表6 節(jié)點(diǎn)6的路由表

表2 節(jié)點(diǎn)2的路由表

表3 節(jié)點(diǎn)3的路由表

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 實(shí)例分析

以圖4為例，假設(shè)此次通信所需密鑰為10，圖中鏈路上的數(shù)字代表路徑上剩余密鑰量。首先，尋找節(jié)點(diǎn)1到節(jié)點(diǎn)5之間的所有最短路徑，找到1條最短為：1-2-6-5。由于當(dāng)前路徑條數(shù)少于3，繼續(xù)尋找節(jié)點(diǎn)1到節(jié)點(diǎn)5之間的所有最短路徑，找到的結(jié)果為：1-10-3-4-5，1-2-3-4-5和1-9-8-7-5，至此，獲得3條最短路徑。隨機(jī)選擇其中的2條，假定選擇的結(jié)果為：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 路由選擇實(shí)例

路由選擇過(guò)程如下：

1) 從源節(jié)點(diǎn)1開(kāi)始，查找路由表，得到的到達(dá)節(jié)點(diǎn)5的路徑有兩條，由于兩條鏈路的密鑰量都充足，因而隨機(jī)選擇下一跳，假設(shè)選擇節(jié)點(diǎn)2；

2) 由于從節(jié)點(diǎn)1經(jīng)節(jié)點(diǎn)2到節(jié)點(diǎn)5有多條路徑，因而將節(jié)點(diǎn)2的回溯點(diǎn)標(biāo)記為1；

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

4) 由于從節(jié)點(diǎn)2經(jīng)節(jié)點(diǎn)6到節(jié)點(diǎn)5有多條路徑，因而將節(jié)點(diǎn)6的回溯點(diǎn)標(biāo)記為節(jié)點(diǎn)2；

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

6) 從節(jié)點(diǎn)2開(kāi)始，去掉選路失敗的下一跳節(jié)點(diǎn)6，進(jìn)一步查找路由表，得到到達(dá)節(jié)點(diǎn)5的唯一一個(gè)下一跳節(jié)點(diǎn)為節(jié)點(diǎn)3，且密鑰量充足，因此確定下一跳節(jié)點(diǎn)為節(jié)點(diǎn)3；

7) 由于從節(jié)點(diǎn)2經(jīng)節(jié)點(diǎn)3到節(jié)點(diǎn)5有多條路徑，因而將節(jié)點(diǎn)3的回溯點(diǎn)標(biāo)記為節(jié)點(diǎn)2；

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

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

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

至此，算法結(jié)束。

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

3 實(shí)驗(yàn)及分析

本文對(duì)圖3的網(wǎng)絡(luò)拓?fù)渥鲞M(jìn)一步的擴(kuò)展，采用圖5所示的網(wǎng)絡(luò)拓?fù)鋱D，對(duì)使用單路徑路由算法、多路徑路由算法、文獻(xiàn)[16]提出的隨機(jī)單路徑路由算法以及本文提出的算法來(lái)實(shí)現(xiàn)Alice和Bob之間的密鑰傳遞情況進(jìn)行仿真實(shí)驗(yàn)。

圖5 實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

3.1 實(shí)驗(yàn)環(huán)境及性能指標(biāo)

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

本文采用以下3個(gè)性能指標(biāo)進(jìn)行評(píng)價(jià)和分析：1)選路成功率。選擇路徑成功與否是路由算法可行與否的關(guān)鍵，該指標(biāo)用來(lái)評(píng)價(jià)路由算法的可行性。2) 密鑰消耗量。充足的密鑰量是信任中繼量子網(wǎng)絡(luò)密鑰傳遞的必要條件，密鑰消耗的多少直接影響到接下來(lái)的密鑰通信，該指標(biāo)用來(lái)評(píng)價(jià)路由算法的效率。3) 選路時(shí)間。一次密鑰傳遞的時(shí)間對(duì)路由的效率影響很大，該指標(biāo)用來(lái)評(píng)價(jià)路由算法的效率。

3.2 選路成功率比較

針對(duì)圖5所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，Alice到Bob之間的路徑有很多條，通過(guò)路由算法選擇3條最短路徑：A-B-C-D-E；A-I-M-F-E；A-H-G-F-E。

針對(duì)密鑰量充足的情況，4種方法的選路成功率均為100%。因此，本實(shí)驗(yàn)只考慮存在密鑰量不足鏈路的情況。本網(wǎng)絡(luò)中可選擇的鏈路有11條。本實(shí)驗(yàn)仿真一條鏈路密鑰量不足時(shí)的選路成功率，分別用4種路由算法做了11組實(shí)驗(yàn)來(lái)仿真11條鏈路在密鑰量不足情況下的選路情況，每組20次，統(tǒng)計(jì)其選路成功次數(shù)和選路成功率(選路成功率=選路成功次數(shù)/實(shí)驗(yàn)次數(shù))。

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

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

分析原因如下：?jiǎn)温窂铰酚伤惴ㄔ谶x路時(shí)選擇一條路徑，當(dāng)選中的路徑的鏈路密鑰量不足時(shí)，就會(huì)宣告選路失??；多路徑路由算法在選路時(shí)，雖然可選擇多條路徑(這里為3條路徑)，但無(wú)論哪條路徑的鏈路密鑰量不足，都會(huì)宣告選路失??；文獻(xiàn)[16]提出的隨機(jī)單路徑路由算法在選路時(shí)隨機(jī)選擇一條，可能會(huì)選中密鑰量不足的鏈路，進(jìn)而導(dǎo)致選路失?。欢疚奶岢龅乃惴?，選路時(shí)會(huì)從3條最短路徑中隨機(jī)選擇一條，當(dāng)選中的最短鏈路密鑰量不足時(shí)，就會(huì)回溯到有具有多條路徑的節(jié)點(diǎn)，繼續(xù)進(jìn)行路由選擇，而不是宣告選路失敗，因而選路代價(jià)較低，成功率較高。因此，相對(duì)于已存在的針對(duì)QKD網(wǎng)絡(luò)的路由算法來(lái)說(shuō)，本文提出的路由選擇算法的選路成功率更高，效果更好。

3.3 密鑰消耗量比較

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

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

密鑰消耗量比較分以下4種情況：

1) 鏈路密鑰量充足：4種算法都選路成功，密鑰消耗量為：K1=K3=K4=40，K2=120。

2) 第二跳密鑰量不足：?jiǎn)温窂铰酚伤惴ㄟx路失敗后從起點(diǎn)重新開(kāi)始進(jìn)行密鑰傳遞，則K1=10+40n(n≥1)；多路徑路由算法其中一條路徑選路失敗后該路徑重新開(kāi)始進(jìn)行密鑰傳遞，則K2=80+10+40n=90+40n(n≥1)；文獻(xiàn)[16]的隨機(jī)路由算法的密鑰消耗量等同于單路徑路由算法，則K3=10+40n(n≥1)；而當(dāng)選中的鏈路密鑰量不足時(shí)，本算法將回溯到回溯點(diǎn)繼續(xù)進(jìn)行密鑰傳遞，直至選路成功，則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。

密鑰消耗量結(jié)果如表7所示：由表7可知，當(dāng)存在鏈路密鑰量不足的情況時(shí)，本算法的密鑰消耗量明顯小于或等于其他3種算法，效率更高。

表7 4種算法的密鑰消耗量的對(duì)比

3.4 選路時(shí)間比較

由單路徑路由、多路徑路由和文獻(xiàn)[16]提出的隨機(jī)路由算法的選路原理可知，3種方法的選路時(shí)間相差無(wú)幾。本實(shí)驗(yàn)只比較文獻(xiàn)[16]算法與本算法的選路時(shí)間。

對(duì)于文獻(xiàn)[16]的路由算法，當(dāng)選擇的路徑密鑰量不足時(shí)，就中斷通信，重新開(kāi)始進(jìn)行密鑰傳遞。為了比較兩個(gè)算法的選路時(shí)間，本實(shí)驗(yàn)設(shè)定密鑰產(chǎn)生速率為100單位/s，當(dāng)文獻(xiàn)[16]的算法失敗后，更新密鑰量，重新開(kāi)始密鑰傳遞，直到密鑰傳遞成功。將每次的時(shí)間相加，即可得到選路時(shí)間。

本實(shí)驗(yàn)利用圖5所示的網(wǎng)絡(luò)，采用本文提出的算法進(jìn)行多次實(shí)驗(yàn)，記錄20次有回溯的選路時(shí)間；采用文獻(xiàn)[16]的算法進(jìn)行多次實(shí)驗(yàn)，記錄20次選擇路徑失敗后重新進(jìn)行選路的選路時(shí)間。對(duì)比結(jié)果如圖7所示。

圖7 選路時(shí)間的對(duì)比

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

上述實(shí)驗(yàn)及分析結(jié)果表明：相對(duì)于已有的單路徑路由算法、多路徑路由算法和隨機(jī)單路徑路由算法，本算法在密鑰量不足的網(wǎng)絡(luò)中有更好的選路成功率、更少的密鑰消耗量和更短的選路時(shí)間。

4 結(jié) 束 語(yǔ)

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

本文工作得到網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室(ICDDXN004)的資助，在此表示感謝。