Using Predictive Prefetching to Improve Location Awareness of Mobile Information Service

Gihwan Cho
Division of Electronic and Information Enginccring, Chonbuk Univcrsity, 664-14 Duckjin-Dong, Duckjin-Gu, Chonju, Chonbuk, 561 -756, S. Korca ghcho@[Link]

Abstract. Mobile information scrviccs havc to provide some dcgrcc of information adaptability onto the current service context, such as mobile user's location, network status. This paper deals with a predictive prefetching scheme for reducing the latcncy to gct rcfrcshcd information appropriatcd on currcnt location. It makes use of the velocity mobility model to exploit location knowledge about thc tcrminal andlor uscr's mobility bchavior. With considcring thc uscr's moving speed and direction, the prefetching zone has been proposed to effectively limit the prefetched information into the most likely future location context whilst to prcscrvc thc prcfctching bcncfits. Thc proposcd schcmc has bccn evaluated with a simulator in the context adaptability point of view.

1 Introduction
With prospcrity of hardware tcchnology, computing devices arc gctting small and higher performance. Moreover, by cooperation of the wireless communication with hand-hold computer, computing users can access their own information anytime, anywhcrc, cvcn thcy movc around. Evcn if many cxisting computing scrviccs may bc logically cxtcndcd into this ncw coming computing paradigm, its inhcrcnt charactcristics, such as user, terminal andlor service mobility, require new service methodologies. That is, mobile information services have to provide some degree of information adaptability onto thc currcnt scrvicc contcxt, whcrc contcxt is dcfincd as thc charactcristics of thc uscr's situation likc as currcnt location, and thc uscr supporting cnvironment like as network status (bandwidth, broadcast etc.) and mobile terminal capabilities (size, color etc.). This feature is generally formalized as context-aware mobile information scrviccs [I]. In thc uscr and/or tcrminal mobility cnvironrncnt, location contcxt may bc changcd whilst the user is still interested in the corresponding answer. Therefore, it is required to bc adaptivcly providcd a rcsponsc appropriate to thc currcnt location: a prcviously providcd rcsponsc must bc rcfrcshcd, if thc corresponding request is still activc aftcr a
This work was supported in part by University Research Program of Ministry of Information nd Communication in South Korca, and Ccntcr for Advanccd Imagc and Information of Chonbuk National Univcrsity in South Korca.
P.M.A. Sloot et al. (Eds.): ICCS 2002, LNCS 2331, pp. 11281136, 2002. Springer-Verlag Berlin Heidelberg 2002

Using Predictive Prefetching to Improve Location Awareness 1129

change of location that invalidates the old response [2]. Thus, thc latcncy to get rcfreshed information appropriated on the current context is the most critical service parameter, especially in the frequently context changed environment. With the long latcncy, the uscr may suffcr thc long timc duration provided with information not appropriate for the currcnt location. To rcducc the latcncy, a wcll-cstablishcd tcchnique, prefetching, can be adapted to fetch information in advance, usually based on what contexts are highly utilized [3]. Thus, it is very important to make use of some dcgrcc of knowlcdgc to limit thc amount of prcfctchcd information; othcrwisc, unncccssarily prcfctchcd information can ovcrwhclm the benefit of latcncy rcduction with communication and memory cost. Therefore, prefetching scheme is usually based on some sort of prediction strategy about the information that will be needed in thc ncar futurc. Thc prcdictivc prcfctching concept has bccn applied and evaluated to rcducc thc latency in retrieving a Web document on the wired environment, based on the user's navigation pattcrn [4]. It shows that thc prcdictivc prcfctching rcduccs significantly in thc avcragc acccss timc. The work in [3] providcs the cffcctivcncss of prcfctching policies in the location-aware mobile information services. The work considered only the uniform mobility pattern based on the Markov model, and did not consider how to cffcctivcly confinc thc prcfctching information to rcducc communication cost. In the rcfcrcncc [S], a semantic based caching schcmc has bccn prcscntcd to acccss location dependent data. The work is just centric to the cache information replacement strategy to utilize the semantic locality in terms of location. In this papcr, a prcdictivc prcfctching schcmc is proposcd by cxploiting uscr movcmcnt knowlcdgc to limit thc prcfctching to the most likcly futurc contexts. Bccausc the location is the most distinguished context for the context aware mobile information system, our discussion is limited in location context after this. The rest of the papcr is organized as follows. In Scction 2, a gcncral architccturc of mobilc information scrvicc is prcscntcd, along with the problem definition. In Scction 3, a velocity based mobility model is presented and a predictive prefetching scheme is formalized with the mobility model. Using a simulation, a numerical result is shown in Section 4. Finally a conclusion is given in Section 5.

2 Mobile Information Service

For mobile information service, a general architecture has been utilized to describe the location-aware feature [2], [3], [S], [6], [7]. The architecture consists of 3 logical componcnts; mobilc dcvicc that possibly movcs around with a uscr, information scrvcr that would bc located somcwhcrc in Intcrnct, and location-aware scrvicc manager that acts as intermediary between the mobile device and the information server. The manager performs a sequence of operations to retrieve information associated with the currcnt location from the scrvcr, and to load it on thc uscr dcvicc. To do this, it periodically monitors thc currcnt uscr location, and checks whcthcr it belongs to the current information scope. If an out-of-scope condition is detected, the service manager restarts to retrieve the corresponding information on current location. A mobile uscr is assumcd to cquippcd with a ccrtain mechanism to obtain its currcnt location,

1130 G. Cho

such as thc GPS or indoor infrarcd scnsors. For a given mobile information service, the set of possible location contexts is assumed to be divided into separated subsets, such as rooms, areas. Then a separate piccc of information is associatcd to cach subsct, such as cquipmcnt availablc in a room, map of a givcn arca. A unit arca, which a uscr may movc around with thc samc information piece, is divided into adjacent geographical portions. Each geographical portion has corresponding portion information that must be provided by the information scrvicc as rcsponsc to a uscr's rcqucst within that gcographical portion. Gcographical portions arc assumcd to bc cqual shapc rcprcscntcd as quadrangles. A discrete time model is used for a user's movement. At the end of each time slot, the user can remain in the same quadrangle, or move to an adjacent quadrangle through one of thc sharcd cdgcs. At a ccrtain point of timc, thc choicc of rcmaining insidc or moving outsidc thc quadranglc of a uscr is just dcpcndcd on thc currcnt location and thc moving direction and speed.

Information sewice time) Information acquisition delay) Move detection delay)

Fig. 1. Mobile information service delay on a given geographical portion

Fig. 1. shows thc dclay to gct corrcsponding information for a givcn gcographical portion (the quadrangle stands for a geographical portion). On crossing a geographical portion, thc latcncy can bc classified with two timc factors; thc dclay nccdcd to dctcct that thc providcd portion information is out of its currcnt contcxt, so to : movc detection delay, and the delay needed to retrieve and start loading the new information for current geographical portion, so t,: information acquisition delay. By reducing two dclays, a rnobilc uscr can bc blcsscd cnough with thc currcnt contcxt information, so t2: information scrvicc timc. Thc cffcct of thc first factor can bc improvcd by reducing the time interval between two consecutive location checks. The most common technique to improve the second factor is to prefetch information that will be rcquircd in thc ncar futurc. With thc practical rcquircmcnts such as communication and storagc limitation of rnobilc dcvicc, thc amount of prcfctchcd information must be minimized as much as possible, whilst the prefetching amount reduction must not hurt the prefetching benefits.

Using Predictive Prefetching to Improve Location Awareness 1131

3 Mobility Model and Predictive Prefetching

At a givcn location, thc uscr's futurc location can bc rclativcly rcprcscntcd by thc moving direction and speed. Therefore, the moving behavior of mobile users can be now modeled from 3 parameters, current location, moving speed and direction. 3.1 Velocity based Mobility Model To model both the direction and speed of a moving user, a velocity Vis defined as a >, where I/, and 1 are integers. A pair of values, 1/, and 4, is the : vector < I/,, projcctions of its spccd vcctor on x axis and y axis rcspcctivcly (in practically, cach axis can stand for the east or the north respectively). The signs of l/, and I/,, and the ratio of the absolute value of I/, and that of determine the directions of the movemcnts. Thc modcl assumcs that a uscr movcs around in a 2-dmcnstional spacc at a spccd that kccps constant during any obscrvcd time period and may changc aftcr a given unit time. So, at a certain point of time, when a user's current location has been given, the location in the future can be specified by considering the movement velocity. This conccpt has bccn mostly borrowcd from [ 5 ] .

3.2 Predictive Prefetching Strategy Generally, a natural prefetching strategy is to prefetch the portion information corresponding to a sct of gcographical portions that arc within a ccrtain dcgrcc of outbound distancc d from thc currcnt location. Thcsc gcographical portions consist of a prefetching zone (shortly PZ). To form a PZ, one possible strategy is to include all the quadrangles within outbound distance d fraction (so, radius d) of rings 0, 1, 2, .. .n [3]. No rcmotc loading is ncccssary unlcss thc uscr movcs around within its currcnt PZ. Whcn thc uscr cntcrs a portion outside its currcnt PZ, thc gcographical portion becomes the new starting position to build a new PZ. The new PZ may include the portion information for quadrangles within distance d ring. Hcrc, our conccrn is to cxploit somc dcgrcc of prcdiction about thc uscr bchavior, in ordcr to bc prcfctchcd only thc information for most likcly futurc contcxts. Whcn a user crosses a PZ, the moving speed is applied to estimate the distance d, and the moving direction is utilized to decide the width w of PZ. Now, a PZ shapes as a rectangle [7], rathcr than a ring. This is bascd on that, if a uscr movcs with high spccd, it would bc vcry rcasonablc to sct thc distancc higher than that of low spccd movcmcnt. Similarly, if a user's behavior tends to move with high degree of obliquity, it would bc vcry rcasonablc to sct thc width widcr than that of low dcgrcc of obliquity. Our stratcgy to prcdictivc prcfctching is as follows. Thc distancc d of a rcctanglc PZ is to get the upper bound integer of the user's speed, that is, the squared root of the as Thus, the signs of sum of squares of two speed values Y, and 6, speed values should be ignored because the distance considers the speed characteristic only. In addition, if onc of spccd valucs is zcro, it must bc rcplaccd with thc othcr

