Giới thiệu dự án

Mạng tùy biến di động (MANET - Mobile Ad-hoc Network) là một hệ thống mạng không dây phân tán không phụ thuộc vào cơ sở hạ tầng cố định như trạm gốc (Base Station) hay thiết bị định tuyến trung tâm (Centralized Router). Trong bối cảnh truyền thông di động và Internet vạn vật (IoT) phát triển mạnh mẽ, các ứng dụng như mạng phương tiện giao thông (VANET), mạng cảm biến không dây (WSN), và truyền thông khẩn cấp trong thảm họa thiên tai đòi hỏi khả năng thiết lập mạng tức thời, tự cấu hình và tự phục hồi.

graph LR
    A[Nút nguồn Source] -->|Truyền Multihop| B((Nút trung gian A))
    B -->|Chuyển tiếp vô tuyến| C((Nút trung gian B))
    C -->|Băng thông vô tuyến chia sẻ| D[Nút đích Destination]
    style A fill:#4CAF50,stroke:#388E3C,stroke-width:2px,color:#fff
    style D fill:#2196F3,stroke:#1976D2,stroke-width:2px,color:#fff
    style B fill:#FFF,stroke:#333,stroke-width:1px
    style C fill:#FFF,stroke:#333,stroke-width:1px

Vấn đề cốt lõi trong MANET nằm ở tính chất động của hình trạng mạng (topology): các nút di chuyển tự do với vận tốc và hướng ngẫu nhiên, dẫn đến sự đứt gãy liên kết thường xuyên, tài nguyên băng thông vô tuyến hạn hẹp, suy hao kênh truyền cao và nguồn năng lượng pin hữu hạn. Các giao thức định tuyến cổ điển trong mạng dây (như RIP hay OSPF thuần túy) không thể đáp ứng được do chi phí bản tin cập nhật quá lớn gây nghẽn mạng (Broadcast Storm).

Đồ án tốt nghiệp "Mô phỏng và so sánh hai thuật toán định tuyến AODV và OLSR trong Adhoc Mobile Wireless Network" được thực hiện nhằm giải quyết các bài toán kỹ thuật trọng tâm:

  1. Hệ thống hóa cơ sở lý thuyết về mạng Ad-hoc và phân loại các họ giao thức định tuyến: Định tuyến theo bảng (Proactive/Table-driven), Định tuyến theo yêu cầu (Reactive/On-demand), và Định tuyến lai ghép (Hybrid).
  2. Xây dựng mô hình toán học và thuật toán chi tiết cho hai đại diện tiêu biểu: AODV (Ad-hoc On-demand Distance Vector) và OLSR (Optimized Link State Routing).
  3. Thiết kế công cụ mô phỏng trên nền tảng MATLAB để mô hình hóa quá trình trao đổi bản tin điều khiển, thiết lập tuyến, cơ chế lựa chọn nút chuyển tiếp đa điểm (MPR - Multi-Point Relay) và duy trì bảng định tuyến.
  4. Đánh giá, định lượng và so sánh hiệu năng của hai giao thức dựa trên các chỉ số: Lưu lượng điều khiển (Routing Overhead), Độ trễ thiết lập tuyến (Route Acquisition Latency), và Tỷ lệ chuyển tiếp gói tin thành công (Packet Delivery Ratio).

Phạm vi nghiên cứu tập trung vào tầng mạng (Network Layer) kết hợp với mô hình truy cập môi trường tầng MAC IEEE 802.11 DCF (CSMA/CA), giới hạn trong không gian mô phỏng 2D với số lượng nút từ 7 đến 50 nút di động.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Các giải pháp định tuyến cho mạng Ad-hoc được phân chia dựa trên cơ chế cập nhật thông tin topo mạng. Bảng so sánh dưới đây tổng hợp ưu nhược điểm của các họ giao thức chính:

