Information Technology Reference
In-Depth Information
cast and
M
represents the number of parallel channels. For
K-object request
,1
K
NM
, the simulator randomly generates 1000 patterns representing the uni-
form distribution of
K
objects among the broadcast channels. The
K
objects from
each randomly generated pattern are retrieved using various retrieval algorithms.
The number of passes is recorded and compared. To prevent the randomness of the
broadcasts from affecting the comparison of the algorithms, the same broadcast is
used for each algorithm in a particular trial and the mean value is reported for each
value of
K
.
7.1.3
Object Retrieval Algorithms
Several algorithms were used to retrieve the objects from the broadcast. This in-
cludes both exact and approximate TSP solution finders. In addition, we studied two
heuristic based methods as well.
7.1.3.1 TSP Methods.
An exact TSP algorithm was used to provide a ba-
sis for comparison with the other algorithms. These algorithms are simply too slow
and too resource-intensive to use at a mobile unit. For example, some TSP problems
with only 14 nodes took several minutes of CPU time in this experiment. While a bet-
ter implementation of the algorithm may somewhat reduce the cost, it cannot change
the fact that finding the exact solution will require exponential time for some inputs.
Knowing the exact solution to a given TSP does, however, allow us to evaluate the
quality of a heuristic approach. A TSP heuristic based on the assignment problem
relaxation is also included. This heuristic requires far less CPU time and memory
than the optimal tour finders, so it is suitable for use on a mobile unit. A publicly
available TSP solving package named TspSolve was used for all TSP algorithm im-
plementations.
7.1.3.2 Next Object Access.
This is a heuristic based algorithm. The
strategy is a simple greedy heuristic that always retrieves the next available object
in a broadcast. It is also similar to the Nearest Neighbor approach to solving TSP
problems.
7.1.3.3 Row Scan.
This algorithm simply reads all the objects from one
channel in each pass. Naturally, if a channel does not have any objects in it, it is
skipped. The upper bound execution time is proportion to the number of air channels.
The benefit of this algorithm is that it does not require any time to decide on an
ordering for objects. In addition, it does not require any channel switching during
a broadcast pass. It can thus begin retrieving objects from a broadcast immediately.