首页 > 文章中心 > 正文

通信网络病毒传播探究

通信网络病毒传播探究

1SIS-CA模型

文献[12]使用元胞自动机建立的病毒传播随机模型如下:CA=(C,Q,V,f)(1)此模型建立在病毒传播机制具有随机特性的基础上,即感染节点以相同的概率感染它的所有邻居节点,其中C表示元胞空间,Q表示有限状态集,V表示节点的邻域,f代表状态转换规则函数。该模型中节点状态只有两种:健康状态(susceptible)和感染状态(infected)之一。节点状态变换关系:suscep-tible→infected→susceptible。网络G=(N;E),N表示网络中节点的个数,E表示网络中节点与节点的边,令A表示网络的邻接矩阵,它反映网络的拓扑信息。根据元胞自动机4要素,建立模型:元胞空间C:建立包含N个元胞的一维元胞空间,一维元胞空间中的一个元胞即代表网络中的一个节点;邻域V:该模型中以网络的邻接矩阵A定义各元胞邻居关系,所以节点i的邻域Vi就被定义为A中的第i行的向量,即Vi={aij|aij∈A,j=1,2,…,N};若aij=1,表示节点i和j之间存在连接。

2本文所提SIS-CA模型

2.1传播策略

在上述的SIS-CA模型中,感染节点在单位时步以相同的概率感染它的所有邻居,而实际情况并非如此,例如在Internet网络中,两个主机之间虽然有通信连接但是没有数据包的传输,那么也就不会有病毒的传播;在人际网络中,互为朋友(邻居)的两个人,在一方患病期间并没有和他的这个朋友(邻居)有任何联系,那么他的这个朋友也不会被感染。考虑到网络中通信流量的不均衡特性以及数据包传输路径的选取与具体的路由转发协议有关的特点,我们对上述SIS-CA模型进行改进。为了便于问题的分析,假设网络中每个节点生成数据包的平均速率为α,则在每一个时步,网络中生成新数据包的总量即网络通信流量[13]为Nα。在每个时步,网络中任何一个节点生成的数据包都随机选择目的节点进行发送,数据包传输路径的选取则采用最短路径优先(ShortestPathFirst,SPF)算法[14]实现,基于此定义网络中节点算法介数[15](algorithmicbetween-ness)balg为穿过一个节点的所有最短数据包传输路径的总和。那么,网络中任一健康节点i在单位时步被感染的概率取决于单位时步穿过这个节点的带病毒的数据包的个数Ni。显然Ni的值与网络通信流量Nα和节点算法介数balg有关:网络通信通量越大,带病毒的数据包数目发送量越多,Ni的值就会越大;节点算法介数balg越大,穿过这个节点的数据包越多,Ni的值就会越大。在这里,一个健康节点收到或者转发的带病毒的数据包的个数Ni来自以下几个方面:(1)感染邻居节点产生的数据包数,这样的数据包一定带有病毒;(2)感染邻居节点转发的带有病毒的数据包,这样的数据包一定带有病毒;(3)感染邻居节点转发的不带病毒的数据包,这样的数据包以一定的概率β变为带病毒的数据包,可见感染邻居节点发送的数据包也是有可能不携带病毒的;(4)健康邻居节点转发的带有病毒的数据包,这样的数据包一定带有病毒,可见健康节点发送的数据包也可能是带有病毒的。以上第(3)、(4)两个方面显然与以往的没有考虑网络通信流量的SIS-CA病毒传播模型不同。当然,健康邻居产生的数据包和健康邻居转发的健康数据包都是不携带病毒的。我们假设一个健康节点接受或者转发一个带病毒的数据包,这个健康节点被感染的概率和一个健康数据包经过一个感染节点,这个数据包被感染的概率都为β。那么一个健康节点i在单位时步被感染的概率为1-(1-β)N。可见,任何节点仅能被它的邻居发送的带病毒的数据包感染,健康节点在单位时步被感染的概率不仅与其邻居在上一时刻自身的状态有关(健康邻居产生并发送健康数据包,感染邻居产生并发送带病毒的数据包),还与邻居转发的数据包的状态有关(健康邻居也可能转发带病毒的数据包,感染邻居也可能转发不带病毒的数据包)。

2.2算法描述

本文所提模型的关键之处在于求任一时步内,穿过网络中任一节点i的带病毒的数据包的个数。假设单位时步网络中有N个数据包传输,我们使用最短路径优先算法求出所有数据包传输的路径,并把它们存放在数组R(N,N)中,数组R(N,N)的每一行表示每个数据包从源节点经过一系列中间节点到达目的节点的所有结点的节点编号,目的节点后的元素值取0。我们使用数组C(1,N)表示网络中N个节点在单位时步接收的带病毒的数据包数目,C(1,i)表示节点i单位时步内接收到的带病毒数据包数。

