實時全額支付系統中基于基本環的高效多邊撮合算法分析和設計

李 世 梁

(中國人民銀行上?？偛俊∩虾?200120)

?

實時全額支付系統中基于基本環的高效多邊撮合算法分析和設計

李 世 梁

(中國人民銀行上?？偛可虾?200120)

基本環實時全額支付系統清算多邊撮合

0　引　言

在跨行轉賬支付系統中，大額支付系統是各國最重要的支付系統。經大額支付系統處理和清算的支付(資金轉賬)指令，通常具有數量多、金額大、實時性要求高等特點，已成為連接社會經濟活動及其資金運行的“大動脈”。若一家或多家參與機構(成員銀行)發生信用或流動性風險，可能會影響整體金融穩定，進而引發系統性金融危機[1,2]。

在跨行轉賬支付系統中，有兩種基本的清算模型：實時全額支付系統(RTGS)和延遲凈額結算系統(DNS)。根據國際清算銀行的定義，在RTGS中，資金轉賬指令的處理和最終清算是實時連續的，對參與機構流動性要求高但結算風險?。欢谘舆t凈額結算系統(DNS)中，指令是周期性地在某一時間點進行軋差，能夠節約參與者流動性但結算風險較高[1]。為了降低金融風險，RTGS已成為包括中國在內的多數國家構建大額支付系統的主要形式。

由于RTGS的定義非常寬泛，其具體設計實現具有很大的差異性，尤其是當發送參與機構在央行清算賬戶余額不足時的支付指令處理方式。例如，RTGS可以拒絕這條指令并返回給發送參與機構，或者RTGS可以暫存這條指令(進入排隊等待狀態)，當發送參與機構清算賬戶余額充足時(解決方法主要是資金注入法，如，央行倫巴第貸款、從其他銀行借款、公開市場拆借、等待接收其他參與機構的轉賬/進賬資金)，才會釋放該條指令。

但使用資金注入法比較困難，會增加參與機構的融資成本，面臨央行高額罰息等風險，并且，解決問題的時效性欠佳，可能引起法律風險和聲譽受損，例如，某參與機構的客戶可能急需轉賬去完成一筆投資，而資金未實時到賬會錯過該筆投資。相比較于資金注入法，撮合法在特定條件下可解決“三角債”問題，無需資金注入實現釋放(或清算)排隊支付指令,可節約參與機構的流動性、提高資金使用效率，已成為支付清算領域中節約參與機構資金流動性的重要手段和研究熱點之一[1]。

1　國內外研究現狀

為描述方便，本文采用有向圖描述法，參與機構代號和其清算賬戶余額作為節點的屬性，其中代號在節點的上部，余額在節點的下部。支付指令抽象為付款方至收款方的有向邊，將交易金額作為有向邊的權值。

傳統撮合法在簡化撮合圖中利用深度優先搜索法尋找一個可撮合環，可撮合環上的所有節點滿足條件：[節點清算賬戶余額+∑(入邊權值)-∑(出邊權值)≥0][3,4]。如圖1(a)所示，有4條支付指令因支付指令金額大于清算賬戶余額，導致清算賬戶余額不足，進入相互循環等待狀態(死鎖狀態)。如圖1(b)所示，若參與機構1,2-4同時抵消1元支付交易金額，則各參與機構均滿足支付交易金額大于清算賬戶余額的條件，解除死鎖。如圖1(c)所示，最后所有支付指令均可得到釋放。

通常，簡化撮合圖往往包括多個可撮合子圖，理想狀態下，希望一次撮合能找出所有可撮合子圖，一次計算完成所有“三角債”的清理[3,4]。

(1) 隨機撮合算法(ROA)鑒于時間和成本約束，一般會選擇找到一個可撮合環后，就立即進行撮合[3,4]。因此，從全局角度來看，該撮合法是一個典型的貪心算法[5]。

(2) 流動性節約算法(LSM)首先搜索支付指令構成的最小環，即檢查是否存在雙邊撮合支付指令，然后依次檢查三邊環撮合、四邊環撮合……[6]。如果檢查到雙邊/多邊環，構成環的支付指令會被撮合。但LSM本質上依然具有貪心算法的特點，沒有從全局角度考慮多環之間的關聯和優化。

