ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Vũ Đức Việt

ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG
QUẢN LÝ GIAO THÔNG

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

HÀ NỘI-2015


ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Vũ Đức Việt

ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG
QUẢN LÝ GIAO THÔNG

Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN HÀ NAM

HÀ NỘI-2015


LI CAM

OAN

Tổi xin cam oan lun vôn n y l cổng trnh nghiản cứu ca riảng tổi. CĂc s liằu, kt
quÊ ữổc trnh b y trong lun vôn l ho n to n trung thỹc v chữa tng ữổc cổng b trong
bĐt ký mt cổng trnh n o khĂc. Tổi  trch dÔn y cĂc t i liằu tham khÊo, cổng tr
nh nghiản cứu liản quan trong nữợc v quc t. Ngoi tr cĂc t i liằu tham khÊo n y, lun
vôn ho n to n l sÊn ph'm ca riảng tổi.

H Ni, ng y 20 thĂng 10 nôm 2015
Kỵ tản ........................................................................

i


LIC MèN
Lới u tiản tổi xin gòi lới cÊm ỡn v lặng bit ỡn sƠu sc nhĐt tợi PGS.TS. Nguyn H Nam,
Ths. L ông Nhc  tn tnh ch bÊo, giúp ù v hữợng dÔn tổi trong sut quĂ trnh thỹc
hiằn lun vôn n y.
Tổi xin chƠn th nh cÊm ỡn quỵ thy cổ v nh trữớng  luổn to iu kiằn thun lổi nhĐt cho
chúng tổi hồc tp v nghiản cứu.
Cui cũng tổi xin gòi lới cÊm ỡn tợi gia nh, bn b ca tổi. Nhng ngữới luổn gi nh thới
gian bản cnh quan tƠm, ng viản, v giúp ù tổi ht mnh trong sut quĂ trnh hồc tp
cụng nhữ l m lun vôn tt nghiằp n y.

H Ni, ng y 20 thĂng 10 nôm 2015

Kỵ tản ........................................................................

ii


Möc löc
1 TŒng quan

1.1 Hi»n tr⁄ng giao thæng t⁄i Vi»t Nam . .
1.2 C¡c gi£i ph¡p hØ træ cho ng÷íi tham
1.3 Gi£i ph¡p • xu§t . . . . . . . . . . . . . . . .
2 C¡c ki‚n thøc cì sð
2.1 T¡c tß v h» a t¡c tß . . . . . . . . . . . .
2.1.1
2.1.2
2.1.3
2.1.4
2.2 H» thŁng Vanet . . . . . . . . . . . . . . . .
2.3 Cæng cö mæ phäng m⁄ng VANET 3 C¡c gi£i thu“t t…m ÷íng
3.1 Nhœng thu“t to¡n cì b£n . . . . . . . . .
3.1.1
3.1.2
3.2 C¡c thu“t to¡n t…m ÷íng n¥ng cao .
3.2.1

3.2.2
3.2.3
3.3 Lüa chån thu“t to¡n . . . . . . . . . . . . .
3.3.1
3.3.2


iii


MÖC LÖC
4

Thüc nghi»m v c¡c k‚t qu£
4.1

4.3

p döng Ant Colony System cho v§n
4.1.1
4.1.2
Thüc nghi»m . . . . . . . . . . . . . . . . .
4.2.1
4.2.2
K‚t qu£ . . . . . . . . . . . . . . . . . . . . . .

KTLUN
5.1
5.2

C¡c cæng vi»c ¢ l m . . . . . . . . . . . .
H÷îng nghi¶n cøu trong t÷ìng lai . . .

4.2

5



Danh sĂch hnh v
1.1 CĂc cổng cử tm
ữớng . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1 TĂc tò trong mổi trữớng ca nõ. TĂc tò s lĐy thổng tin t mổi trữớng
v phÊn ứng li . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 V dử minh

hồa v mng VANET . . . . . . . . . . . . . . . . . . . . 11
2.3
Cổng cử mổ phọng VANETsim . . . . . . . . . . . . . . . .
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10

Mổ hnh hằ thng Vanetsim . . . . . . . . . . . . . . . . . .
Mổ hnh hằ thng Vanetsim vợi Ant Colony System
Biu ỗ luỗng ca thut toĂn ACS cho vĐn ti ữu hoĂ ữ
Thỹc nghiằm vợi bÊn ỗ th
Thỹc nghiằm vợi bÊn ỗ th

im tc nghn trản bÊn ỗ Berlin . . . . . . . . . . . . . . . . .
im tc nghn trản bÊn ỗ H Ni . . . . . . . . . . . . . . . . . .
Kt quÊ ch dÔn ữớng i ca thut toĂn A* trản bÊn ỗ Be
Kt quÊ ch dÔn ữớng i ca thut toĂn ACS trản bÊn ỗ
Kt quÊ ch dÔn ữớng i ca thut toĂn A* trản bÊn ỗ th
H Ni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.11 Kt quÊ

ch dÔn ữớng i ca thut toĂn ACS trản bÊn ỗ th nh ph
H Ni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

v


Danh s¡ch b£ng
4.1 K‚t qu£ thüc nghi»m tr¶n b£n ç th
4.2 K‚t qu£ thüc nghi»m tr¶n b£n ç th

vi


Danh möc tł vi‚t t›t
ACS
Ant Colony System
ACO
Ant Colony Optimization
AS
Ant System
VANET Vehicular Ad Hoc Networks
MANET Mobile Ad Hoc Networks
RSU

