Luận án tiến sĩ tối ưu thời gian sống mạng cảm biến không dây theo hướng xấp xỉ

Tìm hiểu phương pháp tối ưu hóa thời gian sống mạng cảm biến không dây. Nghiên cứu các kỹ thuật tiết kiệm năng lượng và nâng cao hiệu suất hoạt động của hệ

• Tác giả: Nguyễn Thị Tâm
• Người hướng dẫn: PGS.TS. Huỳnh Thị Thanh Bình
• Trường học: Đại học Bách khoa Hà Nội
• Chuyên ngành: Khoa học máy tính
• Đề tài: Tối ưu hóa thời gian sống của một lớp mạng cảm biến không dây theo hướng tiếp cận xấp xỉ
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về tối ưu hóa thời gian sống mạng cảm biến không dây

Mạng cảm biến không dây (WSN) gồm nhiều nút cảm biến nhỏ gọn, có khả năng thu thập và truyền tải dữ liệu môi trường. Thời gian sống của mạng là khoảng thời gian mạng hoạt động liên tục từ khi vận hành đến khi một phần nút cạn kiệt năng lượng. Tối ưu hóa thời gian sống là bài toán then chốt trong thiết kế mạng cảm biến. Bài toán này thường được mô hình hóa dưới dạng tối ưu đa mục tiêu. Các mục tiêu bao gồm cân bằng tải năng lượng giữa các nút, tối thiểu hóa mức tiêu thụ tổng thể, và đảm bảo độ phủ vùng giám sát. Phương pháp tiếp cận xấp xỉ cung cấp lời giải gần đúng chất lượng cao trong thời gian tính toán chấp nhận được. Các thuật toán tiến hóa như NSGA-II, MOEA/D được áp dụng rộng rãi. Kết quả nghiên cứu cho thấy hiệu quả vượt trội so với phương pháp truyền thống.

1.1. Khái niệm mạng cảm biến không dây và cấu trúc

Mạng cảm biến không dây là hệ thống phân tán gồm hàng trăm đến hàng nghìn nút cảm biến. Mỗi nút tích hợp bộ vi xử lý, cảm biến, bộ phát thu sóng, và nguồn năng lượng hạn chế. Các nút tự tổ chức thành mạng đa nhảy để truyền dữ liệu về trạm gốc. Cấu trúc mạng ảnh hưởng trực tiếp đến mức tiêu thụ năng lượng và thời gian sống. Mạng phẳng và mạng phân cụm là hai kiến trúc phổ biến nhất trong thực tế triển khai hiện nay.

1.2. Tầm quan trọng của tối ưu thời gian sống mạng

Thời gian sống quyết định hiệu quả kinh tế và kỹ thuật của hệ thống mạng cảm biến. Nút cảm biến thường hoạt động bằng pin, việc thay thế hoặc sạc lại rất khó khăn trong nhiều ứng dụng thực tế. Mạng hết năng lượng sớm gây gián đoạn giám sát và mất dữ liệu quan trọng. Tối ưu thời gian sống giúp kéo dài hoạt động liên tục, giảm chi phí bảo trì. Đây là tiêu chí đánh giá chất lượng hàng đầu khi thiết kế mạng cảm biến không dây quy mô lớn.

II. Phân tích bài toán tối ưu đa mục tiêu trong mạng cảm biến

Bài toán tối ưu thời gian sống mạng cảm biến là bài toán tối ưu đa mục tiêu phức tạp. Không gian nghiệm rất lớn do số lượng nút và cách phối hợp truyền dữ liệu đa dạng. Các hàm mục tiêu thường xung đột lẫn nhau. Ví dụ, giảm mức tiêu thụ năng lượng có thể làm tăng độ trễ truyền tin. Bài toán này thuộc lớp NP-hard, không tồn tại thuật toán giải chính xác trong thời gian đa thức. Không gian quyết định bao gồm lịch trình truyền dữ liệu, công suất phát sóng, lựa chọn đường truyền. Không gian mục tiêu chứa các vector đánh giá hiệu suất mạng. Bài toán yêu cầu tìm tập nghiệm Pareto tối ưu cân bằng giữa các mục tiêu cạnh tranh. Phương pháp giải chính xác chỉ khả thi cho mạng quy mô nhỏ. Với mạng hàng trăm nút, cần phương pháp xấp xỉ để tìm lời giải gần tối ưu trong thời gian chấp nhận.

2.1. Khái niệm tối ưu Pareto và điểm Utopia

