Broadcasting in Multi-Radio Multi-Channel Wireless Networks using Simplicial Complexes
Abstract
We consider the broadcasting problem in multiradio 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 2011
- Accession Number
- ADA554748
Entities
People
- A. Bar-noy
- A. Swami
- Jian Gao
- M. Johnson
- P. Basu
- Qi Zhao
- R. Ramanathan
- W. Ren
Organizations
- University of California