基于BA网络的突发事件下静态局部路由策略研究

仇多利，梁昌勇，肖建于，李 晨①

（1.合肥工业大学 管理学院，安徽 合肥 230000；2.淮北师范大学 计算机科学与技术学院，安徽 淮北 235000；3.苏试试验集团股份有限公司，江苏 苏州 215000）

0 引言

随着汽车数量的急剧增加，路网负载急距增大，城市管理者可通过优化路网布局解决路网堵问题，增加道路容量，比如完善立体交通、增加车道数、加强停车场建设等，但此类方法综合成本较高，因此可通过对网络模型的研究了解现实路网的内部运行机制，结合突发事件，提出有效的交通路由策略，对于解决路网拥堵问题经济且省时。

60年代初，Erdost提出著名的ER随机图模型，成为复杂网络研究的基础理论。Watts等［1］研究从静态网络向随机网络动态变化的演变过程，提出既拥有规则网络的聚类特性，又拥有随机网络所具有的平均路径长度小的小世界网络。Barabasi等［2］提出度分布符合幂分布的BA网络，指出度数较大的个别节点对网络传输能力起决定性作用。越来越多的学者在BA网络的基础上研究网路拥堵和相变过程。Valverde等［3］考虑BA网络的异质性，模拟交通流的传输过程。Holme等［4］通过控制BA网络一些度大的节点，从而提升网络传输性能。于灏等［5］通过加入适当比例的“受控边”，在网络连接边带宽资源总量固定的条件下，重新分配带宽资源。魏钢等［6］通过对数据包设置优先级和采取动态排队策略，改善传输率。郑文萍等［7］基于成生图模型提出一种具有社区结构的可调节聚集系统和模块性的无标度网络生成算法，该算法采用合理的连边策略，能尽可能维持网络的无标度特征。段佳勇等［8］通过优化系统与网络节点的关联度，通过计算关联度最优时网络各参数值，从而获得理想的网络模型。董昂等［9］针对复杂网络中失效节点或边产生的级联效应，基于初始负载定义对级联故障模型的影响，提出基于局部熵的初始负载定义方式，并验证局部熵的有效性。陆秋琴等［10］利用对偶法构建路网拓扑模型，提出路网在随机换效条件下其可靠性模型和可靠性指数计算方法。王碧瑶等［11］提出一种节点重要度计算方法，结合复杂网络相关理论分析城市轨道交通网络的脆弱性，得出单节点攻击对轨道交通网络的影响较小，累计节点蓄意攻击下轨道交通网络表现出较强的脆弱性。

路由策略好坏很大程度上决定网络性能，因此研究如何优化路由策略，使网络吞吐量达到最大，是近些年研究的热点问题。Wang等［12］提出一种基于局域信息的路由策略，通过设置调节参数α改变路由策略，有利于数据包传输过程避开网络中度数大的节点，降低网络造成堵塞的可能性。Yan等［13］提出的“有效路由”策略可以使数据包在传输过程有效避开原本路径中一些会发生交通拥堵的节点。王开等［14］提出基于随机行走理论的路由优化策略，通过调节可变参数，建立节点处理能力均匀分布的路由策略。文宏等［15］通过优化配置节点处理能力和路由算法参数来提高网络性能的新方法，增加网络容量，减少报文路由时间。罗开田等［16］研究基于引力场理论的动态路由选择过程，提出在介数约束下的引力场路由选择策略。荆霞等［17］将多环网络中的复杂路由问题转换为单环网中的简单路由，结合路径还原算法，将单一环网改进为增强型环网拓扑，使同一环内通信节点间的路径还原为完整最短路径。

目前，城市路网流量经常出现过饱和，若发生突发事件，极易导致交叉口路段交通瘫痪，车辆甚至行人常处于进退两难的境地，拥堵同样使得救援工作困难重重。因此，通过理论方法研究突发事件下的交通拥堵疏散策略，一方面可以避免突发事件所造成的影响，另一方面可以为疏散车辆和行人提供现实指导方法。本文以关键数据节点突发通信能力降低为基础进行基于BA网络的路网建模，研究将静态局部路由策略应用在网络遇到突发事件模型下，带有主动选择偏好性的交通路由策略，通过仿真模拟不同程度突发事件下最优偏好性参数和优化后的静态局部路由策略下网络临界信息包产生率，以使整个网络数据包在各节点的分布更加均匀，从而减少数据包传输时间，降低突发事件对网络交通传输的影响。

1 BA无标度网络模型

网络模型构造如下:设一个全连通网络的节点数为N，网络中的节点数量随每个时间步长逐个增加，加入的节点根据式（1）的概率值在原网络中选择节点连接，从式（1）可以看出，原网络中的节点被连接的概率正比于节点的度。

