Abstracts


BANMAC: An Opportunistic MAC Protocol for Reliable Communications in Body Area Networks


Abstract
We consider reliable communications in Body Area Networks (BAN), where a set of nodes placed on human body are connected using wireless links. In order to keep the Specific Absorption Rate (SAR) as low as possible for health safety reasons, these networks operate in low transmit power regime, which however, is known to be error prone. It has been observed that the fluctuations of the Received Signal Strength (RSS) at the nodes of a BAN on a moving person show certain regularities and that the magnitude of these fluctuations are significant (5 - 20 dB). In this paper, we present BANMAC, a MAC protocol that monitors and predicts the channel fluctuations and schedules transmissions opportunistically when the RSS is likely to be higher. The MAC protocol is capable of providing differentiated service and resolves co-channel interference in the event of multiple co-located BANs in a vicinity. We report the design and implementation details of BANMAC integrated with the IEEE 802.15.4 protocol stack. We present experimental data which show that the packet loss rate (PLR) of BANMAC is significantly lower as compared to that of the IEEE 802.15.4 MAC. For comparable PLR, the power consumption of BANMAC is also significantly lower than that of the IEEE 802.15.4. For co-located networks, the convergence time to find a conflict-free channel allocation was approximately 1 s for the centralized coordination mechanism and was approximately 4 s for the distributed coordination mechanism.

Back


Quantifying the Channel Quality for Interference-Aware Wireless Sensor Networks


Abstract
Reliability of communications is key to expand application domains for sensor networks. SinceWireless Sensor Networks (WSN) operate in the license-free Industrial Scientific and Medical (ISM) bands and hence share the spectrum with other wireless technologies, addressing interference is an important challenge. In order to minimize its effect, nodes can dynamically adapt radio resources provided information about current spectrum usage is available. We present a new channel quality metric, based on availability of the channel over time, which meaningfully quantifies spectrum usage. We discuss the optimum scanning time for capturing the channel condition while maintaining energy-efficiency. Using data collected from a number of Wi-Fi networks operating in a library building, we show that our metric has strong correlation with the Packet Reception Rate (PRR). This suggests that quantifying interference in the channel can help in adapting resources for better reliability. We present a discussion of the usage of our metric for various resource allocation and adaptation strategies.

Back


Opportunistic Packet Scheduling in Body Area Networks


Abstract
Significant research efforts are being devoted to Body Area Networks (BAN) due to their potential for revolutionizing healthcare practices. Energy-efficiency and communication reliability are critically important for these networks. In an experimental study with three different mote platforms, we show that changes in human body shadowing as well as those in the relative distance and orientation of nodes caused by the common human body movements can result in significant fluctuations in the received signal strength within a BAN. Furthermore, regular movements, such as walking, typically manifest in approximately periodic variations in signal strength. We present an algorithm that predicts the signal strength peaks and evaluate it on real-world data. We present the design of an opportunistic MAC protocol, named BANMAC, that takes advantage of the periodic fluctuations of the signal strength to achieve high reliability even with low transmission power.

Back


Bandwidth Allocation in Hexagonal Wireless Sensor Networks for Real-Time Communications


Abstract
We present an algorithm for bandwidth allocation for delay-sensitive traffic in multi-hop wireless sensor networks. Our solution considers both periodic as well as aperiodic real-time traffic in an unified manner. We also present a distributed MAC protocol that conforms to the bandwidth allocation and thus satisfies the latency requirements of real-time traffic. Additionally, the protocol provides best-effort service to non real-time traffic. We derive the utilization bounds of our MAC protocol.

Back


A Distributed Algorithm for Hexagonal Topology Formation in Wireless Sensor Networks


Abstract
Hexagonal wireless sensor network refers to a network topology where a subset of nodes have six peer neighbors. These nodes form a backbone for multi-hop communications. In a previous work, we proposed the use of hexagonal topology in wireless sensor networks and discussed its properties in relation to real-time (bounded latency) multi-hop communications in large-scale deployments. In that work, we did not consider the problem of hexagonal topology formation in practice -- which is the subject of this research. In this paper, we present a decentralized algorithm that forms the hexagonal topology backbone in an arbitrary but sufficiently dense network deployment. We implemented a prototype of our algorithm in NesC for TinyOS based platforms. We present data from field tests of our implementation, collected using a deployment of fifty wireless sensor nodes.

Back


On Scheduling and Real-Time Capacity of Hexagonal Wireless Sensor Networks


Abstract
Since wireless ad-hoc networks use shared communication medium, accesses to the medium must be coordinated to avoid packet collisions. Transmission scheduling algorithms allocate time slots to the nodes of a network such that if the nodes transmit only during the allocated time slots, no collision occurs. For real-time applications, by ensuring deterministic channel access, transmission scheduling algorithms have the added significance of making guarantees on transmission latency possible. In this paper we present a distributed transmission scheduling algorithm for hexagonal wireless ad-hoc networks with a particular focus on Wireless Sensor Networks. Afforded by the techniques of ad-hoc networks topology control, hexagonal meshes enable trivial addressing and routing protocols. Our transmission scheduling algorithm constructs network wide conflict free packet transmission schedule for hexagonal networks, where the overhead of schedule construction in terms of message exchanges is zero above and beyond that for topology control and other network control related functions. Furthermore, the schedule is optimal in the sense that the bottleneck node does not idle. Based on our transmission scheduling algorithm, we present a clock synchronization algorithm that has no message overhead. We derive the real time capacity of our scheduling algorithm. We present performance evaluations of our scheduling algorithm in the presence of topological irregularities using simulation.

Back


Energy Conserving Data Cache Placement in Sensor Networks


