0 引言

电力生产系统需要严格控制间断性和状态的突变，因此要求电力通信网络的路由协议具有非常高的可靠性，并且能够及时应对故障，保证系统持续可靠地运行。不同于其他类型的网络，在电力通信网络中，站点与业务量的分布非常不均匀，这就导致部分关键的节点和链路承载着大量的网络流量，极大地影响了系统的可靠性^[1]。传统的因特网中负载均衡策略并不能很好地针对电力通信网络独特的结构特征与流量特征，无法满足电力通信网络极高可靠性的需求, 因此设计高效的负载均衡的路由策略是电力通信网络中非常重要的问题。

开放最短路径优先(Open Shortest Path First, OSPF)协议在电力信息网中得到了广泛的应用。在大规模的部署OSPF的网络中，网络拓扑会被划分成多个区域。当节点需要向所在区域外的目的地发送数据包时，需要首先将数据包发送到合适的边界路由器，并由边界路由器负责向区域外传输。作为不同区域间沟通的桥梁，边界路由器往往承载着大量的网络流量，一旦发生故障将对整个网络造成严重的影响。原始的OSPF算法的区域划分算法有较大的改进空间，已有的工作^[2-4]主要集中在如何根据实际需求对基于OSPF的网络进行更合理的区域划分。然而这些算法并不能从根本上解决边界路由器容易成为网络瓶颈的问题，不能很好地实现负载均衡。

OSPF协议是一个典型的确定性路由，当有数据包需要转发时，每个节点依据路由表选取确定的下一跳。通过收集准确的路由信息，确定性路由能够选出最优的转发路径，但当网络规模较大时，很难获取并维护全网范围内准确的路由信息，这也是OSPF协议进行区域划分的原因。机会路由协议被广泛应用到高度动态的无线网络中(如无线传感网^[5]与车载网^[6])，当节点进行数据包转发时，并不是指定一个确定的下一跳节点，而是根据实时的网络状态信息分配给候选节点相应的转发概率，然后从中动态选出下一跳作为转发节点。机会路由中节点不需要维护全局精确的路由信息，因而适合大规模的网络。此外，由于每个候选节点均有机会成为最终的转发节点，机会路由^[7-8]天然地具备高容错、负载均衡的特性。文献[9]针对OSPF中单一传输路径导致的文件下载响应时间长的问题，使用多路径负载均衡的技术对OSPF进行改进，能够减少文件下载的相应时间。文献[10]提出负载均衡优先的OSPF协议(Load Balance Advanced-OSPF, LBA-OSPF)，依据工作链路的负载动态调整链路的权重。文献[11]使用粒子群优化算法来实现多路径路由中的负载均衡，粒子群算法可以从理论上分析每条路径上的转发比例，路由策略可以依次进行转发策略的调整，有效地均衡网络的负载，降低丢包率。但是上述的负载均衡方案并没有考虑到区域划分对于负载均衡的影响，与区域内的普通节点相比，区域边界的边界节点往往承载着更大的网络流量，极容易成为网络的瓶颈。已有的算法很好地解决了同一个区域内的负载均衡问题，应用到多区域的OSPF网络依然存在网络负载不均衡的问题^[12]。

本文综合考虑确定性路由与机会路由的优点，提出一种适用于电力通信网络的负载均衡的路由协议。在局部范围内基于精确的路由信息部署确定性路由，而在全局范围内通过预估的远处代价对候选节点划分优先级并确定转发概率，实现高容错与负载均衡，避免瓶颈节点的产生。

1 候选节点集合的确定 1.1 OSPF区域与候选节点集合

在一个OSPF区域中，节点间通过交换链路状态通告(Link State Advertisement, LSA)可以获得该区域内所有节点的链路状态数据库(Link State DataBase，LSDB)。基于LSDB，每个节点可以生成最短路径树作为数据转发的依据来确定路由表，当网络状态发生变化时，通过LSA的交换，可以对LSDB进行更新，进而更新路由表。

由于节点可以获得本区域内较为准确的网络状态信息，当出现节点故障或链路故障时，通过OSPF的触发式更新机制，节点可以快速地基于更新后的LSDB进行重新选路。