Tập Pareto tối ưu gồm các lời giải không bị trội bởi lời giải nào khác. Điểm bị trội nghĩa là tồn tại ít nhất một lời giải tốt hơn ở tất cả các mục tiêu. Điểm Utopia là điểm lý tưởng đạt giá trị nhỏ nhất đồng thời trên mọi mục tiêu. Điểm Utopia thường không thuộc không gian nghiệm khả thi. Khoảng cách từ lời giải thực tế đến điểm Utopia phản ánh chất lượng nghiệm. Các thuật toán xấp xỉ cố gắng đưa tập nghiệm càng gần điểm Utopia càng tốt.

2.2. Độ đo đánh giá hiệu suất thuật toán xấp xỉ

Nhiều độ đo được sử dụng để đánh giá chất lượng tập nghiệm xấp xỉ. Độ đo C đánh giá mức độ trội giữa hai tập nghiệm. Độ đo HV tính thể tích không gian bị chiếm bởi tập nghiệm đến điểm tham chiếu. Độ đo Delta đánh giá mức độ phân bố đều của nghiệm trên biên Pareto. Giá trị HV càng cao càng tốt, Delta càng thấp càng tốt. Việc lựa chọn độ đo phù hợp giúp so sánh công bằng giữa các thuật toán khác nhau.

III. Phương pháp tiếp cận xấp xỉ tối ưu thời gian sống mạng cảm biến

Phương pháp tiếp cận xấp xỉ sử dụng thuật toán tiến hóa để tìm lời giải gần tối ưu. Thuật toán di truyền mô phỏng quá trình chọn lọc tự nhiên với các toán tử lai ghép và đột biến. Thuật toán NSGA-II áp dụng cơ chế sắp xếp không trội và khoảng cách chen lấn. Thuật toán MOEA/D phân rã bài toán đa mục tiêu thành nhiều bài toán con đơn giản hơn. Phương pháp xấp xỉ có ưu điểm xử lý được không gian nghiệm lớn và hàm mục tiêu phức tạp. Kết quả xấp xỉ hội tụ về tập Pareto tối ưu sau nhiều thế hệ lặp. Thời gian tính toán hợp lý hơn nhiều so với phương pháp giải chính xác. Nghiên cứu áp dụng các thuật toán này cho bài toán tối ưu mạng cảm biến cụ thể. Kết quả thử nghiệm chứng minh hiệu quả vượt trội về chất lượng nghiệm và thời gian tính toán.

3.1. Thuật toán NSGA II trong tối ưu mạng cảm biến

NSGA-II là thuật toán tiến hóa đa mục tiêu hiệu quả dựa trên sắp xếp không trội. Thuật toán duy trì quần thể nghiệm và đánh giá theo nhiều mục tiêu cùng lúc. Cơ chế sắp xếp chia nghiệm thành các front không trội xếp theo thứ tự ưu tiên. Khoảng cách chen lấn đảm bảo sự đa dạng phân bố nghiệm trên biên Pareto. Toán tử lai ghép và đột biến tạo ra nghiệm mới khám phá không gian tìm kiếm. NSGA-II được áp dụng thành công cho nhiều bài toán tối ưu mạng cảm biến thực tế.

3.2. Thuật toán MOEA D dựa trên phân rã mục tiêu

MOEA/D phân rã bài toán đa mục tiêu thành N bài toán con sử dụng hàm trọng số. Mỗi bài toán con tương ứng với một hướng trọng số trong không gian mục tiêu. Các bài toán con liền kề chia sẻ thông tin để tăng hiệu quả tìm kiếm. Phương pháp này phù hợp với bài toán có nhiều mục tiêu hơn hai hoặc ba. MOEA/D cho tập nghiệm phân bố đều trên biên Pareto. Thời gian tính toán của MOEA/D thường thấp hơn NSGA-II cho cùng kích thước quần thể.

IV. Kết luận và ứng dụng tối ưu mạng cảm biến không dây

Nghiên cứu đã xây dựng mô hình toán học cho bài toán tối ưu thời gian sống mạng cảm biến không dây. Phương pháp tiếp cận xấp xỉ dựa trên thuật toán tiến hóa cho kết quả chất lượng cao. Tập nghiệm Pareto xấp xỉ hội tụ gần biên Pareto tối ưu thực sự. Độ đo HV, Delta và C được sử dụng để đánh giá toàn diện hiệu suất thuật toán. Kết quả thử nghiệm trên nhiều kịch bản mạng khác nhau chứng minh tính hiệu quả. Thời gian tính toán giảm đáng kể so với phương pháp giải chính xác. Phương pháp áp dụng được cho mạng cảm biến quy mô lớn trong thực tế. Nghiên cứu mở ra hướng phát triển mới cho tối ưu mạng cảm biến thông minh. Ứng dụng bao gồm giám sát môi trường, nông nghiệp thông minh, thành phố thông minh.

4.1. Đóng góp chính của nghiên cứu

Nghiên cứu đóng góp mô hình tối ưu hóa đa mục tiêu mới cho mạng cảm biến không dây. Phương pháp xấp xỉ được thiết kế riêng phù hợp với đặc thù bài toán mạng cảm biến. Kết quả lý thuyết về tính hội tụ và phân bố nghiệm được chứng minh chặt chẽ. Phần mềm mô phỏng và cơ sở dữ liệu thử nghiệm được công bố để tái lập nghiên cứu. So sánh toàn diện giữa các thuật toán tiến hóa trên cùng bài toán chuẩn là đóng góp giá trị.

4.2. Ứng dụng thực tế và hướng phát triển

Kết quả nghiên cứu áp dụng được cho mạng cảm biến giám sát môi trường và nông nghiệp. Mạng cảm biến trong thành phố thông minh hưởng lợi từ thuật toán tối ưu thời gian sống. Hướng phát triển bao gồm tích hợp học máy để cải thiện thuật toán xấp xỉ. Bài toán tối ưu với ràng buộc chất lượng dịch vụ và độ tin cậy cần nghiên cứu thêm. Kết hợp tối ưu năng lượng mặt trời với thuật toán tiến hóa là hướng hứa hẹn.

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

Chương 1 CƠ SỞ LÝ THUYẾT Chương này trình bày các kiến thức cơ sở về bài toán tối ưu, các phương pháp giải bài toán tối ưu đơn mục tiêu và đa mục tiêu. Ngoài ra, các nghiên cứu liên quan đến bài toán tối ưu thời gian sống của mạng cảm biến không dây cũng được trình bày.1 Bài toán tối ưu Trong thực tế, chúng ta thường gặp những vấn đề có nhiều cách giải quyết khác nhau. Một cách tự nhiên, những cách làm “tốt nhất” (hay còn gọi là cách làm tối ưu nhất) thường được lựa chọn, ví dụ như: nhanh nhất, chi phí rẻ nhất hoặc tốn ít nhân công nhất,. Trong khoa học máy tính, việc tìm lời giải “tốt nhất” trong một tập các lời giải khả thi cho một vấn đề nào đó được gọi là tối ưu hóa [13].

Trong nghiên cứu [13], các tác giả đã đưa ra một số cách phân loại bài toán tối ưu, một trong số đó là phân loại dựa vào số lượng mục tiêu. Theo cách phân loại này, bài toán tối ưu được phân thành hai loại: bài toán tối ưu đơn mục tiêu và bài toán tối ưu đa mục tiêu.1 Bài toán tối ưu đơn mục tiêu Bài toán tối ưu đơn mục tiêu được định nghĩa như sau: Định nghĩa 1.1) Ràng buộc: gi (x) ≤ 0 i = 1, ., xn ) với xk là các biến liên tục hoặc rời rạc, k = 1, 2,. ˆ f (x): Rn → R là hàm mục tiêu của bài toán. ˆ gi (x) ≤ 0 là các ràng buộc bất đẳng thức, q là số ràng buộc bất đẳng thức.

ˆ hj (x) = 0 là các ràng buộc đẳng thức, p là số ràng buộc đẳng thức.2 Bài toán tối ưu đa mục tiêu Tối ưu đa mục tiêu (tối ưu Pareto) là tìm lời giải cho bài toán liên quan đến nhiều hơn một mục tiêu (tiêu chí) tối ưu. Các mục tiêu trong một bài toán được gọi là không xung đột nếu việc tối ưu một mục tiêu sẽ không ảnh hưởng đến các mục tiêu còn lại. Do đó, tập lời giải của bài toán tối ưu dạng này chỉ gồm một lời giải. Những bài toán tối ưu với các mục tiêu như vậy, người ta gọi là tối ưu đa mục tiêu tầm thường.

Ngược lại, nếu bài toán tối ưu với các mục tiêu xung đột nhau được gọi là tối ưu đa mục tiêu không tầm thường. Các mục tiêu được gọi là xung đột nếu việc tối ưu một mục tiêu sẽ làm giảm tính tối ưu của các mục tiêu khác. Tập lời giải của bài toán đa mục tiêu không tầm thường sẽ bao gồm nhiều lời giải khác nhau. Tùy vào mục đích, người quyết định có thể lựa chọn lời giải phù hợp.

Phần này sẽ trình bày tổng quan về bài toán tối ưu đa mục tiêu, các khái niệm trong tối ưu đa mục tiêu và các phương pháp thường được dùng để giải quyết bài toán tối ưu đa mục tiêu không tầm thường. Không mất tính tổng quát, giả sử rằng tất cả mục tiêu của bài toán tối ưu đa mục tiêu đều được cực tiểu hóa. Bài toán tối ưu m mục tiêu được định nghĩa như sau: Định nghĩa 1.5) Ràng buộc: gi (x) ≤ 0 i = 1, .7) xlk ≤ xk ≤ xuk k = 1, ., fm (x)) là véc tơ hàm mục tiêu., xn ) là véc tơ lời giải. Giá trị xlk là cận dưới và xuk là cận trên.

ˆ gi (x) ≤ 0 là các ràng buộc bất đẳng thức, q là số ràng buộc bất đẳng thức ˆ hj (x) = 0 là các ràng buộc đẳng thức, p là số ràng buộc đẳng thức.1 Không gian thiết kế và không gian mục tiêu Định nghĩa 1. Không gian thiết kế Ω ∈ Rn của bài toán MOO là tập các véc tơ x thỏa mãn các ràng buộc 1.8 của bài toán.1: Minh họa hai hàm mục tiêu f1 , f2 trong không gian thiết kế [14]. Đường biểu diễn hai hàm mục tiêu lần lượt là các đường tròn có tâm tại (0, 0) và (2, 0). Không gian thiết kế của bài toán này là: Ω = {x ∈ R2 |x1 ≥ 0, x2 ≥ 0}.

Đây chính là góc phần tư thứ nhất trong hình 1. Hàm f1 đạt cực tiểu tại điểm O(0, 0), hàm f2 đạt cực tiểu tại điểm B(2, 0). Tuy nhiên, f2 (O) = 4 và f1 (B) = 4 không phải là điểm cực tiểu. Như vậy, không có một điểm nào làm cho f1 và f2 cùng đạt cực tiểu.

Có thể thấy rằng bất cứ một điểm nào nằm ngoài đường thẳng nối giữa hai điểm O và B (có nghĩa là x2 = 0 và x1 ∈ / (0, 2)) đều không thể làm giảm giá trị cả hai hàm mục tiêu một cách đồng thời. Ví dụ, tại điểm C(3, 0), f1 (C) = 9 và f2 (C) = 1. Ngược lại, bất cứ một lời giải nào nằm giữa hai điểm O và B đều được coi là chấp nhận được vì không thể thực hiện việc giảm giá trị một hàm mục tiêu mà không làm tăng giá trị của hàm mục tiêu còn lại. Do đó, lời giải tối ưu của bài toán là Sp = {x ∈ R2 |0 ≤ x1 ≤ 2, x2 = 0}.

Đối với một bài toán đơn giản như trong ví dụ 1, tập lời giải tối ưu có thể được tìm thấy dễ ràng trong không gian thiết kế. Tuy nhiên, đối với nhiều bài 10 toán khó, việc tìm tập lời giải tối ưu không hề đơn giản. Việc sử dụng không gian thiết kế là không đủ để tìm ra tập lời giải tối ưu. Để hiểu khái niệm bài toán đa mục tiêu và các kỹ thuật giải, bài toán sẽ phải được chuyển sang một không gian mới gọi là không gian mục tiêu (criterion space/ objective space).

Định nghĩa về không gian mục tiêu được đưa ra như sau: Định nghĩa 1. Không gian mục tiêu được định nghĩa là tập của các giá trị hàm mục tiêu tương ứng với các điểm trong không gian thiết kế. Bài toán đa mục tiêu trong ví dụ 1 có thể được biểu diễn trong không gian mục tiêu như trong hình 1.2(b) với các trục là các hàm mục tiêu. Các ràng buộc ban đầu của bài toán được chuyển sang không gian mục tiêu bằng cách giải x1 và x2 theo f1 và f2 như trong phương trình (1.

Không gian mục tiêu Z của bài toán này được định nghĩa trong phương trình (1.13) là tập các giá trị các hàm mục tiêu tương ứng với các điểm khả thi trong không gian thiết kế: Z = {F(x)|x ∈ Ω}.13) Như trong hình 1.2(a), các điểm O, A, B trong không gian thiết kế sẽ được ánh xạ thành các điểm o, a, b trong không gian mục tiêu. Tập các lời giải tối ưu trong không gian thiết kế là Sp , được chuyển thành đường cong Zp trong p không gian mục tiêu, Zp = {F = (f1 , f2 ) ∈ R2 |0 ≤ f1 ≤ 4, 0 ≤ f2 ≤ 4, f1 − x21 = p f1 − (0. Đường cong Zp trong không gian mục tiêu biểu diễn các lời giải tối ưu của bài toán tối ưu đa mục tiêu. Từ không gian mục tiêu trong hình 1.

Hơn nữa, mỗi một mục tiêu f1 , f2 không thể giảm hơn nữa mà không làm tăng giá trị của hàm mục tiêu còn lại tại bất cứ một điểm nào trên đường cong Zp. Đối với mỗi điểm không thuộc đường cong Zp , ví dụ như điểm d(4, 4), có thể giảm 11 đồng thời giá trị của hai hàm mục tiêu bằng cách di chuyển điểm đó gần về phía đường cong này. Cần lưu ý rằng, mỗi điểm trong không gian thiết kế có thể ánh xạ tới một điểm trong không gian mục tiêu. Tuy nhiên, điều ngược lại có thể không đúng; nghĩa là mọi điểm trong không gian mục tiêu không nhất thiết phải tương ứng với các điểm hoặc một điểm duy nhất trong không gian thiết kế.2, điểm e(0, 0) trong không gian mục tiêu không ánh xạ đến bất cứ một điểm nào trong không gian thiết kế.

Điểm d(4, 4) trong không gian mục tiêu ánh xạ đến 2 √ √ điểm D1 (1, 3) và D2 (1, − 3) trong không gian thiết kế, D1 ∈ Ω và D2 ∈ / Ω. (a) Không gian thiết kế (b) Không gian mục tiêu Hình 1.2: Minh họa không gian thiết kế và không gian mục tiêu [14].2 Tối ưu Pareto Việc xác định các lời giải cho bài toán MOO được gọi là tối ưu Pareto. Một điểm x∗ trong không gian thiết kế Ω được gọi là tối ưu Pareto (Pareto optimal ) nếu không có điểm nào khác trong Ω làm giảm tại ít nhất một mục tiêu mà không làm tăng các mục tiêu khác. Tối ưu Pareto được định nghĩa một cách tường minh như sau: Định nghĩa 1.

Một điểm x∗ ∈ Ω được gọi là tối ưu Pareto nếu và chỉ nếu không tồn tại một điểm x trong không gian thiết kế Ω mà fi (x) ≤ fi (x∗ ) với mọi i và fi (x) < fi (x∗ ) với ít nhất một mục tiêu i, i = 1,. Để minh họa cho định nghĩa 1.5, giả sử rằng x∗ = (3, 0) được gọi là tối ưu Pareto (đây chính là điểm C trong hình 1. Tại điểm này, f1 (x∗ ) = 9 và f2 (x∗ ) = 1. Có 12 nhiều điểm x thỏa mãn điều kiện F(x) ≤ F(x∗ ) và fi (x) < fi (x∗ ) với ít nhất một mục tiêu i.

Do đó từ định nghĩa 1.5, điểm x∗ = (3, 0) không là tối ưu Pareto. Mặt khác, nếu chọn x∗ = (1, 0) (điểm A), f1 (x∗ ) = 1 và f2 (x∗ ) = 1, không tồn tại bất cứ một điểm nào mà f1 và f2 nhỏ hơn hoặc bằng giá trị của nó tại điểm (1, 0). Do đó, x∗ = (1, 0) được gọi là tối ưu Pareto. Một véc tơ của các mục tiêu F∗ = F(x∗ ) ∈ Z là không bị trội nếu và chỉ nếu không tồn tại một véc tơ F ∈ Z mà fi (x) ≤ fi (x∗ ) ∀i và fi (x) < fi (x∗ ) với ít nhất một i.

Ngược lại, F∗ là bị trội. Nói một cách khác, một nghiệm x∗ được gọi là trội so với nghiệm x, nếu hai điều kiện sau đây được thỏa mãn: ˆ Nghiệm x∗ không xấu hơn nghiệm x trong tất cả các giá trị của hàm mục tiêu, tức là fi (x∗ ) ≤ fi (x) với mọi i = 1, 2,. ˆ Nghiệm x∗ tốt hơn nghiệm x trên ít nhất một mục tiêu, tức là fi (x∗ ) < fi (x) trên ít nhất một i. Nếu hai điều kiện trên bị vi phạm, ta nói nghiệm x∗ không trội so với nghiệm x.

Là tập bao gồm tất cả các lời giải không bị trội bởi bất cứ một lời giải nào P = {x ∈ Ω|¬∃x0 ∈ Ω, F(x0 )  F(x)} (1.