CN109640286B - Ant colony routing method for space-time air-ground vehicle network - Google Patents

Abstract

The invention belongs to the technical field of traffic information, and particularly relates to an ant colony routing method for an air-ground vehicle network, which comprises the steps of firstly determining a transmission region R according to a source node S and a destination node D, when one node receives a routing request packet RREQ, firstly judging whether the node is in the R, if not, discarding, and if so, carrying out the next step; judging the relationship between the node and the previous node to judge the path loss between the nodes; when the information is transmitted to a destination node D, multiple paths from the same source node are eliminated, paths which do not meet a threshold are eliminated, and an optimal path is selected; and selecting a standby path, finding a path with the maximum difference value by using the difference value between the standby path and the optimal path, returning routing reply information according to the optimal path and the standby path, and updating a routing table by the source node after returning the routing reply information to the source node. The invention ensures the normal communication between the vehicle nodes, and the information can be transmitted quickly and accurately.

Description

Ant colony routing method for space-time air-ground vehicle network

Technical Field

The invention belongs to the technical field of traffic information, and particularly relates to an ant colony routing method for an air-ground vehicle network.

Background

The urban environment building stands, and the communication between vehicles is easily interrupted due to the obstruction of obstacles; and because the vehicles are more, the density of the crowded nodes on the road is high, the information transmission often needs to wait in a queue, and the information is discarded when the congestion is serious.

In the existing method, in the link, an ant colony-based sensing route is provided, and the attenuation factor of the environment is mainly considered when the path loss is calculated. The above method is unreliable in urban environments because in environments with high population, vehicle and building densities the sources of path loss are not only environmental fading (influenced by air etc.) but also mainly shadowing of various obstacles, which is not negligible.

In addition to selecting the best route (ranked first according to some calculation criteria) as the route for transmitting information, an alternate route is often selected, which is ranked second according to the same calculation criteria. In urban environments, the node density is high, the first and second ranked paths have similar performance, so that many nodes may be the same, and when the optimal path cannot be normally transmitted, the second best path is likely to fail.

Disclosure of Invention

Aiming at the technical problem, the invention provides an ad colony routing method for an air-ground vehicle network, which comprises the following steps:

(1) firstly, determining a transmission region R (the region is three-dimensional) according to a source node S and a destination node D, when a node receives a route request packet RREQ, firstly judging whether the node is in the R, if not, discarding, and if so, carrying out the next step;

(2) judging whether the current node and the previous node are aerostat nodes or unmanned aerial vehicle nodes, if one node is not a ground node, multiplying LOSs coefficients to obtain path LOSs, and if the node is a common land node, judging the relationship (LOS, NLOS1 and NLOS2) between the node and the previous node to judge the path LOSs between the nodes and record;

(3) when the information is transmitted to a destination node D, waiting for a period of time is needed, then the destination node D has a plurality of paths from the same source node, paths which do not meet a threshold are eliminated, and then an optimal path needs to be selected from the reserved paths;

(4) except for choosing a path with a high transmission success rate. And selecting a standby path, finding the path with the maximum difference by using the difference between the standby path and the optimal path, then returning a routing reply message (RREP) according to the optimal path and the standby path, returning the RREP to the source node, updating a routing table by the source node, and recording a new path.

The method for routing the ant colony of the space-adjacent-air vehicle network ensures normal communication between vehicle nodes, and information can be transmitted quickly and accurately.

Drawings

FIG. 1 is an overall flow chart of the routing protocol of the present invention;

FIG. 2 is a diagram illustrating an embodiment of determining a flooding domain according to a Manhattan model;

FIG. 3 is an embodiment flooding flow diagram;

FIG. 4 is a diagram of an embodiment of validating node relationships according to a CORNER model;

FIG. 5 is a road segment to which a node belongs determined by the embodiment;

FIG. 6 shows three position relationships of the nodes of the embodiment: LOS, NLOS1, NLOS 2;

FIG. 7 is a diagram of an embodiment NLOS1 path loss;

fig. 8 is a schematic diagram of an embodiment NLOS2 path loss.

Detailed Description

The specific technical scheme of the invention is described by combining the embodiment.

And aiming at the special network structure of the space-time ground vehicle, a network model conforming to the actual physical scene is established. According to the height of the nodes in the network in the physical space, the nodes in the network are divided into three types, which are respectively:

(1) aerostat node: is located at a height h from the ground₁In kilometer of empty space, the coverage area is d₁Kilometers, i.e. the point on the ground where the aerostat is mapped, as the center of the circle, and radius r₁＝d₁Nodes within a/2 km circle may communicate with the aerostat. The ideal dwell state of the aerostat node is stationary.

(2) Unmanned aerial vehicle node: the height from the ground is h₂Kilometer, flight speed v kilometer/hour, itCoverage area to ground node is d₂Kilometers, namely, the point on the ground where the unmanned aerial vehicle is mapped is taken as the circle center, and the radius is r₂＝d₂Ground nodes within a/2 km circle may communicate with the aerostat.

(3) Ground node: the nodes on the ground mainly comprise train nodes, trackside monitoring nodes and the like.

For three types of nodes in the network, the node fairness is specified: each type of node has the same physical characteristics and functions, and the capacity of the node in the ad hoc network is the same, namely, each aerostat node, each unmanned aerial vehicle node, each train node and each trackside node are respectively in equal positions, and the roles of the nodes in the network are respectively the same.

As shown in fig. 1, the method for routing ant colony in space-time air-ground vehicle network is mainly divided into three parts: route discovery, route establishment, route maintenance. Specifically, the method comprises the following steps:

1 route discovery

(1) HELLO message interaction node information

In the route discovery stage, in order to find all eligible routes which can reach the destination node, one node receives the RREQ, and in order to prevent flooding, whether the node is in the corresponding areas of the source node and the destination node is judged firstly, then the sight distance relationship is judged according to the node and the previous hop node so as to obtain the route loss between the two nodes, and preparation is made for obtaining the subsequent route pheromone concentration, and details are as follows.

Firstly, the interaction between two nodes is mainly through a HELLO packet, and a neighbor entry can be newly built or a neighbor is known to remain connected with itself through the HELLO packet. If a neighbor's HELLO message is not received within a certain time, the neighbor is considered to be no longer connected with itself, and the routes using this node as the next hop can no longer be used to transmit data, so the routes are set to an invalid state. The fields in HELLO include: destination IP address, IP address of node, destination sequence number: the latest serial number and hop count of the node are set to 0. Here we improve to add new information to the HELLO packet, including the link number of the node, whether it is an intersection node, the geographical location of the node and the fading parameters/path loss of the surrounding environment.

The following is a schematic of the HELLO packet:

whenever a node receives a HELLO message from a neighbor, the node should be confident that it has a valid route to reach that neighbor, and if necessary, can establish one such route. If a route already exists, the lifetime of this route should be increased. Routes to the neighbors, if any, must contain the latest destination sequence number in the Hello message. The current node can now forward the data packet using this route. In AODV, link detection mainly depends on continuous sending of Hello packets to detect the state of a neighbor, and in actual implementation, a timer is used for controlling and maintaining a route to a neighbor node, and continuously sending and receiving the Hello packets to update the expiration time of the route.

(2) And (3) route searching: knowing the source node and the destination node, finding the intermediate node

When the destination route is searched, each node firstly checks whether a path reaching the destination node exists in the neighbor node table of the node, and if so, information transmission is directly carried out according to the maximum concentration of the path selection pheromone. If the route discovery is not started, a route request RREQ (route request) is directionally broadcasted to the surrounding environment, and the RREQ comprises a source node IP, an address, a destination node IP, an address, an RREQ ID, a node ID on a path, an address, a fading parameter/path loss.

The RREQ packet is as follows:

(3) discarding ineligible intermediate nodes

The position relationship between the source node S and the destination node D can be established according to a manhattan model, as shown in fig. 2 (note that the aerostat and the unmanned aerial vehicle node can be mapped onto a ground two-dimensional plane and regarded as a common node). If the source node and the destination node are on the same road, the position relationship is that the true north is true south and the true west is true east, otherwise, the position relationship is that the north, south, north and south.

The optimal route request area should cover the active areas of S, D and the intermediate nodes necessary for routing as much as possible, and should sufficiently limit the invalid flooding, and should also consider the roads, locations, directions, etc. Based on this, the location determination flooding restriction process is as follows (abstracting the road into a two-dimensional plane):

the intermediate node I receives the RREQ broadcast by the source node S. First, it is determined whether S and D are on the same road. If D is in the positive east, south, west and north direction of S, no matter how the S and D are in the direction relation, S only needs to flood towards the area (1/2 area) where D is located to effectively reduce the flooding area, namely I judges whether the S and D are located in the 1/2 area of S and D, if yes, RREQ is forwarded, otherwise, RREQ is discarded;

if S and D are not on the same road, the position relationship is northeast, northwest, southeast and southwest. In this case, the two-dimensional plane is divided into 4 regions by the double positional relationship, and in this case, S only needs to flood the region where D is located (1/4 region) regardless of the directional relationship between S and D. And I, judging whether the RREQ is in an 1/4 area between S and D, if so, forwarding the RREQ, and otherwise, discarding the RREQ.

Under the limitation of real environment, the moving directions of the same road node are different. Flooding cannot be well limited only by location determination, and flooding can also be limited according to the relationship of the moving direction of the node. According to different moving directions, the neighbor nodes of the source node S can be divided into homodromous neighbors, reverse neighbors and vertical neighbors. Routing forwarding should select nodes in the same direction or the reverse direction for forwarding, because two node links which are vertical to each other are fragile and have the possibility of breaking at any time; the same-direction node is stable, but if no same-direction node exists, the reverse adjacent node can also be used as a supplementary route to transmit data.

If S and D are on the same road, after receiving RREQ, the intermediate node I in the 1/2 area judges the relation between itself and S moving direction. Knowing the direction of movement, speed, and position of I and S, the angle between the two can be calculated using these conditions and discarded if the angle is about 90 degrees. The RREQ is forwarded in the same direction or in the reverse direction.

If S and D are not on the same road, the routing direction may need to "turn" along with the road layout. The intermediate node I in the region 1/4 does not need to make any further direction determination at this time. Since the flooding domain is now the best flooding domain, continuing to shrink the domain may result in no routes being found, as shown in fig. 3.

(4) Determining path loss between nodes

After a candidate node for transmission is found, the transmission may proceed. Firstly, whether a current node and a previous hop node are unmanned aerial vehicles or aerostat nodes is judged, if the current node and the previous hop node are the unmanned aerial vehicles or the aerostat nodes, a path loss coefficient is set to be a constant a1, if the node of the unmanned aerial vehicles is set to be a constant a2, a ground node path loss coefficient is set to be s3, note that a1 is greater than a2 and is less than a3, and multiplication is carried out according to the types of two adjacent nodes to obtain the path loss of the section. If the node and the previous hop node are both common nodes, they may encounter the influence of various obstacles during the transmission process, and the path loss difference between the straight propagation path and the path loss after reflection and refraction is large, so the node can be classified by using the CORNER model, and the flow is as shown in FIG. 4.

And mapping the nodes to the road sections according to the road section information in the neighbor node table, and representing the node information by the road sections. If the node is at the intersection (determined according to the field "whether it is an intersection node"), it is mapped to the road segment of the previous hop node, e.g., B is mapped to road segment 1 of a in fig. 5.

And then judging the position relation of the nodes according to the road section relation, wherein the position relation is totally divided into three types: distance of eye (LOS), one corner distance (NLOS1), two corner distance (NLOS 2). If two nodes can be mapped to the same road section, the LOS is indicated, if the two nodes are mapped into two sections, but are connected by a crossroad and one is in the other sight line range, or the two nodes are connected by two crossroads, the previous-hop node generates two windows, one is a sight line window SWA (between the blue lines of the lower graph) generated at the crossroad closest to the previous-hop node, the other is a sight line window SWB (between the yellow lines of the lower graph) generated at the farthest distance from the previous-hop node, the SWB is contained in the SWA and both contain the current node, and the relationship of the two nodes is indicated as the LOS.

If two nodes are mapped to two road segments, they are not in line of sight with each other, or if mapped to two road segments, they are separated by two intersections, one node being in line of sight with the intersection that is further away. The remaining case is NLOS 2. As shown in fig. 6.

Of these three relationships, the LOS has the lowest Path LOSs (PL), which is related only to the wavelength and the two-point distance.

In NLOS1, the signal received by the destination node is the sum of the reflections and diffractions by the building. In fig. 7, D denotes diffraction, R denotes reflection, T denotes a transmission node, R denotes a reception node, and J denotes an intersection node.

