Transcript wireless mesh networks

Wireless PAN, LAN and MAN研究群
研究能量與研發成果
Members and Research Directions
– Sensor networks
 曾煜棋、陳 健、趙禧綠、王國禎、簡榮宏、易志偉
– WLAN
 曾煜棋、趙禧綠、王國禎、簡榮宏、曾建超、王協源
– Mesh networks
 曾煜棋、陳 健、趙禧綠、王國禎、簡榮宏、易志偉
– WiMax
 陳健、趙禧綠、簡榮宏
研發成果
A Cross-Layer Control Scheme for VoIP
application over 802.11e Wireless Local
Area Networks
Cross layer VoIP over 802.11e WLAN
Policy based 802.11e Network
0
• Motivation:
Centralized admission control scheme for
802.11e WLAN.
• Mechanism
Modify RADIUS message to carry
Service Level Agreement (SLA)
• Classification:
Classify by client can be simpler than by flow
Cross-layer VoIP Application
Application Layer
UDP
Transport Layer
IP
Network Layer
IEEE 802.11e MAC Protocol
Data Link Layer
Physical
Physical Layer
A
LPC
5.6kbps
B
GSM-8K
13.2kbps
C
GSM-16K
26.4kbps
D
RSSImax
G.711
64kbps
• Motivation:
Let VoIP adapt to time-varying wireless
channel condition.
• Mechanism
Select VoIP codec according to current RSSI
• Measurement Metrics:
One-way delay, Mean Opinion Score (MOS)
A Medium Access Protocol for Multi-Channel
Multi-Interface Wireless Mesh Network
B
A
C
D
RTS
CTS
CTS
Wireless Mesh Network
• Let APs connect to Internet without
wired connection
• Utilize multi-channel and multiinterface to increase network capacity
• The 802.11 MAC protocol doesn’t
support multi-channel and multiinterface
DATA
Channel 2
DATA
Channel 1
RTS
Collision
Multi-channel hidden terminal problem
3
3
1
A
2
C
B
Fixed interface
A
3
3
A
D
Switchable interface
Hybrid channel assignment
An Implementation of IEEE 802.16e
General Handover Emulator
Emulation Topology
•To implement an IEEE 802.16e
emulator for further research and
application development.
• IEEE 802.16d, IEEE 802.16e
Implement Components:
• MAC layer frames
• Network layer frames
• Neighbor Table
• MAC and IP address map
• Data buffering
• Data tunneling
Echo Server
Base Station 2
(target BS)
Base Station 1
(serving BS)
4
3 HO_IN
2 HO_OUT
Internet
HO_IN
HO_OUT
1
MS
802.16 connections
Backbone network connections
Tunneling
A Distributed Time-Slotted
Multi-Channel Protocol
for IEEE 802.11 Wireless Mesh Networks
Fig. Wireless Mesh Network
Motivation
The idea of exploiting multiple
channels is appealing in wireless
mesh networks because of their
high capacity requirements to
support backbone traffic.
Goal
To reduce interference of the
wireless mesh networks by using
multi-channel.
Integrating SIP and IEEE 802.11e to Support
Handoff and Multi-grade QoS for VoIP
Applications
Goal:
1. Guarantee QoS of each admitted
VoIP call and achieve early
resumption of resources even
when handoff occurs.
2. Fairly distribute network resource
and improve channel utilization.
Analysis
1. Analytical Model:
A Y-dimension model.
Take transmission rate into
consideration.
2. Performance Analysis:
Using recursive techniques
based on boundary cases.
Ex: IEEE 802.11e WLAN (Y=4)
A Push-Based VoIP Service for an InternetEnabled Mobile Ad Hoc Network
 An Ad Hoc Network-Based VoIP
Service Platform:
 Integrating MANET and
cellular networks, we propose an
MANET-based VoIP service
platform.
 Possible Applications:
- Indoor: home VoIP system
- Outdoor: provide mobile
VoIP service on bus, train…etc.
 However, connecting cellular
networks incurs charges and power
consumption.
 A new node, called push server,
is proposed.
 A push mechanism is
