# PB: A Message Transmission Method Based on Area Layer Division in UAV Networks

Authors: Lisong Wang; Feifei Zhu; Qing Zhou; Kui Li; Liang Liu
Journal: International Journal of Aerospace Engineering
 (2019)

---

## Abstract

A search and rescue mission is a typical UAV network application scenario. In this case, it is necessary to deliver messages quickly and efficiently to the ground station through mutual cooperation between UAVs. Many methods used in this case have problems such as unbalancedpopularity (the ratio of the relayed message number to the total message number) of nodes, large proportion of ping-pong effect, and long delay. In view of the above problems, this paper proposes a method named PB (Popularity Balance Method for UAVs in the same area layer) based on division of the whole search area. The method divides the search area into multiple area layers. Message transmission between area layers adopts a geographical routing manner, that is, messages are transmitted to the area layer closer to the ground station. The division of the search area changes the pattern of message transmission. Messages are delivered to the area layer closer to the destination node rather than the node closer to the destination. The pattern causes messages’ passing direction to be replaced by “point-to-point closer” to “point-to-face closer.” On the basis of message transmission at area layers, reasonable planning of UAVs’ distribution can effectively improve the network performance deterioration caused by a “hot spot.” Both analysis and experiments show that PB is superior to some existing methods in popularity balance of nodes and ping-pong effect. In addition, experiments also show that it gets better results in targets of delay, delivery rate, and hop count.


---

## Body

## 1. Introduction

The UAV is a hotspot in the new round of scientific and technological revolution and industrial revolution in the world, and its industrial development is related to national interests [1]. For many tasks, unmanned units are often required to work together to complete a task [2]. At this point, according to the characteristics of the task scene and the characteristics of the unmanned unit network, how to use the appropriate routing method to transfer messages to the destination node becomes an important technical problem [3].UAVs establish high-throughput links through wireless transmission to form a temporary, multihop regional connection, which is a mobile ad hoc network [4]. However, due to the high-speed continuous movement of drones, the network topology of drones changes frequently. When traditional MANET routing methods were used in UAVs, a series of problems occurred, such as low delivery rate and long delay, greatly affecting network performance [5].Therefore, it is necessary to put forward higher requirements for UAV network routing strategy and conduct relevant researches in a targeted manner. At present, in many situations where UAVs are used, task-driven UAVs are employed [6], and the trajectory of the drone is artificially planned in advance. The drones can only move according to the planned trajectory [7]. For the classic scenario—search and rescue [8]—many existing methods use the idea of geographic routing [9] and delay-tolerant network (DTN) routing algorithms [10]. According to analyzing the characteristics of the scene, messages are transmitted to the direction closer to the ground station and are allowed to be stored and carried during transmission. These methods are likely to cause some specific drones to consume a lot of energy for transmitting messages, which will constrain them from completing other tasks [11].In view of the above problems, by analyzing the characteristics of the investigation and rescue mission—the greater regularity of the investigation area—this paper divides the investigation area into multiple regional layers and at the same time uses the idea based on geographic routing to transmit the message to the area near the ground station. The drone node in the middle causes the message to be transmitted closer to the ground station. Due to the uniformity of the distribution of the drones in the scene, the number of messages passing through the drones in each area layer tends to be balanced, which can effectively avoid the appearance of a “hot spot” and improve poor network performance due to the “hot spot.” In addition, when the detection area is far away from the ground station, the message at the nearest regional layer of the ground station is transmitted to the ground station by means of the idea of relaying by the drone, which avoids the back-and-forth movement between a UAV and the ground station. The method also effectively avoids the ping-pong effect generated by the back-and-forth transmission of the message, so as to reduce delay.


## 2. Related Work

In view of the frequent changes of network topology of UAVs, many researchers have studied it. The routing methods mainly include the following:(1)
Traditional Mobile Ad Hoc Network (MANET) Routing Algorithms. The traditional routing protocol OLSR is applied in the network of two microaircrafts and ground stations in [12]. The results show that traditional routing protocols cannot cope with rapidly changing topologies [13]. The main reason is that UAVs move extremely fast and the establishment and breakdown of the communication link is extremely frequent, which causes the network topology to change extremely fast [14]. The traditional mobile ad hoc routing protocol does not have a definite time to converge [15], so the transmission efficiency is low
(2)
DTN Routing Algorithms. Since messages are allowed to be stored and carried, another method is based on a DTN network. DTN routing algorithms are suitable for intermittent connection [10]. Pure DTN routing methods such as epidemic routing [16] often use a multicopy mechanism. One message is copied to the neighbor nodes as often as possible, so that the message can reach the destination node as soon as possible. In [17], R3 is a special case of epidemic routing, which leverages replication to improve delay. In [18], a forwarding mechanism for FANETs is proposed to reduce redundant broadcasts and collisions, thus improving the end-to-end delay and packet delivery ratio. A multicopy mechanism always causes network congestion; thus, excessive messages are congested on the UAV waiting for transmission, which increases delay, so this type of method causes unnecessary copies of messages in the UAV network [19]
(3)
Geographic Routing Algorithms. Another idea is to transmit messages in a direction closer to the target node based on geographic routing [20]. In [21], GeoDTN+Nav is proposed for ground vehicles; thus, navigation information and the store-carry-forward concept are leveraged. In [14], GPMOR, a geography-based routing protocol, is proposed to address the issue of link interruption due to high mobility by selecting the optimal next hop, but it has a low degree of autonomy. In [22], DTNgeo is proposed for UAVs, which is combined with geographic routing and a DTN algorithm. DTNgeo uses a single-copy mechanism to ensure that only one copy of any message exists in the network, and forwards the message to a neighbor node that is closer to the destination in space. If there is no neighbor node closer to the ground station, the message will be carried. When the method is used in a search and rescue scene, messages are always transmitted to the specific drone node closest to the ground station, which makes the number of messages passing through this UAV much larger than others, forming the so-called “hot spot.” The emergence of a “hot spot” will bring many hazards. Firstly, for the energy-limited UAV, the “hot spot” UAV will consume more energy for message transmission, making the UAV consume too much energy, which will constrain the UAV from completing other tasks. In addition, for the whole UAV network, a large number of messages are congested on the “hot spot” waiting for transmission. The congestion not only easily causes packet loss but also increases the waiting time of message transmission, which can result in the reduction of the delivery rate and the increase of delay. In [22], another two heuristic algorithms, DTNclose and DTNload are also proposed to improve network transmission performance. DTNclose additionally considers the position information of the drone after a fixed time interval F on DTNgeo. The neighbor node closest to the destination node after F time is selected as the next node. DTNload additionally considers the load condition of the node in DTNgeo. According to the number of messages to be transmitted by the neighbor node and the message transmission capability in the F time interval, the transmission efficiency of the message to the F time is the highest and the ratio is higher. This is the node whose current node is closer to the destination node. DTNclose and DTNload have a certain improvement on the message delivery rate and the ping-pong effect, but experimental results also show that there is still room for optimization in terms of delivery rate, ping-pong effect ratio, and delay


## 3. A UAV Message Transmission Method Based on Area Layer Division

In this section, we elaborate on the proposed PB and compare it to other methods of related models. Firstly, we model UAV networks, mainly including the search and rescue scene model, the mobility model, and the rules of area layer division, the message transmission methods between area layers, and the rules of ferry UAVs. Secondly, we describe models ofpopularity balance and ping-pong effect, and we analyze the properties between PB and DTNgeo, DTNclose, and DTNload on these two models. Finally, we theoretically analyze the advantages of PB compared with DTNgeo, DTNclose, and DTNload.


### 3.1. Modeling UAV Networks

#### 3.1.1. Modeling Case Scenario—Search and Recuse

For a typical scene—search and rescue—the target person is waiting to be rescued in the search area. If the search area is large, artificially invested on-site investigation can cause a large amount of human and financial losses because of the unknown geographical situation. Meanwhile, using a unit of UAVs can greatly reduce the loss [23]. UAVs need to collect the picture message in the search area, and transmit collected messages to the ground station as soon as possible. Then, related people in the ground station can piece together the topography in the area to find the location of the target person, and seek the fastest and safest way to save. This task is completely controlled by the ground station, so the trajectory and allocation of drones are all arranged in advance [24].Since the communication range of UAVs and the ground station are all limited, drones cannot directly establish communication links with the ground station when they are far away from the ground station. Admittedly, flying back to the ground station is a simple, but power-hungry solution that does not scale well. Observing UAVs should use their scarce battery power on mission-driven tasks instead of consuming it by moving closer to the transmission peer (in a testbed of quadcopters, we measured a power consumption of about 200-250 Watts for autonomous flight; the dominating factor is the mechanical part of the copter [25]). Similarly, dense placement of relay UAVs for maintaining connectivity is a possible solution; however, this solution comes at high deployment and operational costs. By introducing ferry nodes to establish connectivity, most of the UAVs may search while the ferries move data physically before transmitting. Note that every UAV in the network may additionally relay messages when possible, including the searching UAVs. It is a plan that takes into account the energy and drone resources.In a multi-UAV system, the specific functions of searching UAVs and ferry UAVs are as follows:(1)
Searching UAV: collecting pictures and also acting as a relay for message transmission
(2)
Ferry UAV: acting only as a relay, to help searching UAVs quickly transmit messages to the groundThis article uses a rectangular search area as an illustration, as shown in Figure1.Figure 1
Example of a search and rescue scenario with UAVs.Here, the Ground is responsible for the planning and analysis of the entire task. Before a task, people in the ground station divide all of the search area into multiple parts and plan the running track of UAVs. During the task, the operation track and running direction of drones are controlled by the control signal. In addition, when messages are returned, the ground station needs to parse them, piece them together to find the location of the target person, and find a suitable search and rescue path.In addition, the relevant areas can be divided into three categories, and the relevant definitions are described as follows:(1)
Search area (abbreviated as SA): the entire area to be investigated, which is shown as ABCD in Figure 1, where height is represented as Hall and width is represented as Wall
(2)
Area layer (abbreviated as AL): multiple subarea layers of the entire search area according to the hierarchy, which is shown as AEID in Figure 1
(3)
Subsearch area (abbreviated as SSA): the area of each drone’s searching part, which is shown as EFGH in Figure 1, where height is expressed as Hm and width is expressed as WmThese three types of areas are related to each other. IfareaSA, areaAL, and areaSSA are used to represent the area of SA, AL, and SSA, the following relationships are satisfied:
(1)
∑areaAL=areaSA, that is, the sum area of all area layers is the area of the search area
(2)
∑areaSSA=areaSA, that is, the sum area of all subsearch areas is the area of the search area
(3)
LetALi be the No. i AL, sumi be the number of searching UAVs in the ALi, SSAj is the area of No. j UAV in ALi, and then ∑j=1sumiareaSSAj=areaALi, that is, the sum area of all subsearch areas in the same area layer is the area of that area layerAdditionally, in order to perform the mission faster and easier, the following requirements should be met when designing the drones’ trajectory [26]:
(1)
The number of UAVs in each area layer tends to be the same
(2)
The size and shape of each SSA tend to be the same
(3)
The trajectory of drones tends to be the same


#### 3.1.2. UAV Mobility Model

