Tổng quan luận án

Luận án tiến sĩ công nghệ thông tin với đề tài "Hỗ trợ định vị và nâng cao hiệu năng định tuyến dựa trên thông tin vị trí cho các mạng cảm biến không dây" được nghiên cứu sinh Lê Đình Thanh thực hiện dưới sự hướng dẫn khoa học của PGS. Hồ Thuần và TS. Nguyễn Đại Thọ tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội (bảo vệ năm 2014, chuyên ngành Truyền dữ liệu và Mạng máy tính, mã số: 62.01).

Mạng cảm biến không dây (Wireless Sensor Networks - WSN) là mạng tự hợp gồm số lượng lớn các nút cảm biến có kích thước nhỏ, năng lực tính toán hạn chế, bộ nhớ nhỏ và nguồn pin giới hạn, thường không thể nạp lại năng lượng. Các nút cảm biến thu nhận tín hiệu vật lý từ môi trường (nhiệt độ, độ ẩm, áp suất, ánh sáng, nồng độ khí $CO_2$) và truyền thông không dây phục vụ các ứng dụng giám sát môi trường, nông nghiệp, y tế và quân sự. Trong bối cảnh quy mô mạng có thể lên tới hàng ngàn nút, các giao thức định tuyến dựa trên cấu trúc mạng (topology-based) — bao gồm định tuyến chủ động (proactive), thụ động (reactive) và lai (hybrid) — bộc lộ sự không phù hợp do đòi hỏi bộ nhớ lưu trữ bảng định tuyến lớn và tạo ra lượng gói tin điều khiển phát tràn (flooding) gây cạn kiệt năng lượng các nút.

Định tuyến dựa trên thông tin vị trí (location-based routing / geographic routing) là giải pháp thay thế phù hợp khi mỗi nút chỉ cần duy trì thông tin vị trí cục bộ của các nút láng giềng. Tuy nhiên, việc ứng dụng định tuyến dựa trên vị trí gặp phải hai rào cản kỹ thuật lớn:

  1. Nút cảm biến cần biết tọa độ của mình: Việc trang bị thiết bị định vị toàn cầu (GPS) gây tốn kém chi phí phần cứng và tiêu thụ nhiều năng lượng, đồng thời không hoạt động được trong môi trường kín. Do đó, cần sử dụng các thuật toán định vị phân tán dựa trên kết nối (connectivity-based localization). Tuy vậy, các thuật toán định vị này lại phụ thuộc vào việc xác định các nút biên, trong khi các thuật toán phát hiện biên (boundary detection) hiện hữu hoặc có độ phức tạp truyền thông cao hoặc chỉ hoạt động trên mạng có mật độ nút dày và phân bố đều.
  2. Vấn đề hiệu năng và cực tiểu địa phương (local minimum): Khi gói tin gặp vùng trống truyền thông (communication hole), việc chuyển tiếp tham lam (greedy forwarding) thất bại, buộc giao thức phải chuyển sang chế độ khôi phục bằng cách đi theo biên (boundary detouring). Điều này dẫn đến các đường đi dài, đi vòng, gây quá tải lưu lượng tại các nút biên, làm cạn kiệt pin và khoét rộng thêm các vùng trống. Ngoài ra, việc sử dụng các gói tin định kỳ (hello/beacon packets) để duy trì danh sách láng giềng gây tiêu tốn đáng kể băng thông và năng lượng.

Xuất phát từ các hạn chế trên, luận án xác định ba mục tiêu nghiên cứu cụ thể được đánh số như sau:

  1. Mục tiêu thứ nhất: Đề xuất một thuật toán phát hiện biên dựa trên kết nối phục vụ cho định vị có chi phí truyền thông và tính toán thấp, có khả năng làm việc trên cả các mạng cảm biến có mật độ nút thưa và phân bố không đều.
  2. Mục tiêu thứ hai: Đề xuất một giao thức tối ưu hóa đường đi có thể tạo nhanh và khai thác hiệu quả các đường tắt (shortcuts), có thể áp dụng cho kịch bản có nhiều nút đích, nhằm rút ngắn đường đi và phân tải khỏi các nút biên trong định tuyến đơn phát dựa trên thông tin vị trí.
  3. Mục tiêu thứ ba: Đề xuất một giao thức định tuyến dựa trên thông tin vị trí không sử dụng gói tin chào hỏi, kết hợp đồng thời hai hình thức cạnh tranh quyết liệt (aggressive contention) và không quyết liệt (non-aggressive contention) nhằm kế thừa ưu điểm giảm trễ, tiết kiệm băng thông và triệt tiêu gói tin trùng lặp.

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

  • Đối tượng nghiên cứu: Các thuật toán phát hiện biên mạng, thuật toán định vị dựa trên kết nối, và các giao thức định tuyến đơn phát dựa trên thông tin vị trí trong mạng cảm biến không dây.
  • Phạm vi và giả thiết không gian - thời gian:
    • Mạng cảm biến không dây hai chiều (2D), các nút phân bố ngẫu nhiên trên một khu vực phẳng rộng lớn.
    • Các nút phát sóng vô tuyến đẳng hướng với các liên kết truyền thông đối xứng (hai nút liên kết với nhau nếu khoảng cách hình học nhỏ hơn bán kính phủ sóng $r$).
    • Mạng tĩnh, các nút cảm biến ít hoặc không di chuyển trong suốt quá trình hoạt động.

