Int. J. Communications, Network and System Sciences, 2009, 6, 518-527
doi:10.4236/ijcns.2009.26057 Published Online September 2009 (http://www.SciRP.org/journal/ijcns/).
Bandwidth Optimization in 802.15.4 Networks
through Evolutionary Slot Assignment
Vidya KRISHNAMURTHY, Edward SAZONOV
Department of Electrical and Computer Engineering, Wallace H. Coulter School of Engineering
Clarkson University, NY, USA
Received March 26, 2009; revised May 15, 2009; accepted July 29, 2009
ABSTRACT
Traditional Wireless Sensor Networks (WSNs) based on carrier sense methods for channel access suffer
from reduced bandwidth utilization, increase energy consumptions and latency problems in networks with
high traffic. In this work, a novel Evolutionary Slot Assignment (ESA) algorithm has been developed to in-
crease the throughput of large wireless mesh networks with no centralized controller. In the presented
scheme, the sensor nodes self-adapt to the traffic patterns of the network by selecting transmission slots us-
ing evolutionary learning methods. Each sensor node evolves an independent transmission schedule. Unlike
traditional evolutionary methods, fitness evaluation of every node impacts fitness of every other sensor node
in the network. The ESA algorithm has been simulated using Network Simulator-2 and compared with the
IEEE 802.15.4 CSMA-CA, a Static Slot Assignment (SSA) and a Random Slot Assignment schemes (RSA).
Results show a remarkable improvement in the network throughput using the proposed ESA method as op-
posed to other compared methods.
Keywords: CSMA-CA, 802.15.4, Sensor Networks, Evolutionary Algorithms, Bandwidth Optimization
1. Introduction
Wireless Sensor Networks (WSNs) consist of a group of
sensors nodes that use wireless links to perform distrib-
uted sensing tasks. Sensor nodes combine simple wire-
less communication, minimal computational facilities,
and sensing of the physical environment for an applica-
tion-specific sensor network [1]. In monitoring applica-
tions of Wireless Sensor Networks (WSNs), multiple
nodes may desire to transmit at the same time, for exam-
ple in response to an event detected by multiple sensor
nodes. Same time transmissions by multiple nodes lead
to RF collisions that will cause loss of packets. There are
multiple methods for collision detection and avoidance.
The simplest method developed in the 1970s is ALOHA,
where, a node with a packet to transmit waits for a ran-
dom amount of time and then sends the packet. Another
variation of this method was the slotted ALOHA, where
time was divided into slots and nodes wait for the start of
a slot for transmission. In case of a collision, the node
simply retransmits the packet. These methods failed with
increasing network size and data rate [2]. FDMA (Fre-
quency Division Multiple Access) and TDMA (Time
Division Multiple Access) are methods developed and
used in 1980s and early 90s that divide the available fre-
quency spectrum or time into slots and assign them to
different nodes. These methods divide the available re-
sources amongst sensor nodes and therefore are not very
cost effective and cannot deal with rapidly changing
network topology, such as in mobile nodes [3]. Tradi-
tional WSNs are based on collision free carrier sense
methods for channel access. The most commonly used
scheme by the late 1990s is a Carrier Sense Multiple
Access with Collision Avoidance (CSMA-CA) where the
nodes sense the channel to be idle and wait for a random
amount of time before transmission. This restricts the
collision probability to a situation that two nodes may
have a packet at the same time to transmit and the ran-
dom wait time for them happens to be same.
IEEE 802.11 emerged as a popular choice for WSNs
that use CSMA-CA with its four-way handshaking pro-
tocol [4] to increase the reliability of data transfer. But
this protocol and related hardware are too energy con-
suming for low-data rate, low-power networks and en-
ergy scavenging applications. CSMA-CA mechanism
also affects the network latency [5] thus making it unfit

BANDWIDTH OPTIMIZATION IN 802.15.4 NETWORKS THROUGH
EVOLUTIONARY SLOT ASSIGNMENT
519
for monitoring applications with large number of sensor
nodes. The IEEE 802.15.4 protocol [6] has recently
emerged as a new standard for low rate wireless personal
area networks (LR-PANs) [7]. The popularity of the
low-power, low-rate IEEE 802.15.4 protocol and avail-
ability of low-cost, low-power RF chips has led us to use
it for developing low cost Wireless Sensor Networks
targeted towards monitoring applications, such as appli-
cations of structural health monitoring. However, for
synchronous sensor networks that sample data at the
same time or respond to events, the packet collision
probability is seen to tremendously increase with in-
crease in network size [8]. Such collisions tremendously
reduce bandwidth utilization, increase energy consump-
tions and latency of IEEE 802.15.4 devices. The poor
performance of IEEE 802.15.4 based CSMA/CA have
also been analyzed using discrete time Markov chain
models [9].
We performed preliminary analysis of a multi-hop
network to illustrate quality loss of performance in a
high-traffic 802.15.4 CSMA-CA network. Network
Simulator–2 (NS–2) [10] with IEEE 802.15.4 medium
access protocol [11] has been used. The network topol-
ogy consisted of a beacon-less mesh network with one
PAN Coordinator and 30 sensor nodes placed at random
in a 50m-by-50m area (Figure 1). The receiving thresh-
old of every sensor node was limited to 15m. The input
data rate per node was varied and the total network
throughput was measured as the total number of packets
received at the receiver (sink) per second. Figure 2
shows the result of the simulation that clearly suggests
low bandwidth utilization. A possible solution that can
alleviate the problems faced by IEEE 802.15.4 CSMA-
CA based sensor network is a reservation based mecha-
nism where the contention times of each wireless node
should be separated from each other, thus minimizing
collisions and retransmissions. A number of mechanisms
in this direction have been proposed and developed
[12–17].
Our earlier work [18] shows that a reservation sched-
uler could provide up to 5 times increase in data rate and
99% usage of effectively available bandwidth. The
TDMA scheduler works very well in a single-hop star
topology where the central node is aware of all the sen-
sor nodes in the network. But in a typical wireless mesh
network with large number of sources and less number of
sinks, a centralized scheduling is undesirable. Also, in
case of fluctuation in the topology, that is, if sensor
nodes enter and leave the network continuously, a static
scheduling would not work well. In this paper, we pro-
pose a new algorithm, the Evolutionary Slot Assignment
(ESA) algorithm that continuously adapts transmission
schedule of every sensor node without relying on a cen-
tral coordinator. The proposed Medium Access Control
(MAC) layer method is inspired by the evolutionary al-
gorithms [19–27]. However, the proposed ESA algo-
rithm is based on a novel model of specimen interactions
where fitness evaluation of each individual affects fitness
of other nodes in the network. Unlike other de-synchro-
nized algorithms, ESA does not pose assumptions on
topology and connectivity of the network. ESA algo-
rithm does not need a common time reference or beacons
and is well suited for mesh networks and networks with
high node mobility and substantially increases bandwidth
utilization of IEEE 802.15.4 networks.
The next section discusses the proposed method in de-
tail. The simulation scheme has been outlined in Section
3 and Section 4 presents the results and discussion of the
simulated model. Section 5 concludes the paper with
remarks about the method.
2. Methods
To increase the bandwidth utilization and decrease colli-
sions in ad-hoc beaconless wireless sensor networks, a
probabilistic learning-based scheduling algorithm based
on Evolutionary Slot Assignment (ESA) is proposed. We
Figure 1. Tested mesh topology.
Figure 2. Thr oughput of a multi-hop mesh network with 31
nodes with increasing load.

V. KRISHNAMURTHY ET AL. 520
consider a beaconless IEEE 802.15.4 network with high
data rates characteristic for continuously monitoring ap-
plications as our main target. The nodes in the network
are not synchronized in time. The ESA algorithm is im-
plemented at the sensor node level and requires no cen-
tral coordinator or cluster head; does not rely on beacons
or common time reference and does not pose assump-
tions on topology and connectivity of the network.
Each node in the network schedules slots for periodic
transmissions within a time period called the network
period, or Τ. The network period T is divided into virtual
slots where the sensor node attempts to transmit data.
These transmission slots and network period T should
not be confused with the Guaranteed Time Slots and
beacon interval in a beacon-enabled IEEE 802.15.4 net-
work. In ESA, duration of a transmission slot is deter-
mined by the maximum size of data packets with each
slot consisting of 8 to 20 backoff periods corresponding
1) initialize probability vectors:
a.


