US20140266912A1 - Directional pruning of transmitters to improve position determination - Google Patents

Abstract

Described are systems and methods for identifying transmitters that adversely affect a trilateration result.

Description

CROSS REFERENCE TO RELATED APPLICATIONS
• This application claims priority under 35 U.S.C. §119(e) to co-pending U.S. Provisional Patent Application Ser. No. 61/786,556, filed Mar. 15, 2013, entitled DIRECTIONAL PRUNING OF TRANSMITTERS To IMPROVE POSITION DETERMINATION, the content of which is hereby incorporated by reference herein in its entirety for all purposes.
FIELD
• Various embodiments relate selecting transmitters in a way to improve trilateration performance.
BACKGROUND
• There is a need for improved techniques for improving trilateration results based on analysis of transmitters.
SUMMARY
• Certain embodiments of this disclosure relate generally to removing transmitters that adversely affect a trilateration result.
DRAWINGS
• FIG. 1A depicts aspects of a terrestrial positioning system.
• FIG. 1B depicts two sets of transmitters in a terrestrial positioning system.
• FIG. 2A depicts equal numbers of transmitters in different regions.
• FIG. 2B depicts different regions of unequal numbers of transmitters.
• FIG. 3 illustrates a process for pruning transmitters.
• FIG. 4A andFIG. 4B illustrate how division of transmitters may be carried out.
DESCRIPTION
• Various aspects of the invention are described below. It should be apparent that the teachings herein may be embodied in a wide variety of forms and that any specific structure, function, or both, being disclosed herein is merely representative. Based on the teachings herein one skilled in the art should appreciate that any aspect disclosed may be implemented independently of any other aspects and that two or more of these aspects may be combined in various ways. For example, a system may be implemented or a method may be practiced using any number of the aspects set forth herein.
• As used herein, the term “exemplary” means serving as an example, instance or illustration. Any aspect and/or embodiment described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects and/or embodiments.
• In the following description, numerous specific details are introduced to provide a thorough understanding of, and enabling description for, the systems and methods described. One skilled in the relevant art, however, will recognize that these embodiments can be practiced without one or more of the specific details, or with other components, systems, and the like. In other instances, well-known structures or operations are not shown, or are not described in detail, to avoid obscuring aspects of the disclosed embodiments.
Overview
• Various aspects, features, and functions are described below in conjunction with the appended Drawings. While the details of the embodiments of the invention may vary and still be within the scope of the claimed invention, one of skill in the art will appreciate that the Drawings described herein are not intended to suggest any limitation as to the scope of use or functionality of the inventive aspects. Neither should the Drawings and their description be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in those Drawings.
• Aspects of the disclosure generally relate to positioning systems with satellites and/or terrestrial transmitters positioned at various locations. By way of example,FIG. 1A depicts apositioning system100A that includes a plurality oftransmitters110 and areceiver120. “Range”signals115 transmitted from each of thetransmitters110 may be collected by thereceiver120, and later used to estimate thereceiver120's position relative to the position oftransmitters110. The process of estimating areceiver120's position is often referred to as “trilateration”, which is the process of using geometry to determine a location of an intersection point where transmitted signals from known locations of transmitters converge, where each signal specifies a distance from the respective transmitter to the intersection point.
• In order to precisely determine the location of the intersection point, signals must specify accurate distance measurements. In “time-of-arrival” positioning systems, a signal's travel time can be measured and converted to a distance or “range” using the speed of light. Unfortunately, positing systems like thesystem100A shown inFIG. 1A are often built in urban environments where buildings and other obstructions block “range” or “pseudorange” signals, and then reflect those range signals in a manner so that their overall travel time is increased, which results in inaccurate distance measurements. Inaccurate distance measurements, along with other characteristics are often undesirable because they adversely affect the estimate of a receiver's position after trilateration processing. Accordingly, it is often desirable to identify inaccurate range signal measurements, and then filter or “prune” those measurements during trilateration processing (e.g., by removing the measurements or adjusting the measurements to decrease their effect on the trilateration result).
• However, pruning transmitter range signal measurements that exhibit undesirable characteristics may result in a remaining set of range signal measurements from respective transmitters that exhibits poor relative transmitter-receiver geometry, which ultimately impairs the precision of position measurements with respect to any of latitude, longitude, altitude and time (x, y, z, t).
• FIG. 1B illustrates asystem100B with such aremaining set111aof transmitters after anotherset111bof transmitters has been pruned from trilateration processing. As shown, transmitter set111aincludes transmitters that are clustered around each other in generally the same radial direction from thereceiver120. Ideally, trilateration processing would use range signal measurements fromtransmitters110 that are collectively distributed around the receiver120 (as shown inFIG. 1A) as compared to a group oftransmitters111athat lacks such distribution around the receiver120 (as shown inFIG. 1B). This is because using onlytransmitter set111aprovides geometric position error referred to as “dilution of precision” (DOP), which refers to uneven distribution of transmitters with respect to a receiver.
• Accordingly, other approaches are needed to avoid “over pruning” of range signal measurements. One such approach, as illustrated byFIGS. 2A-2B, identifiestransmitters110 of atransmitter system200 for inclusion into different transmitter sets211a-nbased on transmitter regions. Each transmitter set211 may then be individually analyzed to select the best range signals from that transmitter set211. Division oftransmitters110 into transmitter sets211 may be accomplished using various techniques, including dividing based on the general radial direction of eachtransmitter110 from the current estimated location of thereceiver120.
• Another approach may involve firmware-based or software-based calculations of DOP with all transmitters except a candidate transmitter. However, consideration of many candidate transmitters can lead to a computationally complex load that increases time to first fix (TTIF).
Methodologies
• As discussed above, in order to improve trilateration performance, transmitters that adversely affect the trilateration result (i.e. the position estimate) may be removed or devalued. One way of achieving this is to remove transmitters that are “bad” according to some metric (e.g. estimated range error, estimated distance to receiver, weight applied to range measurement, and other metrics, or a combination of these metrics). However, as previously noted, if we simply remove transmitters that have an undesired metric among all visible transmitters, the remaining set of transmitters that exhibit good metrics may result in poor Dilution of Precision (DOP) at the receiver location, which will adversely affect the position estimate after trilateration.
• Accordingly, candidate transmitters that adversely affect the trilateration result may be identified and removed in such a way as to ensure a reasonable DOP after those candidate transmitters are removed. One approach involves removing one of a sub-set of candidate transmitters to avoid removing all candidate transmitters that are positioned in the same general radial direction from an estimated position of a receiver. By way of example, the area around an estimated position of the receiver may be divided into N transmitter “regions” (e.g., 4 quadrants, 8 half-quadrants, or non-uniform division depending on density of transmitters). Transmitters in each region may then be analyzed to identify poorer performing transmitters, or conversely, better performing transmitters. A minimum number of transmitters may be selected as the better performing transmitters (e.g., 1 or 2 transmitters from each region). It is further contemplated that only a subset of transmitters may be divided into regions for pruning, where another subset of transmitters that exhibit preferred characteristics may not be pruned.
• Attention is drawn toFIG. 3, which illustrates amethodology300 for identifying poorer performing transmitters using transmitter regions that define a set of transmitters (e.g., transmitter sets211 ofFIGS. 2A-B).
• AtStep310, transmitters are divided into transmitter sets (e.g., based on radial regions).FIG. 4A andFIG. 4B illustrate how division of transmitters may be carried out. As shown, the number of regions may be 8 (as depicted by the rectangles), while the number of transmitters per region may be 2 (as depicted by different clusters of dots within each rectangle). By comparison, the number of transmitters in a region may not be fixed, where two transmitter sets may have two transmitters, while another transmitter set may have three transmitters. For example, one way of determining the number of transmitters in a region may involve usage of terrain and building map obstruction information in the direction of a transmitter region from the approximate receiver location in such a way that regions that have a lot of terrain or building clutter may have a lesser number of transmitters or a greater number of transmitters.
• InFIG. 4A, for example, the two charted measurements designated by410(a)(i) (e.g., the lighter dots) may relate to one transmitter of aregion411athat is “in view” of thereceiver120, while the charted measurement designated by410(a)(ii) (e.g., the darker dots) may relate to another transmitter of theregion411athat is “in view” of thereceiver120. Inregion411b, no transmitters are “in view” of thereceiver120, and there are consequently no measurements shown. Inregion411c, only one transmitter is “in view” of thereceiver120.
• Atstep320, a pruning metric is calculated. The overall metric used to determine which transmitters to prune may include a combination of the following sub-metrics: estimated range error (e.g., the smaller the range error, the better the transmitter); trilateration weight, which results from an estimate of ranging error standard deviation (e.g., the higher the weight the better the transmitter (lower estimated ranging error standard deviation)); range quality metric (e.g., the range quality metric may be determined using terrain and/or building map information in the direction of the transmitters or from the set of range measurements or signals themselves); estimated distance to transmitter (e.g., it is possible that the smaller the distance to the transmitter, the better the transmitter (less likelihood of multipath)); angle of incidence of transmitter (e.g., the higher the angle of incidence from a transmitter, the better the transmitter (less likelihood of multipath)); and others. A resultant pruning metric may be a function of any sub-metric, where the function is some function that takes in a set of sub-metrics and calculates a final metric that can be used for pruning some of the transmitters.
• One example of a pruning metric would be:
• 
  pruning_metric=Σ_k=1-nalpha[k]*sub_metric[k],
