# Quality-of-Service Routing Using Path and Power Aware Techniques in Mobile Ad Hoc Networks

Authors: R. Asokan; A. M. Natarajan; C. Venkatesh
Journal: Journal of Computer Systems, Networks, and Communications
 (2008)

---

## Abstract

Mobile ad hoc network (MANET) is a collection of wireless mobile hosts dynamically forming a temporary network without the aid of any existing established infrastructure. Quality of service (QoS) is a set of service requirements that needs to be met by the network while transporting a packet stream from a source to its destination. QoS support MANETs is a challenging task due to the dynamic topology and limited resources. The main objective of this paper is to enhance the QoS routing for MANET using temporally ordered routing algorithm (TORA) with self-healing and optimized routing techniques (SHORT). SHORT improves routing optimality by monitoring routing paths continuously and redirecting the path whenever a shortcut path is available. In this paper, the performance comparison of TORA and TORA with SHORT has been analyzed using network simulator for various parameters. TORA with SHORT enhances performance of TORA in terms of throughput, packet loss, end-to-end delay, and energy.


---

## Body

## 1. Introduction

In mobile ad hoc networks (MANETs), all nodes are connected
dynamically in an arbitrary manner.   All nodes behave as routers and take part
in discovery and maintenance of routes to other nodes in the network. Routing
protocols find a path to be followed by data packets from a source node to a
destination node. MANETs routing protocols can be classified into three major
categories based on routing information update mechanism. They are proactive or
table-driven routing protocols, reactive or on-demand routing protocols, and
hybrid routing protocols. Several routing protocols have been discussed in the
literature. In this paper, TORA, a reactive routing protocol, is taken for
analysis [1].TORA is designed to discover routes on demand, provide
multiple routes to a destination, establish routes quickly, and minimize
communication overhead by localizing algorithmic reaction to topological
changes. SHORT is a mechanism that optimizes the route length result in
significant performance gain over the underlying routing protocols. The proposed
schemes monitor the routing path and try to shorten the path length when
it is feasible. A shorter path not only reduces the latency but also enhances
the throughput [2].  The rest of the paper is organized as follows. In Section 2, the previous work related to QoS routing protocols is briefly reviewed. In
Section 3, self-healing and optimizing routing technique (SHORT) is described. The extension of SHORT for TORA is discussed in Section 4. In Section 5, the simulation results are shown. In Section 6, the result of
the work done is summarized.


## 2. Previous Work

QoS routing protocols search for routes
with sufficient resources in order to satisfy the QoS requirement of a flow.
QoS routing protocol should find the path that consumes minimum resources [3].
Some key design considerations in providing QoS routing support and review of
previous work addressing the issue of route selection subject to QoS
constraints are discussed in [4]. A framework of self-healing and optimizing
routing techniques for mobile ad hoc networks has been proposed in [5].SHORT techniques for both ad hoc on-demand
distance vector routing (AODV) and dynamic source routing (DSR) algorithm have been analyzed and evaluated in
the literature. Simulation results show that higher-delivery rate and longer
network lifetime are achieved by adopting SHORT [5]. Flooding is a strategy
that supports QoS routing, which works by flooding a route searching message
across the entire network to search for a QoS route on demand. Intermediate
nodes forward nonduplicate route searching messages, that they receive,
provided that the given QoS requirements have not been violated yet. Once the
intended destination receives a route searching message, a QoS route is
discovered. This strategy is used to acquire constrained paths in time-slotted
ad hoc networks [6]. AODV-backup routing has some similarity to SHORT in
the sense that it lets neighboring nodes around a route be aware of the route.
Each neighboring node computes an alternative short route for a nearby link on
the route and when the link breaks, relevant neighboring node will salvage the
route and help to deliver the affected packets to the destination [7]. With geographic
positioning system (GPS) support, a novel link cost function is proposed in
[8]. The cost function serves as a localized power aware routing, which includes
not only the necessary transmission energy but also the distance between the
transmitting node and the final destination node.TORA-based QoS routing protocol for
MANETs called INORA (INSIGNIA + TORA) is presented in [9]. INORA is a network
layer QoS support mechanism that makes use of the INSIGNIA in-band signaling
mechanism and TORA routing protocol for MANETs. In INORA, QoS signaling is used
to reserve and release resources and setup, tear down, and renegotiate flows in
the network. QoS-TORA proposed in [10] designed to work in a TDMA network where
the bandwidth of a link is measured in terms of slot reservations in the data
phase of the TDMA frame. A framework of self-healing technique for TORA is
proposed in this paper.


## 3. Self-Healing and Optimizing Routing Technique (Short)

Two broad classes of SHORT are proposed: path aware (PA)-SHORT
and energy aware (EA)-SHORT. PA-SHORT is concerned with optimizing and healing
paths to reduce the number of hops, whereas the the EA-SHORT is to conserve
power in MANETs.


### 3.1. Path Aware (PA)-SHORT

The basic scenario of the shortcut discovery process is
shown in Figure1. The hop-count (HC) field is initialized to zero at the source node and gets
incremented by one at every hop the packet takes. This
information is maintained as an array termed as the hop comparison array. Each of the elements of the array has an
expiration time after which they are invalidated [5]. Consider a routing path from a source node A to a
destination node D as shown in Figure 1(a). This initial path is determined
through the path discovery process, and the packet takes four hops while
getting routed from S to D. Mobility of the nodes may make the shape of the
routing path similar to the one shown in Figure 1(b) while retaining the
connectivity. In this new shape, C is in the transmission range of A. The current routing path is shown by the solid
lines in the figure. The example is analyzed in steps where a step defines the
events during the broadcast of a packet at a node. The entry of the hop
comparison array at the end of each step at each of the node is shown in Table 1.Table 1
The entry of the hop comparison array.
SABCDShortcut(i)(0, S)(0, S)————(ii)(0, S)(0, S)(1, A)(1, A)——(iii)(0, S)(0, S)(1, A)(2, B)——(iv)(0, S)(3, C)(1, A)(2, B)(3, C)Found at A(v)(0, S)(0, S)—(1, A)(2, C)—Hop (2, 1) shortcut path formations.
(a)(b)(c)(i)
S needs
to forward a packet to A. An entry is initialized in A’s hop comparison array (S,
D, 0, S). It broadcasts the packet while marking HC as 0. Node A is in the
transmission range of S and receives the broadcast. So it records (S, D, 0, S)
in its hop comparison array.(ii)
Node A broadcasts the packet with a HC of 1 destined for D.
Nodes B and C also receive the packet as they are in the transmission range. B
and C record (S, D, 1, A) in their hop comparison array.(iii)
Node B broadcasts the packet with a HC of 2. Nodes A and C
have an entry corresponding to (S, D). Since the difference in HCs not more
than 2, nothing is updated.(iv)
While forwarding the packet to D, C broadcasts the packets
with a HC of 3. Nodes A, B, and D are in the transmission range. Node to D
consumes the packet as it is the destination node. B compares the HC with its
stored entry. As the difference in HC is not more than 2, nothing is updated at
B. At A, the HC difference is 3. So, node A then updates its own routing table
to point to C as the next hop node for destination D.(v)
The corresponding entry of the
hop comparison array at S, A, and C is deleted. Thus, path A-B-C is shortened
to A-C. The final path is shown in Figure1(c).
This shortcut path
formation is termed as (2, 1) reduction.


### 3.2. Energy Aware (EA)-SHORT

