a2, United States Patent
`US 6,453,168 B1
`(10) Patent No.:
`McCradyetal. Sep. 17, 2002
`
`(45) Date of Patent:
`
`US006453168B1
`
`(54) METHOD AND APPARATUS FOR
`DETERMINING THE POSITION OF A
`MOBILE COMMUNICATION DEVICE USING
`LOW ACCURACY CLOCKS
`
`(75)
`
`Inventors: Dennis D. McCrady, Holmdel;
`Lawrence J. Doyle, Hazlet; Howard
`Forstrom, Fairlawn, all of NJ (US)
`
`(73) Assignee:
`
`ITT Manufacturing Enterprises, Inc,
`Wilmington, DE (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`
`OTHER PUBLICATIONS
`
`Robert A. Scholtz, The Origins of Spread—Spectrum Com-
`munications, IEEE Transactions on Communications, May
`1982, pp. 822-854, vol. Com. 30, No. 5, University of
`Southern California, Los Angeles, CA.
`Benjamin B. Peterson, et al., Spread Spectrum Indoor
`Geolocation, Journal ofthe Institute of Navigation, Summer
`1998, vol. 45, No. 2, New London, Connecticut.
`
`* cited by examiner
`Primary Examiner—William Trost
`Assistant Examiner—Philip J. Sobutka
`(57)
`ABSTRACT
`
`Aspread spectrum position location communication system
`determines the position of a mobile master radio using a
`(21) Appl. No.: 09/365,702
`round-trip messaging scheme in which the timeof arrive
`(TOA) of ranging messages is accurately determined to
`yield the range estimates required to calculate the position of
`(22)
`Filed:
`Aug. 2, 1999
`
`(SL) Tints C0oe eeccceeccseeeeesseeeeseeeeeesnneeennes H04B 7/00_the mobile radio viatrilateration. The master radio transmits
`(52) U.S. Ch. eee 455/517; 455/506; 455/65;
`outbound ranging messagesto plural reference radios which
`455/277.2; 455/456; 342/457; 375/347
`respond by transmitting reply ranging messages. Upon
`(58) Field of Search oo...eee 455/456, 457,
`reception of the reply ranging message, the master radio
`455/422, 517, 466, 67.1, 65, 59, 504, 506,
`determines the range to the reference radio from the signal
`133-5, 277.1, 277.2; 342/457, 463, 357.06;
`propagation time calculated by subtracting the far-end turn
`375/138, 347
`around time from the round-trip elapsed time. Any combi-
`nation of fixed or mobile radios of known positions can be
`used as the reference radios for another mobile radio in the
`system, thereby providing adaptability under varying trans-
`mission conditions. The individual radios do not need to be
`Synchronized to a commontime reference, thereby elimi-
`nating the need for highly accurate system clocks. By
`performing internal delay calibration, errors caused by
`difficult-to-predict internal transmitter and receiver delay
`variations can be minimized. Leading-edge-of-the-signal
`curve fitting and frequency diversity techniques minimize
`the effects of multipath interference on TOA estimates.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,665,404 A *
`5/1987 Christy et al. wee... 342/463
`5.109.390 A *
`4/1992 Gilhousen etal. ...... 455/506 X
`RE34,004 E
`7/1992 Rogoff et al.
`5,293,642 A
`3/1994 Lo
`5,579,321 A
`11/1996 Van Grinsvenetal.
`5,663,990 A *
`9/1997 Bolgianoet al.
`........... 375/138
`5,774,876 A *
`6/1998 Woolley etal. ...... 340/572.1 X
`5,912,644 A *
`6/1999 Wang... ceeeeee 342/457
`5,982,324 A * 11/1999 Watters et al.
`......... 342/357.06
`
`18 Claims, 6 Drawing Sheets
`
`RIS-1
`
`V
`
`RTS-1
`
`REF
`REE
`
`RADIO2 RADIO3|186
`TOA NSG.
`TOA MSG.
`(MOBILE)
`OA
`MSG
`(MOBILE)
`
`
`
`
`
`
`
`MASTER
`fl RADIO
`MOBILE
`
`2
`
`RIS-T
`
`V
`
`TOA MSG.
`
`RIS-T
`
`REF|14 rer|20
`
`RADIOI
`RADIOA
`(HOBIE
`(HOBIE
`
`TOA OPERATIONAL SETUP
`
`
`
`1
`
`APPLE 1005
`
`APPLE 1005
`
`1
`
`

`

`U.S. Patent
`
`Sep. 17, 2002
`
`Sheet 1 of 6
`
`US 6,453,168 B1
`
`Ol
`
`A
`
`9}|£olavy|7OldvY
`07|aeA4y
`A(J190H)oswoL7Xn,(71190W)
`
`
`
`(a1180W)dNl3STWNOILVYId0VOL(31180W)
`
`poiayylolavy
`43Y434
`L-S1YTIONZI1S
`
`isdsid
`‘DSWVOLDSWVOL
`
`Ol
`
`WIISWH
`
`olayy
`
`2
`
`
`

