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

ĐẠ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

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

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

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

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

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

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

Hình 34. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Walk.....................78

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

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

Dynamic Source Routing DSR

Distance Vector DV

European Telecommunications Standards Institute ETSI

US Federal Communications Commission FCC

First In First Out FIFO

General Packet Radio Service GPRS

Global System for Mobile communication GSM

HiperLAN High Performance European Radio LAN

Institute of Electrical and Electronic Engineering IEEE

Internet Engineering Task Force IETF

iNSpect interactive NS-2 protocol and environment conﬁrmation tool

Industrial, Scientiﬁc and Medical bands ISM

Local Area Network LAN

Link State LS

Media Access Control MAC

MANET Mobile Wireless Adhoc Network

Network Simulation Testbed NEST

Network Simulator 2 NS2

Open Shortest Path First OLSF

Optimized Link State Routing Protocol OLSR

Personal Digital Assistant PDA

Packet Radio Network PRnet

Quality of Service QoS

Realistic and Large REAL

Routing Information Protocol RIP

Route Reply RREP

Route Request RREQ

Request To Send RTS

SURAN Survivable Radio Network

TDMA/TDD Time Division Multiple Access/ Time Division Duplex

Temporally-Ordered Routing Algorithm TORA

Universal Mobile Telecommunications Systems UMTS

Virtual InterNetwork Testbed VINT

Wireless Fidelity WIFI

WiMAX World Interoperability for MicroAccess

Wireless Local Area Network WLAN

Wireless Metropolitan Area Networks WMAN

Wireless Personal Area Networks WPAN

Wireless Routing Protocol WRP

Wireless Wide Area Networks WWAN

Zone Routing Protocol ZRP

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 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ọa như: 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.

1.2. Mục tiêu nghiên cứu

Các mạng AD HOC ngày càng được ứng dụng rộng rãi trong nhiều lĩnh vực cuộc sống như khoa học, giáo dục, y tế, quân sự … do nó có ưu điểm nổi bật là loại bỏ sự phụ thuộc vào các cơ sở hạ tầng mạng cố định. Vấn đề đặt ra là đánh giá hiệu quả hoạt động của các giao thức định tuyến trong mạng MANET trên nhiều khía cạnh và phương diện khác nhau. Một trong những yếu tố ảnh hưởng rất lớn đến hiệu quả của các giao thức định tuyến đó là sự linh động của các nút mạng. Mục đích của luận văn là nghiên cứu các giao thức định tuyến kết hợp với việc đưa ra các kết quả mô phỏng để đánh giá hiệu quả làm việc của chúng. Căn cứ vào mục đích chính của luận văn, tôi xin đưa ra các mục tiêu cụ thể như sau:

 Giới thiệu tổng quan về mạng LAN không dây (Wireless LAN) và Mạng di

động không dây đặc biệt – MANET (Mobile Wireless Adhoc Network).

 Nghiên cứu một số giao thức định tuyến không dây sử dụng trong mạng

MANET: DSDV, OLSR, AODV, DSR.

 Xác định các tham số hiệu suất chính của các giao thức định tuyến.  Tìm hiểu khả năng mô phỏng các giao thức định tuyến cũng như các mô hình

chuyển động khác nhau của bộ mô phỏng mạng NS-2.

 Đánh giá bằng mô phỏng một số giao thức định tuyến phổ biến trong các ngữ

cảnh chuyển động của các nút mạng khác nhau.

1.3. Tổ chức của luận văn

Luận văn được tổ chức thành sáu chương, cụ thể như sau:

 Chương 1: GIỚI THIỆU  Chương 2: MẠNG WLAN VÀ MẠNG MANET  Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET  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Ả

 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

 Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU

Trong đó, chương một trình bày cơ sở khoa học và tính thực tiễn cũng như mục tiêu nghiên cứu của luận văn. Chương hai đưa ra kiến thức cơ sở về mạng WLAN và mạng MANET. Các kỹ thuật định tuyến truyền thống được sử dụng trong mạng cố định và các giao thức định tuyến dùng trong mạng MANET được trình bày chương ba. Chương bốn đưa ra cái nhìn tổng quan về bộ mô phỏng NS-2 và giới thiệu công cụ mô phỏng mới iNSpect từ đó ứng dụng vào việc mô phỏng các giao thức định tuyến. Chương năm sử dụng những kết quả mô phỏng thu được trong chương bốn để tính toán các độ đo hiệu năng sau đó kết hợp với cơ sở lý thuyết về các giao thức định tuyến trình bày trong chương ba để rút ra những đánh giá về ảnh hưởng của sự di dộng của nút mạng đến hiệu quả của các giao thức định tuyến trong mạng MANET. Cuối cùng, trong chương sáu là những nhận xét về kết quả đạt được và hướng nghiên cứu tiếp theo của luận văn.

Chương 2: MẠNG WLAN VÀ MẠNG MANET

Mục tiêu của chương này là giới thiệu với người đọc những kiến thức cơ sở về mạng WLAN và mạng MANET bao gồm lịch sử ra đời, các đặc điểm, những ưu nhược điểm cũng như các ứng dụng trong khoa học, công nhệ và cuộc sống từ đó có cái nhìn tổng quan về hai mạng này và dễ dàng phân biệt được chúng.

2.1. Mạng không dây

Các mạng không dây (Wireless networks) thường được phân thành mạng cá nhân WPAN - chuẩn IEEE 802.15, mạng cục bộ WLAN - chuẩn IEEE 802.11, mạng đô thị WMAN - chuẩn IEEE 802.16 và mạng diện rộng WWAN - chuẩn IEEE 802.20. Sự phân chia này dựa trên quy mô và phạm vi truyền dẫn của các bộ phát (transmitter) vô tuyến và mỗi lớp mạng có thể gồm một vài tiêu chuẩn và công nghệ riêng.

Hình 1 bên dưới minh họa sự phân lớp các mạng không dây dựa trên quy mô:

Hình 1. Phân loại các mạng không dây dựa trên quy mô.

2.1.1. Mạng cục bộ WLAN

Wireless Local Area Network (WLAN) là một mạng cục bộ kết nối hai hay nhiều máy tính với nhau mà không cần các kết nối vật lý giữa chúng. Môi trường truyền được sử dụng trong WLAN là môi trường không khí với một dải tần số được quy định cho các loại hình truyền thông. Có hai công nghệ chính được sử dụng để truyền thông trong WLAN là truyền thông bằng tia hồng ngoại (bước sóng 900 nm) hoặc truyền thông bằng sóng vô tuyến, thông thường thì sóng vô tuyến được dùng phổ biến hơn vì nó truyền xa hơn, lâu hơn, rộng hơn và có băng thông cao hơn. WLAN cũng có hai dạng kiến trúc là WLAN có cơ sở hạ tầng (sử dụng các Access Point) hoặc trạm cơ sở (Base Station) để kết nối phần mạng không dây với phần mạng có dây truyền thống và mạng không có cơ sở hạ tầng (mạng Ad hoc).

2.1.1.1. Lịch sử ra đời mạng WLAN

Năm 1971, tại Đại học Hawaii các công nghệ mạng và truyền thông vô tuyến đã được kết hợp lần đầu tiên trong dự án Alohanet. Dự án này sử dụng các thiết bị máy tính tại bảy điểm khác nhau nằm rải rác trên bốn hòn đảo thực hiện việc giao tiếp với máy tính trung tâm trên đảo Oahu bằng cách sử dụng không khí làm môi trường truyền. Nó thiết lập một topo Star và các trạm từ xa chỉ có thể giao tiếp thông qua máy tính trung tâm đặt tại đảo Oahu.

Tuy nhiên, đến giữa thập niên 1980 thì mạng WLAN mới phát triển mạnh khi Uỷ ban Truyền thông Liên bang Mỹ FCC (US Federal Communications Commission) quyết định cho phép sử dụng phổ biến các dải tần số công nghiệp, khoa học và y tế ISM (Industrial, Scientiﬁc and Medical bands). Quyết định này cho phép các công ty và người dùng sản xuất và sử dụng các sản phẩm không dây của họ mà không cần FCC cấp giấy phép hoạt động. Từ đó, dẫn đến sự tăng trưởng vượt bậc trong lĩnh vực mạng WLAN. Tuy nhiên, do sự xuất hiện của nhiều sản phẩm độc quyền nhưng lại không có một tiêu chuẩn chung thống nhất, dẫn đến các sản phẩm không cùng một công ty sản xuất có thể sẽ không tương thích với nhau. Vì vậy, yêu cầu đặt ra là phải chuẩn hóa trong lĩnh vực mạng WLAN.

Hiện nay, trên thế giới chủ yếu sử dụng hai chuẩn phổ biến cho mạng WLAN là: Chuẩn IEEE 802.11x do các Nhóm công tác của Viện công nghệ Điện và Điện Tử IEEE (Institute of Electrical and Electronics Engineers) phát triển và chuẩn HiperLAN/x (High Performance European Radio LAN) được phát triển bởi nhóm RES10 thuộc Viện Tiêu chuẩn Viễn thông Châu Âu ETSI (European Telecommunications Standards Institute). Chuẩn IEEE 802.11x sử dụng giao thức CSMA/CA, còn chuẩn HiperLAN/x là giao thức TDMA/TDD. Chuẩn IEEE 802.11x được sử dụng phổ biến hơn so với chuẩn HiperLAN/x nhưng chuẩn HiperLAN/x có những ưu điểm nổi trội khi đối phó với vấn đề lưu lượng thời gian thực.

2.1.1.2. Phân loại mạng WLAN

Mạng WLAN có cơ sở hạ tầng

Mạng WLAN có cơ sở hạ tầng là mạng mà các nút mạng truyền thông với nhau sử dụng một thiết bị trung tâm gọi là điểm truy cập chung AP (Access Point), hay còn được gọi là trạm cơ sở BS (Base Station). Các trạm cơ sở không chỉ cung cấp khả năng kết nối mạng mà nó còn thực hiện chức năng điều khiển truy cập đường truyền nhằm chuyển tiếp thông tin từ nguồn đến đích. Ngoài ra, các điểm truy cập mạng còn thường được kết nối với mạng có dây và được kết nối với Internet nên nó đóng vai trò như là cầu nối giữa các mạng không dây và mạng có dây với nhau tạo thành một mạng diện rộng. Tốc độ truyền dữ liệu của mạng không chỉ phụ thuộc vào đặc điểm của các nút mạng mà còn phụ thuộc vào bán kính phủ sóng của các điểm truy cập mạng. Các nút mạng càng gần điểm truy cập mạng AP thì sóng thu được càng mạnh và tốc độ truyền dữ liệu càng cao. Do đó, việc lựa chọn tốc độ truyền và phạm vi hoạt động của điểm

truy cập mạng khiến chúng ta cần phải cân nhắc, khi đó nó sẽ ảnh hưởng trực tiếp tới hiệu năng hoạt động của mạng và của điểm truy cập mạng.

Khái niệm Indoor và Outdoor: Indoor là khái niệm sử dụng sóng vô tuyến trong phạm vi không gian nhỏ, như trong một tòa nhà, một văn phòng. Outdoor là khái niệm sử dụng sóng vô tuyến trong phạm vi không gian lớn hơn, với WLAN thì bán kính đến các thiết bị mà nó quản lý có thể lên đến 5km.

Hình 2. Mạng WLAN có cơ sở hạ tầng

Mạng WLAN không có cơ sở hạ tầng (mạng Ad Hoc)

Một mạng Ad Hoc là một tập hợp các nút không dây di động (có chứ năng như routers) cấu thành nên một mạng tạm thời mà không cần sử dụng cơ sở hạ tầng có sẵn hoặc việc quản trị tập trung. Các routers được tự do di chuyển ngẫu nhiên và tự thiết lập tùy ý, vì vậy topo mạng không dây có thể thay đổi nhanh chóng và không thể biết trước [10].

Mạng Ad Hoc là mạng mà các nút trong mạng có thể tự thiết lập, tự tổ chức và tự thích nghi khi có một nút mới gia nhập mạng, các nút trong mạng cần có cơ chế phát hiện nút mới gia nhập mạng, thông tin về nút mới sẽ được cập nhật vào bảng định tuyến của các nút hàng xóm và gửi đi. Khi có một nút ra khỏi mạng, thông tin về nút đó sẽ được xóa khỏi bảng định tuyến và hiệu chỉnh lại tuyến, ...Mạng Ad Hoc có nhiều loại thiết bị khác nhau tham gia mạng lên các nút mạng không những phát hiện được khả năng kết nối của các thiết bị, mà còn phải phát hiện ra được loại thiết bị và các đặc tính tương ứng của các loại thiết bị đó (vì các thiết bị khác nhau sẽ có các đặc tính khác nhau ví dụ như: khả năng tính toán, lưu trữ hay truyền dữ liệu trong mạng,...)

Hình 3. Mạng WLAN không có cơ sở hạ tầng [10]

2.1.1.3. Các chuẩn đối với mạng WLAN

Chuẩn IEEE 802.11/x

802.11 802.11a 802.11b 802.11g

5.15-5.25 (lower) Frequency Range 2.4-2.4835 2.4-2.4835 2.4-2.4835 5.25-5.35 (middle) (GHz) 5.725-5.825 (upper)

2 55 11 54 Max.DataRate (Mbps)

30 < 10 m 27-30(lowerband) 75-100 Range

Bảng 1. Tổng quan về họ các chuẩn IEEE 802.11 [2]

Chuẩn HIPERLAN/x

WLAN

HIPERLAN 1 HIPERLAN 2 HIPERLAN 3 HIPERLAN 4

WATM Indoor Access

Wireless Point to Point Links - WATM interconnection

Fixed Wireless Access - WATM Remote Access

Application

Frequency Range 5 5 5 17 (GHz)

23.5 20 20 155 Max.DataRate (Mbps)

Bảng 2. Tổng quan về họ các chuẩn ETSI HIPERLAN [2]

2.1.2. Một số mạng không dây phổ biến khác

2.1.2.1. Mạng cá nhân WPAN theo chuẩn 802.15.1, 802.15.3 và 802.15.4

Mạng WPAN (Wireless Personal Area Networks) thường liên quan đến khái niệm văn phòng không dây. Phạm vi của mạng PAN là một vài mét, cung cấp khả năng đồng bộ hóa các máy tính, truyền files và truy cập được vào thiết bị ngoại vi cục bộ như máy in hay các thiết bị cầm tay khác như điện thoại di động và PDAs. Hiện tại, công nghệ nổi tiếng nhất của PAN là Bluetooth.

Viện công nghệ Điện và Điện Tử IEEE đưa ra chuẩn 802.15 sử dụng cho mạng WPAN với các tốc độ truyền dữ liệu như sau: 802.15.1 đặc tả công nghệ Bluetooth có tốc độ truyền dữ liệu ở mức trung bình, trong khi 802.15.3 được phát triển cho mạng Ad hoc với lớp MAC phù hợp cho truyền dữ liệu đa phương tiện có tốc độ truyền dữ liệu ở mức cao và 802.15.4 định nghĩa giao thức liên kết nối các thiết bị ngoại vi truyền thông sóng vô tuyến trong hệ thống mạng một người dùng có tốc độ truyền ở mức thấp.

802.15.1 802.15.3 802.15.4

2.4 Ghz 2.45 Ghz 915MHz 868MHz Frequency Range 2.4 Ghz

1 Mpbs 55 Mpbs 250 Kpbs 40 Kbps 20 Kbps Max.Data Rate

< 10 m < 10 m 10 - 75 m Range

Bảng 3. Tổng quan về họ các chuẩn IEEE 802.15

2.1.2.2. Mạng đô thị WMAN theo chuẩn 802.16

Mạng đô thị không dây WMAN (Wireless Metropolitan Area Networks) được định nghĩa là mạng có qui mô lớn có thể bao phủ một vùng đô thị như một thành phố, một quận, huyện hoặc là một khu vực dân cư rộng lớn nào đó. Mạng này sử dụng các công nghệ dành cho mạng diện rộng (WAN), có tốc độ truyền dẫn cao và khả năng kháng lỗi mạnh.

Năm 2001, chuẩn IEEE 802.16 đã được thiết kế để mở ra một tập hợp các giao tiếp dựa trên giao thức tầng MAC và lớp vật lý. Chuẩn 802.16 cũng đề cập đến công nghệ WiMax là công nghệ không dây băng thông rộng đang phát triển rất nhanh với khả năng triển khai trên phạm vi rộng và mang lại khả năng kết nối Internet tốc độ cao tới các gia đình và công sở. Giao thức lớp MAC của chuẩn IEEE 802.16 hỗ trợ truy cập không dây băng rộng điểm - đa điểm với tốc độ truyền dữ liệu cao trên cả hai hướng truyền đa người dùng, trong cùng thời gian có thể cho phép hàng trăm thiết bị trên kênh đó có thể được chia sẻ đa người dùng. IEEE 802.16 là giao diện cho hệ thống truy nhập băng rộng cố định, lớp MAC và lớp vật lý (PHY) hoạt động ở 10 GHz - 66 GHz.

Ngoài ra chúng ta có thể kể ra các chuẩn mở rộng của chuẩn IEEE 802.16 như chuẩn IEEE 802.16a ra đời năm 2003, chuẩn 802.16d được đưa ra năm 2004 là sự kết hợp của chuẩn IEEE 802.16 và chuẩn IEEE 802.16a có thay đổi lớp MAC và lớp vật lý PHY.

Mạng WiMax là tập hợp các mạng WiFi và được thiết kế riêng cho việc phân bố và di động rộng, phục vụ cho: các xí nghiệp, các khu dân cư nhỏ lẻ, mạng cáp truy nhập WLAN công cộng nối tới mạng đô thị, các trạm gốc BS của mạng thông tin di động và các mạch điều khiển trạm BS. WiMax đem lại tốc độ cao, trên 30 Mbps.

Hiện nay, công nghệ WiMAX được chia ra thành 2 công nghệ chính đó là công nghệ WiMAX cố định theo chuẩn IEEE 802.16d - 2004 và công nghệ WiMAX di động theo chuẩn IEEE 802.16e - 2005. Ưu điểm của WiMax là:

 Được thiết kế riêng cho hoạt động mạng không dây diện rộng.

Những khó khăn của WiMax bao gồm:

 Giá thành sản phẩm WiMax đắt hơn rất nhiều so với WiFi.

2.1.2.3. Mạng diện rộng WWAN theo chuẩn 802.20

Các mạng trải dài trên một quốc gia hoặc thậm chí toàn thế giới được gọi là mạng diện rộng WWAN (Wireless Wide Area Networks), Internet là một trong những mạng WAN cố định nổi tiếng nhất và các mạng GSM/GPRS và 3G đại diện cho các mạng WAN không dây. GSM (Global System for Mobile communication) hiện là hệ thống thông tin liên lạc di động lớn nhất thế giới cung cấp các dịch vụ chuyển mạch kênh. GPRS (General Packet Radio Service) được giới thiệu như là một phần mở rộng dịch vụ chuyển mạch gói được chuẩn hóa của kiến trúc GSM cung cấp tốc độ truyền tối đa cao hơn. Với dịch vụ chuyển mạch gói ta có thể sử dụng thiết bị di động kết nối GPRS tương tự như một máy tính kết nối với Internet, mạng GPRS hoạt động chỉ khi dữ liệu đang được truyền đi, do đó làm giảm chi phí sử dụng.

Các mạng di động thế hệ thứ ba (3G), phát triển bởi ETSI vào năm 1999, được thiết kế để cung cấp cuối cùng tốc độ truyền ngang bằng với các mạng cố định. Điều này làm 3G trở thành một thay thế thú vị cho các mạng WLAN. Mặc dù mục tiêu ban đầu của mạng không dây toàn cầu cuối cùng là hai công nghệ khác nhau cùng tồn tại. Tại châu Âu WCDMA được chọn là công nghệ chính, trong khi CDMA2000 đang phổ biến ở Mỹ, 85% các mạng 3G trên thế giới được dựa trên công nghệ WCDMA.

2.2. Mạng di động không dây đặc biệt MANET

2.2.1. Giới thiệu mạng MANET

MANET là chữ viết tắt của cụm từ Mobile wireless Ad hoc NETwork, là tập hợp các nút di động có trang bị các giao tiếp mạng không dây khi thiết lập truyền thông không cần tới sự hiện diện của các cơ sở hạ tầng mạng và các quản trị trung tâm. Trong MANET mọi nút mạng đều 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.

Mobile = di động, không chịu sự quản lý của quản trị mạng. Adhoc = không hạ tầng mạng, topo mạng động. MANET =

NETwork

Năm 1971, tại Đại học Hawaii các công nghệ mạng và truyền thông vô tuyến đã được kết hợp lần đầu tiên trong dự án Alohanet. Mục tiêu của mạng này là kết nối các cơ sở giáo dục ở Hawaii. Mặc dù các trạm làm việc là cố định nhưng giao thức ALOHA thực hiện việc quản lý truy cập kênh truyền dưới dạng phân tán, do đó cung cấp cơ sở cho sự phát triển về sau của các lược đồ truy cập kênh phân tán cho phép hoạt động của mạng Ad Hoc.

Mạng MANET có khởi nguồn từ mạng PRNet (Packet Radio Network) và dự án SURAN (Survivable Radio Network) của tổ chức DARPA (Defense Advanced Research Projects Agency) thuộc chính phủ Mỹ.

Năm 1972, mạng PRnet ra đời. Đây là mạng vô tuyến gói tin đa chặng đầu tiên. Trong ngữ cảnh này, đa chặng có nghĩa là các nút hợp tác để chuyển tiếp truyền thông cho các nút ở xa nằm ngoài dải truyền thông của một nút khác. PRnet cung cấp cơ chế để quản lý hoạt động trên cơ sở tập trung cũng như phân tán. PRnet cũng là mạng đầu tiên sử dụng trạm điều khiển tập trung, sử dụng những công nghệ sau này là tiền đề để cấu thành một mạng MANET như sau:  Phát triển kiến trúc phân tán  Là mạng sử dụng sóng vô tuyến quảng bá  Tối thiểu hóa quản lý tập trung  Sử dụng định tuyến nhớ và chuyển tiếp đa chặng (sử dụng Aloha/CSMA, phổ

trải rộng trong thập kỷ 80 thế kỷ 20) Vào năm 1983, dự án SURAN được phát triển. Động lực thúc đẩy là:

 Xu hướng kích thước thiết bị truyền dẫn ngày càng nhỏ hơn, chí phí giảm, công

suất sóng vô tuyến thấp.

 Hỗ trợ nhiều giao thức sóng vô tuyến phức tạp.  Phát triển và chứng minh được các thuật toán có tính khả mở rộng (scalable

algorithms), mạng có thể có đến 10.000 nút.

 Phát triển và chứng minh sức chịu đựng và khả năng tồn tại chống lại các cuộc tấn công tinh vi. (cải tiến trải phổ rộng, topo mạng phân cấp, tạo nhóm động …) Trong quân đội (Army Research Office-ARO):

 Đầu tiên, họ sử dụng MANET cho các ứng dụng trên mặt đất.  Được sử dụng chính thay cho các mạng có cơ sở hạ tầng cố định.

Trong hải quân (Office of Naval Research-ONR):

 Ban đầu được dùng cho các tàu trên biển.  Mạng MANET trên biển không có mật độ dày như mạng trên đất liền.  Đòi hỏi kết hợp với liên kết vệ tinh.

Trong lực lượng không quân:

 Khảo sát sử dụng những máy bay để cung cấp truyền thông với các trạm mặt đất.

Ứng dụng của mạng MANET

Truyền dữ liệu không dây di động có những bước tiến cả về công nghệ và khả năng sử dụng, động lực thúc đẩy là sự phát triển mạnh mẽ của Internet và sự thành công của thế hệ hệ thống di động thứ hai (2G), thế hệ hệ thống di động thứ ba (3G). Dự kiến trong tương lai gần, vai trò truyền dữ liệu khoảng cách ngắn sẽ phát triển, là một phần bổ sung cho truyền thông quy mô lớn truyền thống bởi phần lớn các thiết bị thông tin liên lạc cũng như giao tiếp giữa con người xảy ra ở khoảng cách nhỏ hơn mười mét. Một yếu tố khác thúc đẩy sự phát triển của mạng Ad Hoc là các dải tần số được cấp phép miễn phí đem đến việc sử dụng các công nghệ truyền thông phát triển (như Bluetooth) triển khai dễ dàng và không tốn kém.

Mạng MANET có tiềm năng to lớn cho các ứng dụng thương mại và quân sự, và đặc biệt hữu ích cho việc cung cấp sự hỗ trợ thông tin liên lạc tại những nơi không có cơ sở hạ tầng thông tin liên lạc sẵn có hoặc việc triển khai một cơ sở hạ tầng cố định về mặt kinh tế là không khả thi. Ứng dụng của MANET bao gồm các hoạt động quân sự, cứu trợ khẩn cấp, chăm sóc y tế, hoạt động mạng gia đình, môi trường học thuật và các hoạt động khắc phục thảm họa. Ví dụ về các tình huống thiên tai bao gồm động đất và lũ lụt, nơi các đội cứu hộ cần phải phối hợp với nhau mà không có các mạng cố định sẵn có; các hoạt động quân sự, nơi thông tin liên lạc trong một môi trường thù địch; các doanh nghiệp, nơi nhân viên chia sẻ thông tin trong hội nghị…

Hình 4. Mạng MANET và Sensor không dây [14]

2.2.2. Các đặc điểm của mạng MANET

Trong mạng AD HOC, các nút là di động và được trang bị các bộ phát và bộ nhận không dây sử dụng các loại ăng ten đẳng hướng để phát quảng bá hoặc ăng ten định hướng để phát điểm-điểm, có thể điều chỉnh được, hoặc kết hợp các loại ăng ten này. Tại một thời điểm, tùy thuộc vào vị trí của nút và dạng bao phủ của bộ nhận và phát tín hiệu, mức công suất phát và các mức giao thoa cùng kênh, kết nối không dây giữa các nút có dạng ngẫu nhiên, đồ thị đa chặng. Cấu hình này thay đổi theo thời gian do các nút di chuyển hoặc điều chỉnh các thông số phát và nhận sóng.

Mạng MANET có một số đặc điểm nổi bật có ảnh hưởng tới thiết kế và hiệu

suất của các giao thức trong mạng được trình bày dưới đây:

1. Cấu hình mạng động: Các nốt di chuyển tự do, do vậy cấu hình mạng gồm nhiều chặng có thể thay đổi ngẫu nhiên và liên tục tại bất kì thời điểm nào, và có thể bao gồm cả liên kết song hướng và một hướng.

2. Các liên kết với dung lượng thay đổi - băng tần hạn chế: Các liên kết vô tuyến có dung lượng thấp hơn nhiều so với các liên kết hữu tuyến tương ứng. Ngoài ra, thông lượng thực của liên kết vô tuyến sau khi tính toán ảnh hưởng của đa truy nhập, fading, tạp âm và nhiễu... thường nhỏ hơn nhiều so với tốc độ truyền dẫn tối đa. Dung lượng thấp thường gây ra vấn đề tắc nghẽn, nghĩa là lưu lượng tổng thường vượt quá dung lượng của mạng.

3. Hoạt động tiết kiệm năng lượng: Một số hoặc tất cả các nút trong mạng MANET có thể dùng pin làm nguồn cung cấp năng lượng hoạt động. Đối với các nút này, tiêu chí thiết kế hệ thống quan trọng nhất của việc tối ưu hóa là vấn đề tiết kiệm năng lượng. Để thực hiện tiêu chí này, các nút trong mạng Ad Hoc bị hạn chế về khả năng tính toán của CPU, kích thước bộ nhớ, khả năng xử lý tín hiệu, và mức năng lượng phát và nhận sóng.

4. Bảo mật vật lý hạn chế: Đối với các mạng di động vô tuyến, khả năng bị nghe trộm, giả mạo và tấn công từ chối dịch vụ DOS (denial-of-service) cần được xem xét cẩn thận. Các kỹ thuật bảo mật cần được triển khai trên nhiều tầng giao thức để làm giảm các nguy cơ bảo mật.

2.2.3. Phân loại

2.2.3.1. Phân loại mạng MANET theo cách thức định tuyến

Mạng MANET định tuyến một chặng (Single-hop)

Mạng MANET định tuyến một chặng là loại mô hình mạng Ad Hoc đơn giản nhất, trong đó, tất cả các nút đều nằm trong cùng một vùng phủ sóng, nghĩa là các nút có thể kết nối trực tiếp với các nút khác mà không cần thông qua các nút trung gian.

Trong mô hình này, các nút có thể di chuyển tự do nhưng chỉ trong một phạm

vi nhất định đủ để nút có thể liên lạc trực tiếp với các node khác trong mạng.

Hình 5. Định tuyến Single-hop

Mạng MANET định tuyến đa chặng Multi-hop

Đây là mô hình phổ biến nhất trong mạng MANET, mô hình này khác với mô hình trước là các nút có thể kết nối với các nút khác trong mạng mà có thể không cần phải có kết nối trực tiếp với nhau. Các nút có thể định tuyến đến nút khác thông qua các nút trung gian trong mạng. Để mô hình này có thể hoạt động một cách hoàn hảo thì cần phải có các giao thức định tuyến phù hợp với mô hình mạng MANET.

Hình 6. Định tuyến Multi-hop

Mô hình MANET định tuyến Mobile Multi-hop

Mô hình này là sự mở rộng của mô hình thứ hai với một chút khác biệt: mô

hình này tập trung vào các ứng dụng có tính chất thời gian thực như audio, video.

2.2.3.2. Phân loại mạng MANET theo chức năng của Nút

Mạng MANET đẳng cấp (Flat MANET)

Trong kiến trúc này, tất cả các nút có vai trò ngang hàng với nhau (peer-to- peer) và các nút cũng đóng vai trò như các router dùng để định tuyến các gói dữ liệu truyền trên mạng. Trong những mạng lớn thì kiến trúc Flat không tối ưu cho việc sử dụng tài nguyên băng thông của mạng vì những thông báo điều khiển (control message) phải truyền trên toàn bộ mạng. Tuy nhiên, nó thích hợp trong những cấu hình mà các nút di chuyển nhiều. Mạng MANET phân cấp (Hierarchical MANET)

Đây là mô hình mạng được sử dụng phổ biến nhất trong mạng MANET. Trong kiến trúc này, mạng chia làm các domain, trong mỗi domain bao gồm một hoặc nhiều cluster với mỗi cluster bao gồm một hoặc nhiều nút. Do đó, nút trong kiến trúc này chia làm hai loại:

 Master node là node quản trị một cluster và có nhiệm vụ chuyển dữ liệu của các nút trong cluster đến các nút trong các cluster khác và ngược lại. Nói cách khác, nó có chức năng như một gateway.

 Normal node là các nút nằm trong cùng một cluster và chỉ có thể kết nối với các nút trong cùng một cluster hoặc kết nối với các nút trong các cluster khác thông qua master node.

Hình 7. Mạng MANET phân cấp

Với các cơ chế trên, mạng sử dụng tài nguyên băng thông mạng hiệu quả hơn vì các thông báo điều khiển chỉ phải truyền trong một cluster. Tuy nhiên, việc quản lý tính chuyển động của các nút trở nên phức tạp hơn. Kiến trúc mạng phân cấp thích hợp cho các mạng có tính chuyển động thấp. Mạng MANET kết hợp (Aggregate MANET)

Trong kiến trúc mạng này, mạng phân thành các zone và các nút được chia vào trong các zone. Mỗi nút bao gồm hai mức topo (topology ): topo mức thấp (node level) và topo mức cao (zone level) (high level topology).

Ngoài ra, mỗi nút còn đặc trưng bởi hai ID: node ID và zone ID. Trong một

zone có thể áp dụng kiến trúc đẳng cấp hoặc kiến trúc phân cấp.

Hình 8. Mạng MANET kết hợp

Vấn đề định tuyến trong mạng MANET

Trên thực tế trước khi một gói tin đến được đích, nó có thể phải được truyền qua nhiều chặng, như vậy cần có một giao thức định tuyến để tìm đường đi từ nguồn tới đích qua hệ thống mạng. Giao thức định tuyến có hai chức năng chính, lựa chọn các tuyến đường cho các cặp nguồn-đích và phân phối các gói tin đến đích chính xác.

Truyền thông trong mạng MANET dựa trên các đường đi đa chặng và mọi nút mạng đều 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, do vậy đị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 chỉ nghiên cứu sâu vấn đề định tuyến trong mạng MANET 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.

Chương 3: CÁC GIAO THỨC ĐỊNH TUYẾN TRONG MẠNG MANET

Chương 3 trình bày vấn đề định tuyến trong mạng có dây truyền thống cùng những yêu cầu chung đối với các thuật toán trong mạng MANET để giải thích cho việc tạo và sử dụng những thuật toán định tuyến mới phù hợp với những đặc điểm của mạng MANET.

3.1. Các giao thức định tuyến phổ biến trong mạng có dây truyền thống

Định tuyến là việc tìm đường đi từ nguồn tới đích qua hệ thống mạng. Giao thức định tuyến có chức năng chính là lựa chọn đường cho các cặp nguồn-đích và phân phát gói tin tới đích chính xác. Với đặc điểm tỉ lệ lỗi gói tin thấp, cấu hình ít thay đổi và thay đổi chậm truyền thông trong mạng có dây truyền thống có thể áp dụng các thuật toán định tuyến dựa trên bảng là giải thuật trạng thái liên kết (Link State Routing) hoặc véc tơ khoảng cách (Distance Vector Routing). Thuật toán Link State được sử dụng trong giao thức OLSF (Open Shortest Path First) của Internet. Thuật toán Distance Vector còn được gọi là thuật toán Bellman-Ford, được dùng trong mạng ARPANET lúc mới ra đời và được sử dụng trong mạng Internet với tên gọi là RIP (Routing Information Protocol). Các giao thức định tuyến truyền thống cũng sử dụng định tuyến nguồn (Source Routing) và kỹ thuật flooding để tìm đường đi cho các gói tin trong mạng.

3.1.1. Distance Vector

Trong Distance Vector mỗi nút chỉ theo dõi chi phí của các liên kết đi ra của nó, nhưng thay vì quảng bá thông tin này đến tất cả các nút, nó quảng bá định kỳ đến các hàng xóm của nó một ước tính các khoảng cách ngắn nhất đến tất cả các nút khác trong mạng. Các nút nhận sau đó sử dụng thông tin này để tính toán lại các bảng định tuyến, bằng cách sử dụng thuật toán đường đi ngắn nhất.

So với Link State, Distance Vector tính toán hiệu quả hơn, dễ dàng hơn để thực hiện và đòi hỏi không gian lưu trữ ít hơn nhiều. Tuy nhiên, Distance Vector có thể gây ra sự hình thành các vòng lặp định tuyến ngắn và dài. Nguyên nhân chính cho việc này là các nút chọn chặng tiếp theo của chúng một cách hoàn toàn dựa trên thông tin có thể là cũ.

3.1.2. Link State

Trong định tuyến Link State, mỗi nút duy trì một khung nhìn đầy đủ về cấu hình mạng với chi phí cho từng liên kết. Để giữ cho các chi phí này phù hợp, mỗi nút quảng bá định kỳ các chi phí liên kết của các liên kết đi ra của nó cho tất cả các nút khác bằng cách sử dụng kỹ thuật flooding. Khi một nút nhận thông tin này, nó cập nhật khung nhìn của nó về mạng và áp dụng thuật toán tìm đường đi ngắn nhất để chọn chặng tiếp theo cho từng đích đến.

Một số chi phí liên kết trong một khung nhìn của nút có thể không xác định được do độ trễ lan truyền lớn, mạng phân vùng… như vậy không phù hợp với khung nhìn cấu hình mạng có thể dẫn đến hình thành các vòng lặp định tuyến. Tuy nhiên, những vòng lặp là ngắn, vì các gói tin sẽ bị loại bỏ nếu đi quá một số chặng nhất định trong mạng.

3.1.3. Source Routing

Source routing có nghĩa là mỗi gói tin phải mang theo đường dẫn đầy đủ mà gói tin nên đi trong mạng trong tiêu đề của nó, khi đó các nút trung gian chỉ việc chuyển tiếp các gói tin theo đường dẫn đó. Như vậy, việc xác định đường dẫn đầy đủ (định tuyến) được thực hiện tại nút nguồn. Ưu điểm của phương pháp này là loại bỏ nhu cầu quảng cáo đường định kỳ, các gói tin phát hiện hàng xóm và nó rất dễ dàng tránh các vòng lặp định tuyến. Vấn đề lớn nhất với định tuyến nguồn là khi mạng lớn và đường đi dài, việc đặt toàn bộ đường trong tiêu đề gói tin sẽ làm lãng phí băng thông.

3.1.4. Kỹ thuật Flooding

Nhiều giao thức định tuyến sử dụng quảng bá để phân phối thông tin điều khiển, có nghĩa là, gửi thông tin điều khiển từ nút nguồn gốc cho tất cả các nút khác. Một hình thức quảng bá được sử dụng rộng rãi là kỹ thuật flooding hoạt động như sau. Nút nguồn gửi thông tin của nó cho các nút hàng xóm. Những nút hàng xóm sẽ chuyển tiếp cho hàng xóm của chúng và cứ tiếp tục như vậy, cho đến khi các gói tin đến được tất cả các nút trong mạng. Một nút sẽ chỉ chuyển tiếp một gói một lần và để đảm bảo điều này một số kiểu số thứ tự có thể được sử dụng. Số thứ tự này được tăng lên khi mỗi gói tin mới được một nút gửi.

3.2. Các yêu cầu đối với thuật toán định tuyến trong mạng MANET

3.2.1. Mục tiêu thiết kế các giao thức định tuyến cho mạng MANET

Như ta đã biết, các đặc tính xác định của mạng ad hoc bao gồm các thiết bị có tài nguyên hạn chế, băng thông thấp, tỷ lệ lỗi cao và topo động. Trong số các nguồn tài nguyên của nút mạng, năng lượng pin thường là bị ràng buộc nhất. Do đó, mục tiêu thiết kế điển hình cho các giao thức định tuyến mạng Ad Hoc thường bao gồm:

 Phụ tải điều khiển tối thiểu (Minimal control overhead). Kiểm soát việc gửi gói tin để tiết kiệm băng thông, chi phí xử lý và năng lượng pin cho cả việc truyền và nhận gói tin. Bởi vì sử dụng băng thông là một phần chi phí, giao thức định tuyến không nên gửi nhiều hơn số lượng tối thiểu các thông báo điều khiển cần cho các hoạt động, và cần được thiết kế sao cho con số này là tương đối nhỏ. Trong khi truyền năng lượng tiêu thụ gấp nhiều lần khi nhận, do đó việc giảm kiểm soát thông báo cũng giúp bảo tồn năng lượng pin.

 Phụ tải xử lý tối thiểu (Minimal processing overhead). Các thuật toán tính toán phức tạp đòi hỏi nhiều chu trình xử lý trong các thiết bị. Các chu trình xử lý làm cho các thiết bị di động sử dụng nguồn tài nguyên, tiêu thụ nhiều năng lượng pin. Các giao thức đơn giản với yêu cầu quá trình xử lý tối thiểu từ thiết bị di

động dẫn đến năng lượng pin được dự trữ cho các nhiệm vụ theo định hướng người sử dụng nhiều hơn, đồng thời kéo dài tuổi thọ pin.

 Khả năng định tuyến đa chặng (Multihop routing capability). Phạm vi truyền dẫn không dây của các nút di động thường được giới hạn, các nguồn và đích có thể không nằm trong phạm vi truyền dẫn trực tiếp của nhau. Do đó, các giao thức định tuyến phải có khả năng khám phá các tuyến đường đa chặng giữa nguồn và đích để giao tiếp giữa các nút là có thể xảy ra.

3.2.2. Áp dụng các thuật toán định tuyến truyền thống trong mạng MANET

Các giao thức truyền thống như Distance Vector Routing hay Link State Routing được sử dụng trong các mạng truyền thống với tỉ lệ lỗi gói tin thấp, băng thông lớn, cấu hình ít thay đổi và thay đổi chậm. Ngược lại, những đặc điểm nổi bật của mạng MANET là tỉ lệ lỗi gói tin cao, băng thông thấp, cấu hình động. Vậy chúng ta có thể sử dụng các giao thức truyền thống Distance Vector Routing hay Link State Routing để định tuyến trong mạng Ad Hoc không? Câu trả lời là không, vì các lý do sau:

 Thứ nhất, Link State và Distance Vector được thiết kế cho một topo tĩnh, có nghĩa là chúng sẽ gặp vấn đề về tính hội tụ về trạng thái ổn định cấu hình mạng ad hoc thường xuyên thay đổi. Link State và distance vector sẽ làm việc rất tốt trong một ad hoc có tính di động thấp, tức là một mạng mà ở đó topo không thay đổi thường xuyên. Vấn đề tồn tại là link-state và distance vector phụ thuộc nhiều vào các thông báo kiểm soát định kỳ. Mà số lượng các nút mạng lớn dẫn đến số lượng các đích đến cũng lớn. Điều này đòi hỏi trao đổi dữ liệu lớn và thường xuyên giữa các nút mạng, mâu thuẫn với thực tế là tất cả các thông tin cập nhật trong một mạng ad hoc kết nối không dây được truyền qua không khí và do đó tốn kém các tài nguyên như băng thông, năng lượng pin và thời gian CPU. Bởi vì cả link-state và distance vector cố gắng để duy trì các tuyến đường cho tất cả các đích đến có thể truy cập, điều này cần thiết để duy trì các tuyến đường và cũng làm lãng phí nguồn tài nguyên.

 Thứ hai, một đặc trưng khác của các giao thức truyền thống là chúng giả định các liên kết là theo hai hướng cân xứng, ví dụ: việc truyền giữa hai host hoạt động tốt như nhau trong cả hai hướng. Trong môi trường vô tuyến không dây điều này không luôn luôn đúng như vậy. Như đã trình bày ở trên, các giao thức định tuyến truyền thống như Link State và Distance Vector không thể áp dụng trong mạng MANET vì chúng được thiết kế cho mạng có topo tĩnh và các liên kết là liên kết đối xứng. Vì vậy, khi thiết kế các giao thức định tuyến mới cho mạng MANET ta cần phải xem xét các yêu cầu sau đây:

1. Phù hợp với topo động của mạng: Thuật toán phải được thiết kế sao cho phù

hợp với tính động của topo mạng và các liên kết bất đối xứng.

2. Không để xảy ra hiện tượng lặp định tuyến: Giải pháp đưa ra có thể là sử dụng bộ đếm chặng trong mỗi gói tin. Mỗi khi gói tin di chuyển đến một nút mạng mới, bộ đếm chặng sẽ tăng thêm một, và đến một giá trị nào đó thì gói tin sẽ bị loại bỏ.

3. Chi phí tìm đường thấp: Tổng số gói tin tìm đường thấp và thời gian cần thiết để tìm được đường đi nhỏ là những yêu cầu quan trọng đối với vấn đề định tuyến trong mạng không dây.

4. Bảo mật: Giao thức định tuyến của mạng Ad Hoc có thể bị tấn công dễ dàng ở một số dạng như đưa ra các cập nhật định tuyến không chính xác hoặc ngăn cản việc chuyển tiếp gói tin, gián tiếp gây ra việc từ chối dịch vụ dẫn đến gói tin không bao giờ đến được đích. Chúng cũng có thể thay đổi thông tin định tuyến trong mạng, cho dù các thông tin đó là không nguy hiểm nhưng cũng gây tốn băng thông và năng lượng, vốn là những tài nguyên ”quý hiếm” trong mạng ad hoc. Do vậy cần có những phương pháp bảo mật thích hợp để ngăn chặn việc sửa đổi hoạt động của giao thức.

5. Hoạt động phân tán: Cách tiếp cận tập trung cho mạng ad hoc sẽ thất bại do sẽ tốn rất nhiều thời gian để tập hợp các thông tin trạng thái hiện tại của mạng để tính toán rồi lại phát tán lại nó cho các nút mạng. Trong thời gian đó, cấu hình mạng có thể đã thay đổi rất nhiều.

6. Thiết lập những cụm mạng nhỏ: Nếu giao thức định tuyến có thể xác định được các nút mạng gần nhau và thiết lập chúng thành một cụm mạng nhỏ thì sẽ rất thuận tiện trong định tuyến. Nếu các nút mạng đơn di chuyển nhanh hơn thì các cụm mạng lại ổn định hơn. Do đó, định tuyến trong các cụm mạng sẽ đơn giản hơn rất nhiều. Vấn đề đặt ra là làm thế nào để đồng thời đạt được một số trong các yêu cầu nêu trên khi chúng có thể mâu thuẫn với nhau? Ta xét yêu cầu thứ nhất và yêu cầu thứ ba, dễ thấy theo yêu cầu thứ nhất thuật toán phải hoạt động tốt trong điều kiện topo của mạng thay đổi liên tục khi đó các nút mạng di chuyển liên tục dẫn đến số gói tin dùng tìm đường từ các cặp nguồn-đích nhiều hơn đồng thời làm tăng thời gian tìm đường, điều này mâu thuẫn với yêu cầu thứ ba. Chính vì vậy, ta cần đánh giá ảnh hưởng của mức độ linh động của các nút mạng đến hiệu quả của các giao thức định tuyến. Để từ đó:

 Đề xuất chọn sử dụng giao thức định tuyến thích hợp với mức độ linh hoạt của

mạng cụ thể.

 Có thể điều chỉnh (tinh chỉnh) các tham số hoạt động của các giao thức định

tuyến cho tối ưu.

3.3. Phân loại các giao thức định tuyến cho MANET [16]

Các giao thức định tuyến trong mạng MANET ra đời bằng cách cải tiến, bổ sung và kết hợp các thuật toán của các giao thức định tuyến truyền thống (Link State Routing, Distance Vector Routing, Source Routing) với nhau. Dưới đây tôi trình bày sơ lược về bốn giao thức định tuyến DSDV, OLSR, AODV và DSR được trình bày trong luận văn.

Destination-Sequenced Distance-Vector Routing (DSDV) là giao thức định tuyến bảng cho các mạng ad hoc dựa trên thuật toán Bellman-Ford. Nó được phát triển bởi C. Perkins và P.Bhagwat vào năm 1994. Đóng góp chính của thuật toán là giải quyết vấn đề lặp định tuyến.

Optimized Link State Routing Protocol (OLSR) là giao thức định tuyến IP tối ưu hóa cho các mạng ad hoc đặc biệt. Nó thuộc nhóm giao thức định tuyến chủ ứng dựa trên trạng thái liên kết, sử dụng thông báo Hello and Topology Control (TC) để tìm và sau đó lan truyền thông tin trạng thái liên kết trong toàn mạng. Từng nút sử dụng thông tin topo mạng để tính toán những chặng tiếp theo đến mọi đích trong mạng theo đường đi có số chặng chuyển tiếp nhỏ nhất.

Ad hoc On-Demand Distance Vector (AODV) là giao thức định tuyến cho các mạng MANET. Nó được phát triển bởi trung tâm nghiên cứu Nokia, Đại học California, Santa Barbara và Đại học Cincinnati bởi Perkins, E. Belding-Royer và S. Das. AODV là giao thức định tuyến phản ứng, nó thiết lập một tuyến đường đến đích khi có yêu cầu. Cũng giống như DSDV, AODV sử dụng số sequence number để cập nhật tuyến đường để tránh vấn đề lặp định tuyến.

Dynamic Source Routing (DSR) là giao thức định tuyến cho các mạng ad hoc. Tương tự như AODV, DSR là định tuyến theo yêu cầu. Tuy nhiên, nó sử dụng định tuyến nguồn thay vì sử dụng bảng định tuyến tại từng điểm trung gian.

3.3.1. Các khái niệm liên quan

3.3.1.1. Định tuyến chủ ứng và định tuyến phản ứng

Định tuyến chủ ứng (Proactive routing) là phương pháp định tuyến của các giao thức mà đường tới tất cả các đích được tính toán trước. Các thông tin định tuyến được cập nhật định kỳ hoặc bất cứ khi nào cấu hình mạng thay đổi. Ưu điểm của phương pháp là độ trễ phát gói tin thấp. Tuy nhiên, một số đường không cần dùng đến và việc truyền các thông điệp định kỳ tiêu tốn băng thông khi mạng thay đổi nhanh.

Định tuyến phản ứng (Reactive routing) là phương pháp định tuyến theo yêu cầu. Đường tới đích không được tính toán trước và chỉ được xác định khi cần đến. Quá trình phát hiện liên kết bị hỏng và xây dựng lại đường được gọi là quá trình duy trì đường. Ưu điểm của định tuyến phản ứng là hạn chế được băng thông do chỉ cần đường tới các đích cần thiết và loại bỏ các cập nhật định kỳ. Tuy nhiên, vấn đề với phương pháp là độ trễ lớn trước khi phát do việc phát hiện đường.

3.3.1.2. Cập nhật định kỳ và cập nhật theo sự kiện

Cập nhật định kỳ thực hiện bằng việc phát các gói tin định tuyến một cách định kỳ. Kỹ thuật này làm đơn giản hóa các giao thức và cho phép các nút học được về cấu hình và trạng thái của toàn bộ mạng. Tuy nhiên, giá trị quãng thời gian cập nhật là một tham số quan trọng.

Cập nhật theo sự kiện diễn ra khi có sự kiện xảy ra trong mạng như liên kết hỏng hoặc liên kết mới xuất hiện. Khi đó, gói tin cập nhật sẽ được quảng bá và trạng

thái cập nhật được truyền trong toàn bộ mạng. Nhưng khi mạng thay đổi nhanh, số lượng gói tin cập nhật sẽ lớn và có thể gây ra các dao động về đường.

Một số các giao thức sử dụng kết hợp hai cơ chế này như DSDV.

3.3.1.3. Tính toán phi tập trung và tính toán phân tán

Trong giao thức dựa trên tính toán phi tập trung, mọi nút trong mạng duy trì thông tin toàn cục hoàn chỉnh về cấu hình mạng để tính toán các đường đi ngay khi cần. Tính toán đường trong Link state là ví dụ của tính toán phi tập trung. Trong giao thức dựa trên tính toán phân tán, mọi nút trong mạng chỉ duy trì thông tin bộ phận hoặc cục bộ về cấu hình mạng. Khi một đường cần được tính toán, nhiều nút sẽ phối hợp để tính toán đường. Tính toán đường trong Distance vector và phát hiện đường trong các giao thức theo yêu cầu thuộc vào tiếp cận này.

3.3.1.4. Đơn đường và đa đường

Một số giao thức định tuyến tìm một đường duy nhất từ nguồn tới đích. Do đó, giao thức trở lên đơn giản và tiết kiệm được không gian lưu trữ. Tuy nhiên, một số giao thức khác lại áp dụng việc tìm nhiều đường. Mục tiêu của các giao thức này là sự tin cậy và mạnh mẽ.

3.3.2. Phân loại các giao thức định tuyến

Các giao thức định tuyến có thể được phân lớp tùy thuộc vào đặc tính của

chúng. Ta có thể phân lớp theo 3 cách như sau:

Cách đầu tiên để phân loại các giao thức định tuyến là phân chia chúng theo các thuật toán tập trung và phân tán. Trong các thuật toán tập trung, tất cả các lựa chọn tuyến đường được thực hiện tại một nút trung tâm, trong khi ở các thuật toán phân tán, việc tính toán các tuyến đường được chia sẻ giữa các nút mạng.

Cách thứ hai phân loại các giao thức định tuyến liên quan đến sự thích ứng với lưu lượng trên mạng. Trong các thuật toán tĩnh (Static), tuyến đường sử dụng bởi các cặp nguồn-đích được cố định bất kể các điều kiện lưu lượng. Nó chỉ có thể thay đổi để thích ứng với một nút hoặc liên kết bị lỗi. Kiểu thuật toán này không thể đạt được thông lượng cao trong nhiều mô hình đầu vào lưu lượng lớn. Hầu hết các mạng gói tin quan trọng sử dụng một số hình thức định tuyến thích nghi, nơi các tuyến đường được sử dụng để định tuyến giữa các cặp nguồn-đích có thể thay đổi để phản ứng với tắc nghẽn.

Còn cách phân loại thứ ba có liên quan nhiều đến các mạng Ad Hoc là phân loại các thuật toán định tuyến dựa trên cách thông tin định tuyến được tìm thấy và duy trì bởi các nút di động như thế nào, gồm có: định tuyến chủ ứng, định tuyến phản ứng và định tuyến lai. Các giao thức chủ ứng cố gắng để đánh giá liên tục các tuyến đường trong mạng, để khi một gói tin cần được chuyển tiếp, tuyến đường đã được biết và có thể được sử dụng ngay lập tức. Tập hợp các giao thức Distance-Vector là một ví dụ của một giao thức chủ ứng. Các giao thức phản ứng, chỉ gọi một thủ tục xác định lộ trình theo yêu cầu. Vì vậy, khi một tuyến đường được yêu cầu, một số loại thủ tục tìm

kiếm toàn cục được thực hiện. Tập hợp các giao thức sử dụng thuật toán flooding cổ điển thuộc nhóm phản ứng. Các giao thức chủ ứng có lợi thế là khi một tuyến đường được yêu cầu, độ trễ trước khi các gói tin thực có thể được gửi là rất nhỏ. Mặt khác các giao thức chủ ứng cần thời gian để hội tụ về một trạng thái ổn định. Điều này có thể gây ra các vấn đề nếu topo thay đổi thường xuyên.

Trong luận văn này, chúng ta sẽ phân lớp theo cách thứ ba:

Hình 9. Phân loại các giao thức định tuyến trong mạng MANET [13]

3.3.2.1. Destination-Sequence Distance Vector (DSDV)

Giao thức định tuyến DSDV là giao thức định tuyến chủ ứng dựa trên véc tơ khoảng cách theo chặng, được sửa đổi từ giao thức vector khoảng cách để hoạt động của nó phù hợp với mạng MANET. Cơ sở của DSDV là thuật toán Bellman-Ford truyền thống. Vì DSDV là một giao thức chủ ứng nên mỗi nút trong mạng duy trì một bảng định tuyến có chứa chặng tiếp theo và số chặng tới từng đích trong mạng. Để giữ cho các bảng định tuyến được cập nhật, DSDV yêu cầu mỗi nút phát quảng bá định kỳ các cập nhật định tuyến tới các hàng xóm và phát ngay các gói tin cập nhật khi có các thay đổi quan trọng xảy ra trong mạng.

Bảng định tuyến chứa các thông tin sau đây: địa chỉ IP đích, số thứ tự đích, địa chỉ IP chặng tiếp theo, số chặng và thời gian cài đặt. DSDV sử dụng cả cập nhật bảng định tuyến định kỳ và sự kiện thường xuyên. Trong cập nhật định kỳ, ứng với khoảng thời gian cố định, mỗi nút quảng bá đến các hàng xóm số thứ tự hiện tại của nó, cùng với bản cập nhật bảng định tuyến. Các cập nhật bảng định tuyến có dạng:

<địa_chỉ_IP_đích số_thứ_tự_đích số_chặng> Sau khi nhận dữ liệu cập nhật, các nút hàng xóm sẽ sử dụng thông tin này để tính toán các tuyến rồi cập nhật vào bảng định tuyến của mình nhờ các phương pháp lặp vestor khoảng cách.

Ngoài việc cập nhật định kỳ, DSDV cũng sử dụng bảng cập nhật sự kiện thường xuyên được dùng để thông báo thay đổi liên kết quan trọng, chẳng hạn như các

liên kết bị hỏng, một nút nào đó di chuyển... Cập nhật sự kiện thường xuyên được kích hoạt sẽ đảm bảo phát hiện kịp thời các thay đổi đường dẫn định tuyến.

Để tránh lặp định tuyến, DSDV sử dụng số thứ tự gắn với mỗi đường. Số thứ tự cho thấy độ mới của đường. Đường có số thứ tự cao hơn được xem là tốt hơn. Tuy nhiên, hai đường có cùng số thứ tự nhưng đường nào có độ đo tốt hơn thì sẽ tốt hơn. Số thứ tự này được khởi tạo ban đầu bởi nút đích. Mỗi nút trong mạng quảng bá bằng việc tăng đều đặn số thứ tự chẵn của mình. Số thứ tự được tăng lên một khi một nút phát hiện đường tới đích có liên kết hỏng khi không nhận được các cập nhật định kỳ. Trong lần quảng bá đường sau, nút phát hiện liên kết hỏng sẽ quảng bá đường tới đích có số chặng vô hạn và tăng thứ tự đường.

DSDV thực hiện hai tối ưu hóa chính để cải thiện hiệu suất trong các mạng di động. Một là sử dụng hai loại thông điệp cập nhật là: cập nhật đầy đủ (full dump) và cập nhật bổ sung (incremental dump). Cập nhật đầy đủ mang tất cả thông tin định tuyến có trong nút và cập nhật bổ sung chỉ mang các thông tin về những thay đổi từ lần cập nhật đầy đủ gần nhất. Để làm được điều này, DSDV lưu trữ hai bảng khác nhau, một dùng để chuyển tiếp các gói tin, một để phát các gói tin cập nhật bổ sung. Cập nhật đầy đủ được truyền tương đối ít khi các nút ít di chuyển. Còn khi các nút di chuyển thường xuyên, cập nhật đầy đủ được phát trong khi các cập nhật bổ sung sẽ ít đi. Tuy nhiên, khi chỉ có các thay đổi thông thường trong mạng các nút chỉ phát cập nhật bổ sung. Điều này làm giảm chi phí xử lý và tiêu thụ băng thông ít hơn.

Hai là, để tránh sự bùng nổ các cập nhật định tuyến tại các thời điểm cấu hình mạng thay đổi nhanh, DSDV cũng áp dụng cơ chế hãm các cập nhật tức thời khi có các thay đổi xảy ra trong mạng. Bằng việc ghi nhận các quãng thời gian xảy ra những thay đổi về đường, DSDV làm trễ các cập nhật tức thời theo thời gian đó. Thời gian làm trễ thường là thời gian trung bình để có được tất cả các quảng bá cập nhật cho một tuyến đường. Bằng cách này, các nút có thể chắc chắn nhận được tất cả những thay đổi đường dẫn định tuyến đến một đích trước khi lan truyền bất cứ thay đổi nào. Điều này làm giảm việc sử dụng băng thông và tiêu thụ điện năng của các nút hàng xóm.

3.3.2.2. Optimized Link State Routing Protocol (OLSR)

OLSR là giao thức định tuyến chủ ứng dựa trên trạng thái liên kết. Sự khác nhau giữa OLSR và định tuyến link state trong mạng có dây là OLSR dựa trên các chuyển tiếp đa điểm (MultiPoint Relays - MPRs) để giảm chi phí flooding mạng và kích thước của các gói tin cập nhật link state. Các điểm chuyển tiếp MPR là số tối thiểu các nút trong số các hàng xóm trực tiếp có thể chuyển tiếp các gói tin của nút tới các nút xa hơn. Ý tưởng của chuyển tiếp đa điểm là tối thiểu hóa việc phát tràn các thông điệp quảng bá trong mạng.

Hình 10. Tập chuyển tiếp đa điểm MPRs (S là nút nguồn, các nút được tô đậm là các nút MPR)

Mỗi nút tính MPRs của nó từ tập các hàng xóm của nó. Tập MPR được chọn như vậy khi một nút quảng bá một thông báo, các truyền tiếp của thông báo đó bằng tập MPR sẽ đảm bảo rằng thông điệp được nhận bởi mỗi nút có số chặng bằng 2. Do đó, bất cứ khi nào một nút quảng bá một thông báo, chỉ có những người hàng xóm trong tập MPR của nó phát quảng bá lại thông báo đó. Các hàng xóm không trong tập MPR thì chỉ xử lý thông báo nhưng không phát quảng bá lại nó. Hơn nữa, khi trao đổi thông tin định tuyến link state, một nút chỉ liệt kê các liên kết của nó cho những hàng xóm rằng đã chọn chúng như là một MPR. Tập các hàng xóm được gọi là MPR Selectors.

Hình 11. Định tuyến Link State và định tuyến cải tiến trong OLSR

OLSR sử dụng hai loại thông điệp điều khiển HELLO và TC (Topology Control). Thông điệp HELLO được phát định kỳ để cảm nhận trạng thái liên kết với các hàng xóm, và xây dựng nên tập MPR. Thông điệp HELLO chỉ được gửi đi một chặng nhưng thông điệp TC được quảng bá trong toàn mạng. Các thông điệp TC được dùng để quảng bá thông tin về danh sách các MPR của mỗi nút và được phát định kỳ. Tuy nhiên, chỉ các nút trong tập MPR mới chuyển tiếp các thông điệp TC.

Mỗi nút duy trì một bảng định tuyến được xây dựng từ thông tin cấu hình trong các thông điệp TC và thông tin liên kết cục bộ trong các thông điệp HELLO. Khi có bất cứ thay đổi nào trong các thông tin này, bảng định tuyến được tính toán lại. Do

OLSR là giao thức chủ ứng, bảng định tuyến có chứa đường đi tới tất cả các nút trong mạng. Các đường đi trong bảng định tuyến được tính dựa trên giải thuật đường đi ngắn nhất, như là một biến thể của thuật toán Dijkstra.

3.3.2.3. Ad hoc On-demand Distance Vector Routing (AODV)

Một mạng adhoc là sự tham gia hợp tác của một tập hợp các nút di động không có sự can thiệp cần thiết của bất kỳ điểm truy cập tập trung hoặc cơ sở hạ tầng có sẵn. AODV là một thuật toán mới cho hoạt động mạng adhoc. Mỗi nút di động hoạt động như một router chuyên biệt. AODV cung cấp các tuyến đường không có vòng lặp kể cả trong khi sửa chữa các liên kết bị hỏng. Giao thức này không yêu cầu các quảng bá định tuyến định kỳ toàn mạng, nên nhu cầu về băng thông sẵn có cho các nút di động là ít hơn đáng kể so với những giao thức đòi hỏi phải quảng bá toàn mạng.

AODV sử dụng liên kết đối xứng giữa các nút hàng xóm. Nó không cố gắng đi theo các đường dẫn giữa các nút khi một trong các nút không thể “nghe thấy” một nút khác. Với những nút không nằm trên tuyến đường hoạt động, chúng không duy trì bất kỳ thông tin định tuyến và cũng không tham gia vào bất kỳ trao đổi bảng định tuyến định kỳ. Hơn nữa, một nút không thể phát hiện và duy trì một tuyến đường đến một nút khác cho đến khi cả hai cần giao tiếp với nhau, trừ khi nút đó đưa ra những dịch vụ của nó như một trạm chuyển tiếp trung gian để duy trì kết nối giữa hai nút khác. Khi kết nối cục bộ của nút di động được quan tâm, mỗi nút di động có thể nằm trong “hiểu biết” của các nút khác trong lân cận của các nút đó bằng việc sử dụng một vài kỹ thuật, bao gồm quảng bá cục bộ như thông điệp Hello. Các bảng định tuyến của các nút trong lân cận được tổ chức để tối ưu hóa thời gian phản ứng các di chuyển cục bộ và cung cấp thời gian phản ứng nhanh cho các yêu cầu thành lập các tuyến đường mới.

Những mục tiêu chính của thuật toán bao gồm:

 Quảng bá quá trình tìm đường bằng các gói tin chỉ khi cần thiết.  Phân biệt sự dò tìm trong vùng lân cận để quản lý kết nối cục bộ và duy trì cấu

hình mạng tổng thể.

 Phổ biến thông tin về những thay đổi trong kết nối cục bộ với những nút di

động lân cận có khả năng cần thông tin. AODV sử dụng cơ chế broadcast route discovery được sử dụng với những điều chỉnh trong thuật toán DSR. Thay vì định tuyến nguồn, AODV dựa vào thiết lập động các bảng tuyến đường tại các nút trung gian. Sự khác biệt này làm cho chi phí trong những mạng có nhiều nút giảm xuống vì loại bỏ phụ tải lớn do truyền từng gói tin dữ liệu chứa các tuyến đường nguồn trong tiêu đề gói tin.

Để duy trì thông tin định tuyến mới nhất giữa các nút, ta sử dụng khái niệm về số thứ tự đích từ DSDV. Không giống như trong DSDV, mỗi nút duy trì một số tăng đơn điệu được sử dụng để loại bỏ các tuyến đường được lưu trữ đã cũ. Sự kết hợp của những kỹ thuật này đem đến một thuật toán sử dụng băng thông hiệu quả bằng cách giảm thiểu các tải mạng dùng cho điều khiển, và lưu lượng dữ liệu đáp ứng được với những thay đổi trong cấu hình mạng.

AODV sử dụng các thông điệp khác nhau để phát hiện và duy trì các liên kết. Khi có yêu cầu về đường, nếu đường chưa được biết hoặc đã quá hạn, nút quảng bá thông điệp yêu cầu tìm đường Route REQuest (RREQ) tới tất cả các hàng xóm. RREQ được phát đi toàn mạng cho tới khi đến được đích hoặc một nút có đường đi tới đích. Trên đường đi qua mạng, RREQ khởi tạo đường quay trở về nguồn tạm thời tại các nút đi qua. Nút cũng lưu trữ định danh của các RREQ đã nhận để loại bỏ các RREQ được nhận lại.

Một RREQ chứa các thông tin sau đây:

Các cặp nhận biết duy nhất một RREQ. broadcast_id được tăng lên bất cứ khi nào nguồn phát một RREQ mới. Mỗi hàng xóm hoặc thỏa mãn gói tin RREQ bằng cách gửi một gói tin Route REPly (RREP) trở về nguồn, hoặc quảng bá gói tin RREQ đến hàng xóm của mình sau khi tăng số hop_cnt.

Khi RREQ tới đích hoặc nút có đường hợp lệ tới đích, gói tin trả lời RREP được khởi tạo và gửi quay trở lại nút nguồn qua đường đi đã được thiết lập bởi RREQ. Trong quá trình đó, RREP thiết lập đường hướng tới đích tại các nút chuyển tiếp. Khi RREP tới được nguồn, đường từ nguồn tới đích đã được thiết lập. Nếu nút nguồn không nhận được RREP trong khoảng thời gian ít nhất là đủ thời gian cho các RREQ đi qua mạng và tạo một trả lời cho nơi gửi, nút nguồn sẽ gửi lại RREQ hoặc giả thiết là không có đường tới đích.

Một RREP chứa các thông tin sau:

Để cảm nhận liên kết, AODV sử dụng các thông điệp HELLO được quảng bá định kỳ tới các hàng xóm. Thông điệp HELLO cho biết về sự tồn tại của nút và liên kết với nút vẫn hoạt động. Khi thông điệp HELLO không đến từ một hàng xóm trước đó, nút đánh dấu liên kết tới hàng xóm đó là hỏng và thông báo cho các nút bị ảnh hưởng bằng việc gửi thông báo lỗi đường Route ERRor (RERR). Trong cài đặt, việc phát hiện liên kết lỗi có thể thực hiện bởi lớp vật lý hoặc lớp liên kết.

Hình 12. AODV tìm kiếm và duy trì tuyến đường

3.3.2.4. Dynamic Source Routing (DSR) [12]

Giao thức DSR là một giao thức định tuyến đơn giản và hiệu quả được thiết kế riêng cho việc sử dụng trong các mạng ad hoc không dây đa chặng với các nút di động. Sử dụng DSR, mạng hoàn toàn tự tổ chức và tự cấu hình, không cần cơ sở hạ tầng mạng sẵn có hoặc quản trị trung tâm. Các nút mạng hợp tác để chuyển tiếp các gói tin

cho nhau từ đó cho phép giao tiếp qua nhiều “chặng” giữa những nút không trực tiếp nằm trong phạm vi truyền dẫn không dây của nút khác. Khi các nút trong mạng lưới di chuyển xung quanh hoặc gia nhập hoặc rời khỏi mạng, hoặc các điều kiện truyền dẫn không dây như các nguồn nhiễu thay đổi, thì tất cả định tuyến được tự động xác định và duy trì bởi các giao thức định tuyến DSR. Vì số lượng các chặng trung gian cần để đến được đích đến bất kỳ có thể thay đổi bất cứ khi nào, nên topo mạng có thể được thay đổi khá đa dạng và nhanh chóng.