Tổng quan tài liệu và vị trí của luận án

Luận án đã tiến hành hệ thống hóa và phân loại các công trình nghiên cứu liên quan đến định vị, phát hiện biên và định tuyến dựa trên thông tin vị trí:

1. Tổng quan các nghiên cứu định vị trong mạng cảm biến

Các thuật toán định vị được chia thành hai nhóm chính:

  • Định vị dựa trên khoảng (range-based): Sử dụng đo đạc khoảng cách (lateration/multilateration [61, 97]) hoặc góc (angulation [72]). Nhóm này yêu cầu phần cứng phụ trợ để thu nhận tín hiệu (RSSI, TOA, TDOA, AOA), nhạy cảm với nhiễu môi trường và đòi hỏi mật độ điểm neo (anchor nodes) dày đặc.
  • Định vị dựa trên kết nối (connectivity-based): Sử dụng thông tin liên kết topo không cần điểm neo. Điển hình gồm phương pháp co giãn đa chiều MDS (Multi-dimensional Scaling) của Shang và cộng sự [86] (thuật toán tập trung, sai số lớn khi có vùng trống); phương pháp mảng cao su Rubberband của Bruck và cộng sự [27, 81] (độ phức tạp tính toán và truyền thông cao, dễ biến dạng mạng nếu biên sai); và phương pháp sử dụng đồ thị Delaunay kết hợp định vị khoảng cách của Lederer và cộng sự [56] (chính xác và phân tán nhưng yêu cầu đầu vào là tập các nút biên chính xác).
Nhóm phương pháp Thuật toán định vị Yêu cầu điểm neo Yêu cầu phần cứng phụ trợ Yêu cầu biết nút biên Khả năng biến dạng Phân tán Độ phức tạp tính toán Độ phức tạp thông báo
Dựa trên khoảng Định vị theo khoảng cách [61, 97] Có Có Không Thấp Có Thấp Thấp
Định vị theo góc [72] Có Có Không Thấp Có Thấp Thấp
Dựa trên kết nối Co giãn đa chiều (MDS) [86] Không Không Không Cao Không Cao Cao
Mảng cao su (Rubberband) [27, 81] Không Không Có Cao Có Cao Cao
Đồ thị Delaunay & khoảng cách [56] Không Không Có Thấp Có Cao Cao

2. Tổng quan các nghiên cứu phát hiện biên

  • Nhóm thống kê: Dựa trên bậc nút như phân ngưỡng bậc của Fekete và cộng sự [21], so sánh tương phản bậc 2 chặng của Bi và cộng sự [5], hoặc phân ngưỡng mức trung tâm (centrality) [22]. Nhược điểm là chỉ hoạt động chính xác khi nút phân bố đều và mật độ cao.
  • Nhóm dựa trên topo/kết nối: Dựa trên tính tương đồng của Ghrist và cộng sự [29], cấu trúc hoa và chu kỳ gia tăng của Kröller và cộng sự [53], tìm tổ tiên chung bé nhất trên cây đường đi ngắn nhất của Wang và cộng sự [91], hoặc đường đồng mức của Funke [26]. Các phương pháp này đòi hỏi chi phí phát tràn và bầu chọn điểm mốc phức tạp.
