LOCATION PREDICTION FOR MOBILE
AD HOC NETWORKS
By
KHAWAR ISHTIAQUE KHAN
Bachelors ofEngineering
N.E.D University ofEngineering and Technology
Karachi, Pakistan
1995
Submitted to the Faculty of the
Graduate College ofthe
P~~lJP.JP~ St~., lJ..jv~I1'fY
in partial fulfillment of
the requirements for
the Degree of
MASTER OF SCIENCE
December, 2003
LOCATION PREDICTION FOR MOBD..E AD HOC NElWORKS
Thesis Approved:
Dean ofthe Graduate College
n
This thesis is dedieated to
my mom, Shameem Ishtiaque Khan,
and
my dad, Ishtiaque Ahmed Khan,
who have instilled in me the highest sense of
responsibility, disdpline, achievement, and integrity,
towards faith, life, and my work
iii
PREFACE
Wireless networks allow a more flexible model of communication than traditional networks since the user is not limited to a fixed physical location. Unlike cellular wireless networks, an ad hoc wireless network does not have any fixed communication infrastructure. For an active connection, the end host as well as the intermediate nodes can be mobile. Therefore routes are subject to frequent disconnections. In such an environment, it is important to minimize disruptions caused by the changing topology
. for critical applications. This presents a difficult challenge for routing protocols, since rapid reconstruction of routes is crucial in the presence of topology changes. In this thesis we present techniques to predict the future movements of the mobile user and the location of the nodes in the neighboring cells. We can locate the best possible node for the connectivity ofthe path between the source and destination. The future node for communication is determined before the current connection breaks and hence there is no service interruption.
iv
ACKNOLEDGEMENTS First and most important, I thank: Allah for giving me the power, the will, and all else needed to complete my studies.
I wish to express my sincere appreciation to my major advisor, Dr. Thomas Johnson for his intelligent supervision, constructive guidance, inspiration and friendship. My sincere appreciation extends to my other committee members Dr. G.E. Hedrick and Dr. Ajith Abraham, whose guidance, assistance, encouragement, and :fiiendship are also invaluable.
Moreover, I wish to express my sincere gratitude to those, particularly Dr. Debao Chen, who provide suggestions and assistance for this study.
I would also like to give my special appreciation to: My parents for their support, encouragement at times of difficulties and prayers throughout my life. My brother, Khizar Khan, and sister, Hira Khan, for their love and laughter they brought to my life.
Finally, I would like to thank the Department of Computer Science for supporting during these years of study.
v
TABLE OF CONTENTS
Chapter Page
1. INTRODUCTION 1
II. LITERATURE REVIEW " , 4
m. TlIESIS OBJECTIVE , 8
IV. APPROACH 10
Assumptions 10
Rules for assigning the probability 12
Algorithm for Probability Assignment 19
Algorithm for Path Calculation : 19
Algorithm for Best Hop 22
Algorithm for Prefetching " , 23
Example to verify these algorithms 24
V. SIMULATIONS 2 8 REFERENCES... ... ..... ....... .. ....... .. .... ... . 33 GLOSSARy 35 APPENDIXES 38 APPENDIX A -RANDOM MOVEMENT CODE '" 38 APPENDIX B -PROBABILITY BASED PREDICTION MODEL 42
Vl
LIST OF TABLES
Table
Page
I. II. m. IV.
Distance between nodes and states traversed for restricted movement Distance between nodes and prediction accuracy for restricted movement Distance between nodes and states traversed for unrestricted movement. Distance between nodes and prediction accuracy for unrestricted movement
30 32 .35 .36
Vll
LIST OF FIGURES
Figure Page
1.
States and nodes in the network 8
2.
Movement directions of a node from any state 11
3.
Regular States and Boundary States 11
4.
Matching process tree 14
5.
Path calculation 16
6.
Position of nodes in the network when source is at a regular state '" 17
7.
Position of nodes in the network when source is at the boundary state 24
8.
Creating link between the source and the next cell hop 27
9.
Movement directions of a node from any state with 22.5° angle 34
VBl
/~
Chapter I
Introduction
An ad hoc network is a collection of communication devices that wish to communicate, but have no fixed infrastructure available, and have no pre-determined organization of available links. It is a dynamically reconfigurable wireless network with no fixed infrastructure. Each host acts as a router and moves in an arbitrary manner. Individual nodes are responsible for dynamically discovering which other nodes they can directly communicate with. A key assumption is that not all nodes can directly communicate with each other, so nodes are required to relay packets on behalf of other nodes in order to deliver data across the network. A significant feature of ad hoc networks is that rapid changes in connectivity and link characteristics are introduced due to node mobility and power control practices.
Ad hoc networks are suited for use in situations where infrastructure is either not available, not trusted, or should not be relied on in times of emergency. A few examples include: military solders in the field; sensors scattered throughout a city for biological detection; an infrastructure-less network of notebook computers in a conference or campus setting; the forestry or lumber industry; rare animal tracking; space exploration; undersea operations; and temporary offices such as campaign headquarters. In such networks, it is critical to route the packets to destinations effectively without generating excessive overhead.
In typical mobile networks, nodes exhibit some degree of regulantyin the mobility pattern. For example, a car traveling on a road is likely to follow the path of the road and a tank traveling across a battlefield is likely to maintain its heading and
I
speed for some period of time before it changes them. By exploiting a mobile user's non-random traveling pattern, we can predict the future state of a network topology and thus provide a transparent network access during the period of topology changes. In our enhancements, GPS (Global Positioning System) position information is used to locate the node and to predict the distance yet to travel by any node before the link breaks. Based on this prediction, routes are reconstructed before they expire. OUf goal is to provide a seamless connection service by reacting before the connectivity breaks.
As we have assumed so far that the mobility information obtained from GPS is always accurate and each node has a simple mobility pattern i.e. no sudden changes of direction, each node's trajectory follows a straight line and constant velocity for aU node. Under these conditions, the location of a mobile node can always be accurately predicted. However, this assumption cannot hold true all the time. In the real world, the GPS reading obtained may not always be accurate due to various reasons e.g. muItipath fading, indoor conditions, etc. Moreover, a mobile can accelerate, decelerate, and change its direction while it is traveling. All these factors can cause the location prediction to become inaccurate since such events are generally not predictable. But these GPS inaccuracies are not to a great extent. It's just a matter of only few meters. In our case of predicting the distance yet to travel by the node, these few meters doesn't account much. Even if a node changes direction, regularity in the movement pattern and history of past movements help in the prediction process.
Hence, when a path fails, packets experience large delays before the failure is detected and a new path is established. In this paper we investigate introducing the
2
probability calculations for route maintenance and selecting an alternative path when a link is in danger ofbreaking i.e. before the disconnection occurs.
As we have discussed above, the nodes exhibit some degree of regularity in the mobility pattern, there are two basic movement models for regular movements namely, Movement Circle (MC) and Movement Track (MT) models, which efficiently extend the Markov model in mobile applications for modeling the movement of mobile users. What is the difference between Me and MT models -briefly explain.
No matter how mobile users move, their movement history patterns can be basically subdivided into the random part and regularity part. The random infonnation can he used for statistical and probabilistic analysis using stochastic processes and Markov models for motion prediction. The regularity part can be used to predict the future regular movement ofthe users. The idea ofusing the Me and MT patterns is to make the movement pattern easy and simple to be detected and saved.
3
Chapter II
Literature Review
Liu and McGuire [2] describe a class of novel mobile motion prediction algorithms for supporting global mobile data accessing. Traditionally, mobility and routing management includes functions to passively keep track of the location of the users/terminals and to maintain connections to the tenninals belonging to the system. To maintain uninterrupted high-quality service for distributed applications, it is important that a mobile system be more intelligent and can anticipate the change ofthe location of its user. [2] proposes an aggressive mobility and routing management scheme, caned predictive mobility management. A class of mobile motion prediction algorithm predicts the "future" location of a mobile user according to the user's movement history, i.e. previous movement patterns. By combining this scheme with mobility agent functions, the service and user routing data are actually pre-collilected and pre-assigned at the locations to which the user is moving. Thus, the user can immediately receive service or data with virtually the same efficiency as at the previous location, i.e. without encountering a large "data structure handover" delay before service or data is available.
In Predictive Mobility Management scheme, a set of Mobile Motion Prediction (MMP) algorithms is used to predict the future location of a mobile user according to the user's movement history patterns. The MMP algorithms are based on the fact that every node has some degree of regularity in its movement, i.e. the movemellt consists of random movement and regular movement and the majority of mobile users have
4
some regular daily movement-patterns and follow these patterns more or less every day
of the week.
Two basic movement models are proposed, namely, the Movement Circle (MC) and Movement Track (MT) models for the regular movement patterns. The MC algorithm is based on the closed circuit-like (MC) model of user movement behaviors and is used for predicting long-term regular movement. The MT algorithm based on the MT model is used for predicting the routine ones. Stochastic processes and Markov chain model are used to model the random parts ofthe movement.
Several user mobility and movement models can be found in the literature for modeling the mobility behavior ofmobile users. Among them, a widely used one is the fluid flow model [6] in which it is assumed that mobile users are unifonnly populated and the users carrying terminals are moving at an average velocity with uniformly distributed moving-direction over [O,21r].
Three classes of matching schemes are used for correlation analysis of MCs or MTs.
1.
State matching -indicates the degree to which <Ii sequence of states matches another sequence of states having a similar length.
2.
Velocity or Time matching -indicates the degree of the time of a sequence ofstates matches another time sequence of states having a similar length.
3.
Frequency matching -indicates the degree that the frequency of a first sequence ofstates matches a second sequence of states having a similar length.
5
Goff, Abu-Ghazaleh, Phatak and Kahvecioglu [8] describe the signaVpower
reduction technique for route maintenance. Existing on-demand ad-hoc routing algorithms initiate route discovery only after a path breaks, incurring a significant cost in detecting the disconnection and establishing a new route. In this work, we investigate adding proactive route selection and maintenance to on-demand ad-hoc routing algoritluns. More specifically, when a path is likely to be broken, a warning is sent to the source indicating the likelihood of a disconnection. A path is considered likely to break when the received packet power becomes close to the minimum detectable power. Care must be taken to avoid initiating false route warnings due to fluctuations in received power caused by fading, multipath effects and similar random transient phenomena.
Qin and Kunz [5] discuss increasing the Packet Delivery Ratio by link prediction. According to this paper, most existing on-demand mobile ad hoc network routing protocols continue using a route until a link breaks. During the route reconstruction, packets can be dropped which will cause significant throughput degradation. In this paper, they added.3 link breakage prediction algorithm to the Dynamic Source Routing (DSR) protocol. The mobile node uses signal power strength from the received packets to predict the link breakage time, and sends a warning to the source node of the packet ifthe link is soon-to-be-broken. The source node can perfonn a pro-active route rebuild to avoid disconnection. Experiments perfonned demonstrated that adding link breakage prediction to DSR can significantly reduce the total number of dropped data packets.
In Zhimei and Kleinrock [10], they have presented an adaptive prefetch scheme for network use, in which they downloaded files that win very likely be requested in
6
the near future, based on the user access history and the network conditions. The prefetch scheme consisted of two parts: a prediction module and a threshold module. In the prediction module, they estimated the probability with which each file will be requested in the near future. In the threshold module, they computed the prefetch threshold for each related server, the idea being that the access probability is compared to the prefetch threshold. This idea is presented for prefetching files in web browsing, but can be used for any area which uses prediction tedmiques.
The objective of this thesis is to predict the future location of a node so as to reduce the time a source is disconnected to a destination (or something similar). We can combine the techniques discussed in all these papers and combine them for our purpose. As for example, as discussed in [2], we can use Me and MT models to predict
,
the path that should be followed by the node in consideration. Once the path is pre-known,. we do not have to worry about the instantaneous random movement of the node and hence we can more accurately predict the nodes in the neighboring cells of the future-serving-cell for the node in consideration.
We'll not be using packet power in our case, rather we are using the GPS to help us calculate the location of the node, its direction and its speed. Hence, once we predict the fhture-node, the packet-delivery-ratio increases. As soon as we have predicted a node, we'll prefetch the information of that node for the future reference.
7
Chapter III
Thesis Objective
The main objective of this thesis is to predict the near-future location of at node. By knowing the position of the node in the future, we can eliminate the possibility of breaking the link when the node reaches the boundary of the serving cell. There will therefore be no loss of packets which could have occurred because of the link breakage and hence the packet delivery ratio increases.
Once we know the future position of the node, we can look for the nodes in the new serving area before the node reaches there so that the link doesn't break at anytime. Once we find any node that will be there in the new serving area, we can gather all th.e information about that node before time.
In this thesis, we'll first try to predict the path that the node X will follow. Once we know the path, we'll try to locate the nodes in the future serving cell of the node X,
i.e. in area 82 in figure 1.
SI
X
.-.
Figure 1
8
Fig. 1 represents the serving area SI and S2. SI is the current serving area and S2 is the future serving area. Node X is at location M at time t2, at location N at t3, at location 0 at tt and finally at location Y at t5. This figure shows the path of the motion of X. N is the location at which the link is likely to break. This will be just at the boundary ofthe serving cell S1•
This path prediction is done for all the nodes in the network, so that we know the motion of each node. This will help us predicting the nodes in cell S2. Once this path of motion is predicted, we'll find the time required by X to reach
N. At this time, we have to know aU the nodes that are present in 82• Out of all the nodes present in S2, choose the best possible serving node for X in S2. The criterion for choosing the best node involves the speed, direction of travel and the location ofnode in S2 at that time.
9
Chapter IV
Approach
We will make some assumptions. to predict the path of the node and to locate the nodes in the future serving cells. Assumptions:
We make these assumptions to make the calculations a little easy. The assumptions are as follows:
I. We know the direction and speed ofall the nodes in the network.
2.
We know the location of all the nodes at all the times and for that we use the GPS (Global Posi.tioning System).
3.
We know the radius ofeach serving cell (r).
4.
There is no curvilinear motion i.e. all the movements are at a 45°, hence we have only eight possible directions for a node to move from any state.
5.
There is no non-serving area, i.e. all the serving areas are overlapped in such a way that there is no non-serving patch left.
We assume that the nodes move from state to state. The serving cells contain predefined states which are at a fixed distance from each other, say 'd'. There are eight possible directions a node can move from any state as shown in the figure below:
10
• • • •
• • • •
• •
• •
• •
• • • • • •
• • • • • • • •
N
NW NE
W-4---.-.1 .....---.. E
SESW S
Figure 2
The states are defined as of two types, Boundary State (BS) and Regular State (RS). BS is defined as a state which is in the service area of two or more serving cells. All the other states are defined as RS. Figure 3 illustrates the idea of states and serving cells:
SJ
S2
S3
• RS .BS
Figure 3 We assume in our case that the node X will start searching for the next hop in 52 when it is in the state just before the boundary state, e.g. as in Fig.l, node X will start
11
searching for the next hop at location M to provide enough time to node X to search for the best possible node in the next serving cell and to prefetch the information about the next possible hop earlier. If it starts searching the next hop when the node is at a BS, it'll probably have not enough time to locate the best hop before the connection breaks.
Now first we'll predict the path taken by the node. Path prediction is required because it will make easy for us to predict the nodes in the neighboring cells easily and accurately. To predict the path, we define an Itinerary Pattern Base (IPB).. An IPB is a database in which the itinerary patterns and the probability of a node to move to any of the eight possible states from the current state are stored.
Rules for assigning the probability:
The probability is assigned to all the states using these rules: a) Let 'n' be the number of times a node takes the path from state 'x' to 'y'.
b) Let'm' be the number of times a node takes the path from state 'x' to all the eight possmble states, i.e. total number of moves from the current state to all the other states.
c) The probability in this case for a node to move from node 'x' to 'y' is: Px,y=n/m d) If a node reaches a state which was never been reached before, an equal probability of 1/Sth is assigned to all the eight neighboring states.
When a node is in a state, the state with the highest probability is assigned as the next hop for the node. The algorithm we are using for predicting the path includes:
12
a) A comparator that compares the state reached by the node with the state
predicted by the above rules.
b) Methods for matching states to the states stored in the IPB in case the
above prediction rules fail to predict the correct path.
If the comparator indicates that the state predicted by the probability calculation rules is same as the state taken by the node, the complete path is predicted the same way. If the comparator indicates that the predicted and the current states do not match, a motion prediction process is carried out to generate the next prediction.
When a state does not match the corresponding predicted state, the sequence of states that had already been traveled in the current serving cell are matched with aU the sequences stored in the IPB. This matching process determines the best-matched stored
,
itinerary pattern, which becomes the output ofthe motion prediction process.
Three classes of matching schemes are used for correlation analysis. The first-class of matching (with an index J.l), called state-matching, indicates the degree to which a sequence ofstates matches another sequence ofstates having a similar length:
where ms is the number of states in the sequence that matched, and Ns is the total number ofstates in the sequence.
The second-class of matching, called velocity or time-matching (indexed by TJ), indicates the degree of the time of a sequence of states matches another time sequence ofstates having a similar length:
where (ti+1 -ti}l is the time interval.between state i and state i+1 in the first sequence;
13
(ti+J -ti)2 is the time interval between state i and state i+l in the second sequence.
.. and EB are the modulo minus and plus operators, where the moduli are 24 for hours and 60 for seconds.
The third-class of matching, called frequency-matching (indexed by cI», indicates the degree that the frequency of a first sequence of states matches a second sequence of states having a similar length. The frequency of a sequence of states is calculated by how often the "sequence of states" occurs during a defined time period. The third class matching-index <J! is given by the following expression:
Where Fi and Fj are the frequencies of the first sequence and the second sequence; <I? = oindicates exact matching.
The matching process uses explicitly the three classes matching methods to select which pattern has the highest probability to be reused. This matching process is structured like a tree, as depicted in figure below:
J1.-matching
Figure 4
14
In this figure, "=0" means that there is no pattern, "=1" means that there is
exactly one pattern and ">1" means that more than one patterns available in the IPB with the same pattern of states as the current pattern ofstates.
On the right-hand side is the regularity prediction output, which is the prediction output according to the regularity of the movement. On the left-hand side is the random prediction output (CoLlt). The matching tree is operated as a filter to select the best suitable prediction. If only one stored pattern has fulfilled the J1-matching requirement with the incoming sequence, that one pattern is provided as the prediction by the algorithm. If more than one pattern has fulfilled the J1-matching requirement, then the second-class matching indices are examined. If none of stored pattern has fulfilled the Jl-matching requirement with the incoming sequence, then this movement is declar,ed as the random movement and this path is stored in the IPH. If only one stored pattern has fulfilled the l1-matching requirement with the incoming sequence, that one is provided as the prediction by the algorithm. Ifmore than one pattern has fulfilled the l'/-matching requirement, then the third-class matching indices are examined. lf only one stored pattern has an F index that matches the F of the incoming sequence, that one is provided as the prediction by the algorithm. If more than one pattern has an F that matches, then the sequence that is taken the most, is the output ofthe algorithm.
Once we are done with the path calculation for the nodes, we'll now calculate the time required by the node to reach the BS tor cell S1 fTom the state just previous to the BS, given the speed of the node.
We have a node X which is moving on a path as shown in Fig 1. In general, X can move in any direction with 45°. N is the location where the link. is very weak and
15
likely to break. Before node X is at location N, it should find some new node in S2 so
that we avoid the link breakage. This search for the node starts at state M. Now, calculate the time t3 that X requires to reach this location N from M. We can calculate t3 by using the formula:
S =v *t .................................. Eq. I where S represents the distance the node X has traveled to reach N from M, v is the speed of node X and. t is the time node X takes to reach N. Let us defme critical time ts as the time when a node should start looking for the nodes in the neighboring cell.
.................................. Eq.2
where t3 is the time at state N, a BS state, and h is the time at state M, an RS just before a BS. Hence in Equation 1, 'v' is assumed to be known and 't' is 'is', time taken to travel from M to N. 'S' can be calculated by using the information we have from GIS. We know the locations of state M and state N via GPS. So, knowing the location of the two states, we can calculate the distance between them that node X will travel. The distance calculation is very simple, as shown in the figure below:
Figure 5 Let the co-ordinates obtained by GPS for 'M' and 'N' be (Xl, Yl) ;nd (X2, Y2) respectively. The angle between'S' and x-axis is 8) and between'S' and y-axis is 8 2.
16
As we have assumed that a node can move in eight directions, so the angles 8 1 and 8 2 are both 45°. Now, the distance S can be calculated as:
Hence the time node X needs to reach state 'N' is given by:
Eq.4
Now, we know the time that node X requires to move from state 'M' to state 'N'. So, we can calculate t3 by: Eq.6 where tz is the time instant at state 'M'. Hence we get the time t3· At this point while knowing the value of t3, we need to locate all the nodes that
,
will be in the serving cell S2 at time t3. Once we calculate the nodes in this cell S2, we will choose the best possible future serving node amongst all those possible nodes.
S6
Figure 6 This figure shows the positions of the nodes in all the neighboring cells at time instant t1· This figure also shows the states X, N and Y which are in the path ofnode X.
17
Each of these nodes has the same rules for predicting the path. Their movement
patterns are stored in the IPBs. So, we can know their positions at any instant of time.
At t) we know the positions of all the nodes as shown in the figure above. We have already calculated the value of t) above. Now we have to calculate the distance traveled by all of these nodes that are in the neighboring serving cells of S2 by using the same distance formula. We know the direction of travel of these nodes and their respective speeds, so we use this formula again s = v* t. We have three possible cases for the positions of the nodes at t2. which are: Case 1: Those nodes which were present in S2 at tl and now not present at time t2. There is therefore no need to consider these nodes in future for calculations. Case 2: Those nodes which are present in S2 at both the times i.e. at t) and t2. These can be the future serving nodes for node X. Case 3: Those nodes which are not present in S2 at t) but are in the serving cell S2 at time t2. These are also good candidates for creating the link of the node X with the destination node.
Now we'll discuss the algoritluns to calculate the probabilities, the path prediction and the best hop assignment: Step 1: Obtain the probability of all the nodes in the network by using the algorithm for probability assignment below:
18
Algorithm for Probability Assignment
Begin
FOR(0 < i <= k)
Pi [8] = 0
PA,B = PB/ ( LPAU])
End
Here Px[O] represents probability of node X moving towards East; Px[l] represents SE; Px[2] represents S and so on. Also, 'k' represents the total number of states in the network. As any node enters the network, it's been assigned an array P[8] to keep the probabilities of the movement of the node from the current state to all the other eight possible states. PA,B is calculated by dividing the !lumber of times the node B is reached from node A out of all the moves from node A to any of the eight states.
Step 2 : Predict the path that aU the nodes will follow using the algorithm below:
Algorithm for Path Calculation
Begin
FOR (0 <i <= k) ; app,ly the algorithm for all the nodes in the n/w Check the state, the node is in at the moment Path[O] = current_state
Repeat: FOR (0<= i <= 7) Max ( PstateU] ) ; Pstate is the probability of state Predicted_state = max ( Ps1ate[i] ) ; the next stat~ predicted is the state with the max. probability
19
IF ( Predicted_state = state_taken) ; if the prediction is
correct
Pcurrent_state[new_state]++ ; increase the probability for that state from the current state Path[S]++ = new_state ; save the movement path in Path[S]++ in IPB ELSE ; ifthe state predicted is not the one taken by the node, then apply the three matching patterns IF (f.l=l) ; ifthere is only one match for f.l, then alP that Seq. OIP the sequence in the IPB ELSEIF (Il>1) IF ('17=1) ; ifthere is only one match for f.l, then alP that Seq. O/P the sequence in the IPB ELSEIF ('I]>1) IF (<p=1) : ifthere is only one match for f.l, then alP that Seq. OIP the sequence in the IPB ELSEIF (<p>1) ; ifmore than one match OIP the most used path in the IPB Add this path in the IPB PcuITent_state[new_state]++ ; increase the probability of state taken from current state
20
Goto repeat
IF (new_state = RS) ~ if new state reached is an RS, that means that the node will be in the same serving cell and no need to worry about searching the nodes in the neighboring cells.
Goto repeat
ELSEIF ts= (!X2-xIIcos8 j+ IY2-y,1cos8 2)/ v tss = tRS + ts
End
Path[ ] will keep track of the path tbat the node is going through arId it'll store this path illi the IPB as soon as tbe node reaches its destination. Path[O] is the BS for the current serving cell.
Finding the maximum probability state that is likely to be taken by the node from the current state and this is done by using the 'max' function. Predicted_state will be the state with highest probabihty. Ifnow, the state taken by the node is the same as the one predicted, the probability of that state is increased for future movements. Also, the state is saved in the Path[ ].
If the state taken by the node is not the one predicted, then we start the matching criteria. Comparing states first, then time elapsed and then finally frequency of the sequences. The comparison starts with the BS ofthe current serving cell ofthe node up to the current state. If there is no match in the IPB, we'll add this path in the IPB.
21
If the new state is an RS, repeat the same procedure again of finding the next state in the current serving cell. If irs a BS, then start calculating the time at BS. This completes the path detection algorithm. Now, we'll find the nodes in the future serving cell and then find the best possible hop.
Step 3 : Choose the best hop out of all the possible states available to serve as the next-hop using the algorithm below:
Algorithm For Best Hop
Begin
Apply the algorithm for predicting the path ofthe current node.
; Calculate the time current node stays in 82
Find total number ofnodes in the future cell ofnode X, say "total_nodes"
FOR (0 <i <= total_nodes) ; apply the algorithm for all the nodes in cell Apply the algorithm for predicting the path of the node.
tnode = t8S2 -tasI ;Calculate the time it stays in 82
Next..:hop = node ELSE Next_hop = node (max(tnodc) ) End
where 'tnode' is the time required by a node to move from one B8 to the other B8 in the serving celt
22
Calculate the time for which a node will remain in the future serving cell. Then
calculate the times all the nodes will remain in the future serving cell. Compare the times and pick the best node out of all the ones available. Step 4 : use this algorithm to prefetch the information regarding the next hop: Algorithm For Prefetcbing Begin
thop = (tBS -tRS) I2
Use GPS to locate the position of 'Next_hop' node at time thop. This will give
us the current location of <next_hop'.
Create a link between
Prefetch the information End
We create a link between the 'Next_hop' and the current node before the node in consideration reaches the BS.
23
-------
Example to verify these algorithms
We can apply these algorithms to the example in figure 6 to show the difference our algorithms can make to the motion prediction calculations and search for the next hop. We apply these algorithms to figure 6 and calculate the results.
SI
S6
Figure 7
Fig 7 shows the position of all the nodes at time t3 after calculating the distance traveled by all the nodes. We are just showing the nodes that we considered in Fig 6. There will be more nodes in the regions Sj, S3, S4, Ss, S6 but we are not concerned with those at the moment.
We have four nodes in serving cell Sz, namely A, B, D and K. Node G is moving very slow, so it's still in the cell Sj. The slow movement of G makes the probability very high that it will remain in the SI area for a longer period of time. This is the information obtained from the IPB.
As the nodes E, F, G, H, I are not in cell S2 and hence they can't b~ candidates for the serving node for X in cell Sz. We are left with the choices A, B, D and K which
24
are currently in the cell S2. Now the best candidate for the future serving node will be
the one which will remain in S2 for the longest time.
Node A is almost at the center of S2 and is moving quite fast. It has traveled a lot of distance in time t3 and will likely be out of S2 in near future. So there is lot more chanceofnodeA tobeoutof82beforenodeXleaves 82. Thisisobtainedfromstep2 above using algorithm for path calculation.
Node B is nearly at the boundary ofS2 and is actually is a B8. The direction ofB istowardsthe centerof82.Thus,it meansthatithasa lotofdistancetotravelbefore it gets out of S2. Moreover, it is moving quite slowly. There is no reduction in the speed ofnode B even. With all these aspects, there are a lot more chances that node B will be in this cell while node X is in 82. This is obtained from step 2 above using algorithm for path calculation.
Node D is at the boundary of S2 and is moving with high speed. So D will be out of this cell 82 pretty soon. This is obtained from step 2 above using algorithm for path calculation..
Node K has also just entered the cell S2 and is moving towards the center of the cell with a normal speed i.e. not too fast and not too slow. This node will most probably be in 82 while node X is in S2. This is obtained from step 2 above using algorithm for path calculation.
We get this information about the speed and direction of all the nodes from the IPB. With the above discussion, we have two nodes, Band K, that can be potential candidates for the to-be-serving-node for node X in S2. This information-is obtained from step 2 above using algorithm for path calculation and step 3 using the calculation
25
for best hop. Now we have to consider one more thing in deciding the node for a future
serving node, i.e. the probability of the states. If there are more than one nodes that can be a candidate for the hop of the path of the current node, choose the node which has the highest probability or has the most used record as a next state. We can get the probability information from the IPB. By looking at the information obtained, we find out that node K has the maximum probability for being the next hop for node X. This is obtained from step 3 above using algorithm for best hop.
At this point we know that for node X in cell S" node K in S3 will serve as a hop III S2 after time t3. We get this information in advance, so now we can gather information about node K well before time and thus we will have all the information about node K before it is needed and also before the link breaks. This helps us keeping the link tied and no packet loss during the communication. '
In order to gather information about node K, node X will try to locate the cell that is serving node K at time t2'; t2' is the time at location M'. GPS will help gathering this information for node X. Once the node K is located in cell S3, node X tries to make a link with node K via some node in its neighboring nodes, say for example, node J in Fig 8. Node X queries node J if it has any information about node K, if it has then node X will set a new link with node X via hop J and gathers all the information about node K before node X reaches state N.
26
Sl
----~
Link between X & K via J S3
Figure 8
This figure shows the link between node X and node K with nodeJ asahop between the two. As mentioned above, this link helps gathering information about node K for node X at position M'.
27
r-:---.....~ -~--_
Chapter V
Simulations
In our simulations, a few assumptions are made. The distance between two consecutive states is assumed to be 50 meters. At each state, the speed of the node is entered by the user in order to take carre of the movement of the node with arbitrary speeds. It is also assumed that the node will move with the same speed between the two states, i.e. the speed of the node doesn't change from one state to the other state and this assumption is quite reasonable. The total number of nodes in the network is assumed to be 50. In our simulation we have assumed that the time calculation algorithm starts when the node is two states behind the boundary state (BS) for the current serving cell. The reason fOT assuming this condition IS that if we perform the timing algorithm at each state, than there will be overheads in doing so. In order to minimize the overheads, we assume this condition. The reason for assuming to start the algorithm at the state just before the BS is that in most ofthe cases, ifa node is moving in one direction and is reaching the boundary state, it's very rare that it'll change the direction of motion at that time, so this assumption seems moderate to make. The Probability Based Prediction Model (PBPM) will keep track of the path the node has taken to reach the BS and saves it in the database. Once the node is two states distant from the BS, it'll start ca]culating the time the node will take to reach the BS and at that moment of the time, it'll also locate the nodes in the network. Once this information is calculated, tbose nodes are separated which are in the future ~erving cell of the current node. Out of all these nodes that are separated, the algoritlun will pick the best possible bop for the current node in this cell.
28
We first simulate the random motion of the node, which means that there is no
probability model or algorithm to predict the next motion of the node. It'll move from one state to other state randomly. This way, we'll generate the path of node movement from source to the destination. We'll calculate the number of states traversed by the node to reach the destination :from the source.
Secondly, we'll simulate the motion of the node using the PBPM. This model is the model that we have described in our work. This will predict the path of the node from source to destination based on the previous movement history ofthe node and the probabilities involved with the next movement from the state. This model has two cases. In both the cases, the network is assumed to have the Cartesian coordinate system. In the first case, the network is divided into two parts on the y-axis at the source location. In the first case, the maximum probability of the motion is calculated in the direction of travel i.e. in the direction the destination is. Suppose that the destination is in North-East ofthe source, then with this case, the maximum probability of movement is calculated among the directions from North to South, i.e. five directions. In the second case, the maximum probable direction is calculated out of all the possible directions, i.e. four, eight o[ sixteen. Based on tIus model, we'll simulate the path of the node and thus calculate the number of states traversed by the node to reach the destination from that source.
Based on these observations, we plot the graphs for the two cases to calculate which algorithm will give us the more accurate path. The accuracy ofprediction means to predict the path of the source node and all the nodes in the network and predict the next serving cell of the node correctly. The accuracy of predicting the path is the main
29
aspect for determining the efficiency of the proposed PBP model. If we are able to predict the path very accurately, then this algorithm is efficient to use, otherwise it is not advisable to use this algorithm.
In our case, we have run both the algorithms for several times to get the data and then plot the graphs as shown below:
Case 1: This is the case when the probability of movement is calculated out of the restricted directions.
1. Distance b/w source & destination vs. No. ofstates traversed:
No. of States 1 2 3 456 78 9 10 Random
3.125 7.06 9.33 11.78 14.0 20.0' 25.50 33.22 51.06 50.83
Prediction PBPM (4 states) 1.0 2.95 4.30 6.39 8.12 9.52 10.68 11.1 S 12.68 13.22 PBPM(8 states) 1.0 2.43 3.72 6.0 7.44 8.44 9.56 10.67 11.39 11.61 PBPM(] 6states) 1.30 3.50 5.10 8.26 9.86 11.69 12.84 13.93 14.64 15.49
30
Distance b/w source & destination vs. No. of states traversed
60
--+--Random
50 /
A"ediction
~
~
Q) 40 ____ PBPM (4 stales) >
~
7 PBPM (8 states)
2 ~ '" 30
ro
Vi
a 20
~PBPM(16
~ / states)
_~ M,
n--..ft
e
10
l--r""""'-0
2 345678 9 10
Distance blw source & destinatiorl
This graph is plotted beltween the number of states traversed lby the node to reach the destination and the distance between the source and destination. This graphs shows that the number of states traversed by the node using the PBPM uses less number of states to reach the destination as compared to the random prediction algorithm. This means that the PBPM predicts direct or shortest path to reach the destination in contrast to the random prediction algorithm. If we know the destination for a source, it is most likely that the node wHl take the most direct path to reach the destination rather than reaching the destination through a long path. When the distance between the two nodes is small, there is not much difference between the performances of the two algorithms, but as the distance increases, the performance difference becomes visible. For example, for a .distance of one state, i.e. when the distance of the source to reach the destination is only one state, the PBPM will predict the path in only one state whereas tJ1.e random prediction algoritlnn will predict the path of length three. This means· that the PBPM will predict that the node will reach the destination directly from that node while the
31
random prediction predicts, on average, that the node will go to some other two states before reaching the destination. The results are much better when using the PBPM as the distance traveled by the node to reach the destination increases. This shows that on an average, the PBPM uses 5% less states than the random prediction algorithm for small distances but uses at least 30% fewer states than the random prediction algorithm for longer distances to reach the destination. The graph also shows the difference the number of states makes to the results, i.e. the number of possible states a node can take from the current state. Ifthe node has 4 states that it can move to from the current state, the motion of the node is very restricted and it can't move in diagonals and that's not like the real motion of any node. In case of 8 states and 16 states, the number ofstates traversed by the node in the former case is less than the later case. The 16-states case also makes the things a little more complicated. Like, the distance traveled by the node from one state to the other can't be the same in all directions, so we'll have to consider that thing in mind.
2. Distance b/w source & destination vs. Prediction Accuracy: No. of States 1 2 3 456 78 9 10
Random Prediction 0.32 0.28 0.33 0.34 0.35 0.30 0.27 0.24 0.18 0.19 PBPM(4 states) 1.0 0.68 0.70 0.63 0.62 0.63 0.66 0.72 0.71 0.76 PBPM (8 states) 1.0 0.82 0.80 0.67 0.67 0.71 0.73 0.75 0.79 0.86 PBPM (16 states) 0.77 0.57 0.58 0.48 0.51 0.51 0.55 0.57 0.61 0.65
32
~'-------------------:--Distance b/e source & destination vs Prediction Accuracy
1.2
--+-R3ndom
Ftediclion
u
1 '"\
>- --l' _ PBPM (4 states)
~ 0,8 ::
J
u ..-. ,"" ;j., "-~------PBPM (8 states)
c 0.6 -0
~
""0 0.4 ---*-PBPM (16
Q)
.....
.... states)
0.. .... ,
0.2 -------....
0
1 2 34 5 6 78 910 Distance blw source & destination
This graph is plotted between the number of states traversed by the node to reach the destination and the prediction accuracy. This graph represents the accuracy ofpath prediction by the two algorithms. Both of the above graphs are plotted between the same source and destination. 8-states means that there are 8 possible states that a node can move to from the current state and 16-states means that there are 16 possible states. The PBPM predicts the exact state if the boundary state is one less than the current state while random algorithm predicts the next state with a certainty of 33%. Random prediction algorithm will predict the path relatively accurately when the nodes are nearer as compare to when they are at a distance. As the distance increases between the nodes, the accuracy of prediction decreases. On the other hand, as the distance increases for the PBPM, the accuracy of prediction is much high. We have plotted the graph for 4, 8 and 16 states; this suggests us that there is not a big differellce in the accuracy of prediction for 4 or 8-states and also the 8-states algorithm is more accurate than the 16-states algorithm. The reason of this is that as the number of states
33
~~,-----------:-------------Z
increases, the option for the node to move to the other state also increases. In the case
of the 4-states, there is no diagonal motion of the node and that restIicts the motion of the node and it can move only in straight lines. It'll take more number of states to move from source to the destination as compared to the 8-state algorithm. In the case of 16states, there are more options for the node to move from one state to the other and hence the path predicted can be different than the path actually taken by the node because there is a state at every 22.5° angle from one another, as shown in figure 9. With this increase in options, the accuracy of the path prediction decreases. Also, by increasing the number of nodes, the path prediction algorithm runs more than in the other case with less number of states in the network. So, by looking at the graphs, it is clear that by increasing the number ofstates, the performance is actually decreasing.
N
E
S
Figure 9
On average, random prediction algorithm predicts the path with 28% accuracy while the PBPM (4states) predicts the path with an accuracy of 71.1 %; the PBPM (8 states)predictsthe pathwith anaccuracy ofalmost 78% andPBPM(16 states)predicts
the path with an accuracy of58%.
34
Case 2: This is the case when the probability of movement is calculated out of all the
probable directions, four, eight or sixteen.
1. Distance b/w source & destination vs. No. ofstates traversed:
No. of States 1 2 3 4 56 7 8 910 Random
3.125 7.06 9.33 11.78 14.0 20.0 25.50 33.22 51.06 50.83 IPrediction PBPM (4 states) 1.0 3.39 4.97 8.08 9.89 11.05 12.63 13.68 14.69 15.86
PBPM(8 states) 1.0 3.19 4.39 6.98 9.17 10.23 11.56 12.71 13.61 14.48 PBPM(16states) 1.30 3.87 5.15 8.56 10.02 11.15 12.89 13.17 15.10 16.26
Distance bfw source & destination vs. No. of states traversed
60 50 --+---Random
"'0
Q)
Prediction
l/)
.....
~ 40
ro -PBRv1 (4 states)
~
l/)
Q) 30
10
(j)PBRv1 (8 sta.tes)
-200
0
z -¥-PBRv1 (16
10
slates) 0 2 345678 9 10 Distance b/w source & destination
This graph is plotted between the number of states traversed by the node to reach the destination and the distance between the so urce and destination. This graph also shows the same results as with the first case that the number of states used by the node
35
..to move from source to destination using the prediction algoritmn uses fewer number of nodes as compared to that of without prediction. 4-states and 16-states are almost giving the same results with 4-states has a little edge on 16-states. 8-states' case is again better than the other two. Overall, this case with non-restricted movement of the node from any state takes more states to reach the destination as compared to the first case ofrestricted movement ofthe nodes.
2. Distance b/w source & destination vs. Prediction Accuracy:
No. of States 12 3 4 5 6789 10 Random Prediction 0.32 0.28 0.33 0.34 0.35 030 0.27 0.24 0.18 0.19 PBPM(4 states) 1.0 0.59 0.60 0.49 0.51 0.54 0.51 0.58 0.61 0.63
PBPM (8 states) LO 0.62 0.68 0.57 0.55 0.59 0.61 0.63 0.66 0.69
PBPM (16 states) 0.77 0.51 0.58 0.46 0.50 0.53 0.54 0.61 0.60 0.62
Distance bfw source & destination vs. Prediction Accuracy
1.2
>. 1
(.)
co
---+-Random
::::l
I-O.B
(.) Prediction
~
c _ PBFM (4 states)
0.6
0
~
u .~ 0.4
Q) PBPMI (8 states
lll.
0.2 ----¥-PBPM (16
o-state~)
1 2 345 678910 Dlistance b/w source & destlination
36
This graph is plotted between the number of states traversed by the node to reach the destination and the prediction accuracy. This graph shows that the accuracy of prediction in this case decreases with all the 4, 8 and 16-states' as compared to the first case, i.e. with the restricted movement. The accuracy ofprediction for 4-states case is a little better than the 16-states case. The 8-states case again comes out to be the best possible solution. On average, 4-state predicts the path with an accuracy of 60.6%, 8state predicts with 66% and 16-state case with an accuracy of 57.2%.
37
Conc.lusion: Looking at the comparisons above in the graphs, it is clear that the
paths are predicted more accurately using PBP.M as compared to the random motion prediction and hence it is a good idea to use this algorithm to predict paths. As far as the number of states in the network is considered, based on the pros and cons ofthe 4, 8 and 16-states, the best possible case is using the 8-state motion with the restriction of movement, as of the first case. The reason for choosing the 8-state rather than the 4state is that there is not a big difference in the prediction accuracy between 4 and 8states but the freedom of motion for the node in 8-states' case is more than the other case. The prediction accuracy is lower in the 16-states case and also this option is more complicated than the 8-states option.
Hence, we can pre-calculate the path for the node before it reaches its BS and thus avoid the breakage ofthe link. The paths ofthe other nodes in the network are also calculated and the best possible node to serve the current node in the future-serving cell is known well before time and hence we can gather all the information required to create a link between these two nodes. As a resu.lt, the transmission becomes faster without any interruptions and breakage ofthe links.
The accuracy ofpredicting the correct node in the next serving cell depends upon predicting the path of the nodes accurately. Once the path is predicted accurately, the nodes are located in the other cells accurately. The more accurate the path predicted, the more certain a node in a region at any instant ofthe time.
38
REFERENCE
[1] Charles E. Perkins, "Ad Hoc Networking", Addison -Wesley Publications Limited, Dec 2000
[2] George Liu and Gerald Maguire Jr., "A class of mobile prediction algorithm for wireless mobile computing and communications", Mobile Networks and Applications 1, 1996, pgs 113-121, J. C. Baltzer AG, Science Publishers
1st
[3J J. F. DiMarzio, "Sams Teach Yourself Routing in 24 hOUTS", edition, Sams Publishing, Indianapolis, IN, Apri12001
[4] Lawrence Letham, "GPS -Made Easy", 6th edition, T~e Mountaineers, Seattle, WA,1998
[5] Liang Qin and Thomas Kunz, "Increasing packet delivery ratio in DSR by link prediction", Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada, Proceedings of the 36th Hawaii International Conference on System Sciences (HICSS'03), 2002 IEEE
[6] R. Thomas, H. Gilbert, and G. Mazziotto, "Influence of the movement of mobile
Of 3rd
station on the performance of the radio cellular network", Proc. Nordic Seminar, Copenhagen, September 1988
[7] Ram Ramanathan and Jason Redi, "A brief overview of Ad Hoc networks: Challenges and Directions", IEEE Communication Magazine, 50th Anniversary Commemorative Issue/May 2002
39
[8] Tom Goff, Nael B. Abu-Ghazaleh, Dbananjay S. Phatak, and Ridvan Kahvecioglu,
"Preemptive routing in Ad Hoc networks", Computer Science and Electrical Engineering Department, University of Maryland, Baltimore, MD; and Computer System Research Laboratory, Computer Science Department, Binghamton University, Binghamton, NY, ACM SIGMOBILE 7/01 Rome, Italy 2001
[9] William Su, Sung-Ju Lee, and Mario Gerla, "Mobility prediction and routing in Ad Hoc wireless networks", International Journal of Network Management, vol. 11, Issue 1, January-February 2001
[10] Zhimei Jiang and Leonard Kleinrock, HAn Adaptive Network Prefetch Scheme", IEEE journal on selected areas in communication, vol. 16, No.3, April 1998
40
~----'
A'--"'
,..---_
GLOSSARY Ad Hoc Network: A complete wireless network with no wire connection at any stage in the network. An ad hoc network is a collection of communication devices that wish to communicate. In ad hoc wireless networks no base stations exist and each mobile host (MH) acts as a router and a packet forwarder. Networks can be formed and :fragmented on the fly without the intervention of a system administrator or the presence of fixed network devices. The bandwidth available for the exchange of routing information in ad hoc networks is much less than that available in a wired internet. Bandwidth : Bandwidth (the width of a band of electromagnetic frequencies) is used to mean (l) bow fast data flows on a given transmission path, and (2), somewhat more technically, the width of the range of frequencies that an electronic signal occupies on a given transmission medium. Boundary State: A state which is in the service area oftwo or more serving cells. 'Critical Time (ts) : The time at which a node should start searching for the nodes in the neighboring cell. Global Positioning System (GPS) : The Global Position System is a satellite system used in navigation that allows detemline the position of any objecUnode any place of the globe and in any kind of weather. The GPS works with an error of between 15 to 100 meters.
41
Hop: One hop is defined as the transit through one router. Each router always adds 1
to account for itself. Itinerary Pattern Base (IPH) : The database which stores all the infonnation like all the previous movement patterns of all the nodes, probability ofmovements from every state and path taken by the current node. Link : It is the connection between two or more nodes so that they can communicate with each other and data can be transferred between them. Movement Circle (Me) Model : The MC model is based on the assumption that whenever a user moves from a location, the user will eventually retum or has returned. Thus, the movement behavior of mobile users is modeled as different circle-like patterns. Movement Track (MT) Model: An MT is a unidirectional itmerary which begins and ends with a state in which a node remains for some time greater than a specific period oftime Ts. In some special case, an MT can be an MC itself if it begins and ends with the same state. Network : In infonnation technology, a network is a senes of points or nodes intercoillJected by communication paths. Networks can interconnect with other networks and contain sub networks. Node: In a network, a node is a connection point, either a redistribution point or an end point for data transmissions. In general, a node has programmed or engineered capability to recognize and process or forward transmissions to other nodes. Packet Delivery Ratio (PDR) : The number of data packets received by destinations over the number of data packets supposed to be received by destination nodes.
42
i~~ ---~
Route Discovery : Used only when a node attempts to send a packet to a destination
node and does not already know a route to it Route Maintenance : Used to help detect a source node if the network topology has cbanged or whether a link to a destination node is broken. In such cases, Route Maintenance indicates the source node to use any other route it happens to know, or it can invoke Route Discovery again to find a new route. Router : A TOuter is a device that detennines the next network point to which a packet should be forwarded toward its destination. They examine packets, calculate paths, and make intelligent routing decisions. The router is connected to at least two networks and decides which way to send each infonnation packet based on its current understanding ofthe state oftbe networks it is connected to. State : The place in a serving cell at which the location,' direction of travel and probabilityofmovementofnode isknown.
43
F~,
APPENDIX A
1*************** Random Movement Algorithm ***********************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void main(void)
{
int Xn, Yn; /* coordinates ofcurrent location of node */
int Xs, Xd;
int Ys, Yd;
int random=O, p=O, pathX[100], pathY[100];
printf("Enter the value of Xs: ");
scanf("%d",&Xs);
printf("Enter the value ofYs: ");
scanf(l%d",&Ys);
printf("Enter the value ofXci: ");
scanf("%d",&Xd);
printf("Enter the value ofYd: ");
scanf("%d",&Yd);
printf("\n");
printf("Source (%d,%d)\n",Xs,Ys);
printf("Destination: (%d,%d)\n\n",Xd,Yd);
printf("The source is currently at location: (%d,%d)\n",Xs,Ys);
srand( time(NULL) );
while «Xs != Xd) II (Ys != Yd» /* loop until the source
reaches the destination */
{
/* randomly generate the path out ofthe five possibilities until the source is at state one less than the destination */ if( (Xd < Xs) II «Xd == Xs)&&«(Yd-Ys)> 1) II «Ys -Yd) > 1»» /* way(i) */
{
random = randO%5;
switch (random)
{
case 0:
{
Xn =Xs; Yn=Ys+l;
44
break;
case 1:
{
Xn = Xs -1; Yn=Ys+ 1; break;
}
case 2 :
{ Xn =Xs-1; Yn=Ys; break;
}
case3 :
{ Xn=Xs -1; Yn=Ys-l; break;
} case4 : {
Xn=Xs; Yn=Ys-l; break;
} default :
{
Xn=Xs; Yn=Ys+l; break;
}
} } /* end ofway(i) */ else if(Xd > Xs) /* way(ii) */ {
random = randO%5;
switch (random)
{
case0 :
{ Xn=Xs; Yn=Ys+ 1; break;
45
•
}
case 1:
{
Xn = Xs + 1;
Yn=Ys+1;
break;
}
case2 :
{
Xn=Xs+ 1;
Yn=Ys;
break;
}
case 3 :
{
Xn= Xs + 1;
Yn=Ys-l;
break;
}
case4:
{
Xn=Xs;
Yn=Ys-l;
break;
}
default:
{
Xn= Xs;
Yn=Ys+ 1;
break;
} } } /* end ofway(ii) */
else if( (Xd = Xs) && «Yd = Ys-1) 1\ (Yd == Ys -I-1))
{ Yn=Yd; Xn=Xd;
}
else if( (Yd = Ys) && (eXd= Xs-1) II (Xd= Xs+1))) { Xn =Xd;
46
a Yn=Yd;
}
pathX[p] = Xn; /* to store the path in the array */
pathY[p] = Yn;
p=p + 1;
Xs=Xn; /* to shift the source to the next state coordinates */
Ys=Yn;
printf("The source is currently at location: (%d,%d)\n",Xs,Ys);
} /* end ofwhile */ } /* end ofmain */
47
"-.....~----a
APPENDIXB
/*********************************************************************/ /*********************************************************************/ /******* *********/ /******* Probability Based M.ovement Model (PBMM) *********/ /******* *********/ /*********************************************************************/ /*********************************************************************/ /******* This program predicts the path of all the nodes *********/ /******* in the n/w. It also calculates the time. *********/ /******* This will calculate the time to reach the BS and *********/ /******* choose the best hop. *********/ /*********************************************************************/ /*********************************************************************/
#inc1ude<stdio.h> #inc1ude<stdlib.h> #include<time.h> #include<math.h>
/* global array */ float arrayl [100][ 100][8]={0.0};
/* function to initialize the probabilities */ void initialize(void);
int main(void)
{
int Xn, Yn; /* coordinates of current location of node */
int Xs, Xd;
int Ys, Yd;
int k=O, next_state=O;
int i=O;
int Max 1=0, Max2=0, Max3=0;
int min_k=O, max_k=O;
int p=O, pathX[IOO][lOO]={O}, pathY[lOO}[IOO]={O};
char ch='Y';
int speed=5;
int S=50; /* Distance between the states */
int time[100][500]={0}; /* keeps the time taken by source to reach any state */
int t=O, n=O, r=0;
48
int flag=l ~
int rnax_no_oCnodes=O~
int Td=O; /* time to reach the destination from source */
int time_left[3][20]={O} ~
int s=O, Max=O~
int Max_node=O, best_nodeX=O, best_nodeY=O;
nextJ'ath:
printf("Enter the value ofXs: ")~
scanf("%d",&Xs);
printf("Enter the value ofYs: or);
scanf("%d",&Ys);
printf("Enter the value ofXd: ");
scanf("%d",&Xd);
printf("Enter the value ofYd: ");
scanf("%d",&Yd);
printf("\n"};
printf("SauTee : (%d,%d)\n",Xs,Ys);
printf("Destination: (%d,%d)\n",Xd,Yd);
printf("The source is at currently at location : (%d,%d)\n",?Cs,Ys)~
pathX[n][p] = Xs;
pathY[n][p] = Ys;
p=p+l;
initializeO;
while( (Xs != Xd) II (Ys != Yd»
{ /* ifthe current state is one less than the dest, then goto */ F dest directly */ if( «abs(Xd -Xs) == 1) && (abs(Yd -Ys) = 1) II «abs(Xd -Xs) == 1) &&
(abs(Yd -Ys) = 0) II «abs(Xd -Xs) == 0) && (abs(Yd -Ys) = 1» ) { if( «Xs = Xd) && (Ys < Yd» iI «Xs == Xd) && (Ys > Yd» II «Ys = Yd) && (Xs < Xd» II «Ys = Yd) && (Xs > Xd») {
Xs = Xd;
Ys = Yd~
goto print;
}
else
{
Xn=Xd;
49
'-....~---Yn=Yd;
goto step;
}
} if( (Xd > Xs) && (Yd < Ys» {
min_k = 0;
max_k=2;
} else if( (Xd < Xs) && (Yd < Ys» {
min k=2'
-, max_k=4; } else if( (Xd < Xs) && (Yd> Ys» {
min_k = 4;
max_k=6;
} else if( (Xd > Xs) && (Yd > Ys» {
min k=6'
-,
max k=7'
-, }
/* This will calculate the top three probabilities ofeach state */ for(k=min_k;k<max_k;k++)
{
if(arrayl [Xs][Ys][Max1] > array1[Xs][Ys][k+I))
{
if(arrayl[Xs][Ys][k+1] > arrayl[Xs][Ys][Max2])
{
Max3 = Max2;
Max2 = k + 1;
}
else
{
if(arrayl[Xs][Ys][k+1] > array1[Xs][Ys][Max3])
{
Max3=k+l;
Max2=Max2;
}
else
{ Max3 = Max3; Max2 = Max2;
50
}
}
MaxI =Maxl;
}
else
{
Max3 = Max2; Max2 =Maxl; MaxI =k + 1;
} } /* End offor loop for probability calculations */
next_state = MaxI;
repeat: switch (next_state)
{ case 0: /* 0 means East and going clockwise */ {
Xn=Xs+ I; Yn = Ys; break;
} case I: /* 1 means SE */ {
Xn=Xs+I; Yn=Ys-I; break;
} case2: /*2meansS */ {
Xn = Xs; Yn=Ys-I; break;
}
case 3 :
{
Xn =Xs-I; Yn=Ys-1; break;
}
case4 :
{
Xn=Xs-I;
Yn =Ys;
break;
}
51
case 5 :
{ Xn=Xs-1; Yn=Ys+ 1; break;
}
case 6:
{
Xn=Xs; Yn=Ys+ 1; break;
}
case 7:
{
Xn=Xs + 1; Yn=Ys+1; break;
}
default:
Xn=Xs;
Yn=Ys;
} /* end ofswitch */
/* Here check ifthe direction is towards destination or not */
if( (Xd < Xs) && (Yd < Ys) )/* IfDest. is W of Sour. */
{
if( (Xn < Xs) II (Yn < Ys) )
{
if( (p>1) && (p<l 0) )
{ if( (pathX[n][p-2] == Xn) && (pathY[n][p-2] = Yn» {
goto find_next 1; } else
goto step; } else if(p>=10)
{
if(Xn> Xd)
{ Xn = Xn -1; Yn= Yn; goto step;
}
52
'~~--------------------else if( (Xn =Xd) && (Yu > Yd» {
Xn=Xd; Yn= Yn -1; goto step;
}
}
else
goto step;
}
else
{
if(next_state = MaxI)
{
next_state = Max2;
goto repeat;
}
else
{
next_state = Max3;
goto repeat;
}
}
} else if( (Xd > Xs) && (Yd > Ys» /* IfDest. is E of Sour. */ {
if( (Xn> Xs) II (Yn > Ys) )
{
if( (p>1) && (p<10) )
{
if( (pathX[n][p-2] = Xu) && (pathY[n][p-2] == Yu) ) {
goto find_uext2; } else
goto step;
}
else if(p>=10)
{
if(Xu < Xd)
{
Xn=Xn+ 1; Yn=Yn; goto step;
}
else if( (Xu = Xd) && (Yn <Yd) )
53
{
Xn=Xd;
Yn=Yn+ 1;
goto step;
}
}
else
goto step;
}
else
{
find next2:
if(next_state = Maxi)
{
next_state = Max2;
goto repeat;
}
else
{
next_state = Max3;
goto repeat;
}
}
}
else if( (Xs =
Xd) && (Ys < Yd))
{
Xs=Xs;
Ys=Ys+ 1; } else if( (Xs = Xd) && (Ys > Yd)) {
Xs = Xs;
Ys=Ys-l; } else if( (Ys == Yd) && (Xs < Xd) ) {
Xs = Xs + 1;
Ys = Ys; } else if( (Ys = Yd) && (Xs > Xd») {
Xs= Xs-1; Ys = Ys; }
/**** Increase the probability ofthe path that's been taken.
54 We assume 5% increase in probability in the path taken and 5% decrease in probabilty in the paths not taken ****/
step: if(next_state = MaxI)
{
for(i=0;i<8;i++)
{
if(i MaxI) array1[Xs][Ys][Max 1] = (float)(arrayl[Xs][Ys][Maxl] + 0..05); else arrayl[Xs][Ys][i] = (float)(arrayl[Xs][Ys][i] -0.05);
}
}
else if(next_state = Max2)
{
for(i=0;i<8;i++)
{
if(i=Max2) array1[Xs][Ys][Max2) = (float)(arrayl[Xs][Ys][Max2] + 0.05); else arrayI[Xs][Ys][i] = (float)(array1[Xs)[Ys)[i] -0.05);
}
}
else
{
for(i=0;i<8;i++)
{
if(i==Max3) arrayl [Xs][Ys][Max3] = (float)(arrayl [Xs][Ys][Max3] + 0.05); else array1[Xs][Ys][i] = (float)(arrayl[Xs][Ys][i] -0.05); } }
print: /***** Time Calculation Algorithm *****/
if( (Xs = Xd) && (Ys != Yd»
{
printf("Enter the speed of node at (%d,%d) in mls: ",Xs,YS+1);
scanf("%d",&speed);
}
else if( (Ys == Yd) && (Xs != Xd»
{
printf("Enterthe speed ofnode at (%d,%d) in m/s: II ,Xs+ 1,Ys);
55 scanft"%d",&speed)~
}
else
f
printf(tlEnter the speed of node at (%d,%d) III mls: ",pathX[n][p1J~pathY[nJ[p-lJ)~ scanf("%d",&speed);
}
/***** Distance travelled is assumed to be ***50*** meters *****/ j***** fr..om.QBe state to another state *****/
timeLnJIt+lJ = timeIn]ItJ + (S 1speed);
t= t+ 1;
/* initializing the variables *1
MaxI = Max2 = Max] = next_state = 0;
if( «Xs = Xd) && (Ys = Yd» II «Xs = Xd) && (Ys < Yd) II «Xs = Xd) && (Ys> Yd) Jj «Ys = Yd) && (Xs < Xd)) IJ «Ys = Yd) && (Xs > Xd»)
{
/* to store the path. inthe array *1
pathX[n][p] = Xs;
pathYlnJIPl = Ys;
p= P + 1;
}
else if( (Xs != Xd)&& (Ys != Yd) )
{
/* to store the path in the array */
pathX[n][pJ= ~
pathY[n][p] = Yn;
p = p+ 1~
/* Shift the source to the next state coordinates *1
XS=Xn;
Ys = Yn;
}.
printf("The source is currently at location: (%~%d)\ntl,Xs,Ys);
} 1* end ofwhile */
p=o~
printf("\nThe sOUlice has reached the destination..\nil);
56
/~~----------7""-~-----------/* initialize the variables to remove the previous value */
flag = 1;
ch='Y';
getcharO; /* to get the \n character entered after the option */
/* check if user wants to predict rest of the path ofsame node */
while(flag == ~)
{ printf("\nDo you want to predict rest ofthe paths for same node (YIN)? "); scanf("%c",&ch);
if( (ch = 'Y') II (ch = 'y'))
{
flag=O;
goto next-'path;
}
else if( (ch = 'N') II (ch = 'n'))
{
flag=O;
}
else
{
getcharO; /* to get the \n character entered after the option */ flag=l;
}
} /* end ofwhile for next path prediction for same node */
/* initialize the variables to remove the previous value */
flag = 1;
ch= 'V';
getcharO; /* to get the \n character entered after the option */
/* check ifuser wants to predict the paths ofother nodes */
while(flag = 1)
{
printf("\nDo you want to p,redict the path for other nodes (Y/N)? ");
scanf("%c",&ch);
if( (ch = 'Y') II (ch = 'y'))
{
n++; /* increment the value for the next node */ _
t=O; /* initialize the time to save the values for the next node */
flag=O;
goto nextyath;
}
57
else if( (ch = 'N') " (ch = 'n') )
{
flag=O;
}
else
{ getcharO; /* to get the \n character entered after the option */ flag=1 ;
}
} /* end ofwhile for next path prediction for other nodes */
/* Search the nodes in the next serving cell of node ofinterest */
max_no_oCnodes = n;
n=O;
i=l;
while(time[n][i] != 0)
{
i++;
}
Td = time[n][i-I];
Xd = pathX[n][i-l];
Yd = pathY[n][i-I];
for(n=l;n<=max_no_oCnodes;n-t-+)
{
for(i=1 ;i<500;i++)
{
if«int)time[n][i] = (int)Td)
{
/* this ifwill check ifthe other nodes are in serving cell S2 or not? */ if( (eXd -pathX[n]{i]) >= 0) && C(Xd -pathX[n][iD <= 6) && (abs(Yd -pathY[n][i]) <= 3) )
{ /* ifinside, then: */ time_left[O][s] = n; time_left[I][s] = i; while(time[n][i] != 0) {
i++;
}
time_Ieft[2][s] =time[n][i-l] -Td; s=s+l;
58
I.~------------:----break;
}
else
{
/*
ifoutside, no need to store that node */
break;
}
}
else if( (int)time[nJri] = 0) {
break;
}
}
}
/* here find the max "time_Ieft[2][s]" and that's the node which will be the best possible hop in next serving cell */
for(i=O;i<s;i++)
{ if(time_Ieft[2][Max] > time_left[2][s+1]) Max = Max; else Max =s+ 1;
}
Max_node = (int)time_left[O][Max];
best_nodeX = pathX[Max_node][0];
best_nodeY = pathY[Max_node][0];
printf("The best possible hop for node (%d,%d) in next cell 18 (%d,%d)\n",
pathX[G][O], pathY[O][O], best_nodeX, best_nodeY); return 0; } /* end ofmain */
void initialize(void)
{
int i=O, j=O, k=O; int random=O; float random1=0.0;
srand( time(NULL) );
59
!~
for(i=O;i<l OO;i++)
{
for(j=O;j<l OO;j++)
{
for(k=0;k<8;k++)
{
random = 30 + (randO % 46); /* Probabilities b/w 0.30 & 0.75 */
randoml = (float)randorn/(float)100;
arrayl [i][j][k] = randoml;
}
}
}
}
60
VITA
(9)
Khawar Ishtiaque Khan
Candidate for the Degree of
Master of Science
Thesis: LOCATION PREDICTION FOR MOBILE AD HOC NETWORKS
Major Field: Computer Science
Biographical:
Personal Data: Born in Hyderabad, Sindh, Pakistan, On January 8, 1978, the son ofMr. Ishtiaque Ahmed Khan and Mrs. Shameem Ishtiaque Khan
Education: Graduated from Saudi Arabian International High School, Al-Khobar, Saudi Arabia in May 1995; received Bachelor of Engineering degree in Electrical Engineering fmm N.E.D. University of Engineering and Technology, Karachi, Pakistan in April 2000. Completed the requirements for the Master of Science degree with a maj or in Computer Science at Oklahoma State University in December, 2003.
Experience: Employed by Oklahoma State University, Department of Electrical Engineering as a teaching assistant for Embedded Systems; served as a webmaster for the Oklahoma State University, Department of Multicultural Affairs, July 2003 to present.
/~