Bibliography

Scalability is one of the toughest challenges in ad hoc networking. Recent work outlines theoretical bounds on how well routing protocols could scale in this environment. However, none of the popular routing solutions really scales to large networks, by coming close enough to these bounds. In this paper, we study the case of link state routing and OLSR, one of the strongest candidate for standardization. We analyze how these bounds are not reached in this case, and we study how much the scalability is enhanced with the use of Fish Eye techniques in addition to the link state routing framework. We show that with this enhancement, the theoretical scalability bounds are reached.

Keywords: Ad hoc, mobile, network, routing, scalability

Protocols that are to be employed in the context of the Internet of Things (IoT) have to meet a wide variety of application-specific requirements. In this paper, we reflect on recent experiences, gained from several real-world deployments in which we have participated, which use low power, embedded networking devices. We discuss the lessons learned from these deployments, with an emphasis on questions affecting the IP layer and, in particular, on the routing protocols for these networks. We point out open issues and possible directions of future work for such routing protocols.

Keywords: Routing, Standardization

Protocols that are to be employed in the context of the Internet of Things (IoT) have to meet a wide variety of application-specific requirements. In this paper, we reflect on recent experiences, gained from several real-world deployments in which we have participated, which use low power, embedded networking devices. We discuss the lessons learned from these deployments, with an emphasis on questions affecting the IP layer and, in particular, on the routing protocols for these networks. We point out open issues and possible directions of future work for such routing protocols.

Keywords: Routing, Standardization

This paper studies task assignment in a network of resource constrained computing platforms (called microservers). A task is an abstraction of a computational agent or data that is hosted by the microservers. For example, in an object tracking scenario, a task represents a mobile tracking agent, such as a vehicle location update computation, that runs on microservers, which can receive sensor data pertaining to the object of interest. Due to object motion, the microservers that can observe a particular object change over time and there is overhead involved in migrating tasks among microservers. Furthermore, communication, processing, or memory constraints, allow a microserver to only serve a limited number of objects at the same time. Our overall goal is to assign tasks to microservers so as to minimize the number of migrations, and thus be kinetically stable, while guaranteeing that as many tasks as possible are monitored at all times. When the task trajectories are known in advance, we show that this problem is NP-complete (even over just two time steps), has an integrality gap of at least 2, and can be solved optimally in polynomial time if we allow tasks to be assigned fractionally. When only probabilistic information about future movement of the tasks is known, we propose two algorithms: a multi-commodity flow based algorithm and a maximum matching algorithm. We use simulations to compare the performance of these algorithms against the optimum task allocation strategy.

Keywords: Service placement

Intrusion detection is a surveillance problem of practical import that is well suited to wireless sensor networks. In this paper, we study the application of sensor networks to the intrusion detection problem and the related problems of classifying and tracking targets. Our approach is based on a dense, distributed, wireless network of multi-modal resource-poor sensors combined into loosely coherent sensor arrays that perform in situ detection, estimation, compression, and exfiltration. We ground our study in the context of a security scenario called “A Line in the Sand” and accordingly define the target, system, environment, and fault models. Based on the performance requirements of the scenario and the sensing, communication, energy, and computation ability of the sensor network, we explore the design space of sensors, signal processing algorithms, communications, networking, and middleware services. We introduce the influence field, which can be estimated from a network of binary sensors, as the basis for a novel classifier. A contribution of our work is that we do not assume a reliable network; on the contrary, we quantitatively analyze the effects of network unreliability on application performance. Our work includes multiple experimental deployments of over 90 sensor nodes at MacDill Air Force Base in Tampa, FL, as well as other field experiments of comparable scale. Based on these experiences, we identify a set of key lessons and articulate a few of the challenges facing extreme scaling to tens or hundreds of thousands of sensor nodes.

Keywords: Wireless sensor networks, Smart dust, Target classification and tracking, Reliability, Stabilization

Wireless Integrated Network Sensors (WINS) now provide a new monitoring and control capability for transportation, manufacturing, health care, environmental monitoring, and safety and security. WINS combine sensing, signal processing, decision capability, and wireless networking capability in a compact, low power system. WINS systems combine microsensor technology with low power sensor interface, signal processing, and RF communication circuits. The need for low cost presents engineering challenges for implementation of these systems in conventional digital CMOS technology. This paper describes micropower data converter, digital signal processing systems, and weak inversion CMOS RF circuits. The digital signal processing system relies on a continuously operating spectrum analyzer. Finally, the weak inversion CMOS RF systems are designed to exploit the properties of high-Q inductors to enable low power operation. This paper reviews system architecture and low power circuits for WINS.

Keywords: Wireless Sensor Networks

We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.

Keywords: Service placement

In this paper we consider distributed computing systems which exhibit dynamism due to their scale or inherent design, e.g. inclusion of mobile components. Prominent examples are Grids - large networks where computing resources can transparently be shared and utilized for solving complex compute tasks.
One of the hard problems in this domain is the resource allocation problem and the related service placement problem. In this paper we discuss distributed and adaptive resource allocation algorithms performed in such dynamic systems. These algorithms assume that no global information about resource availability and service demand can be provided due to the scale and dynamism.
Interesting aspects of our approaches are the capabilities of self-organization and fault-tolerance. We analyze and “factor-out” these capabilities, making them also usable in the setting of other dynamic distributed systems, for example in mobile computing.

Keywords: Service placement

We consider a variant of the facility location problem with additional interference constraints of the form “not too many facilities can be close to a user”. These constraints arise naturally in the placement of wireless access points or base stations. We model the interference in several (increasingly complex) ways, and show approximation algorithms for them. We also consider the assignment of frequencies to the facilities with the motivation that two facilities with different frequencies do not interfere. This leads to an interesting coloring variant of facility location. Our techniques show that interference constraints are not too hard to enforce in rounding schemes that preserve locality.

Keywords: Service placement

This paper is concerned with reducing communication costs when executing distributed user tasks in a sensor network. We take a service-oriented abstraction of sensor networks, where a user task is composed of a set of data processing modules (called services) with dependencies. Communications in sensor networks consume significant energy and introduce uncertainty in data fidelity due to high bit error rate. These constraints are abstracted as costs on the communication graph. The goal is to place the services within the sensor network so that the communication cost in performing the task is minimized. In addition, since the lifetime of a node, the quality of network links, and the composition of the service graph may change over time, the quality of the placement must be maintained in the face of these dynamics. In this paper, we take a fresh look at what is generally considered a simple but poor performance approach for service placement, namely the greedy algorithm. We prove that a modified greedy algorithm is guaranteed to have cost at most 8 times the optimum placement. In fact, the guarantee is even stronger if there is a high degree of data reduction in the service graph. The advantage of the greedy placement strategy is that when there are local changes in the service graph or when a hosting node fails, the repair only affects the placement of services that depend on the changes. Simulations suggest that in practice the greedy algorithm finds a low cost placement. Furthermore, the cost of repairing a greedy placement decreases rapidly as a function of the proximity of the services to be aggregated.

Keywords: Service placement

Keywords: Service placement

Recent advancement in wireless communications and electronics has enabled the development of low-cost sensor networks. The sensor networks can be used for various application areas (e.g., health, military, home). For different application areas, there are different technical issues that researchers are currently resolving. The current state of the art of sensor networks is captured in this article, where solutions are discussed under their related protocol stack layer sections. This article also points out the open research issues and intends to spark new interests and developments in this field.

Keywords: Wireless Sensor Networks, Survey

This paper is motivated by the concern of a multi-service network provider who plans to offer quality of service guarantees to users. A bandwidth broker acts as the resource manager for each network provider. Neighboring bandwidth brokers communicate with each other to establish inter-domain resource reservation agreements. Conventional approaches for resource allocation rely on pre-determined traffic characteristics. If allocation follows the traffic demand very tightly, the resource usage is efficient but leads to frequent modifications of the reservations. This would lead to increased inter-bandwidth-broker signaling in order to propagate the changes to all the concerned networks. Contrarily, if large cushions are allowed in the reservations, the modifications are far spaced in time but the resource usage becomes highly inefficient. In this paper, a new scheme for estimating the traffic on an inter-domain link and forecasting its capacity requirement, based on a measurement of the current usage, is proposed. The method allows an efficient resource utilization while keeping the number of reservation modifications to low values.

Keywords: Bandwidth broker, Resource allocation, Resource provisioning, Capacity reservation, Traffic estimation, Bandwidth usage

Medium access control for wireless sensor networks has been a very active research area for the past couple of years. The sensor networks literature presents an alphabet soup of medium access control protocols with almost all of the works focusing only on energy efficiency. There is much more innovative work to be done at the MAC layer, but current efforts are not addressing the hard unsolved problems. Majority of the works appearing in the literature are “least publishable incremental improvements” over the popular S-MAC [1] protocol. In this paper we present research directions for future medium access research. We identify some open issues and discuss possible solutions.

Keywords: Wireless Sensor Networks, Medium Access Control

Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. The integration of WMNs with other networks such as the Internet, cellular, IEEE 802.11, IEEE 802.15, IEEE 802.16, sensor networks, etc., can be accomplished through the gateway and bridging functions in the mesh routers. Mesh clients can be either stationary or mobile, and can form a client mesh network among themselves and with mesh routers. WMNs are anticipated to resolve the limitations and to significantly improve the performance of ad hoc networks, wireless local area networks (WLANs), wireless personal area networks (WPANs), and wireless metropolitan area networks (WMANs). They are undergoing rapid progress and inspiring numerous deployments. WMNs will deliver wireless services for a large variety of applications in personal, local, campus, and metropolitan areas. Despite recent advances in wireless mesh networking, many research challenges remain in all protocol layers. This paper presents a detailed study on recent advances and open research issues in WMNs. System architectures and applications of WMNs are described, followed by discussing the critical factors influencing protocol design. Theoretical network capacity and the state-of-the-art protocols for WMNs are explored with an objective to point out a number of open research issues. Finally, testbeds, industrial practice, and current standard activities related to WMNs are highlighted.

Keywords: Wireless Mesh Networks, Ad Hoc Networks, Wireless Sensor Networks, Medium Access Control, Routing Protocol, Transport Protocol, Scalability, Security, Power Management and Control, Timing Synchronization

Keywords: Software Engineering

With the convergence of wireless communication and IP-based networking technologies, future IP-based wireless networks are expected to support real-time multimedia. IP services over wireless networks (e.g. wireless access to Internet) enhance the mobility and flexibility of traditional IP network users. Wireless networks extend the current IP service infrastructure to a mix of transmission media, bandwidth, costs, coverage, and service agreements, requiring enhancements to the IP protocol layers in wireless networks. Furthermore, QoS provisioning is required at various layers of the IP protocol stack to guarantee different types of service requests, giving rise to issues related to cross-layer design methodology. This paper reviews issues and prevailing solutions to performance enhancements and QoS provisioning for IP services over mobile wireless networks from a layered view.

Keywords: Quality of service (QoS), Mobility, Wireless, TCP/IP, Middleware

In-network query processing is critical for reducing network traffic when accessing and manipulating sensor data. It requires placing a tree of query operators such as filters and aggregations but also correlations onto sensor nodes in order to minimize the amount of data transmitted in the network. In this paper, we show that this problem is a variant of the task assignment problem for which polynomial algorithms have been developed. These algorithms are however centralized and cannot be used in a sensor network. We describe an adaptive and decentralized algorithm that progressively refines the placement of operators by walking through neighbor nodes. Simulation results illustrate the potential benefits of our approach. They also show that our placement strategy can achieve near optimal placement onto various graph topologies despite the risks of local minima.

Keywords: Service placement

Keywords: Expert Systems, Overview

Capacity improvement is one of the principal challenges in wireless networking. We present a link-layer protocol called Slotted Seeded Channel Hopping, or SSCH, that increases the capacity of an IEEE 802.11 network by utilizing frequency diversity. SSCH can be implemented in software over an IEEE 802.11-compliant wireless card. Each node using SSCH switches across channels in such a manner that nodes desiring to communicate overlap, while disjoint communications mostly do not overlap, and hence do not interfere with each other. To achieve this, SSCH uses a novel scheme for distributed rendezvous and synchronization. Simulation results show that SSCH significantly increases network capacity in several multi-hop and single-hop wireless networking scenarios.

Keywords: Ad-hoc wireless networks, Channel assignment, Frequency diversity, Pseudo-randomness, Scheduling, Medium access control

There is an emerging market interest in service provisioning over dense Mobile Ad-hoc NETworks (MANETs), i.e., limited spatial regions, such as shopping malls, airports, and university campuses, where a high number of mobile wireless peers can autonomously cooperate without exploiting statically deployed network infrastructures. We claim that it is possible to exploit the high node population of dense MANETs to simplify the replication of common interest resources, in order to increase availability notwithstanding unpredictable node exits from dense regions. To this purpose, we have developed the REDMAN middleware that supports the lightweight and dense MANET-specific management, dissemination and retrieval of replicas of data/service components. In particular, the paper focuses on the presentation of different solutions for replica retrieval and for dissemination of replica placement information. We have compared and quantitatively evaluated the presented solutions by considering their ability to retrieve available replicas and their communication overhead. The original SID solution has demonstrated to outperform the others in dense MANETs and has been integrated in the REDMAN prototype.

Keywords: Service placement

The increasing diffusion of wireless-enabled portable devices is pushing towards service provisioning over dense Mobile Ad-hoc NETworks (MANETs), i.e., limited spatial regions, such as shopping malls, railway stations and airports, where a high number of mobile wireless peers autonomously cooperate, without the need for statically deployed network infrastructures. Dense MANET deployment scenarios can take advantage of high node population to replicate common-interest resources to increase their availability, by overcoming the unpredictable node exit from the dense region. The paper proposes a lightweight middleware, called REDMAN, to manage, retrieve and disseminate replicas of data/service components made available by cooperating nodes in a dense MANET. In particular, the paper focuses on the REDMAN original solutions both to determine the nodes belonging to dense MANETs without exploiting any positioning system and to dynamically elect a suitable replica manager node in charge of enforcing the desired resource replication degree in a lazy consistent way. Experimental results show that REDMAN solutions are lightweight and effective in dense MANET scenarios with almost constant node density and even high node mobility.

Keywords: Service placement

The mass market of wireless devices is pushing towards service provisioning over dense Mobile Ad-hoc NETworks (MANETs), i.e., limited spatial regions, such as university campuses, airports and shopping malls, where many mobile wireless peers autonomously cooperate, without the need of statically deployed support infrastructures. Dense MANETs can take advantage of high node population to replicate resources of common interest to increase their availability overcoming unpredictable node movements. The paper proposes a lightweight application-level middleware, called REDMAN, to manage, retrieve and disseminate replicas of data and service components transparently from the point of view of service developers, thus facilitating the realization of scalable distributed applications for dense MANETs. REDMAN proposes novel lightweight solutions, specific for and effective in dense MANETs, to determine dense region boundaries, to perform resource cloning/distribution/retrieval, and to approximately maintain the desired resource replication degree.

Keywords: Service placement

The spread of wireless portable devices is pushing towards service provisioning over dense Mobile Ad-hoc NETworks (MANETs), i.e., limited spatial regions, such as shopping malls and airports, where a high number of mobile peers can autonomously cooperate without a statically deployed network infrastructure. The paper proposes the REDMAN middleware to manage, retrieve, and disseminate replicas of data/service components to cooperating nodes in a dense MANET. The guideline is to exploit high node population to enable optimistic lightweight resource replication capable of tolerating node exits/failures. REDMAN adopts original approximated solutions, specifically designed for dense MANET, that have demonstrated good scalability and limited overhead for dense MANET configuration (node identification and manager election), for replica distribution/retrieval, and for lazily-consistent replica degree maintenance.

Keywords: Optimistic Replication, Middleware, Mobile Ad Hoc Networks, IEEE 802.11

Thirty years after its creation, C remains one of the most widely used systems programming languages. Unfortunately, the power of C has become a liability for large systems projects, which are now focusing on security and reliability. Modern languages and static analyses provide an opportunity to improve the quality of systems software, and yet adoption of these tools has been slow.
To address this problem, we propose a new language called Ivy that has an evolutionary path from C. The mechanism for this evolutionary path is a system of extensions and refactorings: extensions augment the language with new features, and refactorings assist the programmer in updating their code to use these new features. Extensions and refactorings have a wide variety of applications, from enforcing memory safety to detecting user/kernel pointer errors. We also demonstrate Macroscope, a tool we have built to enable refactoring of existing C code.

Keywords: Programming languages, C

Keywords: Routing

Network researchers must test Internet protocols under varied conditions to determine whether they are robust and reliable. The Virtual Inter-Network Testbed (VINT) project has enhanced its network simulator and related software to provide several practical innovations that broaden the conditions under which researchers can evaluate network protocols.

Keywords: Simulation, ns-2

Keywords: Routing

This paper investigates two fundamental characteristics of a wireless multihop network: its minimum node degree and its k-connectivity. Both topology attributes depend on the spatial distribution of the nodes and their transmission range. Using typical modeling assumptions - a random uniform distribution of the nodes and a simple link model - we derive an analytical expression that enables the determination of the required range r0 that creates, for a given node density p, an almost surely k-connected network. Equivalently, if the maximum r0 of the nodes is given, we can find out how many nodes are needed to cover a certain area with a k-connected network. We also investigate these questions by various simulations and thereby verify our analytical expressions.
Finally, the impact of mobility is discussed. The results of this paper are of practical value for researchers in this area, e.g., if they set the parameters in a network-level simulation of a mobile ad hoc network or if they design a wireless sensor network.

Keywords: Wireless Sensor Networks, Node Degree, Coverage, Deployment Planning

Keywords: Wireless Sensor Networks, Middleware

Public spaces such as airports, railway stations or stadiums bring together large numbers of people on a quite limited space to use a security-sensitive infrastructure. Electronic security systems may help to provide better and faster security, as well as safety for the general public. Application scenarios may include intrusion detection and monitoring of large crowds in order to provide guidance in case of unexpected events (e.g., a mass panic). However, current security systems used within the public infrastructure are typically expensive, non-trivial to deploy, difficult to operate and maintain, prone to malfunction due to individual component failures, and generally lack citizen privacy-friendliness. The advent of novel, large-scale distributed security systems based on wireless, lightweight sensors may enhance security and safety in public spaces. In this realm, SAFEST is a project aiming at analyzing the social context of area surveillance and developing a system that can fulfill this task, both in terms of technology as well as acceptance by the general public. The targeted system will operate in a distributed way, collect anonymized data, securely transfer this data to a central location for evaluation, and – if necessary – notify the operator or issue alerts directly to the general public. Work on the technical aspects of the system is accompanied by social studies investigating the individual perception of risk and the methods for reaching public acceptance of the technical solutions.

Keywords: Event Detection

Wireless mesh networks are in the focus of research for more than a decade. After a short simulation based research period, several testbeds have been set up for the study of particular research topics. As wireless mesh networks are entering a phase of wide-spread commercial application, novel approaches for holistic research are required. In this paper we review the trends, advances, and challenges in experimentally driven wireless mesh network research. The evolution of the experimentation facilities is elaborated by distinguishing three generations of testbeds. Based on the review and the current trends of research, open issues are discussed. We introduce the Distributed Embedded Systems Testbed (DES-Testbed) at Freie Universität Berlin as an example of the current third generation. Further on, its features are elaborated and requirements for future holistic research of wireless networks are discussed.

Keywords: DES-Testbed

Wireless ad hoc sensor networks (WASNs) are in need of the study of useful applications that will help the researchers view them as distributed physically coupled systems, a collective that estimates the physical environment, and not just energy-limited ad hoc networks. We develop this perspective using a large and interesting class of WASN applications called aggregation applications. In particular, we consider the challenging periodic aggregation problem where the WASN provides the user with periodic estimates of the environment, as opposed to simpler and previously studied snapshot aggregation problems. In periodic aggregation our approach allows the spatial-temporal correlation among values sensed at the various nodes to be exploited towards energy-efficient estimation of the aggregated value of interest. Our approach also creates a system level energy vs. accuracy knob whereby the more the estimation error that the user can tolerate, the less is the energy consumed. We present a distributed estimation algorithm that can be applied to explore the energy-accuracy subspace for a sub-class of periodic aggregation problems, and present extensive simulation results that validate our approach. The resulting algorithm, apart from being more flexible in the energy-accuracy subspace and more robust, can also bring considerable energy savings for a typical accuracy requirement (five -fold decrease in energy consumption for 5% estimation error) compared to repeated snapshot aggregations.

Keywords: sensor networks, aggragation applications, distributed estimation, energy vs. accuracy trade-off

An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. Due to the limited transmission range of wireless network interfaces, multiple network “hops” may be needed for one node to exchange data with another across the network. In recent years, a variety of new routing protocols targeted specifically at this environment have been developed, but little performance information on each protocol and no realistic performance comparison between them is available. This paper presents the results of a detailed packet-level simulation comparing four multi-hop wireless ad hoc network routing protocols that cover a range of design choices: DSDV, TORA, DSR, and AODV. We have extended the ns-2 network simulator to accurately model the MAC and physical-layer behavior of the IEEE 802.11 wireless LAN standard, including a realistic wireless transmission channel model, and present the results of simulations of networks of 50 mobile nodes.

Keywords: Wireless Sensor Networks, Simulation, Routing

Keywords: Routing

Based on a review of some actual expert-system projects, guidelines are proposed for choosing appropriate applications and managing the development process.

Keywords: Expert Systems, Case Studies

In this paper we present a modular and extensible visualization framework for wireless sensor networks. These networks have typically no means of visualizing their internal state, sensor readings or computational results. Visualization is therefore a key issue to develop and operate these networks. Data emitted by individual sensor nodes is collected by gateway software running on a machine in the sensor network. It is then passed on via TCP/IP to the visualization software on a potentially remote machine. Visualization plug-ins can register to different data types, and visualize the information using a flexible multi-layer mechanism that renders the information on a canvas. Developers can easily adapt existing or develop new custom tailored plug-ins for their specific visualization needs and applications.

Keywords: Sensor networks, smart dust, visualization, debugging, embedded computing

With the raising number of Internet services, automatic service discovery will be a very important feature in future network scenarios, e.g., in self organizing ad hoc networks. With service discovery, devices may automatically discover network services including their properties, and services may advertise their existence in a dynamic way. This paper compares some well–known service discovery protocols currently under development, namely the Service Location Protocol (SLP), Jini, Salutation, Universal Plug and Play (UPnP), and the Bluetooth Service Discovery Protocol (SDP). Application scenarios for service discovery are presented, which emphasize the importance of these protocols. We also present our SLP beta implementation, which includes the fundamental protocol transactions and demonstrates IP service discovery in action.

Keywords: Service discovery, service location protocol, SLP, IP autoconfiguration, ad hoc communication

A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.

Keywords: Simulation, Algorithms

The highly distributed infrastructure provided by sensor networks supports fundamentally new ways of designing surveillance systems. In this paper, we discuss sensor networks for target classification and tracking. Our formulation is anchored on location-aware data routing to conserve system resources, such as energy and bandwidth. Distributed classification algorithms exploit signals from multiple nodes in several modalities and rely on prior statistical information about target classes. Associating data to tracks becomes simpler in a distributed environment, at the cost of global consistency. It may be possible to filter clutter from the system by embedding higher level reasoning in the distributed system. Results and insights from a recent field test at 29 Palms Marine Training Center are provided to highlight challenges in sensor networks.

Keywords: Sensor Networks, Classification, Tracking, Collaborative Signal Processing, Location Aware Routing

Wireless sensor networks (WSN) are in a transition from research to real world applications. Robust and efficient hardware platforms are needed. These have to offer sufficient processing power and memory while retaining energy efficiency. In this technical report we present the newest ScatterWeb hardware platform that fits the needs of research and prototyping applications of the near future.

Keywords: Wireless Sensor Networks (WSN), Embedded Systems, ScatterWeb Platform

Keywords: QoS, Service Placement

This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput.
This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29-node 802.11b test-bed demonstrate the poor performance of minimum hop-count, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.

Keywords: Routing, ETX

This paper presents Virtual Ring Routing (VRR), a new network routing protocol that occupies a unique point in the design space. VRR is inspired by overlay routing algorithms in Distributed Hash Tables (DHTs) but it does not rely on an underlying network routing protocol. It is implemented directly on top of the link layer. VRR provides both traditional point-to-point network routing and DHT routing to the node responsible for a hash table key.
VRR can be used with any link layer technology but this paper describes a design and several implementations of VRR that are tuned for wireless networks. We evaluate the performance of VRR using simulations and measurements from a sensor network and an 802.11a testbed. The experimental results show that VRR provides robust performance across a wide range of environments and workloads. It performs comparably to, or better than, the best wireless routing protocol in each experiment. VRR performs well because of its unique features: it does not require network flooding or translation between fixed identifiers and location-dependent addresses.

Keywords: Network Routing, Distributed Hash Table, Wireless

Keywords: Channel Assignment

Keywords: Service placement

In this article we show that, although pure general-purpose MANET (mobile ad hoc networks) does not yet exist in the real world, the multihop ad hoc networking paradigm was successfully applied in several classes of networks that are penetrating the mass market. We present as examples mesh, opportunistic, vehicular, and sensor networks, where the multi-hop ad hoc paradigm is applied in a pragmatic way to extend the Internet and/or to support welldefined application requirements. We contrast these successful areas of ad hoc networking to the lack of impact of pure general-purpose MANET, demonstrating how a more pragmatic approach is a winner.

Keywords: MANET, State-of-the-Art

This article reviews the basic principles behind mobile ad hoc networks (MANET) and critically discusses approximately ten years of research in this field. We summarize the main achievements and point out the limits of MANET research. This research was conducted under the assumption that the networks mainly will be used for large-scale general consumer applications, and nodes would be ubiquitous, thus reasonably dense and active. Both assumptions do not reflect reality and certainly would not be true in an initial phase of deployment. A lack of realism regarding the objective of MANET coupled with a lack of realism during the design of MANET are the main causes of MANET running a high risk of failure.

Keywords: MANET, State-of-the-Art

In the rapidly developing field of sensor networks, bridging the gap between the applications and the hardware presents a major challenge. Although middleware is one solution, it must be specialized to the qualities of sensor networks, especially energy consumption. The work presented here provides two contributions: a new operational setting for sensor networks and a middleware for easing software development in this setting. The operational setting we target removes the usual assumption of a central collection point for sensor data. Instead the sensors are sparsely distributed in an environment, not necessarily able to communicate among themselves, and a set of clients move through space accessing the data of sensors nearby, yielding a system which naturally provides context relevant information to client applications. We further assume the clients are wirelessly networked and share locally accessed data. This scenario is relevant, for example, when relief workers access the information in their zone and share this information with other workers. Our second contribution, the middleware itself, is an extension of LIME, our earlier work on middleware for mobile ad hoc networks. The model makes sensor data available through a tuple space interface, providing the illusion of shared memory between applications and sensors. This paper presents both the model and the implementation of our middleware incorporated with the Crossbow Mote sensor platform.

Keywords: Wireless Sensor Networks, Middleware

Very large data centers are very expensive (servers, power/cooling, networking, physical plant.) Newer, geo-diverse, distributed or containerized designs offer a more economical alternative. We argue that a significant portion of cloud services are embarrassingly distributed - meaning there are high performance realizations that do not require massive internal communication among large server pools. We argue further that these embarrassingly distributed applications are a good match for realization in small distributed data center designs. We consider email delivery as an illustrative example. Geo-diversity in the design not only improves costs, scale and reliability, but also realizes advantages stemming from edge processing; in applications such as spam filtering, unwanted traffic can be blocked near the source to reduce transport costs.

Keywords: Embarrassingly Distributed, Economies of Scale, Spam, POPs (Points of Presence)

An approach efficiently and dynamically places services within a multi-node system when expanding or contracting services, that is, increasing and decreasing the number of instances that host a service. Service placement decisions are made in a way that accounts for performance and availability requirements of both the service being placed and other services.

Keywords: Service placement

Energy consumption in hosting Internet services is becoming a pressing issue as these services scale up. Dynamic server provisioning techniques are effective in turning off unnecessary servers to save energy. Such techniques, mostly studied for request-response services, face challenges in the context of connection servers that host a large number of long-lived TCP connections. In this paper, we characterize unique properties, performance, and power models of connection servers, based on a real data trace collected from the deployed Windows Live Messenger. Using the models, we design server provisioning and load dispatching algorithms and study subtle interactions between them. We show that our algorithms can save a significant amount of energy without sacrificing user experiences.

Keywords: Service placement

Keywords: Simulation accuracy

In this paper, we describe the Optimized Link State Routing Protocol (OLSR), a proactive routing protocol for Mobile Ad-hoc NETworks (MANETs). We evaluate its performance through exhaustive simulations using the Network Simulator 2 (ns2), and compare with other ad-hoc protocols, specifically the Ad-hoc On-Demand Distance Vector (AODV) routing protocol and the Dynamic Source Routing (DSR) protocol. We study the protocols under varying conditions (node mobility, network density) and with varying traffic (TCP, UDP, different number of connections/streams) to provide a qualitative assessment of the applicability of the protocols in different scenarios.

Keywords: Routing, Standardization

Keywords: Service Placement

Keywords: Simulation

Keywords: Service placement

The deployment of wireless applications or protocols in the context of Mobile Ad-hoc NETworks (MANETs), often requires to step through a simulation phase. For the results of the simulation to be meaningful, it is important that the model on which is based the simulator matches as closely as possible the reality. In this paper we present the simulation results of a straightforward algorithm using several popular simulators (OPNET Modeler, NS-2, GloMoSim). The results tend to show that significant divergences exist between the simulators. This can be explained partly by the mismatching of the modelisation of each simulator and also by the different levels of detail provided to implement and configure the simulated scenarios.

Keywords: Mobile Ad-Hoc Networks, MANET, Flooding, Simulations, Simulators, Accuracy, OPNET, NS-2, GloMoSim

In this paper, we assess the state of the art of Quality of Services (QoS) support in wireless sensor networks (WSNs). Unlike traditional end-to-end multimedia applications, many non-end-to-end mission-critical applications envisioned for WSNs have brought forward new QoS requirements on the network. Further, unique characteristics of WSNs, such as extremely resource-constrained sensors, large-scale random deployment, and novel data-centric communication protocols, pose unprecedented challenges in the area of QoS support in WSNs. Thus, we first review the techniques for QoS support in traditional networks, analyze new QoS requirements in WSNs from a wide variety of applications classified by data delivery models, and propose some non-end-to-end collective QoS parameters. Next, the challenges of QoS support in this new paradigm are presented. Finally, we comment on current research efforts and identify many exciting open issues in order to stimulate more research interest in this largely unexplored area.

Keywords: Wireless networks, wireless sensor networks, QoS, collective QoS

Advances in microelectronics, array processing, and wireless networking have motivated the analysis and design of low-cost integrated sensing, computing, and communicating nodes capable of performing various demanding collaborative space-time processing tasks. In this paper, we consider the problem of coherent acoustic sensor array processing and localization on distributed wireless sensor networks. We first introduce some basic concepts of beamforming and localization for wide-band acoustic sources. A review of various known localization algorithms based on time-delay followed by least-squares estimations as well as the maximum-likelihood method is given. Issues related to practical implementation of coherent array processing, including the need for fine-grain time synchronization, are discussed. Then we describe the implementation of a Linux-based wireless networked acoustic sensor array testbed, utilizing commercially available iPAQs with built-in microphones, codecs, and microprocessors, plus wireless Ethernet cards, to perform acoustic source localization. Various field-measured results using two localization algorithms show the effectiveness of the proposed testbed. An extensive list of references related to this work is also included.

Keywords: Ad hoc network, beamforming, distributed sensor network, microphone array, source localization, time synchronization, wireless network.

Mobile applications must operate in environments in which the network connectivity, input/output devices, power and contextual information available to them may all vary. Applications which react to changes in these parameters in order to ensure continuing service to the user are termed adaptive applications and have recently emerged as an area of intense research activity. In this paper we describe the design and implementation of a network emulator which facilitates research in this field by allowing applications to be exposed to user controlled fluctuations in network service. The emulator can be used with any application which uses UDP and requires only minimal changes to the application or, it may be used with applications written using the ANSAware distributed systems platform in which case no changes are necessary to the application. The design and implementation of the emulator are described in this paper as our experiences of using the emulator to model three distinct types of wireless network: GSM, an analogue cellular service and a simple shared radio channel. The source code for the emulator is freely available and instructions on obtaining the code are also included.

Keywords: Simulation

In this paper we describe a topology discovery algorithm (TopDisc) for wireless sensor networks with its applications to network management. The algorithm finds a set of distinguished nodes, using whose neighborhood information we can construct the approximate topology of the network. Only these distinguished nodes reply back to the topology discovery probes, thereby reducing the communication overhead of the process. These nodes logically organize the network in the form of clusters comprised of nodes in their neighborhood. TopDisc forms a Tree of Clusters (TreC) rooted at the monitoring node, which initiates the topology discovery process. We show how managing a complex network of sensor nodes is simplified using a TreC. This organization is used for efficient data dissemination and aggregation, duty cycle assignments and network state retrieval. The mechanisms proposed are completely distributed, use only local information and are highly scalable.

Keywords: Wireless Sensor Networks, Clustering

While there exist many papers that compare the performances of different routing protocols for wireless ad hoc networks, these simulations are often using the same simplistic assumptions for the physical layer modeling. In this paper, we propose to combine techniques like ray tracing, Markov chains and experimental data in order to design an high-accuracy physical layer that can be implemented in the NS-2.

Keywords: Wireless networks modeling and simulation, NS-2, Markov chains, Ray-tracing

In most studies on mobile ad-hoc networks (MANET) simulation models are used for the evaluation of devices and protocols. Such simulations focus on the higher-layer protocols that are analyzed, and suppose that the other layers of the OSI model, particularly the physical layer models, do not interfer with the experimentation. In this paper, we present an innovative implementation of the physical layer for the NS-2 network simulator targeted at the performance analysis of indoor ad-hoc networks. It includes realistic signal reception, interference and noise computation, and effects of people moving indoor. However, as shown in this paper, neglecting the physical layer while modeling wireless indoor environments is error prone and should be considered more carefully.

Keywords: Simulation Accuracy

Wireless sensor networks are appealing to researchers due to their wide range of application potential in areas such as target detection and tracking, environmental monitoring, industrial process monitoring, and tactical systems. However, lower sensing ranges result in dense networks, which bring the necessity to achieve an efficient medium access protocol subject to power constraints. Various MAC protocols with different objectives were proposed for wireless sensor networks. In this paper, we first outline the sensor network properties that are crucial for the design of MAC layer protocols. Then, we describe several MAC protocols proposed for sensor networks emphasizing their strengths and weaknesses. Finally, we point out open research issues on MAC layer design.

Keywords: MAC Protocols, Sensor Networks, Survey

Keywords: Functional Programming

Wireless sensor networks are composed of large numbers of tiny networked devices that communicate untethered. For large scale networks it is important to be able to dynamically download code into the network. In this paper we present Contiki, a lightweight operating system with support for dynamic loading and replacement of individual programs and services. Contiki is built around an event-driven kernel but provides optional preemptive multithreading that can be applied to individual processes. We show that dynamic loading and unloading is feasible in a resource constrained environment, while keeping the base system lightweight and compact.

Keywords: Wireless Sensor Networks

Keywords: Routing

As its rapid growth continues and new applications and requirements arise, the technological advance of the Internet is increasingly limited by the facts and shortcomings of the existing infrastructure. Attempts to address this by incrementally extending or revising the existing standards have met with considerable diffculties, as in the case of IPv6 or Mobile IP. Although this is partly due to economical and practical reasons, the question presents itself if the fundamental technologies underlying the Internet themselves might need an overhaul. Part of the discussion of the future of the Internet thus turns towards clean slate designs, which envision how the Internet would look like if it were re-designed from scratch today. Purposely ignoring practical constraints, clean slate research has the liberty to challenge even the most fundamental concepts of the currentfdesign.
TuneInNet is a clean slate design developed at the Freie Universität Berlin and the Universität Zürich. It seeks to banish the intelligence from the network in a more radical manner than the Internet Protocol Suite does, thereby aiming at a backbone that consists of simple, purely optical switches and provides only raw connectivity. In this scenario, data is flooded and filtered rather than routed based on addresses. This can be construed as a move towards the radio, from which it derives its name: the sender sends data without regard to whom, whereas the receiver filters out - or tunes in to - the data that interests him. This thesis presents and evaluates a prototypical implementation of TuneInNet.

Keywords: Internet, Routing, Flooding, TuneInNet

Data Centric Storage (DCS) is a powerful storage paradigm for wireless ad hoc networks. In mobile ad hoc networks (MANETs), however, the mobility and varying density of nodes may significantly impact the efficiency of data access and the level of data consistency for existing DCS mechanisms. In this paper, we propose an efficient resilience mechanism for data centric storage that supports DCS in mobile environments. We introduce a novel indirection strategy that enables us to distinguish the storage of data at dedicated server nodes from the storage of additional information to locate these servers. Our approach places server location information dynamically in strategic parts of the network based on its current topology. Combining our server location advertisement with any geographic routing protocol, we provide a robust data update and query processing technique for data centric storage in MANETs. We show analytically and by means of experimental evaluations that, despite the additional indirection during packet forwarding, our approach provides superior storage and retrieval performance than the original DCS algorithm even for large amounts of dynamic data.

Keywords: Routing

This paper investigates the channel parameters (time dispersive properties) for the novel idea of tiny communicators called `specks'. These tiny devices are limited with power so a clear idea of the channel impairment is mandatory for the design of onboard DSP. In order to facilitate the design, measurement of the impulse response characteristic has been investigated through different media and antennas. The paper investigates the measured impulse response and statistical properties of amplitude variations for individual impulses for distances of around 10cm in addition to power delay profile, path loss, mean excess delay, root mean square delay, coherence bandwidth, and their impact on system design. The narrowband model has been used to predict the path loss of the channel and extent of coverage of the transmitting speck. The wide band channel sounding has been done to investigate the impulse response parameters such as delay spread, which is used to compute several secondary statistics like coherence bandwidth and data rate.

Keywords: Digital Sampling Scope (DSS), Line of Sight (LOS), Non Line of sight (NLOS), Root Mean Square (RMS), Weak Signal (WS)

Optimizing sensor networks involves addressing a wide range of issues steaming from limited energy reserves, computation power, communication capabilities, and self-managing sensor nodes. The ns-2 simulation environment is a flexible tool for network engineers to investigate how various protocols perform with different configurations and topologies. This paper describes how we extended the ns-2 framework to include support for sensor networks, and illustrates their utility with an experiment examining Mobile Ad Hoc Network (MANET) routing within a dynamic sensor network.

Keywords: Wireless Sensor Networks, Simulation

We present a new metric for routing in multi-radio, multi-hop wireless networks. We focus on wireless networks with stationary nodes, such as community wireless networks.
The goal of the metric is to choose a high-throughput path between a source and a destination. Our metric assigns weights to individual links based on the Expected Transmission Time (ETT) of a packet over the link. The ETT is a function of the loss rate and the bandwidth of the link. The individual link weights are combined into a path metric called Weighted Cumulative ETT (WCETT) that explicitly accounts for the interference among links that use the same channel. The WCETT metric is incorporated into a routing protocol that we call Multi-Radio Link-Quality Source Routing.
We studied the performance of our metric by implementing it in a wireless testbed consisting of 23 nodes, each equipped with two 802.11 wireless cards. We find that in a multi-radio environment, our metric significantly outperforms previously-proposed routing metrics by making judicious use of the second radio.

Keywords: Wireless multi-hop networks, multi-radio, routing, performance

Self-organization is a great concept for building scalable systems consisting of huge numbers of subsystems. The primary objectives are coordination and collaboration on a global goal. Until now, many self-organization methods have been developed for communication networks in general and ad hoc networks in particular. Nevertheless, the term self-organization is still often misunderstood or misused. This paper contributes to the ad hoc community by providing a better understanding of self-organization in ad hoc networks. Primarily, solutions for the medium access control and the network layer are analyzed and discussed. The main contribution of this paper is a categorization of self-organization methodologies. Additionally, well-known methods in ad hoc networks are classified and some case studies are provided.

Keywords: self-organization, ad hoc network, wireless sensor network, ad hoc routing, power-aware protocols, network layer, medium access control, clustering, bio-inspired networking

We describe the design of a system for wildfire monitoring incorporating wireless sensors, and report results from field testing during prescribed test burns near San Francisco, California. The system is composed of environmental sensors collecting temperature, relative humidity and barometric pressure with an on-board GPS unit attached to a wireless, networked mote. The motes communicate with a base station, which communicates the collected data to software running on a database server. The data can be accessed using a browser-based web application or any other application capable of communicating with the database server. Performance of the monitoring system during two prescribed burns at Pinole Point Regional Park (Contra Costa County, California, near San Francisco) is promising. Sensors within the burn zone recorded the passage of the flame front before being scorched, with temperature increasing, and barometric pressure and humidity decreasing as the flame front advanced. Temperature gradients up to 5 C per second were recorded. The data also show that the temperature slightly decreases and the relative humidity slightly increases from ambient values immediately preceding the flame front, indicating that locally significant weather conditions develop even during relatively cool, slow moving grass fires. The maximum temperature recorded was 95 C, the minimum relative humidity 9%, and barometric pressure dropped by as much as 25 mbar.

Keywords: Wireless Sensor Networks, Wildfires, TinyOS, Motes

Wireless sensor networks consist of tiny devices that usually have severe resource constraints in terms of energy, processing power and memory. In order to work efficiently within the constrained memory, many operating systems for such devices are based on an event-driven model rather than on multi-threading. While event-driven systems allow for reduced memory usage, they require programs to be developed as explicit state machines. Since implementing programs as explicit state machines is hard, developing, maintaining, and debugging programs for event-driven systems is difficult.
In this paper, we introduce protothreads, a programming abstraction for event-driven sensor network systems. Protothreads simplify implementation of high-level functionality on top of event-driven systems, without significantly increasing the memory requirements. The memory requirement of a protothread is that of an unsigned integer.

Keywords: Wireless Sensor Networks, Event-based Programming

Distributed event detection in wireless sensor networks (WSNs) is the process of observing and evaluating an event using multiple sensor nodes without the help of a base station or other means of central coordination and processing. Current approaches to event detection in WSNs transmit raw data to an external entity for evaluation or rely on simplistic pattern recognition schemes. This implies either high communication overhead or low event detection accuracy, especially for complex events.
In this paper, we present our currently on-going work on a system for distributed event detection that particularly suits the specific characteristics of WSNs. Adapting traditional pattern recognition algorithms to highly embedded devices, it uses the distributed sampling of sensor nodes to optimize the accuracy of the event detection process. Four different algorithms for distributing, classifying and fusing “fingerprints” of the raw data sampled on each sensor are proposed and quantitatively evaluated in a small-scale experiment.

Keywords: Wireless Sensor Networks, Distributed Event Detection, Pattern Recognition

Drahtlose Sensornetze haben aufgrund ihrer verteilten Struktur die Möglichkeit, differenziert Informationen an unterschiedlichen Stellen der Umwelt zu erfassen. Die Erkennung von Ereignissen, die in ihrer Umgebung mehrere Parameter und Messpunkte verschiedentlich beeinflussen, wird mittels drahtlosen Sensornetzen möglich. Das vorgestellte System nutzt die Vorteile drahtloser Sensornetze, indem mehrere Sensorknoten das Problem der verteilten Ereigniserkennung gemeinsam lösen. Mit dieser Arbeit wird ein Erkennungssystem vorgestellt, das verteilt zu betrachtende Ereignisdaten auf Basis einer lokal auf den Sensorknoten durchgeführten Mustererkennung im Netz fusioniert und klassifiziert.
Eine dynamische Kalibrierung des Beschleunigungssensors und ein Mustertraining mit den Sensorknoten ermöglichen eine nachfolgende differenzierte Erkennung der gelernten Bewegungsmuster. Die erfassten Beschleunigungsdaten werden lokal auf den jeweiligen Sensorknoten komprimiert und mit den Daten benachbarter Sensorknoten fusioniert, um im Bezug auf das globale Ereignis ausgewertet zu werden. Verschiedene Fusionstechniken auf Ebene der Klassifizierung sowie der Mustermerkmale werden getrennt und miteinander verknüpft untersucht und bewertet.
Ein qualitativer Vergleich zwischen der hier erarbeiteten lokalen und verteilten Ereigniserkennung sowie einem bestehenden verteilten Erkennungsansatz wird gezogen. Die lokale Ereigniserkennung erreicht eine Korrektklassifikationsrate von 89,4 %. Basierend auf der Komponente der lokalen Erkennung erzielt das verteilte Erkennungssystem in den untersuchten Fusionsmethoden eine Korrektklassifikationsrate von 93,8 % bis 96,3 %. Die Erkennungsratensteigerungen werden auf den Einsatz der verteilten Erkennungsstrategie zurückgeführt.
Die energietechnisch kostenintensivste Operation in drahtlosen Sensornetzen ist das Versenden von Datenpaketen. Aufgrund dieser Problematik wird die Rentabilität der Datenübertragung innerhalb des Sensornetzes in Bezug auf die erbrachte Korrektklassifikationsrate in den Fusionsmethoden analysiert. Außerdem werden während der lokalen und verteilten Mustererkennung die Einflussstärken der Probanden auf die ermittelten Kennwerte untersucht und evaluiert.

Keywords: Wireless Sensor Networks, Event Detection

Distributed event detection in wireless sensor networks is an approach to increase event recognition accuracy by fusing correlated parts of events, recognized by multiple sensor nodes. Events range from simple threshold detection to complex events requiring pattern analysis. Our previous deployment in this area of research investigates the possibility to recognize intrusion events, breaching security of wireless sensor network guarded areas.
We present a new platform, consisting of an improved system layer and application layer that advances distributed event detection in wireless sensor networks. We improve the event detection accuracy, by applying an ARM7-based sensor board with more precise acceleration sensors. In addition, the threaded fire-kernel and adjusted routing take the restricted resources on wireless sensor nodes into account. In order to gain a higher reliability in the detection results, we employ a distributed data quality estimator. The architecture’s goal is to carry out large-scale deployments on fences of construction sites that detect events as stated above.

Keywords: Wireless sensor network, distributed event detection

Athletes can improve their skills by using supervising training devices with integrated digital feedback. For example, martial art techniques are often complex in detail and need to be perfectly adopted from the teacher. Distributed event detection systems for digital devices enhance the individual training, resulting in a higher precision of the technique repetition. Distributed event detection, as employed in Wireless Sensor Networks, enables cooperative evaluation and detection of spatialy or temporaly distributed events like fire or earthquakes.
We evaluate the feasibility of integrating a distributed event detection approach into a wireless motion-based training device, to support fight stick training. We present an ubiquitous computing device for in-network event detection, which enables users to obtain direct feedback from the device itself. Multiple sensors help to improve the reliability of the device, while the wireless technology ensures flexibility in a multi-part device. After a brief introduction to distributed event detection, we evaluate event detection accuracy and how link quality effects different scenarios.

Keywords: Event Detection

Networked sensors - those that coordinate amongst themselves to achieve a larger sensing task - will revolutionize information gathering and processing both in urban environments and in inhospitable terrain. The sheer numbers of these sensors and the expected dynamics in these environments present unique challenges in the design of unattended autonomous sensor networks. These challenges lead us to hypothesize that sensor network coordination applications may need to be structured differently from traditional network applications. In particular, we believe that localized algorithms (in which simple local node behavior achieves a desired global objective) may be necessary for sensor network coordination. In this paper, we describe localized algorithms, and then discuss directed diffusion, a simple communication model for describing localized algorithms.

Keywords: Wireless Sensor Networks, Introduction

We introduce and evaluate a feasible end-to-end congestion control algorithm for overcoming the severe deficiencies of TCP in IEEE 802.11 multihop wireless networks. Our approach, which we denote as TCP with Adaptive Pacing (TCP-AP), implements rate-based scheduling of transmissions within the TCP congestion window. The TCP source adaptively sets its transmission rate using an estimate of the current out-of-interference delay and the coefficient of variation of recently measured round-trip times. TCP-AP retains the end-to-end semantics of TCP and neither relies on modifications at the routing or the link layer nor requires cross-layer information from intermediate nodes along the path. As opposed to previous proposals that build on network simulators, we implement and evaluate our approach in a real wireless mesh test-bed comprising 20 nodes. In a comprehensive comparative performance study using our test-bed, we show that, depending on the current network state and traffic patterns, TCP-AP achieves up to 10 times more goodput than TCP NewReno, provides excellent fairness, and is highly responsive to changing network traffic conditions.

Keywords: Wireless Networking, Transport Layer

The formidable growth of WSN research has opened challenging issues about their performance evaluation. Despite the steady increase in mathematical analysis and experimental deployments, most of the community has chosen simulation for their study. Although it seems straightforward, this approach becomes quite a delicate matter. Complexity is caused by several issues. First, the large number of nodes heavily impacts simulation performance and scalability. Second, credible results demand an accurate characterization of the sensor radio channel. New aspects inherent in WSN must be included in simulators (e.g., a physical environment and an energy model), leading to different degrees of accuracy vs. performance. Moreover, many necessary models are in the continuous time domain (e.g., heat transmission, battery discharge), and thus complex to integrate into discrete event network simulators. These issues result in exponential growth of overall network state information. Through this survey we review these problems both quantitatively and qualitatively while depicting a common suitable simulation model. We also briefly describe the most significant simulation frameworks available.

Keywords: Wireless sensor networks, Simulation

Keywords: Wireless Sensor Networks, Middleware

Employing an emulation capability in network simulation provides the ability for real-world traffic to interact with a simulation. The benefits of emulation include the ability to expose experimental algorithms and protocols to live traffic loads, and to test real-world protocol implementations against repeatable interference generated in simulation. This paper describes the design and implementation of the emulation facility in the NS simulator, a commonly-used publicly available network research simulator.

Keywords: Simulation, ns-2

Mobile ad hoc networks by their nature are highly adaptive systems that can come into existence on an as needed basis. They can grow, reduce in size, fragment, and dismantle as desired. The dynamic and very flexible nature of ad hoc networks can be taken to a further level of sophistication by allowing these networks to retune and adapt themselves according to prevailing network conditions. We are interested in scenarios in which ad hoc nodes must reconfigure as part of a network-wide adaptation process such that network-wide consensus is needed before any change can take place. We present an elegant solution for attaining global consensus in MANETs based on the social science theory of the diffusion of innovations. We present results of the application of this novel approach to an ad hoc network with an adaptive reconfigurable network layer.

Keywords: Distributed Decision Making

A Mobile Ad-Hoc Network is a wireless, selforganizing network where all clients and all servers are mobile and battery powered. Currently, most MANET research has been centered on data routing. Increasingly, data communication methods in MANET are being explored. A MANET allows data communication through data broadcast, data query, and peer-to-peer messages. One significant difficulty in assessing and comparing the different MANET data communication protocols proposed is the lack of a standard test environment or benchmark. A MANET data communication benchmark must include, at a minimum, a standard architecture, standard workload, and a standard set of evaluation parameters. This paper describes the major features of a MANET data communication benchmark and demonstrates the benchmark through analysis and simulation of the TriM MANET data communication protocol. This is the first benchmark targeted at MANET data communication research.

Keywords: Simulation accuracy, Benchmark

Keywords: Expert Systems, Java

We describe an event-based, publish-and-subscribe system based on using “smart subscriptions” to recognize weakly structured events. We present a hierarchy of subscription languages (propositional, predicate, temporal and agent) of increasing expressability and computational complexity, and several algorithms (Sig, Memo, Lattice, Compile and RETE) for efficiently recognizing event matches. We have applied this system to implementing and managing distributed applications.

Keywords: Publish-and-subscribe, Events, Managing Distributed Applications, Subscription Languages, Event Channels, Event Matching Algorithms.

We present a new heuristic method for a clustering problem of sensor networks. The heuristic method is using the uncapacitated facility location problem formulation for the clustering problem of sensor networks. It is an iterative method based on the Voronoi diagram. We also propose a parallel version of the heuristics to reduce the time to obtain a solution. The proposed algorithms are investigated for the quality of their approximate solutions and computational time to obtain them. By comparing the approximate solutions to the exact solutions for examples of one hundred sensors, we found that the quality of the approximate solutions is almost the same as that of the exact ones. The computational time to obtain the approximate solutions is a thousandth of that of obtaining the exact solution. For examples of ten thousand sensors, the computational time to obtain a solution is about 9.1 seconds by the sequential algorithm and about 6.0 seconds by our parallel algorithm with six computers.

Keywords: Service placement

Using distributed real-time applications in mobile environments, e.g., multiplayer games or collaborative working tools, is getting popular as mobile devices and wireless networks are becoming ubiquitous. Especially mobile networked gaming, in regard to the current trends, is considered by game developers, mobile device manufacturers and service providers to be a very attractive source of future revenue. Furthermore, the appearance and evolution of new communication paradigms like mobile ad hoc networking offer new ways and unique features for real-time mobile applications and even for mobile gaming. However, ad hoc networks reserve special challenges mainly due to their self-organized behavior and the resource constraints of the participating mobile devices. One of these challenges is how we can manage applications and support their smooth running in this dynamic and error prone environment. In this paper, we present our algorithm called PBS (priority based selection) which is based on graph theory using dominating sets to give support to distributed services in mobile ad hoc networks. PBS computes an appropriate dominating set of the network graph in a fully distributed manner and it is the first approach in contrast to the existing algorithms that offers continuous maintenance of this set even in dynamically changing network topologies. To get an appreciation about PBS we discuss and analyze our algorithm, evaluate it via simulations and show how the dominating set created and maintained by applying PBS can be used in managing real-time multiplayer games in mobile ad hoc networks.

Keywords: Service placement

We consider configuration of wireless sensor networks, where certain functions must be automatically assigned to sensor nodes, such that the properties of a sensor node (e.g., remaining energy, network neighbors) match the requirements of the assigned function. Essentially, sensor nodes take on certain roles in the network as a result of configuration. To help developers with such configuration tasks for a variety of applications, we propose generic role assignment as a programming abstraction, where roles and rules for their assignment can be easily specified using a configuration language. We present such a role specification language and distributed algorithms for role assignment according to such specifications. We evaluate our approach and show that efficient and robust generic role assignment is practically feasible for wireless sensor networks.

Keywords: Sensor Networks, Programming, Configuration

Many self-configuration problems that occur in sensor networks, such as clustering or operator placement for in-network data aggregation, can be modeled as facility location problems. Unfortunately, existing distributed facility location algorithms are hardly applicable to multi-hop sensor networks. Based on an existing centralized algorithm, we therefore devise equivalent distributed versions which, to our knowledge, represent the first distributed approximations of the facility location problem that can be practicably implemented in multihop sensor networks with local communication. Through simulation studies, we demonstrate that, for typical instances derived from sensor-network configuration problems, the algorithms terminate in only few communication rounds, the runtime does not increase with the network size, and, finally, that our implementation requires only local communication confined to small network neighborhoods. In addition, we propose simple extensions to our algorithms to support dynamic networks with varying link qualities and node additions and deletions. Using link quality traces collected from a real sensor network deployment, we demonstrate the effectiveness of our algorithms in realistic multi-hop sensor networks.

Keywords: Service placement

The MMA7260Q low cost capacitive micromachined accelerometer features signal conditioning, a 1-pole low pass filter, temperature compensation and g-Select which allows for the selection among 4 sensitivities. Zero-g offset full scale span and filter cut-off are factory set and require no external devices. Includes a Sleep Mode that makes it ideal for handheld battery powered electronics.

Keywords: Data Sheet, MMA7260Q Accelerometer

In this paper, we study clustering algorithms for wireless sensor networks from a view of facility location theory. From this view, we can consider that LEACH-C, which is one of the principal studies on cluster-based network organization, formulates the clustering problem as a p-median problem. We point out drawbacks of the formulation in LEACH-C. To overcome the drawbacks, we formulate the problem as an uncapacitated facility location problem. Computational experiments show that the proposed algorithm can extend the lifetime of sensor networks, compared to LEACH-C.

Keywords: Location, p-median problem, UFLP, Wireless sensor network

Keywords: Simulation, ns-2, Manual

Keywords: Simulation, ns-2, Manual

Wireless mesh networks are an emerging and versatile communication technology. The most common application of these networks is to provide access of any number of users to the world wide Internet. They can be set up by Internet service providers or even individuals joined in communities. Due to the wireless medium that is shared by all participants, effects like short-time fading, or the multi-hop property of the network topology many issues are still in the focus of research. Testbeds are a powerful tool to study wireless mesh networks as close as possible to real world application scenarios. In this technical report we describe the design, architecture, and implementation of our work-in-progress wireless testbed at Freie Universität Berlin consisting of 100 mesh routers that span multiple buildings. The testbed is hybrid as it combines wireless mesh network routers with a wireless sensor network.

Keywords: DES-Testbed

Testbeds are a powerful tool to study wireless mesh and sensor networks as close as possible to real world application scenarios. In contrast to simulation or analytical approaches these installations face various kinds of environment parameters. Challenges related to the shared physical medium, operating system, and used hardware components do arise. In this technical report about the work-in-progress Distributed Embedded Systems testbed of 100 routers deployed at the Freie Universität Berlin we focus on the software architecture and give an introduction to the network protocol stack of the Linux kernel. Furthermore, we discuss our first experiences with a pilot network setup, the encountered problems and the achieved solutions. This writing continues our first publication and builds upon the discussed overall testbed architecture, our experiment methodology, and aspired research objectives.

Keywords: DES-Testbed

Em* is a software environment for developing and deploying Wireless Sensor Network (WSN) applications on Linux-class hardware platforms (called “Microservers”). Em* consists of libraries that implement message-passing IPC primitives, tools that support simulation, emulation, and visualization of live systems, both real and simulated, and services that support for networking, sensing, and time synchronization. While Em*'s design has favored ease of use and modularity over efficiency, the resulting increase in overhead has not been an impediment to any of our current projects.

Keywords: Wireless Sensor Networks, Middleware

Many Wireless Sensor Network (WSN) applications are composed of a mixture of deployed devices with varying capabilities, from extremely constrained 8-bit “Motes” to less resource-constrained 32-bit “Microservers”. EmStar is a software environment for developing and deploying complex WSN applications on networks of 32-bit embedded Microserver platforms, and integrating with networks of Motes. EmStar consists of libraries that implement message-passing IPC primitives, tools that support simulation, emulation, and visualization of live systems, both real and simulated, and services that support networking, sensing, and time synchronization. While EmStar's design has favored ease of use and modularity over efficiency, the resulting increase in overhead has not been an impediment to any of our current projects.

Keywords: Wireless Sensor Networks, Operating System

The uncapacitated facility location problem is one of choosing sites among a set of candidates in which facilities can be located, so that the demands of a given set of clients are satisfied at minimum costs. Applications of neighborhood search methods to this problem have not been reported in the literature. In this paper we first describe and compare several neighborhood structures used by local search to solve this problem. We then describe neighborhood search heuristics based on tabu search and complete local search with memory to solve large instances of the uncapacitated facility location problem. Our computational experiments show that on medium sized problem instances, both these heuristics return solutions with costs within 0.075% of the optimal with execution times that are often several orders of magnitude less than those required by exact algorithms. On large sized instances, the heuristics generate low cost solutions quite fast, and terminate with solutions whose costs are within 0.0345% of each other.

Keywords: Uncapacitated facility location;Heuristics, Greedy, Local search, Tabu search, Complete local search with memory

When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput λ(n) obtainable by each node for a randomly chosen destination is Θ(W/√(nlogn)) bits per second under a non-interference protocol.
If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can be transported by the network per second is Θ(W√An) bit-meters per second. Thus even under optimal circumstances, the throughput is only Θ(W/√n) bits per second for each node for a destination nonvanishingly far away.
Similar results also hold under an alternate physical model where a required signal-to-interference ratio is specified for successful receptions.
Fundamentally, it is the need for every node all over the domain to share whatever portion of the channel it is utilizing with nodes in its local neighborhood that is the reason for the constriction in capacity.
Splitting the channel into several subchannels does not change any of the results.
Some implications may be worth considering by designers. Since the throughput furnished to each user diminishes to zero as the number of users is increased, perhaps networks connecting smaller numbers of users, or featuring connections mostly with nearby neighbors, may be more likely to be find acceptance.

Keywords: Wireless networks, Ad hoc networks, Multi-hop radio networks, Through-put, Capacity

Sensor networks are not just data networks with sensors being the sources of data. Rather, they are often developed and deployed for a specific application, and the entire network operation is accordingly geared towards satisfying this application. For overall system efficiency, it may be necessary for nodes to perform computations on data, as opposed to simply originating or forwarding data.
Thus, the entire network can be viewed as performing an application specific distributed computation. The topic of this paper is to survey some lines of research which may be useful in developing a theory of in-network computation, that aims to elucidate how a wireless sensor network should efficiently perform such distributed computation.
We review several existing approaches to computation problems in network settings, with a particular emphasis on the communication aspect of computation. We begin by studying the basic two-party communication complexity model and how to optimally compute functions of distributed inputs in this setting.
We proceed to larger multi-hop networks, and study how block-computation and function structure can be exploited to provide greater computational throughput. We then consider distributed computation problems in networks subject to noise. Finally, we review some randomized gossip based approaches to computing aggregate functions in networks.
These are diverse approaches spanning many different research communities, but together may find a role in the development of a more substantial theoretical foundation for sensor networks.

Keywords: Wireless sensor networks

Most comparisons of wireless ad hoc routing algorithms involve simulated or indoor trial runs, or outdoor runs with only a small number of nodes, potentially leading to an incorrect picture of algorithm performance. In this paper, we report on an outdoor comparison of four different routing algorithms, APRL, AODV, ODMRP, and STARA, running on top of thirty-three 802.11-enabled laptops moving randomly through an athletic field. This comparison provides insight into the behavior of ad hoc routing algorithms at larger real-world scales than have been considered so far. In addition, we compare the outdoor results with both indoor (“tabletop”) and simulation results for the same algorithms, examining the differences between the indoor results and the outdoor reality. Finally, we describe the software infrastructure that allowed us to implement the ad hoc routing algorithms in a comparable way, and use the same codebase for indoor, outdoor, and simulated trial runs.

Keywords: Wireless ad hoc routing, 802.11, MANET, mobile computing

We present design patterns used by software components in the TinyOS operating system. They differ significantly from traditional software design patterns due to TinyOS's focus on static allocation and whole-program composition. We describe how nesC has evolved to support design patterns by including a few simple language primitives.

Keywords: Wireless Sensor Networks, Programming

In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.

Keywords: Facility location, Distributed approximation, Randomized algorithm

We present nesC, a programming language for networked embedded systems that represent a new design space for application developers. An example of a networked embedded system is a sensor network, which consists of (potentially) thousands of tiny, low-power “motes,” each of which execute concurrent, reactive programs that must operate with severe memory and power constraints.
nesC's contribution is to support the special needs of this domain by exposing a programming model that incorporates event-driven execution, a flexible concurrency model, and component-oriented application design. Restrictions on the programming model allow the nesC compiler to perform whole-program analysis, including data-race detection (which improves reliability) and aggressive function inlining (which reduces resource consumption).
nesC has been used to implement TinyOS, a small operating system for sensor networks, as well as several significant sensor applications. nesC and TinyOS have been adopted by a large number of sensor network research groups, and our experience and evaluation of the language shows that it is effective at supporting the complex, concurrent programming style demanded by this new class of deeply networked systems.

Keywords: Wireless Sensor Networks, Language Support

Keywords: DES-Testbed

Keywords: Service Discovery, Service Placement

Keywords: Wireless Sensor Networks, Deployment

Recently deployed Wireless Sensor Network systems (WSNs) are increasingly following heterogeneous designs, incorporating a mixture of elements with widely varying capabilities. The development and deployment of WSNs rides heavily on the availability of simulation, emulation, visualization and analysis support. In this work, we develop tools specifically to support heterogeneous systems, as well as to support the measurement and visualization of operational systems that is critical to addressing the inevitable problems that crop up in deployment. Our system differs from related systems in three key ways: in its ability to simulate and emulate heterogeneous systems in their entirety, in its extensive support for integration and interoperability between motes and microservers, and in its unified set of tools that capture, view, and analyze real time debugging information from simulations, emulations, and deployments.

Keywords: Sensor Networks, Real Code Simulation, EmStar, TinyOS

The concepts of the “center” and the “median vertex” of a graph are generalized to the “absolute center” and the “absolute median” of a weighted graph (a graph with weights attached to its vertices as well as to its branches). These results are used to find the optimum location of a “switching center” in a communication network and to locate the best place to build a “police station” in a highway system. It is shown that the optimum location of a switching center is always at a vertex of the communication network while the best location for the police station is not necessarily at an intersection. Procedures for finding these locations are given.

Keywords: Facility Location Theory

The concept of a median in a weighted graph is generalized to a multimedian. Then, it is shown that the optimum distribution of p switching centers in a communication network is at a p-median of the corresponding weighted graph. The following related problem in highway networks is also considered: What is a minimum number of policemen that can be distributed in a highway network so that no one is farther away from a policeman than a given distance d? This problem is attacked by generating all vertex-coverings (externally stable sets) of a graph by means of a Boolean function defined over the vertices of a graph. Then this idea is extended to Boolean functions that generate all matchings, all factors, and all possible subgraphs of G with given degrees.

Keywords: Facility Location Theory

We present a broad extension of the conventional formalism of state machines and state diagrams, that is relevant to the specification and design of complex discrete-event systems, such as multi-computer real-time systems, communication protocols and digital control units. Our diagrams, which we call statecharts, extend conventional state-transition diagrams with essentially three elements, dealing, respectively, with the notions of hierarchy, concurrency and communication. These transform the language of state diagrams into a highly structured and economical description language. Statecharts are thus compact and expressive small diagrams can express complex behavior-as well as compositional and modular. When coupled with the capabilities of computerized graphics, statecharts enable viewing the description at different levels of detail, and make even very large specifications manageable and comprehensible. In fact, we intend to demonstrate here that statecharts counter many of the objections raised against conventional state diagrams, and thus appear to render specification by diagrams an attractive and plausible approach. Statecharts can be used either as a stand-alone behavioral description or as part of a more general design methodology that deals also with the system's other aspects, such as functional decomposition and data-flow specification. We also discuss some practical experience that was gained over the last three years in applying the statechart formalism to the specification of a particularly complex system.

Keywords: Finite State Machine, Modeling Abstraction

Data replication can drastically improve data accessibility in mobile ad hoc networks (MANETs). In this invited paper, we introduce our recent work that addresses data replication in MANETs, particularly focusing on update management. We explain a few research issues based on both optimistic and pessimistic consistency management policies. We also describe a few prospects for future directions.

Keywords: Service placement

Quality of Service (QoS) support for Mobile Ad-hoc NETworks (MANETs) is a challenging task due to the dynamic topology and limited resource in MANETs, and the QoS model should be the first matter to consider as a system goal. The INSIGNIA framework and DiffServ model can both provide a system-level QoS support for MANETs, but each have pros and cons in service precision and scalability. In this paper, we propose a hybrid QoS model for MANETs, called HQMM, which combines the per-flow granularity of INSIGNIA and the per-class granularity of DiffServ, to provide a responsive, scalable, and flexible QoS support for MANETs. The simulation results show that HQMM can achieve effective service differentiation and offer the best QoS to the per-flow service under various mobility conditions.

Keywords: MANET, QoS

Experience with wired networks has provides guidance about what level of detail is appropriate for simulation-based protocol studies. Wireless simulations raise many new questions about appropriate levels of detail in simulation models for radio propagation and energy consumption. This paper describes the trade-offs associated with adding detail to simulation models. We evaluate the effects of detail in five case studies of wireless simulations for protocol design. Ultimately the researcher must judge what level of detail is required for a given question, but we suggest two approaches to cope with varying levels of detail. When error is not correlated, networking algorithms that are robust to a range of errors are often stressed in similar ways by random error as by detailed models. We also suggest visualization techniques that can help pinpoint incorrect details and manage detail overload.

Keywords: Wireless Network Simulation, Simulation Validation, Energy-Aware Ad Hoc Routing, Data Diffusion, Localization, Robotics, Network Protocol Visualization

Wireless distributed microsensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. In this paper, we look at communication protocols, which can have significant impact on the overall energy dissipation of these networks. Based on our findings that the conventional protocols of direct transmission, minimum-transmission-energy, multihop routing, and static clustering may not be optimal for sensor networks, we propose LEACH (Low-Energy Adaptive Clustering Hierarchy), a clustering-based protocol that utilizes randomized rotation of local cluster base stations (cluster-heads) to evenly distribute the energy load among the sensors in the network. LEACH uses localized coordination to enable scalability and robustness for dynamic networks, and incorporates data fusion into the routing protocol to reduce the amount of information that must be transmitted to the base station. Simulations show that LEACH can achieve as much as a factor of 8 reduction in energy dissipation compared with conventional routing protocols. In addition, LEACH is able to distribute energy dissipation evenly throughout the sensors, doubling the useful system lifetime for the networks we simulated.

Keywords: Wireless Sensor Networks, Routing

Networking together hundreds or thousands of cheap microsensor nodes allows users to accurately monitor a remote environment by intelligently combining the data from the individual nodes. These networks require robust wireless communication protocols that are energy efficient and provide low latency. In this paper, we develop and analyze low-energy adaptive clustering hierarchy (LEACH), a protocol architecture for microsensor networks that combines the ideas of energy-efficient cluster-based routing and media access together with application-specific data aggregation to achieve good performance in terms of system lifetime, latency, and application-perceived quality. LEACH includes a new, distributed cluster formation technique that enables self-organization of large numbers of nodes, algorithms for adapting clusters and rotating cluster head positions to evenly distribute the energy load among all the nodes, and techniques to enable distributed signal processing to save communication resources. Our results show that LEACH can improve system lifetime by an order of magnitude compared with general-purpose multihop approaches.

Keywords: Data aggregation, protocol architecture, wireless microsensor networks

Keywords: Wireless Sensor Networks, Deployment

Keywords: Routing

In the last two decades, the advent of wireless networking technology and the achievements in the miniaturization of electronic devices have set new trends in distributed computing. This ultimately enables a new paradigm for embedding mobile users in intelligent environments that support them in their interactions with their local physical surrounding. This vision is called Ambient Intelligence (AmI). There are still many challenges ahead on the way towards the realization of AmI. One question that is central to the entire concept is: How can we render AmI systems self-organizing such that they can indeed disappear in our environment without creating a massive administrative problem?
In this thesis, we propose a model for a dedicated AmI infrastructure that supports the user in his interaction with his physical environment and with external entities. This infrastructure is called Ad hoc Service Grid (ASG) and provides wireless services in a decentralized and self-organizing fashion. We identify three distinct problems associated with self-organized service provisioning in the ASG model and propose algorithms and protocols that solve them. The problem that is at the center of our work is the self-organized replication and distribution of arbitrary services in an ASG. A set of algorithms is presented that solves this problem in a completely distributed way. The two other problems we tackle are the discovery and lookup of dynamically distributed service replicas and the reconciliation among a dynamic group of replicas. Together, the mechanisms we propose lay the foundation for a general AmI software platform. We will derive the architecture of such a Serviceware from these mechanisms. Detailed experimental results are presented that show the validity of our concepts and identify ways for tailoring our algorithms and protocols to the requirements of specific applications. Furthermore, we propose a new general model and a classification methodology for self-organizing software systems. We employ this model to evaluate our own solutions.
The focus of the research work presented in this thesis is on the global-scale interactions in an AmI system. We call this the macro-level of interactions to separate it from the focus of most current research projects. These projects concentrate more on adaptations at the micro-level, pertaining to the internal structures of specific applications and services. Our work complements these efforts by providing solutions for structuring AmI systems externally, for example by distributing a group of service replicas within an ASG network.

Keywords: Service Placement

Ambient Intelligence (AmI) is an IT concept by which mobile users shall be seamlessly supported in their everyday activities. This includes interactions with remote resources as well as with their current physical environment. We have developed the so-called Ad hoc Service Grid (ASG) infrastructure that supports the latter form of interactions. It allows operators to cover arbitrary locations with ambient services in a drop-and-deploy fashion. An ambient service may autonomously distribute (replicate and migrate) within an ASG network to optimize its availability, response times, and network usage. In this article, we propose a fully decentralized, dynamic, and adaptive service placement algorithm for AmI environments like the ASG. This algorithm achieves a coordinated global placement pattern that minimizes the communication costs without any central controller. It does not even require additional communication among the replicas. Moreover, placement patterns stabilize if no changes occur in the environment while replicas still retain their ability to adapt. Mechanisms for self-organized placement of services are very important for AmI environments in general since they allow for autonomous adaptations to dynamic changes and, thus, remove the need for manual (re)configuration of a running system. We present a detailed evaluation of the algorithm's performance and compare it with three other algorithms to show its competitiveness. Furthermore, we discuss how the desired self-organizing behavior emerges from the interactions of a few simple, local rules that govern the individual placement decisions. In order to do so, we give an in-depth analysis of a series of emergent effects that are not directly encoded into the placement algorithm but stem from its collective dynamics.

Keywords: Service placement

The provisioning of location-specific services in medium-sized facilities like shopping malls, hospitals, and trade fares using WLAN access points or cellular phone systems has some drawbacks. It is rather inflexible or results in high running costs. We propose a new self-organizing infrastructure called Ad hoc Service Grid (ASG) that is based on a mobile ad hoc network to resolve these issues. In this paper, we define the necessary concepts, structures and components for realizing ASGs. We present our approach to building a Serviceware that enables an AGS to self-organize. We evaluate the effectiveness of our mechanisms for service migration, replication, and lookup based on simulation results.

Keywords: Service placement

In order for simulation studies to be useful, it is very important that the simulation results match as closely as possible with the testbed results. This paper compares emulated testbed results with simulation results from NS2 and GloMoSim. OLSR was used as a routing protocol and NRL Mobile Network Emulator (MNE) for dynamic topology control and manipulation. Five Linux based laptops, equipped with IEEE 802.11b wireless network cards were used for testbed implementation. At low traffic rates, testbed results matched closely with the simulation results, at higher traffic rates, testbed results not only differed from the simulation results both qualitatively and quantitatively but the simulation results from both the simulators were barely comparable in some scenarios.

Keywords: Wireless Sensor Networks, Simulation

Directed diffusion is a prominent example of data-centric routing based on application layer data and purely local interactions. In its functioning it relies heavily on network-wide flooding which is an expensive operation, specifically with respect to the scarce energy resources of nodes in wireless sensor networks (WSNs).
One well-researched way to curb the flooding overhead is by clustering. Passive clustering is a recent proposal for on-demand creation and maintenance of the clustered structure, making it very attractive for WSNs and directed diffusion in particular.
The contribution of this paper is the investigation of this combination: Is it feasible to execute directed diffusion on top of a sensor network where the topology is implicitly constructed by passive clustering?
A simulation-based comparison between plain directed diffusion and one based on passive clustering shows that, depending on the scenario, passive clustering can significantly reduce the required energy while maintaining and even improving the delay and the delivery rate. This study also provides insights into the behavior of directed diffusion with respect to its long-term periodic behavior, contributing to a better understanding of this novel class of communication protocols.

Keywords: Wireless Sensor Networks, Routing, Hierarchical Directed Diffusion

This paper describes one of the major efforts in the sensor network community to build an integrated sensor network system for surveillance missions. The focus of this effort is to acquire and verify information about enemy capabilities and positions of hostile targets. Such missions often involve a high element of risk for human personnel and require a high degree of stealthiness. Hence, the ability to deploy unmanned surveillance missions, by using wireless sensor networks, is of great practical importance for the military. Because of the energy constraints of sensor devices, such systems necessitate an energy-aware design to ensure the longevity of surveillance missions. Solutions proposed recently for this type of system show promising results through simulations. However, the simplified assumptions they make about the system in the simulator often do not hold well in practice and energy consumption is narrowly accounted for within a single protocol. In this paper, we describe the design and implementation of a complete running system, called VigilNet, for energy-efficient surveillance. The VigilNet allows a group of cooperating sensor devices to detect and track the positions of moving vehicles in an energy-efficient and stealthy manner. We evaluate VigilNet middleware components and integrated system extensively on a network of 70 MICA2 motes. Our results show that our surveillance strategy is adaptable and achieves a significant extension of network lifetime. Finally, we share lessons learned in building such an integrated sensor system.

Keywords: Sensor networks, Energy conservation, Tracking, Wireless

The Network Emulation Testbed project provides a configurable network environment for the performance analysis of distributed applications and protocols. An emulation scenario consists of a network topology, link parameters, and dynamic change models. In order to set up a scenario automatically, it has to be modeled in an appropriate description language. In this paper, we analyze the requirements for an emulation scenario description language and propose a possible solution.

Keywords: Network Emulation, Scenario Modeling, Network Topologies

In this paper we describe GEA - an interface that enables the development of event-driven network protocols, their testing in a simulated network and deployment using a single, unmodified code. Normally testing and deployment requires separated implementations which results in a significant development and maintenance overhead. This is due to the different APIs of the underlying systems. As a solution to this problem we propose a common, generic event based interface called GEA. We present its design principles and show by example how to implement a network protocols with it. Finally we compare the execution of the protocol implementation in both environments to show the effectiveness of our approach.

Keywords: Simulation

Networking engineers increasingly depend on simulation to design and deploy complex, heterogeneous networks. Similarly, networking researchers increasingly depend on simulation to investigate the behavior and performance of new protocol designs. Despite such widespread use of simulation, today there exists little common understanding of the degree of validation required for various applications of simulation. Further, only limited knowledge exists regarding the effectiveness of known validation techniques. To investigate these issues, in May 1999 DARPA and NIST organized a workshop on Network Simulation Validation. This paper reports on discussions and consensus about issues that arose at the workshop. We describe best current practices for validating simulations and for validating TCP models across various simulation environments. We also discuss interactions between scale and model validation and future challenges for the community.

Keywords: Simulation, Survey, Validation

Comparative performance measurements of distributed applications and network protocols require the availability of appropriate network environments. Network emulation approaches offer a flexible way to mimic the properties of a variety of networks. Existing emulation tools work either with centralized real-time simulation components, limiting the scenario size and maximum traffic, or focus on the emulation of some network properties at a single point. We propose a tool for the realistic emulation of network links, and show how several emulated links can be combined to reproduce a comprehensive network model. In addition to that, the model can include changing network properties, e.g. emerging from mobile communication partners. This facilitates the distributed emulation of a comprehensive, dynamic network scenario to support repeatable performance measurements.

Keywords: Simulation

When using some services across a wireless network, a node should expect to use it in good conditions. The first criterion that comes in mind in wireless environment is network partitioning (i.e. when the client can no more reach the host of the service it is using). This criterion, or QoS attribute, can be handled by predicting partitioning and using service replication which consist of electing a new host for the service and duplicating it on this new host. But wireless networks QoS implies more criterion that could also be handled by service replication. The main problem is then to detect when the replication must occur. In this paper, we propose a metric for link quality evaluation and a fast and reliable protocol to practically compute it.

Keywords: Ad-hoc networks, QoS, Data replication, Link evaluation, Broadcast

A classical problem caused by nodes movement in an ad hoc network is partitioning. Predicting those partitions could be a very useful feature that can be provided to applications in a mobile ad-hoc network environment. Indeed, being aware of a future disconnection in the network can help to ensure a better quality of service by adapting the application behavior. Algorithms already exists to do this but they need position information to be provided by a positioning system. This paper propose an original link robustness evaluation method based on the notion of disjoint paths which allow efficient partition detection without using any kind of positioning system.

Keywords: Partition detection

Technological progress in integrated, low-power, CMOS communication devices and sensors makes a rich design space of networked sensors viable. They can be deeply embedded in the physical world and spread throughout our environment like smart dust. The missing elements are an overall system architecture and a methodology for systematic advance. To this end, we identify key requirements, develop a small device that is representative of the class, design a tiny event-driven operating system, and show that it provides support for efficient modularity and concurrency-intensive operation. Our operating system fits in 178 bytes of memory, propagates events in the time it takes to copy 1.25 bytes of memory, context switches in the time it takes to copy 6 bytes of memory and supports two level scheduling. The analysis lays a groundwork for future architectural advances.

Keywords: Wireless Sensor Networks, Operating Systems

Location-based services offer a powerful approach to provide highly relevant information and functionality to a mobile user. Addressing the problem of location inference, we expand the design space by proposing to employ rule-based programming techniques. Based on position coordinates as well as data gathered by environmental sensors, either a precise location or an abstract location class can be deduced. Both types of location may then be utilized to trigger services in an event-centric manner.

Keywords: Location-Based Services, Rule-Based Programming, Location Inference

Event notification services, or alerting services, are used in various applications such as digital libraries, stock tickers, traffic control, or facility management. However, to our knowledge, a common semantics of events in event notification services has not been defined so far. In this paper, we propose a parameterized event algebra which describes the semantics of composite events for event notification systems. We define the event operators that form composite events and we introduce parameters for event instance selection and event instance consumption. These parameters serve as a support for handling duplicates in both primitive and composite events. The event algebra is exemplified in the domain of transportation logistics.

Keywords: Event Notification Services, Algebra

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.

Keywords: Wireless Sensor Networks, Middleware

Wireless network research in the last years is often based on simulation. Ns-2 is a widely used wireless network simulation tool for this purpose. However, there are no published results about the accuracy of the ns-2 wireless model in the literature so far. In this paper we present the validation of one wireless network model built with ns-2 done by comparing the network characteristics of a simulated, an emulated, and a real wireless network. In order to show only the relevant differences, we have calibrated the radio propagation model of ns-2 to the real network and have used the same routing protocol implementation and the same application data traffic in all the compared networks. The results show that the packet delivery ratios, the connectivity graphs, and the packet latencies are represented in the model with an average error of 0.3%, 10%, and 57% respectively. Based on these results we conclude that the packet delivery ratios, and network topologies are accurately represented in ns-2, once the simulation parameters are properly adjusted. The accuracy of the packet latencies is lower and therefore statements about latencies in the real network based on the simulation results have a lower validity. Based on these results we provide recommendations for future development of the ns-2.

Keywords: Simulation, Validation

The TR1001 hybrid transceiver is ideal for short-range wireless data applications where robust operation, small size, low power consumption and low cost are required. The TR1001 employs RFM's amplifier-sequenced hybrid (ASH) architecture to achieve this unique blend of characteristics. All critical RF functions are contained in the hybrid, simplifying and speeding design-in. The receiver section of the TR1001 is sensitive and stable. A wide dynamic range log detector, in combination with digital AGC and a compound data slicer, provide robust performance in the presence of on-channel interference or noise. Two stages of SAW filtering provide excellent receiver out-of-band rejection. The transmitter includes provisions for both on-off keyed (OOK) and amplitude-shift keyed (ASK) modulation. The transmitter employs SAW filtering to suppress output harmonics, facilitating compliance with ETSI I-ETS 300 220 and similar regulations.

Keywords: Simulation accuracy

Keywords: Simulation accuracy

Keywords: Simulation accuracy

Keywords: Data Processing, Computer Software, Artificial Languages, Logical Structure, Graphic Methods, Graphic Characters

Keywords: WWW

Keywords: Routing

Keywords: Service placement

We analyze the performance of ad hoc pro-active routing protocols. In particular we focuse on the multipoint relay concept introduced in OLSR protocol and which brings a significant improvement in broadcast control traffic overhead.We analyze the performance in two radio network model: the random graph model and the unit graph model. The random graph is more suitable for the modelization of indoor networks. The unit graph is more suitable for outdoor networks. We compare the performance of OLSR with the performance of basic link state protocols using full flooding.

Keywords: MANET, Routing

Network simulation is used widely in network research to test new protocols, modifications to existing protocols and new ideas. The tool used in many cases is ns-2. The nature of the ns-2 protocols means that they are often based on theoretical models that might not behave in the same way as real networks. This paper presents the Network Simulation Cradle which allows real world network stacks to be used in a wrapper that allows the stacks protocols to be used in the ns-2 network simulator. The network stacks from the open source operating systems Linux, FreeBSD and OpenBSD are included in the simulation cradle as well as a stack designed for embedded systems, lwIP. Our results show that ns-2's TCP implementations do not match observed behaviour from real machines in some respects and using the Network Simulation Cradle produces results closer to real world network stacks.

Keywords: Simulation

Much current simulation of TCP makes use of simplified models of TCP, which is a large and complex protocol with many variations possible between implementations. We use direct execution of real world network stacks in the network simulator ns-2 to compare TCP performance between implementations and reproduce existing work. A project called The Network Simulation Cradle provides the real world network stacks and we show how it can be used for performance evaluation and validation. There are large differences in performance between simplified TCP models and TCP implementations in some situations. Such differences are apparent in some reproduced research, with results using the Network Simulation Cradle very different from the results produced with the ns-2 TCP models. In other cases, using the real implementations gives very similar results, validating the original research.

Keywords: Simulation accuracy

The TCP models in the network simulator ns-2 are widely used in network research. They are not aimed at producing results consistent with a TCP implementation, they are rather designed to be a general model for TCP congestion control. The Network Simulation Cradle makes real world TCP implementations available to ns-2: Linux, FreeBSD and OpenBSD can all be simulated as easily as using the original simplified models. These simulated TCP implementations can be validated by directly comparing packet traces from simulations to traces measured from a real network. We describe the Network Simulation Cradle, present packet trace comparison results showing the high degree of accuracy possible when simulating with real TCP implementations and briefly show how this is reflected in a simulation study of TCP throughput.

Keywords: Simulation accuracy

The Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. DSR allows the network to be completely self-organizing and self-configuring, without the need for any existing network infrastructure or administration. The protocol is composed of the two mechanisms of Route Discovery and Route Maintenance, which work together to allow nodes to discover and maintain source routes to arbitrary destinations in the ad hoc network. The use of source routing allows packet routing to be trivially loop-free, avoids the need for up-to-date routing information in the intermediate nodes through which packets are forwarded, and allows nodes forwarding or overhearing packets to cache the routing information in them for their own future use. All aspects of the protocol operate entirely on-demand, allowing the routing packet overhead of DSR to scale automatically to only that needed to react to changes in the routes currently in use. We have evaluated the operation of DSR through detailed simulation on a variety of movement and communication patterns, and through implementation and significant experimentation in a physical outdoor ad hoc networking testbed we have constructed in Pittsburgh, and have demonstrated the excellent performance of the protocol. In this chapter, we describe the design of DSR and provide a summary of some of our simulation and testbed implementation results for the protocol.

Keywords: Wireless Sensor Networks, Routing

Keywords: Simulation, ns-2

Given an undirected graph G = (V, E) with nonnegative costs on its edges, a root node r e V, a set of demands D e V with demand v e D wishing to route w(v) units of flow (weight) to r , and a positive number k, the Capacitated Minimum Steiner Tree (CMStT) problem asks for a minimum Steiner tree, rooted at r, spanning the vertices in D u r, in which the sum of the vertex weights in every subtree connected to r is at most k. When D = V, this problem is known as the Capacitated Minimum Spanning Tree (CMST) problem. Both CMsT and CMST problems are NP-hard. In this article, we present approximation algorithms for these problems and several of their variants in network design. Our main results are the following:
- We present a (vpST + 2)-approximation algorithm for the CMStT problem, where v is the inverse Steiner ratio, and pST is the best achievable approximation ratio for the Steiner tree problem. Our ratio improves the current best ratio of 2pST + 2 for this problem.
- In particular, we obtain (v+2)-approximation ratio for the CMST problem, which is an improvement over the current best ratio of 4 for this problem. For points in Euclidean and rectilinear planes, our result translates into ratios of 3.1548 and 3.5, respectively.
- For instances in the plane, under the Lp norm, with the vertices in D having uniform weights, we present a nontrivial (7/5pST + 3/2)-approximation algorithm for the CMStT problem. This translates into a ratio of 2.9 for the CMST problem with uniform vertex weights in the Lp metric plane. Our ratio of 2.9 solves the long-standing open problem of obtaining any ratio better than 3 for this case.
- For the CMST problem, we show how to obtain a 2-approximation for graphs in metric spaces with unit vertex weights and k = 3, 4.
- For the budgeted CMST problem, in which the weights of the subtrees connected to r could be up to ak instead of k (a >= 1), we obtain a ratio of v + 2a.

Keywords: Spanning trees, minimum spanning trees, approximation algorithms, network design

Researchers have long faced a fundamental tension between the experimental realism of wireless testbeds on one hand, and the control and repeatability of simulation on the other hand. To overcome the stark tradeoff of these traditional alternatives, we are developing a wireless emulator that enables both realistic and repeatable experimentation by leveraging physical layer emulation.
We discuss the design and implementation of a prototype wireless emulator, and show how this emulator can be leveraged to provide insight into wireless network and application behavior. Our experience shows that, compared to simulation, our emulator-based approach provides us with a better understanding of real-world wireless network performance, and enables us to quickly deploy our research into an operational wireless network, while still allowing us to enjoy the benefits of a controlled experimental environment.

Keywords: Wireless Sensor Networks, Simulation

Ad hoc network normally has critical connectivity properties before partitioning. The timely recognition is important in order to perform some data or service replication. Several existing centralized or globalized algorithms declare an edge or a node as critical if their removal will separate the network into several components. We introduce several localized definitions of critical nodes and critical links, using topological or positional information. A node is critical if the subgraph of k-hop neighbours of node (without the node itself) is disconnected. We propose three definitions of critical links, based on verifying common k-hop neighbours, loop length, and critical status of link endpoints, respectively. The experiments with random unit graph model of ad hoc networks show high correspondence of local and global decisions. For instance, in experiments with 500 nodes in connected random unit graphs (using a novel graph generation method from [6], first published here), over half of locally estimated critical nodes and links were indeed globally critical even for k=1 (the accuracy increases to over 70% for k=2 and over 80% for k=3), for average number of neighbours ranging from 3 to 15. The errors mostly occur when alternative routes exist but are relatively long, and therefore may not provide satisfactory service in applications. Therefore our localized protocols provide faster and often more reliable partition warnings for possible timely replication decisions.

Keywords: Partition detection

Most wireless sensor network (WSN) applications are event-based and their special features demand a new paradigm for event services. This paper presents a framework for a generic event service middleware (GEM). GEM provides an integrated service package for WSN applications so that users can specify events accurately, export specified events to the network, and initiate in-mote middleware to provide multi-level event detection. A sensor network event description language (SNEDL), designed specifically for WSN events, is a part of the GEM architecture. Built upon Petri-Nets, SNEDL can also be used as an offline analysis tool. A case study is presented to demonstrate the usefulness of SNEDL. To make the sensor motes understand SNEDL specified events, GEM encodes events into a mote-understood format (called event DNA). GEM also contains an in-mote detection module to read DNAs for event recognition. When communication is necessary for higher level events, a detection module transfers a lightweight structure (called RNA) to support collaborative decisions.

Keywords: Fence Monitoring

Mobile ad hoc networks (MANETs) are gaining a lot of attention in research lately due to their importance in enabling mobile wireless nodes to communicate without any existing wired or predetermined infrastructures. Furthermore, in order to support the growing need for multimedia and realtime applications, quality of service (QoS) support by the networking protocol is required. Several important QoS parameters that are needed by such applications can be identified. They include bandwidth, end-to-end delay, delay jitter, and bit error rate. A good amount of research has been developed in this area covering different issues and challenges such as developing routing protocols that support bandwidth reservation and delay management. In this paper, the current state of research for QoS support in TDMA-based MANETs at the different layers of the networking model is presented and categorized. In addition, the current issues and future challenges that are involved in this exciting area of research are also included.

Keywords: Mobile ad hoc networks (MANETs), Quality of service (QoS), Routing, Time division multiple access (TDMA)

Simulation is the research tool of choice for a majority of the mobile ad hoc network (MANET) community. However, while the use of simulation has increased, the credibility of the simulation results has decreased. To determine the state of MANET simulation studies, we surveyed the 2000-2005 proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). From our survey, we found significant shortfalls. We present the results of our survey in this paper. We then summarize common simulation study pitfalls found in our survey. Finally, we discuss the tools available that aid the development of rigorous simulation studies. We offer these results to the community with the hope of improving the credibility of MANET simulation-based studies.

Keywords: Simulation accuracy

Keywords: RFID, Business Applications

Mobile phones have become a basic commodity and smartphone devices claim a continuously increasing market share. Modern smartphone devices are equipped with powerful processing units and high speed mobile internet capabilities. Mobile operators in turn are offering a wide variety of data plans. These developments will lead to an increase of internet access from mobile devices. At the same time the internet is not solely used anymore for displaying data but collaborative editing, evaluation and distribution of data in any form has become widely popular, as can be seen in the so-called “Web 2.0” services. Suppliers are offering versions of these services that are especially designed for mobile devices.
Today Peer-to-Peer networks are responsible for a considerable amount of the total internet traffic. Although Peer-to-Peer networks mainly gained attention in the media for copyright infringement cases Peer-to-Peer networks offer many positive characteristics. Peer-to-Peer networks are decentralized, self-organizing, scalable and offer no single point of failure. This makes Peer-to-Peer networks an ideal candidate for deploying mobile web services.
The MobP2P base system is a foundation for developing Peer-to-Peer based applications for collaborative data processing developed for the Android platform. Applications built on top of the MobP2P base system enable users to create data items and to share these with remote users. Alterations to these data items are automatically synchronized on authorized devices.

Keywords: Ad Hoc Networks, PUSH Service

Keywords: Facility Location Theory

Wireless sensor networks (WSNs) are deployed to an area of interest to sense phenomena, process sensed data, and take actions accordingly. Due to the limited WSN node resources, distributed processing is required for completing application tasks. Proposals implementing distribution services for WSNs are evolving on different levels of generality. In this paper, these solutions are reviewed in order to determine the current status. According to the review, existing distribution technologies for computer networks are not applicable for WSNs. Operating systems (OSs) and middleware architectures for WSNs implement separate services for distribution within the existing constraints but an approach providing a complete distributed environment for applications is absent. In order to implement an efficient and adaptive environment, a middleware should be tightly integrated in the underlying OS. We recommend a framework in which a middleware distributes the application processing to a WSN so that the application lifetime is maximized. OS implements services for application tasks and information gathering as well as control interfaces for the middleware.

Keywords: ad hoc networking, distribution, service discovery, task allocation, wireless sensor networks

Testing of rule-based expert systems has become a high priority for many organizations as the use of such systems proliferates. Traditional software testing techniques apply to some components of rule-based systems, e.g., the inference engine. However, to structurally test the rule base component requires new techniques or adaptations of existing ones. This paper describes one such adaptation: an extension of data flow path selection in which a graphical representation of a rule base is defined and evaluated This graphical form, called a logical path graph, captures logical paths through a rule base. These logical paths create precisely the abstractions needed in the testing process. An algorithm for the construction of logical path graphs from a rule base is given, and its efficiency and the size of the resulting logical path graphs are analyzed.

Keywords: Basis Path Testing, Data Flow Path Selection, Expert Systems, Rule Bases, Structured Testing

Transmit power control is a prototypical example of a cross-layer design problem. The transmit power level affects signal quality and thus impacts the physical layer, determines the neighboring nodes that can hear the packet and thus the network layer, affects interference which causes congestion and thus affects the transport layer. It is also key to several performance measures such as throughput, delay and energy consumption. The challenge is to determine where in the architecture the power control problem is to be situated, to determine the appropriate power level by studying its impact on several performance issues, to provide a solution which deals properly with the multiple effects of transmit power control, and finally to provide a software architecture for realizing the solution.
We distill some basic principles on power control which inform the subsequent design process. We then detail the design of a sequence of increasingly complex protocols which address the multi-dimensional ramifications of the power control problem. Many of these protocols have been implemented, and may be the only implementations for power control in a real system. It is hoped that the approach in this paper may also be of use in other topical problems in cross-layer design.

Keywords: Wireless Sensor Networks, Power Control

Recently, in an effort to improve the performance of wireless networks, there has been increased interest in protocols which rely on interactions between different layers. However such cross layer design can run at cross purposes with sound and longer term architectural principles, and can lead to various negative consequences. This motivates us to step back and re-examine holistically the issue of cross layer design and its architectural ramifications.
We contend that a good architectural design leads to proliferation and longevity, and illustrate it by some historical examples. Even though the wireless medium is fundamentally different from the wired one, and can offer undreamt of modalities of cooperation, we show that the conventional layered architecture is a reasonable way to operate wireless networks, and is in fact optimal up to an order.
However the temptation and perhaps even the need to optimize by incorporating cross layer adaptation cannot be ignored, and so we examine the issues involved. We show that unintended cross layer interactions can have undesirable consequences on overall system performance. We illustrate them by certain cross layer schemes loosely based on recent proposals. We attempt to distill a few general principles for cross layer design. Moreover, unbridled cross layer design can lead to spaghetti design, which can stifle further innovation and be difficult to upkeep.
At a critical time when wireless networks may be on the cusp of massive proliferation, the architectural considerations may be paramount. We argue that it behooves us to exercise caution while engaging in cross layer design.

Keywords: Wireless Sensor Networks, Cross-layer Networking, Overview

Efficient use of energy while providing an adequate level of connection to individual sessions is of paramount importance in multi-hop wireless networks. Energy efficiency and connection quality depend on mechanisms that span several communication layers due to the existing co-channel interference among competing flows that must reuse the limited radio spectrum. Although independent consideration of these layers simplifies the system design, it is often insufficient for wireless networks when the overall system performance is examined carefully. The multi-hop wireless extensions and the need for routing users' sessions from source to the destination only intensify this point of view. In this work, we present a framework for cross-layer design towards energy-efficient communication. Our approach is characterized by a synergy between the physical and the medium access control (MAC) layers with a view towards inclusion of higher layers as well. More specifically, we address the joint problem of power control and scheduling with the objective of minimizing the total transmit power subject to the end-to-end quality of service (QoS) guarantees for sessions in terms of their bandwidth and bit error rate guarantees. Bearing to the NP-hardness of this combinatorial optimization problem, we propose our heuristic solutions that follow greedy approaches.

Keywords: Wireless Sensor Networks, Cross-layer Networking

Es ist sinnvoll, vor der Ausbringung eines Sensornetzes in die zu beobachtende Umwelt – ein Vorgang, der mit hohen Kosten und großem zeitlichen Aufwand verbunden ist – Aufschluß über die Leistungsfähigkeit des Netzes zu gewinnen. Naheliegenderweise bietet sich dafür die Simulation des Netzes und seiner Umwelt an. Unser Ansatz SEE/OMNeT++ stellt dem simulierten WSN eine virtuelle Umwelt und der WSN-Applikation eine generierbare Plattformabstraktion zu Verfügung. In einem Beispiel werden neue Visualisierungsmöglichkeiten aufgezeigt.

Keywords: Wireless sensor networks, Simulation

There are two usual methods to evaluate a software system in multi-hop wireless ad hoc networks: simulation and real test-bed. The test-bed method is ex- pensive and non-repeatable. The simulation method usually requires re-implementing the real software system inside the simulator, which is also infeasible for large scale software systems. In this paper, we present an emulation system capable of evaluating unmodified real software systems in simulated environments, which is repeatable, detailed, and realistic. The experimental results show that our system is able to emulate large scale ad hoc networks. By using our system, we have greatly improve the performance of the Coda file system in ad hoc networks.

Keywords: Wireless Sensor Networks, Simulation

To increase the utilization of the available frequency channel space in 802.11-based wireless mesh networks, recent work has explored solutions based on multi-radio stations. This paper reports on our design and experimental study of a distributed, self-stabilizing mechanism that assigns channels to multi-radio nodes in wireless mesh networks. We take a modular approach by decoupling the channel selection decision from the data forwarding mechanism, which makes our solution readily applicable to real-world operation when used with emerging multi-radio routing solutions. We demonstrate the efficacy of our protocol on a real-world, 14-node testbed comprised of nodes, each equipped with an 802.11a card and an 802.11g card. We show via extensive measurements on our testbed that our channel assignment algorithm improves the network capacity by 50% in comparison to a homogeneous channel assignment and by 20% in comparison to a random assignment.

Keywords: Channel Assignment

Most research on ad-hoc wireless networks makes simplifying assumptions about radio propagation. The “Flat Earth” model of the world is surprisingly popular: all radios have circular range, have perfect coverage in that range, and travel on a two-dimensional plane. CMU's ns-2 radio models are better but still fail to represent many aspects of realistic radio networks, including hills, obstacles, link asymmetries, and unpredictable fading. We briefly argue that key “axioms” of these types of propagation models lead to simulation results that do not adequately reflect real behavior of ad-hoc networks, and hence to network protocols that may not work well (or at all) in reality. We then present a set of 802.11 measurements that clearly demonstrate that these “axioms” are contrary to fact. The broad chasm between simulation and reality calls into question many of results from prior papers, and we summarize with a series of recommendations for researchers considering analytic or simulation models of wireless networks.

Keywords: Simulation Accuracy

All analytical and simulation research on ad hoc wireless networks must necessarily model radio propagation using simplifying assumptions. We provide a comprehensive review of six assumptions that are still part of many ad hoc network simulation studies, despite increasing awareness of the need to represent more realistic features, including hills, obstacles, link asymmetries, and unpredictable fading. We use an extensive set of measurements from a large outdoor routing experiment to demonstrate the weakness of these assumptions, and show how these assumptions cause simulation results to differ significantly from experimental results. We close with a series of recommendations for researchers, whether they develop protocols, analytic models, or simulators for ad hoc wireless networks.

Keywords: Wireless Network, Wi-Fi, 802.11, Ad Hoc Network, MANET, Mobile Computing, Network Simulation, Experiment, Measurement

We consider the simulation of wireless sensor networks (WSN) using a new approach. We present Shawn [1], an open-source discrete event simulator which has considerable differences to all other simulators currently in existence. Shawn is very powerful in simulating large scale networks with an abstract point of view. It is, to the best of our knowledge, the first simulator to support generic high-level algorithms as well as distributed protocols on exactly the same underlying networks.

Keywords: Wireless Sensor Networks, Simulation

Event-driven programming is a popular paradigm for programming sensor nodes. It is based on the specification of actions (also known as event handlers) which are triggered by the occurrence of events. While this approach is both simple and efficient, it suffers from two important limitations. Firstly, the association of events to actions is static-there is no explicit support for adopting this association depending on the program state. Secondly, a program is split up into many distinct actions without explicit support for sharing information among these, except through global variables. These limitations often lead to issues with code modularity, complexity, and correctness. To tackle these issues we propose OSM, a programming model and language for sensor nodes based on finite state machines. By extending the event paradigm with states and transitions between them, state-based programming supports a dynamic association of events to actions. For removing the second limitation, OSM introduces state attributes that allow sharing of information among actions. They can be considered local variables of a state with support for automatic memory management. OSM specifications can be compiled into sequential C code that requires only minimal runtime support, resulting in efficient and compact systems.

Keywords: Wireless Sensor Networks, Event-based Programming

With the advancement of technology in micro-electronics and wireless communication, small miniature devices called sensor nodes can be used to perform various tasks by forming themselves in to wireless sensor networks. In Wireless Sensor Networks(WSN), event detection is one of the main requirements for most of the applications. An event can be a simple event or a combination of two or more simple events (Composite Event). Detecting and reporting an event desired by the application (user) inspite of stringent constraints of sensor nodes like low energy, low bandwidth, frequent failures etc., is one of the main challenges in WSN. This can be achieved with less uncertainty and masking failures by considering collaboration among sensor nodes. We propose a framework for distributed event detection using collaboration in WSN. The framework consists of two protocols that build a tree by using a communication model similar to the Publish-Subscribe paradigm. This framework is a part of Component Oriented Middleware for Sensor networks (COMiS). In COMiS framework, components are loaded as and when required based on the application semantics. If collaboration is considered, the goal of the application can be easily accomplished even in case of failures of sensors and low energy of nodes.

Keywords: Wireless Sensor Networks, Event of Interest, Collaboration, Middleware, Publish/Subscripe, Simple Event, Composite Event

In this paper we address a well-known facility location problem (FLP) in a sensor network environment. The problem deals with finding the optimal way to provide service to a (possibly) very large number of clients. We show that a variation of the problem can be solved using a local algorithm. Local algorithms are extremely useful in a sensor network scenario. This is because they allow the communication range of the sensor to be restricted to the minimum, they can operate in routerless networks, and they allow complex problems to be solved on the basis of very little information, gathered from nearby sensors. The local facility location algorithm we describe is entirely asynchronous, seamlessly supports failures and changes in the data during calculation, poses modest memory and computational requirements, and can provide an anytime solution which is guaranteed to converge to the exact same one that would be computed by a centralized algorithm given the entire data.

Keywords: Service placement

In the facility location problem (FLP) we are given a set of facilities and a set of clients, each of which is to be served by one facility. The goal is to decide which subset of facilities to open, such that the clients will be served at a minimal cost.
In this paper we investigate the FLP in a setting where the cost depends on data known only to peer nodes. This setting typifies modern distributed systems: peer-to-peer file sharing networks, grid systems, and wireless sensor networks. All of them need to perform network organization, data placement, collective power management, and other tasks of this kind.
We propose a local and efficient algorithm that solves FLP in these settings. The algorithm presented here is extremely scalable, entirely decentralized, requires no routing capabilities, and is resilient to failures and changes in the data throughout its execution.

Keywords: local, distributed, data-mining, large scale

Wireless technologies, such as IEEE 802.11a, that are used in ad hoc networks provide for multiple non-overlapping channels. Most ad hoc network protocols that are currently available are designed to use a single channel. However, the available network capacity can be increased by using multiple channels. This paper presents new protocols specifically designed to exploit multiple channels. Our protocols simplify the use of multiple channels by using multiple interfaces, although the number of interfaces per host is typically smaller than the number of channels. We propose a link layer protocol to manage multiple channels, and it can be implemented over existing IEEE 802.11 hardware. We also propose a new routing metric for multi-channel multi-interface networks, and the metric is incorporated into an on-demand routing protocol that operates over the link layer protocol. Simulation results demonstrate the effectiveness of the proposed approach in significantly increasing network capacity, by utilizing all the available channels, even when the number of interfaces per host is smaller than the number of channels.

Keywords: Channel Assignment

Keywords: Meta

We present the design, implementation, and evaluation of INSIGNIA, an IP-based quality of service framework that supports adaptive services in mobile ad hoc networks. The framework is based on an in-band signaling and soft-state resource management approach that is well suited to supporting mobility and end-to-end quality of service in highly dynamic environments where the network topology, node connectivity, and end-to-end quality of service are time varying. Architecturally INSIGNIA is designed to support fast reservation, restoration, and end-to-end adaptation based on the inherent flexibility and robustness and scalability found in IP networks. We evaluate the framework, paying particular attention to the performance of the in-band signaling system, which helps counter time-varying network dynamics in support of the delivery of adaptive services. Our results show the benefit of our framework under diverse mobility, traffic, and channel conditions.

Keywords: MANET, QoS

Early simulation experience with wireless ad hoc networks suggests that their capacity can be surprisingly low, due to the requirement that nodes forward each others’ packets. The achievable capacity depends on network size, traffic patterns, and detailed local radio interactions. This paper examines these factors alone and in combination, using simulation and analysis from first principles. Our results include both specific constants and general scaling relationships helpful in understanding the limitations of wireless ad hoc networks.
We examine interactions of the 802.11 MAC and ad hoc forwarding and the effect on capacity for several simple configurations and traffic patterns. While 802.11 discovers reasonably good schedules, we nonetheless observe capacities markedly less than optimal for very simple chain and lattice networks with very regular traffic patterns. We validate some simulation results with experiments.
We also show that the traffic pattern determines whether an ad hoc network’s per node capacity will scale to large networks. In particular, we show that for total capacity to scale up with network size the average distance between source and destination nodes must remain small as the network grows. Non-local traffic patterns in which this average distance grows with the network size result in a rapid decrease of per node capacity. Thus the question “Are large ad hoc networks feasible?” reduces to a question about the likely locality of communication in such networks.

Keywords: Ad hoc networks

Composed of tens of thousands of tiny devices with very limited resources (“motes”), sensor networks are subject to novel systems problems and constraints. The large number of motes in a sensor network means that there will often be some failing nodes; networks must be easy to repopulate. Often there is no feasible method to recharge motes, so energy is a precious resource. Once deployed, a network must be reprogrammable although physically unreachable, and this reprogramming can be a significant energy cost.
We present Maté, a tiny communication-centric virtual machine designed for sensor networks. Maté's high-level interface allows complex programs to be very short (under 100 bytes), reducing the energy cost of transmitting new programs. Code is broken up into small capsules of 24 instructions, which can self-replicate through the network. Packet sending and reception capsules enable the deployment of ad-hoc routing and data aggregation algorithms. Maté's concise, high-level program representation simplifies programming and allows large networks to be frequently reprogrammed in an energy-efficient manner; in addition, its safe execution environment suggests a use of virtual machines to provide the user/kernel boundary on motes that have no hardware protection mechanisms.

Keywords: Wireless Sensor Networks, Virtual Machine

Keywords: Wireless Sensor Networks, Introduction

Ad-hoc wireless networks consist of mobile nodes interconnected by multi-hop wireless paths. Unlike conventional wireless networks, ad-hoc networks have no fixed network infrastructure or administrative support. Because of the dynamic nature of the network topology and limited bandwidth of wireless channels, Quality-of-Service (QoS) provisioning is an inherently complex and difficult issue. In this paper, we propose a fully distributed and adaptive algorithm to provide statistical QoS guarantees with respect to accessibility of services in an ad-hoc network. In this algorithm, we focus on the optimization of a new QoS parameter of interest, service efficiency, while keeping protocol overheads to the minimum. To achieve this goal, we first theoretically derive the lower and upper bounds of service efficiency based on a novel model for group mobility, followed by extensive simulation results to verify the effectiveness of our algorithm.

Keywords: Service placement

Wireless ad-hoc networks consist of mobile nodes interconnected by multi-hop wireless paths. Unlike conventional wireless networks, ad-hoc networks have no fixed network infrastructure or administrative support. Because of the dynamic nature of the network topology and limited bandwidth of wireless channels, Quality-of-Service (QoS) provisioning is an inherently complex and difficult issue. In this paper, we propose a fully distributed and adaptive algorithm to provide statistical QoS guarantees with respect to accessibility of services in an ad-hoc network. In this algorithm, we focus on the optimization of a new QoS parameter of interest, service efficiency, while keeping protocol overheads to the minimum. To achieve this goal, we theoretically derive the lower and upper bounds of service efficiency based on a novel model for group mobility, followed by extensive simulation results to verify the effectiveness of our algorithm.

Keywords: Mobile ad-hoc networks, Quality of Service, Group mobility

The advent of light-weight terminals (e.g., PDA) with integrated communication capabilities facilitates service access and hosting anytime, anywhere. However, effective service access requires dealing with the service's QoS, including related resource consumption. This paper introduces a comprehensive framework for QoS-aware service location in ad hoc networks. Our framework divides into: (i) QoS specification that is expressive enough to capture most significant QoS-related properties, and (ii) a benefit function for evaluating the overall benefit of service instances available in the network from the standpoint of QoS regarding both the user's perspective and resource consumption on hosts. Application of the proposed QoS framework is addressed in the context of the mobile AdHoc WS system, which supports QoS-aware location of Web services deployed in mobile ad hoc networks.

Keywords: QoS, MANET

Incentive scheme for stimulating service provision in Mobile Ad hoc NETworks (MANET) has been under intensive investigation due to its significance to the operation of MANET. This paper applies distributed algorithmic mechanism design and utilizes Vickrey auction for service allocation in mobile ad hoc networks.We show that our method stimulates service provision and achieves desired system-wide service allocation in spite of each agent's selfish behavior, while introducing challenges from the inherent shortcomings of Vickrey auction and characteristics of MANET. We discuss the challenges, the existing solutions for wireline networks and propose a system model for service allocation in MANET.

Keywords: Service placement

Service discovery is an important part of realization towards ubiquitous computing with self-configurable mobile ad hoc networks. However, it is faced by the challenge of network dynamics due to node mobility. In this paper, we propose a signal strength based service discovery framework in mobile ad hoc networks. Service discovery is carried out selectively along reliable links by monitoring the qualities of wireless connections to neighbor nodes. We show by simulation that, compared to non-selective distributed service discovery, our approach achieves higher service success ratio, less message overhead and shorter service discovery latency.

Keywords: QoS, MANET

This paper surveys expert systems (ES) development using a literature review and classification of articles from 1995 to 2004 with a keyword index and article abstract in order to explore how ES methodologies and applications have developed during this period. Based on the scope of 166 articles from 78 academic journals (retrieved from five online database) of ES applications, this paper surveys and classifies ES methodologies using the following eleven categories: rule-based systems, knowledge-based systems, neural networks, fuzzy ESs, object-oriented methodology, case-based reasoning, system architecture, intelligent agent systems, database methodology, modeling, and ontology together with their applications for different research and problem domains. Discussion is presented, indicating the followings future development directions for ES methodologies and applications: (1) ES methodologies are tending to develop towards expertise orientation and ES applications development is a problem-oriented domain. (2) It is suggested that different social science methodologies, such as psychology, cognitive science, and human behavior could implement ES as another kind of methodology. (3) The ability to continually change and obtain new understanding is the driving power of ES methodologies, and should be the ES application of future works.

Keywords: Expert Systems, Expert System Methodologies, Expert System Applications, Literature Survey

Keywords: Wireless Sensor Networks, Simulation

Event detection is a crucial task for wireless sensor network applications, especially environment monitoring. Existing approaches for event detection are mainly based on some predefined threshold values, and thus are often inaccurate and incapable of capturing complex events. For example, in coal mine monitoring scenarios, gas leakage or water osmosis can hardly be described by the overrun of specified attribute thresholds, but some complex pattern in the full-scale view of the environmental data. To address this issue, we propose a non-threshold based approach for the real 3D sensor monitoring environment. We employ energy-efficient methods to collect a time series of data maps from the sensor network and detect complex events through matching the gathered data to spatio-temporal data patterns. Finally, we conduct trace driven simulations to prove the efficacy and efficiency of this approach on detecting events of complex phenomena from real-life records.

Keywords: Distributed Event Detection

Multiple non-overlapped channels are available in IEEE 802.11 but are rarely used today in wireless multi-hop networks. Wireless mesh network is a special type of multi-hop ad hoc network and is envisioned to provide high capacity and large coverage. In this paper, we propose a 2-hop clustering based multi-interface, multi-channel network architecture and design a novel channel assignment algorithm and routing metric. Channel assignment is composed of Inter-cluster Static Assignment and Intra-cluster Dynamic Assignment. Since traditional routing metrics, such as hop-count, may not perform well in multi-channel wireless networks, we propose the CDM routing metric, which combines hop-count, channel diversity and channel switching capability together. Simulation results show that our algorithms achieve up to 3.3 times higher end-to-end throughput.

Keywords: Wireless multi-hop networks, wireless mesh networks, multi-channel, multi-interface, channel assignment, routing metric

The RINSE simulator is being developed to support large-scale network security preparedness and training exercises, involving hundreds of players and a modeled network composed of hundreds of LANs. The simulator must be able to present a realistic rendering of network behavior as attacks are launched and players diagnose events and try counter measures to keep network services operating. We describe the architecture and function of RINSE and outline how techniques like multi-resolution traffic modeling and new routing simulation methods are used to address the scalability challenges of this application. We also describe in more detail new work on CPU/memory models necessary for the exercise scenarios and a latency absorption technique that will help when extending the range of client tools usable by the players.

Keywords: Simulation, Security

This paper presents the Real-Time Event Detection Service using Data Service Middleware (DSWare). DSWare provides data-centric and group-based services for sensor networks. The real-time event service handles unreliability of individual sensor reports, correlation among different sensor observations, and inherent real-time characteristics of events. The event service supports confidence functions which are designed based on data semantics, including relative importance of subevents and historical patterns. When the failure rate is high, the event service enables partial detection of critical events to be reported in a timely manner. It can also be applied to differentiate between the occurrences of events and false alarms.

Keywords: Fence Monitoring

Accurate and scalable simulation has historically been a key enabling factor for systems research. We present TOSSIM, a simulator for TinyOS wireless sensor networks. By exploiting the sensor network domain and TinyOS's design, TOSSIM can capture network behavior at a high fidelity while scaling to thousands of nodes. By using a probabilistic bit error model for the network, TOSSIM remains simple and efficient, but expressive enough to capture a wide range of network interactions. Using TOSSIM, we have discovered several bugs in TinyOS, ranging from network bitlevel MAC interactions to queue overflows in an ad-hoc routing protocol. Through these and other evaluations, we show that detailed, scalable sensor network simulation is possible.

Keywords: Wireless Sensor Networks, Simulation

Service oriented middleware draws a lot of attention in current research on sensor networks. The automatic distribution of services within a network and the preservation of this distribution is a fundamental aspect of network applications with self-x properties. The network gains the ability to react on mobility, network fragmentation, node failures and new user demands. This paper proposes a distributed self-organizing algorithm for service distribution and preservation of this distribution using demanded coverages for the services. After discussing the theory of the convergence of the algorithm, this paper presents a real-world deployment of a sensor network scenario and evaluates the performance of the algorithm.

Keywords: Service Placement

Keywords: DES-Testbed

The ability of a sensor network to parse out observable activities into a set of distinguishable actions is a powerful feature that can potentially enable many applications of sensor networks to everyday life situations. In this paper we introduce a framework that uses a hierarchy of Probabilistic Context Free Grammars (PCFGs) to perform such parsing. The power of the framework comes from the hierarchical organization of grammars that allows the use of simple local sensor measurements for reasoning about more macroscopic behaviors. Our presentation describes how to use a set of phonemes to construct grammars and how to achieve distributed operation using a messaging model. The proposed framework is flexible. It can be mapped to a network hierarchy or can be applied sequentially and across the network to infer behaviors as they unfold in space and time. We demonstrate this functionality by inferring simple motion patterns using a sequence of simple direction vectors obtained from our camera sensor network testbed.

Keywords: Human Activity, Behavior Identification, PCFG, Sensor Grammars, Sensor Networks

Keywords: Wireless Sensor Networks, ScatterWeb

In this paper, we describe the design and implementation of a distributed operating system for ad hoc networks. Our system simplifies the programming of ad hoc networks and extends total system lifetime by making the entire network appear as a single virtual machine. It automatically and transparently partitions applications into components and dynamically finds them a placement on nodes within the network to reduce energy consumption and to increase system longevity. This paper describes our programming model, outlines the design and implementation of our system and examines the energy efficiency of our approach through extensive simulations as well as validation of a deployment on a physical testbed. We evaluate practical, power-aware, general-purpose algorithms for component placement and migration, and demonstrate that they can significantly increase system longevity by effectively distributing energy consumption and avoiding hotspots.

Keywords: Service placement

Technological advances and rapid development of the IEEE 802.11 standard have facilitated the growth of wireless local area networks (WLAN) and mobile computing. The throughput reached today by these networks (11 to 54 Mbits/s) allows to execute multimedia applications that require delay and throughput guarantees. Due to the bandwidth constraint and dynamic topology of Mobile Ad hoc NETworks (MANET), supporting Quality of Service (QoS) is a challenging task. A lot of research has been done on QoS in fixed networks (IntServ, RSVP or DiffServ) or wireless networks with access points (Mobile IP or UMTS), but most of them are not suitable for the MANET environment. This is due to the absence of centralized administration and the dynamic nature of network topology. The idea is then to support QoS at the routing level for such networks. For doing so, two approaches exist: the adaptation of the existing ad hoc routing protocols or the development of specific routing algorithms. This paper gives an outline on what is done in this field. We also propose a solution of QoS routing based on an extension of the AODV (Ad hoc One Demand Vector Distance) routing protocol. The proposed extension assumes the IEEE 802.11 DCF MAC layer as underlying technology.

Keywords: Ad hoc networks, QoS routing, AODV, IEEE 802.11

The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed), or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: “How can we determine in a distributed and scalable manner the number and location of service facilities?” We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative reoptimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.

Keywords: Service placement

Keywords: DES-Testbed

A mobile ad hoc network (MANET) is one composed of a set of mobile hosts capable of communicating with each other without the assistance of base stations. This paper considers the QoS (quality-of-service) routing problem in a MANET, which is important for many real-time multimedia applications. We propose an on-demand protocol for searching for a multi-path QoS route from a source host to a destination host in a MANET, where a multi-path is a network with a source and a sink satisfying certain bandwidth requirement. Existing works all tray to find a uni-path to the destination. The basic idea is to distribute a number of tickets from the source, which can be further partitioned into sub-tickets to search for a satisfactory multi-path. Through simulations, we justify that the value of our multi-path protocol is in its flexibility: (i) when the network bandwidth is very limited, it can offer a higher success rate to find a satisfactory QoS route than those protocols which try to find a uni-path, and (ii) when the network bandwidth is sufficient, it can perform almost the same as those protocols which try to find a uni-path (in both routing overhead and success rate).

Keywords: Mobile ad hoc network (MANET), Multi-path, Quality-of-service (QoS), Routing, Wireless Communication

Guaranteeing continuous streaming of multimedia data from service providers to the users is a challenging task in wireless ad hoc networks, particularly when node mobility is considered. The topological dynamics introduced by node mobility are further exacerbated by the natural grouping behavior of mobile users, which leads to frequent network partitioning. Network partitioning poses significant challenges to the provisioning of continuous multimedia streaming services in wireless ad hoc networks, since the partitioning disconnects many mobile users from the centralized streaming service. In this paper, we propose NonStop, a collection of novel middleware-based runtime algorithms that ensures the continuous availability of such multimedia streaming services, while minimizing the overhead involved. The network-wide continuous streaming coverage is achieved by partition prediction and service replication on the streaming sources, and assisted by distributed selection of streaming sources on regular mobile nodes and users. The proposed algorithms are validated by extensive results from performance evaluations.

Keywords: Multimedia streaming, service replication, wireless ad hoc networks

Energy consumption is a crucial characteristic of sensor networks and their applications as sensor nodes are commonly battery-driven. Although recent research focuses strongly on energy-aware applications and operating systems, energy consumption is still a limiting factor. Once sensor nodes are deployed, it is challenging and sometimes even impossible to change batteries. As a result, erroneous lifetime prediction causes high costs and may render a sensor network useless before its purpose is fulfilled.
In this paper, we present AEON (Accurate Prediction of Power Consumption), a novel evaluation tool to quantitatively predict energy consumption of sensor nodes and whole sensor networks. Our energy model, based on measurements of node current draw and the execution of real code, enables accurate prediction of the actual energy consumption of sensor nodes. Consequently, it prevents erroneous assumptions on node and network lifetime. Moreover, our detailed energy model allows to compare different low power and energy aware approaches in terms of energy efficiency. Thus, it enables a highly precise estimation of the overall lifetime of a sensor network.

Keywords: Simulation

Energy consumption is a crucial characteristic of sensor networks and their applications as sensor nodes are commonly battery-driven. Although recent research focuses strongly on energy-aware applications and operating systems, energy consumption is still a limiting factor. Once sensor nodes are deployed, it is challenging and sometimes even impossible to change batteries. As a result, erroneous lifetime prediction causes high costs and may render a sensor network useless before its purpose is fulfilled.
In this paper, we present AEON (Accurate Prediction of Power Consumption), a novel evaluation tool to quantitatively predict energy consumption of sensor nodes and whole sensor networks. Our energy model, based on measurements of node current draw and the execution of real code, enables accurate prediction of the actual energy consumption of sensor nodes. Consequently, it prevents erroneous assumptions on node and network lifetime. Moreover, our detailed energy model allows to compare different low power and energy aware approaches in terms of energy efficiency. Thus, it enables a highly precise estimation of the overall lifetime of a sensor network.

Keywords: Simulation accuracy

Mechanisms found in biological systems are in general robust and adapt well to changes in the environment. Therefore, many techniques that mimic certain behaviors found in nature have been implemented in computer science. Some of these techniques (artificial neural networks, simulated annealing, or genetic algorithms) perform well as optimization techniques for certain problem types, especially in the presence of incomplete or fuzzy input data.
In order to foster research on new information technology based on biologically inspired approaches, a project entitled “New Information Technologies for Building a Networked Symbiosis Environment” was initiated in 2002 at Osaka University in Japan.1 Close interdisciplinary collaboration with researchers from the fields of information science, bioinformatics, and applied mathematics made it possible to find abstractions of behavioral models of various living organisms and apply them to new control methods for communication networks, especially for peer-to-peer (P2P) networks, mobile ad hoc networks (MANETs), and sensor networks.

Keywords: Self-Organisation

Computer simulation is the most common approach to studying wireless ad-hoc routing algorithms. The results, however, are only as good as the models the simulation uses. One should not underestimate the importance of validation, as inaccurate models can lead to wrong conclusions. In this paper, we use direct-execution simulation to validate radio models used by ad-hoc routing protocols, against real-world experiments. This paper documents a common testbed that supports direct execution of a set of ad-hoc routing protocol implementations in a wireless network simulator. The testbed reads traces generated from real experiments, and uses them to drive direct-execution implementations of the routing protocols. Doing so we reproduce the same network conditions as in real experiments. By comparing routing behavior measured in real experiments with behavior computed by the simulation, we are able to validate the models of radio behavior upon which protocol behavior depends. We conclude that it is possible to have fairly accurate results using a simple radio model, but the routing behavior is quite sensitive to one of this model's parameters. The implication is that one should i) use a more complex radio model that explicitly models point-to-point path loss, or ii) use measurements from an environment typical of the one of interest, or iii) study behavior over a range of environments to identify sensitivities.

Keywords: Simulation accuracy

Computer simulation has been used extensively as an effective tool in the design and evaluation of systems. One should not, however, underestimate the importance of validation - the process of ensuring whether a simulation model is an appropriate representation of the real-world system. Validation of wireless network simulations is difficult due to strong interdependencies among protocols at different layers and uncertainty in the wireless environment. The authors present an approach of coupling direct-execution simulation and traces from real outdoor experiments to validating simple wireless models that are used commonly in simulations of wireless ad hoc networks. This article documents a common testbed that supports direct execution of a set of ad hoc routing protocol implementations in a wireless network simulator. By comparing routing behavior measured in the real experiment with behavior computed by the simulation, the authors validate the models of radio behavior upon which protocol behavior depends.

Keywords: Wireless network simulation, direct-execution simulation, trace-driven simulation, simulation verification and validation

This paper describes the architecture and programming model of a semantic-service-oriented sensor information system platform. We argue that the key to enabling scalable sensor information access is to define an ontology and associated sensor information hierarchy for interpretation of raw data streams. The ontological abstraction allows a sensing system to optimize its resource utilization in collecting, storing, and processing data. We describe the SONGS architecture that uses an automatic service planning to convert declarative user queries into a service composition graph, and performs compile-time and run-time optimizations for resource-aware execution of the service composite in a sensor network, building on the sensor information hierarchy. We motivate and demonstrate the SONGS platform using a parking garage example.

Keywords: Service placement

This paper presents preliminary quantitative results from data collected during runs of our multi-hop wireless ad hoc network testbed. The network successfully carried a composite workload including voice, bulk data, and real-time data. Careful analysis of recorded runs highlights radio propagation issues that network protocols will need to address in the future.

Keywords: Wireless Sensor Networks, Simulation

Keywords: Service placement

Stable and dependable IT services and infrastructures are of paramount importance for modern enterprises. Traditional solutions for managing and controlling the networked systems and services that sustain them appear to have reached their limits. As the number of hardware and software components to be managed increases, and as the dependencies between user-perceived services and the underlying networks and systems are ever more intricate and dynamic, management systems have become increasingly complex. They do not scale easily, are difficult to configure and use, and struggle to correlate service-level problems with problems in the underlying infrastructure. Even worse, the algorithms used in the management platforms (such as for event correlation) gradually shift from science to art. This trend brings into question the ability of existing management methodologies to cope with tomorrow's enterprise IT infrastructures and services.

Keywords: Self-Organisation

Keywords: Markets

The average number of joint hops in a shortest-path multicast tree from a root to arbitrary chosen group member nodes is studied. A general theory for all graphs, hence including the graph representation of the Internet, is presented which quantifies the multicast reduction in network links compared to m times unicast. For two special types of graphs, the random graph Gp(N) and the k-ary tree, exact and asymptotic results are derived. Comparing these explicit results with previously published Internet measurements [13] indicates that the number of routers in the Internet that can be reached from a root grows exponentially in the number of hops with an effective degree of approximately 3.2.

Keywords: Efficiency, k-ary tree, multicast, random graph

Keywords: Wireless networks, survey

This Reference Model for Service Oriented Architecture is an abstract framework for understanding significant entities and relationships between them within a service-oriented environment, and for the development of consistent standards or specifications supporting that environment. It is based on unifying concepts of SOA and may be used by architects developing specific service oriented architectures or in training and explaining SOA.
A reference model is not directly tied to any standards, technologies or other concrete implementation details. It does seek to provide a common semantics that can be used unambiguously across and between different implementations. The relationship between the Reference Model and particular architectures, technologies and other aspects of SOA is illustrated in Figure 1.
While service-orientation may be a popular concept found in a broad variety of applications, this reference model focuses on the field of software architecture. The concepts and relationships described may apply to other “service” environments; however, this specification makes no attempt to completely account for use outside of the software domain.

Keywords: Service Placement

We propose CLEAR (Context and Location-based Efficient Allocation of Replicas), a dynamic replica allocation scheme for improving data availability in mobile ad-hoc peer-to-peer (M-P2P) networks. CLEAR exploits user mobility patterns and deploys a super-peer architecture to manage replica allocation efficiently. CLEAR avoids broadcast storm during replica allocation and eliminates the need for broadcast-based querying. CLEAR considers different levels of replica consistency and load as replica allocation criteria. Our performance study indicates CLEAR's effectiveness in improving data availability in M-P2P networks.

Keywords: Service placement

In this paper three recurrent neural network algorithms are proposed for the p-median problem according to different techniques. The competitive recurrent neural network, based on two types of decision variables (location variables and allocation variables), consists of a single layer of 2N p process units (neurons), where N is the number of demand points or customers and p is the number of facilities (medians). The process units form N + p groups, where one neuron per group is active at the same time and neurons in the same group are updated in parallel. Moreover, the energy function (objective function) always decreases as the system evolves according to the dynamical rule proposed. The effectiveness and effciency of the three algorithms under varying problem sizes are analyzed. The results indicate that the best technique depend on the scale of the problem and the number of medians.

Keywords: Service Placement

Keywords: DNS

Keywords: DNS

Keywords: Context

Keywords: Context

Mobile ad hoc networks (MANETs) define a challenging computing scenario where access to resources is restrained by connectivity among hosts. Replication offers an opportunity to increase data availability beyond the span of transient connections. Unfortunately, standard replication techniques for wired environments mostly target improvements to fault-tolerance and access time, and in general are not well-suited to the dynamic environment defined by MANETs.
In this paper we explore replication for mobility in the context of a veneer for Lime, a Linda-based middleware for MANETs. This veneer puts into the hands of the application programmer control over what to replicate as well as a set of novel replication and consistency modes meaningful in mobile ad hoc networks. The entire replication veneer is built on top of the existing Lime model and implementation, confirming their versatility.

Keywords: Data placement

This paper reports on the implementation, design and results from GlacsWeb, an environmental sensor network for glaciers installed in Summer 2004 at Briksdalsbreen, Norway. The importance of design factors that influenced the development of the overall system, its general architecture and communication systems are highlighted.

Keywords: Low Power, Radio Communications, Environmental Monitoring, Glaciology, Sensor Networks

The current state of the art in evaluating applications and communication protocols for ad hoc wireless networks involves either simulation or small-scale live deployment. While larger scale deployment has been performed, it is typically costly and difficult to run under controlled circumstances. Simulation allows researchers to vary system configurations such as MAC layers and routing protocols. However, it requires the duplication of application, operating system, and network behavior within the simulator. While simulation and live deployment will clearly continue to play important roles in the design and evaluation of mobile systems, we present MobiNet, a third point in this space. In MobiNet, the communication of unmodified applications running on stock operating systems is subject to the real-time emulation of a user-specified wireless network environment. MobiNet utilizes a cluster of emulator nodes to appropriately delay, drop or deliver packets in a hop by hop fashion based on MAC-layer protocols, ad hoc routing protocols, congestion, queuing, and available bandwidth in the network. MobiNet infrastructure is extensible, facilitating the development and evaluation of new MAC layers, routing protocols, mobility and traffic models. Our evaluations show that MobiNet emulation is scalable and accurate while executing real code, including video playback.

Keywords: Wireless Sensor Networks, Simulation

The current state of the art in evaluating applications and communication protocols for ad hoc wireless networks usually involves either simulation or small-scale live deployment. Larger-scale live deployment is typically costly and difficult to run under controlled circumstances. Simulation allows more flexibility in varying system configurations, but requires the duplication of application and network behavior within the simulator. While simulation and live deployment will clearly continue to play important roles in the evaluation of mobile systems, we present MobiNet, a third point in this space. In MobiNet, the communication of unmodified applications running on stock operating systems is subject to the real-time emulation of a user-specified wireless network environment. MobiNet utilizes a cluster of emulator nodes to appropriately delay, drop or deliver packets in a hop by hop fashion based on MAC-layer protocols, ad hoc routing protocols, congestion, queuing, and available bandwidth in the network. Our evaluations show that MobiNet emulation is scalable and accurate while executing real code, including video playback.

Keywords: Wireless Sensor Networks, Simulation

The new ARPANET routing algorithm is an improvement over the old procedure in that it uses fewer network resources, operates on more realistic estimates of network conditions, reacts faster to important network changes, and does not suffer from long-term loops or oscillations. In the new procedure, each node in the network maintains a database describing the complete network topology and the delays on all lines, and uses the database describing the network to generate a tree representing the minimum delay paths from a given root node to every other network node. Because the traffic in the network can be quite variable, each node periodically measures the delays along its outgoing lines and forwards this information to all other nodes. The delay information propagates quickly through the network so that all nodes can update their databases and continue to route traffic in a consistent and efficient manner.
An extensive series of tests were conducted on the ARPANET, showing that line overhead and CPU overhead are both less than two percent, most nodes learn of an update within 100 ms, and the algorithm detects congestion and routes packets around congested areas.

Keywords: Routing

Wireless sensor networks have the potential to become significant subsystems of engineering applications. Before relegating important and safety-critical tasks to such subsystems, it is necessary to understand the dynamic behavior of these subsystems in simulation environments. There is an urgent need to develop simulation platforms that are useful to explore both the networking issues and the distributed computing aspects of wireless sensor networks. Current efforts to simulating wireless sensor networks largely focus on the networking issues. These approaches use well-known network simulation tools that are difficult to extend to explore distributed computing issues.
Discrete-event simulation is a trusted platform for modeling and simulating a variety of systems. We report results obtained from a new simulator for wireless sensor networks networks that is based on the discrete event simulation framework called OMNeT++. Work is underway to develop a simulation platform that allows developers and researchers to investigate topological, phenomenological, networking, robustness and scaling issues related to wireless sensor networks. As a first step, we have developed simulations for the 802.11 MAC and the well-known sensor network protocol called Directed Diffusion. We demonstrate the performance of our simulator by comparing its performance to that of the well-known simulator ns2. Our results indicate that our simulator executes at least an order of magnitude faster than NS-2 and makes more efficient use of the available memory. The ease of modifying the sensor network and scalability, which is defined as the number of nodes that can be simulated, are two distinguishing features of our simulator.

Keywords: Sensor Network, Performance Evaluation, Simulation

Long-term deployments of wireless sensor networks so far have been focused on the periodic gathering of simple sensor readings. However, technological advances allow working with more complex types of data that also create larger data volumes. In this paper we use a real world engineering application to identify a series of challenges related to complex data processing in sensor networks. We present a classification of these challenges and outline a set of preliminary solutions that we are currently in the process of developing for our motivating application.

Keywords: Sensor networks, Data processing, Challenges

Wireless sensor networks are currently a viable field of active research. In sensor networks, communication often resembles the publish/subscribe paradigm where source nodes publish data which is subsequently delivered to a set of subscribed sink nodes. We propose to extend routing algorithms known from publish/subscribe systems with data propagation based on the evaluation of the sensed values over time to make them suitable for sensor networks.

Keywords: Wireless Sensor Networks

In this paper, we initiate the study of the approximability of the facility location problem in a distributed setting. In particular, we explore a trade-off between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(sqrt(k)(mp)^(1/sqrt(k)) log (m+n)) approximation in O(k) communication rounds where message size is bounded to O(log n) bits. The number of facilities and clients are m and n, respectively, and p is a coefficient that depends on the cost values of the instance. Our technique is based on a distributed primal-dual approach for approximating a linear program, that does not form a covering or packing program.

Keywords: facility location, distributed approximation, linear programming, primal-dual algorithms

As interest in the networking community turns to increasingly complicated networks run over increasingly long simulation times, performance differences in network simulators increasingly matter. Characteristics of concern include execution speed, size of model that can be simulated, and scalability - how those abilities change as the problem size and simulation engine increase in capability. In January 2002 a paper was published in the CNDS conference discussing the scalability of the simulation tool JavaSim, and that of ns2 SSFNet. We reexamine those experiments, and show that the experimental methodology does not increase intrinsic workload as the model size grows. We furthermore find that the experimental design pushes all the simulators into regimes for which they were not designed, resulting in atypical behavior for each. After modifying the simulators, we reexamine the original experiments, and new experiments that increase the intrinsic workload with increasing model size. We find that (i) ns2 is fastest, but requires the most memory, (ii) JavaSim is significantly slower than the other simulators, but requires significantly less memory than the Java implementation of SSFNet, (iii) that a C++ implementation of SSFNet is nearly as fast as ns2, and uses the least memory among all the simulators.

Keywords: Scalability, SSF, ns, Javasim

A variety of network simulation tools are available today, each with its own functionality, memory demand and execution speed characteristics. Different tools are optimized for different purposes and different audiences. Nevertheless, significant differences in these characteristics creates the problem of qualifying user objectives under which a faster simulator that uses more memory is more “useful” than a slower simulation that uses less memory, and vice-versa. Our study is motivated by examination of performance characteristics of four simulators : JavaSim, ns, SSFNet-Java, and SSFNet-C++. Our approach considers “utility functions” that a user might develop to quantify his view of the speed/memory/functionality tradeoffs. We consider general properties such functions might have, and explore how these properties lead utility to favor one simulator over another. Finally, we apply utility theory to the four simulators that motivated the study, and observe that a balance of speed and model size capability tends to maximize performance.

Keywords: Simulation

All analytical and simulation research on ad hoc wireless networks must necessarily model radio propagation using simplifying assumptions. A growing body of research, however, indicates that the behavior of the protocol stack may depend significantly on these underlying assumptions. The standard response to this problem is a call for more realism in designing radio models. But how much realism is enough? This study is the first to approach this question by validating simulator performance (both at the physical and application layers) against the results of real-world data. Referencing an extensive set of measurements from a large outdoor routing experiment, we start by evaluating the relative realism of common assumptions made in radio model design, identifying which provide a reasonable approximation of reality. Though several such investigations exist for static sensor networks, radio behavior in mobile network deployments is a much less studied topic. We then reproduce our experimental setup in our simulator, and generate the same application-layer metrics under progressively smaller sets of these assumptions. By comparing the simulated outcome to the outcome of our experiment, we are able to discern at what point our balance of simplification and realism captures the real behavior of our target environment.

Keywords: Simulation accuracy

Keywords: Simulation

Subjecting a mobile computing system to wireless network conditions that are realistic yet reproducible is a challenging problem. In this paper, we describe a technique called trace modulation that re-creates the observed end-to-end characteristics of a real wireless network in a controlled and repeatable manner. Trace modulation is transparent to applications and accounts for all network traffic sent or received by the system under test. We present results that show that it is indeed capable of reproducing wireless network performance faithfully.

Keywords: Simulation

Broadcasting is a common operation in a network to resolve many issues. In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal). Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we refer as the broadcast storm problem. In this paper, we identify this problem by showing how serious it is through analyses and simulations. We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem. Simulation results are presented, which show different levels of improvement over the basic flooding approach.

Keywords: Broadcast, Communication, Mobile Ad Hoc Network (MANET), Mobile Computing, Wireless Network

Keywords: Simulation accuracy

This report introduces a new sensor network simulator for the Contiki OS - the COOJA Simulator.
The Contiki OS is a portable operating system designed specifically for resource limited devices such as sensor nodes. It is built around an event-driven kernel but supports pre-emptive multithreading at a per-process basis. It also supports a full TCP/IP stack via uIP and the programming abstraction Protothreads.
The main design goal of the COOJA Simulator is extendibility, for which Interfaces and Plugins are used. An Interface represents a sensor node property or device, such as a position, a button or a radio transmitter. A Plugin is used to interact with a simulation, for example to control the simulation speed or to watch all network traffic between the simulated nodes. Both new Plugins and Interfaces can easily be created and added to the simulation environment. A number of other parts of the simulator, for example a radio medium responsible for forwarding radio network data, can also be implemented and added to the simulator. And by supporting several different simulation environments at the same time in one simulation, different underlying hardware platforms can be simulated in heterogeneous networks.
Java Native Interface is used to connect the new simulator with Contiki, allowing simulated applications to run in a real Contiki system. By using this approach, any simulated application can then be run on a real sensor node unaltered.

Keywords: Sensor Networks, Contiki, Simulator

Simulators for wireless sensor networks are a valuable tool for system development. However, current simulators can only simulate a single level of a system at once. This makes system development and evolution difficult since developers cannot use the same simulator for both high-level algorithm development and low-level development such as device-driver implementations.
We propose cross-level simulation, a novel type of wireless sensor network simulation that enables holistic simultaneous simulation at different levels. We present an implementation of such a simulator, COOJA, a simulator for the Contiki sensor node operating system. COOJA allows for simultaneous simulation at the network level, the operating system level, and the machine code instruction set level. With COOJA, we show the feasibility of the cross-level simulation approach.

Keywords: Simulation accuracy

Scalable service placement is a challenging problem in dynamic environments such as ad hoc or autonomic networks. Existing approaches typically consider static and reduced size networking environments and try to determine the optimal service position (the node at which some cost is minimized) by solving the 1-median problem. Since such approaches are complex and are based on global information knowledge, they are nonscalable and cannot cope with dynamic environments. A more reasonable approach to service placement for large, ad hoc and autonomic environments would be through service migration. That is, instead of solving continuously a large optimization problem requiring global information, consider policies for moving the service position (one hop/node at a time) based on local information, towards more effective positions. Developing service migration policies with good properties is a major challenge, since such policies may be sub-optimal (that is, they never converge to the optimal position), follow a non-monotonically cost decreasing path to the optimal position, etc.
In this paper, the aforementioned issues are discussed and a simple service migration policy is proposed for undirected tree topologies. For this case it is shown analytically that the information available at the current service node only is sufficient for determining the direction towards nodes with monotonically decreasing service provision costs. Consequently, the proposed policy moves the service continuously towards the optimal position in every step and reaches the optimal position through a shortest path migration trajectory. As the optimal position may change in a dynamic environment, the proposed policy adapts the service migration path continuously towards the currently optimal position. Although some of the main results are also applicable to general network topologies, future work will focus on the general network topology by borrowing ideas from the current work.

Keywords: Service, placement, migration

An ad-hoc network is the cooperative engagement of a collection of Mobile Hosts without the required intervention of any centralized Access Point. In this paper we present an innovative design for the operation of such ad-hoc networks. The basic idea of the design is to operate each Mobile Host as a specialized router, which periodically advertises its view of the interconnection topology with other Mobile Hosts within the network. This amounts to a new sort of routing protocol. We have investigated modifications to the basic Bellman-Ford routing mechanisms, as specified by RIP [5], to make it suitable for a dynamic and self-starting network mechanism as is required by users wishing to utilize ad-hoc networks. Our modifications address some of the previous objections to the use of Bellman-Ford, related to the poor looping properties of such algorithms in the face of broken links and the resulting time dependent nature of the interconnection topology describing the links between the Mobile Hosts. Finally, we describe the ways in which the basic network-layer routing can be modified to provide MAC-layer support for ad-hoc networks.

Keywords: Wireless Sensor Networks, Routing

We present a new distributed routing protocol for mobile, multihop, wireless networks. The protocol is one of a family of protocols which we term “link reversal” algorithms. The protocol's reaction is structured as a temporally-ordered sequence of diffusing computations; each computation consisting of a sequence of directed link reversals. The protocol is highly adaptive, efficient and scalable; being best-suited for use in large, dense, mobile networks. In these networks, the protocol's reaction to link failures typically involves only a localized “single pass” of the distributed algorithm. This capability is unique among protocols which are stable in the face of network partitions, and results in the protocol's high degree of adaptivity . This desirable behavior is achieved through the novel use of a “physical or logical clock” to establish the “temporal order” of topological change events which is used to structure (or order) the algorithm's reaction to topological changes. We refer to the protocol as the Temporally-Ordered Routing Algorithm (TORA).

Keywords: Wireless Sensor Networks, Routing

Keywords: Service placement

Keywords: Ad hoc networking

Mobile agents are enjoying a lot of popularity as a novel abstraction for structuring distributed applications. In this paper, we provide an introduction to the related research field by showing evidence of the benefits mobile agents can potentially achieve, illustrating the foundations of architectures and technologies for mobile agents, and discussing some of the open issues still hampering a wider acceptance of this paradigm.

Keywords: Mobile agent, mobile code, design paradigm

Keywords: Wireless Sensor Networks, Virtual Machine

Keywords: Wireless Sensor Networks, Context

In telecommunication networks, as in many other areas of science and engineering, proliferation of computers as research tools has resulted in the adoption of computer simulation as the most commonly used paradigm of scientific investigations. This, together with a plethora of existing simulation languages and packages, has created a popular opinion that simulation is mainly an exercise in computer programming. In new computing environments, programming can be minimized, or even fully replaced, by the manipulation of icons (representing pre-built programming objects containing basic functional blocks of simulated systems) on a computer monitor. One can say that we have witnessed another success of modern science and technology: the emergence of wonderful and powerful tools for exploring and predicting the behavior of such complex, stochastic dynamic systems as telecommunication networks.
But this enthusiasm is not shared by all researchers in this area. An opinion is spreading that one cannot rely on the majority of the published results on performance evaluation studies of telecommunication networks based on stochastic simulation, since they lack credibility. Indeed, the spread of this phenomenon is so wide that one can speak about a deep crisis of credibility. In this paper, this claim is supported by the results of a survey of over 2200 publications on telecommunication networks in recent proceedings of the IEEE INFOCOM and such journals as the IEEE Transactions on Communications, the IEEE/ACM Transactions on Networking, and the Performance Evaluation Journal.

Keywords: Stochastic Simulation, Simulation of Telecommunication Networks, Credibility of Simulation

Web services are increasingly used for deploying Web-based application portals such as eBay and Amazon.com. They are commonly built using middleware, that is, composable building blocks such as HTTP containers, Java-based application beans, and persistent state management. These components are distributed across tiers of servers - Web, application, and database. As Web services offer newer and more sophisticated functionality, the underlying realization of those services in the middleware becomes more complicated. Today's Web services can consist of dozens or hundreds of request types and middleware components. Identifying the correlated effects between components to improve response to overload.

Keywords: Self-Organisation

The project MarathonNet develops wireless sensor networks for monitoring runners during marathon events. The application requires a high degree of connectivity in order to provide actual data for runners and spectators. Depending on the distribution of the runners on the track, the communication range and the number of base stations network partitions might occur that reduce connectivity. To investigate these dependencies in detail we conducted various simulations on connectivity. In this paper we first introduce the application scenario and discuss the impact of the different parameters and their interrelations. We then present the simulation results and discuss their consequences for the application design.

Keywords: Wireless Sensor Network, Deployment

The new generation mobile systems are anticipated to provide mobile users with new broadband services such as wireless multimedia, including real-time video and high-speed data. In these systems, the requirement on service transparency placed by the handling of mobility, both personal and terminal, implies a remarkable increase in the complexity of data management. Therefore, appropriate distributed databases (DDB) must be designed to guarantee speed in the processing and updating of user information, and a high level of reliability and performance. In this paper we analyze a minimally replicated DDB in which different strategies for the redundancy of user data are discussed. First, we develop a Petri net based model in order to analyze the consequences on dependability deriving from faults in nodes at different levels in the DDB structure. Then, we investigate the performance offered by the system through a queuing network model. The measures of interest include reliability, availability, mean time to failure, and mean response time to service access.

Keywords: Data replication

An ad-hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. In this paper we present Ad-hoc On Demand Distance Vector Routing (AODV), a novel algorithm for the operation of such ad-hoc networks. Each Mobile Host operates as a specialized router, and routes are obtained as needed (i.e., on-demand) with little or no reliance on periodic advertisements. Our new routing algorithm is quite suitable for a dynamic selfstarting network, as required by users wishing to utilize ad-hoc networks. AODV provides loop-free routes even while repairing broken links. Because the protocol does not require global periodic routing advertisements, the demand on the overall bandwidth available to the mobile nodes is substantially less than in those protocols that do necessitate such advertisements. Nevertheless we can still maintain most of the advantages of basic distance-vector routing mechanisms. We show that our algorithm scales to large populations of mobile nodes wishing to form ad-hoc networks. We also include an evaluation methodology and simulation results to verify the operation of our algorithm.

Keywords: Ad-Hoc Networking, Distance Vector Routing, Dynamic Routing, Mobile Networking, Wireless Networks

Keywords: Expert Systems, Verification

Recent advances in low-power embedded processors, radios, and micro-mechanical systems (MEMs) have made possible the development of networks of wirelessly interconnected sensors. With their focus on applications requiring tight coupling with the physical world, as opposed to the personal communication focus of conventional wireless networks, these wireless sensor networks pose significantly different design, implementation, and deployment challenges. In this paper, we present a set of models and techniques that are embodied in a simulation tool for modeling wireless sensor networks. Our work builds up on the infrastructure provided by the widely used ns-2 simulator, and adds a suite of new features and techniques that are specific to wireless sensor networks. These features introduce the notion of a sensing channel through which sensors detect targets, and provide detailed models for evaluating energy consumption and battery lifetime.

Keywords: Wireless Sensor Networks, Simulation

Keywords: Simulation accuracy

Many enterprises are beginning to exploit large shared resource pools in data center environments to lower their infrastructure and management costs. These environments may have tens, hundreds, or even thousands of server resources. Capacity management for resource pools decides how many resources are needed to support a given set of application workloads, which applications must be assigned to each resource, and per-application scheduling parameters to ensure appropriate sharing and isolation for the applications. Capacity management is a challenging task for shared environments that currently requires significant manual effort and tends to overprovision resources. Here, we describe our approach to automate the steps of a capacity self-management system that best matches resource supply with demand.

Keywords: Self-Organisation

Even though multiple non-overlapped channels exist in the 2.4GHz and 5GHz spectrum, most IEEE 802.11-based multi-hop ad hoc networks today use only a single channel. As a result, these networks rarely can fully exploit the aggregate bandwidth available in the radio spectrum provisioned by the standards. This prevents them from being used as an ISP’s wireless last-mile access network or as a wireless enterprise backbone network. In this paper, we propose a multi-channel wireless mesh network (WMN) architecture (called Hyacinth) that equips each mesh network node with multiple 802.11 network interface cards (NICs). The central design issues of this multi-channel WMN architecture are channel assignment and routing. We show that intelligent channel assignment is critical to Hyacinth’s performance, present distributed algorithms that utilize only local traffic load information to dynamically assign channels and to route packets, and compare their performance against a centralized algorithm that performs the same functions. Through an extensive simulation study, we show that even with just 2 NICs on each node, it is possible to improve the network throughput by a factor of 6 to 7 when compared with the conventional single-channel ad hoc network architecture. We also describe and evaluate a 9-node Hyacinth prototype that is built using commodity PCs each equipped with two 802.11a NICs.

Keywords: System design, Distributed Algorithms/Protocols, Simulations, Prototype Implementation.

The p-median problem is a network problem that was originally designed for, and has been extensively applied to, facility location. In this bibliography, we summarize the literature on solution methods for the uncapacitated and capacitated p-median problem on a network.

Keywords: Service Placement

Wireless ad hoc networks of sensor nodes are envisioned to be deployed in the physical environment to monitor a wide variety of real-world phenomena. Almost any sensor network application requires some form of selfconfiguration, where sensor nodes take on specific functions or roles in the network without manual intervention. These roles may be based on varying sensor node properties (e.g., available sensors, location, network neighbors) and may be used to support applications requiring heterogeneous node functionality (e.g., clustering, data aggregation). In this paper we argue that the assignment of user-defined roles is a fundamental part of a wide range of sensor network applications. Consequently, a framework for assignment of roles to sensor nodes in an application-specific manner could significantly ease sensor network programming. We outline the general structure of such a framework and present a first approach to its realization. We demonstrate its utility and feasibility using a number of concrete examples.

Keywords: Wireless Sensor Networks, Middleware

The primary performance objective of a broadcast scheme in an ad-hoc wireless network is to reduce the total number of retransmissions needed to reach all nodes. Another (less appreciated) measure of interest is the broadcast latency, i.e., the amount of time required to complete the operation. We point out the tradeoff between the two measures and show how to significantly reduce the broadcast latency in networks whose MAC schemes are derivatives of IEEE 802.11.

Keywords: Ad-hoc Networks, Broadcast, Medium Access Control

The IEEE 802.11 Wireless LAN standards allow multiple non-overlapping frequency channels to be used simultaneously to increase the aggregate bandwidth available to end-users. Such bandwidth aggregation capability is routinely used in infrastructure mode operation, where the traffic to and from wireless nodes is distributed among multiple interfaces of an access point or among multiple access points to balance the traffic load. However, bandwidth aggregation is rarely used in the context of multi-hop 802.11-based LANs that operate in the ad hoc mode. Most past research efforts that attempt to exploit multiple radio channels require modifications to the MAC protocol and therefore do not work with commodity 802.11 interface hardware. In this paper, we propose and evaluate one of the first multi-channel multi-hop wireless ad-hoc network architectures that can be built using standard 802.11 hardware by equipping each node with multiple network interface cards (NICs) operating on different channels. We focus our attention on wireless mesh networks that serve as the backbone for relaying end-user traffic from wireless access points to the wired network. The idea of exploiting multiple channels is particularly appealing in wireless mesh networks because of their high capacity requirements to support backbone traffic. To reap the full performance potential of this architecture, we develop a set of centralized channel assignment, bandwidth allocation, and routing algorithms for multi-channel wireless mesh networks. A detailed performance evaluation shows that with intelligent channel and bandwidth assignment, equipping every wireless mesh network node with just 2 NICs operating on different channels can increase the total network goodput by a factor of up to 8 compared with the conventional single-channel ad hoc network architecture.

Keywords: Channel Assignment

Network protocols are usually tested in operational networks or in simulated environments. With the former approach it is not easy to set and control the various operational parameters such as bandwidth, delays, queue sizes. Simulators are easier to control, but they are often only an approximate model of the desired setting, especially for what regards the various traffic generators (both producers and consumers) and their interaction with the protocol itself.
In this paper we show how a simple, yet flexible and accurate network simulator - dummynet - can be built with minimal modifications to an existing protocol stack, allowing experiments to be run on a standalone system. dummynet works by intercepting communications of the protocol layer under test and simulating the effects of finite queues, bandwidth limitations and communication delays. It runs in a fully operational system, hence allowing the use of real traffic generators and protocol implementations, while solving the problem of simulating unusual environments. With our tool, doing experiments with network protocols is as simple as running the desired set of applications on a workstation.
A FreeBSD implementation of dummynet, targeted to TCP, is available from the author. This implementation is highly portable and compatible with other BSD-derived systems, and takes less than 300 lines of kernel code.

Keywords: Protocol Evaluation, TCP/IP, Simulation

In this paper we present a couple of tools developed by the author on FreeBSD, and available from the author's Web page in source format. The first one, called dummynet, is a tool designed for the performance evaluation of network protocols and applications. Despite its original design goal, there has been a lot of interest on using dummynet as a bandwidth manager in network servers. dummynet simulates the effect of finite queues, bandwidth limitations, and queuing delays, and is embedded in the protocol stack of the host, allowing even complex experiments to be run on a single machine, using existing applications and protocol implementations.
The second tool is a software implementation of an erasure code especially suited for use in network protocols. Erasure codes are used in Forward Error Correction (FEC) techniques to reduce or remove the need for retransmissions in presence of communication errors. FEC has been rarely used in network protocols, because of the encoding/decoding overhead is acceptable for many applications even on low-end machines.

Keywords: Simulation

Middleware for sensor networks aims to support the development of applications for large populations of wirelessly connected nodes capable of computation, communication, and sensing. We examine the purpose, functionality, and characteristics of such middleware.

Keywords: Wireless Sensor Networks, Middleware

Wireless sensor networks can be considered as a tool for detecting certain states in the real world. We examine the use of event-based approaches for this task. In the literature, a number of event notification systems have been presented that facilitate the specification and automatic detection of event patterns - so-called composite events. While events are a valuable abstraction in sensor networks, we show that composite events are less suited to detect real-world states with sensor networks. We illustrate an alternate solution that retains the advantages of an event-based approach, but which provides better support for the specification and detection of real-world states.

Keywords: Fence Monitoring

In the recent past, wireless sensor networks have found their way into a wide variety of applications and systems with vastly varying requirements and characteristics. As a consequence, it is becoming increasingly difficult to discuss typical requirements regarding hardware issues and software support. This is particularly problematic in a multidisciplinary research area such as wireless sensor networks, where close collaboration between users, application domain experts, hardware designers, and software developers is needed to implement efficient systems. In this paper we discuss the consequences of this fact with regard to the design space of wireless sensor networks by considering its various dimensions. We justify our view by demonstrating that specific existing applications occupy different points in the design space.

Keywords: Wireless Sensor Networks, Deployment

Campus and enterprise wireless networks are increasingly characterized by ubiquitous coverage and rising traffic demands. Efficiently assigning channels to access points (APs) in these networks can significantly affect the performance and capacity of the WLANs. The state-of-the-art approaches assign channels statically, without considering prevailing traffic demands. In this paper, we show that the quality of a channel assignment can be improved significantly by incorporating observed traffic demands at APs and clients into the assignment process. We refer to this as traffic-aware channel assignment. We conduct extensive trace-driven and synthetic simulations and identify deployment scenarios where traffic-awareness is likely to be of great help, and scenarios where the benefit is minimal. We address key practical issues in using traffic-awareness, including measuring an interference graph, handling non-binary interference, collecting traffic demands, and predicting future demands based on historical information. We present an implementation of our assignment scheme for a 25-node WLAN testbed. Our testbed experiments show that traffic-aware assignment offers superior network performance under a wide range of real network configurations. On the whole, our approach is simple yet effective. It can be incorporated into existing WLANs with little modification to existing wireless nodes and infrastructure.

Keywords: Channel Assignment

Let UTM(m,n) be the class of universal Turing machines with m states and n symbols. Universal Turing machines are proved to exist in the following classes: UTM(24,2), UTM(10,3), UTM(7,4), UTM(5,5), UTM(4,6), UTM(3,10) and UTM(2,18).

Keywords: Turing Machine

We consider a directed network in which every edge possesses a latency function specifying the time needed to traverse the edge given its congestion. Selfish, noncooperative agents constitute the network traffic and wish to travel from a source s to a sink t as quickly as possible. Since the route chosen by one network user affects the congestion (and hence the latency) experienced by others, we model the problem as a noncooperative game. Assuming each agent controls only a negligible portion of the overall traffic, Nash equilibria in this noncooperative game correspond to s-t flows in which all flow paths have equal latency.
A natural measure for the performance of a network used by selfish agents is the common latency experienced by each user in a Nash equilibrium. It is a counterintuitive but well-known fact that removing edges from a network may improve its performance; the most famous example of this phenomenon is the so-called Braess's Paradox. This fact motivates the following network design problem: given such a network, which edges should be removed to obtain the best possible flow at Nash equilibrium? Equivalently, given a large network of candidate edges to be built, which subnetwork will exhibit the best performance when used selfishly?
We give optimal inapproximability results and approximation algorithms for several network design problems of this type. For example, we prove that for networks with n nodes and continuous, nondecreasing latency functions, there is no approximation algorithm for this problem with approximation ratio less than n=2 (unless P = NP). We also prove this hardness result to be best possible by exhibiting an n/2-approximation algorithm. For networks in which the latency of each edge is a linear function of the congestion, we prove that there is no (4/3-e)-approximation algorithm for the problem (for any e > 0, unless P = NP); the existence of a 4/3-approximation algorithm follows easily from existing work, proving this hardness result sharp.
Moreover, we prove that an optimal approximation algorithm for these problems is what we call the trivial algorithm: given a network of candidate edges, build the entire network. Roughly, this result implies that the presence of harmful extra edges in a network (a phenomenon that can lead to extremely poor performance in large networks with general latency functions) is impossible to detect efficiently.

Keywords: Routing

Keywords: Facility Location Theory

Keywords: Wireless Sensor Networks

In complex concurrent critical systems, such as autonomous robots, unmanned air vehicles, and space systems, every component is a potential point of failure. This is true not only of embedded systems but also of purely software systems such as distributed and cyber applications. Typical attempts to make such systems more robust and secure are both brittle and incomplete due to reliance on manual identification of and solutions to potential failures such as by using exception mechanisms. That is, the security is easily broken, and there are many possible failure modes that are not handled. Failures may be rare events so it is less easy to test for good coverage of fault scenarios. Techniques that expand to handling component - level failures are very expensive to apply, yet are still quite brittle and incomplete. This is not because engineers are lazy - the sheer size and complexity of modern information systems overwhelms the attempts of engineers, and myriad methodologies, to systematically investigate, identify, and specify a response to all possible failures of a system.

Keywords: Self-Organisation

The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean relaxation. Variable fixing tests are used to reduce the size of the problems and a local search procedure is also applied. Variable fixing strategies eliminate 90% of arcs on average. Computational results are reported for large graph instances with about 4000 nodes and 14 millions arcs.

Keywords: Service Placement

This paper describes an advanced simulation environment which is used to examine, validate, and predict the performance of mobile wireless network systems. This simulation environment overcomes many of the limitations found with analytical models, experimentation, and other commercial network simulators available on the market today. We identify a set of components which make up mobile wireless systems and describe a set of flexible modules which can be used to model the various components and their integration. These models are developed using the Maisie simulation language. By modeling the various components and their integration, this simulation environment is able to accurately predict the performance bottlenecks of a multimedia wireless network system being developed at UCLA, determine the trade-off point between the various bottlenecks, and provide performance measurements and validation of algorithms which are not possible through experimentation and too complex for analysis.

Keywords: Wireless Networks, Simulation

Service discovery in Ubiquitous Computing is a task which has to be done frequently due to dynamically changing environments. The limited battery power of mobile devices requires us to optimize frequent and energy costly tasks, especially the ones incurring in communication activities. In this paper we present a novel service discovery algorithm based on node clustering. Nodes within a cluster may sleep to save energy when idle. A clusterhead node is always active and answers discovery requests on behalf of other nodes to achieve low discovery latencies. Simulation experiments show energy savings of up to 66% compared to an approach where all nodes are permanently active while the discovery latencies were not increased.

Keywords: Service discovery

Keywords: Wireless Sensor Networks, ScatterWeb

Connectivity is an important property for QoS Support in Mobile Ad Hoc Networks (MANETs). Recently, there has been a big effort in exploring the critical transmission range (CTR) analytically, based on different network models. While most of these studies rely on a geometric model and come up with asymptotic bounds, their significance regarding finite 802.11 based MANETs is unclear. In this paper, we investigate connectivity in MANETs from a layered perspective. We first point out how the transmission range affects the end-to-end connection probability in a lognormal shadowing model and compare the results to theoretical bounds and measurements in the path loss model. We then show how connectivity issues behave in 802.11 and IP based networks if the fading effect increases. The paper concludes with an analytical model for the link probability in log-normal shadowing environments as a function of the number of nodes, network area, transmission range, path loss exponent and shadowing deviation.

Keywords: Simulation accuracy

Keywords: Mobile communications

Basic analytical models for problems of dynamic and quasi-static routing in data-communication networks are introduced. The models are intended to handle the quantities of interest in an algorithmic form, and as such require only a minimal number of assumptions. Control and estimation methods are used to construct algorithms for the solution of the routing problem.

Keywords: Routing

Discrete-event network simulation is a major tool for the research and development of mobile ad-hoc networks (MANETs). These simulations are used for debugging, teaching, understanding, and performance-evaluating MANET protocols. For the first three tasks, visualization of the processes occurring in the simulated network is crucial for verification and credibility of the generated results. Working with the popular network simulator ns-2, we have not yet found a visualization toolkit capable of reading native ns-2 trace files and providing means to change the evaluated parameters without changing the visualization software. Thus, we developed Huginn, a software providing an intuitive way to visualize simulation properties and to determine how they should be displayed without the need of programming. In addition, Huginn has a 3D interface allowing an improved exploitation of the (human) user's perceptual system. It helps to handle the significant cognitive load associated with the mental reconstruction of simulated network processes. Besides presenting the software interface and architecture, we describe algorithmic solutions that might be of a more general interest for similar problems.

Keywords: Network simulation, visualization, trace file analysis, wireless networks, ad hoc networks, ns-2

The term peer-to-peer (P2P) refers to distributed systems without any central control, where all the nodes (called peers) are equivalent in functionality. In a P2P system, peers can collaborate and communicate with each other without the need for centralized components. P2P systems organize the peer computers in a virtual communication network called an overlay network. Overlay networks generally have self-organizing characteristics, which means they are established and maintained by P2P software without any human intervention and that P2P software manages events such as peers joining and leaving the network. This self-organizing nature of P2P helps reduce the management cost of the computer infrastructure. However, the decentralized nature of P2P networks makes it difficult to develop efficient algorithms for tasks such as clustering and search, which are required by many P2P applications.

Keywords: Self-Organisation

On the contrary to present conjectures, our medium access control (MAC)-based performance studies revealed that battery capacity may not be used as the sole means for achieving energy-based fairness and system longevity for wireless mobile multi-hop ad hoc and sensor networks. Moreover, energy conservation may be attained only if valuable MAC (and PHY) input is passed to the network layer. Hence, in this paper, we propose two schemes the objective of which is to enhance the operation of existing power-based multi-path routing protocols via cross-layer designs and optimal load assignments. Our proposed schemes, namely, Energy-Constrained Path Selection (ECPS) and Energy-Efficient Load Assignment (E2LA), employ probabilistic dynamic programming techniques and utilize cross-layer interactions between the network and MAC layers. To the authors' best knowledge, this is the first time that MAC-originated information is used as the basis for achieving energy-efficient routing.

Keywords: Wireless Sensor Networks, Cross-layer Networking

Network simulation tools are frequently used to analyze performance of MANET protocols and applications. They commonly offer only simple radio propagation models that neglect obstacles of a propagation environment. In this paper, we integrate a more accurate radio propagation model into a simulation tool. The model is based on ray tracing and considers geographic data of the simulation area. We prove that the usage of a more precise propagation model changes simulated connection topologies considerably. Consequently, we obtain different performance evaluation results. To our best knowledge, no other study of MANETs has been performed so far with such a detailed radio propagation model. Hence, this paper also gives new insights on the realistic performance of MANETs in outdoor environments.

Keywords: Communication Systems, Mobile Communication, UHF Propagation, Geographic Information Systems, Simulation

Mobile Ad hoc NETworks (MANETs) conveniently complement infrastructure-based networks, allowing mobile nodes to spontaneously form a network and share their services, including bridging with other networks, either infrastructure-based or ad hoc. However, distributed service provisioning over MANETs requires adequate support for service discovery and invocation, due to the network's dynamics and resource constraints of wireless nodes. While a number of existing service discovery protocols have shown to be effective for the wireless environment, these are mainly aimed at infrastructure-based and/or 1-hop ad hoc wireless networks. Some discovery protocols for MANETs have been proposed over the last couple of years but they induce significant traffic overhead, and are thus primarily suited for small-scale MANETs with few nodes. Building upon the evaluation of existing protocols, we introduce a scalable service discovery protocol for MANETs, which is based on the homogeneous and dynamic deployment of cooperating directories within the network. Scalability of our protocol comes from the minimization of the generated traffic, and the use of compact directory summaries that enable to efficiently locate the directory that most likely caches the description of a given service.

Keywords: Service placement

The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed), or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: “How can we determine in a distributed and scalable manner the number and location of service facilities?” We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative reoptimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.

Keywords: Server migration, resource allocation, facility location, service deployment

This article presents ScatterWeb, a distributed, heterogeneous platform for the ad-hoc deployment of sensor networks offering hardware and open, fully documented software for research and teaching in embedded sensor networks. ScatterWeb consists of sensor nodes and several gateways connecting the sensor network to other wired or wireless networks. Already low-power by design, the sensor nodes offer additional energy conservation mechanisms and support energy efficient routing and applications. Even image capturing and transmission is possible with a minimum of energy. Together with auto-configuration and remote reprogramming techniques, these power saving mechanisms enable ScatterWeb nodes to survive many years in real-life scenarios without any in-place maintenance.

Keywords: Wireless sensor networks, Low-power, Auto-configuration, Self-organising networks

An ad-hoc wireless sensor network-based system is presented that detects and accurately locates shooters even in urban environments. The system consists of a large number of cheap sensors communicating through an ad-hoc wireless network, thus it is capable of tolerating multiple sensor failures, provides good coverage and high accuracy, and is capable of overcoming multipath effects. The performance of the proposed system is superior to that of centralized countersniper systems in such challenging environment as dense urban terrain. In this paper, in addition to the overall system architecture, the acoustic signal detection, the most important middleware services and the unique sensor fusion algorithm are also presented. The system performance is analyzed using real measurement data obtained at a US Army MOUT (Military Operations in Urban Terrain) facility.

Keywords: Sensor Networks, Middleware Services, Time Synchronization, Message Routing, Data Fusion, Acoustic Source Localization

With their increasingly powerful computational resources and high-speed wireless communications, future mobile systems will have the ability to run sophisticated applications on collections of cooperative end devices. Mobility, however, requires dynamic management of these platforms' distributed resources, and such management can also be used to meet application quality requirements and prolong application lifetimes, the latter by best using available energy resources. This paper presents energy-aware Mobile Service Overlays (MSOs), a set of mechanisms and associated policies for running mobile applications across multiple, cooperating machines while actively performing power management to extend system usability lifetimes. MSO policies manage energy consumption by (i) allocating application components to available nodes based upon their current energy capacities and resource availabilities, (ii) monitoring for, and responding to changes in energy and resource characteristics, and (iii) dynamically exploiting energy-performance tradeoffs in overprovisioned situations. Coupled with mobility, such cooperation enables multiple mobile platforms to bring their joint resources to bear on complex application tasks, providing significant benefits to application lifetimes and performance. This paper evaluates MSOs on a MANET computing testbed indicate an extension in system lifetime of upto 10% for an example application.

Keywords: Service placement

Keywords: Wireless Sensor Networks, Deployment

Keywords: Simulation accuracy

Distributed applications running on Mobile Adhoc NETworks (MANETs) can benefit from underlying middleware that provides services for self-management. Such services can address the dynamic conditions associated with a MANET's operational environment and changes in end user needs. This paper describes Mobile Service Overlays (MSOs), an overlay network-based decentralized middleware that provides basic support for online management, shown useful for services like online reconfiguration for managing energy consumption and failure resilience. Decentralization is achieved by partitioning the application's overlay network into smaller units termed chains, and implementing decentralized reconfigurations involving specific chains, triggered by monitoring events. The paper also presents the overheads of these services in a lightweight, non-Java implementation of MSOs targeted at an example MANET application in cooperative robotics.

Keywords: Mobile computing, Recongurable middleware

A user trainable detecting apparatus for on site configuration comprises: one or more sensors; a detector for detecting events within the data arriving from the sensor, and a user interface that has labeling functionality, and which enables the user to label data from the sensor through the interface. A learning unit uses the labeled data for in-situ learning for use in the detector.

Keywords: Distributed Event Detection

Keywords: NS-2, Modellierung, Scatterweb, Simulation, Sensornetzwerke

Keywords: Context

Simulation and physical implementation are both valuable tools in evaluating ad hoc network routing protocols, but neither alone is sufficient. In this paper, we present the design and implementation of a new system that allows existing simulation models of ad hoc network routing protocols to be used - without modification - to create a physical implementation of the same protocol. We have evaluated the simplicity and portability of our approach across multiple protocols and multiple operating systems through example implementations in our architecture of the DSR and AODV routing protocols in FreeBSD and Linux using the existing, unmodified ns-2 simulation models. We also illustrate the ability of the resulting protocol implementations to handle real, demanding applications by presenting a demonstration of this DSR implementation transmitting real-time video over a multihop mobile ad hoc network including mobile robots being remotely operated based on the transmitted video stream.

Keywords: Implementation, Ad Hoc Networks, Routing Protocols, ns-2, DSR, AODV, FreeBSD, Linux

This paper proposes a medium access control (MAC) protocol for ad hoc wireless networks that utilizes multiple channels dynamically to improve performance. The IEEE 802.11 standard allows for the use of multiple channels available at the physical layer, but its MAC protocol is designed only for a single channel. A single-channel MAC protocol does not work well in a multi-channel environment, because of the multi-channel hidden terminal problem. Our proposed protocol enables hosts to utilize multiple channels by switching channels dynamically, thus increasing network throughput. The protocol requires only one transceiver per host, but solves the multi-channel hidden terminal problem using temporal synchronization. Our scheme improves network throughput significantly, especially when the network is highly congested. The simulation results show that our protocol successfully exploits multiple channels to achieve higher throughput than IEEE 802.11. Also, the performance of our protocol is comparable to another multi-channel MAC protocol that requires multiple transceivers per host. Since our protocol requires only one transceiver per host, it can be implemented with a hardware complexity comparable to IEEE 802.11.

Keywords: Ad hoc network, medium access control, multi-channel

Event detection and tracking are attractive research issues in the wireless sensor network (WSN). The paper proposes a fully distributed protocol, CollECT, to event detection and tracking in a Wireless Heterogeneous Sensor Network (WHSN), composed of many kinds of sensors. In CollECT, three major procedures, vicinity triangulation, event determination, and border sensor selection are used to construct the logical triangle in the vicinity of a sensor, to determine the event, and to select the border sensor to identify the event boundary, respectively. The procedures perform repeatedly to both detect and track events. Simulation results demonstrate that CollECT is promising for event detection and tracking due to satisfactory event accuracy and reasonable fitness of border sensors.

Keywords: Fence Monitoring

Keywords: Wireless sensor networks

Keywords: Functional Programming

Mobile ad hoc networks have typically used the IEEE 802.11 MAC protocol with a single interface and a unique channel to transfer data. The trend to use multiple interfaces and multiple channels was only in mesh networks or in cellular networks. This paper is a state of art on multi-hop ad hoc networks where one uses more than one interface and more than one channel. We analyzed recent advances concerning MAC protocols and adapted routing protocols. This description of related work is followed by a discussion on open research issues related to this theme. We focus on throughput-oriented approaches.

Keywords: Multi-hop ad hoc networks, multiple interfaces and multiple channels (MIMC), MAC, power control, routing

Simulation can be an important step in the development of software for wireless sensor networks and has been the subject of intense research in the past decade. While most previous efforts in simulating wireless sensor networks have focused on protocol-level issues utilizing models of the software implementation, a significant challenge remains in precisely measuring time-dependent properties such as radio channel utilization. One promising approach, first demonstrated by ATEMU, is to simulate the behavior of sensor network programs at the machine code level with cycle-accuracy, but poor performance has so far limited its scalability. In this paper we present Avrora, a cycle-accurate instruction-level sensor network simulator which scales to networks of up to 10,000 nodes and performs as much as 20 times faster than previous simulators with equivalent accuracy, handling as many as 25 nodes in real-time. We show how an event queue can enable efficient instruction-level simulation of microcontroller programs and allow the hidden parallelism in finegrained sensor network simulations to be extracted, once two core synchronization problems are identified and solved. Avrora's ability to measure detailed time-critical phenomena can shed new light on design issues for large-scale sensor networks.

Keywords: Simulation

In most studies on mobile ad hoc networks (MANET), simulation models are used for the evaluation of devices and protocols. Typically, such simulations focus on the specific higher layer protocols that are being proposed, and tend to ignore details of models at other layers, particularly the interactions with physical layer models. In this paper, we present the set of factors at the physical layer that are relevant to the performance evaluations of higher layer protocols. Such factors include signal reception, path loss, fading, interference and noise computation, and preamble length. We start the discussion with the comparisons of physical layer models in ns-2 and GloMoSim, two commonly used simulators for MANET studies, and then quantify the impact of the preceding factors under typical scenarios used for the performance evaluation of wireless ad hoc routing protocols. Our experimental results show that the factors at the physical layer not only affect the absolute performance of a protocol, but because their impact on different protocols is non-uniform, it can even change the relative ranking among protocols for the same scenario.

Keywords: Wireless Sensor Networks, Simulation

Debugging, testing, and profiling microcontroller programs are notoriously difficult. The lack of supporting software such as an operating system, a narrow interface to the hardware chip, and delicately timed sequences of code present significant challenges which can be exacerbated by the presence of additional debugging or profiling code. In this paper we present a solution to the precision instrumentation problem for microcontroller code that is based upon our open, flexible simulator framework, Avrora. Our simulator preserves all timing and behavior of the instrumented program while allowing precision measurement of application-specific quantities.

Keywords: Sensor Networks, Instruction-Level Simulation, Cycleaccurate, Parallel Simulation, Instrumentation, Debugging, Monitoring, Profiling

This paper reports on the experience gained during a realworld deployment of a sensor network based on the ESB platform in the heathlands of Northern Germany. The goal of the experiment was to gain a deeper insight into the problems of real deployments as opposed to simulated networks. The focus of this report is on the quality of radio links and the influence of the link quality on multi-hop routing.

Keywords: Wireless Sensor Networks, Deployment

In the first days of the emergence of Wireless Sensor Networks (WSN) programming software involved expertise in both hard-ware and networking. Since then, various middleware architectures have been proposed to achieve a suitable abstraction from distribution and management tasks of sensor devices. This allows the users to focus on the application development.
The approaches suggested so far differ in concept, functionality and envisioned abstraction. This paper presents some representative approaches and states that only three different flavors of middleware exist, each of them addressing some characteristic abstraction middleware architectures are eager to provide. For future middleware implementations it will be beneficial to carefully bal-ance the components of each class to obtain a mature design.

Keywords: Wireless Sensor Networks, Middleware Architectures, Classification

Active networks are a novel approach to network architecture in which the switches of the network perform customized computations on the messages flowing through them. This approach is motivated by both lead user applications, which perform user-driven computation at nodes within the network today, and the emergence of mobile code technologies that make dynamic network service innovation attainable. In this paper, we discuss two approaches to the realization of active networks and provide a snapshot of the current research issues and activities.

Keywords: Active networks

Introducing a middleware layer into wireless sensor networks is a widely accepted solution to facilitate application programming and to allow network organization. In this paper we introduce FACTS, a highly flexible middleware architecture able to provide support for a wide range of different applications. Instead of developing middleware and application apart from one another, we seek to combine them at programming level. Our rule-based language, tailored to this concept and the domain of networked sensors, enables high-level software development. The objective is to combine advantages of event-centric processing and rule-based execution while preserving low resource usage.

Keywords: Wireless Sensor Networks, Middleware, Event-Centric Architecture, Rule-Based Language, Qualitative Simulation

Data-centric, distributed programming for embedded systems with harsh resource constraints poses a heavy burden upon a developer. In this paper, we describe how rule-based programming can alleviate these problems by combining middleware and application at the programming level.
We describe in detail the programming primitives and the implementation of the FACTS middleware architecture. Based on statistics derived from three representative tasks specific to wireless sensor networks, we illustrate how our approach allows for aggressive optimization as well as writing expressive application-level code. We summarize our experience by proposing several rule-oriented programming patterns.

Keywords: Wireless Sensor Networks, Programming Abstraction, Middleware Framework, Rule-Oriented Programming Patterns

Keywords: Wireless Sensor Networks, Experiments

This memo defines name-based sockets. Name-based sockets allow application developers to refer to remote hosts (and it self) by name only, passing on all IP (locator) management to the operating system. Applications are thus relieved of re-implementing features such as multi-homing, mobility, NAT traversal, IPv6/IPv4 interoperability and address management in general. The operating system can in turn re-use the same solutions for a whole set of guest applications. name-based sockets aims to provide a whole set of features without adding new indirection layers, new delays or other dependencies while maintaining transparent backwards compatibility.

Keywords: Service placement

The paper introduces OMNeT++, a C++-based discrete event simulation package primarily targeted at simulating computer networks and other distributed systems. OMNeT++ is fully programmable and modular, and it was designed from the ground up to support modeling very large networks built from reusable model components. Large emphasis was placed also on easy traceability and debuggability of simulation models: one can execute the simulation under a powerful graphical user interface, which makes the internals of a simulation model fully visible to the person running the simulation: it displays the network graphics, animates the message flow and lets the user peek into objects and variables within the model. These features make OMNeT++ a good candidate for both research and educational purposes. The OMNeT++ simulation engine can be easily embedded into larger applications. OMNeT++ is open source, free for non-profit use, and it has a fairly large user community.

Keywords: Discrete Simulation, Performance Analysis, Computer Systems, Telecommunications, Hierarchical

Sensor networks are in wide spread use and with deployments reaching larger numbers, the need for a scalable simulation framework is becoming apparent. Simulation of sensor networks offers the capability to test network protocols under different topologies, with repeatability in mind. While repeatability and scalability are important criteria, wireless channels are hard to model. The best-case scenario would be to evaluate the protocols under a testbed of real nodes. This too, has a severe drawback in that the evaluation is restricted by the size of the testbed. This project presents a simulation framework that can be used to simulate SOS applications and combine them with a hybrid simulation capability that allows for nodes in the simulation to be mapped to real nodes.

Keywords: Hybrid Simulation

This paper presents ModelNet, a scalable Internet emulation environment that enables researchers to deploy unmodified software prototypes in a configurable Internet-like environment and subject them to faults and varying network conditions. Edge nodes running user-specified OS and application software are configured to route their packets through a set of ModelNet core nodes, which cooperate to subject the traffic to the bandwidth, congestion constraints, latency, and loss profile of a target network topology.
This paper describes and evaluates the ModelNet architecture and its implementation, including novel techniques to balance emulation accuracy against scalability. The current ModelNet prototype is able to accurately subject thousands of instances of a distributed application to Internet-like conditions with gigabits of bisection bandwidth. Experiments with several large-scale distributed services demonstrate the generality and effectiveness of the infrastructure.

Keywords: Wireless Sensor Networks, Simulation

Efficient group communication within the Internet has been implemented by multicast. Unfortunately, its global deployment is missing. Nevertheless, emerging and progressively establishing popular applications, like IPTV or large-scale social video chats, require an economical data distribution throughout the Internet.
To overcome the problem the limitations of multicast deployment, we introduce and analyze BIDIR-SAM, the first structured overlay multicast scheme based on bi-directional shared prefix trees. BIDIR-SAM admits predictable costs growing logarithmically with increasing group size. We also present a broadcast approach for DHT-enabled P2P networks. Both schemes are integrated in a standard compliant hybrid group communication architecture, bridging the gap between overlay and underlay as well as between inter- and intra-domain multicast.

Keywords: P2P, Overlay, Multicast, Mobile, Hybrid, ALM, OLM, prefix tree, k-ary tree, analysis

In comparison to traditional sensor networks, wireless sensor networks have a number of strengths such as distributed operation, parallelism, redundancy, and comparatively high cost-effectiveness due to lack of wires. On the other hand, their tininess, need for long-term operation, and dependency on batteries impose severe restrictions on the system. Hence, services provided in sensor networks need to be lightweight in terms of memory and processing power and should not require high communication costs. In our own work we have developed an event monitoring architecture that provides energy-efficient medium access and topology control on the lower layers. On the application layer functionality to detect, track and classify occurring events in a lightweight and distributed manner is provided. The developed system has been used in an office access monitoring application, where illegal office access has been detected and reported.

Keywords: Wireless sensor network, event detection

This paper describes our experiences using a wireless sensor network to monitor volcanic eruptions with low-frequency acoustic sensors. We developed a wireless sensor array and deployed it in July 2004 at Volcán Tungurahua, an active volcano in central Ecuador. The network collected infrasonic (low-frequency acoustic) signals at 102 Hz, transmitting data over a 9 km wireless link to a remote base station. During the deployment, we collected over 54 hours of continuous data which included at least 9 large explosions. Nodes were time-synchronized using a separate GPS receiver, and our data was later correlated with that acquired at a nearby wired sensor array. In addition to continuous sampling, we have developed a distributed event detector that automatically triggers data transmission when a well-correlated signal is received by multiple nodes. We evaluate this approach in terms of reduced energy and bandwidth usage, as well as accuracy of infrasonic signal detection.

Keywords: Fence Monitoring

We present a science-centric evaluation of a 19-day sensor network deployment at Reventador, an active volcano in Ecuador. Each of the 16 sensors continuously sampled seismic and acoustic data at 100 Hz. Nodes used an event-detection algorithm to trigger on interesting volcanic activity and initiate reliable data transfer to the base station. During the deployment, the network recorded 229 earthquakes, eruptions, and other seismoacoustic events.
The science requirements of reliable data collection, accurate event detection, and high timing precision drive sensor networks in new directions for geophysical monitoring. The main contribution of this paper is an evaluation of the sensor network as a scientific instrument, holding it to the standards of existing instrumentation in terms of data fidelity (the quality and accuracy of the recorded signals) and yield (the quantity of the captured data). We describe an approach to time rectification of the acquired signals that can recover accurate timing despite failures of the underlying time synchronization protocol. In addition, we perform a detailed study of the sensor network's data using a direct comparison to a standalone data logger, as well as an investigation of seismic and acoustic wave arrival times across the network.

Keywords: Fence Monitoring

Augmenting heavy and power-hungry data collection equipment with lighter, smaller wireless sensor network nodes leads to faster, larger deployments. Arrays comprising dozens of wireless sensor nodes are now possible, allowing scientific studies that aren't feasible with traditional instrumentation. Designing sensor networks to support volcanic studies requires addressing the high data rates and high data fidelity these studies demand. The authors' sensor-network application for volcanic data collection relies on triggered event detection and reliable data retrieval to meet bandwidth and data-quality demands.

Keywords: Fence Monitoring

Die verteilte Anordnung von Sensorknoten in einem drahtlosen Sensornetz ermöglicht es, Eigenschaften und Veränderungen der Umwelt an unterschiedlichen Stellen zu beobachten. Durch ein Zusammenwirken der Sensorknoten können in der Umwelt auftretende Ereignisse verteilt erkannt werden. Es existiert ein verteiltes Erkennungssystem, welches Ereignisdaten mehrerer Sensorknoten im Sensornetz fusioniert und anhand einer lokal durchgeführten Mustererkennung klassifiziert. Dieses System wurde unter Laborbedingungen entwickelt und getestet. Mit dieser Arbeit wird eine Weiterentwicklung des verteilen Erkennungssystems vorgestellt, welches den Anforderungen einer praktischen Anwendbarkeit gerecht wird.
Während des Mustertrainings können Ereignisdaten von einer dynamischen Anzahl von Sensorknoten verarbeitet werden. Die Daten werden dabei auf die für die Erkennung geeignetsten und aussagekräftigsten Werte reduziert. Die verteilte Ereigniserkennung ist nicht auf den Ort des Trainings beschränkt. Ein unbekanntes Ereignis kann an jedem Punkt des Sensornetzes von den das Ereignis wahrnehmenden Sensorknoten unter Austausch von Merkmalswerten klassifiziert werden. Ort und Typ des Ereignisses werden auf einer Basisstation angezeigt.
Das in der vorliegenden Arbeit entwickelte System wird anhand eines praktischen Anwendungsfalls getestet. Dabei handelt es sich um die Erkennung sicherheitsrelevanter Ereignisse an einem Bauzaun. Die Evaluation erfolgt für die Erkennung der Ereignisse am Ort gleich und ungleich des Trainings. Es wird untersucht, wie sich die Änderung des Ortes auf die Erkennungsraten auswirkt und wie viel Einfluss die Bedingungen der realen Welt auf die Ergebnisse im Vergleich zu denen unter Laborbedingungen besitzen. Am Ort des Trainings wird eine Korrektklassifikationsrate von 74,8% erzielt. Im Vergleich zum Projekt Fence Monitoring, welches sich ebenfalls mit der verteilten Erkennung von Ereignissen an Bauzäunen beschäftigt, wird eine Steigerung von 15,9 Prozentpunkten erzielt. In Bezug auf das dieser Arbeit zugrunde liegenden Erkennungssystem, dessen Ergebnisse durch Versuche unter Laborbedingungen entstanden, ist ein Rückgang von 21,5 Prozentpunkten zu verzeichnen. Für den Fall der Erkennung am Ort ungleich des Trainings ergibt sich eine Korrektklassifikationsrate von 57,7%.

Keywords: Wireless Sensor Networks, Distributed Event Detection, In-network Data Processing, Pattern Recognition

Energy savings and topology control are needed tasks of many sensor network applications. Sensors are assumed to be randomly deployed and shall organize themselves independently after deployment. Moreover, sensor networks shall operate as long as possible warranting network connectivity. To support these tasks we propose the maintenance of a virtual backbone. Nodes not participating in the backbone shutdown their radios and go to sleep for a certain time. The backbone nodes are adaptively altered according to the current network conditions. The backbone is thus able to deal with node failures and/or movements. The non-backbone nodes follow long sleep cycles during which they frequently wake up to check the network conditions. After a long sleep period the backbone is reestablished by the base station. The algorithm shows good approximation of the minimum number of nodes in the backbone after backbone setup, as well as the ability to repair link breaks on demand with short delays and low message overhead.

Keywords: Wireless sensor networks, simulation accuracy

Event detection in wireless sensor networks is a sophisticated method for processing sampled data directly on the sensor nodes, thereby reducing the need for multi-hop communication with the base station of the network. In contrast to application-agnostic compression or aggregation techniques, event detection pushes application-level knowledge into the network. In-network event detection - especially the distributed form involving multiple sensor nodes - has thus an exceptional potential to increase energy efficiency, thus prolonging the lifetime of the network.
In this paper, we summarize recently proposed system architectures and algorithms employed for event detection in wireless sensor networks. On the example of the AVS-Extrem platform, we illustrate how energy-efficient event detection can be implemented through a combination of custom hardware design and distributed event detection algorithms. We then continue to present a brief evaluation of the detection accuracy and the energy consumption that is achievable by current systems.

Keywords: Event Detection

In order to avoid transmitting raw data to a base station, sensor nodes are trained to cooperatively recognize deployment-specific events based on the data sampled by their sensors. As both training and event detection are performed without the need for central coordination or processing, only information about the detected event needs to be reported.

Keywords: Wireless Sensor Networks, Distributed Event Detection, In-network Data Processing, Pattern Recognition

Verfahren zur Merkmalsauswahl für eine Ereigniserkennung in Sensornetzen, mit den Schritten:
- in einer Konfigurationsphase,
- Bereitstellen einer Menge von Merkmalen durch Sensorknoten eines Sensornetzes, die ein zu erkennendes Ereignis charakterisieren, zusammen mit Informationen zum topologischen Ursprung der Merkmale innerhalb des Sensornetzes, und
- Auswählen einer Untermenge aus der Menge der Merkmale, wobei die Auswahl unter Berücksichtigung der Informationen zum topologischen Ursprung der Merkmale erfolgt,
- in einer Ausführungsphase,
- Vornahme einer Ereigniserkennung zu einem aktuell zu erkennenden Ereignis auf der Grundlage von Merkmalen, die zu einer ausgewählten Untermenge gehören.

Keywords: Wireless sensor networks, Event detection

Event detection is a major issue for applications of wireless sensor networks. In order to detect an event, a sensor network has to identify which application-specific incident has occurred based on the raw data gathered by individual sensor nodes. In this context, an event may be anything from a malfunction of monitored machinery to an intrusion into a restricted area. The goal is to provide high-accuracy event detection at minimal energy cost in order to maximize network lifetime.
In this paper, we present a system for collaborative event detection directly on the sensor nodes. The system does not require a base station for centralized coordination or processing, and is fully trainable to recognize different classes of application-specific events. Communication overhead is reduced to a minimum by processing raw data directly on the sensor nodes and only reporting which events have been detected. The detection accuracy is evaluated using a 100-node sensor network deployed as a wireless alarm system on the fence of a real-world construction site

Keywords: Wireless Sensor Network, Distributed Event Detection, In-network Data Processing, Pattern Recognition, Fence Monitoring, Deployment

Keywords: Routing

Specialized elements of hardware and software, connected by wires, radio waves and infrared, will be so ubiquitous that no one will notice their presence.

Keywords: Ubiquitous computing

The resource limitations of Wireless Sensor Network (WSN), especially in terms of energy, require novel and collaborative approach for the wireless communication. In this paper, we present a new on-demand routing algorithm for wireless sensor network, which has fast recovery mechanism relying on MAC layer feed back to counter the mobility and unreliability of nodes. In the route reestablishment, a geographically restricted directional flooding scheme based on the previous knowledge of the location of destination node is devised. Simulations show that the algorithm achieves much improved throughout performance over conventional routing algorithm for WSN, while significantly reduce power consumption on routing maintenance overhead.

Keywords: Wireless Sensor Networks

Keywords: Wireless Sensor Networks, Simulation

This paper describes the replay attack against traditional and channel-based Chaumian mixes and puts it into context with other attacks on anonymizing services. It then evaluates different possible approaches to a defense against said attack, concentrating on the question of efficiently recognizing potentially compromised messages within a channel-based cascade of mixes. Finally, an exemplary implementation of a solution is presented for the anonymizing cascade of mixes of the AN.ON project.

Keywords: Replay Attack, Chaumian Mix, Cascade of Mixes, David L. Chaum, Anonymity, Unobservability, Traffic Analysis, AN.ON, JAP

Wireless Sensor Networks (WSN) are an emerging technology with applications in the fields of environmental monitoring, facility management, and high-precision data gathering in general. They are deployed in the form of a large set of inexpensive sensing units that communicate over an ad-hoc wireless network. Developing applications for WSNs is challenging due to very limited resources available on each sensor node and the distributed nature of the algorithms used.
In order to ease the development effort, we propose the FACTS middleware architecture for wireless sensor networks. Built around a rule-based programming paradigm, FACTS supports event-driven and data-centric applications to be written in the ruleset definition language. Components of the middleware are implemented in rulesets, compiled into bytecode and interpreted on the sensor nodes. We illustrate the capabilities of the FACTS middleware architecture by simulating it using the ns-2 network simulator and the ScatterWeb WSN platform.

Keywords: Wireless Sensor Networks, Middleware

Service provisioning in ad hoc networks is challenging given the difficulties of communicating over a wireless channel and the potential heterogeneity and mobility of the devices that form the network. In order to optimize the performance of the network over which a service host provides a service to client nodes, it is necessary to continuously adapt the logical network topology to both external (e.g., wireless connectivity, mobility, churn) and internal (e.g., communication patterns, service demand) factors. Recent proposals advocate that nodes should dynamically choose which nodes in the network are to provide application-level services to other nodes. Services in this context range from infrastructural services such as the Domain Name System (DNS) to user-oriented services such as the World Wide Web (WWW).
Service placement is the process of selecting an optimal set of nodes to host the implementation of a service in light of a given service demand and network topology. The main questions addressed by service placement are: How many instances of the same service should be available in the network and cooperate to process clients' service requests; where these service instances should be placed, i.e., which nodes are best suited for hosting them; and when to adapt the current service configuration. The service instances of a distributively operating service are exact copies of the software component that provides the service, including both the executable binary and the application-level data. The set of nodes that host a service instance is referred to as the service configuration. A good service configuration increases the performance of a service according to application-specific quality metrics, while at the same time potentially reducing the overall network load. The key advantage of active service placement in ad hoc networks is that it allows for the service configuration to be adapted continuously at run time.
In this work, we propose the SPi service placement framework as a novel approach to service placement in ad hoc networks. The SPi framework takes advantage of the interdependencies between service placement, service discovery and the routing of service requests to minimize signaling overhead. We also propose the Graph Cost / Single Instance (GCSI) and the Graph Cost / Multiple Instances (GCMI) placement algorithms. The SPi framework employs these algorithms to optimize the number and the location of service instances based on usage statistics and a partial network topology derived from routing information. The GCSI and GCMI placement algorithms only require minimal knowledge about the service they are tasked with placing in the network. They are novel in that they take the communication between service instances into account which is required to synchronize the global state of the service. Furthermore, when calculating the optimal timing of their placement decisions, the two algorithms explicitly consider the overhead of the actions required for implementing changes to the current service configuration.
Our implementation of the SPi framework on top of a special low-level API allows us to run the framework on a variety of evaluation platforms including major operating systems and network simulation tools. We examine the properties of our approach to service placement and compare it with other recent proposals in simulations, emulations, and real-world experiments on an IEEE 802.11 wireless testbed. The results of this evaluation show that the SPi service placement framework and our placement algorithms, in particular GCMI, are able to find service configurations that are superior across a variety of scenarios to those found by other approaches. As a consequence, service provisioning improves significantly with regard to its reliability and timeliness, while at the same time causing less network traffic. Furthermore, our results show that distributed service provisioning with active service placement - as implemented in SPi - generally outperforms services that are implemented in a traditional client/server architecture. From these results we conclude that our approach to service provisioning in ad hoc networks is a viable alternative to established architectures.

Keywords: Service Placement, Ad Hoc Networks, Service Placement System, SPi, SPi Service Placement Framework, Service Placement Algorithm, Graph Cost / Single Instance, Graph Cost / Multiple Instances

Die Erfindung betrifft ein Verfahren zur Datenbereitstellung auf mobilen Endgeräten mit den Schritten: Bereitstellen einer durchgängigen Netzkonnektivität einer Mehrzahl mobiler Endgeräte unterschiedlicher Nutzer, Ausführen einer lokalen Anwendung auf einem der Endgeräte, die zu einem Erstellen oder einer Änderung eines Datensatzes führt, und automatisches Bereitstellen des erstellten oder geänderten Datensatzes bei den anderen Endgeräten. Das automatische Bereitstellen des erstellten oder geänderten Datensatzes bei den anderen Endgeräten erfolgt dabei, indem der erstellte oder geänderte Datensatz mittels eines PUSH-Dienstes an die anderen Endgeräte übertragen und der erstellte oder geänderte Datensatz bei den anderen Endgeräten in die entsprechende lokale Anwendung transparent integriert wird. Die Erfindung betrifft des Weiteren ein mobiles Endgerät zur Durchführung eines solchen Verfahrens.

Keywords: Ad Hoc Networks, PUSH Service

Weit verbreiteten Diensten wie dem World Wide Web (WWW) oder E-Mail liegt die Client/Server-Architektur zugrunde. Diese ist jedoch nur eingeschränkt auf drahtlose Ad-hoc-Netze übertragbar. In der aktuellen Forschung werden daher Alternativen untersucht, die die Diensterbringung intelligent auf einer Mehrzahl von am Ad-hoc-Netz teilnehmenden Geräten verteilen. Das in dieser Arbeit vorgestellte System SPi ermöglicht erstmalig den experimentellen Vergleich von unterschiedlichen Ansätzen zur verteilten Diensterbringung. Die experimentelle Untersuchung von SPi und dem ebenfalls vorgestellten Graph Cost/ Multiple Instances Dienstplatzierungsalgorithmus zeigt, dass die verteilte Diensterbringung als neuartige Architektur die Skalierbarkeit von Diensten in Ad-hoc-Netzen entscheidend verbessert.

Keywords: Dienstplatzierung, Service Placement, Service Provisioning, Ad Hoc Networks, Service Placement System, SPi, SPi Service Placement Framework, Service Placement Algorithm, Graph Cost / Multiple Instances

In wireless ad-hoc networks, the network topology changes dynamically and unpredictably due to node mobility. Such topological dynamics are further exacerbated by the natural grouping behavior in mobile user's movement, which leads to frequent network partitioning. Network partitioning poses significant challenges to the provisioning of centralized services in adhoc networks, since the partitioning disconnects many mobile users from the central server. In this paper, we propose a collection of novel run-time algorithms that adaptively ensure the centralized service is available to all mobile nodes during network partitioning, while minimizing the number of servers required. The network-wide service coverage is achieved by partition prediction and service replication on the servers, and assisted by distributed service selection on regular mobile nodes. Simulation results show that our algorithms efficiently achieve guaranteed service coverage to all nodes. To the best of our knowledge, there have been no similar approaches that use partition prediction to adaptively provision centralized service in partitionable mobile ad-hoc networks.

Keywords: Service placement

In wireless ad-hoc networks, network partitioning occurs when the mobile nodes move with diverse patterns and cause the network to separate into completely disconnected portions. Network partitioning is a widescale topology change that can cause sudden and severe disruptions to ongoing network routing and upper layer applications. Its occurrence can be attributed to the aggregate group motion exhibited in the movements of the mobile nodes. By exploiting the group mobility pattern, we can predict the future network partitioning, and thus minimize the amount of disruptions.
In this paper, we propose a new characterization of group mobility based on existing group mobility models, which provides parameters that are sufficient for network partition prediction. We then demonstrate how partition prediction can be made using the mobility model parameters, and illustrate the applicability of the prediction information. Furthermore, we use a simple but effective data clustering algorithm that, given the velocities of the mobile nodes in an ad-hoc network, it can accurately determine the mobility groups and estimate the characteristic parameters of each group.

Keywords: Service placement

The Smart Dust project is probing microfabrication technology's limitations to determine whether an autonomous sensing, computing, and communication system can be packed into a cubic-millimeter mote to form the basis of integrated, massively distributed sensor networks.

Keywords: Wireless Sensor Networks

Keywords: Wireless Sensor Networks, Virtual Machine

Wireless sensor networks (WSNs) have a wide range of useful, data-centric applications, and major techniques involved in these applications include in-network query processing and query-informed routing. Both techniques require realistic environments and detailed system feedback for development and evaluation. Unfortunately, neither real sensor networks nor existing simulators/emulators are suitable for this requirement. In this design paper, we propose a distributed sensor network emulator, a Virtual Mote Network (VMNet), to meet this requirement. We describe the system architecture, the synchronization of the nodes and the virtual time emulation with a focus on mechanisms that are effective for accurate emulation.

Keywords: Wireless Sensor Networks, Simulation

In the domain of wireless sensor networks, simulation is the preferred way of evaluating new algorithms. One commonly found drawback of simulation tools is that they provide a programming environment that does not match the one present on real-world platforms.
In this paper, we address this problem by presenting the steps required to port an existing software stack to a popular network simulator. This novel procedure allows for applications to run both in the simulated environment and on real-world sensor nodes without any changes to the source code. We verify our results by means of performance analyses of several simulated applications.

Keywords: Wireless Sensor Networks, WSNs, Simulation, ScatterWeb, ns-2

In the field of wireless sensor networks, network simulators are commonly used to evaluate properties of software components or the network as a whole. Their advantages in reduced experimental overhead, flexibility, and repeatability come at the expense of questionable credibility of the results. In order to quantify the simulation accuracy of wireless sensor networks, we have conducted a field test measuring the packet loss rate and compared the data with the results obtained from a carefully configured simulation of the same scenario. Our evaluation gives insight into how much trust can be put into the results of simulations of comparable scenarios.

Keywords: Wireless Sensor Networks, Simulation, Accuracy, ScatterWeb, ns-2

Service placement deals with the problem of selecting which node in a network is most suitable for hosting a service that responds to queries from other nodes. Optimally placing services reduces network traffic and improves connectivity between clients and servers. Service placement algorithms may thus be regarded as an interesting building block for research into service-oriented middleware. Recently, new approaches to address the service placement problem in the field of ad-hoc networking have been proposed. This paper surveys, classifies and evaluates ten representative approaches, thereby providing a summary of the state of the art in service placement.

Keywords: Service Placement, Mobile Ad-hoc Networks, MANETs, Survey, Current Directions, State of the Art

Keywords: Service Placement, Ad Hoc Networks, MANETs, Algorithms, SPi

Service placement optimizes the number of instances of a service and their location within an ad hoc network in light of changes in service demand and network topology. The goal is to reduce bandwidth usage and latencies between clients and servers, while improving scalability and availability of the service.
We propose the SPi service placement architecture which is unique in that it addresses the interdependencies between service placement, service discovery, and routing. We give an overview of the system, discuss the service model and algorithms with emphasis on the cost of synchronization between service instances, and present simulation-based results that illustrate the benefits of service placement when compared to traditional client/server architecture.

Keywords: Service Placement, Ad Hoc Networks, SPi Service Placement Architecture

Service provisioning in ad hoc networks is challenging given the difficulties of communicating over a wireless channel and the potential heterogeneity and mobility of the devices that form the network. In order to optimize the performance of the network over which a service host provides a service to client nodes, it is necessary to continuously adapt the logical network topology to both external (e.g., wireless connectivity, mobility, churn) and internal (e.g., communication patterns, service demand) factors. Recent proposals advocate that nodes should dynamically choose which nodes in the network are to provide application-level services to other nodes. Services in this context range from infrastructural services such as the Domain Name System (DNS) to user-oriented services such as the World Wide Web (WWW).
Service placement is the process of selecting an optimal set of nodes to host the implementation of a service in light of a given service demand and network topology. The main questions addressed by service placement are: How many instances of the same service should be available in the network and cooperate to process clients’ service requests; where these service instances should be placed, i.e., which nodes are best suited for hosting them; and when to adapt the current service configuration. The service instances of a distributively operating service are exact copies of the software component that provides the service, including both the executable binary and the application-level data. The set of nodes that host a service instance is referred to as the service configuration. A good service configuration increases the performance of a service according to application-specific quality metrics, while at the same time potentially reducing the overall network load. The key advantage of active service placement in ad hoc networks is that it allows for the service configuration to be adapted continuously at run time.
Service Placement in Ad Hoc Networks proposes the SPi service placement framework as a novel approach to service placement in ad hoc networks. The SPi framework takes advantage of the interdependencies between service placement, service discovery and the routing of service requests to minimize signaling overhead. The work also proposes the Graph Cost / Single Instance (GCSI) and the Graph Cost / Multiple Instances (GCMI) placement algorithms. The SPi framework employs these algorithms to optimize the number and the location of service instances based on usage statistics and a partial network topology derived from routing information. The GCSI and GCMI placement algorithms only require minimal knowledge about the service they are tasked with placing in the network. They are novel in that they take the communication between service instances into account which is required to synchronize the global state of the service. Furthermore, when calculating the optimal timing of their placement decisions, the two algorithms explicitly consider the overhead of the actions required for implementing changes to the current service configuration.
Implementation of the SPi framework on top of a special low-level API allows the framework to be run on a variety of evaluation platforms including major operating systems and network simulation tools. The work examines the properties of this approach to service placement and compares it with other recent proposals in simulations using the network simulator ns-2. The results of this evaluation show that the SPi service placement framework and the placement algorithms, in particular GCMI, are able to find service configurations that are superior across a variety of scenarios to those found by other approaches. As a consequence, service provisioning improves significantly with regard to its reliability and timeliness, while at the same time causing less network traffic. Furthermore, the results show that distributed service provisioning with active service placement – as implemented in SPi – generally outperforms services that are implemented in a traditional client/server architecture. The results suggest that this approach to service provisioning in ad hoc networks is a viable alternative to established architectures.

Keywords: Ad Hoc Networks, Placement Algorithms, SPi Service Placement Framework, Service Placement, Service Placement System, Service Provisioning

Recent efforts are made to construct a globally accessible group communication service by a simultaneous use of network and application layer multicast. Such hybrid approaches provide native multicast to group members wherever available, but relocate data distribution and duplication from the network to applications or gateways if needed. Such services require an abstract programming interface to allow for a transparent use by applications. The contributions of this paper are twofold. First, we explore the problem space of designing a protocol stack for hybrid group communication that covers structured P2P networks. Second, we propose a transparent API that encapsulates a middleware abstraction layer for implementing hybrid multicast, and allows for overlay-underlay agnostic programming.

Keywords: Adaptive Group Protocol Stack, Key-based Routing, Inter-domain Hybrid Multicast, Dabek Model

Group communication services are most efficiently implemented on the lowest layer available. Network layer multicast transparently delegates group distribution to the link layer wherever possible. Native multicast deployment, though, has been mainly limited to 'walled gardens' within provider domains. Overlay multicast overcomes these deployment restrictions on the price of a performance penalty. Current activities focus on hybrid approaches which dynamically combine multicast in overlay and underlay, and adaptively optimize group communication. The basic requirement for such a flexibly deployable architecture is a layer-transparent group communication stack that integrates variable multicast protocols by a common API. In this paper, we present a common group communication stack which serves the requirements of data distribution and maintenance for multicast and broadcast on a middleware abstraction layer, suitable for underlay and overlay communication. We discuss its application in the context of hybrid multicast schemes.

Keywords: Key-based Routing, Hybrid Multicast, Dabek Model, Adaptive Protocol Stack

IPTV, software replication and other large-scale distribution tasks urge the need for efficient multicast mechanisms in overlay networks. Current multicast solutions on the application layer are either efficient, structured, but inflexible, or flexible, unstructured, but of lesser efficiency. This paper introduces Scalable Adaptive Multicast on BI-DIRectional shared trees, a new structured but flexible approach to content distribution. BIDIR-SAM is the first DHT-based overlay multicast that distributes any source multicast data according to source-specific shortest path trees. Built upon bi-directional shared prefix trees, the approach distributes packets uniquely via fully redundant paths, and allows for highly flexible network adaptivity. Guided by an overlay abstraction, it operates directly on top of a prefix routing and does not rely on any kind of rendezvous point or bootstrapping.

Keywords: P2P

A broadcast mode may augment peer-to-peer overlay networks with an efficient, scalable data replication function, but may also give rise to a virtual link layer in VPN-type solutions. We introduce a generic, simple broadcasting mechanism that operates in the prefix space of distributed hash tables without signaling. This paper concentrates on the performance analysis of the prefix flooding scheme. Starting from simple models of recursive k-ary trees, we analytically derive distributions of hop counts and the replication load. Further on, extensive simulation results are presented based on an implementation within the OverSim framework. Comparisons are drawn to Scribe, taken as a general reference model for group communication according to the shared, rendezvous-point-centered distribution paradigm. The prefix flooding scheme thereby confirmed its widely predictable performance and consistently outperformed Scribe in all metrics. Reverse path selection in overlays is identified as a major cause of performance degradation.

Keywords: Prefix flooding, DHT, random recursive k-ary trees, overlay network simulation, Pastry, Scribe

There is an increasing economic desire driven by widespread applications like IPTV or conferencing that a next generation Internet will grant transparent group communication service to all its stationary and mobile users. In this paper, we present a generic approach to inter-domain multicast, which is guided by an abstract, DHT-inspired overlay, but may operate on a future Internet architecture. It is based on the assumptions of a globally available end-to-end unicast routing between resolvable locators, taken from a name space that allows for aggregation. Our protocol design accounts for this aggregation, leading to forward-path forwarding along bidirectional shared distribution trees in prefix space. The scheme facilitates multipath multicast transport, offers fault-tolerant routing, arbitrary redundancy for packets and paths and remains mobility agnostic. We present OASIS, its application to IPv6, and evaluate signaling costs analytically based on its k-ary tree structure.

Keywords: Prefix-directed multicast, Bidirectional shared tree, Internet architecture, IPv6

IPTV, software replication, and other large scale content distribution services raise the need for fast and efficient content delivery mechanisms in underlay as well as overlay networks. Multicast, the natural approach on the network layer, has not been deployed globally, and solutions are pushed to the application layer. For a flexible, sustainable deployment the distribution mechanisms in use should scale up to many thousand group members and provide predictable performance to dynamically adjust to actual performance requirements. In this paper, we present a rigorous analytical model complemented by extensive simulations for content delivery on prefix-based overlay trees. We examine BIDIR-SAM, a generic multicast distribution scheme guided by prefixes that allow for late next-hop binding. Our evaluation quantitatively substantiates all major performance aspects. We derive the distribution functions of hop counts, packet replication loads, as well as all relevant cost measures, which scale logarithmically with network and receiver sizes. Prefix-based content delivery exhibits a churn resistance similar to the underlying key-based routing layer and a multicast efficiency scaling factor close to native group communication protocols. These results make the approach especially suitable for large and very large content groups.

Keywords: Content delivery and management on the Internet, Dynamic content delivery and adaptive CDNs, P2P Networks

In-network data processing and event detection on resource-constrained devices are widely regarded as distinctive and novel features of wireless sensor networks. The vision is that through cooperation of many sensor nodes the accuracy of event detection can be greatly improved. On the practical side however, little real-world experience exists in how far these goals can be achieved.
In this paper, we present the results of a small deployment of sensor nodes attached to a fence with the goal of collaboratively detecting and reporting security relevant incidents, such as a person climbing over the fence. Based on experimental data we discuss in detail the process of in-network event detection both from the conceptual side and by evaluating the results obtained. Reusing the same traces in a simulated network, we also look into the impact of multi-hop event reporting.

Keywords: Wireless Sensor Networks, In-network Data Processing, Event Detection, Experimental Evaluation, Use Case, Fence Monitoring

In wireless ad hoc networks and sensor networks, energy use is in many cases the most important constraint since it corresponds directly to operational lifetime. This paper presents two topology control protocols that extend the lifetime of dense ad hoc networks while preserving connectivity, the ability for nodes to reach each other. Our protocols conserve energy by identifying redundant nodes and turning their radios off. Geographic Adaptive Fidelity (GAF) identifies redundant nodes by their physical location and a conservative estimate of radio range. Cluster-based Energy Conservation (CEC) directly observes radio connectivity to determine redundancy and so can be more aggressive at identifying duplication and more robust to radio fading. We evaluate these protocols through analysis, extensive simulations, and experimental results in two wireless testbeds, showing that the protocols are robust to variance in node mobility, radio propagation, node deployment density, and other factors.

Keywords: Wireless Sensor Networks, Adaptive Topology, Topology Control, Energy Conservation

Keywords: Wireless Sensor Networks, Hardware

Keywords: Wireless Sensor Networks, Hardware

Keywords: Wireless Sensor Networks, Hardware

This document describes how to simulate one 802.11b channel in NS2. It focuses on how to simulate wireless transmission error due to bad channel quality. That means BER need to be considered to determine whether one frame is transmitted correctly. To get BER, SNR need to be calculated. The following sections describe current simulation of transmission error in NS2, the methods to calculate SNR and BER, and how to incorporate these methods into NS to achieve our aim - to simulate 802.11b channels as exactly as possible.

Keywords: Simulation

Many surveillance applications of wireless sensor networks monitor the physical world and report the occurrences of events of interest. To ease the process of event detection in these applications, we propose to add a pattern-based event detection mechanism to an SQL-based in-network sensor query processing framework. Different from existing threshold-based event detection, in our pattern-based approach we abstract events into patterns in sensory data and convert the problem of event detection into a pattern matching problem. In addition to handling general patterns for events, we define five types of basic aptterns that are common in real-world applicatiosn in encapsulate the matching of these patterns into system built-in expensive methods. Considering the limited resources on sensor nodes, we design an on-node cache manager to maintain the historical sensory data required for pattern matching and propose processing techniques peculiar to the event-driven queries in our framework. We have conducted experiments using patterns for events extracted from two real-world dtasets and the results demonstrate the effectiveness of our approach.

Keywords: Sensor networks, Event detection, Pattern matching

The Federal Communications Commission (FCC) has announced that it is willing to consider unlicensed operation in the TV broadcast bands. Compared to the ISM bands, this portion of the spectrum has several desirable properties for robust data communications. However, to make efficient use of this spectrum in a way that is non-disruptive to incumbents, there are a number of challenges that must be handled. For example, an unused portion of the spectrum must be found, and it is likely that its availability will vary over time. To address such challenges, we present KNOWS, a cognitive wireless networking system. KNOWS is a hardware-software platform that includes a spectrum-aware Medium Access Control (MAC) protocol and algorithms to deal with spectrum fragmentation. We describe our prototype and present evaluation results obtained from simulating our MAC protocol. We show that in common scenarios KNOWS accomplishes a remarkable 200% throughput improvement over systems that use a IEEE 802.11 based MAC protocol.

Keywords: Channel Assignment

This paper introduces a compact, cheap, and highly reliable fence breach detection system which can detect any activity on the fence and discriminate the type of activity. The hardware is based on utilization of a 3-axis accelerometer and a RISC microprocessor. The system is equipped with a wireless device which enables the system to work remotely and communicate with a base station. We have developed an algorithm to detect activity vs. no-activity on the fence. Moreover, the algorithm is capable of recognizing the type of the breach; whether the breach was due to rattling caused by strong wind or a person climbing on the fence. The recognition algorithm is computationally inexpensive therefore it can be embedded inside the local RISC microcontroller. The proposed system has been tested on different fences and demonstrated an over 90% correct recognition rate.

Keywords: Event Detection

We present a reflector service that seeks to maintain application-level connectivity in the presence of network-level multicast failures. The service is based on the dynamic deployment of autonomous reflectors modelled as mobile agents on top of an active network infrastructure. It is able to repair multicast tree failures by building a self-organising tree of reflectors, which will be connected to each other via unicast. The scheme is decentralised and takes into account node and link resources to find agent locations that lead to low cost tree configurations. We focus on the basic decision mechanisms related to code mobility during the tree construction and destruction phases, namely: cloning, migration, merging and termination. We show some preliminary simulation results that confirm the viability of the approach and settle directions for further research.

Keywords: Service placement

As raw system and network performance continues to improve at exponential rates, the utility of many services is increasingly limited by availability rather than performance. A key approach to improving availability involves replicating the service across multiple, wide-area sites. However, replication introduces well-known tradeoffs between service consistency and availability. Thus, this paper explores the benefits of dynamically trading consistency for availability using a continuous consistency model. In this model, applications specify a maximum deviation from strong consistency on a per-replica basis. In this paper, we: i) evaluate availability of a prototype replication system running across the Internet as a function of consistency level, consistency protocol, and failure characteristics, ii) demonstrate that simple optimizations to existing consistency protocols result in significant availability improvements (more than an order of magnitude in some scenarios), iii) use our experience with these optimizations to prove tight upper bounds on the availability of services, and iv) show that maximizing availability typically entails remaining as close to strong consistency as possible during times of good connectivity, resulting in a communication versus availability trade-off.

Keywords: Service placement

In this paper, we study the application oriented cross-layer protocol design and optimization. The goal of the study is to provide a feasible and flexible approach to solve the conflicts between the requirements of large scale, long life-time, and multi-purpose wireless sensor networks and the constraints of small bandwidth, low battery capacity, and limited node resources. We justify that the cross-layer optimization is a promising solution and sometime is critical to enable wireless sensor network applications.

Keywords: Wireless Sensor Networks

Low power radio, Packet loss, Performance measurement

Keywords: Wireless sensor networks promise fine-grain monitoring in a wide variety of environments. Many of these environments (e.g., indoor environments or habitats) can be harsh for wireless communication. From a networking perspective, the most basic aspect of wireless communication is the packet delivery performance: the spatio-temporal characteristics of packet loss, and its environmental dependence. These factors will deeply impact the performance of data acquisition from these networks.
In this paper, we report on a systematic medium-scale (up to sixty nodes) measurement of packet delivery in three different environments: an indoor office building, a habitat with moderate foliage, and an open parking lot. Our findings have interesting implications for the design and evaluation of routing and medium-access protocols for sensor networks.

In this paper, we investigate the impact of radio irregularity on the communication performance in wireless sensor networks. Radio irregularity is a common phenomenon which arises from multiple factors, such as variance in RF sending power and different path losses depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 platform, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between spherical radio models used by simulators and the physical reality of radio signals. With this model, we are able to analyze the impact of radio irregularity on some of the well-known MAC and routing protocols. Our results show that radio irregularity has a significant impact on routing protocols, but a relatively small impact on MAC protocols. Finally, we propose six solutions to deal with radio irregularity. We evaluate two of them in detail. The results obtained from both the simulation and a running testbed demonstrate that our solutions greatly improve communication performance in the presence of radio irregularity.

Keywords: Sensor networks, wireless communication, radio irregularity, sending power, path loss, link asymmetry, packet loss

In this paper, we present a high fidelity and efficient emulation framework called TWINE, which combines the accuracy and realism of emulated and physical networks and the scalability and repeatability of simulation in an integrated testbed, for evaluation of real protocols and applications. Our measurements show that the TWINE emulation kernel has a memory footprint of less than 100KB, and occupies no more than 3.5% CPU cycles. Thanks to such small overhead and the accurate modeling of physical layer events(at microseconds level), application throughput measured in TWINE is within 5% of the measured throughput from an equivalent physical wireless LAN. A single commodity PC in TWINE can emulate at least four wireless hosts or simulate sixty nodes in real time at microseconds granularity. This paper also illustrates TWINE's novel capabilities via two case studies: a protocol to maintain fairness in mesh networks and an adaptive streaming media application operating in heterogeneous wireless networks. The results from the case studies clearly show the benefit of the TWINE evaluation methodology, by identifying a mismatch between the performance of the protocol or application based on actual user experience versus its performance as measured using traditional network performance metrics such as application throughput.

Keywords: Wireless Sensor Networks, Simulation

The flourish of large-scale network applications across the Internet and or MANET has raised a challenge to network modeling environments that support experimentation and analysis of close interactions between real applications and network dynamics. To facilitate such experimentations, this paper presents MAYA, a multiparadigm network modeling framework including discrete event models, analytical models and physical network interfaces, together with its illustrative implementation using QualNet, fluid flow TCP model and physical network interface. MAYA framework allows users to interface simulated networks directly with physical networks, while attaining realtime constraints even for large-scale networks by incorporating above multiparadigm network modeling techniques. It also gives user the flexibility to emulate applications on nodes in both real and simulated networks. Experiments are conducted to validate the interoperation of QualNet and fluid flow model, to examine the performance of MAYA as well as to evaluate the optimization techniques, namely interleaved execution of fluid flow model and causality-preserve realtime synchronization relaxation. Experimental results indicate that MAYA is a scalable and extensible solution to modeling of close interactions between real application and network dynamics.

Keywords: Design, Performance, Verification, Fluid Flow Model, Network Modeling and Simulation, Physical Network Interface, QualNet, Realtime Simulation

Mobile Ad-Hoc Network (MANET) has become an increasingly active research area with a plethora of work in ad-hoc routing, media access, and protocols, etc. However, much of the effort so far has been in simulation with only a few systems that have ever been implemented and none that we know have been tried in a scale beyond a dozen nodes. One reason is the high complexity involved in implementing and testing actual ad-hoc networks, and the lack of software tools for doing so. We have thus built an inexpensive and flexible environment to support such tasks and to facilitate network research. The core component is a mobility emulator to test an ad-hoc network of virtually any scale and with any mobility scenario without actually moving the nodes physically.

Keywords: Wireless Sensor Networks, Simulation

This article describes information-based approaches to processing and organizing spatially distributed, multi-modal sensor data in a sensor network. Energy constrained networked sensing systems must rely on collaborative signal and information processing (CSIP) to dynamically allocate resources, maintain multiple sensing foci, and attend to new stimuli of interest, all based on task requirements and resource constraints. Target tracking is an essential capability for sensor networks and is used as a canonical problem for studying information organization problems in CSIP. After formulating a CSIP tracking problem in a distributed constrained optimization framework, the paper describes IDSQ and other techniques for tracking individual targets as well as combinatorial tracking problems such as counting targets. Results from simulations and experimental implementations have demonstrated that these information based approaches are scalable and make efficient use of scarce sensing and communication resources.

Keywords: Collaborative Signal Information Processing, Target Classification and Tracking

Most reactive route discovery protocols in MANETs employ a random delay between rebroadcast route requests in order to avoid “broadcast storms”. However this can lead to problems such as “next hop racing”, and “rebroadcast redundancy”. In this paper we propose a Cross-layer Route Discovery Framework (CRDF) to address both problems by exploiting the cross-layer information. A novel Priority-based Route Discovery Strategy (PRDS) serves as the kernel engine of the framework. PRDS assigns a high rebroadcast priority to “good” candidates for the next hop to reduce next hop racing and introduces a competing procedure to keep “bad” candidates from rebroadcasting to alleviate “rebroadcast redundancy”. CRDF is a general framework that can be applied to different reactive routing protocols to improve the routing performance by enhancing route quality while reducing routing overhead. As an example, a macrobian route discovery strategy under CRDF is introduced and evaluated via various simulations.

Keywords: Ad Hoc Networks, Routing, CRDF, PRDS, Wireless Networks

Network research generally requires a simulation or emulation environment to test protocol implementations, to evaluate the performance of a scheme or a system, and to study complicated and highly varying network operations. For large network simulation, simulators will consume a large amount of time and memory, and its result is largely based on some modeling assumptions that may not hold in the real world. Emulators are difficult to scale for large network emulation because of the high cost of equipment if a one-to-one mapping scheme is employed. Otherwise, the target network has to be abstracted to a single router modeled with some performance metrics. In this paper, we present a distributed IP network emulator cluster EMPOWER, which not only can be used to emulate a large network with a limited number of commodity computers, but also can generate user-defined arbitrary network conditions and traffic dynamics at packet level for specific test scenarios. EMPOWER is highly scalable in that each emulator node could be configured to emulate multiple network nodes, and the increment of the number of emulator nodes does not affect emulation validity. Some significant research issues such as network mapping and mobile wireless network emulation are discussed and addressed. Preliminary emulation results show that EMPOWER is capable of assisting the study of both wireline and wireless network protocols and applications.

Keywords: Network Emulation, Simulation, Topology Mapping, Mobile Wireless Networks

As mobile ad hoc networks (MANETs) become ever more popular, it also becomes more and more interesting to build distributed network applications that one is accustomed to from the Internet on top of MANETs. In the Internet, Distributed Hash Tables (DHTs) have recently proven themselves an efficient building block for such distributed applications. However, DHTs are ill-suited for direct deployment in MANETs as they are largely oblivious of the physical routing.
Therefore, we propose MADPastry, a DHT substrate explicitly designed for the use in MANETs. MADPastry considers physical locality and integrates the functionality of a DHT and an ad hoc routing protocol at the network layer to provide an efficient indirect routing primitive in MANETs.
To answer the fundamental question whether the extra overhead of maintaining a DHT in MANETs is really worth the effort or, instead, one would be better off broadcasting the actual lookups in the first place, we compare MADPastry's performance against an unstructured Gnutella-style broadcast agent and a DHT substrate without locality awareness.

Keywords: P2P, MANETs, DHTs, Range Queries

Range query, which is defined as to find all the keys in a certain range over the underlying P2P network, has received a lot of research attentions recently. However, cover query, which is to find all the ranges currently in the system that cover a given key, is rarely touched. In this paper, we first identify that cover query is a highly desired functionality by some popular P2P applications, and then propose distributed segment tree (DST), a layered DHT structure that incorporates the concept of segment tree. Due to the intrinsic capability of segment tree in maintaining the structure of ranges, DST is shown to be very efficient for supporting both range query and cover query in a uniform way. It also possesses excellent parallelizability in query operations and can achieve O(1) complexity for moderate query ranges. To balance the load among DHT nodes, we design a downward load stripping mechanism that controls tradeoffs between load and performance. We implemented DST on publicly available OpenDHT service and performed extensive real experiments. All the results and comparisons demonstrate the effectiveness of DST for several important metrics.

Keywords: P2P, DHTs, Range Queries

Recently, Distributed Hash Tables (DHT) explicitly designed for the use in MANETs have been proposed. Thus, many DHT-based distributed network applications from the domain of the Internet can be expected to be efficiently ported to MANETs. While the exact key lookups provided by such DHTs might be sufficient for many applications, range queries are often a desirable feature in wireless ad hoc networks (e.g. in sensor networks). However, the implementation of range queries using DHTs is a non-trivial task.
In this paper we present a straight-forward implementation of Distributed Segment Trees as proposed in [4] on top of MADPastry [3] to provide DHT-based range queries for MANETs. The main goal of this work is to gain a first insight into the question whether DHT-based approaches for range queries are feasible in MANETs. First experimental results indicate that DHTs can indeed enable efficient range queries in MANETs.

Keywords: DHTs, MANETs, Range Queries, Distributed Segment Trees