基于最短路径长度的空间网络路由*

林泓 夏永祥† 蒋路茸

1) (杭州电子科技大学通信工程学院,杭州 310018)

2) (浙江理工大学信息学院,杭州 310018)

1 引言

20 世纪50 年代末,Erdös 与Rényi[1]提出的ER 随机图模型开辟了复杂网络领域研究的先河.直至20 世纪末,小世界网络[2]的提出与无标度特性[3]的发现,吸引了一大批科学家参与到复杂网络结构与动力学的研究之中.近十年来,复杂网络成为生物技术、移动通信、交通运输、社会关系等多个不同领域的研究热点[4-8],受到物理、数学、计算机、通信、社会学等领域学者的广泛关注.实际生活中的Internet、移动通信网络、交通运输网络、电力网等都可以被抽象成复杂网络进行研究分析,而这类网络的传输性能与人们的生活息息相关.如何提升网络的传输性能已经成为复杂网络领域研究的热门课题之一.网络传输能力主要取决于网络的拓扑结构与路由方式,针对这两方面的影响因素,一般有“硬策略”和“软策略”两种优化方式[9],即优化网络拓扑结构与优化路由方式.而在实际生活中,不少网络的结构已经固定,修改其结构需要承担高昂的成本.因此,采用更加高效的路由策略来提升网络传输性能更具有可行性.

传统意义上的最短路径的策略是目前应用较为广泛的一种路由方式,即负载从节点A通过最少的边数传输到节点B,但是这种方式很容易在一些度值较大的节点处造成拥塞现象[10].因此,不少研究人员提出了更加高效的路由策略[10-20].Yan等[18]提出了一种“the efficient path”的路由策略,定义任意两点i和j之间的路径为L(P(i →j):β)=以 m in(L) 为目标选择路径,通过绕 开度值较大的节点来减少发生拥塞的可能,大大提升网络的传输性能.Huang 和Chow[19]提出了一种带记忆信息的路由策略,节点记录负载的传输来源,避免出现回溯现象,使得负载在两个不同节点之间来回传输的机会大大减少,有效地提高网络吞吐量.Wang 等[20]提出了一种流量模型,负载从节点a传输到节点b,若节点a与b之间有边连接,则负载可直接传输至目标节点b;否则,将以Πi=的概率传输至a的某个邻居节点i.

之前提出的各种路由策略主要是基于复杂网络的拓扑,很少有研究考虑节点的空间位置.而事实上,由于空间网络中的节点与节点之间的连接受到实际位置的约束,与一般的复杂网络在拓扑结构和鲁棒性[21]等方面具有一定的差异性.在实际生活中,如航空网络[22]、交通网络[23]、无线传感器网络[24]、无人机网络[25]等都受到空间位置的限制.由于这类空间网络的特殊性,对其路由策略的研究具有很强的理论价值和现实意义.

本文提出一种基于最短路径长度的空间路由方式,即负载从源节点沿着最短路径长度的方向传输到目标节点.Zhao 等[26]在2005 年发表的文章中指出,不同结构的网络出现拥塞现象的性能不相同.因此,本文考虑了空间匀质网络和异质网络两种情况,在随机几何图[27]和LAEE (local-area and energy-efficient evolution)模型[28]上进行了仿真模拟.仿真结果表明,本文提出的路由策略能够有效提升网络的传输性能,减少拥塞现象的发生.

2 空间网络模型

2.1 LAEE 演化模型

研究发现,很多实际网络都遵循节点的度值呈幂律分布的无标度特性,即P(k)∝k-γ,其中k表示节点的度,γ为常数.为了探究本文提出的路由算法在异质网络上的适用性,采用Jiang 等[28]提出的具有无标度特性的空间LAEE 演化模型.

该网络的拓扑演化主要分为两个阶段.在第1 阶段,将N个节点随机分布在1 × 1 的区域S内,每个节点传输和处理负载的能力都是相同的.此时所有节点都是孤立的,假设以节点i为圆心、r为半径的连通区域内所有节点为节点i的潜在邻居,并定义最靠近原点O的节点为汇聚节点.

在第2 阶段,从汇聚节点开始进行网络的拓扑演化.

步骤1令汇聚节点与其通信半径r内的a0个潜在邻居节点进行连接,形成初始网络T0.

步骤 2在时间步i,定义网络Ti中具有最多孤立的潜在邻居的节点为v,在其潜在邻居中挑选一个节点ni加入到网络Ti中.

步骤 3如图1 所示,基于优先连接的原则下,以Πi的连接概率选取网络Ti中a个节点与节点ni进行连接,并满足a个节点均在节点ni的连通范围内;若可选取的节点数小于a,则全部连接.连接概率Πi可通过下式求得:

