TY - JOUR
T1 - Almost optimal distributed M2M multicasting in wireless mesh networks
AU - Xin, Qin
AU - Manne, Fredrik
AU - Zhang, Yan
AU - Wang, Xin
PY - 2012
Y1 - 2012
N2 - Wireless Mesh Networking (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 isNP-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(dlog2n+klog 3nlogk) with a polynomial-time computation, which is an almost optimal scheme due to the lower bound Ω(d+klognlogk) given by Chlebus et al. (2009) [5]. Our algorithm also improves the currently best known result with running time O(dlog2n+klog4n) by Gasieniec et al. (2006) [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 Ω(d+k) units of time.
AB - Wireless Mesh Networking (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 isNP-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(dlog2n+klog 3nlogk) with a polynomial-time computation, which is an almost optimal scheme due to the lower bound Ω(d+klognlogk) given by Chlebus et al. (2009) [5]. Our algorithm also improves the currently best known result with running time O(dlog2n+klog4n) by Gasieniec et al. (2006) [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 Ω(d+k) units of time.
KW - Broadcasting
KW - Distributed algorithms
KW - Gossiping
KW - Multicast
KW - Unit disk graphs
KW - Wireless mesh networks
UR - http://www.scopus.com/inward/record.url?scp=84861231635&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.03.015
DO - 10.1016/j.tcs.2012.03.015
M3 - Journal article
AN - SCOPUS:84861231635
SN - 0304-3975
VL - 439
SP - 69
EP - 82
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -