Optimizing hand-off neighbor lists for improved system performance

Method for improving hand-off performance in a code-division multiple access (CDMA) cellular telephone system. A preferred embodiment comprises the analysis of saved hand-off information to minimize the size of neighbor lists for each base station in the cellular telephone system. If a requested base station (for example, base station 618) is listed in any neighbor list of any base station (for example, base stations 605, 617, and 620) involved in the hand-off, then the requested base station is not added to any neighbor list. If the requested base station is not the neighbor lists of any of the base stations involved in the hand-off, then it is added to an initial base station's neighbor list (base station 605).

TECHNICAL FIELD

The present invention relates generally to a method for optimizing performance in a cellular telephone system, and more particularly to a method for optimizing a mobile unit hand-off between a plurality of base stations via the use of an optimized neighbor list in each of the base stations.

BACKGROUND

Generally, when a mobile cellular telephone unit moves around within the coverage area of the cellular telephone system, it will exit the effective coverage area of one base station(s) and enter the effective coverage area of another base station(s). (A base station is also sometimes referred to as a cell-site. The base stations in a cellular telephone system are used to control the communications links from the mobile cellular telephone units and to provide access to the public-switched telephone network.) To provide uninterrupted service, the control of the mobile cellular telephone unit must be passed from base station(s) with the effective coverage area that the mobile cellular telephone unit is exiting and to the base station(s) with the effective coverage area that the mobile cellular telephone unit is entering. This transfer of control is commonly referred to as a hand-off.

There are typically two different types of hand-offs, a hard hand-off and a soft hand-off. Hard hand-offs involve the termination of the control via the base station(s) from the exited effective coverage area prior to the establishment of the control via the base station(s) with the entered effective coverage area. Hard hand-offs can result in the unexpected termination of an existing communications link with the mobile cellular telephone unit if the control with the base station(s) of the entered effective coverage area is not established in a timely manner. Alternatively, soft hand-offs permit a mobile cellular telephone unit to connect to multiple base stations. By simultaneously connecting to multiple base stations, the quality of the communications link is improved. Additionally, since the mobile cellular telephone unit is simultaneously connected to multiple base stations, it is possible for one or more of these base stations to drop off as the mobile cellular telephone unit moves without disconnecting the communications link.

In a code-division multiple access (CDMA) cellular telephone system, both hard and soft hand-offs are permitted. Both soft and hard hand-offs are controlled by a neighbor list. Each base station in the CDMA cellular telephone system has a neighbor list. The neighbor list of a base station is a list of pilot channels of base stations that the mobile cellular telephone unit may handoff to. The mobile cellular telephone unit is continually searching for potential handoff candidates. The searching algorithm focuses on the base stations defined in the neighbor list, in particular a candidate set in the neighbor list. However, the searching algorithm does search all possible pilot channels. Poor quality pilot channels are dropped automatically and good pilot channels are added (if permitted). Ideally, the neighbor list is kept small so that potential pilot channels can be scanned quickly.

The use of the neighbor list can help reduce the time required to search for pilot channels because the neighbor list effectively informs the mobile which pilot offsets should be searched first. To scan all possible pilot channels can take a considerable amount of time and the neighbor list prioritizes the search order for the mobile cellular telephone unit (potentially saving it a lot of time). Once the mobile cellular telephone unit finds a pilot channel (or a plurality of pilot channels) of sufficient strength, the mobile cellular telephone unit can initiate a soft hand-off. In a CDMA cellular telephone system, if a mobile cellular telephone unit is under the control of a plurality of base stations (when there are more than one control links established with different base stations), the quality of the communications channel tends to increase due to the use of signal combining techniques similar to multi-path combining.

When a mobile cellular telephone unit is communicating with a single base station and it requests hands off to another base station, this is commonly referred to as a one-way hand-off. When a hand-off involves two base stations requesting a third, it is commonly referred to as a two-way hand-off. In general, when a mobile cellular telephone unit is communicating with N base stations and requests an N+1 base station, it is performing an N-way hand-off. When a hand-off involves different sectors of a single base station, this is commonly referred to as a softer hand-off.