如圖1(d)所示，當兩個環(<1,2,3,4>與<6,3,5>)共用節點3時，LSM首先會選取<6,3,5>進行檢測(ROA有50%的概率會首先選取<6,3,5>進行檢測)，但節點3顯然不滿足可撮合條件(1+0-2=-1<0)。因此，LSM會放棄撮合該環。但是，如圖1(e)所示，如果能首先考慮<1,2,3,4>,因節點1-4均滿足可撮合條件，<1,2,3,4>上的支付指令均可以得到釋放，最終，節點3的清算賬戶余額變為1。然后，再考慮<6,3,5>,發現節點6、3、5均滿足可撮合條件。最后，兩環均撮合成功。

如圖1(f)所示，當兩個環(<1,2,3,4>與<6,2,3,5>)共用一條邊(<2,3>)時，以上算法均會分別單獨考慮兩個環。因節點2不滿足可撮合條件(1+1-3=-1<0)，兩環均撮合不成功。然而，如圖1(g)所示，如果能同時考慮兩個環，則節點2滿足可撮合條件(對于節點2而言，1+1+1-3=0)，撮合成功。

因此本文研究基于基本環的多邊撮合算法，優化撮合性能。

圖1　撮合案例

2　問題描述

在RTGS中，各參與機構存儲資金或提供質押融資至其央行清算賬戶，以發送和執行各類貸記指令。參與機構發送的貸記指令，需要同時貸記付款方的清算賬戶，并借記收款方的清算賬戶，以維持會計平衡，具有逐筆處理業務、全額清算資金、資金實時到賬的特點[1]。

3　基于基本環的多邊撮合算法原理和過程

首先對有向圖G={V,E}(|V|=n,|E|=m)進行簡化處理，進行雙邊撮合，利用拓撲排序法消除不能構成環的有向邊，然后利用查找基本環算法生成全部基本環。對于多環共用公共節點的情況，利用銀行家算法得出多環安全推進序列(詳見3.4節)；對于多環共用有向邊的情況，不僅給出多環安全推進序列，還應考慮共同撮合的情景；最后，對支付指令進行消除處理。

3.1有向圖簡化處理

(1) 雙邊撮合

復雜度分析：因有向圖G中有m條邊，則雙邊撮合的時間復雜度為O(m)。

圖2　雙邊撮合案例

(2) 拓撲排序

有向有環圖的一個特點是，所有節點的入度大于0。因此，可得如下定理：

定理1利用拓撲排序可快速消除有向圖中不能構成環的節點和邊。

證明根據有向無環圖的一個定理：如果圖G存在一個拓撲排序，則G是一個有向無環圖[5]。該定理的逆否命題是：如果圖G是一個有向有環圖，則G不存在拓撲排序。因此，可利用拓撲排序法，首先在圖G中查找一個入度為0的節點v，然后在圖G中刪除v及其關聯的出邊，重復此過程，直至圖G中不存在入度為0的節點。

圖3　拓撲排序案例

如圖3(a)所示，首先，節點6的入度為0，則刪除節點6及其關聯的兩條邊(p62和p65)；然后，如圖3(b)所示，節點5的入度由1變為0，同樣刪除節點5及其關聯的一條邊(p53)；最后，如圖3(c)所示，只剩下節點入度大于0的節點(可構成環)。

復雜度分析：設有向圖中有n個節點、m條邊，則拓撲排序的時間復雜度為O(m+n)[5]。

3.2查找基本環

本文提出的多邊撮合算法需要基于有向圖的基本環。在查找有向圖的所有基本環方面，已經有很多研究。例如，James C.Tiernan提出的查找算法，該算法理解簡單、易于使用程序語言實現，其經過路徑拓展、環確認、節點關閉、向前推移起始節點等步驟，可獲得一個有向圖的所有簡單基本環[7]。而國內也有針對查找基本環方面的優化算法，例如，王玉英等[8]提出的查找算法，在算法復雜度方面做了一些優化，時間復雜度為O(n32n)。

3.3撮合孤立可撮合環

對于孤立的可撮合環，即環不與其他環相交于任何節點或邊(?i,j∈{1,…,k},V(Ci)∩V(Cj)=?∧E(Ci)∩E(Cj)=?)，并滿足可撮合條件[節點清算賬戶余額+∑(入邊權值)-∑(出邊權值)≥0]則立即進行撮合[3,4]。

