Transcript Overview of Wireless Networks - University of California

Overview of Wireless
Networks
Anuj Puri
Nov. 14, 2000
Outline
Projections of wireless growth
Cellular Networks
Wireless LANs and Bluetooth
WAP
Ad Hoc wireless networks
HUGE EXPECTATIONS AND INVESTMENT IN M-DATA
European UMTS spectrum auctions
$ Billions
Millions of subscribers worldwide
Mobile phone
subscribers
1,200
1,000
17
TV
households
800
46
98
600
400
s
PC
35
200
0
1998 1999
2000 2001
2002 2003
U.K.
lice
nse
s
Ger
man
lice
nse
s
Fre
nch
lice
nse
s
UMTS
license
fee to
date
(not
exhausti
ve)
SUCCESS OF I-MODE IN JAPAN
Number of i-mode subscribers
Thousands
8,000
7,000
6,000
5,000
i-Mode has
already
exceeded
12 million subs
4,000
3,000
2,000
1,000
0
Feb 22,
1999 start
Aug
8
No
De
v 18 c 23
May 31,
2000
Outline
Projections of wireless growth
Cellular Networks
Wireless LANs and Bluetooth
WAP
Ad Hoc wireless networks
Cellular Networks
Mobile phones (internet access)
Cellular concept


Frequency reuse
Handoffs
Organization of Cellular
Networks
BS – modulation, antenna
MSC – switching
HLR – information (location)
about “home” users
VLR – information about
visiting users
BS
(base station)
HLR (home location
register)
MSC (mobile
switching center)
VLR (visitor
location register)
How does a call get to the
mobile ?
Suppose (510) 643 - 1111 is roaming in the
(703) area code
Cell phone registers with the (703) MSC,
which adds it to (703) VLR and informs the
(510) HLR of the location of the cell phone
A call comes in for (510) 643 – 1111. Then
(510) MSC queries its HLR, and directs the
call to the (703) MSC
The (703) MSC forwards the call to the
mobile
Handoff
HLR
MSC
VLR
BS A
BS B
• Mobile is associated with BS A
• It continuously monitors the signal strength from BS A,
and BS B
• When the signal strength from BS B becomes stronger,
it associates with BS B
Evolution of cellular industry
First Generation
Second Generation Third Generation
Analog Voice
Digital Voice
Packet data
AMPS
GSM, IS-95,
IS-136, PDC
W-CDMA, EDGE,
CDMA2000
MULTIPLE MIGRATION PATHS
ARE AVAILABLE
2G
2.5G
3G
PDC
GSM
WCDMA
GPRS
CDMA
(IS95A/B)
* Footnote
Source:Sources
CdmaO
ne
1XRTT
4G
HSPDA
OFDM
EDGE
TDMA
(IS136)
3+G
1XEVDO/HDR
1 xtreme
Software
radio
Array
antennas
cdma2000
MC-3X
3G Networks
SGSN
GGSN
BS A
BS B
Access Network
Physical layer/ MAC
SGSN
IP based Core Network
Routing/network handoff
Mobile IP
Home Agent (HA) – keeps track of where the
mobile is (similar to GGSN)
Foreign Agent (FA) – delivers packets to the
mobile in the foreign network (similar to
SGSN)
All packets for mobile arrive at HA which
“tunnels” them to mobile’s FA
When mobile moves to a new location, it
informs its HA of the new FA
Outline
Projections of cellular growth
Cellular Networks
Wireless LANs and Bluetooth
WAP
Ad Hoc wireless networks
Wireless LANs and Bluetooth
For indoor use or operation over small
areas
Operates in ISM (Industrial Scientific
and Medical) Band
Spread Spectrum techniques
Main Components of 802.11
Roaming
Medium Access
Control
Physical Layer
Physical Layer
Operate in unlicensed bands


In U.S., 900 MHz, 2.4 GHz, 5.7GHz
Various restrictions on use
Spread Spectrum techniques


Direct Sequence Spread Spectrum
Frequency Hopping Spread Spectrum
Medium Access Layer
Why not use Ethernet protocol ?

Sender cannot detect collision
 senders power overwhelms other transmitters
 carrier sense does not necessarily mean
collision


Receiver has a better idea of whether a
collision is happening
Hidden Terminal / Exposed Terminal
Problem
Hidden and Exposed Terminals
A
B
C
A and B can hear each other
B and C can hear each other
A and C can not hear each other
Both A and C want to transmit to B (Hidden Terminal)
B wants to transmit to A when C is transmitting to someone
else (Exposed Terminal)
MACA
A wants to transmit to B
- A sends a RTS to B
- B replies with a CTS
- A sends data to B
RTS: contains the length of data
CTS: also contains the length of data
Everyone hearing RTS stays quiet for CTS
Everyone hearing CTS remains quiet for RTS
802.11 MAC
CSMA/CA (Carrier Sense / Collision
Avoidance)


Carrier Sense (check to see if someone is
transmitting)
Collision Avoidance (RTS-CTS-Ack)
Acknowledgments at link level
Fragmentation and Reassembly
Basic Scheme
RTS
Data
CTS
ACK
Defer Access
NAV (RTS)
NAV (CTS)
Back-off Window
Some Terminology
Distribution
System
Access
Point
Access
Point
Basic Service Set (BSS)
Extended Service Set (ESS)
Bluetooth
Master-slave architecture
Frequency hopping system
System design for cheap production
Outline
Projections of cellular growth
Cellular Networks
Wireless LANs and Bluetooth
WAP
Ad Hoc wireless networks
WAP (or the web for small
wireless devices)
Why not use wired web infrastructure (html,
http, tcp) ?


HTML too feature rich for small devices
TCP may have too much overhead for low
bandwidth wireless links
WAP (Wireless Application Protocol)



An optimized stack for wireless applications
Mobile talks with the WAP gateway
WAP gateway talks with the web server on the
internet
WAP Architecture
WAP
HTTP/TCP
WAP
Gateway
Internet
Web Server
WAP Stack
WML, etc
HTML
WSP (Session
Protocol)
HTTP
WTP (Transaction
Protocol)
WDP (Datagram
Protocol)
Bearer Services
SMS, CSD
TCP/UDP
IP
Gateways/Proxies for Wireless
Devices ?
Gateway
Internet
Web Server
2nd Generation: Low speed data, small displays  WAP
3rd Generation: Higher speed, IP address for each station
 Proxy/ Gateway ?
Outline
Projections of wireless growth
Cellular Networks
Wireless LANs and Bluetooth
WAP
Ad Hoc wireless networks
Ad Hoc Wireless Networks
No base stations or infrastructure
required
Multi-hop wireless networks

Each node can talk with a neighbor
Applications


Sensor networks
Intelligent control applications (i.e, IVHS)
Ad Hoc Wireless Networks
MAC schemes
Addressing
Routing
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.
Routing Tables
Routing Table for Station n:
(x,y) position
Neighbor
Position of n
-
Position of
neighbor a
a
Position of
neighbor b
b
(12,4)
a
Routing Tables:
• Routing tables contain some
additional entries beside neighbors
Routing Algorithm:
• Packet arrives for position p
at node n
• Node n finds the position to
which p is closest and forwards
to the corresponding neighbor
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)
Example
B
Pos(B) --Pos(A) A
Pos(C) C
Pos(C)
A
Pos(A)
---
Pos(B)
B
Pos(A) = (1,1)
Pos(B) = (2,2)
Pos(C) = (3,1)
Pos(C)
C
Pos(C)
Pos(C)
---
Pos(B)
B
Links:
A ---- B
B ---- C
• A gets a packet for Pos(C)
• A forwards it to B because pos(B) is closer to pos(C)
• B forwards it to C because pos(C) is closer to pos(C)
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
Theorem: There are no cycles in the routing tables.
--- Think of the routing entry [ position(D), a] as a path with
end point D. Then we are always following a path whose end
point is closer to the destination then the end point of the
previous path.
A Geometrical View
Routing Table for Station n:
(x,y) position
Position of n
Neighbor
a
-
Position of
neighbor a
a
Position of
neighbor b
b
(12,4)
Vornoi View:
a
n
b
(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
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
Outline
Projections of wireless growth
Cellular Networks
Wireless LANs and Bluetooth
WAP
Ad Hoc wireless networks