Hershey, Pennsylvania
New York, New YorkBeijing, China
Slot Allocation Algorithms for Minimizing Delay in Alarm-Driven WSNs Applications

Slot Allocation Algorithms for Minimizing Delay in Alarm-Driven WSNs Applications

Mário Macedo (INESC-ID, Portugal), António Grilo (INESC-ID, Portugal), and Mário Nunes (INESC-ID, Portugal)
Copyright: © 2011 |Pages: 15
DOI: 10.4018/978-1-60960-589-6.ch008
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

Energy-efficiency and latency requirements in alarm-driven Wireless Sensor Networks often demand the use of TDMA protocols with special features such as cascading of timeslots, in a way that the sensor-to-sink delay bound can stay below the duration of a single frame. However, this single TDMA frame should be as small as possible. The results presented in this paper, point to the conclusion that a largest-distances-first strategy can achieve the smallest single frame sizes, and also the lowest frame size variations. A quite simple distributed version of this algorithm is presented, which obtains the same results of its centralized version. Simulations also show that this discipline presents the best results in terms of sensor-to-sink slot distance, even if they require a few more slots than breadth-first in multi-frame scenarios.
Chapter Preview
Top

While not being a pure TDMA protocol, the Data-gathering MAC (D-MAC) protocol, presented in Lu et al. (2004), uses staggered synchronization so that a data packet received by a node at one level of the tree, is transmitted to the next level in the following time period (i.e., cascading the transmissions in the overall transmission period). The node is then allowed to sleep until the reception period for its level occurs again. D-MAC is still a CSMA/CA based protocol as nodes at the same level of the tree have to compete for timeslot access and may also interfere with nodes located in the same area. Support of several sinks in D-MAC is troublesome.

The use of TDMA for fast broadcast (the converse problem of convergecast) is a well-known subject, which has been studied in the context of multi-hop radio networks. Chlamtac & Kutten (1987) show that the problem of determining optimal channel allocation for fast broadcasting is NP-hard. Two algorithms for tree construction and slot assignment are presented, namely a centralized version, and its distributed version. The distributed algorithm begins at the source node, for which the first slot is granted, and builds a spanning tree, such that each node has a slot number higher than its parent slot, but with the smallest possible value, in order to cascade the broadcast. Tree construction and slot assignment are performed depth-first, by means of passing a token to one node at a time, and by exchanging appropriate protocol messages with the neighbor nodes, in order to obtain a TDMA schedule that meets some slot allocation rules, and that achieves conflict-free schedules. These protocols are also designed to achieve spatial reuse of the slots, with relatively small TDMA frame sizes.

Complete Chapter List

Search this Book:
Reset