以最大容量優先之USB工作排程演算法｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	楊盛富 Sheng-Fu Yang
論文名稱：	以最大容量優先之USB工作排程演算法 Capacity-First based Task Allocation in USB Scheduling
指導教授：	蘇順豐 Shun-Feng Su
口試委員:	王偉彥 none 陶金旺 none 蔡超人 none
學位類別：	碩士 Master
系所名稱：	電資學院 - 電機工程系 Department of Electrical Engineering
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	68
中文關鍵詞：	智慧居家環境、USB 、排程、接受率
外文關鍵詞：	Smart Home, USB, Scheduling, Acceptance Rate
相關次數：	點閱：201 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

近年來，「智慧居家環境（Smart Home）」，已經成為熱門的研究領域。欲實現智慧型居家環境，使其擁有自動化、安全性以及娛樂性等相關功能，首先須建構智慧型居家環境網絡，而目前常見的環境網路建構以TCP/IP和紅外線為主。而隨著USB介面以受到重視及應用，幾乎所有的PC周邊設備，以及消費型電子產品皆已USB介面列為必備的介面。本文中首先會介紹USB 的結構和特點、資料傳輸、傳輸排程等等，來對USB做整體的認識。然而 USB 標準中只簡略的定義資料傳輸容量的限制，沒有一個有效的機制來保證USB同步傳輸的傳輸品質。針對同步傳輸，Fixed-rate policy演算法提供了傳輸品質的保證但卻因為額外的overhead而降底了頻寬利用率，在本篇論文中，我們提出一個有效的排程演算法以提高 USB頻寬重新排程的接受率，且降低額外overhead。而在本研究中，我們根據和先前的排程演算法比較的結果，可以看到這個演算法在排程接受率上明顯的提高且overhead也有顯著的降低。我們也發現當資料量愈大時，這個演算法的效果更是顯著。

Smart home has been a promising research area in recent years. It is necessary that consumers have easy ways of using, managing, and sharing the digital contents or home appliances. Then, all devices must be able to communicate with the home computer server via home networks. Up to present, most of smart home networks still use “TCP/IP” or infrared interface. As the USB interface has been paid much attention to and put in use day by day, almost all peripheral equipment of PCs and consuming electric products have gradually consider USB as a necessary attachment. However, the USB specification only defines approximately the limitations for the data transfer capacity and it lacks an efficient mechanism to ensure QoS requirement for isochronous transfer. In the fixed-rate policy algorithm, it provides guaranteed QoS services to USB isochronous transfer requests, but the bandwidth utilization will be reduced owing to the extra overheads generated. In this paper, we propose an effective scheduling algorithm to improve the scheduling acceptance rate and to reduce the protocol overheads. In this study, we compared the proposed algorithm with the previous approaches and a clearly evident result indicates that the scheduling acceptance rate of the proposed algorithm obviously increases and the protocol overheads are evidently reduced while compared to those existing algorithms. It can also be found that when the workload is heavy, the effectiveness of the proposed algorithm is significant.

ABSTRACT	i
致 謝	iii
Contexts	iv
List of Tables	vi
List of Figures	vii
Chapter 1 Introduction	1
1.1 Introduction	1
1.2 Motivation	4
1.3 Thesis Organization	4
Chapter 2 Introduction to USB Systems	6
2.1 USB System Description	6
2.1.1 List of USB Features	6
2.1.2 USB Physical Interface	7
2.1.3 USB Logical Interface	8
2.2 USB Host Controller	13
2.2.1 Queue List Structure	14
2.2.2 Endpoints	15
2.2.3 Transfer Descriptors	15
2.3 Data Transfer Type	16
2.3.1 Control Transfer	17
2.3.2 Bulk Transfer	17
2.3.3 Interrupt Transfer	18
2.3.4 Isochronous Transfers	18
2.4 Transfer Schedule	19
2.4.1 Bandwidth allocation	19
2.4.2 Periodic Schedule	20
2.4.3 Asynchronous schedule	21
Chapter 3 Related Work	23
3.1 Work Load Re-Insertion Method	23
3.1.1 Period Modification Policy	24
3.1.2 Work Load Re-Insertion	26
3.1.3 Work Load Re-insertion Algorithm	29
3.2 Work Load Spilt Method	30
3.2.1 Bandwidth Budget	34
3.2.2 Optimization Algorithm	35
Chapter 4 Capacity-First Based USB Scheduling	38
4.1 Idea of Capacity-First Based Method	38
4.1.1 Procedure of Capacity-First Based Method	40
4.1.2 Time Complexity of Sorting	45
4.1.3 Service Priority Problem	46
4.2 Capacity-First Based Algorithm	48
Chapter 5 Performance Evaluation	53
5.1 USB Scheduling Requests Acceptance Rate	53
5.2 Protocol Overhead Reduction	57
Chapter 6 Conclusion	62
References	64
Appendix	67
A. Create a binary tree with index number function	67
B. Find maximum capacity function	68

                                

