Bulk Synchronous Medium Access (BSMA) for Sink-based Wireless Sensor
Networks
-
Abstract
Time division multiple access (TDMA) or its assisted method has been
considered for wireless sensor networks (WSNs) due to its superior energy
performance. Since it offers collision-free medium access, it does not
wastage energy on collisions. No control overhead is incurred as nodes
need not contend for the medium. However, TDMA schemes suffer from a high
periodic cost to generate collision-free transmission schedules in a dynamic
environment. Although this problem can be addressed reasonably well in
quasi-static WSNs, their applicability is still limited because they are
not as flexible and robust as carrier sense multiple access (CSMA) protocols.
The main difference between the two is that CSMA is a simple trial-and-error
approach while TDMA is a more complicated speculative approach. In TDMA,
each node speculates on schedule conflicts based on the assumption that
any two nodes within 2-hop connectivity necessarily and sufficiently cause
collisions. However, this does not hold in a realistic communication environment
with obstacles, natural surroundings and changes in communication environment.
They are highly likely to cause asymmetric links and link-quality variations,
and the resultant transmission schedule neither completely eliminates collisions
nor utilizes all available communication opportunities. This paper presents
Bulk Synchronous Medium Access (BSMA), which is a TDMA algorithm but does
not speculate on collisions but just tries it, to generate a collision-free
transmission schedule for sink-based WSNs. It is simple and robust, consumes
less energy and helps reduce message latency, particularly for sensor-to-sink
traffic.
-
Technical report
-
Design issues in wireless sensor networks
-
Energy efficient and fast delivery of a sensed data to a sink
-
Robust communciation in the presence of unreliable communication environment
-
Deterministic performance (energy, message latency)
-
Conventional methods
-
CSMA-based methods: Robust but worst-case performance is not bunded
-
Low duty-cycle based methods (S-MAC, T-MAC, Z-MAC): An event triggers many
reports simultaneously making its performace even worse
-
TDMA-based methods: Underlying two-hop graph-coloring algorithm is not
correct
-
Code
-
Code base: ns-2.26 (network simulator)
-
Source code: bsma.cc, bsma.h
(replacing 802.11 mac code), shadowing.cc (for
simulating unreliable links)
-
Run script: test1.tcl
-
The run script generates not only a trace file but also a number of sm
(Super Mongo) files,
which shows the tree structure in each scheduling phase.
-
We used shadowing radio propagation model to simulate random, asymmetric
communication links. Its randomness is controlled by the value of SD (standard
deviation). However, we assume that the asymmetry is casused by natural
sorroundings and obstacles. In other words, once a link is simulated as
asymmetric in its initial evaluation, it continues to be asymmetric during
the entire network lifetime.
-
Tree construction in BSMA
-
SD denotes the standard deviation in shadowing model (see Section 18.3
of ns-2 manual).
The higher the value of SD, the more radom is the channel. Default value
of SD in ns-2 is 0dB, which means that the radio propagation is deterministically
determined based on communication distance between the sender and the receiver.
-
Zo denotes the capture ratio (see Zorzi, M., and Rao, R. Capture and retransmission
control in mobile radio. IEEE Journal on Selected Areas in Communications,
12(8), 1994, 1289-1298 and C. Yu, K. G. Shin, and L. Song. Link-Layer
Salvaging for Making Routing Progress in Mobile Ad Hoc Networks. ACM
MobiHoc, 2005). When the capture is perfect (Zo=1dB), the receiver can
successfully decode the signal if it signal strength is slightly higher
than interference. In wireless sensor networks, the effect of channel capture
is significant becuaser they employ lower data rate.
-
Each scenario in the below below depicts the BSMA tree of 250 sensor nodes
in consecutive scheduling phases. Sensor nodes in small red circles denote
"orphans" that do not belong to the main tree in the corresponding scheduling
phase. The BSMA tree is completed when it becomes zero.
Mobile Computing Research
Laboratory
Department of Electrical and
Computer Engineering
Cleveland State University
Mailing: Stilwell Hall 437, 2121 Euclid Avenue, Cleveland, OH
44115-2425
Telephone: (216) 687-2584
Email: c.yu91@csuohio.edu