• where alpha[k] is a positive or negative “weight” associated with a particular sub-metric depending on the nature of the k^thsub-metric and whether it makes the transmitter more or less desirable, among other considerations.
• AtStep330, sets of transmitters are sorted and pruned so the a selected subset exhibits better trilateration performance. Step320 may result in an array of pruning metrics, where each pruning metric corresponds to one transmitter in a given region. Transmitters may be sorted based on their pruning metrics, and one or more transmitters with the least preferred pruning metric may pruned. Transmitters with more preferred pruning metrics may then be used during trilateration processing.
• As previously described, certain aspects relate to creating radial sections (e.g., that are equal in number of degrees) around the estimated receiver location, and then, for each section, pick the best M transmitters, where “best” can be defined by any number of metrics. One of the metrics can be the density of terrain and manmade objects in the direction of a particular transmitter.
• The number of transmitters in each radial direction may be a factor of geometry (i.e. where the receiver is and where the transmitters are), so that in one particular receiver location there may be many transmitters in one quadrant (e.g., anortheast quadrant211cofFIG. 2B) and few transmitters in another quadrant (e.g., anorthwest quadrant211dofFIG. 2B). Thus, the number of transmitters in each direction is somewhat fixed to division of quadrants or other types of regions or areas where transmitters reside with respect to the estimated position. Then, at least M transmitters in each such region may need to be selected to avoid poor DOP characteristics.
• For example, if M is 2, and one direction has 8 transmitters, the best2 transmitters may be selected, or at least two transmitters may be selected where others are pruned. Where regions have less than M transmitters, each transmitter in that region may be selected without pruning.
• Regions may be based on the number of radial directions (e.g., ranges of azimuth angles with respect to an estimated receiver position as indicated by211c,211a,211band211dofFIG. 2B, which show azimuth ranges of 0 to 90°, 90 to 180°, 180 to 270° and 270 to 360°), or other configurations (e.g., as shown inFIG. 2A). The number of regions, the number of transmitters (e.g., the value of M, which may depend on the number of transmitters per region), and the metrics may be used to determine the quality of the transmitter with respect to a candidate position estimate.
Algorithms
• The following sample code describes various approaches associated with various aspects disclosed herein.

