Current Issue

• 2015, No. 11　Published:25 November 2015 Last issue    Next issue
  Columns in this issue: 论文

• 论文

  Design and implementation of a real time parsing and
  storage system for massive meteorological data 

  WANG Ruotong1，HUANG Xiangdong2，ZHANG Bo2，WANG Jianmin2，LUO Bing1

  2015, 37(11): 245-2054. doi:

  Abstract ( 225 )   PDF (991KB) ( 867 )   　　

  Meteorological data is a typical non-structure data, which reaches dozens of TBs per day. Parsing, storage and access mode based on RDBMS and file systems become the bottleneck of weather forecast data processing system. To fulfill fast and in time queries of realtime data of the users of national weather forecast platform MICAPS’, we depict a stable 7*24 distributed data parsing system, supporting a realtime parsing system containing dozens of TBs per day. According to the multidimension model and the user behaviors of meteorological data, using nonrelational keyvalue DDBMS, we design and implement a high performance massive data storage system. Experiments prove that the proposed real time data parsing system and the massive data storage system based on non-relational key-value DDBMS can meet storage, query and applications requirements of massive meteorological data. This system is also the core system of China weather forecast data flow, possessing excellent functions and performance.

  A marine monitoring big data placement strategy in cloud
  computing environment based on data dependency  

  HUANG Dongmei1,SUI Hongyun1,HE Qi1,ZHAO Danfeng1,DU Yanling1,SU Cheng2

  2015, 37(11): 1989-1996. doi:

  Abstract ( 170 )   PDF (968KB) ( 341 )   　　

  Marine monitoring data is big and has strong data dependency. How to design a fast placement strategy and control the marine data efficiently becomes more and more important for the management and the application of big marine monitoring data. In cloud computing environments, according to the characteristics of big marine monitoring data we propose a placement strategy based on data dependency. Under the condition of guaranteeing the load balancing of data centers, the dependencies among monitoring tasks, monitoring points and monitoring data are considered comprehensively. The dependency of monitoring points, the dependency of monitoring data and the overall dependency of monitoring data are established.According to the three kinds of dependencies, the marine data placement is done so as to make the big marine monitoring data in the same data center with higher dependency.Experimental results show that our strategy reduces the response time of ocean monitoring data access and provides an effective placement strategy for ocean monitoring data.

  A scalable distributed scheduling method
  for large-scale cloud resources  

  LIN Weiwei，ZHU Chaoyue

  2015, 37(11): 1997-2005. doi:

  Abstract ( 144 )   PDF (913KB) ( 288 )   　　

  The energy consumption optimization of resources allocation in the cloud data center with heterogeneous physical servers is an NPHard combinatorial optimization problem. When the number of servers is large, the solution space is large as well. It is therefore quite difficult to get the optimal solution within reasonable time. We propose a scalable distributed scheduling method (SDSM) based on the "Divide and Conquer" idea from the aspect of scheduling model, which implements an efficient resource allocation algorithm in heterogeneous cloud environments. When the number of physical servers in cloud data centers is large, the servers will be divided into several server clusters, and then in every cluster we use Choco to model and solve the constraint satisfaction problem (CPS) of energy consumption optimization in heterogeneous cloud data centers, which can obtain the optimal resource allocation and greatly reduce its complexity. Finally, we compare the proposed SDSM and the nonscalable scheduling method through experiments, and the experimental results show that the SDSM has obvious advantage in largescale cloud resource allocation.

  A design method using lowthreshold cell for
  high performance and low power consumption  

  NI Cancan, ZHAO Zhenyu,TANG Haoyue,QU Lianhua,LI Huan,LI Peng,DENG Quan

  2015, 37(11): 2006-2012. doi:

  Abstract ( 112 )   PDF (1194KB) ( 217 )   　　

  To reduce the overall power consumption of high performance ICs, we compare the high threshold voltage technology with the low one and analyze their different applications. In order to reduce the total power consumption, we use the low threshold voltage technology to reduce the dynamic power consumption. Firstly, we analyze internal power consumption, timing and size of standard cells in the 40nm technology. Under the same delays we then compare the power consumption of the two kinds of inverter chains composed by standard cells with the two thresholds, respectively. We also analyze the dynamic power consumption of the benchmark and AES circuits which are synthesized by high threshold voltage and low threshold voltage  respectively. By comparison, we find out the corresponding threshold voltage design approach for lower power design under the same clock cycle. The synthesis results show that for the circuits with a large ratio of dynamic power consumption to the total power consumption , low threshold voltage design can reduce power consumption; while the ratio of dynamic power consumption is not large, if the low threshold synthesis slack  is positive or the high threshold synthesis slack is negative and the low threshold synthesis slack is zero, a low threshold voltage design can reduce power consumption; or when both of their synthesis slacks are zero, a  high threshold voltage design can achieve lower power consumption.

  Hardware-based data prefetcher
  implementation in Shenwei microprocessors  

  JIA Xun，HU Xiangdong，YIN Fei

  2015, 37(11): 2013-2017. doi:

  Abstract ( 219 )   PDF (795KB) ( 323 )   　　

  The technique of hardwarebased data prefetching can improve microprocessors’ memory access performance efficiently. Implementation of this technique is urgently needed in Shenwei microprocessors to boost their performance, but it faces the restrictions from hardware cost and architectural characteristics. Based on existing research achievements and current industrial applications of prefetching technique, we propose a hardwarebased data prefetcher implementation framework, which is highly coalescent with Shenwei microprocessors’ architectural characteristics. Take the stream prefetcher as an example, the hardware data prefetching technique can improve integer performance of Shenwei microprocessors by 5.17% on average, 28.88% at most; and improve float performance by 6.39% on average, 30.11% at most, while the chip area is only increased by 0.97%.

  A dynamic scheduling method of virtual machines
  for campus cloud teaching services 

  WANG Jing,WANG Gang,GAO Jing,LI Han,MA Qian

  2015, 37(11): 2018-2024. doi:

  Abstract ( 116 )   PDF (721KB) ( 212 )   　　

  With the continuous deepening of teaching informatization, the campus cloud platform is becoming increasingly popular, but the resource utilization in practical applications is still low. The key problem is that the current scheduling mechanism of virtual machines does not take into account the characteristics of campus teaching applications, resulting in a waste of resources and load unbalancing. To tackle this problem, according to the requirements of teaching applications in universities, we put forward a dynamic scheduling algorithm of course virtual machines(CRS), define the course requirement model and the physical machine load model, and implement a campus cloud platform based on the OpenStack. Experimental results show that the platform achieves energy consumption reduction and load balancing.

  Study and implementation of a parallel range alignment
  algorithm based on OpenMP  

  ZHANG Jiajia1，JIANG Weidong1，LI Kuan2

  2015, 37(11): 2025-2029. doi:

  Abstract ( 139 )   PDF (679KB) ( 197 )   　　

  By using the accumulated cross correlation algorithm based on rectangular window and the minimum entropy algorithm based on the frequency shifting property of the Fourier transform, we aligne a one dimensional range profile. Traditional range alignment algorithms suffer from large data, high complexity, long running time, etc. To overcome such problems, we propose a parallel range alignment algorithm for multicore processors. We use two compiling instructions "#pragma omp section” and "#pragma omp for” of OpenMP for the accumulated cross correlation algorithm and the minimum entropy algorithm to achieve multithreads parallel optimization. Theoretical analysis and experimental results show that the proposed method can increase the execution efficiency largely .

  Design and analysis of a novel synthesisable ADPLL 

  ZHAO Xin，YU Sichen,MIN Hao,WANG Biao,HUANG Yongqin

  2015, 37(11): 2030-2034. doi:

  Abstract ( 183 )   PDF (694KB) ( 203 )   　　

  The All Digital Phase Locked Loop (ADPLL) features higher design density, flexible configurability, and swift transplant to another technology. The ADPLL can solve some bottleneck problems of analogy PLL, such as the big area of passive devices, sensitivity to noise, long lock time and difficult transplant between technologies. In nanometer technology, the minimmal inverter delay is decreased within ten ps, so the jitter performance of the ADPLL is improved greatly. We introduce a new ADPLL structure used in high performance microprocessors.A Sdomain modeling and a noise analysis are conducted based on the proposed ADPLL. This structure is designed by standard cells.The highest frequency can reach 2.4GHz, and the jitter performance is about 2ps.

  Stream Eager transmission:a performance optimization
  technique for the distributed stream architecture 

  LI Xin1,3,GUO Xiaowei1,LIN Yufei2

  2015, 37(11): 2035-2044. doi:

  Abstract ( 73 )   PDF (994KB) ( 195 )   　　

  The distributed stream architecture extends the stream model in the distributed environment, which can provide an efficient and lowcost execution environment for big data computing applications in the Internet. Meanwhile, the long communication overhead in the Internet restricts the performance of the distributed stream architecture. We propose a data stream Eager transmission technique and implement it in a prototype system of the distributed stream architecture, which improves the performance of applications by exploring the parallelism between communications and computation, as well as hides communication latency. Experimental results show that the proposed technique averagely gains a 19.58% reduction of the execution time cost, significantly improves the performance of the applications and has a promising prospec.

  A novel performance evaluation method for processing
  video/image stream based on Spark Streaming 

  HUANG Wenhui，FENG Rui

  2015, 37(11): 2055-2060. doi:

  Abstract ( 124 )   PDF (735KB) ( 267 )   　　

  Intelligent video surveillance technology has a promising application prospect and growing demand in public safety, traffic management, smart city, etc. With a growing number of cameras used in video surveillance, the amount of image data collected by cameras is becoming bigger and bigger, which is out of the processing capacity of one single machine. The rise and development of distributed computing provides a good way to solve the problem of big data processing. We introduce a testing platform based on Spark Streaming, which is used to process video/image data received as stream, and illustrate the composition and working process of the platform. The impact of several important parameters on the performance of the cluster is deeply studied. In particular, the timeoccupancyrate of the CPU is initially proposed as one of the performance evaluating indicators, and together with the total processing time, it demonstrates the performance and resource usage of clusters more comprehensively.

  A dock mining algorithm for massive vessel
  location data based on improved DBSCAN   

  DING Zhaoying1,YAO Di2,WU Lin2,BI Jingping2,ZHAO Ruilian1

  2015, 37(11): 2061-2067. doi:

  Abstract ( 150 )   PDF (771KB) ( 320 )   　　

  In the background of "Onebelt, Oneroad " maritime strategy in current China, maritime industry is booming, and a lot of new docks are under construction. How to quickly and accurately update the space data of wharfs has a strong practical significance for analyzing foreign trades and improving the efficiency of port services. Artificial means are currently the major approach to update marine charts, but an update interval is usually between 3 and 12 months, which cannot meet the demand. As a new approach to obtain space information of docks, we can apply Including Inmarsat C system, Beidou satellite, Argos satellite and other means to obtain vessel position data for dock mining. We propose a dock mining algorithm based on selfoptimizing parameters DBSCAN (densitybased clustering) for large scale vessel position data from Automatic Identification System (AIS ). On the one hand, the DBSCAN core parameters of different vessel types with different density distributions can be automatically optimized and learnt, and the mooring areas containing docks then can be mined out flexibly. On the other hand, by fusing with the integration of landbased structures and other spatial data, we can exclude anchor zones in mooring regions, berthing areas and etc, with high accuracy. Experiments on Chinese real locus of RoRo real data and the international trajectory data over the past two years (April 2012~April 2014) show that the proposed algorithm can mine docks with an accuracy rate of 93%.

  A dynamic level scheduling algorithm based on a
  Bayesian subjective trust model for cloud computing 

  QI Ping,WANG Fucheng,ZHU Guihong

  2015, 37(11): 2068-2077. doi:

  Abstract ( 79 )   PDF (763KB) ( 237 )   　　

  Aiming at the trust problem existing in cloud computing environment, we first propose a subjective trust model based on the Bayesian method to quantify and evaluate the trustworthiness of computing nodes, and demonstrate its mathematical description and implementation. Duo to the characteristics of dynamic, heterogeneity and deception, resource nodes are inevitably unreliable in cloud environments. So we also introduce a punishment mechanism and a pruningfiltering mechanism. We finally propose a dynamic level scheduling algorithm based on a Bayesian subjective trust model named BSTDLS by integrating the existing DLS algorithm. Theoretical analyses and simulation experimental results prove that the BSTDLS algorithm can efficiently improve the ratio of successful execution at the cost of sacrificing fewer schedule length.

  Dilution and mixing optimization for
  digital microfluidic biochips 

  ZHANG Ling,MEI Junjin

  2015, 37(11): 2078-2083. doi:

  Abstract ( 129 )   PDF (750KB) ( 210 )   　　

  Digital microfluidic (DMF)based biochips are a promising category of labonchips (LOCs), in which nanolitervolume fluid droplets are manipulated on a 2D electrode array. A key challenge in designing such chips and mapping labbench protocols to a LOC is to carry out the dilution process of biochemical samples efficiently. We present a solution preparation on the digital microfluidic biochips according to the mixer sources on the chips, and propose the corresponding dilution/mixing algorithm. The production of waste droplets and the error in concentration factor are discussed in the paper. Simulation results show that the proposed technique can make solution preparation efficiently and accurately.

  A spatial keyword query algorithm based on HBase  

  SHAO Qifeng1,LI Feng2

  2015, 37(11): 2084-2090. doi:

  Abstract ( 111 )   PDF (528KB) ( 216 )   　　

  According to the shortcomings of traditional relational databases in handling massive spatial text data, we present a spatial keyword index scheme based on HBase, which  integrates Geohash codes and word segmentation. In addition, on the basis of the spatial keyword index, we also propose a spatial keyword query algorithm within polygon regions. Compared with traditional index schemes based on longitude and latitude coordinates, the proposed algorithm achieves better efficiency and scalability .

  Study on the main factors determining the quality of
  edge ordering in BDDbased networks 

  PAN Zhusheng,MO Yuchang

  2015, 37(11): 2091-2098. doi:

  Abstract ( 93 )   PDF (609KB) ( 196 )   　　

  The computational complexity of network reliability analysis based on the Binary Decision Diagram (BDD) is closely related to the size of BDD, which depends crucially on the quality of edge ordering. So it is of importance to find the best edge ordering that attempts to minimize the memory using BDD manipulation. However, it is still NPhard to find the optimal edge ordering. In practice,heuristic ordering methods such as BreadthFirstSearch (BFS ) or DepthFirstSearch (DFS )，which are suitable for different types of networks, are commonly used.Unfortunately,no formal guidelines or factors which determine the quality of edge ordering are available for choosing a better heuristic approach for the given network. In this work,characterizing the Boundary Set Length (BSL) as the quality of edge ordering, we reveal the relationship between the BSL and the size of BDD.Empirical studies show that the BSL has positive correlation with the size of BDD.This means the smaller the BSL of an edge ordering, the smaller the size of BDD model generated. In most cases, the size of the BDD can get (or be close to) the extreme value when the BSL has its extreme one. This conclusion is useful for choosing or designing high performance edge ordering for a given network.

  A novel reliable multicast mechanism in
  satellite networks based on network coding  

  GUI Yongmao1,ZHAO Baokang1,TANG Zhu1,PENG Wei1,XIA Yan2,XU Fen3

  2015, 37(11): 2099-2104. doi:

  Abstract ( 98 )   PDF (697KB) ( 261 )   　　

  Satellite communication channels have the properties of natural broadcasting and wide area coverage, which make it attractive to carry out multicast services in satellite networks. However, the features of long transmission delay, high bit error and nonsymmetrical link cause large number of message loss, making it difficult to guarantee the multicast reliability. We propose a reliable multicast mechanism named NCM based on the network coding for satellite networks. NCM can recover multiple lost packets locally at the receiving end via sending redundant coding information generated from the original data packets. At the same time, combining with the mechanism of Automatic Repeating reQuest（ARQ）, it can restore multiple lost primitive packets by retransmitting only one coded package when the original and its redundant coded messages are lost simultaneously. Theoretical analysis and simulation results validate the feasibility and effectiveness of the mechanism.

  A novel node influence measurement algorithm based
  on characteristics of users and propagation 

  SHANG Yan，FAN Xinwei，YU Hong

  2015, 37(11): 2105-2111. doi:

  Abstract ( 102 )   PDF (525KB) ( 321 )   　　

  During the spreading process of microblogs, key nodes play an important role as “attitude leaders”. It is essential to figure out those key nodes for analyzing and monitoring public sentiments. As propagation nodes, users’ variety not only depends on their own characteristics, but also the characteristics of propagation. We select three indicators among two characteristics and adopt the evaluation array of the analytic hierarchy process to assess these indicators. User coefficient and propagation coefficient are used as the node weight and the edge weight respectively, thus forming a double weighted topological graph. Then we establish a novel node influence measurement algorithm of nodes based on the characteristics of users and propagation to evaluate the influence of each node. Compared with existing algorithms, the proposed algorithm can evaluate the importance of key nodes more accurately and objectively during propagation process.

  A risk minimization authorization model
  based on knowledge discovery 

  ZHAO Bin1，2，HE Jingsha1， ZHANG Yixuan1，JI Xinrong1

  2015, 37(11): 2112-2120. doi:

  Abstract ( 100 )   PDF (508KB) ( 260 )   　　

  Access control technology is one of the core technologies of network information system security. For authorization requirements in access control of open networks, in this paper we propose a Risk Minimization Authorization Model based on Knowledge Discovery (RMAMKD), in which the model elements, relationships, constraints and rules and the authorization policies are formally defined. We introduce the concepts of trust and risk to finegrained permissions in the RMAMKD model, regard the entity attributes involved in the interaction and their trust value and risk value as the important reference basis of judging the authorization, and join the time constraint to better support the dynamic authorization mechanism. Finally, we give the RMAMKD authorized application example and do safety analysis, which show that the RMAMKD model can effectively guarantee safe accesses to the object resources.Key words:

  Analyzing and verifying an open authorization
  protocol OAuth 2.0 with SPIN 

  CHENG Daolei,XIAO Meihua,LIU Xinqian,MEI Yingtian,LI Wei

  2015, 37(11): 2121-2127. doi:

  Abstract ( 95 )   PDF (554KB) ( 178 )   　　

  The OAuth 2.0 is an open authorization protocol which solves the problem of user accounts associating and resources sharing. However, due to its weak security, massive user information of network companies is leaking. Besides, the https channel used by OAuth 2.0 to transmit data is inefficient, making the OAuth 2.0 an attack object   of hackers. We propose an open authorization protocol, which transmits the data of the OAuth 2.0 protocol in http channels, model the protocol based on the Promale language and DolevYao attacker model, and employ the SPIN for model checking. The results of formal analysis show that the OAuth2.0 protocol encrypted by the public key encryption system is unsafe. The proposed modeling method has great significance in formal analysis of similar license agreement.

  A web cache replacement algorithm based on collaborative filtering 

  WU Junlong，YANG Qing

  2015, 37(11): 2128-2133. doi:

  Abstract ( 136 )   PDF (481KB) ( 269 )   　　

  To address the shortcoming that the GDSF replacement algorithm cannot predict visit frequency, we propose a collaborative filtering based GDSF web cache replacement algorithm (GDSFCF). Considering the similarities among web objects and the time interval of users’ visits, we use the collaborative filtering technology to generate the predicted visit frequency of each web object, and adopts Zipflike parameters to modify the objective functions of the GDSF algorithm. When cache replacement is performed, the value of the objective functions are used to calculate the caching value of each web object, and the web object with the minimum value will be replaced in the first place. Simulation experiments show that the GDSF-CF algorithm has a higher hit rate and byte hit rate.