Communications and Network, 2013, 5, 403-407
http://dx.doi.org/10.4236/cn.2013.53B2074 Published Online September 2013 (http://www.scirp.org/journal/cn)
Gray Re levance Algorithm B ased Routing Protocol in Ad
Hoc Network
Hong Tang, Pusheng He, Haolan Yang, Maosheng Zheng
Chongqing Key Lab of Mobile Communications Technology,
Chongqing University of Posts and Telecommunications, Chongqing, China
Received May 2013
ABSTRACT
The characteristics of nodes moving arbitrarily and the network topology changing frequently lead to AODV routing
protocol, which uses minimum hop-count as the metric for route selection, facing intermittent connectivity frequently
which would cause QoS of network degradation in Ad Hoc Netwo rk. In this paper, we integrate three cro ss layer infor-
mation which consists of the remaining energy of nodes, the remaining queue length and the hop-count from source
node to destination node. Then we present the GRA-AODV routing protocol based on the gray relevance algorithm. By
comparing the simulation and experimental results, in the case of slightly increase in routing overhead, the improved
Gray Relevance Algorithm-AODV routing possesses lower average end to end delay and lower packet loss rate, and it
has superior robustness in the mobile Ad Hoc Network with network topology changing frequently.
Keywords: RREQ; Gray Relevance; Routing Protocol; Ad Hoc Network
1. Introduction
Ad Hoc network is a special network which used the
exchanged information between nodes to achieve net-
work communication. Unlike trad itio nal network, there is
not any infrastructure in it and each node has the function
of routing and for warding [1]. Ad Ho c network has so me
distinctive characteristics: First, the self-organization net-
work provides the probability of cheap and rapid deploy-
ment of the network. Second, the feature of multi-hop
nodes and intermediate nodes have the function of for-
warding to reduce the tr ansmission range of each termin -
al without reducing the scope of the network coverage,
which would reduce the power consumption of the mo-
bile terminal. It does benefit the health of users while
providing the design basis for the miniaturization and
low-power of mobile terminal. The Ad Hoc network, be-
cause of self-organizing characteristic, has strong robust-
ness and survivability, which would meet various specif -
ic applications. The main application scenarios include:
military applications, disaster relief, remote areas or tem-
porary communications, sensor networks, etc.
The Ad Hoc network has a wide range of applications,
but due to the particularity of position change frequently
of each node in the network, the network topology and
the routing protocol change frequently. So it is importan t
to study routing protocol in the Ad Hoc network.
2. Related Works
At present, some traditional routing protocols use mini-
mum h op-count as the metric for route selectio n, such as
the AODV routing protocol [2] and DSR routing proto-
col [3], etc. The criterion implementation is simple, we
can use Dijkstra algorithm to quickly find the shortest
routing path from the source node to the destination node
when knowing the network topology. However, some stu-
dies have shown that these routing protocol which use
minimu m hop -count as the metric for route selection can’t
guarantee QoS of Ad Hoc network in most cases, since
some relevant factors, such as the status information of
the node itself and the quality information of the link sta-
tus, are not taken into account. Even if the hop-count be-
tween source node and destination node meet the mini-
mum hop-count metric, the quality of link may become
unsatisfactory because of the energy of nodes, the inter-
ference conflict and other factors, which would make QoS
of Ad Hoc network be affected severely. In order to solve
this problem of QoS of Ad Hoc network which is se-
verely affected by the energy of nodes and the quality of
link, the researchers hope to combine the information
which consists of the status information of node itself
and the quality information of link to design new routing
metric.
In recent years, many researchers took in-depth study
on these routing protocols which use minimum hop-

