基于软件定义网络的多路径路由算法性能研究

基于不相交多路径的路由方案在负载平衡、容错等方面具有明显优势,但存在计算复杂度高的缺点,故对应的分布式算法难以在网络中大规模部署.通过分析软件定义网络的特点,论证了在其网络中部署不相交路径路由方案的可行性.其次,基于网络流的性质与不相交路径的图论性质,设计并实现了计算不相交路径的算法.最后,通过一系列基于不同网络模型的对比实验,验证所提算法较传统最短单条路径路由算法具有更佳的负载均衡.实验结果表明,该算法的性能与网络中链路能承受的负载极限阈值有关.     

基于网络简化技术的通风网络可靠度新算法

为了解决在网络可靠度计算中存在运算量过大的问题,利用不交和的原理计算网络的可靠性是当今所有计算网络可靠性方法中最有效的方法之一,但对大型网络依然无法快速确定网络可靠度。针对这一问题,采用直接构造不交化通路集的方法,结合网络简化技术和截断误差理论,提出了一种快速确定大型通风网络可靠度的算法。结果表明:本算法可在24 s内计算出传统算法10 h都无法算出的大型通风网络可靠度问题。该算法对提高大型通风网络可靠度计算速度具有很大作用。     

能量感知多路径负载均衡路由算法

针对移动自组织网络的网络拥塞问题,基于能量感知技术并结合负载均衡和拥塞控制方法,提出了一种能量感知多路径负载均衡路由算法。该算法利用能量感知选择满足条件的节点作为路由节点,建立多条连接源节点和目的节点的有效路径;同时分析路径的跳数、节点缓冲区的占用情况,从有效路径中选出用于传输的最优路径;然后对最优路径上的节点和路径的负载情况进行建模分析,当节点能量、节点负载、路径负载到达设定的阀值,就将最优路径上的流量分流到其它路径。利用NS2仿真软件,在不同的场景下对该算法以及QMRB、SMORT进行仿真测试。仿真结果显示:提出的算法与其它路由算法相比将网络性能提升了近20%,起到了均衡负载的作用,能有效地解决网络拥塞问题。     

求解无环K短路径的Dijkstra算法

对多个标号的求解K短路径的Dijkstra改进算法进行完善,引入两个前驱节点矩阵pre和Kpre,通过这两个矩阵可以求出起始点到当前节点的当前路径,并判断这条路径是否有环,从而在寻找K短路的过程中避免了环的出现,完善后的算法可以求出前K短无环路径,该算法仅需要较少的额外计算量,所以仍然保持了算法的多项式复杂性.然后在不同规模的网络上对完善后的算法进行数值试验,验证了算法的正确性和有效性.     

基于多维体理论的生命线网络可靠性的不交和算法

根据生命线网络系统的图论模型,应用计算机辅助逻辑综合技术对网络可靠性的精确算法进行了探讨.采用多维体列阵表示网络可靠性的逻辑函数,应用锐积和二进制布尔运算实现网络的路经不交和算法和计算机编程.最后,通过算例验证了该算法的有效性.     

传感器网络中基于抽样的带权近似Top-k〖WT〗〖HT3,2〗查询算法

提出一种适用于传感器网络的抽样带权阀值过滤近似Top-k聚集查询算法.该近似算法会将无线传感器网络划成几个两两不相交的簇进行处理,在汇聚节点进行预处理以及在各个簇内进行抽样过滤处理,在抽样过程中给可靠而重要的节点赋上相应更大的权值,同时根据节点采集的信息具有时间相关特性,在簇内进行抽样阀值过滤处理,每个簇头节点都会接收到该簇内的Top-k候选子集,然后将每个簇的子集发送给Sink节点,该Sink节点将接收到能代表整网Top-k样本候选集.仿真实验结果显示该算法只需发送少量的数据,更小的抽样样本,并能满足任意精度要求.     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.     

基于弱多径覆盖的自组织网路由协议

