2SYSTEM MODEL
2.1 System Model
We consider a typical on-demand broadcast architecture
similar to [2]. As shown in Fig. 3, the broadcast server is
responsible for maintaining a real-time data set (e.g.,
stock tickers, news updates, and traffic conditions, etc.),
managing the service queue and generating the broadcast
schedule. For simplicity, all data items are assumed to have
equal size (and, hence, they take equal time to broadcast).
Note that variable-size data items can be easily handled by
incorporating the factor of item size into our broadcast
scheduling algorithm. The broadcast program is generated
based on queries registered in the service queue and a
chosen scheduling algorithm. The selected items are sent to
the network controller (e.g., satellites, CDMA, and WiMax
base station) to be transmitted.
A large number of mobile clients retrieve data items
maintained by the broadcast server. Data requests of mobile
clients are sent to the broadcast server in the form of periodic
continuous queries through an uplink channel, and then are
registered in the service queue. After submitting a query,
the mobile client keeps listening to the broadcast channel
and retrieves the needed data when they appear. We
assume that items accessed by a query could be known a
priori and would not vary during its lifetime, which is
reasonable for quite a lot real-life data broadcast applica-
tions and commonly adopted in literature [14], [15].
2.2 Notations
There is a real-time data set D ¼fd
i
j1 i ng maintained
in the broadcast server. The lengths of all items are
assumed identical. In the rest of this paper, time will be
measured at the granularity of the transmission time of a
single item. A broadcast slot is the basic unit in broadcast
schedule, which accommodates a single data item. A set of
periodic continuous queries Q ¼fq
i
j1 i mg are regis-
tered in the broadcast server. We refer to q
j
i
as the jth query
instance of q
i
, p
i
as the execution period of q
i
, and q
i
:rs as
the data set accessed by q
i
. Queries retrieve data from the
broadcast channel in an unordered manner. q
j
i
is invoked at
time t
release
þðj 1Þp
i
and has a relative deadline of p
i
,
where t
release
is the release time of q
i
. We refer to q
j
i
:t
b
and
q
j
i
:t
e
as the beginning and completion time of q
j
i
, respec-
tively. There might be overlaps among read sets of different
queries, more precisely, 8i; j; 1 i; j m ^ i 6¼ j; q
i
:rs \
q
j
:rs could be not empty. A newly issued query is
characterized by a 4-tuple: <id; q
i
:rs; p
i
;t
expireation
>, where
id denotes the query identification number and t
expiration
is
the expired time of a query designated by the mobile client.
3BANDWIDTH U TILIZATION FOR PERIODIC
CONTINUOUS QUERIES
In this section, a novel measure for a continuous query set,
namely the bandwidth utilization, is defined, which not
only quantifies the minimum bandwidth demand of a
query set, but also provides the capability of schedulability
test for this set of queries.
To begin with, let’s go back to the running example
illustrated in Fig. 2. Recall that d
2
is the overlap portion
between read sets of q
1
and q
2
. One can see that when the
broadcast server disseminates d
2
upon q
1
’s request, q
2
can
also see d
2
from the broadcast channel, and vice versa. This
observation motivates us to partition the read set of a query
into two subsets, that is, the shared set and the unique set,
which are denoted by q
i
:rs-s and q
i
:rs-u, respectively.
Intuitively, items in q
i
:rs-s are those that could be shared
from other queries in the broadcast channel, and q
i
:rs-u
consists of items which will be only requested by q
i
and
made available for other queries to share. Take q
1
and q
2
as
an example, q
2
:rs-s and q
2
:rs-u will be {d
2
} and {d
3
;d
4
}, and
q
1
:rs-s and q
1
:rs-u will be and {d
1
;d
2
}, respectively, if we
let q
2
share data from q
1
. As a counterpart, q
2
:rs-s and
q
2
:rs-u will be and {d
2
;d
3
;d
4
}, and q
1
:rs-s and q
1
:rs-u will
be {d
2
} and {d
1
}, respectively, under the reverse sharing
order.
Note that although data sharing is mutual, we cannot
say that q
1
:rs-s and q
2
:rs-s are both equal to {d
2
} at the
same time. The reason is that one out of q
1
and q
2
must
request d
2
explicitly so that the other one could share it.
This suggests that the sharing-order relation, denoted by
, between two queries is asymmetric in the sense that if
q
i
q
j
, then q
j
q
i
does not hold for one calculation of
q
i
:rs-s and q
j
:rs-s. We say q
i
q
j
if we expect q
j
to share
data from q
i
. It is worth mentioning that the sharing-order
relation of two queries, say q
i
and q
j
, still exists even
though q
i
:rs doesn’t share any data items with q
j
:rs. This
is because relation only indicates in which order one
query shares data from the other and has nothing to do
with the sharing content. With the asymmetry of , one
can see that for a query set Q ¼fq
i
j1 i mg, only one
query in Q,sayq
k
,satisfiesq
j
q
k
for all q
j
,
1 j 6¼ k m, at a time. Informally, there is only one
query that can share data from all the other queries in Q
for one calculation of the shared sets of all queries.
Similarly, if we fix q
k
to share data from all the other
queries, only one out of the remaining m 1 queries can
share data from the other m 2 queries, and so on and so
forth.
1328 IEEE TRANSACTIONS ON COMPUTERS, VOL. 61, NO. 9, SEPTEMBER 2012
Fig. 3. The system diagram.