Cùng với sựphát triển của khoa học công nghệ, công nghệthông tin đang ngày
càng được ứng dụng ởhầu hết các lĩnh vực trong cuộc sống xã hội như kinh tế, giáo
dục, xây dựng, y học,. việc ứng dụng công nghệthông tin vào giải quyết các công
việc thì Internet ngày càng khẳng định được vị trí quan trọng của mình trong cuộc
sống xã hội thời hiện đại. Khi cuộc sống con người ngày càng phát triển thì nhu cầu
trao đổi thông tin của con người ngày càng cao. Con người muốn mình có thểđược kết
nối với thếgiới vào bất cứlúc nào, từbất cứnơi đâu mà không cần phải có đường nối.
Đó chính là lý do mà mạng không dây ra đời. Ngày nay, chúng ta có thểthấy được sự
hiện diện của mạng không dây ởnhiều nơi như trong các tòa nhà, các công ty, bệnh
viện, trường học hay thậm trí là các quán cà phê. Cùng với sựphát triển của mạng có
dây truyền thống, mạng không dây cũng đang có những bước phát triển nhanh chóng
nhằm đáp ứng nhu cầu trao đổi thông tin và truyền thông của con người một cách tốt
nhất.
Khi mà mạng không dây đang ngày càng được quan tâm, đầu tư nghiên cứu và
phát triển thì ngày càng nhiều mô hình, kiến trúc mạng được đềxuất bởi các nhà khoa
học, các hội nghị.
Song song với sựphát triển của mạng không dây, mạng WLAN được chia ra
thành hai mô hình chính đó là mô hình mạng không dây có cơ sởhạtầng và mô hình
mạng không dây không có cơ sởhạtầng Ad Hoc
Các mô hình, kiến trúc mạng này được đưa ra nhằm làm cho mạng không dây
dần thoát khỏi sựphụthuộc hoàn toàn vào mạng cơ sởhạtầng. Một trong những mô
hình mạng được đềxuất đó chính là mạng Ad Hoc thường được viết tắt là MANET.
Việc các mạng không dây ít phụ thuộc vào cơ sở hạ tầng là một điều rất thuận lợi
nhưng lại có những vấn đềkhác đặt ra như tốc độtruyền thông không cao, mô hình
mạng không ổn định như mạng có dây truyền thống do các nút mạng hay di chuyển,
năng lượng cung cấp cho các nút mạng thường chủyếu là pin.Do đó, cùng với vấn đề
bảo mật của mạng không dây thì vấn đềđịnh tuyến trongmạng vô tuyến Ad Hoc cũng
là vấn đềvô cùng quan trọng. Nó quyết định rất lớn đến hiệu năng hoạt động của toàn
hệthống mạng
94 trang |
Chia sẻ: oanhnt | Lượt xem: 1884 | Lượt tải: 4
Bạn đang xem trước 20 trang tài liệu Luận văn Định tuyến trong mạng AD HOC vô tuyến, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
3
3
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN DUY TÂN
ĐỊNH TUYẾN TRONG MẠNG AD HOC VÔ TUYẾN
LUẬN VĂN THẠC SĨ
Hà Nội 2009
4
4
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN DUY TÂN
ĐỊNH TUYẾN TRONG MẠNG AD HOC VÔ TUYẾN
Ngành: Công Nghệ Thông Tin
Chuyên ngành: Truyền dữ liệu và Mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. TRẦN HỒNG QUÂN
Hà Nội 2009
5
5
MỤC LỤC
MỤC LỤC...................................................................................................................3
DANH MỤC HÌNH.....................................................................................................8
BẢNG KÝ HIỆU CÁC TỪ VIẾT TẮT .....................................................................10
CHƯƠNG I: TỔNG QUAN VỀ MẠNG VÔ TUYẾN...............................................13
1.1. Giới thiệu chung..............................................................................................13
1.2. Phân loại mạng không dây...............................................................................14
1.3. Mạng cá nhân WPAN (Wireless Personal Area Networks) [5]-[7]-[8]-[12] .....15
1.4. Mạng cục bộ WLAN (Wireless Local Area Network) [5]-[7]-[8]-[12].............15
1.4.1. Lịch sử ra đời mạng WLAN......................................................................16
1.4.2. Một số ưu điểm của mạng WLAN ............................................................16
1.4.3. Nhược điểm của WLAN ...........................................................................17
1.4.4. Mạng WLAN có cơ sở hạ tầng..................................................................18
1.4.5. Mạng Ad Hoc (MANET) [5]-[7]-[8]-[12] .................................................19
1.4.5.1. Khái niệm và một số đặc điểm chung của mạng Ad Hoc ....................19
1.4.5.2. Một số mạng Ad hoc điển hình...........................................................20
1.4.5.3. Các ứng dụng của mạng Ad hoc .........................................................21
1.5. Mạng đô thị không dây WMAN [7]-[14] ........................................................22
1.6. Tóm tắt chương ...............................................................................................24
CHƯƠNG II: MÔ HÌNH KIẾN TRÚC MẠNG KHÔNG DÂY 802.11.....................25
2.2. Mô hình kiến trúc mạng không dây so với mô hình OSI [8] ............................25
2.3. Kiến trúc giao thức mạng WLAN theo chuẩn 802.11 [8]-[7]-[11]-[14]............27
2.3.1. IEEE 802.11b............................................................................................27
2.3.2. IEEE 802.11a............................................................................................27
2.3.4. IEEE 802.11i ............................................................................................28
2.3.5. IEEE 802.11n............................................................................................29
2.4. Lớp Vật Lý (Physical Layer) ...........................................................................29
2.4.1. Kỹ thuật trải phổ nhảy tần [3]-[8]-[13]......................................................30
2.4.2. Kỹ thuật trải phổ tuần tự trực tiếp (DSSS - Direct Sequence Spread
Spectrum) [3]-[8]-[13] ........................................................................................31
2.4.3. Kỹ thuật sử dụng hồng ngoại (Infrared Physical Layer) [3]-[4] .................33
2.4.4. Kỹ thuật OFDM [3]-[8]-[10]-[14] ............................................................33
2.5. Lớp điều khiển truy cập môi trường truyền [7]-[10] ........................................35
2.5.1. Giao thức truy cập CSMA/CA [8].............................................................36
2.5.2. Chức năng phối hợp phân tán ...................................................................39
2.5.2.1. DCF sử dụng phương pháp CSMA/CD [8]-[11] .................................39
2.5.2.2. Sử dụng gói tin điều khiển RTS/CTS..................................................40
2.5.2.3. DCF sử dụng gói tin RTS/CTS để giải quyết vấn đề Hidden Terminal41
6
6
2.5.3. Chức năng phối hợp theo điểm [8]-[11] ...................................................42
2.6. Định dạng gói tin tầng MAC [8]......................................................................44
2.6.1. Khuôn dạng gói tin tầng MAC ..................................................................44
2.6.2. Định dạng gói tin điều khiển ACK, RTS, CTS..........................................45
2.7. Lớp quản lý tầng MAC (MAC Management) ..................................................45
2.7.1. Sự đồng bộ hóa (Synchronization) [11].....................................................45
2.7.2. Quản lý năng lượng (Power Management) ................................................47
2.7.3. Quản lý chuyển vùng (Handoff) ................................................................49
CHƯƠNG III: ĐỊNH TUYẾN TRONG MẠNG VÔ TUYẾN AD HOC ...................51
3.1. Giới thiệu về định tuyến trong mạng Ad hoc [9]-[10]-[11]-[12].......................51
3.2. Các yêu cầu đối với thuật toán định tuyến cho mạng Ad hoc không dây..........52
3.2. Phân loại các thuật toán định tuyến cho mạng Ad Hoc [11]-[12] .....................55
3.2. Định tuyến theo vecter khoảng cách tuần tự đích (DSDV - Destination
Sequenced Distance Vector) [4]-[5]-[10]-[11]-[12] ................................................56
3.3. Định tuyến theo trạng thái đường liên kết tối ưu [5]-[11]-[12] ........................58
3.4. Ad Hoc On-Demand Distance Vector (AODV) [5]-[11]-[12] ..........................60
3.5. Định tuyến nguồn động (DSR - Dynamic Source Routing) [5]-[10]-[11].........62
3.6. Giao thức định tuyến vùng (ZRP - Zone Routing Protocol) [11]-[12] ..............64
3.7. Tóm tắt............................................................................................................66
CHƯƠNG IV: XÂY DỰNG CHƯƠNG TRÌNH ĐỂ ĐÁNH GIÁ HIỆU NĂNG CỦA
CÁC GIAO THỨC ĐỊNH TUYẾN ...........................................................................67
4.1. Bộ mô phỏng mạng NS2 [2]-[15]-[20] ............................................................67
4.1.1. Giới thiệu..................................................................................................67
4.1.2. Sự liên kết giữa C++ và OTCL .................................................................68
4.1.3. Mô hình kiến trúc NS2..............................................................................69
4.1.4. Các đặc điểm chính của NS2.....................................................................69
4.1.5. Khả năng mô phỏng của NS......................................................................69
4.2. Mô phỏng mạng di động không dây 802.11 trong NS [18]-[20]-[21] ...............70
4.2.1. Các mô hình truyền sóng vô tuyến ............................................................70
4.2.1.1. Mô hình FreeSpace.............................................................................70
4.2.1.2. Mô hình hai tia mặt đất (Two Ray Ground) ........................................71
4.2.1.3. Mô hình Shadowing ...........................................................................71
4.2.2. Tạo một nút di động (Mobile Node) ......................................................73
4.2.3. Tạo sự chuyển động cho Node (Creating Node movements) .....................77
4.2.4. Tạo bộ lập lịch sự kiện (Creating Event Scheduler)...................................79
4.2.5. Ghi lại vết các sự kiện mô phỏng (vào file *.tr, *.nam) .............................79
4.2.6. Tạo ra các kết nối TCP và nguồn sinh lưu lượng.......................................79
4.2.7. Tạo ra các kết nối UDP và nguồn sinh lưu lượng ......................................80
4.3. Cấu trúc tệp vết đối với mạng di động không dây theo chuẩn 802.11 [16]-[18]-
[19]-[20]-[21].........................................................................................................80
7
7
4.4. Các công cụ xử lý sau khi mô phỏng ...............................................................84
4.4.1. Sử dụng Grep............................................................................................84
4.4.2. Xử lý file dữ liệu với Awk ........................................................................84
4.4.3. Xử lý file dữ liệu với Perl .........................................................................84
4.3.5. Vẽ đồ thị với gnuplot [26].........................................................................85
4.3.6. Vẽ đồ thị với xgraph [27] ..........................................................................85
4.3.7. Tổng hợp dữ liệu với Trace graph [23]-[24]-[25] ......................................85
4.5. Mô phỏng mạng Ad hoc theo chuẩn IEEE 802.11........................................85
4.5.1. Thiết lập topo mạng Ad hoc ......................................................................85
4.5.2. Thực hiện mô phỏng .................................................................................86
4.5.3. Đánh giá hiệu năng các giao thức mạng ....................................................87
4.5.3.1. Thông lượng trung bình......................................................................87
4.5.3.2. Độ trễ trung bình ................................................................................88
4.5.3.3. Thăng giáng độ trễ trung bình.............................................................88
4.5.3.4. Tỷ lệ mất gói tin .................................................................................89
4.5.4. Đánh giá các tuyến đường được thiết lập trong thời gian mô phỏng ......90
KẾT LUẬN ...............................................................................................................94
TÀI LIỆU THAM KHẢO..........................................................................................95
8
8
DANH MỤC HÌNH
Hình 1.1: Tổng quan về mạng vô tuyến .....................................................................14
Hình 1.2 : Tổng quát về các chuẩn mạng không dây ..................................................14
Hình 1.3: Mô hình mạng không dây có cơ sở hạ tầng.................................................18
Hình 1.4: Mô hình mạng không dây Ad hoc ..............................................................20
Hình 1.5: Mạng Ad Hoc điển hình .............................................................................20
Hình 2.1: Các chuẩn giao thức IEEE 802 và mô hình OSI .........................................26
Hình 2.2: Mô hình kiến trúc theo chuẩn 802.11 .........................................................26
Hình 2.3: Các lựa chọn chuẩn 802.11b.......................................................................27
Hình 2.4: Định dạng của một frame quy định trong FHSS 802.11 PHY.....................30
Hình 2.5: Các kênh và dải tần số hoạt động trùng nhau đáng kể.................................32
Hình 2.6: Các kênh không xung đột nhau khi ở cùng một khu vực.............................32
Hình 2.7: Định dạng của một frame quy định trong DSSS 802.11..............................32
Hình 2.8: Trực giao sóng mang con OFDM trong miền tần số ...................................34
Hình 2.9. Orthogonal Frequency Division Multiplexing (OFDM)..............................34
Hình 2.10 : Quá trình mã hóa và điều chế theo OFDM ..............................................35
Hình 2.11: Tầng MAC và tầng vật lý theo chuẩn 802.11............................................36
Hình 2.12: Định nghĩa các khoảng thời gian truy cập môi trường truyền....................36
Hình 2.13: Minh họa về khoảng tranh chấp truy cập CSMA/CA................................37
Hình 2.14: Minh họa về giao thức truy cập CSMA/CA với 5 trạm.............................37
Hình 2.16: Gửi dữ liệu unicast theo DFWMAC .........................................................39
Hình 2.17: Phân mảnh gói tin gửi dữ liệu unicast theo DFWMAC.............................39
Hình 2.18: DCF sử dụng giao thức CSMA/CA ..........................................................40
Hình 2.19: DCF sử dụng gói tin RTS/CTS..................................................................40
Hình 2.20: Hiện tượng đầu cuối ẩn ............................................................................41
Hình 2.21: Giải quyết hiện tượng đầu cuối ẩn............................................................42
Hình 2.22: Hiện tượng trạm cuối lộ............................................................................42
Hình 2.23:Cơ chế RTS/CTS giải quyết vấn đề trạm cuối ẩn.......................................42
Hình 2.24: Mô tả chu kỳ hoạt động của PCF..............................................................43
Hình 2.25: Khuôn dạng gói tin tầng MAC .................................................................44
Hình 2.26: Khuôn dạng gói tin ACK..........................................................................45
Hình 2.27: Khuôn dạng gói tin RTS...........................................................................45
Hình 2.28: Khuôn dạng gói tin CTS...........................................................................45
Hình 2.29: AP gửi gói tin beacon trong mạng không dây cơ sở hạ tầng .....................46
Hình 2.29: Truyền gói tin beacon trong mạng ad-hoc.................................................47
Hình 2.30: Quản lý năng lượng trong mạng dựa trên cơ sở hạ tầng............................48
Hình 2.31: Quản lý năng lượng trong mạng ad-hoc....................................................49
Hình 3.1: Ví dụ về việc phân chia vùng trong mạng Ad Hoc......................................55
9
9
Hình 3.2: Phân loại các giao thức định tuyến mạng Ad hoc .......................................56
Hình 3.3: Minh họa bảng định tuyến của DSDV ........................................................57
Hình 3.4: Bộ chuyển tiếp đa điểm (Multipoint relays)................................................59
Hình 3.5: AODV Khám phá và duy trì tuyến .............................................................61
Hình 3.6: DSR quá trình khám phá tuyến...................................................................63
Hình 3.7: ZRP bán kính vùng ....................................................................................65
Hình 3.8: Ví dụ khám phá đường đi ZRP ...................................................................65
Hình 4.1. Mô hình tổng quan bộ mô phỏng NS-2.......................................................67
Hình 4.2: C++ và OTcl, hai thành phần đối ngẫu .......................................................68
Hình 4.3: Kiến trúc của NS........................................................................................69
Hình 4.4: Một mobilenode dưới chuẩn wireless của Monarch của CMU mở rộng ra NS
..................................................................................................................................76
Hình 4.5: Một SRNode dưới chuẩn wireless của Monarch của CMU mở rộng ra NS.77
Hình 4.6: Đồ hình mô phỏng 50 node mạng ah hoc ...................................................86
Hình 4-7: Thông lượng trung bình của toàn mạng......................................................87
Hình 4-8: Độ trễ trung bình của toàn mạng ................................................................88
Hình 4-9: Thăng giáng độ trễ trung bình của toàn mạng.............................................89
Hình 4-10: Tỷ lệ mất gói tin trên toàn mạng ..............................................................89
10
10
BẢNG KÝ HIỆU CÁC TỪ VIẾT TẮT
ACK Acknowledgement
AES Advanced Encryption Standard
AODV Ad Hoc On-Demand Distance Vector
AP Access Point
ATIM Ad-hoc Traffic Indication Map
BSS Basic Service Set
BSSID Basic Service Set Identifier
CCK Complementary Code Keying
CCA Clear Channel Assessment
CSMA/CA Carrier Sense Multiple Access with Collision Avoidance
CSMA/CD Carrier Sense Multiple Access/Collision Detect
CTS Clear To Send
COFDM Coded Orthogonal Frequency Division Multiplexing
CW Contention Window
DCF Distributed Coordination Function
DIFS DCF Interframe Space
DS Destination Station
DSDV Destination Sequenced Distance Vector
DSR Dynamic Source Routing
DSSS Direct Sequence Spread Spectrum
DTIM Delivery Traffic Indication Map
EIRP Effective Isotropic Radiated Power
FCC Federal Communication Commission
FEC Forward Error Correction
FHSS Frequency Hopping Spread Spectrum
GFSK Gaussian shaped FSK Frequency Shift Keying
HEC Header Error Check
IEEE Institute of Electrical and Electronics Engineers
IARP Intrazone Routing Protocol
ISM Industry Scientific Medical
ISM Industrial, Scientific and Medical band
IERP Interzone Routing Protocol
LAN Local Area Network
11
11
LLC Logical Link Control
MAC Medium Access Control
MANET Mobile Ad Hoc Network
MPR Multipoint Relays
MPRs Multipoint Relays Selector
NAM Network Animator
NAV Net Allocation Vector
NEST Network Simulation Testbed
NIC Network Interface Card
NLOS Non-Line-of-Sight
NS2 Network Simulation Version 2.0
OFDM Orthogonal Frequency Division Multiplexing
OLSR Optimized Link State Routing
PCF Point Coordination Function
PLCP Physical Layer Convergence Procedure
PMD Physical Medium Dependent
PHY Physical
PSP Power Saving Poll
QoS Quality of Service
QPSK Quadrature Phase Shift Keying
REAL Realistic and Large
RREQ Route Request
RREP Route Reply
RERR Route ERRor
RTS Request To Send
SAP Service Access Point
SFD Start Frame Delimiter
SIFS Short Interframe Space
SNAP Sub-network Access Protocol
TIM Traffic Indication Map
TKIP Temporal Key Integrity Protocol
TMIM Traffic Map Indication Map
TSF Timing Synchronization Function
UNII Unlicensed National Information Infrastructure
VINT Virtual InterNetwork Testbed
WAN Wide Area Network
WEP Wired Encryption Privacy
12
12
WIFI Wireless Fidelity
WiMAX World Interoperability for MicroAccess
WLAN Wireless Local Area Network
WMAN Wireless Metropolitan Area Network
WPAN Wireless Personal Area Networks
WWAN Wireless Wide Area Network
WWiSE WorldWide Spectrum Efficiency
ZRP Zone Routing Protocol
13
13
CHƯƠNG I: TỔNG QUAN VỀ MẠNG VÔ TUYẾN
1.1. Giới thiệu chung
Cùng với sự phát triển của khoa học công nghệ, công nghệ thông tin đang ngày
càng được ứng dụng ở hầu hết các lĩnh vực trong cuộc sống xã hội như kinh tế, giáo
dục, xây dựng, y học,... việc ứng dụng công nghệ thông tin vào giải quyết các công
việc thì Internet ngày càng khẳng định được vị trí quan trọng của mình trong cuộc
sống xã hội thời hiện đại. Khi cuộc sống con người ngày càng phát triển thì nhu cầu
trao đổi thông tin của con người ngày càng cao. Con người muốn mình có thể được kết
nối với thế giới vào bất cứ lúc nào, từ bất cứ nơi đâu mà không cần phải có đường nối.
Đó chính là lý do mà mạng không dây ra đời. Ngày nay, chúng ta có thể thấy được sự
hiện diện của mạng không dây ở nhiều nơi như trong các tòa nhà, các công ty, bệnh
viện, trường học hay thậm trí là các quán cà phê. Cùng với sự phát triển của mạng có
dây truyền thống, mạng không dây cũng đang có những bước phát triển nhanh chóng
nhằm đáp ứng nhu cầu trao đổi thông tin và truyền thông của con người một cách tốt
nhất.
Khi mà mạng không dây đang ngày càng được quan tâm, đầu tư nghiên cứu và
phát triển thì ngày càng nhiều mô hình, kiến trúc mạng được đề xuất bởi các nhà khoa
học, các hội nghị.
Song song với sự phát triển của mạng không dây, mạng WLAN được chia ra
thành hai mô hình chính đó là mô hình mạng không dây có cơ