• function [new_pranges, new_weights, new_tx_enu, new_tx_idx] = prune_txs(pranges, weights,
  tx_enu, rx_enu_hat, prune_method, settings)
  % This function attempts to prune Tx's so that the remaining set of Tx's has better
  % trilateration performance
  % The first prune_method implemented is a radial pruning, i.e. dividing the area around
  % the rx_enu_hat into ″slices″ (e.g. quadrants) and selecting a certain subset from each slice
  % More prune_method's can be implemented in the future.
  %
  % Usage:
  % prune_method = 0;
  % settings = struct(′num_slices′,8, ′max_num_tx_per_slice′, 2);
  % [new_pranges, new_weights, new_tx_enu, new_tx_idx] =

  %	prune_txs(pranges, weights, tx_enu, rx_enu_hat, prune_method, settings);

  %

  % new_pranges, new_weights, and new_tx_enu can now be used to trilaterate

  % Also, new_tx_idx can be used to find out the names of the remaining Tx's:

  %	new_tx_names = tx_names(new_tx_idx);

  %

  % More complex usage:

  % prune_method = 0;

  % settings = struct(′num_slices′,8, ′max_num_tx_per_slice′, 2, ′alpha′,[1 −0.2 0.1 −0.1]);

  % [new_pranges, new_weights, new_tx_enu, new_tx_idx] =

  %	prune_txs(pranges, weights, tx_enu, rx_enu_hat, prune_method, settings);

  prune_method = input_arg_check(′prune_method′, 0);

  settings = input_arg_check(′settings′, struct(′num_slices′,8, ′max_num_tx_per_slice′, 2,

  ′alpha′,[1 0 0 0]));

  if ~isfield(settings,′alpha′)

  settings.alpha = [1 0 0 0];

  end

  if ~isfield(settings,′min_num_total_tx′)

  settings.min_num_total_tx = 4;

  end

  if prune_method == 0

  num_slices

  = settings.num_slices;

  max_num_tx_per_slice = settings.max_num_tx_per_slice;

  alpha

  = settings.alpha;

  min_num_total_tx = settings.min_num_total_tx;

  end

  num_tx

  = size(tx_enu,1);

  switch prune_method

  	% ------------------------------------------------------------------------
  	case 0

  	slices = linspace(0,360,num_slices+1);
  	theta = atan2(tx_enu(:,2) − rx_enu_hat(2), tx_enu(:,1) − rx_enu_hat(1))*180/pi;
  	theta(theta<0) = theta(theta<0) + 360;
  	rx_tx_distance_hat = distance(tx_enu, repmat(rx_enu_hat, num_tx,1), 2)′;
  	pranges_adj = pranges − rx_tx_distance_hat;
  	phi = atan2(tx_enu(:,3) − rx_enu_hat(3), sqrt((tx_enu(:,1)−rx_enu_hat(1)).{circumflex over ( )}2 + (tx_enu(:,2)−

  rx_enu_hat(2)).{circumflex over ( )}2))′*180/pi;

  	new_pranges = [ ] ;
  	new_weights = [ ];
  	new_tx_enu = [ ];
  	new_tx_idx = [ ];
  	num_tx_per_slice = zeros(1,num_slices);
  	for Is=1:num_slices

  idx = find((theta >= slices(Is) & theta < slices(Is+1)) & (weights′ ~= 0) & (pranges_adj′ >

  median(pranges_adj) −1e3));

  num_tx_per_slice(Is) = length(idx);

  	end
  	if isnan(max_num_tx_per_slice)

  max_num_tx_per_slice = ceil(median(num_tx_per_slice));

  	end
  	% Ensure that the total number of remaining Tx's (after pruning) is >= min_num_total_tx (e.g.

  4)

  if ~isnan(min_num_total_tx)

  if sum(num_tx_per_slice) >= min_num_total_tx

  while sum(min(num_tx_per_slice,max_num_tx_per_slice)) < min_num_total_tx,

  max_num_tx_per_slice = max_num_tx_per_slice+1;

  end

  end

  	end
  	for Is=1:num_slices

  idx = find((theta >= slices(Is) & theta < slices(Is+1)) & (weights′ ~= 0) & (pranges_adj′ >

  median(pranges_adj) −1e3));

  if ~isempty(idx)

  	pranges_adj_tmp = pranges_adj(idx);
  	[junk,idxidx] = sort(alpha(1)*pranges_adj_tmp + alpha(2)*weights(idx) +

  alpha(3)*rx_tx_distance_hat(idx) + alpha(4)*phi(idx));

  if max_num_tx_per_slice > 0

  idx_select = idxidx(1:min(max_num_tx_per_slice,length(idxidx)));

  else

  idx_select = idxidx(1:max(length(idxidx)−abs(max_num_tx_per_slice),

  min(2,length(idxidx))));

  end

  else

  	pranges_adj_tmp = [ ];
  	idx_select = [ ];

  	end
  	new_pranges = [new_pranges pranges(idx(idx_select))];
  	new_weights = [new_weights weights(idx(idx_select))];
  	new_tx_enu = [new_tx_enu; tx_enu(idx(idx_select),:)];
  	new_tx_idx = [new_tx_idx idx(idx_select)′];

  end

  otherwise

  error(′Unsupported value for prune_method′)

  end

