BWCM - 900MHz - Final Protocol Design

Basic Wireless Communication for Microcontrollers

Chapter 4 - Design Project 3: 900MHz Automatic Error-Correcting Data Link

Final Protocol Design

Because we are going to be operating over a half-duplex link and want a robust, simple means of communication, an XMODEM-type protocol seems to be the best choice. We don't need any addressing features since we are creating a point-to-point link on a frequency which shouldn't have any similar stations on it. If we wanted to develop something as quickly as possible, it might be best to just pick a standard protocol (such as the typical XMODEM which used to be used on telephone modems) and implement it on a PIC16F876. Since this is an educational project, though, we will design our own very simple protocol which is similar in concept.

Types of Packets

Our protocol will have four types of packets (given here with a short description and a specification of their structure):

DATA - contains outgoing message data [0xAB][0x03][length][packid][--DATA--][-CRC16-][0xAB]
ACK - an acknowledgement to incoming data [0xAB][0x00][-CRC16-][0xAB]
NACK - a non-acknowledgement to incoming data [0xAB][0x01][-CRC16-][0xAB]
RACK - a request for acknowledgement (sent by the transmitter if an expected ACK has not been received after some period of time) [0xAB][0x02][packid][-CRC16-][0xAB]

     Each bracketed object is a particular piece of data in the packet, called a field. Anything in brackets which does not have a dash or dashes (-) around its name is one byte long. The CRC16 field is two bytes long. The data field has a variable length (hence the length field to describe it). Each packet begins and ends with the flag byte, which we have chosen to be 0xAB since it has a lot of bit transitions in it, making it unlikely to be exactly duplicated by stray signals. The second byte of each packet is an indentifier which tells us what kind of packet it is right off the bat (0x00 for ACK, 0x03 for DATA, etc.) For each packet type, the CRC is computed over all data except the beginning and ending flag characters. This helps prevent packets from being interpreted as the wrong type.
     In the data packet, length is the length of the data field itself, in bytes. This will have a maximum length of 20 but can be as small as 1. Ideally, for efficient transfer (to reduce overhead), we would want a much longer length, perhaps 256 or even 1024. Unfortunately, the PIC16F876 doesn't have adequate internal memory to deal with packets that size. You could certainly modify the hardware and software to use external RAM and increase packet size, though. Also in the data packet, packid is a number between 0 and 127. It starts at zero and is incremented after each packet which is sent. The receiver can use this to prevent the reception of duplicate packets.
     The need for a data packet is obvious. We have also discussed before why ACK and NACK packets are needed for XMODEM type protocols (see here). We never discussed a RACK packet, though. The RACK packet is to deal with the situation where a packet is sent but the receiver never even hears it at all. If the transmitter doesn't receive an ACK in time, it will ask for it with the RACK packet. We could actually get away without the RACK packet by simply resending the whole data packet, since it is not very long. However, if you ever decide to expand the system to larger packet sizes, it can slightly help throughput in noisy environments if we just send RACK packets instead of repeating the whole data packet. Also, use of the RACK packet reduces further the chance of receiving duplicate data packets.
     As we will describe later, an escape system is used to prevent the 0xAB byte from appearing anywhere in the middle of the packet.

Flags, Variables, and Buffers

In order to keep track of what is going on, each station will need to maintain certain flag bits (to indicate yes/no conditions, they bear no relation to the 0xAB flag byte), variables , and buffers to hold incoming and outgoing data. The following are defined:

Flags:
WAITACK - The transmitter is currently waiting for an ACK for last data packet
CRCGOOD - The CRC from the last received packet shows that it was not corrupted
NACKED - A NACK was just received
SENDACK - A good data packet was just received, we should send an ACK
SENDNACK - A corrupted data packet was just received, we should NACK it
RXSTART - The start bit of incoming data was detected (note: this is not so relevant to the protocol itself as to the software UART receiver)
CUR_PACKET_VALID - The last packet received was good (CRC checked OK) (note: although this is indicated by SENDACK, too, SENDACK is cleared after sending the ACK, this retains its state until the next data packet is received)

Variables:
rx1_in_ptr - Pointer used by software UART
rx1_out_ptr - Pointer used by software UART
BITCOUNT - used by software UART
BITSAMPLECOUNT - used by software UART
BITSUM - used by software UART
RFRXBYTE - used by software UART
uart1_tx_cmd_length - Transmit command buffer length
uart1_tx_data_length - Transmit data buffer length
rf_packet_buffer_length - Incoming (from radio) data buffer length
lastID - Packid from last valid incoming data packet
outgoing_packID - Value to place in packid of next outgoing data packet
rx_CRC0 - Byte 0 of CRC computed on incoming packet
rx_CRC1 - Byte 1 of CRC computed on incoming packet
tx_CRC0 - Byte 0 of CRC to go with outgoing packet
tx_CRC1 - Byte 1 of CRC to go with outgoing packet
stated_packID - packid from last incoming data packet (valid or not)
TIMER_RFBITDELAY - used by software UART
TIMER_DELAY10MS - used by transmit routine
TIMER_SLOW - used to create an approximately 10ms timer update rate
TIMER_WAITCHANNELCLEAR - used to time how long it has been since the last received signal of any kind
TIMER_RACK - Used to count down until a RACK should be sent
TIMER_SEND - Used to time the delay from when data was last received from PC until when it should be sent over the radio, assuming that there are less than 20 bytes waiting (if there are at least 20, a packet will be formed and sent as soon as the channel is clear)

Buffers:
RX1 buffer - Holds incoming raw data from software UART
TX1_cmd buffer - Holds command packet (ACK,NACK,RACK) to be sent
TX1_data buffer - Holds data packet to be sent
RX_packet buffer - Buffer to assemble incoming packets from bytes received from the radio

Receiver and Transmitter Operation

     Before we get into the rest of the protocol details, we should make sure we are clear on how the actual reception and transmission of data over the air works. We'll discuss transmission first. There are separate buffers to send commands such as ACK,NACK, or RACK (TX1_cmd buffer) and data (TX1_data buffer). This is so a RACK can be sent while keeping the last transmitted packet ready to be resent if needed, and so that the receive side of the protocol can ACK incoming packets while the transmit side is forming and sending its own packets (the actual transmission of both ACK and data cannot happen simultaneously, of course, but there have to be separate buffers to allow the software to assemble a data packet in the TX1_data buffer while an ACK, for example, is being loaded into and sent from the TX1_cmd buffer).
     The transmission is done by a loop which sets the correct bit value on the output pin and then just delays for one bit length. Since a standard UART transmission and reception method is used by the software RX and TX routines, it is called a software UART. It uses the format shown in figure x, where a start bit is sent, followed by the 8 bits of the current byte, LSBit first, then a stop bit. So, 10 bits are actually sent per byte.
     Before each transmission, the receiver is disabled, the transmitter is enabled, and the system delays for 10ms, to allow the transmitter to settle and get ready for operation (the datasheet says that a maximum of 8 milliseconds is required, but it is best to leave a little extra margin). Then, two 0xFF bytes are sent, followed by a flag byte (0xAB), and then the data from the buffer, followed by the CRC (two bytes) and a final 0xAB. In order to prevent any flag bytes from appearing in the main part of the packet, if they are encountered in the buffer, the transmit routine first sends a 0xAC byte, followed by the actual byte (0xAB in this case) exclusive or'ed (XORed) with 0x20. To prevent 0xAC bytes in the buffer from being misinterpreted, the same thing is done for them (they are XORed with 0x20 and preceded by 0xAC). This is called escaping.
     The purpose of sending 0xFF bytes first is to ensure that the receive UART can synchronize to the data stream. Figure x shows the situation. If random junk data is coming into the receiver, any time a falling edge occurs, it will detect it as a start bit. If a legitimate transmission begins in the middle of when the UART is already receiving a junk byte, we want to make sure that the receiver sees a high level at the end of the junk byte, so that the next real start bit will appear as a falling edge (otherwise, if it might have been preceeded with a 0 instead of a 1, the 0-0 sequence would not create a falling edge). The best way to ensure this is to send a 0xFF byte, which is all ones except for its own start bit. We send two 0xFFs just to be even more tolerant of noise which could possibly corrupt the first 0xFF in severe cases. One would almost surely be enough, but two is no harm and insignificant additional overhead.
     On the receive end, the INT0 interrupt is set to trigger on falling edges to detect the start bit of the incoming stream from the module. As soon as a falling edge is detected, the INT0 interrupt is disabled and for the next 8 bit periods after the start bit, the TMR0 interrupt samples the input line 5 times per bit period. It then takes the majority value for each bit (if the majority of the samples are 0, the bit will be 0, otherwise it will be 1), assembling the received byte in RFRXBYTE. This byte is then placed in the RX1 buffer, which is a circular buffer, and the INT0 interrupt is cleared (because of any falling edges which may have occurred during byte reception) and reenabled to allow detection of the next start bit. For more about circular buffers, have a look here
     The main loop continually scans the RX1 buffer for flag bytes. If no packet is currently being received, it purges everything from the RX1 buffer up to the first flag byte, and purges everything if there are no flag bytes. This gets rid of the 0xFF bytes and any junk which may be in the buffer. Then, the bytes between the first flag byte and the next one are assembled in the RX_packet buffer. If the buffer becomes full before the second flag is received, the buffer is processed as if the flag were received. When a second flag is received, it is left in the RX1 buffer and the current RX_packet buffer is processed.
     The processing of the RX_packet buffer consists of checking its CRC, and then checking what type of packet has been received (using the type field, i.e., 0x00=ACK, etc.) For ACK, NACK, and RACK packets, a bad CRC results in them being ignored. For data packets, a bad CRC results in a NACK being sent. The rest of the processing can be explained in the following sections.

Typical Transfer Flow

     Here is how things are supposed to work: When unit A receives data from the PC, it stores it in the RX0 buffer (a circular buffer operated by the interrupt service routine that services the hardware UART). If there is no outstanding packet to be ACKed, the main loop takes the characters from the RX0 buffer and puts them into the TX1_data buffer. If there are enough bytes to fill a packet of the maximum size (20 bytes), then the RF transmit routine waits until the channel is clear. If there aren't 20 bytes waiting, the transmitter starts the timer TIMER_SEND. When new data arrives from the PC, this timer is reset. If the timer reaches zero, and the channel is clear, a packet (less than the maximum in length) will be formed and sent.
     Once the channel is clear, a DATA packet is formed (flag bytes are added, the data is escaped, a CRC is computed and added, etc.) and then the packet is sent over the air. The WAITACK flag is set to allow the unit to remember that it should expect an ACK. While WAITACK is set, no futher outgoing data packets will be sent. Also, while WAITACK is set, the timer TIMER_RACK counts down. If it expires before either an ACK or NACK is received, a RACK will be sent.
     In order to determine if the channel is clear, the transmit routine checks the timer TIMER_WAITCHANNELCLEAR. Every time a falling edge occurs on the RF receive line, the receive interrupt service routine (ISR) sets TIMER_WAITCHANNELCLEAR to a pseudo-random value which depends on the least-significant four bits of TMR0. TIMER_WAITCHANNELCLEAR is then decremented by the timer ISR every 10 milliseconds. Once it reaches zero, it stays there until the RF receive ISR detects another falling edge. If TIMER_WAITCHANNELCLEAR is zero, the transmit routine considers the channel to be clear. This implements a type of CSMA (Carrier Sense Multiple Access).
     On the receiving end, unit B's RF receive ISR gets the incoming data and places it in the RX1 buffer. Each time around the main loop, the routine getRFdata searches the RX1 buffer for flag bytes. It purges all data before the first flag byte, and then collects the data from this point until the next flag byte. This data is then de-escaped, and the CRC is checked, with the result being stored in the flag CRCGOOD. The routine process_rx_packet sends the data to the appropriate routine according to the type of packet (ACK, DATA, etc.)
     ACK, NACK, and RACK packets with bad CRCs are just ignored. DATA packets with bad CRCs result in the flag SENDNACK being set, so that a NACK will be sent when the channel is clear. When a good DATA packet is received, the data is immediately extracted and sent to the PC, and the flag SENDACK is set, so that an ACK will be sent. If a good ACK packet is received, WAITACK is cleared. If a good NACK packet is received, NACKED gets set, which causes the data transmit routine to resend the current outgoing buffer contents and clear NACKED. If a good RACK packet is received, the ACK or NACK for the last data packet is repeated (CUR_PACKET_VALID is used to determine whether the last data packet was good or bad).
     The transmit and receive routines operate simultaneously in the sense that there can be pending outgoing data at the same time as there is incoming data. While not a full-duplex link, it is a fully bidirectional link and each end is equal in status (there is no master or slave unit). Separate command and data transmit buffers are maintained so that the receiver can acknowledge incoming data (by placing an ACK packet in the TX command buffer) while there is outgoing data pending in the TX data buffer.

Error Conditions and Recovery

     We already discussed how "bad CRC" errors are handled. When designing a protocol, though, one must always be careful to think out (or draw a diagram of) the transfer flow to try to determine all of the possible situations which could arise. In designing this protocol and particular implementation, I tried to consider and account for all possibilities. As with almost any system, extensive testing must be done before one can be reasonably certain that no unforseen events can occur. This may seem like a daunting task, but after a few experiments you will get a sense for what types of events you need to be concerned about, and how to modify a protocol to avoid them. We will discuss just a few examples of such "gotcha" situations which one must look out for, and how to handle them.
     If station A transmits a packet and it is so garbled that station B never receives it at all, station B will never send any response. After the RACK timeout period, station A will send a RACK. Station B could think that this RACK was for the previous packet, and reply with an ACK. Station A would interpret this as station B acknowledging the current packet, and it would go on to the next packet of data, causing the current packet to be lost. To prevent this from happening, each packet is assigned a packID, which is a sequence number. This gets incremented with each successive packet. Each RACK packet contains the packID of the data packet it is referring to. When the receiver gets a RACK packet, it first checks whether its packID matches that received with the last data packet. If not, it sends a NACK regardless of the whether the last packet was good or bad. If the transmitter then sends a good packet with a new packID (not the same as the previous packet), the receiver will accept that packet and reset its lastID variable to this packID. Therefore, if the transmitter and receiver loose packID synchronization, it will be regained.
     Note that all types of packet carry a CRC, so that the link cannot be disturbed (sent into an unintended state) by a garbled packet. This CRC covers the packet type byte, length, and packID in addition to data (if it is a data packet).
     Another situation to consider: if noise on the channel prevents the receiver from sending an ACK, and then a RACK comes in from the transmitter, it might be possible for the receiver to buffer two outgoing ACKs and send both, causing the transmitter to think that the reciever was acking the next packet in addition to the current one. To prevent this, the TX command buffer can only hold one command packet at a time, and if a routine needs to load a new ACK or NACK command into the buffer, it is allowed to simply overwrite the previous one, even if it hasn't been sent yet. RACK commands are not allowed to overwrite previous commands in the buffer, though, since it does not matter if RACK packets are delayed.
     We'll consider one final case. If by some means station A manages to send the same packet twice, station B will detect it by seeing that the packID is the same as the previous one. In this case, station B will discard the packet, but will still ACK it, to encourage station A to continue on to the next packet.

Possible Improvements

There are many possible improvements you might make to this protocol or implementation. I'll suggest two. First of all, you might add addressing capability. That is, each station would only accept packets which were intended for it, allowing many stations to operate on the same channel. To do this, you would only need to assign each station an address, and then add an address field to each packet. Any packet received by unit A would be rejected if the address field did not match the address of unit A, for example.
The other improvement would be to make each unit reject packets (NACK them) whenever the PC it was attached to had RTS set high (signalling that the unit should not send any more data). This would cause the other side (call it unit B) of the link to keep trying to resend the last packet. If the PC attached to unit B tried to send more data, unit B's RX0 buffer would fill and it would signal to the PC to hold transmission. This would cause the "hold" condition to be transferred across the link from one PC to the other. The way things are currently implemented, if the TX0 buffer (buffer holding data to be sent to the PC) fills, additional data packets received from the radio are ACKed (if good) and then discarded.

BACK Table of Contents NEXT