# Beacon-Based Hybrid Routing Protocol for Large-Scale Unmanned Vehicle Ad Hoc Network
## 2 Beacon-Based Multi-Agent Network Hybrid Routing Algorithm
### Path Discovery and Maintenance  
#### 2.2.1 Path Discovery  
When the data node had a data sending request, if there was no routing path to the destination node, the path establishment process as shown in Algorithms 1 and 2. ```
1 Tp: Pulse Propagation time
2 Tr:Pluse Reply time
3 Td:Data Sending time
4 IfT > Tp and T < Tr
5 Source node send a pulse reply message along the OPT. 6 OPT node unicast reply message. 7 EIfT > Tr and T < Td
8 Source node send data along the path tree. 9 Eise
10 Wait until the time reaches Tr. 11 Endif

Figure 4: Schematic diagram of spanning tree. ```
1 Pt: Path information table
2 Pd: Path to the destination address
3 Tp: Pulse Propagation time
4 Becan node received the pulse reply message:
5 If Pd is in Pt:
6 Becan node created a reverse path to the source node. 7 Else:
8 Becan node created a reverse path to the source node. 9 If T < Tp:
10
11
12 Becan node send a pulse message with the destination address. 13 Else:
13 Wait until next pulse cycle. 14 Endif
15 Endif
```

**Algorithm 2**Beacon node path request process. (1) Path creation process of data node:

1 The node judged whether it was in the pulse reply state. If it was, it would send the pulse reply along the OPT, reaching the beacon node. 2 If it was not in the pulse reply state, the node then judged whether it was in the data transmission state. If it was, data would be sent directly along the OPT reaching the beacon node. If not, it would wait until the data sending state. (2) Node of OPT:

1 The node in the OPT would create a reverse path to the source node after receiving the pulse reply message with the destination address, as shown in red arrows 6-7 in Figure 5a. 2 The node in the OPT forwarded the pulse reply message with the destination address until it reached the beacon node. (3) 1-hop node around the OPT:

When 1-hop node around the OPT received a pulse reply message with the destination address, a reverse path to the source node was established, as shown in the blue arrows 5-6-7 and 8-7 in Figure 5a. The 1-hop node around the OPT did not forward the pulse reply message to avoid unnecessary routing cost. (4) Beacon node:

1 After the beacon node received a pulse reply request from the source node, a reverse path to the source node would be created, as shown by the red arrow 1-6-7 in Figure 5a. Figure 5: (**a**) Schematic diagram of source node path establishment process. (**b**) Schematic diagram of destination nodepath establishment process. 2 The beacon node judged if there was a path to the destination node. If not, it would send a pulse message with the destination address in the next pulse cycle for path addressing. Subsequently, the beacon node, the source nodes in the OPT from the source node to the beacon source node, and the 1-hop nodes around the OPT would all create a reverse path to the source node. When the destination node received the pulse message with the destination address, the node would send the pulse reply message to the beacon node along the OPT pointing to the beacon source node. The process for each type of node is illustrated Algorithm 1 and Algorithm 2. After the message reached the beacon node, the path 1-9-10-11 from the beacon node to the destination node as shown in Figure 4(b) was established. Node 8 around the path tree established reverse paths from 8 to 11 to the destination node. #### 2.2.2 Optimal Path Creation

As shown in Figure 4(b), the source node would send data to the destination node along the newly established path tree. The initial possible path was 7-6-9-10-11, which was obviously not the optimal path. During the path creation process, 1-hop nodes (nodes 5 and 8) of the path tree would monitor the pulse reply message sent by the source node and the destination node. If the node found a fast path existed, it would send a message to the corresponding node and declared that a fast path existed. The optimal path 7-8-11 shown in the purple arrow in Figure 4(b) would then be created.