Title of Invention

METHOD FOR LOCATION DETERMINATION OF A LOCAL TRANSMITTER USING A DATABASE

Abstract

A method and apparatus for identifying wireless communication base stations from incomplete signal data reported by a Mobile Station (MS). In one embodiment, a database includes a plurality of key BIS data entries, each key BTS data entry including a unique global identifier that uniquely identifies a BTS in the system, and wherein the BTS database further includes associated data entries corresponding to and associated with each key BTS data entry. BTS signal data is obtained from an MS, the BTS signal data including a unique identifier of a first BTS and at least partial identifying information for at least one BTS other than the first BTS. A match is determined between the first associated data entries and the BTS signal data, and a second BTS is identified responsive to the match. Figure 3.

Full Text

CROSS-REFERENCE TO RELATED APPLICATIONS This application claims priority to U.S. Provisional Application No. 60/490,820, filed July 28, 2003 and entitled "OPTIMIZATION OF BASE STATION ALMANAC LOOK-UP FOR IDENTMCATION OF MOBILE STATION REPORTED CELLS," the contents of which are hereby incorporated in their entirety by reference. BACKGROUND Field 001 The disclosed method and apparatus relates to location services for mobile communication devices, and more particularly to a system and method for determining the location of transmitters transmitting signals used to locate a mobile station. Description of Related Art 2 Location services (abbreviated as LCS, for "LoCation Services") for wireless communication devices, referred to as Mobile Stations (MSs), are an increasingly important business area for wireless communication providers. Location information can be used to provide a variety of location services to MS users. For example, public safety authorities can use location information to pinpoint the precise geographical location of an MS. Alternatively, an MS user can use location information to locate the nearest automatic teller machine (ATM), as well as the fee charged by that ATM. As another example, location information can assist a traveler in obtaining step-by-step directions to a desired destination while in route. 3 Technologies that permit a large number of system users to share a wireless commxmication system play an important role in meeting the ever-increasing demands of mobile computing, including the demands for location services. Such systems include Code Division Multiple Access (CDMA) and Wideband CDMA (WCDMA) technology, for example. As is well known, CDMA and WCDMA communication devices are assigned a pseudo noise (PN) code or sequence. Each device uses its PN code to spread its communication signals across a common spread-spectrum frequency band. As long as each communication device uses the correct code, each such device can successfully detect and select a desired signal from among the signals concurrently transmitted within the same frequency band. 4 Two types of positioning systems are commonly known. The first is referred to as an MS-based positioning system. In MS-based positioning systems the computations for determining the MS location are performed within the MS. The second is referred to as an MS-assisted positioning system. In MS-assisted positioning systems, the network provides assistance data to the MS to enable location measurements and/or to improve measurement performance by the MS. The MS provides the signal measurements to the network A conqxment of the network then computes an estimate of the location of the MS. One particular rttettiod of MS-assisted positioning employs the Global Positioning System (GPS) and is referred to as "assisted GPS" or AGPS. In accordance with the AGPS method, the MS acquires measurements from GPS satellites (commonly referred to as "GPS measurements") using assistance data provided by the network. In addition to GPS measurements, the MS acquires terrestrial measurements, such as forward link measurements from a ground reference station, such as a Base Transceiver Station (BTS). 'Torward link" refers to communications transmitted from the BTS and received by the MS. "Reverse link" refers to the communications transmitted from the MS and received by the BTS. Terrestrial measurements can also be acquired on the reverse link, measured at the BTS. Other measurements include altitude assistance and timing information. La MS-assisted operation, regardless of the origin of such measurement information, all of the measurements made for the purpose of servicing a given location request are typically sent to a position determination entity (PDE) for geolocation calculations. 5 One method that may be used in conjunction with GPS or AGPS systems is commonly referred to as Advanced Forward Link Trilateration (AFLT). This is a geolocation technique that utilizes the measured time of arrival (TOA) of radio signals transmitted from a pluraUty of BTSs and received by an MS. Other melhods that utilize TOA include Enhanced Observed Time Difference (E-OTD) and Observed Time Difference of Arrival (OTDOA). 6 hi order to inqjlement TOA-based geolocation techniques, the MS "reports" the receipt of signals transmitted fix)m BTSs. The MS may provide a PDE with PN measurement data for each BTS signal that it receives. The PN measurement data is derived from a phase-coherent sequence of data. The data is commonly referred to as "chips". The sequence of chips is commonly referred to as a pilot chip sequence. The signal that carries the pilot chip sequence is commonly referred to as a pilot signal. Methods for acquiring the pilot signals by the MS are well known to persons skflled in the arts of wireless communications. 7 Within a given geographical region each BTS periodically broadcasts the same pseudo-noise (PN) code pilot signal, but with a different time offset. That is, each BTS transmits the same PN code. However, the start of transmission of the PN code from each BTS is delayed in time by a different precisely known offset with respect a common timing reference. Becatise different BTSs transmit PN codes with different offsets, the PN offset of a pilot signal may be used to identify the corresponding BTS. Consequently, a PDE may identify the BTSs that have transmitted signals received by an MS by referring to a database relating BTS identities to PN offset. It should be noted for the purposes of brevity, reference is made to tiie 'TN offset of the signal" being transmitted rather than to the PN offset of the start of the PN code modulated on the signal. 8 Alternatively, other variations in the PN code may be used to distinguish signals transmitted by different BTSs. PN offset can typically be measured on the incoming signals received from a BTS. One database known to persons skilled in the art is a Base Station Almanac (BSA), which contains information about the terrestrial wireless network. In particular, the BSA may relate the location of a BTS to the PN offset of signals transmitted by that BTS. 9 Unfortunately, due to the linmted number of PN offsets available, some BTSs are assigned to transmit signals with the same PN offset. However, BTSs transmitting signals with the same PN offsets are typically sufficiently far away from each other that no one MS can receive signals from two BTSs assigned the same PN offset. Nonetheless, the PN offset alone may be insufficient to uniquely identify a BTS because an MS may receive signals from a distant BTS having the same PN offset as a more proximate BTS. 10 Li addition to problems in uniquely identifying the BTS from which signals were transmitted, the relatively large mmiber of BTSs in a typical system results in a significant amoimt of time being spent searching through a database in order to identify the particular transmitting BTS. Oil An accurate determination of the location of the MS requires accurate information regarding the location of each BTS from which the MS receives signals. This, in turn, requires rapid and unique identification of each BTS from which a signal is received. Therefore, it can be appreciated that there is a significant need for improved methods by which transmitters may be identified using the limited data received by an MS. Accordingly, there is a need for a method and apparatus for determining the location of BTSs tiiat can be "heard" by an MS. SUMMARY 12 A system and method is disclosed for determining the location of transmitters of signals, such as Base Transceiver Stations (BTSs) rq)orted by a Mobile Station (MS). In one embodiment of the disclosed me&od and apparatus, a database includes a plurahty of key BTS data entries. The term 'Tcey" is used to indicate that the key BTS data entry is used as a "search key" to assist in identifying the particular record of interest witiiin flie database. Each key BTS data entry corresponds to a unique BTS in fhe system. The BTS database further includes associated data entries corresponding to and associated witii each key BTS data entry. One such associated data entry is the Neighbor List for storing "Neighbor" BTS data, including pseudo-random noise (PN) offsets of signals transmitted by BTSs that are geographically proximate to the BTS corresponding to fee key BTS entry. 13 Anottier associated data entry is the Hearable List for storing "Bearable" BTS data, including the PN offset of signals transmitted by BTSs and received by an MS, and not transmitted by BTSs in the Neighbor List. Yet another associated data entry is referred to as the Remaining List for storing the "Remaining" BTS data, including PN offsets of signals transmitted by BTSs that do not belong to the Neighbor List or Hearable Li. 14 In accordance with one embodiment of the disclosed method and apparatus, BTS data is received from an MS. The BTS data includes a imique identifier associated with a "primary serving" BTS. In one embodiment of the disclosed method and apparatus, the unique identifier could be the SID/NID/BaselD or in another embodiment flie identifier could be the Switch Number, Market ID and/or Base ID. The BTS data also includes Pseudo-random noise (PN) data associated with both the primary serving BTS and other BTSs. These other BTSs are hereafter referred to as "non-SCTving" BTSs. However, it will be understood that some of ttiese non-serving BTSs may in fact be secondary serving BTSs. That is, they may be providiog a communication link between the MS and a conranmication network In addition, the BTS data includes an indication of the signal strength of signals transmitted by other BTSs and received by the MS. A match is sought between the received unique identifier and the key BTS data entries wittiin flie database. Once the match is made, the location of the primary serving BTS identified by the key BTS data entry is known from the primary serving BTS data associated with that key BTS data entry. 15 Next, data associated with the signals that are reported by the MS as having been received by the MS from non-serving BTSs are examined. The examination is made to determine whether tiie signal strength reported by the MS for each non-serving BTS signal is greater than the threshold associated with the primary serving BTS in tiie database. If so, then the method checks whether ttie PN offset of signals transmitted by the non-serving BTSs match fee PN offset stored in the Neighbor List. The PN offset of the signals transmitted by the non-serving BTSs is considered to be ambiguous identification data, since the PN offsets may be associated with more than one particular BTS. However, other identification data may be considered to be ambiguous as well. For example, a "System IDentification" number (SID) can be assigned to more than one BTS, making the SID ambiguous as to the identify of the BTS associated with that SID. Accordingly, any information that identifies two or more sources is considered to be ambiguous identification data for the purposes of this disclosure. 16 In accordance with one embodiment of the disclosed method and apparatus, it can be assumed that the PN offset of a signal having signal strength that is above the threshold will match a PN offset associated with a Neighbor BTS listed in the Neighbor List. In another embodiment, if: (1) the signal strength is above the threshold; (2) the PN offset is not found in the Neighbor List, and (3) the PN offset is foimd in one of the other lists, then the entry associated with the PN offset is moved from flie hst in which the PN offset is found to the Neighbor List. In this way, the Neighbor List can be dynanaically constructed rather than having to be downloaded from ttie BTS, or other BTS network database equipment. 17 However, if the signal strength is not greater than the threshold, then we cannot assume that the PN offset will be on the Neighbor List Accordingly, even if the PN offset associated with a non-serving BTS matches the PN offset of a BTS listed in the Neighbor List associated with the primary serving BTS, confirmation of that PN offset is required. That is, an additional step is performed to confirm that the PN offset indicates that the BTS associated with that PN offset in the database is the same as the BTS associated with the PN offset sent by the MS. In one embodiment, this confirmation is made by determining the likelihood that the BTS associated with the PN offset in the database transmitted the signal having the associated PN offset. In an alternative embodiment of the disclosed method and apparatus, the confirming step may be omitted. However, there would then be a chance that the match could be wrong. Any wrong matches would result in the location of at least some of the BTSs from which the MS is receiving signals to be incorrectly determined. 18 If the PN ofeet sent by the MS does not match any of fte PN offsets stored in the Neighbor List, then a match is sou^t from among the PN offsets stored in tiie Hearable List entry, hi one embodiment of the disclosed method and apparatus, if such a match is found, then the match is confirmed. However, in anofeer embodiment, the match can be assumed to be correct at some risk of that assuiiq)tion being wrong. 19 If the PN offset sent by the MS does not match any of ttie PN of&et stored in the Hearable List entry, then a match is sought from among the PN offset stored in the Remaining List If a match is fovmd, then in accordance with one embodiment of the disclosed method and apparatus, the match is confirmed via a further step. Alternatively, the match might be assumed to be correct without further confirmation. In response to determining that there is a match, all of the data associated with the PN offset is transferred from the Remaining List to the Hearable List. BRIEF DESCRIPTION OF THE DRAWINGS 20 FIGURE 1 is a functional block diagram of a wireless commimication system to provide wireless commimications including location services. 21 FIGURE 2 is a fimctional block diagram of a wireless communication system to provide wireless commimications including location services, showing additional components. 22 FIGURE 3 is a conceptual illustration of a database, shown in the form of a table. 23 FIGURE 4 is a flow chart illustrating a method of identifying base transceiver stations according to signal data reported by a Mobile Station (MS). 24 FIGURES 5 and 6 comprise a unitary flow chart illustrating a second method of identifying base transceiver stations according to signal data reported by a MS. 25 FIGURE 7 illustrates a system that performs a statistical analysis based on the amoimt of overlap in coverage areas between a primary serving Base Transceiver Station (BTS) and a BTS represented by a particular set of entries to a database. 26 FIGURE 8 illustrates the coverage area of a primary serving BTS. 027 FIGURE 9 shows the calculation of the relative phase of signals received from different BTSs. DETAILED DESCRIPTION 028 FIGURE 1 illustrates a sin^lified general wireless communication system 100 that may be adapted to provide location services. As shown in FIGURE 1, a Mobile Station (MS) 102 communicates with Base Transceiver Stations (BTSs) 112, 114, 116 and 142 via a plurality of wireless links 122. While four such BTSs are shown, it should be imderstood that the MS 102 may communicate with one or more such BTSs without limits on the number of such BTSs. The MS 102 may be a cell phone, a wireless telephone, a personal digital assistant (PDA) with wireless communication capabilities, a laptop conputer having wireless communication capabilities, or any other mobile device for personal communication via wireless coimection. The MS 102 receives pilot signals transmitted by the BTSs 112, 114, 116, 142. In accordance with one embodiment of the disclosed method and apparatus, the pilot signals, referred to herein as "pilots," are modulated with a "pseudo-random noise" (PN) code, hi another embodiment of the disclosed method and apparatus, the pilots may be any signal that permits the identification of BTSs based on some characteristic of the signal. In one embodiment in which the pilot is modulated with a PN code, the PN code is a string of digital values. Modulation of pilots with such PN codes is commonly used to allow Code Division Multiple Access (CDMA) communication systems to discriminate between different signals sent on the same frequency. In addition, it is common in CDMA cellular telephone systems to modulate the pilot signals transmitted by many, or all, of BTSs in the system with the same PN code. To distinguish the pilot transmitted by one BTS from the pilots transmitted by other BTSs, the PN code from each BTS has a time offset that is unique to the particular transmitting BTS. The offsets are each referenced to a common clock. Therefore, by determining the particular timing offset with respect to the common clock, the MS can determine which BTS transmitted that pilot. 029 However, in most such systems, the same offset is assigned to more than one BTS in accordance with an assignment plan. In accordance with the assignment plan, BTSs that have the same offset assigned should be far enough away from each other that the signals transmitted by them cannot be received by the same MS, for ordinary communications purposes. Therefore, in theory there should not be any ambiguity when atten^ting to use the offset to determine which particular BTS has transmitted a pilot that an MS received at signal levels sfrong enough for communication. However, in practice, there remains a potential for 8 ambiguity. This is especially true in cases where an MS can detect signals weaker than those used for ordinary communications purposes, and thus may detect signals that are coming from farther away than tiie conmiunications assignment plan anticipated. In any case, such potential ambiguities need to be accounted for when attempting to identify the location of the source of a pilot for the purpose of using that pilot to locate an MS. 30 The BTSs 112, 114 and 116 are coupled to a Base Station Controller/Mobile Switching Center (BSC/MSC) 110. The BSC/MSC is coupled to a Position Determination Entity (PDE) 130. The PDE 130 may be incorporated into other con^nents of a communication system (such as a BSCVMSC, a Communication Service Provider Network 150, or some combination thereof). The PDE 130 may provide location services to multiple devices (such as a plurahty of MSs similar to the MS 102) communicating through multiple BSC/MSCs, and BTSs, such as the BSC/MSC 140 and the BTSs 112, 114, 116, and 142. In one alternative embodiment, the location of the MS 102 may be determined solely by processing tiiat occurs within the MS itself hi one embodiment of the disclosed method and apparatus, information required to locate all BTSs may be stored in a centralized PDE, rather than in the MS 102. However, such data nragjit be stored anywhere that would permit it to be accessed, including in the MS 102. 31 In the present example, the BTS 142 is connected to a separate BSC/MSC 140 to jll i i.« *1 4. - ^^^^1 1 -„11..1 4.-1 1 t —rn • 1—J- x-i -rfcoy-nm j-n/-i T»I-. iiiusuaib uiai a lyyix^ai ^ciiuiox icicpxiuuc ajraiciu will uikiuuc luuic Uliui UliC DO\jllviCiy^. J.11C BSC/MSC 110, 140 provide an interface between the BTS and other network elements, such as the PDE 130 and a communications service provider network 150, such as a Public Switched Telephone Network (PSTN). 032 In addition to the signals received from BTSs, the MS 102 may also receive signals (such as GPS signals) from one or more other sources (such as satellites) 126 and 128 via communication links 123 and 124. Similarly, the BSC/MSC 110 may also receive signals, such as GPS signals, from one or more satellites 126 and 128 via communication links 123 and 124. Although two satellites are illustrated by way of example, no satellites, one satellite, or a plurahty of satellites and/or other sources, may be employed when providing location services to an MS. Further, although the satellites are shown communicating with the BSC/MSC 110, persons skilled in the arts of wireless communications will understand that satellite data may also be received by other receivers (not shown) such as a Wide Area Reference Network (WARN). The BSC/MSCs 110 and 140 are connected to the communication service provider network 150 to receive and transmit data such as audio/video/text communication and programming data, position requests or data from the WASN. 33 FIGURE 2 provides additional details regarding the components within the MS 102 and the PDE 130. For simplicity, the GPS satellites that may be used in a positioning system, and their associated communication links, are not shown in FIGURE 2. The PDE 130 has a memory 234, and a processor 232 ftat controls opaation of the PDE 130. The term "processor", as used throughout this description, is intended to encompass any processing device, alone or in combination with other devices (such as a memory), capable of controlling operation of a device in which it is included (such as a PDE 130, an MS 102, a BSC/MSC 110, or a portion thereof). For example, a processor, such as ih 34 The memories 234 and 206 may include read-only memory (ROM) components, random-access memories (RAM), non-volatile RAM components or any other means by which information can be stored and later accessed. The memory 234 stores and provides instructions and data for the processor 232. The components of the PDE 130 are linked together by an internal bus system 236, and the components of the MS 102 are linked together by an internal bus system 207. As described in more detail below, the memory 234 includes a database used to locate the source of signals (i.e., BTSs) according to a PN offset provided by the MS 102. 35 As shown in FIGURE 2, the MS 102 includes a processor 204, a memory 206, and a transceiver 208. The memory 206 stores and provides instructions and data for the processor 204. The transceiver 208 allows the transmission and/or reception of data, such as audio, video, text, and programming data, between the MS 102 and a remote location, such as the BTSs 112, 114, 116 and 142, or GPS satellites (not shown). An antenna 209 is coupled to the transceiver 208. The basic operation of the MS 102 is well known in the art and need not be described herein. 36 PDE 130 may have a database stored that maps PN offset to the location of an associated BTS. As noted above, CDMA systems commonly use pilot PN offsets as a means of identifying BTSs. PN offsets are commonly known as "transmit PN sequence offsets". In another embodiment, signals transmitted by different BTSs may be distinguished based on the PN code values or any other attribute of the modulation of the signals rather than PN offset. lo However, for the sake of sinplicity in describing the disclosed method and apparatus, reference is made to the PN offset. However, it will be understood by those skilled in the art that any other attribute of the signal, including the particular PN code, or some other distinction in the manner in which the signals transmitted by BTSs may be used in place of the PN offset. 37 hi one embodiment, the database may be stored in the memory 234. However, in another embodiment, the database may be stored in the memory 206 wittiin the MS 102. For this embodiment, the MS 102 may require information relating the location of the BTS from which a pilot having a particular PN offset is located. This information may come from a BSC/MSC, a PDE, or other location. 38 FIGURE 3 is a conceptual illustration of a database, shown in the form of a table 300. The table 300 contains a number of records 301, 303, 305. Each record 301, 303, 305 includes a key BTS entry 302 for storing key BTS data entries. The data stored in each key BTS data entry 302 relates to a particular "primary serving" BTS. The primary serving BTS is that BTS with which the MS 102 is registered. "Registration" refers to the network recording that the MS 102 is commxmicating with the network through a particular BTS. In the case in which the MS 102 is registered with more than one BTS, the primary serving BTS might be the BTS from which the MS 102 is receiving the strongest signal, or alternatively, the primary serving BTS might be arbitrarily designated from among all of the BTSs with which the MS t n*^ • _ r _i - - .1 IVZ, 1& ICglMCICU. 39 In one embodiment, each key BTS data entry 302 includes at least two sub-fields. The firet sub-field 307 is referred to herein as the PN data sub-field. The PN data sub-field 307 includes PN data, such as PN offset, used to determine with which BTS 112,114, 116, 142 the MS 102 is registered. The phrase 'TN data" can be used to generally refer to information such as: 1) the offset of the start of a PN code modulated onto a carrier signal transmitted by a BTS, 2) the particular PN code modulated onto a carrier signal transmitted by a BTS, or 3) any other information modulated onto a carrier signal transmitted by a BTS from which signals transmitted by different BTSs can be distinguished from one another, whether that information relates to a pseudo-random noise code or not. However, for the sake of clarity and simplicity, tiie presently disclosed method and apparatus is described using the PN offset as the particular type of PN data. 40 Accordingly, in one embodiment of the disclosed method and apparatus, the data stored in the key BTS data entry 302 includes the PN offset of the start of the PN code modulated onto the signals transmitted by the primary serving BTS. For the sake of simplicity // and brevity, we refer simply to the "TN offset of the signals" rather than the longer phrase "PN offset of the start of the PN code modulated on the signals". However, those skilled in the art will understand the former phrase to mean the same as the later phrase. In addition, the key BTS data entry 302 includes the location of the primary serving BTS. "While the information in the key BTS data entry 302 is typically related to the primary serving BTS, the key BTS data entry 302 may include the PN offset of signals transmitted by a BTS other than the primary serving BTS. For example, the PN offset may be associated with a secondary serving BTS. 41 The second sub-field 309 is referred to as the Serving BTS Location sub-field. In the exsarple shown in FIGURE 3, the Serving BTS Location sub-field 309 provides the location of the primary serving BTS. The location may be provided in any particular format and/or form that would make the location information useful for at least the purpose of identifying from where a signal transmitted by the BTS originated. The location is provided in order to use such signals to assist in determining the location of a receiving MS 102. For the purpose of the disclosed method and apparatus, the location of the MS 102 might be detennined using any of the following methods: 1) time of arrival method, 2) time difference of arrival method, 3) angle of arrival method, 4) triangulation method, 5) trilateration method or 6) any other method that might benefit from knowledge of the location of a source of a transmitted signal. 42 In addition, in some embodiments, information that identifies the primary serving BTS might also be included in one or more additional sub-fields (not shown) in the key BTS data entry 302. In one embodiment, the key BTS data entries may also include other data relevant to the BTS. 43 Associated with each key BTS data entry 302 (i.e., contained within the same record 301, 303, or 305 as the key BTS data entry) are associated data entries. Li accordance with one embodiment of the disclosed method and apparatus, for each key BTS data entry 302, there is an associated Neighbor List 311. The Neighbor List 311 includes two sub-fields. The first sub-field is the Neighbor PN data sub-field 313. The second sub-field is the Neighbor location sub-field 315. In one embodiment of the disclosed method and apparatus, there is a one-to-one correspondence between the entries in the Neighbor PN data subfield 313 and the entries in the location sub-field 315. The Neighbor PN data sub-field 313 includes the PN offset of the signals transmitted by a Neighboring BTS. The corresponding Neighbor location sub-field 315 includes the location of that neighboring BTS. For exaii5)le, FIGUEE 3 shows a database that has n Neighbor BTSs. Each Neighbor BTS has a corresponding Neighbor PN data entry 317 and a corresponding Neighbor location entry 319 in the database 300. Ellipses are shown in 12 FIGURE 3 between the first Neighbor PN data sub-field 317 and the nth PN data sub-field 318 to indicate that there are « minus 2 additional PN data entries not expressly shown. Similarly, ellipses are shown between Neighbor location data entry 319 and Neighbor location data entry 320. A first Neighbor Location sub-field entry 319 corresponds to, and locates, the BTS that transmitted the signal with the PN offset residing in the first Neighbor PN data sub-field entry 317. An nih Neighbor Location sub-field entry 320 corresponds to, and locates, the BTS that transmitted the signal with the PN offset residing in the nth Neighbor PN data sub-field entry 318. 44 The associated data entries also include a "Hearable List" 322 associated with a particular primary serving BTS identified in the key BTS data entry 302 within the same record 301, 303, 305. The Hearable List 322 shown in FIGURE 3 includes two sub-fields with tn entries in each sub-field. The first sub-field is flie Hearable PN data sub-field 321. The Hearable PN data sub-field 321 includes a first Hearable PN data sub-field entry 325 separated by ellipses from an fth Hearable PN data sub-field entry 327. The ellipses indicate the existence of m entries wittiin the sub-field 321. 45 The second sub-field is the Hearable Location sub-field 323, including a first entry 329 to the Hearable Location sub-field 323 separated by ellipses from an mfh Hearable PN data sub-field entry 331 to indicate the existence of m entries wittiin the Hearable Location sub-field ^.i.j. i.ijc uaiii ui uic nciuituic x^isi DZ,Z. anuwa DIOS lu uc luuaieu max: i.) nave u'ansminea signals received by an MS 102 that is currently being served by the BTS corresponding to the key BTS data entry 302 within the same record 301, 303, 305; and 2) are not in the Neighbor List 311. 46 The associated data entries also include a "Remaining BTS List" 333. The Remaining BTS List 333 identifies a set of BTSs tiiat are not identified in either the Neighbor List 311 or the Hearable BTS List 322. In addition, in accordance with one embodiment of the disclosed method and apparatus, in order to be Usted in the Remaining BTS List 333, a BTS should be detectable by an MS 102 being served by the primary serving BTS responsible for transmitting the signal having the PN offset indicated in the key BTS data entry 302. In one particular embodiment, any BTS in the system is considered to be potentially detectable. In yet another embodiment, all BTSs in the system are included in the Remaining List excluding those listed on the Neighbor or Hearable Lists. 47 The Remaining BTS List 333 includes two sub-fields. The first is a Remaining BTS PN sub-field 335. The second is the Remaining BTS Location sub-field 337. The Remaining /s BTS PN sub-field 335 mcludes several Remaining BTS PN sub-field entries as depicted in FIGURE 3 by the ellipses between a first Remaining BTS PN sub-field entry 339 and an /th Remaining BTS PN sub-field entry 341. Similarly, the Remaining BTS Location sub-field includes several Remaining BTS Location sub-field entries as depicted in FIGURE 3 by the ellipses between a first Remaining BTS Location sub-field entry 343 and an /th Remaining BTS Location sub-field 345. Each of tiie entries in flie Remaining BTS Location sub-field 337 provides the location of the BTS transmitting the PN code indicated in the corresponding entry in the Remaining BTS PN sub-field 335. 48 While the embodiment depicted in FIGURE 3 shows storing only the PN offset and BTS location in each of the Lists, the Neighbor List 311, Hearable BTS List 322 and Remaining BTS List 333 may each include any combination of the PN offset, PN code, and/or data pertaining to other attributes, such as, for example, a unique global identifier, geographical coordinates, altitude information, anteima range, etc., that may be used for position determination purposes. Accordingly, table 300 may optionally contain additional fields, and may refer to other databases or tables, or it may not contain all of the fields described herein. For example, in one embodiment, one or more separate databases containing a Remaining List may exist, hi this embodiment, the table 300 might contain a field that refers to the desired Remaining List in the external database, la. fliis embodiment, the PDE 130 (FIGURE 2), or a processor located in another device, looks up the corresponding Remaining BTS data in another database or table, rather than storing it in the field 333. Other servers, such as tiiose in the BSC/MSC 110 or 140, may maintain separate databases and information retrieved by the PDE 130, as needed. In yet another embodiment, the database represented by Table 300 might be incorporated in the MS 102. In this embodiment, in accordance with the methods described in more detail below, the MS 102 may identify the BTSs based upon the PN offset and report the BTS location to the PDE 130, rather than merely reporting the PN offset. 49 FIGURE 4 is a flowchart illustrating a method of identifying BTSs according to PN offset reported by an MS. The method may be en:q)loyed, for example, by the system 100 shown in FIGURE 2. It should be noted that while the present example illustrates the disclosed method and apparatus using PN offset, other forms of ambiguous transmitter identifying information might be used. 50 The method is initiated at STEP 402, wherein a BTS database, such as the database 300, is created. At STEP 404, data is obtained fi-om an MS. Typically, the MS will provide the information when requesting that its position be determined. In accordance with one 14 embodiment of the disclosed method and apparatus, the data includes a unique Global Identifier which identifies the serving BTS. The Global Identifier is included in the information modulated on signals transmitted to the MS by the serving BTS. Accordingly, the MS will receive and demodulate the Global Identifier modulated onto the signals transmitted by the serving basestation. Furthermore, the MS sends a set of PN offsets designated by PN,- (i = 1, n), where i is an index indicating a particular one of n instances of PN offset. Each instance of PN offset is associated with one BTS from which the MS receives signals. The value n is the numbCT of BTSs from which the MS receives signals. The data is provided to a processor. The processor may be incorporated in a PDE or an MS, such as eitiier the processor 204 or the processor 232 of FIGURE 2. The processor is coupled to the database to receive and store data. 51 The method then proceeds to STEP 406. At STEP 406 flie processor finds the key BTS data entry 302 in the database 300 having the unique ID that matches the imique ID obtained from the MS. The method then proceeds to STEP 408. At STEP 408, a counter is initialized by setting the index f = 1. The mefliod then proceeds to STEP 410. 52 At STEP 410, the strength of the signal received by the MS with a PN offset of PN,-is compared to a desired threshold level (THRESH). In accordance with one embodiment of flie disclosed method and apparatus, the value used for THRESH may be the minimum signal T^.,.«1 ...^.«..L^4 ^» «11.^.,. »« ........«^4^ «^ 1 1- x1-.^ 4.1— J IJ-L: /; - T^rrin\ *^ ik'Ywi tv^uubu at auyw oil aaauuipuuu lu u>^ iiiauc uiai uic uaiiMiiiuui^ &ULUi;c ^i.C, DIO) IS close enough to the serving BTS to be considered to be a communications neighbor of the serving BTS. One particular parameter that might be useful is TT_ADD. TT_ADD is a typical value for the signal strength threshold T__ADD. TT_ADD reduces variations in T_ADD, given that T_ADD may vary in different systems or locations. Li another embodiment of the disclosed method and apparatus, THRESH may be the particular T_ADD for the system and location wherein the MS is operating. In this case, the particular T_ADD level to be used for THRESH may be stored in a field associated with the key BTS data entry 302 of FIGURE 3. Alternatively, THRESH may be stored in a sub-field of the key BTS data entry 302. If the signal strength for the signal havmg a PN offset equal to PN,- is greater than THRESH, the method proceeds to STEP 412. 053 At STEP 412, the entry corresponding to PN,- in the Neighbor List 311 is identified. The offset value, PN,-, should be present in the Neighbor List 311, because any signal having a strength greater than THRESH can be assumed to have originated within the area associated wifli the Neighbor BTSs. Therefore, there should not be any ambiguity regarding the mapping /5- of the PN offset and a Neighbor BTS. However, if the PN,- offeet is not identified in the Neighbor List 311, then the PN,- offset is sought from among the other lists in STEP 413. If found, then the information associated with PN,- is moved to the Neiglibor List 311. In accordance with one embodiment of the disclosed method and apparatus, the information to be moved includes the PN,- offset and the location of the BTS from which that PN,- is transmitted. 54 From STEP 412, the method proceeds to STEP 428 at which the method determines whether the most recent value of PN,- is the last value to be considered (i.e., "i" = "n"). If the answer is YES, the method proceeds to STEP 432, which terminates the method. If the answer is NO, the method proceeds to STEP 430 wherein the index "J" is incremented, and then returns to STEP 410. 55 If the signal strength is equal to or less than THRESH, the method proceeds from STEP 410 to STEP 414. At STEP 414, the Neighbor List 311 is searched to determine whether there is a match with the PN,- offset. Even though the signal strength is below the threshold level, such a match may occur if the signal from a Neighbor BTS is blocked by a building or other obstacle. If there is a match, the method proceeds to STEP 416. If not, then the method proceeds to STEP 418. It should be noted that there is a relatively high likelihood that PN,- will match one of the entries 317, 318 in the Neighbor List 311, since many of the BTSs from which the MS 102 will receive signals will be on the Neighbor List 311. However, this assumes that the Neighbor List 311 has been completely compiled. Li one embodiment of the disclosed method and apparatus, the Neighbor List 311 is generated by gathering reports from MSs that have received signals from a BTS that are above THRESH. 56 At STEP 416, since the signal level was below the threshold level, a coverage and phase test (CPT) is applied to the PN,- offiset to determine if the PN,- corresponds to a Neighbor BTS. The CPT is performed because it is possible that two BTSs may have the identical PN, offset. The CPT confirms whether a signal having tiie particular PN offset value foimd in the Neighbor List 311 was actually transmitted by a Neighbor BTS or was transmitted by a BTS that is farther away then would allow that BTS to qualify as a Neighbor BTS. A "YES" answer to this test signifies and confirms that the PN,- offset has been imambiguously identified by the CPT as being from a Neighbor BTS. Jfthe answer at STEP 416 is YES, the method proceeds to STEP 428. If the answer is NO, the method proceeds to STEP 418. The CPT test is described in detail further below. Accordingly, for the sake of clarity, no further information regarding CPT is provided at this point. / 57 At STEP 418, the Hearable List 322 is searched to determine whether there is a match or matches for the PN,- offset. As described in more detail below, the Hearable data is initially empty, and these entries become populated as a result of the operation of the disclosed method. If tiie answer at STEP 418 is YES, the method proceeds to STEP 420. If the answer is NO, the method proceeds to STEP 422. 58 At STEP 420, a CTT is apphed to the PN, offset to confirm a positive match in STEP 418. As indicated above, there may be more than one match foimd for the PN,- offset at the preceding STEP 418. A "YES" answer to this test signifies that the PN,- offset has been unambiguously identified by the C3*T. If the answer at STEP 420 is YES, the method proceeds to STEP 428 for fiirtha: processing. If the answer is NO, the method proceeds to STEP 422. 59 At STEP 422, the Remaining BTS data is searched to detennine if there is a match or matches for the PN,- offset. If the answer is YES, then the method proceeds to STEP 424. If the answer is NO (no match foimd), the method proceeds to STEP 427. 60 At STEP 424, a CPT is apphed to the PN,- offset to confirm a positive identity determination for tiie match(s) identified in STEP 422. As noted above, there may be more than one match found for the PN,- offset at tiie preceding STEP 422. In this case, the result of the CPT test will verify which one, if any, of tiie matches is correct. A "YES" answer to this test signifies that the PN,- offset has been imambiguously identified by the CPT. If the answer at STEP 424 is YES, the method proceeds to STEP 426. If the answer is NO, the method proceeds to STEP 427 where the PN,- offset is labeled with an error flag. 61 At STEP 426, the data for flie Remaining BTS identified for the current PN,- offset is added to the Hearable List 322. Adding to the Hearable List 322 facilitates flie identification of tiie BTS for fiitxffe searches. This process of adding to the Hearable List 322 also improves the efiBciency of the search process. That is because the Remaining List 333 constitutes a much larger data set than the Hearable List 322. By adding a new BTS to the Hearable List 322, the new BTS can be identified in the future without the need for searching the larger Remaining List 333. Thus, in accordance witii one embodiment of the disclosed metiiod and apparatus, adding to the database reduces the search time. The particular set of BTSs that can be heard may change with time. Therefore, in accordance with one embodiment of the disclosed method and apparatus, BTSs that have not been recently detected and reported are removed from the Hearable List 322. Removing BTSs in5)roves search efficiency and/or reduces memory requirements. /7 062 Determining when to remove a BTS may be in:5)lemented, for example, by time stamping entries each time they are detected by an MS being served by the serving BTS identified in the key BTS data entry residing in the same record with the Bearable List 322. Entries may then be deleted if an MS has not detected them for a predetermined period of time. Alternatively, the location of the Hearable BTS entries in the list can be modified by placing the most recently detected BTSs at the top of the list In this way, BTSs that are not recently detected are migrated to tiie bottom of the list and become eligible for deletion. A combination of these two approaches may also be en^loyed. From STEP 426, the method proceeds to STEP 428. 63 At STEP 427, the processor notifies the operator, by means of an error flag, or some other notification message, that a BTS corresponding to the current PN,- offset was not xmiquely identified by the search process. The error flag alerts the operator so that corrective action may be taken. In particular, if the PN,- offset cannot be uniquely identified, it should not be used for conq)utation of a location estimate. From STEP 427, the method proceeds to STEP 428. 64 As noted above, at STEP 428 the data index, i is tested to determine whether all the PN,- offset have been evaluated. If the answer is NO, the method proceeds to STEP 430, where the index i is incremented. The next PN,- offset is identified by searching the database as described above. If the answer is YES, the method proceeds to STEP 432 and the process terminates. 65 FIGURES 5a and 5b comprise a unified flow chart illustrating another operation of a system, such as the system 100 of FIGURE 2, for locating BTSs based on data received fi-om flie MS. The method is initiated at STEP 502, wherein a database, such as the database 300, is created. At STEP 504, data is obtained from an MS requiring its position to be determined. The data is provided to a processor, which may be incorporated in a PDE or an MS. The data is obtained from an MS requiring its position be determined and provided to a processor. The process may be incorporated in a PDE or an MS. The processor is operatively connected to the database to receive and store data, and may be implemented in a processor such as either the processor 204 or the processor 232 of FIGURE 2. The data includes a Global Identifier (GIo) for at least one BTS signal received by the MS, and the PN,- offset (i = 1, n) of each received signal provided by the MS for evaluation, where n is the number of BTS signals provided by the MS for evaluation. The method then proceeds to STEP 506. At STEP 506, the processor finds the key BTS data entry in the database corresponding to the GIo. The method proceeds to /6 STEP 508. At STEP 508, a counter is initialized by setting an index i = 1, and the method proceeds to STEP 510. 66 At STEP 510, the signal strengfli of the signal having the PN offset, PN,-, (hereafter referred to as "the signal having the PN;") is coiqpared to a signal strength ttireshold level THRESH. If the signal strength for the signal having the PN,- is greater than THRESH, the method proceeds to STEP 512. At STEP 512, the PN,- is sorted into a "Candidate Ust", referred to as PNc data, and the method proceeds to STEP 516. At STEP 516, tiie index "i" is tested to determine whe&er all of the PN/S for i equal to 1 through n have been sorted. If the answer is YES, the method proceeds to STEP 520. If flie answer is NO, flie method proceeds to STEP 518. At STEP 518, the index i is incremented. The method then returns to STEP 510 and the sorting process is repeated as described above. 67 If at STEP 510 the signal strength is less than or equal to THRESH, the method proceeds to STEP 514. At STEP 514, the PN,- is sorted into an "Unknown List", referred to as PN„, and the method proceeds to STEP 516. When the sorting process implemented by STEPS 510, 512, 514, 516 and 518 is completed, the entries PN,- (i = 1, n) will have been sorted into one ofthe two sets PNc (c= 1, c,TO«)orPN„(M = 1, Unax). where (^mx + Mimx^n. 68 At STEP 520, all of the data in the PN^ data is assumed to be in the Neighbor List 311. This assumption will typically be valid, since any signal having a signal strength exceeding THRESH can be assumed to have originated within the proximate geographical areas associated with the Neighbor BTSs. Therefore, there is no ambiguity regarding the mapping of the PN offset and the BTS identities for Nei^bor BTSs. The method tiien proceeds to STEP 524 (FIGURE 5(b)) via a flow connector 522. 69 At STEP 524 (FIGURE 5(b)), the index "w" is initiahze by setting M = 1. The method then proceeds to STEP 526. At STEP 526, the Neighbor List 322 is searched to determine whether there is a match for the PN„ data. Such a match will occur, for example, when the signal from a Neighbor BTS is blocked by a building or other obstacle, causing the signal strength to fall below THRESH. If a match is found at STEP 526, the method proceeds to STEP 528. At STEP 528, a CPT is appUed to tiie PN„ data. A "YES" answer to tiiis test signifies that the PN„ has been unambiguously identified by the CPT. Accordingly, if the answer at STEP 528 is YES, then the process proceeds from STEP 540. At STEP 540, the index u is tested to determine whether all of the PN„ offset have been evaluated. As noted above in reference to STEPS 510, 512, 514, 516 and 518, the entries in the PN,- (f = 1, n) hst were sorted into the sets PN^ (c = 1, Cnax) ^^^d PNn (M = 1, Uinax)> where Cn^^ + Mmax = n. If the /9 answer at STEP 540 is NO, the method proceeds to STEP 542 where the index u is incremented, and the next PN„ offset is identified by searching the database as described above. If the answer at STEP 540 is YES, the method proceeds to STEP 544 and the process terminates. 70 Retummg to STEP 526, if tiie answer to STEP 526 is "NO", then the method proceeds to STEP 530. Similarly, if the answer at STEP 528 is NO, the method proceeds to STEP 530. At STEP 530, the Hearable BTS data is searched to determine whether there is a match or matches for the PN„ measurement If the answer at STEP 530 is YES (match was found), the method proceeds to STEP 532. At STEP 532, a CPT is applied to the PN„ data to confirm a positive identity determination for the match(s) identified during STEP 530. A "YES" answer to this test signifies that the PN,- ofiset has been unambiguously identified by the CPT. If the answer at STEP 532 is YES, the method proceeds to STEP 540 for further processing as described below. If the answer is NO, the method proceeds to STEP 534. Returning to STEP 530, if the answer is NO (no match foimd), the method proceeds to STEP 534. 71 At STEP 534, the Remaining List 333 is searched to determine whether there is a match or matches for the PN„ measurement. If a match is found, the method proceeds to STEP 536. At STEP 536, a CPT is appUed to the PN„ offset to confirm a positive identity deternoination for tiie match or matches identified in STEP 534. The CPT verifies which, if any, of the matches is correct. A "YES" answer to the CPT test signifies that the PN„ has been unambiguously identified by the CPT. If the answer at STEP 536 is YES, the method proceeds to STEP 538. At STEP 538, the offset for the Remote BTS identified for tiie current PN„ offset are added to the Hearable List 322. The metiiod tiien proceeds to STEP 540 for fiirther processing as described below. 72 Returning to STEP 534, if tiie answer is NO, tfie metiiod proceeds to STEP 539. Similarly, if the answer at STEP 536 is NO, the metiiod proceeds to STEP 539. At STEP 539, the processor notifies the operator by means of an error flag that a BTS corresponding to the current PNB offset was not uniquely identified by the search process. The method then proceeds to STEP 540 and proceeds as noted above. 73 STEPS described above in reference to FIGURES 4, 5(a) and 5(b) may be implemented by a processor within a PDE, such as tiie PDE 130 (EvIGURE 2), using a processor such as the processor 232, executing according to software instructions stored in a memory such as the memory 234. 2o 74 As previously noted, in an alternative embodiment, the database may be located in an MS ratiier than in the PDE. In this alternative embodiment, the method steps described above may be inq)lemented by a processor within an MS such as ihe MS 102, using a processor such as the processor 204, and a memory such as the memory 206. In Ibis embodiment, the MS reports the BTS identities to the PDE rather than reporting the PN ofiset, so that the PDE is not required to determine the BTS identities. 75 As noted above, the CPT is used to select tiie correct entry from those stored in the Neighbor location sub-fields 315, Bearable location sub-fields 323, or Remaining location sub-fields 337 from within the location entries stored in the recOTd associated with the key BTS entry 302. The particular name or other identifying information, such as SID/NDD/BaselD of tihe BTS need not be known. What is important is that the correct entries within the database 300 be correctly selected. This is important, since the objective is to properly locate the source of the signals received by the MS. fa one embodiment of the disclosed method and apparatus, the relative times of arrival of tiiose signals are used, together with the location of the BTS from which the signals were sent, to determine the location of the MS. 76 fa one example of the disclosed CPT, if the primary serving BTS is located in Seattle, Washington, then the MS 102 must be located close enough to communicate with the primary serving BTS. Accordingly, the MS 102 must be in or near Seattle, fa addition, each other BTS from v/hich the MS is rcccivxrig signals nrast be suluincntly close to the MS to permit the MS to receive those signals. 77 FIGURE 7 illustrates a system 700. The system 700 comprises a CPU 702, a memory 704, a transceiver 712 mcluding a transmitter 708 and receiver 710, a signal analyzer 720, a statistical model 722 and a timer 724. The system 700 performs a statistical analysis based on the amount of overlap in coverage areas between primary serving BTS and a BTS represented by a particular set of entries to the database 300. This geographic region analysis assists in determining the likelihood that the particular BTS represented by the set of entries is the source of signals received by the MS. Once the likelihood is determined, the CPT outputs a decision as to whether the MS received signals from that particular BTS. The system 700 may also perform a phase measurement analysis using relative phase measurements. The coverage overlap and relative phase measurement processes are described in greater detail below. 78 The system 700 is provided with information regarding one or more candidate BTSs including, the PN offset, BAND_CLASS, and frequency of the signals received by the MS 302. The system 700 can limit tiie candidate list to BTSs that are located near the coverage area of 21 the primary serving BTS. The coverage area may be refined based on the identify of any other BTSs that have been previously identified as having transmitted signals received by the MS 102. When the entries associated with a first BTS have been imiquely identified, that information may be used to uniquely identify entries fmrn the database 300 associated with other BTSs from which the MS 102 is receiving signals. As more and more entries are identified, further information is provided to the system 700 to help identify additional entries, and thus locate tiie remaining BTSs from which the MS 102 has received signals. 79 In certain cases, the geographic region analysis described above may be sufficient to uniquely locate the BTS from which signals associated with a particular PN offset were transmitted. For example, there may be only one BTS represented by a particular PN offset that is located within the vicinity of the primary serving BTS. As previously discussed, imiquely locating one BTS from which signals were received by Ihe MS 102 can provide fiirther data used to locate additional BTSs from which signals have been received by the MS 102. 80 A one-dimensional probabihstic calculation is relatively simple to perform using a Gaussian distribution. The HEPE is based on an assumption that the density of MSs that hear a BTS is distributed as a two dimensional Gaussian distribution centered at the center of the BTS coverage area. The system 700 may calculate probabilities in two dimensions to accommodate variations in the location of the MS 102 in the North-South direction as well as variations in the East-West direction. To accommodate such two-dimensional probabilities, the system 700 calculates a "horizontal estimated position error" (HEPE) value based on possible errors in two directions. In one example, the HEPE value of a known coverage area is calculated as the square root of the sum of squares of error estimates in each of the two directions. If one assumes the MS 102 to be located vwthin one-sigma (i.e., one standard deviation) from the mean in a Gaussian distribution of the location of MSs, the HEPE value may be represented by the following: 081 082 HEPE = ^I(T/+CX/ (1) 083 084 where a^, indicates a one-sigma error in the location of an MS in the North-South direction and a^ indicates a one-sigma error in the location of an MS in the East-West 2Z direction. Those skilled in the art will recognize that because the coverage areas are considered to be circles, the HEPE value represents the diagonal of a square, the sides of the square being equal in length to the radius of the circle. FIGURE 8 illustrates a coverage area 850 of a primary serving BTS. Associated with the area 850 is a HEPE value illustrated in FIGURE 8 as 85 Since &e MS 102 is known to be within the coverage area of the primary serving BTS, the coverage area of the primary serving BTS can be referred to as a 'Tcnown area" 850. In addition, the known area 850 can include the into^ection of the coverage areas of the primary serving BTS and tiie coverage area of other BTSs. Accordingly, the known area 850 may be smaller flian the coverage area of the primary serving BTS if there is additional information available regarding other BTS from which the MS 102 is known to be receiving signals. 86 Also illustrated in FIGURE 8 are the coverage areas of three BTSs from which the MS 102 might have received signals based on tiie fact fliat each has an identical PN offset of 25 (i.e., 25 X 64 chips). The coverage areas 852 and 856 do not overlap with the area 850. In contrast, there is overlap between the coverage area 850 and a coverage area 854 corresponding to the PN 25 candidate 2. The one-sigma value for ti»e PN 25 candidate 2 is illustrated in FIGURE 8 by the value ra. The values ri and T2 indicate a metric to be used in determining the relative size of coverage aiea 850 wiili respect to the candidate coverage area 854. Ihe distance from the center of the coverage area 850 and the center of the coverage area 854 is illustrated in FIGURE 8 by the reference D. 87 The statistical model 722 (see FIGURE 7) of the system 700 calculates a measure of coverage area separation using the relative size of coverage areas and the distance D separating the centers of coverage areas. This separation may be represented by tiie following: 088 089 Separation -» . (2) w 090 23 091 where all of the terms have been previously defined. A normal distribution statistical evaluation may be made of the term in equation (2) to generate a probabilistic measure of separation between the coverage area 850 and the coverage area 854. 092 The normal distribution is sometimes calculated using the following: 093 094 ND(X)= -—e 2 (3) 095 096 where x is a number representative of the amount of separation away from a perfect overlap between the coverage area 850 and the coverage area 854. hi one embodiment, the value X is chosen to be the Separation value from equation (2). This equation may be simplified as the following: 097 098 ND(x)^e^ (4) 099 100 where all of the terms have been previously defined. 101 As an example of the application of the model 722 illustrated above, consider that the values rj and ra are 2.0 and 1.0, respectively, while the distance D is 1.1. Note that these distances may be measured in convenient units, such as kilometers or miles. Inserting these values into equation (2) provides a result of 0.49 for the separation. Substituting that value as x in equation (4) provides a result of 0.886. This indicates an 88.6% probability of perfect overlap between the coverage area 850 and the coverage are 854. Note that a perfect overlap gives the result of 1.0. 102 In contrast, the one-sigma value for the coverage area 852, ra, is equal to 1.5 while the distance D between the center of the coverage area 852 and the center of the coverage area 850 is 4.0. Applying these values to equation (2) provides a result of 1.6 for the separation. Substituting that value into equation (4) provides a result of 0.278, which indicates a 27.8% M probability of perfect overlap between the coverage area 850 and the coverage area 852. Thus, it can be seen that there is a greater probability (i.e., higher likelihood) that signals received by the MS were transmitted by the BTS at the center of coverage area 854 then by either the BTS at the center of coverage area 856 or coverage area 852. 103 The system 700 can eliminate BTSs based solely on the geographic region analysis. However, those skilled in the art will recognize that there is some probability, however small, that signals received by the MS could have been transmitted by the BTS at the center,of coverage area 852 or covCTage area 856. Therefore, in accordance witti one embodiment of the disclosed method and apparatus, the system 700 will only eliminate a candidate if the probabilities calculated using equation (4) differ by a factor of 10. That is, a candidate will be eliminated based solely on coverage area overlap only if some other candidate is at least 10 times more likely to be the detected BTS. In the exanqile illustrated above, candidate 2 is slightly more than three times more likely to be the BTS detected by the MS 102 than the candidate 1. Therefore, the system 700 will perform additional analysis to uniquely identify the candidate BTS. 104 In one embodiment, the system 700 will analyze any candidate BTS using equation (4) if the result of equation (2) is less than 8. This first step of analysis ensures that even candidates with a very low probability of coverage overlap will be analyzed using equation (4). If the amoimt of the one-sigma separation in equation (.2) equals 8, the probability using equation (4) is very small. As a practical matter, the system 700 will eliminate any candidate whose one-sigma overlap has such a large value. This may typically occur in a situation where great distances separate the coverage area of a candidate BTS from the coverage area of the primary serving BTS. For example, if the coverage area 850 is in Seattle, Washington and another BTS is in San Francisco, California, the distance D separating the two BTSs is so large that the probability of reception from the San Francisco BTS can be ignored. 105 In addition to a coverage area overlap analysis described above, the system 700 uses a relative phase model to flirther narrow the list of candidate BTSs. The term "relative phase" is used to indicate the difference between the measurement phases between a known BTS and a reference BTS. This "relative phase" (when adjusted for known biases, including the PN offset) should be approximately equal to the difference between the distance from the known BTS and the MS 102, and a candidate BTS to the MS 102. As discussed above, each BTS transmits an identical PN sequence, but witii known time delays or PN offsets. When two candidate BTSs have an identical PN offset, the signal will be detected by the MS 102 at 25- different times (or phase offsets) based on the distance from the candidate BTS to the MS 102. In one example, the MS 102 is known to be within the coverage region of the primary serving BTS 112. If two candidate BTSs are also within that coverage region, it may be possible to eliminate one of the candidate BTSs based on the relative phase, which is indicative of the propagation delay. For example, if one candidate BTS is within two miles of the Reference BTS while the other candidate BTS is twenty miles from tiie primary serving BTS, the relative phase between the two can often be used to eliminate one of the candidate BTSs. 0106 In one embodiment, the statistical model 722 (see FIGURE 7) uses a double-difference relative phase model as follows: 0107 0108 ND ([(dK-dCi)-(pK-pC)]/SC) (5) 0109 110 where dK is the distance from the center of the combined coverage area (i.e., the combined coverage area of the candidate BTS and tiie primary serving BTS or another BTS, the location of which has been identified) to an already known BTS, dCi is the distance from the combined coverage area center to the ith candidate BTS, pK is the phase measurement to the known BTS, pC is the phase measurement to the candidate BTS, and SC is the size of the expected double-difference phase error based on the combined coverage area. The term "double difference" refers to a statistical calculation based on two difference measurements (i.e., the difference in distance minus the difference in phase). 111 The combined coverage area is a probabilistic measure of the combined areas of coverage of the known BTS and the candidate BTS. Details on the measurement of the combined coverage area are provided below. The relative phase model is used to determine whether the phase delay measured by the MS 102 is consistent with the distances between the known BTS and the candidate BTS. As discussed above, the known BTS may be the primary serving BTS or any other measurement BTS that has already been uniquely identified. 112 The exanqjle presented above is one technique that may be used to determine such relative phase differences. Those skilled in the art will recognize that other techniques may be used to determine such phase differences. The present invention is not limited by the specific analysis described above to determine the relative phase differences. J26 113 The calculation of the relative phase is illustrated in FIGURE 9 where the approximate center of a combined coverage area 960 is indicated by the reference numeral 964. The distance dK is the distance between the center 964 of the combined coverage area 960 and a known BTS 966. As discussed above, the known BTS 966 may be the primary serving BTS or any other uniquely identified BTS. 114 A candidate BTS 968 has a coverage area 962, which in this example, is modeled as a circle. As shown in FIGURE 9, the candidate BTS 968 is not located at flie center of the candidate coverage area 962. This is due to the fact that a typical BTS is not omni-directional, but is broken up into a number of sectors. The sector could be modeled by the system 700 as a pie-shaped sector. However, such modeling is often inaccurate due to back scatter from tiie antenna, as weU as reflection off buildings, natural terrain, and other objects. Thus, the candidate coverage area 962 may be modeled as a circle. Similarly, the known BTS 966 is typically not located at the center of the known coverage area (not shown in FIGURE 9) for the reasons discussed above. 115 The coverage areas of each BTS (or each cell sector) is determined at the time of installation and is known. The combined coverage area, indicating the coverage area of the known BTS 966 and the candidate BTS 968, can be calculated linearly by calculating an area of overlap of circular areas of coverage. Alternatively, the combined coverage area may be calculated weighting the coverage areas. The determination of the combmed coverage area is described in greato- detail below. 116 The combined coverage area 960 is determined based on coverage areas mapped when a BTS is installed and calibrated. The combined coverage area 960 is a probabilistic estimation of coverage areas of tiie known BTS 966 and the candidate BTS 968. As discussed above, the two-dimensional positional error, referred to as EEPE value provides a measure of the statistical imcertainty in measuring the combined coverage area 960. In the system 700, a distance SC is based on HEPE value coverage and represents a one-sigma imcertainty in the relative phase. 117 The distance between the center 964 of the combined coverage area 960 to the candidate BTS 968 is indicated by d;. Phase measurements PK and pc are measured by the MS 102 and provided to the BTS using telecommunication standard IS-SOl. 118 As noted above, the system 700 can calculate the expected relative phase difference and compare the expected phase difference with actual distance measurements. The system 700 2^ may apply fee normal distribution equation (4) to calculate fee probability feat fee candidate BTS is consistent wife fee phase and distance measurements. If multiple candidate BTSs (with fee same PN) are detected by fee system 700, it may be possible to eliminate one or more fee candidate BTSs based on the relative phase difference. That is, fee candidate BTS must have a phase difference feat is reasonable given fee location of fee known BTS from fee center 964 of fee combined coverage area 960 to fee distance from fee candidate BTS from fee center of fee combined coverage area. Candidate BTSs that are inconsistent can be eliminated as candidates to have been fee source of signals received by fee MS 102. 119 The relative phase model is applied to ofeer candidate BTSs as well. For example, FIGURE 8 illustrates feree candidates feat all have fee identical PN 25 offset. The analysis process described above is applied to each of fee candidate BTSs (e.g., fee BTSs transmitting PN 25 located in fee center of fee circles 850, 852, 854 in FIGURE 8) wife a probability calculated for each candidate BTS. As noted above, a candidate BTS may be eliminated based solely on fee coverage area overlap model if fee coverage overlap of anofeer BTS is at least 10 times more likely fean fee coverage area overlap of fee BTS to be eliminated. Similarly, a particular candidate BTS may be eliminated based solely on fee relative phase model if fee phase difference probability of another BTS is at least 10 times more likely than fee phase difference probabiUty of fee BTS to be eliminated. This process assures feat a low probability candidate BTS will be eliminated while maintaining a low likelihood of eliminating fee wrong BTS. 120 The probabilities of fee coverage area overlap model and fee relative phase model may be combined to eliminate candidate BTSs. In one exanq)le, fee probability of the coverage area overlap model is multiplied by fee probabiUty of fee relative phase model. The combination of probabilities serves to further eliminate unlikely BTSs from fee set of candidates. A candidate BTS may be eliminated based on fee combined probability model if the combined probability overlap of anofeer BTS is at least 10 times more likely than fee coverage area overlap probability of the BTS to be eliminated. 121 In addition to the analysis described above, fee system 700 may also use signal strength and cell sector coverage models to uniquely identify candidate BTSs. As discussed above, a typical BTS has multiple transmitters and multiple antenna elements, each of which is directed for operation in a sector. In a typical embodiment, a BTS may have three sectors, each of which may be considered a separate BTS. The area of coverage of a typical sector may have a pie-shaped coverage area. 2S 122 The system 700 may calculate scale factors based on received signal strength. One measure of received signal strength is Ec/Io, which is a measure of the pilot energy accumulated over a 1 PN chip period (i.e., Ec) to the total power spectral density (i.e., lo) in the received bandwidth. Those skilled in the art will recognize that other power measurements may also be used with the system 700. The system 700 assigns a scale factor based on tiie strength or weakness of the received signal. If the received signal strengtti is relatively weak, then the MS 102 may be located wittiin a relatively wide area with respect to the BTS. In this event. His circular coverage area may be expanded by a scale factor to produce a larger circular coverage area, hi contrast, the system 700 may reduce the coverage area if tiie received signal strength is strong since the MS is more likely to be close to the BTS. 123 Jn one embodiment of tiie disclosed method and apparatus, the system 700 may apply a scale factor of 0.9 for a strong signal (i.e., a signal above a threshold) and may apply a scale factor of 1.1 for weak signals (below the threshold). In a single calculation, the coverage area of a single known BTS may be identified as a known area for the coverage area overlap model. Similarly, a single Icnown BTS may be used in combination with a single candidate BTS to generate the combined coverage area used in the relative phase model. However, the system 700 can also accommodate calculations of the known area or combined coverage area that may result from mixing coverage areas from multiple cells. The cells may be combined in a linear fashion or may include weighting. 124 Those of ordinary skill in the art shall recognize that computer readable medium that tangibly embodies the method steps of any of the embodimraits described herein may be used in accordance witii flie present teachings. Such a medium may include, without limitation, RAM, ROM, EPROM, EEPROM, floppy disk, hard disk, C3>-R0M, etc. The disclosure also includes the method steps of any of the foregoing embodiments synthesized as digital logic in an integrated circuit, such as a Field Programmable Gate Array, or Programmable Logic Array, or other integrated circuits that can be fabricated or modified to embody computer program instructions. 125 The MS 102, in accordance with the present teachings may include, without limitation: wireless telephone, a personal digital assistant with wireless communication capabilities, a laptop having wireless communication capabilities, and any other mobile digital device for personal communication via wireless connection. 126 A number of embodiments of disclosed method and apparatus have been described. Nevertheless, it will be understood that various modifications may be made to the disclosed 29 method and apparatus. For example, the methods can be executed in software or hardware, or a combination of hardware and software embodiments. As another example, it should be understood that the functions described as being part of one module may, in general, be performed equivalently in another module. As yet another exanq)le, steps or acts shown or described in a particular sequence may generally be performed in a different order. In yet one more example, the disclosed method and apparatus is described with reference to the example of PN offset. However, persons skilled in the communications arts will understand that the disclosed method and apparatus may use other forms of ambiguous transmitter identifying information. 0127 Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiments of the disclosed method and apparatus, but only by the scope of the appended claims. 1. A method for identifying the location of a transmitter of signals received by a mobile station, comprising the steps of: a) receiving a signal having ambiguous identification data; b) checking a neighbor list for data that matches the ambiguous identification data provided in the received signal; c) determining whether the received signal is above a threshold; and d) if above the threshold, then determining the location of the transmitter from location data associated with the matching data in the neighbor list. 2. The method of Claim 1, wherein: a) if the received signal is not above the threshold, then verifying that the transmitter associated with the data that matches is likely to have transmitted the received signal; and b) if the transmitter associated with the data that matches is likely to have transmitted the received signal, then determining the location of the transmitter trom data in the neighbor list associated with the data that matches. 3. The method of Claim 2, wherein: a) if either i) no data in the neighbor list matches or ii) no transmitter associated with data that matches is likely to be the transmitter of the received signal, then checking a bearable list of all transmitters from which signals had been previously received; b) if the received ambiguous data matches data associated with at least one transmitter in the bearable list, then determining from among transmitters on the bearable list associated with data that matches, the most likely transmitter to be the source of the received signal; and c) determining the location associated with the most Hkely transmitter on the hearable list from data in the hearable list. 4. A method for identifying the location of a base station transceiver (BTS), comprising the steps of: a) receiving in a mobile station (MS) a signal from a primary serving BTS; b) receiving in the MS an additional signal from a second BTS, the additional received signal having ambiguous data regarding the identity of the second BTS, the ambiguous data potentially being similar to data transmitted from at least a third BTS but not necessarily received by the MS; c) checking a neighbor list having less then all of the BTSs that could have transmitted the received signal, to determine whether the ambiguous data matches data in the neighbor list associated with at least one BTS, the location of the at least one BTS being discemable from data in the neighbor list; d) if the ambiguous data matches data associated with at least one BTS in the neighbor list, then verifying which BTS associated with the matching data is most likely to have transmitted the received signal; and e) if either the ambiguous data does not match data associated with any of the BTSs on the neighbor list, or none of the BTSs associated with data that matched is likely to have transmitted the received signal, then checking a hearable list containing all BTSs from which signals had been previously received by MSs in communication with the primary serving BTS; f) if data associated with at least one BTS on the hearable list matches the ambiguous data of the received signal, then determining from among those BTSs associated with the matching data, the most likely BTS to have transmitted the received signal; g) determining the location of the transmitter most likely to have transmitted the ambiguous data from data on the hearable list. 5. The method of Claim 4, wherein the data on the hearable list is the location of the transmitter most likely to have transmitted the ambiguous data. 6. The method of Claim 4, wherein the data on the hearable list is a link to a memory that stores the location of the transmitter most likely to have transmitted the ambiguous data. 7. A method for determining the location of a Base Transceiver Station (BTS), comprising the steps of: a) receiving from a mobile station (MS) data including: i) at least one Global Identifier; ii) at least one pseudorandom noise (PN) offset of signals received by the MS; iii) the signal strength of at least one of the signals that have the received PN offset; b) sorting a PN offset into a Candidate List if the strength of the signal received by the MS and having that PN offset is above a predetermined threshold; and c) determining whether each of the PN offsets of the Candidate List is on a neighbor list, the neighbor list including a location associated with each PN offset, and determining the location associated with each PN offset found in the neighbor list, the associated location being the location of the source of the signal having that PN offset. 8. The method of Claim 7, comprising: a) sorting a PN offset into an Unknown List if the strength of the signal having that PN offset is not above a predetermined threshold; b) determining whether each of the PN offsets of the Unknown List is on a neighbor list, the neighbor Ust including a location associated with each PN offset; c) testing whether each PN offset in the Unknown List has been unambiguously associated with a PN offset in the neighbor list; and d) if at least one PN offset has been unambiguously associated, then determining the location associated with unambiguously associated PN offset found in the neighbor list, the associated location being the location of the source of the signal having that PN offset. 9. A device configured to carryout the method claimed in any one of the preceding claims.

Documents:

0340-chenp-2006-abstract.pdf

0340-chenp-2006-assignement.pdf

0340-chenp-2006-claims.pdf

0340-chenp-2006-correspondnece-others.pdf

0340-chenp-2006-description(complete).pdf

0340-chenp-2006-drawings.pdf

0340-chenp-2006-form 1.pdf

0340-chenp-2006-form 26.pdf

0340-chenp-2006-form 3.pdf

0340-chenp-2006-form 5.pdf

0340-chenp-2006-pct.pdf

340-CHENP-2006 ABSTRACT.pdf

340-CHENP-2006 CLAIMS GRANTED.pdf

340-chenp-2006 complete specification as granted.pdf

340-CHENP-2006 CORRESPONDENCE OTHERS.pdf

340-CHENP-2006 CORRESPONDENCE PO.pdf

340-chenp-2006 drawings.pdf

340-CHENP-2006 FORM 18.pdf

340-CHENP-2006 FORM 3.pdf

340-CHENP-2006 PETITIONS.pdf

340-chenp-2006-abstract.jpg

abs 340-chenp-2006 abstract.jpg