臺灣博碩士論文加值系統

　　藍芽是一種新穎的無線通訊技術，在我們生活週遭都可以發現藍芽裝置的存在。而由這些裝置所組成的通訊網路，我們稱為藍芽散射網，它包含Master、Slave及Bridge三種角色。在藍芽散射網路中，Master與Bridge往往都是整個網路流量的瓶頸點所在。因此，如何去衡量藍芽散射網的效能是一個相當重要的問題。雖然Zussman與Segall兩位學者曾提出藍芽散射網容量分派與效能衡量的解決方案，但他們的方法忽略了藍芽節點角色的影響因素。這使得在他們所建議的方法被我們發現對於相同拓撲但含有不同角色的散射網路存在著無法識別其效能程度的問題。在本篇論文，我們提出了一個針對Bridge角色加權的方法來解決這個問題。我們的方法評估節點角色對容量分派的影響，並能夠被用於精確地評估一個散射網的形態。它有助於我們在不改變拓樸結構下，藉由改變節點角色來得到更好的散射網。在本論文的第27頁中，我們使用例子實際說明我們所建議的方法。我們證明了啓發式的方法並不能夠區別這些例子的不同，而在Table 5 5中證明了我們所提議能夠有效的解決這個問題，並符合藍芽網路的特性。

Bluetooth is a novel wireless communication technology, its devices found everywhere. A Bluetooth scatternet made up these devices consists of three roles: master, slave, and bridge. In Bluetooth environments, masters and bridges nodes are usually the bottleneck of data traffic flows in scatternet. Therefore, how to evaluate the formation of scatternet is one of important issues. Although Zussman and Segall have provided a solution for capacity assignment problems in Bluetooth scatternets, they do not consider the factor of roles to impact the performance of scatternet. It was found that undiscriminating problems exist in their proposed solution. In this thesis, we propose a novel weight-based scheme for bridge nodes to solve this problem, which provides a more complete solution for capacity assignment to prevent the undiscriminating problem. Our scheme estimates the influences of nodes’ role for capacity assignment, and can be used to accurately appraise the performance of scatternet formation. It can assist us in identifying a better scatternet via modifying the nodes’ role without changing the scatternets’ topology. For implementation, we show our proposed scheme by some example, as shown in page 27. We have proved that the proposed heuristic scheme really cannot to identify the differences of same topology with difference roles for examples, but our proposed scheme can solve this problem, as shown in Table 5 5. However, our scheme is proven to be effective and conforms to Bluetooth network’s features.

摘要 i
Abstract ii
Table of Contents iii
List of Figures iv
List of Tables vi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Overview of the Research 3
1.3 The Organization of Thesis 3
Chapter 2 Related Work 5
2.1 Bluetooth Scatternet Formation 7
2.1.1 Tree-based Scatternet 7
2.1.2 Ring-based Scatternet 9
2.1.3 Mesh-based Scatternet 10
2.2 Capacity Assignment Algorithm 11
Chapter 3 System Model 14
3.1 Model and Preliminaries 14
3.2 The problem of heuristic capacity assignment method 18
Chapter 4 Role-weighted Scheme 20
4.1 The weighted variable for S/S Bridge 21
4.2 The weighted variable for M/S Bridge 23
Chapter 5 Implement the Role-weighted scheme 27
5.1 Centralized Assigned Method 27
5.2 Distributed Assigned Method 42
Chapter 6 Conclusions 48
Reference 49

