Source: https://patents.google.com/patent/WO2002015614A1/en
Timestamp: 2020-01-27 21:26:59
Document Index: 479035600

Matched Legal Cases: ['art 700', 'art 700', 'art 700', 'art 700', 'art 800', 'art 1000', 'art 1000', 'art 1000', 'art 1100', 'art 1100', 'art 1100', 'art 1100', 'art 1300', 'art\n1300', 'art 1300', 'art 1300']

WO2002015614A1 - Method, system, and computer program product for positioning and synchronizing wireless communications nodes - Google Patents
Method, system, and computer program product for positioning and synchronizing wireless communications nodes Download PDF
WO2002015614A1
WO2002015614A1 PCT/US2001/025381 US0125381W WO0215614A1 WO 2002015614 A1 WO2002015614 A1 WO 2002015614A1 US 0125381 W US0125381 W US 0125381W WO 0215614 A1 WO0215614 A1 WO 0215614A1
PCT/US2001/025381
Douglas C. Szajda
2000-08-15 Priority to US22559200P priority Critical
2000-08-15 Priority to US60/225,592 priority
2001-08-15 Application filed by University Of Maryland, College Park filed Critical University Of Maryland, College Park
2002-02-21 Publication of WO2002015614A1 publication Critical patent/WO2002015614A1/en
POSITIONING AND SYNCHRONIZING WIRELESS
The development of an efficient lightweight protocol to determine the topology of a wireless network of mobile hosts has proven to be elusive.
Several conventional solutions have been explored, but each has serious limitations. Table 1 below provides a summary of these conventional approaches.
Table 1: Positioning Technologies For example, global satellite positioning (GPS) can be used to determine covert absolute positions. GPS can also provide an absolute timing reference. However, GPS receivers are not sensors and the accuracy measurements fall within the range of meters. An ultrasonic system provides improved accuracy measurements, but is effective over limited ranges. As the information in Table 1 shows, there is a need for a method and system that overcome the above limitations of conventional positioning technology.
The present invention solves the above problems by providing methodologies and techniques for determining the precise location (e.g., within a few centimeters) of a collection of nodes within three-dimensional space. In addition, the present invention also determines the clock attributes
(including drift and offset) relative to neighboring nodes. The present invention can be divided into three distinct phases with each phase having one or more communication cycles. Each cycle communication carries out the exchange of information among the nodes according to the protocol defined in this invention.
The accompanying drawings, which are incorporated herein and form part of the specification, illustrate the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the pertinent art to make and use the invention, hi the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the leftmost digit(s) of a reference number identifies the drawing in which the reference number first appears.
FIG. 1 illustrates a wireless multinodal communications system according to an embodiment of the present invention. FIG. 2 illustrates a communications node according to an embodiment of the present invention.
FIG. 6 illustrates a computation module according to an embodiment of the present invention. FIG. 7 illustrates an operational flow diagram for positioning wireless communications nodes according to an embodiment of the present invention.
I. Introduction The present invention includes a method, system, and computer program product for enabling a wireless communications node to determine accurately and precisely the spatial locations of neighboring communications nodes distributed in three-dimensional space. Additionally, the present invention includes methodologies and techniques for determining the clock characteristics, including the relative offset and drift of the neighboring nodes. As a result, each node is permitted to execute precise synchronized actions.
The present invention has significant implications for a broad range of wireless networking infrastructure and applications. The rapid availability of accurate location information can greatly simplify and optimize the implementation of ad-hoc networks and/or sensor-based applications. One exemplary application domain benefiting from the present invention includes vehicle position sensors (e.g., for "smart" highways or for collision detection in adverse conditions). Another example is a tourist information system in which a tourist is given relevant information for the location of the tourist.
FIG. 1 illustrates an embodiment of a wireless multinodal communications system 100 of the present invention. System 100 includes a widely distributed network of wireless communications nodes 102a-102n (collectively referred to herein as "communications nodes 102"). As discussed above, system 100 can be implemented in a variety of mobile and/or non- mobile wireless networks, including sensor-based applications. Additionally, communications nodes 102 are positioned in three-dimensional space. The present invention can be implemented in a system having a centralized communications node 102. However, in the preferred embodiment, no centralized node or node with any special privileges is required. Accordingly, the present invention operates in any environment consisting of a collection of communications nodes 102. As such, the positioning and/or synchronization methodologies and techniques of the present invention can be initiated or executed by any one of the communication nodes 102.
The initiating or executing node is referred to as the base node. Referring to FIG. 1, the base node is communications node 102a (referred to herein as "base node 102a"). The nodes located within the listening range of base node 102a are referred to as the neighboring nodes. The neighboring nodes in FIG. 1 are denoted as communications nodes 102b-102p.
Communications nodes 102q-102r lie outside of the range of base node 102a.
Clock module 204 includes a time-of-day clock, as described in detail below. Clock module 204 is linked to communication module 208 which receives and transmits signals through antenna 216. As discussed below, communication module 208 consists of several send and receive buffers for storing the signals. Clock module 204 and communication module 208 are linked to permit the receive and/or transmit times of the signals to be timestamped and/or recorded. The transmit time of a signal is the value of the time-of-day clock of the transmitting communications node 102 when a specified bit (e.g., the last bit of the message sync header) is transmitted. The specified bit is referred to herein as the "sync bit" of the signal. The receive time of a signal is the value of the time-of-day clock of the receiving communications node 102 at the arrival of the sync bit. Computation module 210 consists of a general-purpose computation and storage engine. Computation module 210 manages clock module 204 and communication module 208, and executes other operations as described in detailed below. Computation module 210 constructs the information (e.g., send messages) residing in the send buffers of communication module 208.
Computation module 210 also instructs clock module 204 to send a timing signal to communication module 208 to initiate the sending operations. Computation module 210 also collects the information residing in the receive buffers of communication module 208. Antenna 216 sends and receives signals (including electronic, electromagnetic, optical, or the like). In an embodiment, antenna 216 is a UHF antenna operating in half-duplex mode at, for example, 10 Mbs data rate, 2.4 GHz carrier, and turnaround time of a microsecond. However, it should be understood that the present invention operates in other regions of the frequency spectrum, including without limitation in the radio, microwave, and infrared spectrum, as would be apparent to one skilled in the relevant art(s).
FIG. 3 shows the components of communication module 208 according to an embodiment of the present invention. Sync detector 308 receives signals from antenna 216 and forwards the signals to decoder 312. Upon recognizing the synch bit of the received signal, sync detector 308 sends a timestamp trigger pulse to clock module 204 (shown in FIG. 2). Thus, in an embodiment, the timestamp trigger pulse corresponds to the last edge of the last bit of the sync header of the received signal. Decoder 312 decodes the rest of the received signal and stores the signal in received message queue 316. Received message queue 316 is one of two receive buffers located in communication module 208. The second receive buffer is received message bypass 304. Antenna 216 delivers signals destined for received message bypass 304 directly to the buffer. Measurement recorder 320 receives and stores signals from received message queue 316 and received message bypass 304. Communication module 208 also includes a send message encoder 328 and an information exchange encoder 332 that send signals to antenna 216 for broadcast to other communications nodes 102. On receiving a control signal (i.e., timing signal from clock module 204), the contents of send message encoder 328 and information exchange encoder 332 are sent out at the prescribed rate of 10 Mbps using a 2.4 GHz carrier.
FIG. 4 shows the components of clock module 204 according to an embodiment of the present invention. Clock module 204 includes a timestamp generator 404, a clock 408, and a control signal generator 416. Clock 408 is a time-of-day clock of nanosecond resolution. The offset and drift of clock 408 are assumed to be essentially constant over a few seconds. High clock drifts, of the order of 100 parts-per-million (pp ), are acceptable. Thus, the present invention can be implemented with a crystal oscillator clock.
With nanosecond resolution, TOD register 504 captures the time of day from clock 408, and continuously records time since the last initialization of the register. Upon receiving an initialization signal, the value of TOD register 504 is reset to zero. TOD register 504 receives a timestamp trigger pulse from communication module 208 (shown in FIG. 2), as discussed below. Upon receipt of the timestamp trigger pulse, the current time value recorded in TOD register 504 is transfeixed to timestamp register 508. The time value serves as the timestamp for the timestamp trigger pulse. Timestamp register
508 interacts with bus 214 to transfer out a timestamp signal representing the time value.
Clock 408 also drives countdown register 512. Countdown register 512 receives nanosecond pulses from clock 408 and counts down to generate a timing signal when the count reaches zero. The timing signal is sent to communication module 208 (shown in FIG. 2) to support operations requiring transmit and receive times. After releasing the timing signal, countdown register 512 refreshes its contents with the contents of reset register 516. Accordingly, reset register 516 contains the refresh value for countdown register 512. The refresh value it provided by computation module 210 (shown in FIG. 2).
FIG. 6 shows the components of computation module 210 according to an embodiment of the present invention. Computation module 210 includes a coordinate processor 604 and a clock attribute processor 608, both of which are connected to an internal universal bus 620. A memory 612 and 110 arbitrator 616 are also connected to bus 620. I/O arbitrator manages the exchange of signals between computation module 210 and bus 214.
III. Operational Flow for Positioning Communications Nodes The present invention provides a lightweight, inexpensive and scaleable solution for determining the location and clock attributes of a collection of spatially distributed communications nodes 102. Referring to FIG. 7, flowchart 700 represents the general operational flow of an embodiment of the present invention. More specifically, flowchart 700 shows an example of a control flow for determining the spatial locations of multiple communications nodes 102 described in reference to FIG. 1-6. The control flow of flowchart 700 begins at step 701 and passes immediately to step 704. At step 704, base node 102a (shown in FIG. 1) initiates the positioning and synchronization process by exchanging measurement messages with neighboring nodes 102b-102p. In turn, each communications node 102 asynchronously transmits and/or receives a measurement message with its neighboring nodes. As intimated above, computation module 210 (shown in FIG. 2) constructs two types of send messages that are transmitted from communication module 208. One type of send message is a measurement message. A measurement message contains an identifier for the transmitting communications node 102 and a transmit timestamp. The measurement message also includes a header and trailer for synchronization and frame delimiting. Computation module 210 interacts with clock module 204 and communication module 208 to construct the measurement message. Once generated, the measurement message is stored in send message encoder 328 (shown in FIG. 3).
In an embodiment, communications node 102 operates in half duplex mode to exchange measurement messages in TDM A slots. As such from the perspective of base node 102a, each neighboring node 102b-102p is assigned a designated time slot for exchanging signals with base node 102a. In send mode, countdown register 512 (shown in FIG. 5) counts down and sends a timing signal pulse to send message encoder 328 (shown in FIG. 3). The timing signal instructs send message encoder 328 to forward the measurement message stored therein to antenna 216. The timing signal is set to enable antenna 216 to transmit the measurement message in the time slot for the designated neighboring node 102b-102p. Computation module 210 (shown in
FIG. 2) provides the refresh values to reset register 516 (shown in FIG. 5) so that it can load countdown register 512 to trigger the next transmission in the designated time slot for the next neighboring node 102b-102p.
Prior to forwarding the measurement message to antenna 216, send message encoder 328 (shown in FIG. 3) sends a timestamp trigger pulse to
TOD register 504 (shown in FIG. 5). In an embodiment, send message encoder 328 pulses TOD register 504 when the sync bit (e.g., the last bit of the message sync header) is transmitted to antenna 216.
Upon receipt of the timestamp trigger pulse, TOD register 504 pulses timestamp register 508 to generate and forward a timestamp signal to send message encoder 328 (shown in FIG. 3). Send message encoder 328 postpends the timestamp to the measurement message which is forwarded to antenna 216. Antenna 216 transmits the measurement message to the neighboring node 102b-102p for the designated time slot.
When base node 102a is operating in receive mode, antenna 216 (shown in FIG. 2) receives measurement messages transmitted from neighboring nodes 102b-102p from their designated TDMA slot. Referring back to FIG. 7 at step 708, base node 102a timestamps the received measurement messages. Sync detector 308 (shown as FIG. 3) receives the measurement message from antenna 216. As sync detector 308 detects the sync bit, sync detector 308 pulses TOD register 504 (shown in FIG. 5) and, in response, timestamp register 508 returns a timestamp signal indicating the receive timestamp to decoder 312 (shown in FIG. 3). Decoder 312 decodes the rest of the received measurement message which contains the transmitting node 102 identifier and transmit timestamp. Decoder 312 also receives the timestamp signal from timestamp register 508, and postpends the receive timestamp to the measurement message.
Afterwards, the measurement message is stored in measurement recorder 320. All measurement messages received from the neighboring nodes 102b-102p are stored in measurement recorder 320. Measurement recorder 320 produces a table of measurement messages containing the transmitting node 102 identifier, transmit timestamp and receive timestamp.
Referring again to FIG. 7 at step 712, the measurement messages from the neighboring nodes 102b-102p are forwarded from measurement recorder 320 (shown in FIG. 3) to information exchange encoder 332. Computation module 210 (shown in FIG. 2) sends a signal to reset register 516 (FIG. 5) to refresh countdown register 512. When countdown register 512 counts down to zero, countdown register 512 sends a timing signal to information exchange encoder 332. Upon receipt of the timing signal, information exchange encoder 332 interacts with antenna 216 to broadcast the measurement messages to the designated neighboring nodes 102b-102p. At step 716 in FIG. 7, the recipient communications nodes 102 receives and processes the measurement messages transmitted in step 712 Referring back to FIG. 3, received message bypass 304 collects the measurement messages from antenna 216 and stores them in measurement recorder 320. Computation module 210 processes the measurement messages to determine the spatial coordinates of the neighboring nodes. As a result, each communications node 102, serving as base node 102a, is able to determine the topology of the widely distributed communications nodes 102 within its network. After the topology has been determined, the control flow of flowchart 700 ends as indicated by step 795. Hence, the present invention includes methodologies and techniques that govern the exchange of measurement messages, the generation of send and receive timestamps, the dissemination of the timestamps to all neighboring nodes, and the calculation of their spatial locations. The present invention can be divided into three phases with each phase having one or more communication cycles. A cycle is divided into time slots which are allocated among communications nodes 102.
The three phases include a measurement phase, information exchange phase and computation phase. The measurement phase (described in reference to steps 704-708 in FIG. 7) consists of one or more measurement cycles. In each cycle, each communications node 102 transmits in a designated time slot a measurement message containing its identifier and the transmit timestamp of the message. The communications node 102 also records the receive timestamp of the measurement messages sent by other communications nodes 102. The information exchange phase (described in reference to step 712 in
FIG. 7) consists of one or more information exchange cycles. In each cycle, each communications node 102 transmits a measurement message containing its receive timestamp for messages transmitted by other communications nodes 102 during the measurement phase.
In an embodiment, the measurement cycle is set for two. FIG. 9 illustrates a timing diagram for transmitting measurement messages over two measurement cycles. Each cycle is divided into 1,024 slots to support asynchronous communications with as many as 1,024 communications nodes 102. Each communications node 102 is allocated a designate slot(s) for transmitting and/or receiving measurement messages. Referring back to FIG. 8, if at step 812 computation module 210 determines that the designated maximum number of cycles has not been reached, the control flow returns to step 804 and another measurement cycle is executed as shown in FIG. 9. If, however, it is determined that the maximum number of cycles has been executed, the control flow passes to step 712. As described above, at step 712, the information exchange phase is executed as shown in FIG. 9. It should be noted that the time slots should be large enough to accommodate the message size and clock drifts. In an embodiment, each measurement cycle slot is ten microseconds and each information exchange slot is ten milliseconds.
Referring again to FIG. 8, at step 716, the computation phase is executed to determine the positions of the communications nodes 102 with respect to each other. After the topology has been determined, the control flow of flowchart 800 ends as indicated by step 895. As discussed, upon completion of the information exchange phase, each communications node 102 should have sufficient information to compute the spatial coordinates of every other communications node 102. Each communications node 102 should also have sufficient information to reduce errors. Referring to FIG. 10, flowchart 1000 represents the general operational flow of an embodiment of the present invention for mitigating computation errors. More specifically, flowchart 1000 shows another example of a control flow for determining the spatial locations of multiple communications nodes 102.
The control flow of flowchart 1000 begins at step 1001 and passes immediately to steps 704-708 as described in reference to FIG. 7. At step
1004, computation module 210 determines whether sufficient information has been collected to confirm the accuracy of the measurements. If network conditions (e.g., noise, collision, invalid checksum, etc.) adversely affects the quality of communications among communications nodes 102, the entire measurement phase is repeated, or another measurement cycle is executed.
Specifically, during the measurement phase, whenever computation module 210 detects a corrupted cycle, computation module 210 starts another measurement cycle until, for example, two successive uncorrupted measurement cycles occur. Computation module 210 could also decide to not execute another measurement cycle if it determines that enough information is available. In an embodiment, computation module 210 determines that it has enough information if there are two successive corrupted cycles that contain enough measurements to compute topology within desired accuracy. In an embodiment, computation module 210 determines that it has enough information if there are two measurement cycles that are not successive but are close enough for the clock constant drift assumption.
The present invention can be used to rapidly compute the precise location of communications nodes 102 within the listening range of base node 102b. Referring to FIG. 11, flowchart 1100 represents the general operational flow of an embodiment of the present invention for executing the computation phase. More specifically, flowchart 1100 shows another example of a control flow for determining the spatial locations of multiple communications nodes 102. In particular, flowchart 1100 shows an alternative embodiment of step The control flow of flowchart 1100 begins at step 1101 and passes immediately to steps 704-712 to execute the measurement and information exchange phases as described in reference to FIG. 7. At step 1104, the computation phase is initiated when coordinate processor 604 (shown in FIG. 6) selects the measurement messages stored in measurement recorder 320
(shown in FIG. 3) from neighboring nodes 102b- 102b.
At step 1108, coordinate processor 604 computes the ratio — , where
βa (also referred to herein as "βbase")lS tne dήft rate for base node 102a and βb
(also referred to herein as "βn0nbase")is the drift rate for neighboring node 102b- 102p.
Equation 1 ** (*) = & («* +')
The present invention uses the time equivalent of the internodal distance "d" between the communications nodes 102. In other words, the internodal distance d is represented in nanoseconds to indicate the time it will take light to travel that distance. It is presumed that for the environments for which the present invention is implemented, the speed of light does not vary significantly making this measure of distance stable.
Time generated from local clock 408 is denoted with the τ notation, while global clock time is denoted with a "t" type notation. Also, when discussing local clock times, the letter contained in the subscript on τ indicates the clock which records the time, so for example z-fll is a time recorded by local clock 408 at communications node A (i.e., base node 102a). Accordingly, at time t\, communications node A broadcasts a measurement message in the form of a tuple giving its identifier and a transmit timestamp, the latter denoted by τaX . That is, the timestamp reads:
τΛ s τa (f, ) = βa (aa + tx ) Equation 2
and the tuple broadcast is (A,τaX) . Communications node B receives the tuple and records the time of receipt as τbi . Denoting the time distance between communications node A and communications node B as d , the global time at which communications node B should receive the broadcast from communications node A is tx + d , so that
τ b\ = b { b +tχd) Equation 3 Since each node is running the same decentralized protocol, communication node B also sends a two-tuple at global time t2 . In steps similar to above, communications node B broadcasts the tuple (B,τb2) , where
τbi = τ {f2 ) = β (ab + 12 ) Equation 4 and communications node A receives this broadcast at global time t2 + d . which communications node A marks as time
τa2 = τa (t2 + d) = βa (aa +t2 +d) Equation 5
In an embodiment, once the first cycle of messages has been completed, communications nodes A and B, both, send a second measurement cycle, with communications node A sending its second message at time t3 , and communications node B sending its message at time t4. Using notation similar to above, the timestamps generated by communications nodes A and B is represented by:
τ a4=βa( a+t4+d),md τb,=βb{ab+t4).
X = βa{aa+tι) τbl=βb( b+t1+d)
^a3=βa{aa+t3) τb3=βb( b+t3+d) τaχβa{(Xa+tχd) τb4=βb(ab+t4)
The above eight expressions are referred to herein as "reference equations." During the information exchange phase, communications node A sends the values τα2and τα4to communications node B, and communications node B sends the values τbl and τb3 to communications node A. At this point, both of communications nodes A and B have all eight values τa > Ta2 ' Ta3 ' τ a\ ' Tbl > Tb2 Tb3 » 3I1" Tfi4 •
Accordingly at step 1104, both communications nodes A and B use these eight values to compute the ratios — from the following equation:
Next at step 1112, coordinate processor 604 computes the quantities Δ, and Δ2 from: Δ, s τbx - τΛ =βb( b+tl+d)-βa ( a + tx ) Equation 6
Δ2 s „2 - τi
+ d)-βb { b + f2 ) Equation 7 At step 1116, coordinate processor 604 computes the quantity βbd from the equation:
-X) Equation 8
Equation 8 is derived by averaging these two quantities Ax and Δ2 , or:
^ ^[Ah+^ή-A(α.+ +A(β.^2+(/)-AK+ϋ]
= βa +β d + ∑±L(βa -βb) Equation 9
The first and second lines of the reference equations provide: r„2 - X = βa {t2 -tx) + βad Equation 10
-h τa2 τa -d Equation 11
Ax +A2 _ βa +βb d ] βa -βb τa2 τa\ d 2 2 2 βa
At step 1120, coordinate processor 604 computes the quantity βad
which is determined from βbd . Note that βad =—βbd , and communications βb nodes 102 know both right hand side quantities. At step 1124, coordinate processor 604 determines the internodal distance "d" between communications nodes A and B. It is presumed that both βa and βb are close to one, so that the quantities βad and βbd are both good estimates of d . Therefore, in an embodiment either quantity βad or βb d is selected by coordinate processor 604 as the distance "d. " In another embodiment, the communications node 102 selects the expression having the drift rate for its respective clock 408. For instance, communications node A would select βad and communications node B would select βbd . In another embodiment, each communications node A and B computes the average of the quantities βad or βbd .
The above steps have been described with reference to only two communications nodes 102. However the present invention is scaleable to determine the positions of more than two communications nodes. As such, base node 102a uses the above steps to calculate the distance "d" to each of its neighboring nodes 102b-102p. Therefore, at step 1128, coordinate processor
604 determines whether the internodal distance to all neighboring nodes 102b- 102p have been computed. If not, steps 1104-1124 are repeated. Otherwise, the control flow passes to step 1132.
At step 1132, coordinate processor 604 produces a pointset to determine the topology for communications nodes 102. The present invention is premised on the assumption that base node 102a is positioned at the coordinate point (0,0) in a x-y coordinate system. In other words, all communications nodes 102 believe they are located at the origin of system 100. If there is at least one other communications node 102, the neighboring node 102b-102p with the minimum node identifier (as determined by the node identification number) is considered to be the first reference node, and is positioned on the positive x-axis. If there are three or more non-coUinear neighboring nodes 102b-102p, the neighboring node 102b-102p with the minimum node identifier among those neighborhood nodes 102b-102p that are neither base node 102a, the first reference node, nor collinear with base 102a and the first reference node, is denoted the second reference node and is positioned in the upper half-plane. Thus, the placement of the first reference node has the effect of fixing a particular rotational orientation, while the placement of the second reference node locks in a particular reflective orientation.
It is also presumed that the computation phase is executed only once.
That is, once a given pointset is determined, communications nodes 102 entering or leaving are added or removed incrementally. Therefore, it is conceivable that the actual first reference node is, after some time, not the non-base local node with the minimum node identifier.
Upon determining the base node 102a and the first two reference nodes 102b-102p, the pointset is constructed by coordinate processor 604. FIG. 12 shows the internodal distances among base node 102a and the first and second reference nodes 102b-102c. The law of cosines provide: dx +d3 — d2 cos(α) =
2dxd3
Once cos(α)is computed, coordinate processor 604 computes the lengths of segments BP and R2P , which give respectively the x and y coordinates of second reference node 102c, since base node 102a is positioned at point (0,0), first reference node 102b on the positive x-axis, and second reference node 102c in the upper half-plane.
Coordinate processor 604 then proceeds to compute the rest of the pointset. For each remaining non-base or reference node 102, coordinate processor 604 determines two candidate positions using distances between the remaining node, base node 102a, and first reference node 102b, as above. Next, coordinate processor 604 uses the distance between the node in question and second reference node 102c in order to choose between the two candidate positions. Thus, once coordinate processor 604 has determined the positions of the two reference nodes, the position of each additional node is determined using only the distances from it to the base and reference nodes. In an embodiment, coordinate processor 604 uses more of the internodal distance information to obtain better estimates on point positions.
Thus somewhere in between using a linear amount of data and an n2 amount of data (where n is the total number of communications nodes 102) lies an amount that will efficiently provide the desired accuracy.
In addition to determining the spatial locations, the present invention also determines the clock attributes of each communications nodes 102. Referring to FIG. 13, flowchart 1300 represents the general operational flow of another embodiment of the present invention. More specifically, flowchart
1300 shows an example of a control flow for determining the clock attributes of multiple communications nodes 102.
The control flow of flowchart 1300 begins at step 1301 and passes immediately to steps 704-716 to execute the measurement, information exchange, and computation phases. However, the computation phase continues into step 1304. At step 1304, clock attribute processor 608 processes the information computed at step 716, to determine the clock attributes of neighboring nodes 102b-102p. As described in reference to FIG. 11, upon completion of step 1128, coordinate processor 604 will have computed, for each communications
node 102, all of the τ values in addition to — ,βad and βbd . Moreover, βb assuming communications node A is base node 102a and communications node B is neighboring node 102b, the value of global time "t" can be determined from: τα (0 = βα (αβ + = βααα + βJ Equation 12 where "β" is the drift rate and "βα" is the offset for the local clock of the designated communications node 102. Therefore, for a reading of the local clock at communications node A, the global time "t" can be determined by:
= βb (cb -cα)+^τα (t) Equation 14
Therefore, clock attribute processor 608 of base node 102a (e.g., communications node A) determines the reading of clock 408 on a neighboring node 102 (e.g., communications node B) by computing the value
of βb {αb -αα) , computing the ratio — , and taking a reading from local βb clock 408 of base node 102a.
The value βb (αb - α) is determined by solving both of the equations in the first line of the reference equations for the α term, as follows: c . = —t Equation 14
«, _ Ή Equation 15
A so that,
= X -βbd-^-τa Equation 16
Thus, each communications node 102 utilizes the reference equations to determine both a very good estimate for the internodal distance " d ", and the values of the respective clocks 408 of neighboring nodes 102b-102p based on readings of its local clock 408. The clock attributes, as describe above, are used by each communications node 102 to synchronize its local clock 408 for subsequent operations. After determining the clock attributes, the control flow of flowchart 1300 ends as indicated by step 1395.
Although in the preferred embodiment base node 102a transmits and receives measurement messages, base node 102a is operable to function in passive mode to only receive measurement messages from each neighboring node 102b-102p. The computation phase is adjusted to calculate the position and synchronization data from received tuples accordingly.
FIGs. 1-13 are conceptual illustrations that allow an easy explanation of the present invention. That is, the same piece of hardware or module of software can perform one or more of the blocks. It should also be understood that embodiments of the present invention can be implemented in hardware, software, or a combination thereof. In such an embodiment, the various components and steps would be implemented in hardware and/or software to perform the functions of the present invention. Additionally, the present invention (e.g., system 100 and/or any part thereof) can be implemented in one or more computer systems or other processing systems. In fact, in an embodiment, the invention is directed toward one or more computer systems capable of carrying out the functionality described herein.
Referring to FIG. 14, an example computer system 1400 useful in implementing the present invention is shown. The computer system 1400 includes one or more processors, such as processor 1404. The processor 1404 is connected to a communication infrastructure 1406 (e.g., communications bus, crossover bar, or network). Various software embodiments are described in terms of this exemplary computer system. After reading this description, it will become apparent to a person skilled in the relevant art(s) how to implement the invention using other computer systems and or computer architectures. Computer system 1400 can include a display interface 1402 that forwards graphics, text, and other data from the communication infrastructure 1406 (or from a frame buffer not shown) for display on the display unit 1430.
Computer system 1400 also includes a main memory 1408, preferably random access memory (RAM), and can also include a secondary memory 1410. The secondary memory 1410 can include, for example, a hard disk drive
1412 and/or a removable storage drive 1414, representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive 1414 reads from and/or writes to a removable storage unit 1418 in a well- known manner. Removable storage unit 1418, represents a floppy disk, magnetic tape, optical disk, etc. which is read by and written to removable storage drive 1414. As will be appreciated, the removable storage unit 1418 includes a computer usable storage medium having stored therein computer software and/or data.
Computer system 1400 can also include a communications interface 1424. Communications interface 1424 allows software and data to be transferred between computer system 1400 and external devices. Examples of communications interface 1424 can include a modem, a network interface
(such as an Ethernet card), a communications port, a PCMCIA slot and card, etc. Software and data transferred via communications interface 1424 are in the form of signals 1428 which can be electronic, electromagnetic, optical or other signals capable of being received by communications interface 1424. These signals 1428 are provided to communications interface 1424 via a communications path (i.e., channel) 1426. This channel 1426 carries signals 1428 and can be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link and other communications channels.
In this document, the terms "computer program medium" and "computer usable medium" are used to generally refer to media such as removable storage drive 1414, a hard disk installed in hard disk drive 1412, and signals 1428. These computer program products are means for providing software to computer system 1400. The invention is directed to such computer program products. Computer programs (also called computer control logic) are stored in main memory 1408 and/or secondary memory 1410. Computer programs can also be received via communications interface 1424. Such computer programs, when executed, enable the computer system 1400 to perform the features of the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor 1404 to perform the features of the present invention. Accordingly, such computer programs represent controllers of the computer system 1400.
1. A method of determining the location of communications nodes in a distributed network, comprising the steps of: creating, at a first node, a transmit timestamp for a message as said message is transmitted by said first node to a second node; creating, at said second node, a receive timestamp as said message is received by said second node; storing, at said second node, a measurement tuple corresponding to said message, wherein said storing includes recording an identifier for said first node, said transmit timestamp from said first node and said receive timestamp from said second node; exchanging, by said second node, said measurement tuple with said first node, so that said first node and said second node each have a record of all measurement tuples stored therein; and analyzing said record of measurement tuples to determine the location of said first node and said second node with respect to each other.
14. A method of claim 1, further comprising the steps of: creating, at said second node, a transmit timestamp for a second message as said second message is transmitted by said second node to said first node; creating, at said first node, a receive timestamp as said second message is received by said first node; storing, at said first node, a second measurement tuple corresponding to said second message, wherein said storing includes recording an identifier for said second node, said transmit timestamp from said second node and said receive timestamp from said first node; and exchanging, by said first node, said second measurement tuple with said second node, so that said second node and said first node each have a record of all second measurement tuples stored therein, wherein said analyzing step processes both sets of measurement tuples to determine the location of said first node and said second node with respect to each other.
PCT/US2001/025381 2000-08-15 2001-08-15 Method, system, and computer program product for positioning and synchronizing wireless communications nodes WO2002015614A1 (en)
US22559200P true 2000-08-15 2000-08-15
US60/225,592 2000-08-15
AU8487701A AU8487701A (en) 2000-08-15 2001-08-15 Method, system, and computer program product for positioning and synchronizing wireless communications nodes
US10/344,857 US7224984B2 (en) 2000-08-15 2001-08-15 Method, system and computer program product for positioning and synchronizing wireless communications nodes
WO2002015614A1 true WO2002015614A1 (en) 2002-02-21
AU (1) AU8487701A (en)
EP1631832A1 (en) * 2003-05-26 2006-03-08 Commonwealth Scientific And Industrial Research Organisation Self surveying radio location method
GB2513211A (en) * 2013-01-03 2014-10-22 Csr Technology Inc Method for determining location of wireless devices
CN1870492B (en) * 2005-05-25 2016-04-20 游天童 The synchronous method of time frame fine is realized in WLAN (wireless local area network) or free net
AU2002225377A1 (en) * 2001-12-28 2003-07-30 Nokia Corporation Node selecting method
EP1894337A1 (en) * 2005-06-13 2008-03-05 Philips Electronics N.V. Methods and receives of data transmission using clock domains
FR2670345B1 (en) * 1990-12-11 1994-09-30 Alcatel Business Systems A method for ensuring the permanence of nóoeuds of synchronizing a private telecommunications network on the best available and corresponding network clocks.
2001-08-15 AU AU8487701A patent/AU8487701A/en active Pending
2001-08-15 US US10/344,857 patent/US7224984B2/en not_active Expired - Fee Related
2001-08-15 WO PCT/US2001/025381 patent/WO2002015614A1/en active Application Filing
EP1631832A4 (en) * 2003-05-26 2007-01-17 Commw Scient Ind Res Org Self surveying radio location method
GB2513211B (en) * 2013-01-03 2019-10-30 Csr Tech Inc Method for determining location of wireless devices
US9980097B2 (en) 2015-05-15 2018-05-22 Motorola Mobility Llc Method and apparatus for indoor location estimation among peer-to-peer devices
US20050020275A1 (en) 2005-01-27
US7224984B2 (en) 2007-05-29
AU8487701A (en) 2002-02-25
EP1821116B1 (en) 2013-08-14 Relative 3D positioning in an ad-hoc network based on distances
US20150289089A1 (en) 2015-10-08 Wide area positioning system
CN1196941C (en) 2005-04-13 Method for determining position of communication satellite using distance measurement in tow direction
Ref document number: 10344857