霍如，倪东，卢华，夏云峰，汪硕,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%。