Luận án Tiến sĩ Khoa học Máy tính: Một số thuật toán META HEURISTIC giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây

Chia sẻ: Gaocaolon6 Gaocaolon6 | Ngày: | Loại File: PDF | Số trang:163

Thêm vào BST

Báo xấu

73
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án nghiên cứu bài toán cực đại diện tích bao phủ trong mạng cảm biến không dây không đồng nhất; bài toán cực đại diện tích bao phủ trong mạng cảm biến không dây đồng nhất có ràng buộc chướng ngại vật; bài toán bao phủ đối tượng đảm bảo kết nối và chịu lỗi trong mạng cảm biến không dây và mạng cảm biến không dây và mạng cảm biến không dây có sử dụng điểm thu phát di động.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học Máy tính: Một số thuật toán META HEURISTIC giải bài toán bao phủ diện tích và đối tượng trong mạng cảm biến không dây

BË GIO DÖC V O TO TR×ÍNG I HÅC BCH KHOA H NËI NGUYN THÀ HNH MËT SÈ THUT TON METAHEURISTIC GII BI TON BAO PHÕ DIN TCH V ÈI T×ÑNG TRONG MNG CM BIN KHÆNG DY LUN N TIN S KHOA HÅC MY TNH H Nëi - 2019
BË GIO DÖC V O TO TR×ÍNG I HÅC BCH KHOA H NËI NGUYN THÀ HNH MËT SÈ THUT TON METAHEURISTIC GII BI TON BAO PHÕ DIN TCH V ÈI T×ÑNG TRONG MNG CM BIN KHÆNG DY Ng nh : Khoa håc m¡y t½nh M¢ sè : 9480101 LUN N TIN S KHOA HÅC MY TNH NG×ÍI H×ÎNG DN KHOA HÅC: 1. PGS.TS Huýnh Thà Thanh B¼nh 2. PGS.TS Nguy¹n ùc Ngh¾a H Nëi - 2019
Líi cam oan Nghi¶n cùu sinh cam oan luªn ¡n n y l cæng tr¼nh nghi¶n cùu cõa ch½nh m¼nh d÷îi sü h÷îng d¨n cõa tªp thº c¡n bë h÷îng d¨n. Luªn ¡n câ sû döng thæng tin tr½ch d¨n tø nhi·u nguçn tham kh£o kh¡c nhau v c¡c thæng tin tr½ch d¨n ÷ñc ghi rã nguçn gèc. C¡c sè li»u, k¸t qu£ trong luªn ¡n l trung thüc v ch÷a tøng ÷ñc cæng bè trong c¡c cæng tr¼nh nghi¶n cùu cõa b§t ký t¡c gi£ n o kh¡c. H Nëi, ng y 05 th¡ng 11 n«m 2019 Thay m°t tªp thº gi¡o vi¶n h÷îng d¨n Nghi¶n cùu sinh PGS.TS Huýnh Thà Thanh B¼nh Nguy¹n Thà H¤nh ii
Líi c£m ìn Líi ¦u ti¶n, tæi xin b y tä láng bi¸t ìn s¥u sc tîi c¡c th¦y cæ gi¡o h÷îng d¨n, PGS.TS Huýnh Thà Thanh B¼nh v PGS.TS Nguy¹n ùc Ngh¾a , ¢ ành h÷îng khoa håc v tªn t¥m gióp ï, ch¿ b£o trong suèt qu¡ tr¼nh ho n th nh luªn ¡n t¤i tr÷íng ¤i håc B¡ch Khoa H Nëi. Tæi xin ch¥n th nh c£m ìn Ban gi¡m hi»u, Ban l¢nh ¤o Vi»n cæng ngh» thæng tin v truy·n thæng, c¡c th¦y cæ bë mæn Khoa håc m¡y t½nh v c¡c b¤n ð pháng nghi¶n cùu Mæ h¼nh hâa, mæ phäng v tèi ÷u hâa, tr÷íng ¤i håc B¡ch khoa H Nëi ¢ t¤o i·u ki»n thuªn lñi nh§t º tæi ho n th nh ch÷ìng tr¼nh håc tªp v thüc hi»n luªn ¡n nghi¶n cùu khoa håc cõa m¼nh. Tæi xin ch¥n th nh c£m ìn Ban gi¡m hi»u tr÷íng ¤i håc Ph÷ìng æng, tªp thº c¡n bë, gi£ng vi¶n Khoa cæng ngh» thæng tin v truy·n thæng nìi nghi¶n cùu sinh cæng t¡c v c¡c b¤n b± th¥n thi¸t ¢ luæn t¤o i·u ki»n, ëng vi¶n, khuy¸n kh½ch º tæi ho n th nh luªn ¡n n y. Cuèi còng, tæi ch¥n th nh b y tä láng c£m ìn tîi gia ¼nh ¢ ki¶n tr¼, chia s´, ëng vi¶n nghi¶n cùu sinh trong suèt qu¡ tr¼nh håc tªp v ho n th nh luªn ¡n n y. H Nëi, ng y 05 th¡ng 11 n«m 2019 Nghi¶n cùu sinh Nguy¹n Thà H¤nh iii
MÖC LÖC BNG THUT NGÚ VIT TT vii DANH SCH BNG ix DANH SCH HNH V xi MÐ U 1 1 CÌ SÐ LÞ THUYT 15 1.1 M¤ng c£m bi¸n khæng d¥y . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.1 C£m bi¸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.2 Nót c£m bi¸n . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.1.3 M¤ng c£m bi¸n . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.1.4 Nhúng v§n · th¡ch thùc trong m¤ng c£m bi¸n . . . . . . 19 1.2 C¡c mæ h¼nh bao phõ cõa c£m bi¸n v m¤ng c£m bi¸n khæng d¥y 20 1.2.1 Mæ h¼nh bao phõ cõa c£m bi¸n . . . . . . . . . . . . . . . . 21 1.2.2 B i to¡n bao phõ trong m¤ng c£m bi¸n khæng d¥y . . . . . 22 1.3 B i to¡n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.3.1 B i to¡n tèi ÷u li¶n töc . . . . . . . . . . . . . . . . . . . . 26 1.3.2 B i to¡n tèi ÷u tê hñp . . . . . . . . . . . . . . . . . . . . . 27 1.3.3 Ph÷ìng ph¡p gi£i b i to¡n tèi ÷u . . . . . . . . . . . . . . . 28 1.4 K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2 BI TON CÜC I DIN TCH BAO PHÕ TRONG MNG CM BIN KHÆNG DY KHÆNG ÇNG NHT 38 iv
2.1 Ph¡t biºu b i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2 Gi£i thuªt · xu§t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.1 Gi£i thuªt t¼m ki¸m chim cuckoo c£i ti¸n . . . . . . . . . . 40 2.2.2 Gi£i thuªt Democratic PSO . . . . . . . . . . . . . . . . . . 46 2.2.3 Gi£i thuªt thö ph§n cho hoa hén t¤p . . . . . . . . . . . . 49 2.2.4 Gi£i thuªt di truy·n c£i ti¸n . . . . . . . . . . . . . . . . . . 53 2.3 K¸t qu£ thüc nghi»m . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.3.1 Dú li»u thüc nghi»m . . . . . . . . . . . . . . . . . . . . . . 65 2.3.2 Tham sè thüc nghi»m . . . . . . . . . . . . . . . . . . . . . 65 2.3.3 So s¡nh ¡nh gi¡ k¸t qu£ thüc nghi»m . . . . . . . . . . . . 68 2.4 K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3 BI TON CÜC I DIN TCH BAO PHÕ TRONG MNG CM BIN KHÆNG DY KHÆNG ÇNG NHT CÂ RNG BUËC CH×ÎNG NGI VT. 76 3.1 Ph¡t biºu b i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2 Gi£i thuªt · xu§t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.2.1 Gi£i thuªt di truy·n c£i ti¸n . . . . . . . . . . . . . . . . . . 77 3.2.2 Gi£i thuªt tèi ÷u hâa b¦y n c£i ti¸n . . . . . . . . . . . . 86 3.3 K¸t qu£ thüc nghi»m . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.3.1 Kàch b£n thüc nghi»m . . . . . . . . . . . . . . . . . . . . . 90 3.3.2 Tham sè thüc nghi»m . . . . . . . . . . . . . . . . . . . . . 91 3.3.3 So s¡nh ¡nh gi¡ k¸t qu£ thüc nghi»m . . . . . . . . . . . . 93 3.4 K¸t luªn ch÷ìng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4 BI TON BAO PHÕ ÈI T×ÑNG M BO KT NÈI V CHÀU LÉI TRONG MNG CM BIN KHÆNG DY V MNG CM BIN KHÆNG DY CÂ SÛ DÖNG IM THU PHT DI ËNG 107 4.1 B i to¡n bao phõ èi t÷ñng £m b£o k¸t nèi v chàu léi trong m¤ng c£m bi¸n khæng d¥y. . . . . . . . . . . . . . . . . . . . . . . . 108 4.1.1 Ph¡t biºu b i to¡n . . . . . . . . . . . . . . . . . . . . . . . 108 4.1.2 Gi£i thuªt · xu§t . . . . . . . . . . . . . . . . . . . . . . . 109 v
4.1.3 K¸t qu£ thüc nghi»m . . . . . . . . . . . . . . . . . . . . . . 114 4.2 B i to¡n bao phõ èi t÷ñng £m b£o k¸t nèi trong m¤ng c£m bi¸n khæng d¥y câ sû döng c¡c iºm thu ph¡t di ëng . . . . . . . 117 4.2.1 Ph¡t biºu b i to¡n . . . . . . . . . . . . . . . . . . . . . . . 117 4.2.2 Gi£i thuªt · xu§t . . . . . . . . . . . . . . . . . . . . . . . 118 4.2.3 K¸t qu£ thüc nghi»m . . . . . . . . . . . . . . . . . . . . . . 126 4.3 K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 KT LUN 134 DANH MÖC CÆNG TRNH CÆNG BÈ 137 TI LIU THAM KHO 140 vi
BNG THUT NGÚ VIT TT Chú vi¸t tt T¶n ¦y õ IoT Internet of Things WSNs Wireless Sensor Networks MWSNs Mobile Wireless Sensor Networks SWSNS Sparse Wireless Sensor Networks HWSNS Hybrid Wireless Sensor Networks LoS Line-of-Sight VFA Virtual Force Algorithm MVFA Modify Virtual Force Algorithm GA Genetic Algorithm PSO Particle Swarm Optimization CS Cuckoo Search ICS Improve Cuckoo Search FPA Flower Pollination Algorithm CFPA Chaotic Flower Pollination Algorithm DPSO Democratic Particle Swarm Optimization ACB Artificial Bee Colony MCT Maximum Cover Tree SCAN Spreadable Connected Automomic Network ITS Intelligent Transportation System MR Mobile Relay RADA Resource Aware Data Accumulation MDC Mobile Data Collector ROM Read only Memory RAM Random Access Memory LX Laplace Crossover AMXO Arithmetic Crossover TC Target Coverage NCFT Network Connectivity Fault Tolerance SSCAT Sensor Set Covering All Targets FS Final Solution USP Using Spanning Tree vii
UTSP Using Travelling Salesman Problem TSP Travelling Salesman Problem SSFTP Sensors Set for Two Paths PGA Pure Greedy Approach SGA Spanning tree and Greedy Approach HCG Heuristic Clustering Greedy MRP Minimum Relay Node Placement MEST Mest Problem in Steiner Tree EMST Euclide Minimum Spanning Tree viii
DANH SCH BNG 2.1 Dú li»u thüc nghi»m. . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.2 B£ng tham sè thüc nghi»m cõa c¡c gi£i thuªt DPSO . . . . . . . . 66 2.3 B£ng tham sè thüc nghi»m cõa gi£i thuªt ICS . . . . . . . . . . . 66 2.4 B£ng tham sè thüc nghi»m cõa gi£i thuªt CFPA . . . . . . . . . . 67 2.5 Tham sè thüc nghi»m cõa gi£i thuªt MIGA. . . . . . . . . . . . . 67 2.6 K¸t qu£ mæ h¼nh thù nh§t . . . . . . . . . . . . . . . . . . . . . . . 69 2.7 Trung b¼nh di»n t½ch bao phõ v ë l»ch chu©n cõa c¡c gi£i thuªt IGA, DPSO, ICS, CFPA v MIGA tr¶n 15 bë dú li»u v méi bë dú li»u ch¤y thüc nghi»m 30 l¦n l§y trung b¼nh (Avg: Trung b¼nh di»n t½ch bao phõ, ë l»ch chu©n (SD) v Upper Bound: di»n t½ch lîn nh§t cõa tøng bë dú li»u ¤t ÷ñc.) . . . . . . . . . . . . . . . 73 3.1 Kàch b£n 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.2 Kàch b£n 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.3 Kàch b£n 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.4 Kàch b£n 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.5 Kàch b£n 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6 Tham sè thüc nghi»m cõa gi£i thuªt MGA . . . . . . . . . . . . . 92 3.7 Tham sè thüc nghi»m cõa gi£i thuªt PSO . . . . . . . . . . . . . . 92 3.8 Tham sè thüc nghi»m cõa gi£i thuªt IPSO . . . . . . . . . . . . . 93 4.1 Dú li»u thüc nghi»m b i to¡n tèi ÷u bao phõ £m b£o k¸t nèi v chàu léi trong WSNs. . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.2 Dú li»u ¦u v o cõa b i to¡n tèi ÷u bao phõ £m b£o k¸t nèi v chàu léi trong WSNs. . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.3 Tham sè thüc nghi»m cho gi£i thuªt UTSP. . . . . . . . . . . . . . 114 ix
4.4 K¸t qu£ thüc nghi»m cõa hai gi£i thuªt USP v UTSP khi so s¡nh v· sè l÷ñng nót c£m bi¸n, nót chuyºn ti¸p v thíi gian thüc hi»n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.5 Dú li»u cho kàch b£n £nh h÷ðng cõa sè l÷ñng tr¤m thu ph¡t dú li»u ëng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.6 Dú li»u cho kàch b£n £nh h÷ðng cõa sè l¦n thu thªp dú li»u . . . 127 4.7 Dú li»u cho kàch b£n £nh h÷ðng cõa sè l÷ñng èi t÷ñng . . . . . . 127 x
DANH SCH HNH V 1.1 C§u t¤o sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2 C§u tróc cõa mët nót c£m bi¸n . . . . . . . . . . . . . . . . . . . . 17 1.3 C§u tróc cõa mët nót c£m bi¸n . . . . . . . . . . . . . . . . . . . . 18 1.4 C¡c mæ h¼nh c£m bi¸n . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5 V½ dö v· b i to¡n bao phõ èi t÷ñng trong WSNs: trong â tªp T1 , T2 , T3 , T4 , l c¡c èi t÷ñng; S1 , S2 , S3 , S4 , S5 , S6 l tªp c¡c c£m bi¸n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.6 C¡c mæ h¼nh bao phõ r o chn trong WSNs. . . . . . . . . . . . . 24 1.7 V½ dö v· b i to¡n bao phõ 100% di»n t½ch trong WSNs. . . . . . . 25 1.8 v½ dö v· b i to¡n cüc ¤i di»n t½ch trong WSNs khæng çng nh§t vîi sè l÷ñng c£m bi¸n cho tr÷îc. . . . . . . . . . . . . . . . . . . . 25 1.9 V½ dö v· b i to¡n thi¸t k¸ m¤ng i»n. . . . . . . . . . . . . . . . . 27 2.1 M¢ hâa c¡ thº: (a ) Biºu di¹n bði khæng gian kiºu gen, (b ) Biºu di¹n bði khæng gian kiºu h¼nh. . . . . . . . . . . . . . . . . . . . . . 41 2.2 Mæ t£ qu¡ tr¼nh khði t¤o heuristic cõa qu¦n thº: h¼nh (a) líi gi£i thu ÷ñc sau qu¡ tr¼nh khði t¤o l khæng tèi ÷u , h¼nh (b) líi gi£i thu ÷ñc sau qu¡ tr¼nh khði t¤o l tèi ÷u (Olap = 0). . . . . . . . . 55 2.3 Qu¡ tr¼nh lai gh²p º sinh ra hai con Z1 v Z2 tø hai cha mµ P1 v P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4 Mæ t£ qu¡ tr¼nh ët bi¸n sû döng Gauss ëng . . . . . . . . . . . 57 2.5 Mæ t£ qu¡ tr¼nh t½nh to¡n cõa b÷îc 1: Chia mi·n A th nh c¡c ph¦n nhä bði c¡c ÷íng th¯ng song song vîi tröc tung v ÷íng th¯ng n y ph£i ti¸p xóc vîi h¼nh trán v c¡c giao iºm cõa c¡c h¼nh trán. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.6 Tr÷íng hñp mët c£m bi¸n ÷ñc triºn khai trong mi·n D. . . . . . 59 2.7 Mæ t£ tr÷íng hñp hai c£m bi¸n khæng giao nhau tr¶n mi·n D. . . 60 xi
2.8 Mæ t£ tr÷íng hñp hai c£m bi¸n giao nhau tr¶n mi·n D. . . . . . . 61 2.9 Thíi gian t½nh to¡n cõa c¡c thuªt to¡n . . . . . . . . . . . . . . . . 69 2.10 ë hëi tö cõa thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . . . 70 2.11 Trung b¼nh di»n t½ch bao phõ cõa c¡c gi£i thuªt IGA, DPSO, ICS, CFPA v MIGA tr¶n c¡c bë dú li»u bao phõ 70% di»n t½ch tr¶n mi·n A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.12 Trung b¼nh di»n t½ch bao phõ cõa c¡c gi£i thuªt IGA, DPSO, ICS, CFPA v MIGA tr¶n c¡c bë dú li»u bao phõ 80% di»n t½ch tr¶n mi·n A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.13 Trung b¼nh di»n t½ch bao phõ cõa c¡c gi£i thuªt IGA, DPSO, ICS, CFPA v MIGA tr¶n c¡c bë dú li»u bao phõ 90% di»n t½ch tr¶n mi·n A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.14 ë l»ch chu©n cõa c¡c gi£i thuªt IGA, DPSO, ICS, CFPA v MIGA tr¶n 15 bë dú li»u. . . . . . . . . . . . . . . . . . . . . . . . 73 2.15 Trung b¼nh thíi gian t½nh cõa c¡c gi£i thuªt IGA, DPSO, ICS, CFPA v MIGA tr¶n 15 bë dú li»u sau 30 l¦n ch¤y méi bë dú li»u. 74 2.16 Líi gi£i thu ÷ñc cõa MIGA tr¶n c¡c bë dú li»u s3-07, s4-09, s5-08 v s5-09. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.1 M¢ hâa c¡ thº: (a ) Biºu di¹n bði khæng gian kiºu gen, (b ) Biºu di¹n bði khæng gian kiºu h¼nh. . . . . . . . . . . . . . . . . . . . . . 78 3.2 Ba tr÷íng hñp khði t¤o qu¦n thº . . . . . . . . . . . . . . . . . . . 79 3.3 Thº hi»n ë chçng cõa hai c£m bi¸n si v sj . . . . . . . . . . . . . 81 3.4 C¡c tr÷íng hñp ë chçng cõa c£m bi¸n vîi bi¶n n¬m ð ngo i vòng gi¡m s¡t A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.5 Ph¥n chia ch½n vòng cõa ch÷îng ng¤i vªt. . . . . . . . . . . . . . . 83 3.6 ë chçng cõa mët ph¦n di»n t½ch cõa c£m bi¸n vîi ch÷îng ng¤i vªt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.7 Qu¡ tr¼nh lai gh²p sû döng ph²p lai BLXα giúa hai cha mµ S1 v S2 sinh ra con Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.8 Khði t¤o qu¦n thº trong IPSO sû döng ph¥n cöm. . . . . . . . . . 87 3.9 X¡c su§t º c¡c c¡ thº ÷ñc lüa chån trð th nh Cbest. . . . . . . . 88 3.10 Mæ phäng qu¡ tr¼nh cªp nhªt cõa c¡ thº trong IPSO. . . . . . . . 89 3.11 T¼m gi¡ trà phò hñp c1 v c2 cõa gi£i thuªt PSO. . . . . . . . . . . 94 xii
3.12 T¼m gi¡ trà c3 phò hñp cõa thuªt to¡n IPSO trong chi¸n l÷ñc 1 (S1-IPSO). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.13 T¼m gi¡ trà c3 phò hñp cõa thuªt to¡n IPSO trong chi¸n l÷ñc 2 (S2-IPSO). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.14 T¼m gi¡ trà c3 phò hñp cõa thuªt to¡n IPSO trong chi¸n l÷ñc 3 (S3-IPSO). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.15 Lüa chån t l» khði t¤o heuristic phò hñp cho PSO. . . . . . . . . 97 3.16 Lüa chån t l» khði t¤o heuristic phò hñp cho MGA. . . . . . . . . 98 3.17 Lüa chån t l» khði t¤o heuristic phò hñp cho chi¸n l÷ñc 1 cõa thuªt to¡n IPSO (S1-IPSO). . . . . . . . . . . . . . . . . . . . . . . 99 3.18 Lüa chån t l» khði t¤o heuristic phò hñp cho chi¸n l÷ñc 2 cõa thuªt to¡n IPSO (S2-IPSO). . . . . . . . . . . . . . . . . . . . . . . 99 3.19 Lüa chån t l» khði t¤o heuristic phò hñp cho chi¸n l÷ñc 3 cõa thuªt to¡n IPSO (S3-IPSO). . . . . . . . . . . . . . . . . . . . . . . 100 3.20 So s¡nh ba chi¸n l÷ñc cõa IPSO khi sû döng t l» khði t¤o heuristic l 50%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.21 p döng MVFA cho PSO, IPSO v MGA. . . . . . . . . . . . . . . 101 3.22 Ph¦n tr«m di»n t½ch bao phõ cõa hai gi£i thuªt PSO v IPSO trong c¡c kàch b£n 1,3 v 5. . . . . . . . . . . . . . . . . . . . . . . 101 3.23 Ph¦n tr«m di»n t½ch bao phõ cõa kàch b£n 1. . . . . . . . . . . . . 102 3.24 Ph¦n tr«m di»n t½ch bao phõ cõa kàch b£n 2. . . . . . . . . . . . . 103 3.25 Ph¦n tr«m di»n t½ch bao phõ cõa kàch b£n 3. . . . . . . . . . . . . 103 3.26 Ph¦n tr«m di»n t½ch bao phõ cõa kàch b£n 4. . . . . . . . . . . . . 104 3.27 Ph¦n tr«m di»n t½ch bao phõ cõa kàch b£n 5. . . . . . . . . . . . . 105 4.1 Bao phõ èi t÷ñng. . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.2 X¥y düng th nh ph¦n li¶n thæng. . . . . . . . . . . . . . . . . . . . 112 4.3 (a)X¥y düng ç thà ¦y õ; (b) x¥y düng c¡ch t¼m hai ÷íng i tø b§t ký mët ¿nh n o trong ç thà. . . . . . . . . . . . . . . . . . 113 4.4 So s¡nh thíi gian giúa hai gi£i thuªt USP v UTSP tr¶n 15 bë dú li»u sau 15 l¦n ch¤y méi bë dú li»u l§y trung b¼nh. . . . . . . . 116 4.5 K¸t qu£ cõa gi£i thuªt USP v UTSP tr¶n bë dú li»u S1-3 v S1-8: h¼nh (a) v h¼nh (b) thº hi»n k¸t qu£ cõa USP. Trong khi, h¼nh (c) v h¼nh (d) thº hi»n k¸t qu£ cõa gi£i thuªt UTSP. . . . . 116 4.6 Bao phõ èi t÷ñng trong tøng cöm. . . . . . . . . . . . . . . . . . . 121 xiii
4.7 °t c£m bi¸n £m b£o t½nh k¸t nèi t¤i thíi iºm thu thªp dú li»u b.124 4.8 nh h÷ðng cõa iºm thu ph¡t dú li»u di ëng l¶n hi»u n«ng cõa to n m¤ng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 4.9 nh h÷ðng cõa sè l÷ñng chu ký thu thªp dú li»u l¶n hi»u n«ng cõa to n m¤ng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.10 nh h÷ðng cõa sè l÷ñng èi t÷ñng l¶n hi»u n«ng cõa to n m¤ng. 132 xiv
GIÎI THIU Trong nhúng n«m g¦n ¥y, Internet v¤n vªt (Internet of Things - IoT) ¢ trð th nh mët chõ · nghi¶n cùu cõa nhi·u nh khoa håc trong v ngo i n÷îc. º ùng döng ÷ñc cæng ngh» IoT mët y¶u c¦u bt buëc °t ra l ph£i sû döng m¤ng c£m bi¸n khæng d¥y (Wireless Sensor Networks - WSNs). M¤ng c£m bi¸n khæng d¥y bao gçm hai th nh ph¦n ch½nh l mët tªp c¡c nót c£m bi¸n (Sensor Nodes) v mët ho°c mët sè tr¤m cì sð (Base Stations - Sink). Sau khi ÷ñc triºn khai t¤i àa iºm cö thº, c¡c nót c£m bi¸n li¶n töc thu thªp thæng tin trong ph¤m vi b¡n k½nh c£m bi¸n, xû lþ v trao êi thæng tin vîi c¡c nót c£m bi¸n kh¡c ho°c gûi thæng tin v· tr¤m cì sð thæng qua k¸t nèi khæng d¥y v giao thùc ành tuy¸n ¢ ÷ñc thi¸t lªp. B¶n c¤nh â, sü ph¡t triºn m¤nh m³ cõa c¡c h» thèng nhóng ¢ cho ph²p t¤o ra c¡c thi¸t bà nhä gån, câ kh£ n«ng xû lþ ëc lªp v truy·n thæng khæng c¦n d¥y d¨n. Nhí vªy m m¤ng c£m bi¸n khæng d¥y d¹ d ng ÷ñc triºn khai ð nhi·u àa h¼nh v ÷ñc ùng döng trong nhi·u l¾nh vüc cõa íi sèng nh÷ b£o v» mæi tr÷íng, qu¥n sü, y t¸, giao thæng thæng minh, qu£n lþ thà tr÷íng b¡n l´, qu£n lþ chuéi quy tr¼nh s£n xu§t, c£nh b¡o thi¶n tai, ch¡y røng, vv. [1], [2], [3], [4], [5]. Tuy nhi¶n, vi»c ph¡t triºn c¡c m¤ng c£m bi¸n khæng d¥y công g°p khæng ½t khâ kh«n do c¡c nót c£m bi¸n câ nguçn n«ng l÷ñng h¤n ch¸, kh£ n«ng ho¤t ëng trong c¡c i·u ki»n khc nghi»t cõa mæi tr÷íng v¨n cán th§p, hìn núa mët m¤ng c£m bi¸n câ thº l¶n ¸n h ng ngh¼n nót m¤ng d¨n ¸n vi»c duy tr¼ ho¤t ëng cõa m¤ng l r§t khâ kh«n. V¼ vªy, y¶u c¦u °t ra l ph£i x¥y düng WSNs sao cho £m b£o ti¸t ki»m chi ph½ x¥y düng m¤ng, truy·n thæng ên ành, kh£ n«ng b£o mªt, k²o d i thíi gian sèng cõa m¤ng,v.v. â ch½nh l nhúng th¡ch thùc m WSNs ang ph£i èi m°t nh÷ ch§t l÷ñng dàch vö m¤ng, n«ng l÷ñng, b£o mªt, ành tuy¸n, bao phõ, k¸t nèi, chàu léi vv. [1],[6], [7], [8], [9], [10], [11]. B¶n c¤nh v§n · sû döng n«ng l÷ñng hi»u qu£ th¼ b i to¡n triºn khai, hay t¼m và tr½ º °t c¡c c£m bi¸n công nhªn ÷ñc nhi·u sü quan t¥m tø c¡c nh nghi¶n cùu v c¡c nh cung c§p gi£i ph¡p li¶n quan ¸n m¤ng c£m bi¸n khæng d¥y. Bði v¼, vi»c °t nhúng c£m bi¸n n y mët c¡ch ng¨u nhi¶n câ thº khæng thüc hi»n ÷ñc nhi»m vö gi¡m s¡t cõa m¤ng v g¥y l¢ng ph½ v¼ ph£i dòng mët sè l÷ñng lîn c¡c c£m bi¸n. Tr¶n thüc t¸, do c¡c nót c£m bi¸n ch¿ ho¤t ëng tèt trong mët vòng b¡n k½nh nh§t ành, vi»c triºn khai c¡c c£m bi¸n º thu ÷ñc ë bao phõ lîn v £m b£o k¸t nèi chàu léi trong to n m¤ng ¢ trð th nh y¶u 1
c¦u c§p thi¸t v ë lîn cõa di»n t½ch vòng bao phõ, t½nh k¸t nèi v chàu léi ¢ trð th nh c¡c ti¶u ch½ quan trång trong vi»c ¡nh gi¡ ch§t l÷ñng dàch vö WSNs [12], [13], [11] [14]. Nhi·u mæ h¼nh b i to¡n kh¡c nhau ¢ ÷ñc c¡c nh khoa håc, tªp o n cæng ngh» ÷a ra º gi£i quy¸t b i to¡n tèi ÷u triºn khai c¡c nót c£m bi¸n £m b£o bao phõ, k¸t nèi v chàu léi trong m¤ng c£m bi¸n khæng d¥y v m¤ng c£m bi¸n khæng d¥y câ sû döng c¡c iºm thu ph¡t di ëng [11], [9], [15], [16], [17], [2], [18]. Tuy nhi¶n, trong méi b i to¡n ¢ ÷ñc nghi¶n cùu ð tr¶n v¨n cán câ nhi·u v§n · c¦n ÷ñc c£i ti¸n º gi£m thiºu v· thíi gian sèng, gi¡ th nh v t«ng ë ên ành trong vi»c triºn khai m¤ng. V¼ vªy, trong luªn ¡n n y t¡c gi£ tªp trung nghi¶n cùu b i to¡n tèi ÷u bao phõ, £m b£o t½nh k¸t nèi v chàu léi trong m¤ng c£m bi¸n khæng d¥y v m¤ng c£m bi¸n khæng d¥y câ sû döng c¡c iºm thu ph¡t di ëng (mobile sinks). C¡c b i to¡n v· tèi ÷u bao phõ, £m b£o t½nh k¸t nèi v chàu léi trong m¤ng c£m bi¸n khæng d¥y v m¤ng c£m bi¸n khæng d¥y câ sû döng c¡c iºm thu ph¡t di ëng ÷ñc gi£i quy¸t trong luªn ¡n ·u l c¡c b i to¡n NP-khâ, ngh¾a l khæng câ thuªt to¡n thíi gian a thùc º gi£i chóng, ngo¤i trø P = N P . Do â, t¡c gi£ chån c¡ch ti¸p cªn gi£i x§p x¿ sû döng gi£i thuªt metaheuristic, heuristic º gi£i quy¸t c¡c b i to¡n ÷ñc nhi·u t¡c gi£ nghi¶n cùu v c¡c mæ h¼nh ÷ñc c£i ti¸n tø mæ h¼nh tr÷îc â cho phò hñp vîi thüc t¸ triºn khai m¤ng. C¡c gi£i thuªt · xu§t ÷ñc c i °t, thû nghi»m tr¶n c¡c bë dú li»u ÷ñc c¡c nh nghi¶n cùu tr÷îc â ÷a ra º so s¡nh, ¡nh gi¡ hi»u n«ng. èi vîi nhúng mæ h¼nh ÷ñc · xu§t trong luªn ¡n, t¡c gi£ ¢ x¥y düng c¡c kàch b£n m¤ng a d¤ng nh¬m xem x²t ¡nh gi¡ kh¡ch quan tr¶n h¦u h¸t c¡c ti¶u ch½ x¥y düng m¤ng. Têng quan t¼nh h¼nh nghi¶n cùu trong v ngo i n÷îc Trong ph¦n n y, t¡c gi£ tr¼nh b y têng quan v· c¡c nghi¶n cùu li¶n quan ¸n vi»c gi£i quy¸t ba v§n · ë bao phõ, t½nh k¸t nèi v chàu léi trong m¤ng c£m bi¸n khæng d¥y v m¤ng c£m bi¸n khæng d¥y câ sû döng iºm thu ph¡t di ëng m luªn ¡n quan t¥m gi£i quy¸t. T¼nh h¼nh nghi¶n cùu ngo i n÷îc Têng quan v· b i to¡n bao phõ trong m¤ng c£m bi¸n khæng d¥y ¢ ÷ñc thüc hi»n bði Bang Wang [11]. Theo t¡c gi£, ë bao phõ, t½nh k¸t nèi, chàu léi l mët y¸u tè quan trång trong ¡nh gi¡ ch§t l÷ñng m¤ng c£m bi¸n. Do â câ r§t nhi·u nghi¶n cùu li¶n quan ¸n v§n · n y. Nh¼n chung, vîi nhúng gi£ thi¸t v möc ti¶u câ thº kh¡c nhau, b i to¡n bao phõ câ thº chia th nh ba nhâm: b i to¡n bao phõ èi t÷ñng (target coverage), b i to¡n bao phõ di»n t½ch (area coverage), b i to¡n bao phõ r o chn. Luªn ¡n tªp trung nghi¶n cùu hai mæ 2
h¼nh b i to¡n bao phõ di»n t½ch v b i to¡n bao phõ èi t÷ñng. B i to¡n bao phõ di»n t½ch: Cho ¸n n«m 2011, khi nhc ¸n b i to¡n bao phõ di»n t½ch trong m¤ng c£m bi¸n khæng d¥y, ng÷íi ta ngh¾ ngay ¸n vi»c to n bë khu vüc °t c£m bi¸n ·u ÷ñc gi¡m s¡t. Câ thº xem ¥y l tr÷íng hñp mð rëng cõa b i to¡n bao phõ èi t÷ñng, trong â måi iºm thuëc khu vüc c¦n gi¡m s¡t ·u ÷ñc coi l èi t÷ñng c¦n ÷ñc bao phõ. Mæ h¼nh b i to¡n bao phõ di»n t½ch công ÷ñc chia th nh nhi·u mæ h¼nh b i to¡n con tòy thuëc v o c¡c ti¶u ch½ nh÷: bao phõ 100% di»n t½ch vîi sè l÷ñng c£m bi¸n ½t nh§t [1922], tèi a hâa di»n t½ch bao phõ vîi sè l÷ñng c£m bi¸n cho tr÷îc, v.v.. Ngo i ra, trong méi mæ h¼nh l¤i câ thº chia th nh nhi·u mæ h¼nh kh¡c nhau khi th¶m v o c¡c ti¶u ch½ kh¡c nhau nh÷: c£m bi¸n còng lo¤i, c£m bi¸n kh¡c lo¤i, c£m bi¸n t¾nh, c£m bi¸n ëng, v.v. Khi th¶m c¡c ti¶u ch½ v o tøng mæ h¼nh b i to¡n th¼ vi»c triºn khai m¤ng công kh¡c nhau. N«m 2002, Andrew v c¡c cëng sü [23] ¢ ti¸p cªn theo h÷îng triºn khai c¡c nót c£m bi¸n º tèi ÷u hâa di»n t½ch bao phõ cõa c¡c c£m bi¸n. C¡c mi·n ÷ñc thi¸t k¸ sao cho nót m¤ng ÷ñc ©y xa khäi ch÷îng ng¤i vªt ho°c c¡c nót m¤ng kh¡c, k²o gi¢n vòng bao phõ di»n t½ch cõa to n m¤ng. Nghi¶n cùu n y gñi mð nhi·u h÷îng ph¡t triºn cho chõ · bao phõ di»n t½ch trong m¤ng. Sau â, Y. Zou [2428] ¢ · xu§t thuªt to¡n lüc ©y £o (Virtual Force Algorithm - VFA) º tèi ÷u hâa và tr½ triºn khai c¡c nót c£m bi¸n. B¶n c¤nh â, [2931] công ¢ · cªp ¸n b i to¡n cüc tiºu sè l÷ñng c£m bi¸n c¦n sû döng vîi r ng buëc bao phõ 100% di»n t½ch cõa mi·n c¦n quan s¡t. Trong lîp c¡c b i to¡n bao phõ di»n t½ch c¡c t¡c gi£ tr÷îc â mîi ch¿ · cªp ¸n v§n · t¼m sè l÷ñng c£m bi¸n nhä nh§t tr¶n méi ìn và di»n t½ch sao cho câ thº bao phõ to n bë vòng c¦n gi¡m s¡t. N«m 2013, Yourim Yoon v cëng sü [32] ¢ chùng minh b i to¡n cüc ¤i di»n t½ch bao phõ trong WSNs khæng çng nh§t l thuëc lîp b i to¡n NP-khâ. Cho tr÷îc sè l÷ñng c¡c c£m bi¸n câ b¡n k½nh kh¡c nhau, c¦n t¼m và tr½ cho méi c£m bi¸n sao cho di»n t½ch bao phõ cõa chóng tr¶n mët mi·n di»n t½ch cö thº l lîn nh§t. ë bao phõ, hay cán gåi l mi·n c£m bi¸n, ÷ñc ành ngh¾a l di»n t½ch cõa h¼nh trán câ t¥m t¤i và tr½ °t c£m bi¸n, b¡n k½nh b¬ng b¡n k½nh c£m bi¸n. T¡c gi£ cho r¬ng khæng thº gi£i quy¸t v§n · n y b¬ng thuªt to¡n ìn ành nh÷ thuªt to¡n circle packing [11] bði mi·n bao phõ cõa méi c£m bi¸n l kh¡c nhau. B¶n c¤nh â, t¡c gi£ công ch¿ ra ¥y l mët d¤ng cõa b i to¡n phõ tªp (set cover) n¶n l b i to¡n NP-khâ. V¼ vªy, t¡c gi£ [32] ti¸p cªn theo ph÷ìng ph¡p gi£i x§p x¿ v · xu§t gi£i thuªt di truy·n º gi£i b i to¡n n y. Trong thuªt gi£i di truy·n ÷ñc · xu§t trong [32], c¡c c¡ thº ÷ñc biºu di¹n l mët m£ng c¡c tåa ë, méi ph¦n tû cõa m£ng cho bi¸t và tr½ cõa c£m bi¸n t÷ìng ùng tr¶n thüc t¸. C¡c c£m bi¸n ÷ñc sp thù tü theo b¡n k½nh. ë th½ch nghi cõa c¡ thº X l di»n t½ch bao phõ (coA) cõa c¡c c£m bi¸n vîi và tr½ m X biºu di¹n ÷ñc t½nh theo ph÷ìng ph¡p Monte Carlo. Þ t÷ðng cõa ph÷ìng ph¡p n y l sinh ng¨u nhi¶n L iºm v kiºm tra xem iºm â câ thuëc mi·n bao phõ 3
cõa c£m bi¸n n o hay khæng. T¡c gi£ [32] ¢ ÷a ra 4 phi¶n b£n nh÷ sau: Phi¶n b£n ¦u ti¶n - PGA: PGA thüc hi»n óng tøng b÷îc nh÷ n¶u ð tr¶n v gi¡ trà L = 100000 ÷ñc giú nguy¶n qua 1000 th¸ h». Phi¶n b£n thù hai - MGA: MGA c£i thi»n thíi gian ch¤y b¬ng c¡ch t«ng d¦n gi¡ trà L. Ban ¦u L = 10000 v cù sau 100 th¸ h» th¼ gi¡ trà n y t«ng th¶m 10000. So vîi PGA, th¼ MGA nhanh hìn g¦n 2 l¦n m ch§t l÷ñng líi gi£i v¨n ÷ñc giú nguy¶n. Phi¶n b£n thù ba - OPTGA: OPTGA ÷ñc ÷a ra º n¥ng cao ch§t l÷ñng líi gi£i. Vîi c¡ch m¢ hâa tr¶n ¥y, khi thay êi và tr½ cõa c¡c gene biºu di¹n tåa ë cõa c¡c c£m bi¸n còng lo¤i th¼ líi gi£i khæng thay êi. Ng÷íi ta gåi ¥y l hi»n t÷ñng kh¡c kiºu gene nh÷ng còng kiºu h¼nh. Tçn t¤i n1 !n2 ! . . . nk ! c¡ thº còng biºu di¹n mët líi gi£i vîi ni , i = 1..k l sè l÷ñng c£m bi¸n lo¤i i. Khi â, khæng gian kiºu gene v khæng gian kiºu h¼nh khæng çng nh§t. Do vªy, to¡n tû di truy·n, °c bi»t l ph²p lai gh²p, tä ra khæng hi»u qu£. OPTGA khc phöc i·u n y b¬ng c¡ch thüc ph²p hi»n chu©n hâa Hungarian [33] cho cha thù 2 trong méi c°p cha mµ tr÷îc khi lai gh²p. Vi»c chu©n hâa n y s³ sp x¸p l¤i thù tü c¡c gene trong cha 2 sao cho kho£ng c¡ch vîi cha 1 l nhä nh§t. Kho£ng c¡ch n y ÷ñc ành ngh¾a nh÷ sau: X n D= d(s1i , s2i ), (1) i=1 vîi s1i = (x1i , yi1 ), s2i = (x2i , yi2 ) l¦n l÷ñt l ph¦n tû thù i trong cha 1, cha 2 v d(s1i , s2i ) l kho£ng c¡ch Euclidean giúa hai c£m bi¸n câ tåa ë s1i , s2i . OPTGA công t«ng d¦n gi¡ trà L nh÷ MGA. K¸t qu£ cho th§y OPTGA câ thíi gian ch¤y t÷ìng ÷ìng MGA nh÷ng ch§t l÷ñng líi gi£i l¤i tèt hìn nhi·u. Phi¶n b£n thù t÷ - OPTHGA: OPTHGA k¸t hñp OPTGA vîi thuªt to¡n VFA (Virtual Force Algorithm) [26] nh÷ mët ph÷ìng ph¡p t¼m ki¸m àa ph÷ìng cho ch§t l÷ñng líi gi£i tèt nh§t. Theo â, méi c¡ thº sau khi ët bi¸n s³ ÷ñc ti¸n h nh VFA. Thuªt to¡n n y ÷a ra 2 kh¡i ni»m: lüc ©y v lüc hót giúa hai c£m bi¸n. Þ t÷ðng l khi mi·n bao phõ cõa hai c£m bi¸n chçng l¶n nhau th¼ giúa chóng tçn t¤i mët lüc ©y, ng÷ñc l¤i tçn t¤i lüc hót. Düa v o gi¡ trà lüc ©y công nh÷ lüc hót cõa mët c£m bi¸n so vîi c¡c c£m bi¸n cán l¤i m và tr½ cõa nâ ÷ñc i·u ch¿nh phò hñp. ¥y l phi¶n b£n tèt nh§t trong [32] c£ v· thíi gian thüc hi»n, ch§t l÷ñng líi gi£i công nh÷ sü ên ành. Tuy nhi¶n, ë phùc t¤p cõa OPTHGA v¨n l O(nL) vîi L n (n l sè l÷ñng c£m bi¸n v L l sè iºm gieo theo ph÷ìng ph¡p Monter Carlo). Ngay vîi bë dú li»u nhä nh§t ch¿ câ 17 c£m bi¸n m OPTHGA v¨n c¦n ¸n g¦n 6 phót mîi ÷a ra ÷ñc líi gi£i. Vîi bë dú li»u lîn nh§t (130 c£m bi¸n), thíi gian l hìn 42 phót. K¸t qu£ n y ÷ñc ÷a ra tr¶n m¡y t½nh sû döng ch½p Intel Xeon CPU 2.4 GHz. M°c dò c¡c k¸t qu£ cho th§y líi gi£i thu ÷ñc l kh¡ tèt xong v¨n ch÷a ph£i tèi ÷u. D¹ th§y r¬ng, khi mi·n bao phõ cõa c¡c c£m bi¸n c ng ½t chçng l¶n nhau (overlap) v ½t ra ngo i bi¶n cõa mi·n gi¡m s¡t A th¼ di»n t½ch bao phõ cõa chóng 4
tr¶n mi·n A c ng lîn. Düa tr¶n lªp luªn â, inh Thà H Ly [34] còng c¡c cëng sü (câ t¡c gi£ luªn ¡n tham gia) ¢ · xu§t mët h m th½ch nghi mîi sû döng kh¡i ni»m ë chçng (Olap) v ùng döng kh¡i ni»m n y º t½nh ë th½ch nghi cõa c¡ thº. Þ t÷ðng l thay v¼ so s¡nh trüc ti¸p c¡c c¡ thº theo di»n t½ch bao phõ tr¶n mi·n A nh÷ trong [32], IGA s³ ti¸n h nh so s¡nh gi¡n ti¸p thæng qua ë chçng. X²t c¡ thº S = (s1 , s2 . . . sn ), ë chçng Olap cõa S ÷ñc ành ngh¾a nh÷ sau: n n 4 ! X X X Olap(S) = overlap(si , sj ) + overlap(si , bm ) , (2) i=1 j=i+1 m=1 trong â, overlap(si , sj ) l ë chçng giúa mi·n bao phõ cõa hai c£m bi¸n si , sj :  0  khi d(si , sj ) ≥ rsi + rsj overlap(si , sj ) = γ(rsi + rsj − d(si , sj )) khi