A novel routing protocol considering the boundary effects for ad hoc networks

Abstract

To alleviate the broadcast storm problem in the route discovery process, this article proposes a novel routing protocol considering the boundary effects for ad hoc networks, named NRP. The novelty of NRP lies in the following: first, NRP defines a forwarding area criterion considering the effects of the node transmission area boundary to reduce the broken links due to the mobility of nodes; second, NRP adopts the idea of a piecewise function to estimate the node degree when the nodes are in the center, borderline, and corner areas, respectively, which considers the effects of both network boundaries and node communication boundaries without broadcasting Hello messages periodically; third, NRP applies the static game forwarding strategy to calculate the forwarding probability during the route discovery process. NRP reduces the redundant retransmissions and collision probability among neighboring nodes, thus improving the forwarding efficiency. The extensive simulation results by NS-2 simulator have shown that NRP performs better than AODV + FDG, AODV + Hello, ad hoc on-demand distance vector, ad hoc on-demand multipath distance vector, and energy-efficient ant-based routing in terms of packet delivery ratio, routing overhead, normalized medium access control load, throughput, and network lifetime.

Introduction

Ad hoc networks are temporary networks consisting of a special kind of wireless mobile nodes without any infrastructure or centralized administration, which have a wide application prospect in civil and military fields. As a core supporting technology of ad hoc networks, routing protocols are mainly used to find routes. ¹ Highly dynamic network topology, as well as limited bandwidth and energy constraint, presents challenges for implementing high-performance routing protocols. Routing protocols are classified into reactive, on-demand, and hybrid types. ² On-demand routing protocols are highly concerned by researchers all over the world for their advantages, such as low routing overhead and no need for maintaining the whole network information. In on-demand routing protocols, source nodes initiate routing discovery processes by means of broadcasting routing request (RREQ) packets. Therefore, the efficiency of the routing discovery process seriously affects the overall performance of routing protocols. The simplest broadcasting is flooding, in which nodes rebroadcast the first received packets to all their neighbors. During the route discovery process, flooding the RREQ packets to establish routes causes the broadcast storm problem, which leads to a large number of packet collisions and redundant rebroadcasts, especially in dense networks.

In order to alleviate the broadcast storm problem, many broadcasting protocols have been proposed in the last decade, which are classified into deterministic and probabilistic schemes. ³ In deterministic schemes, only a subset of nodes is allowed to participate in the broadcasting process. However, the nodes that have repeatedly undertaken the rebroadcast task may deplete their energy, which decreases the connectivity of networks. On the other hand, due to highly dynamic topology, it is difficult to select the forwarding nodes in ad hoc networks. In probabilistic schemes, nodes participate in the broadcasting process according to a certain probability value, so all nodes are allowed to broadcast the received packets. Compared with the deterministic scheme, the probabilistic broadcast scheme exhibits better robustness to routing failures, network attacks, and dynamic topology conditions. However, it is an urgent key issue to calculate the forwarding probability in probabilistic broadcast schemes. Node degree, namely, neighbor number, is an efficient factor for calculating forwarding probability as described in the literature.^4–9 However, in the aforementioned studies, nodes need to periodically broadcast Hello messages to obtain node degrees, which consumes a large amount of energy and takes up a lot of bandwidth.

To overcome these obstacles, this article presents a novel routing protocol considering the boundary effects for ad hoc networks, named NRP. The major contributions of NRP are as follows:

1. NRP defines a novel concept of the forwarding area. The nodes in the forwarding area participate in broadcasting, which reduces the probability of the broken links due to mobility of nodes.

2. NRP considers the border effects of the network area and divides the network area into center, borderline, and corner areas. NRP adopts the idea of a piecewise function to estimate the node degree when the nodes are in the center, borderline, and corner areas, respectively, which avoids unnecessary overhead compared with broadcasting Hello messages periodically to obtain the node degree.

3. NRP adopts a novel static game forwarding strategy to forward RREQ packets, where node degree is used to estimate the number of nodes participating in the forwarding process. Forwarding and no-forwarding packets are used as strategy sets to design a gain function. The forwarding probability is obtained by Nash equilibrium to improve the broadcasting efficiency in the routing discovery process.

The major innovation of NRP is that, for the first time, NRP considers the effects of both network boundaries and node communication boundaries. The node degree information is calculated by considering the network boundary, which is used to estimate the next hop neighbor’s game participants. Therefore, the number of participants in the game is estimated, instead of the number of actual neighbors.

The rest of this article is organized as follows: section “Related work” introduces the related previous works; section “Node degree estimation and static game forwarding strategy–based ad hoc network routing protocol: NRP” proposes a node degree estimation algorithm considering boundary effects, and the NRP protocol and its implementation process are also described in detail; section “Performance evaluation” verifies the performance of NRP using the NS-2 simulator; section “Conclusion and future work” concludes this article and follows the future work.

Related work

The typical on-demand routing protocols are ad hoc on-demand distance vector (AODV), ¹⁰ ad hoc on-demand multipath distance vector (AOMDV), ¹¹ and dynamic source routing (DSR). ¹² In the routing discovery process of AODV and AOMDV, the nodes broadcast RREQ packets to all neighbor nodes, which results in excessive redundant retransmissions and high collision probability due to the broadcast storm problem. ⁹ Although AODV and AOMDV periodically broadcast Hello messages, they do not utilize the information of one-hop neighbor. During the routing discovery process of DSR, RREQ packets contain path information by adding node information into RREQ packets. However, DSR still causes the broadcast storm problem. To overcome the problem, AODV + FDG utilizes one-hop node degree information to calculate the forwarding probability based on game theory. ⁴ Simulation results verified that AODV + FDG performs better than AODV in terms of routing overhead, packet delivery ratio, and average end-to-end delay. In Camilo et al., ¹³ the energy-efficient ant-based routing (EEABR) algorithm is proposed. It allows the nodes in the network to obtain the location information and selects one of the neighbor nodes as the next hop node based on ant colony optimization. Simulation results show that EEABR expands the lifetime of a wireless network. The forwarding probability is adjusted according to the node degree in the range between the maximum and the minimum value. ⁸ Simulation results prove the advantages of the proposed protocol in terms of saved rebroadcast and collision number. In order to improve saved rebroadcast, the forwarding probability is inversely proportional to the one-hop node degree, ⁷ and similar research work is reported in Lysiuk and Haas ⁵ and Wegener et al. ⁶ In order to make full use of node degree information, one- and two-hop node degree information is used to compute the forwarding probability. ¹⁴ When the two-hop node degree is relatively large, the forwarding probability is reduced and vice versa. Simulation results show the superiority of the scheme in terms of packet delivery ratio and routing overhead. In order to optimize routing discovery processes, a neighbor knowledge-based rebroadcast (NKR) protocol is proposed which combines neighbor coverage knowledge and probabilistic methods. ¹⁵ However, due to periodically broadcasting Hello messages to obtain the node degree information in these schemes, the node’s energy and wireless bandwidth are consumed, thus increasing network congestion and routing overhead.