机会路由最初是部署在无线网络中，当把其应用在有线网络时需要根据有线网络的特性进行相应的调整。与无线网络相比，有线网络相对稳定。在无线网络的机会路由中，候选节点集合都是从单跳邻居中进行筛选，主要原因是在高度动态的无线网络环境中，只能维护较为准确的单跳邻居信息。而对于相对稳定的有线网络，LSDB中往往包含较为准确的多跳邻居信息。于是本文可以从一个OSPF区域内进行候选节点集合的筛选，先机会地从候选节点集合中选出中继节点，然后基于最短路径树将数据包确定性地传递到选中的中继节点。

1.2 以节点为中心的区域划分

由于构建OSPF区域的目的是为了从中选择机会路由转发的候选节点集合，因此本文提出以节点为中心的区域划分算法。每个节点维护以自己为中心的由h(h≥2)跳邻居构成的区域，并通过LSA来维护该区域的LSDB。为了给每个节点构建以自己为中心的区域，LSA以受限广播的方式进行发送。同样采用OSPF中LSA的触发式更新机制，当某个节点或链路状态发生变化时，该LSA最多会被在状态变化点h跳邻居范围内传播，收到该LSA的节点对自己的LSDB进行更新。

1.3 区域出口节点的确定

根据由以本节点为中心的h(h≥2)跳邻居构成的区域，节点可以从中确定候选节点集合。候选节点集合由该区域的出口节点构成，即一个节点可以通过将数据包转发给候选节点来进一步将数据包转发至更远的节点。

如图 1所示的拓扑中，本文以节点S为例介绍如何确定节点S的候选节点集合。图中用黑色线框表示了以S为中心的区域的大小，在示例中使用两跳(h=2)的邻居构建以节点自身为中心的区域。节点A，B，C，D与E构成了节点S的第一跳邻居，节点f、g、h、i、j与k构成了节点S的第二跳邻居。这些第二跳邻居中，节点g、h、i与k能够与区域外的节点交互，称之为区域的出口。因此，{g，h，i，k}构成了节点S的候选节点集合。而第一跳邻居与非区域出口的第二跳邻居构成了候选节点的服务节点集合{A，B，C，D，E，f，j}。当S进行数据转发时，如果目的地在以自己为中心的区域内，直接依据LSDB构建最短路径树进行确定性转发；如果目的地在区域外，则依据候选节点的优先级与转发概率动态的选出转发节点。下一节将介绍如何确定候选节点的优先级与转发概率。

2 候选节点优先级与转发概率的确定

对一个进行数据包转发的节点，使用以自身为中心的区域的出口节点构建初始的候选节点集合后，需要为候选节点依据特定的目的节点确定优先级与转发概率。

2.1 近处代价与远处代价

对于一个候选节点，当其被选中时到达目的节点的端到端代价越小，对应的优先级越高，相应的转发概率就越大。例如，对于两个候选节点，如果一个位于目的节点所在的方向，一个位于目的节点相反的方向。显然位于相同方向的候选节点具备更高的优先级与转发概率，更有甚者，位于相反方向的候选节点可以将转发概率设置为零。

一个候选节点对应的代价包含近处代价与远处代价两部分:近处代价指的是发送节点依据最短路径树在本区域内到达候选节点的路径的代价；远处代价指的是候选节点到达目的节点期望的端到端代价。

依据LSDB，很容易计算出到达一个候选节点最佳路径对应的近处代价。而远处代价需要分两种情况去考虑：如果目的节点位于以该候选节点为中心的区域内，依据该候选节点的LSDB，可以获得从该候选节点到达目的节点最佳路径对应的远处代价；如果目的节点不在以该候选节点为中心的区域内，考虑到机会路由的特性，本文需要考虑以该候选节点为源节点到达目的节点所有潜在路径平均的端到端代价，并以此作为该候选节点的远处代价。

图 2给出了两种情况下如何去获得候选节点对应的端到端代价，其中云状图表示省略未画出的网络拓扑。若源节点S要发送数据包到目的节点C，若候选节点A被选为中继节点，路径S→A→C的端到端代价为:

$ {D_{SAC}} = {d_{SA}} + {D_{AC}} = {d_{SA}} + {d_{AC}} $

