Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks

Guangyu Pei Mario Gerla Tsu-Wei Chen

Computer Science Department Computer Science Department Bell Laboratories
University of California, Los Angeles University of Cidifomia, Los Angeles Lucent Technologies
405 Hilgard Avenue 405 Hilgard Avenue 600 Mountain Avenue
Los Angeles, CA 90095 Los Angeles, CA 90095 Murray Hill, NJ 07974
email: pei@cs.ucla.edu email: gerla@cs.ucla.edu email: tsuwei@research.bell-labs.com

Abstract - This paper presents a novel routing protocol for wireless ad flooding to disseminate the update information, excessive con-
hoc networks - Fisheye State Routing (FSR). FSR introduces the notion trol overhead may be generated, especially when high mobility
of multi-level fisheye scope to reduce routing update overhead in large net-
works. Nodes exchange link state entries with their neighbors wirh a fre- triggers frequent updates.
quency which depends on distance to destination. From link state entrier:,
nodes construct the topology map of the entire network and compute opti- The most recent addition to the family are the on demand
mal routes. Simulation experiments show that FSR D a simple, eficient an(d routing schemes (e.g., AODV [18], DSR [8] etc). In these “re-
scalable routing solution in a mobile, ad hoc environment.
active” protocols a node discovers a route in an “on demand”
fashion, namely, it computes a route only when needed. Small
I. INTRODUCTION AND RELATED WORK QueryReply packets are used to discover (possible more than)
one route to a given destination. However, since a route has to
Ad hoc wireless networks are self-organizing, self- be entirely discovered prior to the actual data packet transmis-
configuring and instantly deployable in response to applica- sion, the initial search latency may degrade the performance
tion needs without a fixed infrastructure existence. Therefore:, of interactive applications (e.g., distributed database queries).
ad hoc networks are very attractive for tactical communica- Moreover, it is impossible to know in advance the quality of
tion in military and law enforcement. They are also expected the path (e.g., bandwidth, delay etc) prior to call setup. Such a
to play an important role in civilian forums such as conven- priori knowledge (which can be easily obtained from proactive
tion centers, conferences, and electronic classrooms. Mobility, schemes) is very desirable in multimedia applications, since it
potentially very large number of mobile nodes, and limited re- enables more effective call acceptance control.
sources (e.g., bandwidth and power) make routing in ad hoc
networks extremely challenging. The routing protocols for ad In general, on demand routing performs extremely well (low
hoc wireless networks have to adapt quickly to the frequent and traffic and storage O M ) in large networks with light traffic (di-
unpredictable changes of topology and must be parsimonious rected to a few destinations) and with low mobility. As mobil-
of communications and processing resources. ity increases, the precomputed route may break down, requir-
ing multiple route discoveries on the way to destination. Route
Existing wireless routing schemes can be classified into two caching becomes ineffective in high mobility. Since flooding
categories according to their design philosophy: (a) proactive is used for query dissemination and route maintenance, on de-
(i.e., distance vector or link state based); and (b) on demand. mand routing tends to become inefficient when traffic load is
Proactive schemes compute routes in the background, indepen- high. As discussed in [6], routing load will grow as the traffic
dent of traffic demands. Historically, the first type of routing load increases for on-demand routing protocols. In the case of
scheme used in early packet radio networks such as the PRNET 100 nodes and 40 sources with uniform traffic pattern, the re-
was the distance vector type [9]. The distance vector approach sults in [6] show that both DSR and AODV will generate more
is simple but suffers from slow convergence and tendency of routing overhead than actual throughput. Similar findings are
creating routing loops. Convergence and looping problemis also reported in [ 121.
were later resolved by the Link State (LS) approach, which
is widely used in wired nets (e.g., Internet [16] or ATM [l]). A recent proposal which combines on demand routing and
In Link State, global network topology information is main- conventional routing is Zone Routing Protocol (ZRP) [lo]. For
tained in all routers by the periodic flooding of link state up- routing operations inside a local zone, an arbitrary proactive
dates by each node. Any link change triggers an immediate routing scheme (e.g., distance vector) can be applied. For in-
update. As a result, the time required for a router to converge terzone routing, on demand routing is used. The advantage of
to the new topology is much less than in the distance vector zone routing is its scalability, as “global” routing table over-
approach. Due to global topology knowledge, preventing rout- head is limited by zone size. Yet, the benefits of global routing
ing loop is also easier. Unfortunately, as Link State relies on are preserved within each zone. However, for the interzone
routing, the on-demand solution poses the usual problems of
This work was supported in part by NSF under contract ANI-9814675. in connection latency and high routing load for dense traffic pat-
part by DARPA under contract DAAB07-97-CD321 and in part by Intel. terns.

70
0-7803-6283-7/00/$10.00 0 2000 IEEE
 With the availability of GPS [ 131 technology, any of the pre- In routing, the fisheye approach translates to maintaining accu-
vious routing protocols can be assisted by GPS location in- rate distance and path quality information about the immediate
formation. For example, LAR [ 151 is an on demand protocol neighborhood of a node, with progressively less detail as the
similar to DSR but it restricts control packet flooding by using distance increases.
location information. DREAM [3] is a location based proac-
tive scheme. Each node in the network periodically exchanges FSR is functionally similar to LS Routing in that it maintains
control packets to inform all the other nodes of its location. a topology map at each node. The key difference is the way in
Each control packet is assigned a life time based on the geo- which routing information is disseminated. In LS, link state
graphical distance from the sender. DREAM sends short lived packets are generated and flooded into the network whenever a
packet more frequently than long lived packets due to the so node detects a topology change. In FSR, link state packets are
called distance effect,i.e., the farther two nodes separate, the not flooded. Instead, nodes maintain a link state table based on
slower they seem to be moving with respect to each other. The the up-to-date information received from neighboring nodes,
data packet is broadcast to the nodes in the direction of the des- and periodically exchange it with their local neighbors only
tination using only location information stored at the sender. (no flooding). Through this exchange process, the table entries
with larger sequence numbers replace the ones with smaller se-
In this paper, we introduce a novel “proactive” routing quence numbers. The FSR periodic table exchange resembles
scheme called Fisheye State Routing protocol. It is a link state the vector exchange in Distributed Bellman-Ford (DBF) (or
based routing protocol which is adapted to the wireless ad hoc more precisely, DSDV [ 171) where the distances are updated
environment. The rest of the paper is organized as follows. In according to the time stamp or sequence number assigned by
section 11, we describe the Fisheye State Routing (FSR). Sec- the node originating the update. However, in FSR link states
tion I11 presents the performance results and we conclude our rather than distance vectors are propagated. Moreover, like in
paper in section IV. LS, a full topology map is kept at each node and shortest paths
are computed using this map.
11. FISHEYE STATE ROUTING (FSR)
In a wireless environment, a radio link between mobile
A. Network Model and Data Structures nodes may experience frequent disconnects and reconnects.
The LS protocol releases a link state update for each such
Each node has a unique identifier. Nodes move around and change, which floods the network and causes excessive over-
change speed and direction independently. An undirected link head. FSR avoids this problem by using periodic, instead of
(i,j ) connecting two nodes i and j is formed when the distance event driven, exchange of the topology map, greatly reducing
between i and j become less than or equal to the transmission the control message overhead.
range R. For each node i, one list and three tables are main-
tained. They are: a neighbor list Ai, a topology table TTi, a When network size grows large, the update message could
next hop table NEXTi and a distance table Di. Ai is defined consume considerable amount of bandwidth, which depends
as a set of nodes that are adjacent to node i. Each destination j on the update period. In order to reduce the size of update
has an entry in table TTi which contains two parts: TTi.LS(j) messages without seriously affecting routing accuracy, FSR
and TTi.SEQ(j).TTi.LS(j)denotes the link state informa- uses the fisheye technique. Fig. 1 illustrates the application
tion reported by node j. TTi.SEQ(j)denotes the time stamp of fisheye in a mobile, wireless network. The circles with dif-
indicating the time node j has generated this link state informa- ferent shades of grey define the fisheye scopes with respect to
tion. Similar, for every destination j, N E X T i ( j ) denotes the the center node (node 11). The scope is defined as the set of
next hop to forward packets destined to j on the shortest path, nodes that can be reached within a given number of hops. In
while D i ( j )denotes the distances of the shortest path from i to our case, three scopes are shown for 1 , 2 and > 2 hops respec-
j . Additionally, one or more link weight functions may be de- tively. Nodes are color coded as black, grey and white accord-
fined and used to compute the shortest path based on a specific ingly. The number of levels and the radius of each scope will
metric, possibly with constraints. For instance, a bandwidth depend on the size of the network.
function can be used to support QoS routing. In this paper, we
limit ourselves to min hop paths, thus the link weight is 1. The reduction of routing update overhead is obtained by
using different exchange periods for different entries in routing
B. The Fisheye State Routing (FSR) Protocol table. More precisely, entries corresponding to nodes within
the smaller scope are propagated to the neighbors with the
FSR is an implicit hierarchical routing protocol. It uses the highest frequency. Referring to Fig. 2, entries in bold are
“fisheye” technique proposed by Kleinrock and Stevens [ 141, exchanged most frequently. The rest of the entries are sent
where the technique was used to reduce the size of informa- out at a lower frequency. As a result, a considerable fraction
tion required to represent graphical data. The eye of a fish of link state entries are suppressed in a typical update, thus
captures with high detail the pixels near the focal point. The reducing the message size. This strategy produces timely
detail decreases as the distance from the focal point increases. updates from near stations, but creates large latencies from

71
 proaches its destination, it finds increasingly accurate routing
instructions as it enters sectors with a higher refresh rate.

111. PERFORMANCE EVALUATION

-
A. Simulation Environment

We implemented our routing scheme within the GloMoSim

library [19]. The GloMoSim library is a scalable simulation
environment for wireless network systems using the parallel
discrete-event simulation language called PARSEC [2]. The
distributed coordination function (DCF) of IEEE 802.11 [ 111
is used as the MAC layer in our experiments. It uses Request-
To-Send (RTS) and Clear-To-Send (CTS) control packets to
Fig. 1. Scope of fisheye
provide virtual carrier sensing for unicast data packets to over-
come the well-known hidden terminal problem. Each data
transmission is followed by an ACK. Broadcast data packets
stations afar. However the imprecise knowledge of the best are sent using CSMNCA only. The radio model uses charac-
path to a distant destination is compensated by the fact that teristics similar to a commercial radio interface (e.g., Lucent’s
the route becomes progressively more accurate as the packet WaveLAN). Radio propagation range for each node is 150 me-
gets closer to destination. As the network size grows large, a ters and channel capacity is 2 Mbitskec. In most of experi-
“graded” frequency update plan must be used across multiple ments unless specified, the network consists of 100nodes. The
scopes to keep the overhead low. simulation area is 1000 x 1000 meter square. Each simulation
executed for 30 minutes of simulation time.

The random waypoint model [4], [8] was used in the simula-
tion runs. In this model, a node selects a destination randomly

40{1)
1:{0,2,3)
2:{5,1,4)
3:{1,4)
4:(5.2,3)
5:(2.4)

\ -._
within the roaming area and moves towards that destination at
a speed uniformally distributed between 0 &sec and 20 &sec.
Once the node reaches the destination, it selects another desti-
nation randomly and moves towards it after a predefined pause
time. Aforementioned behavior is repeated for the duration of
the simulation. The traffic is UDP sessions between random
node pairs. The number of source-destination pairs is varied in
the experiments to change the offered load in the network. The
\
\
. / interanival time of the data packets on each source/destination
connection is 2.5 seconds to model an interactive environment.
The size of data payload is 5 12 bytes. The load in the network
is increased by increasing the number of connections. We used
Fig. 2. Message reduction using fisheye 10, 50, 300 and 500 communication pairs in our simulation
experiments.
The FSR concept originates from Global State Routing B. Simulation Results
(GSR) [5]. GSR can be viewed as a special case of FSR, in
which there is only one fisheye scope level. As a result, the en-. The first experiment (Fig. 3) reports how routing overhead is
tire topology table is exchanged among neighbors. Clearly, this reduced when number of fisheye scopes is increased. For 100
consumes a considerable amount of bandwidth when network: nodes, we reduce more than 80% of routing overhead by using
size becomes large. Through updating link state information 3 scopes instead of just one scope (where all routing table en-
with different frequencies depending on the scope distance., tries are being updated very frequently). Also note that there is
FSR scales well to large network size and keeps overhead low not much reduction of overhead if the number of scopes is be-
without compromising route computation accuracy when the: yond 3. This is because most of the nodes are within 3 scopes
destination is near. By retaining a routing entry for each desti- for an area of 1000 x 1000 with 150 radio range. Thus, adding
nation, FSR avoids the extra work of “finding” the destination more levels than 3 only affects very few nodes. On the other
(as in on-demand routing) and thus maintains low single packet hand, having multiple scopes decreases the routing accuracy
transmission latency. As mobility increases, routes to remote: and might degrade the network performance. Fig. 4 shows
destinations become less accurate. However, when a packet ap- that the routing inaccuracies do result in a lower throughput

72
between one scope and two scopes. However, the throughput
is relatively insensitive to the number of scopes when number
l o o 5 ' I I
AODV pairs 10 -
I ,

DSRpairs 10 - - - I C - -
FSR pairs 10 ..... a.....
-
of scopes is greater than 2. This is because in a mobility envi- 80 -i!

ronment, a change on a link far away from the source does not 3
P k..,
necessarily cause a change in the routing table at the source. .? 60 - '...'..., -
B
Moreover, as a packet approaches its destination, the route be- e:
comes more precise.

2e+06

-
#of Scopes = 1 --.+--
# o f S c o p e s = 2 .....a.....
#of Scopes = 3 ---*--
# o f scopes = 5

AODVpain50
DSR pairs 50 - - - E- -
FSR pairs 50 -.El--
<00

500000
80 ,- -I

0
10 20 30 40 50 60 70 80 90 100
Number of Nodes

Fig.3. Overhead, #of Scopes and #of nodes

I I I
50Nodes
75Nodes
100Nodes
- I

--*--
---E--
100
0 100 200 300 400 500 600 700 800 900

I
Pause Time (secs)

I I I I I I I
AODVpairs300 ----C
DSR pairs 300 ---*--
FSR pairs 300 .....El.....
80 - -

.sa - -
8YJ 300
00 60

<
200

100
1 2 3 4 5
Number of Scopes

Fig. 4. Throughput,# of Scopes and # of nodes

Fig. 5 shows the normalized routing load as a function of of- AODVpairsSOO +

fered load and mobility. Normalized routing load is the num- DSR pairs 500 - - - ) I C - -
FSR pairs 500 _____a ___._
ber of routing control packets transmitted per data packet de-
livered at the destination [6]. This metric shows the routing
control penalty involved in delivering data. All previous sim-
ulation studies [6], [4], [7] focused on performance evaluation
for small number of traffic pairs (up to 40 pairs). In our ex-
periments, we study the performance of protocols under large
number of traffic pairs in addition to small number of traffic
pairs. For FSR, the number of control packets is a constant.
It is independent of number of sourcddestination pairs. Thus,
when the number of traffic pairs increases, the normalized rout-
ing load of FSR decreases. In AODV and DSR the number of
control packets increases with number of pairs as well as with
mobility. As number of pairs and load increase, the normalized Fig.5. Normalized Routing Load

73
load of on demand schemes is much higher than that of FSR. solution to the challenge of maintaining accurate routes in ad
hoc networks.

References
The ATM Forum, “Private Network-Network Interface Specification
v1.0,” 1996.
h
600 - R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, and H.Y.
500 Song, “PARSEC A Parallel Simulation Environment for Complex Sys-
tems,” IEEE Computer, vol. 31, no. 10, Oct. 1998, pp.77-85.
$
v

400 S. Basagni, I. Chlamtac, V.R. Syrotiuk, and B.A. Woodward, “A Distance

300 Routing Effect Algorithm for Mobility (DREAM),” In Proceedings of
ACMLEEE MOBZCOM’98, Dallas, TX, Oct. 1998, pp. 76-84.
200 J. Broch, D.A. Maltz, D.B. Johnson, Y.-C. Hu, and J. Jetcheva, “A Per-
100
formance Comparison of Multi-Hop Wireless Ad Hoc Network Routing
Protocols,” In Proceedings of ACMLEEE MOBICOM’98, Dallas, TX,
0 Oct. 1998, pp. 85-97.
0 100 200 300 400 500 600 700 800 900 T.-W. Chen and M. Gerla, “Global State Routing: A New Rout-
Offered load (kbits /sec) ing Scheme for Ad-hoc Wireless Networks,” In Proceedings of IEEE
ZCC’98, Atlanta, GA, Jun. 1998, pp. 171-175.
Fig. 6. Delay vs Offered Load S.R. Das, C.E. Perkins and E. M. Royer, “Performance Comparison of
Two On-demand Routing Protocols for Ad Hoc Networks”, In Proceed-
ings of IEEE ZNFOCOM 2000, Tel Aviv, Israel, Mar. 2000.
In Fig. 6, we report average delay as function of offered P. Johansson, T. Larsson, N. Hedman, B. Mielczarek and M. Degermark,
load. As the offered load increases, delay increases because “Scenario-based Performance Analysis of Routing Protocols for Mobile
Ad-hoc Networks,” In Proceedings of ACWIEEE MOBICOM’99, Aug.
of queue buildup. The delay of AODV increases faster than 1999, pp. 195-206.
the other protocols because of the higher routing overhead and D.B. Johnson and D.A. Maltz, “Dynamic Source Routing in Ad Hoc
thus higher load. Fig. 7 shows the throughput of FSR out- Wireless Networks,” In Mobile Computing, edited by T. Imielinski and
H. Korth, Chapter 5, Kluwer Publishing Company, 1996, pp. 153-181.
performs on demand protocols when number of traffic pairs is J. Jubin and J.D. Tomow, “The DARPA Packet Radio Network Proto-
large. All these simulation results clearly show that compared cols,” Proceedings of the IEEE, vol. 75, no. 1, Jan. 1987, pp. 21-32.
to on demand protocols, FSR exhibits a much better scalability Z.J. Haas and M. R. Pearlman “Determining the Optimal Configuration
for the Zone Routing Protocol,” In IEEE Journal on Selected Areas in
of traffic loads. Communications, Aug. 1999, pp. 1395-1414.
IEEE Computer Society LAN MAN Standards Committee, Wireless
450 I
LAN Medium Access Protocol (MAC) and Physical Layer (PHY)
I I ’ I I __..
I . . . = Specijication, IEEE Std 802.11-1997. The Institute of Electrical and
400 -AODV --C ...’_..’
__.. - Electronics Engineers, New York, NY, 1997.
DSR ---X-- ._..
350 FSR ..........
.a .._...
_..’ - A. Iwata, C.-C. Chiang, G . Pei, M. Gerla, and T.-W. Chen, “Scalable
m.. Routing Strategies for Ad-hoc Wireless Networks,” In IEEE Journal on
-
h

3.- 300 - Selected Areas in Communications, Aug. 1999, pp. 1369-1379.

I
- - E.D. Kaplan (Editor), Understanding the GPS: Principles and Applica-
2
- 250
tions, Artech House, Boston, MA, Feb. 1996.
4 200 L. Kleinrock and K. Stevens, “Fisheye: A Lenslike Computer Display
Transformation:’ Technical report, UCLA, Computer Science Depart-
150
ment, 1971.
100 Y.-B. KO and N.H. Vaidya, “Location-Aided Routing (LAR) in Mobile
Ad Hoc Networks,” In Proceedings of ACMLEEE MOBICOM’98, Dal-
50 l ~TX, , Oct. 1998, pp. 66-75.
0 J. Moy, “OSPF Version 2,” In IETFRFC 1583, 1994.
C.E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced
Distance-Vector Routing (DSDV) for Mobile Computers,” In Proceed-
ings of ACM SIGCOMM’94, London, UK, Sep. 1994, pp. 234-244.
C.E. Perkins and E.M. Royer, “Ad-Hoc On-Demand Distance Vector
Fig. 7. Throughput vs Offered Load Routing,” In Proceedings of ZEEE WMCSA’99, New Orleans, LA, Feb.
1999, pp. 90-100.
M. Takai, L.Bajaj, R, Ahuja, R. Bagrodia and M. Gerla, “GloMoSim:
IV. CONCLUSIONS
A Scalable Network Simulation Environment,” Technical report 990027,
UCLA, Computer Science Department, 1999.
In this paper, we present a new routing scheme, Fisheye
State Routing, which provides an efficient, scalable solution
for wireless, mobile ad hoc networks. We have compared the
performance of our routing protocol with on demand routing
protocols such as AODV and DSR. When the number of com-
munication pairs increases, on demand routing protocols will
generate considerable routing overhead. Simulation shows that
FSR is more desirable for large mobile networks where mobil-
ity is high and the bandwidth is low. By choosing proper num-
ber of scope levels and radius size, FSR proves to be a flexible

74