[1] Y. Kawahara, H. Morikawa, and T. Aoyama, “Intelligent interface systems utilizing user context-awareness,” Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, ICMLC 2007 4, pp. 2119-2124, 2007.
[2] J.-F. Man, L.-M. Yang, W.-Q. Zhu, and Q.-Q. Li, “A model of smart home fusing multi-intelligence,” Proceedings - 2008 4th International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IIH-MSP 2008, pp. 56-59, 2008.
[3] C.-C. Chen, Study of USB Interface Based Smart Home Systems, Master Thesis, Dept. of Electrical Engineering, National Taipei University of Technology, Taiwan, 2008.
[4] M.-X. Qi, C. Qi, and T.-S. Huang, “Home automation system based on power line carrier communication technology,” Dianli Zidonghua Shebei / Electric Power Automation Equipment, Vol. 25, No. 3, pp. 75, 2005.
[5] R. S. Raji and Ted. Davis, “Smart networks for control,” IEEE Spectrum, Vol. 31, No. 6, pp. 49-55, 1994.
[6] N. Sriskanthan, F. Tan, and A. Karande, “Bluetooth based home automation system,” Microprocessors and Microsystems, Vol. 26, No. 6, pp. 281-289, 2002.
[7] P. Tang and T. Venables, “Smart homes and telecare for independent living,” Journal of Telemedicine and Telecare, Vol. 6, No. 1, pp. 8-14, 2000.
[8] H.-S. Kim and C.-G. Lee, “USB-based home control system using OSGi,” International Conference on Consumer Electronics, 2006, ICCE '06, 2006 Digest of Technical Papers, pp. 251-252, 2006.
[9] Y-S Kim, H-S Kim, and C. Lee, “The development of USB home control network system,” The 8th International Conference on Control, Automation, Robotics and Vision 2004. ICARCV 2004, pp. 289-293, 2004.
[10] USB-IF (USB Implementers Forum), http://www.usb.org/home.
[11] Jan Axelson, “USB complete: Everything you need to develop custom USB peripherals,” Lakeview Research Madison, WI, pp. 61– 81, 2005.
[12] Universal Serial Bus Specification, Revision 1.1, http://www.usb.org/.
[13] Universal Serial Bus Specification, Revision 2.0, http://www.usb.org/.
[14] Intel, UHCI Design Guide, http://developer.intel.com/design/USB/UHCI11D.htm.
[15] Compaq, OHCI host controller Specification, http://www.compaq.com/productinfo/development/openhci.html.
[16] Intel, EHCI Specification, http://www.intel.com/technology/usb/ehcispec.htm.
[17] 王成儒, 李英煒, and 許永和, USB2.0原理與研發技術, 全華, 台北,
第5.1–5.34頁, 2006.
[18] T. P Baker and A. Shaw, “The cyclic executive model and Ada,” Real-Time Systems Symposium, 1988.
[19] B. Adelberg, H. Molina and B.Kao, “Emulating soft real-time scheduling using traditional operating systems schedulers,” IEEE 14th Real-Time Systems Symposium, Dec, 1994.
[20] K. A. Kettler, J.P. Lehoczky, and J. K. Strosnider, “Modeling bus scheduling policies for real-time systems,” IEEE Real-Time Systems Symposium, Dec,1995.
[21] C.-Y. Huang, L.-P. Chang, and T.-W. Kuo, “A cyclic-executive-based QoS guarantee over USB,” IEEE 9th Real-Time and Embedded Technology and Applications Symposium, pp. 88 – 95, 2003.
[22] C.-Y. Huang, L.-P. Chang, and T.-W. Kuo, “QoS support for USB 2.0 periodic and sporadic device requests,” The 25th Real-Time Systems Symposium, pp. 395 – 404, 2004.
[23] C.-Y. Huang, Quality of Service Support for I/O Common Bus Interfaces, Ph.D Dissertation, National Taiwan University, Taipei, Taiwan, 2005.
[24] Y.-R. Chang , The USB Host Controller Scheduling Optimization on Embedded System, Master Thesis, National Cheng Kung University , Taiwan, 2005.
[25] Y. Langsam, M. J. Augenstein, and A. M. Tenenbaum, Data Structure using C and C++, Prentice Hall International, NJ, pp. 249 – 280, 1996.
[26] 戴顯權,資料結構, 紳藍出版社,高雄,第5.8 – 5.45頁, 2005.

簡易檢索 / 詳目顯示

相關論文