In a majority of cases, the neighbor list for each base station is created by having a scanner at various places within the base station's effective coverage area detecting as many pilot channels as it can. The scanner detects pilot channels by scanning for pseudo-random number (PN) sequences. Each base station's pilot channel (within a local area) should have a unique PN sequence, although system wide, a single PN sequence may be used by several different base stations. Then, all of the pilot channels are placed in the base station's neighbor list. This method of neighbor list creation ensures that every pilot channel that is detectable within a give base station's effective coverage area is in the neighbor list.

One disadvantage of the prior art is that by placing every detectable pilot channel in the neighbor list, the neighbor list becomes unnecessarily large. A neighbor list that is too large results in an increase in the amount of time that it takes for a mobile cellular telephone unit to search for a pilot channel. This can increase the chance of a communications link being disconnected if a new control link is not established prior to the mobile cellular telephone unit exits the effective coverage area of the base station(s) to which it is currently linked. A problem related to this is that by the time the mobile cellular telephone unit gets around to measuring a particular PN sequence that may or may not correspond to a pilot channel in the neighbor list, it may have become so strong that it has become an interferer and may cause the call to drop.

A second disadvantage of the prior art is that by placing every detectable pilot channel in the neighbor list, it is possible to have multiple pilot channels with the same PN sequence, but associated with different base stations in the neighbor list. This results in ambiguity as to from which base station the pilot channel is being transmitted. This confusion can prevent a hand-off from taking place and may result in the call to drop.

A third disadvantage of the prior art is that by having every detectable pilot channel in the neighbor list, the resulting neighbor list may exceed the neighbor list storage capacity of the mobile cellular telephone unit. This may result in the inclusion of poor hand-off candidates in a portion of the neighbor list stored in the mobile cellular telephone unit while good candidates are excluded due to lack of storage space.

SUMMARY OF THE INVENTION

These and other problems are generally solved or circumvented, and technical advantages are generally achieved, by preferred embodiments of the present invention which optimizes the neighbor list for each base station in a cellular telephone system by parsing a recorded database of successful hand-offs and creating a neighbor list from the successful hand-offs and not by simply placing every detectable pilot channel into the neighbor list.

In accordance with a preferred embodiment of the present invention, a method for creating a neighbor list for use in hand-offs in a cellular communications system comprising: determining a requested base station, a reference base station, and a list of other base stations from a saved call, determining if the requested base station is present in a neighbor list of a base stations listed in the list of other base stations, and adding the requested base station to a neighbor list for an optimal base station if the requested base station is absent from neighbor lists of the reference base station and all base stations listed in the list of other base stations.

In accordance with another preferred embodiment of the present invention, a method for optimizing a neighbor list comprising selecting a saved call from a list of saved calls, determining a requested base station, a reference base station, and a list of other base stations from the saved call, determining if the requested base station is present in a neighbor list of a base stations listed in the list of other base stations, adding the requested base station to a neighbor list for an optimal base station if the requested base station is absent from neighbor lists of the reference base station and all base stations listed in the list of other base stations, and repeating for all remaining saved calls in the list of saved calls.

In accordance with yet another preferred embodiment of the present invention, a method for populating a neighbor list comprising determining a requested base station, a reference base station, and a list of other base stations from call data, searching each base station's neighbor list for an occurrence of the requested base station, wherein each base station is from the list of other base stations, searching the reference base station's neighbor list for an occurrence of the requested base station, and adding the requested base station to an optimal base station's neighbor list if all searches are negative.

An advantage of a preferred embodiment of the present invention is that by scanning a database of requested hand-offs in the creation of the neighbor list for any given base station, the neighbor list will only consist of pilot channels of other base stations that were strong enough to be involved with a hand-off. This results in a smaller neighbor list.

A further advantage of a preferred embodiment of the present invention is that the neighbor list will not include any pilot channels from other base stations that are already present in the neighbor list of base stations already in its neighbor list. This again helps to keep the neighbor list small.

Yet another advantage of a preferred embodiment of the present invention is that by validating composite requested hand-offs in the generation of neighbor lists, the neighbor lists are kept small, minimizing the potential of a single neighbor list containing several pilot channels which use the same PN sequence.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

The present invention will be described with respect to preferred embodiments in a specific context, namely a Code-Division Multiple Access (CDMA) cellular telephone system. The invention may also be applied, however, to cellular communications systems and not just cellular telephone systems. Wherein the main difference between a communications system and a telephone system being that the communications system can be used to transport data (such as video, multimedia, and computer information) as well as voice. The invention also has applications to other cellular communications systems such as systems that are variants of CDMA such as IS95 and IS2000, Universal Mobile Telecommunications Systems (UMTS), 3rdGeneration Mobile Group (3GPP) compliant systems, etc.

With reference now toFIG. 1, there is shown a diagram illustrating an exemplary Code-Division Multiple Access (CDMA) cellular telephone system100with a mobile cellular telephone unit (mobile)105communicating with a base station110. The mobile105is communicating with some device (not shown) through the base station110while a second base station111is operating at a distance and is not involved with the mobile105. The device may be another cellular telephone that is a part of the same CDMA system, another cellular telephone that is a part of a different cellular telephone system, or a land-line telephone. The second base station111may be too far away from the mobile105so that its pilot channel is not of sufficient strength to be measured by the mobile105. If the second base station111is sufficiently close to the mobile105so that its pilot channel may be detected and if the base station111meets certain hand-off requirements (as specified in the CDMA technical standards), the mobile105will attempt to hand-off to the second base station111.

With reference toFIG. 2, there is shown a diagram illustrating an exemplary CDMA cellular telephone system200with a mobile205that has established communications links with three base stations (base stations210,211, and212). The mobile205uses all three communications links to help improve the performance of its communications to some device (not shown). The three communications links with the three base stations210,211, and212are combined to produce a single data stream with better performance characteristics than any one of the communications links alone. The use of multiple communications links in a CDMA cellular system to improve performance is well known by those of ordinary skill in the art of the present invention. A fourth base station213is not involved with the mobile205.

As discussed previously, when a mobile or a base station detects that an existing communications link has degraded below a certain predetermined minimum, the mobile will attempt to drop the link. Of course, if a mobile is only linked to one base station, it will not attempt to drop the link until it has been able to detect a suitable hand-off candidate. As an example, the mobile205(as displayed inFIG. 2) may have originally started with a single communications link with base station211. Then, as the mobile205moved in a north-easterly (assuming that north is towards the top ofFIG. 2) direction, a one-way hand-off was created with the base station210and then finally, a two-way hand-off was created with the base station212. When a mobile205is involved in an N-way hand-off, there is one base station that is referred to as a requested base station and there is one base station that is referred to as a reference base station. The requested base station is the base station that is being added, while the reference base station is the station with which the mobile is obtaining its reference timing information from. Reference timing information is information that is used by the mobile205to help it detect and then attempt to hand-off to the requested base station. For example, in the two-way hand-off example above, the requested base station is the base station212while the reference base station is the base station211.

With reference now toFIG. 3a,there is shown a diagram illustrating an exemplary CDMA cellular system300with a plurality of base stations and the creation of a neighbor list for a base station305(referred to as “BS0”) using a prior art technique. As discussed previously, a prior art technique for creating a neighbor list involves placing a detector at various places with the base station BS0's effective coverage area310and storing each detected pilot channel as an element of the neighbor list.FIG. 3adisplays six additional base stations (base stations315–320) whose pilot signals are detectable from within the effective coverage area310of base station BS0305.

With reference now toFIG. 3b,there is shown a neighbor list370for the base station BS0305(FIG. 3a). The neighbor list370for the base station “BS0”305has six elements, one for each of the six base stations whose pilot channel was detected from within the effective coverage area310of the base station “BS0”305. The six base stations are illustrated inFIG. 3a.Ordering of the neighbor list can be performed by some priority assigned to each of the base stations in the neighbor list or it may simply be arbitrary. The ordering of the neighbor list is well understood by those of ordinary skill in the art of the present invention.

A problem with having large neighbor lists at the base stations is that when a mobile is communicating with and through a base station(s), the mobile stores the neighbor list of each base station with which it is communicating. The various neighbor lists are stored in what is known as a composite neighbor list. For example, if a mobile is communicating with a single base station, then only that base station's neighbor list is stored in the mobile's composite neighbor list. However, if a mobile is communicating with a plurality of base stations, for example, three base stations, then the mobile will have to store the entire neighbor list for all three base stations (or up to a storage limit in the mobile) in its composite neighbor list. As discussed above, the elements of the neighbor list that may or may not be stored may be decided arbitrarily, perhaps at the expense of performance.

With reference now toFIGS. 4aand4b,there are shown diagrams illustrating an exemplary CDMA cellular system400wherein a mobile430has established communications links with a first base station “BS0”405and a second base station “BS3”417and the neighbor lists for the first (neighbor list450) and second base (neighbor list455) stations and a composite neighbor list460stored in the mobile430. Each base station's neighbor list may have been generated using the standard technique of detecting a maximum number of base stations and then placing them in the neighbor list.

As an example, let the neighbor list450include base stations “BS1”415, “BS2”416, and “BS4”418and the neighbor list455include base stations “BS2”416, “BS5”419, and “BS6”420. Note that the above neighbor lists (450and455) may contain other base stations. Therefore, the composite neighbor list460, stored in the mobile430would at least contain entries for each of the base stations (with the repeated base station “BS2” eliminated). Note that if the size of the composite neighbor list460exceeds the storage capacity of the mobile405, entries would be eliminated.

Furthermore, if the CDMA cellular system400is a large system, wherein there are more base stations in the system then available coding sequences, then it is necessary that a single coding sequence be used by several base stations. Normally, this is not a problem because through proper design, the base stations that share the same coding sequence will likely be placed far enough apart so that the likelihood of a mobile being able to detect pilot channels from the base stations using the same coding sequence is highly unlikely.

Unfortunately, the practice of placing as many detectable base stations into a neighbor list may result in having base stations which share a single PN coding sequence in the mobile's composite neighbor list. For example, for illustrative purposes, let “BS1”415and “BS5”419use the same PN coding sequence. The mobile430then will have a composite neighbor list460that has two base stations that use a single coding sequence. Then, when the mobile430searches for pilot channels to perform a hand-off, it may be able to detect a control channel using the coding sequence in question. Unfortunately, when it looks in its composite neighbor list460, it will not be able to determine if it has found the control channel of base station “BS1”415or “BS5”419. In this case, the CDMA system400would likely tell the mobile430to select the first entry in its composite neighbor list460(“BS1”415), which in this example, has a 50-50 chance of being the correct base station. The probability of selecting the correct base station continues to further decrease if more than two base stations share the same PN sequence, with the probability being 1/M, where M is the number of base stations sharing the same PN sequence.

Rather than simply placing every detectable base station in a neighbor list, the neighbor list can be populated depending on hand-offs that have actually been used in the cellular telephone system. A cellular telephone system will typically save data related to every call that is made. This data is commonly referred to as saved call (singular) or a list of saved calls (plural). In some cellular telephone systems, the systems can also be configured to collect other system data beyond simple call data, which can be later analyzed. This saved call data can be parsed to generate the neighbor list for each base station. Because the neighbor list will be created using actual call data, it will likely be more accurate than a neighbor list created from simply detectable pilot channels. Additionally, there is high probability that such a neighbor list will also be smaller than a neighbor list created by detecting pilot channels. Since the saved call data will likely also contain information regarding any hand-offs that occurred during the call, the saved call data is also sometimes referred to as saved hand-off data.

With reference now toFIG. 5a,there is shown an exemplary CDMA cellular system500, wherein hand-offs from a single base station “BS0”505to other base stations are displayed graphically, according to a preferred embodiment of the present invention. There are displayed a series of arrows from other base stations to the base station “BS0”505. The arrows indicate that a successful hand-off was performed and the order of the hand-off, for example, one-way, two-way, etc. As discussed above, the CDMA cellular system500will save the call data and the data can be periodically parsed to maintain the neighbor lists. According to a preferred embodiment of the present invention, the saved call data can be parsed once every week or several weeks in order to maintain the neighbor lists. The amount of time between the parsing of the saved call data may depend on several factors, including (but not limited to): the amount of saved call data that is generated (if too much data is accumulated between each parsing, then the parsing may take an extended amount of time), the performance of the hand-offs (if there are too many failed hand-offs, then the parsing may be performed more frequently to help increase hand-off performance), if a base station is added or removed from the system (changes in the available (and unavailable) base stations need to be reflected in the neighbor list), etc.

