Transcript Application of GPS to a Mobile

Application of GPS to Mobile IP and
Routing in Wireless Networks
Mustafa Ergen, Sinem Coleri, Baris Dundar, Rahul Jain, Anuj Puri, Pravin
Varaiya
{ergen,csinem,dundar,rjain,anuj,varaiya}@eecs.berkeley.edu
University of California Berkeley
IEEE VTC, Vancouver, Canada, September, 2002.
Introduction
•Scenario
•Motivation
•Architecture
•Components
•Performance
•Conclusion
Scenario
Scenario 2
Architecture
Let`s put GPS to the cars and base stations
Management
Center
Internet
Limitations:
•Power constraints of Sensors
Mobile IP
with position
Ad Hoc
Network
Sensor Network
with position
•Overhead of Sensor Network
•Limited # of Base Stations
•Smooth Handoff Problem
User
•Overhead of Ad Hoc routing
Architecture
Mobile IP
Position based
Mobile IP
Ad hoc routing
Geographical
Routing
Sensor Network
Sensor Network
Architecture
Mobile Nodes
Correspondent Node
Management
Center
Transport Layer
Sensors
Sensor Layer
Home Agent
Foreign Agent
Mobile IP
IP
Sensor Network
Ad Hoc Network
(GRA)
IP Network
Geographical Routing Algorithm
Geographical network
Assumptions:
• Each node knows its own position and its neighbors’ position
• Nodes don’t know the global topology
• Destination address is a geographical position to which the
packet is to be delivered
A Simple Routing Algorithm
Routing Decision:
Route to the neighbor which is nearest to the packet destination
Destination
Source
Problem with Simple Routing
Wall
Destination
Source
• Simple routing doesn’t always work
• The Geographical routing algorithm is an extension of the
simple routing algorithm.
Route Discovery




Packet gets “stuck” when a node does not have a
neighbor to which it can forward the packet
When a packet is stuck, a Route Discovery is started
to destination D
A path p = s(0) s(1)...s(k) is found to D
Entry [ position(D), s(i+1) ] is added to the routing
table of s(i)
Route Discovery
Pos(D)
Pos(C) ---
B
Pos(D)
Pos(D)
Pos(B) --Pos(A) A
A
Pos(C) C
Pos(A) ---
Pos(D) C
Pos(B)
B
D
Pos(D)
B
Pos(D)
Pos(D)
C
Pos(B)
B
Pos(D)
D
Pos(D) --Pos(C) C
Pos(A) = (1,1)
Pos(B) = (2,2)
Pos(C) = (3,1)
Pos(D) = (2.5,0)
Links:
A ---- B
B ---- C
C ---- D
• A gets a packet for Pos(D)
• Packet gets stuck at A because Pos(A) is closest to Pos(D)
• Initiate route discovery for D from A
• Update the routing tables and forward the packet
A Geometrical View
Routing Table for Station n:
(x,y) position
Vornoi View:
Neighbor
Position of n
-
Position of
neighbor a
a
Position of
neighbor b
b
a
n
(12,4)
a
(12,4)
• Route discovery is initiated if packet destination falls within
the cell containing station n
• Each route discovery causes the cell with station n to get split
b
Routing Table Size
How many “splits” before station n is alone in its cell ?
• Each split reduces the cells area ~ 1/2
• The cell’s area when station n is alone in the cell ~ 1/N
where N is the number of stations in a unit area
=> log(N) splits before station n is alone in its cell
Each split causes a route discovery
Each route discovery causes L entries to be added to the routing
tables where L is the average route discovery path length
=> O( L log(N) ) entries in routing table of each station
Performance of
GRA
Position based Fast Handover Algorithm
Fast Handover
Mini Base Stations
Internet /
DataBase Server
Intermediate Network
Mobile
Performance of
FASTMIP
•A Handoff Scheme
compared to
vanilla Mobile IP.
•Buffering and Positioning
increase the performance of
the handoff.
Sensor Network
•Initiated by the Mobile
•Localization scheme
•Small scale tree type sensor network configuration
•Time < seconds
Conclusion
•Using Mobile Stations as a mobile base for sensors
-Reduces power loss and routing overhead
•Using GPS on mobiles
-Reduces the adhoc routing overhead
-Reduces the routing table size
•Using GPS on base stations
-Reduces the packet loss and delay
-Integrate easily with the GRA