(1)

使用d表示近处代价，使用D表示远处代价或端到端代价，d_SA指在以源节点S为中心的区域内按照最短路径树到达候选节点A的近处代价，图中使用虚线的原因是因为，从S到A有可能需要区域内的其他节点中转。由于目的节点C在以候选节点A为中心的区域内，所以D_AC=d_AC。若源节点S要发送数据包到目的节点G，如果候选节点B被选为中继节点，则路径S→B→G包括两个部分，以源节点S为中心的区域内路径d_SB，以及候选节点B到达目的节点G的远处代价D_BG，由于目的节点G不在以候选节点B为中心的区域内，要获得D_BG，我们需要综合考虑从候选节点B到目的节点G所有的潜在路径B→D→G，B→E→G与B→F→G。

$ \begin{array}{*{20}{l}} {{D_{SBG}} = {d_{SB}} + {D_{BG}} = }\\ {\;\;\;\;\;\;\;\;\;\;{d_{SB}} + {p_{BD}}{D_{BDG}} + {p_{BE}}{D_{BEG}} + {p_{BF}}{D_{BFG}}} \end{array} $

(2)

其中p_BD指的是当节点B发送数据包时，候选节点D被选中的概率，即转发概率。由式(2)可以看出，远处代价的获得使用的是类似于距离矢量路由协议的机制，即使用邻居节点的端到端代价用于自身端到端代价的计算。为了避免环路，如果一个候选节点比发送节点到达目的节点的代价要大，需要将该候选节点从初始的候选节点集合中移除。基于更新后的候选节点集合，本文对候选节点的转发概率进行分析。

2.2 转发概率

对于一个特定的目的节点并不是所有的候选节点(指的是经过避免环路处理后的候选节点)都有机会成为最终的转发节点，因为有些候选节点会将数据包转发到代价较高的路径上。如果只有很少的候选节点有机会成为转发节点，机会路由高容错与负载均衡的特点就没有体现出来。因此，需要很好地权衡哪些候选节点有机会成为转发节点并为它们分配转发概率。本文使用因子α(0≤α≤1)表示转发概率非零的候选节点占总的候选节点的比重：α=1表明每个候选节点均有非零的转发概率，都有机会成为最终的转发节点，这种情况下负载均衡的性能是最好的；当α≤1/N_S(N_S为发送节点S候选节点的数目)时，机会路由退化成确定性路由，即确定的选择端到端代价最小的候选节点作为最终的转发节点，此时负载均衡的性能很差。根据网络状况设置合适的α可以同时获得较低的端到端代价与较好的负载均衡的性能。

选择端到端代价最小的αN_S个候选节点获得非零的转发概率，这些候选节点表示为i₁, i₂, …, i_αNS。对于目的节点G，每个候选节点的转发概率为:

$ {p_{S{i_k}}} = D_{S{i_k}}^{ - 1}/\sum\limits_{j = 1}^{\alpha {N_S}} {D_{S{i_j}G}^{ - 1}} ;k = 1,2, \cdots ,\alpha {N_S} $

(3)

其中分子D^-1_SikG为i_k被选为中继节点时对应的端到端代价的倒数，分母为所有候选节点端到端代价倒数之和。用这个比值作为转发概率的物理意义是端到端代价越小的候选节点对应着较大的转发概率。

2.3 远处代价的维护

发送节点远处代价的获得依赖于候选节点的端到端代价，当候选节点的端到端代价发生变化时，需要对发送节点的远处代价以及端到端代价进行调整。远处代价的作用主要是指引路由转发的方向，又因为维护远处代价需要引入较大的维护代价，因此本文使用长效时间内的均值来表征远处代价的平均性能，并且设置远处代价的更新频率远低于区域内近处代价基于LSA的更新频率。当一个节点的端到端代价的变化超过一定比例后，会发送更新包给本区域内的节点，所有将该节点作为候选节点的节点会更新自身的端到端代价。以节点i为例，若节点i之前的端到端代价为D_{i, old}，接收到某个候选节点代价变化信息进行更新后的代价为D_{i, new}，为了体现端到端代价长效时间范围内的平均性能，本文将节点i的端到端代价设置为：

$ {D_i} = \left( {1 - \beta } \right)*{D_{i,{\rm{old}}}} + \beta *{D_{i,{\rm{new}}}} $

(4)

其中β(0≤β≤1)为更新后代价占的权重。

使用远处代价指引大致的转发方向，并在路由推进的过程中，每个中继节点都在本区域内使用精确的代价选择最优的路径可以使得本文提出的路由协议在引入可接受的维护代价的情况下获得较低的端到端代价。

2.4 算法描述

提出的电力通信网络中负载均衡的路由算法描述如下：

1)为每个节点构建初始的候选节点集合。

①将以该节点为中心的h跳拓扑作为本地区域；

②选出本地区域的出口节点作为初始的候选节点集合。

2)确定源节点到目的节点的端到端代价。

①基于源节点的本地区域LSDB计算精确的近处代价；

②对每个候选节点端到端代价按照转发概率加权平均获得远处代价；

③候选节点端到端代价发生变化时对远处代价与该节点端到端代价进行更新。

3)源节点有数据包转发时，依据转发概率选择一个候选节点作为转发节点。

①基于最短路径树将数据包发送到转发节点；

②将转发节点作为源节点进行进一步的转发。

3 算法的优化

2.4节提出的算法需要每个节点维护到达所有节点的端到端代价，将会造成大量的存储代价与维护代价。

本文采用类似车载网络中以街道为中心的两级路由的方案来解决上述问题。在车载网络中，用街道代替车辆作为路由转发的单位是一种有效减少因为需要存储或维护大量目的节点的信息而产生的代价的有效方案。在路由决策时只需首先关心目标节点所在的街道以及转发路径上的街道序列，称之为街道间转发；在街道内转发时可以根据车辆在街道内的位置确定合适的转发车辆序列，称之为街道内转发。类似地，本文采用以区域为中心的两级路由的方案，首先将数据包转发到目的节点所在区域，然后再将数据包送到区域内所在的特定目的节点。使用这种策略，每个节点只需维护到达特定区域中心的端到端代价，大幅减少了存储与维护的代价。

与车载网络不同的是，街道是自然存在的，而电力网络中的区域需要对全网拓扑进行划分。由于对全网拓扑的操作代价很高，于是使用最简单的基于地理位置的全网拓扑的划分，在特定地理位置范围内的节点被划分在同一个区域。可以在网络的初始化配置阶段完成这一步骤。每个节点在获得其他节点地理位置信息后判断该节点属于哪个区域，然后选取最靠近该区域中心的节点作为该区域的代表，维护到达该代表节点的端到端代价与候选节点集合。当源节点有数据包需要转发时，首先根据其地理位置信息判断属于哪个全局区域，然后以该全局区域的代表节点为目的地进行机会路由转发。当数据包被转发进入目的节点所在的全局区域后，就没有必要先将数据包转发到该区域的中心节点了，因为目的节点与当前的转发节点已经距离很近了，可以依据更精确的信息直接将数据包转发到目的节点。如果将全局区域的大小设置成小于以节点为中心的本地区域的大小，一旦发现目的节点在某个转发节点为中心的本地区域时就直接依据最短路径树进行发送。

虽说全网区域的划分以及区域中心节点的选择是固定的，但是并不影响网络的容错与负载均衡性能。这是因为全局区域的中心只是作为数据转发的一个方向，将数据包引导到目的节点所在的全局区域，一旦数据包进入了目的节点所在的全局区域，区域中心对于路由转发就不再产生影响。全局区域的中心节点并没有承担过多的网络负载，即便其产生故障，对于路由的转发也不会有严重的影响，进入目标区域后完全可以根据局部精确的网络状态信息选出合适的转发路径。

4 实验 4.1 实验设置

本文实验拓扑采用芜湖市电力通信广域网由67台路由器构成的真实网络。本文分别在网络中部署传统的OSPF协议，负载均衡优先的LBA-OSPF协议^[10]以及本文提出的负载均衡的机会路由协议(Load Balanced Opportunistic Routing，LBOR)。在单条流与多条流的场景下通过增大数据包发送速率分别评测两种路由协议的负载均衡性能与端到端时延性能。其中，数据包的大小为2000 b，链路的带宽为10 Mb/s，数据包的发送速率从每秒1000个数据包依次增加到每秒5000个。依据芜湖电力广域网拓扑的规模，本文使用两跳的邻居作为每个节点本地区域的大小，并依据本文算法从中选出合适的候选节点集合。

