P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

基于增强稀疏性特征选择的网络图像标注

面对网络图像的爆炸性增长,网络图像标注成为近年来一个热点研究内容,稀疏特征选择在提升网络图像标注效率和性能方面发挥着重要的作用.提出了一种增强稀疏性特征选择算法,即,基于l_2,1/2矩阵范数和共享子空间的半监督稀疏特征选择算法(semi-supervised sparse feature selection based on l_2,1/2-matix norm with shared subspace learning,简称SFSLS)进行网络图像标注.在SFSLS算法中,应用l_2,1/2矩阵范数来选取最稀疏和最具判别性的特征,通过共享子空间学习,考虑不同特征之间的关联信息.另外,基于图拉普拉斯的半监督学习,使SFSLS算法同时利用了有标签数据和无标签数据.设计了一种有效的迭代算法来最优化目标函数.SFSLS算法与其他稀疏特征选择算法在两个大规模网络图像数据库上进行了比较,结果表明,SFSLS算法更适合于大规模网络图像的标注.     

Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略

针对无线传感器网络中传输时延长、传输冲突大和吞吐量低等问题,提出了一种在Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略.该策略动态地建立k元n立方体拓扑结构,使用优化的静态信道分配算法提高节点的吞吐量,使用维序寻径的路由算法减少传输冲突.该方法适用于网络节点稠密、节点相互之间通信冲突大的情况,并且在单跳和多跳的网络环境下均适用.实验结果表明,基于k元n立方体这一拓扑结构的信道分配和路由策略与传统方法相比,有效地减少了端到端时延,降低了网络冲突,减少了节点能量消耗,延长了网络寿命,提高了网络吞吐量.     

混合H2/H∞鲁棒控制器设计

在状态空间描述下,定义了混合H₂/H_∞控制的完整信息、完整控制、干扰顺馈、输出估计这4种典型情况.在二次稳定意义上,讨论了混合H₂/H_∞的性能指标,及这4种典型情况的混合H₂/H_∞线性反馈控制器设计,给出了充分必要条件.在典型情况分析的基础上,研究一般意义上的混合H₂/H_∞反馈控制器设计.H₂和H_∞的干扰输入阵及性能评价函数各不相同时的混合H₂/H_∞反馈控制器,与H₂和H_∞控制器设计相似,归结为解两个Riccati方程.但这两个Riccati方程含有参数,最优解要通过搜索这两个参数得到.结果包含了单纯的H₂和H_∞设计,可看作是H₂,H_∞和混合H₂/H_∞的统一设计方法.最后通过一个简单的例子,说明了控制器设计方法的可行性.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

时延网络化控制系统的H2/H∞混合控制

针对存在多步随机传输时延的网络化控制系统模型 ,研究了其随机稳定性及H₂/H_∞混合控制问题 .在一定的系统通信控制模式下 ,网络传输时延可以建模为一个马尔可夫随机过程 ,通过增广系统状态的方法将原系统转化为一个具有随机跳变系数的离散系统 ,同时通过建立随机跳变Lyapunov函数 ,构建了满足系统随机稳定的H_∞次优和H₂/H_∞混合控制状态反馈控制器 .该控制器可通过求解一组耦合的矩阵不等式而得 .     

主动悬架H2/ 广义H2输出反馈控制

本文提出了一种主动悬架控制的H₂ /广义H₂ 输出反馈控制方法. 依照国际标准ISO2631.3选择垂直和俯仰加速度的频率加权. 根据路面干扰谱特征, 选用H₂ 范数作为乘坐舒适性的指标, 广义H₂ 范数描述轮胎接地性等时域约束要求. 在多目标控制框架下, 将输出反馈控制器的设计转化为求解LMI优化问题. 基于半车模型, 给出了输出反馈主动悬架系统的频域分析和时域仿真.     

混合H2/H∞参数辨识

研究了混合H₂/H_∞参数辨识问题.将混合H₂/H_∞估计方法应用到系统参数辨识中,给出了混合H₂/H_∞参数辨识算法.所得的算法不仅能满足规定的鲁棒性能,且为最小二乘(LS)参数估计误差判据提供了一个最优上界.结果表明:提高辨识的鲁棒性,需要牺牲辨识的精度作为代价.最后,仿真结果也验证了该方法的有效性.     

一类约化梯阵的RaRb表示

本文首先阐明线性R_aR_b变换之间的关系，并提出了算法MR_ab，再引用标准线性R_aR_b变换，证明了R_aR_b变换与算法MR_ab求解方程组的能力是等价的．然后讨论MR_ab与算法ALT之间的关系，进而说明受ALT攻击的那些有限自动机包含     

Edge-Cut Bounds on Network Coding Rates

Active networks are network architectures with processors that are capable of executing code carried by the packets passing through them. A critical network management concern is the optimization of such networks and tight bounds on their performance serve as useful design benchmarks. A new bound on communication rates is developed that applies to network coding, which is a promising active network application that has processors transmit packets that are general functions, for example a bit-wise XOR, of selected received packets. The bound generalizes an edge-cut bound on routing rates by progressively removing edges from the network graph and checking whether certain strengthened d-separation conditions are satisfied. The bound improves on the cut-set bound and its efficacy is demonstrated by showing that routing is rate-optimal for some commonly cited examples in the networking literature.     

On the gap between H2 and entropy performance measures in H∞ control design

Recent papers have considered the problem of minimizing an entropy functional subject to an H_∞ performance constraint. Since the entropy is an upper bound for the H₂ cost, there remains a gap between entropy minimization and H₂ minimization. In this paper we consider a generalized cost functional involving both H₂ and entropy aspects. This approach thus provides a means for optimizing H₂ performance within H_∞ control design.     

事件驱动传感器网络中基于数据聚合的自适应路由算法

为优化事件驱动传感器网络总能耗,提出一个基于数据聚合的自适应路由算法,它能够实现低控制开销的事件域节点分布式成簇,计算并借助于路由汇聚中心,建立一棵基于事件的近似Steiner树,有效减少网内数据分组与控制分组的传输量.理论分析与实验表明,该算法的路由结构建立与维护开销较少,能优化数据聚合效率,实现高能效的数据收集,提升网络性能.     

Robust L 2 − L ∞ consensus control for uncertain high-order multi-agent systems with time-delay

This article studies that the robust consensus problem for high-order multi-agent systems with time-delay, which are subjected to external disturbances and communication uncertainties. An approach based on the weighting matrix is introduced to meet the requirement that the peak value of controlled output is often required into a certain range. Then, a dynamic model of high-order multi-agent systems is established. Using a feedback controller and interactions from the neighbours including uncertainties, a linear control protocol is proposed for the systems with networks under fixed or switching topologies. Sufficient conditions in terms of linear matrix inequalities are derived to make all the agents reach robust consensus with the prescribed L ₂???L _∞ performance. A numerical simulation is provided to demonstrate the effectiveness of the proposed protocol.     

A linear-time algorithm for linearL1 approximation of points

In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL ₁ norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n ³) naive algorithm can be easily obtained based on some simple characteristics of an optimumL ₁ solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL ₁ approximation of many points in practice. The complexity ofL ₁ linear approximation of a piecewise linear function is also touched upon.     

Robust H 2 control of Markovian jump systems with uncertain switching probabilities

This article deals with the robust H ₂ control problem for a class of Markovian jump linear systems with uncertain switching probabilities. The uncertainties under consideration appear both in the system parameters and in the mode transition rates. First, a new criterion based on linear matrix inequalities is established for checking the robust H ₂ performance of the uncertain system. Then, a sufficient condition for the existence of the state-feedback controllers is established such that the closed-loop system is quadratically mean square stable and has a certain level of robust H ₂ performance in terms of linear matrix inequalities with equality constraints. A globally convergent algorithm is also presented to construct such controllers effectively. Finally, an illustrative numerical example is used to demonstrate the developed theory.     

New approaches to robust l2?l∞ and H∞ filtering for uncertain discrete-time systemsfiltering for uncertain discrete-time systems

The problems of robust l ₂−l _∞ and H _∞ filtering for discrete-time systems with parameter uncertainty residing in a polytope are investigated in this paper. The filtering strategies are based on new robust performance criteria derived from a new result of parameter-dependent Lyapunov stability condition, which exhibit less conservativeness than previous results in the quadratic framework. The designed filters guaranteeing a prescribed l ₂−l _∞ or H _∞ noise attenuation level can be obtained from the solution of convex optimization problems, which can be solved via efficient interior point methods. Numerical examples have shown that the filter design procedures proposed in this paper are much less conservative than earlier results.     

Fast and scalable conflict detection for packet classifiers

Packet filters provide rules for classifying packets based on header fields. High speed packet classification has received much study. However, the twin problems of fast updates and fast conflict detection have not received much attention. A conflict occurs when two classifiers overlap, potentially creating ambiguity for packets that match both filters. For example, if Rule 1 specifies that all packets going to CNN be rate controlled and Rule 2 specifies that all packets coming from Walmart be given high priority, the rules conflict for traffic from Walmart to CNN. There has been prior work on efficient conflict detection for two-dimensional classifiers. However, the best known algorithm for conflict detection for general classifiers is the naive O(N²) algorithm of comparing each pair of rules for a conflict. In this paper, we describe an efficient and scalable conflict detection algorithm for the general case that is significantly faster. For example, for a database of 20 000 rules, our algorithm is 40 times faster than the naive implementation. Even without considering conflicts, our algorithm also provides a packet classifier with fast updates and fast lookups that can be used for stateful packet filtering.