CN105763451A - Ant colony algorithm-based QoS fault-tolerant route selection method in Internet of Vehicles - Google Patents

Abstract

The invention discloses a QoS fault-tolerant routing selection method based on an ant colony algorithm in the Internet of Vehicles, and relates to the technical field of the Internet of Vehicles. With forward search function. In the algorithm, two ant-like agents are introduced, which are forwarding ants and reverse ants, which are used to evaluate the parameters that meet the QoS constraints. This method uses indicators such as bandwidth, hops and delay to calculate multiple disjoint paths to satisfy a given QoS constraint. By depositing pheromone in the link, the optimal path can be found, and at the same time, a fault-tolerant alternative path can be found after the node fails. Since network stability and QoS constraints are considered in the route selection process, it fully follows the QoS objectives. The present invention also finds that the algorithm has better performance in data packet transmission rate, throughput and routing overhead than other routing algorithms through comparison after simulation experiments.

Description

A QoS fault-tolerant routing selection method based on ant colony algorithm in Internet of Vehicles

technical field

The invention relates to the technical field of the Internet of Vehicles, in particular to a QoS fault-tolerant routing selection method based on an ant colony algorithm in the Internet of Vehicles.

Background technique

With the rapid development of society, vehicles have become an indispensable tool in people's lives. According to statistics from the Traffic Management Bureau of the Ministry of Public Security, by the end of 2014, the number of motor vehicles in my country reached 264 million, of which 154 million were automobiles, and motor vehicle drivers The number of people exceeded 300 million. With the sustained and rapid economic and social development, car ownership is still showing a rapid growth trend. On the one hand, the popularity of automobiles has brought enormous pressure on transportation and environmental protection, and on the other hand, the network formed between automobiles—the Internet of Vehicles has become increasingly important. The Internet of Vehicles will become the third largest Internet carrier after the Internet and the mobile Internet, and related academic research and applications have become current hot spots.

The Internet of Vehicles is based on the intra-vehicle network, the inter-vehicle network and the vehicle-mounted mobile Internet. According to the agreed communication protocol and data interaction standards, it uses radio frequency identification equipment, GPS and other access technologies to connect people, vehicles, roads and the environment. To achieve intelligent collaboration, wireless communication and data interaction, it is the application of traditional mobile ad hoc networks on traffic roads. Different from other self-organizing networks, the vehicle communication network (Vehicle Communication Network, VCN) is highly dynamic and distributed in the urban road system.

First of all, the movement of vehicle nodes is affected by road direction, road signs, traffic lights and traffic conditions, using dedicated short-range communication technology (DedicatedShort-RangeCommunication, DSRC) to communicate with other vehicle nodes (VehicletoVehicle, V2V) or roadside communication facilities (VehicletoRoadside , V2R) for communication; secondly, the vehicle nodes in the VCN build a network in a self-organizing manner, and the network scale is highly scalable and expansive; thirdly, unlike the nodes in wireless sensor networks and mobile terminal networks, vehicle nodes With powerful computing and storage resources, and unlimited usage. Therefore, the research on routing technology based on short-distance communication is the focus of scholars and the industry. How to ensure the accurate, efficient and safe transmission of data from the source vehicle to the terminal vehicle is the basis for the realization of other applications in VCN.

In the traditional mobile ad hoc network, the source routing protocol is the simplest routing protocol, which consists of two stages: route discovery and route maintenance. Once the source node sends a request, the neighbor node will perform route discovery and select an available path without loops according to certain rules. The distance vector routing protocol AODV adds the target sequence number field in the routing table, but due to the continuous change of the network topology, the next hop in the routing table entry may be inconsistent with the actual situation. AODV-BR and AODV-ABR respectively use the backup route and the adaptive backup route when the link fails, but the dynamic identification of the backup route will cause additional overhead. Routing algorithms that support QoS guarantees, such as AQOR, consider bandwidth and end-to-end delay when selecting routes, and use flooding strategies to find the required paths. In the routing algorithm based on game theory, data packet forwarding is only carried out between winning nodes considering different QoS parameters. Proxy nodes need to constantly compete with other nodes to obtain forwarding rights, and are also vulnerable to attacks and threats. The ACAR routing method is based on the known urban road network, and establishes a fixed multi-hop forwarding route between the initial node and the terminal node by obtaining traffic flow information in real time and broadcasting route discovery packets. The path generated by this method is fixed and cannot be used for The Internet of Vehicles whose topology changes frequently.

For the routing problem in VCN, there are already different routing methods, which are mainly divided into unicast, multicast, regional multicast and broadcast. Although these methods are able to transmit data between vehicle nodes, they do not consider QoS constraints and are vulnerable to attackers during the route establishment and data transmission stages.

Contents of the invention

In view of the above-mentioned defects or deficiencies, the purpose of the present invention is to provide a QoS fault-tolerant routing selection method based on an ant colony algorithm in the Internet of Vehicles, which can calculate the path priority, and select a path with the highest weight from all available paths. The optimal path is used to transmit data.

For achieving above object, technical scheme of the present invention is:

A QoS fault-tolerant routing selection method based on ant colony algorithm in the Internet of Vehicles, comprising the following steps:

1) The source node generates multiple paths for finding the destination node, and traverses the addresses of all nodes in the path; then, the source node detects the neighbor nodes and obtains the pheromone value table of the neighbor node, and the pheromone value table includes The path quality between the source node and the adjacent node;

2) the source node broadcasts a FANT message to all neighbor nodes whose path quality is higher than a critical value, and the FANT message includes source address, destination address, sequence number, hop count, bandwidth, start time, and path fields;

3) After the intermediate node receives the FANT message, it detects the path field in the FANT message: if the intermediate node address exists, the FANT information is discarded; if it does not exist, the address of the intermediate node is added to the FANT message to perform the FANT message Update and broadcast to stable neighbor nodes through the NHR value;

4) Repeat step 3) until the FANT message arrives at the destination node;

5) The destination node receives all FANT messages, calculates the QoS parameters according to the parameters in the FANT messages, obtains the path priority of each path, and generates a BANT message unicast to the source node according to the path priority that meets the user-specified QoS critical value requirement ; The BANT message includes destination address, source address, start time, received path field, and path priority;

6) The source node receives the BANT message, and selects the node with the highest pheromone value for data transmission according to the received BANT message of the intermediate node.

In the step 5), when the destination node receives all FANT messages, it needs to wait for a time T _k , and the T _k is an integer coefficient of all end-to-end delays De, and the BANT message is unicast to the source by popping the stack operation node.

In the step 5), during the unicast of the BANT message to the source node, the pheromone value passing through the node is updated, specifically:

When BANT reaches the intermediate node m from node n, the pheromone value in node m is updated by the following formula:

T _m,n =(1+T _m,n )P _(i)d

Among them, P _(i)d is the priority value of the i-th path to the destination node D, which meets the QoS requirement.

Said step 5) also includes step 5.1) after:

During the unicast BANT message process of the destination node, after receiving the BANT message, the intermediate node periodically broadcasts the hello message to update the routing table, so that the intermediate node knows its neighbors; if a relationship is established between node s and node t, then The initial pheromone value on the link between them is stored as 0.1, expressed as T _st =0.1, for each intermediate node receiving FANT, the pheromone value in the link shows a positive growth trend, expressed as T _st ＝ΔT _st +T _st , T _st ＝0.05; if the data is not transmitted within a limited time interval, then the pheromone value in the link will decay according to the coefficient μ, as shown in the following formula:

If the link between two nodes is lost, the pheromone value on the link becomes 0; when the BANT message reaches the intermediate node, if the position of the intermediate node changes, the BANT is deleted.

If the link between two nodes is lost, the pheromone value on the link becomes 0; when the BANT message reaches the intermediate node, if the position of the intermediate node changes, the BANT is deleted.

The user-specified QoS critical value is required to be measured by the fluctuation range of the critical value:

Use d _g , b _g , h _g to represent the delay, bandwidth and hop count respectively, and the calculation formula is as follows:

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; D.</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; D.</span>}\mathrm{<span\; class="notranslate">\; c</span>}}{\mathrm{<span\; class="notranslate">\; D.</span>}\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; B</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; B</span>}\mathrm{<span\; class="notranslate">\; c</span>}}{\mathrm{<span\; class="notranslate">\; B</span>}\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; h</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; h</span>}\mathrm{<span\; class="notranslate">\; c</span>}}{\mathrm{<span\; class="notranslate">\; h</span>}\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; ,</span>$

The priority calculation method of path k is Among them, P _k is the set of available paths from the source node to the destination node found in the route discovery stage, D _t and D _c respectively represent the maximum threshold and current value of the end-to-end delay on each path; B _t and B _c represent each path The maximum threshold and current value of the upper end-to-end bandwidth; H _t and H _c represent the maximum threshold and current value of the end-to-end hop count on each path, respectively.

Said step 6) also includes step 7) after periodically checking the priority of the selected path: if the path quality value of a certain node is lower than the critical value, it will send a message to its predecessor node to close the node, and then select an alternative The path is used for data transmission, and for the alternative path, its validity is also periodically checked.

Compared with prior art, the beneficial effects of the present invention are:

The invention proposes a QoS-supporting multi-path routing algorithm based on ant colony strategy in the vehicle communication network, which has forward search function. In the algorithm, two ant-like agents are introduced, which are forwarding ants and reverse ants, which are used to evaluate the parameters that meet the QoS constraints. This method uses indicators such as bandwidth, hops, and delays to calculate multiple disjoint paths to satisfy a given QoS constraint. By depositing pheromone in the link, the optimal path can be found, and at the same time, a fault-tolerant alternative path can be found after the node fails. Since network stability and QoS constraints are considered in the route selection process, it fully follows the QoS objectives. The present invention also finds that the algorithm has better performance in data packet transmission rate, throughput and routing overhead than other routing algorithms through comparison after simulation experiments.

Description of drawings

Fig. 1 is a flow chart structural representation of the present invention;

Figure 2 is a flow chart of route discovery when the source node receives FANT information;

Fig. 3 is the routing discovery flowchart when the intermediate node receives FANT information;

Fig. 4 is the flow chart of route discovery when destination node receives FANT information;

Fig. 5 is a flow chart of route selection and data transmission;

Fig. 6 is the relationship between the number of faulty nodes and the data packet transmission rate;

Figure 7 is the relationship between the number of failed nodes and throughput;

Figure 8 is the relationship between the number of faulty nodes and routing overhead;

Fig. 9 is the relationship between node moving speed and data packet transmission rate;

Fig. 10 is the relationship between node moving speed and throughput;

Figure 11 is the relationship between node moving speed and routing overhead.

detailed description

The present invention will be described in detail below in conjunction with the accompanying drawings.

Swarm-based intelligence algorithms, such as the ant colony algorithm, use biological techniques as heuristics to determine efficient paths. The self-learning ability of these algorithms is suitable for the dynamics in the mobile network, but the location-based ACO routing algorithm is only suitable for occasions where the network topology changes little. The ACO routing mechanism based on the greedy algorithm only selects an optimal path to the destination node, which has a high data packet transmission rate and throughput, but does not consider the packet loss rate. FTRA introduces the concept of worker ants, similar to control data packets, whose task is to identify wrong routes based on control information from existing effective routes. The protocol supports sending control packets actively or passively. DAR is another ant colony routing algorithm. Its goal is to minimize the computational complexity of routing, and use the hop-by-hop optimal strategy to forward FANT in order to find the best path to the destination node. However, the time spent by this algorithm is not the shortest. good. Most ACO routing algorithms identify and adopt all possible n paths, which reduces the performance of multi-path routing algorithms. After the number of routes increases to a certain extent, the routing table becomes gradually inflated due to storing a large amount of real-time information, and the network bandwidth and Node performance also degrades. Therefore, a fault-tolerant routing algorithm considering QoS constraints in vehicular communication networks is proposed.

Vehicle communication network has become a key technology of next-generation wireless network, which not only supports intelligent transportation system services, especially applications related to public safety, but also supports a large number of multimedia and data applications. As a part of the Internet, vehicles have the functions of mobile nodes, mobile backbone routers or mobile sensors.

The VCN infrastructure includes a two-level communication network. VANET belongs to the first level, which is composed of vehicle-to-vehicle unicast communication and vehicle-to-infrastructure multicast communication. The roadside network is also divided into two parts, respectively. Roadside access network and roadside backbone network composed of units. Different intelligent transportation applications and Internet programs can be run in the VCN, and each application has different requirements for QoS. For example, the security warning application should have the minimum end-to-end delay, because if the delay of the warning message received by the receiving end is too large, the Message just cannot prevent traffic accident from taking place in time. Similarly, packet loss rate and throughput are also two main QoS parameters in active safety applications.

Fault TolerantRoutingAlgorithmBased-onAntColonyPolicy (FTRA-BACP) based on ant colony algorithm is divided into three stages: route discovery stage, route selection stage and route maintenance stage. The corresponding ACO algorithm has six steps, namely: initialization, path selection, pheromone precipitation, credibility calculation, evaporation and negative reinforcement. In the path discovery stage, if the source node does not have a ready-made path available, it will use the pheromone value of the path for initialization. If the pheromone value is 0 or close to 0, it means that the path does not exist or fails and is not suitable for transmitting data. If the source node has a path available, it selects a route with a good state according to the path's pheromone content and time delay. There are two types of pheromone precipitation. In addition to updating the pheromone content of the path in the routing table of the source node, the ant also updates the pheromone in the nodes it traverses. After each worker ant reaches the target node, it traces back the path and updates the pheromone content of each node. The nodes on each path in the path set and the nodes not in the path set perform the evaporation operation, which reduces the pheromone content after the failure of the high-confidence path, but because the path still exists in the path set, the routes passing through the path will be interruption, it should be removed through negative reinforcement. The normal path contains a certain amount of pheromone. If the path fails due to malicious interruption, worker ants cannot deposit pheromone on the path, so they choose an alternative path for data transmission. The main goal of this routing mechanism is to find all available node-disjoint paths between source-destination nodes with the minimum routing overhead. The specific process is:

Example 1

As shown in Figure 1, the present invention provides a kind of QoS fault-tolerant route selection method based on ant colony algorithm in the Internet of Vehicles, comprising the following steps:

1) The source node generates multiple paths for finding the destination node, and traverses the addresses of all nodes in the path; then, the source node detects the neighbor nodes and obtains the pheromone value table of the neighbor node, and the pheromone value table includes The path quality between the source node and the adjacent node;

2) As shown in Figure 2, the source node broadcasts the FANT (forwarding ants) message to the neighbor nodes whose path quality is higher than the critical value to all neighbor nodes, and the FANT message includes source address, destination address, sequence number, hop count, bandwidth, Start time, and path fields; as shown in Table 1:

Table 1 FANT message structure

source address Destination address serial number hop count bandwidth Starting time path field

3) After the intermediate node receives the FANT message, it detects the path field in the FANT message: if the intermediate node address exists, the FANT information is discarded; if it does not exist, the address of the intermediate node is added to the FANT message to perform the FANT message Update and broadcast to stable neighbor nodes through the NHR value;

As shown in Figure 3, if the intermediate node receives the FANT message, it will check the availability of the address in the path field. If the address already exists, it means that there is a loop, and the FANT message will be discarded. Otherwise, the node will add its address to the FANT message and pass The NextHopReachability (NHR) value is broadcast to stable neighbor nodes. In this process, FANT information also records the transmission delay and effective carrying capacity of each link, the processing delay of each node and the total number of hops accessed.

4) Repeat step 3) until the FANT message arrives at the destination node;

5) As shown in Figure 4, the destination node receives all FANT messages, calculates the QoS parameters according to the parameters in the FANT messages, obtains the path priority of each path, and generates BANT according to the path priority that meets the user-specified QoS critical value requirement (Reverse ants) message unicast to source node; Described BANT message comprises destination address, source address, start time, the path field that receives, and path priority, as shown in table 1:

Table 1 BANT message structure

Destination address source address Starting time received path field path priority

After the FANT message arrives at the target node, it uses QoS parameters to calculate the path priority at first, and these paths must meet the QoS critical value requirements specified by the user. Generate BANT messages based on path priority. The path field of the FANT message contains a large number of visiting nodes, and the destination node D needs to wait for T _k to receive all the FANTs, where T _k is an integer coefficient of all end-to-end delays De. BANT unicasts the message to the source node through the stack operation. The user-specified QoS critical value is required to be measured by the fluctuation range of the critical value:

Use d _g , b _g , h _g to represent the delay, bandwidth and hop count respectively, and the calculation formula is as follows:

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; D.</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; D.</span>}\mathrm{<span\; class="notranslate">\; c</span>}}{\mathrm{<span\; class="notranslate">\; D.</span>}\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; B</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; B</span>}\mathrm{<span\; class="notranslate">\; c</span>}}{\mathrm{<span\; class="notranslate">\; B</span>}\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; g</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; h</span>}\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; h</span>}\mathrm{<span\; class="notranslate">\; c</span>}}{\mathrm{<span\; class="notranslate">\; h</span>}\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; ,</span>$

The priority calculation method of path k is Among them, P _k is the set of available paths from the source node to the destination node found in the route discovery stage, D _t and D _c respectively represent the maximum threshold and current value of the end-to-end delay on each path; B _t and B _c represent each path The maximum threshold and current value of the upper end-to-end bandwidth; H _t and H _c represent the maximum threshold and current value of the end-to-end hop count on each path, respectively.

In the step 5), during the unicast of the BANT message to the source node, the pheromone value passing through the node is updated, specifically:

When BANT reaches the intermediate node m from node n, the pheromone value in node m is updated by the following formula:

T _m,n =(1+T _m,n )P _(i)d

Among them, P _(i)d is the priority value of the i-th path to the destination node D, which meets the QoS requirement.

5.1), during the unicast BANT message process of the destination node, after the intermediate node receives the BANT message, it periodically broadcasts the hello message to update the routing table, so that the intermediate node knows its neighbors; relationship, the initial pheromone value on the link between them is stored as 0.1, expressed as T _st =0.1, for each intermediate node receiving FANT, the pheromone value in the link shows a positive growth trend , expressed as T _st =ΔT _st +T _st , T _st =0.05; if the data is not transmitted within a limited time interval, then the pheromone value in the link will decay according to the coefficient μ, as shown in the following formula:

If the link between two nodes is lost, the pheromone value on the link becomes 0; when the BANT message reaches the intermediate node, if the position of the intermediate node changes, the BANT is deleted.

6) The source node receives the BANT message, and selects the node with the highest pheromone value for data transmission according to the received BANT message of the intermediate node, as shown in FIG. 5 .

Preferably, the present invention also provides a preferred solution for implementing monitoring, specifically including:

After said step 6), step 7) is also included to periodically check the priority of the selected path: if the path quality value of a certain node is lower than the critical value, it will send a message to its predecessor node to close the node, and then select a backup The selected path is used for data transmission, and for the alternative path, its validity is also periodically checked.

The present invention also includes the route maintenance stage:

The route discovery phase gives the best available path for packet transmission. Due to the inherent learning properties of the ACO algorithm, the available pheromone value accumulated on the path during the data transmission process gradually increases. Less available bandwidth, and node energy consumption. To avoid this result, the priority of the selected path is checked periodically. As more and more nodes are added in the path, the path priority and merit value are automatically reduced. In addition, node mobility can also lead to link failure. If the merit value of a certain node is lower than the critical value, a message is sent to its predecessor node to shut down the node, and then an alternative path is selected for data transmission. For the alternative path, its validity is also periodically checked. The flow of the fault-tolerant QoS constrained routing algorithm is shown below.

(1) If the node is a source node, go to (2);

(2) Judging the pheromone value and NHR value, if it is greater than the critical value, turn to (3), otherwise turn to (4);

(3) broadcast FANT packet to the selected neighbor node of this node, turn (5);

(4) discard FANT packet, turn (5);

(5) judge whether all neighbor nodes have received FANT, if yes, turn to (6), otherwise turn to (12);

(6) If the neighbor node is the destination node, turn to (7);

(7) Wait for T _w time to receive all FANTs, turn to (8);

(8) find a path satisfying D _c < D _t , B _c < B _t , H _c < H _t , calculate p(i) of each path, and turn to (9);

(9) The node stored in the FANT path field is popped out of the stack, and turns to (10);

(10) generate BANT in the path that has satisfied the QoS requirement, turn (11);

(11) add the address of this node to path field and unicast BANT packet to source node, judge whether the node in the reverse path is source node simultaneously, if turn (19), otherwise turn (20);

(12) judge whether the neighbor node is an intermediate node, if so, turn to (13), otherwise turn to (6);

(13) collect the local information of node, turn (14);

(14) Check whether the node address is in the path field, if turn (15), otherwise turn (18);

(15) judge whether pheromone value and NHR value are greater than critical value, if turn (16), otherwise turn (17);

(16) broadcast FANT to the selected neighbor node and update the pheromone table, turn (12);

(17) Discard FANT, turn to (12);

(18) discard FANT to delete loop, turn (12);

(19) After the source node receives all the BANTs, it selects the path with the largest pheromone value and deletes the BANTs.

(20) If the node in the reverse path is an intermediate node, judge whether it is available, if it is turn (21), otherwise turn (22);

(21) update the routing pheromone table of each BANT;

(22) DON'T BANT.

Experimental simulation results:

The algorithm is verified in OMNET simulation software. In order to show the superiority of the algorithm in data packet transmission rate, throughput and routing overhead, the algorithm is compared with the most commonly used active routing algorithm AODV. The experimental parameters are set as follows: the radio wave range of a single node is 250m, the MAC layer protocol uses IEEE802.11, the traffic type is CBR, the data packet size is 60Bytes, the simulation area is 500m*500m, the number of nodes is 100, and the simulation time is 300s , the node movement mode is random movement, and the node movement speed is 0-50m/s.

Figure 6 shows the data packet transmission rate of the FTRA-BACP algorithm and the AODV algorithm when the number of faulty nodes increases. It can be seen from the figure that the data packet transmission rate of the FTRA-BACP algorithm is higher than that of the AODV algorithm, which shows that the FTRA-BACP algorithm Has good scalability. As the number of faulty nodes further increases, the AODV algorithm has the inherent properties of source-driven routing, and the performance of both algorithms decreases, but the FTRA-BACP algorithm is fault-tolerant, and its packet transmission rate is still higher than that of AODV. The throughput of the two algorithms is compared in Figure 7. The fault-tolerant path in the FTRA-BACP algorithm has fast convergence, and data routing mainly depends on the fault-tolerant path, so the throughput of the algorithm is still higher than that of the AODV algorithm. But as the number of faulty nodes increases, the throughput of both algorithms decreases, and it becomes increasingly difficult to find a fully trusted path from the source node. Due to the highly dynamic nature of vehicle nodes in the Internet of Vehicles, the possibility of link interruption also increases. After a link fails, frequent routing is required, resulting in a large amount of routing overhead. In the FTRA-BACP algorithm, the path discovery phase needs to use control packets such as FANT and BANT to periodically update the path. After a node fails, an alternative path must be constructed to transmit the data packet to the destination node. Therefore, the routing overhead of this algorithm is high. Based on the AODV algorithm, as shown in Figure 8. Figures 9 to 11 show the comparison of the two algorithms in terms of data packet transmission rate, throughput, and routing overhead as the moving speed of the vehicle node increases. Overall, as the moving speed of the vehicle node increases, the data Packet transfer rate and throughput are decreasing while routing overhead is gradually increasing.

The invention proposes a QoS-supporting multi-path routing algorithm based on ant colony strategy in the vehicle communication network. This method uses indicators such as bandwidth, hop count and delay to calculate multiple disjoint paths between source and destination nodes to satisfy given QoS constraints. By depositing pheromone in the link, the optimal path can be found, and at the same time, a fault-tolerant alternative path can be found after the node fails. Since network stability and QoS constraints are considered in the route selection process, it fully follows the QoS objectives. The simulation experiment is carried out in Omnet. Through comparison, it is found that this algorithm has better performance than other routing algorithms in terms of data packet transmission rate, throughput and routing overhead.

For those skilled in the art, it is obvious that the above-mentioned specific examples are only preferred solutions of the present invention, so those skilled in the art may make improvements and changes to some parts of the present invention, which still reflect the present invention. The principle of the present invention is still the object of the present invention, and all belong to the protection scope of the present invention.

Claims (6)

1. based on the QoS Fault-tolerant routing method of ant group algorithm in a car networking, it is characterised in that comprise the following steps:

1) source node generates the mulitpath being used for finding destination node and all addresss of node in traverse path；Then, source node detection neighbor node, obtain the pheromone value table of adjacent node, described pheromone value table includes the path quality between source node and adjacent node；

2) source node broadcasts FANT message to all neighbor node path qualities higher than the neighbor node of marginal value, and described FANT message includes source address, destination address, serial number, jumping figure, bandwidth, time started and path field；

3) after intermediate node receives FANT message, the path field in detection FANT message: if this intermediate node addresses exists, then abandon FANT information；If it does not exist, then the address of this intermediate node is added in FANT message, carry out FANT information updating, and be broadcast to stable neighbor node by NHR value；

4) step 3 is repeated), until FANT message arrives destination node；

5) destination node receives all FANT message, according to parameter in FANT message, carries out qos parameter calculating, it is thus achieved that the heat source in each path power, and generates BANT message unicast to source node according to meeting user and specify the heat source power of QoS critical values mandate；Described BANT message includes destination address, source address, time started, the path field of reception and heat source power；

6) source node receives BANT message and the BANT message according to the intermediate node received, and selects the node having the highest pheromone value to be used for carrying out data transmission.

2. based on the QoS Fault-tolerant routing method of ant group algorithm in car according to claim 1 networking, it is characterised in that described step 5) in, when destination node receives all FANT message, it is necessary to waiting time T_k, described T_kBeing the integer coefficient of all end-to-end time delay De, BANT message passes through Pop operations by message unicast to source node.

3. based on the QoS Fault-tolerant routing method of ant group algorithm in the car networking according to claims 1, it is characterised in that described step 5) in, the pheromone value through node, in source node process, is updated by BANT message unicast, particularly as follows:

When BANT arrives intermediate node m from node n, the pheromone value in node m is updated by following formula:

T_{M, n}=(1+T_{M, n})P_(i)d

Wherein, P_(i)dBeing the priority valve of the i-th paths to destination node D, it meets QoS demand.

4. based on the QoS Fault-tolerant routing method of ant group algorithm in the car networking according to claims 1, it is characterised in that described step 5) also include step 5.1 afterwards):

In destination node clean culture BANT message process, after intermediate node receives BANT message, periodic broadcast hello message updates routing table, so that this intermediate node knows the neighbours of oneself；If establishing relation between node s and node t, then between them, the initial information element value on link is just stored as 0.1, is expressed as T_st=0.1, for each intermediate node receiving FANT, the pheromone value in link presents positive growth trend, is expressed as T_st=Δ T_st+T_st, T_st=0.05；If data are not transmission in limited interval, then the pheromone value in link just decays according to coefficient μ, is shown below:

If the loss of link between two nodes, then the pheromone value on link becomes 0；After BANT message arrives intermediate node, if intermediary locations changes, then BANT is then deleted.

5. based on the QoS Fault-tolerant routing method of ant group algorithm in car according to claim 1 networking, it is characterised in that described user specifies QoS critical values mandate to be weighed by the fluctuating margin of marginal value:

Use d_g, b_g, h_gRepresenting time delay, bandwidth and jumping figure respectively, computing formula is as follows:

$d_g=\frac{Dt-Dc}{Dt}*100,b_g=\frac{Bt-Bc}{Bt}*100,h_g=\frac{Ht-Hc}{Ht}*100,$

The priority computational methods of path k areWherein P_kBe the route discovery stage find source node to destination node can path collection, D_t、D_cRepresent max-thresholds and the currency of end-to-end time delay on every paths respectively；B_t、B_cRepresent max-thresholds and the currency of end-to-end bandwidth on every paths；H_t、H_cRepresent max-thresholds and the currency of end-to-end jumping figure on every paths respectively.

6. based on the QoS Fault-tolerant routing method of ant group algorithm in car according to claim 1 networking, it is characterized in that, described step 6) after also include step 7) priority in path selected by periodic test: if the path quality value of a certain node is lower than marginal value, just send message to its forerunner's node to be closed by node, then alternative path is selected to carry out data transmission, for alternative path, its effectiveness of same periodic test.