[1]S. Baatz, M. Frank, C. Kühl, P. Martini, and C. Scholz, “Adaptive scatternet support for Bluetooth using sniff mode,” in Proceedings of 26th Annual IEEE Conference on Local Computer Networks(LCN), Tampa, Florida, USA, pp. 112–120, Nov. 2001.
[2]S. Baatz, M. Frank, C. Kühl, P. Martini, and C. Scholz, “Bluetooth scatternets: An enhanced adaptive scheduling scheme,” in Proceedings of 21st Annual Joint Conference of the IEEE Computer and Communications Societies( INFOCOM), New York, USA, pp. 782–790, Jun. 2002.
[3]S. Basagni, R. Bruno, and C. Petrioli, “Performance Evaluation of A New Scatternet Formation Protocol for Multi-hop Bluetooth Networks,” in Proceedings of the 5th International Symposium on Wireless Personal Multimedia Communications, Honolulu, Hawaii, USA, pp. 208-212, 2002.
[4]C. C. Foo and K. C. Chua, “BlueRings - Bluetooth Scatternets with Ring Structures,” in Proceedings of IASTED International Conference on Wireless and Optical Communication (WOC), Banff, Alberta, Canada, Jul. 2002.
[5]T. C. Huang, C. S. Yang, C. C. Huang, and S. W. Bai, “Hierarchical Grown Bluetrees (HGB) - An Effective Topology for Bluetooth Scatternets,” in Proceedings of International Symposium on Parallel and Distributed Processing and Applications (ISPA), Aizu-Wakamatsu, Japan, pp. 152-164, Jul. 2003.
[6]T. Y. Lin, Y. C. Tseng, K. M. Chang, and C. L. Tu, “Formation, Routing, and Maintenance Protocols for the BlueRing Scatternet of Bluetooths,” in Proceedings of the 36th Annual Hawaii International Conference on System Sciences, pp. 10, Jan. 2003.
[7]J. Miˇsic´ and V. B. Miˇsic´, “Bridges of Bluetooth County: Topologies, Scheduling, and Performance,” IEEE Journal of Selected Areas in Communications, Vol. 21, Issus 2, pp. 240-258, 2003.
[8]V. B. Mišic´ and J. Mišic´, “Performance of Bluetooth Bridges in Scatternets with Limited Service Scheduling,” Mobile Networks and Applications, Vol. 9, Issus 1, pp. 73-87, 2004.
[9]C. Petrioli, S. Basagni, and I. Chlamtac, “BlueMesh: Degree-constrained Multihop Scatternet Formation for Bluetooth Networks,” ACM/Kluwer Journal on Mobile Networks and Applications, Vol. 9, Issue 1, pp. 33-47, Feb. 2004.
[10]M. T. Sun, C. K. Chang, and T. H. Lai, “A self routing topology for Bluetooth scatternets,” in Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN), Manila, Philippines, pp. 17-23, May 2002.
[11]T. Salonidis, P. Bhagwat, L. Tassiulas, and R. LaMaire, “Distributed Topology Construction of Bluetooth Personal Area Networks,” in Proceedings of IEEE INFOCOM, Anchorage, AK, USA, pp. 1577-1586, Apr. 2001.
[12]S. Sunkavai and B. Rarnalmurthy, “MTSF: A Fast Mesh Scatternet Formation Algorithm for Bluetooth Nnetworks,” in Proceedings of IEEE Global Telecommunications Conference, Vol. 6, pp. 3594-3598, Nov. 2004.
[13]G. Tan, A. Miu, J. Guttag and H. Balakrishnan, “An Efficient Scatternet Formation Algorithm for Dynamic Environments,” in Proceedings of IASTED Communications and Computer Networks (CCN), Cambridge Mass, USA, Nov. 2002.
[14]J. Zhang and W. K. G Seah, “Topology-based Capacity Analysis for Ad Hoc Networks with End-to-End Delay Constraints,” in Proceedings of the IEEE 6th CAS Symposium on Emerging Technologies: Frontiers of Mobile and Wireless Communication, Shanghai, CN, pp. 541-544, 2004.
[15]G. V. Zaruba, S. Basagni, and I. Chlamtac, “Bluetrees - Scatternet Formation to Enable Bluetooth-based Ad Hoc Networks,” in Proceedings of IEEE International Conference on Communications, Vol. 1, pp. 273-277, Jun. 2001.
[16]G. Zussman and A. Segall, “Capacity Assignment in Bluetooth Scatternets – Optimal and Heuristic Algorithms,” Mobile Networks and Applications, Vol. 9, Issus 1, pp. 49-61, 2004.
[17]W. Zhifang, R. J. Thomas, and Z. Haas, “Bluenet - A New Scatternet Formation Scheme,” in Proceedings of the 35th Annual Hawaii International Conference on System Sciences, pp. 7-10, Jan. 2002.
[18]L. Kleinrock, Communication Nets: Stochastic Message Flow and Delay. New York: McGraw-Hill, 1964.
[19]G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. New York: Wiley, 1988.
[20]Bluetooth Specification URL:
http://bluetooth.com/Bluetooth/Learn/Technology/Specifications/