||Time-Constraint Service System in Ubiquitous Computing Environments Based on Quality of Service
||Department of Computer Science and Information Engineering
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.
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
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
|| A. Bestavros. “AIDA-based real-time fault-tolerant broadcast disks”, In Proceedings of Real-Time Technology and Applications Symposium, pages 49–58, 1996.
 Abbott R and Garcia-Molina H. “Scheduling real-time transactions: A performance evaluation”, ACM Transactions on Database Systems 17:513–560, 1992.
 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.
 Acharya S, Franklin M and Zdonik S. “Dissemination-based data delivery using broadcast disks”, IEEE Personal Communications 2(6):50–60, 1995.
 Adelstein F, Gupta SK, III GGR and Schwiebert L. Fundamentals of Mobile and Pervasive Computing, McGraw-Hill, 2005.
 Aksoy D. and Franklin M. “Scheduling for large-scale on-demand data broadcasting”, In Proceedings of the INFOCOM Conference, pp 651–659, 1998.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Francis Cottet, J. Delacroix, C. Kaiser, and Z. Mammeri. Scheduling in Real-Time Systems, John Wiley and Sons, Ltd, 2002.
 G. K. Zipf. Human Behaviour and the Principle of the Least Effort, Addison-Wesley, 1949.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms, The MIT, 1992.
 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.
 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.
 Wang Z. Internet QoS Architecture and Mechanisms for Quality of Service, Morgan Kaufmann, 2001.
 Wong, J.W. “Broadcast delivery”, In Proceedings of the IEEE 76(12), 1566–1577, 1988. (1)
 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.
 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.
 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.
 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.