Transcript 投影片 1
Context-aware
Services in Ubiquitous
Network
Chiung-Ying Wang
Agenda
Introduction
Pervasive
Computing
Context-aware
Context-aware Service
Ubiquitous
Phone System (UPS)
Context-aware Path Planning (UbiPaPaGo)
Conclusion
2009/04/10
1
Introduction
With the advancement of technology and the
rapid development of mobile device, we are
entering the ubiquitous computing (UbiCom)
era advocated by Mark Weiser
A ubiquitous network aims to provide users
intelligent human-centric context-aware
services at anytime anywhere.
Context-aware is the key feature for humancentered services as it enables services
adaptive to human needs.
2009/04/10
2
Pervasive Computing
Mark Weiser’s[1] 1991 paper that described
his vision of ubiquitous computing
(ubicomp) , now also called pervasive
computing
Ubiquitous
computing is the method of enhancing
computer use by making many computers available
throughout the physical environment, but making
them effectively invisible to the user
Ubiquitous environment
Full
2009/04/10
of smart equipments and context-aware
information
Invisible computing
[1] M. Weiser, “The Computer for the Twenty-First Century,” Scientific American, pp. 94-104, September 1991
3
Pervasive Computing (Cont.)
Smart space
Various
Wearable and embedded computer,
Smart phone, PDA, Notebook, PC, Server
Various
interconnected devices
connectives
Peer-to-peer, client-server, MANET, WLAN, 3G and 4G
Seamless integration of networking and computing
capabilities within human environments
Pervasive computing is about making our lives
simpler
2009/04/10
4
GPS Satellite
Ubiquitous Environment
GPS Receiver
GPS
information
Wireless AP
AP
signal
Internet
Servers
AP
signal
GSM
GPS
/ 3G
information
signal
GSM / 3G
signal
RFID
RFID Tag
information
3G Base Station
RFID資訊
2009/04/10
RFID Antenna
5
GPS Satellite
Ubiquitous Environment
Servers
AP
signal
GPS
information
Wireless AP
AP
signal
Internet
Network
Status
GSM
GPS
/ 3G
information
signal
Agents
Location
information
GSM / 3G
signal
RFID
information
3G Base Station
RFID資訊
2009/04/10
RFID Antenna
6
Scenario-1
五月天的下午,開著冷氣您乘坐在舒適豪華的Jaguar愛車
裡,優雅舒適地徜徉於信義計劃區網狀的市區道路中,意
氣風發的您不必為了惱人的單向、雙向行車問題而迷路或
為了工作分派的問題而煩惱,因為您的車載電腦更勝於您
美麗的女助理。“哈囉”,隨著熟悉的聲音,它提示您:
30分鐘後您在台北101世界超高摩天大樓將有一個約會,
並顯示從目前位置前往的路線圖,車程時間為20分鐘。您
告訴它說“瞭解”,並結束對話。
“哈囉”,它又提醒您,走另一條路,車程可能會多個10
分鐘,但您可以順道買一杯您喜歡的StarBuck拿鐵咖啡。
“謝謝您”,您爽朗的回答,您喜歡這個超人性化的提議。
但您可能會因此而遲到,怎麼辦呢?不用擔心,它(您的夥
計)早就為老哥您設想週到地送出一個簡訊給您的約會對象,
2009/04/10
您可以從容不迫地到達目的地就好!不必為了些微的耽擱 7
Scenario-2
一大早,電腦會知道你起床了,於是啟動
咖啡機
你一進入浴室,蓮蓬頭就自動開啟,調到
你最喜歡的水溫
等你開始走下樓,事先裝好土司的烤麵包
機就開始加熱,把早餐依你喜歡的方式煮
好
打開冰箱,機器會提醒你,沒有牛奶了,
而且罐子裡的涼拌包心菜絲已經過期,應
該扔掉了
2009/04/10
http://h50007.www5.hp.com/enterprise/member/info/0403_rfid/rfid01-02.asp
8
Pervasive Computing (Cont.)
How to access information?
Computer-centric
Context-aware
Human-centric
2009/04/10
9
Context-aware
Context-aware means that one is able to use context
information
A system is context-aware if it can extract, interpret and use
context information and adapt its functionality to the current
context of use
Definition of context:
Context is any information that can be used to characterize the
situation of an entity
An entity is a person, place, or object that is considered relevant to the
interaction between a user and an application, including the user and
application themselves
2009/04/10
Context-Aware Applications Survey: http://users.tkk.fi/~mkorkeaa/doc/context-aware.html
10
Example of Context
identity
spatial information - e.g. location, orientation, speed, and
acceleration
temporal information - e.g. time of the day, date, and season of the
year
environmental information - e.g. temperature, air quality, and light
or noise level
social situation - e.g. who you are with, and people that are nearby
resources that are nearby - e.g. accessible devices, and hosts
availability of resources - e.g. battery, display, network, and
bandwidth
physiological measurements - e.g. blood pressure, hart rate,
respiration rate, muscle activity, and tone of voice
activity - e.g. talking, reading, walking, and running
schedules and agendas
2009/04/10
11
Agenda
Introduction
Pervasive
Computing
Context-aware
Context-aware Service
Ubiquitous
Phone System (UPS)
Context-aware Path Planning (UbiPaPaGo)
Conclusion
2009/04/10
12
Ubiquitous Phone
System (UPS)
Motivation
Dual-mode feature-rich business smart phone
has more and more popular.
Besides tri-band UMTS/HSDPA and quadband GPRS/EDGE/GSM, most of these smart
phones also support WiFi, Bluetooth, and GPS
connectivity.
However, use of these feature-rich smart
phones still relies on users’ attention with
complicated configuration, either priori or on
2009/04/10
14
Motivation (Cont.)
For general naïve users, more intelligent,
human-centered services and simplified user
interfaces are expected
2009/04/10
15
Scenario
老闆突然有事要取消meeting,希望能自動撥號
給實驗室任何一位研究生
有空接聽電話的人
費率最低
2009/04/10
16
Problem Definition
How to immediately achieve users’
requirements by context information
How to efficiently help users make explicit
decisions from varieties of communication
ways
How to help the caller contact with the callee
whose personal smart device is out of use
when emergency call is incoming
2009/04/10
17
Solution Approach
Use context digest model and inference model
to achieve users’ requirements by contextawareness
Use inference model to explicitly connect the
most adaptive communication way for users
Use social model to help the caller contact
with the callee whose personal smart device is
out of use
2009/04/10
18
Social Network
Small-world phenomenon
The
six degrees of separation concept
Social network is defined as a social structure
made of nodes which are generally people or
groups
Social network can reflect the relation
between two individuals
2009/04/10
19
Architecture of UPS
2009/04/10
20
Models
Context Digest Model
Ontology
tree
Inference Model
Social Model
2009/04/10
21
Context
Digest Model
Context Digest Model
Status
Context
Location
Context
Schedule
Context
Net. Status
Context
…
Context Information Management Module
Context Acquisition Module
Context Information
Personal
Data
Sensor
Data
Personal
Data
Sensor
Data
Status
Data
Status
Data
Location
Data
Location
Data
Clients
2009/04/10
22
Context Information
Static context
Static
context is the fundamental attribute
users’ profile and preference, device’s profile
Dynamic context
Dynamic
context presents the instant information
user’s presence status and location
Auditing context
Auditing
context is the statistical output by
operating
2009/04/10
phone call logs, location logs and event logs
23
Inference Model
Pre-define intelligent communication policies
with SPARQL (recursively, SPARQL Protocol
And RDF Query Language)
Event-oriented
Rule-based
engine
Reach personalized service by the preference
setting of users
2009/04/10
24
Social Model (1/2)
Social model is designed to assist the caller c
to contact with the user u through the rely
node r when u’s phone is out of use.
Social network is built by the phone call
records
R
R
u ,b
u ,bi
bi ,u
Max ( R two
R
is the weight of relation between
individuals
ωu,bi
i
u,x
x ,u
)
ω is weight of two-individual relation.
R is the number of phone record
Ru,b is indicated as the record of u’s calling to bi
,
x bi
2009/04/10
25
Social Model (2/2)
Prelation
is a rank of social relation between two
individuals
ωu,bi and degree of relation between u and gj (gj: the group in
u’s buddy list)
Ptarget
is an output of social model for contact with the
person by computing the whole statistical data
Ptarget location Plocation relation PrelationWhere location relation 1
Ptarget is the probability of c communicating with u by r
Plocation is the probability of u and bi being in the same location
Prelation is the rank of social relation between bi and u
αlocation is the weight of Plocation to affect Ptarget
α
is the weight of Prelation to affect Ptarget
26
2009/04/10 relation
Intelligent Service of UPS
Ubiquitous Call Service
AnyCall Service
Emergent-contact Service
2009/04/10
27
Intelligent Service of UPS - Ubiquitous
Call Service
Ubiquitous call service is aimed to provide a
novel human-centric phone call service.
When a user desires to call a buddy from his
contact list, he just clicks on the buddy’s name.
The call agent on the user’s PDA phone will
communicate with the service providing server
and provide the most appropriate service to
the user
VoIP
2009/04/10
call, a GSM call, or a short message
28
Intelligent Service of UPS - Ubiquitous
Call Service
Ubiquitous call service automatically choose
the right communication channel to connect to
the callee based on context information like
reachability, call rate, user preference
UbiCall also provides intelligent feedback
service when the callee is not available
such
as when to call back according to callee’s
calendar, whether to automatically re-dial when
the callee becomes available.
2009/04/10
29
Intelligent Service of UPS- AnyCall
Service
AnyCall is similar to the anycast service in IP
networks
It
provides the user to call the most appropriate buddy
within a group
Consider an emergent scenario
where
the user needs to call anyone in his family group to
inform an accident. In such an emergent situation, any
buddy from the family group will be able to help the caller.
AnyCall provides the user an interface to just a
single click on the group name, it will connect the
phone call to one of the group members who is
available at that time to answer the phone.
2009/04/10
30
Intelligent Service of UPS- Emergentcontact Service
The emergent-contact service helps the caller
contact with a third party from callee’s contact
list or a phone at a location when the callee is
not reachable.
social,
calendar and location information are used
to reason the most appropriate third party.
2009/04/10
31
Implementation
Experimental Environment
Middleware
2009/04/10
32
Experimental Environment
Service Providing Servers
Context Management Server
Telecommunication
Network
Agents
Inference Server
Wireless
Network
2009/04/10
Internet
Wireless
Network
33
Middleware
Web Service
SOAP
Ontology tree
OWL
RDF
WSDL
Agents
Encapsulating SOAP Message
XML, DTD, RDF Triple Storage, OWL Semantic Definition
Context Acquisition or Communication
2009/04/10
34
Implemental
achievement
Learn2.0 project
Dormitory
members
hushpuppy
Septhiorth
UbiCom
Group
Web2.0
Group
Messaging Server
Internet
VoIP Server
& Agents
Context Management Server
Engineering College A
Web2.0
Group
2009/04/10
zqq
Lunsrot
In EA315
E-learning
Group
In EA105
35
Ubiquitous Call Service
During Lunsrot’s surveying papers, he has
new thoughts about Web2.0 and he wants to
Lunsrot
Lunsrot
discuss with hushpuppy
In EA315
?
In EA315
Inference
hushpuppy
hushpuppy
In the Library
In the Library
2009/04/10
36
AnyCall
Septhiorth wants to discuss with anyone who
joins Learn2.0
project
Elearn2.0 Proj
hushpuppy
Septhiorth
?
Inference
In the Library
Elearn2.0 Proj
Lunsrot
hushpuppy
In EA315
zqq
In EA105
Septhiorth
In the Library
Lunsrot
In EA315
zqq
2009/04/10
In EA10537
Verification
of Social
Model
Find 22 experimenters
and select
one(1/7)
who
knows others of them
Set the relation
degree of the
chosen one from
No.
Nickname
Relation (Group)
b
masa
Myself
his preference
setting
b
yuwen
Graduate Mate
0
Myself
Record the
phone
call records
of 22
b
puzi
Graduate Mate
1
Family
b
calais
Graduate Mate
experimenters during one month
2
Dorm Mate
b
iamshyang
Graduate Mate
3
Friend
Record the
location
logs Mate/University
of
the chosen
one
b
bluejam
Graduate
Mate/Dorm Mate
4
UniversityMate/University
Mate
b
zqq
Mate
during one
month
and Graduate
calculate
statistics
of logs
5
Graduate Mate
…
Record locations
of 22
experimenters
during
6
Younger
Graduate Mate
7
Graduate Mate for Doctor's degree
some week after
that
month
8
Advisor
1
2
3
4
5
6
7
2009/04/10
38
Classmate in graduate school
Roommate
Verification of Social Model (2/7)
iamshyang
calais
Classmate in university
bluejam
puzi
RecordAdvisor
the phone call records of 22
experimenters during
one
month
zqq
yuwen
sigwa
rhhwang
des33
hopper
septhiorth
masa
hushpuppy
Lunsrot
Younger classmate
in graduate school
yuan
yanmin
Mei
Nick
Senior classmate
in graduate school
2009/04/10
: User
:Group Name
hsg
Dad
sue
Brian
Family
Friend
: No records during a period
39
Experimental
Successful case
Masa
attends group meeting in EA105 from 16:00
to 18:00 on every Tuesday. It is a quite regular
activity and he attends the meeting as usual on
the fifth week.
Table shows the possibility of suggesting each
contact as well as a location if that location has a
phone.
2009/04/10
40
2009/04/10
41
Experimental
Fail case
On
the Friday of the fifth week, masa attends a
BBQ party from 18:00 to 22:00 which is not a
regular activity.
The BBQ party was held in Orange Grange where
masa never been there during the past four weeks.
Furthermore, masa does not put this event in his
calendar.
2009/04/10
42
2009/04/10
43
Experimental
Puzi is the emergent contact suggested by the
system due to his high intensity of social relation with
masa.
However, Puzi is preparing a presentation in EA315
at that time.
Bluejam has the second highest possibility and is
actually also in the BBQ party. Therefore, if the
system provides a list of possible candidates instead
of just one, the user could have chance to find masa
through bluejam.
2009/04/10
44
Agenda
Introduction
Pervasive
Computing
Context-aware
Context-aware Service
Ubiquitous
Phone System (UPS)
Context-aware Path Planning (UbiPaPaGo)
Conclusion
2009/04/10
45
Scenario
Mary has a class at 13:30 PM but she is late. She
leaves library and uses PDA to connect online elearning system and walks to classroom as soon as
possible
Therefore, Mary hopes to find the shorter path
without breaking off online e-learning system and
access printer service.
Application
Path plan in Navigation System
Requirement
2009/04/10
She needs to hand in an hard copy assignment in class, so she
also needs printer to print out her assignment on her moving way.
Signal strength, Bandwidth, shorter path, printer service
46
46
Problem Definition
Based on user’s requirement and available context,
how to plan path?
Path planning problem
Find
a optimal path that maximizes the user-required
fitness function
Goal
Maximum
bandwidth, signal strength
Minimum distance
Available service
2009/04/10
47
Design Idea
Phase 1: Create a trajectory map using Spatial Conceptual
Map (SCM)
Modify the parameters of SCM
Modify the partition rule of Way Element Areas (WEA)
Characteristic Function
Phase 2: Plan optimal path using Genetic Algorithm
Initialization
Fitness function
Parent selection
Reproduction
Coding or Representation
Crossover
Mutation
Convergence
2009/04/10
When to stop
48
CCU Campus Map
2009/04/10
http://www.ccu.edu.tw/eng/GIS/ccumap.swf
49
Spatial Conceptual Map (SCM)
Representation
AP5
AP7
α24 α36 α37 α38 α48 α60
α25
α49
O3
α26
N
W
α51
α17
AP1
α16
O1
α1
α4
α5
α15
α3 α7
α10
α11
α2
O2
α72
α54
α74
α55
α63 α64 α65 α75
α56
α76
α30
O5
α32
AP8
O8
α77
α58
α78
α14 α21 α22 α23 α35 α45 α46 α47 α59
α66 α67 α68 α79
α34
AP2
2009/04/10
O9
α71
α73
α31
α13
α9
O7
α29 α39 α40 α41 α53
α12 α18 α19 α20 α33 α42 α43 α44 α57
α8
α70
α52
α28
α69
AP3
S
α6
α62
α50
O4
α27
E
α61
O6
AP6
AP4
CCU Campus
AP9
50
MOAC Representation
α18
α18
α19
Co (α18)
W
α20
α21
α22
α23
α24
α25
α26
α27
α28
α29
2009/04/10
α19
α20
α21
α22
α23
α25
α24
α26
α27
α28
α29
E
Co (α19)
Co(O2)
W
E
Co (α20)
Co (α21)
W
E
Co (α22)
W
E
Co (α23)
Co (α24)
N
S
Co (α25)
N
S
Co (α26)
Co(O3)
N
S
Co (α27)
Co(O4)
N
S
Co (α28)
N
S
Co (α29)
51
Characteristic Function
Co(Oi)={c1=id c2=name, c3=location,…}
Ex:
Co(O1)={c1=B1, c2=library, c3=α8}
Co(αi)= {c1=distance, c2=AP list,
c3=available service…}
Ex:
Co(α2)= {c1=5, c2={AP1 , AP2},
c3={printer, fax}}
2009/04/10
Co(APi)= {c1=SSID, c2=available
bandwidth, c3=signal strength,…}
Ex:
Co(AP )= {c1=3com, c2=4, c3=5}
52
Step 2: Plan optimal path using
Genetic Algorithm
Initialize chromosomes
Crossover
Mutation
Evaluate fitness function
α24
α48
α69
Node: Object and
crossover
α70
α51
α10
α5
α29
α53
α31
α55
α33
α57
α64
α75
α1
α12
α19
α3
2009/04/10
α14
α35
α46
α59
53
α79
Initial population
Initial population is very important because it
affects the convergence speed and the quality
of solution.
Random initialization possible leads to large
computing overhead and loop path
Heuristic initialization is hard to find global
optimal.
2009/04/10
54
Initial population
We adopt a probability network approach which combines the
features of random and heuristic initializations to generate
initial candidate paths in the gene pool.
This process is repeated from the starting node to the goal
node
A gene in a locus randomly selected from the set of forward direction
nodes which are connected with the node of the locus number and not
visited before
Easily to achieve destination node
Avoid loop problem
The selected gene n put in the mth locus of the chromosome
The nodes x which are not passed through
randomly select one node from the set of nodes which are connected
with x and put it in the xth locus
57
2009/04/10
Initial population
Goal
Randomly
select k paths
Guarantee to destination node
Avoid loop problem
2009/04/10
58
Example-1
Ex: Route 19 -> 51 (O5-> O7)
locus numbers
α24
α48
10 12 14 19 24 29 31 33 35 46 48 51 53 55 57 59
α51
Chromosome
29 14
35
33 29
53
57 46
59 24 48
α29
α53
α31
α55
α33
α57
51 53 55 57
α10
α12
α14
α19
α35
α46
α59
Route 19-> 33 -> 57 -> 55 ->53 ->51
2009/04/10
59
Example-2
Ex: Route 19 -> 51 (O5-> O7)
locus numbers
α24
α48
10 12 14 19 24 29 31 33 35 46 48 51 53 55 57 59
α51
Chromosome
12
19
35 33 48 24 29
31 46 59
51 53 55
57 33
α29
α53
α31
α55
α33
α57
57
α10
α12
α14
α19
α35
α46
α59
Route 19-> 33 -> 31->29->24->48->51
2009/04/10
60
Fitness Function
Fitness function of the chromosome measures the
objective cost function
Signal
strength (S)
Available Bandwidth (B)
Path Length (D)
Available Service (S)
The relative values of ws,wb,wd, ,wa represent the
aggressiveness of the cost function
2009/04/10
Satisfy user’s requirement
61
Fitness Function
signal αi
signal αi , signal αi threshold s
(threshold s signal αi ),0 signal αi threshold
, signal αi 0
bandwidth
αi
bandwidth αi , bandwidth αi threshold b
(threshold b bandwidth αi ),0 bandwidth
, bandwidth αi 0
αi
s
threshold
b
0, if required server is not available
S i
1, if required server is available
2009/04/10
62
Fitness Function
s * ( i ) 1
| signal ( i ) u s |
u s ls
d * ( i ) 1
| dis tan ce( i ) ld |
u d ld
b * ( i ) 1
| available _ bandwidth( i ) ub |
ub lb
n
F ( ws
s * ( )
i
i 1
n
n
wb
ws wb wd wa 1
2009/04/10
b * ( )
i
i 1
n
n
wd
d * ( )
i
i 1
n
n
) w a ( Max ( f ( S i )))
i 1
63
Fitness Function
Route 5-> 10 -> 29-> 31
n
F ( ws
s( )
i
i 1
n
n
wb
b( )
i
i 1
n
n
wd
d ( )
i
i 1
n
n
) w a ( S i )
i 1
AP5
N
E
W
AP3
S
α17
AP1
α16
O1
α5
α15
α6
α10
α29
α30
α31
O5
O2
64
2009/04/10
AP6
Reproduction
The best fitness chromosome is coped into the
gene pool
Crossover
Mutation
2009/04/10
65
Crossover
Crossover operation combines two chromosomes
(called parents) to produce a new chromosome
(called offspring)
our crossover operation is carefully designed to
avoid the path looping problem
Two parent chromosomes are randomly selected
from the gene pool.
If the genes of the locus of two parents are the
same, then just copy the gene to the offspring.
Otherwise, we will prefer to select the gene (node)
that has not been appeared (visited) before.
2009/04/10
66
Example -crossover
Offspring: 19-> 33 -> 31->29->53->51
Ex: Route 19 -> 51 (O5-> O7)
locus numbers
α24
α48
10 12 14 19 24 29 31 33 35 46 48 51 53 55 57 59
α51
Parent 1
29 14
35
33 29 53 33
57 46 59
24 48 51 53
55
α29
α53
α31
α55
α12
α19 α33
α57
α14
α35
57
α10
Parent 2
2009/04/10
12
19
35 33 48 24 29
33
53
29
31 46
31
59 51 53 55 57
51
33
57
α46
67
α59
Mutation
Avoid local optima by preventing the
population of chromosomes
Randomly select one node in the route path as
the mutation gene
2009/04/10
68
Example - Mutation
Ex: Route 19 -> 51 (O5-> O7)
locus numbers
α24
α48
10 12 14 19 24 29 31 33 35 46 48 51 53 55 57 59
α51
Chromosome
29 14
35
33 29
53 33 57
46 59
24 48 51
53 55
α29
α53
α31
α55
α33
α57
57
α10
35
Before
After
2009/04/10
Route 19-> 33 -> 57 -> 55 ->53 ->51
α12
α14
α19
α35
α46
α59
Route 19-> 33 -> 35 -> 46-59-57-55-53-51
69
Implementation -1
User connects to Service Provider and uses UbiPaPago Service
2009/04/10
70
Implementation -2
UbiPaPaGo Service Provider receives the request from user
2009/04/10
71
Implementation -3
2009/04/10
The path planning result
72
Experimental Results -1
Results
2009/04/10
of UbiPaPaGo
Example map with optimal path
73
Experimental Results -2
Average fitness value under various
population sizes
0.9
0.88
0.86
2009/04/10
Random
UbiPaPago
Optimal
0.84
Number of Generation
0
10
90
80
70
60
50
40
30
20
0.82
10
Average Fitness Value
74
Agenda
Introduction
Pervasive
Computing
Context-aware
Context-aware Service
Ubiquitous
Phone System (UbiPhone)
Context-aware Path Planning (UbiPaPaGo)
Conclusion
2009/04/10
75
Conclusion-1
UPS is a context-aware intelligent
communication system
Unify
various intercommunicated interfaces
Intelligently and immediately help human achieve
required services
Integrate a communication system with social
network
2009/04/10
76
Conclusion-2
UbiPaPaGo is a context-aware path planning
mechanism
It
takes into account multiple requirements and
context of users and environment when planning
the best-fitting path
Experimental results show that the proposed
UbiPaPaGo efficiently finds the best-fitting path
which guarantees RSS, bandwidth, available
service and shorter distance simultaneously
2009/04/10
77
Future Works-1
UPS
Handover
between telecommunication network
and IP network
Emotion for presence context can immediately
respond to users’ degree of satisfaction without
users’ feedback and make UPS provide more
adaptive services
Other social behaviors can help strengthen social
network and tune up social model
2009/04/10
78
Future Works-2
UbiPaPaGo
Unknown
destination
Vertical handoff between AP and BS
Resource reservation along the path in advance to
guarantee quality of service of the path
Security and privacy issues
2009/04/10
79
Q&A
Thank You