3－连通基本Harary图上的最优容错路由选择的构成

图Ｇ和路由选择ρ产对故障集Ｆ的容错性能可从其幸存路由图的直径（表示为Ｄ（Ｒ（Ｇ，ρ）／Ｆ）的大小得到反映．在任意大ｋ－连通图上，当ｋ≥３时尚无构成最优容错路由选择的一般方法．本文针对３－连通基本Ｈａｒａｒｙ图，给出了一种最优容错路由选择ρ的构成方法，即当｜Ｆ｜≤２时，有Ｄ（Ｒ（Ｇ，ρ）／Ｆ）≤２．     

3—连通基本Harary图上的最优容错路由选择的构成

图Ｇ和路由选择ρ对故障集Ｆ的容错性能可从其幸存路由图的直径的大小得到反映。在任意Ｋ－连通图上，当ｋ≥３时尚无构成最优容错路由选择的一般方法。本文３－连通基本Ｈａｒａｙ图，给出了一种最优容错路由ρ的构成方法，即│Ｆ│≤２时，Ｄ（Ｒ（Ｇ，ρ））｜Ｆ）≤２。     

边故障超立方体中两条无故障点不交路

文中用归纳假设法证明了结论：当n≥3时,令超立方体中的边故障集｜F｜≤n-3,设x1x2,y1y2是Qn中4个顶点,使得距离d（x1,y1）和距离d（x2,y2）都是奇数,则Qn-F中存在两条路P1和P2使得V（P1）∩V（P2）=φ,V（P1）∪V（P2）=V（Qn）,这里P1连接x1和y1,P2连接x2和y2,而且边故障集｜F｜=n—3（n≥3）是最佳上界．     

基于无线Mesh网络的路由协议性能比较分析

无线Mesh网络（Wireless Mesh Network，WMN）作为一种新型的无线网络，继承了WLAN和Ad hoc网络的一些特点目前，国内外对WMN路由协议的研究还处于初级阶段该文对目前存在的基于WMN的路由协议AODV及CGSR路由协议做了详细的分析，并进行仿真比较，指出了两种路由协议的性能差异，对今后在无线Mesh网络环境下改进更优的路由协议可起到一定的参考作用     

边故障超方中距离为偶长的两条顶点不交无故障路

本文得到如下结果：当n≥4时,超立方体Qn中的边故障集F≤n-3,设x1,y1,x 2,y 2是Qn中任意四个顶点,使得x1和y1属于Qn的一部,x2和y2属于Qn的另一部,则在Qn-F中存在两条顶点不交路P1和P2,这里P1连接x1和y1,P2连接x 2和y2,且V（P1）∪V（P2）=V（Qn）,且故障边数n-3是紧的.     

均衡流量的改进AODV协议

基于距离向量的按需路由协议是adhoc网络中一种具有代表性的按需路由协议.与传统路由协议相比,按需路由协议减少了建立和维护路由所需要的开支,但是随着网络节点发送数据量的增加,网络性能会迅速下降.针对这一问题,提出了一种简单有效的均衡流量改进AODV协议——TB-AODV协议.在TB-AODV协议中,每个节点根据本地链路层的负荷,决定拒绝或接受收到的路由请求,以避免加重局部拥塞,使得网络的负荷能更加均匀地分布.仿真结果表明,改进后的协议提高了网络的吞吐率,降低了分组传送的平均端到端延时,改善了网络性能.     

水声通信网中基于能量平衡的动态路由控制

针对水声传感器网中一些中继节点因过分使用而过早耗尽能量的问题,提出一种动态路由控制新方法.通过周期性预测出节点的信息产生率,并根据节点当前剩余能量,估计出采用不同路由时节点的生命值.以网络节点的最小生命值为目标函数,借助遗传算法周期性搜索出与最大目标函数值对应的路由,这样的路由就是能平衡各节点能量的最佳路由.仿真结果表明,该方法能避免生命值较小的节点承担过分的中继任务,延长节点生命.     

具有点故障的超方体中经过指定路的无故障圈

本文研究了在含有故障点的n维超立方体Qn中通过给定路的无故障圈问题,本文得到以下结果：设n≥3,2≤h〈n,F V（Qn）且｜F｜〈n-h,则在Qn-F中，每一条长度等于h的路P都包含在每个偶长度从2h＋2到2″-2｜F｜的圈中，并且当｜F｜〈h-1 时，则路P还包含在长度等于2h的圈中。     

无线传感器网络中基于Convexhull的能量空洞避免路由算法

提供了一种绕过无线传感器网络“能量空洞”的方法(CHA方法),可以用来找到绕过能量空洞的最优节点路由路径。在数据包从源节点传递到目的节点的过程中,通过遇到能量空洞,先勾勒出空洞范围,再基于凸壳(Convex hull)找到绕过能量空洞的最优节点路由路径。仿真结果表明,该算法优化了能量空洞绕洞路由路径,有效提高了无线传感器网络传输效率,减少了无线传感器能量损耗和信息传递的延迟。     

点故障增广立方体中2条点不交覆盖路

大型互联网系统在运行中某些元件或连线发生故障难以避免，故障的发生对网络的稳定性和数据传输时效性会产生影响．因此，研究网络容错性的参数尤为重要．研究了增广立方体在点容错条件下嵌入2条无故障点不交路覆盖问题．运用假设归纳法得到：当n≥4，增广立方体AQ_n中的点故障集F满足|F|≤2n-8时，若在AQ_n-F中任取4个顶点x₀,x₁,y₀,y₁，则在AQ_n-F中存在2条内部点不交路P₀=(x₀,…,y ₀), P₁=(x₁,…,y₁)，使得V (_P0)∪V (P₁)=V (AQ_n-F).     

