Luận văn Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc

Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
TRƯỜNG ………………….  
KHOA……………………….  
-----[\ [\-----  
Báo cáo tt nghip  
Đề tài:  
SDNG TÁC TDI ĐNG PHÁT HIN DCH VTRONG  
CÁC MNG NGANG HÀNG KHÔNG CÓ CU TRÚC  
Nguyn ThKim Oanh – K50MTT  
Trang 1  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
LI CM ƠN  
Tôi xin gi li cm ơn ti các thy cô trong khoa Công nghThông tin trường  
Đại hc Công ngh, Đại hc Quc Gia Hà Ni, đặc bit là các thy cô trong bmôn  
Mng và truyn thông máy tính. Các thy cô đã dy bo và giúp đỡ tôi rt nhiu  
trong quá trình hc tp, giúp tôi trưởng thành hơn trong suy nghĩ và nhn thc.  
Đặc bit xin chân thành cm ơn thy Nguyn Đại Th, người đã trc tiếp  
hướng dn tôi hoàn thành khóa lun này. Snhit tình hướng dn ca thy là ngun  
động lc ln lao cho tôi.  
Tôi cũng xin chân thành cm ơn nhng người bn thân thiết đã chia snhng  
kinh nghim và kiến thc bích cho tôi, xin cm ơn nhng người thân trong gia  
đình đã động viên và to điu kin cho tôi trong quá trình hoàn thành khóa lun.  
Hà Ni, tháng 5 năm 2009  
Nguyn ThKim Oanh – K50MTT  
Trang 2  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
TÓM TT NI DUNG  
Khóa lun này là kết qunghiên cu ca tác givvn đề tìm kiếm trong  
mng ngang hàng.Trong khuôn khca khóa lun, tác giả đã trình bày tng quan  
nht vmng ngang hàng và vn đề tìm kiếm trong mng ngang hàng không có cu  
trúc. Phương pháp tìm kiếm đề xut trong khóa lun được tác ginghiên cu da  
trên nhiu ngun tư liu trong đó tư liu chính là bài báo [4]  
Khóa lun cũng gii thiu vmt công nghệ đang còn rt nhiu tim năng đó  
là công nghtác tdi động. Công nghhu ích này đã gii quyết bài toán tìm kiếm  
hóc búa như thế nào và da trên nhng cơ slý thuyết nào, đó là vn đề mà khóa  
lun tp trung phân tích. Để làm rõ hơn nhng phân tích và nghiên cu, trong khóa  
lun tác giả đã trình bày phn thí nghim mô phng vi dán MATES ca Evan  
Sultanik. Da trên kết quthc nghim thu được, so sánh vi các công thc lý  
thuyết tác giả đã đánh giá và đưa ra kết lun cho nhng nghiên cu ca mình.  
Nguyn ThKim Oanh – K50MTT  
Trang 3  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
MC LC  
LI CM ƠN .................................................................................................................................... 2  
TÓM TT NI DUNG ..................................................................................................................... 3  
BNG CÁC THUT NGVIT TT............................................................................................ 6  
DANH MC CÁC HÌNH VBNG BIU..................................................................................... 7  
MỞ ĐẦU............................................................................................................................................ 8  
Chương 1. TNG QUAN ................................................................................................................ 10  
1.1. Tng quan mng ngang hàng ................................................................................................ 10  
1.1.1. Định nghĩa...................................................................................................................... 10  
1.1.2. Phân loi......................................................................................................................... 11  
1.1.3. Ưu đim và nhược đim ca mng ngang hàng............................................................. 11  
1.1.4. Các ng dng ca mng ngang hàng.............................................................................. 12  
1.2. Vn đề tìm kiếm trong mng ngang hàng không cu trúc..................................................... 13  
1.2.1. Mt skĩ thut tìm kiếm phbiến ................................................................................. 13  
1.2.2. Xu hướng phát trin ....................................................................................................... 15  
Chương 2. CÔNG NGHTÁC TDI ĐỘNG ............................................................................... 16  
2.1. Tng quan vtác tdi động.................................................................................................. 16  
2.1.1. Lch shình thành.......................................................................................................... 16  
2.1.2. Định nghĩa...................................................................................................................... 16  
2.1.3. Các đặc tính chính.......................................................................................................... 17  
2.2. Nguyên lý hot động ............................................................................................................. 17  
2.3. ng dng............................................................................................................................... 18  
2.3.1. Nhng li đim ca tác tdi động................................................................................. 18  
2.3.2. Các ng dng chính........................................................................................................ 19  
Chương 3. MÔ HÌNH SDNG TÁC TDI ĐỘNG PHÁT HIN DCH VTRONG CÁC  
MNG NGANG HÀNG KHÔNG CU TRÚC ............................................................................. 21  
3.1. Cơ slý thuyết ...................................................................................................................... 21  
3.1.1. Chui Markov và đường đi ngu nhiên.......................................................................... 22  
3.1.2. Thut toán PageRank ..................................................................................................... 24  
3.2. Các tham số đánh giá hiu năng............................................................................................ 26  
Nguyn ThKim Oanh – K50MTT  
Trang 4  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
3.2.1. Xác sut tác tti thăm mt host cho trước................................................................... 26  
3.2.2. Xác sut tác tphát hin dch v................................................................................... 26  
3.2.3. Hàm dự đoán tác tnhìn thy dch vvà thăm host...................................................... 27  
3.2.4. Thi gian kì vng tác tdi chuyn ngu nhiên trvngun......................................... 28  
3.3. Mô hình trin khai................................................................................................................. 29  
3.4. Đánh giá mô hình.................................................................................................................. 30  
Chương 4. CÁC THÍ NGHIM MÔ PHNG VÀ ĐÁNH GIÁ...................................................... 31  
4.1. Chương trình mô phng MATES.......................................................................................... 31  
4.1.1. Kiến trúc chương trình ................................................................................................... 31  
4.1.2. Trin khai chương trình.................................................................................................. 34  
4.1.3. Ưu đim, nhược đim ca chương trình......................................................................... 36  
4.2. Thí nghim đo tn sut tác tti thăm host .......................................................................... 37  
4.3. Thí nghim 2 ......................................................................................................................... 39  
4.4. Thí nghim 3 ......................................................................................................................... 43  
Chương 5. KT LUN VÀ HƯỚNG PHÁT TRIN..................................................................... 45  
LI KT .......................................................................................................................................... 47  
TÀI LIU THAM KHO................................................................................................................ 48  
Nguyn ThKim Oanh – K50MTT  
Trang 5  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
BNG CÁC THUT NGVIT TT  
P2P  
Peer-to-Peer  
WWW  
URL  
World Wide Web  
Uniform Resource Locator  
Content Addressable Networks  
Distributed Hash Table  
Time-to-Live  
CAN  
DHT  
TTL  
MATES  
MANET  
AI  
Macro Agent Transport Event-based Simulator  
Mobile Ad-hoc Network  
Artificial Intelligence  
Nguyn ThKim Oanh – K50MTT  
Trang 6  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
DANH MC CÁC HÌNH VBNG BIU  
Hình 1-Mô hình mng ngang hàng .......................................................................... 10  
Hình 2-Mt agent di chuyn ngu nhiên trong mng ngang hàng .......................... 22  
Hình 3-Mt vòng mô phng...................................................................................... 31  
Hình 4-Mi tương quan gia xp xv và tn sut tác tti thăm host trong 100000  
ln lp....................................................................................................................... 39  
Hình 5-Hàm dự đoán F(N) và xác sut ti thăm host ca tác tcó thông tin vdch  
v.............................................................................................................................. 42  
Hình 6-Thi gian kì vng tác tvngun................................................................ 44  
Nguyn ThKim Oanh – K50MTT  
Trang 7  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
MỞ ĐẦU  
Ngày này cư dân mng đã không còn llm vi thut ngmng ngang hàng  
(P2P). Mng ngang hàng là bước phát trin tmô hình mng client/server truyn  
thng ti mt mô hình mng trong đó mi phn tca mng hot động vi vai trò  
ca cclient và server. Mng ngang hàng đã tưu thế và ích li ca mình trong  
vn đề lưu trvà băng thông. Công nghmng ngang hàng đã trnên gn gũi và  
phdng vi người dùng. Nó gim nhng chi phí đắt đỏ bi nhng người dùng có  
thsdng chung và chia scho nhau nhng phn cng, nhng tài nguyên mng.  
Mt shthng mng ngang hàng đã trnên quen thuc vi người dùng Internet  
như Napster, SETI@Home, ICQ. P2P hin đang được ng dng trong rt nhiu lĩnh  
vc, bao gm cthương mi đin t.  
Thu hút hàng nghìn kết ni tngười dùng mà không phi lo lng ti vn đề  
điu khin tp trung và mrng, P2P vn phi đối mt vi vn đề định vtài  
nguyên do sphân tán ca mng đặc bit khi cu trúc mng không cố định mà  
thường xuyên thay đổi. Các giao thc phát hin tài nguyên phbiến nht trong  
mng ngang hàng vn là truy vn phát tràn và bng băm phân tán. Tuy nhiên  
phương thc phát tràn đặt ra bài toán tc nghn trong mng trong khi bng băm  
phân tán li yêu cu tăng chi phí cho nhng cp nht phân tán. Giao thc tìm kiếm  
truyn thng trong mng ngang hàng có thể được ci tiến nếu mt nút bt đầu truy  
vn có mt chút thông tin vnơi tìm kiếm tài nguyên mà không phi duy trì vic  
băm phân tán. Mt sthông tin như topo mng, băng thông do các nút khác htrợ  
có thể được sdng để cung cp hướng tìm kiếm cho nhng truy vn sau này.  
Sphát trin ca khoa hc máy tính, trí tunhân to và công nghphn mm  
cho ra đời mt đối tượng khá hu dng gii quyết vn đề trên đó là tác t. Mt tác  
tlà mt đon mã có thtiếp tc thi hành nhng hành động đã được lp trình mà  
không cn phi chu sgiám sát ca bqun lý trung tâm. Các tác tthông minh  
cũng có khnăng hc hi thông tin tmôi trường để ci tiến hành động ca chúng  
và di chuyn tmt nút này ti nút khác để thc thi nhng tác vphân tán.  
Nguyn ThKim Oanh – K50MTT  
Trang 8  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Tác tphn mm (software agent) là mt hướng lp trình mi phù hp để thc  
thi cơ chế tìm kiếm thông tin trong mng ngang hàng không có cu trúc. Trong bi  
cnh đó đề tài “Sdng tác tdi động phát hin dch vtrong các mng ngang  
hàng không có cu trúc” đi sâu vào nghiên cu gii pháp ng dng tác tdi động  
phát hin dch vtrong mng ngang hàng không có cu trúc da trên thut toán  
đường đi ngu nhiên và nhng cơ slý thuyết toán hc. Ý tưởng sdng tác tdi  
động phát hin dch vtrong các mng ngang hàng không có cu trúc không phi là  
mi. Vn đề này đã được các nhà khoa hc nghiên cu và có nhng đánh giá nht  
định. Trong khuôn khca khóa lun này, tác gichnghiên cu và xem xét các  
khía cnh liên quan ti nguyên lý, cơ chế, nhng lý thuyết vthut toán ca gii  
pháp và đánh giá nhng lý thuyết đã đưa ra bng nhng thí nghim mô phng cụ  
th.  
Ni dung ca khóa lun sbao gm nhng phn sau:  
Chương 1: Tìm hiu chung vmng ngang hàng, nhng phương pháp tìm  
kiếm truyn thng trong mng ngang hàng.  
Chương 2: Gii thiu công nghtác tdi động, tkhái nim, phân loi, các  
tính cht, nguyên lý hot động, các li đim cho ti nhng ng dng ca công  
nghnày trong thc tin.  
Chương 3: Nghiên cu gii pháp sdng tác tdi động tìm kiếm thông tin  
trong các mng ngang hàng không có cu trúc, cơ slý thuyết, các tham số  
liên quan và nhng đánh giá sơ bvgii pháp.  
Chương 4: Gii thiu chương trình mô phng và cài đặt nhng thí nghim cụ  
thể để đánh giá gii pháp  
Chương 5: Kết lun và hướng phát trin  
Nguyn ThKim Oanh – K50MTT  
Trang 9  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Chương 1. TNG QUAN  
1.1. Tng quan mng ngang hàng  
1.1.1. Định nghĩa  
Mng ngang hàng (peer to peer) là mt mng máy tính trong đó hot động  
ca mng chyếu da vào khnăng tính toán và băng thông ca các máy tham gia  
chkhông tp chung vào mt snhcác máy chtp chung như các mng thông  
thường. Hay nói mt cách đơn gin hơn đó là mng ngang hàng là mt mng mà  
được to ra bi hai hay nhiu máy tính được kết ni vi nhau và chia stài nguyên  
mà không phi thông qua mt máy chrành riêng. Dưới đây là mt ví dvmng  
ngang hàng.  
Hình 1-Mô hình mng ngang hàng  
Nguyn ThKim Oanh – K50MTT  
Trang 10  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
1.1.2. Phân loi  
Có thphân loi các mng đồng đẳng hin nay theo tiêu chí vmc độ tp  
trung ca chúng như sau:  
- Mng ngang hàng “thun túy”:  
Các máy trm có vai trò va là máy chva là máy khách  
Không có máy chtrung tâm qun lý mng  
Không có bộ định tuyến trung tâm, các máy trm có khnăng  
tự định tuyến  
- Mng ngang hàng “lai”:  
Có mt máy chtrung tâm dùng để lưu trthông tin ca các  
máy trm và trli các truy vn thông tin này.  
Các máy trm có vai trò lưu trthông tin, tài nguyên được  
chia s, cung cp các thông tin vchia stài nguyên ca nó cho  
máy ch.  
Sdng các trm định tuyến để xác định địa chIP ca các  
máy trm.  
Các mng ngang hàng "thun túy" có thklà Gnutella và Freenet. Các  
mng ngang hàng lai có nhiu loi: mng P2P tp trung như Napste, mng P2P  
phân tán như KazaA, mng P2P có cu trúc như CAN, mng P2P không cu trúc  
như Gnutella.  
1.1.3. Ưu đim và nhược đim ca mng ngang hàng  
1.1.3.1. Ưu đim  
Mng ngang hàng thhin rõ ưu thế so vi mng theo mô hình  
Client/Server.Nó tn dng được tim năng t"cnh" ca Internet còn ít được khai  
thác. Ví dchcn t10 triu máy tính 100 MHz ni vào mng cùng mt lúc, mi  
máy có dung lượng lưu tr100 MB, băng thông 1000 bps, 10% khnăng xlý  
chưa được sdng đến.  
Nó không da trên server tp trung và thường hot động ngoài hthng tên  
min mà sdng kiến trúc phng, tính kết ni cao để các máy ttìm ra nhau, xác  
định nơi cung cp dch vvà chủ động yêu cu dch vtheo ý mun.  
Nguyn ThKim Oanh – K50MTT  
Trang 11  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Kiến trúc mng ngang hàng cho phép phân tán trách nhim cung cp dch vụ  
đến tt ccác đim nút trên mng. Chính vì thế đã loi bvn đề ngng trdch vụ  
do nơi duy nht cung cp bsc. Đó chính là gii pháp khbiến hơn trong vic  
cung cp dch v.  
Mng ngang hàng tn dng băng thông trên toàn bmng bi vì các máy  
tính giao tiếp qua nhiu đường truyn khác nhau nên đã gim đáng khin tượng  
nghn tc mng.  
Mng ngang hàng phc vtài nguyên vi độ sn sàng cao, chi phí thp đồng  
thi nâng cao hiu sut khai thác trong khi đó thì mng theo mô hình Client-Server  
thì phi cn thêm băng thông, thiết b, phương tin.  
1.1.3.2. Nhược đim  
Do tính các máy tính trong mng có vai trò ngang nhau nên yêu cu dch vụ  
cũng được đáp ng mt cách tùy biến. Ví d, các client yêu cu cùng mt dch vụ  
có thni ti các máy khác nhau, qua các đường truyn khác nhau, vi kết quả  
nhn được khác nhau.  
Mt nhược đim na ca mng ngang hàng là các yêu cu tcác máy có thể  
không nhn được kết qungay và có thkhông được đáp ng do các tài nguyên có  
thbiến mt do máy cung cp ngt kết ni trong khi đó vi Client/Server thì hu  
như tài nguyên liên tc hin din.  
1.1.4. Các ng dng ca mng ngang hàng  
ng dng ln nht có thkể đến ca mng ngang hàng là ng dng chia sẻ  
file. Có hai công nghmng ngang hàng trong lĩnh vc chia sfile đin hình là  
Napster và Gnutenlla. Trong khi Napster cho phép người dùng trao đổi các file MP3  
vi nhau và có thêm chc năng gi tin nhn tc thi thì Gnutenlla có thcho phép  
chia smi kiu file. Napster sdng kiến trúc mng ngang hàng lai ghép trong đó  
server lưu danh sách các file MP3 mi người dùng chia s, cho phép người dùng  
tìm kiếm mt file cthvà các file được trao đổi trc tiếp gia các đim nút.  
Gnutella thì không sdng server.  
Ngoài ng dng chia sfile, mng ngang hàng còn có ng dng tính toán  
phân tán. SETI@Home và Distributed.net là hai ng dng đin hình ca tính toán  
phân tán.  
Nguyn ThKim Oanh – K50MTT  
Trang 12  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
1.2. Vn đề tìm kiếm trong mng ngang hàng không cu trúc  
1.2.1. Mt skĩ thut tìm kiếm phbiến  
1.2.1.1. Phát tràn  
Phát tràn là chiến lược tìm kiếm đơn gin nht và thông dng nht trong mng  
ngang hàng. Bi thế mà mng Gnutella đã sdng phương pháp tìm kiếm này. Vic  
tìm kiếm được tiến hành như sau: đầu tin nút cn tìm gi đi mt thông đip do  
thám ti tt ccác hàng xóm ca nó. Các hàng xóm này schuyn nhng bn sao  
ca thông đip kia ti nhng nút hàng xóm kế tiếp trnút hàng xóm mà đã chuyn  
thông đip ti nó. Cnhư thế, công cuc tìm kiếm được tiếp din.  
Trong quá trình thc thi phương pháp này cho thy mt shn chế và nhược  
đim. Hn chế ln nht đó là vn đề truyn ti. Nhng thành phn tham dvào  
mng như nhng máy tính cá nhân ti gia hay cơ quan là nhng thành phn chu  
nh hưởng nhiu nht. Nếu mt máy tính phi xlý rt nhiu gián đon mng khi  
tham gia vào mng ngang hàng, người dùng chc schng do dmà chn gii pháp  
quay trvvi công vic thc ti hơn là cgng kết ni vào mng chỉ để gii trí.  
Đó là mt lý do làm gim khnăng và shu dng ca mng ngang hàng. Tht  
không may là thut toán tìm kiếm phát tràn li làm gia tăng vn đề này.  
Gnutella đã sdng TTL(Time-To-Live) để điu khin schng mà truy vn  
có thlan truyn. Tuy nhiên vic chn sTTL làm sao cho thích hp li là cvn  
đề. Nếu TTL quá cao, các nút không cn thiết strthành gánh nng cho mng còn  
nếu TTL quá thp, nút có thkhông tìm được đối tượng nó cn.  
Mt vn đề na vi phương thc phát tràn này là có rt nhiu bn sao các  
thông đip được phát tán ra. Điu này đồng nghĩa vi vic tăng chi phí trên mng.  
Nhng bn sao này gia tăng các quá trình xlý ngt ti mi nút nhn nhưng không  
hlàm tăng cơ hi tìm thy đối tượng cn.  
1.2.1.2. Mrng vòng  
Khi phát tràn lrõ nhng hn chế ca mình thì nhng nhà phát trin mng đã  
cgng tìm ra nhng phương pháp thích hp hơn, ti ưu hơn. Đầu tiên hnhm  
vào vn đề chn TTL. Vi phương pháp vòng mrng thì mt nút bt đầu phát tràn  
Nguyn ThKim Oanh – K50MTT  
Trang 13  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
vi sTTL nhđợi xem vic tìm kiếm có thành công hay không. Nếu câu trli  
là có thì nút sdng vic tìm kiếm. Ngược li, nút stăng sTTL và bt đầu lượt  
phát tràn khác. Tiến trình này lp li cho ti khi đối tượng được tìm thy.  
Kết quthc nghim chra rng, mc dù liên tc lp li quá trình phát tràn đó  
nhưng so vi phương pháp phát tràn truyn thng mà sTTL là cố định thì phương  
pháp mrng vòng vn gim đáng kti mng. Tuy nhiên có ththy phương pháp  
này slàm tăng độ trtrong vic tìm ra đối tượng do nó phthuc khá nhiu vào  
thi gian ch.  
Mc dù phương pháp mrng vòng đã gii quyết được vn đề chn sTTL,  
nhưng nó chưa gii quyết được vn đề bn sao thông đip. Để gim slượng bn  
sao thông đip ta thmt hướng tiếp cn khác, đó là đường đi ngu nhiên.  
1.2.1.3. Di chuyn ngu nhiên  
Di chuyn ngu nhiên được đánh giá là mt kĩ thut tt. Nó gi mt thông  
đip truy vn ti mt hàng xóm được chn ngu nhiên ti mi bước cho ti khi đối  
tượng được tìm ra. Ta gi nhng thông đip này là “nhng người đi đường”.  
Khi sdng phương pháp di chuyn ngu nhiên chun (chvi mt người đi  
đường), ti mng sẽ được gim xung mt cách đáng kso vi phương pháp mở  
rng vòng. Tt nhiên nó skéo theo độ trtrong vic tìm ra đối tượng ln hơn. Để  
gim độ trnày ta sdng nhiu “người đi đường” hơn. Thay vì gi đi mt thông  
đip truy vn, nút yêu cu sgi đi k thông đip truy vn và mi thông đip này li  
tnó di chuyn mt các ngu nhiên. Dtính là vi k “người đi đường” sau T bước  
sẽ đi qua mt snút tương tnhư snút mà mt người đi đường đi được sau kT  
bước. Và thc nghim quả đã chng minh điu này. Như vy dùng k “người đi  
đường” hiu qucông vic stăng lên gp k ln và độ trtìm kiếm cũng gim đi rt  
nhiu.  
Để gii hn đường đi trong trường hp có nhiu “người đi đường” các nhà  
nghiên cu đã thnghim hai phương pháp: dùng TTL và kim tra. Phương pháp  
dùng sTTL tương tnhư phát tràn, mi đường đi ngu nhiên sdng sau mt số  
chng xác định. Phương pháp kim tra thì khác, mt “người đi đường” skim tra  
mt cách định kì yêu cu đầu tiên trước khi tiếp tc di chuyn mt cách ngu nhiên  
ti nút khác. Thc ra phương pháp kim tra vn sdng TTL, nhưng sTTL rt  
ln và thường dùng để tránh lp.  
Nguyn ThKim Oanh – K50MTT  
Trang 14  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
phn sau ca khóa lun ta cũng snghiên cu phương pháp di chuyn ngu  
nhiên nhưng có sdng cơ chế khác.  
1.2.2. Xu hướng phát trin  
Theo nhng phân tích trên ta có ththy phương pháp di chuyn ngu nhiên  
vi k người đi đường có nhiu khnăng mrng hơn phương pháp phát tràn. Chìa  
khóa cho tìm kiếm mrng trong mng không có cu trúc là bao quát được các nút  
đúng mt cách nhanh nht có thvà vi chi phí thp nht có th. Trong mng không  
có cu trúc, cách duy nht để tìm các đối tượng là ti thăm tt ccác nút, như thế có  
thnói chc chn là mt nút sđối tượng cn tìm. Tuy nhiên, để đến được nút  
yêu cu thì mt nút cn chú ý ti nhng vn đề sau:  
Ti gin nhng thông đip lp. Mi truy vn nên ti thăm mt nút đúng mt  
ln. Càng nhiu ln ti thăm càng tn nhiu chi phí và tăng ti mng.  
Snút ti thăm trong quá trình tìm kiếm nên nh. Trong mi bước di chuyn  
tiếp sau ca quá trình tìm kiếm nên hn chế snút đã ti thăm. Điu này có llà  
khác nhau cơ bn gia phương pháp phát tràn và phương pháp đường đi ngu nhiên  
có nhiu người đi đường. Trong phát tràn thì snút ti thăm tăng theo hàm mũ còn  
trong đường đi ngu nhiên mi bước lp sau thì snút ti thăm tăng theo mt  
hng s. Khi mi ln tìm kiếm chyêu cu chính xác mt snút để ti thăm thì các  
nút phụ được ti thăm trong phương pháp phát tràn chlàm tăng ti trên mi nút.  
Nguyn ThKim Oanh – K50MTT  
Trang 15  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Chương 2. CÔNG NGHTÁC TDI ĐỘNG  
2.1. Tng quan vtác tdi động  
2.1.1. Lch shình thành  
Vi sphát trin đa dng và phong phú ca công nghthông tin, tng ngày  
tng giờ đang ra đời hàng lot nhng sn phm mi, tin ích hơn, thông minh hơn,  
hu dng hơn và nhgn hơn, đặc bit là nhng sn phm có khnăng hot động  
mt mình và kết hp vi nhng chương trình khác. Là mt sgp nhau gia trí tuệ  
nhân to và công nghphn mm, các software agent là mt chương trình như thế.  
Tác tdi động là mt loi software agent.  
Khái nim “software agent” được Mark Sidell và Chuck Knuff đưa ra năm  
1994. Năm 1995 phiên bn đầu tiên ca software agent xut hin.Ti nhng năm  
1975 thì kĩ thut lp trình phbiến là lp trình hướng cu trúc, nhng năm 1982 kĩ  
thut lp trình phbiến là lp tình hướng đối tượng và đến khi agent ra đời thì nó đã  
mra mt phương pháp lp trình mi.  
2.1.2. Định nghĩa  
Để hiu khái nim vtác tdi động, ta đi tkhái nim tác t(agent). Khái  
nim agent theo Nawana đề xut năm 1996 là mt thành phn phn mm hoc phn  
cng có khnăng hot động chính xác để thay mt chnhân hoàn thành nhim v.  
Nó là skết hp ca nhiu kĩ thut tin hc hin đại như: kĩ thut cơ sdliu và cơ  
stri thc, máy hc, AI và khoa hc nhn dng, phc hi thông tin, các hthng  
phân tán, mobile code.  
Mobile agent (tác tdi động) là tghép ca mobile (tính di động) và agent  
(tác t). Xét trong bi cnh mng internet mt mobile agent là mt chương trình có  
khnăng di chuyn mt cách ttrtnút mng này sang nút mng khác và thc  
hin các xlý thay thế con người hoàn thành nhim v.  
Nguyn ThKim Oanh – K50MTT  
Trang 16  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
2.1.3. Các đặc tính chính  
- Tính ttr: là khnăng tkim soát bn thân ca agent sau khi được giao  
vic mà không cn scan thip nào ca người dùng hoc agent khác. Khnăng này  
ca agent chyếu được quyết định bi tri thc trang bcho agent. Để đánh giá tính  
ttrca agent người ta thường da vào hai đặc tính là hướng đích (goal-oriented)  
và tính chủ động (pro-activeness).  
- Tính di động: là khnăng chuyn tmôi trường thi hành này sang môi  
trường thi hành khác. Có thphân tính di động thành hai loi: di động mnh và di  
động yếu. Di động mnh là khnăng mà hthng có thdi chuyn cmã chương  
trình và trng thái thi hành ca agent ti mt môi trường khác còn di động yếu là  
khnăng mà hthng chcó thdi chuyn mã chương trình gia các môi trường thi  
hành vi nhau, mã ngun có thmang kèm mt sdliu khi to nhưng trng thái  
thi hành thì không thdi chuyn.  
- Khnăng cng tác: là khnăng liên lc, phi hp hot động ca các agent  
vi các agent khác cùng môi trường hay vi các loi đối tượng khác trong nhng  
môi trường khác.  
- Tính thích nghi: là khnăng agent có thhot động trên nhng môi trường lạ  
và cm nhn được nhng thay đổi  
2.2. Nguyên lý hot động  
Vthc cht agent chlà mt đon mã, nó cũng có vòng đời và tùy vào loi và  
mc đích sdng mà agent có chi tiết vòng đời khác nhau. Tuy nhiên vòng đời ca  
agent vn bao gm nhng đim chính sau:  
Khi agent được to ra trên mt host cũng là lúc vòng đời ca agent bt đầu.  
Trong khong thi gian này thì các trng thái ban đầu ca agent cũng có thể được  
khi to theo.  
Khi đã sn sàng hoc được lnh di trú ti mt host khác nm trong đường đi  
ca agent, agent slưu li trng thái hin hành ca mình và tiến hành quá trình di  
trú. Nếu quá trình di trú tht bi, agent stngng hot động. Sau mt khong thi  
gian định trước hay được kích hot nó stiến hành li quá trình di trú ti host khác.  
Khi đã di trú ti host mi thành công, agent sphc hi trng thái, khi đó nó  
bt đầu thc thi nhim vca mình.  
Nguyn ThKim Oanh – K50MTT  
Trang 17  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Sau khi agent hoàn thành nhim v, nó có thbhy hoc chuyn sang trng  
thái ngủ đông cho đến khi có yêu cu tbộ đếm trong chính bn thân agent. Khi đó  
agent slưu li trng thái ca nó và di trú ti mt host khác.  
Vòng đời agent lp li theo quy trình như trên cho đến khi nó hoàn thành  
nhim vhoc hết thi gian hot động thì agent sbhy.  
2.3. ng dng  
2.3.1. Nhng li đim ca tác tdi động  
Tác tdi động có rt nhiu li đim. Dưới đây là mt sli đim chính.  
- Gim ti mng  
Vi phương châm là “mang xlý ti nơi cha dliu hơn là mang dliu đến  
chxlý” kthut Mobile Agent cho phép người dùng đóng gói cuc trao đổi, gi  
đến máy đích và thc hin xlý dliu, trao đổi cc bti đó. Có ththy  
nhng dòng dliu thô trên mng sẽ được gim xung đáng k, điu này đồng  
nghĩa vi ti mng cũng được gim xung.  
- Đóng gói các giao thc  
Khi dliu được trao đổi trong hthng phân tán, vic truyn và nhn dliu  
phi được mã hóa bi các giao thc cn thiết. Các giao thc này được shu bi  
mi máy trong hthng. Tuy nhiên, mt khi các giao thc phi tiến hóa để phù hp  
vi nhng yêu cu mi vbo mt hoc tính hiu qu, chúng bt đầu trnên cng  
knh, nng nvà trthành vn đề nan gii. Vi gii pháp Mobile Agent, các agent  
có thmang trên mình các giao thc thích hp và di chuyên ti các máy xa để  
thiết lp các kênh truyn nhn thông tin tương ng.  
- Thi hành không đồng bvà ttrị  
Hãy tưởng tượng khi agent được nhúng các tác vcn thc hin và được gi  
lên mng. Lúc này agent trnên độc lp thi hành không đồng bvà có khnăng tự  
tr. Các thiết bdi động sau đó có thkết ni trli để đón agent v.  
- Khc phc strmng  
Vic điu khin các hthng có quy mô ln thông qua mng sphi chp  
nhn mt gii hn trnào đó. Tuy nhiên điu này là không được phép nếu đó là  
nhng hthng thi gian thc như điu khin robot, quy trình sn xut…Vi các  
Nguyn ThKim Oanh – K50MTT  
Trang 18  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
agent có thể được gi đi tmt trung tâm điu khin và hành động cc b, ttr,  
trc tiếp thi hành các chdn ca người điu khin thì vn đề này xem ra đã có thể  
được gii quyết.  
2.3.2. Các ng dng chính  
- Thu thp dliu phân tán  
Trong trường hp có nhu cu truy vn phc tp, chuyên bit và liên quan đến  
nhiu ngun dliu phân tán, không đồng nht, vic ccác mobile agent di chuyn  
đến các ngun tin để khai thác ti chvà quay vvi nhng thông tin cn thiết sẽ  
cho phép gim ti mng và gii quyết tt hơn bài toán tương thích. Đã có nhng dự  
án thuc loi này như Distributed Query Processing via Mobile Agents (University  
of Maryland), DB Access (University of Cyprus).  
- Thương mi đin tử  
Các ng dng thương mi đin tlà môi trường hp dn để phát trin công  
nghmobile agents. Mt giao dch thương mi đin tcó thbao gm sthương  
lượng vi các thc thể ở xa và có thể đòi hi truy cp ngun thông tin liên tc thay  
đổi. Thc tế đó ny sinh nhu cu thay đổi hành vi ca các thc thể để đạt được mt  
nghi thc chung trong vic thương lượng. Hơn na vic di chuyn các thành phn  
ca ng dng tiến gn đến ngun thông tin thích hp cho giao dch cũng được quan  
tâm.  
- Qun trhthng mng  
Đối vi nhng hthng mng ln, vic chun đoán li, duy trì sự ổn định ca  
hthng là các công vic rt khó khăn. Vic ng dng mobile agent vào vic qun  
trmng sgiúp cho các công vic chun đoán li và duy trì txa sự ổn định ca hệ  
thng được ddàng hơn.  
- Giám sát và phân tán thông tin  
Các mobile agents là mt minh ha cho mô hình Internet push. Các agent có  
thphbiến tin tc và cp nht phn mm tự động cho các nhà sn xut. Các agent  
mang các thành phn phn mm cũng như các thtc cn thiết đến các máy cá nhân  
ca khách hàng và tcp nht phn mm trên máy đó. Mô hình này giúp cho nhà  
sn xut chủ động hơn trong vic phc vkhách hàng để đảm bo cht lượng dch  
vca mình. Mt khác, các ng dng loi này cũng tra hiu quả đối vi các mng  
Nguyn ThKim Oanh – K50MTT  
Trang 19  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
cc bhay các chương trình qun lý quy trình hot động, sn xut…để giúp người  
qun trgiám sát các hthng con. Có mt sdán ng dng loi này như Banking  
Dartflow [CAI-96], Autopilot [FOS-99].  
- Xlý song song  
Vì các mobile agent có thto ra nhiu bn sao ca nó trên mng, tn dng  
đặc tính này mà mobile agent được ng dng để qun trcác tác vsong song. Mt  
ng dng đòi hi quá nhiu tài nguyên bxlý có thể được phn bcho các mobile  
agent mang đi thc hin trên nhiu máy tính khác nhau để tn dng các tài nguyên  
rnh ri và cân bng ti. Mt ví dca loi ng dng này là Hmobile agents  
không đồng nht [HER-99]  
Nguyn ThKim Oanh – K50MTT  
Trang 20  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Chương 3. MÔ HÌNH SDNG TÁC TDI ĐỘNG PHÁT  
HIN DCH VTRONG CÁC MNG NGANG HÀNG  
KHÔNG CU TRÚC  
Struyn thông tmt nút ti các hàng xóm ca nó trong mng ad-hoc và  
mng ngang hàng vn đã bhn chế, thế nên struyn thông trên nhiu chng trong  
mng càng trnên khó khăn, đin hình là vn đề định tuyến. Nhng nghiên cu gn  
đây tp trung vào vn đề sdng tác tdi động để định tuyến trong mng ad-hoc.  
Hu hết các phương pháp da vào vic sdng tn sut ca tác tti thăm mi nút  
để dự đoán topo mng. Nhng nghiên cu sâu hơn thì tp trung vào vn đề tìm  
kiếm dch vphân tán trong mng. Dch vphân tán có thbao gm cnhng tác  
ttĩnh và tác tdi động.  
Chyếu do sphát trin ca công nghchia sfile ngang hàng, nhng nghiên  
cu quan trng đã được tiến hành trong lĩnh vc mng động. Kiến trúc tìm kiếm  
dch vụ đã tng tn ti trong nhng mng như vy, tuy nhiên khi mun sdng li  
cn phi đăng kí. Trong mng CAN (Content-Addressable Network) kĩ thut tìm  
kiếm cũng đã được áp dng trong vn đề định v. Hướng tiếp tìm kiếm cơ bn  
thường giả định rng các tác tcó thtdi trú tmt máy này ti mt máy khác  
trong mng. Các phương pháp da trên tác tử để tìm kiếm dch vụ đã được trin  
khai. Thêm vào đó CANs và DHTs gisrng chmc và các phn tdliu là cố  
định, không có cái nào trong nhng hướng tiếp cn này đề cp trc tiếp ti vn đề  
vxác định vtrí các dch vdi động.  
Trong chương 2 ta cũng đã biết được rt nhiu ưu đim ca tác tdi động.  
Gii pháp da trên tác tdi động slà mt la chn hp lý cho bài toán tìm kiếm  
đang còn gp nhiu khó khăn.  
3.1. Cơ slý thuyết  
Phát hin dch vcó thể được hiu chính xác nhmô hình trin khai mt tp  
các tác tA, ngu nhiên trên đường đi ca mình chn mt tp các hosts H trong  
mng ngang hàng. Mt các đầy hình nh có thtưởng tượng rng các agent hot  
Nguyn ThKim Oanh – K50MTT  
Trang 21  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
động như nhng chú ong, công vic ca chúng là “thphn” cho mng vi nhng  
thông tin vvtrí ca dch v.  
Hình 2-Mt agent di chuyn ngu nhiên trong mng ngang hàng  
Hướng tiếp cn này có ba li đim quan trng đó là không tn băng thông  
mng, các dch vkhông cn phi được đăng kí và tính cht ca đường đi ngu  
nhiên có liên quan nhiu ti nhng mô hình toán hc, đó là nhng cơ skhoa hc  
chc chn. Dưới đây ta sáp dng nhng mô hình toán hc để mô tnhng trng  
thái ca các tác tnày. Ta sdng các tính cht ca chui Markov để mô hình hóa  
xác sut mt tác tsti thăm mt host xác định, phân bnhphân để mô hình hóa  
xác sut mt tác tnhìn thy mt dch vvà mt phân bnhphân khác để tính giá  
trkì vng stác tsti thăm mt host trong mt khong thi gian.  
3.1.1. Chui Markov và di chuyn ngu nhiên  
3.1.1.1. Chui Markov  
Nhc li mt chút vlý thuyết gii tích, Chui Markov là mt quá trình thng  
kê ngu nhiên thi gian ri rc. Đó là mt tp các trng thái S là các phn tca ma  
trn xác sut chuyn P. S có thlà hu hn hoc vô hn đếm được. Ma trn xác sut  
chuyn P có mt hàng và mt ct cho mi trng thái trong tp S. Mi phn tca  
ma trn này Pij là xác sut chuyn sang trng thái j ttrng thái hin ti là trng thái  
i. Như vy i, j S : 0 P 1 và  
P = 1  
ij  
ij  
j
Nguyn ThKim Oanh – K50MTT  
Trang 22  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Mt tính cht quan trng ca chui Markov là trng thái tương lai chphụ  
thuc vào trng thái hin thi và nó không xy ra ti thi đim hin ti. Theo lun  
đim đó có ththy xác sut chuyn Pij chphthuc vào trng thái i.  
Chui Markov có nhiu ng dng trong nhiu lĩnh vc khác nhau. Vi các  
ng dng Internet thì PageRank là thut toán đin hình sdng mô hình chui  
Markov mà ta stìm hiu trong phn sau.  
3.1.1.2. Di chuyn ngu nhiên và dự đoán tác tti thăm mt host  
Di chuyn ngu nhiên theo đồ thvbn cht là chui Markov hu hn. Nó có  
rt nhiu tính cht tương tnhư chui Markov.  
Thc nghim ca Gkantsidis đã chra rng vi vic tìm kiếm mt thông tin  
xut hin thường xuyên trong mng thì vi lượng thông đip là ngang nhau, phương  
pháp đường đi ngu nhiên chc chn thc hin tt hơn phương pháp truyn thng  
phát tràn.  
Môi trường để tác tthc thi nhim vlà mng ngang hàng động, đầy tính  
ngu nhiên, luôn thay đổi. Ở đó tn ti độ trca snhn biết nhng thay đổi về  
topo mng. Vì vy mc đích cơ bn ca các tác tcũng là di chuyn mt cách ngu  
nhiên trong mng để thu thp thông tin. Hành động ca các tác tchbao gm vic  
di chuyn ngu nhiên tnút mng hin thi ti mt hàng xóm ca nó. Ti mi nút,  
tác ttruy vn dch v, lưu trdliu trong bnh.  
Tn sut tác tti thăm mt host có thể được dự đoán nhhàm F(N). Hàm  
F(N) cho biết xác sut mt tác ta A vi thông tin vdich vs S sti thăm  
mt host h H trong thi gian t. N là mt mô ttrng thái cc bbao gm các  
thành phn:  
t độ dài khong thi gian  
v – xác sut mt tác tsẽ ở ti host h  
η – sthhin ca dch vs  
|H| - tp các host có trong mng  
|A| - tp các tác tử  
l – thi gian trung bình cn để mt tác tdi chuyn tmt nút hàng xóm ti  
mt nút khác  
Nguyn ThKim Oanh – K50MTT  
Trang 23  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
τ – thi gian ln nht mà tác tnhìn thy dch vs  
F(N) được định nghĩa như mt ánh xtN ti xác sut thc:  
F: (t, v, η, |H|, |A|, l, τ ) α [0,1]  
Theo đánh giá trc quan thì |A| càng ln, |H| và l càng nhscó càng nhiu tác  
tti thăm host.  
(1)  
Kalman Filtering là phương pháp đánh giá trng thái ca mt hthng động  
tuyến tính tmt chui các phép đo. Tuy nhiên tn sut tác tmang thông tin ti  
thăm mt host skhông theo phân bGaussian tuyến tính, đặc bit là vi mng có  
độ thay đổi ln, vì thế hàm F(N) không thể được dự đoán bng phương pháp tương  
tnhư Kalman Filtering.  
3.1.2. Thut toán PageRank  
Để dự đoán tn sut ti thăm mt host xác định ca các tác tdi chuyn ngu  
nhiên, ta cn tính xác sut mt tác tsti thăm mt host xác định ti mt thi  
đim nào đó. PageRank là thut toán giúp ta làm vic đó.  
PageRank là thut toán phân tích liên kết để đánh giá trng sca mi phn tử  
trong tp các tài liu siêu liên kết ví dnhư WWW. Thut toán này được sdng  
trong công ctìm kiếm ni tiếng Google. Nó sxác định xác sut mà mt người  
lướt web ngu nhiên sthăm mt trang ti mt thi đim nào đó. Nếu N là strang  
web đã biết và mt trang i có ki liên kết thì xác sut chuyn ttrang i ti các trang  
khác mà i liên kết ti là  
và  
cho các trang mà i không có liên  
kết ti. Trong đó tham sα thường được ly giá trbng 0.85.  
PageRank dùng chui Markov để mô hình hóa đường đi ngu nhiên theo đồ  
thca mng Internet. Thut toán này cũng được áp dng để tính xác sut mt tác tử  
sti thăm mt host xác định ti mt thi đim nào đó. Nó li dng tính dng ca  
đồ th, tính toán vecto đặc trưng π ca ma trn kJ. Vecto đặc trưng π tương ng  
vi giá trriêng λ1 bi phương trình π J = λ1 π π cha xác sut mt agent di  
chuyn ngu nhiên sẽ ở trên mt nút bt kì. Trong trường hp liên quan ti đường  
đi ngu nhiên thì J là ma trn xác sut chuyn thost này ti host khác trong mng.  
Ma trn J có dng:  
Nguyn ThKim Oanh – K50MTT  
Trang 24  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
h h h13 ... h1 n  
11  
12  
h 21 h 22 h 23 ... h 2 n  
.......... .......... .  
h i1 h i 2 .... h ij ... h in  
.......... .......... ..  
h n 1 h n 2 .......... h nn  
J =  
trong đó hij là xác sut chuyn thost i sang host j  
π 1 là xác sut mà tác tử ở ti host 1.  
Theo dự đoán xác sut tác tử ở ti host 2 là π 2 = π 1 J .  
Xác sut tác tử ở ti host 3 là : π 3 = π 2 J = π 1 J2  
Cnhư thế, xác sut tác tử ở ti host n là : π n = π 1 J n1  
Thut toán PageRank vi đầu vào là ma trn kJ đại din cho mng, d là số  
thc nm trong khong [0,1] (thường ly giá tr0.85), iterations là sln lp và tt  
1
ccác phn tca π sẽ được khi to là  
.
| H |  
Phát biu thut toán PageRank như sau:  
Thut toán được lp iterations bước, ti mi bước, duyt các phn tca tp  
|H| . Vi mi phn tnày xét các liên kết ca nó ti các nút khác, nếu có bao nhiêu  
liên kết thì tăng biến đếm lên tng đó. Giá trca π ti các nút hàng xóm schia  
đều cho sliên kết này và cng dn vào biến đếm sum. Và giá trπ ti các nút hin  
thi sbng tng ca (1-d) và d*sum. Dưới đây là đon gimã cho thut toán  
for i = 1 to iterations do  
for j = 1 to |H| do  
sum 0  
for k = 1 to |H| do  
if Jk,j > 0 then  
links |{x| (1 x |H|) (Jk,x > 0)}|  
if links > 0 then  
sum sum + π k ÷links  
π j (1-d) + d*sum  
Nguyn ThKim Oanh – K50MTT  
Trang 25  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Theo thut toán PageRank trên, π h chính là xác sut mà mt tác taA  
nm trên mt host xác định h H ti mt thi gian cho trước. Trong toán hc π có  
thể được tính bng vecto đặc trưng ca (dJT) trong đó J đã được chun hóa.  
3.2. Các tham số đánh giá hiu năng  
3.2.1. Xác sut tác tti thăm mt host cho trước  
Trong trường hp |A| = 1 thì ta có thsdng π để ước lượng v:  
ˆ
v = π h  
(3)  
ˆ
Nếu |A| > 1 thì cn phi sdng mt phân bnhphân để tính toán v . Có thể  
ˆ
thy v bng 1 trừ đi xác sut mà không có |A| tác tsti thăm trong thi gian t.  
|A|  
t
|A| t  
ˆ
v = 1 – (1 – (1 – (1 - π h) ) ) = 1 – (1 - π h)  
(4)  
ˆ
Tuy nhiên skhông đủ nếu chda trên v để định nghĩa F(N) vì không phi  
tt ccác tác tti thăm host đều có đầy đủ dliu vdch vụ được định v.  
3.2.2. Xác sut tác tphát hin dch vụ  
v đưa ra mt cơ chế dự đoán trước stác tdi chuyn ngu nhiên sthăm mt  
host. Tuy nhiên, v không được tính cho trường hp các tác tnày có thchưa nhìn  
thy dch vs.  
H H là mt tp các host mà mt tác nhân ghé thăm trong thi gian τ và  
là tp các dch vmà tác nhân tìm thy trong thi gian τ . Giá trkvng  
ca slượng các host mà tác nhân sghé thăm là :  
τ
λ
⎣ ⎦  
⎢ ⎥  
<|H|> =  
(5)  
⎢ ⎥  
Vi η là sthhin ca dch vs thì xác sut mt thhin ca dch vtn ti  
η
H
mt host ngu nhiên là  
.
Xác sut mà mt tác tdi chuyn ngu nhiên trong mng sphát hin ra mt  
thhin ca dch vs trong thi gian τ có thể được mô hình hóa bng phân bnhị  
phân ca |H| phép th.  
Nguyn ThKim Oanh – K50MTT  
Trang 26  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
H n  
n ⎛  
⎟ ⎜  
⎟ ⎜  
⎠ ⎝  
Η
η
H
η
H
P(n| |H|) =  
1−  
(6)  
n
Trong đó n là sthhin ca dch vs được tìm thy:  
n = |{x|xSx=s}|  
(7)  
Tng tt cn khi n 1 ta có:  
τ
λ
H i  
i ⎛  
⎟ ⎜  
⎟ ⎜  
⎠ ⎝  
H
H ⎞  
η
H
η
H
η
H
P(n 1) =  
1−  
= 1 - 1−  
(8)  
i
i=1  
P(n 1) = P(x, x S x = s) là xác sut mt tác tva nhìn thy ít nht mt thể  
hin ca dch vs trong khi di chuyn ngu nhiên trong thi gian τ  
3.2.3. Hàm dự đoán tác tnhìn thy dch vvà thăm host  
Cho xác sut mt tác ta sghé thăm mt host là v, và xác sut mt tác tdi  
chuyn ngu nhiên sthy mt thhin ca dch vlà P(n 1), ta có thxác định  
được ánh xhàm F(N)  
Gisvic mt tác tthy mt thhin ca dch vs độc lp vi vic nó ghé  
thăm host h. Gi A là tp các agent ghé thăm h trong thi gian t. Sdng A, ta có  
thkết hp công thc (4) và (8) và có :  
Sau đó sdng phân bnhphân ta có thể định nghĩa ánh xF(N) cho tt cgiá trị  
ca t:  
Nguyn ThKim Oanh – K50MTT  
Trang 27  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Hàm F(N) hu dng trong vic đoán trước slượng agent di chuyn ngu  
nhiên nhìn thy dch vs trong thi gian τ và ti thăm host h trong thi gian t. Ly  
ví dtrong lĩnh vc hàng không, gisrng mt tác tcn phi định vị được mt  
dch vtrong mt khong thi gian cố định. Nếu dch vkhông còn tn ti thì tác tử  
sẽ đợi trong khong thi gian đó để ctìm kiếm dch v. Sdng hàm F(N) tác tử  
có thdự đoán nếu nó nghe thy thông tin tbt cmt tác ttìm kiếm dch vnào  
khác trong thi gian t. Nếu F(N) trvxác sut thp, tác tsngay lp tc lp li  
kế hoch mà không cn chthêm.  
3.2.4. Thi gian kì vng tác tdi chuyn ngu nhiên trvngun  
Mng ad-hoc có thể được mô hình hóa bi đồ thliên thông, không hướng nếu  
coi các host là các đỉnh và các liên kết gia các host trong mng là các cnh.  
Ta có đồ thG=(V, E) trong đó V là tp các đỉnh, E là tp các cnh. Đồ thG  
có n đỉnh và m cnh. Vi mi đỉnh v V, Γ(v) là tp các hàng xóm ca v, đường đi  
ngu nhiên trên G là mt quá trình liên tc tiếp din ca mt chui các bước bt đầu  
từ đỉnh v0 chn ngu nhiên 1 đỉnh hàng xóm ca v0, điu này cũng có nghĩa là ta  
chn 1 cnh ngu nhiên xut phát từ đỉnh v0 để đến đỉnh v1 ∈ Γ(v0 ) . Ti đỉnh v1 ta  
li tiếp tc quá trình như thế. Schn la ngu nhiên mi bước là hoàn toàn độc  
lp vi bước trước đó.  
Theo lý thuyết đường đi ngu nhiên trong đồ thta có công thc sau:  
Vi mi v V, hvv = 1/πv = 2m/d(v)  
(11)  
trong đó πv là phân bdng ti đỉnh v, d(v) là sbc ca đỉnh v  
Tcông thc này ta có định nghĩa “hitting time” huv là sbước kì vng trong  
đường đi ngu nhiên xut phát tu và kết thúc v.  
Nguyn ThKim Oanh – K50MTT  
Trang 28  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
Và Cuv là thi gian chuyn mch: Cuv = huv + hvu = Cvu là thi gian kì vng mà  
mt đường đi ngu nhiên bt đầu tu và trvu sau khi đã thăm v ít nht 1 ln.  
Cu(G) là độ ln kì vng ca đường đi bt đầu u và kết thúc trên mi đỉnh ca  
G ít nht 1 ln. Thi gian phca đồ thG: C(G) = maxuCu(G) là thi gian ln nht  
ca đường đi ngu nhiên xut phát tu và ti thăm mi đỉnh ca G ít nht 1 ln.  
Vic tính nhng giá trthi gian kì vng nêu trên rt có ý nghĩa khi tác tcn  
tìm kiếm đường đi và xây dng bng định tuyến cho host hoc đánh giá tn sut cp  
nht thông tin trong mng.  
3.3. Mô hình trin khai  
Để mô hình hóa mng ta sdng phương pháp liên thông chính xác to ra đồ  
thmng di động ad-hoc. Các kết ni được xác định bng khong cách Euclidean  
gia các host. Sdi chuyn ca các host snm trong vùng din tích 1200x1200 m  
và mi host có vùng phsóng là 300 m. Ti thi đim ban đầu ca thí nghim, các  
host được di chuyn mt cách ngu nhiên trong vùng din tích đã định. Tt ccác  
tác tvà thhin ca dch vụ đều được phân bmt cách ngu nhiên trên các host.  
Trong mi ln lp ca mô phng sthc hin các công vic sau:  
1. Hướng di chuyn ca mi host sẽ được chn ngu nhiên. Khnăng host di  
chuyn nhưng vn ginguyên hướng cũ là 60%, host quay 450 theo chiu kim đồng  
hvà ngược chiu kim đồng hmi trường hp là 20%.  
2. Các host di chuyn vphía trước 1m theo hướng đã chn  
3. Các tác tdi trú thost hin ti ti mt hàng xóm ca host đó mt cách  
ngu nhiên.  
4. Mi thhin ca dch vs cũng được coi là mt tác tdi động và cũng có  
thdi trú ti mt nút hàng xóm ngu nhiên như mô tả ở trên  
5. Trong mi ln lp t, mi host sdng hàm F(N) để tính xác sut mt tác tử  
vi thông tin dch vti thăm nó trong nhng ln lp tiếp theo t. Tn sut thc sự  
A
các tác tti thăm là  
cũng được ghi li.  
t
Nguyn ThKim Oanh – K50MTT  
Trang 29  
ĐH Công ngh- ĐH Quc Gia HN  
Sdng tác tdi động phát hin dch vtrong các mng ngang hàng không có cu trúc!  
3.4. Đánh giá mô hình  
Tác tdi động tra hu dng trong vic thu thp thông tin. Nhnhng thông  
tin cp nht cutác tdi động, các hthng đa tác thot động trên mng ngang  
hàng có thto ra nhng khnăng mi đầy tin ích như:  
Đặt ra mt ngưỡng nào đấy, khi mà tác tvi nhim vdo thám không tìm  
thy mt dch vhay host cn thiết nào trong thi gian cho phép thì ta có thcoi là  
dch vhoc host đấy không còn khdng na. Khi đó ta không tiếp tc đợi tác tử  
này na mà ngay lp tc lp lch li cho quá trình tìm kiếm. Điu này làm gim độ  
trvthi gian chờ đợi và tìm kiếm trong mng.  
Phát hin nhng vùng đang xung cp ca mng. Dùng các tác tdo thám ta  
có thdự đoán nhng vùng nào mng bli, bphân đon để kp thi đưa ra hướng  
gii quyết. Nơi đó là nhng nơi tác tkhông xut hin hoc là không có nhng liên  
lc vi nhng nút mng còn sng.  
Các host sdng thông tin do các tác tcung cp để báo cho hàm gii hn  
thi gian vkhong thi gian chúng có thchờ đợi để thc thi nếu các host này bị  
phthuc vào các dch vtxa.  
Ti ưu stác tử để đạt được yêu cu tn sut cp nht thông tin ca các tác tử  
phát hin dch v.  
Vn còn mt sgii hn cn phi kể đến như các phn tca mô ttrng thái  
N, tt cả đều có ththay đổi và không được xác định trong mt smin. Vì vy các  
tác tcó thphi da vào mt stham snhư λη . Thêm vào đó có nhiu cách  
hiu qumà tác tcó thể đi trong mng. Vic nghiên cu nhng công nghthay đổi  
này là cn thiết tuy nhiên các mô hình toán hc ca chúng phc tp hơn là đường đi  
ngu nhiên.  
Còn mt gii hn na đó là mc dù v có thể được định nghĩa tπh nhưng duy  
trì topo mng toàn cc, J, là mt vn đề khó khăn trong mng ngang hàng động.  
Các thut toán định tuyến tích cc trong mng ad-hoc thường định nghĩa mt giao  
thc để lan truyn thông tin nhưng nó rt đắt. Tng lượng bnhhoc băng thông  
yêu cu cho mi thông đip trong trường hp xu nht là O(n2) (đó là trường hp di  
chuyn qua toàn bma trn k).  
Nguyn ThKim Oanh – K50MTT  
Trang 30  
ĐH Công ngh- ĐH Quc Gia HN  

Tải về để xem bản đầy đủ

pdf 48 trang yennguyen 18/06/2025 510
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pdfluan_van_su_dung_tac_tu_di_dong_phat_hien_dich_vu_trong_cac.pdf