Nghiên Cứu và Mô Phỏng Giao Thức AODV Trên Công Cụ NS2

Hiện nay, các hệ thống mạng ngày càng phức tạp, đòi hỏi phải đáp ứng nhiều loại dịch vụ khác nhau, với tốc độ… 65 trang · Trường Đại Học Quảng Nam · 2017.

• Tác giả: Phạm Thị Phương Thùy
• Người hướng dẫn: TS. Nguyễn Hà Huy Cường
• Trường học: Trường Đại Học Quảng Nam
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Nghiên Cứu và Mô Phỏng Giao Thức AODV Trên Công Cụ NS2
• Loại tài liệu: khóa luận tốt nghiệp
• Năm xuất bản: 2017
• Địa điểm: Quảng Nam

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. CHƯƠNG I: TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY WSN VÀ GIAO THỨC AODV
• 1.1. Giới thiệu tổng quan về mạng cảm biến không dây
• 1.2. Cấu trúc của mạng cảm biến không dây
• 1.3. Đặc điểm của mạng cảm biến không dây
• 1.4. Khái quát về giao thức AODV
• 1.4.1. Giới thiệu về giao thức AODV
• 2. CHƯƠNG II: CƠ SỞ NGHIÊN CỨU VỀ GIAO THỨC AODV
• 2.1. Các thuật toán sử dụng trong mạng không dây
• 2.1.1. Thuật toán Vectơ khoảng cách (Distance Vector Algorithm)
• 2.1.2. Thuật toán trạng thái liên kết (Link State Algorithm)
• 2.1.3. Thuật toán AODV. Ý tưởng của thuật toán AODV
• 2.1.4. Lưu đồ thuật toán AODV
• 2.1.5. Mô tả thuật toán AODV
• 2.2. Thuật ngữ AODV
• 2.3. Hoạt động của AODV
• 2.3.1. Duy trì số trình tự. Các mục của bảng định tuyến và danh sách chặn trước
• 2.3.2. Khởi tạo các yêu cầu của Router
• 2.3.3. Điều khiển sự phân phát các bản tin yêu cầu của Router
• 2.3.4. Xử lý và chuyển tiếp các yêu cầu của Router. Duy trì kết nối cục bộ
• 2.3.5. Khởi tạo các yêu cầu của router
• 3. CHƯƠNG III: MÔ PHỎNG GIAO THỨC AODV TRÊN CÔNG CỤ NS2
• 3.1. Giới thiệu về môi trường mô phỏng NS-2
• 3.2. Tổng quan về NS-2
• 3.3. Các đặc điểm của NS-2
• 3.4. Giới thiệu phần mềm Nam dùng kết hợp với NS-2
• 3.5. Cài đặt Cygwin
• 3.6. Mô phỏng giao thức AODV
• 3.7. Thời gian di chuyển của các nút
• KẾT LUẬN VÀ KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Nghiên Cứu Giao Thức AODV Trên NS2 Bắt Đầu

Hiện nay, các hệ thống mạng ngày càng phức tạp, đòi hỏi phải đáp ứng nhiều loại dịch vụ khác nhau, với tốc độ dịch vụ khác nhau. Lưu lượng các gói tin trên đường truyền không ngừng tăng lên, nhiều lúc dẫn đến tắc nghẽn. Vì vậy, việc sử dụng các phương pháp giải thích ngày càng trở nên phức tạp trong tính toán các đối tượng ngẫu nhiên, đồng thời khó có những mô hình thực tế để đo thử nghiệm nên việc sử dụng các hệ thống mô phỏng máy tính trở nên thuận lợi hơn. Phương pháp mô phỏng là sử dụng chương trình phần mềm xây dựng các đối tượng trong mạng dựa trên Topology đã được thiết kế. Hiện tại có rất nhiều phần mềm mô phỏng. Một trong số đó là NS2 một sản phẩm phần mềm lớn, chuyên dụng cho việc mô phỏng. Xu hướng phát triển chung mạng vô tuyến đã và đang được ứng dụng rộng rãi trong cuộc sống bởi lợi ích mà nó mang lại. Việc nghiên cứu về mạng vô tuyến cũng tăng trưởng tương tự.

1.1. Lý Do Chọn Nghiên Cứu Giao Thức AODV và NS2

Số lượng các thiết bị dùng cho mạng vô tuyến sẽ nhanh chóng vượt qua số lượng các thiết bị dùng cho mạng hữu tuyến. Việc sử dụng các hệ thống mô phỏng như NS2 trở nên quan trọng để giải quyết các vấn đề phức tạp trong mạng. Khóa luận này sẽ làm rõ hơn về giao thức định tuyến AODV và được sự gợi ý của Thầy TS. Nguyễn Hà Huy Cường em chọn đề tài “Nghiên cứu và mô phỏng giao thức AODV trên công cụ NS2” để làm báo cáo khóa luận tốt nghiệp.

1.2. Mục Tiêu Nghiên Cứu Chi Tiết Về Giao Thức AODV

Mục tiêu chính của nghiên cứu là tìm hiểu sâu về mạng cảm biến không dây, giới thiệu về giao thức AODV, tìm hiểu cơ chế hoạt động. Nghiên cứu này đi sâu vào giao thức AODV và mô phỏng nó trên công cụ NS2. Nghiên cứu này tập trung vào việc sử dụng chương trình mô phỏng NS2 để mô phỏng quá trình định tuyến trong mạng.

1.3. Phạm Vi Nghiên Cứu Giao Thức AODV Trên Công Cụ NS2

Đề tài tập trung nghiên cứu mô phỏng giao thức AODV trên công cụ NS2. Nghiên cứu sử dụng phương pháp nghiên cứu lý thuyết về mạng cảm biến không dây, giao thức AODV, và công cụ mô phỏng NS2. Thực nghiệm bằng công cụ mô phỏng NS2; Thu thập, phân tích các tài liệu và thông tin liên quan đến đề tài.

II. Tìm Hiểu Về Mạng Cảm Biến Không Dây WSN Và AODV

Với sự phát triển của công nghệ thông tin, mạng máy tính là một lĩnh vực đem lại hiệu quả thiết thực. Thông qua mạng máy tính, chúng ta có thể chia sẻ thông tin ở bất kỳ nơi nào trên mạng, tìm kiếm thông tin một cách nhanh chóng, chính xác và hiệu quả. Cùng với sự ra đời các thiết bị di động thì nhu cầu nghiên cứu và phát triển các hệ thống mạng không dây ngày càng trở nên cấp thiết. Mạng cảm biến không dây (Wireless Sensor Network) bao gồm một tập hợp các thiết bị cảm biến sử dụng các liên kết không dây để phối hợp thực hiện nhiệm vụ thu thập thông tin dữ liệu phân tán với quy mô lớn.

2.1. Chức Năng và Ứng Dụng Của Mạng Cảm Biến Không Dây WSN

Mạng cảm biến không dây có thể liên kết trực tiếp với nút quản lý giám sát trực tiếp hay gián tiếp thông qua một điểm thu phát (Sink) và môi trường mạng công cộng như Internet hay vệ tinh. Các nút cảm biến không dây có thể được triển khai cho các mục đích chuyên dụng như điều khiển giám sát và an ninh; kiểm tra môi trường; tạo ra không gian sống thông minh; khảo sát đánh giá chính xác trong nông nghiệp; trong lĩnh vực y tế; .

2.2. Cấu Trúc Cơ Bản Của Mạng Cảm Biến Không Dây WSN

Một mạng cảm biến không dây bao gồm số lượng lớn các nút được triển khai dày đặc bên trong hoặc ở rất gần đối tượng cần thăm dò, thu thập thông tin dữ liệu. Vị trí các cảm biến không cần định trước vì vậy nó cho phép triển khai ngẫu nhiên trong các vùng không thể tiếp cận hoặc các khu vực nguy hiểm. Khả năng tự tổ chức mạng và cộng tác làm việc của các cảm biến không dây là những đặc trưng rất cơ bản của mạng này.

2.3. Đặc Điểm Nổi Bật Của Mạng Cảm Biến Không Dây WSN

Hoạt động chính của các thiết bị trong mạng cảm biến là đo lường và vận chuyển các dòng thông tin với khối lượng xử lý thấp. Do dung lượng bộ nhớ trong nhỏ nên cần tính toán rất kỹ về khối lượng công việc cần xử lý và các sự kiện mức thấp xen vào hoạt động xử lý mức cao. Một số hoạt động xử lý mức cao sẽ khá lâu và khó đáp ứng tính năng thời gian thực. Tính năng điều khiển ở các nút cảm biến không dây cũng như sự tinh vi của liên kết xử lý lưu trữ chuyển mạch trong mạng cảm biến không dây thấp hơn nhiều trong các hệ thống thông thường.

III. Giao Thức AODV Cơ Chế Định Tuyến Hiệu Quả Cho NS2

Giao thức AODV (Ad hoc On Demand Distance Vector) cho phép định tuyến nhiều bước giữa các nút mạng để thiết lập và duy trì mạng Ad hoc. Thuật toán định tuyến này dựa trên thuật toán vectơ khoảng cách nhưng thuộc loại định tuyến theo yêu cầu, nó chỉ yêu cầu đường định tuyến khi cần thiết. Thuật toán định tuyến AODV khá phù hợp cho cấu hình mạng động. AODV đưa ra các tuyến không bị lặp ngay cả khi nó đang sửa các liên kết lỗi.

3.1. Tổng Quan Về Giao Thức Định Tuyến AODV Trong Mạng

AODV sử dụng liên kết đối xứng giữa các nút hàng xóm. Gói tin không đi theo tuyến đường giữa các nút khi một trong những nút đó không nghe được từ nút khác. Những nút không nằm trên các tuyến đường hoạt động; chúng sẽ không duy trì bất cứ thông tin định tuyến nào cũng như không tham gia vào bất kỳ sự trao đổi bảng định tuyến định kỳ nào. Khi một kết nối cục bộ của nút di động được thiết lập, mỗi nút có thể nhận thấy các nút khác trong vùng lân cận của nó bằng một vài kĩ thuật, bao gồm quảng bá cục bộ các bản tin Hello.

3.2. Cơ Chế Duy Trì Thông Tin Định Tuyến Của AODV

Khi một nút mạng muốn gửi một gói tin tới một nút nào đó, nó sẽ khởi tạo tiến trình xử lý discovery để định vị nút đích. Nếu không có một đường đi nào được tìm thấy trong một khoảng thời gian xác định, nút khởi tạo sẽ cho rằng không tồn tại đường đi tới nút đích. Tiến trình xử lý discovery sẽ kết thúc đồng thời các gói tin tương ứng sẽ hủy bỏ. Ngược lại nếu nút khởi tạo tìm được một đường đi phù hợp, nó sẽ cập nhật đường đi này vào bảng định tuyến của nó như một đầu vào (entry) tương ứng với nút đích.

3.3. Quản Lý Bảng Định Tuyến Trong Giao Thức AODV

Khi một đầu vào mới được tạo ra, tiến trình xử lý cũng đồng thời được kích hoạt để giám sát tình trạng của đường đi vừa được tạo ra, nếu sau một khoảng thời gian đủ lớn mà đường đi không được sử dụng, nút mạng sẽ xóa đường đi này ra khỏi bảng định tuyến. Nếu có lỗi xuất hiện trên một đường đi có trạng thái tích cực, nút mạng sẽ lập tức thông báo ngược lại cho các bước truyền trước đó bằng một gói tin điều khiển cụ thể.

IV. Cơ Sở Nghiên Cứu Thuật Toán AODV Hướng Dẫn Chi Tiết

Chương này đi sâu vào cơ sở nghiên cứu của giao thức AODV, bao gồm các thuật toán sử dụng trong mạng không dây, thuật toán vectơ khoảng cách, thuật toán trạng thái liên kết và thuật toán AODV. Ý tưởng, lưu đồ và mô tả chi tiết thuật toán AODV sẽ được trình bày, giúp người đọc hiểu rõ hơn về cách thức hoạt động của giao thức này. Nghiên cứu về thuật toán AODV rất quan trọng.

4.1. Các Thuật Toán Định Tuyến Trong Mạng Không Dây

Nghiên cứu bao gồm thuật toán Vectơ khoảng cách (Distance Vector Algorithm) và thuật toán trạng thái liên kết (Link State Algorithm). Tìm hiểu chi tiết cách thức hoạt động và ưu nhược điểm của từng thuật toán. So sánh sự khác biệt giữa các thuật toán định tuyến này.

4.2. Ý Tưởng và Lưu Đồ Của Thuật Toán AODV

Trình bày ý tưởng chính của thuật toán AODV. Phân tích lưu đồ thuật toán AODV để hiểu rõ các bước thực hiện. Diễn giải các giai đoạn chính trong quá trình định tuyến của AODV.

4.3. Mô Tả Chi Tiết Thuật Toán AODV

Mô tả chi tiết từng bước trong thuật toán AODV. Giải thích cách thức hoạt động của các gói tin RREQ, RREP, và RERR. Phân tích cách AODV duy trì thông tin định tuyến và xử lý lỗi.

V. Mô Phỏng Giao Thức AODV Trên Công Cụ NS2 Thực Hành

Chương này giới thiệu về môi trường mô phỏng NS-2, bao gồm tổng quan về NS-2, các đặc điểm của NS-2, và cách cài đặt Cygwin. Hướng dẫn chi tiết các bước mô phỏng giao thức AODV trên NS-2, từ việc thiết lập cấu hình mạng đến phân tích kết quả mô phỏng. Mô phỏng AODV giúp hiểu rõ hơn.

5.1. Tổng Quan Về Môi Trường Mô Phỏng NS 2

Giới thiệu về NS-2 và vai trò của nó trong mô phỏng mạng. Trình bày các đặc điểm nổi bật của NS-2. Giải thích về phần mềm Nam và cách sử dụng nó kết hợp với NS-2.

5.2. Hướng Dẫn Cài Đặt Cygwin Để Sử Dụng NS 2

Hướng dẫn từng bước cài đặt Cygwin để chạy NS-2 trên Windows. Giải thích các cấu hình cần thiết để NS-2 hoạt động ổn định. Khắc phục các lỗi thường gặp trong quá trình cài đặt.

5.3. Các Bước Mô Phỏng Giao Thức AODV Trên NS 2

Hướng dẫn chi tiết cách viết script TCL để mô phỏng AODV. Thiết lập các thông số mạng như số lượng nút, tốc độ truyền, và vùng phủ sóng. Phân tích kết quả mô phỏng và đánh giá hiệu suất của AODV.

VI. Kết Luận và Hướng Phát Triển Giao Thức AODV Trên NS2

Tổng kết lại các kết quả đạt được trong quá trình nghiên cứu và mô phỏng giao thức AODV trên công cụ NS2. Đề xuất các hướng phát triển tiếp theo cho đề tài, bao gồm việc cải tiến giao thức AODV, thử nghiệm trên các mô hình mạng phức tạp hơn, và ứng dụng vào các lĩnh vực thực tế. Nghiên cứu AODV vẫn còn nhiều tiềm năng.

6.1. Tóm Tắt Kết Quả Nghiên Cứu và Mô Phỏng

Đánh giá lại các mục tiêu đã đạt được trong đề tài. Nhấn mạnh tầm quan trọng của việc mô phỏng giao thức AODV trên NS2. Nêu bật những ưu điểm và hạn chế của giao thức AODV.

6.2. Các Hướng Phát Triển Tiếp Theo Cho Đề Tài

Đề xuất các hướng nghiên cứu sâu hơn về giao thức AODV. Gợi ý các cải tiến có thể thực hiện để nâng cao hiệu suất của AODV. Mở rộng phạm vi nghiên cứu sang các giao thức định tuyến khác.

6.3. Ứng Dụng Thực Tế Của Giao Thức AODV

Thảo luận về các ứng dụng tiềm năng của giao thức AODV trong thực tế. Nêu ví dụ về việc sử dụng AODV trong các mạng cảm biến không dây, mạng di động ad-hoc, và các hệ thống IoT. Đề xuất các giải pháp để triển khai AODV một cách hiệu quả trong các ứng dụng thực tế.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh công nghệ thông tin và truyền thông phát triển mạnh mẽ, các hệ thống mạng máy tính ngày càng trở nên phức tạp nhằm đáp ứng đa dạng các loại hình dịch vụ với tốc độ và lưu lượng truyền tải không ngừng gia tăng. Sự bùng nổ lưu lượng gói tin trên đường truyền thường xuyên dẫn đến hiện tượng nghẽn mạng. Việc áp dụng các phương pháp giải tích truyền thống để tính toán và đánh giá các đối tượng ngẫu nhiên trong mạng gặp nhiều khó khăn, đồng thời chi phí thiết lập mô hình thực nghiệm vật lý là rất lớn. Do đó, phương pháp mô phỏng trên máy tính thông qua các phần mềm chuyên dụng như NS-2 (Network Simulator 2) trở thành giải pháp tối ưu, cho phép xây dựng và kiểm thử các topo mạng phức tạp trước khi đưa vào ứng dụng thực tế.

Bên cạnh đó, mạng vô tuyến nói chung và mạng cảm biến không dây (Wireless Sensor Network - WSN), mạng di động tùy biến (MANET) nói riêng đang phát triển nhanh chóng. Số lượng thiết bị vô tuyến có xu hướng vượt trội so với thiết bị mạng hữu tuyến, đòi hỏi các giao thức định tuyến phải đảm bảo tính thích ứng cao với sự thay đổi liên tục của topo mạng và hạn chế tiêu hao năng lượng.

Khóa luận tốt nghiệp của tác giả Phạm Thị Phương Thùy, dưới sự hướng dẫn của TS. Nguyễn Hà Huy Cường tại Khoa Công nghệ Thông tin - Trường Đại học Quảng Nam (thực hiện tháng 04/2017), tập trung vào đề tài: "Nghiên cứu và mô phỏng giao thức AODV trên công cụ NS2".

Mục tiêu và nhiệm vụ nghiên cứu của đề tài được xác định gồm 4 nội dung:

1. Nghiên cứu tổng quan về mạng cảm biến không dây (WSN).
2. Giới thiệu về giao thức AODV (Ad-hoc On Demand Distance Vector) và tìm hiểu cơ chế hoạt động chi tiết của giao thức.
3. Đi sâu nghiên cứu cấu trúc thuật toán định tuyến AODV và giải pháp cải tiến định tuyến nhằm giảm thiểu tắc nghẽn mạng.
4. Mô phỏng và đánh giá giao thức AODV trên công cụ phần mềm NS-2 kết hợp trình diễn đồ họa Nam.

Đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Các nguyên lý cơ bản của giao thức mạng, giao thức định tuyến vectơ khoảng cách theo yêu cầu AODV trong môi trường mạng không dây, và công cụ mô phỏng mạng NS-2.
• Phạm vi nghiên cứu: Nghiên cứu cơ chế định tuyến, xử lý gói tin điều khiển của giao thức AODV và thực nghiệm mô phỏng hoạt động định tuyến trên phần mềm NS-2 chạy trên nền tảng giả lập Cygwin.

---

Cơ sở lý thuyết và phương pháp

Khóa luận xây dựng trên nền tảng lý thuyết mạng truyền thông không dây, lý thuyết đồ thị và các thuật toán định tuyến phân tán trong mạng máy tính:

• Khung lý thuyết định tuyến: Phân tích hai trường phái thuật toán định tuyến kinh điển gồm thuật toán Vectơ khoảng cách (Distance Vector Algorithm dựa trên giải thuật Bellman-Ford) và thuật toán Trạng thái liên kết (Link State Algorithm dựa trên giải thuật Dijkstra).
• Mô hình giao thức AODV: Giao thức định tuyến phản ứng (reactive/on-demand), hoạt động đa chặng (multi-hop), không duy trì toàn bộ bảng định tuyến định kỳ như các giao thức chủ động (proactive như DSDV), sử dụng số thứ tự đích (Destination Sequence Number - DSN) để đảm bảo không xảy ra vòng lặp định tuyến (loop-free).
• Phương pháp nghiên cứu:
  • Phương pháp nghiên cứu lý thuyết: Thu thập, tổng hợp, phân tích tài liệu chuyên ngành về mạng cảm biến không dây, cấu trúc gói tin AODV (RREQ, RREP, RERR, HELLO) và cơ chế quản lý bảng định tuyến.
  • Phương pháp mô phỏng thực nghiệm: Cài đặt môi trường mô phỏng NS-2 (Network Simulator 2), môi trường giả lập Unix/Linux Cygwin trên hệ điều hành Windows, kết hợp công cụ trực quan hóa mạng Nam (Network Animator) để kiểm thử và phân tích hoạt động truyền nhận gói tin.
• Nguồn dữ liệu: Các chuẩn giao tiếp mạng không dây (IEEE 802.11), các thông số kỹ thuật chuẩn của giao thức AODV (sử dụng cổng UDP 654, địa chỉ IP broadcast giới hạn 255.255), các tài liệu kỹ thuật từ Đại học UC Berkeley và các công trình nghiên cứu về WSN/MANET.

---

Nội dung chính theo từng chương

Chương 1: Tổng quan về mạng cảm biến không dây WSN và giao thức AODV

Chương này trình bày toàn diện về kiến trúc mạng cảm biến không dây và khái quát vị trí của giao thức AODV trong mô hình mạng tùy biến:

• Khái niệm và cấu trúc nút WSN: Nút cảm biến gồm 4 thành phần cơ bản: bộ cảm biến (đầu đo và bộ chuyển đổi tương tự/số ADC), bộ xử lý (kèm bộ nhớ nhỏ), bộ thu phát không dây (sóng vô tuyến, hồng ngoại hoặc quang) và bộ nguồn (pin, ắc quy hoặc pin năng lượng mặt trời). Ngoài ra có thể có thành phần phụ trợ như hệ thống định vị vị trí và bộ phận di động.
• So sánh đặc tính WSN với các mạng vô tuyến khác: So với mạng Cellular, WLAN hay Bluetooth/HomeRF, mạng WSN có số lượng nút lớn hơn nhiều, khoảng cách giữa các nút láng giềng ngắn, chi phí sản xuất thấp, mức tiêu thụ năng lượng cực thấp, tốc độ dữ liệu và tính di động ở mức vừa phải hoặc thấp.

STT	Chức năng trong WSN	Nội dung chi tiết
1	Định tuyến và phổ biến dữ liệu	Chia thành 3 nhóm (dữ liệu trung tâm, kiến trúc mạng, căn cứ vị trí). Hạn chế dữ liệu dư thừa, giảm tiêu thụ năng lượng và xử lý dữ liệu tại nguồn.
2	Sắp xếp mạng và theo dõi	Quản lý phân nhóm cảm biến, tự tổ chức mạng và thiết lập phiên làm việc.
3	Tập hợp dữ liệu	Dung hợp, tính toán cấu trúc và xử lý tín hiệu dữ liệu thu thập.
4	Bảo mật	Đảm bảo tính nhất quán, bí mật và độ sẵn sàng của thông tin mạng.
5	Quản lý dữ liệu	Quản lý cơ sở dữ liệu phân tán, đánh chỉ số theo không gian và thời gian.

• Lĩnh vực ứng dụng của WSN: Giám sát và điều khiển công nghiệp (nhiệt độ, áp suất, van xả); tự động hóa gia đình (SmartHome); quân sự (trinh sát, theo dõi mục tiêu); y tế (giám sát bệnh nhân, quản lý dược phẩm); nông nghiệp và môi trường (phát hiện cháy rừng, cảnh báo lũ lụt, đo lường vi khí hậu).
• Khái quát giao thức AODV: AODV là giao thức phản ứng, chỉ thiết lập đường truyền khi nút nguồn có nhu cầu gửi dữ liệu. Đường đi được thiết lập thông qua hai cơ chế chính: Tạo thông tin định tuyến (phát broadcast bản tin RREQ, nhận unicast bản tin RREP) và Duy trì thông tin định tuyến (theo dõi liên kết qua bản tin HELLO hoặc phản hồi lớp liên kết, thông báo sự cố bằng bản tin RERR). Bảng định tuyến quản lý theo cấu trúc: <Địa chỉ nút đích, Địa chỉ bước tiếp theo, Số thứ tự, Khoảng cách (Hop count), Danh sách nút trước đó (Precursor list), Ngày hết hạn (Lifetime)>.

Chương 2: Cơ sở nghiên cứu về giao thức AODV

Chương 2 đi sâu vào cấu trúc thuật toán, cơ chế số học và giải pháp cải tiến giao thức AODV:

• Phân tích thuật toán định tuyến cơ sở:
  • Thuật toán Vectơ khoảng cách (Distance Vector): Dựa trên giải thuật Bellman-Ford để tìm đường đi ngắn nhất. Ưu điểm là tiêu tốn ít tài nguyên bộ nhớ nhưng nhược điểm là tốc độ hội tụ chậm và dễ gặp hiện tượng "đếm đến vô cùng" (Count-to-infinity).
  • Thuật toán Trạng thái liên kết (Link State): Dựa trên giải thuật Dijkstra với các gói tin LSA (Link State Advertisement) để xây dựng cơ sở dữ liệu LSDB (Link State Database). Tuy tính toán chính xác nhưng đòi hỏi bộ nhớ lớn và chiếm dụng băng thông khi khởi động.
• Cơ chế hoạt động chi tiết của AODV:
  • Quản lý số thứ tự (Sequence Number): Sử dụng số nguyên không dấu 32-bit (giá trị tối đa 4.294.967.295) với cơ chế rollover số học 32-bit có dấu nhằm phân biệt thông tin định tuyến cũ và mới. Nút luôn ưu tiên tuyến có Sequence Number lớn hơn hoặc có Hop count nhỏ hơn nếu Sequence Number bằng nhau.
  • Khởi tạo và phân phát RREQ: Nút nguồn phát RREQ với cơ chế mở rộng vòng tìm kiếm (Expanding Ring Search) tăng dần trường TTL để tránh tràn lụt mạng (flooding). Tần suất gửi bị giới hạn bởi RREQ_RATELIMIT, thời gian chờ phản hồi RREP tăng theo hàm mũ cơ số 2 ($2 \times NET_TRAVERSAL_TIME$).
  • Duy trì kết nối và Danh sách đen (Blacklist): Khi truyền RREP qua liên kết đơn hướng thất bại, nút sẽ ghi nhận bước chuyển tiếp vào danh sách đen để bỏ qua các gói RREQ sau đó, ngăn chặn việc thiết lập tuyến đường một chiều không khả dụng.
• Đề xuất thuật toán AODV cải tiến: Nhằm khắc phục hiện tượng nghẽn mạng do mật độ phân phối lưu lượng không đồng đều tại các nút trung gian, tác giả đưa ra mô hình tích hợp Tác tử di động (Mobile Agent) bao gồm Forward Agent (FA) và Backward Agent (BA):

Cấu trúc gói tin Forward Agent (FA):

• ID (16 bits): Số thứ tự của yêu cầu khám phá lộ trình.
• Src_ID (16 bits): Địa chỉ nút nguồn.
• Dest_ID (8 bits): Địa chỉ nút đích.

Cấu trúc gói tin Backward Agent (BA):

• ID (16 bits): Số thứ tự phản hồi.
• Intermediate_ID (8 bits): Địa chỉ nút trung gian trên lộ trình.
• CP (16 bits / Double): Mức độ tắc nghẽn của nút trung gian.

Mức độ tắc nghẽn $CP$ của nút trung gian được ước lượng theo công thức: $$CP = \frac{RI}{RA}$$

Trong đó:

• $RI$: Tổng số lộ trình đang đi qua nút trung gian đang xét.
• $RA$: Tổng số lộ trình đã được thiết lập trên toàn bộ mạng.

Nút nguồn khi nhận gói phản hồi BA sẽ ưu tiên lựa chọn tuyến đường có giá trị $CP$ nhỏ nhất để phân tải và hạn chế hiện tượng nghẽn cục bộ.

Chương 3: Mô phỏng giao thức AODV trên công cụ NS2

Chương 3 tập trung vào công cụ mô phỏng và quy trình cài đặt hệ thống thực nghiệm:

• Tổng quan về NS-2: Được phát triển bởi Đại học UC Berkeley kết hợp Sun Microsystems (Dự án Daedalus). NS-2 là phần mềm mô phỏng hướng sự kiện rời rạc (Discrete Event Simulator), xây dựng trên kiến trúc hướng đối tượng kết hợp hai ngôn ngữ:
  • C++: Dùng để định nghĩa cấu trúc giao thức, xử lý luồng dữ liệu mức thấp và thực thi các thuật toán đòi hỏi tốc độ xử lý cao.
  • OTcl (Object-oriented Tcl): Dùng làm kịch bản thiết lập mô hình mạng, cấu hình topo, định nghĩa thời gian chuyển động của nút và gắn kết các đối tượng C++.
• Tính năng của NS-2: Hỗ trợ mô phỏng các kỹ thuật quản lý hàng đợi (Drop Tail, RED, CBQ), truyền thông đa hướng (Multicast), mạng không dây mặt đất (Ad-hoc, 802.11, GPRS, WLAN, Bluetooth), vệ tinh, và các giao thức định tuyến di động như DSR, DSDV, AODV.
• Phần mềm trình diễn đồ họa Nam (Network Animator): Cung cấp giao diện trực quan với các nút điều khiển mô phỏng dạng thanh điều khiển đa phương tiện (Play, Stop, Fast Forward, Rewind, Pause), hỗ trợ hiển thị luồng gói tin trên từng liên kết và giao diện kéo thả topo mạng.
• Quy trình triển khai trên Cygwin: Khóa luận trình bày các bước thiết lập môi trường Cygwin trên Windows thông qua bộ cài đặt cục bộ (Install from Local Directory), tạo nền tảng biên dịch và thực thi kịch bản NS-2.

---

Thiết kế và triển khai

Khóa luận triển khai mô hình kỹ thuật phục vụ việc kiểm thử giao thức định tuyến theo kiến trúc phân tầng:

• Môi trường hệ thống: Nền tảng Windows tích hợp môi trường giả lập POSIX Cygwin để cung cấp giao diện dòng lệnh Unix, bộ biên dịch GCC và thư viện thực thi cho NS-2.
• Ngăn xếp công nghệ:
  • Lõi mô phỏng: NS-2 (phiên bản 2.x) hỗ trợ các mô hình lớp vật lý, lớp liên kết MAC IEEE 802.11, và tầng mạng với module định tuyến AODV.
  • Kịch bản điều khiển: Ngôn ngữ OTcl dùng để khởi tạo số lượng nút mạng, định nghĩa không gian di chuyển, thiết lập các luồng dữ liệu (CBR/UDP hoặc FTP/TCP) và đặt lịch trình sự kiện.
  • Công cụ phân tích trực quan: Nam xử lý tệp vết (.nam) xuất ra từ NS-2 để tái hiện chuyển động của nút và quá trình chuyển tiếp các bản tin RREQ, RREP, RERR.
• Quy trình kiểm thử: Biên dịch module AODV, nạp kịch bản mô phỏng Tcl, ghi nhận tệp vết dữ liệu (.tr) và hiển thị trực quan chuyển động gói tin trên công cụ Nam.

---

Kết quả và đóng góp

• Hệ thống hóa toàn diện cơ sở lý thuyết: Trình bày chi tiết kiến trúc WSN, phân tích so sánh bản chất kỹ thuật giữa hai thuật toán định tuyến Distance Vector (Bellman-Ford) và Link State (Dijkstra).
• Làm rõ cơ chế hoạt động của AODV: Hệ thống hóa chi tiết cấu trúc 4 loại bản tin điều khiển chính (RREQ, RREP, RERR, HELLO), cổng dịch vụ (UDP port 654), cơ chế chống lặp vòng bằng số thứ tự đích (DSN), kỹ thuật mở rộng vòng tìm kiếm (Expanding Ring Search) và xử lý danh sách đen (Blacklist).
• Đề xuất giải pháp cải tiến AODV: Xây dựng mô hình định tuyến nhận biết tắc nghẽn thông qua việc nhúng hai tác tử di động FA và BA, thiết lập công thức toán học tính hệ số tắc nghẽn $CP = \frac{RI}{RA}$ giúp nút nguồn chọn lộ trình tối ưu hơn về mặt tải trọng.
• Xây dựng tài liệu hướng dẫn thực nghiệm: Đóng góp quy trình cài đặt môi trường giả lập Cygwin, cấu hình NS-2 và sử dụng công cụ Nam phục vụ công tác nghiên cứu, học tập trong chuyên ngành Công nghệ thông tin.

