Search

Component-based architectures are the traditional approach to reconcile application specific optimization with reusable abstractions in sensor networks. However, they frequently overwhelm the application designer with the range of choices in component selection and composition. We introduce a component framework that reduces this complexity. It provides a well-defined content-based publish/subscribe service, but allows the application designer to adapt the service by making orthogonal choices about: (1) the communication protocol components for subscription and notification delivery, (2) the supported data attributes and (3) a set of service extension components. We present TinyCOPS, our implementation of the framework in TinyOS 2.0, and demonstrate its advantages by showing experimental results for different application configurations on two sensor node platforms in a large-scale indoor testbed. [ABSTRACT FROM AUTHOR]

Several considerable impediments stand in the way of sensor network prototype applications that wish to realize sustained deployments. These are: scale, longevity, data of interest, and infrastructure integration. We present a tool, Que, which assists those sensor network deployments transitioning from prototypes to early production environments by addressing these issues. Que is able to simulate realistic deployments with faithful data, provide fast and iterative feedback on operations, and compose applications quickly in a platform-independent manner. We demonstrate Que's applicability via tests against our new data center environment-monitoring deployment, DataCenter.NET. [ABSTRACT FROM AUTHOR]

To support the increasing number of sensor devices with various characteristics and requirements, sensor network operating systems should provide an appropriate device driver model that can cover a wide range of device types. Unfortunately, current sensor network operating systems force the user to build complex drivers for even simple devices, provide restricted interfaces, or do not provide any mechanisms. We present a device driver model that is flexible enough to support both simple devices with simple drivers, and complex devices with portable and high-performance device drivers. Users can write a device driver for simple devices with only a few lines of code using the user-mode device driver. Devices that need highly efficient code or portability can be supported by a single-layer or 2-layer kernel-mode device driver. Moreover, shared access and power management can easily be included in the device driver using the device manager. We also provide guidelines for choosing a proper device driver model with concrete examples of real-world devices and support our claims through the evaluation of the device driver model using the RETOS kernel. [ABSTRACT FROM AUTHOR]

Sensors networks instrument the physical space using motes that run network embedded programs thus acquiring, processing, storing and transmitting sensor data. The motes commercially available today are large, costly and trade performance for flexibility and ease of programming. New generations of motes are promising to deliver significant improvements in terms of power consumption and price — in particular motes based on System-on-a-chip. The question is how do we compare mote performance? How to find out which mote is best suited for a given application? In this paper, we propose a vector-based methodology for benchmarking mote performance. Our method is based on the hypothesis that mote performance can be expressed as the scalar product of two vectors, one representing the mote characteristics, and the other representing the application characteristics. We implemented our approach in TinyOS 2.0 and we present the details of our implementation as well as the result of experiments obtained on commercial motes from Sensinode. We give a quantitative comparison of these motes, and predict the performance of a data acquisition application. [ABSTRACT FROM AUTHOR]

We present Typhoon, a protocol designed to reliably deliver large objects to all the nodes of a wireless sensor network (WSN). Typhoon uses a combination of spatially-tuned timers, prompt retransmissions, and frequency diversity to reduce contention and promote spatial re-use. We evaluate the performance benefits these techniques provide through extensive simulations and experiments in an indoor testbed. Our results show that Typhoon is able to reduce dissemination time and energy consumption by up to three times compared to Deluge. These improvements are most prominent in sparse and lossy networks that represent real-life WSN deployments. [ABSTRACT FROM AUTHOR]

By using Elliptic Curve Cryptography (ECC), it has been recently shown that Public-Key Cryptography (PKC) is indeed feasible on resource-constrained nodes. This feasibility, however, does not necessarily mean attractiveness, as the obtained results are still not satisfactory enough. In this paper, we present results on implementing ECC, as well as the related emerging field of Pairing-Based Cryptography (PBC), on two of the most popular sensor nodes. By doing that, we show that PKC is not only viable, but in fact attractive for WSNs. As far as we know pairing computations presented in this paper are the most efficient results on the MICA2 (8-bit/7.3828-MHz ATmega128L) and Tmote Sky (16-bit/8.192-MHz MSP-430) nodes. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) are increasingly being proposed in scenarios whose requirements cannot be fully predicted, or where the system functionality must adapt to changing conditions. In these scenarios, the ability to reconfigure portions of the software running on WSN nodes becomes imperative. At the same time, recent WSN proposals often employ heterogeneous nodes (e.g., sensors and actuators), which require the deployment of different code on different devices, based on their characteristics. Unfortunately, existing work in the field largely focuses on simpler scenarios where the same, monolithic program is distributed to all the nodes in the WSN. In this paper we present FiGaRo, a programming model supported by an efficient run-time system and distributed protocols, collectively enabling an unprecedented fine-grained control over what is being reconfigured, and where. Using FiGaRo, the programmer can deal explicitly with component dependencies and version constraints, as well as select precisely the subset of nodes targeted by reconfiguration, leaving the others unaltered. We show that our run-time support imposes a very limited processing and memory overhead, while the communication overhead lies within 9% of the theoretical optimum. [ABSTRACT FROM AUTHOR]

