Abstract:Message propagation algorithms are very effective in finding satisfying assignments for random kSAT instances and hard regions become more narrow. Unfortunately, this phenomenon is still lacks rigorous theoretical proofs. The Warning Propagation (WP) algorithm is the most basic message propagation algorithm. In order to analysis the WP algorithm convergence for random kCNF formulas, the study gives the sharp threshold point for the existence of cycles in the factor graph of random kCNF formulas, the threshold for the existence of cycles in model G(n,k,p) of random kCNF formulas is p=1/8n² for k=3, p=d/n². When d becomes asymptotically equal to 1/8, cycles begin to appear, but each component contains at most one cycle, the number of the components containing a single cycle and the length of cycle are a constant independent of n. Thus, the factor graph consists of a forest of trees plus a few components that have a single cycle. Then WHP (with high probability) after at most O(logn+s) iterations, WP converges on these instances. Here s is the size of the connected component.

Abstract:The negotiated scheduling problem of distributor is studied for a supply chain that consists of a manufacture and a distributor. The manufacturer is more influential than the distributor. It makes scheduling decisions followed by the distributor. The manufacture and distributor do not share information during the process time of any job. To improve scheduling results of the distributor, a negotiation model is built based on compensation mechanism. A negotiated scheduling strategy with information privacy is designed. A distributor negotiation-scheduling algorithm that consists of a scheduling algorithm of the manufacturer and ecologic population competition based coevolutionary algorithm of the distributor is designed and analyzed. Simulation experiments show that the negotiated scheduling of the distributor can effectively improve the scheduling performance of the distributor. Scheduling cost of the distributor can be cut down over 25% while the scheduling performance of the manufacturer does not become worse. Moreover, the proposed coevolutionary algorithm can obtain better scheduling solutions than the genetic, particle swarm optimization, and ant colony optimization algorithms.

Abstract:Partially observable Markov decision processes (POMDPs) provide a rich framework for sequential decision-making in stochastic domains of uncertainty. However, solving POMDPs is typically computationally intractable because the belief states of POMDPs have two curses: Dimensionality and history, and online algorithms that can not simultaneously satisfy the requirement of low errors and high timeliness. In order to address these problems, this paper proposes a point-based online value iteration (PBOVI) algorithm for POMDPs. This algorithm for speeding up POMDPs solving involves performing value backup at specific reachable belief points, rather than over the entire a belief simplex. The paper exploits branch-and-bound pruning approach to prune the AND/OR tree of belief states online and proposes a novel idea to reuse the belief states that have been computed last time to avoid repeated computation. The experiment and simulation results show that the proposed algorithm has its effectiveness in reducing the cost of computing policies and retaining the quality of the policies, so it can meet the requirement of a real-time system.

Abstract:With the ubiquitous software application, especially the wide usage of database applications and Web applications, strings have become a more important role in the software programs. At the same time, the program analysis techniques that consider the specialty of strings have been developed, and have been applied to various areas in software engineering. Usually, string value analysis is applied to acquire the possible values of a given string variable. Next, a constraint solver is applied to check whether the values satisfy predefined specifications, so that the correctness of the given string variable can be checked. To further apply string analysis to some security analysis and software maintenance problems, the string analysis is further improved to analyze the possible data origins of a given string variable. This paper presents a survey on string analysis, which mainly introduces the string value analysis, string constraint solving, string data origin analysis, and the applications of string analysis in software engineering.

Abstract:As an important application of acceleration in the cloud, the distributed caching technology has received considerable attention in industry and academia. This paper starts with a discussion on the combination of cloud computing and distributed caching technology, giving an analysis of its characteristics, typical application scenarios, stages of development, standards, and several key elements, which have promoted its development. In order to systematically know the state of art progress and weak points of the distributed caching technology, the paper builds a multi-dimensional framework, DctAF. This framework is constituted of 6 dimensions through analyzing the characteristics of cloud computing and boundary of the caching techniques. Based on DctAF, current techniques have been analyzed and summarized; comparisons among several influential products have also been made. Finally, the paper describes and highlights the several challenges that the cache system faces and examines the current research through in-depth analysis and comparison.

Abstract:Middleware is a kind of fundamental software that boomed in 1990s with the rapid development of computer networks. Its main function is to effectively support the development, deployment, operation and management of the network application software systems. With a new connotation, the network computing middleware has encountered a breakthrough of information networks technology and service-oriented software engineering. The former part of this paper, which starts with the network computing environment, gives a comprehensive interpretation on the basic concepts and main technologies of basic middleware, application integration middleware and domain application framework; the second half focuses on hot research topics such as cloud computing, Internet of things, and indicates a number of concerned research directions as well as several challenges and key technologies that need deep exploration from the point view of middleware.

