Data broadcast is a widely accepted approach to dynamic and scalable wireless 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 cannot 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 multiitem
requests with deadlines 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
complicates 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 ondemand
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 opportunity cost, which is derived from economics, into ondemand
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 improvement 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 bandwidth, 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 modeling. 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 connectionoriented
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 increasingly 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 constraints, that is, missing deadlines means
failure of requests. However, without admission control, all clients must wait for their
desired data items until the request 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 problem. After that,
we propose a simplified algorithm of admission control, called Item Level Admission
Control (ILAC). After admission control, to maximize bandwidth sharing, the channel
allocation problem is medelled 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 programming technique. Based on the above two
points, we propose an algorithm called Matching Based Allocation (MBA). Simulation
experiments are conducted to verify the advantages of our proposed algorithms of
admission control and channel allocation.
| Date of Award | 3 Oct 2012 |
|---|
| Original language | English |
|---|
| Awarding Institution | - City University of Hong Kong
|
|---|
| Supervisor | Chung Sing Victor LEE (Supervisor) & Minming LI (Co-supervisor) |
|---|