X结构下VLSI多层绕障Steiner最小树算法

Steiner最小树作为VLSI布线的基础模型,应进一步考虑到X结构、障碍物、多层等条件,文中基于粒子群优化提出了多层绕障X结构Steiner最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.     

无线Mesh网络中的骨干网络部署的优化

在满足用户需求情况下,优化无线Mesh网络中接入点(TAPs)放置以及布线线路以减小布线成本.首先,把该问题中的布线问题模型化为欧氏空间中准组Steiner树问题.解决传统的组Steiner树问题的算法在该问题上并不适用.其次,针对该问题特有的特征给出了一种近似算法.最后,为了达到最小化网络布线的成本的目的,在布线的基础上使用线性规划达到最小化TAPs数目.模拟实验的结果表明,该方法能够显著降低布线成本.优化方法对于无线Mesh网络的骨干网络的部署具有重要指导意义.     

Ad hoc网络时延受限的Steiner树启发式算法

针对Ad hoc网络时延受限的Steiner树问题,设计一个分布式的快速启发式算法DCST,该算法通过对网络中节点进行标号,并根据标号修改节点间的关联关系,建立一棵时延受限的Steiner树。在网络节点保持时间同步的前提下,算法的时间复杂度为O(n)。与现有经典的Steiner树算法相比,该算法具有明显优势。     

基于加权节点的Steiner树启发式算法

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明: NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。     

一种通过加入中继节点以修复大面积网络损坏的能量均衡算法

研究了在大面积受损的无线传感网(WSN)中通过加入中继节点(RN)来修复网络连通性的问题,以修复代价最小化为目标提出了新的算法,目标包括减少中继节点数并均衡节点能量。为了减少中继节点数,在每个分区的边界上寻找代表节点,借助最小生成树、费马点、Steiner树的经典方法。为了均衡网络节点的剩余能量,在分区中选择能量最大的作为代表节点,并让能量大的节点分担更多传输任务。算法优化了所需中继节点的数量,且样本值保持在均值15%区间范围内。此问题可以看作SMT-MSP问题,算法在多项式时间内解决连通性修复,其性能通过仿真进行了验证。     

基于Steiner树的层次型无线传感器网络安全组播协议

在基于查询的无线传感器网络中,组播技术的应用可大幅减少传感器节点的能量消耗,延长节点寿命.针对大型无线传感器网络组播协议性能不高,且易遭受攻击等问题,提出了基于Steiner树的层次型无线传感器网络安全组播协议.该协议主要运用Steiner树与分簇网络的思想,将Steiner树的高效性与簇的高扩展性相结合,提高了无线传...     

新的基于MPH的时延约束Steiner树算法

为了在时延约束条件下进一步优化多播树代价并降低算法的复杂度,研究了时延受限的Steiner树问题。在DCMPH算法的基础上,通过改进节点的搜索路径,提出了一种新的基于MPH的时延约束Steiner树算法。该算法中每个目的节点通过最小代价路径加入当前多播树;若时延不满足要求,则通过合并最小时延树进而产生一个满足时延约束的最小代价多播树。仿真实验表明,新算法在性能、空间复杂度方面均优于DCMPH算法。     

基于布通率的FPGA装箱算法

提出一种基于FPGA布通率的装箱算法.选择连接因子最小的节点作为种子节点;采用基于布通率的启发式函数来选择最合适的逻辑单元(LE)装箱到可配置逻辑单元(CLB)内部.可以同时减少装箱后CLB之间的线网数和CLB引脚的外部使用率,从而减少布线所需的通道数.该算法和已有算法相比较,线网数和布线通道数都减少约30%. 算法的时间复杂度仍然是线性的.     

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是：首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。     

基于延迟合并嵌入的带障碍的时钟树布线算法

提出一种在带障碍情况下,基于延迟合并嵌入方法的时钟树构建算法,并在时钟树构造过程中引入了轨迹图以保证布线可以绕过障碍．该算法以已知障碍为布线约束,首先自底向上计算时钟树内部节点的可能位置,然后自顶向下确定每个节点的确切位置．实验结果表明,该算法能够正确、有效地实现有障碍存在时的时钟树布线,线长优化率超过7％．     

基于SOM特征映射图上引力场的故障模式识别

