Abstract:Circuit partitioning is an important part of any very large scale integration (VLSI) physical design automation, but it is a NP-hard combinatorial optimization problem. In this paper, a hybrid particle swarm optimization algorithm with FM strategy is proposed to approch this problem. Inspired by the mechinism of genetic algorithm (GA), two-point crossover and random two-point exchange mutation operators have been designed to avoid generating infeasible solutions. To improve the ability of local exploration, FM strategy is applied to the proposed algorithm to update its position. A mutation strategy is also built into the proposed algorithm to achieve better diversity and break away from local optima. Experiments on ISCAS89 benchmark circuits show that the proposed algorithm is efficient.

Abstract:Based on the caving degree method, this paper proposes a heuristic approach to solve the cuboid packing problem by incorporating the cuboid arrangement strategy. Experiments on 15 classic LN benchmark instances, performed by Loh and Nee in 1992, have shown that this approach has the potential of performing very well. In the difficult instance of LN2, it achieved a volume utilization of 98.2%, which is an improvement from the current best record by 1.6%. In another difficult instance of LN6, it achieved a volume utilization of 96.2%, which matches that of the current best record. For each of the other 13 instances, it maintains optimal layout that packs all cuboid items into the container, matching current best record. As a whole, the average volume utilization on the 15 LN instances is 70.96%.

Abstract:This paper presents a Trustworthy Services Selection Based on Preference Recommendation (TSSPR) method that assists users in selecting the right Web services, according to their own preferences. First, a group of recommenders that have similar preferences are found, and then the similarity rating is computed by using the Pearson correlation method. Second, filtering services based on the user’s recommending level, relative domain degrees, and similarity ratings can improve the quality of recommendations. Experimental results show that given an appropriate setting, this method can effectively solve the weaknesses of recommendation systems, such as sparseness, cold starts, and inaccurate recommendations.

Abstract:This paper proposes a framework for the specification of open environment properties. This framework enables convenient and formal specification of properties of asynchronous environments, including temporal properties which cannot be handled in the existing work. This framework also supports implementation of effective schemes for monitoring environment properties based on distributed predicate detection. A middleware infrastructure is designed and implemented, which supports efficient monitoring of environment properties for building high-confidence systems in open environments. This paper also evaluates design of the proposed infrastructure with a case study.

Abstract:This paper presents an overview of a quantum programming language NDQJava-2. NDQJava-2 is an extension of NDQJava with additional quantum components such as quantum conditional statement, quantum loop statement, quantum subprogram, quantum module, and quantum exception handling mechanism. The added commponents make NDQJava-2 a structured quantum programming language. Experience in writing quantum programs indicates that compared with NDQJava, NDQJava-2 is a more practical, more readable and more suitable (components setting) quantum programming language.

Abstract:Different from previous works such as hand-crafted patterns and rule based methods, this paper proposes a novel method that uses syntactic paths to automatically recognize the appraisal expressions. In detail, the syntactic paths are first automatically collected to describe the relationships between the polarity words and their corresponding targets. Next, an edit distance based syntactic path matching strategy is used to improve the performance of the exact syntactic path matching method. Experimental results on the camera and MP3 player domains show that (1) syntactic paths are helpful for appraisal expression recognition, and (2) edit distance based syntactic path matching method can further improve the performance of appraisal expression recognition.

Abstract:Fitness Distance Correlation (FDC) can hardly predict the evolution difficulty of Gene Expression Programming (GEP) because problems with different hardness would result in very similar FDC values in GEP. To solve the problem, the authors propose a posture model and region density to predict GEP’s evolution difficulty. This study made the following contributions: (1) It introduces the concepts of the chromosomes’ distance and posture model in GEP; (2) It proposes region density of a posture model; (3) It proves that the posture model is a mapping from the original searching space, and the mapping preserves the population’s dynamic migration property in the original searching space; (4) It demonstrates the validity of using posture model and region density to predict GEP’s evolution difficulty; (5) It conducts extensive experiments to show that the new model can precisely predict the evolution difficulty of GEP.

Abstract:This paper proposes an ordering relation named Admissible Subgoal Ordering (ASO). The definition of ASO is formalized, and its relative importance for incremental planning is discussed. Then, this paper introduces the notion of dependency relations over facts, and develops fact dependency graph technique that can approximate admissible ordering relations in polynomial time. Finally, an algorithm to compute subgoals sequence with admissible orderings is presented. All the ideas presented in the paper are implemented in the planning system ASOP, and the effectiveness of the techniques is demonstrated on the benchmarks of International Planning Competitions (IPC). The results show that these techniques can efficiently solve large planning problems and lead to a greater improvement in planning performance.

