HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY MASTER’S GRADUATION THESIS Optimal deployment of intelligent mobile air quality systems NGUYEN VIET DUNG Dung.vn Major: Data Science and Artificial Intelligence (Elitech) Thesis advisor: Assoc. Do Phan Thuan _________________ Institute: School of Information and Communication Technology HA NOI, 09/2022 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – 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: Nguyễn Việt Dũng Đề tài luận văn: Triển khai tối ưu các hệ thống quan trắc không khí di động thông minh Chuyên ngành: Khoa học dữ liệu và Trí tuệ nhân tạo Mã số SV: 20202342M Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả đã sửa chữa, bổ sung luận văn theo 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 chi 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 formulation & hardness” thành “Problem formulation”. - Thêm phát biểu về bài toán opportunistic sensing optimization trước khi viết tắt thành OSO.
- Đổi tên phần 3.2 thành “Mathematical formulation 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 lý do giải thích vì sao sử dụng thuật toán 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 𝛼𝛼 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ố giải thích chi tiết về các thuật toán meta-heuristics và lý do lựa chọn sử dụng chúng, cụ thể như sau: + “They are appropriate methods to verify efficiency of the approximation algorithm, since their tremendous performance in practice was shown in numerous research papers, especially researches related to air monitoring systems. If the greedy approximation approach is decent, the experimental results produced SĐH.BM11 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 true, and we will show the experimental results supporting this observation later in this thesis.” + “Two meta-heuristics, the genetic 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 challenging 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 cho các thuật toán. “Comparison of results between the approximation algorithm and the meta-heuristics” và chuyển mục 6. 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 SĐH.BM11 Ban hành lần 1 ngày 11/11/2014 Graduation Thesis Assignment Name: Nguyen Viet Dung Phone: +84 399629097 Email : Dung.vn Student ID: 20202342M Class: 20BKHDL-E Thesis title: Optimal deployment of intelligent mobile air quality systems Thesis code: 2020BKHDL-KH01 Affiliation : Hanoi University of Science and Technology I – Nguyen Viet Dung - hereby warrants that the work and presentation in this thesis performed by myself under the supervision of Assoc. Do Phan Thuan.
All the results 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 and fully documented in the bibliography. I 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 of Science (M.
Nguyen Viet Dung is the record of research work carried out 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 Learning. Hanoi, 28th September, 2022 Thesis Advisor Assoc. Do Phan Thuan 3 Acknowledgements In order to obtain this master's thesis, apart from my own efforts, it is impossible not to mention the help of many other people. First, I would like to thank Associate Professor Do Phan Thuan and Dr.
Nguyen Phi Le, my direct mentors. From the time I got my thesis title to the time I finished it, there was not a moment that they didn't encourage me to run to the finish line. I am where I am today in large part because of their support. Next, I have to mention the funding source of VinIF.
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, I wouldn't have made it to the end of the road. Two years of wonderful lectures and extremely helpful time doing research will be in my heart forever.
4 Abstract Monitoring air quality plays a critical role in the sustainable development of developing regions where the air is severely polluted. Air quality monitoring systems based on static monitors often do not provide information about the area each monitor represents or represent only small areas. In addition, they have high deployment costs that reflect the efforts needed to ensure sufficient quality of measurements. Meanwhile, the mobile air quality monitoring system, such as the one in this work, shows the feasibility of solving those challenges.
The system includes environmental sensors mounted on buses that move along their routes, broadening the monitoring areas. In such a system, we introduce a new optimization problem named opportunistic sensing that aims to find (1) optimal buses to place the sensors and (2) the optimal monitoring timing to maximize the number of monitored critical regions. We investigate the optimization problem in two scenarios: simplified and general bus routes. Initially, we mathematically formulate the targeted problem and prove its NP-hardness.
1 𝑒𝑒−1 Then, we propose a polynomial-time 2 -, 2𝑒𝑒−1 - approximation algorithm for the problem with the simplified, general routes, respectively. To show the proposed algorithms’ effectiveness, we have evaluated it on the real data of real bus routes in Hanoi, Vietnam. The evaluation results show that the former algorithm guarantees an average performance ratio of 75.70%, while the latter algorithm achieves the ratio of 63. Notably, when the 𝑒𝑒−1 sensors can be on (e., enough energy) during the whole route, the 2𝑒𝑒−1 -approximation 1 algorithm achieves the approximation ratio of (1 − 𝑒𝑒).
Such ratio, which is almost twice as 𝑒𝑒−1 2𝑒𝑒−1 , enlarges the average performance ratio to 78. To further test the efficiency of the greedy approximation algorithm and optimize the results, we propose two more meta-heuristic algorithms for this problem: genetic algorithm and simulated annealing algorithm. Experiments show that the above meta-heuristic algorithms only increase the goodness of the results by 1% to 3% on average, but have a much larger running time than the greedy algorithm. From there, we see that the approximation algorithm in particular is already a feasible solution in practice without mentioning any other complicated tools.
5 Content Graduation Thesis Assignment 3 Acknowledgements 4 Abstract 5 Content 6 List of Figures 8 List of Tables 9 Acronyms 10 Chapter 1. Mobile air quality monitoring systems 11 1. Opportunistic sensing optimization (OSO) problem 12 1. Structure of thesis 12 Chapter 2.
Related works 13 Chapter 3. Mathematical formulation of OSO 18 3. Hardness of OSO 22 Chapter 4. Meta-heuristic algorithms 24 6 4.
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.
Comparison of results between the approximation algorithm and the meta-heuristics 61 6. Conclusion 63 Published papers 64 References 65 7 List of Figures Figure 1. A map of size 4 × 4 with 3 bus routes and 6 critical squares. When 𝑘𝑘 = 2, an example of the sensor’s turn-on positions on bus 1 is shown.
With such selected positions, that sensor can observe 5 critical squares 𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷 and 𝐸𝐸. Illustration of observable boundary, observable square, and observable segment. Illustration of Theorem 3.1’s proof (𝑋𝑋 is an arbitrary point on a bus route segment 𝑃𝑃. 𝑌𝑌 is the leftmost observable bound closest to 𝑋𝑋.
If 𝐶𝐶 is a critical square observable by 𝑋𝑋, then it is also observable by 𝑌𝑌). A corresponding bus map when 𝛽𝛽 = 3, 𝑉𝑉 1 = {𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷, 𝐹𝐹}, 𝑉𝑉 2 = {𝐴𝐴, 𝐶𝐶, 𝐷𝐷, 𝐸𝐸}, and 𝑉𝑉 3 = {𝐵𝐵, 𝐹𝐹}. The remaining map after removing bus 1 from the map in Fig. 1, and the greedy process continues.
(a) [l Ab , 𝑟𝑟 Ab ] is the unique close segment that contains all sensor’s turn-on positions on the bus route 𝑏𝑏 where the critical square 𝐴𝐴 is observed. Each square 𝑖𝑖 can be observed by a sensor turned on at somewhere in the middle of the interval [l ib , 𝑟𝑟 ib ]. We then have 𝑑𝑑 critical points which are the left endpoints (l ib , where 𝑖𝑖 = 1, … , 𝑑𝑑) of such intervals. Performance in the simplified scenario with 𝑝𝑝 = 10, 𝑞𝑞 = 12.
Performance in the simplified scenario with 𝑝𝑝 = 25, 𝑞𝑞 = 30. Performance in the simplified scenario with 𝑝𝑝 = 30, 𝑞𝑞 = 36. Performance in the simplified scenario with 𝑝𝑝 = 42, 𝑞𝑞 = 50. Performance in the general and special scenario with 𝑝𝑝 = 10, 𝑞𝑞 = 12.
Performance in the general and special scenario with 𝑝𝑝 = 30, 𝑞𝑞 = 36. Performance in the general and special scenario with 𝑝𝑝 = 42, 𝑞𝑞 = 50.50 8 List of Tables Table 1. Meta-heuristics performance compared to the approximation algorithm’s results in the simplified scenario…………………………………………………. Meta-heuristics performance compared to the approximation algorithm’s results in the general scenario.
55 9 Acronyms Abbreviations and terms Meaning OSO Opportunistic sensing optimization GA Genetic algorithm SA Simulated annealing Fig. Mobile air quality monitoring systems The fast industrialization and urbanization, especially in developing countries, cause air pollution in urban areas. According to WHO, the polluted air is the main reason causing 36% of deaths due to lung cancer, 27% of heart attacks, 34% of strokes, and 35% of deaths from respiratory [1]. In such circumstances, it is indispensable to have a comprehensive solution for monitoring air quality on a large scale for citizens and local governments.
Accordingly, there have been many air quality monitoring systems in literature, which can be roughly classified into two main categories: stationary and mobile. The stationary system uses fixed stations to monitor air quality, either outdoor [2] or indoor [3]. The air quality monitoring system operates as a wireless sensor network (WSN) [4–6]. While the sensor nodes monitor the surrounding environment, the base stations are in charge of storing and processing the sensory data On the one hand, the sensor nodes monitor their surrounding environments.
On the other hand, the sensory data is either stored at the sensor’s local memory or transferred to the base station. Despite the wide adoption, the stationary systems still suffer from an inherent critical limitation: the low-resolution sensing data. That is because the fixed monitoring station has the sensed data for only a limited area. Besides, the stations require high deployment and maintenance costs.
It is, therefore, challenging to deploy them densely. For example, in Hanoi, Vietnam, the local government and other organizations have less than 50 stations in the total area of 3329 km2 [7].