Volume 19,Issue 1,2008 Table of Contents
2008, 19(1):1-8.
Abstract:
Since the first quantum programming language came about in 1996, many scientists and researchers are interested and involved in this field. After talking about several representative quantum programming languages, this paper gives an overview of the quantum programming language NDQJava designed by the authors, including design criteria, language paradigm, hardware platform, basic components and examples. Besides, the related works have also been mentioned.
Since the first quantum programming language came about in 1996, many scientists and researchers are interested and involved in this field. After talking about several representative quantum programming languages, this paper gives an overview of the quantum programming language NDQJava designed by the authors, including design criteria, language paradigm, hardware platform, basic components and examples. Besides, the related works have also been mentioned.
2008, 19(1):9-16.
Abstract:
This paper describes one of the processing systems for the quantum programming language NDQJava. Its main feature lies that the classical parts of NDQJava programs are processed by the Java processing system, so this effort emphasizes on the processing of program's quantum parts. This processing system follows the compilation-interpretation approach, and it includes lexical analyzer, syntactic analyzer, code transformer, quantum assembler and quantum interpreter. By the end of this paper, some examples are given. The system was implemented by simulation in June 2006 on the classical computer.
This paper describes one of the processing systems for the quantum programming language NDQJava. Its main feature lies that the classical parts of NDQJava programs are processed by the Java processing system, so this effort emphasizes on the processing of program's quantum parts. This processing system follows the compilation-interpretation approach, and it includes lexical analyzer, syntactic analyzer, code transformer, quantum assembler and quantum interpreter. By the end of this paper, some examples are given. The system was implemented by simulation in June 2006 on the classical computer.
2008, 19(1):17-26.
Abstract:
The abstract interpretation theory was proposed by P. Cousot and R. Cousot in 1977, and is widely used in the program’s static analysis domain to construct and approximate the program’s fixpoint semantics. This paper describes the abstract interpretation framework of the program semantics based on the Galois connection, and then discusses three typical applications of the abstract interpretation theory: The program transformation, the program verification techniques about the safety property and the program verification techniques about the liveness property. Finally, it points out the main directions of the program verification techniques based on the abstract interpretation theory.
The abstract interpretation theory was proposed by P. Cousot and R. Cousot in 1977, and is widely used in the program’s static analysis domain to construct and approximate the program’s fixpoint semantics. This paper describes the abstract interpretation framework of the program semantics based on the Galois connection, and then discusses three typical applications of the abstract interpretation theory: The program transformation, the program verification techniques about the safety property and the program verification techniques about the liveness property. Finally, it points out the main directions of the program verification techniques based on the abstract interpretation theory.
2008, 19(1):27-38.
Abstract:
With the growing increase in software/hardware system scale and function, the further development and application of model checking has been greatly limited by state space explosion, which becomes the bottleneck of verifying large industrial designs. Predicate abstraction, as one of the most effective ways to address state explosion, has been fueled over the recent years. This paper presents a survey of the latest developments in predicate abstraction. A basic algorithm for predicate abstraction is introduced first, followed by comparison among several solvers. Emphases are put on counterexample-guided abstraction refinement and interpolation-based abstraction refinement, including the principles and improvements. The qualities of the new predicate generation methods are also analyzed. Finally, the major challenges in making this technology more pervasive in industrial design verification domain are noted.
With the growing increase in software/hardware system scale and function, the further development and application of model checking has been greatly limited by state space explosion, which becomes the bottleneck of verifying large industrial designs. Predicate abstraction, as one of the most effective ways to address state explosion, has been fueled over the recent years. This paper presents a survey of the latest developments in predicate abstraction. A basic algorithm for predicate abstraction is introduced first, followed by comparison among several solvers. Emphases are put on counterexample-guided abstraction refinement and interpolation-based abstraction refinement, including the principles and improvements. The qualities of the new predicate generation methods are also analyzed. Finally, the major challenges in making this technology more pervasive in industrial design verification domain are noted.
2008, 19(1):39-47.
Abstract:
This paper presents a framework combining variable abstraction with bounded model checking, in order to prove the counterexamples' absence or establish the counterexamples' existence. A mathematical definition of variable minimal unsatisfiability (VMU) is introduced to drive this abstraction refinement process. The set of variables of VMU formula is a minimal one guaranteeing its unsatisfiability. Furthermore, the authors prove that VMU-driven refinement is valid and minimal by mathematical reasoning. Although the determining problem of VMU is as hard as the well-known problem called minimal unsatisfiability (MU), i.e. DP-complete, the case study has shown that VMU could be more effective than MU in variable abstraction refinement process.
This paper presents a framework combining variable abstraction with bounded model checking, in order to prove the counterexamples' absence or establish the counterexamples' existence. A mathematical definition of variable minimal unsatisfiability (VMU) is introduced to drive this abstraction refinement process. The set of variables of VMU formula is a minimal one guaranteeing its unsatisfiability. Furthermore, the authors prove that VMU-driven refinement is valid and minimal by mathematical reasoning. Although the determining problem of VMU is as hard as the well-known problem called minimal unsatisfiability (MU), i.e. DP-complete, the case study has shown that VMU could be more effective than MU in variable abstraction refinement process.
2008, 19(1):48-61.
Abstract:
The research actuality and new progress in clustering algorithm in recent years are summarized in this paper. First, the analysis and induction of some representative clustering algorithms have been made from several aspects, such as the ideas of algorithm, key technology, advantage and disadvantage. On the other hand, several typical clustering algorithms and known data sets are selected, simulation experiments are implemented from both sides of accuracy and running efficiency, and clustering condition of one algorithm with different data sets is analyzed by comparing with the same clustering of the data set under different algorithms. Finally, the research hotspot, difficulty, shortage of the data clustering and some pending problems are addressed by the integration of the aforementioned two aspects information. The above work can give a valuable reference for data clustering and data mining.
The research actuality and new progress in clustering algorithm in recent years are summarized in this paper. First, the analysis and induction of some representative clustering algorithms have been made from several aspects, such as the ideas of algorithm, key technology, advantage and disadvantage. On the other hand, several typical clustering algorithms and known data sets are selected, simulation experiments are implemented from both sides of accuracy and running efficiency, and clustering condition of one algorithm with different data sets is analyzed by comparing with the same clustering of the data set under different algorithms. Finally, the research hotspot, difficulty, shortage of the data clustering and some pending problems are addressed by the integration of the aforementioned two aspects information. The above work can give a valuable reference for data clustering and data mining.
2008, 19(1):62-72.
Abstract:
A fundamental and difficult problem in cluster analysis is the determination of the "true" number of clusters in a dataset. The common trail-and-error method generally depends on certain clustering algorithms and is inefficient when processing large datasets. In this paper, a hierarchical method is proposed to get rid of repeatedly clustering on large datasets. The method firstly obtains the CF (clustering feature) via scanning the dataset and agglomerative generates the hierarchical partitions of dataset, then a curve of the clustering quality w.r.t the varying partitions is incrementally constructed. The partitions corresponding to the extremum of the curve is used to estimate the number of clusters finally. A new validity index is also presented to quantify the clustering quality, which is independent of clustering algorithm and emphasis on the geometric features of clusters, handling efficiently the noisy data and arbitrary shaped clusters. Experimental results on both real world and synthesis datasets demonstrate that the new method outperforms the recently published approaches, while the efficiency is significantly improved.
A fundamental and difficult problem in cluster analysis is the determination of the "true" number of clusters in a dataset. The common trail-and-error method generally depends on certain clustering algorithms and is inefficient when processing large datasets. In this paper, a hierarchical method is proposed to get rid of repeatedly clustering on large datasets. The method firstly obtains the CF (clustering feature) via scanning the dataset and agglomerative generates the hierarchical partitions of dataset, then a curve of the clustering quality w.r.t the varying partitions is incrementally constructed. The partitions corresponding to the extremum of the curve is used to estimate the number of clusters finally. A new validity index is also presented to quantify the clustering quality, which is independent of clustering algorithm and emphasis on the geometric features of clusters, handling efficiently the noisy data and arbitrary shaped clusters. Experimental results on both real world and synthesis datasets demonstrate that the new method outperforms the recently published approaches, while the efficiency is significantly improved.
2008, 19(1):73-81.
Abstract:
Existing relational learning approaches usually work on complete relational data. However, in real-world applications, data are often incomplete. This paper proposes the MLTEC (maximum likelihood tree and evolutionary computing method) method to learn structures of the probabilistic relational models (PRMs) from incomplete relational data. The incomplete relational data are filled randomly at first, and a maximum likelihood tree (MLT) is generated from each completed data sample. This population of MLTs is then evolved through an evolutionary computing process, and the incomplete data are modified by using the best evolved structure in each generation. As a result, the probabilistic structure is learned. Experimental results show that the MLTEC method can learn good structures from incomplete relational data.
Existing relational learning approaches usually work on complete relational data. However, in real-world applications, data are often incomplete. This paper proposes the MLTEC (maximum likelihood tree and evolutionary computing method) method to learn structures of the probabilistic relational models (PRMs) from incomplete relational data. The incomplete relational data are filled randomly at first, and a maximum likelihood tree (MLT) is generated from each completed data sample. This population of MLTs is then evolved through an evolutionary computing process, and the incomplete data are modified by using the best evolved structure in each generation. As a result, the probabilistic structure is learned. Experimental results show that the MLTEC method can learn good structures from incomplete relational data.
2008, 19(1):82-89.
Abstract:
One of the most important issues in Text Categorization (TC) is Feature Selection (FS). Many FS methods have been put forward and widely used in TC field, such as Information Gain (IG), Document Frequency (DF) thresholding, Mutual Information (MI) and so on. Empirical studies show that IG is one of the most effective methods, DF performs similarly, in contrast, and MI had relatively poor performance. One basic research question is why these FS methods cause different performance. Many existing work answers this question based on empirical studies. This paper presents a formal study of FS based on category resolve power. First, two desirable constraints that any reasonable FS function should satisfy are defined, then a universal method for developing FS functions is presented, and a new FS function KG using this method is developed. Analysis shows that IG and KG (knowledge gain) satisfy this universal method. Experiments on Reuters-21578 collection, NewsGroup collection and OHSUMED collection show that KG and IG get the best performance, even KG performs better than the IG method in two collections. These experiments imply that the universal method is very effective and gives a formal evaluation criterion for FS method.
One of the most important issues in Text Categorization (TC) is Feature Selection (FS). Many FS methods have been put forward and widely used in TC field, such as Information Gain (IG), Document Frequency (DF) thresholding, Mutual Information (MI) and so on. Empirical studies show that IG is one of the most effective methods, DF performs similarly, in contrast, and MI had relatively poor performance. One basic research question is why these FS methods cause different performance. Many existing work answers this question based on empirical studies. This paper presents a formal study of FS based on category resolve power. First, two desirable constraints that any reasonable FS function should satisfy are defined, then a universal method for developing FS functions is presented, and a new FS function KG using this method is developed. Analysis shows that IG and KG (knowledge gain) satisfy this universal method. Experiments on Reuters-21578 collection, NewsGroup collection and OHSUMED collection show that KG and IG get the best performance, even KG performs better than the IG method in two collections. These experiments imply that the universal method is very effective and gives a formal evaluation criterion for FS method.
2008, 19(1):90-102.
Abstract:
Recently, the QoS architecture in the beyond 3rd generation mobile communication system is becoming a hot topic in the area of computer networks and telecommunications. In this paper, the state-of-the-art QoS architectures are presented. By analyzing and comparing the key projects and papers published abroad, it is concluded that QoS architecture in B3G (beyond 3rd generation) system should be an all-IP, hierarchical and end-to-end framework. The main characteristics include scalability, controllable, self-adaptation and dynamic resource management. Finally, the design principals are proposed, and future works are summarized as well.
Recently, the QoS architecture in the beyond 3rd generation mobile communication system is becoming a hot topic in the area of computer networks and telecommunications. In this paper, the state-of-the-art QoS architectures are presented. By analyzing and comparing the key projects and papers published abroad, it is concluded that QoS architecture in B3G (beyond 3rd generation) system should be an all-IP, hierarchical and end-to-end framework. The main characteristics include scalability, controllable, self-adaptation and dynamic resource management. Finally, the design principals are proposed, and future works are summarized as well.
2008, 19(1):103-115.
Abstract:
Information brokerage in wireless sensor networks involves producers (such as sensor nodes) storing in storage positions a large amount of data that they have collected and consumers (e.g. base stations, users, and nodes) retrieving that information. In this paper, first, the data storage problem is formalized into a one-to-one (one producer and one consumer) model, a many-to-one (m producers and one consumer) model, and a many-to-many (m producers and n consumers) model with the goal of minimizing the total energy consumption. Second, based on the above models, two algorithms are proposed to determine the storage positions based on data rates of producers, query rates of consumers, and transmission scheme of information brokerage. The optimal data storage (ODS) scheme, a greedy algorithm, produces the global optimal data storage positions and the near-optimal data storage (NDS) scheme, an approximate algorithm, can greatly reduce the computational overhead while achieving local optimal positions. Both ODS and NDS are able to adjust the storage positions adaptively to minimize energy consumption that includes the costs of storing and querying the data. Simulation results show that NDS not only provides substantial cost benefits but also performs as effective and efficient as ODS in over 70% of the tested cases.
Information brokerage in wireless sensor networks involves producers (such as sensor nodes) storing in storage positions a large amount of data that they have collected and consumers (e.g. base stations, users, and nodes) retrieving that information. In this paper, first, the data storage problem is formalized into a one-to-one (one producer and one consumer) model, a many-to-one (m producers and one consumer) model, and a many-to-many (m producers and n consumers) model with the goal of minimizing the total energy consumption. Second, based on the above models, two algorithms are proposed to determine the storage positions based on data rates of producers, query rates of consumers, and transmission scheme of information brokerage. The optimal data storage (ODS) scheme, a greedy algorithm, produces the global optimal data storage positions and the near-optimal data storage (NDS) scheme, an approximate algorithm, can greatly reduce the computational overhead while achieving local optimal positions. Both ODS and NDS are able to adjust the storage positions adaptively to minimize energy consumption that includes the costs of storing and querying the data. Simulation results show that NDS not only provides substantial cost benefits but also performs as effective and efficient as ODS in over 70% of the tested cases.
2008, 19(1):116-124.
Abstract:
In wireless mesh networks, the sample space of evidence may be not integrative or reliable because of the change of network topology and the occurrence of wireless collision. It makes the existing trust evaluation models inapplicable. To evaluate trust values of nodes and establish trust relationship in nodes, a trust model is proposed on the basis of the analyses of the existing trust models and the minimal principle of uncertainty metric. The model reduces the influence of the non-integrated and unreliable sample space through importing a credible parameter. According to the real situation of networks, the model can minimize the amendment of evaluation values in the whole scope. Contrasted with the evidence-based trust model, the simulation results show that the proposed model is effective.
In wireless mesh networks, the sample space of evidence may be not integrative or reliable because of the change of network topology and the occurrence of wireless collision. It makes the existing trust evaluation models inapplicable. To evaluate trust values of nodes and establish trust relationship in nodes, a trust model is proposed on the basis of the analyses of the existing trust models and the minimal principle of uncertainty metric. The model reduces the influence of the non-integrated and unreliable sample space through importing a credible parameter. According to the real situation of networks, the model can minimize the amendment of evaluation values in the whole scope. Contrasted with the evidence-based trust model, the simulation results show that the proposed model is effective.
2008, 19(1):125-135.
Abstract:
This paper presents a Cooperant Congestion Control Protocol (C3P) that uses 1 bit routers' explicit feedback predicted information and delay signals to adjust the congestion windows appropriately. Simulation results show that C3P can efficiently improve the bandwidth utilization, TCP (transmission control protocol)-friendliness, RTT (round trip time) fairness and reduce the packet drop rate in High Bandwidth-Delay Product Networks.
This paper presents a Cooperant Congestion Control Protocol (C3P) that uses 1 bit routers' explicit feedback predicted information and delay signals to adjust the congestion windows appropriately. Simulation results show that C3P can efficiently improve the bandwidth utilization, TCP (transmission control protocol)-friendliness, RTT (round trip time) fairness and reduce the packet drop rate in High Bandwidth-Delay Product Networks.
2008, 19(1):136-143.
Abstract:
It is difficult to evaluate the document collection partition in distributed information retrieval. Recently, there is no clear evaluation criterion for the document collection partition problem. In this paper, two partition models are built to formulate the document collection partition problem from the essence of the problem itself and they can be used as the evaluation criterion of the document collection partition problem. A Huffman_encoding_like algorithm is introduced to compute the optimum partition solution given a test query set. The optimum partition solution is a good reference of other partition solution. The experimental results show that the two models are effective document collection partition evaluation criteria.
It is difficult to evaluate the document collection partition in distributed information retrieval. Recently, there is no clear evaluation criterion for the document collection partition problem. In this paper, two partition models are built to formulate the document collection partition problem from the essence of the problem itself and they can be used as the evaluation criterion of the document collection partition problem. A Huffman_encoding_like algorithm is introduced to compute the optimum partition solution given a test query set. The optimum partition solution is a good reference of other partition solution. The experimental results show that the two models are effective document collection partition evaluation criteria.
2008, 19(1):144-155.
Abstract:
A practical pricing mechanism is the foundation for the deploying of IP multicast in the inter-domain Internet. The IP multicast service model and its pricing mechanism are discussed in this paper, by considering the motivations of different partners in the process. Three models are proposed for all applications in the real environments. They are ICP-USER model, ICP-ISP model and ICP-ISP-USER model. In every model, the applied scenarios, resolving method and the complexity of algorithm are described. Here, the Internet is considered as an ecosystem. So the work embodies the self-organization property of the Internet based on the game theory, and respects every role's right and benefit, which is good at the health and stable development of the Internet. So it has great practical feature.
A practical pricing mechanism is the foundation for the deploying of IP multicast in the inter-domain Internet. The IP multicast service model and its pricing mechanism are discussed in this paper, by considering the motivations of different partners in the process. Three models are proposed for all applications in the real environments. They are ICP-USER model, ICP-ISP model and ICP-ISP-USER model. In every model, the applied scenarios, resolving method and the complexity of algorithm are described. Here, the Internet is considered as an ecosystem. So the work embodies the self-organization property of the Internet based on the game theory, and respects every role's right and benefit, which is good at the health and stable development of the Internet. So it has great practical feature.
2008, 19(1):156-166.
Abstract:
This paper proposes a scheduling algorithm, RTCLA (real-time cross-layer scheduling algorithm for real-time application), at MAC layer for real-time applications traversing heterogeneous networks including wired and wireless links. RTCLA is a cross-layer algorithm, combined with adaptive modulation and coding (AMC) and selective repeat-automatic repeat request (SR-ARQ). It is designed to improve spectrum utilization when satisfying packet error rate (PER) and delay requirements. Simulations are employed to evaluate the performance of RTCLA in three metrics including system packets time-out rate, average system effective throughput and fairness and it is compared with the modified proportional fair (MPF), the earliest deadline first (EDF) and the modified largest weighted delay first (M-LWDF) algorithms. Simulation results show that RTCLA outperforms MPF, EDF and M-LWDF algorithms in terms of the strict delay requirements of real-time applications, scarcity of spectrum and the time-varying channels, especially in the performance of packet time-out rate. Furthermore, the simulation results show that RTCLA performs the same as other three algorithms in stability.
This paper proposes a scheduling algorithm, RTCLA (real-time cross-layer scheduling algorithm for real-time application), at MAC layer for real-time applications traversing heterogeneous networks including wired and wireless links. RTCLA is a cross-layer algorithm, combined with adaptive modulation and coding (AMC) and selective repeat-automatic repeat request (SR-ARQ). It is designed to improve spectrum utilization when satisfying packet error rate (PER) and delay requirements. Simulations are employed to evaluate the performance of RTCLA in three metrics including system packets time-out rate, average system effective throughput and fairness and it is compared with the modified proportional fair (MPF), the earliest deadline first (EDF) and the modified largest weighted delay first (M-LWDF) algorithms. Simulation results show that RTCLA outperforms MPF, EDF and M-LWDF algorithms in terms of the strict delay requirements of real-time applications, scarcity of spectrum and the time-varying channels, especially in the performance of packet time-out rate. Furthermore, the simulation results show that RTCLA performs the same as other three algorithms in stability.
2008, 19(1):167-176.
Abstract:
BGP (border gateway protocol) security is very important to the inter-domain routing security. Many solutions have been proposed, but none has been deployed until now. This paper analyzes the main problems of these approaches. It studies the AS (autonomous system) topology of the Internet, especially the rich-club property, and gives the notion of the AS alliance. It proposes SE-BGP (security enhanced BGP) as a new way for BGP security. An alliance-based security architecture, and a new trust model-TTM (translator trust model) for SE-BGP are constituted. An authentication scheme based on TTM is also designed. Furthermore, the way of how to extend the BGP protocol is considered. The SE-BGP has strong ability of security and good scalability, and the number of the used certificates is about 1% of the traditional solutions.
BGP (border gateway protocol) security is very important to the inter-domain routing security. Many solutions have been proposed, but none has been deployed until now. This paper analyzes the main problems of these approaches. It studies the AS (autonomous system) topology of the Internet, especially the rich-club property, and gives the notion of the AS alliance. It proposes SE-BGP (security enhanced BGP) as a new way for BGP security. An alliance-based security architecture, and a new trust model-TTM (translator trust model) for SE-BGP are constituted. An authentication scheme based on TTM is also designed. Furthermore, the way of how to extend the BGP protocol is considered. The SE-BGP has strong ability of security and good scalability, and the number of the used certificates is about 1% of the traditional solutions.
联系方式
- 《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.
