In this paper we propose a distributed algorithm to construct a scatternet for multi-hop ad hoc networks of Bluetooth devices. This algorithm is fully distributed and does not require the nodes in the networks being in-range(i.e., each pair of nodes in the network may be unable to communicate with each other directly). The role-selection process in existing scatternet formation mostly uses the strategy of message exchange and comparing their weights like IDs or power strength. This results in a large amount of control messages to be sent and a longer scatternet formation time. In our algorithm, the role selection procedure is simple. Nodes can decide their role by a randomly generated counter rather than their ¡¥weights¡¦. According to the proposed approach, nodes can determine their role of either a master or a slave of the piconet without recognizing its neighbors¡¦ ¡¥weight¡¦. The algorithm performs better time and reduces the number of control messages remarkably during the role-selection process. In this paper, we also define the gateways of 2-hops and 3-hops for evaluating the distance between two piconets.

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).

The Bluetooth Scatternet Formation (BSF) problem can be defined as the problem of forming wireless networks of Bluetooth devices in an efficient manner. A number of restrictions imposed by the Bluetooth specifications make the BSF problem challenging and unique. Many interesting solution algorithms have been proposed in the literature to solve this problem. In this thesis, we investigate the BSF problem. We concentrate on problems introduced by the procedures of device discovery of the Bluetooth specifications and on the different solutions used by BSF algorithms to deal with these problems. We study also in this thesis problems introduced by the specifications of link establishment in Bluetooth due to their close interaction with the device discovery specifications. We survey and categorize the different device discovery techniques used by BSF algorithms. This categorization is then used as a basis to identify the different theoretical computational models used to study BSF algorithms. We argue, in this thesis, that the currently available models for Bluetooth wireless networks do not model adequately, in most cases, the complexities of the Bluetooth specifications and we show that these models were oversimplified in many cases. A general computational model will be useful as a starting point to design BSF algorithms and to compare the different and numerous BSF algorithms – especially in term of the execution time efficiency. In this thesis, we provide a set of suggestions that will help in the creation of such model. We survey a number of studies that examined in more depth the specifications of device discovery in Bluetooth. We survey also other studies that attempted to simplify the Bluetooth network model, either by suggesting modifications on the Bluetooth specifications or by the use of communication technologies other than Bluetooth. Finally, we present some experiments accompanied with analyzes to show the complexities of the Bluetooth specifications and their sensitivity to minor changes (whether in the specifications or in their implementation).

A Wireless Personal Area Network (WPAN) is an ad hoc network that consists of devices that surround an individual or an object. Bluetooth® technology is especially suitable for formation of WPANs due to the pervasiveness of devices with Bluetooth® chipsets, its operation in the unlicensed Industrial, Scientific, Medical (ISM) frequency band, and its interference resilience. Bluetooth® technology has great potential to become the de facto standard for communication between heterogeneous devices in WPANs. The piconet, which is the basic Bluetooth® networking unit, utilizes a Master/Slave (MS) configuration that permits only a single master and up to seven active slave devices. This structure limitation prevents Bluetooth® devices from directly participating in larger Mobile Ad Hoc Networks (MANETs) and Wireless Personal Area Networks (WPANs). In order to build larger Bluetooth® topologies, called scatternets, individual piconets must be interconnected. Since each piconet has a unique frequency hopping sequence, piconet interconnections are done by allowing some nodes, called bridges, to participate in more than one piconet. These bridge nodes divide their time between piconets by switching between Frequency Hopping (FH) channels and synchronizing to the piconet's master. In this dissertation we address scatternet formation, routing, and security to make Bluetooth® scatternet communication feasible. We define criteria for efficient scatternet topologies, describe characteristics of different scatternet topology models as well as compare and contrast their properties, classify existing scatternet formation approaches based on the aforementioned models, and propose a distributed scatternet formation algorithm that efficiently forms a scatternet topology and is resilient to node failures. We propose a hybrid routing algorithm, using a bridge link agnostic approach, that provides on-demand discovery of destination devices by their address or by the services that devices provide to their peers, by extending the Service Discovery Protocol (SDP) to scatternets. We also propose a link level security scheme that provides secure communication between adjacent piconet masters, within what we call an Extended Scatternet Neighborhood (ESN).

In the short-range wireless communication and networking, Bluetooth is a promising technology, mainly used as a replacement for connected cables. Since the Bluetooth specification only defines how to build a Piconet, several solutions have been proposed to construct a Scatternet from the Piconets in the literatures. The process of constructing a Scatternet is called the Scatternet formation. The traditional scatternet formation has three defects: First, more power and time need to be consumed in order to construct the scatternet. Second, after the scatternet is formed, more power and bandwidth are required to maintain the connection of scatternet. Third, due to the restriction of topology, the communication between two nodes must be relayed through the bridge or master, even when they are in the communication range. In this thesis, we propose a novel method in the transmission ranges of all the other nodes to form temporary point-to-point piconet only when two nodes want to communicate with each other. When the communication is finished, the temporary point-to-point piconet is destroyed immediately. Two nodes in the communication range can communicate with each other directly without the relay node. Our On-Demand Point-To-Point Piconet Formation (ODP2P) scheme resolves the defects of traditional scatternet formation in communication range. In order to reduce the communication delay, every node owns its list to record the information of all nodes within the communication range. An on-event method maintains the list. Network performance analysis and simulations show that our method can reduce the routing path significantly, provide better utilization for Bluetooth personal area network (PAN), and maintain the range list efficiently.

