Note: Descriptions are shown in the official language in which they were submitted.
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
-1-
METHOD AND APPARATUS FOR DETECTING AND
PREDICTING MOTION OF MOBILE TERMINALS
BACKGROUND
Applicants' invention relates to systems and methods for predicting
movements of mobile radio transceivers, such as mobile cellular telephones.
A fundamental shift is occurring that is moving mobile communication
and computing together into one synergistic activity - mobile computing - a
new
dimension in mobile communication networks. Future mobile communication
systems will support electronic mail, database and file accessing services,
and
multimedia services in addition to ordinary voice communication.
Due to non-uniform traffic patterns of mobile terminals in different
geographical areas, a layered, or hierarchical, cell architecture is a
promising
solution for future mobile communication systems. In general, a hierarchical
cell
structure comprises orthogonal cell layers of different cell typeslsizes,
covering a
common geographical area. A hierarchical cell structure is commonly made up
of macrocells overlying microcells and picocells, which are distinguished by
their
spatial extent, among other characteristics. For example, a picocell is an
area
having a number of channel groups or an identical code, and the nominal cell
radius of a picocell is often less than 200 meters. In a layered communication
system, the communication bandwidth of a picocell, which is commonly indoors,
can be up to 2-10 megabits per second (Mbls), while the communication
bandwidth of a macrocell is on the order of IO-100 kilobits per second (Kb/s).
Nevertheless, many challenging issues must be solved to support user-
transparent, continuous communication for both speech and data across the
boundaries of the different cell layers. The connectivity and configuration of
such wireless networks is highly dynamic because the mobile terminals can
change positions and their radio environments can change at any time. Also,
due
to the large differences in bandwidth between the cell layers, the
communication
networks currently available are not transparent for mobile data users.
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
-2-
Conventional data caching and prefetching techniques are not efficient in this
environment.
Caching and prefetching are commonly used for improving system
performance in large-scale distributed computing systems. Measurements
indicate that even small caches provide substantial benefits. Caches not only
can
reduce latency but also can greatly reduce the volume of network traffic as
well
as the number of server utilizations in a client-server system. Prefetching is
complementary to caching, and successful prefetching of data to the local
cache
will increase the cache hit-rate, i.e., how frequently requested data is found
in
the cache.
The idea of using caches to reduce latency and network traffic is based on
the properties of temporal locality of data accessing patterns of computer
programs. This is described in D. Lilja, "Cache Coherence in Large-Scale
Shared-Memory Multiprocessors: Issues and Comparisons," ACM Computing
Surve s vol. 25, no. 3, pp. 303-338 (Sept. 1993). Temporal locality means that
data recently accessed by a program are likely to be accessed again in the
near
future. Thus, a local copy, or cache, of the remote data that have recently
been
accessed is maintained so .that repeated accesses to the same data can be
handled
locally without additional network traffic. With a well-managed cache, a
substantial amount of remote data can be accessed with virtually the same
efficiency as local data.
On the other hand, the existence of the multiple copies of shared data
introduces a problem of maintaining consistency of the copies that is
discussed in
the above-cited Lilja publication. When cached data are modified, the changes
must be effected in all copies, local and remote, of that data. Various cache
coherence schemes can be used to keep the copies consistent according to the
data sharing semantics used, but maintaining cache consistency in distributed
systems is a very complicated problem involving a tactical balance between
consistency, transparency, and network traffic volume.
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95101198
-3-
Prefetching is another useful technique in distributed computing systems
that uses knowledge about expected needs for remote data. The remote data is
prefetched to a client, viz. , fetched before the remote data are actually
requested.
The knowledge of expected needs can be determined from the client's past
behavior. For example, working-sets of files are often prefetched in
distributed
file systems, and the working-sets are determined based on knowledge of the
client's file access pattern. Another common prefetch method uses spatial
locality, which refers to the high probability that a client will need data
stored at
addresses or pages that are neighbors of data already needed.
Current networks are not efficient in wireless data accessing in that they
do not support data and service mobility. While users and terminals are
mobile,
their data is still configured statically in the system. Traditionally,
personal/terminal mobility management included passive functions for keeping
track of the locations of the users/terminals and for maintaining connections
to
the terminals belonging to the system.
Also, due to the large differences in data communication bandwidth
between cell layers, the communication system is not transparent for mobile
data
users. In other words, different cell layers have large differences in
performance
for mobile data users. Conventional cache and prefetch management techniques
are mainly designed for fixed data communication networks, and are inefficient
in a communication environment, such as a cellular radiotelephone system, in
which the communication channels are unpredictable and highly variable with
time and location.
The issue is how to improve network performance in a hierarchical cell
system, and especially how to make network utilization and management more
intelligent in balancing network traffic and dynamic channel allocation, how
to
make intelligent data caching and prefetching management in the mobile
environment, and how to provide efficiently wireless data access.
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
Accordingly, techniques that can predict the motion (or itinerary) of a
mobile terminal user are needed for supporting connection handovers, or
handoffs, between the different cell layers with high integrity.
SUMMARY
These problems are solved by Applicants' invention, which provides
methods and apparatus for predicting movements of mobile radio transceivers.
In this way, Applicants' invention achieves the important objects of improving
performance of a hierarchical communication network, improving network
utilization and management in balancing network traffic and dynamic channel
allocation, and improving data caching and prefetching in a cellular mobile
communication network.
In one aspect of Applicants' invention, a method of predicting a next
location of a mobile terminal based on stored previous locations of the mobile
terminal includes the step of comparing a current sequence that includes the
current location of the mobile terminal and a plurality of previous locations
of
the mobile terminal to each of a plurality of stored sequences that each
include
previous locations of the mobile terminal. The method also includes the steps
of
selecting one of the stored sequences based on at least one quantitative
measure
of a degree of matching between the current sequence and each stored sequence,
and predicting the next location of the mobile terminal based on the selected
one
of the stored sequences.
In another aspect of Applicants' invention, a method of predicting
movements of a mobile terminal includes the steps of (a) comparing a current
sequence that includes the current location of the mobile terminal and a
plurality
of previous locations of the mobile terminal to each of a plurality of stored
sequences that each .include previous.locations of the mobile terminal;
(b) determining at least one quantitative measure of a degree of matching
between the current sequence and each stored sequence; and (c) if the at least
one
quantitative measure exceeds a predetermined value, using the locations of the
CA 02203623 1997-04-24
WO 96113951 PGT/SE95/01198
-5-
respective stored sequence as predictions of the movements of the mobile
terminal.
In another aspect of Applicants' invention, a method of determining
regular patterns in movements of a mobile terminal includes the step of
comparing a current location of the mobile terminal to each of a plurality of
previous locations stored in a queue of a plurality of previous locations, the
previous locations being stored in the queue in first-in-first-out order of
occurrence. The method also includes marking a sequence of locations
comprising the current state, the previous location that matches the current
location, and the previous locations that occurred after the previous location
that
matches the current location, if the current location matches one of the
plurality
of previous locations stored in the queue. The method also includes comparing
the marked sequence to each of a plurality of stored sequences of locations
and
determining at least one quantitative measure of a degree of matching between
the marked sequence and each stored sequence, and increasing a priority
parameter'of the respective stored sequence by a predetermined amount if the
at
least one quantitative measure exceeds a predetermined value.
Such a method may further include the steps of storing the current
location of the mobile terminal in the queue in first-in-first-out order of
occurrence, determining whether the current location is at least one of a
stationary state and a boundary state, and carrying out the other steps if the
current location is at least one of a stationary state or a boundary state.
In another aspect of Applicants' invention, a method of determining
regular patterns in movements of a mobile terminal includes the steps of
(a) determining whether a current location of the mobile terminal is one of a
stationary state and a boundary state; (b) marking a sequence of locations
comprising the current location, one of the most recent previous stationary
state
and the most recent previous boundary state, and previous locations that
occurred
between the one of the most recent previous stationary state and the most
recent
previous boundary state; (c) comparing the marked sequence to each of a
CA 02203623 1997-04-24
WO 96/13951 PCTISE95/01198
-6-
plurality of stored sequences of locations and determining at least one
quantitative measure of a degree of matching between the marked sequence and
each stored sequence; and (d) if the at least one quantitative measure exceeds
a
predetermined value, increasing a priority parameter of the respective stored
sequence by a predetermined amount.
Such a method may further include the step of storing the current location
in a queue of a plurality of the previous locations, the locations being
stored in
the queue in first-in-first-out order of occurrence, and carrying out the
other
steps if the current location is at least one of a stationary state and a
boundary
state.
In such methods, the plurality of stored sequences may include movement
circles and movement tracks, and the one of the stored sequences may be
selected based on a ratio of a number of locations in the current or marked
sequence that are the same as locations in a stored sequence and a total
number
of locations in the current or marked sequence. Also, the one of the stored
sequences may be selected based on a quantitative measure of a degree that a
duration of the current or marked sequence matches a duration of each stored
sequence and on a quantitative measure of a degree that a frequency of the
current or marked sequence matches a frequency of each stored sequence.
In other aspects of Applicants' invention, an apparatus for predicting a
next location of a mobile terminal based on previous locations of the mobile
terminal, and apparatus for determining regular patterns in movements of a
mobile terminal are provided.
For example, an apparatus for predicting a next location of a mobile
terminal based on previous locations of the mobile terminal includes a memory
for storing sequences of previous locations of the mobile terminal, and a
device,
in communication with the memory, for comparing a current sequence that
- includes the current location of the mobile terminal and a plurality of
previous
locations of the mobile terminal to each of a plurality of stored.sequences.
The
apparatus further includes a device for selecting one of the stored sequences
CA 02203623 1997-04-24
WO 96/13951
PCT/SE95/01198
_~_
based on at least one quantitative measure of a degree of matching between the
current sequence and each stored sequence, and a device for generating a
prediction of the next location of the mobile terminal based on the selected
one
of the stored sequences.
In such an apparatus, the plurality of stored sequences may include
movement circles and movement tracks, and the selecting device may include a
device for determining a ratio of a number of Iocations in the current
sequence
that are the same as locations in a stored sequence and a total number of
locations in the current sequence. One of the stored sequences is selected
based
on the ratio. The selecting device may further include a device for generating
a
second quantitative measure of a degree that a duration of the current
sequence
matches a duration of each stored sequence, and a device for generating a
third
quantitative measure of a degree that a frequency of the current sequence
matches a frequency of each stored sequence. The one of the stored sequences
may be selected based on the ratio and the second quantitative measure or on
the
ratio, the second quantitative measure, and the third quantitative measure.
In yet another aspect of Applicants' invention, a communication network
comprises a plurality of servers, the servers being positioned in respective
geographical areas and organized in a distributed file system; a mobile
terminal
having a device for communicating with the server nearest the mobile terminal,
wherein the communicating device accesses application files and data files
stored
in the servers; and a mobile distributed system platform having a device for
controlling the distributed file system of the servers and a device for
predicting a
next location of a mobile terminal, wherein the controlling device distributes
location sensitive information among the servers based on a next location
predicted by the predicting device.
BRIEF DESCRIPTION OF THE DRAWINGS
The features and advantages of Applicants' invention will be understood
by reading this description in conjunction with the drawings, in which:
CA 02203623 1997-04-24
WO 96/13951 PGTlSE95/01198
_$_
Fig. 1 is an exemplary hierarchical, or mufti-layered, cellular system;
Fig. 2 is a block diagram of an exemplary cellular mobile radiotelephone
system, including an exemplary base station and mobile station;
Fig. 3 is an illustration of mobile motion in a hierarchical communication
system;
Fig. 4 illustrates Applicants' mobile motion predictor MMP;
Fig. 5 illustrates how a user moves through various states that are
grouped in movement circles;
Fig. 6 illustrates how states are grouped in movement tracks;
Fig. 7 illustrates the operation of an itinerary pattern detector and the data
structures generated in an itinerary pattern database;
Fig. 8 is a flowchart of a movement circle detection method in accordance
with Applicants' invention;
Fig. 9 is a flowchart of a movement track detection method in accordance
with Applicants' invention;
Fig. 10 illustrates the operation of a motion predictor;
Fig. 11 illustrates the tree-like structure of a motion prediction method;
Fig. 12 illustrates an example of how a user moves through various states
as a function of time;
Figs. 13a, 13b illustrate an example of constitutional constraints used in
the matching process;
Fig. 14 is a flowchart of a mobile motion predictor in accordance with
Applicants' invention;
Fig. 15 shows an example of normalized results of a simulation of
Applicants' mobile motion predictor; and
Fig. 16 illustrates a mobile floating agent and a mobile distributed system
platform agent employing Applicants' mobile motion predictor; and
CA 02203623 1997-04-24
WO 96/I3951
-9-
DETAILED DESCRIPTION
PCT/SE95/01198
Most people, including the majority of mobile terminal users, have
regular patterns of movement that they follow more or less every day of the
week. Applicants' invention .uses this regularity in everyone's movements to
predict one's next location. For example, if a mobile user is on the way out
of
an area covered by a picocell (or a microcell), the mobile (or the network)
can
predict this change of location and inform the network to prefetch data, if
necessary.
Using Applicants' invention, a mobile terminal or the communication
network can predict the mobile's itinerary and take appropriate actions before
the
mobile reaches a new location. Such predictions can also be used for dynamic
channel allocation, mobile terminal location, and call handoffs from channel
to
channel, either infra-cell or inter-cell, inter-layer or infra-layer. The
predictions
can be inputs to a locating algorithm, which generates a list of candidate
communication channels for handover or assignment of a connection. As used in
this application, the term "mobile terminal" will be understood to encompass
mobile telephones, portable computers, mobiletexts, personal digital
assistants,
and like devices.
Fig. 1 is an exemplary hierarchical, or mufti-layered, cellular system. An
umbrella macrocell 10 represented by a hexagonal shape makes up an overlying
cellular structure. Each umbrella cell may contain an underlying microcell
structure. The umbrella cell 10 includes microcell 20 represented by the area
enclosed within the dotted line and microcell 30 represented by the area
enclosed
within the dashed line corresponding to areas along city streets, and
picocells 40,
50, and 60, which cover individual floors of a building. The intersection of
the
two city streets covered by the microcells 20 and 30 may be an area of dense
traffic concentration, and thus might represent a hot spot.
Fig. 2 represents a block diagram of an exemplary cellular mobile
radiotelephone system, including an exemplary base station 110 and mobile
station 120. The base station includes a control and processing unit 130 which
is
CA 02203623 2005-10-05
WO 9GlI3951 PCTJS)r9510I198
AMENDED PAGE
-10-
connected to a mobile switching center (MSC) 140 which in turn is connected o0
a public switched telephone network (PSTI~ (not shown).
The base station 110 handles a plurality of voice channels through a voice
- channel traraceivtr 150, which is controlled by the control and processing
unit 130. Also, each base station includes a control channel transceiver 160,
which may be capable of handling more than one control channel. The control
channel transceiver 160 is controlled by the control and processing unit 130.
The control channel transceiver 160 broadcasts control information over the
I5 control channel of the base station or cell to mobiles locked to that
control
channel. h will be understood that the transceivers 150 and 160 can be
implemented as a single device, like the voice and control transceiver 170,
for
use with digital control and traffic chanruels that share the same radio
carrier
frequency.
The mobile station 120 receives the information broadcast on a control
channel at its voice and control channel transceiver 170. Then, the processing
emit 180 evaluates the received control channel information, which includes
the
characteristics of cells that are candidates for the mobile station to lock on
to,
and determines on which cell the mobile should lock. Advantageously, the
received control channel information not only includes absolute information
concerning the cell with which it is associated, but also contains relativa
information concerning other cells pro~cimate to the eel! with which the
control
channel is associated,
CA 02203623 1997-04-24
WO 96!13951 PCT/SE95/01198
-11-
An example of a mobile terminal's movement pattern is shown in Fig. 3.
A mobile user A moves through an area covered by a hierarchical cell
architecture, which includes a picocell system having 2 Mb/s communication
bandv~ridth and a macrocell system, such as a GSM system, having a bandwidth
of 9.6 Kb/s for data transmission. The user A entered one of the picocell-
covered areas through door D, and moved about inside the picocell-covered area
(which may be inside a building) for a period of time. The user A entered
room L, moved to conference room C, and then left the first picocell-covered
area through the door D, entering the macrocell-covered area, as shown in the
figure. The user A moved through the macrocell-covered area to another
picocell-covered area, entering through another door B and moving about within
that area.
In accordance with one aspect of Applicants' invention, user A's itinerary
would be recorded as it happens by a Mobile Motion Predictor (MMP) in
user A's mobile terminal or in the network. When user A moves with a certain
velocity to the point M from room C or room L, the MMP would indicate a high
probability that user A will move out of the high-bandwidth, picocell-covered
area. The MMP would inform other systems and applications to take appropriate
action, such as dynamic channel allocation and data.prefetching, if necessary,
before user A is out.
As illustrated by Fig. 4, Applicants' MMP comprises an itinerary pattern
detector IPD, an itinerary pattern database IPB, and a motion predictor MP.
The
IPD is used for detecting the regular itinerary patterns (IPs) in a user's
movements between locations, or states, and for saving the IPs into an
itinerary
pattern database (IPB). In general, the IPB also includes predetermined
infornnation relating to the constitution, or physical structure, of the
communication system, as described in more detail below. , The MP uses the
itinerary pattern information stored in the IPB for predicting the next
location, or
state, of the user. The MP also compares its predictions to the actual next-
states
of the user and updates the IPs stored in the IPB.
CA 02203623 1997-04-24
WO 96/13951
PCT/SE95IQ1198
-12-
The input data provided to the MMP are the IAs, or states, in which the
mobile is located, and it is currently believed that the system should
continually
check for a new state with a predetermined period, e.g., every I-5 seconds. It
will be appreciated that the IAs identify the locations of the mobile, i.e.,
the cells
where the mobile has been and is located. Thus, the IAs can have any suitable
form, such as code numbers in a Code Division Multiple Access (CDMA)
communication system, or cell locations in a Time Division Multiple Access
(TDMA) communication system like the GSM system used in Europe and the
AMPS system used in North America. The itinerary patterns, or sequences of
IAs, are stored in the IPB, which is accessed by the motion predictor MP.
Three classes of matching schemes are used for correlation analysis of
. MCs or MTs. First-class matching, or state-matching, indicates the degree
that a
sequence of states matches another sequence of states having a similar length;
it
is quantified by a first-class matching index that is described below. Second-
class matching, or velocity- or time-matching, indicates the degree that the
duration of a sequence of states matches the duration of another sequence of
states having a similar length; it is quantified by a second-class matching
index
that is described below. Third-class matching, or frequency-matching,
indicates
the degree that the frequency of a sequence of states matches the frequency of
another sequence of states having a similar length; it is quantified by the
third-
class matching index that is described below.
Before describing Applicants' invention in more detail, it will be helpful
to note the following concepts and abbreviations.
boundary MC (BMC): a movement circle,(MC) in which at least one
state is a boundary state; a BMC has a higher priority than an MC, with a
boccndary priority parameter B.
boundary MT (BMTj: a movement track (MT) in.which at least one state
is a boundary state; a BMT has a higher priority than an MT, with the boundary
priority parameter 13.
boundary state (BS): a state at the boundary of a cell layer.
CA 02203623 1997-04-24
WO 96/13951
-13-
FIFO: first in, first out.
PCT/SE95/01198
forked state (FS): a joint state for which the following states are in _
distinguishable movement circles.
idenriry area (IA): ~a cell or group of cells sending (broadcasting) .
identified information to an area covered by the cell or group of cells.
itinerary pattern base (IPB): an information database including a
maximum number M of itinerary patterns.
joint state (JS): a state included in at least two distinguishable movement
circles.
LRU: least recently used.
movement circle (MC): a circle having n (where n > 1) sequential states
including at least one stationary state.
movement track (MTj: a track that begins and ends with a stationary state
or a boundary state.
pointer state (PS): a state in a state-queue that contains a pointer pointing
to a saved MC or MT in an IPB.
p: the priority parameter, indicating the priority of an MC or MT.
state (S): a user location, i.e., an identity area IA, in a movement pattern
(or motion graph), where Sk,~ indicates state k at time t (current time).
state queue (SQ): a queue of states saved in temporal order of
occurrence.
stationary state (SS): a state (IA) in which a mobile terminal has stayed
for at least a period of time r.
Tm~: the period of an MC, given by. t" - t1, the time interval between the
first and last states in the MC.
transitional state (TS): a state in which a mobile terminal has stayed for
less than a period of time r.
rb: a time criterion for identifying a BS.
rf: a time criterion for identifying a SS.
CA 02203623 1997-04-24
WO 96/13951
-14-
PCT/SE95/01198
In accordance with Applicants' invention, the IPD is grounded on two
basic procedures: a movement circle (MC) model and a movement track (MT)
model. The MC model addresses long-term, regular user movements, which are
assumed to take the form of closed loops, or circles, of states. The MT model
addresses routine movements, which are assumed to take the form of linear
tracks of states.
The MC model is based on the assumption that when a user moves from a
location, the user will eventually return. Thus, the movements of a mobile
terminal user are modeled as different circle-like patterns, examples of which
are
shown in Fig. 5. The states are represented by circles identified by the
numbers
1-27, 29-35 which indicate the identity areas IA corresponding to the states.
From the figure, it can be seen that an MC is a closed loop, or "circle", of
states
having a duration Tm~ and including at least two states and at /east one
stationary
state. Applicants' MMP determines that a state is a stationary state by
applying
the following criterion: if the IA signal (the input state) provided to the
MMP
has not changed during a predetermined period of time TS (e.g., TS >_ five
minutes), then the state Sk,~ is a stationary state.
Looked at in a different way, each movement circle is a sequence of
states, e.g.-,~-[1, 16, 17, 18, 21, 20, 19, 18, 1]. It will be understood that
when
considering a movement circle, one must move around the circle in a known
direction because the order of the states may differ for different directions.
Also, associated with each MC are an LRU priority parameter p, which indicates
the priority of the MC with respect to other MCs in the IPB, a frequency
parameter F, which indicates the frequency of the sequence of states (see
Fig. 12), and a boundary priority parameter 13, all of which are initialized
to zero
for each new MC. A "new" MC is detected by comparing an incoming MC to
each of the MCs already stored in the IPB. If the new MC's first-class
matching
index ~, which is described in more detail below, matches the index ~c of one
of
the stored MCs, the priority factor p of the stored MC is increased by 1.
Otherwise, the new MC is stored in the IPB with the initial values of
CA 02203623 1997-04-24
WO 96/13951
-15-
PCT/SE95/01198
p = F = 13 = 0. If one or more states in an MC is a boundary state, that MC is
called a boundary MC and has its boundary priority parameter fi increased by
1.
Applicants' MMP determines that an input state is a boundary state by
applying ~orie of the following criteria: either. (1) if no input IA signals
have been
received for a predetermined period of time rb (e.g., Tb >_ five minutes),
then the
state Sk,~_~, is a boundary state; or (2) if no input IA signals have been
received
after the predetermined period of time rb (e.g., rb >_ five minutes) and a new
IA
signal (state Sk+~.~ has been received, then the state Sx+l.r is a boundary
state.
Using the MT model, the IPD generates movement tracks, which are
itineraries that each begin and end with either a stationary state or a
boundary
state. In that closed loops of states are not required, the MT model is a less-
constrained version of the MC model. Six examples of MTs are shown in Fig. 6
that are derived from the MCs shown in Fig. 5, and it will be noted that every
MC includes at least one MT.
As with the movement circles, it will be understood that when considering
a movement track, one must move along the track ~in a known direction because
the order of the states may differ for different directions. Also, associated
with
each MT are the LRU priority parameter p, which indicates the priority of the
MT with respect to other MTs, the frequency parameter F, and the boundary
priority parameter B, all of which are initialized to zero for each new MT. A
"new" MT is detected by comparing an incoming MT to each of the MTs already
stored in the IPB. If the new MT's first-class matching index ~c, which is
described in more detail below, matches the index ~. of one of the stored MTs,
the priority parameter p of the stored MT is increased by 1. Otherwise, the
new
2~ MT is stored in the IPB with the initial values of p = F = 1i = 0. If one
or
more states in an MT is a boundary state, that MT is called a boundary MT and
has its boundary priority parameter B increased by 1.
The operation of the IPD and the data structures generated in the IPB will
be further understood by referring to Fig. 7, which illustrates one movement
circle MC 1 comprising three movement tracks MTI , MT2, MT3 stored in the
CA 02203623 1997-04-24
WO 96/13951 " PCT/SE95/01198
-16-
IPB in least recently used (LRU) order. Also shown in Fig. 7 is a state queue
SQ comprising the most recent N states provided to the MMP, stored in first-in
fast-out (FIFO) order (reading from left to right in the figure). The arrows
indicate how the IPD transforms the sequence of states in the state queue into
the
MTs stored in the IPB (which do not correspond to Figs. 5 and 6). The
indication "C: 1/8, Wall, Street, Highway, etc." refers to examples of
constitutional constraint states that arise from the physical construction of
the
communication system, which will be described in more detail below. It will be
understood that the IPB and the SQ may be implemented by a wide variety of
conventional electronic memory circuits.
The MC Detection IMCD) Method
In generating itinerary patterns based on the MC model from states in the
state queue, the IPD carries out a movement circle detection (MCD) method
comprising the following steps, which are also illustrated in flowchart shown
in
Fig. 8. The MCD and methods in accordance with Applicants' invention are
described in terms of C-language pseudocode, by which the methods may be
implemented easily in hardware and software in any of the mobile stations,
base
' stations, and mobile switching center of a cellular radiotelephone
communication
system.
' Let N be the maximum number of states in the state queue SQ; let MCP
be the j-th MC; and let other terms be as defined above. Keep a queue of k
states (where 1 <_ k <_ N) in a FIFO order and a number j of MCs (where
1 S j <_ M) in a LRU replacement order in the IPB according to the followine
steps.
BEGIN
1) IF Sk,~ is a stationary state or a boundary state,
IF FOR i = k-L to 1, if any 5;,~==Sk,~ (for any t, and for
k-i > L) and S;,~ is a SS or a BS, mark the state sequence
[S~.t-u~ S.+1.~-e, ..., Sk.~ as a new MC;
~ ENDIF;
CA 02203623 1997-04-24
WO 96/13951
-17-
ELSE GOTO END;
ENDIF;
PGT/SE95101198
2) IF any state in the new MC is a boundary state, mark the new MC
as "boundary priority" with boundary priority parameter
Q = l3 + 1; ENDIF;
3) Compare each new MC with each saved MC, i.e., each MC
already stored in the IPB,
IF ~ >_ a, (matching), then increase the priority parameter
p of the saved MC by 1 and calculate the frequency
parameter F of the saved MC;
ELSE
IF a~ 5 ~c < al (partially matching), then mark the latest
matched states as "forked states" in both MCs;
ENDIF;
Save the new MC into the IPB in LRU-replacement order;
ENDIF;
Remove the sequence [S;.~.~,, S;+t.~.~, ..., Sr,~ from the state
queue;
END.
In the foregoing, a2 and al are numbers such that 0 < a~ < al _< 1; SS
are Stationary States; BS are Boundary States; L = 1, 2, 3, ... is the length
(in
number of states) of the shortest MC stored in the IPB; and ~, is the first-
class
matching index. The parameter al is a confidence level that is set according
to
the accuracy requirements or confidence level desired; usually, a, is set to
0.95,
2~ 0.975, 0.99, or the like. The parameter a2 is a partially-matching factor
that
represents the degree of matching between two sequences of states, such that
a~ _ 0.3, 0; 4, 0.5 . . . corresponds to 70 % , 60 % , 50 % . . . of the
states match;
it is currently believed that a2 should be set -to ~ at least 0.5 because
interesting
results currently seem, to be produced only when at least half the states in
two
sequences match.
CA 02203623 1997-04-24
WO 96!13951
-18-
PGT/SE95/01198
The first-class matching index ~. is an indicator of the degree that a first
sequence of states matches a second sequence of states having a similar length
(state-matching). The index ~c is given by the following expression:
ms
h=NS
where ms is the number of states in the sequences that match, and N, is the
total
number of states in each sequence.
Movement Track Detection (MTD) Method .
In generating itinerary patterns based on the MT model, the IPD carries
out a movement track detection (MTD) method comprising the following steps,
which are also illustrated in flowchart shown in Fig. 9.
Let MTj be the j-th MT; let M be the maximum number of MTs in the
IPB; and let other parameters be as defined above. Keep a queue of k states
(where 1 <- k < N) in a FIFO order and keep a number j of MTs (where
1 _<< j _< M) in the IPB in LRU replacement order.
BEGIN
1) IF Sk.~ is a'stationary or boundary state,
FOR i = k-L to 1, IF S;,~ is a SS or BS (for any t, and for
k-1 > L), mark the sequence [5;,~_~l, S;+l.r-~z, ~~~, Sk.~ as a
new MT; ENDIF;
ELSE GOTO END;
ENDIF;
2) IF any state in the new MT is a boundary state, mark the new MT
as "boundary priority" with boundary priority parameter
13 = 13 + 1; ENDIF;
3) Compare each new MT with each already saved MT,
IF ~c Z a, (matching), then increase the priority parameter
p of the saved MT by 1 and calculate the frequency
parameter F of the saved MT;
CA 02203623 1997-04-24
WO 96/13951 '
-19-
ELSE
PCT/SE95/01198
IF az <_ ~c < al (partially matching), mark the
latest matched states as "forked states" in both MTs;
' ' ENDIF;
Save the new MT into the IPB in LRU-replacement order;
ENDIF;
Replace the new saved MT with a PS in the state queue;
END .
In the foregoing, ~c is the first-class matching index; a, and al are
numbers such that 0 <_ ai < al S 1; PS is a Pointer State; L = 1, 2, 3, ... is
the minimum length (in number of states) of an MT. It will be noted that using
a pointer state instead of another state is advantageous because it avoids
duplication.
Motion Predictor
The motion predictor MP included in Applicants' MMP generates
predictions of the next states of movement circles or movement tracks by using
regression and correlation analysis of the current movement itinerary with the
IPs
stored in the IPB. In general, the output PDa~~ of the MP is a future state or
a
sequence of future states.
Fig. 10 illustrates the operation of the MP, which includes means for
comparing input states provided to the MMP to predicted states generated by
the
MMP and means for matching input states to IPs stored in the IPB and for
generating predictions. If the comparator indicates that a prediction is
right, i.e.,
that the current input state matches the predicted state, the prediction is
provided
as the output of the MMP. If the comparator indicates that the current input
state does not match the prediction, or when the MMP is initialized, a motion
prediction process is carried out to generate the next prediction.
When an input state does not match the corresponding predicted state, the
sequence of input states beginning with the most recent stationary state or
boundary state is compared by the MP to each of the MCs and MTs stored in the
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
-20-
IPB. This matching process determines the best-matched stored itinerary
pattern,
which becomes the output of the motion predictor. The motion prediction
method, comprising the following steps, is advantageously structured like a
tree
as illustrated in Fig. 11.
Motion Prediction Method (MPMI
Let 5~,~ be the state k at time t, and let n > 0, t; > 0, and M be the
maximum number of MTs and MCs in the IPB. Keep a queue of k states (where
1 < k <_ N) in a FIFO order and keep a number j of MTs and MCs (where
1 < j <_ ~ in the IPB in a LRU replacement order. Also, assume PDou~ _ [0] -
or PDo~~ ~ [O] and Sk,~ is not matched with the first state of PDa~,.
BEGIN
1) FOR each new incoming state Sk.~, compare the new sequence
[Sk-n.t-m~ Sk-n+l.c-m+1 ~ ~ ~ ~ ~ Sk.~ v'i~ each MC and MT stored in the
IPB, (where Sk_n.~_~ is the latest SS or BS, and n > 0);
2) use first-class (~,) matching:
IF only one stored MC or MT has fulfilled the ~c-matching
requirement with the new sequence (~, z a1), then
PD~,~ _ [Sk+~.~+~,, Sk+z.~+~z~ ~ ~ ~ ~ Sx+m.~+~"] of the matched MC or
MT, (m > 0); GOTO END;
ELSEIF no stored MC or MT has a ~, that matcres the ~c of the
new sequence, then PDo~~ = Coin; GOTO END; .
ELSE use second-class (r~) matching; ENDIF;
3) use second-class (n) matching:
FOR all stored MCs or MTs having ~. that ~.-matched with the new
sequence (~c ~ a,), (joint states), IF only one stored MC or MT
has fulfilled the r~-matching requirement with the nev sequence
('~ S a3), then PDo"~ _ [Sk+l.c+tl ~ Sk+Z.c+t2~ ~ ~ ~ ~ Sk+m.t+~ of the
matched MC or MT, (m > 0); GOTO END;
CA 02203623 1997-04-24
WO 96/13951 PCTISE95/01198
-21-
ELSEIF no stored MC or MT has a r~ that matches the r~ of the
new sequence, find one having a constraint state that is best p.-
matched and best r~-matched to the new sequence; GOTO END;
ELSE use third-class (~) matching; ENDIF;
4) use third-class (~) matching:
FOR all ~c- and rl-matched stored MCs or MTs (joint states),
IF only one stored MC or MT has fulfilled the ~-matching
requirement, PDa~~ _ [Sk+~.~+~,, Sk+2.~+~~ ~.~, Sk+m.t+~ ~f ~e
matched MC or MT, (m > 0); GOTO END;
ELSEIF no stored MC or MT has a F that matches the F of the
new sequence (~ S a4), find one having a constraint state that is
best u-matched, best ~-matched, and best ~-matched to the new
sequence; GOTO END;
ELSE (more than one stored MC or MT has a F that matches the
F of the new sequence (~ <_ a,)), find one of the constraint states
having the highest p+13,
ENDIF;
END
In the foregoing, ~ is the first-class matching index, r~ is the second-class
matching index, ~ is the third-class matching index, and the other terms are
as
described above. Also in the foregoing procedure, have ~ _< a3 when r~-
matching, and have ~ _< a4 when ~-matching, where a3 and a4 are confidence
levels associated with the second- and third-class matches, respectively,
which
match the speeds or frequencies of two sequences of states. Because the speed
or frequency of a mobile user is generally more highly variable, the values of
the
parameters a3, a4 need not be as restricted as the values of the parameters
al, a2.
Thus, the values of a, and a, can be 0.1, 0.05, 0.025, 0.005, . . ., depending
on
the accuracy requirements or the confidence level desired; usually, a3 and a~
would be set to 0.05 for the 95 %-confidence level.
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
-22-
The second-class matching index n is an indicator of the degree that the
duration (speed) of a first sequence of states matches the duration (speed) of
a
second sequence of states having a similar length (velocity- or time-
matching).
The index r~ is given by~ the following expression:
N,-t
2~ ~(t;.yt,)2'(t;.t-t;)t~
N,-t
~ ~(=;.t-=;)2~(t;.t-tt)tl
- t-t
. where: (t;+1 - tat is the time interval between state i and state i+1 in the
first
sequence; (t;+ t - t~2 is the time interval between state i and state i + I in
the
second sequence; "H" is the modulo minus operator, where the modulus is 24 for
time intervals measured in hours and 60 for time intervals measured in
minutes;
and "~" is the modulo plus operator, where the modulus is 24 for time
intervals
measured in hours and 60 for time intervals measured in minutes.
The third-class matching index ~ is an indicator of the degree that the
frequency of a first sequence of states matches the frequency of a second
sequence of states having a similar length (frequency- or period-matching).
Referring to Fig. 12, which illustrates how a user moves through various
states
(indicated on the vertical axis) as a function of time (indicated on the
horizontal
axis), the third-class matching index ~ is determined as follows. The six
movement circles depicted in Fig. 12 can be interpreted as recurring with
different frequencies Ft, F2, where Ft is the frequency of the two longer
movement circles and FZ is the frequency of the four shorter movement circles.
The frequency Fk of an MC or an MT is given by the following
expression:
CA 02203623 1997-04-24
WO 96/13951
-23-
Fk = nn
tk
k-i
PGT/SE95101198
where n = p + 1. The frequency Fk' of a new incoming sequence of states is
given by the following expression:
F.' _ 1
k T
k
as seen in Fig. 12. Thus, the third-class matching index ~ is given by the
following expression:
n
tk
k~l -1
k _ n.Tk
where ~k = 0 indicates exact matching. It will also be recognized that the
third-
class matching index ~ is given by the following expression:
~ . ~Fi_1~
2
where Fl is the frequency of a first one of the sequences being matched and F2
is
the frequency of the other sequence being matched.
Referring again to Fig. 11, if only one stored MC or MT has fulfilled the
p,-matching requirement with the incoming sequence (/.c >_ a,), that one is
provided as the prediction by the MMP. If more than one MC or MT has
fulfilled the p.-matching requirement, then the second-class matching indices
are
examined. If only one _ stored MC or MT has fulfilled the ,~-matching
requirement with the incoming sequence ( r~ > a3), that one is provided as the
prediction by the MMP. If more than one MC or MT has fulfilled the r~-
matching requirement, then the third-class matching indices are examined. If
only one stored MC or MT has a F that matches the F of the incoming sequence,
CA 02203623 1997-04-24
WO 96/I3951 PCT/SE95/01198
-24-
that one is provided as the prediction by the MMP. If more than one MC or MT
has a F that matches, then the sequence having a constitutional constraint
state
with the highest priority parameter p is provided as the prediction by the
MMP.
The constitutional constraint states used in the matching process are based
5: on the physical construction of the communication system, which is known to
the
system a priori. If the MMP is implemented in a mobile station, this physical
construction information can be provided to the mobile through overhead
messages sent on a control channel. The basis for the constraint states is
illustrated in Figs. 13a, 13b.
As indicated by Fig. 13a, a mobile user located in a given cell, say cell 0,
can move to any one of the six adjoining cells 1-6 in the same plane and
adjoining cells that might be above and below that plane; thus, in the absence
of
any other information, each of those eight adjoining cells may be the next
state
with a probability of I/8 if the user moves uniformly randomly in all
directions.
Fig. 13b illustrates a physical configuration in which a door is at one end of
a
corridor that is also joined by another corridor. The communication system
would know a priori that a mobile user in one of the corridors cannot pass
through a wall of the corridor and enter one of the other cells. This
information
can be used to identify the constraint states.
The process carried out by Applicants' Mobile Motion Predictor MMP
can now be summarized by the following pseudocode, which is illustrated in the
flowchart shown in Fig. 14.
BEGIN
1) IF an incoming Sk.~ is a new state, DO steps 2), 3), 4), ELSE DO
steps 5), 6), 7), 8), ENDIF;
2) FOR each new incoming Sk.~, keep a queue of k states (where
1 <_ k <_ N) in a FIFO order and mark Sk,t as "Boundary State"
based on the criteria;
CA 02203623 1997-04-24
WO 96!13951 PCT/SE95/01198
-25-
3) IF the length of PD~,~ is greater than unity, and Sr,~ is p,-matched
with the first state of PD~,~, PD~" = PDou~ - Sk,~; GOTO step 9);
ENDIF;
4) execute motion prediction method (MPM);
5) IF Sk,~ _ = Sk,~_f (for T z r,), mark Sk,~ as "Stationary State"
based on the criterion; ENDIF;
6) execute movement track detection (MTD) method;
7) execute movement circle detection (MCD) method;
8) Keep a number j of (MCs + MTs) in LRU-replacement order in
an IPB, (where 0 _< j <_ M);
9) Repeat from step 1);
END
Using Applicants' invention, mobile terminals will be more intelligent in
data caching and prefetching management for data communication and mobile file
systems; information management, e.g., in selecting information transmission
forms, etc.; and network utilization and management, e.g., in balancing
network
traffic and dynamic channel allocation, etc. Mobile data communication will be
more user-transparent, and service quality will be better.
The operation of Applicants' MMP has been simulated, and the results of
the simulation will now be described with reference to Fig. 15, which shows an
example of the normalized results of a simulation of Applicants' MMP in which
the number of states was 100, the length of the state queue was 500, the size
of
the IPB was 500, and ~ was 0.05. The operation of the MMP for a period of
five weeks was simulated.
Fig. 15 shows the relationship between.a prediction ratio PR and a
randomness factor. The randomness factor refers to the proportion of a
movement that is due to pure chance; a randomness factor of unity means a
particular movement, or transition between states, was completely random. The
prediction ratio is the ratio of the number of correctly predicted states to
the total
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95lOi I98
-26-
number of input states; a prediction ratio of unity means every one of the
MMP's
state predictions is correct.
In Fig. 15, the "optimum" line is the expected best (theoretical) result,
i.e., if there is a regularity factor X in a movement (i.e., the randomness
factor
is 1-X), then the prediction ratio is X. It can be seen from Fig. 15 that the
simulated MMP results track the optimum line quite well; the dashed line in
Fig. 15 shows the mean-squared simulation results. The simulated MMP's
prediction efficiency, which is the ratio of the prediction ratio to the
regularity
factor, was about 95 % .
In carrying out the simulation, a few simplifying assumptions were made
that would not necessarily reflect conditions in a real-world situation. In
particular, the probability of a mobile's moving from one IA to any other IA
was
assumed to have a uniform distribution; in other words, no constitutional
constraint states were used (the constraint outputs were zero).
Also, the time intervals between consecutive states were assumed to have
a Poisson distribution, which was adjusted by a daily mobility factor
according to
the following relationship:
~=yMF
where ~ was the unadjusted density of the assumed Poisson distribution. The
daily mobility factor MF took on one of three values, depending on the
simulated
time of day: MF = 2, for times between 2000 hr and 0600 hr; MF = 4, for
times between 0830 hr and 1600 hr; and MF = 8, for. times between 0600 hr
and 0830 hr and between 1600 hr and 2000 hr. This behavior of the mobility
factor is believed to approximate real-world behaviors sufficiently closely.
Applicants' Mobile Motion Predictor can be employed in an aggressive
mobility management scheme that may be called predictive mobility management.
The MMP predicts the location where a user will be based on the user's
historical movement patterns, and data and/or services are pre-connected
and/or
pre-assigned at the predicted location before the user gets there. In this
way, the
CA 02203623 2005-10-05
WO 96113951 PGTlSE95l01198
AMENDED PAGE
-27-
user can obtain access to his or her data and/or services at the predicted
location
with virtually the same efficiency as at the previous location.
To distribute network services and resources closer no mobile users, i.e.,
to provide service and resource mobility in wireless data networks, a Mobile
5 Floating Agent (MFA) and a Mobile Distributed System Platform Agent
(MDSPA) can be implemented with Applicants' MMP. Service mobility is
defined as the mobility of various service logic in the underlying network to
meet
quality of service requirements of the mobile users. Rrsource mobility is
defined
as the mobility of resources, such as system datalprograms, user data, user
10 programs, etc., in the underlying network to meet quality of service
requirements
of the mobile users. Mobility management developed fmm user and terminal
mobility is required for managing the service and resource mobility.
To efficiently support mobility, each user and each terminal may
advantageously be represented in the network by respective agents, which
contain
15 all service logic and service data related to the user or terminal and
control all
communication sessions of the user or ~terntinal. The uxrslterminaIs are
connected to access nodes in the network, and the agents provide their
services in
xrving nodes. In networks such as the GSM network in Europe, the base station
controllers act as the access nodes and the MSC, with its integrated visitor
20 location register, acts as both a serving node and a visited location.
25 Referring to Fia. I6, the MFA can be implemented as a process or set of
processes, executing on remote fixed hosts or routers, that cotnznunicate and
pre-
connect with local host resources and that manage a variable replicated second
~. class data cache on behalf of ~a MDSPA. ' A MDSPA can be implemented as a
process or set of processes, executing on a home fixed host or muter, that
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
-28-
communicate and pre-assign a MFA to remote fixed hosts or routers on behalf of
its mobile client user.
A Mobile Distributed System Platform (MDSP) and the MFA are
designed to cope with the varying bandwidth and connectivity of different
communication links at different locations and to support service and resource
mobility. The MDSP typically includes Location-Sensitive Information
Management (LSIM) functions and Predictive Mobility Management (PMM)
functions in order to support different applications, such as mobile file
systems,
': mobile intelligent networking, etc. In brief, the LSIM functions involve
- information about the services or resources (including hardware and software
resources, network connectability, types of communication protocol available,
etc.) provided by the systems or networks in a defined geographical area. The
PMM functions involve predictions of the mobile terminal's location and
Virtual-
Distributed Floating Agent Assignment (FAA) functions, which assign the agent
to different locations according to the location predictions and provide
service
pre-connection and servicelresource mobility.
The LSIM in the MDSP manages the location-sensitive information and
maps it to the different services offered by the mobile infrastructure at
different
geographical locations. Also, the LSIM informs both the applications and the
agents in the mobile network supporting the applications about changes in
location of a mobile terminal and provides dynamical service connections. For
example, suppose a network has a distributed file system and several servers
positioned in different geographic areas. If a mobile terminal were to move
from
a location near one of the servers to a location near another server, the LSIM
would inform both the second server and the cache manager in the mobile
terminal that the second server is the nearest, should a fetch of a file be
required.
With the support of the MDSPA and the MFA, service logic and local
resources are unbundled from the underlying network and can move around,
following their mobile users. Furthermore, by using the predictive mobility
management functions available with Applicants' MMP, the service logic and
CA 02203623 1997-04-24
WO 96/13951 PCT/SE95/01198
-29-
resources can be pre-assigned and pre-connected at the places to which a user
is
moving .
Also, Applicants' MMP can be employed in making connection handoffs
and cell reselections more.efficient. Typically, a mobile telephone, while
camped on a given cell, maintains a priority list of information concerning
adjacent cells to which it might camp. The mobile obtains the priority list
information by scanning the control channels possible for such adjacent cells.
Applicants' MMP can reduce the number of control channels that would be
scanned and reduce the amount of information in the priority list by causing
to be
scanned only those cells that were likely candidates for the user to move
into.
It is, of course, possible to embody the invention in specific forms other
than those described above without departing from the spirit of the invention.
The embodiments described above are merely illustrative and should not be
considered restrictive in any way. The scope of the invention is determined by
IS the following claims, rather than the preceding description, and all
variations and
equivalents which fall within the scope of the claims are intended to be
embraced
therein.