To overcome the weakness of broadcasting Hello messages to obtain the node degree, scientific researchers proposed node degree acquirement methods without relying on Hello messages.^16–18 The link probability and the number of nodes in the networks are used to obtain node degree information. ¹⁶ However, the effects of the network boundary are not taken into account. The average number of neighbors is calculated by considering the effect of network boundary,^17,18 while the deficiency of such method lies in the following: (1) nodes located in any areas have the same node degree. In fact, the node degree varies with the area range of node location; (2) due to no analytic solution, it is difficult to be applied in routing protocol. A node degree estimation and game forwarding based routing protocol (NGRP) is proposed in Qing-Wen et al., ¹⁹ which does not consider the effects of node transmission area boundary.

The difference between our work and the aforementioned works is that NRP considers not only the impact of network boundaries, but also that of node communication boundaries. NRP adopts a static game forwarding strategy to forward RREQ packets, in which the number of participants in the game is estimated, instead of the number of actual neighbors.

Node degree estimation and static game forwarding strategy–based ad hoc network routing protocol: NRP

Forwarding area definition

When a node sends a packet, its mobile neighbor nodes near the border area are likely to leave its transmission area after one-hop delay, thus causing broken links. NRP defines the forwarding area as shown in Figure 1. $R$ and $R\prime$ are the radius of the node’s transmission range and that of the node’s forwarding area, respectively

$$R\prime =\alpha R$$

(1)

where $0<\alpha <1$ . Only the nodes in the forwarding area are allowed to participate in forwarding during the routing discovery process. Therefore, the proposed forwarding area reduces the probability of broken links due to mobility of nodes, especially in highly dynamic network topology.

Figure 1.

Forwarding area.

Node degree estimation algorithm considering border effects of network area

The total area of a network is $L\times L$ , where $L$ is the side length. $n$ represents the total number of nodes in the entire network. The nodes’ geographical location is uniformly distributed. The network area is divided into center, border, and corner areas, which are denoted by $S_1$ , $S_2$ , and $S_3$ , respectively, as shown in Figure 2. We propose a node degree estimation algorithm by means of considering the border effects of the network area. The node degree is estimated by applying the idea of a piecewise function when the nodes are in the center, border, and corner areas, respectively, which avoids unnecessary overhead caused by broadcasting Hello messages periodically.

Figure 2.

Geographic division of the network scenario.

When the lower left corner of the network scenario is set to be the origin point, a rectangular area is set up where the left border is the y-axis and the lower border is the x-axis. The center, border, and corner areas are obtained, respectively, by expressions (2)–(4) in the coordinate system as follows

$$S_1=\{(x,y)|\begin{array}{c}\alpha R<x<L-\alpha R\hfill \\ \multicolumn{1}{c}{\alpha R<y<L-\alpha R}\end{array}\}$$

(2)

$$S_2=\{(x,y)|\begin{array}{c}\left(\begin{array}{c}0\le x\le \alpha R\hfill \\ \multicolumn{1}{c}{\alpha R\le y\le L-\alpha R}\end{array}\right)\mathrm{or}\hfill \\ \multicolumn{1}{c}{\left(\begin{array}{c}\alpha R\le x\le L-\alpha R\hfill \\ \multicolumn{1}{c}{0\le y\le \alpha R}\end{array}\right)\mathrm{or}}\\ \multicolumn{1}{c}{\left(\begin{array}{c}\alpha R\le x\le L-\alpha R\hfill \\ \multicolumn{1}{c}{L-\alpha R\le y\le L}\end{array}\right)\mathrm{or}}\\ \multicolumn{1}{c}{\left(\begin{array}{c}L-\alpha R\le x\le L\hfill \\ \multicolumn{1}{c}{\alpha R\le y\le L-\alpha R}\end{array}\right)}\end{array}\}$$

(3)

$$S_3=\{(x,y)|\begin{array}{c}\left(\begin{array}{c}0\le x<\alpha R\hfill \\ \multicolumn{1}{c}{0\le y<\alpha R}\end{array}\right)\mathrm{or}\hfill \\ \multicolumn{1}{c}{\left(\begin{array}{c}0\le x<\alpha R\hfill \\ \multicolumn{1}{c}{L-\alpha R<y\le L}\end{array}\right)\mathrm{or}}\\ \multicolumn{1}{c}{\left(\begin{array}{c}L-\alpha R<x\le L\hfill \\ \multicolumn{1}{c}{0\le y<\alpha R}\end{array}\right)\mathrm{or}}\\ \multicolumn{1}{c}{\left(\begin{array}{c}L-\alpha R<x\le L\hfill \\ \multicolumn{1}{c}{L-\alpha R<y\le L}\end{array}\right)}\end{array}\}$$

(4)

where $(x,y)$ denotes the two-dimensional coordinates of nodes. It can be seen from Figure 2 that, according to the geographic positions of nodes, the forwarding area range of nodes is classified into three situations when considering the border effects.

When nodes are located in $S_1$

As shown in circle ${\mathrm{O}}_1$ in Figure 2, when nodes are located in $S_1$ , the forwarding area range of the nodes is

