A Drones Optimal Path Planning Based on Swarm Intelligence Algorithms

Mahmoud Ragab, Ali Altalbe, Abdullah Saad Al-Malaise ALGhamdi, S.Abdel-khalekand Rashid A.Saeed

1Information Technology Department, Faculty of Computing and Information Technology, King Abdulaziz University,Jeddah 21589, Saudi Arabia

2Center of Artificial Intelligence for Precision Medicines, King Abdulaziz University, Jeddah 21589, Saudi Arabia

3Information Systems Department, Faculty of Computing and Information Technology, King Abdulaziz University,Jeddah 21589, Saudi Arabia

4Department of Mathematics, Faculty of Science, Al-Azhar University, Naser City 11884, Cairo, Egypt

5Department of Mathematics, Faculty of Science, Taif University, Taif, Saudi Arabia

6Department of Mathematics, Faculty of Science, Sohag University, Sohag, Egypt

7Department of Computer Engineering, College of Computers and Information Technology, Taif University, Taif,Saudi Arabia

Abstract: The smart city comprises various interlinked elements which communicate data and offers urban life to citizen.Unmanned Aerial Vehicles(UAV) or drones were commonly employed in different application areas like agriculture, logistics, and surveillance.For improving the drone flying safety and quality of services, a significant solution is for designing the Internet of Drones (IoD) where the drones are utilized to gather data and people communicate to the drones of a specific flying region using the mobile devices is for constructing the Internet-of-Drones, where the drones were utilized for collecting the data, and communicate with others.In addition,the SIRSS-CIoD technique derives a tuna swarm algorithm-based clustering(TSA-C) technique to choose cluster heads (CHs) and organize clusters in IoV networks.Besides, the SIRSS-CIoD technique involves the design of a biogeography-based optimization (BBO) technique to an optimum route selection (RS) process.The design of clustering and routing techniques for IoD networks in smart cities shows the novelty of the study.A wide range of experimental analyses is carried out and the comparative study highlighted the improved performance of the SIRSS-CIoD technique over the other approaches.

Keywords: Drones; smart city; swarm intelligence; route selection; internet of drones; networking

1 Introduction

Recently, Smart cities have attracted growing interest in the field of institutions, transportation,home energy management, also providing facilities for the citizens, safety and security, and businesses in healthcare management.The smart city technology presented by National Institute of Standards and Technology (NIST) consists of 6 major elements that is smart people, smart mobility, smart environment, smart economy, smart governance, and smart living, with cloud computing as the environment for storing information, and the Internet-of-Things (IoT) as an enabling technique [1].Furthermore, it is predicted that in 2020, the amount of smaller-scale drones attained 2.7 million,smartphone undertakes an important role in extending the use of smart city applications, since it allows the citizen to send and receive information as well as logging on to the application [2,3].Unmanned Aerial vehicles (UAV), is also called drones, are considered smart city components which provide surveillance and smart mobility for the citizen.UAV includes various kinds of sensor nodes that assist many applications using cooperative form among themselves [4].

Especially, a drone has smart devices, like time-of-flight (ToF) sensor, magnetic-field change sensor, light-pulse distance sensor, thermal and chemical sensor orientation sensor, radio range, and detection sensor.It is remotely controlled and often moves autonomously with no human interference.Now, drones were utilized in a large number of civilian applications, namely package delivery, air traffic control, remote sensing, monitoring, firefighting, and an inspection of infrastructure.This drone would provide various services and occupy lower airspace.The concept of“Internet-of-Drones(IoD)”relates to technique where multiple drones, each containing flying zones, procedure an aerial mesh network for gathering data and communicate via sensors, i.e., subsequently transmitted to a control server.The sample structure of IoD in the smart city is shown in Fig.1.External mobile users could access and monitor any drones via their mobile phones in a certain flying zone over a control server providing that she/he is allowed to access the drone.The communication could take place inbetween the trusted control server, the user and the drone, and amongst the user or drones [5].