Supporting Aspects
• Various aspects relate to disclosures of other patent applications, patent publications, or issued patents. For example, each of the following applications, publications, and patents are incorporated by reference in their entirety for any and all purposes: United States Utility patent application Ser. No. 13/412,487, entitled WIDE AREA POSITIONING SYSTEMS, filed on Mar. 5, 2012; U.S. Utility patent Ser. No. 12/557,479 (now U.S. Pat. No. 8,130,141), entitled WIDE AREA POSITIONING SYSTEM, filed Sep. 10, 2009; United States Utility patent application Ser. No. 13/412,508, entitled WIDE AREA POSITIONING SYSTEM, filed Mar. 5, 2012; United States Utility patent application Ser. No. 13/296,067, entitled WIDE AREA POSITIONING SYSTEMS, filed Nov. 14, 2011; Application Serial No. PCT/US12/44452, entitled WIDE AREA POSITIONING SYSTEMS (WAPS), filed Jun. 28, 2011); U.S. patent application Ser. No. 13/535,626, entitled CODING IN WIDE AREA POSITIONING SYSTEMS (WAPS), filed Jun. 28, 2012; U.S. patent application Ser. No. 13/565,732, entitled CELL ORGANIZATION AND TRANSMISSION SCHEMES IN A WIDE AREA POSITIONING SYSTEM (WAPS), filed Aug. 2, 2012; U.S. patent application Ser. No. 13/565,723, entitled CELL ORGANIZATION AND TRANSMISSION SCHEMES IN A WIDE AREA POSITIONING SYSTEM (WAPS), filed Aug. 2, 2012; U.S. patent application Ser. No. 13/831,740, entitled SYSTEMS AND METHODS CONFIGURED TO ESTIMATE RECEIVER POSITION USING TIMING DATA ASSOCIATED WITH REFERENCE LOCATIONS IN THREE-DIMENSIONAL SPACE, filed Mar. 14, 2013. The above applications, publications and patents may be individually or collectively referred to herein as “incorporated reference(s)”, “incorporated application(s)”, “incorporated publication(s)”, “incorporated patent(s)” or otherwise designated. The various aspect, details, devices, systems, and methods disclosed herein may be combined with disclosures in any of the incorporated references in accordance with various embodiments.
• This disclosure relates generally to positioning systems and methods for providing signaling for position determination and determining high accuracy position/location information using a wide area transmitter array of transmitters in communication with receivers such as in cellular phones or other portable devices with processing components, transceiving capabilities, storage, input/output capabilities, and other features.
• Positioning signaling services associated with certain aspects may utilize broadcast-only transmitters that may be configured to transmit encrypted positioning signals. The transmitters (which may also be denoted herein as “towers” or “beacons”) may be configured to operate in an exclusively licensed or shared licensed/unlicensed radio spectrum; however, some embodiments may be implemented to provide signaling in unlicensed shared spectrum. The transmitters may transmit signaling in these various radio bands using novel signaling as is described herein or in the incorporated references. This signaling may be in the form of a proprietary signal configured to provide specific data in a defined format advantageous for location and navigation purposes. For example, the signaling may be structured to be particularly advantageous for operation in obstructed environments, such as where traditional satellite position signaling is attenuated and/or impacted by reflections, multipath, and the like. In addition, the signaling may be configured to provide fast acquisition and position determination times to allow for quick location determination upon device power-on or location activation, reduced power consumption, and/or to provide other advantages.
• The receivers may be in the form of one or more user devices, which may be any of a variety of electronic communication devices configured to receive signaling from the transmitters, as well as optionally be configured to receive GPS or other satellite system signaling, cellular signaling, Wi-Fi signaling, Wi-Max signaling, Bluetooth, Ethernet, and/or other data or information signaling as is known or developed in the art. The receivers may be in the form of a cellular or smart phone, a tablet device, a PDA, a notebook or other computer system, and/or similar or equivalent devices. In some embodiments, the receivers may be a standalone location/positioning device configured solely or primarily to receive signals from the transmitters and determine location/position based at least in part on the received signals. As described herein, receivers may also be denoted herein as “User Equipment” (UE), handsets, smart phones, tablets, and/or simply as a “receiver.”
• The transmitters may be configured to send transmitter output signals to multiple receiver units (e.g., a single receiver unit is shown in certain figures for simplicity; however, a typical system will be configured to support many receiver units within a defined coverage area) via communication links). The transmitters may also be connected to a server system via communication links, and/or may have other communication connections to network infrastructure, such as via wired connections, cellular data connections, Wi-Fi, Wi-Max, or other wireless connections, and the like.
• Various embodiments of a wide area positioning system (WAPS), described herein or in the incorporated references, may be combined with other positioning systems to provide enhanced location and position determination. Alternately, or in addition, a WAPS system may be used to aid other positioning systems. In addition, information determined by receivers of WAPS systems may be provided via other communication network links, such as cellular, Wi-Fi, pager, and the like, to report position and location information to a server system or systems, as well as to other networked systems existing on or coupled to network infrastructure.
• For example, in a cellular network, a cellular backhaul link may be used to provide information from receivers to associated cellular carriers and/or others via network infrastructure. This may be used to quickly and accurately locate the position of receiver during an emergency, or may be used to provide location-based services or other functions from cellular carriers or other network users or systems.
• It is noted that, in the context of this disclosure, a positioning system is one that localizes one or more of latitude, longitude, and altitude coordinates, which may also be described or illustrated in terms of one, two, or three dimensional coordinate systems (e.g., x, y, z coordinates, angular coordinates, vectors, and other notations). In addition, it is noted that whenever the term ‘GPS’ is referred to, it is done so in the broader sense of Global Navigation Satellite Systems (GNSS) which may include other satellite positioning systems such as GLONASS, Galileo and Compass/Beidou. In addition, as noted previously, in some embodiments other positioning systems, such as terrestrially based systems, may be used in addition to or in place of satellite-based positioning systems.
• Embodiments of WAPS include multiple transmitters configured to broadcast WAPS data positioning information, and/or other data or information, in transmitter output signals to the receivers. The positioning signals may be coordinated so as to be synchronized across all transmitters of a particular system or regional coverage area, and may use a disciplined GPS clock source for timing synchronization. WAPS data positioning transmissions may include dedicated communication channel resources (e.g., time, code and/or frequency) to facilitate transmission of data required for trilateration, notification to subscriber/group of subscribers, broadcast of messages, and/or general operation of the WAPS system. Additional disclosure regarding WAPS data positioning transmissions may be found in the incorporated references.
• In a positioning system that uses time difference of arrival or trilateration, the positioning information typically transmitted includes one or more of precision timing sequences and positioning signal data, where the positioning signal data includes the location of transmitters and various timing corrections and other related data or information. In one WAPS embodiment, the data may include additional messages or information such as notification/access control messages for a group of subscribers, general broadcast messages, and/or other data or information related to system operation, users, interfaces with other networks, and other system functions. The positioning signal data may be provided in a number of ways. For example, the positioning signal data may be modulated onto a coded timing sequence, added or overlaid over the timing sequence, and/or concatenated with the timing sequence.
• Data transmission methods and apparatus described herein may be used to provide improved location information throughput for the WAPS. In particular, higher order modulation data may be transmitted as a separate portion of information from pseudo-noise (PN) ranging data. This may be used to allow improved acquisition speed in systems employing CDMA multiplexing, TDMA multiplexing, or a combination of CDMA/TDMA multiplexing. The disclosure herein is illustrated in terms of WAPS in which multiple towers broadcast synchronized positioning signals to UEs and, more particularly, using towers that are terrestrial. However, the embodiments are not so limited, and other systems within the spirit and scope of the disclosure may also be implemented.
• In an exemplary embodiment, a WAPS system uses coded modulation sent from a tower or transmitter, such as transmitter, called spread spectrum modulation or pseudo-noise (PN) modulation, to achieve wide bandwidth. The corresponding receiver unit, such as receiver, includes one or more modules to process such signals using a despreading circuit, such as a matched filter or a series of correlators. Such a receiver produces a waveform which, ideally, has a strong peak surrounded by lower level energy. The time of arrival of the peak represents the time of arrival of the transmitted signal at the receiver. Performing this operation on a multiplicity of signals from a multiplicity of towers, whose locations are accurately known, allows determination of the receivers location via trilateration. Various additional details related to WAPS signal generation in a transmitter, along with received signal processing in a receiver are described herein or in the incorporated references.
• Transmitters may include various blocks for performing associated signal reception and/or processing. For example, a transmitter may include one or more GPS modules for receiving GPS signals and providing location information and/or other data, such as timing data, dilution of precision (DOP) data, or other data or information as may be provided from a GPS or other positioning system, to a processing module. Other modules for receiving satellite or terrestrial signals and providing similar or equivalent output signals, data, or other information may alternately be used in various embodiments. GPS or other timing signals may be used for precision timing operations within transmitters and/or for timing correction across the WAPS system.
• Transmitters may also include one or more transmitter modules (e.g., RF transmission blocks) for generating and sending transmitter output signals as described subsequently herein. A transmitter module may also include various elements as are known or developed in the art for providing output signals to a transmit antenna, such as analog or digital logic and power circuitry, signal processing circuitry, tuning circuitry, buffer and power amplifiers, and the like. Signal processing for generating the output signals may be done in the a processing module which, in some embodiments, may be integrated with another module or, in other embodiments, may be a standalone processing module for performing multiple signal processing and/or other operational functions.
• One or more memories may be coupled with a processing module to provide storage and retrieval of data and/or to provide storage and retrieval of instructions for execution in the processing module. For example, the instructions may be instructions for performing the various processing methods and functions described subsequently herein, such as for determining location information or other information associated with the transmitter, such as local environmental conditions, as well as to generate transmitter output signals to be sent to the user devices.
• Transmitters may further include one or more environmental sensing modules for sensing or determining conditions associated with the transmitter, such as, for example, local pressure, temperature, or other conditions. In an exemplary embodiment, pressure information may be generated in the environmental sensing module and provided to a processing module for integration with other data in transmitter output signals as described subsequently herein. One or more server interface modules may also be included in a transmitter to provide an interface between the transmitter and server systems, and/or to a network infrastructure.
• Receivers may include one or more GPS modules for receiving GPS signals and providing location information and/or other data, such as timing data, dilution of precision (DOP) data, or other data or information as may be provided from a GPS or other positioning system, to a processing module (not shown). Of course, other Global Navigation Satellite Systems (GNSS) are contemplated, and it is to be understood that disclosure relating to GPS may apply to these other systems. Of course, any location processor may be adapted to receive and process position information described herein or in the incorporated references.
• Receivers may also include one or more cellular modules for sending and receiving data or information via a cellular or other data communications system. Alternately, or in addition, receivers may include communications modules for sending and/or receiving data via other wired or wireless communications networks, such as Wi-Fi, Wi-Max, Bluetooth, USB, or other networks.
• Receivers may include one or more position/location modules for receiving signals from terrestrial transmitters, and processing the signals to determine position/location information as described subsequently herein. A position module may be integrated with and/or may share resources such as antennas, RF circuitry, and the like with other modules. For example, a position module and a GPS module may share some or all radio front end (RFE) components and/or processing elements. A processing module may be integrated with and/or share resources with the position module and/or GPS module to determine position/location information and/or perform other processing functions as described herein. Similarly, a cellular module may share RF and/or processing functionality with an RF module and/or processing module. A local area network (LAN) module may also be included.
• One or more memories may be coupled with processing module and other modules to provide storage and retrieval of data and/or to provide storage and retrieval of instructions for execution in the processing module. For example, the instructions may perform the various processing methods and functions described herein or in the incorporated references.
• Receivers may further include one or more environmental sensing modules (e.g., inertial, atmospheric and other sensors) for sensing or determining conditions associated with the receiver, such as, for example, local pressure, temperature, movement, or other conditions, that may be used to determine the location of the receiver. In an exemplary embodiment, pressure information may be generated in such an environmental sensing module for use in determining location/position information in conjunction with received transmitter, GPS, cellular, or other signals.
• Receivers may further include various additional user interface modules, such as a user input module which may be in the form of a keypad, touchscreen display, mouse, or other user interface element. Audio and/or video data or information may be provided on an output module (not shown), such as in the form or one or more speakers or other audio transducers, one or more visual displays, such as touchscreens, and/or other user I/O elements as are known or developed in the art. In an exemplary embodiment, such an output module may be used to visually display determined location/position information based on received transmitter signals, and the determined location/position information may also be sent to a cellular module to an associated carrier or other entity.
• The receiver may include a signal processing block that comprises a digital processing block configured to demodulate the received RF signal from the RF module, and also to estimate time of arrival (TOA) for later use in determining location. The signal processing block may further include a pseudorange generation block and a data processing block. The pseudorange generation block may be configured to generate “raw’ positioning pseudorange data from the estimated TOA, refine the pseudorange data, and to provide that pseudorange data to the position engine, which uses the pseudorange data to determine the location of the receiver. The data processing block may be configured to decode the position information, extract packet data from the position information and perform error correction (e.g., CRC) on the data. A position engine of a receiver may be configured to process the position information (and, in some cases, GPS data, cell data, and/or LAN data) in order to determine the location of the receiver within certain bounds (e.g., accuracy levels, etc.). Once determined, location information may be provided to applications. One of skill in the art will appreciate that the position engine may signify any processor capable of determining location information, including a GPS position engine or other position engine.
Variations of Implementation
• Methods may: identify a first set of two or more transmitters from the network of transmitters; and evaluate the first set of transmitters to determine which transmitters associate with one or more characteristics; and refine the estimated position of the receiver based on the transmitters that exhibit the one or more characteristics.
• In accordance with certain aspects, a first number of transmitters in the first set depends on a density of terrain and manmade objects. In accordance with certain aspects, the first number and the first density are inversely proportional. In accordance with certain aspects, the first number and the first density are proportional.
• Methods may: identify a second set of two or more other transmitters from the network of transmitters. In accordance with certain aspects, the number of transmitters in the first set differs from the number of transmitters in the second set. In accordance with certain aspects, the numbers of transmitters in all sets, including the first set and the second set, are equal.
• In accordance with certain aspects, a first number of transmitters in the first set depends on a first density of terrain and manmade objects near the transmitters in the first set, and a second number of transmitters in the second set depends on a second density of terrain and manmade objects near the transmitters in the second set. In accordance with certain aspects, the first set of transmitters includes transmitters that are within a first transmission region with respect to an estimated position of the receiver. In accordance with certain aspects, the size of the first transmission region is based on a spatial mapping of natural terrain or manmade structures nearby the transmitters of the network.
• Methods may: calculate a first quality metric corresponding to a first transmitter in the first set, wherein the estimated position is refined based on a first range measurement corresponding to the first transmitter when the first quality metric meets a threshold condition.
• Methods may: calculate a first quality metric corresponding to a first transmitter in the first set; and calculate a second quality metric corresponding to a second transmitter in the first set, wherein the estimated position is refined based on a first range measurement corresponding to the first transmitter when the first quality metric is preferred over the second quality metric, and the estimated position is refined based on a second range measurement corresponding to the second transmitter when the second quality metric is preferred over the first quality metric.
• In accordance with certain aspects, the first quality metric is based on a calculation of one or more weighted sub metrics selected from the group consisting of: estimated range error, weight applied to the first range measurement during trilateration, estimated distance between the estimated position and the first transmitter, quantification of probable multipath effect associated with obstructions in the direction of the first transmitter from the estimated position; and angle of incidence of first transmitter. In accordance with certain aspects, only a subset of transmitters from the first set of transmitters associate with the one or more characteristics.
• In accordance with certain aspects, the one or more characteristics include one or more of low estimated range error, high weight applied to range measurement of the respective transmitters during trilateration, shorter estimated distance between the estimated position and the respective transmitter with respect to estimated distances for other transmitters, low estimated multipath effect associated with obstructions in the direction of the respective transmitter from the estimated position, and high angle of incidence of the respective transmitter.
• The various components, modules, and functions described herein can be located together or in separate locations. Communication paths couple the components and include any medium for communicating or transferring files among the components. The communication paths include wireless connections, wired connections, and hybrid wireless/wired connections. The communication paths also include couplings or connections to networks including local area networks (LANs), metropolitan area networks (MANs), wide area networks (WANs), proprietary networks, interoffice or backend networks, and the Internet. Furthermore, the communication paths include removable fixed mediums like floppy disks, hard disk drives, and CD-ROM disks, as well as flash RAM, Universal Serial Bus (USB) connections, RS-232 connections, telephone lines, buses, and electronic mail messages.
• Aspects of the systems and methods described herein may be implemented as functionality programmed into any of a variety of circuitry, including programmable logic devices (PLDs), such as field programmable gate arrays (FPGAs), programmable array logic (PAL) devices, electrically programmable logic and memory devices and standard cell-based devices, as well as application specific integrated circuits (ASICs). Some other possibilities for implementing aspects of the systems and methods include: microcontrollers with memory (such as electronically erasable programmable read only memory (EEPROM)), embedded microprocessors, firmware, software, etc. Furthermore, aspects of the systems and methods may be embodied in microprocessors having software-based circuit emulation, discrete logic (sequential and combinatorial), custom devices, fuzzy (neural) logic, quantum devices, and hybrids of any of the above device types. The underlying device technologies may be provided in a variety of component types, e.g., metal-oxide semiconductor field-effect transistor (MOSFET) technologies like complementary metal-oxide semiconductor (CMOS), bipolar technologies like emitter-coupled logic (ECL), polymer technologies (e.g., silicon-conjugated polymer and metal-conjugated polymer-metal structures), mixed analog and digital, etc.
• It should be noted that any system, method, and/or other components disclosed herein may be described using computer aided design tools and expressed (or represented), as data and/or instructions embodied in various computer-readable media, in terms of their behavioral, register transfer, logic component, transistor, layout geometries, and/or other characteristics. Computer-readable media in which such formatted data and/or instructions may be embodied include, but are not limited to, non-volatile storage media in various forms (e.g., optical, magnetic or semiconductor storage media) and carrier waves that may be used to transfer such formatted data and/or instructions through wireless, optical, or wired signaling media or any combination thereof. Examples of transfers of such formatted data and/or instructions by carrier waves include, but are not limited to, transfers (uploads, downloads, e-mail, etc.) over the Internet and/or other computer networks via one or more data transfer protocols (e.g., HTTP, HTTPs, FTP, SMTP, WAP, etc.). When received within a computer system via one or more computer-readable media, such data and/or instruction-based expressions of the above described components may be processed by a processing entity (e.g., one or more processors) within the computer system in conjunction with execution of one or more other computer programs.
• Unless the context clearly requires otherwise, throughout the description and the claims, the words “comprise,” “comprising,” and the like are to be construed in an inclusive sense as opposed to an exclusive or exhaustive sense; that is to say, in a sense of “including, but not limited to.” Words using the singular or plural number also include the plural or singular number respectively. Additionally, the words “herein,” “hereunder,” “above,” “below,” and words of similar import, when used in this application, refer to this application as a whole and not to any particular portions of this application. When the word “or” is used in reference to a list of two or more items, that word covers all of the following interpretations of the word: any of the items in the list, all of the items in the list and any combination of the items in the list.
• The above description of embodiments of the systems and methods is not intended to be exhaustive or to limit the systems and methods to the precise forms disclosed. While specific embodiments of, and examples for, the systems and methods are described herein for illustrative purposes, various equivalent modifications are possible within the scope of the systems and methods, as those skilled in the relevant art will recognize. The teachings of the systems and methods provided herein can be applied to other systems and methods, not only for the systems and methods described above. The elements and acts of the various embodiments described above can be combined to provide further embodiments. These and other changes can be made to the systems and methods in light of the above detailed description.
• One of skill in the art will appreciate that the processes shown in the Drawings and described herein are illustrative, and that there is no intention to limit this disclosure to the order of stages shown. Accordingly, stages may be removed and rearranged, and additional stages that are not illustrated may be carried out within the scope and spirit of the invention.
• In one or more exemplary embodiments, the functions, methods and processes described may be implemented in whole or in part in hardware, software, firmware, or any combination thereof. If implemented in software, the functions may be stored on or encoded as one or more instructions or code on a computer-readable medium. Computer-readable media includes computer storage media. Storage media may be any available media that can be accessed by a computer.
• By way of example, and not limitation, such computer-readable media can include RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disk and disc, as used herein, includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk and Blu-ray disc where disks usually reproduce data magnetically, while discs reproduce data optically with lasers. Combinations of the above should also be included within the scope of computer-readable media.
• Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.
• Those of skill in the art would further appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the disclosure.
• The various illustrative logical blocks, modules, processes, and circuits described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.
• The steps or stages of a method, process or algorithm in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.
• The claims are not intended to be limited to the aspects shown herein, but is to be accorded the full scope consistent with the language of the claims, wherein reference to an element in the singular is not intended to mean “one and only one” unless specifically so stated, but rather “one or more.” Unless specifically stated otherwise, the term “some” refers to one or more. A phrase referring to “at least one of” a list of items refers to any combination of those items, including single members. As an example, “at least one of: a, b, or c” is intended to cover: a; b; c; a and b; a and c; b and c; and a, b and c.
• The previous description of the disclosed aspects is provided to enable any person skilled in the art to make or use the present disclosure. Various modifications to these aspects will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects without departing from the spirit or scope of the disclosure. Thus, the disclosure is not intended to be limited to the aspects shown herein but is to be accorded the widest scope consistent with the appended claims and their equivalents.
• As used herein, computer program products comprising computer-readable media including all forms of computer-readable medium except, to the extent that such media is deemed to be non-statutory, transitory propagating signals.
• While various embodiments of the present invention have been described in detail, it may be apparent to those skilled in the art that the present invention can be embodied in various other forms not specifically described herein. Therefore, the protection afforded the present invention should only be limited in accordance with the following claims.

Claims (13)

1. A method for estimating a position of a receiver using a network of transmitters, the method comprising:

identifying a set of transmitters from the network of transmitters;

associating each transmitter from the set of transmitters with at least one of three or more groups of transmitters based on geographic information associated with of that transmitter; and

determining an estimated position of the receiver using at least one range measurement corresponding to at least one transmitter in each of the three or more groups that includes a transmitter from the set of transmitters.

2. The method ofclaim 1, wherein the geographic information associated with include an estimated azimuth relating to a location of the transmitter.

3. The method ofclaim 2, wherein each of the three or more groups corresponds to a different range of azimuths, and each transmitter is associated with a particular group of the three or more groups when the azimuth relating to that transmitter falls within the range of azimuths corresponding to that particular group.

4. The method ofclaim 1, wherein the geographic information associated with include a location of the transmitter.

5. The method ofclaim 4, wherein each of the three or more groups corresponds to a different geographic region, and each transmitter is associated with a particular group of the three or more groups when the location relating to that transmitter falls within the geographic region corresponding to that particular group.

6. The method ofclaim 1, wherein each of the three or more groups corresponds to a different geographic region in the network of transmitters.

7. The method ofclaim 1, the method comprising:

determining, for each of the three or more groups, the number of transmitters associated with each group;