`

`U.S. Patent
`
`Sep. 17, 2002
`
`Sheet 2 of 6
`
`US 6,453,168 B1
`
`
`
`ee)F
`
`vivd=Dviva=OY\/\/4||INDY
`
`Ios10||LIMSNVL
`viva|_OW¥0lyLvdOvWSN\>of\/
`
`
`‘SWolayNa¥0lNIWA
`
`Lyd3945S3HiINDI
`ONIs
`
`Idiay
`
`
`SNISNVYYO1030L0Ud¥I-VWS)GIHIGOW
`
`
`
`
`||H—LIMSNYYL
`
`
`
`Isiy
`
`
`
`sausnow
`JNINDIS
`
`NWO)
`
`3
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 17, 2002
`
`Sheet 3 of 6
`
`US 6,453,168 B1
`
`CC
`
`0€
`
`Ol
`
`
`8¢—97
`S1991SLid91SdIH)9606SIOGWAS
`
`
`S7199S7149$77878ZIHLIM
`
`
`YIHLONOLLVNILSICVOLWNO0)
`ViVdSsJuaayNONLVZINOWHINAS|NOILISINODY
`
`
`ONISSIIONdVOLYOIWHOJFAVML-S1Y
`
`
`
`
`
`S77pX9]
`
`HWSd1H)
`
`ve
`
`4
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 17, 2002
`
`Sheet 4 of 6
`
`US 6,453,168 B1
`
`yOu
`
`I-W)DSWS-¥OL
`
`
`
`Wisi¥]---
`
`
`
`[71S1y |L-S1Y
`
`
`
`—-~[L95WS-¥0l]---[19swvol][01-47][1]
`
`
`
`
`OldvY39NIYITY
`
`WOAVTAC
`
`{vol
`
`foe]
`
`
`
`OlOVYYILSVW
`
`
`
`“W)AV1A0
`
`100V
`
`OL
`
` 10)010UdVOL
`
`5
`
`

`

`U.S. Patent
`
`Sep. 17, 2002
`
`Sheet 5 of 6
`
`US 6,453,168 B1
`
`OL
`
`
`
`
`
`
`
`09YOLVIFYYO)JININDISTOAWAS
`
`
`
`
`
`NOLLII190NOILISINODW
`
`NOILVZINOWHINAS
`
`
`
`VOLSYIDONL
`
`NOILDI1I0
`
`MIOHSIYHL
`
`
`
`
`
`
`
`
`
`
`
`
`INITA190Q3dd¥1Y3ZILNYNO
`
`08
`
`XI1dW0)
`
`wyonlNo)
`
`XdN0)}gy
`
`pLYOLALI0WIINGWagIa«7
`
`xF1dWO)u
`
`\I1dHOD
`
`
`
`
`LINNaH1YNWuigia|-——2
`AV130Yd
`
`
`
`Ss
`
`WOW
`
`6
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 17, 2002
`
`Sheet 6 of 6
`
`US 6,453,168 B1
`
`86
`
`
`4904ISVHdYalWuv)une|YO.|SNIGVI1LVMdWHId0
`wy<-|11dJAWN)ASILYOHSHEA
`
`
`
`wy5|Wad180d“SOUdONId
` STIANYS7VOL|itimuidaaun|SdH&<dW|aSThd
`
`
`7903JW)
`
`
`
`
`
`
`ONISSIIOUdNOILISINOIYNNO)
`
`
`
`—-_——
`
`14150WHO)
`
`CIOHSIYHL
`
`YOLWTTWO)
`
`TOSWAS
`
`41d
`
`413d
`
`
`
`SdIH}€>dW
`
`4¥114d
`
`
`
`(W)SONId40“ON
`
`1¥OL
`
`vl
`
`HLM“O34GNI
`
`O1LUTIVdW
`
`WalidAVN
`
`LdJAWND
`
`AVIAH1Vd
`
`Yaa
`
`FUVMHOSdSNISNISSIDOdVOL
`
`WWO)|
`
`194130
`
`Lold
`
`7
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US 6,453,168 B1
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`1
`METHOD AND APPARATUS FOR
`DETERMINING THE POSITION OF A
`MOBILE COMMUNICATION DEVICE USING
`LOW ACCURACY CLOCKS
`
`2
`location capabilities such that the device can communicate
`and establish position location at
`the same time without
`disruption of the voice or data communication.
`Among convention techniques employed to determine the
`position of a mobile communication device is the reception
`at
`the mobile communication device of multiple timing
`signals respectively transmitted from multiple transmitters
`at different, knownlocations(e.g., global positioning system
`The present invention relates to a position location system
`(GPS)satellites or ground-based transmitters). By determin-
`for determining the position of a mobile communication
`ing the range to each transmitter from the arrival time of the
`device, and, more particularly, to a system employing two-
`timing signals, the mobile communication device can com-
`way transmission of spread spectrum ranging signals
`pute its position using triangulation.
`between the mobile communication device and reference
`The accuracy and operability of such position location
`communication devices having relatively low accuracy
`techniques can be severely degraded in the presence of
`clocks, to rapidly and accurately determine the position of
`multipath interference caused by a signal traveling from a
`the mobile communication device in the presence of severe
`transmitter to the receiver along plural different paths,
`multipath interference.
`including a direct path and multiple, longer paths over which
`2. Description of the Related Art
`the signal is reflected off objects or other signal-reflective
`The capability to rapidly and accurately determine the
`media. Unfortunately, multipath interference can be most
`physical location of a mobile communication device would
`severe in some of the very environments in which position
`be of great benefit in a variety of applications. In a military
`location techniques would have their greatest usefulness,
`context,
`it 1s desirable to know the location of military
`such as in urban environments and/or inside buildings, since
`personnel and/or equipment during coordination of field
`artificial structures create opportunities for signals to be
`operations and rescue missions, including scenarios where
`reflected, thereby causing signals to arrive at the receiver via
`signals of conventional position-determining systems, such
`a numberof different paths.
`as global position system (GPS) signals, may not be avail-
`Attempts have been madein position location systems to
`able (e.g., within a building). More generally, appropriately
`mitigate the effects of multipath interference. An example of
`equipped mobile communication devices could be used to
`a system reported to provide position location in a multipath
`track the position of personnel and resources located both
`environment
`is presented by Peterson et al.
`in “Spread
`indoors or outdoors, including but not limited to: police
`Spectrum Indoor Geolocation,” Navigation: Journal of The
`engaged in tactical operations; firefighters located near or
`Institute of Navigation, Vol. 45, No 2, Summer 1998,
`within a burning building; medical personnel and equipment
`incorporated herein by referenceinits entirety. In the system
`in a medical facility or en route to an emergency scene,
`described therein (hereinafter referred to as the Peterson
`including doctors, nurses, paramedics and ambulances; and
`system),
`the transmitter of a mobile radio continuously
`personnel
`involved in search and rescue operations. An
`transmits a modulated pseudorandom noise (PRN)
`integrated position location communication device would
`sequence, with a carrier frequency of 258.5 MHz and a
`also allow high-value items to be tracked and located,
`chipping rate of 23.5 MHz. The transmitter is battery pow-
`including such items as personal computers,
`laptop
`ered and therefore can be easily transported inside a build-
`computers, portable electronic devices, luggage, briefcases,
`ing. Four wideband antennas located on the roofofatestsite
`40
`valuable inventory, and stolen automobiles.
`In urban
`receive the signal
`transmitted by the mobile radio. The
`environments, where conventional position determining sys-
`signals are conveyed from the antennas to four correspond-
`tems have moredifficulty operating, it would be desirable to
`ing receivers via low loss cable that extends from the roof to
`reliably track fleets of commercial or industrial vehicles,
`the receivers disposed in a central location. The receivers
`including trucks, buses and rental vehicles. Tracking of
`demodulate the signal transmitted by the mobile radio using
`people carrying a mobile communication device is also
`an analog-to-digital (A/D) converter board disposed inside a
`desirable in a numberof contexts, including, but not limited
`host personal computer (PC), which samples the signal at
`to: children in a crowded environment such as a mall,
`1.7 s intervals for 5.5 ms and processes the raw data to
`amusement park or tourist attraction; location of personnel
`determine the Time of Arrival (TOA). The system uses two
`within a building; and location of prisoners in a detention
`receiver computers, each with a dual channel A/D board
`facility.
`inside. The output from the receiver boxes is fed into a dual
`The capability to determine the position of a mobile
`channel A/D board on two host computers. Each of the host
`communication device also has application in locating the
`computers processes the signal on each channel of the A/D
`board to determine the TOA for each channel relative to a
`position of cellular telephones. Unlike conventional land-
`based/wire-connected telephones,
`the location of conven-
`trigger common to both channels on the A/D board. The
`tional cellular telephones cannot automatically be deter-
`TOAalgorithm is based on finding the leading edge of the
`mined by emergency response systems(e.g., the 911 system
`cross correlation function of the PRN sequence that
`is
`in the United States) when an emergency call is placed.
`available at the output of the correlator using frequency
`Thus, assistance cannot be providedif the caller is unable to
`domain techniques. TOAs are transferred via wireless local
`speak to communicate his or her location (e.g., when the
`area network to the RAM-drive of a third computer acting as
`caller is unconscious, choking or detained against will). The
`the base computer. From the TOAs,
`the base computer
`capability to determine the position of cellular telephones
`calculates time differences (TDs) and determines the two-
`could be used to pinpoint
`the location from which an
`dimensional position of the transmitter. This position is then
`emergencycall has been made. Such information could also
`plotted in real time on a building overlay.
`be used to assist in cell network management.
`The Peterson system suffers from a number of shortcom-
`Naturally, in cases where a mobile communication device
`ings. The range between the target radio and each reference
`is being used primarily to transmit or receive voice or data
`radio is determined by measuring the duration of time
`information, it would be desirable to incorporate position
`required for a signal
`to travel between the radios. This
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`
`8
`
`