developed.
System Architecture
Resource Allocation and Packet Forwarding
in Multi-radio Multi-mode Multi-channel
Multi-rate (M4) Wireless Mesh Networks
M4 wireless infrastructure mesh
Graph representation
Much higher throughput
Utilizing M4 benefits and traffic splitting
Linear Programming Formulation
Joint Multi-Channel Link layer and MultiPath Routing Design for wireless Mesh
Network
A WMN is two-tier architecture:
•Forming a wireless backbone
•Providing large coverage
•Offering strong connectivity
•Producing high robustness
An Adaptive Quorum-based Mechanism
for the Clock Asynchronism Problem in
IEEE 802.11 MANETs
The Concept of Quorum:
• Grid-based Quorum
n
n
0
1
2
…
…
n-1
0
1
2
…
…
n-1
n
n+1
n+2
…
…
2n-1
n
n+1
n+2
…
…
2n-1
2n
2n+1
2n+2
…
…
3n-1
2n
2n+1
2n+2
…
…
3n-1
n
n
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
(n-1)*n
…
…
…
…
n2-1
(n-1)*n
…
…
…
…
n2-1
Protocol Design:
n2 beacon Intervals n2 beacon Intervals n2 beacon Intervals n2 beacon Intervals
n2 beacon Intervals
n
quorum interval
0
1
2
…
…
n-1
n
n+1
n+2
…
…
2n-1
2n
2n+1
2n+2
…
…
3n-1
…
…
…
…
…
…
…
…
…
…
…
…
Beacon
Beacon
non-quorum interval
non-quorum interval
n
Beacon
Beacon
(n-1)*n
…
…
…
…
n2-1
Adaptive Attenuation Factor Model
for Localization in Wireless Sensor
Networks
• Adopting a centralized architecture to localize sensor nodes
• Dynamically measuring n and X locally to increase the accuracy of localization
IRN: Initial Reference Node
UN: Unknown Node
Wireless Communication
A
G
B
I 2. Signal Strength
D
E
K
J
3. Neighbor-Signals
Response
C
H
F
1. Neighbor-Probe Request
Fusion Center
An Integrated Call Agent of the
Converged VoIP Network
•Using IN basic call state model (BCSM)
• Unified event trigger
• Mapping VoIP message to BCSM
•Supports:
• H.323, SIP, MGCP, H.248
• Inter domain interworking
NCTU
SIP Proxy
ITRI
SIP Protocol Stack
OpenH323
ITRI
SIP-UA
User
User
GK
CA
O T
O T
O T
User
Registrar
MGC
O T
Global
Global
user
user
ITRI
MGCP protocol Stack
NCTU
RGW
ICA
h323
h323
Call
Call control
control
ICA
dispatcher
dispatcher
mgcp
mgcp
Microsoft
NetMeeting
or OpenPhone
User
SIP
Proxy/
Opengate
Gatekeeper
Components in our ICA
Telephone
Call
Call
table
table
megaco
megaco
siplib
siplib
Protocol
Protocol dispatcher
dispatcher
Network
ICA functional blocks
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
A NEW MODEL FOR OPTIMAL RWA
WITH FIXED-LENGTH TUNNEL
ALLOCATION IN MG-OXC NETWORKS
Multigranularity Optical
Cross-Connect (MG-OXC)
Bundle a group of consecutive wavelength
channels together and switch them as a
single unit on a specific route (tunnel)
Layered Auxiliary Graph
Routing and Wavelength
Assignment (RWA) with tunnel
allocation
Given a set of static lightpath requests,
(a) allocate a set of fixed-length tunnels
(b) find routes from source to destination nodes,
The objective is to minimize the blocking
probability.
Fast Packet Classification Using MultiDimensional Encoding
Multi-Dimension Encoding
Solution:
1. Divide rules into several multidimensional collision-free rule
sets
2. Use these sets to form the new
coding vector to replace the bit
vector
Minimum-Delay and Energy-Efficient
Source to Multisink Routing in Wireless
Sensor Networks
Problem:
• Obtain minimum-delay and energy-efficient
transmission paths under Single-Source to MultiSinks routing scenario in wireless sensor networks
Minimum delay, Large energy cost
Energy efficient, Large delay
Minimum-delay, Energy-efficient
SmartBone: An Energy-Efficient Smart Backbone
Construction in Wireless Sensor Networks
Problem:
• Energy consumed by awaken sensor nodes
• Radio interference of awaken sensor nodes raises
packet retransmission resulting additional energy
consumption
Flow-Bottleneck preprocessing
Dynamic Density Cutback
SmartBone algorithm:
Shared Risk Link Group (SRLG) Diverse
Routing and Channel Assignment in
Survivable Wireless Mesh Networks
SRLG:
• A SRLG is a group of links share a common channel from a NIC
• The SRLG groups are
{(B, C), (A, C)}, NIC of node C tunes to channel 3
{(B, E), (D, E), (C, E)} , NIC of node E tunes to channel 2
{(B, D), (D, E)} , NIC of node D tunes to channel 1
•
NIC fail result in failure of all links in the same SRLG group
Fair Scheduling with QoS Guarantees for Uplink
Transmission in WiMAX Networks
2TSA Operations
Fairness Improvement
Average throughput
Fairness under greedy behavior
Fair Queuing with Power Saving in Wireless
Ad Hoc Networks
Algorithm flow chart
Fairness
Power consumption
Network life
Asymptotic Distribution of The Number of
Isolated Nodes in Wireless Ad Hoc Networks
with Unreliable Nodes and Links
•
•
•
Main Results:
p ln n   and nodes have the same maximum transmission radius r =
Suppose that lim
n-
constant ξ.

