臺灣博碩士論文加值系統

在Bluetooth的規範下，藍芽分散網的拓璞形成，樹狀的藍芽樹算是常見到的一種形成方法.。在藍芽樹的拓璞結構下, Link scheduling 與 packet routing 是比其他拓璞結構來的容易管理與控制。在這篇文章裡，我們提出了一個分散式的方法，藉由各點不同的traffic負載，來改善整體的樹狀結構。在這裡我們利用了藍芽微網的移動觀念，來改善traffic負載，首先，經由各微網之間的traffic，來判別各點較佳的位置，也利用了”樹的拜訪”此技術，來尋找最後的各點的位置，最後再形成比原本更好的拓璞結構。跟先前的方法相比較，本篇有更少的計算時間和scalability，最後，模擬結果也呈現出不錯的結果。

In scatternet formation, Bluetree is one commonly formed topology. With the Bluetree topology, the link scheduling and packet routing become easy in a scatternet. In this thesis, we propose a distributed approach to improving the Bluetree formation by taking the traffic load into account. In the proposed approach, we utilize the piconet transfer concept to reduce the traffic load of a well-formed Bluetree. First, each piconet uses its traffic load with other piconets to find its preferable location on the Bluetree. The tree traversal technique is used to assist the preferable location determination. Then, the well-formed Bluetree is reconstructed by moving each piconet to its preferable location. Compared to previous approaches, the proposed approach can take less computation time and has better scalability in the number of traffic flows to be handled. Finally, simulation experiments are performed to show the effectiveness of the proposed approach in improving the Bluetree scatternet formation.

Chapter 1. Interdiction....................................................................................................1
Chapter 2. Preliminaries.................................................................................................3
2.1 Tree Traversal..............................................................................................................3
2.2 Related Work...............................................................................................................3
Chapter 3. Proposed Approach.......................................................................................6
3.1 Basic Idea..........................................................................................................6
3.2 Detailed Operations.................................................................................................10
3.2.1 The First Problem...........................................................................................10
3.2.2 The Second Problem.......................................................................................11
3.2.3 The Third and Fourth Problems......................................................................12
3.2.3.1 The Up Movement...............................................................................13
3.2.3.2 The Down Movement..........................................................................18
3.3 Time Complexity...............................................................................................22
Chapter 4. Simulation Evaluation........................................................................................26
4.1 Simulation Settings................................................................................................26
4.2 Simulation Results.............................................................................................27
Chapter 5. Conclusions.................................................................................................35
References.......................................................................................................................36