In a Wireless Sensor Network, sensor nodes may fail for several reasons and the network may split into two or more disconnected partitions. This may deteriorate or even nullify the usefulness and effectiveness of the network. Therefore, repairing partitions is a priority. In this paper we present a method to repair network partitions by using mobile nodes. By reasoning upon the degree of connectivity with neighbours, a mobile node finds the proper position where to stop in order to re-establish connectivity. Factors influencing the method performance are singled out and criteria for their selection are discussed. Simulations show that the proposed method is effective and efficient notwithstanding packet loss. [ABSTRACT FROM AUTHOR]

Clustering is an important mechanism in large multi-hop wireless sensor networks for obtaining scalability, reducing energy consumption and achieving better network performance. Most of the research in this area has focused on energy-efficient solutions, but has not thoroughly analyzed the network performance, e.g. in terms of data collection rate and time. The main objective of this paper is to provide a useful fully-distributed inference algorithm for clustering, based on belief propagation. The algorithm selects cluster heads, based on a unique set of global and local parameters, which finally achieves, under the energy constraints, improved network performance. Evaluation of the algorithm implementation shows an increase in throughput in more than 40% compared to HEED scheme. This advantage is expressed in terms of network reliability, data collection quality and transmission cost. [ABSTRACT FROM AUTHOR]

We consider the problem of determining the transmission power assignment that maximizes the lifetime of a data-gathering wireless sensor network with stationary nodes and static transmission power levels. We present a simple and efficient distributed algorithm for this task that works by establishing the minimum power level at which the network stays connected. The algorithm is based on a binary search over the range of feasible transmission power levels and does not require prior knowledge of network topology. We study the performance of the resulting BSpan protocol by network simulations and compare the number of control messages required by BSpan to two other recently proposed methods, the Distributed Min-Max Tree (DMMT) and Maximum Lifetime Spanner (MLS) algorithms. We find that BSpan outperforms both DMMT and MLS significantly. [ABSTRACT FROM AUTHOR]

The mass casualty emergency response involves logistic impediments like overflowing victims, paper triaging, extended victim wait time and transport. We propose a new system based on a location aware wireless sensor network (WSN) to overcome these impediments and assists the emergency responders (ER) in providing efficient emergency response. We have developed a ZigBeeready acceleration sensor node hardware which is energy efficient as shown by its current consumption results. ZigBee mesh network is setup and a RSSI-based localization solution is analyzed. The main functionality of this WSN is to collect real time data - patient/emergency doctor tracking, triage information, patient vital signs/activity and communicate it to the ER' Monitor Station device that runs the visualization software. We have implemented this software using the new ‘Care Zone Count Algorithm' a dynamic mechanism based on localized events and data acquired from the WSN. This algorithm calculates and displays the patient count in each care zone, victim flow rate, transport capacity, thereby enabling the ER to efficiently estimate the resources required. The analysis of this algorithm verifies that the proposed system creates situation awareness to the ER. [ABSTRACT FROM AUTHOR]

Future mobile sensing systems are being designed using 802.15.4 low-power short-range radios for a diverse set of devices from embedded mobile motes to sensor-enabled cellphones in support, for example, of people-centric sensing applications. However, there is little known about the use of 802.15.4 in mobile sensor settings nor its impact on the performance of future communication architectures. We present a set of initial results from a simple yet systematic set of benchmark experiments that offer a number of important insights into the radio characteristics of mobile 802.15.4 person-to-person communication. Our results show that the body factor - that is to say, the human body and where sensors are located on the body (e.g., on the chest, foot, in the pocket) - has a significant effect on the performance of the communications system. While this phenomenon has been discussed in the context of other radios (e.g., cellular, WiFi, UWB) its impact on 802.15.4 based mobile sensor networks is not understood. Other findings that also serve to limit the communication performance include the effective contact times between mobile nodes, and, what we term the zero bandwidth crossing, which is a product of mobility and the body factor. This paper presents a set of initial findings and insights on this topic, and importantly, we consider the impact of these findings on the design of future communication architectures for mobile sensing. [ABSTRACT FROM AUTHOR]

Although formerly conceived for industrial sensing and control over Wireless Sensor Networks, LR-WPANs are registering an increasing interest in experimenting multimedia applications, with particular emphasis on evaluating the streaming capability of Zigbee networks. Due to their limited throughput they are not expected to provide high QoS, nevertheless there are several application scenarios such as distributed surveillance, emergency and rescue where audio and video streaming over low cost Zigbee networks is highly desirable. In this paper we first investigate the feasibility of Zigbee-like networks for low-rate voice streaming applications. We analyze important streaming metrics such as throughput, packet loss and jitter in multi-hop topologies. We propose some improvements in the stack implementation and show the performance in order to determine the streaming capacity limits of LR-WPAN networks. [ABSTRACT FROM AUTHOR]

Storing and disseminating coded information instead of the original data can bring significant performance improvements to sensor network protocols. Such methods reduce the risk of having some data replicated at many nodes, whereas other data is very scarce. This is of particular importance for data persistence in sensor networks. While coding is generally beneficial, coding over all available packets can be detrimental to performance, since coded information might not be decodable after a network failure. In this paper we investigate the suitability of different codeword degree distributions with respect to the dynamics of the underlying wireless network and design a corresponding data management algorithm. We further propose a simple buffer management scheme for continuous data gathering. The performance of the protocols is demonstrated by means of simulation, as well as experiments with an implementation on MICAz motes. [ABSTRACT FROM AUTHOR]

We examine the problem of tracking dynamic boundaries occurring in natural phenomena using range sensors. Two main challenges of the boundary tracking problem are energy-efficient boundary estimations from noisy observations and continuous tracking of the boundary. We propose a novel approach which uses a regression-based spatial estimation technique to determine discrete points on the boundary and estimates a confidence band around the entire boundary. In addition, a Kalman Filter-based temporal estimation technique is used to selectively refresh the estimated boundary to meet the accuracy requirements. Our algorithm for dynamic boundary tracking (DBTR) combines temporal estimation with an aperiodically updated spatial estimation and provides a low overhead solution to track boundaries without requiring prior knowledge about the dynamics of the boundary. Experimental results demonstrate the effectiveness of our algorithm and estimated confidence bands achieve loss of coverage of less than 2 − 5% for a variety of boundaries with different spatial characteristics. [ABSTRACT FROM AUTHOR]

In Wireless Sensor Networks large number of nodes and limited energy available per node calls for designing efficient transmission protocols. Cooperative transmission is one of the protocols which helps wireless nodes to achieve spatial diversity, which translates into reduction in transmission power or increase in coverage area. Cooperative protocol can be realized with or without (called conventional afterward) network coding; and the network-coding-based (respectively the conventional) protocol can be operated in either static or adaptive manner. For an efficient operation of cooperative protocols, good quality inter-source channels are required, which in turn depend on relative location of nodes within a network. In this work, a three-node cooperative network consisting of source, relay, and destination nodes is considered. At high signal-to-noise ratio values, we first approximate the outage probability result when the network-coding-based adaptive protocol is implemented. Then, based on the approximate probability result, a diversity-multiplexing tradeoff is studied; the result shows that this protocol performs similar to an amplify-and-forward protocol. Next, for the various protocols, the coverage area and relative location of the relay that minimizes the outage are studied; for that the exact outage probability results are used. Over wider geographic area, network-coding-based static and adaptive protocols perform better than their conventional counterparts, and this happens when the relaying node is positioned closer to the destination than the source. The conventional protocols perform better when the relay is positioned closer to the source. In Wireless Sensor Networks, assuming that relay nodes which are closer to both the source and destination exist, these results help as a guide in selecting with which node to cooperate (relay selection) when one cooperative scheme is implemented. [ABSTRACT FROM AUTHOR]

Today it is possible to deploy sensor networks in the real world and collect large amounts of raw sensory data. However, it remains a major challenge to make sense of sensor data, i.e., to extract high-level knowledge from the raw data. In this paper we present a novel in-network knowledge discovery technique, where high-level information is inferred from raw sensor data directly on the sensor nodes. In particular, our approach supports the discovery of frequent distributed event patterns, which characterize the spatial and temporal correlations between events observed by sensor nodes in a confined network neighborhood. One of the key challenges in realizing such a system are the constrained resources of sensor nodes. To this end, our solution offers a declarative query language that allows to trade off detail and scope of the sought patterns for resource consumption. We implement our proposal on real hardware and evaluate the trade-off between scope of the query and resource consumption. [ABSTRACT FROM AUTHOR]

A localization algorithm using radio interferometric measurements is presented. A probabilistic model is constructed that accounts for general noise models and lends itself to distributed computation. A message passing algorithm is derived that exploits the geometry of radio interferometric measurements and can support sparse network topologies and noisy measurements. Simulations on real and simulated data show promising performance for 2D and 3D deployments. [ABSTRACT FROM AUTHOR]

In this paper, we use Bayesian Networks as a means for unsupervised learning and anomaly (event) detection in gas monitoring sensor networks for underground coal mines. We show that the Bayesian Network model can learn cyclical baselines for gas concentrations, thus reducing false alarms usually caused by flatline thresholds. Further, we show that the system can learn dependencies between changes of concentration in different gases and at multiple locations. We define and identify new types of events that can occur in a sensor network. In particular, we analyse joint events in a group of sensors based on learning the Bayesian model of the system, contrasting these events with merely aggregating single events. We demonstrate that anomalous events in individual gas data might be explained if considered jointly with the changes in other gases. Vice versa, a network-wide spatiotemporal anomaly may be detected even if individual sensor readings were within their thresholds. The presented Bayesian approach to spatiotemporal anomaly detection is applicable to a wide range of sensor networks. [ABSTRACT FROM AUTHOR]

Precise localization of mobile objects is a common problem in WSN research for which various approaches exist. However, apart from technical aspects and the location estimation itself, speed, reliability and energy efficiency are central but barely addressed aspects within such systems. We will point out, that the applied wireless communication affects these aspects significantly before comparing some well-known and commonly used radio protocols to the self-organizing HashSlot approach which was optimized for efficiency in wireless information aggregation. Besides some theoretical considerations, this paper presents practical results from a real-world testbed based on the ultrasound localization system SNoW Bat. [ABSTRACT FROM AUTHOR]

We address the problem of designing practical, energy-efficient protocols for data collection in wireless sensor networks using predictive modeling. Prior work has suggested several approaches to capture and exploit the rich spatio-temporal correlations prevalent in WSNs during data collection. Although shown to be effective in reducing the data collection cost, those approaches use simplistic corelation models and further, ignore many idiosyncrasies of WSNs, in particular the broadcast nature of communication. Our proposed approach is based on approximating the joint probability distribution over the sensors using undirected graphical models, ideally suited to exploit both the spatial correlations and the broadcast nature of communication. We present algorithms for optimally using such a model for data collection under different communication models, and for identifying an appropriate model to use for a given sensor network. Experiments over synthetic and real-world datasets show that our approach significantly reduces the data collection cost. [ABSTRACT FROM AUTHOR]

Activity recognition from an on-body sensor network enables context-aware applications in wearable computing. A guaranteed classification accuracy is desirable while optimizing power consumption to ensure the system's wearability. In this paper, we investigate the benefits of dynamic sensor selection in order to use efficiently available energy while achieving a desired activity recognition accuracy. For this purpose we introduce and characterize an activity recognition method with an underlying run-time sensor selection scheme. The system relies on a meta-classifier that fuses the information of classifiers operating on individual sensors. Sensors are selected according to their contribution to classification accuracy as assessed during system training. We test this system by recognizing manipulative activities of assembly-line workers in a car production environment. Results show that the system's lifetime can be significantly extended while keeping high recognition accuracies. We discuss how this approach can be implemented in a dynamic sensor network by using the context-recognition framework Titan that we are developing for dynamic and heterogeneous sensor networks. [ABSTRACT FROM AUTHOR]

Duty-cycling is an appealing solution for energy savings in densely deployed, energy-constrained wireless sensor networks (WSNs). Indeed, several applications, such as intruder detection and tracking, require the design of k-covered WSNs, which are densely in nature and where each location in a monitored field is covered (or sensed) by at least k active sensors. With duty-cycling, sensors can be turned on or off according to a scheduling protocol, thus reducing the number of active sensors required to k-cover a field and helping all sensors deplete their energy slowly and uniformly. In this paper, we propose a duty-cycling framework, called clustered randomized m-connected k-coverage (CRACCmk), for k-coverage of a sensor field. We present two protocols using CRACCmk, namely T-CRACCmk and D-CRACCmk, which differ by their degree of granularity of network clustering. We prove that the CRACCmk protocols are minimum energy m-connected k-coverage protocols in that each deploys a minimum number of active sensors to k-cover a sensor field and that k-coverage implies m-connectivity between all active sensors, with m being larger than k. We enhance the practicality of the CRACCmk protocols by relaxing some widely used assumptions for k-coverage. Simulation results show that the CRACCmk protocols outperform existing k-coverage protocols for WSNs. [ABSTRACT FROM AUTHOR]

Parser combinators are higher-order functions used to build parsers as executable specifications of grammars. Some existing implementations are only able to handle limited ambiguity, some have exponential time and/or space complexity for ambiguous input, most cannot accommodate left-recursive grammars. This paper describes combinators, implemented in Haskell, which overcome all of these limitations. [ABSTRACT FROM AUTHOR]

An extended practice in the realm of Software Engineering and programming in industry is the application of coding rules. Coding rules are customarily used to constrain the use (or abuse) of certain programming language constructions. However, these rules are usually written using natural language, which is intrinsically ambiguous and which may complicate their use and hinder their automatic enforcement. This paper presents some early work aiming at defining a framework to formalise and check for coding rule conformance using logic programming. We show how a certain class of rules - structural rules - can be reformulated as logic programs, which provides both a framework for formal specification and also for automatic conformance checking using a Prolog engine. Some examples of rules belonging to actual, third-party coding rule sets are discussed, along with the corresponding Prolog code. Experimental data regarding the practicality and impact of their application to real-life software projects is presented and discussed. [ABSTRACT FROM AUTHOR]