Giao thức DSR là giao thức phản ứng dựa trên định tuyến nguồn, nó cho phép các nút tìm kiếm tự động một tuyến đường nguồn qua nhiều chặng đến đích bất kỳ trong mạng ad hoc. Mỗi gói tin dữ liệu gửi đi mang trong tiêu đề của nó danh sách xếp thứ tự đầy đủ các nút mà nó phải đi qua, cho phép định tuyến gói tin ở các nút trung gian có thể thực hiện nhanh chóng không có vòng lặp và tránh yêu cầu phải cập nhật thông tin định tuyến tại các nút trung gian mà các gói tin được chuyển tiếp. Bằng cách thêm tuyến đường nguồn trong header của mỗi gói dữ liệu, các nút đang chuyển tiếp hoặc đang nghe bất kỳ gói tin nào trong các gói tin đó có thể dễ dàng lưu giữ thông tin định tuyến để sử dụng trong tương lai.

Giao thức DSR gồm có hai cơ chế làm việc cùng nhau cho phép tìm kiếm và

duy trì các tuyến đường nguồn trong mạng ad hoc:

 Route discovery (Cơ chế tìm kiếm tuyến đường): Là cơ chế mà theo đó một nút nguồn S có nhu cầu gửi một gói tin đến một node đích D có được một tuyến đường từ nguồn đến nút đích D. Route discovery được sử dụng chỉ khi S cố gắng gửi một gói tin đến D mà không thực sự biết một tuyến đường đến D. Route discovery hoạt động như sau: Mỗi nút duy trì một bộ nhớ route cache có chứa các tuyến đường đi đã biết. Khi tuyến đường được cần đến không có trong route cache, Route discovery được khởi tạo bằng việc phát gói tin yêu cầu đường Route Request. Khi một nút nhận được gói tin yêu cầu đường, nút tìm trong route cache đường tới đích được yêu cầu. Nếu đường trong route cache không tìm thấy, nút chuyển tiếp gói tin yêu cầu đường cho các hàng xóm sau khi bổ sung địa chỉ vào thứ tự các chặng được lưu trong gói tin yêu cầu đường. Gói tin yêu cầu đường được truyền qua mạng cho tới khi đến đích hoặc nút có đường đi tới đích. Nếu đường được tìm thấy, gói tin trả lời (Route Reply) có chứa thứ tự các chặng tới đích được gửi trở lại nguồn.

Hình 13. Ví dụ về Route discovery: nút A là nút nguồn, nút E là nút đích.

 Route maintenance (Cơ chế duy trì tuyến đường): Là cơ chế mà theo đó nút S có thể phát hiện ra hiện tượng: một tuyến đường mà nó đã biết không còn sử dụng được để sửa lại. Tức là trong khi sử dụng một tuyến đường từ nguồn S đến đích D, nếu topo mạng thay đổi khiến S có thể không sử dụng được tuyến đường của nó đến D vì một liên kết trên tuyến đường không còn hoạt đông. Khi đó cơ chế Route maintenance cho biết một tuyến đường nguồn bị đứt liên kết, S có thể cố gắng sử dụng tuyến đường khác bất kỳ có trong bộ nhớ route cache của nó để đến D, hoặc có thể gọi cơ chế Route discovery một lần nữa để tìm kiếm một tuyến đường mới. được sử dụng chỉ khi S thực sự đang gửi các gói tin đến D. Cơ chế Route maintenance bao gồm việc thực hiện các biên nhận theo chặng hoặc đầu cuối, kèm theo đó là phát các gói tin Route Error để thông báo về hiện tượng đứt liên kết. DSR có thể sử dụng lớp MAC để thông báo về hiện tượng đứt liên kết. Trong trường hợp có hiện tượng đứt liên kết, gói tin Route Error được gửi lại cho nút nguồn. Nút nguồn sau đó sẽ xoá bỏ liên kết bị hỏng ra khỏi route cache và tất cả các đường có chứa chặng này được cắt tại điểm có liên kết hỏng. Ngoài ra, các nút trung gian chuyển tiếp gói tin Route Error có thể cập nhật route cache theo cách tương tự.

Hình 14. Ví dụ về Route maintenance:

(nút C không thể chuyển tiếp gói tin từ nút A đến nút E do liên kết giữa C và D bị hỏng) Đặc biệt, không giống như các giao thức khác, DSR không yêu cầu phát các gói tin định tuyến định kỳ trong bất kỳ trường hợp nào, tại bất kỳ tầng nào trong mạng. Ví dụ, DSR không sử dụng quảng bá định tuyến định kỳ, cảm nhận trạng thái liên kết, hoặc các gói tin tìm kiếm nút hàng xóm và không dựa vào các chức năng từ bất kỳ giao thức cơ bản trong mạng. Các thông tin điều khiển của route discovery and route maintenance trong DSR được thiết kế để cho phép các liên kết một chiều và các tuyến đường bất đối xứng được hỗ trợ một cách dễ dàng. Như ta đã biết, trong các mạng không dây có thể xảy ra trường hợp một liên kết giữa hai nút có thể không làm việc tốt như nhau trong cả hai hướng, do khác biệt về ăng ten hoặc các mô hình lan truyền hoặc các nguồn nhiễu. DSR cho phép liên kết một chiều sẽ được sử dụng khi cần thiết, điều này nâng cao hiệu năng tổng thể và tính liên kết mạng trong hệ thống.

3.3.2.5. So sánh các giao thức định tuyến cho MANET

Bảng 4 so sánh độ phức tạp của các giao thức với các tiêu chuẩn:

 Độ phức tạp lưu trữ: kích thước lưu trữ mỗi nút cần để lưu các thông tin cần thiết.  Độ phức tạp thời gian: số các bước cần để thực hiện một hoạt động của giao thức.

 Độ phức tạp truyền thông: số thông điệp cần để thực hiện một hoạt động của

giao thức.

Giao thức Độ phức tạp lưu trữ Độ phức tạp thời gian Độ phức tạp truyền thông

DSDV O(N) O(D) O(N)

OLSR O(MxA) O(D) O(M)

AODV O(Dd) O(2D) O(2N)

DSR O(D) O(2D) O(2N)

Bảng 4: So sánh độ phức tạp của các giao thức định tuyến

Trong đó:

 M: số các nút lựa chọn chuyển tiếp sóng (MPR).  N: Tổng số nút trong mạng.  A: Số trung bình các nút liền kề (các nút hàng xóm).  D: Đường kính mạng (số chặng lớn nhất trong mạng).  Dd: Số các đích giao tiếp lớn nhất.

Bảng 5 và 6 tổng kết và so sánh các đặc điểm của các giao thức:

Vectơ khoảng

Định kỳ và

Vectơ khoảng

Các hàng xóm

Giao thức Thông tin lưu trữ Thời gian cập nhật Thông tin cập nhật Đối tượng cập nhật

cách

theo sự kiện

cách

Nút nguồn

Đường đi

Cơ chế duy trì theo sự

Thông điệp lỗi (route

DSDV

tới các đích có giao tiếp

đường kiện

đường error)

Nút nguồn

Chặng

Cơ chế duy trì theo sự

Thông điệp lỗi (route

DSR

tiếp theo tới mỗi đích có giao tiếp

đường kiện

đường error)

Toàn bộ cấu

Định kỳ

Tất cả các nút

Thông

hình mạng

trong mạng

AODV

điệp Hello: thông tin liên kết cục bộ, xóm và hàng (MPR).

Thông

điệp TC: thông tin về các MPR

OLSR

Bảng 5: So sánh các đặc điểm của các giao thức định tuyến

Trong đó:

 Thông tin lưu trữ: Thông tin được lưu tại mỗi nút.  Thời gian cập nhật: Áp dụng trong các giao thức định tuyến chủ ứng. Các giá trị so sánh là: định kỳ, theo sự kiện và lai (kết hợp cả hai cơ chế). Đối với các giao thức phản ứng, khi liên kết bị hỏng, cơ chế duy trì đường được thực hiện, việc xây dựng lại đường được gọi là hướng sự kiện.

 Thông tin cập nhật: Thông tin về trạng thái liên kết. Đối với các giao thức phản ứng, cơ chế duy trì đường theo sự kiện, thông tin cập nhật là các thông điệp ROUTE-ERROR.

 Đối tượng cập nhật: là các hàng xóm hoặc các nút nguồn bị ảnh hưởng.

Quảng bá tới

Trước,

phân

Một

các hàng xóm

tán

Duy trì đường Giao thức Số đường Phương pháp cập nhật Tính toán đường

đường (đường đi ngắn nhất)

Gửi các cập nhật định kỳ và theo sự kiện

Unicast

Nhiều đường

Xóa

DSDV

đường, thông báo cho nút nguồn

Phản ứng theo yêu cầu, quảng bá thông điệp truy vấn

Unicast

Xóa

Một

DSR

Phản ứng theo yêu cầu, quảng bá thông điệp truy vấn

đường, thông báo tới tất cả các nút nguồn bị ảnh hưởng

đường (đường đầu tiên nhận được bởi trả thông điệp lời)

Gửi các cập

Một

Quảng bá

thực

nhật

Trước, hiện bởi nút

AODV

đường (đường đi ngắn nhất)

OLSR

Bảng 6: So sánh các đặc điểm của các giao thức định tuyến

Trong đó:

 Phương pháp cập nhật: quảng bá hoặc unicast.  Tính toán đường: Khi nào đường được tính toán. Có ba trường hợp: tính toán trước, theo yêu cầu, và lai giữa hai cơ chế. Đối với các giao thức định tuyến trước, việc tính toán có thể thực hiện bởi nút hoặc hợp tác, phân tán giữa các nút. Tuy nhiên, trong các giao thức định tuyến phản ứng, việc tính toán đường thông thường là việc gửi quảng bá thông điệp truy vấn đường được truyền qua toàn mạng để phát hiện đường.

 Số đường: Số đường tìm thấy được lưu trữ.  Duy trì đường: Việc có áp dụng hay không cơ chế duy trì đường trong các

giao thức.

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Ả

Chương 4 trình bày các phương pháp mô phỏng mạng quan trọng từ đó đưa ra lựa chọn phương pháp mô phỏng bằng cách sử dụng công cụ NS-2 là tối ưu nhất trong luận văn. Chương này cũng trình bày công cụ hiển thị trực quan mạng MANET trong quá trình hoạt động là INSPECT. Nội dung chính tiếp theo là việc thiết lập mô phỏng mạng MANET trong NS-2 và các tham số hoạt động của bốn giao thức định tuyến DSDV, OLSR, AODV, DSR trong NS-2.

4.1. Lựa chọn phương pháp và công cụ đánh giá hiệu năng mạng [1]

4.1.1. Lựa chọn phương pháp

Trong quá trình hình thành và phát triển của mạng máy tính từ xưa đến nay, những nhà thiết kế và người nghiên cứu mạng luôn dành sự quan tâm lớn đến vấn đề đánh giá và dự đoán hiệu năng mạng; mục đích chính là để nắm được và cải thiện đặc trưng giá - hiệu năng. Xuyên suốt trong quá trình thiết kế - xây dựng - vận hành - bảo trì hệ thống mạng, ngay từ giai đoạn bắt đầu cho đến khi mạng đã được lắp đặt và đưa vào hoạt động thì yêu cầu đánh giá và dự đoán hiệu năng mạng luôn song hành. Trong giai đoạn đầu của quá trình thiết kế, người ta thường phải dự đoán hai vấn đề. Vấn đề thứ nhất là bản chất của các ứng dụng sẽ chạy trên mạng và các yêu cầu dịch vụ mà các ứng dụng này đòi hỏi hệ thống mạng phải đáp ứng. Vấn đề dự đoán thứ hai liên quan tới việc lựa chọn một trong các thiết kế kiến trúc, dựa trên các công nghệ phần cứng và phần mềm sẽ được phát triển và đưa ra thị trường trong tương lai, khi hệ thống mạng bước vào giai đoạn triển khai thực hiện.

Để tìm được các khiếm khuyết chính trong thiết kế hoặc các lỗi trong việc lập trình hệ thống, các nhà nghiên cứu thường so sánh hiệu năng dự đoán với hiệu năng thực tế đạt được. Ngày nay, việc dự đoán và đánh giá hiệu năng thường được coi là một phần không thể thiếu được của công việc thiết kế và triển khai thực hiện hệ thống nhằm đạt được mục tiêu là tối ưu hóa hiệu năng hệ thống.

 Định cấu hình mạng: Sau khi hoàn thành triển khai và đưa mạng vào hoạt động, việc dự đoán và đánh giá hiệu năng mạng đối với các ứng dụng cụ thể cũng có ý nghĩa quan trọng. Để tối ưu hoá hiệu năng mạng, nhà sản xuất phải chỉ ra được các cách kết hợp và tổ chức phần cứng và phần mềm mạng để đem lại một giải pháp tốt nhất cho các yêu cầu của khách hàng, việc này thường được gọi là định cấu hình mạng.

 Tinh chỉnh hệ thống: Sau khi hệ thống sản phẩm đã được lắp đặt tại địa điểm của khách hàng, nhà cung cấp sản phẩm cần phải làm sao cho hệ thống mà họ bán cho khách hàng đạt được hiệu năng hoạt động như họ đã hứa hẹn khi chào hàng, việc này được gọi là tinh chỉnh hệ thống. Đối với các hệ thống mạng, việc tìm ra được điểm làm việc tối ưu và ổn định trên toàn mạng là rất khó.

4.1.1.1. Mô hình Giải tích

Đối với mạng máy tính, ta có thể thiết lập mô hình như một mạng hàng đợi. Khách hàng (customer) của các hàng đợi là các gói số liệu đến với yêu cầu được truyền đi, còn người phục vụ (server) chính là các phương tiện truyền, bao gồm hệ chuyển mạch và đường kết nối vật lý. Hầu hết các vấn đề liên quan đến hiệu năng đều liên quan tới thời gian mà các gói số liệu phải xếp hàng chờ được phục vụ. Trong các mạng chuyển mạch gói, gói số liệu là các khối dữ liệu có chiều dài thay đổi được, và được truyền qua mạng từ nguồn tới đích theo một con đường nào đó do hệ thống mạng quyết định. Khi các gói số liệu này đi qua mạng, chúng sẽ cùng nhau chia sẻ các tài nguyên mạng. Nói chung, tất cả các tham số như: số lượng và chiều dài các gói số liệu đi vào hoặc đi qua mạng tại mọi thời điểm, thời gian kéo dài các cuộc kết nối … thay đổi một cách thống kê. Do đó, cần phải sử dụng các khái niệm về xác suất để nghiên cứu sự tương tác của chúng với mạng khi xác định các tiêu chuẩn đo lường định lượng về hiệu năng. Lý thuyết Hàng đợi đóng vai trò mấu chốt trong việc phân tích mạng, bởi vì đó là công cụ Toán học thích hợp nhất để phát biểu và giải các bài toán về hiệu năng. Theo phương pháp này, chúng ta viết ra các mối quan hệ hàm giữa các tiêu chuẩn hiệu năng cần quan tâm và các tham số của hệ thống mạng bằng các phương trình có thể giải được bằng giải tích.

4.1.1.2. Mô phỏng mạng bằng chương trình máy tính

Mô phỏng, theo nghĩa chung nhất là sự bắt chước một hay nhiều khía cạnh của sự vật có thực, bằng một cách nào đó càng giống càng tốt. Trong các lĩnh vực nghiên cứu hiện đại nói chung và lĩnh vực đánh giá hiệu năng mạng nói riêng, mô phỏng được hiểu là một kỹ thuật sử dụng máy tính điện tử số để làm các thí nghiệm về mạng có liên quan đến thời gian. Chúng ta có thể xem hoạt động của mạng máy tính là một dãy các sự kiện xảy ra liên tiếp, tại các thời điểm xác định, rời rạc; mỗi sự kiện diễn ra trong một khoảng thời gian xác định. Do vậy, mô hình Mô phỏng hoàn toàn mô tả được hành vi động của mạng, ngay cả khi người nghiên cứu chỉ quan tâm đến giá trị trung bình của một số độ đo trong trạng thái dừng. Bằng cách sử dụng máy tính điện tử số, chúng ta có thể xây dựng các mô-đun chương trình phần mềm để mô phỏng các thành phần khác nhau của mạng thực cũng như hành vi của chúng. Các mô-đun chương trình phần mềm nói trên thường được gộp thành bộ mô phỏng với cấu trúc và độ phức tạp phụ thuộc vào phạm vi của thí nghiệm mô phỏng.

4.1.1.3. Đo trên mạng thực

Đây là phương pháp xác định hiệu năng dựa trên việc đo trên mạng thực các tham số mạng cấu thành độ đo hiệu năng cần quan tâm. Việc đo hiệu năng nhằm thực hiện một trong ba nhiệm vụ sau. Một là, giám sát hiệu năng của mạng . Hai là, thu thập số liệu để lập mô hình dữ liệu vào cho các phương pháp đánh giá hiệu năng bằng giải tích hoặc mô phỏng. Nhiệm vụ thứ ba là kiểm chứng các mô hình khác dựa trên các số liệu đo được. Đo hiệu năng không chỉ quan trọng trong các giai đoạn triển khai thực

hiện và tích hợp hệ thống mà còn cả trong các giai đoạn lắp đặt và vận hành hệ thống. Bởi vì sau khi lắp đặt và đưa vào sử dụng, mỗi một hệ thống cụ thể sẽ có một tải hệ thống và các độ đo hiệu năng được quan tâm riêng của nó, cho nên sau khi lắp đặt, người ta thường phải điều chỉnh cấu hình cho phù hợp. Các tham số cấu hình sẽ được chọn sau khi các phép đo hiệu năng cho thấy các tham số cấu hình này làm cho hệ thống đạt được hiệu năng tốt nhất.

4.1.1.4. Lý do sử dụng phương pháp mô phỏng để đánh giá hiệu năng mạng

Trong những trường hợp mô hình Giải tích mà chúng ta nhận được, dù đã được đơn giản hoá, hoặc phân rã nhưng vẫn không thể giải được bằng Toán học, khi đó, nói chung, chúng ta sẽ chỉ còn một phương pháp là mô phỏng. Phương pháp mô phỏng có thể được sử dụng ngay trong giai đoạn đầu của việc thiết kế hệ thống mạng, cho đến giai đoạn triển khai thực hiện và tích hợp hệ thống. Phương pháp này nói chung, đòi hỏi một chi phí rất cao cho việc xây dựng bộ mô phỏng cũng như kiểm chứng tính đúng đắn của nó. Tuy nhiên, sau khi đã xây dựng xong bộ mô phỏng, người nghiên cứu có thể tiến hành chạy chương trình mô phỏng bao nhiêu lần tuỳ ý, với độ chính xác theo yêu cầu và chi phí cho mỗi lần chạy thường là rất thấp. Các kết quả mô phỏng nói chung vẫn cần được kiểm chứng, bằng phương pháp giải tích hoặc đo. Phương pháp mô hình Giải tích và mô hình Mô phỏng đóng vai trò rất quan trọng trong việc thiết kế và triển khai thực hiện hệ thống, đặc biệt là ở giai đoạn đầu.

Trong luận văn này, tôi sử dụng bộ mô phỏng NS-2 kết hợp với các độ đo hiệu nă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 giao thức định tuyến trong mạng MANET. 4.1.2. Công cụ mô phỏng NS-2 [1, 12, 15]

NS là chữ viết tắt của cụm từ Network Simulation, là bộ mô phỏng mạng theo sự kiện rời rạc do nhóm nghiên cứu tại Phòng thí nghiệm Quốc gia Lawrence Berkeley, Hoa Kỳ xây dựng và được tiếp tục phát triển bởi dự án VINT (Virtual InterNetwork Testbed) do Bộ Quốc phòng Mỹ cấp kinh phí. NS được phát triển từ bộ mô phỏng REAL (Realistic and Large) của S. Keshav từ năm 1989, còn REAL thì bắt nguồn từ bộ mô phỏng NEST (Network Simulation Testbed). Sau năm 1997, các phiên bản 2.xx của NS ra đời và bắt đầu từ đây người ta thường gọi bộ mô phỏng NS là NS- 2, nó có những khác biệt khá nhiều so với các phiên bản 1.xx ban đầu. Khi sử dụng NS-2, ta có thể lập trình thay đổi cấu hình và mở rộng mô hình mạng mô phỏng một cách dễ dàng, ngay cả khi chương trình mô phỏng đang chạy. Ban đầu, NS chỉ được thiết kế để chạy trên nền hệ điều hành Unix/Linux, sau này người ta cũng xây dựng một số phiên bản NS chạy trong môi trường Windows.

Hình 15. Kiến trúc NS-2

Hiện nay, cộng đồng sử dụng NS có trên 1000 trường đại học, viện nghiên cứu, công ty... với hơn 10 nghìn người sử dụng trên toàn thế giới. Cộng đồng sử dụng NS có một diễn đàn chung để trao đổi các vấn đề có liên quan.

Ba chủ đề chính thường được nghiên cứu bằng NS là: lựa chọn một trong một số cơ chế, nghiên cứu tỉ mỉ các hành vi phức tạp và điều tra các tương tác còn chưa biết giữa các giao thức.

Các đặc điểm nổi bật chính bộ mô phỏng NS là:

 Khả năng trừu tượng hoá: có thể thay đổi độ mịn của mô phỏng cho phù hợp

với cả các mô phỏng chi tiết lẫn các mô phỏng mức cao.

 Khả năng phát sinh ra kịch bản: NS có khả năng tạo ra một cách tự động các mẫu lưu lượng, các hình trạng mạng, các sự kiện thay đổi động và phức tạp, kể cả việc mô phỏng các nút mạng và đường truyền bị hỏng.

 Khả năng mô phỏng tương tác với mạng thực: NS có một giao diện đặc biệt, cho phép lưu lượng thực đi qua nút mạng tương tác với bộ mô phỏng chạy trên nút mạng đó.

 Khả năng hiển thị trực quan: Công cụ hiển thị NAM giúp chúng ta thấy được hình ảnh hoạt động của mạng bằng trực giác và trợ giúp cho việc gỡ rối giao thức cần nghiên cứu.

 Khả năng mở rộng được: Bộ mô phỏng NS có khả năng mở rộng được dễ dàng khi người nghiên cứu muốn bổ sung các chức năng mới, thử nghiệm các kịch bản khác nhau và nghiên cứu các giao thức mới. Các thành phần của bộ chương trình mô phỏng NS

Trong bộ chương trình mô phỏng mạng NS, hai thành phần quan trọng nhất là chương trình mô phỏng NS và các công cụ hiển thị trực quan. Khi sử dụng chương trình mô phỏng NS, ta có thể lập trình cho nó để định ra hình trạng (tô-pô) mạng là tĩnh hoặc động, cũng như tạo ra các luồng lưu lượng theo một số phân bố đã được định nghĩa trước. Mặt khác, ta có thể lựa chọn chính sách quản lý hàng đợi tại các nút mạng, cũng như có thể đưa các mô hình sinh lỗi vào các đường truyền.

Thành phần thứ hai là các công cụ hiển thị trực quan NAM và XGRAPH. NAM là công cụ hiển thị, cho phép người nghiên cứu nhìn thấy bằng đồ hoạ hình trạng mạng, gồm các nút mạng, các đường truyền nối các nút ở dạng tĩnh và động; NAM cũng có thể hiển thị hành vi động của hàng đợi tại các nút, cũng như sự chuyển động của các gói số liệu trên mạng. Đối với mạng di động không dây, các phiên bản mới của NAM có thể hiển thị hình trạng động của mạng, tức là sự chuyển động của các nút mạng trong không gian hai chiều.

Hiện nay, ta có thể sử dụng công cụ iNSpect để thay thế NAM trong hiển thị hình ảnh động của các mạng di động không dây. Công cụ mới này được phát triển bởi nhóm Toilers Research Group gồm những thành viên thuộc trường Colorado School of Mines và khoa Công nghệ an ninh – trường Fraunhofer Institute.

XGRAPH là một chương trình ứng dụng chạy trong X-Windows. Những tệp vết dạng text do chương trình mô phỏng sinh ra được XGRAPH sử dụng làm dữ liệu đầu vào để vẽ đồ thị trong không gian hai chiều. Các dạng đồ thị mà XGRAPH có thể vẽ là đồ thị dạng đường (Line graph), đồ thị điểm (Scatter plots) và đồ thị cột (Bar charts). Các đồ thị này có thể được sao lưu dưới dạng các file ảnh thông dụng và sử dụng cho các chương trình ứng dụng khác nhau.

4.1.2.1. Các chức năng mô phỏng chính của NS

Đối với mạng có dây:

 Các đường truyền điểm-điểm đơn công, song công, mạng cục bộ LAN.  Các chính sách phục vụ hàng đợi.  Các mô hình sinh lỗi.  Vấn đề định tuyến Unicast/Multicast (Unicast/Multicast routing).  Các giao thức tầng Giao vận: TCP/Tahoe/Reno/New-Reno/Sack/Vegas, UDP,

điều khiển lưu lượng và điều khiển tắc nghẽn.

 Các giao thức tầng Ứng dụng, Web caching, truyền luồng dữ liệu đa phương tiện.

Đối với mạng không dây:

 Kênh truyền.  Sự di chuyển của các nút mạng trong không gian hai chiều.  Mạng LAN không dây (WLAN) 802.11.  Mobile IP.  Các thuật toán định tuyến trong mạng không dây đặc biệt (Adhoc networks):

DSDV, DSR, AODV, TORA...

 Liên mạng sử dụng vệ tinh (Satellite Networking).

Trong lĩnh vực mạng hỗn hợp có dây và không dây:

 Trạm cơ sở (BS) đóng vai trò gateway giữa mạng có dây và mạng không dây.  Snoop TCP.

4.1.2.2 Cấu trúc phần mềm của NS

Lập trình tách biệt

Người ta đã xây dựng NS theo tư tưởng tạo cho nó khả năng mở rộng được dễ dàng khi người nghiên cứu muốn bổ sung các chức năng mới, thử nghiệm các kịch bản khác nhau và nghiên cứu các giao thức mới. Để đạt được mục tiêu trên, NS sử dụng một mô hình lập trình phân tách làm hai phần; ngôn ngữ C++ được sử dụng để triển khai thực hiện hạt nhân của bộ mô phỏng, gồm các chức năng căn bản nhất của mô phỏng cần chạy ở tốc độ cao. Phần thứ hai của NS sử dụng ngôn ngữ Tcl, thực hiện các nhiệm vụ định nghĩa, định cấu hình và điều khiển mô phỏng. Lập trình hướng đối tượng

Việc phân chia NS làm hai phần được lập trình bằng các ngôn ngữ khác nhau cũng thường thay đổi trong quá trình nghiên cứu các giao thức. Vì vậy, việc tái sử dụng các môđun chương trình có ý nghĩa hết sức quan trọng, điều này dẫn đến sự lựa chọn lập trình hướng đối tượng. Tuy nhiên, ban đầu khi người ta thiết kế NS, ngôn ngữ Tcl không hỗ trợ việc lập trình hướng đối tượng, vì thế dự án VINT đã chấp nhận sử dụng các mở rộng hướng đối tượng của ngôn ngữ Tcl, được phát triển tại Viện Công nghệ Massachuset (MIT), ngôn ngữ này được gọi là OTcl. Ngoài ra, VINT cũng chấp nhận một sự mở rộng đơn giản của Tcl, đó là các lớp (TclCL). Nhờ đó có thể dễ dàng tạo ra một đối tượng được xây dựng bằng cả hai ngôn ngữ C++ và OTcl.

4.1.2.3. Lập trình mô phỏng bằng NS

Dưới đây chúng tôi liệt kê các thao tác cơ bản trong việc lập trình mô phỏng bằng NS, mỗi thao tác này nói chung được biểu diễn bằng một dòng lệnh trong chương trình mô phỏng, sử dụng “ngôn ngữ” của NS. Các hướng dẫn chi tiết hơn có thể tra cứu trong tài liệu ns-Manual.

1. Các thao tác đối với bộ lập lịch các sự kiện. 2. Tạo ra mạng. 3. Chọn thuật toán định tuyến. 4. Tạo ra kết nối và lưu lượng. 5. Đưa mô-đun sinh lỗi vào đường truyền của mạng mô phỏng. 6. Ghi lại vết của mô phỏng (Tracing) để xử lý và phân tích sau. 7. Ghi lại vết của các sự kiện để hiển thị trực quan bằng chương trình NAM.

4.1.3 Công cụ hỗ trợ phân tích kết quả mô phỏng

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

Tệp vết có tên mở rộng là .tr: mỗi dòng ghi lại một sự kiện trong mạng và các thông tin liên quan đến sự kiện. Trong NS-2, có hai kiểu cấu trúc tệp vết chứa kết quả mô phỏng mạng không dây là: Kiễu cũ: r 160.093884945 _6_ RTR --- 5 tcp 1492 [a2 4 6 800] ------- [655 36:0 16777984:0 31 16777984] [1 0] 2 0

Kiểu mới: s -t 0.267662078 -Hs 0 -Hd -1 -Ni 0 -Nx 5.00 -Ny 2.00 -Nz 0.00 -Ne -1.000000 -Nl RTR -Nw --- -Ma 0 -Md 0 -Ms 0 -Mt 0 -Is 0.255 -Id -1.255 -It message -Il 32 -If 0 -Ii 0 -Iv 32

Ngoài 2 loại tệp vết có cấu trúc như trên, người lập trình mô phỏng (bằng Otcl) có thể thay đổi (thí dụ bỏ bớt...) một số trường (field) trong tệp vết, nhằm giảm kích thước của tệp vết và các thông tin không cần quan tâm.

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

Với tệp vết ghi lại các sự kiện trong mạng có cấu trúc được định nghĩa rõ ràng, người phân tích có thể xử lý và kết xuất thông tin bằng mọi công cụ có thể, thí dụ các ngôn ngữ lập trình hoặc các phần mềm chuyên dụng. Dưới đây là các phần mềm và ngôn ngữ thường được sử dụng, trong đó phần lớn là các sản phẩm thuộc dự án GNU. Grep

Grep là thuật ngữ viết tắt của cụm từ Global Regular Expression Parser, nó là một lệnh trong Unix|Linux. Grep là một bộ lọc, nó tìm và hiển thị (hoặc kết xuất kiểu pipling) các dòng trong input có chứa mẫu ký tự mà người sử dụng chỉ ra. Awk

AWK là một ngôn ngữ lập trình được sáng tạo bởi 3 người là Alfred Aho, Peter Weinberger và Brian Kernighan. Chương trình gawk được tích hợp trong Linux là ứng dụng GNU của ngôn ngữ lập trình awk.

Ngôn ngữ awk không chỉ là một ngôn ngữ lập trình, nó còn là một công cụ hầu như không thể thiếu được đối với nhiều người quản trị hệ thống và người lập trình UNIX. Ngôn ngữ này dễ học, dễ nắm vững và mềm dẻo một cách đáng kinh ngạc. Perl

Perl là thuật ngữ viết tắt của Practical Extraction and Report Language, và là một ngôn ngữ lập trình được phát triển bởi Larry Wall. Perl đi kèm với các phiên bản của Linux và chính perl cũng được hoàn thiện qua nhiều version.

Perl là một chương trình ứng dụng rất mạnh, kết hợp các đặc điểm của awk, grep, sed và C. Chương trình viết cho perl thực hiện cũng tương tự shell script và cũng được gọi là script. Phần mềm soạn thảo GNU Emacs có “perl mode” để soạn thảo perl script. GNUPLOT

Gnuplot có thể chạy trên Windows và trên Unix|Linux. Gnuplot có thể nhận input là file văn bản có nhiều cột, khi đó cần chỉ ra 2 cột để lấy số liệu vẽ đồ thị. Gnuplot còn có thể nhận input từ nhiều file và vẽ trên một đồ thị, điều này rất thuận lợi cho việc so sánh các kết quả cần nghiên cứu. Trace graph

Tác giả của Trace graph là Jaroslaw Malek (Copyright (c) 2001-2003 by Wroclaw University of Technology, Poland). Đây là một phần mềm mã nguồn mở tự do (đã thương mại hoá các phiên bản ra đời từ khoảng năm 2004), có khả năng phân tích và hiển thị các kết quả mô phỏng khá tốt (input là tệp vết).

4.1.4. Công cụ hiển thị trực quan mạng MANET trong quá trình hoạt động iNSPECT

iNSpect (The interactive NS-2 protocol and environment conﬁrmation tool) là một công cụ trực quan dựa trên C++ và OpenGL cho phép hiển thị hình ảnh động của các mạng không dây được mô phỏng trong NS-2. Chương trình đọc các file di chuyển trong NS-2 và trả về các kết quả mô phỏng. iNSpect đưa ra một màn hình hiển thị hình ảnh của các nút trong một kịch bản không dây dựa trên hệ tọa độ Đề-các (x, y). Chương trình có một event builder (bộ xây dựng sự kiện) để đọc trực tiếp một tập tin di chuyển và lập lịch chuyển động và tạm dừng của từng nút riêng rẻ. Chức năng event builder cho phép iNSpect sử dụng trực tiếp các tập tin di chuyển được tạo ra bởi các mô hình động bên ngoài. Mặt khác, iNSpect không yêu cầu tạo ra một tập tin vết riêng cho nó từ bộ mô phỏng NS-2, do đó tiết kiệm không gian ổ cứng.

Khi một tệt vết được tạo ra, iNSpect sử dụng cùng một event builder để đọc tệt vết và lập lịch các phiên truyền gói tin với các di chuyển của nút. Khác với NAM, iNSpect hiển thị các tuyến đường không dây cũng như sự thành công hay thất bại của một phiên truyền gói tin. Các phiên truyền được hiển thị bằng các đường thẳng và các nút mã hoá màu sắc. Khi một nút truyền đến một nút khác, một đường thẳng được vẽ giữa hai nút. Đường thẳng đó đại diện cho sự cố gắng để truyền tải giữa hai nút, tương tự như các đối tượng liên kết trong các kịch bản NAM có dây. Nút trung gian trong một phiên truyền trở về màu xanh để cho biết nó đang gửi đi. Các nút nhận chuyển sang màu đỏ cho đến khi gói tin được nhận thành công, sau đó nó chuyển về màu xanh lá cây hoặc màu xanh. Nếu nút nhận là đích đến của gói tin, nó chuyển sang màu xanh lá cây. Nếu nút nhận không phải là đích đến cuối cùng, nó đổi sang màu xanh để hiển thị sự cố gắng truyền chuyển tiếp, và các đường thẳng biểu diễn tuyến đường được mở rộng để hiển thị sự chuyển tiếp gói tin. Hình 16 minh họa ba giai đoạn của một phiên truyền gói tin từ nút nguồn 1 đến các nút 20, 27, 21, và 18, tới nút đích 48. Việc tồn tại các đường và trạng thái nút cho phép phân tích tuyến đường riêng rẽ.

(a) Đường truyền từ nút 1 đến nút 20

(b) Đường truyền từ nút 1 đến nút 18 (c) Đường truyền từ nút 1 đến nút 48

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

Trong iNSpect, sự tương tác giữa các sự kiện nút và vấn đề hiển thị xảy ra liên tục trong suốt thời gian mô phỏng khi mỗi nút cập nhật vị trí và hoạt động của mình. Vì việc phát lại đã được lên lịch điều khiển trước nên iNSpect cung cấp một tốc độ phát lại gần như ngay tại thời điểm bắt đầu thay đổi cho mô phỏng. Dẫn đến, người nghiên cứu có thể “nhảy” tới một thời điểm cụ thể trong tập vết mô phỏng lớn để phân tích chi tiết.

Chương trình iNSpect cho phép người dùng hiển thị các đối tượng phủ như vòng tròn, chữ nhật và vị trí (x, y) hiện hành của mỗi nút. Hình bao phủ có thể xác định các khu vực mà ta quan tâm. Ví dụ, hình 17 minh họa một hình tròn bao phủ ở trung tâm của khu vực mô phỏng (150 m, 300 m) với bán kính 30 m. Tôi sử dụng hình tròn bao phủ với một mô hình di chuyển mới để hiển thị vấn đề các nút di chuyển tắc nghẽn trong một khu vực nhất định của mô phỏng. Trong mô hình di chuyển này, các nút di chuyển theo mô hình Random Waypoint. Khi đó, một nút di chuyển vào khu vực tắc nghẽn, nó di chuyển chậm lại. Tôi sử dụng hình tròn bao phủ trong iNSpect để đại diện cho khu vực bị tắc nghẽn, xác nhận rằng các nút di chuyển chậm lại trong khu vực đó. Khu vực này có thể đại diện cho một đường nhỏ tại một trung tâm mua bán hoặc ngã tư lớn trong thành phố. Vị trí và kích thước của vòng tròn được cấu hình trong iNSpect.

Hình 17. Hình tròn bao phủ biểu diễn khu vực tắc nghẽn

Hình chữ nhật bao phủ cũng được cung cấp trong iNSpect. Nó được sử dụng trong việc đánh giá các giao thức định tuyến Geocast. Trong định tuyến Geocast, các gói tin được chuyển tiếp đến các nút trong một khu vực địa lý cụ thể của vùng mô phỏng. Ví dụ, một người quản lý có thể cần phải gửi thông tin khẩn cấp đến một khu vực nhất định trong một thị trấn để cảnh báo người dân phải sơ tán. Hình 18 mô tả một khu vực hình chữ nhật được quan tâm với các đỉnh có tọa độ (150 m, 400 m) và (300 m, 600 m). Hình chữ nhật bao phủ trên iNSpect cho phép phân tích của tuyến đường mà một gói tin đến khu vực.

Hình 18. Hình tròn bao phủ biểu diễn khu vực nguy hiểm

Hình bao phủ của iNSpect có thể được sử dụng để đại diện cho những trở ngại. Và các trở ngại làm cho các mô hình di động giống thực tế hơn. Những trở ngại ảnh hưởng đến đường truyền cũng như chuyển động của các nút. Chương trình iNSpect có thể được sử dụng để quan sát ảnh hưởng của những trở ngại về chuyển động của các nút và việc truyền gói tin.

Hình 19, iNSpect hiển thị vị trí nút với tọa độ (x, y). Các thông tin vị trí này có thể được sử dụng để xác định chính xác vị trí nút. Và chúng cũng có thể được sử dụng để đánh giá các giao thức định tuyến dựa trên vị trí.

Hình 19. iNSpect hiển thị tọa độ (x, y) của các nút

Trong các giao thức dựa trên vị trí, hiểu biết của một nút về vị trí của đích đến được sử dụng để xác định một tuyến đường đến đích. Sử dụng các tuyến đường và vị trí nút trên cửa sổ iNSpect, người nghiên cứu có thể đánh giá hiệu suất của một giao thức trên các tuyến đường riêng biệt. Điều này cho phép người nghiên cứu chi tiết thông tin không có sẵn trong số liệu thống kê tổng hợp.

Chương trình iNSpect thường được điều khiển bởi một file cấu hình, điều này làm giảm thiểu các dòng lệnh, sự cần thiết phải biên dịch lại trong khi cho phép người dùng kiểm soát nhiều khía cạnh của màn hình hiển thị. Vị trí và kích thước của các đối tượng bao phủ, là một phần của tệp tin cấu hình. Chương trình iNSpect có thể hiển thị và hoạt họa các kết quả của một tệp di chuyển đơn lẻ, nó có thể một tệp vết NS-2, và nó cũng có thể làm hoạt họa một tệp di chuyển và một tệp vết iNSpect để chỉ ra hoạt động liên kết. Tệp vết iNSpect được sử dụng để xác định các kết nối không dây không có hiển thị trong các tệp vết NAM.

4.2. Thiết lập mô phỏng mạng MANET trong NS

4.2.1. Tạo các nút mạng trong MANET

4.2.1.1 Nút di động

Các thành phần mạng chính được dùng để cấu trúc nên tầng giao thức cho mỗi nút di động gồm có: kênh (channel), giao tiếp mạng (network interface), mô hình phát sóng vô tuyến (radio propagation model), các giao thức MAC, hàng đợi giao diện (interface queue), lớp liên kết (link layer), mô hình giao thức phân giải địa chỉ ARP và thành phần định tuyến (routing agent).

Hình 20 dưới đây biểu diễn cấu tạo nút di động mô phỏng trong NS2:

Hình 20. Nút di động mô phỏng trong NS2

Mô phỏng lớp vật lý thực

Các mô hình phát sóng quyết định khoảng cách gói tin có thể được truyền đi trong không khí. Nếu gọi r là khoảng cách giữa các ăng ten thì sự suy yếu của sóng vô tuyến giữa các ăng ten ở gần mặt đất được mô hình là 1/r2 với khoảng cách ngắn và và 1/r4 với các khoảng cách xa. Khi đó, điểm giao giữa khoảng cách ngắn và khoảng cách xa được gọi là khoảng cách tham chiếu (reference distance). Khoảng cách này thông thường là 100 m đối với các ăng ten 1,5m loại có độ lợi thấp (low-gain) ngoài trời hoạt động ở dải tần 1-2GHz. Đặc tả của mô hình phát sóng trong NS2 tương tự như giao tiếp sóng vô tuyến Lucent’s WaveLAN với tốc độ bit danh định có thể đạt tới 2,5Mb/s

và phạm vi truyền sóng vô tuyến là 250m. Các mô hình cũng thể hiện độ trễ truyền, các ảnh hưởng và cảm nhận sóng mang. Mô phỏng lớp MAC

Lớp liên kết của bộ mô phỏng cài đặt hoàn chỉnh chuẩn giao thức MAC của IEEE 802.11 DCF(Distributed Coordination Function). Các chức năng của lớp MAC được cài đặt bao gồm phát hiện xung đột, phân mảnh, biên nhận và đặc biệt có khả năng phát hiện các lỗi truyền (transmision error). 802.11 là giao thức CSMA/CA. Việc tránh xung đột được thực hiện bằng việc kiểm tra kênh truyền trước khi sử dụng. Nếu kênh rỗi, nút có thể bắt đầu gửi. Nếu không, nút phải đợi một khoảng thời gian ngẫu nhiên trước khi kiểm tra lại. Mỗi lần cố gắng gửi không thành công, giải thuật rút lui theo hàm mũ được sử dụng. Vấn đề trong môi trường không dây là thiết bị đầu cuối ẩn (hidden terminal). Việc khắc phục được thực hiện bằng cơ chế tránh xung đột CA cùng với lược đồ biên nhận tích cực (RTS/CTS). 802.11 cũng hỗ trợ việc tiết kiệm năng lượng và bảo mật. Các gói tin được lưu trong bộ đệm khi hệ thống ở trạng thái nghỉ (sleep); bảo mật được cung cấp bởi giải thuật WEP xác thực và mã hóa. Một trong các đặc điểm quan trọng nhất của 802.11 là chế độ AD HOC cho phép xây dựng các mạng WLAN không có cơ sở hạ tầng. Mô phỏng giao thức phân giải địa chỉ ARP

Giao thức ARP dịch địa chỉ IP thành địa chỉ phần cứng MAC. Việc này được

thực hiện trước khi gói tin được gửi tới lớp MAC. Hàng đợi giao diện

Mỗi nút có hàng đợi các gói tin đang chờ để được truyền bởi giao diện mạng. Hàng đợi được cài đặt là DropTail (thuật ngữ trong bộ mô phỏng NS2, tương tự như hàng đợi kiểu FIFO) và có khả năng chứa 50 gói tin. Giao diện sóng vô tuyến

Đây là mô hình phần cứng thực sự chuyển gói tin vào kênh. Giao diện sóng vô

tuyến được mô hình hóa với các mức năng lượng và lược đồ điều biến. Năng lượng truyền

Bán kính bộ thu phát sóng phụ thuộc vào dạng ăngten, nhiều dạng ăngten được

hỗ trợ bởi bộ mô phỏng. Các giao thức định tuyến AD HOC

Hiện tại có bốn giao thức được cài đặt sẵn trong NS2 là DSDV, AODV, TORA

và DSR.

4.4.1.2 Mô hình phương tiện chia sẻ trong NS2

Mô hình không dây được dựa trên mô hình phương tiện chia sẻ (Ethernet trong không khí), được minh họa trên hình 21. Tất cả các nút di động có một hoặc nhiều giao diện mạng kết nối vào một kênh. Kênh là một dải tần số vô tuyến cụ thể với lược đồ điều biến và mã hóa riêng. Các kênh là trực giao, có nghĩa là các gói tin được gửi trên một kênh không làm nhiễu các gói tin được truyền và nhận trên một kênh khác.

Hoạt động cơ bản như sau, mọi gói tin được gửi hoặc đặt vào kênh sẽ được nhận hoặc sao chép bởi tất cả các nút di động có kết nối tới cùng kênh. Khi nút di động nhận được gói tin, đầu tiên nút xem xét nó có được nhận gói tin hay không. Điều này được quyết định bởi mô hình phát sóng vô tuyến, dựa trên dải truyền thông, khoảng cách gói tin đã di chuyển và lượng bit lỗi.

Hình 21. Mô hình phương tiện chia sẻ trong NS2

4.4.1.3 Hoạt động của nút di động

Hoạt động của nút di động được thể hiện trong hình 16 như sau. Mỗi nút di động sử dụng thành phần định tuyến (routing agent) để tính toán đường tới các nút khác trong mạng AD HOC. Các gói tin được gửi từ ứng dụng và được nhận bởi thành phần định tuyến. Bộ phận này sẽ quyết định đường đi của gói tin để tới đích và gắn vào gói tin thông tin này. Gói tin sau đó được gửi xuống lớp liên kết. Lớp liên kết sử dụng giao thức phân giải địa chỉ ARP để quyết định địa chỉ phần cứng của nút hàng xóm và ánh xạ địa chỉ IP tới giao diện chính xác. Khi thông tin nhận được, gói tin được gửi xuống hàng đợi giao diện và đợi tín hiệu từ giao thức MAC. Khi lớp MAC quyết định gói tin có thể được gửi vào kênh, gói tin được lấy từ hàng đợi chuyển tới giao diện mạng và sau đó được gửi ra kênh vô tuyến. Gói tin được sao chép và được phân phát tới tất cả các giao diện mạng tại thời điểm bít đầu tiên của gói tin bắt đầu đến giao diện trong hệ thống vật lý. Mỗi giao diện mạng đánh dấu gói tin với các thuộc tính của giao diện nhận và sau đó gọi tới mô hình phát sóng.

Mô hình phát sóng sử dụng các đánh dấu truyền và nhận để quyết định mức năng lượng mà giao diện nhận gói tin. Các giao diện nhận sử dụng các thuộc tính của chúng để quyết định việc nhận gói tin thật sự thành công hay không và gửi gói tin tới lớp MAC nếu thích hợp. Nếu lớp MAC nhận gói tin không có lỗi và không có xung đột, gói tin được gửi tới điểm đầu vào của nút di động. Từ đó, gói tin tới bộ phân tách kênh (demultiplexer) để xác định gói tin có được chuyển tiếp nữa hay không hoặc đã tới nút đích. Nếu tới được nút đích, gói tin được gửi tới bộ phân tách cổng (port demultiplexer) để quyết định ứng dụng nhận của gói tin. Nếu gói tin được chuyển tiếp, thành phần định tuyến sẽ đươc gọi và thủ tục được lặp lại.

4.4.1.4 Cấu hình nút di động trong NS

(như classiﬁers, dmux, LL, Mac, Channel, …)

Nút di động (MobileNode) là đối tượng nsNode cơ bản với các chức năng bổ sung như di chuyển, khả năng truyền và nhận trên một kênh cho phép nó được sử dụng để tạo tính di động, mô phỏng môi trường không dây. Lớp MobileNode có nguồn gốc từ lớp cơ sở Node. MobileNode là một đối tượng tách biệt (split object). Các đặc tính di động bao gồm di chuyển nút, cập nhật vị trí định kỳ, duy trì ranh giới cấu trúc liên kết … được thực hiện trong C++, trong khi các thành phần mạng trong chính được thực MobileNode hiện trong Otcl. Các chức năng và thủ tục mô tả có thể được tìm thấy trong ~ns/mobilenode.{cc,h}, ~ns/tcl/mobility/dsdv.tcl, ~ns/tcl/lib/ns-mobilenode.tcl, ~ns/tcl/mobility/dsr.tcl, ~ns/tcl/mobility/tora.tcl. [ns Manual]

Cấu hình API để tạo một nút di động được mô tả như sau: $ns_ node-config -adhocRouting $opt(adhocRouting) -llType $opt(ll) -macType $opt(mac) -ifqType $opt(ifq) -ifqLen $opt(ifqlen) -antType $opt(ant) -propInstance [new $opt(prop)] -phyType $opt(netif) -channel [new $opt(chan)] -topoInstance $topo -wiredRouting OFF -agentTrace ON -routerTrace OFF -macTrace OFF

Các thủ tục trên tạo một đối đối tượng Mobilenode , một agent định tuyến adhoc-routing xác định, tạo ngăn xếp mạng (stack network) gồm một lớp liên kết, hàng đợi giao diện, lớp MAC và một giao tiếp mạng với một ăng ten, sử dụng mô hình phát sóng vô tuyến, các liên kết giữa các thành phần và kết nối ngăn xếp tới kênh. Nút di động như trong sơ đồ dưới đây:

Hình 22. Sơ đồ của một mobilenode dưới chuẩn wireless của Monarch CMU mở rộng ra NS [12]

4.4.1.5 Tạo sự di chuyển của nút trong NS

Mobilenode được thiết kế để di chuyển trong không gian 3 chiều. Tuy nhiên, cho đến nay chiều thứ 3 (Z) không được sử dụng, nghĩa là mobilenode được giả định luôn di chuyển trên một mặt phẳng với Z = 0. Khi đó, mobilenode có tọa độ X, Y, Z (= 0) được liên tục điều chỉnh khi nút di chuyển. Có 2 cơ chế để tạo chuyển động trong các mobilenode. Trong phương pháp thứ nhất, bắt đầu từ vị trí của nút và các đích đến của các nút đó có thể được thiết lập rõ ràng. Các chỉ thị điều khiển thường nằm trong một file kịch bản di chuyển riêng biệt.

Vị trí ban đầu và đích đến đối với một mobilenode có thể được thiết lập bằng

cách sử dụng các API dưới đây:

$node set X_ $node set Y_ $node set Z_ $ns at $time $node setdest

Tại thời điểm $time, nút bắt đầu di chuyển từ vị trí ban đầu (x1,y1) của nó tới một đích đến (x2,y2) với vận tốc speed xác định. Trong phương pháp này, các cập nhật di chuyển của nút được kích hoạt bất cứ khi nào để xác định vị trí nút tại thời điểm yêu cầu. Việc kích hoạt có thể do một nút hàng xóm có yêu cầu truy vấn để xác định khoảng cách giữa chúng hoặc bộ công cụ setdest trực tiếp mô tả bằng chỉ thị điều khiển hướng hoặc vận tốc của nút.

Phương pháp thứ hai sử dụng chuyển động ngẫu nhiên của nút, như sau:

$mobilenode start

nó bắt đầu mobilenode với vị trí ngẫu nhiên, có các cập nhật thường xuyên để thay đổi hướng và vận tốc của nút. Các giá trị vận tốc và đích được tạo theo một kiểu ngẫu nhiên. Với cả hai phương thức tạo di chuyển nút trên, vùng mô phỏng cần được xác định trước khi tạo các mobilenode. Thông thường, vùng mô phỏng là miền phẳng và được tạo bằng cách xác định chiều dài và chiều rộng, ta định nghĩa như sau:

set topo [new Topography] $topo load_flatgrid $opt(x) $opt(y)

trong đó opt(x) và opt(y) lần lượt là chiều dài và chiều rộng của vùng mô phỏng.

4.4.2. Tạo các đường truyền không dây (air interface) trong MANET

4.4.2.1 Mô hình FreeSpace

Mô hình FreeSpace trình bày cơ bản dải truyền thông như một vòng quanh máy phát. Nếu một máy nhận trong phạm vi vòng vòng tròn phát, nó nhận tất cả các gói tin. Ngược lại nó làm mất tất cả các gói tin.

Giao diện OTcl với việc sử dụng một mô hình truỵền thông là lệnh cấu hình

nút. Một cách để sử dụng nó ở đây là:

$ns_ node-config -propType Propagation/FreeSpace Một cách khác là : set prop [new Propagation/FreeSpace] $ns_ node-config -propInstance $prop

4.4.2.2 Mô hình Two Ray Ground

Một đường truyền đơn trong tầm nhìn thấy giữa hai nút di động là rất hiếm gặp trong thực tế. Mô hình Two Ray Ground phản xạ hai tia mặt xem xét đường truyền trực tiếp và đường truyền phản xạ từ mặt đất. Nó nói lên rằng mô hình này đem đến các dự đoán chính xác hơn với một khoảng cách lớn hơn so với mô hình FreeSpace.

Thông thường, trình thông dịch OTcl sử dụng mô hình phản xạ hai tia mặt đất

như sau:

$ns_ node-config -propType Propagation/TwoRayGround Hay có thể sử dụng: set prop [new Propagation/TwoRayGround] $ns_ node-config -propInstance $prop

4.4.2.3 Mô hình Shadowing

Mô hình FreeSpace và mô hình phản xạ Two Ray Ground dự đoán nguồn năng lượng nhận như một chức năng tất định của khoảng cách. Cả hai trình bày dải truyền thông như một vòng tròn lí tưởng. Trên thực tế, nguồn năng lượng nhận ở một khoảng cách nhất định là một giá trị ngẫu nhiên tại vì nhiều hiệu ứng truyền khác nhau, nó cũng được biết đến như hiện tượng fading (tượng biến đổi cường độ tín hiệu sóng mang). Trên thực tế, cả hai mô hình trên đều dự đoán giá trị trung bình của nguồn năng lượng nhận ở khoảng cách d. Một mô hình tổng quát và thường được sử dụng hơn là mô hình Shadowing.

Mô hình Shadowing mở rộng mô hình vòng tròn lí tưởng để đạt tới mô hình thống kê: các nút có thể chỉ truyền theo xác suất khi ở gần rìa của miền truyền thông. Mục đích mô hình Shadowing: Trước khi sử dụng mô hình Shadowing, người sử dụng cần chọn các giá trị của hệ số suy hao trên đường truyền (path loss) và độ lệch hiệu ứng màn chắn chuẩn σ dB tuỳ theo môi trường mô phỏng.

Chúng ta vẫn sử dụng lệnh cấu hình nút bằng Otcl. Một cách để sử dụng nó như

sau, với các giá trị tham số chỉ được đưa ra làm ví dụ:

# Đầu tiên phải thiết lập giá trị của mô hình hiệu ứng màn chắn. Propagation/Shadowing set pathlossExp_ 2.0 ;hệ số mất đường dẫn Propagation/Shadowing set std_db_ 4.0 ; độ lệch hiệu ứng màn chắn (dB) Propagation/Shadowing set dist0_ 1.0 ; khoảng cách tham chiếu (m) Propagation/Shadowing set seed_ 0 ; khởi đầu với RNG $ns_ node-config -propType Propagation/Shadowing ;Cấu hình cho nút Mô hình Shadowing tạo ra một số ngẫu nhiên khởi xướng đối tượng RNG (Random number Genrator). RNG có ba kiểu khởi tạo: Khởi tạo thô, khởi tạo xác định trước (một thiết lập tốt của khởi tạo) và khởi tạo thông minh (hueristic). Các API trên chỉ sử dụng khởi tạo xác định trước. Nếu một người sử dụng muốn khởi tạo bằng một phương thức khác, API dưới đây có thể được sử dụng. set prop [new Propagation/Shadowing] $prop set pathlossExp_ 2.0 $prop set std_db_ 4.0 $prop set dist0_ 1.0 $prop seed 0 $ns_ node-config -propInstance $prop có thể là thô, xác định trước hay heuristic.

4.4.3. Tạo ngữ cảnh chuyển động

Trong mô phỏng mạng AD HOC, việc mô phỏng được dựa trên hai mô hình là mô hình truyền thông thể hiện khuôn dạng truyền thông giữa các nút trong mạng và mô hình di chuyển thể hiện chuyển động của các nút trong mạng.

4.4.3.1 Tạo diện tích mô phỏng

Tôi xây dựng mạng mô phỏng với các nút di động tạo nên một mạng ad hoc. Các nút này di chuyển trong một khu vực địa lý (không gian phẳng, hình chữ nhật). Toạ độ của các nút tại mỗi thời điểm là (x, y, z), trong đó tọa độ z = 0. Giá trị chiều dài và chiều rộng của vùng mô phỏng được khai báo bằng câu lệnh sau: ;# X dimension of the topography ;# Y dimension of the topography set val(x) a set val(y) b

4.4.3.2. Tạo các thực thể giao thức và các nguồn sinh lưu lượng

Các mô hình truyền thông được mô phỏng trong NS2 (hình 23) gồm hai loại bộ tạo lưu lượng (traffic generator) và các ứng dụng mô phỏng (simulated application) [12]. Các các bộ tạo truyền thông sử dụng giao thức UDP để gửi các gói tin và các ứng dụng mô phỏng sử dụng giao thức TCP.

Hình 23. Các mô hình truyền thông trong NS2

Có bốn loại bộ tạo lưu lượng là: bộ tạo lưu lượng có phân bố lũy thừa, pareto,

CBR và theo file trace.

 Bộ tạo lưu lượng có phân bố lũy thừa: tạo lưu lượng theo một phân bố bật/ tắt lũy thừa. Trong quãng thời gian “bật”, các gói tin được gửi với tốc độ cố định, và trong quãng thời gian “tắt” không có gói tin nào được gửi. Ngoài ra, quãng thời gian bật, tắt được phân bố theo một phân bố lũy thừa. Các gói tin có kích thước không đổi. Bộ tạo lưu lượng lũy thừa có thể cấu hình để hoạt động như một quá trình Poisson.

 Bộ tạo lưu lượng có phân bố Parero: tạo lưu lượng theo phân bố bật/ tắt Pareto. Phân bố này tương tự phân bố bật/ tắt lũy thừa, chí khác là các quãng thời gian bật, tắt lấy theo phân bố Pareto. Các nguồn này có thể được dùng để tạo các lưu lượng kết hợp thể hiện sự phụ thuộc.

 Bộ tạo lưu lượng có phân bố đều - CBR: tạo lưu lượng theo một tốc độ xác định. Kích thước gói tin là không đổi. Ngoài ra, một số các dao động ngẫu nhiên được thực hiện giữa các quãng khởi đầu của các gói tin.

 Bộ tạo lưu lượng theo tệp vết: tạo lưu lượng theo một tệp vết (trace file) xác định thời gian phát và ngừng phát gói tin cùng các thông số khác dựa trên số liệu thu được từ mạng thực, đã được ghi trong tệp vết.

Trong thực nghiệm mô phỏng của luận văn, tôi sử dụng bộ tạo lưu lượng CBR

để tạo tệp truyền thông. Câu lệnh tạo tệp như sau: ns cbrgen.tcl [-type cbr|tcp] [-nn nodes] [-seed seed] [-mc connections] [-rate rate] > outdir/file_name

Trong đó: -type: kiểu lưu lượng kết nối cbr hay tcp; -nn: số lượng nút; -seed: giá trị seed; -mc: số lượng kết nối; -rate: vận tốc nút; -outdir: đường dẫn đến thư mục chứa tệp cần tạo; -file_name: tên tệp lưu lượng

4.4.3.3. Tạo các dạng chuyển động theo mẫu

Trong mô phỏng mạng AD HOC, các mô hình di chuyển đóng một vai trò rất quan trọng. Chúng cần thể hiện chính xác các ngữ cảnh có thể của mạng và góp phần quyết định đúng hiệu suất của các giao thức trước khi được triển khai trong thực tế. Đối với các mạng không dây, hai loại mô hình di chuyển được sử dụng là mô hình vết (trace model) và mô hình tổng hợp (synthetic model). Các mô hình vết là các khuôn dạng di chuyển được quan sát trong hệ thống thực. Mô hình vết cung cấp thông tin chính xác, đặc biệt khi chúng liên quan tới nhiều bên tham gia và quãng thời gian quan sát đủ dài. Tuy nhiên, với môi trường mạng mới, các mạng AD HOC không dễ dàng được mô hình vết. Trong trường hợp này cần thiết phải sử dụng các mô hình tổng hợp. Các mô hình tổng hợp cố gắng thể hiện thực hành vi của các nút di động mà không sử dụng tới mô hình vết bằng việc mô tả các di chuyển của nút một cách thống kê. Mỗi nút được gán một giải thuật dùng để ngẫu nhiên hóa sự di chuyển. Khuôn dạng di chuyển của mạng là tập hợp các di chuyển từ việc áp dụng mô hình di chuyển vào một hoặc nhiều nút. Hai mô hình di chuyển tiêu biểu mô phỏng các mạng AD HOC là Random Waypoint và Random Walk. Mô hình Random Waypoint

Mô hình Random Waypoint được sử dụng rộng rãi trong mô phỏng các giao thức định tuyến thiết kế cho các mạng AD HOC đặc biệt, nó được định nghĩa như sau. Đầu tiên nút có một ví trí ngẫu nhiên trong khu vực mô phỏng và ở tại đó một khoảng thời gian gọi là thời gian tạm dừng. Khi quãng thời gian này hết hạn, nút chọn ngẫu nhiên một đích trong khu vực mô phỏng và một tốc độ được phân bố đồng đều giữa [Speedmin, Speedmax]. Sau đó, nút di chuyển tới vị trí mới với tốc độ đã chọn. Khi tới vị trí mới, nút dừng một khoảng thời gian được chọn theo phân bố đồng đều giữa [Pmin, Pmax], và sau đó tiếp tục lại quá trình.

Trực quan hoá di chuyển của một nút theo mô hình Random Waypoint bởi

Gnuplot trong hình 24 bên dưới.

Hình 24. Di chuyển của một nút theo mô hình Random Waypoint Các tham số mô phỏng cho Random Waypoint được cho trong bảng 7:

Tham số Ý nghĩa

Tốc độ thấp nhất Speedmin

Tốc độ cao nhất Speedmax

Thời gian tạm dừng nhỏ nhất Pmin

Thời gian tạm dừng lớn nhất Pmax

Bảng 7. Các tham số của mô hình Random Waypoint

Mô hình Random Waypoint được dùng rộng rãi trong các nghiên cứu về mạng AD HOC, do nó rất linh động trong việc tạo ra khuôn dạng di chuyển thực tế theo cách mọi người chuyển động trong các hội thảo, hội nghị. Trong NS2, mô hình Random Waypoint được tạo bởi công cụ setdest. Cấu trúc câu lệnh của setdest tạo tệp ngữ cảnh (scenario file) như sau:

Tạo tệp di chuyển kiểu cũ:

-n < nodes> -v <1> -p -M -t

./setdest -x -y

Tạo tệp di chuyển kiểu mới:

./setdest -v <2> -n < nodes> -s -m -M -t -P -p -x -y

Trong đó: -v: version; -n: số tham gia mô phỏng nút; -P: kiểu thời gian tạm dừng; -p: thời gian tạm dừng; -m: vận tốc di chuyển nút nhỏ nhất; -M: vận tốc di chuyển nút tối đa; -t: thời gian mô phỏng; -x: chiều X vùng mô phỏng; -y: chiều Y vùng mô phỏng.

Mô hình Random Walk

Mô hình Random Walk mô phỏng chuyển động ngẫu nhiên của các thực thể trong tự nhiên. Nút di động di chuyển từ vị trí hiện tại tới vị trí mới bằng việc chọn ngẫu nhiên hướng [0, 1800], tốc độ [Speedmin, Speedmax]. Mỗi chuyển động diễn ra trong khoảng thời gian Travel_time hoặc khoảng cách hằng số, không có khoảng thời gian tạm dừng trước khi nút thay đổi hướng và tốc độ. Trực quan hoá di chuyển của một nút theo mô hình Random Walk bởi Gnuplot trong hình 25.

Hình 25. Di chuyển của một nút theo mô hình Random Walk Các tham số mô phỏng cho Random Walk được cho trong bảng 8:

Tham số Ý nghĩa

Tốc độ thấp nhất Speedmin

Tốc độ cao nhất Speedmax

Travel_time Thời gian di chuyển của nút trước khi thay đổi hướng và tốc độ

Bảng 8. Các tham số của mô hình Random Walk

Trong mô hình Random Walk, tham số thay đổi hướng của nút di động quyết định mức độ thay đổi của mạng. Nếu tham số này có giá trị nhỏ, sự di chuyển ngẫu nhiên giới hạn trong một phạm vi nhỏ của khu vực mô phỏng, mạng nửa tĩnh và còn được gọi là di chuyển Brownian. Nếu tham số có giá trị lớn, mạng thay đổi trên phạm vi rộng.

Trong luận văn này, tôi sử dụng chương trình Palm Calculus để tạo tệp ngữ cảnh theo mô hình Random Walk. Cấu trúc câu lệnh của Palm Calculus tạo khuôn dạng di chuyển như sau: ./rwall 3

Trong đó: number of nodes: số nút tham gia mô phỏng; max -x: chiều X vùng mô phỏng; max -y: chiều Y vùng mô phỏng; end time: thời gian mô phỏng; speed mean: vận tốc nút; speed delta: vận tốc delta; pause time: thời gian tạm dừng; pause time delta: thời gian tạm dừng delta.

4.4.4. Sơ đồ khái quát quá trình mô phỏng

Quá trình mô phỏng mạng AD HOC trong NS2 được thể hiện trong hình 26.

Quá trình bao gồm việc tạo hai tệp đầu vào cho NS2:

 Tệp ngữ cảnh (scenario file): là file kịch bản mô tả khuôn dạng di chuyển của

các nút.

 Tệp truyền thông (communication file): là file kịch bản mô tả các truyền thông

trong mạng.

Hình 26. Sơ đồ tổng quan quá trình mô phỏng

Trong quá trình chương trình mô phỏng chạy, bộ mô phỏng NS ghi nhận các hoạt động mạng tại các lớp sau đó xuất dữ liệu thu được ra một tệp vết (trace file). Do đó, trước khi mô phỏng ta cần lựa chọn các tham số cấu hình cho việc ghi tệp vết. Tệp vết sau đó có thể được duyệt và phân tích để xác định các tham số cần tính toán. Các kết quả tính toán, phân tích có thể dùng là dữ liệu cho các chương trình vẽ đồ thị như gnuplot, xgraph, tracegraph. Tệp vết cũng có thể được dùng để trực quan hóa việc chạy mô phỏng bằng ad-hockey hoặc NAM.

4.5 Các tham số hoạt động của các giao thức định tuyến trong NS-2

tại địa chỉ web

Trong bộ mô phỏng NS phiên bản 2.34 được sử dụng trong luận văn có bốn giao thức định tuyến AD HOC được cài đặt sẵn là AODV, DSR, DSDV và TORA. Ngoài ra, mã mô phỏng của giao thức OLSR cho NS2 được cung cấp bởi Francisco J. Ros, Ph.D. Student và Pedro M. Ruiz, Ph.D là http://masimum.inf.um.es/?Software:UM-OLSR. Trong luận văn này, tôi đánh giá ảnh hưởng của sự di động của nút mạng trên bốn giao thức định tuyến là AODV, DSR, DSDV và OLSR.

Dưới đây là các giá trị tham số hoạt động và các lưu ý cài đặt của các giao thức

trong mô phỏng theo tài liệu của NS2 và các file cài đặt các giao thức.

4.5.1 Giao thức định tuyến DSDV

Trong giao thức định tuyến DSDV, thông điệp được trao đổi giữa các nút hàng xóm. Các cập nhật có thể định kỳ hoặc tức thời. Các cập nhật tức thời xảy ra khi thông tin định tuyến từ một trong các hàng xóm gây ra thay đổi trong bảng định tuyến của nút. Các gói tin chưa có đường tới đích được giữ trong bộ đệm khi truy vấn về đường được gửi. Các gói tin được lưu cho tới khi trả lời đường nhận được từ đích. Kích thước bộ đệm lớn nhất để lưu giữ các gói tin đang chờ thông tin về đường được qui định. Quá khả năng này các gói tin sẽ bị loại bỏ.

Tất cả các gói tin có đích là nút di động được bộ phân tách địa chỉ (address mux) chuyển tới bộ phân tách cổng (port mux). Bộ phân tách cổng chuyển các gói tin tới ứng dụng đích tương ứng. Một cổng trong số 255 cổng được dùng cho thành phần định tuyến trong nút di động. Đích mặc định trong bộ phân tách địa chỉ là thành phần định tuyến. Khi đích của gói tin không được tìm thấy bởi bộ phân tách địa chỉ, nút di động không phải đích của gói tin, gói tin sẽ được chuyển cho đích mặc định là thành phần định tuyến. Thành phần định tuyến gắn chặng tiếp theo của gói tin và gửi nó xuống lớp liên kết.

Các tham số hoạt động của DSDV trong bộ mô phỏng ns-2.34 như sau:

Tham số Giá trị

Quãng cập nhật đường định kỳ 15s

Số cập nhật định kỳ bị mất trước khi liên kết được xem là bị hỏng

Thời gian cập nhật tức thời đầu tiên được giữ trong hiệu ứng hãm

Thời gian kết hợp các quảng cáo đường 1s

Số lượng các gói tin lớn nhất trong bộ đệm mỗi nút 5

Bảng 9. Các tham số hoạt động của DSDV trong NS2

4.5.2 Giao thức định tuyến OLSR

Các tham số hoạt động của OLSR trong bộ mô phỏng ns-2.34 như sau:

Tham số Giá trị

Thời gian phát các thông điệp HELLO 2s

Thời gian phát các thông điệp TC 5s

Quãng thời gian làm mới thông tin tại mỗi nút 2s

Thời gian thông điệp HELLO là hợp lệ 6s

Thời gian thông điệp TC là hợp lệ 15s

Bảng 10. Các tham số hoạt động của OLSR trong NS2

4.5.3 Giao thức định tuyến AODV

Trong đặc tả của giao thức AODV, việc phát hiện hàng xóm được thực hiện bằng việc gửi thông điệp HELLO định kỳ. Trong phiên bản mô phỏng của AODV trong NS2, việc phát hiện liên kết hỏng được thay thế bằng thông báo từ lớp MAC. Cách tiếp cận này đã cho thấy ưu điểm là loại bỏ được tổng phí của việc gửi định kỳ các thông điệp HELLO.

Các tham số hoạt động của AODV trong bộ mô phỏng ns-2.34 như sau:

Tham số Giá trị

Thời gian đường được xem là hợp lệ 300s

Thời gian tồn tại của RREP được gửi bởi đích 600s

Số RREQ được phát lại 3

Thời gian trước khi một RREQ được phát lại 6s

Thời gian broadcastID của một gói tin RREQ được giữ 3s

Thời gian đường đi ngược lại cho RREP được giữ 3s

Thời gian trước khi liên kết bị hỏng được xóa khỏi bảng định tuyến

Phát hiện liên kết hỏng bằng lớp MAC có

Bảng 11. Các tham số hoạt động của AODV trong NS2

4.5.4 Giao thức định tuyến DSR

Nút di động của DSR không sử dụng bộ phân tách hay phân loại địa chỉ, tất cả các gói tin nhận bởi nút đều được chuyển tới thành phần định tuyến theo mặc định. Thành phần định tuyến DSR hoặc nhận gói tin cho chính nó bằng việc chuyển gói tin tới bộ phân tách cổng hoặc chuyển tiếp gói tin theo thông tin về đường trong gói tin hoặc gửi các yêu cầu đường và trả lời đường.

Mặc dù giao thức DSR hỗ trợ đường đi đơn hướng, IEEE 802.11 yêu cầu việc trao đổi RTS/CTS/Data/Ack đối với tất cả các gói tin unicast. Do vậy, phiên bản DSR được mô phỏng chỉ phát hiện các đường hai chiều.

Các tham số hoạt động của DSR trong bộ mô phỏng ns-2.34 như sau:

Tham số Giá trị

Thời gian giữa các ROUTE REQUEST được phát lại 500ms

Kích thước tiêu đề gói tin mang địa chỉ đường với n chặng 4n+ 4byte

Thời gian hết hạn tìm kiếm đường trong các hàng xóm 30ms

Thời gian giữ các gói tin chờ đường 30s

Tốc độ cao nhất việc gửi các gói tin REPLY cho một đường 1 pkt/s

Bảng 12. Các tham số hoạt động của DSR trong NS2

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

Chương này trình bày các kết quả mô phỏng từ đó rút ra những nhận xét về hiệu quả của các giao thức định tuyến khi hoạt động trong các trường hợp thay đổi vận tốc nút mạng khác nhau trong hai mô hình là Random Waypoint và Random Walk. Cuối cùng ta thực hiện việc so sánh và đánh giá các giao thức định tuyến với nhau.

5.1. Thực nghiệm mô phỏng

5.1.1 Các thông số mô phỏng

Mạng MANET có những đặc điểm là: cấu hình mạng động, các liên kết với dung lượng thay đổi - băng tần hạn chế, các nút có năng lượng thấp và bảo mật vật lý hạn chế. Do đó, khi phân tích hiệu suất các giao thức định tuyến AD HOC ta cần xem xét một số tham số của ngữ cảnh mạng như sau [24]:

 Kích thước mạng: được thể hiện bằng số các nút trong mạng.  Kết nối mạng: được thể hiện bằng số trung bình các hàng xóm của một nút.  Tốc độ thay đổi mạng: là tốc độ thay đổi tô-pô của mạng theo thời gian.  Khả năng của liên kết: là băng thông của liên kết không dây, được tính bằng bps.  Dạng truyền thông: được thể hiện bằng các mức độ tải trong mạng, có thể là

đồng dạng, không đồng dạng hoặc bùng phát.

 Dạng di chuyển: được thể hiện các mô hình chuyển động cụ thể.

Mục đích các thí nghiệm của tôi là đánh giá khả năng của các giao thức định tuyến trong việc phản hồi lại các thay đổi cấu hình mạng gây ra bởi sự di động của các nút mạng. Phương pháp của chúng tôi là áp dụng nhiều dạng di chuyển với vận tốc chuyển động của các nút khác nhau. Các mạng AD HOC mô phỏng được xây dựng dựa trên các mô hình di chuyển và mô hình truyền thông. Đối với mô hình di chuyển, chúng tôi sử dụng hai mô hình tiêu biểu Random Waypoint và Random Walk thể hiện các dạng di chuyển khác nhau được mô tả trong phần 4.3.1.2. Đối với mỗi mô hình, chúng tôi thay đổi các giá trị tham số để thay đổi các trạng thái của mạng như vận tốc chuyển động của các nút mạng, lần lượt là 0, 5, 10, 15, 20, 25, 30 m/s.

Khi so sánh các giao thức định tuyến, để đảm bảo tính công bằng, điều quan trọng là phải áp dụng các điều kiện tải và môi trường giống nhau với từng giao thức. Chính vì vậy, với mỗi mô hình di chuyển tôi xây dựng các file ngữ cảnh mô tả chính xác chuyển động của mỗi nút cùng với thời gian diễn ra sự thay đổi của nút. Còn đối với các mô hình truyền thông, các file ngữ cảnh truyền thông được tạo ra thể hiện chính xác các kết nối giữa các nút và thời gian các truyền thông này diễn ra. Do đó, tập các file ngữ cảnh chuyển động và truyền thông giống nhau được áp dụng cho từng giao thức.

Trong tất cả các thí nghiệm, tôi lựa chọn mô hình truyền thông là CBR. Tôi không sử dụng các mô hình truyền thông là các ứng dụng mô phỏng sử dụng TCP để

gửi các gói tin. Vì TCP điều phối tải theo tình trạng mạng, có nghĩa là thời gian gửi gói tin thay đổi dựa trên khả năng truyền tải hiện tại của mạng. Do vậy, thời gian mỗi gói tin được tạo ra tại bên gửi và vị trí của nút khi gửi các gói tin sẽ khác nhau giữa các giao thức do vậy khó có thể thực hiện các so sánh giữa các giao thức với nhau.

Lần lượt áp dụng các giao thức AODV, DSR, DSDV, OLSR vào các ngữ cảnh mạng khác nhau. Bộ mô phỏng ghi nhận lại các hoạt động mạng diễn ra tại các lớp. Từ các ghi nhận này, ta đánh giá khả năng làm việc của các giao thức, chủ yếu là trên lớp ứng dụng và lớp mạng. Các thí nghiệm và các đánh giá được thể hiện trong các phần sau bao gồm thí nghiệm với mô hình Random Waypoint, thí nghiệm với mô hình Random Walk. Các nhận xét về hiệu suất các giao thức được trình bày trong phần 5.3.3.

5.1.2 Chương trình mô phỏng

Chương trình mô phỏng của tôi được đặt tên là: dsdv-cbr10-rwp0-speed10.tcl,

được trình bày tại phụ lục.

Tôi đã cho thi hành chương trình mô phỏng như sau: ns dsdv-cbr10-rwp0-speed10.tcl Kết xuất thông tin ra tệp dsdv-cbr10-rwp0-speed10-out.tr để phân tích bằng các

script perl như sau:

10 >> routing_overhead.pl dsdv-cbr10-rwp0-speed10-out.tr

avg_rwp_dsdv.out, nro_rwp_dsdv.out, các

perl average_end-end_delay.pl dsdv-cbr10-rwp0-speed10-out.tr 10 >> avg_rwp1_dsdv.out perl normalized_routing_overhead.pl dsdv-cbr10-rwp0-speed10-out.tr 10 >> nro_rwp1_dsdv.out perl packet_delivery_fraction.pl dsdv-cbr10-rwp0-speed10-out.tr 10 >> pdf_rwp1_dsdv.out perl ro_rwp1_dsdv.out perl throughput.pl dsdv-cbr10-rwp0-speed10-out.tr 10 >> thr_rwp1_dsdv.out Kết quả nhận được lưu trong các file sau: avg_rwp1_dsdv.out nro_rwp1_dsdv.out pdf_rwp1_dsdv.out ro_rwp1_dsdv.out thr_rwp1_dsdv.out Để kết quả đạt độ chính xác cao hơn, ứng với mỗi vận tốc 0, 5, 10, 15, 20, 25 và 30 m/s tôi tạo 5 tệp mẫu di chuyển khác nhau. Như vậy, tổng số tệp vết được tạo ra là: 2 (mô hình di chuyển) x 4 (giao thức định tuyến) x 7 (vận tốc) x 5 (kiểu tệp mẫu di chuyển) = 280 tệp vết (*.tr). Từ những tệp vết thu được ta dùng các script perl phân tích để tính toán các độ đo hiệu năng mạng. Kết quả cuối cùng (của các độ đo hiệu năng mạng) được chọn là trung bình của 5 kết quả đã được tính toán và được trả về trong pdf_rwp_dsdv.out, file: ro_rwp_dsdv.out, thr_rwp_dsdv.out

5.2. Các độ đo hiệu năng được dùng trong luận văn

Theo nghĩa chung, hiệu năng là một độ đo công việc mà một hệ thống thực hiện được. Hiệu năng chủ yếu được xác định bởi tính sẵn sàng để dùng, thông lượng và thời gian đáp ứng. Trong mạng Ad Hoc, các giới hạn về tài nguyên mạng yêu cầu các giao thức bên cạnh các yếu tố hiệu suất nêu trên cần đảm bảo việc dùng hiệu quả các tài nguyên hạn chế này. Với các giao thức định tuyến, đó chính là chi phí để thực hiện các yêu cầu định tuyến được thể hiện bởi mức tải định tuyến.

Do vậy, chúng tôi sử dụng các độ đo sau để đánh giá hiệu quả các giao thức

định tuyến trong các mạng mô phỏng:

 Phần trăm gói tin được phân phát thành công (Packet delivery fraction): Là tỷ lệ giữa số các gói tin được phân phát thành công tới đích so với số các gói tin tạo ra bởi nguồn phát.

 Trễ đầu cuối trung bình của các gói dữ liệu (Average end to end data packet delay): Là độ trễ toàn phần được tính từ khi gói tin phát đi từ ứng dụng phát cho tới khi được nhận bởi ứng dụng nhận bao gồm các trễ có thể như trễ do quá trình phát hiện đường, xếp hàng tại các hàng đợi, trễ phát lại tại tầng MAC, và thời gian trễ truyền.

 Thông lượng dữ liệu đầu cuối (End-to-end data throughput): Tổng số dữ liệu của các gói tin tạo bởi mọi nguồn đo được trong một khoảng thời gian mô phỏng, tính bằng k bit/s.

 Tải định tuyến chuẩn hóa (Normalized Routing Load): Là tỷ lệ giữa số các gói tin định tuyến trên số gói tin dữ liệu được phân phát thành công. Nếu gói tin định tuyến đi qua nhiều chặng thì mỗi chặng được tính như một lần truyền thông. Hai độ đo đầu đánh giá kết quả làm việc của các giao thức. Các độ đo này có ý nghĩa đối với hoạt động của các giao thức lớp trên như các giao thức giao vận và các giao thức ứng dụng. Độ đo tải định tuyến chuẩn hóa thể hiện việc sử dụng các tài nguyên mạng.

5.3. Kết quả mô phỏng

5.3.1 Mô phỏng sử dụng mô hình Random Waypoint

5.3.1.1 Thiết lập thông số mô phỏng

Đối với mô hình RW, chúng tôi xây dựng mạng mô phỏng gồm 50 nút di động, hình thành nên một mạng ad hoc. Các nút này di chuyển trong một khu vực địa lý rộng 1500m x 900m (không gian phẳng). Toạ độ của các nút tại mỗi thời điểm là (x, y, z), trong đó tọa độ z = 0. Chúng tôi lựa chọn không gian hình chữ nhật để đường đi giữa các nút có độ dài lớn hơn so với trong các không gian hình vuông với mật độ nút tương đương. Cụ thể là độ dài đường lớn nhất trong mạng mô phỏng của chúng tôi là 8 chặng (trong khi không gian hình vuông là 4 chặng). Thời gian mô phỏng là 900 giây.

Tôi tạo ra 7 tệp mẫu di chuyển của nút với 7 giá trị vận tốc nút khác nhau là 0, 5, 10, 15, 20, 25 và 30 m/s. Thời gian tạm dừng 0 giây tương ứng với việc các nút di chuyển liên tục trong suốt thời gian mô phỏng.

Mô hình truyền thông được lựa chọn là CBR (constant bit rate). Đây là mô hình truyền thông được mô phỏng bởi NS2 với tốc độ phát gói tin không đổi. Tôi chọn tham số cho nguồn phát CBR có tốc độ gửi là 4 gói tin/giây với kích thước các gói tin là 512 bytes. Số lượng kết nối cho mỗi mô hình di chuyển nút là 10 nguồn phát.

Tổng kết về các cấu hình mạng mô phỏng và các tham số của các mô hình di

chuyển, mô hình truyền thông được cho trong bảng 13.

Tham số mô phỏng Giá trị

Số nút tham gia mô phỏng 50

Kích thước vùng mô phỏng (m x m) 1500 x 900

Phạm vi truyền sóng vô tuyến (m) 250

Băng thông (Mbps) 2

Kích thước gói tin (bytes) 512

Tốc độ gửi gói tin (packets/ s) 4

Dạng truyền thông Cbr

Số lượng nguồn phát 10

Thời gian tạm dừng (s) 0

Tốc độ nút di chuyển (m/s) 0-5-10-15-20-25-30

Thời gian mô phỏng (s) 900

Giao thức định tuyến mô phỏng AODV-DSDV-DSR-OLSR

Bảng 13. Cấu hình các mạng mô phỏng trong mô hình Random Waypoint

5.3.2.2 Kết quả và nhận xét

Phần trăm gói tin được phân phát thành công

Hình 27. Đánh giá kết quả phân phát gói tin trong mô hình Random Waypoint Trễ đầu cuối trung bình

Hình 28. Đánh giá kết quả trễ đầu cuối trong mô hình Random Waypoint

Thông lượng đầu cuối trung bình

Hình 29. Đánh giá kết quả thông lượng trong mô hình Random Waypoint Tải định tuyến chuẩn hóa

Hình 30. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Waypoint

Với tập các cấu hình mạng mô phỏng được xây dựng ở trên, tôi tiến hành mô phỏng, phân tích, đánh giá các kết quả làm việc giữa các giao thức dựa trên các độ đo hiệu suất. Các kết quả so sánh được cho thấy sau đây bao gồm: kết quả phân phát gói tin, độ trễ đầu cuối trung bình, thông lượng đầu cuối trung bình và tải định tuyến chuẩn hóa của bốn giao thức.

Từ hình 27, nếu coi tỷ lệ phân phát gói tin thành công là độ đo quan trọng nhất thì ta có thể đánh giá giao thức AODV hoạt động ổn định, đạt hiệu quả tốt nhất với tỷ lệ phân phát gói tin thành công trung bình trên 80%. Còn lại, 3 giao thức DSDV, DSR và OLSR thì tỷ lệ phân phát gói tin thành công xuống thấp khi vận tốc nút tăng lên. Điều này phù hợp với thông lượng đầu cuối trung bình, hình 29 cho thấy kết quả là thông lượng của AODV lớn nhất trung bình đạt trên 130 kpbs, trong khi thông lượng của DSDV, DSR và OLSR giảm dần khi vận tốc nút tăng. Những cải tiến từ DSR giúp AODV hoạt động tốt hơn, cụ thể là AODV dựa vào thiết lập động các bảng định tuyến ở các nút trung gian, điều này làm giảm rất nhiều tải định tuyến chuẩn hóa so với việc truyền từng gói tin dữ liệu chứa các tuyến đường nguồn trong tiêu đề như trong DSR. Hai nguyên nhân: Một là, DSR là giao thức phản ứng dựa trên định tuyến nguồn; hai là, trong bộ mô phỏng ns-2.34 thời gian giữa các ROUTE REQUEST được phát lại chỉ là 500 ms trong khi thời gian giữ các gói tin chờ đường là 30s dẫn đến số lượng gói tin ROUTE REQUEST là rất lớn lý giải cho vấn đề thông lượng đầu cuối trung bình thấp và độ trễ đầu cuối trung bình cao của DSR. Cuối cùng, ta thấy DSR có tải định tuyến chuẩn hóa rất cao. Từ bốn độ đo trên, trong mô hình này ta có thể đánh giá DSR hoạt động tồi khi vận tốc các nút lớn. Còn đối với AODV, đây là giao thức định tuyến phản ứng dựa trên vec tơ khoảng cách với các bảng định tuyến của các nút hàng xóm được tổ chức để tối ưu hóa thời gian phản ứng các di chuyển cục bộ và cung cấp thời gian phản ứng nhanh cho các yêu cầu thành lập tuyến đường mới. Chính sự linh hoạt này đã khiến AODV hoạt động ổn định, hiệu quả kể cả khi vận tốc các nút tăng.

Với các thể hiện của DSDV, ta có thể nhận thấy rõ hoạt động rất hiệu quả của giao thức chủ ứng dựa trên vecto khoảng cách này trong việc định tuyến khi vận tốc nút tăng. Trễ đầu cuối trung bình của DSDV rất nhỏ, khá ổn định với các mức độ linh động của nút khác nhau mặc dù độ trễ có tăng lên khi vận tốc tăng. Mặt khác, tỷ lệ phân phát gói tin thành công là khá tốt trong khi tải định tuyến chuẩn hóa rất nhỏ, điều này minh chứng cho nhận xét của ta về hoạt động hiệu quả của DSDV. Ta lý giải như sau: DSDV sử dụng cập nhật định kỳ và cập nhật sự kiện nên phản ứng tốt với sự thay đổi cấu hình mạng nhanh, mặt khác nó tối ưu hóa cập nhật bằng cách sử dụng hai loại thông điệp cập nhật là thông điệp cập nhật đầy đủ và thông điệp cập nhật bổ xung do đó trong bốn giao thức, tải định tuyến chuẩn hóa của DSDV là tốt nhất. Để tránh sự bùng nổ các cập nhật định tuyến tại các thời điểm cấu hình mạng thay đổi nhanh, DSDV cũng áp dụng cơ chế hãm các cập nhật tức thời khi có các thay đổi xảy ra trong mạng. Bằng việc ghi nhận các quãng thời gian xảy ra những thay đổi về đường, DSDV làm trễ các cập nhật tức thời theo thời gian đó. Thời gian làm trễ thường là thời gian trung bình để có được tất cả các quảng bá cập nhật cho một tuyến đường. Bằng cách này, các nút có thể chắc chắn nhận được tất cả những thay đổi đường dẫn định tuyến đến một đích trước khi lan truyền bất cứ thay đổi nào. Điều này làm giảm việc sử dụng băng thông và tiêu thụ điện năng của các nút hàng xóm. Kết quả là, trong hình 29 thông lượng của DSDV là khá tốt. Trong mô hình Random Waypoint, giao thức định

tuyến OLSR chỉ đạt hiệu quả trung bình. Mặc dù là giao thức định tuyến chủ ứng nhưng tải định tuyến chuẩn hóa của OLSR cao hơn nhiều so với DSDV do nó dựa trên định tuyến trạng thái liên kết dù đã được cải tiến bằng cách sử dụng các chuyển tiếp đa điểm (MultiPoint Relays - MPRs) để giảm chi phí flooding mạng và kích thước của các bản cập nhật trạng thái liên kết. Nhưng so với các giao thức phản ứng như AODV, DSR thì tải định tuyến chuẩn hóa của OLSR khá nhỏ. Tuy nhiên, trễ đầu cuối trung bình của OLSR là rất cao, đi kèm với phần trăm phân phát gói tin thành công thấp. Điều này là phù hợp với thông lượng đầu cuối trung bình chỉ ở mức thấp.

5.3.3 Mô phỏng sử dụng mô hình Random Walk

5.3.3.1 Thiết lập thông số mô phỏng

Với mô hình Random Walk, tôi lựa chọn cấu hình gồm 50 nút di động di chuyển trong không gian phẳng 1500m x 900m. Như đã phân tích trong phần 4.4.2.2 về các mô hình di chuyển, tham số quan trọng trong mô hình Random Walk là quãng thời gian dịch chuyển của nút trước khi thay đổi hướng và tốc độ. Nếu quãng thời gian này nhỏ, sự di chuyển của các nút sẽ bị giới hạn trong phạm vi nhỏ của khu vực mô phỏng, mạng nửa tĩnh. Nếu quãng thời gian này lớn, thay đổi của mạng sẽ thường xuyên hơn. Với mục đích chọn ra một cấu hình mạng tiêu biểu, chúng tôi đã kiểm tra các trạng thái vật lý của mạng với các giá trị thời gian dịch chuyển là 5, 10, 30, 60 và 120 giây. Cuối cùng, tôi đã sử dụng giá trị thời gian dịch chuyển của nút là 10 giây để xây dựng mạng mô phỏng cho việc đánh giá các giao thức.

Tương tự như mô hình Random Waypoint, trong mô hình Random Walk tôi cũng sử dụng 7 mẫu di chuyển của nút với 7 giá trị vận tốc nút khác nhau là 0, 5, 10, 15, 20, 25 và 30 m/s.

Về mô hình truyền thông, tôi vẫn sử dụng nguồn phát CBR với các tham số tốc độ gửi 4 gói tin/giây, kích thước gói tin 512byte. Trong thí nghiệm này, số nguồn phát là 10 nguồn.

Tổng kết về các cấu hình mạng mô phỏng được cho trong bảng 14

Tham số mô phỏng Giá trị

Số nút tham gia mô phỏng 50

Kích thước vùng mô phỏng (m x m) 1500 x 900

Phạm vi truyền sóng vô tuyến (m) 250

Băng thông (Mbps) 2

Kích thước gói tin (bytes) 512

Tốc độ gửi gói tin (packets/ s) 4

