區塊鏈PCN 的高效路由策略

霍如，倪東，盧華，夏云峰，汪碩,4，黃韜,4，劉韻潔,4

（1.北京工業大學信息學部，北京 100124；2.網絡通信與安全紫金山實驗室，江蘇 南京 211111；3.廣東省新一代通信與網絡創新研究院，廣東 廣州 510663；4.北京郵電大學網絡與交換國家重點實驗室，北京 100876）

1 引言

區塊鏈技術本質上是一種基于分布式對等網絡的基礎架構和計算范式，具有去中心化、不可篡改、可追溯、匿名性和透明性五大特征，這些特征為構建安全可信的分布式交易環境提供了良好的契機[1-3]。然而，受嚴格共識過程和簽名認證機制的約束，區塊鏈的吞吐量很低且可擴展性差。比特幣的吞吐量為3～7筆/秒交易，而以太坊的吞吐量大約是比特幣的兩倍[4-5]。在全球電子支付場景中，Visa 或其他集中式支付服務提供商每秒可以處理數千筆交易，這是目前的區塊鏈技術無法企及的。隨著微交易的出現，區塊鏈的可擴展性問題被進一步放大，這種交易通常對實時性要求較高。此外，區塊鏈賬本收取的費用可能高于交易金額，這對交易雙方來說通常不能接受。

付費信道可以解決上述挑戰，方法是在2 個用戶之間建立付費信道，并在信道中托管一定的資金，將交易從鏈上轉移到鏈下，避免了鏈上共識和確認的時延[6]。付費信道只有開啟和關閉時，才會在區塊鏈中寫入交易，鏈下交易可以在用戶之間頻繁執行，不需要上鏈。因此提高了交易效率、可擴展性和吞吐量。

在每個交易發送方與接收方之間建立付費信道會產生一定成本，對于不存在直接付費信道的用戶之間可以通過中間節點轉發交易。連接不同用戶的付費信道共同構成了付費信道網絡（PCN,payment channel network）[7]。

PCN 和傳統網絡的根本區別在于存在節點的資金消耗。節點之間的交易通過中間節點轉發，中間節點一側資金的輸入意味著另一側資金的輸出。如果中間節點的輸出側資金耗盡，它將無法啟動該方向的任何交易或充當交易的中間節點。人們可以通過鏈上對資金耗盡節點的資金補充來解決這個問題，但該過程涉及復雜的鏈上共識和簽名認證，影響鏈下的交易進程和交易成功率[8]。為此如何維持鏈下付費信道的長時間穩定性運行、減少鏈上交易次數是保證PCN 高吞吐量穩定運行的重要因素。

現階段提升PCN 吞吐量的主要策略有業務路由優化策略和鏈下信道再均衡策略2 種。路由優化策略指設計路由策略讓業務沿著資金足夠或增加信道平衡的路徑傳輸。鏈下信道再均衡策略指在PCN 出現信道失衡時進行全網資金調整，為資金不足的節點注入資金，進而實現PCN 均衡。

在PCN 路由優化策略研究方面，Sivaraman 等[7]提出了一種Spider 算法來解決最短路徑算法選路引起的資金耗盡問題。該策略利用了互聯網包交換的思想將交易劃分為交易單元，并使用多路徑傳輸協議實現高吞吐量路由，同時設計多路徑擁塞控制協議確保信道的均衡使用。Yu 等[9]提出了一種CoinExpress 新型分布式動態路由機制。該機制設計了基于網絡流和并發流的PCN 路由模型，在保證交易路由的同時保證交易時延。Zhang 等[10]提出了一種分布式穩健支付路由協議RobustPay 來抵抗事務失敗，實現了PCN 的穩健性、高效性和分布式，同時修改了閃電網絡的HTLC 協議，使其適應強大的支付路由協議。Lin 等[11]提出了一種FSTR 路由算法，該算法基于資金傾斜度進行交易路徑選擇，在減小資金傾斜度的同時提高交易成功率。Pavel等[12]提出了一種混合路由算法Flare，該算法通過設置網絡中的信標節點來獲取網絡的本地視圖，本地節點和信標節點的結合使節點最大限度地減少路由狀態，同時以高概率查找到任意給定節點的路由。

在 PCN 鏈下信道再均衡策略研究方面，Pickhardt 等[13]提出了一種閃電網絡的鏈下信道再均衡算法，通過對網絡上循環路徑的資金調整實現信道再均衡。Mercan 等[14]提出了一種物聯網場景下的PCN 設計，通過在網絡上使用通用權重策略來保持信道均衡，并針對不平衡的支付方案，為每個物聯網設備設置多個連接來提高交易成功率。

目前，對路由優化策略的研究大多只考慮交易成功率，如文獻[9-12]，這些研究未考慮交易后的信道失衡問題，導致網絡的平衡度迅速下降，而且一個交易請求到達時立即原子性地路由整筆交易。當付費信道缺少足夠的資金時，即使信道在短時間內會進行資金補充，也會導致交易立即失敗。其對金額較大的交易影響尤其嚴重。目前，大多的鏈下信道再均衡策略采用全網均衡的方式，如文獻[13-14]，這些研究可以很好地解決PCN 吞吐量低的問題，但在逐年擴大的PCN 中進行全網均衡將影響正常的交易進程，這對于實時性要求較高的電子支付類業務是無法接受的。最重要的是，目前主要是針對2 種策略的單獨研究，很少考慮2 種策略的結合，業務路由優化策略和鏈下信道再均衡策略的割裂導致算法的性能優化受限。最后，現階段的PCN對所有的業務采用統一的選路策略，沒有考慮針對不同的業務類型設置優先級，對于服務質量要求較高的業務無法實現服務質量保障。

基于上述問題，本文提出PCN 的高效路由策略（ERS_PCN,efficient routing strategy of blockchain-based PCN）。該策略根據業務類型及業務優先級為高優先級業務建立專用付費信道，并將常規業務劃分為多個交易單元，通過信道均衡選路算法為各交易單元選路，在路由層面上實現信道均衡，減少鏈上交易次數，維持付費信道的長時間穩定性運行，提高交易成功率。本文的主要貢獻如下。

1) 設計差異化專用信道服務算法。根據交易類型和交易優先級為高優先級交易建立專用付費信道，來保證交易的服務質量。

2) 設計多路徑轉發算法。將交易拆分為獨立的交易單元，采用多路徑傳輸的方式獨立傳送這些單元。

3) 設計信道均衡選路算法。針對請求計算一定數量的候選路徑，計算每一條候選路徑路由后的網絡基尼系數，并選擇使網絡基尼系數最低的路徑轉發交易。

4) 設計ERS_PCN 策略。該策略由差異化專用信道服務算法、多路徑轉發算法、信道均衡選路算法3 個部分組成。

5) 采用網絡基尼系數、交易成功率作為評價指標，構建PCN 拓撲與業務模型進行仿真，驗證算法優越性。

2 系統模型

為了設計ERS_PCN 策略，本節從平臺和算法2 個層面考慮來設計系統模型。其中，平臺模型包括PCN 應用分層模型、區塊鏈模型和PCN 模型，主要為ERS_PCN 策略的實現提供底層支撐平臺；算法模型包括K 路徑算法模型和PCN 基尼系數模型，主要為ERS_PCN 策略的實現提供算法支撐。PCN 與區塊鏈網絡之間存在交互關系，本節首先設計PCN 應用分層模型，該模型由物理層、區塊鏈層、PCN 層和應用層組成，其中區塊鏈層和PCN層是模型的核心。考慮到區塊鏈層是支撐PCN 安全穩定運行的重要因素，因此本節進一步對區塊鏈模型進行了介紹。同時，為了便于后續算法研究的量化，本節提出了PCN 模型，對PCN 層進行模型抽象。最后介紹了K 路徑算法模型和PCN 基尼系數模型，為ERS_PCN 策略中的多交易單元多路徑傳輸和評價信道是否均衡提供理論參考依據。

2.1 PCN 應用分層模型

參考現有的通用區塊鏈應用分層模型[15]，本文設計了如圖1 所示的PCN 應用分層模型，該模型分為4 層，自下而上分別為物理層、區塊鏈層、PCN層和應用層。考慮到應用與區塊鏈網絡及PCN 的交互關系，4 層模型主要在傳統通用區塊鏈應用分層模型基礎上進行了PCN 層的增加和各層的改進，以適用于本文方法的應用與實現，其中PCN 層處在應用層和區塊鏈層之間，便于對上支持支付類應用，對下與區塊鏈底層技術進行交互。

圖1 PCN 應用分層模型

1) 物理層

物理層是硬件層，它由個人計算機、云服務器、小型服務器、大型服務器等硬件設備組成。該層為區塊鏈層提供豐富的計算資源與存儲資源，可以在眾多平臺上挖掘不同硬件的計算能力與存儲能力，加快上層的共識進程，減小鏈上共識時間。

2) 區塊鏈層

區塊鏈是通過區塊鏈接在一起的有序記錄的列表，該層利用分布式共識算法生成和更新數據，并利用對等網絡進行節點間的數據傳輸，結合密碼學原理等技術保證存儲數據不可篡改，支撐PCN 層的穩定運行，保證PCN 層交易的鏈上最終一致性。

3) PCN 層

PCN 層是PCN 應用分層模型的核心，主要完成應用層下發的付費業務，完成與區塊鏈層的交互，將交易從鏈上轉移到鏈下，避免了鏈上共識和確認的時延，保證付費交易的安全性與實時性。

4) 應用層

應用層為眾多付費應用的集合，這些應用通過接入網關接入PCN 層，實現跨境支付、知識付費等電子支付業務。

2.2 區塊鏈模型

區塊鏈主要解決PCN 資金交易的信任和安全問題，本文主要利用區塊鏈的4 種技術來支撐PCN的安全穩定運行。

1) 分布式賬本

交易記賬由分布在不同地方的多個節點共同完成，每一個節點都記錄完整的交易副本，共同參與監督交易的合法性。PCN 鏈下資金交易結束，需上鏈存儲到分布式賬本進行交易的記錄。

2) 非對稱加密和授權技術

存儲在區塊鏈上的交易信息是公開的，但是交易賬戶身份信息是高度加密的，只有在數據擁有者授權的情況下才能訪問到，從而保證了交易信息的安全和個人的隱私。

3) 共識機制

共識機制通過特殊節點的投票，完成對交易的驗證和確認；對一筆交易，如果利益不相干的若干個節點能夠達成一致，則可以認為全網對此達成共識，即由不同節點組成的系統之間依賴一個制度來維護系統的數據一致性。PCN 鏈下資金交易結束，在鏈上達成共識后方可進行交易上鏈。

4) 智能合約

智能合約是基于可信不可篡改的數據，自動化執行的一些預先定義好的規則和條款。PCN 鏈下資金交易結束，需通過智能合約實現交易的上鏈邏輯，進行PCN 與區塊鏈的交互。

2.3 PCN 模型

假設拓撲G=(N,E)是一個PCN，其中，N表示整個網絡中的節點數，即PCN 中的所有參與者個數，N≥2；E表示整個網絡中的鏈路集合，即PCN 中的所有付費信道。假設節點vi和節點vj為G中存在付費信道的2 個節點，信道Path(v i,vj)為鏈路e1,…,el的集合，l為Path(v i,vj)的鏈路個數。當l=1時，v i和vj之間存在直連鏈路。為了方便說明，本文假設l≥3。ek=(u k,uk+1)表示Path(v i,vj)路徑上中間節點uk與uk+1之間的直連鏈路，表示節點uk到節點uk+1方向的可流通資金。Path(v i,vj)示意如圖2(a)所示。此外，將MaxMPath(vi,vj)定義為Path(v i,vj)的最大可流通資金，計算式為

其中，min(…) 表示取最小值函數。

假設在時刻t，節點vi到節點vj存在交易需求transt(vi,v j,m)，其中m表示交易金額。如果該信道上MaxMPath(vi,vj)≥m，則信道ek交易后節點uk到節點uk+1方向的可流通資金變為m(uk,uk+1)?m，節點uk+1到節點uk方向的可流通資金變為m(uk+1,uk)+m，路徑上其他鏈路的資金流動情況相同，交易后的示意如圖2(b)所示。

圖2 PCN 模型示意

2.4 K 路徑算法模型

路由技術旨在發現業務的源、目的節點之間的合適路徑[16]。其中，最短路徑算法指尋找網絡中兩節點之間的最短路徑，是目前網絡路由研究中較常用的基礎路由算法。K 最短路（KSP,K shortest paths）算法[17-18]是在最短路徑算法基礎上的升級。與最短路徑算法不同，KSP 算法尋找源節點與目的節點之間的多條路徑，并組成最短路徑集合，以滿足用戶對不同路徑的多樣化需求。

