Genetic Algorithm-Based Cooperative Coding and Caching Data Dissemination Scheme in Multi-UAV-Enabled Internet of Vehicles

4.1. Problem Formulation

4.2. NP-Hardness Proof

5.1. Algorithm Design

• Generation of Initial Population
  A population of individuals is initialized and denoted by ${\Lambda }_1=\{{\lambda }_1^1,{\lambda }_2^1,\dots ,{\lambda }_M^1\}$, where M is the size of population. In particular, as shown in Figure 3, an individual ${\lambda }_i^1({\lambda }_i^1\in {\Lambda }_1)$, which represents a candidate solution and is denoted by a binary matrix of size $\left|U\right|\times N$, where $\left|U\right|$ and N denote the overall count of UAVs and the overall count of the randomly generated $\left|D\right|$-dimensional coefficient vectors, respectively. Note that given a coefficient vector $a_k=[a{\left(k\right)}_1,a{\left(k\right)}_2,\dots ,a{\left(k\right)}_{\left|D\right|}]$ ($1\le k\le N$), $a{\left(k\right)}_q$$(1\le q\le |D\left|\right)$ is 1 or 0. Then, if ${\lambda }_i^1\left[j\right]\left[k\right]$ is set to 1, it means that $a_k$ is selected and scheduled by UAV $u_j$. Otherwise, ${\lambda }_i^1\left[j\right]\left[k\right]=0$. Additionally, the scheduling period allows for a maximum capacity of T packets to be scheduled. Given a feasible solution ${\lambda }_i^1({\lambda }_i^1\in {\Lambda }^1)$, each row of ${\lambda }_i^1$ should satisfy 0 $\le {\sum }_{k=1}^N{\lambda }_i^1\left[j\right]\left[k\right]\le T$. The process of population initialization is illustrated within Algorithm 1.
• Fitness Function
  The coefficient vector $a\left(p\right)$ is appended to the coefficient matrix for each vehicle located within the radio coverage range of UAV $u_j$ when packet p is scheduled by UAV $u_j$. Note that the C2BS problem aims to identify and arrange a minimal collection of packets P to cater to all vehicles. Then, the following fitness function is designed to evaluate solutions. Specifically, given a solution ${\lambda }_i^g({\lambda }_i^g\in {\Lambda }_g)$, if ${\lambda }_i^g\left[j\right]\left[k\right]$ ($1\le k\le \left|U\right|$, $1\le k\le N$) is eauql to 1, $a_k$ is attached to each vehicle’s coefficient matrix. In a scheduling period, the overall count of packets scheduled by UAV $u_j$ is denoted by $b_j={\sum }_{k=1}^N{\lambda }_i^g\left[j\right]\left[k\right]$. As shown in Figure 3, for the solution ${\lambda }_i$, the total number of scheduling is represented by $b_{num}=max\{b_1,b_2,\dots ,b_{\left|U\right|}\}$. Then, according to the solution ${\lambda }_i^g$, for each vehicle $v_k^j(v_k^j\in V_j)$ in the coverage of the UAV $u_j$, let $r\left(v_k^j\right)$ and $r^{\prime }\left(v_k^j\right)$ represent the ranks of original and updated matrices, respectively. After a scheduling period, the average improvement in matrix rank for these vehicles can be calculated by ${\sum }_{n=1}^{b_j}{\sum }_{k=1}^{|V_j|}(r^{\prime }\left(v_k^j\right)-r\left(v_k^j\right))/\left|V_j\right|$. Based on this, we define the following fitness function to evaluate solutions.

  $$f\left({\lambda }_i^g\right)=\sum _{j=1}^{\left|U\right|}(\sum _{n=1}^{b_j}\sum _{k=1}^{|V_j|}(r^{\prime }\left(v_k^j\right)-r\left(v_k^j\right))/|V_j\left|\right)/b_{num}$$

  (1)
