Top

Published in:

01-08-2013

Broadcasting in multi-radio multi-channel wireless networks using simplicial complexes

Authors: Wei Ren, Qing Zhao, Ram Ramanathan, Jianhang Gao, Ananthram Swami, Amotz Bar-Noy, Matthew P. Johnson, Prithwish Basu

Published in: Wireless Networks | Issue 6/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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-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. 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.

previous article UVOC-MAC: a MAC protocol for outdoor ultraviolet networks

next article A new busy signal-based MAC protocol supporting QoS for ad-hoc networks with hidden nodes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

The ‘reception energy’ denotes the energy consumed by the radio in reception mode.

Strictly speaking, a subcomplex should also be closed under the subset operation, but without loss of generality, we do not include this condition in the definition of minimum connected spanning subcomplex, which is also more relevant to the broadcasting problem at hand.

Although there is no unified definition of tree in simplicial complexes, a couple of definitions can be obtained by generalizing those equivalent definitions of tree in a graph. For example, simplicial trees can be defined based on the universal existence of leaves in any subgraph, or the uniqueness of simplicial facet paths.

Notice that since A is its own nonempty subset, the simplex A is also a face of A.

\({({\mathcal{S}},w)}\) suffices to denote the WSC since \({V\subseteq {\mathcal{S}}}\), but we use the redundant \({(V,{\mathcal{S}},w)}\) for convenience.

We say that the weight function satisfies the monotone property if for any two faces \(S_1\subseteq S_2,\, w(S_1)\leq w(S_2)\), i.e., the weight is monotone non-decreasing with respect to the dimension of the face.

The approximation ratio of the greedy algorithm for general weighted MCSC problem is still an open problem.

A dominating set of a graph is a subset of vertices such that every vertex of the graph is either in the subset or a neighbor of some vertex in the subset, and a connected dominating set (CDS) is a dominating set where the subgraph induced by the vertices in the dominating set is connected. The CDS problem asks for a CDS with the minimum total weight, and it is shown to be a special case of the MCSC problem [21].

A random simplicial complex \(\Updelta (n,D,{\bf p})\) with n vertices, dimension at most D, and a D-dimensional probability vector \({\bf p}=\{p_1,p_2,\ldots,p_D\}\) is constructed in a bottom-up manner: first n vertices are fixed, which are the 0-simplices of \(\Updelta\), and then higher-dimensional simplices are generated inductively. Specifically, for each 1 ≤ i ≤ D, after all the simplices with dimension lower than i have been generated, consider every i-tuple of vertices: if they have formed all the lower dimensional simplices, then an i-simplex consisting of them is generated with probability p _i. Notice that a random simplicial complex \(\Updelta (n,1,p)\) is the random graph introduced by Erdős and Rényi [5].

Bazlamacci, C. F., & Hindi, K. S. (2001). Minimum-weight spanning tree algorithms: A survey and empirical study. Computers & Operations Research, 28(8), 767–785.MathSciNetMATHCrossRef

Čagalj, M., Hubaux, J., Enz, C. (2002). Minimum-energy broadcast in all-wireless networks: Np-completeness and distribution issues. In Proceedings of the ACM MobiCom, pp. 172–182.

Chiu, H. S., Wu, B., Yeung, K. L., & Lui, K. S. (2008). Widest spanning tree for multi-channel multi-interface wireless mesh networks. In Proceedings of the IEEE WCNC, pp. 2194–2199.

Chou, C. T., Misra, A., & Qadir, J. (2006). Low-latency broadcast in multirate wireless mesh networks. IEEE Journal on Selected Areas in Communications (JSAC), 24(11), 2081–2091.CrossRef

Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pp. 17–61.

Feige, U. (1998). A threshold of ln n for approximating set cover. Journal of the ACM, 45(4), 634–652.MathSciNetMATHCrossRef

Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374–387.MathSciNetMATHCrossRef

Guha, S., & Khuller, S. (1999). Improved methods for approximating node weighted steiner trees and connected dominating sets. Information and Computation, 150(1), 57–74.MathSciNetCrossRef