<p> Wireless communication has been thriving in recent years. Developments in the hardware and software industries enable more and more devices to be embedded in wireless communication modules. All kinds of interesting applications based on wireless connections are emerging, demanding simple and efficient ways to inter-connect different devices. Bluetooth is an industry standard initially proposed by Ericsson, IBM, Microsoft and some other leading IT companies to meet this growing demand. Initially, it intended to provide universal low cost, low power, and low complexity wireless interface to various devices. Furthermore, it also proposed to provide the possibility of interconnecting a number of mobile devices to form a network. However, the details of network formation and operation have not yet been regulated. In this work, we will investigate Bluetooth enabled network formation issues (especially when the traffic patterns on the network are well known).</p> <p> In this thesis, we use a small indoor area network model with a wired infrastructure network installed in the wall. A number of mobiles are distributed in the area and require inter-connectivity with each other and/or the outside world through multiple gateways. Unbalanced traffic in the network may result in hotspots leading to poor network throughput. Therefore, a centralized network formation algorithm is needed for Bluetooth networks to solve this problem.</p> <p> This thesis proposes novel Network Formation based on a Traffic Distribution (NFTD) mechanism. This centralized mechanism co-ordinates the behavior of mobiles and is implemented on gateways (also called access points). It forms the network topology according to the traffic distribution so that the path length of hotspot flows can be limited in order to maximize the network capacity. Last but not least, infrastructure networks provide free high-speed links for mobiles to further increase network capacity. The proposed mechanism is a promising mechanism as supported by simulation results.</p> / Thesis / Master of Applied Science (MASc)

The Internet of Things (IoT) is a vision that aims at inter-connecting every physical identifiable object (or, a thing) via a global networking infrastructure (e.g., the legacy Internet). Several architectures are proposed to realize this vision; many of which agree that the IoT shall be considered as a global network of networks. These networks are used to manage wireless sensors, Radio Frequency IDentification (RFID) tags, RFID readers and other types of electronic devices and integrate them into the IoT. A major requirement of the IoT architectures is scalability, which is the capability of delivering high performance even if the input size (e.g., number of the IoT objects) is large. This thesis studies and proposes solutions to meet this requirement, and specifically focuses on the scalability issues found in the networks of the IoT. The thesis proposes several network formation algorithms to achieve these objectives, where a network formation algorithm is an algorithm that, if applied to a certain network, optimizes it to perform its tasks in a more efficient manner by virtually deleting some of its nodes and/or edges. The thesis focuses on three types of networks found in the IoT: 1) RFID readers coverage networks; whose main task is to cover (i.e., identify, monitor, track, sense) IoT objects located in a given area, 2) readers inter-communications networks; whose main task is to guarantee that their nodes are able to inter-communicate with each other and hence use their resources more efficiently (the thesis specifically considers inter-communication networks of readers using Bluetooth for communications), and 3) Object Name Systems (ONS) which are networks of several inter-connected database servers (i.e., distributed database) whose main task is to resolve an object identifier into an Internet address to enable inter-communication via the Internet. These networks are chosen for several reasons. For example, the technologies and concepts found in these networks are among the major enablers of the IoT. Furthermore, these networks solve tasks that are central to any IoT architecture. Particularly, the thesis a) studies the data and readers redundancy problem found in RFID readers coverage networks and introduces decentralized RFID coverage and readers collisions avoidance algorithms to solve it, b) contributes to the problem of forming multihop inter-communications networks of Bluetooth-equipped readers by proposing decentralized time-efficient Bluetooth Scatternet Formation algorithms, and c) introduces a geographic-aware ONS architecture based on Peer-To-Peer (P2P) computing to overcome weaknesses found in existing ONS architectures.

The Internet of Things (IoT) is a vision that aims at inter-connecting every physical identifiable object (or, a thing) via a global networking infrastructure (e.g., the legacy Internet). Several architectures are proposed to realize this vision; many of which agree that the IoT shall be considered as a global network of networks. These networks are used to manage wireless sensors, Radio Frequency IDentification (RFID) tags, RFID readers and other types of electronic devices and integrate them into the IoT. A major requirement of the IoT architectures is scalability, which is the capability of delivering high performance even if the input size (e.g., number of the IoT objects) is large. This thesis studies and proposes solutions to meet this requirement, and specifically focuses on the scalability issues found in the networks of the IoT. The thesis proposes several network formation algorithms to achieve these objectives, where a network formation algorithm is an algorithm that, if applied to a certain network, optimizes it to perform its tasks in a more efficient manner by virtually deleting some of its nodes and/or edges. The thesis focuses on three types of networks found in the IoT: 1) RFID readers coverage networks; whose main task is to cover (i.e., identify, monitor, track, sense) IoT objects located in a given area, 2) readers inter-communications networks; whose main task is to guarantee that their nodes are able to inter-communicate with each other and hence use their resources more efficiently (the thesis specifically considers inter-communication networks of readers using Bluetooth for communications), and 3) Object Name Systems (ONS) which are networks of several inter-connected database servers (i.e., distributed database) whose main task is to resolve an object identifier into an Internet address to enable inter-communication via the Internet. These networks are chosen for several reasons. For example, the technologies and concepts found in these networks are among the major enablers of the IoT. Furthermore, these networks solve tasks that are central to any IoT architecture. Particularly, the thesis a) studies the data and readers redundancy problem found in RFID readers coverage networks and introduces decentralized RFID coverage and readers collisions avoidance algorithms to solve it, b) contributes to the problem of forming multihop inter-communications networks of Bluetooth-equipped readers by proposing decentralized time-efficient Bluetooth Scatternet Formation algorithms, and c) introduces a geographic-aware ONS architecture based on Peer-To-Peer (P2P) computing to overcome weaknesses found in existing ONS architectures.