4.2 实验结果与分析

图 3描述了当网络中只存在单条流时随着数据包发送速率的增长节点的平均负载如何变化。节点的平均负载指的是节点接收并处理的数据包的总数除以进行过数据包转发的节点的总数。LBOR协议能够显著减少每个节点的平均负载。当数据包的发送速率增大时，性能的提升更加明显。这是因为在LBOR协议中，当一个节点发送数据包时，会依据转发概率将数据包动态的转发给候选节点集合中的节点，每个候选节点均有机会成为最终的转发节点，数据包将均衡地分布在多条路径上。而在传统的OSPF协议中，当选中一条转发节点后，数据包将会一直转发给确定的转发节点并沿着固定的路径进行转发，造成较大的节点平均负载。LBA-OSPF协议同样考虑了负载均衡，并且在只存在单条流时与LBOR有着非常接近的性能。

图 4描述了当数据包的发送速率增大时，平均的端到端时延如何变化。当数据包的发送速率较小时，网络中的流量较小，这时候三种路由协议的端到端时延性能差别不大，但当数据包发送速率持续增大时，链路与路由器的处理能力受到更严峻的挑战，更多的排队时延的引入会导致端到端时延的增加。LBOR协议与传统的OSPF协议相比，可以将数据包均衡在多条潜在的转发路径上，有效地避免确定性路由单一转发节点的大量排队时延的问题，在高流量时有更小的端到端时延。与LBA-OSPF协议相比，LBOR有着一定的性能提升。

在更实际的网络场景中，网络中会随机产生多条数据流。在这种情况下，一些位置比较关键的节点，如OSPF区域的边界结点，将会承担多条流的汇聚流量，造成过大的负载压力，影响路由的性能。图 5描述了在多条流的网络场景下，节点的平均负载随数据包发送速率增大的变化趋势。在这种场景下，LBOR相对于LBA-OSPF与OSPF的性能优势比单条流的场景下更加明显，节点的平均负载分别降低了32.3%与41.7%；并且随着数据包发送速率的增大性能提升更加显著。LBA-OSPF虽然有着一定的负载均衡的能力，但在跨区域传输时仍然需要先将数据包转发到区域的边界节点，在数据量较大时边界节点仍然会成为网络的瓶颈。上述结果验证了LBOR有较强的负载均衡的能力，在处理多条流的实际网络场景时有更好的适应性。

图 6描述了在电力网络中多条流的场景下，数据包传输的平均端到端时延随数据包发送速率的变化趋势。当每条流增大其数据包的发送速率，即增大每条流的流量时，OSPF与LBA-OSPF的端到端时延性能急剧恶化。这是因为大量的数据包将汇聚在OSPF区域的边界节点，引入大量的排队时延。而LBOR能够有效避免“热点”的产生，数据流量均衡的分布在多条路径上，不会出现某一节点产生的大量的排队时延。因此在数据包发送速率增大后，时延性能与LBA-OSPF与OSPF相比有着显著的提升，分别降低了50.3%与60.4%。

5 结语

本文针对电力通信网络的特点，设计了一个高容错、负载均衡的机会路由协议，能够有效地平衡网络中节点的负载，避免出现OSPF网络中区域边界路由器承载大量网络流量的问题。首先每个节点建立以自身为中心的区域，并从中选出数据包转发的候选节点结合。依据近处代价与远处代价，为每个候选节点设置对应的转发概率。这样每个候选节点均有机会成为转发节点，网络中的流量将会被分流在多条潜在的端到端路径上，有效地实现了负载均衡和减少了排队时延。我们基于芜湖市电力通信广域网的拓扑在单条流与多条流的场景下分别进行实验仿真，实验结果证明本文提出的负载均衡的路由协议能够显著地提升路由性能，在高流量的网络环境中性能的提升尤为明显。