Nhóm phương pháp Thuật toán phát hiện biên Phân tán Yêu cầu mạng phân bố đều, dày Độ phức tạp tính toán Độ phức tạp thông báo
Thống kê Phân ngưỡng bậc [21] Có Có Thấp Thấp
So sánh tương phản bậc [5] Có Có Thấp Thấp
Phân ngưỡng mức trung tâm [22] Có Có Trung bình Trung bình
Dựa trên topo Tính tương đồng [29] Không Có Trung bình Trung bình
Hoa và chu kỳ gia tăng [53] Có Có Trung bình Trung bình
Tổ tiên chung bé nhất [91] Có Có Cao Cao
Đường đồng mức [26] Có Không Cao Cao

3. Tổng quan các nghiên cứu định tuyến dựa trên thông tin vị trí và xử lý cực tiểu địa phương

  • Chuyển tiếp dựa trên vị trí: Chuyển tiếp tham lam (Greedy Forwarding - GF [24]), bước tiến ngẫu nhiên (RPM [73]), chuyển tiếp theo góc (Compass Forwarding [6, 7, 52]), chuyển tiếp theo góc bị chặn (Bounded Compass [18]), chuyển tiếp theo bước tiến (MFR [88]), chuyển tiếp với quán tính (Inertia Forwarding [75]).
  • Tránh cực tiểu địa phương: Mở rộng vùng lân cận/tầm vực (Viewscope của Lim và cộng sự [62], Topological Awareness - TA của Xi và cộng sự [95], gắn nhãn đỏ/trắng 2 chặng của Wuu và cộng sự [94]); mô hình hóa vùng trống hình tròn [101], hình elip [60, 89, 100], đa giác lồi [87]; sử dụng hệ tọa độ ảo (AVCS [63], HopID [103], đồ thị phẳng Gabriel dựa trên định lý Tutte [10, 86], thêm chiều tọa độ [2], tọa độ đa cấp [99], dòng Ricci rời rạc [17, 34, 42, 83]).
  • Định tuyến khôi phục: Phát tràn [41, 88], quay lui [31], định tuyến trên mặt phẳng (Face Routing [46, 49, 54, 55, 58, 65]), đi theo biên (Boundary Detouring như BOUNDHOLE [20], GRIC [74]), cây bao lồi (Hull Tree [58, 102]).
Kỹ thuật khôi phục Chiến lược Yêu cầu duy trì thông tin phụ trợ Độ phức tạp thông báo Độ phức tạp tính toán Độ dài đường đi / Trễ đầu cuối - đầu cuối
Phát tràn [41, 88] Đa đường Không Cao Thấp Nhỏ
Quay lui [31] Đơn đường Trạng thái nút trống Trung bình Thấp Lớn
Định tuyến trên mặt [46, 58] Đơn đường Đồ thị phẳng Trung bình Trung bình Trung bình
Đi theo biên (BOUNDHOLE) [20] Đơn đường Không Thấp Thấp Trung bình
Cây bao lồi (Hull Tree) [58, 102] Đơn đường Cây bao lồi Cao Cao Trung bình

Khoảng trống nghiên cứu được lựa chọn: Luận án lựa chọn giải pháp định vị dựa trên đồ thị Delaunay của Lederer [56] và khắc phục nhược điểm của nó bằng cách xây dựng thuật toán phát hiện biên cục bộ trên đồ thị lân cận 2 chặng. Về định tuyến, luận án phát triển trên nền tảng kết hợp chuyển tiếp tham lam [24] và đi theo biên BOUNDHOLE [20], giải quyết triệt để vấn đề đường đi vòng và quá tải biên bằng kỹ thuật tối ưu hóa đường tắt phân tán đa đích, đồng thời loại bỏ gói tin chào hỏi thông qua cơ chế cạnh tranh kết hợp hai giai đoạn.

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

1. Cơ sở lý thuyết và các khái niệm nền tảng

  • Đồ thị vùng lân cận 2 chặng ($2NG - \text{2-hop Neighbourhood Graph}$): Với mỗi nút $p$, $2NG(p)$ là đồ thị phẳng con cảm ứng được tạo bởi tập hợp các nút cách $p$ đúng 2 chặng và các liên kết trực tiếp giữa các nút này.
  • Heuristic hình học liên tục và rời rạc: Trong mặt phẳng liên tục, đường tròn tâm $p$ bán kính $r$ cắt biên sẽ bị chia thành các cung liền nét (vùng có mạng) và cung đứt nét (vùng trống). Chuyển sang không gian topo rời rạc, một nút $p$ nằm gần biên khi và chỉ khi đồ thị $2NG(p)$ của nó không tạo thành một cấu trúc "vành" khép kín (ring).
  • Cực tiểu địa phương và quy tắc chuyển trạng thái: Tiến trình xử lý gói tin chuyển tiếp dựa trên vị trí chuyển đổi giữa hai trạng thái: chế độ tham lam (Greedy Mode) và chế độ khôi phục (Recovery Mode). Nút cực tiểu địa phương là nút không có láng giềng nào gần đích hơn chính nó.
  • Kỹ thuật quay (Sweeping Rule) trong BOUNDHOLE: Xác định nút chuyển tiếp tiếp theo dựa trên việc quay tia định hướng từ nút hiện tại sang nút trước đó theo chiều kim đồng hồ để lần theo đường bao của vùng trống.
  • Cơ chế đường tắt (Shortcut) và vùng khả áp dụng: Tạo các liên kết logic bỏ qua đoạn đường cong lõm men theo biên và ánh xạ đường tắt này cho một không gian vùng đích (applicable area) thay vì một nút đích đơn lẻ.

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

