Location estimation of one or more transmitters based on signals transmitted therefrom

[0002] This application claims the benefit of U.S. Provisional Application No. 60/191,269, filed Mar. 22, 2000 and entitled “Location Estimation of One or More Transmitters Based On Signals Transmitted Therefrom”, hereby incorporated by reference.

[0003] The present invention relates to a system and method that estimates the location of a single or multiple transmitters. More particularly, the present invention relates to such an estimation method that uses measured data such as Received Signal Strength Indication (RSSI) data collected by a scanning and tracking receiver such as that which may be commercially available.

[0004] The non-invasive estimation of transmitter location and configuration based on signals received from such transmitter(s) is considered to be highly useful in many circumstances. For example, an investment banker or the like may employ such information for preliminary asset determination among other things; a tower company or the like may employ such information for development of a business plan and guidance for site acquisition personnel among other things; a competitor wireless service provider or the like may employ such information to assess the overall system layout of other service providers in a particular market among other things; and a consultant or the like may employ such information to provide value added services to improve overall system performance to a client among other things.

[0005] One typical methodology that may be employed to non-invasively estimate the location of a particular transmitter is to measure signal strengths of signals received from such transmitter at several reception locations, to estimate distance based on such measured signal strengths, and then to triangulate based on such estimated distances. However, and importantly, many factors affect signal strength as measured at a particular reception location, including but not limited to transmission power, terrain, atmospheric conditions, interference, line of sight issues, etc. Thus, the distances estimated from such measured signal strengths have relatively large margins of error, and accordingly triangulation calculations based on such estimated distances have relatively large margins of error, too. Ultimately, the margin of error of such triangulation calculations is so significant as to render the result of the calculations highly suspect if not meaningless.

[0006] Accordingly, a need exists for a system and methodology for non-invasively estimating transmitter location and configuration information, whereby the margin of error of the result of the methodology is within a more acceptable range.

[0007] The present invention satisfies the aforementioned need by providing a method for estimating the location of a transmitter based on signals transmitted therefrom. The transmitted signals are received at a plurality of reception locations and are employed to compile data including a plurality of entries, where each entry includes a received signal level (RSL) of a received signal, a channel identification of the received signal, and position information corresponding to the respective reception location when the received signal was received.

[0008] In the method, the entries are organized into groups according to channel identification, and, in each group, entries having the same position information are consolidated. Thereafter, for each entry, the distance DRT between the reception location and the transmitter is estimated, and the distance DRR between the reception location thereof and an adjacent reception location is also estimated. Then, for each group, the location of the transmitter corresponding to the channel identification of such group is estimated based on the distances DRT and DRR.

[0009] The foregoing summary as well as the following detailed description of the present invention will be better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there are shown in the drawings embodiments which are presently preferred. As should be understood, however, the invention is not limited to the precise arrangements and instrumentalities shown. In the drawings:

[0010] FIG. 1 is a data collection system employed in accordance with one embodiment of the present invention;

[0011] FIG. 2 is a diagram showing data points (P1, P2) at which data was collected and possible transmitter locations (P3, P3′) represented by the data;

[0012] FIG. 3 is a diagram employed to show how an iterative approach are used to solve for four isosceles triangles using distances derived from FIG. 2 in accordance with one embodiment of the present invention;

[0013] FIG. 4 is a diagram employed to show how transmitter locations are estimated from data points in accordance with one embodiment of the present invention; and

[0014] FIG. 5 is a flow diagram detailing an algorithm performed in accordance with one embodiment of the present invention.

[0015] Certain terminology may be used in the following description for convenience only and is not considered to be limiting. For example, the words “left”, “right”, “upper”, and “lower” designate directions in the drawings to which reference is made. Likewise, the words “inwardly” and “outwardly” are directions toward and away from, respectively, the geometric center of the referenced object. The terminology includes the words above specifically mentioned, derivatives thereof, and words of similar import.

[0016] In one embodiment of the present invention, a system and method are employed to estimate the location of a transmitter through an iterative application of received signal strength data (such as RSSI data), slow fading characteristics and geometric triangulation. In particular, and referring now to the drawings in detail, wherein like numerals are used to indicate like elements throughout, there is shown in FIG. 1 a data collection system 10 in accordance with one embodiment of the present invention. As seen, the system 10 includes a The essential elements of the equipment are a tunable receiver 12 with an appropriate antenna 12afor receiving RF transmissions (or the like) from one or more transmitters, a GPS (Global Positioning System) positioning device 14 with an appropriate antenna 14afor determining the global position of the system 10 at the time of each collection of data, and a recording device such as a computer 16 for recording the collected data from the receiver 12 and the corresponding positioning information from the GPS device 14. Thus, the system 10 is employed to produce a data file containing a plurality of entries, where each entry includes a Received Signal Level (RSL) (perhaps expressed in dBm) as obtained from the receiver 12, channel number as obtained from the receiver 12, and corresponding GPS coordinates as obtained from the GPS device 14, where all the data in the entries is collected from/in connection with an operating transmitter network with unknown transmitter locations.

[0017] Each of the aforementioned elements 12, 14, 16 of the system 10 may be any appropriate element without departing from the spirit and scope of the present invention, and may be appropriately configured in any particular arrangement, again without departing from the spirit and scope of the present invention. Moreover, the computer/recording device 16 may be running any appropriate software once again without departing from the spirit and scope of the present invention. The details and specifics of such elements, configuration, and software are known or should be apparent to the relevant public, and therefore need not be described further herein.

[0018] With the system 10 as shown in FIG. 1, the following method is employed in one embodiment of the present invention to estimate transmitter location. Briefly, in the method, the slow fading characteristics of the propagation environment are characterized by {P1, m} where P1 represents the one mile intercept, expressed in dBm, and m is the decay slope, expressed in dB per decade. Under these conditions, the RSL from each entry of the aforementioned data file and the distance from the associated transmitter are directly related. Applying triangulation and this relationship, an estimate of the transmitter location may be obtained.

[0019] The slow fading characteristics of an RF signal in the land mobile environment may be expressed as L_P≈1/rⁿ, where L_Prepresents the RF path loss, r represents the distance, and n is the slow fading decay constant for a specific morphology group. Expressed in the logarithmic domain, 1/rⁿbecomes −10 nlog(r). The decay slope, m, is equal to −10 n. The concept of the 1-mile intercept, P1, allows for convenient calculations in the logarithmic domain. An added benefit is the distance is great enough to ensure the main lobe of the antenna is considered thereby stabilizing the calculations.

[0020] The above concepts were applied with great success by W. C. Y. Lee in the equation: $\begin{array}{c}\mathrm{RSL}=\mathrm{P1}+10\log \left(\frac{P_t}{P_{\mathrm{ref}}}\right)+m\log \left(r\right)+\\ \alpha \log \left(\frac{h_t}{h_{\mathrm{ref}}}\right)+\beta \log \left(\frac{h_m}{h_{\mathrm{ref}}}\right)+\mathrm{APE}+\mathrm{KED}\end{array}$

[0021] where:

[0022] RSL=Received Signal Level (dBm)

[0023] P1=1 mile intercept (dBm)

[0024] P_t=Effective Radiated Power (ERP) of the site

[0025] P_ref=Reference ERP

[0026] m=slow fading decay slope (dB/decade)

[0027] r=distance

[0028] α=coefficient applied to transmitter height adjustment

[0029] h_t=height above ground level of the base station transmit antenna

[0030] h_ref=reference height of the base station transmit antenna

[0031] β=coefficient applied to receiver height adjustment

[0032] h_m=height above ground level of the receiver (mobile) antenna

[0033] h_ref=reference height of the receiver antenna

[0034] APE=antenna pattern effects (vertical and horizontal beamwidths)

[0035] KED=Knife Edge Diffraction

