Started in January,1974(Monthly)
Supervised and Sponsored by Chongqing Southwest Information Co., Ltd.
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
Editors
Current Issue
Volume 46 Issue 8, 15 August 2019
  
Big Data & Data Science
Overview on Multi-agent Reinforcement Learning
DU Wei, DING Shi-fei
Computer Science. 2019, 46 (8): 1-8.  doi:10.11896/j.issn.1002-137X.2019.08.001
Abstract PDF(1381KB) ( 6687 )   
References | Related Articles | Metrics
Multi-agent system is a distributed computing technology,which can be used to solve problems in various fields,including robot system,distributed decision-making,traffic control and business management.Multi-agent reinforcement learning is an important branch in the field of multi-agent system research.It applies reinforcement learning technology and game theory to multi-agent systems,enabling multiple agents to complete more complicated tasks through interaction and decision-making in higher-dimensional and dynamic real scenes.This paper reviewed the recent research progress and development of multi-agent reinforcement learning.Firstly,the theoretical background of multi-agent reinforcement learning was introduced,and the learning objectives and classical algorithms of multi-agent reinforcement learning proposed in the literature were reviewed,which are respectively applied to complete cooperation,complete competition and more general (neither cooperation nor competition) tasks.Secondly,the latest development of multi-agent reinforcement learning was summarized.With the maturity of deep learning technology in recent years,in more and more complex realistic scene tasks,researchers use deep learning technology to automatically learn abstract features of massive input data,and then use these data to optimize the decision-making of agents in reinforcement lear-ning.Recently,researchers have combined deep learning and other technologies to improve and innovate algorithms in different aspects,such as scalability,agent intent,incentive mechanism,and environmental framework.At the end of this paper,the prospect of the application of multi-agent reinforcement learning were summarized.Multi-agent reinforcement learning has made good progress in the fields of robot system,man-machine game and autonomous driving,and will be applied in the fields of resource management,transportation system,medical treatment and finance in the future
Survey on Meta-event Extraction
GAO Li-zheng, ZHOU Gang, LUO Jun-yong, LAN Ming-jing
Computer Science. 2019, 46 (8): 9-15.  doi:10.11896/j.issn.1002-137X.2019.08.002
Abstract PDF(1308KB) ( 3594 )   
References | Related Articles | Metrics
Event extraction is an important branch of information extraction.It is widely used in intelligence collection,knowledge extraction,document summarization,question answering,etc.This paper presented a survey on meta-event extraction which attracts most attention in event extraction.It firstly interpreted the basic concepts of meta-event and meta-event extraction and briefly introduced the main implementation methods of meta-event extraction.Then it focused on the tasks of meta-event extraction,highlighted the task of meta-event identification,and briefly introduced other tasks.Finally,it summarized the problems of current meta-event extraction and predicted the trend of meta-event extraction
Study on Clustering Mining of Imbalanced Data Fusion Towards Urban Hotspots
CAI Li, LI Ying-zi, JIANG Fang, LIANG Yu
Computer Science. 2019, 46 (8): 16-22.  doi:10.11896/j.issn.1002-137X.2019.08.003
Abstract PDF(3223KB) ( 1399 )   
References | Related Articles | Metrics
In the era of big data,multi-source data fusion is a trending topic in the field of data mining.Previous studies have mostly focused on fusion models and algorithms of balanced data sets,but seldom on issues of clustering mining for imbalanced data sets.DBSCAN algorithm is a classical algorithm for mining urban hotspots.However,it cannot deal with imbalanced location data,and the clustering results generated by the minority class are difficult to discovery.Aiming at the imbalanced data fusion,this paper proposed a novel fusion model based on spatio-temporal features,at the same time,proposed a novel approach to solve the mining problem of imbalance data from data aspect and algorithm aspect.Since the evaluation index of current clustering algorithm is not suitable for the evaluation of unbalanced data clustering results,a new comprehensive evaluation index was proposed to reflect the clustering quality.GPS trajectory data (the majority class data) from the traffic field and microblog check-in data (the minority class data) from the social field are fused,and then the proposed method is used to mine hot spots.The mining results of hot spots based on multi-source data fusion are better than those of single source data fusion.The location,distribution and number of hot spots are consistent with the actual situation.The proposed fusion model algorithm and evaluation index method are effective and feasible,and can also be used for the fusion and analysis of location data from other sources
Important Location Identification of Mobile Users Based on Trajectory Division and Density Clustering Method
YANG Zhen, WANG Hong-jun
Computer Science. 2019, 46 (8): 23-27.  doi:10.11896/j.issn.1002-137X.2019.08.004
Abstract PDF(1834KB) ( 991 )   
References | Related Articles | Metrics
As emerging spatial trajectory data,mobile user trajectory data can be used to analyze individual or group behavioral characteristics,hobbies and interests,and are widely used in smart cities,transportation planning,and anti-terrorism maintenance.In order to identify the important locations of mobile user from a huge data set,this paper proposed a trajectory division method based on the angle and distance offset.The method firstly extracts the important locations candidate set by trajectory division,and then further clusters the important locations through an improved density clustering algorithm,extracting the final important location of user.The experiment on Geolife trajectory data set and Foursquare data set shows that the important location identification method combining trajectory division and density clustering has higher accuracy than other existing important location identification method,which proves the feasibility and superiority of the proposed method
Integrating Dynamic Collaborative Filtering and Deep Learning for Recommendation
DENG Cun-bin, YU Hui-qun, FAN Gui-sheng
Computer Science. 2019, 46 (8): 28-34.  doi:10.11896/j.issn.1002-137X.2019.08.005
Abstract PDF(1806KB) ( 1049 )   
References | Related Articles | Metrics
In the era of information explosion,the recommendation system plays an enormous role in reducing information overload.At present,the recommendation system generally uses the traditional collaborative filtering algorithm to learn the hidden vector in the user-item behavior matrix,but it has the problem of data sparseness and cold start,and does not consider the customer preferences and the popularity dynamics of items.This greatly limits the accuracy of the recommendation system.Some scholars have used the deep learning model to learn the features of the auxiliary information to enrich the features of the collaborative filtering algorithm,and achieved certain results,which does not fully solve all the problems.This paper took film recommendation as the research object,and proposed a recommendation algorithm that combines dynamic collaborative filtering and deep learning.Firstly,the dynamic collaborative filtering algorithm incorporates temporal features.Secondly,it uses deep learning model to learn user and movie feature information to form the hidden vector of user features and movie features in high-dimensional latent space.Finally,it is integrated into the dynamic collaborative filtering algorithm.Extensive experiments on MovieLens datasets show that the proposed method improves the accuracy of film score prediction
Node Selection Scheme for Data Repair in Heterogeneous Distributed Storage Systems
ZHONG Feng-yan, WANG Yan, LI Nian-shuang
Computer Science. 2019, 46 (8): 35-41.  doi:10.11896/j.issn.1002-137X.2019.08.006
Abstract PDF(1632KB) ( 683 )   
References | Related Articles | Metrics
In recent years,the growth of massive data poses severe challenges to existing storage systems,including storage cost and data reliability requirements.Because erasure code can provide higher data reliability under the same storage overhead,it has been paid wide attention.However,the coding characteristics of erasure code increases the extra overhead for the storage system using erasure code,in the process of data repair,such as computing,scheduling,transmission,disk reading and writing,and so on.In recent years,the study of erasure code data recovery is based on the assumption that each node in the distributed storage system is indiscriminate.In a large scale of data center,however,equipment replacement,hardware failure and other reasons may not only cause data loss,but also lead to different sto-rage cost of each storage node in the data center,so that the amount of data stored on each storage node is not always the same,this phenomenon is called storage capacity isomerism.The repair process under the heterogeneous storage capacity is faced with the selection of the providers.It is necessary to design a node selection strategy to make the repair cost lower,and improve the reliability and availability of the storage system.Based on the different transformation cost of nodes participating in repair in the actual repair process of data,this paper proposed a node selection strategy,namely tree topology repair algorithm,to reduce the cost of repair in the whole repair process.The simulation results show that the proposed tree selection strategy can further reduce the cost of data repair compared with the fixed node selection strategy of IFR code
Spatio-Temporal Evolution of Geographical Topics
SUN Guo-dao, ZHOU Zhi-xiu, LI Si, LIU Yi-peng, LIANG Rong-hua
Computer Science. 2019, 46 (8): 42-49.  doi:10.11896/j.issn.1002-137X.2019.08.007
Abstract PDF(3747KB) ( 1030 )   
References | Related Articles | Metrics
The tweets posted by users in social media record a wide variety of user information.The text information includes various topics contained in the tweet.It is very important to analyze the temporal and spatial evolution of topics from these messages.Based on the tweet data,this paper designed a set of visual analysis process to mine the tweet information and display the spatiotemporal evolution process of the tweet topic through user interaction.Specifically,based on the partial historical tweet data,the global geographic space is divided by the DBSCAN clustering algorithm combined with the Tyson polygon.For the user to query the search topic of interest,the index finds all relevant tweet content and binds the information to the cluster center.Finally,the temporal and spatial evolution of the topic is demonstrated by the design of multiple combined time series clustering algorithms and visualization components of the adaptive algorithm.Through the experiment and analysis of the tweet data stored in the API provided by Twitter official website,the improved visual view adaptive layout algorithm effectively solves the problem of graphic occlusion and fully displays the temporal and spatial evolution mode of the tweet.The division of geographic regions and visualization components can effectively help researchers analyze the temporal and spatial evolution of tweets,as well as the distribution of hot topics of global concern
User Reviews Clustering Method Based on Topic Analysis
ZHANG Hui-bing, ZHONG Hao, HU Xiao-li
Computer Science. 2019, 46 (8): 50-55.  doi:10.11896/j.issn.1002-137X.2019.08.008
Abstract PDF(1997KB) ( 1100 )   
References | Related Articles | Metrics
The rational clustering analysis of user reviews in social business is beneficial to providing accurate service or recommendation information.This paper proposed a user reviews clustering method based on topic analysis.According to the mutual information intensity of topic words in user reviews and the similarity between topic words,the weight of topic words is calculated,and the topic vector of user reviews is constructed.On this basis,an adaptive canopy+kmeans clustering algorithm based on user comment similarity to automatically select the initial threshold of canopy clustering algorithm is proposed,which is used to cluster and analyze the subject vector.On Amazon’s review data,the results show that the proposed method makes full use of the weight of different topic words in the user’s reviews and improves the disadvantage of the K-means clustering algorithm easily falling into the local optimal.Compared with the traditional LDA+K-means algorithm,the proposed method can achieve better results
Method for Generating Massive Data with Assignable Distribution
LI Bo-jia, ZHANG Yang-sen, CHEN Ruo-yu
Computer Science. 2019, 46 (8): 56-63.  doi:10.11896/j.issn.1002-137X.2019.08.009
Abstract PDF(2253KB) ( 828 )   
References | Related Articles | Metrics
Affected by factors such as privacy protection,corporate and government data are slow to be exposed.At the same time,due to the influence of network bandwidth,it is difficult for scientific research institutions to download and use massive public data.It is rare that the existing data generation tools can concurrently meet the requirements of scien-tific research work in terms of the generation of data distribution pattern,correlation,accuracy and scalability of the system.Specific to the problem of mass data generation,this paper put forward a distributed data generation model.According to the data distribution pattern and correlative relation specified in the user’s configuration,the reservoir sampling or random sampling algorithm is used for the sampling,calculation of relative relationship and splicing of the Web data knowledge base to generate the data of which the attribute accords with the user’s configuration.Through the data generation test on the distributed computing engine Apache Spark,the generated data meets the specified data distribution and correlation requirements,and the data generation speed is linear with the data size and cluster size from the statistical point of view.It shows that the data generated by the proposed data method has high accuracy and diversity of distribution,and the proposed data generation system has good scalability
Alert Correlation Algorithm Based on Improved FP Growth
LU Xian-guang, DU Xue-hui, WANG Wen-juan
Computer Science. 2019, 46 (8): 64-70.  doi:10.11896/j.issn.1002-137X.2019.08.010
Abstract PDF(2158KB) ( 967 )   
References | Related Articles | Metrics
The original alerts generated by intrusion detection system have some shortcomings,such as low level,mutual isolation and irrelevance,which makes security managers be difficult to find unknown and high-level security threats and cannot understand the overall security situation of the target network.In order to make use of low-level alerts to construct attack scenarios,this paper analyzed the existing alert correlation knowledge,and proposed a new alert correlation algorithm based on data mining to solve the problem of poor performance of existing algorithms when dealing with sparse data.In this paper,firstly,the existing alert correlation algorithms were compared,then the principles and merits and demerits of classical Apriori algorithm and FP growth algorithm were elaborated,and the FP growth algorithm was improved based on two-dimensional table.Finally,the improved algorithm was used to mine the association rules between the alerts,and thus the alert correlation was proceeded.In order to verify the feasibility and performance of the proposed method,the Darpa data set is utilized to carry out relevant simulation tests.The experimental results show that the proposed scheme can achieve better alert correlation.
Log-induced Morphological Fragments Process Clustering Method
SUN Shu-ya, FANG Huan, FANG Xian-wen
Computer Science. 2019, 46 (8): 71-77.  doi:10.11896/j.issn.1002-137X.2019.08.011
Abstract PDF(1797KB) ( 606 )   
References | Related Articles | Metrics
In the business process management system,there may be many different arrangements of several event sets in the task flow for performing the same purpose.Corresponding to the logs,it shows that many logs have many changes,but also have some common characteristics of many services.Therefore,extracting the commonality of the logs behavior and clustering multiple similar logs of the similar type of business system have positive significance for the business integration of similar processes.This paper proposed an approach of process clustering method.Firstly,low-frequency events are filtered out,and common high-frequency fragments from the morphological fragments in the log are extracted by automata.And then the extracted public high-frequency fragments are converted into clusters of similar logs through automation formal method.Then,a morphological fragment-based approach is proposed.A business combination algorithm is generated for those frequent execution paths of the commonality of the process model.By combining similar equivalent morphological fragments for business combination,a fused Petri net model is obtained.Finally,a practical case is proposed to verify the feasibility and validity of the proposed method
Diverse Video Recommender Algorithm Based on Multi-property Fuzzy Aggregate of Items
ZHANG Yan-hong, ZHANG Chun-guang, ZHOU Xiang-zhen, WANG Yi-ou
Computer Science. 2019, 46 (8): 78-83.  doi:10.11896/j.issn.1002-137X.2019.08.012
Abstract PDF(2235KB) ( 753 )   
References | Related Articles | Metrics
In order to improve the diversity of the collaborative filtering recommender system of videos,this paper proposed a diverse videos collaborative filtering recommender algorithm based on multi-property aggregate.According to the history of interaction between users and recommendation system,users are judged whether they are satisfied with the recommendation items of the system.If a user watches the videos on the same topic produced by different video authors,it indicates that this user shows high diversity to the video authors,and low diversity to the video subjects.Information entropy and user profile length are used to evaluate the diversity of each item’s attributes.According to the combination of the two indicators,the user’s diversity of each item’s attributes is divided into four quadrants,and the user’s diversity is fuzzified to obtain the membership degree of user’s diversity to the four quadrants.In the first phase,it predicts the rates of unrated items.In the second phase,it re-ranks all items,which improves the diversity of recommendation list.At last,experimental results based on the public Movielens 1M dataset show that,the proposed algorithm can realize the similar accuracy with top-N algorithm,at the same time,it enhances the diversity effectively.In the application scenario of balancing recommendation accuracy and diversity,setting appreciate parameters can improve the individual diversity,total diversity and freshness significantly with acceptable recommendation accuracy reduction
HPC China 2018
Scalable Parallel Finite Volume Lattice Boltzmann Method Based on Unstructured Grid
XU Lei, CHEN Rong-liang, CAI Xiao-chuan
Computer Science. 2019, 46 (8): 84-88.  doi:10.11896/j.issn.1002-137X.2019.08.013
Abstract PDF(2668KB) ( 815 )   
References | Related Articles | Metrics
Although the lattice Boltzmann method (LBM) has become an effective and promising approach in computational fluid dynamics (CFD),it is still difficult to simulate large-scale flow field with complex geometric boundaries.In this paper,the finite volume lattice Boltzmann method with cell-centered scheme on unstructured grids was given.The convective fluxes are evaluated by low-diffusion Roe scheme,and the gradients of the particle distribution function are computed with Green-Gauss approach.In order to simulate large-scale complex flow field,a parallel algorithm for the finite volume lattice Boltzmann method on unstructured grids was presented.In this method,ParMETIS is applied to partition the unstructured mesh,and then the partitioned meshes are sent to the MPI processes.The parallel performance of two kinds of meshes are compared.The correctness of the parallel algorithm was verified by two benchmark flows:1)the lid-driven flow with Re=400,1 000,3 200,5 000;2)the steady viscous flowpast a circular cylinder with Re=10,20,40.The results of parallel numerical experiments show that the parallel algorithm still has good scalability on 1 920 cores,which achieves 78.42% efficiency on 1 920 cores compared with 240 cores
HPIC-LBM Method Based Simulation of Large Temporal-Spatial Scale 3D Turbulent Magnetic Reconnection on Supercomputer
YAN Hui, ZHU Bo-jing, WAN Wen, ZHONG Yin, David A YUNE
Computer Science. 2019, 46 (8): 89-94.  doi:10.11896/j.issn.1002-137X.2019.08.014
Abstract PDF(5112KB) ( 946 )   
References | Related Articles | Metrics
Large temporal-spatial scale turbulent magnetic reconnection (LTSTMR) is a general explosive astrophysical phenomena in space physics,solar physics and cosmology.To investigate this phenome,the mechanism of magnetic energy transfer-release-dissipation,plasma heating and acceleration of high energy particle should be learned,where the key is the role of turbulence.Previous 2D/2.5D simulation can only provide simplified physical pictures,which ignores the 3D nature and properties.By HPIC-LBM simulation on Tianhe-2 from National Supercomputer Center in Guang Zhou (NSCCGZ) with up to 100 000 CPU cores,the existence of oblique instability was firstly proved from fine structure simulation (0~500 km) of solar atmosphere activities.It also presented three kind of macroscopic representation inside the dissipation area:self-generating-organization,self-feeding-sustaining and interaction between magnetic field and plasma.This research provides a new tool for investigating 3D LTSTMR phenomenon on supercomputer
Performance Evaluation of ARM-ISA SoC for High Performance Computing
WANG Yi-chao, LIAO Qiu-cheng, ZUO Si-cheng, XIE Rui, LIN Xin-hua
Computer Science. 2019, 46 (8): 95-99.  doi:10.11896/j.issn.1002-137X.2019.08.015
Abstract PDF(2828KB) ( 1606 )   
References | Related Articles | Metrics
In order to compare the performance of Intel Xeon processor for high performance computing,this paper eva-luated an ARM-ISA based-SoC floating point computing capacity,memory access bandwidth and latency.Computing capacity of double floating point on this is about 475 GFLOPS that is only 66% of Intel Xeon E5-2680v3.Memory bandwidth is 105 GB/s,better than Xeon processor.Moreover,this paper ported 4 scientific computing applications including stencil method on this SoC.The experiments show that the performance of two stencil applications on this SoC is close to that on Intel Xeon processors,and thread mapping for cache locality is a kind of performance optimization methods for this SoC.More performance study later on the new generation ARM Server SoC will be explored
Low-power Mapping Method for Three-dimensional Network on Chip Based on Hybrid Chaotic Big Bang-big Crunch
FAN Xing-ran, SONG Guo-zhi, LI Jia-zheng
Computer Science. 2019, 46 (8): 100-105.  doi:10.11896/j.issn.1002-137X.2019.08.016
Abstract PDF(2029KB) ( 704 )   
References | Related Articles | Metrics
Three-dimensional network on chip (3D NoC) is envisioned as a way to achieve high performance of multi-processor systems.For the design of 3D NoC,how to properly allocate IP cores on a given application feature map (APCG) to the 3D NoC architecture is the key problem of IP core mapping.An excellent mapping algorithm and a reasonable mapping can greatly improve the power consumption,heating,delay and other indicators of network-on-chip.The big bang-big crunch (BB-BC) algorithm is a new type of meta-heuristic swarm intelligence optimization algorithm.The hybrid chaotic big bang-big crunch (HCBB-BC) is a modified algorithm based on the big bang-big crunch (BB-BC) algorithm,which has simple parameters and fast convergence speed.In this paper,the hybrid chaotic big bang-big crunch (HCBB-BC) was proposed to solve the problem of 3D NoC mapping.This is the first time that big bang-big crunch (BB-BC) algorithm is used to solve the 3D NoC mapping problem.Simulations are conducted to prove that the proposed method requirs less number of iterations and time to find a better solution and can reduce energy consumed compared with existing NoC mapping algorithms.Under the condition of the classical task graphs,compared with the genetic algorithm (GA) algorithm,the convergence speed of the hybrid chaotic big bang-big crunch (HCBB-BC) is increased by 36.73%,and the 22.45% improvement is witnessed compared with the particle swarm optimization (PSO) algorithm.The average power consumption of the hybrid chaotic big bang-big crunch (HCBB-BC) mapping is lower than that of GA with the maximum as 5.75%,and lower than that of PSO with the maximum as 3.90%.Under the condition of the random tasks,the hybrid chaotic big bang-big crunch (HCBB-BC) algorithm can still maintain stable optimization efficiency and higher convergence speed
GPU-accelerated Non-negative Matrix Factorization-based Parallel Collaborative Filtering Recommendation Algorithm
KANG Lin-yao, TANG Bing, XIA Yan-min, ZHANG Li
Computer Science. 2019, 46 (8): 106-110.  doi:10.11896/j.issn.1002-137X.2019.08.017
Abstract PDF(1889KB) ( 1134 )   
References | Related Articles | Metrics
Collaborative filtering (CF) is widely used in recommendation systems.However,with the increase of user and item number,the efficiency of collaborative filtering algorithm and the correctness of the result will be greatly reduced.To solve this problem,this paper proposed a GPU-accelerated non-negative matrix factorization(NMF)-based parallel collaborative filtering algorithm.By utilizing the advantages of data dimensionality reduction and feature extraction of NMF,as well as the multi-core parallel computing mode of CUDA,dimension reduction and user similarity are realized.The proposed algorithm improves the recommendation accuracy and also reduces the computational cost,which can better solve the sparseness and scalability of CF-based recommendation system,and generate accurate and persona-lized recommendations quickly.The new algorithm was evaluated on a NVIDIA CUDA device using real MovieLens datasets.Experimental results show that,NMF-based collaborative filtering outperforms traditional User-based and Item-based CF with higher processing speed and higher accuracy recommendations
Deep Neural Network Recommendation Model Based on User Vectorization Representation and Attention Mechanism
GUO Xu, ZHU Jing-hua
Computer Science. 2019, 46 (8): 111-115.  doi:10.11896/j.issn.1002-137X.2019.08.018
Abstract PDF(1953KB) ( 1331 )   
References | Related Articles | Metrics
With the rapid development of Internet application,recommendation system,as an effective measure to solve information overloading,has become a research hot topic in industry and academia.Traditional recommendation algorithms for users’ implicit feedback are mainly based on collaborative filtering and learning-to-rank method,which do not make full use of the implicit feedback features in users’ behaviors.In this paper,a users’ vectorization representation model based on neural network was proposed,which can make full use of heterogeneous implicit feedback features of users’ behaviors.At the same time,referring to the self-attention mechanism in machine translation,this paper designed a neural attentive recommendation model which integrates the dynamic temporal features of user-item interaction and user vectorization representation,to improve the performance of the recommendation system.The comparison experiment is conducted on two public datasets,and the recommendation performance is evaluated by recall,precision and NDCG.Compared with other recommendation models for implicit feedback,the proposed recommendation model has better recommendation performance and better generalization ability
Network & Communication
Efficient Intra-domain Routing Protection Algorithm Based on i-SPF
GENG Hai-jun, YIN Xia
Computer Science. 2019, 46 (8): 116-120.  doi:10.11896/j.issn.1002-137X.2019.08.019
Abstract PDF(1870KB) ( 666 )   
References | Related Articles | Metrics
LFC(Loop-Free Criterion)has been proposed to cope with all the single link failure scenarios.However,the existing LFC implementation algorithms are time-consuming and require a large amount of router CPU resources.Therefore,this paper studied how to reduce the computational overhead of the LFC implementation,and proposed an efficient Intra-domain routing protection algorithm based on i-SPF (ERPISPF).Theoretical analysis indicates that the time complexity of ERPISPF is less than that of constructing a shortest path tree,and ERPISPF can compute all the valid LFC next-hop sets for any source-destination pairs.The experiment results show that ERPISPF reduce more than 93% computation overhead compared with the LFC,and can provide the same protection ratio with LFC
Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios
LIAO Yong, YANG Xin-yi, XIA Mao-han, WANG Bo, LI Shou-zhi, SHEN Xuan-fan
Computer Science. 2019, 46 (8): 121-126.  doi:10.11896/j.issn.1002-137X.2019.08.020
Abstract PDF(2186KB) ( 692 )   
References | Related Articles | Metrics
Aiming at the technical challenges brought by the fast time-selective and frequency-selective channel characteristics of high-speed mobile to Multiple Input Multiple Output (MIMO)system precoding,this paper proposed a user scheduling scheme based on greedy algorithm,which schedules and ranks users with the goal of maximizing channel capacity.Further,this paper proposed an improved Tomlinson-Harashima precoding (THP)algorithm based on greedy algorithm for user scheduling.The channel matrix is reconstructed according to the user scheduling result,and the reconstructed channel matrix is applied to the THP algorithm to optimize the traditional THP algorithm,improving the precoding precision.The simulation results show that the proposed precoding has better Bit Error Ratio (BER)performance and channel capacity than traditional precodings,and its robust performance is also better,which verifies that the proposed algorithm can adapt to high-speed mobile scenarios effectively
Utility Function Heterogeneous Network Access Algorithm Based on Green Energy Perception
FANG Xu-yuan, TIAN Hong-xin, SUN De-chun, DU Wen-cong, QI Ting
Computer Science. 2019, 46 (8): 127-132.  doi:10.11896/j.issn.1002-137X.2019.08.021
Abstract PDF(2271KB) ( 627 )   
References | Related Articles | Metrics
In the 5G mobile communication network,a large number of communication base stations using green and grid energy mixed power supply can reduce operating costs significantly.Aiming at the problem of user access of base stations supplied by hybrid energy in heterogeneous networks,a comprehensive utility function access algorithm based on green energy perception and a green energy perception based comprehensive utility function adjustment algorithm were proposed.The user first calculates the utility value according to the green energy status of the base station,the access signal-to-noise ratio and other access selection parameters,and selects the base station with the smallest utility va-lue to access.After the user accesses the base station,the algorithm adjusts the access user through the base station to reduce the cost of energy costs.By using MATLAB platform,simulation results show that the GEPC algorithm can reduce the total energy consumption cost more effectively at low load compared to RSRP (based on user received signal power)and SINR (based on user maximum signal to interference and noise ratio) algorithm.Compared with the NEAT (Green Energy User Awareness Access) algorithm,the GEPCA algorithm significantly improves the utilization of green energy to 90% and is beneficial to heterogeneous network load balancing at high load
Hybrid Filtering Algorithm Based on RSSI
NI Xiao-jun, GAO Yan, LI Ling-feng
Computer Science. 2019, 46 (8): 133-137.  doi:10.11896/j.issn.1002-137X.2019.08.022
Abstract PDF(1934KB) ( 969 )   
References | Related Articles | Metrics
Received signal strength index (RSSI) based ranging technology is widely used in wireless sensor network (WSN)positioning technology,because of its low cost and low complexity.The RSSI value is easily affected by the environment,even if the RSSI value collected at the same location is subject to fluctuations and abrupt changes,thus the ranging error is large.Based on the analysis of RSSI ranging principle and the current common filtering algorithm,this paper proposed a hybrid filtering algorithm based on Dixon test filtering,median filtering and gaussian filtering by comparing the effect of single filtering through experiments and taking advantage of the significant effect of filtering.Firstly,the linear regression algorithm is used to optimize the parameters of the RSSI ranging model,and then the optimal value is obtained by filtering the abnormal RSSI value through the hybrid filter to achieve accurate ranging.The experimental results show that compared with a single filtering algorithm,the hybrid filtering algorithm can significantly reduce the fluctuation of the RSSI value,and eliminate the abnormal RSSI value more effectively.The filtered RSSI value is closer to the ideal value,and the ranging error is smaller.It proves that the hybrid filtering algorithm is effective and feasible
Study on Attack Strategy and Robustness of Complex Weighted Supply Chain Network
ZHAO Zhi-gang, ZHOU Gen-gui, LI Hu-xiong
Computer Science. 2019, 46 (8): 138-144.  doi:10.11896/j.issn.1002-137X.2019.08.023
Abstract PDF(2949KB) ( 905 )   
References | Related Articles | Metrics
This paper studied how to improve the robustness of complex supply chain network under different attack strategies.First of all,the priority connection parameters of the complex weighted supply chain network were adjusted,the evolutionary process of the actual network was simulated,supply chain network’s degree distribution function and betweenness distribution function were analyzed,and its scale-free characteristics were verified.Then,various attack strategies of weighted supply chain network were studied.The statistics on relative size of maximal connected subgraph and network efficiency index of supply chain network were conducted,and the robustness of network was analyzed.The simulation results show that the node degree attack and the blend attack are more destructive for node attack strategy,and double-point betweenness attack is more destructive for edge attack strategy.The robustness of network can be improved by changing network’s evolution mechanism,which provides certain research thoughts on how to optimize network design,protect few important nodes and edges in the network and improve network invulnerability in practical works
Advanced MDS-MAP Localization Algorithm with Clustering and Fusion Compensation Strategy
WANG Jing, QIU Xiao-he
Computer Science. 2019, 46 (8): 145-151.  doi:10.11896/j.issn.1002-137X.2019.08.024
Abstract PDF(1952KB) ( 635 )   
References | Related Articles | Metrics
The classic multi-dimensional scaling positioning (MDS-MAP)algorithm has the problem of high energy consumption and low positioning accuracy in large-scale wireless sensor networks.The improved MDS-MAP algorithm evaluates the residual energy,the balance of energy consumption and the local density of the cluster head when nodes are used as cluster heads and then the clustering is performed.The clusters have good connectivity and low energy loss.To overcome the limitation of the flattening rule,this paper proposed a method to obtain the unknown Euclidean distance between nodes,and the method of angle discrimination was used for eliminating the solution of interference.After compensating for common nodes,the improved rules was applied to the inter-cluster merging.Simulation and comparison results indicate that the proposed advanced MDS-MAP localization algorithm with clustering and fusion compensation strategy has lower splitting requirements,high positioning accuracy and robustness,which is good for the network expansion and the reduction of positioning power consumption
Transmission Scheme for Asymmetric Two-way Relay X Channel Based on Delayed CSIT
LIU Feng, GE Pei-xin, ZENG Lian-sun
Computer Science. 2019, 46 (8): 152-156.  doi:10.11896/j.issn.1002-137X.2019.08.025
Abstract PDF(1372KB) ( 634 )   
References | Related Articles | Metrics
In the fast fading channel,when instantaneous channel state information at transmitter (CSIT) is unavailable,the delayed channel state information can be used to improve the degree of freedom (DoF) of the system.Assuming that each node of the system has a delayed CSIT,the DoF of asymmetrical (with unequal number of users on the both sides of the relay) bidirectional relayed X-channels was investigated in this paper.The transmission procedure was divided into two phases,including multiple access channel (MAC) and broadcast channel (BC).A multi-stage transmission scheme combining interference alignment and physical layer network coding was proposed,which uses the delayed CSIT to decode the desired messages in multiple time slots.The experimental result shows that the proposed scheme can achieve a multiplexing gain of 21.8%,which is higher than the upper bound proposed by Vaze,and get an increase of 166.7% compared with the TDMA scheme.The analysis result shows that the proposed scheme can achieve some DoF gain compared with the TDMA scheme and Vaze bound
Improved LZW Prefix Coding Scheme Based on Azimuth Information
HAN Bin, ZHANG Hong-hong, JIANG Hong, DING Yi
Computer Science. 2019, 46 (8): 157-162.  doi:10.11896/j.issn.1002-137X.2019.08.026
Abstract PDF(1741KB) ( 681 )   
References | Related Articles | Metrics
LZW compression algorithm has important application value in real-time acquisition and wireless transmission.Generally,it adopts the acquisition-compression-transmission working mode,and high compression ratio in this mode can greatly reduce the pressure on wireless transmission.But in the case of fast acquisition speed,low data transmission bandwidth and limited hardware resources,it can easily lead to problems that the compression rate is not high or the speed of acquisition is mismatched when compressing the digital signal which has a sampling point of uniform probability distribution.To this end,this paper proposed an improved LZW prefix encoding scheme based on azimuth information.Firstly,the improved compression algorithm maps the sampling points based on compression ratio factor,so that it can identify the compression condition of adjacent sampling points.Secondly,through the azimuth information between the sampling points,the code length of the sampling points is shortened,so the data of the sampling points is compressed.Experiments show that,compared with the original LZW compression algorithm,the improved algorithm can increase the compression ratio by 26.25% without increasing the complexity and hardware storage space.Therefore,the effectiveness of the algorithm in the acquisition system was proved
Cloudlet Workload Balancing Algorithm in Wireless Metropolitan Area Networks
ZENG Jin-jing, ZHANG Jian-shan, LIN Bing, ZHANG Wen-de
Computer Science. 2019, 46 (8): 163-170.  doi:10.11896/j.issn.1002-137X.2019.08.027
Abstract PDF(2040KB) ( 640 )   
References | Related Articles | Metrics
With the development of wireless communication technology,more and more business,entertainments and social activities are built on portable mobile devices.The size of portable mobile devices limits their computing power,and the lack of computing power conflicts with the high computational requirement of the application.Edge computing enables computational tasks to be processed in time near the source,which is an effective way to reduce system delay.Cloudlet technology is an important application of edge computing,and deploying cloudlet is an effective way to solve the above contradiction.Multiple cloudlet are connected to form a network,and end-user can get cloudlet services via wireless metropolitan area network(WMAN).The currently major challenges are how to offload and schedule the tasksto a reasonable cloudlet to reduce system delay.This paper investigated how to balance the workload between multiple cloudlet in a network to optimize the performance of mobile applications.It first introduced a system model to get the response times of offloaded tasks,and developed an optimal solution finding the best offloading scheme of the task between cloudlet to minimize the average responses time at cloudlets.Then,it proposed a fast,scalable heuristic algorithm for this problem to reduce the user task response time.Finally,it evaluated the performance of the proposed algorithm through experimental simulation.Experimental results show that the algorithm has a positive effect on reducing task response time and improving user experience
Study on Application of Network Coding and Multipath Transmission in Internet Live Video Broadcasting
ZHANG Jin-hui, DENG Qian, LI Zhen-yu
Computer Science. 2019, 46 (8): 171-177.  doi:10.11896/j.issn.1002-137X.2019.08.028
Abstract PDF(2125KB) ( 1868 )   
References | Related Articles | Metrics
Internet live video users can upload videos in real time,and other users can watch online in real time.This mode makes it impossible to push video to CDN node in advance based on popularity,and requires that the delay from video generates to viewers be as low as possible.The performance of video uploading has the greatest impact on the viewing experience of Internet live video.The pause of the upload stream often causes no data to be sent in the download stream,accounting for 87.6% of the video freeze.In response to the above questions,the paper proposed a method of combining network coding and multi-path transmission into Internet live video uploading.Firstly,the real-time generated video data are redundantly coded through network coding to enhance anti-dropping packets.Secondly,the speed of each link of the uploading terminal to the CDN is measured,and the performance of each link is evaluated by the utility function.Finally,the encoded data are allocated to the links for transmission according to the utility values of different links.Theoretical analysis and experiments show that the transmission rate is 7.6 times that of TCP under the network condition of 2% packet loss rate and 50ms delay compared with the TCP transmission method currently widely used.The results show that the combination of network coding and multi-path transmission into Internet live video uploading can significantly improve the upload rate,quickly sense the changes of the network,and enhance the adaptability to the changing network environment
Information Security
Network Traffic Anomaly Detection Based on Wavelet Analysis
DU Zhen, MA Li-peng, SUN Guo-zi
Computer Science. 2019, 46 (8): 178-182.  doi:10.11896/j.issn.1002-137X.2019.08.029
Abstract PDF(1310KB) ( 1404 )   
References | Related Articles | Metrics
High-quality feature extraction and anomaly detection of large-scale network traffic data is an important basis for network forensics.The key research and implementation of this paper is the data processing and modeling library in network forensics.A method of network traffic anomaly detection based on wavelet analysis was studied to detect pcap files containing two different injection attacks.The study was implemented on the Windows system,and Python language was used to complete the function code.First,the required training data from a large amount of data are extracted,then the features are extracted from trainning data by using wavelet analysis.Finally,the support vector machine is used for classifier training.Thus,two types of anomaly traffic are identified from the mixed traffic containing normal traffic and abnormal traffic.Qualitative and quantitative experimental results show that the method achieves good classification results,and can provide a way for the improvement of network forensics from the two perspectives of feature extraction and classification analysis
Study on Restoration of Electronic Disguised Voice Based on DC-CNN
WANG Yong-quan, SHI Zheng-yu, ZHANG Xiao
Computer Science. 2019, 46 (8): 183-188.  doi:10.11896/j.issn.1002-137X.2019.08.030
Abstract PDF(2530KB) ( 823 )   
References | Related Articles | Metrics
Aiming at the fact that there is no breakthrough in modeling for the electronic disguised voicer estoration,this paper proposed a new model based on Dilated Casual-Convolution Neural Network (DC-CNN) for restoring electronic disguised voice.DC-CNN is used as the framework of restoring model,and convolution and nonlinear mapping are performed on the historical sampling acoustic information and restoring factors of the electronic disguised voice.Meanwhile,the model’s neural network adopts skip-connection for deep transmission and outputs the restoring voice after companding transformation.The model has obvious characteristics such as nonlinear mapping,expansibility,adaptability and conditionality,concurrency,etc.In the experiment,the original voice was processed by three basic disguised functions:pitch,tempo and rate.Then,voiceprint features comparison,LPC analysis and voice identity of human audiometry recognition were made between restoring voice and original voice.The voiceprint of the restoringvoice fits that of the original voice perfectly,and high quality formant waveform restoration is achieved.The piano music’s and English voice’sgeneral restoring fitting rates of the formant’s parameters are 79.03% and 79.06% respectively,which are much higher than the similarity of electronic disguised voice to original voice.The results turn out that this model can minify the electronic disguised characteristics effectively and it is efficient on the restoration of electronic disguised piano music and English voice
Integral Fault Analysis on LED Cryptosystem in Digital Data Forensic
WANG Yi
Computer Science. 2019, 46 (8): 189-193.  doi:10.11896/j.issn.1002-137X.2019.08.031
Abstract PDF(1566KB) ( 642 )   
References | Related Articles | Metrics
The competition between digital data forensic and anti-forensic is upgrading day by day.Data encryption is an important research field in anti-forensic technology.In order to have the lead in the competition,this paper mainly studiedLED cryptosystem widely used in IoT field.Through analyzing encryption and decryption process of LED algorithm,integral fault analysis was introduced to test security attribute of LED algorithm,and a method of breaking LED cryptosystem was proposed by integral fault analysis attacking.Integral fault analysis mainly uses difference between ciphertext outputted by normal encryption of the same plaintext and ciphertext generated after injection failures.The attackers induce random errors in some rounds of the encryption,and thus obtain faulty ciphertexts.By constructing an integral distinguisher,the attackers can recover the value of the last subkey.Then they can decrypt the right ciphertext to obtain the input of the last round,which is the output of the penultimate round.At last,they repeat the above procedure to induce more faults until the secret key is obtained by the key schedule.Then through mathematical proof and experimental proof from accuracy,reliability and time latency,this paper drew the conclusion that integral fault analysis attacking can break LED cryptosystem by constructing a three-round fault distinguisher in a half byte-oriented fault model.This attacking method can provide more reference of AES-like lightweight cryptosystems
Efficient Access Control Scheme for Internet of Things Search Technology
ZHANG Yuan-yuan, QIN Ling
Computer Science. 2019, 46 (8): 194-200.  doi:10.11896/j.issn.1002-137X.2019.08.032
Abstract PDF(1601KB) ( 616 )   
References | Related Articles | Metrics
Internet of Things search technology is widely used in daily life,however,due to the openness of the Internet of Things search engine and the incomplete credibility of the search center,information stored in the search background has serious security issues.This paper proposed a secure and efficient attribute-based access control scheme for suppor-ting ciphertext search to solve this problem.In terms of data protection,in order to ensure the security of user attribute information and data,access policy partial hiding and attribute authority decentralization are used.Besides,ciphertext fixed length is used to improve algorithm efficiency and save storage space.At the same time,this paper proposed an attribute revocation scheme that supports policy comparison,which can reduce the computational complexity in the traditional revocation scheme and improve the efficiency of re-encryption.In the ciphertext search,the super peer is introduced and the hybrid index is used to improve the retrieval efficiency.The analysis results show that the solution effectively solves the security problem in the Internet of Things search technology
Study on Selection of Privacy Parameters ε in Differential Privacy Model
LI Lan, YANG Chen, WANG An-fu
Computer Science. 2019, 46 (8): 201-205.  doi:10.11896/j.issn.1002-137X.2019.08.033
Abstract PDF(1454KB) ( 1627 )   
References | Related Articles | Metrics
Differential privacy is different from the traditional privacy protection methods.Differential privacy can quantify the privacy protection intensity.Because of this feature,differential privacy is widely studied and applied in data publishing and data mining.The privacy budget factor ε is one of the important factors affecting the privacy protection intensity.How to choose a reasonable ε value to maximize the availability of data and quantitatively analyze the privacy protection intensity is an urgent problem to be solved.Therefore,by analyzing the relationship between the probability density function and the distribution function satisfying the Laplace distributed,three kinds of noises in different range were choosen,so as to establish privacy parameter probability mathematical relational expression between epsilon and placement.And the function of image model was used to quantificationally analyze the selection formula of the parameter ε. Finally,the upper bound of privacy parameter epsilon was discussed combining with the attack probability
Formal Verification of Cloud-aided Lightweight Certificateless Authentication Protocol Based on Probabilistic Model
XIA Nu-nu, YANG Jin-ji, ZHAO Gan-sen, MO Xiao-shan
Computer Science. 2019, 46 (8): 206-211.  doi:10.11896/j.issn.1002-137X.2019.08.034
Abstract PDF(2343KB) ( 654 )   
References | Related Articles | Metrics
Anonymous wireless body area networks communication technology is one of the most powerful means to protect the privacy of Internet users and servers,but formal authentication of anonymous wireless body area networks certificateless authentication protocol is still a difficult problem to be solved.The method of probabilistic model detection is used to set up a discrete time Markov chain model based on a cloud-aided lightweight certificateless authentication protocol with anonymity for wireless body area networks.The attack rate is added to the state migration of the protocol modeling,and in particular,the attack rate was analyzed quantitatively.The protocol attributes are described with the probability calculation tree logic,the PRISM namely a probabilistic model testing tool was used for quantitative analysis and verification of the protocol,and the performance of the protocol was compared with the SIP protocol.The result shows that the attack rate between the entities of the cloud-aided lightweight certificateless authentication protocol has different influence on non-repudiation,time delay and effectiveness of the protocol under anonymous WBANs communication environment.The control of the attack rate can improve the security of the protocol.It is of great significance to the quality of medical services,the improvement of real-time monitoring efficiency and the basic needs of telemedicine
Location Privacy Preserving Nearest Neighbor Querying Based on GeoHash
ZHOU Yi-hua, LI Guang-hui, YANG Yu-guang, SHI Wei-min
Computer Science. 2019, 46 (8): 212-216.  doi:10.11896/j.issn.1002-137X.2019.08.035
Abstract PDF(1626KB) ( 831 )   
References | Related Articles | Metrics
With the continuous development of mobile applications and location technologies,Location-Based Services has become more and more widely used.LBS brings convenience to people while also posing a risk of privacy breaches.In recent years,the issue of privacy protection in location services has received continuous attention from researchers,especially the issue of location privacy protection in neighboring queries has been extensively studied.Aiming at the lack of credibility of third-party anonymous servers and the problem of being a system bottleneck,this paper proposed a GeoHash-based neighbor query location privacy protection method that does not depend on third-party anonymous servers for adaptive location privacy protection.The method uses the GeoHash algorithm to encode the exact position coordinates of the user and convert the two-dimensional latitude and longitude coordinates into a one-dimensional string.The LBS server matches the GeoHash encoded string by constructing the Trie prefix tree and returns the query result to the user.Theoretical analysis and experimental results show that the algorithm reduces the query communication overhead and can effectively protect the user’s location privacy information
Software & Database Technology
Embedded Software Reliability Model and Evaluation Method Combining AADL and Z
LI Mi, ZHUANG Yi, HU Xin-wen
Computer Science. 2019, 46 (8): 217-223.  doi:10.11896/j.issn.1002-137X.2019.08.036
Abstract PDF(1358KB) ( 813 )   
References | Related Articles | Metrics
In the early stage of embedded software development,a reliability model is established for it to discover problems in software design as early as possible,thereby saving embedded software development costs.AADL establishes software reliability model from two aspects of software structure and fault propagation.However,the semi-formal nature of AADL makes it difficult to analyze and verify the non-functional attributes such as reliability and security.The formal specification language Z language has a strong logical description ability and can accurately express various constraints in the software,which makes the reliability model based on the Z language well rigorously analyzed and verified.Therefore,considering the characteristics of AADL and Z,an embedded software reliability model combined with Z and AADL (ZARM) was proposed.The modeling methods of ZARM fault model,structure model and behavior model were given,and the data constraints related to reliability were described in the predicate.Based on the ZARM model,a probabilistic DTMC-based reliability evaluation method was proposed to quantitatively evaluate and analyze the ZARM model.Finally,the process of reliability modeling using ZARM model was described by a flight management system (FMS),and the reliability evaluation was carried out by using the proposed evaluation method.The comparison between the evaluation results and the reference [19] results shows the correctness and effectiveness of the proposed method.
Method for Identifying and Recommending Reconstructed Clones Based on Software Evolution History
SHE Rong-rong, ZHANG Li-ping
Computer Science. 2019, 46 (8): 224-232.  doi:10.11896/j.issn.1002-137X.2019.08.037
Abstract PDF(3458KB) ( 582 )   
References | Related Articles | Metrics
The research on the existing clone code reconstruction is limited to a single version of static analysis while ignoring the evolution process of the cloned code,resulting in a lack of effective methods for reconstructing the cloned code.Therefore,this paper firstly extracted the evolution history information closely related to the clone code from clone detection,clone mapping,clone family and software maintenance log management system.Secondly,the clone code that needs to be reconstructed was identified,and the traced clone code was identified at the same time.Then,static features and evolution features were extracted and reconstructed and a feature sample database was built.Finally,a variety of machine learning methods were used to compare and select the best classifier recommended reconstruction of clones.In this paper,experiments were performed on nearly 170 versions of 7 software.The results show that the readiness for reconstructing cloned code is more than 90%.It provides more accurate and reasonable code reconstruction suggestions for software development and maintenance personnel
Test Case Prioritization Method Based on AHP for Regression Testing
FENG Shen-feng, GAO Jian-hua
Computer Science. 2019, 46 (8): 233-238.  doi:10.11896/j.issn.1002-137X.2019.08.038
Abstract PDF(1595KB) ( 881 )   
References | Related Articles | Metrics
Test case prioritization methods are based on specific criteria to sort test cases to improve the test efficiency.Considering that the existing techniques are limited to single objective or a few influencing factors,which affect the comprehensive analysis and evaluation of test cases,this paper proposed a test case prioritization method based on analytic hierarchy process.This method aims at optimizing test case sequence,takes the influencing factors as the criterion,and takes the test cases as schemes.It constructs hierarchical structure model and judgment matrices.Lastly,it sorts the test cases,carries out the consistency check,and optimizes the ratio of influencing factors.The experiment uses Matlab software and the APFD as the metric to evaluate.Experimental results show that compared with other existing prioritization methods,this method achieves higher APFD value of 85% and improves the test efficiency.In addition,according to actual requirements,it increases the number of influencing factors,so that it can be flexible
Priority Ranking Method of Test Cases Based on Fault Location
CHEN Jing, SHU Qiang, XIE Hao-fei
Computer Science. 2019, 46 (8): 239-243.  doi:10.11896/j.issn.1002-137X.2019.08.039
Abstract PDF(1765KB) ( 682 )   
References | Related Articles | Metrics
Protocol conformance testing is a method to verify whether the tested implementation is consistent with the standard protocol specification,which can ensure the interconnection and interworking of the equipment or system in accordance with the protocol.In the process of debugging,upgrading and repairing the tested equipment,it is often necessary to re-execute all test cases to ensure the completeness of protocol conformance testing.In the process of protocol implementation,it is necessary to test frequently and repairs this process until the protocol implementation of the tested equipment fully conforms to the protocol standard specification.In each regression process,the unstrategic execution of all test cases in the test case set will increase the workload of the test.Only at the end of all test cases,whether the test failure has been repaired correctly,or if other new failures have been detected,can be determined.As a result,some test cases that can detect faults can not be executed as soon as possible,and the test can not focus on the error-prone parts.The cost of test execution is large,which affects the test efficiency.Therefore,in the process of protocol conformance testing,how to optimize the huge test case set and reduce the test cost.Under the premise of ensuring the test requirements,using as few test cases as possible to detect the faults in the system as soon as possible,and improving the test fault detection rate has become an urgent problem to be solved.In this paper,based on the research of the existing test case priority sorting methods,the test case priority sorting algorithm based on fault location was improved,so as to improve the efficiency of fault detection.Combined with the dependence between test requirements,the dynamic adjustment of sequence is performed,and the test cases with high error detection probability are selected dynamically.The algorithm is verified effectively on the protocol conformance test system of wireless sensor networks.Compared with the Additional and FTP algorithms,its average percentage of fault detection APFD and test cost TCFD increases by at least 9.2% and 7.6% respectively.
Artificial Intelligence
Event Temporal Relation Classification Method Based on Self-attention Mechanism
ZHANG Yi-jie, LI Pei-feng, ZHU Qiao-ming
Computer Science. 2019, 46 (8): 244-248.  doi:10.11896/j.issn.1002-137X.2019.08.040
Abstract PDF(1635KB) ( 1265 )   
References | Related Articles | Metrics
Classifying temporal relation between events is a significant subsequent study of event extraction.With the development of deep learning,neural network plays a vital role in the task of event temporal relation classification.However,it remains a major challenge for conventional RNNs or CNNs to handle structural information and capture long distance dependence relations.To address this issue,this paper proposed a neural architecture for event temporal relation classification based on self-attention mechanism,which can directly capture relationships between two arbitrary tokens.The classification performance is improved significantly through combing this mechanism with nonlinear layers.The contrast experiments on TimeBank-Dense and Richer Event Description datasets prove that the proposed method outperforms most of the existing neural methods.
Selection of Cutset Threshold for Cutset-type Possibilistic C-means Clustering Based on Shadowed Set
LUO Xi, FAN Jiu-lun, YU Hai-yan, LIANG Dan
Computer Science. 2019, 46 (8): 249-254.  doi:10.11896/j.issn.1002-137X.2019.08.041
Abstract PDF(2522KB) ( 758 )   
References | Related Articles | Metrics
By introducing the cutset threshold and modifying the typicality,the cutset-type possibilistic C-means clustering algorithm overcomes the most critical problem (consistent clustering)of the possibilistic C-means clustering algorithm.Aiming at the parameter selection problem in the algorithm,this paper proposed a new method based on the shadowed set.This algorithm uses the optimization method to determine the threshold of the shadowed set for each cluster and takes this threshold as the cutset threshold.The modification method of the typicality is improved by analyzing the influence of the selection method on the typicality and the center deviation.Finally,the influence of the new parameter selection method on the performance of the clustering algorithm is analyzed by artificial dataset.The number of iterations and the clustering accuracy of the algorithm are analyzed through the UCI dataset.Experimental results show that the proposed method can effectively reduce the number of iterations and improve the accuracy of clustering
Unit Clauses and Their Complementary Literals and Redundant Clauses in Propositional Logic
LIU Ting, XU Yang, CHEN Xiu-lan
Computer Science. 2019, 46 (8): 255-259.  doi:10.11896/j.issn.1002-137X.2019.08.042
Abstract PDF(1238KB) ( 665 )   
References | Related Articles | Metrics
In the logical formula of propositional logic,some equivalence conditions for the set of clauses containing an unit clause was given by studying the unit clause and its complementary literal,and the redundancy of literals and clauses in the set of clauses were described.The methods of judging redundant literals and redundant clauses were obtained,and the equivalence conditions of the satisfiability of clause sets were also proposed.These methods can simplify the logic formula and provide some theoretical support for simplifying the logic formula in propositional logic.
LDA Algorithm Based on Dynamic Weight
JU Ya-ya, YANG Lu, YAN Jian-feng
Computer Science. 2019, 46 (8): 260-265.  doi:10.11896/j.issn.1002-137X.2019.08.043
Abstract PDF(2333KB) ( 1130 )   
References | Related Articles | Metrics
The latent Dirichlet allocation (LDA)is a popular three-layer probability topic model,which implements the clustering of words in document and document at the topic level.This model is based on the Bag of Words(BOW) mo-del,and each word has the same importance.It simplifies the complexity of modeling,but makes the topic distributions tend to high-frequency words,which affects the semantic coherence of the topic model.To achieve this goal,an LDA algorithm based on dynamic weight was proposed.The fundamental idea of the algorithm is that each word has different importance.In the iterative process of modeling,word weights are generated dynamically according to the topic distribution of words and feedback to topic modeling,reducing the influence of high frequency words and improving the role of keywords.Experiments on four public datasets show that the LDA algorithm based on dynamic weight can be superior to the current popular LDA inference algorithms in terms of topic semantic coherence,text classification accuracy,gene-ralization performance and precision
Scale Change Based on MQHOA Optimization Algorithm
ZHOU Yan, WANG Peng, XIN Gang, LI Bo
Computer Science. 2019, 46 (8): 266-271.  doi:10.11896/j.issn.1002-137X.2019.08.044
Abstract PDF(2576KB) ( 628 )   
References | Related Articles | Metrics
Scale convergence is an important part of the computational process of intelligent optimization algorithm.The uncertainty principle and quantum tunneling effect prove this importance.In the optimization iterative process of the multi-scale quantum harmonic oscillator algorithm (MQHOA),by adjusting the scale convergence range,the algorithm’ssolution effect and computational performance can be affected.The scale variation was studied,and the optimal scale convergence parameter corresponding to the function in the 2-dimensional state was defined as the scale factor of the function.The scale factor can be used as a qualitative criterion for measuring the complexity of the function scale structure.The scale factor can help the algorithm to find the optimal solution by using the most suitable convergence scale for different functions
Natural Language Querying with External Semantic Enrichment
FENG Xue
Computer Science. 2019, 46 (8): 272-276.  doi:10.11896/j.issn.1002-137X.2019.08.045
Abstract PDF(1577KB) ( 712 )   
References | Related Articles | Metrics
Semantic Web is one kind of extremely important resources based on Internet technique.Querying on a semantic Web only supports formal languages,which need manipulator to strictly observe certain syntax constraints,and thus only experts that are familiar with semantic Web system and formal language are capable of querying.To overcome this problem,this paper presented an unsupervised natural language querying system,which can convert natural languages into formal languages automatically,thus making common users query on a semantic web using natural languages conveniently.The system first extracts all entities and attributes in a sentence based on a specific semantic Web,then connects them to form a semantic relationship graph,and finally exploits a heuristic strategy to search for an optimum path which is used to produce the output SPARQL expression.The key of the system is the coverage of the entities and attributes from the semantic Web,which directly decides the quality of the inter-mediate semantic relationship graph,and influences the final performance of system.In order to achieve a practical system,this paper enriched a human-annotated semantic Web for a specific domain through using external semantic knowledge,so that the natural language formed languages can contain more information.By this method,better semantic relationship graphs can be obtained and more accurate SPARQL expressions for sentences are achieved.Finally,this paper used the dataset based on American geography for experimental evaluation to verify this system.The dataset is widely acceptable for related research work of natural language querying,which includes manually-annotated SPARQL expressions with 880 questions.The experimental results show that this system can correctly answer 77.6% of the natural queries,outperforming the best unsupervised system in the literature significantly.After knowledge enriching by the external semantic Web,the system reaches 78.5% in term of the correctly-answering accuracy
Employing Multi-attention Mechanism to Resolve Event Coreference
FANG Jie, LI Pei-feng, ZHU Qiao-ming
Computer Science. 2019, 46 (8): 277-281.  doi:10.11896/j.issn.1002-137X.2019.08.046
Abstract PDF(1489KB) ( 796 )   
References | Related Articles | Metrics
Event coreference resolution is an asignificant subtask of information extraction and plays an import role in information fusion,QA system and reading comprehension.This paper introduced a multi-attention-based CNN neural network,called CorefNet,to resolve document-level event coreference.CorefNet uses a deep CNN to extract event features and a multi-attention mechanism to capture important features.Compared with most previous studies with probability-based or graph-based models,the proposed model only uses a few features.Compared with the current main stream nueral network model,this menthod can extract deep event features,and significantly improve the performance of event coreference resolution.The experimental results on the ACE2005 corpus show that this model achieves the state-of-the-art results
Dynamic Trajectory Based Implicit Calibration Method for Eye Tracking
CHENG Shi-wei, QI Wen-jie
Computer Science. 2019, 46 (8): 282-291.  doi:10.11896/j.issn.1002-137X.2019.08.047
Abstract PDF(4040KB) ( 1540 )   
References | Related Articles | Metrics
Aiming at the limitations of the existing multi-point calibration schemes,such as time-consuming and poor gaze accuracy of simplified calibration schemes,this paper proposed an implicit calibration method for eye tracking,which makes the eye tracking system only need a few samples to establish an accurate mapping relationship.The me-thod has three steps.Firstly,it collects calibration data.With user’s gaze following the dynamictrajectory,it records the mapping points between the image of user’s eyes and the calibration points in this process.Then,a rationalized outlier removal method is proposed to automatically eliminate the sample noise and select the best point pair to establish a mapping model.The acquisition of eye movement data is delayed,which can reduce the error caused by the dynamic traje-ctory.Furthermore,when the noise data of the sample are removed,a method for eliminating the pupil error data is proposed,and the sample data are further filtered by Random Sample Consensus (RANSAC) algorithm.Finally,the two methods of calibration-free and single-point calibration are combined to simplify the subsequence implicit calibration process.Experiment results show that the average calibration time is 8 s,and the average accuracy is 2.0° of visual angle when visual distance is 60 cm.In the simplified implicit calibration prototype system,for the user who is calibrated,the coordinates of the fixation are obtained by the calibration-free method.The average calibration time is 2 s,and the ave-rage calibration accuracy is 2.47° of visual angle.For the new user who performs eye tracking,the individual difference compensation model is calculated by the single point calibration method to obtain the coordinates of the fixation.The ave-rage calibration time is 3 s,and the average calibration accuracy is 2.49° of visual angle,which further improves the practicality of the implicit calibration method
Graphics ,Image & Pattern Recognition
Track Defect Image Classification Based on Improved Ant Colony Algorithm
CAO Yi-qin, WU Dan, HUANG Xiao-sheng
Computer Science. 2019, 46 (8): 292-297.  doi:10.11896/j.issn.1002-137X.2019.08.048
Abstract PDF(2081KB) ( 810 )   
References | Related Articles | Metrics
In view of the disadvantages of the traditional methods,such as low accuracy,slow classification speed,and a great difference in the recognition accuracy of different types of track defects,a new method of track defect image classification based on improved ant colony algorithm was proposed.The track defect image is preprocessed,the vertical projection method is used to extract the track surface area,the fuzzy theory and the hyper entropy theory are combined to obtain the best segmentation threshold,and the image segmentation is completed.Combined with adaptive threshold Canny edge detection operator and Hough transformation method,the rail defect part is determined.The edge details of defects are improved to make the contour of track defects more obvious.On the basis of this,the basic ant colony algorithm is analyzed,the characteristic similarity is used as a discriminant function,and the improved ant colony algorithm is used to classify the track defect image.Experimental results show that the classification accuracy and classification speed of the proposed method are high.
Face Hallucination Reconstruction Algorithm Based on Hierarchical Clustering Regression Model
WANG Shu-yun, GAN Zong-liang, LIU Feng
Computer Science. 2019, 46 (8): 298-302.  doi:10.11896/j.issn.1002-137X.2019.08.049
Abstract PDF(6466KB) ( 737 )   
References | Related Articles | Metrics
Face hallucination reconstruction refers to the process of reconstructing high-resolution enhanced face from a low-resolution image.Most of the traditional methods assume that the input image is aligned and noise-free.However,the super resolution performance will decrease when the input facial image is unaligned and affectedby noise.This paper proposed an effective single image super resolution method for unaligned face images,in which the learning-based hierarchical clustering regression approach is used to get better reconstruction model.The proposed face hallucination methodcan be divided into clustering and regression.In the clustering part,a dictionary is trained on the whole face image with tiny size,and the training images are clustered based on the Euclidean distance.Thus,the facial structural prior is fully utilized and the accurate clustering result can be obtained.In the regression part,to reduce the time complexity effectively,only one global dictionary needs to be trained during the entire training phase whose atoms are taken as the anchors.In particular,the learned anchors are shared with all the clusters.For each cluster,the Euclidean distance is used to search the nearest neighbors for each anchor to form the subspace.Moreover,in every subspace,a regression model is learned to map the relationship between low-resolution features and high-resolution samples.The core idea of this method is to utilize the same anchors but different samples for clusters to learn the local mapping more accurately,which can reduce training time and improve reconstruction quality.The results of comparative experiments with other algorithms show that the PSNR can be increased by at least 0.39 dB and the SSIM can be increased by 0.01 to 0.18
Consistent Correspondence of 3D Dynamic Surface Based on Space-Time Constraints
CHENG Zhi-hao, PAN Xiang, ZHENG He-rong
Computer Science. 2019, 46 (8): 303-309.  doi:10.11896/j.issn.1002-137X.2019.08.050
Abstract PDF(5063KB) ( 887 )   
References | Related Articles | Metrics
Existing corresponding algorithms will cause error mappings since geometric signatures can’t remain stable and highly similar under different poses.This paper focused on corresponding 3D dynamic surface based on space-time constraints.Firstly,this algorithm constructs the energy optimization function according to the non-rigid deformation model.Secondly,sparse correspondence is computed by optimizing the energy function.Finally,this algorithm of surface sampling and isometric mapping is used to solve the dense matching problem.In experimental part,the analysis and quantification of different 3D motions are carried out,and it turns out that this algorithm can improve the correspondence accuracy.
Image Compression Encoding Based on Wavelet Transform and Fractal
ZHANG Jing-jing, ZHANG Ai-hua, JI Hai-feng
Computer Science. 2019, 46 (8): 310-314.  doi:10.11896/j.issn.1002-137X.2019.08.051
Abstract PDF(2730KB) ( 674 )   
References | Related Articles | Metrics
Fractal image encoding with the high compression ratio can maintain a good quality of reconstructed image.However,there are some disadvantages such as high computational complexity and long encoding time.Therefore,based on the definition of a new sub-block feature called sum of frame and point,combined with the smoothing characteristics of continuous wavelet transform,an image compression encoding on the basis of wavelet transform and fractal was proposed.This algorithm makes full use of the correlation of sub-bands,so as to improve the quality of reconstructed ima-ge.And it converts the global search into the nearest neighbor search to shorten search range and reduce encoding and decoding time.The simulation results show that compared with the basic fractal algorithm and other algorithms,the new algorithm has better performance.In addition,it not only shortens the encoding and decoding time,but also improves the reconstructed image quality
Adaptive Multi-level Threshold Binaryzation Method for Optical Character Recognition in Mobile Environment
ZHU De-li, YANG De-gang, HU Rong, WAN Hui
Computer Science. 2019, 46 (8): 315-320.  doi:10.11896/j.issn.1002-137X.2019.08.052
Abstract PDF(2338KB) ( 647 )   
References | Related Articles | Metrics
In order to solve the problem of poor binaryzation quality caused by uneven illumination and uncontrollable environment in OCR applications of mobile terminals,this paper proposed an adaptive multi-level threshold binaryzation method based on integral graph.First,a specific sliding window is set by focusing on the points to be calculated.The normal threshold is the mean value of the sliding window where the current point is located.The two front sliding windows are weighted according to the Gauss function,and then the relaxation factor is obtained according to the weights.The relaxation threshold of pixels are obtained based on the evaluation of the relaxation factor and illumination condition.Experiments were carried out in typical mobile environments such as irregular shadows,multi-level illumination and linear light changes.Lenovo ZUK Z2 Pro is used as the test equipment.The average recall of the algorithm is 95.5% and the average accuracy is 91%.The recognition accuracy of this algorithm is 96.8%,98.2% and 93.2% respectively in the environment of irregular shadow,multilevel illumination and linear light change.The result shows that the proposed algorithm has strong robustness and adaptability,and can meet the requirement of image preprocessing in the OCR application of mobile terminal
Automatic Quantitative Evaluation Approach for Medical Renal Dynamic Imaging
CHAI Rui, XUE Fan, ZENG Jian-chao, QIN Pin-le
Computer Science. 2019, 46 (8): 321-326.  doi:10.11896/j.issn.1002-137X.2019.08.053
Abstract PDF(2555KB) ( 983 )   
References | Related Articles | Metrics
The evaluation method of renal function in clinical renal dynamic imaging depends too much on manual acquisition of ROI (Region of Interest)and has low time efficiency.In order to solve this problem,this paper proposed anautomatic quantitative assessment method for medical renal dynamic imaging.Firstly,the images of renal dynamic imaging at different stages are pretreated.Secondly,an improved level set model is utilized to obtain the ROI of the renal function imaging.The ROI is obtained by morphological methods,then the ROI of the aorta in the renal perfusion imaging is located and obtained.Finally,GFR(Glomerular Filtration Rate) is calculated according to the Gates method,and the time-radioactivity curve is plotted based on the radioactivity counts in ROI,so as to achieve integrated and automated assessment for renal function.The results of clinical trials show that the proposed automatic assessment method can improve the automation level in a short period of time and raise the assessment accuracy,which provide effective help for clinical diagnosis and adjuvant treatment
Low Light Images Enhancement Based on Retinex Adaptive Reflectance Estimation and LIPS Post-processing
PAN Wei-qiong, TU Juan-juan, GAN Zong-liang, LIU Feng
Computer Science. 2019, 46 (8): 327-331.  doi:10.11896/j.issn.1002-137X.2019.08.054
Abstract PDF(3091KB) ( 852 )   
References | Related Articles | Metrics
Due to the influence of strong light,the images acquired at night have high contrast,the same situation also appears in backlit images collected in the daytime.Contrast enhancement method is usually applied to the images for obtaining images with favorable contrast.Whereas,over-enhancement commonly occurs in bright regions.Accordingly,in order to solve the problem of over-enhancement for high contrast images,a Retinex based low light image enhancement algorithm through adaptive reflection component estimation and logarithmic image processing subtraction post-proces-sing was proposed.The algorithm mainly includes into two parts:reflection component estimation and logarithmic image processing subtraction (LIPS) enhancement.First,adaptive parameter bilateral filters are used to get more accu-rate illumination layer data,instead of Gaussian filter.Moreover,the weighting estimation method is used to calculate the adaptive parameter to adjust the removal of the illumination and obtain the reflectance by just-noticeable-distortion (JND)factor.In this way,it can effectively prevent the over-enhancement in high-brightness regions.Then,the LIPS method based on maximum standard deviation of the histogram is applied to enhance reflectance component part,where the interval of the parameter is according to the cumulative distribution function (CDF).Experimental results demonstrate that the proposed method outperforms other competitive methods in terms of subjective and objective assessment
Ship Target Detection Based on Improved YOLO v2
YU Yang, LI Shi-jie, CHEN Liang, LIU Yun-ting
Computer Science. 2019, 46 (8): 332-336.  doi:10.11896/j.issn.1002-137X.2019.08.055
Abstract PDF(1909KB) ( 1124 )   
References | Related Articles | Metrics
Aiming at the problem of low target detection accuracy and poor system robustness in ship image target detection,an improved YOLO v2 algorithm was proposed to detect ship image targets.The traditional YOLO v2 algorithm is improved by clustering the target frame dimension,optimizing the network structure,multi-scale transformation of input image,so as to better adapt to the ship target detection task.The test results show that the mean Average Precision (mAP)of the algorithm is 79.1% when the input image size is 416×416,and the detection speed is 64 frames per se-cond (FPS),which can satisfy the real-time detection and exhibit high precision and strong robustness for small target detection
Fault Detection Method Based on Immune Homeostasis Mechanism
XIAO Zhen-hua, LIANG Yi-wen, TAN Cheng-yu, ZHOU Wen
Computer Science. 2019, 46 (8): 337-341.  doi:10.11896/j.issn.1002-137X.2019.08.056
Abstract PDF(1408KB) ( 581 )   
References | Related Articles | Metrics
In view that the existing DCA (dendritic cell algorithm) relies heavily on domain knowledge and artificial experience defining antigen signals in fault detection application,and a single antigen anomaly evaluation method can’t reflect the overall health condition of system,this paper proposed a fault detection method based on immune homeostasis mechanism-IHDC-FD.First of all,in order to solve problem that the danger signal definition is not explicit in actual application,by introducing body’s immune homeostasis mechanism,the change that breaks the homeostasis is consi-dered to be the danger source of system.Therefore,the method of antigen signal of DC adaptive extraction from the change of system state by numerical differential method is proposed.Secondly,the concentration of specific cells within the tissue is the critical factor that can reflect the health of body,and in order to keep healthy,the body’s immune homeostasis has to be maintained.So,by reference to the activation and suppression mechanism of body’s immune homeostasis,the Th and Ts cell concentration which maintain the immune homeostasis is regarded as the evaluation indicators of system imbalance,and once the system lose balance,a fault occurs.Finally,the performance of our method is tested by using step,random and slow drift faults on TE benchmark.Compared with the original DCA,the results show that IHDC-FD not only improves the adaptability of DCA,but also increases the average of fault detection rate by 9.93%,decreases false alarm rate by 230.4% and decreases delay time by 101.2% on the three types of faults testing.Therefore,the IHDC-FD method based on immune homeostasis mechanism has a large improvement than the original DCA on detection performance and adaptability,and it is effective and generality