Tổng quan nghiên cứu

Mạng di động ad-hoc (Mobile Ad-hoc Network - MANET) đóng vai trò then chốt trong hạ tầng truyền thông không dây hiện đại, đặc biệt trong các tình huống cứu nạn khẩn cấp khi thảm họa tự nhiên phá hủy hoàn toàn trạm thu phát sóng cố định. Trong cấu trúc MANET, các thiết bị di động tự động kết nối và kiêm nhiệm vai trò router chuyển tiếp dữ liệu mà không phụ thuộc vào hạ tầng quản lý trung tâm. Tuy nhiên, tính di động tự do của các nút mạng với vận tốc dao động từ 1 m/s đến 10 m/s khiến tô-pô mạng thay đổi liên tục, gây ra hiện tượng đứt gãy liên kết thường xuyên và suy giảm hiệu năng truyền tải. Các giao thức định tuyến cổ điển khi tìm tuyến thường sử dụng phương pháp phát tán mù (blind flooding), dẫn đến hiện tượng bão quảng bá (broadcast storm), làm lãng phí hơn 70% băng thông khả dụng và gây nghẽn nghiêm trọng với các gói tin kích thước chuẩn 512 bytes.

Nhằm khắc phục triệt để thách thức này, đề tài luận văn thạc sĩ ngành Công nghệ thông tin, chuyên ngành Truyền dữ liệu và Mạng máy tính tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội đã tiến hành khảo sát và đánh giá thuật toán phát tán dữ liệu có kiểm soát mang tên Flooding With Dominant Pruning (FWDP). Mục tiêu trọng tâm của nghiên cứu là phân tích cơ sở toán học của kỹ thuật cắt tỉa tập chuyển tiếp dựa trên thông tin láng giềng 2-chặng, cài đặt thuật toán trên môi trường mô phỏng và đánh giá định lượng hiệu năng so với giao thức định tuyến chuẩn AODV (Ad-hoc On-Demand Distance Vector). Nghiên cứu được triển khai trong phạm vi không gian từ 1 km² đến 2 km² với 25 nút mạng hoạt động liên tục trong 300 giây mô phỏng. Kết quả đạt được cung cấp cơ sở dữ liệu quan trọng giúp nâng cao tỷ lệ truyền gói tin thành công (Delivery Ratio) và tối ưu hóa tài nguyên mạng không dây trong điều kiện địa hình phức tạp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng lý thuyết mạng phân tán và lý thuyết tối ưu hóa tổ hợp. Trọng tâm của khung lý thuyết bao gồm mô hình mạng di động ad-hoc theo tiêu chuẩn IEEE 802.11 với các đặc tả vật lý như 802.11b (băng thông 11 Mb/s, tần số 2.4 GHz) và 802.11g (băng thông 54 Mb/s). Trong cấu trúc mạng không dây, việc tối ưu hóa quá trình phát tán thông tin được quy về bài toán tìm cây bao trùm nhỏ nhất (Minimum Spanning Tree - MST) với số lượng nút trung gian phát lại ít nhất. Về mặt toán học, đây là bài toán tối ưu hóa thuộc lớp NP-đầy đủ (NP-complete).

Bên cạnh đó, nghiên cứu tích hợp lý thuyết phủ tập hợp tham lam (Greedy Set Cover Approximation) để xây dựng thuật toán FWDP. Khác với các giao thức định tuyến theo bảng ghi như DSDV hay định tuyến theo yêu cầu như DSR và TORA, FWDP tiếp cận bài toán truyền tin dựa trên cơ chế chỉ định từ phía nút gửi (sender-based). Bằng việc khai thác thông tin láng giềng 2-chặng, mỗi nút chuyển tiếp tính toán tập chuyển tiếp tối ưu F nhằm bao phủ toàn bộ tập đỉnh U = N(N(vj)) - N(vi) - N(vj) với tỷ lệ xấp xỉ tiệm cận ln|U| + 1, loại bỏ hoàn toàn các nút nhận dư thừa trong bán kính truyền sóng 250m.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp mô phỏng thực nghiệm trên công cụ Network Simulator 2 (NS-2 phiên bản 2.34) tích hợp module mở rộng tính di động không dây CMU Monarch do Đại học Carnegie Mellon phát triển. Đây là công cụ chuẩn mực trong nghiên cứu mạng máy tính nhờ khả năng mô phỏng chi tiết các tầng từ MAC (IEEE 802.11 với cơ chế phân tán CSMA/CA), tầng liên kết dữ liệu ARP đến tầng mạng và ứng dụng. Lý do lựa chọn NS-2 là khả năng trích xuất dữ liệu vết (trace file) chính xác, hỗ trợ phân tích định lượng các chỉ số hiệu năng mà không tốn kém chi phí phần cứng thử nghiệm.

Cỡ mẫu nghiên cứu bao gồm 25 nút mạng di động phân bố trên diện tích thử nghiệm mở rộng từ 1 km² (1.000.000 m²) đến 2 km² (4.000.000 m²). Phương pháp chọn mẫu kịch bản di chuyển được thực hiện bằng cách tạo ngẫu nhiên 10 kịch bản chuyển động (movement patterns) độc lập dựa trên mô hình Random Waypoint, với vận tốc di chuyển từ 1 m/s đến 10 m/s và thời gian dừng cố định 20 giây. Lưu lượng truyền thông (traffic pattern) được thiết lập dạng dòng bit không đổi (CBR) với tốc độ 4 gói/giây (4 Pkt/s) và kích thước payload 512 bytes trên kênh truyền băng thông 2 Mb/s. Toàn bộ 10 kịch bản được thực thi đồng bộ với thời gian mô phỏng 300 giây mỗi phiên nhằm thu thập số liệu trung bình thống kê tin cậy nhất.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, về tỷ lệ phân phát gói tin thành công (Delivery Ratio), thuật toán FWDP thể hiện sự vượt trội rõ rệt so với giao thức AODV trong môi trường mạng thưa. Khi diện tích mô phỏng mở rộng từ 1 km² lên 2 km² (làm giảm mật độ nút từ 25 nút/km² xuống còn 6.25 nút/km²), tỷ lệ chuyển phát thành công của AODV sụt giảm nhanh chóng do các tuyến đường định tuyến liên tục bị phá vỡ. Ngược lại, FWDP duy trì tỷ lệ Delivery Ratio cao hơn từ 15% đến 25% so với AODV nhờ khả năng phân tán dữ liệu chủ động mà không phụ thuộc vào chu kỳ tìm đường lặp lại.

Thứ hai, về khả năng cắt tỉa nút phát lại, FWDP giảm thiểu được khoảng 40% số lượng gói tin quảng bá dư thừa so với cơ chế flooding mù và tiết kiệm hơn 18% chi phí truyền thông so với phương pháp chỉ dựa trên thông tin 1-chặng (1HI). Việc áp dụng giải thuật tham lam để xác định tập chuyển tiếp F đã loại bỏ triệt để hiện tượng trùng lặp vùng phủ sóng giữa các nút láng giềng.

Thứ ba, về độ ổn định của hệ thống dưới tải mạng liên tục 4 gói/giây, FWDP triệt tiêu hoàn toàn các gói tin điều khiển tìm đường RREQ và trả lời RREP, từ đó hạn chế tối đa nguy cơ xung đột tại tầng MAC IEEE 802.11 trong phạm vi bán kính truyền sóng 250m.

Thảo luận kết quả

Nguyên nhân cốt lõi dẫn đến sự chênh lệch hiệu năng giữa hai phương pháp bắt nguồn từ cơ chế thích ứng với tính di động của nút mạng. Giao thức AODV hoạt động theo cơ chế phản ứng (on-demand), yêu cầu khởi tạo quy trình khám phá tuyến đường bằng gói tin RREQ và chờ đợi phản hồi RREP mỗi khi xảy ra đứt gãy liên kết. Trong mạng có mật độ thưa (diện tích 2 km² với 25 nút) và tốc độ di chuyển lên tới 10 m/s, thời gian trễ của quá trình tìm tuyến tăng cao, làm cạn kiệt hàng đợi giao diện (interface queue) và dẫn đến rớt gói tin hàng loạt.

Trái lại, FWDP giải quyết bài toán này bằng cách biến mỗi gói tin dữ liệu thành một thông điệp tự mang danh sách chuyển tiếp (forward list). Bằng việc phân tích cấu trúc láng giềng 2-chặng, nút truyền chỉ định trực tiếp các nút trung gian tối ưu để tái phát gói tin, bảo đảm dữ liệu vượt qua các vùng đứt gãy truyền thông mà không cần duy trì bảng định tuyến toàn cục. Dữ liệu thực nghiệm của luận văn có thể được biểu diễn trực quan qua biểu đồ đường so sánh tương quan tỷ lệ Delivery Ratio trên trục tung với diện tích vùng phủ (1.0 km², 1.5 km², 2.0 km²) trên trục hoành, kết hợp cùng bảng tổng hợp số liệu trung bình của 10 kịch bản ngẫu nhiên. Kết quả này hoàn toàn nhất quán với các nghiên cứu của dự án CMU Monarch về giới hạn của định tuyến vector khoảng cách trong môi trường vô tuyến biến động cao.

