CN112351438B - Unmanned aerial vehicle base station deployment method based on undirected graph - Google Patents
Unmanned aerial vehicle base station deployment method based on undirected graph Download PDFInfo
- Publication number
- CN112351438B CN112351438B CN202011219855.5A CN202011219855A CN112351438B CN 112351438 B CN112351438 B CN 112351438B CN 202011219855 A CN202011219855 A CN 202011219855A CN 112351438 B CN112351438 B CN 112351438B
- Authority
- CN
- China
- Prior art keywords
- aerial vehicle
- unmanned aerial
- base station
- undirected graph
- vertex
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W16/00—Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
- H04W16/18—Network planning tools
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04B—TRANSMISSION
- H04B7/00—Radio transmission systems, i.e. using radiation field
- H04B7/14—Relay systems
- H04B7/15—Active relay systems
- H04B7/185—Space-based or airborne stations; Stations for satellite systems
- H04B7/18502—Airborne stations
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04B—TRANSMISSION
- H04B7/00—Radio transmission systems, i.e. using radiation field
- H04B7/14—Relay systems
- H04B7/15—Active relay systems
- H04B7/185—Space-based or airborne stations; Stations for satellite systems
- H04B7/18502—Airborne stations
- H04B7/18504—Aircraft used as relay or high altitude atmospheric platform
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Astronomy & Astrophysics (AREA)
- Aviation & Aerospace Engineering (AREA)
- General Physics & Mathematics (AREA)
- Mobile Radio Communication Systems (AREA)
Abstract
The invention provides an undirected graph-based unmanned aerial vehicle base station deployment method, which mainly solves the problem of optimal deployment of an unmanned aerial vehicle base station. The realization method comprises the following steps: 1) And drawing an undirected graph according to the distance information between the ground terminals. 2) And preprocessing the nodes with the degrees of 0 and 1 in the undirected graph based on the undirected graph. 3) And dividing the undirected graph into a plurality of first-order or second-order complete subgraphs, and deploying the unmanned aerial vehicle base station on the basis of the undirected graph. 4) And continuously adjusting the coverage range of the base station according to the degree information of the vertex and the adjacent information of the vertex in the undirected graph, combining the base stations and reducing the number of the base stations. 5) Repeating the processes 3) and 4) for a plurality of times to optimize the deployment scenario until a termination condition is reached. The invention can deploy the unmanned aerial vehicle base station with high efficiency and low cost, and can be applied to area monitoring, temporary communication and the like.
Description
Technical Field
The patent relates to the field of wireless communication technology, in particular to an optimization method for unmanned aerial vehicle base station deployment.
Background
As a new communication method, the unmanned aerial vehicle wireless communication has been rapidly developed in recent years due to its high mobility and high possibility of LOS channel. Currently, unmanned aerial vehicle wireless communication has wide application in applications such as auxiliary communication, relay communication, information collection and the like. For example, the drone can serve as a flying mobile base station to provide temporary communication service for the ground terminal. The unmanned aerial vehicle base station has the characteristics of fast deployment and low cost, and gradually becomes a research hotspot in recent years. Unmanned aerial vehicle base station has been widely used at present, post-disaster temporary communication network, fire detection, traffic patrol and the like.
Limited by the limited battery energy of the unmanned aerial vehicle, communication power and other reasons, how to deploy the unmanned aerial vehicle base station quickly and with low cost is a technical challenge for the existing unmanned aerial vehicle base station to be put into use. Currently, there are some studies on deployment methods of drone base stations. The document 'Deployment of UAV-hosted access points accessing to specific users in two-tier cellular networks' adopts a K-means method to deploy the base station of the UAV, but the method has low efficiency and the algorithm is greatly influenced by the number of clusters. The document "Placement Optimization of UAV-Mounted Mobile Base Stations" adopts an algorithm of spiral layout and convex hull boundary solving to arrange the unmanned aerial vehicle Base Stations, but the solution space of the method is limited, and the optimal solution is difficult to obtain. The literature "Placement optimization method for multi-UAV relay communication" adopts a genetic algorithm to perform combined coding on an unmanned aerial vehicle and a ground terminal to deploy an unmanned aerial vehicle base station, but the method needs to continuously try the number of unmanned aerial vehicle base stations, and when the number of unmanned aerial vehicle base stations is large, the algorithm efficiency is low.
Disclosure of Invention
The invention aims to overcome the defects of the technology and provides an unmanned aerial vehicle base station deployment method based on an undirected graph.
An unmanned aerial vehicle base station deployment method based on undirected graphs comprises the following steps:
s1: establishing a system model, and constructing an undirected graph according to the distance information of the ground terminal;
s2: preprocessing the vertexes in the undirected graph based on the adjacent information of the vertexes in the undirected graph;
s3: a plurality of unmanned aerial vehicle base stations are randomly constructed, and the unmanned aerial vehicle base stations are not available, so that the number of the unmanned aerial vehicle base stations is reduced;
s4: and circularly executing S3 until the maximum circulation times are reached or the number of the base stations of the optimal deployment scheme is unchanged.
The specific method of S1 is as follows:
establishing a coordinate system by taking the initial position of the unmanned aerial vehicle as an origin (0,0), wherein the coordinate of the unmanned aerial vehicle at any moment is u (t) = (x) u (t)，y u (t)), wherein x u (t) is the abscissa of the unmanned plane at any time t, y u (t) is the ordinate of the unmanned aerial vehicle at any time t, and for all N ground terminals {1,2,3,.., N }, the position of any ground terminal i on the coordinate system is q i ＝(x i ，y i ) Wherein x is i ，y i Respectively are the abscissa and ordinate information of the ground terminal i on the coordinate system.
The Distance between any ground terminals i, j is Distance (i, j),
wherein x is i ，y i Information of abscissa and ordinate, x, of the ground terminal i j ，y j And the information of the abscissa and the ordinate of the ground terminal j is obtained.
Assuming that the unmanned aerial vehicle flies at a fixed height H, the channel between the unmanned aerial vehicle and the ground terminal is an LOS channel, and the farthest allowable communication distance between the unmanned aerial vehicle and each ground terminal is R, according to the formula:
R 2 ＝r 2 +H 2
and solving the farthest horizontal communication distance r between the unmanned aerial vehicle and the ground terminal, and determining the horizontal coverage range of the base station.
The formulation of the problem of minimizing the number of drone base stations K is described as (P):
according to the distance information between the ground terminals, an undirected graph G is constructed, which specifically comprises the following steps: if the distance between any ground terminal i and terminal j is less than or equal to 2r, two corresponding vertexes of the undirected graph are adjacent, and W (i, j) =1 is recorded; if the distance between them is greater than 2r, then its corresponding two vertices in the undirected graph are not adjacent, let W (i, j) =0, which can be expressed as:
the degree information of each vertex in the undirected graph is obtained as follows: if there are k vertices adjacent to any vertex i in the undirected graph G, the connectivity of the vertex is k, and is denoted as Degree (i) = k.
Based on the created undirected graph, the following inferences can be determined:
the distance between any two ground terminals in the range covered by the unmanned aerial vehicle base station is not more than 2r, and the distance between the ground terminals corresponding to any two nonadjacent vertexes in the undirected graph G is not more than 2r, so that the conclusion can be drawn that the ground terminals corresponding to any two nonadjacent vertexes in the undirected graph can not be covered by one unmanned aerial vehicle base station;
further, for any subgraph in the undirected graph, if the subgraph is not a complete subgraph, non-adjacent points are inevitably present therein, and terminals with a distance greater than 2r are also inevitably present in the ground terminals corresponding thereto, so that the ground terminals corresponding to the subgraph cannot be covered by one unmanned aerial vehicle base station;
based on the above conclusion, it is necessary that any plurality of ground terminals can be covered by one drone base station, and a subgraph formed by vertices in an undirected graph corresponding to the ground terminals is a complete subgraph.
The specific method of S2 is as follows:
circularly executing the steps (1) to (2), wherein the circulation end condition is as follows: the undirected graph G is a null graph or the number of all points in the undirected graph is more than or equal to 2.
(1) Finding isolated points with the middle Degree of 0 in the undirected graph G, namely Degree (i) =0, deploying the unmanned aerial vehicle base station by taking the isolated points as the center, and deleting the points from the undirected graph G;
(2) Finding whether suspended vertexes with the degree of 1 exist in the undirected graph G, obviously, the suspended vertexes, and vertexes uniquely connected with the suspended vertexes, form a tree structure, and for each tree structure, the minimum number of the suspended vertexes which are divided into complete subgraphs can be determined as h-1, wherein h is the number of nodes of each tree structure, and for each tree structure in the undirected graph G, the following operations are performed: father node and arbitrary leaf node in the tree structure set up an unmanned aerial vehicle basic station, and every leaf node that remains sets up unmanned aerial vehicle basic station separately respectively.
The specific method of S3 is as follows:
if G is an empty map, directly executing the step S4; if G is not an empty graph, then execution continues downward.
At present, all vertex degrees in the undirected graph G are greater than or equal to 2, and if any two adjacent vertices in the undirected graph form a complete subgraph, it is obvious that the ground terminal corresponding to the point in the second-order complete subgraph can be covered by one unmanned aerial vehicle base station.
And (3) randomly forming a plurality of second-order or first-order complete subgraphs by pairwise adjacent points in the undirected graph G, wherein the complete subgraphs are required to be mutually non-overlapped, so that a preliminary scheme for deploying the unmanned aerial vehicle base station is obtained.
And traversing all the vertexes in the undirected graph G from small to large according to the degrees of the vertexes in the undirected graph G, and executing the processes a) to b).
(a) Hypothesis selectedThe vertex is a, and the unmanned aerial vehicle base station covering the a is defined as MBS a If the unmanned aerial vehicle base station where the a is located is not processed, continuing to execute the following steps; otherwise, skipping vertex a;
(b) Define the set of vertices at the SAME drone base station as a as { SAME a Defining a set of vertices adjacent to a as { Connection } a -traversing the set of connections from small to large in degree order a }-{SAME a All vertices in the tree, the following processes (b 1) - (b 3) are performed until the Connection is traversed a }-{SAME a All vertices in (1);
(b1) Let the selected point be z, if z is equal to { SAME a Continuing if all the top points in the graph are adjacent, otherwise skipping a point z;
(b2) If the z belongs to the unmanned aerial vehicle base station MBS at the moment z The number of medium vertex is less than or equal to MBS a If yes, continuing, otherwise skipping over the point z;
(b3) If z is equal to a, and { SAME a The radius of the smallest enclosing circle formed by all the vertexes in the Z is not more than r, then z is selected from the unmanned aerial vehicle base station MBS covering z z Deleting the point A and adding the point Z to the MBS (base station of unmanned aerial vehicle) to which the point A belongs at present a Otherwise, skip point z.
S4, the specific implementation method comprises the following steps:
step S3 is executed in a loop until the following termination condition is reached: 1. the maximum cycle number is reached; 2. the optimal deployment scenario for m consecutive times is unchanged (where the value of m defaults to 5, which may vary as the case may be).
Through the process, the deployment scheme of the unmanned aerial vehicle base station is obtained.
Compared with the prior art, the invention has the remarkable advantages that: the invention utilizes the knowledge of the complete subgraph in the undirected graph to solve the deployment problem of the base station of the unmanned aerial vehicle for the first time, can preliminarily screen out the ground terminal which can not be covered by one base station of the unmanned aerial vehicle by judging whether the vertex forms the complete subgraph, improves the arrangement efficiency of the base station, is simple and easy to realize, and does not need to consume a large amount of resources of a computer.
Drawings
FIG. 1 is a flow chart of the algorithm as a whole in the present invention.
Fig. 2 shows the distribution of the ground terminals on a plane.
Fig. 3 is an undirected graph drawn based on location information of a ground terminal.
Fig. 4 is a schematic diagram of processing isolated points in an undirected graph.
FIG. 5 is a schematic illustration of the processing of suspended vertices in an undirected graph.
Fig. 6 is a schematic diagram of a base station deployment after preprocessing.
Fig. 7 is a schematic diagram of a preliminary arrangement of drone base stations.
Fig. 8 is a schematic diagram of the final placement of the drone base station.
Detailed Description
The present invention will be further described in detail with reference to the accompanying drawings, and the overall flow chart of the present invention is shown in fig. 1.
S1: and constructing a system model and establishing an undirected graph.
As shown in fig. 2, the ground terminals are distributed on a plane, assuming that the ground terminals are all at the same height and the terrain is flat, and at any moment, the coordinate of the unmanned aerial vehicle is q U (t)＝(x U (t)，y U (t)), wherein x u (t) is the abscissa of the unmanned plane at any time t, y u (t) is the vertical coordinate of the unmanned aerial vehicle at any moment t, and the unmanned aerial vehicle is positioned at the origin of the coordinate system at the initial moment. The number of ground terminals is N, and the position information of any ground terminal i is q i ＝(x i ，y i ) Wherein x is i ，y i Respectively, the abscissa and ordinate information of the ground terminal i.
The Distance between any ground terminals i, j is denoted Distance (i, j), where,
wherein x is i ，y i Information of abscissa and ordinate, x, of the ground terminal i j ，y j Is the transverse of the ground terminal jCoordinates and ordinate information.
Assuming that the unmanned aerial vehicle is flying horizontally at a constant altitude H, according to the formula
R 2 ＝r 2 +H 2
And calculating the farthest horizontal distance R between the unmanned aerial vehicle and the ground terminal, wherein R is the farthest allowable communication distance between the unmanned aerial vehicle and the ground terminal.
And constructing an undirected graph according to the distance information between the ground terminals, wherein the undirected graph is constructed in the following mode: if the distance between any two ground terminals is greater than 2r, the two ground terminals are not considered to be adjacent, and if the distance between the two ground terminals is less than or equal to 2r, the two ground terminals are considered to be adjacent, and an undirected graph is drawn as shown in fig. 3.
And determining the degrees of all the vertexes in the undirected graph G, and if k vertexes adjacent to any point i are provided, determining the Degree of the point as k, and keeping Degree (i) = k.
S2: and (4) preprocessing vertexes with degrees of 0 and 1 in the undirected graph based on the system model.
Circularly executing the steps (1) to (2), wherein the circulation end condition is as follows: the undirected graph G is a null graph or the number of all points in the undirected graph is more than or equal to 2.
(1) As shown in fig. 4, an isolated point of undirected graph G with a middle value of 0, i.e., the point Degree (i) =0, is found. Deploying the unmanned aerial vehicle base station by taking the isolated points as the center, and deleting the points from the undirected graph G;
(2) And searching whether the suspension vertex with the degree of 1 exists in the undirected graph G. For each tree structure consisting of each suspended vertex in G and its uniquely connected vertices, the following operations are performed:
(2a) And deploying an unmanned aerial vehicle base station for a father node and any leaf node in the tree structure, wherein the center of the base station is the center of mass of the father node and any leaf node, and each remaining leaf node is respectively and independently provided with the unmanned aerial vehicle base station, and the center of the unmanned aerial vehicle base station is the center of the leaf node.
Step S2 is explained below with reference to an example.
As shown in fig. 5, the leaf nodes are a, b, c, and d, the father node is e, the leaf node a and the father node e are covered by an unmanned aerial vehicle base station, and the center of the base station is the centroid of the nodes a and e. And for other nodes b, c and d, respectively setting unmanned aerial vehicle base stations in the centers of the nodes.
The result of the deployment of the drone base station is shown in fig. 6 after step S2.
S3: based on undirected graph G, a plurality of unmanned aerial vehicle base stations are randomly deployed, the coverage area of each base station is continuously adjusted, the base stations are combined, the number of the base stations is reduced, and the specific execution process is as follows:
if the undirected graph G is an empty graph at the moment, directly executing S4; if G is not an empty graph, then execution continues down.
In the undirected graph G, adjacent vertices are arbitrarily grouped into a plurality of second-order or first-order complete subgraphs, and the complete subgraphs are required to be mutually non-overlapped, so as to obtain a preliminary scheme for deploying the base station of the unmanned aerial vehicle, as shown in fig. 7.
And (c) traversing all the vertexes in the undirected graph G from small to large according to the vertex degree information in the undirected graph G, and executing the processes (a) and (b).
(a) Assuming that the selected vertex is a, defining the unmanned aerial vehicle base station covering a as MBS a . If the unmanned aerial vehicle base station where the a is located is not processed, continuing to execute the following steps; otherwise, vertex a is skipped.
(b) Define the set of vertices at the SAME drone base station as a as { SAME a Defining a set of vertices adjacent to a as { Connection } a And traversing the set { Connection from small to large according to the degree sequence a }-{SAME a At all points in the sequence, processes (b 1) - (b 3) are executed until the Connection is traversed a }-{SAME a All points in.
(b1) Let the selected vertex be z, if z is equal to { SAME a If all the vertexes are adjacent, continuing to execute downwards; otherwise point z is skipped.
(b2) If z belongs to the UAV base station MBS z The number of middle top points is not more than MBS a If yes, continuing to execute downwards; otherwise, point z is skipped.
(b3) If z is equal to a, and { SAME a The radius of the smallest enclosing circle formed by the vertices in (z) is not greater than r, then z is taken from the circle covering zUnmanned aerial vehicle base station MBS z Deleting the point A and adding the point Z to the MBS (base station of unmanned aerial vehicle) to which the point A belongs at present a Performing the following steps; otherwise, skip point z.
S4: step S3 is executed in a loop until the following termination condition is reached: 1. the maximum cycle number is reached; 2. the 5 consecutive best solutions did not change.
Based on the above procedure, a deployment scenario of drone base stations for ground terminals distributed as shown in fig. 2 can be obtained, and the result is shown in fig. 8.
Claims (4)
1. An unmanned aerial vehicle base station deployment method based on undirected graphs is characterized by comprising the following steps:
step 1, establishing a system model of unmanned aerial vehicle communication, which comprises the following specific steps:
(1) At any moment, the position information of the unmanned aerial vehicle is: u (t) = (x) u (t)，y u (t)), wherein x u (t) is the position of the abscissa of the unmanned aerial vehicle at any moment t, y u (t) the position of the vertical coordinate of the unmanned aerial vehicle at any time t, and the coordinate of the unmanned aerial vehicle at the initial time is the origin of a coordinate system; the position information of the ground terminal is as follows: q. q.s i ＝(x i ，y i ) Wherein x is i ，y i Respectively representing the abscissa and ordinate information of the ground terminal i on a coordinate system;
(2) Distance (i, j) between any ground terminals i, j:
wherein x is i ，y i Information of abscissa and ordinate, x, of the ground terminal i j ，y j Information of a horizontal coordinate and a vertical coordinate of the ground terminal j;
(3) The farthest horizontal communication distance r between the unmanned aerial vehicle and the ground terminal is as follows:
r 2 ＝R 2 -H 2
wherein R is the farthest communication distance allowed between the unmanned aerial vehicle and each ground terminal, and H is the fixed flight height of the unmanned aerial vehicle;
(4) The problem of minimizing the number K of drone base stations can be described in a formulation as:
wherein q is i Position information of ground terminals, u j The position information of the unmanned aerial vehicle is obtained, N is the number of ground terminals, i is the serial number of the ground terminals, and j is the serial number of the unmanned aerial vehicle;
(5) Constructing an undirected graph according to distance information between ground terminals, determining the degree of any vertex in the undirected graph, and preliminarily judging whether the ground terminals can be covered by an unmanned aerial vehicle base station or not based on adjacent information between the vertices in the undirected graph;
step 2, preprocessing a vertex with the degree of 0 or 1 in the undirected graph, deploying an unmanned aerial vehicle base station for a corresponding ground terminal, and reducing the workload of the step 3; the method specifically comprises the following steps: based on a system model, preprocessing vertexes with degrees of 0 and 1 in the undirected graph, circularly executing steps (1) to (2), and circularly terminating: the undirected graph G is a null graph or the number of all points in the undirected graph is more than or equal to 2;
(1) Searching an isolated point with the middle Degree of 0 in the undirected graph G, namely the point Degree (i) =0; deploying the unmanned aerial vehicle base station by taking the isolated points as the center, and deleting the points from the undirected graph G;
(2) Searching whether a suspension vertex with the degree of 1 exists in the undirected graph G; for each tree structure consisting of each suspended vertex in G and its uniquely connected vertices, the following operations are performed: (2a) Deploying an unmanned aerial vehicle base station for a father node and any one leaf node in the tree structure, wherein the center of the base station is the mass center of the father node and any one leaf node, and the centers of the remaining leaf nodes are the unmanned aerial vehicle base stations respectively and independently;
step 3, randomly constructing a plurality of unmanned aerial vehicle base stations, continuously adjusting and combining the unmanned aerial vehicle base stations, and reducing the number of the base stations; constantly adjust and merge unmanned aerial vehicle basic station, include: according to the conclusion that any non-adjacent vertex in an undirected graph corresponds to a ground terminal which cannot be covered by an unmanned aerial vehicle base station, a plurality of first-order and second-order complete subgraphs are randomly constructed, and then whether the vertex forms a complete subgraph or not is checked, whether the diameter of a minimum enclosing circle formed by the vertex is larger than that of the unmanned aerial vehicle base station or not is checked, the range of the unmanned aerial vehicle base station is continuously adjusted, the unmanned aerial vehicle base stations are combined, and the deployment scheme is optimized, wherein the specific implementation scheme is as follows:
(1) Forming a plurality of second-order complete subgraphs from adjacent points in the undirected graph G in pairs, if the vertex cannot form a second-order subgraph, independently forming a first-order complete subgraph, and setting an unmanned aerial vehicle base station based on the complete subgraphs to obtain a primary scheme for placing the unmanned aerial vehicle base station;
(2) Continuously optimizing the deployment scheme, traversing all vertexes in the undirected graph G from small to large according to the degrees of the vertexes in the undirected graph G, and executing the processes (2 a) and (2 b) until all the vertexes are traversed;
(2a) Suppose that the arbitrarily selected vertex is a, and the base station of the unmanned aerial vehicle to which a belongs is MBS a ，{SAME a Denoted as the set of vertices with a at the same drone base station, { Connection } a The vertex adjacent to the vertex a is represented as a set, if the unmanned aerial vehicle base station to which the vertex a belongs is processed, the vertex a is skipped, otherwise, the process 2b is executed downwards);
(2b) Traversing the set { Connection from small to large according to degree order a }-{SAME a Execute the processes (2 b 1) - (2 b 3) until all the Connection points are traversed a }-{SAME a Points in (c) };
(2b1) Let z be the arbitrarily chosen vertex, if z is equal to { SAME a If all the vertexes are adjacent, continuing, otherwise, skipping the vertex z;
(2b2) If z belongs to the unmanned aerial vehicle base station MBS z The number of medium vertex is less than or equal to MBS a If yes, continuing, otherwise, skipping over the vertex z;
(2b3) If z is equal to a, and { SAME a The radius of the smallest enclosing circle formed by all points in the z is not more than r, then z is selected from the unmanned aerial vehicle base station MBS to which z belongs z Delete and add z to the current none of a pointsMan-machine base station MBS a Otherwise, skipping over the z point;
and 4, circularly executing S3 until the following termination conditions are reached: 1) Reaching a maximum cycle number; 2) The m consecutive best solutions are unchanged, wherein m is 5.
2. The unmanned aerial vehicle base station deployment method based on the undirected graph as claimed in claim 1, wherein the adjacent information between the vertexes in the undirected graph is determined according to the distance between the ground terminals, and the method for determining the adjacent information between the vertexes in the undirected graph is as follows: if the distance between any ground terminal i and any ground terminal j is not more than 2r, the vertex corresponding to the terminal i and the vertex corresponding to the terminal j are considered to be adjacent in the undirected graph, and if the distance between the vertex corresponding to the terminal i and the vertex corresponding to the terminal j is larger than 2r, the vertex corresponding to the terminal i and the vertex corresponding to the terminal j are considered to be not adjacent; and then, constructing an undirected graph based on adjacent information between the vertexes, and determining the degrees of each vertex in the undirected graph.
3. The undirected graph-based unmanned aerial vehicle base station deployment method of claim 1, wherein: the preliminary judgement ground terminal can be covered by an unmanned aerial vehicle basic station, includes:
(1) According to the adjacent information of the vertexes in the undirected graph, for any pair of vertexes which are not adjacent in the undirected graph, the distance between the corresponding ground terminals is larger than 2r, and then the ground terminals can be determined to be incapable of being covered by one unmanned aerial vehicle base station;
(2) The necessary condition that any two ground terminals can be covered by one drone base station is that the vertexes of the undirected graph corresponding to the two ground terminals are adjacent;
(3) Accordingly, a necessary condition that any plurality of ground terminals can be covered by one drone base station is that a subgraph formed by corresponding vertexes of the base station on the undirected graph is a complete subgraph.
4. The undirected graph-based unmanned aerial vehicle base station deployment method of claim 1, wherein h-1 unmanned aerial vehicle base stations are deployed for each tree structure formed by each suspended vertex and the vertex uniquely connected with the suspended vertex, wherein h is the number of vertices of each tree structure, and the specific process is as follows:
the number of unmanned aerial vehicle base stations deployed in the tree structure is determined, h-1 is obtained, one unmanned aerial vehicle base station is deployed for one leaf node and the father node randomly, and one unmanned aerial vehicle base station is deployed for each leaf node of the rest leaf nodes.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011219855.5A CN112351438B (en) | 2020-11-04 | 2020-11-04 | Unmanned aerial vehicle base station deployment method based on undirected graph |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011219855.5A CN112351438B (en) | 2020-11-04 | 2020-11-04 | Unmanned aerial vehicle base station deployment method based on undirected graph |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112351438A CN112351438A (en) | 2021-02-09 |
| CN112351438B true CN112351438B (en) | 2022-12-02 |
Family
ID=74428730
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202011219855.5A Active CN112351438B (en) | 2020-11-04 | 2020-11-04 | Unmanned aerial vehicle base station deployment method based on undirected graph |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112351438B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113190031B (en) * | 2021-04-30 | 2023-03-24 | 成都思晗科技股份有限公司 | Forest fire automatic photographing and tracking method, device and system based on unmanned aerial vehicle |
| CN114840028B (en) * | 2022-07-04 | 2023-04-07 | 中国科学院自动化研究所 | Target monitoring method, target monitoring device, electronic equipment and storage medium |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107124755A (en) * | 2017-04-26 | 2017-09-01 | 哈尔滨工业大学 | The double-layer network Poewr control method of Gossip algorithm is broadcasted based on unbiased |
| CN111194038A (en) * | 2020-01-07 | 2020-05-22 | 北京航空航天大学 | Position deployment method for multiple unmanned aerial vehicles mobile base stations |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9464902B2 (en) * | 2013-09-27 | 2016-10-11 | Regents Of The University Of Minnesota | Symbiotic unmanned aerial vehicle and unmanned surface vehicle system |
| CN103716803B (en) * | 2013-12-03 | 2017-06-27 | 西安交通大学 | A kind of wireless sensor network relay node deployment method |
| CN106454739B (en) * | 2016-11-07 | 2019-10-15 | 南京佰联信息技术有限公司 | A kind of base station deployment method, network server and unmanned plane |
| US10602056B2 (en) * | 2017-01-13 | 2020-03-24 | Microsoft Technology Licensing, Llc | Optimal scanning trajectories for 3D scenes |
| US10624070B2 (en) * | 2017-04-14 | 2020-04-14 | Qualcomm Incorporated | Scheduling and transmission scheme for periodic and aperiodic control information |
| US11243540B2 (en) * | 2018-05-17 | 2022-02-08 | University Of Connecticut | System and method for complete coverage of unknown environments |
| CN109819453B (en) * | 2019-03-05 | 2021-07-06 | 西安电子科技大学 | Cost optimization unmanned aerial vehicle base station deployment method based on improved genetic algorithm |
| CN110233657B (en) * | 2019-04-01 | 2021-07-09 | 南京邮电大学 | Multi-unmanned aerial vehicle regional coverage deployment method based on particle swarm genetic algorithm |
| CN110557767B (en) * | 2019-09-06 | 2023-05-02 | 华南师范大学 | Base station allocation method, device and equipment |
| CN111163477B (en) * | 2020-02-29 | 2022-06-14 | 天津灵机科技有限公司 | Automatic deployment method of integrated intelligent base station in wide-area three-dimensional environment |
| CN111426810B (en) * | 2020-05-11 | 2021-02-09 | 河海大学 | Air-space-ground-integration-oriented water environment monitoring system deployment method |
-
2020
- 2020-11-04 CN CN202011219855.5A patent/CN112351438B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107124755A (en) * | 2017-04-26 | 2017-09-01 | 哈尔滨工业大学 | The double-layer network Poewr control method of Gossip algorithm is broadcasted based on unbiased |
| CN111194038A (en) * | 2020-01-07 | 2020-05-22 | 北京航空航天大学 | Position deployment method for multiple unmanned aerial vehicles mobile base stations |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112351438A (en) | 2021-02-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109819453B (en) | Cost optimization unmanned aerial vehicle base station deployment method based on improved genetic algorithm | |
| CN114690799B (en) | Air-space-ground integrated unmanned aerial vehicle Internet of things data acquisition method based on information age | |
| CN112351438B (en) | Unmanned aerial vehicle base station deployment method based on undirected graph | |
| CN111194038B (en) | Position deployment method for multiple unmanned aerial vehicles mobile base stations | |
| CN110267249B (en) | Post-disaster unmanned aerial vehicle base station deployment method and system based on artificial bee colony algorithm | |
| He et al. | Towards 3D deployment of UAV base stations in uneven terrain | |
| CN113645143B (en) | Optimization method and device for air trunking communication network | |
| CN114301784A (en) | Network shooting range training environment construction method and device, electronic equipment and storage medium | |
| CN109960279B (en) | Heuristic algorithm-based unmanned aerial vehicle hovering radius optimization method | |
| Rachedi et al. | BadZak: An hybrid architecture based on virtual backbone and software defined network for Internet of vehicles | |
| Zhang et al. | Base stations from current mobile cellular networks: Measurement, spatial modeling and analysis | |
| Guo et al. | 3D aerial vehicle base station (UAV-BS) position planning based on deep Q-learning for capacity enhancement of users with different QoS requirements | |
| Sawalmeh et al. | Providing wireless coverage in massively crowded events using UAVs | |
| CN109600756B (en) | Physical cell identification and distribution method based on maximum degree priority dyeing algorithm | |
| Wang et al. | Capacity-aware cost-efficient network reconstruction for post-disaster scenario | |
| CN113727331A (en) | 5G base station deployment method and device | |
| Alaghehband et al. | Efficient fuzzy based uav positioning in iot environment data collection | |
| CN113468819B (en) | Energy consumption optimization method based on genetic algorithm and adopting unmanned aerial vehicle to assist edge calculation | |
| CN113747389B (en) | High-capacity uplink data transmission method based on distributed OAM mode multiplexing | |
| Wu et al. | Joint Power and Coverage Control of Massive UAVs in Post-Disaster Emergency Networks: An Aggregative Game-Theoretic Learning Approach | |
| CN116861951A (en) | Optimization method for calculation efficiency of distributed graph neural network | |
| CN112437445B (en) | Power wireless private network networking method and system based on low-altitude platform | |
| CN115209424B (en) | Unmanned aerial vehicle base station shunt deployment method based on elliptical coverage model | |
| Wu et al. | A novel deployment method for uav-mounted mobile base stations | |
| Lv et al. | Design of Tethered UAV Low Altitude Relay Communication Networking Technology |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| DD01 | Delivery of document by public notice |
Addressee: Xu Juan Document name: Notice of publication and substantive examination of invention patent application |
|
| DD01 | Delivery of document by public notice | ||
| DD01 | Delivery of document by public notice |
Addressee: Xu Juan Document name: Notice of deemed withdrawal |
|
| DD01 | Delivery of document by public notice | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |