Digital Commons Network^™

A First Practical Algorithm For High Levels Of Relational Consistency, Shant Karakashian, Robert J. Woodward, Christopher Reesons, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R(∗,m)C, which is equivalent to m-wise consistency proposed in relational databases. We also define wR(∗,m)C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tightening the existing relations and without introducing new ones. We empirically show that wR(∗,m)C solves in a backtrack-free manner all the instances of some CSP benchmark classes, thus hinting at the tractability of those classes.

Communication With Aboveground Devices In Wireless Underground Sensor Networks: An Empirical Study, Agnelo R. Silva, Mehmet C. Vuran

CSE Conference and Workshop Papers

Wireless Underground Sensor Networks (WUSNs) consist of wirelessly connected underground sensor nodes that communicate untethered through soil. WUSNs have the potential to impact a wide variety of novel applications including intelligent irrigation, environment monitoring, border patrol, and assisted navigation. Although its deployment is mainly based on underground sensor nodes, a WUSN still requires aboveground devices for data retrieval, management, and relay functionalities. Therefore, the characterization of the bi-directional communication between a buried node and an aboveground device is essential for the realization of WUSNs. In this work, empirical evaluations of underground-to-aboveground (UG2AG) and aboveground-to-underground (AG2UG) communication are presented. More specifically, …

A First Practical Algorithm For High Levels Of Relational Consistency, Shant Karakashian, Robert J. Woodward, Christopher Reeson, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

•Introduction

•Relational Consistency R(*,m)C :

–Definition, Naïve algorithm, Properties

•Preliminaries: Dual CSP

•Our Approach

–Algorithm

–Index-Tree Data Structure

–Advantages

•A weakened version of R(*,m)C: wR(*,m)C

•Experimental Evaluations

•Conclusions & Future Work

A First Practical Algorithm For High Levels Of Relational Consistency, Shant Karakashian, Robert J. Woodward, Christopher Reeson, Berthe Y. Choueiry, Christian Bessiere

CSE Conference and Workshop Papers

Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R(*,m)C, which is equivalent to m-wise consistency proposed in relational databases. We also define wR(*,m)C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tightening the existing relations and without introducing new ones. We empirically show that wR(*,m)C solves in a backtrackfree manner all the instances of some CSP benchmark classes, thus hinting at the tractability …

A Partial Taxonomy Of Substitutability & Interchangeability, Shant Karakashian, Robert J. Woodward, Berthe Y. Choueiry, Steven D. Prestwich, Eugene C. Freuder

CSE Conference and Workshop Papers

•Introduction

–Basic form & extensions

–Features & use

–Further developments

•Taxonomy using a partial order

–One example

•Relation to

–General forms of symmetry

–Symmetry breaking during search

•Future research & conclusions

A Partial Taxonomy Of Substitutability And Interchangeability, Shant Karakashian, Robert J. Woodward, Berthe Y. Choueiry, Steven D. Prestwich, Eugene C. Freuder

CSE Conference and Workshop Papers

Substitutability, interchangeability and related concepts in Constraint Programming were introduced approximately twenty years ago and have given rise to considerable subsequent research. We survey this work, classify, and relate the different concepts, and indicate directions for future work, in particular with respect to making connections with research into symmetry breaking. This paper is a condensed version of a larger work in progress.

A Unified Solution To Scan Test Volume, Time, And Power Minimization, Zhen Chen, Sharad C. Seth, Dong Xiang, Bhargab B. Bhattacharya

CSE Conference and Workshop Papers

The double-tree scan-path architecture, originally proposed for low test power, is adapted to simultaneously reduce the test application time and test data volume under external testing. Experimental results show significant performance improvements over other existing scan architectures.

Linear Programming Models For Multi-Channel P2p Streaming Systems, Miao Wang, Lisong Xu, Byrav Ramamurthy

CSE Conference and Workshop Papers

Most of the commercial P2P video streaming deployments support hundreds of channels and are referred to as multichannel systems. Measurement studies show that bandwidth resources of different channels are highly unbalanced and thus recent research studies have proposed various protocols to improve the streaming qualities for all channels by enabling cross-channel cooperation among multiple channels. However, there is no general framework for comparing existing and potential designs for multi-channel P2P systems. The goal of this paper is to establish tractable models for answering the fundamental question in multi-channel system designs: Under what circumstances, should a particular design be used to …

Spatio-Temporal Soil Moisture Measurement With Wireless Underground Sensor Networks, Xin Dong, Mehmet C. Vuran

CSE Conference and Workshop Papers

In this paper, the estimation distortion of distributed soil moisture measurement using Wireless Underground Sensor Networks (WUSNs) is investigated. The main focus of this paper is to analyze the impact of the environment and network parameters on the estimation distortion of the soil moisture.More specifically, the effects of rainfall, soil porosity, and vegetation root zone are investigated by exploiting a rainfall model, in addition to the effects of sampling rate, network topology, and measurement signal noise ratio. Spatio-temporal correlation is characterized to develop a measurement distortion model with respect to these factors. The evaluations reveal that with porous soil and …

Cost Efficiency Of Anycast-Based Forwarding In Duty-Cycled Wsns With Lossy Channel, Yuyan Xue, Mehmet C. Vuran, Byrav Ramamurthy

CSE Conference and Workshop Papers

Anycasting has been proposed recently as an efficient communication method for asynchronous duty-cycled wireless sensor networks. However, the interdependencies between end-toend communication cost and the anycasting design parameters have not been systematically studied. In this paper, a statistical endtoend cost model is presented to capture the end-to-end latency and energy consumption of anycasting operation under a realistic wireless channel model. By exploring the relationship between the end-to-end cost efficiency and the forwarding decision dependent anycasting design parameters, two anycasting forwarding metrics are proposed for fully distributed forwarding decision. By exploring the relationship among the preamble length, the size of the …

Stochastic Analysis Of Energy Consumption In Wireless Sensor Networks, Yunbo Wang, Mehmet C. Vuran, Steve Goddard

CSE Conference and Workshop Papers

Limited energy resources in increasingly sophisticated wireless sensor networks (WSNs) call for a comprehensive crosslayer analysis of energy consumption in a multi-hop network. For reliability analysis in such networks, the statistical information about energy consumption and lifetime is required. However, traditional energy analysis approaches only focus on the average energy consumed. In this paper, instead, we provide a stochastic analysis of the energy consumption in a random network environment. Accordingly, a comprehensive cross-layer analysis framework, which employs a stochastic queueing model, is developed. Using this framework, the distribution of energy consumption for nodes in WSNs during a given time period …

Preface, Berthe Y. Choueiry, Bob Givan

CSE Conference and Workshop Papers

The Tenth International Symposium on Artificial Intelligence and Mathematics (ISAIM 2008) gathered a fine and distinguished crowd of researchers active in mathematics, theoretical computer science, and artificial intelligence. The three-day meeting, held from January 2 to 4, 2008, in Fort Lauderdale, featured invited talks by keynote speakers David McAllester, Francesca Rossi and Naftali Tishby. The program also included special sessions on “Computation and Social Choice” (organized by Toby Walsh), “Effective Exploration in Active Learning and Reinforcement Learning” (organized by Pascal Poupart), and “Logic in Artificial Intelligence” (organized by Michael Kaminski and Miroslaw Truszczynski, and the subject of a separate special …