





























离与度融合的策略。
节点传递信息给具有,最小度量值的邻居,依此下去,直到信息传递到目标节点。
通常,度量函数,是节点到目标节点的最短距离与节点的度的函数。
采用该方法的效率可以达到很高,接近于全局信息的路由策略。
文献提出种相似性与度混合的路由规则。
节点传递信息给具有最优化值,的邻居节点,依次下去,直到信息传递到目标节点。
其中相似性和度混合度量函数,定义为节点和节点之间的相似性度量参数如节点连接到节点的概率与节点的度的函数。
若网络没有相似性,则选择最大度路由策略若所有节点的度均相等,则选择与目标节点相似的节点。
但在实际网络中,这两种情况很少见。
基于生物行为的复杂网络路由方法生物学中的很多行为与现代通信网络中分组传播行为有很多相似的地方,且生物学中的很多结构也符合复杂网络的特征。
通过对生物学行为的揭示,将生物学原理应用到计算机网络中,以控制分组的传播行为,成为研究人员关注的热点之。
基于生物行为的理论,研究人员提出了很多复杂网络中的路由机制和思想,包括基于病毒传播机制的网络路由基于免疫学方法的路由机制以及基于蚁群的路由方法等。
基于病毒传播机制的路由方法在流行病学模型中,种群内的个体被抽象定义为有限的几个典型状态。
流行病学模型基本的状态包括个状态,易染状态,被感染状态,免疫状态或恢复状态。
通常用这些状态之间的转换过程来命名模型。
例如,易染群体被感染,然后恢复健康并具有免疫能力,称之为模型若易染群体被感染后,又返回到易染状态,则称之为模型。
此外,可以用概率来描述这类模型各状态之间的转换。
例如可假设从易染状态到被感染状态的概率为,从被感染状态到易染状态的概率为等。
研究表明图越稀疏,病毒传播速率越慢,病毒传播扩散的概率就越小,这也意味着稀疏性可以有助于抑制全局病毒的传播不包括局部传播。
在病毒网络中,通常存在传播临界值。
若有效传播率大于临界值,则感染个体能够将病毒传播扩散,最后网络感染个体总数达到平衡状态若有效传播率小于临界值,则病毒无法大范围传播。
通常,在无标度网络中,节点的度越高,被感染的几率就越高。
基于流行病毒的传播方式,文献提出种流行病的路由方法。
该路由方法并没有确定的源节点和目的节点,通过节点间以随机交换的方式复制信息,直到节点有每个信息的拷贝。
其中些节点具有免疫能力,即收到消息后不再复制转发。
该路由方法可以提高消息的传播速度以及缩短消息的传播时间。
文献提出了种加权的流行病路由算法,对流行病路由算法进行了改进,考虑了节点存储能力和带宽的限制。
通过给每个消息分配权重来决定消息的转发或删除。
消息的权重由受感染节点数存活时间和受感染节点周围的信息副本数量来确定。
在节点缓冲区内,信息传递与排序的顺序由权重来决定。
权重高的消息具有被优先发送的权利,当缓冲区溢出时,权重低的消息将被丢弃。
基于免疫学的路由方法免疫学的思想主要用于有效地控制疾病的传播。
与现代通信网络相似,网络路由的本质就是要控制分组的传播。
等人设计并分析了种叫做熟识者免疫的策略,即每次选择都分两步,先随机选择个个体,再随机选择该个体的个相邻个体进行免疫。
这种策略可以避免计算每个节点的度,且由于在无标度网络中度大的节点比度小的节点被选中的概率大很多,因此该策略效果比随机免疫好。
与的策略类似的方法如接触免疫和环状免疫已经在应用中取得了较好效果。
目前主要有分为两种免疫路由方法随机免疫和目标免疫。
随机免疫在随机免疫中,进行免疫时随机地选择节点,与节点的度以及其他特性无关。
随机免疫可以根据传播速率与节点度的特性,计算出免疫的临界值,以保证可以最终阻止扩散。
无论消息以何种速率传播,随机免疫法虽然能够局部抑制传播,但速度非常慢。
同时在无限无标度网络中,临界值消失,即随机免疫法需要免疫网络中所有节点才能保证最终消息停止传播,这显然是不太现实的。
因此,对于无标度网络而言,即使对其上大量的节点都进行随机免疫,仍不能阻止消息的扩散。
目标免疫研究人员在随机免疫的基础上,利用网络节点度的非均匀性特点提出了有选择的目标免疫的思想。
选取节点度大的节点进行免疫,旦这些节点被免疫,则意味着它们所连的边可以从网络中删除,删除这些边后即重构了网络。
和提出了种针对无标度网路的比例优先免疫策略,即每个个体被选中接种疫苗的概率与相应节点在网络中的度成正比。
文献针对模型提出了目标免疫方法,即对节点度大的节点优先免疫。
目标免疫法是种。
若在定范围内无法找到公共节点,则将消息转发到个相对中心即节点度比较大的节点上。
基于偏好的路由为实现高效的信息传输,已有许多研究致力于提出更好的路由策略。
每个路由器能够感知到的网络拓扑结构的范围对网络容量起着至关重要的作用。
在社会学中,人对于不同的事物具有不同程度的偏好性质,往往人们根据自己的偏好进行相关的选择。
在自然界中,基于偏好转移聚集机制的凝聚现象十分普遍。
例如在城市人口增长过程中,拥有越多人口和便利交通的城市就越容易吸引更多的移民进入,表现为粒子对大城市有正偏好聚集。
等人研究了在无标度网络上依赖节点人口数目与度相关的移民聚集,发现了与在二维空间中完全不同的城市人口分布,这与美国城市人口分布相吻合。
在交通网络中,数据包将避免经过发生阻塞的节点,表现出对阻塞节点有负偏好聚集。
基于社会意识的路由在社交网络中,具有相同兴趣爱好的人们往往会形成个团体,经常相互交流,并且会更新确认团体内成员的信息,当有消息要转发时,会选择个最有可能将消息传播出去的人。
基于这种思想,文献提出种基于社会意识的路由。
该路由算法通过选择最佳的消息传播载体来实现消息的传播,采用功效值来选择最佳的消息载体。
功效值代表了个节点作为转发节点的能力。
功效值的确定和节点的位置信息以及可能与目标节点分享同兴趣的概率有关,与目标节点分享同兴趣的概率般通过卡尔曼滤波器进行预测。
进步研究方向社会网络信息网络和生物网络这些复杂系统的网络在不断演化,对它们的研究网络模型也从早先的规则网和随机网的认识,发展到现在的复杂网络。
然而,到目前为止,人们对复杂网络的本质传播动力学行为及高效的路由方法等方面仍有待进步的深入研究。
基于复杂网络的真实网络模型真实的网络系统大多同时具有个特征,即小世界高集团度和无标度。
方面和所提出的增长和择优机制虽然是第个能反映网络动态增长和幂律度分布唯具有无标度特性的分布的最简单模型,但模型的度指数为常数,而实际网络的度指数大多在另方面,无标度网络模型中平均距离固然较短,集群效应却很低,聚集系数会随着网络规模的增大而趋于零。
需要进步研究能更好刻画真实网络系统的复杂网络模型。
路由算法的计算复杂性目前,复杂网络中的路由问题已得到了较为充分的研究,但随着网络规模的增加,信息分发数据量的激增如物联网中的海量信息,新的信息表示方法的采用如语义事件等等,都要求网络路由器在转发信息时,具有高速海量及实时的特性。
众所周知,路由算法的复杂度直接影响了网络路由的性能及转发效率。
传统的路由从在线计算演化到离线计算在线查表的方法,大大降低路由转发时在线计算的复杂度,提高了路由器的路由能力。
面向海量数据互联网规模的网络时,需进步探索计算复杂度小转发效率高的路由算法及机制。
复杂网络中的可信路由在复杂网络环境下,同样存在信息传递的安全问题。
尽管复杂网络中的路由研究已经受到了研究人员的重视,与传统网络相似,但到目前为止,人们对复杂网络路由的认识和研究尚停留在寻路机制方面的研究,尚未充分关注可信路由的研究。
结语本文研究并讨论了复杂网络环境下的路由理论和方法,分析并归纳了现有的网络路由机制和方法。
由于复杂网络的直径短些节点的集聚度高等特性,与传统网络条件下路由有许多区别,研究人员针对复杂网络,利用社会学生物学等现象来研究网络路由理论和方法。
尽管人们针对复杂网络提出了很多网络路由的方法,但由于对复杂网络本质的认识和理解尚不充分,需要进步研究复杂网络的本质和机制,以及能适应未来网络要求的路由方法,包括对安全以及泛在网络的路由支持方法等。
参考文献陈华良刘忠信陈增强等复杂网络的种加权路由策略研究物理学报李涛裴文江王少平无标度复杂网络负载传输优化策略物理学报赵寒刘峰李明基于度负载联合偏好的无标度网络局部路由策略上海理工大学学报复杂网络环境下的路由方法研究摘要与规则网和随机网相比,复杂网络能更好地刻画和描述网络的特征,而路由策略是信息网络信息分发和交换最重要的手段之。
近年来,复杂网络中的路由受到研究人员的高度关注。
通过深入研究和讨论现有复杂网络中的路由策略,包括基于传统路由方法的复杂网络路由基于生物学行为的复杂网络路由以及基于社会学行为的复杂网络路由,提出了进步研究的方向。
关键词复杂网络路由策略生物学行为路由社会学行为路由引言通常用,来描述网络,其中为顶点,为边。
按照顶点度的分布,可将网络分为规则网随机网及复杂网络。
规则网中,各顶点度相等,如立方体网络环等随机网中各顶点度分布是随机的复杂网络的顶点度分布遵循幂次定律,且幂指数的值,通常为。
复杂网络具有较好的鲁棒性集群效应,且在规模相当的网络中,平均最短路径小于随机网。
最为常见的复杂网络,包括与提出的小世界模型以及与提出的无标度网络模型,也称模型。
长期以来,研究人员对传统的规则网和随机网路由进行了广泛的研究,已经提出了些行之有效的路由策略,如最短路径路由最小代价路由等。
人们对复杂网络中的路由及传播机制的研究,刚开始主要从复杂网络的简单统计特性如平均路径长度度分布边介数和节点介数等着手,近年来,部分研究人员则进步引入生物学和社会学的行为等思想和方法来研究路由策略及传播机制问题同时,也有些研究人员则从均匀化分配流量减轻最大介数节点的负载压力等提高网络传输能力方面来研究复杂网络路由问题。