$$S_{{\mathrm{O}}_1}=\pi {\left(\alpha R\right)}^2$$

(5)

The average neighbor number of the nodes is given by

$$N_{{\mathrm{O}}_1}=\frac{(n-1)\pi {\left(\alpha R\right)}^2}{L^2}$$

(6)

When nodes are located in $S_2$

When nodes are located in area $S_2$ , four situations are divided because the network scenario has four borders. The nodes are close to the right border of the network scenario as shown in Figure 3, where $B$ is the midpoint between points A and C and ${\mathrm{O}}_{2}B\perp \mathrm{AC}$ .

Figure 3.

Node in the border area.

Therefore, angle $\theta$ between ${\mathrm{O}}_{2}A$ and ${\mathrm{O}}_{2}B$ is computed by

$$\theta =\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}}{\alpha R}$$

(7)

Then, the area of sector ${\mathrm{O}}_2\mathrm{CDA}$ is calculated by

$$S_{{\mathrm{O}}_2\mathrm{CDA}}=\frac{1}{2}2\theta {\left(\alpha R\right)}^2=\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}}{\alpha R}{\left(\alpha R\right)}^2$$

(8)

The area of triangle ${\mathrm{O}}_2\mathrm{CA}$ is given by

$$S_{{\mathrm{O}}_2\mathrm{CA}}=\frac{1}{2}{d}_{{\mathrm{O}}_{2}B}{d}_{\mathrm{AC}}=d_{{\mathrm{O}}_{2}B}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}$$

(9)

Then, the invalid forwarding range of ${\mathrm{O}}_2$ is

$$\begin{array}{c}\multicolumn{1}{c}{S_{\mathrm{ABCD}}=S_{{\mathrm{O}}_2\mathrm{CDA}}-S_{{\mathrm{O}}_2\mathrm{CA}}}\\ =\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}}{\alpha R}{\left(\alpha R\right)}^2\hfill \\ -d_{{\mathrm{O}}_{2}B}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}\hfill \end{array}$$

(10)

Therefore, the forwarding area range of node ${\mathrm{O}}_2$ is obtained as follows

$$\begin{array}{c}\multicolumn{1}{c}{S_{{\mathrm{O}}_2}=\pi {\left(\alpha R\right)}^2-S_{\mathrm{ABCD}}}\\ =(\pi -\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}}{\alpha R}){\left(\alpha R\right)}^2\hfill \\ +d_{{\mathrm{O}}_{2}B}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}\hfill \end{array}$$

(11)

Here, the node degree is estimated by

$$\begin{array}{cc}\multicolumn{1}{c}{N_{{\mathrm{O}}_2}}& =\frac{(n-1)S_{{\mathrm{O}}_2}}{L^2}=\frac{(n-1)[(\pi -\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}}{\alpha R}){\left(\alpha R\right)}^2+d_{{\mathrm{O}}_{2}B}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{2}B}^2}]}{L^2}\hfill \end{array}$$

(12)

In the same way, the node degree is obtained in three situations when nodes are close to the upper, lower, and left borders, respectively.

When nodes are located in $S_3$

When nodes are located in the corner area of the network scenario, four situations are divided when nodes are located in the upper left, lower left, upper right, and lower right corners, respectively. We take the nodes in the upper right corner as an example. The situation is classified into two. $d_{{\mathrm{O}}_{3}D}$ is the distance from the circle center of node ${\mathrm{O}}_3$ to the right upper corner D, and then the two situations are classified according to the values of $d_{{\mathrm{O}}_{3}D}$ and $R\prime$ .

When $d_{{\mathrm{O}}_{3}D}\ge \alpha R$

When the nodes are located in area $S_3$ , the forwarding area range of nodes is intercepted by two borders, as shown in Figure 4. According to equation (10), the invalid forwarding area range of node ${\mathrm{O}}_3$ due to the impact of borders is computed as follows

$$\begin{array}{c}\multicolumn{1}{c}{S_{\mathrm{ABCK}}=S_{{\mathrm{O}}_3\mathrm{CBA}}-S_{{\mathrm{O}}_3\mathrm{CA}}=\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}{\left(\alpha R\right)}^2}\\ -d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}\hfill \end{array}$$

(13)

In the same way

$$\begin{array}{c}{S}_{\mathrm{EFGM}}=S_{{\mathrm{O}}_3\mathrm{GEF}}-S_{{\mathrm{O}}_3\mathrm{GE}}=\arcsin \hfill \\ \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R}{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}\hfill \end{array}$$

(14)

Here, the forwarding area range of node ${\mathrm{O}}_3$ is computed as follows

$$S_{{\mathrm{O}}_3}=\pi {\left(\alpha R\right)}^2-S_{\mathrm{ABCK}}-S_{\mathrm{EFGM}}$$

(15)

$$\begin{array}{c}{S}_{{\mathrm{O}}_3}=(\pi -\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}-\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R}){\left(\alpha R\right)}^2\hfill \\ +d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}+d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}\hfill \end{array}$$

(16)

Here, the node degree is given by

$$\begin{array}{cc}\multicolumn{1}{c}{N_{{\mathrm{O}}_3}=}& \frac{(n-1)}{L^2}[(\pi -\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}-\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R}){\left(\alpha R\right)}^2\hfill \\ \multicolumn{1}{c}{}& +d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}+d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}]\hfill \end{array}$$

(17)

Figure 4.

Node in the corner area (a).

When $d_{{\mathrm{O}}_{3}D}<\alpha R$

Here, according to equation (10), the invalid forwarding area range of node ${\mathrm{O}}_3$ due to the impact of borders, $S_{\mathrm{ABCDK}}$ , is computed by

$$\begin{array}{c}{S}_{\mathrm{ABCDK}}=S_{{\mathrm{O}}_3\mathrm{CBA}}-S_{{\mathrm{O}}_3\mathrm{CA}}=\arcsin \hfill \\ \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}\hfill \end{array}$$

(18)

Another part of the area of node ${\mathrm{O}}_3$ due to the impact of borders is computed by the integral method. Assuming that the coordinates of the circle center of node ${\mathrm{O}}_3$ are $(x_{{\mathrm{O}}_3},y_{{\mathrm{O}}_3})$ , then the function of circle ${\mathrm{O}}_3$ is as follows

$$(x-x_{{\mathrm{O}}_3}{)}^2+(y-y_{{\mathrm{O}}_3}{)}^2={\left(\alpha R\right)}^2$$

(19)

By transformation, we obtain

$$x=x_{{\mathrm{O}}_3}\pm \sqrt{{\left(\alpha R\right)}^2-{(y-y_{{\mathrm{O}}_3})}^2}$$

(20)

For the instance in Figure 5, we obtain

$$x=x_{{\mathrm{O}}_3}+\sqrt{{\left(\alpha R\right)}^2-{(y-y_{{\mathrm{O}}_3})}^2}$$

(21)

Here, the valid forwarding area range of node ${\mathrm{O}}_3$ due to the impact of borders $S_{\mathrm{DCGM}}$ is given by

$$\begin{array}{cc}\multicolumn{1}{c}{S_{\mathrm{DCGM}}}& =\underset{y_{\mathrm{G}}}{\overset{y_{\mathrm{D}}}{\int }}(x-L)\mathrm{dy}\hfill \\ \multicolumn{1}{c}{}& =\underset{y_{\mathrm{G}}}{\overset{y_{\mathrm{D}}}{\int }}(x_{{\mathrm{O}}_3}+\sqrt{{\left(\alpha R\right)}^2-{(y-y_{{\mathrm{O}}_3})}^2}-L)\mathrm{dy}\hfill \end{array}$$

(22)

Because

$$x_{{\mathrm{O}}_3}=L-d_{{\mathrm{O}}_{3}M}$$

(23)

we obtain

$$S_{\mathrm{DCGM}}=\underset{y_G}{\overset{y_D}{\int }}(\sqrt{{\left(\alpha R\right)}^2-{(y-y_{{\mathrm{O}}_3})}^2}-d_{{\mathrm{O}}_{3}M})\mathrm{dy}$$

(24)

$$S_{\mathrm{DCGM}}=\underset{y_G-y_{{\mathrm{O}}_3}}{\overset{y_D-y_{{\mathrm{O}}_3}}{\int }}\sqrt{{\left(\alpha R\right)}^2-t^2}\mathrm{dt}-\underset{y_G}{\overset{y_D}{\int }}{d}_{{\mathrm{O}}_{3}M}\mathrm{dy}$$

(25)

By further derivation, we obtain

$$\begin{array}{cc}\multicolumn{1}{c}{S_{\mathrm{DCGM}}=}& (\frac{t}{2}\sqrt{{\left(\alpha R\right)}^2-t^2}+\frac{{\left(\alpha R\right)}^2}{2}\arcsin \frac{t}{\alpha R}){|}_{y_G-y_{{\mathrm{O}}_3}}^{y_D-y_{{\mathrm{O}}_3}}\hfill \\ \multicolumn{1}{c}{}& -d_{{\mathrm{O}}_{3}M}(y_D-y_G)\hfill \end{array}$$

(26)

and then

$$\begin{array}{cc}\multicolumn{1}{c}{S_{\mathrm{DCGM}}=}& \frac{d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}-d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{2}\hfill \\ \multicolumn{1}{c}{}& +\frac{{\left(\alpha R\right)}^2(\arcsin \frac{d_{{\mathrm{O}}_{3}K}}{\alpha R}+\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R})}{2}\hfill \\ \multicolumn{1}{c}{}& -d_{{\mathrm{O}}_{3}K}{d}_{{\mathrm{O}}_{3}M}\hfill \end{array}$$

(27)

By combining equations (18) and (27), the invalid forwarding area range of node ${\mathrm{O}}_3$ due to the impact of borders, $S_{\mathrm{ABCGMDK}}$ , is given by

$$\begin{array}{cc}\multicolumn{1}{c}{S_{\mathrm{ABCGMDK}}=}& \frac{{\left(\alpha R\right)}^2(2\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}+\arcsin \frac{d_{{\mathrm{O}}_{3}K}}{\alpha R}+\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R})}{2}\hfill \\ \multicolumn{1}{c}{}& -\frac{d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}+d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{2}-d_{{\mathrm{O}}_{3}M}{d}_{{\mathrm{O}}_{3}K}\hfill \end{array}$$

(28)

Then, the forwarding area range of node ${\mathrm{O}}_3$ is

$$S_{{\mathrm{O}}_3}=\pi {\left(\alpha R\right)}^2-S_{\mathrm{ABCGMDK}}$$

(29)

By combining equations (28) and (29), we obtain

$$\begin{array}{cc}\multicolumn{1}{c}{S_{{\mathrm{O}}_3}=}& \frac{{\left(\alpha R\right)}^2(2\pi -2\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}-\arcsin \frac{d_{{\mathrm{O}}_{3}K}}{\alpha R}-\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R})}{2}\hfill \\ \multicolumn{1}{c}{}& +\frac{d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}+d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{2}+d_{{\mathrm{O}}_{3}M}{d}_{{\mathrm{O}}_{3}K}\hfill \end{array}$$

(30)

Here, the node degree is estimated by

$$\begin{array}{cc}\multicolumn{1}{c}{\stackrel{~}{N_{{\mathrm{O}}_3}}=}& \frac{(n-1)}{L^2}[\frac{{\left(\alpha R\right)}^2(2\pi -2\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{\alpha R}-\arcsin \frac{d_{{\mathrm{O}}_{3}K}}{\alpha R}-\arcsin \frac{\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}}{\alpha R})}{2}\hfill \\ \multicolumn{1}{c}{}& +\frac{d_{{\mathrm{O}}_{3}M}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}M}^2}+d_{{\mathrm{O}}_{3}K}\sqrt{{\left(\alpha R\right)}^2-d_{{\mathrm{O}}_{3}K}^2}}{2}+d_{{\mathrm{O}}_{3}M}{d}_{{\mathrm{O}}_{3}K}]\hfill \end{array}$$

(31)