Abstract
Wireless sensor networks hold a very promising future. The nodes of wireless sensor networks (WSN) have a small energy supply and limited bandwidth available. Since radio communication is expensive in terms of energy consumption, the nodes typically spend most of their energy reserve on wireless communication (rather than on CPU processing) for data dissemination and retrieval. Therefore, the role of energy conserving data communication protocols and services in WSN can not be overemphasized. Caching data at locations that minimize packet transmissions in the network reduces the power consumption in the network, and hence extends its lifetime. Finding locations of the nodes for caching data to minimize communication cost corresponds to finding the nodes of a weighted Minimum Steiner tree whose edge weights depend on the edge's Euclidean length and its data traffic rate. We call this tree a Steiner Data Caching Tree (SDCT). We prove that an optimal SDCT is binary, and that at-least two of the three internal angles formed at the Steiner points are equal. We derive expressions that determine the exact location of a Steiner point for a set of three nodes based on their location and their data refresh rate requirements. Based on these (optimality) results, we present a dynamic distributed energy-conserving application-layer service for data caching and asynchronous multicast. We present the results of simulation of our service that verifies its power saving properties.

Back


On real-time capacity limits of multihop wireless sensor networks


Abstract
Multihop wireless sensor networks have recently emerged as an important embedded computing platform. This paper defines a quantitative notion of real-time capacity of a wireless network. Real-time capacity describes how much real-time data the network can transfer by their deadlines. A capacity bound is derived that can be used as a sufficient schedulability condition for a class of fixed-priority packet scheduling algorithms. Using this bound, a designer can perform capacity planning prior to network deployment to ensure satisfaction of applications' real-time requirements.

Back


Energy-Conserving Data Placement and Asynchronous Multicast in Wireless Sensor Networks

Abstract
In recent years, large distributed sensor networks have emerged as a new fast-growing application domain for wireless computing. In this paper, we present a distributed application-layer service for data placement and asynchronous multicast whose purpose is power conservation. Since the dominant traffic in a sensor network is that of data retrieval, (i) caching mutable data at locations that minimize the sum of request and update traffic, and (ii) asynchronously multicasting updates from sensors to observers can significantly reduce the total number of packet transmissions in the network. Our simulation results show that our service subsequently reduces network energy consumption while maintaining the desired data consistency semantics.

Back


Theses

Real-Time Wireless Sensor Networks

Abstract
This dissertation studies real-time application support in wireless ad-hoc and sensor networks. Real-time applications are performance critical applications that require bounded service latency. In multi-hop wireless ad-hoc and sensor networks, communication delays are dominant over processing delays. Therefore, to enable real-time applications in such networks, the communication latency must be bounded. The shared nature of the communication medium makes the delay characteristics of the medium access control (MAC) protocol in use very important. Furthermore, it is desirable that the MAC protocols for such networks be distributed and be able to spatially reuse the communication channel for scalability and efficiency.

In this dissertation, we derive expressions of real-time capacity that characterize the ability of a network to deliver data on time as well as develop network protocols that achieve this capacity. We introduce a hexagonal network topology based architecture for wireless ad-hoc and sensor networks for real-time applications. We present addressing and constant time routing protocols for the hexagonal network. We develop two distributed spatial-reuse time domain multiplexed MAC protocols with provable real-time properties for convergecast traffic. One protocol constructs network-wide transmission schedule and gives equal bandwidth to all the nodes. This protocol has zero scheduling message overhead and is optimal in the sense that the base-station does not idle. The other protocol supports a more general (unequal bandwidth to nodes) mixture of real and non-real time traffic. Clock synchronization is achieved implicitly. Real-time capacity expressions are obtained and analyzed for the earliest deadline first, deadline monotonic and these two scheduling algorithms.

Data gathering (many-to-one) and data dissemination (one-to-many) are two of the three canonical traffic patterns in WSN. Unlike data gathering at base-stations, transmission scheduling for data dissemination is an easy problem and hence is not as much an issue as is the minimization of number of transmissions for interference suppression and energy conservation. We present and prove the properties of an optimal multicast tree in WSN, which is cast as a generalized Steiner Tree Problem. We present a distributed heuristic that constructs and maintains near-optimal multicast tree on-line.

Performance of BLACKBOX Planning System on a Hard Problem of Satisfiability

Abstract
BLACKBOX is one of the best SAT-based planning systems available at present. The system's performance on a supposedly hard problem is presented. The problem is to find values of unbound variables that make a given Problem Goal true. The variables take two values. The goal of the problem is in the form of 3-CNF sentences, e.g., (A OR C OR F) AND (NOT A OR B OR NOT L) AND ... Algorithms are described to find a model for the goal, and to encode the problem in a format that is compatible with the input restrictions of BLACKBOX.

Collective Modes of Dipole Oscillations in Dusty Plasmas

Abstract
Dusty plasma consists of micron size negatively charged particles immersed in plasma. Recent experiments have shown that under appropriate conditions dust grains crystallize. This is significant because it provides an easily observable and manipulable mesoscopic model for studying the dynamics and structure of crystal lattices, solid-liquid phase transitions and to investigate basic plasma interactions. Experiments also suggest that the crystallization is affected by dipole-dipole interaction between dust grains. I have studied the collective modes governed by the dipole-dipole interaction over linear (1D), square (2D) and cubic (3D) lattices. The lattice structure is fixed by the combined Coulomb and dipole interactions and the grains are assumed to carry permanent dipole moments which undergo directional oscillations. The interaction of these dipoles can lead to collective behavior. The dispersion relations for these wobbling modes are discussed. The longitudinal and transverse modes, and instability domains which delineate the different structure boundaries are identified.

Back