1. Introduction

Mobile ad-hoc network is an autonomous system of mobile nodes connected by wireless links; each node operates as an end system and a router for all other nodes in the network. Furthermore, nodes in mobile ad-hoc network are free to move and organize themselves in an arbitrary fashion. Each mobile user is free to roam about while communication with others and display in diverse patterns. In the ideal case, user mobility is indeed changing over time and with the changes in the user mobility, based on user behaviours (shopping, wakeup, daily-life, etc.) and impact factors (working-hours, holidays, distance, velocity, obstacle, etc). Several research communities have addressed the issues as following: Kostov et al.,[1] proposed a prediction of the user’s destination using a concept of external information categories based on the history data of the moves obtained from a car navigator.[2, 3] They applied the Markov chain algorithm to build their predictors. It reads the string of locations –when a user has visited– over time in the order of which they were visited and build a location visiting history of each user.

Konishi et al.,[4] designed and developed a network simulator called “MobiREAL”. It can simulate realistic mobility of humans and automobiles, and enable to change their behaviour depending on a given application context. They adopt a probabilistic rule-based model to describe behaviour of mobile nodes, which is often used in cognitive modelling of human behaviour. From many studies, we extended the idea that the proposed model allows us to describe how mobile nodes change their destinations, routes and speeds/directions based on their positions, surroundings (obstacles and neighbouring nodes), and information obtained from applications, and so on. Spindler et al.,[5] utilized a Collaborative Filtering (CF) technique that matched users based on social contexts rather than user interaction with the system. Users u_a receives rating tuples from another users u_b if they are within reachability in terms of duration of at least p. On the other hand, ratings are exchanged if the users consume an item simultaneously at least once.

In this paper, we propose a new route destination prediction method based on the movement history including many parameter variations such as location, date, time, weather, which are stored in a trace file that subscribes location information from GPS. Moreover, factors with categories that have correlation to the user's destination based on entropy are extracted. The time and the day of the week attributes are divided into a fixed layered structure and the categories that contribute most for the decision of the future behaviour of the user are decided automatically. The past history movement, the categories that contain a cause-effect relation with the user’s destination also are chosen and the value of our method in destination recommendation experiments is shown. Furthermore, we learn from the experiment[6, 12, 25] how to detect a high resolution GPS fix and/or the GSM Cell-ID.

The remainder of this paper is organized as follows. Section 2 presents some reviews and describes background on mobility pattern mining, prediction models and location services recommendation technique to improve individual preference results. Section 3 addresses the problem statement and proposal, describes the research design and shows the results from a preliminary study. Section 4 describes and discusses the results from the experiments. The final section provides a conclusion and ideas for future work.

2. Background

In this section, we review related literature relating to the mobility mining conducted by other researchers. Accordingly, we classify the related literature into four main categories: Mobility Model, Radio Propagation Models, Routing Protocols for Ad-Hoc Networks and Network Simulators.

2.1. Mobility Models

A mobility model defines the exact position of a mobile node at any time. Brownian movement[7], initial position of node randomly chooses a direction (uniformly distributed in[0, 2π]) and a travel speed (uniformly distributed in[speed _min, speed _max]). Random Waypoint, when a pause after the node has reached its destination point. After the pause, the node starts moving towards the next randomly chosen destination point and the process is repeated again. Bettstetter[8], investigated some of its fundamental stochastic properties with respect to: (a) the transition length and time of a mobile node between two waypoints, (b) the spatial distribution of nodes, (c) the direction angle at the beginning of a movement transition, and (d) the cell change rate if the model is used in a cellular-structured system area.

Figure 1. Random Waypoint Mobility Model show movement pattern of a nodes[9]

Figure 1 shows the distribution of the modes in the simulation area and the distribution of the mode speeds varying over the simulation time. Reference Point Group Mobility Model is applied in many scenarios such as military vehicles in a battlefield or classroom students. Sivajothi and Naganathan[10] defined a source node s that starts a communication session with a destination node d, and it does not have routing information for d available, it broadcasts a reactive forward ant F^s_d. Due to this initial broadcasting, each neighbour of s receives a replica of F^s_d. They refer to the set of replicas which is originated from the same original ant as an ant generation. The task of each ant of the generation is to find a path connecting s and d. At each node, an ant is either unicast or broadcast, according to whether or not the node has routing information for d. The routing information of a node I is represented in its pheromone table Tⁱ. The entry Tⁱ_ndεR of this table is the pheromone value indicating the estimated goodness of going from i over neighbour n to reach destination d. If pheromone information is available, the ant chooses its next hop n with probability P_nd. STRreet RAndom Waypoint (STRAW) proposed by Choffnes and Bustamante[11], uses roads defined by real street maps to model vehicular mobility. The simplified traffic control mechanism models are employed to describe the behaviour of vehicles at intersections.

