Communications and Network, 2013, 5, 408-413
http://dx.doi.org/10.4236/cn.2013.53B2075 Published Online September 2013 (http://www.scirp.org/journal/cn)
Copyright © 2013 SciRes. CN
Ad Hoc On-Demand Mu l ti path Dis tance Vector Routi ng
Protocol Based on Node State
Jieying Zhou, Heng Xu, Zhaodong Qin, Yanhao Peng, Chun Lei
School of Information Science and Technology, Sun Yat-sen University, Guangzhou, China
Email: isszjy@mail.sysu.edu.cn
Received June 2013
ABSTRACT
To improve the performance of Ad hoc on-demand multipath distance vector (AOMDV) protocol, we proposed NS-
AOMDV which is short for “AOMDV based on node state”. In NS-AOMDV, we introduce node state to improve
AOMDV’s performance in selecting main path. In route discovery process, the routing update rule calculates the node
weight of each path and sorts the path weight by descending value in route list, and we choose the path which has the
largest path w eight for data transmission. NS-AOMDV also uses the technology of route request (RREQ) packet delay
forwarding and energy threshold to ease network congestion, limit the RREQ broadcast storm, and avoid low energy
nodes to participate in the establishment of the path. The results of simulation show that NS-AOMDV can effectively
improve the networkspackets delivery rate, through put and normalized routing overhead in the situation of dynamic
network topology and heavy load .
Keywords: Ad Hoc; AOMDV; Node State; Path Weight; Packet Delay Forwarding; Energy Threshold
1. Introduction
Mobile ad hoc network is a self-organized and special
wireless communication network, which is made up of
some mobile nodes by using distributed protocols. Since
each node in ad hoc network has the function of the host
and router, it has the characteristics of flexibility and
convenience in deployment. In the situation of no fixed
network infrastructure, mobile ad hoc network can com-
municate with each other by using multi-hop way, and
provide the convenience to some special occasions such
as medical, meeting, military and so on. Routing protocol
[1] plays an important role in the communication be-
tween nodes. And the research of it has become a hot spo t.
This paper discusses the existing defects when the
AOMDV [2,3] selects the main path. We introduce NS-
AOMDV, a protocol based on node state that can effec-
tively improve the performance of AOMDV.
The rest of the paper is organized as follows. Section 2
describes the related work. In Section 3, we make some
network model assumptions. The design of NS-AOMDV
is showed in Section 4, and its performance is evaluated
and compared with AOMDV and AODV [4] in Section 5.
At last, we make a short conclusion in Section 6.
2. Related Work
The main idea in AOMDV is to compute multiple paths
during route discovery procedure for contending link fail-
ure [5]. When AOMDV builds multiple paths, it will se-
lect the main path for data transmission which is based
on the time of routing establishment. The earliest one
will be regarded the best one, and only when the main
path is down other paths can be effective. In fact, a large
number of studie s indic ate t hat t he aforem entione d scheme
is not necessarily the best path. Mobile nodes, which usual-
ly due to residual energ y are too low or under h eavy load
and other factors, seriously affect the performance of the
network. In order to improve the performance, we pro-
pose the novel NS-AOMDV protocol based on existing
AOMDV. First, we consider the rate of node residual
energy and idle buffer queue as the weight of node. Second,
in route discovery process, the routing update rules cal-
culate the node weight of each path and sort the path
weight by descending value of path weight in route list,
and we choose the path which has the largest path weight
to transmit data packets. At the same time, the protocol
uses the technology of RREQ delay forwarding [6] and
energy threshold to ease network congestion, limit the
RREQ broadcast storm, and avoid low energy nodes to
participate in the establishment of the path.
3. Network Model Assumptions
In the process of designing routing protocols, we make
J. Y. ZHOU ET AL.
Copyright © 2013 SciRes. CN
409
some network model assumptions:
We assume the ad hoc network is an undirected graph
,G NL=<>
, where
N
is the number of nodes in
the network, and
L
represents the number of link.
In this network, each node owns the ability of receiv-
ing and fo rwardin g da ta.
Every node is made up of some network compo-
nents. These components include a network interface,
the MAC layer, interface queue, link layer and the
module for node receiving information and
processing information, etc. Mobile node information
can got through these artifacts.
In the network, each mobile nod e is p eer-to-peer, shares
radio channel, and uses the IEEE 802.11 protocol in
MAC layer.
4. NS-AOMDV Design
4.1. The State Parameters of The Node
1) Residual Energ y Rate
This paper first defines residual energy rate
()
i
et
,
which refers to the residual energy level of the node
n
at
a certain time of
t
. The formula is shown as follows:
()
() i
i
initial
Et
et E
=
. (1)
Where,
()
i
et
is the residual energy of the node at
time t, and
is the initial energy of it. We can eas-
ily find that
()
i
et
indicates one nodes level of energy
consumption. At the same time, this parameter also can
indirectly reflect the location of a node in the network. In
the network, each node produces energy consumption due
to sensing the signal of the neighbor no des around. Then
excessive power consumption means large node density
of one node in the case of common communication ser-
vice. As a result, it can b e concluded that its under heavy
load in the process of communication.
2) The Idle Rate of Buffer Queue
The idle rate of buffer queue is expressed by the for-
mula below:
max
max
()
()
i
i
L Lt
lt L
=
. (2)
Where,
()
i
Lt
is defined as the length of the buffer
queue at time t.
max
L
means the maximum length of the
buffer queue. This formula reflects the congestion status
of the network. The smaller available buffer queue length
means more data packets need to be processed and worse
network congestion.
In ad hoc networks, a mobile node can be considered
as a consist of the network interface, the MAC layer,
interface queue, the link layer and the modules of receiv-
ing and processing information, as shown in Figur e 1. It
shows the MAC layer a nd the link layer; when a node in
Figure 1. Diagram for mobile node structure.
the transmitted data packet, the data stream is usually
required in the node interface queue filter delete processing.
Therefore, we get the idle rate of buffer queue by calcu-
lating the length of the interface queue, namely we utilize
the bottom of the interface queue information to reflect
the network status.
3) Node Weight
To some extent, two state parameters above reflect the
status of the network. In this paper, we will take both of
them into consideration, and propose a new definition
which is called No de Weight (NW). The formula is shown
as follows :
()() ()
i ii
NW tetlt
αβ
=+
. (3)
Where,
1, 1
αβ αβ
+≤≤ ≤≤=1(00 )
, if
αβ
>
, the
residual energy rate is the main consideration. If
αβ
<
,
we contend the idle rate of buffer queue as the main in-
fluencing factor.
4.2. Selecting The Main Path
First, we define Path Weight (PW) as the least NW of all
nodes on a path. Its computation formula is as follows:
() {min(())|}
ii
PW tNW tiNODE= ∈
. (4)
()
i
PW t
is the path weight at time t, and
NODE
is
the set of nodes on a path. Because we need to take the
level of every path into consideration when we select the
main path, it includes two important steps: updating path
weight and selecting the main path.
1) Updating Pa th Weight
Updating node weight occurs in the time of routing
updating. Meanwhile, we can get path weight of every
path. NS-AOMDV is similar to AOMDV, and its main
difference is that NS-AOMDV needs to update node weight
in the ste p of updatin g route.
2) Selecting The Main Path
The main idea in AOMDV is to co mpute mult iple paths
during route discovery procedure for contending link fail-
ure. When AOMDV creates multip le paths between source
node and destination node, only the path based on some
metric is chosen for data transmission.
In other words, the path which first reaches the desti-
nation node is chosen for the primary path and the other
paths will become alternate ones. In this way, we can
quickly create a path for data transmission. However, we
J. Y. ZHOU ET AL.
Copyright © 2013 SciRes. CN
410
ignore the state of the nodes own level and other factors.
Nodes, which own the low level of residual energy and
heavy load, may exist in the primary path. If so, this path
is very likely to be disconnected because of energy dep-
letion.
Compared to AOMDV, NS-AOMDV firstly utilizes
the forward path on which the first RREP packet arrives
at source node earliest for data transmission. When mul-
tiple RREP packets arrive at the source node, it will util-
ize the path which owns the largest PW recorded in the
routing table for data transmission. Because PWs are in
descending order in route table, we can always select the
path of largest PW every time. The formula is as follows:
max{() |}
list p
routePW tpPATH= ∈
. (5)
Where,
list
route
represents the path for data trans-
mission and
PATH
is the set of paths in routing table.
4.3. Technology of RREQ Delay Forwarding
In the route disc overy proce dure, we can al so control those
intermediate nodes with heavy load to delay forwarding
RREQ packet, based on the level of NW. Its main go al is
to allow a node with lighter load to be quickly involved
in setting up the path. Its main purpose is to make a lighter
load node to participate in the establishment of the path
quickly. Also the node with heavy load can participate in
the establishment of the path again when the network
status improves. In this way, network traffic is balanced
and network congestion is avoided efficiently. The paths
will be relatively independent at the same time. We get
the RREQ delay forwarding time based on the formula
below:
,( )0.5
() ,( )0.5
()
ci
ici
i
TNW t
delay tTNW t
NW t
>
=
. (6)
Where,
()
i
delay t
is the time for intermediate node i
forwarding RREQ packet. In AOMDV,
c
T
is the time
that set for forwarding the RREQ packet by default. If
( )0.5
i
NW t>
, it reflects the node owns light load. So if
( )0.5
i
NW t<
, it means the node is busy now, it should
delay forward this RREQ packet.
4.4. Technology of Energy Threshold
It’s very dangerous while the intermediate node owns
low level of energy and it also needs to forward RREQ
packet simultaneously. If you accidentally use it to estab-
lish one route, it will easily lead to the emergence of
network segmentation. In order to avoid selecting this
kind of nodes involved in the route setup, we set up an
energy threshold
threshold
E
to exclude them. The energy
threshold size setting refer s to the Ref. [7] setting method.
Ref. [7] points out that one nodes energy level is classi-
fied as a “discarded” level, and its survival time will be
estimated less than 10s when the residual energy of it is
less than 10% of the initial. We propose to set the energy
threshold 20% based on this. In the process of interme-
diate node processing RREQ packet, only when its own
residual energy rate is larger than
threshold
E
, will it for-
wards the RREQ packet.
5. Performance Evaluation
To evaluate the performance of NS-AOMDV, we com-
pare it with AODV and AOMDV by using NS2.34. In
the pro cess of si mulation , we assu me ever y protocol shares
the same model and node configuration. Their initial pa-
rameters are shown in Table 1. Also we assume α = β =
0.5. We eva luate the p erformance o f NS-AOMDV through
four metrics below:
Packet delivery rate
Throughput
The normaliz ed routing overhead
The average end-to-end delay
5.1. Simulation Scenario 1: Varying Mobility
We set the speed of sending packets 1 packet/s. Pause
time for the node is 10 seconds. The maximum number
of connections between the nodes is 20. The maximum
moving speed of the node changes in 5 m/s, 10 m/s, 15
m/s, 20 m/s, 25 m/s, 30 m/s.
Figure 2 plots packet delivery rate against the maxi-
mum moving speed. The graph demonstrates packet de-
livery rate of the thre e protocols ar e significantly redu ced
with the increase of node maximum speed. But NS-
AOMDV has a higher packet delivery rate than the other
two. The reasons for NS-AOMDVs better performance
are shown as follows:
Table 1. Initial parameters for node configuration.
Parameter Value
Dimensions 1000 m × 1000 m
Number of nodes 30
Source type CBR
Antenna Type Omnidirectional
Spread type TwoRayGround
Wireless channel capacity 2 Mb/s
Communication radius 250 m
Packet size 512 bytes
Initial Energy 60 J
Transmission power 1.3 W
Reception power 0.8 W
Buffer size 50
MAC Layer IEEE802.11b DCF
Transport Layer UDP
Simulation time 300 s
J. Y. ZHOU ET AL.
Copyright © 2013 SciRes. CN
411
Figure 2. Packet delivery rate as the changes of the maxi-
mum moving speed of the node.
Comprehensive consideration of residual energy
rate and idle rate of buffer queue in selecting the main
path.
Setting energy threshold avoids the nodes with
lower energy participating in the construction of the
path.
These measures ensure the main path more robust and
data transmission more reliable.
Figure 3 reflects the network throughput varies with
the changes of speed. When the mobile nodes speed up,
throughput of the three agreements declines significantly.
Because NS-AOMDV employs the technology of RREQ
delay forwarding, it limits the broadcast storm of RREQ,
eases the network congestion and balances network traf-
fic. It also takes the length of buffer queue in the process
of selecting the main path. All aforementioned schemes
causes hi g her thro ughput.
Figure 4 shows the normalized routing overhead in-
creases with th e increase of maximum moving speed. Due
to path failure, AODV needs to re-route discovery process,
which corresponding increases routing overhead simul-
taneously. In the other two protocols, NS-AOMDV owns
higher normalized routing overhead at the speed of 20
m/s. Overall, NS-AOMDV is better than AOMDV. The
main reason is that NS-AOMDV sets the energy thre-
shold, forces some node with low energy not to forward
RREQ packets and reduces the amount of control packets
sent. On the other hand, RR E Q de l a y forwarding im proves
the ratio for node processing RREQ packets, optimizes
the forwarding mechanism, and avoids some unnecessary
routin g overheads.
Figure 5 demonstrates that the average end-to-end de-
lay has a tendency to increase with the acceleration of the
maximum speed of the mobile node. i.e., the instability
of the network topology causes that time for data trans-
mission and processing increases. Because AODV has no
Figure 3. Throughput as the changes of the maximum
moving speed of the node.
Figure 4. Normalized routing overhead as the changes of
the maximum moving speed of the node.
Figure 5. Average end-to-end delay as the changes of the
maximum moving speed of the node.
J. Y. ZHOU ET AL.
Copyright © 2013 SciRes. CN
412
alternate path, it needs to re-route discovery process and
consume a certain period of time when the primary link
is broken. In multi-path protocols, there are more advan-
tages in this aspect. The average end-to-end delay of
NS-AOMDV is larger than AOMDV. On the one hand,
in the process of forwarding RREQ packet, NS-AOMDV
needs delay forwarding according to the state of the node.
Therefore it spends extra time. On the other hand, in se-
lecting a path for data transmission, NS-AOMDV focus-
es on the reliability, wh ile AOMDV focuses on the time.
So NS-AOMDV makes a certain sacrifice in the average
end-to-end delay.
5.2. Simulation Scenario 2: Varying Pause Time
We set the speed of sending packets 1 packet/s. The maxi-
mum number of connections between the nodes is 20.
The maximum moving speed of the node is 10 m/s. The
pause time of the node changes in 0 second, 20 seconds,
40 seconds, 60 seconds, 80 seconds, 100 seconds.
Figure 6 shows packet delivery rate is low when net-
work topology changes rapidly. Packets delivery rate in-
creases with the augment of nodes pause time. Since the
introduction of node weight, NS-AOMDV ensures the
selected path robust enough. Especially when the net-
work tends to be stable, NS-AOMDV shows better per-
formance than t he others.
Figure 7 demonstrates that throughput augments sig-
nificantly when the pause time increases dramatically.
The introduction of node weight and technology of RREQ
delay forwarding, which balances the utilization of vari-
ous nodes in the network, improves the performance of
throughput.
Figure 8 shows the changes in normalized routing
overhead. There is a decreasing trend in the normalized
routing overhead of the three protocols. This illustrates
that with the increase of pause time, the rate for the des-
tination node successfully accepting the request packet
improves. With the changes of pause time, the normalized
routing overhead changes slightly, which shows the per-
formance of the three protocols on routing overhead is
relatively stable. Similarly, AODVs bigger routing over-
head is mainly caused by several route discovery processes,
and the local repair mechanism also requires a certain
overhead. The setting of energy threshold decreases the
control packets sent by low-energy node. At the same
time, the delay forwarding RREQ enhances the efficien-
cy for node processing route request p acket. It makes the
NS-AOMDV protocol performs better than AOMDV in
this aspect.
Figure 9 shows that when the node pause time in-
creases, the end-to-end delay of the network tends to de-
crease, but brings in some volatility due to the change of
node mobility. It also tells us that AODV has a large gap
with the other two. The main reason for the gap is re-
Figure 6. Packet delivery rate as the changes of pause time.
Figure 7. Thr ou gh put as the changes of pause time.
Figure 8. Normalized routing overhead as the changes of
pause time.
routing discovery process takes time, and the frequency
of route discovery is faster than multi-path protocols. For
J. Y. ZHOU ET AL.
Copyright © 2013 SciRes. CN
413
Figure 9. Average end-to-end delay as the changes of pause
time.
two types of multi-path routing protocol, NS-AOMDVs
end-to-end delay is still longer than AOMDV. This fur-
ther illustrates delay forwarding RREQ and selecting the
main path need some extra time.
From the simulation results of two scenarios, we can
conclude that most performances of the network will get
different degrees of improvement when network topolo-
gy tends to be flattened. As for overall performance, AODV
performs worse than AOMDV and NS-AOMDV espe-
cially in time delay and normalized routing overhead. For
two multi-path protocols, NS-AOMDV is generally bet-
ter than AOM DV .
6. Conclusion
In this paper, a novel multipath distance vector routing
protocol, NS-AOMDV, for MANETs is proposed to im-
prove some performances of present AOMDV. In the
process of building transmission path, we synthetically
consider the residual energy rate and the idle rate of buf-
fer queue. And we introduce the technology of RREQ
delay forwarding and energy threshold in route discovery.
Also we update the information of the nodes on the path,
and choose the path of maximum node weight for data
transmission.
REFERENCES
[1] Z. Chen, L. Guan, X. Wang and X. Fan, “Ad hoc
On-demand Multipath Distance Vector routing with
Backup Route Update Mechanism,” IEEE 14th Interna-
tional Conference on High Performance Computing and
Communications, 2012, pp. 908-913.
[2] K. Marina and R. Samir, “On-Demand Multipath Dis-
tance Vector Routing in Ad Hoc Networks,” Internation-
al Conference on Network Protocols, 2001, pp. 14-23.
[3] K. Marina and R. Samir, “Ad Hoc on-Demand Multipath
Distance Vector Routing,” Wireless Communications and
Mobile Computing, 2006, pp. 969-988.
http://dx.doi.org/10.1002/wcm.432
[4] E. Charles, M. Elizabeth, “Ad-Hoc on Demand Distance
Vector Routing,” The IEEE Workshop on Mobile Compu-
ting Systems and Applications, New Orleans, 1999, pp.
90-100.
[5] X. Li, S. Zhi and S. Xin, “Ad-Hoc Multipath Routing
Protocol Based on Load Balance and Location Informa-
tion,” Wireless Communications & Signal Processing
(WCSP), 2009, pp. 1-4.
[6] M. Tekaya, N. Tabbane and S. Tabbane, “Multipath
Routing Mechanism with Load Balancing in Ad Hoc
Network,” International Conference on Computer Engi-
neering and Systems (ICCES), 2010, pp. 67-72.
[7] S. Getsy, P. Neelavathy and D. Sridharan, “Energy Effi-
cient Ad Hoc On Demand Multipath Distance Vector
Routing Protocol,” International Journal of Recent Trends
in Engineering, 2009, pp. 10-12