Title of Invention

A METHOD AND APPARATUS FOR PERFORMING NETWORK DISCOVERY

Abstract

At least portions of the map of the base stations, i.e., which base stations are neighbors, is discovered and updated using a wireless terminal controlled handotT process. The portion of the map that is discovered by a particular base station is typically its neighbors to which it can possibJy hand off a call it is serving. It takes at least one handotT with each such base station neighbor for the particular base station to discover its entire local map, i.e., all the base stations to which the particular base station can perform handotTs. The wireless terminal handotT process is used to supply a base station with information about other base stations with whom the base station can cooperate to perform handotTs. The handotT process may subsequently be performed more expeditiously between the particular base station and such other base stations using the obtained information. As part of the handotT process, the wireless terminal tells the new base station to which it is handing off the call the identity of the previous base station from which control is being handed off. The wireless terminal then completes handotT and begins to be served by the new base station. If the new base station does not have a valid record for the previous base station, it forms a trust relationship with the previous base station and creates' a record for it, thus identifying it as a neighbor to which it can perform expedited handotT in response to the control of a wireless terminal.

Full Text

Tecnnical F leiu This invention relates to the art of wireless communication, and more particularly, to a system of handing off communications with a wireless terminal from one base station to another. Background of the Invention Prior art wireless systems have a central controller which determines which base station communicates with a wireless terminal and facilitates transferring, or so-called "handing off, of communication between the wireless terminal from a first base station to a second base station when it is determined that a better communications link can be maintained between the second base station and the wireless terminal than between the first base station and the wireless terminal. Typically, the wireless terminal may assist in the handoff process by providing signal strength measurements to the central controller, while the central controller has ultimate control of the handoff process. For the purposes of handoff, as well as other reasons, prior art wireless systems that support mobile terminals need to know a priori, such as upon initial system installation, or reinstallation, e.g., upon adding to or removing from the system a base station, the "map" of the base stations. This map includes information about at least which base stations are neighbors, and may also include the frequencies and/or timing parameters used by the various base stations and other such configuration information, depending on the nature of the air interface, i.e., the wireless links between the wireless terminals and the base stations, employed in the system. Typically such information is provided at a high cost by system engineering or planning before constructing the network. Summary of the Invention We have recognized that the cost of wireless systems can be reduced significantly, in accordance with the principles of the invention, through the use of a wireless terminal controlled handoff process by which at least portions of the map of the base stations is discovered and updated. The portion of the map that is discovered by a particular base station is typically its neighbors to which it can possibly hand off a call it is serving. It takes at least one handoff with each such base station neighbor for the particular base station to discover its entire local map, i.e., the map information for all the base stations that surround the particular base station and to which the particular base station can perform handoffs. More specifically, it is possible that the old base station from which the handoff will occur is not known by the new base station to which the call is being handed. Alternatively, it is possible that the new base station to which the call is being handed is not known by the old base station from which the handoff will occur. Therefore, in accordance with an aspect of the invention, the wireless terminal handoff process is used to supply a base station with information about other base stations with whom the base station can cooperate to perform handoffs. Advantageously, as information is obtained via the wireless terminals as to the other base stations to which a particular base station may make handoffs, the handoff process may subsequently be performed more expeditiously between the particular base station and such other base stations. Further advantageously, the costs associated with the a priori system engineering are avoided. As part of the handoff process, the wireless terminal tells the new base station to which it is handing off the call the identity of the previous base station from which control is being handed off. The wireless terminal then completes the handoff and begins to be served by the new base station. If the new base station does not have a valid record for the previous base station, it forms a trust relationship with the previous base station and creates a record for it, thus identifying it as a neighbor to which it can perform expedited handoff in response to the control of a wireless terminal. Brief Description of the Drawing In the drawing: FIG. 1 shows an exemplary network arrangement in accordance with the principles of the invention; FIG. 2 shows an exemplary process, in flow chart form, for performing a handoff between the base stations of FIG. 1 in accordance with the principles of the invention; and FIG. 3 shows an exemplary process, in flow chart form, by which one base station gets to know about another base station that it does not currently have a valid entry for, and whose presence it became aware of by virtue of a recent need for a handoff by a wireless terminal. Detailed Description The following merely illustrates the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements which, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope. Furthermore, all examples and conditional language recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure. Thus, for example, it will be appreciated by those skilled in the art that the block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudocode, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown. The functions of the various elements shown in the FIGs., including functional blocks labeled as "processors" may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term "processor" or "controller" should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the FIGS, are conceptual only. Their function may be carried out through the operation of program logic, through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementor as more specifically understood from the context. In the claims hereof any element expressed as a means for performing a specified function is intended to encompass any way of performing that function including, for example, a) a combination of circuit elements which performs that function or b) software in any form, including, therefore, firmware, microcode or the like, combined with appropriate circuitry for executing that software to pertorm the function. The invention as defined by such claims resides in the fact that the functionalities provided by the various recited means are combined and brought together in the manner which the claims call for. Applicant thus regards any means which can provide those functionalities as equivalent as those shown herein. Unless otherwise explicitly specified herein, the drawings are not drawn to scale. FIG. 1 shows an exemplary network arrangement in accordance with the principles of the invention. Shown in FIG. 1 are a) wireless terminal 101; b)N base stations 103, where N is an integer greater than or equal to 2, including base station 103-1 through 103-N;c)N antennas 105, including antennas 105-1 through 105-N;d)N structures 107, including structures 107-1 through 107-N; e)N cells 109, including cells 109-1 through 109-N; f) network 111; g) base station authentication unit I13;h)N communication links 115, including communication links 115-1 through 115-N; i) communication links 117 and 121; j) security center 119. Wireless terminal 101 is able to communicate with multiple base stations which transmit with sufficient signal strength to be detected and useable for communication at the current location of wireless terminal 101. Once a signal of sufficient strength is detected for a particular base station, wireless terminal 101 may engage in communication with that base station. The particular types of wireless link and protocol, i.e., the air interface, employed by wireless terminal 101 are not essential to the invention and may be any type desired by the implementor, although of course the radio link and protocol employed by wireless terminal 101 must be the same type employed by base stations 103. Wireless terminal 101 may achieve communication with multiple base stations in any manner desired by the implementer. For example, wireless terminal 101 may have only a single receiver, and it may receive signals, when not occupied with the exchange of information with the base station currently serving it, from other base stations that have signals of sufficient strength reaching wireless terminal 101. Alternatively, wireless terminal 101 may receive signals from multiple base stations simultaneously, e.g., by employing multiple parallel receivers in wireless terminal 101. Further alternatively, wireless terminal 101 may have more than one receiver, but the number of receivers is less than the number of base stations from which wireless terminal 101 can receive a signal of sufficient strength at its current location, so wireless terminal 101 needs to perform scanning on at least one of its receivers to obtain signals for some of the base stations. Base stations 103 are substantially conventional base stations except for the following. First, base stations 103 need not be connected to a dedicated network for inter-base-station communication. Instead, base stations 103 can employ a shared public network, e.g., an internet protocol (IP)-based network such as the Internet. Second, each base station 103 need not contain any "map" information. Instead, each of base stations 103 is capable of discovering its necessary portions of the "map" information, in accordance with the principles of the invention. Preferably, base stations 103 are small base stations that can easily be incorporated into a small space, e.g., one that is already available, rather than requiring dedicated construction and site preparation. Advantageously, such small size, coupled with the ability to discover the necessary portions of the "map" information, enable the rapid construction of a new wireless communication network. Furthermore, such a wireless commimication network is flexible in its architecture, i.e., base stations can easily be added or removed, and it is also easy to maintain. Each of antennas 105 are coupled to a respective one of base stations 103. Each of antennas 105 radiates the signal developed by its respective one of base stations 103. Each combination of a one of base stations 103 and its respective one of antennas 105 yields a one of cells 109, which is a particular coverage area. The shape of cells 109 in FIG. 1 do not represent actual cell shapes but instead are merely conventional notation for cells. Note that the shape of the actual various cells 109 are all independent. Each of structures 107 provides a facility in which to place one or more of base stations 103. Furthermore, structures 107 may also provide a place on which to mount antennas 105. For example, some of structures 107 may be already existing homes in which a one of base stations 103 is located in an unused space and to which a one of antennas 105 is exteriorly affixed. Network 111 provides a way for base stations 103 to communicate with each other, as well as with base station authentication unit 113 and security center 119. Network 111 may be made up of various subnetworks, which may be networks in their own right. Furthermore, the various subnetworks may be of different types and may employ different protocols. In one embodiment of the invention, network 111 is a packet based network, e.g., an asynchronous transfer mode (ATM) network or an IP network. Each of base stations 103 is connected to network 111 via a respective one of communication links 115, which may be construed as part of network 111. For example, where network 111, or at least a subnetwork thereof, is an IP network, and one of base stations 103 are located within structures 107 that are homes, communications link 115 may be an Internet connection, e.g., over cable television lines or a fiber-to-the curb connection, that is shared by the base station for communicating with other base stations and by the occupants of the home for Internet browsing. Base station authentication unit 113 contains a list of all valid base stations 103, and any associated information such as security keys and alternative identifiers or addresses of the base station. A base station may be listed in base station authentication unit 113 at any point. However, the base station only becomes valid once it is listed in base station authentication unit 113. Although shown herein as a single unit, in practice base station authentication unit 113 may be made up of several parts, which need not be geographically collocated. Furthermore, to improve reliability and performance, some or all of the various parts or functions of base station authentication unit 113 may be replicated, as will be readily recognized by those of ordinary skill in the art. Base station authentication unit 113 is connected to network 111 via communication link 117. Of course, when base station authentication unit 113 is made up of more than one part, or is replicated, communication link 117 is construed as covering all the necessary communications paths between network 111 and the various parts or replicas. Security center 119 contains a list of all valid wireless terminals that may be served. In addition, security center 119 contains security information, such as authentication challenge-response pairs and/or encryption keys associated with each wireless terminal. The security information may be distributed by security center 119 to base stations 103, as necessary. A wireless terminal may be listed in security center 119 at any point. However, the wireless terminal only becomes valid once it is listed in security center 119. Although shown herein as a single unit, in practice security center 119 may be made up of several parts, which need not be geographically collocated. Furthermore, to improve reliability and performance, some or all of the various parts or functions of security center 119 may be replicated, as will be readily recognized by those of ordinary skill in the art. Security center 119 is connected to network 111 via communication link 121. Of course, when security center 119 is made up of more than one part, or is replicated, communication link 121 is construed as covering all the necessary communications paths between network 111 and the various parts or replicas. FIG. 2 shows an exemplary process, in flow chart form, for performing a handoff of wireless terminal 101 between the base stations of FIG. 1, in accordance with the principles of the invention. More specifically, in accordance with an aspect of the invention, as part of the handoff process, a base station may discover and update at least portions of the "map". The portion of the map that is discovered by a particular base station, i.e., the base station"s local map, is typically its neighbors to which it can possibly handoff a call it is serving. It takes at least one handoff with each such base station neighbor for the particular base station to discover its entire local map. The process is entered in step 201 when it is determined that a wireless terminal, e.g., wireless terminal 101 (FIG. 1), requires a handoff, because the signal of the radio link of the base station with which it is communicating, e.g., base station 103-1 of FIG. I, has become sufficiently weaker than that of another particular base station, e.g., base station 103-2 of FIG. 1, so that it appears that the other particular base station could provide a better radio link. Next conditional branch point 203 (FIG. 2) tests to determine if the connection to the first base station, e.g., base station 103-1 of FIG. 1, still exists, since it is possible that the received signal from the first base station became so weak at the wireless terminal, or the signal received at the first base station from the wireless terminal became so weak, that the connection between the first base station and the wireless terminal has become severed prior to a handoff being achieved. If the test result in step 203 is YES, indicating that that the connection continues to exist between the first base station and the wireless terminal, control passes to step 205, in which the wireless terminal requests a handoff from the first base station to the second base station, e.g., base station 103-2 of FIG. 1. Alternatively, the wireless terminal may send various measurements of the signal strengths as received at the wireless terminal for the first and second base stations to the first base station, which determines that it is an appropriate time for a handoff. The first base station therefore tells the wireless terminal to connect to the second base station. Next, conditional branch point 207 tests to determine if the first base station "knows" the second base station, i.e., the first base station has the second base station listed in its "map" information, such a listing having been the result of a previous handoff of a wireless terminal between the first and second base stations. More specifically, as part of the listing in the map information, the first base station may know a) the base station identification of the second base station, b) the network address of the second base station, e.g., its IP address, and c) security information, such as the public key of the second base station, which is used to secure communication between the first and second base stations. If the test result in step 207 is NO, indicating the first base station does not "know" the second base station, control passes to step 209, in which the first base station tells the wireless terminal that it does not know the second base station and that the wireless terminal must arrange for a wireless link connection with the second base station on its own. This may be achieved, for example, by using the same process that a wireless terminal uses to establish an initial wireless link with a base station when it first powers up within the cell served by that base station, as described further hereinbelow. If the test result in step 203 is NO, indicating that the connection from the wireless terminal to the first base station had been terminated, or after step 209, control passes to step 211, in which the wireless terminal requests that the second base station establish with it a wireless link. In response to this request, the second base station attempts to authenticate the wireless terminal, which may require use of information stored in a security center, e.g., security center 119 of FIG. 1, in step 213. Thereafter, conditional branch point 215 tests to determine if the wireless terminal was successftiUy authenticated. If the test result in step 215 is YES, indicating that the wireless terminal is allowed to utilize the base stations for communication, control passes to step 217, in which the wireless terminal is connected for carrying user traffic to the second base station. As part of this step, other portions of the network which were transmitting data to the wireless terminal via the first base station are instructed to now transmit their data to the wireless terminal via the second base station, e.g., using the techniques of the well known Mobile Internet Protocol. Thereafter, the process is exited in step 219. If the test result in step 215 is NO, indicating that the wireless terminal is not allowed to utilize the base stations for communication, control passes to step 219 and the process is exited. If the test result in step 207 is YES, indicating the first base station "knows" the second base station, control passes to step 221, in which the first base station sends the second base station information to expedite the handoff process, in accordance with an aspect of the invention. Such expediting information may include a) an indication that it is OK to take the handoff, i.e., the wireless terminal is permitted to make use of the base stations, b) security information associated with the wireless terminal, such as authentication challenge-response pairs and/or encryption keys, and c) any data not yet sent by the first base station to the wireless terminal. Thereafter, control passes to step 217 and the process continues as described above. FIG. 3 shows an exemplary process, in flow chart form, by which one base station gets to know about another base station that it does not currently have a valid entry for, and whose presence it became aware of by virtue of a recent need for a handoff by a wireless terminal. The process is entered in step 301 after there is a request for a nonexpedited handoff by a wireless terminal, e.g., at any point after execution of step 211 of FIG. 2. In such a case the second base station wants to know about the first base station. In step 303, the second base station, e.g. base station 103-2 of FIG. 1, contacts a base station authentication unit, e.g., base station authentication unit 113 of FIG. 1, requesting the establishment of a trust relationship with the first base station. Next, in step 305, the base station authentication unit looks up the first and second base stations in its list, and attempts to determine if they are who they say they are, e.g., using a challenge response process. Conditional branch point 307 tests to determine if both the first and second base stations are valid. If the test result in step 307 is YES, indicating that both the first and second base stations are valid, control passes to step 309, in which the base station authentication unit sends a validation message for the first base station to the second base station and for the second base station to the first base station. This message may also include additional information such as network addresses" and security information. Alternatively, the first and second base stations may exchange such additional information among themselves. In step 311, in response to receipt of the message regarding the second base station, the first base station updates its data base with an entry for the second base station, in accordance with an aspect of the invention. As a result, the first base station will now "know" the second base station and will be able to perform expedited handoffs with it. Similarly, in step 313, in response to receipt of the message regarding the first base station, the second base station updates its data base with an entry for the first base station, in accordance with the principles of the invention. As a result, the second base station will now "know" the first base station and will be able to perform expedited handoffs with it. Thereafter the process is exited in step 315. If the test result in step 307 is NO, indicating that at least one of the first and second base stations is not valid, control passes to step 317, in which the request for the establishment of a trust relationship with the first base station is denied, in accordance with an aspect of the invention. This may be achieved by an explicit denial message or implicitly by a failure to receive a validation message within a defined time period. Thereafter the process is exited in step 315. In an alternative embodiment of the invention, the process of FIG. 3 may be entered after step 207 (FIG. 2) when the test result in step 207 is NO. In such an alternative embodiment, however, the roles of first base station and second base station are interchanged. Note that in an alternative embodiment of the invention, the request for a handoff may not come from, or be controlled by, the wireless terminal. Instead, the request for a handoff, or the decision to perform the handoff, may be originated by a base station, typically using information obtained from the wireless terminal. WE CLAIM : 1. A method for performing network discovery in a network having at least first and second base stations and a least one wireless terminal, the method comprising the steps of: receiving a request for a handoff of said wireless terminal between said first base station and said second base station; determining if said second base station knows said first base station prior to receiving said request; and when said second base station did not know said first base station prior to receiving said request, recording in said second base station that said second base station can engage in handoffs with said first base station. 2. The method as claimed in claim 1 wherein said request for said handoff is received from said wireless terminal. 3. The method as claimed in claim 1 wherein said request for a handoff is transmitted from said first base station which is providing wireless service to said wireless terminal and is received by said second base station. 4. The method as claimed in claim 1 wherein said request for a handoff is transmitted from first base station and is received by said second base station which is providing wireless service to said wireless terminal. 5. The method as claimed in claim 1 wherein the recording in the second base station is performned only when said first base station successfully authenticates said second base station. 6. The method as claimed in claim 1 wherein said request is received in a wireless format directly from said wireless terminal. 7. The method as claimed in claim 1 wherein said request identifies said first base station to said second base station. 8. The method as claimed in claim 1 wherein : when said second base station was not aware of said first base station prior to receiving said request, recording in said second base station that it can engage in handoffs with said first base station. 9. The method as claimed in claim Iwherein : when said second base station was not aware of said first base station prior to receiving said request performing an nonexpedited handoff between said first and second base station. 10. The method as claimed in claim 1wherein : when said second base station was not aware of said first base station prior to receiving said request, establishing a new connection between said wireless terminal and said second base station. 11. An apparatus for performing network discovery in a network providing wireless communication service, comprising; at least a first base station having a first data base indicating base stations with which said first base station can perform expedited handoffs; a second base station; a communication network connecting said first and second base stations; at least one wireless terminal, said wireless terminal being able to communicate with said first and second base stations substantially simultaneously; said first base station entering said second base station into its first data base in response to a request from said wireless terminal for a handoff between said first base station and said second base station.

Documents:

0103-mas-2001 abstract-duplicate.pdf

0103-mas-2001 abstract.jpg

0103-mas-2001 abstract.pdf

0103-mas-2001 claims-duplicate.pdf

0103-mas-2001 claims.pdf

0103-mas-2001 correspondence-others.pdf

0103-mas-2001 correspondence-po.pdf

0103-mas-2001 description (complete)-duplicate.pdf

0103-mas-2001 description (complete).pdf

0103-mas-2001 drawings-duplicate.pdf

0103-mas-2001 form-1.pdf

0103-mas-2001 form-13.pdf

0103-mas-2001 form-19.pdf

0103-mas-2001 form-26.pdf

0103-mas-2001 form-3.pdf

0103-mas-2001 form-4.pdf

0103-mas-2001 form-5.pdf

0103-mas-2001 others.pdf

0103-mas-2001 petition.pdf