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