其中,局部区域指以节点ni为圆心;r为半径的连通范围;kmax是默认节点最大的度值;q是已经达到kmax的节点的个数;f(Ei) 是功能函数,为了方便处理,这里取f(Ei)=1 .

步骤 4重复步骤2 和步骤 3,直至区域S内的所有节点都被加入到网络中.

从上述过程可以看出,在此模型中,虽然N个节点的位置开始就已经确定了,但它们是一个一个加入到网络中的,且它们的连边是基于优先连接的原则建立的,因此有少部分节点拥有大量的连接,而大多数节点的度则比较小.LAEE 网络的度分布如图2 所示.可以发现其度分布呈现幂律分布的特点,是典型的异质网络.

图2 N=1500,〈 k〉 =8 时的LAEE 网络的度分布Fig.2.Degree distribution of the LAEE network.N =1500,〈k〉=8.

2.2 随机几何图模型

最简单的空间网络是随机几何图模型[24].该模型主要分为以下3 个阶段:

步骤1将N个节点随机地分布在1 × 1 的区域S内.

步骤2 随机选取一个节点i,以它为圆心,r为连通半径,构成一个圆形的连通区域.如图3所示,节点i与其连通区域内的全部节点建立连接.

图3 节点i 与其连通区域内的全部节点建立连接Fig.3.Node i connects all nodes in its connection area.

步骤3 重复步骤2,直至所有节点都与其连通半径内的所有节点建立连接.

2.3 改进的随机几何图模型

在节点数N与平均度〈k〉相同的情况下,随机几何图模型的连通半径要小于LAEE 演化模型.为了更公平地比较匀质与异质网络,我们希望两个网络模型中的连通半径r相同.对此,本文在经典的随机几何图模型基础上,提出一种改进的随机几何图模型.

网络的生成如下所示:

步骤1将N个节点随机的分布在 1×1 的区域S内.

步骤2随机选取一个节点i,以节点i为圆心,r为连通半径,构成一个圆形的连通区域.如图4 所示,定义连接概率p,节点i与其连通区域内的节点以p概率建立连接.

图4 节点i 与其连通范围内的节点以p 概率进行连接Fig.4.Node i connects nodes within its connection range with probability p.

步骤3重复步骤2,直至所有节点都被遍历到.

从上述过程可以看出,在改进的随机几何图模型中,每个节点的连接概率相同,不同节点之间不存在明显的差异.该模型的度分布情况如图5 所示.与LAEE 网络相比,改进的随机几何图更接近匀质网络.

图5 N=1500,〈 k〉 =8 时改进的随机几何图的度分布Fig.5.Degree distribution of the improved random geometric graph.N=1500,〈 k〉=8.

3 路由策略

假设每个节点都具有相同的传输负载的能力.负载在网络上的传输过程描述如下:在每一个时间步,网络产生R个单位的负载,它们的源节点与目标节点均随机确定,根据路由策略由源节点向目的节点传输.每个节点在每个时间步中所能处理的最大负载量为C个单位的负载,为了便于问题的分析,假设C=1 .在每个时间步,负载只能向前传输一步,即从一个节点抵达至其邻居节点.当负载到达目标节点时,自动从网络中删除.用参数H(R)表示网络的序参量[18]:

其中,ΔW=W(t+Δt)-W(t),Δt表示一个时间步的长度,W(t) 表示t时刻网络中负载的总量.当R较小时,所有的负载都能被及时处理,因此H(R)=0,这种状态称为自由流状态.如果R逐渐增大,使得在某个节点处每个时间步需要处理的负载量超过C,那么必然会有一部分负载无法被及时处理,此时H(R)＞0,即网络出现拥塞现象.我们关心网络从自由流状态到拥塞状态的相变点处的R值,称为Rc,它表示网络在不出现拥塞现象时最多能处理的负载量,即网络的最大吞吐量.Rc的值一方面取决于网络的拓扑结构,不同拓扑结构的网络具有不同的Rc;另一方面,Rc的值取决于所采用的路由方式.因此,本文将在具有不同拓扑结构的空间网络模型下进行仿真,并对比本文提出的路由方式与传统的最少跳数路由方式.

3.1 传统的最少跳数路由策略

在考虑负载传输时,经常采用所谓的最短路径路由.在一般的复杂网络中,两点之间的最短路径通常指它们之间经过最少连边的路径,即最少跳数路由.但是,在空间网络中,所谓最短路径可能有多种含义,例如跳数最少或者长度最短.为了不引起混淆,本文将通常意义下的最短路径路由称为“最少跳数路由”.