12
,,......, N
TTT T
VVV V
{0,1}
i
T
V
,
b.


12
,,......, N
TTT T
PPP P
[0,1]
i
T
P
,
2) if packet to transmit at time t:
a. find i: i
V=1 and i > t
b. packet_wait_timer = t – i;
c. if packet_wait_timer == 0
i. transmit packet; α = rand(0,
0.2)
ii. if status == success
ii
PP


, if 1 ,11 T
i
TPP
iii. elseif status == failure
ii
PP



1
, if , if 0, 0
ii
PP


,11 T
i
TPP
iv. elseif status == medium_busy
ii PP


, if 0, 0
ii
PP


3) if i P
< β, then
a. i V= 0
b. j = random number Є {1, 2, ……, N};
j
V= 1
4) adaptation:
a.
9
10
T
i
iT






Figure 3. ESA Algorithm.
to minimal and maximal possible packet lengths. Net-
work period T defines the maximum number of trans-
mission slots that can be scheduled and the length of the
scheduling table. For the purpose of simplicity of analy-
sis, the network period is kept constant for all the sensor
nodes in the network and it is assumed that the network
period starts on node power-up. Since sensor nodes
start-up at random times, the beginning of a network
period is not synchronized between sensors. However,
since every sensor will evolve an independent schedule
without knowing schedules of other nodes, the algorithm
does not need a common time marker or a synchronizing
beacon. All sensor nodes are assumed to have the same
sampling rate and thus have the same average data rate.
This represents heavy load conditions of a real-time mul-
tipoint continuous monitoring application. The sensor
nodes may send data using constant bit rate (CBR) traffic
or an exponential (Poisson) traffic pattern. The number
of slots (N) each node would need to transmit packets of
size (χ bytes) at an average data rate of γ kbps is calcu-
lated for the time Τ as:
*T
N


 (1)