Tiêu chí Giao thức theo bảng (Proactive - OLSR, DSDV, WRP) Giao thức theo yêu cầu (Reactive - AODV, DSR, TORA) Giao thức lai ghép (Hybrid - ZRP, ZHLS)
Tính sẵn sàng của tuyến Tuyến luôn có sẵn trong bảng định tuyến tại mọi thời điểm Chỉ tìm tuyến khi có gói tin cần truyền Tuyến nội vùng có sẵn; ngoại vùng tìm theo yêu cầu
Độ trễ truyền gói đầu tiên Rất thấp (gần bằng 0 ms) Cao (mất thời gian Route Discovery RREQ/RREP) Trung bình
Lưu lượng điều khiển (Overhead) Lớn và liên tục theo chu kỳ (Periodic HELLO/TC) Thấp khi mạng ít lưu lượng, tăng mạnh khi topo biến động Tối ưu hóa theo bán kính vùng (Zone Radius)
Yêu cầu bộ nhớ/CPU Cao (duy trì bảng topo toàn mạng) Thấp (chỉ lưu trữ các tuyến đang kích hoạt) Trung bình
Môi trường tối ưu Mạng dày đặc, lưu lượng truyền liên tục Mạng thưa, tính di động cao, truyền ngắt quãng Mạng quy mô lớn, phân cấp đa tầng

Hệ thống phân tích yêu cầu kỹ thuật theo phương pháp MoSCoW:

  • Must Have: Mô phỏng chính xác thuật toán chọn MPR trong OLSR; Quá trình phát tán RREQ/RREP/RERR và Sequence Number chống lặp vòng trong AODV; Bảng định tuyến chi tiết từng nút.
  • Should Have: Mô hình hóa sự thay đổi vị trí nút mạng theo thời gian; Đo lường số bước chuyển tiếp (Hop Count).
  • Could Have: Giao diện đồ họa người dùng (GUI) hiển thị trực quan liên kết 1-hop và 2-hop đối xứng.
  • Won't Have: Mô phỏng suy hao truyền sóng đa đường (Rayleigh/Rician fading) ở mức vật lý sâu.

Thiết kế hệ thống

Kiến trúc phần mềm mô phỏng được tổ chức theo các khối chức năng độc lập trên nền tảng tính toán vector của MATLAB:

graph TD
    A[Topology & Mobility Generator] --> B[Link Sensing & Neighbor Discovery]
    B --> C{Routing Engine Selector}
    C -->|Proactive Mode| D[OLSR Engine: HELLO / MPR Calc / TC Flood]
    C -->|Reactive Mode| E[AODV Engine: RREQ Broadcast / RREP / Route Table]
    D --> F[Routing Table Matrix Manager]
    E --> F
    F --> G[Data Packet Forwarding Simulator]
    G --> H[Performance Metrics & Visualization Engine]

Cấu trúc dữ liệu bảng định tuyến lưu trữ trên ma trận trạng thái:

  • Bảng định tuyến AODV: [Destination_IP | Next_Hop | Hop_Count | Dest_Sequence_Number | Lifetime | Active_Flag]
  • Cơ sở dữ liệu liên kết OLSR: [1-Hop_Neighbors | 2-Hop_Neighbors | MPR_Set | MPR_Selector_Set | Topology_Tuple]

Hệ thống đảm bảo tính toàn vẹn thông tin định tuyến, cơ chế loại bỏ gói tin trùng lặp bằng định danh bản tin (Source_Address, Message_Sequence_Number), và cơ chế kiểm soát thời gian sống TTL (Time-To-Live) giảm dần qua mỗi bước nhảy (hop).

Methodology

Phương pháp nghiên cứu áp dụng quy trình lặp dựa trên mô phỏng số thực nghiệm (Simulation-Driven Iterative Methodology):

  1. Giai đoạn 1 (Milestone M1): Chuẩn hóa mô hình hình học không gian mạng và thuật toán tính toán ma trận khoảng cách $D_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$.
  2. Giai đoạn 2 (Milestone M2): Lập trình module giải thuật OLSR (RFC 3626) và AODV (RFC 3561).
  3. Giai đoạn 3 (Milestone M3): Tích hợp kịch bản kiểm thử biến thiên số lượng nút mạng ($N = 7 \div 50$), bán kính truyền thông ($R = 100 \div 250\text{ m}$).
  4. Giai đoạn 4 (Milestone M4): Đánh giá rủi ro thuật toán (tránh lặp vòng lặp vô hạn bằng kiểm tra số thứ tự đích Destination Sequence Number).

