Giảm Độ Trễ End-to-End và Tổng Năng Lượng Tiêu Thụ Trong Các Mạng Cảm Biến Không Dây

Luận án tiến sĩ nghiên cứu giảm độ trễ end to end và tối ưu năng lượng trong mạng cảm biến không dây, góp phần nâng cao hiệu suất hệ thống.

• Tác giả: Huỳnh Trọng Thừa
• Người hướng dẫn: PGS. Trần Công Hùng
• Trường học: Đại học Bách Khoa, Đại học Quốc Gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Giảm Độ Trễ End-to-End và Tiêu Thụ Năng Lượng Trong Mạng Cảm Biến Không Dây
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2017
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• TÓM TẮT LUẬN ÁN
• ABSTRACT
• LỜI CÁM ƠN
• DANH MỤC CÁC HÌNH ẢNH
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC CÁC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu của đề tài
• 1.3. Đối tượng và phạm vi nghiên cứu của đề tài
• 1.4. Phương pháp nghiên cứu
• 1.5. Các đóng góp chính của luận án
• 1.6. Cấu trúc luận án
• 2. CHƯƠNG 2: TỔNG QUAN
• 2.1. Tổng quan về mạng cảm biến không dây
• 2.1.1. Các thành phần của một nút cảm biến
• 2.1.2. Chồng giao thức trong mạng cảm biến không dây
• 2.1.3. Các nhân tố ảnh hưởng đến việc thiết kế mạng cảm biến không dây
• 2.1.4. Một số ứng dụng của mạng cảm biến không dây
• 2.1.5. Thử thách và vấn đề mở trong định tuyến cho các mạng cảm biến không dây
• 2.2. Tổng quan về tình hình nghiên cứu
• 2.2.1. Các nghiên cứu nhằm cân bằng giữa độ trễ và năng lượng tiêu thụ ở lớp truy cập môi trường truyền
• 2.2.2. Các nghiên cứu nhằm tiết kiệm năng lượng tiêu thụ và giảm độ trễ end-to-end ở lớp mạng
• 3. CHƯƠNG 3: GIẢI THUẬT PHÂN CỤM HIỆU QUẢ NĂNG LƯỢNG VÀ ĐỘ TRỄ - TED
• 3.1. Mô hình mạng
• 3.2. Mô hình năng lượng
• 3.3. Mô hình độ trễ
• 3.4. Giải thuật phân cụm cân bằng năng lượng tiêu thụ và độ trễ - TED
• 3.5. Phân tích độ phức tạp của giải thuật phân cụm TED
• 3.6. Đánh giá hiệu quả giải thuật phân cụm
• 4. CHƯƠNG 4: GIẢI THUẬT ĐỊNH TUYẾN CÂN BẰNG NĂNG LƯỢNG TIÊU THỤ VÀ ĐỘ TRỄ ĐẦU CUỐI - DEM
• 4.1. Tính chi phí đường đi ban đầu
• 4.2. Cập nhật chi phí đường đi
• 4.3. Truyền dữ liệu
• 4.4. Đánh giá hiệu quả giải thuật DEM
• 5. CHƯƠNG 5: GIẢI THUẬT ĐỊNH TUYẾN HIỆU QUẢ NĂNG LƯỢNG VỚI K ĐƯỜNG NGẮN NHẤT ĐẢM BẢO ĐỘ TRỄ ĐẦU CUỐI - DCEM
• 5.1. Tính chi phí liên kết và chi phí đường đi
• 5.2. Giải thuật định tuyến đa chặng
• 5.3. Phân tích tính hội tụ và độ phức tạp của giải thuật DCEM
• 5.4. Đánh giá hiệu quả giải thuật DCEM
• 6. CHƯƠNG 6: GIẢI THUẬT ĐỊNH TUYẾN PHÂN TÁN HIỆU QUẢ NĂNG LƯỢNG RÀNG BUỘC ĐỘ TRỄ ĐẦU CUỐI - DCEER
• 6.1. Giải thuật khám phá đường đi
• 6.2. Phân tích tính hội tụ và độ phức tạp của giải thuật DCEER
• 6.3. Đánh giá hiệu quả giải thuật DCEER
• 7. CHƯƠNG 7: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 7.1. Những điểm mới của luận án
• 7.2. Đánh giá các phương pháp đề xuất
• 7.3. Cân bằng hai yếu tố độ trễ và năng lượng tiêu thụ
• 7.4. Khả năng áp dụng trong thực tế
• 7.5. Hướng mở rộng nghiên cứu
• DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Mạng Cảm Biến Không Dây Tổng quan về độ trễ năng lượng

Mạng cảm biến không dây (WSN) đang ngày càng trở nên phổ biến nhờ những tiến bộ vượt bậc trong công nghệ vi điều khiển và truyền thông không dây. Ứng dụng của mạng lưới cảm biến trải rộng trên nhiều lĩnh vực, từ giám sát môi trường đến y tế thông minh. Tuy nhiên, vấn đề tiêu thụ năng lượng luôn là một thách thức lớn, đặc biệt khi số lượng nút cảm biến tăng lên. Việc giảm độ trễ end-to-end cũng quan trọng, đặc biệt trong các ứng dụng yêu cầu thời gian phản hồi nhanh. Bài viết này sẽ đi sâu vào các phương pháp giảm độ trễ end-to-end và tiết kiệm năng lượng trong mạng cảm biến không dây (WSN), tập trung vào kỹ thuật phân cụm và định tuyến đa chặng.

1.1. Kiến trúc Mạng Cảm Biến Không Dây WSN cơ bản

Một mạng cảm biến không dây (WSN) điển hình bao gồm nhiều nút cảm biến nhỏ bé, được triển khai rải rác trong một khu vực nhất định. Các nút này thu thập dữ liệu môi trường (ví dụ: nhiệt độ, độ ẩm, áp suất) và truyền dữ liệu về một trạm gốc (sink). Trạm gốc này sau đó xử lý và phân tích dữ liệu. Các nút cảm biến thường có nguồn năng lượng hạn chế (pin), do đó, quản lý năng lượng là một yếu tố thiết yếu. Theo tài liệu nghiên cứu, "Sự quan tâm chủ yếu trong thiết kế và triển khai những ứng dụng mạng cảm biến không dây nhƣ thế chính là vấn đề tiêu thụ năng lƣợng."

1.2. Các yếu tố ảnh hưởng đến Độ Trễ End to End

Độ trễ end-to-end trong mạng cảm biến không dây (WSN) bị ảnh hưởng bởi nhiều yếu tố, bao gồm: độ trễ truyền, độ trễ hàng đợi, độ trễ xử lý và độ trễ lan truyền. Giao thức truyền thông được sử dụng cũng có tác động đáng kể đến độ trễ. Việc lựa chọn thuật toán định tuyến tối ưu là vô cùng quan trọng để giảm thiểu độ trễ. Số lượng hop trên đường truyền dữ liệu từ nút cảm biến đến trạm gốc cũng ảnh hưởng trực tiếp đến độ trễ. "Số lƣợng chặng tỷ lệ thuận với độ trễ truyền thông".

II. Thách Thức Năng lượng Độ trễ trong Mạng Cảm Biến WSN

Việc đồng thời tối ưu hóa tiêu thụ năng lượng và độ trễ end-to-end trong mạng cảm biến không dây (WSN) là một thách thức lớn. Các giải pháp tiết kiệm năng lượng thường dẫn đến tăng độ trễ, và ngược lại. Ví dụ, việc sử dụng các giao thức ngủ/thức để giảm tiêu thụ năng lượng có thể làm tăng độ trễ. Do đó, cần có các giải pháp cân bằng giữa hai yếu tố này. Các giải pháp cần phải tính đến các ràng buộc về chất lượng dịch vụ (QoS) của ứng dụng.

2.1. Mối quan hệ giữa Tiêu Thụ Năng Lượng và Độ Trễ

Mối quan hệ giữa tiêu thụ năng lượng và độ trễ end-to-end thường là nghịch đảo. Việc giảm tiêu thụ năng lượng bằng cách giảm số lần truyền dữ liệu (ví dụ, sử dụng thuật toán tổng hợp dữ liệu) có thể làm tăng độ trễ. Ngược lại, việc giảm độ trễ bằng cách tăng tần suất truyền dữ liệu có thể làm tăng tiêu thụ năng lượng. Cần có một sự đánh đổi cẩn thận để đạt được hiệu suất tối ưu cho ứng dụng cụ thể. "Việc giảm số chặng trên đƣờng đi từ các nút cảm biến nguồn đến nút gốc có thể làm giảm độ trễ end-to- end nhƣng lại làm tăng tổng năng lƣợng tiêu thụ".

2.2. Tầm quan trọng của Giao Thức MAC trong WSN

Giao thức MAC đóng vai trò quan trọng trong việc quản lý truy cập kênh truyền và ảnh hưởng trực tiếp đến cả tiêu thụ năng lượng và độ trễ end-to-end. Các giao thức MAC theo lịch trình (TDMA) có thể đảm bảo độ trễ thấp nhưng có thể lãng phí năng lượng khi không có dữ liệu để truyền. Các giao thức MAC tranh chấp (CSMA/CA) linh hoạt hơn nhưng có thể gây ra độ trễ cao do xung đột. Việc lựa chọn giao thức MAC phù hợp là rất quan trọng để đạt được hiệu suất mong muốn.

2.3. Ảnh hưởng của Thuật Toán Định Tuyến tới Độ Trễ và Năng Lượng

Thuật toán định tuyến ảnh hưởng lớn đến độ trễ và tiêu thụ năng lượng. Các thuật toán định tuyến ngắn nhất có thể giảm độ trễ nhưng có thể không phải là hiệu quả nhất về năng lượng. Các thuật toán định tuyến dựa trên năng lượng có thể kéo dài thời gian tồn tại mạng (Network Lifetime) nhưng có thể làm tăng độ trễ. Các thuật toán định tuyến đa đường có thể cung cấp sự cân bằng tốt hơn giữa hai yếu tố này. "Do vậy, việc phân bố phù hợp các nút vào trong các cụm và chọn đƣờng đi với số lƣợng chặng tối ƣu để cân bằng cả hai yếu tố năng lƣợng tiêu thụ và độ trễ end-to-end là một vấn đề khó."

III. Giải Pháp Phân Cụm Giảm Độ Trễ và Tiết Kiệm Năng Lượng

Kỹ thuật phân cụm là một phương pháp hiệu quả để giảm tiêu thụ năng lượng trong mạng cảm biến không dây (WSN). Trong kỹ thuật này, các nút cảm biến được nhóm thành các cụm, và mỗi cụm có một nút trưởng cụm (cluster head) đảm nhận vai trò thu thập và tổng hợp dữ liệu từ các nút thành viên. Nút trưởng cụm sau đó truyền dữ liệu tổng hợp về trạm gốc. Việc phân cụm giúp giảm số lượng truyền dữ liệu trực tiếp đến trạm gốc, do đó giảm tiêu thụ năng lượng. Đồng thời, kỹ thuật phân cụm có thể giảm độ trễ bằng cách định tuyến dữ liệu qua các nút trưởng cụm gần trạm gốc hơn.

3.1. Thuật toán Phân Cụm LEACH Ưu và Nhược điểm

LEACH (Low-Energy Adaptive Clustering Hierarchy) là một trong những thuật toán phân cụm đầu tiên và phổ biến nhất. LEACH chọn các nút trưởng cụm một cách ngẫu nhiên, giúp phân phối tiêu thụ năng lượng đều cho các nút trong mạng. Tuy nhiên, LEACH không xem xét độ trễ và có thể không hiệu quả trong các mạng có mật độ nút không đồng đều. Tham khảo thêm các giải thuật phân cụm khác như HEED, DEEC.

3.2. Phân Cụm dựa trên Năng Lượng và Độ Trễ TED Algorithm

Một số thuật toán phân cụm tiên tiến hơn xem xét cả năng lượng và độ trễ trong quá trình chọn nút trưởng cụm. TED (Tradeoff Energy and Delay) là một ví dụ, thuật toán này sử dụng một hàm chi phí kết hợp cả năng lượng còn lại của nút và khoảng cách đến trạm gốc. Điều này giúp chọn các nút trưởng cụm có khả năng truyền dữ liệu về trạm gốc một cách hiệu quả về cả năng lượng và độ trễ. Theo tài liệu, "Luận án đề xuất mô hình phân cụm dựa trên mức năng lƣợng còn lại của các nút cảm biến và độ trễ end-to-end."

3.3. Cải tiến Thuật toán TED Cân bằng Năng Lượng và Độ Trễ

Nghiên cứu tiếp tục cải tiến thuật toán TED bằng cách tinh chỉnh hàm chi phí và bổ sung các cơ chế điều chỉnh để thích ứng với các điều kiện mạng khác nhau. Ví dụ, một số giải pháp sử dụng các kỹ thuật học máy (Machine Learning) để dự đoán tiêu thụ năng lượng và độ trễ trong tương lai, từ đó đưa ra các quyết định phân cụm tốt hơn. "Cùng với việc đề xuất một giải thuật phân cụm cân bằng năng lƣợng tiêu thụ và độ trễ end-to-end, luận án cũng thiết kế một hàm chi phí tổng hợp dựa trên mức năng lƣợng còn lại của mỗi nút cảm biến và khoảng cách giữa chúng nhằm chọn ra các nút trƣởng cụm tối ƣu để phân phối dữ liệu đến trạm gốc một cách hiệu quả nhất."

IV. Định Tuyến Đa Chặng Tối Ưu Đường Truyền trong Mạng WSN

Định tuyến đa chặng là một kỹ thuật quan trọng để giảm tiêu thụ năng lượng và độ trễ end-to-end trong mạng cảm biến không dây (WSN). Thay vì truyền dữ liệu trực tiếp đến trạm gốc, các nút cảm biến truyền dữ liệu qua nhiều nút trung gian (hop). Điều này giúp giảm khoảng cách truyền, do đó giảm tiêu thụ năng lượng. Tuy nhiên, định tuyến đa chặng có thể làm tăng độ trễ do phải truyền qua nhiều nút. Việc lựa chọn đường đi tối ưu là rất quan trọng để cân bằng giữa năng lượng và độ trễ.

4.1. Các Thuật Toán Định Tuyến Đa Chặng Tiêu Biểu

