實(shí)時(shí)全額支付系統(tǒng)中基于基本環(huán)的高效多邊撮合算法分析和設(shè)計(jì)

李 世 梁

(中國(guó)人民銀行上海總部　上海 200120)

?

實(shí)時(shí)全額支付系統(tǒng)中基于基本環(huán)的高效多邊撮合算法分析和設(shè)計(jì)

李 世 梁

(中國(guó)人民銀行上海總部上海 200120)

基本環(huán)實(shí)時(shí)全額支付系統(tǒng)清算多邊撮合

0　引　言

在跨行轉(zhuǎn)賬支付系統(tǒng)中，大額支付系統(tǒng)是各國(guó)最重要的支付系統(tǒng)。經(jīng)大額支付系統(tǒng)處理和清算的支付(資金轉(zhuǎn)賬)指令，通常具有數(shù)量多、金額大、實(shí)時(shí)性要求高等特點(diǎn)，已成為連接社會(huì)經(jīng)濟(jì)活動(dòng)及其資金運(yùn)行的“大動(dòng)脈”。若一家或多家參與機(jī)構(gòu)(成員銀行)發(fā)生信用或流動(dòng)性風(fēng)險(xiǎn)，可能會(huì)影響整體金融穩(wěn)定，進(jìn)而引發(fā)系統(tǒng)性金融危機(jī)[1,2]。

在跨行轉(zhuǎn)賬支付系統(tǒng)中，有兩種基本的清算模型：實(shí)時(shí)全額支付系統(tǒng)(RTGS)和延遲凈額結(jié)算系統(tǒng)(DNS)。根據(jù)國(guó)際清算銀行的定義，在RTGS中，資金轉(zhuǎn)賬指令的處理和最終清算是實(shí)時(shí)連續(xù)的，對(duì)參與機(jī)構(gòu)流動(dòng)性要求高但結(jié)算風(fēng)險(xiǎn)小；而在延遲凈額結(jié)算系統(tǒng)(DNS)中，指令是周期性地在某一時(shí)間點(diǎn)進(jìn)行軋差，能夠節(jié)約參與者流動(dòng)性但結(jié)算風(fēng)險(xiǎn)較高[1]。為了降低金融風(fēng)險(xiǎn)，RTGS已成為包括中國(guó)在內(nèi)的多數(shù)國(guó)家構(gòu)建大額支付系統(tǒng)的主要形式。

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

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

1　國(guó)內(nèi)外研究現(xiàn)狀

為描述方便，本文采用有向圖描述法，參與機(jī)構(gòu)代號(hào)和其清算賬戶余額作為節(jié)點(diǎn)的屬性，其中代號(hào)在節(jié)點(diǎn)的上部，余額在節(jié)點(diǎn)的下部。支付指令抽象為付款方至收款方的有向邊，將交易金額作為有向邊的權(quán)值。

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

通常，簡(jiǎn)化撮合圖往往包括多個(gè)可撮合子圖，理想狀態(tài)下，希望一次撮合能找出所有可撮合子圖，一次計(jì)算完成所有“三角債”的清理[3,4]。

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

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

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

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

因此本文研究基于基本環(huán)的多邊撮合算法，優(yōu)化撮合性能。

圖1　撮合案例

2　問題描述

在RTGS中，各參與機(jī)構(gòu)存儲(chǔ)資金或提供質(zhì)押融資至其央行清算賬戶，以發(fā)送和執(zhí)行各類貸記指令。參與機(jī)構(gòu)發(fā)送的貸記指令，需要同時(shí)貸記付款方的清算賬戶，并借記收款方的清算賬戶，以維持會(huì)計(jì)平衡，具有逐筆處理業(yè)務(wù)、全額清算資金、資金實(shí)時(shí)到賬的特點(diǎn)[1]。

3　基于基本環(huán)的多邊撮合算法原理和過(guò)程

首先對(duì)有向圖G={V,E}(|V|=n,|E|=m)進(jìn)行簡(jiǎn)化處理，進(jìn)行雙邊撮合，利用拓?fù)渑判蚍ㄏ荒軜?gòu)成環(huán)的有向邊，然后利用查找基本環(huán)算法生成全部基本環(huán)。對(duì)于多環(huán)共用公共節(jié)點(diǎn)的情況，利用銀行家算法得出多環(huán)安全推進(jìn)序列(詳見3.4節(jié))；對(duì)于多環(huán)共用有向邊的情況，不僅給出多環(huán)安全推進(jìn)序列，還應(yīng)考慮共同撮合的情景；最后，對(duì)支付指令進(jìn)行消除處理。

3.1有向圖簡(jiǎn)化處理

(1) 雙邊撮合

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

圖2　雙邊撮合案例

(2) 拓?fù)渑判?/p>

有向有環(huán)圖的一個(gè)特點(diǎn)是，所有節(jié)點(diǎn)的入度大于0。因此，可得如下定理：

定理1利用拓?fù)渑判蚩煽焖傧邢驁D中不能構(gòu)成環(huán)的節(jié)點(diǎn)和邊。

證明根據(jù)有向無(wú)環(huán)圖的一個(gè)定理：如果圖G存在一個(gè)拓?fù)渑判颍瑒tG是一個(gè)有向無(wú)環(huán)圖[5]。該定理的逆否命題是：如果圖G是一個(gè)有向有環(huán)圖，則G不存在拓?fù)渑判颉Ｒ虼耍衫猛負(fù)渑判蚍ǎ紫仍趫DG中查找一個(gè)入度為0的節(jié)點(diǎn)v，然后在圖G中刪除v及其關(guān)聯(lián)的出邊，重復(fù)此過(guò)程，直至圖G中不存在入度為0的節(jié)點(diǎn)。

圖3　拓?fù)渑判虬咐?/p>

如圖3(a)所示，首先，節(jié)點(diǎn)6的入度為0，則刪除節(jié)點(diǎn)6及其關(guān)聯(lián)的兩條邊(p62和p65)；然后，如圖3(b)所示，節(jié)點(diǎn)5的入度由1變?yōu)?，同樣刪除節(jié)點(diǎn)5及其關(guān)聯(lián)的一條邊(p53)；最后，如圖3(c)所示，只剩下節(jié)點(diǎn)入度大于0的節(jié)點(diǎn)(可構(gòu)成環(huán))。

復(fù)雜度分析：設(shè)有向圖中有n個(gè)節(jié)點(diǎn)、m條邊，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為O(m+n)[5]。

3.2查找基本環(huán)

本文提出的多邊撮合算法需要基于有向圖的基本環(huán)。在查找有向圖的所有基本環(huán)方面，已經(jīng)有很多研究。例如，James C.Tiernan提出的查找算法，該算法理解簡(jiǎn)單、易于使用程序語(yǔ)言實(shí)現(xiàn)，其經(jīng)過(guò)路徑拓展、環(huán)確認(rèn)、節(jié)點(diǎn)關(guān)閉、向前推移起始節(jié)點(diǎn)等步驟，可獲得一個(gè)有向圖的所有簡(jiǎn)單基本環(huán)[7]。而國(guó)內(nèi)也有針對(duì)查找基本環(huán)方面的優(yōu)化算法，例如，王玉英等[8]提出的查找算法，在算法復(fù)雜度方面做了一些優(yōu)化，時(shí)間復(fù)雜度為O(n32n)。

3.3撮合孤立可撮合環(huán)

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

復(fù)雜度分析：因已找到基本環(huán)，僅需對(duì)環(huán)上的節(jié)點(diǎn)進(jìn)行檢測(cè)和撮合，時(shí)間復(fù)雜度為O(n)。

3.4公共節(jié)點(diǎn)撮合

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

算法1公共節(jié)點(diǎn)撮合

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

whileS≠φdo

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

對(duì)環(huán)Ci進(jìn)行撮合;

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

S=S-{Ci};

else

exit();

end

end

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

定理2當(dāng)環(huán)C1,C2,…,Ck均無(wú)法優(yōu)先執(zhí)行撮合時(shí)，C1,C2,…,Ck不可共同(同時(shí))撮合。