Figure 1: Structure of IoD in a smart city environment

Drones have limited computational power scarce and battery resources that could affect the entire transmission efficacy in IoD.To effectively employ this scarce resource, a transmission technique has been developed that yields higher throughput, guarantees lower computational complexity, and lower routing overhead could be a tedious process.The routing mechanism for an effective transmission is needed for the data transmission amongst drones.The ever-growing mobility and topology of the drones in IoD create the transmission amongst drones a challenging process [6].The solution to this problem is hierarchal routing which is also called clustering.In clustering, the network forms into subgroups, a cluster includes cluster member (CM) and cluster head (CH).A CH is selected between each member in the cluster and it controls the performances of the cluster by handling it effectively and efficiently [7,8].Therefore, the selection of CH is the most significant task of clustering and all the CMs could be a candidate for the selection of CH.Rather than a single-hop transmission network, a multihop cluster-based network leads to scalability and better performance.

In clustering algorithms, CH election and cluster formation are essential tasks to effectively preserve cluster topology.Successive modifications in the relative location of CM change the entire cluster topology.Hence, it is necessary to design an effective clustering method for the effective use of energy resources and better scalability of rapidly developing topology [9].The swarm intelligence (SI)based models are utilized to a near-optimum solution.In an Adhoc technique, there is no centralized control that leads to growing complexities in management and configuration [10].Therefore, it is necessary to develop this network architecture which contains self-organizing abilities like selfoptimization, self-configuring, self-healing, and adaptive to environments.

This study designs a novel Swarm Intelligence-based Route Selection Strategy for Clustered Internet of Drones Enabled Smart City Applications, called SIRSS-CIoD.In addition, the SIRSSCIoD technique derives a tuna swarm algorithm-based clustering(TSA-C)technique to choose cluster heads (CHs) and organize clusters in IoV networks.Besides, the SIRSS-CIoD technique involves the design of a biogeography-based optimization (BBO) technique to a better route selection (RS)process.The design of clustering and routing techniques for IoD networks in smart cities shows the novelty of the study.A wide range of experimental analyses is carried out and the comparative study highlighted the improved performance of the SIRSS-CIoD technique over the other approaches.

The rest of the paper is organized as follows.Section 2 offers the related works, Section 3 provides the proposed method, Section 4 discusses the results, and Section 5 concludes the work.

2 Related Works

In[11],the function of UAVs in the Adhoc network and their cooperation with vehicles in VANET is examined for assisting the method of detection and routing of malicious vehicles.The routing protocol called VRU is presented which consists of 2 distinctive methods of routing of data: (1)routing packets of information among UAVs with a protocol called VRU_u, and (2) delivering a packet of information among vehicles through UAVs with a protocol termed VRU_vu.In [12], a tight plane-based architecture is presented that uses the current public transportation like city trains, public buses, and their paths to offer time-sensitive monitoring.Then, proposed a loose hierarchical-based architecture.To assist seamless monitoring over wide-ranging, they utilize 2 kinds of UAVs, that enable replenishment amongst heterogeneous UAVs at distinct layers via airborne docking.

In [13], a UAV heterogeneous fleet routing problem is addressed, handling vehicles constrained autonomy with the consideration of respecting operational requirements and multiple charging stations.A green routing problem is developed to overcome problems that are present because of constrained vehicle driving range.As a result of the massive number of emerging drones in society,UAV efficacy and use need to be enhanced.In [14], a lower complex architecture is designed for determining the time plans shortest and trajectories for all the members of the fleet when considering the various limitations.A collision can be prevented by forcing several drones to statically hover to permit its peers to securely permit the path segments.Some scenarios were examined to display the efficacy of the scheduling and routing architecture.

