16-09-2016, 12:22 PM
[attachment=71103]
abstract
Anycast is an important way of communication for Mobile Ad hoc Networks (MANETs) in
terms of resources, robustness and efficiency for replicated service applications. Most of
the anycast routing protocols select unstable and congested intermediate nodes, thereby
causing frequent path failures and packet losses. We propose a mobility and quality of
service aware anycast routing scheme in MANETs (MQAR) that employs three models:
(1) node movement stability, (2) channel congestion, and (3) link/route expiry time.
These models coupled with Dynamic Source Routing (DSR) protocol are used in the route
discovery process to select nearest k-servers. A server among k-servers is selected based on
less congestion, route expiry time, number of hops, and better stability. The simulation
results indicate that proposed MQAR demonstrates, reduction in control overheads, path
delays and improved packet delivery ratio compared to existing methods such as flooding,
DSR and load balanced service discovery.
Introduction
Mobile Ad hoc Networks (MANETs) consists of a set of wireless mobile nodes communicating to each other without any
centralized control or fixed network infrastructure and can be deployed quickly [1,2]. The potential applications include
emergency disaster relief, battlefield situations, mine site operations, and wireless classrooms or meeting rooms in which
participants wish to share information or to acquire data.
Anycast is an important way of communication for replicated service applications in terms of resources, robustness and
efficiency, when mobility and link disconnections are frequent. Anycast allows a source node to transmit packets to a single
destination node out of set of several destination nodes. The idea behind anycast is that a client wants to send packets to any
one of the nearest possible servers offering a particular service or application. The set of destination nodes is identified by
anycast address [3]. As compared to unicast and multicast, anycast is a new type of communication defined in IPv6 that provides
a service mainly in client server environment [4].
Constructing and maintaining anycast communication should be simple so as to keep minimum control overheads. It is a
common practice in most of the anycast routing protocols, where in packets are sent along the shortest path [5]. This is
because, fewer nodes involved in transmission may save the power, network bandwidth and collisions during the message
transmission.
One of the most important issue in MANETs is to find an efficient and reliable anycast route. The current research on
MANETs mainly focuses on ad-hoc routing protocols with minimum hop count, energy efficiency, low server load, and
low congestion, as the route selection criterion. Although there are many proposed routing protocols for MANETs, most of
them consider the shortest-path with minimum hop count as the route selection criterion. Even though hop metric is easy
to implement and reliable in dynamic environments, the queuing delay and the contention delay at the intermediate nodes
are not taken into account for route selection. Thus, a minimum hop path may sometimes incur a higher end-to-end delay
than some alternate paths. Moreover, routing protocols based on minimum number of hops some times cannot fairly distribute
the routing load among mobile hosts. An unbalanced distribution of traffic may lead to higher packet dropping rate
and faster battery power depletion on certain mobile nodes.
The objective of this paper is to design and analyze a stability and QoS based anycast routing scheme in MANET to
improve the performance and enhance the service availability through the method of evenly distributed traffic load. The
scheme uses Dynamic Source Routing (DSR) [6] as basic route finding protocol along with stability and QoS models. Our contributions
as compared to existing works are as follows. (1) Designing a mathematical model for selecting stable nodes (with
respect to position) based on node’s own stability, i.e., self stability, and neighbor nodes stability. (2) Designing a mathematical
model for selecting noncongested nodes based on channel load and node buffer occupancy. (3) Designing a mathematical
model for finding link expiry time between pair of nodes. (4) Design of route discovery process, which includes request phase
to find routes to anycast servers through forwarding intermediate nodes which satisfy stability, congestion criteria and also
meet the route expiry deadline; and reply phase to update routing cache and confirm the routes found in request phase, and
(5) designing route maintenance procedure to handle node and link failures.
The rest of the paper is organized as follows. Section 2 presents an overview of existing MANET anycast routing protocols,
Section 3 discusses the proposed work. Simulation and result analysis are presented in Section 4, and conclusions are given
in Section 5.
2. Related work
Related works done in the field of anycast routing are presented in this section. Anycast service discovery in MANETs usually
relies on network-layer message broadcasting, which leads to large traffic overhead for the scarce bandwidth of
MANETs. In Design and implementation of an anycast services discovery (DIASD) [7], traffic-control mechanism is used to
balance the load in anycast service discovery, and also supports k-anycast service. With k-anycast service, the fault tolerance
and service flexibility is improved. DIASD scheme is used for comparison with our scheme to overcome some of its drawbacks
as follows.
DIASD is basically a hierarchical routing protocol, where in prior to the construction of anycast tree, node clustering and
virtual backbone are required to organize the nodes in a MANET. Route computation is carried out at the cluster head nodes
only; the movement of the cluster nodes adversely affects the performance of the protocol. Also, the cluster node update
information could cause a significant amount of control overhead. Thus the main drawback of the tree based protocols is
that they are not robust enough to operate in highly mobile environments.
The work presented in [8] introduces anycast method and theory into challenged communication processes in
opportunistic network. In [9], IPv6 uses anycast concept and proposes a k-anycast communication model which can route
k-anycast service request messages to the nearest k-anycast tree node to provide the requested service, and can evenly distribute
across the k-anycast tree nodes.
In [10], authors consider the density of nodes through count of routes to the anycast group member as a routing metric. In
[11], a QoS anycast routing algorithm based on ant colony optimization is proposed, which regulates the pheromone on the
best path and adopts resetting method and candidate set strategy to avoid falling into local optimal path and expand searching
space of ant colony. In [12], Zone Routing Protocol (ZRP) and anycast addressing is presented assuming the destination as
a member of anycast address.
The work presented in [13] proposes an Adaptive Neuro-Fuzzy Inference System (ANFIS) based multiple QoS constrained
anycast routing by using a set of static and mobile agents. The work given in [14] provides load balancing and failover services
in a way that other IT organization teams can use without having to manage the underlying technology.
A Petri-net-based simulation model of a MANET is developed and studied in [15]. The model enables representation of
reliability aspects of wireless communication such as fading effects, interferences, presence of obstacles and weather conditions
in a general and rather easy way.
The work proposed in [16] is an adaptive congestion aware protocol that detects and reacts to congested nodes and congested
parts of the network by using implicit hybrid contact and resources congestion heuristic in delay tolerant networks. In
[17], a framework to evaluate network dependability and performability is presented.
In [18], various schemes to improve routing protocol performance by using mobility prediction is presented. To avoid
congestion in IP, a backup topology design method is used in [19]. This backup topology design method splits the traffic
on high load links to other links by considering network conditions, such as the traffic matrix or topology.
The work given in [20] explores an end-to-end threshold-based algorithm which enhances congestion control to address
link failure loss in MANET by using link failures, round trip time and retransmission time out estimation. The work presented
in [21] for Limiting Greedy Connections (LGC) uses an active congestion control mechanism for minimizing the degradation
in network performance caused by bandwidth greedy applications on a congested node. The work presented in [22] proposes an early congestion detection and adaptive routing which constructs a NHN (non-congested neighbors) list and finds a route
to a destination through NHN nodes.
The work given in [23] considers finding QoS anycast path from client (source) to any one of the server by using software
agents. Protocol uses integration of static and mobile agents for inferring the QoS path from a set of multiple paths by using
Fuzzy Inference System (FIS). The work given in [24] proposes a QoS-Oriented Distributed routing protocol (QOD) to enhance
the QoS support capability of hybrid networks. Taking advantage of fewer transmission hops and anycast transmission features
of the hybrid networks, QOD transforms the packet routing problem to a resource scheduling problem.
In [25], k-anycast members are selected from a set of servers by three different schemes. The three schemes discuss about
how to select k servers depending on the radius of flooding, by selecting at least k members and members less than k members.
The Adaptive On-demand Distance Vector (AODV) routing protocol extended to support anycast routing is presented in
[26]. Route request and route reply are used to identify anycast server. A node communicates simultaneously with only one
anycast member.
The work given in [27] describes the probability of connected route to anycast member as a function of dynamicity and
density of the network. Anycast routing scheme chooses the shortest path routing as well as considers node degree density of
hosts in the network through count of routes to the anycast group member.
There are some works on smart packet based routing, hybrid routing and DSR security enhancement which may be helpful
in anycast routing. The work in [28] presents a new infrastructure where smart data packets are used to guide through
best available route in the network and minimizes convergence time. The work given in [29] proposes a routing protocol that
divides the Spatial Wireless Ad Hoc networks (SWAH) into backbone and non-backbone networks to perform static routing
and dynamic routing, respectively. It provides load balancing adaptively by establishing and maintaining multiple nodedisjoint
routes. Authors in [30] present a security enhancement to DSR protocol against wormhole attacks in ad hoc
networks for multirate transmissions which relies on calculation of round trip time (RTT). It uses the processing and queuing
delays of each participating node in the calculation of RTTs between neighbors.
According to the literature survey, it has been observed that there is scope for improving anycast routing schemes in
MANETs in terms of control overheads, load balancing, stable routes, and QoS. Thus there is a need to develop a robust
and an efficient movement stability and QoS based congestion aware anycast routing scheme in MANET. We have designed
three major models in our approach to anycast routing discovery problem. (1) Stability model to identify stable nodes, (2)
congestion model to take QoS into consideration by checking congestion aware parameters like channel load, and buffer
occupancy, and (3) link expiry time model to make sure the link duration will fall within an acceptable range.
3. Proposed work
This section presents, background of DSR, node movement stability model, congestion model, link expiration time model,
route establishment, route discovery and maintenance.
3.1. Background of DSR
Dynamic source routing (DSR) is an on-demand reactive routing protocol designed to restrict the bandwidth consumed by
control packets, by eliminating the periodic table update messages required in the table driven proactive approach.
It uses source routing instead of relying on the routing table at each intermediate node. DSR is beaconless and hence does
not require periodic hello packet transmissions. Route construction phase establishes a route by flooding route request (RR)
packets in the network. An intermediate node, upon receiving a RR packet, checks the sequence number on the packet before
forwarding it. The packet is forwarded only if it is not duplicate RR. The sequence number on the packet is used to prevent
loop formation. RR packet updates itself with traversed nodes address, which will facilitate in path construction. The destination
node, on receiving a RR packet, responds by sending a route reply (RP) packet to the source by using traversed
addresses. Thus source will have the address to destination through intermediate nodes.
Even though DSR protocol performs well in static and low mobility environment, the performance degrades rapidly with
increasing mobility. To enhance the performance, we use modified DSR and call it as Mobility and QoS aware Anycast
Routing in Mobile ad hoc Networks (MQAR). Our protocol (MQAR) works better under dynamic and high mobility environment,
since we include stability model to identify more stable nodes, congestion model to check traffic on the channel
dynamically and link expiry model to check duration of the link, so that selected path will stay for longer duration in anycast
routing.
abstract
Anycast is an important way of communication for Mobile Ad hoc Networks (MANETs) in
terms of resources, robustness and efficiency for replicated service applications. Most of
the anycast routing protocols select unstable and congested intermediate nodes, thereby
causing frequent path failures and packet losses. We propose a mobility and quality of
service aware anycast routing scheme in MANETs (MQAR) that employs three models:
(1) node movement stability, (2) channel congestion, and (3) link/route expiry time.
These models coupled with Dynamic Source Routing (DSR) protocol are used in the route
discovery process to select nearest k-servers. A server among k-servers is selected based on
less congestion, route expiry time, number of hops, and better stability. The simulation
results indicate that proposed MQAR demonstrates, reduction in control overheads, path
delays and improved packet delivery ratio compared to existing methods such as flooding,
DSR and load balanced service discovery.
Introduction
Mobile Ad hoc Networks (MANETs) consists of a set of wireless mobile nodes communicating to each other without any
centralized control or fixed network infrastructure and can be deployed quickly [1,2]. The potential applications include
emergency disaster relief, battlefield situations, mine site operations, and wireless classrooms or meeting rooms in which
participants wish to share information or to acquire data.
Anycast is an important way of communication for replicated service applications in terms of resources, robustness and
efficiency, when mobility and link disconnections are frequent. Anycast allows a source node to transmit packets to a single
destination node out of set of several destination nodes. The idea behind anycast is that a client wants to send packets to any
one of the nearest possible servers offering a particular service or application. The set of destination nodes is identified by
anycast address [3]. As compared to unicast and multicast, anycast is a new type of communication defined in IPv6 that provides
a service mainly in client server environment [4].
Constructing and maintaining anycast communication should be simple so as to keep minimum control overheads. It is a
common practice in most of the anycast routing protocols, where in packets are sent along the shortest path [5]. This is
because, fewer nodes involved in transmission may save the power, network bandwidth and collisions during the message
transmission.
One of the most important issue in MANETs is to find an efficient and reliable anycast route. The current research on
MANETs mainly focuses on ad-hoc routing protocols with minimum hop count, energy efficiency, low server load, and
low congestion, as the route selection criterion. Although there are many proposed routing protocols for MANETs, most of
them consider the shortest-path with minimum hop count as the route selection criterion. Even though hop metric is easy
to implement and reliable in dynamic environments, the queuing delay and the contention delay at the intermediate nodes
are not taken into account for route selection. Thus, a minimum hop path may sometimes incur a higher end-to-end delay
than some alternate paths. Moreover, routing protocols based on minimum number of hops some times cannot fairly distribute
the routing load among mobile hosts. An unbalanced distribution of traffic may lead to higher packet dropping rate
and faster battery power depletion on certain mobile nodes.
The objective of this paper is to design and analyze a stability and QoS based anycast routing scheme in MANET to
improve the performance and enhance the service availability through the method of evenly distributed traffic load. The
scheme uses Dynamic Source Routing (DSR) [6] as basic route finding protocol along with stability and QoS models. Our contributions
as compared to existing works are as follows. (1) Designing a mathematical model for selecting stable nodes (with
respect to position) based on node’s own stability, i.e., self stability, and neighbor nodes stability. (2) Designing a mathematical
model for selecting noncongested nodes based on channel load and node buffer occupancy. (3) Designing a mathematical
model for finding link expiry time between pair of nodes. (4) Design of route discovery process, which includes request phase
to find routes to anycast servers through forwarding intermediate nodes which satisfy stability, congestion criteria and also
meet the route expiry deadline; and reply phase to update routing cache and confirm the routes found in request phase, and
(5) designing route maintenance procedure to handle node and link failures.
The rest of the paper is organized as follows. Section 2 presents an overview of existing MANET anycast routing protocols,
Section 3 discusses the proposed work. Simulation and result analysis are presented in Section 4, and conclusions are given
in Section 5.
2. Related work
Related works done in the field of anycast routing are presented in this section. Anycast service discovery in MANETs usually
relies on network-layer message broadcasting, which leads to large traffic overhead for the scarce bandwidth of
MANETs. In Design and implementation of an anycast services discovery (DIASD) [7], traffic-control mechanism is used to
balance the load in anycast service discovery, and also supports k-anycast service. With k-anycast service, the fault tolerance
and service flexibility is improved. DIASD scheme is used for comparison with our scheme to overcome some of its drawbacks
as follows.
DIASD is basically a hierarchical routing protocol, where in prior to the construction of anycast tree, node clustering and
virtual backbone are required to organize the nodes in a MANET. Route computation is carried out at the cluster head nodes
only; the movement of the cluster nodes adversely affects the performance of the protocol. Also, the cluster node update
information could cause a significant amount of control overhead. Thus the main drawback of the tree based protocols is
that they are not robust enough to operate in highly mobile environments.
The work presented in [8] introduces anycast method and theory into challenged communication processes in
opportunistic network. In [9], IPv6 uses anycast concept and proposes a k-anycast communication model which can route
k-anycast service request messages to the nearest k-anycast tree node to provide the requested service, and can evenly distribute
across the k-anycast tree nodes.
In [10], authors consider the density of nodes through count of routes to the anycast group member as a routing metric. In
[11], a QoS anycast routing algorithm based on ant colony optimization is proposed, which regulates the pheromone on the
best path and adopts resetting method and candidate set strategy to avoid falling into local optimal path and expand searching
space of ant colony. In [12], Zone Routing Protocol (ZRP) and anycast addressing is presented assuming the destination as
a member of anycast address.
The work presented in [13] proposes an Adaptive Neuro-Fuzzy Inference System (ANFIS) based multiple QoS constrained
anycast routing by using a set of static and mobile agents. The work given in [14] provides load balancing and failover services
in a way that other IT organization teams can use without having to manage the underlying technology.
A Petri-net-based simulation model of a MANET is developed and studied in [15]. The model enables representation of
reliability aspects of wireless communication such as fading effects, interferences, presence of obstacles and weather conditions
in a general and rather easy way.
The work proposed in [16] is an adaptive congestion aware protocol that detects and reacts to congested nodes and congested
parts of the network by using implicit hybrid contact and resources congestion heuristic in delay tolerant networks. In
[17], a framework to evaluate network dependability and performability is presented.
In [18], various schemes to improve routing protocol performance by using mobility prediction is presented. To avoid
congestion in IP, a backup topology design method is used in [19]. This backup topology design method splits the traffic
on high load links to other links by considering network conditions, such as the traffic matrix or topology.
The work given in [20] explores an end-to-end threshold-based algorithm which enhances congestion control to address
link failure loss in MANET by using link failures, round trip time and retransmission time out estimation. The work presented
in [21] for Limiting Greedy Connections (LGC) uses an active congestion control mechanism for minimizing the degradation
in network performance caused by bandwidth greedy applications on a congested node. The work presented in [22] proposes an early congestion detection and adaptive routing which constructs a NHN (non-congested neighbors) list and finds a route
to a destination through NHN nodes.
The work given in [23] considers finding QoS anycast path from client (source) to any one of the server by using software
agents. Protocol uses integration of static and mobile agents for inferring the QoS path from a set of multiple paths by using
Fuzzy Inference System (FIS). The work given in [24] proposes a QoS-Oriented Distributed routing protocol (QOD) to enhance
the QoS support capability of hybrid networks. Taking advantage of fewer transmission hops and anycast transmission features
of the hybrid networks, QOD transforms the packet routing problem to a resource scheduling problem.
In [25], k-anycast members are selected from a set of servers by three different schemes. The three schemes discuss about
how to select k servers depending on the radius of flooding, by selecting at least k members and members less than k members.
The Adaptive On-demand Distance Vector (AODV) routing protocol extended to support anycast routing is presented in
[26]. Route request and route reply are used to identify anycast server. A node communicates simultaneously with only one
anycast member.
The work given in [27] describes the probability of connected route to anycast member as a function of dynamicity and
density of the network. Anycast routing scheme chooses the shortest path routing as well as considers node degree density of
hosts in the network through count of routes to the anycast group member.
There are some works on smart packet based routing, hybrid routing and DSR security enhancement which may be helpful
in anycast routing. The work in [28] presents a new infrastructure where smart data packets are used to guide through
best available route in the network and minimizes convergence time. The work given in [29] proposes a routing protocol that
divides the Spatial Wireless Ad Hoc networks (SWAH) into backbone and non-backbone networks to perform static routing
and dynamic routing, respectively. It provides load balancing adaptively by establishing and maintaining multiple nodedisjoint
routes. Authors in [30] present a security enhancement to DSR protocol against wormhole attacks in ad hoc
networks for multirate transmissions which relies on calculation of round trip time (RTT). It uses the processing and queuing
delays of each participating node in the calculation of RTTs between neighbors.
According to the literature survey, it has been observed that there is scope for improving anycast routing schemes in
MANETs in terms of control overheads, load balancing, stable routes, and QoS. Thus there is a need to develop a robust
and an efficient movement stability and QoS based congestion aware anycast routing scheme in MANET. We have designed
three major models in our approach to anycast routing discovery problem. (1) Stability model to identify stable nodes, (2)
congestion model to take QoS into consideration by checking congestion aware parameters like channel load, and buffer
occupancy, and (3) link expiry time model to make sure the link duration will fall within an acceptable range.
3. Proposed work
This section presents, background of DSR, node movement stability model, congestion model, link expiration time model,
route establishment, route discovery and maintenance.
3.1. Background of DSR
Dynamic source routing (DSR) is an on-demand reactive routing protocol designed to restrict the bandwidth consumed by
control packets, by eliminating the periodic table update messages required in the table driven proactive approach.
It uses source routing instead of relying on the routing table at each intermediate node. DSR is beaconless and hence does
not require periodic hello packet transmissions. Route construction phase establishes a route by flooding route request (RR)
packets in the network. An intermediate node, upon receiving a RR packet, checks the sequence number on the packet before
forwarding it. The packet is forwarded only if it is not duplicate RR. The sequence number on the packet is used to prevent
loop formation. RR packet updates itself with traversed nodes address, which will facilitate in path construction. The destination
node, on receiving a RR packet, responds by sending a route reply (RP) packet to the source by using traversed
addresses. Thus source will have the address to destination through intermediate nodes.
Even though DSR protocol performs well in static and low mobility environment, the performance degrades rapidly with
increasing mobility. To enhance the performance, we use modified DSR and call it as Mobility and QoS aware Anycast
Routing in Mobile ad hoc Networks (MQAR). Our protocol (MQAR) works better under dynamic and high mobility environment,
since we include stability model to identify more stable nodes, congestion model to check traffic on the channel
dynamically and link expiry model to check duration of the link, so that selected path will stay for longer duration in anycast
routing.