Có nhiều thuật toán định tuyến đa chặng khác nhau, mỗi thuật toán có những ưu và nhược điểm riêng. AODV (Ad-hoc On-demand Vector Routing) là một thuật toán định tuyến theo yêu cầu, chỉ thiết lập đường đi khi cần thiết. DSR (Dynamic Source Routing) là một thuật toán định tuyến theo nguồn, mỗi gói tin mang thông tin về đường đi. Các thuật toán này có thể không hiệu quả trong các mạng có mật độ nút cao do overhead định tuyến lớn.

4.2. Định Tuyến Cân Bằng Năng Lượng và Độ Trễ DEM

Một số thuật toán định tuyến tiên tiến hơn xem xét cả năng lượng và độ trễ trong quá trình lựa chọn đường đi. DEM (Delay Energy Multi-hop) là một ví dụ, thuật toán này sử dụng một hàm chi phí kết hợp cả năng lượng còn lại của nút và độ trễ của liên kết. Điều này giúp chọn các đường đi có hiệu suất tốt về cả năng lượng và độ trễ. Theo tài liệu, "Luận án đề xuất một hàm chi phí kết hợp hai yếu tố năng lƣợng tiêu thụ tại mỗi nút cảm biến và độ trễ liên kết giữa các nút cảm biến lân cận nhau."

4.3. Định Tuyến Đa Đường K Ngắn Nhất DCEM

DCEM là một thuật toán định tuyến đa đường, tìm kiếm k đường đi ngắn nhất từ nút nguồn đến trạm gốc và chọn đường đi có hiệu suất tốt nhất về năng lượng và độ trễ. DCEM cung cấp sự cân bằng tốt hơn giữa năng lượng và độ trễ so với các thuật toán định tuyến đơn đường. "Luận án đề xuất một hàm chi phí chỉ dựa vào năng lƣợng còn lại của mỗi nút cảm biến và một giải thuật định tuyến k đƣờng ngắn nhất theo tổng năng lƣợng tiêu thụ đảm bảo ràng buộc độ trễ end-to-end của ứng dụng."

V. Ứng Dụng Kết Quả Nghiên Cứu về Giảm Độ Trễ Năng Lượng

Các giải pháp giảm độ trễ end-to-end và tiết kiệm năng lượng trong mạng cảm biến không dây (WSN) đã được áp dụng trong nhiều ứng dụng thực tế. Ví dụ, trong hệ thống giám sát cháy rừng, việc giảm độ trễ là rất quan trọng để phát hiện và ứng phó nhanh chóng với các đám cháy. Trong hệ thống giám sát núi lửa, việc tiết kiệm năng lượng là quan trọng để đảm bảo hoạt động liên tục của mạng trong thời gian dài. Các kết quả nghiên cứu cho thấy rằng các giải pháp kết hợp phân cụm và định tuyến đa chặng có thể đạt được hiệu suất tốt về cả năng lượng và độ trễ.

5.1. Giám Sát Môi Trường Ứng dụng trong thực tế

Mạng cảm biến không dây (WSN) được sử dụng rộng rãi trong giám sát môi trường, ví dụ như giám sát chất lượng không khí, chất lượng nước, và các điều kiện thời tiết. Việc giảm tiêu thụ năng lượng là rất quan trọng để đảm bảo hoạt động liên tục của mạng trong các môi trường khắc nghiệt. Việc giảm độ trễ cũng quan trọng trong các ứng dụng yêu cầu cảnh báo sớm về các sự kiện bất thường.

5.2. Ứng dụng trong Hệ Thống Giám Sát Y Tế

Mạng cảm biến không dây (WSN) đang được sử dụng ngày càng nhiều trong hệ thống giám sát y tế, ví dụ như giám sát nhịp tim, huyết áp, và các chỉ số sức khỏe khác của bệnh nhân. Việc giảm độ trễ là rất quan trọng để phát hiện và ứng phó nhanh chóng với các tình huống khẩn cấp. Việc tiết kiệm năng lượng cũng quan trọng để đảm bảo thời gian sử dụng pin lâu dài cho các thiết bị đeo.

5.3. So sánh hiệu suất giữa các giải pháp Định tuyến

Nghiên cứu so sánh hiệu suất của các giải pháp định tuyến khác nhau cho thấy rằng các giải pháp định tuyến cân bằng năng lượng và độ trễ (ví dụ, DEM, DCEM) có hiệu suất tốt hơn so với các giải pháp chỉ tập trung vào một yếu tố. Các giải pháp định tuyến đa đường cũng cho thấy hiệu suất tốt hơn so với các giải pháp định tuyến đơn đường trong các mạng có mật độ nút cao. Theo luận án, "Kết quả mô phỏng cho thấy giải thuật này tạo sự cân bằng cho cả năng lƣợng tiêu thụ và độ trễ end-to-end."

VI. Kết Luận Hướng Nghiên Cứu Tương Lai về Tiết Kiệm Năng Lượng

Việc giảm độ trễ end-to-end và tiết kiệm năng lượng trong mạng cảm biến không dây (WSN) vẫn là một lĩnh vực nghiên cứu sôi động. Các hướng nghiên cứu tương lai bao gồm việc phát triển các thuật toán thông minh hơn, sử dụng các kỹ thuật trí tuệ nhân tạo (AI) và học máy (Machine Learning) để tối ưu hóa hiệu suất mạng. Việc khai thác năng lượng tái tạo (ví dụ, năng lượng mặt trời, năng lượng gió) cũng là một hướng đi đầy hứa hẹn để kéo dài thời gian tồn tại mạng (Network Lifetime).

6.1. Điện Toán Biên Edge Computing trong WSN

Điện toán biên (Edge Computing) đang nổi lên như một giải pháp tiềm năng để giảm độ trễ và tiêu thụ năng lượng trong mạng cảm biến không dây (WSN). Bằng cách xử lý dữ liệu gần với nguồn (tức là tại các nút cảm biến), điện toán biên có thể giảm lượng dữ liệu cần truyền về trạm gốc, do đó giảm tiêu thụ năng lượng và độ trễ. Áp dụng các kỹ thuật Data fusion và Data aggregation.

6.2. Ứng Dụng Học Máy Machine Learning trong WSN

Học máy (Machine Learning) có thể được sử dụng để dự đoán tiêu thụ năng lượng, độ trễ, và các điều kiện mạng khác nhau, từ đó đưa ra các quyết định tối ưu hóa mạng. Ví dụ, học máy có thể được sử dụng để điều chỉnh các tham số của thuật toán phân cụm và định tuyến một cách động, thích ứng với các thay đổi trong môi trường mạng. Các mô hình học máy giúp dự đoán và giảm thiểu rủi ro. Các phương pháp Trí tuệ nhân tạo (AI) cũng là một hướng đi tiềm năng.

6.3. Năng Lượng Tái Tạo Renewable energy cho Mạng WSN

Việc khai thác năng lượng tái tạo (ví dụ, năng lượng mặt trời, năng lượng gió) có thể giúp kéo dài thời gian tồn tại mạng (Network Lifetime) của mạng cảm biến không dây (WSN). Các nút cảm biến có thể được trang bị các tấm pin mặt trời hoặc các thiết bị thu năng lượng gió để thu thập năng lượng từ môi trường. Việc sử dụng năng lượng tái tạo giúp giảm sự phụ thuộc vào pin, do đó giảm chi phí và tăng tính bền vững của mạng. Tập trung vào Harvesting energy.

Nội dung chính

Tổng quan về luận án