Klein, P. N. & Ravi, R. (1995). A nearly best-possible approximation algorithm for node-weighted steiner trees. Journal of Algorithms, 19(1), 104–115.MathSciNetMATHCrossRef

10.

Kleinberg, J. & Tardos, E. (2005). Algorithm design. Boston, MA: Addison Wesley.

11.

Kyasanur, P., & Vaidya, N. H. (2006). Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks. ACM SIGMOBILE Mobile Computing and Communications Review, 10(1), 31–43.CrossRef

12.

Kyasanur, P., So, J., Chereddi, C., Vaidya, N. H. (2006). Multichannel mesh networks: Challenges and protocols. IEEE Wireless Communications, 13(2), 30–36.CrossRef

13.

Li, L., Qin, B., Zhang, C., & Li, H. (2007). Efficient broadcasting in multi-radio multi-channel and multi-hop wireless networks based on self-pruning. In Proceedings of the HPCC, pp. 484–495.

14.

Liang, W. F. (2006). Approximate minimum-energy multicasting in wireless ad hoc networks. IEEE Transactions on Mobile Computing 5(4), 377–387.CrossRef

15.

Mannucci, M. A., Sparks, L., & Struppa, D. C. (2006). Simplicial models of social aggregation I. URL: http://arxiv.org/abs/cs/0604090.

16.

Munkres, J. R. (1984). Elements of algebraic topology. Menlo Park, CA: Addison-Wesley.MATH

17.

Nguyen, H. L., & Nguyen, U. T. (2009). Channel assignment for multicast in multi-channel multi-radio wireless mesh networks. Wireless Communications and Mobile Computing, 9(4), 557–571.CrossRef

18.

Ramanathan, R., Bar-Noy, A., Basu, P., Johnson, M., Ren, W., Swami, A., et al. (2011). Beyond graphs: Capturing groups in networks. In Proceedings of the IEEE NetSciCom.

19.

Raniwala, A., & Chiueh, T. (2005). Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In Proceedings of the IEEE INFOCOM, pp. 2223–2234.

20.

Redi, J., & Ramanathan, R. (2011). The DARPA WNaN network architecture. In Proceedings of the IEEE MILCOM, Baltimore.

21.

Ren, W., & Zhao, Q. (2011). A note on: ‘Algorithms for connected set cover problem and fault-tolerant connected set cover problem’. Theoretical Computer Science, 412(45), 6451–6454.MathSciNetMATHCrossRef

22.

Tang, J., Xue, G., & Zhang, W. (2005). Interference-aware topology control and QoS routing in multi-channel wireless mesh networks. In Proceedings of the ACM MobiHoc, pp. 68–77.

23.

Wieselthier, J. E., Nguyen, G. D., & Ephremides, A. (2002). Energy-efficient broadcast and multicast trees in wireless networks. Mobile Networks and Applications, 7(6), 481–492.MathSciNetCrossRef

24.

Zhang, Z., Gao, X. F., & Wu, W. L. (2009). Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theoretical Computer Science, 410(8–10), 812–817.MathSciNetMATHCrossRef

Title: Broadcasting in multi-radio multi-channel wireless networks using simplicial complexes
Authors: Wei Ren
Qing Zhao
Ram Ramanathan
Jianhang Gao
Ananthram Swami
Amotz Bar-Noy
Matthew P. Johnson
Prithwish Basu
Publication date: 01-08-2013
Publisher: Springer US
Published in: Wireless Networks / Issue 6/2013
Print ISSN: 1022-0038
Electronic ISSN: 1572-8196
DOI: https://doi.org/10.1007/s11276-012-0522-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2013

Energy-balanced cooperative routing in multihop wireless networks

Band-based geocasting for mobile sink groups in wireless sensor networks

Downlink user selection and resource allocation for semi-elastic flows in an OFDM cell

Cognitive radio resource management exploiting heterogeneous primary users and a radio environment map database

UVOC-MAC: a MAC protocol for outdoor ultraviolet networks

Reinforcement learning for cooperative sensing gain in cognitive radio ad hoc networks