Một số thuật toán metaheuristic 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

Nội dung tài liệu: Một số thuật toán metaheuristic 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

1. 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 METAHEURISTIC 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 Ng nh : Khoa håc m¡y t½nh M¢ sè : 9480101 TÂM TT LUŠN N TI˜N Sž KHOA HÅC MY TNH H Nëi - 2019
2. Cæng tr¼nh ÷ñc ho n th nh t¤i: Tr÷íng ¤i håc B¡ch khoa H Nëi 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 Ph£n bi»n 1: PGS.TS Ngæ Hçng Sìn Ph£n bi»n 2: PGS.TS Ngæ Th nh Long Ph£n bi»n 3: PGS.TS Nguy¹n Long Giang Luªn ¡n ÷ñc b£o v» tr÷îc Hëi çng ¡nh gi¡ luªn ¡n ti¸n s¾ c§p Tr÷íng håp t¤i Tr÷íng ¤i håc B¡ch khoa H Nëi V o hçi . . . . . . gií, ng y . . . th¡ng . . . n«m . . . . . . . . . Câ thº t¼m hiºu luªn ¡n t¤i th÷ vi»n: 1. Th÷ vi»n T¤ Quang Bûu - Tr÷íng HBK H Nëi 2. Th÷ vi»n Quèc gia Vi»t Nam
3. DANH MÖC CC CÆNG TRœNH ‚ CÆNG BÈ CÕA LUŠN N 1. Nguyen Thi Hanh, Nguyen Hai Nam, Huynh Thi Thanh Binh, 2016, Swarm Optimiza- tion Algorithms for Maximizing Area Coverage in Wireless Sensor Networks, Proceed- ings of SAI Intelligent Systems Conference (IntelliSys), pp. 1145-1151. 2. Nguyen Thi Hanh, Le Quoc Tung, Nguyen Thanh Hai, Huynh Thi Thanh Binh, Ernest Kurniawan, 2016, Connectivity Optimization Problem in Vehicular Mobile Wireless Sensor Networks, International Conference on Computational Intelligence and Cyber- netics, pp. 55-61. 3. Nguyen Thi Hanh, Phan Hong Hanh, Huynh Thi Thanh Binh, Nguyen Duc Nghia, 2016, Heuristic Algorithm for Target Coverage with Connectivity Fault-tolerance Problem in Wireless Sensor Networks, Conference on Technologies and Applications of Artificial Intelligence (TAAI), pp. 235-240. 4. Nguyen Thi Hanh, Nguyen Phi Le, Phan Thanh Tuyen, Ernest Kurniawan, Yusheng Ji, Huynh Thi Thanh Binh, 2018, Node Placement for Target Coverage and Network Connectivity in WSNs with Multiple Sinks, IEEE Consumer Communications and Net- working Conference - CCNC, Las Vegas, NV, USA, pp. 1-6. 5. Huynh Thi Thanh Binh, Nguyen Thi Hanh, La Van Quan, Nilanjan Dey, 2018, Im- proved Cuckoo Search and Chaotic Flower Pollination Algorithms for Maximizing Area Coverage in Wireless Sensor Networks, Neural Computing and Applications, October 2018, Volume 30, Issue 7, pp. 23052317, (SCI-E Index, IF: 4.664). 6. Nguyen Thi Hanh, Huynh Thi Thanh Binh, Nguyen Xuan Hoai, Marimuthu Swami Palaniswami, 2019, An Efficient Genetic Algorithm for Maximizing Area Coverage in Wireless Sensor Networks, Journal Information Sciences (accepted)-2019. , (SCI-E In- dex, IF: 5.524). 7. Nguyen Thi Hanh, Huynh Thi Thanh Binh, Nguyen Van Son, Phan Ngoc Lan, 2019, Minimal Node Placement for Ensuring Target Coverage with Network Connectivity and Fault Tolerance Constraints in Wireless Sensor Networks, 2019 IEEE Congress on Evolutionary Computation Conference (CEC 2019), pp.2924-2931. 8. Nguyen Phi Le, Nguyen Thi Hanh, Nguyen Tien Khuong, Huynh Thi Thanh Binh, Yusheng Ji, 2019, Node placement for connected target coverage in wireless sensor networks with dynamic sinks, Journal Pervasive and Mobile Computing, Volume 59, pp. 1-21, 2019 (SCI, IF: 2.769). 9. Huynh Thi Thanh Binh, Nguyen Thi Hanh, La Van Quan, Nguyen Duc Nghia, Nilanjan Dey, 2019, Metaheuristics for Maximization of Obstacles Constrained Area Coverage in Heterogeneous Wireless Sensor Networks, Journal Applied Soft Computing (SCI, IF: 4.8) (Accepted).
4. GIÎI THI›U 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 b­t 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 câ r§t nhi·u ùng döng trong c¡c l¾nh vüc cõa íi sèng nh÷ 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,v.v. [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 kh­c 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. V¼ vªy, y¶u c¦u °t ra 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 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 1
5. khæng câ thuªt to¡n thíi gian a thùc º gi£i chóng, ngo¤i trø P = NP . 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. Möc ti¶u nghi¶n cùu cõa luªn ¡n Möc ti¶u thù nh§t cõa luªn ¡n l nghi¶n cùu v· m¤ng c£m bi¸n khæng d¥y, v§n · bao phõ, k¸t nèi v chàu léi trong m¤ng c£m bi¸n khæng d¥y. °c bi»t, luªn ¡n i s¥u gi£i quy¸t c¡c v§n · bao phõ: cüc ¤i hâa di»n t½ch bao phõ trong m¤ng c£m bi¸n khæng d¥y khæng çng nh§t v tèi thiºu hâa sè l÷ñng c¡c nót triºn khai º bao phõ t§t c£ c¡c è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 câ sû döng c¡c iºm thu ph¡t di ëng. Cö thº, c¡c b i to¡n ÷ñc kh£o s¡t trong luªn ¡n: • B i to¡n cüc ¤i hâa bao phõ di»n t½ch trong m¤ng c£m bi¸n khæng d¥y khæng çng nh§t ÷ñc · xu§t bði Yourim Yoon [19] v · xu§t c¡c thuªt to¡n metaheuristic º c£i thi»n ë bao phõ vòng triºn khai m¤ng c£m bi¸n khæng d¥y v gi£m thiºu thíi gian t½nh to¡n v ë l»ch chu©n v· ë bao phõ ¤t ÷ñc cõa c¡c gi£i thuªt · xu§t. • º phò hñp vîi thüc ti¹n, t¡c gi£ ph¡t triºn b i to¡n tèi a hâa bao phõ di»n t½ch trong m¤ng c£m bi¸n khæng d¥y khæng çng nh§t trong [19] câ xem x²t ¸n y¸u tè ch÷îng ng¤i vªt l h¼nh chú nhªt. T¡c gi£ · xu§t c¡c thuªt to¡n metaheuristic º gi£i quy¸t b i to¡n · xu§t. º ¡nh gi¡ ë tèt cõa gi£i thuªt · xu§t t¡c gi£ nghi¶n cùu c¡c c¡ch x¥y düng kàch b£n m¤ng v dú li»u thüc nghi»m cho tøng kàch b£n m¤ng mët c¡ch kh¡ch quan thº hi»n ÷ñc h¦u h¸t c¡c tr÷íng hñp x£y ra trong c¡c b i to¡n n y. • Vîi v§n · bao phõ èi t÷ñng, luªn ¡n nghi¶n cùu hai b i to¡n l 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 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 2
6. d¥y câ sû döng c¡c iºm thu ph¡t di ëng. T¡c gi£, nghi¶n cùu v · xu§t c¡c thuªt to¡n heuristic º gi£i quy¸t c¡c mæ h¼nh b i to¡n n y v x¥y düng c¡c kàch b£n m¤ng v dú li»u thüc nghi»m theo tøng ti¶u ch½ x¥y düng m¤ng º ¡nh gi¡ ë tèt cõa gi£i thuªt · xu§t. Möc ti¶u thù hai cõa luªn ¡n l nghi¶n cùu c¡c kÿ thuªt º gi£i quy¸t lîp c¡c b i to¡n ÷ñc luªn ¡n quan t¥m ÷ñc tr¼nh b y ð tr¶n. Bði v¼, c¡c b i to¡n ÷ñc luªn ¡n nghi¶n cùu ·u l c¡c b i to¡n thuëc lîp NP-khâ. Do â, t¡c gi£ ti¸p cªn theo ph÷ìng ph¡p gi£i x§p x¿ sû döng c¡c gi£i thuªt heuristic v metaheuristic º gi£i quy¸t. Möc ti¶u thù ba cõa luªn ¡n l nghi¶n cùu c¡c ph÷ìng ph¡p x¥y düng kàch b£n m¤ng, x¥y düng c¡c bë dú li»u v c¡c ph÷ìng ph¡p ¡nh gi¡ thüc nghi»m mët c¡ch kh¡ch quan thº hi»n ÷ñc h¦u h¸t c¡c tr÷íng hñp x£y ra trong c¡c mæ h¼nh b i to¡n m luªn ¡n quan t¥m gi£i quy¸t. Ph÷ìng ph¡p nghi¶n cùu Ph÷ìng ph¡p nghi¶n cùu düa tr¶n nghi¶n cùu lþ thuy¸t, ph¥n t½ch t i li»u, mæ h¼nh to¡n håc v thüc nghi»m º ¡nh gi¡ c¡c gi£i thuªt · xu§t so s¡nh vîi c¡c gi£i thuªt · xu§t tr÷îc â º gi£i quy¸t b i to¡n. Tø â, câ thº · xu§t c¡c b i to¡n v c¡ch gi£i quy¸t b i to¡n cho phò hñp vîi thüc t¸ triºn khai m¤ng c£m bi¸n khæng d¥y. Ph¤m vi nghi¶n cùu Nghi¶n cùu b i to¡n bao phõ trong m¤ng c£m bi¸n khæng d¥y. C¡c y¸u tè £nh h÷ðng ¸n v§n · bao phõ cõa m¤ng c£m bi¸n khæng d¥y. C¡c gi£i thuªt metaheuristic. C¡c nghi¶n cùu li¶n quan trong b i to¡n tèi ÷u hâa bao phõ di»n t½ch v bao phõ èi t÷ñng. Nghi¶n cùu, têng hñp, ph¥n t½ch v · xu§t (ho°c c£i ti¸n) mæ h¼nh cüc ¤i bao phõ di»n t½ch vîi sè l÷ñng c£m bi¸n cho tr÷îc trong m¤ng khæng çng nh§t v tèi ÷u bao phõ èi t÷ñng nh¬m möc ½ch tèi thiºu hâa sè l÷ñng c¡c nót sû döng £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. X¥y düng c¡c kàch b£n thüc nghi»m º ¡nh gi¡ ë tèt cõa mæ h¼nh b i to¡n · xu§t v gi£i thuªt · xu§t gi£i quy¸t cho tøng mæ h¼nh b i to¡n. So s¡nh ¡nh gi¡ k¸t qu£ thüc nghi»m theo c¡c ti¶u ch½ x¥y düng m¤ng v so s¡nh vîi c¡c nghi¶n cùu ¢ cæng bè tr÷îc â. C¡c âng gâp cõa luªn ¡n • Vîi 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: · xu§t c¡c gi£i thuªt metaheuristic º c£i thi»n ë tèt 3
7. v· vòng bao phõ, gi£m thiºu thíi gian t½nh to¡n v ë l»ch chu©n so vîi c¡c nghi¶n cùu tr÷îc â. Chi ti¸t cõa c¡c gi£i thuªt · xu§t ÷ñc tr¼nh b y trong ch÷ìng 2. • º phò hñp vîi thüc t¸ triºn khai m¤ng, t¡c gi£ · xu§t mæ h¼nh 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â xem x²t ¸n mi·n triºn khai m¤ng câ ch÷îng ng¤i vªt. Sau â, · xu§t c¡c thuªt to¡n metaheuristic º gi£i quy¸t b i to¡n. º ¡nh gi¡ ë tèt cõa mæ h¼nh v cõa gi£i thuªt t¡c gi£ · xu§t c¡c ti¶u ch½ x¥y düng kàch b£n thüc nghi»m ¡nh gi¡ sü £nh h÷ðng cõa tøng èi t÷ñng ¦u v o cõa b i to¡n ¸n k¸t qu£ ¦u ra cõa b i to¡n. Hìn núa, t¡c gi£ · xu§t c¡ch lüa chån tham sè cho tøng thuªt to¡n º thu ÷ñc líi gi£i tèt nh§t. C¡c k¸t qu£ n y ÷ñc tr¼nh b y trong ch÷ìng 3. • Li¶n quan ¸n v§n · bao phõ èi t÷ñng, t¡c gi£ · xu§t hai b i to¡n l 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 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. C£ hai b i to¡n · xu§t tr¶n ·u ái häi tèi thiºu sè l÷ñng nót c£m bi¸n v nót chuyºn ti¸p çng thíi £m b£o c¡c i·u ki»n n¶u ra trong tøng b i to¡n. Sau â, t¡c gi£ · xu§t c¡c thuªt to¡n heuristic º gi£i quy¸t hai b i to¡n n y. Trong méi b i to¡n t¡c gi£ · xu§t c¡c ti¶u ch½ ¡nh gi¡ ch§t l÷ñng cõa m¤ng c£m bi¸n v ti¸n h nh x¥y düng c¡c kàch b£n m¤ng theo tøng ti¶u ch½ ¡nh gi¡. Chi ti¸t v· mæ h¼nh c¡c b i to¡n v c¡c gi£i thuªt · xu§t ÷ñc tr¼nh b y trong ch÷ìng 4. C§u tróc cõa luªn ¡n Mð ¦u: Tr¼nh b y þ ngh¾a, möc ½ch nghi¶n cùu cõa luªn ¡n, ph÷ìng ph¡p nghi¶n cùu, ph¤m vi nghi¶n cùu, c¡c âng gâp cõa luªn ¡n v c§u tróc cõa luªn ¡n. Ch÷ìng 1: Cì sð lþ thuy¸t, tr¼nh b y cì sð lþ thuy¸t m¤ng c£m bi¸n khæng d¥y, têng quan t¼nh h¼nh nghi¶n cùu trong v ngo i n÷îc, cì sð lþ thuy¸t b i to¡n tèi ÷u. Ch÷ìng 2: 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 · xu§t bði [19]. Ch÷ìng 3: 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 trong vòng triºn khai m¤ng câ ch÷îng ng¤i vªt. Ch÷ìng 4: B i to¡n tèi ÷u bao phõ èi t÷ñng £m b£o k¸t nèi, 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. Cuèi còng, ph¦n k¸t luªn ¡nh gi¡ nhúng k¸t qu£ ¤t ÷ñc trong luªn ¡n v 4
8. ÷a ra ph÷ìng h÷îng ph¡t triºn ti¸p theo. CH×ÌNG 1. CÌ SÐ LÞ THUY˜T 1.1. M¤ng c£m bi¸n khæng d¥y Trong ph¦n n y, t¡c gi£ tr¼nh b y c¡c kh¡i ni»m v· c£m bi¸n, nót c£m bi¸n, m¤ng c£m bi¸n khæng d¥y (ành ngh¾a m¤ng c£m bi¸n khæng d¥y, mët sè ki¸n tróc m¤ng c£m bi¸n khæng d¥y, ùng döng cõa m¤ng c£m bi¸n khæng d¥y), nhúng th¡ch thùc trong m¤ng c£m bi¸n khæng d¥y 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 1.2.1. Mæ h¼nh bao phõ cõa c£m bi¸n Bang Wang [22] ¢ ÷a ra 4 mæ h¼nh c£m bi¸n thæng döng sau: Mæ h¼nh qu¤t nhà ph¥n, mæ h¼nh ¾a nhà ph¥n, mæ h¼nh suy gi£m v mæ h¼nh suy gi£m rót gån. 1.2.2. B i to¡n bao phõ trong m¤ng c£m bi¸n khæng d¥y Trong b i nghi¶n cùu têng quan v o n«m 2010, Bang Wang ¢ chia th nh ba d¤ng sau ¥y: B i to¡n bao phõ èi t÷ñng (Target Coverage Problem), b i to¡n bao phõ di»n t½ch (Area Coverage Problem), b i to¡n bao phõ bi¶n (Barrier Coverage Problem). 1.4. B i to¡n tèi ÷u Trong ph¦n n y, t¡c gi£i tr¼nh b y mët sè lþ thuy¸t cì b£n v· b i to¡n tèi ÷u (b i to¡n tèi ÷u li¶n töc, b i to¡n tèi ÷u tê hñp) v ph÷ìng ph¡p ti¸p cªn º gi£i b i to¡n tèi ÷u. C¡c ki¸n thùc n y l n·n t£ng º gi£i quy¸t c¡c v§n · ÷ñc tr¼nh b y trong luªn ¡n. 1.5. K¸t luªn ch÷ìng Trong ch÷ìng n y, t¡c gi£ tr¼nh b y mët sè kh¡i ni»m cì b£n mang t½nh têng quan v· m¤ng c£m bi¸n khæng d¥y v c¡c b i to¡n li¶n quan. Nhúng kh¡i ni»m n y s³ ÷ñc sû döng th÷íng xuy¶n ð ch÷ìng sau. 5
9. CH×ÌNG 2. 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 Trong ch÷ìng n y, t¡c gi£ s³ tr¼nh b y 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 vîi sè l÷ñng c£m bi¸n cho tr÷îc ÷ñc ph¡t biºu bði Yourim trong [19]. 2.1. Ph¡t biºu b i to¡n 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 · xu§t bði Y.Yoon trong [19]. B i to¡n ÷ñc ph¡t biºu nh÷ sau: Vòng gi¡m s¡t A câ k½ch th÷îc W × H v cho tr÷îc sè l÷ñng c¡c c£m bi¸n câ b¡n k½nh kh¡c nhau. B i to¡n °t ra l t¼m và tr½ °t c¡c c£m bi¸n tr¶n mi·n A sao cho di»n t½ch bao phõ cõa t§t c£ c¡c c£m bi¸n tr¶n mi·n A (k½ hi»u: coA) l lîn nh§t. Gi£ sû câ n c¡c nót c£m bi¸n, trong â c£m bi¸n thù i câ b¡n k½nh c£m bi¸n l r vîi nhi»m vö c£m nhªn v thu thªp thæng tin tø èi t÷ñng trong si vòng c£m bi¸n v b¡n k½nh truy·n l r câ nhi»m vö k¸t nèi trong to n m¤ng, ci sao cho rc = 2 × rs [40]. • M¤ng c£m bi¸n khæng d¥y khæng çng nh§t ÷ñc ành ngh¾a l mët m¤ng sû döng c¡c c£m bi¸n câ b¡n k½nh kh¡c nhau. • ë 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 nót c£m bi¸n, b¡n k½nh b¬ng b¡n k½nh c£m bi¸n. Mæ h¼nh to¡n håc cõa b i to¡n t¼m cüc ¤i di»n t½ch bao phõ cõa m¤ng c£m bi¸n khæng d¥y khæng çng nh§t vîi sè l÷ñng c£m bi¸n cho tr÷îc ÷ñc ph¡t biºu nh÷ sau: n ! T¼m cüc ¤i [ \ (2.1) coA = area cri (xi; yi) A i=1 vîi i·u ki»n x = (xi; yi) 2 A; trong â l h¼nh trán câ t¥m t¤i v b¡n k½nh . K½ hi»u cri (xi; yi) (xi; yi) ri area(X) l di»n t½ch cõa mi·n X. B i to¡n n y l mët d¤ng cõa b i to¡n phõ tªp (set cover) v ¢ ÷ñc chùng minh l b i to¡n NP-khâ trong [19]. Trong ch÷ìng n y t¡c gi£ ti¸p cªn theo ph÷ìng ph¡p gi£i g¦n óng v · xu§t gi£i thuªt metaheuristic º gi£i quy¸t b i to¡n n y. 6
10. 2.2. Gi£i thuªt · xu§t Trong ph¦n n y t¡c gi£ · xu§t mët sè gi£i thuªt metaheuristic º gi£i b i to¡n: gi£i thuªt b y  n thæng minh (ICS, DPSO, CFPA); gi£i thuªt di truy·n c£i ti¸n (MIGA). 2.2.1. Gi£i thuªt t¼m ki¸m chim cuckoo c£i ti¸n Gi£i thuªt t¼m ki¸m chim cuckoo c£i ti¸n - Improved Cuckoo Search (ICS) ÷ñc ph¡t triºn tø gi£i thuªt Cuckoo Search (CS) ÷ñc · xu§t bði Yang v Deb [81]. T÷ t÷ðng ch½nh cõa thuªt to¡n ÷ñc l§y c£m hùng tø thâi quen sinh s£n cõa lo i chim Cuckoo. Lo i chim n y °t trùng cõa m¼nh v o tê cõa nhúng lo i chim kh¡c (chim chõ). Chim chõ câ thº ph¡t hi»n ra sü x¥m nhªp cõa nhúng qu£ trùng l¤. N¸u ph¡t hi»n ÷ñc, nâ s³ n²m qu£ trùng i ho°c tø bä tê v x¥y düng tê mîi theo x¡c su§t p cho tr÷îc. Düa tr¶n gi£i thuªt CS, t¡c gi£ · xu§t gi£i thuªt c£i ti¸n ICS công bao gçm bèn giai o¤n nh÷ gi£i thuªt CS l : biºu di¹n c¡ thº, khði t¤o qu¦n thº, t½nh h m th½ch nghi, cªp nhªt c¡ thº. º t¤o ra líi gi£i mîi, ICS sû döng Le'vy flight [82] º mæ phäng l¤i qu¡ tr¼nh chim Cuckoo t¼m ki¸m tê cõa chim chõ. çng thíi, nâ công ÷ñc sû döng º thüc hi»n nhúng Le'vy fight (thº hi»n trong cæng thùc (2.4)) cho c¡c h¤t ph§n thº hi»n trong thuªt to¡n CFPA ÷ñc tr¼nh b y ð ph¦n ti¸p theo. Trong thuªt to¡n CS c¡c tham sè cõa thuªt to¡n ·u l c¡c h¬ng sè v ÷ñc cè ành qua c¡c th¸ h». Tuy nhi¶n, n¸u cè ành nh÷ vªy s³ g¥y ra mët sè b§t lñi trong qu¡ tr¼nh t¼m ki¸m, c¡c gi£i ph¡p mîi ÷ñc t¤o ra câ thº s³ bà ©y ra ngo i khæng gian t¼m ki¸m ho°c vòng hùa hµn chùa líi gi£i tèi ÷u do k½ch th÷îc b÷îc nh£y qu¡ lîn, °c bi»t l khi sè th¸ h» t«ng l¶n. Ch½nh v¼ vªy, t¡c gi£ · xu§t i·u ch¿nh l¤i c¡c tham sè. Trong ICS ¢ thüc hi»n nhúng thay êi mët sè tham sè α v pa ÷ñc thº hi»n trong cæng thùc (2.5) v (2.6). Gi¡ trà cõa pa(t) v α(t) ÷ñc khði t¤o lîn trong nhúng th¸ h» ¦u ti¶n º t¤o ra khæng gian t¼m ki¸m rëng lîn. Sau â, chóng s³ ÷ñc gi£m d¦n º t«ng t¿ l» hëi tö v duy tr¼ c¡c gi£i ph¡p tèt trong qu¦n thº. Tr¶n thüc t¸, thæng tin v· qu£ trùng mîi s³ chàu £nh h÷ðng tø Le'vy flight v thæng tin v· nhúng l¦n sinh s£n tr÷îc â. Sü xu§t hi»n n y âng vai trá quan trång trong thuªt to¡n ICS v¼ nâ l m t«ng kh£ n«ng t¼m ki¸m c¡c líi gi£i mîi. Do â công gióp cho vi»c t¼m ki¸m và tr½ triºn khai c£m bi¸n tèt hìn. Sau khi nhªn ÷ñc mët líi gi£i mîi, câ hai kh£ n«ng s³ x£y ra: 1) N¸u chim chõ ph¡t hi»n ra sü x¥m nhªp cõa trùng l¤ (x¡c su§t ph¡t hi»n l pa), nâ s³ bä qu£ trùng chim â i ho°c ríi tê v x¥y düng tê mîi. 2) N¸u trùng chim Cuckoo khæng bà ph¡t hi»n th¼ trùng chim Cuckoo v trùng cõa chim chõ s³ còng c¤nh tranh º tçn t¤i. Tùc l qu£ trùng n o câ h m th½ch nghi tèt hìn s³ chi¸m l§y tê v lo¤i bä qu£ trùng cán l¤i. 7
11. 2.2.2. Gi£i thuªt Democratic PSO Gi£i thuªt Democratic PSO (DPSO) l§y þ t÷ðng tø thuªt to¡n PSO ÷ñc · xu§t trong [89]. Do â, DPSO công tr£i qua c¡c b÷îc cõa PSO l m¢ hâa c¡ thº, khði t¤o qu¦n thº, h m th½ch nghi v cªp nhªt c¡ thº. Trong DPSO câ sü c£i ti¸n trong qu¡ tr¼nh cªp nhªt c¡ thº v DPSO sû döng h m th½ch nghi OLap ÷ñc giîi thi»u trong [40]. Tuy nhi¶n, DPSO [89] ÷ñc sû döng º gi£i quy¸t cho b i to¡n n y khæng thº sû döng cæng thùc t½nh và tr½ v vªn tèc nh÷ trong PSO truy·n thèng v¼ trong DPSO sû döng th¶m v²c-tì democratic (cæng thùc (2.11), (2.12), (2.13)). Theo â, kinh nghi»m cõa t§t c£ c¡c c¡ thº, bao gçm c£ c¡c c¡ thº ùng t¤i và tr½ khæng tèt, ÷ñc sû döng º i·u h÷îng trong qu¡ tr¼nh cªp nhªt c¡ thº. Nâi c¡ch kh¡c, DPSO câ kh£ n«ng t¼m ki¸m rëng hìn gióp t«ng t½nh a d¤ng cõa qu¦n thº trong qu¡ tr¼nh t¼m ki¸m. 2.2.3. Gi£i thuªt thö ph§n cho hoa hén t¤p Thuªt to¡n thö ph§n cho hoa hén t¤p (Chaotic Flower Pollination Algorithm - CFPA) ÷ñc c£i ti¸n b¬ng c¡ch ¡p döng þ t÷ðng ch½nh cõa thuªt to¡n thö ph§n cho hoa (Flower Pollination Algorithm - FPA). N«m 2013, Yang v cëng sü l¦n ¦u ti¶n giîi thi»u v· FPA trong [90] º gi£i quy¸t c¡c b i to¡n tèi ÷u to n cöc. Cö thº, [90] ¢ ành ngh¾a hai c¡ch º ph¥n lo¤i qu¡ tr¼nh thö ph§n cho hoa tü thö ph§n (thö ph§n cöc bë) ho°c thö ph§n ch²o (thö ph§n to n cöc). Thuªt to¡n CFPA bao gçm ba b÷îc gièng nh÷ ICS. C¡c b÷îc m¢ hâa c¡ thº, khði t¤o qu¦n thº v t½nh ë th½ch nghi ÷ñc x¥y düng gièng nh÷ ICS. Ph¦n n y t¡c gi£ s³ tªp trung th£o luªn giai o¤n thö ph§n cõa CFPA. Qu¡ tr¼nh ti¸n hâa cõa CFPA ho n to n kh¡c so vîi ICS. Câ hai b÷îc ti¸n hâa ch½nh â l : thö ph§n to n cöc v thö ph§n cöc bë. Kh¡c vîi thuªt to¡n FPA nguy¶n thõy ch¿ sû döng ch§t li»u di truy·n cõa h¤t ph§n tèt nh§t, CFPA do t¡c gi£ · xu§t sû döng thæng tin cõa to n bë qu¦n thº º thüc hi»n c¡c ph²p thö ph§n. T÷ìng tü nh÷ ICS, CFPA công sû döng ph÷ìng ph¡p hi»u ch¿nh tham sè α(t); β(t) ÷ñc thº hi»n trong cæng thùc (2.15), (2.16), (2.17). Trong thö ph§n to n cöc, CFPA sû döng thæng tin cõa ph§n hoa tèt nh§t trong qu¦n thº hi»n t¤i. Ngo i ra thuªt to¡n cán sû döng âng gâp di truy·n cõa c£ qu¦n thº bði mët v²c-tì Democratic t ¤i di»n cho sü £nh h÷ðng cõa Di t§t c£ c¡c c¡ thº l¶n c¡ thº thù i ÷ñc thº hi»n trong cæng thùc (2.18). Möc ½ch cõa vi»c sûa êi n y l º c£i thi»n qu¡ tr¼nh t¼m ki¸n to n cöc - n¥ng cao ch§t l÷ñng líi gi£i. Nâ l m gi£m kh£ n«ng rìi v o cöc bë v mð rëng kh£ n«ng t¼m ki¸m cho CFPA. Sau khi thüc hi»n thö ph§n to n töc, c¡c c¡ thº hoa s³ ti¸n h nh qu¡ tr¼nh tü thö ph§n. Cuèi còng, t¡c gi£ · xu§t vi»c thay êi t¿ l» thö ph§n to n cöc v thö ph§n cöc bë theo thíi gian, thay cho vi»c chóng ÷ñc giú cè ành nh÷ trong phi¶n 8
12. b£n gèc cõa thuªt to¡n FPA. 2.2.4. Gi£i thuªt di truy·n c£i ti¸n Gi£i thuªt di truy·n - GA ÷ñc x¸p v o lîp thuªt to¡n ti¸n hâa vîi möc ½ch t¼m ra líi gi£i tèi ÷u ho°c g¦n tèi ÷u. GA th÷íng ÷ñc ¡p döng º gi£i c¡c b i to¡n thuëc lîp b i to¡n NP-Khâ. Nh÷ ¢ tr¼nh b y ð tr¶n b i to¡n n y ¢ ÷ñc chùng minh l b i to¡n NP-Khâ [19]. V¼ vªy, º n¥ng cao ch§t l÷ñng líi gi£i t¡c gi£ · xu§t mët gi£i thuªt di truy·n c£i ti¸n düa tr¶n gi£i thuªt IGA trong [40] l gi£i thuªt di truy·n tèt nh§t hi»n t¤i º gi£i quy¸t b i to¡n n y. Tuy nhi¶n, trong [40] l¤i sû döng mët ph÷ìng ph¡p t½nh x§p x¿ h m th½ch nghi l ë chçng cõa c¡c c£m bi¸n v c£m bi¸n vîi bi¶n tr¶n mi·n A gåi l Olap() vîi b¡n k½nh chçng. V¼ vªy, ph÷ìng ph¡p n y khæng £m b£o ÷ñc t½nh ch½nh x¡c v t½nh ên ành cõa h m th½ch nghi. Do â, trong nghi¶n cùu n y t¡c gi£ · xu§t mët Gi£i thuªt di truy·n c£i ti¸n IGA °t t¶n l MIGA bao gçm: · xu§t mët c¡ch t½nh ch½nh x¡c h m th½ch nghi düa v o ph÷ìng ph¡p t½nh t½ch ph¥n. Ph÷ìng ph¡p n y s³ £m b£o t½nh ên ành cõa líi gi£i thu ÷ñc khi so vîi c¡c ph÷ìng ph¡p t½nh g¦n óng º t½nh to¡n h m th½ch nghi nh÷ ph÷ìng ph¡p t½nh h m th½ch nghi düa v o ë chçng (Olap()) ÷ñc · xu§t bði [40]. Ngo i ra, t¡c gi£ · xu§t th¶m mët sè c£i ti¸n: khði t¤o qu¦n thº mîi, k¸t hñp sû döng hai to¡n tû lai gh²p (LX v AMXO). Sau khi x¥y düng ÷ñc líi gi£i mîi, c¡c thuªt to¡n ICS, DPSO, CFPA v MIGA sû döng VFA [96] º hi»u ch¿nh và tr½ cõa c¡c c£m bi¸n. Câ thº xem ¥y l ph÷ìng ph¡p t¼m ki¸m àa ph÷ìng º c£i thi»n vòng phõ sâng. 2.3. K¸t qu£ thüc nghi»m 2.3.1. Dú li»u thüc nghi»m T¡c gi£ ti¸n h nh thüc nghi»m tr¶n 15 bë dú li»u ¢ ÷ñc x¥y düng bði [19]. Chi ti¸t cõa b£ng dú li»u thüc nghi»m ÷ñc thº hi»n trong b£ng [2.1]. 2.3.2. Tham sè thüc nghi»m º ti¸n h nh thüc nghi»m c¡c gi£i thuªt · xu§t, t¡c gi£ ¢ mæ phäng l¤i c¡c gi£i thuªt b¬ng ngæn ngú lªp tr¼nh Java, ch¤y tr¶n mæi tr÷íng h» i·u h nh Windows 10 Professional, vîi c¡c thæng sè ph¦n cùng: Intel Core i5-2.4 GHz, RAM 8GB 1600 MHz DDR3. Tham sè thüc nghi»m cõa c¡c gi£i thuªt DPSO, ICS, CFPA v MIGA ÷ñc mæ t£ trong b£ng 2.2, b£ng 2.3, b£ng 2.4 v b£ng 2.5. 9
13. Thüc nghi»m 1 Möc ½ch cõa thüc nghi»m n y º ¡nh gi¡ hi»u qu£ cõa c¡c gi£i thuªt · xu§t khi còng sû döng mët h m th½ch nghi l ë chçng Olap() ¢ ÷ñc · xu§t trong [40]. Cö thº k¸t qu£ cõa c¡c gi£i thuªt · xu§t DPSO, ICS v CFPA ÷ñc so s¡nh vîi IGA [40] tr¶n 15 bë dú li»u ¢ tr¼nh b y trong b£ng 2.1. B£ng 2.6 minh håa hi»u qu£ cõa c¡c thuªt to¡n, c¡c sè li»u ÷a ra gçm ë bao phõ trung b¼nh, thíi gian t½nh to¡n trung b¼nh sau 30 l¦n ch¤y méi bë dú li»u. K¸t qu£ thüc nghi»m cho th§y, DPSO, CFPA v ICS ÷a ra ch§t l÷ñng líi gi£i v thíi gian t½nh to¡n tèt hìn gi£i thuªt IGA [40]. Cö thº, khi so s¡nh v· thíi gian t½nh giúa DPSO, ICS v CFPA nhªn th§y CFPA tèt hìn ICS tø 47% - 69.05% v· thíi gian t½nh to¡n vîi nhúng bë dú li»u câ sè c£m bi¸n lîn (n > 50). Lþ do c£i ti¸n r§t lîn thíi gian t½nh cõa 3 gi£i thuªt DPSO, ICS v CFPA l n¬m trong b£n th¥n thuëc t½nh ri¶ng cõa tøng gi£i thuªt. Gi£i thuªt ICS sû döng nhúng b÷îc i ng¨u nhi¶n v nhúng c£i ti¸n v· tham sè sû döng d¨n ¸n tèc ë hëi tö cao ngay ð th¸ h» thù 300 ÷ñc thº hi»n ð h¼nh 2.10. M°t kh¡c, CFPA tªn döng sü ên ành cõa hoa, cho ph²p nhúng bæng hoa t÷ìng ùng trao êi ph§n hoa trong méi l¦n thö ph§n º câ ë hëi tö cao. K¸t qu£ v· di»n t½ch bao phõ ÷ñc thº hi»n trong b£ng 2.6 nhªn th§y DPSO, CFPA v ICS ÷a ra c¡c gi£i ph¡p t÷ìng èi tèt khi so s¡nh vîi IGA. Cö thº, DPSO mang l¤i k¸t qu£ tèt nh§t vîi c¡c bë dú li»u s1-07, s2-07, s4-07, s5-07 v s4-08. ICS mang l¤i k¸t qu£ tèt nh§t vîi c¡c bë dú li»u s3-08, s5-08, s3-09, s4-09 v °c bi»t tèt vîi bë dú li»u s5-09. CFPA th¼ ch¿ ÷a ra ÷ñc k¸t qu£ tèt nh§t vîi bë dú li»u s3-07 v s1-08. Tuy nhi¶n, c¡c gi£i ph¡p m CFPA ÷a ra ch§t l÷ñng líi gi£i câ t¿ l» th§p hìn khæng ¡ng kº so vîi ICS v DPSO v cao hìn IGA. Thüc nghi»m 2 Möc ½ch cõa thüc nghi»m n y º so s¡nh v· di»n t½ch bao phõ, thíi gian t½nh v ë l»ch chu©n cõa c¡c gi£i thuªt · xu§t (MIGA, DPSO, ICS v CFPA) vîi gi£i thuªt IGA trong [40] cho 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. Méi bë dú li»u thüc nghi»m 30 l¦n v t½nh trung b¼nh c¡c gi£i ph¡p v· di»n t½ch bao phõ, thíi gian t½nh v ë l»ch chu©n. Chi ti¸t cõa tøng gi£i ph¡p ÷ñc tr¼nh b y d÷îi ¥y. ¦u ti¶n, t¡c gi£ ¡nh gi¡ v· trung b¼nh di»n t½ch bao phõ cõa 5 gi£i thuªt (IGA, MIGA, DPSO, ICS v CFPA). º ¡nh gi¡ ti¶u ch½ n y t¡c gi£ thèng k¶ k¸t qu£ cõa 5 gi£i thuªt theo c¡c ti¶u ch½ bao phõ 70%, 80% v 90% di»n t½ch tr¶n mi·n A. K¸t qu£ l¦n l÷ñt ÷ñc thº hi»n trong c¡c h¼nh 2.11, h¼nh 2.12, h¼nh 2.13 v trong b£ng 2.7. Ta câ thº nhªn th§y, MIGA ÷a ra k¸t qu£ tèt 13/15 bë dú li»u khi so s¡nh vîi 4 gi£i thuªt IGA, DPSO, CFPA v ICS. °c bi»t vîi bë 10
14. dú li»u bao phõ 70% (bë dú li»u tø s1-07 ¸n s5-07) di»n t½ch tr¶n mi·n A th¼ MIGA cho k¸t qu£ b¬ng cªn tr¶n (Upper bound) v MIGA tèt hìn ICS kho£ng 1.5% v· di»n t½ch bao phõ (ICS l thuªt to¡n tèt nh§t hi»n t¤i khi sû döng h m th½ch nghi l ë chçng Olap()). Thù ba, t¡c gi£ ¡nh gi¡ v· thíi gian t½nh to¡n cõa 5 gi£i thuªt (IGA, DPSO, CFPA, ICS v MIGA) ÷ñc thº hi»n trong h¼nh 2.15. K¸t qu£ thû nghi»m thüc sü cho th§y thíi gian t½nh to¡n cõa MIGA trung b¼nh cao g§p 3 l¦n so vîi ICS ¤t ÷ñc. i·u n y l câ thº gi£i th½ch l do ICS kh¡m ph¡ khæng gian t¼m ki¸m hi»u qu£ hìn nhí ¡p döng nhúng b÷îc nh£y ng¨u nhi¶n v sü c£i ti¸n cõa vi»c lüa chån tham sè cho b i to¡n d¨n ¸n tèc ë hëi tö cao ngay ð th¸ h» thù 300 ÷ñc thº hi»n ð h¼nh 2.10. Tuy nhi¶n, tø tøng ùng döng cõa b i to¡n º c¥n nh­c trong vi»c lüa chån giúa ë ên ành cõa c¡c gi£i ph¡p · xu§t hay thíi gian t½nh to¡n. 2.4. K¸t luªn ch÷ìng. Trong ch÷ìng n y, t¡c gi£ tr¼nh b y 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, · xu§t c¡c gi£i thuªt metaheuristic (DPSO, ICS, CFPA v MIGA) º gi£i quy¸t b i to¡n. âng gâp cõa t¡c gi£ bao gçm: · xu§t khði t¤o heuristic, · xu§t h m th½ch nghi t½nh ch½nh x¡c di»n t½ch bao phõ cho thuªt to¡n MIGA; · xu§t mët sè thuªt to¡n ti¶u biºu cõa lîp c¡c thuªt to¡n b¦y  n thæng minh (DPSO, ICS, CFPA) k¸t hñp vîi c¡c kÿ thuªt c£i ti¸n trong tøng thuªt to¡n tòy thuëc v o °c tr÷ng cõa tøng gi£i thuªt º n¥ng cao ch§t l÷ñng líi gi£i, ë ên ành v kh£ n«ng hëi tö cõa thuªt to¡n. C¡c ph÷ìng ph¡p · xu§t ¢ ÷ñc thüc nghi»m tr¶n 15 bë dú li»u ÷ñc x¥y düng trong [19]. Thüc nghi»m ch¿ ra r¬ng £nh h÷ðng °c t½nh cõa tøng gi£i thuªt £nh h÷ðng r§t nhi·u ¸n ch§t l÷ñng líi gi£i. Do â, trong méi gi£i thuªt · xu§t ·u câ nhúng c£i ti¸n mîi nh÷: Trong DPSO · xu§t vi»c ¡p döng th¶m v²c-tì democratic; trong ICS · xu§t vi»c thay êi c¡c tham sè º i·u ch¿nh k½ch th÷îc b÷îc nh£y, º x¡c su§t ph¡t hi»n trùng chim Cuckoo v sè l÷ñng chim Cuckoo; trong CFPA · xu§t vi»c sû döng thæng tin cõa to n bë qu¦n thº º thüc hi»n c¡c ph²p thö ph§n, CFPA công sû döng c¡c ph÷ìng ph¡p hiºu ch¿nh tham sè v · xu§t mët v²c-tì hén lo¤n º ¤i di»n cho sü £nh h÷ðng cõa t§t c£ c¡c c¡ thº l¶n qu¦n thº; MIGA · xu§t vi»c sû döng k¸t hñp c¡c ph²p lai gh²p (LX v AMXO) v °c bi»t l · xu§t t½nh ch½nh x¡c h m möc ti¶u. Möc ½ch cõa c¡c · xu§t trong tøng gi£i thuªt ngo i vi»c n¥ng cao ch§t l÷ñng líi gi£i, ë ên ành v thíi gian t½nh to¡n nâ cán mang l¤i âng gâp v· m°t håc thuªt trong vi»c hiºu b£n ch§t cõa tøng gi£i thuªt v · xu§t ÷ñc nhúng kÿ thuªt c£i ti¸n tøng gi£i thuªt º ¡p döng v o gi£i b i to¡n. Tr¶n cì sð â, vîi mong muèn c£i thi»n thíi gian ch¤y v ë bao phõ, luªn ¡n · xu§t mët sè gi£i thuªt b y  n nh÷ gi£i thuªt Democratic Particle Swarm Optimization (DPSO), Improve Cuckoo Search (ICS) v Chaotic Flower Polli- 11
15. nation Algorithm (CFPA) k¸t hñp vîi c¡c kÿ thuªt heuristic ÷ñc · xu§t vîi ký vång c£i thi»n thíi gian t½nh to¡n vîi ë tèt bao phõ ngang b¬ng ho°c tèt hìn c¡c gi£i thuªt tr÷îc â º n¥ng cao ë bao phõ v gi£m thíi gian t½nh to¡n. C¡c k¸t qu£ cõa ch÷ìng n y ÷ñc cæng bè trong c¡c cæng tr¼nh (1), (5) v (6) trong danh möc c¡c cæng tr¼nh ¢ cæng bè cõa t¡c gi£ luªn ¡n. CH×ÌNG 3. 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 B i to¡n cüc ¤i di»n t½ch bao phõ trong WSNs khæng çng nh§t vîi sè l÷ñng c£m bi¸n cho tr÷îc ÷ñc giîi thi»u bði Y. Yoon [19]. Tuy nhi¶n, trong thüc t¸ vòng triºn khai m¤ng th÷íng câ c¡c ch÷îng ng¤i vªt (t÷íng, c¥y cèi, táa nh , v.v.). V¼ vªy, trong nhúng khu vüc câ ch÷îng ng¤i vªt th÷íng c£n trð vi»c giao ti¸p khæng d¥y do kho£ng c¡ch truy·n thæng cõa c¡c c£m bi¸n h¤n ch¸. Do â, trong nghi¶n cùu n y t¡c gi£ · xu§t mæ h¼nh b i to¡n cüc ¤i di»n t½ch bao phõ trong WSNs vîi sè l÷ñng c£m bi¸n bi¸t tr÷îc v c¡c c£m bi¸n kh¡c kiºu trong vòng quan t¥m câ xem x²t ch÷îng ng¤i vªt l h¼nh chú nhªt. T¡c gi£ gi£ thi¸t r¬ng c¡c ch÷îng ng¤i vªt ch­n h¸t sâng truy·n thæng khæng d¥y, do â khi c£m bi¸n bao phõ trong vòng chùa ch÷îng ng¤i vªt l b¬ng 0. 3.1. Ph¡t biºu b i to¡n B i to¡n cüc ¤i di»n t½ch bao phõ trong WSNs khæng çng nh§t câ r ng buëc ch÷îng ng¤i vªt (Maximization of Obstacles Constrained Area Coverage in Heterogeneous Wireless Sensor Networks) ÷ñc ph¡t biºu nh÷ sau: Cho vòng gi¡m s¡t A l mët h¼nh chú nh§t câ k½ch th÷îc W × H v n c£m bi¸n t¾nh s1; s2; : : : ; sn. Méi c£m bi¸n s câ b¡n k½nh c£m nhªn rs. Gåi O l tªp c¡c ch÷îng ng¤i vªt O = fo1::omg, trong â ot l ch÷îng ng¤i vªt h¼nh chú nhªt x¡c inh bði gâc tr¶n b¶n ph£i v gâc d÷îi b¶n tr¡i v (ut1 ; vt1 ) (ut2 ; vt2 ) ot \ oh = ?; 8t; h = . B i to¡n °t ra l t¼m c¡c và tr½ °t c£m 1 : : : m (x1; y1 ) ; (x2; y2 ) ;:::; (xn; yn ) bi¸n s1; s2; : : : ; sn sao cho di»n t½ch bao phõ tr¶n vòng gi¡m s¡t A l lîn nh§t. Trong b i to¡n n y sû döng mæ h¼nh ¾a nhà ph¥n trong [19]. Gåi sri (xi; yi) l vòng bao phõ bði b¡n k½nh c£m bi¸n ri cõa c£m bi¸n si t¤i và tr½ (xi; yi) v l vòng bao phõ bði ch÷îng ng¤i vªt h¼nh chú nhªt . sot (ut1 ; vt1 ; ut2 ; vt2 ) ot 12
16. Mæ h¼nh to¡n håc cõa b i to¡n ÷ñc ph¡t biºu nh÷ sau: n m !! T¼m cüc ¤i [ \ [ (3.1) coA = area sri(xi; yi) A n sot(ut1 ; vt1 ; ut2 ; vt2 ) i=1 t=1 vîi i·u ki»n x = (xi; yi) 2 A; i = 1; : : : ; n;(xi; yi) 2= ot; t = 1; : : : ; m trong â (xi; yi) l tåa ë t¥m cõa c£m bi¸n si. Yoon v Kim ¢ chùng minh ÷ñc b i to¡n cüc ¤i di»n t½ch bao phõ trong m¤ng c£m bi¸n khæng çng nh§t khæng câ ch÷îng ng¤i vªt vîi sè l÷ñng c£m bi¸n cho tr÷îc l b i to¡n NP-Khâ [19]. Do â, b i to¡n cüc ¤i di»n t½ch bao phõ trong m¤ng c£m bi¸n khæng çng nh§t vîi sè l÷ñng c£m bi¸n cho tr÷îc công l b i to¡n NP-khâ. Trong ph¦n ti¸p theo t¡c gi£ tr¼nh b y hai gi£i thuªt metaheuristic º gi£i quy¸t cho b i to¡n n y ÷ñc °t t¶n l¦n l÷ñt l gi£i thuªt di truy·n (MGA) v gi£i thuªt tèi ÷u hâa b¦y  n (IPSO). C£ hai gi£i thuªt ·u sû döng chung h m th½ch nghi (OSlap) do t¡c gi£ · xu§t. 3.2. Gi£i thuªt · xu§t 3.2.1. Gi£i thuªt di truy·n c£i ti¸n Trong ph¦n n y t¡c gi£ s³ tr¼nh b y gi£i thuªt di truy·n c£i ti¸n (MGA) ÷ñc · xu§t º gi£i 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â ch÷îng ng¤i vªt bao gçm c¡c b÷îc: m¢ hâa c¡ thº gièng MIGA v IGA, · xu§t khði t¤o qu¦n thº heuristic k¸t hñp ph÷ìng ph¡p khði t¤o qu¦n thº trong [19] v [40], x¥y düng cæng thùc t½nh h m th½ch nghi º c£i thi»n ph÷ìng ph¡p t½nh ë chçng Olap() trong [40] chi ti¸t c¡ch t½nh h m th½ch nghi ÷ñc thº hi»n trong cæng thùc (3.3) v ÷a ra c¡c t½nh to¡n phò hñp vîi b i to¡n bao phõ di»n t½ch câ ch÷îng ng¤i vªt, lai gh²p sû döng BLX-α, ët bi¸n sû döng Gauss ëng v cuèi còng l b÷îc chån låc. 3.2.2. Gi£i thuªt tèi ÷u hâa b¦y  n c£i ti¸n Gi£i thuªt tèi ÷u hâa b¦y  n c£i ti¸n - IPSO l gi£i thuªt l§y þ t÷ðng tø thâi quen sinh ho¤t cõa b¦y  n. Trong PSO truy·n thèng ÷ñc sû döng r§t phê bi¸n trong nhi·u ùng döng nh÷ng nâ v¨n cán tçn t¤i mët sè y¸u iºm nh÷ d¹ x£y ra hi»n t÷ñng hëi tö sîm do c¡c c¡ thº ·u i theo h÷îng cõa c¡ thº tèt nh§t d¨n ¸n k¸t qu£ thu ÷ñc ch¿ l cüc trà àa ph÷ìng. Ch½nh v¼ th¸ t¡c gi£ · xu§t mët ph÷ìng ph¡p khði t¤o düa tr¶n ph¥n cöm c¡c c¡ thº. IPSO khæng ch¿ nhªn kinh nghi»m cõa c¡ thº tèt nh§t ð th¸ h» hi»n t¤i m cán nhªn ÷ñc kinh nghi»m cõa måi c¡ thº kh¡c trong qu¦n thº. Do â, vîi ph÷ìng ph¡p khði t¤o n y s³ l m cho IPSO câ kh£ n«ng t¼m ki¸m tèt hìn ph÷ìng ph¡p khði t¤o ng¨u nhi¶n. IPSO sû döng h m th½ch nghi gièng nh÷ trong MGA l t½nh OSLap ÷ñc giîi thi»u trong cæng thùc (3.3) v cªp nhªt c¡ thº mîi. 13
17. Tuy nhi¶n, IPSO · xu§t º gi£i quy¸t cho b i to¡n n y khæng thº sû döng cæng thùc (1.14), (1.15) l cæng thùc t½nh và tr½ v vªn tèc cõa PSO truy·n thèng, v¼ vªn tèc cõa méi c¡ thº khæng ch¿ chàu £nh h÷ðng bði kinh nghi»m cõa c¡ thº h÷îng theo c¡ thº ¦u  n v c¡ thº ¦u cöm. V¼ vªy, º phò hñp vîi c¡c chi¸n l÷ñc · xu§t trong ph¦n khði t¤o qu¦n thº t¡c gi£ · xu§t c¡ch t½nh to¡n sûa êi cæng thùc t½nh vªn tèc v và tr½ trong qu¡ tr¼nh cªp nhªt c¡ thº ÷ñc thº hi»n trong cæng thùc (3.16) v (3.17). 3.3. K¸t qu£ thüc nghi»m 3.3.1. Kàch b£n thüc nghi»m Trong mæ h¼nh b i to¡n tèi a di»n t½ch bao phõ trong m¤ng c£m bi¸n khæng d¥y câ xem x²t ¸n y¸u tè ch÷îng ng¤i vªt, t¡c gi£ x¥y düng 5 kàch b£n m¤ng vîi 23 bë dú li»u º ¡nh gi¡ hi»u n«ng cõa c¡c gi£i thuªt · xu§t. Chi ti¸t cõa c¡c kàch b£n ÷ñc tr¼nh b y nh÷ sau: Kàch b£n 1 : Möc ti¶u cõa kàch b£n n y l ¡nh gi¡ sü £nh h÷ðng cõa và tr½ c¡c ch÷îng ng¤i vªt. Dú li»u ÷ñc tr¼nh b y trong b£ng 3.1. Kàch b£n 2 : Möc ½ch cõa kàch b£n n y l ¡nh gi¡ £nh h÷ðng cõa t l» di»n t½ch ch÷îng ng¤i vªt so vîi mi·n A. Dú li»u cõa kàch b£n n y ÷ñc thº hi»n ð b£ng 3.2. Kàch b£n 3 : Möc ½ch cõa kàch b£n n y l ¡nh gi¡ £nh h÷ðng cõa sè l÷ñng ch÷îng ng¤i vªt tr¶n mi·n A. Dú li»u cõa kàch b£n n y ÷ñc thº hi»n ð b£ng 3.3. Kàch b£n 4 : Möc ½ch cõa kàch b£n n y l ¡nh gi¡ £nh h÷ðng cõa têng di»n t½ch c£m bi¸n câ thº bao phõ ÷ñc tr¶n mi·n A. Dú li»u cõa kàch b£n n y ÷ñc thº hi»n ð b£ng 3.4. Kàch b£n 5 : Möc ½ch cõa kàch b£n n y l ¡nh gi¡ £nh h÷ðng cõa b¡n k½nh c£m bi¸n tr¶n mi·n A. Dú li»u cõa kàch b£n n y ÷ñc thº hi»n ð b£ng 3.5. 3.3.2. Tham sè thüc nghi»m º ¡nh gi¡ hi»u qu£ cõa tøng gi£i thuªt · xu§t: MGA v IPSO. T¡c gi£ thüc nghi»m mët gi£i thuªt PSO cì b£n ¢ ÷ñc giîi thi»u bði [79] °t t¶n l (PSO) º l m cì sð so s¡nh vîi hai gi£i thuªt MGA v IPSO · xu§t. Tham sè thüc nghi»m cõa tøng gi£i thuªt ÷ñc thº hi»n trong b£ng 3.6, b£ng 3.7, b£ng 3.8. T§t c£ gi£i thuªt · xu§t ÷ñc c i °t tr¶n mæi tr÷íng: Intel Core i7-3.60GHz, RAM 16GB, Windows 8 64-bit. 14
18. 3.3.3. So s¡nh ¡nh gi¡ k¸t qu£ thüc nghi»m T¡c gi£ x¥y düng n«m thüc nghi»m º ¡nh gi¡ k¸t qu£ cõa gi£i thuªt · xu§t. Méi thüc nghi»m ·u ÷ñc ¡nh gi¡ tr¶n 23 bë dú li»u trong n«m kàch b£n m¤ng ¢ ÷ñc x¥y düng ð tr¶n. Thüc nghi»m 1 : T¼m gi¡ trà phò hñp cõa c¡c tham sè trong tøng thuªt to¡n · xu§t º ¤t hi»u qu£ nh§t. T¡c gi£ · xu§t cæng thùc fj (i) º lüa chån c¡c tham sè thüc nghi»m phò hñp vîi tøng thuªt to¡n · xu§t chi ti¸t cõa cæng thùc thº hi»n trong cæng thùc (3.19). Sau khi ¡p döng cæng thùc fj (i) ta thu lüa chån ÷ñc c¡c tham sè c1 = c2 = 0:1; c3 = 0:9 l nhúng gi¡ trà phò hñp nh§t º ÷a v o thuªt to¡n cho c¡c thüc nghi»m ti¸p theo. Thüc nghi»m 2 : ¡nh gi¡ sü £nh h÷ðng cõa t¿ l» c¡ thº khði t¤o heuristic · xu§t trong tøng thuªt to¡n · xu§t. t¡c gi£ thay êi t l» khði t¤o heuristic l¦n l÷ñt l 0%, 50% v 100%. T¡c gi£ công sû döng h m fi (j) ÷ñc tr¼nh b y trong cæng thùc (3.19) vîi P = f0%; 50%; 100%g º ¡nh gi¡ ë tèt cõa khði t¤o heuristic düa tr¶n gi¡ trà v· di»n t½ch bao phõ tr¶n mi·n A. K¸t qu£ cho th§y MGA vîi t l» khði t¤o heuristic 100% cho k¸t qu£ tèt nh§t. Cán IPSO vîi t l» khði t¤o heuristic 50% cho k¸t qu£ tèt nh§t. Thüc nghi»m 3 : ¡nh gi¡ c¡c chi¸n l÷ñc x¥y düng cöm tr÷ðng cõa IPSO. B¬ng c¡ch l§y k¸t qu£ tèt nh§t cõa c¡c tham sè t¼m ÷ñc cõa thüc nghi»m 1, 2 ¡p döng gi£i thuªt PSO truy·n thèng v IPSO nhªn th§y IPSO cho k¸t qu£ tèt hìn PSO truy·n thèng. Thüc nghi»m 4 : ¡nh gi¡ £nh h÷ðng cõa MVFA ¸n hi»u qu£ cõa thuªt to¡n · xu§t. B¬ng c¡ch ti¸n h nh so s¡nh c¡c gi£i thuªt · xu§t câ sû döng th¶m MVFA v khæng sû döng MVFA. Câ thº nhªn th§y vîi phi¶n b£n sû döng MFVA thu ÷ñc ch§t l÷ñng líi gi£i tèt hìn phi¶n b£n khæng sû döng MVFA. Do â, MVFA s³ ÷ñc sû döng v o phi¶n b£n tèt nh§t. Thüc nghi»m 5 : ¡nh gi¡ k¸t qu£ tøng gi£i thuªt · xu§t vîi hai gi£i thuªt ICS v CFPA ÷ñc tr¼nh b y trong ch÷ìng 2 (ICS v CFPA l hai gi£i thuªt hi»u qu£ nh§t trong c¡c gi£i thuªt sû döng h m th½ch nghi ë chçng Olap ÷ñc · xu§t bði [40]). Tuy nhi¶n, trong thüc nghi»m n y ICS v CFPA sû döng h m th½ch nghi l ë chçng OSLap ÷ñc thº hi»n trong cæng thùc (3.3) v ÷ñc so s¡nh vîi gi£i thuªt MGA v IPSO tr¶n n«m kàch b£n ¢ ÷ñc tr¼nh b y trong ph¦n kàch b£n thüc nghi»m ð tr¶n. Nhªn th§y r¬ng, MGA v IPSO thu ÷ñc k¸t qu£ tèt hìn ICS v CFPA tr¶n t§t c£ 5 kàch b£n m¤ng. V¼ ICS v CFPA ÷ñc thi¸t k¸ º phò hñp vîi b i to¡n cüc ¤i di»n t½ch bao phõ trong WSNs kh¡c kiºu khæng câ r ng buëc ch÷îng ng¤i vªt. Cán MGA v IPSO ÷ñc thi¸t k¸ º gi£i quy¸t b i to¡n cüc ¤i di»n t½ch bao phõ trong WSNs kh¡c kiºu câ r ng buëc ch÷îng ng¤i vªt. 15
19. 3.4. K¸t luªn ch÷ìng Trong ch÷ìng n y, t¡c gi£ · xu§t c£i ti¸n b i to¡n [19] câ xem x²t ¸n ch÷îng ng¤i vªt cho phò hñp vîi thüc t¸ , · xu§t hai gi£i thuªt MGA v IPSO º gi£i quy¸t b i to¡n bao gçm: khði t¤o heuristic, · xu§t h m th½ch nghi (OSlap) v c£i ti¸n thuªt to¡n lüc ©y £o (MVFA), · xu§t c¡ch gi£m d¦n trång sè qu¡n t½nh º c£i thi»n tèc ë hëi tö trong IPSO. Hìn th¸ núa, t¡c gi£ · xu§t ba chi¸n l÷ñc t¼m c¡ thº ¦u cöm trong IPSO. C¡c ph÷ìng ph¡p · xu§t ¢ ÷ñc thû nghi»m tr¶n 23 bë dú li»u vîi c¡c kàch b£n kh¡c nhau ÷ñc x¥y düng cho tøng möc ½ch sû döng kh¡c nhau. Qua c¡c th½ nghi»m n y, t¡c gi£ ¢ rót ra mët sè k¸t luªn câ þ ngh¾a li¶n quan ¸n vi»c lüa chån tham sè phò hñp cho tøng thuªt to¡n · xu§t, £nh h÷ðng cõa khði t¤o heuristic, £nh h÷ðng cõa chi¸n l÷ñc lüa chån c¡ thº ¦u cöm, £nh h÷ðng cõa MVFA l¶n c¡c thuªt to¡n · xu§t (IPSO v MGA). K¸t qu£ thüc nghi»m ¢ chùng minh r¬ng c¡c °c t½nh nh÷ và tr½ cõa ch÷îng ng¤i vªt, têng di»n t½ch cõa ch÷îng ng¤i vªt, sè l÷ñng c¡c ch÷îng ng¤i vªt, ë bao phõ cõa c£m bi¸n v b¡n k½nh c£m bi¸n £nh h÷ðng r§t lîn ¸n hi»u su§t cõa c¡c thuªt to¡n ÷ñc · xu§t. Trong h¦u h¸t c¡c kàch b£n thû nghi»m, IPSO ho¤t ëng tèt hìn ICS, CFPA v MGA, °c bi»t l khi xû lþ c¡c bë dú li»u câ sè l÷ñng c£m bi¸n r§t lîn. M°t kh¡c, vi»c · xu§t chi¸n l÷ñc t¼m c¡ thº ¦u cöm trong IPSO công c£i thi»n ch§t l÷ñng líi gi£i nhí c¡ch sû döng kinh nghi»m cõa tøng c¡ thº thay v¼ ch¿ xem x²t c¡ thº tèt nh§t, do â tr¡nh hëi tö sîm. Ngo i ra, MGA nêi bªt l¶n khi thüc nghi»m tr¶n c¡c bë dú li»u câ sè l÷ñng lîn c¡c ch÷îng ng¤i vªt, v¼ trong MGA câ to¡n tû ët bi¸n s³ gióp tho¡t khäi vòng vi ph¤m (vòng chùa ch÷îng ng¤i vªt). C¡c k¸t qu£ cõa ch÷ìng n y ÷ñc cæng bè trong cæng tr¼nh (9) trong danh möc c¡c cæng tr¼nh ¢ cæng bè cõa t¡c gi£ luªn ¡n. CH×ÌNG 4. 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 C SÛ DÖNG IšM THU PHT DI ËNG 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. B i to¡n n y gi£i quy¸t mët sè th¡ch thùc cõa vi»c triºn khai c¡c nót trong m¤ng c£m bi¸n khæng d¥y nh÷: bao phõ èi t÷ñng, £m b£o k¸t nèi v chàu léi trong to n m¤ng WSNs vîi möc ti¶u tèi thiºu hâa sè l÷ñng c¡c nót ÷ñc sû döng. Gi£ sû r¬ng c¡c èi t÷ñng v mët tr¤m cì sð (Base station) ÷ñc triºn khai trong mi·n gi¡m s¡t. Y¶u c¦u cõa b i to¡n l m sao bao phõ ÷ñc t§t c£ c¡c èi t÷ñng bði c¡c c£m bi¸n (c¡c c£m bi¸n s³ thu thªp thæng tin dú li»u trong 16
20. vòng c£m bi¸n cõa c¡c nót) sau khi thu thªp xong dú li»u c¡c c£m bi¸n ph£i truy·n dú li»u ¢ thu thªp ÷ñc v· tr¤m cì sð (kh£ n«ng k¸t nèi). Tuy nhi¶n, khi câ sü cè x£y ra l m gi¡n o¤n kh£ n«ng truy·n tin cõa c¡c nót. Y¶u c¦u °t ra ph£i t¼m ÷ñc mët ÷íng truy·n thù hai ph¥n bi»t º gûi dú li»u v· tr¤m cì sð (kh£ n«ng chàu léi). Möc ti¶u cõa b i to¡n l tèi thiºu hâa sè nót sû döng khi triºn khai m¤ng. Chi ti¸t mæ h¼nh to¡n håc cõa b i to¡n ÷ñc tr¼nh b y nh÷ sau: 4.1.1. Ph¡t biºu b i to¡n Cho n èi t÷ñng câ tåa ë T = f(xi; yi) j 0 ≤ xi ≤ W; 0 ≤ yi ≤ H; i = 1::ng v mët tr¤m cì sð (Base Station) câ tåa ë B (xB; yB) sao cho (0 ≤ xB ≤ W; 0 ≤ yB ≤ H) ÷ñc triºn khai tr¶n mi·n quan t¥m A = f(x; y) j 0 ≤ x ≤ W; 0 ≤ y ≤ Hg. T§t c£ c¡c c£m bi¸n câ b¡n k½nh c£m bi¸n l Rs v b¡n k½nh truy·n thæng l Rc vîi (Rc = 2 × Rs) [40]; t§t c£ c¡c nót chuyºn ti¸p v tr¤m cì sð B ·u câ b¡n k½nh truy·n thæng l Rc. B i to¡n °t ra l triºn khai ½t nh§t c¡c nót c£m bi¸n v c¡c nót chuyºn ti¸p tr¶n mi·n A sao cho: i) méi èi t÷ñng ÷ñc bao phõ bði ½t nh§t mët c£m bi¸n, ii) luæn t¼m ÷ñc hai ÷íng i ph¥n bi»t º méi c£m bi¸n ÷ñc k¸t nèi vîi tr¤m cì sð B thæng qua c¡c c£m bi¸n v c¡c nót chuyºn ti¸p º £m b£o k¸t nèi v chàu léi trong to n m¤ng. º £m b£o bao phõ c¡c èi t÷ñng: B i to¡n n y sû döng mæ h¼nh c£m bi¸n nhà ph¥n ¢ ÷ñc giîi thi»u trong Ch÷ìng 1 v ÷ñc thº hi»n ð cæng thùc (1.2). º £m b£o k¸t nèi: Hai nót s v s0 (c£m bi¸n ho°c nót chuyºn ti¸p) k¸t nèi ÷ñc vîi nhau theo cæng thùc (4.1) ÷ñc giîi thi»u trong [11]. ( 0 1; n¸u d (s; s ) < Rc; (4.1) f s; s0
    = 0; n¸u ng÷ñc l¤i; trong â d (s; s0) l kho£ng c¡ch Euclide giúa hai nót s v s0. Gåi Sl l tªp t§t c£ c¡c và tr½ câ thº °t c£m bi¸n tr¶n mi·n quan F = i=1 fi t¥m A. Gåi Sm l tªp t§t c£ c¡c và tr½ câ thº °t c¡c nót chuyºn ti¸p tr¶n R = j=1 rj mi·n A. Gåi Sl+m l tªp t§t c£ c¡c và tr½ câ thº °t Q = i=1 qi = ff1; f2; :::; fl; r1; r2; :::; rmg c¡c nót c£m bi¸n v c¡c nót chuyºn ti¸p tr¶n mi·n A. Mæ h¼nh to¡n håc cõa b i to¡n ÷ñc ph¡t biºu nh÷ sau: 17
21. T¼m cüc tiºu jQj ; (4.2) Q⊆Q vîi i·u ki»n: vîi méi Ti 2 T (4.3)
    9 q ; q ; ::; q 2 Q v q 0 ; q 0 ; ::; q 0 2 Q (4.4) i1 i2 ik i1 i2 ih 8 d(Ti; qi ) ≤ Rs > 1 > d(Ti; qi0 ) ≤ Rs > 1 > d(q ; q ) ie ie+1 c sao cho: 0 0 (4.5) d(qie ; qie+1) > d(qik ;B) > d(q 0 ;B) ik :> 0 ij 6= it; 8j = 1; k; 8t = 1; h • Cæng thùc (4.2) tèi thiºu sè l÷ñng nót c£m bi¸n v nót chuyºn ti¸p sû döng trong to n m¤ng. • Cæng thùc (4.3), (4.4) v (4.5) l r ng buëc y¶u c¦u tø méi èi t÷ñng Ti luæn tçn t¤i hai ÷íng truy·n tin khæng chung nót ¸n tr¤m cì sð B, méi ÷íng truy·n tin ph£i ¡p ùng c¡c r ng buëc k¸t nèi ¸n tr¤m cì sð B v nót ¦u ti¶n ð méi ÷íng truy·n tin ph£i luæn l nót c£m bi¸n. 4.1.2. Gi£i thuªt · xu§t T¡c gi£ · xu§t sû döng thuªt to¡n heuristic bao gçm hai pha º gi£i quy¸t b i to¡n °t ra, trong â pha ¦u ti¶n s³ t¼m tªp c£m bi¸n nhä nh§t º câ thº bao phõ h¸t t§t c£ èi t÷ñng v pha thù hai s³ £m b£o t½nh k¸t nèi câ chàu léi trong m¤ng WSNs. Chi ti¸t cõa tøng pha ÷ñc tr¼nh b y nh÷ sau: Pha 1. T¼m tªp c¡c c£m bi¸n tèi thiºu º bao phõ t§t c£ c¡c èi t÷ñng p döng thuªt to¡n tham lam t¼m tªp c¡c c£m bi¸n º bao phõ t§t c£ c¡c èi t÷ñng ÷ñc kþ hi»u l tªp SSCAT (Sensor Set Covering All Targets) bao gçm tªp c¡c c£m bi¸n ÷ñc °t trong mi·n A vîi sè l÷ñng nhä nh§t thäa m¢n bao phõ t§t c£ èi t÷ñng. Sau khi t§t c£ c¡c èi t÷ñng thuëc T ·u ÷ñc bao phõ bði ½t nh§t mët c£m bi¸n trong SSCAT , º £m b£o t½nh chàu léi th¼ méi èi t÷ñng ph£i ÷ñc bao phõ bði ½t nh§t 2 c£m bi¸n. T¤i méi và tr½ cõa c£m bi¸n trong SSCAT ta °t th¶m mët c£m bi¸n núa, tªp c£m bi¸n mîi ÷ñc gåi l tªp SSCAT 0. Nh÷ vªy, SSCAT 0 thäa m¢n méi èi t÷ñng ÷ñc bao phõ bði ½t nh§t 2 c£m bi¸n [22]. 18
22. Pha 2. £m b£o t½nh k¸t nèi câ chàu léi º gi£i quy¸t b i to¡n trong pha n y bao gçm 3 b÷îc: B÷îc 1: Ph¥n cöm tªp SSCAT 0: B÷îc ph¥n cöm n y s³ chia tªp SSCAT 0 v tr¤m cì sð B th nh c¡c tªp con khæng giao nhau, méi tªp con l tªp c£m bi¸n lîn nh§t m t§t c£ c¡c c£m bi¸n trong tªp con â ·u câ thº truy·n thæng vîi nhau. Sau khi ph¥n cöm tªp SSCAT 0, x¥y düng mët ç thà ¦y õ væ h÷îng câ trång sè G2 vîi méi ¿nh cõa G2 l mët cöm. B÷îc 2: °t th¶m c¡c nót chuyºn ti¸p º m¤ng £m b£o t½nh li¶n thæng v chàu léi: Tr¶n ç thà G2 t¼m tªp c¤nh sao cho £m b£o t½nh k¸t nèi v chàu léi cõa m¤ng. Ti¸p â, °t th¶m c¡c nót chuyºn ti¸p tr¶n c¡c c¤nh nèi n y. Trong b÷îc n y · xu§t hai thuªt to¡n USP v UTSP º l m èi t÷ñng so s¡nh vîi nhau. B÷îc 3: Tèi thiºu hâa sè l÷ñng nót chuyºn ti¸p c¦n sû döng, kþ hi»u l tªp FS (Final Solution): Sau khi °t th¶m c¡c nót chuyºn ti¸p, m¤ng x¥y düng ÷ñc ¢ thäa m¢n t½nh li¶n thæng v chàu léi. Tuy nhi¶n, m¤ng cán mët sè nót chuyºn ti¸p d÷ thøa, b÷îc n y s³ lo¤i bä c¡c nót chuyºn ti¸p â º m¤ng tèi ÷u. 4.1.3. K¸t qu£ thüc nghi»m Dú li»u thüc nghi»m Trong b i to¡n n y, t¡c gi£ x¥y düng 15 bë dú li»u vîi c¡c tham sè ÷ñc tr¼nh b y chi ti¸t trong b£ng 4.1 v b£ng 4.2. Trong â: Dú li»u ÷ñc ch¤y thüc nghi»m tr¶n mi·n khæng gian 2 chi·u A vîi n l sè l÷ñng èi t÷ñng, Rs l b¡n k½nh c£m bi¸n. Tham sè thüc nghi»m Ch÷ìng tr¼nh thüc nghi»m ÷ñc c i °t b¬ng ngæn ngú Java, ch¤y tr¶n mæi tr÷íng h» i·u h nh Windows 10 Ultimate. Thæng sè ph¦n cùng: Bë vi xû lþ: Intel Core i5 2.4 GHz; RAM = 4GB. Tham sè thüc nghi»m cõa gi£i thuªt UTSP ÷ñc tr¼nh b y trong b£ng 4.3. So s¡nh ¡nh gi¡ k¸t qu£ thüc nghi»m Trong b i to¡n n y t¡c gi£ ti¸n h nh so s¡nh 2 gi£i thuªt · xu§t USP v UTSP (K¸t qu£ thüc nghi»m cõa UTSP ÷ñc l§y trung b¼nh sau 15 l¦n ch¤y tr¶n 15 bë dú li»u). K¸t qu£ cõa c¡c gi£i thuªt · xu§t ÷ñc thº hi»n tr¶n b£ng 4.4. Nh¼n v o b£ng k¸t qu£ nhªn th§y: V· sè l÷ñng c¡c nót (nót c£m bi¸n v nót chuyºn ti¸p) ÷ñc sû döng gi£i thuªt UTSP nhä hìn gi£i thuªt USP trong c¡c bë dú li»u câ sè l÷ñng èi t÷ñng 19
23. ÷ñc triºn khai tr¶n mi·n A nhä th¼ UTSP ti¸t ki»m ÷ñc kho£ng 10% sè l÷ñng c¡c nót sû döng so vîi USP. V· thíi gian t½nh to¡n UTSP tèt hìn 80% so vîi USP vîi c¡c bë dú li»u câ sè l÷ñng èi t÷ñng ÷ñc triºn khai tr¶n mi·n A nhä. Nh÷ng khi sè l÷ñng èi t÷ñng t«ng l¶n th¼ thíi gian thüc hi»n UTSP cao hìn USP kho£n 15%. Nguy¶n nh¥n câ k¸t qu£ tr¶n l do: Khi sè l÷ñng èi t÷ñng t«ng l¶n th¼ sè l÷ñng c£m bi¸n c¦n dòng cho pha 1 t«ng l¶n v sè ¿nh trong ç thà G2 t«ng l¶n, l m cho khæng gian t¼m ki¸m cõa gi£i thuªt di truy·n (UTSP) rëng hìn. Do â, gi£i thuªt di truy·n s³ câ k¸t qu£ v· sè l÷ñng nót sû döng v thíi gian t½nh cao hìn so vîi USP v ng÷ñc l¤i. 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 Nh÷ñc iºm cõa m¤ng c£m bi¸n t¾nh l c¡c nót ÷ñc triºn khai ð g¦n iºm thu ph¡t t¾nh (Static Sink) ph£i ti¶u hao nguçn n«ng l÷ñng nhi·u hìn c¡c nót ð xa iºm thu ph¡t. V¼ nhúng nót ð xa iºm thu ph¡t ph£i thu nhªn dú li»u v truy·n dú li»u v· tr¤m cì sð thæng qua c¡c nót ð g¦n iºm thu ph¡t. Do â, nót n o c ng g¦n iºm thu ph¡t kh£ n«ng m§t n«ng l÷ñng c ng cao. V¼ nhúng h¤n ch¸ n y t¡c gi£ sû döng m¤ng c£m bi¸n vîi c¡c iºm thu ph¡t di ëng (Mobile Sink) º k²o d i thíi gian sèng cõa m¤ng v · xu§t b i to¡n bao phõ èi t÷ñng £m b£o k¸t nèi trong m¤ng c£m bi¸n câ sû döng c¡c iºm thu ph¡t di ëng. 4.2.1. Ph¡t biºu b i to¡n Cho n èi t÷ñng câ tåa ë T = f(xi; yi) j 0 ≤ xi ≤ W; 0 ≤ yi ≤ H; i = 1::ng v l sè c¡c iºm thu ph¡t di ëng (mobile sinks) sao cho D1; ::; Dm m Di (xDi ; yDi ) l tåa ë cõa iºm thu ph¡t sao cho v l sè 2D Di (0 ≤ xDi ≤ W; 0 ≤ yDi ≤ H) B l÷ñng c¡c chu ký c¦n o. Gi£ thi¸t r¬ng c¡c iºm thu ph¡t di ëng s³ di chuyºn ¸n và tr½ mîi sau méi mët chu ký. Trong t§t c£ c¡c chu ký th¼ quÿ ¤o di chuyºn cõa tøng iºm thu ph¡t di ëng ¢ ÷ñc bi¸t tr÷îc và tr½. Cö thº, ð chu ký thù b n o và tr½ cõa iºm thu ph¡t câ tåa ë (b) (b) (b) , trong â m P = P1 ; :::; Pm b = 1; :::; B v (b) l và tr½ cõa iºm thu ph¡t trong chu ký thù . Y¶u c¦u Pi Di(i = 1; :::; m) b °t ra l c¦n triºn khai c¡c nót sao cho t§t c£ c¡c èi t÷ñng ÷ñc bao phõ bði ½t nh§t mët c£m bi¸n v t¤i méi mët chu ký luæn £m b£o méi c£m bi¸n s³ ÷ñc k¸t nèi vîi ½t nh§t mët iºm thu ph¡t thæng qua c¡c nót c£m bi¸n v c¡c nót chuyºn ti¸p. Möc ti¶u cõa b i to¡n l tèi thiºu hâa sè l÷ñng nót sû döng. Trong b i to¡n n y, gi£ sû r¬ng t§t c£ c¡c c£m bi¸n câ còng b¡n k½nh c£m bi¸n (kþ hi»u l Rs) v còng b¡n k½nh truy·n thæng (kþ hi»u l Rc) sao cho (Rc = 2 × Rs) trong [40]. T¡c gi£, công sû döng mæ h¼nh c£m bi¸n ¾a trán ¢ ÷ñc tr¼nh b y trong Ch÷ìng 1 cõa luªn ¡n v kh£ n«ng mët èi t÷ñng ÷ñc 20
24. bao phõ bði c£m bi¸n ÷ñc thº hi»n ð cæng thùc (4.8). Gåi F l tªp t§t c£ c¡c và tr½ cõa c£m bi¸n câ thº ÷ñc triºn khai tr¶n mi·n A º bao phõ t§t c£ c¡c èi t÷ñng trong t§t c£ c¡c chu ký B, vîi méi và tr½ fi 2 F sao cho Sl . F = i=1 fi Gåi R l tªp c¡c nót chuyºn ti¸p câ thº °t º £m b£o k¸t nèi trong to n m¤ng trong t§t c£ c¡c chu ký B, vîi méi và tr½ mët nót chuyºn ti¸p ri 2 R sao cho Sh . R = j=1 rj 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 sû döng c¡c iºm thu ph¡t di ëng câ thº mæ h¼nh hâa b¬ng to¡n håc nh÷ sau: T¼m cüc tiºu jQj ; (4.9) Q⊆Q vîi i·u ki»n: (( l h ) l+h ) [ [ [ Q 2 fi; rj = qi (4.10) i=1 j=1 i=1 fi 2 F; rj 2 R; i = 1; : : : ; l; j = 1; : : : ; h v (F; R) 2 A (4.11) vîi méi Ti 2 T v vîi méi b 2 B (4.12)   v (b) (b) (4.13) 9 qi1 ; : : : ; qik 2 Q Di 2 P 8 d(T ; q ) ≤ R < i i1 s sao cho: (4.14) d(qie ; qie+1) < Rc; 8e = 1; k − 1; : (b) d(qik ;Di ) < Rc • Cæng thùc (4.9) mæ t£ möc ti¶u cõa b i to¡n, tùc l tèi thiºu hâa têng sè l÷ñng c¡c nót c£m bi¸n v c¡c nót chuyºn ti¸p sû döng trong to n m¤ng. • Cæng thùc (4.10) mæ t£ Q l tªp hñp c¡c nót c£m bi¸n v nót chuyºn ti¸p câ thº ÷ñc triºn khai tr¶n mi·n A. • Cæng thùc (4.11) thº hi»n và tr½ câ thº °t c¡c nót c£m bi¸n v nót chuyºn ti¸p tr¶n mi·n A. • Cæng thùc (4.12), (4.13) v (4.14) mæ t£ trong méi chu ký b vîi méi mët èi t÷ñng Ti luæn tçn t¤i ½t nh§t mët c£m bi¸n bao phõ Ti v tçn t¤i mët tªp hñp c¡c nót c£m bi¸n v nót chuyºn ti¸p º £m b£o k¸t nèi tø c£m bi¸n bao phõ èi t÷ñng v· iºm thu ph¡t (b). Ti Di 4.2.2. Gi£i thuªt · xu§t B i to¡n bao phõ v k¸t nèi trong m¤ng c£m bi¸n khæng d¥y sû döng tr¤m thu ph¡t dú li»u ëng câ hai v§n · c¦n gi£i quy¸t, thù nh§t, £m b£o t§t c£ èi 21
25. t÷ñng ph£i ÷ñc bao phõ bði c¡c c£m bi¸n, v thù hai, t¤i méi chu ký thu thªp dú li»u, t§t c£ c£m bi¸n ·u ph£i ÷ñc k¸t nèi tîi tr¤m thu ph¡t dú li»u ëng. º gi£i quy¸t c¡c y¶u c¦u tr¶n, t¡c gi£ · xu§t hai gi£i thuªt PGA v SGA, méi gi£i thuªt ·u bao gçm hai pha, l¦n l÷ñt gi£i quy¸t hai v§n · cõa b i to¡n. Pha I: Bao phõ èi t÷ñng vîi sè l÷ñng c£m bi¸n tèi thiºu b¬ng vi»c k¸t hñp gi£i thuªt ph¥n cöm K-means v ph÷ìng ph¡p heuristic. Pha II: £m b£o c¡c c£m bi¸n ÷ñc k¸t nèi tîi tr¤m thu ph¡t dú li»u t¤i méi chu ký thu thªp dú li»u. Hai gi£i thuªt · xu§t sû döng chung còng mët ph÷ìng ph¡p cho pha I, sü kh¡c bi»t cõa hai gi£i thuªt ¸n tø pha II °t t¶n l PGA v SGA trong â: PGA düa tr¶n þ t÷ðng tham lam cán SGA düa tr¶n þ t÷ðng tham lam k¸t hñp vîi gi£i thuªt c¥y khung. 4.2.3. K¸t qu£ thüc nghi»m T¡c gi£ so s¡nh c¡c gi£i thuªt ÷ñc · xu§t cõa t¡c gi£ vîi gi£i thuªt SMT- MSP câ li¶n quan nh§t [56] cho v§n · £m b£o k¸t nèi trong m¤ng. Dú li»u thüc nghi»m Trong ph¦n n y, t¡c gi£ thüc hi»n thüc nghi»m vîi ba kàch b£n kh¡c nhau º xem x²t sü £nh h÷ðng cõa tøng tham sè ¦u v o èi vîi c¡c gi£i thuªt · xu§t bao gçm (sè l÷ñng tr¤m thu ph¡t di ëng, sè chu ký thu thªp dú li»u, sè l÷ñng c¡c èi t÷ñng). Chi ti¸t cõa dú li»u thüc nghi»m ÷ñc tr¼nh b y trong b£ng 4.5, b£ng 4.6 v b£ng 4.7. Tham sè thüc nghi»m C£ ba kàch b£n thüc nghi»m ·u ÷ñc xem x²t thüc hi»n trong vòng quan t¥m câ di»n t½ch 2000 × 2000 v gi£ sû t§t c£ c£m bi¸n ·u câ b¡n k½nh c£m bi¸n Rs = 15(m) v b¡n k½nh truy·n Rc = 30(m). Ch÷ìng tr¼nh thüc nghi»m ÷ñc c i °t b¬ng ngæn ngú Java, ch¤y tr¶n h» i·u h nh Windows 10 Professional 64-bit vîi thæng sè ph¦n cùng nh÷ sau:Bë vi xû lþ: Intel(R) Core(TM) i7-5500U (2.4GHz); RAM = 8GB. So s¡nh ¡nh gi¡ k¸t qu£ thüc nghi»m ƒnh h÷ðng cõa sè l÷ñng tr¤m thu ph¡t dú li»u ëng: Nh¼n v o h¼nh 4.8 ta câ thº nhªn th§y sè l÷ñng c¡c nót sû döng câ xu h÷îng gi£m khi sè l÷ñng tr¤m thu ph¡t dú li»u ëng t«ng. Cö thº PGA cho k¸t qu£ tèt hìn SGA v SMT-MSP. Tuy nhi¶n, SMT-MSP câ thíi gian t½nh to¡n ½t hìn hai gi£i thuªt PGA v SGA. ƒnh h÷ðng cõa sè chu ký thu thªp dú li»u: ƒnh h÷ðng cõa sè chu ký thu thªp dú li»u tîi sè nót c¦n ÷ñc triºn khai cõa c¡c thuªt to¡n ÷ñc thº hi»n 22
26. trong h¼nh 4.9. Câ thº nhªn th§y SMT-MSP c¦n nhi·u nót sû döng hìn PGA v SGA. Tuy nhi¶n SMT-MSP l gi£i thuªt câ thíi gian ch¤y ½t hìn hai gi£i thuªt · xu§t. ƒnh h÷ðng cõa sè l÷ñng c¡c èi t÷ñng: Sü £nh h÷ðng cõa sè èi t÷ñng l¶n sè l÷ñng c¡c nót c¦n triºn khai cõa c¡c gi£i thuªt ÷ñc thº hi»n tr¶n h¼nh 4.10. Ta câ thº nhªn th§y tèc ë t«ng sè l÷ñng c¡c nót c¦n triºn khai cõa c¡c gi£i thuªt câ xu h÷îng gi£m khi sè l÷ñng èi t÷ñng õ lîn. Lþ do l khi sè l÷ñng èi t÷ñng lîn ¸n mët ng÷ïng nh§t ành th¼ c¡c nót ÷ñc triºn khai d y °c tr¶n mi·n quan t¥m v tü chóng £m b£o t½nh bao phõ to n bë èi t÷ñng v t½nh k¸t nèi trong m¤ng. K¸t luªn ch÷ìng. Trong ch÷ìng n y t¡c gi£ · xu§t hai b i to¡n ¤i di»n cho lîp c¡c b i to¡n trong v§n · bao phõ èi t÷ñng trong m¤ng c£m bi¸n khæng d¥y. Vîi méi b i to¡n t¡c gi£ · xu§t c¡c gi£i thuªt heuristic º gi£i quy¸t hai b i to¡n nh÷ sau: 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; · xu§t c¡c gi£i thuªt USP v UTSP; 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 iºm thu ph¡t dú li»u di ëng; · xu§t c¡c gi£i thuªt PGA, SGA. C¡c k¸t qu£ cõa ch÷ìng n y ÷ñc cæng bè trong c¡c cæng tr¼nh (2), (3), (4), (7) v (8) trong danh möc c¡c cæng tr¼nh ¢ cæng bè cõa t¡c gi£ luªn ¡n. K˜T LUŠN CHUNG C¡c âng gâp mîi • 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 ÷ñc · xu§t trong [19] v · xu§t mët sè thuªt to¡n meta-heuristic (DPSO, ICS, CFPA v MIGA) º gi£i quy¸t b i to¡n. C¡c gi£i xu§t · xu§t ÷ñc so s¡nh ¡nh gi¡ vîi c¡c thuªt to¡n tèt nh§t tr÷îc â (IGA) [40] v· di»n t½ch bao phõ, thíi gian t½nh to¡n v ë l»ch chu©n. K¸t qu£ nhªn th§y c¡c gi£i thuªt · xu§t ·u tèt hìn v· di»n t½ch bao phõ, thíi gian t½nh to¡n v ë ên ành cõa thuªt to¡n khi so s¡nh vîi IGA. °c bi»t MIGA cho k¸t qu£ tèt nh§t trong sè t§t c£ c¡c thuªt to¡n · xu§t. Bði v¼, MIGA sû döng k¸t hñp nhi·u to¡n tû lai gh²p º a d¤ng v· kiºu gen. Th¶m v o â, MIGA sû döng heuristic trong ph¦n khði t¤o l m cho c¡c c¡ thº ÷ñc sinh ra câ °c t½nh di truy·n tèt. °c bi»t, t¡c gi£ trong luªn ¡n ¢ · xu§t c¡ch t½nh di»n t½ch ch½nh x¡c m ch÷a câ cæng tr¼nh nghi¶n cùu 23
27. n o tr÷îc â · xu§t º gi£i quy¸t cho 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. • Trong thüc t¸, vòng triºn khai m¤ng th÷íng câ c¡c ch÷îng ng¤i vªt, t¡c gi£ · xu§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 khæng çng nh§t câ r ng buëc ch÷îng ng¤i vªt. V¼ ¥y l b i to¡n NP-khâ do vªy t¡c gi£ ti¸p cªn theo ph÷ìng ph¡p gi£i x§p x¿ v · xu§t hai gi£i thuªt ti¶u biºu trong lîp c¡c thuªt to¡n metaheuristic (GA, PSO) º gi£i quy¸t. º ¡nh gi¡ £nh h÷ðng cõa c¡c y¸u tè tîi k¸t qu£ cõa b i to¡n. T¡c gi£ ¢ x¥y düng c¡c kàch b£n m¤ng phö thuëc v o tøng möc ½ch triºn khai m¤ng. K¸t qu£ thüc nghi»m cho th§y hai gi£i thuªt · xu§t cho k¸t qu£ tèt v· di»n t½ch bao phõ. Qua thüc nghi»m công chùng minh ÷ñc sü phò hñp cõa gi£i thuªt · xu§t cho b i to¡n °t ra. • Vîi b i to¡n bao phõ èi t÷ñng t¡c gi£ · xu§t hai b i to¡n: 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îi sè l÷ñng c£m bi¸n triºn khai l tèi thiºu v b i to¡n bao phõ èi t÷ñng £m b£o t½nh 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. C£ hai bai to¡n · xu§t ÷ñc chùng minh l b i to¡n NP-khâ v · xu§t c¡c gi£i thuªt heuristic (USP, UTSP, PGA v SGA) º gi£i quy¸t. T¡c gi£ trong luªn ¡n ¢ x¥y düng thüc nghi»m º ¡nh gi¡ tøng y¸u tè trong b i to¡n £nh h÷ðng ¸n k¸t qu£ cõa b i to¡n. Tø â, gióp cho c¡c nh triºn khai m¤ng c¥n nh­c quy¸t ành trong tøng ùng döng cö thº n¶n triºn khai m¤ng c£m bi¸n nh÷ th¸ n o cho ti¸t ki»m chi ph½ v thíi gian thüc hi»n. H÷îng nghi¶n cùu ti¸p Trong nhúng nghi¶n cùu ti¸p theo, t¡c gi£ ti¸p töc mð rëng nghi¶n cùu v· c¡c v§n ·: • Vîi v§n · bao phõ di»n t½ch trong m¤ng c£m bi¸n khæng d¥y câ r ng buëc ch÷îng ng¤i vªt: T¡c gi£ s³ mð rëng nghi¶n cùu gi£i quy¸t b i to¡n vîi ch÷îng ng¤i vªt l h¼nh d¤ng b§t ký. • Vîi v§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. T¡c gi£ s³ mð rëng nghi¶n cùu v· t½nh chàu léi cõa b i to¡n nh­m möc ti¶u tèi thiºu hâa sè l÷ñng nót sû döng v k²o d i thíi gian sèng cõa m¤ng º gi£m thiºu chi ph½ x¥y düng m¤ng. 24