POSIT:RWG Notes

From Notes

Jump to: navigation, search

Contents

Introduction

RWG is POSIT's implementation of ad-hoc networking. Ad-hoc networking allows phones to communicate with each other in peer-to-peer mode in the absence of WiFi or mobile infrastructure.

RWG stands for random walk gossip algorithm, a protocol for transmitting messages through a partially and intermittently connected network of the kind one might expect to encounter during a disaster scenario. It was developed by Professor Simin Nadjn-Tehrani and her PhD student, Mikael Asplund, at the Real Time Systems Laboratory at Linkoping University in Sweden.

As described in <ref name="rwg1">Asplund and Nadjn-Tehran, 2009</ref>, RWG is a partition-tolerant manycast algorithm designed originally to work in disaster scenarios. RWG uses a store-and-forward mechanism to overcome partitions in an intermittently connected network. RWG keeps track of already informed nodes with minimal signaling, thereby reducing unnecessary transmissions and conserving energy. In experimental evaluation at Linkoping's RTS lab, RWG was shown to have a high delivery ratio, low latency, and low overhead.

The RWG Algorithm

The RWG protocol uses a manycast (as opposed to a broadcast) strategy. That is, rather than broadcasting the message through the entire network, it passes the message peer-to-peer until it has been received by (around) k nodes, where k is a parameter. This strategy is designed to reduce the number of messages sent by the individual phones.

A given node (phone) can be in one of two states regarding a particular message, m: uninformed (hasn't received m) or informed (has received m). In the informed state, the phone can be in one of three phases:

  • During the active phase the phone is the active custodian of the message and will attempt to forward the message to a randomly selected node.
  • During the inactive phase messages reside in a node (phone) waiting for an uninformed neighbor to appear.
  • During the silent phase the message has been successfully received by k nodes and phones will no longer attempt to transmit it.
Alt
Figure 1: RWG Algorithm

Each hop of a message from one node to another is preceded by a sequence of packet exchanges (Figure 1):

  1. The custodian sends a request forwarding packet (REQF).
  2. Neighboring (reachable) nodes reply with an acknowledge packet (ACK).
  3. The custodian randomly chooses one neighbor and sends an Ok to forward packet, containing the message (OKTF).
  4. The recipient node becomes the new custodian of the message.

Message m is retained by the custodian in the inactive phase even after it has been forwarded to another node. When an inactive node encounters an uninformed neighbor, it will become active and initiate a new random walk.

Table 1. RWG Header
0-78-1516-2324-31
packet lengthpacket typehops
group sizesequence number
origin
target
sender
time to live
target
informed bit vector

Each message sent by RWG contains a 32-byte header (Figure 1). The packet length is the total length of the packet. The packet type is REQF or ACK or OKTF. The group size determines how many nodes the message should be delivered to. Messages are uniquely identified by their sequence number and origin. Address fields (origin, target, sender) can be ordinary IP addresses or some other id, such as the device's MAC address, that uniquely identifies the node. The target field is used for those messages (OKTF) that a receiver.

The 256-bit informed vector is used to indicate which nodes have received the message. If a node with ID nodeId has received a message, then informedhash(nodeId) = 1. In other words, the hash value] of the node's ID is used as an index into the informed vector. This vector must be at least as large as k. A 256-bit vector would mean that the system could manage up to 256 nodes.

POSIT Implementation of RWG

Alt
Figure 2: POSIT/RWG Architecture

The POSIT implementation of RWG is shown in Figure 2. Its current implementation is written in Java/Android and is adapted from the RWG code developed at the RTS Laboratory at Linkoping University.

The current implementation relies on datagram sockets. Two different transmission modes are implemented. In infrastructure mode the phone relies on a local hotspot -- e.g., an Android phone set in WiFi hotspot mode. In this mode phones connected to the hotspot -- i.e., those sharing the same SSID -- send packets to the 255.255.255.255 IP address, which then forward them to other nodes in the vicinity. This mode works with off-the-shelf, non-rooted phones.

In adhoc mode, for rooted phones, phones transmit packets peer-to-peer without any reliance on a hotspot. In this mode the phones share an IP subnet (e.g., 192.168.2) and each phone is given a unique IP in the range 192.168.2.1 - 192.168.254. In this mode each phone sends packets to the subnet's broadcast address (192.168.2.255). This mode limits POSIT/RWG to users who are willing to root their phones.

In its current implementation, RWG is represented as an Android Service, which is started from PositMain:

case R.id.rwg_start:
    Intent serviceIntent = new Intent();
    AdhocService.setActivity(this);
    serviceIntent.setClass(this, AdhocService.class);
    serviceIntent.putExtra(AdhocService.MODE, mode);
    startService(serviceIntent);
    break;

The Adhoc Service sets up the phone's Wifi interface. It then creates the RWG protocol manager and starts the Sender and Receiver threads:

try {
   mRwgManager = new RwgManager(mMacAddress, mGroupSize);
   mRwgReceiver = new RwgReceiver(this, mRwgManager);
   mRwgSender = new RwgSender(mMacAddress, mRwgManager);
} catch (Exception e) {
   ...
}

Once started, RWG will send and receive packets delivered from the POSIT's application layer to other RWG-enabled phones through the Datagram (UDP) layer.

Field Tests

Alt
Figure 3: Field testing POSIT/RWG
NOTE: Field testing of POSIT/RWG was performed on an earlier prototype based on raw sockets (rather than datagram sockets). In addition to the benchmark testing that was performed at the RTS lab (See <ref name="rwg1">Asplund and Nadjn-Tehran, 2009</ref>), field testing of POSIT/RWG was performed at Trinity College in Hartford, CT. These results are described in <ref name="rwg2">Asplund et al.</ref>.
Table 2. RWG Experiment Scipt.
TimeActionTimeAction
00:00

Node A1 starts at C1, walks to find F1
Node A2 starts at C1, walks to find F2
Node A3 starts at C1, walks to find F3
Node A4 starts at C1, walks to find F6
Node A5 starts at C1, walks to find F11

00:09 Node A5 walks to C2
00:04Node A2 walks to find C2 00:10

Node A1 walks to C3
Node A2 walks to find F7

00:05

Node A1 walks to find F10
Node A3 walks to find F4

00:11Node A4 walks to C3
00:06Node A5 walks to find F12 00:12 Node A3 walks to find F5
00:07

Node A2 walks to find F8
Node A4 walks to find F9

00:13 Node A1 walks to find F13
00:08 Node A3 walks to C1 00:15 All nodes go to the end position E

The experiments consisted of five persons each carrying an Android developer phone running POSIT/RWG. The devices have a range of 300 meters when there is free line of sight. With obstacles the range decreases significantly. The nodes moved (by walking) in an approximate area of 350mx350m. Since the nodes will move away from the center of the map, the network will be disconnected most of the time.

A map of the experiment area is shown in Figure 3. There are three communication points C1, C2, C3 to which each node goes individually at least once during the experiment. At these places, the likelihood to meet some other node is higher than in the rest of the field. In the experiment area there were also 13 so called finds, F1, ..., F13, that were to reported when found by one of the actors. Upon locating a find, a manycast message was sent with the termination criterion to reach at least four nodes. Before the experiment, the clocks of all the nodes where synchronized to within one minute precision. The experiments were repeated twice and similar results were achieved in both trials.

The script shown if Table 2 was used to ensure that the ad-hoc network would be partitioned are various times during the experiment. The expectation was that despite these partitions, all messages (Finds) would be communicated to k=4 other nodes. The goals of the experiment were met with a 92% success ratio. All finds except F12 were delivered to at least four nodes, which was the delivery criterion. Out of the 13 packets, 7 (54%) were unnecessarily delivered to all 5 nodes. This was expected, as the protocol does not guarantee that only the required number of nodes receives the message. The most probable explanation for the message with F12 not being 4-delivered is that the nodes holding it did not discover any of the uninformed nodes. Unfortunately, we haven’t been able to verify that this is really the cause.

Resources and References

Personal tools
NSF K-12