Energy aware (EA)-SHORT extends node and network lifetime by
routing packets through nodes that have sufficient remaining power and avoiding
nodes that are low on battery supply. To achieve routing fairness, routing
protocols use self-healing mechanism so that it can drag itself out of the situations
in which certain nodes are being over-used while other nodes are idle.Energy aware (EA)-SHORT will
fairly distribute the traffic load among all the participating nodes in the
network [5]. Consider a part of an MANET shown in Figure 2(a), the path S-X-Y-D
is the optimal path for a connection from source S to destination D. Nodes X
and Y will continuously be used in forwarding the traffic, leaving the other
nodes free from the traffic load. Nodes X and Y will eventually be drained out
of battery supply and die early. However, an energy-aware routing scheme will
try to divert the traffic to other nodes. As the data
packets are successively forwarded by the two nodes (X and Y), node U overhears
the same packet and finds out the energy difference at node X and at itself with help of overhear
table. If it is significant enough, node U will do the redirection. Similarly,
the energy level difference between Y and V is significant enough, and then the
node V will do the redirection. With successive local
redirection operations, the route will gradually converge to an alternative
node disjoint path S-U-V-W-D as shown in Figures 2(b) and 2(c). An overhear
table is maintained at each node.Successive local route redirection operations.
(a)
Initial path that drains the residual energy at nodes X and Y(b)
After route redirection, node X is eliminated(c)
After route redirection, node Y also eliminated


## 3.1. Path Aware (PA)-SHORT

The basic scenario of the shortcut discovery process is
shown in Figure1. The hop-count (HC) field is initialized to zero at the source node and gets
incremented by one at every hop the packet takes. This
information is maintained as an array termed as the hop comparison array. Each of the elements of the array has an
expiration time after which they are invalidated [5]. Consider a routing path from a source node A to a
destination node D as shown in Figure 1(a). This initial path is determined
through the path discovery process, and the packet takes four hops while
getting routed from S to D. Mobility of the nodes may make the shape of the
routing path similar to the one shown in Figure 1(b) while retaining the
connectivity. In this new shape, C is in the transmission range of A. The current routing path is shown by the solid
lines in the figure. The example is analyzed in steps where a step defines the
events during the broadcast of a packet at a node. The entry of the hop
comparison array at the end of each step at each of the node is shown in Table 1.Table 1
The entry of the hop comparison array.
SABCDShortcut(i)(0, S)(0, S)————(ii)(0, S)(0, S)(1, A)(1, A)——(iii)(0, S)(0, S)(1, A)(2, B)——(iv)(0, S)(3, C)(1, A)(2, B)(3, C)Found at A(v)(0, S)(0, S)—(1, A)(2, C)—Hop (2, 1) shortcut path formations.
(a)(b)(c)(i)
S needs
to forward a packet to A. An entry is initialized in A’s hop comparison array (S,
D, 0, S). It broadcasts the packet while marking HC as 0. Node A is in the
transmission range of S and receives the broadcast. So it records (S, D, 0, S)
in its hop comparison array.(ii)
Node A broadcasts the packet with a HC of 1 destined for D.
Nodes B and C also receive the packet as they are in the transmission range. B
and C record (S, D, 1, A) in their hop comparison array.(iii)
Node B broadcasts the packet with a HC of 2. Nodes A and C
have an entry corresponding to (S, D). Since the difference in HCs not more
than 2, nothing is updated.(iv)
While forwarding the packet to D, C broadcasts the packets
with a HC of 3. Nodes A, B, and D are in the transmission range. Node to D
consumes the packet as it is the destination node. B compares the HC with its
stored entry. As the difference in HC is not more than 2, nothing is updated at
B. At A, the HC difference is 3. So, node A then updates its own routing table
to point to C as the next hop node for destination D.(v)
The corresponding entry of the
hop comparison array at S, A, and C is deleted. Thus, path A-B-C is shortened
to A-C. The final path is shown in Figure1(c).
This shortcut path
formation is termed as (2, 1) reduction.


## 3.2. Energy Aware (EA)-SHORT

