臺灣博碩士論文加值系統

藍芽(Bluetooth)是一種新興的短距離無線通訊技術，最初就是為了取代有線連結而發展出來的。在2.4GHz的ISM(Industrial Scientific Medical)頻帶上，以FH(Frequency Hopping)的方式與另一個裝有Bluetooth晶片的裝置建立一個連結。一個藍芽小網路(piconet)裡有一個master及最多七個active Slaves。若空間中的Bluetooth裝置超過八個，就會建構出兩個以上的piconets。piconet可以藉由Bridge device彼此連接在一起，而成為藍芽網路(scatternet)。但是Bluetooth裝置有10公尺的傳輸範圍，在超過傳輸範圍的Bluetooth裝置，就沒辦法跟別的Bluetooth裝置互相通訊。
本篇論文就提出了一個Scalable Bluetooth Scatternet Formation的演算法，讓不在傳輸範圍內的裝置，可以彼此連接在一起。此演算法總共分成兩個階段，第一階段，空間中所有的Bluetooth裝置可以連接到幾棵彼此沒有連接的tree-based scatternets；第二階段就是在這些tree-based scatternets間尋找links，將之連接在一起。經過這兩個階段，就能讓Bluetooth裝置不再受限在10公尺的傳輸範圍。
經由模擬顯示，我們的演算法成形的scatternet具有高連接率、短直徑及number of piconet少的特性。

Bluetooth is a new short-range wireless communication technology. It is developed for cable-requirement. Bluetooth device employs a pseudo-random frequency-hopping scheme to communicate with another Bluetooth device on the unlicensed 2.4Ghz ISM band. . There are one master and up to seven slaves in a piconet. When there are more than eight Bluetooth devices want to connect each other, they must to construct more than two piconets connected via bridge nodes. But the range of the Bluetooth device is 10 meter. If the distance of two Bluetooth devices is more than 10 meter, they can’t communicate each other. This paper proposes a distributed algorithm to form a scatternet spread over a area larger than 10m times 10m. The algorithm has two phases. In Phase 1, each Bluetooth devices located on a tree-based scatternets. After Phase 2, each tree-based scatternet connect to another tree-based scatternets through at most two links. Hence, there is a connected scatternet on area larger than 10m times 10m.
Deducing from the simulation results, the scatternets formed by our algorithm have higher connection ratio, short diameter, short formation time and less number of piconets.

摘要 I
Abstract II
目錄 V
圖表目錄 VII
一、Introduction 1
二、Background 5
三、Relative Works 8
四、Scalable Bluetooth Scatternet Formation Algorithm 13
4.1 建構disjoint tree-based scatternet 14
4.2 在每個disjoint tree-based scatternet間建立連結 23
4.3 Algorithm 25
五、Simulation Results 26
5.1 Phase 1和Phase 2持續時間對connection的影響 27
5.2 Connection ratio的比較 29
5.2.1 比較連結率 29
5.2.2 連結失敗原因分析 30
5.3 Formation time的比較 32
5.4 Piconet個數的比較 34
5.5 Diameter的比較 36
六、Conclusion 38
References 39

[1] The Bluetooth Special Interest Group, http://www.bluetooth.com
[2] Jennifer Bray and F. Charies, “Bluetooth: Connect Without Cables.” Prentice Hall, 2001
[3] Brent A Miller and Chatschik Bisdikian, “Bluetooth Revealed: The Insider’s Guide to an Open Specification for Global Wireless Communications.” Prentice Hall, 2000
[4] GV. Zaruba, S. Basagni, I. Chlamtac, “Bluetrees - Scatternet Formation to Enable Bluetooth-Based Ad Hoc Networks.” Communications, 2001. ICC 2001. IEEE International Conference on , Volume: 1 , 2001. Page(s): 273 —277
[5] T. Salonidis, P. Bhagwat, L. Tassiulas, R. LaMaire, “Distributed Topology Construction of Bluetooth Personal Area Networks.” INFOCOM 2001. Proceedings. IEEE , Volume: 3 , 2001 Page(s): 1577 —1586
[6] Sun Min-Te, Chang Chung-Kuo, Lai Ten-Hwang, “A Self-Routing Topology for Bluetooth Scatternets.” Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Proceedings. International Symposium on , 2002 Page(s): 13 —18
[7] S. Basagni, C. Petrioli, “Multihop Scatternet Formation for Bluetooth Networks.” Vehicular Technology Conference, 2002. VTC Spring 2002
[8] Ching Law, Siu. Kai-Yeung, “Performance of a new bluetooth scatternet formation protocol.” Massachusetts Institute of Technology.林崇智, 張志勇, and 許健平, “A Tree-Based Scatternet Construction Protocol for Improving Performance of Inter-Piconet Communication Service over Bluetooth Radio Systems.” Proceedings of the National Computer Symposium (NSC 2001), Taipei, Taiwan, 2001
[10] Godfrey Tan, Allen Miu, John Guttag and Hari Balakrishnan , “Forming Scatternets from Bluetooth Personal Area Networks.” MIT Laboratory for Computer Science
[11] Z. Wang, R. Thomas, Z. Haas, “Bluenet - A New Scatternet Formation Scheme.” System Sciences, 2001. HICSS. Proceedings of the 35th Annual Hawaii International Conference om, 2002 Pages(s): 779-787
[12] Christoph Bieschke, Garmen Kuhl, “Building Efficient Bluetooth Scatternet Topologies From 1-Factors.” Proceedings of the IASTED international Conference on Wireless and Optical Communications, WOC 2002 Page(s): 300-305, Banff, Alberta, Canada, July 2002
[13] Ivan Stojnebovic, “Dominating set based Bluetooth scatternet formation with localized maintenance.” Parallel and Distributed Processing Symposium. Proceedings International, IPDPS 2002, Page(s): 148-155S Basagni, C. Petrioli, “Degree - Constrained Multihop Scatternet Formation for Bluetooth Networks.” Proceedings of the IEEE Globe