The motion of the drone can be described as a linear, directional movement model [13], and the trajectory of the drone is determined by the ground station when performing the investigation-search and rescue mission [27]. For the convenience of description, this paper selects straight flight as the trajectory of each drone in a real scene, as shown in Figure 2.Figure 2
UAV mobility model.We describe the subsearch area as a rectangle. The entire area GHIJ is the detection module of each drone. LetHm be the height of the subsearch area in y-axis, Wm be the width of the subsearch area in the x-axis direction, and Rg be the maximum perception of the sensor on the drone. In order to ensure that all UAVs can complete the investigation of the entire area, it must be ensured that the area of each UAV’s investigation is not less than the subsearch area, that is, the detection range covered by the movement track of each UAV is not less than the subsearch area. Therefore, the following constraints must be met between the drone and the reconnaissance module:
(1)x0−a2+y0−b2≤Rg,x0+k0−a−Wm2+y0+k1−b−Hm2≤Rg.When the above constraint (1) is satisfied, the drone can complete the investigation of the entire module. The drone selects a point as the starting position, and we take the point Ax0,y0 as the starting point as an example for the description. It moves along the AB direction through the k1 distance to point Bx0,y0+k1. The direction of motion begins to move along BC to point Cx0+k2/2,y0, reaching point C again to change direction along the CD motion, and to point Dx0+k2,y0+k1 again to change direction to point Ex0+k2,y0. Thus, after changing the direction of motion multiple times, the drone will complete the task of detecting the entire module via A→B→C→D→E→F→A. The position of the drone at each moment is related to its initial position x0,y0 and moving speed v and direction of motion, giving the relationship between the position x,y of the drone and time t (where t0 is just the point when the task is changed in the running direction):
(1)
Movement equation along the AB direction: when a drone moves in the AB direction, the task time is represented ast∈0,k1/v; let t0=0, and the equation of motion at this period is as follows:
(2)x=x0,y=y0+v·t−t0
(2)
Movement equation along the BC direction: when a drone moves in the AB direction, the task time is represented as(3)t∈k1v,k1v+k12+k222
let(4)t0=k1v
the equation of motion at this period is as follows:(5)x=x0+k2·v·t−t02k12+k2/22,y=y0+k1−k1·v·t−t0k12+k2/22
(3)
Movement equation along the CD direction: when a drone moves in the CD direction, the task time is represented as(6)t∈k1v+k12+k222,k1v+2k12+k222
let(7)t0=k1v+k12+k222
the equation of motion at this period is as follows:(8)x=x0+k22+k2·v·t−t02k12+k2/22,y=y0−k1·v·t−t0k12+k2/22
(4)
Movement equation along the DE direction: when a drone moves in the DE direction, the task time is represented as(9)t∈k1v+2k12+k222,2k1v+2k12+k222
let(10)t0=k1v+2k12+k222
the equation of motion at this period is as follows:(11)x=x0+k2,y=y0+k1−v·t−t0
(5)
Movement equation along the EF direction: when a drone moves in the EF direction, the task time is represented as(12)t∈2k1v+2k12+k222,2k1v+3k12+k222,
let(13)t0=2k1v+2k12+k222
the equation of motion at this period is as follows:(14)x=x0+k2−k2·v·t−t02k12+2,y=y0+k1·v·t−t0k12+k2/22
(6)
Movement equation along the FA direction: when a drone moves in the FA direction, the task time is represented as(15)t∈2k1v+3k12+k222,2k1v+4k12+k222
let(16)t0=2k1v+3k12+k222,the equation of motion at this period is as follows:
(17)x=x0+k22−k2·v·t−t02k12+k2/22,y=y0+k1−k1·v·t−t0k12+k2/22
Therefore, after the time2k1/v+4k12+k2/22, the drone completes the task of detection, perception, and collection of messages in the entire SSA. In addition, due to interference from outdoor geography, signals, and other factors, the drone may need to repeat the investigation after a round of investigation to ensure the accuracy and completeness of messages.


#### 3.1.3. Division Rules of Area Layers

In this paper, the detection area is a rectangle, and the height and width of the task area are represented byHall and Wall. The task area is divided into multiple area layers according to the hierarchical structure, so that the drone is routed according to the hierarchical increment method, as shown in Figure 3. For each area layer, in order to ensure that the UAVs in the area layer can communicate, the division of the area layer satisfies the following rules.Rule 1.
Leth be the height of AL and let Range be the maximum communication range of a UAV, then h≤Range.Figure 3
The setting of ferry UAVs.f1‐fn are ferry UAVs, and they move back between bs and be with the same speed.Rule1 ensures that UAVs in the upper and lower ALs can transmit messages.Rule 2.
Letw and Hall be the width of the area layer and the height of the detection area and let Numsub be the number of ALs, then Numsub≥Hall/Range.Rule2 can be calculated from Rule 1.Rule 3.
The rule of numbering ALs. ALs are numbered far and near according to the distance from the ground station.Letsri be the No.i AL and let n be the number of ALs. According to Rule 3, shown in Figure 3, the AL farthest from the ground station is numbered as sr1, and the area layer closest to the ground is numbered as srn, so that messages are transmitted in the direction of increasing area layer.


#### 3.1.4. Message Transmission Method between Adjacent Area Layers—PB

Multiple searching UAVs are allocated in each AL to detect, sense, and collect messages. Messages are transmitted from the current AL to the next high AL. For each AL namedsri and each searching UAV mij∈sri, we compare the distance of all the neighbors located in the moment, and select the next node mi+1kinsri+1 that fulfills the following condition:
(18)argminjdmij,mi+1ksubjecttodmij,mi+1k≤Range.In the formula,dmij,mi+1k is the geographical distance of node mij to the node mi+1k. dmij,mi+1k<Range ensures that the drone in sri can establish connections with drones in sri+1. PB selects the closest neighbor in sri+1 as the next node to reduce delay. The algorithm PB (Popularity Balance Method for UAVs in the same area layer) is shown as Algorithm 1.Algorithm 1: PB.
1:formijinsri do
2: procedure PBmij,next,Mdata  //Sending Mdata from mij to next
3:  fora∈1,Numsri+1 do
4:   ifdmij,mi+1a≤Range and dmij,mi+1a<dmij,mi+1k then
5:k←a
6:   end if
7:  end for
8:  FORWARDTomi+1k,Mdata  //Sending Mdata to mi+1k
9: end procedure
10:end forAs a result, messages insri transfer along sri,sri+1,sri+2,⋯,srn, and finally to the highest AL, which is named srn.


#### 3.1.5. Setting Rules of Ferry UAVs

When there is a certain distance between the detection area and the ground station, the text [22] additionally uses ferry UAVs to move back and forth between the searching UAVs and the ground station to help the message transmission. When a drone uses a geographical routing method for message transmission, a large number of messages will be transmitted back and forth. This article resets the running rules of ferry UAVs, so that the message is still transmitted to the ground station in a hierarchical manner. The setting of the ferry UAV satisfies the following rules.Rule 4.
Numbering rules for ferry UAV. The ferries are numbered far and near according to the distance from the ground station.Letfi be the No.i ferry UAV and let n be the number of ferry UAVs. According to Rule 4 above, the ferry farthest from the ground station is numbered f1, as shown in Figure 3, and ferries are numbered from the search area to Ground via f1,f2,f3,⋯,fn in order.Rule 5.
LetdG,SA be the distance between the ground and SA, let Rg be the maximum sensing range of each searching UAV, and let Rf be the maximum communication range of each ferry, so the number of ferry UAVs Numferry needs to satisfy the formula: Numferry×Rf>dG,SA+Rg.According to Rule5 above, fn can establish a connection with searching UAVs in the highest AL srn during the task time, and messages can be transmitted to the ground via f1,f2,f3,⋯,fn.Rule 6.
The operating rule of ferry UAVs. Each ferry moves back and forth along the width of SA.According to Rule6 above, shown in Figure 3, the ferry moves back and forth between the boundary bs and be. Ferry UAVs expand the communication range of SA, so that messages can reach the ground station via f1,f2,f3,⋯,fn, and finally to Ground.Rule 7.
Distance rule between adjacent ferry UAVs. At any timet during the mission, the distance between adjacent ferries dtfi,fi+1 is always less than its maximum communication range Rf, that is, ∀t,∃i∈1,Numferry−1,dtfi,fi+1≤Rf.According to Rule7 above, the adjacent ferry UAVs remain connected; thus, messages can transmit to a higher-number ferry at all times.Rule 8.
Distance rule between ferry UAVs and ground. At some timet during the mission, the distance between the highest-number ferry fn and ground G can be less than the ferry’s maximum communication range Rf, that is, ∃t,dtfn,G≤Rf.According to Rule8 above, the highest-number ferry UAV can be connected to the ground during the mission time, so that messages can be transmitted to the ground station.


#### 3.1.6. Modeling thePopularity Balance of Searching UAVs

To evaluate the overheads associated with the detection tasks, we consider two aspects—the overhead of the message and overhead of the UAV. In terms of messages, we mainly consider time delay, which is the time from when the messages are perceived to the time it reaches the ground station. In terms of UAVs, the main cost is the battery. One one hand, UAVs need to fly to the required area and to move along a planned track to detect messages. One other hand, UAVs need to collect messages through sensors and need to transmit messages back to the ground station [27]. All these processes cost energy. The cost of flying is hard to avoid and each UAV similarly remains in the search and rescue scene. However, the different locations of the UAVs require them to use up different amounts energy to transmit messages because of the different number of messages passed on. Based on these, for the convenience of discussion, we analyse the unbalanced transmission of messages on different UAVs.Sometimes, if an unsuitable transmission method is chosen to transmit messages, it can cause a “hot spot.” A “hot spot” means that the number of messages passing on a node is much larger than the number of messages passing on other nodes. It spends a lot of energy on message transmission, and it could probably not have enough energy to complete the investigation task, which may bring unpredictable losses, so we should take measures to avoid a “hot spot” as much as possible [28].“Popularity” is proposed to indicate the ratio of the relayed message number to the total message number. Based on geographic routing, messages are transmitted closer to the destination; thus, the number of messages passing through some drones closer to the ground is much larger than number of messages passing through drones far from the ground [29].Therefore, for the entire UAV network, thepopularity of all UAVs is definitely not balanced. So, in this paper, we only discuss the popularity degree of the searching UAVs in the same AL to analyze whether there is a “hot spot.” Based on this, we use the variance FCi to represent the popularity balance of searching UAVs in each AL. For the convenience of description, the relevant symbol representations are shown in Table 1.Table 1
Symbol description.
Symbol
Value
mij
No.j searching UAV in No.i AL
sri
No.i AL
Numsri
The number of searching UAVs insri
Smij
The total number of messages passing on allmij
SNi¯
Average number of allSmij in sri
FCi
Thepopularity balance of searching UAVs in sri
Scollectmij
Total number of messages collected bymij
Sreceivemij
Total number of messages received bymij
e
The number of messages collected per second for each searching UAV (s/sec)
T
Task duration (s)
Pa,b
Probability of message transmission between UAVa and b
mi
The set of searching UAVs insri
ferry
The set of all ferry UAVs
searching
The set of all searching UAVsThe model ofpopularity balance of searching UAVs in sri is given as follows:
(19)FCi=∑j=1NumsriSmij−SNi¯2.The number of messages relayed on each searching UAV is the total number of messages collected and received from others, andSmij can be described as follows:
(20)Smij=Scollectmij+Sreceivemij,where Scollectmij denotes the sum number of messages collected by mij during task duration T:
(21)Scollectmij=e×T.Additionally,others represents the set of drones other than mij, and Po,mij represents the probability of message transmission between o∈others and mij; thus, Sreceivemij can be expressed through the following equation:
(22)Sreceivemij=∑o∈othersSo·Po,mij.Thus, the total number of messages passing on all searching UAVs in each ALSsri can fulfill the following condition:
(23)Ssri=∑j=1NumsriSmij.In addition, based on equation (23), the average messages SNi¯ in equation (19) can be expressed as follows:
(24)SNi¯=SsriNumsri.Obviously, it can be seen from equation (19) that the larger the value of FCi, the more unbalanced the popularity of the drones and the more likely the “hot spot” appears. So in order to avoid the “hot spot,” we hope that the total number of messages passing on different searching UAVs tends to be the same.


#### 3.1.7. Modeling the Effect of Ping-Pong

The “Ping-pong effect” means that a message is transmitted from one node to another and then back to the node, that is, the transmission path of the message exists in a loop [30].In order to analyze the proportion of messages in the UAV network that produces the ping-pong effect, we can simply express the number of messages in the loop in the message transmission asNumpp and the total number of received messages as totalmessage, then the ping-pong effect model can be expressed as follows:
(25)PP=Numpptotalmessage.Obviously, it can be seen from the above formula that when the total number of received messages is the same, the more messages that have loops, the larger the proportion of the ping-pong effect.


### 3.2. Properties of the Models ofPopularity Balance and Ping-Pong Effect