[0036] The primary contributors are RSL, P1, 10 log(P_t/P_ref), mlog(r), and αlog(h_t/h_ref). The remaining terms are either unknown or have little impact on the result. RSL is obtained from the collected data. P1, P_t, m, α, and h_tare assumed. The distance r is to be calculated. The final equation to be used becomes: $r=10^\left[\frac{1}{m}\left(\mathrm{RSL}-\mathrm{P1}-10\log \left(\frac{P_t}{P_{\mathrm{ref}}}\right)-\mathrm{\alpha log}\left(\frac{h_t}{h_{\mathrm{ref}}}\right)\right)\right]$

[0037] Referring now to FIG. 2, it is seen that P1 and P2 represent the location of two measured data points given by:

[0038] P1: Lat1, Lon1, RSL1, Chan1

[0039] P2: Lat2, Lon2, RSL2, Chan1

[0040] as derived from the aforementioned data file. Note here that Chan1 was measured at P1 and P2. P3 represents the estimated location of the transmitter from which Chan1 originated. P3′ represents the mirror solution. D12 is the distance between the two data points and may be calculated with a reasonable degree of accuracy. D13 and D23 are the respective distances from the data point to the transmitter location and may be estimated by applying an assumed set of propagation parameters, including the slow fading characteristics of the environment. However, since D13 and D23 are estimated, the direct use of D12, D13, and D23 may not form a triangle that can be easily solved using the Law of Cosines.

[0041] In one embodiment of the present invention, then, and as shown in FIG. 3, an iterative approach of solving for four isosceles triangles using the three distances is implemented, thereby yielding 4 possible solutions (P3a,P3b,P3c,P3d). The coordinates of such isosceles triangles may be readily solved using the Law of Cosines. Performing the above procedure on N data points will yield 2N possible solutions. Such solutions are then divided into two groups, G1 and G2, where G1: {P3a,P3b} and G2: {P3c,P3d}.The arithmetic mean of each group is then calculated, and the average with the smallest variance is chosen to yield the estimated most likely location of the transmitter.

[0042] In a transmitter network of a system such as a wireless communication systems, multiple channels are typically used multiple times (Frequency Reuse). In many cases, multiple directional antennas, each with its own channel, are assigned to an individual location (Sectorization). Also, the sampling rate of the scanning receiver is often greater than the rate of update of the GPS receiver, thereby producing multiple measurements at the same recorded location (Duplicate Coordinates). Therefore, the present invention must account for each of these real world conditions.

[0043] Duplicate Coordinates may be handled by either discarding subsequent entries or averaging them. Discarding subsequent entries is computationally more efficient than averaging but imposes significant risk of increased error due to limiting the information about the environment to a single data point. Averaging provides a mechanism to which more information about the environment is used, thereby decreasing the overall error imposed in the process. The computational cost of averaging is considerable small compared to the increased confidence associated with using all of the information. Therefore, averaging the RSL for duplicate coordinates is implemented in the present invention.

[0044] Frequency reuse is the retransmission of a given frequency, typically designated by a channel number, at multiple locations in a manner that introduces tolerable levels of interference into the communication path. In high capacity systems, reuse distances may be as small as two to three miles. An evaluation of the relative distances between successive coordinates of the same channel may be used to detect reuse. The limitation of this approach is that there is a risk of assigning a reuse characteristic to channels transmitted from a location with a discontinuous cover region. However, the solution for discontinuous coverage regions should converge to a relatively small area and may be treated as a sectored site.

[0045] Sectorization is a generic term that implies a location has multiple antennas transmitting unique frequencies. The solutions obtained for multiple channels from a single location should converge in a relatively small region. All solutions within a user-defined region will be attributed to a single location and assigned to the arithmetic average of all solutions within the region. This approach assumes the individual solutions are reasonably correct and will account for sites with discontinuous coverage areas.

[0046] In one embodiment of the present invention, an algorithm such as that detailed in connection with the example set forth below is employed to perform transmitter location estimation for one or more transmitters. Of course, many variations may be made to the algorithm listed below without departing from the spirit and scope of the present invention. Note that each step of the algorithm is also shown in FIG. 5.