• Offspring Generation
  The operators with parent selection, crossover, and mutation are performed to evolve the generation. Specifically, first, the tournament selection scheme [36] is implemented for determining the two parents to allow them to pass their good genes to successive generations. Hence, given the g-th generation population ${\Lambda }_g$, the underlying principle of the tournament selection scheme is to prioritize two individuals, denoted as ${\lambda }_x^g$ and ${\lambda }_y^g$ (${\lambda }_x^g,{\lambda }_y^g\in {\Lambda }_g$), who exhibit the highest levels of fitness. The parent selection is shown in lines 2∼4 in Algorithm 2. Furthermore, crossover sites are randomly chosen from ${\lambda }_x^g$ and ${\lambda }_y^g$. Then, a completely new offspring is created by exchanging the genes at these crossover sites. The process of the crossover operator is depicted in lines 5∼10 within Algorithm 2. Additionally, to preserve the variety of the population, the new population undergoes bit mutation with a predetermined probability $\rho$. The process of mutation operator is illustrated in lines 11∼18 within Algorithm 2.
• Local Search
  Local search is carried out on each solution in the population to search its neighborhood by steps for a better one. Specifically, given a solution ${\lambda }_i^g$ (${\lambda }_i^g\in {\Lambda }_g$), a local search is performed on ${\lambda }_i^g$ from the first to the last dimension by conducting a sequential value flipping. Then, through sequential evaluation and comparison of new individuals, only the individual exhibiting the highest fitness value is accepted and saved in the population. The local search is shown in lines 24∼38 within Algorithm 2.
• Repair Operator
  It is worth noting that an individual may become an infeasible solution in evolution (i.e., crossover operator, mutation operator, and local search). In each scheduling period, the maximum number of packets broadcast by a UAV is T. Then, for a solution ${\lambda }_i^g$ (${\lambda }_i^g\in {\Lambda }_g)$, if ${\sum }_{k=1}^N{\lambda }_i^g\left[j\right]\left[k\right]>T$, ${\lambda }_i^g$ is an infeasible solution. Hence, we design a repair operator to adjust an infeasible solution. In particular, given a solution ${\lambda }_i^g$, we traverse each row of ${\lambda }_i^g$, if ${\sum }_{k=1}^N{\lambda }_i^g\left[j\right]\left[k\right]>T$, randomly choose ${\sum }_{k=1}^N{\lambda }_i^g\left[j\right]\left[k\right]-T$ nonzero elements and set them to 0. Consequently, we have ${\sum }_{k=1}^N{\lambda }_i^g\left[j\right]\left[k\right]=T$ by performing the repair operator.
• Population Replacement
  Population replacement is to update the population and keep the population size steady. To achieve this, new individuals are inserted into the current population. Then, we sort the individuals by their fitness values in descending order. Finally, the top-M individuals are selected to form the new population for the next evaluation. The process of population replacement is illustrated in lines 7∼8 within Algorithm 3.

5.2. Time Complexity Analysis

6.1. Simulation Setup

• Average Service Delay (ASD): The delay in service for vehicle $v_k$ ($v_k\in V$) (denoted by $t_k$) is indicated as the duration between entering the simulated area and obtaining all data items in the database. The ASD is computed as the sum of service delays for all vehicles divided by the overall count of vehicles, as follows:

  $$ASD=(\sum _{k=1}^{\left|V\right|}{t}_k)/|V|$$

  (2)
• Average Service Productivity (ASP): Let $r_k$ and $r_k^{\prime }$ denote the ranks of the original and new coefficient matrices, respectively, for vehicle $v_k\in V$, while $n_k$ represents the number of scheduling packets during its service. The ASP is calculated as the sum of the improved rank for each vehicle per scheduling packet divided by the overall count of vehicles, as follows:

  $$ASP=(\sum _{k=1}^{\left|V\right|}\frac{r_k-r_k^{\prime }}{n_k})/|V|$$

  (3)
• Average Service Ratio (ASR): After the simulation, let s denote the total count of vehicles that successfully retrieve all data items. Then, the SR is calculated as follows:

  $$SR=s/\left|V\right|$$

  (4)

6.2. Performance Analysis