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. / 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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-215108 |
| Date | January 2017 |
| Creators | Fuglesang Geuken, Niclas |
| Publisher | KTH, Optimeringslära och systemteori |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-MAT-E ; 2017:65 |
Page generated in 0.0013 seconds