An Extended Location-based Routing Approachfor Disaster Recovery of Wireless Networks
Guowei Chen , and Takuro Sato

Graduate School of Global Information and Telecommunication Studies Waseda University
1Introduction

With extensive research over the past few years, several
routing protocols, which do not make use of location
information, have been defined within MANET working groupof IETF. These protocols mainly adopt some mechanisms offlooding, either to detect routes on-demand, or to maintainrouting information proactively on each node. Due to theoverhead introduced by flooding, such protocols are considered
not to scale in networks with more than some hundred nodes. Inorder to solve this problem, geometric algorithm is introduced.
Recent availability in inexpensive and low-power GPS receivers
provides feasibility in adoption of location information inrouting algorithms for ad hoc networks. This research’s
motivation is to establish communication under natural disasters
especially earth quake disaster or tsunami disaster.
In location-based routing, usually the whole transfer processof a packet from a source node to a destination node consists ofa series of sub-processes of next-hop selection, based on thethree types of information as follows, location of the current
node, location of destination, and location of one-hop
neighboring nodes within the transmission range of the current
node. The first information is achieved via GPS, and the second
is available through some location management schemes, suchas VHR, GLS, and is contained in the packet’s header. The thirdcan be attained through a beaconing mechanism – exchange oflocation information via small packets broadcasts – which
introduces some traffic overhead and power consumption. Withthe three above information, a notion named progress can bevalued, and according to this value, the current node makes aselection out of all neighboring nodes as a next-hop in order toachieve optimum of the routing in a certain sense. But locating anode indoors remains a challenging problem. In an indoor
situation, the GPS approach cannot provide precise location
information. In this case, RSS (Received Signal Strength) can beused as an approach of location estimation.

D is considered forward, and node A1 and node A2 know thatthey are within the forward 60
sector and thus consider
themselves the candidates of the next-hop selection. So theyschedule to relay the packet with respective delay time
according to the notion of progress. In this algorithm, progress isdefined as a projection of the line from the current node to a
candidate on the line from the current node to the destination, as
explained in the figure. Here the delay time formula is definedas:Delay time = Max_Delay * ( r – p ) / r (1)Where Max_Delay is a global constant known by all nodes, r isthe broadcast radius, and p is the progress. Candidate nodes
have different progress, and they have different delay time. Thecandidate with the minimum delay time will broadcast thepacket first. On hearing this broadcast, other candidates willcancel the scheduled relay, and meanwhile some other nodes inforward direction will become new candidates. So the routing
continue hop-by-hop until reaching D. The above routing

Fig 1: beaconless routing
behavior is efficient, and is called basic mode.
3
3.1

2

Related Work

Lately, a new class of location-based algorithms andprotocols, such as BLR[1], IGF[2], and CBF[3], has achieved afeature of being beaconless. In these algorithms, the selection
decision is not made by the current node, but via a newmechanism of transmission time contention - DFD (dynamicforwarding delay), where the third information above is notnecessary, thus the beaconing is not needed. In another word,
only the first and the second information is needed. With theavoidance of periodical beacon messages, signalling overhead
and battery consumption are significantly reduced. Here theDFD mechanism and the selection process of BLR are explained.
As shown in Fig 1, a bunch of mobile nodes exist as the hostsof the network. They all have the functions of sending/receiving
as well as forwarding packets for others. A packet from a node S
is to be sent to a node D. Following the BLR algorithm, S
broadcasts the packet, and the neighboring nodes within thetransmission range of S, receive the packet. Direction from S toBLR Algorithm with Received Signal Strength
Avoidance of routing into sparse area

For the above beaconless protocols, operating mostly in thebasic mode is a key to efficiency, thus letting the routing happenas much as possible in a dense area is desired. Information ofneighboring nodes could have been helpful for picking out anode in relatively dense area during the next-hop selection. But
as a feature of such class of algorithms, the knowledge ofneighboring nodes is not required and not available without
beaconing.
But actually the broadcasts received from other nodes give
hints of existence of the neighbors, even though the update of
information is not as guaranteed as periodic beaconing. So if thenetwork traffic is above a certain level, the neighboring info ispossible to be obtained by short-termed historical traffic. In thispaper, the total signal strength from neighboring nodes within alatest historical period, e.g. 0.5 second, is considered as ameasure for the neighboring density. It is assumed that thestronger the neighboring signal strength is, the more dense area
the node is possibly in.

As in Figure 2 (a) and (b), A1 and A2 become the candidatesof next-hop, and the delay time is to be calculated. A candidate
might have received some signal from its neighboring rightbefore this moment. The strength of the signal received can betaken into consideration for calculating delay time.

Fig 2 (a) A1 & A2
are candidates

3.2

Fig 2 (b) historical signal
strength is considered