[0047] Consider Table 1, as follows, which is derived from a sample data file containing the Latitude, Longitude, Channel, and RSL information therein:

[0048] 1. Assign Reference Channels (RefChan) to raw data:

[0049] As seen in Table 1, Measurements 1 through 4 are all from channel 857 and are assigned Reference Channel 1; Measurements 5 through 12 are all from channel 101 and are assigned Reference Channel 2; and Measurements 13 through 36 are all from channel 857 and are assigned Reference Channel 3.

[0050] 2. Consolidate the Raw Data to remove identical coordinates for the same Reference Channel:

[0051] For each group of data entries having a common assigned Reference Channel, the average RSL is calculated as: $\stackrel{\_}{x}=\frac{1}{N}\sum _{i=1}^N{x}_i,$

[0052] where {overscore (x)} is the average RSL, N is the number of measurements with identical Reference Channel and GPS Coordinates, x_iis the individual measurement. The standard deviation, sigma (σ), is given by: $\sigma =\frac{1}{N-1}\sum _{i=1}^N\left(x_i^2-x^{-2}\right).$

[0053] If there is only one sample, the standard deviation is theoretically infinity but is determined to be 0 for practical purposes. The standard deviation as calculated here is not further employed in the algorithm of the present invention, but does aid in determining the reliability or ‘spread’ of the RSL data. The consolidated raw data with the average RSL and standard deviation appears in Table 2, below.

[0054] 3. Estimate the distance from the transmitter for each consolidated data entry by applying a set of assumed reference conditions:

[0055] The following reference conditions are employed in connection with the present example, and are typical of an 850 MHz system operating in a suburban environment. Of course, other reference conditions may be employed without departing from the spirit and scope of the present invention.

[0056] P_t=100 Watts

[0057] P_ref=100 Watts

[0058] P1=−59 dBm

[0059] m=38.4 dB/decade

[0060] h_t=130′

[0061] h_ref=150′

[0062] α=15

[0063] Applying the above conditions to the consolidated data file using the equation set forth above for r yields the results given in Table 2, as follows:

[0064] 4. Estimate distances between measurements for same Reference Channel:

[0065] The triangulation procedure requires at least two consolidated measurements with the same reference channel. Since Reference Channel 1 has only one consolidated measurement, no estimate can be made. However, estimates may be made for Reference Channels 2 and 3.

[0066] First, the distance between measurements of the same reference channel must be determined. The constants of interest are:

[0067] Polar circumference of the earth (C_Pol)=2*π*3949.9028 miles=817.9712377 miles

[0068] Equatorial circumference of the earth (C_Equ)=2*π*3963.1906 miles=901.4609475 miles

[0069] Latitudinal Distance—consider two lines of latitude (La1, La2). Since the lines of latitude are equally spaced, the latitudinal distance may be easily calculated by: $D_{\mathrm{Lat}}=\frac{C_{\mathrm{Pol}}*\left|\mathrm{La1}-\mathrm{La2}\right|}{360}$

[0070] Longitudinal Distance—consider two lines of longitude (Lo1, Lo2). Since the distance between lines of longitude are dependant on the corresponding latitudes, longitudinal distance is calculated by: $D_{\mathrm{Lon}}=\frac{C_{\mathrm{Pol}}*\left|\mathrm{Lo1}-\mathrm{Lo2}\right|}{360}{\cos }_{\mathrm{deg}}\left(\frac{\mathrm{La1}+\mathrm{La2}}{2}\right)$

[0071] Final Distance—the final distance is given by the hypotenuse of the right triangle formed by D_Latand D_Lonand is calculated using the Pythagorean Theorem as follows.

[0072] D=(D_Lat²+D_Lon²)^½

[0073] Applying the above equations to the data in Table 2 yields the data in Table 3, below. Note that since each D_Latand D_Loncalculation requires a pair of latitude—longitude position coordinates, the calculation for each data entry (row) employs the coordinates of that row and of the next row below. In the case of the last data entry (row) for a particular reference channel, no calculation is performed since no next row exists for such last row.