---

Hạn chế và hướng nghiên cứu tiếp

• Hạn chế:
  • Đề tài tập trung chủ yếu vào phần mô tả lý thuyết giải thuật và hướng dẫn thiết lập công cụ mô phỏng; phần thực nghiệm trong văn bản chủ yếu dừng lại ở các bước cấu hình cài đặt môi trường Cygwin/NS-2 và quan sát trực quan trên Nam.
  • Chưa cung cấp các biểu đồ số liệu đo lường định lượng so sánh chi tiết (như tỷ lệ phân phát gói tin PDR, độ trễ trung bình End-to-End Delay, chi phí truyền thông Routing Overhead) giữa thuật toán AODV cải tiến với AODV chuẩn hoặc các giao thức DSR, DSDV.
• Hướng nghiên cứu tiếp:
  • Triển khai lập trình thực tế thuật toán cải tiến sử dụng Agent FA/BA vào mã nguồn C++ của module AODV trong NS-2.
  • Thiết lập các kịch bản mô phỏng đa dạng với mật độ nút dày đặc, vận tốc di chuyển nút cao để đánh giá hiệu năng định lượng của hệ số $CP$.
  • Thử nghiệm trên các nền tảng thiết bị phần cứng WSN thực tế.

---

Giá trị tham khảo

Khóa luận là tài liệu hữu ích cho:

• Sinh viên chuyên ngành Công nghệ Thông tin, Mạng máy tính và Truyền thông: Dùng làm tài liệu học tập, tham khảo khi thực hiện đồ án môn học hoặc khóa luận tốt nghiệp liên quan đến mạng không dây, mạng Ad-hoc và mạng cảm biến WSN.
• Học viên và nhà nghiên cứu bước đầu tiếp cận NS-2: Phần phân tích kiến trúc kết hợp giữa C++ và OTcl, cũng như các bước cài đặt Cygwin và công cụ Nam là tài liệu hướng dẫn thực hành hữu ích.
• Các đề tài nghiên cứu tối ưu hóa giao thức định tuyến: Cấu trúc gói tin Agent và ý tưởng tính toán hệ số tắc nghẽn $CP$ là cơ sở gợi mở tốt cho các hướng nghiên cứu cải tiến giao thức định tuyến phản ứng.

---

Câu hỏi thường gặp

1. Giao thức AODV ngăn chặn hiện tượng lặp vòng định tuyến (Routing Loop) bằng cách nào?
AODV sử dụng chỉ số số thứ tự đích (Destination Sequence Number - DSN) cho mỗi mục trong bảng định tuyến. DSN do chính nút đích tạo ra và cập nhật mỗi khi có thông tin mới. Khi nhận được nhiều thông tin định tuyến, các nút luôn ưu tiên tuyến có DSN lớn hơn (thông tin mới hơn). Nếu DSN bằng nhau, nút sẽ chọn tuyến có số chặng (Hop count) nhỏ hơn, qua đó triệt tiêu khả năng hình thành vòng lặp.

2. Bản tin RREQ trong AODV được điều khiển phân phát như thế nào để tránh gây nghẽn mạng?
AODV áp dụng thuật toán mở rộng vòng tìm kiếm (Expanding Ring Search). Nút nguồn ban đầu phát RREQ với giá trị TTL nhỏ (ví dụ TTL = 1). Nếu không nhận được RREP sau khoảng thời gian quy định, nút sẽ tăng dần TTL trong các lần gửi tiếp theo. Tần suất phát gói bị khống chế bởi tham số RREQ_RATELIMIT và thời gian chờ tăng theo hàm mũ cơ số 2 ($2 \times NET_TRAVERSAL_TIME$).

3. Công thức tính mức độ tắc nghẽn $CP$ trong giải pháp AODV cải tiến được xác định như thế nào?
Mức độ tắc nghẽn $CP$ của một nút trung gian được tính bằng tỷ lệ $CP = \frac{RI}{RA}$, trong đó $RI$ là tổng số lộ trình đi qua nút trung gian đang xét, còn $RA$ là tổng số lộ trình đã được thiết lập trên toàn bộ mạng. Gói Backward Agent (BA) mang giá trị $CP$ này về nút nguồn để nguồn lựa chọn đường đi có $CP$ thấp nhất.

4. Vì sao công cụ NS-2 lại sử dụng song song hai ngôn ngữ C++ và OTcl?
NS-2 sử dụng C++ cho tầng xử lý giao thức mức thấp, cấu trúc gói tin và giải thuật định tuyến nhằm đảm bảo tốc độ thực thi nhanh và tối ưu hiệu năng tính toán. Trong khi đó, OTcl được sử dụng ở tầng điều khiển kịch bản, giúp người dùng dễ dàng cấu hình topo mạng, số lượng nút, thời gian mô phỏng và thay đổi tham số mà không cần phải biên dịch lại toàn bộ mã nguồn C++.

