Tiến hóa đa nhiệm giải bài toán cây tổng hợp dữ liệu năng lượng nhỏ nhất

Luận văn trình bày giải pháp tiến hóa đa nhiệm (MFEA) tối ưu cây tổng hợp dữ liệu, giúp giảm thiểu năng lượng tiêu thụ cho mạng cảm biến không dây.

• Tác giả: Trần Quang Tuấn
• 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: Tiến hóa đa nhiệm giải bài toán cây tổng hợp dữ liệu với năng lượng nhỏ nhất
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về Tiến hóa đa nhiệm trong Mạng cảm biến

Tiến hóa đa nhiệm (MFEA - Multifactorial Evolutionary Algorithm) là một giải thuật tối ưu hóa hiện đại được áp dụng để giải quyết các bài toán phức tạp trong mạng cảm biến không dây. Mạng cảm biến WSN ngày nay đóng vai trò quan trọng trong nhiều lĩnh vực từ y tế, môi trường đến thông minh xã hội. Tuy nhiên, hạn chế năng lượng của các nút cảm biến là thách thức lớn nhất. Tối ưu năng lượng mạng cảm biến trở thành ưu tiên hàng đầu nhằm kéo dài vòng đời hoạt động của hệ thống. Giải thuật tiến hóa đa nhiệm cung cấp một phương pháp hiệu quả để xây dựng cây tổng hợp dữ liệu tối ưu với chi phí năng lượng tối thiểu, giúp cải thiện hiệu suất tổng thể của mạng.

1.1. Khái niệm Mạng cảm biến không dây

Mạng cảm biến không dây (WSN) bao gồm hàng trăm hay hàng nghìn nút cảm biến nhỏ phân tán trong không gian giám sát. Mỗi nút có khả năng thu thập dữ liệu, xử lý thông tin và truyền thông tin qua sóng vô tuyến. Kiến trúc của nút cảm biến gồm bộ cảm nhận, bộ xử lý, bộ truyền thông và pin cấp năng lượng. Vấn đề chính là pin có dung lượng hạn chế, do đó việc quản lý năng lượng hiệu quả là rất quan trọng để duy trì hoạt động lâu dài của mạng.

1.2. Tầm quan trọng của Tối ưu năng lượng

Tối ưu năng lượng mạng cảm biến là yếu tố then chốt quyết định tuổi thọ của hệ thống. Năng lượng được tiêu hao chủ yếu qua các hoạt động truyền dữ liệu, thu nhận dữ liệu và xử lý thông tin. Bằng cách thiết kế cây tổng hợp dữ liệu tối ưu, ta có thể giảm đáng kể số lần truyền thông và lượng dữ liệu cần xử lý, từ đó kéo dài vòng đời mạng và nâng cao hiệu quả hoạt động.

II. Bài toán Cây tổng hợp dữ liệu với Năng lượng tối thiểu

Bài toán cây tổng hợp dữ liệu là một bài toán tối ưu hóa tổ hợp nhằm xác định cấu trúc cây tối ưu để các nút cảm biến gửi dữ liệu tới nút đích (sink node) với tổng chi phí năng lượng nhỏ nhất. Cây tổng hợp dữ liệu đảm bảo rằng thông tin từ tất cả nút cảm biến được thu thập và hợp nhất trước khi gửi tới trung tâm điều khiển. Mục tiêu chính là tối ưu hóa cấu trúc cây sao cho tổng năng lượng tiêu hao trong quá trình truyền và tổng hợp dữ liệu đạt mức tối thiểu. Đây là bài toán NP-khó, không thể giải quyết hiệu quả bằng các phương pháp chính xác, do đó cần sử dụng các giải thuật metaheuristic như tiến hóa đa nhiệm.

2.1. Định nghĩa và mô hình hóa bài toán

Mạng cảm biến được mô hình hóa dưới dạng đồ thị có hướng G = (V, E), trong đó V là tập hợp các nút cảm biến và E là tập hợp các cạnh đại diện cho khoảng cách giữa các nút. Cây tổng hợp dữ liệu T là một cây bao trùm của đồ thị G, nối tất cả nút với nút sink. Chi phí của mỗi cạnh được tính dựa trên khoảng cách Euclid và lượng dữ liệu truyền qua. Tổng năng lượng của cây là tổng chi phí của tất cả các cạnh trong cây.

