Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimisation Methods for Bluetooth ScatternetFormation
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Optimeringsmetoder för bluetooth scatternet formation (Swedish)
Abstract [en]

The Bluetooth scattnernet formation problem is to find a network on a graph under constraints inspired by the limitations of Bluetooth technology. The problem is presented along with a summary of the current state of research. A method of finding solution is proposed that takes the problem and splits it into three parts where every part is solved using a distributed algorithm. The approach uses methods from network optimisation to first find a maximal independent subset that makes up the masters of the network, then an assignment of slaves to masters using an auction algorithm and finally a minimal spanning tree that connects the clusters around the masters together. It's shown that a solution can't always be found and it is investigated how often the algorithm finds a solution. The method is then compared to a brute force solution to asses how close to the best possible network the algorithm comes. It was found that for smaller graphs the algorithm lands not far from the best solution. Informal arguments are made regarding optimality and complexity of the method and suggestions for further research are made.

Abstract [sv]

Bluetooth scatternet formations-problemet är att hitta ett nätverk på en graf givet vissa bivillkor inspirerade av begränsningarna i Bluetoothteknologin. Problemet presenteras tillsammans med en sammanfattning av nuläget i forskningen kring Bluetoothnätverk. En metod för att hitta lösningar till problemet föreslås som tar problemet och delar upp det i tre delar där varje del löses med en distribuerad algoritm. Tillvägagångssättet använder metoder från nätverksoptimering för att först hitta et maximals oberoende delmängd av nätverket som utgör mästarnoderna, sedan görs en tilldelning av slavar till mästare genom en auktionsalgoritm och till sist tas ett minimalt uppspännande träd fram som kopplar ihop alla kluster kring mästarna. Det visar sig att en lösning inte alltid finns och det undersöks hur ofta algoritmen hittar en lösning. Metoden jämförs sedan med en metod som använder Brute Force för att bedöma hur nära den bästa lösningen metoden lyckas komma. Det visas att för små grafer lyckas algoritmen komma nära det bästa nätverket. Informella argument görs gällande optimalitet och komplexitet och förlag för vidare studier ges.

Place, publisher, year, edition, pages
2017.
Series
TRITA-MAT-E ; 2017:65
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-215108OAI: oai:DiVA.org:kth-215108DiVA, id: diva2:1146339
Subject / course
Optimization and Systems Theory
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
Available from: 2017-10-02 Created: 2017-10-02 Last updated: 2017-10-02Bibliographically approved

Open Access in DiVA

fulltext(1058 kB)36 downloads
File information
File name FULLTEXT01.pdfFile size 1058 kBChecksum SHA-512
bcfdf5a500d1bf2e3e36e24908f5d533b2d3f0d8bb9fe23c08a8fa85c5b3556997a27eb2c7128a974fce1998c95e757bc91067698ecb173ea7e7e4072a13ec19
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 36 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 126 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf