系統識別號 | U0002-1801201100284700 |
---|---|
DOI | 10.6846/TKU.2011.00610 |
論文名稱(中文) | 在普適計算環境中以品質服務為基礎之即時型服務系統 |
論文名稱(英文) | Time-Constraint Service System in Ubiquitous Computing Environments Based on Quality of Service |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 資訊工程學系博士班 |
系所名稱(英文) | Department of Computer Science and Information Engineering |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 99 |
學期 | 1 |
出版年 | 100 |
研究生(中文) | 江定榮 |
研究生(英文) | Ding-Jung Chiang |
學號 | 896410171 |
學位類別 | 博士 |
語言別 | 英文 |
第二語言別 | |
口試日期 | 2010-12-13 |
論文頁數 | 87頁 |
口試委員 |
指導教授
-
施國琛(timothykshih@gmail.com)
委員 - 王俊嘉(gcwang@tsint.edu.tw) 委員 - 施國琛(timothykshih@gmail.com) 委員 - 許輝煌(h_hsu@mail.tku.edu.tw) 委員 - 郭穎鋒(yfkuo@cc.cust.edu.tw) 委員 - 林其誼(chiyilin@mail.tku.edu.tw) |
關鍵字(中) |
時間限制 普適計算 服務品質 |
關鍵字(英) |
Time-Constraint Ubiquitous Computing Quality of Service (QoS) |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在行動網路的環境中,網路連接的效能將影響網路的服務品質,為提升系統的服務範圍以及處理多變化的資料樣本,即時無線廣播方法是一項可靠的資料傳輸機制,本研究針對即時無線廣播系統提出一個分析與實作模型,正如本研究實驗結果所示,傳統的即時運算演算法應用於無線廣播環境時,其即時性資料的處理,效能表現已無法滿足傳統的預測,因此,本研究提供一個以服務品質為基礎的排程演算法—在多重廣播頻道上動態調整演算法,來處理即時性的資料並服務行動使用者的需求。 為突顯本研究的貢獻,在效能評比方面,本研究引用傳統主從式即時運算演算法作為效能評量標準,評比項目包括網路存取延遲時間、使用者等待時間、系統擴展性與系統執行負載率,除此之外,更重要的是最佳化即時性資料的截止率,從一系列的實驗結果得知,本研究所提出的演算法與機制,在各項效能評估中均優於傳統的演算機制,由此證明,本研究的可行性與貢獻度。 在未來研究工作上,除了著手改進本研究的演算機制,以降低其執行時間複雜度,提高實用性與執行效率,在本研究的研究過程中,也觸發一些相關的研究方向,包括即時演算法的精進、即時傳輸交易的錯誤控制、即時性熱門資料的篩選與更新、可變動大小的即時資料傳輸、行動裝置快取資料管理與多重節點即時資料通訊。 |
英文摘要 |
Network connectivity affects the quality of service (QoS) in a mobile network. Real-time broadcasting is a promising data dissemination method to improve system scalability and deal with dynamic data access pattern. This study presents an analysis model and a simulation model for real-time broadcasting systems. As this study demonstrates, traditional strategies like EDF (Earliest Deadline First) and LSF (Least Slack First) in the non-mobile real-time environment do not perform efficiently in a mobile broadcasting environment. Therefore, this study proposes an efficient scheduling algorithm with guaranteed QoS, called dynamic adjustment scheduling (DAS), which is designed for timely delivery of data to mobile clients. This study also compares DAS with traditional client/server based real-time scheduling strategies and mobile non-real-time broadcast strategies. The proposed approach generally outperforms existing real-time strategies with different deadline distributions. A series of simulation experiments evaluates the performance of the proposed scheme. The results demonstrate that this algorithm outperforms other algorithms for performance metrics such as miss rate, waiting time, and stretch. Results also show that the overhead of this algorithm is low compared with other scheduling algorithms. In the future, we plan to improve the DAS strategy by reducing its scheduling time complexity. Other topics for future research include the investigation of real-time scheduling algorithms that can handle transmission errors, update access patterns, unfixed page sizes, client cache management schemes and multi-hop communication. |
第三語言摘要 | |
論文目次 |
Contents Chapter 1 Introduction 1 Chapter 2 Preliminary and Related Work 6 2.1 Ubiquitous Computing and Database 6 2.2 Data Dissemination 12 2.3 Broadcast Models of Data Delivery Mechanism 16 Chapter 3 Quality of Service in Mobile Network 20 3.1 Architectures and Mechanisms for Quality of Service 20 3.2 Quality of Service for Ubiquitous Computing Environments 23 3.2.1 The Impacts of Link Type on Quality of Service 23 3.2.2 The Impacts of Movement on Quality of Service 25 3.2.3 The Impacts of Portable Devices on Quality of Service 27 3.2.4 The Impacts on Other Non-functional Parameters 29 3.3 Management of Quality of Service in Ubiquitous Environments 31 3.3.1 Management Adaptability of Quality of Service 31 3.3.2 Resource Management and Reservation for Quality of Service 36 3.3.3 Context Awareness for Quality of Service 38 3.3.4 Use of Standards for Quality of Service 40 Chapter 4 Proposed Mechanisms and Algorithm 42 4.1 Task States and Scheduling with Time-Constraint 42 4.2 Mechanisms with Time-Constraint to Mobile Users 48 4.3 Proposed Broadcasting Algorithm with Time-constraint 52 4.3.1 Proposed System Model 54 4.3.2 Problem Formulation and Definition 63 4.3.3 Design of the Proposed Algorithm 65 Chapter 5 Experiment Results and Analysis 71 5.1 Simulation Environment 74 5.2 Simulation Results and Analysis 76 Chapter 6 Conclusion and Future Work 82 6.1 Conclusion 82 6.2 Future Work 83 Bibliography 84 List of Figures Figure 1 mobile network architecture 1 Figure 2 Mobility management for mobile users 2 Figure 3 An enhanced architecture based on time-constraint service 3 Figure 4 Ubiquitous computing environment and database 6 Figure 5 Data dissemination by mobile switches over mobile network 13 Figure 6 Push-based broadcast 16 Figure 7 Pull-based broadcast 17 Figure 8 End-to-end quality of service (QOS) scenario 20 Figure 9 An overview of time-constraint system 42 Figure 10 Data delivery of broadcasting architecture 61 Figure 11 Broadcasting 10 data items with time constraints to partition 3 disjoint subsets and the miss rate = 0.342 69 Figure 12 Using dynamic scheduling algorithm to partition 3 disjoint subsets and the miss rate = 0 70 Figure 13 Deadline miss rate over different data access skewed patterns 76 Figure 14 Deadline miss rate over overhead of mobile clients 77 Figure 15 Deadline miss rate over stretch of multichannel 78 Figure 16 Deadline miss rate by data size 79 List of Tables Table 1 Common wireless communication systems 23 Table 2 Technology-based quality of service with time-constraint 47 Table 3 User-based quality of service with time-constraint 51 Table 4 example of data items for proposed algorithm 68 Table 5 Simulation parameters 80 Table 6 Performance comparison of different scheduling algorithms 81 |
參考文獻 |
[1] A. Bestavros. “AIDA-based real-time fault-tolerant broadcast disks”, In Proceedings of Real-Time Technology and Applications Symposium, pages 49–58, 1996. [2] Abbott R and Garcia-Molina H. “Scheduling real-time transactions: A performance evaluation”, ACM Transactions on Database Systems 17:513–560, 1992. [3] Acharya S, Alonso R, Franklin M and Zdonik S. “Broadcast disks: data management for asymmetric communication environments”, In Proceedings of ACM SIGMOD, pp 199–210, 1995. [4] Acharya S, Franklin M and Zdonik S. “Dissemination-based data delivery using broadcast disks”, IEEE Personal Communications 2(6):50–60, 1995. [5] Adelstein F, Gupta SK, III GGR and Schwiebert L. Fundamentals of Mobile and Pervasive Computing, McGraw-Hill, 2005. [6] Aksoy D. and Franklin M. “Scheduling for large-scale on-demand data broadcasting”, In Proceedings of the INFOCOM Conference, pp 651–659, 1998. [7] Azzedine Boukerche and Harold Owens II. “Media synchronization and qos packet scheduling algorithms for wireless systems”, ACM Mobile Networks and Applications, 10(1-2):233–249, February 2005. [8] C. Liu and J. Layland. “Scheduling algorithms for multiprogramming in hard real-time traffic environments”, Journal of the Association for Computing Machinery, 20(1):179–194, 1973. [9] Comer Douglas and Droms Ralph. “Consequences of IPv6 addressing”, Real Time Media Delivery over the Internet, Journal of Internet Technology, 5(4):305–309, October 2004. [10] D. Aksoy and M. Franklin. “Rxw: a scheduling approach for large-scale on-demand data broadcast”, IEEE/ACM Transactions on Networking, 7(6):846–860, 1999. [11] Dapeng W, Yan Z, Muqing W and Xiaojing Z. “Medium access control access delay analysis of IEEE 802.11e wireless lan”, IET Communications 3(6):1061–1070, 2009. [12] Ding-Jung Chiang, Hwei-Jen Lin, and Timothy K. Shih. “Providing data items with time constraints in multi-channel broadcasting environments”, Journal of Software, 3(8):65–72, November 2008. [13] Ding-Jung Chiang, Jen-Shiun Chiang, Stephen Y. Kuo and Timothy K. Shih. “Mobile data with time constraint over ubiquitous computing environments”, In Proceedings of U-media2010, pages 6-11, July, 2010. [14] Ding-Jung Chiang and Timothy K. Shih. “Scheduling Data Items with Time Constraints Based on On-Demand Mode in Ubiquitous Environments”, In Proceedings of MSEAT2010, pages 237-242, July, 2010. [15] Dykeman H. and Wong J. “A performance study of broadcast information delivery systems”, Seventh Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE, INFOCOM’88, pages 739-745, 1988. [16] Francis Cottet, J. Delacroix, C. Kaiser, and Z. Mammeri. Scheduling in Real-Time Systems, John Wiley and Sons, Ltd, 2002. [17] G. K. Zipf. Human Behaviour and the Principle of the Least Effort, Addison-Wesley, 1949. [18] Goodridge W.S., Robertson W., Phillips W.J. and Sivakumar S. “Traffic driven multiple constraint-optimization for qos routing”, International Journal of Internet Protocol Technology 1(1):19–29, 2005. [19] Han-Chieh Chao. “An overview and analysis of mobile internet protocols in cellular environments”, Internet Research-Electronic Networking Applications and Policy, 11(5):435–450, 2001. [20] Hu Q.L., Lee D.L. and Lee W.C. “Dynamic data delivery in wireless communication environments”, In Proceedings of International Workshop on Mobile Data Access, pp 218–229, 1998. [21] J. Fernandez-Conde and K. Ramamritham. “Adaptive dissemination of data in time-critical asymmetric communication environments”, In Proceedings of the 11th Euromicro Conference on Real-Time Systems, pages 195–203, 1999. [22] J. Xu, X. Tang, and W. Lee. “Time-critical on-demand data broadcast: algorithms, analysis, and performance evaluation”, IEEE Transactions on Parallel and Distributed Systems, 17(1):3–14, 2006. [23] J.-L. Chen and Han-Chieh Chao. “Fair resource sharing scheduling for cellular data services with qos provisioning”, IEE Proceedings V Communications, 148(3):144–148, June 2001. [24] Jiang Zhifeng and Leung Victor C. M. “End-to-end quality of service provisioning for nternet access via third generation wireless networks”, Object-Oriented Technology and Applications, Journal of Internet Technology, 6(4):367–374, October 2005. [25] Jun Chen, Victor C.S.Lee, and Edward Chan. “Scheduling real-time multi-item requests in wireless on-demand broadcast networks”, In Proceedings of the 4th Intl. Conf. on Mobile Technology, Applications and Systems (Mobility 2007), pages 125–131, September 2007. [26] K. Prabhakara, K. A. Hua, and J.-H. Oh. “Multi-level multi-channel air cache designs for broadcasting in a mobile environment”, In Proceedings of the 16th International Conference on Data Engineering, pages 167–176, February 2000. [27] Louta Malamati D. and Michalas Angelos C. “Quality of service management in IP networks through dynamic service rate reconfiguration”, Journal of Internet Technology, 7(1):45–57, January 2006. [28] Marojevic V., Balleste X.R. and Gelonch A. “A computing resource management framework for software-defined radios”, IEEE Transactions on Computers 57(10):1399–1412, 2008. [29] Rajendran M. Sivasankaran, John A. Stankovic, Don Towsley, Bhaskar Purimetla, and Krithi Ramamritham. “Priority assignment in real-time active databases”, The International Journal on Very Large Data Bases, 5(1):019–034, January 1996. [30] S. Baruah and A. Bestavros. “Pinwheel scheduling for fault-tolerant broadcast disks in real-time database systems”, In Proceedings of the 13th International Conference on Data Engineering, pages 543–551, April 1997. [31] Sun Y., Belding-Royer E.M., Gao X. and Kempf J. “Real-time traffic support in heterogeneous mobile networks”, ACM Wireless Networks 13(4):431–445, 2007. [32] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms, The MIT, 1992. [33] Talukdar A.K., Badrinath B. and Acharya A. “Integrated services packet networks with mobile hosts: Architecture and performance”, ACM Wireless Networks 5(2):111–124, 1999. [34] Tiecheng Liu and Chekuri Choudary. “Real-time content analysis and adaptive transmission of lecture videos for mobile applications”, ACM Multimedia 2004, pages 400–403, October 2004. [35] Wang Z. Internet QoS Architecture and Mechanisms for Quality of Service, Morgan Kaufmann, 2001. [36] Wong, J.W. “Broadcast delivery”, In Proceedings of the IEEE 76(12), 1566–1577, 1988. (1) [37] Yee W.G. and Navathe S.B. “Efficient data access to multi-channel broadcast programs”, In Proceedings of the 12th International Conference on Information and Knowledge Management, pp 153–160, 2003. [38] Yuan Sun, Elizabeth M. Belding-Royer, Xia Gao, and James Kempf. “Real-time traffic support in heterogeneous mobile networks”, ACM Wireless Networks, 13(4):431–445, August 2007. [39] Yuen JCH, Chan E., Lain K.Y., Leung H.W. “Cache invalidation scheme for mobile computing systems with real-time data”, SIGMOD Record 29(4):34–39, 2000. [40] Yun-Sheng Yen, Weimin Chen, Jia-Cheng Zhhuang, and Han-Chieh Chao. “A novel sliding weighted fair queueing scheme for real-time applications”, In IEE Proceedings V Communications, 152(3):320–326, June 2005. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信