Inergency
An online hub for emergency and natural disaster solutions

Joint Efficient UAV Trajectory and Velocity Optimization for IoT Data Collection Using a New Projection Algorithm

5
Joint Efficient UAV Trajectory and Velocity Optimization for IoT Data Collection Using a New Projection Algorithm


In this section, we first introduce CirCo, a joint UAV trajectory and velocity optimization framework, as shown in Figure 4. First, the information of all IoT ground nodes would be collected, including location information and the sizes of the data that need to be transferred. Then, CirCo would group these GNs based on the overlapped transmission ranges, which means all GNs in a connected domain are considered as one cluster, called a GNC. Moreover, a greedy strategy would be adopted to determine the visiting order on the GNC and GN levels, respectively. Furthermore, based on the order and cluster information, CirCo would design the trajectory of the process in each cluster by an algorithm of the projection method and determine the corresponding speed with two-speed selection principles. Moreover, the UAV would finish all data collection tasks as scheduled and calculate the total energy consumption and flight time.

3.2. Design of the Projection Method

After determining the visiting order, the next step is to find the optimal trajectory and velocity to minimize energy consumption. Firstly, we divide the problem into two parts, intra-GNC and inter-GNC.

The inter-GNC is a process where the UAV travels to the next GNC after completing all tasks of the previous GNC. Due to no data collection tasks between GNCs, the UAV only needs to fly at



V
E

from the starting point to the endpoint between any two sequential GNCs, accordingly, Moreover, for the inter-part between the



G
i

and



G

i
+
1


, the starting point is the leaving point when the UAV comes out of



G
i

. Then UAV flies in the direction of the location of the first GN in



G

i
+
1


. Moreover, the endpoint is the border point where the UAV flies to the border of the transmission range of the first GN in



G

i
+
1


.

The intra-GNC is a process where the UAV flies across a series of transmission ranges inside each GNC and finishes all data collection tasks from all GNs within. When planning the trajectory and speed of the UAV, we need to ensure that the UAV could remain long enough in each range of nodes for data collection tasks, which would be more complex. Moreover, it is a key part of the optimization procedure of CirCo. We propose a projection method to simplify and directly solve this problem. Before elaborating on the algorithm details, the mathematical principles are presented in this part.

We leveraged a



3
D

model with three axes, x, y, and t; the x and y axes are used to describe the location of the UAV, while the t axis represents the time of the UAV at a certain location. The velocity of the UAV is described in Equation (13).






V
=




(


Δ
x


Δ
t


)

2

+


(


Δ
y


Δ
t


)

2



=





Δ
x

2

+


Δ
y

2




Δ
t






When the UAV collects data from a GN, it needs to satisfy two constraints: (1) within the transmission range of this GN; (2) the transmission time between the UAV and this GN must be greater than the minimum time requirement of this GN. In a



3
D

space, each GN constraint is a cylinder, as shown in Figure 5a. The UAV needs to pass through the interior of each cylinder from one circular surface to the other. The heights of the cylinders on the t-axis are the values of the actual flight times of these GNs.

Ideally, the UAV should fly in a straight line from the starting point to the endpoint at



V
P

, always within the communication ranges of the GNs, which means that the trajectory in a



3
D

space can pass through all cylinders as the minimum transmission time of these GNs. However, in reality, due to the distribution of GNs and the time requirements of transmission tasks, this ideal case can hardly be achieved. Therefore, in every step, CirCo chooses to pass through as many cylinders as possible, in a straight line, to obtain an approximate optimal solution. However, it is difficult to intuitively judge how many cylinders CirCo can pass through all at once.

Therefore, we propose an ingenious projection method to map this



3
D

problem to



2
D

. Figure 6 illustrates the process of projection. Firstly, CirCo leverages the plane of the first overlapped area (



o

i
,
j


) as the projection plane, i.e., the plane that



t
=

t
1


in Figure 5a. Then, CirCo projects the following overlapped area (



o

i
,
j
+
1


) to this plane, and the result is the overlapped area of the two green circles, as shown in Figure 6a. Then, CirCo can directly derive the feasible crossing window, which is the common intersected region of the first overlapped area (



o

i
,
j


) and the projection area of the following overlapped area (



o

i
,
j
+
1


), marked in green in Figure 6b. If there are more GNs in this cluster, similarly, CirCo needs to project as many overlapped areas as possible until the projection of the next overlapped area has no feasible crossing window. Moreover, the final common intersection region of the first overlapped area (



o

i
,
j


) and all the projection areas are the feasible crossing window. At this point, one projection ends. (The new projection could repeat if needed). Note that the contraction ratio of the projection area to the original overlapped area is related to the minimum transmission time required by each GN. As shown in Figure 5a, if CirCo projects



o

i
,
j
+
1


to the plane of



o

i
,
j


based on the red starting point, then the ratio of the



o

i
,
j
+
1


projection



o

i
,
j
+
1






to



o

i
,
j
+
1


is




t
1

/

t
2


.

After the projection is finished, CirCo will find the optimal trajectory and velocity in the feasible crossing window, which will be explained in detail in the following section.

3.3. Algorithm of CirCo

The algorithm to find the optimal trajectory and velocity in the intra-part leverages an iteration method. Each iteration has three steps. The first step is to find a feasible crossing window. Specifically, project the overlapped areas behind the current overlapped area (



o

i
,
j


) until there is no common region between the initial overlapped area (



o

i
,
j


) and all the projected regions in line 2 of the algorithm, and then the final common region is the feasible crossing window. The second step is to calculate the speed range of the UAV based on the information on the borders of the feasible crossing window. Note that



V

l
o
w


is the low-bound ratio of the shortest trajectory and the minimal time requirement, as parameters used to determine the speed of the UAV, which will be further explained in the following part of choosing the speed. Moreover, it is not the minimal speed of the UAV in reality because if the UAV flies at a lower speed than



V

l
o
w


, it can still finish all of the tasks but may consume more time and energy. The third step is to determine the speed and route of the UAV based on the following Algorithm 1 of choosing the speed.

Algorithm 1 The CirCo algorithm in the jth intra-GNC part

Input:

  • Initialize the first GN (



    g

    i
    ,
    0


    ) in the ith GNC; The total number of GNs in the ith GNC



    J
    i

    ; Initialize two integer variates



    t
    =
    1

    and



    k
    =
    1

    ; Define the feasible crossing window as F; The speed of the UAV V; The speed range



    {

    V

    l
    o
    w


    ,

    V

    u
    p


    }

    .

1:

while



g

i
,
j


(



j


J
i


) unvisited do

2:

   while Project



o

i
,
j
+
t


to the plane of



o

i
,
j


, and obtain



o

i
,
j
+
t






AND

 

   



o

i
,
j
+
t






has no common region with all



o

i
,
j
+
k






(



k

[
1
,
t
]

) and



o

i
,
j


together do  

3:

       Projecting terminate

4:

       



F
=

o

i
,
j




all




o

i
,
j
+
k






,
k


[
1
,
t
]

)

5:

       Obtain the border location of the window

6:
       Calculate the speed range



{

V

l
o
w


,

V

u
p


}

by Equation (9)

7:

       Determine the optimal speed (V)

8:

       Determine the corresponding route of UAV

9:

       



i

i
+
t

10:

   end while

11:

end while

Output: the speed and route of the UAV in the jth GNC

The projecting principle of the feasible crossing window (the first step) is illustrated in Section 3.2. CirCo needs to calculate the speed range and calculate the optimal velocity and trajectory within the feasible crossing window (the second step). Due to the requirement of the minimum transmission time, we can derive the speed range



[

V

l
o
w


,

V

u
p


]

by calculating the ratio of the distance between the farthest point in the boundary and the nearest point of the feasible window to the minimum time, according to Equation (13). We need to choose suitable speeds and trajectories for different conditions (the third step) according to the relationship between the speed range and the minimum power consumption speed. There are three different cases for trajectory and velocity optimization shown in Figure 7.

Case1: If




V

u
p




V
P


, then




V

U
A
V


=

V

u
p



, and UAV follows the path corresponding to



V

u
p


.

Case2: If




V

l
o
w




V
P


, then (1) if




V

l
o
w


>

V
E


, then




V

U
A
V


=

V
E


, and UAV follows the path corresponding to



V

l
o
w


; (2)




V

l
o
w




V
E


, then




V

U
A
V


=

V

l
o
w



and UAV follows the path corresponding to



V

l
o
w


.

Case3: If




V

u
p


>

V
P


and




V

l
o
w


<

V
P


,




V

U
A
V


=

V
P


, and UAV follows the path corresponding to



V
P

.

In addition, for the last GN in one GNC, CirCo needs to determine the trajectory and velocity separately. The location of the endpoint satisfies that: (1) The transmission time must exceed the minimum transmission time. (2) The transmission time must be as close as the minimum transmission time. (3) The speed of the UAV must be as close as the optimal velocity.

To summarize the above procedures—CirCo firstly groups all GNs into multiple GNCs. Then, CirCo determines the visiting order of GNCs and GNs in each GNC, respectively. Finally, CirCo finds the optimal trajectory and velocity in the intra-GNC and inter-GNC parts. For the intra-GNC part, CirCo leverages a projection algorithm to find the feasible crossing window that maps a



3
D

problem to a



2
D

problem for the intra-GNC part. Moreover, CirCo classifies the specific condition and fine-planning of the optimal trajectory and velocity of each condition. For the inter-GNC part, CirCo determines its path and speed based on some proposed principles.

3.4. Computation Complexity Analysis

To determine the trajectory and velocity of the UAV in the range of each node, we may use partial exhaustive research that calculates all situations by traversing all of the points in the transmission range for each node; we then find the optimal set among them for each GN based on the information of the current GN and the following one. However, the computational complexity is too high. Specifically, it is assumed that n GNs in a projection process and the average radius of the transmission range is r. Moreover, the search step is



k
100

(i.e., the default value is 5, which means the step is 0.05 m. Moreover, it can be changed based on the actual scenario). The computational complexity of the exhaustive search is



O
(
n
π


(


100
r

k

)

2

)

. However, CirCo only needs to traverse the border of an intersection area of multiple projected circles in a projection process, so we use




2
π
r

a

to represent the lengths of these borders, in which




1
a

<
<
1

. Moreover, the computational complexity of CirCo is



O
(


200
π
r


a
k


)
)

. Therefore, the partial exhaustive research is




100
a
n
r

k

times as complex as CirCo, pointing out that CirCo can dramatically reduce the computing overhead. Moreover, the result from the exhaustive research method may be inferior to that from CirCo; the exhaustive research only considers the information from the current GN and the following one while CirCo takes the global information into account. The simulations of the trajectory and planning with tens of GNs only need a few seconds on our computing platform (Intel i7-10710U CPU @ 12 cores @ 1.10 GHz).

Comments are closed, but trackbacks and pingbacks are open.