Road Side Unit
OBU
On Board Unit
PSO
Particle Swarm Optimization
GA
Genetic Algorithm

vii


M U
Vn chuyn h nh khĂch, h ng hõa v thổng tin luổn õng mt vai trặ quan trồng trong
x hi hiằn i. CĂc hot ng kinh t trong thới i hiằn nay gn cht vợi giao thổng, chnh
v th ti nhng quc gia phĂt trin, giao thổng luổn ữổc quy hoch v u tữ phĂt
trin úng mức. Ngo i ra nhng nữợc phĂt trin, tm nhn chin lữổc v phĂt trin cỡ
s h tng giao thổng luổn ữổc ữu tiản úng mức, nhớ vy nhng nữợc phĂt trin
luổn cõ ữổc hằ thng giao thổng n nh, phũ hổp trong nhiu nôm. Cặn
nhng nữợc ang phĂt trin nhữ Viằt Nam, tnh trng cỡ s h tng giao thổng khổng
theo kp vợi sỹ phĂt trin kinh t x hi cụng nhữ sỹ bũng n dƠn s v gia tông cĂc
phữỡng tiằn giao thổng, gƠy cÊn tr v km hÂm sỹ phĂt trin ca cÊ quc gia. Hiằn
nay, thỹc trng giao thổng Viằt Nam ang l mt vĐn nhức nhi i vợi nhng ngữới
tham gia giao thổng. Theo thng kả t cửc thng kả, s lữổng cĂc phữỡng tiằn mợi
phĂt sinh tham gia giao thổng Viằt Nam u tông theo tng nôm, trong khi õ hằ
thng giao thổng Viằt Nam chữa Ăp ứng ữổc sỹ bũng n v cĂc phữỡng tiằn tham
gia giao thổng cụng nhữ lữu lữổng giao thổng hiằn ti. cĂc ổ th lợn nhữ th ổ H
Ni, th nh ph Hỗ Ch Minh ..., tnh trng n y cặn phức tp hỡn, chữa k n nhng
hằ thng ữớng, bin bĂo, vch kã ữớng hỉn n, thiu nhĐt quĂn, khổng theo quy chu'n
chung n o v mang c tnh giÊi phĂp tnh th ca cĂc nh chức trĂch. Ngo i ra ỵ thức
tham gia giao thổng ca ngữới dƠn chữa tt cụng dÔn n hu quÊ l sỹ gia tông tnh

trng tc ữớng, tai nn giao thổng v ổ nhim mổi trữớng. iu n y dÔn n nhng Ênh
hững trỹc tip v sức khọe, l m tn km thới gian v cõ th Ênh hững n tnh mng
ca nhng ngữới tham gia giao thổng. hỉ trổ ti a ngữới tham gia giao thổng cõ
th di chuyn hiằu quÊ trản quÂng ữớng ca mnh, Â cõ nhiu hnh thức cụng nhữ
biằn phĂp ữổc ra. Ti M v gn Ơy Viằt Nam, cĂc bÊn tin v giao thổng luổn cp
nht tin tức v tnh trng giao thổng trản ữớng giúp ngữới tham gia giao thổng lỹa
chồn ữổc quÂng ữớng ti ữu, hiằn nay mt s hÂng cổng nghằ lợn ang phĂt trin mổ
hnh ổ tổ tỹ lĂi v cĂc hằ thng hỉ trổ cp nht thới gian thỹc

1


DANH S CH B NG
cho cĂc lĂi xe khi tham gia giao thổng. Tuy nhiản nhng cĂch tip cn trản
ch cõ th Ăp dửng ti mt s nỡi Viằt Nam hoc chữa cõ khÊ nông Ăp dửng trong
tữỡng lai gn. Trong lun vôn n y, chúng tổi sò dửng phữỡng phĂp mổ phọng mổ
hnh giao thổng thỹc t kt hổp thut toĂn ti ữu quÂng ữớng ữa ra lỹa chồn
hổp lỵ nhĐt cho ngữới tham gia giao thổng.
Ni dung lun vôn n y ữổc chúng tổi trnh b y nhữ sau:
Chữỡng 1: Tng quan
Chữỡng 2: CĂc kin thức cỡ s
Chữỡng 3: CĂc thut toĂn tm ữớng
Chữỡng 4: Thỹc nghiằm v cĂc kt quÊ
Chữỡng 5: Kt lun
Chúng tổi ữa ra cĂi nhn khĂi quĂt v hiằn trng hằ thng giao thổng Viằt Nam, cĂc
giÊi phĂp, nghiản cứu v giao thổng ti Chữỡng 1. Chữỡng 2, chúng tổi trnh
b y cĂc kin thức cỡ s liản quan tợi hằ thng a tĂc tò, tĂc tò thổng minh, mng

VANET, Ơy l nhng kin thức cỡ s liản quan tợi mổi trữớng thỹc nghiằm ca
chúng tổi. Chúng tổi trnh b y nhng thut toĂn tm ữớng truyn thng v thut

toĂn chúng tổi Ăp dửng Chữỡng 3. CĂc thỹc nghiằm v kt quÊ thỹc nghiằm vợi hằ
thng Vanet vợi thut toĂn chúng tổi Ăp dửng ữổc chúng tổi trnh b y Chữỡng
4. Cui cũng, chúng tổi ữa ra nhn xt v nhng kt quÊ t ữổc v cĂc hữợng phĂt
trin trong tữỡng lai ti phn Kt lun Chữỡng 5 ca lun vôn.


