一种新的ASON恢复容量优化算法

针对ASON网络恢复容量问题,建立了相应的数学模型并提出了一种基于粒子群的恢复容量优化算法.与线性规划寻优方法相比,该算法的可行解搜索空间及计算量大大降低,为算法在工程上的实现提供了可行性.该算法可处理不同故障情况下的多种最佳恢复路由的选取问题,能有效地解决链路波长信道恢复容量的"碎片"问题.仿真实验验证了该算法具有较强的实用性.     

基于软件定义网络的卫星网络容错路由机制

鉴于卫星网络对安全性和应对故障的能力有很高的要求，引入了软件定义网络（SDN）技术，在网络中放置中央控制器来增强网络对故障的应对能力。首先，基于SDN的思想设计了一种卫星网络模型，计算了三层轨道上卫星运行的参数并构建星座；然后，采用分层路由的方法，设计了一种针对卫星网络的容错路由机制；最后，在Mininet平台上进行了仿真实验，将容错路由算法（FTR）的实验结果与基于链路感知的星间路由算法（LRSR）和多层卫星网络路由算法（MLSR）的实验结果进行了对比。对比结果表明，在网络中无损坏节点和链路的情况下，FTR的路由总延时比LRSR平均降低了6.06%，说明了引入SDN集中控制的有效性；FTR的丢包率比同样以最小延时为目标的MLSR降低了25.79%，说明了在网络模型中为中轨道（MEO）卫星设计临时存储路由机制的有效性。而当网络中节点和链路的失效情况比较严重时，FTR的路由总延时比LRSR降低了3.99%，比MLSR降低了19.19%；其丢包率比LRSR降低了16.94%，比MLSR降低了37.95%，说明了FTR的容错有效性。实验结果验证了基于SDN的卫星网络路由机制具有更好的容错能力。     

耐故障Clos网及其路由算法

提出了一种新的耐故障Clos网,通过在基础Clos网各段中增加冗余的交换单元,使其能够在发生少量故障的情况下正常工作,从而提供更可靠的服务。针对耐故障Clos网,给出一种耐故障Clos路由算法,该算法采用最小分布优先的策略逐列计算Clos网连接说明矩阵,通过重排完全实现无阻塞路由,该算法的时间复杂度在最坏情况下仅为O(N3/2)。该耐故障Clos网及其算法设计可以用于实现更为可靠的Clos网络。     

K步故障扩散定位算法的Matlab实现

分析了故障传播的机理并推断出其有限步扩散性,提出了一种K步故障扩散定位算法.对系统故障有向图进行了分片处理,结合故障传播概率矩阵对故障嫌疑节点进行故障扩散模拟寻找最佳扩散路径和最大嫌疑节点.使用C 编程和Matlab工具实现了KFL算法并给出部分具体工程源代码,对实际工程项目故障定位进行了仿真模拟.该算法可同时模拟诊断单点故障和多点故障,与传统故障定位的逆向算法不同,该算法是一种新型的正向思维的图匹配算法.     

超立方体并行计算机的一个新型故障诊断算法

提出了超立方体并行计算机的一个新型系统级故障诊断算法.与现有诊断算法相比,该算法能够在系统中存在较多故障处理器的情况下,正确定位全部故障处理器（代价是至多误诊断三个无故障处理器）.另外,该算法的时间复杂度与最好的现有算法相当.     

K步故障扩散算法的设计与实现

文中分析了故障传播的机理及其有限步扩散性,提出了一种K步故障扩散算法．针对系统故障有向图寻找最佳扩散路径．使用C＋＋编程实现算法并对具体工程进行了仿真实验．可同时模拟和诊断单点和多点故障。与传统的故障定位算法相比,它是一种新型的正向思维匹配算法,结合了传播代价,定位更加准确.KFP算法可模拟产生系统的故障扩散运行图,预测和定位故障源,在实际工程得到了较好地应用。     

面向共享风险链路组故障恢复的多路径路由生成算法

为了在IP层恢复网络共享风险链路组(SRLG)故障,提出一种基于改进人工蜂群算法的网络多路径路由生成算法.针对SRLG故障特点建立多路径路由生成模型,最后通过改进人工蜂群算法求解.仿真验证该方法不仅可以生成满足SRLG约束的备用路径,还可以增强故障恢复能力、降低算法复杂度、缩短重路由的平均路径长度.     

快速排序性能分析

在决策树计算模型下,任何一个基于比较来确定元素相对位置的排序算法需要的计算时间是Ω(nlog2n).如果能设计一个需要O(nlog2n)时间的排序算法,在渐近的意义上,这个排序算法就是最优的.由C.A.R.Hoare发明的快速排序算法它在平均情况下需要O(nlog2n)时间.本文就该算法在最好情况下、最坏情况下、平均情况下的性能进行分析.     