This paper presents an environment to support high-level database programming in the multi-paradigm declarative programming language Curry. We define an application programming interface (API) that abstracts from the concrete database access methods. The API supports transactions and exploits Curry's type system to ensure a strict separation between queries and updates. In order to ensure database updates that are safe w.r.t. an intended data model (e.g., containing specific relations between entities), we assume a description of the data dependencies in the entity-relationship (ER) model from which all access and update operations related to the database are generated. We propose a representation of ER diagrams in the declarative language Curry so that they can be constructed by various tools and then translated into this representation. Furthermore, we have implemented a compiler from this representation into a Curry program that provides safe access and update operations based on the API for database programming. [ABSTRACT FROM AUTHOR]

More and more software systems use a browser as the universal graphical user interface. As a consequence these applications inherit browser navigation as part of their interface. Typical browser actions are the use of the back- and forward-button and the cloning of windows. Browser navigation is difficult to deal with because it has effects that are noticed indirectly by the application logic. It is easy to forget or misunderstand the consequences of this aspect in the construction of a program. Hence, testing the correct behavior of the application is very desirable, preferably with an automatic model-based test tool. For this kind of model-based testing a specification including browser navigation is needed. We introduce a transformation to lift the specification of a program without browser navigation to one with browser navigation. This reduces the specification effort considerably. The distinguishing feature of our method is that it allows the test engineer to specify only the exceptions to the general rule. We show how this lifting of specifications is used for some examples and how errors are found in real web applications. The described system builds on the model-based test tool G∀ST. [ABSTRACT FROM AUTHOR]

In this paper, we present an implementation of a modular synthesizer in Haskell using Yampa. A synthesizer, be it a hardware instrument or a pure software implementation, as here, is said to be modular if it provides sound-generating and sound-shaping components that can be interconnected in arbitrary ways. Yampa, a Haskell-embedded implementation of Functional Reactive Programming, supports flexible, purely declarative construction of hybrid systems. Since music is a hybrid continuous-time and discrete-time phenomenon, Yampa is a good fit for such applications, offering some unique possibilities compared to most languages targeting music or audio applications. Through the presentation of our synthesizer application, we demonstrate this point and provide insight into the Yampa approach to programming reactive, hybrid systems. We develop the synthesizer gradually, starting with fundamental synthesizer components and ending with an application that is capable of rendering a standard MIDI file as audio with respectable performance. [ABSTRACT FROM AUTHOR]

Logtalk, an object oriented logic programming language, provides experimental support for multi-threading programming with selected back-end Prolog compilers. By making use of core, low-level Prolog predicates that interface with operating-system native threads, Logtalk provides a high-level set of directives and predicates that allows programmers to easily take advantage of modern multi-processor and multi-core computers without worrying about the details of creating, synchronizing, or communicating with threads. Logtalk multi-threading programming features include support for concurrent calls akin to and-parallelism and or-parallelism, non-deterministic thread goals, asynchronous calls, and predicate synchronization. The integration with the Logtalk object-oriented features allows objects to send and receive both synchronous and asynchronous messages and to call local predicates concurrently. Logtalk multi-threading features are orthogonal to object-oriented concepts and can be useful even in the context of plain Prolog. [ABSTRACT FROM AUTHOR]

Most efficient implementations of parallel logic programming rely on complex low-level machinery which is arguably difficult to implement and modify. We explore an alternative approach aimed at taming that complexity by raising core parts of the implementation to the source language level for the particular case of and-parallelism. We handle a significant portion of the parallel implementation at the Prolog level with the help of a comparatively small number of concurrency-related primitives which take care of lower-level tasks such as locking, thread management, stack set management, etc. The approach does not eliminate altogether modifications to the abstract machine, but it does greatly simplify them and it also facilitates experimenting with different alternatives. We show how this approach allows implementing both restricted and unrestricted (i.e., non fork-join) parallelism. Preliminary experiments show that the performance sacrificed is reasonable, although granularity control is required in some cases. Also, we observe that the availability of unrestricted parallelism contributes to better observed speedups. [ABSTRACT FROM AUTHOR]

Master-worker systems are a well-known and often applicable scheme for the parallel evaluation of a pool of tasks, a work pool. The system consists of a master process managing a set of worker processes. After an initial phase with a fixed amount of tasks for each worker, further tasks are distributed in reply to results sent back by the workers. As this setup quickly leads to a bottleneck in the master process, the paper investigates techniques for hierarchically nesting the basic master-worker scheme. We present implementations of hierarchical master-worker skeletons, and how to automatically calculate parameters of the nested skeleton for good performance. Nesting master-worker systems is nontrivial especially in cases where new tasks are dynamically created from previous results (typically breadth- or depth-first tree search algorithms). We discuss how to handle dynamically growing pools in a hierarchy and present a declarative implementation for nested master-worker systems with dynamic task creation. The skeletons are experimentally evaluated with two typical test programs. We analyse their runtime behaviour and the effects of different hierarchies on runtimes via trace visualisations. [ABSTRACT FROM AUTHOR]