Then the total number of isolated nodes is asymptotically Poisson with mean e .
ln n  
np1 p2
Network Topology
p1 = 1 and p2 = 0.9
for some
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)
多天線多通道多模多速率無線網狀網路之設計與實作-總計畫(1/3), NSC, 2005.08
至2006.07
Major Projects

多天線多通道多模多速率無線網狀網路之設計與實作-子計畫
二:M4無線網狀網路之存取控制協定及繞徑設計(1/3), NSC,
2005.08至2006.07

後卓越計劃(93R045)下ㄧ世代資訊通訊網路尖端技術與應用(二)
-子計畫三:後三代全IP無線網路技術, Ministry of Education,
2004.04至2008.03

M4無線網狀網路具品質知覺之無縫交遞(1/3), NSC, 2005.082006.07

含行動隨意網的MPLS無線基礎網路, NSC, 2003.08 -2006.07

智慧型手持式裝置雙模網路支援能力之研究與網路應用服務,
Institute for Information Industry, 2004.01-2004.12
Major Projects


多階層行動隨意網路之設計及實作-總計劃, NSC,
2003.08 -2005.07
多階層行動隨意網路之設計及實作-子計劃一:多階層行動
隨意網路之虛擬家網環境, NSC, 2003.08 - 2005.07

無線感測網路之動態定位技術, NSC, 2004~2007

Advanced System Design of Power Aware Mobile
Devices, NSC, 2003~2006

Network flow control based Generalized Multiprotocol
Label Switching 2 (GMPLS), NSC, 2003~2005
Major Projects


A Wi-Max Gateway implementation Using
IXP 425, Intel, Taiwan, 2004~2006
Resource Management and Performance
Modeling for WCDMA Mobiles - subproject 3:
Performance Modeling of Mobile Processor
using SystemC, MediaTek Inc., Taiwan,
2004~2005
Prof. Rong-Hong Jan
(簡榮宏教授)

B.S., NTHU-IE, 1979
–
Location-aware WWW

M.S.,NTHU-IE,1983
–

Ph.D., NTHU-CS, 1987
An adaptive Web System for
Heterogeneous for IPv6 Networks

Professor, NCTU-CS, 1987~
–
Home Network Gateway wit WAP
and SMS

Chairman NCTU-CS, 1996


Visiting associate professor, UMDCS 1992
–

Research projects in last
three years
–
M4 wireless mesh networks:
design and implementation
–
GPRS/WAN Two-tier Mobility
System

