Broadcasting in Multi-Radio Multi-Channel Wireless Networks using Simplicial Complexes
Wei Zhong Ren, Qing Zhao, Ram Ramanathan, Jianhang Gao, Ananthram Swami, Amotz Bar-Noy, Matthew P. Johnson, Prithwish Basu · 2011
We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total broadcast cost, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. These two algorithms offer tradeoffs between performance and time complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem.