Ternary schedules for energy-limited sensor networks

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop (vi, vj), communication is effective only when vi is transmitting, vj is receiving, and no other node in proximity of vj is also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use arc-decompositions of the complete λ-fold directed graph Kn into directed complete bipartite subgraphs Ka,b as a model for ternary scheduling in WSNs. We associate the vertices of Kn with the nodes of the WSN, and occurrences of Ka,bs (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of λ Kn guarantees that every ordered pair of nodes in the WSN can communicate in λ time slots.

Original languageEnglish (US)
Pages (from-to)2791-2798
Number of pages8
JournalIEEE Transactions on Information Theory
Issue number8
StatePublished - Aug 2007


  • Direct combinatorial constructions
  • Ternary schedules
  • Wireless sensor networks

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Ternary schedules for energy-limited sensor networks'. Together they form a unique fingerprint.

Cite this