Reconfigurable geolocation system

Technical Field

The present invention relates to global positioning systems, and more particularly to apparatus and methods for providing a reconfigurable geolocation system.

Background Art

One of the most hazardous jobs firefighters and other emergency personnel must do is to enter a burning building. In this situation, the building floor plan may be unknown (and may change), visibility is impaired, and the locations of equipment and personnel may change. Combining this situation with a limited air supply and potentially obstructed escape paths results in an extremely dangerous environment.

In such an environment, there are strict limits on the amount of time a firefighter may be inside a burning building due to limitations imposed by the limited air supply and on increasing fire and smoke intensity. Additional challenges result as a consequence of the complete or partial failing of the building, which may result in the destruction of escape paths.

Pseudo-satellites, or pseudolites, are commonly known in the art as devices which transmit a GPS, or GPS-type signal, but which are located in relatively close proximity to the ground. When using pseudolites to provide navigation in an indoor, underground or obstructed environment, there is a concern that nearby pseudolites will negatively impact the ability of a receiver to track all of the available pseudolites. This problem, known as the "near-far" problem, is a consequence of limited dynamic range. Some techniques for solving this problem, such as modifying the pseudolite duty cycle or synchronizing the pseudolite transmissions have been previously proposed.

A system for locating emergency personnel in a building has been discussed in "A System of Tracking and Locating Emergency Personnel Inside Buildings" presented by Progri et al. at the Institute of Navigation (ION GPS 2000, 19-22 September 2000, pp. 560-568). Similarly, techniques for dealing with the "near-far" problem have been discussed in "Techniques for Reducing the Near-Far Problem in Indoor Geolocation Systems" presented by Hill et al., at the Institute of Navigation (ION NTM 2001, 22-24 January 2001, pp. 860-865). The above referenced publications and presentations are hereby incorporated herein, in their entirety, by reference.

WO 99/63358 discloses a positioning system which utilizes a network of self-integrating positioning devices synchronized to a Global Navigation Satellite System. The positioning system uses GPS signals to determine the position of the devices, even in an indoor environment. Determination of absolute and relative position of the positioning devices is effected using a network of positioning devices synchronized to signals provided by a Global Navigation Satellite System. The signals of the system of are modulated upon two Course/Acquisition codes which must be received from the GPS satellites.

In "Relative Location in Wireless Networks", IEEE, Patwari et al disclose a maximum likelihood method to calculate device locations given pair-wise received power measurements and reference device coordinates. Reference devices are positioned in set places within an area and blindfolded devices are positioned randomly within the area. Received power is randomly generated for the devices and a processor guesses the initial coordinates for each blindfolded device. The system estimates the range between blindfolded devices and reference devices based on the generated power and if a blindfolded devices is not in the range of at least 3 reference devices, the system generates a random guess. A conjugate gradient algorithm finds a maximum in a likelihood function and locations estimates are compared with actual locations.

Summary of the Invention

The invention is defined by the appended claims.

In accordance with an embodiment of the invention, a portable reconfigurable indoor geolocation system includes at least three portable pseudolite nodes in communication with one another. Each of the pseudolite nodes comprises a transmitter, a receiver for receiving and demodulating the signals transmitted between the nodes and a processor for receiving the demodulated signals, extracting data values and derived values from the demodulated signals. The system also includes at least two portable user nodes, each of the user nodes being in communication with each other and with the pseudolite nodes. Each user node has a user interface and at least one of the user nodes is at a known location. Each user node further includes a transmitter, a receiver for receiving and demodulating the signals transmitted between the nodes an a processor for receiving the demodulated signals, extracting data values and derived values from the demodulated signals. Each of the pseudolite node and user node transmitters generates a signal on one or more carrier frequencies, each signal being modulated by at least three pseudo random codes necessary to establish distances between the nodes and to convey data between the nodes and each of the pseudolite node and user node processors determines a three dimensional position of each node in the system.

In accordance with a related embodiment, communication between the nodes may be wireless. In accordance with another related embodiment, the at least three pseudo random codes may include at least two digital signals, and the at least two digital signals may establish at least two communication channels that are substantially orthogonal to one another. In accordance with other related embodiments, at least one signal generated by the nodes may be modulated by a short pseudo random code to provide signal selection for a particular signal frequency and/or a long pseudo random code to provide interference resistance. At least one signal generated by the nodes may also be modulated by a s pseudo random code which is identical for every signal to provide bit synchronization resolution. The processor may optimize ranging and communications topology of the system by modulating signals by a code sequence and/or the processor may verifys the integrity of information transmitted in the system by encoding the signals such that transmission errors may be detected. The processor may further provide dynamic reconfiguration of the system in the event of node failure by providing communication between the nodes.

In accordance with another embodiment of the invention, a method of locating a communication node in an indoor area includes distributing a plurality of portable pseudolite nodes within the area, each of the nodes including a transmitter that generates a signal on one or more carrier frequencies, a receiver and a processor. A signal from a first portable user node is generated, the first user node being at a known location and including a transmitter that generates a signal on one or more frequencies, a receiver, a processor and a user interface. Signals generated by by the nodes are modulated by at least three pseudo random codes to enable communication between the nodes and to convey data between the nodes and a relative three-dimensional position of each of the nodes is determined using the modulated signals.

In accordance with a related embodiment, modulating signals generated by the nodes may include establishing at least two communication channels that are substantially orthogonal to one another. In accordance with another related embodiment, establishing communication between the nodes may include establishing wireless communication between the nodes. Modulating signals generated by the nodes may include modulating the signals by at least two digital signals. In accordance with other related embodiment, Modulating signals generated by the nodes may include modulating the signals by a short pseudo random code to provide signal selection for a particular signal frequency and/or by a long pseudo random code to provide interference resistance. Modulating signals generated by the nodes may also include modulating the signals by a pseudo random code that is identical for every signal to provide bit synchronization resolution.

In accordance with yet another related embodiment, the method may include providing a human with a-second portable user node, the second user node including a transmitter that generates a signal on one or more carrier frequencies, a receiver, a processor and a user interface. Signals generated by first user node, the second user node and the pseudolite nodes are modulated by at least three pseudo random codes to establish communication among the first and second user nodes and the pseudolite nodes and to convey data among the first and second user nodes and pseudolite nodes. A relative position of the human is determined using the relative position of the first and second user nodes and the pseudolite nodes. Providing the human with second user node may include providing the human with a-user node that includes an input/output device.

In accordance with a further embodiment of the invention, a portable node includes a transmitter that generates a signal on one or more carrier frequencies, each signal being modulated by at least three pseudo random codes necessary to establish distances between a plurality of nodes and to convey data between the nodes and a receiver for receiving a signal from a user node at a known location and demodulating the signals transmitted between the nodes. A processor receives the demodulated signals, extracts data values and derived values from the demodulated signals and determines a three-dimensional position of each node in the system. In accordance with related embodiments, the portable node may also include a user interface and/or an input/output device.

Brief Description of the Drawings

The foregoing features of the invention will be more readily understood by reference to the following detailed description, taken with reference to the accompanying drawings, in which: <ul id="ul0001" list-style="none" compact="compact"><li>Fig. 1 is a block diagram illustrating a reconfigurable geolocation system in accordance with an embodiment of the invention;</li><li>Fig. 2 is a block diagram illustrating a pseudolite node of the reconfigurable geolocation system of Fig. 1;</li><li>Fig. 3 is a flowchart illustration a method for locating the position of a communication node in an area in accordance with another embodiment of the invention; and</li><li>Fig. 4 is a flow chart illustrating a method for locating a human in an area in accordance with a further embodiment of the invention.</li></ul>

Detailed Description of Specific Embodiments

The present invention provides users with the ability to accurately navigate in environments where access signals from the Global Positioning System is unavailable and where radio navigation aids are either unavailable or of insufficient accuracy and/or reliability.