For example, the saved call data, when parsed, may show that base stations “BS1”515, “BS2”516, and “BS3”517were all involved in one-way hand-offs with the base station “BS0”505. Additionally, base stations “BS4”518and “BS6”520were involved in two-way hand-offs with the base station “BS0”505. Finally, base station “BS5”519was involved in a three-way hand-off with the base station “BS0”505. Using the above example, a neighbor list for the base station “BS0”505can be created.

With reference now toFIG. 5b,there is shown a diagram illustrating a neighbor list570for the base station “BS0”505, wherein the neighbor list570is created from saved call data, according to a preferred embodiment of the present invention. According to a preferred embodiment of the present invention, the parsing of the saved call data is performed in increasing order of the hand-off. For example, one-way hand-offs are parsed first, followed by two-way hand-offs and so on.

Using the data illustrated in the example above, the creation of the neighbor list570is as follows. Start by parsing the one-way hand-offs. The base stations “BS1”515, “BS2”516, and “BS3”517were all involved in one-way hand-offs with the base station “BS0”505. Since the neighbor list570is initially empty, each one of these three base stations “BS1”, “BS2”, and “BS3” are added to the neighbor list570.

Next, the two-way hand-offs are parsed. The base stations “B4”518and “B6”520were involved in two-way hand-offs with the base station “B0”505. Suppose that base station “B4”518was requested while a mobile was connected to base stations “B0”505and “B1”515. As the neighbor list570stands, base station “B4”518is not in the neighbor list570. However, base station “B1”515has base station “B4”518in its neighbor list, so base station “B4”518is not added to the neighbor list570. Suppose now that base station “B6”520was requested while a mobile was connected to base stations “B0”505and “B3”517. Since “B6”520is in the neighbor list of“B3”517, “B6”520is not added to the neighbor list570. Finally, base station “B6”520was again requested, but this time, a mobile was connected to base stations “B0”505and “B2”516. Since “B6”520is not is the neighbor list of“B2”516and the neighbor list570, it is added to the neighbor list570.

Finally, the three-way hand-off is parsed. The base station “B5”519was involved in a three-way hand-off with the base station “B0”505. The base station “B5”519was requested while a mobile was connected to base stations “B0”505, “B3”517, and “B6”520. Since the base station “B5”519is already in the neighbor list of the base station “B6”520, it is not added to the neighbor list570.

Note that in this particular example, there are no four-, five-, or six-way hand-offs. Though if there were, saved data corresponding to the four-, five-, and six-way hand-offs would also be parsed and any new base stations would be added to the neighbor list570. After parsing the saved call data, the neighbor list570of the base station “B0”505is as displayed inFIG. 5b.

With reference now toFIGS. 6aand6b,there are shown diagrams illustrating an exemplary CDMA cellular system600, wherein a mobile625takes part in a three-way hand-off, and neighbor lists for each base station involved, including a composite neighbor list665located in the mobile625, according to a preferred embodiment of the present invention.FIG. 6aillustrates an exemplary three-way hand-off wherein a base station “B5”618is requested by the mobile625, which happens to be already linked to three base stations “B0”605, “B3”617, and “B6”620.FIG. 6bdisplays neighbor lists for each of the three base stations to which the mobile is already linked, neighbor list650(“B0”), neighbor list655(“B3”), and neighbor list660(“B6”). Note that the neighbor lists as displayed may not necessarily be complete. The composite neighbor list665represents the composition of the three individual neighbor lists and is stored in the mobile625.

Note that the composite neighbor list665contains the base station “B5”618, therefore the hand-off would succeed. Additionally, since the base station “B5”618is already in the neighbor lists of the base stations “B3”617and “B6”620, the subsequent parsing of the saved call data would not result in the addition of the base station “B5”618into the neighbor list650of the base station “B0”605. At least not as the direct result of this particular three-way hand-off, since there are other combinations of base stations that may result in the addition of base station “B5”618into the neighbor list650.

With reference now toFIG. 7, there is shown a flow diagram illustrating an algorithm700for use the generating neighbor lists for base stations in a CDMA cellular system by parsing through saved call data, according to a preferred embodiment of the present invention. According to a preferred embodiment of the present invention, the algorithm700executes on a controller for the CDMA cellular system and controlled by a base station manager (BSM). Alternatively, the algorithm700may execute on a remotely connected computer, with the remotely connected computer being connected through a communications link to a controller for the CDMA cellular system, such as an overall CDMA cellular system controller. The BSM may, itself, be a part of an overall CDMA cellular system controller.

According to a preferred embodiment of the present invention, in a typical CDMA cellular system, the neighbor list should be updated once every one or two weeks. This provides a good trade-off in terms of collecting a sufficient amount of call data and not allowing the saved call data to become unmanageably large. Alternatively, the neighbor list can be updated whenever a base station is added or removed from the cellular system. Finally, the neighbor list can be updated whenever the hand-off performance of the cellular system drops below some specified threshold.

When the controller begins execution of the algorithm700, it preferably starts with an empty neighbor list. By starting with an empty neighbor list, any residual history information regarding past hand-offs which may no longer be accurate (especially when a base station has been removed or added to the cellular system), is eliminated.

According to a preferred embodiment of the present invention, the saved call data contains data in the following format: a reference base station (the base station that the mobile originally established communications with), a requested base station (the base station that is requested to join in the hand-off), a list of other base stations (a list of any other base stations that are a part of the hand-off). Note that the list of other base stations can be empty if the particular hand-off is a one-way hand-off. In general, for an N-way hand-off, the list of other base stations will contain N−1 other base stations.

After clearing the existing neighbor lists, the controller begins to parse the saved call data. To do so, it begins by setting a variable, “N” to one. This signifies that one-way hand-offs will be parsed first. In block715, the controller performs the analysis of all one-way call data. Once complete, the controller increments “N” (block720). The controller checks to see if it has analyzed all call data (up to and including six-way hand-offs) (block725). If it has, then the controller terminates the algorithm700and if it has not, the controller returns to block715and performs an analysis of the current N-way call data. Note that if the algorithm700could-start with N equal to zero and then block725would test to see if N was greater than 6. This is solely dependent on where in the algorithm the termination condition (the complete parsing of all N-way hand-offs) is checked and has no bearing on the operation of the algorithm itself.

With reference now toFIG. 8, there is shown a flow diagram illustrating a detailed view of an algorithm800for the analysis of N-way call data, according to a preferred embodiment of the present invention. Algorithm800may be representative of a software routine used to analyze call data, such as in block715fromFIG. 7. The algorithm800would likely execute on the same platform as the algorithm700(FIG. 7), such as the controller or the remotely connected computer.

The controller would begin the analysis of N-way hand-off data by retrieving a single piece of N-way call data (block805). It would check to see if it has analyzed all available N-way call data (block810). If it has, then the algorithm800terminates. If it has not analyzed all of the N-way call data, the controller would check to see if the N-way call data has already been analyzed (block815). This check may be required because the CDMA cellular system may simply save all call data without checking to see if it has already saved a call involving the same combination of base stations. If the CDMA cellular system does not perform the check, it is likely that a hand-off involving the same set of base stations will appear multiple times in the saved data.

If the N-way call data is new, then the controller will check the neighbor lists of all base stations involved in the hand-off to see if the requested base station is in any of the neighbor lists (block820). If the requested base station is not in any of the neighbor lists, then the requested base station is added to the neighbor list of an optimal base station in the hand-off (block825). Note that the optimal base station in the hand-off can be determined in a number of ways, such as, selecting a base station out of the ones that are involved in the hand-off (not necessarily the reference base station) that will result in the smallest composite neighbor list. If the requested base station is in at least one of the neighbor lists, then the requested base station is not added to any neighbor list. The controller returns to block805to process additional call data.