Luận văn thạc sĩ thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad hoc di động

Luận văn thạc sĩ toán học phân tích thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad, đánh giá thực trạng, chỉ ra hạn chế, đề xuất

• Tác giả: Lê Hồng Sơn
• Người hướng dẫn: TS. Đỗ Đình Cường
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Thuật Toán Tối Ưu Chi Phí Định Tuyến Trong Mạng Ad Hoc Di Động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ MẠNG AD HOC VÀ ỨNG DỤNG
• 1.1. Tổng quan về mạng ad hoc
• 1.1.1. Định nghĩa và đặc trưng của mạng ad hoc
• 1.1.2. Đặc điểm của mạng ad hoc
• 1.1.3. Ứng dụng của mạng ad hoc
• 1.2. Giao thức định tuyến AODV trong mạng ad hoc
• 1.2.1. Đặc điểm chung của giao thức định tuyến AODV
• 1.2.2. Cơ chế hoạt động của giao thức AODV
• 1.3. Một số phương pháp cải tiến cơ chế quảng bá thông tin định tuyến
• 1.3.1. Vấn đề bão quảng bá của giao thức AODV
• 1.3.2. Phương pháp sử dụng các bộ đếm thời gian
• 1.3.3. Phương pháp khám phá đường theo xác suất
• 1.3.4. Phương pháp định tuyến đa đường
• 1.3.5. Phương pháp lập lịch
• 1.3.6. Phương pháp quảng bá lại dựa trên thông tin từ các nút lân cận
• 1.4. Tổng kết Chương 1
• 2. CHƯƠNG 2: NGHIÊN CỨU THUẬT TOÁN CẢI TIẾN QUẢNG BÁ ĐỊNH TUYẾN DỰA TRÊN THÔNG TIN TỪ CÁC NÚT LÂN CẬN
• 2.1. Ý tưởng của phương pháp
• 2.2. Giao thức NKR
• 2.2.1. Tính trễ quảng bá
• 2.2.2. Tính xác suất quảng bá
• 2.2.3. Triển khai phân cụm ảo LVC
• 2.2.4. Chu kỳ hiệu lực của liên kết LEP
• 2.2.5. Thuật toán quảng bá lại dựa trên thông tin nút lân cận
• 2.3. Tổng kết Chương 2
• 3. CHƯƠNG 3: MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU QUẢ
• 3.1. Các tham số mô phỏng và độ đo đánh giá hiệu năng
• 3.1.1. Các tham số mô phỏng
• 3.1.2. Các độ đo đánh giá hiệu năng
• 3.2. Đánh giá về tỉ lệ quảng bá
• 3.2.1. Tỉ lệ quảng bá theo lưu lượng mạng
• 3.2.2. Tỉ lệ quảng bá theo số nút mạng
• 3.2.3. Tỉ lệ quảng bá theo vận tốc di chuyển
• 3.2.4. Tỉ lệ quảng bá theo băng thông yêu cầu
• 3.3. Đánh giá về chi phí định tuyến
• 3.3.1. Chi phí định tuyến theo số nút mạng
• 3.3.2. Chi phí định tuyến theo vận tốc di chuyển
• 3.4. Đánh giá về tỉ lệ tái liên kết
• 3.5. Tổng kết Chương 3
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về thuật toán tối ưu chi phí định tuyến trong mạng ad hoc di động

Mạng ad hoc di động là một cấu trúc mạng không dây tự tổ chức, cho phép các nút di động kết nối và giao tiếp mà không cần cơ sở hạ tầng cố định. Thuật toán tối ưu chi phí định tuyến trong mạng này đóng vai trò quan trọng trong việc cải thiện hiệu suất truyền thông. Việc tối ưu hóa chi phí định tuyến không chỉ giúp giảm thiểu tài nguyên sử dụng mà còn nâng cao chất lượng dịch vụ cho người dùng. Các nghiên cứu gần đây đã chỉ ra rằng việc áp dụng các thuật toán tối ưu có thể cải thiện đáng kể hiệu suất mạng.

1.1. Định nghĩa và đặc trưng của mạng ad hoc di động

Mạng ad hoc di động là một tập hợp các nút không dây có khả năng tự tổ chức và giao tiếp với nhau mà không cần sự hỗ trợ của cơ sở hạ tầng. Đặc trưng của mạng này bao gồm tính động, khả năng tự cấu hình và khả năng thích ứng với sự thay đổi của môi trường.

1.2. Vai trò của thuật toán tối ưu trong mạng ad hoc

Thuật toán tối ưu chi phí định tuyến giúp cải thiện hiệu suất mạng bằng cách giảm thiểu chi phí truyền thông và tăng cường khả năng phục hồi của mạng. Điều này đặc biệt quan trọng trong các tình huống khẩn cấp hoặc khi cơ sở hạ tầng bị hỏng.

II. Vấn đề và thách thức trong tối ưu chi phí định tuyến

Mặc dù có nhiều lợi ích, việc tối ưu chi phí định tuyến trong mạng ad hoc di động cũng gặp phải nhiều thách thức. Các vấn đề như độ tin cậy của liên kết, bão quảng bá và sự thay đổi liên tục của cấu trúc mạng là những yếu tố cần được xem xét. Những thách thức này có thể dẫn đến việc tăng chi phí định tuyến và giảm hiệu suất mạng.

2.1. Độ tin cậy của liên kết trong mạng ad hoc

Độ tin cậy của liên kết là một yếu tố quan trọng trong mạng ad hoc. Các liên kết có thể bị đứt do sự di chuyển của các nút, dẫn đến việc tăng chi phí định tuyến và giảm hiệu suất truyền thông.

2.2. Vấn đề bão quảng bá trong giao thức AODV

Bão quảng bá là một vấn đề phổ biến trong giao thức AODV, khi nhiều thông điệp quảng bá được gửi đồng thời, gây tắc nghẽn mạng. Điều này làm tăng chi phí định tuyến và giảm hiệu suất tổng thể của mạng.

III. Phương pháp tối ưu hóa chi phí định tuyến hiệu quả

Để giải quyết các vấn đề trên, nhiều phương pháp tối ưu hóa chi phí định tuyến đã được đề xuất. Các phương pháp này bao gồm việc sử dụng các bộ đếm thời gian, khám phá đường theo xác suất và định tuyến đa đường. Những phương pháp này không chỉ giúp giảm chi phí mà còn cải thiện hiệu suất mạng.

3.1. Sử dụng bộ đếm thời gian để tối ưu hóa

Phương pháp sử dụng bộ đếm thời gian giúp giảm thiểu số lượng thông điệp quảng bá cần thiết, từ đó giảm chi phí định tuyến. Bằng cách điều chỉnh thời gian gửi thông điệp, mạng có thể hoạt động hiệu quả hơn.

3.2. Khám phá đường theo xác suất

Khám phá đường theo xác suất cho phép các nút trong mạng lựa chọn đường đi tối ưu dựa trên xác suất thành công. Phương pháp này giúp cải thiện khả năng phục hồi của mạng và giảm thiểu chi phí định tuyến.

IV. Ứng dụng thực tiễn của thuật toán tối ưu chi phí định tuyến

Các thuật toán tối ưu chi phí định tuyến đã được áp dụng trong nhiều lĩnh vực khác nhau, từ quân sự đến cứu hộ thiên tai. Việc tối ưu hóa chi phí định tuyến không chỉ giúp cải thiện hiệu suất mạng mà còn đảm bảo thông tin được truyền tải một cách hiệu quả trong các tình huống khẩn cấp.

4.1. Ứng dụng trong quân đội

Trong quân đội, mạng ad hoc di động cho phép các đơn vị giao tiếp hiệu quả mà không cần cơ sở hạ tầng cố định. Việc tối ưu hóa chi phí định tuyến giúp cải thiện khả năng truyền thông trong các chiến dịch.

4.2. Ứng dụng trong cứu hộ thiên tai

Trong các tình huống thiên tai, mạng ad hoc di động có thể được triển khai nhanh chóng để hỗ trợ cứu hộ. Tối ưu hóa chi phí định tuyến giúp đảm bảo thông tin được truyền tải một cách nhanh chóng và hiệu quả.

V. Kết luận và tương lai của thuật toán tối ưu chi phí định tuyến

Việc tối ưu chi phí định tuyến trong mạng ad hoc di động là một lĩnh vực nghiên cứu quan trọng và đầy tiềm năng. Các nghiên cứu hiện tại đã chỉ ra rằng việc áp dụng các thuật toán tối ưu có thể cải thiện đáng kể hiệu suất mạng. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều phát triển mới, đặc biệt là trong bối cảnh công nghệ không ngừng tiến bộ.

5.1. Hướng phát triển trong nghiên cứu

Nghiên cứu trong lĩnh vực tối ưu chi phí định tuyến sẽ tiếp tục phát triển, với nhiều phương pháp mới được đề xuất. Các nghiên cứu này sẽ tập trung vào việc cải thiện hiệu suất mạng và giảm thiểu chi phí.

5.2. Tác động của công nghệ mới

Công nghệ mới như 5G và IoT sẽ có tác động lớn đến mạng ad hoc di động. Việc tích hợp các công nghệ này vào các thuật toán tối ưu sẽ mở ra nhiều cơ hội mới cho việc cải thiện hiệu suất mạng.

Nội dung chính

Tổng quan nghiên cứu

Mạng ad hoc di động (MANET - Mobile Ad-hoc Network) là tập hợp các nút không dây tự trị, vận hành linh hoạt mà không phụ thuộc vào bất kỳ hạ tầng mạng cố định hay trạm điều khiển trung tâm nào. Trong kiến trúc này, mỗi thiết bị di động đồng thời đảm nhận hai vai trò: thiết bị đầu cuối và bộ định tuyến chuyển tiếp gói tin theo phương thức đa chặng. Tuy nhiên, tính chất di chuyển ngẫu nhiên và liên tục của các nút khiến cấu trúc hình trạng mạng biến động không ngừng, làm đứt gãy các tuyến truyền thông và kích hoạt quy trình tìm đường liên tục.

Giao thức định tuyến theo yêu cầu kinh điển AODV (Ad hoc On-Demand Distance Vector) sử dụng cơ chế truyền tràn ngập (flooding) để phát tán gói tin yêu cầu tìm đường (RREQ). Trong môi trường mật độ thiết bị dày đặc, cơ chế này gây ra hiện tượng "bão quảng bá" (broadcast storm), đẩy tỷ lệ xung đột gói tin lên tới hơn 65%, gây tắc nghẽn nghiêm trọng, gia tăng độ trễ đầu cuối và làm tiêu hao nhanh chóng nguồn năng lượng hạn hẹp của các nút mạng.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính với đề tài "Thuật toán quảng bá lại thông tin định tuyến nhằm tối thiểu hoá chi phí định tuyến trong mạng ad hoc di động" được thực hiện tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên nhằm giải quyết triệt để bài toán này. Mục tiêu trọng tâm của nghiên cứu là xây dựng và triển khai giao thức NKR (Neighbor Knowledge-based Rebroadcasting) tích hợp kỹ thuật phân cụm ảo LVC (Logical Virtual Clustering), kết hợp dự đoán chu kỳ sống của liên kết LEP (Link Expiration Period).

Nghiên cứu được hoàn thành vào năm 2020, cung cấp giải pháp giảm thiểu tới hơn 50% chi phí định tuyến dư thừa, cắt giảm lưu lượng điều khiển, duy trì chất lượng dịch vụ (QoS) với băng thông ổn định và kéo dài thời gian hoạt động của toàn mạng trên các kịch bản mô phỏng từ 20 đến 100 nút mạng di động.

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 truyền thông không dây tự cấu hình, tiêu chuẩn định tuyến AODV theo khuyến nghị RFC 3561 của tổ chức IETF, và lý thuyết đồ thị có hướng biểu diễn cấu trúc hình trạng mạng $G = (N, C)$. Trong đó, $N$ là tập hợp các nút mạng và $C$ là tập các liên kết truyền thông. Cơ chế truyền tín hiệu sóng vô tuyến được mô hình hóa qua hàm suy hao công suất thu $R_p(m) = (T_p T_G R_G \omega^2) / (4\pi m)^2$, với khoảng cách $m$ và bước sóng $\omega$, làm cơ sở xác định ngưỡng công suất thu nhận tín hiệu.

Bên cạnh giao thức định tuyến gốc AODV với 4 thông điệp điều khiển chính (RREQ, RREP, RERR, Hello), luận văn tích hợp 4 khái niệm lý thuyết cốt lõi:

1. Vùng phủ lân cận và độ trễ quảng bá: Xác định thứ tự chuyển tiếp gói tin dựa trên số lượng nút láng giềng chưa được bao phủ, gán độ trễ nhỏ hơn cho các nút có mật độ bao phủ cao hơn.
2. Hệ số kết nối (Connectivity Factor - CF): Tỷ số định lượng mức độ liên kết giữa các nút, đóng vai trò tham số quyết định xác suất phát lại thông tin.
3. Phân cụm ảo (Logical Virtual Clustering - LVC): Phân cấp chức năng nút thành nút công suất cao (H_Node) và nút công suất thấp (L_Node) kèm ba trạng thái thành viên (Lisolated, Lmember, Lgateway) nhằm giảm xung đột truyền dẫn.
4. Chu kỳ hiệu lực liên kết và tuyến đường (LEP/REP): Mô hình hình học - động học tính toán tuổi thọ liên kết dựa trên tọa độ vị trí, vận tốc và góc di chuyển của hai nút liền kề.

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

Nghiên cứu sử dụng phương pháp mô phỏng số lượng tử hóa kết hợp phân tích so sánh đối sánh thực nghiệm trên không gian mạng mô phỏng diện tích $1000m \times 1000m$.

• Cỡ mẫu và thiết lập thông số: Mạng lưới khảo sát bao gồm quy mô từ 20 đến 100 nút di động. Phạm vi truyền sóng của nút đạt bán kính 250m đối với nút thông thường và mở rộng đối với các nút H_Node. Tốc độ di chuyển của nút biến thiên từ 5 m/s đến 30 m/s theo mô hình chuyển động điểm ngẫu nhiên (Random Waypoint). Lưu lượng truyền dữ liệu sử dụng nguồn lưu lượng CBR (Constant Bit Rate) với kích thước gói tin chuẩn 512 bytes, thời gian mô phỏng mỗi kịch bản đạt 500 giây.
• Phương pháp chọn mẫu và phân tầng kịch bản: Dữ liệu được thu thập qua 4 kịch bản thực nghiệm biến thiên độc lập: (1) biến thiên lưu lượng mạng, (2) biến thiên số lượng nút mạng (20, 40, 60, 80, 100 nút), (3) biến thiên vận tốc di chuyển (5, 10, 15, 20, 25, 30 m/s), và (4) biến thiên băng thông yêu cầu.
• Lý do lựa chọn phương pháp phân tích: Việc phân tích định lượng thống kê trên môi trường mô phỏng chuẩn giúp đánh giá chính xác các tham số hiệu năng phức tạp mà không thể đo đạc thủ công trên mạng thực tế quy mô lớn. Phương pháp này cho phép kiểm chứng độc lập mức độ cải thiện của giao thức NKR so với giao thức gốc AODV cũng như các giải thuật cải tiến cùng thời kỳ như MERVS (giảm 55% chi phí) và QUACS (giảm 71% chi phí).

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

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

Quá trình phân tích thực nghiệm trên các kịch bản mô phỏng đa dạng đã đem lại 4 phát hiện quan trọng:

1. Cắt giảm vượt bậc tỷ lệ quảng bá gói tin RREQ: Khi số lượng nút mạng tăng từ 20 lên 100 nút, giao thức NKR đã kiểm soát chặt chẽ các gói tin truy vấn đường trùng lặp. Tỷ lệ phát lại của NKR luôn duy trì ở mức thấp hơn từ 45% đến 65% so với giao thức AODV truyền thống. Ngay cả khi lưu lượng kết nối tăng vọt, cơ chế tính toán diện tích phủ bổ sung giúp triệt tiêu hoàn toàn các gói tin dư thừa tại vùng giao thoa tín hiệu.
2. Tối ưu hóa chi phí định tuyến trong điều kiện di động cao: Ở vận tốc di chuyển cực đại 30 m/s, chi phí điều khiển định tuyến của AODV tăng vọt do hiện tượng mất liên kết liên tục. Ngược lại, giao thức NKR duy trì chi phí định tuyến ổn định, giảm khoảng 50% tổng số gói tin điều khiển so với AODV tiêu chuẩn, đồng thời tiết kiệm hơn giao thức MERVS khoảng 18% chi phí tiêu hao băng thông.
3. Nâng cao độ ổn định liên kết và giảm tỷ lệ tái liên kết: Thông qua chỉ số độ mở rộng tuyến đường $D = REP / TH$ (với $REP$ là chu kỳ hiệu lực tuyến và $TH$ là số chặng nhảy), thuật toán luôn ưu tiên chọn các đường truyền có tuổi thọ cao nhất và số chặng ngắn nhất. Tỷ lệ tái thiết lập liên kết bị đứt giảm hơn 40% so với phương pháp tìm đường ngẫu nhiên, bảo đảm tiêu chuẩn băng thông đáp ứng quy tắc $2 \times \text{Bandwidth} \le \sum \text{PathBW}$.
4. Hiệu quả vượt trội của phân cụm ảo LVC khi hệ số kết nối thấp: Khi hệ số kết nối $CF < 0.5$, việc kích hoạt LVC và chuyển quyền phát sóng cho các nút H_Node đã giúp mạng tránh được tình trạng phân mảnh, giảm tỷ lệ nghẽn kênh truyền tại các nút trung gian xuống dưới 15%.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán đề xuất đạt hiệu năng vượt trội là việc xóa bỏ hoàn toàn cơ chế phát tán mù quáng của AODV. Thay vì để tất cả các nút lân cận nhận được RREQ cùng đồng loạt phát lại, thuật toán NKR thiết lập hàng đợi trễ thông minh: nút nào có khả năng bao phủ nhiều nút chưa biết nhất sẽ được quyền phát trước, khiến các nút xung quanh tự động hủy bỏ gói tin trùng lặp khi nhận được tín hiệu tiếp sóng.

So sánh với các nghiên cứu trước đây, kỹ thuật điều chỉnh bộ định thời của Periyasamy chỉ giảm được gần 40% chi phí định tuyến nhưng vẫn bị động trước sự biến đổi topo đột ngột. Kỹ thuật xác suất tĩnh như MERVS hay QUACS dù giảm được từ 55% đến 71% chi phí nhưng không tính đến yếu tố vận tốc và hướng di chuyển của thiết bị. Luận văn của tác giả Lê Hồng Sơn đã khắc phục hoàn toàn nhược điểm này bằng cách kết hợp dự báo động học phân chia vị trí Newton với cơ chế phân cụm LVC.

Toàn bộ dữ liệu thực nghiệm trong luận văn được hệ thống hóa trực quan thông qua 7 biểu đồ phân tích xu hướng hiệu năng (từ Hình 3.1 đến Hình 3.7) và 8 bảng dữ liệu thống kê chi tiết (từ Bảng 3.1 đến Bảng 3.8), phản ánh rõ nét mối tương quan giữa vận tốc di chuyển, mật độ nút và chi phí truyền thông.

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

Nhằm chuyển hóa các kết quả nghiên cứu lý thuyết vào thực tiễn phát triển mạng không dây thế hệ mới, luận văn đưa ra 4 khuyến nghị và giải pháp hành động cụ thể:

1. Tích hợp module thuật toán NKR vào hệ điều hành mạng nhúng cho thiết bị IoT:

   • Hành động: Biên dịch và nhúng thuật toán tính trễ quảng bá và hệ số kết nối vào firmware của các thiết bị định tuyến biên di động.
   • Mục tiêu: Cắt giảm 45% năng lượng tiêu hao cho tiến trình định tuyến trên các thiết bị chạy pin.
   • Thời gian thực hiện: Lộ trình 6 đến 12 tháng.
   • Chủ thể thực hiện: Các kỹ sư phát triển phần mềm nhúng và giao thức mạng không dây.

