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

Current Issue

    • Acceleration of histogram of oriented gradient (HOG)
      based on Sunway manycore processor
       
      ZHAO Mei-ting1,2,LIU Yi1,2,LIU Rui1,2,SONG Kai-da1,2,QIAN De-pei1,2
      2017, 39(04): 611-618. doi:
      Abstract ( 193 )   PDF (1564KB) ( 502 )     
      HOG features are a simple and efficient feature descriptor commonly used for object detection. It is widely used in pedestrian detection and other fields. However, they face severe performance challenges when dealing with massive images. One of the solutions is to speed up the pedestrian detection algorithm in the context of mass images by using the Sunway SW26010 processor nodes of the SunwayTaihuLight supercomputer. We propose two methods of parallel implementation: one method is that a processor processes 4 images simultaneously, and the other is that 256 images are processed at the same time. Through a large number of serial and parallel processing experimental tests, the results show that  the first parallel implementation method can be used to process highresolution images and the speedup can reach up to 83; the second parallel implementation method can be used to process lowresolution images and the maximum speedup is 95. The results on multinode processors show that our parallel implementation methods have good scalability. 
      Design and implementation of an optimal job scheduling #br# model in the high performance computing environment 
      WANG Xiao-ning,XIAO Hai-li,CAO Rong-qiang
      2017, 39(04): 619-626. doi:
      Abstract ( 171 )   PDF (727KB) ( 428 )     
      The high performance computing environment is a computing platform, which aggregates multiple distributed high performance computers from indifferent organizations, providing users with unified access and usage patterns. The system middleware matches the appropriate highperformance computing resources according to users’job request. With the opening of the environment programming interface (API) and the substantial increase in the number of job submission requests, some job submission requests fail because of too many network connections under high concurrent job submission requests. Also, the job scheduling strategy is lack of flexibility. We propose an optimized job scheduling model in the high performance computing environment, which introduces environment job queues, refines the systemlevel status for each job, and increases the configuration of job scheduling strategy. We also implement a prototype system based on middleware SCE. Test results show that no job request fails under the workload of 200 job requests each minute in a single system service. In a total of 1000 jobs, nearly 500 job submissions are completed within 0.3 seconds, and more than 800 job submissions are completed in less than 0.5 seconds.
      A temperatureaware task scheduling algorithm for mobile devices
      MO Wen-dao1,LI Ye-da2,WEN Ang-zhan3,LIN Wei-wei3
      2017, 39(04): 627-633. doi:
      Abstract ( 124 )   PDF (638KB) ( 366 )     
      Because the volunteer distributed computing can provide sufficient computing power for the research projects needing massive computing, it is even more powerful than supercomputing. As a result, the volunteer distributed computing technology has attracted a lot of attentions so that many architectures of different volunteer distributed computing are widely used. Most of those architectures usually consider the PC computers as volunteers, or simply treat the mobile devices as PC computers. Because many characteristics of mobile devices are very different from PC computers, those architectures cannot efficiently handle the volunteer computing projects that have both PC computers and mobile devices as volunteers. In order to solve the shortcomings of two popular task scheduling methods of the volunteer distributed computing: the iteration scheduling algorithm (ISA) and the firstcomefirstserve algorithm (FCFS)) in dealing with the calculation of  mobile device volunteers, and improve the efficiency of the volunteer distributed computing platform with mobile devices volunteers, we propose a temperatureaware task scheduling algorithm (TATSA). Experimental results show that the TATSA is more efficient than the two mainstream task scheduling algorithms ISA and FCFS in mobile device volunteer computing.
       
      Distributed heterogeneous parallel Boolean
      matrix multiplication and its performance optimization
      ZHU Min,TANG Bo,ZHAO Juan,ZOU Dan,LI Jincai
      2017, 39(04): 634-640. doi:
      Abstract ( 110 )   PDF (545KB) ( 321 )      Review attachment

      The Boolean polynomial solution is a key step in the analysis of cryptographic algebra, and the F4 algorithm is an efficient algorithm for Boolean polynomial solution. We analyze the Gaussian elimination algorithm designed by Lachartre for F4 matrix, then design and implement the distributed heterogeneous (CPU + MIC) parallel algorithm for the time consumption calculation of Boolean matrix multiplication. The Boolean matrix differs from ordinary matrixes mainly in the valuetaking intervals of matrix elements. The optimization method of the general matrix multiplication cannot satisfy the Boolean matrix multiplication because the Boolean matrix element (0,1) leads to the particularity of the matrix multiplication operation. We realize the distributed heterogeneous parallel algorithms of Boolean matrix multiplication by optimizing its performance respectively on binary domain matrix storage, OpenMP multithreading organization, fetch, task partition and scheduling, etc. By randomly generating the Boolean matrix tests, the optimized distributed heterogeneous parallel program achieves an acceleration ratio of 2.45 compared with the distributed isomorphism parallel program, which shows a good performance improvement.

      A multi-source streaming data real-time
      storage system based on load balance
      GUO Hui-yun1,2,FANG Jun1,2,LI Dong1,2
      2017, 39(04): 641-647. doi:
      Abstract ( 157 )   PDF (927KB) ( 287 )     
      The perceptual streaming data of the Internet of things is mainly centered on timeseries data, and has the characteristics of a large amount of data, continuous arrival, and multiple sources and so on. When data is written in a large amount of concurrency, the existing traffic streaming data storage system based on HBase still has the problems of storage efficiency and system availability. To solve the problems, we design and implement a multisource streaming data realtime storage system based on load balance. The system expands the data proxy into a cluster architecture, presents a task scheduling algorithm based on load balance, and achieves the sequence matching between tasks and data proxy servers, thus making the data proxy cluster processing tasks in a balanced manner and achieving data storage in parallel in the HBase database. Experimental results show that the system maintains the data distribution ratio of each data agent between 0.3 and 0.4, and writes data to the HBase database at about 1.5 times the speed of the single data proxy.
       
      An improved orthogonal list based storage
      technique and its application in short circuit calculation
      HE Zhi-jun,HE Hong-ying,HUANG Xu
      2017, 39(04): 648-655. doi:
      Abstract ( 109 )   PDF (785KB) ( 297 )     

      The node admittance matrix is a sparse matrix, and the short circuit current calculation needs to query the admittance matrix data. In order to keep querying the element numerical value according to row and column and to further improve the efficiency of querying the line number according to the numerical value, which can facilitate the storage and subsequent matrix processing, we propose an improved orthogonal list method for constructing the highly balanced binary tree. Based on productive capacity table stores,  the data node pointer field is expanded so as to form a balanced binary tree. The tree’s whose height is maintained at (O(log2 n)),and its average search length is maintained at (O(log2 n)).It can reduce operation time complexity and improve the efficiency of numerical query. At the same time, in order to ensure the fairness of the test results, the time to construct the highly balanced binary tree is included in the total time for comparison. The corresponding examples verify the efficiency of the improved method.

      A hybrid-CS based optimization method
      of energy consumption in WSN
      XIE Cheng-yang,NIU Yu-gang,ZOU Yuan-yuan,XIAO Nan
      2017, 39(04): 656-662. doi:
      Abstract ( 132 )   PDF (779KB) ( 399 )     

      The energy consumption of network nodes has an important effect on network lifetime. We propose a network energy consumption optimization method based on HybridCS. Firstly, according to the number of nodes participating in data gathering, a reasonable dimension range of measurement matrix is determined in order to ensure the accuracy of date reconstruction. Secondly, by analyzing the effect of different measurement matrix dimensions on the amount of sending data, we derive a better measurement matrix dimension for HybridCS, thus the reduction of network energy consumption can be achieved. Simulation results show that the proposed method cannot only save network energy, but also ensure the accuracy of data reconstruction.

       

      A light-weight data encryption
      mechanism in wireless sensor networks
      DENG Yun,CHENG Xiao-hui
      2017, 39(04): 663-672. doi:
      Abstract ( 139 )   PDF (1162KB) ( 330 )     

      Aiming at the limited processing power, storage space, and energy of wireless sensor networks, we a design lightweight data encryption mechanism which improves the RC6 algorithm and adds in “symmetric layer” operation. The improved RC6 algorithm is easier to implement and the hardware resource consumption is smaller when the computational workload is not changed. In order to further increase the security of cipher texts and the intensity of data encryption, dual keys are applied to reencrypt the texts. In addition, a random key management mechanism is introduced, which makes the network nodes use different keys for each encryption. Thus, the security of the key is improved. Meanwhile the data encryption mechanism also adopts ID authentication and various kinds of security authentication mechanisms such as key pools with identity authentication to prevent access to illegal nodes. Based on the low power consumption CortexM3 core control chip, we design a wireless sensor network node hardware platform and a communication protocol, and the mechanism is transplanted and implemented on the hardware platform. Experimental results  reveal that the encryption mechanism can run well on the lowpower platform.

      A double connectivity recovery algorithm in partition
      based on backbone polygon in sensor networks
      QIN Ning-ning1,2,WU De-en1,YU Ying-hua1
      2017, 39(04): 673-677. doi:
      Abstract ( 148 )   PDF (526KB) ( 271 )     
      In order to solve the problem that the existing algorithms have poor fault tolerance when recovering the partition connectivity, we propose a double connectivity recovery algorithm in partition (DCRA). The algorithm aims at building a backbone polygon in the center area of the network and connecting partitions with the polygon by two disjoint paths to realize double connectivity between partitions. Simulation experiments show that compared with some existing double connectivity algorithms, the proposed algorithm cannot only reduce the number of deployed relay nodes and the running time of the algorithm by about 60%, but also quickly determine the location of the relay nodes so as to quickly recovery partition connectivity.
      A hybrid localization algorithm based on
      multifingerprint union matching
      HOU Zhenhuan,MA Yongtao,JIANG Qideng,DOU Zhi
      2017, 39(04): 678-683. doi:
      Abstract ( 162 )   PDF (799KB) ( 333 )      Review attachment

      With the rapid development of information technology, indoor localization technology has become one of the most important research hotspots in location based service (LBS). Hybrid algorithms combining the received signal strength (RSS) location fingerprinting and pedestrian dead reckoning (PDR) can effectively improve the localization accuracy, but existing algorithms can hardly achieve higher localization accuracy and smaller calculation simultaneously. The common Kalman filter algorithm has limit localization accuracy while a large amount of calculation is required by the particle filter algorithm. We propose a hybrid localization algorithm based on multifingerprint union matching, which fuses the inertial sensor and the RSS fingerprint information effectively. Under the premise of low calculation amount, it can achieve higher precision of localization. Experimental results show that, 80% of the errors remain within 1m and the average accuracy reaches as high as 0.77m.

      A parallel multi-signcryption scheme
      based on self-certified cryptography
      WANG Yun1,LU Dianjun2
      2017, 39(04): 684-688. doi:
      Abstract ( 125 )   PDF (389KB) ( 301 )      Review attachment

      Signcryption integrates the two concepts of signature and encryption, and outperforms the traditional signaturefirstencryptionthen system in computation amount and operation speed. And the selfcertified public key eliminates the need  of public key certificate management and saves cost. In view of the advantages of both, we present a parallel multiple signcryption scheme based on self certified cryptography, which makes the idea that  multiple signers can sign the same message and multiple decryptors can decrypt it simultaneously achievable. It can be widely used in electronic cash, secret key management and message  distribution of the router. The random predict theory verifies its security.

      An enhanced role-based access control model
      for multi-domains in cloud systems
      CAI Ting1,NIE Qing-bin1,OUYANG Kai2,ZHOU Jing-li2
      2017, 39(04): 689-697. doi:
      Abstract ( 127 )   PDF (818KB) ( 337 )      Review attachment

      We propose an enhanced role-based access control (ERBAC) model to solve the shortcomings of the RBAC’s resource usage constraints, policy management and interoperability security in multi-domain cloud systems. Firstly, we introduce elements of containers and two role cardinality constraints into the RBAC, and establish the containers + dynamic role cardinality constraints based resource usage policy. Secondly, we study the role inheritance management for multi-domains in depth and present an inter-domain policy management function, whose objective is to check for the number of violations before committing an inter-domain role inheritance relation. Then, various security detection algorithms for policy conflict are given. Analysis results show that the ERBAC model can improve the security of inter-domain interoperation, enforce usage constraints upon resources and manage the security policies in an easy and effective way, which proves to be feasible and applicable for multi-domain cloud systems.

      A new attack intent detection method
      based on possible graph
      LI Yan,HUANG Guang-qiu
      2017, 39(04): 698-707. doi:
      Abstract ( 156 )   PDF (815KB) ( 364 )      Review attachment

      The attack graph model which uses the causal relationship between the attack steps to infer the attack progress from the initial state to the target state is a key method for network risk assessment. And the whole analysis process is based on the graph data expressed in formal style, but few uncertainty factors such as the uncertainty degree of the network link, network congestion, and intrusion alarm, are considered. Based on the concept of uncertain graphs, we expand the attack graph content to a possible attack graph, describe the construction method for the possible attack graph, and propose a maximum probability algorithm and an algorithm to find maximum possible attack paths based on reachability. Experimental results show that we can generate the possible attack graph within acceptable time, effectively speculate the attack intentions, and provide decision-making foundation for a network administrator.

      A transformation method for AltaRica3.0
      to Promela and its verification
       
      HU Jun,CHEN Song,WANG Ming-ming
      2017, 39(04): 708-716. doi:
      Abstract ( 179 )   PDF (998KB) ( 354 )      Review attachment

      AltaRica language is used in safety critical systems modeling. It has a complete set of modeling analysis tools. However, with the AltaRica3.0 update, traditional AltaRica modeling and analysis tools like ARC are no longer supportive, and the SPIN as an exhaustive model verification tool is widely used. We briefly introduce the improvement of AltaRica3.0 over the previous version in terms of expressive ability and the basic structure of the underlying model GTS. Based on the idea of AltaRica3.0 flattening into the GTS model, we propose a conversion rule for AltaRica3.0 model transformation to the Promela model. Taking the civil aircraft wheel brake system (WBS) as an example, the AltaRica3.0 model is established and transformed into the Promela model by the conversion rule. Finally, according to the safety requirements of the WBS in 4761, the SPIN tool is used to verify the safety property of the WBS.

      Deductive proof of security-relevant
      properties under bounded constraints
      LONG Teng1,2,XU Zhi-wu3
      2017, 39(04): 717-724. doi:
      Abstract ( 122 )   PDF (521KB) ( 371 )      Review attachment

      Security-relevant properties such as access control in a complex environment play a very important role. In terms of procedural verification, not only the safety and activity verification are considered, but the nature of some security policies, such as non-interference, should also be considered. These security policies that cannot be described by the general nature can be considered as “hypersafety”. Boundary constraints are common to represent different degrees of access frequency restrictions. They are one of the effective auxiliary methods in safety-related property verification, and have wide application value in the attribute verification of wireless sensor network protocols, embedded systems and other important fields. Based on the above description, we propose an approach for extracting deductive proof of security-relevant properties under bounded constraints.

      Computing minimal cut sets of fault tree using SAT solver
      LUO Wei-lin,WEI Ou,HUANG Ming-yu
      2017, 39(04): 725-733. doi:
      Abstract ( 189 )   PDF (565KB) ( 438 )      Review attachment

      Fault tree analysis is widely used in the safety analysis of safety crisis areas such as nuclear industry, aerospace engineering, traffic control, etc. It is the key step to solve the minimal cut sets of fault tree in fault tree analysis. The conventional algorithms solving the minimal cut sets of large-scale fault tree are mainly based on the binary decision diagram. Their main drawback is that the time and space consumption of the algorithm relies heavily on a good order of variables. In order to reduce the storage resources and speed up the process, we propose a new algorithm based on Boolean satisfiability problem to solve the minimal cut sets in fault tree analysis. Firstly, we convert this problem into a Boolean satisfiability problem. Secondly, the SAT solver is used to solve the minimal satisfiability of the Boolean formula, namely the minimal cut sets of the fault tree, through the iteration of above processes. Experimental results show that compared with conventional algorithms, this new algorithm is not only more accurate but also more efficient for solving the minimal cut sets in fault tree analysis.

      Property guided symbolic execution
      based bug detection of Linux Drivers
      CHEN Ying-jie,CHEN Zhen-bang,DONG Wei
      2017, 39(04): 734-739. doi:
      Abstract ( 126 )   PDF (467KB) ( 363 )      Review attachment

      Device drivers constitute an important part of an operation system (OS). The reliability of device drivers is critical to the security and reliability of OSs. We propose a property guided symbolic execution based framework for the bug detection of Linux device drivers. To analyze multiple properties simultaneously, we propose a  multiple properties guided symbolic execution method. Based on the LLVM and KLEE, the framework and the property guided method are implemented. The results of the preliminary experiments on real world Linux drivers demonstrate the effectiveness and efficiency of the proposal.

      An abstract domain based on
      two-interval octagonal constraints
      DING Ze-wen1,GUO Hong-chang2,KAN Shuang-long1,ZHANG Chi1
      2017, 39(04): 740-747. doi:
      Abstract ( 149 )   PDF (690KB) ( 316 )      Review attachment

      Static program analysis with abstract interpretation has been successfully applied to industry in order to avoid runtime errors and ensure the correctness of the software. Abstract domain is one of the important aspects in abstract interpretation theory. However, most of the existing numerical abstract domains cannot express non-convex properties. These limitations often affect the precision of numerical analysis and even lead to more false alarms.We propose a numerical abstract domain based on two-interval octagonal constraints. This abstract domain allows us to represent invariants of the form x±y∈[a,b]∪[c,d], where x  and y are variable values and a,b,c,d∈R. Domain elements in this abstract domain are represented by two-interval octagonal constraints, so the new abstract domain can express certain non-convex properties and is more expressive than the octagon abstract domain, with only a small overhead in the computational complexity of domain operation.

      Camera self-calibration based on multiple view images
      TANG Qiu-hu,ZHANG Zhi-yi
      2017, 39(04): 748-755. doi:
      Abstract ( 186 )   PDF (1050KB) ( 554 )      Review attachment

      Camera calibration is an essential step of 3D reconstruction. Conventional calibration methods require high precision equipment and sophisticated operations. Compared with them, camera self-calibration is simple but has low precision, which leads to significant performance degradation of 3D reconstruction. Therefore, there is a growing need for a simple and accurate high precision self-calibration method. By using the bundle adjustment algorithm and SIFT points matching relationship, we propose a local-global hybrid iterative optimization method. As for the large number of matching features, we propose a neighborhood image matching method, which can significantly reduce the matching time under the premise of maintaining accuracy. Experimental results show that the proposed method is effective  and accurate, and it can reduce the time consumption of image matching. Based on the relationship between corresponding  matching points in multi view images, our method makes full use of the local-global hybrid idea to compute the parameters of the camera. Compared with other existing methods, it is more robust with higher precision.

      Design and implementation of a multi-source space science
      data visualization and management system based on 3D-earth
      JIAO Peng1,2,3,LI Sheng-yang1,2,LIU Zhi-wen1,2,YU Hai-jun1,2,HAO Zhong-weng1,2
      2017, 39(04): 756-762. doi:
      Abstract ( 109 )   PDF (1234KB) ( 379 )      Review attachment

      How to efficiently organize and manage growing massive multi-sourcespace science data and enhance the availability and usability of data is a key technical problem to solve. Based on a full analysis of existing space science data management technologies and data characteristics, we propose an effective system architecture. Spatial relational database and distributed database technology are studied and utilized to achieve efficient storage, retrieval and positioning of massive heterogeneous data.The key technologies of levels of details display, 3D data clipping, and parallel loading via multi-thread based on 3D digital earth are studied so as to improve the efficiency of integrated visualization and application for space science data. Finally, we design and integrate a multi-source space science data visualized organization and management system. Practical engineering application results show the rationality and validity of the system design.