Chữỡng 1
Tng quan
1.1

Hiằn trng giao thổng ti Viằt Nam

Theo bĂo cĂo ca u ban an to n giao thổng quc gia, s lữổng ngữới thiằt mng
do tai nn giao thổng nhng nôm gn Ơy u con s lợn t 9000 n 13000 ngữới
thiằt mng h ng nôm. Trong õ Ăng chú ỵ l tai nn giao thổng ữớng b chim t trồng
rĐt lợn t 97% n 99%, tai nn liản quan n ổ tổ, xe mĂy chim trản 70% tng s
vử trản cÊ nữợc. Ngo i ra tnh trng ũn tc thữớng xuyản xÊy ra ti cĂc th nh ph
lợn v o nhng giớ cao im, nhng ng y ngh l, ngh tt gƠy Ênh hững nghiảm
trồng tợi thới gian i li v sỹ an to n ca ngữới tham gia giao thổng. Trữợc thỹc trng
Ăng buỗn trản, cõ th k n mt v i nguyản nhƠn sau:
Nhiu dỹ Ăn xƠy dỹng liản tửc ữổc trin khai nhng th nh ph lợn nhữ H
Ni hay Hỗ Ch Minh dÔn tợi mt s tuyn ữớng b cĐm hoc thu hàp l n
1

ữớng li l m gia tông cĂc im ũn tc giao thổng .
H tng giao thổng ca nữợc ta  lc hu v quy hoch thiu khoa hồc, khổng
Ăp ứng ữổc nhu cu i li ca ngữới dƠn. Theo bĂo cĂo ca b giao thổng vn
tÊi, s lữổng cĂc phữỡng tiằn tham gia giao thổng ang cõ triu hữợng tông
mnh. Ti H Ni, s lữổng phữỡng tiằn giao thổng ông kỵ mợi trong ba quỵ
u nôm 2015 l 5.5 triằu phữỡng tiằn. Tng s lữổng phữỡng tiằn tham gia

giao thổng H Ni  gĐp 6 ln lữu lữổng chu tÊi ca hằ thng giao
thổng trản th nh ph.
1

gia-tang-nhieu-diem-un-tac-giaothong.aspx

3


1.2. CĂc giÊi phĂp hỉ trổ cho ngữới tham gia giao thổng

ị thức ca ngữới dƠn i vợi viằc thỹc hiằn ni quy giao thổng chữa thỹc sỹ
tt, nhng lỉi thữớng mc phÊi ch yu l vữổt n ọ, i sai l n ữớng...
Nhng lỉi n y gõp phn gia tông tnh trng Ăch tc giao thổng v o giớ cao
im.
CĂc thức quÊn lỵ giao thổng ổ th Viằt Nam cặn chữa cht ch, trang
thit b k thut lc hu, thiu nhng giÊi phĂp giao thổng cõ th hỉ trổ tt
cho ngữới quÊn lỵ v ngữới tham gia giao thổng mt cĂch thit thỹc v trỹc tip
nhĐt.
Trữợc nhng thỹc trng v nguyản nhƠn trản ca ng nh giao thổng vn tÊi nữợc
nh , viằc ữa ra nhng giÊi phĂp hổp lỵ l rĐt cn thit v cĐp bĂch.

1.2

CĂc giÊi phĂp hỉ trổ cho ngữới tham gia giao
thổng

Hiằn nay, cõ mt s giÊi phĂp ữổc ữa ra nhm trớ giúp cho ngữới tham gia giao
2


thổng ph bin nhữ kảnh VOV Giao thổng do i VOV th nh lp , Ơy l kảnh thổng
tin cp nht tnh trng giao thổng trản cĂc tuyn ữớng Viằt Nam. Tuy nhiản phm vi
hot ng ch yu ca kảnh VOV giao thổng ch tp trung chnh v o th nh ph v dỹa
nhiu v o sỹ phÊn hỗi t nhng lĂi xe i trản ữớng, ngo i ra Ơy cụng ch l kảnh thổng
tin trổ giúp ữa ra thổng tin b ch cho nhng lĂi xe chứ chữa th hỉ trổ trỹc tip
cho ngữới tham gia giao thổng. Ngo i giÊi phĂp hỉ trổ thổng tin theo kảnh radio,
ngữới tham gia giao thổng cụng cõ th nhn ữổc sỹ hỉ trổ t cĂc cổng cử bÊn ỗ
3

4

5

nhữ Google Map , Bing Map , Here Map ... tợi t cĂc tp o n cổng nghằ thổng tin
6

ni ting trản th giợi hay Vietmap - mt giÊi phĂp tợi t Viằt Nam nhữ hnh 1.1. Tuy
nhiản cĂc giÊi phĂp tợi t cĂc cổng cử bÊn ỗ
n y ch ỡn thun kt hổp thổng tin vằ tinh GPS v bÊn ỗ s ữa ra nhng

ch dÔn cho ngữới dũng trong viằc xĂc nh ữớng i m khổng th kt hổp thảm
thổng tin v lữu lữổng xe, hiằn trng giao thổng trản ữớng ữa ra ch dÔn cho
ngữới tham gia giao thổng. Ngo i ra hiằn nay  cõ mt s nh khoa hồc nghiản
cứu v
2
3
4


/>

/>
6

5


1.3. GiÊi phĂp xuĐt

