Quadratic Programming for TDMA Scheduling in Wireless Sensor Networks

Abstract

This paper presents a novel Multihop Aperiodic Scheduling (MAS) algorithm which guarantees energy-efficient data collection by Wireless Sensor Networks (WSNs) under delay constraints. Present Medium Access Control (MAC) protocols in WSNs typically sacrifice packet latency and/or the reliability of packet transfer to achieve energy-efficiency. Thus, the paper is concerned with developing a novel protocol to achieve energy efficient and reliable multihop data transfer in WSNs satisfying given latency requirements. Energy efficiency is achieved by optimizing the scheduling of the underlying Time Division Multiple Access (TDMA) system by minimizing the wake-up number of the nodes. Schedule optimization is transformed into a quadratic programming (QP) task, which is then solved by the Hopfield net in polynomial time. In this way, an energy efficient scheduling can be obtained which meets a given delay requirement in TDMA systems. The performance of the new algorithm has been evaluated by simulations and compared to the performance of well-known scheduling methods, such as SMAC, UxDMA (a slot assignment algorithm for WSN), and traditional tree-based protocols. The simulations have demonstrated that our method reduces global power consumption for time-driven monitoring.