2.2. Radio Propagation Models

Radio waves are exposed to reflection, diffraction or scattering based on the environmental conditions leading to multipath propagation. A radio signal can be successfully received when the signal to noise ratio (SNR) is above the receiver’s sensitivity. The received power can be calculated as:

(1)

Where:

P_r = received power

P_t = transmitter output power

L_p = total transmitter gain

G_t = path loss

G_r = total receiver gain

The UDelModel for radio propagation[13] uses a 3-dimensional ray-tracing approach to determine the channel gain matrix by calculating signal paths.

2.3. Routing Protocols for Ad-Hoc Networks

Ad-Hoc on Demand Distance Vector (AODV) is a re-active routing protocol. Routes are calculated on demand when a node wants to send a data packet. The route discovery process is started when a source node S wants to send a data packet to a destination node D for which no route is available in the routing table of S. Node S floods a route request packet (RREQ) into the network. Perkins and Royer[13], proposed a new routing algorithm that is quite suitable for a dynamic self starting network, as required by users wishing to utilized ad-hoc networks. Optimized Link State Routing (OLSR) is a pro-active routing protocol based on link state. Network topology information is continuously distributed over the network and stored locally at each node. Continuous flooding generates a lot of redundancy, increases the possibility of collisions and wastes a lot of bandwidth. Munaretto et al.,[14] developed a quality-of-services (QoS) routing protocol for mobile ad hoc networks. They performed the proposed QoS-based routing in the optimized link state routing (OLSR) protocol, introducing a more appropriate metric than the hop distance.

2.4. Routing Protocols for Ad-Hoc Networks

Reference Point Group Mobility Model (RPGM)[14-16, 20-21] model is one of the typical group mobility models, and it has a logical centre node as team leader that determined the group’s movement behaviour. The movement of group leader at time, t can be represented by motion vector,[14, 15] provides the general motion trend of the whole group. The motion vector can be randomly chosen or carefully designed based on certain predefined paths. The movement of group members[19] is significantly affected by the movement of its group leader. For each node, mobility is assigned with a reference point that follows the group movement. Upon this predefined reference point, each mobile node could be randomly placed in the neighbourhood. The formally, motion vector of group member, I, at time t, , can be described as:

(2)

From equation (2) illustrated[14], the motion vector  is a random vector deviated by group member i from its own reference point. The vector  is an independent identically distributed random process whose length is uniformly distributed in the interval[0, ] (where is maximum allowed distance deviation) and whose direction is uniformly distributed in the interval[0, 2].

Figure 2. Reference Point Group Mobility Model[3, 6]

From Figure 2 illustrates, each node has a reference point RP(t) within a certain range from the group centre which is moved together with the movement of the group centre. The Defence Advanced Research Projects Agency (DARPA) has classified the movement behaviour of nodes for military operations and natural disaster into three categories based on the RPGM model[14-18, 27, 30]:

• In-Place Mobility Model: the entire field is divided into several adjacent regions. Each region is exclusively occupied by a single group. One such example is battlefield communication.

• Overlay Mobility Model: different groups with different tasks travel on the same field in an overlapping manner. Disaster relief is a good example.

• Convention Mobility Model: this scenario is to emulate the mobility behaviour in the conference. The area is also divided into several regions while some groups are allowed to travel between regions.

However, the RPGM model has two disadvantages[14, 17]: First, it has to know the complete information for the whole mobility groups, including their member nodes and movements. In natural ad-hoc network environments including tactical networks, however, such the assumption of the knowledge on global information for mobility groups can’t be achieve. Second, each mobile node's location is represented by its physical coordinates. Given only the instantaneous physical locations of the nodes, however, it is difficult to discern the nodes’ group movement patterns and the trend in the network topology changes. With the disadvantages of the RPGM model, it is difficult for the model to be applied to realistic environments.

3. Mobility Prediction Based on Trace File

In this section, we describe our algorithm which consists of three phases: user mobility pattern (UMP)[22-24, 26-29] mining, generation of mobility rules using the mined UMPs, and the mobility prediction. The next inter-cell movement of mobile users is predicted based on the mobility rules in the last phase. However, we proposed a new route destination prediction method based on the movement history including the many parameter variations such as location, date, time and weather which are stored in a trace file that subscribes location information from GPS as shown in Figure 3, 4 and 5.

Figure 3. Viewing trace 2011.09.04.04.56.08.gpx

Figure 4. Viewing trace 2011.09.04.04.55.26.gpx

Figure 5. Viewing trace 2011.08.28.05.17.19.gpx

From Figure 3, 4 and 5, we recorded a user mobility traversal based on XML trace file that collects data such as the start coordinates, previous traverse and many other parameters.

Figure 6. A screenshot from the OpenStreetMap

Figure 6 illustrates a screenshot from the OpenStreetMap that we recorded the data from a mobile users’ traverse from the starting point to the destination point.

We proposed a mobility prediction based on the movement of the mobile.

Table 1. All Possible Mobility Rules Mobility Rules (Rules) Confidence 2 > 0 66.6 4 > 0 50 3 > 4 66.6 5 > 0 50 4 > 5 83.33 3, 4 > 0 75 3 > 4,0 75

Table 1 illustrates the mobility rules and the threshold confidence value. The minimum confidence is assumed to be 50. We defined another parameter, m, which is the maximum number of predictions that can be made each time the user moves. For prediction, we selected the first m tuples from the sorted tuples array. The cells of these tuples are our predictions for the next movement of the mobile user. It means that we used the first m matching rules that have the highest confidence plus support value for predicting the users’ next movement.

Figure 7. The example XML mobility trace format

Figure 7 illustrates the XML–based mobility trace format which is not bound to any specific network simulator.

4. System Design

In this section, we describe the influencing factors analysis, movement factors and random factors as the following:

4.1. Influencing Factors

Users must make different responses to different environments when moving in a cell. Therefore, location prediction should be assisted by the information about the terrain. The environmental factors used in the proposed model include both the concepts of a mobile communication system and the reality of the environment. The environmental factors are described as follows:

• Cell ID: Cell information reflects the logical topology of mobile communication. The structure of a cell may be hexagonal or pentagonal or entirely irregular.

• Road Length: The length of a road is used to calculate the residence time on a particular road. The location prediction model makes use of this information to predict when the user will leave the current cell.

• Intersection location: The type of intersection is one of the key pieces of information in the process of location prediction. A user needs to make different choices for different types of intersections.

• Spatial Feature: Since the terrain is three-dimensional, the velocity and acceleration will display certain behaviour while a mobile user is, for example, climbing. The location prediction model should recognize changes caused by such spatial features.

• Other environment factors: Other statistical information may be used in the proposed model to reflect other environmental patterns.

4.2. Movement Factors

Although the mobile behaviours are mainly controlled by users themselves, a series of regulations are shown in the process of movement before the users make a state changing choice.

• p(x, y): Position information of a user that is used to describe the movement of a mobile user can be obtained using a global positioning system or through triangulation.

• V (t): Current velocity of a user can be calculated through p(x, y). The model proposed in this paper divides users into three classes according to movement velocity.

• a(t):When there are several roads provided to choose from, the acceleration of a mobile user can deliver some movement information in advance.

• w(t): Angular velocity that changes sharply provides useful information for location prediction as it may indicate that the user is changing direction for some reasons.

4.3. Random Factors

While a mobile user is moving, the key factor which can decide the future location of the user is the destination. However, currently there is no way to obtain this kind of information for every mobile communication system. There are also several factors that cannot be used to assist location prediction such as movement changing for emergency events, traffic jam caused by an accident, traffic control in special situations and so on.

5. Location Prediction Model Based Bayesian Network

In this section, we describe the Bayesian Network Model, BNM, which is used in the location prediction model. In addition, a mechanism for distributing predictive factors is designed.

5.1. Construction of CRT based on Cell Environment

