Simple and efficient protocols for guaranteed message delivery in wireless ad-hoc networks

The paper presents several new protocol classes for mobile wireless ad-hoc networks that rely on specific mobility patterns of router nodes in order to guarantee tight upper bounds on communication delays. We introduce a generic formal model of a heterogeneous network in which regular nodes exchange messages through a subnetwork of dedicated router nodes, and use it to identify desirable properties of router mobility patterns. In particular, the analysis focusses on protocols that periodically cover (´sweep´) the entire communication zone. We define specific classes of sweep protocols and prove the upper bounds on router contact delays and on end-to-end message delivery times that they guarantee to stationary or mobile populations of regular nodes. The results of simulation experiments show that a translatory chain sweep protocol outperforms the runners protocol with respect to end-to-end message delivery times for both stationary and mobile regular nodes.