vĐn mổ phọng giao thổng t õ tm ra v tr xƠy dỹng cụng nhữ phƠn luỗng
hiằu quÊ giao thổng. Trản th giợi  cõ mt s nhõm nghiản cứu v vĐn tm
ữớng i ngn nhĐt những thữớng ch Ăp dửng cho mt bÊn ỗ xĂc nh v phn nhiu
vÔn cõ thiản hữợng nghiản cứu v cổng cử mổ phọng.

Hnh 1.1: CĂc cổng cử tm ữớng

1.3

GiÊi phĂp

xuĐt

Trữợc thỹc trng giao thổng Viằt Nam nõi trản, xƠy dỹng ữổc mt giÊi phĂp giao
thổng ỗng b cõ tnh ứng dửng cao cn phÊi cõ sỹ phi hổp ca nhiu pha, t
cĂc cỡ quan quÊn lỵ giao thổng cho tợi nhng ngữới tham gia giao thổng. Trong
khuƠn kh ca lun vôn n y chúng tổi quyt nh nghiản cứu v nhng thut toĂn
dÔn ữớng cho hằ thng mổ phọng giao thổng trản cĂc th nh ph nhm ti ữu hõa


1.3. GiÊi phĂp xuĐt


chi ph i ữớng cho ngữới dƠn khi tham gia giao thổng, qua õ phn n o giĂn tip
cõ th giÊi quyt ữổc b i toĂn Ăch tc giao thổng ti nhng th nh ph lợn bi
nhng lỵ do:
Tit kiằm ữổc thới gian ca ngữới tham gia giao thổng.
QuÂng ữớng i li giÊm qua õ giÊm ữổc lữổng nhiản liằu tiảu thử v lữổng kh
thÊi khi tham gia giao thổng ca cĂc phữỡng tiằn.
Tit kiằm cĂc chi ph i li cho ngữới dƠn.
Khi kt quÊ ca lun vôn ữổc Ăp dửng trong thới i Internet-Of-Things (IOT), ngữới
tham gia giao thổng s cõ thảm mt lỹa chồn hỉ trổ mnh khi tham gia giao
thổng trản ữớng.


Chữỡng 2
CĂc kin thức cỡ s
Trong chữỡng n y, chúng tổi s trnh b y nhng kin thức cỡ s v tĂc tò, tĂc tò
thổng minh, kin thức v mng VANET. Ơy l nhng kin thức cỡ bÊn xƠy dỹng lản
cổng cử VANETsim - cổng cử ữổc chúng tổi sò dửng trong lun vôn ca mnh.

2.1
2.1.1

TĂc tò v hằ

a tĂc tò

TĂc tò

Theo [9], mt tĂc tò (agent) l mt hằ thng mĂy tnh cõ khÊ nông tỹ hot ng c
lp thay mt cho ngữới dũng hoc ngữới ch ca nõ nhn bit cĂi g cn thit phÊi l
m tữỡng thch vợi mửc tiảu  nh trữợc. CĂc tĂc tò cõ th cÊm ứng mổi trữớng v

phÊn ứng li mổi trữớng. Sỹ tữỡng tĂc n y din ra liản tửc v khổng cõ giợi hn.
Thổng thữớng, mt tĂc tò s trang b mt tp cĂc h nh ng. Tp hổp cĂc h nh ng
th hiằn khÊ nông phÊn ứng li vợi mổi trữớng ca cĂc tĂc tò. Tuy nhiản, khổng
phÊi tĐt cĂc h nh ng ca chúng cõ th thỹc hiằn ữổc trong tĐt cÊ cĂc trng thĂi.
V th mỉi h nh ng phÊi cõ cĂc tin iu kiằn xĂc nh cĂc iu kiằn thch hổp
nõ cõ th Ăp dửng. Hnh 2.1 ữa ra mt cĂi nhn tru tữổng v tĂc tò. Trong h
nh trản, chúng ta cõ th thĐy ữổc h nh ng ữa ra ữổc to bi tĂc tò tĂc ng n
mổi trữớng ca nõ. VĐn quan trồng vợi mt tĂc tò l chúng phÊi ữa ra ữổc quyt
nh cho nhng h nh ng n o cn phÊi ữổc thỹc hiằn t ữổc mửc tiảu m nõ
ữổc thit k. Kin trúc tĂc tò thỹc ra l kin trúc hằ thng phn mm thit k cho viằc
ra quyt nh trong mt mổi trữớng.

7


2.1. TĂc tò v hằ a tĂc tò

Hnh 2.1: TĂc tò trong mổi trữớng ca nõ. TĂc tò s lĐy thổng tin t mổi trữớng
v phÊn ứng li

2.1.2

Mổi trữớng

Nhữ Â nõi trản, kin trúc tĂc tò thỹc ra l kin trúc phn mm cho hằ thng sinh
quyt nh ữổc thit k trong mt mổi trữớng. Tnh phức tp ca tin trnh sinh
quyt nh tũy thuc v o thuc tnh ca mổi trữớng. Theo [6] th mổi trữớng cõ
th phƠn loi dỹa v o thuc tnh nhữ sau:
Tip cn v khổng th tip cn: Mổi trữớng tip cn ữổc l mổi trữớng m mỉi tĂc
tò cõ th t ữổc y chnh xĂc v cp nht kp thới cĂc thổng tin v trng thĂi

