CN116261200A - An MPOLSR protocol optimization method based on link transmission quality for multi-UAV flight ad hoc network - Google Patents

Abstract

The present invention provides an MPOLSR protocol optimization method based on link transmission quality used in multi-UAV flight ad hoc networks. The MPOLSR protocol optimization based on information interaction between multi-UAVs is achieved through node connectivity and node connectivity. The link transmission number is expected to be screened by MPR nodes, and at the same time, the link transmission expectation is used as the link weight index to perform the shortest path calculation to realize the optimization of the MPOLSR protocol. The invention is created to solve the problems of single MPR screening mechanism, high execution complexity of the shortest path algorithm, and undifferentiated multi-path weights, etc., comprehensively considering node connectivity and node link transmission number expectations to perform MPR node screening, and replace the shortest path at the same time Algorithm, and the link transmission expectation is used as the path weight to distinguish, so as to improve the effectiveness and reliability of the network.

Description

A MPOLSR protocol optimization method based on link transmission quality for multi-UAV flying ad hoc networks

Technical Field

The present invention belongs to the field of unmanned aerial vehicle communication, and in particular relates to an MPOLSR protocol optimization method based on link transmission quality for use in a multi-unmanned aerial vehicle flight ad hoc network.

Background Art

Information exchange between multiple drones requires Flying Ad-hoc Networks (FANETs), which is an extended application of Mobile Ad-hoc Networks (MANETs) in the field of drones and belongs to a special kind of MANETs. Compared with other networking information collection methods, multi-drone self-organizing networks have extremely high flexibility in rapid movement, strong mobility without the need for pre-arranged ground base stations, and excellent adaptability to various complex and harsh ground environments. Therefore, multi-drone self-organizing networks have been increasingly widely used in fire monitoring, earthquake relief, power transmission, and target tracking. However, they have the characteristics of fast node movement, large scene range, and frequent topology changes. Therefore, designing a highly stable routing protocol to ensure the effectiveness and reliability of data transmission is one of the important research contents of multi-drone self-organizing networks.

Compared with other active routing protocols, the MPOLSR (Multi-Path Optimized Link State Routing) protocol introduces the concept of multi-point relay (MPR). Only the points selected as MPR by a node can forward the topology control information of the node, thereby greatly reducing the routing overhead of the flooding mechanism and having higher performance than active routing protocols such as DSDV (Destination Sequenced Distance Vector). Calculating multiple shortest paths at the same time effectively improves reliability and can ensure the efficiency and quality of drone clusters when performing tasks. However, the protocol has problems such as a single MPR screening mechanism, high execution complexity of the shortest path algorithm, and failure to distinguish between multiple path weights.

Summary of the invention

The present invention provides an MPOLSR protocol optimization method based on link transmission quality for a multi-UAV flying ad hoc network, which is used to solve the problems of single MPR screening mechanism, high execution complexity of the shortest path algorithm, and failure to distinguish multi-path weights.

The present invention is achieved through the following technical solutions:

A MPOLSR protocol optimization method based on link transmission quality for a multi-UAV flight ad hoc network, the MPOLSR protocol optimization method comprising:

The MPOLSR protocol optimization based on information interaction between multiple UAVs performs MPR node screening through node connectivity and node link transmission number expectation. At the same time, the SPFA shortest path algorithm is adopted, and the link transmission expectation is used as the link weight indicator for shortest path calculation to achieve MPOLSR protocol optimization.

Further, the MPR node screening is an MPR set selection based on network state perception, which specifically includes the following steps:

Step S1: First, establish a candidate MPR node list M set, which is initialized as an empty set;

Step S2: traverse the node 1-hop neighbor set to establish N1, and traverse the node 2-hop neighbor set to establish a strict 2-hop neighbor set N2;

Step S3: Determine whether the points in the MPR set can reach all strictly 2-hop neighboring points of the central node. If they can be covered, the algorithm ends, otherwise it goes to step S4;

Step S4: Calculate the weights of all nodes in N1, including node connectivity and node link transmission expectations;

Step S5: traverse all the points calculated previously and find the point with the largest weight;

Step S6: Add the node with the largest weight to the M set;

Step S7: remove the node with the largest weight in N1;

Step S8: Remove the points in N2 that can be reached through the largest node, and then return to step S3.