2. Chuẩn hóa công thức dự báo liên kết LEP trên các hệ thống định vị thời gian thực:

   • Hành động: Ứng dụng mô hình tính toán LEP kết hợp tín hiệu GPS vi sai hoặc cảm biến quán tính IMU trên phương tiện di chuyển để chủ động chuyển mạch trước khi liên kết đứt gãy.
   • Mục tiêu: Đạt độ chính xác dự báo tuổi thọ liên kết trên 90%, giảm độ trễ tìm đường xuống dưới 20ms.
   • Thời gian thực hiện: Trong vòng 12 tháng.
   • Chủ thể thực hiện: Các nhóm nghiên cứu viễn thông và giao thông thông minh (ITS/VANET).

3. Mở rộng cơ chế phân cụm ảo LVC đa mức dựa trên chỉ số năng lượng dư thừa:

   • Hành động: Nâng cấp thuật toán phân loại H_Node và L_Node bằng cách bổ sung trọng số dung lượng pin thực tế bên cạnh công suất phát sóng vô tuyến.
   • Mục tiêu: Kéo dài thời gian sống của toàn mạng thêm 30% trong các tình huống cứu hộ khẩn cấp.
   • Thời gian thực hiện: Giai đoạn 2026 - 2027.
   • Chủ thể thực hiện: Các nhà khoa học máy tính và chuyên gia tối ưu hóa mạng.

4. Triển khai thử nghiệm thực địa trên mô hình dàn thiết bị thực tế (Testbed):

   • Hành động: Thiết lập mạng thử nghiệm với quy mô từ 50 đến 100 thiết bị di động (máy bay không người lái drone, xe cứu thương, thiết bị cầm tay) trong môi trường thực địa phức tạp.
   • Mục tiêu: Đánh giá mức độ suy hao kênh truyền thực tế và tinh chỉnh tham số trễ quảng bá.
   • Thời gian thực hiện: Kế hoạch 18 tháng.
   • Chủ thể thực hiện: Các viện nghiên cứu quốc phòng, cứu hộ thảm họa và doanh nghiệp công nghệ viễn thông.

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

Luận văn là tài liệu học thuật và kỹ thuật chuyên sâu, mang lại giá trị thực tiễn cao cho 4 nhóm đối tượng chính:

1. Học viên cao học, nghiên cứu sinh và giảng viên ngành Khoa học máy tính, Mạng máy tính:

   • Lợi ích: Tiếp cận khung lý thuyết toán học hoàn chỉnh về định tuyến mạng ad hoc, các phương trình vi phân chuyển động và thuật toán phân cụm ảo.
   • Trường hợp sử dụng: Làm tài liệu tham khảo cho các đề tài nghiên cứu chuyên sâu về giao thức định tuyến không dây, tối ưu hóa thuật toán phân tán và lý thuyết đồ thị ứng dụng.

2. Kỹ sư phát triển phần mềm mạng, hệ thống nhúng và giao thức không dây:

   • Lợi ích: Nắm vững mã giả chi tiết của hai thủ tục then chốt Route_Finding và Route_maintenance, cơ chế xử lý hàng đợi FIFO và quản lý bảng định tuyến.
   • Trường hợp sử dụng: Ứng dụng trực tiếp vào việc lập trình giao thức định tuyến cho mạng cảm biến không dây (WSN) và mạng kết nối xe cộ (VANET).

3. Chuyên gia thiết kế hệ thống truyền thông tác chiến quân sự và cứu nạn khẩn cấp:

   • Lợi ích: Sở hữu giải pháp thiết lập mạng dã chiến tức thời tại các khu vực bị thiên tai phá hủy hoàn toàn hạ tầng trạm viễn thông cố định.
   • Trường hợp sử dụng: Xây dựng mạng liên lạc nội bộ ổn định giữa các phương tiện cứu hỏa, cảnh sát và nhân viên cứu hộ với băng thông đảm bảo chất lượng QoS.

4. Kiến trúc sư giải pháp IoT công nghiệp và đô thị thông minh:

   • Lợi ích: Giải pháp mở rộng quy mô mạng kết nối hàng nghìn nút cảm biến tự trị mà không lo quá tải băng thông hay xung đột bão quảng bá.
   • Trường hợp sử dụng: Thiết kế kiến trúc mạng Rooftop băng rộng và mạng lưới cảm biến quan trắc môi trường thông minh.

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

Hiện tượng bão quảng bá trong mạng MANET là gì và gây ra những hậu quả kỹ thuật nào? Hiện tượng bão quảng bá xuất hiện khi các nút mạng đồng loạt phát tán gói tin yêu cầu tìm đường RREQ theo cơ chế làm tràn ngập truyền thống. Điều này khiến hơn 60% gói tin bị xung đột trên kênh vô tuyến dùng chung, làm nghẽn băng thông, gia tăng độ trễ tìm đường lên nhiều lần và gây sụt giảm nghiêm trọng tỷ lệ truyền dữ liệu thành công.

