Apparatus and method for management of resources in cellular networks

• US 6,385,454 B1
• Filed: 10/13/1998
• Issued: 05/07/2002
• Est. Priority Date: 10/09/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Tong, Bahl, Paramvir
• Primary Examiner(s): Kincaid, Lester G.
• Application Number:
  US09/170,822
• Time in Patent Office: 1,302 Days
• Field of Search: 455/432, 455/436, 455/437, 455/438, 455/439, 455/440, 455/441, 455/442, 455/443, 455/422, 455/456, 455/517, 455/524, 455/525, 455/450, 455/451, 455/452, 455/453
• US Class Current: 455/450
• CPC Class Codes: H04W 16/06 Hybrid resource partitioning, e.g. channel borrowing
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination

Abstract

Wireless networks require efficient mobility management to cope with frequent mobile handoff and rerouting of connections. The invention treats this problem by developing a hierarchical prediction engine that employs approximate pattern matching and Kalman filtering techniques to yield an accurate prediction of both the immediate next cell to be entered by the mobile and the overall or global route of the mobile unit in the wireless cellular network. The prediction of the mobile'"'"'s future movement is used by the network to reserve resources, relieve congestion, reduce latency, and optimize the establishment of routes in the wireless cellular network.

Claims

1. A method for maintaining a connection between a mobile communications unit and a cellular communications network, the method comprising the steps of:

predicting a route of the unit through cells of the network by comparing a plurality of stored previous routes to an actual route of the unit, wherein the actual route includes cells the unit has crossed during the connection to the network and a predicted next cell that the unit will enter; and

actively reserving one or more resources of the network for use by the unit based at least in part on the predicted route.

2. The method of claim 1 wherein the step of actively reserving bandwidth includes the step of a cell borrowing a channel assigned to another cell using mobile unit'"'"'s movement information that is dynamically predicted.

3. The method of claim 2 wherein the borrowed channel is the same channel being used by the unit to communicate with the network.

4. The method of claim 2 wherein the borrowed channel is preferentially borrowed from an adjacent cell that is along the predicted route.

5. The method of claim 1 above wherein the step of predicting includes the step of generating a user profile containing predicted routes of the user based on routes through the network previously taken by the unit.

6. The method of claim 5 wherein the step of predicting includes the steps of recording the actual path of the unit through the cells of the network, editing one or more of the predicted routes to approximate the actual path of the user, selecting one of the edited routes as the predicted route.

7. The method of claim 1 wherein the steps of predicting the routing of the unit through the network is performed by the unit and communicated to the network, which responds to the receipt of the predicted routing by reserving bandwidth along the predicted route.

8. The method of claim 1 above wherein the step of predicting includes the steps of (i) recording the cells in the network crossed during the present connection of the unit to the network, (ii) predicting the next cell the unit will enter, and (iii) selecting as the predicted route one of several previous routes taken by the unit that best matches the actual path of the unit as determined from (i) and (ii).

9. The method of claim 1 including the steps of estimating the unit'"'"'s intra-cellular trajectory, the trajectory including position, direction and velocity, and predicting the next cell the unit will enter based on the estimated trajectory.

10. The method of claim 9 wherein the step of predicting the next cell includes the step of applying a stochastic signal processing technique.

11. The method of claim 1 wherein the step of actively reserving bandwidth along the predicted route includes the step of estimating the unit'"'"'s time of arrive (ETA) into the predicted next cell and reserving bandwidth within the predicted next cell for a time period based at least in part on the ETA of the unit into the predicted next cell.

12. The method of claim 11 wherein the reserved bandwidth is released if the user does not arrive at the predicted next cell within a time period equal to or greater than the ETA.

13. The method of claim 1 wherein the step of reserving bandwidth includes the step of handing off a channel assignment from a previous cell in the actual path to the predicted cell.

14. The method of claim 1 including the step of arbitrating between adjacent cells for identification of the predicted next cell when the predicted route of the unit meets predetermined criteria with respect to the unit'"'"'s proximity to the border of the adjacent cells.

15. A system for predicting a route through a network by a network user during a connection between the network and the user, the system comprising:

a profile of the network user containing a record of selected routes taken by the user for past connections to the network, wherein each of the routes in the record represents a plurality of routes resembling the recorded route, a memory containing a history of the cells through which the user has traveled during the connection, a sensor for providing a trajectory of the user during the present connection, a prediction engine responsive to the profile, the memory and the trajectory for predicting a sequence of network cells through which the user will pass for the remaining duration of the connection to the network, where the prediction is based on (1) determining an actual route of the user and (2) selecting a recorded route that best resembles the actual route from which the predicted sequence of network cells is determined.

16. The system of claim 15 including a mobile unit that contains the profile of the network user.

17. The system of claim 15 wherein the prediction engine includes a global predictor that identifies a recorded route having a cellular sequence that best fits the cellular sequence through which the user has traveled during the present connection.

18. The system of claim 17 wherein the mobile unit includes the global predictor.

19. The system of claim 17 wherein the prediction engine includes a local predictor that predicts the next cell of the network the user will enter based on the trajectory of the user.

20. The system of claim 15 wherein the network includes a processor for reserving network resources that reserves a channel for the user in a predicted next cell that is the same channel the user is assigned immediately prior to the user entering the predicted next cell.

21. The system of claim 15 wherein the prediction engine includes an editor that edits the recorded routes to match the path through the cells of the network taken by the mobile unit during the present connection.

22. The system of claim 21 wherein the editor includes criteria for selecting the recorded route that requires the least amount of editing to match the present path.

23. The system of claim 22 wherein the editor includes criteria for recognizing the present path as a new route to be recorded into the profile.

24. The system of claim 15 wherein the sensor includes an estimator responsive to a strength of a signal providing the connection between the mobile unit and the network.

25. The system of claim 24 wherein the estimator is a Kalman estimator.

26. The system of claim 15 wherein one of the criteria is that a recorded selected route differs from all other selected routes in the record by a threshold amount.

27. The system of claim 26 wherein at least one of the selected routes is recorded into a record as a difference from another selected route.

28. The system of claim 15 wherein the record includes attributes of the selected routes, including one or more of the following attributes:

the frequency of the user taking each of the selected routes and the age of the last time the user has taken each of the selected routes.

29. The system of claim 15 wherein the recorded routes are indexed by a time at which they occurred.

30. A method for predicting the routing of a mobile communications unit through a communication network of cells, including the steps of:

(i) creating a profile of the mobile communication unit'"'"'s movement through the cells in the network during a connection of the unit to the network, the profile including an identification of the cells through which the unit has moved, (ii) predicting the next cell the unit will enter during the connection, and (iii) selecting as a predicted route one of several previous routes taken by the unit that best matches an actual path of the unit determined from steps (i) and (ii).

31. The method of claim 30 including the step of storing the differences between the route the unit is taking and an existing route the unit has taken.

32. The method of claim 30 wherein the profile has a data structure in which the routes are indexed by their occurrence times.

33. A method for reserving a resource along a predicted route of a mobile unit in a cellular communication network such that the unit maintains a constant channel assignment through one or more adjacent cells in an actual path of the unit, including the steps of (i) estimating the unit'"'"'s time of arrive (ETA) into a predicted next cell, (ii) reserving the resource within the predicted next cell for a time period based at least in part on the ETA of the unit into the predicted next cell, and (iii) releasing the reserved resource if the unit does not arrive at the predicted next cell within a time period derived from the ETA.

34. A method for predicting a route of a mobile unit through a cellular communications network to which the mobile unit is connected, the method comprising the steps of:

predicting a next cell of the network the mobile unit will enter;

recording the mobile unit'"'"'s actual route, which includes cells of the network through which the unit has passed and the predicted next cell;

comparing the actual route to one or more previous routes and generating from the comparison a measurement that quantifies a degree of resemblance between the actual route and each of the previous routes to which the actual route is compared; and

selecting one of the stored routes as the predicted route for the present connection that best resembles the actual route based on an evaluation of the measurement.

35. The method of claim 34 wherein the step of comparing includes the step of measuring the resemblance of the actual route to the previous routes by (a) editing either the actual or one of the previous routes to match the other, and (b) quantifying an amount of the editing required to match the actual and said one of the previous routes.

36. The method of claim 35 wherein the step of selecting includes selecting the previous route requiring the least amount of editing to match the actual route as the previous route best resembling the actual route.