復雜度分析：因已找到基本環，僅需對環上的節點進行檢測和撮合，時間復雜度為O(n)。

3.4公共節點撮合

假設多環C1,C2,…,Ck有一個公共節點(v=V(C1)∩…V(Ck))。如果多環的其他節點(非公共節點)均滿足可撮合條件，則利用銀行家算法，可避免死鎖的產生[9]。

算法1公共節點撮合

初始：v=V(C1)∩…∩V(Ck)

whileS≠φdo

if ?i,Ci∈S∧R(Ci)+A(v)≥0 then

對環Ci進行撮合;

A(v)=A(v)+R(Ci);

S=S-{Ci};

else

exit();

end

end

復雜度分析：在集合S中查找符合條件的環Ci需要執行k次，集合S的元素數量減少為k-1個，然后繼續查找，直至S為空，復雜度為O(k2)。在循環體內，需要執行撮合操作，復雜度為O(n)。因此，算法1的時間復雜度為O(nk2)。

定理2當環C1,C2,…,Ck均無法優先執行撮合時，C1,C2,…,Ck不可共同(同時)撮合。

3.5公共邊撮合

假設多環C1,C2,…,Ck有一個公共邊(e=[v1,v2]=E(C1)∩…E(Ck))。在多環的其他節點(不依附于公共邊的節點)均滿足可撮合條件的情況下，可按如下步驟進行撮合：(1)利用銀行家算法找出安全推進序列；(2)對于無法進行撮合的環，嘗試使用公共邊共同撮合。

(1) 公共邊有序撮合

與算法1類似，利用銀行家算法找出公共邊安全推進序列。引入變量：環資源需求(R)、公共節點剩余資源量(A)，兩者均為二維向量。

算法2公共邊按序撮合

初始：e=〈v1,v2〉=E(C1)∩…∩E(Ck);A=[dv1dv2]T;

whileS≠? do

對環Ci進行撮合;

A=A+R(Ci);

S=S-{Ci};

else

exit();

end

end

復雜度分析：與算法1相同，算法2的復雜度為O(nk2)。但因環資源需求R維度為2(涉及公共邊的兩個節點)，故無法做出排序優化。

(2) 公共邊共同撮合

在算法2撮合失敗的情況下，若對于該公共邊，其起點的入邊權值之和加上起點的清算賬戶余額大于公共邊的權值，且其終點的清算賬戶余額與公共邊的權值之和大于終點的出邊權值之和(簡稱“公共邊共同撮合條件”)，則多環可同時撮合清算。

算法3公共邊共同撮合

初始：e=〈v1,v2〉=E(C1)∩…E(Ck);

Fori={1..k} do

EndFor

Elseexit();

EndIf

復雜度分析：因只需要做一個判定條件，然后對k個環進行撮合，復雜度為O(nk)。

3.6多環有多個公共節點和多個公共邊情況分析

(1) 多個公共節點撮合

多環有多個公共節點的情況，可拆分為如下兩種情況或兩種情況的疊加。

情況1多環依次連續相交于一個公共點。假設多環C1,C2,…,Ck，且?i∈[1,…,k-1],vi=V(Ci)∩V(Ci+1)，則利用算法1，可得到偏序集[A,]。A上的“”關系定義如下：CxCyiff使用算法1，Cy在Cx之前優先執行。然后，通過偏序集構造哈斯圖(Hasse)[11]，找到偏序集中的極大元y：?x∈A,x=y(可能不唯一)。最后，使用拓撲排序，得出多環的執行順序(若哈斯圖不是線性圖形，則得出的線性序列可能不唯一)。

情況2兩環交于多點。假設兩環C1、C2交于多點，{v1,v2,…,vm}=V(C1)∩V(C2)，則在不同節點分別執行算法1，可得C1、C2的執行順序?i∈[1,…,m],C1RiC2。為了綜合不同節點處R之間的關系，如表1所示，定義“°”運算符。若?i,j∈[1,…,m](i≠j),Ri°Rj=?，則兩環必須等待，否則按照?i,j∈[1,…,m],Ri°Rj順序執行。

表1　“°”運算符

(2) 多個公共邊撮合