Đề xuất và khuyến nghị

Dựa trên kết quả khảo sát và phân tích thực nghiệm, nghiên cứu đề xuất 4 nhóm giải pháp kỹ thuật cụ thể nhằm tối ưu hóa việc truyền dữ liệu trong mạng di động ad-hoc:

  1. Tích hợp thuật toán FWDP vào các giao thức định tuyến lai (Hybrid Routing): Tiến hành cài đặt giải thuật cắt tỉa vượt trội vào pha khám phá tuyến của AODV hoặc DSR nhằm nâng cao tỷ lệ chuyển phát gói tin lên trên 85% trong các kịch bản mạng thưa thớt. Lộ trình thực hiện dự kiến kéo dài 6 tháng do nhóm nghiên cứu giao thức mạng máy tính chủ trì.
  2. Tối ưu hóa mức tiêu thụ năng lượng cho nút mạng: Thiết kế cơ chế chuyển trạng thái thông minh cho các nút không nằm trong danh sách chuyển tiếp F sang chế độ chờ (stand-by/sleep mode), hướng tới mục tiêu cắt giảm từ 20% đến 30% năng lượng tiêu hao trên thiết bị di động trong thời gian 12 tháng, thực hiện bởi các kỹ sư phần mềm nhúng.
  3. Thử nghiệm trên môi trường thiết bị phần cứng thực tế: Mở rộng nghiên cứu từ môi trường giả lập NS-2 sang hạ tầng mạng thiết bị thực tế (Mesh Router, bo mạch nhúng ARM hoặc thiết bị Wi-Fi ad-hoc) với quy mô từ 20 đến 50 nút vật lý trong phạm vi diện tích 1 km², dự kiến hoàn thành trong vòng 18 tháng dưới sự phối hợp giữa viện nghiên cứu và các doanh nghiệp viễn thông.
  4. Xây dựng cơ chế kiểm soát tắc nghẽn và an toàn thông tin: Thiết lập các thuật toán xác thực phân tán và giới hạn tốc độ truyền dữ liệu dưới ngưỡng băng thông 2 Mb/s nhằm giảm tỷ lệ nghẽn kênh truyền xuống dưới 3%, thực hiện trong vòng 9 tháng bởi các chuyên gia an toàn thông tin.

Đối tượng nên tham khảo luận văn