In Fig. 1 is shown a block diagram illustrating a portable reconfigurable geolocation system in accordance with an embodiment of the invention. The system <b>100</b> employs a plurality of portable pseudolite nodes <b>102</b> as well as one or more portable user nodes <b>104.</b> The user nodes <b>104</b> may be identical to the pseudolite nodes <b>102</b> and augmented with an ability to interact in a more sophisticated manner with a user, such as through a user interface and/or data input and output devices.

As shown in Fig. 2 each portable pseudolite node <b>102</b> contains one or more transmitters <b>206</b> and one or more receivers <b>208</b> as well as appropriate antennae and batteries (not shown). Each pseudolite node <b>102</b> also includes a computing element or processor <b>210</b> which performs any necessary data processing, signal processing, and general control operations to support the operation of the node <b>102.</b> Each portable user node <b>104</b> includes one or more transmitters <b>216,</b> one or more receivers <b>218,</b> appropriate antennae and batteries, a processor <b>220,</b> and a user interface <b>222.</b> Each user interface <b>222</b> may be configured for a particular user. For example, the interface <b>222</b> may be part of a hand-held portable device for one user, such as a firefighter or other human being in a building. Similarly, the interface <b>222</b> may be a conventional CRT for a user at a command and control center, and the user node may be provided with other input and output devices <b>224</b> such as keyboard and mouse, modem, monitor, facsimile and/or printer.

Every pseudolite signal is modulated by three known pseudo random codes at a rate commonly known as the chipping rate and the bandwidth of the resulting signal is proportional to the chipping rate. The first pseudo random code is shorter and is used only to select the appropriate signal from a given channel. The second pseudo random code is identical for every signal and it is used to resolve the bit synchronization and, at the same time, to improve the signal auto-correlation properties. The third pseudo random code is much longer and provides better jammer/interference resistance due to its auto-correlation and cross-correlation properties. Examples of apparatuses and methods that may be used to modulate the pseudolite signals are described in co-pending patent application entitled "Adaptive Spatial Temporal Selective Attenuator with Restored Phase" filed on the same day of the present application (June 11, 2003) and bearing attorney docket number 2627/104, which is hereby incorporated by reference.

The transmitted signal is typically modulated in such a way that both an in-phase channel and a quadrature-phase channel are formed. Typically, the code sequences used on the in-phase and quadrature-phase channels are orthogonal or near orthogonal. In general, the data transmitted between nodes <b>102, 104</b> (pseudolite or user) can be modulated on one or the other or both of these channels. Further, the data modulated on the in-phase channel can be different from the data modulated on the quadrature-phase channel. To improve system performance by further increasing the system dynamic range, the transmitted signal can also be modulated by an additional code sequence. Such a code sequence may be applied to resolve bit synchronization and provide timing information on both or either of the in-phase and quadrature-phase channel(s).

The number of channels supported by the transmitters and receivers may or may not be the same as the number of pseudolite nodes <b>102.</b> The only issue associated with the number of channels that are supported is that a sufficient number of channels should be available to avoid any near-far problem that exists in the deployment area. The architecture of each channel is similar to that of an ordinary Global Positioning System receiver, with the exception that every channel must optionally track a different carrier.

Although each pseudolite node <b>102</b> can operate on a single frequency (as is the case with the Global Positioning System), the system <b>100</b> also permits the use of multiple frequencies. Such multiple frequencies would typically be equally spaced by integer multiples of π multiplied by the chipping rate. When multiple frequencies are used, a significant improvement in receiver dynamic range results, which eliminates the so-called "near-far" problem that reduces the effectiveness of single frequency systems.

In accordance with the embodiment of Fig. 1, the pseudolite nodes <b>102</b> are distributed in an ad-hoc manner, the only restriction being that each pseudolite node <b>102</b> must be able to make contact with one or more other pseudolite nodes <b>102</b> in the system <b>100.</b> On initialization, the pseudolite nodes will exchange information to allow them to determine both the achievable connectivity of the network and the distance to each pseudolite node <b>102</b> having a direct communication path. As a result of this information, both the physical configuration and the network paths to each node in the system <b>100</b> can be determined. Using signals received from a known location, the specific geographic location of each pseudolite node <b>102</b> in the system <b>100</b> can be determined using, for example, the same kinds of algorithms which are commonly used in current GPS receivers. A similar process allows determining the location of user node <b>104</b> in the system <b>100.</b>

