Bluetooth是一種短距離無線通訊的技術，並具有低耗電量、低成本及體積小等特性。本論文擬在藍芽網路中發展繞徑及群播通訊協定。首先，在繞徑通訊協定此議題上，本論文提出一個位置感知的繞徑協定(LAMP)，利用位置資訊動態調整散網架構、縮短繞徑長度及建立備份繞徑，以同時達到省電及高效能傳輸之目的。之後，本論文亦提出繞徑維護演算法(ROMA)，以保證藍芽裝置的連結、重建繞徑並減少繞徑長度。另一方面，在群播通訊協定此議題上，為了在藍芽網路提供群播服務，建立一個群播樹以提供群播訊息給所有的群播成員，將可減少網路延遲及節省頻寬與電量消耗，然而，礙於藍芽通訊協定的限制，一個現有的散網拓撲可能不適合建構一個有效的群播樹，這將造成電量消耗及傳輸延遲。因此，本論文提出一個二層式的群播樹通訊協定(TMCP)，利用角色轉換技術以建構有效的群播樹，使得群播樹的高度及傳輸延遲可以被減少。由實驗的數據顯示，本論文所提出的協定能有效縮短繞徑長度、重建繞徑、提供良好的郡播服務、減少網路延遲及提高頻寬使用率。

Bluetooth is a low power, low cost, and short-range wireless technology developed for personal area networks. This thesis aims at developing routing and multicasting communication protocols for Bluetooth radio networks. In the routing issue, this thesis firstly presents a Location Aware Mobility based routing Protocol (LAMP), which considers location information of the devices to minimize the number of hop of the route between any source and destination and constructs the backup path to prevent the route from failure raised due to the mobility of devices. Next, we propose a novel ROute Maintenance Algorithm (ROMA) for guaranteeing the connectivity among devices, reconstructing the routes dynamically, and reducing the path length based on the location information and mobility of devices. In the multicasting issue, this thesis proposes a Two-layer Multicast Communication Protocol (TMCP) using role switching techniques for constructing an efficient multicast tree is developed. In order to provide multicast services in the multicasting issue, constructing a multicast tree can serve the delivery of multicast messages for all multicast members so that the propagation delay is reduced and the bandwidth and energy consumption are saved. However, due to the constrain of Bluetooth protocol, a given connected scatternet topology may not be appropriate for constructing an efficient multicast tree and hence causes energy consumption and end-to-end delay. The proposed TMCP collects as many as possible the members into the same piconet, reduces the length of multicast paths and assigns each member with a proper role. The constructed multicast tree has several features, including as few as possible the non-member devices, the smallest tree level and the minimal propagation delay. Experimental results show that our protocols can efficiently construct the shortest routing paths, reestablish the routing paths, offer multicast service and outperform in terms of the transmission delay, bandwidth and energy consumption as compared to the other protocols that we have considered.

Table of Contents IV
List of Figures VI
List of Tables X
Chapter 1 Introduction 1
Chapter 2 Related Work 5
2.1 Literature Review of Routing Protocols 5
2.2 Literature Review of Multicast Protocols 10
Chapter 3 Preliminary 12
3.1 Radio Characteristics of Bluetooth Networks 12
3.2 Role Switch Operations 17
Chapter 4 Mobility Based Routing Protocols 21
4.1 Basic Concept of LAMP and ROMA 21
4.2 System Model 25
4.3 Location Aware Mobility Based Routing Protocol 25
4.3.1 Route Search Phase 27
4.3.2 Route Reply Phase 28
4.3.3 Route Construction Phase 35
4.4 LAMP Enhancement Scheme	37
4.4.1 Network Routing Problem 38
4.4.2 Piconet Combination Operation 42
4.4.3 Route Optimization Operation 43
4.5 Performance Evaluation of LAMP 45
4.6 Route Maintenance Algorithms 52
4.6.1 Node Add Procedure 55
4.6.2 Node Leaving Procedure 58
4.7 Performance Study of ROMA 69
Chapter 5 Multicast Communication Protocol 76
5.1 Basic Concept of TMCP 76
5.2 Two-Layer Multicast Communication Protocol 81
5.2.1 Multicast Tree Construction Phase 81
5.2.2 Multicast Tree Reorganization Phase 86
5.3 Performance Study of TMCP 91
Chapter 6 Conclusions and Future Work 101
References 103

