# 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
### Discussion of Design Details  
The previous section gives the general design and implementation of ACE, but there are still some design details that need to be discussed separately to present some performance tradeoffs:  
**Tradeoff between constrained resources and routing scale:** One of the major characteristics of IoT devices is its constrained resources. Take nRF52840 SoC as an example. It has 256 KB RAM and 1 MB Flash, whose storage size is relatively large among similar chips. But it still can not afford a large routing table. In terms of ACE, each routing table entry include a 6-byte MAC address of next hop, 1-byte TTL, 2-byte element address of the next hop, and 4-byte pointer to the next table item. The RAM occupied by this data structure is 16 B since the memory is not aligned for ARM-GCC and SEGGER ARM compiler. Theoretically, the maximum size of the routing table is 16,000. However, we need to reserve some RAM for BLE protocol stack, application code, etc. The size of the routing table available in the real scenario is much smaller than 16,000 entries. Besides, the RAM of other mainstream BLE chip is much smaller than nRF52840. For example, 64 KB for nRF52832 and 88 KB for CC2642. The computational overhead increases as the number of table entries increase. We evaluate the searching time for routing tables with different sizes. The result shows that the searching time and routing table size are linearly proportional. The nRF52840 chip costs about 1.64 us the check one routing table entry. For a massive network with 10,000 nodes, the time for searching the routing table would be 16.4 ms for each hop, but the delay of one-hop data transmission is 24.7 ms. So, the size of the routing table needs to be carefully designed. ```
start_timer(online_timer); start_timer(routing_update_timer); while1 do  pkt_rx \(\leftarrow\) packet_RX();  pkt_tx \(\leftarrow\) packet_TX(); ifonline_timer is not firedthen ifpkt_rx is not NULLthen  timer_reschedule(online_timer); ifupdate_entries_timer is startthen  routing_table_pointer \(\leftarrow\)update_routing_table(pkt_rx);  update_neighbor_table(routing_table_pointer);  end if RX_process(pkt_rx);  end if ifpkt_tx is not NULLthen  TX_process(pkt_tx);  end if  end if else  start_timer(route_recovery_timer); whileroute_recovery_timer is not fireddo  listen(beacon_channel);  pkt_beacon \(\leftarrow\) packet_RX() ;  routing_table_pointer \(\leftarrow\) update_routing_table(pkt_beacon);  end if  update_neighbor_table(routing_table_pointer);  publish heartbeat packet;  listen(compute_channel(self_adv_addrdr));  end if ifrouting_update_timer is firedthen  start_timer(update_entries_timer);  end if  end if
```  
**Algorithm 3**routing_maintenance  
Our solution is to manually change the initial TTL value of heartbeat packets during the route creation phase. This means that nodes only create routes for nodes within a certain hop count radius because packets with a TTL value of 0 can be discarded. If a node has to transmit messages to an element address with a hop count larger than the initial TTL value, according to our algorithm, the message will be broadcast to all of its neighbors at the beginning until some relays have the route entry of the destination address. This is equivalent to adding a multipath characteristic to distant nodes adaptively, improving the reliability performance. Therefore users should set an appropriate initial TTL value in terms of actual scenario requirements and hardware conditions, leading to a good tradeoff between the resource overhead and the routing scale. **Tradeoff between communication overhead and reliability:** Co-existing with other 2.4 GHz wireless technologies such as Wi-Fi, BLE is prone to be interference by these signals. To reduce the interference issue, a dedicated frequency hopping mechanism on 37 data channels between two paired Bluetooth devices has been proposed by Bluetooth specification.