本文利用KSP 算法的思路，并根據不同的基礎路由算法設計新的K 路徑算法，如K 最短路徑算法的基礎路由算法為最短路徑算法。假設一個業務請求的源、目的節點分別為vi和vj，K 路徑算法可分為兩部分。

1) 利用基礎路由算法算出首條路徑Path1(v i,vj)，然后在此基礎上依次算出其他的K-1條路徑。

2) 在求Pathk+1(v i,vj)時（1

采用合適的K 路徑算法，在各候選路徑上進行獨立的交易單元傳輸可以分散高金額交易到多個付費信道中，從而達到提供交易成功率的目的。

假設K=3，節點vi與vj之間存在交易量為3 的請求，節點vi與vj的K 路徑選路結果示例如圖3(a)所示。其中，Path1(vi,vj)與Path2(vi,vj)之間的偏離節點為vi，Path2(vi,vj)與Path3(vi,vj)之間的偏離節點為uk。從圖3(a)可以看出，3 條路徑的最大可流通資金均無法滿足需求，將交易請求平均分散到3條候選路徑可交易成功，結果如圖3(b)所示。

圖3 K 路徑算法示例

2.5 PCN 基尼系數模型

基尼系數[19]是根據洛倫茲曲線判斷一項內容分配公平程度的指標。本文采用該指標評價PCN的均衡程度。

假設用戶在網絡中實際托管金額曲線與托管金額絕對平等曲線之間為區域A，實際托管金額曲線與坐標軸之間為區域B，如圖4 所示。區域A 的面積除以區域A與區域B的面積和表示網絡不均衡程度，如式(2)所示，稱之為PCN 基尼系數。

圖4 PCN 洛倫茲曲線與基尼系數

其中，SA表示區域A 的面積，SB表示區域B 的面積。

如果區域A 的面積為0，即GiniG_PCN=0，表示網絡完全均衡；如果區域B 的面積為0，則GiniG_PCN=1，此時網絡絕對不均衡。

式(2)可以從物理意義上直觀地表示網絡基尼系數，但不具有實際可操作性。為了便于在實際問題中更好地運用該指標直接度量PCN 的不平衡程度，此處從數學意義上描述網絡基尼系數，并證明該描述方式的正確性，PCN 基尼系數的數學表達形式為[20]

其中，μ表示網絡托管金額均值，Δ表示基尼平均差。Δ可由式(4)計算得到[20]。

其中，|mj?mi|是任何一個付費信道中的兩用戶托管金額差值的絕對值，M表示PCN 的總付費信道個數。

3 策略設計與實現

PCN 高效路由策略根據業務類型及業務優先級為高優先級業務建立專用付費信道，并將常規業務劃分為多個交易單元，通過信道均衡選路算法為各交易單元選路，減少鏈上交易次數，維持付費信道的長時間穩定性運行，提高交易成功率，該策略由差異化專用信道服務算法、多路徑轉發算法和信道均衡選路算法3 個部分組成。

3.1 差異化專用信道服務算法

差異化專用信道服務算法針對不同的業務類型建立不同的專用信道，保證高優先級業務獲得transt(vi,v j,m,type,p ri)更好的服務質量。對于高優先級用戶，針對其不同的業務類型建立專用信道提供差異化服務。本文將交易類型分為高金額業務、低時延業務、高可靠業務、常規業務幾類。對除了常規業務以外的業務建立專用信道保證交易的服務質量。差異化專用信道服務算法可簡述為：首先，判斷交易的業務類型及優先級；其次，決定業務的交易路徑。具體算法流程如算法1 所示。

算法1差異化專用信道服務算法

輸入transt(vi,v j,m,type,p ri)

3.2 多路徑轉發算法

多路徑轉發算法在交易發送方將交易拆分成一系列獨立路由的交易單元，每個交易單元都轉移一筆以最大交易單元（TRANS_UINT,transaction unit）為邊界的金額。由于使用獨立的密鑰創建每個交易單元，拆分交易并不會影響交易的安全性。當交易接收方接收并確認交易單元時，發送方可以選擇性地僅顯示已確認交易單元的密鑰。交易發送方在交易過程中將收到通知，告知他們已完成了多少交易單元，發送方可以選擇取消未完成的交易單元或在區塊鏈上重試。多路徑轉發算法簡述如下。首先，計算交易單元個數為

其中，RoundU(…) 表示向上取整函數，MTU 表示交易單元大小，m表示交易金額。

其次，劃分交易單元，并對各交易單元加密。然后，使用K 路徑算法計算各交易單元的轉發路徑，計算轉發路徑條數為

最后，沿著各路徑獨立轉發交易單元。具體算法流程如算法2 所示。

算法2多路徑轉發算法

輸入transt(vi,v j,m,type,pr i)，MTU，K 路徑算法，交易簽名策略

3.3 信道均衡選路算法

在一個交易請求到達PCN 時，為該請求計算一定數量的候選路徑，信道均衡選路算法會計算每一條候選路徑路由后的網絡基尼系數，并選擇網絡基尼系數最小的路徑轉發交易。如果找不到可行的路徑，則路由失敗。信道均衡選路算法流程可整理為：首先，計算M條候選路徑；其次，計算通過各候選路徑路由后的網絡的基尼系數；最后，選擇使網絡基尼系數最小的路徑作為最終的交易路徑。具體算法流程如算法3 所示。

算法3信道均衡選路算法

輸入transt(vi,v j,m,type,pr i)，候選路徑個數M，K 路徑算法

3.4 PCN 高效路由策略實現

根據算法1～算法3，本節設計了ERS_PCN 策略的具體實現，流程如圖5 所示。對于t時刻到來的一個交易請求transt(vi,v j,m,type,pri)，首先根據type 和pri 判斷交易是否為常規業務，如果不是，則按照算法 1 進行交易的路由與轉發。如果transt(vi,v j,m,type,pri)為常規業務，則使用算法2計算轉發路徑個數為NUMpath(transt(vi,vj,m,type,pri))。計算候選路徑個數如式(8)所示。

圖5 ERS_PCN 策略實現流程

其中，mutli≥1。為了實現更好的信道均衡，PCN的連通度越高，mutli 應越大。

然后，計算NUMCpath(transt(vi,v j,m,type,pri))條候選路徑的路由后網絡基尼系數。對計算得到的網絡基尼系數進行升序排序整理，選擇排名在前NUMpath(transt(vi,v j,m,type,pri))條的路徑作為本次交易路徑。

在ERS_PCN 策略中，為了避免多個交易同時使用某一鏈路導致資金的暫時性短缺，交易到達某一節點時需要計算該節點與下一跳節點之間的托管金額是否滿足交易需求，如果滿足則轉發至下一跳，否則交易在該節點處進行排隊，并為隊列中的每一筆交易設置一個時間閾值，如果在閾值范圍內該節點與下一跳節點之間流入足夠的資金，業務沿著原路徑轉發，否則以該節點為源節點，利用算法3為其計算新的轉發路徑。

4 仿真分析

為了驗證所提ERS_PCN 策略的優越性，本文利用python 的networkx 庫模擬網絡拓撲來構建實驗。使用一臺Linux 服務器作為硬件運行環境，服務器采用Centos 系統，32 GB 內存。本文分別采用small-world 和scale-free 這2 個拓撲，節點個數均為300 個，small-world 網絡拓撲的節點平均度數為4，scale-free 網絡拓撲的節點平均度數為3[21]。本節分別從交易成功率和網絡基尼系數2 個方面進行算法的仿真，并與Dijkstra 算法[22]和Spider 算法[7]進行了對比。其中，交易成功率指一段時間內成功交易的個數占總交易請求個數的比值。本文仿真參數設置如表1 所示。

表1 仿真參數設置

瑞波幣是Ripple 網絡[21]內的流動性代幣，可以作為各類貨幣之間兌換的中間品。本文從Ripple 網絡收集了現實世界中的付款數據，并以瑞波幣作為PCN 中的流動代幣。為此，本文檢索了2020 年12月31 日發生的所有瑞波幣交易，通過隨機抽樣從該數據集中選擇交易。實驗中交易數量以120 個為步長，每秒到達PCN 的交易個數從120 個依次遞增到720 個，對每個交易數量進行50 次重復實驗，保證實驗結果的有效性。