List of Figures
1.1 A scatternet consists of three piconets. An S/S bridge connects piconets Pa and Pb and an M/S bridge connects piconets Pb and Pc	2
3.1 Bluetooth radio operation 13
3.2 Link establishing operation 16
3.3 A scatternet structure containing two relays 17
3.4 (a) Topology before executing Piconet Combining operation. (b) Topology after executing Piconet Combining switching operation 18
3.5 (a) Topology before executing Piconet Splitting operation. (b) Topology after executing Piconet Splitting operation 19
3.6 (a) Topology before executing Piconet Take Over operation. (b) Topology after executing Piconet Take Over operation 20
4.1 An example of a scatternet initially formed by several Bluetooth nodes 22
4.2 Routing path formed by the RVM algorithm to route data from S to D 22
4.3 Routing path formed by the LORP algorithm to route data from S to D 23
4.4 Routing and backup paths formed by the LAMP to route data from S to D 23
4.5 Routing path formed by the ROMA to route data from S to D 24
4.6 Format of the Route Search Packet 28
4.7 An example of shortest and backup path between the source S and destination D 29
4.8 Format of the Route Reply Packet (RRP) 30
4.9 RSP is forwarded along the path from the destination D to the source S 33
4.10 The FFN and FBN set of each node along the routing path 35
4.11 Final route construction phase in LAMP 37
4.12 An example of network bottleneck problem 39
4.13 M2 cannot establish a link with A due to limitation of nodes 39
4.14 An Example of takeover operation 41
4.15 An example of split operation 41
4.16 An example of park operation 42
4.17 An example of the piconet combination operation 43
4.18 The basic idea of route optimization 43
4.19 An example of route optimization 44
4.20 The average hop counts in different protocols for the different number of mobile nodes 47
4.21 The average hop counts in different protocols for the different average mobility speed 47
4.22 The average number of control packets in different protocols for the different number of mobile nodes 49
4.23 The average number of control packets in different protocols for the different average mobility speed 49
4.24 The total bandwidth consumption ratio in different protocols for the different number of mobile nodes 50
4.25 The total bandwidth consumption ratio in different protocols for the different average mobility speed 50
4.26 The total energy consumption ratio in different protocols for the different number of mobile nodes 52
4.27 The total energy consumption ratio in different protocols for the different average mobility speed 52
4.28 Illustration of weak node and weak link. (b) Example of a weak link and weak node due to mobility of any node Si 54
4.29 The algorithm of node add procedure 56
4.30 The algorithm of connecting procedure 56
4.31 Illustration of route maintenance due to addition of a new node. (a) Addition of new node S11 to the routing master M1. (b) The new routing path after addition of node S11 57
4.32 The algorithm of node replacement procedure 59
4.33 An example of node replacement due to mobility of a node. (a) Original scatternet without any node replacement. (b) Replacement of node due to mobility of S11 60
4.34 The algorithm of link replacement procedure 61
4.35 An example of link replacement due to mobility of a node. (a) Original scatternet without any link replacement. (b) One weak link is formed due to mobility of S11, which is replaced by the bold lines 62
4.36 Formation of two weak links and their replacement. (a) Original scatternet without any link problem. (b) Two weak links are formed due to mobility of S11, which are replaced later 64
4.37 Formation of weak link, where a weak node is connected to two routing masters. (a) Original scatternet without any link problem. (b) Weak link is formed due to mobility of B61 65
4.38 The algorithm of node leaving procedure 66
4.39 The algorithm of subroute construction procedure 68
4.40 An example for executing Subroute Construction Procedure before and after mobility of a node. (a) Execution of Subroute Construction Procedure: before movement of node S11. (b) Execution of Subroute Construction Procedure: after movement of node S11 68
4.41 Average number of hop counts for different number of newly added nodes 71
4.42 Average number of hop counts in different protocols for different rate of mobile devices 71
4.43 Average number of hop counts for different average speed of the nodes 71
4.44 Average end-to-end delay for different number of newly added nodes 73
4.45 Average end-to-end delay in different protocols for different rate of mobile devices 73
4.46 Average end-to-end delay for different average speed of the nodes 73
4.47 Bandwidth consumption ratio for different number of newly added nodes 73
4.48 Required average number of control packets for different average speed of the mobile nodes 74
4.49 Average number of control packets for different rate of mobile nodes 74
5.1 An ideal multicast tree in Bluetooth scatternet 77
5.2 An example of multicast tree construction by applying the flooding-based mechanism 78
5.3 An example of efficient multicast tree constructed by applying the TMCP mechanism 80
5.4 An example of multicast tree constructed after executing the Phase I of TMCP on Fig. 5.2(b) 84
5.5 (a) Topology before executing Members_Switch(f, a, b). (b) Topology after executing Members_Switch(f, a, b) 87
5.6 Comparisons of TMCP and Flooding mechanisms in terms of the number of forwarding nodes in the constructed multicast tree. The region size is set at L×L units, where L=10, 20 or 30 92
5.7 The power consumptions for executing phases I and II of TMCP. The region size is set at L×L units, where L=10, 20 or 30 92
5.8 Comparison of the TMCP and Flooding mechanisms in terms of the tree height. The region size is set at L×L units, where L=10, 20 or 30 93
5.9 Comparison of the TMCP and Flooding mechanisms in terms of the down-link number of internal nodes. The region size is set at L×L units, where L=10, 20 or 30 93
5.10 Comparison of TMCP and Flooding mechanisms in terms of power consumption under various transmission loads. The region size is set at 20×20 units 95
5.11 Tree construction delay of phase I and II of TMCP. The region size is set at L×L units, where L=10, 20 or 30 95
5.12 Comparison of TMCP and Flooding mechanisms in terms of the guard time. The region size is set at L×L units, where L=10, 20 or 30 96
5.13 Comparison of TMCP and Flooding schemes in terms of tree construction. The region size is set at L×L units, where L=10, 20 or 30 96
5.14 Comparison of TMCP and Flooding schemes in terms of the propagation delay of multicast service under various transmission loads. The region size is set at 20×20 units 98
5.15 Comparison of Flooding(nonQoS), TMCP(nonQoS) and TMCP(QoS) schemes in terms of transmission delay. The number of members and region size are set at 45 and 20×20 units, respectively 98

