Understanding multi-task schedulabilityin duty-cycling sensor networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

4 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number6471978
Pages (from-to)2463-2474
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume25
Issue number9
Publication statusPublished - Sep 2014
Externally publishedYes

Abstract

In many sensor network applications, multiple data forwarding tasks usually exist with different source-destination node pairs. Due to limitations of the duty-cycling operation and interference, however, not all tasks can be guaranteed to be scheduled within their required delay constraints. We investigate a fundamental scheduling problem of both theoretical and practical importance, called multi-task schedulability problem, i.e., given multiple data forwarding tasks, to determine the maximum number of tasks that can be scheduled within their deadlines and work out such a schedule. We formulate the multi-task schedulability problem, prove its NP-Hardness, and propose an approximate algorithm with analysis on the performance bound and complicity. We further extend the proposed algorithm by explicitly altering duty cycles of certain sensor nodes so as to fully support applications with stringent delay requirements to accomplish all tasks. We then design a practical scheduling protocol based on proposed algorithms. We conduct extensive trace-driven simulations to validate the effectiveness and efficiency of our approach with various settings. © 2013 IEEE.

Research Area(s)

  • data forwarding, duty-cycling, schedulability, Wireless sensor networks

Citation Format(s)

Understanding multi-task schedulabilityin duty-cycling sensor networks. / Li, Mo; Li, Zhenjiang; Shangguan, Longfei; Tang, Shaojie; Li, Xiang-Yang.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 25, No. 9, 6471978, 09.2014, p. 2463-2474.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review