Optimal deployment of intelligent mobile air quality systems

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.95 MB, 71 trang )

HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY

MASTER’S GRADUATION THESIS
Optimal deployment of intelligent mobile
air quality systems
NGUYEN VIET DUNG

Major: Data Science and Artificial Intelligence (Elitech)

Thesis advisor:
Institute:

Assoc.Prof. Do Phan Thuan _________________

School of Information and Communication
Technology

HA NOI, 09/2022

123doc
Mang
Ln
thay vì
h■■ng
l■im■i
s■
cam
tr■
h■u
m■t

k■t
nghi■m
t■im■t
là
s■
cáwebsite
nhân
mang
kho
m■ith■
kinh
m■
l■i
d■n
vi■n
nh■ng
cho
doanh
■■u
kh■ng
ng■■i
quy■n
chia
t■ th■c
dùng,
l■
s■l■i
v■i
và
hi■n

t■t
cơng
h■n
mua
ngh■a
nh■t
2.000.000
ngh■
báncho
tài
v■
hi■n
ng■■i
li■u
c■a
tài
th■
hàng
mình
li■u
dùng.
hi■n
■■u
■
thìt■t
Khi
■■i,
s■p
Vi■t
c■

khách
b■n
t■i,
l■nh
Nam.
ngh■a
online
hàng
v■c:
Táctr■
khơng
v■
tài
phong
thành
chính
c■a
khác
chun
c■a
thành
tíngì
d■ng,
hàng
so
nghi■p,
viên
v■i
tri■u
cơng

c■a
b■n
hồn
nhà
ngh■
123doc
g■c.
bán
h■o,
thơng
B■n
và
hàng
■■
n■p
có
tin,
l■i
cao
th■
ti■n
ngo■i
chuy■n
tính
phóng
vào
ng■,...Khách
trách
tài
giao

to,kho■n
nhi■m
thu
sang
nh■
c■a
■■i
■■n
hàng
tùy123doc,
v■i
v■
ý.
cót■ng
qu■n
th■b■n
d■
ng■■i
lýChào
dàng
s■ dùng.
■■■c
m■ng
tra c■u
M■c
h■■ng
b■n
tàitiêu
li■u
■■n

nh■ng
hàng
m■t
v■i■■u
quy■n
cách
123doc.
c■a
chính
l■i123doc.net
sau
xác,n■p
nhanh
ti■n
tr■
chóng.
trên
thành
website
th■ vi■n tài li■u online l■n nh■t Vi■t Nam, cung c■p nh■ng tài li■u ■■c khơng th■ tìm th■y trên th■ tr■■ng ngo■i tr■ 123doc.net.
Nhi■u event thú v■, event ki■m ti■n thi■t th■c. 123doc luôn luôn t■o c■ h■i gia t■ng thu nh■p online cho t■t c■ các thành viên c■a website.

Mangh■n
Ln
Th■a
Xu■t
Sau
Nhi■u
123doc
Link

khi
h■■ng
phát
thu■n
l■i
event
cam
s■
nh■n
xác
m■t
tr■
t■
h■u
k■t
s■
thú
nghi■m
t■i
th■c
ýxác
n■m
t■■ng
m■t
d■ng
v■,
là
s■
nh■n
s■

website
ra
mang
event
kho
m■i
■■■c
■■i,
1.
t■o
tLink
t■
th■
m■
l■i
c■ng
ki■m
■■ng
d■n
123doc
CH■P
g■i
vi■n
xác
nh■ng
cho
■■u
■■ng
ti■n
v■

th■c
h■
kh■ng
ng■■i
NH■N
■ã
■■a
quy■n
th■ng
thi■t
chia
t■ng
s■
ki■m
dùng,
l■
ch■
CÁC
s■
■■■c
th■c.
s■
l■i
b■■c
v■i
ti■n
và
email
chuy■n
■I■U

t■t
cơng
h■n
mua
123doc
g■i
online
kh■ng
nh■t
b■n
2.000.000
v■
ngh■
bán
KHO■N
sang
b■ng
ln
cho
■■a
■ã
tài
■■nh
hi■n
■■ng
ng■■i
li■u
ph■n
ln
ch■

tài
TH■A
tài
v■
th■
li■u
hàng
t■o
email
li■u
thơng
ky,
dùng.
tríhi■n
THU■N
hi■u
c■
c■a
b■n
■■u
■b■n
tin
t■t
h■i
Khi
■■i,
qu■
mình
vui
Vi■t

xác
c■
■ã
khách
gia
lịng
b■n
nh■t,
minh
trong
l■nh
■■ng
Nam.
t■ng
Chào
■■ng
online
hàng
uy
tài
v■c:
l■nh
thu
Tác
m■ng
ky,
tín
kho■n
tr■
nh■p

nh■p
khơng
b■n
tài
phong
v■c
cao
thành
b■n
chính
vui
email
nh■t.
tài
email
online
oLink
khác
chun
■■n
li■u
lịng
thành
tínb■n
Mong
c■a
xác
gì
cho
d■ng,

và
■■ng
v■i
so
nghi■p,
viên
th■c
kinh
■ã
mình
t■t
123doc.
123doc.net!
v■i
mu■n
cơng
■■ng
nh■p
c■a
c■
doanh
s■
b■n
vàcác
hồn
mang
■■■c
ngh■
123doc
click

email
ký
g■c.
online.
thành
v■i
h■o,
Chúng
vào
l■i
thơng
B■n
g■i
c■a
và
123doc.netLink
CH■P
cho
viên
linkí
Tính
■■
v■
n■p
có
mình
tơi
tin,
c■ng
c■a

cao
■■a
th■
■■n
cung
NH■N
ti■n
ngo■i
và
tính
mình
website.
phóng
■■ng
ch■
th■i
click
vào
c■p
CÁC
ng■,...Khách
trách
xác
trong
email
tài
■i■m
D■ch
vào
xã

to,kho■n
■I■U
th■c
nhi■m
h■i
thu
linkơng
l■nh
b■n
tháng
V■
nh■
m■t
s■
KHO■N
c■a
■ã
v■c
(nh■
■■i
hàng
■■■c
tin
tùy
ngu■n
5/2014;
■■ng
123doc,
tài
v■i

xác
■■■c
ý.
có
li■u
TH■A
g■i
t■ng
minh
th■
tài
ky,
123doc
và
v■
mơ
ngun
b■n
b■n
d■
ng■■i
THU■N
tài
kinh
■■a
t■
dàng
kho■n
s■
vui

v■■t
d■■i
doanh
tri
dùng.
■■■c
ch■
lịng
tra
th■c
m■c
email
■ây)
email
c■u
■■ng
Chào
online.
M■c
h■■ng
q
100.000
cho
tài
b■n
b■n
m■ng
tiêu
báu,
nh■p

li■u
Tính
b■n,
■ã
nh■ng
■ã
hàng
phong
m■t
l■■t
■■n
email
■■ng
b■n
tùy
■■ng
■■u
quy■n
cách
truy
thu■c
■■n
th■i
phú,
c■a
ký
ky,
c■a
c■p
chính

v■i
■i■m
v■i
■a
mình
l■i
b■n
vào
123doc.net
m■i
123doc.netLink
d■ng,
123doc.net!
sau
xác,
các
vui
tháng
vàngày,
n■p
click
lịng
“■i■u
nhanh
giàu
5/2014;
ti■n
s■
vào
■■ng

tr■
giá
Kho■n
Chúng
chóng.
h■u
trên
linkc■a
thành
tr■
xác
123doc
nh■p
2.000.000
website
■■ng
th■c
Th■a
tơi
th■
website.
cung
email
v■■t
s■
vi■n
th■i
Thu■n
■■■c
c■p

c■a
thành
mong
m■c
tài D■ch
v■
li■u
mình
g■i
viên
100.000
mu■n
S■
online
v■
và
V■
■■ng
D■ng
click
■■a
t■o
(nh■
l■■t
l■n
ký,
D■ch
■i■u
vào
ch■

nh■t
■■■c
truy
l■t
link
email
ki■n
V■”
vào
c■p
Vi■t
123doc
mơtop
sau
cho
b■n
m■i
Nam,
t■200
■ây
d■■i
cho
ngày,
■ã
cung
các
các
(sau
■■ng
g■i

■ây)
s■
website
c■p
users
■ây
h■u
ky,
cho
nh■ng
■■■c
có
b■n
2.000.000
b■n,
ph■
thêm
vui
tài
bi■n
tùy
g■i
lịng
thu
li■u
thu■c
t■t
thành
nh■t
nh■p.

■■c
■■ng
T■i
vào
t■i
viên
khơng
t■ng
Chính
nh■p
Vi■t
các
■■ng
th■i
“■i■u
th■
Nam,
vì
email
v■y
■i■m,
ký,
tìm
t■
Kho■n
c■a
l■t
123doc.net
th■y
l■chúng

vào
mình
tìm
trên
Th■a
top
ki■m
và
tơi
th■
200
ra
click
Thu■n
cóthu■c
■■i
tr■■ng
các
th■
vào
nh■m
website
c■p
v■
top
link
ngo■i
S■
3nh■t
■áp

123doc
Google.
D■ng
ph■
tr■
■KTTSDDV
■ng
123doc.net.
bi■n
■ã
D■ch
Nh■n
nhu
g■i
nh■t
c■u
V■”
■■■c
theo
t■i
chia
sau
Vi■t
quy■t
danh
■ây
s■ Nam,
tài
(sau
hi■u

...li■u
t■
■ây
do
ch■t
l■c■ng
■■■c
tìm
l■■ng
ki■m
■■ng
g■i
và
thu■c
t■t
bình
ki■m
T■i
ch■n
top
ti■n
t■ng
3 Google.
là
online.
th■i
website
■i■m,
Nh■n
ki■m

chúng
■■■c
ti■ntơi
online
danh
có th■
hi■u
hi■u
c■p
do
qu■
nh■t
c■ng
và ■KTTSDDV
uy
■■ng
tín nh■t.
bình ch■n
theo quy■t
là website
... ki■m ti■n online hi■u qu■ và uy tín nh■t.

Lnh■n
123doc
Sau
Th■a
Xu■t
khi
h■■ng
phát

thu■n
cam
nh■n
m■t
t■k■t
s■
t■i
ýxác
n■m
t■■ng
d■ng
là
s■
nh■n
website
ra
mang
■■i,
1.
t■o
t■l■i
c■ng
■■ng
d■n
123doc
CH■P
nh■ng
■■u
■■ng
h■

NH■N
■ã
quy■n
th■ng
chia
t■ng
ki■m
CÁC
s■s■
l■i
b■■c
ti■n
vàchuy■n
■I■U
t■t
mua
online
kh■ng
nh■t
bán
KHO■N
sang
b■ng
cho
■■nh
thay
ng■■i
ph■n
tài
TH■A

vìv■
li■u
m■i
thơng
dùng.
tríTHU■N
hi■u
m■t
c■atin
Khi
qu■
mình
cá
xác
khách
nhân
nh■t,
minh
trong
Chào
kinh
hàng
uy
tài
l■nh
m■ng
doanh
tín
kho■n
tr■

v■c
cao
thành
b■n
t■
email
nh■t.
tàith■c
■■n
li■u
thành
b■n
Mong
hi■n
và
v■i
viên
kinh
■ã
123doc.
123doc.net!
mu■n
ngh■a
■■ng
c■a
doanh
mang
123doc
v■
kýonline.

c■a
v■i
Chúng
l■ivà
123doc.netLink
mình
cho
Tính
n■p
tơi
c■ng
thì
■■n
cung
ti■n
s■p
■■ng
th■i
vào
c■p
t■i,
xác
tài
■i■m
D■ch
xã
ngh■a
kho■n
th■c
h■itháng

V■
m■t
s■
v■
c■a
(nh■
■■■c
c■a
ngu■n
5/2014;
123doc,
■■■c
c■a
g■i
tài
123doc
hàng
v■
mơ
ngun
b■n■■a
t■
tri■u
s■
v■■t
d■■i
tri
■■■c
ch■
nhà

th■c
m■c
■ây)
email
bán
h■■ng
q
100.000
cho
hàng
b■n
báu,
b■n,
nh■ng
l■i
■ã
phong
l■■t
chuy■n
tùy
■■ng
quy■n
truy
thu■c
phú,
ky,
c■p
giao
■a
l■i

b■n
vào
m■i
sang
d■ng,
sau
các
vuingày,
n■p
■■n
lịng
“■i■u
giàu
ti■n
s■
■■ng
v■
giá
Kho■n
h■u
qu■n
trên
tr■
nh■p
2.000.000
website
■■ng
Th■a
lý hồn
email

th■i
Thu■n
h■o,
c■a
thành
mong
v■
■■
mình
viên
mu■n
S■
cao
và
■■ng
D■ng
tính
click
t■otrách
ký,
D■ch
■i■u
vàol■t
link
nhi■m
ki■n
V■”
vào
123doc
top

sau
cho
■■i
200
■ây
cho
v■i
■ãcác
các
(sau
g■i
t■ng
website
users
■ây
ng■■i
■■■c
cóph■
dùng.
thêm
bi■n
g■i
thu
M■c
t■t
nh■t
nh■p.
T■i
tiêu
t■i

t■ng
hàng
Chính
Vi■tth■i
■■u
Nam,
vì v■y
■i■m,
c■a
t■123doc.net
l■
123doc.net
chúng
tìm ki■m
tơiracó
tr■
thu■c
■■i
th■
thành
nh■m
c■p
topth■
3nh■t
■áp
Google.
vi■n
■KTTSDDV
■ng
tàiNh■n

nhu
li■uc■u
online
■■■c
theo
chia
l■n
quy■t
danh
s■nh■t
tài
hi■u
...li■u
Vi■t
do
ch■t
Nam,
c■ng
l■■ng
cung
■■ng
và
c■p
bình
ki■m
nh■ng
ch■n
ti■ntài
là
online.

website
li■u ■■cki■m
khơng
ti■n
th■
online
tìm th■y
hi■utrên
qu■th■
và tr■■ng
uy tín nh■t.
ngo■i tr■ 123doc.net.
Ln
Th■a
Xu■t
Sau
Nhi■u
123doc
Mang
thayh■n
khi
vì
h■■ng
phát
thu■n
l■i
event
m■i
cam
s■

nh■n
m■t
tr■
t■
h■u
m■t
k■t
s■
thú
nghi■m
t■i
ýxác
n■m
t■■ng
m■t
d■ng
v■,
là
s■
cá
nh■n
website
ra
nhân
mang
event
kho
m■i
■■i,
1.

t■o
t■
th■
kinh
m■
l■i
c■ng
ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
cho
doanh
■■u
■■ng
ti■n
h■
kh■ng
ng■■i
NH■N
■ã
quy■n
th■ng
thi■t
chia
t■t■ng
ki■m

th■c
dùng,
l■
CÁC
s■
th■c.
s■
l■i
b■■c
v■i
ti■n
và
hi■n
chuy■n
■I■U
t■t
cơng
h■n
mua
123doc
online
kh■ng
ngh■a
nh■t
2.000.000
ngh■
bán
KHO■N
sang
b■ng

ln
cho
tài
■■nh
v■
hi■n
ng■■i
li■u
ph■n
ln
c■a
tài
TH■A
tài
v■
th■
li■u
hàng
t■o
mình
li■u
thơng
dùng.
tríhi■n
THU■N
hi■u
c■
c■a
■■u
■

thìtin
t■t
h■i
Khi
■■i,
qu■
s■p
mình
Vi■t
xác
c■
khách
gia
b■n
t■i,
nh■t,
minh
trong
l■nh
Nam.
t■ng
Chào
ngh■a
online
hàng
uy
tài
v■c:
l■nh
thu

Tác
m■ng
tín
kho■n
tr■
nh■p
khơng
v■
tài
phong
v■c
cao
thành
b■n
chính
c■a
email
nh■t.
tài
online
khác
chun
■■n
c■a
li■u
thành
tínb■n
Mong
gì
cho

d■ng,
và
hàng
v■i
so
nghi■p,
viên
kinh
■ã
t■t
123doc.
123doc.net!
v■i
mu■n
tri■u
cơng
■■ng
c■a
c■
doanh
b■n
các
hồn
nhà
mang
ngh■
123doc
ký
g■c.
online.

thành
bán
v■i
h■o,
Chúng
l■i
thơng
B■n
và
hàng
123doc.netLink
cho
viên
Tính
■■
n■p
có
tơi
tin,
c■ng
l■i
c■a
cao
th■
■■n
cung
ti■n
ngo■i
chuy■n
tính

website.
phóng
■■ng
th■i
vào
c■p
ng■,...Khách
trách
xác
tài
■i■m
D■ch
giao
xã
to,kho■n
th■c
nhi■m
h■i
thu
sang
tháng
V■
nh■
m■t
s■
c■a
(nh■
■■i
■■n
hàng

■■■c
tùy
ngu■n
5/2014;
123doc,
v■i
v■
■■■c
ý.
cóg■i
t■ng
qu■n
th■
tài
123doc
v■
mơ
ngun
b■n
d■
ng■■i
lý,
■■a
t■
dàng
s■
cơng
v■■t
d■■i
tri

dùng.
■■■c
ch■
tra
th■c
ngh■
m■c
■ây)
email
c■u
M■c
h■■ng
q
hi■n
100.000
cho
tài
b■n
tiêu
báu,
li■u
b■n,
th■
nh■ng
■ã
hàng
phong
m■t
l■■t
hi■n

tùy
■■ng
■■u
quy■n
cách
truy
thu■c
■■i,
phú,
ky,
c■a
c■p
chính
■a
b■n
l■i
b■n
vào
123doc.net
m■i
d■ng,
sau
online
xác,
các
vuingày,
n■p
lịng
“■i■u
nhanh

giàu
khơng
ti■n
s■
■■ng
tr■
giá
Kho■n
chóng.
h■u
trên
khác
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
gìth■
so
email
vi■n
th■i
v■i
Thu■n
c■a
thành
b■n
mong

tài v■
li■u
mình
g■c.
viên
mu■n
S■
online
và
B■n
■■ng
D■ng
click
t■o
l■n
cóký,
D■ch
■i■u
vào
th■
nh■t
l■t
link
phóng
ki■n
V■”
vào
Vi■t
123doc
top

sau
cho
to,
Nam,
200
thu
■ây
cho
■ã
cung
nh■
các
các
(sau
g■iwebsite
tùy
c■p
users
■ây
ý.nh■ng
■■■c
cóph■
thêm
tài
bi■n
g■i
thu
li■u
t■t
nh■t

nh■p.
■■c
T■it■i
khơng
t■ng
Chính
Vi■tth■i
th■
Nam,
vì v■y
■i■m,
tìm
t■123doc.net
th■y
l■chúng
tìm
trên
ki■m
tơi
th■
racóthu■c
■■i
tr■■ng
th■nh■m
c■p
top
ngo■i
3nh■t
■áp
Google.

tr■
■KTTSDDV
■ng
123doc.net.
Nh■n
nhu c■u
■■■c
theo
chiaquy■t
danh
s■ tài
hi■u
...li■udo
ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.
Chia
m■t
u■t
Nhi■u
Mang
Ln
123doc
Th■a

Xu■t
Sau
tri■n
phát
khi
h■n
member
s■
h■■ng
phát
khai
thu■n
l■i
event
s■
cam
nh■n
câu
t■
m■t
tr■
t■
event
h■u
ýk■t
s■
chuy■n
thú
nghi■m
t■i

ýkhơng
t■■ng
xác
n■m
t■■ng
m■t
d■ng
v■,
là
khuy■n
s■
nh■n
website
ra
mang
m■y
event
t■o
kho
thành
m■i
■■i,
1.
t■o
t■
mãi
c■ng
th■
n■i
m■

l■i
c■ng
ki■m
■■ng
d■n
cơng
123doc
CH■P
th■
vi■n
b■t
nh■ng
cho
■■ng
■■u
■■ng
ti■n
trên
n■p
h■
c■a
kh■ng
ng■■i
NH■N
■ã
quy■n
th■ng
123doc
thi■t
chia

ki■m
v■i
c■ng
t■ng
ki■m
dùng,
l■
CÁC
s■
nh■ng
th■c.
ti■n
s■
l■i
b■■c
■■ng
v■i
ti■n
-và
ki■m
chuy■n
■I■U
t■t
cơng
online
h■n
mua
123doc
online
■u

kh■ng
123doc
nh■t
5■ãi
2.000.000
ngh■
bán
KHO■N
tri■u
b■ng
sang
b■ng
ln
cho
c■c
tài
■■nh
■ã
hi■n
ch■
tài
ng■■i
li■u
ph■n
ln
k■
tài
TH■A
xu■t
li■u

tài
v■
v■i
th■
li■u
h■p
hàng
t■o
li■u
thơng
s■c
dùng.
trí
hi■u
7hi■n
THU■N
hi■u
d■n.
tài
c■
c■a
■■u
■■■ng
li■u!
tin
qu■
t■t
h■i
Khi
■■i,

qu■
mình
■■ng
Vi■t
xác
c■
khách
gia
nh■t,
Nghe
trong
b■n
nh■t,
minh
trong
l■nh
Nam.
t■ng
Chào
b■online
có
uy
hàng
danh
l■
uy
tài
v■c:
l■nh
thu

Tác
v■
tín
m■ng
nhé,
tín
kho■n
tr■
sách
cao
nh■p
khó
khơng
tài
phong
v■c
cao
tr■■c
thành
b■n
chính
nh■t.
tin
Top
email
nh■t.
tài
online
khác
nh■ng

chun
■■n
li■u
tiên
thành
danh
tín
Mong
b■n
Mong
gì
cho
d■ng,
và
hãy
v■i
■ây
so
thu
nghi■p,
viên
kinh
■ã
mu■n
t■t
123doc.
123doc.net!
cùng
v■i
mu■n

cao
là
cơng
■■ng
c■a
c■
doanh
b■n
con
nh■t
mang
tìm
các
hồn
mang
ngh■
123doc
s■
ký
g■c.
hi■u
online.
thành
tháng
v■i
l■i
hồn
h■o,
Chúng
l■i

thơng
B■n
thơng
cho
và
123doc.netLink
cho
viên
t■o
tồn
Tính
■■
n■p
có
c■ng
tơi
tin,
c■ng
tin
c■
c■a
cao
th■
chính
■■n
cung
ti■n
ngo■i
v■
h■i

■■ng
tính
website.
phóng
■■ng
Khách
th■i
vào
c■p
xác
gia
ng■,...Khách
trách
xác
xã
tài
t■ng
■i■m
mà
D■ch
xã
to,
hàng
h■i
kho■n
th■c
nhi■m
h■i
BQT
thu

thu
m■t
tháng
V■
có
nh■
m■t
s■
nh■p
123doc
c■a
th■
(nh■
■■i
hàng
ngu■n
■■■c
tùy
ngu■n
5/2014;
123doc,
d■
v■i
online
■■■c
ý.
có
■ã
dàng
tài

g■i
t■ng
th■
tài
thu
123doc
ngun
cho
v■
mơ
ngun
b■n
tra
d■
ng■■i
th■p
t■t
■■a
t■
c■u
dàng
s■
v■■t
tri
d■■i
c■
■■■c
tri
dùng.
■■■c

ch■
tài
th■c
các
tra
th■c
m■c
li■u
■ây)
email
c■u
sau
thành
q
M■c
h■■ng
q
m■t
100.000
cho
■■t
tài
báu,
b■n
tiêu
báu,
viên
li■u
cách
b■n,

t■ng
nh■ng
phong
■ã
hàng
phong
c■a
m■t
l■■t
chính
tùy
■■ng
k■t
■■u
website.
phú,
quy■n
cách
truy
thu■c
phú,
doanh
xác,
ky,
c■a
c■p
■a
chính
■a
nhanh

l■i
b■n
vào
d■ng,
thu
123doc.net
m■i
d■ng,
sau
xác,
các
vui
tháng
chóng.
ngày,
n■p
giàu
lịng
“■i■u
nhanh
giàu
11
ti■n
giá
s■
■■ng
tr■
giá
uy
Kho■n

chóng.
h■u
tr■
trên
tín
thành
tr■
nh■p
■■ng
cao
2.000.000
website
■■ng
Th■a
th■
nh■t.
email
th■i
vi■n
th■i
Thu■n
Mong
mong
c■a
thành
mong
tài v■
li■u
mình
mu■n

mu■n
viên
mu■n
S■
online
và
■■ng
D■ng
mang
t■o
click
t■o
l■n
■i■u
ký,
D■ch
■i■u
vào
l■i
nh■t
l■t
cho
link
ki■n
ki■n
V■”
vào
Vi■t
c■ng
123doc

cho
top
sau
cho
Nam,
■■ng
cho
200
■ây
cho
■ã
cung
các
các
các
(sau
g■i
xãusers
website
h■i
c■p
users
■ây
m■t
nh■ng
có
■■■c
cóph■
thêm
ngu■n

thêm
tài
bi■n
g■i
thu
thu
li■u
tài
t■t
nh■p.
nh■t
nh■p.
ngun
■■c
T■it■i
Chính
khơng
t■ng
Chính
Vi■t
tri th■c
th■i
vìth■
Nam,
vìv■y
v■y
q
■i■m,
tìm
123doc.net

t■123doc.net
báu,
th■y
l■chúng
tìm
phong
trên
ki■m
tơi
ra
th■
ra
phú,
có
■■i
thu■c
■■i
tr■■ng
th■
■Sau
nh■m
nh■m
c■p
top
ngo■i
h■n
■áp
3nh■t
■áp
Google.

m■t
■ng
tr■
■KTTSDDV
■ng
123doc.net.
n■m
nhu
Nh■n
nhuc■u
rac■u
■■i,
■■■c
chia
theo
chia
123doc
s■
quy■t
danh
s■tàitài
hi■u
li■u
■ã
...li■u
t■ng
ch■t
do
ch■t
c■ng

b■■c
l■■ng
l■■ng
■■ng
kh■ng
vàvàki■m
bình
ki■m
■■nh
ch■n
ti■n
ti■n
v■
online.
là
online.
tríwebsite
c■a mình
ki■m
trong
ti■nl■nh
online
v■c
hi■u
tài li■u
qu■và
vàkinh
uy tín
doanh
nh■t.online

Nhi■u
Mang
Ln
123doc
Th■a
Xu■t
Sau
khi
h■n
h■■ng
phát
thu■n
l■i
event
s■
cam
nh■n
m■t
tr■
t■
h■u
k■t
s■
thú
nghi■m
t■i
ýxác
n■m
t■■ng

m■t
d■ng
v■,
là
s■
nh■n
website
ra
mang
event
kho
m■i
■■i,
1.
t■o
t■
th■
m■
l■i
c■ng
ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
cho
■■u
■■ng

ti■n
h■
kh■ng
ng■■i
NH■N
■ã
quy■n
th■ng
thi■t
chia
t■ng
ki■m
dùng,
l■
CÁC
s■
th■c.
s■
l■i
b■■c
v■i
ti■n
vàchuy■n
■I■U
t■t
cơng
h■n
mua
123doc
online

kh■ng
nh■t
2.000.000
ngh■
bán
KHO■N
sang
b■ng
ln
cho
tài
■■nh
hi■n
ng■■i
li■u
ph■n
ln
tài
TH■A
tài
v■
th■
li■u
hàng
t■o
li■u
thơng
dùng.
tríhi■n
THU■N

hi■u
c■
c■a
■■u
■ tin
t■t
h■i
Khi
■■i,
qu■
mình
Vi■t
xác
c■
khách
gia
b■n
nh■t,
minh
trong
l■nh
Nam.
t■ng
Chào
online
hàng
uy
tài
v■c:
l■nh

thu
Tác
m■ng
tín
kho■n
tr■
nh■p
khơng
tài
phong
v■c
cao
thành
b■n
chính
email
nh■t.
tài
online
khác
chun
■■n
li■u
thành
tínb■n
Mong
gì
cho
d■ng,
và

v■i
so
nghi■p,
viên
kinh
■ã
t■t
123doc.
123doc.net!
v■i
mu■n
cơng
■■ng
c■a
c■
doanh
b■n
các
hồn
mang
ngh■
123doc
ký
g■c.
online.
thành
v■i
h■o,
Chúng
l■i

thơng
B■n
và
123doc.netLink
cho
viên
Tính
■■
n■p
có
tơi
tin,
c■ng
c■a
cao
th■
■■n
cung
ti■n
ngo■i
tính
website.
phóng
■■ng
th■i
c■p
thay
ng■,...Khách
trách
xác

■i■m
D■ch
xã
to,
vì th■c
nhi■m
m■i
h■i
thutháng
V■
nh■
m■t
s■(nh■
■■i
hàng
■■■c
tùy
ngu■n
5/2014;
cáv■i
nhân
■■■c
ý.
cóg■i
t■ng
th■
tài
123doc
kinh
v■

mơ
ngun
d■
ng■■i
doanh
■■a
t■
dàng
v■■t
d■■i
tri
dùng.
ch■
t■
tra
th■c
m■c
■ây)
th■c
email
c■u
M■c
q
100.000
cho
tài
hi■n
b■n
tiêu
báu,

li■u
b■n,
ngh■a
■ã
hàng
phong
m■t
l■■t
tùy
■■ng
■■u
cách
truy
v■
thu■c
phú,
ky,
c■a
c■a
c■p
chính
■a
b■n
vào
mình
123doc.net
m■i
d■ng,
xác,
các

vuingày,
thì
lịng
“■i■u
nhanh
giàu
s■p
s■
■■ng
tr■
giá
t■i,
Kho■n
chóng.
h■u
thành
tr■
ngh■a
nh■p
2.000.000
■■ng
Th■a
th■
email
v■vi■n
th■i
Thu■n
c■a
c■a
thành

mong
tài
c■a
v■
li■u
mình
viên
hàng
mu■n
S■
online
và
■■ng
D■ng
tri■u
click
t■o
l■n
ký,
D■ch
■i■u
vào
nhà
nh■t
l■t
link
bán
ki■n
V■”
vào

Vi■t
123doc
hàng
top
sau
cho
Nam,
200
l■i
■ây
cho
■ã
chuy■n
cung
các
các
(sau
g■iwebsite
c■p
users
■ây
giao
nh■ng
■■■c
cósang
ph■
thêm
tài
bi■n
g■i

■■n
thu
li■u
t■t
nh■t
v■
nh■p.
■■c
T■i
qu■n
t■i
khơng
t■ng
Chính
Vi■t
lý th■i
quy■n
th■
Nam,
vì v■y
■i■m,
tìm
l■i
t■123doc.net
th■y
l■
sau
chúng
tìm
trên

n■p
ki■m
tơi
th■
ti■n
racóthu■c
■■i
tr■■ng
trên
th■nh■m
c■p
website
top
ngo■i
3nh■t
■áp
Google.
tr■
■KTTSDDV
■ng
123doc.net.
Nh■n
nhu c■u
■■■c
theo
chiaquy■t
danh
s■ tài
hi■u
...li■udo

ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

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

Chun 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
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

by it should be competitive to the ones produced by the chosen metaheuristics. 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
Giáo viên hướng dẫn

tháng

năm

Tác giả luận văn

CHỦ TỊCH HỘI ĐỒNG

SĐH.QT9.BM11

Ban hành lần 1 ngày 11/11/2014
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

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
3

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

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

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

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

𝑒𝑒−1

2𝑒𝑒−1

-approximation

algorithm achieves the approximation ratio of (1 − 𝑒𝑒). Such ratio, which is almost twice as
𝑒𝑒−1

, enlarges the average performance ratio to 78.42%.

2𝑒𝑒−1

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

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Content
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
6

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

6.1. Experimental settings

42

6.2. Numerical results of approximation algorithms

45

6.3. Numerical results of meta-heuristic algorithms

51

6.4. Comparison of results between the approximation algorithm and the meta-heuristics 61
6.5. Discussion

61

Chapter 7. Conclusion

63

Published papers

64

References

65

7

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

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 𝐸𝐸. ................................................17

Figure 2. Illustration of observable boundary, observable square, and observable segment.
..............................................................................................................................................19
Figure 3. 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 𝑌𝑌). ...........................................................................................20

Figure 4. A corresponding bus map when 𝛽𝛽 = 3, 𝑉𝑉 1 = {𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷, 𝐹𝐹}, 𝑉𝑉 2 = {𝐴𝐴, 𝐶𝐶, 𝐷𝐷, 𝐸𝐸},
and 𝑉𝑉 3 = {𝐵𝐵, 𝐹𝐹}. ..................................................................................................................23

Figure 5. The remaining map after removing bus 1 from the map in Fig. 1, and the greedy
process continues.. ...............................................................................................................29
Figure 6. (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. (b) There are 𝑑𝑑 critical squares

observed by turning on sensor from bus route 𝑏𝑏 (in this figure, 𝑑𝑑 = 5). 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.
..............................................................................................................................................33
Figure 7. Efficiency heatmap.. ............................................................................................45
Figure 8. Performance in the simplified scenario with 𝑝𝑝 = 10, 𝑞𝑞 = 12. ..............................46
Figure 9. Performance in the simplified scenario with 𝑝𝑝 = 25, 𝑞𝑞 = 30. ..............................47
Figure 10. Performance in the simplified scenario with 𝑝𝑝 = 30, 𝑞𝑞 = 36. ............................47
Figure 11. Performance in the simplified scenario with 𝑝𝑝 = 42, 𝑞𝑞 = 50. ............................47

Figure 12. Performance in the general and special scenario with 𝑝𝑝 = 10, 𝑞𝑞 = 12. ..............48
Figure 14. Performance in the general and special scenario with 𝑝𝑝 = 30, 𝑞𝑞 = 36. ..............49
Figure 15. Performance in the general and special scenario with 𝑝𝑝 = 42, 𝑞𝑞 = 50. ..............50
8

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

List of Tables
Table 1. Notation list………………………………………………………………...…… 18
Table 2. Meta-heuristics performance compared to the approximation algorithm’s results in
the simplified scenario…………………………………………………...……………….. 51
Table 3. Meta-heuristics performance compared to the approximation algorithm’s results in
the general scenario. ............................................................................................................ 55

9

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

Fig.

Figure

10

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Chapter 1. Introduction
1.1. 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].
Unlike the stationary system, the mobile one makes use of mobile sensors to broaden the
monitoring areas. The sensors can leverage unmanned aerial vehicles (UAVs) [8,9] or landbased ones [10]. Despite having a significant advantage in capturing spatial information, the
UAV-based approach copes with many critical issues, including high deployment cost,
energy constraint, etc. Therefore, this work focuses on the mobile air monitoring approach
that exploits land-based vehicles. We consider the public buses, on which a battery-powered
sensor senses the environmental information along the bus route. In such a system, it is
essential to determine which buses to place the sensors on and schedule the measurement,
considering the limited number of sensors and their battery capacity constraint.

11

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

1.2. Opportunistic sensing optimization (OSO) problem
This thesis addresses the issues of the vehicle-based mobile air quality monitoring system.
We form a novel optimization problem named opportunistic sensing optimization (OSO),
which is as follows. Given the 𝑛𝑛 bus routes’ trajectories, each bus route includes two paths

sharing endpoints, the 𝑚𝑚 available monitoring sensors, and the locations of critical regions

that need to be monitored. Each sensor can measure at most 𝑘𝑘 positions on each bus path
due to the energy and computational resource constraints. The OSO problem then asks to

determine 𝑚𝑚 optimal buses to place the sensors and 2𝑘𝑘 positions on each sensor’s bus route

to perform the air quality measurement. The objective is to maximize the number of
observable critical regions. OSO can be seen as a hybrid problem that jointly optimizes the
trajectory (i.e., the bus route) and the schedule (the positions to perform the measurement)

of the mobile sensors.

1.3. Thesis contribution
• We provide a theoretical model and prove the NP-hardness of the OSO problem.
• We propose the polynomial-time constant approximations for the OSO problem. More
specifically, in general, our algorithm guarantees the performance ratio of

𝑒𝑒−1

2𝑒𝑒−1

. In a

simplified case where the two paths of each bus route are identical, the guaranteed
performance ratio of our algorithm is
performance ratios.

1

. We present theoretical proofs about these

2

• We utilize two meta-heuristics algorithms: genetic algorithm and simulated annealing, to
further verify the efficiency of the approximation algorithm. Experimental results showed
that these meta-heuristics helped increase only 1-3% the number of observable critical
squares on average, and they were slower than the simple greedy approach.
• We present extensive experiments to evaluate the proposed algorithms’ performance.

1.4. Structure of thesis

The remainder of the thesis is organized as follows. Chapter 2 presents the related works.
We formulate the OSO problem and prove its NP-hardness in Chapter 3. Chapter 4 is a brief
explanation about the techniques used to solve OSO in this thesis. Chapter 5 describes our
proposed algorithms and theoretical analysis about their effectiveness. The algorithms’
performance in practice is discussed in Chapter 6. In the end, chapter 7 concludes the thesis.

12

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Chapter 2. Related works
There are many efforts in the previous works aiming to build air monitoring systems.
However, most of them use static monitoring sensors. The works in [10,11] introduced a

concept similar to our investigated system. However, they focus on realizing the sensor
device, systems rather than optimizing the deployment. The OSO problem in this work is
close to the sensor placement optimization and scheduling under the target coverage
constraint in static WSNs and mobile WSNs.
In [12], the relay node placement problem is mathematically formulated as an NP-hard
Steiner minimum tree problem with a minimum number of Steiner points and bounded edge
length. The authors then proposed two heuristic algorithms whose performance ratios are
2.5 and 3.0, respectively. In [13], F. Senel et al. proposed to divide the target coverage
problem into sub-problems, each of which contains only three sensors. In [14], Anxing Shan
et al. considered a network comprised of omnidirectional probabilistic sensors. The authors
studied how to activate the least number of sensors to detect all targets with a probability
higher than a threshold 𝜖𝜖. In [15], the authors investigated the optimal deployment in the
wireless rechargeable sensor networks. Specifically, they studied how to deploy a minimum
number of sensors to cover all the targets under the sensors’ limited sensing angle and the
mobile charger’s energy constraint. The problem of deterministic deployment in 3D
underwater WSN is addressed in [16]. The authors exploited a nature-inspired evolutionary
algorithm named Cuckoo search to determine the optimal position for placing sensors. The
objective is to maximize the target coverage capability with a minimum number of sensors.
The authors in [17] addressed, at the same time, the target coverage, connectivity, and fault
tolerance problems in wireless sensor networks. They proposed a hybrid algorithm that
combines the greedy approach and spanning tree technique to determine a minimal number
of sensors. Unfortunately, all of the algorithms mentioned above consider only networks
with static sensors.
Concerning the target coverage problem in mobile WSNs, there are relatively rare related
works. In this chapter we highlight four remarkable researches related to our problem, which
are [18], [19], [20] and [21].
In [18], the authors considered the target coverage problem to minimize the moving distance
of all sensors. The problem was named k-Sink Minimum Movement Target Coverage (k13

luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

MMTC). m): They have k sink stations to send mobile sensors and to cover all targets on an
Euclidean space, k-MMTC is to schedule the sensor movement trajectories and minimize
the sum of moving distance. They proved that k-MMTC was NP-hard.
To solve that problem, they proposed a polynomial-time approximation scheme (PTAS),
named Energy Effective Movement Algorithm (EEMA). They divided EEMA into two
phases. In the first phase, they proposed a novel method to divide the surveillance region
into some sub-areas according to the locations of targets. The sensors in the same sub-area
can cover the same target set. In the second phase, they scheduled the mobile sensors and
move the sensors to cover all targets. They proved that ∀ε > 0, EEMA can be an (1+ε)2

approximation algorithm for k-MMTC problem that runs in time O(𝑛𝑛1/𝜀𝜀 ). For large scale
networks, they proposed a distributed version named D-EEMA. In particular, to keep the

connectivity of the sensors, they used some mobile sensors for communication. They called
these sensors as communication sensors which do not have sensing tasks. The
communication sensors just need to move around the targets and the stations to collect
sensing data. D-EEMA was divided into two phases. In the first phase, they divided the
surveillance region into some subareas and got the positions of the targets. In the second
phase, they grouped the targets and dealt with different groups respectively. They also
provided experiments to validate the effectiveness and efficiency of EEMA and D-EEMA.
In all, EEMA was the first PTAS for sensor movement scheduling for target coverage
problem.
Nguyen et al. in [19] focused on mobile WSNs where the sensors cannot cover all the targets.
In mobile wireless sensor networks, the movement of sensors consumes much more power
than that in sensing and communication. In that research, the targets are weighted by their
importance. The more important a target is given a higher weight. These requirements make
the problem interesting, and also difficult. The aim of that study is to study a more general
and practical problem in terms of target coverage and network connectivity, namely the
Maximum Weighted Target Coverage and Sensor Connectivity with Limited Mobile
Sensors (TAR-CC) problem. Originally, the TAR-CC problem is to schedule a limited
number of mobile sensors to appropriate locations to cover targets and form a connected
network such that the total weight of the covered targets is maximized. In addition, when the
transmission range is assumed to be large enough for any communication, a subproblem of
the TAR-CC problem, termed the Reduced TAR-CC (RTARCC) problem was also
introduced.
An approximation algorithm, termed the weighted maximum-coverage-based algorithm
(WMCBA), with an approximation ratio of 1−1/e is proposed for the RTARCC problem,
where e denotes the base of the natural logarithm, was proposed. In the WMCBA, all
14

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

possible sets of targets that can be covered by a mobile sensor located at any point in the
sensing field are considered. Then, a greedy method is used to select suitable sets of targets
to be covered by mobile sensors. Based on the WMCBA, the Steiner-tree-based algorithm
(STBA) is proposed for the TAR-CC problem. In the STBA, the Fermat points and a nodeweighted Steiner tree algorithm are used to find a tree such that the number of mobile sensors
deployed by the tree structure to form a connected network is minimized. Simulation results
demonstrate that even if the number of mobile sensors is high enough such that a connected
network can always be formed to cover all targets, the STBA requires a significantly lower
total movement distance than the best solution proposed for the MSD problem. In addition,
when the mobile sensors may be not enough to cover all targets, the STBA works better than
the greedy method proposed in the simulation section of that paper.
In [20], Rout et al. addressed the target coverage problem with the consideration of obstacle
avoidance. In that piece of work, they proposed a localized self-deployment scheme, named
as Obstacle Avoidance Target Involved Deployment Algorithm (OATIDA), for deployment
of randomly scattered mobile sensor nodes to cover predefined targets while maintaining

connectivity with the base station in the presence of obstacles. The proposed deployment
scheme is based on the following assumptions. They were: (i) All the sensor nodes have
locomotion capability and can move independently, (ii) The base station is fixed in any place
inside the region of interest and bears all the information about the targets. (iii) Initially, all
the sensor nodes are randomly deployed within the communication range of the base station
(iv) Each sensor node has one unique ID, (v) Every sensor node has the ability to know its
own coordinates by some localization method (e.g., GPS, triangulation and multilateration),
(vi) Every sensor node is able to acquire the relative position of the other sensor nodes within
its communication range, (vii) All the sensor nodes have circular sensing and communication
areas, (viii) The sensing field contains obstacles of arbitrary shapes, and (ix) Every sensor
node is able to detect the shape and position of any obstacles in its sensing range and can
calculate the nearest distance from the obstacle by using the time-of-flight method.
They used the concept of potential field theory and relative neighborhood graph for selfdeployment of mobile sensor nodes in an unknown environment to achieve target coverage
while preserving connectivity with the base station. Their proposed approach is localized in
the sense that each decision taken by the sensor node is strictly based on information
acquired from its neighboring sensors that are part of the relative neighborhood graph. That
algorithm works well in scenarios of single target, multiple targets and moving targets in the
presence of single or multiple obstacles. The proposed algorithm preserves connectivity
during the deployment procedure and minimizes the number of sensor nodes to maintain the
connectivity so that large numbers of sensor nodes are available for monitoring targets.

15

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

The problem of minimizing the mobile sensors’ moving distance under the target coverage
constraint is re-visited by Choudhuri et al. in [21]. The existing sensor relocation algorithms
for target coverage and connectivity are based on the assumption of the free mobility models.
Under these models, each sensor can move any amount in any direction. But for real life
situations, the movement of the sensors may be restricted. Here they intended to solve the
problem of target coverage with a rectilinear mobility model where a sensor can move only
along two mutually perpendicular directions. Since the (x, y) coordinates of a location can
be transformed to another set of coordinates by a simple rotation, they assumed in that paper
that a sensor can move along directions parallel to the x and y-axes only. Thus, if a sensor
moves from point u to v, the distance covered by it is the Manhattan Distance between u and
v.
Their algorithm worked in two phases. In the first phase, a subset of sensors are moved to
new locations such that all targets are covered. The sensors which are essential to ensure
coverage are called assigned sensors. Only if the first phase results in some assigned sensors
not connected to BS, the second phase is initiated to move some unassigned sensors to
achieve connectivity. The proposed algorithm initiates movement of the sensors only if it is
strictly necessary. Even though that work gives a way of relocating sensors when the initial
deployment does not ensure coverage, it can be also used at a later stage when some of the

sensors die out resulting in either loss of coverage or connectivity.
All existing works above on mobile WSNs focus only on either the trajectory or the sensors’
schedule. This thesis takes a more general approach, in which we address at the same time
both the optimal trajectories to place the mobile sensors and the optimal positions to perform
the measurement. We establish a complete process from formulating to solving our problem
and conducting experiments, which makes the results valuable in research and applicable in
real-life cases.

16

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Chapter 3. Problem formulation

3.1. Problem statement
We introduce a new problem named opportunistic sensing optimization (OSO). A map of
bus routes is given on a grid of 𝑝𝑝 × 𝑞𝑞 squares on a 2-dimensional plane (𝑝𝑝 and 𝑞𝑞 are
predefined integers). Each square is marked either critical or non-critical. The critical
squares are regions that need to be monitored. The grid has a total of 𝑐𝑐 critical squares (𝑐𝑐 ≤
𝑝𝑝 × 𝑞𝑞). There are 𝑛𝑛 bus routes on the map, each of which consists of departure, arrival

endpoints, and two bus paths connecting two endpoints. A bus path is assumingly a fixed
polyline. A bus departs on one path and returns on another path. We assume that every bus

route has exactly one bus. There are 𝑚𝑚 (𝑚𝑚 ≤ 𝑛𝑛) air quality monitoring sensors that need to
be installed on buses, where each bus can have at most one sensor installed. We adopt the
disk-based model to represent the sensing capability of the sensors. Each sensor can observe
all points in the disk of radius 𝑟𝑟 centered at its position. Due to the energy and computation
resource constraint, a sensor can only be turned on at exactly 𝑘𝑘 positions on each path of a

bus route to measure the air quality (and thus, 2𝑘𝑘 positions in total on the two paths).
Otherwise, it has to be turned off immediately after a quick measurement. The measurement
time is negligible, and the turn-on positions of sensors are free to be chosen. However, they
are fixed before installation on the buses (see Fig. 1 for an example). We assume that the air
quality of every point inside the same square is almost identical. A square is then said
observable by a sensor if it intersects the circle of radius 𝑟𝑟 centered at a turn-on position of

the sensor.

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

17

Number of rows in the bus map grid

c

Number of critical squares

n

Number of bus routes

m

Number of sensors

r

Sensing radius of a sensor

k

Maximum number of time a sensor can be turned on a path

O(𝐶𝐶)

Observable boundary of C

C(b)

The set of the leftmost and rightmost observable bounds of a bus

route b

The OSO problem asks to choose 𝑚𝑚 bus routes to install sensors and decide the sensor’s

turn-on positions on each of these 𝑚𝑚 routes to maximize the number of observable critical
squares. This work considers two scenarios: the general scenario and a simplified scenario
where the two paths on each bus route are identical.

3.2. Mathematical formulation of OSO
In this section, we introduce the definition and mathematically formulate the targeted
problem. To facilitate readability, we summarize all the notations in Table 1.
Definition 3.1 (Observable Boundary). Let 𝐶𝐶 be a critical square. The outer contour that has

a distance of 𝑟𝑟 to 𝐶𝐶’s boundary is called the observable boundary of 𝐶𝐶, and denoted as O(𝐶𝐶).

Fig. 2 illustrates two critical squares (𝐶𝐶 1 , 𝐶𝐶 2 ) and their observable boundaries (𝐶𝐶 1 ) and (𝐶𝐶 2 ).

Definition 3.2 (Observable Square). Let 𝑋𝑋 be a point on the plane. An observable square of

𝑋𝑋 is a critical square that is monitored by a sensor located at 𝑋𝑋; the observable square set of

𝑋𝑋 is the set of all observable squares of 𝑋𝑋.

In Fig. 2, 𝐶𝐶 1 is an observable square of X 1 and X 2 , while 𝐶𝐶 2 is observable by only X 1 . The
observable square set of X 1 consists of 𝐶𝐶 1 and 𝐶𝐶 2 , while that of X 2 contains only 𝐶𝐶 1 .

18

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Figure 2. Illustration of observable boundary, observable square, and observable segment.
Proposition 1. A critical square 𝐶𝐶 is an observable square of 𝑋𝑋 if and only if 𝑋𝑋 stays on the

boundary or inside of O(𝐶𝐶).

Proof. 𝐶𝐶 is observable by 𝑋𝑋 if and only if the distance from 𝑋𝑋 to 𝐶𝐶’s boundary does not
exceed 𝑟𝑟. This condition is equivalent to that 𝑋𝑋 stays on the boundary or inside O(𝐶𝐶)

Definition 3.3 (Observable Segment). Suppose 𝐶𝐶 is a critical square and 𝑃𝑃 is a straight bus

route segment. The observable segment of 𝑃𝑃 concerning 𝐶𝐶 is defined by the portion of 𝑃𝑃
staying on the boundary or inside O(𝐶𝐶).

Moreover, we define the leftmost and rightmost observable bounds of 𝑃𝑃 concerning O(𝐶𝐶) as
the first and last point of the observable segment when we move from one end of the other
end of the bus route.
Fig. 2 represents a bus route 𝑏𝑏 and its observable segments. Segment P 1 P 2 stays inside

O(𝐶𝐶 1 ), thus its observable segment concerning 𝐶𝐶 1 is itself. Segment P 5 P 6 has the left end

point, i.e., P 5 , stays inside O(𝐶𝐶 2 ), thus the observable segment of P 5 P 6 concerning P 5 P 6

comprises of two end points, one is P 5 and the other is the intersection of P 5 P 6 and O(𝐶𝐶 2 ),
i.e., I 6 . As the two end points of segment P 8 P 9 stays outside of O(𝐶𝐶 2 ), P 8 P 9 ’s observable
segment concerning 𝐶𝐶 2 comprises of the two intersection points of P 8 P 9 and O(𝐶𝐶 2 ), i.e., I 8 ,

I 9 . In a special case, the observable segment of P 7 P 8 concerning 𝐶𝐶 2 deduces to a point P 7 .

Proposition 2. Let 𝑃𝑃, 𝑋𝑋 be a straight bus route segment and a point on 𝑃𝑃 ; 𝐶𝐶 is a critical
square. Suppose I 1 I 2 is the observable segment of 𝑃𝑃 concerning 𝐶𝐶. 𝐶𝐶 is an observable square

of 𝑋𝑋 if and only if 𝑋𝑋 stays between I 1 and I 2 .

19

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Proof. According to Proposition 1, 𝐶𝐶 is an observable square of 𝑋𝑋 if and only if 𝑋𝑋 stays on
the boundary or inside of O(𝐶𝐶). On the other hand, 𝑋𝑋 stays on 𝑃𝑃 , thus, 𝐶𝐶 is an observable
square of 𝑋𝑋 if and only if 𝑋𝑋 belongs to the intersection of 𝑃𝑃 and O(𝐶𝐶). i.e., I 1 I 2

Theorem 3.1. Suppose 𝑏𝑏 is a bus route and C(𝑏𝑏) is the set of 𝑏𝑏’s leftmost and rightmost
observable bounds concerning all the critical squares. Let 𝑋𝑋 be an arbitrary point of 𝑏𝑏 such
that 𝑋𝑋’s observable square set is not null. Suppose 𝑌𝑌 is the leftmost bound of 𝑋𝑋’s observable
segment, closest to 𝑋𝑋. Then the observable square set of 𝑋𝑋 is the subset of 𝑌𝑌 ’s.

Proof. Let us denote by 𝑃𝑃 the straight bus route segment containing 𝑋𝑋, then obviously 𝑃𝑃
must also contain 𝑌𝑌 . Suppose 𝐶𝐶 is an observable square of 𝑋𝑋, we will prove that 𝐶𝐶 is also an
observable square of 𝑌𝑌 . We denote by P u P v the observable segment of 𝑃𝑃 with respect to 𝐶𝐶,

where P u and P v are the leftmost and rightmost observable bounds. As 𝐶𝐶 is an observable

square of 𝑋𝑋, according to Proposition 2, 𝑋𝑋 must stay between P u and P v . Specifically, 𝑋𝑋 must

stay on the right side of P u and the left side of P v . As 𝑌𝑌 is the leftmost observable bound
closest to 𝑋𝑋, 𝑌𝑌 must either overlap or stay on the right side of P u . On the other hand, as P v

stays on the right side of 𝑋𝑋, it also stays on the right side of 𝑌𝑌. Consequently, 𝑌𝑌 stays between
P u and P v . Thus, 𝐶𝐶 must be an observable square of 𝑌𝑌 (see Fig. 3).

Figure 3. 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 𝑌𝑌).

From Theorem 3.1, we deduce that to decide the optimal turn on locations of sensors on
buses, we just need to determine the optimal turn on points among the leftmost observable
bounds. We call these leftmost observable points critical points.

20

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep

In the following, we present the mathematical formulation of the considered problem. We
𝑖𝑖1 𝑖𝑖2 𝑖𝑖1 𝑖𝑖2
define binary variables 𝑠𝑠𝑠𝑗𝑗𝑗𝑗
, 𝑠𝑠𝑠𝑗𝑗𝑗𝑗 , 𝑠𝑠𝑗𝑗𝑗𝑗 , 𝑠𝑠𝑗𝑗𝑗𝑗 , 𝑏𝑏𝑗𝑗𝑖𝑖1 , 𝑏𝑏𝑗𝑗𝑖𝑖2 , 𝑎𝑎𝑖𝑖 as follows.

• 𝑠𝑠𝑠𝑗𝑗𝑖𝑖1𝑗𝑗 equals 1 if the critical square 𝑡𝑡 can be observed from the 𝑗𝑗th critical point on the first
path of bus route 𝑖𝑖, is 0 otherwise.

• 𝑠𝑠𝑠𝑗𝑗𝑖𝑖2𝑗𝑗 equals 1 if the critical square 𝑡𝑡 can be observed from the 𝑗𝑗th critical point on the second

path of bus route 𝑖𝑖, is 0 otherwise.

• 𝑠𝑠𝑗𝑗𝑡𝑡𝑖𝑖1 equals 1 if we choose to observe the critical square 𝑡𝑡 from the 𝑗𝑗th critical point on the

first path of bus route 𝑖𝑖, is 0 otherwise.

• 𝑠𝑠𝑗𝑗𝑗𝑗𝑖𝑖2 equals 1 if we choose to observe the critical square 𝑡𝑡 from the 𝑗𝑗th critical point on the
second path of bus route 𝑖𝑖, is 0 otherwise.

• 𝑏𝑏𝑗𝑗𝑖𝑖1 equals 1 if the 𝑗𝑗th critical point on the first path of bus route 𝑖𝑖 is chosen to be a turn-on
position, is 0 otherwise.

• 𝑏𝑏𝑗𝑗𝑖𝑖2 equals 1 if the 𝑗𝑗th critical point on the second path of bus route 𝑖𝑖 is chosen to be a turn-

on position, is 0 otherwise.

• 𝑎𝑎𝑖𝑖 equals is 1 if a sensor is installed on bus route 𝑖𝑖, is 0 otherwise.

Moreover, denoting 𝑚𝑚 i1 , 𝑚𝑚 i2 as the number of critical points on the first and second path of

bus route 𝑖𝑖, our problem is mathematically formulated as follows.
Objective
Maximize
𝑐𝑐

�
Subject to

𝑡𝑡=1

𝑛𝑛

�
𝑖𝑖=1

∀𝑡𝑡, 1 ≤ 𝑡𝑡 ≤ 𝑐𝑐: ∑𝑛𝑛𝑖𝑖=1
𝑚𝑚

𝑖𝑖1
∀𝑖𝑖, 1 ≤ 𝑖𝑖 ≤ 𝑛𝑛: ∑𝑗𝑗=1

∑𝑛𝑛𝑖𝑖=1

𝑎𝑎𝑖𝑖 = 𝑚𝑚

𝑚𝑚𝑖𝑖1

�

𝑗𝑗1 =1

𝑖𝑖1
∑𝑚𝑚
𝑗𝑗1 =1

𝑚𝑚𝑖𝑖2

�

𝑗𝑗2 =1

𝑖𝑖2
∑𝑚𝑚
𝑗𝑗2 =1

𝑚𝑚

𝑖𝑖2
𝑏𝑏𝑗𝑗𝑖𝑖1 ≤ 𝑘𝑘, ∑𝑗𝑗=1

(3)

𝑎𝑎𝑖𝑖 × (𝑠𝑠𝑠𝑗𝑗𝑖𝑖11 𝑡𝑡 × 𝑠𝑠𝑗𝑗𝑖𝑖1
× 𝑏𝑏𝑗𝑗𝑖𝑖1
+ 𝑠𝑠𝑠𝑗𝑗𝑖𝑖22 𝑡𝑡 × 𝑠𝑠𝑗𝑗𝑖𝑖2
× 𝑏𝑏𝑗𝑗𝑖𝑖2
)

1 𝑡𝑡
1
2 𝑡𝑡
2
(𝑠𝑠𝑠𝑗𝑗𝑖𝑖11 𝑡𝑡 × 𝑠𝑠𝑗𝑗𝑖𝑖1
+ 𝑠𝑠𝑠𝑗𝑗𝑖𝑖22 𝑡𝑡 × 𝑠𝑠𝑗𝑗𝑖𝑖2
)≤1
1 𝑡𝑡
2 𝑡𝑡

𝑏𝑏𝑗𝑗𝑖𝑖2 ≤ 𝑘𝑘

(1)

(2)

21

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

The objective function that has to be maximized is simply the number of critical squares
covered. A square t is covered when four conditions below are satisfied:
- A bus route i is chosen to install sensor (i.e. 𝑎𝑎𝑖𝑖 = 1).

- The square t can be observe from the jth critical point on the first path of i, i.e. 𝑠𝑠𝑠𝑗𝑗𝑖𝑖1𝑗𝑗 = 1 (or
the second path of i, i.e. 𝑠𝑠𝑠𝑗𝑗𝑖𝑖2𝑗𝑗 = 1).

- The jth critical point on the first path is chosen to observe t, i.e. 𝑠𝑠𝑗𝑗𝑗𝑗𝑖𝑖1 = 1 (or on the second
path is chosen to observe t, i.e. 𝑠𝑠𝑗𝑗𝑗𝑗𝑖𝑖2 = 1).

- The jth critical point on the first path is chosen to be a sensor’s turn-on position, i.e. 𝑏𝑏𝑗𝑗𝑖𝑖1 =
1 (or on the second path, i.e. 𝑏𝑏𝑗𝑗𝑖𝑖2 = 1).

That’s why the objective function is written as above. To make sure that an observed critical
square is not count twice or more, and to guarantee that we don’t use more than m sensors
or turn on them more than k times on some bus path, we need three additional constraints.
Constraint (1) ensures each observable critical square is counted at most once in the objective
function. Constraint (2) guarantees that there are at most 𝑘𝑘 turn-on positions on any path.
The last constraint depicts that there are 𝑚𝑚 bus routes picked to install a sensor.

3.3. Hardness of OSO

We prove the hardness of the OSO problem by the reduction theory using the known NPhard maximum coverage problem (MCP) [22], stated as below.

Given a number 𝛼𝛼 and a collection of sets 𝑉𝑉 = {𝑉𝑉 1 , 𝑉𝑉 2 , … , 𝑉𝑉 β }, the maximum coverage

problem require to find a subset 𝑉𝑉 ′ ⊆ 𝑉𝑉 of sets to maximize the number of covered elements
|⋃ 𝑉𝑉𝑉𝑉 ∈𝑉𝑉 ′ 𝑉𝑉 i | such that |𝑉𝑉 ′ | ≤ 𝛼𝛼.

Theorem 3.2. OSO belongs to the NP-hard class.
Proof. We prove this by reducing from MCP to OSO. First, we set a bus map on a grid of
𝛽𝛽

size |𝑈𝑈| × 3 (columns × rows), where 𝑈𝑈 = ∪𝑖𝑖=1

𝑉𝑉𝑖𝑖 . Let the critical regions be at all squares

of the second row, hence each element in 𝑈𝑈 represents a square. We then need to build a bus

route including the depart and return parts for each set 𝑉𝑉 i , ∀𝑖𝑖 = 1 … 𝛽𝛽, such that one of its
paths does not touch any square on the map’s second row; and the other path goes through

only the squares represented in 𝑉𝑉 i . Such a route always exists by passing alternatively these

three rows at each column containing a square represented in 𝑉𝑉 i (see Fig. 4 for an example).
Finally, we set 𝑚𝑚 = 𝛼𝛼, 𝑛𝑛 = 𝛽𝛽, 𝑟𝑟 = 0, and 𝑘𝑘 = max i |𝑉𝑉 i |.

22

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Figure 4. A corresponding bus map when 𝛽𝛽 = 3, 𝑉𝑉 1 = {𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷, 𝐹𝐹}, 𝑉𝑉 2 = {𝐴𝐴, 𝐶𝐶, 𝐷𝐷, 𝐸𝐸},
and 𝑉𝑉 3 = {𝐵𝐵, 𝐹𝐹}.

It is clear that if there is an optimal solution for OSO, the subset 𝑉𝑉 ′ containing 𝑉𝑉 ’s elements,

which correspond to the routes in 𝑉𝑉 , is also an optimal solution for MCP. The optimal

solution 𝑉𝑉 ′ for MCP can also be converted to an optimal set of bus routes and turn-on
positions for such instance of OSO in polynomial time. Therefore, MCP is proven to be not
harder than OSO. That means OSO is NP-hard.
In chapter 5, we introduce a greedy approximation algorithm for OSO. We prove that in a
general case, the algorithm gives an

𝑒𝑒−1

2𝑒𝑒−1

. Moreover, in a simplified case where the

approximation ratio of two paths on each bus route are identical, it gives an approximation
1

ratio of 2.

23

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Chapter 4. Theoretical Background

4.1. Approximation algorithms
In computer science and operations science, approximation algorithms produce near-optimal
results, which the furthest distance from the optimal result is always provable. Because of
the belief that P is different from NP, some problems are said to be unsolvable in polynomial
time, hence approximation algorithms are proposed as an alternative to finding the optimal
algorithm.
Any approximation algorithm must be accompanied by a theoretical proof that certifies the
efficiency of the result produced in the worst case. Algorithms of this class differ from metaheuristics, such as genetic or simulated annealing algorithms, in that meta-heuristic
algorithms do not guarantee the quality of results by theoretical proof, although in practice
they are often superior to approximation algorithms.
In this thesis, the greedy approximation algorithms provide results with provable efficiency,
thereby serving as the basis for other algorithms to compare.

4.2. Meta-heuristic algorithms
Meta-heuristic is the name for a group of algorithms that allow to find good enough results
for problems that do not have a polynomial time solution and the search space for a solution
is much larger than the computation capacity. These algorithms do not guarantee the optimal
solution, nor prove the efficiency of the solution as approximation algorithms. However,
there are still many proofs about the convergence ability and the probability of obtaining
optimal results of these algorithms. Many meta-heuristic algorithms are inspired by natural
processes, such as genetic algorithm, simulated annealing algorithm, swarm algorithm, and
more. They are often very good at experimentation, and can especially be used for many
different problems.
In this thesis, two meta-heuristic algorithms, genetic algorithm and simulated annealing
algorithm, are used as independent models to solve the OSO problem, which is an NP-hard
problem. 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
24

Optimal deployment of intelligent mobile air quality systems

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về