Ternary Schedules for Energy-Limited Sensor Networks
Peter J. Dukes, Violet R. Syrotiuk, Charles J. Colbourn · IEEE Transactions on Information Theory · 2007
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 viis transmitting, vjis receiving, and no other node in proximity of vjis 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 lambda-fold directed graph Koarrninto directed complete bipartite subgraphs Koarra,bas a model for ternary scheduling in WSNs. We associate the vertices of Koarrnwith the nodes of the WSN, and occurrences of Koarra,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 lambdaKoarrnguarantees that every ordered pair of nodes in the WSN can communicate in lambda time slots.