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