ki为节点i的度，对节点l的所有相邻节点求和。给定足够长演化时间，最终能得到Y=3 的无标度网络，并且度的分布符合幂律分布p(k)≈k-3，网络的平均距离D～lnN/ln lnN，簇系数C～(lnN)2。此时网络呈现出无标度和传输平均距离短的特征，可以用来进行路网模拟。图1展示BA网络中的度分布。

图1 BA网络中的度分布

2 突发事件下路网建模

路网建模如下:每一时间步，网络随机新增R个数据包待传输，新增数据包随机选定节点加入网络并随机选择目的节点。每个节点数据包传输能力定义为Ci，Ci=ki，其中ki为节点i的度，即节点i在单位时间内向其邻居节点最多传输ki个数据包，数据包发送采用FIFO（先进先出）策略。每一时间步，数据包依据排队长度对节点处理能力范围内相邻节点进行搜索，若存在目的节点，则节点直接将数据包转发到目的地节点后将数据包从网络中删除，否则，数据包随机选择邻居节点转发。突发事件定义如下:在原来网络基础上降低网络最大度节点数据包处理能力，根据突发事件程度大小分别降低10%、20%、30%、40%和50%。

临界信息包产生率Rc作为网络传输能力评价指标，定义如下:在保证整个网络数据包总数最终处于稳定状态下，每个时间步向网络中允许加入的最大数据包个数。当每个时间步网络中新产生的数据包数小于等于RC时，给予充足演化，最终，网络中总数据包数会趋向稳定，此时网络以自由流方式运行。当每个时间步网络中新增随机数据包数大于RC时，网络中数据包总数持续增长，随着网络深化，网络将会发生拥堵。可以得出，网络在RC处由自由流状态向拥堵状态转变，也可用式（2）来刻画相变点的位置。

其中ΔNp=Np(t+Δt)-Np(t)，表示网络总数据包数在Δt时间内的变化量。Np(t)代表t时刻网络数据包总量。当序参数η=0，总数据包增长率为0，网络处于自由流状态；当序参数η＞0，总数据包增长率大于0，网络总数据包数持续增加，网络向拥堵演化。

3 网络交通在突发事件下的变化情况

对基于无标度BA网络的带有突发事件下的路网进行仿真，设置如下参数:节点数N=1 000 ，平均度k=6。当网络未发生突发事件，即ε=0%时，从图2可以看出:R≤32 时，给定足够的演化时间，网络数据包总数最终处于稳定状态，网络未发生拥堵。在这个演化过程中，由于网络数据包从起始节点到达目的地节点需要一段时间，在演化初期，网络大部分数据包均未找到终点，所以网络总数据包数增量较大。随着演化深入，数据包逐渐接近或者到达目的节点。由于已到达目的节点的数据包被删除，所以网络总数据包数增速明显变缓，随着网络再进一步演化，每个时间步新加入的数据包和到达目的节点被删除的数据包相等时，网络中总数据包数基本不变，网络稳定处理各数据包。当R＞32 时，网络在演化初期，网络总数据包数急速增加，随着演化时间增加，网络总数据包数增速放缓，但与R≤32 时情况不同，网络最终每个时间步数据包因到达目的节点被删除数持续小于新增数据包数，因此，网络总数据包数随时间持续增加，被删除数据包持续降低，网络最终会产生全面拥堵，如图2。

图2 网络总信息包数随演化时间变化曲线

由上可得，网络在R=32 处发生相变，由自由流状态转变为拥堵状态，所以，在基于BA的无标度网络中使用自由路径传输路由模型的临界信息包产生率为32。

当序参数η在R≤32 取值保持为0，当R＞32 时序参数η取值大于0，得出R=32 为网络由自由流向拥堵状态转变的临界点，网络信息包通讯能力为32，如图3。

图3 η-R 曲线

选择网络中最大度节点处理能力降低作为网络突发事件研究对象。在不同程度突发事件下，依次对网络交通情况进行模拟，得出在网络最大度节点信息包处理能力分别降低10%、20%、30%、40%及50%，即ε=10%、20%、30%、40%、50%时网络相应的临界信息包产生率。从图4可以看出，随着最大度节点数据包处理能力显著降低，网络临界信息包产生率也随之大幅降低；随着最大度节点处理能力降低一半，网络临界信息包产生率也将近降低一半，说明最大度节点数据包处理能力降低严重影响全网传输能力。

图4 临界信息包产生率随突发事件程度变化情况