Furthermore, the 1-hop neighbor set in step S2 includes four fields:

N_neighbor_main_addr represents the IP address of the neighbor node of the source node, N_status represents the link symmetry relationship between the source node and the neighbor node, N_willingness represents the willingness of the neighbor node to forward the message of the source node, and ETX_R is a newly added field, which represents the inverse of the link transmission expectation between the source node and the neighbor node. The value is obtained by querying the modified node link information table.

Further, the node link information table includes seven fields, specifically, L_local_iface_addr represents the IP address of the local node, L_neighbor_iface_addr represents the IP address of the neighbor node of the local node, L_SYM_time records the expiration time of the symmetric link between the source node and the neighbor node, L_ASYM_time records the expiration time of the asymmetric link between the source node and the neighbor node, L_time represents the expiration time of the link information, and the LQ_I field and the ETX_R field are newly added fields, which respectively represent the modified forward link quality and the expected reciprocal of the number of transmissions between the node and the neighbor node. The LQ_I field is obtained by querying the node sending information table and the node receiving information table newly defined in the present invention, and the ETX_R field is obtained by obtaining the modified HELLO message packet of the present invention.

Further, the node sending information table and the node receiving information table are specifically as follows: S _ij is obtained by querying the node sending information table newly defined in the present invention, the node sending information table includes an N_neighbor_main_addr field to record the neighbor IP, and a Send_cnt field to record the number of messages sent to the corresponding IP node; at the same time, R _ij is obtained by querying the node receiving information table newly defined in the present invention, the node receiving information table includes an N_neighbor_main_addr field to record the neighbor IP, and a Recv_cnt field to record the number of messages received from the corresponding IP node; thereby, the LQ_I value can be calculated.

Furthermore, the modified HELLO message packet includes the Reserved first reserved field, Htime sending interval, Willingness data forwarding intention, Linkcode link coding information, Reserved second reserved field, LinkMessage Size link state size information, NeighborInterfaceAddress neighbor node interface address and the newly added LQ_I field, which indicates the LQ_I size of the source node that generates the HELLO message and the node that receives the HELLO message. After receiving the message, the source node can know the NLQ_I size of itself and the corresponding neighbor node, thereby calculating ETX_R through the aforementioned scheme and filling the result into the node link information table.

Furthermore, the calculation of the MPR node weight index in step S4 is specifically as follows:

Where ETX_R refers to the inverse of the expected ETX of link transmission, D refers to the node connectivity; α and β are weight indicators, and α+β=1.

Furthermore, the expected calculation of the node link transmission number is specifically as follows:

The link transmission expectation is:

Where R _ji refers to the number of HELLO messages received by node j from node i, and S _ij refers to the number of HELLO messages sent by node i to node j; R _ij refers to the number of HELLO messages received by node i from node j, and S _ji refers to the number of HELLO messages sent by node j to node i; LQ represents the forward link quality, NLQ represents the reverse link quality, LQ_I represents the modified forward link quality, and NLQ_I represents the modified reverse link quality.

Furthermore, the shortest path is the expected number of link transmissions, and the shortest path optimization calculation using the SPFA algorithm is specifically as follows:

Step D1: Customize a node_map structure, which contains four member variables, namely the address of each node, the previous hop address from the source node to the node, the distance from the central node to the point, and a Boolean variable, indicating whether the node is in the calculation queue, which is filled by traversing the 1-hop neighbor set, 2-hop neighbor set and topology table of the source node;

Step D2: Create a two-dimensional array etx_r_map to store the link weights from each node to any other node, and fill it by traversing the 1-hop neighbor set, 2-hop neighbor set and topology table of the source node. The link weight is the link transmission expectation of the node;

Step D3: Set the loop variable and initialize it to 0;

Step D4: Determine whether the value of the loop variable has reached the set number of multipath routes. If so, the algorithm ends. Otherwise, it goes to step D5.

Step D5: Set a calculation queue to store the nodes to be updated, and put the current source node into the calculation queue;

Step D6: Determine whether the calculation queue is empty, if it is empty, go to step 10, otherwise go to step D7;

Step D7: Take out the head node a;

