An effective algorithm for delay-constrained dynamic multicasting

With the development of multimedia group applications, the construction of multicast routing tree satisfying Quality of Service (QoS) is more important. In many multicast applications, it is required that the network supports dynamic multicast, which the membership of the multicast group changes with the time. In this paper an effective heuristic algorithm is proposed for dynamic multicast routing with delay-constrained. Aims of this proposed algorithm is to guarantee that: (1) the cost of multicast tree is as small as possible at each node addition/removal event, (2) all the maximal path delay is meet a fixed delay-constrained, (3) minimize perturbation to an existing tree. The proposed algorithm is based on ‘damage’ and ‘usefulness’ concept, and a Balancing Factor (BF) is provided to judge whether or not to arrange a region of tree. Mutation operation in Genetic Algorithm (GA) is also employed to find an attached node in tree for a dynamic adding node. Simulation shows that our algorithm performs well than those static heuristic algorithms in term of cost especially.     

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

无资源管理自协调网格计算模型的研究

提出了一个无资源管理自协调网格计算模型,描述了该模型的体系结构、信息管理和递归资源调度机制。在该模型中,不存在任何管理节点,所有节点功能相同,采用改进的eager scheduling来屏蔽环境的动态性。对该模型的性能进行了初步分析,仿真结果表明,该模型能充分利用Internet上空闲的计算资源,用以解决大规模分布式应用问题。     

一种简化DFT的滑窗迭代算法在电力谐波检测中的应用

文章介绍了一种在有源滤波控制器应用中基于简化离散傅立叶变换的谐波电流检测技术的设计和应用。为检测由非线性负载产生的谐波电流成分,运算过程中应用了滑窗迭代算法,它能有效地提高系统的实时性、目标跟随特性和抗干扰性,并且具有计算量小、容易工程实现的特点。该算法的有效性通过实验和仿真结果得到了证明。     

一种语义网服务发现过程排序算法

针对语义网服务发现过程的排序问题,提出一种新的语义网服务排序算法。采用重写思想的方法对候选语义网服务进行排序。实验结果证明,该算法运行效率较高、耗时较少,可有效辅助用户的选择和静态语义网服务平台的自动化计算。     

A hybrid of electromagnetism-like mechanism and back-propagation algorithms for recurrent neural fuzzy systems design

This article introduces a novel hybrid evolutionary algorithm for recurrent fuzzy neural systems design in applications of nonlinear systems. The hybrid learning algorithm, IEMBP-improved electromagnetism-like (EM) with back-propagation (BP) technique, combines the advantages of EM and BP algorithms which provides high-speed convergence, higher accuracy and less computational complexity (computation time in seconds). In addition, the IEMBP needs only a small population to outperform the standard EM that uses a larger population. For a recurrent neural fuzzy system, IEMBP simulates the ‘attraction’ and ‘repulsion’ of charged particles by considering each neural system parameters as a charged particle. The EM algorithm is modified in such a way that the competition selection is adopted and the random neighbourhood local search is replaced by BP without evaluations. Thus, the IEMBP algorithm combines the advantages of multi-point search, global optimisation and faster convergence. Finally, several illustration examples for nonlinear systems are shown to demonstrate the performance and effectiveness of IEMBP.     

Design of a high performance architecture for real-time enhancement of video stream captured in extremely low lighting environment

A high performance digital architecture for the implementation of a non-linear image enhancement technique is proposed in this paper. The image enhancement is based on a luminance dependent non-linear enhancement algorithm which achieves simultaneous dynamic range compression, colour consistency and lightness rendition. The algorithm provides better colour fidelity, enhances less noise, prevents the unwanted luminance drop at the uniform luminance areas, keeps the ‘bright’ background unaffected, and enhances the ‘dark’ objects in ‘bright’ background. The algorithm contains a large number of complex computations and thus it requires specialized hardware implementation for real-time applications. Systolic, pipelined and parallel design techniques are utilized effectively in the proposed FPGA-based architectural design to achieve real-time performance. Estimation techniques are also utilized in the hardware algorithmic design to achieve faster, simpler and more efficient architecture. The video enhancement system is implemented using Xilinx’s multimedia development board that contains a VirtexII-X2000 FPGA and it is capable of processing approximately 67 Mega-pixels (Mpixels) per second.     

On developing theory of reservoir computing for sensing applications: the state weaving environment echo tracker (SWEET) algorithm

As a paradigm of computation, reservoir computing has gained an enormous momentum. In principle, any sufficiently complex dynamical system equipped with a readout layer can be used for any computation. This can be achieved by only adjusting the readout layer. Owning to this inherent flexibility of implementation, new applications of reservoir computing are being reported at a constant rate. However, relatively few studies focus on sensing, and in the ones that do, the reservoir is often exploited in a somewhat passive manner. The reservoir is used to post-process the signal from sensing elements that are placed separately, and the reservoir could be replaced by other information processing system without loss of functionality of the sensor (‘reservoir computing and sensing’). An entirely different novel class of sensing approaches is being suggested, to be referred to as ‘reservoir computing for sensing’, where the reservoir plays a central role. In the State Weaving Environment Echo Tracker (SWEET) sensing approach, the reservoir functions as the sensing element if the dynamical states of the reservoir and the environment one wishes to analyze are strongly interwoven. Some distinct characteristics of reservoir computing (in particular the separability and the echo state properties) are carefully exploited to achieve sensing functionality. The SWEET approach is formulated both as a generic device setup, and as an abstract mathematical algorithm. This algorithmic template could be used to develop a theory (or a class of theories) of ‘reservoir computing for sensing’, which could provide guidelines for engineering novel sensing applications. It could also provide ideas for a creative recycling of the existing sensing solutions. For example, the Horizon 2020 project RECORD-IT (Reservoir Computing with Real-time Data for future IT) exploits the SWEET sensing algorithm for ion detection. Accordingly, the terms SWEET sensing algorithm and the RECORD-IT sensing algorithm can be used interchangeably.     

生成矩形毛坯最优两段排样方式的确定型算法

排样价值、切割工艺和计算时间是排样问题主要考虑的3个因素.文中提出一个新的基于排样模式的确定型排样算法——同质块两段排样算法,此算法适合剪冲下料工艺,在实现工艺简化的同时提高了排样价值时间比.首先通过动态规划算法生成最优同质块,然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式,最后选择两个段生成最优的两段排样方式.通过3组经典测题对该文算法进行了测试,将算法与4种著名算法进行了比较.实验结果表明,该文算法的优化结果好于以上4种著名算法,有效地提高了板材利用率,并且计算时间合理.     

非精确实时计算的方面框架及编织测试

针对应用面向方面技术提出了一个非精确实时计算的框架。该框架允许开发人员将可选任务定义和设计为方面,基于运行时可用资源动态编织可选的方面。通过一系列编织与解编织的时间测试,找到影响编织与解编织时间的两个主要因素——通知和目标方法的数目。测试结果表明,在实时系统中动态编织技术可实现非精确计算的可行性,且无需引入不可预测性。     

Exploiting the untapped potential of mobile distributed computing via approximation

Mobile computing is one of the largest untapped reservoirs in today’s pervasive computing world as it has the potential to enable a variety of in-situ, real-time applications. Yet, this computing paradigm suffers when the available resources–such as energy in the network, CPU cycles, memory, I/O data rate–are limited. In this article, the new paradigm of approximate computing is proposed to harness such potential and to enable real-time computation-intensive mobile applications in resource-limited and uncertain environments. A reduction in time and energy consumed by an application is obtained via approximate computing by decreasing the amount of computation needed; such improvement, however, comes with the potential loss in accuracy. Hence, a Mobile Distributed Computing framework, is introduced to determine offline the ‘approximable’ tasks in an application and a light-weight online algorithm is devised to select the approximate version of the tasks in an application during run time. The effectiveness of the proposed approach is validated through extensive simulation and testbed experiments by comparing approximate versus exact-computation performance.     

基于Beowulf机群中改进粒子滤波的3D人体运动跟踪

针对标准的粒子滤波算法在视频三维人体运动跟踪中存在的计算量巨大、粒子退化、跟踪失效而无法同时满足跟踪精度和跟踪实时性要求的问题,提出了基于Beowulf机群中改进的粒子滤波新算法。新算法通过三维人体模型参数的自动初始化、粒子数目和模板的调整来实现跟踪失效的自动恢复,基于任务动态分配策略、低开销通信策略设计的Beowulf机群中的迁移式粒子滤波并行算法克服了粒子退化问题和提高了计算速度。实验结果显示：新方法有效地减轻了粒子退化和跟踪失效问题,降低了计算时间,提高了跟踪精度,能够同时满足三维人体运动跟踪精度和实时性的要求。     

A mean approximation based bidimensional empirical mode decomposition with application to image fusion

Empirical mode decomposition (EMD) is an adaptive decomposition method, which is widely used in time-frequency analysis. As a bidimensional extension of EMD, bidimensional empirical mode decomposition (BEMD) presents many useful applications in image processing and computer vision. In this paper, we define the mean points in BEMD ‘sifting’ processing as centroid point of neighbour extrema points in Delaunay triangulation and propose using mean approximation instead of envelope mean in ‘sifting’. The proposed method improves the decomposition result and reduces average computation time of ‘sifting’ processing. Furthermore, a BEMD-based image fusion approach is presented in this paper. Experimental results show our method can achieve more orthogonal and physical meaningful components and more effective result in image fusion application.     

Recognition of human actions using CNN-GWO: a novel modeling of CNN for enhancement of classification performance

Recognizing human actions from unconstrained videos turns to be a major challenging task in computer visualization approaches due to decreased accuracy in the feature classification performance. Therefore to improve the classification performance it is essential to minimize the ‘classification’ errors. Here, in this work, we propose a hybrid CNN-GWO approach for the recognition of human actions from the unconstrained videos. The weight initializations for the proposed deep Convolutional Neural Network (CNN) classifiers highly depend on the generated solutions of GWO (Grey Wolf Optimization) algorithm, which in turn minimizes the ‘classification’ errors. The action bank and local spatio-temporal features are generated for a video and fed into the ‘CNN’ classifiers. The ‘CNN’ classifiers are trained by a gradient descent algorithm to detect a ‘local minimum’ during the fitness computation of GWO ‘search agents’. The GWO algorithms ‘global search’ capability as well as the gradient descent algorithms ‘local search’ capabilities are subjected for the identification of a solution which is nearer to the global optimum. Finally, the classification performance can be further enhanced by fusing the classifiers evidences produced by the GWO algorithm. The proposed classification frameworks efficiency for the recognition of human actions is evaluated with the help of four achievable action recognition datasets namely HMDB51, UCF50, Olympic Sports and Virat Release 2.0. The experimental validation of our proposed approach shows better achievable results on the recognition of human actions with 99.9% recognition accuracy.     

Global data and control in multicomputers: Operating system primitives and experimentation with a parallel branch-and-bound algorithm

The static distribution of work among tasks is not possible in many parallel applications. Therefore, it is essential to implement convenient and efficient abstractions for ‘work sharing’ on multicomputers. This paper compares the utility of two operating system facilities for the implementation of such ‘work sharing’: (1) a system for the migration of processes from heavily to less loaded processors and (2) a more general OS construct for the implementation of arbitrary distributed objects. Both were implemented as extensions to the Intel iPSC/1 operating system on a 32-node hypercube. Their experimental evaluation is based on a parallel implementation of a branch-and-bound algorithm. Two sets of results are attained. First, the necessity of the constructs for dynamic work sharing is demonstrated for applications with dynamic data domains, such as parallel branch-and-bound algorithms. This is followed by measurements that demonstrate the acceptable cost of process migration for a specific parallel branch-and-bound algorithm. These measurements are then compared with results attained with the construct for the implementation of distributed objects. Second, when using branch-and-bound to solve the Travelling Salesperson Problem (TSP), evaluation of the resulting parallel TSP program shows that some analytical and simulation results attained in past, published work may not hold.     

Segmentation using contrast and homogeneity measures

The present work describes an algorithm for automatic image segmentation using a ‘homogeneity’ measure and a ‘contrast’ measure defined on the co-occurrence matrix of the image. The measure of contrast involves the concept of logarithmic response (adaptibility with background intensity) of the human visual system (HVS). A merging algorithm is also introduced in order to remove the undesirable thresholds.Effectiveness of the algorithm and the comparison of its performance with the existing ones are demonstrated for a set of images.     

The OPIT system II. Job control and scheduling for large applications programs

A strategy is described for a controlling algorithm (‘the job’) to schedule and supply many data sets (‘problems’) to a large, long-running applications program. The algorithm also controls very closely the run time environment of each problem and provides protection against breakdown of the computer or its operating system. The principles described are applicable on any computer with a sufficiently flexible operating system. The particular example used here is the running of the OPIT Program (see paper I page 123) on an ICL 1900 Computer with the GEORGE 3 operating system.     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

Profitability Edge by Dynamic Back Testing Optimal Period Selection for Technical Parameters Optimization,in Trading Systems with Forecasting

Back testing process is widely used today in forecasting experiments tests. This method is to calculate the profitability of a trading system, applied to specific past period. The data which are used, correspond to that specific past period and are called “historical data” or “training data”. There is a plethora of trading systems, which include technical indicators, trend following indicators, oscillators, control indicators of price level, etc. It is common nowadays for calculations of technical indicator values to be used along with the prices of securities or shares, as training data in fuzzy, hybrid and support vector machine/regression (SVM/SVR) systems. Whether the data are used in fuzzy systems, or for SVM and SVR systems training, the historical data period selection on most occasions is devoid of validation (In this research we designate historical data as training data). We substantiate that such an expert trading system, has a profitability edge—with regard to future transactions—over currently applied trading strategies that merely implement parameters’ optimization. Thus not profitable trading systems can be turned into profitable. To that end, first and foremost, an optimal historical data period must be determined, secondarily a parameters optimization computation must be completed and finally the right conditions of parameters must be applied for optimal parameters’ selection. In this new approach, we develop an integrated dynamic computation algorithm, called the “d-BackTest PS Method”, for selection of optimal historical data period, periodically. In addition, we test conditions of parameters and values via back-testing, using multi agent technology, integrated in an automated trading expert system based on Moving Average Convergence Divergence (MACD) technical indicator. This dynamic computation algorithm can be used in Technical indicators, Fuzzy, SVR and SVM and hybrid forecasting systems. The outcome crystalizes in an autonomous intelligent trading system.