Time Efficient Unmanned Aircraft Systems Deployment in Disaster Scenarios Using Clustering Methods and a Set Cover Approach

elec onics A icle Time E icien Unmanned Ai c a Sys ems Deploymen in Disas e Scena ios Using Clus e ing Me hods and a Se Co e App oach Donald Maho o N wa i 1, Daniel Gu ie ez-Reina 1,* , Se gio Luis To al Ma ín 1and Hissam Taw ik 2   Ci a ion: Maho o N wa i, D.; Gu ie ez-Reina, D.; To al Ma ín, S.L.; Taw ik, H. Time E icien Unmanned Ai c a Sys ems Deploymen in Disas e Scena ios Using Clus e ing Me hods and a Se Co e App oach. Elec onics 2021,10, 422. h ps:// doi.o g/10.3390/elec onics10040422 Academic Edi o : Luis M. Fe nández-Ramí ez Recei ed: 29 Decembe 2020 Accep ed: 1 Feb ua y 2021 Published: 9 Feb ua y 2021 Publishe ’s No e: MDPI s ays neu- al wi h ega d o ju isdic ional clai- ms in published maps and ins i u io- nal a ilia ions. Copy igh : © 2021 by he au ho s. Li- censee MDPI, Basel, Swi ze land. This a icle is an open access a icle dis ibu ed unde he e ms and con- di ions o he C ea i e Commons A - ibu ion (CC BY) license (h ps:// c ea i ecommons.o g/licenses/by/ 4.0/). 1Elec onic Enginee ing Depa men , Uni e si y o Se ille, 3139 Se ille, Spain; [email p o ec ed] (D.M.N.); [email p o ec ed] (S.L.T.M.) 2School o Buil En i onmen , Enginee ing and Compu ing, Leeds Becke Uni e si y, Leeds LS16 5LF, UK; [email p o ec ed] *Co espondence: dgu ie [email p o ec ed] Abs ac : Unmanned ai c a , which a e mo e commonly known as d ones, a e nowadays ex ensi ely used in an e e inc easing se o applica ions. In a wide sys em, he ai c a a e usually associa ed o addi ional elemen s such as g ound-based con olle s. Fu he mo e, when hese componen s o m a ne wo k o elemen s ha can communica e, he sys em is said o o m an Unmanned Ai c a Sys em (UAS). This sys em is pa icula ly e ec i e when he ai c a wi hin a e o ganized in o swa ms wi h se s o objec i es o accomplish. The ex ensi e use o swa ms in o UASs is mo e and mo e exploi ed nowadays due o he dec easing cos o hose ai c a . In he p esen wo k we a e in e es ed in a pa icula applica ion o UASs, namely hei deploymen in disas e scena ios o communica ions se ices p o ision o a ge s on he g ound. These g ound a ge s, howe e , a e no pa o he UASs and should no be con used wi h g ound-based con olle s. The p esen wo k does no only ocus on co e age o g ound a ge s bu also on a gua an eed minimum numbe o co e s o each a ge , which is called he edundancy equi emen . The esea ch wo k also ensu es ha he deployed UAS o ms a unique connec ed componen so ha a s eady s eam o communica ion is kep wi h he a ge s o co e . Resea ch wo k simila o he p esen pe o m he ini ial deploymen o hei ai c a in a di e en manne , ei he andomly, based on a p ede e mined g id o ma ion, o using o he elabo a ed me hods. This wo k p oposes a new solu ion based on he use o clus e ing algo i hms, combined o a design o he p oblem o mula ed as a se co e op imiza ion model. The clus e ing phase is used o disc e ize he sea ch space and ease he op imiza ion phase by loca ing egions o in e es , and hen a u he p ocedu e is applied, only when needed, o econnec sca e ed connec ed componen s and gua an ee connec i i y in he ne wo ks. This way o doing i has achie ed a deploymen o UASs wi h maximum co e age o all a ge s, a gua an eed minimum numbe o co e s o each o hem, and esul s in a compe i i e compu a ion ime. The la e also allowed o mo e scalabili y by ex ending he es s o e y la ge inpu ins ances. Keywo ds: disas e managemen ; unmanned ai c a sys ems; clus e ing algo i hms; se co e app oach 1. In oduc ion I is always a complica ed ask o know how se ious a disas e scena io can be. Nobody can con iden ly asse ha he consequences o an a e ma h can be con olled. I can e en be mo e d ama ic when he e a e people apped in isola ed c owds ha a e unable o use hei communica ion de ices, o en because o loss o ne wo k co e age. I has indeed been epo ed ha in disas e scena ios people a e usually unable o use hei mobile and/o sma -phones in a no mal way [ 1 , 2 ]. In o de hen o p e en such ha dship, a lo o e o has been used o p o ide e icien esponses, and among hose we ind he use o Unmanned Ai c a Sys ems (UASs), sugges ed o elie ope a ions in disas e scena ios [3,4] and e ec i e o moni o di icul - o-access egions [5]. Elec onics 2021,10, 422. h ps://doi.o g/10.3390/elec onics10040422 h ps://www.mdpi.com/jou nal/elec onics Elec onics 2021,10, 422 2 o 26 O iginally, UASs wi h a single ai c a we e in oduced. Howe e , due o signi ican echnological ad ancemen s, pa icula ly imp o emen s in wi eless communica ion, he swa m in he UASs became la ge , and wi h i he numbe o missions o accomplish. Wi h hese ad ancemen s he UASs we e, o example, able o ac as access poin s o use s making calls o connec ing o he In e ne [ 6 , 7 ]. One such applica ion can o ins ance be ound in he deploymen o UASs o p o ision o eliable communica ion se ices o ixed a ge s on he g ound [8]. In his wo k, we conside hese kinds o applica ions whe e he goal is o deploy a UAS o communica ion se ices p o isions o a ge s on he g ound. Al hough he e m ai c a (o e en Unmanned Ae ial Vehicles (UAVs)) is mo e widely used by he public, o icial ins i u ions such as he In e na ional Ci il A ia ion O ganiza- ion and he Single Eu opean Sky Ai -T a ic-Managemen Resea ch Join , ha e adop ed Unmanned Ai c a Sys ems as he e minology ha be e emphasizes he impo ance o elemen s o he han jus he ai c a (g ound con ol s a ions, da a links, e c.). Fo ins ance, in ou con ex , g ound-based con ol s a ions could be added o he UAS, and would egu- la ly assemble new upda es abou he posi ions o mo ing g ound a ge s in o de o decide on new deploymen s. Howe e , gi en ha he ansmission ange o ai c a is usually high wi h espec o he expec ed mobili y o g ound nodes, and also ha in a disas e scena io con ex mos people a e apped, he expec ed mobili y would be mode a e and hus he changes be ween upda es. Conside ing hen he deploymen o UASs o communica ion p o ision o g ound a ge s in a disas e scena io, a minimum gua an ee o eliable se ices is equi ed. Wi h hen he aim o es ablishing minimum condi ions o sa e communica ion, he p esen wo k mainly ocuses on wo equi emen s: he co e age and edundancy equi emen s [ 9 ]. These wo equi emen s ha e o espec i e conce n: (1) o maximize he numbe o a ge s co e ed, and (2) o s eng hen he abili y o a g ound node o s ay co e ed in he e en o ai c a ailu e. Fu he mo e, o a lesse ex en , he esea ch wo k also conside s a sha ing o wo k be ween he ai c a in case o conges ion. This edundancy equi emen is also o en e e ed o as he k-co e age p oblem [ 10 ], whe e k is he minimum numbe o co e s equi ed o each a ge . Fu he mo e, al hough he co e age equi emen is conside ed as he mos signi ican objec i e in his wo k, he edundancy is also p o i able o wo al eady a o emen ioned easons: (1) a g ound node co e ed mo e han once can s ay co e ed in he e en o co e s ailu e, (2) a hea ily cha ged ai c a can be elie ed o some g ound a ge s and ans e hem o o he ai c a . We hen ocus on p o iding me hods o he wo componen s a he same ime: co e age and edundancy equi emen . This wo k is con ibu ing o he esea ch by p oposing a new s a egy o dealing wi h he deploymen o UASs, consis ing in: inding good and limi ed po en ial loca ions o ai c a placemen s, and il e hem by sol ing a se co e p oblem combining bo h he co e age and he edundancy equi emen in o a single mono-objec i e model. The app oach consis s o wo p incipal p ocedu es: (1) apply clus e ing me hods o gene a e loca ions in o a eas o in e es . These loca ions a e ob ained by i e a i ely conside ing sho e anges o ai c a , which adds di e si y in he sea ch space. (2) un he op imiza ion phase o u he il e he gene a ed loca ions and keep he ones ha sa is y he bes he co e age and edundancy equi emen s. Finally, when bo h he co e age and edundancy cons ain s a e sa is ied, an addi ional ou ine is applied, only when necessa y, ha builds a single connec ed componen in o de o sa is y he connec i i y o he esul ing ne wo k. Wi h his app oach, we we e able o achie e good esul s in a compe i i e compu a ion ime: ull co e age o all he a ge s, a gua an eed k-co e age, and he connec i i y o he o e all UAS. Plus, since he solu ion p o ided esul s e y as o ins ances o mode a e size, i allowed us o expand he es s and scale he solu ion o much la ge sea ch space, bo h on he numbe o a ge s o co e and on he size o he map. This epo is s uc u ed as ollows: ela ed wo k is p esen ed in Sec ion 2and a o mal desc ip ion o he ask unde conside a ion in Sec ion 3. We a e p esen ing in Sec ion 4ou Elec onics 2021,10, 422 3 o 26 p oposed app oach: he selec ed o mula ion o he p oblem (Sec ion 4.1) and de ails on he app oach we adop ed o gene a e he equi ed SCP ins ances (Sec ion 4.2). In Sec ion 5 we p o ide de ails on how he edundancy equi emen is inco po a ed in he model and desc ibe how we managed o gua an ee he connec i i y o ou ne wo k. We p esen in Sec ion 6 he esul s o ou expe imen s, plus addi ional es s o he scalabili y o he solu ion, and we inally conclude in Sec ion 7. 2. Rela ed Wo k The e is al eady a conside able amoun o ma e ial a ailable on he subjec o deploy- men o UASs. I is an issue ha has been ho oughly s udied, and many solu ions a e al eady a ailable o se e al o i s componen s, co e age in pa icula . Fo ins ance, se e al app oaches simila o ou s a e using clus e ing algo i hms o ind app op ia e posi ions o he UASs. In [ 7 ], he au ho s use clus e ing me hods o deploy hei UAS in a con ex whe e ai c a a e used o complemen mac ocell in as uc u es in egions wi h high a ic o use equipmen . In hei wo k, he au ho s use he K-means clus e ing algo i hm o deploy a p ede ined numbe o ai c a , which is unc ion o he numbe o a ge s o o load om he mac ocells and he maximum numbe o a ge s ha can be simul aneously o loaded by a single ai c a . They subsequen ly seek mac ocells wi h high numbe s o use equipmen connec ed o hem, while also compu ing he dis ance o hese mac ocells o he ai c a so ha hey can iden i y mac ocells o o load i s . In ou wo k we also conside his capaci y cons ain o he ai c a , e en hough i is no explici ly men ioned. Fo us, when an ai c a is o e loaded, we p o ide a solu ion o ease conges ion by cons aining a ge s o be co e ed wi h mo e han one ai c a . Thus making possible he sha ing o bu den in he UASs. In a mo e ecen wo k [ 11 ], he au ho s p opose a mul iobjec i e op imiza ion model which seeks o minimize he numbe o deployed ai c a while minimizing he da a a e dissa is ac ion o elays. In his esea ch wo k, he idea ele an o ou pu pose is o ake ad an age o he posi ion o g ound a ge s o educe he sea ch space. The au ho s use a con ex hull en elope o educe hei sea ch space and posi ion hei UASs in o a mesh o ma ion on which hey can apply gene ic modi ica ions using he NSGA-II eli is mul iobjec i e e olu iona y algo i hm. The use o he mesh ne wo k allows hem o easily apply gene ic modi ica ions while keeping he o e all UAS connec ed. This wo k is also simila o ou se co e model in he ac ha hei model has elemen s common wi h ou model o e e ence: one o hei wo objec i es is o minimize he numbe o used ai c a while cons aining a leas one o hem o co e each g ound node. The model, howe e , has i s own speci ici y and canno be p esen ed as jus a mul iobjec i e p oblem in eg a ing a se co e model. Simila ly o he wo a o emen ioned wo ks [ 7 , 11 ], ou app oach also akes ad an age o he posi ions o g ound a ge s o in e sui able posi ions o ai c a o be placed. Howe e , unlike hese wo ks, ou wo k does no impose any p ede ined numbe o pa i ions no en o ce a p ede ined ne wo k o ma ion. We a he use di e en me hods mainly consis ing in gene a ing as many a ied po en ial pa i ions as i is possible o ind. We hen gi e he UASs he possibili y o ha e a nonde e minis ic o ma ion. Ou app oach can hen be seen as mo e dynamic. Each o he p eceding choices ha e bo h ad an ages and d awbacks, pa icula ly when used o ou speci ic p oblem. In [ 7 ], applying a dynamic sea ch, ha is he a io o he numbe o use equipmen (g ound a ge s) needed o o load, o he maximum capaci y o ai c a , can a oid many ha dships. Howe e , i he e is mo e use equipmen ound in a gi en pa i ion han an ai c a can handle, he e can ne e be o e laps o co e age. Tha means ha only one ai c a can be deployed a he exac coo dina es o one cen oid (Vo onoi cell), unless se e al ai c a a e deployed a hese p ecise coo dina es. In o he wo ds, only he amoun o use equipmen ha a single ai c a can handle can be o loaded. Fo ou pa , we app oach he ma e di e en ly and use a dynamic assignmen o he Elec onics 2021,10, 422 4 o 26 numbe o ai c a s o deploy. We we e able o ind a way o gene a ing se e al di e en po en ial loca ions o he UAS, e en in he coo dina es al eady gene a ed o some ai c a . Fo [ 11 ], e en hough deploying a mesh ne wo k in a educed sea ch space can be bene icial on many poin s, in some cases his can cos a lo and no p o ide any imp o e- men . Tha is he case when he a ge s o co e a e la gely sp ead o e he map, o when he e a e la ge gaps be ween dis inc connec ed componen s. Fo example, in ou es ins ance o Sec ion 6 ha can be isualized in Figu e 1, we ha e 125 g ound a ge s in ed, mainly agg ega ed in o ou egions bu la gely sp ead o e he map. I we had used he app oach o enclosing he sea ch space in o he con ex hull o he a ge nodes, and placed he po en ial placemen poin s o he UAS in a g id layou whe e he dis ance be ween wo placemen s is equal o he ange o he ai c a , jus only one placemen poin on he bo om igh o he map ( he ed poin ) would ha e been disca ded. Mo eo e , depending on he dis ance used o ix neighbo ai c a in he UAS mesh ne wo k, a lo o hem would be needed jus o connec ing he gaps be ween he sepa a ed connec ed componen s, wi hou co e ing any g ound a ge a all. The con ex hull sea ch space educ ion would ha e e u ned oughly he en i e map. Figu e 1. Candida es o ai c a placemen as a mesh ne wo k wi hin a con ex hull. Ano he in e es ing wo k is [ 12 ]. In his esea ch wo k, he au ho s ha e de eloped a biobjec i e linea model whe e one o he objec i e is o minimize he deploymen cos o he UASs, and he o he is o ind he bes al i ude o an ai c a ha p o ides he bes co e age. Thei model is also cons ained o main ain ull co e age o he a ge s on he g ound, as well as a connec i i y cons ain in he esul ing UASs. In hei expe imen s hey conside a 3D en i onmen sea ch space whe e he ai c a can ha e di e en al i udes bu need o s ay in ange o co e age and communica ion equi emen s. Howe e , as in [ 11 ], he UAS is placed in a g id o ma ion. Fu he mo e, in spi e o gua an eeing he connec i i y o he UASs, hese a e s ill deployed in a a he igid manne ha can be e y expensi e when he di e en connec ed componen s a e a apa . Elec onics 2021,10, 422 5 o 26 The p oblem we a e dealing wi h is also o be ound in o he domains ela ed o ou subjec . I is indeed he case ha di e en communi ies a e ac i ely endea o ing o ackle he co e age p oblem and alike issues. Fo ins ance, he co e age p oblem is widely s udied in esea ch o wi eless senso ne wo ks. A la ge collec ion o gene ic ([ 10 , 13 ]) and e olu iona y solu ions ([ 9 , 14 ]) ha e been sugges ed o sol e he co e age p oblem and o he simila objec i es. Likewise, exac app oaches ha e also been used join ly wi h heu is ics o sol e o example he ne wo k li e ime maximiza ion p oblem ([ 15 , 16 ]). This la e objec i e is no o p o ide simul aneous co e age bu o maximize he o al amoun o ime du ing which he a ge s a e co e ed. This kind o p oblem is usually sol ed using a s a egy o deploying mo e senso s han ac ually needed so ha hey can be able o swi ch be ween ac i e and do man senso s [16]. None heless, i seemed o us ha many o hese wo k would ha e been e en mo e p oduc i e i hey had s a ed wi h be e ini ial solu ions. In mos o hese wo ks he ini ial deploymen is pe o med ei he andomly ([ 9 , 16 ]), using p ede e mined o ma ion ([ 11 ]) o h ough he use o mo e sophis ica ed me hods, such as he Mon e-Ca lo me hod ([ 13 ]). So, u he o he conce n o inding good deploymen s o s a wi h, we we e able o p o ide an app oach ha inds good ini ial posi ions based on he coo dina es o he g ound nodes o co e . We suppose hen ha , p io o he deploymen , a scan o he sea ch space has been accomplished o collec he posi ions o all he g ound nodes. Fo ins ance, in [ 17 ], he au ho s use a pa icle swa m op imiza ion based app oach o as - ack posi ions o a ge nodes wi h po en ial con e gence in o a eas wi h high amoun o a ge s. Fu he mo e, in he same spi i , he e a e o he solu ions ha could help de ec o app oxima e he posi ions o isola ed g ound a ge s wi hou being able o p o ide he ull se ices ha a UAS could. Using sa elli e images o low cellphone signal de ec ion wi h a sweep o he sea ch space can gi e a close ep esen a ion o he posi ions o he a ge s. The o he c i e ion ela ed o p ac ical conside a ions o UASs deploymen s in disas e scena ios is o ake in o accoun he cos o physical equipmen . High p ecision ma e ial o p oblems such as he one a hand a e s ill a om being e y accessible. Mili a y and scien i ic g ade na iga ion sys ems a e he only ones able o p o ide e y good accu acy and small e o a e e en o non s a ic objec s acking. Howe e , hey o en come a a e y high cos . Mo e common and cheape equipmen on he o he hand a e less eliable and usually subjec o dis up ions. So, depending on he accep able deg ee o accu acy equi ed by he deploymen , ha di e ence should always be emembe ed. As a conclusion, when we compa ed ou esea ch wo k o hose seen p e iously, we could see om expe imen s ha we ha e ye o imp o e ou app oach in ackling he connec i i y issue. Indeed, ou goal being o ensu e i s ull co e age and edundancy o he a ge nodes, he connec i i y issue is ackled only a e wa ds and only i necessa y. The me hod used o ha ma e can be pe cei ed as oo s aigh o wa d as i seeks o connec he sp ead componen s by i e a i ely linking he wo closes . S ill, e en wi h his simple me hod we we e able o ob ain as esul s o ully connec ed UASs wi h ull co e age o a subs an ial numbe o a ge s sca e ed o e la ge maps. 3. P oblem Desc ip ion P esen ed b ie ly, he p oblem we in end o sol e consis s in deploying UASs o moni o (o co e ) as many g ound a ge s nodes as possible. We also assume ha he size o he sea ch space ( he map) is known, and he posi ions o he g ound a ge s oo (gi en by hei coo dina es). Fo he objec i e o ou model, we need o co e all he g ound nodes wi h a minimum numbe o ai c a . Fu he mo e, in o de o s eng hen he co e s we also en o ce as a cons ain a edundancy ea u e (o k-co e age), ha ensu es each a ge is co e ed wi h a leas k co e s. Mo e o mally, we ha e a se U o kpo en ial loca ions a ailable o he deploymen o he UAS: U={u1 , . . . , uk} wi h hei espec i e coo dina es (xu1 , yu1) , . . . , (xuk , yuk) . The g ound nodes (o a ge s), o co e a e gi en by a se T o size n: T={ 1 , . . . , n} wi h ixed coo dina es (x 1 , y 1) , . . . , (x n , y n) wi hin he limi s o a wo-dimensional map. Elec onics 2021,10, 422 6 o 26 E e y po en ial loca ion o U can only be es ablished wi hin he bounda ies o he map, and we also assume a ansmission ange angei o e e y such loca ion i∈U , ha allows an ai c a assigned o ha loca ion o co e g ound nodes wi hin ha ansmission ange, o communica e wi h o he ai c a in o he loca ions. We hen ha e an undi ec ed g aph G(V , E) , whe e V=T∪U , and E is he se o edges exp essing whe he he e is a connec ion a ge -ai c a o ai c a -ai c a . An edge is a pai (i , j)∈E , indica ing whe he a g ound node is co e ed by an ai c a si ua ed a a gi en loca ion, o i wo ai c a assigned o wo di e en loca ions can sha e in o ma ion. Such edges exis ei he i (1) i∈U , j∈T and j is in he co e ing ange o i ( j is co e ed by i ); o (2) i , j∈U and bo h ai c a a e in he ansmission ange o each o he . To his end, we use he disk model, o Boolean disk co e age model ([ 13 , 18 ]), o assess whe he ei he o he condi ions abo e hold: i∈U,j∈T,jis co e ed by ii : dis ance(i,j)< angei(1) i,j∈Ucommunica e i :dis ance(i,j)<min angei angej(2) The conside ed dis ance is he usual Euclidean dis ance: q(xi−xj)2+ (yi−yj)2 , whe e (xi , yi) , (xj , yj) a e he espec i e coo dina es o i and j . And o symme y b eaking pu poses, i a g ound node is co e ed by an ai c a loca ed a u hen (u , )∈E and ( , u)6∈ E ; and i wo ai c a a loca ion up and uq a e in he ange o each o he , hen (up,uq)∈E o p<q, and (uq,up)6∈ E. Rega ding he edundancy equi emen , a g ound node iis said o ha e a edundancy, o accessibili y o p, i i can be co e ed simul aneously om pdi e en ai c a . One way o compu ing he o al edundancy o he deploymen o he UAS is, o each a ge o sum he numbe o deployed ai c a ha co e i . In [ 9 ] o ins ance, he au ho s encoded such measu emen , ha hey op imized unde a mul iobjec i e model. The op imiza ion exp ession can be ansla ed in ou no a ion wi h (3), whe eas i he exp ession is only needed o measu emen pu poses, (4) can be used. In ou model, zu is used as a decision a iable s a ing whe he a gi en ai c a is ac i a ed a he po en ial loca ion u in he deploymen . max ∑ ∈T (∑ (u, )∈E|u∈U zu)(3) o ∈T, edundancy( ) =∑ (u, )∈E|u∈U zu(4) In he p esen wo k, we chose a di e en app oach han using he edundancy as a speci ic objec i e in a mul iobjec i e p oblem. We p opose a simple mono-objec i e SCP app oach consis ing in minimizing he numbe o deployed ai c a in he UAS while gua an eeing a minimum edundancy o he a ge s. Fu he mo e, al hough (3) is no explici ly included in he model, i is used in Sec ion 6as a means o measu emen o e alua e ou expe imen s. As s a ed, ou wo k ocuses mainly on he co e age and edundancy ma e s. E en hough he connec i i y cons ain is also en o ced on ne wo ks, his s ep is pe o med a e ob aining a deploymen ha sa is ies he wo a o emen ioned cons ain s. I is only hen ha we apply an addi ional ou ine o connec all he sp ead connec ed componen s. We a e ully awa e o how icky he connec i i y equi emen can be. Al hough he connec i i y cons ain is an essen ial componen o all he esea ch wo k p esen ed in Sec ion 2, i is always a he expense o ei he he deploymen cos (numbe o used ai c a ), he quali y o he co e age, o e en he ime cos : whe eas he s i mesh deploymen o [ 11 , 12 ] causes a deploymen o mo e han needed ai c a o keep he connec i i y, he clus e ing app oach o [ 7 ] does no allow o a ull co e age in some cases. Fu he mo e, compa ed o hese wo ks, he p oposed solu ion a o s inpu ins ances wi h much la ge a ge s o co e and p o ides esul s in much as e ime. Hence, he s aigh o wa d me hod used o connec i i y does no unde mine he esul s o he solu ion. Elec onics 2021,10, 422 7 o 26 In he nex sec ion we p esen he se co e in ege model used o sol ing ou p oblem, be o e we can de ail how he ins ances o he Se Co e P oblem we e ob ained. We made ha choice o i s gi e an in dep h p esen a ion o he app oach selec ed o sol ing ou p oblem, and hen show how we managed o ob ain he inpu da a. 4. P oposed App oach 4.1. Se Co e ing Op imiza ion P oblem Fo mula ion Gi en he p oblem desc ibed in Sec ion 3, he p oposed se co e ing p oblem o mula- ion is s a ed in (5)–(7). I is an In ege P og amming p oblem (IP p oblem) whose objec i e unc ion (5) is o ac i a e o deploymen he minimum numbe o ai c a (o co e s), o comple e hei mission. ai c a loca ions a e ac i a ed o deploymen h ough he use o a se o in ege decision a iables s a ed in cons ain (7) whe e: a gi en ai c a is ac i a ed o deploymen a loca ion u∈U when zu= 1, o he wise, no ai c a is deployed a his posi ion ( zu= 0). The edundancy es ic ion o co e ing a ge s wi h a gi en minimum numbe po ai c a is s a ed in cons ain (6). min ∑ u∈U zu(5) s. . ∑ (u, )∈E|u∈U zu≥p,∀ ∈T(6) zu∈ {0, 1} ∀u∈U(7) This model is no always easy o sol e. I is a ha d p oblem in i sel (NP-Comple e [ 19 ]), which is added o he ac ha IP p oblems a e ha d a some poin compa ed o hei linea coun e pa s [ 20 ]. IP p oblems a e usually sol ed based on he esul s o hei linea elaxa ions, which consis s in loosening some o all o he in ege cons ain s by allowing hem o be con inuous. One simple such s a egy is o elax he in ege a iables, sol e he linea p oblem, and ansla e back he linea p oblem o i s o iginal IP e sion by ixing he con inuous alues o hei closes in ege s. Howe e , i is an o e simpli ica ion a he expense o quali a i e esul s. Fo he mos pa , and in spi e o ensuing longe unning ime, IP/MIP sol e s usually p o ide be e s a egies o sol ing he p oblems o de ec ea lie un easible ins ances. S ill, due o he combina o ial explosion o IP p oblems, p ecau ions a e o be aken so as o no make he p oblem ha de om he s a . Some p ocedu es used in IP sol e s, such as enume a ion app oaches, b anch-and-bound, o cu ing-plane echniques, a e indeed e y sensi i e o g ow h in size. Enume a ion me hods a e ime-consuming when building and sea ching h ough la ge b anching ees needed o check he possible solu ions, and cu ing planes, in some ins ances, gene a e subs an ial cu s o ind in ege op imums, leading o leng hy ope a ions. Fo una ely, o he echniques a e used o ease he p ocess, among which is he use o heu is ics. Fo ou pu pose, a he han using heu is ics o sol e IP p oblems e icien ly, we chose o use hem o gene a e good inpu alues o he IP/MIP sol e . Ou solu ion p oduces inpu da a o limi ed size ha a e used o sol e he p oblem wi h an IP/MIP sol e . We we e cau ious no o p oduce oo many loca ions oo big o he sol e . Ou app oach gene a es limi ed posi ions a ound a eas o in e es , by lea ning om he posi ions o he a ge s. In his pape , due o he ac ha we a e using a se co e app oach, we o en e e o he gene a ed loca ions as co e s. Ins ead o andomly gene a ing hese co e s hen, we p opose a solu ion ha p oduces limi ed numbe s o hem ha a he e y leas will ne e be emp y, as migh happen in andom p ocedu es. Su ely, he e would be no eal ad an age o using he SCP model i we we e no able o p o ide smalle and good inpu ins ances o he sol e . The isk wi h andom gene a ions is ha no only a lo o gene a ed co e s a e usually no aluable enough, bu i can also be ha d o ind he app op ia e numbe o co e s o gene a e and ind an easy ins ance o he sol e . In o he wo ds, he e a e oo ew co e s— he esul Elec onics 2021,10, 422 8 o 26 migh miss aluable choices, po en ially leading o un easible solu ions—, and oo many co e s —and he ins ances could lead o an in ac able p oblem. In he o me case, i is e en possible o ha e andomly gene a ed co e s wi h no a ge s co e ed a all. Wi h ou app oach we p opose a me hod ha always ind co e s wi h a ge s wi hin and ha a e ne e emp y. In he nex sec ion we desc ibe wi h mo e de ails how hese disc e e ins ances a e ound. 4.2. Gene a ing SCP Ins ances As s a ed be o e, in i s aw o m, only he coo dina es o he g ound nodes a e known; hus, he e is no co e a ailable ye (ins ances) o he SCP sol e . In o de o ans o m aw da a in o SCP ins ances, we pe o med a p ep ocessing using clus e ing me hods: o g oup a ge s in o clus e s o di e se sizes. These clus e s (co e s), a e ci cula a eas o adius he ange o he ai c a . Fo simpli ica ion, a his poin we suppose ha all he ai c a in he UAS ha e he same ange. Fu he mo e, gi en ha in he beginning he numbe o needed co e s is no known, we use a clus e ing algo i hm known as he single pass algo i hm [ 21 ] in o de o ind i . As a esul , we also ob ain he coo dina es o he ep esen a i es o cen oids o he clus e s. These ep esen a i es a e poin s in he map such ha he dis ance o a g ound node in a gi en clus e o i s ep esen a i e ( he ai c a loca ion in ou case) is s ic ly less o a gi en h eshold ( he ange o he ai c a ). This ep esen a i e is also he closes compa ed o o he ep esen a i es: i a a ge i belongs o a clus e uj , hen, om (1): (uj, i)∈E, and he e is no o he clus e ulsuch ha dis ance(ul, i)<dis ance(uj, i). The single pass algo i hm is gi en in Algo i hm 1. In sho , he algo i hm scans once o e he whole se o g ound nodes and o each g ound node seeks he closes ep esen a i e in ange and assigns i o ha clus e . I no ep esen a i e is close enough, hen a new clus e is c ea ed wi h he cu en a ge as i s ep esen a i e. Algo i hm 1begins by conside ing he i s ead g ound node as he i s ep esen a i e and as he only node in he i s clus e . I hen epea s he upda ing s ep un il all g ound nodes a e o ganized in o clus e s. The upda ing ule o he ep esen a i es consis s in compu ing mean ec o s o he poin s wi hin each clus e . In he algo i hm, Ccloses _ ep ep esen s he closes clus e o he cu en a ge l ; Vcloses _ ep is he cen oid o he closes clus e ; and d∈Ccloses _ ep is e e y a ge in clus e Ccloses _ ep . A he end, we ha e Kclus e s, wi h K≤N , whe e N is he numbe o a ge s o collec in o clus e s. I is gua an eed ha i we assign Kai c a o he coo dina es o he ep esen a i es o each clus e , hen all he g ound nodes will be co e ed. The complexi y o Algo i hm 1is polynomial ( 1 2N(N+ 1 ) , o O(N2) ), wi h he wo s case occu ing when he e a e as many clus e s as he e a e g ound nodes (K = N). This happens when he dis ance be ween he wo closes g ound nodes is highe han he highes h eshold. I is use ul o no e ha e en hough his si ua ion is in eali y less likely o occu , he algo i hm p o ides o ha scena io he op imal maximum co e age, as he e is no be e solu ion han o deploy as many ai c a as he e a e g ound nodes i he objec i e is a maximum co e age o he g ound nodes. I is also impo an o poin ou ha excep o his wo s case scena io, he algo i hm can ne e deploy all he ai c a a he exac posi ion o he a ge s. Some commen s should be made abou he esul s o he algo i hm. Fi s , al hough us- ing he single pass clus e ing me hod has ad an ages such as gene a ing disc e e ins ances, i also has laws. Indeed, he o med clus e s and hei ep esen a i es a e dependen o he o de in which he nodes a e ead [ 22 ]. None heless, he esul ing numbe o clus e is a good indica o o s a wi h. Plus, now ha he needed numbe o clus e s is app oxima ed, he algo i hm can be supplemen ed wi h be e clus e ing me hods, such as he k-means algo i hm, o imp o e he alues o he ep esen a i es. Elec onics 2021,10, 422 9 o 26 Algo i hm 1 Single pass algo i hm 1: Inpu s: T={ 1, . . . , N} he se o N a ge coo dina es. 2: K←1 3: CK={ 1}// The clus e s and hei con en s 4: VK={ 1}// The ep esen a i es o each clus e 5: o l∈ {2 . . . N}do 6: smalles _dis ←min 1≤j≤Keuclidian_dis ance( l,Vj) 7: closes _ ep ←a gmin 1≤j≤K euclidian_dis ance( l,Vj) 8: i smalles _dis ≤ ange hen 9: Ccloses _ ep =Ccloses _ ep ∪ { l} 10: Vcloses _ ep =1 |Ccloses _ ep |(∑ d∈Ccloses _ ep d) 11: else 12: K←K+1 13: CK={ l} 14: VK={ l} 15: end i 16: end o 17: Re u ns: Va se o K ep esen a i es (po en ial loca ions o ai c a ) and C he pa i ions o g ound nodes (co e s). Second, and ela ed o he i s ema k, he single pass algo i hm and k-means a e ha d-clus e ing algo i hms, ha assign each g ound node o only one single clus e . Tha somehow makes hem no app op ia e o ou pu pose. Indeed, because o he edundancy equi emen , we alue mo e a ge s ha a e p esen in di e se co e s. We could use a so -clus e ing algo i hm ha would allow g ound nodes o belong o di e en clus e s a he ime. Howe e , i u ns ou ha he ime complexi y o a classic so -clus e ing algo i hm canno ge any be e han using a ou ine ha simply checks whe he a g ound node is in he ange o a gi en ai c a : using a k-means ype algo i hm o imp o e he posi ion o ep esen a i es and combine i o a sub ou ine ha pai s each g ound node o accessible ep esen a i es, he o e all complexi y sums up o TNK +NK ( O(TNK) ), wi h T he numbe o i e a ions needed o each he ole able e o ange ( he s opping c i e ion). While on he o he hand, he complexi y o a so -clus e ing algo i hm, like uzzy c-means, is O(TNK2)[23], wi hou aking in o accoun he dimension o he p oblem. Finally, and simila ly o he second poin , since he e a e o he objec i es ha need o be op imized, building s i co e s is no eally aluable o he di e si y o he solu ion. Wi h he igh esul s ob ained wi h ha d clus e ing algo i hms, we migh end up using Elec onics 2021,10, 422 16 o 26 ollow he di e en s eps o he app oach. Wi h hese ins ances i was easie o con ol he esul s g aphically, simple o iden i y and manipula e he di e en s eps he solu ion goes h ough, and was also possible o compa e he esul s wi h o he benchma ks. Fu he mo e, in o de o assess he eliabili y o ou solu ion, we assumed necessa y o examine how i esponded on mo e challenging ins ances and how i s un- ime cos beha ed on g adually inc easing numbe s o a ge s o co e . Tha is why we implemen ed he second se ies o expe imen s. The simula ions pa ame e s o he i s and second se ies o expe imen s a e sum- ma ized in Table 1. In he i s se ies he e a e i e ins ances wi h di e en dis ibu ion o a ge s con ained wi hin a map o a ea dimension 1000 × 1000 m 2 . In addi ion, o all hese ins ances he ai c a a e conside ed o ha e a ange o 125 m. The ins ances consis o 50, 75, 100, and 125 a ge s o co e , plus an addi ional ins ance o 50 a ge s wi h all a ge s isola ed, used o cons ain he solu ion on he speci ic ask o econnec ing he di e en connec ed componen s. The dis ibu ions o a ge s in he di e en ins ances a e p esen ed om Figu e 6a–e, whe e he posi ions o he g ound nodes a e ma ked in ed. The ins ances wi h 50, 75, 100, 125 g ound nodes a e espec i ely ep esen ed om Figu e 6a–d , while Figu e 6e p esen s he dis ibu ion o he special case whe e all he g ound nodes a e isola ed. Table 1. Simula ion pa ame e s o he wo se ies o expe imen s. Simula ions Pa ame e s Simula ion 1 Simula ion 2 A ea dimensions 1000 m ×1000 m (see Table 2) Numbe o ins ances 5 6 se s o 20 ins ances each Numbe o a ge s pe ins ances [50, 75, 100, 125, 50] (see Table 2) Mobili y o g ounds nodes s a ic s a ic Range o ai c a 125 m 125 m The second se ies o expe imen s on he o he hand consis o six se s o 20 ins ances each. Fo he wen y ins ances in each se , he numbe o a ge s o co e is inc easingly ge ing la ge : om 50 a ge s, and g owing e e y ime by 50 mo e a ge s, un il an ins ance o 1000 a ge s is eached (50,100,150, . . . ,900,950,1000). The di e ence be ween he ins ances in he se s esides in he dispe sion o he a ge s which is g owing wi h each consecu i e se . This second se ies was made o challenge he applica ion and de ec he con igu a ions ha a e ha de o handle, bu also, since he goal is o ge as close as possible o ealis ic scena ios, o use ins ances wi h nume ous and sepa a e a ge s, as i is usually he case in eal-li e. In ha ega d hen, he gene a ed 20 inpu ins ances in each se s we e o ganized such ha hey we e g owing la ge in numbe bu also such ha he dispe sion in each se was highe compa ed o i s p e ious. In o de o demons a e ha he dispe sion was indeed expanding, we calcula ed he s anda d de ia ion o he a ge s in each o he 20 ins ances in he se s, and hen calcula ed he qua iles o hese s anda d de ia ions needed o d aw he box-plo s in Figu e 7(see Table 2). The dispe sion is indeed expanding wi h each successi e se s, he in e qua ile ange is ela i ely he same o all he se s, and he e a e no ou le s. Table 2. Simula ion pa ame e s o second se ies o expe imen s. 2nd Simula ion Pa ame e s Numbe o Ins ances (Numbe o Ta ge s pe Ins ance) A e age A ea Dimensions Qua iles o S anda d De ia ions o Ta ge s in Ins ances (1s Qua ile, 2nd, and 3 d) se 1 20 ({i×50 a ge s |1≤i≤20} ) 871.6 m ×866.9 m 178.11, 230.34, 284.21 se 2 20 ({i×50 a ge s |1≤i≤20} ) 1210.5 m ×1212.1 m 271.88, 331.50, 382.89 se 3 20 ({i×50 a ge s |1≤i≤20} ) 1564.6 m ×1568.2 m 375.19, 434.08, 508.99 se 4 20 ({i×50 a ge s |1≤i≤20} ) 1915.6 m ×1912.1 m 489.15, 534.49, 603.94 se 5 20 ({i×50 a ge s |1≤i≤20} ) 2265.9 m ×2263.5 m 612.87, 660.76, 697.05 se 6 20 ({i×50 a ge s |1≤i≤20} ) 2609.3 m ×2609.9 m 705.20, 747.64, 809.67 Elec onics 2021,10, 422 17 o 26 (a) Ins ance 1: 50 g ound nodes (b) Ins ance 2: 75 g ound nodes (c) Ins ance 3: 100 g ound nodes (d) Ins ance 4: 125 g ound nodes (e) Ins ance 5: 50, all isola ed g ound nodes Figu e 6. Dis ibu ion o he di e en es ins ances. Elec onics 2021,10, 422 18 o 26 Figu e 7. Fo each es se used o scalabili y analysis (se 1 o se 6): he box-plo s o he s anda d de ia ion o he a ge s in each o he 20 inpu da a (50 a ge s o 1000 a ge s). 6.2. Simula ion Resul s 6.2.1. Resul s o Fi s Se ies o Expe imen s Fo he i e di e en ins ances in he i s se ies o expe imen s, and o he alues o p= 1 and p= 2 o (6), he applica ion p o ided solu ions sa is ying all he cons ain s: co e age, edundancy, and connec i i y; in less han 1 decisecond. Table 3p esen s he esul s o he applica ion on he i e inpu ins ances, execu ed wi h di e en alues o p . The able p o ides he numbe o loca ions gene a ed on each o he h ee s ages o he applica ion: (1) he clus e ing phase ha inds egions o in e es a ound he a ge nodes; (2) he op imiza ion phase ha il e s he loca ions gene a ed in he i s phase and keep hose ha minimize he objec i e unc ion (5), subjec o he cons ain s; (3) when necessa y, comple e co e age and edundancy wi h he connec i i y cons ain . The numbe o ai c a in he i s phase does no change o di e en alues o p since in ha phase p is no ele an . Table 3also p o ides he alue o edundancy o he o e all ne wo k. In ins ance 5 wi h p= 2, we can no ice ha he e a e wice he numbe o ai c a deployed han he e a e numbe o a ge s. This is due o he ac ha he e a e nume ous gaps be ween he gene a ed UAS, which hinde s i o o m a unique connec ed componen . This shows ha he posi ions o a ge nodes in luence he cos o he inal ne wo k. The inal solu ions o he i e di e en ins ances, all wi h p= 2 can be seen in Figu e 8 . Fo each igu e, he ed c osses ep esen he g ound nodes, he g een squa es ep esen he ai c a gene a ed by he MIP sol e (2nd phase), and he o ange squa es hose used o connec ions. The edges ep esen he connec ions ai c a -ai c a . Fo Figu e 8e, he a ge s canno be seen as hey a e hidden by he ai c a co e ing hem, and only 50 ai c a used o co e age can be seen in g een a he han 100, since ai c a a e o e lapping, due o he edundancy o 2, and he ac ha a ge s a e isola ed. As expec ed, he numbe o ai c a deployed inc ease wi h he numbe o a ge s bu mo e impo an ly wi h hei dispe sion. This can be seen wi h ins ance 5 (Figu e 6e) whe e he e a e e y ew a ge s bu many gaps be ween hem. Fo his special case i would be mo e p o i able o place he ai c a a he middle o wo isola ed g ound nodes, bu i is ha d o iden i y hose s uc u es be o ehand. The o he in e es ing case, mo e plausible as UASs deploymen s a e usually needed in places wi h a ge s ga he ed in o ela i ely compac g oups, is Figu e 8d whe e se e al a ge s a e sp ead on he map. When p= 2, he i s phase gene a es 105 po en ial loca ions, Elec onics 2021,10, 422 19 o 26 hen in he second phase, he GLPK MIP sol e il e s hese posi ions o less han a hal o hem (42 ai c a o deploy). (a) Ins ance 1: 50 g ound nodes (b) Ins ance 2: 75 g ound nodes (c) Ins ance 3: 100 g ound nodes (d) Ins ance 4: 125 g ound nodes (e) Ins ance 5: 50, all isola ed g ound nodes Figu e 8. G aphical esul s o he 5 inpu es s ins ances, wi h p=2. Elec onics 2021,10, 422 20 o 26 In addi ion, al hough i is no appa en in he 2D igu es, ai c a can o e lap due o he duplica ion equi ed o he edundancy on isola ed g ound nodes. Fo ins ance, in Figu e 8 d, wo ai c a a e o e lapping a coo dina es abou (500,800), and co e an isola ed a ge a ha exac posi ion. These isola ed g ound nodes, oge he wi h ai c a used o connec i i y, a e wi h no much su p ise he ones ha cos he mos . So, he edundancy equi emen should be ixed wi h cau ion i one does no wan he numbe o ac i a ed ai c a o s eadily g ow. None heless, in o a eas wi h g ea concen a ion o g ound nodes he e is a s ong po en ial o edundancy, as in he ins ance in Figu e 8d whe e some imes g ound nodes a e co e ed wi h up o i e ac i e ai c a . Table 3. Resul s o he inpu ins ances wi h 2 alues o equi ed minimum edundancy pa ame e p. Ins ances po (6)Numbe o Ac i e Loca ions ∑ ∈T edund( ),o (3)CPU Time (in secs) 1s Phase 2nd (SCP Resul s) Final G aph 1 (Figu e 6a) 1 36 2 5 81 0.005642 1 (Figu e 6a) 2 36 4 7 131 0.007040 2 (Figu e 6b) 1 64 17 35 216 0.012458 2 (Figu e 6b) 2 64 35 48 267 0.015921 3 (Figu e 6c) 1 83 17 33 281 0.016422 3 (Figu e 6c) 2 83 36 49 376 0.019009 4 (Figu e 6d) 1 105 19 39 351 0.018976 4 (Figu e 6d) 2 105 42 56 472 0.022005 5 (Figu e 6e) 1 50 50 97 158 0.015618 5 (Figu e 6e) 2 50 100 147 208 0.044414 6.2.2. Scalabili y (Resul s o Second Se ies o Expe imen s) As p esen ed in Sec ion 6.1, wi h ega d o he second se ies o expe imen s, he objec i e was o analyze he o e all un- ime g ow h o he app oach on la ge and g owing se s o ins ances. I was also o e alua e he execu ion ime o he pa icula h ee main s eps o he app oach so ha we can de ec he ones ha a e mo e challenged depending on he numbe o a ge s o co e and hei dis ibu ion. The esul s o he six da ase s a e gi en in Figu es 9and 10, whe e on he le we ha e he consecu i e un- imes on a speci ic se and on he igh he dis ibu ion o he mos challenging ins ance o ha pa icula se ( he peak). The ime cos s a e ep esen ed in g een ( • ) o he i s phase, cyan ( • ) o he MIP p oblem, yellow (•) o he connec i i y, and uchsia (•) o he o e all cos . F om hese igu es, one can al eady no ice ha un- ime does no always g ow wi h he numbe o a ge s o co e . Also, e en hough a some poin he execu ion imes o he h ee phases a y a lo and e en in e wine, some impo an ea u es a e no iceable om he esul s: • he cos o he clus e ing phase e ol es on he numbe o a ge s bu also on he dis ance be ween hem, since he gene a ed posi ions depend on hese dis ances and hus he numbe o i e a ions un il he s opping c i e ion is eached. This phase is he one wi h a ela i ely mo e consis en un- ime g ow h ha is unlikely o explode. • he execu ion cos o he MIP sol e depends on he numbe o a ge s ( he cons ain s) and he posi ions gene a ed in he i s s ep ( he decision a iables), bu i mos impo an ly depends on he s uc u e o he p oblem. Indeed, he b anch-and-cu me hod used by glpk is mos sensi i e o he s eps needed o each he op imal in ege solu ion han on he size o he p oblem. • he ime cos o he connec i i y s ep depends on he gaps in he sepa a e con- nec ed componen s. Elec onics 2021,10, 422 21 o 26 (a) Se 1 (b) Peak un- ime se 1: 950 g ound nodes (c) Se 2 (d) Peak un- ime se 2: 750 g ound nodes (e) Se 3 ( ) Peak un- ime se 3: 900 g ound nodes Figu e 9. Da ase s o e all un- ime and speci ic o he 3 main s eps; and dis ibu ion o ins ance wi h highes execu ion ime (Pa 1). Elec onics 2021,10, 422 22 o 26 (a) Se 4 (b) Peak un- ime se 4: 850 g ound nodes (c) Se 5 (d) Peak un- ime se 5: 1000 g ound nodes (e) Se 6 ( ) Peak un- ime se 6: 1000 g ound nodes Figu e 10. Da ase s o e all un- ime and speci ic o he 3 main s eps; and dis ibu ion o ins ance wi h highes execu ion ime (Pa 2). Elec onics 2021,10, 422 23 o 26 The execu ion ime expansion o he clus e ing phase is somewha egula and akes less han wo seconds o all he ins ances in he da ase . I g ows wi h he numbe o a ge s and mode a ely luc ua es wi h he ex en o sepa a ion be ween g oups o a ge s. Mo eo e , compa ed o he o he s eps, i is he one ha is less likely o inc ease d as ically. On he o he hand, he second s ep can some imes be conside ably expensi e, e en o small numbe s o a ge s. In Figu e 9 o example, we see a e y subs an ial inc ease o he ins ance o 900 a ge s, whe eas o he p e ious and i s nex (950 and 1000 a ge s), he du a ion is much mo e mode a e. Tha is due o he numbe s o b anching and cu s used o each he op imal in ege solu ion o ha speci ic ins ance. Tha is why he s uc u e o he inpu ins ance is mo e challenging o he sol e han i s size. As o he las phase, i is ob ious o expec seeing a sha p escala ion in execu ion ime o ins ances wi h la ge gaps wi hin he di e en connec ed componen s. Wha is mo e in e es ing o obse e o his phase, is he e ec o using a ype o g eedy s a egy as he one we used: o he connec i i y, we ha e adop ed as a solu ion o connec he wo closes connec ed componen s. The g eedy app oach can some imes make a de ou and ake a longe pa h, causing a gene a ion o la ge numbe o ai c a used only o connec i i y. Such ins ance can be seen in Figu e 11d whe e he e a e conside able numbe s o ai c a dedica ed jus o connec i i y (in g een) han hose used o co e age (in blue): 1114 ai c a o connec i i y, s 616 o co e age. This ins ance (1000 a ge s o co e ) was pa o an addi ional se o inpu es s used o examine he pe o mance o ou app oach o he speci ic connec i i y ea u e. Compa ed o he o he se s o he second se ies o expe imen s, his new se o ins ances (“La ge” in Figu e 11a) had a much g ea e ex en o expansion bu s ill had he same pool o numbe o a ge s (50 o 1000). We can clea ly no ice in Figu e 11b ha on much la ge maps he cos o connec ing he connec ed componen s is he one ha s ands ou he mos . The de ou s caused by he g eedy app oach a e also appa en in Figu e 11d. F om ha g aphical ep esen a ion i is easy o ealize ha a be e solu ion can be ound. (a) S anda d de ia ions (b) Execu ion imes (se “La ge”) Figu e 11. Con . Elec onics 2021,10, 422 24 o 26 (c) G ounds only (1000 a ge s) (d) G ounds + co e s + connec i i y Figu e 11. Resul s on he da ase wi h la ge gaps be ween connec ed componen s. 7. Conclusions In o de o p o ide e icien solu ions o he deploymen o Unmanned Ai c a Sys ems (UASs) o g ound a ge s communica ion p o ision in disas e scena ios, he p esen wo k p oposed a solu ion p o iding a maximum co e age o a ge s on he g ound and a gua an eed minimum numbe o co e s o each a ge o ensu e ha in case o ai c a ailu es in he UAS, a ge s s ay co e ed. Howe e , also, in o de o keep a s eady s eam o communica ion be ween he UAS and he g ound a ge s, he app oach p o ides a way o building ne wo ks ha always o m unique connec ed componen s. This epo p esen ed he me hod ha wo ks in h ee main phases: (1) Apply clus e ing me hods o gene a e loca ions o he ai c a in o good a ea o in e es . This phase uses a p ocedu e o building smalle clus e s on each i e a ion o add mo e po en ial loca ions and di e si y he sea ch space o he nex phase; (2) Run an op imiza ion phase ha il e s he gene a ed loca ions and keep only he ones ha bes sa is y wo equi emen s: co e age and edundancy o he co e s; (3) When necessa y, build a unique connec ed componen o he UAS by i e a i ely connec ing he wo closes sepa a ed connec ed componen s. Wi h he clus e ing me hod, we wan ed o p oduce good and limi ed loca ions o he UASs, wi h he in en ion o using hem as disc e e da a o a se co e ype p oblem. The op imiza ion phase hen minimized he esul s om phase 1 by il e ing hem and keep only he bes . This way o doing hings has enabled us o o e maximum co e age o all he a ge nodes on he g ound and gua an ees a minimum k-co e age o each a ge wi h a low numbe o ai c a o deploy. Finally, i he esul s om phase 2 do no o m a unique connec ed componen , a las phase ensu es ha a single one is buil om he sp ead ones. We es ed ou app oach wi h di e en scena ios, and assessed i s cos on se e al se s o ins ances, di e en by he numbe o a ge s o co e , as well as hei dis ibu ions. The app oach p o ided good esul s bu mos impo an ly in a e y sho pe iod o ime. S ill, a his s age o he wo k, we belie e ha he way connec i i y is en o ced in o he UASs can be imp o ed. Indeed, ou app oach builds a unique connec ed componen wi h a g eedy solu ion: connec he wo closes ai c a in wo di e en connec ed componen s. Fo his, a pai wise compa ison o ai c a loca ions is equi ed and i can ge hea y as he numbe o ai c a inc eases. So, as a u he assignmen , i could be in e es ing o es new me hods and d aw ideas om o he s esea ch wo k in o de o ackle his issue. In many o he wo ks p esen ed in Sec ions 1and 2, he connec i i y equi emen is deal wi h as a ne wo k low p oblem and di ec ly included as a cons ain in an in ege p og amming model. I can indeed be con enien o sol e he whole p ocess in o a single model, bu , i he sea ch space o he connec i i y canno be disc e ized as i is done in he p esen wo k, he Elec onics 2021,10, 422 25 o 26 p oblem migh ce ainly s ay complex o handle and he solu ions could ha dly be scaled o la ge ins ances. Exac and app oxima e me hods like [ 9 , 15 , 16 , 28 ] p opose o sol e mo e objec i es on la ge scale bu on he expense o compu a ion ime and some imes e en on he quali y o he solu ions. So, we belie e ha he p esen wo k could be a new addi ion o he esea ch and could eally bene i om o he esea ch oo. The g ea es bene i o he p oposed app oach is ha i is modeled as a simple mono-objec i e op imiza ion p oblem, which makes i eally con enien o ans o m in o a mul iobjec i e model. Au ho Con ibu ions: Concep ualiza ion, D.M.N., D.G.-R., S.L.T.M., H.T.; Me hodology, D.M.N. and D.G.-R.; Resou ces, H.T. and S.L.T.M.; So wa e, D.M.N.; Supe ision, D.G.-R., H.T. and S.L.T.M.; Valida ion, D.M.N.; W i ing—o iginal d a , D.M.N.; W i ing— e iew and edi ing, D.G.-R., H.T. and S.L.T.M. All au ho s ha e ead and ag eed o he published e sion o he manusc ip . Funding: This wo k has been pa ially unded by he Uni e sidad de Se illa unde he con ac “Con a os de acceso al Sis ema Español de Ciencia, Tecnología e Inno ación pa a el desa ollo del p og ama p opio de I+D+i de la Uni e sidad de Se illa”, by he Spanish “Minis e io de Ciencia, inno ación y Uni e sidades, P og ama Es a al de I+D+i O ien ada a los Re os de la Sociedad” unde he P ojec “Despliegue Adap a i o de Vehículos no T ipulados pa a Ges ión Ambien al en Escena ios Dinámicos RTI 2018-098964-B-I00”, and by he eginal go e men Jun a de Andalucía unde he P ojec s “Despliegue In eligen e de una ed de Vehículos Acuá icos no T ipulados pa a la moni o ización de Recu sos Híd icos US-1257508”, “Despliegue y Con ol de una Red In eligen e de Vehículos Au ónomos Acuá icos pa a la Moni o ización de Recu sos Híd icos Andaluces PY18- RE0009” and “Desa ollo de nue as ecnologías WiFi in eligen es en en o nos mó iles y con al a densidad de usua ios P18-TP-1520”. Con lic s o In e es : The au ho s decla e no con lic o in e es . Re e ences 1. Asimakopoulou, E.; Bessis, N.; Asimakopoulou, E.; Bessis, N. Ad anced ICTs o Disas e Managemen and Th ea De ec ion: Collabo a i e and Dis ibu ed F amewo ks; In o ma ion Science Re e ence—Imp in o : IGI Publishing: He shey, PA, USA, 2010. 2. Reina, D.; Askalani, M.; To al, S.; Ba e o, F.; Asimakopoulou, E.; Bessis, N. A su ey on mul ihop ad hoc ne wo ks o disas e esponse scena ios. In . J. Dis ib. Sens. Ne w. 2015,11, 647037. [C ossRe ] 3. Haya , S.; Yanmaz, E.; Muza a , R. Su ey on Unmanned Ae ial Vehicle Ne wo ks o Ci il Applica ions: A Communica ions Viewpoin . IEEE Commun. Su . Tu o ials 2016,18, 2624–2661. [C ossRe ] 4. Gup a, L.; Jain, R.; Vaszkun, G. Su ey o Impo an Issues in UAV Communica ion Ne wo ks. IEEE Commun. Su . Tu o ials 2016,18, 1123–1152. [C ossRe ] 5. Sánchez-Ga cía, J.; Ga cía-Campos, J.; A zamendia, M.; Reina, D.G.; To al, S.; G ego , D. A su ey on unmanned ae ial and aqua ic ehicle mul i-hop ne wo ks: Wi eless communica ions, e alua ion ools and applica ions. Compu . Commun. 2018 , 119, 43–65. [C ossRe ] 6. Reina, D.G.; To al, S.L.; Taw ik, H. UAVs Deploymen in Disas e Scena ios Based on Global and Local Sea ch Op imiza ion Algo i hms. In P oceedings o he 2016 9 h In e na ional Con e ence on De elopmen s in eSys ems Enginee ing (DeSE), Li e pool, UK, 31 Augus –2 Sep embe 2016; pp. 197–202. [C ossRe ] 7. Galkin, B.; Kibilda, J.; DaSil a, L.A. Deploymen o UAV-moun ed access poin s acco ding o spa ial use loca ions in wo- ie cellula ne wo ks. In P oceedings o he 2016 Wi eless Days (WD), Toulouse, F ance, 23–25 Ma ch 2016; pp. 1–6. [C ossRe ] 8. Sánchez-Ga cía, J.; Ga cía-Campos, J.M.; To al, S.L.; Reina, D.G.; Ba e o, F. An In elligen S a egy o Tac ical Mo emen s o UAVs in Disas e Scena ios. In . J. Dis ib. Sens. Ne w. 2016,12, 8132812. [C ossRe ] 9. Reina, D.G.; Taw ik, H.; Ma ín, S.L.T. Mul i-subpopula ion e olu iona y algo i hms o co e age deploymen o UAV-ne wo ks. Ad Hoc Ne w. 2018,68, 16–32. [C ossRe ] 10. Gup a, S.K.; Kuila, P.; Jana, P.K. Gene ic algo i hm app oach o k-co e age and m-connec ed node placemen in a ge based wi eless senso ne wo ks. Compu . Elec . Eng. 2016,56, 544–556. [C ossRe ] 11. Sabino, S.; Ho a, N.; G ilo, A. Cen alized Unmanned Ae ial Vehicle Mesh Ne wo k Placemen Scheme: A Mul i-Objec i e E olu iona y Algo i hm App oach. Senso s 2018,18, 4387. [C ossRe ] [PubMed] 12. Cailloue , C.; Raza ind alambo, T. E icien Deploymen o Connec ed Unmanned Ae ial Vehicles o Op imal Ta ge Co e age. In P oceedings o he IEEE GIIS 2017—Global In o ma ion In as uc u e and Ne wo king Symposium, S . Pie e, F ance, 25–27 Oc obe 2017. [C ossRe ] 13. Yoon, Y.; Kim, Y. An E icien Gene ic Algo i hm o Maximum Co e age Deploymen in Wi eless Senso Ne wo ks. IEEE T ans. Cybe n. 2013,43, 1473–1483. [C ossRe ] [PubMed] 14. Kons an inidis, A.; Yang, K. Mul i-objec i e K-connec ed Deploymen and Powe Assignmen in WSNs using a p oblem-speci ic cons ained e olu iona y algo i hm based on decomposi ion. Compu . Commun. 2011,34, 83–98. [C ossRe ]