Mạng di động không dây đặc biệt MANET (Mobile Wireless Adhoc Network) cho
phép các máy tính di động thực hiện kết nối và truyền thông với nhau không cần dựa trên
cơ sởhạtầng mạng có dây. Trong MANET mọi nút m ạng đều cóthể thực hiện chức năng
của một router, chúng cộng tác với nhau, thực hiện chuyển tiếp các gói tin hộcác nút mạng
khác nếu các nút mạng này không thểtruyền trực tiếp với nút nhận. Định tuyến là bài toán
quan trọng nhất đối v ới việc nghiên cứu MANET. Chođến nay, đã có nhiều thuật toán định
tuyến được đềxuất, m ỗi thu ật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là
mức độcủa các ưu như ợc điểm phụthuộc rất nhi ều vào mức độdi động của các nút mạng.
Một sốthuật toán là ưu việt hơn các thuật to án khác trong điều kiện các nút mạng di động ở
mức độthấp nhưng lại kém hơn hẳn khi mức độdi động của các nút mạng tăng cao. Đềtài
luận văn này nhằm mục đích đánh giá và so sánh ảnh hưởng của sựdi động của nút mạng
đến hiệu quảcủa một sốthuật toán định tuyến trong mạng MANET.
Vềmặt thực tiễn, mạng MANET rất hữu ích cho các nhu cầu thiết lập mạng khẩn
cấp tại những nơi xảy ra thảm họanhư: hỏa hoạn, lụt lội, động đất .hay những nơi yêu
cầu tính nhanh chóng, tạm thời như trong các trận chiến, do thám Việc đánh giá và so
sánh ảnh hưởng của sựdi động đến hiệu quảcủa các thuật toánđịnh tuyến giúp cho việc
lựa chọn thuật toán định tuyến thích hợp cho các điều kiện cụthểkhi sửdụng MANET.
91 trang |
Chia sẻ: oanhnt | Lượt xem: 1669 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Đánh giá ảnh hưởng của sự di động của nút mạng đến hiệu quả của các thuật toán định tuyến trong mạng manet, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
PHAN HỮU DŨNG
ĐÁNH GIÁ ẢNH HƯỞNG CỦA SỰ DI ĐỘNG
CỦA NÚT MẠNG ĐẾN HIỆU QUẢ CỦA CÁC THUẬT
TOÁN ĐỊNH TUYẾN TRONG MẠNG MANET
LUẬN VĂN THẠC SĨ
Hà Nội - 2011
2
Lời cảm ơn
Đầu tiên tôi xin gửi lời cảm ơn tới các thầy cô giáo trong Trường Đại học Công
nghệ - Đại Học Quốc Gia Hà Nội, Viện Khoa học kỹ thuật Bưu điện và Viện Công
nghệ Thông tin - Viện Khoa học và Công nghệ Việt Nam đã tận tình chỉ bảo tôi trong
suốt khóa học; cảm ơn tập thể lớp K15T1, tập thể lớp K15 chuyên ngành Mạng và
Truyền thông máy tính. Cảm ơn các thành viên trong nhóm nghiên cứu với những ý
kiến góp ý quý báu trong quá trình tôi thực hiện đề tài, và đặc biệt tôi chân thành cảm
ơn thầy hướng dẫn - PGS.TS Nguyễn Đình Việt, người đã tận tình hướng dẫn, chỉ bảo
tôi trong học tập và nghiên cứu.
Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè của tôi,
những người đã luôn ở bên động viên và khích lệ tôi trong suốt khóa học.
Do thời gian và điều kiện có hạn nên luận văn không tránh khỏi có những thiếu
sót, tôi rất mong nhận được sự góp ý từ bạn bè, thầy cô và những người quan tâm đến
đề tài này.
Let’s start at the very beginning,
a very nice place to start,
when you sing, you begin with A, B, C,
when you simulate, you begin with the topology
- The ns Manual
3
Lời cam đoan
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn,
những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn
tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp
pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định
cho lời cam đoan của mình.
Hà Nội, ngày 01 tháng 05 năm 2011
Phan Hữu Dũng
4
Mục lục
Lời cảm ơn ..................................................................................................................1
Lời cam đoan ...............................................................................................................3
Danh mục hình vẽ........................................................................................................7
Danh mục bảng............................................................................................................9
Bảng ký hiệu các chữ viết tắt .....................................................................................10
Chương 1: GIỚI THIỆU ............................................................................................12
1.1. Đặt vấn đề.......................................................................................................12
1.2. Mục tiêu nghiên cứu........................................................................................12
1.3. Tổ chức của luận văn ......................................................................................13
Chương 2: MẠNG WLAN VÀ MẠNG MANET ......................................................14
2.1. Mạng không dây .............................................................................................14
2.1.1. Mạng cục bộ WLAN ................................................................................14
2.1.1.1. Lịch sử ra đời mạng WLAN ..............................................................15
2.1.1.2. Phân loại mạng WLAN .....................................................................15
2.1.1.3. Các chuẩn đối với mạng WLAN........................................................17
2.1.2. Một số mạng không dây phổ biến khác.....................................................18
2.1.2.1. Mạng cá nhân WPAN theo chuẩn 802.15.1, 802.15.3 và 802.15.4.....18
2.1.2.2. Mạng đô thị WMAN theo chuẩn 802.16 ............................................18
2.1.2.3. Mạng diện rộng WWAN theo chuẩn 802.20 ......................................19
2.2. Mạng di động không dây đặc biệt MANET.....................................................19
2.2.1. Giới thiệu mạng MANET.........................................................................19
2.2.2. Các đặc điểm của mạng MANET .............................................................22
2.2.3. Phân loại ..................................................................................................22
2.2.3.1. Phân loại mạng MANET theo cách thức định tuyến ..........................22
2.2.3.2. Phân loại mạng MANET theo chức năng của Nút..............................23
Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET ................26
3.1. Các giao thức định tuyến phổ biến trong mạng có dây truyền thống................26
3.1.1. Distance Vector........................................................................................26
3.1.2. Link State.................................................................................................26
3.1.3. Source Routing.........................................................................................27
3.1.4. Kỹ thuật Flooding ....................................................................................27
3.2. Các yêu cầu đối với thuật toán định tuyến trong mạng MANET......................27
3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET.................27
5
3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET......28
3.3. Phân loại các giao thức định tuyến cho MANET [16]........................................29
3.3.1. Các khái niệm liên quan ...........................................................................30
3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng......................................30
3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện .........................................30
3.3.1.3. Tính toán phi tập trung và tính toán phân tán .....................................31
3.3.1.4. Đơn đường và đa đường ....................................................................31
3.3.2. Phân loại các giao thức định tuyến ...........................................................31
3.3.2.1. Destination-Sequence Distance Vector (DSDV) ................................32
3.3.2.2. Optimized Link State Routing Protocol (OLSR)................................33
3.3.2.3. Ad hoc On-demand Distance Vector Routing (AODV) .....................35
3.3.2.4. Dynamic Source Routing (DSR) [12] ..................................................36
3.3.2.5. So sánh các giao thức định tuyến cho MANET..................................38
Chương 4: NGHIÊN CỨU VIỆC SỬ DỤNG CÔNG CỤ MÔ PHỎNG VÀ PHÂN
TÍCH KẾT QUẢ .......................................................................................................41
4.1. Lựa chọn phương pháp và công cụ đánh giá hiệu năng mạng [1] ......................41
4.1.1. Lựa chọn phương pháp .............................................................................41
4.1.1.1. Mô hình Giải tích ..............................................................................42
4.1.1.2. Mô phỏng mạng bằng chương trình máy tính ....................................42
4.1.1.3. Đo trên mạng thực .............................................................................42
4.1.1.4. Lý do sử dụng phương pháp mô phỏng để đánh giá hiệu năng mạng .43
4.1.2. Công cụ mô phỏng NS-2 [1, 12, 15]...............................................................43
4.1.2.1. Các chức năng mô phỏng chính của NS.............................................45
4.1.2.2 Cấu trúc phần mềm của NS ................................................................46
4.1.2.3. Lập trình mô phỏng bằng NS.............................................................46
4.1.3 Công cụ hỗ trợ phân tích kết quả mô phỏng...............................................46
4.1.3.1 Cấu trúc tệp vết chứa kết quả mô phỏng mạng không dây ..................46
4.1.3.2 Một số công cụ hỗ trợ việc phân tích và hiển thị kết quả mô phỏng ....47
4.1.4. Công cụ hiển thị trực quan mạng MANET trong quá trình hoạt động
iNSPECT ...........................................................................................................48
4.2. Thiết lập mô phỏng mạng MANET trong NS..................................................53
4.2.1. Tạo các nút mạng trong MANET .............................................................53
4.2.1.1 Nút di động.........................................................................................53
4.4.1.2 Mô hình phương tiện chia sẻ trong NS2..............................................54
4.4.1.3 Hoạt động của nút di động..................................................................55
4.4.1.4 Cấu hình nút di động trong NS ...........................................................56
6
4.4.1.5 Tạo sự di chuyển của nút trong NS .....................................................57
4.4.2. Tạo các đường truyền không dây (air interface) trong MANET................58
4.4.2.1 Mô hình FreeSpace.............................................................................58
4.4.2.2 Mô hình Two Ray Ground..................................................................58
4.4.2.3 Mô hình Shadowing ...........................................................................59
4.4.3. Tạo ngữ cảnh chuyển động.......................................................................59
4.4.3.1 Tạo diện tích mô phỏng ......................................................................60
4.4.3.2. Tạo các thực thể giao thức và các nguồn sinh lưu lượng ....................60
4.4.3.3. Tạo các dạng chuyển động theo mẫu .................................................61
4.4.4. Sơ đồ khái quát quá trình mô phỏng .........................................................64
4.5 Các tham số hoạt động của các giao thức định tuyến trong NS-2......................65
4.5.1 Giao thức định tuyến DSDV......................................................................65
4.5.2 Giao thức định tuyến OLSR ......................................................................66
4.5.3 Giao thức định tuyến AODV .....................................................................66
4.5.4 Giao thức định tuyến DSR.........................................................................67
Chương 5: ĐÁNH GIÁ HIỆU NĂNG CÁC GIAO THỨC ĐỊNH TUYẾN THEO
MỨC ĐỘ LINH ĐỘNG CỦA CÁC NÚT MẠNG.....................................................68
5.1. Thực nghiệm mô phỏng ..................................................................................68
5.1.1 Các thông số mô phỏng .............................................................................68
5.1.2 Chương trình mô phỏng ............................................................................69
5.2. Các độ đo hiệu năng được dùng trong luận văn ...............................................70
5.3. Kết quả mô phỏng...........................................................................................70
5.3.1 Mô phỏng sử dụng mô hình Random Waypoint.........................................70
5.3.1.1 Thiết lập thông số mô phỏng ..............................................................70
5.3.2.2 Kết quả và nhận xét ............................................................................72
5.3.3 Mô phỏng sử dụng mô hình Random Walk ...............................................75
5.3.3.1 Thiết lập thông số mô phỏng ..............................................................75
5.3.3.2 Kết quả và nhận xét ............................................................................77
5.3.4 Đánh giá hiệu quả của các giao thức định tuyến ........................................79
Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU...............................................81
6.1. Kết quả đạt được của luận văn.........................................................................81
6.2. Hướng nghiên cứu...........................................................................................82
TÀI LIỆU THAM KHẢO..........................................................................................83
PHỤ LỤC..................................................................................................................84
7
Danh mục hình vẽ
Hình 1. Phân loại các mạng không dây dựa trên quy mô. ..........................................14
Hình 2. Mạng WLAN có cơ sở hạ tầng .....................................................................16
Hình 3. Mạng WLAN không có cơ sở hạ tầng [10] ...................................................17
Hình 4. Mạng MANET và Sensor không dây [14].....................................................21
Hình 5. Định tuyến Single-hop..................................................................................23
Hình 6. Định tuyến Multi-hop ...................................................................................23
Hình 7. Mạng MANET phân cấp ..............................................................................24
Hình 8. Mạng MANET kết hợp.................................................................................24
Hình 9. Phân loại các giao thức định tuyến trong mạng MANET [13].......................32
Hình 10. Tập chuyển tiếp đa điểm MPRs ..................................................................34
Hình 11. Định tuyến Link State và định tuyến cải tiến trong OLSR............................34
Hình 12. AODV tìm kiếm và duy trì tuyến đường .....................................................36
Hình 13. Ví dụ về Route discovery: nút A là nút nguồn, nút E là nút đích. ................37
Hình 14. Ví dụ về Route maintenance: ......................................................................38
Hình 15. Kiến trúc NS-2 ...........................................................................................44
Hình 16. Ba giai đoạn của một phiên truyền từ nút nguồn 1 đến nút đích 48 .............49
Hình 17. Hình tròn bao phủ biểu diễn khu vực tắc nghẽn ..........................................50
Hình 18. Hình tròn bao phủ biểu diễn khu vực nguy hiểm.........................................51
Hình 19. iNSpect hiển thị tọa độ (x, y) của các nút ....................................................52
Hình 20. Nút di động mô phỏng trong NS2 ...............................................................53
Hình 21. Mô hình phương tiện chia sẻ trong NS2......................................................55
Hình 22. Sơ đồ của một mobilenode dưới chuẩn wireless của Monarch CMU mở rộng
ra NS [12] ..................................................................................................................57
Hình 23. Các mô hình truyền thông trong NS2..........................................................60
Hình 24. Di chuyển của một nút theo mô hình Random Waypoint ............................62
Hình 25. Di chuyển của một nút theo mô hình Random Walk ...................................63
Hình 26. Sơ đồ tổng quan quá trình mô phỏng ..........................................................64
Hình 27. Đánh giá kết quả phân phát gói tin trong mô hình Random Waypoint.........72
Hình 28. Đánh giá kết quả trễ đầu cuối trong mô hình Random Waypoint ................72
Hình 29. Đánh giá kết quả thông lượng trong mô hình Random Waypoint................73
Hình 30. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Waypoint ..............73
Hình 31. Đánh giá kết quả phân phát gói tin trong mô hình Random Walk ...............77
Hình 32. Đánh giá kết quả trễ đầu cuối trong mô hình Random Walk .......................77
Hình 33. Đánh giá kết quả thông lượng trong mô hình Random Walk.......................78
8
Hình 34. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Walk.....................78
9
Danh mục bảng
Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2] ................................................17
Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2]........................................17
Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15 .....................................................18
Bảng 4: So sánh độ phức tạp của các giao thức định tuyến ........................................39
Bảng 5: So sánh các đặc điểm của các giao thức định tuyến ......................................39
Bảng 6: So sánh các đặc điểm của các giao thức định tuyến ......................................40
Bảng 7. Các tham số của mô hình Random Waypoint ..............................................62
Bảng 8. Các tham số của mô hình Random Walk ......................................................63
Bảng 9. Các tham số hoạt động của DSDV trong NS2...............................................65
Bảng 10. Các tham số hoạt động của OLSR trong NS2 .............................................66
Bảng 11. Các tham số hoạt động của AODV trong NS2 ............................................66
Bảng 12. Các tham số hoạt động của DSR trong NS2................................................67
Bảng 13. Cấu hình các mạng mô phỏng trong mô hình Random Waypoint ...............71
Bảng 14. Cấu hình các mạng mô phỏng theo mô hình Random Walk........................76
10
Bảng ký hiệu các chữ viết tắt
AODV Ad hoc On-demand Distance Vector
CSMA/CA Carrier Sense Multiple Access with Collision Avoidance
DARPA Defense Advanced Research Projects Agency
DSDV Destination-Sequenced Distance Vector
DSR Dynamic Source Routing
DV Distance Vector
ETSI European Telecommunications Standards Institute
FCC US Federal Communications Commission
FIFO First In First Out
GPRS General Packet Radio Service
GSM Global System for Mobile communication
HiperLAN High Performance European Radio LAN
IEEE Institute of Electrical and Electronic Engineering
IETF Internet Engineering Task Force
iNSpect interactive NS-2 protocol and environment confirmation tool
ISM Industrial, Scientific and Medical bands
LAN Local Area Network
LS Link State
MAC Media Access Control
MANET Mobile Wireless Adhoc Network
NEST Network Simulation Testbed
NS2 Network Simulator 2
OLSF Open Shortest Path First
OLSR Optimized Link State Routing Protocol
11
PDA Personal Digital Assistant
PRnet Packet Radio Network
QoS Quality of Service
REAL Realistic and Large
RIP Routing Information Protocol
RREP Route Reply
RREQ Route Request
RTS Request To Send
SURAN Survivable Radio Network
TDMA/TDD Time Division Multiple Access/ Time Division Duplex
TORA Temporally-Ordered Routing Algorithm
UMTS Universal Mobile Telecommunications Systems
VINT Virtual InterNetwork Testbed
WIFI Wireless Fidelity
WiMAX World Interoperability for MicroAccess
WLAN Wireless Local Area Network
WMAN Wireless Metropolitan Area Networks
WPAN Wireless Personal Area Networks
WRP Wireless Routing Protocol
WWAN Wireless Wide Area Networks
ZRP Zone Routing Protocol
12
Chương 1: GIỚI THIỆU
1.1. Đặt vấn đề
Mạng di động không dây đặc biệt MANET (Mobile Wireless Adhoc Network) cho
phép các máy tính di động thực hiện kết nối và truyền thông với nhau không cần dựa trên
cơ sở hạ tầng mạng có dây. Trong MANET mọi nút mạng đều có thể thực hiện chức năng
của một router, chúng cộng tác với nhau, thực hiện chuyển tiếp các gói tin hộ các nút mạng
khác nếu các nút mạng này không thể truyền trực tiếp với nút nhận. Định tuyến là bài toán
quan trọng nhất đối với việc nghiên cứu MANET. Cho đến nay, đã có nhiều thuật toán định
tuyến được đề xuất, mỗi thuật toán đều có các ưu và nhược điểm riêng. Điều đặc biệt là
mức độ của các ưu nhược điểm phụ thuộc rất nhiều vào mức độ di động của các nút mạng.
Một số thuật toán là ưu việt hơn các thuật toán khác trong điều kiện các nút mạng di động ở
mức độ thấp nhưng lại kém hơn hẳn khi mức độ di động của các nút mạng tăng cao. Đề tài