[attachment=12607]
ABSTRACT
Location prediction serves to save capacity on the air interface of mobile radio networks. A selection of neural networks of the feed-forward and feedback type are examined to prove their suitability for this purpose. As first results preferable network structures, input vectors, learning parameters and the simulated prediction probabilities are presented. A comparison with conventional methods shows the advantages and disadvantages of the use of neural networks for motion prediction. The results show that the gain depends on the user profile and the amount of extraordinary movements of the subscriber.
1 INTRODUCTION
Mobile networks of the next generations will be designed with smaller cells than today’s systems, because of the expected growth in the number of subscribers and physical reasons like higher frequency caused by higher bandwidth. The smaller cells cause smaller location areas by keeping the paging efficiency constant. The lower size of the location areas and the higher number of subscribers lead to rising signaling traffic for the purpose of location management. The location updating information is transmitted over the air interface of the mobile system. The air interface is the bottleneck in a wireless system. To save capacity on the air interface, it will be necessary to reduce the signaling traffic.
One main factor in signaling via the air interface is the location updating of the mobile stations which are not in a call but attached to the system. They do not occupy a traffic channel which can be used to transfer the necessary signaling. To prevent overload on the air interface in future systems, it is necessary to find methods to reduce the traffic caused by location updating. There are some proposals to minimize the signaling traffic on the radio link. They reach from creating dynamic location or paging areas to the idea to use the user behaviour and his traffic characteristics. One way to use the movement data of the subscriber is to predict his future location.
2. LOCATION PREDICTION
2.1 Conventional Methods
Location prediction means the use of the historical movement patters of a subscriber to calculate his possible future locations. To solve this problem some algorithms are proposed. One method bases on a table with the possible locations and the probability the user is located in there in a deterministic period of time.
1. In the case of mobile terminating call the subscriber is paged in the possible location areas, in the order of falling possibility, until the mobile terminal answers.
2. A second method stores the historical movement pattern in a database and compares the recent states with these movement tracks in the database to find the one witch samples the actual states. If a pattern matches with some criteria the next state from the stored pattern is used to predict the future location of the subscriber.
The first algorithm is only dependent on time because the time is the criteria to determine the table index and the second method is only dependent on states. In reality it can be assumed that the location of a subscriber is dependent on time as well as actual state. Both methods do not predict the right location, if the subscriber shows different movement patterns at different times. One method to combine the time and location information is to use the prediction characteristics of some neural network types.
2.2 Method using Neural Networks
At the beginning the user has to be observed to store his movement patterns as a function of time m(t). This action is the same as in the mentioned methods, because they also need information about the user’s movements. The first method to record the location and the probability belonging to it. The second algorithm needs no explicit learning phase, but prediction is not possible until some regular movement patterns are detected and stored in the database.
In the next step the suitable neural network has to be trained (s. chap. 4) with the observed motion pattern m(t) (s. chap. 2.3). After training the network the recall phase is used for prediction. The actual movement and time is used to feed the neural network and to get the output the next location or locations depending on the output vector (s. chap. 3). We expect from this method that it shows better results with unknown movements than the conventional methods, but the same results with known movements.
2.3 Subscriber Profile
The movement pattern function m(t) is a discrete function, it consists of samples {m(ti)}. The time intervals ti-ti-1 may be constant or non constant depending on the recording method. The first method is to register each location update generated from the mobile terminal when changing the location area. The location update messages arrive in non deterministic times. The second variant takes samples in constant time intervals by looking in the networks location table.
Figure 2. Subscriber Profile (Example)
In this examination we use only constant time intervals to build the user profile. A mobile network with 20 location areas was chosen, numbered from 1 to 20. We constructed a subscribers movement pattern (s. Figure 2)in this exemplary mobile network by writing down the locations regularly six times a day for four weeks, that means we obtain 168 location values. The sample rate may be higher depending on the subscribers’ movement and location area size. The absolute time values, e.g. days and weeks, don’t constitute a restriction of the generality. With these order of location area numbers, transformed into a set of input and output patterns, we carried out our investigations.
3. INPUT AND OUTPUT VECTORS
3.1 Contents
The contents of the input and output vector depends one the neural network type and on our different studies to find a relation between prediction output and contents of the vectors. Feedback neural networks have the ability to remember the order in which the input patterns are presented during the training, because of their backward connections. With these networks, it is only necessary to give the last known location area number l as input vector (1).
i = (l); l =1, 2, ..., 20 (1)
Feed-forward neural networks are memory-less, that means their output is independent of the previous inputs. For this neural network architecture a modified input vector is appropriate. One possibility is the presentation of the N last known locations (2). N has to be varied in our examination, to get the best prediction probabilities.
i = ( li, li-1 ,...,li-N ); l = 1, 2, ..., 20 (2)
In addition to the last known locations of the subscriber, other information can be given to the neural network. For example, we considered the absolute time, in form of a couple of day and hour (3). This information may be useful, because it may be correlated with the subscriber habits. The time information in the input vector is useful with both types of neural networks.
i = ( li, li-1 ,...,li-N , t ); l = 1, 2, ..., 20 (3)
The output-information is an other important topic. We want to obtain as output information only the location area number, in our example a value between 1 and L. The time information is not necessary in the output vector because we studied only a prediction for the next time interval t+Dt. If the prediction should be extended to the prediction of the location at the time t+kDt the time information has to be included in the input vector. A second information which will be useful in the output vector are the probabilities that the subscriber is located in the predicted location areas.
3.2 Encoding of the input and output information
An input pattern is a set of activation values of the neurones belonging to the input layer of the neural network. The conversion of the real data into the input pattern is called encoding. There are several possibilities to present the input data to the neural network in a appropriate form. We studied the quasi-continuous and the binary coding.
Quasi-continuous representation means the real input data, e.g. location area number and time, are encoded with rational values in a certain interval, e.g. [0;1] in steps of (1/l). In this configuration the neural networks can be building with only one neurone in the input layer.
Binary encoding means the real input data are encoded with the values ‘0’ and ‘1’. In this case the amount of neurones in the input layer is equal to the amount of location areas plus the time values for one period. For this reason the total number of neurones in the input layer rises with the size of the modeled mobile network and the sample rate of the subscriber movement function in case of binary encoding.
The encoding of the output vector corresponds to the encoding of the input vector, with the difference that the time has not to be considered. Binary encoding of the output information means the predictions consists of one or more location area numbers without any probability information. Whereas quasicontinuous encoding is able to deliver probability information corresponding to the predicted location area number. This information can be used for multiple paging attempts. The disadvantage of this output layer structure is that each location area number needs to be coded with one output neurone.
Following the multiple paging method is described. The mobile system first pages the location area corresponding to the neurone with the greatest activation value. If the subscriber does not respond to the paging, the system tries the location areas corresponding to the next activation values in order of falling activation, until the subscriber is found or a maximal number of attempts are reached.