Tabled evaluation has been proved an effective method to improve several aspects of goal-oriented query evaluation, including termination and complexity. Several "native" implementations of tabled evaluation have been developed which offer good performance, but many of them require significant changes to the underlying Prolog implementation, including the compiler and the abstract machine. Approaches based on program transformation, which tend to minimize changes to both the Prolog compiler and the abstract machine, have also been proposed, but they often result in lower efficiency. We explore some techniques aimed at combining the best of these worlds, i.e., developing an extensible implementation which requires minimal modifications to the compiler and the abstract machine, and with reasonably good performance. Our preliminary experiments indicate promising results. [ABSTRACT FROM AUTHOR]

We present the design and prototype implementation of the scheduling component in ArTCoP(architecture transparent control of parallelism), a novel run-time environment (RTE) for parallel execution of high-level languages. A key feature of ArTCoP is its support for deep process and memory hierarchies, shown in the scheduler by supporting light-weight threads. To realise a system with easily exchangeable components, the system defines a micro-kernel, providing basic infrastructure, such as garbage collection. All complex RTE operations, including the handling of parallelism, are implemented at a separate system level. By choosing Concurrent Haskell as high-level system language, we obtain a prototype in the form of an executable specification that is easier to maintain and more flexible than conventional RTEs. We demonstrate the flexibility of this approach by presenting implementations of a scheduler for light-weight threads in ArTCoP, based on GHC Version 6.6. [ABSTRACT FROM AUTHOR]

Packrat parsing is a newly popular technique for efficiently implementing recursive descent parsers. Packrat parsing avoids the potential exponential costs of recursive descent parsing with backtracking by ensuring that each production rule in the grammar is tested at most once against each position in the input stream. This paper argues that (a) packrat parsers can be trivially implemented using a combination of definite clause grammar rules and memoing, and that (b) packrat parsing may actually be significantly less efficient than plain recursive descent with backtracking, but (c) memoing the recognizers of just one or two nonterminals, selected in accordance with Amdahl's law, can sometimes yield speedups. We present experimental evidence to support these claims. [ABSTRACT FROM AUTHOR]

Pattern matching is a programming language feature for selecting a handler based on the structure of data while binding names to sub-structures. By combining selection and binding, pattern matching facilitates many common tasks such as date normalization, red-black tree manipulation, conversion of XML documents, or decoding TCP/IP packets. Matchete is a language extension to Java that unifies different approaches to pattern matching: regular expressions, structured term patterns, XPath, and bit-level patterns. Matchete naturally allows nesting of these different patterns to form composite patterns. We present the Matchete syntax and describe a prototype implementation. [ABSTRACT FROM AUTHOR]

We address the tension between software generality and performance in the domain of simulations based on Monte-Carlo methods. We simultaneously achieve generality and high performance by a novel development methodology and software architecture centred around the concept of a specialising simulator generator. Our approach combines and extends methods from functional programming, generative programming, partial evaluation, and runtime code generation. We also show how to generate parallelised simulators. We evaluated our approach by implementing a simulator for advanced forms of polymerisation kinetics. We achieved unprecedented performance, making Monte-Carlo methods practically useful in an area that was previously dominated by deterministic PDE solvers. This is of high practical relevance, as Monte-Carlo simulations can provide detailed microscopic information that cannot be obtained with deterministic solvers. [ABSTRACT FROM AUTHOR]

Domain-specific languages facilitate solving problems in a targeted domain by providing features particular to the domain. Declarative domain-specific languages have the additional benefit that users specify what something means rather than how to do something. As a result, the language compiler is free to choose the best implementation strategies and to generate multiple artifacts from a single description. pads/ml is a declarative data description language designed to facilitate ad hoc data management. From a single description, the compiler generates a myriad of artifacts, including data structures for the in-memory representation of the data and parsers and printers. In this paper, we describe a new generic programming infrastructure for pads/ml that allows third-party developers to define additional useful artifacts without modifying the compiler. We report on two case studies that use this infrastructure. In the first, we build a version of padx for pads/ml, allowing any data source with a pads/ml description to be queried as if it were xml. In the second, we extend Harmony with the ability to synchronize any data with a pads/ml description. [ABSTRACT FROM AUTHOR]