For the models of thepopularity balance and ping-pong effect in Section 3.1, this section analyzes the characteristics of PB, DTNgeo, DTNload, and DTNclose methods to obtain the following series of properties.Property 1.
For a certain layersr1 in PB, Sm1j=e×t,j∈Numsr1.Proof.
PB causes messages to be transmitted to a higher-numbered AL. The drones in the lowest ALsr1 do not receive messages from other ALs, that is, for mij in sr1,∀o∈others,Po,mij=0, so equation (22) can be converted as follows:
(26)Sreceivem1j=0.
Therefore, equation (20) can be simplified as Sm1j=Scollectm1j=e×t.Property 2.
For a certain layersr1 in PB, SN1¯=e×t.Proof.
According to Property1, when i=0, equation (23) can be simplified as follows:
(27)SN1¯=Numsr1×e×tNumsr1=e×t.Property 3.
LetFC1PB be the situation of popularity balance in sr1 for PB, and it can be calculated that FC1PB=0.Proof.
According to Properties1 and 2, equation (19) can be simplified as follows:
(28)FC1PB=∑j=1Numsr1e×t−e×t2=0.Property 4.
For PB,∀k∈1,Numsri,Smik≈e×t×i.Proof.
(1)
Wheni=1, according to Property 1, we can get the following:
(29)∀k∈1,Numsr1,Sm1k=e×t.
(2)
Analyze the result wheni≠1
According to design requirement (1) of the search and rescue model in Section 3.1, it can be deduced that
(30)∀i,j∈1,n,Numsri=Numsrj.
Since messages are transmitted in the direction of the higher-numbered AL, the message in this area layer is only transmitted to the next higher AL, so formij in sri, others in equation (22) can be expressed as
(31)others=mi−1,where mi−1 represents the set of all searching UAVs in sri.
Thus, equation (22) can be simplified as follows:
(32)Smij=e×t+∑omi−1So·Po,mij.In addition, according to design requirements (2) and (3) of the search and rescue model in Section 3.1, we can analyze that any drone in sri has a similar probability of message transmission with other drones, which can be expressed as
(33)∀x,y∈1,Numsri,∑omi−1So·Po,mix≈∑omi−1So·Po,miy.From equations (32) and (33), it can be deduced that
(34)∀x,y∈1,Numsri,Smix≈Smiy.From (1), i=1, ∀k∈1,Numsr1,Sm1k=e×t; when not considering conditions such as packet loss, it can be deduced that
(35)Sm2k≈e×t+SN1¯=e×t+e×t=2×e×t,Sm3k≈e×t+SN2¯=e×t+2×e×t=3×e×t.Thus, it can be obtained through mathematics that(36)S≈e×t×i,i≠1.The following conclusion can be drawn from the discussion wheni=1 and i≠1:
(37)∀k∈1,Numsri,Smik≈e×t×i.where searching represents the set of all searching UAVs and ferry represents the set of all ferry UAVs.Property 5.
For PB, it can be deduced that∀i∈1,Numsub,SNi¯≈e×t×i.Proof.
According to Property4, equation (23) can be simplified as follows:
(38)SNi¯≈Numsri×e×t×iNumsri=e×t×i.Property 6.
LetFCiPB be the situation of popularity balance in sri,i∈1,Numsub, and it can be deduced that FCiPB≈0.Proof.
According to Property4 and Property 5, equation (19) can be simplified as follows:
(39)FCiPB≈∑j=1Numsrie×t×i−e×t×i2=0.Property 7.
For a certain layersri,i∈1,Numsub in DTNgeo, DTNclose, and DTNload, it can be deduced that
(40)Smij=e×t+∑osearching−mij+ferrySo·Po,mij,where searching is the set of all searching UAVs and ferry is all ferry UAVs.Proof.
Since ferries move back and forth between the ground and searching UAVs, each searching UAV receives the number of messages transmitted from the other searching UAVs and ferry UAVs. Therefore, formij in sri, others in equation (22) can be expressed as
(41)others=searching−mij+ferry,Therefore, equation (22) can be simplified as
(42)Smij=e×t+∑osearching−mij+ferrySo·Po,mij.Property 8.
ForDTNgeo, DTNclose, and DTNload, it can be deduced that Smia≫Smib,a∈HA,b∉HA, where HA represents a “hot area” that means some area nearer the destination than others in each AL.Proof.
ForDTNgeo, DTNclose, and DTNload, any drone selects the neighbor node closest to the ground as the next node. Each time that mik selects the next node, the drone always select some node with a higher probability [31]; it can be expressed as follows:
(43)Pmik,a≫Pmik,ba∈HA,b∉HA.
According to Property7 and formula (43), it can be deduced that
(44)Smia≫Smib.Property 9.
LetFCiDTNgeo,FCiDTNclose, and FCiDTNload be the situation of popularity balance of DTNgeo,DTNclose,DTNload sri,i∈1,Numsub in the three schemes; it can be calculated that FCiDTNgeo≫0,FCiDTNclose≫0, and FCiDTNload≫0.Proof.
According to Property8, and with the characteristics of equation (19)—when values of Smij are not equal to each other and the difference is larger, the value FCi is greater, and it can be deduced that
(45)FCiDTNgeo≫0,FCiDTNclose≫0,FCiDTNload≫0.Property 10.
For PB,Numpp=0.Proof.
All messages are transmitted viasri,sri+1,sri+2,⋯,srn,f1,f2,⋯,fn,G, so there is no loop in the transmission path; thus, Numpp=0.Property 11.
ForDTNgeo, DTNclose, and DTNload, Numpp>0.Proof.
DTNgeo transmits messages to the neighbor node closest to the ground, and because ferries move back and forth between searching UAVs and the ground, the distance between ferries and the ground always changes. If one ferry is closest to the ground station in the neighbor node, messages will be transmitted to that at the time. If one ferry is far away from the ground, the messages will be retransmitted back; there exists a loop in the transmission path, so Numpp>0.


### 3.3. Comparison of PB withDTNgeo, DTNload, and DTNclose in the Popularity Balance and Ping-Pong Effect

Theorem 1.
FCiPB<FCiDTNgeo.Proof.
According to Property6 and Property 9, it can be deduced that
(46)FCiPB<FCiDTNgeo.Theorem 2.
LetPPPB and PPDTNgeo be the ping-pong effect ratio of PB and DTNgeo, respectively, then PPPB<PPDTNgeo.Proof.
According to Property10 and Property 11, with the same value of totalmessage, equation (25) can be deduced as follows:
(47)PPPB<PPDTNgeo.Theorem 3.
FCiPB<FCiDTNclose.Proof.
According to Property6 and Property 9, it can be deduced that
(48)FCiPB<FCiDTNclose.Theorem 4.
LetPPPB and PPDTNclose be the ping-pong effect ratio of PB and DTNclose, respectively, then PPPB<PPDTNclose.Proof.
According to Property10 and Property 11, with the same value of totalmessage, equation (25) can be deduced as follows:
(49)PPPB<PPDTNclose.Theorem 5.
FCiPB<FCiDTNload.Proof.
According to Property6 and Property 9, it can be deduced that
(50)FCiPB<FCiDTNload.Theorem 6.
LetPPPB and PPDTNload be the ping-pong effect ratio of PB and DTNload, respectively, then PPPB<PPDTNload.Proof.
According to Property10 and Property 11, with the same value of totalmessage, equation (25) can be deduced as follows:
(51)PPPB<PPDTNload.


### 3.4. Comparison of PB withDTNgeo, DTNload, and DTNclose in the Complexity of the Algorithm

Theorem 7.
LetOPB,ODTNgeo,ODTNload and ODTNclose be the complexity of PB, DTNgeo, DTNload, and DTNclose, then OPB<ODTNgeo=ODTNclose=ODTNload.Proof.
For PB, since each drone always selects the drone that is closer to itself in the next area layer for transmission of messages, it only needs to calculate distances of drones in the next area layer. Forn drones in the whole system, if the number of drones in each area layer is k, the complexity of PB OPB=On∗k, where k<n.ForDTNgeo, DTNload, and DTNclose, when each drone chooses a message transmission object, it needs to calculate the distances of all the other drones. For n drones in the whole system, the complexity of DTNgeo, DTNload, and DTNclose ODTNgeo=ODTNclose=ODTNload=On2.Therefore,OPB<ODTNgeo=ODTNclose=ODTNload, that is PB has lower complexity than DTNgeo, DTNload, and DTNclose.


## 3.1. Modeling UAV Networks

### 3.1.1. Modeling Case Scenario—Search and Recuse

For a typical scene—search and rescue—the target person is waiting to be rescued in the search area. If the search area is large, artificially invested on-site investigation can cause a large amount of human and financial losses because of the unknown geographical situation. Meanwhile, using a unit of UAVs can greatly reduce the loss [23]. UAVs need to collect the picture message in the search area, and transmit collected messages to the ground station as soon as possible. Then, related people in the ground station can piece together the topography in the area to find the location of the target person, and seek the fastest and safest way to save. This task is completely controlled by the ground station, so the trajectory and allocation of drones are all arranged in advance [24].Since the communication range of UAVs and the ground station are all limited, drones cannot directly establish communication links with the ground station when they are far away from the ground station. Admittedly, flying back to the ground station is a simple, but power-hungry solution that does not scale well. Observing UAVs should use their scarce battery power on mission-driven tasks instead of consuming it by moving closer to the transmission peer (in a testbed of quadcopters, we measured a power consumption of about 200-250 Watts for autonomous flight; the dominating factor is the mechanical part of the copter [25]). Similarly, dense placement of relay UAVs for maintaining connectivity is a possible solution; however, this solution comes at high deployment and operational costs. By introducing ferry nodes to establish connectivity, most of the UAVs may search while the ferries move data physically before transmitting. Note that every UAV in the network may additionally relay messages when possible, including the searching UAVs. It is a plan that takes into account the energy and drone resources.In a multi-UAV system, the specific functions of searching UAVs and ferry UAVs are as follows:(1)
Searching UAV: collecting pictures and also acting as a relay for message transmission
(2)
Ferry UAV: acting only as a relay, to help searching UAVs quickly transmit messages to the groundThis article uses a rectangular search area as an illustration, as shown in Figure1.Figure 1
Example of a search and rescue scenario with UAVs.Here, the Ground is responsible for the planning and analysis of the entire task. Before a task, people in the ground station divide all of the search area into multiple parts and plan the running track of UAVs. During the task, the operation track and running direction of drones are controlled by the control signal. In addition, when messages are returned, the ground station needs to parse them, piece them together to find the location of the target person, and find a suitable search and rescue path.In addition, the relevant areas can be divided into three categories, and the relevant definitions are described as follows:(1)
Search area (abbreviated as SA): the entire area to be investigated, which is shown as ABCD in Figure 1, where height is represented as Hall and width is represented as Wall
(2)
Area layer (abbreviated as AL): multiple subarea layers of the entire search area according to the hierarchy, which is shown as AEID in Figure 1
(3)
Subsearch area (abbreviated as SSA): the area of each drone’s searching part, which is shown as EFGH in Figure 1, where height is expressed as Hm and width is expressed as WmThese three types of areas are related to each other. IfareaSA, areaAL, and areaSSA are used to represent the area of SA, AL, and SSA, the following relationships are satisfied:
(1)
∑areaAL=areaSA, that is, the sum area of all area layers is the area of the search area
(2)
∑areaSSA=areaSA, that is, the sum area of all subsearch areas is the area of the search area
(3)
LetALi be the No. i AL, sumi be the number of searching UAVs in the ALi, SSAj is the area of No. j UAV in ALi, and then ∑j=1sumiareaSSAj=areaALi, that is, the sum area of all subsearch areas in the same area layer is the area of that area layerAdditionally, in order to perform the mission faster and easier, the following requirements should be met when designing the drones’ trajectory [26]:
(1)
The number of UAVs in each area layer tends to be the same
(2)
The size and shape of each SSA tend to be the same
(3)
The trajectory of drones tends to be the same


### 3.1.2. UAV Mobility Model