H. TANG ET AL.
Copyright © 2013 SciRe s. CN
404
count as the metric for route selection, and to improve
and optimize these. For example: Reference [4] proposed
a MAODV-BER (Modified AODV-BER) routing proto-
col, comparing with the traditional AODV routing pro-
tocol, the routing protocol added the BER factor of link
into the routing metric; Reference [5] proposed a TAODV
(Turbo-AODV) routing protocol, the routing protocol
designed a new routing metric: RREQweight = α*RSSI +
β*RE + γ*RQL, here the RSSI represents the percentage
of received signal strength, the RE represents the percen-
tage of remai ning ene rgy of nodes, the RQL represen ts t h e
percentage of remaining queue length of nodes, α, β, γ
respectively represent the corresponding weight; Refer-
ence [6] proposed a QBDSR (Quality of Service Based
DSR) routing protocol, comparing with the traditional
DSR routing protocol, the routing protocol added the fac-
tor of bandwidth obtained between two nodes into routing
metric.
3. GRA-AODV Routing Protocol
This paper proposed GRA-AODV routing protocol based
on the traditional AODV protocol, collected cross-layer
information into the RREQ packet header, and then se-
lected the routing using the gray relevance algorithm.
3.1. The Principle of Grey Relevance Algorithm
Grey system theo ry was propo sed by Prof essor Deng J in
the 1980s, the gray relevance algorithm is one of the im-
portant theories [7]. We use the gray correlation algorithm
to quantitatively analyze and compare various message
impact factors which are carried in the RREQ messages
received by the destination node, and establish the con-
nection between message impact factors by using the level
of similarity and variability, then we selected a RREQ
message with the highest grey relevance degree. Grey re-
levance algorithm main steps are as follows:
1) Select evaluation message impact factors:
We select remaining energy of nodes, received signal
strength, available bandwidth, remaining queue length of
nodes which can reflect the congestion status of link,
hop-count and other information as evaluation message
impact factors.
2) Determine the candidate list of RREQ message and
form a sequence:
Assuming in the route establishment process, the des-
tination node receives multiple RREQ message sent by
source node. The sequence composed by multiple RREQ
message is:
[ ]
12 1
, ,...,,
mm
X xxx x
−
=
.
3) Obtain factors from RREQ message and form factor
set sequence:
In the above m RREQ messages, each RREQ message
includes n message impact factors; these factors can be
some or all of step (1). Thus the factor sequence com-
posed by n message impact factors is:
[ ]
(1),(2),...,(1),(), i=1,2,3,...,m
ii ii
X xxxnxn= −
Then
the matrix composed by n message impact factors in the
m RREQ messages as show in Equation (1):
11 121311 1
21 222321 2
1231
,,, ... ,,
,,, ...,,.
...................................
,, ,...,,
nn
nn
m mmmnmn
xxxx x
xxxx x
X
xxxxx
−
−
−




=



(1)
4) Dimensionless the factor sequence to form a scalar
sequence:
If the impact factor is cost type, we hope the smaller
cost the better, for the cost type impact factor, the scalar
sequence as show in Equation (2):
max ()()
() , k=1,2,3,...,n.
max( )min( )
ii
k
iii
k
k
xk xk
Zk xk xk
−
=−
(2)
If the impact factor is benefit type, we hope the bigger
benefit the better, for the benefit type impact factor, the
scalar sequence as show in Equation (3):
() min()
() , k=1,2,3,...,n
max( )min( )
ii
k
iii
k
k
xk xk
Zk xk xk
−
=−
(3)
5) Determine the reference set sequence:
We use
max( )
i
i
xj
to represent the maximum number
of row i and column j in the m × n scalar sequence, use
to represent the minimum number of row i and
column j in the m × n scalar sequence. So the optimal
reference set sequence is:
max
max (1),max (2),...,max ()
ii i
ii i
Xx xxj

=

.
The worst reference set sequence is:
min
min (1),min (2),...,min ()
ii i
ii i
Xx xxj

=
.
6) Calculate the grey relevance coefficient:
We use
γ
+
to represent the optimal grey relevance
coefficient, use
γ
−
to represent the worst grey relevance
coefficient. The optimal grey relevance coefficient as
shown in Equation (4):
max max
max max
min min() max max
() .
() max max
ii i
ik ik
iii i
ik
Xk k kXk k
kXk k kXk k
+
| ()−Ζ()|+ρ| ()−Ζ()|
γ=|()−Ζ()|+ρ|()−Ζ()|
(4)
min( )
i
i
xj

H. TANG ET AL.
405
The worst grey relevance coefficient as show in Equa- tion(5):
min min
min min
min min() max max
() .
() max max
i ii
ik ik
ii ii
ik
kXkkkXk
kkXkkkXk
−|Ζ()− ()|+ρ|Ζ()− ()|
γ=|Ζ()−()|+ρ|Ζ()−()|
(5)
Here,
ρ
is the distinguishing coefficient and its gen-
eral value is 0.5.
7) Calculate the grey relevance degree:
We use
+
η
to represent the optimal grey relevance
degree, use
−
η
to represent the worst grey relevance
degree. Generally grey relevance degree is to take the
mean of grey relevance coefficient, but here we take into
account the actual impact of each factor of the selected
route is not the same degree of influence, so we use
weighting to calculate grey relevance degree. The o ptim-
al grey relevance degree as shown in Equation (6):
1( ).
n
i ki
k
k
++
=
η =ργ
∑
(6)
The worst grey relevance degree as show in Equation
(7):
1( ).
n
i ki
k
k
−−
=
η =ργ
∑
(7)
Here,
ρ
is the weight of each impact factor, and
.
8) Calculate the grey relevance degree of each RREQ
message and select a RREQ message with the highest
grey relevance degree:
We use
ξ
to represent the grey relevance degree of
each RREQ message, the grey relevance degree as show
in Equati o n ( 8):
2
22
).
))
+
+−
(η
ξ=(η+ (η
(8)
3.2. The Implementation of GRA-AODV
Routing Protocol
Comparing with the traditional AODV protocol, the GRA-
AODV routing protocol has been improved mainly in the
routing building phase the route maintenance phase is the
same with the traditional AODV routing protocol. The
main step of routing building phase of GRA-AODV
routin g protocol as f ol lows:
1) Studies have shown that synthesizing the informa-
tion of physical layer, data link layer and routing layer to
design routing protocol can greatly improve QoS of net-
work [8]. So we add the information which consists of
the remaining energy of node and the remaining queue
length of nodes into the RREQ packet header, and use th e
hop count which is carried on the RREQ packet header as
the information of routing layer.
2) Due to the performance of whole link depends on
the worst state node in the link, we collect the minimum
remaining energy and the m inim um remaining queue length
of nodes to reflect the information of whole link.
3) When the source nodes want to send data to the
destination node, the source nodes check whether its own
routing table has the path to the destination node at first.
If there is a path to destination node, then send data pack-
ets by this path; if there is not a path to the destination
node, then broadcasts RREQ route request message to its
neighbor node to launch a route discovery process.
4) When the intermediate node received a RREQ route
request message, we should first check the destination
node address of RREQ packet header. If the destination
node is itself, then follow the step (5) to handle. If the
destination node is not itself , we compare the destination
sequence number, the remaining energy and the remain-
ing queue length in its own route table to those of RREQ
packet header, updating the destination sequence number
in the RREQ packet header as the maximum one, and
updating the remaining energy and the remaining queue
length of node in the RREQ packet header as the mini-
mum one, and the hop-count plus one. The difference
with the traditional AODV routing protocol is that we
don’t use the path to the destination which may be caught
in the route table of intermediate node, which aim to en-
sure that the RREQ message received by target node can
more accurately reflect the information of the whole link.
5) When the destination node received the first RREQ
message, then we start a timer, this is done to receive
more RREQ message so that we can make use of gray
relevance algorithm to choose the best one. When the
timer expired, we extract the information which consist
of the remaining energy, the remaining queue length and
the hop-count from the RREQ packet header as the im-
pact factors, we take the remaining energy of node and
the remaining queue length of nodes as benefit type to
handle, and take the hop-count as cost type to handle,
then we calculate the gr ey relevance degree of each RREQ
message.
6) The destination node only to send the RREP mes-
sage to source node according to the RREQ message with
the maximum grey relevance degree. Finally the source
node sends da te to the de s t inati on by this path.
4. Simulation
In this paper, we take average end to end delay, packet
1
1
n
k
k=
ρ=
∑

H. TANG ET AL.
Copyright © 2013 SciRe s. CN
406
loss rate and routing overhead three index to compare the
performance of GRA-AODV routing protocol with
AODV routing protocol.
4.1. The Set of Simulation Parameters
This simulation used two scenarios, one is the scene of
60 nodes with different maximum speed, and the other
one is the scene of nodes fixed maximum movement speed
for 10 m / s unde r di ff erent node numbe r .
4.2. Analysis of Simulation Results
The Figures 1-4 show that the improved GRA-AODV
routing possesses lower average end to end delay and
lower packet loss rate than AODV routing protocol, this
is because the GRA-AODV routing protocol takes the
remaining energy of node and the remaining queue
length of node accoun t into the ro uting bu ildin g pha se, so
that the path possesses better link quality and superior
robustness than AODV routing protocol, which can ef-
fectively avoid congestion path and reduce the number of
link failure.
Table 1. Simulation Parameters.
Parameter Value
Network Simulation Platform Ns-2.28 + Cygwin
Size of the network 1000 m × 1000 m
Type of packet CBR
Size of packet 512 bytes
Mac 802.11
Time of simulation 1000 seconds
Pause Time 0.0 seconds
Number of seed 1.0
Contract rate 10 packets/s
Number of nodes 20, 40, 60, 80, 100
Maximum speed (m/ s ) 1, 5, 10, 15, 20
Figure 1. Average end-to-end delay vs. Number of nodes.
Figure 2. Average end-to-end delay vs. maximum speed.
Figure 3. Packet loss rate vs. number of node s .
Figure 4. Packet loss rate vs. maximum speed.
The Figures 5 and 6 show that the routing overhead
simulation results comparison diagram in GRA-AODV
routing protocol and AODV routing protocol two scenes,
we can find that the improved GRA-AODV routing pro-
tocol routing overhead has slightly increased comparing

H. TANG ET AL.
407
Figure 5. Routing overhead vs. number of nodes.
Figure 6. Routing overhead vs. maximum speed.
with AODV routing protocol. This is because we don’t
use the path to the destination which may be caught in
the route table of intermediate node, which aims to en-
sur e that the RREQ message received by target node can
more accurately reflect the information of the whole link,
we still continue to broadcast RREQ messages until the
destination node. Although the establishment of the route
has better robustness, and can effectively avoid conges-
tion path and reduce the number of link failure, the im-
proved GRA-AODV routing protocol routing overhead
has slightly increased comparing with the AODV routing
protocol.
5. Conclusion
The characteristics of nodes moving arbitrarily and the
network topology changing frequently cause QoS of net-
works degradation and bring great difficulties to design
routing protocol in Ad Hoc Networks. The traditional
AODV routing protocol does not take node itself and the
quality information of the link status account into the
routing building phase, to this point, in this paper we add
the remaining energy of node and the remaining queue
length of node into the RREQ packet header to propose
the GRA-AODV routing protocol based on the gray re-
levance algorithm. By comparing the simulation and ex-
peri menta l resul ts, in the ca se of slig htl y increa se in routing
overhead, the improved Gray Re levance Algorithm-AODV
routing possesses lower average end to end delay and
lower packet loss rate, thus verifying the effectiveness of
GRA-AODV rout i ng protoc ol.
6. Acknowledgements
This work was supported by National Science & Tech-
nology Major Program (2012ZX03004009), the special
fund of Chon gqing ke y laborator y (CSTC), the project of
CSTC(CSTC2012jjA40044) and the project of Chongq-
ing education committee (Kjzh11206).
REFERENCES
[1] J. Wang, D. Man, L. Wu, et al. “Study of QoS in Cross
Layer Based Ad Hoc Networks,” IEEE 4th International
Conference on Wireless Communications, Networking
and Mobile Computing, WiCOM’08, 2008, pp. 1-4.
[2] C. E. Perkins, E. M. Royer, “Ad-hoc on-Demand Dis-
tance Vector Routing,” Proceedings of Second IEEE
Workshop on Mobile Computing Systems and Applica-
tions, WMCSA’99, 1999, pp. 90-100.
[3] D. B. Johnson, D. A. Ma ltz and J. Broch “DSR: The Dy-
namic Source Routing Protocol for Multi-Hop Wireless
ad Hoc Networks,” Ad Hoc Networking, Vol. 5, 2001, pp.
139-172.
[4] R. S. Dahal and T. Sanguankotchakorn, “QoS Routing in
MANET through Cross-Layer Design with BER and
Modifying AODV,” IEEE Second Asian Himalayas In-
ternational Conference on Internet (AH-ICI), 2011, pp.
1-4.
[5] Z. El-Bazzal, K. El-Ahmadieh, Z. Merhi, et al., “A Cross
Layered Routing Protocol for Ad Hoc Networks,” IEEE
International Conference on Information Technology and
E-Services (ICITeS), 2012, pp. 1-6.
[6] M. Feham, B. Kadri and D. Moussaoui, “A Cross-Layer
Design for QoS Implementation in MANETs Applied to
DSR,” 2008.
[7] H. Tang, S. Yao and Y. Zhang, “Study on the cross-layer
handover method based on grey relational analysis in Ad
hoc network,” 2011 IEEE Seventh International Confe-
rence on Natural Computation (ICNC), 2011, Vol. 4, pp.
2042-2045.
[8] J. Chen, Z. Li, J. Liu, et al., “QoS Multipath Routing
Protocol Based on Cross Layer Design for Ad hoc Net-
works,” 2011 IEEE International Conference on Internet
Computing & Information Services (ICICIS), 2011, pp.
261-264.