Broadcasting in Multi-Radio Multi-Channel Wireless Networks using Simplicial Complexes
Abstract
We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total cost of the network-wide broadcast 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-radiomulti-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. The first approximation algorithm converts the minimum spanning problem in simplical complexes to a minimum connected set cover problem. The second algorithm converts it to a node-weighted Steiner tree problem under the classic graph model.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 2012
- Accession Number
- ADA563940
Entities
People
- Amotz Bar-noy
- Ananthram Swami
- Jianhang Gao
- Matthew P. Johnson
- Prithwish Basu
- Qing Zhao
- Ram Ramanathan
- Wei Ren
Organizations
- United States Army Research Laboratory