在采用最少跳数路由的情况下,可以用介数来描述各个节点的负载情况,任意一个节点v的介数表示如下[18]:

其中σst表示节点s到节点t的最少跳数路径的数量,σst(v) 表示节点s到节点t的最少跳数路径中经过节点v的数量.当R＜Rc时,网络处于自由流状态,不会出现拥塞现象,单位时间到达节点v的负载为Rg(v)/[N(N -1)] ;当R＞Rc时,网络出现拥塞现象,假设在节点v处出现拥塞,此时Rg(v)/[N(N -1)]＞C.研究表明,拥塞最先发生在介数值最大的节点处.因此,Rc可表示为[18]

3.2 最短路径长度路由策略

在空间网络中,由于每个节点都有一个空间位置,因此每条连边都有长度.简单起见,考虑二维平面上的网络,那么对于连接节点i和j的连边,其长度为

其中 (xi,yi) 与 (xj,yj) 分别为节点i和j的二维坐标.这样,对于任意节点对 (s,t),可以定义它们之间的一条路径的长度为这条路径所经过的所有连边长度之和.即路径

的长度为

在这些路径中,长度最小的路径被称为最短长度路径,而其长度被称为最短路径长度,采用最短长度路径的路由策略称为最短路径长度路由.可以看到,这种路由策略只可能出现在空间网络中,因为连边长度乃至路径长度的概念是建立在节点的空间坐标基础上的.

需要说明的是,采用最短路径长度路由策略时,节点的介数仍可以采用类似(3)式的方法计算,但是式中的变量含义有所变化.具体地,σst表示节点s到节点t的具有最短长度的路径的数量,σst(v)表示节点s到节点t的具有最短长度的路径中经过节点v的数量.

4 路由性能仿真及分析

为了检验两种路由策略的性能,采用前文提到的LAEE 演化模型和改进的随机几何图模型两种空间网络进行仿真实验.其中,LAEE 演化模型产生具有无标度特性的空间网络,是典型的异质网络;而改进的随机几何图模型继承了经典随机几何图模型的特点,是典型的匀质网络.

先将N个节点随机地分布在1 × 1 的区域S内,由于空间位置的限制,节点i只能与以节点i为圆心,r为半径的区域内的潜在邻居节点进行连接.根据(5)式,可以计算出任意两点之间的距离,找到节点i的所有潜在邻居节点,再根据LAEE与改进的随机几何图模型的生成规则,将节点i与其部分潜在邻居节点连接,分别生成具有异质与匀质特性的空间网络.

对于网络的任意节点对,其路径可由(6)式来表示.在空间网络的背景下,连边被赋予了长度的属性,通过(7)式可以得到任意节点对之间的路径的长度,本文提出的最短路径长度的路由正是基于(5)式—(7)式去寻找任意节点对 (s,t) 之间的最短长度的路径,即 m inL(s →t) .传统的最少跳数路由和最短路径长度路由从不同角度刻画了节点之间的“最短路径”.接下来将通过仿真分析来比较两种路由的性能,进而确定那种路由效果更好.

首先对两种路由策略下的拓扑指标进行分析.不同路由策略下平均路径长度、平均跳数与节点数N的关系如图6 和图7 所示.可以看到,正如它们的名称所示,最少跳数路由具有更小的平均跳数,而最短路径长度路由具有更小的平均路径长度.比较两种网络可以发现,结构上异质的LAEE网络具有更短的平均路径长度和更小的平均跳数.这是因为LAEE 网络中具有少量大度节点,它们提供了传输的捷径.但是,在同一种网络中,随着节点数的增加,平均路径长度略有减少,而平均跳数却有所增加.这是因为在保证平均度不变的前提下,随着节点数的增加,连通半径r是不断减小的.这样,平均来讲,从源节点到目的节点所经过的连边数会增加.

图6 平均度 〈 k〉=4 时,不同节点规模下两种路由方式平均路径长度的比较 (a) LAEE 演化模型;(b)改进的随机几何图模型.图中每个点是10 次仿真的平均值Fig.6.With the average degree 〈 k〉=4,the average path length under two routing strategies with different node sizes:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

网络最大吞吐量Rc与节点数N的关系如图8所示.可以看出,无论在哪种网络中,最短路径长度路由都具有更大的Rc值,这说明采用最短路径长度路由会有效提高空间网络的吞吐量.当然,如图7 所示,最短路径长度路由增加了平均跳数,这将导致平均传输延时变长.也就是说,最短路径长度路由提高空间网络吞吐量是以增加传输延时为代价的.而比较两种网络发现,结构上异质的LAEE 网络具有更小的Rc值,这是因为异质网络中的大度节点在提供传输捷径的同时,不可避免地成为传输的瓶颈,制约了网络的吞吐量.此外,网络吞吐量随着网络规模增加而增大.

图7 平均度 〈 k〉=4 时,不同节点规模下两种路由方式平均跳数的比较 (a) LAEE 演化模型;(b)改进的随机几何图模型.图中每个点是10 次仿真的平均值Fig.7.With the average degree 〈 k〉=4,the average number of hops under two routing strategies with different node sizes:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

图8 平均度 〈 k〉=4 时,不同节点规模下两种路由方式的网络最大吞吐量 Rc 的比较 (a) LAEE 演化模型;(b)改进的随机几何图模型.图中每个点是10 次仿真的平均值Fig.8.With the average degree 〈 k〉=4 ,Rc under two routing strategies with different node sizes:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

不同路由策略下平均路径长度、平均跳数与平均度〈k〉的关系如图9 和图10 所示.与改变网络规模类似,这里也可以看到,无论平均度如何变化,最少跳数路由总是具有更小的平均跳数,而最短路径长度路由总是具有更小的平均路径长度.另一方面,随着〈k〉的增加,网络中的连边数逐渐增加,各节点间路径有了更多的选择,因此传输的路径长度变短,平均跳数减小.

图9 节点数 N =1000 时,不同平均度下两种路由方式平均路径长度的比较 (a) LAEE 演化模型;(b)改进的随机几何图模型.图中每个点是10 次仿真的平均值Fig.9.With N=1000,the average path length under two routing strategies with different average degrees:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

图10 节点数 N =1000 时,不同平均度下两种路由方式平均跳数的比较 (a) LAEE 演化模型;(b)改进的随机几何图模型.图中每个点是10 次仿真的平均值Fig.10.With N=1000,the average number of hops under two routing strategies with different average degrees:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

图11 给出了网络最大吞吐量Rc随平均度〈k〉的变化情况.总体来看,最短路径长度路由总是具有更大的Rc值.而随着平均度的不断增大,网络连接越来越稠密,负载传输的路径越来越均匀地分布在网络中,结果是导致Rc值的迅速增加,即网络吞吐量迅速变大.

图11 节点数 N =1000 时,不同平均度下两种路由方式的网络最大吞吐量 Rc 的比较 (a) LAEE 演化模型;(b)改进的随机几何图模型.图中每个点是10 次仿真的平均值Fig.11.With N =1000 ,R c under two routing strategies with different average degrees:(a) LAEE evolution model;(b) improved random geometric graph model.Each point is the average of 10 runs.

图12 和图13 分别给出了两种网络在采用两种路由策略时的介数分布.可以看出,无论哪种网络,采用最短路径长度路由时的最大介数值都比采用最少跳数路由时的最大介数小.正是这个更小的最大介数,导致最短路径长度路由具有更大的Rc.那么,为什么最短路径长度路由会导致更小的最大介数呢? 这是因为采用最短路径长度路由时,为了保证路径长度尽可能短,所遵循的路径更接近于直线,所以所谓网络关键节点的作用并不突出.相比之下,最少跳数路由追求更少的跳数,网络中少量关键节点往往起到中介的作用,汇聚了大量的路径,导致最大介数更大.综上所述,最短路径长度路由能使网络传输的负载得到更加合理的分布,从而使网络具有更大的吞吐量,是一种更加有效的路由策略.

图12 LAEE 演化模型中,节点数N=1000,〈 k〉=4 时的介数分布 (a)最少跳数路由;(b)最短路径长度路由Fig.12.Betweenness distribution of the LAEE network with N=1000,〈 k〉 =4:(a) Least number of hops routing strategy;(b) shortest path length routing strategy.

图13 改进的随机几何图模型中,节点数N=1000,〈 k〉 =4 时的介数分布 (a)最少跳数路由;(b)最短路径长度路由Fig.13.Betweenness distribution of the improved random geometric graph with N=1000,〈 k〉 =4:(a) Least number of hops routing strategy;(b) shortest path length routing strategy.

5 结论

在空间网络中,“最短路径”可以有不同的解读,传统的最短路径等效于跳数最少的路径.而空间网络中由于连边具有长度属性,最短路径也可以理解为从源节点到目的节点所经过的所有连边的长度之和(即路径长度)最短.本文提出的最短路径长度路由策略就是基于后者.通过在匀质和异质空间网络上的仿真发现,这种新路由策略能够有效提升网络最大吞吐量.本文提出的路由策略对现实生活中交通运输、无线通信网络等都具有很好的借鉴意义.