Abstract:Some variables in a constraint-based configuration model may not have any immediate or indirect relationship between them; therefore, these variables will never intervene with each other in a constraint propagation. According to this characteristic of configuration, this paper proposes a preprocessing approach based on equivalent class partition, which can be used in the process of building the product model, so that the original configuration problem can be effectively divided into several sub-problems, and these sub-problems can be solved independently. The two backtracking-strategies are used in testing this method. The experimental results show that this method can effectively improve searching efficiency. Moreover, the method is integrated with the QUICKXPLAIN algorithm to compute conflict explanations, and the result show that it can also improve the efficiency of the algorithm.

Abstract:First, this paper establishes an effective partition relationship in the finite integer set and an effective splitting relationship in the coalition set, and devises an EOCS (effective optimal coalition structure) algorithm, which only evaluates bipartite effective splittings of coalition to find the optimal value from bottom to top, so it decreases the number of bipartite splitting. Secondly, the correctness of the EOCS algorithm is proved based on the Kleene closure function. Moreover, this paper proves that the EOCS lower bound is Ω(2.818ⁿ) by the integration limit theorem, and discovers that the EOCS upper bound is O(2.983ⁿ) by the time serial analysis technique. Finally, this paper compares the EOCS algorithm with other algorithms to point out that the EOCS algorithm can find optimal coalition structure in O(2.983ⁿ) time whether the coalition values meet which probability distributions or not. The DP (dynamic programming) algorithm and the IDP (improved dynamic programming) algorithm proposed by Rothkopf and Rahwan can find an optimal solution in O(3ⁿ). The EOCS algorithm’s design, correctness proof, and time complexity analysis are all improvements of Rothkopf and Rahwan’s related work.

Abstract:This paper proposes a density-based network clustering algorithm, TRAVEL. The algorithm produces a traveling order containing clustering with various densities and finds the optimal clusters in it. The traveling order is subsequently transformed into a data structure of contiguous subinterval heap based on which a clustering algorithm, HCLU, is designed to find the hierarchical cluster boundaries of the network without any user interaction. Experimental results on real-world and computer-generated synthetic networks show that the clustering accuracy of the proposed algorithms is higher than the baseline methods. Furthermore, they are able to produce robust hierarchical communities in various networks with low redundancy in the presence of noise.

Abstract:In this paper, Intent Waned Values and Compact Dependency are proposed as new concepts. It has strictly been proven that a dependent foundation that consisted of compact dependencies is an irredundant and complete dependency basis on an axiom system that includes only one rule: attributes are increased at the left side and reduced at the right side. In this way, another irredundant and complete dependency basis is found, which is distinguished from the Guigues-Duquenne basis. This basis changes the traditional idea that there exists a sole irredundant and complete dependency basis and discloses the prospect of finding multiple kinds of irredundant and complete dependency basis for a variety of requirements.

Abstract:This paper introduces an idea that solves the synchronization problem in the process of application-level multicast routing without using the dedicated synchronizing controller. Furthermore, the low-delay multicast communication is achieved on base of an idea. The contributions of this paper include: (1) The process of multipoint synchronizing interaction is modeled, and the theorem of application-level multicast routing algorithms supporting multipoint interaction synchronization is proved; (2) An effective low-delay multicast routing algorithm that supports multipoint interaction synchronization is proposed; (3) Performance analysis of this algorithm and the existing similar algorithm is carried out by mathematic methods. Both simulation experiments and practical applications demonstrate that the algorithm is correct and effective.

Abstract:Through a joint study in architecture and application, it is found that lock synchronization in a fine-grained parallel betweenness centrality (BC) program poses an obstacle for the efficient execution of parallel architectures. This paper proposes a data-centric parallel algorithm that eliminates lock synchronization. This algorithm reduces execution time and improves speeds up twice as fast on both AMD 32 core SMP and Intel 8core SMP.

Abstract:In order to analyze intrusion evidences automatically, a layered method for reconstructing intrusion scenario is proposed. It includes 3 main phrases. First, the intruder’s abstract steps and the relationships between them are reconstructed by the alert correlation. Secondly, detailed behaviors of each step are reconstructed based on attack signatures and the OS-Level dependency tracking. Finally, the results are mapped and refined, and a behavior graph is generated. This graph can describe the completed intrusion process. The experiments on DARPA 2000 prove that the results are not only easy to understand, but are also full and accurate. Hence, it is fit to be presented in the court. Compared with current methods, this method shows more advantages. For example, it can process more complex scenarios.

Abstract:This paper provides a detailed analysis on the threats of topology-exposure in Mobile Ad Hoc Network (MANET) and proposes a secure topology-hiding multipath routing protocol based on the analysis. In Route Discovery, the new protocol exposes no routing information in packets to hide the network topology and adopts a node-excluded mechanism to find multiple paths. During this process, this protocol implements on-demand Neighbor Discovery to verify node identities. In Route Maintenance, a fault detection mechanism is designed to provide assurance that the selected paths are available and secure. Considering the factors of both reaction time and the path length, the scheme aims to find the shortest secure path. The security analysis shows that this scheme can resist the black hole attack, the wormhole attack, the rushing attack, the sybil attack, and other types of common attacks. Through extensive simulations, results demonstrate that this approach can find many more active paths than SRP without bringing negative influences into the normal scenario. Furthermore, this solution largely improves the packet delivery ratio in the black hole attack scenario at an acceptable cost.

