Expected quorum overlap sizes of quorum systems for asynchronous power-saving in mobile ad hoc networks

Quorum systems satisfying the rotation closure property can be used to realize asynchronous power-saving algorithms for mobile ad hoc networks. The FPP, grid, cyclic, torus and e-torus quorum systems can provide the algorithms with the lowest or near lowest active ratios since they have the optimal or near optimal quorum sizes. The algorithms guarantee that a node can sense the status of every neighbor by receiving one or more beacons from it within a round of beacon intervals. Traditionally, the smallest quorum overlap size (SQOS) and the maximum quorum overlap separation (MQOS) are used to measure the neighbor sensibility. However, it is difficult to differentiate the quorum systems by SQOS and MQOS since most of them have the same SQOS and MQOS values. In this paper, the expected quorum overlap size (EQOS) is proposed as an average-case neighbor sensibility measurement. We can easily judge the goodness of quorum systems by EQOS since they have different EQOS values. Larger than one EQOS values are desirable. Observing quorum systems are of EQOS values far larger than one, we are inspired to devise a new quorum system, called the fraction torus (f-torus) quorum system, for the construction of flexible mobility-adaptive power-saving algorithms. The f-torus quorum system can further reduce the active ratio to save energy by shrinking the quorum size, while still keeping the EQOS larger than one. We derive EQOS values for all the above-mentioned quorum systems by analysis and simulation experiments. As we will show, the EQOS analysis and simulation results coincide very closely. (C) 2008 Elsevier B.V. All rights reserved.