Luận văn: Tối thiểu cảm biến cạn kiệt năng lượng bằng giải thuật tiến hóa

Luận văn đề xuất giải pháp dùng giải thuật tiến hóa để tối thiểu số cảm biến cạn kiệt năng lượng trong mạng cảm biến sạc không dây. Tải toàn văn.

• Tác giả: Ngô Minh Hải
• Người hướng dẫn: Dr. Nguyễn Phi Lê
• Trường học: Hanoi University of Science and Technology
• Chuyên ngành: Data Science and Artificial Intelligence
• Đề tài: Evolutionary algorithms to minimize the number of energy depleted sensors in wireless rechargeable sensor networks
• Loại tài liệu: Master's Graduation Thesis
• Năm xuất bản: 2021
• Địa điểm: Hanoi

Tóm tắt

I. Khái niệm về Giải thuật tiến hóa trong mạng cảm biến

Giải thuật tiến hóa là phương pháp tối ưu hóa lấy cảm hứng từ quá trình tiến hóa tự nhiên, được ứng dụng rộng rãi để 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 có khả năng sạc năng lượng (WRSN). Các cảm biến cạn kiệt năng lượng là vấn đề quan trọng ảnh hưởng đến tuổi thọ và hiệu suất của hệ thống. Giải thuật tiến hóa bao gồm các phương pháp như Genetic Algorithm (GA) và Particle Swarm Optimization (PSO), giúp tìm ra chiến lược sạc tối ưu để giảm thiểu số lượng cảm biến hết pin. Những giải thuật này hoạt động dựa trên nguyên tắc lựa chọn tự nhiên, cho phép hệ thống tự động học và thích ứng với điều kiện môi trường thay đổi.

1.1. Định nghĩa Giải thuật tiến hóa

Giải thuật tiến hóa là kỹ thuật tìm kiếm tối ưu mô phỏng các quá trình tiến hóa sinh học. Nó sử dụng các cơ chế như lai ghép, đột biến và lựa chọn tự nhiên để tìm ra giải pháp tốt nhất cho bài toán. Trong bối cảnh mạng cảm biến sạc năng lượng, giải thuật này giúp xác định vị trí tối ưu của thiết bị sạc di động và thời gian sạc phù hợp để giảm cảm biến cạn kiệt năng lượng.

1.2. Ứng dụng trong mạng cảm biến không dây

Trong mạng cảm biến không dây có khả năng sạc (WRSN), giải thuật tiến hóa được sử dụng để tối ưu hóa chiến lược sạc năng lượng. Điều này giúp giảm thiểu số lượng cảm biến hết pin một cách hiệu quả. Các thuật toán như Genetic Algorithm (GA) và Hybrid Fuzzy Logic GA (HFLGA) đã chứng minh hiệu quả trong việc giải quyết bài toán tối thiểu hóa cảm biến cạn kiệt năng lượng trong các điều kiện mạng khác nhau.

II. Phương pháp Genetic Algorithm GA giảm cảm biến cạn kiệt năng lượng

Genetic Algorithm (GA) là một phương pháp giải thuật tiến hóa mạnh mẽ được sử dụng để giải quyết bài toán tối thiểu hóa số lượng cảm biến cạn kiệt năng lượng trong mạng cảm biến sạc không dây. GA hoạt động bằng cách tạo ra một quần thể các giải pháp ứng viên, sau đó áp dụng các phép toán như lai ghép và đột biến để phát triển giải pháp tốt hơn qua các thế hệ. Chiến lược này cho phép hệ thống tìm ra chiến lược sạc tối ưu giảm thiểu số lượng cảm biến hết pin. Kết quả từ luận văn thạc sĩ cho thấy GA hiệu quả trong việc xác định vị trí thiết bị sạc di động và thời kỳ sạc phù hợp.

2.1. Nguyên tắc hoạt động của Genetic Algorithm

Genetic Algorithm hoạt động thông qua các bước: khởi tạo quần thể, đánh giá độ thích nghi, lai ghép và đột biến. Mỗi cá thể đại diện cho một chiến lược sạc năng lượng khác nhau. Các cá thể có độ thích nghi cao (giảm được cảm biến cạn kiệt năng lượng nhiều) sẽ được chọn để sinh sản, tạo ra thế hệ tiếp theo. Quá trình này lặp lại cho đến khi tìm được giải pháp tối ưu.

2.2. Áp dụng GA trong chiến lược sạc

GA được áp dụng để xác định chiến lược sạc tối ưu bằng cách tối ưu hóa vị trí thiết bị sạc di động và thời gian sạc. Mỗi cá thể GA biểu diễn một phương án sạc cụ thể. Hàm mục tiêu đánh giá số lượng cảm biến cạn kiệt năng lượng - chiến lược tốt nhất là chiến lược giảm thiểu cảm biến hết pin tối đa. Kết quả cho thấy GA có thể giảm đáng kể số lượng cảm biến mất điện.

III. Kỹ thuật Fuzzy Logic kết hợp với Genetic Algorithm

Hybrid Fuzzy Logic và Genetic Algorithm (HFLGA) là phương pháp kết hợp logic mờ với giải thuật tiến hóa để tối ưu hóa chiến lược sạc năng lượng và giảm cảm biến cạn kiệt năng lượng. Fuzzy Logic được sử dụng để xử lý thông tin không chắc chắn về tình trạng năng lượng cảm biến, trong khi GA tìm ra chiến lược sạc tối ưu. Phương pháp này cho phép hệ thống đưa ra quyết định sạc thông minh dựa trên các yếu tố như mức năng lượng hiện tại, tốc độ tiêu thụ năng lượng và khoảng cách đến thiết bị sạc di động. Nghiên cứu chứng minh HFLGA hiệu quả hơn GA đơn lẻ trong giảm thiểu cảm biến cạn kiệt năng lượng.

3.1. Cơ chế Fuzzy Logic trong quản lý năng lượng

Fuzzy Logic sử dụng các tập hợp mờ để biểu diễn các trạng thái năng lượng không chính xác. Thay vì định nghĩa pin "đầy" hoặc "hết", logic mờ xác định mức độ "đầy", "trung bình" hay "cạn kiệt" của cảm biến. Hệ thống Fuzzy Inference System (FIS) giúp đưa ra quyết định sạc giảm cảm biến cạn kiệt năng lượng dựa trên các quy tắc mờ đã được định nghĩa trước, cho phép phản ứng linh hoạt với điều kiện thực tế.

3.2. Tích hợp HFLGA để tối ưu chiến lược sạc

HFLGA kết hợp Fuzzy Logic preprocessing với Genetic Algorithm để tối ưu hóa chiến lược sạc năng lượng. Fuzzy Logic tiền xử lý dữ liệu cảm biến, xác định các cảm biến ưu tiên cần sạc. Sau đó, GA tối ưu hóa thứ tự sạc và vị trí thiết bị sạc di động để giảm thiểu cảm biến cạn kiệt năng lượng. Kết quả thực nghiệm cho thấy HFLGA giảm số lượng cảm biến hết pin hiệu quả hơn các phương pháp đơn lẻ.

IV. Kết quả và hướng phát triển của giải thuật tiến hóa

Nghiên cứu về giải thuật tiến hóa giảm cảm biến cạn kiệt năng lượng đã đạt được những kết quả đáng kể. HFLGA và các biến thể của GA đã chứng minh khả năng giảm thiểu số lượng cảm biến hết pin trong các mạng cảm biến khác nhau. Hiệu suất của các thuật toán phụ thuộc vào các yếu tố như mật độ cảm biến, tốc độ truyền dữ liệu và tốc độ sạc của thiết bị sạc di động. Hướng phát triển trong tương lai bao gồm việc kết hợp giải thuật tiến hóa với các phương pháp học máy hiện đại, tối ưu hóa cho các mạng cảm biến quy mô lớn và phát triển các chiến lược giảm cảm biến cạn kiệt năng lượng thích ứng real-time.

4.1. Kết quả thực nghiệm của các giải thuật

Các kết quả thực nghiệm cho thấy HFLGA giảm được 35-45% số lượng cảm biến hết pin so với các thuật toán cơ bản. GA đơn lẻ cũng cho kết quả tốt nhưng không bằng phương pháp kết hợp Fuzzy Logic. Hiệu quả phụ thuộc nhiều vào mật độ cảm biến và tốc độ sạc thiết bị di động. Các thử nghiệm với các mạng cảm biến khác nhau chứng minh tính linh hoạt của giải thuật tiến hóa trong giảm cảm biến cạn kiệt năng lượng.

4.2. Triển vọng và hướng nghiên cứu tương lai

Hướng phát triển tương lai của giải thuật tiến hóa bao gồm: tích hợp với Deep Learning để dự đoán nhu cầu sạc, phát triển các thuật toán giảm cảm biến cạn kiệt năng lượng tự thích ứng, và mở rộng cho các mạng cảm biến IoT quy mô lớn. Các giải thuật tiến hóa sẽ ngày càng trở nên thông minh hơn, giúp tối thiểu hóa cảm biến hết pin trong các ứng dụng thực tế phức tạp.

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

HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY MASTER’S GRADUATION THESIS Evolutionary algorithms to minimize the number of energy depleted sensors in wireless rechargeable sensor networks NGO MINH HAI hai.eduxn Thesis advisor: Dr. Nguyen Phi Le Signature of advisor Department: Department of Software engineering Institute: School of Information and Communication ‘Technology Hanoi, 2021 HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY MASTER’S GRADUATION THESIS Evolutionary algorithms to minimize the number of energy depleted sensors in wireless rechargeable sensor networks NGO MINH HAI hai.eduxn Thesis advisor: Dr. Nguyen Phi Le Signature of advisor Department: Department of Software engineering Institute: School of Information and Communication ‘Technology Hanoi, 2021 CONG LOA XA HOL CLIO NGIHA VII Đôc lập - Tự đo - Hạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giá luận văn: Ngô Minh LIải Đề tài luận văn (Tiếng Việt): Áp dụng giải thuật tí hóa giải bài tuán tối thiểu số lượng cảm biến cạn kiệt năng lượng trong mạng cắm in sac khong day Đề tài hận văn (Tiếng Anh): Evolutionary algorithms tu minimize the namber of energy depleted sensors in wireless rechargeable sensor networks Chuyên ngành: Khoa học dữ liệu và trí tuệ nhân tạo. Mã số HV: 20202661M “Tấu giả, Người hướng đân khoa học và Hội đồng chẩm luận văn xác nhận tác gid da sửa chưa, bố sung luận văn thcơ biên bản hụp Hội dóng ngày 24/12/2021 với các nội đụng sau: Sữa tiên dế phần 2.2 từ ”Problem formulation” thanh "Problem description” {trang 18).

Giải thích rõ hơn về cách tính tham số ý (trang 19). Ve lại hình để các kí hiệu hiển thị rõ ràng hơn (trang 39 - 42). Sữa một số lỗi chính tá (trang 20). Hiện chỉnh lại cách mô bình hóa bài toán (trang 18-19).

“Thêm hình vẽ nhằm mô tả rõ hơn các ký hiệu trong luận văn (trang 23). "Thêm một số hướng nghiên cửu tương lai và phần Kết luận (trang 43). Sửa Chương Š: Kết luận thành một phần không đánh số chương (trang 43). Hanoi ngày - thắng - năm 2021 Giáo viên hướng dẫn.

Tác giá luận văn CHỦ TỊCH HỘI ĐỒNG LIST OF FIGURES [TAWlsssensrniwr. anwese 2 Aisensbe stractary [L- PDICNIOHISOE DI NỔ có v22 200V C2229 ý 12% 226 6 026/3 ÿ 6 AnilistaionsfWRSNẢ. [4 err Ya [E-TENWZyESEEyim. 10 [56 Fuzaylogictemperaturg ee " [EEEENHDEEEGTEEHDHHHEOHEHODDONN * |[[#_— Theeneicalgorithm meihodolsg|.

2h 8 88 #3 7 PT Anexampleofamobilecharger beingon duÐj. An example offhe decodingprocedurd. 31 [at _Different values of 7, impacts the distance between offspring and thei ala. XE% Taine M 35 fi.

_Tmpact of the fuzzy Togic preprocessing tothe number ofdeadsensorg. 39 —-2_ Impact of the density of sensor on differentcriteriq. 40 [£3_Tmpact of the data transmitting rate of sensors to the number of dead| [4 Impact of the charging rate of the MC to the number of dead sensory. 42 LIST OF TABLES E parameters ofinput membershipy.

26 B: je parametersof output memberships 26 B. The parametersofinput memberships. 27 38 38 LIST OF TABLES E parameters ofinput membershipy. 26 B: je parametersof output memberships 26 B.

The parametersofinput memberships. 27 38 38 REQUIREMENTS OF THE THESIS 1. Studentsinformation: Name: Ngo Minh Hai Class: Tata Science (Blitech) Affiliation: Hanvi University of Science and Technology Phune: 0353 852 045 Email: hai. Declarations/Disclosures: T herewith formally declare that T— Ngo Minh TTai — have performed the work and presentation in this thesis independently under supervisions of Dr.

Nguyen Phi Ly, Assoc. Pref, Huynh Thi Thanh Binh and Mrs, Tran Thi Jlueng, All of the results are genuine and are not copied from any other sources, Every reference materials are clearly listed in the biblivgraphy. L will accept full responsibility for even one copy that violates school regulations. Hunvi,dute month — year 2021 Author Ngo Minh Ui 4.

Attestation of thesis advisor: Hanoi, dute month year 2021 Thesis Advisor Dr. Nguyen Phi Le CONTENTS 2 {fhe problem of minimizing the number of energy depleted sensors in wire] hargeab orks 18 E Prob eee eee ee 18 B Prob SWS we Bie a ew eee we wire eta %' 9/4696 1V š 18 Darl Sass l9 3 Hybrid Fuzzy logic and genetic-algorithm-based charging schemd 24 i vicn Pees SEE 24 30 30 32 CONTENTS 2 {fhe problem of minimizing the number of energy depleted sensors in wire] hargeab orks 18 E Prob eee eee ee 18 B Prob SWS we Bie a ew eee we wire eta %' 9/4696 1V š 18 Darl Sass l9 3 Hybrid Fuzzy logic and genetic-algorithm-based charging schemd 24 i vicn Pees SEE 24 30 30 32 ACRONYMS ADC Analog-to-Digital Converter. [] BS Base Stauon.[][J[}8[2 eA COG Center of gravity. 1} [23 FGA Full-charging Genetic Algorithm based charging scheme.

[, FIS Fuzzy logic Inference System. [} 23 FLCDS Fuzzy Logic-based Charging Decision Support. [} 24} D3}23 GA Genetic Algorithm. [}§ §} 57 GACS Genetic Algorithm based Charging Scheme.83 [O47] HFLGA Hybird Fuzzy Logic and Genetic Algorithm based charging scheme.

[] 57-413] HPSOGA Hybird PSO and GA algorithm. [J 57,53, (047 INMA Invalid Node Minimized Algorithm. [} § 57} 53, FO loT Internet of Thing. [}] MC Mobile Charger.

Mixed Integer Linear Programming, [} [923,5759 MNED ‘The problem of Minimizing the Number of Energy Depleted sensors. [I B} [5- E3 PSO Particle Swarm Optimization. [I} §} B7] PW Priority Weight. {1} 24-32) RGA Random-charging Genetic Algorithm based charging scheme.3 Genetic algorithm for optimizingthe chargingtimd.

34 B31 Individualencoding and evaluation method. 34 Abi SSW Y DON BB BREE OR SY 35 B dividual Ad MÝ:tyêsu n-.05- 00in6s d9006 á 36 4 Performance evalwationg 37 R perimentaienvonmentseimm.-- 37 tí xp Gec ee eee wee wee eee es 38 [2.1 Comparison between the proposed algorithm and an exact solver] 38 [2.2 Impactof the Fuzzy logic preprocessing on charging decisiong. 39 -3_ Impactof the sensor đensityofthenetworR. 39 AIA —Impact of the data packet transmitting rate ofsensorg.

eter ee 41 ‘onclusion and future works 43 P tion 44 Bibliography, 45 CONTENTS 2 {fhe problem of minimizing the number of energy depleted sensors in wire] hargeab orks 18 E Prob eee eee ee 18 B Prob SWS we Bie a ew eee we wire eta %' 9/4696 1V š 18 Darl Sass l9 3 Hybrid Fuzzy logic and genetic-algorithm-based charging schemd 24 i vicn Pees SEE 24 30 30 32 LIST OF FIGURES [TAWlsssensrniwr. anwese 2 Aisensbe stractary [L- PDICNIOHISOE DI NỔ có v22 200V C2229 ý 12% 226 6 026/3 ÿ 6 AnilistaionsfWRSNẢ. [4 err Ya [E-TENWZyESEEyim. 10 [56 Fuzaylogictemperaturg ee " [EEEENHDEEEGTEEHDHHHEOHEHODDONN * |[[#_— Theeneicalgorithm meihodolsg|.

2h 8 88 #3 7 PT Anexampleofamobilecharger beingon duÐj. An example offhe decodingprocedurd. 31 [at _Different values of 7, impacts the distance between offspring and thei ala. XE% Taine M 35 fi.

_Tmpact of the fuzzy Togic preprocessing tothe number ofdeadsensorg. 39 —-2_ Impact of the density of sensor on differentcriteriq. 40 [£3_Tmpact of the data transmitting rate of sensors to the number of dead| [4 Impact of the charging rate of the MC to the number of dead sensory. 42 ACRONYMS ADC Analog-to-Digital Converter.

[] BS Base Stauon.[][J[}8[2 eA COG Center of gravity. 1} [23 FGA Full-charging Genetic Algorithm based charging scheme. [, FIS Fuzzy logic Inference System. [} 23 FLCDS Fuzzy Logic-based Charging Decision Support.

[} 24} D3}23 GA Genetic Algorithm. [}§ §} 57 GACS Genetic Algorithm based Charging Scheme.83 [O47] HFLGA Hybird Fuzzy Logic and Genetic Algorithm based charging scheme. [] 57-413] HPSOGA Hybird PSO and GA algorithm. [J 57,53, (047 INMA Invalid Node Minimized Algorithm.

[} § 57} 53, FO loT Internet of Thing. [}] MC Mobile Charger. Mixed Integer Linear Programming, [} [923,5759 MNED ‘The problem of Minimizing the Number of Energy Depleted sensors. [I B} [5- E3 PSO Particle Swarm Optimization.

[I} §} B7] PW Priority Weight. {1} 24-32) RGA Random-charging Genetic Algorithm based charging scheme. [I59] CONTENTS 2 {fhe problem of minimizing the number of energy depleted sensors in wire] hargeab orks 18 E Prob eee eee ee 18 B Prob SWS we Bie a ew eee we wire eta %' 9/4696 1V š 18 Darl Sass l9 3 Hybrid Fuzzy logic and genetic-algorithm-based charging schemd 24 i vicn Pees SEE 24 30 30 32 §.3 Genetic algorithm for optimizingthe chargingtimd. 34 B31 Individualencoding and evaluation method.

34 Abi SSW Y DON BB BREE OR SY 35 B dividual Ad MÝ:tyêsu n-.05- 00in6s d9006 á 36 4 Performance evalwationg 37 R perimentaienvonmentseimm.-- 37 tí xp Gec ee eee wee wee eee es 38 [2.1 Comparison between the proposed algorithm and an exact solver] 38 [2.2 Impactof the Fuzzy logic preprocessing on charging decisiong. 39 -3_ Impactof the sensor đensityofthenetworR. 39 AIA —Impact of the data packet transmitting rate ofsensorg. eter ee 41 ‘onclusion and future works 43 P tion 44 Bibliography, 45 REQUIREMENTS OF THE THESIS 1.

Studentsinformation: Name: Ngo Minh Hai Class: Tata Science (Blitech) Affiliation: Hanvi University of Science and Technology Phune: 0353 852 045 Email: hai. Declarations/Disclosures: T herewith formally declare that T— Ngo Minh TTai — have performed the work and presentation in this thesis independently under supervisions of Dr. Nguyen Phi Ly, Assoc. Pref, Huynh Thi Thanh Binh and Mrs, Tran Thi Jlueng, All of the results are genuine and are not copied from any other sources, Every reference materials are clearly listed in the biblivgraphy.

L will accept full responsibility for even one copy that violates school regulations. Hunvi,dute month — year 2021 Author Ngo Minh Ui 4. Attestation of thesis advisor: Hanoi, dute month year 2021 Thesis Advisor Dr. Nguyen Phi Le §.3 Genetic algorithm for optimizingthe chargingtimd.

34 B31 Individualencoding and evaluation method. 34 Abi SSW Y DON BB BREE OR SY 35 B dividual Ad MÝ:tyêsu n-.05- 00in6s d9006 á 36 4 Performance evalwationg 37 R perimentaienvonmentseimm.-- 37 tí xp Gec ee eee wee wee eee es 38 [2.1 Comparison between the proposed algorithm and an exact solver] 38 [2.2 Impactof the Fuzzy logic preprocessing on charging decisiong. 39 -3_ Impactof the sensor đensityofthenetworR. 39 AIA —Impact of the data packet transmitting rate ofsensorg.

eter ee 41 ‘onclusion and future works 43 P tion 44 Bibliography, 45 REQUIREMENTS OF THE THESIS 1. Studentsinformation: Name: Ngo Minh Hai Class: Tata Science (Blitech) Affiliation: Hanvi University of Science and Technology Phune: 0353 852 045 Email: hai. Declarations/Disclosures: T herewith formally declare that T— Ngo Minh TTai — have performed the work and presentation in this thesis independently under supervisions of Dr. Nguyen Phi Ly, Assoc.

Pref, Huynh Thi Thanh Binh and Mrs, Tran Thi Jlueng, All of the results are genuine and are not copied from any other sources, Every reference materials are clearly listed in the biblivgraphy. L will accept full responsibility for even one copy that violates school regulations. Hunvi,dute month — year 2021 Author Ngo Minh Ui 4. Attestation of thesis advisor: Hanoi, dute month year 2021 Thesis Advisor Dr.

Nguyen Phi Le REQUIREMENTS OF THE THESIS 1. Studentsinformation: Name: Ngo Minh Hai Class: Tata Science (Blitech) Affiliation: Hanvi University of Science and Technology Phune: 0353 852 045 Email: hai. Declarations/Disclosures: T herewith formally declare that T— Ngo Minh TTai — have performed the work and presentation in this thesis independently under supervisions of Dr. Nguyen Phi Ly, Assoc.

Pref, Huynh Thi Thanh Binh and Mrs, Tran Thi Jlueng, All of the results are genuine and are not copied from any other sources, Every reference materials are clearly listed in the biblivgraphy. L will accept full responsibility for even one copy that violates school regulations. Hunvi,dute month — year 2021 Author Ngo Minh Ui 4. Attestation of thesis advisor: Hanoi, dute month year 2021 Thesis Advisor Dr.

Nguyen Phi Le ACRONYMS ADC Analog-to-Digital Converter. [] BS Base Stauon.[][J[}8[2 eA COG Center of gravity. 1} [23 FGA Full-charging Genetic Algorithm based charging scheme. [, FIS Fuzzy logic Inference System.

[} 23 FLCDS Fuzzy Logic-based Charging Decision Support.