This repo contains the implementation of the network evaluated in "A Real-World Evaluation of ESP32's Suitability for Use in Wireless Ad Hoc Networks".
We used Espressif's IoT Development Framework (ESP-IDF), which is based on FreeRTOS, an open-source, real-time operating system. Focussing on a simple and understandable architecture, we base the implementation of our logic on FreeRTOS's capability to run priority scheduled tasks. While this approach introduces a context switching overhead, which can result in increased latency, it also facilitates a modular layout. Our software architecture divides functionality related to the data link and network layer as well as the application into distinct tasks as depicted below. These tasks communicate via designated queues, and remain suspended while inbound queues are empty. They resume operation on receipt of input from other tasks and process messages sequentially.
Our network stack is designed to support sending of packets larger than the maximum frame size on the data link layer. To achieve this, a large packet may be split into multiple smaller fragments, that fit the frame size and can be transmitted directly. The header of a fragment, see the table below, contains fields that are used for reassembly of a fragmented packet, notably Frag ID, #frag and Frag no. A packet that must be split into multiple fragments first gets assigned a sequence number, which is subsequently used in the Frag ID field to identify all fragments that belong to this packet. Each fragment also contains the total number of fragments belonging to the packet in #frag, and the order of the fragments in Frag no. This information is used by the receiving node to reassemble the packet from its fragments before delivering it to the application.
Our approach does not depend on the underlying data link (DL) technology. Our implementation only relies on a callback, that makes the payload of a received transmission available as well as a function that takes a payload for sending and transmits its bytes. Currently, we base our implementation on ESP-NOW broadcasts, the lower part of the graphic above shows the relation between different tasks. Our implementation includes logic for forwarding, and filtering of packets a node needs to process. We strive to reduce the amount of data processed by the network layer, by filtering fragments early. For unicast-like fragments, this means a node discards them if it is neither the destination nor the next hop. In case of broadcast fragments, this decision is more complex, as they are addressed to all nodes in the network. A node needs to determine if it has already forwarded the fragment. Additionally, it needs to determine if the corresponding packet has already been delivered in its entirety to determine if an ACK needs to be sent.
To realize a desynchronization scheme described, we leverage FreeRTOS's capability to instantiate the Data Link task multiple times. This allows parallelizing the handling of data in the queue and basic reordering of fragments before they are sent based on their type.
Our network task realizes the core functionality of the system, taking on the responsibility of multi-hop routing and reliability mechanisms. In order to offer a reliable broadcast mechanism, the task needs membership information about peers in the network. This information is maintained via heartbeats sent to a leader node that in turn distributes a current groupview periodically, see Groupview and Heartbeat Task for a detailed description. The network task itself has two main responsibilities that are logically separate: packet reception and packet (re)transmission.
Once a fragment has passed filtering, it is handed over to the network task via the DL Receive Queue. If the fragment in question belongs to a packet that has previously been delivered, the node retransmits the corresponding ACK and discards the fragment. Otherwise, the fragment passes several processing steps, that we will briefly outline below: First, relevant routing information is derived if the fragment type warrants it. Second, the fragment is forwarded, if applicable. Third, data packets are assembled from their fragments and delivered to the application.
Routing fragments (RREQ and RREP) are used to derive information about the topology of the network and establish routes. When processing a fragment of type RREQ or RREP, a new route to the source is established, if the sequence number of the fragment is larger than the last sequence number associated with the route entry. If the current node is also the destination of an RREQ, it responds by sending a RREP back to the source of the fragment. Additionally, broadcast fragments are taken into account only if no suitable route for the acknowledgement is currently known (This introduces the possibility for cyclic routes). This is to prevent the introduction of slow routes, due to the delay of broadcasts. The necessity of establishing a route through the last hop of a broadcast packet is derived from the need to send ACKs in unicast fashion to the sender of the broadcast.
The forwarding logic differs based on the type of the fragment in question. The network task forwards unicast fragments to the next hop according to the routing table, while broadcast fragments are forwarded as broadcasts again.
The last step in processing incoming fragments remains their assembly into packets and delivery to the application. All received fragments corresponding to one packet are buffered together until the complete packet has been received. The complete packet is then reassembled and handed over to the application via the Application Queue as depicted in the picture above. Receipt of the packet is then signaled to its source, via an ACK, and the packet is marked as delivered.
When the application requests transmission of a packet, it is placed into a buffer containing all packets that have not been acknowledged yet. The network task uses it to store relevant state related to the (re)transmission process of each packet and clears it after all ACKs have been received. We offer broadcast and unicast transmissions, both achieving reliability through the use of ACKs and retransmissions.
Once a packet is enqueued in this buffer, the network task regularly checks the state and takes appropriate action to get the packet delivered. Necessary steps include:
- Route Discovery: If the routing table does not contain information about the path towards the destination, the node initiates route discovery by sending a RREQ.
- Initial Transmission: Once a route is established, the node sends the packet. It starts by splitting it into fragments as, that can then be sent over the network.
- Waiting For ACKs: After the transmission, the node waits for the arrival of ACKs from all destinations.
- Timeout and Retransmission: If not all expected ACKs have been received after CONFIG_PACKET_RETRANSMIT_TIMEOUT, the node begins retransmission of the packet and goes back to waiting for ACKs. This is attempted a maximum of CONFIG_PACKET_MAX_RETRIES times before giving up. These values can be configured to tune the network stack.
One notable difference between unicast and broadcast packets exists in the retransmission mechanism. When the timeout interval for an unicast packet is reached and no ACK has been received, the node starts the route discovery process anew. Once a (new) route has been found, the packet is transmitted again the same way as in the initial transmission. In the case of a broadcast packet that reaches the timeout, the node switches to individual unicast transmissions to nodes whose ACKs have not been received.
Our broadcast mechanism relies on the availability of membership information of peers in the network. To achieve this, we employ heartbeats sent to a leader node, which then disseminates the groupview to all members of the network. To this end, the network task is complemented by either a groupview task, on the leader, or a heartbeat task on all other nodes. The leader is tasked with maintaining a consistent view of all peers that are currently participating in the network. It recognizes implicit leaves, when multiple, consecutive heartbeats of a node are missing and informs all peers of the changes in membership status.
The independence of the underlying network enables the ability to create custom applications for ad hoc networks only restricted by free memory and flash.
Setup the ESP-IDF toolchain as described in https://docs.espressif.com/projects/esp-idf/en/stable/esp32/get-started/index.html. Simply build an run the project from the root directory by running
idf.py flashDebug Output is available via
idf.py monitorWe tested the code with version 5.3.1 of ESP-IDF and ESP32S3 with 16MB flash memory.