臺灣博碩士論文加值系統

在這篇論文中，我們提出了一個二種階段最佳化重組演算法來減少在藍芽(Bluetooth)無線網路環境之中，跨越piconet通訊所增加的通訊成本。首先針對在一個通訊會期(session)之中，各個程式之間的相互存取關係(access pattern)來建立一個訊息成本模型。
這個模型的參數取得，是經由剖析(profiling)所產生。由於藍芽實作規範上的範制，在同一個piconet之內，無法同時容納太多的通訊裝置，這使得跨piconet時的訊息傳輸成本變得異常昂貴。另一方面，裝置和裝置之間的通訊成本，是由二點之間所跨越的通訊節點數的多寡所決定。利用這些特性和限制，我們採用二分拓樸(bipartite topology)的網路連結型態來作為一開始的scatternet，再對此scattenet，做切割以及重組的動作。在傳統的圖論研究裡，圖型分割(graph partitioning)的技巧可以用來幫助區別那一個裝置或節點應該被置放於那一個群組(cluster)之中。因此，依據各個裝置之間的通訊成本，利用遞迴切割(recursive
graph partitioning)的方式切割出適當的群組，每一個群組對應著一個piconet，再經由Kernighan-Lin的演算法，對分配不均的群組做修正，使得每個群組之間的大小都相同。最後，我們必須在這些大小相同的群組(balanced clusters)之間建立連結，來形成最後的通訊網路。
這個步驟可以使用圖論之中的加權二分匹配(weighted bipartite matching)的方式來賦予每個裝置所應擔任的角色。經由這些步驟所形成的scatternet，確保經常通訊或有著高通訊成本的裝
置，將被組在同一個piconet之內，以降低整個scatternet的訊息成本。
論文的實驗主要建立在一連串的模擬和調整不同的參數來觀察scatternet通訊成本的改變。在所有的變數均為均勻分佈(uniform distribution)時，使用最佳化重組演算法可以降低大約13%的通訊成本；另一方面，若程式之間的通訊方式，具備著某種特殊的群組關係，而在初始時形成的
scatternet之中，卻未將這些裝置以同一個piconet連接，在這種情況之下，可以改善的幅度更為可觀。在現今大多數的分散式計算環境之中，例如使用Java遠端程序呼叫(RMI)，我們所提出的方法可以有效的減少程式在進行訊息交換或通訊時所造成的通訊成本。這種結果對於在欲在藍芽無線網路之中，建立分散式計算的環境而言，是很有幫助的。

In this thesis, we describe a two-phase approach for cost
reduction on Bluetooth inter-piconet communication. A cost model
is established on the access pattern of bluetooth devices during a communication session, which performs a profiling mechanism. Due to the physical limits on Bluetooth specifications, inter-piconet communications are cost expensive, and we can not put lots of nodes in the same piconet. The end-to-end message cost between each node pair is determined by the number of hops on nodes. We apply a bipartite topology manner for constructing a initial scatternet and reconstructing the initial one. Traditional graph partitioning scheme is used to help us to distinguish what nodes should be grouped to a cluster. We adopt a recursive graph bisection method and KL refinement procedure to achieve nodes grouping using access frequency. These balanced clusters have to connect by the role of nodes for forming the last scatternet topology. Applying weighted bipartite matching method to assign the appropriate node attributes with the result that we configure a low message cost scatternet.
Our experiments are performed on simulating the variation of total message cost in adjusting diverse parameters. In variables with uniform distribution, we improve the original cost about 13%. If choosing a test set which owns natural group property, we can obtain the better improvements. In a distributed computing model such as Java RMI, our works can greatly enhance the transmission cost between method invocations. This facilitates the distributed computation applications to implement on Bluetooth environment.

Contents
Acknowledgements i
Abstract ii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Bluetooth enabling technology 5
2.1 Bluetooth overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Bluetooth protocol stack . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Hardware protocol . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Host Control Interface . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Software protocol . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Topology and Interpiconet communication 14
3.1 Piconet Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Scatternet Formation . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Inter-piconet communication . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Problem descriptions and models . . . . . . . . . . . . . . . . . . . . 22
3.4.1 Communication delays of scatternet . . . . . . . . . . . . . . . 22
3.4.2 Packets routing on scatternet . . . . . . . . . . . . . . . . . . 25
4 Device regrouping and scatternet formation 27
4.1 Message cost of end-to-end communication . . . . . . . . . . . . . . . 27
4.2 Recursive spectral bisection and clustering . . . . . . . . . . . . . . . 29
4.3 Building connections between clusters and forming scatternet . . . . . 31
4.4 Case study: reconfiguring a two-piconet scatternet . . . . . . . . . . . 33
5 Experiments and Discussions 38
6 Conclusions and related works 44

