Network Packet that allows maximum throughput

Question

I created a basic wireless system between two microcontrollers. Each uses the on-chip UART and an HM-TRP radio module to communicate with each other. Eventually I'll have a master-slave setup where many systems are slaves and one is master, but I wont have more than 40 units total.

My Idea

My packet format is basically 16-bytes long, and is similar to a UDP packet, but different in the following ways:

1st byte is an 8-bit address of the local machine.
2nd byte is an 8-bit address of the remote machine.
3rd byte through 15th byte is data
16th byte is 8-bit CRC checksum of all previous bytes.

With this setup, there could be big delays if any hardware is unable to receive any byte of data in time. I'll explain in terms of data.

Suppose Master (ID #34) sends to a slave (ID #12) the full data out numerous times in the correct format and assume FE is the correct checksum. Example:

12 34 01 02 03 04 05 06 07 08 09 10 11 12 13 FE

Now if slave is on and received nothing before this entire packet and the connection is excellent, there would be no problem. But lets say that the receiver didn't receive the first two bytes because of a network (wireless) error. It then receives:

01 02 03 04 05 06 07 08 09 10 11 12 13 FE 12 34

Since my packet format treats the first 2 bytes as machine addresses and the 13 after as data, then the receiver would discard the above data because it picked up 34 as the checksum instead of the expected FE value.

My new idea

Because I have less than 128 machines I'm working with, I thought of stripping one bit off each byte of data and fitting the data in the remaining 7 bits, then using the remaining bit as a flag to indicate start of data. Here's an example in binary:

0mmmmmmm 1rrrrrrr 1ddddddd 1ddddddd 1ddddddd ..... 1ddddddd 1ccccccc

where the m is local address in binary, r is remote address, d is data and c is checksum.

The advantage I see to this method is that the receiver knows not to start anything until it receives 0 as the most significant bit.

Question is, which of these formats are best for guaranteed wireless transmission over such a link and why? and if the formats I have described are not the best, then which format is better?

Remember, I'm working with 8-bit microcontrollers (specifically chip AT89C2051) so my resources are very limited.

Answer 1

Consider, as mentioned by Martin in comments, using SLIP to solve your framing issue. https://www.rfc-editor.org/rfc/rfc1055

It's simple, and stops you reinventing the wheel. The optimisation of sending END when idle can solve a number of issues too. Despite being a "non-standard", it's very widely implemented, for example on Cisco equpiment, and so you also have a way to integrate your project with standard networking if you choose to do so at a later day.

Answer 2

Basically, you're using the wireless channel as a 8-bit parallel channel using some kind of encoding inherent within the microcontroller. The problem you're seeing is that you can't detect where a frame starts or aligns.

The efficient approach would be to solve this on the physical layer (you're describing the link layer mostly). Apparently, there is a wireless symbol indicating the start-of-byte already (within the hardware codec or a library you're using) so you don't have to worry about byte alignment. If the physical layer could additionally supply a start-of-frame indication/symbol, that would be an efficient solution.

If you're stuck with the inherently byte-sized channel without extra symbols you need to encode the start-of-frame using that. Basically, you need to use a sequence that doesn't appear as user data. This can be a special bit combination (as you've suggested) or a byte sequence. You need to analyze the data you're expecting (and allowing) as user data to find a sequence that doesn't create too much overhead. If you're transmitting 7-bit data all of the time the HSB flag is a good choice. If you need 8 bit width it'll create 12.5% overhead which is not small.

You might be better off using a special byte as start-of-frame that doesn't exist in user data or is very rare. The same byte in user data would then have to be escaped in a way that provides easy decoding in the case of an intact frame and gets detected in the case of a partial frame.

Depending on your performance requirements, you might need to increase the frame size and CRC size to make this feasible. With a larger frame size, you could use a proper header with user data length indication, solving the escape problem.

Using SLIP as has been proposed will require some extension to SLIP which doesn't handle partial frames and lost bytes very well.