||Information Delivery in an Infostation System
|| Christopher Rose
Ana Lucia Iacono
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.
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.
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.
||Ana Lucia Iacono and Christopher Rose,
"Minimizing File Delivery Delay in an Infostation System", Technical Report
TR-167, WINLAB, Rutgers University, August 1998
This page was last updated
November 22, 1999.
Project Index page
Back to WINLAB Home page
If you have
questions, comments or other suggestions, please contact us at