Bluetooth Mesh networking pathfinding algorithm development using Renode
Topics: Open networking, Open OS, Open source tools
Antmicro’s open source Renode simulation framework offers support for the Bluetooth Low Energy (BLE) protocol and multi-node simulation capabilities, which makes it a great environment for development, debugging and testing of local area radio networks, such as IoT consumer devices, smart home applications or multi-sensor telemetry systems. On top of device-level debugging through virtual machine code execution, Renode features probabilistic packets loss simulation, global network state analysis and, perhaps most notably in this case, automated testing of various network configurations with the Robot Framework.
One recent use case which illustrates the capabilities of Renode in that regard is a real-life radio network problem of gathering race car telemetry data. The use case involves data being transmitted by a mobile node (race car) and gathered in real time by a data acquisition node (pit-lane). These two nodes are generally beyond each other’s transceiver range, and the transmission is relayed through a network of intermediate nodes set around the race track. The network is responsible for passing the data packets through an optimal path, taking into account the mobile transmitter position and variable radio link reliability.
Developing distributed systems, especially in combination with mesh communication, can be challenging, but with Renode’s advanced simulation, testing and debugging features, this process can be greatly simplified. This note demonstrates how such a system can be developed exclusively in Renode based on the race car example, but this approach can be successfully applied in other use cases such as inspection drones, delivery robots and other mobile devices. A simplified version of the code for this demonstration, which can serve as a starting point for your own custom protocol developments, can be found on GitHub.
Finding the optimal path
The key feature of the network, necessary to meet the variable topology and variable link reliability requirements, is message pathfinding. Upon sending a message from the transmitting node, the network nodes need to spontaneously determine the data propagation path.
By default, BLE Mesh does not use routing. Instead, a message is propagated through multiple nodes by “flooding” the network - each node repeats the message to all the adjacent nodes until it reaches its destination node. This simple approach is sufficient for systems transmitting events or short data packets, such as lighting systems, but might not be efficient for scenarios like the one presented here, as long packets of complex telemetry data repeated between all of the network nodes would eventually choke the radio links with unnecessary data traffic.
Rather than flooding, the project demonstrated here implements the Dijkstra pathfinding algorithm for finding an optimal routing path through the node mesh. Unlike network flooding or simpler pathfinding algorithms such as Depth-First Search or Breadth-First Search, this algorithm considers the node mesh as a weighted graph, taking into account the “distance” between the traversed nodes. This metric can represent radio link characteristics such as signal strength or reception success rate, allowing the algorithm to prioritize reliable radio communication legs over weak or noisy ones. Once the pathfinding phase is completed, the actual data packet is transmitted through the established path. While the Dijkstra algorithm approach reduces the radio traffic and network energy consumption required for transmission of large telemetry packets, the pathfinding overhead makes it more suitable for rather small networks, with a limited number of nodes.
Simulating the BLE Mesh
The mesh nodes were implemented using Nordic’s nRF52840 SoC used in Antmicro’s Open Hardware M2 Smart IoT Module. The networking layer, including Dijkstra pathfinding and message handling, was built on top of Zephyr RTOS and its BLE stack. The nodes exchange radio packets in an ad hoc fashion using BLE connectionless communication in observer / broadcaster mode. This mode allows lower energy consumption and better communication efficiency in a network with mobile nodes. Usually the observer-broadcaster communication model is not directed, but this solution implements a way of sending direct messages using a node identifier added to the header of each packet. At reception, the node will check whether it is the addressee by simply checking the message header (limiting the computational overhead).
The network was designed so that all nodes have equal responsibilities, which simplifies the network architecture and, later, potential issues with restructuring the mesh in case of a node failure. Such a model distributes the computational overhead between the nodes more evenly rather than putting more strain on particular nodes with more responsibilities than others, which would not be desirable for such small IoT devices like the nRF52840.
As the development was carried out in Renode, the design could be validated with an automated test suite. The test involved pathfinding and evaluating the transmission efficiency in a number of custom node topologies. Initially, the mesh protocol and node application was developed using a basic, five node test case (as released in the repository linked to above). Throughout the project, the performance of the solution was validated with a randomized network topology generator - which is an obvious advantage that simulation-based testing can leverage over real-world testing involving physical nodes.
Developing distributed systems with Renode
The Bluetooth telemetry network developed in this project tackles a non-standard mesh networking scenario which takes into account variable topology, changing inter-node link conditions, as well as reliability and data rate requirements. This approach can be adjusted to a number of use cases with multi-node environments and mobile agents such as home automation systems (like a robotic lawn mower, for instance), shopping malls or automated manufacturing and storage facilities.
Using the Renode simulation framework allowed for rapid development of the data routing algorithm, as well as its validation against a number of automated test cases. This approach provides not only increased debugging capabilities, but also repeatable and deterministic testability - and Antmicro can help you utilize these features of our simulation framework in your project. If you’re interested in developing your next distributed system with Renode, reach out to us at email@example.com and find out how our engineering services can be beneficial for your custom use case.