Procedures of the Algorithm

Network nodes attain the information of their own location
coordinates via GPS, Galileo, or other location service
technology. And via a location management scheme, a source
node can attain its destination’s location coordinates accuratelyenough. (Such location management schemes are not theresearch topic of this article.) There are two global constants
that are widely known by all nodes. One is Max_Delay, whichindicates the maximum time that a candidate node delays before
relaying a packet. Another one is transmission rage r, withwhich the network is modeled with unit disk graph where two
nodes can communicate directly in one-hop if their distance isless than r. Thus the radio links are bi-directional and theantennas are omni-directional. When a source node is to send apacket, it first retrieves the geographical coordinates of thedestination, and put it into the packet’s header. The coordinatesof the source node will be put into the header as well. Then thesource node broadcast the packet. If there are nodes within thetransmission rage, they will receive it. Now each of theseneighboring nodes has the location information of the source
and the destination, and in associate with its own location, theycan via geometrical calculation determine whether they are in a
forward area and evaluate progress. The nodes within theforward area become candidates of next-hop relay and apply
Dynamic Forwarding Delay, while other neighboring nodes
drop the received packet. The candidate with the shortest delay
time will make a broadcast as a relay first of the packet andother candidates will receive it and cancel the scheduled relay.
Each candidate node will replace in the packet header theprevious node’s location coordinates with its own location
coordinates. Thus, during the whole routing, each intermediate
node repeats a same behavior and eventually the packet willreach the destination.
3.3

Location Estimation Model with Received Signal
Strength Indicator

About the received signal strength distribution, path loss aswell as shadow effect is considered. Rayleigh fading isneglected here because it can be averaged out over the timescale considered. So the RSSI distribution is modeled as
y = K1 – K2 log(d) + μ +υ(2)where y is the value of RSSI, K1 and K2 represent the path loss
factors, d denotes the distance between the signal sending node
and a receiving node, andμandυrepresent the shadowing andmobility variables and, which are modeled as independent WSS
Gaussian process.
44.1

Simulation
Network Model

Simulation has been done on the platform of OMNET
network simulator with module mobility-framework, version
1.0a6. On the playground, a certain numbers of mobile nodes
are initially distributed in random. As the test begins, the nodes
will start to move and communicate with each other. The nodes
are designed to move at a constant velocity and change to arandom direction at a constant interval. At every sampling time,
subject to a global packet rate, a certain numbers of senderreceiver pairs are selected to perform packet transmission. One
time of the test lasts 10 minutes. The simulated protocols are theoriginal BLR and the BLR with historical signal strength whichis proposed in this article, operating in basic mode if possible,
else in backup mode. The backup mode that is employed here is
the Half-transmission Rang Approach.
4.2
Result of Delivery failure ratio
If a packet delivery failure happens in basic mode, the routing
will have to be switched to a backup mode. To evaluate theperformance of the next-hop selection algorithms, the failure
ratio of delivery in basic mode is taking as a performance
criterion. Tests have been performed with gradually increased
global packet rates, which specify a total number of the packets
to be send in a time unit (10 ms) by all nodes. This packet rate
indicates the global traffic level.
Figure 3 shows the failure ratios in basic mode of the original
and the proposed algorithms. It is shown that in general thefailure ratio of the original algorithm is higher than the proposed
one. This is less evident when the network traffic is too low, but
as the traffic increases, the difference turns more apparent. Thisis because as the traffic increases, the nodes update theirneighbors more frequently, so nodes in dense area gain morepriorities. The result shows that the proposed algorithm keeps
the routing working in basic mode more.

Fig. 3 Failure ratio in basic mode
5Conclusion

Location-based routing algorithms have the advantage that no
global topology information is needed, and that these algorithms
are more adaptive to the changes in the networks than thetopology based protocols. Beaconless location-based routing
algorithms further the sparing of signaling overhead and battery
consumption, but give up the knowledge of neighborhood.
Actually the neighboring information is possible to be extracted
from signal strength and location estimation is possible.
References
[1]

[2]

M. Heissenbuttel and T. Braun, A novel position-based andbeanconless routing algorithm for mobile ad-hoc networks, inProc. ASWN’ 03, Bern, Switzerland, pp. 197-210, July 2003.
B. Blum, T. He, S. Son, and 1. Stankovic, IGF: A state-freerobust communication protocol for wireless sensor networks,
Department of Computer Science, University of Virginia, USA,Tech. Rep. CS-XQ3-11,2003
H. F ussler, 1. Widmer. M. K memann, M. Mauve, and H.
Hartenstein, Beaconless position-based routing blr mobile ad-hoc
networks, Department for Mathematics and Computer Science,
University of Mannheim, Germany, Tech. Rep. TR-03-001,2003.