Energy aware (EA)-SHORT extends node and network lifetime by
routing packets through nodes that have sufficient remaining power and avoiding
nodes that are low on battery supply. To achieve routing fairness, routing
protocols use self-healing mechanism so that it can drag itself out of the situations
in which certain nodes are being over-used while other nodes are idle.Energy aware (EA)-SHORT will
fairly distribute the traffic load among all the participating nodes in the
network [5]. Consider a part of an MANET shown in Figure 2(a), the path S-X-Y-D
is the optimal path for a connection from source S to destination D. Nodes X
and Y will continuously be used in forwarding the traffic, leaving the other
nodes free from the traffic load. Nodes X and Y will eventually be drained out
of battery supply and die early. However, an energy-aware routing scheme will
try to divert the traffic to other nodes. As the data
packets are successively forwarded by the two nodes (X and Y), node U overhears
the same packet and finds out the energy difference at node X and at itself with help of overhear
table. If it is significant enough, node U will do the redirection. Similarly,
the energy level difference between Y and V is significant enough, and then the
node V will do the redirection. With successive local
redirection operations, the route will gradually converge to an alternative
node disjoint path S-U-V-W-D as shown in Figures 2(b) and 2(c). An overhear
table is maintained at each node.Successive local route redirection operations.
(a)
Initial path that drains the residual energy at nodes X and Y(b)
After route redirection, node X is eliminated(c)
After route redirection, node Y also eliminated


## 4. Self-Healing Optimization Routing Technique for TORA

SHORT is a general
technique that should work with any mobile ad hoc routing protocol. TORA is a source-initiated on-demand
routing protocol which uses a link reversal algorithm [11]. Path
length and power aware techniques are incorporated into TORA protocol. SHORT
improves routing optimality by gradually shortening the routes whenever
possible. When shortcut occurs and is estimated to be stable, it will be
utilized to shorten the route. It should be noted that the SHORT algorithm does not react to every little
change in the topology or transient conditions. Let us consider the network
topology shown in Figure 3. When node 1 has data packets to be sent to the
destination node 7, a query packet is originated by node 1 with the destination
address included in it.Figure 3
Illustration of temporal ordering in TORA.This query packet is forwarded by
intermediate nodes 2, 3, 4, 5, 6 and reaches the destination node 7. The node
that terminates the query packet replies with an update packet containing its
distance from the destination. The destination node 7 originates an update
packet. Each node that receives the update packet sets its distance to a value
higher than the distance of the sender of the update packet. By doing this, a
set of directed links from the node which originated the query to the
destination node 7 is created. This forms the directed acyclic graph (DAG) depicted in Figure3. When an intermediate
node discovers that the route to the destination node is invalid, as
illustrated in Figure 4, it changes its distance value to a higher value than
its neighbors and originates an update packet.Illustration of route maintenance in TORA.
(a)(b)The neighboring node 4 that receives the
update packet reverses the link between 1 and 4 and forwards the update packet.
This is done to update the DAG corresponding to destination node 7. This
results in a change in the DAG. In TORA-SHORT, both the hop comparison
array and overhear table are maintained in each node. The format of each entry
in the array is 〈SA, DA, HC, NA〉, where NA is the neighbors address from
which the packet was broadcasted. Each
entry overhear table contains the following three fields source-destination
pairs, sequence number and overhear list. Each entry represents a traffic flow
in the network, identified by the source-destination pair field. Each new entry
has three fields as hop counter, residual energy level, and the sender. The
residual energy field records the residual energy level of transmitting node of
the packets.


## 5. Performance Evaluation

The performance of the proposed protocol TORA-SHORT is
evaluated using the nanoseconds-2 simulator [12]. QoS
parameters like delay,
throughput, packet loss, and control
overhead are analyzed. Table 2 lists the simulation parameters and
environments used.Table 2
Simulation parameters.
ParameterValueSimulation
area500m×500mNode communication range250 mRouting protocolTORA, TORA-SHORTMedium access mechanismIEEE
802.11bTraffic source modelConstant bit rateBandwidth2 MbpsPacket size1024 BytesMobility model and speedRandom waypoint, 20–100 m/s


### 5.1. Throughput

The effects
of mobility and pause time on throughput for the protocols TORA and TORA-SHORT are
shown in Figures5 and 6. During high mobility, both
protocols show small degradation in throughput
due to high-link breakage. TORA-SHORT shows around 3% improvement in
throughput over TORA. The higher the pause time is, the longer each
node remains stable before the next movement. Throughput increases with the increase in pause time, due to
less number of link breaks. The performance improvement over TORA is around 50%
when the pause time varies from 10 to 30 seconds. This is because SHORT will
gradually heal and rectify if there is a shortcut path, thus resulting in
better throughput.Figure 5
Effect of mobility on throughput.Figure 6
Effect of pause time on throughput.


### 5.2. End-to-End Delay

Figure7 shows the effect of number of nodes on
end-to-end delay. When the number of active mobile nodes in a network
increases, the delay increases. This is due to the increase in traffic in
network.Figure 7
Effect of number of nodes on delay.Delay
of TORA-SHORT is less than TORA. Here, the reduction in delay is about 50%.
When the number of packets increases, the delay also increases in both
cases. Figure8  shows the effect packets on end-to-end delay. This is also due to the increase in traffic in network. Delay of
TORA-SHORT is less than TORA. Here, the reduction in delay is about 50%. This
is due to the fact
that SHORT improves routing optimality by gradually shortening the routes
whenever possible.Figure 8
Effect of number of packets on delay.


### 5.3. Packet Loss

Figure9 depicts the effect of mobility on packet loss. When the
speed of the node increases, the packet loss also increases. Here, the node
speed is varied from 20 m/s to 100 m/s. In TORA, there is a nonlinear variation
in the packet loss. This is due to sudden changes in the number of link
breaks. A linear decrease in the packet
loss for both the cases from 20 m/s to 40 m/s mobile speed. In TORA-SHORT,
there is a slight increase in packet loss in the 40 m/s to 100 m/s. The reduction in packet loss varies from 17 to 73%. The packets in
TORA-SHORT follow a shortest path and also eliminate node which is low in energy level. Figure 10 depicts effect of number of nodes on packet loss. It is observed that when
the number of the nodes increases the packet loss also increases. The reduction
in packet loss varies from 12 to 57%. The result shows a low-dropped packet loss for
TORA-SHORT than the conventional one due to the fact that the packets follow a
shortest path, and also the probability of a link to get break is reduced.Figure 9
Effect of mobility on packet loss.Figure 10
Effect of number of nodes on packet loss.


### 5.4. Routing Overhead and Average Energy

When the
number of active mobile nodes in a network increases, the routing overhead
increases. This is due to the increasing number of routing packets between the
ad hoc nodes. Figure11 depicts the effect of nodes on routing overhead. TORA-SHORT has high-routing overhead compared to TORA.Figure 11
Effect of nodes on routing overhead.TORA-SHORT uses a very small amount
of memory space to maintain the hop comparison array for every shortcut
formation, only one extra message is necessary to inform one of the neighboring
nodes to update its routing table. TORA-SHORT routing overhead also includes
shortcut informing messages as well. Figure12 shows the average energy with respect to number of nodes. When the number of active
mobile nodes in a network increases, the average energy increases in both
protocols. EA-SHORT will fairly
distribute the traffic load among all the participating nodes in the network.
Average energy of TORA-SHORT is more than TORA. The improvement in average
energy over TORA is about 43%.Figure 12
Effect of nodes on average energy.


## 5.1. Throughput

The effects
of mobility and pause time on throughput for the protocols TORA and TORA-SHORT are
shown in Figures5 and 6. During high mobility, both
protocols show small degradation in throughput
due to high-link breakage. TORA-SHORT shows around 3% improvement in
throughput over TORA. The higher the pause time is, the longer each
node remains stable before the next movement. Throughput increases with the increase in pause time, due to
less number of link breaks. The performance improvement over TORA is around 50%
when the pause time varies from 10 to 30 seconds. This is because SHORT will
gradually heal and rectify if there is a shortcut path, thus resulting in
better throughput.Figure 5
Effect of mobility on throughput.Figure 6
Effect of pause time on throughput.


