淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1707200611433000
中文論文名稱 在無線藍芽個人網路中發展高效率繞徑協定
英文論文名稱 Efficient Routing Protocols for Bluetooth Wireless Personal Area Network
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 94
學期 2
出版年 95
研究生中文姓名 李世傑
研究生英文姓名 Shih-Chieh Lee
學號 691190218
學位類別 博士
語文別 英文
口試日期 2006-06-17
論文頁數 78頁
口試委員 指導教授-張志勇
委員-陳裕賢
委員-陳宗禧
委員-謝孫源
委員-王三元
委員-石貴平
中文關鍵字 藍芽  無線個人區域網路  繞徑協定  拓撲調整  位置感知 
英文關鍵字 Bluetooth  Wireless Personal Area Network  Routing Protocol  Relay Reduction  Location-aware 
學科別分類 學科別應用科學資訊工程
中文摘要 Bluetooth是一種短距離無線通訊的技術,並具有低耗電量、低成本及體積小等特性。Relay在Bluetooth的架構裡提供不同piconet間資料代傳的服務。由於scatternet中存在的relay數量及degree的大小影響整體網路的效能,而不適當的relay將造成piconet間scheduling難度提高及relay在不同piconet間切換產生的guard time overhead 及傳輸延遲。因此,本論文透過移除不適當的relay,提出一動態調整網路拓撲的協定,使調整後的scatternet能具有連通、高頻寬使用率及低維護成本的特性。此外,本論文亦提出繞徑協定(LORP),能有效減少繞徑長度及建立備份路徑,並考量在具位置資訊的網路環境下,提出一loaction-aware的繞徑協定(LARP),利用位置資訊動態調整scatternet架構及縮短繞徑長度。最後,本論文提出繞徑協定(HLARP),解決當環境中部份無線設備具有位置資訊時的繞徑問題。由實驗的數據顯示,本論文所提出的協定能有效縮短繞徑長度、減少網路延遲及提高頻寬使用率。
英文摘要 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.
論文目次 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

參考文獻 [1]The Bluetooth Specification, http://www.bluetooth.org 1.0b & 1.1
[2]Pravin Bhagwat, Adrian Segall, “A Routing Vector Method (RVM) for Routing in Bluetooth Scatternets,” The Sixth IEEE International Workshop on Mobile Multimedia Communications (MOMUC'99), pp 375-379, Nov 1999.
[3]Pravin Bhagwat, “Bluetooth: Technology for Short-Range Wireless Apps,” IEEE Internet Computing 5(3), 2001.
[4]C. Y. Chang, G. J. Yu, C.-F. Lin, and T.-T. Wu, “Relay Reduction and Route Construction for Scatternet over Bluetooth Radio Systems,” Proceedings of the IEEE 16th International Conference on Information Networking, Korea, 2002.
[5]Simon Baatz , Matthias Frank , Carmen Kuhl , Peter Martini , Christoph Scholz, “Adaptive Scatternet Support for Bluetooth using Sniff Mode,” 26th Annual Conference on Local Computer Networks.
[6]Zhang Pei, Li Weidong, Wang Jing, Wang Youzhen, “Bluetooth-The Fastest Developing Wireless Technology,” WCC - ICCT 2000. pp1657 -1664, 2000.
[7]G.V.Zaruba, S. Basagni, and I. Chlamtac, “Bluetrees –Communications Scatternet Formation to Enable Bluetooth-based Ad Hoc Networks,” IEEE International Conference on (ICC), pp.273-277,2001 .
[8]C. Petrioli, S. Basagni, “Multihop Scatternet Formation for Bluetooth Networks,” IEEE Vehicular Technology Conference Spring, vol.1, pp.424-428, 2001.
[9]Lakshmi Ramachandran, Manika Kapoor, Abhinanda Sarkar and Alok Aggarwal, “Clustering Algorithms for Wireless Ad hoc Networks,” Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications , pp. 54-63, August 2000.
[10]Abhishek Das, Abhishek Ghose, Ashu Razdan, Huzur Saran, and Rajeev Shorey, “Enhancing Performance of Asynchronous Data Traffic over the Bluetooth Wireless Ad-hoc Network.” in the Proceedings of IEEE INFOCOM, April 2001.
[11]Manish Kalia, Sumit Garg, Rajeev Shorey, “Scatternet Structure and Inter-Piconet Communication in the Bluetooth System,” IEEE National Conference on Communications, 2000.
[12]Manish Kalia, Deepak Bansal, Reajeev Shory, “MAC Scheduling and SAR policies for Bluetooth: A Master Driven TDD Pico-Cellular Wireless,” Proceedings of IEEE Internationl Workshop on Mobile Multimedia Communications (MoMuC), November 1999.
[13]D. B. Johnson, and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Networks,” Mobile Computing, pp. 153-181, 1996.
[14]Z. J. Haas and M. R. Pearlman. “The Zone Routing Protocol (ZRP) for Ad-Hoc Networks(internet draft).” August 1998.
[15]Y. B. Ko and N. H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” Proceedings of the Fourth ACM/IEEE International Conference on Mobile Computing and Networking, pp. 66-75, October 1998.
[16]C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV) for Mobile Computers,” Proceedings of the Conference on Communication Architectures, Protocol, and Applications, pp. 234-244, 1994.
[17]Lakshmi Ramachandran, Manika Kapoor, Abhinanda Sarkar and Alok Aggarwal, “Clustering Algorithms for Wireless Ad hoc Networks,” Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 54-63, August 2000.
[18]Theodoros Salonidis, Pravin Bhagwat, Leandros Tassiulas, “Distributed Topology Construction of Bluetooth Personal Area Networks”, Proceedings of the IEEE INFOCOM, pp.1577-1586, 2001.
[19]G.V. Zaruba, S. Basagni, I. Chlamtac, “Bluetrees - scatternet formation to enable Bluetooth-based ad hoc networks”, IEEE International Conference on Communications (ICC), pp. 273-277,2001.
[20]Godfrey Tan, Allen Miu, John Guttag and Hari Balakrishnan, “Forming Scatternets from Bluetooth Personal Area Networks”, MIT Technical Report, MIT-LCS-TR-826, October 2001.
[21]S. Baatz, M. Frank, C. Kuhl, P. Martini, and C. Scholz, “Bluetooth scatternets: An enhanced adaptive scheduling scheme," Proceedings of the IEEE INFOCOM, June 2002.
[22]M. Kazantzidis and M. Gerla, “On the impact of inter-piconet scheduling in Bluetooth scatternets," Proceedings of the International Conference on Internet Computing (IC2002), vol. 1, pp. 37-43, June 2002.
[23]L. Har-Shai, R. Kofman, G. Zussman, and A. Segall, “Inter-picnoet scheduling in Bluetooth scatternets," Proceedings of OPNETWORK, 2002.
[24]L. Har-Shai, R. Kofman, A. Segall, and G. Zussman, “Load adaptive inter-piconet scheduling in small-scale Bluetooth scatternets," IEEE Communications Magazine, vol. 42, no. 7, pp. 136-142, July 2004.
[25]Younseog Chang; Sin-Chong Park; Seoungyoung Lee, ”An enhanced throughput and QoS-aware scheduling policy for Bluetooth,” Proceedings of Wireless Communications and Networking Conference, pp.1004 – 1007, March 2004.
[26]J. Werb and C. Lanzl, “A positioning system for finding things indoors”. IEEE Spectrum, Vol 9, pp. 71-78, 1998.
[27]N. B. Priyantha, A. Chakraborty and H. Balakrishnan. “The Cricket location-support system”. Proceedings of the Sixth Annual ACM International Conference on mobile Computing and Networking, 2000.
[28]A. Harter, A. Hopper, P.Steggles, A. Ward, and P. Webster. “The anatomy of a context-aware application”. Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999.
[29]Texas Instruments TIRIS. http://www.ti.com/tiris/default.htm
[30]F. J. Gonzalez-Castano, J. Garcia-Reinoso, “Survivable Bluetooth Location Networks”, Proceedings of the IEEE ICC, vol.2, pp. 1014- 1018, 2003.
[31]U. Vershney, R. J. Vetter, and R. Kalakota, “Mobile commerce: A new frontier,” Computer, vol. 10, pp. 32-38, 2000.
[32]A. Darling, “Waiting for the m-commerce explosion”, Telecommunication International, Vol 3, pp. 34-39, 2001.
[33]http://www.blueblitz.com/
[34]J. Engebretson, “Opportunities for growth,” Wireless Asia, March, 2006 http://www.telecomasia.net/telecomasia/article/articleDetail.jsp?id=314224
[35]Mobile RFID Activities in Korea, Electronics and Telecommunications Research Institute (ETRI), Expert Group Meeting on RFID, Oct. 2005.
[36]R. Bridgelall, “Enabling mobile commerce through pervasive communications with ubiquitous RF tags” Proceedings of the IEEE Wireless Communications and Networking (WCNC), vol. 3, pp. 2041 - 2046, 2003.
[37] K. Sangani, “RFID sees all,” Proceedings of the IEE Review, pp. 22–24, 2004.
[38] V. Stanford, “Pervasive computing goes the last hundred feet with RFID systems”, Proceedings of the IEEE Pervasive Computing, pp. 9 – 14, 2003.
[39] “First Handheld Bluetooth RFID Reader”, Electronic Devices, 2004. http://www.physorg.com/news1215.html
[40] RFID, Steven Shepard, McGraw-Hill Networking Professional.
[41] L. M. Ni, Y. Liu, Y. C. Lau and A. P. Patil, “LANDMARC: Indoor Location Sensing Using Active RFID”, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, 2003.
[42] F. J. Gonzalez-Castano, J. Garcia-Reinoso, “Bluetooth Location Networks,” Proceedings of the Globecom, 2002.
[43] Bluetooth Nokia. http://www.nokia.com/phones/6210/bluetooth.html.
論文使用權限
  • 不同意紙本論文無償授權給館內讀者為學術之目的重製使用。
  • 同意授權瀏覽/列印電子全文服務,於2009-07-26起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信