2.2. Thách thức và ứng dụng thực tiễn

Thách thức chính là bài toán có độ phức tạp tính toán rất cao, không thể giải quyết tối ưu trong thời gian hợp lý. Ứng dụng thực tiễn bao gồm giám sát môi trường, theo dõi sức khỏe bệnh nhân, quản lý nông nghiệp thông minh và an ninh giám sát. Trong các ứng dụng này, việc kéo dài thời gian hoạt động của mạng là cực kỳ quan trọng để đảm bảo tính liên tục của dịch vụ.

III. Giải thuật Tiến hóa đa nhiệm MFEA và Ứng dụng

Giải thuật tiến hóa đa nhiệm (MFEA) là một phương pháp tiên tiến dựa trên lý thuyết tiến hóa và di truyền để giải quyết các bài toán tối ưu hóa phức tạp. Khác với các giải thuật di truyền truyền thống, MFEA có khả năng xử lý nhiều tác vụ tối ưu hóa đồng thời và tận dụng kinh nghiệm được chia sẻ giữa các tác vụ để tăng hiệu quả tìm kiếm. Trong bối cảnh tối ưu năng lượng mạng cảm biến, MFEA được áp dụng để xây dựng cây tổng hợp dữ liệu tối ưu bằng cách tìm kiếm không gian các cây bao trùm có thể có. Thuật toán sử dụng các toán tử tiến hóa như lai ghép (crossover) và đột biến (mutation) để sinh ra các giải pháp tốt hơn.

3.1. Nguyên lý hoạt động của MFEA

MFEA hoạt động dựa trên mô hình tiến hóa đa nhiệm, trong đó một quần thể chung được duy trì để giải quyết nhiều bài toán cùng lúc. Mỗi cá thể trong quần thể được mã hóa dưới dạng một không gian chung, chứa thông tin của tất cả các tác vụ. Hàm thích nghi được tính toán cho từng tác vụ dựa trên mã hóa này. Các cá thể tốt từ các tác vụ khác nhau được lai ghép và đột biến để tạo ra thế hệ con, giúp chia sẻ thông tin di truyền giữa các tác vụ và nâng cao tốc độ hội tụ.

3.2. Mã hóa và Giải mã trong không gian chung

Để áp dụng MFEA cho bài toán cây tổng hợp dữ liệu, cần phải thiết kế phương pháp mã hóa hiệu quả trong không gian chung. Mỗi cá thể được mã hóa dưới dạng một vector chứa thông tin về cây bao trùm của tất cả mạng cảm biến liên quan. Quá trình giải mã sử dụng đồ thị giao nhau từ các cây của các tác vụ khác nhau để xây dựng cây bao trùm hợp lệ. Điều này cho phép chia sẻ các cạnh chung giữa các cây khác nhau, tăng cường tính hiệu quả của thuật toán.

IV. Kết quả Thực nghiệm và Kết luận

Kết quả thực nghiệm cho thấy giải thuật tiến hóa đa nhiệm đạt hiệu quả vượt trội so với các phương pháp giải thuật di truyền truyền thống trong việc giải quyết bài toán cây tổng hợp dữ liệu với năng lượng tối thiểu. Thuật toán được đánh giá trên nhiều kịch bản khác nhau với số lượng nút cảm biến từ 20 đến 100 nút. Kết quả cho thấy MFEA hội tụ nhanh hơn và tìm được các giải pháp có chi phí năng lượng thấp hơn so với GA truyền thống. Đặc biệt, tốc độ hội tụ của MFEA được cải thiện đáng kể khi sử dụng mã hóa trong không gian chung và kỹ thuật chia sẻ thông tin giữa các tác vụ. Kết luận rằng MFEA là giải pháp hiệu quả cho tối ưu năng lượng mạng cảm biến.

4.1. Hiệu quả Thuật toán trên các Kịch bản

Thực nghiệm được tiến hành trên hai nhóm kịch bản với tôpô mạng khác nhau. Nhóm kịch bản 1 sử dụng mạng với cấu trúc đều đặn, trong khi nhóm kịch bản 2 sử dụng mạng với tôpô ngẫu nhiên. Kết quả cho thấy MFEA vượt trội trong cả hai trường hợp, với độ cải thiện từ 15-25% so với GA truyền thống. Tốc độ hội tụ của MFEA nhanh hơn khoảng 20-30% ở các thế hệ đầu tiên, giúp tìm giải pháp tốt nhanh chóng.

4.2. Hướng phát triển và Ứng dụng tương lai

MFEA có tiềm năng ứng dụng lớn trong các bài toán tối ưu hóa khác của mạng cảm biến như định tuyến, lập lịch truyền thông và quản lý năng lượng. Các hướng nghiên cứu tương lai bao gồm cải thiện hiệu suất thuật toán thông qua các toán tử di truyền nâng cao và kỹ thuật học máy. Ngoài ra, việc mở rộng MFEA để giải quyết các bài toán đa mục tiêu trong mạng cảm biến cũng là hướng phát triển đáng khám phá.

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

Chương 1: Cơ sở lý thuyết. Trình bày kiến thức tổng quan về mạng cảm biến, cây tổng hợp dữ liệu, các bài toán định tuyến và tối ưu năng lượng trong mạng cảm biến. • Chương 2: Giải thuật đề xuất. Giới thiệu về mô hình bài toán & thuật toán tiến hóa và thuật toán tiến hóa đa nhiệm.

Trình bày về thuật toán tiến hoá đa nhiệm giải quyết bài toán cây tổng hợp dữ liệu với tổng năng lượng nhỏ nhất. Trình bày chi tiết về giải thuật, các chiến lược mã hoá và lai ghép, …vv sử dụng trong thuật toán. • Chương 3: Kết quả thực nghiệm. Tổng hợp kết quả thực nghiệm của giải thuật đề xuất với các phương pháp tiếp cận dựa trên cây đường đi ngắn nhất và giải thuật di truyền đơn nhiệm.1 Tổng quan về mạng cảm biến Mạng cảm biến không dây (Wireless Sensor Network) là tập hợp các thiết bị cảm biến sử dụng các liên kết không dây.

Chúng phối hợp với nhau để thực hiện nhiệm vụ thu thập thông tin dữ liệu với quy mô lớn. Mạng cảm biến không dây có thể liên kết trực tiếp hoặc gián tiếp với bên ngoài (mạng công cộng như Internet hay vệ tinh) thông qua một nút thu phát (Sink). Các nút cảm biến không dây có thể được triển khai cho các mục đích chuyên dụng như điều khiển giám sát và an ninh; thu thập thông tin môi trường; giám sát sức khỏe cho bệnh nhân trong y tế,. [5] Thế mạnh của mạng cảm biến đó là sự linh hoạt nên có thể triển khai ở những khu vực đặc biệt mà các thiết bị có dây khó tiếp cận.

Ngoài ra, mạng cảm biến không dây còn có nhưng đặc điểm nổi bật như sau [5]: Kích thước vật lý nhỏ gọn Các thiết bị trong mạng cảm biến không dây thường được thiết kế nhỏ gọn và tiện dụng. Vì kích thước thiết bị tỉ lệ nghịch với tốc độ xử lý, giới hạn lưu trữ và thời gian hoạt động nên mạng cảm biến cần được phát triển và thiết kế sao cho hợp lý và hài hòa nhất. Với công nghệ tiên tiến bây giờ các thiết bị trong mạng cảm biến không dây cũng khá đủ cho nhu cầu của người dùng: kích thước bé, năng lượng tiêu thu thấp, tốc độ nhanh,… Hoạt động đồng thời với độ tập trung cao Một mạng cảm biến không dây có thể cần động liên tục và chính xác cao trong thời gian dài, tùy vào nhu cầu sử dụng. Ví dụ như việc giám sát sức khỏe người bệnh trong y tế, người bệnh phải được theo dõi thường xuyên và liên tục.

Điều này đến chủ yếu từ thiết kế phần cứng của mạng cảm biến, tuy nhiên đôi khi thiết kế phần mềm hợp lý cũng đem lại những hiệu quả bất ngờ. Tính đa dạng trong thiết kế và sử dụng Hiện nay có rất nhiều thiết bị cảm biến được dành riêng cho một số lĩnh vực nhất định: những hệ thống được thiết kế cho những công việc đặc thù như đo lượng dầu trong nước hay đo nồng độ khí CO2 trong không khí. Những nhóm phát triển mạng cảm biến không dây đưa ra những giải pháp thích hợp là xây dựng một nền tảng 13 chung có thể kết hợp nhiều thiết bị lại với nhau. Chúng sử dụng phần mềm linh hoạt để có thể thích ứng với phần cứng riêng nhằm đem lại hiệu quả công việc.

Hoạt động tin cậy Đối với những lĩnh vực đặc biệt (y tế, …) những thông tin dữ liệu mà mạng cảm biến mang lại rất quan trọng và cấp thiết. Hiện nay khoa học công nghệ phát triển đã thiết kế ra những thiết bị cảm biến có độ tin cây cao và cung cấp thông tin nhanh chóng [5]. Như tính linh hoạt đã nêu ở trên, việc sử dụng phần mềm thích hợp cũng sẽ mang lại cho mạng tính hiệu quả và độ tin cậy thông tin cao. Trong thực tế, có nhiều yếu tố mang lại sự tin cậy cho mạng cảm biến không dây cũng như có nhiều yếu tố bên ngoài gây ra việc giảm độ tin cậy.

Trong mỗi trường hợp, con người có thể đưa ra những giải pháp hợp lý để mang lại tính tin cậy cao nhất.1 Cấu trúc của mạng cảm biến Một mạng cảm biến không dây thường có số lượng lớn các nút được phủ trong một vùng mà chúng ta muốn thăm dò hay thu thập thông tin dữ liệu. Do có sự gắn kết trong mạng nên các nút có thể tùy chỉnh vị trí sao cho phù hợp với địa hình cũng như yêu cầu người dùng. Với khả năng mở rộng cho nên mạng cảm biến không dây có thể tiếp cận những khu vực nguy hiểm hoặc địa hình đặc thù. Khả năng liên kết cũng như công tác làm việc chính là đặc trưng cơ bản của mạng cảm biến không dây.

Với số lượng lớn các cảm biến không dây được triển khai gần nhau thì truyền thông đa liên kết thường được lựa chọn để công suất tiêu thụ là nhỏ nhất (so với truyền thông đơn liên kết [6]) và mang lại hiệu quả truyền tín hiệu tốt hơn so với truyền khoảng cách xa. 14 Hình 1-1 Mạng cảm biến không dây trong thực tế[7] Cấu trúc cơ bản của một mạng cảm biến không dây được thể hiện trên Hình 1-1. Mỗi nút cảm biến được sắp đặt trong mạng có khả năng thu thập thông tin dữ liệu và định tuyến gói tin về nút chủ là bộ thu nhận (Sink, Base station).Dữ liệu này được chuyển tới người dùng (User) qua internet hoặc một môi trường khác. Nút Sink có thể quản lý việc định tuyến giúp các nút cảm biến truyền gói tin theo mong muốn.

Số liệu được nút Sink nhận về thường không có một định dạng cụ thể, có thể tùy chỉnh sao cho phù hợp với mục đính của người sử dụng. Hình 1-2 Kiến trúc của 1 nút cảm biến [7] Mỗi nút cảm biến bao gồm bốn thành phần cơ bản là: hệ thống cảm biến, bộ xử lý, bộ phận lưu trữ nếu cần, thiết bị thu phát không dây và nguồn năng lượng. Tùy theo nhu cầu người dùng nên có những nút cảm biến còn được gắn thêm các thiết bị như hệ thống định vị, hệ thống năng lượng mặt trời, … Các thành phần cơ bản trong một nút cảm biến được thể hiện ở Hình 1-2: Hệ thống cảm biến bao gồm các đầu đo Sensor và một bộ chuyển đổi tương tự số ADC. Các tín hiệu tương tự được thu nhận từ đầu đo được chuyển sang tín hiệu số bằng bộ chuyển đổi ADC, những 15 tín hiệu số được đưa vào bộ xử lý.

Bộ xử lý thường được gắn thêm một bộ nhớ nhỏ, nhằm xử lý tín hiệu số và truyền dữ liệu cho thiết bị thu phát không dây. Ở đây bộ xử lý có thể tiến hành định dạng gói tin cũng như định tuyến cho thiết bị không dây. Thiết bị không dây có nhiệm vụ thu phát các thông tin dữ liệu giữa các nút cảm biến với nhau.2 Kiến trúc giao thức của mạng cảm biến không dây Hình 1-3 Kiến trúc giao thức của mạng cảm biến không dây [7] Kiến trúc giao thức được sử dụng trong nút chủ (Sink) và tất cả các nút cảm biến được thể hiện trên Hình 1-3. Kiến trúc giao thức bao gồm lớp ứng dụng (Application Layer), lớp giao vận (Transport Layer), lớp mạng (Network Layer), lớp liên kết số liệu (Datalink Layer), lớp vật lý (Physical Layer), mặt bằng quản lý năng lượng (Power Management Plane), mặt bằng quản lý di động (Mobility Management Plane) và mặt bằng quản lý nhiệm vụ (Task Management Plane).

Kiến trúc gồm ba mặt phẳng quản lý là: Mặt phẳng quản lý nguồn, mặt phẳng quản lý tính di động, mặt phẳng quản lý tác vụ. Mặt phẳng quản lý nguồn Mặt phẳng quản lý nguồn quản lý cách cảm biến sử dụng nguồn năng lượng của nó. Ví dụ: một nút cảm biến có thể bật hoặc tắt bộ thu nhận sau khi nhận được một gói tin. Các nút cảm biến có thể broadcast đến các nút bên cạnh rằng mình không đủ năng lượng để thực hiện công việc được nữa.

Mặt phẳng quản lý tính di động Có nhiệm vụ quản lý tính di động của nút. Có thể phát hiện các nút bên cạnh và thông báo vị trí của nó cho các nút đó. 16 Mặt phẳng quản lý tác vụ Làm nhiệm vụ sắp xếp các công việc giữa các nút trong vùng liên quan. • Tầng vật lý: Có nhiệm vụ lựa chọn tần số, tạo ra tần số sóng mang, phát hiện tín hiệu, điều chế và mã hóa tín hiệu.

Trong mạng cảm biến thì băng tần sử dụng nhiều nhất là ISM 915 MHZ. • Tầng liên kết dữ liệu: Lớp này có nhiệm vụ liên kết dữ liệu, phát hiện dữ liệu hay các frame dữ liệu cần thiết. Vì một mạng cảm biến thường nhận được nhiều tín hiệu tạp âm nên 1 trong các nhiệm vụ của lớp này là lọc nhiễu. • Tầng mạng: Lớp mạng được thiết kế dùng để phân biệt các mạng cảm biến khác nhau.

Trong lớp này có nhưng số liệu mà người dùng cài đặt để xây dựng một mạng cảm biến riêng cho mình. • Tầng truyền tải: Chỉ cần thiết khi hệ thống được thiết kế cho việc truy cập qua internet hoặc mạng bên ngoài. • Tầng ứng dụng: Tùy theo nhiệm vụ của cảm biến, các loại ứng dụng, phần mềm khác nhau được xây dựng và sử dụng ở lớp ứng dụng này.3 Ứng dụng của mạng cảm biến Mạng cảm biến ngày càng trở nên phổ biến và có rất nhiều ứng dụng trong cuộc sống hiện nay. Một số ứng dụng phổ biến có thể kể đến như: Giám sát và điều khiển công nghiệp Hiện nay với nền công nghiệp phát triền, rất nhiều lĩnh vực cần đến sự tự động hóa.

Có những công việc phải điều khiển từ xa, hoặc vì lý do sức khỏe mà con người không thể lại gần: những khu vực nguy hiểm cần phải giám sát thường xuyên như hầm mỏ, khu sản xuất vật liệu nguy hiểm, khu vực thử nghiệm thuốc súng thuốc nổ. Do đó, mạng cảm biến không dây có thể đem lại nguồn thu lớn lao cho con người, giảm thiểu khả năng tai nạn ảnh hưởng sức khỏe người lao động. Một ví dụ đơn gian và dễ thấy là hệ thống phòng cháy chữa cháy trong công ty. Chúng thường bao gồm một cảm biến nhiệt độ và cảm biến khói trong phòng.

Khi phát hiện ra cháy hệ thống sẽ tự động phun nước dập lửa. Tự động hoá gia đình và điện dân dụng 17 Hình 1-4 Ứng dụng smarthouse [8] Hiện nay nhà thông minh (SmartHouse) không còn xa lạ đối với chúng ta. Hệ thống nhà thông minh bao gồm một hoặc nhiều mạng cảm biến khác nhau, phục vụ rất nhiều công việc cho con người.