为了提高无线自组织网路由协议的可扩展性,根据多路径路由协议的特点,建立了多径寻由策略的数学模型.针对节点分离(Node disjoint)和链路分离(Link disjoint)式两种多径拓扑组织结构的缺点,提出了基于弱多径覆盖的具有可扩展能力的路由协议.在此基础上对多径算法进行了分析和仿真实现.仿真结果验证了算法的正确性和有效性.基于弱多径覆盖的路由算法对网络拓扑要求不高,更容易得到可行解,同时有效地提高了网络的可扩展能力.     

用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkcrson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中，后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流，就是利用找独立通路的思想来找增广路，找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边，找分支的可增广量为量大的出边，将该出边的末节点作为新的寻边始节点，继续找可增广量最大的出边，该搜索过程一直到所寻找的分支的末节点为网络的汇点为止，一条增广路即一条通路确定完毕，将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和，删除饱和分支，用导出的网络继续找新的增广路并增广。     

网络可靠度一种新的不交和算法

给出网络可靠度一种新的不交和算法，对两终端可靠度而言，当给出两终端道路集合后，撮一种排列道路顺序的新原则，利用不交和算法，在计算中借助布尔代数，定理进行简化，使得算法步骤较少而可靠度的符号表达式更加紧凑。     

利用二分决策图计算网络可靠度的一个有效算法

利用二分决策图,同时采用道路排序技巧及布尔代数运算给出了求不交和的方法,它比单纯采和二分决策图的算法更简单,不交和的项数更少,从而得到一个求网络可靠度的有效算法。『     

全光Johnson网络容错路由设计

随着光通信技术的发展，如何在光网络中提供较好的容错路由成为光网络的主要研究内容．本文在Johnson网络模型中通过对结点位串中相异子串的转换运算，先找出网络中的任意结点间最短路，在寻找次短路时在源结点和目标结点的相同位串中转换一位后再在不同位串上应用最短路算法，最终提出一种按预先商定模式（pre-negotiated mode）的容错路由，使全光Johnson网络J（n,k）中任意两结点之间存在k条内部不相交的路，它们由最短路与次短路组成．     

An Algorithm Based on Mobile Agent for Delay Constrained Least Cost Unicast Routing

0Introduction Distributedreal timemultimediaapplicationsrequirethenetworktoprovidestrictboundsonend to enddelay,costandotherqualitiesofservice(QoS)metrics,suchaslossanddelayjitter.Thisrequiresroutingalgorithmsthatarede signedtotakeintoaccounttheQoSconstraints.Efficientrouteselectionalgorithmsareabletooptimizetheusageofnetworkresources,reducethecostofservices,andallowmoreapplica tionstorunsimultaneously[13].RoutingproblemswithmorethanoneadditiveconstraintareNP Complete[46].Oneoftheproblemss…     

Topology Control Algorithm Using Fault-Tolerant 1-Spanner for Wireless Ad Hoc Networks

A fault-tolerant 1-spanner is used to preserve all the minimum energy paths after node failures to cope with fault-tolerant topology control problems in wireless ad hoc networks.A fault-tolerant 1-spanner is a graph such that the remaining graph after node failures will not only remain connected,but also have a stretch factor of one.The fault-tolerant 1-spanner is used in a localized and distributed topology control algorithm,named the k-Fault-Tolerant 1-Spanner (k-FT1S),where each node constructs a minimum energy path tree for every local failed node set.This paper proves that the topology constructed by k-FT1S is a k-fault-tolerant 1-spanner that can tolerate up to k node failures,such that the remaining network after node failures preserves all the minimum energy paths of the remaining network gained from the initial network by removing the same failed nodes.Simulations show that the remaining network after removal of any k nodes still has the optimal energy efficiency and is competitive in terms of average logical degree,average physical degree,and average transmission radius.     

基于网络编码的共享链路路径保护机制

网络编码(network coding,NC)方法能够有效地提高路径保护技术的保护效率.但目前提出的基于网络编码的保护机制要求工作路径链路分离,限制了保护机制的性能和应用范围.为此提出一种基于网络编码的有共享链路的路径保护机制(shared-link network coding path protection,SNCPP).该机制将共享链路的端节点加入到保护路径源目的节点集中,采用改进的ASTAR算法建立经过节点集中所有节点的最短保护路径,并利用网络编码实现对有共享链路的路径进行保护.仿真表明所提出的机制在工作路径出现共享链路故障的情况下,能够对网络提供保护,并提高了保护效率.     

k-不相交路径的容错拓扑控制算法

针对无线传感器网络中拓扑控制算法优化目标单一的问题,提出一种既能优化网络能量效率,又能保证网络容错性的k-不相交路径的容错拓扑控制算法.首先,构建传感器节点到sink节点的k条不相交路径,通过增加冗余链路以提高网络的容错性;其次,选择路径能耗、路径中节点功率的标准差及路径跳数检测路径质量;最后,建立多目标规划,并利用智能优化算法对其进行求解,根据k值的不同对路径进行择优选择以达到降低网络能耗并延长网络寿命的目的.仿真实验结果表明,由该算法构造的网络拓扑能有效降低网络能耗,延长网络寿命并提高网络的容错性.     

攻击图算法在入侵防御系统中的应用

 针对目前及时发现网络漏洞,增强网络安全十分困难等问题,提出了基于攻击图的入侵防御方法.该方法通过生成全局网络攻击图算法来建立网络初始攻击图,并调用攻击图优化算法来去除全局攻击图中不合理路径,达到简化攻击图目的.最后,通过计算攻击图各状态节点损失度算法来为管理人员提供优化网络安全策略的依据.实验证明,这种入侵防御方法合理有效,并具有简单易行等优点.     

带转向延误和限制的最短路径问题及其求解方法

阐述了带转向延误和限制的最短路径问题(SP-Turn)的基本原理,系统介绍了现有的求解方法,包括扩展网络法、对偶网络法和弧标号算法,并提出了一个节点标号算法用于对比.分析指出弧标号、节点标号算法在算法原理上是一致的,对偶网络法是对它们的直观化.同时指出在SP-Turn方法中,扩展邻接表是高效的网络表示形式,在合理选择的前提下,一般SP算法的标号设定、标号修正等标号技术同样适用,最短路径可由节点至弧的形式转换为节点至节点的常规形式.     

Combining Topological Properties and Strong Ties for Link Prediction

Link prediction is an important task that estimates the probability of there being a link between two disconnected nodes. The similarity-based algorithm is a very popular method that employs the node similarities to find links. Most of these types of algorithms focus only on the contribution of common neighborhoods between two nodes. In sociological theory relationships within three degrees are the strong ties that can trigger social behaviors.Thus, strong ties can provide more connection opportunities for unconnected nodes in the networks. As critical topological properties in networks, nodes degrees and node clustering coefficients are well-suited for describing the tightness of connections between nodes. In this paper, we characterize node similarity by utilizing the strong ties of the ego network(i.e., paths within three degrees) and its close connections(node degrees and node clustering coefficients). We propose a link prediction algorithm that combines topological properties with strong ties, which we called the TPSR algorithm. This algorithm includes TPSR2, TPSR3, and the TPSR4 indices. We evaluate the performance of the proposed algorithm using the metrics of precision and the Area Under the Curve(AUC). Our experimental results show the TPSR algorithm to perform remarkably better than others.     

一种无线传感器网络中的虫洞攻击检测算法

分析了无线传感器网络中的虫洞攻击的特点,根据某些路径变短和某些节点的邻居数增加的特点,提出了一种无线传感器网络中虫洞攻击的检测算法.首先在边界部署一些源、目的节点对,然后利用路由发现过程来发现跳数异常少的可疑路由.通过检查邻居节点数来检测可疑路径上的每个节点,如果节点的邻居数增加,则该节点为被感染节点,网络中存在虫洞攻击.被感染节点被从网络中隔离,以避免更大的破坏.实验结果表明该算法具有较低的漏报率和较高的准确性.