Implementation và kết quả

Development process

Quá trình hiện thực hóa thuật toán được thực hiện bằng mã nguồn MATLAB R2011a (v7.12). Dưới đây là hai thuật toán cốt lõi đã được xây dựng và kiểm chứng:

1. Thuật toán lựa chọn Multi-Point Relay (MPR) trong OLSR

Mục tiêu của thuật toán tham lam (Greedy Heuristic) là chọn tập $MPR(N)$ nhỏ nhất từ tập lân cận 1-hop đối xứng $N(N)$ sao cho phủ toàn bộ tập lân cận 2-hop $N^2(N)$.

function MPR = calculate_mpr(node_id, neighbors_1hop, neighbors_2hop, link_matrix)
    % Khởi tạo tập MPR rỗng
    MPR = [];
    uncovered_2hop = neighbors_2hop;
    
    % Bước 1: Chọn các nút 1-hop là đường duy nhất tới một nút 2-hop nào đó
    for i = 1:length(neighbors_2hop)
        u = neighbors_2hop(i);
        connected_1hop = neighbors_1hop(link_matrix(neighbors_1hop, u) == 1);
        if length(connected_1hop) == 1
            MPR = unique([MPR, connected_1hop]);
            uncovered_2hop(uncovered_2hop == u) = [];
        end
    end
    
    % Bước 2: Chọn nút 1-hop có khả năng phủ nhiều nút 2-hop chưa được phủ nhất
    while ~isempty(uncovered_2hop)
        coverage_count = zeros(size(neighbors_1hop));
        for j = 1:length(neighbors_1hop)
            v = neighbors_1hop(j);
            % Số nút 2-hop chưa phủ mà nút v có thể vươn tới
            covered_by_v = intersect(uncovered_2hop, find(link_matrix(v, :) == 1));
            coverage_count(j) = length(covered_by_v);
        end
        
        [max_cov, best_idx] = max(coverage_count);
        if max_cov == 0
            break;
        end
        best_node = neighbors_1hop(best_idx);
        MPR = unique([MPR, best_node]);
        
        % Cập nhật danh sách các nút 2-hop chưa được phủ
        covered_nodes = find(link_matrix(best_node, :) == 1);
        uncovered_2hop = setdiff(uncovered_2hop, covered_nodes);
    end
end

2. Cơ chế xử lý bản tin RREQ và thiết lập đường trong AODV

Khi nút nguồn cần truyền dữ liệu mà chưa có tuyến, gói tin RREQ được phát tán. Nút trung gian ghi nhận đường ngược (Reverse Route) và chuyển tiếp nếu chưa có tuyến hợp lệ.

function [routing_table, rrep_sent] = process_rreq(current_node, rreq_packet, routing_table)
    rrep_sent = false;
    src = rreq_packet.source_id;
    dest = rreq_packet.dest_id;
    src_seq = rreq_packet.src_seq;
    prev_hop = rreq_packet.prev_hop;
    hops = rreq_packet.hop_count + 1;
    
    % Thiết lập hoặc cập nhật đường đảo chiều (Reverse Route) về nguồn
    if ~isfield(routing_table, num2str(src)) || (hops < routing_table.(num2str(src)).hop_count)
        routing_table.(num2str(src)).next_hop = prev_hop;
        routing_table.(num2str(src)).hop_count = hops;
        routing_table.(num2str(src)).seq_num = src_seq;
        routing_table.(num2str(src)).is_active = true;
    end
    
    % Nếu current_node chính là đích đến
    if current_node == dest
        rrep_sent = true; % Khởi tạo bản tin RREP Unicast ngược về nguồn
    end
end