图5展示网络临界信息包产生率随平均度变化情况，可以得出Rc会随着网络平均度的增加而增加，即平均度增加，保持自由流状态的Rc也会增加。但对于同一平均度的网络，Rc同样会随着突发事件程度的增加而降低，因此为提高整个网络的数据包传输能力，既要尽可能增加节点的度，同时又要降低发生突发事件的可能性。

图5 网络临界信息包产生率随平均度变化情况

评价网络传输效率不仅要考虑每个时间步能够向网络中加入的最大数据包个数，还需考虑整个网络数据包平均传输时间，对此，模拟出网络最大度节点数据包处理能力降低对整个网络数据包平均传输时间的影响变化曲线，结果如图6所示。在R=10，R=15时，随着最大度节点数据包处理能力变低，网络数据包平均传输并未发生明显变化，因为此时网络处于自由流状态，网络中所有节点均不会发生排队情况，最大度节点处的数据包也不会随其节点处理能力降低而在节点处滞留，所以自由流状态下传输时间基本不受最大度节点处理能力降低的影响。在R=35，R=40时，这时网络处于拥堵状态时，网络中必有部分节点发生排队现象，最大度节点也发生数据包排队现象。由于最大度节点数据包处理能力降低，单位时间内向邻居节点传送出去数据包个数随之减少，将会加剧数据包在最大度节点的排队情况。数据包在最大度节点的滞留时间更长，导致整个网络数据传输效率变慢，所以网络拥堵状态时，传输时间会随着突发事件程度的增加而增加，相反传输效率会不断降低。

图6 不同等级突发事件下数据包平均传输时间

4 突发事件下网络交通拥堵疏散策略

当网络发生突发事件，如果网络中数据包维持原来的路由策略将无法主动避开意外情况，对此将原网络随机路由策略进行优化调整。在突发事件下，每个节点在确定下一个传输节点时进行偏好设置。路由策略如下:节点对其邻居节点进行搜索，如果搜索到数据包的目的节点，则直接将该信息转发至目的地节点并从网络中删除；如果没有搜索到目的节点地址，则依据概率P选择节点进行转发，概率定义如下:

其中ki为节点i的度。对节点l所有邻居节点进行求和。由式（3）可知，α值越大，其相邻的度大节点有较大概率被选择，可以充分发挥度大节点的传输优势，但是度大节点数据包处理能力是有上限的，如果都简单的依据选择度大节点进行传输，随着演化深入，度大节点会产生拥堵现象，从而导致传输处理时间延长，全网传输能力下降，因此α取值过大反而降低临界信息包产生率；相反，如果α过小，则度大节点被选择的概率越小，度大节点的传输优势得不到发挥，无法提高临界信息包产生率，因此对于不同程度的突发事件，α对应着一个最优值能使网络临界信息包产生率达到最大。图7展示不同程度突发事件下能使临界信息包产生率达到最大最优的α值。可以看出不同突发事件下随着α的增加，临界信息包产生率都是先增加后减小，呈现上凸状，最优α值分别为0、-0.1、-0.1、-0.1、-0.2，优化后的临界信息包产生率分别为31、27、26、24、22，与原策略相比，分别提高0%、8.00%、13.04%、20.00%、29.41%。

图7 不同程度突发事件下最优α 值

网络中数据包在节点处的分布越均匀，则越不易发生拥堵，图8和图9分别模拟出网络在突发事件ε=30%和ε=50%情况下自由流状态时网络信息包节点分布。从图8和图9中可以看出节点度越大，平均排队数据包越多，并且网络未优化时度小节点平均排队数据包数小于优化后度小的节点，未优化时度大节点平均排队数据包数则小于优化后度大的节点，说明优化后避免网络部分节点出现数据包堆积现象，使得数据包在节点处的分布更加均匀。

图8 不同度节点平均排队信息包情况，ε=30%，R=20

图9 不同度节点平均排队信息包情况，ε=50%，R=15

5 结语

本文基于BA网络，使用降低最大度节点数据包处理能力模拟路网遇到突发事件进行路网建模。通过仿真分析得出不同程度突发事件对网络临界信息包产生率及数据包平均传输时间的影响可以得出，随着网络最大度节点数据包处理能力降低，网络临界信息包产生率随之降低，网络产生拥堵，数据包传输时间也会加长。针对此种情况，将静态局部路由策略应用在网络突发事件模型下，网络在发生突发事件后原随机路由策略更改为带有主动选择偏好性路由策略，经过仿真得出不同程度突发事件下最优偏好性参数时网络临界信息包产生率，经过优化，网络临界信息包产生率分别提高0%、8.00%、13.04%、20.00%、29.41%。