Information Technology Reference
In-Depth Information
3.6.2 Generation of Access Patterns—A Top Down Retrieval
Approach
The retrieval method discussed in the previous section produces access patterns
with excessive channel switches. This in turn increases the energy consumption at
the mobile unit. In addition, to determine “the best” access pattern, it generates a
complete weighted access forest prior to the path selection step and then in a bottom
up fashion it ranks all the potential access patterns along the access forest. This
increases the execution time and space requirements. To overcome these limitations,
the priority list of heuristics was revised as follows:
Eliminate the number of conflicts;
Minimize the number of channel switches;
Retrieve the maximum number of objects;
and “Least-Cost Path” method was employed to generate the access patterns
[53]
.
Similar to our discussion in Section
3.6.1
, the temporal and spatial information
provided by the index is used to plot an access pattern for the requested objects.
The index is used to generate a weighted tree consisting of nodes as data objects
and arcs. However, to improve the efficiency and effectiveness of the access pattern
generation process, a top-down “best-first search” method is employed—heuristic
information is used to assess the cost of every search avenue and the search contin-
ues down the path with the lowest cost. By nature of the search algorithm, nodes on
the same level in a tree that possess a higher cost will produce non-ideal patterns.
Thus, higher cost nodes are eliminated, and only those nodes that provide a poten-
tial least-cost path are expanded and searched further. For large user requests, the
least-cost path approach provides a means for reducing the number of branches to
be searched, thus having potential to reduce the overall searching time for an ideal
access pattern. Our previous running example (
Fig. 7
) will be used to clarify the
process.
(1)
Probe the index
: The index containing the user's requests is retrieved, and is
used to determine the channel number and offset of each requested item.
(2)
Generate access forest
: For each channel, find the first object to be broadcast.
The root nodes in the running example are O
1
,O
3
,O
6
, and O
8
.
(3)
Root node assignment
: For each root node from step 2, temporarily assign a
tag of “C
0
” and create an access tree with the root.
(4)
Children assignment
: For each node, find the closest non-conflicting objects
that may be accessed later on in the broadcast by the node. Label the arc for
each child respectively—“1” if the child is on a different channel, “0” if the
child is on the same channel. All child nodes are temporarily assigned a tag of
