臺灣博碩士論文加值系統

無線網路近年來蔚為風潮。隨著個人化數位產品的普及，無線個人區域網路相關的研究亦逐漸受到重視，藍芽科技便在此時因運而生。一般而言，它能提供在大約十公尺直徑範圍內的無線通訊，同時範圍內的設備可以構成星狀的藍芽微網網路，而不再僅是點對點式的通訊。在超過基本可通訊範圍時，藍芽亦提供了藍芽聯網這樣的方式來讓設備間仍能保持通連。
使用藍芽聯網方式將設備串連時，必須透過適當的路徑選擇方法，來建立起發送者到接收者之間的資料傳送路徑。從既有的許多路徑選擇演算法來看，大部份的方法是以發送者至接收者之間的單向最小延遲時間作為路徑選擇時考慮的主要依據。在考慮到藍芽微網為主導式的網路時，我們發現其在技術特性上與傳統的網路有所不同。加上現實中一些以發送者至接收者間全程延遲為考量的應用愈來愈見其重要性，如資料庫查詢或服務探索等等，因此我們首先證明了在藍芽聯網環境中單向的最小時間延遲並非意味著全程的最小時間延遲，進而以此原則作為路徑選擇的策略，而提出了發送者決定法與接收者決定法兩個新的路徑選擇方法，並與既有的方法進行比較。
在理想無網路壅塞的情況下，我們所提出的方法，不論是在全程的資料傳輸延遲時間，或是路徑建立所需花費的時間，透過分析皆可發現較既有的方法要來的好。這樣的結果，說明了我們所提出的問題確有其研究價值，而研究中所提出的方法，也確有其實際上的價值。至於實際效能的表現為何，則有待後續研究者再接再勵。

Wireless networking related researches are more and more popular today. Personalized digital devices make WPAN(Wireless Personal Area Network) related topics more important, and Bluetooth appears in a result. Generally, Bluetooth can support wireless communications of any two devices within 10 meters, forming a star-topology network, instead of peer to peer communication. Bluetooth also provides scatternets to let any two devices keep connected when their distance is more than 10 meters.
When building connection between devices in the scatternet environment, we have to find the route from the sender to the receiver by some routing algorithm. Most of the existed routing algorithms only take the minimum delay from the sender to the receiver into consideration when selecting the best route for them. We found that Bluetooth piconet is master-driven network, which has some characteristics different from the traditional wired network, i.e. internet. At the same time, we also fount that some real-world applications, such as database queries or look-up services, may concern more about the round-trip delay between the sender and the receiver, instead of the one way minimum delay from the sender to the receiver. So first, we prove that in bluetooth scatternet environment, one way minimum delay does not mean round-trip minimum delay. Then we propose two new approaches, sender decides and receiver decides, which select the best route based on the minimum round-trip delay, and we compare these two approaches with the existed approach.
Both of our approaches are theoretically better than the existed one, no matter in round-trip delay or in route setup time, when taking no network congestion into consideration. Such results show its meanings in both research and practical use. Hoping that the following researchers can test its performance in real-world environment for further study.

謝詞I
論文中文摘要II
Thesis AbstractIII
圖次VI
表次VIII
第一章 緒論........................................1
第一節研究動機.....................................1
第二節研究主題與目的...............................2
第二章 文獻探討....................................4
第一節藍芽(Bluetooth)技術..........................4
2.1.1藍芽的背景[1]................................4
2.1.2藍芽微網(piconet)運作原理[1][2][6][8].......13
第二節需求導向路徑選擇相關研究....................21
2.2.1需求導向路徑選擇............................21
2.2.2最佳路徑選擇考量因素........................23
2.2.3ODMRP(On Demand Multiast Routing Protocol)..24
2.2.4針對藍芽聯網設計的路徑向量法................25
第三章 研究策略...................................28
第一節研究問題....................................28
第二節最適路徑選擇策略............................39
第四章 分析與比較.................................45
第一節最佳路徑之全程延遲時間......................45
第二節最佳路徑之路徑建立時間......................46
第五章 結論與建議.................................47
第六章 未來研究方向...............................49
參考文獻............................................51
簡 歷............................................54

[1]Bluetooth SIG, “Bluetooth Specification Version 1.0B,” http://www.bluetooth.com/
[2]J. Haartsen, “BLUETOOTH — the universal radio interface for ad-hoc, wireless connectivity,” Ericsson Review, No. 3, 1998.
[3]G. Miklos, A. Racz, Z. Turanyi, A. Valko, P. Johansson, “Performance Aspects of Bluetooth Scatternet Formation,” IEEE Mobile and Ad Hoc Networking and Computing, 2000, pp.147-148.
[4]Pravin Bhagwat, Adrian Segall, “A Routing Vector Method (RVM) for Routing in Bluetooth Scatternets,” IEEE Mobile Multimedia Communications, 1999, pp.375-379.
[5]Sung-Ju Lee, “Routing and Multicasting Strategies in Wireless Mobile Ad hoc networks”, Doctor Thesis, Dep. of Computer Sciense of UCLA, 2000.
[6]James Kardach, “Bluetooth Architecture Overview, ”Intel Technology Journal, Q2, 2000.
[7]J. Haartsen, M. Naghshineh, J. Inouye, ”Bluetooth: Vision, Goals, and Architecture”, IEEE Mobile Computing and Communications Review, No. 2, Vol. 1, 1999.
[8]J. Haatsen, “The Bluetooth Radio System,” IEEE Personal Communications, February 2000, pp.28-36.
[9]C.E.Perkins and E.M. Royer, “Ad-Hoc On Demand Distance Vector Routing,” Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), New Orleans, LA, February 1999, pp. 90-100.
[10]C.E.Perkins, E.M. Royer, and S.R.Das, “Ad Hoc On Demand Distance Vector (AODV) Routing,” Internet Draft, draft-ietf-manet-aodv-05.txt, March 2000, Work in progress.
[11]C.-K. Toh, “Associativity-Based Routing for Ad-Hoc Mobile Networks,” Wireless Personal Communications Journal, special issue on Mobile Networking and Computer Systems, Kluwer Academic Publishers, vol. 4, no. 2, March 1997, pp.103-139.
[12]Sung-Ju Lee and Mario Gerla, “AODV-BR: Backup Routing in Ad Hoc Networks,” Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Chicago, IL, September 2000.
[13]Sung-Ju Lee, Mario Gerla, and Ching-Chuan Chiang, “On-Demand Multicast Routing Protocol,” Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, LA, September 1999, pp1298-1032.
[14]Sung-Ju Lee, William Su, and Mario Gerla, “On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks,” IETF Internet Draft, draft-ietf-manet-odmrp-02.txt, January 2000, Work in progress.
[15]D.B.Johnson and D.A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” In Mobile Computing, edited by Tomasz Imielinski and Hank Korth, Chpater 5, Kluwer Academic Publishers, 1996, pp. 153-181.
[16]D.A. Maltz, J.Broch, J.Jetcheva, and D.B.Johnson, “The Effects of On-Demand Behavior in Routing Protocols for Multihop Wireless Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications, special issue on Wireless Ad Hoc Networks, vol. 17, no. 8, August 1999, pp. 1439-1453.
[17]Y.-B. Ko and N.H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Dallas, TX, October 1998, pp. 66-75.
[18]S.Corson and J.Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” IETF RFC 2501, January 1999.
[19]S.Basagni, I.Chlamtac, V.R.Syrotiuk, and B.A.Woodward, “A Distance Routing Effect Algorithm for Mobility (DREAM),” Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), Dallas, TX, October 1998, pp. 76-84.