臺灣博碩士論文加值系統

近年來，藍芽技術的發展逐漸成為目前無線網路市場中最熱門的一項議題，藍芽主要將用途鎖定在短距離個人區域網路 (PAN, Personal Area Network)上，以跳頻展頻的方式，由Master端主導整個Piconet的封包傳輸排程。在目前的藍芽規格中，MAC層使用Round Robin的方式輪流對各個Slave進行資料傳輸。由於無法預知Slave端的佇列狀態，造成頻寬使用效率不佳以及封包在進行傳輸前的等待時間延長等缺點。為了有效解決上述的問題，本研究提出一種預知Slave封包大小的方法，並且在此前提下導入最短先做演算法(SJF, Shortest Job First)的排程方式，提出一SPF(Shortest Packet First)的封包排程機制。經由平均等待時間的模擬實驗，可以證明本研究所提出的方法的確有效改進RR演算法所造成的問題。

Computing and communication anytime, anywhere is an emerging issue in the network technology. People would like to access information services or the Internet while they are moving frequently in an outdoor open environment. Besides, the concept of the Person Area Network (PAN) was proposed to facilitate our daily life that digital devices interconnect and coordinate to provide various human- friendly services, such as smart home and Intelligent Appliance (IA). Hence, a lot of wireless standards were designed to meet the above requirements.
Among these wireless standards, Bluetooth is an ideal solution for this purpose and the relative protocol was developed by many mobile telephony and computing leaders in 1998 to standardize a simple and inexpensive personal ad-hoc network. In the Bluetooth standard, master of the Bluetooth piconet proceeds a Round Robin scheduling to serve slaves into a fixed order. From the previous research and advanced discussions, Round Robin scheduling lead to a low performance due to bandwidth wastage, unfair sharing and queueing delay. In this research, we design a 2-bits field in Bluetooth packets to preview each slave queue. Then we conduct the Shortest-Job-First (SJF) algorithm into Bluetooth scheduling and propose a SPF (Shortest Packet First) scheme, master defines the serve order dynamically to resolve above problems and improve the performance. Finally, with the experiment analysis of various scheduling algorithms, we can conclude that the SPF scheduling can achieve a lower packet delay and higher bandwidth utilization than the current Round Robin scheme.

致謝 II
摘要 IV
Abstract V
目錄 VI
圖目錄 VIII
表目錄 X
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 4
1.3 研究目的 6
1.4 研究架構 7
第二章 藍芽技術簡介 8
2.1 起源及應用 8
2.2 藍芽的特性 9
2.2.1 Bluetooth Radio 11
2.2.2 Baseband 12
2.2.3 LMP (Link Manager Protocol) 16
2.2.4 L2CAP (Logic Link Control and Adaptation Protocol) 16
2.2.5 SDP (Service Discovery Protocol) 17
第三章 文獻探討 18
3.1 非預視排程(Non-Preview Scheduling) 18
3.1.1 Pure Round Robin (PRR; RR) 19
3.1.2 Exhaustive Round Robin (ERR) 20
3.1.3 ERR according to Master Queues (MERR) 21
3.1.4 ERR according to Slave Queues (SERR) 21
3.1.5 Exhaustive Pseudo-Cyclic Master Queue Length (EPM) 21
3.1.6 Longest Queue (LQ) and Shortest Queue (SQ) 22
3.2 預視排程(Preview Scheduling) 22
3.2.1 Priority Policy (PP) 23
3.2.2 K-Fairness Policy (KFP) 24
3.2.3 Look-Ahead Round Robin (LARR) 26
3.3 文獻比較 26
第四章 研究方法 29
第五章 模擬實驗與結果 41
5.1 實驗架構 41
5.2 實驗分析 42
5.2.1 對稱、均勻型 42
5.2.2 對稱、不均勻型 45
5.2.3 非對稱、均勻型 48
5.2.4 非對稱、不均勻型 50
第六章 結論 54
6.1 研究結論 54
6.2 未來研究 54

[1]姜春霞(2003)，「藍芽技術之研究與實作」，國立台灣大學電機工程學研究所碩士論文。
[2]劉慶富(2002)，「適用於藍芽網路下的彈性頻寬管理機制」，國立暨南國際大學資訊工程學研究所碩士論文。
[3]廖啟宏(2003)，「RR-FCFS：一個新的藍芽非預視MAC層排程機制」，中華大學資訊工程學研究所碩士論文。
[4]禹帆(2002)，深入探討無線藍芽技術，第一版，文魁資訊股份有限公司。
[5]杉浦彰彥(2001)，藍芽技術解說，第一版，全華科技圖書股份有限公司。
[6]亞伯拉罕著，駱詩軒、鄧俊修譯(1998)，作業系統概念，台北：東華書局。
[7]Bluetooth Special Interest Group (2001), Specification of the Bluetooth System, Version 1.1, available from http://www.bluetooth.org.
[8]A. Capone, M. Gerla and R. Kapoor (2001), “Efficient Polling schemes for Bluetooth picocells,” in Proc. of IEEE International Conference on Communications, Helsinki, Finland, June, vol. 7, pp. 1990-1994.
[9]A. Das, A. Ghose, A. Razdan et al. (2001), “Enhancing performance of asynchronous data traffic over the Bluetooth wireless ad-hoc network,” in Proc. of IEEE INFOCOM’01, pp.591-600.
[10]C. Bisdikian (2001), “An Overview of the Bluetooth Wireless Technology,” IEEE Communications Magazine.
[11]D. Yang, G. Nair, B. Sivaramakrishnan et al. (2002), “Round robin with look ahead: a new scheduling algorithm for Bluetooth,” in Proc. IEEE International Conference on Parallel Processing Workshops, pp. 45-50.
[12]H. S. Liron, R. Kofman, G. Zussman et al. (2002), “Inter-piconet scheduling in Bluetooth scatternets,” in Proc. OPNETWORK 2002 Conference, August.
[13]J. C. Haartsen (2000), “The Bluetooth Radio System,” IEEE Personal Communications, Vol. 7, No. 1, pp. 28-36.
[14]J. Haartsen, W. Allen, J. Inouye et al. (1998), “Bluetooth: Visions, Goals, and Architecture,” ACM Computer Communications Review, Vol. 4, No.2, pp. 38-45.
[15]J. S. Oh, K. H. Tchah, O. S Kwon, T. J. Lee, Y. I. Joo, Y. S. Kim (2002), “An efficient and QoS-aware scheduling policy for Bluetooth,” in Proc. IEEE 56th Vehicular Technology Conference (VTC 2002-Fall), vol. 4, pp. 2445-2450.
[16]M. Kalia, D. Bansal, and R. Shorey (2000), “Data scheduling and SAR for Bluetooth MAC,” in Proc. of IEEE 51st Vehicular Technology Conference (VTC 2000-Spring), Tokyo, Japan, May, vol. 2, pp. 716-720.
[17]M. Kalia, D. Bansal, and R. Shorey (1999), “MAC scheduling and SAR policies for Bluetooth: A Master driven TDD pico-cellular wireless system,” in Proc. Sixth IEEE International Workshop on Mobile Multimedia Communications (MOMUC''99), San Diego, USA, Nov. pp. 384-388.
[18]S. Garg, M. Kalia, and R. Shorey (2000), “MAC scheduling policies for power optimization in Bluetooth: a Master driven TDD wireless system,” in Proc. IEEE 51st Vehicular Technology Conference (VTC 2000-Spring), Japan, Tokyo, May, vol. 1, pp. 196–200.