In the proposed model, CRT (Cell and Road Topology) is used to denote the reality of a cell and road conditions. The identity of a cell is denoted as C = (C₁, C₂, ...,C_i), where i = 1, 2, ..., n. The sequence of road junctions is presented as J = (J₁, J₂, ..., J_j), where j is the maximum number of junctions. The method of CRT construction is: generation of a sequence of cell IDs C; generation of a sequence of roads R = (r₁, r₂, ..., r_k) on the basis of cell and road junction information, the element of R denotes the road segment constructed by a cell and road junction, or two road junctions only.

5.2. Construction of RST based on CRT

RST(G,E) (Road State Transition) is used to denote a transition of a user moving from the current road to another road, where G is the vertex set denoting the road segment in the model. E denotes the edge set of RST. The approach of RST generation is as following: each elements of R (r₀, r₁, ..., r_k) is added into the RST vertex set; For G, and i = j, if r_i and r_j have a common junction, set the edge < r_i, r_j > belongs to E. As an example, one user may be moving in road r_i and be close to junction J_j , there are then roads r₂, r₇, r₈, r₁ to choose from. The resultant choices are decided on the basis of previous movement information and user movement status. Three edges are generated in RST including < r1, r2 >,< r1, r7 >,< r1, r8 >.

5.3. Construction of PDN based RST

Table 2. Probability of State Transition POS P(1021.5, 6543.5) L(543) UC H M L AC P Z N P Z N / S3 0.35 0.05 0.60 0.05 0.05 0.05 0.35 S4 0.50 0.45 0.05 0.40 0.15 0.15 0.45 S5 0.15 0.05 0.35 0.55 0.35 0.35 0.20

The PDN is the abbreviation of Probability Distribution Network. As the information of the cell topology, road state and movement state are hierarchically coded and attached to each RST node. The probability transition tables and RST structure together make up the PDN. As each node of PDN is related with one status variable, the status can be denoted as S = (S₁, S₂, ..., S_n ), where S_i = V_i = (v_1i , v_2i , ..., v_μi ) is node state variable, μ is the number of possible combinations of predictive factors. The PDN nodes sequence can also be used to present the movement direction as shown in Table 2 and 3.

Table 2 presents the probabilities of state transitions. In addition to the probabilities of state transition, there are location prediction calculation related information including the length of the road, user type and acceleration type.

Table 3. Probability of Predictive Factors Distribution Node Factors Probability Transition S3 UC / H M L H 0.60 0.40 0.00 M 0.33 0.34 0.33 L 0.05 0.45 0.50 AC / P Z N P 0.33 0.50 0.17 Z 0.24 0.36 0.40 N 0.25 0.65 0.10 AVC / P Z N P 0.66 0.30 0.04 Z 0.28 0.22 0.50 N 0.17 0.45 0.38

Table 3 presents the probabilities of predictive factors distribution. The entries include candidate roads, the probability of user type, acceleration type and angle velocity type in the next road.

6. Conclusions

In this paper, we apply a Bayesian Network Model to predict a new route anchored in the mobility pattern mining of trace files obtained from GPS. We all know that mobile nodes move with diverse patterns, therefore it is difficult to accurately predict the events henceforward. Through accurate prediction of mobile user movements, our algorithm aims to deliver performance in terms of accuracy and applicability under various system conditions. Our proposed algorithm consists of three steps as the following; first, we collect the mobile user’s movement history. Second, we demonstrate how prediction can be made via mobility model parameters to investigate the influence of other parameter variations using Bayes' theorem. Third, we propose a new route destination prediction system for adjusting the weight function adaptively. The algorithm has been simulated through a realistic mobility pattern generator. Consequently, prediction model results show that the system achieves high prediction accuracy when the combined decision scheme is adopted. Prediction accuracy on the order of 70–80 percent seems very promising for mobile/wireless computing solutions and architectures.

In future work, we will focus on developing an autonomous group mobility prediction model in order to simulate the behaviour of mobile Ad-hocs through wireless networks. We will propose a new group mobility model to predict the next movements of the group mobile users travelling between the cells of a PCS or GSM network as the.

ACKNOWLEDGEMENTS

The authors would like to thank the anonymous reviewers for their valuable feedbacks and suggestions for this work. We would also like to acknowledge support from the Graduate School of Information Technology at Siam University.