Trong bối cảnh bùng nổ của công nghệ vi điều khiển và truyền thông vô tuyến, mạng cảm biến không dây (Wireless Sensor Networks - WSN) đã trở thành hạ tầng cốt lõi cho các hệ thống giám sát môi trường, cảnh báo thiên tai và Internet vạn vật (IoT). Tuy nhiên, các nút cảm biến luôn bị ràng buộc nghiêm ngặt bởi nguồn năng lượng pin hữu hạn, năng lực tính toán khiêm tốn và bộ nhớ hạn chế. Nghịch lý cốt lõi trong thiết kế giao thức mạng WSN nằm ở sự đánh đổi mang tính đối kháng (trade-off) giữa hai mục tiêu: tối ưu hóa năng lượng tiêu thụ để kéo dài thời gian sống của mạng (network lifetime) và giảm thiểu độ trễ đầu cuối (end-to-end delay) để đáp ứng tính thời gian thực cho các ứng dụng cảnh báo khẩn cấp.

Khoảng trống nghiên cứu (research gap) được xác định rõ nét trong y văn: Các giao thức kinh điển như LEACH (Heinzelman et al., 2000, 2002) giả định mô hình truyền thông một chặng (single-hop) trực tiếp từ nút trưởng cụm (Cluster Head - CH) đến trạm gốc (Sink), dẫn đến cạn kiệt năng lượng nhanh chóng đối với các nút ở xa và gây mất cân bằng năng lượng nghiêm trọng. Ngược lại, các mô hình truyền thông đa chặng (multi-hop) như HEED (Younis & Fahmy, 2004) hay C2E2S giúp bảo toàn năng lượng nhưng lại làm gia tăng độ trễ tích lũy và bùng nổ khối lượng thông điệp điều khiển (overhead).

Luận án "Giảm độ trễ end-to-end và tổng năng lượng tiêu thụ trong các mạng cảm biến không dây" của tác giả Huỳnh Trọng Thưa (Chuyên ngành Khoa học máy tính, Trường Đại học Bách khoa - ĐHQG TP. Hồ Chí Minh, 2017) đã giải quyết triệt để bài toán tối ưu hóa đa mục tiêu này thông qua 4 câu hỏi nghiên cứu và giả thuyết khoa học:

1. RQ1 / H1: Làm thế nào để thiết lập thuật toán phân cụm cân bằng giữa năng lượng còn lại và khoảng cách vật lý với độ phức tạp tính toán tuyến tính $O(n)$?
2. RQ2 / H2: Làm thế nào để xây dựng hàm chi phí liên kết đa mục tiêu kết hợp năng lượng và độ trễ cục bộ nhằm tìm đường truyền tối ưu?
3. RQ3 / H3: Việc áp dụng thuật toán tìm $k$-đường ngắn nhất có ràng buộc độ trễ đầu cuối có thể kéo dài thời gian sống của mạng trong thời gian đa thức hay không?
4. RQ4 / H4: Cơ chế định tuyến phân tán dựa trên vectơ khoảng cách cục bộ có thể giảm thiểu overhead điều khiển và hội tụ nhanh trong mạng quy mô lớn hay không?

Nghiên cứu được thiết lập trên không gian mô phỏng chuẩn xác $100\text{m} \times 100\text{m}$ với quy mô $N = 100$ nút cảm biến, năng lượng ban đầu $1\text{ Joule/nút}$, phối hợp cùng giao thức lớp truy cập môi trường T-MAC, tạo nên đóng góp đột phá trong việc kéo dài vòng đời mạng và đảm bảo ràng buộc độ trễ thời gian thực.

Literature Review và Positioning

Khảo sát y văn quốc tế cho thấy hai trường phái tiếp cận đối nghịch trong việc tối ưu hóa hiệu năng WSN:

1. Trường phái ưu tiên năng lượng (Energy-centric paradigm): Tiêu biểu là LEACH (Heinzelman et al., 2000) và HEED (Younis & Fahmy, 2004). LEACH thực hiện quay vòng ngẫu nhiên vai trò trưởng cụm nhưng áp dụng truyền thông trực tiếp một chặng tới Sink, khiến năng lượng suy giảm phi tuyến theo lũy thừa bậc 4 ($d^4$) ở khoảng cách xa. HEED phát triển cơ chế phân cụm phân tán dựa trên năng lượng dư và mật độ nút, song việc sử dụng thông tin đệm tĩnh (cached information) trong định tuyến đa chặng dẫn đến hiện tượng mâu thuẫn đường đi và nghẽn cục bộ.
2. Trường phái ưu tiên chất lượng dịch vụ và độ trễ (Delay/QoS-centric paradigm): Đại diện là SPEED (He et al., 2003), MMSPEED (Felemban et al., 2006) và EAQoS (Akkaya & Younis, 2005). SPEED sử dụng thuật toán chuyển tiếp địa lý phi tiền định (SNGF) kết hợp vòng phản hồi cục bộ (NFL) để duy trì tốc độ truyền dẫn gói tin, nhưng lại tiêu tốn năng lượng truyền thông rất lớn do không xét đến mức năng lượng dư của từng nút. EAQoS mở rộng thuật toán Dijkstra có ràng buộc độ trễ nhưng đòi hỏi mỗi nút phải nắm bắt trạng thái toàn mạng (global state), sinh ra overhead khổng lồ và không khả thi khi mở rộng quy mô.

Bên cạnh đó, các nghiên cứu đa đường như SAR (Sohrabi et al., 2000) và DEAR phải duy trì trạng thái bảng định tuyến phức tạp, trong khi các giải pháp như RPAR (Chipara et al., 2006) hay EDAL (2015) gặp khó khăn khi mạng xảy ra tắc nghẽn hoặc xuất hiện lỗ hổng topo (routing holes).

Luận án định vị nghiên cứu tại điểm giao thoa giữa kỹ thuật phân cụm phân tán và định tuyến đa chặng thích ứng. Bằng cách mô hình hóa toán học chính xác độ trễ liên kết theo lý thuyết hàng đợi $M/M/1$ và tích hợp tham số điều khiển trọng số thích nghi ($\alpha, \beta$), công trình đã khắc phục triệt để các nhược điểm của LEACH và HEED, đồng thời duy trì độ phức tạp tính toán thấp hơn hẳn so với các giải thuật Dijkstra cải tiến của EAQoS hay cơ chế phân tán của MMSPEED.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mở rộng và làm phong phú hệ thống lý thuyết định tuyến và phân cụm trong WSN thông qua 4 đóng góp cốt lõi:

1. Mở rộng mô hình tiêu hao năng lượng vô tuyến của Heinzelman et al.: Tích hợp chi phí tiêu thụ năng lượng thu/phát với năng lượng tổng hợp dữ liệu ($E_F(l, m) = m \times E_{fuse} \times l$) tại nút trưởng cụm, thiết lập trạng thái cân bằng giữa truyền thông đa chặng và nén dữ liệu.
2. Hệ thống hóa mô hình độ trễ liên kết toán học: Xây dựng công thức tổng quát cho độ trễ liên kết $D_l(i, j) = d_Q + d_T + d_P$, trong đó độ trễ hàng đợi $d_Q = \frac{1}{\mu - \lambda}$ được giải quyết thông qua lý thuyết hàng đợi $M/M/1$, độ trễ truyền gói $d_T = \frac{l}{\psi}$ và độ trễ lan truyền $d_P = \frac{d_{ij}}{\gamma}$.
3. Đề xuất chỉ số chi phí tổng hợp TED (Tradeoff for Energy and Delay): Xây dựng hàm tương quan: $$TED_i = \alpha \frac{E_i}{E_{total}} + \beta \frac{1}{dis}$$ cho phép chuyển dịch linh hoạt trọng tâm mạng từ tiết kiệm năng lượng ($\alpha = 1, \beta = 0$) sang ưu tiên giảm độ trễ ($\alpha = 0, \beta = 1$).
4. Chuyển dịch mô hình định tuyến đa mục tiêu sang bài toán tối ưu đơn mục tiêu có ràng buộc: Luận án chứng minh rằng việc quy hoạch bài toán tìm đường truyền thành bài toán tối thiểu hóa tổng năng lượng tiêu thụ dưới ràng buộc độ trễ đầu cuối $D_{ete}(x, s) \le D_{constraint}$ giúp giảm không gian tìm kiếm từ cấp số mũ về thời gian đa thức.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp chặt chẽ 3 nền tảng lý thuyết: Lý thuyết mạng cảm biến phân cấp (Hierarchical WSN Theory), Lý thuyết hàng đợi viễn thông (Queuing Theory) và Lý thuyết đồ thị tối ưu (Graph Optimization Theory). Luận án đề xuất cấu trúc 4 giải thuật liên hoàn:

• Giải thuật 1 - Phân cụm TED: Thiết lập cụm dựa trên năng lượng dư và khoảng cách tới Sink với độ phức tạp $O(n)$.
• Giải thuật 2 - Định tuyến DEM (Delay Energy Multi-hop): Cập nhật hàm chi phí đường đi kết hợp năng lượng nút và độ trễ liên kết lân cận.
• Giải thuật 3 - Định tuyến DCEM (Delay-Constrained Energy Multi-hop): Khai phá $k$-đường ngắn nhất đảm bảo ngưỡng trễ khắt khe của ứng dụng.
• Giải thuật 4 - Định tuyến phân tán DCEER (Delay Constrained Energy Efficient Routing): Cơ chế định tuyến thích nghi dựa trên thông tin vectơ khoảng cách cục bộ, triệt tiêu overhead toàn cục.

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

Thiết kế nghiên cứu

Luận án tuân thủ thế giới quan thực chứng (Positivism) kết hợp phương pháp luận diễn dịch toán học (Deductive Mathematical Modeling) và mô phỏng thực nghiệm đối chứng nghiêm ngặt. Thiết kế phân tầng được định nghĩa rõ ràng:

• Cấp độ nút (Node-level): Xử lý tính toán cục bộ, định thời gian chờ $\tau = \frac{1}{E}$ và $\omega = \frac{1}{TED_i}$ để tự ứng cử vai trò trưởng cụm.
• Cấp độ cụm (Cluster-level): Tổng hợp dữ liệu từ các nút thành viên thông qua lập lịch phân chia thời gian TDMA.
• Cấp độ liên cụm (Inter-cluster level): Định tuyến đa chặng giữa các CH hướng về trạm gốc Sink theo đường truyền tối ưu.

Quy trình nghiên cứu rigorous

Quy trình thực nghiệm được chuẩn hóa qua các giao thức nghiêm ngặt:

1. Ước lượng khoảng cách bằng chỉ số RSSI: Nút cảm biến tính toán khoảng cách tới Sink ($dtoSink$) thông qua suy hao tín hiệu log-distance: $RSSI(dBm) = -10n \log_{10}(dtoSink) + A$, với tham số không gian tự do $n = 2$ và độ nhạy thu chuẩn tại khoảng cách 1m là $A = -95\text{ dBm}$.
2. Giao thức trao đổi thông điệp: Chuẩn hóa 5 loại gói tin điều khiển bao gồm: Gói báo hiệu Sink ($BEA$), Gói quảng bá ứng viên ($ADV$), Gói yêu cầu gia nhập cụm ($JCR$), Gói chấp nhận ($ACK$) và Gói tìm kiếm trưởng cụm láng giềng ($NCR$).
3. Độ tin cậy toán học:
   • Chứng minh Định lý 3.1: Độ phức tạp tính toán của thuật toán phân cụm TED đạt mức tuyến tính $O(N_i) \approx O(n)$, với $N_i = N/K$ là số nút trung bình trong mỗi cụm.
   • Chứng minh Định lý 3.2: Độ phức tạp trao đổi thông điệp trong trường hợp xấu nhất là hàm bậc hai $O(n^2)$, cụ thể bằng $\frac{N^2}{K} + N + K^2$ thông điệp.

Data và phân tích

Môi trường thực nghiệm được thiết lập trên nền tảng mô phỏng mạng Castalia/OMNeT++ với các thông số vật lý và lớp mạng chi tiết:

• Quy mô mạng: 100 nút cảm biến phân bố ngẫu nhiên trong diện tích $100\text{m} \times 100\text{m}$, trạm gốc Sink đặt tại tọa độ gốc $(0,0)$.
• Nguồn năng lượng ban đầu: $1.0\text{ Joule/nút}$; Kích thước gói dữ liệu: $l$ bits.
• Cấu hình lớp MAC (T-MAC): Khung thời gian $frameTime = 610\text{ ms}$, khoảng tranh chấp $contentionPeriod = 10\text{ ms}$, thời gian chờ lắng nghe $listenTimeout = 15\text{ ms}$, thời gian chờ hồi đáp $waitTimeout = 5\text{ ms}$, chu kỳ đồng bộ $resyncTime = 6\text{ s}$, số lần truyền lại tối đa $maxTxRetries = 2$, tốc độ dữ liệu vật lý $phyDataRate = 250\text{ kbps}$, trễ cảm nhận sóng mang $phyDelayForValidCS = 0.128\text{ ms}$.

Phát hiện đột phá và implications

Những phát hiện then chốt

1. Sự phân bố cụm đồng đều và triệt tiêu điểm chết mạng: Thuật toán TED tạo ra cấu trúc phân cụm đồng nhất trên toàn bộ không gian địa lý, loại bỏ hoàn toàn hiện tượng tập trung trưởng cụm cục bộ thường gặp ở LEACH.
2. Khả năng cân bằng thích ứng thông qua tham số $\alpha$ và $\beta$: Thực nghiệm chỉ ra rằng khi $\alpha = 0, \beta = 1$, các nút CH được chọn chủ yếu nằm gần Sink để tối ưu hóa thời gian truyền; khi $\alpha = 1, \beta = 0$, các nút có năng lượng dồi dào nhất được chọn làm CH. Cấu hình cân bằng $\alpha = 0.5, \beta = 0.5$ mang lại hiệu quả vượt trội trong việc kéo dài tuổi thọ mạng.
3. Vượt trội về số lượng nút sống sót theo thời gian: Thuật toán DCEM và DCEER duy trì số lượng nút sống sót (alive nodes) cao hơn rõ rệt so với Gen-LEACH và Multihop-HEED dưới cùng một điều kiện ràng buộc độ trễ đầu cuối.
4. Giảm thiểu tiêu thụ năng lượng tích lũy: Tổng năng lượng tiêu hao toàn mạng của DCEER thấp hơn đáng kể so với Multihop-HEED và DEM khi kích thước mạng tăng dần, nhờ khả năng tối ưu hóa việc chọn chặng kế tiếp chỉ dựa trên thông tin láng giềng một chặng.
5. Bảo đảm tỷ lệ phân phối gói tin tin cậy: Thuật toán DCEER đạt độ tin cậy truyền dữ liệu (packet delivery ratio) vượt trội ngay cả khi các ràng buộc về độ trễ đầu cuối bị siết chặt.

