Information Technology Reference
In-Depth Information
3.6.1 Generation of Access Patterns—A Bottom Up Retrieval
Approach
The scheduling algorithm generates an
access forest
—a collection of trees (
access
trees
), where each
access tree
represents all possible access patterns during a broad-
cast cycle
[48,49]
.An
access tree
is composed of two elements: nodes and arcs.
Node
: A node represents a requested object. Nodes are labeled to indicate their
conflict status: mnemonically, “C
1
” represents if the object is in conflict with
another object(s) in the broadcast; and “C
0
” indicates the lack of conflict. Each
access tree in the access forest has a different node as a root—the root is the
first accessible requested object on a broadcast cycle. This simply implies that
an access forest can have at most
n
trees where
n
is the number of broadcast
channels.
Arcs
: The arcs of the trees are weighted arcs. A weight denotes whether or
not channel switching is required in order to retrieve the next scheduled object
in the access pattern. A branch in a tree represents a possible access pattern
of objects during a broadcast cycle with no conflicts. Starting from the root,
the total number of branches in the tree represents all possible access patterns
during a broadcast cycle.
Using the access forest, all possible non-conflicting weighted access patterns are
generated and ranked based on their weights. A suitable access pattern for each
broadcast cycle is the one that retrieves the maximum number of object with mini-
mum number of channel switches.
Figure 7
is used as a sample example to detail the
generation of the access patterns for each broadcast cycle:
(1)
Search
: Based on the user's query, this step determines the offset and the chan-
nel number of the requested objects on the broadcast channels.
(2)
Generation of the access forest
: For each broadcast channel, search for the
requested object with the smallest offset (these objects represent the roots of
access tree). For the example, the objects with the smallest offsets are O
1
,O
3
,
O
6
and O
8
.
(3)
Root assignment
: For each channel with at least one object requested, generate
a tree with root node as determined in step 2. The roots are temporarily tagged
as “C
0
.”
(4)
Child assignment
: For each root, and relative to its position on the air channel,
determine the closest non-conflicting objects on each channel. With respect
to an object
O
i,x
at location
X
on air channel
i
(1
i
n
) the clos-
est non-conflicting object is either the object
O
i,x+
1
or the object
O
j,x+
2
,
j = i
. If the child is in the same broadcast channel as the root, the arc is