Luận án kết hợp giữa phương pháp nghiên cứu lý thuyết hình thức và mô phỏng thực nghiệm:

  • Phương pháp lý thuyết: Thiết kế thuật toán phân tán cục bộ tại từng nút mạng, chứng minh tính đúng đắn của cấu trúc vành trên đồ thị 2 chặng, xây dựng quy tắc định tuyến hình học và hàm trễ cho cạnh tranh kênh truyền không dây.
  • Phương pháp thực nghiệm và mô phỏng định lượng:
    • Cài đặt mô phỏng kiểm chứng thuật toán phát hiện biên: Đánh giá độ chính xác (Precision) và độ hồi tưởng (Recall) trên các kịch bản mạng có mật độ nút và hình dạng vùng trống thay đổi.
    • Mô phỏng giao thức định tuyến GPOR và HCGR: So sánh định lượng với các giao thức đại diện (GPSR, BOUNDHOLE, ACGR, NCGR) theo các cấu hình:
      • Kích thước mạng thay đổi (số lượng nút tăng dần).
      • Số lượng luồng lưu lượng đồng thời thay đổi.
      • Số chặng được ghi nhận trong tiêu đề gói tin.
    • Các chỉ số đo lường định lượng: Tỷ lệ kéo dài độ dài đường đi (Path Stretch Ratio), trễ trung bình đầu cuối – đầu cuối (End-to-End Delay), tỷ lệ chuyển gói tin thành công (Packet Delivery Ratio), chi phí truyền thông / phụ tải tổng số phát tỏa (Communication Overhead / Transmissions), và tỷ lệ gói tin trùng lặp (Duplicate Packet Ratio).

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

Chương 1: Mở đầu

Chương 1 giới thiệu tổng quan về mạng cảm biến không dây, cấu trúc phần cứng của nút mạng (vi xử lý, bộ nhớ, bộ thu phát vô tuyến IEEE 802.15.4, nguồn pin, bảng cảm biến), và các lĩnh vực ứng dụng thực tế. Tác giả phân tích những thách thức trong thiết kế giao thức mạng do tài nguyên hạn chế, quy mô nút lớn, chu kỳ thức/ngủ và hiện tượng nút chết tạo vùng trống. Chương này định hình ba mục tiêu nghiên cứu, phạm vi giả thiết nghiên cứu (mạng 2D phẳng, tĩnh, anten đẳng hướng) và tóm tắt các đóng góp khoa học của luận án.

Chương 2: Tổng quan về định vị và định tuyến dựa trên thông tin vị trí

Chương 2 trình bày chi tiết bức tranh tổng quan về các hướng tiếp cận định vị và định tuyến trong WSN:

  • Khảo sát các kỹ thuật định vị dựa trên khoảng cách, định vị theo góc, co giãn đa chiều (MDS), mảng cao su và đồ thị Delaunay.
  • Khảo sát các kỹ thuật phát hiện biên dựa trên thống kê bậc nút và dựa trên topo mạng.
  • Phân tích chi tiết quy trình xử lý gói tin trong định tuyến vị trí kết hợp chuyển tiếp tham lam và định tuyến khôi phục (Bảng 2.3).
Quy trình xử lý gói tin tại mỗi nút cảm biến:
1. Nếu nút hiện tại là đích:
   Chuyển gói tin lên tầng giao vận.
