IIANOI UNIVERSITY OF SCIENCE AND TECIINOLOGY MASTER’S GRADUATION THESIS Optimal deployment of intelligent mobile air quality systems NGUYEN VIET DUNG Dung.yn Major: Data Science and Artificial Intelligence (Elitech) Thesis advisor: Assoc. Do Phan Thuan Institute: School of Information and Communication Technology IIA NOI, 09/2022 CỘNG HÒA XÃ HỘI CHỮ NGIĨA. VIỆT NAM Độc lập— Tự do — lạnh phúc BẢN XÁC NHẬẠN CHỈNH SỬA LUẬN VĂN THẠC SĨ Ilo và tên tác giả luận văn: Nguyễn Việt Dững Để tài luận văn: 1riền khai tốt ưu các hệ thông quan trắc không khi di động thong minh Chuyên ngành: Khoa học dữ liệu va Tri tuệ nhân tạo Ma sé SV: 20202342M Tác giả, Người hướng dẫn khoa học và Hội đồng cham luan vin xác nhận tác giả đã sửa chữa, bổ sung luận văn thco biên bản họp Hội đồng ngày 29/10/2022 với các nội dung sau - Thêm giới thiệu chỉ tiết hơn về các nghiên cửu có liên quan trong chương 2. - Đổi tên chương 3 từ “Problem formmulatien & hardness” thanh “Problem formulation”.
- Thém phat biểu về bài toán Øpportunistic sensing optimization trước khi viết tắt thành O8O. - _ Dễi tên phân 3.2 thành “Mathematical fornulatien of OSO”, - Thém giải thích rỗ hơn về hàm mục tiêu và các điều kiện trong mục 3. - Thém ly do gidi thich vi sao sit dung thuat loan quy hoạch động, “In this simplified scenario, our dynamic programming approach guarantees that the set found by the submaxSet function is always maximum. thus the number a mentioned in the previous section 5.2 will be equal to 1.
Later we will show that we cannot use dynamic programming in the general scenario, and we will need another greedy sub-process which has a lower performance ratio for that.” - ‘Thém mét sé pidi thich chi tiét vé cdc thuat ton meta-heuristics va ly đo lựa chọn sử dụng chúng, cụ thể như sau + “They arc approprialc methods to verily cfliciency off the approximation algorithm, since their Wemendous performance in practice was shown in numerous roscarch papers, cspecially researches related to air monitoring systems. If the greedy approximation approach is decent, the experimental results produced SPH.BMII Ban hành lần 1 ngày 11/11/2014 by it should be competitive to the ones produced by the chosen meta- heuristics. It is indeed truc, and we will show the experimental results supporting this observation later in this thesis.” + “Two mela-heuristics, the genclie algorithm and the simulated annealing algorithm, are chosen to solve the OSO problem because of their simplicity and efficiency in practice. Related researches about air monitoring systems also deployed these methods to solve challengmg problems, and the results usually show that they are good choices for creating a solution.” Thêm giải thích cho các hình vẽ và bảng biểu.
-_'Thêm mô tã input và output chơ các thuật toán - Thêm mục 6. “Ởomparison of results beiwccn the approximation algorithm and the meta-heuristics” và chuyển mục 64 cũ thành mục 6. “Discussion” Ngày tháng năm Giáo viên hướng dẫn Tác giả luận văn CHỦ TỊCH HỘI ĐỒNG SPH.BMII Ban hành lần 1 ngày 11/11/2014 Graduation Thesis Assignment Name: Nguyen Viet Dung Phone: 184 399629097 Email: Ding. NV202342M@sis hust edu.vn Student ID: 20202342M Class: 20BKIIDL-E ‘Thesis title: Optimal deployment of intelligent mobile air quality systems ‘Thesis code: 2020BKHI2L-KH0L Affiliation ; Hanoi University of Science and Technology 1 Nguyen Vier Dung - hereby warrants that the work and presentation in this thesis performed by mysclf under the supervision of Assoc.
Prof Do Phan Tharan. All the resulls presented in this thesis are truthful and are not copied from any other works. All references in this thesis including images, tables, figures and, quotes are clearly amd fully documented in the bibliography. T will take full responsibility for even one copy that violates school regulations Hanoi, 28th September, 2022 Author Nguyen Viet Dung Attestation of thesis advisor I certify that the thesis entitled “Optimal deployment of intelligent mobile air quality systems” submitted for the degree of Master d[ Scicncc (M.
Nguyen Viel Dung is the record of research work carried ont by him during the period from 10/2020 to 10/2022 under my guidance and supervision, and that this work has not formed the basis for the award of any Degree, Diploma, Associateship and Fellowship or other Titles in this University or any other University or institution of Higher Leaming. Hanoi, 28th September, 2022 Thesis Advisor Aasac.Prof, Do Phan Thuan List of Figures Figure 1. A map of size 4 x 4 with 3 bus routes and 6 ciitical squares. When k example af the sensor's lumt-on positions on bus 1 is shown.
With such selected posilions, that sensor can observe 5 critical squares A, 8, C,D and £ 17 Figure 2. Illustration of obscrvablz boundary, obscrvable square, and observable scgment. Ilustration of Theorem 3.1’s proof (X is an arbitrary point ona bus route segment P. ¥is the Jaflmost obscrvable bound closest to X.
106 is a critieal square obsarvable by X, then it is also observable by ¥) - 20 Figure 4. Á corcsponding bus map when ổ — 3, V\ — {A, B, €, D. F), V2 — {4, €, DE}, anÄV; ={B, F} 23 Figure 5. The remaining map after removing bus | ftom the map in Fig.
1, and the greedy process continucs. Rach square é can be observed by a sensor tured on at somewhere in the middle of the interval [/», r»]. We then have d critical paints which arc the Iefl endpoints Qa, whers i= 1,. , d) of such inlsrvals 33 Figure 7.
Performance in the simptified sconarie with p = LO, q = 12 ~. Performance in the simplified scenario withp — 25, g — 30. 47 Figure 10, Performance in the simplified scenario with p30, q 36. Performance in the simplified seenario withp = 42, ¢= 50.
Dorformaneo in ths gencral and special scenario wilh p = 10, g = 12.4 Figure 14, Performance in the general and special scenario withp — 30, g — 36.4Ð Figure 15, Performance in the general and special scenario withp = 42, g = 50. 5Ú List of Figures Figure 1. A map of size 4 x 4 with 3 bus routes and 6 ciitical squares. When k example af the sensor's lumt-on positions on bus 1 is shown.
With such selected posilions, that sensor can observe 5 critical squares A, 8, C,D and £ 17 Figure 2. Illustration of obscrvablz boundary, obscrvable square, and observable scgment. Ilustration of Theorem 3.1’s proof (X is an arbitrary point ona bus route segment P. ¥is the Jaflmost obscrvable bound closest to X.
106 is a critieal square obsarvable by X, then it is also observable by ¥) - 20 Figure 4. Á corcsponding bus map when ổ — 3, V\ — {A, B, €, D. F), V2 — {4, €, DE}, anÄV; ={B, F} 23 Figure 5. The remaining map after removing bus | ftom the map in Fig.
1, and the greedy process continucs. Rach square é can be observed by a sensor tured on at somewhere in the middle of the interval [/», r»]. We then have d critical paints which arc the Iefl endpoints Qa, whers i= 1,. , d) of such inlsrvals 33 Figure 7.
Performance in the simptified sconarie with p = LO, q = 12 ~. Performance in the simplified scenario withp — 25, g — 30. 47 Figure 10, Performance in the simplified scenario with p30, q 36. Performance in the simplified seenario withp = 42, ¢= 50.
Dorformaneo in ths gencral and special scenario wilh p = 10, g = 12.4 Figure 14, Performance in the general and special scenario withp — 30, g — 36.4Ð Figure 15, Performance in the general and special scenario withp = 42, g = 50. Research methodology 27 Chapter 5. Meta-heuristic algorithms 38 Chapter 6. Numerical results of approximation algorithms 45 6.
Numerical results of meta-heuristic algorithms 51 6.4, Comparison of resnlls between Ihe approximation algorithm and the mela-heuristics 61 6. Conclusion 63 Published papers 64 References 65 Graduation Thesis Assignment Name: Nguyen Viet Dung Phone: 184 399629097 Email: Ding. NV202342M@sis hust edu.vn Student ID: 20202342M Class: 20BKIIDL-E ‘Thesis title: Optimal deployment of intelligent mobile air quality systems ‘Thesis code: 2020BKHI2L-KH0L Affiliation ; Hanoi University of Science and Technology 1 Nguyen Vier Dung - hereby warrants that the work and presentation in this thesis performed by mysclf under the supervision of Assoc. Prof Do Phan Tharan.
All the resulls presented in this thesis are truthful and are not copied from any other works. All references in this thesis including images, tables, figures and, quotes are clearly amd fully documented in the bibliography. T will take full responsibility for even one copy that violates school regulations Hanoi, 28th September, 2022 Author Nguyen Viet Dung Attestation of thesis advisor I certify that the thesis entitled “Optimal deployment of intelligent mobile air quality systems” submitted for the degree of Master d[ Scicncc (M. Nguyen Viel Dung is the record of research work carried ont by him during the period from 10/2020 to 10/2022 under my guidance and supervision, and that this work has not formed the basis for the award of any Degree, Diploma, Associateship and Fellowship or other Titles in this University or any other University or institution of Higher Leaming.
Hanoi, 28th September, 2022 Thesis Advisor Aasac.Prof, Do Phan Thuan Content Graduation Thesis Assignment Acknowledgements Ahstract Content List of Figures List of Tables Acronyms Chapter 1. Mobile air quality monitoring systems 1. Opportunistic sensing optimization (OSQ) problem 1.4, Structure of thesis Chapter 2. Related works Chapter 3.
Mathematical formulation of OSO. Tlardness of OSO. Meta-heuristic algorithms 24 43. Research methodology 27 Chapter 5.
Meta-heuristic algorithms 38 Chapter 6. Numerical results of approximation algorithms 45 6. Numerical results of meta-heuristic algorithms 51 6.4, Comparison of resnlls between Ihe approximation algorithm and the mela-heuristics 61 6. Conclusion 63 Published papers 64 References 65 Acknowledgements In order to obtain this master's thesis, apart fom my own efforts, it is impossible not to mention the help of many other peopie.
Fitst, T would like to thank Associate Professor Do Phan Thuan and Dir. Nemyen Phi Le, my direct mentors. From the time I got my thesis title to the tims I finished it, there was not a moment that they didnt encourage me to run to the finish line, | am where I am today in large part because of their support Next, I have to mention the funding source of Vinll. Their financial support helped me to pay my tuition fees and complete my studies with peace of mind, Finally, I would like to express my sincerest thanks to my teachers, friends and family.
Without them by my side, | wouldn't have made it to the end of the road Two years of wonderfil feclures and extremely hetpful time doing rescarch will be in ny heart forever. Research methodology 27 Chapter 5. Meta-heuristic algorithms 38 Chapter 6. Numerical results of approximation algorithms 45 6.
Numerical results of meta-heuristic algorithms 51 6.4, Comparison of resnlls between Ihe approximation algorithm and the mela-heuristics 61 6. Conclusion 63 Published papers 64 References 65 List of Figures Figure 1. A map of size 4 x 4 with 3 bus routes and 6 ciitical squares. When k example af the sensor's lumt-on positions on bus 1 is shown.
With such selected posilions, that sensor can observe 5 critical squares A, 8, C,D and £ 17 Figure 2. Illustration of obscrvablz boundary, obscrvable square, and observable scgment. Ilustration of Theorem 3.1’s proof (X is an arbitrary point ona bus route segment P. ¥is the Jaflmost obscrvable bound closest to X.
106 is a critieal square obsarvable by X, then it is also observable by ¥) - 20 Figure 4. Á corcsponding bus map when ổ — 3, V\ — {A, B, €, D.