The ESA algorithm for evolution of transmission
schedules (Figure 3) is continuously executed on every
node in the network. The algorithm is divided into the
following phases:
1) Initialization Phase: In this phase, the internal vari-
ables of the algorithm are initialized by each node. A
binary slot vector VΤ is created of size equal to the total
number of transmission slots (N) possible in Τ.


12
,,......, N
TTT T
VVV V, … (2) {0,1}
i
T
V
A 1
i
T
V

indicates a slot in which the node will at-
tempt to transmit.
Another vector PΤ contains the probability associated
with every transmission slot (or fitness of a slot):


12
,,......, N
TTT T
P
PP P, (3) [0,1]
i
T
P
During initialization, all values of VΤ are initialized to
0 and of PΤ to 0.5. Due to periodic nature of the network
period T both vector VΤ and PΤ are ring structures (Fig-
ure 4), i.e. the algorithm traverses from the last element
into the first element of the vectors. Ring representation
allows to eliminate the need for common time reference
since slot m of a wireless node 1 will always correspond
to slot n of wireless node i as long as relative time drift
between the nodes is close to zero (a safe assumption for
most applications). The initial set of (N*r) slots is se-
lected from the list of slots using a tournament selection
algorithm [28]. Specifically, a random number of slots is
drawn from the list of available slots and a single slot j
with the highest probability
j
P
 is selected from the set
and VΤ is updated with
j
V

= 1. The tournament selection

BANDWIDTH OPTIMIZATION IN 802.15.4 NETWORKS THROUGH
EVOLUTIONARY SLOT ASSIGNMENT
521
is repeated till N*r slots are assigned. During the initial
selection procedure, however, the probability of all the
slots is equal and is hence not critical. The redundancy
factor r is needed for any retransmissions due to colli-
sions. An example of the vectors VΤ and PΤ updated with
the initial selected slots is:
VΤ = {0, 0, 1, 0,……0, 1, 1, 0 ……0, 0]}, PΤ = {0.5,
0.5, 0.5, 0.5, ……0.5, 0.5, 0.5, 0.5 ……0.5, 0.5}
2) Transmission Phase: Whenever a node has a packet
to transmit, it traverses the vector VΤ for the next avail-
able slot i () and sets packet_wait_timer to wait
until beginning of slot i to transmits the packet. After
packet_wait_timer expires the node attempts an IEEE
802.15.4 compliant CSMA-CA transmission with ac-
knowledgement and updates vector PΤ based on the out-
come of the transmission as:
1
i
T
V
a) Success: If the packet transmission in slot i is suc-
cessful (acknowledgement received) the probability
value is increased by the absolute value of a random
Gaussian integer α (mean 0, deviation 0.2):
i
P

ii
TT
PP


.
If the results is greater than 1, then . The increase
in slot’s probability increases the fitness measure of the
slot in reward for a successful transmission. Maintaining
above the threshold β is required for continuing use
of slot i in transmission schedule.
1
i
P

i
P

b) Failure: If the packet transmission in slot x fails (no
acknowledgement),
ii
PP


… (4)
For a Gaussian α with zero mean, this operation
equiprobably increases or decreases the fitness of slot i.
However, if0
i
P

 , or if 0
i
P
1
i
T
P