5. Cơ chế xử lý của AODV khi một liên kết trên đường truyền đang hoạt động bị đứt gãy?
Khi một nút phát hiện liên kết tới chặng kế tiếp bị hỏng (thông qua mất bản tin HELLO hoặc không nhận được tín hiệu ACK/CTS ở lớp liên kết), nó tăng Sequence Number của nút đích lên 1, gán khoảng cách bằng vô cùng ($\infty$), và gửi bản tin báo lỗi RERR tới tất cả các nút lân cận đang hoạt động trong danh sách tiền thân (Precursor list). Các nút này tiếp tục chuyển tiếp RERR về nút nguồn để xóa bỏ tuyến hỏng và tái khởi động quá trình tìm đường nếu cần.

---

Kết luận

Khóa luận tốt nghiệp của tác giả Phạm Thị Phương Thùy đã hoàn thành việc nghiên cứu tổng quan về mạng cảm biến không dây WSN và phân tích sâu cơ chế hoạt động của giao thức định tuyến AODV. Tác giả đã trình bày chi tiết cấu trúc thuật toán định tuyến theo yêu cầu, đề xuất giải pháp cải tiến phân tải giảm tắc nghẽn bằng Tác tử di động và chỉ số $CP$, đồng thời xây dựng tài liệu hướng dẫn cài đặt môi trường mô phỏng NS-2 trên nền Cygwin kết hợp công cụ trực quan Nam. Công trình cung cấp hệ thống tài liệu tham khảo có giá trị học thuật và thực tiễn cho sinh viên, nghiên cứu viên trong lĩnh vực mạng truyền thông không dây.

Trích đoạn nội dung tài liệu

CHƯƠNG I. TỔNG QUAN VỀ MẠNG CẢM BIẾN KHÔNG DÂY WSN VÀ GIAO THỨC AODV 1. Giới thiệu tổng quan về mạng cảm biến không dây Với sự phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng như trong các hoạt động thực tế, trong đó mạng máy tính là một lĩnh vực đem lại hiệu quả thiết thực cho con người. Thông qua mạng máy tính chúng ta có thể chia sẻ thông tin ở bấ t kỳ nơi nào trên ma ̣ng, tìm kiếm thông tin một cách nhanh chóng, chính xác và hiệu quả.

Mặc dù mạng máy tıń h đã xuất hiện từ nhiều thập niên nhưng cho đến những năm gần đây, cùng với sự ra đời các thiết bị di động thì nhu cầu nghiên cứu và phát triển các hệ thống mạng không dây ngày càng trở nên cấp thiết. Nhiều công nghệ, phần cứng, các giao thức, chuẩn giao tiếp mạng lần lượt ra đời và đang được tiếp tục nghiên cứu để nâng cao hiệu năng làm việc [1]. “Mạng cảm biến không dây (Wireless Sensor Network)” bao gồm một tập hợp các thiết bị cảm biến sử dụng các liên kết không dây (vô tuyến, hồng ngoại hoặc quang học) để phối hợp thực hiện nhiệm vụ thu thập thông tin dữ liệu phân tán với quy mô lớn trong bất kỳ điều kiện và ở bất kỳ vùng địa lý nào. Mạng cảm biến không dây có thể liên kết trực tiếp với nút quản lý giám sát trực tiếp hay gián tiếp thông qua một điểm thu phát (Sink) và môi trường mạng công cộng như Internet hay vệ tinh [2].

Các nút cảm biến không dây có thể được triển khai cho các mục đích chuyên dụng như điều khiển giám sát và an ninh; kiểm tra môi trường; tạo ra không gian sống thông minh; khảo sát đánh giá chính xác trong nông nghiệp; trong lĩnh vực y tế;. Lợi thế chủ yếu của chúng là khả năng triển khai hầu như trong bất kì loại hình địa lý nào kể cả các môi trường nguy hiểm không thể sử dụng mạng cảm biến có dây truyền thống [1] [2]. “Mạng cảm biến không dây” là một trong những công nghệ thông tin mới phát triển nhanh chóng nhất, với nhiều ứng dụng trong nhiều lĩnh vực. Mạng cảm biến không dây WSN là mạng liên kết các nút với nhau nhờ sóng radio.

Phạm Thị Phương Thùy-DT13CTT01 3 Khóa luận tốt nghiệp GVHD: Nguyễn Hà Huy Cường Nhưng trong đó, mỗi nút mạng bao gồm đầy đủ các chức năng để cảm nhận, thu thập, xử lý và truyền dữ liệu. Các nút mạng thường là các thiết bị đơn giản, nhỏ gọn, giá thành thấp ,…và có số lượng lớn, được phân bố không có hệ thống trên phạm vi rộng, sử dụng nguồn năng lượng (pin) hạn chế thời gian hoạt động lâu dài [19]. Mô hình mạng cảm biến không dây thông thường 1. Cấu trúc của mạng cảm biến không dây Một mạng cảm biến không dây bao gồm số lượng lớn các nút được triển khai dày đặc bên trong hoặc ở rất gần đối tượng cần thăm dò, thu thập thông tin dữ liệu.

Vị trí các cảm biến không cần định trước vì vậy nó cho phép triển khai ngẫu nhiên trong các vùng không thể tiếp cận hoặc các khu vực nguy hiểm. Khả năng tự tổ chức mạng và cộng tác làm việc của các cảm biến không dây là những đặc trưng rất cơ bản của mạng này. Với số lượng lớn các cảm biến không dây được triển khai gần nhau thì truyền thông đa liên kết được lựa chọn để công Phạm Thị Phương Thùy-DT13CTT01 4 Khóa luận tốt nghiệp GVHD: Nguyễn Hà Huy Cường suất tiêu thụ là nhỏ nhất (so với truyền thông đơn liên kết) và mang lại hiệu quả truyền tín hiệu tốt hơn so với truyền khoảng cách xa [10].