Ternary schedules for energy-limited sensor networks

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 (v_i, v_j), communication is effective only when v_i is transmitting, v_j is receiving, and no other node in proximity of v_j 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 K^→_n into directed complete bipartite subgraphs K^→_a,b as a model for ternary scheduling in WSNs. We associate the vertices of K^→_n with the nodes of the WSN, and occurrences of K^→_a,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 λ K^→_n guarantees that every ordered pair of nodes in the WSN can communicate in λ time slots.