Luận văn thạc sĩ này là nguồn tài liệu học thuật và kỹ thuật giá trị dành cho các nhóm đối tượng chuyên môn sau:

  1. Học viên cao học và nghiên cứu sinh chuyên ngành Mạng máy tính và Viễn thông: Luận văn cung cấp phương pháp luận chặt chẽ trong việc mô hình hóa tô-pô mạng, giải thuật tổ hợp và kỹ năng lập trình mô phỏng trên nền tảng NS-2 với hơn 10 kịch bản di chuyển thực tế.
  2. Kỹ sư phát triển phần mềm nhúng và hệ thống IoT không dây: Tài liệu mang đến giải pháp cụ thể về quản lý bộ nhớ đệm, tối ưu hóa gói tin chuyển tiếp có kích thước 512 bytes và giảm thiểu chi phí tính toán CPU trên các vi điều khiển có tài nguyên hạn chế.
  3. Chuyên gia thiết kế hệ thống thông tin cứu hộ cứu nạn và quân sự: Cung cấp mô hình mạng ad-hoc tự định hình với bán kính phủ sóng 250m mỗi chặng, giúp triển khai hạ tầng liên lạc khẩn cấp tức thì tại các vùng thiên tai bị cô lập hoàn toàn mạng di động tế bào.
  4. Giảng viên và cán bộ nghiên cứu tại các cơ sở đào tạo kỹ thuật: Có thể sử dụng toàn bộ mã nguồn mô phỏng kịch bản OTcl và C++ trong phụ lục luận văn làm tài liệu giảng dạy thực hành môn Mạng máy tính nâng cao và Truyền thông không dây.

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

  1. Thuật toán FWDP giải quyết vấn đề bão quảng bá (broadcast storm) như thế nào? FWDP giải quyết triệt để vấn đề này bằng cách tận dụng thông tin hàng xóm 2-chặng để chọn lọc một tập chuyển tiếp tối thiểu F thông qua giải thuật tham lam. Thay vì tất cả 25 nút đều phát lại gói tin gây lãng phí 70% băng thông như flooding mù, chỉ những nút được chỉ định mới thực hiện phát lại, bao phủ toàn bộ vùng U = N(N(vj)) - N(vi) - N(vj) hiệu quả.

  2. Tại sao FWDP lại đạt tỷ lệ truyền gói cao hơn AODV trong môi trường mạng thưa? Trong mạng thưa có diện tích 2 km², khoảng cách giữa các nút xa nhau và liên kết vô tuyến dễ bị đứt khi nút di chuyển 1 - 10 m/s. AODV mất nhiều thời gian phát lại gói RREQ để tìm đường dẫn đến rớt gói, trong khi FWDP phát tán gói tin qua nhiều nhánh trung gian chủ động, giúp tăng tỷ lệ phân phát thành công thêm 15% đến 25%.

  3. Bộ mô phỏng NS-2 phiên bản 2.34 có ưu điểm gì trong nghiên cứu này? NS-2 phiên bản 2.34 kết hợp module CMU Monarch cho phép mô phỏng chính xác tầng vật lý và tầng MAC theo chuẩn IEEE 802.11. Công cụ này xử lý các tệp vết trace file chi tiết trong 300 giây mô phỏng, giúp đánh giá định lượng chính xác Delivery Ratio qua 10 kịch bản ngẫu nhiên mà không tốn chi phí thực nghiệm phần cứng.

  4. Độ phức tạp tính toán của thuật toán FWDP là bao nhiêu? FWDP sử dụng giải thuật xấp xỉ Greedy Set Cover với tỷ lệ xấp xỉ ln|U| + 1, trong đó U là tập các nút láng giềng 2-chặng chưa được phủ sóng. Độ phức tạp tính toán dừng lại ở mức đa thức, hoàn toàn phù hợp với năng lực xử lý CPU của các thiết bị di động nhỏ gọn trong bán kính truyền dẫn 250m.

  5. Mạng MANET trong nghiên cứu có thể ứng dụng trong điều kiện thực tế nào? Mạng MANET phát huy hiệu quả cao nhất trong các hoạt động cứu hộ bão lũ, hỏa hoạn khi trạm viễn thông bị phá hủy, hoặc các hội nghị tạm thời và liên lạc quân sự tại vùng sâu vùng xa. Hệ thống có khả năng kết nối 25 đến 50 thiết bị độc lập mà không cần bất kỳ dây dẫn hay trạm cơ sở cố định nào.

Kết luận

Nghiên cứu về thuật toán Flooding With Dominant Pruning (FWDP) trong mạng di động ad-hoc đã giải quyết hiệu quả bài toán cân bằng giữa độ tin cậy truyền dữ liệu và mức độ tiêu hao tài nguyên mạng. Năm đóng góp chính của luận văn bao gồm:

  • Hệ thống hóa toàn diện cơ sở lý thuyết về mạng MANET, chuẩn IEEE 802.11 và phân loại chi tiết các giao thức định tuyến DSDV, AODV, DSR, TORA.
  • Phân tích toán học sâu sắc về bài toán cây phát tán tối ưu MST và cơ chế cắt tỉa láng giềng 2-chặng theo thuật toán tham lam.
  • Cài đặt thành công thuật toán FWDP trên nền tảng mô phỏng mạng tiêu chuẩn NS-2 phiên bản 2.34.
  • Chứng minh định lượng tính ưu việt của FWDP với tỷ lệ chuyển phát gói tin cao hơn AODV từ 15% đến 25% trong môi trường mạng thưa 25 nút trên diện tích 2 km².
  • Xây dựng bộ mã nguồn kịch bản mô phỏng hoàn chỉnh làm tiền đề phát triển các giao thức định tuyến không dây thế hệ mới.

Trong giai đoạn tiếp theo từ 6 đến 12 tháng tới, các nhóm nghiên cứu nên tiếp tục hoàn thiện giải pháp tiết kiệm năng lượng và tiến hành thử nghiệm trên phần cứng thực nghiệm để đưa công nghệ này vào ứng dụng cứu hộ khẩn cấp thực tế.