[0074] 5. Estimate Transmitter Position for each Reference Channel:

[0075] The position estimation is accomplished using D/2 and r from Table 3, above, to form a series of right triangles. Consider the diagram shown in FIG. 4, where P1, and P2 are measured data points given by (La1, Lo1) and (La2, Lo2) respectively (La is latitude, Lo is longitude). P3 is the midpoint between the P1 and P2 along the line D. E1 and E2 are estimated transmitter locations using the distance calculated from the RSL of P1. E1 and E2 lie along a line that is perpendicular to and bisects D at P3 and are given by (ELa1, ELo1) and (ELo2, ELo2) respectively. The distance from P3 to either E1 or E2 is given by $r_{\mathrm{perp}}=\sqrt{r^2-{\left(\frac{D}{2}\right)}^2}$

[0076] The slope of r_perpis the negative reciprocal of the slope m of line D. Applying the above properties, the coordinates of E1 and E2 may be calculated as follows: $\mathrm{ELa1}=\mathrm{La3}+\frac{360*r_{\mathrm{perp}}}{m*C_{\mathrm{Pol}}}$ $\mathrm{ELo1}=\mathrm{Lo3}-\frac{360*m*\left(\mathrm{ELa1}-\mathrm{ELa3}\right)}{C_{\mathrm{Equ}}}$ $\mathrm{ELa2}=\mathrm{La3}-\frac{360*r_{\mathrm{perp}}}{m*C_{\mathrm{Pol}}}$ $\mathrm{ELo2}=\mathrm{Lo3}+\frac{360*m*\left(\mathrm{ELa2}-\mathrm{ELa3}\right)}{C_{\mathrm{Equ}}}$

[0077] Applying the above equations to the data from Table 3 yields Table 4A and 4B (where the first three columns thereof are identical), as follows:

[0078] 6. Determine final location for each Reference Channel:

[0079] The final location for each reference channel is determined by averaging the results of E1 and E2 for each reference channel and assessing the spread of results for each E1 and E2. Such assessment is accomplished by treating the standard deviation of the latitude and longitude calculations as independent and calculating the composite standard deviation σ as a root mean square, as follows:

[0080] σ={square root over (σ_La²+σ_Lo²)}

[0081] The composite standard deviations a for the solutions of reference channels 2 and 3 are:

[0082] The above results are then examined to determine from the sigmas 1 and 2 for each reference channel which of E1 and E2 is the more likely true location of the transmitter corresponding to such reference channel. That is, a smaller sigma indicates a smaller spread of the associated data and therefore a higher reliability in the results of such data. In particular, the results indicate that the location of the reference channel 2 transmitter is most likely E1, which has a sigma 1 less than the sigma 2 of E2, and E1 has the coordinates shown. The most likely location estimate for the reference channel 3 transmitter is E2 with a sigma 2 much less than the sigma 1 of E1.

[0083] It is to be noted that the method of the present invention may be performed manually, although with considerable effort and time required to do so. Of course, such method may also be performed in an automated and faster manner by way of a computer or processor 18 or the like, as is shown in FIG. 1. Such computer or processor 18 may be any appropriate computer or processor without departing from the spirit and scope of the present invention. In fact, the computer 18 may be the recording device/computer 16, which is to say that the method of the present invention may be performed on the computer 16, thus obviating the need for an additional computer to be computer 18. Moreover, the software employed to perform the method on the computer 18 may be any appropriate software, again without departing from the spirit and scope of the present invention. The details of such software are known or should be apparent to the relevant public, and therefore need not be described herein in further detail.

[0084] In the foregoing description, it can be seen that the present invention comprises a new and useful method for estimating the position of one or more transmitter locations based on signals transmitted from such transmitter(s). It should be appreciated that changes could be made to the embodiments described above without departing from the inventive concepts thereof. It should be understood, therefore, that this invention is not limited to the particular embodiments disclosed, but it is intended to cover modifications within the spirit and scope of the present invention as defined by the appended claims.