The motion of the drone can be described as a linear, directional movement model [13], and the trajectory of the drone is determined by the ground station when performing the investigation-search and rescue mission [27]. For the convenience of description, this paper selects straight flight as the trajectory of each drone in a real scene, as shown in Figure 2.Figure 2
UAV mobility model.We describe the subsearch area as a rectangle. The entire area GHIJ is the detection module of each drone. LetHm be the height of the subsearch area in y-axis, Wm be the width of the subsearch area in the x-axis direction, and Rg be the maximum perception of the sensor on the drone. In order to ensure that all UAVs can complete the investigation of the entire area, it must be ensured that the area of each UAV’s investigation is not less than the subsearch area, that is, the detection range covered by the movement track of each UAV is not less than the subsearch area. Therefore, the following constraints must be met between the drone and the reconnaissance module:
(1)x0−a2+y0−b2≤Rg,x0+k0−a−Wm2+y0+k1−b−Hm2≤Rg.When the above constraint (1) is satisfied, the drone can complete the investigation of the entire module. The drone selects a point as the starting position, and we take the point Ax0,y0 as the starting point as an example for the description. It moves along the AB direction through the k1 distance to point Bx0,y0+k1. The direction of motion begins to move along BC to point Cx0+k2/2,y0, reaching point C again to change direction along the CD motion, and to point Dx0+k2,y0+k1 again to change direction to point Ex0+k2,y0. Thus, after changing the direction of motion multiple times, the drone will complete the task of detecting the entire module via A→B→C→D→E→F→A. The position of the drone at each moment is related to its initial position x0,y0 and moving speed v and direction of motion, giving the relationship between the position x,y of the drone and time t (where t0 is just the point when the task is changed in the running direction):
(1)
Movement equation along the AB direction: when a drone moves in the AB direction, the task time is represented ast∈0,k1/v; let t0=0, and the equation of motion at this period is as follows:
(2)x=x0,y=y0+v·t−t0
(2)
Movement equation along the BC direction: when a drone moves in the AB direction, the task time is represented as(3)t∈k1v,k1v+k12+k222
let(4)t0=k1v
the equation of motion at this period is as follows:(5)x=x0+k2·v·t−t02k12+k2/22,y=y0+k1−k1·v·t−t0k12+k2/22
(3)
Movement equation along the CD direction: when a drone moves in the CD direction, the task time is represented as(6)t∈k1v+k12+k222,k1v+2k12+k222
let(7)t0=k1v+k12+k222
the equation of motion at this period is as follows:(8)x=x0+k22+k2·v·t−t02k12+k2/22,y=y0−k1·v·t−t0k12+k2/22
(4)
Movement equation along the DE direction: when a drone moves in the DE direction, the task time is represented as(9)t∈k1v+2k12+k222,2k1v+2k12+k222
let(10)t0=k1v+2k12+k222
the equation of motion at this period is as follows:(11)x=x0+k2,y=y0+k1−v·t−t0
(5)
Movement equation along the EF direction: when a drone moves in the EF direction, the task time is represented as(12)t∈2k1v+2k12+k222,2k1v+3k12+k222,
let(13)t0=2k1v+2k12+k222
the equation of motion at this period is as follows:(14)x=x0+k2−k2·v·t−t02k12+2,y=y0+k1·v·t−t0k12+k2/22
(6)
Movement equation along the FA direction: when a drone moves in the FA direction, the task time is represented as(15)t∈2k1v+3k12+k222,2k1v+4k12+k222
let(16)t0=2k1v+3k12+k222,the equation of motion at this period is as follows:
(17)x=x0+k22−k2·v·t−t02k12+k2/22,y=y0+k1−k1·v·t−t0k12+k2/22
Therefore, after the time2k1/v+4k12+k2/22, the drone completes the task of detection, perception, and collection of messages in the entire SSA. In addition, due to interference from outdoor geography, signals, and other factors, the drone may need to repeat the investigation after a round of investigation to ensure the accuracy and completeness of messages.


### 3.1.3. Division Rules of Area Layers

In this paper, the detection area is a rectangle, and the height and width of the task area are represented byHall and Wall. The task area is divided into multiple area layers according to the hierarchical structure, so that the drone is routed according to the hierarchical increment method, as shown in Figure 3. For each area layer, in order to ensure that the UAVs in the area layer can communicate, the division of the area layer satisfies the following rules.Rule 1.
Leth be the height of AL and let Range be the maximum communication range of a UAV, then h≤Range.Figure 3
The setting of ferry UAVs.f1‐fn are ferry UAVs, and they move back between bs and be with the same speed.Rule1 ensures that UAVs in the upper and lower ALs can transmit messages.Rule 2.
Letw and Hall be the width of the area layer and the height of the detection area and let Numsub be the number of ALs, then Numsub≥Hall/Range.Rule2 can be calculated from Rule 1.Rule 3.
The rule of numbering ALs. ALs are numbered far and near according to the distance from the ground station.Letsri be the No.i AL and let n be the number of ALs. According to Rule 3, shown in Figure 3, the AL farthest from the ground station is numbered as sr1, and the area layer closest to the ground is numbered as srn, so that messages are transmitted in the direction of increasing area layer.


### 3.1.4. Message Transmission Method between Adjacent Area Layers—PB

Multiple searching UAVs are allocated in each AL to detect, sense, and collect messages. Messages are transmitted from the current AL to the next high AL. For each AL namedsri and each searching UAV mij∈sri, we compare the distance of all the neighbors located in the moment, and select the next node mi+1kinsri+1 that fulfills the following condition:
(18)argminjdmij,mi+1ksubjecttodmij,mi+1k≤Range.In the formula,dmij,mi+1k is the geographical distance of node mij to the node mi+1k. dmij,mi+1k<Range ensures that the drone in sri can establish connections with drones in sri+1. PB selects the closest neighbor in sri+1 as the next node to reduce delay. The algorithm PB (Popularity Balance Method for UAVs in the same area layer) is shown as Algorithm 1.Algorithm 1: PB.
1:formijinsri do
2: procedure PBmij,next,Mdata  //Sending Mdata from mij to next
3:  fora∈1,Numsri+1 do
4:   ifdmij,mi+1a≤Range and dmij,mi+1a<dmij,mi+1k then
5:k←a
6:   end if
7:  end for
8:  FORWARDTomi+1k,Mdata  //Sending Mdata to mi+1k
9: end procedure
10:end forAs a result, messages insri transfer along sri,sri+1,sri+2,⋯,srn, and finally to the highest AL, which is named srn.


### 3.1.5. Setting Rules of Ferry UAVs

When there is a certain distance between the detection area and the ground station, the text [22] additionally uses ferry UAVs to move back and forth between the searching UAVs and the ground station to help the message transmission. When a drone uses a geographical routing method for message transmission, a large number of messages will be transmitted back and forth. This article resets the running rules of ferry UAVs, so that the message is still transmitted to the ground station in a hierarchical manner. The setting of the ferry UAV satisfies the following rules.Rule 4.
Numbering rules for ferry UAV. The ferries are numbered far and near according to the distance from the ground station.Letfi be the No.i ferry UAV and let n be the number of ferry UAVs. According to Rule 4 above, the ferry farthest from the ground station is numbered f1, as shown in Figure 3, and ferries are numbered from the search area to Ground via f1,f2,f3,⋯,fn in order.Rule 5.
LetdG,SA be the distance between the ground and SA, let Rg be the maximum sensing range of each searching UAV, and let Rf be the maximum communication range of each ferry, so the number of ferry UAVs Numferry needs to satisfy the formula: Numferry×Rf>dG,SA+Rg.According to Rule5 above, fn can establish a connection with searching UAVs in the highest AL srn during the task time, and messages can be transmitted to the ground via f1,f2,f3,⋯,fn.Rule 6.
The operating rule of ferry UAVs. Each ferry moves back and forth along the width of SA.According to Rule6 above, shown in Figure 3, the ferry moves back and forth between the boundary bs and be. Ferry UAVs expand the communication range of SA, so that messages can reach the ground station via f1,f2,f3,⋯,fn, and finally to Ground.Rule 7.
Distance rule between adjacent ferry UAVs. At any timet during the mission, the distance between adjacent ferries dtfi,fi+1 is always less than its maximum communication range Rf, that is, ∀t,∃i∈1,Numferry−1,dtfi,fi+1≤Rf.According to Rule7 above, the adjacent ferry UAVs remain connected; thus, messages can transmit to a higher-number ferry at all times.Rule 8.
Distance rule between ferry UAVs and ground. At some timet during the mission, the distance between the highest-number ferry fn and ground G can be less than the ferry’s maximum communication range Rf, that is, ∃t,dtfn,G≤Rf.According to Rule8 above, the highest-number ferry UAV can be connected to the ground during the mission time, so that messages can be transmitted to the ground station.


### 3.1.6. Modeling thePopularity Balance of Searching UAVs

To evaluate the overheads associated with the detection tasks, we consider two aspects—the overhead of the message and overhead of the UAV. In terms of messages, we mainly consider time delay, which is the time from when the messages are perceived to the time it reaches the ground station. In terms of UAVs, the main cost is the battery. One one hand, UAVs need to fly to the required area and to move along a planned track to detect messages. One other hand, UAVs need to collect messages through sensors and need to transmit messages back to the ground station [27]. All these processes cost energy. The cost of flying is hard to avoid and each UAV similarly remains in the search and rescue scene. However, the different locations of the UAVs require them to use up different amounts energy to transmit messages because of the different number of messages passed on. Based on these, for the convenience of discussion, we analyse the unbalanced transmission of messages on different UAVs.Sometimes, if an unsuitable transmission method is chosen to transmit messages, it can cause a “hot spot.” A “hot spot” means that the number of messages passing on a node is much larger than the number of messages passing on other nodes. It spends a lot of energy on message transmission, and it could probably not have enough energy to complete the investigation task, which may bring unpredictable losses, so we should take measures to avoid a “hot spot” as much as possible [28].“Popularity” is proposed to indicate the ratio of the relayed message number to the total message number. Based on geographic routing, messages are transmitted closer to the destination; thus, the number of messages passing through some drones closer to the ground is much larger than number of messages passing through drones far from the ground [29].Therefore, for the entire UAV network, thepopularity of all UAVs is definitely not balanced. So, in this paper, we only discuss the popularity degree of the searching UAVs in the same AL to analyze whether there is a “hot spot.” Based on this, we use the variance FCi to represent the popularity balance of searching UAVs in each AL. For the convenience of description, the relevant symbol representations are shown in Table 1.Table 1
Symbol description.
Symbol
Value
mij
No.j searching UAV in No.i AL
sri
No.i AL
Numsri
The number of searching UAVs insri
Smij
The total number of messages passing on allmij
SNi¯
Average number of allSmij in sri
FCi
Thepopularity balance of searching UAVs in sri
Scollectmij
Total number of messages collected bymij
Sreceivemij
Total number of messages received bymij
e
The number of messages collected per second for each searching UAV (s/sec)
T
Task duration (s)
Pa,b
Probability of message transmission between UAVa and b
mi
The set of searching UAVs insri
ferry
The set of all ferry UAVs
searching
The set of all searching UAVsThe model ofpopularity balance of searching UAVs in sri is given as follows:
(19)FCi=∑j=1NumsriSmij−SNi¯2.The number of messages relayed on each searching UAV is the total number of messages collected and received from others, andSmij can be described as follows:
(20)Smij=Scollectmij+Sreceivemij,where Scollectmij denotes the sum number of messages collected by mij during task duration T:
(21)Scollectmij=e×T.Additionally,others represents the set of drones other than mij, and Po,mij represents the probability of message transmission between o∈others and mij; thus, Sreceivemij can be expressed through the following equation:
(22)Sreceivemij=∑o∈othersSo·Po,mij.Thus, the total number of messages passing on all searching UAVs in each ALSsri can fulfill the following condition:
(23)Ssri=∑j=1NumsriSmij.In addition, based on equation (23), the average messages SNi¯ in equation (19) can be expressed as follows:
(24)SNi¯=SsriNumsri.Obviously, it can be seen from equation (19) that the larger the value of FCi, the more unbalanced the popularity of the drones and the more likely the “hot spot” appears. So in order to avoid the “hot spot,” we hope that the total number of messages passing on different searching UAVs tends to be the same.


### 3.1.7. Modeling the Effect of Ping-Pong

The “Ping-pong effect” means that a message is transmitted from one node to another and then back to the node, that is, the transmission path of the message exists in a loop [30].In order to analyze the proportion of messages in the UAV network that produces the ping-pong effect, we can simply express the number of messages in the loop in the message transmission asNumpp and the total number of received messages as totalmessage, then the ping-pong effect model can be expressed as follows:
(25)PP=Numpptotalmessage.Obviously, it can be seen from the above formula that when the total number of received messages is the same, the more messages that have loops, the larger the proportion of the ping-pong effect.


## 3.1.1. Modeling Case Scenario—Search and Recuse

