An Improved Directional Broadcast Algorithm Based on Brownian Motion

Abstract

Several broadcast algorithms have been developed in recent years. However, the problem of reducing routing overhead in ad hoc networks is always to be concerned. This paper proposes an improved directional broadcast algorithm based on Brownian motion for AODV protocol (DBB-AODV). We bring Brownian motion into network model and gain the distribution of the nodes which encountered destination before. This algorithm uses encounter records to predict the direction to destination and forwards RREQ packets with reasonable probability according to the distribution just mentioned. Simulation results indicate that DBB-AODV saves up to 20% of average routing overhead compared to the probabilistic protocol and about 80% of the blind flooding.

1. Introduction

Different from computer networks, mobile ad hoc network (MANET) is characterized by its dynamic topology. The network consists of mobile nodes equipped with wireless transceivers. The nodes could communicate at any time and any place. Because no infrastructure is involved, each mobile node should perform as both host and router. Therefore, MANETs are widely used in many fields, from battle field in the beginning to business applications and personal communication now.

Due to the limitation of the energy of mobile terminal, routing overhead is a key factor for designing routing protocols in mobile ad hoc networks. AODV is a kind of ondemand routing protocols which establishes a unique route from the source to the destination while sending packets. Utilizing blind flooding broadcast is a fundamental communication operation for routing discovery. Flooding is widely used for MANETs since it does not need topological information. However, it easily leads to severe redundancy, contention, and collision, called broadcast storm problem [1].

In order to avoid the problem, many improved algorithms have been proposed. A lot of messages are forwarded to the negative direction to the destination due to omnidirectional broadcast which causes huge redundancy. Some algorithms limit the broadcast to the forwarding zone, toward the direction of the destination. Some routing protocols draw support from equipped positioning devices or smart antenna to obtain the direction [2–4] which causes great reduction for the routing overhead. However, there is no auxiliary equipment that can be used in some cases. Some protocols use historical encounter record with destination node to replace the auxiliary equipment [5–7]. If one node is in another node's transmission range, we call two nodes encounter. According to encounter records, the general location of destination node can be predicted because the node with more recent encounter time is closer to the destination in general. Instead of searching for the destination, source node searches for intermediate node which encounters the destination more and more recently [5]. But it is also quite a waste if the nodes which encountered destination more recently all participate in forwarding. The grey area is the forwarding zone which is covered by the nodes encountered destination as shown in Figure 2.

In probabilistic algorithms [8–11], intermediate nodes forward the message based on a fixed or dynamic probability. The number of the forwarding nodes is reduced greatly, while the broadcast is still omnidirectional as shown in Figure 1. In order to further reduce the routing overhead, some algorithms combine probabilistic forwarding and the use of encounter records together, with the purpose of reducing the density of the nodes in forwarding zone [7]. Apparently, unnecessary routing messages still exist as forwarding probability is difficult to be determined. If the probability is too high, there is a waste as shown in Figure 2(a). Otherwise, the search will be quick to die.

Figure 1

Description of pure probabilistic protocol.

Figure 2

Description of directional broadcast based on encounter record (the grey area is forwarding zone which limits broadcast to the right direction to destination node. But there is still some unnecessary broadcast especially closer to destination node in (a)).

In this paper, we propose an improved routing protocol. The protocol makes use of encounter records and probabilistic forwarding to reduce routing overhead. Predict the direction to destination first and then set up reasonable forwarding probability. As we know, Brownian motion is a classical physical phenomenon and the theoretical study about the phenomenon is quite mature. Floating particles and mobile nodes in ad hoc networks have the similar motion pattern that both of them move randomly. Therefore, this paper proposes to introduce the theory of Brownian motion into ad hoc network model and gets the distribution of nodes encountered destination. The closer to the destination, the more nodes encountered it as shown in Figure 3. We try to use Brownian motion to adjust the forwarding probability based on the density of nodes with valuable encounter information. This change will minimize the loss as far as possible as shown in Figure 2(b).

Figure 3

Distribution of the nodes keeping encounter records.

The rest of the paper is organized as follows. Section 2 summarizes the related works. Section 3 presents the theoretical analysis about the distribution of nodes which encountered the destination recently based on Brownian motion. Section 4 describes the implementation of the DBB-AODV. Simulation results are provided in Section 5 and concluding remarks in Section 6.

2. Related Work

In this section, we introduce the related previous work refering to directional broadcast or probabilistic forwarding.

Location based protocols would get the general position of destination node [2, 3, 12]. Many protocols get the direction to destination with the help of smart antenna [4] guiding the search in the right direction easier. GPSR [3] is a geographic routing system that utilizes a planar subgraph of the wireless network graph to route around holes. Routing loss can be reduced greatly. However, the position or direction information cannot be got in many cases.

The protocols using encounter records can replace the location based protocols which also steer the search in the general direction to destination. The FRESH algorithm [5] uses the age gradient to constrain the search to advance “in the right direction.” Source node searches for intermediate node which encountered the destination more recently. In neighbor-assisted route discovery protocol (NARD) [13], source node floods in a limited portion of the network looking not only for the destination node but also for routing information of neighbor nodes near the destination node recently. Obviously, not every node in the forwarding zone needs to participate in forwarding.

Predecessors in probabilistic protocols have already done a lot of work. Lazy gossip [14] protocol floods periodically gossip with neighbor nodes about the packet ID they have received. A lot of attentions were paid on how to select the best forwarding probability in different network environment. Many papers adjust the probability based on the number of neighbor nodes [9, 10]. Large number of neighbor nodes means nodes distribution in network is dense and the probability should be smaller. The routing success rate is also a judgment standard in [15]. High success rate means the probability can be cut down a little and low success rate means the probability should be raised. There are also many protocols taking the rest of the energy into consideration [4].

In order to reduce routing loss further, many protocols combine probabilistic forwarding with encounter information together. In [6], the nodes in network exploit a set of routing metainformation (called hints) to discover a path from source to the destination on-the-fly. Hints are calculated by encounter time. In polarized gossiping algorithm [7], messages are forwarded with two different probabilities in and outside the forwarding zone. The determination of forwarding zone is also based on hints.

3. Theoretical Analysis

The performance of DBB-AODV is relevant closely to mobility process. Therefore, the mobility process of the nodes which encountered the destination based on Brownian motion is studied in this section.

The mobility model of the nodes in ad hoc networks is random waypoint mobility [16] and also called random motion. Nodes change mobile speed and direction randomly in this model. The concept of RWK model is the ideal mathematical state of Brownian motion. Therefore, we assume that all nodes perform Brownian motion and each node moves independently.

The mobility motion of particles floating on the liquid surface is known as Brownian motion and these particles form an ad hoc network just like the mobile nodes. We abstract a theoretical model of floating particles on the basis of realistic network. First, there is a container large enough for some water that is just like the field where the mobile nodes can move in ad hoc networks. Then, throw some particles on the water surface in the container and these particles represent mobile nodes in the network.

In order to study the mobility motion of nodes which encountered the destination, we assume that destination node at the center of the water surface and the floating particles are also thrown at the center. It means that these particles are destination's neighbor nodes and those have the encounter time record to destination. In the realistic network, the nodes keep moving and there are new nodes to meet destination every once in a while because the older neighbor nodes have moved away. In other words, the neighbor nodes around the destination node will constantly be updated. Therefore, throwing floating particles only once is not enough in the theoretical model. New particles are thrown at suitable intervals and the same place, the center of water surface, just like the destination meets the new neighbor nodes.

As shown in Figures 4 and 5, the red point is at the center of water surface and black points are particles. If the particles are thrown at the center only once, the pattern of uniform distribution would be shown after a long time. If the particles are thrown repeatedly and the outdated particles are removed in time as shown in Figure 5, the particles show the pattern of drawing close to the center. Obviously, the later the particles are thrown, the closer to the center they are. Therefore, the routing search can be guided to destination node based on encounter time.

Figure 4

Distribution of particles thrown just once.

Figure 5

Distribution of particles thrown repeatedly.

The theoretical analysis will be introduced in two parts. In the first part, particles are thrown just once, which simulates a whole diffusion process of nodes with different encounter time. In the second part, particles are thrown repeatedly to simulate the whole diffusion process of nodes with different last encounter time.

3.1. Thrown Just Once

A lot of relevant work of Brownian motion has been done, especially Einstein diffusion equation. Next, we will elaborate the derivation process of the diffusion equation which proposes probability and random process by Albert Einstein in detail [17]. For simplicity, we just consider one-dimensional space (x direction) and generalize it to multidimensional space by parity of reasoning.

The particles are thrown in the container at $t=0$ and $x=0$ . We assume that $P(\Delta )$ represents the probability density that one particle shifts Δ in the x direction in specific time range. And $P(\Delta )$ meets the normalization condition:

$$\begin{array}{cc}& {{\displaystyle \int }}_{-\infty }^{\infty }P\left(\Delta \right)d\Delta =\mathrm{1}.\end{array}$$

(1)

$f(x,t)$ represents the number density of nodes at time t and position x. Noting that t is not the traditional sense of the time, but it is the diffusion time of particles, which starts when particles were thrown in container. Then, we get the following relation:

$$\begin{array}{cc}& f\left(x,t+\tau \right)={{\displaystyle \int }}_{\Delta =-\infty }^{\infty }f\left(x-\Delta ,t\right)P\left(\Delta \right)d\Delta .\end{array}$$

(2)

Because τ is very small, we get the following formula:

$$\begin{array}{cc}& f\left(x,t+\tau \right)\approx f\left(x,t\right)+\tau \frac{\partial f\left(x,t\right)}{\partial t},\\ f\left(x-\Delta ,t\right)\approx f\left(x,t\right)-\Delta \frac{\partial f\left(x,t\right)}{\partial x}+\frac{{\Delta }^{\mathrm{2}}}{\mathrm{2}}\frac{{\partial }^{\mathrm{2}}f\left(x,t\right)}{\partial x^{\mathrm{2}}}.\end{array}$$

(3)

Then, we can get the following formula:

$$\begin{array}{l}f+\frac{\partial f}{\partial t}·\tau \approx f{{\displaystyle \int }}_{-\infty }^{\infty }P\left(\Delta \right)d\Delta -\frac{\partial f}{\partial x}{{\displaystyle \int }}_{-\infty }^{\infty }\Delta P\left(\Delta \right)d\Delta \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+\frac{{\partial }^{\mathrm{2}}f}{\partial x^{\mathrm{2}}}{{\displaystyle \int }}_{-\infty }^{\infty }\frac{{\Delta }^{\mathrm{2}}}{\mathrm{2}}P\left(\Delta \right)d\Delta .\end{array}$$

(4)

Based on the normalization condition and the symmetrical nature of the positive and negative, the above equation can be simplified to the following form:

$$\begin{array}{cc}& \frac{\partial f}{\partial t}=D\frac{{\partial }^{\mathrm{2}}f}{\partial x^{\mathrm{2}}},\end{array}$$

(5)

$$\begin{array}{cc}& D=\frac{\mathrm{1}}{\mathrm{2}\tau }{{\displaystyle \int }}_{-\infty }^{\infty }{\Delta }^{\mathrm{2}}P\left(\Delta \right)d\Delta .\end{array}$$

(6)

Equation (6) is diffusion equation. D represents diffusion capability of particles and it is a constant which is called diffusion coefficient. In ad hoc networks, D represents diffusion capability of mobile nodes. D is relevant to the size of network and the number and the moving speed of nodes. Let N represent the total number of particles and all particles are located at the place where $x=0$ at start. Then, get the solution for the diffusion equation as follows:

$$\begin{array}{cc}& f\left(x,t\right)=\frac{N}{\sqrt{\mathrm{4}\pi Dt}}{e}^{-x^{\mathrm{2}}/\mathrm{4}Dt}.\end{array}$$

(7)

As the description of diffusion equation above, $f(x,t)$ represents the number density of the particles. Apparently, $f(x,t)$ is normal distribution based on (7) as shown in Figure 2. Obviously there are more nodes when we get closer to the destination. With the moving time getting longer and longer, nodes run away farther and farther, yet they still keep the characteristics of normal distribution. The longer the particles move, the wider and lower the distribution curve becomes. However, after a very long time, the distribution curve would become a straight line. It means that the encountered nodes may be distributed in the network evenly and there is no close relationship between the destination node and the encountered nodes. Therefore, in DBB-AODV, not all encountered nodes can be utilized. Because the distribution pattern of nodes with outdated encounter records is more likely to a uniform distribution than to a bell-shaped one, prediction based on them will cause inaccuracy. Therefore, we limit the lifetime of encounter record and let T represent this time threshold.

3.2. Thrown Repeatedly

Through the derivation above, we know that the mobility of the particles presents the normal distribution when thrown just once and $f(x,t)$ represents the number density of the nodes at time t and position x. The neighbor nodes around the destination node are constantly updated. Therefore, we should throw particles in the container at the same position repeatedly to simulate the distribution of particles with different last encountered records. In other words, at the same position where $x=0$ and the different time, we should throw different number of particles. We assume that the number of particles thrown is $N_j$ ( $j=1,\dots ,S$ ) at jth time. $f(x,t_j)$ represents the number density of nodes thrown at different time and $t_j$ ( $j=1,\dots ,S$ ) is diffusion time from the time throwing particles into container up to now. Then $f(x,t_j)$ is calculated as follows:

$$\begin{array}{cc}& f\left(x,t_j\right)=\frac{N_j}{\sqrt{\mathrm{4}\pi D{t}_j}}{e}^{-x^{\mathrm{2}}/\mathrm{4}D{t}_j},\hspace{1em}(j=\mathrm{1},\dots ,S).\end{array}$$

(8)

There exists a time threshold T explained in the above section. Therefore, the number of thrown particles is also limited in the limited time. Namely, S is limited. By adding all these functions with different diffusion time together we get the following formula:

$$\begin{array}{l}{\displaystyle \sum }_{j=1}^{s}f\left(x,t_j\right)=f\left(x,t_1\right)+f\left(x,t_2\right)+\cdots +f\left(x,t_s\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\frac{N_1}{\sqrt{4\pi D{t}_1}}{e}^{-x^2/4D{t}_1}+\cdots +\frac{N_s}{\sqrt{4\pi D{t}_s}}{e}^{-x^2/4D{t}_s}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\displaystyle \sum }_{j=1}^s\frac{N_j}{\sqrt{4\pi D{t}_j}}{e}^{-x^2/4D{t}_j}.\end{array}$$

(9)

We assume that the average time interval of throwing particles in container is $\Delta t$ . The above formula can be simplified as

$$\begin{array}{l}{\displaystyle \sum }_{j=1}^{s}f\left(x,j·\Delta t\right)\\ \hspace{1em}=f\left(x,\Delta t\right)+f\left(x,2\Delta t\right)+\cdots +f\left(x,s\Delta t\right)\\ \hspace{1em}=\frac{N_1}{\sqrt{4\pi D\Delta t}}{e}^{-x^2/4D\Delta t}+\cdots +\frac{N_s}{\sqrt{4\pi Ds\Delta t}}{e}^{-x^2/4Ds\Delta t}.\end{array}$$

(10)

Assuming $N_1=\cdots N_j=\cdots =N_s$ and $f(x,j·\Delta t)$ are independent of each other, we get the following formula:

$$\begin{array}{cc}& {\displaystyle \sum }_{j=1}^{s}f\left(x,j·\Delta t\right)=\frac{N_1}{\sqrt{2\pi }·\sqrt{D\Delta t·S(S+1)}}{e}^{-x^2/2D\Delta t·S(S+1)}.\end{array}$$

(11)

According to formula (11), we know that if x is very small, $\sum f(x,t_j)$ is great. Otherwise, $\sum f(x,t_j)$ is small. Map this result to the ad hoc network and we get that the closer to the destination the more nodes encountered it, just as shown in Figure 3. When source node is far away from the destination, the number of nodes keeping encounter records with destination is small and the possibility of finding these nodes is slimmer. Therefore, the forwarding probability is great under this circumstance. When RREQ packet is near the destination, the density of nodes with fresh encounter records becomes larger. So, the possibility of confronting these nodes is also greater. We do not need every one nearby to forward the RREQ even though we know that they really can take the packet to the destination successfully. Actually, we only need one. With the purpose of reducing routing overhead unnecessary, forwarding probability should be smaller and smaller. From formula (11), we get that if x is fixed, $\sum f(x,j·\Delta t)$ is a constant. The number of nodes keeping encounter record away from destination with different distance is a constant. In other words, after a long time, it would be almost a stable state.

Assume that the number of particles thrown in container every time is the same and equal to the mean number of neighbor nodes that the destination encountered each time. Based on the conclusion from Section 3.1, we learn that the mobility of particles thrown once presents normal distribution. Just as shown in Figure 6, we can regard the two curves as the distribution curves of nodes which encountered destination in different time. The steep curve shows the nodes with more recent encounter time and the other curve shows the nodes with longer encounter time. Obviously, there are more nodes with more recent encounter time at the position closer to destination. Therefore, when RREQ packets find the nodes having more recent encounter time, the forwarding probability should be smaller.

Figure 6

Distribution of number density.

4. Improved Algorithm

According to the theoretical analysis in Section 3, we get the distribution of nodes keeping encounter records and it is necessary to put forward a new algorithm for further reducing routing overhead. In this section, DBB-AODV is described in detail.

4.1. Monitor and Record

DBB-AODV is closely related to encounter records. Each node needs a table to record the encounter records with other nodes in network, which we call encounter record (ER) table. The ER table includes node ID and the most recent encounter time, also called as last encounter time. In communications, each node receives lots of packets from the nodes within its transmission range, including RREQ, RREP, RRER, and HELLO packets. When one node receives a packet, it first inquires the ER table to see whether the record of last-hop node exists.

If the record exists, which means that these two nodes have encountered before, the record will be updated with the most recent encounter time. If not, a new record will be inserted.

As shown in Figure 7, when the intermediate node i receives a packet from node 2 for the first time, this record will be inserted into the table with encounter time $t_2$ and node ID. If the intermediate node i receives a packet from node 1 once more, the ER table will update the record with the latest encounter time $t_3$ .

Figure 7

Operation of ER table of node i.

In Section 3, we explain that the lifetime of records is limited and assume the time threshold is T. Therefore, the outdated record will be removed when the lifetime exceeds the threshold T. When the node inquires the table on receiving a packet, the outdated records can be removed by the way.

4.2. Packet Forwarding

Generally, if source node has encounter record with destination node before, there would be a lot of nodes which also encountered the destination around it. The possibility of finding the destination is very large only with the aid of these nodes. If source node does not have encounter record with destination node, there may be a few nodes which encountered the destination before around it. The possibility to find the destination is very small only with the aid of these nodes which encountered destination. In other words, not only these nodes which encountered destination but also the nodes without records with destination should be involved in forwarding zone. Therefore, we divide the new algorithm into two parts according to whether the source node has encounter record with destination or not.

4.2.1. Encountered Recently

There are three kinds of nodes: source node s, destination node d, and intermediate node i. When source node s needs to build the route to destination d, it first looks up the ER table and gains the conclusion whether the record with destination node d exists. If the record exists, source node puts this last encounter time into the head of RREQ packets and broadcasts them to its neighbor nodes. At the same time, mark this packet in reserved field in order to facilitate the intermediate nodes to make reasonable judgment. Similarly, if other nodes receive RREQ packets, they put their last encounter time into the packets too. If they never encountered the destination before, the nodes put infinity into the packet.

When intermediate node i receives a RREQ packet, it confirms whether a fresh enough route in route table to destination node d has existed. If it exists, node i sends reply to source node s and this route will be established.

If the fresh route does not exist, the establishment of this route needs to use encounter records. If intermediate node i does not have encounter record, the RREQ packet is discarded directly because the route can be set up with the nodes keeping encounter record. If intermediate node i has encounter record, some simple calculations are needed. The accurate distance to the destination is not easy to get; however, there is correlation between the last encounter time and moving distance within a certain period of time which is proved by the experiment in [5]. The relationship between encounter time and the moving distance is close to linearity within a certain period of time. Therefore, the intermediate nodes choose reasonable forwarding probability with the help of the last encounter time. The calculations mainly consist of three time differences: the time difference $t_d$ between the current time $t_c$ and the last encounter time of current node $t_{e-c}$ , the time difference $t_{d-l}$ between the current time $t_c$ and the last encounter time from last-hop node $t_{e-l}$ , and the time difference $t_{\Delta }$ between the two time differences $t_{\Delta 1}$ and $t_{\Delta 2}$ :

$$\begin{array}{cc}& t_d=t_c-t_{e-c},\\ t_{d-l}=t_c-t_{e-l},\\ t_{\Delta }=t_d-t_{d-l}.\end{array}$$

(12)

If $t_{\Delta }>0$ , the last-hop node encountered the destination more recently than current node. The distance between current node and destination node is farther than last-hop node in all probabilities. Obviously, letting the nodes further away from destination forward RREQ packet is not reasonable. The RREQ packet is discarded.

If $t_{\Delta }<0$ , the current node encountered the destination more recently than last-hop node. That is to say, the distance between current node and destination node is closer than last-hop node in all probabilities. However, based on the distribution density, the closer to destination, the more nodes keep last encounter time will be found in the forwarding process. Therefore, the forwarding probability should be smaller and smaller as the distance to destination is closer and closer.

Assume $x=vt$ (v is the average speed of mobile node) and substitute $j·\Delta t$ for $S·\Delta t$ from formula (11). We get

$$\begin{array}{cc}& {\displaystyle \sum }_{j=1}^{s}f\left(x,j·\Delta t\right)=\frac{N_1}{\sqrt{2\pi D(S+1)}}·\frac{1}{\sqrt{j·\Delta t}}{e}^{-\left(v^2/2D\left(S+1\right)\right)·j·\Delta t}.\end{array}$$

(13)

When we substitute $j·\Delta t$ for $S·\Delta t$ , the variance of the distribution function will be decreased, which makes the distribution curve of density function slimmer and taller. In this case, nodes far away from the destination express a slimmer density than before, which can bring about higher forwarding probability for the purpose of successful establishment of connection. And nodes near the destination express a higher density, which brings about smaller forwarding probability. Due to the high density of nodes with encounter records, a relative small forwarding probability will not make any difference.

Put all of the constant term together and substitute t for $j·\Delta t$ . Simplify $\sum f(x,t_j)$ to

$$\begin{array}{cc}& {\displaystyle \sum }f\left(x,t_j\right)=\alpha \frac{1}{\sqrt{t}}{e}^{-kt},\\ \alpha =\frac{N_1}{\sqrt{2\pi D(S+1)}},\hspace{1em}k=\frac{v^2}{2D(S+1)}.\end{array}$$

(14)

The forwarding probability is inversely proportional to $\sum f(x,t_j)$ . So, get the probability P as the following formula:

$$\begin{array}{cc}& P=\beta ·\frac{1}{\alpha }\sqrt{t_d}{e}^{{kt}_d}.\end{array}$$

(15)

$t_d$ is still the time difference between the current time and the last encounter time of current node. Because parameter D representing diffusion ability of mobile nodes in ad hoc network is unknown, α and k are parameters changing with the network density and the average speed of mobile nodes. The best value of α and k is obtained through experiments.

Not every route can be set up successfully. If the route fails to be built up repeatedly, the forwarding probability would be increased. Of course, if the route can be set up successfully every time, the forward probability maybe a little higher. Cutting down a little bit is reasonable. Therefore, β is a self-adapting parameter changing with the success ratio of route establishment.

The detailed algorithm process is shown in Algorithm 1.

Algorithm 1

Definition:

Random(0, 100): Return a random number between $[$ 0, 100)

   if recently received this RREQ then

  drop RREQ packet; return; end if

   if I am the destination then

    send RREP to source; return; end if

   if I has a fresh enough route to destination then

       send RREP to source; return; end if

if source node has encounter record then

  lookup the ER Table

    if the record to destination exists then

     calculate $t_{\mathrm{\Delta }}$ ;

     if   $t_{\mathrm{\Delta }}<0$   then

        adjust α based on success rate of route establishment

          if Random(0, 100) < P  then

          forward the RREQ; return;

          else drop this RREQ; return; end if

     else drop this RREQ; return; end if

    else drop RREQ packet; return;

end if

4.2.2. Never Encountered Recently

If source node does not have the last encounter record with destination, more nodes need to be involved in forwarding process. Besides the nodes keeping records, the nodes which did not encounter the destination recently should also participate in forwarding.

When source node initiates route search without the last encounter time record, it puts infinite into the packet which marks that source node has no time record in reserved field. If the intermediate node does not have record too, the forwarding probability $P_b$ is chosen based on network density as shown in pure probabilistic algorithm [10]. Intermediate node estimates the local density around it according to the HELLO packets sent from its neighbor nodes. On the other hand, if intermediate node has time record with destination, the forwarding probability also is P as the situation when source node has time record. Do the same calculations to get $t_{\Delta }$ and set reasonable value for the parameters α and k. The detailed algorithm process is shown in Algorithm 2. If all the nodes did not encounter destination recently, DBB-AODV becomes the pure probabilistic algorithm with the best forwarding probability $P_b$ .

Algorithm 2

if source node has no encounter record then

  lookup the ER Table

    if the record to destination exists then

      the RREQ is forwarded with probability P; return;

    else

      the RREQ is forwarded with best probability $P_b$ ; return;

    else    drop RREQ packet; return;

end if

5. Performance and Simulation Results

To assess the performance of DBB-AODV, we have performed simulations based on random walk model. The mobile speed set in random walk model is the maximum velocity rather than average velocity.

The simulations were performed in two parts: warm-up period of 500 s and statistical data collection period. In the warm-up period, simulations run with blind flooding protocol in the first 500 seconds in order to get more chances to meet other nodes. After warm-up period, the simulations run with DBB-AODV to collect the statistical data. Parameters of the model used in simulations are summarized in Table 1.

Table 1

Simulation parameters.

Parameter	Value
Simulator	ns-2.34
Simulation time	1000 sec
Simulation area	1000 × 1000
Transmission range	250 m
Node number	100
Bandwidth	2 MBit
Traffic type	CBR
Bandwidth	2 Mbps
Speed	2, 5, 8, 11, 14, and 17 m/s

In addition to the new protocol, we also simulate and compare three other protocols: blind flooding, probabilistic protocol [10], and FRESH protocol [5]. In probabilistic protocol, the forwarding probability of intermediate node is dynamically based on the number of neighbor nodes. In FRESH protocol, source node searches for intermediate node which encountered the destination more recently by expanding ring search algorithm.

Four performance metrics were estimated during the simulation: average path length, average end-to-end delay, normalized overhead, and packet delivery fraction.

Figures 8, 9, 10, and 11 show how the performance metrics vary with different speed. Here comes the explanation of the figure.

Figure 8

Packet delivery ratio varies with speed.

Figure 9

Average routing overhead varies with speed.

Figure 10

Average path length varies with speed.

Figure 11

Average end-to-end delay varies with speed.

Packet Delivery Fraction. The packet delivery fraction is depicted in Figure 8. Blind flooding is the most stable protocol. But three other protocols also perform well. FRESH protocol searches destination with flooding if the first time failed. Therefore, it avoids the case that no nodes meet the destination. DBB-AODV gets help of the nodes without the last encounter time and also gains the high packet delivery fraction. So, the success rate of link prediction is high.

Average Routing Overhead. The average number of RREQ packets consumed to successful deliver one data packet to the destination. As shown in Figure 9, the difference among each protocol is very obvious. Blind flooding is the most wasted. Probabilistic protocol is better than FRESH protocol because FRESH protocol does not have obvious advantage in the network without a large number of nodes. DBB-AODV has a distinct advantage saving up to 20% of average routing overhead compared to the probabilistic protocol and about 80% of the blind flooding. This result proves that DBB-AODV is an efficient means to track the destination node.

Average Path Length. The route established by DBB-AODV is not the shortest path as shown in Figure 10. There also exists the problem of roundabout because the nodes participating in forwarding may not be near the straight line connecting source node with destination node. So, more improvement can be made in the future work.

Average End-To-End Delay. Since the route is not the shortest path, average end-to-end delay of DBB-AODV is also not the best as shown in Figure 11. The end-to-end delay relates to many factors and this should be covered in the future work.

6. Conclusion

This paper verifies the good performance of DBB-AODV by simulations. Routing overhead is greatly reduced and packet delivery fraction is high meanwhile. What is more, the forwarding probability can be changed adaptively according to network situation. How to make the route approach the shortest path as much as possible is a key question we would pay more attention to in the future.