On scheduling and real-time capacity of hexagonal wireless sensor networks

K. Shashi Prabh, Tarek F. Abdelzaher

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Since wireless ad-hoc networks use shared communication medium, accesses to the medium must be coordinated to avoid packet collisions. Transmission scheduling algorithms allocate time slots to the nodes of a network such that if the nodes transmit only during the allocated time slots, no collision occurs. For real-time applications, by ensuring deterministic channel access, transmission scheduling algorithms have the added significance of making guarantees on transmission latency possible. In this paper we present a distributed transmission scheduling algorithm for hexagonalwireless ad-hoc networks with a particular focus on Wireless Sensor Networks. Afforded by the techniques of ad-hoc networks topology control, hexagonal meshes enable trivial addressing and routing protocols. Our transmission scheduling algorithm constructs network-wide conflict-free packet transmission schedule for hexagonal networks, where the overhead of schedule construction in terms of message exchanges is zero above and beyond that for topology control and other network control related functions. Furthermore, the schedule is optimal in the sense that the bottleneck node does not idle. We also present an implicit clock synchronization algorithm to facilitate scheduling. We derive the real time capacity of our scheduling algorithm. We present evaluations of our scheduling algorithm in the presence of topological irregularities using simulation.

Original languageEnglish (US)
Title of host publicationProceedings - 19th Euromicro Conference on Real-Time Systems, ECRTS 2007
Number of pages10
StatePublished - 2007
Event19th Euromicro Conference on Real-Time Systems, ECRTS 2007 - Pisa, Italy
Duration: Jul 4 2007Jul 6 2007

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070


Other19th Euromicro Conference on Real-Time Systems, ECRTS 2007

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture


Dive into the research topics of 'On scheduling and real-time capacity of hexagonal wireless sensor networks'. Together they form a unique fingerprint.

Cite this