3.5公共邊撮合

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

(1) 公共邊有序撮合

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

算法2公共邊按序撮合

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

whileS≠? do

對(duì)環(huán)Ci進(jìn)行撮合;

A=A+R(Ci);

S=S-{Ci};

else

exit();

end

end

復(fù)雜度分析：與算法1相同，算法2的復(fù)雜度為O(nk2)。但因環(huán)資源需求R維度為2(涉及公共邊的兩個(gè)節(jié)點(diǎn))，故無(wú)法做出排序優(yōu)化。

(2) 公共邊共同撮合

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

算法3公共邊共同撮合

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

Fori={1..k} do

EndFor

Elseexit();

EndIf

復(fù)雜度分析：因只需要做一個(gè)判定條件，然后對(duì)k個(gè)環(huán)進(jìn)行撮合，復(fù)雜度為O(nk)。

3.6多環(huán)有多個(gè)公共節(jié)點(diǎn)和多個(gè)公共邊情況分析

(1) 多個(gè)公共節(jié)點(diǎn)撮合

多環(huán)有多個(gè)公共節(jié)點(diǎn)的情況，可拆分為如下兩種情況或兩種情況的疊加。

情況1多環(huán)依次連續(xù)相交于一個(gè)公共點(diǎn)。假設(shè)多環(huán)C1,C2,…,Ck，且?i∈[1,…,k-1],vi=V(Ci)∩V(Ci+1)，則利用算法1，可得到偏序集[A,]。A上的“”關(guān)系定義如下：CxCyiff使用算法1，Cy在Cx之前優(yōu)先執(zhí)行。然后，通過(guò)偏序集構(gòu)造哈斯圖(Hasse)[11]，找到偏序集中的極大元y：?x∈A,x=y(可能不唯一)。最后，使用拓?fù)渑判颍贸龆喹h(huán)的執(zhí)行順序(若哈斯圖不是線性圖形，則得出的線性序列可能不唯一)。

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

表1　“°”運(yùn)算符

(2) 多個(gè)公共邊撮合

多環(huán)有多個(gè)公共邊的情況，可拆分為如下兩種情況或兩種情況的疊加。

情況1多環(huán)依次連續(xù)相交于一條公共邊。假設(shè)多環(huán)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中環(huán)的執(zhí)行順序依賴于Ci和Cj在偏序集中的執(zhí)行順序。若存在偏序集[A,]，使得相鄰兩環(huán)CiCi+1，則Ci+1優(yōu)先執(zhí)行撮合后，Ci+1上的所有邊(支付指令)均得到釋放(包括ei=E(Ci)∩E(Ci+1)。因此，缺少了ei這條邊，環(huán)Ci+1已經(jīng)被破壞了。為方便生成計(jì)算機(jī)程序統(tǒng)一處理，可以生成一條ei虛擬支付指令(p(ei)=0)。

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

4　方案分析

4.1復(fù)雜度分析

本文提出的多邊撮合算法經(jīng)歷了雙邊撮合、拓?fù)渑判颉⒉檎一经h(huán)、撮合孤立可撮合環(huán)、公共節(jié)點(diǎn)撮合、公共邊撮合等一系列步驟，算法主要的耗費(fèi)有兩點(diǎn)：(1)查找基本環(huán)，時(shí)間復(fù)雜度為：O(n32n)；(2)公共節(jié)點(diǎn)撮合：O(nklogk)或公共邊撮合：O(nk2)。因此，算法總的時(shí)間復(fù)雜度為:O(max{n32n,nklogk,nk2})=O(n32n)。顯然該算法的執(zhí)行效率主要取決于查找基本環(huán)。

4.2算法應(yīng)用

以下設(shè)計(jì)較為復(fù)雜的案例，然后應(yīng)用算法解決問題。

(1) 多環(huán)交于多點(diǎn)

對(duì)與多環(huán)交于多點(diǎn)的情況，可拆分為多個(gè)兩環(huán)比較，得出偏序集，然后構(gòu)造哈斯圖，通過(guò)拓?fù)渑判虻贸鲎罱K執(zhí)行順序。