Unification, one of the key processes underlying logic programming (LP), provides a powerful mechanism for assembling and disassembling structures, lists in particular, by matching patterns. In recent work, we showed how spreadsheets can be enhanced by adding a visual form of LP in which lists, the fundamental structures of LP, are replaced by rectangular arrays, the fundamental structures of spreadsheets. The benefits include enhanced programmability and a way to specify high level templates for spreadsheet structures. Here, we focus on the structure of arrays, and describe the array unification algorithm underlying our current implementation. [ABSTRACT FROM AUTHOR]

Declarative authorization languages promise to simplify the administration of access control systems by allowing the authorization policy to be factored out of the implementation of the resource guard. However, writing a correct policy is an error-prone task by itself, and little attention has been given to tools and techniques facilitating the analysis of complex policies, especially in the context of access denials. We propose the use of abduction for policy analysis, for explaining access denials and for automated delegation. We show how a deductive policy evaluation algorithm can be conservatively extended to perform abduction on Datalog-based authorization policies, and present soundness, completeness and termination results. [ABSTRACT FROM AUTHOR]

Nonlinear constraint satisfaction or optimisation models need to be reduced to equivalent linear forms before they can be solved by (Integer) Linear Programming solvers. A choice of linearisation methods exist. There are generic linearisations and constraint-specific, user-defined linearisations. Hence a model reformulation system needs to be flexible and open to allow complex and novel linearisations to be specified. In this paper we show how the declarative model reformulation system Cadmium can be used to effectively transform constraint problems to different linearisations, allowing easy exploration of linearisation possibilities. [ABSTRACT FROM AUTHOR]

When BDDs are used for propagation in a constraint solver with nogood recording, it is necessary to find a small subset of a given set of variable assignments that is enough for a BDD to imply a new variable assignment. We show that the task of finding such a minimum subset is NP-complete by reduction from the hitting set problem. We present a new algorithm for finding such a minimal subset, which runs in time linear in the size of the BDD representation. In our experiments, the new method is up to ten times faster than the previous method, thereby reducing the solution time by even more than 80%. Due to linear time complexity the new method is able to scale well. [ABSTRACT FROM AUTHOR]

In this paper we discuss an approach to support declarative reasoning over aspect-oriented (AO) programs, adopting AspectJ as a representative technology. The approach is based on the transformation of source code into a set of facts and rules, stored into a Prolog database. Declarative analysis allows us to extract complex information through its rich and expressive syntax. Our approach has two contributions. First, it aims to improve the comprehension of AspectJ programs. The type of knowledge provided is categorized in three main groups: i) general knowledge, ii) bad smells, and iii) quality metrics. The second contribution is the provision of dependency analysis of AspectJ programs. To that end, we identify dependencies in aspect-oriented programs, and translate them into Prolog rules. Expected beneficiaries of our approach include system maintainers who can obtain comprehension and perform dependency analysis through querying the Prolog database during the change planning stage of system evolution. [ABSTRACT FROM AUTHOR]

This paper presents our feedback from the study on the use of Objective Caml for safety-critical software development tools implementation. As a result, Objective Caml is now used for the new Scade$^{\mathtt{TM}}$ certified embedded-code generator. The requirements for tools implementation are less strict than those for the embedded code itself. However, they are still quite demanding and linked to imperative languages properties, which are usually used for this kind of development. The use of Objective Caml is outstanding: firstly for its high level features (functional language of higher order, parametric polymorphism, pattern matching), secondly for its low level mechanisms needed by the runtime system (GC, exceptions). In order to develop the tools to check the safety-critical software development rules, it is necessary to reinterpret them for this language, and then to adapt Objective Caml so that it satisfies them. Thus, we propose a language restriction and a simplified runtime library in order that we can define and measure the coverage of a program written in Objective Caml according to the MC/DC criteria. Then we can look forward to seeing this kind of languages spread out the industrial environment, while raising the abstraction level in the conception and implementation of tools for certified programs production. [ABSTRACT FROM AUTHOR]

Overloading is a technique to accommodate more number of users than the spreading factor N. This is an efficient way to increase the number of users in a fixed bandwidth, which is of practical interest to mobile system operators. In this paper we have reviewed the different overloading schemes proposed in the literature for the DS-CDMA systems. The performance of an Orthogonal/Orthogonal (O/O) overloading scheme, using two sets of orthogonal codes (O/s-O) has been evaluated. Iterative multistage detector (IMSD) is used to reduce the multiple access interference between the users of two sets. The BER performance of IMSD is evaluated with hard and soft decisions functions using Monte-Carlo simulations. It is found that, this scheme provides 19% and 11% channel overloading for synchronous DS-CDMA system in an AWGN channel, with a SNR degradation of less than 0.5 dB at a BER of 10− 5 compared to single user bound for N=16 and 64 respectively. [ABSTRACT FROM AUTHOR]

This paper presents a novel approach to processing continuous aggregate queries in sensor networks, which lifts the assumption of tree-based routing. Given a query workload and a special-purpose gateway node where results are expected, the query optimizer exploits query correlations in order to generate an energy-efficient distributed evaluation plan. The proposed optimization algorithms identify common query sub-aggregates, and propose common routing structures to share the sub-aggregates at an early stage. Moreover, they avoid routing sub-aggregates of the same query through long-disjoint paths, thus further reducing the communication cost of result propagation. The proposed algorithms are fully-distributed, and are shown to offer significant communication savings compared to existing tree-based approaches. A thorough experimental evaluation shows the benefits of the proposed techniques for a variety of query workloads and network topologies. [ABSTRACT FROM AUTHOR]

The topology of a MANET is maintained enduring transmission failures by suitably selecting multiple coordinators among the nodes constituting the MANET. The basic philosophy behind the algorithm is to isolate four coordinators based on positional data. Once elected, they are entrusted with the responsibility to emit signals of different frequencies while the other nodes individually decide the logic they need to follow in order to maintain the topology, thereby eliminating the need for routing. The algorithm is going to be formulated in such a way, that the entire network is going to move in one direction while each node can move freely. As far as our knowledge goes, we are the first ones to conceive the concept of multiple coordinators. The simulation results prove the efficacy of the scheme in topology maintenance. [ABSTRACT FROM AUTHOR]

An interesting and useful application in ad hoc wireless mobile community is searching and locating information in a distributed and decentralized manner. Locating and collecting information in a highly dynamic network while minimizing the consumption of scarce resources such as bandwidth and energy is the main challenge in this domain. In this paper we present a radically new location aided content searching mechanism that can determine the location and the content as well of the information searched that incurs minimum overhead. Here we have used a stable geographically clustered network that enables us to distribute the search message in a location-aided manner. In disastrous scenarios the access of emergency information, services or resources is considered to be of special interest to the user groups. Mobile terminals are there to gather information from sensors and other sources. The location-Aided content searching mechanism discussed here is concerned with efficiently delivering this information together with the geographical location of the information to the person in the field on need basis. The mobility tolerant clusters structures are used to lower the proactive traffic while minimizing the query cost. We present results from detailed simulations that demonstrate the efficiency of our mechanism and discuss the scalability of this model to larger networks. [ABSTRACT FROM AUTHOR]

We study routing algorithms for three-dimensional ad hoc networks that guarantee delivery and are k-local, i.e., each intermediate node v's routing decision only depends on knowledge of the labels of the source and destination nodes, of the subgraph induced by nodes within distance k of v, and of the neighbour of v from which the message was received. We model a three-dimensional ad hoc network by a unit ball graph, where nodes are points in ℝ3, and nodes u and v are joined by an edge if and only if the distance between u and v is at most one. The question of whether there is a simple local routing algorithm that guarantees delivery in unit ball graphs has been open for some time. In this paper, we answer this question in the negative: we show that for any fixed k, there can be no k-local routing algorithm that guarantees delivery on all unit ball graphs. This result is in contrast with the two-dimensional case, where 1-local routing algorithms that guarantee delivery are known. Specifically, we show that guaranteed delivery is possible if the nodes of the unit ball graph are contained in a slab of thickness $1/\sqrt{2}$. However, there is no k-local routing algorithm that guarantees delivery for the class of unit ball graphs contained in thicker slabs, i.e., slabs of thickness $1/\sqrt{2} + \epsilon$ for some ε> 0. The algorithm for routing in thin slabs derives from a transformation of unit ball graphs contained in thin slabs into quasi unit disc graphs, which yields a 2-local routing algorithm. We also show several results that further elaborate on the relationship between these two classes of graphs. [ABSTRACT FROM AUTHOR]

Motivated by reducing communication overhead and prolonging network lifetime in wireless ad hoc and sensor networks, we propose an energy-efficient dominating tree construction (EEDTC) algorithm to construct a dominating tree that can serve as a communication backbone in wireless infrastructures. The algorithm has a theoretical approximation factor of at most 9, and has O(n) message complexity and O(n) time complexity. Due to the low message complexity, EEDTC performs well on energy consumption. The energy-aware ranking technique introduced can also balance energy consumption in the network, and hence reduce the probability of network failures caused by energy depletion of backbone nodes. [ABSTRACT FROM AUTHOR]

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modify k arbitrary locations, such as k-read-modify-write (kRMW). Aiming to increase concurrency in order to exploit the parallelism offered by today's multi-core and multiprocessing architectures, we propose a software implementation of kRMW that efficiently breaks apart delay chains. Our algorithm ensures that two operations delay each other only if they are within distance O(k) in the conflict graph, dynamically induced by the operations' data items. The algorithm uses double compare-and-swap (DCAS). When DCAS is not supported by the architecture, the algorithm of Attiya and Dagan [3] can be used to replace DCAS with (unary) CAS, with only a slight increase in the interference among operations. [ABSTRACT FROM AUTHOR]