Volume 18,Issue 6,2007 Table of Contents
2007, 18(6):1257-1269.
Abstract:
he current research progresses and the existing problems of smantics representation of the semantic Web are analyzed. A kind of new fuzzy description logic FSHOIQ (fuzzy SHOIQ) for semantics representation of the semantic Web is presented, and the syntax and semantics of FSHOIQ are given. The fuzzy Tableaux of FSHOIQ is presented, then the ABox satisfiability reasoning algorithm of FSHOIQ based on the fuzzy Tableaux is presented, and the correctness of the satisfiability reasoning algorithm is proved. The TBox expansion and elimination methods are presented. It is proved that TBox subsumption reasoning problem may be translated into a satisfiability reasoning problem in FSHOIQ. Theoretical foundation for fuzzy knowledge representation and reasoning of the semantic Web is provided through FSHOIQ.
he current research progresses and the existing problems of smantics representation of the semantic Web are analyzed. A kind of new fuzzy description logic FSHOIQ (fuzzy SHOIQ) for semantics representation of the semantic Web is presented, and the syntax and semantics of FSHOIQ are given. The fuzzy Tableaux of FSHOIQ is presented, then the ABox satisfiability reasoning algorithm of FSHOIQ based on the fuzzy Tableaux is presented, and the correctness of the satisfiability reasoning algorithm is proved. The TBox expansion and elimination methods are presented. It is proved that TBox subsumption reasoning problem may be translated into a satisfiability reasoning problem in FSHOIQ. Theoretical foundation for fuzzy knowledge representation and reasoning of the semantic Web is provided through FSHOIQ.
2007, 18(6):1270-1281.
Abstract:
Model checking and refinement checking are two approaches to formal verification, whose difficulties are due to the state explosion problem. As one of the proposed solutions to the problem, it is suggested to introduce compositionality in model checking and refinement checking based on the idea of divide-and-conquer, by which the verification task of the whole system is decomposed to several smaller subtasks on the subsystems. In a uniform framework, this paper surveys the approaches of compositional model checking and compositional refinement checking in a systematic way. From the perspective of module checking, the principle and verification strategies of the two compositional verification approaches are introduced. In addition, the complexities of various kinds of related problems are summarized and a comparison is made between compositional model checking and compositional refinement checking, which exposes the intrinsic relation between them. Finally, some trends are given for the future research.
Model checking and refinement checking are two approaches to formal verification, whose difficulties are due to the state explosion problem. As one of the proposed solutions to the problem, it is suggested to introduce compositionality in model checking and refinement checking based on the idea of divide-and-conquer, by which the verification task of the whole system is decomposed to several smaller subtasks on the subsystems. In a uniform framework, this paper surveys the approaches of compositional model checking and compositional refinement checking in a systematic way. From the perspective of module checking, the principle and verification strategies of the two compositional verification approaches are introduced. In addition, the complexities of various kinds of related problems are summarized and a comparison is made between compositional model checking and compositional refinement checking, which exposes the intrinsic relation between them. Finally, some trends are given for the future research.
2007, 18(6):1282-1286.
Abstract:
In this paper, some topological characterizations of automata theory based on quantum logic (abbr. l-valued automata theory) are discussed. First, l-valued successor and source operators are redefined and the equivalences of l-valued successor operators, source operators and l-valued subautomata are demonstrated. Afterwards, some topological characterizations in terms of the l-valued successor. source operators and l-valued subautomata are described, and then some fundamental properties of l-valued successor operators, source operators and l-valued subautomata are characterized. Particularly, when the multiplication (&) is distributive over the union in the truth-value lattices, some of the special properties of l-valued successor operators, source operators and l-valued subautomata are verified. So a weaker limitation to form a topology is obtained. Finally, it is shown that the l-valued topologies in terms of the l-valued successor, source operators and l-valued subautomata are equivalent.
In this paper, some topological characterizations of automata theory based on quantum logic (abbr. l-valued automata theory) are discussed. First, l-valued successor and source operators are redefined and the equivalences of l-valued successor operators, source operators and l-valued subautomata are demonstrated. Afterwards, some topological characterizations in terms of the l-valued successor. source operators and l-valued subautomata are described, and then some fundamental properties of l-valued successor operators, source operators and l-valued subautomata are characterized. Particularly, when the multiplication (&) is distributive over the union in the truth-value lattices, some of the special properties of l-valued successor operators, source operators and l-valued subautomata are verified. So a weaker limitation to form a topology is obtained. Finally, it is shown that the l-valued topologies in terms of the l-valued successor, source operators and l-valued subautomata are equivalent.
2007, 18(6):1287-1297.
Abstract:
This paper proposes an approach, namely the arena’s principle (AP), to construct the Pareto optimal solutions by utilizing features of the multi-objective evolution. It is proved that the AP works correctly and its computational complexity is O(rmN) (0<1). Theoretically, when AP is compared with Deb’s algorithm and Jensen’s algorithm (their computational complexity are O(rN2) and O(Nlog(r-1)N) respectively), AP is better than Deb’s, and is also better than Jensen’s when the objective number r is relatively large (such as r≥5). Moreover, AP performs better than the other two algorithms when m/N is relatively small (such as m/N≤50%). Experimental results indicate that AP performs better than the other two algorithms on the CPU time efficiency. In applications, AP can be integrated into any Pareto-based MOEA to improve its running efficiency.
This paper proposes an approach, namely the arena’s principle (AP), to construct the Pareto optimal solutions by utilizing features of the multi-objective evolution. It is proved that the AP works correctly and its computational complexity is O(rmN) (0
2007, 18(6):1298-1307.
Abstract:
Finding common pattern, motifs or signals, in a set of DNA sequences is an important problem in computational biology. Recently, some biologists extremely focus on the (l,d)-(K-k) motif finding problem when the number of sequences K is 20 and the number of sequences with instances k is 16, (l,d)-(20-16) problem for short. For solving this problem, this paper introduces a novel sample-driven algorithm (SDA), called color coding motif finding algorithm, CCMF for short. It uses color coding technology to converse a (l,d)-(20-16) problem to some (l,d)-(16-16) problems, then uses divide-and-conquer and branch-and-bound approaches to solve this (l,d)-(16-16) problem. Using the conversion process can reduce 4 845 combinations to 403 colorings, while increasing the running rate enormously. The experimental results on synthetic and real datasets show that the CCMF algorithm can accurately and efficiently find all (l,d)-(20-16) patterns and instances. Its comprehensive performances in finding motifs are superior to those of other existing algorithms. It is applicable for real biological purpose. The color coding technology can also be used to improve the performances of other similar (l,d)-(K-k) problems when k is less than K.
Finding common pattern, motifs or signals, in a set of DNA sequences is an important problem in computational biology. Recently, some biologists extremely focus on the (l,d)-(K-k) motif finding problem when the number of sequences K is 20 and the number of sequences with instances k is 16, (l,d)-(20-16) problem for short. For solving this problem, this paper introduces a novel sample-driven algorithm (SDA), called color coding motif finding algorithm, CCMF for short. It uses color coding technology to converse a (l,d)-(20-16) problem to some (l,d)-(16-16) problems, then uses divide-and-conquer and branch-and-bound approaches to solve this (l,d)-(16-16) problem. Using the conversion process can reduce 4 845 combinations to 403 colorings, while increasing the running rate enormously. The experimental results on synthetic and real datasets show that the CCMF algorithm can accurately and efficiently find all (l,d)-(20-16) patterns and instances. Its comprehensive performances in finding motifs are superior to those of other existing algorithms. It is applicable for real biological purpose. The color coding technology can also be used to improve the performances of other similar (l,d)-(K-k) problems when k is less than K.
2007, 18(6):1308-1318.
Abstract:
A distributed topology control algorithm for ad hoc networks with directional antennas is proposed in this paper. The topology is controlled not only by adjusting the transmission powers of nodes but also by changing the antenna’s pattern (direction). A node grows its transmission power until it finds some neighbor nodes in every sector of its directional antenna. Two planarized optimizations that further reduce some redundant edges are employed and make the topology as a planar graph eventually. The resulting network topology increases network lifetime by reducing transmission power and decreases traffic interference by having low node degrees. Simulation results demonstrate the effectiveness of the proposed algorithm.
A distributed topology control algorithm for ad hoc networks with directional antennas is proposed in this paper. The topology is controlled not only by adjusting the transmission powers of nodes but also by changing the antenna’s pattern (direction). A node grows its transmission power until it finds some neighbor nodes in every sector of its directional antenna. Two planarized optimizations that further reduce some redundant edges are employed and make the topology as a planar graph eventually. The resulting network topology increases network lifetime by reducing transmission power and decreases traffic interference by having low node degrees. Simulation results demonstrate the effectiveness of the proposed algorithm.
2007, 18(6):1319-1327.
Abstract:
A general-purpose parallel three-list six-table algorithm that can solve a number of knapsack-like NP-complete problems is developed in this paper. This kind of problems includes knapsack problem, exact satisfiability problem, set covering problem, etc. Running on an EREW PRAM model, The proposed parallel algorithm can find a solution of these problems of size n in O(27n/16) time, with O(213n/48) space and O(2n/8) processors, resulting in a time-space-processor tradeoff of O(25n/6). The performance analysis and comparisons show that it is both work and space efficient, and thus is an improved result over the past researches. Since it can break greater variables knapsack-based cryptosystems and watermark, the new algorithm has some cryptanalytic significance.
A general-purpose parallel three-list six-table algorithm that can solve a number of knapsack-like NP-complete problems is developed in this paper. This kind of problems includes knapsack problem, exact satisfiability problem, set covering problem, etc. Running on an EREW PRAM model, The proposed parallel algorithm can find a solution of these problems of size n in O(27n/16) time, with O(213n/48) space and O(2n/8) processors, resulting in a time-space-processor tradeoff of O(25n/6). The performance analysis and comparisons show that it is both work and space efficient, and thus is an improved result over the past researches. Since it can break greater variables knapsack-based cryptosystems and watermark, the new algorithm has some cryptanalytic significance.
2007, 18(6):1328-1349.
Abstract:
This paper anatomizes all actions in planning domain, proposes a descriptive method for the relations between preconditions and effects of action, and defines some basic relations between preconditions and effects of action, such as direct concomitant relation, conditional concomitant relation, and direct obstructive relation. These basic relations express the domain knowledge hiding in the definition of actions. For these basic relations, this paper defines some compound operations, and obtains indirect obstructive relations and absolute obstructive relations. The indirect obstructive relation shows the transitivity of preconditions of action, and the absolute obstructive relation expresses the impact on other predications when one predication is realized by action. Finally, this paper gives some applications of these relations in the planning system. These relations are the essential theory basis for sorting predications in target state, judging the target state, and optimizing the strategy of action selection for one predication.
This paper anatomizes all actions in planning domain, proposes a descriptive method for the relations between preconditions and effects of action, and defines some basic relations between preconditions and effects of action, such as direct concomitant relation, conditional concomitant relation, and direct obstructive relation. These basic relations express the domain knowledge hiding in the definition of actions. For these basic relations, this paper defines some compound operations, and obtains indirect obstructive relations and absolute obstructive relations. The indirect obstructive relation shows the transitivity of preconditions of action, and the absolute obstructive relation expresses the impact on other predications when one predication is realized by action. Finally, this paper gives some applications of these relations in the planning system. These relations are the essential theory basis for sorting predications in target state, judging the target state, and optimizing the strategy of action selection for one predication.
2007, 18(6):1350-1360.
Abstract:
This paper introduces an affine invariant of trapezia, and the explicit constraint equation between the intrinsic matrix of a camera and the similarity invariants of a trapezium are established using the affine invariant. By this constraint, the inner parameters, motion parameters of the cameras and the similarity invariants of trapezia can be linearly determined using some prior knowledge on the cameras or the trapezia. The proposed algorithms have wide applicability since parallel lines are not rare in many scenes. Experimental results validate the proposed approaches. This work presents a unifying framework based on the parallelism constraint, and the previous methods based on the parallelograms or the parallelepipeds can be integrated into this framework.
This paper introduces an affine invariant of trapezia, and the explicit constraint equation between the intrinsic matrix of a camera and the similarity invariants of a trapezium are established using the affine invariant. By this constraint, the inner parameters, motion parameters of the cameras and the similarity invariants of trapezia can be linearly determined using some prior knowledge on the cameras or the trapezia. The proposed algorithms have wide applicability since parallel lines are not rare in many scenes. Experimental results validate the proposed approaches. This work presents a unifying framework based on the parallelism constraint, and the previous methods based on the parallelograms or the parallelepipeds can be integrated into this framework.
2007, 18(6):1361-1368.
Abstract:
The detector generation is the key step of negative selection. Current detector generation algorithms have holes area and redundancy detector problems. A negative selection algorithm with the variable length detector is proposed in this paper. This algorithm can not only remove the holes, but also decrease redundancy detectors by the corresponding detector optimization algorithm. Therefore, both the detector generation efficiency and the detecting efficiency are improved well. This algorithm is analyzed in this paper and verified by experiments. The experimental results prove that this algorithm is better than the traditional negative selection algorithms and the negative selection algorithm with the r-adjustable detector.
The detector generation is the key step of negative selection. Current detector generation algorithms have holes area and redundancy detector problems. A negative selection algorithm with the variable length detector is proposed in this paper. This algorithm can not only remove the holes, but also decrease redundancy detectors by the corresponding detector optimization algorithm. Therefore, both the detector generation efficiency and the detecting efficiency are improved well. This algorithm is analyzed in this paper and verified by experiments. The experimental results prove that this algorithm is better than the traditional negative selection algorithms and the negative selection algorithm with the r-adjustable detector.
2007, 18(6):1369-1378.
Abstract:
There exist some issues in current intrusion detection algorithms such as unbalanced detection performance on different types of attacks, and redundant or useless features that will lead to the complexity of detection model and degradation of detection accuracy. This paper presents an ensemble approach to intrusion detection based on improved multi-objective genetic algorithm. The algorithm generates the optimal feature subsets, which achieve the best trade-off between detection rate and false positive rate through an improved MOGA. And the most accurate and diverse base classifiers are selected to constitute the ensemble intrusion detection model by selective ensemble approach. The experimental results show that the algorithm can solve the feature selection problem of intrusion detection effectively. It can also achieve balanced detection performance on different types of attacks while maintaining high detection accuracy.
There exist some issues in current intrusion detection algorithms such as unbalanced detection performance on different types of attacks, and redundant or useless features that will lead to the complexity of detection model and degradation of detection accuracy. This paper presents an ensemble approach to intrusion detection based on improved multi-objective genetic algorithm. The algorithm generates the optimal feature subsets, which achieve the best trade-off between detection rate and false positive rate through an improved MOGA. And the most accurate and diverse base classifiers are selected to constitute the ensemble intrusion detection model by selective ensemble approach. The experimental results show that the algorithm can solve the feature selection problem of intrusion detection effectively. It can also achieve balanced detection performance on different types of attacks while maintaining high detection accuracy.
2007, 18(6):1379-1399.
Abstract:
Peer-to-Peer (P2P) has been one of the most important architectures for Internet applications for its inherent scalability, fault tolerance, and high performance. The research of P2P storage systems is one of the hottest issues, and P2P storage system is regarded as one of the most promising P2P applications. However, to provide durable data storage is not trivial work and sets great barrier to real deployed systems. This paper surveys the P2P storage systems and techniques for durable storage. This paper first introduces the basic components of a durable P2P storage system and the advantages by using P2P architecture, and then introduces a series of techniques for durable storage including data redundancy, data placement, failure detection and data maintenance. Following the research framework, some typical P2P storage systems and their techniques are introduced. By a detailed comparison, the pros and cons of the techniques are discussed. In the end, the problems in current research and some future research issues are outlined.
Peer-to-Peer (P2P) has been one of the most important architectures for Internet applications for its inherent scalability, fault tolerance, and high performance. The research of P2P storage systems is one of the hottest issues, and P2P storage system is regarded as one of the most promising P2P applications. However, to provide durable data storage is not trivial work and sets great barrier to real deployed systems. This paper surveys the P2P storage systems and techniques for durable storage. This paper first introduces the basic components of a durable P2P storage system and the advantages by using P2P architecture, and then introduces a series of techniques for durable storage including data redundancy, data placement, failure detection and data maintenance. Following the research framework, some typical P2P storage systems and their techniques are introduced. By a detailed comparison, the pros and cons of the techniques are discussed. In the end, the problems in current research and some future research issues are outlined.
2007, 18(6):1400-1418.
Abstract:
XML has become the de facto standard for data representation and exchange for Web applications, such as digital library, Web service, and electronic business. How to retrieve interesting information from the promising XML data is an active research area. Among techniques in this area, the description of query patterns is a crucial section. This paper reviews the actualities of recent researches on this topic. It classifies the query descriptors into two categories, XML Query type and XML IR type (with three subcategories: XML IR/keyword, XML IR/fragment and XML IR/query), and concludes three popular problems: Twig pattern processing, SLCA (smallest lowest common ancestor) problem, and similarity measuring techniques for retrieved XML fragments. It analyzes the virtue and deficiency of related techniques based on their convenience for common users. And hereby it proposes four issues for further XML querying researches: structural keywords and corresponding structural similarity measuring, wiping off the redundancy in XML data processing between XML Query (including XML IR/query) and XML IR/keyword, theoretical discussion of XML Query and its realization, and the management of peculiar XML data.
XML has become the de facto standard for data representation and exchange for Web applications, such as digital library, Web service, and electronic business. How to retrieve interesting information from the promising XML data is an active research area. Among techniques in this area, the description of query patterns is a crucial section. This paper reviews the actualities of recent researches on this topic. It classifies the query descriptors into two categories, XML Query type and XML IR type (with three subcategories: XML IR/keyword, XML IR/fragment and XML IR/query), and concludes three popular problems: Twig pattern processing, SLCA (smallest lowest common ancestor) problem, and similarity measuring techniques for retrieved XML fragments. It analyzes the virtue and deficiency of related techniques based on their convenience for common users. And hereby it proposes four issues for further XML querying researches: structural keywords and corresponding structural similarity measuring, wiping off the redundancy in XML data processing between XML Query (including XML IR/query) and XML IR/keyword, theoretical discussion of XML Query and its realization, and the management of peculiar XML data.
2007, 18(6):1419-1428.
Abstract:
In the similarity query processing based on high dimensional indexing, the searching space is usually narrowed down by pruning the inactive subspaces which do not contain any query results. However, among the active subspaces, some of them do not contain any query results at all, those are called false active subspaces. It is obvious that the performance of query processing degrades in the presence of false active subspaces. The problem becomes seriously in the case of high dimensional data. The experiment in this paper shows that the number of accesses to false active subspaces increases as the dimensionality increases. In order to overcome the problem, a space mapping approach is proposed to reduce such unnecessary accesses. For a given query, it can be refined by filtering within its mapped space. A maximal gap space mapping strategy, MaxGapMapping, is proposed to improve the efficiency of the refinement processing. An index structure——MS-tree, the algorithms of construction, and query processing based on this refining method are designed and implemented. Finally, the performance of MS-tree is systemically compared with that of other competitors in terms of range queries based on a real data set.
In the similarity query processing based on high dimensional indexing, the searching space is usually narrowed down by pruning the inactive subspaces which do not contain any query results. However, among the active subspaces, some of them do not contain any query results at all, those are called false active subspaces. It is obvious that the performance of query processing degrades in the presence of false active subspaces. The problem becomes seriously in the case of high dimensional data. The experiment in this paper shows that the number of accesses to false active subspaces increases as the dimensionality increases. In order to overcome the problem, a space mapping approach is proposed to reduce such unnecessary accesses. For a given query, it can be refined by filtering within its mapped space. A maximal gap space mapping strategy, MaxGapMapping, is proposed to improve the efficiency of the refinement processing. An index structure——MS-tree, the algorithms of construction, and query processing based on this refining method are designed and implemented. Finally, the performance of MS-tree is systemically compared with that of other competitors in terms of range queries based on a real data set.
2007, 18(6):1429-1442.
Abstract:
How to process twig query quickly and correctly has attracted much attention in research society recently. Filtering query irrelevant elements before query execution is an important step for reducing elements scanned at query processing. As a flattened structural index, F-Index is proposed to filter out all query irrelevant index nodes, thus query irrelevant elements can be filtered out rapidly and mostly, especially when it is processing deeply nested XML documents with a complex structure. After filtering, a new efficient query algorithm based on the remaining elements is proposed to accelerate query processing. Experimental results on various datasets indicate that twig query’s performance can be improved significantly by using F-Index.
How to process twig query quickly and correctly has attracted much attention in research society recently. Filtering query irrelevant elements before query execution is an important step for reducing elements scanned at query processing. As a flattened structural index, F-Index is proposed to filter out all query irrelevant index nodes, thus query irrelevant elements can be filtered out rapidly and mostly, especially when it is processing deeply nested XML documents with a complex structure. After filtering, a new efficient query algorithm based on the remaining elements is proposed to accelerate query processing. Experimental results on various datasets indicate that twig query’s performance can be improved significantly by using F-Index.
2007, 18(6):1443-1455.
Abstract:
It is an important problem to efficiently support similarity search for multi-dimensional data spaces in peer-to-peer (P2P) data management environment. Current unstructured P2P data sharing systems provide only a very rudimentary facility in query processing, i.e., matching-based query processing. This paper therefore presents a simple, yet effective index structure called EVARI (extended vector approximation routing index) to address the problem of multi-dimensional range search in unstructured P2P systems, by means of both data approximation and routing index techniques. With the aid of the EVARI, each peer can not only process range queries with its local dataset, but also route queries to promising peers with the desired data objects. In the proposed scheme, each peer summarizes its local content using space-partitioning technique, and exchanges the summarized information with neighboring peers to construct the EVARI. Furthermore, each peer can reconfigure its neighboring peers to keep the relevant peers nearby so as to optimize system resource configuration and improve system performance. Extensive experiments show the good performance of the proposed approach.
It is an important problem to efficiently support similarity search for multi-dimensional data spaces in peer-to-peer (P2P) data management environment. Current unstructured P2P data sharing systems provide only a very rudimentary facility in query processing, i.e., matching-based query processing. This paper therefore presents a simple, yet effective index structure called EVARI (extended vector approximation routing index) to address the problem of multi-dimensional range search in unstructured P2P systems, by means of both data approximation and routing index techniques. With the aid of the EVARI, each peer can not only process range queries with its local dataset, but also route queries to promising peers with the desired data objects. In the proposed scheme, each peer summarizes its local content using space-partitioning technique, and exchanges the summarized information with neighboring peers to construct the EVARI. Furthermore, each peer can reconfigure its neighboring peers to keep the relevant peers nearby so as to optimize system resource configuration and improve system performance. Extensive experiments show the good performance of the proposed approach.
2007, 18(6):1456-1467.
Abstract:
In this paper, according to the resource management problems brought by a large number of replicas, a multi-replica clustering management method based on limited-coding is proposed. In this method, according to the process of creating new replicas from existent single replica, replicas are partitioned into different hierarchies and clusters. Then replicas are coded and managed based on the user-defined limited-coding rule consisting of replica hierarchy and replica sequence, which can also dispose the alteration of clusters caused by dynamic adjustments on replicas (replica addition or replica removal) effectively. After that, a management model of centralization in local and peer to peer in wide area is adopted to organize replicas, and the cost of reconciling consistency can be greatly depressed combining with defined minimal-time of update propagation. The relevance between the coding rule and the number of replicas, and the solutions to replica failure and replica recover are discussed. The results of the performance evaluation show that the clustering method is an efficient way to manage a large number of replicas, achieving good scalability, not sensitive to moderate node failure, and adapting well to applications with frequent updates.
In this paper, according to the resource management problems brought by a large number of replicas, a multi-replica clustering management method based on limited-coding is proposed. In this method, according to the process of creating new replicas from existent single replica, replicas are partitioned into different hierarchies and clusters. Then replicas are coded and managed based on the user-defined limited-coding rule consisting of replica hierarchy and replica sequence, which can also dispose the alteration of clusters caused by dynamic adjustments on replicas (replica addition or replica removal) effectively. After that, a management model of centralization in local and peer to peer in wide area is adopted to organize replicas, and the cost of reconciling consistency can be greatly depressed combining with defined minimal-time of update propagation. The relevance between the coding rule and the number of replicas, and the solutions to replica failure and replica recover are discussed. The results of the performance evaluation show that the clustering method is an efficient way to manage a large number of replicas, achieving good scalability, not sensitive to moderate node failure, and adapting well to applications with frequent updates.
2007, 18(6):1468-1476.
Abstract:
After analyzing the temporal data characteristics and the effects on scheduling transaction, a real-time concurrency control protocol is proposed, which improves the performance of real-time systems by evaluating data-deadline and transactions execution time, improving transactions validation rules, and adjusting transactions committing order. Theoretical analysis and experimental results demonstrate that the new protocol reduces the transaction restarts numbers and the miss deadline percentage, and outperforms the previous ones.
After analyzing the temporal data characteristics and the effects on scheduling transaction, a real-time concurrency control protocol is proposed, which improves the performance of real-time systems by evaluating data-deadline and transactions execution time, improving transactions validation rules, and adjusting transactions committing order. Theoretical analysis and experimental results demonstrate that the new protocol reduces the transaction restarts numbers and the miss deadline percentage, and outperforms the previous ones.
2007, 18(6):1477-1490.
Abstract:
Vehicle ad-hoc network (VANET), as an application of mobile ad-hoc network and sensor network on road, has no an integrated protocol architecture, and has no special transmission control protocols available. In order to provide the reference for transmission protocol design of VANET, this paper investigates the goals and elements that the transmission protocol design should conform with. At first, this paper introduces the characteristics and applications of VANET, and the challenges of transmission control of VANET. Then the classification standards for wireless transmission protocol are presented. The advantages and disadvantages are discussed with analysis and comparison if various classes of wireless transmission control protocol are applied to VANET. Furthermore, according to the characteristics of VANET, the goals and elements of transmission control design of VANET are proposed. Finally, the research trends of transmission control of VANET are prospected.
Vehicle ad-hoc network (VANET), as an application of mobile ad-hoc network and sensor network on road, has no an integrated protocol architecture, and has no special transmission control protocols available. In order to provide the reference for transmission protocol design of VANET, this paper investigates the goals and elements that the transmission protocol design should conform with. At first, this paper introduces the characteristics and applications of VANET, and the challenges of transmission control of VANET. Then the classification standards for wireless transmission protocol are presented. The advantages and disadvantages are discussed with analysis and comparison if various classes of wireless transmission control protocol are applied to VANET. Furthermore, according to the characteristics of VANET, the goals and elements of transmission control design of VANET are proposed. Finally, the research trends of transmission control of VANET are prospected.
2007, 18(6):1491-1500.
Abstract:
The issue of QoS (quality of service) provisioning for adaptive multimedia in wireless communication networks is considered. A reinforcement learning based online adaptive bandwidth allocation optimization algorithm is proposed. First, an event-driven stochastic switching model is introduced to formulate the adaptive bandwidth allocation problem as a constrained continuous-time Markov decision problem. Then, an online optimization algorithm that combines policy gradient estimation by learning and stochastic approximation is derived. This algorithm can online handle the constrained optimization problem efficiently without explicit knowledge of the underlying system parameters. Moreover, this algorithm does not require the computation of performance potentials or other related quantities (e.g. Q-factors), which is necessary in previous schemes, and therefore saves computational cost significantly. Simulation results demonstrate the effectiveness of the proposed algorithm.
The issue of QoS (quality of service) provisioning for adaptive multimedia in wireless communication networks is considered. A reinforcement learning based online adaptive bandwidth allocation optimization algorithm is proposed. First, an event-driven stochastic switching model is introduced to formulate the adaptive bandwidth allocation problem as a constrained continuous-time Markov decision problem. Then, an online optimization algorithm that combines policy gradient estimation by learning and stochastic approximation is derived. This algorithm can online handle the constrained optimization problem efficiently without explicit knowledge of the underlying system parameters. Moreover, this algorithm does not require the computation of performance potentials or other related quantities (e.g. Q-factors), which is necessary in previous schemes, and therefore saves computational cost significantly. Simulation results demonstrate the effectiveness of the proposed algorithm.
2007, 18(6):1501-1509.
Abstract:
The security and flexibility are two goals that various improved BLP models attempt to achieve. How to enhance the flexibility of BLP model is a challenging problem that security researchers try to solve. However, the implementation of an insecure “security model” in the system will result in an insecure system. In this paper, two improved BLP models, for short DBLP (dynamic BLP) and SLCF (security label common framework), are analyzed. Although the designers of the two models claimed that their proposals can adjust the security level of the untrusted subject dynamically and accordingly improve the flexibility of the classical BLP model, the analytic results show that the two improved models are not secure at all. Under the rules of the two improved models a Trojan horse can “legally” read the high-level information and then write them to low-level objects, which violate the principle of multi-level security (MLS). This effort provides a theoretical foundation for avoiding the choice of insecure MLS model.
The security and flexibility are two goals that various improved BLP models attempt to achieve. How to enhance the flexibility of BLP model is a challenging problem that security researchers try to solve. However, the implementation of an insecure “security model” in the system will result in an insecure system. In this paper, two improved BLP models, for short DBLP (dynamic BLP) and SLCF (security label common framework), are analyzed. Although the designers of the two models claimed that their proposals can adjust the security level of the untrusted subject dynamically and accordingly improve the flexibility of the classical BLP model, the analytic results show that the two improved models are not secure at all. Under the rules of the two improved models a Trojan horse can “legally” read the high-level information and then write them to low-level objects, which violate the principle of multi-level security (MLS). This effort provides a theoretical foundation for avoiding the choice of insecure MLS model.
2007, 18(6):1510-1521.
Abstract:
With the in-depth researches of large scale distributed systems, such as Grid computing, Ubiquitous computing, P2P computing, Ad hoc networks, etc, system is a dynamic and cooperative model made up of multi-software serving. Under these dynamic and uncertainty environments, trust mechanism based on CA (certificate authority) in a regular PKI (pubic key infrastructure) can’t adapt to these requirements. Dynamic trust mechanism is a new and hot topic of security research for these new distributed applications. In this paper, firstly, the concepts, problems, and research approaches of dynamic trust relationship are summarized and presented. Secondly, several typical dynamic trust model systems including their mathematical methods are described in detail. And then, this paper presents the results of comparative evaluation of these models under a selection of scenarios. Finally, the current problems and the challenges of this field for future research are presented. The research work indicates that the dynamic nature of trust creates the biggest challenge in measuring trust and predicting trustworthiness. So the future work will focus on the theoretical research of dynamic trust relationships to present a solid theoretical foundation for the practical applications.
With the in-depth researches of large scale distributed systems, such as Grid computing, Ubiquitous computing, P2P computing, Ad hoc networks, etc, system is a dynamic and cooperative model made up of multi-software serving. Under these dynamic and uncertainty environments, trust mechanism based on CA (certificate authority) in a regular PKI (pubic key infrastructure) can’t adapt to these requirements. Dynamic trust mechanism is a new and hot topic of security research for these new distributed applications. In this paper, firstly, the concepts, problems, and research approaches of dynamic trust relationship are summarized and presented. Secondly, several typical dynamic trust model systems including their mathematical methods are described in detail. And then, this paper presents the results of comparative evaluation of these models under a selection of scenarios. Finally, the current problems and the challenges of this field for future research are presented. The research work indicates that the dynamic nature of trust creates the biggest challenge in measuring trust and predicting trustworthiness. So the future work will focus on the theoretical research of dynamic trust relationships to present a solid theoretical foundation for the practical applications.
2007, 18(6):1522-1530.
Abstract:
The primary goal of the Transport Layer Security (TLS) protocol is to provide confidentiality and data integrity between two communicating entities. Since the most computationally expensive step in the TLS handshake protocol is the server's RSA decryption, it is introduced that optimal batch RSA can be used to speedup TLS session initialization. This paper first indicates that the previous batch method is impractical since it requires a multiple of certificates, then it proposes the unique certificate scheme to overcome the problem. It is also introduced that the batching parameter is optimized when integrating users' requirements for Internet Quality of Service (QoS). To select the optimal batching parameters, not only the server's performance but also the client's tolerable waiting time is considered. Based on the analysis of the mean queue time, batching service time and the stability of the system, a novel batch optimal scheduling algorithm which is deployed in a batching Web server is proposed. Finally, the proposed algorithm is evaluated to be practical and efficient through both analysis and simulation studies.
The primary goal of the Transport Layer Security (TLS) protocol is to provide confidentiality and data integrity between two communicating entities. Since the most computationally expensive step in the TLS handshake protocol is the server's RSA decryption, it is introduced that optimal batch RSA can be used to speedup TLS session initialization. This paper first indicates that the previous batch method is impractical since it requires a multiple of certificates, then it proposes the unique certificate scheme to overcome the problem. It is also introduced that the batching parameter is optimized when integrating users' requirements for Internet Quality of Service (QoS). To select the optimal batching parameters, not only the server's performance but also the client's tolerable waiting time is considered. Based on the analysis of the mean queue time, batching service time and the stability of the system, a novel batch optimal scheduling algorithm which is deployed in a batching Web server is proposed. Finally, the proposed algorithm is evaluated to be practical and efficient through both analysis and simulation studies.
2007, 18(6):1531-1542.
Abstract:
This paper presents a new pipeline for rendering depth images entirely on GPU (graphics processing unit). The implementation exploits inherent parallelism of GPU to speed up the rendering of depth images. By the scheme, a novel forward 3D warping method is proposed for vertex shader to obtain high rendering performance. Furthermore, the hardware pipeline’s rasterization function is utilized to conduct the image re-sampling efficiently to generate holes free rendering results. Per pixel lighting effect is implemented in pixel shader to get high image quality. The rendering shows rapid performance at full screen resolution, with correct self-occlusions and accurate silhouettes. Moreover, a real-time walkthrough system is implemented for the objects based on cylindrical depth image rendered by view-dependent dynamic LOD (level of detail) representation at runtime.
This paper presents a new pipeline for rendering depth images entirely on GPU (graphics processing unit). The implementation exploits inherent parallelism of GPU to speed up the rendering of depth images. By the scheme, a novel forward 3D warping method is proposed for vertex shader to obtain high rendering performance. Furthermore, the hardware pipeline’s rasterization function is utilized to conduct the image re-sampling efficiently to generate holes free rendering results. Per pixel lighting effect is implemented in pixel shader to get high image quality. The rendering shows rapid performance at full screen resolution, with correct self-occlusions and accurate silhouettes. Moreover, a real-time walkthrough system is implemented for the objects based on cylindrical depth image rendered by view-dependent dynamic LOD (level of detail) representation at runtime.
2007, 18(6):1543-1552.
Abstract:
This paper presents a geodesic-based constrained deformation method for polygonal mesh models. After a user specifies a series of constraints (which may consist of points, lines and faces), their effective radii, maximum displacements, scaling, and rotation angles, the method creates the deformation weights for the vertices of the mesh surfaces using the field values determined by the geodesic distances between the vertices and the constraint sources. Compared with the traditional constrained deformation model based on Euclidean distance, this method can avoid the undesired deformation on the regions near the constraints. Experimental results show that the new deformation model is both efficient and intuitive.
This paper presents a geodesic-based constrained deformation method for polygonal mesh models. After a user specifies a series of constraints (which may consist of points, lines and faces), their effective radii, maximum displacements, scaling, and rotation angles, the method creates the deformation weights for the vertices of the mesh surfaces using the field values determined by the geodesic distances between the vertices and the constraint sources. Compared with the traditional constrained deformation model based on Euclidean distance, this method can avoid the undesired deformation on the regions near the constraints. Experimental results show that the new deformation model is both efficient and intuitive.
联系方式
- 《Journal of Software 》
- 主办单位：Institute of Software, CAS, China
- 邮编：100190
- 电话：010-62562563
- 电子邮箱：jos@iscas.ac.cn
- 网址：https://www.jos.org.cn
- 刊号：ISSN 1000-9825
- CN 11-2560/TP
- 国内定价：70元
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
