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