Information Technology Reference
nodes in the system are either in the set or neighbors of nodes in the set. Routing
based on a connected dominating set is a promising approach, since the searching
space for a route is reduced to nodes in the set. GRID tries to exploit location infor-
mation in route discovery, packet relay, and route maintenance.
In GRID the geographic area is partitioned into a number of squares called grids.
In each grid, one mobile host (the one nearest to the physical center of the grid) will
be elected as the leader of the grid. The size of each grid depends on transmission
radius R, and several options are proposed, with general idea of one leader being able
to communicate directly with leaders in neighboring grids, and all nodes within each
grid being connected to their leaders. Routing is then performed in a grid-by-grid
manner through grid leaders, and non-leaders have no such responsibility. Hence, the
number of packets related to route search is insensitive to the network density. On the
contrary, the cost slightly goes down as the host density increases, since routes are
becoming more stable with denser hosts.
In GRID, efforts are made in two directions to reduce the route search cost; using
the locations of source and destination to confine the search range (like request zone
in LAR) and delegating the searching responsibility to the gateway hosts. One attractive
feature of GRID is its strong route maintenance capability since when a leader moves,
another leader from the same grid replaces it by a handoff procedure. The probability
of route breakage due to a nodes roaming is reduced since the next hop is identified by
its physical location, instead of its address. Grid uses a specific field to detect duplicate
request packets from the same source, so endless flooding of the same request can be
avoided, i.e., it is loop-free routing.
Simulations in [ 15 ] showed that GRID can reduce the probability of route breakage,
reduce the number of route discovery packets and lengthen routes' lifetime. On the
other hand their simulations showed that GRID uses longer paths than that used with
LAR, since the former always confines relay hosts to gateway hosts while LAR tries
to search the route with the smallest host count. Also, the authors do not elaborate
on route maintenance required when a grid remains empty after its leader and only
node leaves it [ 24 ]. Feeney and Nillson in [ 28 ] and Shih et al. in [ 29 ] concluded that
the idle power consumption is nearly as large as that of receiving data. Also, a node
in idle mode spends about 15-30 times more energy than if it is in sleep mode.
Therefore, developing protocols that have as many as possible sleeping nodes, such as
GRID, will save network energy significantly.
TERMINODES [ 16 ] is an example of hierarchical routing protocols. TERMINODES
presents a two-level hierarchy within which, if the destination is close to the sender
(in terms of number of hops), packets will be routed base on a proactive distance vector.
Greedy routing is used in long distance routing [ 13 ]. TERMINODES addresses the
following objectives: scalability (both in terms of the number of nodes and geographical
coverage), robustness, collaboration, and simplicity of the nodes [ 24 ].