# Research on Routing Algorithm of Construction Robot Cluster Enhanced Ad Hoc Network
## 3 ACER Routing Algorithm
### Route Discovery Based on the Connectivity Feedback Mechanism  
The general case of route discovery is divided into four steps, which are: (1) the source node sends a route request information packet RREQ containing node identifier, node energy, and experience path to the neighbor nodes; (2) if the source node does not contain the target node in its neighbor node-set, the node in the neighbor node set continues to forward the node's RREQ as a relay node; (3) the target node receives the RREQ from the node through one or more paths, establishes the set of reachable paths, and constructs route reply information packet RREP containing node identifier, node energy, experienced path, and link hops, and sends it to the source node along the original path; (4) after the source node receives the RREP from the target node by the specified time, it confirms the route reply information packet according to the agreed rules. It confirms the reachable path set, and then route discovery ends and enters route selection. In the preceding step (2), the neighboring nodes of the source node tend to forward route requests as intermediate nodes to seek available routes. Broadcast routes and multicast routes tend to result in a large number of duplicate route requests being received by the forwarding node and the target node with high energy consumption. In contrast, single-route routing, such as distance vector routing algorithms, can forward data along a unique path to the destination node, but the complex field environment in dynamic networks makes a single routing path for which it is impossible to guarantee network connectivity. Probabilistic broadcasting, such as DV-cast (distributed vehicular broadcast-cast) protocol, has some shortcomings--the message cannot be propagated in two directions and the cached message is easily forwarded blindly. Therefore, the route discovery part of the routing algorithm in this paper introduces a connectivity feedback mechanism, i.e., the network connectivity contribution is calculated for the intermediate nodes that forward the route request data, and the probability of intermediate nodes forwarding the routing information is formed as shown in Equation (9) so that the forwarding nodes are selected. A comparison between the general route discovery process and the route discovery process in this paper is shown in Figure 2. In this paper, the route request RREQ message adds a connectivity state field in addition to the source node sequence number, destination node sequence number, node energy, and link quality, indicating the connectivity probability of the route path up to the current node. Figure 2: Comparison of route discovery processes. The connectivity rate of the regional network centered on intermediate node \(m\) is calculated by constructing the adjacency matrix \(A\). Suppose the adjacency matrix of intermediate node \(m\) is given in Equation (7):  
\[A= \begin{bmatrix}1&1\\ 0&1\end{bmatrix}  \tag{7}\]  
The adjacency matrix characterizes the 1-hop pathway, and \(A^{k}\) can reflect the k-hop reachable situation. The matrix \(P\) was introduced as the connectivity judgment matrix, and \(P_{ij}=1\) indicates that it is connected from \(i\) to \(j\). Otherwise, it is not connected. The connectivity contribution is calculated as follows:  
1. Place the new matrix \(P\): = \(A\);
2. \(t\) = 1,......, \(k\), \(P\) = \(P*A\), circular superposition to obtain the final connectivity matrix;
3. Successive judgments are made on the \(P\) matrix \(P_{ij}\), and the number of elements with \(P_{ij}>0\) is accumulated num. The contribution of nodes as forwarding nodes to network connectivity \(C\) is obtained as shown in Equation (8):  
\[C=\frac{num}{N(A)\times N(A)} \tag{8}\]  
where \(N(A)\) denotes the dimension of the adjacency matrix \(A\). The final probability that source node \(i\) selects intermediate node \(m\) as the forwarding node is obtained, as shown in Equation (9). \[P_{i,m}=\left\{