mổi trữớng. Phn lợn mổi trữớng trong thỹc t u l loi khổng th tip cn
ữổc.
Mổi trữớng tắnh v mổi trữớng ng: Mổi trữớng tắnh l mổi trữớng m cõ
th t giÊ nh l mổi trữớng khổng thay i ngoi tr cĂc tĂc ng ca tĂc tò.
Ngữổc li, mổi trữớng ng l mổi trữớng m cõ sỹ vn ng bản trong nõ tức
l nõ cõ th tỹ thay i khổng phử thuc v o cĂc tĂc ng ca tĂc tò. Mổi
trữớng thỹc t l mt mổi trữớng ng, cõ th v dử nhữ mng Internet.
Mổi trữớng rới rc v mổi trữớng liản tửc: Mổi trữớng rới rc l mổi trữớng m cõ
hu hn cĂc h nh ng v tri giĂc trong Đy. V dử, mổi trữớng trong cớ l rới rc,
mổi trữớng trong giao thổng l liản tửc. Mổi trữớng rới rc th d thit k cĂc
tĂc tò hỡn mổi trữớng liản tửc.


2.1. TĂc tò v hằ a tĂc tò

Mổi trữớng cõ phƠn on hay khổng phƠn on: Trong mổi trữớng phƠn on,
hot ng ca tĂc tò lằ thuc v o s lữổng cĂc on rới rc m khổng liản kt vợi
cĂc hot ng ca tĂc tò trong phƠn on khĂc. Theo cĂc chuyản gia, mổi trữớng
cõ phƠn on ỡn giÊn hỡn v cĂc tĂc tò cõ th quyt nh h nh vi ca nõ dỹa
trản phƠn on hiằn ti. Nõ khổng cn quan tƠm n giao tip gia phƠn on n
y vợi phƠn on k tip ca nõ.
Nhn chung, hu ht cĂc mổi trữớng u l khổng truy cp ữổc, khổng xĂc
nh, ng v liản tửc. Nhng thuc tnh ca mổi trữớng õng mt vai trặ quyt nh
n phức tp ca tin trnh thit k tĂc tò. Tuy nhiản, khổng cõ nghắa õ l nhng
nhƠn t duy nhĐt m ch õng mt phn. Phn quan trồng chnh l sỹ tữỡng tĂc
gia tĂc tò v mổi trữớng.

2.1.3

TĂc tò thổng minh


TĂc tò thổng minh l tĂc tò cõ khÊ nông hot ng linh hot v mm dão ho n th nh
mửc tiảu ữổc giao. Theo [8], tĂc tò thổng minh l tĂc tò cn cõ khÊ nông thỹc
hiằn cĂc h nh vi c biằt nhữ phÊn ứng (reactivity), ch ng (proactivity) v cng tĂc x
 hi (social ability).
PhÊn ứng: KhÊ nông phÊn ứng ca tĂc tò l khÊ nông phÊn ứng li nhng
thay i ca mổi trữớng úng lúc nhm Ăp ứng mửc tiảu  ữổc nh trữợc.
Ch ng: KhÊ nông ch ng ca tĂc tò l khÊ nông luổn ch ng tm cĂch t
ữổc mửc tiảu  ữổc giao. Ch ng Ơy l sinh ra v hữợng n mửc tiảu chứ
khổng phÊi thỹc hiằn mÂi theo cĂc sỹ kiằn xÊy ra. TĂc tò cn phÊi kt hổp
v cƠn bng cÊ hai c im: phÊn x v ch ng mt cĂch thch hổp.
KhÊ nông cng tĂc: KhÊ nông x hi ca tĂc tò l khÊ nông tữỡng tĂc vợi cĂc tĂc
tò khĂc thm ch vợi con ngữới nhm Ăp ứng ữổc nhng mửc tiảu  nh
trữợc. Th giợi thỹc l mt mổi trữớng a tĂc tò. Do vy chúng ta khổng th
ch hữợng n mửc tiảu t ra m khổng quan tƠm n cĂc tĂc tò khĂc. nhng
tĂc tò trong mt hằ a tĂc tò tữỡng tĂc (interact) vợi nhau th ặi họi chúng
phÊi cõ khÊ nông hổp tĂc (cooperate), khÊ nông phi hổp (coordinate) v
khÊ nông m phĂn (negotiate) vợi nhau.


2.1. TĂc tò v hằ a tĂc tò

2.1.4

Hằ thng

a tĂc tò

Theo [9], hằ thng a tĂc tò (multiagent system) l hằ thng bao gỗm cĂc tĂc tò
tữỡng tĂc vợi nhau, trong õ cĂc tĂc tò s hot ng tỹ ch vợi nhng ng cỡ v mửc tiảu

khĂc nhau. Hằ a tĂc tò cõ lổi trong thỹc t bi nõ giúp con ngữới cõ th giÊi quyt
ữổc nhng b i toĂn khõ hiằn nay m cĂc hằ thng ỗng nhĐt khổng giÊi quyt ữổc
nhữ dỹ bĂo thiản tai, mổ phọng li cĂc cĐu trúc trong x hi... Hiằn nay, cĂc hằ a
tĂc tò ữổc nghiản cứu, thò nghiằm v sò dửng hiằn nay phn lợn l cĂc tĂc tò phn
mm.
Nhữ vy, hằ a tĂc tò l mt tp hổp cĂc tĂc tò cũng chia sã mt mổi trữớng trong
õ: Thổng tin hoc khÊ nông giÊi quyt vĐn ca tng tĂc tò l hn ch, khổng y .
Khổng cõ sỹ iu khin tp trung cho to n hằ thng. D liằu phƠn tĂn trản nhng
th nh phn khĂc nhau ca hằ thng. QuĂ trnh tnh toĂn ữổc thỹc hiằn khổng
ỗng b. Mt hằ a tĂc tò thữớng cõ rĐt nhiu tnh chĐt m chúng ta cn suy xt khi
c i t, tuy nhiản, hằ a tĂc tò cỡ bÊn thữớng phÊi cõ nhng tnh chĐt quan trồng
nhữ tnh tỹ ch (autonomy), tm nhn a phữỡng (local views), tnh phƠn tĂn
(decentralization)
Tnh tỹ ch: mỉi tĂc tò thữớng phÊi cõ tnh tỹ ch riảng ca mnh
(nghắa l nõ cõ th tỹ ữa ra quyt nh ca bÊn thƠn tĂc tò õ khi cõ tn hiằu
v o hoc sỹ kiằn n o õ xÊy ra).
Tm nhn a phữỡng: mỉi tĂc tò thữớng ch cn cõ cĂi nhn cửc b v nm
gi mt phn tri thức ca hằ thng thay v to n b cĂc tri thức hiằn cõ
trong hằ thng, nu khổng hằ thng s tr nản quĂ phức tp cõ th mổ
phọng nhng hot ng ging nhữ nõ ang din ra trong thỹc t.
Tnh phƠn tĂn: cĂc tĂc tò thữớng ữổc phƠn tĂn, s khổng cõ tĂc tò n o nm
quyn iu khin cĂc tĂc tò cặn li, nu khổng hằ thng s tr th nh mt hằ
thng ỗng nhĐt, v hiằu nông s b giÊm i rĐt nhiu so vợi nhng g chúng
ta mong mun.
Ngo i ra, cĂc tĂc tò cõ th trao i tri thức thổng qua mt ngổn ng chung, ữổc
xem nhữ l phữỡng thức trao i thổng tin gia cĂc tĂc tò. V dử nhữ cĂc ngổn
ng: KQML (Knowledge Query Manipulation Language) hay FIPAs (Foundation for
Intelligent Physical Agents), ACL (Agent Communications Language)... Mỉi hằ a tĂc
tò tỹ bÊn thƠn nõ u cõ khÊ nông tỹ t chức (self-oganization) v nhng



2.2. Hằ thng Vanet

h nh ng rĐt phức tp, mc dũ mỉi tĂc tò cĂ th thữớng cõ chin lữổc rĐt ỡn giÊn.

2.2

Hằ thng Vanet

Mng VANET (Vehicular Ad Hoc Network) l mt cổng nghằ sò dửng cĂc xe di
chuyn nhữ cĂc nút trong mt mng to nản mt mng di ng. VANET bin mỉi xe
tham gia giao thổng th nh mt router hay mt nút khổng dƠy, cho php cĂc xe n
y cõ th kt ni vợi cĂc xe khĂc trong phm vi bĂn knh t 100 n 300 mt, t õ to
nản mt mng vợi vũng ph sõng rng. Do cĂc xe cõ th i ra khọi vũng ph sõng v
thoĂt khọi mng, trong khi nhng xe khĂc cõ th tham gia, kt ni vợi cĂc phữỡng
tiằn khĂc trản mt mng Internet di ng ữổc to nản. Trong thỹc t, hằ thng u
tiản ữổc tch hổp cổng nghằ n y l cĂc xe ca cÊnh sĂt v lnh cứu họa nhm
liản lc trao i thổng tin vợi nhau phửc vử cho cổng tĂc cứu h, Êm bÊo an ninh
trt tỹ.
Thổng tin trao i trong mng VANET bao gỗm thổng tin v lữu lữổng xe c, t
nh trng kàt xe, thổng tin v tai nn giao thổng, cĂc tnh hung nguy him cn
trĂnh v cÊ nhng dch vử thổng thữớng nhữ a phữỡng tiằn, Internet,. . .

Hnh 2.2: V dử minh hồa v mng VANET
Mửc ch chnh ca VANET l cung cĐp sỹ an to n v thoÊi mĂi cho h nh
khĂch. CĂc thit b iằn tò c biằt ữổc t bản trong cĂc phữỡng tiằn giao thổng s
cung cĐp kt ni mng Adhoc cho cĂc h nh khĂch. Mng n y hữợng n hot ng m
khổng cn cĐu trúc h tng cho php cĂc liản lc ỡn giÊn. Mỉi thit b hot ng
trong mng VANET s l mt nút mng cõ th trỹc tip gòi nhn hoc l m trung gian
trong cĂc phiản kt ni thổng qua mng khổng dƠy. Xt trữớng hổp



2.2. Hằ thng Vanet

xÊy ra ca trm gia cĂc phữỡng tiằn trản ữớng, cĂc tn hiằu cÊnh bĂo s ữổc gòi i
thổng qua mng VANET tợi cĂc phữỡng tiằn tham gia giao thổng, cũng vợi cĂc cổng
cử tiằn ch giúp ù viằc giÊi quyt sỹ c, Êm bÊo an to n cho cĂc phữỡng tiằn khĂc.
Ngữới tham gia giao thổng cụng cõ th kt ni Internet thổng qua mng VANET, thm
ch cõ th sò dửng cĂc dch vử a phữỡng tiằn nhữ trao i thổng tin hnh Ênh,
video, gồi iằn video. Ngo i ra, thổng qua mng VANET, cĂc phữỡng tiằn tham gia
giao thổng cõ th tỹ ng thanh toĂn cĂc cữợc ph nhữ ph gòi xe, ph cu ữớng ...
c im ca mng VANET cụng ging vợi cổng nghằ hot ng ca mng MANET õ l : quĂ
trnh tỹ t chức, tỹ quÊn lỵ, bông thổng thĐp v chia sã ữớng truyn vổ tuyn. Tuy
nhiản im khĂc biằt chnh ca VANET v MANET l
chỉ: cĂc node mng (xe c) di chuyn vợi tc cao v khổng xĂc nh khi truyn t

n hiằu cho nhau. VĐn t ra l chúng ta cn tm hiu, Ănh giĂ giao thức nh
tuyn cho mng VANET dỹa trản kin trúc mng MANET phũ hổp vợi tnh di
ng ca cĂc node mng trong mng VANET.
VANET l mt mng cõ nhng c tnh riảng, cỡ bÊn nhĐt l nõ khổng yảu cu cỡ s h
tng nhữ cĂc hằ thng vổ tuyn khĂc: khổng cn Base Station nhữ nhng hằ thng
di ng khĂc nhau (GSM CDMA, 3G); khổng cn b Access Point hỉ trổ cho Wifi v
Wimax. V yu t khoÊng cĂch, VANET cõ th khc phửc ữổc giợi hn ca truyn dÔn
sõng vổ tuyn nhớ v o cĂc nút trung gian. Tuy nhiản, do giao tip
m khổng cn cỡ s h tng, li dũng bin i nh tuyn qua nhiu tng nản rĐt nhiu

khÊ nông b nghe trm hoc l thổng tin truyn i cõ th b sai lằch. Trong mng viằc
truyn tin tức giao thổng gia cĂc xe vợi nhau l rĐt quan trồng, iu õ cõ th cõ tĂc
dửng tt (nu nhữ thổng tin ữổc truyn i phÊn Ănh ứng tnh hnh giao thổng hoc
cĂc sỹ cổ trản giao l) những cụng cõ th gƠy ra nhng tĂc ng nguy him khổn

lữớng (nu nhữ thổng tin do mt xe truyn i l khổng chnh xĂc hoc sai lằch). S dắ
nhữ vy v khi thit k mng n y, thữớng th cĂc thổng tin s

ữổc phĂt quÊng bĂ v ữổc trung chuyn qua nhiu nút iu õ gƠy ra Ênh hững
nhữ phÊn ứng dƠy truyn .
CĂc c im ca mng VANET
CĂc node mng di chuyn vợi tc cao: Nu hai xe di chuyn ngữổc chiu vợi
tc 25m/s (90km/h) v phm vi truyn dÔn khoÊng 250m th kt ni gia
hai xe ch ko d i khoÊng 5s.
Thữớng xuyản ngt kt ni mng: Nhữ giÊ thit nảu trản th sau 5s hai chic
xe  ngt kt ni vợi nhau, Êm bÊo kt ni thổng sut th chúng ta phÊi


2.3. Cổng cử mổ phọng mng VANET - VANETsim

thit lp liản kt khĂc vợi xe gn õ. Trong cĂc trữớng hổp ngt kt ni nhữ vy,
c biằt trong khu vỹc mt xe thĐp th thữớng xuyản xÊy ra viằc ngt kt
ni mng, giÊi phĂp l phÊi cõ cĂc node mng chuyn tip.
Mổ hnh chuyn ng v dỹ oĂn: Chúng ta cn cĂc thổng tin v v tr cĂc
node v sỹ chuyn ng ca chúng, rĐt khõ oĂn chuyn ng ca cĂc xe. kin
trúc mng hot ng hiằu quÊ chúng ta cn phÊi nghiản cứu mổ hnh
chuyn ng v dỹ oĂn chuyn ng t trữợc.
Mổi trữớng truyn thổng tin: Mổ hnh cĂc node (xe) chuyn ng trản hằ
thng ữớng cao tc, chuyn ng mt chiu iu n y l d dỹ oĂn ữổc những cĐu
trúc ữớng ph, mt xe, tặa nh , cƠy ci li gƠy ra cÊn tr quĂ trnh truyn
thổng tin.
Hn ch tr cứng: CĂc vĐn an to n (tai nn, phanh xe,. . . ) ca node mng
phÊi thổng bĂo n cĂc node mng liản quan. iu n y ỡn giÊn khổng th thọa
hiằp vợi tr d liằu cứng trong vĐn n y. Do õ tc d liằu cao khổng l
vĐn quan trồng cho VANET nhữ viằc khc phửc cĂc vĐn v hn ch sỹ

chm ca tr cứng.
Tữỡng tĂc vợi onboard cÊm bin: CÊm bin n y s giúp cung cĐp cĂc v tr
nút v chuyn ng ca cĂc node sò dửng cho liản kt truyn thổng hiằu quÊ
v mửc ch nh tuyn.

2.3

Cổng cử mổ phọng mng VANET - VANETsim
1

VANETsim l cổng cử ữổc Andreas Tomandl v cĂc cng sỹ giợi thiằu trong [7] theo
hnh 2.3. Ơy l cổng cử cho php mổ phọng li cĂc khĂi niằm trong mng VANET.
VANET l cổng cử trỹc quan cho php nhng nh nghiản cứu Ănh giĂ phữỡng phĂp
ca hồ v so sĂnh chĐt lữổng vợi nhng nghiản cứu khĂc mt cĂch hiu quÊ. KhĂc vợi
2

3

4