Thuật toán NKR kiểm soát việc phát lại gói tin RREQ khác biệt như thế nào so với AODV truyền thống? Thay vì chuyển tiếp ngay lập tức mọi gói RREQ nhận được, thuật toán NKR tính toán diện tích phủ bổ sung và gán thời gian trễ phát sóng ngược với số lượng láng giềng quen thuộc. Nút có độ phủ lớn nhất sẽ phát trước, cập nhật danh sách nút đã nhận cho các thiết bị xung quanh, giúp các nút lân cận tự động hủy bỏ gói tin trùng lặp để tiết kiệm 45% đến 65% lưu lượng.

Cơ chế phân cụm ảo LVC đóng vai trò gì trong việc tối ưu hóa chi phí định tuyến? Phân cụm ảo LVC chia mạng thành các nút công suất cao (H_Node) và nút công suất thấp (L_Node). Khi hệ số kết nối mạng $CF < 0.5$, LVC chỉ cho phép các nút H_Node có phạm vi truyền sóng rộng tham gia chuyển tiếp dữ liệu đa chặng. Cơ chế này giảm đáng kể số bước nhảy trung gian và cắt giảm hơn 35% chi phí điều khiển định tuyến phát sinh.

Chu kỳ hiệu lực liên kết LEP được tính toán dựa trên các thông số động học nào? Chu kỳ hiệu lực liên kết LEP được tính toán dựa trên mô hình chuyển động hình học gồm tọa độ không gian 2 chiều $(i, j)$, vận tốc di chuyển $S$, hướng chuyển động góc $\alpha$ của hai nút liền kề và bán kính truyền thông $a$. Qua đó, thuật toán dự báo chính xác thời điểm liên kết bị đứt để chủ động chuyển tuyến mà không làm gián đoạn luồng dữ liệu.

Thuật toán cải tiến trong luận văn đã được kiểm chứng trên những kịch bản hiệu năng nào? Giao thức NKR được kiểm chứng qua 4 kịch bản mô phỏng toàn diện: biến thiên số nút mạng (20 đến 100 nút), biến thiên vận tốc di chuyển (5 đến 30 m/s), biến thiên mật độ lưu lượng truyền và biến thiên mức băng thông yêu cầu. Kết quả chứng minh NKR vượt trội về tỷ lệ quảng bá, chi phí định tuyến và tỷ lệ duy trì liên kết so với AODV và QUACS.

Kết luận

• Luận văn đã giải quyết triệt để bài toán "bão quảng bá" của giao thức AODV bằng việc đề xuất thành công giao thức định tuyến cải tiến NKR kết hợp cơ chế phân cụm ảo LVC.
• Xây dựng hoàn chỉnh mô hình toán học dự báo chu kỳ sống liên kết LEP và tuyến đường REP, cho phép tối ưu hóa việc chọn đường truyền chất lượng cao dựa trên hệ số mở rộng $D = REP / TH$.
• Kết quả thực nghiệm khẳng định giải pháp giúp cắt giảm từ 45% đến 65% tỷ lệ phát lại gói tin dư thừa, hạ 50% chi phí định tuyến và duy trì băng thông ổn định trong môi trường di động cao tới 30 m/s.
• Kế hoạch mở rộng nghiên cứu trong giai đoạn 12 đến 24 tháng tới tập trung vào việc thử nghiệm thuật toán trên mạng xe cộ VANET và tích hợp trí tuệ nhân tạo dự đoán quỹ đạo di chuyển của các thiết bị bay không người lái (UAV).
• Các nhà nghiên cứu, kỹ sư hệ thống và chuyên gia viễn thông hãy khai thác và ứng dụng ngay các thuật toán định tuyến tiên tiến này nhằm nâng cao hiệu năng và độ tin cậy cho các hệ thống mạng không dây tự cấu hình thế hệ mới.

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

Chương 1 trình bày tổng quan về mạng ad hoc, giao thức định tuyến AODV và một số phương pháp cải tiến cơ chế quảng bá thông tin định tuyến của giao thức AODV. Phương pháp và thuật toán cải tiến thuật toán quảng bá định tuyến dựa trên thông tin từ các nút lân cận sẽ được trình bày chi tiết trong Chương 2. Kết quả của việc mô phỏng, so sánh đánh giá hiệu năng của giao thức NKR – giao thức triển khai phương pháp cải tiến thuật toán quảng bá định tuyến dựa trên thông tin từ các nút lân cận so với một số giao thức có liên quan được trình bày trong Chương 3. Cuối cùng là phần kết luận đưa ra những tổng kết và hướng phát triển của luận văn.

TỔNG QUAN VỀ MẠNG AD HOC VÀ ỨNG DỤNG 1. Tổng quan về mạng ad hoc 1. Định nghĩa và đặc trưng của mạng ad hoc Theo định nghĩa của Tổ chức IETF (Internet Engineering Task Force), Mạng ad hoc không dây di động là một vùng tự trị (Autonomous System) của các bộ định tuyến được kết nối với nhau bằng liên kết không dây. Mỗi nút mạng vừa đóng vai trò là thiết bị đầu cuối vừa đóng vai trò là bộ định tuyến.

