一种无标度网络上的局部路由策略

摘要：提出了一种无标度(scale-free)网络上的局部路由策略。每个节点根据其当前负载与自身发送能力(设为等于节点度)的关系，自适应调整其接收邻居节点信息包的概率。此概率与每个节点度的a次方成正比，a是可自适应变化的偏好因子，由节点度以及负载联合决定。当节点负载小于发送能力时，增大其偏好因子；反之，则减小。这样使得整个网络业务量较小时，可以优先把业务转发往度较大的节点，从而更快到达目的地；而业务量较大时，度大以及度小节点的发送能力均能得到充分利用，从而提高了整个网络的业务承载能力。仿真结果表明，该策略有效地提高了网络容量，并且降低了网络中信息包的平均传输时延。
关键词：无标度网络；自适应；偏好概率；网络容量；路由策略

0 引言
    由于以因特网为代表的大型通信网络，如：生物细胞蛋白质交互作用网、科学家合作网、航空运输网等许多现实中的网络都被证明具有小世界网络特点及无标度(scale-free)的连接特性，复杂网络的构造及其动力学机制的研究问题日益引起人们的关注。对于以交流为目的的网络来说，人们最为关心的是如何实现无拥塞的信息交互，所以在scale-free这种基本连接结构之上的网络中信息流传输问题也逐渐成为研究的热点。
    为实现高效的信息传输，已经有许多研究都致力于提出更好的路由策略。有些文章提出了根据全局拓扑连接信息进行路由选择判断的机制。这对于试验性质的中小型网络或许适用，但对于类似因特网规模的网络或者高动态性的连接结构不断变化的无线网络而言，这种路由策略所需的巨大的计算量以及能量消耗是不可能得到满足的。
    因此人们开始关注局部路由策略。随机游走策略是最原始的局部路由策略，但是由于随机游走的方法过于简单，在网络中实际效果很差。王文旭等人提出一种局部路由策略，发送节点根据邻居节点的连结度和策略指定的度指数计算转发概率，做出路由选择，由于其策略固定偏好因子进行路由选择，所以称之为静态偏好局部路由策略。
    本文的局部路由策略设定了发送方根据邻居节点动态变化的负载与固定的发送能力的关系，自适应地调整各个邻居节点的偏好因子。首先，使网络信息流量适度地向度大的节点集中，增大了对度大节点的利用率，从而有效地减少了网络中信息包的平均传输时延；其次，在业务增大时进行分流，避免部分度大节点的过饱和带来整个网络的拥塞，尽量做到充分利用所有节点的发送能力，提高网络容量。

1 模型及定义
    为了不失一般性选择由Barabdsi与Albert提出的B—A模型作为网络基本构造，模型产生方法与文献相同，其节点的度分布具有幂率特性，即p(k)～k-y，y=3。
    由于在无标度网络中，度大的节点具有较大的介数，是连接各节点对的最短路径集中通过的关键节点，所以应该尽量使用度大的节点进行通信，便于迅速查找目的地(后文称scale-free网络中度较大的节点为hub节点)；而当业务加重时，为了避免在hub节点处造成拥塞，应该适当的分流。因此在信息包产生速率不高且所有节点均未饱和时，应该使得度大的节点具有较大地接收信息包的偏好概率；而在度大的节点饱和后，就根据其负载状况减小其接受概率，把业务流转移至负载轻尚空余有发送能力未被利用的节点。
    业务传输过程定义如下：
    (1)每一时刻开始有R个信息包生成于网络中，即此时信息包产生速率为R，随机地为每个新产生的包选择源节点和目的节点。
    (2)每一个节点均具有无限大的存储空间容纳信息包，信息包队列服从先进先出的原则，节点i的发送能力固定为节点连结度ki。
    (3)网络中所有节点同时为其缓存内将要发送的每个信息包分别进行下一跳目的地的搜索并发送。如果信息包的目的节点是当前节点的邻居节点，则直接把这个包发往其目的节点，并从网络中消除该信息包。否则，就在所有邻居节点中进行偏好选择，把信息包发往邻居节点i的概率是：
   
    式中：ki是节点i的度；ai是节点i的自适应可调选择指数(后称偏好因子)，在初始时刻所有节点的偏好因子都是0。分母是对发送方的所有邻居点求和。
    (4)更新网络中所有节点的偏好因子。自适应变化过程如下：当节点i时刻存储的信息包队列长度小于其发送能力ki时，其偏好因子ai就增大一个步长λ；反之，当节点i时刻存储的队列长度超过其发送能力ki时，其偏好因子ai就减小一个步长λ。同时为偏好因子设定上下限amax(>0)，amin(<O)，ai的增长或减小不可以越过界限，并且选取amax=-amin。。为了使具有不同负载节点的偏好概率之间有明显的区分，偏好因子的变化步长λ可以取作amax的1／20～1／100之间。
    在每一时刻都顺序执行步骤(1)～(4)完成业务传输。
    设定界限amax，amin的原因是考虑到当偏好因子增长的过大时，度大节点的偏好概率会远远大于度较小的节点，信息包会全部尽量涌向度较大的节点，向度小节点转移的概率极低，不利于在整个网络内搜索目的节点，所以要为ai设定上限amax；而偏好因子如果变为较小的负值，就意味着信息会尽量选择度小的末梢点作为传输对象，完全避开hub节点将导致信息包传输时延大大增加，所以也要为ai设定下限amin。

2 路由方法分析
    考察scale-free网络路由策略性能的最主要指标是网络容量，通常用网络不拥塞时可以达到的最大信息包产生速率Rc(又称临界速率)来衡量。
    在任一信息包产生速率下，如果只是每次进入部分节点的信息包队列长度超过了节点发送能力，使信息包堆积，导致了拥塞的发生(后文称之为节点过饱和)，那么只需把这部分业务转移到尚未饱和的节点中去，就可以缓解这种局部负载过重带来的拥塞，并且可以进一步扩大产生速率。只有当全部节点均达到了饱和，整个网络拥塞的发生才是无可避免的。所以目的就是避免局部节点拥堵带来网络拥塞，尽量提高网络容量，最后全部节点可以同步地达到饱和状态。
    设定节点发送能力等于其连接度，首先使度大节点有较大的偏好概率，以大业务流进入速率把负载优先分配给度大的节点进行存储转发，搜索目的地；当度大节点的负载等于甚至超过发送能力(后文称之为饱和)后，自适应地调整其信息进入速率，把业务向尚未饱和的度较小的节点转移，避免度大的节点过早进入拥塞状态。
    注意到在本策略定义的自适应传输机制下，l(ki)的长度从0开始逐渐增长，当l(ki)≤ki时，每次发送完成后不会有信息包在节点内滞留，所以节点处于未饱和平稳状态；反之，若l(ki)>ki，信息包会不断在节点堆积，节点就处在过饱和拥塞状态。所以称l(k)=k为节点未饱和与过饱和的相分界线。
    在自适应策略下，选取任何非负的偏好因子上限amax都能得到相同的最大网络容量Rc_max。这是因为自适应策略根据节点的负载与发送能力的关系不断变化偏好因子ai，进而调整信息流的进入速率，不断向未饱和的节点分流信息包，从而使信息包不会在饱和节点处不断积累增加，避免节点达到过饱和造成全局拥塞。未饱和节点，由于队列长度一直满足l(ki)≤ki，其偏好因子ai均会随时间不断增长，直至等于其上限amax，不会减小；达到相分界线的饱和节点，其偏好因子不再保持等于上限amax，而是随负载的变化波动。在自适应调整偏好因子的反馈作用下，饱和节点的信息包进入速率将基本等于发送能力，即平均队列长度稳定在相分界线l(ki)=ki上，由于相分界线斜率为1，参考式(1)，得出饱和节点的偏好因子接近于0。同时考虑到，当所有节点都达到饱和，偏好因子ai均接近于0时，网络达到最大容量。因此在任何偏好因子的界限amax下，网络均有惟一相同的最大容量Rc_max。
    图1反映的是不同发送速率下，节点平均队列长度的变化情况。图中粗直线代表的就是相分界线。节点均未饱和时，反映在图中就是l(ki)未接触相分界线，此时l(ki)服从式(1)。随着R增加，部分节点接触相分界线后开始进入饱和状态，l(ki)也开始分为两段。度较大的一部分饱和节点的平均队列长度与相分界线完全重合，平均队列长度变为l(ki)=ki；另一部分节点未达到饱和状态，平均队列长度保持原来的斜率，即。

    随着R的增加，l(ki)与相分界线重合部分增加。当所有节点均达到饱和，即l(ki)与相分界线完全重合时，所有节点的偏好因子的均值均达到0，网络达到最大容量，此时的R就是最大临界发送速率Rc。

3 仿真结果
    首先观察采用自适应策略后网络容量的变化情况。为了精确地找出临界发送速率，利用了以下序参量：
   
    式中：△Np=N(t+△t)-N(t)是一段时间△t内网络总包数的变化；＜＞意味着选取足够多的时间段计算得出的平均值；η(R)可以视为网络内总包数的变化率。
    图2反映静态局部路由策略和本文提出的自适应局部路由策略不同R对应的η变化。ai=0，0．4，0．8代表在静态偏好局部路由策略下，网络中所有节点的优化因子的选择情况。amax=0．4，amin=-0．4；amax=0．8，amin=-0．8；amax=1，amin=-1代表在自适应局部路由策略下优化因子上下限选择情况。从η的数值变化可以看到，在静态偏好局部路由策略下，只有在选取ai=0时，具有最大的临界发送速率，固定优化因子ai为其他值时所得到的Rc均无法达到这一最大值。按照本文提出的自适应局部路由策略，在为ai选取不同的amax，amin的时候，均超过静态策略的Rc可以获得相同的最大Rc_max。

    反映网络路由策略效能的另一个重要指标就是信息包的平均传输时延。图3反映的是采用自适应路由策略、静态偏好路由策略，以及王文旭等提出的结合动态和静态信息的路由策略得到的不同平均传输时延。
    图3中，β=-3代表结合动态和静态信息的局部路由策略，及其关键参数的选取情况，具体可参见文献。ai=0代表在静态偏好局部路由策略，amax=0.4，amin=-0．4，amax=1，amin=-1，amax=1．5，amin=-1．5，分别代表在本文提出的局部路由策略下网络中所有节点的优化因子的上下限。可以看到，结合动态和静态信息的局部路由策略在R较小时可以保持较低的传输时延，但是随着发送速率的增加，平均传输时延也迅速增大。静态路由策略(ai=0时)的传输时延在接近临界发送速率前随发送速率逐渐增大。

    从图3可以看到，本文提出的自适应局部路由策略的平均传输时延受到不同的amax的影响。在接近临界状态时采用本文策略的平均传输时延明显小于原有策略。

4 结语
    本文提出了一种自适应的无标度网络上的局部路由策略。每个节点的转发概率由节点度k及偏好因子a共同决定。偏好因子a值根据每个节点自身的缓存平均队列长度自适应变化，当节点缓存平均队列长度大于发送能力(等于节点度k)时，a增加；反之，则减小。a的上下限amax，amin可调，并且互为相反数。当网络中所有节点均未饱和时，不同度节点的偏好因子基本都达到上限amax；当部分节点达到饱和时，这些节点的偏好因子显示出a=0的统计特性，其余节点的偏好因子仍基本保持为amax。这使得一方面无论网络业务轻重时，都可以保证网络信息流量优先地向hub节点集中，连接度大的节点得到充分的利用；另一方面能够使节点发送能力得到恰当的使用而不会达到“过饱和”状态，自适应地避免拥塞的发生。仿真结果表明，为偏好因子选择不同的上下限时，本策略都能使所有节点同步饱和，以达到网络的最大临界发送速率；基于对hub节点的适度优先利用，本文提出的自适应局部路由策略，可以获得比静态偏好局部路由策略、结合动态和静态信息的局部路由策略更小的平均信息包传输时延。