Dissertation > Excellent graduate degree dissertation topics show

Scheduling Real-time Multi-item Requests in Multi-channel Data Broadcast Systems

Author: LvJinSong
Tutor: ChenEnHong
School: University of Science and Technology of China
Course: Applied Computer Technology
Keywords: admission control scheduling channel allocation data broadcastsystems real-time system
CLC: TN934
Type: PhD thesis
Year: 2012
Downloads: 64
Quote: 0
Read: Download Dissertation

Abstract


Data broadcast is a widely accepted approach to dynamic and scalable wire-less information dissemination. With the rapidly increasing number of mobile users and real-time applications, real-time data demand from clients becomes more intractable in data broadcast systems. Moreover, the large data demand results in large database at the server side. Hence a static push-based broadcast program based on historical data access statistics or pre-determined request profiles can-not work well to achieve optimal performance. Therefore, on-demand broadcast is preferable. However, on-demand broadcast requires online data scheduling, which is hard to get optimal or near-optimal performance. Secondly, in some emerging applications, such as road traffic navigation systems, clients may request more than one dependent data items at a time. Such multi-item requests with dead-lines complicate the design of data scheduling algorithms for real-time on-demand data broadcast systems. Thirdly, although existing multi-channel architecture increases the available bandwidth for satisfying the large data demand, it com-plicates the bandwidth sharing among different channels and different clients as a client can only retrieve one data item from one channel at a time. Based on the above discussions, an online data scheduling algorithm is a vital component of real-time on-demand data broadcast systems.With the proliferation of real-time applications, minimizing request deadline miss ratio in scheduling multi-item requests has become an important task. In this study, we prove the NP-hardness of scheduling real-time multi-item requests in both single-and multi-channel data broadcast environments. Furthermore, we propose two profit-based scheduling algorithms, PVC and SSA, for single-and multi-channel architectures, respectively. Both algorithms utilize our two new concepts which are "profit" of pending items and "opportunity cost" of pending requests. To the best of our knowledge, it is the first time to introduce opportu-nity cost, which is derived from economics, into on-demand broadcast scheduling. Based on the scheduling decisions made by PVC, SSA allocates data items in the scheduled requests to available channels. Simulation results show great im-provement in comparison with traditional algorithms. In general, PVC for single channel scheduling is superior to the best of other algorithms in terms of request deadline miss ratio. For multi-channel scheduling, SSA has larger advantage with increasing number of channels in terms of request deadline miss ratio than the best of other algorithms. In addition, in the condition of the same total band-width, as simulation results show that scheduling in single-channel environment has better real-time performance than scheduling in multi-channel environment in terms of request deadline miss ratio, it motivates us to compare the former two kinds of scheduling through theoretical modelling. Our theoretical results show that single-channel scheduling is better than multi-channel scheduling in terms of average turnaround time.Although various works on admission control have been done for connection-oriented congestion control in wired and wireless networks, to the best of our knowledge. there is no admission control proposed for real-time data broadcast systems. In wireless/mobile network environments, data broadcasting is an in-creasingly popular method for information dissemination due to its potential to satisfy all outstanding requests for the same data item with a single response. In addition, data broadcasting can accommodate arbitrary populations of clients with common interests. In real-time applications, all requests have deadline con-straints, that is, missing deadlines means failure of requests. However, without admission control, all clients must wait for their desired data items until the re-quest deadlines. If the requests fail at the end, it is a waste of battery power and time. In addition, the clients have no idea about whether their requests can be satisfied at the time of submission. It will deteriorate client experience and service attraction. To reduce unnecessary waiting time of the failed requests and to provide some QoS guarantee to the clients, admission control is introduced to real-time data broadcast systems. After submission, the data items in a request are allocated to channels. If the allocation is infeasible, the request will be rejected in advance.However, by constructing the sub-problem of admission control, namely a clique problem, we prove that admission control of real-time multi-item requests that maximizes bandwidth sharing in data broadcast systems is an NP-hard prob-lem. After that, we propose a simplified algorithm of admission control, called Item Level Admission Control (ILAC). After admission control, to maximize band-width sharing, the channel allocation problem is modelled as a matching based allocation problem and is solved by utilizing the classical Primal-dual method. In addition, switching cost among channels is reduced through dynamic program-ming technique. Based on the above two points, we propose an algorithm called Matching Based Allocation (MBA). Simulation experiments are conducted to ver-ify the advantages of our proposed algorithms of admission control and channel allocation.

Related Dissertations

  1. Research on Scheduling of Whole-set Orders in JSP Based on Differential Evolution Algorithm,F273
  2. Data Aggregation Scheduling Algorithms in Wireless Sensor Networks,TP212.9
  3. Design and Implementation of Automotive Can-Can Gateway,TP273
  4. Research of Scheduling Algorithm Based on Hybrid Adaptive Genetic Algorithm in Computing Grid,TP393.09
  5. Public Transport Optimal Dispatching Based on the Genetic-Newton Algorithm,TP18
  6. Mining resources based on genetic algorithm optimization model of,O224
  7. Study of the Water-Inrush Mechanism and Prediction of the Water-Resisting Floor,TM734
  8. Wireless network based multi- layer protocols transmit power across key technologies,TN92
  9. On Data Scheduling Strategies of Serving Peers in P2P VoD Systems,TN948.64
  10. Research on the Improvements and Applications of Particle Swarm Optimization,TP18
  11. Improvement and Simulation of Dynamic Call Admission Control Algorithm in WiMAX System,TN929.5
  12. The Research of Network Traffic Control System Based on Linux,TP393.06
  13. Multi-user MIMO Downlink User Selection Algorithm,TN919.3
  14. Multi-Radio sensor networks research on cross-layer protocol,TN929.5
  15. Research of Packet Scheduling Algorithm of the Click Modular Software,TP393.05
  16. Research on the Problem of Multi-objective Flexible Job Shop Scheduling Optimization,O224
  17. A New Scheduling Algorithm of LTE Based on Proportional Fair,TN929.5
  18. Research on Task Scheduling Strategy of Cloud Computing Based on MPSO Algorithm,TP3
  19. Based on the study of resource management in the cloud environment of credibility,TP315
  20. Scheduling and Process Monitoring System of Steelmaking-Refining-Continuous Casting Production,TF345
  21. Sdesign and Implementation of Course Scheduling Management System,TP311.52

CLC: > Industrial Technology > Radio electronics, telecommunications technology > Broadcasting > Radio broadcasting
© 2012 www.DissertationTopic.Net  Mobile