多環有多個公共邊的情況，可拆分為如下兩種情況或兩種情況的疊加。

情況1多環依次連續相交于一條公共邊。假設多環C1,C2,…,Ck，且?i∈[1,…,k-1],ei=〈vi1,vi2〉=E(Ci)∩E(Ci+1)，則利用算法2，可得到偏序集[A,]或共同撮合集合S={Ci,C2,…,Cj}?{C1,C2,…,Ck}(1≤i≤j≤k)，其中S中環的執行順序依賴于Ci和Cj在偏序集中的執行順序。若存在偏序集[A,]，使得相鄰兩環CiCi+1，則Ci+1優先執行撮合后，Ci+1上的所有邊(支付指令)均得到釋放(包括ei=E(Ci)∩E(Ci+1)。因此，缺少了ei這條邊，環Ci+1已經被破壞了。為方便生成計算機程序統一處理，可以生成一條ei虛擬支付指令(p(ei)=0)。

情況2兩環交于多條邊。假設兩環C=C1,C2交于多條邊，E*={e1,e2,…,em}=E(C1)∩E(C2)。具體執行方法分為如下兩種：(1)方法一：類似于3.6.1節情況2的討論，在不同邊分別執行算法2，可得到C1,C2的執行順序，然后利用“°”運算符得出最終執行順序；(2)方法二：在方法一失效的情況下，嘗試利用算法3，得出可撮合邊集合A={e1,e2,…,en}?{e1,e2,…,em}(n≤m)。如果E*的所有邊均屬于可撮合邊集合，則環C1,C2可參與公共邊共同撮合。

4　方案分析

4.1復雜度分析

本文提出的多邊撮合算法經歷了雙邊撮合、拓撲排序、查找基本環、撮合孤立可撮合環、公共節點撮合、公共邊撮合等一系列步驟，算法主要的耗費有兩點：(1)查找基本環，時間復雜度為：O(n32n)；(2)公共節點撮合：O(nklogk)或公共邊撮合：O(nk2)。因此，算法總的時間復雜度為:O(max{n32n,nklogk,nk2})=O(n32n)。顯然該算法的執行效率主要取決于查找基本環。

4.2算法應用

以下設計較為復雜的案例，然后應用算法解決問題。

(1) 多環交于多點

對與多環交于多點的情況，可拆分為多個兩環比較，得出偏序集，然后構造哈斯圖，通過拓撲排序得出最終執行順序。

如圖4(a)所示，環C1=<1,2,3,4>與環C2=<3,5,6,7,8,9>交于點3，環C2與環C3=<6,10,8,11,12>交于點{6,8}。首先，在點3處執行算法1，可得C1C2；同樣在點6處有C2=C3(R1=″=″)，而在點8處有C2?C3(R2=″?″)。由于R1°R2=?,故C2?C3。其次，如圖5(a)所示，根據環C1、C2與C3之間的偏序關系構造哈斯圖，通過拓撲排序得出環執行順序為C2->C1->C3或C2->C3->C1(圖5(b))。如圖4(b)所示，因為極大元是C2，優先撮合環C2。最后，C2撮合完成后，環C1和C3顯然都變成可撮合環，其執行順序沒有要求。

圖4　多環交于多點撮合案例

圖5　多環哈斯圖

(2) 多環交于多邊

對與多環交于多邊的情況，可拆分為多個兩環比較，得出偏序集或共同撮合集合，然后構造哈斯圖，通過拓撲排序得出最終執行順序。

如圖6(a)所示，環C1=<1,2,3,4>與環C2=<2,3,5,6,7,8,9>交于邊<2,3>，環C2與環C3=<5,6,12,8,9,10,11>交于邊<5,6>和<8,9>。首先，在邊<2,3>執行算法2，得到C1?C2。其次，在邊<5,6>上執行算法2，無法得到C2和C3的執行順序，進而嘗試執行算法3，發現C2和C3在邊<5,6>上可同時撮合清算。然后在邊<8,9>上執行算法3，C2和C3在邊<8,9>上亦可同時撮合清算。因為E*上的所有邊(<5,6,<8,9>)均屬于可撮合邊集合，所以C2和C3可參與公共邊共同撮合。如圖6(b)所示，當環C1優先執行后，邊<2,3>被同時釋放，環C2事實上已被破壞。為了使得C2和C3可參與同時撮合，生成一條虛擬邊<2,3>(p(<2,3>)=0)。最后，環C2和C3參與公共邊共同撮合。

顯然，算法可以很容易擴展到多環同時交于多點和多邊的復雜情況，限于篇幅，本文省略該情景。

圖6　多環交于多邊撮合案例

5　結　語

本文算法改進的主要意義是：(1)提出使用雙邊撮合和拓撲排序對有向圖進行簡化處理，剩下節點和邊必然構成環，通過減少有向圖中節點數(n)，降低查找基本環算法的時間復雜度過高的影響O(n32n)。(2)從全局角度考慮多環清算，通過考慮公共節點撮合和公共邊撮合，提升多邊撮合的性能：對于多環共用公共節點的情況，利用銀行家算法得出多環的安全推進序列；對于多環共用有向邊的情況，不僅給出多環的安全推進序列，還考慮了共同撮合的情景。有效解決了傳統撮合法無法進行多環撮合優化的問題，有利于參與機構節約流動性。

對于緊急支付指令，因其時間約束較高，其所在環應優先撮合，但緊急支付指令所在環優先執行撮合后，可能會造成其他環無法撮合，進而影響多邊撮合的目標。在應用前景上，本文算法亦可應用于第三方支付、證券交易清算等領域。

[1] Bank for International Settlements.Real-time gross settlement systems[R].Basle.Switzerland,1997.

[2] 陳錫明.支付系統流動性管理研究[J].南方金融,2013(10):85-88.

[3] 田立中，周昭濤，孔昭龍.利用有向圖解決支付清算中的“三角債”問題[J].今日科苑,2007,11(20):112.

[4] 孔昭龍.利用有向圖解決支付清算中的“三角債”的改進[J].今日科苑,2010,14(8):365.

[5] Jon Kleinberg,Eva Tardos.Algorithm design-影印版[M].北京:清華大學出版社,2012.

[6] Xiaonan Che.Markov type models for large-valued interbank payment systems[D].London School of Economics & Political Science,2011.

[7] James C Tiernan.An efficient search algorithm to find the elementary circuits of a graph[J].Communications of the ACM,1970,13(12):273-276.

[8] 王玉英,陳平,蘇旸.生成有向圖中全部簡單回路的一種有效算法[J].計算機應用與軟件,2009,26(12):27-29,33.

[9] Silberschatz A,Galvin P B,Gagne G.Operating System Concepts[M].9th ed.Wiley publication,2012.

[10] Main M,Savitch W.Data Structures and other Objects Using C++(Fourth Edition)影印版[M].北京:科學出版社,2012.

[11] H R Kenneth.Discrete Mathematics and its Application[M].北京:機械工業出版社,2012.

ANALYSIS AND DESIGN OF ELEMENTARY CIRCLES-BASED EFFICIENT MULTILATERAL OFFSETTING ALGORITHM IN REAL TIME GROSS SETTLEMENT SYSTEM

Li Shiliang

(The People’s Bank of China Shanghai Head Office,Shanghai 200120,China)

Traditional offsetting methods will immediately start to offset after finding an executable offsetting circle,which belong to the typical greedy algorithm.In view of this,the paper proposes an algorithm from the global perspective to consider the multi-cyclic clearing.First,the algorithm adopts bilateral offsetting and topological ordering to simplify a directed graph,and the rest of nodes and edges must constitute circles,which improves the efficiency of basic circles searching algorithm (time complexity:O(n32n)).In the case of multi-cyclic sharing common vertexes,the algorithm utilises the bank’s algorithm to obtain an orderly offsetting sequence.In the case of multi-cyclic sharing directed edges,the algorithm not only provides a multi-cyclic orderly offsetting sequence,but also considers the circumstance of common offsets.Through the above steps,the performance of the multilateral offsetting is improved,which saves the liquidity of participants and improves the efficiency of fund utilisation.Finally,the time complexity of the algorithm is analysed,and complex case applications (e.g.multi-cyclic sharing common multi-vertexes or multi-edges) are presented.

Elementary circlesReal time gross settlement systemClearingMultilateral offsetting

2015-05-29。李世梁，工程師，主研領域：支付清算系統，計算機網絡。

TP3

A

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