9
Routing protocols in mobile
and wireless networks
Mobile and wireless networks allow the users to access information and services elec-
tronically, regardless of their geographic location. There are infrastructured networks and
infrastructureless (ad hoc) networks. Infrastructured network consists of a network with
fixed and wired gateways. A mobile host communicates with a Base Station (BS) within
its communication radius. The mobile unit can move geographically while it is commu-
nicating. When it goes out of range of one BS, it connects with a new BS and starts
communicating through it by using a handoff. In this approach, the BSs are fixed.
In contrast to infrastructure-based networks, in ad hoc networks all nodes are mobile
and can be connected dynamically in an arbitrary manner. All nodes of these networks
behave as routers and take part in discovery and maintenance of routes to other nodes in
the network. Ad hoc networks are very useful in emergency search-and-rescue operations,
meetings, or conventions in which persons wish to quickly share information and data
acquisition operations in inhospitable terrain.
An ad hoc network is a collection of mobile nodes forming a temporary network
without the aid of any centralized administration or standard support services regularly
available in conventional networks. We assume that the mobile hosts use wireless radio
frequency transceivers as their network interface, although many of the same principles
will apply to infrared and wire-based networks. Some form of routing protocol is necessary
in these ad hoc networks since two hosts wishing to exchange packets may not be able
to communicate directly.
Wireless network interfaces usually operate at significantly slower bit rates than their
wire-based counterparts. Frequent flooding of packets throughout the network, a mecha-
nism many protocols require, can consume significant portions of the available network
bandwidth. Ad hoc routing protocols must minimize bandwidth overhead at the same time
as they enable routing.
Ad hoc networks must deal with frequent changes in topology. Mobile nodes change
their network location and link status on a regular basis. New nodes may unexpectedly join
Mobile Telecommunications Protocols For Data Networks. Anna Ha

Protocol (RIP) used in parts of the Internet. Consequently, DSDV only makes use of
bidirectional links.
In DSDV, packets are routed between nodes of an ad hoc network using a Routing
Table (RT) stored at each node. Each RT at each node contains a list of the addresses of
every other node in the network. Along with each node’s address, the table contains the
address of the next hop for a packet to take in order to reach the node.
DSDV generates and maintains the RTs. Every time the network topology changes,
the RT in every node needs to be updated. In addition to the destination address and
next hop address, RTs maintain the route metric (the number of hops) and the route
sequence number.
Periodically, or immediately when network topology changes are detected, each node
will broadcast an RT update packet. The update packet starts out with a metric of one.
This signifies to each receiving neighbor that it is one hop away from the node. The
neighbors will increment this metric and then retransmit the update packet. This process
repeats itself until every node in the network has received a copy of the update packet
with a corresponding metric. If a node receives duplicate update packets, the node will
only consider the update packet with the smallest metric and ignore the remaining ones.
TABLE-DRIVEN ROUTING PROTOCOLS
165
To distinguish stale update packets from valid ones, each update packet is tagged by the
original node with a sequence number. The sequence number is a monotonically increasing
number that uniquely identifies each update packet from a given node. Consequently, if
a node receives an update packet from another node, the sequence number must be equal
to or greater than the sequence number already in the RT; otherwise the update packet is
stale and ignored. If the sequence number matches the sequence number in the RT, then
the metric is compared and updated.
Each time an update packet is forwarded, the packet not only contains the address of
the destination but it also contains the address of the transmitting node. The address of
the transmitting node is entered into the RT as the next hop. The update packets with the
higher sequence numbers are always entered into the RT, regardless of whether they have

neighbors. A station also transmits its RT if a significant change has occurred in its
table from the last update sent. Thus, the update is both time-driven and event-driven.
The RT updates can be sent in two ways: a full dump or an incremental update. A full
dump sends the full RT to the neighbors and could span many packets, whereas in an
166
ROUTING PROTOCOLS IN MOBILE AND WIRELESS NETWORKS
incremental update, only those entries from the RT are sent that have a metric change
since the last update, and they must fit in a packet. If there is space in the incremental
update packet, then those entries may be included whose sequence number has changed.
When the network is relatively stable, incremental updates are sent to avoid extra traffic
and full dumps are relatively infrequent. In a fast-changing network, incremental packets
can grow, and full dumps will be more frequent. Each route update packet, in addition to
the RT information, also contains a unique sequence number assigned by the transmitter.
The route labeled with the highest (i.e., the most recent) sequence number is used. If
two routes have the same sequence number, then the route with the best metric (i.e., the
shortest route) is used. On the basis of the past history, the stations estimate the settling
time of routes. The stations delay the transmission of a routing update by settling time so
as to eliminate those updates that would occur if a better route was found very soon.
9.1.2 The wireless routing protocol
The Wireless Routing Protocol (WRP) is a table-based distance-vector routing protocol.
Each node in the network maintains a Distance table, an RT, a Link-cost table, and a
Message Retransmission List (MRL). The Distance table of a node x contains the distance
of each destination node yvia each neighbor z of x. It also contains the downstream
neighbor of z through which this path is realized. The RT of node x contains the distance
of each destination node y from node x, the predecessor and the successor of node x
on this path. It also contains a tag to identify if the entry is a simple path, a loop, or
invalid. Storing predecessor and successor in the table is beneficial in detecting loops
and avoiding counting-to-infinity problems. The Link-cost table contains cost of link to
each neighbor of the node and the number of timeouts since an error-free message was
received from that neighbor. The MRL contains information to let a node know which

