Current Issue

• 2017, No. 10　Published:25 October 2017 Last issue    Next issue
  Columns in this issue:

• A high-radix hybrid topology in interconnection networks

  LU Wen-bin,SONG Xin-liang,LU Hong-sheng,DING Ya-jun

  2017, 39(10): 1781-1787. doi:

  Abstract ( 175 )   PDF (686KB) ( 254 )   　　

  With the continuous expansion of high performance computer systems to meet the increasing requirements for high performance computers, the interconnectiction network system has become the key factor that influences the performance. How to design larger-scale networks faster with lower latency and lower cost, and larger throughput based on high-radix router by making full use of the features of high-radix router is currently the main research direction. We analyze the features of the high-radix network and synthesize the torus and fat-tree topology, and put forward a new hierarchical hybrid interconnection network topology. The proposed topology has satisfactory scalability and communication capability. We finally use the network simulator NetSim to simulate and analyze its performance.

   

  Design and implementation of a prefix computation

  model of leading zero anticipator algorithm

  FU Kun1,2，WEI Si-jie1,2，GENG Yue-hua3

  2017, 39(10): 1788-1793. doi:

  Abstract ( 228 )   PDF (564KB) ( 262 )   　　 Review attachment

  The leading zero anticipator (LZA) algorithm is very important for studying floating-point addition operation, and the analysis of floating-point addition indicates that the LZA  module plays a critical role in the performance improvement of  floating-point addition operations. We define a series of definitions and theorems from the perspective of prefix computation, and prove that the LZA algorithm can be attributed to a prefix computation problem in nature. Thus, the problem can be solved by the dichotomy recursive method. In LZA process, we firstly convert the prediction problem of two operations  to a digital string feature detection problem on numeric character set of {1,0, 1} by performing the subtraction of "Borrow Retirement" on addition operations. Secondly, a unified form of bit strings is obtained via the recoding technique which eliminates the continuous string of "1". Finally, the dichotomy recursive algorithm is designed based on the bit string structure of leading zero digits.

   

  Design and implementation of

  a new elastic buffer for USB 3.0

  CHANG Hong，MENG Jian，PENG Te，KE Dao-ming

  2017, 39(10): 1794-1800. doi:

  Abstract ( 182 )   PDF (1496KB) ( 186 )   　　 Review attachment

  The process of adding SKP is usually completed by breakpoint restoration and pointer jump in an elastic buffer. Aiming at the problems of complex asynchronous logic circuit design and possible timing errors caused by this realization method, we propose a novel technique to achieve SKP adding by the read pointer pause. Firstly, the threshold monitor checks the amount of valid data, which are then compared with the adding threshold to generate an adding instruction. Secondly, we make the read pointer pause and add the SKP to the output data, which guarantees the state of elastic buffer at half-full by raising the volume of effective data. Experimental results show that the proposed elastic buffer can achieve the function of SKP adding and removing correctly while both the read and write frequencies of the buffer can reach 500MHz, which meets the design requirements of universal serial bus 3.0 (USB 3.0).

  A parallel MRACO-PAM clustering

  algorithm based on MapReduce

   

  ZHAO Bao-wen,XU Hua

  2017, 39(10): 1801-1806. doi:

  Abstract ( 130 )   PDF (502KB) ( 187 )   　　 Review attachment

  Clustering analysis is one of the most commonly used data processing algorithms, and the partitioning around medoid (PAM) has been one of the most popular clustering algorithms since it was proposed in 1990. The PAM clustering algorithm solves the problem that the K-Means algorithm encounters when processing outlier data, which is sensitive to dirty data in clustering process. However, the original PAM’s convergence speed is slow and it works inefficiently for large datasets due to its time complexity. To address this problem, we enhance the global and local searching capabilities of the PAM by taking advantage of the ant colony algorithm, and propose a parallel MRACO-PAM clustering algorithm based on MapReduce programming framework. Experimental results demonstrate that the parallel MRACO-PAM algorithm based on MapReduce  improves the convergence speed and is capable of dealing with large-scale data with good scalability.

  A document similarity calculation method based on fully

  homomorphic encryption technology for cloud storage

  JIANG Xiao-ping,ZHANG Wei,LI Cheng-hua,ZHOU Hang,SUN Jing

  2017, 39(10): 1807-1811. doi:

  Abstract ( 132 )   PDF (1551KB) ( 178 )   　　 Review attachment

  In order to preserve user privacy in cloud storage services, we propose a method for calculating the similarity of documents under the ciphertext environment. After the data owner uploads the document ID, the ciphertext of document and the ciphertext of document simhash to Cloud servers, the cloud server performs fully homomorphic addition operations on the simhash ciphertext of the document whose similarity is expected and the simhash ciphertext of the data owner's document. Then the ciphertext of the Hamming distance between documents  is obtained. The data owner can get the results of document similarity ranking by decrypting the ciphertext of the Hamming distance. The goal of privacy preservation can be achieved by this method because the cloud server can complete  similarity calculation without any plaintext information, neither the document text nor its simhash value. We explain the proposed method in detail and the related experimental data verify its feasibility and correctness.

  An overall scheme and a software tool of coordination and control

  of accessories stock for cloud service platform of industrial chian

  Lv Rui1,2,SUN Lin-fu1,2

  2017, 39(10): 1812-1818. doi:

  Abstract ( 88 )   PDF (840KB) ( 140 )   　　

  To meet the spare parts collaborative needs of manufacturing industry chain collaborative platform, we propose a cross-enterprise inventory control solution and establish a near-term demand forecasting model. In order to ensure the effectiveness of the inventory control program, we dynamically extract historical transaction data of each node and real-time inventory data, and obtain the optimal solution based on the genetic algorithm. We use the MapReduce framework to calculate model parameters and improve the processing speed. By pushing the results to downstream service providers, the feedback information can control the dynamically generated orders. The application in the automotive industry chain cloud services platform demonstrates that the response time of the industry chain is compressed.

  A constrained pseudo-random function

  construction  scheme based on hierarchical proxy

  ZHANG Li-na1,2,ZHOU Yan-wei2,HOU Hong-xia2,3

  2017, 39(10): 1819-1824. doi:

  Abstract ( 114 )   PDF (431KB) ( 141 )   　　 Review attachment

  The concept of constrained pseudo-random functions (CPRF) was proposed independently by Boneh and Waters, Boyle etc., Kiayias etc. in 2013. In a CPRF a constrained key  ks can be derived from the master key  k. Both  ks and   k can be used to calculate the same pseudo-random function (PRF) value. Based on the CPRF with bit-fixing structure proposed by Boneh and Waters, we propose a construction of hierarchical proxy based on constrained pseudorandom functions. The size of the constrained set cannot be influenced by the layer number of the hierarchical proxy. The proposed scheme is proved to be secure in the standard model under the multilinear decisional Diffie-Hellman assumption. And it can be used to generate the encryption key of broadcast encryption or the session key of the identity-based non-interactive key exchange under the hierarchical proxy in practice.

  An enhanced naive Bayesian relationship

  prediction model in complex networks

  WU Jie-hua1,2,SHEN Jing1,ZHOU Bei1

  2017, 39(10): 1825-1831. doi:

  Abstract ( 87 )   PDF (708KB) ( 156 )   　　 Review attachment

  Complex networks include biological information networks, collaboration networks and social networks. Studying the relationship prediction of complex networks helps predict relationship between proteins, find out cooperation relationship among scientists, as well as mine potential social networks. Currently, most relationship prediction algorithms are realized by similarity-based models, however, this type of algorithms based on network topology feature are explicitly constructed, which ignore latent information behind generated relationship. To solve this problem, we propose an enhanced naive Bayesian relation prediction model (ELNB), which defines a conditional probability to model the local sub-graph structure. It can effectively alleviate the independence assumption of LNB and realize a quantitative calculation of neighbors contribution. Experiments on artificial datasets and real datasets show that the proposed model is better than the baselines and some recently proposed models. Meanwhile，the idea of ELNB can be extended to other similarity algorithms based on common neighbor nodes, which provides a new method for the research of such kind of model.

   

  Attack and improvement on an ID-based

  partially blind signature scheme

   

  ZUO Li-ming1,2,ZHANG Ting-ting1,2,GUO Hong-li1,2，CHEN Zuo-song1,2

  2017, 39(10): 1832-1836. doi:

  Abstract ( 87 )   PDF (414KB) ( 125 )   　　 Review attachment

  The partially blind signature scheme is an important foundation signature scheme widely used in anonymous applications such as electronic cash, electronic payment and electronic voting. Through the crypt analysis of the ID-based partially blind signature scheme proposed by Yin et al. We find that there are forgery signature defects between multiple users in the scheme. The attacker can forge the signature by indexing the key parameters and using the repeated parameters. We therefore propose an improved partially blind signature scheme and it proves to be existentially unforgeable against adaptive chosen message in random oracle model. The new signature can resist indexing attacks and be applied to certificateless  electronic voting occasions.

   

  A hybrid feature-based detection method on Android malware

  XU Lin-xi,GUO Fan

  2017, 39(10): 1837-1846. doi:

  Abstract ( 112 )   PDF (1273KB) ( 182 )   　　 Review attachment

  Currently, Android malware detection is one of the hotpots in the security research field. Since Android is open source and very popular, the Android platform becomes a target of most malwares. Current approaches only extract syntax features or semantic features respectively so that it is difficult for them to know the real intention of the malware exactly. We propose a hybrid feature extraction method, using the set of class-based taint propagation paths as semantic features and claiming permissions and Intent-Actions as syntax features. We normalize all the extracted features before training and clustering data sets by K-means, and then produce feature vectors of each malware family. Finally we adopt the Euclidean distance computation to measure the similarity between the unknown program and feature vectors. The prototype is implemented on top of FlowDroid to analyze 400 real programs, and the results demonstrate that the method has higher precision.

   

  A geographic location routing method for

   energy balance in wireless sensor networks

  LI Lan-ying，JIANG Wei-cheng，HE Yong，LI Xiao-fang

  2017, 39(10): 1847-1853. doi:

  Abstract ( 89 )   PDF (552KB) ( 125 )   　　

  The wireless sensor network routing algorithm based on geographical position only focuses on the geographic

  information. We propose a multi-path routing algorithm based on energy of nodes. We use geographic location

  and energy to establish a 3D coordinate system and calculate the probability of the next hop according to the

  effective forward distance and the energy of neighbor nodes. The energy consumption is scattered in the

  neighbor nodes which are effective to move forward so the network survival time is prolonged. Routing holes

  are reduced and delayed. Experimental results show that the number of dead nodes, surviving nodes and routing

  holes are significantly improved in comparison with the two-phase geographic greedy forwarding (TPGF)

  algorithm. The validity of the algorithm is verified.

   

  Application of discrete Walsh transform

  in  digital multiplexer network design

   

  JAING En-hua,JIANG Wen-bin

  2017, 39(10): 1854-1861. doi:

  Abstract ( 75 )   PDF (728KB) ( 148 )   　　 Review attachment

  We study the applications of discrete Walsh transform in the design of digital multiplexer networks, and

  propose a computer aided design theory and an algorithm of the multiplexer networks based on the Walsh

  spectral techniques. We also present a practical application example, which shows that the algorithm can

  minimize or nearly minimize the multiplexer tree-type network, and that the method is effective and suitable

  for computer aided design of multiplexer tree-type networks. By using CMOS circuits, the 1-of-4 multiplexer

  module and the designed multiplexer network with minimal size are realized. HSPICE simulation results show

  that the designed circuit has correct logic functions.

   

  Robust visual odometry based on front and back cameras

   

  SHI Xiao-tian1,ZHANG Yu2,FANG Zhou1

  2017, 39(10): 1862-1869. doi:

  Abstract ( 97 )   PDF (980KB) ( 169 )   　　

  We propose a new visual odometry method to use front and back cameras at the same time due to the terrible

  impact of luminance on indoor visual odometry and the dual-camera feature of modern  mobile devices. By the

  state estimation of the visual odometry on each side, we can achieve the sustained output even when one side

  fails, and the robustness of visual odometry is improved. In addition, we fusion the output of the two-side

  visual odometry by Kalman filter to improve the accuracy when the two sides both run normally. Experimental

  results under various practical environments in various velocities show that the system can output regularly

  even when one side fails and the accuracy of the output is improved when the two sides work normally.

  A multi-threshold 3D reconstruction algorithm

  based on labeled medical images

  XIAO Hong-xu,YANG Zhi-yong,JIANG Shan,HUANG Zhe,ZHAO Sheng-li

  2017, 39(10): 1870-1876. doi:

  Abstract ( 72 )   PDF (902KB) ( 126 )   　　 Review attachment

  As a traditional surface reconstruction algorithm the marching cubes (MC) is unable to extract multi-

  threshold organs at one time. We propose a multi-threshold reconstruction algorithm to divide the target area

  and surrounding tissues in the MRI image into several label values. Changing the lables of multi-threshold

  organs into brief numbers can decrease the memory space and accelerate the speed of drawing contour surfaces.

  We also define the index way of voxel vertexes and isosurface intersecting morphology of multi-threshold

  three-dimensional reconstruction, which can avoid the situation of triangle facets and vertexes reuse of the

  MC. Furthermore, the contour surface reconstruction of the multi-organ requires only one time scanning of the

  MRI image. Experimental results show that the number of facets and vertices is decreased more significantly

  when the number of organs is larger and their relationship is closer in comparison with the traditional MC

  algorithm, and the reconstruction speed is improved by 30% while the reconstruction effect is guaranteed.

  An improved sparse iterative closest point algorithm

  ZHOU You，GENG Nan，ZHANG Zhi-yi

  2017, 39(10): 1877-1883. doi:

  Abstract ( 94 )   PDF (865KB) ( 210 )   　　 Review attachment

  The sparse iterative closest point algorithm for point cloud with noise points is sensitive to the outliers

  contained in the target point cloud, and is inefficient. To solve the problems, we find the corresponding

  point-pairs based on neighborhood information to improve the sparse iterative closest point algorithm. The

  improved sparse iterative closest point algorithm firstly uses the improved registration based on the PCA to

  adjust the position of the two point clouds, and then finds the corresponding point-pairs based on

  neighborhood information. Finally we use the alternating direction method of multipliers (ADMM) to get the

  optimal transformational matrix for corresponding point-pairs. Experiments on Stanford rabbit and potted

  model show that the improved algorithm can handle the outliers contained in the target point cloud, and the

  algorithm speed can be increased by 30%.

  Murals inpainting based on generalized

  regression neural network

  REN Xiao-kang，CHEN Pei-lin

  2017, 39(10): 1884-1889. doi:

  Abstract ( 103 )   PDF (902KB) ( 200 )   　　 Review attachment

  We propose a digital inpainting and protection method for Dunghuang murals through the application of the

  generalized regression neural network. The damaged mural images are denoised with the anisotropic diffusion

  method. Morphological dilation operator is applied to extract the boundary pixels in the damaged region. The

  sample blocks of pixels similar to those around the boundary of the damaged region serve as input training

  samples of the generalized regression neural network. The pixel values of the sample blocks are input into

  the generalized regression neural network by the zigzag scanning. Adaptive smoothing parameters, in addition,

  are also used. Finally, an approximate inpainting model is obtained, which can predict the information of the

  pixels in the damaged region. Experimental results indicate that the proposed method is effective in the

  digital inpainting of murals.

  A SURF image registration algorithm based on fusion features

  QIN Yu1，WU Jing-jing 1,2，AN Wei1,2，ZHANG Mei-juan3

  2017, 39(10): 1890-1895. doi:

  Abstract ( 76 )   PDF (894KB) ( 133 )   　　 Review attachment

  The speed-up robust features (SURF) algorithm is a scale-invariant, rotation-invariant and robust

  registration algorithm. However, since the color features of the image can be lost, its registration effect

  of color images is poor. We therefore propose a SURF registration algorithm based on fusion features.

  Firstly, we utilize the color invariant and the double local binary pattern (DLBP) texture features of the

  color image to construct the grayscale of fusion features. Meanwhile, we propose an adaptive method to adjust

  the weights of fusion features based on the color histogram of the color image. Then, the SURF algorithm is

  used to extract and match the feature points on the grayscale of fusion features. Finally, the improved

  random sample consensus (RANSAC) algorithm is used to remove the mismatch points. Experimental results show

  that the proposed algorithm can effectively increase the feature points and speed up the registration rate

  for color images.

  Application of spectrum and Kuhn-Munkres

  algorithm in graph matching

   

  LI Chang-hua,LI Zhi-jie,GAO Yang

  2017, 39(10): 1896-1900. doi:

  Abstract ( 94 )   PDF (607KB) ( 141 )   　　 Review attachment

  In order to match and analyze effectively of the structured graph in the database, we present an improved

  Kuhn-Munkres algorithm based on the global similarity matrix and location similarity matrix. Firstly, we

  construct a global matrix and a location matrix from graph data. The global similarity matrix is constructed

  with the adjacency matrix and the Laplacian spectrum of feature structures. As for the location similarity

  matrix, we use the Gaussian kernel function to perform the normalized calculation of the relative position

  and construct  the matrix with the spectral features. The nodes location similarity matrix describes the

  relative position of all nodes in the graph, which can offset the drawback of the global similarity matrix,

  which means it can only depict the overall structure of the graph. Finally, we use the Kuhn-Munkres algorithm

  to do graph matching, and get the maximum weight matching in bipartite graphs. Experiments show that the

  improved Kuhn-Munkres algorithm can effectively enhance matching accuracy between nodes.

   

  A new summation multi-kernel learning

  method based on sample weighting

  SHEN Jian，JIANG Yun，ZHANG Ya-nan，HU Xue-wei

  2017, 39(10): 1901-1907. doi:

  Abstract ( 78 )   PDF (516KB) ( 152 )   　　 Review attachment

  Multi-kernel learning is a new research hotspot in current kernel machine learning field. By mapping data

  into the high dimensional space, kernel methods increase the computing performance of linear classifiers such

  as support vector machines, and it is a convenient and effective way to deal with nonlinear pattern

  recognition and classification. However, in some complex situations, such as heterogeneous data or irregular

  data, large sample size and non-flat sample distribution, the kernel learning method based on single kernel

  function cannot completely meet the requirement, so it is necessary to develop multiple kernel functions in

  order to get better results. We propose a new summation multi-kernel learning method based on sample

  weighting which can be weighted by the capability of how much a single kernel function can fit the sample.

  Experiment analysis on several data sets shows that the proposed method can obtain high classification

  accuracy.

  Target threat assessment based on

  improved grey correlation algorithm

  ZHANG Hao-wei,XIE Jun-wei,SHEN Chuan,ZHANG Zhao-jian

  2017, 39(10): 1908-1914. doi:

  Abstract ( 96 )   PDF (709KB) ( 187 )   　　 Review attachment

  Aiming at the threat assessment of targets in air defense combats, we propose a new target assessment method

  based on improved grey correlation algorithm. Time sequence weights are introduced to construct the dynamic

  threat assessment model of targets, which improves traditional methods by on-ly assessing current targets’

  threat. According to subjective and objective properties, the weights of tar-gets threat elements are

  calculated in real time, which are then converted to the same layer by using the set pair analysis theory.

  Finally, the improved grey correlation algorithm based on the technique for or-der preference by similarity

  to an ideal solution (TOPSIS) is applied to get the final targets threat order. Theoretical analysis and

  simulation results prove the reliability and validity of the method.