Abstract:This paper presents a bottom-up approach to implement the automatic and scientific transform of access control policies in the migration. First, the problem of mining security labels optimally is described formally, and it is then proved to be NP-complete. Next, an approximate optimization algorithm based on hierarchical clustering and genetic algorithm is presented, which decomposes the problem into two parts: category partition and secret level assignation. Finally, experimental results show that the algorithm is effective in finding an optimal solution. The proposed approach can be applied to migration projects in hierarchy protection in information security.

Abstract:This paper proposes an efficient Identity-Based authenticated key agreement protocol based on Waters’ Identity-Based Encryption scheme and gives a detail security analysis with provable security techniques in the standard model. It is more efficient than other similar protocols, and provides known-key security and forward secrecy. And it also resists key-compromise impersonation and unknown key share attacks. Moreover, this protocol is extended to satisfy the requirement that the session key should be escrowed by the Private Key Generation (PKG) center, and is given a key confirmation property with a secure message authentication code algorithm.

Abstract:Routing fails frequently because of the node mobility of MANET. The regular TCP works badly in MANET because the congestion control algorithm takes all the problems in MANET (disconnections, route changes, etc.) as congestion. To improve the efficiency of end to end transmission, this paper proposes a cross-layer transmission control protocol that interacts with link reliable routing protocols, which are called TCP-PLRT (transmission control protocol based on probability of link residual lifetime). TCP-PLRT judges the stability of end to end connection through information about the probability of the link residual lifetime that feedback from routing layer. Three complementary mechanisms have been proposed: ROUTING SWITCH, if the link is not stable enough, SAVE THEN FORWARD, if the link is about to break, and ACK RECONFIRM, if the routing has been rebuilt. Therefore, TCP-PLRT can do prediction before routing failure, and do remediation after it happens. It has been shown by computer simulation that results of TCP-PLRT have significantly improved the packet loss, caused by routing failure, and have increased the throughput much more.

Abstract:Ad hoc and sensor networks have a wide range of potential, practical and useful applications. Efficient hierarchical cluster organization plays an important role in wireless network systems without centralized control or infrastructure. In cluster-based wireless networks, in order to select a few dominating nodes to form a virtual backbone that supports routing and other tasks, such as broadcasting, area monitoring, etc., most of the published research regarding construction of connected dominating sets (CDS) in the literature has focused on selecting a small nodes set for high efficient performance based on different assumptions and design objectives. A review on more than 20 CDS construction mechanisms based on various assumptions, design objectives and performance results is provided in this paper. Some future research directions in this area are also pointed out.

Abstract:In this paper, a toolkit is created for designing vision-based gesture interactions. First, an abstract model for non-contact devices is proposed. Then, based on a data flow diagram method and an interactive learning approach, the IEToolkit is presented. It is designed based on the attributes of vision interaction and shields the underlying details of the computer vision algorithms. It has the following characteristics: a scalable interface to facilitate developers to add new classifiers, a unified management mechanism that provides dynamic configuration for all of the classifiers, and a visual user interface that supports the definition of a high-level semantic gesture. Finally, several prototypes are given. Experimental results show that the IEToolkit can provide a unified platform and a general solution for vision-based hand gesture games.

Abstract:This paper proposes a Post-WIMP interface model for personal information management (PWPIM), presents five facets to elaborate user character, domain objects, and interaction tasks, and gives the modeling method. Finally, this paper applies PWPIM to a physical interface based PIM (personal information management) system. The application example of PWPIM shows that, PWPIM can effectively describe the Post-WIMP interface for personal information management. Results also show that PWIM is fit for the feature of PIM system and is capable of guiding the PIM interface in design, development, and evaluation.

Abstract:The paper presents a local greedy algorithm that minimizes the energy defined by a variational mesh approximation. The algorithm simplifies the mesh by controlling the number of target polygons, while attempting to gain ideal effect from adaptively selected seed triangles. The algorithm has an intuitive geometric meaning. The algorithm is efficient enough to be efficiently adopted in the geometric modeling system.

Abstract:This paper proposes a 3D geometric constraint solving method, based on equivalence analysis in graph theory, that can handle over-constrained, well-constrained, and under-constrained configurations naturally and efficiently. The basic idea is that there are equivalent geometric constraint systems with different geometric constraint graphs. If the geometric domain knowledge is exploited to transform a geometric constraint system into an equivalent one that has a better geometric constraint graph structure using equivalent constraint substitution, the decomposition of geometric constraint system can be optimized. Therefore, the proposed approach will not depend on the initial geometric constraint graph structure, but on the inherent characteristic of the geometric constraint system. This proposition can usually find the optimal decomposition of the geometric constraint system. Several typical examples have been given to illustrate the correctness and effectiveness of the proposed method.