,
. The goal of this fitness (probability) adjustment
1
i
T
P
Figure 4. Ring structure of PT and VT vectors permits
asynchronous operation of wireless.
is to move the transmission probability of nodes com-
peting for access in time slot i in the opposite directions.
The optimal outcome for two competing nodes is when
the probability of the slot in one node is increased and
probability of a matching slot in another node is de-
creased. Using random Gaussian variable as described
will produce such an outcome in 50% of failures.
c) Medium Busy: If the medium is busy when the
packet transmission is attempted in slot i, is decre-
mented by the absolute value of α:
i
P

ii
TT
PP

 How-
ever, if 0
i
P



, 0
i
P


. The probability is de-
creased due to the fact that some other node is using the
medium at this time. Repeated observation of busy me-
dium will cause i
P

falling below the threshold β and
deselection of the slot i.
3) Selection Phase: The probability (fitness) of each
transmission slot marked for transmission in VΤ is ad-
justed in transmission phase. Based on those adjustments,
corresponding values of i P

may fall below the thresh-
old β, indicating that transmissions repeatedly fail in slot
i. The re-selection of slots is performed after completion
of every network period (T) for those slots whose prob-
ability falls below a certain threshold β. This is done
using the tournament selection method. For a slot i with
i
P

< β, i
V

set to 0. A random number of slots are
drawn from the list of unused slots and the slot j with of
the highest probability value among these slots is
selected. This procedure is repeated for all slots that need
rescheduling (such slots are excluded from the pool from
which new slots are drawn).
i
P

4) Adaptation Phase: Being a part of a multi-hop mesh
network, a node may receive packets that need to be
forwarded. Therefore, additional slots for forwarding
traffic need to be added to the transmission schedule
every interval T. Since a node makes no assumptions of
topology of the network and ESA algorithm does not use
information from upper layers (routing for example), the
number of forwarding slots δ is estimated for by moni-
toring the total number of forwarding packets received
by a node over each time period Τ. The value of δ is
computed and updated every network period based on a
floating average of δ for the last 10 network periods.
Thus the total number of slots available for a node in the
interval Τ is (N*r + δ). Selection of δ additional slots in
the vector VΤ is performed by tournament selection. After
adaptation phase the node transitions into transmission
phase.
This evolutionary process is performed on a continu-
ous basis and adapts the node to the network traffic con-
ditions. It should also be noted that the ESA algorithm is
not a classical evolutionary algorithm. Traditional evolu-
tionary algorithms (genetic algorithms, evolution strate-
gies, etc.) evolve a population of individuals but fitness

