Purpose:
The Infostation network consists of many base stations, each with a small and discontinuous coverage area. The radios transmit at very high bit rate and it is possible to download a significant amount of information even when the mobile station is in the coverage area for a short time. Therefore, if the information is available at the Infostation, the user will be able to receive it with a very short delay. However, this may not always be the case and the information may have to be transferred from the server and pass through the fixed network before reaching the mobile. Since the coverage area is small, the short time the mobile spends in the coverage area may not be sufficient to bring the information from the server to the Infostation. This is the reverse of the usual wireless problem, in which the radio is the main concern since there are many users being served by the same base station. In this problem the bottleneck of the network is actually the backbone and not the radio. The goal of this project is to derive a delivery schedule for file parts that minimizes overall delay in receiving the whole file.

Approach:
We consider a system where the Infostations are connected as a cluster in a hierarchy where there is a higher level with a cluster controller. As mentioned before, even though the radio rate is high, the coverage area is small and the short time the mobile spends in the coverage area may not be sufficient to bring the information from the server to the Infostation. To overcome this problem the cluster controller can coordinate the delivery to the next Infostation in the mobile path, so that the information is locally available at that Infostation when the mobile user arrives in its coverage area. If the path is not known then the cluster controller can send the information to Infostations that are most likely to be in the mobile user path.

Status:
The case of a single user with fixed velocity was studied first. The interesting result is that a higher aggregate delivery rate is possible for a user in motion than for one who dwells at a single Infostation. Then a random walk with fixed velocity but random travel direction was investigated. We derived bounds on minimum delivery delay for a variety of Infostation geometries. These were the one-dimensional highway scenario, the two-dimensional street grid and the three-dimensional street grid with tall buildings. A heuristic algorithm for the one-dimensional case (single user) was proposed and simulation results show that the algorithm is near optimum (minimum delay). We are currently working with the multiple user case. Results for two users with fixed velocity show that the scheduling algorithm that minimizes the average delay gives priority to one of the users. This result is similar to what we see in conventional scheduling algorithms where to minimize the average delay the jobs are scheduled in order of non-decreasing processing time, what is called shortest-processing-time sequencing.

Related Publications: