A generalized quorum system for asynchronous sleep scheduling in multi-hop wireless networks

It has been shown that quorum systems with rotation closure property can be utilized to enable asynchronous power saving in wireless ad-hoc networks. Moreover, the quorum system characteristics (e.g., cycle length, activity ratio, overlap size) can be exploited to provide for a variety of sleep-scheduling paradigms which differ in terms of their adaptability and symmetry properties. To enable these paradigms, generally requires that the quorum schedules available to the nodes be heterogeneous so that they may pick their schedules in accordance with their roles or instantaneous conditions. Motivated by this heterogeneity requirement, in this paper, we generalize the basic notion of a quorum system into what we refer to as a Multi-Class Quorum System (MCQS). MCQS consists of a set of quorum classes, each of which is basically a quorum system with a guaranteed intra-class overlap size. Also, every two quorum classes have a guaranteed inter-class overlap size. We extend the classical rotation closure property of the quorum systems to guarantee any desirable number of intra- and inter-class overlaps between asynchronous nodes. We show that MCQS gives rise to a unified framework for quorum-based scheduling which can be easily tailored to enable all types of sleep-scheduling paradigms. We propose a binary integer programming (BIP) model to compute instances of MCQS which are optimal in terms of activity ratio. Also, unlike comparable quorum systems in the literature, MCQS is relieved of many restrictions on cycle length and overlap size. As a proof of concept, we study the application of MCQS in the joint problem of Quorum-based Sleep-scheduling and Routing (QSR) in wireless sensor networks (WSNs). We propose a centralized energy-optimal formulation as well as a decentralized algorithm for the QSR problem, and compare their performance through simulations.