1889757
Lightweight Deployment-Aware Scheduling for Wireless Sensor Networks
Wireless sensor networks consist of a large number of tiny sensors that have only limited energy supply. One of the major challenges in constructing such networks is to maintain long network lifetime as well as sufficient sensing areas. To achieve this goal, a broadly-used method is to turn off redundant sensors. In this paper, the problem of estimating redundant sensing areas among neighbouring wireless sensors is analysed. We present simple methods to estimate the degree of redundancy without the knowledge of location or directional information. We also provide tight upper and lower bounds on the probability of complete redundancy and on the average partial redundancy. With random sensor deployment, our analysis shows that partial redundancy is more realistic for real applications, as complete redundancy is expensive, requiring up to 11 neighbouring sensors to provide a 90 percent chance of complete redundancy. Based on the analysis, we propose a scalable Lightweight Deployment-Aware Scheduling (LDAS) algorithm, which turns off redundant sensors without using accurate location information. Simulation study demonstrates that the LDAS algorithm can reduce network energy consumption and provide desired QoS requirement effectively.
45061344
Space Complexity of Estimation of Distribution Algorithms
In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure.
181464
An Analysis of Phase Transition in NK Landscapes
In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.
2287582
Resolution complexity of random constraint satisfaction problems: Another half of the story
Let C"n","m^2^,^k^,^t be a random constraint satisfaction problem (CSP) on n binary variables, where m constraints are selected uniformly at random from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions. We establish an upper bound on the constraint tightness threshold for C"n","m^2^,^k^,^t to have an exponential resolution complexity. The upper bound partly answers the open problem regarding the CSP resolution complexity with the tightness between the existing upper and lower bounds [D. Mitchell, Resolution complexity of random constraints, in: Proceedings Principles and Practices of Constraint Programming-CP 2002, Springer, Berlin, 2002, pp. 295-309].
3221081
Consistency and Random Constraint Satisfaction Models
In this paper, we study the possibility of designing non-trivial random CSP models by exploiting the intrinsic connection between structures and typical-case hardness. We show that constraint consistency, a notion that has been developed to improve the efficiency of CSP algorithms, is in fact the key to the design of random CSP models that have interesting phase transition behavior and guaranteed exponential resolution complexity without putting much restriction on the parameter of constraint tightness or the domain size of the problem. We propose a very flexible framework for constructing problem instances with interesting behavior and develop a variety of concrete methods to construct specific random CSP models that enforce different levels of constraint consistency. 
 
A series of experimental studies with interesting observations are carried out to illustrate the effectiveness of introducing structural elements in random instances, to verify the robustness of our proposal, and to investigate features of some specific models based on our framework that are highly related to the behavior of backtracking search algorithms.
11821573
Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference
There has been great interest in identifying tractable subclasses of NP complete problems and designing efficient algorithms for these tractable classes. Constraint satisfaction and Bayesian network inference are two examples of such problems that are of great importance in AI and algorithms. In this paper we study, under the frameworks of random constraint satisfaction problems and random Bayesian networks, a typical tractable subclass characterized by the treewidth of the problems. We show that the property of having a bounded treewidth for CSPs and Bayesian network inference problem has a phase transition that occurs while the underlying structures of problems are still sparse. This implies that algorithms making use of treewidth based structural knowledge only work efficiently in a limited range of random instance.
27306380
A case for exploiting self-similarity of network traffic in TCP congestion control
Analytical and empirical studies have shown the self-similar traffic can have detrimental impact on network performance including amplified queuing delay and packet loss ratio. On the flip side, the ubiquity of scale-invariant burstiness observed across diverse networking contexts can be exploited to better design resource control algorithms. In this paper, we explore the issueof exploiting the self-similar characteristics of network traffic in TCP congestion control. We show that the correlation structure present in long-range dependent traffic can be detected on-line and used to predict the future traffic. We then devise a novel scheme, called TCP with traffic prediction (TCP-TP), that exploits the prediction result to infer, in the context of AIMD steady state dynamics, the optimal operational point at which a TCP connection should operate. Through analytical reasoning, we show that the impact of prediction errors on fairness is minimal. We also conduct ns-2 simulation and freeBSD, 4.1-based implementation studies to validate the design and to demonstrate the performance improvement in terms of packet loss ratio and throughput attained by connections.
18781820
QSAR in grossly underdetermined systems: Opportunities and issues
Regression in grossly underdetermined systems has emerged as an important means for understanding molecular activity via comparative molecular field analysis (CoMFA) and other quantitative structure activity relationship (QSAR) studies. But this methodology has applications in much broader areas; for example, near-infrared spectroscopy, mutational enzyme activity studies including protein folding rates to determine which sites are important for determining conformation, and analyses of gene expression data from chip arrays. An error analysis which answers questions concerning the quality of the predictivity, the relative importance of each descriptor, the quality of the estimates of the contribution by each descriptor, and the number of independent components expressed by the associated data is indispensable in understanding whether some particular set of structure variables is important in defining the mechanisms driving the chemical or biological activities. This paper reviews opportunities for QSAR studies. It also considers the analytical aspects of error analysis in least-squares regression, and contrasts principal component regression (PCR) and partial least-squares (PLS) procedures with cross-validation on the issues of error analysis (e.g., the quality of the contribution estimates for each structure descriptor). Further, a methodology for selecting optimal subsets of components in PCR is presented.
16464835
Automated Face Pose Estimation Using Elastic Energy Models
Face pose estimation forms an important part in a face recognition system. However, fully automated and accurate pose determination still remains an unsolved problem in the research community. In this paper, we propose a novel elastic energy model to automatically estimate face poses. Our method employs statistical energy contributions of a set of feature points, which can avoid over-trusting selected anchor points. It provides a robust solution to the feature localisation inaccuracy problem, which is inevitable in practical applications with cluttered backgrounds. As a general configuration, our model can be easily implemented and extended to other non-rigid objects. Its effectiveness and robustness are revealed in our experiments
10844784
Meta-game Equilibrium for Multi-agent Reinforcement Learning
This paper proposes a multi-agent Q-learning algorithm called meta-game-Q learning that is developed from the meta-game equilibrium concept Different from Nash equilibrium, meta-game equilibrium can achieve the optimal joint action game through deliberating its preference and predicting others' policies in the general-sum game A distributed negotiation algorithm is used to solve the meta-game equilibrium problem instead of using centralized linear programming algorithms We use the repeated prisoner's dilemma example to empirically demonstrate that the algorithm converges to meta-game equilibrium.
6963840
Applying Neural Network to Reinforcement Learning in Continuous Spaces
This paper is concerned with the problem of Reinforcement Learning (RL) in large or continuous spaces. Function approximation is the main method to solve such kind of problem. We propose using neural networks as function approximators in this paper. Then we experiment with three kind of neural networks in Mountain-Car task and illustrate comparisons among them. The result shows that CMAC and Fuzzy ARTMAP perform better than BP in Reinforcement Learning with Function Approximation (RLFA).