Thin AP with Light weight Access
Point
Areas of research interests
–
Mobile computing
–
Wireless internet
–
Computer networks
–
Computer algorithms
–
Network reliability
Publications
–
International journal: 32
–
International conference: 28
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. Chien-Chao Tseng
(曾建超教授)
-August 1989 - August 1996
Associate Professor,
Department of Computer
Science and Information
Engineering, National
Chiao Tung University.
-August 1996 – Now
Professor, Department of
Computer Science and
Information Engineering,
National Chiao Tung
University.
Research Interests:
Wireless Internet Infrastructure and Protcols,
Wireless Internet Applications
Topics:
Integration of Wirelsss Networks:
- 3G, GPRS, Wireless LAN, Bluetooth, PAN
- Mobile IP, NAT, VPN, MPLS
- Mobile Router and Proxy, Ad Hoc Networks
- Fast Handover (802.11i)
Seamless Handover for Wireless Internet
- Drivers, Network Layer, Transport Layer,
Application Layer
- SIP Mobility, 802.11x, Authentications
(802.1x, 802.11i)
Wireless Internet Applications:
-Mobile e-learning Platform, ITS Platform,
Location-aware Applications
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. Shie-Yuan Wang
(王協源教授)
– Ph.D. (Harvard University), 1999

– Wireless Network
– Associate Professor (NCTU), 2003–
present


– Assistant Professor (NCTU), 2000-2003

– Founder and director of NCTU
“Network and System Laboratory,”
2000 –
– Vice director of NCTU EE college and
CS college’s Honors Undergraduate
Program, 2005 –
– Author of NCTUns Network Simulator
and Emulator (As of 11/24/2005, more
than 4,500 people from 95 countries
have registered and download this tool)
Research Interests
Mobile ad hoc network
Wireless LAN and mesh networks
WiMax and WLAN integrated networks
– Network Simulation and Emulation
– Internet Technology
– Network System Design and
Implementation

Publications




Journal Papers : 13
Conference Papers : 15
Book Chapters : 1
Patents : 1
Prof. Chien Chen
(陳 健 教授)
Energy-efficient Flooding in
MANETs
 Topology Control and Data
Aggregation in Wireless Sensor
Networks
 Wireless Mesh Routing and
Channel Assignment
 Survivable Wireless Mesh
Networks
WiMAX QoS Management Architecture
(Intel & III)
 Connection Management –
Measurement based CAC
 QoS Guarantee – Upstream
scheduler
 Service Provisioning – Packet
classification
Broadband & Optical Networks
 Network Processor (Intel)
 NAPT, and IP Classifier (III)
 Traffic Engineering in GMPLS
Networks (NSC)






Assistant Professor (NCTU), 2002~
Director & Chief Architect (Terapower)
2001-2002
Chief Engineer (Coree Networks)
2000-2001
Member of Technical Staff (Lucent,
Bell Labs) 1996-2000
–
Lecturer (Tunghai University) 19861988

B.S., NCTU-CE, 1982

M.S.,NCTU-CE,1984

Ph.D., Stevens-EE, 1996

Research Interests
–
–
Ad Hoc/Sensor/Wireless Mesh
Networks (NSC)

Link Stability Model and Adaptive
Routing Strategy in MANETs

Publications
– International journal: 2
– International conference: 13
Prof. Hsi-Lu Chao
(趙禧綠教授)





Ph.D., NTU-EE, 2004
Assistant Professor, NCTU-CS,
2004/8~
A member of the IEEE and
ACM
Listed in the Marquis Who's
Who in the World, 2006
Research interests
–
Protocol design for wireless
networks
–
Broadband Internet
–
Quality of Service issues

On-going research
includes:
– MAC layer issues in WiFi,
UWB and WiMax
– Power saving technologies
in MANETs, WSNs, WMNs
– QoS issues of multimedia
delivery
– Mobility issues in
heterogeneous networks

Publications
– International journal: 3
– Local journal: 1
– International conference: 3
Prof. Chih-Wei Yi
(易志偉教授)





He is an Assistant Professor with the Department of
Computer Science, National Chiao Tung University
He received his Ph.D. in Computer Science from the Illinois
Institute of Technology, May 2005.
His research interesting focuses on wireless ad hoc networks,
especially about the power saving issue.
He has 9 articles published or accepted by famous journals,
including IEEE TCOM, IEEE/ACM ToN, IEEE TPDS, IEEE IT,
ACM MONET, WCMC, etc., and 10 papers published in
international conferences, including INFOCOM, WCNC, ICC,
MobiHoc, etc..
Contact information:
– Email: [email protected]
– Tel: +886-3-5712121 ext 56686