Giải thuật tìm kiếm địa phương giải bài toán định tuyến đa điểm tối ưu năng lượng trên mạng cảm biến không dây nhiệm vụ tuần hoàn

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 (2.13 MB, 67 trang )

VÕ KHÁNH TRUNG

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------Mang l■i tr■ nghi■m m■i m■ cho ng■■i dùng, công ngh■ hi■n th■ hi■n ■■i, b■n online khơng khác gì so v■i b■n g■c. B■n có th■ phóng to, thu nh■ tùy ý.

VÕ KHÁNH TRUNG

CƠNG NGHỆ THƠNG TIN

TÊN ĐỀ TÀI LUẬN VĂN
GIẢI THUẬT TÌM KIẾM ĐỊA PHƯƠNG GIẢI BÀI TOÁN ĐỊNH
TUYẾN ĐA ĐIỂM TỐI ƯU NĂNG LƯỢNG TRÊN MẠNG CẢM
BIẾN KHƠNG DÂY NHIỆM VỤ TUẦN HỒN

LUẬN VĂN THẠC SĨ KỸ THUẬT CƠNG NGHỆ THƠNG TIN

KHỐ 2014B
Hà Nội – Năm 2016
123doc
Xu■t
Sau
Nhi■u
h■n
phát
event
s■
m■t
t■
h■u
thú

ýn■m
t■■ng
m■t
v■,raevent
kho
■■i,
t■oth■
c■ng
ki■m
123doc
vi■n
■■ng
ti■n
kh■ng
■ãthi■t
t■ng
ki■m
l■
th■c.
b■■c
v■i
ti■nh■n
123doc
online
kh■ng
2.000.000
b■ng
ln
■■nh
ln

tàitài
v■
li■u
t■o
li■u
tríhi■u
c■
c■a
■ t■t
h■i
qu■
mình
c■
gianh■t,
trong
l■nh
t■nguy
v■c:
l■nh
thu
tínnh■p
tài
v■c
cao
chính
nh■t.
tài
online
li■u
tínMong

cho
d■ng,
và kinh
t■t
mu■n
cơng
c■
doanh
các
mang
ngh■
online.
thành
l■i
thơng
cho
viên
Tính
tin,
c■ng
c■a
■■n
ngo■i
website.
■■ng
th■i
ng■,...Khách
■i■m
xã h■itháng
m■thàng

ngu■n
5/2014;
có th■
tài
123doc
ngun
d■ dàng
v■■t
tri tra
th■c
m■c
c■u
q
100.000
tàibáu,
li■uphong
m■t
l■■t cách
truy
phú,c■p
chính
■am■i
d■ng,
xác,
ngày,
nhanh
giàus■
giá
chóng.
h■u

tr■ 2.000.000
■■ng th■ithành
mongviên
mu■n
■■ng
t■oký,
■i■u
l■t ki■n
vào top
cho200
chocác
cácwebsite
users cóph■
thêm
bi■n
thunh■t
nh■p.
t■iChính
Vi■t Nam,
vì v■yt■123doc.net
l■ tìm ki■m
ra thu■c
■■i nh■m
top 3■áp
Google.
■ng Nh■n
nhu c■u
■■■c
chiadanh
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.
Nhi■u
123doc
Sau
Th■a
khi
thu■n
event
s■
cam
nh■n
h■u
k■t
s■
thú
xác
m■t
d■ng
v■,
s■

nh■n
mang
event
kho
1. t■
th■
l■i
ki■m
■■ng
CH■P
vi■n
nh■ng
ti■n
h■
kh■ng
NH■N
quy■n
th■ng
thi■tl■
CÁC
th■c.
s■
l■i
v■ichuy■n
■I■U
t■t
h■n
123doc
nh■t
2.000.000

KHO■N
sang
ln
cho ng■■i
ph■n
ln
TH■A
tàit■o
li■u
thơng
dùng.
THU■N
c■
■ tin
t■t
h■i
Khixác
c■
khách
giaminh
l■nh
t■ng
Chào
hàng
tài
v■c:
thu
m■ng
kho■n
tr■

nh■p
tài thành
b■n
chính
email
online
■■n
thành
tínb■n
cho
d■ng,
v■i
viên
■ã
t■t
123doc.
123doc.net!
cơng
■■ng
c■a
c■ các
ngh■
123doc
kýthành
v■i
Chúng
thơng
và
123doc.netLink
viên

n■p
tơi
tin,
c■a
cung
ti■n
ngo■i
website.
vào
c■p
ng■,...Khách
xác
tài
D■ch
kho■n
th■c
V■
s■
c■a
(nh■
hàng
■■■c
123doc,
■■■c
cóg■i
th■v■
mơ
b■n
d■■■a
t■

dàng
s■
d■■i
■■■c
ch■
tra■ây)
email
c■u
h■■ng
cho
tài
b■n
li■u
b■n,
nh■ng
■ã
m■t
tùy
■■ng
quy■n
cách
thu■c
ky,
chính
l■i
b■n
vàosau
xác,
các
vuin■p

lịng
“■i■u
nhanh
ti■n
■■ng
Kho■n
chóng.
trên
nh■p
website
Th■a
email
Thu■n
c■a v■
mình
S■vàD■ng
click D■ch
vào link
V■”
123doc
sau ■ây
■ã (sau
g■i ■ây ■■■c g■i t■t T■i t■ng th■i ■i■m, chúng tơi có th■ c■p nh■t ■KTTSDDV theo quy■t ...
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
vào
c■p
ng■,...Khách
trách
xác
tài
■i■m
D■ch
xã
to,kho■n
th■c
nhi■m
h■i

thutháng
V■
nh■
m■t
s■
c■a
(nh■
■■i
hàng
■■■c
tùy
ngu■n
5/2014;
123doc,
v■i
■■■c
ý.
cóg■i
t■ng
th■
tài
123doc
v■
mơ
ngun
b■n
d■
ng■■i
■■a
t■

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

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

s■
■■ng
tr■
giá
Kho■n
chóng.
h■u
trên
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
th■
email
vi■n
th■i
Thu■n
c■a
thành
mong
tài v■
li■u
mình
viên
mu■n
S■
online

và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t
link
ki■n
V■”
vào
Vi■t
123doc
top
sau
cho
Nam,
200
■ây
cho
■ã
cung
các
các
(sau

g■iwebsite
c■p
users
■âynh■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.
Mangh■n
Ln
123doc
Th■a
Xu■t
Sau
Nhi■u
khi
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
vào

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

t■ng
th■
tài
123doc
v■
mơ
ngun
b■n
d■
ng■■i
■■a
t■
dàng
s■
v■■t
d■■i
tri
dùng.
■■■c
ch■
tra
th■c
m■c
■ây)
email
c■u
M■c
h■■ng
q
100.000

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

m■i
d■ng,
sau
xác,
các
vuingày,
n■p
lịng
“■i■u
nhanh
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
chóng.
h■u
trên
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
th■
email
vi■n

th■i
Thu■n
c■a
thành
mong
tài v■
li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t
link
ki■n
V■”
vào
Vi■t
123doc

top
sau
cho
Nam,
200
■ây
cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■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.
Lnh■n
123doc
Th■a
Xu■t
Sau
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
tài
■■nh
ng■■i
li■u
ph■n
tài
TH■A
v■
li■u
hàng

thơng
dùng.
tríTHU■N
hi■u
c■a
■■u
tin
Khi
qu■
mình
Vi■t
xác
khách
nh■t,
minh
trong
Nam.
Chào
hàng
uy
tài
l■nh
Tác
m■ng
tín
kho■n
tr■
phong
v■c
cao

thành
b■n
email
nh■t.
tàichun
■■n
li■u
thành
b■n
Mong
và
v■i
nghi■p,
viên
kinh
■ã
123doc.
123doc.net!
mu■n
■■ng
c■a
doanh
hồn
mang
123doc
kýonline.
v■i
h■o,
Chúng
l■ivà

123doc.netLink
cho
Tính
■■
n■p
tơi
c■ng
cao
■■n
cung
ti■n
tính
■■ng
th■i
vào
c■p
trách
xác
tài
■i■m
D■ch
xãkho■n
th■c
nhi■m
h■itháng
V■
m■t
s■
c■a
(nh■

■■i
■■■c
ngu■n
5/2014;
123doc,
v■i
■■■c
g■i
t■ng
tài
123doc
v■
mơ
ngun
b■n
ng■■i
■■a
t■s■
v■■t
d■■i
tri
dùng.
■■■c
ch■
th■c
m■c
■ây)
email
M■c
h■■ng

q
100.000
cho
b■n
tiêu
báu,
b■n,
nh■ng
■ã
hàng
phong
l■■t
tùy
■■ng
■■u
quy■n
truy
thu■c
phú,
ky,
c■a
c■p
■a
l■i
b■n
vào
123doc.net
m■i
d■ng,
sau

các
vuingày,
n■p
lịng
“■i■u
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
h■u
trên
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
th■
email
vi■n
th■i
Thu■n
c■a
thành
mong
tài v■

li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t
link
ki■n
V■”
vào
Vi■t
123doc
top
sau
cho
Nam,
200
■ây

cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■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.
Lnh■n
Th■a
Xu■t
Sau
Nhi■u
123doc
Mang
khi
h■■ng
phát
thu■n
l■i
event
cam
s■
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
vào
c■p
ng■,...Khách
trách
xác
tài
■i■m
D■ch
xã
to,kho■n
th■c
nhi■m
h■i
thutháng
V■
nh■
m■t
s■
c■a
(nh■
■■i
hàng
■■■c
tùy
ngu■n

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

email
c■u
M■c
h■■ng
q
100.000
cho
tài
b■n
tiêu
báu,
li■u
b■n,
nh■ng
■ã
hàng
phong
m■t
l■■t
tùy
■■ng
■■u
quy■n
cách
truy
thu■c
phú,
ky,
c■a
c■p

chính
■a
l■i
b■n
vào
123doc.net
m■i
d■ng,
sau
xác,
các
vuingày,
n■p
lịng
“■i■u
nhanh
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
chóng.
h■u
trên
thành
tr■
nh■p
2.000.000

website
■■ng
Th■a
th■
email
vi■n
th■i
Thu■n
c■a
thành
mong
tài v■
li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t

link
ki■n
V■”
vào
Vi■t
123doc
top
sau
cho
Nam,
200
■ây
cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■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.
Vi■c
■■ng
Thành
s■
u■t
Nhi■u

Mang
Ln
123doc
Th■a
Xu■t
Sau
h■u
phát
khi
h■n
b■n
h■■ng
phát
thu■n
l■i
ýevent
viên
s■
cam
nh■n
r■ng
m■t
t■
m■t
tr■
s■
t■
h■u
s■
ýk■t

s■
thú
kho
nghi■m
t■i
ýd■ng
n■u
t■■ng
xác
n■m
ph■i
t■■ng
m■t
d■ng
v■,
là
s■
th■
nh■n
Thành
website
ra
ho■c
mang
th■c
event
t■o
kho
vi■n
m■i

■■i,
1.
t■o
t■
c■ng
th■
viên
■■ng
hi■n
m■
l■i
kh■ng
c■ng
ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
ti■p
cho
theo
■■ng
■■u
ký
■■ng
ti■n
h■
l■

kh■ng
ng■■i
t■c
NH■N
s■
■ã
■úng
v■i
quy■n
th■ng
thi■t
chia
ki■m
d■ng
t■ng
s■
ki■m
h■n
dùng,
l■
các
CÁC
s■
d■ng
th■c.
ti■n
s■
l■i
b■■c
các

v■i
ti■n
2.000.000
và
ch■
chuy■n
■I■U
t■t
cơng
online
h■n
D■ch
mua
123doc
d■ch
online
kh■ng
d■n
nh■t
2.000.000
ngh■
bán
KHO■N
v■
b■ng
V■
■■■c
sang
tài
b■ng

ln
cho
tài
■■nh
c■a123doc.net
sau
li■u
hi■n
tài
ng■■i
li■u
ph■n
ln
tài
niêm
TH■A
khi
■
li■u
tài
v■
th■
li■u
hàng
t■t
t■o
■KTTSDDV
li■u
thơng
dùng.

trí
y■t
hi■u
hi■n
THU■N
c■
hi■u
c■
c■a
■■u
■
ho■c
l■nh
tin
qu■
■■ng
t■t
h■i
Khi
■■i,
qu■
mình
Vi■t
xác
c■
khách
gia
các
v■c:
nh■t,

■■■c
b■n
nh■t,
ngh■a
minh
trong
l■nh
Nam.
t■ng
Chào
quy
tài
online
uy
hàng
uy
c■p
tài
v■c:
■■nh
chính
l■nh
thu
Tác
tín
v■i
m■ng
tín
kho■n
tr■

cao
nh■t,
nh■p
khơng
tài
vi■c
phong
v■c
cao
tín
áp
thành
b■n
chính
nh■t.
d■ng,
d■ng
email
nh■t.
tài
b■n
vi■c
online
khác
chun
■■n
li■u
thành
tín
Mong

■ã
■ó
cho
b■n
cơng
Mong
gì
cho
d■ng,
và
v■i
■■ng
có
so
các
nghi■p,
viên
ki
kinh
■ã
mu■n
t■t
ngh■
123doc.
123doc.net!
ngh■a
v■i
mu■n
123doc
cơng

d■ch
■■n■
■■ng
c■a
c■
cwebsite.
ýdoanh
b■n
v■i
thơng
mang
các
hồn
mang
là
ngh■
123doc
v■
ký
v■■t
g■c.
các
■■a
Thàn
online.
thành
■ó
v■i■ng
v■i
l■i

tin,
h■o,
Chúng
Chún
■i■u
l■i
thơng
B■n
ch■
m■c
có
cho
ngo■i
và
là
123doc.netLink
chogun
cho
viên
Tính
■■
website
th■
mơ
n■p
kho■n
email
có
c■ng
tơi

tin,
ky,
100.000
c■ng
c■a
cao
ng■,...Khách
t■
■■■c
th■
■■n
cung
ti■n
b■n
ngo■i
d■■i
b■n
■■ng
tính
c■a
ki■m
website.
phóng
■■ng
trith■i
vào
c■p
vui
l■■t
niêm

th■c
ng■,...Khách
■ã
trách
n■ây)
xác
lịng
xã
ti■n
tài
■i■m
khơng
D■ch
xã
to,
■■ng
truy
y■t
q
h■i
kho■n
th■c
hànnh
nhi■m
h■i
cho
thu
■■ng
online
c■p

theo
m■t
báu,
tháng
V■
■■ng
ky,
nh■
m■t
b■n,
s■
c■a
xác,
m■i
(nh■
■■i
nh■p
hi■u
hàng
t■ng
ngu■n
b■n
phong
■■■c
tùy
ngu■n
5/2014;
ýtùy
123doc,
nhanh

v■i
Mong
ngày,
vui
■■■c
qu■
ý.
email
th■i
có
thu■c
phú,
tài
g■i
t■ng
lịng
th■
tài
123doc
và
s■
■i■m.
mu■n
ngun
chóng.
c■a
v■
mơ
ngun
b■n

■a
vào
uy
d■
■■ng
ng■■i
h■u
■■a
t■
tín
d■ng,
mình
dàng
các
s■
man
T■t
v■■t
tri
2.000.000
d■■i
nh■t.
nh■p
tri
dùng.
■■■c
ch■
th■c
“■i■u
c■

và
ngun
tra
th■c
giàu
m■c
■ây)
click
các
email
c■u
email
q
M■c
h■■ng
giá
Kho■n
q
100.000
thành
ocho
vào
tri
tài
báu,
tr■
b■nn
b■n
c■a
tiêu

báu,
th■c
li■u
b■n,
link
■■ng
nh■ng
Th■a
viên
phong
■ã
hàng
mình
phong
viên
m■t
l■■t
q
123doc
tùy
■■ng
■■ng
th■i
Thu■n
■■u
c■a
báo
và
phú,
quy■n

cách
truy
thu■c
phú,
click
mong
■ã
ky,
các
ký,
website.
c■a
c■p
■a
chính
v■
■a
l■i
b■n
g■i
vào
l■t
vào
users
d■ng,
123doc.net
m■i
S■
mu■n
d■ng,

sau
vào
xác,
các
link
vui
D■ng
ngày,
có
n■p
giàu
top
lịng
“■i■u
123doc
nhanh
t■o
giàu
thêm
200
ti■n
D■ch
giá
s■
■■ng
■i■u
tr■
giá
Kho■n
thu

chóng.
các
h■u
tr■
■ã
trên
thành
tr■
V■”
ki■n
nh■p.
nh■p
■■ng
g■i
website
2.000.000
website
■■ng
Th■a
sau
th■
cho
email
Chính
th■i
■ây
vi■n
th■i
ph■
Thu■n

chomong
c■a
thành
vì
(sau
mong
các
tài
bi■n
v■y
v■
li■u
mình
users
mu■n
■ây
viên
nh■t
mu■n
S■
123doc.net
online
và
■■■c
■■ng
có
D■ng
t■i
t■o
click

t■o
thêm
l■n
Vi■t
■i■u
g■i
ký,
D■ch
■i■u
vào
ra
nh■t
thu
Nam,
l■t
t■t
■■i
link
ki■n
nh■p.
ki■n
V■”
vào
T■i
Vi■t
123doc
nh■m
t■
cho
top

sau
cho
t■ng
l■
Nam,
Chính
cho
200
tìm
■ây
■áp
cho
■ã
th■i
cung
các
ki■m
các
vìcác
(sau
g■i
■ng
v■y
■i■m,
users
website
c■p
users
thu■c
■ây

nhu
123doc.net
nh■ng
có
chúng
c■u
■■■c
có
top
ph■
thêm
thêm
chia
3tơi
tài
bi■n
Google.
g■i
thu
ra
có
thu
li■u
s■
■■i
t■t
nh■p.
th■
nh■t
nh■p.

tài
■■c
T■i
Nh■n
nh■m
li■u
c■p
t■i
Chính
khơng
t■ng
Chính
ch■t
nh■t
Vi■t
■■■c
■áp
th■i
vìth■
l■■ng
Nam,
■KTTSDDV
vì■ng
v■y
v■y
danh
■i■m,
tìm
123doc.net
nhu

t■
và
123doc.net
th■y
hi■u
l■
ki■m
chúng
c■u
tìm
trên
theo
do
chia
ki■m
ti■n
c■ng
tơi
ra
th■
quy■t
ra
s■
có
■■i
online.
thu■c
■■i
tr■■ng
■■ng

th■
tài...
nh■m
nh■m
li■u
c■p
top
bình
ngo■i
ch■t
■áp
3nh■t
■áp
Google.
ch■n
l■■ng
■ng
tr■
■KTTSDDV
■ng
123doc.net.
lànhu
Nh■n
nhu
website
vàc■u
ki■m
c■u
■■■c
chia

theo
ki■m
chia
ti■n
s■
quy■t
danh
s■
online.
ti■n
tàitài
hi■u
li■u
online
...li■uch■t
do
ch■t
hi■u
c■ng
l■■ng
l■■ng
qu■
■■ng
vàvàki■m
uy
bình
ki■m
tín ch■n
ti■n
nh■t.

ti■nonline.
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

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------VÕ KHÁNH TRUNG

GIẢI THUẬT TÌM KIẾM ĐỊA PHƯƠNG GIẢI BÀI TOÁN ĐỊNH TUYẾN
ĐA ĐIỂM TỐI ƯU NĂNG LƯỢNG TRÊN MẠNG CẢM BIẾN KHƠNG

DÂY NHIỆM VỤ TUẦN HỒN

Chun ngành : Cơng nghệ thơng tin

LUẬN VĂN THẠC SĨ KỸ THUẬT CƠNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Huỳnh Thị Thanh Bình

Hà Nội – Năm 2016

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hồn

MỤC LỤC
MỤC LỤC ................................................................................................................... i
DANH MỤC HÌNH VẼ ............................................................................................ iv
DANH MỤC CÁC BẢNG..........................................................................................v
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ ........................................... vi
DANH MỤC CÁC KÝ HIỆU ................................................................................. vii
LỜI MỞ ĐẦU .............................................................................................................1
CHƯƠNG 1: CƠ SỞ LÝ THUYẾT ...........................................................................3
1.

Các khái niệm cơ bản về đồ thị .........................................................................3

1.1.

Định nghĩa đồ thị ........................................................................................3

1.2.

Đường đi và tính liên thơng .......................................................................4

1.3.

Cây và cây Steiner ......................................................................................4

2.

Độ phức tạp tính tốn ........................................................................................5

2.1.

Một số khái niệm cơ bản ............................................................................5

2.2.

Các ký hiệu tiệm cận: .................................................................................6

2.3.

Độ phức tạp tính tốn của bài tốn.............................................................7

3.

Lớp bài tốn NP-khó .........................................................................................8

3.1.

Một số khái niệm cơ bản ............................................................................8

3.2.

Lớp bài toán P, NPvà co-NP ......................................................................9

3.3.

Khái niệm quy dẫn .....................................................................................9

3.4.

Lớp bài toán NP-đầy đủ và NP-khó .........................................................10

4.

Các giải thuật tìm kiếm trên đồ thị..................................................................11

4.1.

Tìm kiếm theo chiều sâu...........................................................................11

4.2.

Tìm kiếm theo chiều rộng.........................................................................13

5.

Các giải thuật tìm đường đi ngắn nhất ............................................................14

5.1.

Giải thuậtDijkstra .....................................................................................14

5.2.

Giải thuật Ford-Bellman ...........................................................................15

5.3.

Giải thuật Floyd-Warshall ........................................................................16

6.

Một số phương pháp giải quyết bài tốn NP-khó ...........................................17

6.1.

Giải thuật heuristic ...................................................................................19

6.2.

Giải thuật tìm kiếm địa phương ................................................................22

6.3.

Giải thuật tabu search ...............................................................................22

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

4.1.

Ứng dụng trong quân đội ..........................................................................28

4.2.

Ứng dụng trong môi trường......................................................................29

4.3.

Ứng dụng trong chăm sóc sức khỏe .........................................................30

4.4.

Ứng dụng trong gia đình...........................................................................30

CHƯƠNG 3: GIẢI THUẬT TÌM KIẾM ĐỊA PHƯƠNG GIẢI BÀI TỐN MEM
DC-WSN ...................................................................................................................31
1.

Giải thuật đề xuất ............................................................................................31

1.1.

Tìm lịch truyền tốt nhất trên cây multicast...............................................31

1.2.

Khởi tạo lời giải ........................................................................................33

1.3.

Tìm lời giải láng giềng .............................................................................35

1.3.1.

Đổi chỗ 2 nút trên cây ..............................................................................36

1.3.2.

Thay một nút trong cây bằng một nút ở ngoài cây ..................................37

1.3.3.

Loại bỏ cạnh và tìm kết nối mới ..............................................................38

1.3.4.

Di chuyển một cây con .............................................................................39

2.

Đánh giá độ phức tạp của giải thuật đề xuất ...................................................40

3.

Cải tiến giải thuật ............................................................................................40

CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM ..............................................................42
1.

Dữ liệu thử nghiệm .........................................................................................42

2.

Thiết lập hệ thống ...........................................................................................42

3.

Tham số thực nghiệm ......................................................................................42

4.

Kết quả thực nghiệm .......................................................................................43

4.1.

Bảng thống kê kết quả ..............................................................................43

4.2.

Đồ thị so sánh kết quả ..............................................................................44

5.

Nhận xét ..........................................................................................................46

5.1.

Về tổng năng lượng tiêu tốn trong một phiên multicast ..........................46

5.2.

Về thời gian chạy chương trình ................................................................47

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

KẾT LUẬN ...............................................................................................................48

PHỤ LỤC ..................................................................................................................50
TÀI LIỆU THAM KHẢO .........................................................................................57

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hồn

DANH MỤC HÌNH VẼ
Hình 1: Minh họa một số ứng dụng thực tế của mạng cảm biến ................................1
Hình 2: Đồ thị vơ hướng và đồ thị có hướng ..............................................................3

Hình 3: Cây Steiner .....................................................................................................5
Hình 4: Các lớp bài tốn P, NP và co-NP ...................................................................9
Hình 5: Sơ đồ q trình quy dẫn ...............................................................................10
Hình 6: Phân lớp tạm thời các bài tốn .....................................................................11
Hình 7: Minh họa tìm kiếm theo chiều sâu ...............................................................12
Hình 8: Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4 ....................................................14
Hình 9: Các kỹ thuật tìm kiếm ..................................................................................19
Hình 10: Sơ đồ khối giải thuật heuristic tổng quát ...................................................21
Hình 11: Sơ đồ khối giải thuật tabu search ...............................................................24
Hình 12: Mạng cảm biến khơng dây nhiệm vụ tuần hồn và một cây multicast ......25
Hình 13: Minh họa giải thuật tham lam tìm minimum hitting set ............................33
Hình 14: Phép biến đổi số 1 – Đổi chỗ 2 nút trên cây ..............................................36
Hình 15: Phép biến đổi số 2 – Thay thế một nút.......................................................37
Hình 16: Phép biến đổi số 3 – Loại bỏ cạnh và tìm kết nối mới...............................38
Hình 17: Phép biến đổi số 4 – Di chuyển một cây con .............................................39
Hình 18: So sánh năng lượng multicast của các giải thuật trên bộ dữ liệu 1 ............44
Hình 19: So sánh năng lượng multicast của các giải thuật trên bộ dữ liệu 2 ............45
Hình 20: So sánh năng lượng multicast của các giải thuật trên bộ dữ liệu 3 ............45
Hình 21: So sánh năng lượng multicast của các giải thuật trên bộ dữ liệu 4 ............46
Hình 22: So sánh thời gian chạy mỗi test dữ liệu của các giải thuật ........................46

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

DANH MỤC CÁC BẢNG
Bảng 1: Tham số của các bộ dữ liệu .........................................................................42
Bảng 2: Tỷ lệ tối ưu về năng lượng multicast của giải thuật đề xuất so với giải thuật
R-TCS và GS-MEM ..................................................................................................43
Bảng 3: Tỷ lệ tối ưu về thời gian của giải thuật đề xuất so với giải thuật R-TCS và
GS-MEM ...................................................................................................................43
Bảng 4: Năng lượng multicast của giải thuật dề xuất trên các bộ dữ liệu ................53
Bảng 5: Thời gian chạy chương trình của giải thuật đề xuất (đơn vị:ms) ................56

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Minimum-Energy Multicating
MEM DC-WSN

problem in Duty-Cycle
Wireless Sensor Network
Local Search algorithm for

LSMEM

solving MEM problem in DCWSN

Ý nghĩa
Mạng cảm biến không dây
Định tuyến đa điểm tối ưu năng
lượng
Bài toán định tuyến đa điểm tối
ưu năng lượng trên mạng cảm
biến khơng dây nhiệm vụ tuần
hồn
Giải thuật tìm kiếm địa phương
giải bài tốn MEM DC-WSN

.

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Tập khe thời gian hoạt động của nút u

𝑀

Tập các nút terminal

𝑠

Nút nguồn 𝑠 ∈ 𝑀

𝑉(𝑇)

Tập các nút của cây T

𝐸(𝑇)

Tập các cạnh của cây t

𝑛𝑙(𝑇)

Tập các nút không phải là lá (non leaf) của cây T

𝑐ℎ𝑖𝑙𝑑(𝑢, 𝑇)

Tập các nút của của nút u trên cây T

𝑀𝐻𝑆(𝐶)

Minimum hitting set của họ tập C

П(T, B)

Tổng năng lượng tiêu tốn trong một phiên multicast trên cây
multicast T và theo lịch truyền B

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn
LỜI MỞ ĐẦU

Ngày nay, bởi các ưu điểm nhỏ gọn và giá thành rẻ mạng cảm biến không dây đã
được sử dụng rộng rãi trong nhiều ứng dụng thực tế. Một số ứng dụng nổi bật của
mạng cảm biến khơng dây có thể kể tên sau đây: theo dõi tình trạng sức khỏe của
người bệnh, theo dõi sự biến đổi của môi trường, dám sát các mặt trận quân sự. Tuy
nhiên việc sử dụng mạng cảm biến khơng dây cũng gặp nhiều khó khăn do các nút
cảm biến trong mạng thường có năng lượng thấp, khó hoạt động liên tục được.
Cũng bởi chính lý do này vấn đề tối thiểu hóa năng lượng trong q trình hoạt động
của mạng cảm biến không dây rất được quan tâm. Đây cũng là vấn đề rất thách thức
và được đề cập nhiều trong các nghiên cứu về mạng cảm biến khơng dây trong
những năm gần đây.

Hình 1: Minh họa một số ứng dụng thực tế của mạng cảm biến

Để tiết kiệm năng lượng, các nút cảm biến không hoạt động liên tục mà hoạt động
tuần hoàn qua các chu kỳ. Trong từng chu kỳ, mỗi nút có thể luân chuyển giữa hai
trạng thái hoạt động và tạm nghỉ. Những mạng cảm biến không dây này gọi là mạng
cảm biến không dây nhiệm vụ tuần hoàn. (DC-WSN: Duty-Cycled Wireless Sensor
Networks).DC-WSN đã được chứng minh là hiệu quả về mặt tiết kiệm năng lượng.
Tuy nhiên, việc thiết kế các giao thức trên DC-WSN là đặc biệt khó khăn do các nút
ln ln chuyển giữa các trạng thái (hoạt động và tạm nghỉ) dẫn tới tính kết nối và
cấu trúc mạng khơng cố định.
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

Truyền dữ liệu đa điểm (multicast) là quá trình truyền dữ liệu từ một nút nguồn đến
một tập các nút đích. Multicast được thực hiện thường xuyên trong q trình hoạt
động của mạng. Do đó, thiết kế một giao thức multicast hiệu quả về mặt tiết kiệm
năng lượng cho mạng cảm biến không dây là rất cần thiết. Bài toán định tuyến đa
điểm tối ưu năng lượng (MEM: Minimum-Energy Multicasting) đã được chứng
minh thuộc lớp NP-Khó và thường được giải quyết bằng các giải thuật xấp xỉ. Tuy
nhiên, hầu hết các giải thuật chỉ áp dụng cho các mạng mà các nút ln hoạt động.
Tính đến hiện tại chỉ có một số ít các cơng trình nghiên cứu về bài toán MEM trong
DC-WSN.
Luận văn này nghiên cứu về bài toán định tuyến đa điểm tối ưu năng lượng trên
mạng cảm biến khơng dây nhiệm vụ tuần hồn (viết gọn là bài tốn MEM DCWSN) với mục đích mang lại lời giải tốt hơn cho bài toán. Luận văn đề xuất một
giải thuật tìm kiếm địa phương để giải quyết bài toán. Giải thuật đề xuất được cài
đặt và tiến hành thử nghiệm trên bốn bộ dữ liệu gồm 72 test case. Kết quả thử
nghiệm được so sánh với giải thuật tốt nhất hiện tại để đưa ra các phân tích về ưu và

nhược điểm của giải thuật đề xuất. Qua đó, luận văn cũng đưa ra các hướng phát
triển tiếp theo của đề tài.

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

CHƯƠNG 1: CƠ SỞ LÝ THUYẾT
Các khái niệm cơ bản về đồ thị

1.

Đồ thị biểu diễn được rất nhiều cấu trúc. Nhiều bài tốn thực tế có thể được biểu
diễn bằng đồ thị. Trong toán học, lý thuyết đồ thị là một lĩnh vực đã xuất hiện từ lâu
và có rất nhiều ứng dụng trong thực tế. Vào những năm đầu của thế kỷ 18, những tư
tưởng cơ bản của lý thuyết đồ thị được đề xuất bởi nhà toán học lỗi lạc người Thụy
Sỹ Leonhard Euler. Đặc biệt trong khoảng vài chục năm trở lại đây, với sự ra đời
máy tính điện tử và sự phát triển nhanh chóng của cơng nghệ thơng tin, lý thuyết đồ
thị ngày càng được quan tâm nhiều hơn.
Sau đây, xin được trình bày qua các khái niệm cơ bản của đồ thị làm nền tảng cho
việc áp dụng các giải thuật trong các lĩnh vực ứng dụng đồ thị.
1.1. Định nghĩa đồ thị
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và cách cạnh nối các đỉnh này. Chúng ta
phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối các đỉnh này. Ta
định nghĩa các loại đồ thị như sau.
Định nghĩa 1.1 Đơn đồ thị vô hướng G = (V, E) bao gồm V là tập không rỗng chứa
các đỉnh và E là tập các cặp khơng có thứ tự gồm hai phần tử khác nhau của V gọi
là cạnh [Hình 2.a].
Định nghĩa 1.2 Đơn đồ thị có hướng G = (V, E) bao gồm tập các đỉnh V và tập các
cạnh E là các cặp có thứ tự gồm hai phần tử khác nhau của V. Các cạnh của đồ thị
có hướng cịn được gọi là các cung [Hình 2.b].

1

4

1

3

5

2

4

6

3

2

5

(b)

(a)

Hình 2: Đồ thị vơ hướng và đồ thị có hướng

Để tiện sử dụng, chúng ta sẽ gọi đồ thị thay cho đơn đồ thị vơ hướng mà khơng có
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hồn

chú thích gì thêm.
1.2. Đường đi và tính liên thơng
Định nghĩa 1.3 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương trên đồ thị vô hướng G= (V, E) là dãy x0, x1, x2, … xn-1, xn trong đó u = x0, v
= xn, (xi, xi+1)  E, i = 1..n.Đỉnh u được gọi là đỉnh đầu, còn đỉnh v được gọi là
đỉnh cuối của đường đi. Đường đi mà có đỉnh đầu trùng với đỉnh cuối được gọi là
chu trình. Chu trình được gọi là đơn nếu như khơng có cạnh nào lặp lại.
Để xác định xem có luôn tồn tại đường đi giữa 2 cặp đỉnh trong đồ thị, chúng ta đưa
ra khái niệm tính liên thơng của đồ thị.
Định nghĩa 1.4Đồ thị vô hướng G= (V, E) được gọi là liên thơng nếu ln tìm được
đường đi giữa hai đỉnh bất kỳ của nó.
Định nghĩa 1.5Đồ thị có hướng G = (V, E) được gọi liên thông mạnh nếu luôn
được đường đi giữa hai đỉnh bất kỳ của nó. Đồ thị có hướng G = (V, E) được gọi là
liên thông yếu nếu đồ thị vô hướng tương ứng với nó là liên thơng.
1.3. Cây và cây Steiner

Định nghĩa 1.6 Cây là đồ thị vô hướng, liên thơng và khơng chứa chu trình.
Định nghĩa 1.7 Cho đồ thị vô hướng G = (V, E) và tập các đỉnh S⊂ V. Cây T = (V’,
E’) được gọi là cây Steiner của S nếu nó là cây trong G bao trùm tất cả các đỉnh
của S. Quy ước:
 Terminal node: là các đỉnh trong S
 Steiner node: là các đỉnh trong V’\S
Dễ thấy rằng một đồ thị vô hướng liên thơng bất kỳ có thể có nhiều hơn một cây
Steiner.
Trọng số của cây Steiner: nếu mỗi cạnh e  E của đồ thị G được gán một số thực
C(e) - gọi là trọng số của cạnh, thì trọng số của cây Steiner T là giá trị được tính bởi
công thức Cost(T ) 

 C ( e)

eE '

Cây Steiner nhỏ nhất: cây Steiner nhỏ nhất của G là cây Steiner T có Cost(T) nhỏ
nhất.

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

2

3

1
1
5

2

5
5

8

5

1
3

6

4

4

4

6

8

1

5
1

4

2

5
3

1

7

7

(a)

(b)

4

4

Hình 3: Cây Steiner

Ví dụ hình 3:
(a)

là đồ thị ban đầu đã cho.

(b)

Cây Steiner T = (V’, E’ )tương ứng của đồ thị (a) với S = {1,2,3,4}

Các thông số của cây T:
 V’={1,2,3,4,5}
 E’ = {(2,3),(3,4),(4,1), (2,5)} có tổng trọng số là 11
 Terminal node:S={1,2,3,4}
 Steiner node: V’\S={5}
2.

Độ phức tạp tính tốn

Các vấn đề kỹ thuật thường được khái qt dưới dạng bài tốn tính tốn để tiện cho
việc nghiên cứu và giải quyết. Bài toán tính tốn là mối quan hệ giữa đầu vào
(những yếu tố cho trước của bài toán) và đầu ra (những kết quả tính tốn cần đạt
được) của bài tốn. Khái niệm độ phức tạp tính tốn được xem như là chuẩn mực
quan trọng để đánh giá hiệu quả của một bài tốn tính tốn.
2.1. Một số khái niệm cơ bản
Định nghĩa 2.1 Bài tốn tính tốn F là ánh xạ từ các xâu nhị phân độ dài hữu hạn
vào tập các xâu nhị phân độ dài hữu hạn F: {0,1}*→ {0,1}*
Ở đây, các yếu tố đầu vào và đầu ra của bài toán được biểu diễn bằng xâu nhị phân.
Mọi dạng dữ liệu (số, kí tự, xâu, mảng, tập hợp…) đều có thể mã hóa được bằng
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hồn

xâu nhị phân.
Bài tốn chỉ ra mối quan hệ giữa đầu vào và đầu ra, nhưng để đạt được đầu ra từ
đầu vào cho trước thì phải sử dụng các thuật tốn để giải bài tốn đó.
Định nghĩa 2.2 Thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm
hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của
bài toán.
Với mọi thuật toán, bên cạnh tính đúng đắn, thì độ phức tạp tính tốn của thuật tốn

đó cũng là một yếu tố đáng được quan tâm.
Định nghĩa 2.3 Độ phức tạp tính tốn của một thuật tốn là lượng tài ngun tính
tốn mà thuật tốn đó sử dụng để thực hiện cơng việc. Có hai loại tài nguyên cần
quan tâm khi đánh giá độ phức tạp tính tốn của thuật tốn là bộ nhớ và thời gian.
Ngày nay, do sự phát triển của công nghệ chế tạo bộ nhớ, vấn đề tài nguyên bộ nhớ
cho thuật tốn thường ít được tập trung hơn vấn đề về thời gian tính tốn. Thời gian
chạy thực tế của một thuật toán phụ thuộc vào nhiều yếu tố: cấu hình máy, ngơn
ngữ cài đặt và cách thức cài đặt thuật tốn, trình biên dịch và dữ liệu vào, trong đó
dữ liệu vào là yếu tố quan trọng và đặc trưng nhất, được dùng để so sánh hiệu quả
của thuật toán.Để tạo ra sự thống nhất trong cách đánh giá thời gian tính của thuật
tốn, chỉ xét đến yếu tố kích thước dữ liệu vào khi đánh giá.
2.2. Các ký hiệu tiệm cận:
Các ký hiệu tiệm cận thường hay sử dụng khi đánh giá độ phức tạp tính tốn của
thuật tốn gồm có Θ, Ο, Ω và ο, ω. Phần này sẽ nhắc lại định nghĩa và một số tính
chất của các tiệm cận (bỏ qua hai ký hiệu ο, ω).
Định nghĩa 2.4 Cho các hàm f(n) và g(n) là các hàm số của số n nguyên dương
 Θ(g(n)) = {f(n): tồn tại các hằng số dương c1, c2 và n0 sao cho 0 ≤ c1 ≤
f(n) ≤ c2g(n), với mọi n ≥ n0}. g(n) được gọi là đánh giá tiệm cận đúng
của f(n) hay f(n) có bậc là g(n).
 Ο(g(n)) = {f(n): tồn tại các hằng số dương c và n0 sao cho f(n) ≤ cg(n),
với mọi n ≥ n0} g(n) gọi là tiệm cận trên tiêm cận của f(n) hay f(n) có bậc
khơng q g(n).
 Ω(g(n)) = {f(n): tồn tại các hằng số dương c và n0 sao cho cg(n) ≤ f(n),
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

với mọi n ≥ n0}. g(n) được gọi là tiệm cận dưới tiệm cận của f(n) hay f(n)
có bậc ít nhất là g(n).
Để sử dụng các ký hiệu tiệm cận ở bên trong việc đánh giá thời gian tính của các
thuật tốn, các quy ước sau được sử dụng:
 Nếu thuật tốn có thời gian tính trong tình huống nhanh nhất (tốt nhất)
t(n) với kích thước dữ liệu đầu vào n và t(n) = Ω(g(n)) thì thời gian tính
tốt nhất của thuật tốn có bậc khơng nhỏ hơn g(n) hay thời gian tính tốt
nhất của thuật tốn là Ω(g(n)).
 Nếu thuật tốn địi hỏi thời gian tính trong tình huống chậm nhất (tồi
nhất) t(n) với kích thước dữ liệu đầu vào n và t(n) = Ο(g(n)) thì thời gian
tính tốt nhất của thuật tốn có bậc khơng nhỏ hơn g(n) hay thời gian tính
tốt nhất của thuật tốn là Ο(g(n)).
 Nếu thuật tốn địi hỏi thời gian tính trong trung bình t(n) với kích thước

dữ liệu đầu vào n và t(n) = Θ(g(n)) thì thời gian tính tốt nhất của thuật
tốn có bậc khơng nhỏ hơn g(n) hay thời gian tính tốt nhất của thuật tốn
là Θ(g(n)).
Thơng thường khi nói thuật tốn có thời gian tính là Ο(f(n)) thì hiểu là thời gian tính
của thuật tốn đánh giá trong tình huống tồi nhất là Ο(f(n)).
Cịn khi nói thuật tốn có thời gian tính là Ω(f(n)) thì hiểu đánh giá thời gian tính
của thuật tốn trong tình huống tốt nhất là Ω(f(n)).
2.3. Độ phức tạp tính tốn của bài tốn
Định nghĩa 2.5 Độ phức tạp tính tốn của một bài tốn là thời gian tính (ở đây chỉ
quan tâm đến đánh giá thời gian thực hiện, bỏ qua đánh giá về yêu cầu bộ nhớ) của
thuật toán tốt nhất trong số tất cả các thuật toán giải bài tốn đó.
Với bài tốn chắc chắn sẽ có những thuật toán chưa biết, vậy làm thế nào để biết
được thời gian tính của thuật tốn tốt nhất? Có 2 cách để giải quyết vấn đề này:
 Cách thứ nhất: Sử dụng các kỹ thuật đưa ra cận dưới cho độ phức tạp tính
tốn của bài tốn.
 Cách thứ hai: Chỉ ra rằng bài tốn đang xét có mức độ khó (tức là độ
phức tạp tính tốn) khơng thua kém gì bất kỳ một bài tốn khó nào hiện
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Ο(f(n)) = 2 ;

2 n ; n!

Định nghĩa 3.2 Bài toán quyết định là bài toán mà đầu ra của nó chỉ có thể là
“yes” hoặc “no” (0 hoặc 1 đúng hoặc sai…).
Định nghĩa 3.3 Xét bài tốn tối ưu hóa (P) max{f(x): x  D}.Ta gọi bài toán dạng
quyết định tương ứng với bài toán tối ưu (P) là bài toán quyết định sau:
(PD) “Cho giá trị K. Hỏi có tìm được u  D sao cho f(u) ≥ K hay khơng?”
Bài tốn tối ưu và bài tốn quyết định của nó có mối liên hệ được phát biểu trong
định lý sau:
Định lý 3.1 Nếu bài toán quyết định tương ứng với một bài toán tối ưu có thể giải
được hiệu quả (chẳng hạn bằng thuật tốn có thời gian tính đa thức) thì bài tốn tối
ưu đó cũng giải được hiệu quả (bằng thuật tốn thời gian tính đa thức).
Định nghĩa 3.4 Ta gọi bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời
“yes” cho bộ dữ liệu vào “yes” của bài toán là một bằng chứng có độ dài bị chặn
bởi một đa thức bậc cố định của độ dài dữ liệu đầu vào của bài toán, và việc kiểm
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hồn

tra nó là bằng chứng xác nhận câu trả lời “yes” đối với đầu vào đã cho của bài
tốn có thể thực hiện xong sau thời gian đa thức.
3.2. Lớp bài toán P, NPvà co-NP
Dưới đây là phân loại các lớp của bài toán:
Định nghĩa 3.5 P là lớp bài tốn quyết định có thể được giải quyết trong thời gian
đa thức.
Hay nói cách khác, P là lớp các bài tốn có thể được giải một cách nhanh chóng.
Định nghĩa 3.6 NP là lớp bài tốn quyết định mà để xác nhận câu trả lời là “yes”
của nó, có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Hay có thể nói NP là lớp bài tốn mà có thể kiểm tra câu trả lời “yes” một cách
nhanh chóng trong thời gian đa thức nếu đã có được lời giải.
Hiển nhiên ta có P ⊂ NP, tuy nhiên xác định xem NP ⊂ P hay không hiện vẫn chưa
có lời giải.
Định nghĩa 3.7 co-NP là lớp bài tốn mà để xác nhận câu trả lời “no” thì có thể
đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Như vậy có thể thấy co-NP là lớp bài tốn hồn tồn ngược với lớp NP. Có thể
miêu tả mối quan hệ giữa ba lớp bài tốn trên như trong hình dưới đây:

NP

Co-NP

P

Hình 4: Các lớp bài tốn P, NP và co-NP

3.3. Khái niệm quy dẫn
Định nghĩa 3.8 Giả sử A và B là hai bài tốn quyết định. Ta nói bài tốn A có thể
quy dẫn sau thời gian đa thức về bài toán B nếu tồn tại thuật toán thời gian đa thức
R cho phép biến đổi bộ dữ liệu vào x của A thành bộ dữ liệu vào R(x) của B sao cho
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

x là bộ dữ liệu “yes” của A khi và chỉ khi R(x) là bộ dữ liệu “yes” của B.

x
Đầu vào
cho A

Thuật toán
quy dẫn R

R(x)

Yes/no

Thuật toán
giải B

Đầu vào
cho B

Đầu ra
cho B

Đầu ra
cho A

Hình 5:Sơ đồ quá trình quy dẫn

Ký hiệu A < B được dùng để chỉ bài tốn A có thể quy dẫn về bài tốn B. Phép quy
dẫn thường dùng để so sánh độ khó của hai bài toán. Nếu A quy dẫn được về B thì
A khơng khó hơn B. Nếu A là khó (theo nghĩa chưa tìm được thuật tốn thời gian
tính đa thức để giải A ) thì B cũng là khó, cịn nếu B là dễ (nghĩa là đã có thuật tốn
thời gian tính đa thức giải B) thì A cũng là dễ.
3.4. Lớp bài tốn NP-đầy đủ và NP-khó
Định nghĩa 3.9 Một bài toán quyết định A được gọi là NP-đầy đủ nếu như A là bài
toán trong NP và mọi bài tốn trong NP đều có thể quy dẫn về A.
Định nghĩa 3.10 Một bài toán A được gọi là NP-khó nếu như sự tồn tại thuật tốn
đa thức để giải nó kéo theo sự tồn tại thuật tốn đa thức để giải mọi bài tốn trong
NP.
Nói cách khác, nếu có thể giải một bài tốn NP-khó nào đó một cách nhanh chóng,
thì cũng có thể nhanh chóng giải quyết bất kỳ một bài toán nào khác. Bài toán NPkhó ít nhất là khó bằng bất cứ một bài tốn nào trong NP. NP-đầy đủ là những bài
tốn khó nhất trong NP. Hình dưới đây biểu diễn cách phân lớp tạm thời các bài
toán.

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

thống các đỉnh, các giải thuật như vậy gọi là các giải thuật tìm kiếm trên đồ thị.
Mục này sẽ trình bày hai giải thuật cơ bản nhất: Tìm kiếm theo chiều sâu và tìm
kiếm theo chiều rộng.
4.1.

Tìm kiếm theo chiều sâu

Ý tưởng của giải thuật là xuất phát từ một đỉnh và đi cho đến khi không thể đi tiếp
được nữa thì quay lại đỉnh xuất phát trước đó. Trong q trình quay lại:
 Nếu gặp một cạnh đi đến một đỉnh chưa được thăm thì tiếp thì lặp lại bước
trên.
 Nếu khơng tìm được cạnh nào đến một đỉnh chưa được thăm thì kết thúc tìm
kiếm.
Giải thuật có thể viết mã giả dưới dạng đệ quy như sau:
DFS
1.

Procedure DFS(u ∈ V)

2.

visit(u) ← true

3.

For (v ∈ V and (u, v) ∈ E)

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

11

DFS(v)

7.

endIf

8.

endFor

9.

End Procedure

1

4

2

3

6

7

5

Thứ tự thăm: 1, 2, 4, 6, 5, 3, 7

Hình 7: Minh họa tìm kiếm theo chiều sâu

Quá trình thăm các đỉnh diễn ra như sau: Saukhi thăm đỉnh 1, vì đỉnh 2 chưa được
thăm nên đi theo cạnh (1, 2) thăm đỉnh 2, tiếp tục theo cạnh (2, 4) tới thăm đỉnh 4.
Từ đỉnh 4 không thể tiếp tục đi xa hơn, quay lại đỉnh 2. Từ đỉnh 2 theo cạnh (2, 6)
đến thăm đỉnh 6, từ đỉnh 6 đến thăm đỉnh 5. Từ đỉnh 5, vì đỉnh 1 đã được thăm nên
quay lại đỉnh 6 rồi quay lại đỉnh 2. Tại đỉnh 2, vì tất cả các đỉnh kề với đỉnh 2 đã
được xét nên quay lại đỉnh 1. Từ đỉnh 1 tiếp tục thăm các đỉnh 3 và 7.
Độ phức tạp tính tốn:
Giải thuật tìm kiếm theo chiều sâu thăm mỗi đỉnh và mỗi cạnh đúng một lần. Nếu
biểu diễn đồ thị bằng ma trận kề giải thuật có độ phức tạp là O(|V|2), biểu diễn bằng

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hồn

danh sách kề giải thuật có độ phức tạp là O(|V| + |E|).
4.2.

Tìm kiếm theo chiều rộng

Ý tưởng của giải thuật là lập lịch duyệt các đỉnh. Việc thăm một đỉnh sẽ lên lịch
duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần đỉnh s
(đỉnh duyệt đầu tiên) nhất sẽ được duyệt trước). Các đỉnh chờ thăm được xếp vào
hàng đợi. Tại mỗi bước, đỉnh nằm đầu hàng đợi sẽ được thăm và các đỉnh kề với nó
chưa được thăm sẽ được xếp vào cuối hàng đợi. Tiếp tục q trình trên cho đến khi
khơng cịn đỉnh nào trong hàng đợi.
Mã giả của giải thuật tìm kiếm theo chiều rộng:
BFS
1.

Procedure BFS(s∈ V)

2.

queue ← ∅

3.

Push(s) // Thêm đỉnh s vào hàng đợi

4.

visit(s) ← true

5.

While (queue ≠ ∅ ) do
u ← pop() // lấy đỉnh u từ hàng đợi

6.
7.

For (v ∈ V and (u, v) ∈ E)

8.

If (not visit(v)) then

9.

visit(v)← true

10.

push(v)

11.

endIf

12.

endFor

13.

endWhile

14.

End Procedure

Độ phức tạp tính tốn:
Giống như giải thuật tìm kiếm theo chiều sâu, giải thuật tìm kiếm theo chiều rộng
thăm mỗi đỉnh và mỗi cạnh đúng 1 lần, do đó độ phức tạp của giải thuật là O(|V| +
|E|) nếu biểu diễn đồ thị theo danh sách kề.

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

3

4

1

20

5

6

6

4
Hình 8: Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4

5.1. Giải thuậtDijkstra
Giải thuật Dijkstra cho phép tìm đường đi ngắn nhất từ một đỉnh s đến các đỉnh cịn
lại của đồ thị có trọng số.
Phương pháp của giải thuật là xác định tuần tự đỉnh có chiều dài đến s theo thứ tự
tăng dần.
Giải thuật được xây dựng dựa trên cơ sở gán cho mỗi đỉnh các nhãn tạm thời. Nhãn
tạm thời của các đỉnh cho biết cận trên của chiều dài đường đi ngắn nhất từ s đến
đỉnh đó.Nhãn của các đỉnh sẽ biến đổi trong các bước lặp, mà ở mỗi bước lặp sẽ có
một nhãn tạm thời trở thành chính thức. Nếu nhãn của một đỉnh nào đó trở thành
chính thức thì đó cũng chính là chiều dài ngắn nhất của đường đi từ s đến đỉnh đó.
Giải thuật Dijkstra
15.

For all v  V do

16.

d(v) ← ∞

17.

color[u] ← white

18.

End For

19.

d[s] ← 0

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

For all v là đỉnh kề của u do

25.

If (d[u] + w(u,v) < d[v])

26.

d[v] ← d[u] + w(u,v)

27.

pred[v] ← u

28.

End If

29.

End For

30.

Color[u] ← black

31.

Q←Q\u

32.

End While

Độ phức tạp tính tốn:
Thời gian chạy của giải thuật Dijkstra phụ thuộc vào hàng đợi ưu tiên nhỏ nhất
được cài đặt như thế nào. Xét trường hợp chúng ta duy trì hàng đợi ưu tiên nhỏ nhất
bằng cách tận dụng các đỉnh được đánh số từ 1 đến |V|. Chúng ta đơn giản lưu trữ
d[v] nó dưới dạng mảng. Mỗi thao tác chèn hay xóa cần O(1) thời gianvà thao tác
tìm đỉnh có d[u] nhỏ nhất cần O(|V|) thời gian (cần tìm kiếm trên tồn bộ phần tử
của mảng). Như vậy toàn bộ thời gian cần thiết của giải thuậtDijkstra sẽ là
O(|V|2+|E|) = O(|V|2). Kết hợp giải thuật Dijkstra với cấu trúc dữ liệu heap, độ phức
tạp của giải thuật là O((|V| + |E|).log(|V|)). Nếu sử dụng Fibonacci heap thì độ phức
tạp của giải thuật Dijkstra giảm xuống O(|E| + |V|.log(|V|)).
5.2.

Giải thuật Ford-Bellman

Trong trường hợp đồ thị có trọng số âm, chúng ta khơng thể áp dụng giải thuật
Dijkstra để tìm đường đi ngắn nhất. Giải thuật Ford-Bellman được đề xuất để giải
bài tốn tìm đường đi ngắn nhất trên đồ thị có thể có trọng số âm.
Giải thuật Ford-Bellman có thể phát biểu rất đơn giản:
Với đỉnh xuất phát là s, gọi d[v] là khoảng cách từ s tới v với các giá trị khởi tạo là:
Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Định tuyến đa điểm trên mạng cảm biến không dây nhiệm vụ tuần hoàn

 d[s] = 0
 d[v] =  nếu v  s
Sau đó ta tối ưu hóa dần các d[vư như sau: Xét mọi cặp đỉnh u, v của đồ thị, nếu có
một cặp đỉnh u, v mà d[v] > d[u]+c[u,v] thì ta đặt lại d[v] = d[u]+c[u,v]. Tức là nếu
độ dài đường đi từ s tới v lại lớn hơn tổng độ dài đường đi từ s tới u cộng với độ dài
từ u tới v thì ta sẽ hủy bỏ đường đi từ s tới v đang có và coi đường đi từ s tới v
chính là đường đi từ s tới u sau đó đi tiếp từ u tới v. Giải thuật sẽ kết thúc khi không
thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa.
Giải thuật Ford-Bellman
1.

For all v V do d[v] ← 

2.

d[s] ← 0

3.

Repeat

4.

stop ←true

5.

For all u V do

6.

For all vV: (u,v) E do

7.

If (d[v] > d[u]+c[u][v])then

8.

d[v] ← d[u]+c[u][v]
Stop ←true

9.

10.

End If

11.

End for

12.

End for

13.

Until stop

Độ phức tạp tính tốn:
Vì đường đi ngắn nhất là đường đi đơn, nên mỗi đỉnh chỉ xuất hiện 1 lần ở trên
đường đi đó, suy ra vịng lặp repeat của giải thuật chỉ lặp tối đa |V| lần để sửa nhãn
cho các đỉnh. Giải thuậtFord-Bellman sử dụng 3 vòng lặp lồng nhau, mỗi vòng lặp
thực hiện |V| bước lặp, do đó độ phức tạp của giải thuật là O(|V|3).
5.3. Giải thuật Floyd-Warshall

Học viên thực hiện: Võ Khánh Trung – CB140145 – 2014B CNTT

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

Giải thuật tìm kiếm địa phương giải bài toán định tuyến đa điểm tối ưu năng lượng trên mạng cảm biến không dây nhiệm vụ tuần hoàn

Tài liệu liên quan

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