Information Technology Reference
In-Depth Information
air channel(s), the single-class indexing method resulted in a faster response time
and lower energy consumption than the hierarchical method.
7.
Conflict Resolution and Generation of Access
Patterns—Heuristic Solution
Broadcasting information over the parallel air channels reduces the access time
and power consumption at the expense of conflicts between accessing objects on
different channels. As a result of conflicts, the retrieval protocol requires several
passes over the air channels in order to pull the requested information. Conflicts will
directly influence the access latency and hence, the overall execution time.
7 . 1 R e t r i e v i n g O b j e c t s f r o m P a r a l l e l B r o a d c a s t A i r C h a n n e l s
i n t h e P r e s e n c e o f C o n fl i c t s
The problem of scheduling the retrieval order of the requested objects can be
modeled as a Travel Salesman Problem (TSP). Making the transformation from a
broadcast to the TSP requires the creation of a complete weighted directed graph
G
with
K
nodes, where each node represents a requested object. The weight
w
of each
edge
(i, j )
is either 0 or 1. A weight of 0 indicates that the object
j
is after object
i
in
the broadcast and that objects
i
and
j
are not in conflict. A weight of 1 indicates that
object
j
is either before or in conflict with objects
i
. An example of this conversion
is shown in
Fig. 26
.
The nature of the problem dictates that
G
is asymmetric; that is, the weight of
edge
(i, j )
is not necessarily equal to the weight of edge
(j, i)
. Thus, in solving this
problem we can apply those techniques that are applicable to the Asymmetric TSP.
7.1.1 Performance Evaluation
A simulator was developed to randomly generate broadcasts and determine how
many passes were required to retrieve a varying number of requested objects. Several
algorithms for ordering the retrieval of objects from the broadcast, both TSP-related
and non-TSP-related, were analyzed. In addition, issues such as the optimal num-
ber of broadcast channels to use, optimal broadcast length, and the effectiveness of
splitting large requests into smaller ones were also studied
[40,41]
.
7.1.2 Simulation Model
In this simulation model, a broadcast is represented as an
N × M
two-dimensional
matrix, where
N
represents the number of objects in each channel of a broad-