In the same way, node degree is estimated when nodes are located in the upper left, lower left, and lower right corners, respectively.

Figure 5.

Node in the corner area (b).

Node degree estimation

NRP assumes that nodes in networks carry locating devices, and every node knows its geographic location information. First, the node makes use of its location information to determine its located area in the network scenario based on equations (2)–(4). Then, the node computes its node degree. When the node is located in the center area, the node degree is computed by equation (6). When the node is located in the border area, the node degree is obtained by equation (12). When the node is located in the corner area and $d_{\mathrm{O}D}\ge \alpha R$ , the node degree is given by equation (17). When the node is located in the corner area and $d_{\mathrm{O}D}<\alpha R$ , the node degree is acquired by equation (31). To sum up, by combining equations (6), (12), (17), and (31), the node degree of node $\mathrm{O}$ is estimated by

$$N_{\mathrm{O}}=\{\begin{array}{c}{N}_{{\mathrm{O}}_1}\mathrm{O}\in S_1\hfill \\ \multicolumn{1}{c}{N_{{\mathrm{O}}_2}\mathrm{O}\in S_2}\\ \multicolumn{1}{c}{N_{{\mathrm{O}}_3}\mathrm{O}\in S_3\mathrm{and}{d}_{\mathrm{O}D}\ge \alpha R}\\ \multicolumn{1}{c}{\stackrel{~}{N_{{\mathrm{O}}_3}}\mathrm{O}\in S_3\mathrm{and}{d}_{\mathrm{O}D}<\alpha R}\end{array}$$

(32)

On one hand, by considering the boundary impact of the network scenario, NRP improves the accuracy of node degree; on the other hand, compared with broadcasting Hello messages to obtain node degree information, NRP avoids the unnecessary network overhead.

Static game forwarding strategy

NRP is an on-demand routing protocol substantially. When source nodes have data to forward to destination nodes and no routing to destination nodes, they initiate the routing discovery process by broadcasting RREQ packets. NRP regards the forwarding process as a static game process, that is, nodes participating in forwarding RREQ do not know the strategies of other nodes when they make decisions. There is no the exchange of game information among nodes who participate in forwarding packets. Once nodes make decisions, the development of the game will not be affected. Static game forwarding is defined as follows

$$G=\{N_{\mathrm{O}},A,U\}$$

(33)

where $N_{\mathrm{O}}$ denotes the number of nodes participating in forwarding, which is computed by equation (32), $A$ denotes a strategy set which contains the forwarding and the non-forwarding element, and $U$ denotes a utility function, as shown in Table 1.

Table 1.

Forwarding dilemma game.

Current node	Other $N_{\mathrm{O}}-1$ nodes
	All nodes do not forward packets	At least one node forwards packets
Non-forwarding	0	$u$
Forwarding	$u-v$	$u-v$

In Table 1, $u\ge v>0$ . It is known from Table 1 that one of the nodes is selected as the current node to make the analysis, where $N_{\mathrm{O}}$ is the number of participants in the static forwarding game. When both the current node and other $N_{\mathrm{O}}-1$ nodes do not forward packets, the benefit is 0; when the current node does not forward packets and at least one of the other $N_{\mathrm{O}}-1$ nodes does, the benefit is $u$ ; when the current node forwards packets and other $N_{\mathrm{O}}-1$ nodes do not, the benefit is $u-v$ ; when both the current node and other $N_{\mathrm{O}}-1$ nodes forward packets, the benefit is still $u-v$ . It is assumed that all nodes in the game forward packets with a fixed probability $P$ , and then the probability that at least one node among the other $N_{\mathrm{O}}-1$ nodes forwards packets is given by

$$P_{N_{\mathrm{O}}-1}=1-(1-P{)}^{N_{\mathrm{O}}-1}$$

(34)

The Nash equilibrium point of static game packet forwarding is as follows: the benefit of the current node forwarding the packets equals the benefit when at least one node among $N_{\mathrm{O}}-1$ nodes forwards packets while the current node does not

$$u-v=u\times P_{N_{\mathrm{O}}-1}$$

(35)

Let $u=\beta v$ , where $\beta$ is a constant and $\beta >1$ . By substituting it into equation (36), we obtain

$$P=1-{\beta }^{-\frac{1}{N_{\mathrm{O}}-1}}$$

(36)

If $N_{\mathrm{O}}=1$ , we set $P=1$ .

Packet structure

The RREQ packet structure is shown in Table 2, where node degree information is added into the RREQ packet. Source node address and broadcast ID identify a unique RREQ packet.

Table 2.

Routing request packet.

Type	Field	Comment
u_int8_t	rq_type	Packet type
u_int8_t	reserved[2];	Reserved field
u_int8_t	rq_hop_count	Hop number
u_int32_t	rq_bcast_id	Broadcast ID
u_int8_t	rq_neighbor_count	Node degree
double	rq_x	Location x of source or sending node
double	rq_y	Location y of source or sending node
nsaddr_t	rq_dst	Destination node address
u_int32_t	rq_dst_seqno	Destination sequence number
nsaddr_t	rq_src	Source node address
u_int32_t	rq_src_seqno	Source sequence number
double	rq_timestamp	When RREQ is sent

RREQ: routing request.

The route table and route reply packets of NRP are the same as those of AODV.

Route discovery process

The procedure of the route discovery process of NRP is as follows:

1. When a source node attempts to send a data packet to a destination but it does not already know the route, it initiates the routing discovery processes. The source node estimates its node degree $N_{\mathrm{O}}$ by equation (32) and adds $N_{\mathrm{O}}$ to the RREQ packet. Then, the source node broadcasts the RREQ packet.

2. When an intermediate node in the forwarding area receives an RREQ packet for the first time, if it is not the destination or it does not have a route to the destination in its route cache, then it calculates the forwarding probability $P$ by equation (36) and adds its $N_{\mathrm{O}}$ to the RREQ packet and then rebroadcasts the received RREQ packet with forwarding probability $P$ . If not, the intermediate node replies to the RREQ with a route reply packet that is routed back to the original source. When the intermediate node receives a duplicated RREQ packet, it discards the packet.

We modify the source code of AODV in NS-2 (v2.34) to implement NRP. The procedure of the receive RREQ function is shown in Table 3.

Table 3.

The procedure of the NRP receive RREQ function.

NRP receive RREQ () Definitions: $n_i$ : intermediate node. $n_j$ : last hop node of $n_i$ . $\mathrm{FA}(n_j)$ : forwarding area of $n_j$ . $P$ : forwarding probability. $\mathrm{RN}$ : a random number in the interval [0, 1). RREQ: routing request packet. $N_{\mathrm{O}}$ : node degree. 1. If $n_i$ receives an RREQ packet from $n_j$ for the first time 2.  If $n_i$ is not the destination node or does not have a route to the destination in its route cache 3.  If $n_i\in \mathrm{FA}(n_j)$ 4.    $n_i$ calculates $P$ using $N_{\mathrm{O}}$ of $n_j$ by equation (36) 5.   Generating $\mathrm{RN}$ 6.    If $\mathrm{RN}\le P$ 7.      $n_i$ obtains its $N_{\mathrm{O}}$ by equation (32) and adds $N_{\mathrm{O}}$ to the RREQ 8.      $n_i$ rebroadcasts the RREQ 9.    Else 10.     $n_i$ discards the RREQ 11. Else 12. $n_i$ discards the RREQ 13. Else 14. $n_i$ replies to the RREQ with a route reply packet 15. Else 16. $n_i$ discards the RREQ

Performance evaluation

Simulation environment

In order to evaluate the performance of the proposed NRP protocol, we compare it with the performance of some other protocols using the NS-2 simulator. The compared protocols include AODV + FDG, AODV + Hello, AOMDV, AODV, and EEABR. NRP-0.95, NRP-0.9, and NRP-0.85 represent NRP with α = 0.95, 0.90, and 0.85, respectively. AODV + Hello and AODV are different modes of the AODV protocol. AODV + Hello allows the nodes to send Hello messages periodically, while AODV does not. AOMDV allows the nodes to send Hello messages periodically. The simulation parameters are as follows: the wireless transmission radius is 250 m; the bandwidth of networks is 2 MBPS; we choose 802.11 as the medium access control (MAC) layer protocol; the number of CBR (constant bit rate) connections is 10 in the experiments. The source nodes send one packet per second. The simulation results are the average of simulation results from 10 rounds. Table 4 shows the global simulation parameters.

Table 4.

Simulation parameters.

Name	Description
Simulation time	200 s
Data flow	CBR (constant bit rate)
Queue length	50
Interface queue	PriQueue
Propagation model	TwoRayGround
Antenna	OmniAntenna
Channel	WirelessChannel
Initial energy	200 J
Transmission power	1.6 W
Receiving power	1.2 W
Idle power	1.15 W
Sleep power	0.001 W
$\beta$	${10}^6$
$\alpha$	0.95, 0.9, 0.85

Performance metrics

Five important performance metrics are evaluated.

Average end-to-end delay $\mathrm{Avdelay}$

$$\mathrm{Avdelay}=\frac{1}{N}\sum _{i=0}^N(R_{\mathrm{time}}(i)-S_{\mathrm{time}}(i))$$

(37)

where $N$ denotes the number of data packets of the successful transmissions, $R_{\mathrm{time}}(i)$ denotes the arrival time of the ith packet, and $S_{\mathrm{time}}(i)$ denotes the sending time of the ith packet.

Packet delivery ratio $\mathrm{Pdelivery}$

$$\mathrm{Pdelivery}=\frac{P_R}{P_S}$$

(38)

where $P_R$ is the number of data packets arriving at destination successfully and $P_S$ denotes the total number of data packets sent by source nodes.

Routing overhead $\mathrm{Nload}$

$$\mathrm{Nload}=\frac{P_C}{P_D}$$

(39)

where $P_C$ denotes the total number of control packets sent by the network layer of nodes and $P_D$ denotes the total number of data packets received by the destination node.

Normalized MAC load $\mathrm{Mload}$

$$\mathrm{Mload}=\frac{P_M}{P_D}$$

(40)

where $P_M$ represents the total number of control packets sent by the MAC layer of nodes and $P_D$ represents the total number of data packets received by the destination node.

Throughput $\mathrm{Th}$

$$\mathrm{Th}=\frac{1}{T_{\mathrm{Rend}}-T_{\mathrm{Rstart}}}\sum _{i=0}^N{R}_{\mathrm{bytes}}(i)\times 8$$

(41)

where $R_{\mathrm{bytes}}(i)$ denotes the byte number of the ith packet arriving at destination successfully, $N$ denotes the total number of packets received by the destination node, $T_{\mathrm{Rend}}$ denotes the time when packet reception is completed in networks, and $T_{\mathrm{Rstart}}$ denotes the time when nodes in the network start to send data packets.

Network lifetime

Network lifetime is defined as the duration between network initialization and energy depletion of all the nodes in the network.

Simulation results

Verifying the effects of the node density on protocol performance

The purpose of the simulations presented in this subsection is to investigate the effects of different network densities on the performance of these protocols. The number of nodes varies from 275 to 450. All nodes are allowed to move using the random waypoint model in a field of 1500 m × 1500 m. The maximum speed of 20 m/s is chosen to study the effects of network density in the network with a high speed. The pause time of nodes is 100 s.

Figure 6 shows the effects of the network density on the average end-to-end delay. It is clear that, with the increase in node density, the end-to-end delays of NRP, AOMDV, and AODV + FDG remain stable, but AODV + Hello and AODV show fluctuation in end-to-end delay. The average end-to-end delays of NRP, AOMDV, and AODV + FDG are obviously better than those of AODV + Hello, AODV, and EEABR. It is due to the fact that, with the increase in node density, NRP, AOMDV, and AODV + FDG are capable of reducing the number of redundant rebroadcasting packets because of the probability forwarding modes, thus suppressing the network congestion, and reducing the competitions and collisions among nodes.

Figure 6.

Effects of network density on average end-to-end delay.

Figure 7 depicts the relationship between the packet delivery ratio and the network node density. It is seen that the packet delivery ratio of NRP is obviously better than that of the other protocols. The reason is that NRP adopts the static game strategy and node degree estimation algorithm to obtain node degree information while considering the boundary effects, so that it reduces the number of packet drops caused by collisions. NRP and AODV perform significantly better than AODV + FDG, AODV + Hello, AOMDV, and EEABR. It is due to the fact that the periodical broadcast of Hello messages increases network collisions, thus resulting in the reduction of the packet delivery ratio.

Figure 7.

Relationship between packet delivery ratio and network node density.

Figure 8 illustrates the effects of the network density on the routing overhead. It is observed that NRP is the lowest in terms of routing overhead. As the network density increases, the routing overheads of AODV, AOMDV, AODV + FDG, and EEABR increase significantly, but that of the NRP is still stable. This is because NRP adopts the static game strategy and forwarding area criterion, which decreases the number of nodes participating in forwarding routing requests in dense networks. On the other hand, AODV + FDG, AOMDV, AODV + Hello, and EEABR need to broadcast Hello messages periodically, thus increasing routing overhead. Because NRP adopts the static game strategy, the number of nodes participating in forwarding routing requests decreases in dense networks. Therefore, NRP decreases the number of control packets in the routing layer.

Figure 8.

Effects of network density on routing overhead.

Figure 9 depicts the results of the MAC routing overhead versus the network density. Apparently, this figure shows that NRP achieves better performance in comparison with other protocols. As the network node density increases, the metric of NRP remains stable, while those of AODV + FDG, AODV + Hello, AOMDV, AODV, and EEABR increase rapidly. The reason is that AODV + FDG, AOMDV, and AODV + Hello broadcast the Hello message periodically, which increases the number of control packets in the MAC layer. NRP adopts the static game strategy and forwarding area criterion, which reduces the number of nodes forwarding the routing requests, thus decreasing the number of control packets in the MAC layer.

Figure 9.

Results of MAC routing overhead versus network density.

Figure 10 presents the effects of the network density on the throughput. It is obvious that NRP exhibits better performance than the other protocols. The reason is that, on one hand, NRP obtains the node degree information without broadcasting Hello messages while considering boundary effects; on the other hand, it adopts the game forwarding strategy. Therefore, the broadcast storm problem is relieved significantly in NRP. NRP achieves high packet delivery ratio and low end-to-end delay, which increases the reception efficiency of data packets.

Figure 10.

Effects of network density on throughput.

Figure 11 illustrates the results of the network lifetime versus the network density. It is seen that NRP achieves better performance in comparison with other protocols. As the network node density increases, the metric of NRP remains stable, while those of AODV + FDG, AODV + Hello, AOMDV, and AODV decrease rapidly. This is because NRP is capable of reducing the number of nodes participating in forwarding by means of adopting the static game strategy, thus reducing the energy consumption of nodes in the network. AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast Hello messages periodically, which wastes a large amount of energy of nodes.

Figure 11.

Results of network lifetime versus network density.

Verifying the effects of the nodes’ maximum speed on protocol performance

The purpose of the simulations presented in this subsection is to study the effects of the nodes’ maximum speed on the performance of these protocols. The nodes’ maximum speed changes between 1 and 25 m/s. All nodes are allowed to move using the random waypoint model in a field of 1500 m × 1500 m, in which each node moves to a random selected destination with a random speed from a uniform distribution [0, maximum speed]. The pause time is 0. The number of nodes is 275.

Figure 12 shows the effects of the nodes’ maximum speed on the average end-to-end delay. It is observed that, with the increase in the nodes’ maximum speed, the end-to-end delay of all protocols increases gradually. The average end-to-end delays of NRP, AOMDV, and AODV + FDG are obviously better than those of AODV + Hello, AODV, and EEABR. It is due to the fact that, with the increase in the nodes’ maximum speed, NRP and AODV + FDG adopt the probability forwarding modes, which decrease the number of redundant rebroadcasting packets, thus suppressing the network congestion, and reduce the competitions and collisions among nodes.

Figure 12.

Effects of nodes’ maximum speed on average end-to-end delay.

Figure 13 depicts the relationship between the packet delivery ratio and the nodes’ maximum speed. It is seen that the packet delivery ratio of NRP is obviously better than those of the other protocols. The reason is that NRP adopts the static game strategy and node degree estimation algorithm to obtain node degree information while considering the boundary effects, so that it reduces the number of packet drops caused by collisions. As we all know, mobile bordering nodes are likely to get out of the node’s transmission area, thus causing broken links. Whenever a broken link occurs, a new discovery phase should be started which in turn will increase the use of control messages. Therefore, NRP improves the packet delivery ratio using the forwarding area criterion. NRP and AODV perform significantly better than AODV + FDG, AOMDV, AODV + Hello, and EEABR. It is due to the fact that the periodical broadcast of Hello messages increases network collisions, thus resulting in the reduction of the packet delivery ratio.

Figure 13.

Relationship between packet delivery ratio and nodes’ maximum speed.

Figure 14 illustrates the effects of the nodes’ maximum speed on the routing overhead. It is observed that NRP produces the lowest amount of routing overhead. As the nodes’ maximum speed increases, the routing overheads of AODV, AOMDV, AODV + Hello, and AODV + FDG increase significantly, but that of the NRP grows slowly. This is because NRP adopts the static game strategy and forwarding area criterion, which decreases the number of nodes participating in forwarding. Therefore, NRP decreases the number of control packets in the routing layer. On the other hand, AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast Hello messages periodically, thus increasing routing overhead.

Figure 14.

Effects of nodes’ maximum speed on routing overhead.

Figure 15 depicts the results of the MAC routing overhead versus the nodes’ maximum speed. Obviously, this figure shows that NRP achieves better performance in comparison to other protocols. As the nodes’ maximum speed increases, the metric of NRP grows slowly, while those of AODV + FDG, AODV + Hello, AOMDV, and AODV increase rapidly. The reason is that AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast the Hello message periodically, which results in a large number of control packets in the MAC layer. NRP adopts the static game strategy and forwarding area criterion, which reduces the number of nodes forwarding the routing requests, thus decreasing the number of control packets in the MAC layer.

Figure 15.

Results of MAC routing overhead versus nodes’ maximum speed.

Figure 16 presents the effects of the nodes’ maximum speed on the throughput. It is obvious that NRP exhibits better performance than the other protocols. The reason is that NRP obtains the node degree information without broadcasting Hello messages and then adopts the game forwarding strategy, which relieves the broadcast storm problem significantly. NRP achieves high packet delivery ratio and low delay, which increases the data packet reception efficiency.

Figure 16.

Effects of nodes’ maximum speed on throughput.

Figure 17 illustrates the results of the network lifetime versus the nodes’ maximum speed. It is seen that NRP performs better than the other protocols. As the nodes’ maximum speed increases, the metric of NRP remains stable, while that of AODV decreases rapidly. This is because NRP adopts the static game strategy, which reduces the number of nodes participating in forwarding, thus reducing the energy consumption of nodes in the network. AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast the Hello message periodically, which results in a large amount of energy of nodes.

Figure 17.

Results of network lifetime versus nodes’ maximum speed.

Verifying the effects of the nodes’ speed on protocol performance

The purpose of the simulations presented in this subsection is to study the effects of the nodes’ speed on the performance of these protocols. The nodes’ speed changes between 1 and 25 m/s. All nodes are allowed to move following the uniform speed mobility model in a field of 750 m × 750 m, in which each node moves to a random selected destination with a constant speed. The pause time is 0. The number of nodes is 70.

Figure 18 depicts the results of the average end-to-end delay versus the nodes’ speed. It can be seen that the end-to-end delays of all protocols increase with the increase in the nodes’ speed. NRP and AODV + FDG perform obviously better than AODV + Hello, AOMDV, AODV, and EEABR. It is due to the fact that, with the increase in the nodes’ speed, NRP and AODV + FDG adopt the probability forwarding, which reduces the number of redundant rebroadcasting packets.

Figure 18.

Results of average end-to-end delay versus nodes’ speed.

Figure 19 presents the relationship between the packet delivery ratio and the nodes’ speed. It shows that NRP performs better than the other protocols. The reason is that NRP adopts the static game strategy, so that it reduces the number of packet drops caused by collisions. NRP designs the forwarding area by means of considering the impact of node communication boundaries, which reduces the number of new routing discoveries caused by broken links. NRP and AODV perform significantly better than AODV + FDG, AOMDV, AODV + Hello, and EEABR. It is due to the fact that NRP and AODV do not need to broadcast Hello messages periodically, thus increasing the packet delivery ratio.

Figure 19.

Relationship between packet delivery ratio and nodes’ speed.

Figure 20 depicts the effects of the nodes’ speed on the routing overhead. It is clear that NRP exhibits the lowest routing overhead. With the increase in the nodes’ speed, the routing overheads of AODV, AOMDV, AODV + Hello, and AODV + FDG grow significantly, but that of the NRP increases slowly. This is because NRP adopts the static game strategy and forwarding area, which decreases the number of nodes participating in forwarding. Therefore, NRP decreases the number of control packets in the routing layer. On the other hand, AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast Hello messages periodically, thus increasing the routing overhead.

Figure 20.

Effects of nodes’ speed on routing overhead.

Figure 21 illustrates the results of the MAC routing overhead versus the nodes’ speed. It is obvious that NRP achieves better performance in comparison with other protocols. With the increase in the nodes’ speed, the metric of NRP grows slowly. However, the metrics of AODV + FDG, AODV + Hello, AOMDV, and AODV increase rapidly. The reason is that AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast the Hello message periodically, which results in a large number of control packets in the MAC layer. NRP reduces the number of nodes participating in forwarding, thus decreasing the number of control packets in the MAC layer.

Figure 21.

Results of MAC routing overhead versus nodes’ speed.

Figure 22 presents the effects of the nodes’ speed on the throughput. It is clear that NRP exhibits better performance than the other protocols. The reason is that NRP obtains the node degree information without broadcasting Hello messages and then adopts the game forwarding strategy, which relieves the broadcast storm problem significantly. NRP achieves high packet delivery ratio and low delay, which increases the data packet reception efficiency.

Figure 22.

Effects of nodes’ speed on throughput.

Figure 23 depicts the results of the network lifetime versus the nodes’ speed. It is clear that NRP performs better than the other protocols. This is because NRP adopts the static game strategy, which reduces the number of nodes participating in forwarding, thus reducing the energy consumption of nodes in the network. AODV + FDG, AOMDV, AODV + Hello, and EEABR broadcast Hello messages, which results in a large amount of energy consumption.

Figure 23.

Results of network lifetime versus nodes’ speed.

Conclusion and future work

In this article, we proposed a novel routing protocol considering the boundary effects (NRP) for ad hoc networks. NRP considers boundary effects to obtain the node degree information and does not apply broadcasting of Hello messages. NRP adopts the static game forwarding strategy and forwarding area, which suppresses the broadcast storm problem caused by broadcasting of routing packets in the routing discovery process. Simulation results show that NRP performs better than AODV + FDG, AODV + Hello, AOMDV, AODV, and EEABR in terms of packet delivery ratio, routing overhead, normalized MAC load, throughput, and network lifetime.

The NRP protocol has some drawbacks to be further improved. First, NRP is suitable for high-density scenarios instead of sparse ones. How to improve the NRP protocol so as to make it suitable for sparse scenarios is one future aim. Second, the NRP protocol is suitable for nodes with uniform distribution. How to make NRP suitable for the networks with non-uniform node distribution is one future work. Third, we use rectangular network scenarios to evaluate protocol performance. Although the network scenarios are not rectangular actually, some scenarios can be converted into rectangular ones. Existing network simulators such as NS-2, NS-3, and OPNET also use rectangles as network scenarios. For those network scenarios that cannot easily be converted into rectangular, we will make further research in the future. In addition, our one future aim is to study the effects of $\alpha$ and $\beta$ on the performance of NRP.