臺灣博碩士論文加值系統

無線網路是一種在行動裝置上很受歡迎的媒介。藍芽技術也是一種在行動網路的一種媒介。藍芽技術是一種短距離的無線通信技術，它提供了多種資料傳送率，多種封包類型，低功率運作而且對安全通信的支持。因此，藍芽技術在近年蓬勃地發展。而藍芽的散網形成是被討論的重要問題之一，但是卻沒有在藍芽系統的規格書上面所說明。

在這篇文章裡，我們提出一個新的基於樹狀結構的動態可自我修復藍芽散網形成演算法，稱作可調適的五元樹散網形成演算法。這個方法克服一些早期研究所產生的缺點。它是一種可以遠距傳輸且適合處理節點動態的加入與離開的一種方法。為了避免散網產生迴圈而違背樹狀架構，我們採用一個旗標當做樹的編號解決這個問題。另外，我們為了達成散網擁有更高的連接性，使得在微網之間交流能更有效率，透過降低散網形成的時間並且降低微網在散網中的數量。此方法擁有自我修復的能力，可以在任何時刻避免節點發生錯誤或是有連結斷開並且有效的解決，更由於有偵測和修復的功能而保證資料傳輸。

Wireless LAN is a popular medium to be used for mobile networks. It is also promising to use Bluetooth as a medium for mobile ad hoc networks. Bluetooth is a short range wireless communication technology that offers multiple data transfer rates, multiple packet types, low power operation and support for secure communications. Hence, Bluetooth technology is vigorously developed in recent years. Scatternet formation scheme is one of important issues, which is not specified in the specifications of the Bluetooth system.

In this thesis, we proposed a novel scatternet formation algorithm with self-healing capability based on tree structure called Adaptive Five-ary tree scatternet formation (AFTSF). AFTSF overcomes several of earlier work shortcomings. AFTSF is a multi-hop dynamic environment where nodes may arrive and leave arbitrarily. In order to avoid producing loops, which is going against tree structure, we adopt a tree number flag to solve this problem. In addition, our scheme tends to form a scatternet with higher connectivity, communicating between piconets is more efficient, reducing the scatternet formation time and decreasing the number of piconets in the scatternet whenever as possible and AFTSF with self-healing capability which solves the node failed or link disconnected problem. It detects the links between nodes, and assures the data transmission.

Chapter 1 Introduction 1
Chapter 2 Bluetooth overview 4
2.1 Physical Channel 7
2.1.1 Basic Piconet Channel 8
2.1.2 Inquiry Scan Channel 9
2.1.3 Page Scan Channel 10
2.2 Physical Links 11
2.3 Logical Layer 12
2.4 L2CAP Layer 13
Chapter 3 Related Work 14
3.1 Centralized Scatternet Formation algorithm 14
3.2 Distributed Scatternet Formation algorithm 15
3.2.1 Tree Scatternet Formation Scheme (TSF) 16
3.2.2 SHAPER Scheme 17
3.2.3 DMSFA Scheme 19
Chapter 4 Proposed schemes 21
4.1 Motivation and problem definition 21
4.1.1 Motivation 21
4.1.2 Problem definition 21
4.2 The characteristics of the scatternet 22
4.3 Adaptive Five-ary tree scatternet formation (AFTSF) algorithm 23
4.3.1 Scatternet formation algorithm 23
4.3.2 Self-healing algorithm 32
Chapter 5 Performance Evaluation 37
5.1 The Metrics for Performance Evaluation 37
5.2 Assumptions and Parameter setting 38
5.3 Simulation Results and Analysis 39
Chapter 6 Conclusions 45
Bibliography 46

