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

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.
Nội dung trích xuất từ tài liệu:
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Ë GIO DÖC V€ €O T„O TR×ÍNG „I HÅC BCH KHOA H€ NËI NGUY™N THÀ H„NH MËT SÈ THUŠT TON METAHEURISTICGIƒ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 LUŠN N TI˜N Sž KHOA HÅC MY TNH H Nëi - 2019 BË GIO DÖC V€ €O T„O TR×ÍNG „I HÅC BCH KHOA H€ NËI NGUY™N THÀ H„NH MËT SÈ THUŠT TON METAHEURISTICGIƒ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 Ngnh : Khoa håc m¡y t½nh M¢ sè : 9480101 LUŠN N TI˜N Sž KHOA HÅC MY TNH NG×ÍI H×ÎNG DˆN KHOA HÅC: 1. PGS.TS Huýnh Thà Thanh B¼nh 2. PGS.TS Nguy¹n ùc Ngh¾a H Nëi - 2019Líi cam oan Nghi¶n cùu sinh cam oan luªn ¡n ny l cæng tr¼nh nghi¶n cùu cõa ch½nhm¼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öngthæng tin tr½ch d¨n tø nhi·u nguçn tham kh£o kh¡c nhau v c¡c thæng tin tr½chd¨n ÷ñc ghi rã nguçn gèc. C¡c sè li»u, k¸t qu£ trong luªn ¡n l trung thüc vch÷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£ nokh¡c. H Nëi, ngy 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 iiLíi c£m ìn Líi ¦u ti¶n, tæi xin by tä láng bi¸t ìn s¥u sc tîi c¡c th¦y cæ gi¡o h÷îngd¨n, PGS.TS Huýnh Thà Thanh B¼nh v PGS.TS Nguy¹n ùc Ngh¾a , ¢ ànhh÷îng khoa håc v tªn t¥m gióp ï, ch¿ b£o trong suèt qu¡ tr¼nh hon thnhluªn ¡n t¤i tr÷íng ¤i håc B¡ch Khoa H Nëi. Tæi xin ch¥n thnh 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¡chkhoa H Nëi ¢ t¤o i·u ki»n thuªn lñi nh§t º tæi hon thnh ch÷ìng tr¼nhhå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 thnh c£m ìn Ban gi¡m hi»u tr÷íng ¤i håc Ph÷ìng æng, tªpthº c¡n bë, gi£ng vi¶n Khoa cæng ngh» thæng tin v truy·n thæng nìi nghi¶ncù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 hon thnh luªn ¡n ny. Cuèi còng, tæi ch¥n thnh by tä láng c£m ìn tîi gia ¼nh ¢ ki¶n tr¼, chias´, ëng vi¶n nghi¶n cùu sinh trong suèt qu¡ tr¼nh håc tªp v hon thnh luªn¡n ny. H Nëi, ngy 05 th¡ng 11 n«m 2019 Nghi¶n cùu sinh Nguy¹n Thà H¤nh iiiMÖC LÖCBƒNG THUŠT NGÚ VI˜T TT viiDANH SCH BƒNG ixDANH SCH HœNH V“ xiMÐ †U 11 CÌ SÐ LÞ THUY˜T 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 Bi to¡n bao phõ trong m¤ng c£m bi¸n khæng d¥y . . . . . 22 1.3 Bi to¡n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.3.1 Bi to¡n tèi ÷u li¶n töc . . . . . . . . . . . . . . . . . . . . 26 1.3.2 Bi to¡n tèi ÷u tê hñp . . . . . . . . . . . . . . . . . . . . . 27 1.3.3 Ph÷ìng ph¡p gi£i bi to¡n tèi ÷u . . . . . . . . . . . . . . . 28 1.4 K¸t luªn ch÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 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 38 iv 2.1 Ph¡t biºu bi 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753 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 C R€NG BUËC CH×ÎNG NG„I VŠT. 76 3.1 Ph¡t biºu bi 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 . . . . . . . . . . . . . . . . . ...