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

摘要：提出了一种无标度(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。