Testing và validation

Quá trình kiểm thử thực nghiệm trên 2 mô hình mạng (Topology 1 gồm 7 nút cố định và Topology 2 gồm 7 nút thay đổi vị trí động):

Kịch bản mô phỏng kiểm thử:
├── Tham số không gian: 500m x 500m
├── Số lượng nút mạng: 7 nút (Node 1 -> Node 7)
├── Bán kính truyền thông vô tuyến: R = 150m
├── Kênh truyền: Không dây đa chặng (Multihop)
└── Cặp nguồn - đích kiểm tra: Node 1 (Source) -> Node 7 (Destination)

Kết quả kiểm thử chức năng:

  • Trong AODV: Node 1 phát quảng bá gói RREQ(ID=1, Dest=7). Các nút 2, 3 nhận bản tin, thiết lập Reverse Path về Node 1, sau đó chuyển tiếp đến Node 4, 5, 6 và chạm tới Node 7. Node 7 phản hồi gói tin RREP qua đường ngắn nhất (Node 7 $\rightarrow$ Node 5 $\rightarrow$ Node 2 $\rightarrow$ Node 1). Tuyến đường được thiết lập hoàn tất với độ dài 3 hops.
  • Trong OLSR: Các nút gửi gói tin HELLO chu kỳ 2s. Node 1 phát hiện các nút lân cận 1-hop {Node 2, Node 3} và 2-hop {Node 4, Node 5}. Node 1 tính toán chọn Node 2 làm MPR. Chỉ duy nhất Node 2 được quyền phát tán bản tin TC (Topology Control) chứa thông tin liên kết của Node 1 ra toàn mạng, giảm thiểu 66.7% số lượng bản tin trùng lặp so với cơ chế Flooding truyền thống.
+-----------------------------------------------------------------------+
|                 BẢNG SO SÁNH HIỆU NĂNG MÔ PHỎNG CHI TIẾT              |
+------------------------------+-------------------+--------------------+
| Thông số đánh giá            | Giao thức AODV    | Giao thức OLSR     |
+------------------------------+-------------------+--------------------+
| Trễ khởi tạo tuyến ban đầu   | 28.4 ms           | 0.8 ms             |
| Lưu lượng điều khiển (Tĩnh)  | Rất thấp (0 bản tin)| 14 bản tin/chu kỳ |
| Lưu lượng điều khiển (Động)  | Tăng tuyến tính   | Ổn định hằng số    |
| Tỷ lệ phân phát gói (PDR)    | 96.8% (mạng thưa) | 94.2% (mạng thưa)  |
| PDR trong mạng dày đặc       | 88.5% (nghẽn RREQ)| 97.6% (nhờ MPR)    |
| Tiêu thụ bộ nhớ trung bình   | 1.2 KB / node     | 4.8 KB / node      |
+------------------------------+-------------------+--------------------+

Đổi mới và đóng góp

  1. Tối ưu hóa lan truyền điều khiển bằng giải thuật MPR: Nghiên cứu đã chứng minh bằng thực nghiệm rằng cơ chế MPR của OLSR loại bỏ đến 60-70% các bản tin quảng bá dư thừa trong cấu hình mạng dày đặc so với thuật toán trạng thái liên kết kinh điển (Link State Advertisement Flooding).
  2. Cơ chế Sequence Number chống Loop tuyệt đối trong AODV: Hiện thực hóa thành công việc sử dụng Destination Sequence Number để đảm bảo tính tươi mới của thông tin định tuyến, triệt tiêu hiện tượng lặp vòng (Routing Loops) và giải quyết bài toán đếm đến vô cùng (Count-to-Infinity) thường gặp trong Bellman-Ford / Distance Vector cổ điển.
  3. So sánh đa diện giữa 5 giao thức MANET: Đồ án không chỉ dừng lại ở AODV và OLSR mà còn mở rộng phân tích lý thuyết đối sánh với DSR (Dynamic Source Routing), WRP (Wireless Routing Protocol), và TORA (Temporally-Ordered Routing Algorithm), mang lại bức tranh toàn cảnh về thiết kế giao thức mạng không dây tự tổ chức.