Implications đa chiều

• Về mặt lý thuyết: Thiết lập mô hình quy hoạch chi phí liên kết kết hợp giữa năng lượng tiêu hao và độ trễ hàng đợi, mở đường cho các nghiên cứu định tuyến QoS trong môi trường mạng vô tuyến hạn chế tài nguyên.
• Về mặt phương pháp luận: Cung cấp quy trình kết hợp chặt chẽ giữa mô hình hóa giải tích (hàng đợi $M/M/1$, phân tích độ phức tạp thuật toán) và mô phỏng thực nghiệm cấp gói tin trên Castalia/T-MAC.
• Về mặt thực tiễn: Mở ra giải pháp ứng dụng trực tiếp cho các hệ thống giám sát cảnh báo cháy rừng, quan trắc hoạt động núi lửa, cảnh báo sớm động đất - sóng thần và hệ thống phát hiện xâm nhập biên giới - những lĩnh vực đòi hỏi dữ liệu đo đạc (nhiệt độ, độ rung chấn) phải truyền về trung tâm điều hành trước khi vượt ngưỡng thời gian vô hiệu lực.
• Về mặt chính sách: Cung cấp cơ sở khoa học để xây dựng tiêu chuẩn kỹ thuật cho các hệ thống quan trắc môi trường thông minh và hạ tầng nông nghiệp công nghệ cao tại Việt Nam.

Limitations và Future Research

Luận án thẳng thắn thừa nhận các giới hạn nghiên cứu:

1. Độ phức tạp trao đổi thông điệp: Chi phí truyền thông điều khiển vẫn ở mức hàm đa thức $O(n^2)$, có thể tạo gánh nặng kênh truyền khi mật độ nút tăng vọt lên hàng nghìn nút/km².
2. Tối ưu hóa số chặng trong mạng tổng quát: Luận án chưa đưa ra công thức giải tích đóng để xác định số chặng tối ưu tuyệt đối cho mọi hình thái mạng bất kỳ.
3. Giả định nút cố định (Static Nodes): Mô hình mạng hiện tại chưa tích hợp tính di động của nút cảm biến (Mobile WSN) hoặc trạm gốc di động (Mobile Sink).

Chương trình nghiên cứu tương lai (Future Research Agenda):

• Ứng dụng các giải thuật tối ưu bầy đàn (Swarm Intelligence: PSO, ACO) để phân bố vị trí cụm tối ưu.
• Mở rộng giao thức định tuyến hỗ trợ mạng cảm biến đa phương tiện (Wireless Multimedia Sensor Networks - WMSN) truyền tải hình ảnh/video.
• Phát triển cơ chế định tuyến thích nghi cho các nút cảm biến di động và tích hợp công nghệ thu thập năng lượng môi trường (Energy Harvesting).

Tác động và ảnh hưởng

• Ảnh hưởng học thuật: Công trình đã công bố các bài báo khoa học chất lượng cao trên các tạp chí và kỷ yếu hội nghị chuyên ngành viễn thông - khoa học máy tính, tạo nền tảng trích dẫn vững chắc cho các nghiên cứu định tuyến tiết kiệm năng lượng có ràng buộc QoS.
• Chuyển đổi công nghiệp và IoT: Cung cấp lõi thuật toán tối ưu cho các nhà phát triển thiết bị IoT công nghiệp, nông nghiệp chính xác (đo độ ẩm đất, pH, độ mặn phục vụ tưới tiêu tự động) và giám sát kết cấu công trình xây dựng (cầu, đập thủy điện, tòa nhà cao tầng).
• Tác động xã hội: Giảm thiểu thiệt hại nhân mạng và vật chất nhờ hệ thống cảnh báo sớm thảm họa thiên nhiên vận hành bền bỉ với độ trễ thấp.

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

• Nghiên cứu sinh và học viên cao học: Tiếp cận phương pháp phân tích toán học độ phức tạp thuật toán $O(n)$, mô hình hàng đợi $M/M/1$ và kỹ thuật mô phỏng Castalia/T-MAC chuyên sâu.
• Giảng viên và nhà nghiên cứu cấp cao: Khai thác khung phân tích đa mục tiêu ($\alpha, \beta$) để mở rộng sang các hệ thống mạng không dây 5G/6G và mạng cảm biến dưới nước (UWSN).
• Kỹ sư R&D công nghệ mạng: Tích hợp mã giả và nguyên lý của các thuật toán TED, DEM, DCEM, DCEER vào firmware của các dòng vi điều khiển cảm biến thương mại.
• Cơ quan quản lý và quy hoạch đô thị: Ứng dụng triển khai hệ thống quan trắc giao thông thời gian thực và mạng lưới giám sát chất lượng không khí đô thị thông minh.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và mở rộng lý thuyết nào? Đóng góp độc đáo nhất là việc thiết lập chỉ số cân bằng động TED và hàm chi phí liên kết đa mục tiêu tích hợp mô hình hàng đợi $M/M/1$. Nghiên cứu đã mở rộng trực tiếp lý thuyết phân cụm LEACH (Heinzelman et al.) và HEED (Younis & Fahmy) từ không gian đơn mục tiêu (năng lượng) sang không gian tối ưu hóa đa mục tiêu (năng lượng - độ trễ - khoảng cách).

2. Đổi mới phương pháp luận so với các nghiên cứu quốc tế tiền nhiệm? So với EAQoS (Akkaya & Younis) đòi hỏi thông tin trạng thái toàn mạng với độ phức tạp cao, và SPEED (He et al.) bỏ qua mức năng lượng dư của nút, luận án đã đề xuất giải thuật DCEER dựa trên vectơ khoảng cách phân tán. DCEER chỉ sử dụng thông tin cục bộ giữa các nút lân cận một chặng để tìm đường tối ưu, giảm thiểu đáng kể overhead điều khiển và đảm bảo độ phức tạp tính toán tại mỗi nút chỉ là $O(n)$.

3. Phát hiện thực nghiệm đáng ngạc nhiên nhất là gì? Việc tăng số chặng truyền thông (multi-hop) tuy làm tăng tổng độ trễ tích lũy trên lý thuyết, nhưng khi kết hợp với cơ chế phân cụm TED và gom cụm dữ liệu (data fusion $E_F$), tổng năng lượng tiêu thụ của toàn mạng giảm đi theo cấp số nhân so với truyền thông ít chặng khoảng cách xa ($d^4$), trong khi độ trễ đầu cuối vẫn được kiểm soát nghiêm ngặt dưới ngưỡng cho phép của ứng dụng.

4. Nghiên cứu có cung cấp giao thức tái lập (Replication Protocol) không? Có. Luận án cung cấp đầy đủ mã giả chi tiết (từ Hình 3.2, 4.1, 5.3, 5.4 đến 6.3), cấu trúc định dạng gói tin ($CCR$, $ADV$, $BEA$), hệ thống tham số lớp MAC T-MAC chuẩn hóa và mô hình tiêu hao năng lượng giải tích chi tiết, cho phép tái lập hoàn chỉnh trên công cụ mô phỏng Castalia.

5. Lộ trình nghiên cứu 10 năm tiếp theo được định hình như thế nào? Lộ trình hướng tới: (i) Tích hợp thuật toán tối ưu hóa bầy đàn (Swarm Intelligence) trong việc tự cấu hình mạng; (ii) Phát triển giao thức định tuyến cho mạng cảm biến di động (WSN with mobile sinks/nodes); (iii) Xây dựng giải pháp an toàn thông tin và bảo mật chống tấn công nút giả mạo trong quá trình chuyển tiếp đa chặng.

Kết luận

1. Luận án đã giải quyết trọn vẹn bài toán mâu thuẫn giữa tiết kiệm năng lượng và giảm độ trễ đầu cuối trong mạng cảm biến không dây thông qua hệ thống giải pháp phân cấp toàn diện.
2. Đề xuất thành công thuật toán phân cụm thích nghi TED với độ phức tạp tính toán tuyến tính $O(n)$, phân bố đồng đều các nút trưởng cụm và cân bằng tải năng lượng mạng.
3. Thiết kế giải thuật định tuyến DEM kết hợp hàm chi phí đa tham số và giải thuật DCEM tìm $k$-đường ngắn nhất đảm bảo ràng buộc độ trễ khắt khe.
4. Phát triển giải thuật định tuyến phân tán thích ứng DCEER giúp giảm thiểu overhead trao đổi thông điệp, đạt tốc độ hội tụ nhanh và phù hợp cho các mạng quy mô lớn.
5. Kiểm chứng độ tin cậy và hiệu năng vượt trội của các giải thuật đề xuất thông qua phân tích toán học giải tích và mô phỏng thực nghiệm chuyên sâu trên công cụ Castalia/T-MAC.
6. Mở ra các hướng nghiên cứu liên ngành giá trị cao về tối ưu hóa bầy đàn, mạng cảm biến đa phương tiện thời gian thực và các hệ thống IoT cảnh báo sớm thảm họa thiên tai phục vụ phát triển kinh tế - xã hội.

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

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA HUỲNH TRỌNG THƢA GIẢM ĐỘ TRỄ END-TO-END VÀ TỔNG NĂNG LƢỢNG TIÊU THỤ TRONG CÁC MẠNG CẢM BIẾN KHÔNG DÂY LUẬN ÁN TIẾN SĨ KỸ THUẬT TP. HỒ CHÍ MINH NĂM 2017 ĐẠI HỌC QUỐC GIA TP. HCM TRƢỜNG ĐẠI HỌC BÁCH KHOA HUỲNH TRỌNG THƢA GIẢM ĐỘ TRỄ END-TO-END VÀ TỔNG NĂNG LƢỢNG TIÊU THỤ TRONG CÁC MẠNG CẢM BIẾN KHÔNG DÂY Chuyên ngành: Khoa học máy tính Mã số chuyên ngành: 62480101 Phản biện độc lập 1: PGS.

HÀ HẢI NAM Phản biện độc lập 2: PGS. HUỲNH XUÂN HIỆP Phản biện 1: GS. NGUYỄN NGỌC SAN Phản biện 2: PGS. NGUYỄN HUY HOÀNG Phản biện 3: PGS.

TRẦN VĂN HOÀI NGƢỜI HƢỚNG DẪN KHOA HỌC 1. TRẦN CÔNG HÙNG 2. ĐINH ĐỨC ANH VŨ LỜI CAM ĐOAN Tác giả xin cam đoan đây là công trình nghiên cứu của bản thân tác giả. Các kết quả nghiên cứu và các kết luận trong luận án này là trung thực, và không sao chép từ bất kỳ một nguồn nào và dƣới bất kỳ hình thức nào.

Việc tham khảo các nguồn tài liệu đã đƣợc thực hiện trích dẫn và ghi nguồn tài liệu tham khảo đúng theo yêu cầu. Tác giả luận án (chữ ký) __________________________________ Huỳnh Trọng Thƣa i TÓM TẮT LUẬN ÁN Trong những năm gần đây, những tiến bộ vƣợt bậc trong công nghệ vi điều khiển và các kỹ thuật truyền thông không dây đã cho phép triển khai nhiều mạng cảm biến không dây với một số lƣợng rất lớn các nút cảm biến. Sự quan tâm chủ yếu trong thiết kế và triển khai những ứng dụng mạng cảm biến không dây nhƣ thế chính là vấn đề tiêu thụ năng lƣợng. Giải thuật phân cụm là một kỹ thuật hiệu quả đƣợc sử dụng để tiết kiệm năng lƣợng cho các nút cảm biến trong quá trình truyền thông.

Ngoài ra, kỹ thuật này cũng làm tăng tính co giãn, bền vững và thời gian sống của mạng. Trong nhiều sơ đồ phân cụm đã đề xuất, để đơn giản trong vấn đề định tuyến, việc truyền thông giữa các cụm với nút gốc đƣợc thiết kế theo mô hình một chặng trực tiếp. Tuy nhiên, mô hình truyền thông đa chặng thƣờng sẽ phù hợp hơn khi dải truyền thông của các nút cảm biến bị giới hạn hoặc số lƣợng nút cảm biến là rất lớn trong một mạng. Mặt khác, truyền thông đa chặng lại gặp phải vấn đề về độ trễ xử lý và phân phối dữ liệu từ các nút cảm biến nguồn đến nút gốc.

Để giải quyết bài toán này, hƣớng nghiên cứu phối hợp kỹ thuật phân cụm vào trong vấn đề định tuyến đa chặng đã và đang thu hút nhiều sự quan tâm trong những năm gần đây. Qua khảo sát nhiều mô hình và giải thuật đề xuất cho thấy việc giảm số chặng trên đƣờng đi từ các nút cảm biến nguồn đến nút gốc có thể làm giảm độ trễ end-to- end nhƣng lại làm tăng tổng năng lƣợng tiêu thụ và số lƣợng thông điệp trao đổi để quyết định chọn hƣớng chuyển tiếp dữ liệu phù hợp. Ngoài ra, có thể dễ dàng nhận thấy rằng, số lƣợng chặng tỷ lệ thuận với độ trễ truyền thông và tỷ lệ nghịch với năng lƣợng tiêu thụ. Do vậy, việc phân bố phù hợp các nút vào trong các cụm và chọn đƣờng đi với số lƣợng chặng tối ƣu để cân bằng cả hai yếu tố năng lƣợng tiêu thụ và độ trễ end-to-end là một vấn đề khó.

