复杂网络中基于层次分析法的路由策略

　　0引言

　　具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络[1]。自然界与社会生活中众多复杂系统都可用复杂网络来描述。近年来，关于复杂网络的研究正处于蓬勃发展阶段，其中复杂网络的传输能力与人们的工作生活关系密切，在现代社会中占据了非常重要的地位。因此，发生在复杂网络拓扑之上的各种动力学过程，如改善复杂网络路由效率以提高网络容量等问题，越来越多地受到统计物理学界和工程界的关注[1]。

　　1相关研究

　　随着网络规模和信息量的大幅增加，拥塞现象成为现实网络中常见的动态特性之一。许多实际网络，如因特网、交通网络等经常发生拥塞，由此导致网络整体性能下降，甚至瘫痪。导致网络拥塞的主要原因有两方面：一是网络中传输的大量数据流（特别是并发数据）；二是网络本身的特性，包括节点容量、节点转发数据包能力、网络拓扑结构、通信链路带宽等。

　　目前，学者们通常用3种方式缓解网络拥塞的问题：一是使用特定的网络拓扑结构；二是提高单个节点转发数据包的能力；三是改进路由策略。第一种方法需要改变现有的拓扑结构，和第二种方法一样都存在成本高、资源浪费等问题。当网络规模较大时这些改变较难实现，单靠升级硬件能带来的改善效果也有限。因此，许多研究人员在改进复杂网络路由策略方面做出了很多有影响力的工作[1]。

　　广度优先[2]和随机游走[3]是复杂网络中最简单的路由策略，但它们没有考虑网络的拓扑结构，随着网络规模的扩大，网络中会产生大量的重复数据包，从而导致网络拥塞。因此，尽管它们在路由效率的理论分析中被广泛采用，在实际中却难以应用。目前，现实网络中的路由算法多采用基于最短路径路由算法[4]，但该算法要求所有节点都知道全局信息，只考虑了网络结构属性而忽略了网络中负载的动态特性。另外，上述研究都基于一种假设，即复杂网络的结构是单层的，所有节点在处理数据包能力等方面一致且每个节点等待队列的长度无限。但实际通信网络中，这些假设很难成立，需要依照实际设计综合考虑网络拓扑和负载动态等问题的更优化的路由策略[5]。另外，在网络的动态演进过程中，由于网络规模大，要每个节点都知道全局信息并不现实。因此，基于局部信息比基于全局信息的动态路由策略更易于部署实施。

　　在综合考虑网络中节点处理能力、空闲队列长度、聚类性、度等网络拓扑和动态负载参数的基础上，引入层次分析法[6]建模，提出了复杂网络中基于层次分析法的路由策略（RoutingStrategyinComplexNetworkbasedonAnalyticHierarchyProcess，简称RSAHP）。算法利用若干权重因子的组合来选取下一跳转发节点，其中权重因子的组合综合地反映了网络的拓扑属性和动态负载等当前状态。理论分析和实验证明，RSAHP具有如下良好性质：①分布式的网络路由策略在实际网络中易于实现；②具有自适应性，每个接收到数据包的节点在系统的观点下综合判断、决定下一跳转发点，通过合理选择下一跳有效地提高网络通信能力。理论分析和仿真实验表明，RSAHP比最短路径算法更能有效避免拥塞，并能进一步增强复杂网络的网络容量。

　　造成上述问题的主要原因是SPRS只考虑了网络拓扑结构属性而没有考虑网络中负载的动态特性，要传送的数据包也无法选择其它的路由路径，当最短路径中的节点发生拥塞时，SPRS会使拥塞节点更拥塞，从而进一步降低网络性能，甚至加速网络崩溃。而RSAHP在综合考虑网络中节点处理能力、空闲队列长度、聚类性、度等网络拓扑和动态负载参数的基础上，利用若干权重因子的组合来选取下一跳转发节点，综合地反映了网络的拓扑结构属性和动态负载等当前状态。理论分析和仿真实验表明，RSAHP比SPRS更适合大规模网络，更能有效避免拥塞，并进一步增加了复杂网络的网络容量。

　　参考文献：

　　[1]臧海娟，任彦，薛小平等.复杂网络环境下的路由方法研究[J].计算机应用，2010（8）.

　　[2]SHARMAG，MAZUMDARRR.Hybridsensornetworks：asmallworld[C].Proceedingsof6thACMInternationalSymposiumonMobileAdHocNetworkingandComputing，2005.

　　[3]席峰.基于复杂网络理论的无线传感器网络地理路由和信息融合.[D].南京：南京理工大学，2010.

　　[4]WUZX，WANGWX，YEUNGKH.Trafficdynamicsinscalefreenetworkswithlimitedbuffersanddecongestionstrategy[J].NewJournalofPhysics，2008（2）.

　　[5]卓越.两层复杂网络上的动态权重路由策略研究[J].计算机应用研究，2011（9）.

　　[6]SUNLU.Aminmaxoptimizationapproachforweightdeterminationinanalytichierarchyprocess[J].JournalofSoutheastUniversity.2012（2）.