如圖4(a)所示，環(huán)C1=<1,2,3,4>與環(huán)C2=<3,5,6,7,8,9>交于點(diǎn)3，環(huán)C2與環(huán)C3=<6,10,8,11,12>交于點(diǎn){6,8}。首先，在點(diǎn)3處執(zhí)行算法1，可得C1C2；同樣在點(diǎn)6處有C2=C3(R1=″=″)，而在點(diǎn)8處有C2?C3(R2=″?″)。由于R1°R2=?,故C2?C3。其次，如圖5(a)所示，根據(jù)環(huán)C1、C2與C3之間的偏序關(guān)系構(gòu)造哈斯圖，通過(guò)拓?fù)渑判虻贸霏h(huán)執(zhí)行順序?yàn)镃2->C1->C3或C2->C3->C1(圖5(b))。如圖4(b)所示，因?yàn)闃O大元是C2，優(yōu)先撮合環(huán)C2。最后，C2撮合完成后，環(huán)C1和C3顯然都變成可撮合環(huán)，其執(zhí)行順序沒有要求。

圖4　多環(huán)交于多點(diǎn)撮合案例

圖5　多環(huán)哈斯圖

(2) 多環(huán)交于多邊

對(duì)與多環(huán)交于多邊的情況，可拆分為多個(gè)兩環(huán)比較，得出偏序集或共同撮合集合，然后構(gòu)造哈斯圖，通過(guò)拓?fù)渑判虻贸鲎罱K執(zhí)行順序。

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

顯然，算法可以很容易擴(kuò)展到多環(huán)同時(shí)交于多點(diǎn)和多邊的復(fù)雜情況，限于篇幅，本文省略該情景。

圖6　多環(huán)交于多邊撮合案例

5　結(jié)　語(yǔ)

本文算法改進(jìn)的主要意義是：(1)提出使用雙邊撮合和拓?fù)渑判驅(qū)τ邢驁D進(jìn)行簡(jiǎn)化處理，剩下節(jié)點(diǎn)和邊必然構(gòu)成環(huán)，通過(guò)減少有向圖中節(jié)點(diǎn)數(shù)(n)，降低查找基本環(huán)算法的時(shí)間復(fù)雜度過(guò)高的影響O(n32n)。(2)從全局角度考慮多環(huán)清算，通過(guò)考慮公共節(jié)點(diǎn)撮合和公共邊撮合，提升多邊撮合的性能：對(duì)于多環(huán)共用公共節(jié)點(diǎn)的情況，利用銀行家算法得出多環(huán)的安全推進(jìn)序列；對(duì)于多環(huán)共用有向邊的情況，不僅給出多環(huán)的安全推進(jìn)序列，還考慮了共同撮合的情景。有效解決了傳統(tǒng)撮合法無(wú)法進(jìn)行多環(huán)撮合優(yōu)化的問題，有利于參與機(jī)構(gòu)節(jié)約流動(dòng)性。

對(duì)于緊急支付指令，因其時(shí)間約束較高，其所在環(huán)應(yīng)優(yōu)先撮合，但緊急支付指令所在環(huán)優(yōu)先執(zhí)行撮合后，可能會(huì)造成其他環(huán)無(wú)法撮合，進(jìn)而影響多邊撮合的目標(biāo)。在應(yīng)用前景上，本文算法亦可應(yīng)用于第三方支付、證券交易清算等領(lǐng)域。

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

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

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

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

[5] Jon Kleinberg,Eva Tardos.Algorithm design-影印版[M].北京:清華大學(xué)出版社,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] 王玉英,陳平,蘇旸.生成有向圖中全部簡(jiǎn)單回路的一種有效算法[J].計(jì)算機(jī)應(yīng)用與軟件,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].北京:科學(xué)出版社,2012.

[11] H R Kenneth.Discrete Mathematics and its Application[M].北京:機(jī)械工業(yè)出版社,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。李世梁，工程師，主研領(lǐng)域：支付清算系統(tǒng)，計(jì)算機(jī)網(wǎng)絡(luò)。

TP3

A

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