`

`US 6,453,168 B1
`
`3
`information can be determined from a one-way communi-
`cation only if the target radio and the reference radios remain
`synchronized to the same time reference. That is, the trans-
`mitting radio establishes the time of transmission of the
`signal based on its local clock, and the receiving radio
`determinesthe timeof arrival of the signal based onits local
`clock which must constantly be synchronized to the same
`time reference as the clock of the transmitter. The signal
`propagation duration can then be determined essentially by
`subtracting the time of transmission from the timeof arrival.
`Because the Peterson system uses this one-way measure-
`ment
`technique,
`the system requires synchronization
`between the clocks of the transmitter and the four receivers.
`
`Unfortunately, the precise time synchronization required to
`accurately measure the duration of the signal propagation
`cannottolerate significant time drift of any local clocks over
`time. Consequently, all of the clocks of the system must be
`highly accurate (i.e., on the order of 0.03 parts per million
`(ppm)), thereby increasing the cost and complexity of the
`system.
`in the Peterson system to keep the
`The requirement
`transmitter and receiver clocks synchronized has further
`implications on the accuracy of the position estimates made
`from the one-way ranging signals. Asynchronous events
`occur within each radio which cannot readily be character-
`ized or predicted in advance. These events introduce errors
`in the radio with respect to knowledge of the actual time of
`transmission and time of arrival,
`thereby degrading the
`accuracy of the range and position estimates.
`Developed to demonstrate the feasibility of indoor
`geolocation, Peterson’s test system does not address a num-
`ber of technical issues required to construct a commercially
`useful system. For example, the receiver antennas are fix-
`edly mounted (immobile) and cabled to receivers in a remote
`location. Consequently, the system is not adaptable to vary-
`ing transmission conditions and cannot adjust to or com-
`pensate for scenarios where the radio of interest cannot
`communication with one or moreof the reference receivers.
`
`Signal processing and analysis are performed with standard-
`size personal computers and other bulky experimental
`equipment. The system uses a relatively low chipping rate
`and remains susceptible to multipath interference, impacting
`the accuracy and operability of the system. Further,
`the
`position of radio determined by the system is only a two-
`dimensional position (i.e., in a horizontal plane).
`Accordingly, there remains a need for a commercially
`viable position location system capable of quickly and
`accurately determining the three-dimensional indooror out-
`door position of a compact mobile communication device in
`the presence of severe multipath interference for use in the
`aforementioned practical applications.
`SUMMARYOF THE INVENTION
`
`It is an object of the present invention to rapidly, reliably
`and accurately determine the three-dimensional position of
`a mobile communication device in a variety of
`environments, including urban areas and inside buildings
`where multipath interference can be great.
`It is a further object of the present invention to provide a
`compact, handheld or portable mobile communication
`device having position location capabilities useful in a wide
`array of applications, including location and/or tracking of
`people and items such as: military personnel and equipment,
`emergency personnel and equipment, valuable items,
`vehicles, mobile telephones, children and prisoners.
`It is another object of the present invention to minimize
`the effects of interference caused by multipath signal propa-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`thereby providing
`gation in a position location system,
`highly accurate three-dimensional position estimates even
`under severe multipath conditions.
`It is yet another object of the present invention to reduce
`the cost of a position detection system by avoiding the need
`for synchronization to the same timing reference throughout
`the system, thereby eliminating the need for certain expen-
`sive components, such as highly accurate clocks.
`It is a still further object of the present invention to use
`state-of-the-art spread spectrum chipping rates and band-
`widths to reduce multipath interference and improve posi-
`tion measurement accuracy in a position location system.
`Another object of the present invention is to separate
`multipath interference from direct path signals to accurately
`determine the time of arrival of the direct path signal to
`accurately determine range.
`Yet another object of the present invention is to minimize
`errors caused by processing delays that are difficult
`to
`characterize or accurately predict.
`Still another object of the present invention is to provide
`a self-healing system, wherein a mobile communication
`device can adaptively rely on any combination of fixed
`radios and other mobile radios to determine its own position
`under varying communication conditions.
`A further object of the present invention is to minimize
`design and manufacturing costs of a position-locating
`mobile communication device by using muchofthe existing
`hardware and software capability of a conventional mobile
`communication device.
`
`A still further object of the present invention is to incor-
`porate position location capabilities into a mobile commu-
`nication device being used to transmit or receive voice or
`data information, such that the device can communicate and
`establish its position at the same time without disruption of
`the voice or data communication.
`
`The aforesaid objects are achieved individually and in
`combination, and it is not intended that the present invention
`be construed as requiring two or more of the objects to be
`combined unless expressly required by the claims attached
`hereto.
`
`invention, a position
`In accordance with the present
`location communication system provides accurate, reliable
`three-dimensional position location of a handheld or
`portable, spread spectrum communication device within
`milliseconds without interruption of voice or data commu-
`nications. Using spread spectrum waveformsand processing
`techniques, the system of the present invention is capable of
`determining position location to an accuracy ofless than one
`meter in a severe multipath environment.
`More particularly,
`the system of the present invention
`employs a two-way, round-trip ranging message scheme in
`which the time of arrive of the ranging messages is accu-
`rately determined to yield accurate range estimates used to
`calculate the position of a mobile radio via trilateration. A
`master or target mobile radio transmits outbound ranging
`messagesto plural reference radios which respondbytrans-
`mitting reply ranging messagesthat indicate the location of
`the reference radio and the message turn around time (i.e.,
`the time betweenreception of the outbound ranging message
`and transmission of the reply ranging message). Upon
`reception of the reply ranging message, the master radio
`determines the signal propagation time, and hence range, by
`subtracting the turn around time and internal processing
`delays from the elapsed time between transmission of the
`outbound ranging message and the time ofarrival of the
`
`9
`
`9
`
`