small-world 拓撲下每秒到達PCN 不同交易個數時ERS_PCN 算法與Dijkstra 算法及Spider 算法的交易成功率對比情況如圖6 所示，此時設置網絡中各節點在各鏈路的平均托管金額為10 個瑞波幣。從圖6 可以看出，隨著交易個數的增加，ERS_PCN算法的交易成功率均高于Dijkstra 算法及Spider 算法，一直保持穩定的交易成功率，其他算法性能則會出現持續下降的趨勢，交易成功率差值隨著交易個數的增加而增大。這是因為ERS_PCN 算法結合了多路徑轉發算法和信道均衡選路算法，將交易劃分為多個交易單元，降低了因鏈路資金不足而交易失敗的概率，同時在選路時保證信道均衡，減少了因信道失衡導致的交易失敗。當交易個數為720 個時，ERS_PCN 算法的交易成功率較Dijkstra 算法增加了約180%，較Spider 算法增加了約78%。

圖6 small-world 下ERS_PCN 與Dijkstra 算法、Spider 算法的交易成功率對比

small-world 拓撲下每秒到達PCN 不同交易個數時ERS_PCN 算法與Dijkstra 算法及Spider 算法的網絡基尼系數對比情況如圖7 所示。為了保證交易全部成功，此時設置網絡中各節點在各鏈路的平均托管金額為100 個瑞波幣。從圖7 可以看出，不同交易個數時，ERS_PCN 算法的網絡基尼系數均低于Dijkstra 算法和Spider 算法。并且隨著交易個數的增加，ERS_PCN 算法的網絡基尼系數呈現較為緩慢的增長速度，3 種算法間的網絡基尼系數差值的絕對值呈現逐漸增大的趨勢，說明本文算法可以在一定程度上維持PCN 信道長時間穩定運行。當交易個數為720 個時，ERS_PCN 算法的網絡基尼系數較Dijkstra 算法減小了約150%，較Spider算法減小了約45%。

圖7 small-world 下ERS_PCN 與Dijkstra 算法、Spider 算法的網絡基尼系數對比

與此同時，本文采用相同的方法驗證了scale-free 拓撲下ERS_PCN 算法的性能，結果分別如圖8 和圖9 所示。

圖8 scale-free 下ERS_PCN 與Dijkstra 算法、Spider 算法的交易成功率對比

圖9 scale-free 下ERS_PCN 與Dijkstra 算法、Spider 算法的網絡基尼系數對比

從圖8 可以看出，ERS_PCN 算法在scale-free網絡拓撲下仍可以表現出穩定的交易成功率。這是因為該算法實現了多路徑轉發算法與信道均衡選路算法的結合，減少了因鏈路資金不足與信道失衡導致的交易失敗。當交易個數為 720 個時，ERS_PCN算法的交易成功率較Dijkstra算法增加了約100%，較Spider 算法增加了約66%。從圖9 可以看出，在scale-free 網絡拓撲下ERS_PCN 算法的網絡基尼系數仍低于Dijkstra 算法和Spider 算法。隨著交易個數的增加，ERS_PCN 算法的網絡基尼系數增長較緩慢，但3 種算法間的網絡基尼系數差值的絕對值呈現逐漸增大的趨勢。當交易個數為720個時，ERS_PCN算法的網絡基尼系數較Dijkstra算法減小了約100%，較Spider 算法減小了約44%。

5 結束語

本文提出了一種PCN 的高效路由策略，該策略由差異化專用信道服務算法、多路徑轉發算法和信道均衡選路算法3 個部分組成。通過差異化專用信道服務算法為高優先級業務建立專用信道，保證服務質量。多路徑轉發算法將業務劃分為TRANS_UINT 大小的交易單元獨立傳輸，增加交易成功率。信道均衡選路算法采用網絡基尼系數作為信道是否均衡的指標進行選路，減少鏈上交易次數，維持付費信道的長時間穩定性運行。針對提出的方案，本文分別以交易成功率和網絡基尼系數作為評價指標，在 small-world 網絡和scale-free 網絡上對算法的性能進行了仿真。仿真結果表明，本文方案可以在增加交易成功率的同時，增加網絡均衡性。small-world 網絡下，當每秒到達網絡的交易個數為720 個時，ERS_PCN 算法的交易成功率較Dijkstra 算法增加了約180%，較Spider 算法增加了約78%；網絡基尼系數較Dijkstra 算法減小了約150%，較Spider 算法減小了約45%。