Current Issue

• 2014, No. 10　Published:25 October 2014 Last issue    Next issue
  Columns in this issue: 论文

• 论文

  A new RNS approach for fast
  Fp elliptic curve point multiplication          

  WU Tao1,LI Shuguo2,LIU Litian2

  2014, 36(10): 1839-1845. doi:

  Abstract ( 161 )   PDF (519KB) ( 228 )   　　

  The basic computation in Elliptic Curve Cryptography (ECC) is Elliptic Curve Point Multiplication (ECPM), which consists of a series of modular multiplications.Through Montgomery modular multiplications in Residue Number System (RNS),the modular multiplications inFpcan be transformed into modular arithmetic over RNS moduli.A new RNS approach is proposed to accelerate ECPM.Firstly,instead of almost two symmetric RNSs,two asymmetric RNSs are chosen,with 2 moduli  {2L, 2 L-1} for RNS Γ and 8 moduli with the form of　2L－2Ki+1 for RNS Ω,which makes the modular reductions quite easy.Secondly,in the asymmetric RNSs,most modular multiplications can be performed by direct multiplications in RNS rather than modular multiplications in Fp.Especially,Montgomery ladder with only x coordinates is used for ECPM. At the end of every parallel point doubling and point addition,4 RNS Montgomery modular multiplications are performed to narrow the output range.As a result, the total time for an Nbit Fp ECPM is around 55.5N·I,with I being the time delay of a (L/2)bit multiplication,a carry save addition,and a (L/2)bit full addition.

  Dynamic data distribution for stream processing system       

  WANG Chengzhang1,LIN Xuelian1,TAN Jingfang2

  2014, 36(10): 1846-1853. doi:

  Abstract ( 105 )   PDF (674KB) ( 192 )   　　

  In stream processing systems,data skew often leads to load imbalance among computing nodes,thereby increases the response time of data process.Traditional load balancing methods such as operator distribution,operator migration and load shedding have never been widely applied in stream processing systems because of a relatively high performance penalty.Considering the characteristics of stream processing systems, a new load balancing mechanism is proposed. In this mechanism, the data on computing units are split into some sections,and each section can be allocated and migrated dynamically among computing units.Then,for the purpose of load balancing, the input streams and utilizations are balanced among computing units by adjusting sections with few disturbances on steam processing systems. Based on this,we design and implement a load balancing algorithm as well as an online data migration method.The experimental results show that our mechanism can reduce the average latency of data processing and improve the system throughput significantly.

  A software debugger for general many-core processors         

  WANG Jingyu，FAN Hao

  2014, 36(10): 1854-1859. doi:

  Abstract ( 116 )   PDF (752KB) ( 210 )   　　

  Recently, the many-core processor technology has been rapidly developed, but the software debugging for such architecture is underdeveloped. According to the characteristics of software debugging for many-core processors, the debugging model of onetomany mapping is proposed. Using this model, we configure the open source debugger gdb and design a breakpoint algorithm based on displaced instruction. The design overcomes the limitations on hardware breakpoint number, improves the accuracy of abnormal localization and makes the improved gdb more efficiently and effectively on many-core processors. Finally, experiments are carried out by a debugging example, and results show that the debugging model and algorithm are helpful to solve the problem of debugging many-core programs and improve the execution efficiency of software debugger.

  Optimizing load balancing of joins in MapReduce      

  ZHAI Hongmin, LIU Guohua, ZHAO Wei, LIU Yuanyuan, ZHAI Hongkun

  2014, 36(10): 1860-1865. doi:

  Abstract ( 100 )   PDF (551KB) ( 187 )   　　

  Data analysis and processing is one of the most important tasks in largescale distributed data processing applications.Due to its simplicity and scalability,MapReduce programming model has gradually become the crucial model for largescale distributed data processing systems (eg.Hadoop).Since the data may be uniformly distributed,data skew occurs when MapReduce programming model joins data,thus degrading the join performance severely.To solve data skew,its reason is analyzed,the load balancing cost model is established,and the rangepartitioner algorithm is proposed to control data skew so as to realize load balancing.Experimental results demonstrate that our method can obviously improve the efficiency of joins.

  论文

  Research of tasks scheduling in heterogeneous multi-core
  system based on artificial fish-swarm and genetic algorithm         

  YAO Lisha1，WANG Zhanfeng2，CHENG Jiaxing1

  2014, 36(10): 1866-1871. doi:

  Abstract ( 154 )   PDF (785KB) ( 202 )   　　

  Tasks scheduling for heterogeneous-multi-core processor system have been proved to be a NP complete problem. Artificial fish-swarm algorithm begins to converge quickly, then has slow convergence. It is robust for genetic algorithm to initialize population; the initialization of the first population affects the performance of genetic algorithm. Based on artificial fish-swarm and genetic algorithm, a task scheduling algorithm is proposed. Firstly, the tasks scheduling of heterogeneous multi-core system is analyzed. Secondly, the improved artificial fish-swarm Algorithm is used to construct the initial population of genetic algorithm. Finally, the improved genetic algorithm is applied to perform iterative optimization and it improves the convergence of algorithm.

  Study on asynchronous rendezvous algorithms based on
  channel hopping sequence in cognitive radio networks               

  KONG Dekai,WU Keyu,HAN Fangjing,HAN Fangjian

  2014, 36(10): 1872-1879. doi:

  Abstract ( 128 )   PDF (774KB) ( 169 )   　　

  Cognitive radios have been envisioned as a chief technique for alleviating the severe shortage of available spectrum as well as improving the efficiency in using licensed spectrum in next generation communicating networks.Cognitive Radio Users (CRUs) coexist with Licensed Users through dynamically accessing licensed spectrum when it is idle.Before communication,it is vital for CRUs in asynchronous Cognitive Radio Networks (CRNs) to accomplish rendezvous and channel negotiation.We review recent studies on rendezvous schemes based on channel hopping sequences, analyze three classes of these schemes and conduct Matlab simulations to evaluate the performance of eight specific algorithms in terms of ETTR,MTTR and Fairness,concluding their respective merits and demerits.

  A relay path selection scheme based on
  application layer traffic optimization             

  ZHANG Wei，LEI Weimin，LI Guangye，GUAN Yunchong

  2014, 36(10): 1880-1887. doi:

  Abstract ( 181 )   PDF (919KB) ( 145 )   　　

  The single default IP path determined by the network layer routing protocols can hardly meet the transmission requirements of growing QoSsensitive applications.Multipath transport has been proven to be an effective way to improve the efficiency of data delivery.On the base of the general multipath transport system based on application-level relay (MPTS-AR) proposed in our earlier work,a relay path selection scheme based on application layer traffic optimization (ALTO) is presented.This scheme is facilitated by means of ALTO that is under the standardization within the IETF.Rules to be obeyed during path selection procedure are proposed. An optimal relay path selection algorithm based on provider-defined domains is proposed.The goal of the path selection algorithm is to find the superior relay paths,while trying to balance the overlay traffic among the provider-defined domains and relays.Simulation results demonstrate that the proposed scheme performs well in selecting superior paths and meanwhile provides the flexibility to balance the overlay load among the provider-defined domains.

  Person entity global schema constructed dynamically with SVM      

  CAO Luhui

  2014, 36(10): 1887-1893. doi:

  Abstract ( 108 )   PDF (475KB) ( 166 )   　　

  To constructed  person entity global schema in structured web pages,a method of dynamic construction with SVM is proposed, it has two stages.The first stage is to transform person entity instances from the same data source to person entity local schema.The second stage is to map person entity local schema to person entity global schema with the SVM classifier.Our method can adapt to the change of data sources and ensure the completeness of the global model.Through experiments,the effectiveness and feasibility of the construction algorithm are verified and the stability of the global schema with increasing of structured web pages is studied.

  A joint compression and encryption scheme
  for JPEG image adapt to smart Phones       

  WANG Wei,JIN Cong

  2014, 36(10): 1894-1898. doi:

  Abstract ( 91 )   PDF (707KB) ( 214 )   　　

  Smart phone is becoming closer to people's life, bringing great convenience. However, developers’concept of“focus on experience but ignore security”makes the security issue caused by smart phone more prominent. The program of image encryption is studied and an image encryption algorithm in combination with JPEG compression is designed in order to solve the image security  problem in smart phone platforms. This algorithm can realize the image encryption while keeping image compression efficient. Experimental analysis shows that, after the JPEG compression is added to the program of image encryption, the loss of compression ratio and the increase of the time are controlled within 20%.Thus, the proposed scheme is suitable for transplantation into smart phone platforms.

  UDP/NLT：A novel UDP based on
  LT code in wireless networks      

  GE Weimin,LIU Yukai,TIAN Ye

  2014, 36(10): 1899-1905. doi:

  Abstract ( 123 )   PDF (662KB) ( 163 )   　　

  With a rapid growth of UDPbased applications in wireless networks,how to improve the performance of UDP in wireless networks is becoming an important research topic.A novel protocol,named UDP/NLT,is proposed.This protocol uses LT code and network coding technique to encode and decode the packets in order to decrease the negative influence due to the frequent network packet loss, thus increasing the throughput.UDP/NLT does not change the existing protocol stack structure and semantics of UDP and hence come true easily.Analysis and simulations in NS2 show that the UDP/NLT has better throughput performance than traditional UDP,almost without increasing the network latency in wireless networks.

  A data-based rapid checking method of
  GSM system antenna feeder interference        

  WANG Xiaojing

  2014, 36(10): 1906-1910. doi:

  Abstract ( 107 )   PDF (913KB) ( 165 )   　　

  The passive intermodulation interference has unique characteristics.Traditional test methods to this interference are in short of efficiency and accuracy.A new test method of intermodulation interference is proposed.By utilizing interference spectrum numerical comparison, the method isolates the intermodulation interference caused by antenna feeder from the composite interference. Therefore,the proposal improves the efficiency and accuracy of interference checking.

  A resource matching method
  based on capabilities model with QoS            

  XIONG Fang1,3,HUANG Hongbin2,HUANG Yucheng1,3,HU Jianzhong3

  2014, 36(10): 1911-1918. doi:

  Abstract ( 115 )   PDF (1345KB) ( 203 )   　　

  The description of resources needs to consider the integration of three aspects,viz.property,capability and status, especially in the environment of InternetofThings where the users concern about capabilities of resources and description of status much more.So far as we know,most researchers have laid emphasis on the descriptions of information resources mostly based on property description rather than capabilities,status and QoS of resources. In order to overcome the weakness of current methods,we introduce QoS parameters of resource to build a resource capacility mode  based on the descriptions of actions.The paper proposes a resource matching method BQRM with QoS assessment,and constructs a four step matching mechanism with QoS assessment.At last,the experimental analysis validates the advantages of the capabilities of entity resources modeling and resource matching method with QoS.

  Agent based D-S data fusion in wireless sensor networks           

  SUN Ziwen1,LIU Jiajie2,JI Zhicheng1

  2014, 36(10): 1919-1924. doi:

  Abstract ( 106 )   PDF (478KB) ( 212 )   　　

  An agent-based D-S data fusion algorithm with evidence weights in wireless sensor networks is proposed.Evidence weights are adopted to modify the evidences before fusion in order to reduce the impact of data conflicts on fusion result.Three-level D-S combination rules are used to make fusion decision, the fusion detection probabilities of single node in time domain are calculated in the node-level fusion,and the detection probabilities of intra-cluster nodes in space domain are calculated to obtain the local decision in the intra-cluster level fusion.The fusion detection probabilities among clusters are calculated to obtain the final global decision in the inter-cluster level fusion.The stimulation results show that the proposed algorithm can obtain an accurate fusion result with lower energy consumption.

  Personalized WeChat recommendation system
  based on indoor WLAN localization           

  FENG Jinhai1,YANG Lianhe1,LIU Junfa2,HU Lisha2

  2014, 36(10): 1925-1931. doi:

  Abstract ( 113 )   PDF (783KB) ( 258 )   　　

  With the popularity of WLAN(Wireless Local Area Networks) indoors, mobile devices can easily get real-time access to it,  which provides us an unprecedented opportunity to understand individual behavior in everyday life. Recently, mining persons’ point of interest and behaviors attracts more attentions. A WeChat recommendation system based on indoor WLAN localization is proposed, which uses users’ historical information to obtain users’ interest from the overload information. Existing location services usually aim for users’ outdoor location data, lack analyzing indoor data through mining, and ignore an amount of semantic information in users’ location data. The users’ activities are traced by the indoor positioning technology. According to the shops which  users visited and the products users saw, users’ interest is estimated so as to recommend users for personalized products that may interest them. Based on the above work, we design a personalized product recommendation system based on indoor WLAN localization and the WeChat platform.

  Research of the EDCA selfadaptive backoff
  algorithm for IEEE 802.11p VANET protocol          

  ZHANG Junjian,WU Yue

  2014, 36(10): 1932-1936. doi:

  Abstract ( 137 )   PDF (537KB) ( 183 )   　　

  802.11p is the standard for PHY and MAC promulgated by the IEEE for VANET. Density of vehicles is dynamic in the networks, but IEEE 802.11p protocol does not optimize network performance by adjusting the EDCA parameters dynamically according to network status. In order to solve the problem of low throughput and high collision rate caused by the change of network density, an algorithm is proposed, which dynamically adjust EDCA parameters to improve data throughput. The simulation results indicate that the proposed method can achieve better performance than EDCA.

  Adaptive scheduling optimization
  mechanism for virtual NIC interrupt on Xen     

  LI Guoqing

  2014, 36(10): 1937-1942. doi:

  Abstract ( 110 )   PDF (532KB) ( 161 )   　　

  For the Xen network model, high load under the environment of network causes bottleneck of the system where most CPU resources are occupied by frequent interrupt from the NIC. To alleviate this problem, an adaptive interrupt latency scheduling mechanism based on Xen is proposed, which uses the polling or interrupt method in accordance with the queue length of virtual buffer without supplementing any additional processing units. And the mechanism can guarantee different qualities of service to some extent through the definition of the two types of priority virtual buffers. Experimental results show that, when frequent interrupt from the NIC occurs, CPU will not be interrupted frequently so that the CPU utilization is improved.

  Modeling and development of multi-application
  smart cards based on Event-B 

  ZHANG Yue1,2，GUO Jian1,2，ZHU Xiaoran1，WANG Wenjun1，ZHU Jingyang1，TANG Jiahua

  2014, 36(10): 1943-1951. doi:

  Abstract ( 100 )   PDF (768KB) ( 167 )   　　

  Event-B is a formal modeling language based on set theory and predicate logic, within which hierarchical models can be established by refinement strategy. A method for applying Event-B to practical industry is proposed, which consists of rewriting requirement, establishing abstract model, and step-by-step refining. Firstly, requirements are rewritten from three different views: environmental view, functional view, and property view. During this phase, refinement strategy reflecting model hierarchy is identified. Secondly, formal methods are adopted to establish abstract model and validate the established model. Using well-proved abstract model, requirement appending, model refining and model validating are carried out at the following levels of the model hierarchy according to the refinement strategy. Finally, based on the whole established models corresponding to requirements, implementation codes can be automatically generated by the related tools. With refinement theory adopted in this method, requirements and properties of system under development can be identified in a refinement way and incrementally. Modeling and verification using formal methods guarantees the correctness of models. To illustrate the feasibility of the method, the development of multi-application smart cards is shown as a case study. Application example of the proposed method in practical modeling and validation is given based on Event-B and Rodin platform.

  A fault localization approach using
  multivariate Logistic regression model   

  JU Xiaolin1, 2,JIANG Shujuan1,CHEN Xiang2,CAO Heling1,WANG Xingya1

  2014, 36(10): 1952-1960. doi:

  Abstract ( 86 )   PDF (701KB) ( 179 )   　　

  Fault localization plays an important role in software development. Combining both construction features and behavior characteristics of program can benefit fault locating. A framework based on multivariate logistic regress model for locating fault in evolving software is proposed. Firstly, the feature data set is constructed by statically analyzing and tracing the program that runs with a set of designed metrics of program construction features and behavior characteristics. Meanwhile, the fault information of old version is obtained from the bug tracking system. Secondly, a univariate analysis is performed to select the metrics that are significantly related to fault, and then we train the multivariate Logistic model on the selected metrics with the constructed feature data set and the tracked fault information. Finally, based on the trained Logistic model, we conduct the multivariate logistic analysis on the feature data set of a new version of evolved software, and predict the faulty class methods. We also conduct an empirical study on a set of benchmarks. The results indicate that the multivariate Logistic model can improve the effectiveness of fault localization.

  Research on the rolling batch planning
  based on particle swarm optimization

  PENG Pin

  2014, 36(10): 1961-1965. doi:

  Abstract ( 85 )   PDF (390KB) ( 188 )   　　

  The rolling batch planning is regarded as a vehicle routing problem. Particle swarm optimization algorithm is used to solve the model of the problem. The particle representation of the rolling batch planning is proposed. The detailed realization of the algorithm is illustrated. The simulation results based on the actual production data show the effectiveness of particle swarm optimization algorithm for the rolling batch planning.

  Gene expression programming combining
  depth-first and breadth-first decoding principles       

  ZHANG Jianming,TANG Yong,ZHOU Shuren,WU Honglin

  2014, 36(10): 1966-1971. doi:

  Abstract ( 102 )   PDF (874KB) ( 191 )   　　

  Gene Expression Programming (GEP) is an automatic programming approach widely used in many areas,such as time series analysis,classification,multiobjective optimization and massive data analysis.A new GEP algorithm is proposed by combining the advantages of the depthfirst and breadth-first technologies in the GEP decoding process.The new algorithm can increase the diversity of individuals and properly preserve better sub_ETs.The experimental results show that,compared with the standard GEP algorithm,the new algorithm can improve the mean fitness without increasing too much evolutionary time,thus achieving a higher success rate.