`

`US 6,453,168 B1
`
`5
`reply message. In this manner, the individual radios do not
`need to be synchronized to a common time reference,
`thereby eliminating the need for highly accurate system
`clocks required in conventional time-synchronized systems.
`The brief ranging messages can be interleaved with voice
`and data messages in a non-intrusive manner to provide
`position detection capabilities without disruption of voice
`and data communications.
`
`To provide high accuracy range estimates, the time of
`arrival of the ranging messagesare precisely estimated. By
`performing internal delay calibration, errors caused by
`difficult-to-predict internal transmitter and receiver delay
`variations can be minimized. The system uses state-of-the-
`art spread spectrum chipping rates and bandwidthsto reduce
`multipath interference, taking advantage of existing hard-
`ware and software to carrying out a portion of the TOA
`estimation processing. Leading edge curvefitting is used to
`accurately locate the leading-edge of an acquisition
`sequence in the ranging message in order to further reduce
`effect of multipath interference on TOA estimates. The
`severity of multipath interference is determined by evaluat-
`ing the pulse width of the acquisition sequence. If necessi-
`tated by severe multipath, frequency diversity is used to
`orthogonalize multipath interference with respect
`to the
`direct path signal, wherein an optimal carrier frequency is
`identified and used to estimate the TOA to minimize the
`impact of multipath interference.
`invention is self-
`Further,
`the system of the present
`healing. Unlike conventional systems which require com-
`munication with a certain set of fixed-location reference
`
`radios, the system of the present invention can use a set of
`reference radios that includes fixed and/or mobile radios,
`wherein the set of radios relied upon to determine the
`location of a mobile communication device can vary over
`time depending on transmission conditions and the location
`of the mobile communication device. Any combination of
`fixed or mobile radios of knownpositions can be used as the
`reference radios for another mobile radio in the system,
`thereby providing adaptability under varying conditions.
`The ranging and position location techmique of the present
`invention is useful in wide variety of applications, including
`location and/or tracking of people and items such as: mili-
`tary personnel and equipment, emergency personnel and
`equipment, valuable items, vehicles, mobile telephones,
`children and prisoners.
`The above andstill further objects, features and advan-
`tages of the present invention will become apparent upon
`consideration of the following detailed description of a
`specific embodiment
`thereof, particularly when taken in
`conjunction with the accompanying drawings wherein like
`reference numerals in the various figures are utilized to
`designate like components.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a diagrammatic view of the operational setup of
`the position location system according to the present inven-
`tion.
`
`FIG. 2 is a message timing diagram illustrating a modified
`CSMA-CAprotocol useful for exchanging ranging mes-
`sages in accordance with an exemplary embodimentof the
`present invention.
`FIG. 3 illustrates the structure of an initial outbound
`ranging message transmitted by the master radio in accor-
`dance with an exemplary embodimentof the present inven-
`tion.
`
`FIG. 4 illustrates the timing of the internal delay calibra-
`tion performed by the master radio and reference radios
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`during the ranging message sequence in accordance with an
`exemplary embodimentof the present invention.
`FIG. 5 is a functional block diagram illustrating the
`internal delay calibration processing performed by the mas-
`ter radio and the reference radios in accordance with an
`
`exemplary embodimentof the present invention.
`FIG. 6 is a functional block diagram illustrating the
`acquisition processing employed to detect the communica-
`tion acquisition sequence of the ranging messagesin accor-
`dance with an exemplary embodimentof the present inven-
`tion.
`
`FIG. 7 is a functional block diagram illustrating the
`processing performed to determine the time of arrival of a
`ranging message,
`involving evaluation and separation of
`multipath interference from the direct path signal.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`In accordance with the present invention, a handheld or
`portable, spread spectrum communication device provides
`accurate, reliable position location information within mil-
`liseconds without interruption of voice or data communica-
`tions. Using spread spectrum waveforms and processing
`techniques, the system of the present invention is capable of
`determining position location to an accuracy ofless than one
`meter in a severe multipath environment. In particular, a
`two-waytime-of-arrival messaging scheme is employed to
`achieve the aforementioned objectives, while eliminating
`the need for highly accurate system clocks required in
`conventional
`time-synchronized systems. By performing
`internal delay calibration, frequency diversity and leading-
`edge-of-the-signal curve fitting, a highly accurate estimate
`of ranging signal time of arrival can be obtained, ensuring
`the accuracy of the range and position calculations based
`thereon. Unlike conventional systems which require com-
`munication with a certain set of fixed-location reference
`
`radios, the system of the present invention can use a set of
`reference radios that includes fixed and/or mobile radios,
`wherein the set of radios relied upon to determine the
`location of a mobile communication device can vary over
`time depending on transmission conditions and the location
`of the mobile communication device.
`
`Referring to FIG. 1, a position location system 10
`includesa target or “master” mobile communication device
`or “radio” 12 communicating with four reference commu-
`nication devices 14, 16, 18 and 20. As used herein and in the
`claims, a mobile communication device or mobile radio is
`any portable device capable of transmitting and/or receiving
`communication signals,
`including but not
`limited to:
`a
`handheld or body-mounted radio; any type of mobile tele-
`phone (e.g., analog cellular, digital cellular or satellite-
`based); a pager or beeper device; a radio carried on, built
`into or embedded in a ground-based or airborne vehicle; or
`any portable electronic device equipped with wireless trans-
`mission and reception capabilities.
`Each of reference radios 14, 16, 18 and 20 can be any
`radio located at a knownposition that is capable of com-
`municating with the master radio 12 in the mannerdescribed
`herein to convey position and range-related information. For
`example, one or more of the reference radios can be a
`beacon-like radio fixedly mounted in a knownlocation, such
`as on a tower or building. One or more of the reference
`radios can also be a mobile radio capable of determining its
`position from others sources, such as from reception of
`global position system (GPS) signals or from being pres-
`ently located at a surveyed position whose coordinates are
`
`10
`
`10
`
`

