以藍芽為基礎隨意網路形成機制與系統性能之研究

Abstract

本文中提出三種分散網路形成演算法，首先，Blueweb是一個基於藍芽之多跳躍(Multi-hop)網路新架構，包含有效率的分散形成演算法與混成路由協定。Blueweb之演算法設計兩種機制，一個是角色交換機制，在整個網路中僅用slave當作中繼節點，另一個是返回連接機制，將分散網路架構由樹狀改成網狀，同時，設計一個修正的來源路由(Modified Source Routing)協定來尋找路徑和傳送資料。 而Configured Blueweb設計一個自動組態(Automatic Configuration)方法來對Blueweb之路由協定決定出最佳化組態。此方法包含三種功能方塊，路由master選擇方塊以低的計算成本來作路由master的選擇，節點指定方塊指定節點到每個子網路以降低路徑詢問成本，子網路數目決定方塊以最少成本來達到最大的效能改善，並決定出最佳子網路數目。 最後，Modified Blueweb是一個基於階層的方法來決定新的根(root)節點，同時，新的根節點再產生他們各自的子網路，此方法對各種不同規模的藍芽網路可以分配出有效的組態架構。

In this dissertation, three scatternet formation mechanisms are proposed. Firstly, Blueweb is a new Bluetooth-based multihop network with an efficient scatternet formation algorithm and a hybrid routing protocol. Blueweb’s scatternet formation uses two mechanisms. One is the role exchange mechanism in which only slave nodes serve as the role of relay through the whole scatternet. The other one is the return connection mechanism in which we convert the scatternet from a tree-shaped to a web-shaped topology. Meanwhile, a modified source routing protocol is designed for Blueweb in which we combine the proactive method with the reactive method to discover the optimal path for packet transmission. Then we present configured Blueweb with an automatic configuration algorithm to determine the optimal network configuration for the Blueweb routing protocol. This algorithm contains three main functional blocks including route master selection, node assignment, and subnet number decision. The route master selection block selects new route masters at a low computation cost. The node assignment block assigns nodes to each newly configured subnet in order to minimize the average route query cost. The subnet number decision block determines the optimal number of subnets which achieves the largest system performance improvement ratio at minimum operation cost. Finally, Modified Blueweb is a tier-based method to determine new roots and each new root spontaneously generates their individual web-shaped subnets. This method can be used to generate an efficient scatternet configuration for various sizes of Bluetooth scatternet.