Loading...
 

Experiment: Dynamic Distributed Deadline-Aware Collision Avoidance

Authors

Davi Resner
Gustavo Medeiros

Plan

Theme

Wireless Sensor Networks

Scope

Collision avoidance algorithm for transmission of packets with a deadline (i.e. lifeness, time-to-live) in an IEEE 802.15.4 network.

Scenario

A Wireless Sensor Network (WSN) in which a number of nodes send periodic data. All data packets are real-time and must arrive at the destination within a deadline (e.g. the time of the next periodic transmission).
Example: a smart room with several environment sensors.

Problem

All the nodes in the environment compete for the channel to transmit, which calls for a Collision-Avoidance (CA) scheme. In IEEE 802.15.4, there are two variations for CA:

  • GTS (Guaranteed Time Slot) assignment: where a master node allocates slots of time exclusive to a single node. When the node wants to transmit, it simply waits for its slot. This is called the Contention Free Period (CFP), which is followed by a Contention Access Period (CAP), in which nodes use:
  • TDMA (Time-Division Multiple Access) contention: before transmitting, the node follows an algorithm for sleeping for a random time and checking if the channel is free.


WSNs are often very dynamic, with nodes sleeping and failing at different times, and dealing with noisy and lossy channels. In this scenario, it is often better to resort to distributed algorithms, based on local decisions by the nodes, than centralized algorithms based on global decisions by a master node.
The CFP is a centralized solution which i optional in IEEE 802.15.4 networks, and even if it is present and packets are optimally scheduled, there is still a CAP following, in which nodes compete in a fully distributed manner. TDMA is a fully distributed method to compete for the channel, but since it is based on time delays and packets have a deadline, nodes have a limited number of trials to access the channel, which may be insufficient for all the nodes to transmit, resulting in packet loss.

Motivation

We noticed the problem of particular nodes losing too many packets in TSTP, in which nodes send periodic data with a deadline and use time delays to compete for the channel, as described. We wish to demonstrate the problem and validate the solution in a similar case using a well-known protocol (IEEE 802.15.4), so we can later apply the same solution to TSTP. We believe this experiment can be published by itself, and we also plan to write a journal paper on the whole MAC, incorporating results from this experiments.

Proposed Solution

To improve packet delivery rate and/or fairness in the CAP using only local decisions, we need a way for nodes to dynamically detect that they might be losing too many packets and compensate appropriately. A node might be losing more packets than average due to "bad luck" when picking random backoffs, having a particularly bad radio antenna, or being in a particularly noisy region, for example.
We propose tuning the backoff algorithm to use the proximity to the deadline to indicate priority. Nodes with a closer deadline should check the channel more often, and therefore be more likely to win the contention quickly.

Goal

Devise and validate an algorithm to improve packet delivery rate and fairness in the aforementioned scenario.

Tasks

1.1. Define the algorithm

1.1.1. Review similar algorithms in the literature

1.1.2. Define and write the exact mechanism that will be use to compensate the backoff based on the deadline.

1.2. Validate the algorithm

1.2.1. Write a theoretical/statistical analysis of the expected behaviour

1.2.2. Define experiment cases and metrics

1.2.3. Implement the algorithm in Omnet++

1.2.4. Implement the algorithm in EPOSMote III

1.2.5. Run experiments in both implementations and plain IEEE 802.15.4 (i.e. without the proposed backoff modification)

1.2.6. Analyse and compare the results

1.3. Write paper and submit

Experiments

For each topology, two initial experiments will be performed:

  1. Measuring mean round trip time Mrtt: Period = 1s, Size of msgs = 100B, Number of msgs = 10, Repetitions = 10.
  2. Mesuring deadline misses: Period = {0.5*Mrtt, 1*Mrtt, 1.5*Mrtt}, Size of msgs = 100B, Number of msgs = 10, Repetitions = 10.

Nodes' characteristics

  • TX power: 7dBm
  • RX sensitivity: -97dBm

Topology 1: Guto's room

Star topology. 5 sensors, 1 sink, none on batteries.
Locations (all in centimeters, (x,y,z)):
sink (0, 0, 0)
outlet0 (-200, -444, -40)
outlet1 (-50, 30, -40)
lights0 (0, -320, 220)
lights1 (-110, -320, 220)
battery0 (40, 30, -20)
Real world results: Mrtt = X. Deadline misses = {X, X, X}
Simulation results: Mrtt = X. Deadline misses = {X, X, X}

Bibliography

Report

Dynamic Distributed Deadline-Aware Collision Avoidance
Davi Resner, Gustavo Medeiros
Software/Hardware Integration Lab
Federal University of Santa Catarina
davir@lisha.ufsc.br

1.1. Introduction


Introduction must contain the motivation, objectives and the paper's contribution clearly.

1.2. State of Art


In http://www.hindawi.com/journals/ijdsn/2013/139804/#sec3, the authors consider a beacon-enabled IEEE 802.15.4 network. During the contention-free period, the slots are assigned with Rate Monotonic, and during the CAP, nodes are statically assigned a priority level from 1 to 3, and tune the Backoff Exponent (BE) and Contention Window (CW) parameters of the CSMA/CA protocol according to their level (higher-priority nodes will check the channel more often).
Our work contrasts by devising a fully-distributed and dynamic solution, with no traffic classification.

1.3. Implementation Description


Describe your implementation: language, compiler, platform, etc

1.4. Results


What and how you have measured? Put tables, graphics and comment about them.

Are the results good or bad? why?

1.5. Conclusion

Internal Research Grant Application

note: it has been agreed that the author is allowed a PD2M grant (similar to PQ2M) without the 5-minutes presentations and paper submission, due to his performance in industrial projects over the last semester

Referee 1:

  • Name: Rodrigo Schmitt Meurer
  • Grade: 9.0
  • Report:

The author proposes to use a well-known protocol to demonstrate the problem of packet loss due to the random backoff timing. The envisioned solution for such problem is to reduce the packet loss rate by tuning the backoff time algorithm accordingly to each node's respective deadlines. The tests will yield data that will be compared in order to validate the results.
The experiment is very well-thought and has a clear contribution. I only missed a detailed schedule for the proposed tasks. The application for the IRG also fulfils the requirements, since the author showed a very good performance in industrial projects.

Referee 2:

  • Name: João Gabriel Reis
  • Grade: 8.5
  • Report:

Initially, the authors propose to demonstrate the increasing packet
loss due to the limited number of transmitting retries when using TDMA
collision avoidance schemes in 802.15.4 networks. They state the
results can be expanded to a TSTP network. To improve the packet
delivery rate and fairness of the CAP phase in GTS, they propose to
consider the deadline proximity of each node in the backoff algorithm
to indicate priority. This way, a node near its deadline is more
likely to be granted access to the medium in the case of contention.
The experiment scope is quite relevant: it explores a practical
problem in WSNs experienced in real deployments such as the UFSC Smart
Solar Building. Task 2.5 description is not clear, I see that you will
run the experiment in Omnet++ and EPOSMote III but what do you mean by
plain IEEE 802.15.4? The other tasks are clearly described but I
missed a gantt chart to analyse the tasks feasability for a give time
frame. The author fulfils the IRG requirements, the experiment is well
thought, and the scientific contribution is evident thus, the IRG is
justified.