In accordance with another embodiment, the pseudolite nodes 102 may be arranged in specific locations, eliminating the need to automatically determine the geographic locations and network paths in the system <b>100.</b>

Fig. 3 is a flowchart illustration a method for locating the position of a communication node in an area in accordance with another embodiment of the invention. A plurality of portable nodes are distributed <b>301</b> within the area. Each of the nodes includes a transmitter that generates a signal on one or more carrier frequencies, a receiver, and a processor. In process <b>302,</b> communication between the nodes is established, and signals generated by nodes are modulated <b>303</b> with signals necessary to establish distances between the nodes and to convey data between the nodes. A three-dimensional position of each of the nodes is determined <b>304</b> using the modulated signals. Modulating signals generated by the nodes may include establishing at least two communication channels that are substantially orthogonal to one another.

Fig. 4 is a flow chart illustrating a method for locating a human being such a firefighter or rescue worker, in an area in accordance with another embodiment of the invention. The person is provided with a portable user node in process <b>401.</b> The user node includes a transmitter that generates a signal on one or more carrier frequencies, a receiver, and a processor. The user node may also include a user interface, as well as other input and output devices.

A plurality of portable pseudolite nodes are distributed <b>402</b> within the area. Each of the pseudolite nodes includes a transmitter that generates a signal on one or more carrier frequencies, a receiver, and a processor. Signals generated by the user node and the pseudolite nodes are modulated <b>403</b> with digital signals to establish communication among the user node and the pseudolite nodes and to convey data among the user node and pseudolite nodes. A relative position of the user node and the pseudolite nodes is determined <b>404</b> using the modulated signals, and a relative position of the firefighter or other person is determined <b>405</b> using the relative position of the user node and the pseudolite nodes.

In order to ensure that both positioning and communications among the user and pseudolite nodes are reliable, certain features may be included to ensure that the integrity of the system is preserved. In the case of communications information, integrity can be enhanced by encoding the signals in such a way that transmission errors may be detected and/or corrected. Commonly known methods of providing this form of integrity include techniques such as Viterbi coding or the inclusion of forward error correction ("FEC") codes. The reliability of position information may be enhanced using receiver autonomous integrity monitoring ("RAIM") techniques such as those commonly used in GPS receivers.

Further discussion related to indoor geolocation systems and integration systems related thereto may be found in "A DSSS/CDMA/FDMA Indoor Geolocation System" presented by Progri et al. at the Institute of Navigation (ION GPS 2002, 24-27 September 2002, Portland, OR, pp. 155-164) and "GPS/Pseudolite/SDINS Integration Approach for Kinematic Applications" presented by Lee at the Institute of Navigation (ION GPS 2002, 24-27 September 2002, Portland, OR, pp. 1464-1473). Further disclosure relating to pseudolite signal structure maybe found in "The Impact of Proposed Pseudolite's Signal Structure on the Receiver's Phase Code Error" presented by Progri and Michalson at the Institute of Navigation (ION 57^th Annual Meeting/CIGTF 20^th Biennial Guidance Test Symposium, 11-13 June 2001, Albuquerque, NM, pp. 414-422) and "An Investigation of the Pseudolite's Signal Structure for Indoor Applications" presented by Progir et al. at the Institute of Navigation (ION 57^th Annual Meeting/CIGTF 20^th Biennial Guidance Test Symposium, 11-13 June 2001, Albuquerque, NM, pp. 453-462). Further disclosure relating to the ''near-far'' problem for indoor geolocation systems may be found "An Alternative Approach to Multipath and Near-Far Problem for Indoor Geolocation Systems" presented by Progri and Michalson at the Institute of Navigation (ION GPS, 2001, September 11-14, 2001, Salt Lake City, UT, pp. 1434-1443).