US 7876266 B2
A method solving for unknown location values and clock rate values of one or more nodes of a network of nodes communicating with one another entails associating multiple transmitting nodes and receiving nodes that produce, respectively, ping transmit events and ping receive events by receiving and associating receive count stamps to the ping transmit events. Ping event values corresponding to ping events relating to associated ones of the ping transmit events and the ping receive events are generated and accumulated. Solutions for transmit and receive node clock rate values and node location values relating to the transmit and receive ping events at arbitrary times within a harmonic block time interval are generated from the grouped, accumulated ping event values. The generated solutions for one of the associated multiple nodes are a function of the ping transmit events and ping receive events produced by the others of the associated multiple nodes.
1. A method of solving for unknown location values and clock rate values of one or more nodes of a network of nodes communicating with one another, comprising:
associating multiple nodes including multiple transmitting nodes and multiple receiving nodes that operate with, respectively, a priori asynchronous node transmit clocks and node receive clocks, the transmitting nodes producing ping transmit events and the receiving nodes producing ping receive events by receiving and associating receive count stamps to the ping transmit events;
for each transmitting node of the multiple nodes, the ping transmit events taking place at transmission times corresponding to a transmit clock count produced in response to operation of the node transmit clock, and, for each receiving node of the multiple nodes, the ping receive events taking place at receive times corresponding to a receive clock count produced in response to operation of the node receive clock;
generating ping event values corresponding to ping events relating to associated ones of the ping transmit events and the ping receive events;
accumulating the ping event values produced by the multiple nodes;
grouping the accumulated ping event values corresponding to multiple ones of the ping events that include ping events associated with multiple different pairs of nodes of the network and that occur within a harmonic block time interval; and
generating from the grouped, accumulated ping event values solutions for transmit and receive node clock rate values and node location values relating to the transmit and receive events at arbitrary times within the harmonic block time interval, the solutions for node clock rate and node location values of one of the associated multiple nodes being a function of the ping transmit events and ping receive events produced by the others of the associated multiple nodes.
2. The method of
3. The method of
4. The method of
5. The method of
6. The method of
7. The method of
8. The method of
9. The method of
10. The method of
11. The method of
12. A method of solving for unknown location values and clock rate values of one or more nodes of a network of nodes communicating with one another, comprising:
associating multiple nodes including multiple transmitting nodes and multiple receiving nodes that operate with, respectively, a priori asynchronous node transmit clocks and node receive clocks, the associated multiple nodes over time being formed in different groups of transmitting and receiving nodes, and the transmitting nodes producing ping transmit events and the receiving nodes producing ping receive events by receiving and associating receive count stamps to the ping transmit events;
for each transmitting node of the multiple nodes, the ping transmit events taking place at transmission times corresponding to a transmit clock count produced in response to operation of the node transmit clock, and, for each receiving node of the multiple nodes, the ping receive events taking place at receive times corresponding to a receive clock count produced in response to operation of the node receive clock;
generating ping event values corresponding to ping events relating to associated ones of the ping transmit events and the ping receive events;
accumulating the ping event values produced by the multiple nodes;
grouping the accumulated ping event values corresponding to multiple ones of the ping events that occur within multiple harmonic block time intervals such that the ping event values occurring within the multiple harmonic block time intervals are produced by the different groups of the transmitting and receiving nodes, and for each of the multiple harmonic block time intervals, the grouped, accumulated ping event values corresponding to ping events associated with multiple different pairs of nodes of the network and that occur within the harmonic block time interval; and
generating from the grouped, accumulated ping event values solutions for transmit and receive node clock rate values and node location values relating to the transmit and receive events at arbitrary times within each of the multiple harmonic block time intervals.
13. The method of
This application is a continuation of International Application No. PCT/US2007/025172, filed Dec. 7, 2007, which claims benefit of U.S. Provisional Patent Application No. 60/873,891, filed Dec. 7, 2006.
This disclosure relates to embodiments of a “PhaseNet” technique, which is shorthand for implementation of space-time solutions, in which, in one preferred embodiment, a single node determines its own space-time solutions based on other network nodes with which the single node communicates. In other preferred embodiments, space-time solutions for the node can be generated using other resources in the network. PhaseNet enables reliable, precise object positioning particularly for environments where the Global Positioning System (GPS) is blocked or subject to interference such as within the urban core.
Current techniques for positioning within the urban environment include the following:
GPS is a space-based satellite constellation that provides constant, global geopositioning to the end user. A user's GPS device processes signals from three or more GPS satellites, and by way of trilateration provides latitude and longitude data. GPS may be global, but it is not ubiquitous because foliage, building edifices, and bridges all block GPS signals. The absence of GPS signals in places such as the urban core is problematic because high value applications for reliable positioning abound, yet no reliable solution exists. The urban core in major cities is also known as the “urban canyon,” because skyscrapers on both sides of the streets block GPS signals. Another common problem is multipath distortion in which signals bounce off many surfaces before reaching the user, resulting in vastly inaccurate positioning data.
PhaseNet is original equipment manufacturer (OEM) “plumbing level” technology that is integrated into device and infrastructure products such as those sold by Motorola, Cisco, D-Link, Nokia, Ericsson, HP, Agilent, and Intel. This OEM technology is primarily in the form of software modules, but it also includes custom hardware for Military “MILSPEC” and custom applications. Additionally, hardware reference designs for very minor chip level modifications (IP) at the transceiver level can improve the performance. Because of its interoperability, PhaseNet can include any number of the additional positioning methods listed above; however, PhaseNet can reside independent of these and still provide sub-meter positioning to the end user.
To overcome the limitations of the GPS system mentioned above, a GPS extension can be provided by PhaseNet. Furthermore, PhaseNet can create an entirely independent navigational capability by embedding positioning data into wireless networks that abound in the urban canyon. PhaseNet is an interoperable architecture; hence, it implements a capability to effectively coordinate disparate devices operating at different frequencies, and with different standards and protocols. This architecture is reliable, precise, scalable, dynamic, broad baseline, plug-and-play, secure and cost-effective.
Potential users include city visitors relying on in-car navigation systems that show onscreen location data provided by GPS. GPS fails when a traveler crosses the threshold into the urban canyon where unreliable signals show inaccurate navigation data or may be blocked entirely. However, urban drivers are well within reception of reliable WiFi, WiMax or cellular networks and PhaseNet positioning data embedded in the corresponding wireless signals provide the necessary positioning data.
First responders tending to an emergency on a city sidewalk, copier technicians needing proof of performance for 50 copiers on various floors of a downtown building, courier dispatch wanting to know the location of a the driver, and city workers ensuring a backhoe is not cutting gas or fiber optic lines are all examples of situations in which PhaseNet service can substitute for inadequate GPS capability.
The abundance of WiFi in urban settings provides an excellent example of how PhaseNet may leverage a robust and abundant signal source. For example, increasing deployments of individual WiFi access points by businesses and consumers make it difficult to walk through a downtown area without detecting WiFi signals. WiFi “sniffers” typically installed on personal computer (PC) operating systems constantly look out for WiFi sources. PhaseNet positioning data can be added to the inbound and outbound packets sent from these access points to alert the user that a WiFi spot is available. These PhaseNet positioning data are located outside the firewall, enabling users to receive the data even if they are not logged onto a network, thus enabling both secured and unsecured access points to provide positioning data.
Reliable sub-meter positioning performance and sub-nanosecond timing calibration are readily obtained using this PhaseNet based methodology. The method entails weaving positioning data into the fabric of wireless networks. More specifically, the method entails embedding PhaseNet data into the communications channel of the various wireless networks that proliferate throughout our environment. WiMax, WiFi, Cellular, Mesh Networks, Ad Hoc Networks, First Responder Radio, and Spaceborne systems such as Iridium and the GPS constellation itself are all potential PhaseNet carriers. Wireline networks are also potential PhaseNet carriers for use in areas such as wireline IT networks synchronization, geodetic remote sensing, and fiber optic backbone calibration.
Consequently, an end user having only a laptop, PDA, VoIP phone or other device with a WiFi network connection receives positioning data without the need for a costly GPS chip. Cities are deploying metropolitan-wide industrial grade WiFi networks that enable a WiFi user to maintain continuous WiFi access while moving almost anywhere within the city. The development of metropolitan-wide WiFi networks in more than 250 cities will by 2009 create a very large user base for WiFi-based positioning devices.
Just as WiFi provides positioning signals, WiMax, cellular, broadcast television, digital radio, satellite, and mesh networks are potential PhaseNet signal carriers. This “last-mile” wireless broadband solution is like cellular service in that base stations provide the signals to the user for broad baseline service. Individually, each signal type can provide robust positioning. If all the signals are synthesized, then the resulting ‘signal soup’ enables almost any communicating device to be a reliable, precision locator without requiring an embedded GPS chip.
This disclosure describes a simple example of an overall PhaseNet embodiment that explicitly uses sound waves as opposed to electromagnetic waves to communicate between PhaseNet nodes. It also explicitly affords a tutorial treatment of how PhaseNet works, most notably in the use of relatively common “low and medium tech” methods, without sacrificing critical underlying engineering principles required for enabling electromagnetic-based PhaseNet operations as well. The extrapolation of audio principles to electromagnetic (EM) methods is a generally straightforward exercise, with the details of count-stamping circuitry and hardware being the primary physical difference between audio-based and electromagnetic-based implementations. The details of how the physical system-agnostic principles work on leading-edge satellite systems or terrestrial wireless and cell networks can all reference back to this simple enabling example using audio.
Various experiments described below test different combinations of the number of cars that are actually communicating, and how PhaseNet principles function as nodes turn on and off, or as effective communication links between cars become intermittent or shut down.
Each car includes a core counting element that includes a low cost digital clock with an associated digital counter. The counter is driven by the clock; it should have at least a 64 bit counting range. For a baseline embodiment, it can run at roughly 1 million counts per second. The core counting element can be built using cascades of counters, with 8 or 16 bit counters running at the highest speed, and driving lower rate 64 bit counters, for example. These specifications are quite flexible. Given that PhaseNet solutions ultimately solve for count-rate variabilities between PhaseNet nodes, their quality can be commensurate with extremely low-cost parts and very basic performance specifications.
There are many possible choices for audio communication protocols between cars. The minimum digital communication requirement for a monoplex or duplex channel in a preferred embodiment may be the ability to transmit 10,000 bits per second (bps). Normal telephone-line audio modem protocols are the specific example used in this embodiment, where the state-of-the-art functional bit rate for such equipment is significantly higher than 10 Kbit per second (10 Kbps). 10 Kbps will be sufficient for this embodiment, however.
PhaseNet operates using generic D3P or duplex ping-pong-pung signaling protocols. In this embodiment, pings will dominate the raw generation of space-time data, pongs will be used for the purpose of determining where the outside walls of the gymnasium are located, and pungs will be part of the digital communications between cars.
In short, a ping is any network-agreed method or multiple agreed methods of generating an event at a car, count-stamping that event using the car's local counter, and communicating the event to another car that count-stamps the arrival of the event. This is essentially the idea behind GPS-satellite-to-GPS-receiver signaling. A pong is similar to a ping in that a car count-stamps and communicates (often broadcasts) an event, but the event is reflected back to the event-generating car by its external environment or to another car, to be subsequently count-stamped by the event-generating car upon arrival of one or more echoes. A pung is a digital packet of information sent between two cars or sent by one car broadcasting to all others that might be listening. It is called out as a discrete entity to highlight its most common form of a modern digital packet or some fractional payload within a digital packet.
Skilled persons will instantly recognize that pings, pongs, and pungs, entities as defined above, are in very wide use in many systems today, under different names appropriate to specific applications and systems. The central reason for creating these entities within PhaseNet is to aggregate and optimally exploit this rich source of prior methods, while abstracting and generalizing their basic information content across all systems and spatial-scales. PhaseNet can thus operate on these generic entities rather than taking into account specific details of the physical instruments being employed, or details of the specific medium of communication or its inherent topology. In short, nodes move about in a soup of pings, pongs, and pungs, whether that soup is composed of acoustic waves from a semiconductor integrated circuit or laser pulses from a space probe at the edge of the solar system. PhaseNet is designed to work no matter what the soup contains.
Each audio signaling protocol supplies its own precise definition of a “ping event.” The main concerns in making this definition are the noise properties relative to a node's ability to count-stamp an outgoing broadcast ping as well as count-stamping an incoming received ping, using its local digital counter as the component that effectively enumerates the ping event. “Time-stamp” is an intuitive cousin to “count stamp,” but PhaseNet has a strong preference for the phrase “count-stamp” because the notion of “time” is asymptotically defined. Across the vast range of PhaseNet application and configurations, there is an equally vast range of “ping” definitions, with general ideas behind “carrier phase” methods within GPS playing an important lead role. The description below touches upon carrier phase methods even in this rather straightforward baseline audio embodiment.
It is not necessary to literally impress a dedicated ping signal or “pulse-like spike” directly onto the chosen audio signaling protocol. The normal operation of an audio signaling method has certain regular properties that can be defined as the ping event, such as specific zero crossings of a carrier signal or the tagging of a specific symbol or preamble sent out over the audio communication channel. Carrier phase methods within GPS receivers are prior art in this regard (as alluded to above), in which the normal oscillation of the GPS carrier signal is used as a tagged event, as well as code symbols sent out as an explicit time-stamped event.
Though it is unnecessary to impress ping events onto a communications protocol, neither is it precluded. In certain situations requiring precision, one may wish to modify a given communication protocol to more explicitly and physically create a ping event, generally with the intent of improving the precision with which an outgoing ping is count-correlated with its local digital counter. An example of this is the creation of a simplified waveform such as a de-modulated delta function or rise-time waveform where precision methods of measurement can be applied.
In the current embodiment, conventional modem protocols are assumed to be the communications mechanism between cars, using the speakers and microphones described above as the physical channel. Provisions are made for slight Doppler shifts in the primary carrier frequency of such protocols, because the cars may travel up to a few meters per second in random directions (which in the current embodiment may be of insignificant consequence, whereas in other applications such as motor vehicles on an open road and aircraft communications, Doppler issues become more pronounced). Most modem equipment has such provisions to cope with slow drift or offsets in carrier frequencies, typically in the form of phase-locked-loops having reasonable capture ranges on the carrier frequency.
For the purposes of simply demonstrating how PhaseNet functions, it can be assumed that digital data carried by audio communications include two primary payloads: (1) data used to actually drive the car if it is not autonomous; and (2) pung data packets which, in this embodiment, are essentially the sharing of local count-stamps of sent and received pings (with significant “compression” as will be seen, because the redundancies in raw ping data need not be communicated). Overall PhaseNet monitoring data and node-health data are also part of the digital communication channel, and explicit companions to the ping data within the pung packet.
Also included in the inventory of core elements on a given car/node, are the physical/electronic components that actually correlate the local digital counter with both broadcast ping events and the incoming ping events on individual audio microphones. The output of these components is a digital stream of count values, representing values of ping events broadcast via the car's speaker, and count values of ping events being received on microphones. Up-to-date implementations of these components can use digital waveform generators and a digital to analog (D/A) converter for generating and sending out pings and pungs. Likewise, a simple analog to digital (A/D) converter on received audio is quite straightforward. Skilled persons will generally recognize that all that is being described here are simple forms of what is now called “software-defined radio.”
There exists master software that runs the ongoing processes further described below, monitors the health of the node and its immediate network, stores data, and in certain situations, oversees or even conducts calculations of space-time solutions. For the preferred embodiment, this software is generic personal computer software that can easily operate (keep up with) processing the flow of information involved. As other embodiments are considered, this software can become much more complex and it can be segmented into various physical modules and locations.
The act of actually calculating space-time solutions in real time may overtax the numerical capabilities of certain CPUs, thus necessitating a second parallel CPU on a car dedicated to numerical calculations as described below. Indeed, a sophisticated robotic car may have many CPUs.
By putting the pieces together, one can see the operation of individual cars, quickly culminating in all ten cars moving around and undergoing the ambiguities of links and nodes going on and off-line. The end goal is to illustrate PhaseNet's functioning both as it allows cars to determine where they are relative to one another, as well as separately illustrating how they can situate themselves relative to their known universe of the gymnasium.
First, counters are switched on and begin counting at a million counts per second. All cars can “start their counting engines” whenever they please, but at some point all of them are counting, generally at slightly different count rates and with randomly different count values. Later experiments will deliberately impose conditions on poor and erratic count rates in order to illustrate the extreme flexibility built into PhaseNet, but for the purposes of the current embodiment, one can assume that the counters and clocks being used are of reasonably high quality and generally within a fraction of one percent of each other, as defined by an objective calibrated observer in the gymnasium. (State-of-the-art EM systems may not have the luxury of an external master calibration, where this is a core subject in the discussion on how PhaseNet can potentially be a tool in the continual evolution of global time and space standards.)
Next, assignments among cars are made. There are many ways to do this. Specifically, combinations of both fixed schedule linking and unlinking can be tested, as well as adaptive behavior responsive to real-time conditions, such as one car occluding another.
Once initial communication assignments are in place, each car synchronizes, at least in a digital communication (modem) sense, to its assigned partners. Each car begins to broadcast a simple repetitive modem-like signal to which the other cars can tune, following a well-established modem ritual. The easiest way to isolate individual car-to-car communications is to assign specific audio carrier frequencies to pairs of cars. But there are also ways to have the network share a common carrier frequency and use spread spectrum methods or other kinds of shared medium methods to nevertheless instantiate car-car monoplex and duplex channels. Indeed, when moving from this embodiment to various state-of-the-art wireless and cellular embodiments, the options become as numerous as the panoply of modern communication systems allows.
In the mono-directional assignment case where a car is simply listening to the broadcast signal of one other car, this means tuning into the broadcasting signal of its assigned car and ensuring that the repetitive signal is being properly received and decoded. In the bi-directional assignment case, the listening car B starts to supplement its initialization message with a few bytes of information broadcast specifically to let car A know that it is receiving car A's signal, and expects to hear from car A to find out whether car A is also hearing and decoding car B's signal. In general, these are all rudimentary and standard operations for establishing an arbitrary network of communicating nodes and are very well known engineering issues for both network and communications engineers.
When all nodes are cooperating and sending out a network-wide message that given car has established its assigned channels and that all its assigned channel nodes are reporting the same information, the pre-assignments are known to be complete. Once all pre-assignments of communications partners are established, the count-stamping componentry on all cars can start to count-stamp outgoing pings and incoming pings, if it has not started doing this already. That componentry can begin at any time; it simply needs actual communications running before the count values have meaning.
Looking at a car D, the local clock that is driving the digital counter happens to be the clock that is driving the 50 Kilohertz central frequency on its modem communications channels. Since in this example it has been determined that each car will produce 1,000 pings per second (distinct from, but loosely related to the previously chosen 10 Kbps), the “ping event” for car D has been determined to be every fiftieth zero crossing of its central frequency. It thus automatically produces the virtual 1,000 pings per second by simply oscillating as usual. Because the digital counter and the modem are running off the same local clock, it is known that there are exactly 1,000 count values (1 million divided by 1000) elapsing between each transmitted ping (every fiftieth zero crossing). Thus, the count-stamping of the outgoing pings is also automatic. Practitioners of GPS equipment design will recognize distinct similarities of these ideas to GPS code phase and carrier phase prior art, and they may anticipate engineering challenges such as keeping track of “every fiftieth cycle,” cycle slips, carrier phase ambiguity, and the like. Except for one example, data-driven modulation of the carrier frequency itself gives rise to pseudo-noise on the uniformity of the fiftieth zero crossing, requiring a sub-process to determine and effectively remove the pseudo-noise prior to executing the core PhaseNet algorithm. Later descriptions explore these challenges in this simplified gymnasium setting using audio waveforms.
(Note that the speed of sound is just over 30 centimeters per millisecond, thus ensuring that cars separated by several meters will have non-trivial delays or count intervals between transmitting and receiving a ping. This simple point is centrally important in the subsequent extrapolation of this embodiment to satellites, in that satellites several hundred or several thousand kilometers apart will encounter similar multi-count delays in pings-sent to pings-received even when electromagnetic waves traveling at 30 cm/ns are used. Automobiles on a “smart highway” that can alert a car to the aberrant sub-millimeter-level fluctuations of a drunk driver approaching from several hundred meters away would need to account for these non-trivial delays in light signals over sub-kilometer distances.)
In one detailed scenario, a car D happens to be listening to five other cars with its microphone. In establishing communication with all the other cars, each car informs car D of exactly which zero crossing of its unique near-50-KHz central frequency corresponds to its ping event. A variety of methods could accomplish this, but perhaps the simplest one is to explicitly modulate a code symbol onto the carrier signal such that the very end of the code symbol corresponds to the desired zero crossing, later to be enumerated through a separate digital communication.
Note also that existing communication hardware typically does not include one of these “ping pulse generators,” as depicted in
Though low cost digital clocks can provide sufficient accuracy for this simple example, they may be deliberately perturbed. The flexibility of PhaseNet can thus be demonstrated, because a primary function of PhaseNet is to sleuth and solve for the inter-variability of count rates between PhaseNet nodes, amidst a cacophony of influencing factors such as dynamic spatial relationships, environmental factors, instrument drifts and delays, and eventually gravitational and relativistic perturbations. Without deliberate perturbation on count rates alluded to above, this enabling example would still come up with solutions for count inter-variability, but it would represent almost a trivial level of solution for clock irregularities relative to the spatial dynamics of the cars.
Thus, for this enabling example, deliberate perturbations to the digital clocks highlight the ability of PhaseNet to measure count drift, an exercise that portrays the same issues when dealing with EM communications and the system engineering goal of reaching single digit picosecond network synchrony. Measuring higher bandwidth phase noise on individual PhaseNet nodes has pragmatic implications to signal acquisition and tracking, as well as communications bandwidth and quality of service. The phase noise associated with a given node can become a network-defined variable and can begin to have real-time measurements approaching the chosen ping-rate. The measurement of drift consumes the higher bandwidth phase noise due to a web of communication links, as illustrated in
Pingforms into Space-Time Solutions
The primary data generation aspects of this embodiment are represented in
Counting and Communicating Construct Space-Time Solutions
A central conclusion of “set physics” is that a set of elements (nodes) having the ability to count, the ability to communicate their counts, and the ability to associate count values received by other nodes with their own internal count, may define, based solely on structures similar to the pingforms of
The notion of “absolute” space-time is unsupportable because (A) space-time is not defined for a null set or a single element set, and (B) space-time is defined for a populated set only after communications have taken place between set members, and the definition can refer to only a space-time description of an asymptotic past state of the set. The fact that it is fundamentally impossible to define the current state of the set because only active in-process communications can do that is referred to as the “asymptotic collision frame.” As records of more communications are accumulated, past states of the entire set can be determined, and collisions between set members can be a set-wide defined phenomena rather than a mathematical construct of relative motion. This becomes an important practical matter as PhaseNet is scaled to solar-system spatial scales.
In the context of the 10-car example, the metric that PhaseNet creates as the companion to the pingforms of
There are several specific approaches to mathematically expressing the space containing a set of elements. A fundamental equation that relates the metrics described above to the pingforms of
Critics might be quick to ask “change with respect to what?” when they consider that isolated variables (e.g., the variability of car A's counting) are being measured; what is the external standard being used to set the context for this variability? This is a very reasonable question especially relative to the introduction of equation (1). The change is the primary entity in the particular metric space chosen. There is no need to isolate one particular car/node's counting and demand that a master car drive up along side it and judge its counting capabilities (uniformity of rate, rate itself, etc.). Change itself can be a candidate primary entity—an explicit choice for a metric; a dx is just as good as an x to start building equations and solutions to those equations; each is just a symbol for an entity, and there is no need to burden the entities with axiomatic relationships.
Building the baseline embodiment of the moving cars, exchanging information, with eventual resultant measurements of change being the fundamental entities measured within the system is mathematically straightforward.
The sequential differences in the intervals between arriving pings can be accounted for through three core mechanisms: rate non-uniformities in the receiving node at the instance of arrival of the ping, rate non-uniformities in the sending node at the instance of sending the ping, and “spatial movements” of, independently, the sending node at the instance of sending the ping and the receiving node at the instance of receiving the ping. With this equation, there is an initial connection between acquired data and a ‘pseudo-metric’ in that distance still needs to be more practically rendered.
Toward this end (practically transforming ‘distance’ into something useable), for the case of the cars, a two dimensional space is defined using ‘change entities.’ The introduction of two-dimensional space is represented by equation (2) and the accompanying graphic
The subscripted k values are essential to two-dimensional and higher dimensional formulations of PhaseNet. This disclosure refers to the entity kxy
Mathematically, there is no reason to require interpreting spatial change with respect to a physical framework other than what is implied by equation (2). All ten of the cars can roam around, pinging each other, collecting data in the form of the left-hand term of equation (2), and then start to ask how the unknown entities on the right hand side of equation (2) can begin to resolve themselves as more data are collected.
Duplex Pings and Initial Metric Solutions
With reference to
Each car listens to and records the other 9 cars' pings, yielding 9×10 or 90 pingforms that are then recorded. At the same time, there are three basic metric unknowns for each car, giving a total of 3×10 or 30 metric unknowns. Without consideration of data production rates and metric solution rates, the baseline embodiment uses a 3× over-sampling ratio as the set evolves. Each new connection adds two new pingforms to an otherwise constant network. Each addition of a new node adds three new unknown metric waveforms, and up to 2×(N−2) new data pingforms, where N is the number of previous nodes in the set. This gives a first taste of one of the primary mechanisms by which PhaseNet can enhance overall system precisions and accuracies through Metcalf-like networking principles.
The simple form of the matrix equation relating acquired data to a chosen metric space is given by
One choice is to order the darrival values (vector g) in groups of 90, corresponding to roughly synchronous pings of the 45 duplex channels existing amongst the 10 cars/nodes. There is nothing inherently wrong with this ordering choice. PhaseNet organizes the g vector in short snippets of dpingforms, of a size equal to the length of the “harmonic block.” In the baseline embodiment, this length is defined as 10 milliseconds or nominally 10 ping epochs for any given car/node. Most PhaseNet implementations will probably choose between 5 and 100 fundamental ping epochs per harmonic block, being a trade-off between, on the one hand, flexibility in dealing with different sampling rates on the chosen metrics, and on the other hand, inverting very large matrices. As computing resources continue to improve, the choice will slowly move beyond “100”, as the pressure to worry about the size of matrices and the speed of inversions lessens.
Vector “f” on the right hand side of equation (3) is the metric solution vector made up of the entire set of the right-hand-side variables of equation (2) (not including the coarse direction vectors, which will be discussed below) collected from the time that all cars started to record pings to the time when a solution snapshot is attempted with use of equation (3).
The f vector is also ordered in an essentially arbitrary enumeration, with car A naturally coming first and so on. Any given car then has 2×2+1 or 5 metric unknowns per harmonic block, while the g vector for that given car is producing 9×10 or 90 data points per harmonic block. There exists here another kind of over-sampling that is effectively the same as time-averaging or filtering signals in classic signal measurement systems. But with PhaseNet, one has finer control over how the raw data filtering is apportioned into solution vector error, with this example showing that there is a distinct difference between measurements on spatial changes relative to count-rate changes. This is intended to be a simple example, and mixed-rate solutions can become much more sophisticated in general EM-node PhaseNet configurations.
The H matrix term of equation (3), depicted in
According to basic statistics, two harmonic blocks occur in 20 milliseconds, each block containing 90×10 or 900 dping data points as well as 10×5 or 50 solution metric points. Putting both blocks together, the 20 milliseconds of data collection creates a 1,950×150 sparse matrix, that can be solved to measure the space-time characteristics of the cars during that 20 milliseconds. This is a reasonably sized matrix to invert, provided inverting it at a rate of “many-times-per-second” is not required. The section on H-families and inversion explore this specific topic further.
Metric Solution Challenges
One challenge is that the matrix H in equation (3) is always singular because it is formulated initially using only rows derived from equation (2). Consequently, the matrix H is non-invertible and theoretically there is no single solution, f, to equation (3) but rather a multi-dimensional sub-space family of solutions. One illustration of why equation (3) must always be singular is as follows: all counters on all ten cars speed up at a rate proportional to their distance from the average location of the ten cars, while at the same time all the cars begin to uniformly move away from the center of the ten cars at a rate also proportional to the distance from the center. The dpingforms are then identical to the case where all the cars are standing still. There are other such interesting singular modes. It will be seen that this challenge is quite manageable using Moore-Penrose type matrix solutions as well as general Singular Value Decomposition (SVD) analyses of the H matrix, along with appropriate “external knowns” applied to how the singular properties are regularized. Kalman-type filtering as well as the gentle (i.e., small) zero bias are designed to provide band-aids to this singularity issue, but the main thrust in handling it comes from explicit singularity-mode regularization.
A second challenge is referred to as the “double frayed edges” problem that is evident in equation (2), effectively a row in the matrix. At the start of the one second within the first harmonic block of pings, all cars are recording pings from prior harmonic block epochs, and in the last harmonic block, pings have been sent out from the cars during that epoch, helpful in solving the metric parameters of that epoch, yet the pings have not yet been received and recorded by other cars and hence have not been included in the two primary harmonic blocks. Several approaches to managing the double frayed edge challenge will be presented, with the preferred approach already alluded to in
A third challenge is the simple but nevertheless subtle interpolation issue when mixed rates between data production and solution point production are used. The metric solution waveforms within the f vector are discretely sampled on the one hand, but are effectively representing a band-limited pseudo-continuous wave on the other hand. As in classic digital signal processing, sequences of digital samples are viewed as Nyquist-band-limited sinc functions, linearly combined. The practical import of this is that certain interpolation methods must be used in constructing the H matrix, which tends to add non-zero elements to the H matrix, making it less sparse.
A fourth challenge that is not necessarily contained in equation (3) but is almost always present in any practical application, is how to situate the resultant f vector in an agreed framework. This challenge is the subject of an entire section below. In summary, a wide range of options exist that are fundamentally incorporated with the PhaseNet protocols. The H-matrix organization of
A fifth challenge is that space-time solutions are formed not for merely twenty milliseconds but for an indefinite time period. Given the double frayed edge challenge, a preferred solution handles network initialization non-uniformities on the one hand, and as time progresses, collects enough information to make snapshot solutions for past epochs of the overall network. GPS engineers will note a similarity with what motivated the introduction of Kalman filtering, first explicated in 1960. Kalman filtering plays a strong role in optimizing PhaseNet solutions, extended to mixed-rate, mixed-epoch interacting waveforms as opposed to the more familiar advancing and discrete system-state formulation.
A final highlighted challenge is that all the cars move, and links between cars are always changing. This means that the H matrix must adapt in time to the coarse geometric configuration of the network, including the existence and non-existence of the ping-links between the nodes themselves. This particular challenge gets to the heart of the adaptability of PhaseNet to ever-changing conditions, including, but not limited to, link existence, link quality, network configurations, mixed technologies, fluctuating precisions, and coarse vector changes beyond pre-set specifications.
From Raw Solutions to Structured PhaseNet Solutions
For the baseline embodiment of the ten cars in the gymnasium, despite the challenges presented above, pseudo-inverse solutions to equation (3) can be obtained on the blocks of data and the overall procedure applied one epoch to the next, resulting in dynamic (motion) solutions of the cars relative to one another and the individual counting rate variations relative to one another. There are large matrices involved that generally require re-inversion every few seconds because of range and coarse direction dynamics. The matrices do require regularization in their pseudo-inversions, which adds a small amount of overall error to the solutions, but it works. This may even be called the raw PhaseNet solution. It has at least organized the data collection and solution formation in reasonably complete terms.
The central PhaseNet challenge, which this disclosure addresses and fully meets, is to turn the raw information content inherent in the data collection procedures and the metric solutions outlined in equation (3) into universally scalable protocols, shared structures, hardware-agnostic procedures and modular algorithms. The term “plug and play” comes to mind. From cars on a gymnasium floor using audio communications to space probes using laser communications, a generic PhaseNet enabled node should cooperate with any other PhaseNet node or network of nodes, and together form optimal space-time solutions. The raw mathematics falls into line once a PhaseNet foundation is in place.
To attain the necessary universality of functionality between applications and physical instantiations, time-positioning approaches including differential GPS, WAAS, e-911 cell location, blended navigation methods using INS and/or accelerometers, precision timing and navigation approaches and two-way time transfer methods may be fully described in PhaseNet topological terms, enhanced through PhaseNet networking principles, and extended by using PhaseNet shared protocols. Translating existing methods into PhaseNet architectural terms and structures requires understanding how pings, pongs, and pungs are accomplished in any particular prior art system, followed by how existing algorithmic solutions relate to the predictive PhaseNet solution families and the asymptotic PhaseNet solution families. A properly constructed PhaseNet architecture accommodates existing mathematical approaches. If it requires extension or modification, it has not been designed properly.
This last point is possibly the most subtle yet important distinction between PhaseNet and prior art approaches to space-time calibration: PhaseNet is designed to be a general network operating system for specific space-time calibration approaches, including GPS, DGPS, and its related systems. Productization of the space-time calculating engine found in GPS receivers, combined with a counter, replete with generalized information source inputs and solution family outputs, is an important difference between PhaseNet and existing methods. A GPS receiver contains a sub-unit that routinely collects signal information and cranks out space-time solutions, while a “PhaseNet Core,” be it software or hardware or any combination thereof, performs the same function for any device that communicates (or just listens, e.g., a GPS receiver itself). The product of PhaseNet is this universal core, often referred to here in this disclosure and elsewhere as a Space-Time Calibration Unit or SCU.
The Generic Space-Time Calibration Unit: SCU
With reference to
The core circle in
The outer circle surrounding the core is split into four parts. These outer circle sections are referred to as “managers” in that there exists a wide range of options for how to physically instantiate them. Below, the baseline embodiment implements these managers as processing loops with associated high level structures managing the data within the loops.
Finally, the truncated second outer circle in three sections are the drivers for collection and communication of raw and processed data, including interfaces and data exchange with instruments and systems, which are largely self-contained instruments computing their own space-time calibration functions, with the most common type being a GPS receiver.
Universal PhaseNet Data Structures
The architecture of both hardware and software SCU's is built around the PhaseNet “Qlocknode” or just “Qlock” structure, or “qlockstructure.” These terms are intended to highlight participation and specific attributes within a set or group of cooperating PhaseNet nodes. The “q” on what otherwise would be “clock” highlights that the SCU/PhaseNet structure counts like a typical clock, but it does so explicitly within a network of other such counting nodes using shared communication protocols.
A key engineering notion associated with the qlockstructure approach is that an arbitrary dynamic network of disparate communicating devices shares a common geometric and computational framework in order to be interoperable and scalable. To be truly scalable across spatial scales from intra-CPU circuitry through cis-lunar communications networks, all nodes at some level share pre-agreed structures and dynamic communications protocols inherent in those structures.
The following paragraphs step through the Qlock hierarchical structure, or qlockstructure: using a Matlab type formalism, the following is the top tier organization of the Qlock structure:
To participate in a PhaseNet network, a component, device, instrument, or vehicle either instantiates this structure itself or, in the case of components or devices streamlined to collect and transmit ping data, or non-cooperative objects such as radar targets, have this structure located within the network. In other words, no matter where this actual data structure is physically located, all PhaseNet nodes have this basic structure.
Stepping through the Qlocknode structure begins with the name itself, which in C/Matlab code instantiates a generic data structure conforming to the text fields and sub-structures inside the parentheses. This formalism associates four broad and multifaceted sub-structures with the text fields just before them, each of which is described herein. These sub-structures are designed to continually evolve as usage models extend, and furthermore, it can almost be anticipated that the number of core sub-structures will increase beyond four once actual industrial-scalability occurs, i.e., wide deployment of PhaseNet-enabled systems is expected to put pressure on clarifying and expanding even the highest level of PhaseNet organization.
Initially, the four sub-structures are: node specific information, the ‘info’ text field and its associated info_struct; raw data information that is being collected and shared, dominated by D3P data and rolled up in the data_struct structure; all information associated with space-time solutions or other information derived from the ‘data,’ stored in the solutions_struct with the text field ‘solutions’; and finally the broad category of information associated with communication links between nodes, network topographies, real-time cooperation tracking, and even such items as the status of the availability of alternate information sources such as compass data, inertial navigation unit data and the like, all going under the text field ‘linqs,’ indicating a PhaseNet-defined relationship between a node and the external world. The ‘linqs’ field is the structure most likely to be expanded quickly into major sub-fields for any given PhaseNet application.
Stepping through the four substructures at the next level of granularity begins with the info_struct structure as it exists within the baseline embodiment:
There remains a high level split in data between node information that remains stable through the node's lifetime and is an inherent property of the node, and node data that is a dynamic operational characteristic of the node and its evolving relationship to the network the mode finds itself within. This split becomes clearer by looking at the constituents of node information:
In the baseline embodiment, some of these fields are not necessarily used, or their values are uniform across the entire set of cars. The idea behind these structures is that the same templates are used across all PhaseNet applications and hardware configurations. One important type of data, referred to as ‘ratings,’ relates to the quality of data and solutions associated with a given node and what it can contribute to the network. In many ways, this concept is akin to error analysis, though in PhaseNet it becomes more explicitly part of network solutions and the ‘weighting’ of input sources as a function of their perceived quality (both static and dynamically quantified).
The qlock_data field in the static structure identifies precisely what type of counting this particular node performs, including information on clocks on-board the node or accessible to the node. The qlock_data field also has inherent quality information about the local clock, to what extent precision oscillators are used by the node, and the oscillators relationship to the clock and to digital counters, if applicable.
Another concept within the dynamic structure, encapsulated by a still-broad framework_rating data structure, relates to the ongoing relationship and error estimation between a node and one or more external standards to which it subscribes. A very common situation is a given node's relationship to the GPS framework, for example, or more simply a node's latitude, longitude, (and altitude) relative to Earth coordinates. The specific dynamic information contained in this field relates to higher level relationships between a node and these external standards, while real-time error estimation of the actual solutions within these frameworks is contained within the solutions structure.
Another data field is the ‘harmonics’-type data, which contains high level information regarding ping rates, solution rates, harmonic block configurations and how the node organizes its data input to solutions output relationships both internally and within its local neighborhood.
The clock steering field may range from a null value indicating no clock steering is used to a very complicated sub-structure replete with a past record of steering the local clock to maintain rough synchrony with either a local network of clocks, or some external standard such as UTC (Universal Coordinated Time in its French acronym form). PhaseNet is designed to not require any clock steering, inasmuch as one of the main solved metrics is the difference between a local counter and some external standard such as UTC; it is often convenient to gently steer all clocks to some globally accepted standard such as UTC or GPS time (which itself is generally steered toward UTC).
With reference to the second of the four main sub-structures:
The pingform_data structure contains all of the raw information collected by the node through listening and count-stamping ping arrivals from other nodes. In the case of information sources such as, for example, speedometers and INS information, raw data outputs from these devices, as count-stamped by the node's local counter, would have similar raw data structures. The pingform_data structure is essentially what is behind the waveforms in
The pongBuffer text field, together with its associated pong_data data structure, is a communications buffer for the digital ‘back-channel’ data that this given node communicates to other nodes. Though they can have a variety of components and properties, pong data is considered ‘raw data’ in that nodes require receiving these pong data before they can form asymptotic solutions. It is thus a kind of shared raw data. One main property that distinguishes pongBuffer data from pingforms is that pingform data is compressed before placing it into the pongBuffer, so that pong communications are maximally efficient from an information standpoint. In general, pingforms are meant to be “oversampled” in time, meaning that ping sampling is at a rate sufficiently higher than the rates of system variations being measured such as spatial movements and counting variability. Thus a reasonable compression of data can occur by filtering raw pingform data and using lower bandwidth waveforms (further apart digital value time spacings) to represent the acquired pingforms within the pongBuffer data structures. Later sections will show how this operates in situ.
The ‘simData’ text field, together with its associated structure, exists only for a car simulation and would not be used in actual operation of the cars in the physical world. The simData structure is meant to contain “truth data” that would plot the courses of simulated cars, as well as contain simulated variations in counting between cars. This simData could then drive mathematical models of how the cars move about, communicate, produce data, and eventually create solutions. The solutions would be compared against the original simData, and error analysis could then be performed on the raw PhaseNet operations and algorithms. This simData structure as outlined here cannot incorporate by reference a physical demonstration.
The third of the highest level sub-structures is:
The ‘nominal’ solution is meant to encapsulate virtually all modern state-of-the-art methods and algorithms that attempt to calculate time and position of an object in pre-metricized space-time systems such as GPS. In short, a given node has a given estimate of its absolute position at a given local moment (as defined by its clock) when it sends out a ping, a second receiving node receives this ping at some point in absolute space, and straightforward “pseudo-ranging” solutions are formulated. Time and position are treated as absolute quantities with a notional error metric attached to those quantities. Straightforward geometry, dominated by triangulation and angle measurements, drives nominal solutions.
For many applications, including well-behaved examples of the baseline embodiment, the nominal solution is sufficient to meet given time and space accuracy specifications, especially when one or more nodes have been given very high accuracy ratings, effectively becoming a “master reference,” as is common in many existing systems. Systems wherein the nodes are closer together than one ping-time see that the nominal solutions are often close to the more fully constructed asymptotic and harmonic solutions. The scalability of PhaseNet will put a pressure on ping times to speed up over the years, thus shrinking the spatial scales over which nominal solutions are very close to asymptotic solutions and attempting to increase the time-bandwidth with which a given node's phase noise is being measured.
The ‘harmonic’ solution type is the raw solutions to equation (3), as regulated through pseudo-inversions stored in the H_inverse structure, and other ad hoc methods. These solutions, at least in the baseline embodiment, are in terms of variations in the system from moment to moment, tracking spatial movements, count variations, atmospheric variations, and instrumental delay variations. These solutions also are explicit in dealing with mixed-epoch interaction of waveforms, in which absolute space-time coordinate solutions similar to the ‘nominal’ solution family become quadratic formulations, which complicate the implementation of equation (3).
The harmonic type is split into local harmonic and global harmonic. The primary distinction between local and global is that in the local harmonic case, a small number of nodes form local groups and produce self-consistent equations of the form of equation (3) which can be solved for very short-term variations as a small group. In the global harmonic case, aggregations of many nodes take some time to gather pung data for the entire set, and the resultant matrices are therefore rather large. Most applications form local harmonic solutions, while higher precision systems and “standards-oriented” systems use a global harmonic solution approach. In the baseline embodiment of ten cars, an example of the difference between the local and global harmonic solutions is given below.
Finally, the ‘asymptotic’ solutions are effectively the post-hoc syntheses of the nominal and harmonic solution types. To the extent GPS receivers, speedometers, compasses, and INS data are data sources as well, the asymptotic solutions are where the “all-source, mixed-epoch, hyper-blended solutions” are formulated. Certain existing approaches in particular applications apply information blending principles to ‘nominal’ solutions on a case-by-case basis.
PhaseNet protocols and the resulting asymptotic solutions attempt to hardwire the all-source information into the short-period harmonic blocks, thus not only including such information in the variational harmonic solutions directly, but also helping to handle intermittent sources that are nevertheless useful during the scattered moments when they are providing information.
The baseline embodiment presents examples of these three basic types of solution, their relationship, and how different applications utilize different aspects of the various solutions.
The ‘self ratings’ text field and associated data structure is straightforward conceptually in that it attempts to associate an error and/or accuracy estimate with one or more solution types, generally on a harmonic-block by harmonic-block level basis. It is in effect the real-time error-bar plot of the solution(s). This data structure has an important role, however, in that the ratings data structure is used both as a binary gate when another node decides whether or not to include data generated by this node, and if so, how much to rely upon and weight the data generated by this node. The self-rating data becomes an active data structure primarily within the asymptotic solutions, but also in the harmonic solutions as weighting factors on the data, or even the gate on whether certain rows of the H matrix of equation (3) exist or not.
The fourth and, for the baseline embodiment, last main sub-structures is:
The linqs_struct is possibly the most important and wide ranging structure within the PhaseNet core set of structures. It contains all the information necessary to relate a given node to its external world and all the space-time information sources available to the node, in real-time and changing as the node changes according to its environment. The term ‘linqs’ encapsulates this interface between a node and all other nodes (its environment). The q in “linq” highlights its interaction with all other nodes or its environment with a PhaseNet protocol: sending out pings, receiving pings, count-stamping pings and other events such as pongs or natural beacons, storing information in pung packets, and communicating those packets. Perhaps the most important aspect of the linqs_struct is its ability to track and characterize node to external world relationships approaching ping rate and harmonic block rate bandwidths, as highlighted by the RRQ (Riccian-Raleigh-Quality) table. The RRQ table illustrates how networks of nodes handle an environment subject to echoes and jamming such as a battlefield or an urban core. This characterization of a linq or duplex linq at the millisecond and finer level is sorted by line-of-sight versus scatter criteria and signal-to-noise ratio. The RRQ may be refined according to the adaptability of PhaseNet and its ultimate scalability to any environment.
The overall organization of the linq_struct is closer in type to how network layer software keeps track of ongoing network connections and configurations than it is to the mathematical type of the solutions_struct, the raw data storage type of the data_struct, or the identity and properties description type of the info_struct. These differences in type largely drive the categorization of the four primary sub-structures.
The ‘linq_list’ structure is simply the list of both active and potentially active sources of information to the node, while the ‘linqweights’ structure represents the binary or weighted status of each one of those listed linqs.
The ‘linqvector’ data structure is fundamental to forming equations like equation (3). It contains the coarse direction vectors (the k's, in equation (2)), as well as coarse range values. The coarse range values assist in interpolations within the multi-epoch waveforms.
Both the linqweights and linqvector data structures are simplified forms of the RRQ table.
‘local_solution_groups’ is a higher level logic structure that attempts to understand local relationships between communicating PhaseNet nodes and how “closed form” solutions can be formulated in tightly defined groups of nodes. This structure contains data describing which nodes are connected, and through what collection of pings and pung packets, can harmonic (or nominal) solutions be formed. This generic structure is designed to be dynamic, tracking rapid re-configurations and possibly even changing from harmonic block to harmonic block. Local_solution_groups also keeps track of the unique status of certain nodes in local groups that have calibrated or “server-like” properties, or even simply a stand-alone GPS receiver with rudimentary or ‘wired’ (non line-of-sight) communications capabilities. ‘Local_solution_groups’ is primarily aimed at supporting and recording the wide variety of local harmonic solutions that can be formed; ‘regional_topology’ is a broad type of data structure similar to local_solutions_group, but primarily aimed at supporting asymptotic solutions and large PhaseNet networks. It still is geared toward forming variation solutions of the equation (3) type, while keeping track of raw network topologies that ultimately will be grounded in globally accepted standards and frameworks. Closely related to ‘regional_topology’ is the ‘topology_graphic,’ a structure that is an intuitive aid to programmers and PhaseNet users who wish to visually understand the status of a given Qlocknode, its available active linqs, and its relationship to an external network. It is anticipated that though the topology graphic may not be of use to the data loop operation or the solution loop operation, it will nevertheless become an important structure for programmers and users.
‘H_family’ is a structure that may possibly be placed inside the solutions structure next to the H_inverse structure, but in the present case it is placed in the linqs structure. The constantly changing network topologies and local group combinations/detailed geometry may encourage reformulating the H matrix in equation (3), and then inverting the reformulated matrix. Such a requirement would drastically increase processing demands. Instead, closely associated with tracking current and evolving linqs, more slowly varying ‘families’ of possible H matrices are tracked within the linqs structure, with particular H inverses then removed from those families and placed into the solution structure for tighter-loop operations.
The last data structure named ‘external_frame’ is meant to encapsulate the details of how a given node connects to an external space-time framework, e.g., the GPS frame. This can be as simple as the singular data structure, which effectively says “my close neighbor node, node Z, has a very good GPS receiver and I'm simply going to steal its values”, or as complicated as many sub-structures in a precision PhaseNet node that is cooperating with many other precision nodes attempting to support precision time transfer and data exchange between space-time calibration sites.
The PhaseNet structures outlined above are meant to provide a functional starting point for the baseline embodiment as well as highlighting a few items that go beyond the needs of the baseline embodiment (included because they are fundamental to almost all PhaseNet embodiments and applications).
Active Versus Passive Qlockstructures
The assignment of a qlockstructure to a node is the basis for adhering to PhaseNet protocols, combined with basic software operation. Note that PhaseNet principles can be applied to passive or non-cooperative objects as well as active participants.
In all cases, a PhaseNet-enabled set of nodes can instantiate a Qlocknode structure for the passive object, characterize the properties of the object by filling out appropriate fields and data structures in the four sub-structures, and proceed to collect information as a pong-type signal measurement (i.e., a ping sent out, reflected, and received by the pinging node). Variants to a pure pong include just one PhaseNet node sending out a ping with multiple nodes receiving the reflected ping, as well as some non-PhaseNet EM source pulsing the object, the reflected pulse being captured by cooperative PhaseNet nodes. Count-rate variations normally associated with a PhaseNet node can be treated as a null parameter for purely reflective topologies. Count-rate variations can still be calculated for situations where either an external EM pulse is illuminating the object, or some signal emission from the object is being received and one wishes to independently measure rate variations for what has become a virtual counter associated with the passive node.
Passive nodes do not contribute information to solutions in the form of new equations of the type similar to equation (2) simply because they contribute no data directly to the overall network. Hence, solutions that contain passive nodes may not be over-determined by the resultant equations, an intuitive and natural consequence. The same principles of solution still apply, however.
The Garden-Variety Qlock
The baseline embodiment and other PhaseNet applications have active qlocknodes.
The channel circle in
The counter box in
Finally, the CPU circle is included as a typical element of a normal PhaseNet node, though it is unnecessary if other nodes control the formation of space-time solutions for a given node. For instance, a cell phone without a CPU or with a very minimally capable one may be assisted by a mainframe within the cell network that performs the PhaseNet operation steps.
A First Sampling of PhaseNet Topologies
PhaseNet operates on the premise that communication is ongoing between nodes, or between a node and its environment. Given that all forms of communication have some finite speed, dynamics is therefor an integral aspect of PhaseNet operation. This may appear obvious, but
Solid lines indicate functioning duplex ping channels, dashed lines indicate mono-directional ping channels, and parallel lines indicate an active pung packet being pushed from one node to another. Though three instances of local group connectivity are depicted, an intuitive notion of continuous background time fluidly moving from one state to the next, replete with motions on the coarse direction vectors, would an animated version of
The PhaseNet Core Engine: Hierarchical Embedded Cycles
This manifests itself as repetitive and rate-related queries about whether a given structure requires attention, and if so, providing that attention. This highest level description will be familiar to those skilled in the art of real-time operating systems and associated software.
The hierarchy suggested by
The info_loop depicted in
The job of the linqs_loop, illustrated in
The solutions_loop is typically looped at a slower rate than the data_loop, because it need only meet the Qlocknode's requirements to generate a space-time solution, as opposed to the demands of the data_loop, which is actively managing count-stamping and subsequent storage of pings, pongs and pung packets.
With reference to
Other cases where intermittency of channels or extremely dynamic situations will mean that the solutions_loop has no applicable inverted H matrix available or, if it does, that inverted matrix has gone out of specification ranges pre-determined by the Qlocknode. In this case, the loop is designed to either default to lower precision solutions (sometimes to the nominal solution families only), or to flag the large loops that re-inversion is necessary to meet the performance specifications. (It certainly can perform inversions itself, if need be, without the need to flag wider loops.) As reflected in the solutions_struct itself, this loop may also be calculating classic nominal solutions using pre-metricized space-time. Other than CPU capabilities, there is no limit to the number of solution families that can be generated at any given instance, a useful feature in volatile or jammed situations in which raw-data-supply conditions change frequently, leading to solutions that inherently adapt to those instantaneous conditions.
The solutions_loop cooperates with the linqs_loop as a preprocessor to determine final network topography configurations and to calculate the various solutions.
With reference to
Special note should be made of the ‘switch’ statement inside the data_loop of
With reference to the SCU high level operation depicted in
Raw “f-vector-snippet” Solutions Using Harmonic Blocks
One approach to stitching together a sequence of f-snippets (clipped-epoch solutions to equation (3)) is to formulate equations and solutions across two or more harmonic blocks, introducing a new harmonic block of data and solutions each block time, to replace the harmonic block several blocks earlier. In addition, weighting can be employed such that earlier harmonic blocks which already have growing estimations (solutions) due to earlier block solutions can be differentially weighted relative to recently added blocks.
Before placing these blocks together, however, there is a different take on equation (3) and the harmonic block organization of the g and f vectors.
With reference to
There is in
Even the common path metric(s) use variational metrics as opposed to pre-metricized absolute quantities, and hence one can interpret the whole of
Likewise, when car A receives a ping at instance a, it is not at integral values of car A's solution waveform sinc pole points (or linear interpolation pole points in this case), thus interpolation implicating at least two solution points for each solution waveform is the rule. In the depicted case, the instance a is in the first half of harmonic block N+2, and hence the implicated spatial solution waveform points are both within that harmonic block, while the dcount waveform having only one point for each harmonic block necessarily implicates a solution point in harmonic block N+3.
In this example, ‘frac’ refers to fractions and the (1−frac) have already been pre-calculated, while ‘kep’ in the longer variables here refers to k vectors with additional ‘keplarian’ orbital elements that a satellite might need to keep track of. The code example demonstrates that actually filling the H-row with appropriate numeric values can be accomplished quite efficiently.
The rank-deficient (always-singular) matrix H is a manifest result of
This completes the general discussion on how f-solution snippets are formulated and solved; the next section which describes how PhaseNet software executes operations to feed the space-time calculation.
PhaseNet Initialization and Operation
In the baseline embodiment, a CPU manages PhaseNet data structures, the operation of pings, pongs, and pungs, and solution formation. The CPU may be inside an SCU, or a time-multiplexed general CPU.
Initialization of the data structures is the first order of business. The following description presents a detailed initialization scheme that entails ten cars, and explains how the CPU then manages the data flows of pings, pungs and evolving structures.
It was postulated above that the cars have already revved up and started counting. It is also assumed that before moving, each car establishes basic audio communications with each of the other nine cars using a chosen ‘audible’ or supra-audible carrier frequency, and that all 90 mono-directional communication links have been established and verified.
In the baseline embodiment, PhaseNet is now ready to initialize by populating its linq_list data structure with the identities of the nine other cars it is communicating with, along with any specific data about that car that it may require. An example of such data is the type of clock each of the other cars carries. Data is recorded within the linq_list structure, associated with the given node in question. As equations are established and decisions are made about linqs, reliability, and the like, required data about other cars is added to the linq_list data structure. The baseline embodiment stores nine letters A-J, in a given car's linq_list, while excluding its own identity. Each of the nine letters stores information about another car/node.
The cars ensure that ping data are properly being sent and received across all 90 mono-directional channels. Initializing PhaseNet in this example entails assuming that each car has a reasonably good clock/counter and that each car can start count-stamping every fiftieth zero crossing of its audio carrier wave. (This initialization approach is simplified; industrial applications would have more developed methods of ensuring proper generation and receipt of ping data.) A discussion follows of how the other nine cars determine which of the zero crossings any other given car is using as its reference.
The circuitry enabling car B to count-stamp the zero'th crossing of the incoming audio carrier is simple in this baseline embodiment, in which sample of the received digital waveforms are slaved to the local clock and thus the sample times are known relative to the clock inside car B. Using digital signal processing, fractional sample-time values for this zero crossing can be calculated. Thus,
Because packets are broadcast as opposed to transmissioned between pairs of cars, only 10 separate “audio channels” are needed in the current baseline embodiment instead of requiring 90 distinct mono-directional channels to share the same audio airwaves. Thus, when a car communicates a pung packet (as described below), it broadcasts to all other cars at once, and the other cars broadcast their pung packets simultaneously, as spread-spectrum multiplexing of the 10 individual audio channels allows.
The pre-processing of these raw data is very straightforward. There are two primary processing elements that turn the de-multiplexed zero-crossing raw data into data fit for placing into the data_struct.pingforms buffer: (1) subtracting the “symbol modulation bias” from the zero-crossing data as previously outlined, and (2) bandpass filtering the raw data using a low pass filter with a classic cut-off around 100 Hz. This is a deliberately low bandpass cut-off for this baseline embodiment, which focuses on 10 Hz level spatial variations of the cars, and 50 Hz count variability levels. The 100 Hz bandpass thus preserves the information relevant to these ultimate goals.
Once these two pre-processing steps have been performed on the raw pingforms, it will be necessary to store only 200 pingform points per second into the data_struct.pingforms data buffers, even though 1,000 virtual pingform points are part of the initial sampling. Less than one second's worth of data requires retention until it is overwritten with more recent data. Thus, each car collects 9×200 16-bit pingform samples per second or 3,600 bytes of information per second for placement into the data_struct.pingforms data Buffer. A ring buffer implements the data_struct.pingforms buffer, such that, for example, a new block of 3,600 bytes overwrites 3,600 bytes from two seconds earlier.
The data_loop procedure performs these operations just described, and the results are placed into data_struct sub-structures as appropriate, generally into data structures that have been assigned the label of the car from which the pings are being received. For the ‘baseline operation’ of the baseline embodiment, this empirical data flow is the most fundamental. In a sense, each car acts as GPS satellite for all the other cars. But rather than having known orbital parameters and synchronized clocks on such pseudo-satellites, they instead contribute sent pings and collected pings that, as a combined set, create a self-consistent space-time framework.
The pingform data are also organized according to harmonic blocks.
The pung structure associated with one harmonic block should have 81 other-node pingforms×10 pings per block×2 bytes per pingform data point or 1,620 bytes of information if no down-sampling or compression is used. This amounts to 18,000 bytes of pung information per channel per second, exceeding the channel capacity. Above, it was shown that only 3,600 bytes of pingform data per second were stored in the pingform structure, thus limiting the data transfer rate to 10 Kbps. One of the goals of PhaseNet is to reduce “PhaseNet Pung Overhead,” the communications demand for the pung channel, to only a small percentage of a given channel's data carrying capacity. The baseline embodiment does not meet that goal; at the very least, the pung data rate must be below the channel capacity.
This is where classic data compression comes to the rescue.
A Detailed Look at Memory Ring Buffers
PhaseNet applications, including the baseline embodiment use ring buffers, that is, memory that has “old and fully processed data” overwritten with new data. In the baseline embodiment, a three second rule for harmonic block data storage and ring buffer flow is used. In brief, an initial three seconds' worth of data is placed into memory, then the fourth second's worth and all subsequent data overwrites the harmonic block from three seconds earlier. The size of the ring buffer is an arbitrary choice driven by the fact that the solutions_loop often processes a short sequence of harmonic blocks that cross from one second to another, and it would be preferable if neither of those seconds of harmonic block data is overwritten during processing. A “third second” is allocated for memory swapping, while “at most” two seconds of data are being accessed. This three second rule is deliberately simple. Experienced engineers working with much higher data rates and finer time-resolution on processing harmonic block data can push these ring buffer requirements down to the tens of milliseconds or even smaller.
Again, for the baseline embodiment, all data_struct structures outlined immediately above (the pingforms and the pung structures) adhere to this ring buffer management, with the info_loop, the data_loop and the solutions_loop ensuring that data processing is properly segregated from memory management and the process of overwriting data.
PhaseNet software operation was introduced by first discussing raw data flow and data storage, but as
As previously described, the linqs_loop performs many tasks, and this section concentrates on how the linqs_loop manages instantaneous network topologies, including potentially swift changes in those topologies, thereafter supplying the solutions_loop with the appropriate family of solution frameworks, so as to reserve the solutions_loop for calculations rather than decision-making in highly dynamic, jammed or otherwise intermittent networks.
With reference to
Topology information is stored in the regional_topology structure. Operation of the linqs_loop includes constantly updating regional_topology. In the baseline embodiment, for the initial configuration, all cars register that ten cars are part of the regional topology and that each car can communicate pings with all other cars.
Initialization within linqs_loop also includes estimating and storing initial coarse direction and coarse range vectors. There are many ways to do this. The general idea is to determine coarse range to roughly one-tenth of a ping-time as projected into audio spatial distances, and to determine coarse direction to a very coarse five or ten degrees. These specifications later determined the accuracy and residual error of calculations performed in the solutions_loop.
A car in the group of ten can determine coarse range to each of the other nine cars according to the following straightforward method, as depicted in
Coarse direction can likewise be initialized and updated though the direction calculation may be more convoluted than the coarse range calculation. The good news is that, relative to the coarse range specification of one-tenth of a ping time, the coarse direction vector need only be known to a few degrees or even ten degrees for many applications, including the baseline embodiment. The way the cars will determine it, presuming there are no ‘directionality’ capabilities built into the audio communication system, is through an initialization process of comparing and triangulating on the full set (45 in the baseline embodiment) of coarse range estimates calculated above. The process is straightforward: Once two cars determine their coarse range, they may introduce a third car and draw range circles around the first two cars, as depicted in
The actual units and reference direction used by the coarse direction vectors are arbitrary, but must be specified. An external framework such as the gymnasium floor and walls, for example, is initially ignored by the cars. However, later, the cars may identify the locations of the walls and then use the walls as a set-wide agreed external framework. In this case, one car is designated as the external frame explorer and performs echo-location from its own location. As
The results of this cooperation and agreed framework is that the initial coarse direction and coarse range data is stored in the appropriate data structures. These structures are updated on an ongoing basis, with guidance from the solution families without repeating the initialization processes. However, processes are also established to ensure that the solution families adhere to the chosen external framework, not only to ensure accuracy in the coarse data structures, but also to ensure the PhaseNet space-time solutions remain fully compatible with classic positioning systems such as GPS.
H-Family Creation Within the LINQS_LOOP
The linqs_loop then proceeds to create the H-families and certain H inversions that the solutions_loop will make use of. The H_family_struct is the ultimate destination for the results of this aspect of the linqs_loop. The high level explanation of H-families was already discussed, and here are presented a few more details.
“H_family” refers to all mathematical relationships between acquired data and space-time solutions. GPS uses an N×4 matrix, where N is the number of actively received satellite signals; this matrix and its inversion belong as members of the H_family_struct, to the extent GPS is subsumed or utilized by any PhaseNet node. Just as shepherds whistle to dogs, not simply to convey instructions (round 'em up) but to impart timing and positioning information between whistles; Qlocks, by way of descriptions of the relationships between specific whistles heard (the data) and by way of actions taken in a spatial and timing sense (the solutions) belong as members of the H_family_struct.
This analogy emphasizes that equation (3) and its H element are interpreted as broadly as possible. The idea here is that PhaseNet protocols incorporate and support past, present and future methods of calculating time and position. This compatibility allows PhaseNet to be universally scalable not simply across small to vast spatial scales, but also across all industrial and scientific applications as well. The PhaseNet platform is flawed without this aspect. Thus, the H_Family label and its associated structure may potentially become a very complicated repository for signaling and numeric methods associated with a Qlock. Applications-level software engineers need only know how to relate vectors using equation (3); the H_family class of structures and functions tracks the details as directed by a Qlock.
This flexibility regarding contents of the H_family_struct does not imply that there is no preference from the start. A preferred embodiment of PhaseNet explicitly chooses the ‘multiple-epoch waveform equations’ or MEWEs as the default and recommended primary relationship between data and solutions, and hence the normal and default member of the H_family_struct.
These MEWEs are laid out conceptually in
The reason the two degenerate cases are immediately introduced along with the formal definition of MEWEs is to emphasize that even MEWEs are rather broad in the assumptions, approximations and constraints that can potentially be applied to them. A “PhaseNet-wrapper description” of most prior art space-time measurement systems is accommodated by the basic PhaseNet protocols and architecture.
Later sections give examples of the full MEWE approach for the audio-based cars, followed by replacing the audio with EM-based 802.11 where it is shown that degenerate MEWEs can perform quite well in gymnasium-scale applications for position measurement (though they begin to break down for higher bandwidth phase-noise measurement). Measuring higher phase noise bandwidth within a group of nodes is a factor behind using full MEWEs versus degenerate MEWEs.
Before moving on to specific examples of H_family creation, however, it is advantageous to discuss the two discrete axes of H_family members, depicted in
The vertical axis is the “Predictive and Intermittent” distinction between H_family members, a key pragmatic aspect of how PhaseNet operates. The PhaseNet architecture is designed to operate in increasingly dynamic, harsh conditions. The structures employed must be capable of evolving to more dynamic applications, and to more intermittent channels and data sources in the millisecond range. This may not be required for audio-cars not to collide in the gymnasium, but it can become important in life safety applications such as collision avoidance in urban canyons or on the open road. The ‘predictive’ aspect of H_family structures goes to the heart of this pragmatic goal.
The simple way it does this is by not just calculating one single H matrix or one single H-relationship between g's and f's, but a range of H's that may apply within the next few seconds to minutes of operation. The range can include statistics on whether a given channel will be available during a specific harmonic block period (10 milliseconds in the baseline embodiment). This is particularly important in packet-based communication systems such as 802.11 in which a given channel may be inoperative for seconds or more, at least from a ping-sending if not ping-receiving point of view. The range may also include predictive dynamics in the local group, in which coarse range and coarse direction vectors move through their tolerance ranges on sub-second timescales, indicating slow evolution of the H structure in relation to the harmonic block period.
The predictive axis of the H_family structure is primarily a real-time efficiency mechanism that takes into account what kind of CPU resources are available to a Qlock, how to best utilize register-level circuitry within the CPUs and how to properly schedule H inversion calculations in time for the solutions_loop computes f solution snippets as simple vector processing steps. While the predictive axis of the H_family structure is not absolutely necessary to PhaseNet operations, it is central to PhaseNet's application in harsh, jammed and intermittent environments. The baseline embodiment of the cars illustrates some rudimentary examples of H_family members within the two axes of
The initial horizontal position (vertical column) on the bottom of
The particular example of
One option not taken in the baseline embodiment is to simply invert the implied H matrix of
A preferred approach is to string together a few harmonic blocks into a single H and its inverse that represented the optimal current state of the system, then to consider likely variants around that optimal state. The fate of the single optimal H's inverse will be placement into the current_Hinv_struct structure of the solutions_loop as, usually, the most likely vector processing array within the solutions_loop (the most likely H-family member).
The Solutions_Loop: Weaving f-Vector Snippet Solutions into Error-Estimated Solution Families
The method by which the solutions_loop performs these collective operations at the component level has already been laid out in previous sections, with explanations of specific data structures and explanations of the info_loop, data_loop and linqs_loop operations.
It has been shown how ping data and pung data accumulate through data_loop processes and are available to the solutions_loop. It has also been shown how the linqs_loop keeps track of harmonic-block-level network topologies. The discussion now turns to how f-vector snippet solutions are formed in the baseline embodiment, and how these snippets can be strung together into error-bar encapsulated continuous space-time solutions for a given Qlock, its relationship to neighboring Qlocks, and their collective placement into one or more external frames.
For example, f-snippet solutions have already been described with associated discussions on how snippets can be strung together in a pseudo Kalman-type fashion. This section emphasizes on software-hardware processes inherent in the solutions_loop as a defined entity. The job of this entity is to compute space-time solutions and their associated error estimates. There exists a myriad of options available to implementers for specific algorithms and accommodating families of algorithms and solutions. The solutions_loop may be seen as a vesicle for a range of evolving algorithms, with an initial high level organization between classic triangulation-based solutions that ignores speed-of-communications delays between nodes or treat them as post-hoc corrections, interim harmonic solutions that isolate group-level intervariability, and the more scalable and robust MEWE-derived asymptotic solutions and the unavoidable reality that realtime data collection systems of any kind can only asymptotically define past metricized states.
Node-Centric, Local Network Space-Time Solutions
The most general form of PhaseNet solutions entails that a single node should determine its own space-time solutions based on neighboring nodes it is in communications with, where the notion of the linq extends this somewhat by treating internal instrumentation as linqs to some form of external node. This property of a single node is fundamental to the scalability and network robustness of PhaseNet.
As with all aspects of PhaseNet, the choices and details of precisely how to do this are deliberately and maximally flexible and adaptable to both application directives as well as improvements in technology and information sciences. This flexibility is built into the protocols and structures utilized to formulate ongoing matrix solutions and governs the time-dependent evolution of the matrices involved.
Perhaps the simplest form of this node-centric point of view is a combination of external de facto trust combined with a classic pre-defined metric space that forms the mathematical basis to express trust. In other words, a given node simply accepts the estimate of a neighboring node in that it was definitively at location xi, yi when it sent out pingi at globally synchronized (coordinate) time ti, the same given node trusts its own clock in that it received pingi at time tj, the given node collects such pings from several neighbors accordingly, and determines its location based on classic range circles as indicated in
Likewise, perhaps the most general form of this node-centric point of view is that a node's solution family exists within embedded and (using coarse-metric definitions) spherically expanding clouds of set-wide nodes, where quicker error-prone solutions can be initially formed relying only on local sets of nodes, while eventual global set-wide asymptotic solutions can eventually be formed for any given node as set-wide pung information is globally shared and made available to the node in question. Fortunately, this most general form of node-centric solution can be kept as an exercise in reference frame creation and operation.
The solutions_loop independently quantifies its own linqs, relying upon implied network topologies both local and global, incorporates pung-channel data into its own solution framework, treats nominal versus harmonic versus asymptotic solutions relative to the specified needs of its host instrument or device (the car), and how it presents (and represents) its solutions to other Qlocknodes.
Pre-Defined Metric Framework Solutions: the Nominal Solution Family
In GPS nominal solution approaches, clock-drift on client receiving devices becomes a central parameter in the known and anticipated deviations from geometric ideals, and thus there are more circles depicted in
The strength of this “pre-defined metric” approach is that it follows time-honored standard ideas. It works quite well for many applications in which meter-level spatial accuracies suffice or nanosecond-level time accuracies. The weakness of this method for use in PhaseNet-based networks is that it encompasses a whole host of “ultimate standards” questions (e.g., ‘who knows where who is and what gives them that authority?’), that questions do not affect PhaseNet's basic operation and tend to be responsible for at least some of the inaccuracy in solutions. PhaseNet harmonic and asymptotic solutions focus on the interactions and inter-relationships between elements in sets and subsets. Whereas nominal solutions attempt to account for errors in external-trust-based frameworks, harmonic solutions pro-actively try to measure the variational in the error. With harmonic solutions, it is as though corrections to the official ephemeredes of the GPS satellites that were updated every hour or minute are now updated every millisecond, not just because there are more efficient communication processes in place, but because the GPS satellites themselves can actively participate in group-harmonic solutions.
The Harmonic Solutions Family
Harmonic solutions get their name ‘harmonic’ from the utilization of harmonic blocks as a practical method to construct equations within sets/groups that either or both exhibit: (a) unknown interacting waveforms with inherently different underlying time constants (bandpass characteristics); and (b) non-trivial and essentially arbitrary delays between the waveforms of one node and another node. Said another way, the harmonic block approach replaces classic discrete-time interaction descriptions with short-snippet harmonic waveforms that retain delay characteristics according to the coarse direction vectors and coarse ranging. A huge motivating factor in the choice of using harmonic blocks, beyond the added fidelity afforded in handling mixed time-constant parameters, was the simplification of H-matrix row and column logistics that otherwise becoming unwieldy in discrete-time formulations for relatively dynamic systems and/or local solutions involving more than a few nodes.
The formal use of the term ‘harmonic solution’ in PhaseNet expands beyond its generative aspect of using harmonic block waveforms by also encompassing the purely variational nature of both input data and solution output. In simpler terms, the inputs are variations/changes in some otherwise intuitively defined metric, as well as the outputs being the same kind of changes or variations. As mentioned earlier, a ‘dx’ is just as legitimate as an ‘x’ as an element of the f-vector solution being calculated. One of the great benefits of using a variational foundation for the harmonic solutions, in conjunction with the approximation represented by the coarse direction and coarse range variables, is the construction of purely linear H matrix formulations for the interactions of arbitrary sets of dynamic nodes.
Raw algorithms used to produce the harmonic solutions are, subject to change, hence earning the title of ‘families.’ The basic solution method has already been laid out in earlier discussions of equation (3) and the associated H-matrix and f/g vectors. Taking into account the generic need for regularization because of the “double frayed edge” issues and the inherent singularities in variational formulations, harmonic solutions simply represent repeatedly solving equation (3). Streams of g-vector values pour in and f-vector solutions come out the other side of the vector processing core:
A given node defines its own version of a local group of cooperative nodes (which could include GPS satellites as part of the ‘local group’) defining the structure of the f and g vectors themselves (and, by extension, the structure of H). Thus, a node actively solves for its neighbors' f-vector solutions as well as its own, and likewise, neighboring nodes solve for the given node's f-vector simultaneously. Obviously if a local group is strictly defined as in the case of the ten cars, and an identical stream of equation (4)'s are created that apply to the whole local group, only one node needs to actually perform f-vector vector processing for the whole group and then it can simply broadcast solutions via the pung channel(s). The potential for time-multiplexed CPU and vector-processing loading across nodes is manifest, if all computing resources were kept fully busy, anticipating various network topologies, pre-computing H inverses continuously, thus creating a low maintenance f-vector solution engine.
Error-mitigation in loosely connected overlapping sub-sets of local groups is summarily depicted in
The initial solution from local group one, which may have one or more group members shared with local group two, can use the f-vector solutions it has to reformulate the H matrix (and its inverse) for group 2, and group 2 can thus perform a second iteration of solving for its own f vector using this additional information. Doing the same operation for local group two is also possible, hence the six total equations in ‘equations (5).’
One of the primary solutions_loop operations associated with calculating f vector harmonic solutions is to ensure that the proper H−1 matrix is being used in the vector processing step that actually calculates the f vector. The linqs_loop monitors the general current epoch and anticipated near-future epoch topologies as well as trying to anticipate intermittent ping channels, producing a small family of ‘potential H inverse’ candidates for the solutions_loop to use, but it is the solutions_loop that makes the final call on which exact H−1 to use for any given harmonic-block epoch (or short string of harmonic blocks). This gets to the heart of PhaseNet's realtime adaptability to deal with harsh and ever-changing network conditions in the hundredth of a second to hundredth of a second timescale: the harmonic solutions vector engine can constantly swap in and out H−1 from a small family of likely matrices associated with the current epoch, and if an H−1 is required that is not part of the pre-calculated family, the solutions_loop must flag the linqs_loop that a proper H−1 was not available for a given epoch and that a custom H−1 must be calculated for that epoch and supplied to the solutions_loop before it can proceed with a solution for the f-vector.
For the baseline embodiment of the ten cars, the harmonic solutions portion of the solutions_loop includes the steps described in the preceding paragraphs. For applications such as multi-aperture coherent data collection wherein differential drift between collection points is sufficient to “phase up” data collection, the harmonic solution generally suffices and there is little need to place solutions back into an external framework. For many other applications, however, there is either a general desire or critical demand to package harmonic solutions back into external metric frameworks. The experienced reader may recognize that this operation should essentially be an integration activity turning variations into absolute metric entities. Integration constants and “random walk” divergence of solutions are addressed in the process of obtaining an asymptotic solution.
The Asymptotic Solutions Family
It would not be entirely unfair to view the asymptotic family as simply the integration of the harmonic family, or as an independent peer to the two previously described solution families. Though the strictest ‘observables only’ mathematical formalism will always find the harmonic family of solutions to be on more solid ground, special classes of nodes cannot be easily defined that form the basis of the intuitive world of three-dimensional space and commonly understood time. The gravitational accumulation of nodes into semi-rigid structures is the historical precedent here: the Earth-centered earth-fixed coordinate systems. Consideration of ‘semi-rigid’ structures is akin to the previously introduced concepts of a coarse direction vector and coarse range variable, concepts that are central to the practical implementation of the harmonic solutions themselves. In any event, an objective is to maintain a level of rigor in defining core differences between solution families, where the accumulation of nodes into semi-rigid structures bridges the intuitive transom between the harmonic solutions world and a world using absolute metrics and defined standards such as UTC, ITRF, ICRF, and GPS (formally defined).
In the baseline embodiment of ten cars, while the nominal solutions sub-routine of the solutions_loop is providing coarse estimates of a car's location within the gymnasium using classic triangulation methods, and the f-vectors are being produced from the harmonic solutions sub-routine of the solutions_loop letting cars know in some detail how they are moving relative to one another, one of the cars may ask the question: ‘so where am I really?’ This is the job of the asymptotic solutions family to answer. Asymptotic solutions have emphasized the word ‘family’ over the member term ‘algorithm.’
The ‘background collision frame’ or ‘asymptotic collision frame’ are two phrases that the set physics materials describe wherein the very messy problem of rotationally interacting relativistic frames can be recast into a functional (and conventions-defined) absolute space-time. The set physics materials go to lengths to dissuade readers from considering this absolute space-time framework as anything philosophical or in some sense ‘real,’ it is simply a shared space-time metric wherein after some information is gathered by many nodes over a long time period, a globally defined (shared) space-time asymptotically aligns wherein two otherwise disconnected relativistic frames can describe collisions and other events in their past. A fascinating implication of such an asymptotic frame is the possibility of exploring black hole physics through an overlapping neighboring local-groups approach as opposed to a pre-metricized relativistic approach that produces physically unrealistic singularities.
In the baseline embodiment, simpler questions can be asked, such as how can the best of both worlds—the elegance of the nominal solutions and the detail of the harmonic solutions—be obtained? The following outlines a fairly straightforward hybrid choice.
Recalling the harmonic solutions derived from equation (2), wherein the coarse direction vector was introduced, and the coarse range that accounts for finite delays between nodes, a question arises as to whether these coarse entities can be made more accurate as more ping data is collected across an entire set. The short answer is yes: collecting more and more data may determine what the coarse direction vectors and coarse ranges ‘were’ in the past.
The right hand side of
Topologically Defined Metric Frames
A given topology of a set or subset of PhaseNet nodes can form the definitional basis for a metric space. Nodes in this definitional set are referred to as metric nodes. An ideal topology of metric nodes would be stable and node-node connections would be constant, whereas real implementations of metric nodes are highly redundant and expect occasional minor breakdowns in connections. The word topology is used here in its classic form: the description of connectivity and relationships in and amongst elements in a set.
Asymptotic Solution Example
In summary, the asymptotic solution family approaches must take into account these motions, while continuously re-examining coarse range and coarse direction estimates and the effect of noise on coarse ranging measurements and the application of harmonic solution data in the asymptotic solution formulation. Low bandwidth (classically ‘fixed’) delays in the instrumentation utilized by all cars is a non-trivial nuisance.
Of the many choices for algorithms that can handle all of these motion issues, classic noise, and delays,
The inset to
Equations (6), follow the simplified two-car metric outlined in the inset of
The last two lines in equations (6) a set of two equations and two unknowns, x2—0 and y2—0, representing the offset of car 2 at time 0. The ‘count’ values in the first two lines are directly measured from the raw pseudo-range values, and all of the ‘d_XXX’ variables are provided by the harmonic solutions family, thus being treated as constants.
The ‘asymptotic’ term in asymptotic solution families refers to refining and connecting assumptions and approximations made by the methods and algorithms. This is a central topic for the set physics material that deals with Planck-scale assemblies of PhaseNet nodes. In terrestrial applications of PhaseNet, where the speed of communications is significantly faster than the motion of the nodes, a one-step or possibly a two-step iterative process is possible with strong convergence properties. This convergence approach is used to correct for the coarse metrics in the nominal solution families and the coarse range and coarse direction vectors used to generate harmonic solutions. This convergence may barely justify use of the term ‘asymptotic,’ but as larger groups of PhaseNet nodes create better harmonic solutions, these benefits also accrue to the final asymptotic solution families of large defined groups and super-groups, with ever-refining space-time solutions as more past data are used to place nodes within the asymptotic collision frame.
Space-Time Calibration Unit (SCU) Output
All three solution families are available to the client node, which contains the SCU.
The previous disclosure described in detail the versatility of the design and application of systems implemented with the PhaseNet space-time calibration technique. The following description presents a specific implementation of the computations performed and solutions generated to achieve overall system operation with error correction.
A differential clock count value representing the difference between Ping 2 and Ping 1, ΔPingAB, can be expressed as
The following two equations express, in terms of ping counts, changes in the distance between nodes A and B, assuming that ping events are also transmitted from node B and received and count stamped by node A:
When the three components are combined and the coordinates of node A are included, ΔDistAB can be expressed as
The solution of the ΔCLKA and ΔCLKB terms is developed with reference to
Equation (24) is in the form of the equation to which matrix algebra is applied to solve for the unknown displacement values and changes in clock rates. The matrix equation is expressed as
The table below presents qualitatively how the system of equations that can be developed becomes more overdetermined as nodes are added to a network. The first row of the table indicates that two nodes present eight unknowns with two equations. The eight unknowns include, for each node, changes in clock time and changes in location in x, y, and z displacements. An example of the two equations is presented by equations (10) and (11). The table also reveals that, for an increasing number of nodes, there is a widening difference between a larger number of equations and a smaller number of unknowns. This difference indicates that a system network of a sufficient number of nodes can undergo changes to (by addition or subtraction of) the number of observed ping events and still generate unique time and location solutions for the system nodes operating.
The word “qualitatively” used in the previous paragraph connotes a need for particular attention in the design of working systems around the generic networking principles expressed in the table set forth immediately above. In particular, as but one of many examples, many systems in which there are short communication baselines on the order of a few kilometers or less begin to erode the independence of the duplex channels. Likewise, nontrivial and highly variable instrumental delay error sources also can become appreciable, explicit unknowns in H matrix formulations. Yet further subtleties in actual implementations entail the use of “knowns” associated with one or both of the nodes and the environment, such as, for example, one node being immobile or a node happening to be slaved to an optical clock and treated as a master clock. The primary important point of the table is to highlight the benefit of the presence of more nodes in a network.
With reference to
A first ping event, PE1, and a second ping event, PE2, appear as shown in HB1 and partly in HB2. The transmit time difference between ping events PE1 and PE2 is represented by (At2−At1), which is the time interval when ΔCLKA12 occurs.
The location solution LS1 for each of nodes A and B entails location interpolation weighting between successive location solutions, using the TM and RM interpolation benchmarks described for the time interpolation weighting.
With reference to equation (14), the following are location coefficient values of LS1:
For the five nodes, location solution 1 and clock solution 1 are arranged as
Similarly, for the five nodes, location solution 2 and clock solution 3 are arranged as
The values of θ, α, and φ are realizable based upon coordinates assigned to nodes A and B in the nominal solution. The remaining location coefficient values of LS1 and LS2 for the remaining solution indices and for successive harmonic blocks are determined in analogous manner.
In this embodiment, the system clock is defined as the average of the node clocks. Skilled persons will appreciate that many other system clock determination techniques are possible. For example, if one of the system nodes operates with an atomic clock, that clock can establish the system clock with extremely small clock drift. Also, in this embodiment, the first four nodes are specified as fixed fiducial nodes. They are placed in fixed and known locations and can provide a reference for the solution of other node(s). Additional equations are added to the system of equations described above to provide this clock and location determination. The equations used in this embodiment to aid in clock determination are:
In the example of solution vector calculation given with reference to
The following analysis presents a derivation of a system equation, in which on one side of the equal sign there is one scalar observable (or already solved) quantity and on the other side of the equal sign there is a linear combination of starting times for, and locations at the start of, the transmitting and receiving nodes. The start is defined as the beginning of a current solution iteration.
The following is a set of definitions of terms:
t(−) is system time at event−
ping_tx=a ping transmit event
ping_rx=a ping receive event
raw_ping_dist=actual (system) distance of ping travel
rx_time(−) is receive node's (noisy) proper clock at event−
tx_time(−) is transmit node's (noisy) proper clock at event−
tx_iter_blk_start=start of transmit iteration block event
rx_iter_blk_start=start of receive iteration block event
The analysis begins with equations (26) and (27):
The following matrix equation corresponds to equation (18).
The left-hand side is a column vector of ping events, the right-side is a product of a column vector of the delta location (x, y, z) and delta time solution variables and a two-dimensional “A” matrix of coefficients already known. For each node, the solutions for δx, δy, and δz are start position offsets and the solution for δt is a start time offset from, respectively, the finish location and the finish time of the previous solution interval.
In this embodiment, equations are added to the system of equations described above. The following equation is added to provide clock correction solutions:
It will be obvious to those having skill in the art that many changes may be made to the details of the above-described embodiments without departing from the underlying principles of the invention. The scope of the present invention should, therefore, be determined only by the following claims.