Dạng truyền thông Cbr

Số lượng nguồn phát 10

Tốc độ nút di chuyển (m/s) 0-5-10-15-20-25-30

Thời gian dịch chuyển của nút (s) 10

Thời gian mô phỏng (s) 900

Giao thức định tuyến mô phỏng AODV-DSDV-DSR-OLSR

Bảng 14. Cấu hình các mạng mô phỏng theo mô hình Random Walk

5.3.3.2 Kết quả và nhận xét

Phần trăm gói tin được phân phát thành công

Hình 31. Đánh giá kết quả phân phát gói tin trong mô hình Random Walk Trễ đầu cuối trung bình

Hình 32. Đánh giá kết quả trễ đầu cuối trong mô hình Random Walk

Thông lượng đầu cuối trung bình

Hình 33. Đánh giá kết quả thông lượng trong mô hình Random Walk Tải định tuyến chuẩn hóa

Hình 34. Đánh giá kết quả tải chuẩn hóa trong mô hình Random Walk

Hình 31 Đánh giá kết quả phân phát gói tin cho thấy một sự khác biệt với kết quả trong mô hình Random Waypoint khi DSR hoạt động hiệu quả hơn so với DSDV và OLSR đó là sự kết hợp của cả hai yếu tố phần trăm phân phát gói tin thành công của DSR tăng lên trong khi của DSDV và OLSR giảm xuống. Điều thú vị này cũng lặp lại trong hình 33 Đánh giá kết quả thông lượng. Với hai độ đo, phần trăm phân

phát gói tin thành công và thông lượng đầu cuối trung bình ta có thể sắp xếp hiệu quả hoạt động của bốn giao thức theo thứ tự giảm dần như sau: AODV; DSR; DSDV và OLSR cùng ở vị trí thứ ba.

Trễ đầu cuối trung bình được chỉ ra trong hình 32 cho thấy DSDV phản hồi tốt và ổn định nhất khi thời gian trễ luôn nhỏ hơn hoặc bằng 0.1s trong khi cơ chế của DSR đã gây ra nghẽn mạng dẫn đến trễ đầu cuối trung bình tăng cao khi vận tốc các nút tăng. Cũng giống như DSDV, OLSR có kết quả phản hổi ổn định còn trễ đầu cuối trung bình của AODV tăng khi vận tốc nút tăng. Cũng giống như trong mô hình Random Waypoint, tải định tuyến chuẩn hóa của bốn giao thức cho kết quả tương tự. Một điều dễ thấy là tải định tuyến chuẩn hóa của DSR cao nhất dù phần trăm phân phát gói tin thành công tốt hơn nhưng số gói tin định tuyến lại quá cao. Điều ngược lại xảy ra với DSDV, tải định tuyến chuẩn hóa của nó nhỏ nhất do số lượng gói tin định tuyến rất nhỏ của nó.

5.3.4 Đánh giá hiệu quả của các giao thức định tuyến

Trong cả hai mô hình Random Waypoint và Random Walk, tôi xây dựng các mạng mô phỏng với các vận tốc nút khác nhau còn các tham số hoạt động khác là giống nhau đồng thời sử dụng một tệp truyền thông duy nhất với 10 nguồn phát để đánh giá hiệu quả hoạt động của bốn giao thức định tuyến: AODV, DSR, DSDV và OLSR. Các giao thức này thuộc nhiều các kỹ thuật định tuyến khác nhau bao gồm định tuyến nguồn, định tuyến theo yêu cầu, định tuyến trước, định tuyến phân tán, định tuyến dựa trên trạng thái liên kết, định tuyến dựa trên véc tơ khoảng cách, … Từ những kết quả mô phỏng thu được, ta thấy được mỗi giao thức đã thể hiện tính hiệu quả khác nhau của các cơ chế định tuyến. Những kết luận chung nhất về hiệu suất của từng giao thức và các cơ chế định tuyến được trình bày dưới đây.

Là giao thức chủ ứng dựa trên vectơ khoảng cách, DSDV hoạt động hiệu quả trong cả hai mô hình với hai độ đo là trễ trung bình đầu cuối và tải định tuyến chuẩn hóa thấp và ổn định. Còn phần trăm phân phát gói tin thành công và thông lượng đầu cuối trung bình trong mô hình Random Walk lại thấp hơn khá nhiều so với trong mô hình Random Waypoint nhưng trong cả hai mô hình thì hai độ đo này đều giảm khi vận tốc nút tăng. Tổng hợp kết quả của bốn độ đo, ta có thể thấy được tính ổn định cùng hiệu quả khá tốt của DSDV trong hoạt động định tuyến ở cả hai mô hình.

Tương tự như DSDV, OLSR là giao thức chủ ứng nhưng dựa trên phương pháp định tuyến trạng thái liên kết. Trong mô hình Random Waypoint độ trễ đầu cuối trung bình cao hơn nhiều so với trong mô hình Random Walk mà phần trăm phân phát gói tin thành công và thông lượng đầu cuối trung bình lại cho kết quả cao hơn. Kết quả tải định tuyến chuẩn hóa ở cả hai mô hình Random Waypoint và Random Walk là giống nhau. Như vậy, ta có thể đánh giá hiệu quả hoạt động của OLSR đạt mức trung bình.

Thuộc giao thức định tuyến phản ứng, AODV là sự kết hợp cơ chế định tuyến véc tơ khoảng cách của DSDV và cơ chế định tuyến phản ứng theo yêu cầu của DSR.

Sự kết hợp này đem đến cho AODV hiệu quả hoạt động rất tốt khi vận tốc nút tăng. Trong cả hai mô hình, phần trăm phân phát gói tin thành công và thông lượng đầu cuối trung bình ổn định và cao. Trung bình của phần trăm phân phát gói tin thành công là trên 80% còn của thông lượng đầu cuối trung bình là trên 130 kbps. Với hai độ đo còn lại là trễ đầu cuối trung bình và tải định tuyến chuẩn hóa cho kết quả tương tự ở cả hai mô hình và đó là kết quả khá tốt. Đánh giá hiệu quả hoạt động của AODV ta thấy đây là một giao thức phản ứng tốt với sự linh động của các nút mạng.

Cuối cùng, ta xét đến hiệu quả hoạt động của giao thức định tuyến DSR. Cũng là giao thức phản ứng như AODV nhưng DSR dựa trên định tuyến nguồn. Do đó, DSR đã loại bỏ được các chi phí cho cập nhật định kỳ đường và phát hiện hàng xóm. Chính vì vậy, khi cấu hình mạng thay đổi nhanh chóng do các nút chuyển động nhanh thì DSR hoạt động kém hiệu quả. Kết quả trễ đầu cuối trung bình và tải định tuyến chuẩn hóa lớn đã làm rõ nhận định trên. Điều này cho thấy đặc điểm của các giao thức phản ứng theo yêu cầu là tải định tuyến thay đổi theo môi trường mạng. Khi vận tốc các nút tăng kéo theo cấu hình mạng thay đổi liên tục và nhanh chóng, tải định tuyến chuẩn hóa của các giao thức phản ứng đã cao hơn hẳn các giao thức chủ ứng. Nguyên nhân là sự bùng nổ các gói tin phát hiện đường, trả lời đường và thông báo lỗi. Mặc dù tải định tuyến chuẩn hóa không quyết định hiệu suất cuối cùng là phân phát tỷ lệ cao các gói tin thành công tới đích, tải định tuyến chuẩn hóa quá cao sẽ tiêu tốn băng thông mạng và có thể gây nên tắc nghẽn mạng. Đây chính là hạn chế của các giao thức phản ứng theo yêu cầu. Và cũng giống như DSDV, OLSR, AODV phần trăm phân phát gói tin thành công và thông lượng đầu cuối trung bình của DSR giảm khi vận tốc nút tăng. Nhận xét của ta về DSR là nó hoạt động tồi khi vận tốc nút tăng lên.

Ta có thể đưa ra một sắp xếp giảm dần về hiệu quả hoạt động của các giao thức định tuyến khi chịu ảnh hưởng của sự linh động của các nút mạng như sau: Hoạt động hiệu quả nhất là AODV khi hai độ đo quan trọng là phần trăm gói tin thành công và thông lượng đầu cuối trung bình đều cho kết quả tốt nhất; Đứng thứ hai là DSDV với tải định tuyến chuẩn hóa và trễ đầu cuối trung bình đều thấp trong khi phần trăm gói tin thành công và thông lượng đầu cuối trung bình cho kết quả chấp nhận được; OLSR đứng vị trí thứ ba khi cả bốn độ đo đều đạt kết quả trung bình; Đứng cuối cùng là DSR, giao thức này hoạt động tồi khi vận tốc nút tăng với số gói tin định tuyến rất lớn, trễ đầu cuối trung bình cao, thông lượng đầu cuối trung bình và phần trăm phân phát gói tin thành công thấp.

Chương 6: KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU

6.1. Kết quả đạt được của luận văn

Luận văn đã trình bày kiến thức cơ sở về mạng AD HOC với trọng tâm là các kết quả nghiên cứu về vấn đề định tuyến. Đi đôi với sự phát triển nhanh chóng của mạng không dây là nhu cầu kết nối mọi lúc mọi nơi kể cả trong khi di chuyển đặt ra yêu cầu giải quyết được các vấn đề giữa sự linh động của các nút với tính hiệu quả của các giao thức định tuyến trong mạng AD HOC. Đây là vấn đề khó và quan trọng trong hoạt động của loại mạng này.

Để đảm báo tính đúng đắn khi đánh giá các yêu cầu này, ngoài những phân tích định tính về các giải thuật thì ta cần đánh giá các giao thức định tuyến trong một môi trường có đủ các yếu tố phức tạp của mạng thực. Trong chương 4, Luận văn đã trình bày những nghiên cứu chi tiết về môi trường mạng, các yêu cầu đối với một giao thức định tuyến làm việc hiệu quả và xây dựng các mạng mô phỏng đáp ứng các yếu tố cần thiết mà môi trường thực có thể đặt ra cho các giao thức. Từ đó, trong chương 5 Luận văn đã đưa ra các thí nghiệm với các tham số cấu hình mạng đa dạng cho việc kiểm tra các giao thức. Với những kết quả tính toán thu được, tôi đã có những đánh giá định lượng về hiệu quả của các giao thức và cho phép có thể so sánh các yếu tố hoạt động khác nhau giữa các giao thức.

Cụ thể, tôi đã xem xét chi tiết hoạt động của bốn giao thức định tuyến AODV, DSR, DSDV và OLSR với vận tốc di chuyển của các nút lần lượt là: 0, 5, 10, 15, 20, 25, 30 m/s. Dựa trên các kỹ thuật định tuyến mà bốn giao thức này sử dụng là khác nhau: AODV là giao thức phản ứng dựa trên bảng véc tơ khoảng cách, DSR là giao thức phản ứng dựa trên định tuyến nguồn, DSDV là giao thức chủ ứng dựa trên véc tơ khoảng cách và OLSR là giao thức chủ ứng dựa trên trạng thái liên kết. Kết hợp với kết quả mô phỏng đã cho thấy các kết luận như sau:

 DSDV đạt hiệu quả làm việc tốt khi vận tốc các nút mạng thay đổi. Ưu điểm của DSDV là tải định tuyến chuẩn hóa ổn định và trễ đầu cuối trung bình thấp. Tuy nhiên, tỷ lệ phân phát gói tin thành công và thông lượng cần được cải thiện.

 OLSR mặc dù là giao thức chủ ứng như DSDV nhưng trong cả hai mô hình đều

cho kết quả hoạt động ở mức trung bình.

 AODV là giao thức phản ứng có kết quả hoạt động tốt nhất, trong các trường hợp khác nhau của sự linh động của nút mạng phần trăm phân phát gói tin thành công và thông lượng đầu cuối trung bình tốt nhất. Tuy nhiên, tải định tuyến chuẩn hóa gây khó khăn cho hoạt động của AODV.

 DSR hoạt động rất tồi do các cơ chế của giao thức này chưa tối ưu khi cấu hình mạng thay đổi nhanh với sự bùng nổ các gói tin điều khiển dẫn đến tải định tuyến rất lớn khi sự linh động của các nút mạng ở mức cao.

6.2. Hướng nghiên cứu

Với những kết quả nghiên cứu mà luận văn đã đạt được, ta có được cái nhìn khái quát về mối quan hệ giữa sự linh động của các nút với tính hiệu quả của các giao thức định tuyến trong mạng AD HOC. Tuy nhiên, còn rất nhiều các vấn đề khác của các giao thức cần được xem xét như sau:

 Đánh giá ảnh hưởng của sự di động của nút mạng đến hiệu quả của những giao

thức khác: TORA, ZRP …

 Định tuyến multicast,…  Nghiên cứu, xây dựng và triển khai các vấn đề về an ninh cho mạng vô tuyến

Ad hoc.

 Vấn đề giảm phụ tải truyền thông trong mạng MANET.  Các yêu cầu hiệu suất liên quan tới các ứng dụng cụ thể như vấn đề đảm bảo

chất lượng dịch vụ (QoS),…

 Vấn đề kết nối mạng AD HOC với Internet.

TÀI LIỆU THAM KHẢO

Tiếng Việt

1. Nguyễn Đình Việt (2008), Bài giảng đánh giá hiệu năng mạng máy tính, Trường

Đại học Công nghệ - Đại học quốc gia Hà Nội.

Tiếng Anh

2. Andrea Goldsmith (2005), Wireless Communications, Cambridge University Press. 3. Eitan Altman, Tania Jiménez (2003), NS Simulator for beginners,

4. Stefano Basagni, Marco Conti, Silvia Giordano and Ivan Stojmenovic (2004),

Mobile AdHoc Networking, A John Wiley & Sons., Publication.

5. Torbjörn Grape (2003), Wireless LANs Real-Time Traffic, Master’s Thesis,

Linköping University, Sweden.

6. Yasser Kamal Hassan, Mohamed Hashim Abd El-Aziz and Ahmed Safwat Abd El- Radi (2010), Performance Evaluation of Mobility Speed over MANET Routing Protocols, International Journal of Network Security.

7. P. Nicopolitidis, M.S.Obaidat, G.I.Papadimitriou, A.S.Pomportsis (2003), Wireless

networks, John Wiley & Son Ltd.

8. Timo Ralli (2006), National strategies for public WLAN roaming, Master’s

Thesis, Technology Helsinki.

9. Mohd Izuan Mohd Saad, Zuriati Ahmad Zukarnain (2009), Performance Analysis of Random-Based Mobility Models in MANET Routing Protocol, European Journal of Scientific Research.

10. Subir Kumar Sarkar, T G Basavaraju, C Puttamadappa, Ad Hoc Mobile Wireless

Networks, Auerbach Publications.

11. Yinfei Pan, Design Routing Protocol Performance Comparison in NS2: AODV

comparing to DSR as Example

12. VINT Project, UC Berkely, LBL, USC/ISI, and Xerox PARC. (2005), The ns

Manual (formerly ns Notes and Documentation)

13. http://www.eetimes.com

14. http://www.flickr.com

15. http://www.isi.edu/nsnam/ns/tutorial/

16. http://en.wikipedia.org/

17. http://t16web.lanl.gov/Kawano/gnuplot/index-e.html

18. http://4ellene.net/tt/1077

19. http://mailman.isi.edu/pipermail/ns-users/2007-August/060797.html

20. http://toilers.mines.edu/Public/Code/Nsinspect.html

21. http://masimum.inf.um.es/?Software:UM-OLSR:Installation 22. http://users.crhc.illinois.edu/thkim/ece439/ns2_assignment2.htm

PHỤ LỤC

Propagation/TwoRayGround Phy/WirelessPhy

Queue/DropTail/PriQueue LL Antenna/OmniAntenna

;# X dimension of the topography ;# Y dimension of the topography ;# max packet in ifq

dsdv-cbr10-rwp0-speed10.tcl # ============================================================ # Define options # ============================================================ set val(chan) Channel/WirelessChannel set val(prop) set val(netif) set val(mac) Mac/802_11 set val(ifq) set val(ll) set val(ant) set val(x) 1500 set val(y) 900 set val(ifqlen) 50 set val(seed) 1.0 set val(adhocRouting) DSDV set val(nn) 50 ;# how many nodes are simulated set val(cp) "/home/phd1983/ns-2.34/protocols/cbr/cbr-50-10-4" set val(sc) "/home/phd1983/ns-2.34/protocols/scen/rwp/rwp-1500-900-50-0-10-0" set val(stop) 900.0 ;# simulation time # ============================================================ # Main Program # ============================================================ # # Initialize Global Variables #

[new Simulator]

[new Topography]

[open dsdv-cbr10-rwp0-speed10-out.tr w]

# create simulator instance set ns_ # setup topography object set topo # create trace object for ns and nam set tracefd set namtrace [open dsdv-cbr10-rwp0-speed10-out.nam w] $ns_ trace-all $tracefd $ns_ namtrace-all-wireless $namtrace $val(x) $val(y) # define topology $topo load_flatgrid $val(x) $val(y) # # Create God # set god_ [create-god $val(nn)] # # define how node should be created # #global node setting $ns_ node-config -adhocRouting $val(adhocRouting) \ -llType $val(ll) \ -macType $val(mac) \ -ifqType $val(ifq) \ -ifqLen $val(ifqlen) \ -antType $val(ant) \ -propType $val(prop) \ -phyType $val(netif) \ -channelType $val(chan) \ -topoInstance $topo \ -agentTrace ON \ -routerTrace ON \ -movementTrace ON \

-macTrace OFF

; # disable random motion

$ns_ initial_node_pos $node_($i) 50

$ns_ at $val(stop).0 "$node_($i) reset";

# # Create the specified number of nodes [$val(nn)] and "attach" them to the channel. # for {set i 0} {$i < $val(nn) } {incr i} { set node_($i) [$ns_ node] $node_($i) random-motion 0 } # # Define node movement model # puts "Loading connection pattern..." source $val(cp) # # Define traffic model # puts "Loading scenario file..." source $val(sc) # Define node initial position in nam for {set i 0} {$i < $val(nn)} {incr i} { } # # Tell nodes when the simulation ends # for {set i 0} {$i < $val(nn) } {incr i} { } $ns_ at $val(stop).0002 "puts \"NS EXITING...\" ; $ns_ halt" puts $tracefd "M 0.0 nn $val(nn) x $val(x) y $val(y) rp $val(adhocRouting)" puts $tracefd "M 0.0 sc $val(sc) cp $val(cp) seed $val(seed)" puts $tracefd "M 0.0 prop $val(prop) ant $val(ant)"

{$start_time = $x[1]; }

if (( $x[0] eq "s") && ( $x[6] eq "cbr" ) && ( $x[3] eq "AGT" )) if (( $x[0] eq "r") && ( $x[6] eq "cbr" ) && ( $x[3] eq "AGT" )) {$end_time = $x[1]; $recvnum++;} $packet_duration =$end_time - $start_time; if ( $packet_duration > 0 ) { $sum += $packet_duration; }

puts "Starting Simulation..." $ns_ run average_end-end_delay.pl # type: perl average_end-end_delay.pl # --------------------------------------------------------------------------- $infile=$ARGV[0]; $speed=$ARGV[1]; $sum=0; $recvnum=0; # --------------------------------------------------------------------------- open (DATA,"<$infile") || die "Can't open $infile $!"; while () { @x = split(' '); for ($x[5]) { } } # --------------------------------------------------------------------------- $delay=$sum/$recvnum; #print STDOUT "Total delay time of packets = $sum\n"; #print STDOUT "Total packets = $recvnum\n";

if (( $x[0] eq "r") && ( $x[6] eq "cbr" ) && ( $x[3] eq "AGT" ))

if (( $x[0] eq "s" || $x[0] eq "f") && ( $x[6] eq "message" ) && ( $x[3] eq

print STDOUT "$speed", " ", "$delay\n"; close DATA; exit(0); normalized_routing_overhead.pl # type: perl normalized_routing_overhead.pl # --------------------------------------------------------------------------- $infile=$ARGV[0]; $speed=$ARGV[1]; $routing_packets=0; $sum_received=0; # --------------------------------------------------------------------------- open (DATA,"<$infile") || die "Can't open $infile $!"; while () { @x = split(' '); {$sum_received++; } "RTR" )) {$routing_packets++; } } # --------------------------------------------------------------------------- $normalized_routing_overhead=($routing_packets/$sum_received); #print STDOUT "Total packets received = $sum_received\n"; #print STDOUT "Total routing packets sent & forward = $routing_packets\n"; print STDOUT "$speed", " ", "$normalized_routing_overhead \n"; close DATA; exit(0);

{$sum_sent++; }

if (( $x[0] eq "s") && ( $x[6] eq "cbr" ) && ( $x[3] eq "AGT" )) if (( $x[0] eq "r") && ( $x[6] eq "cbr" ) && ( $x[3] eq "AGT" )) {$sum_received++; }

packet_delivery_fraction.pl # type: perl packet_delivery_fraction_ratio.pl # --------------------------------------------------------------------------- $infile=$ARGV[0]; $speed=$ARGV[1]; $sum_sent=0; $sum_received=0; # --------------------------------------------------------------------------- open (DATA,"<$infile") || die "Can't open $infile $!"; while () { @x = split(' '); } # --------------------------------------------------------------------------- $packet_delivery_ratio=($sum_received/$sum_sent)*100; #print STDOUT "Total packets sent = $sum_sent\n"; #print STDOUT "Total packets received = $sum_received\n"; print STDOUT "$speed", " ", "$packet_delivery_ratio\n"; close DATA; exit(0);

$startTime = $x[1];

if ($x[1] < $startTime) { }

$stopTime = $x[1];

if ($x[1] > $stopTime) { } # Rip off the header $hdr_size = $pkt_size % 512; $pkt_size -= $hdr_size; # Store received packet's size $recvdSize += $pkt_size;

@x = split(' '); $pkt_size = $x[7]; # Store start time if (($x[3] eq "AGT") && ($x[0] eq "s") && ($pkt_size >= 512)) { } # Update total received packets' size and store packets arrival time if (($x[3] eq "AGT") && ($x[0] eq "r") && ($pkt_size >= 512)) { }

throughput.pl # type: throughput.pl # --------------------------------------------------------------------------- $infile=$ARGV[0]; $speed=$ARGV[1]; $recvdSize = 0; $startTime = 1000; $stopTime = 0; # --------------------------------------------------------------------------- open (DATA,"<$infile") || die "Can't open $infile $!"; while () { } # ---------------------------------------------------------------------------

",($recvdSize/($stopTime-$startTime)) *

#print("Average Throughput[kbps] = (8/1000)," ",$startTime," ","$stopTime\n"); print STDOUT "$speed", " ", ($recvdSize/($stopTime-$startTime))*(8/1000),"\n"; close DATA; exit(0);

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

ĐẠ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

Lời cảm ơn

Danh mục bảng

PHỤ LỤC

Có thể bạn quan tâm

Tài liêu mới

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

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

ĐẠ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

Lời cảm ơn

Danh mục bảng

PHỤ LỤC

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok