Loading...
  • 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Current Issue

    • 论文
      Task optimization scheduling to inter-connection network
      on embedded system with chip multi-processors      
      DU Jiayi,LI Renfa,DU Linna
      2016, 38(04): 617-623. doi:
      Abstract ( 159 )   PDF (516KB) ( 368 )     

      Communication between cores is significant for the performance of embedded system of chip multiprocessors (CMPs). It is a promising solution to design and customize the interconnection network based on a particular application. We propose a task optimization scheduling for communication connection algorithm (TOCCA)when connection is of the type of P2P. The interconnected network has minimal P2P connections and satisfies the communication demands, while not increasing the makespan. Besides, to help deploy the network, we present a deterministic algorithm of data transition (DDT) and a construction algorithm of interconnection network (CICN). Experimental results show that the TOCCA can dramatically reduce the number of P2P connections in comparison with the HLFET algorithm.

      A cloud servitization method for job shop scheduling
      capability of MES in big data environment         
      XU Dieshi,LIU Shenghui,MA Chao,ZHANG Shuli,ZHANG Hongguo
      2016, 38(04): 624-633. doi:
      Abstract ( 151 )   PDF (1961KB) ( 436 )     

      Cloud manufacturing brings new opportunities for manufacturing enterprises, but in the meantime it also brings new challenges to the design and implementation of manufacturing execution system (MES). To solve the issues of "job shop scheduling" in single and small batch MES, firstly we design a closedloop architecture that is from static scheduling to realtime monitoring and active perception of manufacturing execution, then to intelligent response of abnormal events, and finally, to dynamic scheduling. Then for solving three sub issues, i.e. realtime acquisition of exception information and discovery of abnormal events, intelligent processing of abnormal events and servitization of job shop scheduling optimization algorithms, we analyze them and provide technical solutions. Finally, taking Harbin Electrical Machinery Plant as a case, and combining IEC/ISO 62264 standard, big data analysis and mining method, and the cloud computing method consisting of virtualization, servitization and SOA together,  we develop an integrated job shop scheduling optimization system of single and small batch MES, and the aforementioned theory and method are validated.

      State of the art and future research of
      a SAT problem solver on FPGA  
      MA Kefan,XIAO Liquan,ZHANG Jianmin,LI Tiejun
      2016, 38(04): 634-639. doi:
      Abstract ( 177 )   PDF (585KB) ( 299 )     

      As the first proved NPcomplete problem,Boolean satisfiability problem (SAT) is a key problem in computer theory and applications, and has crucial significance in both theoretical research and practical applications. A variety of SAT solvers have emerged in recent years. However, the operation efficiency of SAT solvers is always a key factor affecting its applications, so taking advantage of the hardware's high performance and parallelism to accelerate the SAT solving process becomes a hot research topic in the area of verification. We summarize the methods for accelerating SAT solving solution, which use the parallelism and flexibility of FPGA, and analyze the acceleration policies of applicationspecified solver emphatically. Through indepth analysis of these methods, we point out their advantages and disadvantages, and provide ideas for future research.

      Systemlevel fault diagnosis based on bat algorithm  
      XUAN Hengnong,MIAO Chunling,ZHAO Dong
      2016, 38(04): 640-647. doi:
      Abstract ( 148 )   PDF (4068KB) ( 325 )     

      In this paper we apply the bat algorithm to solving the systemlevel fault diagnosis problem for the first time as an effective diagnosis algorithm. During the initialization phase, the population is divided into two categories: large and small, and they are handled in different ways. An equationconstrained fitness function is designed according to the characteristics of the systemlevel fault model. To balance global search and local search, a variable coefficient is added to the velocityupdating formula. We also perform binary mapping for bat speed to achieve the discretization of the addressing mode. Simulation results show that using the bat algorithm for fault diagnosis has significant advantages over FAFD, a typical representative of swarm intelligence diagnosis algorithms in aspects of the number of iterations, diagnostic accuracy and fitness of optimal solution.

      Multidimensional QoS cloud task scheduling
      based on colony algorithm
      YAN Liyan,ZHANG Guizhu
      2016, 38(04): 648-655. doi:
      Abstract ( 134 )   PDF (1107KB) ( 318 )     

      In order to meet the users’ Quality of Service(QoS) requirements and the efficient resource scheduling requirements in cloud environment, we propose a multidimensional QoS cloud task scheduling algorithm based on the artificial bee colony algorithm, which includes building a task model, a cloud resource model and a QoS model. In order to achieve efficient scheduling, we introduce an artificial bee colony algorithm. Because of its defects such as slow convergence and easy to fall into local optimization at the later stage, we introduce the profitability ratio, following ratio, current personal best value and random vectors to avoid the premature phenomenon. We compare this algorithm with the heterogeneous earliest finish time(HEFT ) algorithm and the artificial bee colony(ABC) algorithm through simulation, and experimental results show that the proposed algorithm can achieve higher operation efficiency and user satisfaction.

      A lowoffset dynamic comparator with
      calibration based on digital DAC 
      AN Kang,LI Jinwen,LIU Yao,CHANG Liping,LIANG Bin
      2016, 38(04): 656-660. doi:
      Abstract ( 189 )   PDF (802KB) ( 324 )     

      We propose a calibration technique based on binary capacitor DAC. We also design a lowpower highprecision dynamic comparator using 65nm CMOS technology. Simulation results based on layout show that our proposal can reduce the offset less than 0.25mV under 1.2V supply. It achieves 0.33μW power dissipation, an increase of 57% in comparison with the comparators without calibration.

      A dynamic uneven clustering scheme with load
      balancing in wireless sensor network   
      LIU Tao1,GUAN Yawen1,WANG Jun2
      2016, 38(04): 661-666. doi:
      Abstract ( 121 )   PDF (528KB) ( 279 )     

      A wireless sensor network (WSN) consists of several sensor nodes, all of which are resource limited, and the energy consumption on every node has significant influence on the network. Clustering schemes can effectively control overall energy consumption. Based on the characteristics of the node status, the dynamic change of the event location at the actual running phase of the network, we propose a dynamic uneven clustering scheme with load balancing. The main idea is that the network completes uneven clustering using the OLEACH algorithm with self organization, and then a certain number of decision nodes from the cluster heads are selected dynamically for data aggregation. The role of decision nodes changes dynamically with the transformation of the event location and node state. Simulation results show that the scheme balances the energy consumption, improves transmission efficiently and prolongs the network life in comparison with the CAPNet scheme.

      A location recommendation algorithm
      based on locationbased social networks 
      WANG Sen
      2016, 38(04): 667-672. doi:
      Abstract ( 182 )   PDF (601KB) ( 365 )     

      The existing location recommendation algorithms based on collaborative filtering have many problems, such as difficulty in estimating users preference and low recommendation accuracy. In order to improve the traditional similarity calculation algorithms for users, we propose a location recommendation algorithm. We firstly calculate user similarity and location similarity separately, and at the same time, conduct  cross adjustment to the two values continuously till convergence is achieved. The proposed algorithm is more effective for sparse data. In addition, we also take into account the user interest and the distance of the recommended location, and set a threshold to control weights of the two factors so as to adaptively generate recommendation lists. Experimental results show that compared with others, our algorithm can achieve better recommendation results.

      A lightweight and efficient RFID authentication
      protocol based on synchronization code       
      XIAO Hongguang1,LI Wei1,WU Xiaorong2
      2016, 38(04): 673-678. doi:
      Abstract ( 124 )   PDF (478KB) ( 298 )     

      While RFID technology is widely used, its security is facing serious challenges. Under the premise of ensuring safety performance, how to save system cost and improve efficiency has become a research focus. We propose a lightweight and efficient RFID authentication protocol base on synchronization code after analyzing the defects of various protocols and referring to the synchronization digital principle of code hopping encoder. This protocol guarantees the security of the system by using synchronous number and bidirectional authentication mechanism, and analyzes the threats to ensure the safety of the protocol. Comparing with other protocols, the proposed protocol is of low cost and efficient. Finally, the BAN logic protocol is adopted for a formal analysis, which theoretically proves the feasibility of the proposed protocol.

      An improved software fault localization technology #br# based on crossover matrix statistics  
      YANG Shuxin1,DIAO Wen1,2
      2016, 38(04): 679-685. doi:
      Abstract ( 136 )   PDF (488KB) ( 319 )     

      Fault localization is time consuming in the process of software debugging. Combining the automatic fault location technology with the automatic testing technology, high efficiency of software debugging can be realized. We propose an improved software fault localization technology based on crossover matrix statistics. We firstly conduct clustering reduction for all traces (successful or not) before localizing the faults so as to eliminate redundant execution traces. The remaining execution traces are stored in the crossover matrix. Finally the dubiety degree of the statements in the crossover matrix is calculated by the Crosstab algorithm and ranked to get the fault report. Performance experiments before and after the clustering reduction of traces on Siemens Suites verify the effectiveness of the proposed method.   

      An evaluation model of flight collaborative scheduling
      to guarantee flight punctuality rate  
      DING Jianli,WANG Man
      2016, 38(04): 686-692. doi:
      Abstract ( 132 )   PDF (563KB) ( 266 )     

      To guarantee flight punctuality rate and evaluate the cooperative conditions of ATC, airlines and airport in flight scheduling process, we propose an evaluation model of flight collaborative scheduling to guarantee flight punctuality rate. The model establishes the index system of flight collaborative scheduling based on flights' average deviation value of arrival time, average deviation value of departure time, average deviation value of flight service completion time, the accuracy rate of ‘Target OffBlocking Time’, and the accuracy rate of ‘Calculate TakeOff Time’. Firstly, the impact thresholds of each index on flight cooperative scheduling or flight delay are determined through the association rule mining method. Then, the magnitude evaluation of each unit’s coordination in the process of flight collaborative scheduling is given through the combination of the fuzzy analytic hierarchy process and the comprehensive evaluation method. Experimental results show that the proposed model can evaluate the coordination of each unit in the process of flight scheduling scientifically and effectively, and it has great significance for optimizing flight security as well as improving the flights’ normal releasing rate.

      Compatible evaluation of processor and desktop
      operating system based on SPEC 2000  
      LUO Jun,L Hongfeng,WANG Xiaoqiang,SUN Yu
      2016, 38(04): 693-698. doi:
      Abstract ( 143 )   PDF (2673KB) ( 241 )     

      Compatible evaluation of desktop operating system (DOS) and processor is crucial to promote the quality of the computer system. Traditionally, the evaluation of DOS mainly focuses on software, while the compatible performance between processor and DOS is barely concerned. SPEC 2000 is proposed to evaluate the compatible performance of processor and DOS in this paper. Eliminatingfactor  (λ)  is adopted to evaluate the influence difference of benchmark suits on different DOSs. Three DOSs are used in the experiment, and the results show that the benchmark suit may change the running results of SPEC 2000 of two DOSs under certain eliminatingfactor  (λ) . The proposed eliminatingfactor can be used to improve the performance of DOS and help choosing a robust benchmark suit.

      A classification algorithm of extreme learning
      machine based on influence degree pruning   
      ZHANG Hui1,2,SHI Tong1,WANG Yaonan2
      2016, 38(04): 699-705. doi:
      Abstract ( 143 )   PDF (1818KB) ( 296 )     

      To slove the network size control problems of the extremely learning machine (ELM), we propose an ELM classification algorithm based on the  influence degree pruning. The algorithm uses the individual ELM hidden node which connects the input and output layer weight vector, the output of the node, the number of samples and the initial number of hidden nodes to define the influence degree of the hidden node on the entire network. Then the importance of the hidden node is determined by the sorted influence degree, and the pruning step length which matches the ELM network scale is used to delete redundant nodes. Finally the weight vectors are updated. We categorize several practical problems on UCI data sets through experiments, and compare the proposed algorithm with the EMELM, PELM and ELM. Experimental results show that the proposed algorithm has higher stability and precision and faster training speed, and it can control the network size effectively. 

      An improved teaching learning based optimization
      with selfstudy and simulated anneal          
      WANG Peichong
      2016, 38(04): 706-712. doi:
      Abstract ( 114 )   PDF (575KB) ( 312 )     

      Concerning the problem that the teaching learning based optimization (TLBO) algorithm is easy to premature with low solution precision, we propose an improved TLBO algorithm with selfstudy of teachers and optionalstudy of students. In every iteration, individual teachers adopt the oppositionbased learning (OBL) to generate an opposition search population, and the search space of the algorithm is guided to approximate optimum space. This mechanism is helpful for improving the balance and exploring the ability of the TLBO. Every individual student  executes OBL randomly and studies from teachers at the same time. For keeping the diversity of the population, we calculate the students' jumping probability to current teachers. We adopt the roulette mechanism to choose the individuals which will replace the parent individuals. Compared with related algorithms, the simulations on 11 classical benchmark functions show that the proposed algorithm has better convergence rate and accuracy for numerical optimization, and is suitable for solving high dimensional optimization problem.

       

      Shortterm traffic flow prediction of optimized RBF neural
      networks based on the modified ABC algorithm        
      HUANG Wenming,XU Shuangshuang,DENG Zhenrong,LEI Qianqian
      2016, 38(04): 713-719. doi:
      Abstract ( 174 )   PDF (671KB) ( 492 )     

      In order to improve the prediction accuracy of radial basis function (RBF) neural network model for shortterm traffic flow, we propose a prediction model for shortterm traffic flow of optimized RBF neural networks based on the modified artificial bee colony (ABC) algorithm. The modified ABC algorithm is used to confirm center value and unit numbers of the hidden layers of the RBF neural networks. Then the modified RBF neural network prediction model is trained, and the efficiency of the proposed prediction model is tested through simulations on the shortterm traffic flow data of a city in four days. Experimental results of the proposed model are compared with the traditional RBF neural network model, the BP neural network model and the wavelet neural network model, which  verify the higher prediction accuracy of the proposed method.

      Parallel robot nonlinear equation solution
      based on CoDeSys environment 
      CHEN Chimei1,2,CHEN Lixue2
      2016, 38(04): 720-725. doi:
      Abstract ( 200 )   PDF (755KB) ( 352 )     

      So far, the problem of Kinematics of the closedform solution remains a technical problem, and currently the most popular method in practice is the use of numerical solution method and the generalized geometric equations method. However, the derivations of these methods are very complicated, and there is no unique solution in the process of solving equations. To avoid these problems, we propose a triple nonlinear equation of parallel robot Newton iteration algorithm based on the Taylor formula multivariate function. Based on the mathematical principles, the antiparallel robot solutions can be obtained. The Taylor algorithm avoids multiple solutions tradeoffs skillfully, and the solution meets the demand of continuous exercise directly. In terms of rate of convergence, this algorithm is very promising. We apply the proposed algorithm in the CoDeSys environment, which proves that parallel kinematics can be applied flexibly in real time in CoDeSys environment via configuration.

      Image quality assessment based on structure similarity
      with variation function global texture enhancement  
      WANG Wei1,LIU Jing1,LI Ji1,LIU Yang1,PAN Wei2
      2016, 38(04): 726-732. doi:
      Abstract ( 118 )   PDF (1358KB) ( 254 )     

      To solve the defects of image quality assessment by structure similarity algorithms, we propose an image quality assessment method based on structure similarity with variation function texture enhancement. Firstly the improved logarithmic variation function model is utilized to extract the texture information characteristics of the original image and  the distorted images in the four directions of horizontal 0°, vertical 90°, diagonal 45° and diagonal 135°, and the corresponding texture enhancement images are calculated respectively. Then the structure information of the improved SSIM is used  to determine the obvious distorted texture region, and the VSSIM value of the whole image is calculated. At present most of the existing evaluation methods are mainly used for a particular type of distortion , while the proposed  method  can be applied to all the five types of distortion in LIVE  database. Experimental results show that  the distortion evaluation results are stable, reasonable and relatively consistent with subjective evaluation database, and its performance is superior to other quality evaluation models.

      An improved anomaly detection algorithm for
      hyperspectral images based on PCA and IHS fusion     
      JIANG Tiecheng
      2016, 38(04): 733-738. doi:
      Abstract ( 132 )   PDF (565KB) ( 344 )     

      Lack of spatial resolution in hyperspectral images can cause high false alarm rate in anomaly detection. Aiming at this problem, we present a new anomaly detection algorithm. Firstly, the main components of the low resolution hyperspectral images are extracted by the principal component analysis (PCA) method. Then the extracted principal components and highresolution images are converted using the IHS transform, and the intensity of each component is obtained. Taking its advantage of reversibility, the IHS inverse transform is performed on the new strength of hyperspectral data components, the colors of the components H and the saturation component S, thus the hyperspectral image data with spatial information enhancement is obtained. Finally the KwRX algorithm is used for detecting the anomaly of hyperspectral images. Simulation experiments show that the proposed algorithm outperforms the KRX algorithm and the PCAKRX algorithm, in the number of target pixels and the number of false alarms thus demonstrating its effectiveness and feasibility.

      Medical image classification based on
      neighborhood relation fuzzy rough set   
      HU Xuewei,JIANG Yun,ZOU Li,LI Zhilei,SHEN Jian
      2016, 38(04): 739-746. doi:
      Abstract ( 115 )   PDF (609KB) ( 324 )     

      For medical images classification, feature selection is an important factor that affects classification accuracy. Aiming at the particularity of medical image as well as undesirable effects of current feature selection methods, we propose a fuzzy rough set model based on neighborhood relation, and a feature selection algorithm based on the model as well. We apply our algorithm to mammography, and the experimental results show that it can effectively select features and improve classification accuracy in comparison with the existing algorithms.

      Subpixel registration based on adaptive particle
      swarm optimization with mutual learning         
      LIU Huan1,2,XIAO Genfu3,OUYANG Chunjuan1
      2016, 38(04): 747-754. doi:
      Abstract ( 120 )   PDF (3000KB) ( 312 )     

      In order to solve the problem of huge computation and high time cost in subpixel registration resolution of digital image correlation, we propose a new improved PSO for subpixel registration of the respective flight velocities. The flying velocity and range of particles which are subdivided at two directions x and y, can adaptively adjust according to the deformation degree of each interest point so as to improve their displacement solution quality. In addition, the reliable mutual learning mechanism is introduced and the historical information of the previous feature points is fully utilized, which helps to reduce the number of iterations and enhance algorithm efficiency. Compared with the NewtonRaphson and the NRPSO, the proposed method has higher accuracy, and the feasibility and availability are verified. Particularly, the superiority of time cost is more distinct when dealing with a large number of interest points.