3仿真结果与讨论

本节分别以NC网络、WS网络和BA网络为例,通过数值仿真研究本文提出新的SIS-CA模型在最近邻耦合网络、小世界网络和无标度网络上的传播特性。仿真过程中选取参数如下:网络的节点数为N=200,病毒在网络中传播的初始时刻为0,随机选择一个节点作为感染节点;在NC网络中每个节点的邻居节点个数为6;在WS网络中随机化重连概率p的取值为0.2,网络的平均度<k>=6;在BA网络中m和m0的取值分别为m0=8,m=3,这里的m0为网络的初始节点数,m为与网络中任意一个节点相连的最少节点数。假设初始时刻网络中感染病毒的节点数为1,I(t)表示t时刻网络中受感染节点数目,即I(0)=1,其它参数取值如下:β=0.3,μ=0.5,α分别取1、2、3、4。仿真过程中转发数据包的路由选择协议采用开放最短路径优先协议,即OSPF协议。分别在NC网络、WS网络和BA网络中,针对不同的α值分别执行100次仿真试验,i(t)表示t时刻网络中受感染节点比率,对仿真所得数据进行统计平均,得到病毒的传播演化曲线。网络通信流量对病毒传播行为的影响是显著的:随着网络通信流量增大,病毒在不同拓扑结构网络中传播速度都明显加快,病毒在更短的时间内达到稳定的更高的感染规模。当网络通信流量很少的时候,例如在单位时步里每个节点只产生一个数据包时,即图中α=1时,在WS网络和BA网络中,病毒传播最早期就趋于消亡的可能性是很大的,仿真结果显示100次仿真结果中WS网络出现了46次消亡、BA网络出现了60次消亡。这告诉我们,在异质网络中,减少网络的通信流量可以有效地降低病毒爆发的可能性。随着网络中通信流量的增加,即在单位时步里网络中产生并发送的数据包数量的增加,病毒爆发的可能性明显增大,但是当网络通信流量达到一定的值后,再增加网络通信流量,对病毒感染规模的影响却不再明显,这一点NC最近邻耦合网络表现得最为明显。可见病毒最终感染规模并不是随网络通信流量的增加而线性增加的。仿真结果中还有一点必须指出:在最近邻耦合网络中,无论网络通信流量为多少,始终没有观察到病毒消亡的现象,这说明病毒在最近邻耦合网络中最易传播。为了说明本文所提新SIS-CA模型中网络拓扑结构对病毒传播行为的影响,下面我们研究不同网络通信流量下不同网络拓扑的病毒爆发率。仿真中网络通信流量分别取N、2N、3N、4N,对NC网络、WS网络和BA网络进行仿真。在本文所提新的SIS-CA模型中,在给定网络通信流量和路由选择算法下,病毒在节点度异质化程度较高的BA无标度网络中最不易传播,而在节点度分布均匀的同质网络最近邻耦合网络中最易爆发,这恰好与以往的研究结果相反:病毒更加容易在度分布异质化程度更高的网络中传播。这是因为本文考虑网络中数据包的传输遵循一定的路由选择协议,而不是单位时步里每个节点都向它的所有邻居发送发送相同数目的数据包,由于源节点随机选择目的节点进行发送,在最近邻耦合网络中,随机选择的目的节点离发送节点越远,数据包达到目的节点所要经过的中间节点就会越多,那么带有病毒的数据包经过的中间节点的数目也会越多,那么在单位时步内,节点接受或者转发的带病毒的数据包就会增多,这样就更有利于病毒的传播;而在无标度网络中,由于节点分布的异质化程度较高,节点很有可能与它较远的节点直接相连,这样就会大大减少数据包传输所经历的中间节点数目,从而使病毒不易爆发。

4结束语

在许多复杂网络病毒传播过程中,病毒的传播特性会受到网络通信流量的影响。为此本文提出了一种新的SIS-CA传播模型,研究了该模型在最近邻耦合网络、小世界和无标度网络上的传播行为。经研究发现:随着网络通信流量的增大,病毒在不同拓扑结构网络中的传播速度都明显加快,病毒可以在更短的时间内达到稳定的更高的感染规模。研究还发现,在考虑一定通信流量和路由协议的情况下,网络拓扑结构是影响病毒传播行为的关键要素,病毒在节点度分布异质化程度较高的网络中最不易爆发,这恰好与以往的研究结果相反。原因在于本文所提模型中健康节点能否被其邻居节点感染是由其邻居是否发送了带病毒的数据包决定,而不是由其邻居自身的状态决定。