[1]Bluetooth SIG, http://www.bluetooth.com.
[2]J. Haartsen, “The Bluetooth Radio System,” IEEE Personal Communications, vol. 7(1), pp. 28–36, Feb 2000.
[3]T. Salonidis, P. Bhagwat, L. Tassiulas, and R. LaMaire, “Distributed topology construction of Bluetooth personal area networks,” IEEE INFOCOM 2001, Anchorage, Alaska, vol. 3, pp. 1577–1586, April 2001.
[4]S. Baatz, C. Bieschke, M. Frank, C. Kuhl, P. Martini, and C. Scholz, “Building Efficient Bluetooth Scatternet Topologies from 1-Factors,” Proceedings of the IASTED International Conference on Wireless and Optical Communications, WOC 2002, Banff, Alberta, Canada, pp. 300– 305, July 2002.
[5]G. Tan, A. Miu, J. Guttag, and H. Balakrishnan, “Forming Scatternets from Bluetooth Personal Area Networks,” MIT Technical Report, no. MIT-LCS-TR-826, October 2001.
[6]G. Zaruba, S. Basagni, and I. Chlamtac, “Bluetrees - Scatternet formation to enable Bluetooth-based ad hoc networks,” IEEE ICC 2001, Helsinki, Finland, vol. 1, pp. 273–277, June 2001.
[7]C. Petrioli and S. Basagni, “Degree-Constrained Multihop Scatternet Formation for Bluetooth Networks,” Proceedings of IEEE Globecom, 2002, Taipei, Taiwan, R.O.C., vol. I, pp. 222–226, November 2002.
[8]T. Salonidis, P. Bhagwat, and L. Tassiulas, “Proximity awareness and fast connection establishment in Bluetooth,” Mobile and Ad Hoc Networking and Computing, pp. 141–142, 2000.
[9]C. C. Foo and K. C. Chua, “BlueRings - Bluetooth scatternets with ring structures,” IASTED International Conference on Wireless and Optical Communication (WOC 2002), Banff, Canada, July 17-19 2002.
[10]M. A. Marsan, C. F. Chiasserini, A. Nucci, G. Carello, and L. D. Giovanni, “Optimizing the topology of Bluetooth wireless personal area networks,” Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings.IEEE INFOCOM 2002, vol. 2, pp. 572–579, June 2002.
[11]T.-Y. Lin, Y.-C. Tseng, and K.-M. Chang, “Formation, Routing, and Maintenance Protocols for the BlueRing Scatternet of Bluetooth,” 36th Hawaii Intl Conf. on System Sciences (HICSS) - Track 9, p. 313a, January 2003.
[12]G. Tan, A. Miu, J. Guttag, and H. Balakrishnan, “An Efficient Scatternet Formation Algorithm for Dynamic Environments,” IASTED Communications and Computer Networks (CCN), Cambridge, MA, no. 0-88986- 329-6, November 2002.
[13]F. Cuomo, G Di Bacco, T. KMelodia, “Shaper: a self-healing algorithm producing multi-hop Bluetooth scatternets, “ 2003 IEEE GLOBECOM ’03 Volume: 1, 1-5 Dec. 2003. pp 236-240
[14]R. He, X. Fang “A scatternet formation algorithm for dynamic multi-hop environments” Proceedings.IEEE INFOCOM 2005, Volume 1, 27-30 May 2005 pp 388 - 391
[15]G. Tan, “Self-organizing Bluetooth Scatternets,” SM Thesis, Massachusetts Institute of Technology, January 2002.
[16]S. Basagni and C. Petrioli, “A Scatternet Formation Protocol for Ad hoc Networks of Bluetooth Devices,” IEEE Vehicular Technology Conference, vol. 1, pp. 424–428, Spring 2002.
[17]J. Yun, J. Kim, Y.-S. Kim, and J. Ma, “A Three-Phase Ad Hoc Network Formation Protocol for Bluetooth Systems,” Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications(WPMC) 2002, Hawaii, October 2002.
[18]I. Stojmenovic, “Dominating set based Bluetooth scatternet formation with localized maintenance,” Proceedings of the Workshop on Advances in Parallel and Distributed Computational Models, Fort Lauderdale, FL, p. 148b, April 2002.
[19]M. S. Rohit Kapoor and M. Gerla, “An Analysis of Bluetooth Scatternet Topologies,” ICC 2003, Anchorage, Alaska, vol. 1, pp. 266 –270, May 2003.
[20]G. Tan, “Blueware: Bluetooth Simulator for ns”, MIT Laboratory for Computer Science, Cambridge, October 2002