V. KRISHNAMURTHY ET AL. 522
of any given individual does not impact fitness of other
individuals in the population. In ESA fitness is inter-
preted as transmission probability associated with a slot.
A node evaluates fitness of a slot by attempting a trans-
mission and thus actively impacting fitness of matching
slots in schedules of all other nodes that may attempt a
transmission at the same time. In this sense the ESA al-
gorithm is better characterized as a competitive co-evo-
lutionary algorithm.
To illustrate the gain in bandwidth utilization due to
evolutionary component of the algorithm, we propose
two simplified variants of the above Evolutionary Slot
Assignment (ESA) and compare them with the regular
CSMA-CA mechanism. First is a Static Slot Assignment
(SSA) technique where both the evolutionary mechanism
and randomness of slot reselection are eliminated. In
SSA the slot vector VΤ is initialed to (N*r + δ) slots. The
data packets are only transmitted in this pre-selected
random slot schedule and PΤ vector is never updated.
Second is Random Slot Assignment (RSA) algorithm in
which the evolutionary component is eliminated but
randomness of slot reselection is maintained through
periodic re-initialization of the transmission schedule VΤ
every period for (η*r + δ) slots. Comparison with SSA
and RSA allows evaluating the performance gain attrib-
uted to evolutionary learning. We also perform compari-
son to standard CSMA-CA technique to illustrate per-
formance gain of ESA.
3. Simulation Scheme
Network Simulator–2 (NS–2) [10] with IEEE 802.15.4
medium access protocol [6] has been used to simulate
ESA, SSA and RSA methods. The simulation scenario
consists of a beaconless network with one PAN Coordi-
nator and 30 nodes placed at random in a 50m-by-50m
area (Figure1) with range of each node limited to 15m.
The nodes utilize the IEEE 802.15.4 medium access and
physical layers for transmissions and receptions. The
nodes are not synchronized in time and start-up at ran-
dom times. The ESA algorithm was implemented at the
SSCS (Service Specific Convergence Sublayer) that acts
as an interface between the MAC and the upper layers.
The SSCS layer is an implementation specific module
that provides access to the MAC primitives and allows
for their modification for any specific application. A
wireless channel with two-ray ground propagation model
was used. Each node is chosen to have omni-directional
antenna and the maximum number of packets allowed in
the interface queue was set to 10. The packets were
transmitted using AODV routing protocol [29].
One of the nodes (Node 0) is assigned as the PAN
Coordinator. This node allows all other nodes to join the
network through the regular association procedure of the
IEEE 802.15.4 standard [6]. This node is also used as the
sink node. However, it is no different from any other
node in functionalities and other nodes may be sinks too.
The nodes formed a star network (single-hop, single re-
ceiver) or a mesh network (multi-hop, multiple receivers)
topology with up to five hops. The average data rate per
node is varied from 0.2 kbps to 3.2 kbps, placing the
upper bound on the total network throughput at 100 kbps
(max possible throughput of the IEEE 802.15.4 network
[18]). No assumptions was made on packet inter-arrival
time except that every node attempts to send all the data
in the network period of T=5 seconds. The length of sin-
gle transmission slot of the SSA, RSA and ESA algo-
rithms was set to be 20 backoff slot (6.4 milliseconds)
allowing the maximal possible packet size of 127 bytes.
The following medium access methods were used for
each topology:
a) CSMA-CA: A regular CSMA-CA channel access
mechanism to analyze the network throughput under
varying loads. Here, whenever a sensor node has a
packet to transmit, it waits for a random amount of time
and then senses if the medium is free and if so, transmits
the packet. In case the medium is busy or the packet fails
delivery (no acknowledgement received), the node waits
for another random amount of time and then retries. The
limit on the maximum transmission attempts for a single
packet was set to 3.
b) Static Slot Assignment scheme with a fixed redun-
dancy factor δ=0.05*r: The random schedule is selected
at start-up with (N*r + δ) slots, as discussed in Section II.
When a sensor node has a packet to transmit, it traverses
the schedule to look for the next slot marked as available
for transmission. The time until that slot is calculated and
a wait timer is generated. The packet is transmitted in the
slot using CSMA/CA. Any retransmissions also follow
the same procedure. The mesh forwarding parameter δ
remains constant and the slot schedule is not updated
during operation.
05001000 15002000 25003000
0
20
40
60
80
100
120
Star Network
Data Rat e per Node (bps)
Network T hroughput (Packets /Second)
CSMA - CA
ESA
SSA
RSA
Theoretic al Li m i t
Figure 5. Comparison of throughput of a Star Network
with CBR traffic.

BANDWIDTH OPTIMIZATION IN 802.15.4 NETWORKS THROUGH
EVOLUTIONARY SLOT ASSIGNMENT
523
01000 2000 3000 4000 5000
0
200
400
600
800
1000
1200
1400
1600
1800
2000
2200
2400
2600
2800
3000
3200
3400
200 bps
400 bps
800 bps
1600 bps
2400 bps
3200 bps
Through p ut (Number of pac kets/ 50 seconds)
Data rate per node (bps)
(a)
05001000 15002000 2500 3000 3500
0
500
1000
1500
2000
2500
3000
3500
4000
Convergen ce T im e (s e c)
Data rate per node (bps)
(b) (c)
Figure 6. (a) Comparison of throughput varying with simulation time of an ESA Star network with CBR traffic with differ-
ent data rates (b) Convergence times of an ESA Star network with CBR traffic at different data rates (c) Histogram of packet
transmission for 400bps data rate for a Star Network with CBR traffic.
c) Random Slot Assignment: A random schedule is
generated by each sensor node every network period by
random re-initialization of VΤ to mark (η*r + δ) slots as
available for transmission. Packet transmissions follow
the same procedure as in part (b) above. The vector PΤ is
not updated with the status of the transmissions and pa-
rameter δ=0.05*r remains constant.
d) Evolutionary Slot Assignment: The network is
simulated with every node using ESA algorithm as out-
lined in Section II. Vector PΤ is updated after every
transmission attempt and vector VΤ is updated by tour-
nament selection every network period. Redundancy
parameter δ is updated every network period.
Star and multi-hop mesh network topologies with con-
stant-bit-rate (CBR) traffic from the sensor nodes and a
mesh topology with Poisson traffic were analyzed. All
simulations were run for 5000 seconds. The throughput
was measured as the net received data in the last 1000

V. KRISHNAMURTHY ET AL. 524
seconds of the simulation. The effect of increasing traffic
on the throughput network was studied. The convergence
time was measured as the time taken to settle to 90% of
the maximum stable value. In order to avoid any local-
ized inferences, the results are averaged from three ran-
dom seeds of each simulation setup.
4. Results
Three different simulation scenarios were created as dis-
cussed in the previous section: a star topology with CBR
traffic, mesh topology with CBR traffic and a mesh to-
pology with Poisson traffic.
Figure 5 shows the throughput of the network at vary-
ing input data rates for the different methods of medium
access for a 31 node star network. It can be clearly seen
that as the data rate per node increases, the throughput of
CSMA-CA method falls below 20 kbps or ≈20% of use-
ful bandwidth. The peak of SSA and RSA methods bring
the throughput up to 50 kbps but for a large data rate of
3.2 kbps per node, the network throughput is seen to fall.
On the other hand, the maximum network throughput
achieved by ESA is about 60 kbps which is a 300% im-
provement over a CSMA-CA network. From Figure 6(a)
and 6(b), it can be seen that the convergence time of
ESA increases exponentially with increase in the data
rate per node.
Mesh networks do not follow the same behavior as
that of the star networks since they have to adjust their
schedules to cater to intermediate traffic, even when
these nodes are absolutely unaware of the routes estab-
lished. Figure 7(a) shows that for mesh networks,
CSMA-CA outperforms SSA and RSA for lower data
rates, however for higher data rates, these algorithms
begin to show better performance than CSMA-CA. The
ESA method out-performs all other methods by provid-
ing up to a 200% improvement in throughput compared
to any other tested method. ESA provides fair channel
access to all nodes of the network as illustrated in Figure
6(c) and Figure 9(c).
5. Discussions
The very first observation is that in both star and mesh
network configurations ESA provides a consistent ad-
vantage over IEEE 802.15.4 CSMA-CA protocol and
simpler SSA and RSA methods. Results demonstrate that
ESA creates a substantial (200%–300%) improvement in
throughput over CSMA-CA networks while providing
fair access to the medium. This increase in performance
is created without any awareness of packet routing,
without centralized scheduling and extra scheduling traf-
fic, and without using a common time reference, beacons
or knowing schedules of other nodes. Performance gain
200 400800160024003200
0
20
40
60
80
100
120
Mesh Network
Data Rate per Node (bps)
Network T hroughput (P ackets/Second)
CS MA-CA
ESA
SSA
RS A
Theoret i cal Li m i t
Figure 7. Comparison of throughput of a Mesh Network
with CBR traffic
05001000 15002000 25003000
0
20
40
60
80
100
120
Poisson Mesh Network
Data Rat e per Node (bps)
Network Th roughput (P ac k ets / S ec ond)
CS MA-CA
ESA
SSA
RS A
Theoretical Li m i t
Figure 8. Comparison of throughput of a Mesh Network
with poisson traffic.
of the ESA method becomes very clear for networks with
high traffic, where probability of collisions grows signifi-
cantly. As results in Figure 5, Figure 7 and Figure 8
show, performance of the simpler SSA and RSA meth-
ods degrade significantly for higher bit rates since nei-
ther transmission slots nor CSMA-CA procedure are not
capable of effective collision resolution under heavy
loads. ESA gains this improvement by adapting individ-
ual transmission schedule of each node so that the total
number of collisions is minimized. This adaptation is
purely based on outcome of packet transmission and in-
dependent of neighboring node visibility, thus eliminat-
ing any need for knowledge of network topology (ex.
hidden terminal problem).

BANDWIDTH OPTIMIZATION IN 802.15.4 NETWORKS THROUGH
EVOLUTIONARY SLOT ASSIGNMENT
525
The second observation is that the consistent gain in
bandwidth utilization of ESA method is achieved
through the adaptive, evolutionary nature of the algo-
rithm. Random selection nature of SSA and RSA meth-
ods itself shows improvement over CSMA-CA for higher
data rates by increasing the overall randomness of the
channel access. However, under heavy load condition
ESA provides almost twice the bandwidth in comparison
to SSA and RSA (Figure 5 and Figure 7). Another im-
portant clue showing the advantage of evolutionary ad-
aptation is presented in Figure 7, where throughput of
SSA and RSA for data rates below 2.4kbps is worse than
pure CSMA-CA. We attribute this effect to the fact that a
node in a pure IEEE 802.15.4 CSMA-CA network is not
bound by a schedule and has more attempts at transmis-
sion than a node using SSA or RSA. ESA will attempt
virtually the same number of transmission attempts as
SSA and RSA but adapting the schedule will allow ESA
to avoid most collisions and thus provide reliable per-
formance over a wide range of data rates.
Our third observation is that the speed of convergence
for ESA (Figure 6(b) and Figure 9(b)) depends on a spe-
cific network configuration and traffic. The convergence
is fastest for networks with low traffic since there exists
01000 2000 3000 4000 5000
0
200
400
600
800
1000
1200
1400
1600
1800
2000
200 bps
400 bps
800 bps
1600 bps
2400 bps
3200 bps
Network Throughput
(Number o f p a c kets/ 50 seconds )
Data Rate per node (bps)
(a)
05001000 1500 20002500 3000 3500
2000
2500
3000
3500
4000
4500
5000
5500
Convergence Time (sec)
Data rate per node (bps)
(b) (c)
Figure 9. (a) Throughput varying with simulation time of an ESA mesh network with poission traffic at different data rates
(b) Convergence times of an ESA Star network with CBR traffic at different data rates (c) Histogram of packet transmission
for 400bps data rate for a Mesh Network with CBR traffic.

V. KRISHNAMURTHY ET AL. 526
a multitude of possible non-conflicting transmission
schedules. As the network size grows, the number of
possible solutions is decreased and the algorithm spends
a longer time seeking a suitable set of schedules.
Finally, we would like to note that the ESA algorithm
is computationally lightweight and can be easily imple-
mented even on most energy-constrained platforms. For
example, the number of C code lines in the ESA sched-
uler is 652. On the other hand, the proposed algorithm
can actually reduce power consumption of a node by
reducing the number of retransmission attempts. Overall,
one of the strong points of ESA is that the schedule will
remain stable if all packets are delivered as needed and
will self-adapt if the traffic pattern is changed.
6. Conclusions
In this work, a novel Evolutionary Slot Assignment was
developed and tested. In the ESA method, the sensor
nodes, independent of each other, adapt internal sched-
ules to a traffic pattern minimizing collisions and im-
proving bandwidth utilization. ESA method makes no
assumption of network topology, packet routing, traffic
from neighboring nodes, does not require a centralized
scheduler and does not create scheduling traffic. ESA
also does not need to know schedules of neighboring
nodes and does not require a common time marker or
synchronizing beacons. Simulations were performed for
two topologies, a star and a mesh network, and two dif-
ferent traffic scenarios, constant-bit rate traffic and Pois-
son traffic. Networks using CSMA-CA medium access
were compared with the static slot assignment, random
slot assignment and the evolutionary slot assignment
algorithms. Simulation results show 200%–300% im-
provement in throughput of proposed ESA algorithm in
comparison to pure CSMA-CA.
7. References
[1] H. Karl and A. Willig, “A short survey of wireless sensor
networks,” Telecommunication Networks Group, Tech-
nische Universitat Berlin, Hasso-Plattner Institute, Pots-
dam.
[2] A. El-Hoiydi, “Aloha with preamble sampling for spo-
radic traffic in ad hoc wireless sensor networks,” in Pro-
ceedings of IEEE International Conference Communica-
tions, pp. 3418–3423, 2002.
[3] I. Demirkol, C. Ersoy, and F. Alagöz, “MAC protocols
for wireless sensor networks: A survey,” IEEE Commu-
nications Magazine, Vol. 44, No. 4, pp. 115–121, 2006.
[4] G. Bianchi, “Performance analysis of the IEEE 802.11
distributed coordination function,” IEEE Journal on Se-
lected Areas in Communications, Vol. 18, No. 3, pp.
535–547, March 2000.
[5] J. Zheng and M. J. Lee, “A comprehensive performance
study of IEEE 802.15.4,” IEEE Press Book, 2004.
[6] IEEE P802.15.4/D18, Draft Standard: Low Rate Wireless
Personal Area Networks, February 2003.
[7] G. Lu, B. Krishnamachari, and C. S. Raghavendra, “Per-
formance evaluation of the IEEE 802.15.4 MAC for
low-rate low power wireless networks,” in Proceedings of
IEEE International Performance Computing and Com-
munication Conference (IPCCC’04), pp. 701–706, Phoe-
nix, AZ, April 2004.
[8] J. Misic, S. Shafi, and V. B. Misic, “Maintaining reliabil-
ity through activity management in 802.15.4 sensor clus-
ters,” IEEE Transactions on Vehicular Technology, Vol.
55, No. 3, pp. 779–788, 2006.
[9] J. Misic, S. Shafi, and V. B. Misic, “Performance of bea-
con enabled IEEE 802.15.4 cluster with downlink and
uplink traffic,” IEEE Transactions on Parallel and Dis-
tributed Systems, Vol. 17, No. 4, pp. 361–376, 2006.
[10] K. Varadhan, “The Ns manual,” The VINT Project, Au-
gust 2000.
[11] E. Sazonov, R. Jha, K. Janoyan, V. Krishnamurthy, M.
Fuchs, and K. Cross, “Wireless intelligent sensor and ac-
tuator network (WISAN): A scalable ultra-low-power
platform for structural health monitoring,” SPIE Pro-
ceedings 6177, March 2006.
[12] W. Ye, J. Heidemann, and D. Estrin, “An energy-efficient
MAC protocol for wireless sensor networks,” IEEE In-
focom’02, Vol. 3, pp. 1567–1576, June 2002.
[13] T. van Dam, and K. Langendoen, “An adaptive en-
ergy-efficient MAC protocol for wireless sensor net-
works,” ACM SenSys 2003, pp. 171–180, November
2003.
[14] C. S. Raghavendra and S. Singh, “PAMAS–power aware
multi-access protocol with signaling for ad hoc net-
works,” ACM Computer Communications Review, Vol.
28, No. 3, pp. 5–26, 1998.
[15] M. J. Miller and N. H. Vaidya, “On-demand TDMA
scheduling for energy conservation in sensor networks,”
Technical Report, University of Illinois at Urbana
Champaign, 2004.
[16] M. L. Sichitiu, “Cross-layer scheduling for power effi-
ciency in wireless sensor networks,” IEEE Infocom’04,
March 2004.
[17] V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves,
“Energy-efficient, collision-free medium access control
for wireless sensor networks,” ACM SenSys’03, pp.
181–192, November 2003.
[18] V. Krishnamurthy and E. Sazonov, “A reservation-based
protocol for monitoring applications using IEEE 802.15.4
sensor networks,” in International Journal of Sensor
Networks, Vol. 4, No. 3, pp. 155 –171, 2008.
[19] T. Bäck, “Evolutionary algorithms in theory and prac-
tice,” Oxford University Press, New York, 1996.
[20] T. Bäck, D. Fogel, and Z. Michalewicz, “Handbook of
evolutionary computation,” Oxford University Press,
1997.
[21] S. Baluja, “Population-based incremental learning: A

BANDWIDTH OPTIMIZATION IN 802.15.4 NETWORKS THROUGH
EVOLUTIONARY SLOT ASSIGNMENT
527
method for interacting genetic search based function op-
timization and coemptive learning,” Technology Repub-
lic, No. CMU-CS-94-163, Carnegie Mellon University,
1994.
[22] G. Harik, F. G. Lobo, and D. E. Goldberg, “The compact
genetic algorithm,” in Proceedings of the International
Conference on Evolutionary Computation (ICEC 98), pp.
523–528, 1998.
[23] H. Pang, K. Hu, and Z. Hong, “Adaptive PBIL algorithm
and its application to solve scheduling problems,” IEEE
International Symposium on Computer-Aided Control
Systems Design, pp. 784–789, October 2006.
[24] Z. He, C. Wei, B. Jin, W. Pei, and L. Yang, “A new
population-based incremental learning method for the t-
raveling salesman problem,” in Proceedings of the 1999
Congress on Evolutionary Computation, Vol. 2, pp.
–1156, 1999.
[25] S. Yang and X. Yao, “Dual population-based incremental
learning for problem optimization in dynamic environ-
ments,” in M. Gen et al. (editors), Proceedings of the 7th
Asia Pacific Symposium on Intelligent and Evolutionary
Systems, pp. 49–56, 2003.
[26] S. Baluja and D. Simon, “Evolution-based methods for
selecting point data for object localization: Applications
to computer-assisted surgery,” International Journal of
Applied Intelligence, Vol. 8, pp. 1–13, 1997.
[27] L. Chen and A. Petroianu, “Application of PBIL to the
optimization of PSS tuning, power system technology,”
in Proceedings of 1998 International Conference on
Power System Technology, Vol. 2, pp. 834–838, 1998.
[28] B. L. Miller and D. E. Goldberg, “Genetic algorithms,
tournament selection, and the effects of noise,” Complex
Systems, pp. 193–212, June 1995.
[29] C. E. Perkins and E. M. Royer, “The ad hoc on-demand
distance vector protocol,” Ad hoc Networking, Addi-
son-Wesley, pp. 173–219, 2000.