Tuesday, March 26, 2013

Toward Reliable Virtual Wire Interface Messaging

As described in the previous posting on the Virtual Wire Interface (VWI) the communication channels are not reliable and lack node addressing. Messages may be lost due to noise, collision, etc. The basic message passing provided by VWI or the original VirtualWire library is boardcast and the application must, if needed, realize a method of addressing and retransmission. This posting presents the Cosa VWI client-server example sketches demonstrating basic implementation techniques addressing these issues.

The first step is to design a protocol for addressing and retransmission. The simplest method is to add a client node address and message sequence number to the data messages sent from the client to the server. The server should transmit an acknowledgement message back to the client. The client will retransmit the message until an acknowledge is received (CosaVWIclient.ino). To keep things simple, data is only sent from the client to the server. The server only sends acknowledgements to one client at a time. 

There are error situation that are ignored in this simple solution. A final solution should include a maximum limit of retransmission. If this limit is exceeded the communication channel, server, should be regarded as inoperative; e.g. server is down.

The message structure for this simple protocol will be sent as the payload of the VWI message. The data message sent from client to server will contain the address of the client (32-bits), a message sequence number (8-bit), and data payload. The acknowledgement message sent back from the server to the client will contain the client address and the message sequence as received in the data message. Additional data could be piggy-backed with the acknowledgement. This is a common method of reducing messages in protocols. The above extra message fields are often hidden from the application and part of the protocol stack.

Note that messages are sent in binary form (struct) without any special serialization. The sending of a message  may be viewed as copying a memory block between processors. This works nicely in a homogeneous environment such as sending between Arduino's but would give problems between processors with different byte order/data representation. The data representation below is in a portable data width but the byte order dependents on the host architecture.

AVR is little endian (LSB first) while network order is big endian (MSB first). Many of the original VirtualWire examples use text strings as messages. Sending, for instance, an integer in textual representation (ASCII) avoids the byte order issue but may be inefficient, require longer messages, be more difficult to extend and requires more processing to translate to and from text.

// Data message type
struct msg_t {
  uint32_t id;
  uint8_t nr;
  uint16_t data[12];
};

// Acknowledge message type
struct ack_t {
  uint32_t id;
  uint8_t nr;
};


To improve the message passing between processors with different byte order the data could be put in a specific order before transmission and put back when received. This is know as network order. Typically the functions/macros hton() (host-to-network) and ntoh() (network-to-host) are used to force byte order on the data fields in the message.

// Encoder/decoder for the Virtual Wire Interface
VirtualWireCodec codec;

// Virtual Wire Interface Transmitter and Receiver
VWI::Transmitter tx(Board::D9, &codec);
VWI::Receiver rx(Board::D8, &codec);
const uint16_t SPEED = 4000;

void setup()
{
  ...
  // Start virtual wire interface, transmitter and receiver
  VWI::begin(SPEED);
  tx.begin();
  rx.begin();
}


The above snippet from CosaVWIclient.ino is the setup() section for the Virtual Wire Interface (VWI). Please note how the transmitter and receiver are declared to use the VirtualWire Codec and the Board pins D9 and D8. Also that the transmitter and receiver are separate objects.

In the loop() section below, the client constructs a message with the node address (0xC05A0001) and the message sequence number (cnt). In the example sketch the data send is two analog pin readings and a rotating data pattern.

  // Statistics; Number of messages and error count (retransmissions)
  static uint16_t cnt = 0;
  static uint16_t err = 0;

  // Message types (data and acknowledgement)
  msg_t msg;
  ack_t ack;
 

  // Initiate the message with id, sequence number and payload data
  msg.id = 0xC05A0001;
  msg.nr = cnt++;
  msg.data[0] = luminance.sample();
  msg.data[1] = temperature.sample();
  for (uint8_t i = 2; i < membersof(msg.data); i++)
    msg.data[i] = ((cnt << 8) | ((i << 4) + i)) ^ 0xa5a5;


The client will send the message and wait for an acknowledgement. A retransmission will occur if an acknowledgement is not received within the time limit, 64 ms, or the acknowledgement message was wrong.

  // Send message and receive acknowledgement
  uint8_t nr = 0;
  int8_t len;
  do {
    nr += 1;
    tx.send(&msg, sizeof(msg));
    tx.await();
    len = rx.recv(&ack, sizeof(ack), 64);
    if (len != sizeof(ack))
      DELAY(300);
  } while (len != sizeof(ack) || (ack.nr != msg.nr) || (ack.id != msg.id));


  // Check if a retransmission did occur and print statistics
  if (nr > 1) {
    err += 1;
    INFO("cnt = %ud, err = %ud, nr = %ud (%ud%%)",
     cnt, err, nr, (err * 100) / cnt);
  }


The client will collect statistics on the number of retransmission and the total number of errors. The DELAY(300) is used to reduce collision between retransmission and acknowledgements.

The server is even simpler then the client as it only receives data messages, sends acknowledgements and "processes" new messages (CosaVWIserver.ino). Below is essential section of the server loop().

  // Wait for a message
  rx.await();
  msg_t msg;
  int8_t len = rx.recv(&msg, sizeof(msg));

  // Check that the correct message size was received
  if (len != sizeof(msg)) return;
 
  // Send an acknowledgement
  ack_t ack;
  ack.id = msg.id;
  ack.nr = msg.nr;
  tx.send(&ack, sizeof(ack));
  tx.await();


The above retransmission solution must be extended with additional logic to handle multiple clients and/or channels per client. Also the protocol header (address and sequence number) may be compressed to reduce the size of the messages, and improve wireless bandwidth efficiency. There are also techniques to improve throughput and flow-control with a sliding window protocol. The above sketch is the basic framework for reliable messaging.

The two VWI example sketches may be used to benchmark the different Codec's with regard to error and retransmission rate. The bandwidth efficiency may be calculated from the statistics and the encoder parameters. The original VirtualWire Codec is 4 to 6 bits (+50%), Manchester 4 to 8 bits (+100%), 4B5B and fixed bitstuffing are 4 to 5 bits (+25%).

Typical retransmission rates are in the order of 1-5% depending on antenna, bit-rate/speed, noise and distance but also the length of the message; i.e. number of bits used to transmit the message. With even distribution of noise, collisions, etc, the probability of an error will increase with the number of bits sent.

Another factor is how well the software Phase-Locked-Loop (PLL) in the receiver code can regenerate the clock and sample the data channel correctly. Where Manchester code increases the number of bits with 100% the clock is perfectly recovered and error due to drift are almost zero.

The Next Step

The above examples are part of the prototyping for further development of the Virtual Wire Interface (VWI) in Cosa. The idea is to evolve VWI to handle both addressing and automatic retransmission as this is a very common usage pattern for wireless connections. The current proposed changes to the API are to 1) add a new network address parameter to the begin() method, 2) some new functions for retransmission control and statistics. All other details about the address matching and retransmission would be hidden.

An addressing scheme is proposed to be added to allow server and client address matching. Depending on the number of units needed in a small network the address would be 16- or 32-bits. A simple interpretation of the address may be used to distinguish between servers and clients. A servers would have a network address where the lowest byte is zero(0). A server would be allowed to have at most 255 clients. On recv() a server will match addresses with the same highest bytes in the address as the server it self while clients would match the whole address for acknowledgement frames.

VWI: [preamble, start-symbol, size, payload, checksum]
VWI+: [preamble, start-symbol, size, address, seqnr, payload, checksum]

The VWI frame contains a preamble sequence, a start symbol, frame size, payload and a 16-bit checksum. This would be extended (VWI+) to include the network address and a frame sequence number. The send() and recv() methods would be as VWI and the handling of the new frame fields would be internal.

1 comment:

  1. Although I can see that this code looks very promising I have some issues with it...
    I cannot find the sample code (like: CosaVWIclient.ino).
    Installation required me to install a lot more that I needed (only the VWI would have been enough for me).
    Now I'm kinda stuck...

    ReplyDelete