在行動網路的環境中，網路連接的效能將影響網路的服務品質，為提升系統的服務範圍以及處理多變化的資料樣本，即時無線廣播方法是一項可靠的資料傳輸機制，本研究針對即時無線廣播系統提出一個分析與實作模型，正如本研究實驗結果所示，傳統的即時運算演算法應用於無線廣播環境時，其即時性資料的處理，效能表現已無法滿足傳統的預測，因此，本研究提供一個以服務品質為基礎的排程演算法—在多重廣播頻道上動態調整演算法，來處理即時性的資料並服務行動使用者的需求。
    為突顯本研究的貢獻，在效能評比方面，本研究引用傳統主從式即時運算演算法作為效能評量標準，評比項目包括網路存取延遲時間、使用者等待時間、系統擴展性與系統執行負載率，除此之外，更重要的是最佳化即時性資料的截止率，從一系列的實驗結果得知，本研究所提出的演算法與機制，在各項效能評估中均優於傳統的演算機制，由此證明，本研究的可行性與貢獻度。
    在未來研究工作上，除了著手改進本研究的演算機制，以降低其執行時間複雜度，提高實用性與執行效率，在本研究的研究過程中，也觸發一些相關的研究方向，包括即時演算法的精進、即時傳輸交易的錯誤控制、即時性熱門資料的篩選與更新、可變動大小的即時資料傳輸、行動裝置快取資料管理與多重節點即時資料通訊。

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.