For a typical scene—search and rescue—the target person is waiting to be rescued in the search area. If the search area is large, artificially invested on-site investigation can cause a large amount of human and financial losses because of the unknown geographical situation. Meanwhile, using a unit of UAVs can greatly reduce the loss [23]. UAVs need to collect the picture message in the search area, and transmit collected messages to the ground station as soon as possible. Then, related people in the ground station can piece together the topography in the area to find the location of the target person, and seek the fastest and safest way to save. This task is completely controlled by the ground station, so the trajectory and allocation of drones are all arranged in advance [24].Since the communication range of UAVs and the ground station are all limited, drones cannot directly establish communication links with the ground station when they are far away from the ground station. Admittedly, flying back to the ground station is a simple, but power-hungry solution that does not scale well. Observing UAVs should use their scarce battery power on mission-driven tasks instead of consuming it by moving closer to the transmission peer (in a testbed of quadcopters, we measured a power consumption of about 200-250 Watts for autonomous flight; the dominating factor is the mechanical part of the copter [25]). Similarly, dense placement of relay UAVs for maintaining connectivity is a possible solution; however, this solution comes at high deployment and operational costs. By introducing ferry nodes to establish connectivity, most of the UAVs may search while the ferries move data physically before transmitting. Note that every UAV in the network may additionally relay messages when possible, including the searching UAVs. It is a plan that takes into account the energy and drone resources.In a multi-UAV system, the specific functions of searching UAVs and ferry UAVs are as follows:(1)
Searching UAV: collecting pictures and also acting as a relay for message transmission
(2)
Ferry UAV: acting only as a relay, to help searching UAVs quickly transmit messages to the groundThis article uses a rectangular search area as an illustration, as shown in Figure1.Figure 1
Example of a search and rescue scenario with UAVs.Here, the Ground is responsible for the planning and analysis of the entire task. Before a task, people in the ground station divide all of the search area into multiple parts and plan the running track of UAVs. During the task, the operation track and running direction of drones are controlled by the control signal. In addition, when messages are returned, the ground station needs to parse them, piece them together to find the location of the target person, and find a suitable search and rescue path.In addition, the relevant areas can be divided into three categories, and the relevant definitions are described as follows:(1)
Search area (abbreviated as SA): the entire area to be investigated, which is shown as ABCD in Figure 1, where height is represented as Hall and width is represented as Wall
(2)
Area layer (abbreviated as AL): multiple subarea layers of the entire search area according to the hierarchy, which is shown as AEID in Figure 1
(3)
Subsearch area (abbreviated as SSA): the area of each drone’s searching part, which is shown as EFGH in Figure 1, where height is expressed as Hm and width is expressed as WmThese three types of areas are related to each other. IfareaSA, areaAL, and areaSSA are used to represent the area of SA, AL, and SSA, the following relationships are satisfied:
(1)
∑areaAL=areaSA, that is, the sum area of all area layers is the area of the search area
(2)
∑areaSSA=areaSA, that is, the sum area of all subsearch areas is the area of the search area
(3)
LetALi be the No. i AL, sumi be the number of searching UAVs in the ALi, SSAj is the area of No. j UAV in ALi, and then ∑j=1sumiareaSSAj=areaALi, that is, the sum area of all subsearch areas in the same area layer is the area of that area layerAdditionally, in order to perform the mission faster and easier, the following requirements should be met when designing the drones’ trajectory [26]:
(1)
The number of UAVs in each area layer tends to be the same
(2)
The size and shape of each SSA tend to be the same
(3)
The trajectory of drones tends to be the same


## 3.1.2. UAV Mobility Model

The motion of the drone can be described as a linear, directional movement model [13], and the trajectory of the drone is determined by the ground station when performing the investigation-search and rescue mission [27]. For the convenience of description, this paper selects straight flight as the trajectory of each drone in a real scene, as shown in Figure 2.Figure 2
UAV mobility model.We describe the subsearch area as a rectangle. The entire area GHIJ is the detection module of each drone. LetHm be the height of the subsearch area in y-axis, Wm be the width of the subsearch area in the x-axis direction, and Rg be the maximum perception of the sensor on the drone. In order to ensure that all UAVs can complete the investigation of the entire area, it must be ensured that the area of each UAV’s investigation is not less than the subsearch area, that is, the detection range covered by the movement track of each UAV is not less than the subsearch area. Therefore, the following constraints must be met between the drone and the reconnaissance module:
(1)x0−a2+y0−b2≤Rg,x0+k0−a−Wm2+y0+k1−b−Hm2≤Rg.When the above constraint (1) is satisfied, the drone can complete the investigation of the entire module. The drone selects a point as the starting position, and we take the point Ax0,y0 as the starting point as an example for the description. It moves along the AB direction through the k1 distance to point Bx0,y0+k1. The direction of motion begins to move along BC to point Cx0+k2/2,y0, reaching point C again to change direction along the CD motion, and to point Dx0+k2,y0+k1 again to change direction to point Ex0+k2,y0. Thus, after changing the direction of motion multiple times, the drone will complete the task of detecting the entire module via A→B→C→D→E→F→A. The position of the drone at each moment is related to its initial position x0,y0 and moving speed v and direction of motion, giving the relationship between the position x,y of the drone and time t (where t0 is just the point when the task is changed in the running direction):
(1)
Movement equation along the AB direction: when a drone moves in the AB direction, the task time is represented ast∈0,k1/v; let t0=0, and the equation of motion at this period is as follows:
(2)x=x0,y=y0+v·t−t0
(2)
Movement equation along the BC direction: when a drone moves in the AB direction, the task time is represented as(3)t∈k1v,k1v+k12+k222
let(4)t0=k1v
the equation of motion at this period is as follows:(5)x=x0+k2·v·t−t02k12+k2/22,y=y0+k1−k1·v·t−t0k12+k2/22
(3)
Movement equation along the CD direction: when a drone moves in the CD direction, the task time is represented as(6)t∈k1v+k12+k222,k1v+2k12+k222
let(7)t0=k1v+k12+k222
the equation of motion at this period is as follows:(8)x=x0+k22+k2·v·t−t02k12+k2/22,y=y0−k1·v·t−t0k12+k2/22
(4)
Movement equation along the DE direction: when a drone moves in the DE direction, the task time is represented as(9)t∈k1v+2k12+k222,2k1v+2k12+k222
let(10)t0=k1v+2k12+k222
the equation of motion at this period is as follows:(11)x=x0+k2,y=y0+k1−v·t−t0
(5)
Movement equation along the EF direction: when a drone moves in the EF direction, the task time is represented as(12)t∈2k1v+2k12+k222,2k1v+3k12+k222,
let(13)t0=2k1v+2k12+k222
the equation of motion at this period is as follows:(14)x=x0+k2−k2·v·t−t02k12+2,y=y0+k1·v·t−t0k12+k2/22
(6)
Movement equation along the FA direction: when a drone moves in the FA direction, the task time is represented as(15)t∈2k1v+3k12+k222,2k1v+4k12+k222
let(16)t0=2k1v+3k12+k222,the equation of motion at this period is as follows:
(17)x=x0+k22−k2·v·t−t02k12+k2/22,y=y0+k1−k1·v·t−t0k12+k2/22
Therefore, after the time2k1/v+4k12+k2/22, the drone completes the task of detection, perception, and collection of messages in the entire SSA. In addition, due to interference from outdoor geography, signals, and other factors, the drone may need to repeat the investigation after a round of investigation to ensure the accuracy and completeness of messages.


## 3.1.3. Division Rules of Area Layers

In this paper, the detection area is a rectangle, and the height and width of the task area are represented byHall and Wall. The task area is divided into multiple area layers according to the hierarchical structure, so that the drone is routed according to the hierarchical increment method, as shown in Figure 3. For each area layer, in order to ensure that the UAVs in the area layer can communicate, the division of the area layer satisfies the following rules.Rule 1.
Leth be the height of AL and let Range be the maximum communication range of a UAV, then h≤Range.Figure 3
The setting of ferry UAVs.f1‐fn are ferry UAVs, and they move back between bs and be with the same speed.Rule1 ensures that UAVs in the upper and lower ALs can transmit messages.Rule 2.
Letw and Hall be the width of the area layer and the height of the detection area and let Numsub be the number of ALs, then Numsub≥Hall/Range.Rule2 can be calculated from Rule 1.Rule 3.
The rule of numbering ALs. ALs are numbered far and near according to the distance from the ground station.Letsri be the No.i AL and let n be the number of ALs. According to Rule 3, shown in Figure 3, the AL farthest from the ground station is numbered as sr1, and the area layer closest to the ground is numbered as srn, so that messages are transmitted in the direction of increasing area layer.


## 3.1.4. Message Transmission Method between Adjacent Area Layers—PB

Multiple searching UAVs are allocated in each AL to detect, sense, and collect messages. Messages are transmitted from the current AL to the next high AL. For each AL namedsri and each searching UAV mij∈sri, we compare the distance of all the neighbors located in the moment, and select the next node mi+1kinsri+1 that fulfills the following condition:
(18)argminjdmij,mi+1ksubjecttodmij,mi+1k≤Range.In the formula,dmij,mi+1k is the geographical distance of node mij to the node mi+1k. dmij,mi+1k<Range ensures that the drone in sri can establish connections with drones in sri+1. PB selects the closest neighbor in sri+1 as the next node to reduce delay. The algorithm PB (Popularity Balance Method for UAVs in the same area layer) is shown as Algorithm 1.Algorithm 1: PB.
1:formijinsri do
2: procedure PBmij,next,Mdata  //Sending Mdata from mij to next
3:  fora∈1,Numsri+1 do
4:   ifdmij,mi+1a≤Range and dmij,mi+1a<dmij,mi+1k then
5:k←a
6:   end if
7:  end for
8:  FORWARDTomi+1k,Mdata  //Sending Mdata to mi+1k
9: end procedure
10:end forAs a result, messages insri transfer along sri,sri+1,sri+2,⋯,srn, and finally to the highest AL, which is named srn.


## 3.1.5. Setting Rules of Ferry UAVs

When there is a certain distance between the detection area and the ground station, the text [22] additionally uses ferry UAVs to move back and forth between the searching UAVs and the ground station to help the message transmission. When a drone uses a geographical routing method for message transmission, a large number of messages will be transmitted back and forth. This article resets the running rules of ferry UAVs, so that the message is still transmitted to the ground station in a hierarchical manner. The setting of the ferry UAV satisfies the following rules.Rule 4.
Numbering rules for ferry UAV. The ferries are numbered far and near according to the distance from the ground station.Letfi be the No.i ferry UAV and let n be the number of ferry UAVs. According to Rule 4 above, the ferry farthest from the ground station is numbered f1, as shown in Figure 3, and ferries are numbered from the search area to Ground via f1,f2,f3,⋯,fn in order.Rule 5.
LetdG,SA be the distance between the ground and SA, let Rg be the maximum sensing range of each searching UAV, and let Rf be the maximum communication range of each ferry, so the number of ferry UAVs Numferry needs to satisfy the formula: Numferry×Rf>dG,SA+Rg.According to Rule5 above, fn can establish a connection with searching UAVs in the highest AL srn during the task time, and messages can be transmitted to the ground via f1,f2,f3,⋯,fn.Rule 6.
The operating rule of ferry UAVs. Each ferry moves back and forth along the width of SA.According to Rule6 above, shown in Figure 3, the ferry moves back and forth between the boundary bs and be. Ferry UAVs expand the communication range of SA, so that messages can reach the ground station via f1,f2,f3,⋯,fn, and finally to Ground.Rule 7.
Distance rule between adjacent ferry UAVs. At any timet during the mission, the distance between adjacent ferries dtfi,fi+1 is always less than its maximum communication range Rf, that is, ∀t,∃i∈1,Numferry−1,dtfi,fi+1≤Rf.According to Rule7 above, the adjacent ferry UAVs remain connected; thus, messages can transmit to a higher-number ferry at all times.Rule 8.
Distance rule between ferry UAVs and ground. At some timet during the mission, the distance between the highest-number ferry fn and ground G can be less than the ferry’s maximum communication range Rf, that is, ∃t,dtfn,G≤Rf.According to Rule8 above, the highest-number ferry UAV can be connected to the ground during the mission time, so that messages can be transmitted to the ground station.


## 3.1.6. Modeling thePopularity Balance of Searching UAVs

