Efficient data dissemination in Dense Multi-channel Wireless Mesh Networks - 11/05/2010

Kan Lin

Abstract: New broadcasting protocols supported by emerging standards will enable providers to scale up the number of concurrently connected devices in wireless mesh networks by several orders of magnitude. However, the large client audience and the lossy nature of the wireless channels significantly complicate the task of implementing effective reliable broadcasting protocols. We consider the problem of achieving data dissemination (broadcasting) with minimum delay in lossy, multi-channel wireless mesh networks using rateless coding or plaintext. Our analysis shows that this problem can be greatly simplified as the density of clients gets large since transmission demand (i.e., the number of transmissions required) grows almost deterministically in this regime. This allows us to devise asymptotically optimal transmission policies using linear programming formulations. We find that both transmission modes are subject to a sub-linear performance gain with increasing number of channels that is related to the difference between the chromatic number and the fractional chromatic number of the underlying graph modeling the network. Overall, our analysis can be used as an engineering tool for designing and deploying dense WMNs with a data dissemination orientation.

-- JiaxiJin - 18 Nov 2010