Broadcasting in multi-radio multi-channel wireless networks using simplicial complexes
- PDF / 1,106,938 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 103 Downloads / 223 Views
Broadcasting in multi-radio multi-channel wireless networks using simplicial complexes Wei Ren • Qing Zhao • Ram Ramanathan • Jianhang Gao • Ananthram Swami • Amotz Bar-Noy Matthew P. Johnson • Prithwish Basu
•
Published online: 27 November 2012 Ó Springer Science+Business Media New York 2012
Abstract We consider the broadcasting problem in multiradio 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 multiradio 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 Part of this work was presented at IEEE MASS 2011. W. Ren (&) Microsoft Corporation, Redmond, WA, USA e-mail: [email protected] Q. Zhao J. Gao Department of Electrical and Computer Engineering, University of California, Davis, CA, USA e-mail: [email protected] R. Ramanathan P. Basu Raytheon BBN Technologies, Cambridge, MA, USA A. Swami Army Research Laboratory, Adelphi, MD, USA A. Bar-Noy Department of Computer Science, City University of New York, New York City, NY, USA M. P. Johnson Department of Computer Science and Engineering, Pennsylvania State University, Philadelphia, PA, USA
order-optimal performance guarantee. The first approximation algorithm converts the minimum spanning problem in simplical complexes to a minimum connected set cover (MCSC) problem. The second algorithm converts it to a node-weighted Steiner tree problem under the classic graph model. 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 MCSC problem. Keywords Broadcast Multi-radio multi-channel Ad hoc network Simplicial complex Minimum spanning Minimum connected set cover
1 Introduction Multi-radio multi-channel (MR-MC) wireless networking arises in the context of wireless mesh networks, dynamic spectrum access via cognitive radio, and next-generation cellular networks [12]. By the use of multiple channels, spatially adjacent transmissions can be carried over nonoverlapping channels to avoid mutual interference. Furthermore, each node, equipped with multiple radios, is capable of working in a full-duplex mode by tuning the transmitting and receiving radios to two non-overlapping channels. The increasing demand for high data rate and the persistent reduction in radio costs have greatly stimulated research on MR-MC networks. Considerable work has been done on capacity analysis, channel and radio assignment
Data Loading...