对聚类方法SOM特征映射图使用引力场进行区域划分,实现远程故障识别.首先由SOM得到输入模式的具有不同响应特性的聚类区域;对SOM特征图进行邻域相关性分析并使用阀值划分种子区域;以种子区域为引力源在SOM特征图中构造引力场,根据特征图中点沿在引力场所受力的方向运动而收殓到的种子区域进行区域划分,并以此进行模式识别.该方法不用考虑区域边界上点的分类问题且很容易扩展到多维空间.对12种典型飞机起落架故障进行远程检测仿真,取得了较满意的效果,较大地提高了正确识别率.     

基于人工力场的移动机器人路径规划研究

针对传统人工势场法中存在的一些局部极小点问题,文中提出了一种基于人工力场的移动机器人路径规划方法.该方法将机器人与目标的相对距离引入斥力函数,定义斥力的一个分力方向与障碍物的影响范围相切,另一个分力方向与引力方向一致,规定斥力向量与引力向量的内积始终大于等于零.这样,克服了传统人工势场法中存在的一些局部极小点问题,尤其是三个典型的、具有代表性的局部极小点问题.MATLAB仿真结果表明该人工力场法可以避开上述局部极小点,有效的规划出从起点到目标点的无碰路径.     

Compressible swirling flow through a significantly bent duct

The three-dimensional vortical flow of an inviscid compressible fluid through a bend in a slender duct is considered. The duct of simple cross-section gradually bends the flow through a substantial angle. The flow is motivated by industry and involves high speeds and short time intervals. The relative radius of curvature and the magnitude of the inertial forces are important factors here. Weakly and fully non-linear coupling between the streamwise and cross-sectional velocities is considered, and numerical results are derived for a duct of rectangular cross-section in each case, based on a fourth-order compact-differencing approach to solving the three-dimensional Euler equations. The governing equations are parabolic in the streamwise direction, enabling a forward-marching approach. The bend leads to significant growth in vorticity which mixes the streamwise velocity. The weakly non-linear study reveals a role for compressibility which is absent in the fully non-linear study when the cross-sectional area is constant. In both cases there is relatively little pressure loss, in contrast to viscous flows. Linear growth of the total streamwise vorticity in the bend is shown analytically to occur in keeping with the numerical solutions. Far downstream behaviours in finite bends and bends which continue indefinitely are investigated. The latter case leads to a more strongly non-linear flow structure far downstream due to continued evolution of the vorticity.     

Information transmittal, Newton’s law of gravitation, and tensor approach to general relativity

The special relativity considered in [A. Einstein, Zur Elektrodynamik der bewegte Körper. Ann. Physik, 17 (1905) 891-921] is based on the concept of finite speed of information transmittal by the available signals (rays of light). It is demonstrated that the same concept applies to Newton’s law of universal gravitation since the magnitude of distances between attracting masses can be physically defined (carried, accounted in acting forces of gravity) only by signals (physical processes) propagating at finite velocities. It follows that the speed of propagation of gravity is finite. The linear transformations of special relativity are applied to Newton’s law of gravitation to take into account the relativistic effects of information transmittal in a field of central forces of attraction. Relativistic representations of Newton’s law are obtained with respect to the center of gravity exposing illusory effects that appear at high velocities. It is verified that in atomic physics the effect of Newtonian gravitation on the motion of elementary particles at high velocities is negligible also in relativistic consideration. Computational methods are developed to measure the intensity of gravitation at a distant space-time location using a body that travels in space, emitting uniform pulses of light that are received by the observer at a different space-time location. It is demonstrated that the tensor approach to the general relativity and the united theory of space, time and gravitation in which the geometrical properties (metric) of the four-dimensional space-time continuum depend on the distribution of gravitating masses in space and their motion represent a transformed Lorentz invariant with a new type of inertia in the field of forces changing in space and time. Real physical processes evolve according to the forces represented in the tensor form by this invariant which is equivalent to the coordinate-free local invariant of relativistic dynamics that defines the field and the motion of a body whose velocities and accelerations can be measured by relativistic identification methods at a point, time and direction of interest. The results open new avenues for research in the general relativity and can be used for software development, field measurements and experimental studies in application to distant or fast moving systems.     

空间主反射镜轻量化及柔性支撑设计与分析

由于空间主反射镜的质量直接影响到发射成本,所以对其进行轻量化显得尤为重要.采用将理论与有限元计算软件相结合的方式对一主反射镜进行了轻量化,并讨论了主反射镜的支撑方式、支撑半径大小及支撑数目.在空间工作环境下,主反射镜由于受到温变及微重力的影响会发生镜面变形,影响成像质量.为了改善成像质量,进一步探讨了柔性支撑的设计应用及其对主反射镜镜面变形的影响.并通过在仿真环境中对刚性支撑和柔性支撑下主反射镜的镜面变形进行了计算和对比,验证了柔性支撑的使用在改善空间成像系统成像质量上的重要作用.     

