A fast CPU conserving algorithm for optimal broadcast scheduling in networks of pervasive devices

The search for optimal broadcast scheduling scheme (S_optimal), in a hybrid unicast-broadcast system with users of realistic-impatient behavioral patterns, is shown to be a rather complex, nonlinear inequality-constrained optimization problem. By exploiting some mathematical properties of the main cost function, we prove that the given optimization problem can be considerably simplified. Based on this simplification, first we derive a closed form approximate expression for S_optimal and, consequently, we propose an algorithm for fast CPU conserving estimation of S_optimal. Experimental results verify that the proposed algorithm requires minimum computation, while providing performance almost identical to S_optimal obtained through numerical estimation. The given algorithm is shown to have a direct applicability in the area of pervasive computing, one example being Service Discovery Service (SDS) or node discovery in ad hoc networks.