Optimal deployment of intelligent mobile air quality systems

HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY

MASTER’S GRADUATION THESIS

Optimal deployment of intelligent mobile

air quality systems

NGUYEN VIET DUNG

[email protected]

Major: Data Science and Artificial Intelligence (Elitech)

Thesis advisor: Assoc.Prof. Do Phan Thuan _________________

Institute: School of Information and Communication

Technology

HA NOI, 09/2022

SĐH.QT9.BM11 Ban hành lần 1 ngày 11/11/2014

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.2.

- 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.1.1.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.QT9.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.

- Thêm mục 6.4. “Comparison of results between the approximation

algorithm and the meta-heuristics” và chuyển mục 6.4 cũ thành mục

6.5. “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

3

Name: Nguyen Viet Dung

Phone: +84 399629097 Email : [email protected]

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.Prof. 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.S.) by Mr. 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.Prof. Do Phan Thuan

Graduation Thesis Assignment

4

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.

Acknowledgements

5

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.

Then, we propose a polynomial-time 1

2 -, ����−1

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.96%. Notably, when the

sensors can be on (e.g., enough energy) during the whole route, the ����−1

2����−1 -approximation

algorithm achieves the approximation ratio of (1 − 1

����

). Such ratio, which is almost twice as

����−1

2����−1

, enlarges the average performance ratio to 78.42%.

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.

Abstract

6

Graduation Thesis Assignment 3

Acknowledgements 4

Abstract 5

Content 6

List of Figures 8

List of Tables 9

Acronyms 10

Chapter 1. Introduction 11

1.1. Mobile air quality monitoring systems 11

1.2. Opportunistic sensing optimization (OSO) problem 12

1.3. Thesis contribution 12

1.4. Structure of thesis 12

Chapter 2. Related works 13

Chapter 3. Problem formulation 17

3.1. Problem statement 17

3.2. Mathematical formulation of OSO 18

3.3. Hardness of OSO 22

Chapter 4. Theoretical background 24

4.1. Approximation algorithms 24

4.2. Meta-heuristic algorithms 24

Content