1 .-

1132 G. Cho

non-zero value. Similarly, the width w of a rectangle PZ can be obtained with the upper bound integer of the mean value of the sum i f two speed values, V. and , that is . Note that the signs of speed values should be ignored because the direction reflects the degree of obliquity-rather than that of dimension. Differently with the distance, zero valued speed will be ignored in the width. Fig. 2. shows an example for the predictive prefetching reconstruction idea for three different moves. The dark rectangles depict the new PZ that is constructed on each crossing of the PZ. For each moving with the velocity 12, 1>, <3, 5> and <5,0>, the size of PZs is calculated as the distance d = 3,6 and 8, the width w = 2,4 and 3 respectively.
vxI+

Iv,I

Fig. 2. A predictive prefetching reconstruction example

As shown in the Fig. 2., the gap between the PZs is inevitable. The location aware manager may start to build a new PZ and to prefetch the new PZ, just after it finds out the fact of crossing the current PZ, so the move detection delay in Fig. 1. Then, until the device is refreshed with information for the new PZ, so the information acquisition delay in Fig. 1., the mobile user therefore does not have any information appropriate to its current context. Due to the mobility feature, the user is in the out-of-scope condition of an effective information service. This situation can be improved with defining the edge geographical portions of a PZ into the crossing zone; it should be also defined with considering its moving speed and direction. When a user meets a geographical portion in the crossing zone, it starts to prefetch the new PZ in advance.

Using Predictive Prefetching to Improve Location Awareness 1133

4 Numerical Result
In order to provide the cffcctivcncss of proposed scheme, a comparison has bccn made between the ring PZ approach and the rectangle PZ one, through a simulation study. For simulation runs, a set of system parameters has been borrowed from other works, as shown in Table 1. Some numerical result has bccn measured for the amount of prcfctchcd portion information, the ratio of utilization of the prcfctchcd portion information, and the service time for end user. The first is significant to reduce the communication cost, the second stands for how much the prefetched portion information is made use of rcal information scrvicc, and the last is meaningful to configure thc uscr's satisfaction for thc scrvicc. The simulator has bccn implcmcntcd in C language using an event-based simulator CSIM [8].
Table 1. System paramctcrs for simulation Parameter Wired bandwidth L4'ircles bandnidth Movc dctcction time
I

Description bandwidth of the wired line

I

Value 800 kbps - 1.2 Mbps 100 ms

I bandwidth ol'thc \~~ircIcss medium 1 80 kbps - 120 kbps

1 time
to detect the fact a user

4.1 User Move Scenario