To evaluate the overheads associated with the detection tasks, we consider two aspects—the overhead of the message and overhead of the UAV. In terms of messages, we mainly consider time delay, which is the time from when the messages are perceived to the time it reaches the ground station. In terms of UAVs, the main cost is the battery. One one hand, UAVs need to fly to the required area and to move along a planned track to detect messages. One other hand, UAVs need to collect messages through sensors and need to transmit messages back to the ground station [27]. All these processes cost energy. The cost of flying is hard to avoid and each UAV similarly remains in the search and rescue scene. However, the different locations of the UAVs require them to use up different amounts energy to transmit messages because of the different number of messages passed on. Based on these, for the convenience of discussion, we analyse the unbalanced transmission of messages on different UAVs.Sometimes, if an unsuitable transmission method is chosen to transmit messages, it can cause a “hot spot.” A “hot spot” means that the number of messages passing on a node is much larger than the number of messages passing on other nodes. It spends a lot of energy on message transmission, and it could probably not have enough energy to complete the investigation task, which may bring unpredictable losses, so we should take measures to avoid a “hot spot” as much as possible [28].“Popularity” is proposed to indicate the ratio of the relayed message number to the total message number. Based on geographic routing, messages are transmitted closer to the destination; thus, the number of messages passing through some drones closer to the ground is much larger than number of messages passing through drones far from the ground [29].Therefore, for the entire UAV network, thepopularity of all UAVs is definitely not balanced. So, in this paper, we only discuss the popularity degree of the searching UAVs in the same AL to analyze whether there is a “hot spot.” Based on this, we use the variance FCi to represent the popularity balance of searching UAVs in each AL. For the convenience of description, the relevant symbol representations are shown in Table 1.Table 1
Symbol description.
Symbol
Value
mij
No.j searching UAV in No.i AL
sri
No.i AL
Numsri
The number of searching UAVs insri
Smij
The total number of messages passing on allmij
SNi¯
Average number of allSmij in sri
FCi
Thepopularity balance of searching UAVs in sri
Scollectmij
Total number of messages collected bymij
Sreceivemij
Total number of messages received bymij
e
The number of messages collected per second for each searching UAV (s/sec)
T
Task duration (s)
Pa,b
Probability of message transmission between UAVa and b
mi
The set of searching UAVs insri
ferry
The set of all ferry UAVs
searching
The set of all searching UAVsThe model ofpopularity balance of searching UAVs in sri is given as follows:
(19)FCi=∑j=1NumsriSmij−SNi¯2.The number of messages relayed on each searching UAV is the total number of messages collected and received from others, andSmij can be described as follows:
(20)Smij=Scollectmij+Sreceivemij,where Scollectmij denotes the sum number of messages collected by mij during task duration T:
(21)Scollectmij=e×T.Additionally,others represents the set of drones other than mij, and Po,mij represents the probability of message transmission between o∈others and mij; thus, Sreceivemij can be expressed through the following equation:
(22)Sreceivemij=∑o∈othersSo·Po,mij.Thus, the total number of messages passing on all searching UAVs in each ALSsri can fulfill the following condition:
(23)Ssri=∑j=1NumsriSmij.In addition, based on equation (23), the average messages SNi¯ in equation (19) can be expressed as follows:
(24)SNi¯=SsriNumsri.Obviously, it can be seen from equation (19) that the larger the value of FCi, the more unbalanced the popularity of the drones and the more likely the “hot spot” appears. So in order to avoid the “hot spot,” we hope that the total number of messages passing on different searching UAVs tends to be the same.


## 3.1.7. Modeling the Effect of Ping-Pong

The “Ping-pong effect” means that a message is transmitted from one node to another and then back to the node, that is, the transmission path of the message exists in a loop [30].In order to analyze the proportion of messages in the UAV network that produces the ping-pong effect, we can simply express the number of messages in the loop in the message transmission asNumpp and the total number of received messages as totalmessage, then the ping-pong effect model can be expressed as follows:
(25)PP=Numpptotalmessage.Obviously, it can be seen from the above formula that when the total number of received messages is the same, the more messages that have loops, the larger the proportion of the ping-pong effect.


## 3.2. Properties of the Models ofPopularity Balance and Ping-Pong Effect

For the models of thepopularity balance and ping-pong effect in Section 3.1, this section analyzes the characteristics of PB, DTNgeo, DTNload, and DTNclose methods to obtain the following series of properties.Property 1.
For a certain layersr1 in PB, Sm1j=e×t,j∈Numsr1.Proof.
PB causes messages to be transmitted to a higher-numbered AL. The drones in the lowest ALsr1 do not receive messages from other ALs, that is, for mij in sr1,∀o∈others,Po,mij=0, so equation (22) can be converted as follows:
(26)Sreceivem1j=0.
Therefore, equation (20) can be simplified as Sm1j=Scollectm1j=e×t.Property 2.
For a certain layersr1 in PB, SN1¯=e×t.Proof.
According to Property1, when i=0, equation (23) can be simplified as follows:
(27)SN1¯=Numsr1×e×tNumsr1=e×t.Property 3.
LetFC1PB be the situation of popularity balance in sr1 for PB, and it can be calculated that FC1PB=0.Proof.
According to Properties1 and 2, equation (19) can be simplified as follows:
(28)FC1PB=∑j=1Numsr1e×t−e×t2=0.Property 4.
For PB,∀k∈1,Numsri,Smik≈e×t×i.Proof.
(1)
Wheni=1, according to Property 1, we can get the following:
(29)∀k∈1,Numsr1,Sm1k=e×t.
(2)
Analyze the result wheni≠1
According to design requirement (1) of the search and rescue model in Section 3.1, it can be deduced that
(30)∀i,j∈1,n,Numsri=Numsrj.
Since messages are transmitted in the direction of the higher-numbered AL, the message in this area layer is only transmitted to the next higher AL, so formij in sri, others in equation (22) can be expressed as
(31)others=mi−1,where mi−1 represents the set of all searching UAVs in sri.
Thus, equation (22) can be simplified as follows:
(32)Smij=e×t+∑omi−1So·Po,mij.In addition, according to design requirements (2) and (3) of the search and rescue model in Section 3.1, we can analyze that any drone in sri has a similar probability of message transmission with other drones, which can be expressed as
(33)∀x,y∈1,Numsri,∑omi−1So·Po,mix≈∑omi−1So·Po,miy.From equations (32) and (33), it can be deduced that
(34)∀x,y∈1,Numsri,Smix≈Smiy.From (1), i=1, ∀k∈1,Numsr1,Sm1k=e×t; when not considering conditions such as packet loss, it can be deduced that
(35)Sm2k≈e×t+SN1¯=e×t+e×t=2×e×t,Sm3k≈e×t+SN2¯=e×t+2×e×t=3×e×t.Thus, it can be obtained through mathematics that(36)S≈e×t×i,i≠1.The following conclusion can be drawn from the discussion wheni=1 and i≠1:
(37)∀k∈1,Numsri,Smik≈e×t×i.where searching represents the set of all searching UAVs and ferry represents the set of all ferry UAVs.Property 5.
For PB, it can be deduced that∀i∈1,Numsub,SNi¯≈e×t×i.Proof.
According to Property4, equation (23) can be simplified as follows:
(38)SNi¯≈Numsri×e×t×iNumsri=e×t×i.Property 6.
LetFCiPB be the situation of popularity balance in sri,i∈1,Numsub, and it can be deduced that FCiPB≈0.Proof.
According to Property4 and Property 5, equation (19) can be simplified as follows:
(39)FCiPB≈∑j=1Numsrie×t×i−e×t×i2=0.Property 7.
For a certain layersri,i∈1,Numsub in DTNgeo, DTNclose, and DTNload, it can be deduced that
(40)Smij=e×t+∑osearching−mij+ferrySo·Po,mij,where searching is the set of all searching UAVs and ferry is all ferry UAVs.Proof.
Since ferries move back and forth between the ground and searching UAVs, each searching UAV receives the number of messages transmitted from the other searching UAVs and ferry UAVs. Therefore, formij in sri, others in equation (22) can be expressed as
(41)others=searching−mij+ferry,Therefore, equation (22) can be simplified as
(42)Smij=e×t+∑osearching−mij+ferrySo·Po,mij.Property 8.
ForDTNgeo, DTNclose, and DTNload, it can be deduced that Smia≫Smib,a∈HA,b∉HA, where HA represents a “hot area” that means some area nearer the destination than others in each AL.Proof.
ForDTNgeo, DTNclose, and DTNload, any drone selects the neighbor node closest to the ground as the next node. Each time that mik selects the next node, the drone always select some node with a higher probability [31]; it can be expressed as follows:
(43)Pmik,a≫Pmik,ba∈HA,b∉HA.
According to Property7 and formula (43), it can be deduced that
(44)Smia≫Smib.Property 9.
LetFCiDTNgeo,FCiDTNclose, and FCiDTNload be the situation of popularity balance of DTNgeo,DTNclose,DTNload sri,i∈1,Numsub in the three schemes; it can be calculated that FCiDTNgeo≫0,FCiDTNclose≫0, and FCiDTNload≫0.Proof.
According to Property8, and with the characteristics of equation (19)—when values of Smij are not equal to each other and the difference is larger, the value FCi is greater, and it can be deduced that
(45)FCiDTNgeo≫0,FCiDTNclose≫0,FCiDTNload≫0.Property 10.
For PB,Numpp=0.Proof.
All messages are transmitted viasri,sri+1,sri+2,⋯,srn,f1,f2,⋯,fn,G, so there is no loop in the transmission path; thus, Numpp=0.Property 11.
ForDTNgeo, DTNclose, and DTNload, Numpp>0.Proof.
DTNgeo transmits messages to the neighbor node closest to the ground, and because ferries move back and forth between searching UAVs and the ground, the distance between ferries and the ground always changes. If one ferry is closest to the ground station in the neighbor node, messages will be transmitted to that at the time. If one ferry is far away from the ground, the messages will be retransmitted back; there exists a loop in the transmission path, so Numpp>0.


## 3.3. Comparison of PB withDTNgeo, DTNload, and DTNclose in the Popularity Balance and Ping-Pong Effect

Theorem 1.
FCiPB<FCiDTNgeo.Proof.
According to Property6 and Property 9, it can be deduced that
(46)FCiPB<FCiDTNgeo.Theorem 2.
LetPPPB and PPDTNgeo be the ping-pong effect ratio of PB and DTNgeo, respectively, then PPPB<PPDTNgeo.Proof.
According to Property10 and Property 11, with the same value of totalmessage, equation (25) can be deduced as follows:
(47)PPPB<PPDTNgeo.Theorem 3.
FCiPB<FCiDTNclose.Proof.
According to Property6 and Property 9, it can be deduced that
(48)FCiPB<FCiDTNclose.Theorem 4.
LetPPPB and PPDTNclose be the ping-pong effect ratio of PB and DTNclose, respectively, then PPPB<PPDTNclose.Proof.
According to Property10 and Property 11, with the same value of totalmessage, equation (25) can be deduced as follows:
(49)PPPB<PPDTNclose.Theorem 5.
FCiPB<FCiDTNload.Proof.
According to Property6 and Property 9, it can be deduced that
(50)FCiPB<FCiDTNload.Theorem 6.
LetPPPB and PPDTNload be the ping-pong effect ratio of PB and DTNload, respectively, then PPPB<PPDTNload.Proof.
According to Property10 and Property 11, with the same value of totalmessage, equation (25) can be deduced as follows:
(51)PPPB<PPDTNload.


## 3.4. Comparison of PB withDTNgeo, DTNload, and DTNclose in the Complexity of the Algorithm

Theorem 7.
LetOPB,ODTNgeo,ODTNload and ODTNclose be the complexity of PB, DTNgeo, DTNload, and DTNclose, then OPB<ODTNgeo=ODTNclose=ODTNload.Proof.
For PB, since each drone always selects the drone that is closer to itself in the next area layer for transmission of messages, it only needs to calculate distances of drones in the next area layer. Forn drones in the whole system, if the number of drones in each area layer is k, the complexity of PB OPB=On∗k, where k<n.ForDTNgeo, DTNload, and DTNclose, when each drone chooses a message transmission object, it needs to calculate the distances of all the other drones. For n drones in the whole system, the complexity of DTNgeo, DTNload, and DTNclose ODTNgeo=ODTNclose=ODTNload=On2.Therefore,OPB<ODTNgeo=ODTNclose=ODTNload, that is PB has lower complexity than DTNgeo, DTNload, and DTNclose.


## 4. Simulation Design and Results

### 4.1. Simulation Setup

In this paper, PB,DTNgeo, DTNclose, and DTNload are implemented in the ONE simulator [32]. In order to compare the ratio of popularity and ping-pong effect of the three schemes, we construct the simulation scenario with the maximum number of drones in [22].The trajectories of UAVs ofDTNgeo, DTNclose, and DTNload are shown in Figure 4. The scene consists of a basic ground station (G), up to nine searching UAVs (u1-u0), and four ferry UAVs (f1‐f4). f1‐f4 moves back and forth between u1 and u9 and ground station G, and f1‐f4 and f2‐f3 always maintain reverse motion. The detection subarea of each searching UAV is 200m×200m, which defines the service and message collection area of each drone.Figure 4
Simulation scenario ofDTNgeo, DTNclose, and DTNload with a ground station and the trajectories of four ferry UAVs (f1‐f4) and nine searching UAVs (u1-u9),The trajectories of UAVs in PB are shown in Figure5, where u1/u4/u7, u2/u5/u8, and u3/u6/u9 are, respectively, located in sr1,sr2, and sr3. And the distance between the detection area and the ground station dG,SA is 200 m, the sensing radius of the searching UAV Rg is 100 m, and the sensing radius of the ferry UAV Rf is 200 m. According to Rule 2, Rule 3, and Rule 7 of setting the rules of ferry UAVs in Section 3.1, two ferries are planned for message transmission between sr3and G, and we also define the distance between adjacent ferries, that is, the distance is always 100 m. In addition, in order to be consistent with the number of ferry UAVs of the other three methods, we also plan f1 and f2 between the regional layers to ensure link quality of the wireless communication of drones.Figure 5
Simulation scenario of PB with a ground station and the trajectories of four ferry UAVs (f1‐f4) and nine searching UAVs (u1-u9); u1, u4, and u7 are in the same AL named sr1.The specific experimental parameters of this paper are shown in Table2.Table 2
Experimental parameters.
Parameters
Values
Height of each AL
200 m
dG,SA
200 m
Number of Ground
1
Number of UAVs (searching/ferry)
16 (12/4)
Mission time
8 min
Speed of all UAVs
4.5 m/s
Transmission range of all UAVs
200 m
Sensing radius of searching UAVRg
100 m
The size of each message
1.4 kbBy comparing the performance hazard caused by the unbalancedpopularity of drones, we analyse that the more messages generated per second, the more likely the network is to generate congestion, and drones will consume more energy in message transmission. Therefore, the experimental variable in this paper that we selected is the rate of messages generated per second, and we selected different message rates (1/2/3/4/5/10/15) to analyse the results of different algorithms. In addition, in order to analyse the influence of the size of the search area on the results, we also use different areas 800m×200m/800m×600m/800m×800m/800m×1000m, separately using (7/10/13/16) drones.Additionally, we only consider a routing algorithm in this paper. And reliable transmission is completed by relevant protocols in the physical layer and the data link layer, so there is no excessive consideration of mechanisms such as message retransmission and packet acknowledgment. Then, the natural problem of link protocols cannot guarantee that all messages reach the destination node successfully, but the number of messages’ loss rate varies depending on the routing algorithm selected. So, we set the indicator “delivery rate” to evaluate the value of messages that succeed in reaching the destination. Moreover, to evaluate algorithms in different aspects, the following metrics are used to evaluate the performance of these algorithms:(1)
Popularity: that is, the ratio of the relayed message number to the total message number
(2)
Ping-pong effect ratio: that is, the number of messages that have a loop in path transmission out of the total number of messages
(3)
Delivery ratio: that is, the number of messages that have been successfully transmitted to the ground out of the total number of messages
(4)
Delay: that is, the communication delay generated from the node to the destination
(5)
Hop count: that is, the sum of hops a message passes through until it reaches the destination


### 4.2. Discussion of Results

#### 4.2.1. Comparing thePopularity

In order to evaluate the degree ofpopularity in PB, DTNgeo, DTNclose, and DTNload schemes, we select the experimental parameters in [22] for comparison, that is, the rate of messages generated per second is 5. As shown in Figure 6, PB and UAVs in the same area layer (such as u1/u4/u7, u2/u5/u8, and u3/u6/u9) have a similar degree, while the DTNgeo, DTNclose, and DTNload methods all have obvious “hot spots” shown as u6. The reason for the results is that all the methods above are based on geographical routing, making the message closer to the ground station, and PB transmits messages to the area layer closer to the destination node instead of the closer node. Accordingly, messages’ delivery direction is replaced by “point-to-point closer” to “point-to-face closer”, avoiding u6 which is the closest to the ground accepting a large number of relayed messages. In addition, Figure 6 also shows that the degree of f1‐f4 in the PB method is greater than that of the DTNgeo, DTNclose, and DTNload methods, indicating that PB plays a better role of ferry UAVs as a relay.Figure 6
Thepopularity of different methods.In addition, Figure6 not only shows that the degree of u6 is much larger than that of all other searching UAVs but it also indicates that as the number of layers in the area increases, the degree of heat of the drone increases. So we set the different rates of the messages generated per time, and compared the FC3 of each method by calculating the value of formula (19). As shown in Figure 7, the experimental results show that the larger the message rate generated per time, the larger the value of FC3 and FC3DTNgeo>FC3PB,FCiLB<FCiDTNclose, and FCiLB<FCiDTNload with all different rates, which is consistent with Theorems 1, 3, and 5 in Section 3.3.Figure 7
Influence of the rate of the messages generated per time on FC3.


#### 4.2.2. Comparing the Ping-Pong Effect Ratio

In Section4.2.1, we selected one special experimental parameter to analyze the popularity of each UAV of different algorithms. In this section, we experiment on the impact of different rates of messages generated per time and the different numbers of UAVs on a ping-pong effect ratio. The result is shown in Figures 8 and 9. Figure 8 shows the influence of the rate of the messages generated per time on a ping-pong effect ratio, and Figure 9 shows the influence of the number of UAVs on a ping-pong effect ratio.Figure 8
Influence of the rate of the messages generated per time on a ping-pong effect ratio.Figure 9
Influence of the number of UAVs on a ping-pong effect ratio.Both Figures8 and 9 show that the degree of the PB method is always 0, and those of DTNgeo, DTNclose, and DTNload are always greater than 30%. PB can effectively avoid the ping-pong effect, which is consistent with Theorems 2, 4, and 6 in Section 3.3.The reason for the appearance of the ping-pong effect is mainly that theDTNgeo, DTNclose, and DTNload methods enable messages to be point-to-point closer to the destination, and the distance between ferries and the ground is changing during mission time. For example, at a certain time, when a UAV calculates the distance between all neighbours and the ground station, if one ferry is the closest, the drone will transmit messages to the ferry. At some point later, when the ferry UAV calculates the distance between all neighbours and the ground and the distance between the UAV and the ground station is the closest, the message will be returned. PB replaces the relay between searching UAVs and the ground station by replacing the ferry UAVs as the relay between the highest regional layer and the ground station, so that messages are always toward the area layer closer to the ground. Thus, it can avoid back and forth transmission of messages, avoiding poor performance caused by the ping-pong effect.


#### 4.2.3. Comparing the Delivery Ratio

In this section, we examine the impact of the different rates of the messages generated per time and the different numbers of UAVs on the delivery ratio. The results are shown in Figures10 and 11. Figure 10 shows the influence of the rate of the messages generated per time on the delivery ratio, and Figure 11 shows the influence of the number of UAVs on the delivery ratio.Figure 10
Influence of the rate of the messages generated per time on the delivery ratio.Figure 11
Influence of the number of UAVs on the delivery ratio.Both Figures10 and 11 show that PB has a certain improvement in the delivery rate compared with DTNgeo, DTNclose, and DTNload. The reason for the result is that PB balances the popularity of UAVs in the same area layer and avoids the appearance of a “hot spot,” thereby reducing the problem of packet loss due to congestion, so as to improve the delivery ratio.


#### 4.2.4. Comparing the Delay

In this section, we examine the impact of the different rates of the messages generated per time and the different numbers of UAVs on delay. The result is shown in Figures12 and 13. Figure 12 shows the influence of the rate of the messages generated per time on delay, and Figure 13 shows the influence of the number of UAVs on delay.Figure 12
Influence of the rate of the messages generated per time on delay.Figure 13
Influence of the number of UAVs on delay.Both Figures12 and 13 show that PB has a significant improvement on delay compared to DTNgeo, DTNclose, and DTNload, reducing from about 80 s to about 40 s. The reason for the result is that PB avoids the appearance of a “hot spot,” then reduces the waiting time for messages on the “hot spot.” On the other hand, replanning the running rules of ferry UAVs avoids the ping-pong effect, so as to reduce unnecessary back-and-forth transmission time of messages, thereby reducing delay.


#### 4.2.5. Comparing the Hop Count

In this section, we examined the impact of the different rates of the messages generated per time and the different numbers of UAVs on hop count. The result is shown in Figures14 and 15. Figure 14 shows the influence of the rate of the messages generated per time on hop count, and Figure 15 shows the influence of the number of UAVs on hop count.Figure 14
Influence of the rate of the messages generated per time on hop count.Figure 15
Influence of the number of UAVs on hop count.Both Figures14 and 15 show that PB has a slight decrease in hop count compared to DTNgeo, DTNclose, and DTNload. Although the hop count in the DTNclose has a decrease with the increase in the number of messages generated per second, it is still slightly higher than PB. The reason for the result is that PB replans the trajectory of ferry UAVs, so as to avoid the effect of the ping-pong effect, thereby reducing the unnecessary hops caused by the ping-pong effect.


## 4.1. Simulation Setup

In this paper, PB,DTNgeo, DTNclose, and DTNload are implemented in the ONE simulator [32]. In order to compare the ratio of popularity and ping-pong effect of the three schemes, we construct the simulation scenario with the maximum number of drones in [22].The trajectories of UAVs ofDTNgeo, DTNclose, and DTNload are shown in Figure 4. The scene consists of a basic ground station (G), up to nine searching UAVs (u1-u0), and four ferry UAVs (f1‐f4). f1‐f4 moves back and forth between u1 and u9 and ground station G, and f1‐f4 and f2‐f3 always maintain reverse motion. The detection subarea of each searching UAV is 200m×200m, which defines the service and message collection area of each drone.Figure 4
Simulation scenario ofDTNgeo, DTNclose, and DTNload with a ground station and the trajectories of four ferry UAVs (f1‐f4) and nine searching UAVs (u1-u9),The trajectories of UAVs in PB are shown in Figure5, where u1/u4/u7, u2/u5/u8, and u3/u6/u9 are, respectively, located in sr1,sr2, and sr3. And the distance between the detection area and the ground station dG,SA is 200 m, the sensing radius of the searching UAV Rg is 100 m, and the sensing radius of the ferry UAV Rf is 200 m. According to Rule 2, Rule 3, and Rule 7 of setting the rules of ferry UAVs in Section 3.1, two ferries are planned for message transmission between sr3and G, and we also define the distance between adjacent ferries, that is, the distance is always 100 m. In addition, in order to be consistent with the number of ferry UAVs of the other three methods, we also plan f1 and f2 between the regional layers to ensure link quality of the wireless communication of drones.Figure 5
Simulation scenario of PB with a ground station and the trajectories of four ferry UAVs (f1‐f4) and nine searching UAVs (u1-u9); u1, u4, and u7 are in the same AL named sr1.The specific experimental parameters of this paper are shown in Table2.Table 2
Experimental parameters.
Parameters
Values
Height of each AL
200 m
dG,SA
200 m
Number of Ground
1
Number of UAVs (searching/ferry)
16 (12/4)
Mission time
8 min
Speed of all UAVs
4.5 m/s
Transmission range of all UAVs
200 m
Sensing radius of searching UAVRg
100 m
The size of each message
1.4 kbBy comparing the performance hazard caused by the unbalancedpopularity of drones, we analyse that the more messages generated per second, the more likely the network is to generate congestion, and drones will consume more energy in message transmission. Therefore, the experimental variable in this paper that we selected is the rate of messages generated per second, and we selected different message rates (1/2/3/4/5/10/15) to analyse the results of different algorithms. In addition, in order to analyse the influence of the size of the search area on the results, we also use different areas 800m×200m/800m×600m/800m×800m/800m×1000m, separately using (7/10/13/16) drones.Additionally, we only consider a routing algorithm in this paper. And reliable transmission is completed by relevant protocols in the physical layer and the data link layer, so there is no excessive consideration of mechanisms such as message retransmission and packet acknowledgment. Then, the natural problem of link protocols cannot guarantee that all messages reach the destination node successfully, but the number of messages’ loss rate varies depending on the routing algorithm selected. So, we set the indicator “delivery rate” to evaluate the value of messages that succeed in reaching the destination. Moreover, to evaluate algorithms in different aspects, the following metrics are used to evaluate the performance of these algorithms:(1)
Popularity: that is, the ratio of the relayed message number to the total message number
(2)
Ping-pong effect ratio: that is, the number of messages that have a loop in path transmission out of the total number of messages
(3)
Delivery ratio: that is, the number of messages that have been successfully transmitted to the ground out of the total number of messages
(4)
Delay: that is, the communication delay generated from the node to the destination
(5)
Hop count: that is, the sum of hops a message passes through until it reaches the destination


## 4.2. Discussion of Results

### 4.2.1. Comparing thePopularity

In order to evaluate the degree ofpopularity in PB, DTNgeo, DTNclose, and DTNload schemes, we select the experimental parameters in [22] for comparison, that is, the rate of messages generated per second is 5. As shown in Figure 6, PB and UAVs in the same area layer (such as u1/u4/u7, u2/u5/u8, and u3/u6/u9) have a similar degree, while the DTNgeo, DTNclose, and DTNload methods all have obvious “hot spots” shown as u6. The reason for the results is that all the methods above are based on geographical routing, making the message closer to the ground station, and PB transmits messages to the area layer closer to the destination node instead of the closer node. Accordingly, messages’ delivery direction is replaced by “point-to-point closer” to “point-to-face closer”, avoiding u6 which is the closest to the ground accepting a large number of relayed messages. In addition, Figure 6 also shows that the degree of f1‐f4 in the PB method is greater than that of the DTNgeo, DTNclose, and DTNload methods, indicating that PB plays a better role of ferry UAVs as a relay.Figure 6
Thepopularity of different methods.In addition, Figure6 not only shows that the degree of u6 is much larger than that of all other searching UAVs but it also indicates that as the number of layers in the area increases, the degree of heat of the drone increases. So we set the different rates of the messages generated per time, and compared the FC3 of each method by calculating the value of formula (19). As shown in Figure 7, the experimental results show that the larger the message rate generated per time, the larger the value of FC3 and FC3DTNgeo>FC3PB,FCiLB<FCiDTNclose, and FCiLB<FCiDTNload with all different rates, which is consistent with Theorems 1, 3, and 5 in Section 3.3.Figure 7
Influence of the rate of the messages generated per time on FC3.


### 4.2.2. Comparing the Ping-Pong Effect Ratio

In Section4.2.1, we selected one special experimental parameter to analyze the popularity of each UAV of different algorithms. In this section, we experiment on the impact of different rates of messages generated per time and the different numbers of UAVs on a ping-pong effect ratio. The result is shown in Figures 8 and 9. Figure 8 shows the influence of the rate of the messages generated per time on a ping-pong effect ratio, and Figure 9 shows the influence of the number of UAVs on a ping-pong effect ratio.Figure 8
Influence of the rate of the messages generated per time on a ping-pong effect ratio.Figure 9
Influence of the number of UAVs on a ping-pong effect ratio.Both Figures8 and 9 show that the degree of the PB method is always 0, and those of DTNgeo, DTNclose, and DTNload are always greater than 30%. PB can effectively avoid the ping-pong effect, which is consistent with Theorems 2, 4, and 6 in Section 3.3.The reason for the appearance of the ping-pong effect is mainly that theDTNgeo, DTNclose, and DTNload methods enable messages to be point-to-point closer to the destination, and the distance between ferries and the ground is changing during mission time. For example, at a certain time, when a UAV calculates the distance between all neighbours and the ground station, if one ferry is the closest, the drone will transmit messages to the ferry. At some point later, when the ferry UAV calculates the distance between all neighbours and the ground and the distance between the UAV and the ground station is the closest, the message will be returned. PB replaces the relay between searching UAVs and the ground station by replacing the ferry UAVs as the relay between the highest regional layer and the ground station, so that messages are always toward the area layer closer to the ground. Thus, it can avoid back and forth transmission of messages, avoiding poor performance caused by the ping-pong effect.


### 4.2.3. Comparing the Delivery Ratio

In this section, we examine the impact of the different rates of the messages generated per time and the different numbers of UAVs on the delivery ratio. The results are shown in Figures10 and 11. Figure 10 shows the influence of the rate of the messages generated per time on the delivery ratio, and Figure 11 shows the influence of the number of UAVs on the delivery ratio.Figure 10
Influence of the rate of the messages generated per time on the delivery ratio.Figure 11
Influence of the number of UAVs on the delivery ratio.Both Figures10 and 11 show that PB has a certain improvement in the delivery rate compared with DTNgeo, DTNclose, and DTNload. The reason for the result is that PB balances the popularity of UAVs in the same area layer and avoids the appearance of a “hot spot,” thereby reducing the problem of packet loss due to congestion, so as to improve the delivery ratio.


### 4.2.4. Comparing the Delay

In this section, we examine the impact of the different rates of the messages generated per time and the different numbers of UAVs on delay. The result is shown in Figures12 and 13. Figure 12 shows the influence of the rate of the messages generated per time on delay, and Figure 13 shows the influence of the number of UAVs on delay.Figure 12
Influence of the rate of the messages generated per time on delay.Figure 13
Influence of the number of UAVs on delay.Both Figures12 and 13 show that PB has a significant improvement on delay compared to DTNgeo, DTNclose, and DTNload, reducing from about 80 s to about 40 s. The reason for the result is that PB avoids the appearance of a “hot spot,” then reduces the waiting time for messages on the “hot spot.” On the other hand, replanning the running rules of ferry UAVs avoids the ping-pong effect, so as to reduce unnecessary back-and-forth transmission time of messages, thereby reducing delay.


### 4.2.5. Comparing the Hop Count

In this section, we examined the impact of the different rates of the messages generated per time and the different numbers of UAVs on hop count. The result is shown in Figures14 and 15. Figure 14 shows the influence of the rate of the messages generated per time on hop count, and Figure 15 shows the influence of the number of UAVs on hop count.Figure 14
Influence of the rate of the messages generated per time on hop count.Figure 15
Influence of the number of UAVs on hop count.Both Figures14 and 15 show that PB has a slight decrease in hop count compared to DTNgeo, DTNclose, and DTNload. Although the hop count in the DTNclose has a decrease with the increase in the number of messages generated per second, it is still slightly higher than PB. The reason for the result is that PB replans the trajectory of ferry UAVs, so as to avoid the effect of the ping-pong effect, thereby reducing the unnecessary hops caused by the ping-pong effect.


## 4.2.1. Comparing thePopularity

In order to evaluate the degree ofpopularity in PB, DTNgeo, DTNclose, and DTNload schemes, we select the experimental parameters in [22] for comparison, that is, the rate of messages generated per second is 5. As shown in Figure 6, PB and UAVs in the same area layer (such as u1/u4/u7, u2/u5/u8, and u3/u6/u9) have a similar degree, while the DTNgeo, DTNclose, and DTNload methods all have obvious “hot spots” shown as u6. The reason for the results is that all the methods above are based on geographical routing, making the message closer to the ground station, and PB transmits messages to the area layer closer to the destination node instead of the closer node. Accordingly, messages’ delivery direction is replaced by “point-to-point closer” to “point-to-face closer”, avoiding u6 which is the closest to the ground accepting a large number of relayed messages. In addition, Figure 6 also shows that the degree of f1‐f4 in the PB method is greater than that of the DTNgeo, DTNclose, and DTNload methods, indicating that PB plays a better role of ferry UAVs as a relay.Figure 6
Thepopularity of different methods.In addition, Figure6 not only shows that the degree of u6 is much larger than that of all other searching UAVs but it also indicates that as the number of layers in the area increases, the degree of heat of the drone increases. So we set the different rates of the messages generated per time, and compared the FC3 of each method by calculating the value of formula (19). As shown in Figure 7, the experimental results show that the larger the message rate generated per time, the larger the value of FC3 and FC3DTNgeo>FC3PB,FCiLB<FCiDTNclose, and FCiLB<FCiDTNload with all different rates, which is consistent with Theorems 1, 3, and 5 in Section 3.3.Figure 7
Influence of the rate of the messages generated per time on FC3.


## 4.2.2. Comparing the Ping-Pong Effect Ratio

In Section4.2.1, we selected one special experimental parameter to analyze the popularity of each UAV of different algorithms. In this section, we experiment on the impact of different rates of messages generated per time and the different numbers of UAVs on a ping-pong effect ratio. The result is shown in Figures 8 and 9. Figure 8 shows the influence of the rate of the messages generated per time on a ping-pong effect ratio, and Figure 9 shows the influence of the number of UAVs on a ping-pong effect ratio.Figure 8
Influence of the rate of the messages generated per time on a ping-pong effect ratio.Figure 9
Influence of the number of UAVs on a ping-pong effect ratio.Both Figures8 and 9 show that the degree of the PB method is always 0, and those of DTNgeo, DTNclose, and DTNload are always greater than 30%. PB can effectively avoid the ping-pong effect, which is consistent with Theorems 2, 4, and 6 in Section 3.3.The reason for the appearance of the ping-pong effect is mainly that theDTNgeo, DTNclose, and DTNload methods enable messages to be point-to-point closer to the destination, and the distance between ferries and the ground is changing during mission time. For example, at a certain time, when a UAV calculates the distance between all neighbours and the ground station, if one ferry is the closest, the drone will transmit messages to the ferry. At some point later, when the ferry UAV calculates the distance between all neighbours and the ground and the distance between the UAV and the ground station is the closest, the message will be returned. PB replaces the relay between searching UAVs and the ground station by replacing the ferry UAVs as the relay between the highest regional layer and the ground station, so that messages are always toward the area layer closer to the ground. Thus, it can avoid back and forth transmission of messages, avoiding poor performance caused by the ping-pong effect.


## 4.2.3. Comparing the Delivery Ratio

In this section, we examine the impact of the different rates of the messages generated per time and the different numbers of UAVs on the delivery ratio. The results are shown in Figures10 and 11. Figure 10 shows the influence of the rate of the messages generated per time on the delivery ratio, and Figure 11 shows the influence of the number of UAVs on the delivery ratio.Figure 10
Influence of the rate of the messages generated per time on the delivery ratio.Figure 11
Influence of the number of UAVs on the delivery ratio.Both Figures10 and 11 show that PB has a certain improvement in the delivery rate compared with DTNgeo, DTNclose, and DTNload. The reason for the result is that PB balances the popularity of UAVs in the same area layer and avoids the appearance of a “hot spot,” thereby reducing the problem of packet loss due to congestion, so as to improve the delivery ratio.


## 4.2.4. Comparing the Delay

In this section, we examine the impact of the different rates of the messages generated per time and the different numbers of UAVs on delay. The result is shown in Figures12 and 13. Figure 12 shows the influence of the rate of the messages generated per time on delay, and Figure 13 shows the influence of the number of UAVs on delay.Figure 12
Influence of the rate of the messages generated per time on delay.Figure 13
Influence of the number of UAVs on delay.Both Figures12 and 13 show that PB has a significant improvement on delay compared to DTNgeo, DTNclose, and DTNload, reducing from about 80 s to about 40 s. The reason for the result is that PB avoids the appearance of a “hot spot,” then reduces the waiting time for messages on the “hot spot.” On the other hand, replanning the running rules of ferry UAVs avoids the ping-pong effect, so as to reduce unnecessary back-and-forth transmission time of messages, thereby reducing delay.


## 4.2.5. Comparing the Hop Count

In this section, we examined the impact of the different rates of the messages generated per time and the different numbers of UAVs on hop count. The result is shown in Figures14 and 15. Figure 14 shows the influence of the rate of the messages generated per time on hop count, and Figure 15 shows the influence of the number of UAVs on hop count.Figure 14
Influence of the rate of the messages generated per time on hop count.Figure 15
Influence of the number of UAVs on hop count.Both Figures14 and 15 show that PB has a slight decrease in hop count compared to DTNgeo, DTNclose, and DTNload. Although the hop count in the DTNclose has a decrease with the increase in the number of messages generated per second, it is still slightly higher than PB. The reason for the result is that PB replans the trajectory of ferry UAVs, so as to avoid the effect of the ping-pong effect, thereby reducing the unnecessary hops caused by the ping-pong effect.


## 5. Conclusion

PB, a message transmission method based on area layer division in UAV networks, is proposed in the paper.It divides the search area into multiple area layers and then transmits messages to the area layer closer to the ground based on the idea of geographical routing. The method transmits messages to the closer area layer instead of the closer node to the destination; thus, message delivery direction is replaced by “point-to-point closer” to “point-to-face closer.” In addition, by resetting the operating rules, ferry UAVs are used as relays between the search area and the ground to replace the original motion between the searching UAVs and the ground, which effectively avoids a ping-pong effect, reducing the average number of hop counts and delay caused by unnecessary round-trip transmission. In the scenario simulation, delay is reduced from about 80 s to about 40 s. During the same mission time, the number of messages successfully transmitted to the ground is also increased. Because of less congestion, delivery ratio is also increased from over 80% to over 90%. Theoretical and experimental results both show that PB is superior toDTNgeo, DTNclose, and DTNload in terms of popularity, ping-pong effect ratio, delivery ratio, delay, and hop count.



---

*Source: 2592189-2019-11-11.xml*