Step D8: Traverse all neighboring edges in etx_r_map of node a, and for a's neighbor b, calculate Wa+Wab, where Wa represents the distance from the source node to a, and Wab represents the distance from point a to point b;

Step D9: If Wb<Wa+Wab, then update Wb=Wa+Wab in node_map, and determine whether node b is in the queue. If not, put b into the calculation queue, and set the Boolean type variable of node b in node_map to true, and then go to step D6;

Step D10: Check whether the weight from the source node to the destination node d is greater than the preset maximum value. If so, it indicates that the distance between the two points exceeds the preset value. By default, there is no shortest path and the algorithm ends. Otherwise, go to step D11;

Step D11: Update the link weight between the destination node d and the previous hop node d_pre of the destination node in etx_r_map to twice the previous value;

Step D12: assign d_pre information to the current node destination node d;

Step D13: Determine whether node d is a source node, if not, proceed to step D11, otherwise proceed to step D14;

Step D14: Set the weights of all points except the source node to infinity, increment the loop variable, and return to step D4.

Furthermore, the link weight between the nodes is defined as ETX, which is obtained by querying the modified topology table of the present invention; the modified topology table includes five fields:

T_dest_addr indicates the IP address of the destination node, T_last_addr indicates the IP address of the previous hop node to the destination node, T_seq indicates the sequence number of this topology message, T_time indicates the expiration time of this topology message, and ETX_R is a newly added field, indicating the inverse of the expected number of transmissions; the topology table entry is filled by the TC message received by the node;

The TC message includes ANSN indicating the topology message sequence number, Reserved indicating a reserved field, AdvertisedNeighbor MainAddress indicating the node address of the TC message generator node selected as the MPR point, and the ETX_R field is a newly added field indicating the inverse of the link transmission expectation between the TC message generator and the node corresponding to the IP address of the Advertised Neighbor MainAddress field, which is obtained by querying the one-hop neighbor node of the TC message generator.

The beneficial effects of the present invention are:

The present invention improves the packet delivery rate, end-to-end delay and throughput of the network.

The present invention improves the effectiveness and reliability of the network.

Under the premise of ensuring that the MPR point selected by the central node can cover all its strictly 2-hop neighboring points, the present invention comprehensively considers the node connectivity and link quality, making the selected MPR point forwarding message more reliable, while reducing the shortest path calculation time and improving the packet delivery rate.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a flowchart of an improved MPR node screening process of the present invention.

FIG. 2 is a flow chart of the improved multi-path SPFA algorithm of the present invention.

FIG3 is a diagram showing the relationship between the end-to-end delay and the node moving speed of the present invention.

FIG. 4 is a diagram showing the relationship between the packet delivery rate and the node moving speed of the present invention.

FIG. 5 is a graph showing the relationship between throughput and node moving speed according to the present invention.

FIG. 6 is a table of newly added node sending information of the present invention.

FIG. 7 is a newly added node reception information table of the present invention.

FIG. 8 is a modified node link information table of the present invention.

FIG. 9 is a modified node neighbor table of the present invention.

FIG. 10 is a modified HELLO packet structure of the present invention.

FIG. 11 is a modified TC packet structure of the present invention.

FIG. 12 is a modified network topology table structure of the present invention.

FIG13 is a calculation block diagram of the present invention.

DETAILED DESCRIPTION

The technical solutions in the embodiments of the present invention will be described clearly and completely below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of the present invention.

The calculation of node connectivity can be obtained by traversing the node neighbor table and the two-hop table. The calculation of node link transmission quality requires modifying the node HELLO message and the corresponding table and looking it up.

Figure 6 is a newly added node sending information table of the present invention, which is used to store the number of messages sent by the node to other nodes with corresponding IP addresses. Whenever a node sends a HELLO message to a neighbor node, the number of Send_cnt in the corresponding N_neighbor_main_addr in this table is increased by 1.

Figure 7 is a newly added node receiving information table of the present invention, which is used to store the number of messages received by the node from other nodes with the corresponding IP address. Whenever a node receives a HELLO message sent by a neighboring node, the Recv_cnt number in the corresponding N_neighbor_main_addr in this table is increased by 1.

