# Optimizing Routing Protocol Design for Long-Range Distributed Multi-Hop Networks
## 3 MPR Selection Algorithm Based on Connection Necessity  
This paper proposes an improved MPR selection algorithm from the necessity perspective, eliminating the redundancy present in traditional algorithms. The algorithm flow is shown in Figure 2. The relevant concepts involved in the algorithm process are as follows:  
1. Node Depth: The depth of a one-hop neighbor node k (where node k is a one-hop neighbor of node N) represents the number of neighbors with strictly symmetric links to node k, excluding the one-hop neighbors of node N. For example, in Figure 3, the depth of node 1 is 2, including nodes a and b. 2. Node Coverage: The coverage of a one-hop neighbor node k indicates the number of neighbors with strictly symmetric links to node k after removing the nodes already included in the MPR set and their covered two-hop neighbors, excluding the one-hop neighbors of node N. For example, in Figure 3, if node 1 is already included in the MPR set, the coverage of node 2 is 2, including nodes c and d, but excluding node b. Table 1 describes the parameters of the MPR selection algorithm based on connection necessity. Algorithm 1 presents the MPR selection algorithm based on connection necessity. In this study, networks were formed by randomly setting 100, 200, 300, and 400 nodes, while controlling the coverage radius of the nodes to achieve an average number of neighboring nodes of 10, 20, 40, and 60. We compared the number of global MPR nodes obtained using the improved MPR selection algorithm with that of the standard MPR selection algorithm under the same network scale. The results indicated that, under varying densities, the improved MPR selection algorithm demonstrates a reduction in the number of calculated MPR nodes ranging from 2% to 12% compared to the standard algorithm. This finding suggests that the improved MPR selection algorithm can significantly reduce the redundancy of MPR nodes, as shown in Figure 4. \begin{table}
\begin{tabular}{c c} \hline
**Algorithm Parameter** & **Parameter Description** \\ \hline MPR\_Sel & MPR selection nodes \\ Sel\_MPRS & MPR node set \\ Sel\_MPRS[]\_SIZE_ & Number of nodes in the MPR set \\ FN[]\_SIZE_ & Number of one-hop neighbors \\ FN[i] & The i-th hop neighboring node \\ SN[]\_SIZE_ & Number of two-hop neighbors \\ SN[i] & The i-th two-hop neighboring node \\ Avail\_FN & Remaining available one-hop neighbors \\ Avail\_SN & Remaining available two-hop neighbors \\ ACC\_uni & Unique path between two-hop and one-hop neighbors \\ Cov[i] & Two-hop neighbors covered by node i \\ Cov[i]\_SIZE_ & Maximum coverage of node i \\ Max\_Cov[i]\_SIZE_ & Depth of node i \\ Dep[i]\_SIZE_ & Maximum depth of node i \\ \hline \end{tabular}
\end{table} 
Table 1: Description of parameters in MPR selection algorithm based on connection necessity. Figure 2: Flow of MPR selection algorithm based on connection necessity. The improved MPR selection algorithm significantly reduces redundant nodes within the MPR set from a necessity standpoint. As illustrated in Figure 5, in a small-scale sparse network, where the number of neighbor nodes per node is relatively few, the traditional MPR selection algorithm results in fewer redundant MPR nodes. Hence, the improvement effect is not pronounced. However, in a large-scale dense network, where the number of neighbor nodes per node is relatively high, the traditional MPR selection algorithm leads to many redundant MPR nodes. The improved algorithm can significantly reduce redundancy. This demonstrates that the advantages of the improved MPR selection algorithm are more evident in large-scale, dense networks, effectively reducing the control message overhead, cutting down on network topology maintenance costs, and improving routing computation efficiency. Figure 4: Changes in the number of global MPR nodes under different network sizes. Figure 3: MPR node selection.