Index

Sensor Distribution Network

1. Overview

The principle goal is to assure that multiple sources deliver frames that are temporaly correlated, so that if a process uses frames from independent sources, those frames are known to derive sensor readings taken a the same time.

The synchronizing mechanism is a stream object, is essentially a data buffering object with a single source and multiple sinks.

• A writers is blocked from overwriting a frame until all Readers have processed that frame; and
• all Readers are blocked until the Writer has completed providing the next frame.

This is a dataflow architecture, in that processing is synchronized by the data, but it is not necessarily an input-driven ("data push") scheme. It is anticipated that system throughput will govern the rate of data acquisition at the source.

1.1. Networking.

An implementation task is to decompose and distribute the processes on multiple nodes in such a way as to satisfy global timing constraints on throughput and latency. This task may entail:

• Sizing the streams to absorb variations in individual frame processing times.
• Providing transparent network communication of the data.

Phase 1. Sensor stream processes are local to the nodes managing their sensors. Theses process identify and extract individual features for transmission to higher level process (e.g. the Navigator). In the fortunate circumstance that such a "smart instrument" system suffices, then we are done, and can refine the sensory system under this scheme.

Phase 2. It is unlikely that all desired sensor processing can be done with the "smart sensor" paradigm. Processing high-bandwidth sources (e.g. video) will require multi-processing; synthesis of high-level features will involve multiple sources (e.g. stereoscopy); and processing will involve multiple stages (e.g. pipelining and interleaving). In anticipation of a truely distributed sensor network, the second phase incorporates stream-based synchronization and interfacing for network transparency.

The goal is distributed processing for static process configurations. Metworks are configured at either compile time or start-up, and the topology remains fixed throughout.

Phase 3. The third phase focuses on performance refinement and possible re-implementation of the Phase 2 network. Experience with coordinated sensor processing will expose the need for specialized processing, to achieve rate balancing for example. This phase provides the "final" infrastructure for the 2005 competition.

Further Phases. We should develop with a view toward moving ahead. Some areas of future enhancement include:

• Dynamic reconfiguration for situational awareness.
• Greater resilience to node and sensor failure.
• Incorporating special purpose hardware for front-end processing.

1.? Terminology

Term	Definition
frame	Any object that is communicated through the stream object. Many of these objects are image frames derived from the video source, but here the term is used generically for any data structure.
hiaton	A frame representing the absence of data. A process may need to indicate that its result in the current cycle should be ignored.
erron	A frame representing erroneous data. A process may need to indicate that its result in the current cycle is wrong, incomplete or produced from erroneous inputs.

1.? References

2. Stream Object (Very Preliminary)

2.1. Requirements

• Streams are generic with respect to the data they transmit. Streamed items may be arbitrary structures.
• Stream networks are static. At start-up all connections are instantiated and do not subsequently change.
• Streams are homogeneously typed. All objects passed through a specific stream instance are uniform.
• A stream has a single Writer (or producer) delivering items to the channel, and may have multiple Readers sharing the the items. Readers do not alter the content of the objects they read. Processes may read from many input streams and write to many output streams.
• Both readers and writers process each element in the stream, in order. This does not preclude acceleration operators that (for example) help a reader "catch up" by performing no data manipulation. However, such a reader does have to produce an element for every element it passes over.

2.2. Structures

2.2.1 Stream objects

Stream items are header cells containing references to data content. Although items are accessed sequentially, and so could therefore be indexed in an array, nxt links are used to leave open the possiblity of rearrangement. In the initial implementation, these links never change and are set up at creation time.

4. Initial Design ( under review)

1. Each relay channel is simply double buffered. The data can be any declared type. Space for frames may be statically declared at compile time or allocated at creation time. Dynamic allocation during run time is disallowed

   All Readers are concurrently consuming the current buffer, now (at least conceptually) while the Writer fills the ensuing nxt frame. Readers never "remove" (or alter) anything from the stream, they only advance through it. We want multiple readers to share frames.

   Representation options:

   • A 2-item circular list, in anticipation of extending to n-ary lists later.
   • Pointer variables now and nxt that are swapped when the Writer advances (i.e. Queue first/last references.)
   • Not to be used: Index arithmetic.

   Stream content contain pointers to the data items, rather than the data iself, in anticipation of future optimization, such as sharing objects among streams. However, the stream object must include allocated storage for "local" items.

2. Network Transparency. The communication network is transparent to the processes. Feeds from/to sockets are straightforward I/O operations, presumably. We will have to use compression of some kind, of course, eventually. The network interfaces are specialized of Readers/Writers.

3. Throughput. The system must function at the source frame rate. All processes visit every frame in each input stream, and for each frame cosumed, a frame is written to every output stream. A process doesn't have to perform computations on every frame, however. However, as a Writer, that process must produce a frame on each of its output streams in every cycle. As a matter of terminology, we need to distinquish several cases:
   • A process may perform the identity operation on a frame. At the outset, identity transformations are implemented by copying data from input buffers to output buffers. A safe form of copying (e.g. strlcpy rather than strcpy) must be used to minimize the risk of buffer overruns.
   • A special value called a hiaton represents the absence of a real object. Processes have the option of conveying no information in a cycle.
   • We may also want other generic objects, such errons, which propagate knowledge of erroneous conditions. However, this is not an immediate implementation priority.

4. Process Synchronization.
   • In must be guaranteed that all Readers have completed their operation on a buffer before the Writer can overwrite the data. (A weaker form of synchronization has been discussed in which Readers detect when a frame has been corrupted by a Writer. But for the time being, this idea is rejected). Since each stream instance has a fixed number of Readers, it makes sense for the stream object itself to monitor a reference count, blocking the Writer until this count reaches zero.
   • Conversely, all Readers must block until the Writer has completed filling the next frame. There are signalling mechnisms in Gthreads and other libraries to release a group of waiting processes, but these appear to be insufficient for the purpose here, since they cannot guarantee that all Readers have reached the blocking point (but only that no individual Reader is active during a write). Furthermore, a Reader may be waiting for multiple Writers, and there should be no prior ordering constraint on signals. A weaker synchronization has been discussed in which Readers detect when a frame has been corrupted by a Writer.

5. Discrete Latency. Consider the system below in which E coelesces streams produced with different latencies.

   
                      +----(B)----(C)---------+
                      |                       |                   
                (A)---+                      (E)--->
                      |                       |
                      +----(D)----------------+
   

   In effect, each stream delays a given value for one cycle, so the upper stream is arriving at E out of sync with the lower stream. A simple provision to balance the latencies is to introduce delay processes to balance the flow:

                      +----(B)----(C)---------+
                      |                       |                   
                (A)---+                      (E)--->
                      |                       |
                      +----(D)------(X)-------+
                                  {delay}
   

   X is just an iterated "identity" process, but the STREAM API should provide a secure version.