Uniform and regular reliable broadcast protocols facilitating concurrent message dissemination for mobile ad hoc networks with the network liveness property. (March 2022) - Kalewski, Michał; Brzeziński, Jerzy
Abstract: A mobile ad hoc network is an infrastructure-less network composed of autonomous and mobile hosts, which communicate only through wireless links. One of the fundamental communication operations in these networks is broadcast—a process of sending a message from one host to all hosts in the network. However, it is important for any broadcast protocol to provide some deterministic delivery guarantees, all the more so, if we make allowances for host failures. For mobile ad hoc networks, it is possible to provide such deterministic guarantees under the assumption of the network liveness property, which, informally, ensures that no host is permanently isolated. Therefore, in this paper, we propose uniform and regular reliable broadcast protocols, and discuss the implementation of best-effort reliable broadcast, for mobile ad hoc networks with the network liveness property. The proposed protocols facilitate concurrent message dissemination, but their time requirements are independent of the total number of messages that each node can start disseminate concurrently, and hence, of the total number of messages that can be disseminated concurrently in an ad hoc network by all nodes. For the proposed protocols, we prove analytically their correctness, and evaluate experimentally their efficiency in simulation tests. The obtained results show that the concurrent dissemination parameters of the proposed uniform and regular reliable broadcast protocols may be adjusted in actual ad hoc networks to improve broadcast efficiency.