Transcript Document

Pervasive Computing研究群
研究能量與研發成果
Members and Research Directions
–
Sensor networks

–
WLAN

–
邵家健、彭文志
Ubiquitous sensor/actuator infrastructure

–
曾煜棋、王國禎
Mobile peer-to-peer service grid

–
曾煜棋、王國禎
Mesh networks

–
曾煜棋、王國禎、黃俊龍
邵家健
Sensor data management and mining

彭文志、黃俊龍
研發成果
A Cluster-based Energy Efficient Routing
Algorithm in Mobile Wireless Sensor Networks
Step 1. Select one hop neighbor
nodes closer to the anchor
Energy consumption vs. number of nodes
Step 2. Choose the node with the
maximum energy level from the
selected nodes
Latency per packet vs. number of nodes.
A Deferred-Workload-based Dynamic Voltage
Scaling Algorithm for Hard Real-Time Systems
An illustration of dwDVS
CPU energy consumption
(Normalized)
Static
laEDF
DRA
dwDVS
Bound
120
100
80
60
40
20
0
1
2
3
4
5
6
7
8
9
10
WCET/BCET ratio
Effect of WCET/BCET ratio on
energy consumption
CPU energy consumption
(Normalized)
Static
laEDF
DRA
dwDVS
Bound
120
100
80
60
40
20
0
10
20
30
40
50
60
70
80
90
Worst-case utilization (%)
Effect of worst-case utilization on
energy consumption
100
A Power Saving MAC Mechanism for VoIP over
IEEE 802.11e WLANs
VoIP over WLANs system architecture
Power saving mechanism in PSM-V
A Power-Efficient MAC Protocol for VoIP Traffic
over IEEE 802.11e WLANs
QSTA 1
QSTA 2
QSTA 1
QSTA 2
Proposed power-efficient polling scheme
…..
QAP
PIFS
Beacon
SIFS
....
SIFS
SIFS
QoS CFPoll
SIFS
PIFS
ACK
Data
....
Beacon
....
QoS
Null
QSTA
TXOP 1
Controlled Access Phase (CAP)
Contention
Period (CP)
Polling scheme comparison
CAP
Scheme
Round-robin polling
(RRP) scheme [8]
On-demand polling
(ODP) scheme [4]
Power-Efficient Polling
(PEP) scheme (Proposed)
Characteristics of polling
scheme
Static
Dynamic
Dynamic
Complexity of
implementation
Easy
Medium
Medium
Normalized power
consumption
Highest
Medium
Lowest
Aggregate throughput
Higher
Lower
Almost the same as
RRP
Average end-to-end delay
Lowest
Highest
Medium
Emergency Guiding System by
Wireless Sensor Networks
Emergency Guiding Scheme
Water toward low spot
 Hazardous regions
 Distributed adjust weight
to find escape path

Monitoring
Tree Reconstruction
Support reliable reporting scheme,
when emergencies occur
 Dynamically recover the failure links
 Low cost and quick convergence

Guidance Interface
Protocol Stack
Applicationlevel UI
Deployment
Network
initialization
Guidance
initialization
Query
GUI
Users part
Sensors part
Application
layer
Tree
Reconstruction
Sensor task
Network
layer
Symmetric link
detection
Tree
maintenance
HELLO
Report
Physical layer and Data link layer
Guidance
service
EMG
The Deployment and Dispatch Issues of
Mobile Wireless Sensor Networks
Indoor Sensor Deployment
k-covered Sensor Deployment
• Characteristics
- Arbitrary-shaped obstacles in the field
- Arbitrary relationships of rc and rs
- Fewer sensors required for deployment
- Sensor dispatch to reduce deployment cost
>> Max-weight max-match problem
rs
rc
• Characteristics
- Deployment for multi- level coverage WSN
- Arbitrary relationships of rc and rs
- Fewer sensors required for deployment
- Distributed sensor dispatch algorithms
>> greedy-based & pattern-based schees
3 rs
rc
obstacle
rs
1 2
4 3
iMouse System
• Characteristics
- Implementation of “mobile” sensor
- Provide WSN-based surveillance service
- Combine adv. of both WSN and traditional
surveillance systems
Multi-type Sensor Dispatch
•Problem
- How to dispatch sensors so that events
can be detected on time & total energy
consumption can be minimized
{a, b}
{b, c}
WLAN
card
Stargate
Static sensor
b
b
a
WebCam
a
c
c
{a, c}
Mobile
sensor
Lego car
{a, b}
{b, c}
Event “a” is not detected
{a, c}
All events are detected
Coverage of a Wireless Sensor Network
without Location Information
• Goal
– Determine whether the sensing region of each sensor is sufficiently
covered by k other nodes without location information
– Provide comparable results to the location-based algorithm
S6
S5
S7
S1
S3
S2
S4
S0
S0
S3
S4
S2
S1
S5
S6
S7
Real Network
SS77
S
S2
SS44
S6
S6
S5
S5
S1
S33
S3
S1
S0
S0
S0
S33
S1
SSS444
S2
S2
SS77
S7
S5
S6
Location Management for Object Tracking
in Wireless Sensor Networks
Tree-based location management scheme that consists of
(1) The update and query mechanisms
(2) The tree construction algorithms
Two Location Management Schemes
The Beacon Movement Detection Problem
in Wireless Sensor Networks for
Localization Applications
If beacon sensors are moved by accident, the localization error will be increased seriously.
•System model:
A Noise-Tolerant Indoor Positioning
Method by Signal Scrambling
Design Guidelines:
• Propose a tracking scheme to improve accuracy of various localization algorithms
• Temporal dependency is used to enlarge real-time sample space
• Spatial dependency is used to select a better location
System Flow
Viterbi-like Location Selection Module
Quick Convergecast in ZigBee/IEEE 802.15.4
Tree-Based Wireless Sensor Networks
Problem formulation
•
•
•
Convergecast is a fundamental operation
in wireless sensor networks
This paper defines a minimum delay
beacon scheduling problem for quick
convergecast in ZigBee/IEEE 802.15.4
tree-based wireless sensor networks
We prove that this problem is NPcomplete.
Current results
•
•
Our formulation is compliant with the lowpower design of IEEE 802.15.4.
We propose
–
–
•
Optimal solutions for special cases
Heuristic algorithms for general cases
Simulation results show that the proposed
algorithms can indeed achieve quick
convergecast
Energy Efficient Algorithms for Mobile
Sensors
• Sensor dispatching problem in collaborative network
Mobile sensors
achieve advanced
detection
Static sensors detect
the event
• Impact of load balancing
Remaining sensors bear
heavier load
This sensor is dead!
85
45
95
70
0
85
20
0
40
1. Always minimize the total cost
100 100 100
Total:300
Total :225
Usage:75
70
70
70
Total :155
Usage:70
50
40
40
Total :60
Usage:95
40
20
30
2. Consider load balancing issue
Total :210
Usage:90
Total :130
Usage:80
Total :90
Usage:40
ROUND 1
ROUND 2
ROUND 3
Exploiting Data Coverage for Approximate
Query Processing in Wireless Sensor
Networks
• Data Coverage
SELECT AVG(S.Temperature)
FROM Sensor S
WHERE S.Location IN region
• Sensors with correlated
readings are clustered together.
• We pick a representative out
from each cluster.
• The representatives will
answer queries; the other
sensors only sense the
environment and do not respond.
• Data-Covering Problem
Input: set of sensors S, clustering criteria
ε
Output: set of representatives R
Constraint: minimize the size of R while
keeping every sensor is clustered.
sink
sink
user
user
query
approximate
approximate
answer
answer
Filtering Faulty Readings to Improve Data
Accuracy in Sensor Networks
• Byzantine Problem (trust degree is equal)
Traitor
o
x
o
Patriot
v.s.
x
o
x
x
o Stable
No cheat
Unstable
cheated
Traitor
Hybrid Program Verification for AFSM Based
Sensory-Motor Control
•Use Binary Decision
Diagram (BDD)
verification technique (for
program) to check
automatic robot behaviors
•Based on Rodney Brooks’
Augmented FSM(AFSM)
model
Cleaning Crew
Interacting AFSM Modules
•Described by
UNITY specification
language
•Can be verified by
BDD-based model
checker
•Verify obstacle avoidance
behaviors of roving robot
Transform Experiment from continuous
domain to discrete domain
Resilient Application Layer Multicast
Tailored for dynamic Peers with Asymmetric
Connectivity
•Application Layer Multicast (ALM)
•Minimize and equalize transport latency to all peers
•Dynamic Peer Behaviors
•Unpredictable join/leave
•Asymmetric connectivity
•Limited upstream bandwidth
Multiple Multicast Trees
Application layer Multicast System
Demand of Helper
Major Projects

ZyXEL Inc.: “802.11e無線網路下的傳輸品質與快速換手之研究 (QoS and Fast
Handover in 802.11e WLAN)”, 2005.03-2006.02.

工研院/學研計畫: "Communication Protocols for Wireless Access Networks".
(2005.01~2005.12)



後卓越計劃(Program for Promoting Academic Excellence of Universities II), NSC:
"Advanced Technologies and Applications for Next Generation Information
Networks" 下一世代資訊通訊網路尖端技術與應用(2004.04~2008.03).
– 分項計畫三: B3G All-IP Wireless Network Technologies, 後三代全IP無線網路
技術
– 分項計畫四: Wireless Ad Hoc and Sensor Networks Technologies, 無線隨意
及感測網路技術
國科會: “藍芽個人無線區域網路上通訊議題之設計實作與分
析”(2003.08~2006.07)
無線感測網路之動態定位技術, National Science Council, August 1, 2004 - July
31, 2007
Prof. Kuochen Wang
(王國禎教授)

B.S., NCTU-Control Eng., 1978

M.S., Univ. of Arizona-ECE, 1986

Ph.D., Univ. of Arizona-ECE, 1991

Senior Engineers, Directorate
General of Telecommunications,
1980-1984

Professor, NCTU-CS, 1999 ~

Research projects

Areas of research interests
–
Wireless networks and mobile
Computing

–

–
NCTU-MediaTek Project: Low power,
handover and QoS schemes in
heterogeneous wireless networks
–
NSC Project: Dynamic localization in
wireless sensor networks
Sensor networks, ad-hoc networks, and
mesh networks
–
Power-aware computing and
communications
Network reliability and security
–
–
–
Journal papers: 22
Conference papers: 47
Book Chapters: 1
Publications
Prof. Yu-Chee Tseng
(曾煜棋教授)

B.S., NTU-CSIE, 1985

M.S., NTHU-CSIE, 1987

Ph.D., Ohio State University-CIS, 1994

Professor, NCTU-CS, 2000~






Chief Executive Officer, ITRI-NCTU Joint
Research Center, 2005~
Chairman, NCTU-CS, 2005~
“Distinguished Alumnus Award”, 2005,
The Ohio State University
Distinguished Research Award (two
times)
Distinguished EE Professor Award, The
Chinese EE Institute, 2005




Areas of research interests
–
Wireless Network
–
Communication Protocol
–
Mobile Computing
–
Network Security
–
Wireless Sensor Network
–
Wireless Mesh Network
–
Wireless VoIP
–
Distributed System
–
Parallel Processing Publications
International journal: 91
International conference: 99
Book Chapters: 12
Patents: 2 granted, 5 pending
Prof. Wen-Chih Peng
(彭文志教授)

B.S., NCTU-CSIE, 1995

M.S., NTHU-CSIE, 1997

Ph.D., NTU-EE, 2001
Assistant Professor, NCTU-CS, 2003/8~
A member of the IEEE

Research interests



–
Data management and mining in sensor networks
–
Mobile data management
–
Data mining/databases
Publications
– International journal: 8
– International conference: 14

Email:
[email protected]
Prof. Jiun-Long Huang
(黃俊龍教授)





Associate Professor, NCTU,
2005–
Ph.D., NTU EE, 2003
M.S., NCTU CSIE, 1999
B.S., NCTU CSIE, 1993
Research interests
– Mobile data management


Dependent data broadcast
On-demand data broadcast
– Mobile Internet


Cache relocation
Transcoding proxy
– Sensor network


Publications
– Journal papers: 5
– Conference papers: 17
Email: [email protected]
Prof. John K. Zao
(邵家健教授)








Associate Professor (NCTU),
2004 –
Ph.D. (Harvard), 1995
Senior Member, IEEE, 2001
Senior MTS (BBN), 1994–2002
Principal MTS (BBN), 2002–
2003
Chairman, Security Policy Task
Force, DARPA Information
Assurance (IA) Program, 1999–
2000
Member, US Army Task Force
XXI Tactical Internet Graybeard Panel, 1996–1997
Co-founder, SecurKey Inc.
(Canada), 1987–1990

Research interests
– Pervasive Sensor-Actuator Systems



Autonomous Sensor/Actuator
Assembly
Model-based Software Specification
& Implementation
Operational/Functional Component
Coordination
– Infrastructure-less (P2P) Service
Security



Publications





P2P Security Policy Management
P2P Service Security Enforcement
Journal Papers : 2
Conference Papers : 7
Internet Draft : 3
Patents : 2
Email: [email protected]