4. A NEAR-OPTIMUM ALGORITHM

In the last two sections we presented bounds on file delivery for a general n-dimensional model. Those results give bounds on the maximum number of file segments that can be downloaded for the user in the case where R _i>N R _b and R _r>M R _b and were derived assuming that an optimum algorithm is used. But it does not tell us how such an algorithm would work. Therefore, in this section we will provide an algorithm for the one-dimensional case. Given that the file can be divided in many different smaller segments, and we label each segment, the role of the algorithm is to decide after every step which segments should be sent to which infostations. As always, the goal is to minimize the overall file transfer delay.

4.1 OVERVIEW

We will concentrate in the one-dimensional scenario, as shown in Figure 1.21, where infostations are equally spaced at distance d.

Figure 1.21: The One-dimensional Model

Assume a file of size F, and this file is divided in N segments of size B, where

(1.65)

and

(1.66)

Given that the mobile is at some position x, an algorithm that delivers file segments to infostations around that user will have to deliver segments to a given number of infostation to the right and left of the mobile. Therefore our algorithm will work in a range of infostations. The first important characteristic of the algorithm is the calculation of...