determining, when the number is less than the integer M, the estimated position using range measurements corresponding to each of the transmitters in that group; and

determining, when the number is equal to or greater than an integer M, the estimated position using at least M range measurements corresponding to at least M of the transmitters in that group.

8. The method ofclaim 1, the method comprising:

determining, for each of the three or more groups, the number of transmitters associated with each group;

determining, when the number is equal to or less than an integer M, the estimated position using range measurements corresponding to each of the transmitters in that group; and

determining, when the number is greater than the integer M, the estimated position using a selection of M range measurements corresponding to a selection of M transmitters in that group, wherein a value of a quality metric for each of the M transmitters is at least equal to each value of the quality metric for the unselected transmitters in that group.

9. The method ofclaim 8, wherein each value of the quality metric relates to at least one of: an estimated range error related to that transmitter; a trilateration weight related to that transmitter; an estimated distance between the transmitter and an initial estimate of the receiver's position; and an angle of incidence related to that transmitter.

10. The method ofclaim 1, wherein the method comprises:

identifying one or more preferred transmitters with a value of a quality metric that is above a threshold level of the quality metric; and

determining the estimated position of the receiver using a range measurement corresponding to a preferred transmitter from each of the three or more groups that includes at least one of the preferred transmitters.

11. The method ofclaim 10, wherein the method comprises:

identifying each non-preferred transmitter with a value of the quality metric that is below the threshold level of the quality metric, wherein the estimated position of the receiver is determined without using range measurements corresponding to any of the non-preferred transmitters from each of the three or more groups that includes at least one of the preferred transmitters.

12. A system comprising one or more processors that perform the method ofclaim 1.

13. A non-transitory machine-readable medium embodying program instructions adapted to be executed to implement the method ofclaim 1.

Images