Development of a UAV placement algorithm to establish redundant communication between nodes

Abstract

The poaching of rhinoceroses in South Africa has increased to such an extent that it may become extinct in the wild. The horn of the rhinoceros is used in traditional medicine to cure various ailments. The price for rhinoceros horns has increased and, as a result, poachers use more advanced technology to obtain the horns. Consequently, the conservation of the rhinoceros becomes more challenging and expensive. In attempts to reduce rhinoceros poaching, conservationists implemented various tracking systems. The problem with some of these systems is that the communication range is limited and consequently, once out of range, the rhinoceros behaviour is no longer monitored. In which case, a live alarm cannot be sent in the case of an emergency. The current rhinoceros tracker comprises a collar around the foot of the animal. Signal repeaters are mounted to poles to extend the communication range. These repeaters disrupt the natural environment and are expensive. The proposed solution is to replace the signal repeaters on poles with solar charged Unmanned Aerial Vehicles (UAVs). Dedicated landing positions are predefined, and the UAV can move between these positions while tracking a pair of rhinoceroses. For landing sites outside the communication range of the base station, UAV repeaters are placed at landing sites to propagate the signal to the base station. The developed algorithm has two objectives: Firstly, it should ensure a redundant path between the rhinoceros and the base station exists. This will ensure reliable communication of the status of the rhinoceroses, even if a node in a path should fail. Secondly, the number of UAVs needed to create a path between a rhinoceros and the base station should be minimised. Two shortest path algorithms were identified, implemented and the results compared to determine which landing sites to use between two communication nodes. The Dijkstra and Bellman-Ford algorithms were modified to use less landing sites when multiple source nodes are used. This is achieved when the source nodes share paths to the base station. The modified algorithms were simulated to compare them in terms of the Individual Path Node Count (IPNC), the Cumulative Paths Node Count (CPNC), spread dependency and the running time. Twenty different scenarios were simulated for each number of source nodes (2-10). The IPNC for a single scenario was determined by simulating the shortest path from each individual source node to the base station and then adding up the number of landing sites used with each individual simulation. The IPNC value for a network of a given size, is calculated using the average IPNC value of twenty different scenarios. From the results, was found that the modified Bellman-Ford's algorithm uses fewer landing sites for individual source nodes than the modified Dijkstra's algorithm. The CPNC was determined by simulating all the source nodes simultaneously for each of the scenarios. The CPNC value for each number of source nodes is the average value of the different scenarios. The average number of landing sites used for each number of source nodes was compared, and the results indicated that the CPNC was less for the modified Bellman-Ford algorithm. The spread dependency of the algorithms was determined by evenly spreading six source nodes confined to different sector sizes. The IPNC values were kept constant to remove the effects that distance has on the number of landing sites used. The number of landing sites used for each sector size was compared, and the results indicated that both algorithms are dependent on the spread of the source nodes. The run time for each algorithm was compared for each number of source nodes. The modified Bellman-Ford algorithm took significantly longer to complete than the modified Dijkstra's algorithm. The run time increased as the number of source nodes increased. In conclusion, two shortest path algorithms were selected and modified to create a redundant communication path between the UAV following a rhinoceros and the base station. Fewer landing sites were used with the modified algorithms to connect all the source nodes to the base station. Renosterstropery in Suid Afrika het tot so 'n mate toegeneem, dat hul die gevaar in die gesig staar om uitgewis te word in die wild. Die horing van die renoster word in tradisionele medisyne gebruik vir die behandeling van verskeie siektes. Die prys van renoster horings het toegeneem en gevolglik gebruik die stropers meer gevorderde tegnologie om die horings in die hande te kry. Daarom het die bewaring van renosters moeiliker en duurder geword. Verskillende opspoorstelsels is al ge¨ımplimenteer in 'n poging om renosterstroping te verminder. 'n Probleem met van hierdie opspoorstelsels is dat dit 'n beperke kommunikasie reikwydte het en daarom word die gedrag van die renoster slegs gemonitor terwyl dit binne die reikwydte is. Dit verhoed lewendige alarm deteksie in die geval van nood. Die huidige manier om renosters te volg is 'n band om die voet van die renoster. Pale met sein herhalers word geplant om die kommunikasie reikwydte te vergroot. Die pale steur die natuurlike omgewing en is boonop duur. Die voorgestelde oplossing is om die sein herhalers op pale te vervang met songelaaide Onbemande Lugtuie (OLT). Spesifieke landingsposisies word vooraf ge¨ıdentifiseer en die OLT'e kan tussen die posisies beweeg terwyl dit die renoster volg. Vir landingsposisies buite die kommunikasie reikwydte na die basisstasie word OLT herhalers geplaas op beskikbare landingsposisies om die sein oor te dra na die basisstasie. Om volgehoue kommunikasie te verseker tydens die faling van 'n node, word oortollige paaie geskep. Die plasing van die OLT'e moet bepaal word ten einde oortollige paaie te verseker, vanaf elke OLT wat 'n renoster volg tot by die basisstasie, deur die minste hoeveelheid landingsposisies te gebruik. Twee algoritmes vir kortste paaie is ge¨ıdentifiseer om die landinsposisies tussen twee punte te bepaal. Die gewigte van Dijkstra en Bellman-Ford se algoritmes is aangepas om minder landingsposisies te gebruik wanneer veelvoudige oorsprong nodes gebruik word. Hierdie doel word bereik wanneer oorsprong nodes paaie na die basisstasie deel. Die aangepaste algoritmes is gesimuleer om dit te vergelyk in terme van die Individuele Pad Node Telling (IPNT), die Kummulatiewe Pad Node Telling (KPNT), verspreiding afhanklikheid en die simulasietyd. Twintig verskillende scenarios is gesimuleer vir elke hoeveelheid oorsprong nodes (2-10). Die IPNT vir 'n enkele scenario is bepaal deur die kortste pad vanaf elke oorsprong node na die basisstasie te bepaal en die hoeveelheid landingsposisies wat gebruik is met elke individuele simulasie bymekaar te tel. Die IPNT waarde vir elke hoeveelheid oorsprong nodes is die gemiddeld van die IPNT waarde van die twintig verskillende scenarios. Uit die resultate kan gesien word dat die aangepaste Bellman-Ford algoritme minder landingsposisies gebruik vir individuele oorsprong nodes in vergelyking met die aangepaste Dijkstra algoritme. Die KPNT is bepaal deur al die oorsprong nodes gelyktydig te simuleer vir elke scenario. Die KPNT waarde vir elke hoeveelheid oorsprong nodes is die gemiddeld van die verskillende scenarios. Die gemiddelde hoeveelheid landingsposisies gebruik vir elke hoeveelheid oorsprong nodes is vergelyk en die resultate het aangedui dat die KPNT minder was vir Bellman-Ford se algoritme. Die verspreiding afhanklikheid van die algoritmes is bepaal deur ses oorsprong nodes eweredig te versprei in verskillende sektor groottes. Die IPNT waardes is konstant gehou om die invloed van afstand op die hoeveelheid landingsposisies gebruik te elimineer. Die hoeveelheid landingsposisies wat vir elke sektor gebruik is, is vergelyk en die resultate toon dat beide algoritmes afhanklik is van die verspreiding van die oorsprong nodes. Die simulasietyd van elke algoritme is vergelyk vir elke hoeveelheid van oorsprong nodes. Die aangepaste Bellman-Ford algoritme se simulasietyd was drasties langer as die van die aangepaste Dijkstra algoritme. Die simulasietyd het toegeneem soos wat die hoeveelheid oorsprong nodes verhoog het. Ten slotte, twee kortste pad algoritmes is gekies en aangepas om 'n oortollige kommunikasie pad tussen die OLT wat 'n renoster volg en die basisstasie te skep. Minder landingsposisies is gebruik met die aangepaste algoritmes om al die oorsprong nodes met die basisstasie te konnekteer.