Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

基于Vega的战术与火力协同作战视景仿真系统

为了评估战术与火力协同作战对抗效能,建立了分布式战术与火力协同作战对抗网络仿真系统,给出系统框架并介绍各节点功能,详细介绍了视景仿真系统的实现方法和关键技术。基于Vega仿真软件环境开发了战场中的各种复杂场景特效,解决了非视觉物理量的可视化问题;利用Visual C++开发了视景仿真程序,解决了视景驱动和自动视点切换等具体问题。仿真结果表明视景系统可以逼真演示战术与火力协同作战过程并给出作战效能的直观评估。     

频谱搬移法的误差和噪声分析

频谱搬移法是一种新型的高分辨率成像技术,文章采用理论推导与数值仿真相结合的方法,对该技术应用于实际时可能遇到的误差和噪声做了讨论。研究发现:在条纹存在移动误差的情况下,还原图像的质量随条纹移动次数增加反而下降,一般条纹移动3次就能达到最好效果,这也是频谱搬移法原理要求的最少次数,因此这种方法的成像效果与成像速度是不矛盾的,而且在移动误差比较大的情况下,图像质量仍能有所改善;另外,其对条纹场噪声要求也不是很高,一般在信噪比15～20dB时就能非常接近无噪声时的理想效果。     

多轴向织物层合板层间剪切强度有限元分析与实验研究

用VIMP工艺制备了UD、0/45/-45、0/45/90/-45三种多轴向织物增强,四种厚度的GFRP层合板试样,采用短梁剪切实验考察了层间剪切强度和破坏模式。建立了GFRP层合板短梁剪切试样有限元模型,计算了内部层间剪应力分布。结合计算和实验结果分析表明层合板存在由宽度方向层间剪应力变化导致的自由边缘效应,含偏轴铺层的层合板更容易发生边缘开裂破坏。厚度相同时0/45/-45多轴向织物增强层合板的层间剪切强度最高。短梁剪切强度测试存在尺寸效应,随着厚度的增加,强度下降,样品波动系数增大。     

对特殊类型Feistel密码的Square攻击

对轮函数为SP结构的两类特殊类型Feistel密码抗Square攻击的能力进行了研究。通过改变轮函数中P置换的位置从而给出了此类Feistel密码的等价结构,以SNAKE(2)和CLEFIA为例,给出了基于等价结构Square攻击的具体过程,将6轮SNAKE(2)的Square攻击的时间复杂度由224降为213.4;将6轮CLEFIA的Square攻击的时间复杂度由234.4降为212.4。结果表明,在设计轮函数为SP结构的Feistel密码时,必须充分考虑等价结构对算法抗Square攻击的影响。     

二维超声速空气引射器启动特性试验研究

超声速引射器是高空模拟试车台的重要组件,在发动机启动前利用引射器对试验舱预抽真空,可避免发动机启动初始时刻燃气漏入试验舱造成燃气在发动机中分离,对获取发动机在高空环境下的完整推力特性具有重要意义。而该工况下超声速引射器的启动过程是引射器工作过程中最为恶劣的工况,设计不合理的引射器会导致启动压力过高甚至不能实现启动。建立了缩比超声速空气引射器试验台对超声速引射器的启动特性进行研究,采用压力测量方法结合纹影技术对超声速引射器处于极限启动压比时的流场进行了描述,研究结果表明混合室收缩比越小,引射器极限启动压比越低。同时给出了定位超声速引射器不启动原因的判据:当引射器不启动是由引射总压不足引起时,盲腔压力在引射总压提高时降低,并在临界启动状态下达到最小值;而由混合室收缩比过小导致的引射器不启动在引射总压提高时盲腔压力单调上升。     

自由漂浮柔性机械臂系统的动力学建模与仿真

动量矩守恒约束使自由漂浮柔性机械臂系统成为非完整系统,其动力学模型通常是难以求解的微分—代数方程,因此提出将机械臂系统等效为一个完整系统进行建模。假设载体存在姿态控制力矩,此时由于不存在动量矩守恒约束,系统变成一个完整系统,采用Lagrange方法建立其动力学方程;令方程中载体的姿态控制力矩为零,即得到自由漂浮机械臂系统的动力学方程;采用数值方法求解动力学方程,并将动力学分析的结果与ADAMS中仿真的结果进行对比,验证了模型能够有效模拟自由漂浮柔性机械臂系统的动力学特性。     

无线认知网络中一种分布式最大频谱分配算法

无线认知网络被认为是下一代无线网络的核心架构之一。该网络能解决日益增长的频谱使用需求和低下的频谱使用率之间的矛盾。通过伺机接入临时可用频谱资源,其频谱利用率能得到大幅的提高。由于频谱资源分配是影响频谱资源利用率的关键,因此如何对频谱资源进行高效的分配一直是无线认知网络的重要研究领域之一。我们证明了在异构频谱使用概率条件下的最优频谱分配是NP难的问题。为了有效解决该问题,本文提出了一种基于分布式最大加权独立集的频谱分配算法——DMWIS。该算法的时间复杂度为O(V2/2)。通过大量的仿真实验,验证了在90%以上的不同随机网络环境下算法能在3轮内收敛,并且该算法一般能获得最优解90%的性能。     

基于并行模拟的多核集群系统性能预测和分析

针对多核集群系统所表现出的新的性能特征,提出了面向多核集群系统消息传递应用程序的并行模拟模型并设计、实现了一个并行模拟器MCPSim(Multi-core Cluster Parallel Simulator),MCPSim在功能模型和性能模型上体现了片内核间、结点内片间以及结点间等三个层次上消息通信的特点,同时支持对应用的消息数量、通信量等的百分比分布的profiling功能,采用PRIMEJ、acobi3D、NPB IS以及HPL等Benchmark程序对MCPSim进行了测试,结果表明MCPSim性能预测的精度优于BigSim,同时能够广泛应用于针对多核集群系统消息传递应用程序的性能分析中。     

一种时频混叠的欠定混合通信信号盲分离算法

针对衰减-延迟欠定混合通信信号的盲分离问题,提出了一种基于子空间最小距离的源信号估计算法,通过计算观测信号到混合矩阵列矢量张成子空间的距离,估计任意时频点同时存在的源信号数目以及当前源信号对应的混合矩阵列矢量,把欠定混合问题转化为超定问题,然后通过计算Moore-Penrose逆矩阵求解源信号,理论分析和仿真结果验证了算法的有效性。