|
Author(s):
|
Qin Xin, Simula Research Laboratory, Norway ; Fredrik Manne, University of Bergen, Norway; Yan Zhang, Simula Research Laboratory, Norway; Jianping Wang, City University of Hong Kong, Hong Kong; Zeyu Zheng, Cityu University of Hong Kong, Hong Kong
|
|
Abstract:
|
Wireless Mesh Networks (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 network with $n$ 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$ wireless mesh nodes. It is known that the computation of an optimal M2M multicasting schedule is {\bf\sl 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 distance between any two out of the $k$ participants is $d$, then the studied M2M problem can be solved in time $O(d\log^2 n+\frac{k\log^3 n}{\log k})$, which is an almost optimal scheme due to the lower bound $\Omega(d+\frac{k\log n}{\log k})$ given by Chlebus, Kowalski, and Radzik in [Algorithmica: 2008, to appear]. Our algorithm also improves the currently best known result with running time $O(d\log^2 n+ k\log^4 n)$ by G\k{a}sieniec, Kranakis, Pelc, and Xin in [Theor. Comput. Sci. 362(1-3): 196-206 (2006)]. In this paper, we also propose a distributed deterministic algorithm which accomplishes the M2M multicast in time $O(d + k)$ in the unit disk graphs. This is an optimal algorithm in the sense that there exists a WMN topology, e.g., a line, a ring, a star and a complete graph, in which the M2M multicast cannot complete in less than $\Omega(d+k)$ units of time.
|
