Loading...
ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 June 2012, Volume 49 Issue 6
Paper
Survey of Cyber-Physical Systems
Li Renfa, Xie Yong, Li Rui, and Li Lang
2012, 49(6):  1149-1161. 
Asbtract ( 885 )   HTML ( 5)   PDF (1630KB) ( 1207 )  
Related Articles | Metrics
Cyber-physical systems (CPS) are integrations of computing and physical systems. Through embedded computers and networks, CPS has realized the cooperation and fusion of these two systems. It will pose great impacts on way of life and mode of production. CPS is a brand new research area, and many problems still need to be solved when utilizing the existing theories and technologies to construct it. Firstly, the concept, characteristics and architecture of CPS are summarized, and its relations with embedded system and network are analyzed. Then, from the perspective of computing system, network system and control system, the main challenges that CPS met are discussed, and currently available theories and technologies that can be utilized in CPS design and the most recent research advances of it are surveyed. Finally it is proposed that the CPS development of the next step should be led by solving the problems of systems abstraction layer design, modeling, architecture design, data transferring and management and system integration as the main research directions, and also offers the possible solutions for those key problems.
Advances in Active Learning Algorithms Based on Sampling Strategy
Wu Weining, Liu Yang, Guo Maozu, and Liu Xiaoyan
2012, 49(6):  1162-1173. 
Asbtract ( 996 )   HTML ( 1)   PDF (1765KB) ( 1696 )  
Related Articles | Metrics
The classifier in active learning algorithms is trained by choosing the most informative unlabeled instances for human experts to label. In the cycling procedure, the classification accuracy of the model is improved, and then the classifier with high generalization capability is obtained by minimizing the totally labeling cost. Active learning has attracted attentions of researchers both at home and abroad widely. It is pointed out that the active learning technique is a very important research at present. In this paper, the active learning algorithms are introduced by putting a particular emphasis on the sampling strategies. The iterative processes of the learning engine and the sampling engine are described in detail. The existing theories of active learning are summarized. The recent work and the development of active learning are discussed, including their approaches and corresponding sampling strategies. Firstly, the active learning algorithms are categorized into three main classes according to different ways of selecting the examples. And then, the sampling strategies are summarized by analyzing their correlations. The advantages and the shortcomings of sampling strategies are discussed and compared deeply within real applications. Finally the open problems which are still remained, and the interests of active learning in future research are forecasted.
Modeling and Analysis of Multicast Delay in Network Coding-Based Multi-Radio Wireless Mesh Networks
Wang Wei, Yang Ming, Luo Junzhou, and Wu Wenjia
2012, 49(6):  1174-1184. 
Asbtract ( 466 )   HTML ( 0)   PDF (2560KB) ( 375 )  
Related Articles | Metrics
Network coding greatly improves the throughput in multi-radio wireless mesh networks (MR-WMNs), however, it also increases the multicast transmission delay due to packets buffering during the coding/decoding procedure. In order to optimize multicast transmission delay, it is crucial to quantitatively analyze key parameters affecting the performance of WMNs. An average multicast transmission delay (AMTD) optimization scheme is proposed based on modeling and analysis of MR-WMN multicast transmission delay using network coding. Firstly, we propose a multi-radio multicast model consisting of M/M/Nr and GI/GI/1 queueing systems in tandem. Secondly, we analyze the features of multicast transmission delay based on the proposed model, and obtain the quantitative relationship between AMTD and network parameters by computing the sum of average waiting time of two queueing systems. Finally, theoretical analysis and simulation results show that the parameters among network load intensity, channel quality, multicast group size, network coding size and RF allocation ratio, can be used to optimize the average multicast transmission delay. The conclusion is given that the best ratio with lowest delay may not still hold within different network coding sizes for a given network and the average multicast transmission delay optimization can be achieved by adjusting RF receive/send ratio suggested by the AMTD formula.
Closely Social Circuit Based Routing in Social Delay Tolerant Networks
Li Zhi, Li Qianmu, Zhang Hong, and Liu Fengyu
2012, 49(6):  1185-1195. 
Asbtract ( 572 )   HTML ( 1)   PDF (2569KB) ( 604 )  
Related Articles | Metrics
In delay tolerant networks (DTN), multi-copies of packet are used to improve performance by many routing algorithms. But uncontrolled redundant packets will increase the payload of networks even infect network communication especially in large scale social networks. The problem is that the redundant packets which can’t be well controlled by routing algorithm will cause the node’s packet buffer overflow and drop useful packets. In mobile adhoc networks (MANET), using cluster architecture is a feasible way to resolve routing problem and decrease the redundant routing packets in the similar scenarios. But the clustering algorithm in MANET can’t be used in DTN directly, because the topology of DTN changes rapidly and the links between nodes connect intermittently due to the high mobility. In social DTN applications, such as vehicles of the public transportation system or campus mobile networks, it can be found that the node’s mobility (such as time and path) follows a special rule. Based on this characteristic, closely social circuit is defined and a clustering algorithm is presented in which nodes with similar mobility rules can be clustered in the same social circuit. A routing algorithm is proposed based on this social circuit architecture, which consists of spray, forward and epidemic phases. It is proved by the experiment that the proposed clustering method and routing algorithm can effectively control redundant packets, and it is more efficient than other DTN routings used in the high payloads and large scale network scenarios.
An Interpolation Algorithm Based on Sliding Neighborhood in Wireless Sensor Networks
Li Bin, Lin Yaping, Zhou Siwang, Luo Qing, and Yin Bo
2012, 49(6):  1196-1203. 
Asbtract ( 650 )   HTML ( 0)   PDF (2303KB) ( 389 )  
Related Articles | Metrics
There are usually coverage holes caused by uneven deployment of the nodes in wireless sensor network, which brings about many difficulties in various applications, as data value in coverage holes can’t be detected directly. To solve this problem, the major idea so far is to place new nodes into the coverage holes with respect to the coverage percentage. However, it is hard to cover the whole region by deploying new nodes, when the network size is huge. Recently, a few methods are designed to estimate the data value in the coverage hole using sensed data of neighboring nodes. Motivated by this idea, a new moving-neighborhood interpolation algorithm is proposed in this paper. The algorithm based on Delaunay triangulation technique can find out a neighbor set of points by iterative searching, which has strong spatial correlation with interpolation point. Then, the value of interpolation point is able to estimate by our proposed algorithm, according to the observations of neighbor set. Moreover, an adaptive selection technique is designed for searching different neighbor set to meet different error thresholds. Experimental results on a real-world dataset show that our proposed algorithm can estimate the value of coverage holes more accurately and robustly. Besides, it can help retrieve the real-time value of a point in the sensor network.
A Globaltrust-Based Differentiated Service Scheme in BitTorrent
Man Jingui, Wang Miao, Zhang Hanwen, and Zhang Yujun
2012, 49(6):  1204-1210. 
Asbtract ( 519 )   HTML ( 0)   PDF (1340KB) ( 422 )  
Related Articles | Metrics
BitTorrent system suffers from free-riding because free-riding behavior has negative effect on the performance of the system. However, existing mechanisms used to counter free-riding in BitTorrent are not effective enough. In this paper, we propose a global-trust-based differentiated service scheme to deal with free-riding problem. In our scheme, tracker serves as a computation agent to calculate peers' global trust values. With these values, tracker identifies free-riders and contributive peers, and then disseminates the information of free-riders to free-riders and the information of contributive peers to contributive peers. Through such isolation, free-riders will have no chance to connect with contributive peers to obtain resources. Moreover, contributive peers are divided into high-contributors and normal-contributors. Tracker provides differentiated service for these peers according to their return ratios, which makes high-contributors achieve faster download bandwidth. Simulations show that the proposed scheme can significantly isolate and penalize free-riders, thus incentivizing peers to donate more upload bandwidth for the system.
Adaptive Executable Test Sequences Generation from an Extended Finite State Machine
Shu Ting, Liu Lianggui, Xu Weiqiang, and Li Wenshu
2012, 49(6):  1211-1219. 
Asbtract ( 688 )   HTML ( 1)   PDF (1458KB) ( 580 )  
Related Articles | Metrics
Automatic test sequences generation using the extended finite state machine (EFSM) model can improve the test efficiency. However, unexecutable test sequences due to the conflicts among the predicates and internal variables of transitions in an EFSM may exist. The existence of unexecutable test sequences increases the difficulties of automatic test sequences generation. How to determine whether a test sequence is executable becomes a challenging problem. In this paper, the intrinsic characteristics and dependence relations among transitions in an EFSM are discussed in detail. Then an adaptive approach to automated executable test sequence generation for EFSM models is proposed, which is based on an adjacency transition dependence graph. In this method, firstly, transitions are classified according to their variables and predicates; Then dependence relationships between any two adjacency transitions can be mined and defined; Finally, executable test sequences are generated through expanding a reachability analysis tree, with the heuristic guidance using an adaptive exploration function. Experimental results show that, compared with the reachability analysis algorithm based on bread-first-search, the proposed method can reduce the number of states explored in the reachability analysis process and relieve the state explosion problem. As a result, the efficiency of automatic executable test sequences generation is improved. In the worst case, time and space complexity of the proposed method is also not more than the bread-first-search algorithm.
A Load Balanced Switch Architecture Based on Implicit Flow Splitter
Shen Zhijun, and Zeng Huashen
2012, 49(6):  1220-1227. 
Asbtract ( 376 )   HTML ( 0)   PDF (2299KB) ( 343 )  
Related Articles | Metrics
In order to solve the problems of high computation complexity, PHOL (pseudo head of line) blocking, etc. in Byte-Focal switches, this paper proposes a load balanced switch architecture called LB-IFS (load balanced switch based on implicit Flow Splitter). LB-IFS promotes a DBM (double-buffering mode) and a 2-step scheduling scheme to satisfactorily solve the PHOL problem and ensure that packets of the same flow depart from the first crossbar in the same order as they arrive. Furthermore, the novel IFSs (implicit flow splitters) at the input port assign a TFP (theoretical forwarding paths) for individual cells to be used by output ports. The RB (re-sequencing buffer) organized in VIQ (virtual input queue) structure, in conjunction with TFPs, will ensure that packets can be emitted out of switch without disordering conveniently. Theoretic analysis and simulation results have shown that LB-IFS has better performance than Byte-Focal in delay and ensures the computation complexity of O(1) in the whole switching process.
Localization Based on Particle Swarm Optimization with Penalty Function for Wireless Sensor Network
Cai Shaobin, Gao Zhenguo, Pan Haiwei, and Shi Ying
2012, 49(6):  1228-1234. 
Asbtract ( 574 )   HTML ( 1)   PDF (1063KB) ( 474 )  
Related Articles | Metrics
WSN (wireless sensor network) is formed by a large number of cheap sensors, which communicate through an ad hoc wireless network to collect information of sensed objects of a certain area. Hence, it can be used widely in military affairs, environment detection and intelligent home. In most applications of WSN, the acquired information is useful only when the locations of sensors and objects are known. Therefore, localization is one of the most important technologies of WSN. Now, some intelligent algorithms, for example PSO (particle swarm optimization), are studied for node localization in WSN. However, the existing PSO algorithm has lower localization accuracy and convergence speed. Hence, in order to improve the convergence speed and the localization accuracy further, a new localization algorithm based on PSO with penalty function (PSOPF) is proposed in this paper. In PSOPF, an error correction factor is defined to reflect the average error of distance measure between a node and some sample anchors firstly. And then, a penalty function based on error correction factor for PSO is defined to improve its convergence speed and localization accuracy. The simulation results show that, compared with PSO location algorithms, PSOPF has higher positioning accuracy and higher convergence speed.
Dynamic and Comprehensive Evaluation Mothod for Interoperability Trust Based on Fuzzy Variable Weighting
Wang Yanhui, Xiao Xuemei, and Jia Limin
2012, 49(6):  1235-1242. 
Asbtract ( 383 )   HTML ( 0)   PDF (1354KB) ( 410 )  
Related Articles | Metrics
With the development of information technology, information island has become an obstacle to information resources sharing between cross-domains. Interoperability is the key technology to solve this problem. However, establishing good trust relationship is a prerequisite for achieving the interoperation between cross-domains. Under the background of information system interoperability, and from the perspective of the organizational trust relationship, the interoperability trust is studied. On the one hand, the qualitative and quantitative factors affecting the interoperability trust are analyzed, and the trust evaluation index system is established; on the other hand, with the characteristics of local autonomy and dynamic change of interoperability, and in view of the fact that the evaluation index system of interoperability trust is characterized by the comprehensiveness, fuzziness, dynamics and multi-dimension, a dynamic and comprehensive evaluation method for interoperability trust based on fuzzy variable weighting theory is proposed and studied. Finally, the feasibility of the research results above is simulated. It is proved through analysis that the proposed method could implement dynamic change of dynamic trust and interoperability logical reconstruction based on trust. It could also provide support for interoperability access control.
Dimensions of Vector Spaces of Annihilators for Maiorana-McFarland's Bent Functions
Zhang Fengrong, Hu Yupu, Ma Hua, Xie Min, and Zhou Yu
2012, 49(6):  1243-1247. 
Asbtract ( 554 )   HTML ( 0)   PDF (609KB) ( 461 )  
Related Articles | Metrics
It is known that Boolean functions used in stream and block ciphers should have good cryptographic properties to resist the existing efficient attacks. The number of linearly independent low degree annihilators of a given Boolean function and of its complement function is an important parameter for evaluating the complexity of algebraic attacks on the systems using this Boolean function. The dimensions of vector spaces of annihilators for Boolean functions have received much attention in cryptographic literature. According to one-to-one correspondence between Maiorana-McFarland's (M-M) Bent functions and Boolean permutations, a family of Boolean functions are presented. Moreover, it is shown that the presented family of Boolean functions is linearly independent. In addition, it is known that every nonzero linear combination of a Boolean permutation is a balanced Boolean function. On the basis of the above facts, a new upper bound on the dimension of vector spaces of annihilators with prescribed degrees of a special M-M Bent function and of its complement is proposed. As far as the special M-M Bent functions are concerned, the new upper bound is less than the known ones. Furthermore, the new upper bound for all M-M Bent functions can be obtained.
Approximate Model Selection on Regularization Path for Support Vector Machines
Ding Lizhong and Liao Shizhong
2012, 49(6):  1248-1255. 
Asbtract ( 575 )   HTML ( 0)   PDF (1294KB) ( 476 )  
Related Articles | Metrics
Model selection is an indispensable step to guarantee the generalization of support vector machines (SVM). The main problem of existing SVM model selection approaches is that a standard SVM needs to be solved with high complexity for each iteration. In this paper, a novel model selection approach for SVM via kernel matrix approximation and regularization path is proposed, based on the observation that approximate computation is sufficient for model selection. Firstly, a kernel matrix approximation algorithm KMA-α is presented and its matrix approximation error bound is analyzed. Then, an upper model approximation error bound is derived via the error bound of KMA-α. Under the guarantee of these approximation error bounds, an approximate model selection algorithm AMSRP is proposed. AMSRP applies KMA-α to compute a low-rank approximation of the kernel matrix that can be used to efficiently solve the quadratic programming of SVM, and further utilizes the regularization path algorithm to efficiently tune the penalty factor C. Finally, the feasibility and efficiency of AMSRP is verified on benchmark datasets. Experimental results show that AMSRP can significantly improve the efficiency of model selection for SVM, and meanwhile guarantee the test set accuracy. Theoretical and experimental results demonstrate that AMSRP is a feasible and efficient model selection algorithm.
Supervised and Transductive Ranking Algorithms with Relational Objects
Peng Zewu, Tang Yong, Luo Haixia, and Pan Yan
2012, 49(6):  1256-1263. 
Asbtract ( 533 )   HTML ( 0)   PDF (1157KB) ( 499 )  
Related Articles | Metrics
Learning to rank task is a learning process which aims at obtaining a ranking model through machine learning techniques for ranking objects. It has become one of the hot research topics in both information retrieval and machine learning communities recently. In information retrieval and machine learning fields, most of existing learning to rank approaches assume that all objects in a given query are independently and identically distributed. Although this assumption simplifies the ranking problems, the implicit interconnections among objects for each query are not exploited in the learning process. Actually, the information of the implicit interconnections can help improve the ranking performance of the ranking algorithms. In this paper, new methods are proposed in supervised ranking and transductive ranking problems to utilize the latent interconnections. In supervised ranking, a graph based ranking framework is proposed, which takes advantage of global consistency that similar objects deserve similar scores. In transductive ranking, a new query similarity measure by the interconnections among the objects is proposed, such that the more representative objects are, the more importance weighting are obtained for them. Finally, this paper validates the usefulness of relational information among objects by improving the performances of RankSVM-primal algorithm and transductive ranking algorithm in the experiments.
A Weight Design Method Based on Power Transformation for Multi-Objective Evolutionary Algorithm MOEA/D
Liu Hailin, Gu Fangqing, and Cheung Yiuming
2012, 49(6):  1264-1271. 
Asbtract ( 801 )   HTML ( 0)   PDF (1817KB) ( 482 )  
Related Articles | Metrics
In multi-objective optimization problems, it is very important to find a group of uniformly distributed Pareto optimal solutions on Pareto fronts. MOEA/D is one of the promising evolutionary algorithms for multi-objective optimization at present. When the Pareto front is some known types of shape, the MOEA/D can find uniformly distributed Pareto-optimal solutions by using the advanced decomposition. Nevertheless, it is a nontrivial task for the MOEA/D for a general shape of the Pareto front. In this paper, each objective function is transformed by the power function, which makes the Pareto front of multi-objective optimization close to the desired shape. Furthermore, a kind of weight design method of MOEA/D is proposed to solve general multi-objective optimization problem. This paper also discusses the distance preserving character of Pareto front by mathematics transform. MOEA/D, making use of proposed weight design method, easily finds uniformly distributed Pareto optimal solutions for general multi-objective optimization problem. Numerical results show the effectiveness of MOEA/D with the proposed weight design method.
Regularized Semi-Supervised Multi-Label Learning
Li Yufeng, Huang Shengjun, and Zhou Zhihua
2012, 49(6):  1272-1278. 
Asbtract ( 725 )   HTML ( 3)   PDF (743KB) ( 657 )  
Related Articles | Metrics
Multi-label learning is proposed to deal with examples which are associating with multiple class labels simultaneously. Previous multi-label studies usually assume that large amounts of labeled training examples are available to obtain good performance. However, in many real world applications, labeled examples are few and amounts of unlabeled examples are readily available. In order to exploit the abundant unlabeled examples to help improve the generalization performance, we propose a novel regularized inductive semi-supervised multi-label method named MASS. Specifically, aside from minimizing the empirical risk, MASS employs two regularizers to constrain the final decision function. One is to characterize the classifier’s complexity with consideration of label relatedness, and the other requires that similar examples share with similar structural multi-label outputs. This leads to a large scale convex optimization problem, and an efficient alternating optimization algorithm is provided to achieve its global optimal solution in super-linear convergence rate due to the strong convexity of the objective function. Comprehensive experimental results on two real-world data sets, i.e., webpage categorization and gene functional analysis with varied numbers of labeled examples, demonstrate the effectiveness of the proposal.
Invariant Synthesis for Conformant Planning
Zhao Jingjing, Liu Dayou, and Cai Dunbo
2012, 49(6):  1279-1287. 
Asbtract ( 532 )   HTML ( 0)   PDF (952KB) ( 457 )  
Related Articles | Metrics
In order to compress the state space and accelerate the speed of conformant planning, invariants are introduced into conformant planning. Invariants of conformant planning are defined formally, and new knowledge representation “multi-valued conformant planning task” is given. The action model of multi-valued conformant planning is defined accordingly. An invariant synthesis method is proposed for conformant planning and a conformant invariant synthesis algorithm is specified. The synthesis method guesses candidates of invariants firstly. Then the synthesis method tests candidates among all initial world states and all actions according to the properties of conformant invariants. Some candidates are given up and some candidates are modified to form new candidates for testing again. Other candidates are proved to be invariants. Theoretical analysis and experimental results show that the algorithm can synthesize correct invariants and produce multi-value conformant planning tasks. For conformant planning, multi-valued conformant task can greatly compress the state space than Boolean codes used by conformant planning. In order to specify the application of the conformant invariants, the heuristics of reusing plan is combined with the multi-valued conformant tasks for solving the conformant tasks. The comparative experiments with planning system CFF are conducted for testing the efficiency and quality of the combination. Experimental results show that this combination is better than planning system CFF in some domains.
Dynamic Adaptive Differential Evolution Based on Novel Mutation Strategy
Bi Xiaojun, Liu Guo'an, and Xiao Jing
2012, 49(6):  1288-1297. 
Asbtract ( 527 )   HTML ( 0)   PDF (1930KB) ( 564 )  
Related Articles | Metrics
To overcome the slow convergence speed, premature convergence and tedious parameter settings of the differential evolution when solving complex optimization problems, a dynamic adaptive differential evolution, called p-ADE, based on a novel mutation strategy, is proposed. Firstly, the best global solution and the best previous solution of each individual are utilized in the new mutation strategy to guide the search direction by introducing more effective directional information, avoiding the search blindness brought by the random selection of individuals in the difference vector. Secondly, a self-adaptive parameter setting strategy is designed, which is utilized to balance the global and local search dynamically. Experimental results on 10 benchmark functions show that p-ADE can effectively improve the global search ability of DE and outperforms several state-of-the-art optimization algorithms in terms of the main performance indexes.
Query Classification Based on URL Topic
Zhang Yu, Song Wei, Liu Ting, and Li Sheng
2012, 49(6):  1298-1305. 
Asbtract ( 757 )   HTML ( 0)   PDF (1803KB) ( 565 )  
Related Articles | Metrics
Many online resources contain crowd intelligence. Categorized website directory is one kind of resources constructed and maintained manually. It aims to organize websites according to a topical taxonomy. Based on the URLs with topical labels in website directory, a URL topical classifier could be designed. Together with pseudo relevance feedback technique and search engine query logs, an automatic, fast and efficient query topical classification method is proposed. In detail, the method combines two strategies. Strategy-1 is to predict a query’s topic by computing the topic distribution among the returned URLs of a search system. Strategy-2 is to train a statistical classifier using the automatically labeled queries in query logs based on the topic of clicked URLs. The experimental results show that our method can achieve better precision compared with a state of the art algorithm and is more efficient for online processing. It has good scalability and can construct large scale training data from query logs automatically.
An Active Labeling Method for Text Data Based on Nearest Neighbor and Information Entropy
Zhu Yan, Jing Liping, and Yu Jian
2012, 49(6):  1306-1312. 
Asbtract ( 509 )   HTML ( 0)   PDF (862KB) ( 524 )  
Related Articles | Metrics
As it is quite time-consuming to label text documents on a large scale, a kind of text classification with a few labeled data is needed. Thus, semi-supervised text classification emerges and develops rapidly. Different from traditional classification, semi-supervised text classification only requires a small set of labeled data and a large set of unlabeled data to train a classifier. The small set of labeled data is used to initialize the classification model in most cases. Its rationality will affect the performance of the final classifier. In order to make the distribution of the labeled data more consistent with the distribution of the original data, a sampling method is proposed to avoid selecting the K nearest neighbors of the labeled data to be new candidate labeled data. With the help of this method, the data located in various regions will have more opportunities to be labeled. Moreover, in order to obtain more category information from the very few labeled data, this method compares the information entropy of the candidate labeled data and the datum with the highest information entropy is chosen as the next datum to be labeled manually. Experiments on real text data sets suggest that this approach is very effective.
Mining Algorithm of Association Rules Based on Disk Table Resident FP-TREE
Shen Yan, , Song Shunlin, and Zhu Yuquan
2012, 49(6):  1313-1322. 
Asbtract ( 466 )   HTML ( 0)   PDF (3701KB) ( 510 )  
Related Articles | Metrics
As the size of the database to be mined is increasing constantly, the size of physical memory available has become a bottleneck when using FP-GROWTH algorithm for association rules mining. So, it is necessary to tackle space scalability by some new algorithms in order to mine association rules in huge database. Nowadays, disk-resident algorithm has become the main target. Therefore, the original data structure of FP-TREE is improved and a novel algorithm called DTRFP-GROWTH (disk table resident FP-TREE growth) is presented. This algorithm uses disk table for storing FP-TREE to decrease memory usage. When the mining works failed for FP-GROWTH using too much memory, DTRFP-GROWTH can continue to mine association rules from huge database by its special skill called disk table resident FP-TREE, which is suitable to occasions of space performance priority. In addition, this algorithm also integrates association rules mining with RDBMS system. It overcomes the problems of some relative solutions based on file system, such as low performance, high difficulty in development, etc. The correctness verification and performance analysis of the above mentioned algorithm are presented. The experiment results on real world data sets also support effectiveness of this algorithm. The study shows that in memory limited occasion, DTRFP-GROWTH is an effective association rules mining algorithm based on disk.
Temporal Consistency Based Heuristics for Cost Optimization in Workflow Scheduling
Liu Cancan, Zhang Weimin, Luo Zhigang, and Ren Kaijun
2012, 49(6):  1323-1331. 
Asbtract ( 413 )   HTML ( 0)   PDF (1020KB) ( 452 )  
Related Articles | Metrics
Leveling heuristics are used to solve the time-cost trade-off problems in the grid workflow scheduling with temporal constraint by distributing the tasks into groups based on levels and scheduling them level by level. However, due to the absence of an effective method to ensure the temporal constraint, the applicability and performance of these leveling heuristics are damaged. Based on the previous heuristic deadline bottom level (DBL), an advanced heuristic referred to as temporal consistency based deadline bottom level (TCDBL) is proposed by studying the temporal properties of workflows and by optimizing their execution cost based on the temporal consistency. TCDBL satisfies the workflow temporal constraint by setting a consistent temporal point for each task, distributes the redundancy time based on the parallel degree of each level, and optimizes the workflow cost with a soft temporal constraint strategy. As a result, the workflow execution cost decreases. The experimental results in this study demonstrate that the average execution cost of TCDBL is 14% less than the cost of DBL.
Adaptive Software Testing Based on Controlled Markov Chain
Bao Xiao'an, Yao Lan, Zhang Na, and Song Jinyu
2012, 49(6):  1332-1338. 
Asbtract ( 582 )   HTML ( 1)   PDF (976KB) ( 522 )  
Related Articles | Metrics
Adaptive testing for software means that software testing strategy should be adjusted online by using the testing data collected. Existing researches on adaptive testing rely on a simplified controlled Markov chain (CMC) model for software testing, which focus on how to detect and remove all of the defects with minimum expectation cost. The CMC model for software testing employs several unrealistic assumptions and this makes it have limited applicability. In order to overcome the limitations of applicability and low efficiency, this paper presents an improved CMC model with cost constraints by a series of new transformation of limit conditions. This model is designed according to the software cybermetics methodology. It can reach a balance among efficiency, complexity and applicability. Based on this model, a new optimal test strategy of software defects is designed to remove most defects within cost constraints. Then an adaptive testing strategy is proposed which can be adjusted on-line in accordance with the changes of parameters taking place in the controlled object. Finally a set of simulations are conducted and testing results prove the effectiveness of this model.
Noise Image Segmentation Using Fisher Criterion and Regularization Level Set Method
Wen Qiaonong, Wan Suiren, and Xu Shuang
2012, 49(6):  1339-1347. 
Asbtract ( 593 )   HTML ( 0)   PDF (3074KB) ( 483 )  
Related Articles | Metrics
With the active contour model gradually coming to maturity and development, how to improve noise immunity of the model has become an important research topic. Considering the image segmentation from the perspective of the classification, Fisher criterion function is introduced into image segmentation creatively, which uses Fisher criterion to guide the image segmentation and gives Fisher explanation about the C-V model. For the noise image, non-negative robust function is defined as edge-preserving potential function and ensures that the edges are not blurred. In order not to smooth out the edge and texture information in the process of removing noise, we introduce a robust function for regularization, regard Fisher criterion as the standard of image segmentation, and establish a variational level set model which is the combination of region-based model and edge-based model. The model can perform simultaneously denoising and segmentation. The numerical solution of the model is discussed in detail. Experiments confirm that the theory is correct and reliable, and the regularization term constraints are able to achieve good effect in the respect of noise removal and edge preservation during the process of image processing. The model for image denoising and segmentation is more efficient than that using clustering algorithm, relaxation iterative algorithm and mean shift algorithm with three sets of experiments.
An Image Identification Algorithm Based on Digital Signature Method
Li Xiaofei, Shen Xuanjing, Chen Haipeng, and Lü Yingda
2012, 49(6):  1348-1356. 
Asbtract ( 539 )   HTML ( 0)   PDF (2281KB) ( 365 )  
Related Articles | Metrics
In view of the question of images' authenticity, an effective and robust image identification algorithm is presented based on digital signature. Firstly, image is preprocessed to enhance the capability of images' anti-JPEG compression. Then the image is divided into two regions equally, and the top five of image's block average value are extracted and mapped to the element of GF(25) to construct the RS code. The generated check code is scrambled by Arnold transform as digital signature to authenticate the original image. Experimental results show that the algorithm not only can detect whether the content of the image is tampered or not but also can accurately locate the tampered position, which improves the image on the robustness of JPEG compression. Thus this algorithm can effectively distinguish JPEG compression operation from the deliberate tampering.
Spatial Information Services Chaining Based on Graphic-Workflow
Zhang Jianbo, Liu Jiping, and Wang Bei
2012, 49(6):  1357-1362. 
Asbtract ( 455 )   HTML ( 0)   PDF (1334KB) ( 460 )  
Related Articles | Metrics
Traditional workflow technology can't meet the requierments of spatial information services chaining aggregation because of the particularity of the long time cost of spatial data processing and the interface that workflow calls spatial information services chaining. The main problems lie in the mismatch of interface, and low efficiency. Thence, the model of spatial information service chaining aggregation is established, expending the model of traditional WPS chaining whose insufficient is considered. By analyzing the main problems between the interface and spatial data processing about spatial information services during the workflow scheduling, we present corresponding methods of the interface transformation to make the workflow call spatial information services chaining well, and adopt a strategy of GML-compressed scheduling to guarantee the spatial data flow be lowly transmitted on the network. Finally, the concrete solutions of spatial information services chaining processing are presented in the paper combined Kepler workflow engine. The experimental results show that this scheduling method not only breakthroughs interface bottlenecks through the interface transformation used in the workflow before, but also improves spatial information service chain execution efficiency through the strategy transformation of spatial data flow.
Locality Analysis and Optimization for Stream Programs Based on Iteration Sequence
Tang Tao, Yang Xuejun, and Lin Yisong
2012, 49(6):  1363-1375. 
Asbtract ( 501 )   HTML ( 0)   PDF (2789KB) ( 369 )  
Related Articles | Metrics
The stream programming model has been widely studied in recent years, and it is proved to be a good candidate for the stream architecture based on software-managed streaming memory such as stream register file. However, some researches point out that the stream programming model is also beneficial to the hardware-managed coherent cache-based architectures. Besides, general data cache has been integrated into the GPGPU recently, which is the most important scenario where the stream programming model is used. Thus, exploiting the cache locality becomes very critical to improve the performance of the stream programs on these architectures. Due to the particular execution model, the way that the reuse carried by the stream programs is transformed into locality differs from that of serial programs. The traditional locality analysis method cannot be used to analyze the stream programs directly. Based on the detailed analysis of transformation from reuse to locality, we propose the concept of “iteration sequence” to capture the difference between the execution model of stream and serial programs. Then we extend the traditional locality analysis method and propose a general locality analysis method based on the iteration sequence. Further, we propose two locality optimization techniques derived from the locality analysis model. The experimental results obtained on the GPGPUSim simulator illustrate that our quantitative analysis about the locality of stream program is efficient and the locality optimization techniques can evidently improve the locality and the performance.