## 5.2. End-to-End Delay

Figure7 shows the effect of number of nodes on
end-to-end delay. When the number of active mobile nodes in a network
increases, the delay increases. This is due to the increase in traffic in
network.Figure 7
Effect of number of nodes on delay.Delay
of TORA-SHORT is less than TORA. Here, the reduction in delay is about 50%.
When the number of packets increases, the delay also increases in both
cases. Figure8  shows the effect packets on end-to-end delay. This is also due to the increase in traffic in network. Delay of
TORA-SHORT is less than TORA. Here, the reduction in delay is about 50%. This
is due to the fact
that SHORT improves routing optimality by gradually shortening the routes
whenever possible.Figure 8
Effect of number of packets on delay.


## 5.3. Packet Loss

Figure9 depicts the effect of mobility on packet loss. When the
speed of the node increases, the packet loss also increases. Here, the node
speed is varied from 20 m/s to 100 m/s. In TORA, there is a nonlinear variation
in the packet loss. This is due to sudden changes in the number of link
breaks. A linear decrease in the packet
loss for both the cases from 20 m/s to 40 m/s mobile speed. In TORA-SHORT,
there is a slight increase in packet loss in the 40 m/s to 100 m/s. The reduction in packet loss varies from 17 to 73%. The packets in
TORA-SHORT follow a shortest path and also eliminate node which is low in energy level. Figure 10 depicts effect of number of nodes on packet loss. It is observed that when
the number of the nodes increases the packet loss also increases. The reduction
in packet loss varies from 12 to 57%. The result shows a low-dropped packet loss for
TORA-SHORT than the conventional one due to the fact that the packets follow a
shortest path, and also the probability of a link to get break is reduced.Figure 9
Effect of mobility on packet loss.Figure 10
Effect of number of nodes on packet loss.


## 5.4. Routing Overhead and Average Energy

When the
number of active mobile nodes in a network increases, the routing overhead
increases. This is due to the increasing number of routing packets between the
ad hoc nodes. Figure11 depicts the effect of nodes on routing overhead. TORA-SHORT has high-routing overhead compared to TORA.Figure 11
Effect of nodes on routing overhead.TORA-SHORT uses a very small amount
of memory space to maintain the hop comparison array for every shortcut
formation, only one extra message is necessary to inform one of the neighboring
nodes to update its routing table. TORA-SHORT routing overhead also includes
shortcut informing messages as well. Figure12 shows the average energy with respect to number of nodes. When the number of active
mobile nodes in a network increases, the average energy increases in both
protocols. EA-SHORT will fairly
distribute the traffic load among all the participating nodes in the network.
Average energy of TORA-SHORT is more than TORA. The improvement in average
energy over TORA is about 43%.Figure 12
Effect of nodes on average energy.


## 6. Conclusion

The performance comparison of TORA and
TORA with SHORT has been analyzed in this paper using network simulator-2. The
performance of TORA is improved by using self-healing technique which optimizes
path length and power. SHORT can be used to improve routing optimality by
monitoring routing paths continuously and gradually redirecting the path
whenever a shortcut path is available. Path length and power aware techniques
are incorporated into TORA protocol. SHORT improves routing optimality by gradually
shortening the routes whenever possible. When shortcut occurs and is estimated
to be stable, it will be utilized to shorten the route. Simulation results show
that higher throughput, lower end-to-end delay, lower delay, and higher network
life time are achieved. In the simulation study, it has been found that
TORA-SHORT outperforms the TORA protocol in terms of throughput, end-to-end
delay, packet loss, and network life time. In future, this can be extended to
other QoS routing metrics.



---

*Source: 160574-2008-04-06.xml*