A Localized De-synchronization
Algorithm for Periodic Data
Reporting in IEEE 802.15.4 WSNs

Giuseppe Anastasi
Pervasive Computing & Networking Lab (PerLab)
Dept. of Information Engineering, University of Pisa
E-mail: giuseppe.anastasi@iet.unipi.it
Website: www.iet.unipi.it/~anastasi/
PerLabHong Kong Polytechnic University, IMC Lab, April 27, 2013

A Localized De-synchronization
Algorithm for Periodic Data
Reporting in IEEE 802.15.4 WSNs

Based on Joint work withDomenico De Gugliemo, University of Pisa, Italy
Marco Conti, IIT-CNR, Italy
PerLabHong Kong Polytechnic University, IMC Lab, April 27, 2013

Overview
PerLabIntroduction and Motivations
Related Work
ASAP Algorithm
Simulation Results
Current Activity

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

3

Introduction& Motivations

Introduction & Motivations
PerLabEnergy efficiency is typically the major
concern in WSNs
In certain scenarios, additional requirements
need to be considered
Reliability
Scalability
Timeliness…

IEEE 802.15.4/ZigBee is unsuitable
TDMA is typically used in such scenarios
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs5

Introduction & Motivations
PerLab

TDMA provides
guaranteed bandwidth
high energy efficiency
absence of collisions (i.e. reliability)
Predictable latency

Buthas limited flexibility
A change in the operating conditions may require re-computing
the transmission scheduleFinding a collision-free schedule in multi-hop WSNs may be hardrequires synchronization among sensor nodes

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

6

De-synchronization
PerLabDe-synchronization is the opposite ofsynchronizationeach sensor node performs its periodic datatransmissions as far away as possible from all othernodes

Goalarrange periodic transmissions from different sensor
nodes in an interleaved, round-robin style
like in conventional TDMA

without requiring a strict synchronization among sensor
nodes

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

7

Related WorkDe-synchronization in single-hop WSNs
PerLab

Bio-Inspired De-synchronization
Sensor nodes generates packets periodically
Initially, each node selects a random firing time within
the period.
At each step, every nodeobserves the firing time of all other nodes
and derives its own firing time for the next period(e.g., as the midpoint between the firing times of thenodes that fired before and after it)

J. Degesys, I. Rose, A. Patel, R. Nagpal, DESYNC: Self-Organizing Desynchronization and TDMA on Wireless Sensor
Networks, Proc. Int’l Conference on Information Processing in Sensor Networks, Cambridge, USA, April 25-27, 2007.
R. Pagliari, Y. Hong, A. Scaglione, Bio-Inspired Algorithms for Decentralized Round-Robin and Proportional Fair
Scheduling, IEEE Journal on Selected Areas in Communications (J-SAC), Vol. 28, N. 4, May 2010.
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

9De-synchronization in multi-hop WSNs
PerLabMulti-hop DESYNC
The DESYNC algorithm has been extended to multihop sensor networks
J. Degesys, R. Nagpal, Towards DeDe-synchronization of MultiMulti-hop Topologies,Topologies IEEE International
Conference on Self-Adaptive and Self-Organizing Systems (SASO 2008), Venice, Italy, October 2024, 2008.

Localized Multi-Hop De-synchronization
Addresses the hidden node problem
Each node relies on external information
number of nodes, priorities

Not fully localized
H. Kang, J. Wong, A Localized Multi-Hop Desynchronization Algorithm for Wireless Sensor Networks,
Proceedings of IEEE INFOCOM 2009, Rio de Janeiro, Brazil, April 19-25, 2009

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

10

Limits of previous schemes
PerLabThey are not fully localized
Relies on external information to adjust theirtransmission (firing) times
received from either the sink or other sensor nodes

They are not robust against packet losses
a missing information may compromise the correct
behavior

They are not energy efficient
Nodes need to remain active more than necessary toreceive external information

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

11

Our Proposal
PerLabAsynchronous Adaptive Periodic (AsAP) accessCompletely decentralized and local
Nodes decide transmission (firing) times autonomously
On the basis of local information only
Robust against losses and energy efficient

Customized to IEEE 802.15.4 MAC
Non-Beacon Enabled Mode (CSMA/CA)
Can be extended to any contention-based MAC protocol
With minor changes

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

12

AsAP Algorithm

Assumptions and Basic Ideas
PerLabAssumptions
Single-hop network
Packets are generated periodically
All sensor nodes have the same period Ta

The algorithm operates on top of the IEEE 802.15.4 MAC

Basic ideas
Initially all nodes select a random transmission time within
the period Ta
Then, each node dynamically adjusts its transmission timedepending on the outcome of the previous transmission
After some time, a transmission schedule (almost) free ofcollision is obtained.
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

14

AsAP Algorithm
PerLabUpon sending a packet to the sink, four
different outcomes can occuri.

The packet is correctly received by the sink after
the first attempt
ii. The packet is correctly received by the sink after
one or more re-transmissionsiii. The packet is discarded due to exceeded
number of channel access attempts
iv. The packet is discarded due to exceeded
number of re-transmissions

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

15

AsAP Algorithm (case i)
PerLabIf the packet is successfully transmitted at the firstattempt (i.e., without retransmissions)no collisions have occurred
the selected portion of the period is (apparently) free of competitors.

The same time interval will be reused in the next
period.

To minimize latency and energy consumption, the preliminary phase dueto the random backoff time will be avoided.
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs16AsAP Algorithm (case ii)
PerLabThe packet is successfully transmitted with one
or more re-transmissions
The algorithm assumes that re-transmissions arecaused by channel errors
Channel errors are typically caused by a transientphenomenon

The next send time is exactly the same as in thecurrent period

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

17

AsAP Algorithm (case iii)
PerLab

The packet is discarded due to exceeded number ofbackoff stages.
The portion of time selected by the sensor node is congested

It is convenient not to retry the same time in the next period
The sensor node will start sending at a time corresponding tothe end of the current transmission.
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

18

AsAP Algorithm (case iv)
PerLab

The packet is discarded due to exceeded number ofretransmissions
Communication errors (bad channel)
it makes no sense to change the transmission interval as channel
unreliability is typically a transient phenomenon.

Collisions (e.g., due to a hidden node)a change in the transmission interval is convenient

The real cause is unknown to the sensor node
The algorithm initially assumes that retransmissions are caused bycommunication errors the transmission time remains unchanged
If the problem persists the algorithm selects a new transmission time,
randomly in [0, Ta]

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

19

AsAP Algorithm
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

20

Simulation Analysis

Simulation SetupPerLabns2 simulation tool
PHY layer

2.4 GHzBit Rate

250 Kbps

Sensor nodes

from 1 to 180

Distance from Coordinator Node10m

CS range

30m

RX range

15m

Traffic Generation
Message Size

Periodic (period ~1s)
127 bytes

Messages per Period

1Message Loss Rate

0%Coordinator always ON

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

22

Comparison
PerLab802.15.4 MAC in Beacon Enabled Mode (BE)All sensor nodes compete for channel access at thebeginning of each Beacon period.
This scheme maximizes competition

802.15.4 MAC in Beacon Disabled Mode (BD)
Sensor nodes are assumed to transmit data packets at
random times within the period.
This scheme tries to minimize contention, however
conflicts can still occurs.

TDMA
Each node uses its own slot
Conflicts are avoided
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

23

Performance Indices
PerLab

Delivery Ratio
ratio between the number of data packets correctly
received by the sink and the total number of data
packets generated by all sensor nodes.

Average Latency
average time from when the packet transmission isstarted at the source node to when the same packet iscorrectly received by the sink

Avg. Energy Consumption per Packet
total energy consumed by all sensor nodes divided by
the overall number of data packets correctly delivered tothe sink
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

24

Analysis in stationary conditions
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

25

Converge TimePerLabTime taken to reach a steady state
when no sensor node changes its transmissionintervalA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

26

Analysis in Dynamic Conditions
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

27

Summary
PerLabDe-synchronization in WSNs
Collision-free transmission schedule
Without requiring a strict synchronization

Fully localized De-synchronization Algorithm
Only relies on local measurements
Robust against packet losses
Energy efficient

Simulation analysis
AsAP is scalable and provides performance very similar to that of anideal TDMA scheme.

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

28

Further Study
PerLab

Convergence analysis
Derive analytically the time taken to get a complete desynchronization

Comparison with other de-synchronization schemesin terms of convergence time, energy spent to converge,
robustness to losses, …

Extension to multi-hop topologies

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

29

Current Activity

Convergence Analysis
PerLabAssumptions
Time is slotted
N slots available (N is also the # of sensor nodes)

Distributed Slot allocation
Based on local information only6-slot
frame

6-slotframe
31453

56-slot
frame
124Question
How much time it takes to achieve a complete slot
allocation?
A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

31

Localized Slot Allocation
PerLabBased on contention
Each node transmit a (fake) packet on a slot
And wait for the related success/failure notification
Success: the slot is acquired
Failure– Collision– Busy slot

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

32Localized Slot Allocation Algorithm
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

33

Markov ChainPerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

34

Parameters
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

35

Results
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

36

Comparison with CDM
PerLabCollision Detection with Memory
based on a lightweight vertex-coloring approach

Initially, all sensor nodes are in search mode.
At each round (period) p, a generic node v(ii) picks up randomly a color from the set of colors(iiii)
ii checks whether it has a conflict with any other node
If there is no conflict, node v enters permanent mode,
selects c as its permanent color, and stops.
Otherwise, it waits for a new round and performs the sameactions again.

The algorithm ends when all sensor nodes are inpermanent mode.
Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

37

Results
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

38

Results
PerLabA Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

39

Next Activity
PerLabExtension to multi-hop topologies
Comparison between
Ideal localized slot allocation
Asynchronous de-synchronization

Reliable & Energy-Efficient Data Delivery in WSNs with Multiple Mobile Sinks

40

PerLabThank you!

A Localized De-synchronization Algorithm for Periodic Data Reporting in IEEE 802.15.4 WSNs

41

Questions