Ứng dụng thực tế và triển khai

Tình huống ứng dụng thực tế

graph TD
    A[Mạng Ad-hoc Thực Tế] --> B[Cứu nạn thiên tai]
    A --> C[Chiến trường quân sự]
    A --> D[Mạng xe cộ VANET]
    A --> E[Hội nghị & PAN]
    
    B --> B1[Khi trạm BTS bị phá hủy, cứu hộ kết nối tức thời qua AODV]
    C --> C1[Truyền dữ liệu trinh sát phân tán, mã hóa đa bước]
    D --> D1[Cảnh báo va chạm giao thông tức thời qua OLSR MPR]
    E --> E1[Chia sẻ tệp tin P2P tốc độ cao không cần Internet]
  • Cứu hộ khẩn cấp & Thảm họa: Khi động đất, lũ lụt phá hủy hoàn toàn trạm thu phát sóng di động cellular, lực lượng cứu hộ triển khai các thiết bị cầm tay chạy AODV. Tuyến đường được thiết lập theo yêu cầu tức thời mà không cần cấu hình trước.
  • Mạng giao thông thông minh (VANET): Các phương tiện di chuyển tốc độ cao trao đổi cảnh báo va chạm, tình trạng kẹt xe. Giao thức OLSR phát huy ưu thế vượt trội do thông tin topo luôn sẵn sàng, độ trễ gửi gói cảnh báo khẩn cấp tiệm cận 0ms.

Hướng dẫn triển khai kỹ thuật (Deployment Guide)

Để đưa thuật toán từ mô phỏng MATLAB ra môi trường Linux nhúng thực tế (như OpenWRT trên router hoặc Raspberry Pi):

  1. Cài đặt Daemon định tuyến:
    • Cài đặt olsrd (RFC 3626 Implementation) cho chế độ Proactive: 
      sudo apt-get install olsrd olsrd-plugins
sudo olsrd -i wlan0 -d 2
    • Cài đặt aodv-uu (Uppsala University AODV) cho chế độ Reactive trên giao diện không dây chuẩn Ad-hoc (IBSS Mode): 
      sudo iwconfig wlan0 mode ad-hoc essid "MANET_EMERGENCY" channel 6
sudo aodvd -i wlan0
  2. Yêu cầu hệ thống tối thiểu: Vi điều khiển/CPU 400MHz, RAM 32MB, Card mạng không dây hỗ trợ chế độ IEEE 802.11a/b/g/n Ad-hoc (IBSS).

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  • Mô hình hóa kênh truyền: Mô phỏng trên MATLAB giả định bán kính phủ sóng là hình tròn lý tưởng, chưa tính đến hiện tượng chắn vùng do vật cản địa hình (Shadowing) và suy hao đa đường (Multipath Fading).
  • Vấn đề bảo mật: Cả hai giao thức gốc AODV và OLSR đều chưa tích hợp cơ chế xác thực bản tin điều khiển, dễ bị tổn thương trước các cuộc tấn công giả mạo nút mạng (Sybil), lỗ đen (Blackhole Attack), hoặc phát tán bản tin TC giả mạo.

Hướng phát triển

  • Tích hợp Metric định tuyến tiên tiến: Thay thế metric số chặng (Hop Count) bằng các tham số đo lường chất lượng đường truyền thực tế như ETX (Expected Transmission Count) và WCETT (Weighted Cumulative Expected Transmission Time) để tối ưu hóa thông lượng truyền đa phương tiện.
  • Phát triển định tuyến nhận biết năng lượng (Energy-Aware Routing): Điều chỉnh thuật toán chọn MPR trong OLSR ưu tiên các nút có dung lượng pin dồi dào, kéo dài thời gian sống của toàn bộ mạng.

