基于三维胞元空间的MA双向并行路由算法

针对传统移动代理(MA)在监测无线传感器网络(WSNs)的感兴趣信息时产生的延迟较大和能耗较多问题,提出了基于三维胞元空间的MA双向并行(3D-BPMA)路由算法.3D-BPMA将MA与传统的客户/服务器(c/S)模式相结合,在胞元内利用C/S模式搜集信息,在单层胞元系统和路由器与路由器之间采用MA双向并行的策略进行传输.仿真结果表明:3D-BPMA与LCF,DSG-MIP算法相比减少了平均响应时间和网络平均能耗,提高了MA发送率.     

An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods simultaneously. The Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD) differs from the VRPSPD in that the customers may have either pickup or delivery demand. However, the solution approaches proposed for the VRPSPD can be directly applied to the VRPMPD. In this study, an adaptive local search solution approach is developed for both the VRPSPD and the VRPMPD, which hybridizes a Simulated Annealing inspired algorithm with Variable Neighborhood Descent. The algorithm uses an adaptive threshold function that makes the algorithm self-tuning. The proposed approach is tested on well-known VRPSPD and VRPMPD benchmark instances derived from the literature. The computational results indicate that the proposed algorithm is effective in solving the problems in reasonable computation time.     

Time-series clustering – A decade review

Clustering is a solution for classifying enormous data when there is not any early knowledge about classes. With emerging new concepts like cloud computing and big data and their vast applications in recent years, research works have been increased on unsupervised solutions like clustering algorithms to extract knowledge from this avalanche of data. Clustering time-series data has been used in diverse scientific areas to discover patterns which empower data analysts to extract valuable information from complex and massive datasets. In case of huge datasets, using supervised classification solutions is almost impossible, while clustering can solve this problem using un-supervised approaches. In this research work, the focus is on time-series data, which is one of the popular data types in clustering problems and is broadly used from gene expression data in biology to stock market analysis in finance. This review will expose four main components of time-series clustering and is aimed to represent an updated investigation on the trend of improvements in efficiency, quality and complexity of clustering time-series approaches during the last decade and enlighten new paths for future works.     

一种自动布线方法：多级线探索法

本文介绍了一种在微机上实现的印制板自动布线方法──多级线探索法及其编程方法。这种方法是基于完备布线算法的概念，通过分析李氏算法和传统线探索法的不足之处而得到的。虽然它也是一种线探索法，但有较传统线探索法更强的探索能力，不需要结合李氏算法而能单独完成布线任务，是一种较理想的算法，通过实验获得了较为满意的效果。     

An Effective Software Pipelining Algorithm for Clustered Embedded VLIW Processors

This paper proposes a software pipelining framework, CALiBeR (ClusterAware Load Balancing Retiming Algorithm), suitable for compilers targetingclustered embedded VLIW processors. CALiBeR can be used by embedded systemdesigners to explore different code optimization alternatives, that is, high-qualitycustomized retiming solutions for desired throughput and program memory sizerequirements, while minimizing register pressure. An extensive set of experimentalresults is presented, demonstrating that our algorithm compares favorablywith one of the best state-of-the-art algorithms, achieving up to 50% improvementin performance and up to 47% improvement in register requirements. In orderto empirically assess the effectiveness of clustering for high ILP applications,additional experiments are presented contrasting the performance achievedby software pipelined kernels executing on clustered and on centralized machines.     

一种支持QoS的拓扑自适应动态组播路由算法

YAM、QoSMIC、DSDMR等一类支持QoS的动态组播路由算法允许组播成员动态地加入和离开，同时为接收方提供多个可选择的组播接入路径，以满足不同应用的QoS需求。但这些算法普遍存在控制信令开销大和结点加入时延长，可扩展性不好等问题。本文在分析这些算法的基础上，提出改进的支持QoS的动态组播路由算法，即拓扑自适应动态组播路由（Topology Adaptive Dynamic Multicast Routing，TADMR）算法。该算法避免了以往算法中大部分盲目的路径搜索，并使结点加入时延不再受限于固定的等待时钟，而与网络拓扑相自适应。性能分析和仿真结果表明，该算法具有较低的控制信令开销和结点加入时延，适用于各种网络规模和群组规模，具有良好的可扩展性。     

FindOut: Finding Outliers in Very Large Datasets

Finding the rare instances or the outliers is important in many KDD (knowledge discovery and data-mining) applications, such as detecting credit card fraud or finding irregularities in gene expressions. Signal-processing techniques have been introduced to transform images for enhancement, filtering, restoration, analysis, and reconstruction. In this paper, we present a new method in which we apply signal-processing techniques to solve important problems in data mining. In particular, we introduce a novel deviation (or outlier) detection approach, termed FindOut, based on wavelet transform. The main idea in FindOut is to remove the clusters from the original data and then identify the outliers. Although previous research showed that such techniques may not be effective because of the nature of the clustering, FindOut can successfully identify outliers from large datasets. Experimental results on very large datasets are presented which show the efficiency and effectiveness of the proposed approach. Received 7 September 2000 / Revised 2 February 2001 / Accepted in revised form 31 May 2001 Correspondence and offprint requests to: A. Zhang, Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA. Email: azhang@cse.buffalo.eduau     

自动交换光网络中的信令与路由

自动交换光网络的概念一经提出即受到业界的广泛关注，运营商尤其对其寄予了厚望。本文首先概要地介绍了ASON的优点，然后重点论述了ASON的信令与路由功能，包括对它们的要求以及标准化工作。     

Optimal algorithms for adjacent side routing

We consider the switchbox routing problem of two-terminal nets in the case when all thek nets lie on two adjacent sides of the rectangle. Our routing model is the standard two-layer model. We develop an optimal algorithm that routes all the nets whenever a routing exists. The routing obtained uses the fewest possible number of vias. A more general version of this problem (adjacent staircase) is also optimally solved.This research was supported in part by NSA Contract No. MDA-904-85H-0015, NSF Grant No. DCR-86-00378, and by NSF Engineering Research Centers Program NSFD CDR 88003012.