集群系统中实现软实时服务机制的研究与评估

研究了集群架构服务器的三种实时调度策略,即集中式策略、分布式策略和主动型全分布策略。与调度功能主要集中在前端机的集中式策略比较,分布式策略将调度功能部分离散至后端节点,改善了系统的可扩展性。而主动型全分布式调度则进一步实现了调度分派功能的完全离散化,通过后端机的主动拉取事件和频率调控实现了负载平衡的自调节,极大地改善了系统的扩展性和服务效率。通过试验研究和试验表明,这三种都有效地降低了集群的响应服务请求的时间,还保证了系统的输出最大化。     

对象依赖集合性质的研究

在复杂对象模式的规范化设计中,对象间的语义关系起了重要作用。然而,目前还没有关系的研究报告,讨论了对象依赖集合的一些性质,首先概括了基本概念和性质;然后给出并证明获取一个OD集合所有关键字的JINGSI算法;最后证明要作为复杂对象模式规范化设计的MIMI算法输入的OD集合的特性,并基于此改进复杂对象模式规范化设计。     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

限制树宽图上的有界聚类

有界聚类问题源于II3M研究院开发的一个分布式流处理系统,即S系统。问题的输入是一个点赋权和边赋权的无向图,并指定若干个称为终端的顶点。称顶点集合的一个子集为一个子类。子类中所有顶点的权和加上该子类边界上所有边的权和称为该子类的费用。有界聚类问题是要得到所有顶点的一个聚类,要求每个子类的费用不超过给定预算召,每个子类至多包含一个终端,并使得所有子类的总费用最小。对于限制树宽图上的有界聚类问题,给出了拟多项式时间精确算法。利用取整的技巧对该算法进行修正,可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(1+ε)B,:是任意小的正数。如果进一步要求每个子类恰好包含一个终端,则所给算法可在多项式时间之内得到(1+ε)-近似解,其中每个子类的费用不超过(2+ε)B。     

基于矩阵谱分析的文本聚类集成算法

聚类集成技术可有效提高单聚类算法的精度和稳定性,其中的关键问题是如何根据不同的聚类成员组合为更好的聚类结果.文中引入谱聚类算法解决文本聚类集成问题,设计基于正则化拉普拉斯矩阵的谱算法(NLM-SA).该算法基于代数变换,通过求解小规模矩阵的特征值和特征向量间接获得正则化拉普拉斯矩阵的特征向量,并用于后续聚类.进一步研究谱聚类算法的关键思想,设计基于超边转移概率矩阵的谱算法(HTMSA).该算法通过求解超边的低维嵌入间接获得文本的低维嵌入,并用于后续K均值算法.在TREC和Reuters文本集上的实验结果验证NLMSA和HTMSA的有效性,它们都获得比其它基于图划分的集成算法更为优越的结果.HTMSA获得的结果比NLMSA略差,而时间和空间需求则比NLMSA低得多.     

Signal shaper with a distributed delay: Spectral analysis and design

Input shapers with time delays have proved useful in many applications related to controls for various oscillatory devices, for example flexible manipulators and cranes. In the paper, a novel approach for designing a zero-vibration signal shaper based on equally distributed delay is proposed. The parameter assessment of the shaper is based on the spectral approach. Various characteristics of the shaper are analyzed and compared with the classical zero-vibration shaper with a lumped delay. The analysis shows that the novel shaper is a slower, but more robust alternative to the classical shaper. Besides, the discrete implementation of the shaper is proposed and tested. It includes zero placement based parameter adjustment with the objective to preserve full compensation of the oscillatory mode by the discrete algorithm.     

Efficient approximation algorithms for the routing open shop problem

We consider the routing open shop problem being a generalization of two classical discrete optimization problems: the open shop scheduling problem and the metric traveling salesman problem. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule with the minimum makespan. The problem is NP-hard even on the two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.     

Optimal radio resources and transmission formats assignment in OFDMA systems

The problem of assigning radio resources and transmission formats to users in the downlink of an OFDMA network is addressed. In particular, a single cell environment with a realistic interference model and a margin adaptive approach is considered, i.e., the aim is of minimizing the total transmission power while maintaining a certain given rate for each user. The computational complexity issues of the problem are discussed, and an approximation analysis is presented. Heuristic approaches, based on rounding techniques and graph models, are also proposed. Computational experiences show that, in a comparison with a commercial state-of-the-art optimization solver and with alternatives from the literature, the proposed algorithms are effective in terms of solution quality and CPU times.     

Stability preservation analysis in direct discretization of fractional order transfer functions

In this paper, a class of the direct methods for discretization of fractional order transfer functions is studied in the sense of stability preservation. The stability boundary curve is exactly determined for these discretization methods. Having this boundary helps us to recognize whether the original system and its discretized model are the same in the sense of stability. Finally, some illustrative examples are presented to evaluate achievements of the paper.     

Minimum cost flows with minimum quantities

We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NP-complete even on series-parallel graphs. We start by showing that the problem is strongly NP-complete and cannot be approximated in polynomial time (unless P=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs.