An optimal model to partition the evolution of periodic tasks in wireless sensor networks

Our research targets an operating paradigm that can be referred to as WSN cloud infrastructure, in which a WSN provider maintains the sensor network over a certain area and allows potential clients to deploy their applications to monitor some parameters of interest. Applications coming from multiple heterogeneous sources may have very inhomogeneous periods and tolerable slacks, inducing a fragmented and inefficient duty cycle on the nodes, strongly accelerating the energy depletion process. In such a paradigm, a way to merge as much as possible the execution moments of the periodic tasks is mandatory, in order to reduce the energy overheads of frequent awakenings of system and devices. The partitioning method presented in this paper subdivides the evolution of the periodic tasks in small self-contained optimization sub-problems, which can be subsequently processed at run-time through a task-merging or a scheduling policy. The model and the related algorithm have been conceived such that the formal guarantees of global optimality are satisfied in the general case of a coverage problem, aimed at finding the sequence of system awakenings that fulfill the deadlines of each periodic task in the system. Moreover, the generality of the model makes it suitable for a variety of task-merging policies and algorithms. Experimental results demonstrate the high computational efficiency of the proposed partitioning approach.