基于rLFA技术的性能优化及重路由选择算法研究

为进一步提高网络单故障快速恢复能力,基于改进的Remote Loop-Free Alternates(rLFA)重路由技术,提出一种采用混沌粒子群并考虑网络物理传输代价和拥塞代价的重路由选择算法.首先基于rLFA的隧道建立方法对其进行改进,结合引入隧道技术的链路增补方法来实现故障全覆盖,通过设置权重因子来保证在不同业务量下的重路由选择针对性.实验表明,改进的rLFA能进一步提高网络单故障覆盖率,同时结合链路增补方法在保证故障完全覆盖的情况下能够大幅度减少链路增补数量;路由选择算法能够动态选择不同业务量下的重路由路径,在提高网络单故障环境下的传输效率的同时也实现了负载均衡.     

基于协同过滤的连续黑箱优化问题元启发算法选择

算法选择(AS)问题旨在为给定问题在算法集合中选择最佳算法.随着优化算法的不断提出,算法选择问题是优化领域亟待解决的问题.提出基于聚类的元启发算法五星评价体系,将算法性能指标映射至整数评价以减小评价空间.通过测试24种常见优化算法与4种最新CEC大赛优胜算法在219种、3000多个标准测试问题上的性能,得到评价矩阵.将评价矩阵作为训练数据,使用协同过滤(CF)算法建立算法评价的预测模型.使用该模型预测算法集内的所有算法在新问题上的评价,结果显示所提出方法预测精度较高,超过90%的预测最佳算法为最终可行算法.敏感性分析显示,该方法在先验信息有限的情况下仍可以保持较高的预测精度.     

无线传感器网络方向性分区路由算法

针对中小规模无线传感器网络路由算法效率不高的问题,提出了一种新的路由算法——方向性分区路由算法。新算法采用方向性信息传输及区域划分方法,便于信息融合及移动节点处理,路由维护简单,节能性好并易于实现。通过仿真实验与洪泛法及理想路由情况比较,结果表明该算法在数据包接收速率和节能性方面具有明显的优势。     

基于ODMRP的分布式核心稳定路由算法

在无人机网络中,由于节点具有较强的移动性,对于组播路由的建立以及组播组的划分提出更高要求,一般的组播路由协议往往无法满足网络需求.为此,提出了一种基于ODMRP的分布式核心稳定路由算法.该算法结合了改进贪婪机制,根据路由状况对路径进行优化,为了降低源节点的数据处理负担,提出了分布式核心节点选择机制,将组播组的信息储存在多个核心节点中,同时释放了转发节点的储存空间.文章通过路由抢修机制,监控路由状态变化,对即将断裂的路由提前修复,保证了路径的有效性.仿真表明,该算法与标准的ODMRP算法及改进算法VCMP算法相比,能够优化传输路径,降低端到端时延,提高分组交付率,提升网络性能.     

二维网格中基于最小通路区的自适应和最小容错路由算法

网格结构是并行与分布式处理中最流行的一种网络拓扑结构。在存在故障的情况下，如何设计具有最优性的容错路由算法一直是研究的热，点问题。本文研究了采用故障块模型的二维网格的最小路由问题，提出存在最小通路的一个充分必要条件。基于最小通路区（RMP）的概念，提出一种自适应的最小容错路由算法。如果源节点和目的节点之间存在最小通路区，则在最小通路区中进行自适应最小容错路由；反之，则采用多阶段最小容错路由。主要思想就是在存在故障的情况下，尽量保证路由算法能走最短路径。因为只要求知道每个节点的局部信息，故算法是分布式的。     

Mobile-Agent的空洞避免路由算法

为了解决空洞恢复路由算法在能耗、路由开销及可扩展性等方面的问题,提出了使用移动代理(mobile-agent,MA)进行网间处理来避免"路由空洞"的算法(hole avoiding routing algorithm with mobile-agent,HAMA)。HAMA将网络中的节点分为"空洞相关节点"或"空洞无关节点",通过采用MA方式,对"空洞相关节点"进行路由处理,为其找到一个最优下一跳节点,最终成功建立到Sink节点的路由,从而达到避免"路由空洞"的目的。HAMA使节点提前意识到"路由空洞"的存在,尽可能绕开路由空洞,从而降低网络能耗,均衡网络负载。与经典空洞路由算法GPSR(greedy perimeter stateless routing)相比,HAMA能够成功避免"路由空洞",即使遇到"空洞相关节点",也能较为成功地启用各种恢复机制绕过空洞,具有低成本、高性能的特点。     