In the velocity based mobility model, a user moves around in a 2-dmenstional portion's geographical space at a spccd that kccps constant during any givcn unit timc pcriod. Thcn it changes its spccd and dircction, and moves constantly within the unit time. Therefore, the model is much significant when a user's moving pattern is uniform. Practically, this is analogous to many rcal life cases, such as driving a car on highways or walking a street. A typical uscr move sccnario has bccn utilized for the simulation. A user moves around 20 by 20 geographical portions, as shaped in Fig. 2. It starts from the position (10, lo), and moves 20 times, sequenced as (2, -4), (3,2), (3,4), (-5, O), (2, -51, (-3, -3), (5, - 4 , (0, 31, (4, - 4 , (-1, 3), (3, 3), (0, 51, (-2, 5), (-3, 01, (-5, -21, (5, -2), (-5, O), (-2,4), (-3, -61, (4, -5).
4.2 Simulation Experiments

With the givcn uscr mobility sccnario, the numbcr of prcfctchcd portion information has been evaluated to show the effectiveness of prefetching strategies by comparing three different cases; prefetching with ring PZ, prefetching with rectangle PZ, pre-

1134 G. Cho

fetching is not applied. The same simulation parameters are used for each case, whilst different strategies are used to build a PZ. For the prefetching with ring PZ, radius of some degree of fairness the ring is a critical simulation parameter. In order to provide -

Y is adapted for : with that of prefetching with rectangle PZ, the speed value calculating the radius of ring PZ. Fig. 3. shows the number of prefetched portion information for each cases. The prefetching with ring PZ has relatively large variation depending on the speed value. Thus, some of portion information would be overlapped between that of the previous PZ and that of the current PZ. After excluding these overlapped portions, 1,105 portions are totally prefetched for the ring PZ strategy, and mean number of prefetched portion information is 55.25 for each move. In the rectangle PZ scheme, the number of prefetched portion information is stable; total number of prefetched portion information is 335, mean number of prefetched portion information is 16.75. In the case of prefetching is not applied, each portion information has to be acquired for every geographical portions in turn, on the path of the user moves through.
1 1 1 1 1 1 1 1 1

prefetching with ring PZ prefetching with rectangle PZ ~refetchmg not applied is

1 1 1 I 1 1 l 1 1 1 l 1 1 1 1 1 1 1 1 1 1 1 ~ ~ ~

1 2

10 11 12 13 14 15 16 17 18 19 20

Fig. 3. The number of prefetched portion information

Now, it is meaningful to figure out how much the prefetched portion information would be actually participated for the user's location-aware service. Fig. 4. shows the utilization ratio of prefetched portion information for two prefetching strategies, so the ring PZ and the rectangle PZ. Note that the utilization ratio is just depended on the user's mobility pattern. With the given user move scenario, the utilization of rectangle PZ is much better than that of ring PZ; the former shows that over 30% of prefetched portion information is utilized for real service, whilst the later figures around 10%. We believe that the predictive prefetching with considering the user's move behavior plays great role in building a prefetching method for mobile information service.

dv:

move sequence

Using Predictive Prefetching to Improve Location Awareness 1135

move sequence
Fig. 4. Utilization ratio of the prefetched portion information

Fig. 5. shows the service time which has been spent to provide the corresponding information on each move. In the case of the prefetching is not applied, the time can be obtained by adding the service delay for getting each of portion information that the user has visited. So, mean service time is 570 sec. for each PZ. With the rectangle PZ strategy, the service delay is applied for only when a user crosses the current PZ. Once the service delay has been given on the portion, the other portion information within current PZ would be delivered in concurrently during the first portion information is serviced to end user. So the delay is the same for getting one of portion information on crossing PZ, and can be reduced as about 95 sec.

move sequence

Fig. 5. Information service Time

1136 G. Cho

5 Conclusion
In thc location awarc mobile information scrvicc, prcfctching has a tradcoff bctwccn the amount of information transferred and the time delay to get the current context. In this paper we proposed a predictive prefetching scheme to limit the prefetched portion information to thc most likcly futurc contcxts, whilst to prcscrvc thc prcfctching bcncfits. This has bccn achicvcd by defining the prcfctching zonc with distancc and width based on the user's moving behavior, that is, speed and direction. Using a simulator, the effectiveness of the proposed prefetching strategy has been measured with rcspcct to thc scrvicc cffcctivcncss. Thc proposcd prcfctching with rcctanglc PZ was highly bcncficial for both the prcfctchcd data amount as well as the latency reduction. The idea in this paper is expected to be able to be extended to the other mobile server contexts, such as network bandwidth, mobile device type.

References
1. Brown, P. J., Bovey, J. D., Chen, X.: Context-aware Applications: From the Laboratory to the Marketplace. IEEE Personal Communications, Vol. 4, No. 5 (1997) 55-65 2. Couderc, P., Kermarrec, A. -M.: Improving Level of Service for Mobile Users Using Context-Awareness. Proc. 18th IEEE Symp. on Reliable Distributed Systems (1 999) 24-33 3. Persone, V. N., Grassi, V., Morlupi, A.: Modeling and Evaluation of Prefetching Polices for Context-Aware Information Services. Proc. ACM Conf on Mobile Computing and Networking (1998) 55-65 4. Padmanabhan, V. N., Mogul, J. C.: Using Predictive Prefetching to improve World Wide Web Latency.-ACM Computer Communication Review, Vol. 26, No. 3 (1 998) 22-36 5. Ren, Q., Dunham, M. H.: Using Semantic Caching to Manage Location Dependent Data in Mobile Computing. Proc. ACM Conf. on Mobile Computing and Networking (2000) 21022 1 6. Kovacs, E., Rohrle, K., Schiemann, B.: Adaptive Mobile Access to Context-aware Services. Proc. 1st Symp. on Agent Systems and Applications (1999) 190-201 7. Kim, M. J., Cho, G. H., Cho, I. J.: A Prefetching Scheme for Context-Aware Mobile Information Services, Proc. 3rd Conf. on Advanced Communication Technology (2001) 123-125 8. Mesquite Software Inc.: CSTMI 8 Simulation Engine (1997)