Almost optimal distributed M2M multicasting in Wireless Mesh Networks

Wireless Mesh Network (WMN) is an emerging communication paradigm to enable resilient, cost-efficient and reliable services for the future-generation wireless networks. In this paper, we study the problem of multipoint-to-multipoint (M2M) multicasting in a WMN which aims to use the minimum number of time slots to exchange messages among a group of k mesh nodes in a multi-hop WMN with n mesh nodes. We study the M2M multicasting problem in a distributed environment where each participant only knows that there are k participants and it does not know who are other k -1 participants among n mesh nodes. It is known that the computation of an optimal M2M multicasting schedule is NP-hard. We present a fully distributed deterministic algorithm for such an M2M multicasting problem and analyze its time complexity. We show that if the maximum hop distance between any two out of the k participants is d, then the studied M2M multicasting problem can be solved in time O(d log² n+k log³ n/log k) with a polynomial-time computation, which is an almost optimal scheme due to the lower bound Omega(d+ k log n/log k) given in [5]. Our algorithm also improves the currently best known result with running time O(d log² n + k log⁴ n) in [13]. In this paper, we also propose a distributed deterministic algorithm which accomplishes the M2M multicasting in time O(d+k) with a polynomial-time computation in unit disk graphs. This is an asymptotically optimal algorithm in the sense that there exists a WMN topology, e.g., a line, a ring, a star or a complete graph, in which the M2M multicasting cannot be completed in less than Omega(d+k) units of time.