Abstract:
Disclosed are methods for determining the neighborhood local view of a mobile node in time which can facilitate the forwarding decision in the design of network protocols. In conventional mobile ad hoc networks nodes set up local topology view based on periodical received “Hello” messages. The conventional method is replaced with proactive and adaptive methods of predicting locations of nodes based on preserved historical information extracted from received “Hello” messages and constructing neighborhood view by aggregating predicted locations. This method is useful for providing updated and consistent topology local view that a network communication employs to determine optimal forward decisions and improve communication performance.

Description:
BACKGROUND 
       [0001]    1. Technical Field 
         [0002]    The invention relates generally to the communication of wireless LANs and more specifically to communication of mobile ad hoc networks. Still more specifically, the invention relates to methods of predicting the mobility of mobile devices for constructing precise neighborhood local view in such networks. 
         [0003]    2. Description of the Related Art 
         [0004]    In most existing localized protocols for Mobile Ad hoc Networks (MANETs), each node emits “Hello” messages to advertise its presence and update its information. In periodical update, “Hello” intervals at different nodes can be asynchronous to reduce message collision. Each node extracts its neighbors&#39; information from latest received “Hello” messages to construct a local view of its neighborhood (e.g., 1-hop location information). 
         [0005]    However, there are two main problems in that kind of neighborhood local view construction scheme. 1) Outdated local view: when we consider a general case where broadcasts or routing occur within “Hello” message interval while nodes move during that interval, forward decisions of localized protocols will be based on outdated neighborhood view; 2) Asynchronous local view: asynchronous sample frequency at each node, asynchronous “Hello” intervals in periodical update, and different “Hello” intervals in conditional update will cause asynchronous information for each neighbor in neighborhood local view. 
         [0006]    Forward decisions based on outdated and asynchronous network topology view may be inaccurate and hence cause delivery failure which can induce poor coverage of broadcast task or route failures. If the dynamics of the network topology could be predicted in advance, appropriate forward decision can be made in order to avoid or reduce delivery failures. Neighborhood tracking is a task to determine the neighborhood local view of a mobile node in time which can facilitate the forwarding decision in network protocols&#39; design. Therefore, it could be of significance to the design of network protocols. 
         [0007]    There exist two kinds of work which try to maintain accurate topology view to assist the route path selection. First, in the work of Kim et al. (W.-I. Kim, D. H. Kwon, and Y.-J. Suh, “A reliable route selection algorithm using local positioning systems in mobile ad hoc networks,”  In Proceedings the IEEE International Conference on Communications,  Amsterdam, USA, pp. 3191-3195, June, 2001.), a stable zone and a caution zone of each node have been defined based on a node&#39;s position, speed, and direction information obtained from GPS. Specifically, a stable zone is the area in which a mobile node can maintain a relatively stable link with its neighbor nodes since they are located close to each other. A caution zone is the area in which a node can maintain an unstable link with its neighbor nodes since they are relatively far from each other. Second, Wu and Dai (J. Wu and F. Dai, “Mobility Control and Its Applications in Mobile Ad Hoc Networks,” Accepted to appear in  Handbook of Algorithms for Wireless Networking and Mobile Computing,  A. Boukerche (ed.), Chapman &amp; Hall/CRC, pp. 22-501-22-518, 2006.) have proposed a conservative “two transmission radius” method to compensate the outdated topology local view. However, all the above approaches are passive since they just try to compensate the inaccuracy of network topology view rather than predict mobile nodes&#39; positions to construct precise network topology view in advance. 
       SUMMARY 
       [0008]    The present invention achieves the foregoing features and results, as well as others, by providing methods to predict the neighborhood of mobile nodes in time in wireless ad hoc networks. 
         [0009]    To address asynchronism problem, the present invention attaches the current sending time into “Hello” messages. Nodes which receive “Hello” messages should include not only message contents but also reception time. By comparing reception time and sending time in “Hello” message, the time difference between two nodes can be calculated. To get a synchronized local view of any node S at any future time t, the present invention sets node S as the reference node and deduce its neighbor&#39;s synchronous time t′. To construct the updated neighborhood local view, piecewise linear and nonlinear prediction models are proposed which make use of a node&#39;s latest two or one information to predict its future location. By aggregating predicted neighbors&#39; location, node S can construct the updated and synchronous neighborhood view at actual transmission time. 
         [0010]    Using the methods of the invention, a dynamic approach can be made use of to construct predictive synchronized neighborhood local view when a routing or broadcasting task is triggered. Then the existing localized protocols can make forward decisions based on this updated local view which can improve the performance of protocols. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0011]      FIG. 1  is a flowchart showing a method for predicting the mobility in mobile ad hoc networks according to a embodiment consistent with the present invention. 
           [0012]      FIG. 2  is a analysis model for prediction interval according to a embodiment consistent with the present invention. 
           [0013]      FIG. 3A  is the sketch of location-based prediction model according to a embodiment consistent with the present invention. 
           [0014]      FIG. 3B  is the sketch of velocity-aided prediction model according to a embodiment consistent with the present invention. 
           [0015]      FIG. 3C  is the sketch of constant acceleration prediction model according to a embodiment consistent with the present invention. 
           [0016]      FIG. 4  is the function of smaller neighborhood range according to a embodiment consistent with the present invention. 
           [0017]      FIG. 5  is analysis model for smaller neighborhood range according to a embodiment consistent with the present invention. 
           [0018]      FIGS. 6A and 6B  show examples of neighborhood tracking in periodical update where the Z dimension coordinates according to a embodiment consistent with the present invention. 
       
    
    
     DETAILED DESCRIPTION 
     1. Predictive and Synchronized Neighborhood Tracking Overview 
       [0019]    Neighborhood tracking method flowchart of the present invention is shown in  FIG. 1 . In  FIG. 1 , method for predicting the mobility in mobile ad hoc networks is illustrated. First step is constructing neighborhood local view (S 101 ). Next step is predicting locations of said node and its neighbor nodes at the same future time using said neighborhood local view (S 103 ). Next step is updating neighborhood local view by aggregating neighbors&#39; predicted location (S 105 ). And next step is reconstructing said neighborhood local view by setting smaller neighborhood range (S 107 ). 
         [0020]    In  FIG. 1 , to address the asynchronous and outdated local view problem, the location of node S and the location of all its neighbor nodes are predicted at the same future time t p  (with node S&#39;s clock) which is the node S&#39;s actual emission time t b +broadcast delay time t D . By collecting the predicted locations, node S can construct an updated and synchronized neighborhood local view. The delay time t D  includes not only the wireless network transmission delay t e  but also the packet and transmission processing time t s . t e  is basically fixed in wireless networks while t s  can vary according to packet size. 
         [0021]    Moreover, the prediction interval is also affected by some other factors and has a bound which we will analyze in next separate section. However there are still two issues: how to calculate neighbor nodes&#39; corresponding prediction time and how to predict nodes&#39; locations. 
         [0022]    To calculate any neighbor node A&#39;s prediction time t′ p , its time difference to reference node S, t′ d  is calculated. Then t′ p =t p +t′ d . To get t′ d , local sending time t 1  and local received time t r  are included in “hello” messages. Then the time difference between two nodes can be calculated as t′ d =t l −t r +t e  where t e  is the wireless network transmission delay. 
       2. Analysis for Prediction Interval 
       [0023]    When we schedule an actual transmission time for node S, if within the prediction interval, neighbor nodes already move out of the transmission range of node S, our prediction scheme will have no meaning. Therefore we analyze the Transmission Range Dwell Time, T dwell , the time period within which any neighbor node U stays in the transmission range of node S. R dwell  is the rate of crossing the boundary of its transmission range. 
         [0024]      FIG. 2  shows an analytical model where we assume that node S moves with a velocity {right arrow over (V)} 1  and node U moves with a velocity {right arrow over (V)} 2 . The relative velocity {right arrow over (V)} of node U to node S is given by 
         [0000]        {right arrow over (V)}={right arrow over (V)}   2   −{right arrow over (V)}   1    (1) 
         [0025]    The magnitude of {right arrow over (V)} is given by 
         [0000]        V =√{square root over ( V   1   2   +V   2   2 −2 V   1   V   2  cos(Φ 1 −Φ 2 ))}  (2) 
         [0026]    where V 1  and V 2  are the magnitudes of {right arrow over (V)} 1  and {right arrow over (V)} 2 , respectively. The mean value of V is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       E 
                        
                       
                         [ 
                         V 
                         ] 
                       
                     
                     = 
                     
                       
                         ∫ 
                         
                           V 
                           min 
                         
                         
                           V 
                           max 
                         
                       
                        
                       
                         
                           ∫ 
                           
                             V 
                             min 
                           
                           
                             V 
                             max 
                           
                         
                          
                         
                           
                             ∫ 
                             0 
                             
                               2 
                                
                               π 
                             
                           
                            
                           
                             
                               ∫ 
                               0 
                               
                                 2 
                                  
                                 π 
                               
                             
                              
                             
                               
                                 
                                   
                                     u 
                                     1 
                                     2 
                                   
                                   + 
                                   
                                     u 
                                     2 
                                     2 
                                   
                                   - 
                                   
                                     2 
                                      
                                     
                                       u 
                                       1 
                                     
                                      
                                     
                                       u 
                                       2 
                                     
                                      
                                     
                                       cos 
                                        
                                       
                                         ( 
                                         
                                           
                                             φ 
                                             1 
                                           
                                           - 
                                           
                                             φ 
                                             2 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                                
                               
                                 fv 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                   , 
                   
                     v 
                     2 
                   
                   , 
                   
                     Φ 
                     1 
                   
                   , 
                   
                     
                       
                         Φ 
                         2 
                       
                        
                       
                         ( 
                         
                           
                             u 
                             1 
                           
                           , 
                           
                             u 
                             2 
                           
                           , 
                           
                             φ 
                             1 
                           
                           , 
                           
                             φ 
                             2 
                           
                         
                         ) 
                       
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         φ 
                         1 
                       
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         φ 
                         2 
                       
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         u 
                         1 
                       
                     
                      
                     
                         
                     
                      
                     
                        
                       
                         u 
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0027]    where f V     1     ,V     2     Φ     1     ,Φ     2   (v 1 ,v 2 ,φ 1 ,φ 2 ) is the joint pdf of the random variables V 1 , V 2 , Φ 1 , Φ 2 , V min  and V max  are the minimum and maximum moving speeds, the symbol E[V] is an average value of the random variable V. Since the moving speeds V 1  and V 2  and directions Φ 1  and Φ 2  of nodes S and U are independent, Eq. (3) can be simplified 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       [ 
                       V 
                       ] 
                     
                   
                   = 
                   
                     
                       ∫ 
                       
                         V 
                         min 
                       
                       
                         V 
                         max 
                       
                     
                      
                     
                       
                         ∫ 
                         
                           V 
                           min 
                         
                         
                           V 
                           max 
                         
                       
                        
                       
                         
                           ∫ 
                           0 
                           
                             2 
                              
                             π 
                           
                         
                          
                         
                           
                             ∫ 
                             0 
                             
                               2 
                                
                               π 
                             
                           
                            
                           
                             
                               
                                 
                                   υ 
                                   1 
                                   2 
                                 
                                 + 
                                 
                                   υ 
                                   2 
                                   2 
                                 
                                 - 
                                 
                                   2 
                                    
                                   
                                     υ 
                                     1 
                                   
                                    
                                   
                                     υ 
                                     2 
                                   
                                    
                                   
                                     cos 
                                      
                                     
                                       ( 
                                       
                                         
                                           φ 
                                           1 
                                         
                                         - 
                                         
                                           φ 
                                           2 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                              
                             
                               
                                 f 
                                 V 
                               
                                
                               
                                 ( 
                                 
                                   υ 
                                   1 
                                 
                                 ) 
                               
                             
                              
                             
                               
                                 f 
                                 V 
                               
                                
                               
                                 ( 
                                 
                                   υ 
                                   2 
                                 
                                 ) 
                               
                             
                              
                             
                               
                                 f 
                                 Φ 
                               
                                
                               
                                 ( 
                                 
                                   φ 
                                   1 
                                 
                                 ) 
                               
                             
                              
                             
                               
                                 f 
                                 Φ 
                               
                                
                               
                                 ( 
                                 
                                   φ 
                                   2 
                                 
                                 ) 
                               
                             
                              
                             
                                
                               
                                 φ 
                                 1 
                               
                             
                              
                             
                                 
                             
                              
                             
                                
                               
                                 φ 
                                 2 
                               
                             
                              
                             
                                 
                             
                              
                             
                                
                               
                                 υ 
                                 1 
                               
                             
                              
                             
                                 
                             
                              
                             
                                
                               
                                 υ 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0028]    If Φ 1  and Φ 2  are uniformly distributed in (0, 2π), Eq. (4) can be further rewritten as 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       [ 
                       V 
                       ] 
                     
                   
                   = 
                   
                     
                       1 
                       
                         π 
                         2 
                       
                     
                      
                     
                       
                         ∫ 
                         
                           V 
                           min 
                         
                         
                           V 
                           max 
                         
                       
                        
                       
                         
                           ∫ 
                           
                             V 
                             min 
                           
                           
                             V 
                             max 
                           
                         
                          
                         
                           
                             ( 
                             
                               
                                 υ 
                                 1 
                               
                               + 
                               
                                 υ 
                                 2 
                               
                             
                             ) 
                           
                            
                           
                             
                               F 
                               e 
                             
                              
                             
                               ( 
                               
                                 
                                   2 
                                    
                                   
                                     
                                       
                                         υ 
                                         1 
                                       
                                        
                                       
                                         υ 
                                         2 
                                       
                                     
                                   
                                 
                                 
                                   
                                     υ 
                                     1 
                                   
                                   + 
                                   
                                     υ 
                                     2 
                                   
                                 
                               
                               ) 
                             
                           
                            
                           
                               
                           
                            
                           
                             
                               f 
                               V 
                             
                              
                             
                               ( 
                               
                                 υ 
                                 1 
                               
                               ) 
                             
                           
                            
                           
                             
                               f 
                               V 
                             
                              
                             
                               ( 
                               
                                 υ 
                                 2 
                               
                               ) 
                             
                           
                            
                           
                              
                             
                               υ 
                               1 
                             
                           
                            
                           
                               
                           
                            
                           
                              
                             
                               υ 
                               2 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0029]    where 
         [0000]    
       
         
           
             
               
                 F 
                 ɛ 
               
                
               
                 ( 
                 k 
                 ) 
               
             
             = 
             
               
                 ∫ 
                 0 
                 1 
               
                
               
                 
                   
                     
                       1 
                       - 
                       
                         
                           k 
                           2 
                         
                          
                         
                           t 
                           2 
                         
                       
                     
                     
                       1 
                       - 
                       
                         t 
                         2 
                       
                     
                   
                 
                  
                 
                     
                 
                  
                 
                    
                   t 
                 
               
             
           
         
       
     
         [0000]    is complete elliptic integral of the second kind. Therefore, now we can consider that node S is stationary, and node U is moving at a relative velocity. 
         [0030]    Assume that nodes are distributed uniformly and nodes&#39; moving direction is distributed uniformly over [0, 2π], the mean value of R dwell  is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     R 
                     dwell 
                   
                   = 
                   
                     
                       
                         E 
                          
                         
                           [ 
                           V 
                           ] 
                         
                       
                        
                       L 
                     
                     
                       π 
                        
                       
                           
                       
                        
                       A 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0031]    where A is the area of the transmission range and L is the perimeter of this area. Therefore 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       [ 
                       
                         T 
                         dwell 
                       
                       ] 
                     
                   
                   = 
                   
                     
                       π 
                        
                       
                           
                       
                        
                       A 
                     
                     
                       
                         E 
                          
                         
                           [ 
                           V 
                           ] 
                         
                       
                        
                       L 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0032]    In a word, our prediction interval should be bounded within the time E[T dwell ]. 
       3. Mobility Prediction 
       [0033]    Camp et al. (T. Camp, J. Boleng and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,”  Wireless Comm.  &amp;  Mobile Computing  ( WCMC ),  special issue on mobile ad hoc networking: research, trends and applications,  vol. 2, no. 5, pp. 483-502, 2002.) have given a comprehensive survey on mobility models for MANETs, from which we can find that in some models nodes move linearly before changing direction. In the other models, they are not precisely linearly movement, nodes also move linearly in a segment view. 
         [0034]    Location-based Prediction: Suppose that there are two latest updates for a particular node respectively at time t 1h  and t 2h  (t 1h &gt;t 2h ) with location information of (x 1h , y 1h , z 1h ) and (x 2h , y 2h , z 2h ). Assume at least within two successive update periods the node moves in a straight line with fixed speed as depicted in  FIG. 3A , we obtain 
         [0000]    
       
         
           
             
               
                 
                   { 
                   
                     
                       
                         
                           
                             
                               
                                 x 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                               - 
                               
                                 x 
                                 
                                   2 
                                    
                                   h 
                                 
                               
                             
                             
                               
                                 t 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                               - 
                               
                                 t 
                                 
                                   2 
                                    
                                   h 
                                 
                               
                             
                           
                           = 
                           
                             
                               
                                 x 
                                 p 
                               
                               - 
                               
                                 x 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                             
                             
                               
                                 t 
                                 p 
                               
                               - 
                               
                                 t 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               
                                 y 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                               - 
                               
                                 y 
                                 
                                   2 
                                    
                                   h 
                                 
                               
                             
                             
                               
                                 t 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                               - 
                               
                                 t 
                                 
                                   2 
                                    
                                   h 
                                 
                               
                             
                           
                           = 
                           
                             
                               
                                 y 
                                 p 
                               
                               - 
                               
                                 y 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                             
                             
                               
                                 t 
                                 p 
                               
                               - 
                               
                                 t 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               
                                 z 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                               - 
                               
                                 z 
                                 
                                   2 
                                    
                                   h 
                                 
                               
                             
                             
                               
                                 t 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                               - 
                               
                                 t 
                                 
                                   2 
                                    
                                   h 
                                 
                               
                             
                           
                           = 
                           
                             
                               
                                 z 
                                 p 
                               
                               - 
                               
                                 z 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                             
                             
                               
                                 t 
                                 p 
                               
                               - 
                               
                                 t 
                                 
                                   1 
                                    
                                   h 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0035]    then the location (x p , y p , z p ) at a future time t p  can be calculated as 
         [0000]    
       
         
           
             
               
                 
                   { 
                   
                     
                       
                         
                           
                             x 
                             p 
                           
                           = 
                           
                             
                               x 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   
                                     x 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     x 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                                 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     t 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             y 
                             p 
                           
                           = 
                           
                             
                               y 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   
                                     y 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     y 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                                 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     t 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             z 
                             p 
                           
                           = 
                           
                             
                               z 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   
                                     z 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     z 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                                 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     t 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                               
                                
                               
                                 
                                   ( 
                                   
                                     
                                       t 
                                       p 
                                     
                                     - 
                                     
                                       t 
                                       
                                         1 
                                          
                                         h 
                                       
                                     
                                   
                                   ) 
                                 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0036]    In the conditional update, however, this model cannot be used because the latest update represents considerable changes compared to previous update. 
         [0037]    Velocity-aided Prediction: Let (v′ x , v′ y , v′ z ) be the velocity of its latest update for a particular node. Assume the node moves with the speed within update period as depicted in  FIG. 3B , the location (x p , y p , z p ) at a future time t p  can be calculated as 
         [0000]    
       
         
           
             
               
                 
                   { 
                   
                     
                       
                         
                           
                             x 
                             p 
                           
                           = 
                           
                             
                               x 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 υ 
                                 x 
                                 ′ 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             y 
                             p 
                           
                           = 
                           
                             
                               y 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 υ 
                                 y 
                                 ′ 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             z 
                             p 
                           
                           = 
                           
                             
                               z 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   υ 
                                   z 
                                   ′ 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       t 
                                       p 
                                     
                                     - 
                                     
                                       t 
                                       
                                         1 
                                          
                                         h 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0038]    In high speed mobility networks we can assume the force on the moving node is constant, that is, nodes move with constant acceleration. 
         [0039]    Constant Acceleration Prediction: Let (v′ x , v′ y , v′ z ) and (″ x , v″ y , v″ z ) respectively be the velocity of those two update as depicted in  FIG. 3C . The principle of motion law are 
         [0000]        V=v+at    (11) 
         [0040]    and 
         [0000]    
       
         
           
             
               
                 
                   S 
                   = 
                   
                     
                       
                         υ 
                          
                         
                             
                         
                          
                         t 
                       
                       + 
                       
                         
                           1 
                           2 
                         
                          
                         
                           at 
                           2 
                         
                       
                     
                     = 
                     
                       
                         
                           υ 
                           _ 
                         
                          
                         
                             
                         
                          
                         t 
                       
                       = 
                       
                         
                           
                             υ 
                             + 
                             V 
                           
                           2 
                         
                          
                         t 
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0041]    where S is the displacement, v is the initial velocity and a is the acceleration during period t. We employ V denoting the final velocity after period t. 
         [0042]    Assume the fixed acceleration (a x , a y , a z ), and we apply above principle to X-dimension, we can obtain 
         [0000]    
       
         
           
             
               
                 
                   { 
                   
                     
                       
                         
                           
                             υ 
                             x 
                             ′ 
                           
                           = 
                           
                             
                               υ 
                               x 
                               ″ 
                             
                             + 
                             
                               
                                 a 
                                 x 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                   - 
                                   
                                     t 
                                     
                                       2 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             υ 
                             x 
                           
                           = 
                           
                             
                               υ 
                               x 
                               ′ 
                             
                             + 
                             
                               
                                 a 
                                 x 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               x 
                               p 
                             
                             - 
                             
                               x 
                               
                                 1 
                                  
                                 h 
                               
                             
                           
                           = 
                           
                             
                               
                                 ( 
                                 
                                   
                                     υ 
                                     x 
                                     ′ 
                                   
                                   + 
                                   
                                     υ 
                                     x 
                                   
                                 
                                 ) 
                               
                               2 
                             
                              
                             
                               ( 
                               
                                 
                                   t 
                                   p 
                                 
                                 - 
                                 
                                   t 
                                   
                                     1 
                                      
                                     h 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0043]    Then we can get the expected location x p  as: 
         [0000]    
       
         
           
             
               
                 
                   
                     x 
                     p 
                   
                   = 
                   
                     
                       x 
                       
                         1 
                          
                         h 
                       
                     
                     + 
                     
                       
                         
                           
                             2 
                              
                             
                               υ 
                               x 
                               ′ 
                             
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   υ 
                                   x 
                                   ′ 
                                 
                                 - 
                                 
                                   υ 
                                   x 
                                   ″ 
                                 
                               
                               ) 
                             
                              
                             
                               
                                 
                                   t 
                                   p 
                                 
                                 - 
                                 
                                   t 
                                   
                                     1 
                                      
                                     h 
                                   
                                 
                               
                               
                                 
                                   t 
                                   
                                     1 
                                      
                                     h 
                                   
                                 
                                 - 
                                 
                                   t 
                                   
                                     2 
                                      
                                     h 
                                   
                                 
                               
                             
                           
                         
                         2 
                       
                        
                       
                         ( 
                         
                           
                             t 
                             p 
                           
                           - 
                           
                             t 
                             
                               1 
                                
                               h 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0044]    Since Y and Z dimensions are the same with X-dimension, we obtain 
         [0000]    
       
         
           
             
               
                 
                   { 
                   
                     
                       
                         
                           
                             x 
                             p 
                           
                           = 
                           
                             
                               x 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   
                                     2 
                                      
                                     
                                       υ 
                                       x 
                                       ′ 
                                     
                                   
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           υ 
                                           x 
                                           ′ 
                                         
                                         - 
                                         
                                           υ 
                                           x 
                                           ″ 
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       
                                         
                                           t 
                                           p 
                                         
                                         - 
                                         
                                           t 
                                           
                                             1 
                                              
                                             h 
                                           
                                         
                                       
                                       
                                         
                                           t 
                                           
                                             1 
                                              
                                             h 
                                           
                                         
                                         - 
                                         
                                           t 
                                           
                                             2 
                                              
                                             h 
                                           
                                         
                                       
                                     
                                   
                                 
                                 2 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             y 
                             p 
                           
                           = 
                           
                             
                               y 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   
                                     2 
                                      
                                     
                                       υ 
                                       y 
                                       ′ 
                                     
                                   
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           υ 
                                           y 
                                           ′ 
                                         
                                         - 
                                         
                                           υ 
                                           y 
                                           ″ 
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       
                                         
                                           t 
                                           p 
                                         
                                         - 
                                         
                                           t 
                                           
                                             1 
                                              
                                             h 
                                           
                                         
                                       
                                       
                                         
                                           t 
                                           
                                             1 
                                              
                                             h 
                                           
                                         
                                         - 
                                         
                                           t 
                                           
                                             2 
                                              
                                             h 
                                           
                                         
                                       
                                     
                                   
                                 
                                 2 
                               
                                
                               
                                 ( 
                                 
                                   
                                     t 
                                     p 
                                   
                                   - 
                                   
                                     t 
                                     
                                       1 
                                        
                                       h 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             z 
                             p 
                           
                           = 
                           
                             
                               z 
                               
                                 1 
                                  
                                 h 
                               
                             
                             + 
                             
                               
                                 
                                   
                                     2 
                                      
                                     
                                       υ 
                                       z 
                                       ′ 
                                     
                                   
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           υ 
                                           z 
                                           ′ 
                                         
                                         - 
                                         
                                           υ 
                                           z 
                                           ″ 
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       
                                         
                                           t 
                                           p 
                                         
                                         - 
                                         
                                           t 
                                           
                                             1 
                                              
                                             h 
                                           
                                         
                                       
                                       
                                         
                                           t 
                                           
                                             1 
                                              
                                             h 
                                           
                                         
                                         - 
                                         
                                           t 
                                           
                                             2 
                                              
                                             h 
                                           
                                         
                                       
                                     
                                   
                                 
                                 2 
                               
                                
                               
                                 
                                   ( 
                                   
                                     
                                       t 
                                       p 
                                     
                                     - 
                                     
                                       t 
                                       
                                         1 
                                          
                                         h 
                                       
                                     
                                   
                                   ) 
                                 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0045]    Finally, by collecting predicted locations, we can construct an updated and consistent neighborhood local view. 
       4. Enhancement Scheme 
       [0046]    Inaccurate Local View: Although we provide a predictive and synchronized solution, however there exists another possible situation which can cause inaccurate local view. That is, a node S has not received a node U&#39;s latest update, so S neglects the existence of U. However U moves into the node S&#39;s neighborhood during prediction time.  FIG. 4(   a ) shows the predicted local view of node S, where node U is not included although it is the neighbor of S. 
         [0047]    Smaller Neighborhood Range Scheme: In order to prevent the afore mentioned problem, we propose how to reconstruct the neighborhood local view of S by applying smaller neighborhood radius (SR). By applying SR scheme, node S achieves smaller but accurate local view which is shown in  FIG. 4(   b ). 
         [0048]    Consider two nodes S and U as shown in  FIG. 5 . Node U is not within the transmission range of node S at time t 0  and moves to position U′ at t 1 . Assume that their distance at t 0  is d and U moves a distance of x with respect to S at t 1 . The probability that U enters into the transmission range of S is 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       
                         x 
                         , 
                         d 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             0 
                              
                             
                               : 
                             
                           
                         
                         
                           
                             x 
                             &lt; 
                             
                               d 
                               - 
                               
                                 R 
                                 1 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               φ 
                               π 
                             
                              
                             
                               : 
                             
                           
                         
                         
                           
                             
                               d 
                               - 
                               
                                 R 
                                 1 
                               
                             
                             ≤ 
                             x 
                             ≤ 
                             
                               d 
                               + 
                               
                                 R 
                                 1 
                               
                             
                           
                         
                       
                       
                         
                           
                             0 
                              
                             
                               : 
                             
                           
                         
                         
                           
                             
                               x 
                               &gt; 
                               
                                 d 
                                 + 
                                 
                                   R 
                                   1 
                                 
                               
                             
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0049]    where 
         [0000]    
       
         
           
             φ 
             = 
             
               arccos 
               ( 
               
                 
                   
                     x 
                     2 
                   
                   + 
                   
                     d 
                     2 
                   
                   - 
                   
                     R 
                     1 
                     2 
                   
                 
                 
                   2 
                    
                   xd 
                 
               
               ) 
             
           
         
       
     
         [0000]    is the largest value of □SUU′ that satisfies R 2 &lt;R 1 . The probability that any node moves into the transmission range of node S at t 1  is 
         [0000]    
       
         
           
             
               
                 
                   
                     p 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∫ 
                       
                         R 
                         t 
                       
                       ∞ 
                     
                      
                     
                       
                         p 
                          
                         
                           ( 
                           
                             x 
                             , 
                             d 
                           
                           ) 
                         
                       
                        
                       
                           
                       
                        
                       
                          
                         d 
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0050]    The probability that a node with any relative speed v with respect to S moves into its transmission range is 
         [0000]    
       
         
           
             
               
                 
                   p 
                   = 
                   
                     
                       ∫ 
                       0 
                       
                         2 
                          
                         s 
                       
                     
                      
                     
                       
                         
                           f 
                           
                              
                             
                               V 
                               → 
                             
                              
                           
                         
                          
                         
                             
                         
                         ( 
                         v 
                         ) 
                       
                        
                       
                         p 
                          
                         
                           ( 
                           fv 
                           ) 
                         
                       
                        
                       
                          
                         v 
                       
                     
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0051]    where {right arrow over (V)} is the random relative velocity vector proposed in previous section and s is the maximum speed for any node. Recall, the direction of {right arrow over (V)} is also uniformly distributed in [0, 2π] and is independent of the speed of {right arrow over (V)}. We know that □{right arrow over (V)}□ is uniformly distributed in [0, 2π]. We calculate f □ {right arrow over (V)} □  at a give time t as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             f 
                             
                                
                               
                                 V 
                                 → 
                               
                                
                             
                           
                            
                           
                             ( 
                             t 
                             ) 
                           
                         
                         ≈ 
                           
                          
                         
                           
                             
                               
                                 F 
                                 
                                    
                                   
                                     V 
                                     → 
                                   
                                    
                                 
                               
                                
                               
                                 ( 
                                 
                                   δ 
                                   t 
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 F 
                                 
                                    
                                   
                                     V 
                                     → 
                                   
                                    
                                 
                               
                                
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           
                             δ 
                             t 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             P 
                              
                             
                               ( 
                               
                                 t 
                                 ≤ 
                                 
                                    
                                   
                                     V 
                                     → 
                                   
                                    
                                 
                                 ≤ 
                                 
                                   t 
                                   + 
                                   
                                     δ 
                                     t 
                                   
                                 
                               
                               ) 
                             
                           
                           
                             δ 
                             t 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           = 
                             
                            
                           
                             
                               ∮ 
                               
                                 ( 
                                 
                                   0 
                                   , 
                                   0 
                                 
                                 ) 
                               
                               
                                 ( 
                                 
                                   
                                     2 
                                      
                                     π 
                                   
                                   , 
                                   s 
                                 
                                 ) 
                               
                             
                              
                             
                               
                                 ∮ 
                                 
                                   ( 
                                   
                                     0 
                                     , 
                                     0 
                                   
                                   ) 
                                 
                                 
                                   ( 
                                   
                                     
                                       2 
                                        
                                       π 
                                     
                                     , 
                                     s 
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                   
                                     
                                       R 
                                       ( 
                                       
                                         
                                           
                                             V 
                                             → 
                                           
                                           2 
                                         
                                         , 
                                         
                                           
                                             V 
                                             → 
                                           
                                           1 
                                         
                                         , 
                                         t 
                                         , 
                                         
                                           t 
                                           + 
                                           
                                             δ 
                                             t 
                                           
                                         
                                       
                                       ) 
                                     
                                     
                                       
                                         
                                           ( 
                                           
                                             2 
                                              
                                             π 
                                              
                                             
                                                 
                                             
                                              
                                             s 
                                           
                                           ) 
                                         
                                         2 
                                       
                                        
                                       
                                         δ 
                                         t 
                                       
                                     
                                   
                                   · 
                                   
                                      
                                     
                                       
                                         V 
                                         → 
                                       
                                       2 
                                     
                                   
                                 
                                  
                                 
                                    
                                   
                                     
                                       V 
                                       → 
                                     
                                     1 
                                   
                                 
                               
                             
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0052]    where f □ {right arrow over (V)} □(t)  is the distribution function, δ t  is a small positive value, and 
         [0000]    
       
         
           
             
               
                 
                   
                     R 
                     ( 
                     
                       
                         
                           V 
                           → 
                         
                         2 
                       
                       , 
                       
                         
                           V 
                           → 
                         
                         1 
                       
                       , 
                       a 
                       , 
                       b 
                     
                     ) 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                              
                             
                               : 
                             
                           
                         
                         
                           
                             a 
                             ≤ 
                             
                                
                               
                                 
                                   
                                     V 
                                     → 
                                   
                                   2 
                                 
                                 - 
                                 
                                   
                                     V 
                                     → 
                                   
                                   1 
                                 
                               
                                
                             
                             ≤ 
                             b 
                           
                         
                       
                       
                         
                           
                             0 
                              
                             
                               : 
                             
                           
                         
                         
                           
                             otherwise 
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0053]    Combining all above formulas, we can calculate the probability that any node U moves into the transmission range of node S. Then, the expected value of smaller neighborhood range (SR) can be given by 
         [0000]        E[SR ]=(1− p ) R   1    (21) 
       5. Simulation Results  
       [0054]    We use ns-2.28 and its CMU wireless extension as simulation tool and assume AT&amp;T&#39;s Wave LAN PCMCIA card as wireless node model with parameters as listed in Table 1. To demonstrate the comprehensive effectiveness of our proposal, we perform experiments in not only linear (Random Waypoint) but also nonlinear (Gauss-Markov) mobility models which are widely used in simulating protocols designed for MANETs. 
         [0055]    In neighborhood tracking, any node S is randomly chosen to predict its neighbor nodes&#39; locations for constructing local view. Local view construction occurs within update interval. Table 2 displays our simulation parameters. 
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Parameters for wireless node model 
               
             
          
           
               
                   
                 Parameters 
                 Value 
               
               
                   
                   
               
               
                   
                 Frequency 
                 2.4 GHz 
               
               
                   
                 Maximum transmission range 
                 250 m 
               
               
                   
                 MAC protocol 
                 802.11 
               
               
                   
                 Propagation model 
                 free space/two ray ground 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Simulation parameters 
               
             
          
           
               
                   
                 Parameters 
                 Value 
               
               
                   
                   
               
               
                   
                 Simulation network size 
                 900 × 900 m 2   
               
               
                   
                 Mobile nodes speed range 
                 [0, 15] m/s 
               
               
                   
                 Nodes number 
                 50 
               
               
                   
                 Simulation time 
                 50 s 
               
               
                   
                 Periodical update/check interval 
                 2 s 
               
               
                   
                 Prediction interval 
                 20 ms 
               
               
                   
                 Reference distance of conditional update 
                 1 m 
               
               
                   
                   
               
             
          
         
       
     
         [0056]    The sample of predicted local view with velocity-based prediction under periodical update is illustrated in  FIG. 6  where the actual local view and local view based on update information are also shown for comparison. We can find that whatever in linear model or nonlinear mobile environment our predictive neighborhood views are almost the same as actual neighborhoods while update info based views show obvious inaccuracy. 
         [0057]    To evaluate the inaccuracy of local view, we define the metric of position error (PE) as the average distance difference between neighbors&#39; actual positions and their positions in neighborhood view. For any node S suppose there are K neighbors (including S itself) in its jth local view, and for any neighbor i let (x i , y i , z i ) represent the actual location and (x′ i , y′ i , z′ i ) be the location in local view, the PE j  for the jth neighborhood can be calculated as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       1 
                       K 
                     
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         K 
                       
                        
                       
                         [ 
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                   ′ 
                                 
                                 - 
                                 
                                   x 
                                   i 
                                 
                               
                               ) 
                             
                             2 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   y 
                                   i 
                                   ′ 
                                 
                                 - 
                                 
                                   y 
                                   i 
                                 
                               
                               ) 
                             
                             2 
                           
                           + 
                           
                             
                               ( 
                               
                                 
                                   z 
                                   i 
                                   ′ 
                                 
                                 - 
                                 
                                   z 
                                   i 
                                 
                               
                               ) 
                             
                             2 
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0058]    Finally suppose we have W local views, 
         [0000]    
       
         
           
             
               
                 
                   PE 
                   = 
                   
                     
                       1 
                       W 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           1 
                         
                         W 
                       
                        
                       
                         PE 
                         j 
                       
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
         [0059]    The smaller the value of PE is, the more accurate the neighborhood local view is. 
         [0060]    Table 3 and 4 show position error results under Random Waypoint and Gauss-Markov models in our simulation. From above simulation results we can demonstrate (1) both periodical and conditional update info based view has more than three times inaccuracy compared with that of our tracking schemes, which proves the necessary and effectiveness of our proposition, (2) our schemes have very small prediction inaccuracy (especially in linear mobility environment), that is, they can precisely track neighborhood, (3) but different prediction models have different performance: velocity-aided scheme performs much better than other two methods and the constant acceleration model does better than location-based one, (4) in addition, the mobility model and update protocol also affects the performance of our scheme: under different mobility models and update protocols the PE values are also different. 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 PE under Random Waypoint model 
               
             
          
           
               
                   
                 Records Type 
                 Prediction Scheme 
                 PE Value 
               
               
                   
                   
               
               
                   
                 Periodical 
                 Update Info Based 
                 7.258410 
               
               
                   
                 Update 
                 Location-based 
                 0.755039 
               
               
                   
                   
                 Velocity-aided 
                 0.003444 
               
               
                   
                   
                 Constant Acceleration 
                 0.261483 
               
               
                   
                 Conditional 
                 Update Info Based 
                 9.267584 
               
               
                   
                 Update 
                 Velocity-aided 
                 0.000006 
               
               
                   
                   
                 Constant Acceleration 
                 0.637606 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 PE under Gauss-Markov Model 
               
             
          
           
               
                   
                 Records Type 
                 Prediction Scheme 
                 PE Value 
               
               
                   
                   
               
               
                   
                 Periodical 
                 Update Info Based 
                 7.407275 
               
               
                   
                 Update 
                 Location-based 
                 2.281239 
               
               
                   
                   
                 Velocity-aided 
                 0.497334 
               
               
                   
                   
                 Constant Acceleration 
                 1.046533 
               
               
                   
                 Conditional 
                 Update Info Based 
                 9.497269 
               
               
                   
                 Update 
                 Velocity-aided 
                 1.617758 
               
               
                   
                   
                 Constant Acceleration 
                 2.813394 
               
               
                   
                   
               
             
          
         
       
     
         [0061]    What has been described are preferred embodiments of the present invention. The foregoing description is intended to be exemplary and not limiting in nature. Persons skilled in the art will appreciate that various modifications and additions may be made while retaining the novel and advantageous characteristics of the invention and without departing from this spirit. Accordingly, the scope of the invention is defined solely by the appended claims as properly interpreted.