| Bluetooth is a de fac to global standard for short-range wireless data and voicecommunication. It enables various personal data devices to have wireless comm-unication function easily because it has many intriguing characteristics, such as lowcost, low power, small size, and free spectrum. With the development and populari-zation of Bluetooth, there is increasing interest in wireless ad hoc networks builtfrom portable devices equipped with Bluetooth. But the certain constraints of Blue-tooth make the new challenge in constructing and managing a wireless ad hoc net-work with the Bluetooth devices.The ad hoc wireless mobile network based on Bluetooth is self-construction,self-organization and self-management wireless mobile network without additionalnetwork devices or manual configuration. It applies frequency-hopping spread spect-rum technology in the MAC layer, so Bluetooth devices are not able to communicateunless they have previously discovered each other by synchronizing their frequencyhopping patterns. Bluetooth network is composed of piconets, each piconet has itsown frequency-hopping sequence. Within a piconet, a Bluetooth device can be eithera master or a slave, each piconet has only one master and up to 7 active slaves. Thecommunication between devices obeys on a centralized master-slave mechanism.Multiple piconets can co-exist in a common area and piconets can be interconnectedvia bridge device to form a larger , flexible and complex ad hoc network known as ascatternet. The Bluetooth specification has not had feasible introduction on scatternettopology formation , packet routing, channel or link scheduling and access pointhand of .To construct a determinate Bluetooth network topology, Bluetooth devices areinquired to discovery each other, and then to construct point-to-point physicalconnection in order to synchronize their frequency-hopping sequence and exchangetheir essential address and clock information. Better scatternet topology constructionalgorithm can fastly carry out these steps to make devices within communicationrange form steady networks in a short time. Once Bluetooth scatternet topology isconstructed, as the base of network routing and scheduling, it will considerablyinfluence on the whole network performances of the routing and scheduling.In this paper, we analyze the Bluetooth protocol, the characteristics of frequencyhopping and master-slave mechanism, and then addresses the fundamental problemof scatternet formation, i.e., the problem of the self organization of Bluetoothdevices into a multi-hop network. The whole work is divided into three parts:First, according to the Bluetooth devices states and the process of physicalconne-ction construction in the current BT specifications, we conclude that thedevice discovery in multi-hop Bluetooth networks, the process and method ofelection of header device, the election of master device in each piconet, and theselection of bridge device's type are the key to fast construct connected and robustBluetooth scatternet topology. A scatternet topology formation algorithm has suchimportant performance measures: I. the connectedness of the formed network. IIwhether the algorithm is distributed. III. the number of de-vices in each piconet. IV.the number roles assumed by each node. V.routing robustness. VI. time complexity.VII. network diameter. VIII. message complexity. IX average degree of the devices.X the number of piconets. XI dynamic mainten-ance in network—self healing.Second, this paper introduces and analyses several typical Bluetooth scatternetformation algorithms and their formative processes in literature, and compares theirperformances of the main scatternet algorithms. It indicates that there are somedeficiencies in present algorithms on network topologies self-healing, discussesfamiliar problems in dynamic networks such as devices ingress, slave devices quit ormalfunction, master devices quit or malfunction, M/S bridge devices quit ormalfunction, S/S bridge devices quit or malfunction and so forth, thereby improvestopology algorithm, which could better adapt to dynamic condition.Third, this paper proposes a backup Bluetooth scatternet topology algorithm,which is distributed. Devices are independent each other, they are located at randomand know none messages about their neighbors. This algorithm doesn't demand thatthe devices are in communication range. By mathematical proving, it has suchfeatures: time complexity is O(logN), message complexity is O(N), networkdiameter is O(logN), In the formed scatternet the number of piconets close tominimum, the number roles assumed by each node approach to 1, the maximumdegree of the devices is 2. The core of this algorithm is to elect master deviceaccording to their remainder energy and data processing capability of nodes and soforth, this super master device begins to construct the first piconet. Based on thispiconet, by electing secondary master devices, the network expands step by step andpiconets are connected, finally a set of Bluetooth devices which are unknownquantitatively, distributed evenly at random, independent for each other and notlocated within communication range connect each other and form connectedBluetooth scatternet. After scatternet is constructed, each master device or bridgedevice chooses one pure slave device as its backup device. Once there are masterdevices or bridge devices quit or malfunction, the backup devices will take place ofthem to assure the network connected. This enhances scatternets' self-healing ability.The algorithm adapts to dynamic network.In this paper, we adopt BlueHoc Bluetooth network simulation softwareplatform based on NS2 in Linux operating system to simulate the backup Bluetoothscatternet topology algorithm. The result proves that the algorithm can be easilyimplemented. The formed scatternet has fewer piconets, fewer number rolesassumed by each node and lesser average degree of the devices. The time of networktopology constructed is shorter, and it's easy to manage the dynamic network. Thisalgorithm applies to construct Bluetooth scatternet topology. |
PDF Full Text Request