关于连接时间和空闲度的Ad Hoc网络路由方案

传统的Ad Hoc网络路由协议主要是基于“最短路径”来考虑,这样可能使网络中某些节点负载过重,还可能导致延迟、数据丢失等问题。利用非最短路径路由中那些保持连接时间较长,并且通信量较少的节点,将节点的连接时间和空闲度加权和作为选择路径的依据,提出一种新的路由算法LLAODV（Link expiration time and Leisure degree AODV）,实验结果表明,改进后的算法改善了网络性能。     

无线传感器网络权衡生存时间与数据分组跳数的分流路由算法*

无线传感器网络的节点大多采用电池供电.因而节能对无线传感器网络就显得至关重要.该文提出一种能耗感知的优化网络生存时间的路由算法,称之为分流路由算法(DTRA,Diffluent Traffic Routing Algorithm).DTRA算法采用一个优化模型以优化每个节点发出的数据比例,从而达到权衡网络生存时间和数据分组跳数.此外,采用一个简单的遗传算法求解该优化问题.仿真结果表明:DTRA算法能显著地提高网络的生存时间,同时将数据分组平均跳数保持在一个较低的水平;在网络生存时间上,DTRA算法比一些已有的知名算法更优.     

Robust load-balanced backbone-based multicast routing in mobile opportunistic networks

Mobile opportunistic network (MON) is an efficient way of communication when there is no persistent connection between nodes. Multicast in MONs can be used to efficiently deliver messages to multiple destination nodes. However, because multiple destination nodes are involved, multicast routing is more complex than unicast and brings a higher communication cost. Backbone-based routing can effectively reduce the network overhead and the complexity of routing scheme. However, the load of backbone nodes is larger than that of regular nodes. If the backbone node’s buffer is exhausted, it will have a significant impact on the performance of the routing scheme. Load balancing can improve the ability of backbone to deal with the change of network load, and backbone maintenance algorithm can provide backbone robustness. In this paper, we propose a robust load-balanced backbone-based multicast routing scheme in MONs. In the backbone construction algorithm, we transform the problem of backbone construction into a multi-objective optimization problem, and propose a multi-objective evolutionary algorithm-based backbone construction algorithm, namely LBMBC-MOEA algorithm. In addition, in order to increase the robustness of the backbone-based routing scheme, we propose a localized multicast backbone maintenance algorithm (MBMA) to deal with the buffer exhaustion of backbone nodes. When a backbone node’s residual buffer is insufficient, MBMA algorithm selects other nodes to replace the backbone node. The results on extensive simulations show that when considering the node buffer size constraints, compared with previous backbone-based multicast routing schemes, our proposed algorithm has better performance, and when the node’s residual buffer is insufficient, MBMA algorithm can significantly improve the performance of the backbone-based multicast routing scheme.     

Efficient routing and sorting schemes for de Bruijn networks

We consider the problems of routing and sorting on a de Bruijn network. First, we show that any deterministic oblivious routing scheme for permutation routing on a d-ary de Bruijn network with N=dⁿ nodes, in the worst case, will take Ω(√N) steps under the single-port model. This improves the existing lower bounds provided d is not a constant. We also show that the lower bound is indeed a tight one. Second, we present a deterministic nonoblivious permutation routing algorithm which runs in O(d.n²) time on a d-ary de Bruijn network with N=dⁿ nodes. This algorithm is currently the fastest known nonoblivious deterministic routing algorithm for de Bruijn networks of arbitrary degree. Finally, we present an efficient general sorting algorithm for the de Bruijn networks of arbitrary degree. This algorithm is the best sorting algorithm known so far. It runs in O((log d).d.n²) time for directed de Bruijn network with dⁿ nodes, degree d, and diameter n. As a corollary, we show that on a binary de Bruijn network of Nnodes, our sorting scheme requires at most 2 log² Nsteps     

一种新型煤矿井下无线通信系统研究

针对应急救援常用的救灾通信电话存在通信链路建立时间长、通话质量差、不能实时在线等问题,提出了一种基于Mesh多跳和跳频扩谱技术的煤矿井下无线通信系统的设计方案。采用骨干路由节点和中继路由节点相互配合构建Mesh多跳的基础结构,同时采用多射频多通道技术来提高多跳子系统的容量、多跳次数及覆盖范围;针对跳频扩谱通信链路中需要解决多频天线技术和异频无线路由技术的问题,采用改进型最小费用路由算法来确保在灾变后煤矿井下不确定性因素增强的情况下,无线传输选择最优路由链路。测试结果表明,该系统能够实时准确地将井下信息传送到地面救援指挥中心,且能够实现地面救援指挥中心与井下救护队员的直接对话和通信指挥,提升了应急救援能力。