Abstract:Task parallel programming model is a widely used parallel programming model on multi-core platforms. With the intention of simplifying parallel programming and improving the utilization of multiple cores, this paper provides an introduction to the essential programming interfaces and the supporting mechanism used in task parallel programming models and discusses issues and the latest achievements from three perspectives: Parallelism expression, data management and task scheduling. In the end, some future trends in this area are discussed.

Abstract:Mobile recommender systems have recently become one of the hottest topics in the domain of recommender systems. The main task of mobile recommender systems is to improve the performance and accuracy along with user satisfaction utilizing mobile context, mobile social network and other information. This paper presents an overview of the field of mobile recommender systems including key techniques, evaluation and typical applications. The prospects for future development and suggestions for possible extensions are also discussed.

Abstract:ROC Curve is an important method of model selection, but its uncertainty affects the accuracy of model selection. Based on discernible granularity and the view of reflecting the score's uncertainty, the study proposes the concept of gROC and gAUC, and discusses, theoretically, some properties of the gROC. The study also tests the reasonableness of gROC using binormal model after gave its algorithm. On this basis, the paper also proposes two model selection measures, λAUC and ρAUC. The effieciency of these measures is verified based on UCI data sets. Experimental results show that the gROC can effectively reflect the uncertainty of ROC curve, and the model selection methods based on λAUC and ρAUC are better than the method based on AUC or sAUC. In some cases, gROC has stronger capability on comparison of classifiers performance.

Abstract:BGP is a core Internet routing protocol. The Internet inter-domain routing relies on the exchange of BGP routing information. BGP has significant vulnerabilities, which have been found to cause problems such as prefix hijacking, route leak and Internet-targeted denial of service attack. First, by analyzing BGP route propagation and BGP routing policies, the fundamental flaw in the design of the protocol is revealed. The paper then discusses possible threats to BGP and presents a route leak model, which contributes to the description of its characteristics. Second, the existing defense mechanisms for BGP security are generalized, and their shortcomings are exposed. The paper then classifies various BGP security-enhancing technologies and studies them in detail to explore their advantages and disadvantages. Finally, the research trends of BGP security are discussed in this paper.

Abstract:The construction of overlays is a crucial problem in the research of mobile peer-to-peer networks. The architecture of overlays determines the robustness, security and performance of MP2P networks. The paper first introduces the concept of mobile P2P overlays, including the definition, significance of the construction of overlays and the classification of them. Next, three kinds of overlays, distributed unstructured, distributed structured and semi distributed (hybrid) network, are described. The application of overlays in MANET, VANET and WMN is especially introduced. Furthermore, the aforementioned overlays are analyzed and compared. Finally, the paper concludes and presents the future research directions.

Abstract:In order to decrease the resource cost in delay tolerant networks, single-copy forwarding protocols have been proposed by researchers. However, recent research has pointed out that single-copy forwarding protocols lead to great unfairness of the nodes' traffic load and make the highly connected nodes suffer congestion. In order to bridge this gap, a congestion control mechanism based on accepting the threshold is put forward in this paper, which makes each DTN node dynamically adjust to its accepting threshold and accordingly to its congestion state. Moreover, the mechanism can be widely adopted, since it is independent of the forwarding protocols and does not affect the choice of the relay nodes made by the forwarding protocol. In order to validate the proposed mechanism, an algorithm named SimBetCC is proposed, which incorporates the congestion control mechanism with existing SimBet protocol. Experimental results show that SimBetCC can cope with congestion and also outperforms FairRoute with congestion control in many aspects, e.g., the message delivery ratio, the delivery delay.

Abstract:To determine the end-to-end throughput capacity of IEEE 802.11-based wireless networks, existing works used a simplistic approach to divide the 1-hop throughput capacity by the number of contending links in the bottleneck region, which has is limited in terms accuracy, and relies on complicated non-linear equations. This makes it impractical to solve for a large number of hops. This paper presents an optimization methodology to analytically calculate the end-to-end throughput capacity of IEEE 802.11-based chain-topology wireless networks. The calculation considers the interference due to neighboring nodes and assesses the impact of hidden node collision as well as multi-rate terminals (i.e., nodes can transmit at different rates) on throughput capacity. The proposed methodology provides a very accurate calculation of the end-to-end throughput capacity when compared to existing works, and yet, is more practical to implement. With extensive simulation experiments, the study verifies the analysis and validates the proposed methodology.