k-ary n立方体中的测地泛圈

文中用归纳假设法证明了结论：当n≥2,k≥3,u和v是Qkn中任意2个顶点,由对称性,不妨设u=（0,0,…,0）,v=（d1,d2,…,dn）,这里0≤di≤k/2,（i=1,…,n）,记d=d1＋d2＋…＋dn≤1,N=kn,则对于每个偶数l适合2d＋2≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.若有i和j满足1≤i≤j≤n,使得di≥1且dj≥1,或有且dj=k/2且dj=0,j≠i,1≤j≤n,则又有l=2d;当n≥2,k≥3是奇数,u和v是Qkn中任意2个顶点,由对称性,不妨设u=（0,0,…,0）,v=（d1,d2,…,dn）,这里0≤di≤k/2,,（i=1,…,n）,记d=d1＋d2＋…＋dn≥1,N=kn,r=max{di},则对于每个奇数l适合2d＋k-2r≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.     

边故障3-aryn立方体中两条无故障点不交路

文中用归纳假设法证明了结论：当n≥2,FE（Qn3）,∣F∣≤2 n-4,令x1,y1,x2,y 2是Qn 3中任意四个顶点,则在Qn 3-F中存在两条顶点不交的路P1和P2,使得V（P1）∪V（P2）=V（Q n3）,这里P1连接x1和y1,P 2连接x 2和y 2.     

复杂网络图中心节点分布的研究

复杂网络图中不同的节点的作用和重要程度不同.节点的中心性度量,可以反映节点在图中的作用以及对其他节点的影响.复杂网络的全局中心节点有时分布较为集中,不能很好地反映网络图各处的重要节点.局部中心点是中心性度量值大于等于它的所有邻居节点的中心性度量值的节点,分散分布在网络图中,分散分布在社区中,是复杂网络中具有大的局部影响力的重要节点.     

完全二部图K_（n,n）的容错偶泛连通性和完全k（k≥3）部图K_（n,n,…,n）的泛连通性

图G称为泛连通的,如果对于G中距离为d（x,y）的任意两点x和y,G中都存在每个长为l的x：y路（这里d（x,y）≤l≤︱V（G）︱-1）;图G称为偶泛连通的,如果对于G中距离为d（x,y）的任意两点x和y,G中都存在每个长为l的x： y路（这里d（x,y）≤l≤︱V（G）︱-1）,且l和d（x,y）有相同的奇偶性.本文用归纳法证明了以下结论：当n≥2时,在完全二部图K n,n中,若故障边数︱Fe︱≤n-2,则K n,n-Fe是偶泛连通的,并且︱Fe︱的上界n-2是最优的;完全k（k≥3）部图K n,n,…,n是泛连通的.     

两台机器流水作业中带成组加工的最大迟后问题

考虑分批加工中的流水作业问题:且工件在两台机器间作成批转移,目标函数为L_max.文中指出该问题为NP-hard后给出了其多项式可解的特例并构造了相应的动态规划算法.     

移动Ad Hoc网中基于QoS的功率优化自适应多业路由协议

移动Ad Hoc网是一种由移动节点组成、拓扑结构动态变化的自组织网络。在网络中没有固定的基础设施，移动节点既是通信主体，又承担报文转发的功能。由于其与众不同的特点，路由的选择就变得特别重要。在已存的路由协议中，主要考虑提供单业务路由，而对多业务路由则较少涉及。提出了一种充分考虑功率优化和QoS要求的多业务路由协议，通过发射较大的功率来建立最大功率的满足QoS要求的路由，同时通过中间节点的窃听和重定向来建立功率优化的路由，然后根据不同业务来选择不同的路由进行通信。通过比较发现，此协议能够提高网络的综合性能。     

一个可拒装卸引发的排序问题

从生产实际中提炼出下述可拒装卸引发的排序问题：有n条船（工件）在时刻零同时抵达同一码头（机器）等待装卸货物（加工）,因而也希望在同一时刻（应交工时间）完成装卸任务。如某船的货物不能如期装卸完而延误了该船的离港,船主会向港方索赔。反之,如提前装卸完而使该船可提前投入运输,则船主会向港方发一定奖金。同时若某船货期较紧而延期罚值较大时,港方宁可付出较小费用安排该船到附近的码头去装卸货物。对这样一个可拒装卸问题,从港方来说需考虑的是是否装卸这些船以及如何适当安排所装卸船的装卸顺序以使总费用最小。文中在对该问题给出了一些性质后,对共同应交工时间不大于所有工件的最小加工时间的上述问题证得为 并构造了一伪多项式时间算法,从而证明了此时的问题为普通意义下 的,对共同应交工时间大于所有工件的最小加工时间的上述问题也证得为 的并研究了其几个子问题,指出它们或为普通意义下 的,或为多项式时间可解的。     

基于树形拓扑网络的实用拜占庭容错共识算法

实用拜占庭容错算法在节点数量较多的广域网环境下存在性能瓶颈.为提高该算法的可扩展性，基于树形拓扑网络将全网范围共识拆分为若干子网范围共识；同时引入信誉模型以降低错误节点在共识过程中的影响力，提高系统的安全性、容错性与可靠性.实验结果表明：所提算法的性能明显优于原有算法，表现出良好的可扩展性，可用于大规模许可链系统.