# ACE: A Routing Algorithm Based on Autonomous Channel Scheduling for Bluetooth Mesh Network
## 5 ACE: A Routing Algorithm Based on Autonomous Channel Scheduling for Bluetooth Mesh Network
### Design and Implementation  
We implement ACE on the nRF52840 SoC from Nordic Semiconductor. The design points of the four main modules are described below. **Route discovery:** In the route creation phase, route discovery is done by sending heartbeat packets defined in the specification. Furthermore, every node setting the DST field of heartbeat packets to 0 xFFFF, and the TTL value requires a tradeoff between the network size and node's memory capacity in terms of realistic condition. A larger initial TTL value means nodes can be discovered by the further nodes and thus increase the size of routing table. For example, if a Bluetooth Mesh network is large-scale, but the resource of nodes is constrained, we should set a small initial TTL value to limit the size of routing table. Especially if the TTL value in the received packets is exactly one less than the initial value, meaning the element address of SRC filed is one of its neighbors'. We record ADV address for each neighbor in the neighbor table after setting up a stable routing table. **Routing Table Generation:** How to build a routing table for each relay node is a critical issue. Unlike most existing routing protocols, which need to record the entire routing path within a packet or send additional management packets to find the routing path. We explore the characteristics of BLE packets and novelly utilize two types of addresses in unmodified Bluetooth Mesh packets to simplify this process. One is the ADV address from PDU, and the other is the SRC address from the network PDU. The ADV address represents the address of next hop to the SRC element node, and the SRC element address represents the address of the destination element of this route entry. We choose minimum hop-count as the optimal routing metric for the latency reduction purpose. In the process of routing table creation, each node updates the ADV address of the next hop to the DST element by keeping the hop count minimal as a criterion. Concretely, each node obtains the hop count value by subtracting the TTL field in the received packet with a fixed initial TTL value. For example, if the received packet's TTL field is 125 and the initial TTL is set to 127, it means the packet has been relayed twice (\(127-125=2\)). With the above two modules, we give the answer to the first challenge that reduces the complexity of the routing algorithm by reusing existing mesh messages without additional traffic overhead for route creation. **Channel Selection:** How to deliver the packet to the next hop in terms of the routing table? Due to we do not consider a high delay and complex connection-oriented communication, sending messages to a specific next hop without overhearing by other nodes is a challenging issue. Novelly, We propose the following channel scheduling scheme, which operates autonomously to solve this problem: Each node should listen to one of the BLE channels after the network topology establishment phase. This specific channel is obtained by hashing the node's ADV address, which is expressed by:  
\[Channel=\text{mod}\,(Hash(ADV\_addr(k)),N_{BLE\_channel}-1) \tag{3}\]  
where \(N_{BLE\_channel}\) is the number of channels used by BLE and \(k\) represents a node in Bluetooth Mesh. \(N_{BLE\_channel}-1\) means reserving one channel for beaconing, which aims to cope with a dynamic network and will be explained further in the next part. The same hashing algorithm is used by all nodes in the network. Each node will use the algorithm to compute the scanning channels of all of its neighbors and record the computed results in the neighbor table. Now, if a node has a packet to deliver to the next hop, it should look up the neighbor table first and then send the packet to the channel, which the next hop node is scanning on. By executing the above process, we can not only make full use of BLE channel resources but also alleviate the potential collision issue in Bluetooth Mesh. In addition, the end-to-end latency can be reduced in ACE owe to no channel matching delay introduced.