Luận án tập trung nghiên cứu và thiết kế giải thuật phân cụm kết hợp các giải thuật định tuyến đa chặng giữa các cụm nhằm giải quyết các mục tiêu cụ thể nhƣ: (i) Giảm thiểu độ phức tạp tính toán và trao đổi thông điệp điều khiển cho các nút cảm biến nhằm tiết kiệm năng lƣợng tiêu thụ và thời gian trễ do xử lý và truyền thông; (ii) Giảm độ trễ end-to-end do việc phân phối dữ liệu từ các nút cảm biến nguồn đến nút gốc; và (iii) Cân bằng năng lƣợng giữa các nút cảm biến để kéo dài thời gian sống của toàn mạng. Cụ thể, luận án đề xuất các giải thuật sau: ii 1) Giải thuật phân cụm: Luận án đề xuất mô hình phân cụm dựa trên mức năng lƣợng còn lại của các nút cảm biến và độ trễ end-to-end. Cùng với việc đề xuất một giải thuật phân cụm cân bằng năng lƣợng tiêu thụ và độ trễ end-to-end, luận án cũng thiết kế một hàm chi phí tổng hợp dựa trên mức năng lƣợng còn lại của mỗi nút cảm biến và khoảng cách giữa chúng nhằm chọn ra các nút trƣởng cụm tối ƣu để phân phối dữ liệu đến trạm gốc một cách hiệu quả nhất. Độ phức tạp tính toán của giải thuật đề xuất đƣợc chứng minh là một hàm tuyến tính.

Điều này giúp các nút cảm biến tiết kiệm đƣợc nhiều năng lƣợng hơn và giảm thiểu thời gian xử lý cục bộ. Kết quả mô phỏng cho thấy giải thuật phân cụm đƣợc đề xuất tạo ra sự phân bố đồng đều các nút cảm biến vào trong các cụm so với các giải thuật tƣơng tự. 2) Giải thuật định tuyến cân bằng năng lƣợng tiêu thụ và độ trễ end-to-end: Luận án đề xuất một hàm chi phí kết hợp hai yếu tố năng lƣợng tiêu thụ tại mỗi nút cảm biến và độ trễ liên kết giữa các nút cảm biến lân cận nhau. Ngoài ra, luận án cũng đề xuất một giải thuật cập nhật hàm chi phí để phân phối dữ liệu đến trạm gốc theo đƣờng đi có tổng chi phí kết hợp thấp nhất.

Kết quả mô phỏng cho thấy giải thuật này tạo sự cân bằng cho cả năng lƣợng tiêu thụ và độ trễ end-to-end. 3) Giải thuật định tuyến hiệu quả năng lƣợng với k đƣờng ngắn nhất đảm bảo độ trễ đầu cuối: Luận án đề xuất một hàm chi phí chỉ dựa vào năng lƣợng còn lại của mỗi nút cảm biến và một giải thuật định tuyến k đƣờng ngắn nhất theo tổng năng lƣợng tiêu thụ đảm bảo ràng buộc độ trễ end-to-end của ứng dụng. Phân tích toán học và kết quả mô phỏng cho thấy các nút cảm biến đạt đƣợc sự cân bằng về năng lƣợng tiêu thụ và thời gian sống của toàn mạng đƣợc kéo dài khi so sánh với các đề xuất tƣơng tự. 4) Giải thuật định tuyến phân tán hiệu quả năng lƣợng có ràng buộc độ trễ đầu cuối: Luận án đề xuất giải thuật chọn nút trƣởng cụm tối ƣu năng lƣợng tiêu thụ nhƣng phải đảm bảo yêu cầu về ràng buộc độ trễ đầu cuối làm nút chuyển tiếp dữ liệu chỉ dựa vào thông tin cục bộ giữa các nút lân cận.

Điều này làm giảm lƣợng overhead trao đổi trong quá trình khám phá iii đƣờng đi, giúp giải thuật đạt đƣợc sự hội tụ nhanh. Minh chứng toán học cho thấy giải thuật đề xuất có độ phức tạp tính toán và trao đổi thông điệp thấp, và vì thế nó có thể đƣợc áp dụng hiệu quả cho các mạng cảm biến không dây với số lƣợng lớn các nút cảm biến. Kết quả mô phỏng cho thấy giải thuật đề xuất tạo sự cân bằng năng lƣợng tiêu thụ giữa các nút cảm biến và nâng cao thời gian sống toàn mạng. Trong các giải thuật đƣợc đề xuất trong luận án, dễ nhận thấy tiềm năng của việc ứng dụng chúng vào trong thực tiễn hiện nay là rất lớn.

Có thể chỉ ra đây một vài ứng dụng trong thực tế có thể áp dụng hiệu quả mô hình phân cụm và các giải thuật định tuyến đã đề xuất nhƣ: hệ thống giám sát cháy rừng, hệ thống giám sát các hoạt động núi lửa, hệ thống cảnh báo động đất, sóng thần, hệ thống phát hiện xâm nhập và nhiều dạng ứng dụng khác có yêu cầu độ nhạy về thời gian đáp ứng thông tin. Mặc dù mô hình phân cụm và các giải thuật định tuyến đề xuất đã cho thấy sự cải thiện đáng kể về việc tiết kiệm năng lƣợng tiêu thụ và giảm độ trễ end-to-end trong các mạng cảm biến không dây, chúng vẫn còn một số hạn chế nhƣ: phƣơng pháp xác định số chặng tối ƣu trong một kích thƣớc mạng tổng quát chƣa đƣợc chỉ ra, độ phức tạp trong trao đổi thông điệp điều khiển vẫn là một hàm đa thức. Do vậy, luận án đề xuất hƣớng nghiên cứu tiềm năng khác là phƣơng pháp tối ƣu bầy đàn để phân bố phù hợp các nút cảm biến trong mạng nhằm cân bằng tốt hơn năng lƣợng tiêu thụ và độ trễ truyền thông. iv ABSTRACT In recent years, continued and rapid advances in microcontroller and wireless communication technologies have enabled to deploy wireless sensor networks with a large number of sensor nodes.

The main concern in designing and deploying applications for wireless sensor networks is energy consumption problem. Clustering algorithm is an effective technique used to save energy for sensor nodes in the communication. In addition, this technique also increases scalability, sustainability and network lifetime. In many proposed clustering schemes, to simplify the routing problem, the communication between clusters and the base station is designed in a direct one-hop model.

However, the multi-hop communication model is more suitable when the communication range of sensor nodes is limited or the number of sensor nodes is very large in the network. On the other hand, multi-hop communication has to face up the problem on delay processing and data delivery from source sensor nodes to the base station. To solve this problem, research direction by collaboration clustering technique with multi-hop routing problem has been attracting a lot of attention in recent years. Through surveying on many proposed models and algorithms, it shows that reducing the number of hops on the path from source sensor nodes to the base station can reduce end-to-end delay but increase the total energy consumption and the number of exchanged messages in order to decide on direction to forward data accordingly.

In addition, it easy to see that the number of hops is directly proportional to the communication delay and inversely proportional to the energy consumption. Therefore, the appropriate distribution sensor nodes into clusters and selection the path with the optimal number of hops to balance both energy consumption and end-to-end delay is a difficult problem. This thesis focuses on researching and designing the clustering algorithm in combination with the multi-hop routing algorithms between clusters to address specific goals: (i) minimizing computational complexity and exchanged control messages for sensor nodes in order to save energy consumption and delay by processing and communication; (ii) reducing end-to-end delay by data delivery from source sensor nodes to the base station; and (iii) balancing the energy between sensor nodes to v extend the lifetime of the whole network. Particularly, the thesis proposes the following algorithms: 1) Clustering algorithm: The thesis proposes the clustering model based on the remaining energy level of the sensor nodes and end-to-end delay.

Along with proposing a clustering algorithm to trade-off the consumed energy and end-to-end delay, this thesis also design an aggregate cost function based on the remaining energy level of each sensor node and distance between them to select the optimal cluster head nodes for distributing data to the base station (or sink) in the most efficient way.