2. Nếu nút hiện tại không phải là đích:
   2.1. Nếu gói tin ở chế độ tham lam:
        Áp dụng chuyển tiếp vị trí (GF).
        - Nếu chọn được láng giềng gần đích hơn: Chuyển tiếp gói tin.
        - Nếu không chọn được: Ghi vị trí nút vào tiêu đề (cực tiểu địa phương),
          chuyển sang chế độ khôi phục.
   2.2. Nếu gói tin ở chế độ khôi phục:
        - Nếu nút hiện tại gần đích hơn cực tiểu địa phương đã ghi:
          Chuyển về chế độ tham lam và tiếp tục chuyển tiếp tham lam.
        - Nếu không: Áp dụng định tuyến khôi phục (đi theo biên). 
          Nếu thất bại thì hủy gói tin.
  • Khảo sát sâu các kỹ thuật dịch vụ vị trí (DREAM, RLS, hàm băm chia ô), các kỹ thuật chuyển tiếp (GF, RPM, Compass, MFR, Inertia), các giải pháp tránh cực tiểu địa phương (Viewscope, Topological Awareness, mô hình hóa biên, tọa độ ảo) và các kỹ thuật khôi phục (Face routing, BOUNDHOLE với kỹ thuật quay sweeping, Hull tree).

Chương 3: Hỗ trợ định vị với phát hiện biên dựa trên kết nối

Chương 3 đề xuất thuật toán phát hiện biên cục bộ dựa trên kiểm tra tính chất tạo vành của đồ thị vùng lân cận 2 chặng ($2NG$).

1. Thuật toán kiểm tra tính chất tạo vành $\text{IsRing}(G_2)$: Mỗi nút $p$ chỉ cần trao đổi danh sách láng giềng 1 chặng ($MYNB$) với các nút láng giềng để xây dựng đồ thị $G_2 = (V_2, E_2)$ cho các nút cách $p$ đúng 2 chặng. Sau đó $p$ thực thi hàm $\text{IsRing}(G_2)$:

Thuật toán phát hiện biên cho nút p:
Đầu ra: nearBoundaries = true (nút gần biên), false (nút trong).

Khởi tạo: nearBoundaries = false; MYNB = {láng giềng của p}; V = {}; PE = {}
1. Phát tỏa MYNB tới các nút cách 2 chặng.
2. Nhận danh sách láng giềng từ các nút cách 2 chặng, thiết lập đồ thị G2 = <V, E>.
3. Gọi hàm IsRing(G2):
   - Nếu IsConnected(G2) = false: Trả về false.
   - Chọn một đỉnh bất kỳ t thuộc V2:
     + Đặt V20 = {t}
     + V21 = {v thuộc V2 | có cạnh <v, t>}
     + V22 = {v thuộc V2 | v khác t, v không thuộc V21, tồn tại u thuộc V21 có cạnh <u, v>}
     + Tạo đồ thị g2 từ tập đỉnh V22.
   - Nếu V22 rỗng HOẶC IsConnected(g2) = true: Trả về false.
   - Ngược lại:
     + Đặt V'2 = V2 - V20 - V21; tạo đồ thị G'2 từ tập đỉnh V'2.
     + Nếu IsConnected(G'2) = false: Trả về false.
     + Ngược lại: Trả về true.
4. Nếu IsRing(G2) = true thì nearBoundaries = false; ngược lại nearBoundaries = true.

2. Đánh giá và thử nghiệm: Thuật toán có tính phân tán hoàn toàn, chỉ sử dụng thông tin kết nối trong phạm vi 2 chặng, không cần phát tràn toàn mạng và không phụ thuộc vào việc lựa chọn điểm mốc. Kết quả thử nghiệm chứng minh thuật toán đạt độ chính xác và độ hồi tưởng cao ngay cả khi mật độ nút mạng thưa và phân bố không đồng đều.

Chương 4: Tối ưu hóa đường đi trong định tuyến dựa trên thông tin vị trí

Chương 4 trình bày thiết kế và đánh giá giao thức GPOR (Greedy with Path Optimization Routing).

1. Cơ chế hoạt động của GPOR:

  • Gói tin ban đầu đi qua vùng trống bằng cách kết hợp chuyển tiếp tham lam và đi men theo biên bằng kỹ thuật quay (sweeping).
  • Quá trình đi qua vùng lõm của biên ghi nhận danh sách một số nút đã đi qua vào tiêu đề gói tin.
  • Giao thức sinh các gói tin tạo đường tắt (Shortcut Creation - SC) gửi ngược lại để tạo phần tử định tuyến (Routing Element) tại các nút ở lối vào vùng lõm.
  • Phần tử định tuyến không chỉ phục vụ riêng cho một nút đích duy nhất mà xác định một vùng khả áp dụng (Applicable Area). Khi các luồng dữ liệu tiếp theo hướng tới bất kỳ đích nào nằm trong vùng khả áp dụng, nút sẽ sử dụng cơ chế chuyển tiếp có chỉ dẫn (Guided Forwarding) để chuyển gói tin trực tiếp qua đường tắt, tránh hoàn toàn vùng cực tiểu địa phương.

2. Kết quả mô phỏng và so sánh: Mô phỏng định lượng so sánh GPOR với các giao thức định tuyến vị trí truyền thống cho thấy:

  • Tỷ lệ kéo dài độ dài đường đi: GPOR rút ngắn đường đi đáng kể so với việc phải đi men theo toàn bộ biên vùng trống.
  • Trễ đầu cuối – đầu cuối: Giảm thiểu rõ rệt do số chặng truyền dẫn giảm và triệt tiêu hàng đợi tắc nghẽn tại các nút biên.
  • Tỷ lệ chuyển gói thành công: Duy trì ở mức cao khi số luồng lưu lượng đồng thời tăng lên.
  • Cân bằng tải: Giảm tải lưu lượng tập trung vào các nút biên, ngăn ngừa hiện tượng nút biên chết sớm làm mở rộng vùng trống.
  • Luận án cũng phân tích ảnh hưởng của tham số số chặng được ghi lại (recorded hop count) để xác định cấu hình tối ưu giữa kích thước tiêu đề gói và hiệu quả rút ngắn đường tắt.

Chương 5: Định tuyến dựa trên thông tin vị trí sử dụng cạnh tranh kết hợp

Chương 5 đề xuất giao thức HCGR (Hybrid Contention-Based Geographic Routing), loại bỏ hoàn toàn việc sử dụng gói tin chào hỏi (beaconless/hello-free).

1. Cơ chế cạnh tranh kết hợp (Hybrid Contention): HCGR kết hợp hai cơ chế cạnh tranh trong không gian:

  • Vùng cạnh tranh quyết liệt ($AA - \text{Aggressive Area}$): Nằm ở khu vực có bước tiến vị trí tốt nhất hướng về đích. Các nút trong vùng này cạnh tranh bằng cách phát trực tiếp gói dữ liệu sau một khoảng thời gian trễ được tính toán bằng hàm trễ tỷ lệ nghịch với khoảng cách tiến tới đích. Nếu một nút trong vùng $AA$ phát dữ liệu thành công, các nút khác nghe được sẽ tự động hủy bỏ cạnh tranh.
  • Vùng cạnh tranh không quyết liệt ($NA - \text{Non-aggressive Area}$): Dành cho các nút có vị trí kém ưu tiên hơn. Các nút này sử dụng gói tin điều khiển ngắn để cạnh tranh kênh truyền nếu vùng $AA$ không có nút nào phản hồi.
  • Khi chuyển sang chế độ khôi phục, HCGR áp dụng biến thể của kỹ thuật đi theo biên kết hợp cạnh tranh nhằm đảm bảo gói tin thoát khỏi cực tiểu địa phương mà không cần bảng láng giềng tĩnh.

2. Kết quả phân tích và mô phỏng: Luận án tiến hành mô phỏng so sánh HCGR với giao thức cạnh tranh quyết liệt thuần túy (ACGR) và cạnh tranh không quyết liệt thuần túy (NCGR):

  • Tỷ lệ chuyển gói thành công: HCGR đạt tỷ lệ xấp xỉ NCGR và cao hơn ACGR.
  • Phụ tải truyền thông: HCGR tiết kiệm đáng kể số lượng phát tỏa so với NCGR do phần lớn các trường hợp chuyển tiếp thành công ngay từ giai đoạn cạnh tranh quyết liệt.
  • Độ trễ đầu cuối – đầu cuối: Đạt mức thấp tương đương ACGR.
  • Tỷ lệ gói tin trùng lặp: Triệt tiêu phần lớn các gói tin trùng lặp vốn là nhược điểm nghiêm trọng của hình thức cạnh tranh quyết liệt thuần túy.

Kết quả và những đóng góp mới

Luận án đã đạt được ba đóng góp khoa học chính:

  1. Đóng góp về thuật toán phát hiện biên hỗ trợ định vị: Đề xuất thuật toán phát hiện biên dựa trên kết nối topo thông qua việc đánh giá tính chất tạo vành của đồ thị vùng lân cận 2 chặng ($2NG$). Thuật toán có tính chất phân tán cục bộ, chi phí tính toán và truyền thông thấp, hoạt động ổn định trên các mạng có mật độ nút thấp và phân bố không đồng đều mà không cần giả thiết vị trí ban đầu hay điểm mốc.
  2. Đóng góp về tối ưu hóa đường đi trong định tuyến vị trí (GPOR): Đề xuất giao thức GPOR kết hợp chuyển tiếp tham lam và đi theo biên, sử dụng cơ chế tạo đường tắt (Shortcut Creation) để rút ngắn đường truyền và đẩy luồng dữ liệu ra xa biên vùng trống. Giao thức mở rộng khái niệm vùng khả áp dụng (Applicable Area), cho phép một đường tắt được chia sẻ và tái sử dụng cho nhiều luồng lưu lượng hướng tới các nút đích khác nhau.
  3. Đóng góp về cơ chế cạnh tranh không dùng gói tin chào hỏi (HCGR): Đề xuất giao thức định tuyến HCGR tích hợp mô hình cạnh tranh kết hợp hai giai đoạn (quyết liệt $AA$ và không quyết liệt $NA$). Giao thức tối đa hóa tỷ lệ chuyển gói thành công, duy trì độ trễ thấp, giảm thiểu phụ tải truyền thông và khắc phục triệt để hiện tượng trùng lặp gói tin trong mạng cảm biến không dây.

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

Căn cứ theo nội dung và phạm vi nghiên cứu được tác giả trình bày:

  • Hạn chế: Các mô hình và giao thức trong luận án được thiết kế và kiểm chứng trên không gian mạng 2D phẳng, với giả thiết môi trường truyền sóng vô tuyến lý tưởng (hình tròn đẳng hướng, liên kết đối xứng) và các nút mạng ở trạng thái tĩnh.
  • Hướng nghiên cứu tiếp:
    • Mở rộng thuật toán phát hiện biên và các giao thức định tuyến cho không gian ba chiều (mạng cảm biến 3D).
    • Nghiên cứu cơ chế thích ứng của giao thức GPOR và HCGR trong điều kiện mạng có các nút cảm biến di động (mobile sensor nodes).
    • Khảo sát ảnh hưởng của các mô hình truyền sóng thực tế với vùng phủ sóng bất đối xứng và liên kết không thuần nhất (lossy/irregular radio links).

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với:

  • Nghiên cứu sinh và học viên cao học ngành Công nghệ Thông tin, Truyền dữ liệu và Mạng máy tính: Cung cấp tài liệu tổng quan hệ thống về lý thuyết định vị không dùng GPS, cấu trúc hình học topo rời rạc, và các kỹ thuật xử lý cực tiểu địa phương trong mạng không dây.
  • Giảng viên và nhà nghiên cứu trong lĩnh vực Mạng cảm biến không dây và IoT: Tham khảo thuật toán phân tán cục bộ $\text{IsRing}(G_2)$ trên đồ thị 2 chặng (Chương 3), cơ chế tối ưu hóa đường tắt phân tán GPOR (Chương 4), và thiết kế giao thức không gói tin định kỳ HCGR (Chương 5).
  • Kỹ sư thiết kế hệ thống nhúng và mạng truyền thông: Tham khảo các phụ lục về phương pháp ước lượng khoảng cách/góc (RSSI, TOA, TDOA, AOA) và cơ sở toán học cho bài toán định vị đa khoảng cách (Multilateration).

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

1. Tại sao các giao thức định tuyến dựa trên cấu trúc topo truyền thống không phù hợp cho mạng cảm biến không dây quy mô lớn?

Các giao thức định tuyến dựa trên cấu trúc mạng (như AODV, DSR, DSDV, OLSR) đòi hỏi mỗi nút phải duy trì bảng định tuyến chi tiết hoặc phải phát tràn các gói tin điều khiển để tìm đường khi có nhu cầu. Trong mạng cảm biến quy mô hàng ngàn nút với bộ nhớ nhỏ và nguồn pin giới hạn, việc duy trì bảng định tuyến vượt quá dung lượng lưu trữ của nút, đồng thời lượng gói tin điều khiển phát tràn sẽ gây nghẽn băng thông và làm cạn kiệt nhanh chóng năng lượng của toàn mạng.

2. Thuật toán phát hiện biên trong luận án dựa trên nguyên lý nào để nhận biết một nút nằm gần biên?

Thuật toán dựa trên nguyên lý hình học rời rạc của đồ thị vùng lân cận 2 chặng ($2NG$). Đối với một nút nằm sâu bên trong mạng, tập hợp các nút cách nó đúng 2 chặng và các liên kết giữa chúng sẽ tạo thành một cấu trúc "vành" khép kín bao quanh nút. Ngược lại, nếu nút nằm gần biên ngoài của mạng hoặc gần biên của vùng trống truyền thông, đồ thị $2NG$ của nó sẽ bị đứt đoạn thành một hoặc nhiều mảnh vỡ (không tạo thành vành). Bằng việc kiểm tra tính liên thông của các đồ thị con cảm ứng từ $2NG$ thông qua hàm $\text{IsRing}(G_2)$, nút tự xác định được trạng thái gần biên của mình mà chỉ cần trao đổi thông tin trong phạm vi 2 chặng.

3. Giao thức GPOR khắc phục hiện tượng quá tải và nghẽn mạng tại biên vùng trống bằng cách nào?

Khi gói tin đầu tiên đi men theo biên qua vùng lõm, GPOR ghi nhận thông tin đường đi và gửi gói tin tạo đường tắt ($SC$) về phía trước. Giao thức tạo ra phần tử định tuyến đại diện cho một vùng khả áp dụng rộng lớn. Các gói tin tiếp theo hướng tới các đích trong vùng này sẽ được chuyển tiếp có chỉ dẫn qua đường tắt xuyên qua mạng thay vì tiếp tục đi men theo mép biên. Việc này rút ngắn chiều dài đường đi, giảm độ trễ và chuyển lưu lượng ra xa biên, giúp bảo vệ năng lượng cho các nút biên và tránh hiện tượng vùng trống bị khoét rộng.

4. Cơ chế cạnh tranh kết hợp trong giao thức HCGR mang lại lợi ích gì so với các hình thức cạnh tranh đơn lẻ?

Hình thức cạnh tranh quyết liệt thuần túy ($ACGR$) có ưu điểm trễ thấp nhưng dễ gây ra xung đột và tạo nhiều gói tin trùng lặp khi nhiều nút cùng phản hồi. Ngược lại, cạnh tranh không quyết liệt ($NCGR$) dùng gói điều khiển nên triệt tiêu được gói trùng lặp nhưng lại làm tăng trễ và tiêu tốn phụ tải. Cơ chế cạnh tranh kết hợp của HCGR ưu tiên phân vùng cạnh tranh quyết liệt ($AA$) cho các nút có vị trí tối ưu để chuyển tiếp dữ liệu ngay lập tức với độ trễ tối thiểu; nếu vùng $AA$ không có nút, giao thức mới kích hoạt vùng cạnh tranh không quyết liệt ($NA$). Sự phối hợp này giúp HCGR đạt tỷ lệ chuyển gói thành công cao, giữ trễ ở mức thấp và loại bỏ phần lớn gói tin trùng lặp.

5. Sự khác biệt cơ bản giữa định vị dựa trên khoảng (range-based) và định vị dựa trên kết nối (connectivity-based) trong WSN là gì?

Định vị dựa trên khoảng đòi hỏi phần cứng phụ trợ để ước lượng khoảng cách hoặc góc giữa các nút (như đo cường độ tín hiệu, thời gian truyền sóng) và cần mật độ điểm neo có tọa độ GPS phân bố dày. Phương pháp này nhạy cảm với nhiễu môi trường và tốn kém chi phí. Trong khi đó, định vị dựa trên kết nối chỉ sử dụng thông tin liên kết topo mạng (nút nào kết nối với nút nào), không cần phần cứng đo đạc phụ trợ và không cần điểm neo, do đó có chi phí thấp và phù hợp hơn với đặc tính tài nguyên hạn chế của mạng cảm biến không dây.

Kết luận

Luận án của tác giả Lê Đình Thanh đã giải quyết có hệ thống hai bài toán then chốt trong mạng cảm biến không dây: hỗ trợ định vị thông qua phát hiện biên mạng và nâng cao hiệu năng định tuyến đơn phát dựa trên thông tin vị trí. Ba đóng góp trọng tâm gồm thuật toán phát hiện biên cục bộ trên đồ thị lân cận 2 chặng $2NG$, giao thức tối ưu hóa đường tắt phân tán đa đích GPOR, và giao thức định tuyến cạnh tranh kết hợp không dùng gói tin chào hỏi HCGR. Các giải pháp đề xuất đều đạt hiệu quả truyền thông, tiết kiệm năng lượng nút và giải quyết triệt để các hạn chế về đường đi vòng, quá tải biên và xung đột gói tin trong WSN.