[[alternative]]在無線藍芽個人網路中發展高效率繞徑協定

博士[[abstract]]Bluetooth是一種短距離無線通訊的技術，並具有低耗電量、低成本及體積小等特性。Relay在Bluetooth的架構裡提供不同piconet間資料代傳的服務。由於scatternet中存在的relay數量及degree的大小影響整體網路的效能，而不適當的relay將造成piconet間scheduling難度提高及relay在不同piconet間切換產生的guard time overhead 及傳輸延遲。因此，本論文透過移除不適當的relay，提出一動態調整網路拓撲的協定，使調整後的scatternet能具有連通、高頻寬使用率及低維護成本的特性。此外，本論文亦提出繞徑協定(LORP)，能有效減少繞徑長度及建立備份路徑，並考量在具位置資訊的網路環境下，提出一loaction-aware的繞徑協定(LARP)，利用位置資訊動態調整scatternet架構及縮短繞徑長度。最後，本論文提出繞徑協定(HLARP)，解決當環境中部份無線設備具有位置資訊時的繞徑問題。由實驗的數據顯示，本論文所提出的協定能有效縮短繞徑長度、減少網路延遲及提高頻寬使用率。[[abstract]]Bluetooth is a new technology for low-cost, low-power, and short-range wireless communication. By constructing a piconet, Bluetooth device establishes link and communicates with other device in a master-slave manner. Relay is a Bluetooth device that joins two or more piconets and forwards data from one piconet to another, providing multi-hop (or inter-piconet) communication services. In a Bluetooth scatternet, the number of relays and the degree of each relay are factors that significantly affect the performance of entire network. Unnecessary relays raise the difficulty of scheduling, leading to frequent packet loss. Relay switching among several piconets in turns also creates guard time overhead and increases the transmission delay. This proposal first presents an effective protocol that can dynamically adjust the network topology by reducing the unnecessary relays. An efficient scatternet environment thus can be constructed with characteristics of connected, high bandwidth utilization and low maintenance cost. Then, a routing protocol, LORP, is developed to reduce the path length and generate two disjoint routes for any pair of source and destination devices located in different piconets. Additionally, a location-aware routing protocol, LARP, for the Bluetooth scatternet is aslo proposed, which reduces the hop counts between the source and the destination and reconstructs the routes dynamically using the location information of the Bluetooth devices. Finally, a hybrid location-aware routing protocol, HLARP, is proposed to construct the shortest routes among the devices with or without having the location information and degenerate the routing schemes without having any location information. Experimental results show that our protocols are efficient to construct the shortest routing paths and to minimize the transmission delay, bandwidth and power consumption as compared to the other protocols that we have considered.[[tableofcontents]]Contents 1. Introduction 1 2. Backgrounds and Basic Concepts 9 3. Dynamic Relay Reduction Protocol 21 4. Local Optimal Routing Protocol for Scatternet over Bluetooth Radio system 28 4.1 Path Reduction Procedure 32 4.2 Creating the Disjoint Routes 35 4.3 The Routing Protocol 39 4.4 Performance Study 43 5. Location-Aware Routing Protocol for the Bluetooth Scatternet 51 5.1 Network Model 51 5.2 The Location-Aware Routing Protocol (LARP) 55 5.3 Hybrid Location Aware Routing Protocol (HLARP) 66 5.4 Simulation Results and Comparison 69 6. Conclusions and Future Works 74 References 76 List of Figures 1.1. Applications of Bluetooth technology in a Wireless Personal Area Network 3 1.2. Bluetooth scatternet diagram 4 2.1. Bluetooth Radio Operation 10 2.2. Link establishing operation 13 2.3. A Scatternet structure containing two relays 14 2.4. The scatternet obtained by applying the proposed relay reduction protocol on the scatternet shown in Fig. 2.3 16 2.5. Transmission of control packet and routing path in RVM Protocol 17 2.6. Transmission of control packet and routing path in LORP 18 2.7. Final routing path constructed in LARP 19 3.1. A simple scatternet environment, where rc={1,3}, rc ={2,3}, rc ={1,2,3} are relays in the scatternet 21 3.2. A scatternet structure before executing the Relay Reduction Protocol 24 3.3. The resultant scatternet after executing the Relay Reduction Protocol 26 4.1. Path Reduction Procedure 30 4.2. Two routes share the same Bluetooth node 31 4.3. Scheduling of parallel data transmission by two disjoint routes 36 4.4. Problem encountered during the construction of second routes 37 4.5. Construction of two disjoint routes 38 4.6. A snapshot before relay reduction 44 4.7. A snapshot after relay reduction 44 4.8. Comparison of the number relay under any size 44 4.9. A snapshot of executing routing protocol 45 4.10. Comparison in route length with space size 20*20 46 4.11. Comparison in route length with space size 40*40 46 4.12. Comparison in route length with space size 80*80 47 4.13. Comparison in the number of control packet with space size 20*20 47 4.14. Comparison in the number of control packet with space size 40*40 48 4.15. Comparison in the number of control packet with space size 80*80 48 4.16. The impact of network density on throughput 49 4.17. The impact of network density on Packet Lost Rate 49 4.18. Comparison of the data packet traffic 50 5.1. Format of the Route Search Packet 55 5.2. Steps of the route search phase of Algorithm 1 58 5.3. Format of the Route Search Packet sent by different nodes in the scatternet 58 5.4. Format of the Route Reply Packet 59 5.5. Example of applying Reduction and Replacement Rule in route reply phase 62 5.6. Route Reply Phase based on reduction and replacement rule 63 5.7. The DFN field in RRP sent by different nodes in the Route Replay Phase 64 5.8. Final route Construction Phase in LARP 65 5.9. Construction of route in HLARP 67 5.10. The rate of finding successful path for different scatternet sizes 70 5.11. The route construction time scatternet sizes 70 5.12. Average number of hop counts in different protocols for various scatternet sizes 71 5.13. Average number of hop counts in different protocols for different device numbers 71 5.14. Bandwidth consumption in different protocols for various scatternet sizes 72 5.15. Bandwidth consumption in different protocols for different device numbers 72 5.16. Ratio of power consumption in different protocols for different number of routing paths 73[[note]]學號: 691190218, 學年度: 9