9.1.4 Fisheye state routing
Fisheye State Routing (FSR) is an improvement of GSR. The large size of update messages
in GSR wastes a considerable amount of network bandwidth. In FSR, each update message
does not contain information about all nodes. Instead, it exchanges information about
closer nodes more frequently than it does about farther nodes, thus reducing the update
message size. Each node receives accurate information about neighbors, and the detail
and accuracy of information decreases as the distance from the node increases. The scope
is defined in terms of the nodes that can be reached in a certain number of hops. The
center node has the most accurate information about the other nodes. Even though a node
does not have accurate information about distant nodes, the packets are routed correctly
because the route information becomes more and more accurate as the packet moves
closer to the destination. FSR scales well to large networks as the overhead is controlled
in this scheme.
9.1.5 Hierarchical state routing
The characteristic feature of Hierarchical State Routing (HSR) is multilevel clustering
and logical partitioning of mobile nodes. The network is partitioned into clusters and
a cluster head elected as in a cluster-based algorithm. In HSR, the cluster heads again
organize themselves into clusters and so on. The nodes of a physical cluster broadcast
their link information to each other. The cluster head summarizes its cluster’s information
and sends it to the neighboring cluster heads via the gateway. These cluster heads are
members of the cluster on a level higher and they exchange their link information as well
as the summarized lower-level information among themselves and so on. A node at each
level floods to its lower level the information that it obtains after the algorithm has run
at that level. The lower level has a hierarchical topology information. Each node has a
hierarchical address. One way to assign hierarchical address is to use the cluster numbers
on the way from the root to the node. A gateway can be reached from the root via more
than one path; thus, a gateway can have more than one hierarchical address. A hierarchical
address is enough to ensure delivery from anywhere in the network to the host.
In addition, nodes are also partitioned into logical subnetworks and each node is
assigned a logical address <subnet, host>. Each subnetwork has a Location Manage-

a dynamic network, a cluster-head scheme can cause performance degradation due to
frequent cluster-head elections, so CGSR uses a Least Cluster Change (LCC) algorithm.
In LCC, cluster-head change occurs only if a change in network causes two cluster heads to
come into one cluster, or one of the nodes moves out of the range of all the cluster heads.
The general algorithm works in the following manner: the source of the packet transmits
the packet to its cluster head. From this cluster head, the packet is sent to the gateway
node that connects this cluster head and the next cluster head along the route to the
destination. The gateway sends it to that cluster head and so on till the destination cluster
head is reached in this way. The destination cluster head then transmits the packet to the
destination.
Each node maintains a cluster member table that has mapping from each node to
its respective cluster head. Each node broadcasts its cluster member table periodically
and updates its table after receiving other node’s broadcasts using the DSDV algorithm.
ON-DEMAND ROUTING PROTOCOLS
169
In addition, each node also maintains an RT that determines the next hop to reach the
destination cluster.
On receiving a packet, a node finds the nearest cluster head along the route to the
destination according to the cluster member table and the RT. Then it consults its RT to
find the next hop in order to reach the cluster head selected in step one and transmits the
packet to that node.
9.2 ON-DEMAND ROUTING PROTOCOLS
In contrast to table-driven routing protocols, all up-to-date routes are not maintained at
every node; instead, the routes are created as and when they are required. When source
wants to send a packet to destination, it invokes the route discovery mechanisms to find
the path to the destination. The route remains valid till the destination is reachable or
until the route is no longer needed.
9.2.1 Temporally ordered routing algorithm
Temporally Ordered Routing Algorithm (TORA) is a distributed routing protocol based
on a link reversal algorithm. It is designed to discover routes on-demand, provide multiple