Broadcasting a Means to Disseminate Public Data in a Wireless Environment—Issues and Solutions - Advances in Computers - page 29

“C 0 .” Figure 8 shows the state of the access trees after generating the children
of the roots.
It is at this point in the algorithm where the new method differs from the one
presented in Section 3.6.1 .
(5) Node label update : After the generation of the children, they are examined
and assessed for conflicts. If the parents of the children are the root nodes the
root nodes are also examined for conflicts. A node that is in conflict with at
least one other node is labeled as “C 1 ,” and a node that is not in conflict with
any node is labeled as “C 0 .”
A special case occurs if there is only one requested object on a channel.
The tree of this root node is assigned a channel switch cost of “1” to signify
that an extra broadcast pass is required to retrieve that object if its access tree
is used. If a cost of “1” was not assigned, an attempt might be made to only
use that tree because that path has a switching cost of “0.” Therefore, it is
desirable to attempt to retrieve this item using a channel switch during the
retrieval of some other objects first. In the running example, O 8 is an example
of this special case.
(6) Cost evaluation : At this stage of the retrieval method, the children are exam-
ined to determine the least-cost path of the tree. Using the weights assigned to
the arcs of each child, the switching cost of each node is calculated. The node
with the lowest switching cost (arc with label “0”) will be expanded in step 7.
If more than one node has the lowest switching cost, then all paths are to be
expanded.
(7) Expansion : Using the node with the lowest switching cost found in step 6,
the children of that node are determined to expand the least-cost path. The
children are added as defined in step 4. Step 5 is repeated to further define the
least-cost path.
(8) Repeat : Step 7 is repeated until all least-cost paths can no longer be expanded.
The fully expanded least-cost paths for the running example are depicted in
Fig. 11 .
(9) Compare : If more than one least-cost path is determined for each tree, the
heuristics are used to determine the most ideal path to follow. The least-cost
path to use will be the access pattern that:
Eliminates the most conflicts (has highest number of “C 1 ” nodes);
Uses the least channel switches (the path whose arcs are weighted with
the most “0”s;
Retrieves the most objects (the highest node count).