Mobility-based multicast routing algorithm for wireless mobile Ad-hoc networks: A learning automata approach

During the last decades, many studies have been conducted on multicast routing in mobile ad hoc networks (MANET) and a host of algorithms have been proposed. In existing algorithms, the mobility characteristics are assumed to be constant, and so they do not scale well when the mobility parameters are not deterministic. To the best of our knowledge no work has been done on multicast routing when the mobility parameters are stochastic, while in realistic applications these parameters vary with time. In this paper, we propose a mobility-based multicast routing algorithm for wireless MANETs wherein the mobility characteristics are stochastic and unknown. The proposed algorithm estimates the expected relative mobility of each host, by sampling its movement parameters in various epochs, to realistically predict its motion behavior, and takes advantage of the Steiner connected dominating set to form the virtual multicast backbone. To do this, in this paper, a stochastic version of the minimum Steiner connected dominating set problem in weighted network graphs, where the relative mobility of each host is considered as its weight is initially introduced. Then, a distributed learning automata-based algorithm is designed to solve this problem. The designed algorithm is proposed for multicast routing in wireless mobile Ad-hoc networks. The experiments show the superiority of the proposed multicast routing algorithm over the existing methods in terms of the packet delivery ratio, multicast route lifetime, and end-to-end delay. We present a strong convergence theorem in which the convergence of the proposed distributed learning automata-based algorithm to the optimal solution is proved. It is shown that the most stable multicast route is found with a probability as close as to unity by the proper choice of the parameters of the distributed learning automata.