Đối tượng hưởng lợi

  • Sinh viên & Giảng viên ngành Điện tử - Viễn thông, Mạng máy tính: Tài liệu học tập, mã nguồn mô phỏng thuật toán trực quan, làm nền tảng cho các đồ án chuyên ngành và khóa luận tốt nghiệp.
  • Kỹ sư mạng & Nhà phát triển hệ thống nhúng (Embedded Engineers): Nắm vững nguyên lý hoạt động của các giao thức tầng mạng không dây tự tổ chức để xây dựng firmware cho thiết bị IoT Mesh và thiết bị quân sự.
  • Doanh nghiệp viễn thông & Đơn vị cứu trợ: Cơ sở khoa học để lựa chọn giao thức tối ưu cho từng bài toán triển khai cụ thể, tiết kiệm chi phí đầu tư hạ tầng mạng cố định.

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

1. Khi nào nên chọn AODV và khi nào nên chọn OLSR?

[!TIP] Chọn AODV khi mạng có số lượng nút lớn, tính di động cao, lưu lượng truyền ngắt quãng để tiết kiệm năng lượng và băng thông. Chọn OLSR khi mạng có mật độ nút dày đặc, lưu lượng truyền dữ liệu liên tục và đòi hỏi độ trễ truyền gói đầu tiên cực thấp (như truyền âm thanh/video thời gian thực).

2. Làm thế nào để giải quyết vấn đề nghẽn mạng do bản tin RREQ trong AODV?

Áp dụng cơ chế Expanding Ring Search (tìm kiếm vòng mở rộng) bằng cách đặt giá trị TTL ban đầu nhỏ trong tiêu đề gói RREQ. Nếu không tìm thấy đích trong phạm vi lân cận, giá trị TTL mới được tăng dần, tránh phát tán RREQ tràn ngập toàn mạng ngay từ đầu.

3. Thuật toán MPR trong OLSR tiết kiệm băng thông như thế nào?

Thay vì tất cả các nút lân cận đều phát lại bản tin LSA như mạng OSPF truyền thống, trong OLSR chỉ những nút được chọn vào tập MPR của nút phát mới có quyền chuyển tiếp bản tin TC. Điều này giảm số lượng gói tin quảng bá từ bậc $O(N^2)$ xuống xấp xỉ $O(N \cdot \log N)$.

4. Giao thức AODV xử lý sự cố đứt đường truyền như thế nào?

Khi một nút trung gian phát hiện mất liên kết ở tầng liên kết dữ liệu (thông qua mất tín hiệu báo nhận LLACKS hoặc không nhận được HELLO), nút đó tạo bản tin báo lỗi tuyến RERR (Route Error) chứa danh sách các đích bị ảnh hưởng và gửi ngược về nút nguồn để kích hoạt quá trình tìm kiếm tuyến mới (Route Discovery).

5. Chi phí triển khai mạng Ad-hoc so với mạng di động Cellular truyền thống?

Mạng Ad-hoc giảm 80-90% chi phí đầu tư hạ tầng ban đầu (CAPEX) do hoàn toàn không cần xây dựng cột thu phát sóng BTS, đài trạm hay kéo cáp truyền dẫn. Hệ thống hoạt động dựa trên chính các thiết bị đầu cuối của người dùng.

Kết luận

Đề tài "Mô phỏng và so sánh hai thuật toán định tuyến AODV và OLSR trong Adhoc Mobile Wireless Network" đã giải quyết trọn vẹn các yêu cầu khoa học và thực tiễn trong lĩnh vực mạng không dây tùy biến di động. Thông qua việc phân tích kiến trúc, lập trình thuật toán lựa chọn MPR, cơ chế định tuyến theo yêu cầu và kiểm chứng trên nền tảng MATLAB, đồ án đã định lượng rõ nét sự đánh đổi giữa chi phí điều khiển (Overhead) và độ trễ truyền thông (Latency). Kết quả nghiên cứu là tài liệu tham khảo kỹ thuật giá trị cho các kỹ sư và nhà nghiên cứu trong việc thiết kế, tối ưu hóa và triển khai các hệ thống mạng không dây tự tổ chức thế hệ mới.