List of Tables
3.1 Simulation parameters 46

[1] The Bluetooth Specification, http://www.bluetooth.org.
[2] http://www.ieee802.org/15/.
[3] G. J. Yu, C. Y. Chang, K. P. Shih and S. C. Lee, "Relay Reduction and Disjoint Routes Construction for Scatternet over Bluetooth Radio Systems," Journal of Network & Computer Applications, vol. 30, Apr. 2007, pp. 728-749.
[4] C. Perkins and P. Bhagwat, “Destination Sequenced Distance Vector Routing for Mobile Computers,” in Proc. of the ACM SIGCOMM, Sep. 1994.
[5] C. Perkins and E. Royer, “Ad-hoc On-Demand Distance Vector Routing,” in Proc. of the IEEE Workshop on Mobile Computing Systems and Applications, Feb. 1999.
[6] S. Giordano, I. Stojmenovic and L. Blazevic, “Position Based Routing Algorithms for Ad Hoc Networks: A Taxonomy,” In Ad Hoc Wireless Networking, Kluwer Academic Publishers, 2003.
[7] S. Ali, “The Feasibility of Mobile Adhoc Routing Over Bluetooth,” Thesis of MEng Degree in Computer Science, University College London, 2004.
[8] M. Sun, C. K. Chang and T. H. Lai, “A Self-Routing Topology for Bluetooth Scatternets,” in Proc. of the International Symposium on Parallel Architectures, May 2002.
[9] C. S. Choi and C. W. Choi, “DSR Based Bluetooth Scatternet,” in Proc. of the International Conference on Circuits/Systems Computers and Communications, May 2002.
[10] A. B. Mirza and J. K. Pollard, “Dynamic Source Routing in Bluetooth Personal Area Networks,” http://www.ducati.doc.ntu.ac.uk/uksim/journal/Vol-5/No-1&2/MIRZA.pdf
[11] C. H. Yang and J. W. Ruan, “On-demand Routing for Bluetooth Scatternets Subject to Device Mobility,” in Proc. of the 19th International Conference on Advanced Information Networking and Applications, 2005.
[12] Z. Jian, Z. Fei and W. Bin, ”Cluster Based Routing in Bluetooth Ad-hoc Network,” in Proc. of the International Conference on Wireless Communications Networking and Mobile Computing, Sep. 2005.
[13] J. Werb and C. Lanzl. “Designing a Positioning System for Finding Things and People indoors,” IEEE Spectrum, vol. 9, no. 35, Sep. 1998, pp. 71-78.
[14] N. B. Priyantha, A. Chakraborty and H. Balakrishnan, “The Cricket Location-Support System,” in Proc. of the Sixth Annual ACM Intl. Conf. on mobile Computing and Networking, Aug. 2000. 
[15] Texas Instruments TIRIS. http://www.ti.com/tiris/default.htm.
[16] F. J. Gonzalez-Castano, J. Garcia-Reinoso, “Survivable Bluetooth Location Networks,” in Proc. of the IEEE International Conference on Communication, May 2003.
[17] U. Vershney, R. J. Vetter and R. Kalakota, “Mobile Commerce: A New Frontier,” Computer, vol. 10, Oct. 2000, pp. 32-38.
[18] A. Darling, “Waiting for the M-commerce Explosion,” Telecommunication International, vol. 3, Feb. 2001, pp. 34-39.
[19] J. Engebretson, “Opportunities for Growth,” Wireless Asia, 2006.
[20] R. Bridgelall, “Enabling Mobile Commerce through Pervasive Communications with Ubiquitous RF Tags,” in Proc.of the IEEE Wireless Communications and Networking Conference, Mar. 2003.
[21] K. Sangani, ”RFID Sees All,” IEEE Review, vol. 50, no. 4, Apr. 2004, pp. 22-24.
[22] L. M. Ni, Y. Liu, Y. C. Lau and A. P. Patil, ”LANDMARC: Indoor Location Sensing Using Active RFID,” in Proc. of the First IEEE International Conference on Pervasive Computing and Communications, Mar. 2003.
[23] F. J. Gonzalez-Castano and J. Garcia-Reinoso, “Bluetooth Location Networks,” in Proc. of the IEEE Global Telecommunications Conference, Nov. 2002.
[24] Bluetooth Nokia. http://www.nokia.com/phones/6210/bluetooth.html.
[25] P. Bhagwat and A. Segall, “A Routing Vector Method (RVM) for Routing in Bluetooth Scatternets,” in Proc. of the IEEE Workshop on Mobile Multimedia Communications, Nov. 1999.
[26] O. Song, C. Lim and C. H. Choi, “Mobility Management in Bluetooth Ad Hoc Networks,” in Proc. of the 14th Joint Conference on Communications & Information, Apr. 2004.
[27] C. Y. Chang, P. K. Sahoo and S. C. Lee, “A Location-Aware Routing Protocol for the Bluetooth Scatternet,” Wireless Personal Communication, vol. 40, no. 1, Jan 2007, pp. 117-135. 
[28] S. K. Das, B. S. Manoj and C S R. Murthy, “A Dynamic Core Based Multicast Routing Protocol for Ad Hoc Wireless Networks,” in Proc. of the 3th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, Jun. 2002.
[29] C. R. Dow, J. H. Lin, K. T. Chen, S. C. Chen and S. F. Hwang, “A Scalable and Reliable Multicast Routing Protocol for Ad-hoc Wireless Networks,” Wireless Personal Communications, vol. 34, no. 4, Sep. 2005, pp. 335-357.
[30] C. C. Chiang, M. Gerla and L. Zhang, “Adaptive Shared Tree Multicast in Mobile Wireless Networks,” in Proc. of the IEEE Global Telecommunications Conference Nov. 1998. 
[31] S. J. Lee, W. Su and M. Gerla, “On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks,” Mobile Networks and Applications, vol. 7, no. 6, Dec. 2002, pp. 441-453.
[32] L. Layuan and L. Chunlin, “A Distributed Multicast Routing Protocol with QoS Constraints,” in Proc. of the IEEE 10th International Conference on Networks Aug. 2002.
[33] S. Lee, W. Su, J. Hsu, M. Gerla and R. Bagrodia, “A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols,” in Proc. of the 19th Conference of the IEEE Communications Society, Mar. 2000.
[34] J. G. Jetcheva and D. B. Johnson, “Adaptive Demand-Driven Multicast Routing in Multi Hop Wireless Ad Hoc Networks,” in Proc. of the 2th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing Oct. 2001.
[35] L. Farkas, B. Bakos and P. Spanyi, “A Practical Approach to Multicasting in Bluetooth Piconets,” in Proc. of the IEEE Wireless Communications and Networking Conference, Mar. 2006.
[36] Zhang Pei, Li Weidong, Wang Jing and Wang Youzhen, “Bluetooth-The Fastest Developing Wireless Technology,” in Proc. of the International Conference on Communication Technology, Aug. 2000.
[37] Lakshmi Ramachandran, Manika Kapoor, Abhinanda Sarkar and Alok Aggarwal, “Clustering Algorithms for Wireless Ad Hoc Networks,” in Proc. of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Aug. 2000.
[38] C. Y. Chang and H. R Chang, "Adaptive Role Switching Protocol for Improving Scatternet Performance in Bluetooth Radio Networks," IEEE Transactions on Consumer Electronics, vol. 52, no. 4, Nov. 2006, pp. 1229-1238. 
[39] J. Bray and C.F. Sturman, Bluetooth Connect Without Cables, Prentice-Hall, America, 2001.
[40] X. Zeng, R. Bagrodia and M. Gerla, “GloMoSim: A Library for Parallel Simulation of Large-Scale Wireless Networks,” in Proc. of the Twelfth Workshop on Parallel and Distributed Simulation, May 1998.
[41] J. P. Sheu, K. P. Shih, S. C. Tu and C. H. Cheng, “A Traffic-Aware Scheduling for Bluetooth Scatternets,” IEEE Transactions on Mobile Computing, vol. 5, no. 7, Jul. 2006, pp. 872-883.