Where PLD is the sum of the path loss diffraction and PLR is the sum of the reflections. It can be seen that it is related to the arrival of nodes at the intersection, and if it is close to the intersection node, reflection is dominant, whereas diffraction is dominant.

When the relationship between the two nodes is NLOS2, the signal needs to go through multiple bends, needs to go through multiple reflections R, DD, reflected diffraction RD and diffracted reflection DR interleaving, and the obtained path loss result is as shown in fig. 8.

Therefore, the sum of the node and the path loss of the previous hop is obtained according to the formula, the RREQ is written in for transmission until the destination node is reached, the loss on each path is accumulated at the destination node and is brought into m in the formula (2), the fading parameters can be directly brought into the aerostat and the unmanned aerial vehicle, then the congestion condition of the paths is calculated, and the successful receiving probability of each path is obtained, so that the pheromone density phi of the path is obtained.

2, establishing a route: finding optimal path and standby path from found paths

For the destination node, it has received the information of multiple paths from the same source node, and the purpose of this part is to select the optimal path for information transmission, and at the same time, select the backup path to ensure that the information can be transmitted quickly when the optimal path fails, as detailed below.

After receiving the RREQ, the node waits for a period of time t, and calculates the concentrations of the pheromones of the received multiple paths according to a formula as follows:

due to the openness of wireless channel transmission, the complexity of a receiving environment and the random mobility of communication users, wireless signals are lost to different degrees, and in order to make our routing protocol more suitable for practical scenes, the problems of fading and interference of radio waves in the transmission process need to be considered.

The Nakagami channel model has good fitting degree on measured data, is suitable for any fading parameters, has small operand, theoretically becomes a wireless channel model with wide representative significance and has important application value. By combining the model with the characteristics of the private network, the probability formula of successfully receiving the message by the two nodes i, j is obtained as follows:

where D is the distance between two points, R is the communication radius, m is the fading factor (fading parameters for aerostat and drone nodes, which vary from environment to environment, and path loss for land nodes from the node to the previous hop), Γ is the gamma function, and P is the probability of successful reception between two points.

In addition to taking into account channel fading, congestion between nodes needs to be consideredThe problem is as in equation (3). Suppose q_ij(t) is the length of the waiting packet sent by node i to node j, q_totalIs the sum of the lengths of all waiting packets of the j node, and M is the length of the node buffer queue, so the congestion status of the path is as follows:

alpha is an pheromone heuristic, representing the relative importance of the trace, a larger value indicating that an ant is more inclined to select the path that other ants have traveled.

The formula (4) for calculating pheromones on the whole path (accumulating pheromone values of each adjacent node on the path) after the pheromone formula (4) can be obtained by integrating the congestion condition and the probability of successfully receiving the message, and the specific meanings in the formula are as follows: the adjustment factor of β is increased if the transmission accuracy of the side weight message is correct, and is decreased if the transmission speed of the side weight message is fast, and the adjustment factor of β can be adjusted according to different requirements.

When the RREQ reaches the destination node, the RREP updates the pheromone of the path, an information volatilization mechanism is added to avoid excessive inundation of information by the residual pheromone, and each route found by the ants has proper survival time by adjusting the volatilization coefficient. At the time t + Δ t, the pheromone concentration of the node on the route is updated to the following formula, r is an information volatilization coefficient, and the coefficient design can be carried out according to the type of the node:

and setting a pheromone concentration threshold T at the destination node, wherein the concentration is larger than the threshold to be used as a candidate path, and then summarizing and selecting the candidate path to transmit with high pheromone concentration. But in order to prevent the link from being interrupted and failed and other emergencies, the strategy of standby routing is adopted, the stability of the network is enhanced, and the throughput and the packet delivery rate of the network are improved. When the standby route is selected, a route with the second pheromone concentration rank is not selected, but a route with the maximum difference from the optimal route is selected from candidate routes, the difference between the two routes is calculated by utilizing the sum of squares of the node IDs on the routes, such as formula (11), the route with the maximum difference from the optimal route is found to be used as a candidate, the information can be transmitted with a high probability after the optimal route fails, and the effect of the candidate route can also be ensured because an pheromone concentration threshold T is set before, and the final destination node returns a route response RREP (route reply) packet to the two route transmission routes, quickly transmits the collected route information back, and updates a route decision table of each node in time.

DIFF＝C(R1id-R2id)² (11)

In addition, in the neighbor table maintained by each node, there are not only the ID of the node, the address, the ID of the destination node, the address and the pheromone concentration on the path, as shown in the formulas (6) and (7), the pheromone concentration is volatilized with time, if the path is not used for a long time, the path disappears in the neighbor table until the pheromone concentration is volatilized to be 0; if the route is used, the concentration of the pheromone is restored to the initial value and is volatilized again, so that the routing timeliness can be ensured, and the maintenance of useless routing is reduced.

3 route maintenance

(1) Path fracture detection

The routes being used are often disrupted due to the mobility of the Ad Hoc. The node judges the state of the link by periodically broadcasting the HELLO message, if the node does not receive the HELLO corresponding message for 3 times continuously, the node considers that the link is disconnected, deletes the routing information of the link, and informs the adjacent node and the corresponding upstream node to delete the routing information which can not be reached by the destination node due to the disconnection of the link.

(2) Reconstruction after path fracture

When the algorithm detects that the node on the maintained path has link interruption, firstly caching the data packet, checking whether other routes to the destination node exist, and if so, selecting the next hop of the maximum pheromone for forwarding; and if not, sending an error message to the source node for route reconstruction.

Claims (1)

1. The method for routing the ant colony of the space-adjacent-air vehicle network is characterized by comprising the following steps:

(1) firstly, determining a transmission region R according to a source node S and a destination node D, when a node receives a route request packet RREQ, firstly judging whether the node is in the R, if not, discarding, and if so, carrying out the next step;

(2) judging whether the current node and the previous node are aerostat nodes or unmanned aerial vehicle nodes, if one node is not a ground node, multiplying loss coefficients to obtain path loss, specifically, judging whether the current node and the previous node are unmanned aerial vehicles or aerostat nodes, if the current node and the previous node are the unmanned aerial vehicle nodes or the aerostat nodes, setting the path loss coefficient to be a1, if the unmanned aerial vehicle nodes are the unmanned aerial vehicle nodes, setting the path loss to be a2, setting the ground node path loss coefficient to be a3, paying attention that a1 is smaller than a2 is smaller than a3, and multiplying the current node and the previous node according to the types of two adjacent nodes to obtain the path loss of the section;

if the node is a common land node, judging the relationship between the node and the previous node, wherein the three types are divided into three types: in-view distance LOS, one corner distance NLOS1, two corner distances NLOS 2;

among the three relationships, the path LOSs, i.e., PL, of LOS is the lowest, and is only related to the wavelength and the distance between two points;

where λ is the signal wavelength and d is the distance between two nodes;

in NLOS1, the signal received by the destination node is the sum of the reflections and diffractions by the building;

where PLD is the sum of path loss diffraction and PLR is the sum of reflections;

when the relation between the two nodes is NLOS2, the signal needs to pass through multiple bends, needs to pass through multiple reflections R, DD, RD and DR interweaving to obtain a path loss result;

wherein PLDD is the path loss multiple diffraction sum, PLR is the emission sum, PLRD is the reflection diffraction sum, PLD is the diffraction reflection sum;

recording;

(3) when the information is transmitted to a destination node D, waiting for a period of time, then D has a plurality of paths from the same source node, paths which do not meet a threshold are eliminated, and then an optimal path needs to be selected from the reserved paths;

the method specifically comprises the following steps: setting an pheromone concentration threshold T at a destination node, wherein the concentration is greater than the threshold and can be used as a candidate path, and then summarizing and selecting the candidate path to transmit with high pheromone concentration; when the backup route is selected, instead of selecting the route with the second pheromone concentration rank, the route with the largest difference from the optimal route is selected from the candidate routes, the difference between the two routes is calculated by using the sum of squares of the node IDs on the route as shown in formula (11), and the route with the largest difference from the optimal route is found as a candidate:

DIFF＝∑(R1id-R2id)² (11)

(4) and selecting a standby path, finding a path with the maximum difference value by using the difference value between the standby path and the optimal path, returning routing reply information according to the optimal path and the standby path, returning the routing reply information to the source node, updating a routing table by the source node, and recording a new path.

Images