[1] A. Racz, G. Miklos, F. Kubinszky and A. Valko, “A pseudo random coordinated scheduling algorithm for Bluetooth scatternets ”, Proceedings of the 2001 ACM International Symposium on Mobile ad hoc networking and computing, 2001, pp.
193-203.
[2] Alex Pothen, “Graph Partitioning Algorithms with Applications to Scientific Computing”, Technical Report, Old Dominion University, 1997.
[3] B. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs”, Bell System Technical Journal, 1970, pp. 291-307.
[4] Bluetooth Special Interest Group, Specification of the Bluetooth System, version 1.1, volumes 1, 2, and profiles, Feb 2001.
[5] Bluetooth Special Interest Group, An Overview of Bluetooth Qualification, http://qualweb.opengroup.org/Template2.cfm, Feb 2001.
[6] Brent A. Miller and Chatschik Bidsdikian, Bluetooth Revealed, Prentice Hall, 2001.
[7] Bruce Hendrickson and Robert Leland, The Chaco User’s Guide, Sandia Na-tional Laboratories, 1995.
[8] D. Kammer, G. McNutt, B. Senese, and J. Bray, Bluetooth Application Developer's Guide, Syngress Publishing, 2002.
[9] ETSI Technical Specicfication 07.10 , http://webapp.etsi.org/pda/.
[10] Bruce Hendrickson and Robert Leland, “An improved spectral graph partition-ing algorithm for mapping parallel computations”, SIAM Journal on Scientific Computing, 16(2), 1995, pp. 452—469.
[11] Bruce Hendrickson and Robert Leland, “Multidimensional Spectral Load Bal-ancing”, Technical Report, Sandia National Laboratories, 1993.
[12] Ching Law and Kai-Yeung Siu, “A bluetooth scatternet formation algorithm”, Global Telecommunications Conference, 2001.
[13] Douglas B. West, Introduction to Graph Theory, Prentice Hall, 2001.
[14] F. Rendl and H. Wolkowicz, “A projection technique for partitioning the nodes of a graph”, Technical Report, University of Waterloo, Canada, 1995.
[15] G. Miklos, A. Racz, Z. Turanyi, A. Valko, and P. Johansson, “Performance aspects of Bluetooth scatternet formation ”, First Annual Workshop on Mobile
and Ad Hoc Networking and Computing, 2000, pp. 147-148.
[16] G. V. Zaruba, S. Basagni and I.Chlamtac, “Bluetrees-scatternet formation to enable Bluetooth-based ad hoc networks ”, IEEE International Conference on
Communications, 2001, pp. 273-277.
[17] HomeRF official website, http://www.homerf.org/.
[18] IEEE 802.15 WPAN Task Group 1(TG1),
http://grouper.ieee.org/groups/802/15/pub/TG1.html, Mar, 2002.
[19] Infrared Data Association, http://www.irda.org/standards/specifications.asp.
[20] Ian Foster, Designing and Building Parallel Programs, Addison Wesley, 1994.
[21] Jennifer Bray and Charles F. Sturman, Bluetooth Connect Without Cables, Pren-tice Hall, 2001.
[22] Liron Har-Shai, Ronen Kofman, and Gil Zussman, “Routing in BlueTooth ScatterNet”, in Bluetooth ScatterNet Performance Simulator available at http://comnet.technion.ac.il/ cn18s01/.
[23] Manish Kalia, Sumit Garg, and Rajeev Shorey “Scatternet Structure and Inter-Piconet Communication in the Bluetooth System ”, IEEE National Conference on Communications, 2000.
[24] Marcin Michalak, “Multimedia transmission in Bluetooth-based networks”, Master of Science Thesis, University of Mining and Metallurgy, Porland, 2001.
[25] P. Bhagwat and S. P. Rao, “On the Characterization of Bluetooth Scatternet Topologies ”, Submitted for publication, Oct, 2001.
[26] Pravin Bhagwat and Adrian Segall, “A routing vector method (RVM) for routing in Bluetooth scatternets ”, IEEE International Workshop on Mobile Multimedia Communications, 1999, pp. 375-379.
[27] R. Bruno, M. Conti and E. Gregori, “Wireless Access to Internet via Bluetooth: Performance Evaluation of the EDC Scheduling Algorithm”, Proceedings of ACM WMI, July, 2001.
[28] S. Baatz, M. Frank, C. Kah, P. Martini and C. Scholz, “Adaptive scatternet support for bluctooth using sniff mode ”, Proceedingsof 26th Annual IEEE Con-ference,
2001, pp. 112-120.
[29] Sun Microsystems Inc., Java Remote Method Invocation,
http://java.sun.com/products/jdk/rmi/.
[30] T. Salonidis, P. Bhagwat, L. Tassiulas, and R. LaMaire, “Proximity Awareness and Ad Hoc Network Establishment in Bluetooth”, Technical Report, CSHCN, Center for Satellite and Hybrid Communication Networks, 2001.
[31] T. Salonidis, P. Bhagwat, L. Tassiulas and R. LaMaire, “Distributed topology construction of Bluetooth personal area networks ”, Proceedings of the 20th annual Joint Conference of the IEEE Computer and Communications Societies, 2001.
[32] Wireless Standard Package(802.11), this package is made available at http://shop.ieee.org/store.