# Routing Selection Algorithm for Mobile Ad Hoc Networks Based on Neighbor Node Density
## 4 Proposed New Routing Method  
### Cnd-Aodv  
Based on the analysis from the previous sections, it is evident that both isolated nodes and over-dense nodes are determined based on the common neighbor nodes between the receiver and sender. If it is judged as an isolated node, the RREQ is forwarded with a probability of 100%. If it is judged as an over-dense node, the RREQ is discarded directly. Motivated by that, in this subsection, we propose a solution called CND-AODV (common neighborhood density AODV) to address those issues, which will be detailed in the followings. Figure 7 illustrates the basic idea of the common neighbor nodes, where \(N\) represents the number of common neighbor nodes between two adjacent nodes \(i\) and \(j\), and the number of blue nodes in the figure is shown as \(N_{ij}\). In the process of sending a route request at a node, the basic parameters required by CND-AODV can be obtained by carrying its corresponding routing table and neighbor table. Therefore, the number of common neighbor nodes between the sender \(j\) and the receiver \(i\) is denoted as \(N_{ij}\). \[N_{ij}=S_{i}\cap S_{j} \tag{2}\]  
where \(S_{i}\) and \(S_{j}\) are the collection of neighbor nodes of receiver \(i\) and sender \(j\). Figure 6: Illustration of over-dense receiver in ad hoc networks, over-dense node. Then, for the judgment of isolated nodes and over-dense nodes, simply speaking, an isolated node means that the \(N_{ij}\) value is small, and an over-dense node means that the \(N_{ij}\) value is large. So, it is necessary to analyze how to define the smaller and larger values. It is obvious that when the sender \(j\) forwards control information, each of its neighbor nodes will receive it. Each receiver will have the number of common neighbor nodes \(N_{ij}\) with the sender. Thus, the mean \(\overline{N_{j}}\) of the number of common neighbor nodes between sender \(j\) and its neighbor nodes is suitable to represent the density of the neighbor nodes, i.e.,  
\[\overline{N_{j}}=\frac{\sum_{i=1}^{n}N_{ij}}{Nb_{j}} \tag{3}\]  
where \(Nb_{j}\) is the number of neighbor nodes of the sender \(j\). Therefore, it can be defined that when the \(N_{ij}\) of receiver \(i\) and sender \(j\) far exceeds the \(\overline{N_{j}}\) of the sender \(j\), it can be defined as an over-dense node; if it is much smaller than \(\overline{N_{j}}\), it can be defined as an isolated node. Next, we will present a discriminative example of common neighbor nodes to illustrate the proposed method. The number of nodes \(N_{ij}\) in common between the sender \(j\) and its neighbors will be counted, and the number of neighbors of the sender exceeds \"\(k\)\". In the simulation experiment, with an area of \(1000\ \times\ 1000\) m\({}^{2}\), two different methods were employed for node generation: random distribution and uniform distribution. These experiments involved two scenarios with different node counts, specifically 125 (it was observed that when the number of nodes is less than or equal to 75, it is difficult to form cases where the number of neighbor nodes exceeds \"\(k\)\") and 275. For random distribution, node positions were non-fixed, while uniform distribution represents an extreme and special case of random distribution. Additionally, each node was assigned a random motion direction upon appearance, with their speeds randomly set between 0 and 5 m/s. As shown in Figures 8 and 9, the initial simulation plots for 125 and 275 nodes under random and uniform distribution illustrate the spatial distribution of nodes in the simulation environment. The left graph represents 125 nodes, while the right graph represents 275 simulated nodes. Since uniform distribution is an extreme and special case of random distribution, it is primarily considered to analyze whether there are any impacts on network performance in extreme scenarios. Therefore, the simulation experiments in  
Figure 7: Illustration of the number of common neighbor nodes.