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

Current Issue

    • Design and optimization of large scale dissipative particle dynamics simulation on Intel MIC platform
      XU Shun1,2,LIU Qian1,2,ZHANG Bao-hua1,2,HE Lian-hua1,2,JIN Zhong1,2
      2017, 39(08): 1391-1396. doi:
      Abstract ( 171 )   PDF (640KB) ( 364 )      Review attachment

      Dissipative particle dynamics (DPD) simulation is an important computational simulation method to investigate the dynamic characteristics of the fluid. We design and carry out an Intel MIC platform-based large-scale dissipative particle dynamics simulation. The design combines the characteristics of DPD simulation and the features of MIC platform. The critical codes of DPD simulation such as neighbor list building and calculation of short-range force are designed with the vector optimization. A load balancing mechanism of tasks between the CPU and MIC co-processors is applied to support the load balancing control of the number of threads within a MPI process. The performance analysis on a prototype program and LAMMPS integration program is compared, and the experimental data show the effectiveness of introducing relevant optimization technologies. This work lays the foundation for further research on molecular dynamics simulations on MIC many-core platform.

      A  Bayesian network based test generation method 
      for Cache coherency protocol verification
      AI Yang-yang,LUO Li,YANG Qing-na,ZHANG Heng-hao,XIA Ting-ting
      2017, 39(08): 1397-1402. doi:
      Abstract ( 198 )   PDF (674KB) ( 351 )      Review attachment
      As the complexity of integrated circuit design increases exponentially, functional verification has become a bottleneck in large-scale chip design. And in multi-core processor design, Cache coherency protocols are very complex and difficult to verify. We propose a random test generation method based on Bayesian network for simulation-based verification to solve the state space explosion problem of Cache coherency protocols. We discuss the Cache coherency protocol, analyze the coverage directed test generation (CDG) method based on Bayesian network reasoning, and apply the method to Cache consistency verification. Taking the verification of the Cache coherence protocol of the FT processor as an example, the results show that the CDG method can increase coverage by nearly 30% in comparison with the pseudo-random test.
       
      A parallel FP-Growth mining algorithm
      based on Spark framework
      ZHANG Wen,LUO Ke
      2017, 39(08): 1403-1409. doi:
      Abstract ( 183 )   PDF (655KB) ( 295 )      Review attachment

      The Apriori and FP-Growth are classical algorithms in frequent pattern mining. Since the Apriori has more flaws, the FP-Growth is a more efficient algorithm in stand-alone computing environment. Aiming at the bottlenecks of non-parallel computing in the era of big data, we propose a balanced parallel frequent pattern (BPFT) growth algorithm based on the connect-weight (CW) matrix of items in each transaction, called CWBPFP, which achieves parallel computing based on Spark framework. We use the load balance strategy to group data, and the corresponding code of each frequent item is stored in the relevant group during grouping. The connect information of items in each transaction of each grouped data is stored into a lower triangular connect-weight matrix by each working node. We use the restricted sub-tree to accelerate the speed of producing conditional FP-tree, and employ the connect-weight matrix to avoid the first scanning for the conditional patterns during mining frequent patterns of grouped data. The performance of the parallel mining FP-tree is improved due to the combination of the CW matrix and the restricted sub-tree applied to FP-tree mining process of each node. Experiments show that the CWBPFP has high performance and scalability on big data sets.

      A secret sharing-based authentication scheme for
      ocean remote sensing images in cloud environment
      HUANG Dong-mei1,XU Hui-fang1,HE Qi1,DU Yan-ling1,WEI Quan-miao2
      2017, 39(08): 1410-1418. doi:
      Abstract ( 120 )   PDF (921KB) ( 202 )      Review attachment
      The emergence of cloud storage model has brought new opportunities to the storage and management of massive ocean remote sensing images, and more and more users choose to transfer their image data into the cloud, which brings challenges for image data security and usability due to the openness of cloud. We propose an image authentication scheme to protect the ocean remote sensing image confidentiality in cloud environment, which combines the Hash function with the (k, n) threshold secret sharing method to detect the changes of the image data in sensitive regions and verify the consistency between encrypted and recovered images. The sensitive-region image cannot be restored when more than n-k out of n sub-secrets get lost or tampered. To avoid this, we divide the sensitive region image into blocks, and implement secret sharing for each sub block, thus guaranteeing the lossless recovery of partial images and enhancing the availability of image data. Analysis on comparison experiments shows that the algorithm can effectively prevent fraud in the process of secret image recovery, and obtain higher cloud storage security for remote sensing images than traditional methods.

       

       
      A parallel 3D poisson equation solver
      based on discrete sine transform
      LIN Shi-wei1,2,3,ZHANG Wei-min1,2,FANG Min-quan1,2,LI Song1,2
      2017, 39(08): 1419-1424. doi:
      Abstract ( 224 )   PDF (650KB) ( 337 )      Review attachment
      Poisson equations are widely applied in physical and engineering problems. Most of numerical methods for solving 3D Poisson equations have no remarkable parallelism, and use the global iteration methods which limit the computational efficiency and stability. We abandon the idea of global iteration and combine the discrete sine transform theory (DST) with 27-point four-order difference scheme to modify and parallelize the 3D Poisson equation solver at the algorithm level, which separates the whole problem to several smaller independent ones and greatly improves the stability and parallel performance. For a given discrete form, common parameters can be used to solve different Possion equations so that the programming efficiency is greatly improved. The algorithm is implemented on the basis of the shared memory parallel model. Experimental results show that  for the given instance, the new algorithm has a good acceleration effect and the final error of the computing result is about 10e-5, within an acceptable rang. And the result accuracy gets improved with the increase of problem scale.
       
      A preconditioned squared Smith algorithm
      for large Sylvester matrix equations
      CAI Zhao-ke,BAO Liang,XU Dong-mei
      2017, 39(08): 1425-1430. doi:
      Abstract ( 134 )   PDF (748KB) ( 196 )      Review attachment
      We propose a preconditioned squared Smith algorithm to solve large scale continuous-time Sylvester matrix equations. We firstly construct a preconditioner by using the alternating directional implicit (ADI) iteration, and transform the original equation to an equivalent non-symmetric Stein matrix equation. Then we apply the squared Smith algorithm to generate the low-rank approximation form with a Krylov subspace. Numerical experiments show that the algorithm has better iteration efficiency and convergence accuracy in comparison with the Jacobi iteration method.
       
      A cloud scheduling strategy for long jobs
      JIANG Wei-cheng,LI Lan-ying,GUO Jun,XU Cao-cao
      2017, 39(08): 1431-1437. doi:
      Abstract ( 118 )   PDF (510KB) ( 183 )      Review attachment
      With the popularity of cloud computing, a large number of data processing is completed by cloud services. Current algorithms seldom consider the different computing capability of the virtual machine in the heterogeneous system, so the waiting time is too long. We propose a scheduling algorithm which adapts to the size of real-time virtual machine load. Given the virtualization of cloud computing resources, we propose a method for evaluating the computing capability of virtual machines. Based on the virtual machine capability and the changes of the process, the adaptive task size is adjusted to meet the real-time requirements. Task completion time is unified and the load balancing of the virtual machine is maintained so the total execution time is shortened and the system throughput and the overall service capability are improved, hence the benefit is improved. Experimental results show that the algorithm can adaptively adjust the size of tasks according to the operating conditions, and maintain the load balance of the virtual machine.

       
      An energy-efficient sensor scheduling algorithm based
      on multi-band sensor-aided cognitive radio networks
       
      ZHANG Yun-lei,LIU Kai-hua,MA Yong-tao,LI Yang
      2017, 39(08): 1438-1443. doi:
      Abstract ( 95 )   PDF (762KB) ( 209 )      Review attachment
      Traditional energy-efficient sensor scheduling problems only consider single frequency band in sensor-aided cognitive radio networks. Multi-band energy-efficient sensor scheduling problems have many novel research fields. We formulate a multi-band sensor scheduling problem and propose a genetic algorithm based energy-efficient scheduling algorithm to improve the throughput. We take account of the energy consumption of the sensor when switching frequency bands. In the model, the cognitive base station assigns a set of sensors for each frequency to improve energy efficiency. The genetic algorithm based energy-efficient scheduling algorithm optimally schedules the activities of the sensors to increase the overall secondary system throughput and achieve the goal of energy efficiency. Simulation results show that our algorithm achieves higher network throughput than the greedy algorithm and other algorithms.
       
      A topology control algorithm in wireless
      sensor networks based on fuzzy control
       
      ZHANG Qiang-yu,QI Jian-dong,HE Yi
      2017, 39(08): 1444-1449. doi:
      Abstract ( 143 )   PDF (666KB) ( 271 )      Review attachment
      In wireless sensor networks and even wireless networks, topology control is a research hotspot. Nowadays, many topology control algorithms claim to be energy efficient, which try to find either appropriate transmit power or good network topology. However, in practice, the two aspects both should be considered. We propose a novel topology control method called hybrid fuzzy-logic topology control (HFLTC) which introduces the idea of XTC to build links. It is based on the fuzzy control and an optimized link quality evaluation model to achieve power control. Simulation results show that the method that combines topology and power control together can save more average energy consumption of networks and extend the entire network life cycle.
       
      Sum-rate maximization based beamforming
      design for full-duplex SWIPT systems
       
      WANG Zhi1,2,Chen Dong-hua1,2,He Yu-cheng1,2
      2017, 39(08): 1450-1456. doi:
      Abstract ( 155 )   PDF (579KB) ( 411 )      Review attachment

      We propsoe a joint optimization scheme of the beamforming vectors based on the maximization of system sum rate for the SWIPT communication systems with full-duplex (FD) base station. The proposed scheme makes an improvement in information transmission rate and spectrum efficiency (SE) with the aim of maximizing the system and rate while guaranteeing the maximum transmitting power constraints in the uplinks/downlinks and meeting the minimum energy harvesting requirement. Because the problem of rate is non-convex, we firstly transform the original problem to a convex one via the techniques of semi-definite relaxation (SDR) and first-order Taylor approximation, and then obatain the optimal information beamforming vectors and energy beamforming vectors by the iterative algorithm based on successive convex approximation (SCA). Simulation results show that the proposed scheme outperforms the traditional schemes, and effectively improves the system sum rate.

      Key management schemes based on access
      control and Chinese remainder theorem in database
      YAN Xi-xi1,HU Qian-wei1,TANG Yong-li1,YE Qing1,LI Zi-chen2
      2017, 39(08): 1457-1464. doi:
      Abstract ( 128 )   PDF (1128KB) ( 238 )      Review attachment
      Since the number of data items keys is larger, much higher security is needed in database encryption systems. In view of this question, we propose new key management schemes based on access control and Chinese remainder theorem which makes the management of data items keys convenient. A large number of the data items keys Ki which the user  ui has access to, can be compounded to user class keys
      uki when the user applies for the key, then this key is saved. When the user decrypts the data, user class keys  uki  are broken down into key data items using the system tables and the Chinese remainder theorem. The schemes can solve the problems of high time cost on processing data and more system resources occupation, thus improving the efficiency and security of the key management in the cipher text database. Experiments and comparison prove the significant improvement in efficiency and security of key management.
       
      Abnormal crowd behavior detection
      based on optical flow computation
      ZOU Zheng,YAN Wei,XIE Jian-bin,LIU Tong,LI Pei-qin
      2017, 39(08): 1465-1470. doi:
      Abstract ( 121 )   PDF (2366KB) ( 315 )      Review attachment

      We propose a detection method based on optical flow to detect the abnormal crowded behavior in a crowd scene. In this method, the motion characteristics of the crowd are extracted by using the optical flow vector field. Then the interaction force between the particles is calculated based on the social force model. Finally, we implement histogram entropy discrimination process on the interaction force to achieve the discrimination of crowd behavior. Simulation results show that the algorithm can distinguish the size of the interaction force in abnormal regions in the crowd scene, identify and locate the abnormal congestion.

      Graph connectivity based on hierarchical
      quotient space chain
      ZHOU Min1,WANG Jia-yang1,LONG Chen-feng2,CHEN Lin-shu1
      2017, 39(08): 1471-1475. doi:
      Abstract ( 100 )   PDF (485KB) ( 215 )      Review attachment
      Judgment of graph connectivity is significant for judging the connectivity between any two points and the division of the connecting block in path planning. We analyze graph hierarchy by starting from edge connectivity relationship, and obtain the distribution of each node on different levels in the chain by constructing a graph hierarchical quotient space chain, thus achieving a new method of judging graph connectivity. Compared with conventional methods, it has the advantages of high efficiency and is easy to implement. It can not only effectively determine graph connectivity but also the branch number, and identify which node is located in the same connected component in the graph.
       
      A capacitor element localization method
      based on geometrical features of target contour
      NI Yao,BAO Yu
      2017, 39(08): 1476-1482. doi:
      Abstract ( 110 )   PDF (847KB) ( 247 )      Review attachment

      As the printed circuit board (PCB) manufacturing process is becoming increasingly complicated, identifying the position of capacitor elements becomes more challenging. In order to save costs and reduce the error rate in actual production, the circuit board needs to be detected before welding. At the same time, in order to fix the components, a plate is often used to fix circuit boards. We propose a positioning method for covered capacitor elements under a complex background. We perform image preprocessing, threshold segmentation, edge extraction, Harris corner detection and other operations on the collected PCB images, and then locate capacitor elements according to the geometric characteristics of their target contour. The method can be widely applied in production due to the high positioning accuracy and fast speed.

      An improved particle filter algorithm based on
      UKF and optimized combination scheme
      ZHANG Kun1,TAO Jian-feng2,HE Si-san2
      2017, 39(08): 1483-1488. doi:
      Abstract ( 196 )   PDF (584KB) ( 249 )      Review attachment
      In order to solve particle degeneracy and simultaneously avoid sample impoverishment, we propose a new improved particle filter algorithm based on the unscented Kalman filter (UKF), optimized combination strategy, and the standard particle filter method. We use the UKF to generate the importance density function and solve all the problems caused by the traditional particle filters which use prior density function as the particle distribution. And then we employ the optimized combination scheme to ensure all useful information inherited, which can maintain particle diversity. Theoretical analysis and simulation results both show that the improved particle filter algorithm can solve particle degeneracy and avoid sample impoverishment, and it has higher filtering accuracy in state estimation.
       
      An approximate algorithm based on quartic B-spline curves
      CHEN Han-yu,JIANG Yong
      2017, 39(08): 1489-1494. doi:
      Abstract ( 142 )   PDF (553KB) ( 207 )      Review attachment
      To overcome the shortcomings of the traditional interpolation spline that is difficult to add or delete points and the inaccuracy of the traditional approximate spline, we propose an approximate algorithm based on the cubic B-spline. The algorithm, which is based on the approximation and the iteration, improves the calculation speed and precision. Based on the periodic cubic B-spline curves, the algorithm extends to quartic B-spline, which is third derivative. Besides, the theoretical proof of the convergence of the algorithm is given out. Finally, the numerical approximation experiments on common functions show that the algorithm has a faster convergence speed and can meet higher practical industrial needs.
       
      Laser marking grid image feature
      extraction based on RANSAC
      QIN Yu1,WU Jing-jing 1,2,AN Wei1,2
      2017, 39(08): 1495-1501. doi:
      Abstract ( 113 )   PDF (810KB) ( 231 )      Review attachment
      In 3D vision technology, the feature extraction of the surface of the workpiece is the premise and key of 3D reconstruction. However, the natural features often appear less obvious so the feature extraction is very difficult. The laser grid is often projected onto the surface of the workpiece so that the workpiece surface can be identified with definable characteristics. Aiming at the characteristics of laser grid mark images, we propose a method of pixel weights and hypothetical model pre-detection based on the RANSAC algorithm for line feature extraction. Experimental results show that this method can not only overcome the disadvantages of large computation and parameter sensitivity of the RANSAC algorithm, but also has good accuracy and robustness.
       
      An infrared radiation simulation method
      for aircrafts and typical features
      YE Xin1,ZHANG Yan1,CHEN Xiao-tian1,ZHANG Feng1,ZHANG Jun-jun1,QIU Tiao-wen1,2
      2017, 39(08): 1502-1507. doi:
      Abstract ( 129 )   PDF (1019KB) ( 298 )      Review attachment

      Aircrafts and typical ground objects have an important application value in military. In order to obtain training samples to study the detection, recognition and dynamic monitoring of the targets, we develop a new piece of software which can achieve infrared image simulation of typical aircrafts and ground objects in different conditions, including different seasons, different weather conditions, and different times of the day. Based on the Visual Studio 2010 environment, we build a model of aircrafts and typical ground objects on the OpenGL. Besides, we adopt the theoretical analysis of heat transfer and infrared radiation, and embed the kernel of the RadThermIR which is a heat-analysis tool, into the algorithm. Finally, we propose a simulation method to calculate the infrared radiation intensity and build up infrared images of aircrafts and typical ground objects. The similarity of image grey scale is taken as the evaluation index, and the test results reveal that the simulation accuracy of infrared images can reach over 80%, providing rich training samples for target auto-detection, target recognition and object tracking of the aircrafts on airport. 
       

      Remote sensing target recognition based on extended
       dictionary and sparse representation classification
      LI Ji,WANG Yan-ran,WANG Wei
      2017, 39(08): 1508-1512. doi:
      Abstract ( 122 )   PDF (562KB) ( 205 )      Review attachment

      We propose a remote sensing target recognition method based on the extended dictionary and sparse representation classification to solve problems such as poor visual contrast, low resolution, and rotation in different angles. Firstly, the training and test samples are enhanced with dyadic wavelet transform. Secondly, a feature dictionary is constituted by extracting SIFT features from the enhanced images. We then compose an extended dictionary which contains both an original training dictionary and a feature dictionary for sparse representation, so that the extended dictionary can be more discriminative, and the recognition rate can be higher. We also analyze the influence of SIFT features after random projection on the recognition rate. Experimental results show that the method is robust to the recognition of remote sensing targets.

      A background subtraction method based
      on robust local texture features
       
      JIN Jing1,DANG Jian-wu1,WANG Yang-ping1,2,ZHAI Feng-wen1
      2017, 39(08): 1513-1519. doi:
      Abstract ( 104 )   PDF (805KB) ( 185 )      Review attachment

      Focusing on the precise detection of moving objects, we propose a new local texture descriptor—LBP_Center, which is robust to noise and invariant to gray scale. And together with the color information of pixels we apply it to the background model. Then we update the model by random sampling and introduce background complexity to remove the noise of the multimode dynamic background. Experimental results on standard testing datasets indicate that the new method has good robustness to soft project shadows and slow illumination change, and better comprehensive performance in comparison with other algorithms.