Data gravitation based classification

Data gravitation based classification (DGC) is a novel data classification technique based on the concept of data gravitation. The basic principle of DGC algorithm is to classify data samples by comparing the data gravitation between the different data classes. In the DGC model, a kind of “force” called data gravitation between two data samples is computed. Data from the same class are combined as a result of gravitation. On the other hand, data gravitation between different data classes can be compared. A larger gravitation from a class means the data sample belongs to a particular class. One outstanding advantage of the DGC, in comparison with other classification algorithms is its simple classification principle with high performance. This makes the DGC algorithm much easier to be implemented. Feature selection plays an important role in classification problems and a novel feature selection algorithm is investigated based on the idea of DGC and weighted features. The proposed method is validated by using 12 well-known classification data sets from UCI machine learning repository. Experimental results illustrate that the proposed method is very efficient for data classification and feature selection.     

Microchannel miter bend effects on pressure equalization and vortex formation

Simulations have been carried out for water flow in a square microchannel with a miter bend. The simulation considered a pressure-driven flow in a channel-hydraulic diameter of 5 μm for series of Reynolds number (Re) range from 0.056 to 560, in order to investigate water flow at bends. The result shows formation of two vortices after the miter bend, which are more discernible above Re 5.6. The critical inlet velocity for the generation of vortex in this particular geometry occurs at 1 m/s. A simple energy mechanism is postulated to explain the vortex formation as well as core skew direction. The high pressure region at the outer wall before and after the bend is a major factor for vortex formation since the liquid needs to reduce the additional energy effected by the high pressure region. Navier–Stokes equation is utilized with a no slip boundary condition for a total microchannel centerline length of 795 μm which is sufficient to produce a laminar flow pattern at the outlet.     

基于虚拟目标的AGV局部路径规划研究

针对传统人工势场法对AGV(Automated Guided Vehicles)进行路径规划时,容易产生局部极小值的问题,提出了一种基于虚拟目标的人工势场路径规划方法.基本原理是AGV在行驶过程中,根据障碍的分布和目标的方位,动态地改变目标点的方位,即改变引力的方向,来避免引力和斥力的合力为零的情形发生,从而消除局部极小值产生的条件.设计了模糊逻辑控制器,用来预测合力为零的可能性.如果合力有可能为零,则计算为避免合力为零,目标方位的改变量.仿真结果表明,该方法能有效地解决局部极小值问题,为AGV规划出一条光滑的行驶路径.     

仿生机器鱼S形起动的控制与实现

给出一种仿生机器鱼S形起动的控制方法.结合北美狗鱼S形起动的形态特征及水动力学知识, 建立了多关节链式结构仿生机器鱼的S形起动模型.整个过程设计为两个阶段: 1)弯曲阶段:以转向速度最大化为目标.在鱼体S形变保证重心稳定平移的前提下, 增大较长转向力臂处的转向力矩,提高转向速度,使鱼体迅速转向目标方向. 2)伸展阶段:以增大前推力为目标.始终保持部分将要伸展的鱼体垂直前进方向,以L形滑动方式打开鱼体. 同时,为保证转向精度,采用模糊控制调节已展开鱼体关节的小角度转动,实时纠正鱼体展开所引起的游动方向偏离. 在S形起动末期,采用变幅值——频率的中枢模式发生器(Central pattern generator, CPG)实现向稳态游动方式的过渡:前期为保证游动方向及获取较大推进力,采用小幅值——高频率的CPG信号, 后期则进入大幅值——低频率的稳态游动.最终,采用四关节仿生机器鱼验证了该方法的有效性, 实现了峰值转速为318.08±9.20°/s、转向误差为1.03±0.48°的较好结果, 对提升水下游动机器人的机动性能具有指导意义.     

基于万有引力的遥感影像分类

本文从物理学中的万有引力得到启发,提出了“引力分类法”。即假设任意样本与待定点存在着万有引力,根据引力的大小使待定点属于不同的类,从而达到分类的目的。并且通过对武汉城区的TM3、4、5波段遥感影像数据进行监督分类的试验,初步证明了该分类方法的可行性。