Transcript Mobile Computing

What is Mobile Computing?
 Wireless Communication Systems
 Mobile Communication Systems Architecture
 Key Technologies of Mobile Computing
 Applications

Key Technologies of Mobile Computing
Positioning
 Mobility management
 Routing
 Mobile agent

Positioning – Needs of Pedestrains
汽車導航：靠GPS，精準度容忍較高
行人導航：可能在indoor或地下室，精準度容忍較低
Positioning Technologies
Concepts of positioning
 Satellite-based solutions
 Network-based solutions
 IMU-based solutions

Concepts of Positioning
測量使用者與衛星距離
系統管理者survey network infrastructure，
BS如何佈置，訊號特徵
慣性導航，感測手機加速度及方向
(角度)改變以進行導航
Comparisons of Positioning Technologies


Satellite-based solutions
 higher hardware cost (terminal-based positioning)
 function well in outdoor environments
[高樓大廈密集會有問題]
 example: GPS, A-GPS, D-GPS
Network-based solutions
 need communication infrastructure
[e.g. base station]
 more suitable in indoor environments
[有infrastructure訊號覆蓋就可以]
 example: WiFi, PHS, GSM

IMU (Inertial Measurement Unit)-based solutions
 extra hardware cost
[G-sensor (重力感應器) 和M-sensor (電子羅盤)]
 without any infrastructure support
 inherently accumulated errors
[同時需要依賴其他技術及參考座標，會有累積誤差問題]
 usually operate as auxiliary component
Satellite-Based Solutions

Triangulation (Trilateration)





triangulation：利用GPS或BS訊號，透過TOA (Time of
Arrival)技術，量測自己跟三個點的距離跟角度
trilateration: a method for determining the
intersections of three sphere surfaces given the
centers and radii of the three spheres.
measure distances or angles of at least three
reference points
usually need specific hardware supports
widely used in many positioning systems, such as
GPS
GPS

GPS
distance is measured by time of arrival (ToA)
[根據打下來的訊號傳送到參考點的時間，再乘以光速當
做距離的判斷]
 need very precise time synchronization
 1μs time shift will result in 300m distance error


GPS systems
USA: GPS
 Russia: GLONASS
 Europe: Galileo
 China: Beidou

Data Transferred from Satellites
Constellation [星曆，星座區域，衛星的位置] of 24 satellites
 L1 frequency for civilian use
 L2 frequency for military and government use
 1500 bits/frame, 50bps (pretty low)

[星曆資訊包在一個frame的內容中傳送，手機透過GPS設備接
受此星曆資訊]

Time of week, TOW
Data Transferred from Satellites
Broadcast Ephemeris [【天】星曆表;(帶星曆表的)曆書]
(accurate position)
 Almanac [曆書;年曆]
 At least 30 sec. for first fix

[開機後需30 sec設定時間，對汽車導航算是可接受，對手機
使用者LBS服務30 sec時間太長]
AGPS (Assisted GPS)

GPS’s weaknesses
TTFF (Time To First Fix) of GPS > 30 seconds
(average case: 2~3 min)
 signal cannot be correctly received in buildings or
sheltered areas


Possible solutions
A-GPS
 透過BS接收星曆資訊，透過網路傳給手機
 FCC: a preferred solution for E911
 operators: no need to change telecommunication
infrastructure

AGPS Concept
Positioning Errors of GPS

Standard Positioning Service (SPS)
 C/A-Code (Coarse/Acquisition Code)
 SA (Selective Availability)
西元2000年前US Army在衛星加入SA干擾，定位誤差達
150m
 西元2000年後，移除SA干擾，定位誤差可到25m，汽車
導航才能精準使用，但需求精準度更高的LBS服務仍無
法使用

horizontal accuracy: 100m
 vertical accuracy: 156m
 commercial use


Deviation is more than 5 meters
 weather error
 multipath error
 GDOP (Geometric Dilution of Precision)
 receiver error
 Ephemeris error
 SA (Selective Availability)
 cycle slips
DGPS (Differential GPS)
Goal: increase the accuracy of positions derived
from GPS receivers
 Use base receivers with known locations nearby
the GPS receivers to achieve high positioning
accuracy (< 5m)

[根據自己的經緯度座標，再與收到的衛星訊號做計算，最
後把校正碼(corrections)送給附近的使用者]
The cost of build-in GPS chip is more than 10% of
the material cost of mobile phones
 The number of mobile phones equipped with GPS

OBSERVATION

Americans time spent
indoors: 89%
 transport: 6%
 outdoors: 5%

Network-Based Postioning

Properties
need communication infrastructure
 more suitable in indoor environments
 example: WiFi, PHS, GSM


Site survey
deployment of base stations
 radio map


Categories
cell-ID
 triangulation / trilateration
 fingerprinting

Cell-ID Localization
Error = 200m~1km
1. User找最近的BS
2. 管理者需經過site survey知道BS座標
3. Cell-ID localization最易實作，
但誤差大(約數百公尺到一公里)
Triangulation Localization
Problems:
propagation attenuation,
multipath
1. 利用訊號衰減做為距離量測方式
2. 根據收到三個BS訊號強度，
換算距離，可定自己的位置
3. 缺點：訊號強度不穩定，
會有multipath的問題
Indoor is better, error = 3m
Fingerprinting Localization
1. 西元2000年，Microsoft Lab提出，
透過特徵比對做定位
2. 管理者先做site survey，在固定點收訊號，
用特徵值表示在該位置附近的BS所收訊號
(Radio Pattern)
3. 將這些特徵值存在DB (包括經緯座標
及訊號特徵)
4. 商業化系統：Skyhook Wireless
Technology Used in Revolutionary iPhone
and iPod touch (蒐集上億802.11訊號)
5. 此方法適用在indoor (精準度可達3m)，
其位置與訊號特徵值差異不會太大
IMU-Based Positioning

Properties
without any infrastructure support
 inherently accumulated errors
 usually operate as auxiliary component


Extra hardware cost
inertia reference
 relative acceleration (G-Sensor [重力感應器], Pedometer [
步數計;步程計] Function)
 relative angle (M-Sensor [電子羅盤], Compass Function)

Summary of Positioning Technologies
A reliable and ubiquitous positioning technology
is the key factor of LBS
 There is no dominating positioning technology
 Hybrid positioning may be the answer

SMS for Location

Simple format for mobile phones’ short message service
[描述定位結果]

Google Maps and Google Latitude support announce
location via SMS (proprietary format).
Source: 工業技術研究院GPS位置資訊簡訊共通標準座談會
OPEN GeoSMS

Examples
OMIA,1;2504.8015,N;12133.9766,E;1;101,02-81018898,台北市
信義路五段七號
 GeoSMS/2;2502.01,N;12133.851,E;P;101/02-81018898/台北市
信義路五段七號

Source: 工業技術研究院GPS位置資訊簡訊共通標準座談會
Application: Car Accident Insurance Process
Key Technologies of Mobile Computing
Positioning
 Mobility management
 Routing
 Mobile agent

Mobile Management – Cellular System
GSM System Architecture
GSM Location Area Hierarchy
Handoff
Inter-LA Registration
Inter-MSC Registration
Inter-VLR Registration
Successful registration
HLR
Location update into HLR
Deregistration
Delete VLR data
3
5
TMSI
Old
VLR
New
VLR
2
MS IMSI & other data for authentication
1
TMSI, old LAI,
MSC, VLR
4
new
TMSI
Call Origination Procedure
Call Termination Procedure
Mobile Management –
Mobile IPv4

Mobility issues in IP Networks
once a mobile terminal moves to a new subnet, a
correspondent node needs to use the mobile’s new IP
address
 it is difficult to force every possible correspondent
node to keep track when a mobile terminal may
change its IP address and what the mobile’s new
address will be
 changing IP address will cause on-going TCP
sessions to break


Mobility management should
ensure on-going TCP connection does not break
 restore quickly if TCP connection breaks

Home Network
 Home
address
a globally unique and routable IP address
 preconfigured or dynamically assigned

 Home

network
the network whose network address prefix matches that of
the mobile terminal’s home address
 Home
agent (HA)
maintain up-to-date location information for the mobile
 intercept packets addressed to the mobile’s home address
 tunnel packets to the mobile’s current location

Note: Network Prefix
7
A:
0
24
Network
Host
14
B:
C:
1
1
0
1
16
Network
0
Host
21
8
Network
Host
Class A Network (/8 Prefixes)
Class B Networks (/16 Prefixes)
Class C Networks (/24 Prefixes)

IP addresses are divided into three different
classes
each of the following figure defines different-sized
network and host parts
 there are also class D addresses specify a multicast
group, and class E addresses that are currently
unused
 in all cases, the address is 32 bits long

43
7
A:
0
24
Network
Host
14
B:
1
0
16
Network
Host
21
C:
1
1
0
Network
8
Host
IP addresses: (a) class A; (b) class B; (c) class C
44

45
the class of an IP address is identified in the most
significant few bits
 if the first bit is 0, it is a class A address
 if the first bit is 1 and the second is 0, it is a class B
 if the first two bits are 1 and the third is 0, it is a class
C address
32
 of the approximately 4 billion (= 2 )possible IP
addresses
 one-half are class A
 one-quarter are class B
 one-eighth are class C
Class A addresses
 7 bits for the network part and 24 bits for the host part
7
 126 (= 2 -2) class A networks (0 and 127 are reserved)
24
 each network can accommodate up to 2 -2 (about 16
million) hosts (again, two are reserved values)
 Class B addresses
 14 bits for the network part and 16 bits for the host
part
16
 65,534 (= 2 -2) hosts

46

47
Class C addresses
 21 bits for the network part and 8 bits for the host
part
2l
 2,097,152 (= 2 ) class C networks
 254 hosts (host identifier 255 is reserved for
broadcast, and 0 is not a valid host number)
IP addresses are written as four decimal integers
separated by dots
 each integer represents the decimal value
contained in 1 byte (= 0~255) of the address,
starting at the most significant
 eg., 171.69.210.245
 Internet domain names (DNS)
 also hierarchical
 domain names tend to be ASCII strings separated
by dots, e.g., cs.nccu.edu.tw

48
Foreign Network

Care-of Address (CoA)
 assigned to the mobile by the foreign network
 a mobile uses its CoA to receive IP packets in
the foreign network

Foreign agent (FA)
 provides CoAs and other necessary
configuration information (e.g., address of
default IP router) to visiting mobiles
 de-tunnels packets from the tunnel sent from a
visiting mobile’s HA and then delivers the
packets to the visiting mobile
 acts as the IP default router for packets sent
by visiting mobile terminals
 helps visiting mobiles to determine whether
they have moved into a different network
Two Types of COAs in MIPv4

Foreign Agent CoA
 an IP address of a FA
 each FA is responsible for providing FA CoAs
to visiting mobiles
 when FA CoA is used, the mobile’s HA tunnels
the packets to the mobile’s current FA that
addressed to the mobile’s home address
 the FA will then de-tunnel the packets and
deliver them to the mobile

Co-located CoA
a CoA acquired by a mobile terminal through any
method external to Mobile IP
 example, a mobile may use the Dynamic Host
Configuration Protocol (DHCP) to obtain a temporary
address dynamically
 the mobile terminal’s HA tunnels the packets
addressed to the mobile’s home address directly to
the mobile itself; these packets do not have to go
through any FA

Key Technologies of Mobile Computing
Positioning
 Mobility management
 Routing
 Mobile agent

Ad Hoc Routing Protocols

Ad hoc routing protocols must deal with




high power consumption
low bandwidth
high error rates
Ad hoc routing protocols category


table-driven
source-initiated (demand-driven)
Ad hoc routing
protocols
Table-driven
DSDV
CGSR
WRP
Source-initiated
on-demand
AODV DSR
LMR
ABR
TORA
SSR
Table-Driven Routing Protocols

Table-driven routing protocols



maintain consistent, up-to-date routing information
require each node to maintain one or more tables to store routing
information
Protocols



Destination-Sequenced Distance-Vector Routing (DSDV)
Clusterhead Gateway Switch Routing (CGSR)
Wireless Routing Protocol (WRP)
Source-Initiated On-Demand Routing
Protocols

Source-initiated on-demand routing protocols


creates routes only when desired by the source node
Some routing scheme





Ad Hoc On-Demand Distance Vector Routing (AODV)
Dynamic Source Routing (DSR)
Temporally Ordered Routing Algorithm (TORA)
Associativity-Based Routing (ABR)
Signal Stability Routing (SSR)
Ad Hoc On-Demand Distance Vector Routing
(AODV)

A source node initiates a path discovery process when



desires to send a message
does not already have a valid route
Path discovery
broadcasts a route request (RREQ) packet to its neighbors
 neighbors then forward the request to their neighbors until either
the destination or an intermediate node with a "fresh enough"
route to the destination is located

Propagation of the PREQ
 RREQ
& RREP
intermediate nodes record the address of the
neighbor from which the first copy of the broadcast
packet is received
 if additional copies of the same RREQ are later
received, these packets are discarded
 once the RREQ reaches the destination, the
destination node responds by unicasting a route
reply (RREP) packet back
 if a route entry is not used within the specified
lifetime, the route will be deleted

Path of the RREP to the Source
Key Technologies of Mobile Computing
Positioning
 Mobility management
 Routing
 Mobile agent

What is a Mobile Agent?

Mobile Agent (Intelligent Message)



an electronic message carries a computer program
either procedural or declarative
it can be executed by the receiving servers on behalf
of the originating client
the program in the message can instruct a receiving
server to forward the message to another server
continuously in a pipeline fashion
Mobile Agent Model

The agent model is based on the concepts of
places and agents

places
 places provide the environment for executing
mobile agents
 a place is entirely located on a single node of the
underlying network
 an agent system consists of a number of these
places

agents
 mobile agents are active entities, which may move
from place to place to meet other agents and to
access the places' services
 an agent can be identified by a globally unique
agent identifier, which is generated at the agent's
creation time and is not changed throughout its life
 communication between agents may be local or
global
Example of a Mobile Agent










指令l : 設定旅遊日期
指令2 : 要求進入某航空公司(airline A)的定位系統
指令3 : 要求定八月一日中午以後從紐約到芝加哥的頭等艙機位
指令4 : 要求進入AVIS租車公司的預約系統
指令5 : 要求預定一部中型車，取車時間為飛機到達後半小時，使
用期兩天
指令6 : 要求進入芝加哥希爾頓旅館的定房系統
指令7 : 要求訂一個晚上的單人房，到達時間為飛機抵達後兩小時
指令8 : 要求回到客戶的終端機(PC或smart phone等)
指令9 : 要求把結果存檔
指令10 : 要求顯示結果
Mobile Agent Itinery
Classification of Agents in a Mobile Agent
System
Mobile agents
 Service agents

system services
 application-level services

Types of Agents Communication
Agent / service agent interaction [client/server]
 Mobile agent / mobile agent interaction [peer-topeer]
 Anonymous agent group interaction
 User / agent interaction

Agent / Service Agent Interaction
Service agents are the representatives of services
in the agent world, the style of interaction is
typically client/server
 Services are requested by issuing requests,
results are reported by responses
 An RPC-like communication mechanism should
be provided

Client Server Paradigm
Mobile Agent / Mobile Agent Interaction
The rule of the communication partners in this
type are peer-to-peer rather than client/server
 Each mobile agent has its own agenda and hence
initiates and controls its interactions according to
its needs and goals

Mobile Agent Paradigm
Why Mobile Agents for Mobile Computing?

Resolve the problems with wireless communications
noisy
 expensive
 low bandwidth
 unreliable (intermittent connection)
 limited battery life


Scalable clients

Resource optimization


if an agent's goals require extensive communication
with a particular resource on the network, moving
closer to the resource can reduce or eliminate
network traffic, allowing the agent to perform its
duties more quickly
Distributed parallel processing

agents can move to lightly loaded machines when
necessary and delegate subtasks to other mobile
agents, allowing true parallel processing

Reliability


mobility and autonomy allow an agent to move from its
point of origin into a network and continue to operate,
even if the originating device is temporarily or
permanently disconnected from the network
by doing so, the agent can provide services and satisfy
predefined goals without user intervention
Mobile Agent Systems
Mobile Agent System Author
Language
Secure Communication Server Resource
Agent Protection
Telescript
General Magic
Created their own
OO, type-safe
language
Not supported
Tacoma
D'Agents
Cornell University
University of Tromso,
Norway
Dartmouth College
Agent transfer is authenticated Capability-based
using RSA and encrypted
resource access. Quotas
using RC4
can be imposed.
Authorization based on
agent's identity
Not supported
Not supported
Aglets
IBM
Voyager
ObjectSpace
Concordia
Mitsubishi Electric
Ajanta
University of
Minnesota
Tcl, but is created
to be written in other
scripting languages
Tcl interpreter, mo- Uses PGP for authentication
dified to execute
and encryption
scripts and capture
state of execution at
thread level
Java. IBM developed Not supported
a separate class
library to create
mobile agents
Java. Unique feature Not supported
is a utility which
takes any Java class
and creates a remotely-accessible version of it.
Java. Has Itinerary Agent transfer is encrypted and
object, which keeps authenticated using SSL
track of an agent's
migration path
Java
Transfer is encrypted using
DES and authenticated using
ElGamal protocol
Not supported
Uses safe-Tcl as its
Not supported
secure execution envireon
ment. No support for
owner-based authorization
Statically specified access Not supported
rights, based on only two
security categories:
trusted and untrusted
Programmer must extend Not supported
Security Manager. Only
two security categories:
native and foreign.
SecurityManager screen
acceses using a statically
configured ACL based on
agent owner identity
Capability-based resource
access. Authorization
based on agent's owner
Agents protected from
other agents via the
resource access
mechanism
Mechanisms to detect
tampering of agent's
state and code