Các nút có thể di chuyển một cách tự do làm cho kiến trúc của mạng thay đổi liên tục. Minh họa mạng ad hoc di động Như vậy có thể thấy mạng ad hoc di động bao gồm tập các nút không dây di động có thể trao đổi dữ liệu một cách linh động mà không cần sự hỗ trợ của trạm cơ sở cố định hoặc mạng có dây. Mỗi nút di động có một phạm vi truyền giới hạn, do đó chúng cần sự trợ giúp của các nút láng giềng để chuyển tiếp các gói dữ liệu.1 là một ví dụ minh họa cho một mạng ad hoc di động. Trong ví dụ này, các gói tin từ nút nguồn là một máy tính cần chuyển tới một nút đích là 4 một điện thoại thông minh không nằm trong phạm vi truyền của nút nguồn.

Vì vậy, cần có sự trợ giúp của các nút trung gian để chuyển tiếp gói tin từ nút nguồn tới nút đích. Để thực hiện được công việc này, các nút mạng phải sử dụng giao thức định tuyến phù hợp cho mạng ad hoc di động. Trong mạng ad hoc, liên kết giữa các nút mạng được đặc trưng bởi khoảng cách giữa các nút và tính sẵn sàng hợp tác để tạo thành mạng mặc dù là tạm thời. Để triển khai thành công được mạng ad hoc, thiết kế và công nghệ mạng phải đáp ứng được các yêu cầu sau:  Đảm bảo kết nối khi nút mạng di chuyển: Khoảng cách giữa các nút hoặc trạng thái ở gần nhau của chúng định nghĩa ranh giới mạng.

Chỉ cần hai hoặc nhiều nút chuyển động trong một bán kính nhất định là tạo thành một mạng ad-hoc. Chính sự chuyển động làm cho khoảng cách giữa các nút thay đổi gây ra bản chất đặc biệt (ad-hoc) của mạng.  Tính sẵn sàng hợp tác: Các nút ở trong khoảng cách đủ gần phải sẵn sàng hợp tác để tạo thành mạng. Nói cách khác, tự bản thân nút quyết định “online” hay “offline”.

 Mạng ngang hàng tạm thời: Tại bất cứ một thời điểm nào, mạng ad-hoc được xác định bởi các nút đang “online” và ở trong một khoảng cách nhất định. Một nút luôn có xu hướng tham gia hay biến mất khỏi mạng. Do đó, mạng được coi là tạm thời. Hơn nữa, do không có một cơ sở hạ tầng mạng cho trước, các nút trong mạng phải truyền thông theo kiểu ngang hàng (peer- to-peer).

Đặc điểm của mạng ad hoc Do ad hoc là một mạng không dây hoạt động không cần sự hỗ trợ của hạ tầng mạng cơ sở trên cơ sở truyền thông đa chặng giữa các thiết bị di động vừa đóng vai trò là thiết bị đầu cuối, vừa đóng vai trò là bộ định tuyến nên mạng ad hoc còn có một số đặc điểm nổi bật sau [11]:  Cấu trúc động: Do tính chất di chuyển ngẫu nhiên của các nút mạng nên cấu trúc của loại mạng này cũng thường xuyên thay đổi một cách ngẫu nhiên ở những thời điểm không xác định trước. Trong khi thay đổi, cấu trúc của mạng ad hoc có thêm hoặc mất đi các kết nối hai chiều hoặc kết nối một chiều.  Chất lượng liên kết hạn chế: Các liên kết không dây thường có băng thông nhỏ hơn so với các liên kết có dây. Ngoài ra, do ảnh hưởng của cơ chế đa truy cập, vấn đề suy giảm tín hiệu, nhiễu và các yếu tố khác, băng thông thực của các liên kết không dây thường thấp hơn nhiều so với tốc độ truyền tối đa theo lý thuyết của môi trường truyền không dây.

 Các nút mạng có tài nguyên hạn chế: Mỗi nút di động trong mạng ad hoc có thể là một bộ cảm biến, một điện thoại thông minh hoặc một máy tính xách tay. Thông thường các thiết bị này có tài nguyên hạn chế so với các máy tính trong mạng có dây và không dây truyền thống về tốc độ xử lý, dung lượng bộ nhớ và năng lượng nguồn pin nuôi sống hoạt động của nút.  Độ bảo mật thấp ở mức độ vật lý: Mạng không dây di động thường chịu tác động về mặt vật lý từ các nguồn gây nguy hại về an ninh nhiều hơn so với mạng có dây. Về khía cạnh vật lý, các kỹ thuật gây mất an ninh và bảo mật trong mạng như nghe lén, giả mạo và tấn công từ chối dịch vụ thường dễ triển khai trong mạng ad hoc hơn là trong mạng có dây truyền thống.

Ứng dụng của mạng ad hoc Mạng ad hoc có rất nhiều ưu thế so với các mạng truyền thống về mặt ứng dụng trong những điều kiện khó có thể triển khai được một cơ sở hạ tầng mạng cố định hoặc việc triển khai là không khả thi do những lý do về mặt thực hành (địa hình,…) hoặc do những lý do về kinh tế (chi phí cáp trong một không gian lớn, chi phí thiết lập nhiều điểm truy cập).  Ứng dụng trong quân đội Những thành tựu mới của công nghệ thông tin thường được áp dụng trong quân sự đầu tiên, và mạng không dây kiểu không cấu trúc cũng không phải là một ngoại lệ. Nhiều năm nay, quân đội đã sử dụng các mạng “packet radios” – một nguyên mẫu đầu tiên của mạng chuyển mạch gói không dây ngày nay. Mạng ad hoc thuần túy thường tuân theo một mô hình điểm ngẫu nhiên, các nút tự do di chuyển theo bất cứ hướng nào, với bất cứ tốc độ nào.

Trong mô hình mạng ad hoc cho quân đội, các nút phân nhóm theo bản chất tự nhiên của chúng khi chúng cùng thực hiện một nhiệm vụ cụ thể. Xu hướng di động ở đây là theo nhóm. Do đó, nếu đưa ra được một mô hình chuyển động theo nhóm, các vấn đề của mạng ad hoc sẽ trở nên cụ thể hơn (ví dụ: định tuyến, sử dụng các ứng dụng thời gian thực như tiếng nói, video,…), cho phép phát triển một giải pháp tối ưu.  Các ứng dụng trong cuộc sống Mạng ad hoc rất lý tưởng trong các trường hợp không có sẵn một cơ sở hạ tầng thông tin, tuy nhiên lại cần phải thành lập một mạng tạm thời nhằm trao đổi thông tin và hợp tác cùng làm việc.

7 Tại các vùng bị thiên tai, thảm họa, khó có thể có được một cơ sở hạ tầng về thông tin vững chắc. Hệ thống có trước đó rất có thể bị hỏng hoặc bị phá hủy hoàn toàn. Tại vùng có thảm họa, tất cả các phương tiện và hệ thống truyền thông đều bị phá hủy hoàn toàn. Mỗi chiếc xe của cảnh sát, cứu hỏa, cứu thương,… đều được trang bị như một thiết bị đầu cuối di động – là một phần của mạng ad-hoc.

Mỗi nhân viên cũng mang theo một thiết bị đầu cuối di động. Các thiết bị đầu cuối này đều liên kết với nhau, hình thành nên một mạng tạm thời nhằm trao đổi thông tin. Cấu hình mạng thay đổi theo những thời điểm khác nhau. Ngoài ra, các thiết bị đầu cuối di động không chỉ cung cấp chức năng gửi và nhận thông tin mà còn có thể chuyển tiếp thông tin – đóng vai trò như router trên Internet.

Đối với ứng dụng chia sẻ tài nguyên trong hội họp, khác với cách làm truyền thống khi những người tham gia hội thảo muốn chia sẻ tài liệu cho nhau là gửi file đính kèm qua email hoặc sao chép qua các thiết bị lưu trữ thứ cấp có khả năng di động, tất cả những người tham dự hội thảo đều có thể sử dụng thiết bị di động để tạo thành một mạng ad-hoc trong suốt thời gian đó. Các thiết bị có thể truyền thông với nhau, truyền/nhận các tài liệu được sử dụng trong hội thảo. Khi hội thảo kết thúc, các thiết bị được tắt nguồn, mạng tự bị hủy bỏ. Đối với ứng dụng trong cuộc sống hàng ngày, môi trường mạng là mạng ad hoc thuần túy, tức là không có cơ sở hạ tầng về cáp, các thiết bị đầu cuối tự cấu hình để thành lập mạng, mà không có sự quản lý tập trung.

Mạng này có thể tự chia nhỏ thành các mạng con. Ví dụ như một mạng riêng giữa em học sinh và bạn của em, một mạng “chung” được khởi tạo bởi người muốn chia sẻ các chương trình trò chơi điện tử trên máy của anh ta. Hai mạng này được trộn lẫn vào nhau một cách linh động. Ví dụ minh họa mạng ad hoc trên xe bus  Mạng cảm biến Cảm biến là các thiết bị nhỏ, phân tán, giá thành thấp, tiết kiệm năng lượng, có khả năng truyền thông không dây và xử lý cục bộ.

Mạng cảm biến là mạng gồm các nút cảm biến (sensor) – các nút này hợp tác với nhau để cùng thực hiện một nhiệm vụ cụ thể, ví dụ như: giám sát môi trường (không khí, đất, nước), theo dõi môi trường sống, hành vi, dân số của các loài động, thực vật, dò tìm động chấn, theo dõi tài nguyên, thực hiện trinh thám trong quân đội,. Trước đây mạng cảm biến thường bao gồm một lượng nhỏ các nút cảm biến được kết nối bằng cáp tới một trạm xử lý tập trung. Ngày nay, các nút mạng cảm biến thường là không dây, phân tán để vượt qua các trở ngại vật lý của môi trường, tiết kiệm năng lượng và do trong nhiều trường hợp không thể có được một hạ tầng có sẵn về năng lượng và truyền thông. Công nghệ mạng không dây kiểu không cấu trúc thường được áp dụng để triển khai mạng cảm biến do:  Các nút cảm biến được phân tán trong vùng không có sẵn cơ sở hạ tầng về truyền thông và năng lượng.

Các nút phải tự hình thành kết nối.