The performances of UAVs flight (single/group flight) for the decision of distinct target tasks in the city using data air navigation methods [15] and technique of arithmetical modeling in artificial intelligence (AI) (methods of deciding risk graph theory, fuzzy logic (FL) model, dynamic programming, Expert Judgment Method and so on.).The optimization and configuration group flight paths for UAVs are based on the kinds of“target tasks”.The limitations of emergency response and traffic policing handling schemes are addressed in [16].Besides, the authors presented a smart, independent UAV-assisted solution; and describes the structure in simulated setting.Some scenarios of policing system and traffic monitoring are taken into account in the simulation: mobile speeding trap and automatic notifications, accident detection and traffic light violation, vehicle tracing using UAV, traffic rerouting and congestion detection, autonomous emergency response handling system, and pending arrest warrants or flagged stolen vehicles [17].

A spatiotemporal scheduling architecture is developed for autonomous UAVs with the RL method.This architecture allows UAV to separately define their schedule to cover the maximal prescheduled event temporally and spatially dispersed over a pre-defined time horizon and provided geographical region.The proposed method can upgrade the planned schedule in the event of an unpredicted emergency.Huang et al.[18] proposed the Active Trust Verification Data Collection(ATVDC) system to the secure, efficient, and cheap gathering of information.In this system, a UAV is adapted for collecting basic information from the sensor to estimate the trust of mobile vehicle (MV),and a high-trust MV priority recruitment (HTMPR) approach is presented for recruiting credible MV at a lower cost.Additionally, a genetic-algorithm-based trajectory planning (GATP) strategy was developed for permitting the UAV for collecting further basic information at minimal flight costs.

3 The Proposed Model

In this study, an efficient SIRSS-CIoD technique is derived for grouping the drones in the cluster and enabling optimal data transmission in smart cities via shortest routes.The proposed SIRSS-CIoD technique involves the TSA-C technique to choose CHs and BBO algorithm for optimal RS.The detailed working of these modules is discussed in the following sections.

3.1 Phase I: Algorithmic Steps Involved in TSA-C Technique

Primarily, the TSA-C technique gets executed to pick an optimal set of CHs from the available drones in the network [19].Tuna, scientifically called Thunnini, is a marine carnivorous fish.They utilize their intelligence to attack and find their prey.This creature has changed a huge amount of intelligent and effective foraging behaviors.The initial behavior was spiral foraging.Once tuna are feeding, it swim by making a spiral procedure for acquiring the prey as to shallow water where they are attacked more easily.The next behavior is parabolic foraging.Every tuna swim afterward the prior individuals, which form a parabolic formation for enclosing their prey.Tuna effectively forages by the above mentioned 2 strategies.In this work, a novel swarm based meta-heuristic optimized method, such as tuna swarm optimization, is presented dependent upon modeling this natural foraging behavior.

Initiation

Like other swarm-based metaheuristics method, TSA begin the procedure of optimization by making the first population at random uniformly in the searching space,

whereasrepresent theithfirst individual, ub & lb indicate the upper as well as lower bounds of the searching space,NPindicates the amount of tuna’s population, and rand represents a uniform distribution arbitrary vector range in zero to one

Spiral Foraging

Once sardines, herring, also other smaller school fish encounters predator, the whole schooling of fish forming a dense structure continuously changes the swimming direction, which makes it complex for the predator for locking the target.Now, the tuna group chases the prey by creating a tight spiral form.Even though many school fishes have a small sense of direction, as soon as a smaller group of fish swims firmly in specific direction, the neighboring fish would alter its direction consecutively and lastly create a larger group with similar goals and starts to hunt.Besides spiraling afterward their prey, the school of tuna exchanges data with one another.All the tuna following the prior fish, hence enabling data sharing between adjacent tuna.As mentioned above, the arithmetical equation for the spiral foraging behavior can be expressed in the following:

Parabolic Foraging

Besides feeding by making a spiral form tuna forms a parabolic cooperative feeding.Tunas form a parabolic shape using food as a reference point.Additionally, tuna hunts to food by seeking everywhere.Both strategies are carried out concurrently, with the assumption that chosen probability is 50% for both.The arithmetical expression can be determined in the following:

In whichTFrepresents an arbitrary value within [-1,1].Fig.2 shows the flowchart of the TSA algorithm.

Figure 2: Flowchart of TSA

Usually, there are 4 objective functions in which it encompasses all the considerable factors essential for energy effective clusterings such as identifying present energy ratio, preserving the energy using the constrained number of CH,mitigation of intracluster distance, improved intercluster distance from CH, balancing the load between CHs, and reducing the distance among base station (BS) and CH.The newly developed TSA-C technique makes an optimal solution by acquiring a fitness function(FF) with distance to BS, distance to neighbors, network load, and energy.Consequently, FF is determined in the currently utilized technique by:

In whichm1,m2,m3, and m4signifies the weight constant determined by the user, andFFspecifies the FF.Furthermore,y1,y2,y3, andy4, represents the objective function.The presented TSA-C technique was applied to recognize the finest solution according to FF.Currently, the solution has obtained using an agent.So, the enhanced solution to above mentioned FF includes the minimal amount of clusters with the highest link＜quality and vigorously defined CH with maximum residual energy (RE).The main purpose is for preserving the energy, and energy ratio as described in the following.Once there areRclusters, existing CH energy,Mnodes, and the ratio of node energy.

The subsequent function determines the distance to neighbors that are determined as a Euclidean distance between the sensor nodes (SNs).

The 3rd function decreases the distance among CH & BS.In this technique was deliberated asA×A; the entire cluster representsRthat is demonstrated in Eq.(14).

The ultimate operation is employed to accomplish the load in CH.Eq.(15)restraint the maximum load amongst CHs.|CNq| means the quantity of nodes inqcluster.Subsequently, a range is regarded asA×A; whole cluster representsR.

3.2 Phase II: Algorithmic Steps Involved in BBO-RS Technique

At this stage, the BBO-RS technique is employed to derive an optimal set of routes to the destination in the IoD network [20].

In BBO, every problem solution is regarded as a“habitat”with habitat survival index (HSI), i.e.,the same as a fitness of EAto estimate an individual.Higher HSI habitat shares their feature with lower HSI habitat.The procedure of sharing better features amongst solutions are represented as migration.BBO adapts the migration behavior for sharing data between solutions.Better individuals’data could be preserved at the time of the evolutionary procedure to guarantee population convergence.Mutation.Mutation operators are utilized for generating various solutions to help the variety of the population.The complete processes are given in the following.Assume that the specific amount of all the individualsirepresentSi, and its immigration rate λiiand emigration rate μiis estimated by

where asSmaxrepresent the specific amount of each habitat.I&Erepresents the maximized of immigration rate as well as emigration rate, correspondingly.During the migration operator, the individual emigration rate and immigration rate are utilized for deciding either a solution must share its feature values using another solution.The best solution consists of a high immigration rate and a low emigration rate.Using migration, the solution with higher emigration rate tend for sharing its data with those with a higher immigration rate.Solution with higher immigration rate accepts several features from solution with higher emigration rate.Using migration, BBO demonstrates better exploitation capacity in the searching space.

Assume that species amount changes with species migrating;Psthe probability that habitat comprises accuratelySspecies as follows:

Next, the mutation ratemiis determined by

where asPmutedenotes a predetermined variable,Piis estimated, andPmax= max1≤i≤N{Pi}.The mutation operator is performed according tomi.A solution with a lower probabilityPiis possible to mutate another solution.On the other hand, few solutions with higherPihave a smaller possibility of mutating.With the mutation operators, different solutions are generated.

For detecting an optimum set of paths, the dimension of all the BBO-RS techniques can be determined to be equal to CH and the additional locations are situated in the BS.Consider,θi=signifies aithfish,denotes a real value within [0,1].Consequently, the provided function is utilized to define the following hops to BS as

The objective is for defining an optimum set of paths from CH to BS with an FF with 2 variables like distance and energy.At first, the RE of the following hop nodes can be determined and the nodes using the highest energy are processed as a relay node.For transmitting the information, the source node is transferred to the relay node which further moves to BS utilizing inter CH.So, the nodes using high RE are processed as the following hop nodes.The primary sub-objectivesf1 have been shown below:

As well, Euclidean distance is utilized to define the distance from CH to BSs.The minimalization of energy dissipation is dependent largely on the broadcast distance.If a lower distance occurs, the energy could be stored considerably.As soon as the distance gets increased, a massive quantity of energy could be expended.Henceforth, a node with less distance is chosen for relay nodes.Hence, the subsequent sub-objectives using distance isf2 can be represented as:

As mentioned, sub-objective can be briefly described to FF as follows, while α1and α2signifies the weights assigned to all the sub-objectives.

4 Performance Validation

This section investigates the performance validation of the proposed model under the distinct number of drones.Primarily, an extensive Network Lifetime (NLT) analysis of the SIRSS-CIoD technique is provided in Tab.1 and Fig.3.A comparative results analysis is made with glowworm swarm optimization based clustering with routing (GSOCR), grey wolf optimization based clustering with routing (GWOCR), improved particle swarm optimization based clustering with routing (IPSOCR),and particle swarm optimization based clustering with routing (PSOCR).

Figure 3: Comparative NLT analysis of SIRSS-CIoD with recent approaches

The results revealed that the SIRSS-CIoD technique has accomplished improved NLT over the other techniques.For instance, with 10 drones, the SIRSS-CIoD methodology has accomplished an increased NLT of 6010 rounds while the GSOCR method, GWOCR model, IPSOCR approach,and PSOCR algorithms have attained lower NLT of 5880, 5850, 5650, and 5100 rounds respectively.Concurrently, with 20 drones, the SIRSS-CIoD technique has offered enhanced NLT of 6220 rounds but the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have attained decreased NLT of 5830, 5620, 5500, and 5070 rounds respectively.In addition, with 30 drones, the SIRSS-CIoD methodology has accomplished a superior NLT of 6070 rounds although the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have attained decreased NLT of 5610, 5320, 5170, and 4900 rounds respectively.

Table 1: NLT analysis of SIRSS-CIoD with recent approaches

A comparative average delay (AD) analysis of the SIRSS-CIoD technique takes place in Tab.2 and Fig.4.The results showcased that the SIRSS-CIoD system has gained minimal AD over the other techniques.For instance, with 10 drones, the SIRSS-CIoD technique has obtained a lower AD of 1.59s whereas the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have gotten maximum AD of 2.02, 2.09, 2.21, and 2.75s respectively.Eventually, with 20 drones, the SIRSS-CIoD technique has reached the reduced AD of 2.36s whereas the GSOCR method, GWOCR model,IPSOCR approach,and PSOCR algorithms have resulted in higher AD of2.52, 2.82, 3.71, and 4.87 s respectively.Meanwhile,with30drones,the SIRSS-CIoD technique has provided decreased AD of 2.79s whereas the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have reached increased AD of 3.25, 3.51, 4.77, and 6.01s respectively.

Figure 4: Comparative AD analysis of SIRSS-CIoD with recent approaches

Table 2: AD analysis of SIRSS-CIoD with recent approaches

A detailed energy consumption (ECM) analysis of the SIRSS-CIoD technique takes place in Tab.3 and Fig.5.The results showcased that the SIRSS-CIoD technique has offered reduced ECM over the other techniques.For instance, with 10 drones, the SIRSS-CIoD technique has attained a lower ECM of 42mJ whereas the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have obtained higher ECM of 0.19, 46, 51, 47, and 56mJ respectively.Likewise, with 20 drones, the SIRSS-CIoD technique has reached to reduced ECM of 60 mJ whereas the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have obtianed increased ECM of 66, 72, 79, and 82mJ respectively.Concurrently, with 30 drones, the SIRSS-CIoD technique has provided decreased ECM of 95mJ whereas the GSOCR method,GWOCR model,IPSOCR approach,and PSOCR algorithms have obtained raised ECM of 100, 102, 112, and 118mJ respectively.

Table 3: ECM analysis of SIRSS-CIoD with recent approaches

Figure 5: Comparative ECM analysis of SIRSS-CIoD with recent approaches

AA comparative throughput (THR) analysis of the SIRSS-CIoD technique is provided in Tab.4 and Fig.6.The results exposed that the SIRSS-CIoD technique has accomplished improved THR over the other techniques.For instance, with 10 drones, the SIRSS-CIoD approach has accomplished a higher THR of 0.92Mbps but the GSOCR method,GWOCR model, IPSOCR approach, and PSOCR algorithms have attained lowerTHRof 0.81, 0.79, 0.74, and 0.72Mbps respectively.Concurrently,with 20 drones, the SIRSS-CIoD technique has offered enhanced THR of 0.86 Mbps although the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have attained decreased THR of 0.73, 0.75, 0.62, and 0.57 Mbps respectively.Simultaneously, with 30 drones, the SIRSS-CIoD technique has accomplished an increased THR of 0.83 Mbps while the GSOCR method, GWOCR model, IPSOCR approach, and PSOCR algorithms have attained decreased THR of 0.73, 0.59, 0.54,and 0.55 Mbps respectively.

Table 4: THR analysis of SIRSS-CIoD with recent approaches

Figure 6: Comparative THR analysis of SIRSS-CIoD with recent approaches

Finally, a brief packet loss rate (PLR) analysis of the SIRSS-CIoD technique takes place in Tab.5 and Fig.7.The results reported that the SIRSS-CIoD technique has resulted in reduced PLR over the other techniques.

For instance, with 10 drones, the SIRSS-CIoD technique has attained a lower PLR of 0.08 Mbps whereas the GSOCR method, GWOCR approach, IPSOCR algorithm, and PSOCR system have obtained higher PLR of 0.19, 0.21, 0.26, and 0.28 Mbps respectively.Likewise, with 20 drones, the SIRSS-CIoD technique has reached to reduced PLR of 0.14 Mbps whereas the GSOCR method,GWOCR approach, IPSOCR algorithm, and PSOCR technique have gained increased PLR of 0.27,0.25, 0.38, and 0.43 Mbps respectively.Concurrently, with 30 drones, the SIRSS-CIoD technique has provided decreased PLR of 0.17 Mbps whereas the GSOCR method, GWOCR approach, IPSOCR algorithm, and PSOCR technique have obtained raised PLR of 0.27, 0.41, 0.46, and 0.45 Mbps respectively.

Figure 7: Comparative PLR analysis of SIRSS-CIoD with recent approaches

Table 5: PLR analysis of SIRSS-CIoD with recent approaches

From the aforementioned tables and figures, it can be evident that the SIRSS-CIoD system is an effective tool for data collection and routing in the smart cities’environment.

5 Conclusion

In this study, an efficient SIRSS-CIoD technique is derived for grouping the drones in the cluster and enabling optimal data transmission in smart cities via shortest routes.The proposed SIRSS-CIoD technique involves the TSA-C technique to choose CHs and BBO algorithm for optimal RS.Primarily,the TSA-C technique gets executed to pick an optimum group of CHs from the available drones in the network.Followed by, the BBO-RS approach was employed for deriving an optimal group of routes to the destination in the IoD network.A wide range of experimental analyses is carried out and the comparative study highlighted the improved performance of the SIRSS-CIoD technique over the other approaches.Therefore, the proposed SIRSS-CIoD technique can be applied as a proficient approach for data collection and routing in IoD-enabled smart city applications.In future, data aggregation and scheduling methods are developed to improve the network performance.

Acknowledgement:The authors extend their appreciation to the Deputyship for Research & Innovation,Ministry of Education in Saudi Arabia for funding this research work through the project number(IFPIP-1266-611-1442) and King Abdulaziz University, DSR, Jeddah, Saudi Arabia.

Funding Statement:This project was supported financially by Institution Fund projects under Grant No.(IFPIP-1266-611-1442).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.