nhng cổng cử khĂc nhữ Transim , MATSim hay SimTRAVEL - nhng cổng
cử thiản v mổ phọng hằ thổng giao thổng dỹa trản hằ thng tĂc tò
1
2

/>
/> />4
/>3



2.3. Cổng cử mổ phọng mng VANET - VANETsim

thổng minh, VANETsim l cổng cử d d ng sòa i, thảm mợi kch bÊn hỡn v cho
php t ra nhiu kch bÊn. VANETsim cõ nhng tnh nông chnh nhữ sau:

Hnh 2.3: Cổng cử mổ phọng VANETsim
Cõ tch hổp b to kch bÊn, cho php ngữới nghiản cứu cõ th lp i lp li
nhng thỹc nghiằm ca mnh vợi nhng tham s u v o khĂc nhau Ănh
giĂ chnh xĂc hỡn m khổng cn phÊi thao tĂc nhiu.
VANETsim cung cĐp nhng cĂch thức mổ phọng gn ging nhĐt vợi th giợi
thỹc qua Đy t ữổc nhng kt quÊ gn ging thỹc t nhĐt. Cổng cử n y sò
dửng mổ hnh giao thổng micro-traffic mổ phọng li cĂc quyt nh lĂi xe
ca tng phữỡng tiằn.
5

VANETsim sò dửng bÊn ỗ t OpenStreetMap to bÊn ỗ, do vy viằc lĐy
bÊn ỗ chi tit cho tng th nh ph khổng phÊi l r o cÊn lợn cho nhng nh
nghiản cứu.
VANETsim cho php l m thỹc nghiằm vợi s lữổng lợn phữỡng tiằn giÊ lp
lản tợi 16000 phữỡng tiằn v mng lữợi giao thổng lợn.
Cổng cử n y hỉ trổ chy trản hằ thng ỡn lã nhữ desktop n nhng hằ
thng sò dửng nhiu b vi xò lỵ.
VANETsim hỉ trổ ỗ hồa, to sỹ thun tiằn cho nhng nh nghiản cứu cõ th
phƠn tch lỉi trong cĂc thỹc nghiằm ca mnh.
5




2.3. Cæng cö mæ phäng m⁄ng VANET - VANETsim


Ngo i nhœng ÷u i”m ð tr¶n, VANETsim l cæng cö ÷æc vi‚t tr¶n n•n Java v khæng
y¶u cƒu qu¡ nhi•u bº nhî khi ch⁄y. VANETsim công cung c§p t i li»u ph¡t tri”n ƒy ı
cho nhœng nh nghi¶n cøu muŁn sßa Œi s¥u hìn v o h» thŁng. Trong lu“n v«n n
y chóng tæi chı y‚u sß döng VANETsim nh÷ mºt cæng cö mæ phäng h» thŁng
giao thæng v ti‚n h nh nghi¶n cøu v• nhœng thu“t to¡n t…m ÷íng d÷îi nhœng i•u
ki»n gi£ ành tr¶n cæng cö n y.


Ch֓ng 3
C¡c gi£i thu“t t…m

֒ng

Phƒn n y chóng tæi s‡ tr…nh b y nhœng gi£i thu“t cì b£n trong t…m ki‚m ÷íng i
tr¶n ç thà v thu“t to¡n ant colony ÷æc chóng tæi ¡p döng v o h» thŁng Vannet.

3.1
3.1.1

Nhœng thu“t to¡n cì b£n
Gi£i thu“t Djkstra

Gi£i thu“t Dijsktra l gi£i thu“t t…m ÷íng i ng›n nh§t giœa c¡c i”m trong ç thà. Gi£i
thu“t n y ÷æc Edsger W. Dijkstra ÷a ra v o n«m 1956 v ÷æc cæng bŁ trong n«m
1959. Gi£i thu“t n y tçn t⁄i d÷îi nhi•u bi‚n th”, thu“t to¡n nguy¶n b£n cıa Dijkstra ÷a
ra ” t…m ÷íng i ng›n nh§t giœa hai i”m trong ç thà, nh÷ng mºt bi‚n th” phŒ bi‚n
thay Œi mºt ¿nh ìn nh÷ l ¿nh nguçn v t…m ki‚m t§t c£ c¡c ÷íng i ng›n nh§t tł ¿nh
nguçn tîi c¡c ¿nh kh¡c trong ç thà gåi l c¥y ÷íng i ng›n nh§t.
B i to¡n ÷æc °t ra nh÷ sau: Cho mºt ç thà câ h÷îng G=(V, E), mºt h m


trång sŁ w: E ! [0, 1 ) v mºt ¿nh nguçn s. Cƒn t‰nh to¡n ÷æc ÷íng i
ng›n nh§t tł ¿nh nguçn s ‚n mØi ¿nh cıa ç thà. V‰ dö: Chóng ta dòng ¿nh cıa ç
thà ” mæ t£ c¡c i”m giao c›t tr¶n ÷íng ð mºt th nh phŁ. Chóng ta cƒn di chuy”n tł
i”m s tîi i”m t trong mºt th nh phŁ. Thu“t to¡n Dijkstra s‡ gióp chóng ta t…m ÷æc
c¥y ÷íng i ng›n nh§t tł i”m s tîi måi i”m trong th nh phŁ v qua §y bi‚t ÷æc ÷íng i
ng›n nh§t tł s tîi t.
Thu“t to¡n Dijkstra

÷æc mæ t£ d÷îi ¥y theo [2].

16