All-to-all communication in a sensor
network
EG
2006-07-17
Given are N sensor nodes. A pair of nodes is
either connected with a direct bi-directional link (if the nodes are sufficiently
close to each other) or the two nodes are not directly connected. Each node
contains its own unique message. The nodes must transmit and re-transmit to
each other messages such that at the end of the communications each node has
the messages of all other nodes. If we are dealing with isolated sub-networks,
a node must receive at least the messages of all nodes in the same sub-network.
The communication relies on
flowing and is carried out stage by stage. In each stage, one transmission
timeframe is assigned to every node. The transmission timeframe is sufficiently
long to allow a node to broadcast all messages it needs to transmit. The
messages are broadcasted to all the neighboring nodes. The transmitting node
decides what to transmit and/or re-transmits at the given stage.
The neighbors receiving the
message are storing it if the message is fresh and are ignoring it if the
message was already in the receiving node. If the message is fresh the receiver
node also adds this message to its own list of transmissions to be carried out
at the next stage.
The following diagrams show the
progress of flooding for several network samples. The diagrams are animated
where each timeframe representing a flooding stage. The numbers on the nodes
indicate the number of messages collected by the node. At the initial stage all
nodes has only one message (their own). The number in the bottom left corner of
the diagram indicates the aggregate number of all fresh messages received by
all nodes at the given communication stage. The red segments at nodes indicate
the relative portion of received messages out of the total number in the entire
network.
The simulator
is a single file program written on C++. The diagrams are built from the series
of postscript files generated by the simulator. The postscript files are
converted to animated gif files using ImageMagick
package (convert). The simulator uses also AFPL Ghostscript
package for converting the postscript files to PDF format (gswin32c).
The next step would be to
compare such a classical flooding scheme with an implementation of all-to-all
communication relying on network coding [Lun06], [Pakzad05], [Tuninetti05].
[Lun06] D. S. Lun, P. Pakzad, C. Fragouli,
M. Medard, and R. Koetter, “An Analysis of Finite-Memory Random Linear Coding
on Packet Streams”, Submitted to 2nd Network Coding Workshop NetCod’06, 2006
[Pakzad05] P. Pakzad, C. Fragouli and A.
Shokrollahi, “Coding Schemes for Line Networks”, to appear in IEEE
International Symposium on Information Theory – ISIT’05, Adelaide, Australia,
Sept. 4-9, 2005
[Tuninetti05] D.
Tuninetti and C. Fragouli, “On the Throughput Improvement due to Limited
Complexity Processing at Relay Nodes”, ISIT 2005
* * *