Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Wireless Networks
Erschienen in: Wireless Networks 5/2014

01.07.2014

Bluetooth scatternet formation from a time-efficiency perspective

verfasst von: Ahmed Jedda, Arnaud Casteigts, Guy-Vincent Jourdan, Hussein T. Mouftah

Erschienen in: Wireless Networks | Ausgabe 5/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The Bluetooth Scatternet Formation (BSF) problem consists of interconnecting piconets in order to form a multi-hop topology. While a large number of BSF algorithms have been proposed, only few address time as a key parameter, and when doing so, virtually none of the solutions were tested under realistic settings. In particular, the baseband and link layers of Bluetooth are highly specific and known to have crucial impacts on performance. In this paper, we revisit performance studies for a number of time-efficient BSF algorithms, focusing on BlueStars, BlueMesh, and BlueMIS. We also introduce a novel time-efficient BSF algorithm called BSF-UED (for BSF based on Unnecessary-Edges Deletion), which forms connected scatternets deterministically and limits the outdegree of nodes to 7 heuristically. The performance of the algorithm is evaluated through detailed simulation experiments that take into account the low-level specificities of Bluetooth. We show that BSF-UED compares favorably against BlueMesh while requiring only 1/3 of its execution time. Only BlueStars is faster than BSF-UED, but at the cost of a very large number of slaves per master (much more than 7), which makes it impractical in many scenarios.
Vorheriger Artikel Joint delay and energy model for IEEE 802.11 networks
Nächster Artikel Cooperative network solution and implementation for emergency applications with enhanced position estimation capability

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
2
In the following, a piconet is modeled as a star graph with a master and slaves. We model a master-slave relationship as a directed edge from the master to slave, hence the number of slaves of a master is its outdegree.
 
3
Bluehoc: http://​bluehoc.​sourceforge.​net/​. Fetched on Dec. 20, 2012
 
4
Given two functions f, g, we say that g is in O(f) if there is a constant c > 0 such that \(g(n) < c\cdot f(n)\) for a sufficiently large n.
 
5
An independent set of a network (or a graph) is a set of nodes that none of which is neighbor to another. A maximal independent set is an independent set that is not a subset of any other independent set.
 
6
In this rule, the fact that v captures u (and not the opposite) is important; it follows the anticipated decrease of \(\varphi(v)\) in Phase 1 when the edge (u, v) was colored red. In a sense, v is “more prepared” than u to handle new slaves. The impact of this operation is seen while starting the elimination algorithm from smaller to larger piconets.
 
7
This case may occur if u delegated to a neighbor w the responsibility of v, and hence (u, v) is red. Also, there is a node a \(w^{\prime}\) that is larger than v and delegated to v the responsibility of slaving common neighbors between v and \(w^{\prime}\).
 
8
We thank the anonymous reviewer for directing our attention to this important issue in the field of Bluetooth Scatternet Formation algorithms
 
Literatur
1.
Nokia. 5 surprising facts about Bluetooth, May (2011).
2.
Bluetooth SIG. Bluetooth specifications ver 4.0, (2010).
3.
Petrioli, C., Basagni, S., & Chlamtac, I. (2003). Configuring BlueStars: Multihop scatternet formation for Bluetooth networks. IEEE Transactions on Computers, 52, 779–790.CrossRef
4.
Li, X. Y., Stojmenovic, I., & Wang, Y. (2004). Partial delaunay triangulation and degree limited localized Bluetooth scatternet formation. IEEE Transactions on Parallel and Distributed Systems, 15(4), 350–361.CrossRef
5.
Wang, Z., Thomas, R. K., & Haas, J. (2009). Performance comparison of Bluetooth scatternet formation protocols for multi-hop networks. Wireless Networks, 15(2), 209–226.CrossRef
6.
Petrioli, C., Basagni, S., & Chlamtac, I. (2004). BlueMesh: Degree-constrained multi-hop scatternet formation for Bluetooth networks. Mobile Networks and Applications, 9(1), 33–47.CrossRef
7.
Zaguia, N., Daadaa, Y., & Stojmenovic, I. (2008). Simplified Bluetooth scatternet formation using maximal independent sets. Integrated Computer-Aided Engineering, 15(3), 229–239. ISSN 1069-2509.
8.
Howell, F., & McNab, R. (1998). SimJava: A discrete event simulation library for java. Simulation Series, 30, 51–56.
9.
Jedda, A., Jourdan, G. V., & Mouftah, H. T. (July 2012). Time-efficient algorithms for the outdegree limited Bluetooth scatternet formation problem. In Proceedings of the IEEE symposium on computers and communications (ISCC) 2012, pp. 000132–000138. doi:10.​1109/​ISCC.​2012.​6249281.
10.
Jedda, A., Jourdan, G. V., & Zaguia, N. (2012). Towards better understanding of the behaviour of Bluetooth networks distributed algorithms. International Journal of Parallel, Emergent and Distributed Systems, 27(6), 563–586.CrossRef
11.
Stojmenovic, I., & Zaguia, N. (2006). Bluetooth scatternet formation in ad-hoc wireless networks. In: J. Misic, V. Misic (Eds.), Chapter 9 in: Performance modeling and analysis of Bluetooth networks: Network formation, polling, sceduling, and traffic control (pp. 147–171).
12.
13.
Vergetis, E., Guérin, R., Sarkar, S., & Rank, J. (2005). Can Bluetooth succeed as a large-scale ad hoc networking technology? IEEE Journal on Selected Areas in Communication, 23(3), 644–656.CrossRef
14.
Basagni, S., Bruno, R., Mambrini, G., & Petrioli, C. (2004). Comparative performance evaluation of scatternet formation protocols for networks of Bluetooth devices. Wireless Networks, 10(2), 197–213. ISSN 1022-0038. doi:10.​1023/​B:​WINE.​0000013083.​41155.​fa.
15.
Song, W. Z., Wang, Y., Ren, C., & Wu, C. (2009). Multi-hop scatternet formation and routing for large scale Bluetooth networks. International Journal of Ad Hoc and Ubiquitous Computing, 4(5), 251–268.CrossRef
16.
Salonidis, T., Bhagwat, P., Tassiulas, L., & LaMaire, R. (2001). Distributed topology construction of Bluetooth personal area network. In IEEE INFOCOM 2001.
17.
Sreenivas, H., & Ali, H. (2004). An evolutionary Bluetooth scatternet formation protocol. In System sciences. (2004). Proceedings of the 37th annual hawaii international conference on, p. 8–pp. IEEE.
18.
Hodge, L. E., Whitaker, R. M., & Hurley, S. (2006). Multiple objective optimization of Bluetooth scatternets. Journal of Combinatorial Optimization, 11(1), 43–57.CrossRefMATHMathSciNet
19.
Marsan, M. A., Chiasserini, C. F., Nucci, A., Carello, G., & De Giovanni, L. (2002). Optimizing the topology of Bluetooth wireless personal area networks. In INFOCOM 2002. Twenty-first annual joint conference of the IEEE computer and communications societies. Proceedings. IEEE, vol. 2, pp. 572–579. IEEE.
20.
Huang, L., Chen, H., Sivakumar, T., Kashima, T., & Sezaki, K. (2005). Impact of topology on Bluetooth scatternet. International Journal of Pervasive Computing and Communications, 1(2), 123–134.CrossRef
21.
Kiss Kalló, C., Chiasserini, C. F., Jung, S., Brunato, M., & Gerla, M. (2007). Hop count based optimization of Bluetooth scatternets. Ad Hoc Networks, 5(3), 340–359.CrossRef
22.
Daptardar, A. (2004). Meshes and cubes: Distributed scatternet formations for Bluetooth personal area networks.
23.
Song, W. Z., Li, X. Y., Wang, Y., & Wang, W. Z. (2005). dBBlue: Low diameter and self-routing Bluetooth scatternet. Journal of Parallel and Distributed Computing, 65(2), 2.CrossRef
24.
Zhang, H., Hou, J. C., & Sha, L. (2003). A Bluetooth loop scatternet formation algorithm. In Communications. (2003). ICC’03. IEEE International Conference on, vol. 2, pp. 1174–1180. IEEE.
25.
Wang, Y., Stojmenovic, I., & Li, X.-Y. (2004). Bluetooth scatternet formation for single-hop ad hoc networks based on virtual positions. In Computers and Communications. (2004). Proceedings. ISCC 2004. Ninth International Symposium on, vol. 1, pp. 170–175. IEEE.
26.
Barrière, L., Fraigniaud, P., Narayanan, L., & Opatrny, J. (2003). Dynamic construction of Bluetooth scatternets of fixed degree and low diameter. In Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms (pp. 781–790). Society for Industrial and Applied Mathematics.
27.
Yu, C. M., & Lin, J. H. (2012). Enhanced Bluetree: A mesh topology approach forming Bluetooth scatternet. IET Wireless Sensor Systems, 2(4), 409–415.CrossRef
28.
Cuomo, F., Melodia, T., & Akyildiz, I. F. (2004). Distributed self-healing and variable optimization algoritms for QoS provisioning in scatternets. IEEE Journal on Selected Areas in Communication, 22(7), 1220–1236.CrossRef
29.
Law, C., Mehta, A. K., & Siu, K. (2003). A new Bluetooth scatternet formation protocol. Mobile Networks and Applications, 8(5), 485–498.CrossRef
30.
Gallager, R. G., Humblet, P. A., & Spira, P. M. (1983). A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5(1), 66–77.CrossRefMATH
31.
Tan, G., Miu, A., Guttag, J., & Balakrishnan, H. (2002). An efficient scatternet formation algorithm for dynamic environments. In Proceedings of the IASTED communications and computer networks (CCN), pp. 4–6.
32.
Huang, T. C., Yang, C. S., Huang, C. C., & Bai, S. W. (2006). Hierarchical Grown Bluetrees (HGB): An effective topology for Bluetooth scatternets. International Journal of Computational Science and Engineering, 2(1), 23–31.
33.
Zaruba, G., Basagni, S., & Chlamtac, I. BlueTrees-Scatternet formation to enable Bluetooth-based personal area networks. In Proceedings of the IEEE international conference on communications, vol. 1, pp. 273–277, 6 (2001).
34.
Dong, Y., & Wu, J. (2003). Three bluetree formations for constructing efficient scatternets in Bluetooth. In Proceedings of the 7th joint conference on information sciences, pp. 385–388.
35.
Pagani, E., Rossi, G., & Tebaldi, S. (2004). An on-demand Bluetooth scatternet formation algorithm. Wireless On-Demand Network Systems, pp. 51–61.
36.
Methfessel, M., Peter, S., & Lange, S. (2011). Bluetooth scatternet tree formation for wireless sensor networks. In Mobile adhoc and sensor systems (MASS), 2011 IEEE 8th international conference on, pp. 789–794. IEEE.
37.
Dubhashi, D., Häggström, O., Mambrini, G., Panconesi, A., & Petrioli, C. (2007). Blue pleiades, a new solution for device discovery and scatternet formation in multi-hop Bluetooth networks. Wireless Networks, 13, 107–125, January 2007. ISSN 1022-0038.
38.
Wattenhofer, R., & Zollinger, A. (2004). XTC: A practical topology control algorithm for ad-hoc networks. In Parallel and distributed processing symposium, (2004). Proceedings. 18th international, p. 216, April 2004.
39.
Wang, Q. (2006). Scheduling and simulation of large scale wireless personal area networks. PhD thesis, University of Cincinnati, Cincinnati, USA.
40.
Metadaten
Titel
Bluetooth scatternet formation from a time-efficiency perspective
verfasst von
Ahmed Jedda
Arnaud Casteigts
Guy-Vincent Jourdan
Hussein T. Mouftah
Publikationsdatum
01.07.2014
Verlag
Springer US
Erschienen in
Wireless Networks / Ausgabe 5/2014
Print ISSN: 1022-0038
Elektronische ISSN: 1572-8196
DOI
https://doi.org/10.1007/s11276-013-0664-z

Weitere Artikel der Ausgabe 5/2014

Wireless Networks 5/2014 Zur Ausgabe

OriginalPaper

Opportunistic routing with in-network aggregation for asynchronous duty-cycled wireless sensor networks

OriginalPaper

Power saving mechanism for VoIP services over WiMAX systems

OriginalPaper

Joint delay and energy model for IEEE 802.11 networks

OriginalPaper

Vertical handoff decision in 4G wireless networks using multi attribute decision making approach

OriginalPaper

Stochastic spectrum handoff protocols for partially observable cognitive radio networks

OriginalPaper

Cooperative network solution and implementation for emergency applications with enhanced position estimation capability

Neuer Inhalt

    Bildnachweise