Abstracts


A Bandwidth Allocation Scheme for Real-Time Communication in Hexagonal Wireless Sensor Networks


K. Shashi Prabh, Tarek F. Abdelzaher
Dept. of Computer Science,
University of Illinois, Urbana-Champaign, IL, USA
In submission

Abstract
In this paper, we consider the problem of bandwidth allocation for both periodic as well as aperiodic traffic in a multi-hop wireless sensor network connected in a hexagonal topology. We present an algorithm for bandwidth allocation to periodic and budgeted real-time and non-budgeted best-effort aperiodic traffic. We present a token based MAC protocol for scheduling of the packets. We derive the utilization bounds and the real-time capacity of the MAC protocol.

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


K. Shashi Prabh (1), Tarek F. Abdelzaher(2)
Dept. of Computer Science,
(1) University of Virginia, Charlottesville, VA, USA
(2) University of Illinois, Urbana-Champaign, IL, USA
In the Proceedings of the 19th Euromicro Conference on Real-Time Systems
Publication Date: 4-6 July 2007
On pages: 136 -- 145

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


EDF Scheduling of Real-Time Aperiodic Tasks on a Pipeline


K. Shashi Prabh, Tarek F. Abdelzaher
Department of Computer Science
University of Virginia, Charlottesville, VA, USA
In submission

Abstract
We analyze the schedulability of real-time aperiodic tasks on a pipeline using preemptive Earliest Deadline First (EDF) scheduling algorithm. We derive sufficient end-to-end schedulability conditions with and without the presence of information on the breakdown of the overall compute time of the tasks across the stages of the pipeline. We show that among all possible distributions of compute time, the load balanced distribution guarantees maximum system utilization. We present constant-time admission control algorithms based on the utilization bounds derived herein, and evaluate the performance of these admission controllers experimentally.

Back


Energy Conserving Data Cache Placement in Sensor Networks


K. Shashi Prabh, Tarek F. Abdelzaher
Dept. of Computer Science,
University of Virginia, Charlottesville, VA, USA
The ACM Transactions on Sensor Networks, Volume 1, Number 2, page 178--203, 2005

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


Tarek F. Abdelzaher, K. Shashi Prabh, Raghu Kiran
Dept. of Computer Science
University of Virginia, Charlottesville, VA, USA
In the Proceedings of the 25th IEEE International Real-time Systems Symposium (RTSS)
Publication Date: 5-8 Dec. 2004
On page(s): 359 - 370

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

Sagnik Bhattacharya, Hyung Kim, Shashi Prabh, and Tarek Abdelzaher
Dept. of Computer Science
University of Virginia, Charlottesville, VA, USA
In the Proceedings of the The First International Conference on Mobile Systems, Applications, and Services (MOBISYS)
Publication Date: 5-8 May 2003
On page(s): 173-186

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

K. Shashi Prabh
Department of Computer Science
University of Virginia, Charlottesville, VA, USA

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

K. Shashi Prabh
Department of Computer Science
New York University, New York, NY, USA

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

K. Shashi Prabh
Department of Physics
Boston College, Chestnut Hill, MA, USA

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