[1] Bluetooth, Bluetooth Special Interest Group, 2006, http://www.bluetooth.com.
[2] P. McDermott-Wells, “What is Bluetooth?,” IEEE Potentials, Vol. 23, Issue 5, pp. 33 – 35, Dec. 2004-Jan. 2005.
[3] K.E. Persson, D. Manivannan, M. Singhal, “Bluetooth scatternets: criteria, models and classification,” Ad Hoc Networks, Vol. 3, Issue 6, pp. 777-794, Nov. 2005, In press, available at: www.sciencedirect.com.
[4] P. McDermott-Wells, “Bluetooth scatternet models,” IEEE Potential, Vol. 23, Issue 5, pp. 36 – 39, Dec. 2004-Jan. 2005.
[5] Roger M. Whitaker, Leigh Hodge, Imrich Chlamtac,” Bluetooth scatternet formation: A survey,” Ad Hoc Networks, Vol. 3, Issue 4, pp.403-450, Jul. 2005.
[6] G. Tan, A. Miu, J. Guttag and H. Balakrishnan, “An Efficient Scatternet Formation Algorithm for Dynamic Environments,” Proc. IASTED Comm. and Computer Networks (CCN), Nov. 2002.
[7] F. Cuomo, G. D. Bacco, T. Melodia, “SHAPER: a self-healing algorithm producing multi-hop Bluetooth scatternets,” IEEE GLOBECOM., Vol.1, 1-5, pp. 236 - 240 , Dec. 2003.
[8] M. Tekkalmaz, H. Sozer, I. Korpeoglu, “Distributed Construction and Maintenance of
Bandwidth and Energy Efficient Bluetooth Scatternets,” IEEE Tran. Parallel and Distributed Systems, Vol. 17, Issue 9, pp. 963 – 974, Sept. 2006.
[9] C. Y. Chang, C. T. Chang, ”TARP: A traffic-aware restructuring protocol for Bluetooth radio networks,” Computer Networks, Vol. 51, Issue 14, pp. 4070-4091, Oct. 2007, In press, available at: www.sciencedirect.com.
[10] G.-J. Yu, C.-Y. Chang. ”Congestion control of bluetooth radio system by piconet restructuring,” Journal of Network and Computer Appl., Vol. 31, Issue 3, pp. 201-223, Aug. 2008, In press, available at: www.sciencedirect.com.
[11] K. P. Shih, S. S. Wang, and J. H. Su, "A Bluetooth Group-scatternet Formation Algorithm for Efficient Routing," in Proceedings International Conference on Parallel Processing Workshops, pp. 50-56, Oct. 2003.
[12] C. Y. Chang, K. P. Shih, and S. C. Lee, C. H. Tseng, "Adaptive Role Switching Protocols for Improving Scatternet Performance in Bluetooth Radio Networks," The 15th IEEE International Symposium on PIMRC 2004, Vol. 1, 5-8, pp.375 – 379, Sept. 2004.
[13] G.-J. Yu, C.-Y. Chang, K.-P. Shih, S.-C. Lee, “Relay reduction and disjoint routes construction for scatternet over Bluetooth radio system,” Journal of Network and Computer Appl., Vol. 30, Issue 2, pp.728-749, Apr. 2007.
[14] C. Law, A.K. Mehta, and K.Y. Siu, “A New Bluetooth Scatternet Formation Protocol”, Mobile Networks and Applications, Vol.8, pp.485-498, 2003.
[15] D. S. Malik, P. S. Nair, “Data Structures Using Java, “ THOMSON, Inc. Publication, 2003.
[16] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein,” Introduction to Algorithms,” 2001.
[17] Y. Liu, M. J. Lee, T. N. Saadawi, “A Bluetooth scatternet-route structure for multihop ad hoc networks,” IEEE Jour. Selected Areas in Comm., Vol. 21, Issue 2, pp. 229 – 239, Feb. 2003.
[18] T. Salonidis, P. Bhagwat, L. Tassiulas, R. LaMaire,” Distributed topology construction of Bluetooth wireless personal area networks,” IEEE Jour. selected Areas in Comm., Vol. 23, Issue 3, pp. 633 - 643, Mar. 2005.
[19] T.-Y. Lin, Y.-C. Tseng, K.-M. Chang, C.-L. Tu, “Formation, Routing, and Maintenance Protocols for the BlueRing Scatternet of Bluetooths,” Proc. 36th Annua Hawaii Int’l Conf. System Sciences 6-9, pp.10, Jan. 2003.
[20] C. Petrioli, S. Basagni, M. Chlamtac, ”Configuring BlueStars: Multihop Scatternet Formation for Bluetooth Networks,” IEEE Tran. Computers, Vol. 52, Issue 6, pp.779 – 790. Jun. 2003.
[21] V.P. Verma, A.A. Chandak, ”Distributed Bluetooth Scatternet Formation Algorithm,” IEEE GLOBECOM '03, Vol. 3, 1-5, pp.1274 – 1278, Dec. 2003.
[22] S. Basagni, R. Bruno, G. Mambrini, and C. Petrioli," Comparative performance evaluation of scatternet formation protocols for networks of Bluetooth devices," Wireless Networks, vol. 10, no. 2, pp. 197-213, Mar. 2004.
[23] F. Cuomo, G. D. Bacco, and T. Melodia, "Optimized Scatternet Topologies for Personal Area Networking in Dynamic Environments," IEEE International Conf. on Comm., Vol. 6, pp. 3696-3700, Jun. 2004.
[24] M. Medidi, J. Campbell, ”Energy-Efficient Bounded-diameter Tree Scatternet for Bluetooth PANs,” 30th Anniversary IEEE Conf. Local Computer Networks, pp. 268 – 275, Nov. 2005.
[25] W. Heinzelman, A. Chandrakasan, H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” Proc. Hawaii Int’l Conf. System Sciences, 2000.