Tóm tắt luận ánTóm tắt luận án Tiến sĩ Khoa học Máy tí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

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

Thêm vào BST

Báo xấu

61
lượt xem 3
download

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

Mục tiêu của luận án nhằm 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; 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.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận ánTóm tắt luận án Tiến sĩ Khoa học Máy tí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

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 TÂM TT LUN N TIN S KHOA HÅC MY TNH H Nëi - 2019
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
DANH MÖC CC CÆNG TRNH CÆNG BÈ CÕA LUN 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).
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 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 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. 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
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
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
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. • b i Li¶n quan ¸n v§n · bao phõ èi t÷ñng, t¡c gi£ · xu§t hai b i to¡n l 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
÷a ra ph÷ìng h÷îng ph¡t triºn ti¸p theo. CH×ÌNG 1. CÌ SÐ LÞ THUYT 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
CH×ÌNG 2. BI TON CÜC I DIN TCH BAO PHÕ TRONG MNG CM BIN KHÆNG DY KHÆNG ÇNG NHT 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 rsi vîi nhi»m vö c£m nhªn v thu thªp thæng tin tø èi t÷ñng trong vòng c£m bi¸n v b¡n k½nh truy·n l rci câ nhi»m vö k¸t nèi trong to n m¤ng, 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 coA = area cri (xi , yi ) A (2.1) i=1 vîi i·u ki»n x = (xi , yi ) ∈ A, trong â cri (xi , yi ) l h¼nh trán câ t¥m t¤i (xi , yi ) v b¡n k½nh ri . K½ hi»u 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
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
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 Dit ¤i di»n cho sü £nh h÷ðng cõa 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
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
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
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 nhc 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
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. 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 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 chn 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 = {o1 ..om }, 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 (ut1 , vt1 ) v gâc d÷îi b¶n tr¡i (ut2 , vt2 ) v ot ∩ oh = ∅, ∀t, h = 1 . . . m. B i to¡n °t ra l t¼m c¡c và tr½ (x1 , y1 ) , (x2 , y2 ) , . . . , (xn , yn ) °t c£m 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 sot (ut1 , vt1 , ut2 , vt2 ) l vòng bao phõ bði ch÷îng ng¤i vªt h¼nh chú nhªt ot . 12
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 coA = area sri (xi , yi ) A\ sot (ut1 , vt1 , ut2 , vt2 ) (3.1) i=1 t=1 vîi i·u ki»n x = (xi , yi ) ∈ A, i = 1, . . . , n; (xi , yi ) ∈ / 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
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
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 = {0%, 50%, 100%} º ¡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
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. 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 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
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 T = {(xi , yi ) | 0 ≤ xi ≤ W, 0 ≤ yi ≤ H, i = 1..n} v èi t÷ñng câ tåa ë 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 = {(x, y) | 0 ≤ x ≤ W, 0 ≤ y ≤ H}. 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, s0 ) < Rc , (4.1) f s, s = 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 . Sl Gåi F = i=1 fi l tªp t§t c£ c¡c và tr½ câ thº °t c£m bi¸n tr¶n mi·n quan t¥m A. Sm Gåi R= j=1 rj l tªp t§t c£ c¡c và tr½ câ thº °t c¡c nót chuyºn ti¸p tr¶n mi·n A. Sl+m Gåi Q= i=1 qi = {f1 , f2 , ..., fl , r1 , r2 , ..., rm } l tªp t§t c£ c¡c và tr½ câ thº °t 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