`

`US 6,453,168 B1
`
`7
`known and entered into the radio (the reference radios are
`not themselves GPSsatellites). Finally, as explain in greater
`detail hereinbelow,one or more of the reference radios relied
`upon by a particular target radio can be another mobile
`communication device similar or identical to the master
`radio, wherein the reference radio determines its own posi-
`tion in accordance with the technique of the present inven-
`tion (in this case, the “reference” radio functions as both a
`reference radio for other radios and as its own “master”
`radio). The fact that each reference radio could potentially
`be a mobile radio is indicated in FIG. 1 by the designation
`“(MOBILE)”nextto eachof reference radios 14, 16, 18 and
`20.
`Master radio 12 communicates with the four reference
`radios 14, 16, 18 and 20 to determine its location in three
`dimensions. Specifically, master radio 12 and each ofref-
`erence radios 14, 16, 18 and 20 includes an antenna coupled
`to a transmitter and a receiver for transmitting and receiving
`ranging messages. The antenna, transmitter and receiver of
`each radio mayalso be used for other communications, such
`as voice and data messages. The time of arrival (TOA) of
`ranging messages transmitted between the master and ref-
`erence radios is used to determine the range to each refer-
`ence radio, andtrilateration is then used to determine from
`the range measurementsthe location of the master radio with
`respect to the reference radios. Each reference radio must
`know its own position and convey this information to the
`master radio to enable the master radio to determine its
`
`10
`
`15
`
`20
`
`25
`
`position from the ranging messages exchanged with the
`reference radios.
`
`30
`
`Importantly, the system of the present invention employs
`a two-way or round-trip ranging message scheme, rather
`than a one-way TOA scheme, such as those conventionally
`used to estimate range. As seen from the bi-directional
`arrows in FIG. 1, master radio 12 transmits to each of the
`reference radios 14, 16, 18 and 20 an initial outbound
`ranging message and receives back from each reference
`radio a reply ranging message. For example, master radio 12
`sequentially exchanges ranging message with each indi-
`vidual reference radio, first exchanging ranging messages
`with reference radio 14, then with reference radio 16, etc.
`By way of non-limiting example, to take advantage of
`existing hardware and software found in certain radios, the
`messaging protocol used for ranging can be derived from the
`Carrier Sense Multiple Access—Collision Avoidance
`(CSMA-CA)protocol used by these radios. As shown in
`FIG. 2, the Request-to-Send (RTS) and Clear-to-Send (CTS)
`messages of the CSMA-CAprotocol are retained to provide
`an initial outbound ranging message and a reply ranging
`message, respectively, and the Message and Acknowledge-
`ment packets of the CSMA-CAprotocol need not be used.
`The RTS message can be adapted for use as the initial
`outbound ranging message transmitted from the master radio
`to the reference radios (designated as RTS-Tin the figures),
`and the CTS message can be adapted for use as the reply
`ranging message transmitted from each of the reference
`radios to the master radio (designated as TOA Msg. in the
`figures). The format of the standard RTS and CTS messages
`can be modified to support the ranging messaging schemeof
`the present invention, as explained in greater detail herein-
`below. As with standard RTS and CTS messages,the ranging
`messages of the present invention can be interleaved with
`voice and data communication messages to permit exchange
`of the ranging messages without disrupting voice and data
`communications. Of course, it will be understood that the
`messaging schemeof the present invention is not limited to
`any particular protocol, and any suitable message structure
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`that permits transmission of an outbound ranging message
`and a reply ranging message can be used to implement the
`present invention.
`Referring again to FIG. 2, the ranging message sequence
`begins with the master radio transmitting an initial outbound
`ranging message RTS-T to a particular reference radio (the
`process is repeated with each reference radio in sequence).
`The reference radio receives the RTS-T message after a
`delay proportional to the range from the master radio, and
`determines the time of arrival of the RTS-T message.
`Subsequently, the reference radio transmits a reply ranging
`message (TOA Msg.) to the master radio. The TOA message
`packet indicates the turn around timeat the reference radio,
`1e., the time between arrival of the RTS-T message and
`transmission of the corresponding TOA message. The mas-
`ter radio determinesthe time of arrival of the TOA message
`and derives the range to the reference radio from knowledge
`of the round trip delay time and the turn around time.
`An example of an RTS-T waveform 22 adapted for
`accurately determining the time of arrival of the RTS-T
`message is shown in FIG. 3. The waveform comprises an
`acquisition portion followed by a data portion. The acqui-
`sition portion of the waveform begins with a communication
`acquisition sequence (comm. acquisition) 24 comprising
`sixteen 4 us symbols with 128 chips each. The communi-
`cation acquisition sequence is the same as the communica-
`tion acquisition sequence in a conventional RTS waveform
`of the CSMA-CAprotocol. Consequently, existing hardware
`and software in the receiver of the reference radios of the
`exemplary embodiment can be used to detect the arrival of
`the RTS-T message. The acquisition por