FIG8 is a node link information table modified by the present invention, which is used to record specific information between different links of a node. Newly added LQ_I field and ETX_R field are used to store the forward link quality and transmission expectation of the node. The calculation method of LQ_I and ETX_R fields is as described above. FIG9 is a node neighbor table modified by the present invention, which is used to record information related to neighbor nodes of the current node. Newly added ETX_R field is used to store the transmission expectation of the node. The ETX_R field is consistent with that in the link information table.

Figure 10 depicts the modified HELLO packet structure, with a new LQ_I field added, which refers to the forward link transmission quality between the source node and the corresponding neighbor node. Whenever a node needs to send a HELLO message, it queries its own link information table, finds the LQ_I of the corresponding IP address and fills it in.

A MPOLSR protocol optimization method based on link transmission quality for a multi-UAV flight ad hoc network, the MPOLSR protocol optimization method comprising:

The MPOLSR protocol optimization based on information interaction between multiple UAVs performs MPR node screening through node connectivity and the expected number of node link transmissions. At the same time, the SPFA shortest path algorithm is adopted, and the link transmission expectation is used as the link weight indicator to calculate the shortest path to achieve MPOLSR protocol optimization.

Further, the MPR node screening is an MPR set selection based on network state perception, which specifically includes the following steps:

Step S1: First, establish a candidate MPR node list M set, which is initialized as an empty set;

Step S2: traverse the node 1-hop neighbor set to establish N1, and traverse the node 2-hop neighbor set to establish a strict 2-hop neighbor set N2 (strict 2-hop means that the source node can only be reached through 2 hops, excluding the 1-hop neighbor nodes);

Step S3: Determine whether the points in the MPR set can reach all strictly 2-hop neighboring points of the central node (that is, whether N2 is empty). If so, the algorithm ends, otherwise proceed to step S4;

Step S4: Calculate the weights of all nodes in N1, including node connectivity and node link transmission expectations;

Step S5: traverse all the points calculated previously and find the point with the largest weight;

Step S6: Add the node with the largest weight to the M set;

Step S7: remove the node with the largest weight in N1;

Step S8: Remove the points in N2 that can be reached through the largest node, and then return to step S3.

Furthermore, the 1-hop neighbor set in step S2 includes four fields:

N_neighbor_main_addr represents the IP address of the neighbor node of the source node, N_status represents the link symmetry relationship between the source node and the neighbor node, N_willingness represents the willingness of the neighbor node to forward the message of the source node, and ETX_R is a newly added field, which represents the inverse of the link transmission expectation between the source node and the neighbor node. The value is obtained by querying the modified node link information table.

Further, the node link information table includes seven fields, specifically, L_local_iface_addr represents the IP address of the local node, L_neighbor_iface_addr represents the IP address of the neighbor node of the local node, L_SYM_time records the expiration time of the symmetric link between the source node and the neighbor node, L_ASYM_time records the expiration time of the asymmetric link between the source node and the neighbor node, L_time represents the expiration time of the link information, and the LQ_I field and the ETX_R field are newly added fields, which respectively represent the modified forward link quality and the expected reciprocal of the number of transmissions between the node and the neighbor node. The LQ_I field is obtained by querying the node sending information table and the node receiving information table newly defined in the present invention, and the ETX_R field is obtained by obtaining the modified HELLO message packet of the present invention.

Further, the node sending information table and the node receiving information table are specifically as follows: S _ij is obtained by querying the node sending information table newly defined in the present invention, the node sending information table includes an N_neighbor_main_addr field to record the neighbor IP, and a Send_cnt field to record the number of messages sent to the corresponding IP node; at the same time, R _ij is obtained by querying the node receiving information table newly defined in the present invention, the node receiving information table includes an N_neighbor_main_addr field to record the neighbor IP, and a Recv_cnt field to record the number of messages received from the corresponding IP node; thereby, the LQ_I value can be calculated.

Furthermore, the modified HELLO message packet includes the Reserved first reserved field, Htime sending interval, Willingness data forwarding intention, Linkcode link coding information, Reserved second reserved field, LinkMessage Size link state size information, NeighborInterfaceAddress neighbor node interface address and the newly added LQ_I field, which indicates the LQ_I size of the source node that generates the HELLO message and the node that receives the HELLO message. After receiving the message, the source node can know the NLQ_I size of itself and the corresponding neighbor node, thereby calculating ETX_R through the aforementioned scheme and filling the result into the node link information table.

Furthermore, the calculation of the MPR node weight index in step S4 is specifically as follows:

Among them, ETX_R refers to the inverse of the expected ETX of link transmission, and D refers to the node connectivity; α and β are weight indicators, and α+β=1; the specific setting of the weight indicator can be adjusted accordingly according to different actual application scenarios.

Furthermore, the expected calculation of the node link transmission number is specifically as follows:

The link transmission expectation is:

Wherein R _ji refers to the number of HELLO messages received by node j from node i, and S _ij refers to the number of HELLO messages sent by node i to node j; R _ij refers to the number of HELLO messages received by node i from node j, and S _ji refers to the number of HELLO messages sent by node j to node i; LQ represents the forward link quality, NLQ represents the reverse link quality, LQ_I represents the modified forward link quality, and NLQ_I represents the modified reverse link quality. For node i, the number of HELLO messages that i can obtain is only "the number of HELLO messages sent by i to j" and "the number of HELLO messages sent by i to j". It is impossible to calculate LQ and NLQ based on this data alone, and further it is impossible to calculate ETX. Therefore, the present invention makes a certain degree of change to the two parameters of the expected transmission number, and the numerators of LQ and NLQ are exchanged to become two new parameters LQ_I and NLQ_I, while not affecting the calculation of the expected transmission number.

The original MPOLSR protocol uses the Dijkstra algorithm to calculate multiple shortest paths, which is highly complex and does not distinguish the weights of different links. The present invention uses link transmission expectations as the weights of each link to distinguish, and uses the SPFA algorithm with lower complexity to implement it. By modifying the TC message, each node can perceive the edge weights of all links in the network, and at the same time modify the network topology table to look up the table to calculate the shortest path.

FIG11 illustrates the modified TC packet structure, with a newly added ETX_R field, which refers to the expected inverse of the link transmission number between the source node and the corresponding neighbor node.

FIG12 illustrates the modified network topology table structure, with a newly added ETX_R field recording the expected inverse of the transmission between the T_last_addr and T_dest_addr links.

The shortest path algorithm based on link transmission expectation is shown in FIG2 , and includes the following steps:

Furthermore, the shortest path is an optimization calculation of the expected shortest path of the link transmission number, specifically,

Step D1: Customize a node_map structure, which contains four member variables, namely the address of each node, the previous hop address from the source node to the node, the distance from the central node to the point, and a Boolean variable, indicating whether the node is in the calculation queue, which is filled by traversing the 1-hop neighbor set, 2-hop neighbor set and topology table of the source node;

Step D2: Create a two-dimensional array etx_r_map to store the link weights from each node to any other node, and fill it by traversing the 1-hop neighbor set, 2-hop neighbor set and topology table of the source node. The link weight is the link transmission expectation of the node;

Step D3: Set the loop variable and initialize it to 0;

Step D4: Determine whether the value of the loop variable has reached the set number of multipath routes. If so, the algorithm ends. Otherwise, it goes to step D5.

Step D5: Set a calculation queue to store the nodes to be updated, and put the current source node into the calculation queue;

Step D6: Determine whether the calculation queue is empty, if it is empty, go to step 10, otherwise go to step D7;

Step D7: Take out the head node a;

Step D8: Traverse all neighboring edges in etx_r_map of node a, and for a's neighbor b, calculate Wa+Wab, where Wa represents the distance from the source node to a, and Wab represents the distance from point a to point b;

Step D9: If Wb<Wa+Wab, then update Wb=Wa+Wab in node_map, and determine whether node b is in the queue. If not, put b into the calculation queue, and set the Boolean type variable of node b in node_map to true, where Wb represents the distance from the source node to b, and then go to step D6;

Step D10: Check whether the weight from the source node to the destination node d is greater than the preset maximum value. If so, it indicates that the distance between the two points exceeds the preset value. By default, there is no shortest path and the algorithm ends. Otherwise, go to step D11;

Step D11: Update the link weight between the destination node d and the previous hop node d_pre in etx_r_map to twice the previous value, in order to prevent the calculation of duplicate paths;

Step D12: assign d_pre information to the current node destination node d;

Step D13: Determine whether node d is a source node, if not, proceed to step D11, otherwise proceed to step D14;

Step D14: Set the weights of all points except the source node to infinity, increment the loop variable, and return to step D4.

Furthermore, the link weight between the nodes is defined as ETX, which is obtained by querying the modified topology table of the present invention; the modified topology table includes five fields:

T_dest_addr indicates the IP address of the destination node, T_last_addr indicates the IP address of the previous hop node to the destination node, T_seq indicates the sequence number of this topology message, T_time indicates the expiration time of this topology message, and ETX_R is a newly added field, indicating the inverse of the expected number of transmissions; the topology table entry is filled by the TC message received by the node;

The TC message includes ANSN indicating the topology message sequence number, Reserved indicating a reserved field, AdvertisedNeighbor MainAddress indicating the node address of the TC message generator node selected as the MPR point, and the ETX_R field is a newly added field indicating the inverse of the link transmission expectation between the TC message generator and the node corresponding to the IP address of the Advertised Neighbor MainAddress field, which is obtained by querying the one-hop neighbor node of the TC message generator.

The MPOLSR protocol optimized by this invention is named as AMPOLSR protocol. To verify the effect achieved by the present invention, based on the network simulation software NS2, the simulation of MPOLSR in different scenarios, AMPOLSR-Dijkstra using Dijkstra algorithm to calculate the shortest path, and AMPOLSR-SPFA optimized by SPFA algorithm are implemented, and the main performance indicators of these three routing protocols are compared, including packet delivery rate, average end-to-end delay and network throughput. The main simulation parameters used by the present invention are shown in the table below, and the simulation model uses the RPGM mobile model.

Figure 3 describes the relationship between end-to-end delay and node movement speed under different protocols. It can be seen from Figure 3 that:

The average end-to-end delay shows an upward trend as the node movement speed increases. This is because when the node movement speed is low, the network topology is relatively static and the routing is stable, so the delay is low; but as the maximum node movement speed increases, the network topology structure changes further, and the topology table is not updated in time, resulting in the shortest path previously calculated may not be the shortest path under the current network conditions, which increases the information propagation delay. At the same time, it can be seen that the modified protocol has a lower delay than the original protocol, and the delay of the SPFA algorithm is less than the delay of the Dijkstra algorithm, indicating that the improved algorithm finds a better shortest path, so the information transmission delay is reduced, and the SPFA algorithm has a lower delay than the Dijkstra algorithm because of its low complexity.

Figure 4 describes the relationship between packet delivery rate and node movement speed under different protocols. It can be seen from Figure 4 that:

The packet delivery rate shows a downward trend as the node movement speed increases. This is because when the node movement speed is low, the network topology is relatively static and the information packet loss rate is low. However, as the maximum node movement speed increases, the network topology structure changes further and the link stability decreases. Therefore, the packet delivery rate shows a downward trend overall. At the same time, it can be seen that the packet delivery rate of the modified protocol is larger than that of the original protocol. The delivery rate of the SPFA algorithm is greater than that of the Dijkstra algorithm, which shows that the algorithm does optimize the packet delivery rate, and the SPFA algorithm is more effective, reducing more packet loss rates and improving network transmission reliability.

Figure 5 describes the relationship between throughput and node movement speed under different protocols. It can be seen from Figure 5 that:

The network throughput generally shows a downward trend as the node movement speed increases. This is because when the node movement speed is low, the network topology is relatively static, the links between nodes are stable, the network control overhead is small, and more actual message packets can be sent, so the network throughput is large. However, as the maximum node movement speed increases, the network topology changes further accelerate, the link instability becomes greater, and the information packet loss rate increases, resulting in a decrease in network throughput. This trend is consistent with the aforementioned packet delivery rate. At the same time, it can be seen that the throughput of the modified protocol is larger than that of the original protocol. The throughput of the SPFA algorithm is greater than the throughput of the Dijkstra algorithm, indicating that more information flows are transmitted.

The simulation results show that the improved MPOLSR routing protocol not only improves the network's packet delivery rate and throughput by optimizing the MPR selection method and the shortest path algorithm, but also reduces the network's end-to-end delay, that is, the effectiveness and reliability are improved. Therefore, the improved MPOLSR routing protocol can be better applied to UAV flight ad hoc networks to meet mission requirements.

The present invention adopts a shortest path optimization algorithm based on link transmission expectation, the core of which is to adopt the SPFA algorithm, the average complexity of which is O(km), where k is a very small constant and m represents the number of edges in graph theory. In the worst case, the complexity is O(nm), where n represents the number of points in graph theory. The original protocol shortest path algorithm adopts the Dijkstra algorithm, which is limited by the node topology table structure of the protocol and has an execution complexity of O(nm). Therefore, in general, the complexity of the SPFA algorithm is smaller than that of the Dijkstra algorithm, and this method distinguishes the weights of different edges based on link transmission expectations. Executing this algorithm can reduce end-to-end delay and effectively improve packet delivery rate and network throughput.

The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and principle of the present invention should be included in the protection scope of the present invention.

Claims (10)

1. a kind of MPOLSR protocol optimization method based on link transmission quality in many unmanned aerial vehicle flight ad hoc networks, it is characterized in that, described MPOLSR protocol optimization method comprises, The MPOLSR protocol optimization based on information interaction between multiple UAVs screens MPR nodes through node connectivity and node link transmission expectations, and at the same time selects the shortest path and uses link transmission expectations as the MPR node weight index to implement the MPOLSR protocol optimization. 2. according to claim 1, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, described MPR node is screened as the MPR set based on network state awareness selection, specifically including the following steps, Step S1: First, create a candidate MPR node list M set, which is initialized as an empty set; Step S2: Traversing the node 1-hop neighbor set to establish N1, traversing the node 2-hop neighbor set to establish a strict 2-hop neighbor set N2; Step S3: Determine whether the points in the MPR set can reach all the strict 2-hop neighbor points of the central node. If they can be covered, the algorithm ends, otherwise, enter step S4; Step S4: Calculate the weights of all nodes in N1, including node connectivity and node link transmission expectations; Step S5: Traversing all the previously calculated points to find out the point with the largest weight; Step S6: Add the node with the largest weight into the M set; Step S7: remove the node with the largest weight in N1; Step S8: Remove the point that can be reached through the largest node in N2, and then return to step S3. 3. according to claim 2, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, the 1-hop neighbor set in the described step S2 comprises four Field: N_neighbor_main_addr represents the ip address of the neighbor node of the source node, N_status represents the link symmetry relationship between the source node and the neighbor node, N_willingness represents the message willingness program of the neighbor node to forward the source node, ETX_R is a newly added field, representing the source node and the neighbor node The reciprocal of the link transmission expectation of , and obtain the value by querying the modified node link information table. 4. according to claim 3 a kind of MPOLSR protocol optimization method based on link transmission quality in the multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, described node link information table comprises seven fields, specifically L_local_iface_addr represents the ip address of the local node, L_neighbor_iface_addr represents the ip address of the neighbor node of the local node, L_SYM_time records the expiration time of the symmetric link between the source node and the neighbor node, L_ASYM_time records the time of the asymmetric link between the source node and the neighbor node The expiration time, L_time indicates the expiration time of the link information, the LQ_I field and the ETX_R field are newly added fields, which respectively represent the reciprocal of the modified forward link quality and transmission number expectation of the node and the neighbor node. The LQ_I field is obtained by querying the node transmission information table and the node reception information table newly defined in the present invention, and the ETX_R field is obtained by obtaining the modified HELLO message package of the present invention. 5. according to claim 4, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flying ad hoc network, it is characterized in that, described node sends information table and node receives information table specifically as , obtain S _ij by querying the node sending information table newly defined in the present invention, the node sending information table includes the N_neighbor_main_addr field record neighbor ip, the Send_cnt field record sending to the number of messages corresponding to the ip node; meanwhile, by querying the new definition of the present invention The node receiving information table obtains R _ij , and the node receiving information table includes the N_neighbor_main_addr field to record the neighbor ip, and the Recv_cnt field to record the number of messages received from the corresponding ip node; thus the LQ_I value can be calculated. 6. according to claim 4, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, the HELLO message package after the modification includes Reserved first reserved Field, Htime sending interval, Willingness data forwarding willingness, Linkcode link encoding information, Reserved second reserved field, LinkMessage Size link state size information, NeighborInterfaceAddress neighbor node interface address and the newly added LQ_I field, indicating the source of the HELLO message The LQ_I size of the source node and the node that received the HELLO message. After receiving the message, the source node can know the NLQ_I size of itself and the corresponding neighbor node, so as to calculate ETX_R through the above scheme, and fill the result into the node link information table middle. 7. according to claim 2, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, the calculation of MPR node weight index in the described step S4 is specific The index calculation formula is:

Where ETX_R refers to the reciprocal of link transmission expectation ETX, D refers to node connectivity; α and β are weight indexes, and satisfy α+β=1. 8. according to claim 7, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, the expected calculation of the number of node link transmissions is specifically, The link transmission expectation is,

Among them, R _ji refers to the number of HELLO messages that node j receives from node i, S _ij refers to the number of HELLO messages that node i sends to node j; R _ij refers to the number of HELLO messages that node i receives from node j, S _ji refers to the number of HELLO messages sent by node j to node i; LQ stands for forward link quality, NLQ stands for reverse link quality, LQ_I stands for modified forward link quality, NLQ_I stands for modified reverse link quality road quality. 9. according to claim 1, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, it is characterized in that, described shortest path is the expected shortest path of link transmission number The optimization calculation, specifically, Step D1: Customize a node_map structure, which contains four member variables, which are the address of each node, the address of the last hop from the source node to the node, the distance from the center node to the point, and a Boolean The type variable indicates whether the node is in the calculation queue, and is filled by traversing the 1-hop neighbor set, 2-hop neighbor set and topology table of the source node; Step D2: Create a etx_r_map two-dimensional array to store the link weight value from each node to any other node, and fill it by traversing the 1-hop neighbor set, 2-hop neighbor set and topology table of the source node. The size of the link weight is the link transmission expectation of the node; Step D3: Set the loop variable and initialize it to 0; Step D4: Determine whether the value of the loop variable has reached the set number of multipath routes, and if so, end the algorithm, otherwise enter step D5; Step D5: Set a calculation queue to store the nodes to be updated, and put the current source node into the calculation queue; Step D6: Determine whether the calculation queue is empty, if it is empty, go to step 10, otherwise go to step D7; Step D7: Take out the queue head node a; Step D8: Traverse all adjacent edges in the etx_r_map of node a, and calculate Wa+Wab for neighbor b of a. Where Wa represents the distance from the source node to a, and Wab represents the distance from point a to point b; Step D9: If Wb<Wa+Wab, then update Wb=Wa+Wab in node_map, and judge whether node b is in the queue at the same time, if not, put b into the calculation queue, and set the Boolean type of node b in node_map The variable is set to true, and then enter step D6; Step D10: Check whether the weight value from the source node to the destination node d is greater than the preset maximum value, if so, it indicates that the distance between these two points exceeds the preset value, there is no shortest path by default, and the algorithm ends; otherwise, enter step D11; Step D11: In etx_r_map, update the link weight between the destination node d and the last hop node d_pre of the destination node to twice the previous value; Step D12: Assign d_pre information to the destination node d of the current node; Step D13: Determine whether node d is a source node, if not, go to step D11, otherwise go to step D14; Step D14: Set the weights of all points except the source node to infinity, meanwhile the loop variable is incremented, and return to step D4. 10. according to claim 9, a kind of MPOLSR protocol optimization method based on link transmission quality for multi-unmanned aerial vehicle flight ad hoc network, is characterized in that, the link weight value size between described nodes is defined as ETX, Obtain by querying the modified topology table of the present invention; the modified topology table includes five fields: T_dest_addr indicates the ip address of the destination node, T_last_addr indicates the ip address of the last hop node to reach the destination node, T_seq indicates the sequence number of this topology message, T_time indicates the expiration time of this topology message, ETX_R is a newly added field, indicating the number of transmissions The expected reciprocal; the topology entry is filled by the TC message received by the node; The TC message includes ANSN representing the sequence number of the topology message, Reserved representing the reserved field, AdvertisedNeighbor MainAddress representing the node address for selecting the TC message generator node as the MPR point, and the ETX_R field being a newly added field, indicating that the TC message generator and the corresponding Advertised Neighbor The reciprocal of the link transmission expectation of the node with the ip address in the MainAddress field is obtained by querying the one-hop neighbor node of the TC message generator.

Images