CN103298059A - Connectivity sensing routing method on basis of location prediction in vehicle ad hoc network - Google Patents

Abstract

The invention discloses a location prediction-based connectivity-aware routing method in a vehicle ad hoc network, which solves the problem in the prior art that path connectivity cannot be guaranteed when determining an optimal path. The specific steps are: firstly, use the method of regional flooding to find the path to reach the destination node; secondly, comprehensively consider the connection probability of the path and the forwarding delay of the data packet on the path, and choose the path with a higher connectivity probability and the smallest delay As the optimal path; again, forward the data packet according to the method based on location prediction. The connection performance of the path calculated by the present invention is superior, and the selected optimal path has a high connection probability and the shortest time delay, which can effectively avoid forwarding data packets to road sections that are easy to be interrupted, improve the delivery rate of data packets and reduce The transmission delay of the data packet is reduced; the location prediction of the neighbor node effectively reduces the possibility of forwarding the data packet to the failed neighbor node, and improves the delivery rate of the data packet.

Description

Connectivity-aware routing method based on location prediction in vehicular ad hoc network

technical field

The invention belongs to the technical field of communication, and further relates to a location prediction-based connectivity-aware routing method in Vehicle Ad Hoc Networks (VANETs). The present invention can select the path with the smallest delay by estimating the forwarding delay of the data packet on the premise of ensuring the connectivity of the path, and forward the data packet on the selected path according to the greedy algorithm based on position prediction, effectively improving the vehicle self-efficiency. performance of the organization's network.

Background technique

Vehicle Ad Hoc Networks (VANETs) is a special regional network that supports dynamic, random, and multi-hop topology applications in the transportation field. It is a new application of mobile Ad Hoc technology in the transportation field. The applications of VANs generally include security applications and information service applications. The former can reduce traffic accidents and improve traffic safety; the latter improves traffic efficiency by providing a variety of information services to vehicles on the road, meets passengers' comfort and entertainment requirements, and brings a lot of business opportunities. Therefore, the research and application of VAN has gradually become a research hotspot. In the VAM, the vehicle is generally regarded as a node. Since the vehicles in the VAN are basically in motion and moving at a relatively fast speed, if the speed and direction of the vehicle are not considered, the information of neighbor nodes will be inconsistent. Accurate, and then lose some good data packet forwarding nodes, and even cause data forwarding failure. Furthermore, in the urban environment, due to many reasons such as heavy traffic volume, vehicle driving is restricted by traffic lights and roads, and wireless signals are easily blocked by obstacles on the street, routing in VANs becomes more complicated. How to find a routing method suitable for the urban environment in combination with the characteristics of the VAN is an urgent technical problem to be solved.

The patent application of Beijing University of Posts and Telecommunications "for the greedy forwarding method of data packets in the vehicle-mounted Ad hoc network" (publication number CN101369982, application number CN200810224402.4) discloses a kind of data packet greediness in the vehicle-mounted Ad hoc network suitable for urban environment The forwarding method. This method first models the urban road environment as an undirected graph with weight values, then dynamically selects and updates the intersections in the data packet forwarding path, and then according to the predicted position of the vehicle node, based on the greedy forwarding strategy, the data The packet is forwarded. The disadvantage of this method is that, first of all, when selecting an intersection, only the influence of the number of vehicles on the road on data packet forwarding is considered, and the influence of data packet forwarding delay caused by uneven distribution of vehicles on information is not considered. The impact of the transmission causes the link to be interrupted during the data forwarding process, resulting in the failure of the data packet forwarding. Secondly, at the intersection, the data packet is forwarded to the node closest to the intersection as the next hop, without considering the relationship between the location of the neighbor node and the forwarding direction of the data packet, resulting in forwarding the data packet to a useless intersection node, which increases the routing Hop count and network delay.

Contents of the invention

The purpose of the present invention is to overcome the shortcomings of the above-mentioned prior art, and propose a connectivity-aware routing method based on location prediction in a VAN. Based on the predictability of the path connectivity probability in the vehicle ad hoc network in the urban environment, the present invention fully considers the impact of the forwarding delay on the data packet forwarding in the urban environment, adopts a method based on location prediction, and reduces Small data forwarding delay reduces routing overhead and achieves better forwarding performance.

The specific idea of the present invention to achieve the above purpose is: firstly, the method of regional flooding is used to find the intersection sequence that the path to the destination node will pass through; then, according to the number of vehicles on the selected path, the connection probability of the path is calculated. Under certain conditions, the forwarding delay of the data packet on the path is comprehensively considered, and the path with a higher connectivity probability and the smallest delay is selected as the optimal path; finally, on the selected optimal path, greedy forwarding based on location prediction Algorithms forward packets.

The concrete steps that the present invention realizes above-mentioned object are as follows:

(1) Initiate a routing request:

1a) All nodes in the vehicle ad hoc network obtain their own node information from their own GPS receivers;

2a) All nodes in the vehicle ad hoc network periodically exchange node information with neighbor nodes. After node information exchange, each node can obtain the node information of its neighbor nodes;

3a) The source node initiates a routing request according to the obtained node information, and searches for a path to the destination node.

(2) Query whether there is a destination node among the neighbor nodes:

The source node queries the obtained neighbor node information, if there is a destination node among the neighbor nodes, execute step (12); otherwise, execute step (3).

(3) Calculate the connectivity probability of the path:

3a) The source node obtains the location of the source-destination node and the location of the intersection from the GPS receiver, and determines the routing request area according to the coordinates of the two farthest intersections on the road section where the source-destination node is located, and performs a routing request for the intersection located in the request domain. Flooding, find the sequence of intersections that the path to the destination node must pass through;

3b) Using the dynamic density collection method to obtain the number of vehicles on each road section, and calculate the connectivity probability of the path to the destination node.

(4) Calculate the forwarding delay of the data packet:

The data packet forwarding delay of all road sections included in the path to the destination node is added to obtain the data packet forwarding delay of the path.

(5) Determine whether the difference in connectivity probability is greater than the preset threshold:

Determine whether the difference between the connectivity probability of the largest path and other paths is greater than the preset threshold, if the difference of the connectivity probability is greater than the preset threshold, select the path with the highest connectivity probability; otherwise, consider the path forwarding delay, in Among the paths whose connection probability difference is smaller than the preset threshold, the path with the smallest data packet forwarding delay is selected.

(6) Determine the optimal path:

In each path, the path with higher connectivity probability and smaller packet forwarding delay is selected as the optimal path.

(7) Query whether there is an intersection node among the neighbor nodes:

The node receiving the data packet queries the neighbor nodes, if there is an intersection node among the neighbor nodes, execute step (8), otherwise, execute step (9).

(8) Judging whether the current road section and the road section to be forwarded are in the same direction:

8a) compare the abscissas of the current intersection, the next intersection to be forwarded, and the three parameters of the node, if the abscissas of the three parameters are all the same, then perform step (9); otherwise, perform step (10);

8b) Compare the ordinates of the current intersection, the next intersection to be forwarded, and the node. If the ordinates of the three parameters are all the same, execute step (9); otherwise, execute step (10).

(9) Forward data packets to neighbor nodes:

Using a location prediction method to predict the current location of the neighbor node, forward the data packet to the neighbor node farthest from itself, and perform step (10).

(10) Forward the data packet to the junction node:

The location prediction method is used to predict the current location of the intersection node in the neighbor nodes, and forward the data packet to the intersection node closest to the next intersection.

(11) Determine whether the node is the destination node:

The node receiving the data packet compares the destination node identification number in the data packet with its own node identification number, if the two node identification numbers are the same, it is the destination node, and step (12) is performed; otherwise, step (7) is performed.

(12) Routing ends:

The source node forwards the data packet to the destination node, and the routing ends after the destination node receives the data packet forwarded by the source node.

Compared with the prior art, the present invention has the following advantages:

First, because the present invention adopts the method of calculating the path connectivity probability based on the number of vehicles, it overcomes the problem in the prior art that the path connectivity cannot be guaranteed when determining the optimal path, making the present invention more accurate in calculating the path communication quality. The path has a high probability of connectivity, which can effectively avoid forwarding data packets to road sections that are prone to interruption, improve the delivery rate of data packets and reduce the transmission delay of data packets.

Second, under the premise of considering the connectivity performance of the path, the present invention comprehensively considers the influence of the data packet forwarding delay on the path on the data packet forwarding, and avoids the problem of forwarding the data packet to a large number of vehicles due to uneven distribution of vehicles. The road section where communication is interrupted reduces the possibility of data packets encountering local optimal problems, effectively reducing the number of routing hops and network delay.

Third, after the present invention selects the optimal path, the location prediction method is used to predict the location information of the neighbor node, which effectively reduces the possibility of forwarding the data packet to the failed neighbor node and improves the delivery rate of the data packet; at the same time, by judging The direction of the current road section and the road section to be forwarded avoids forwarding data packets to unnecessary intersection nodes and reduces the number of routing hops.

Description of drawings

FIG. 1 is a schematic diagram of a scene in an embodiment of the present invention;

Fig. 2 is a flowchart of the present invention.

Detailed ways

The present invention will be further described below in conjunction with accompanying drawing 1 and accompanying drawing 2.

Referring to accompanying drawing 1, in the schematic diagram of the scene of the specific embodiment of the present invention, the strip area defined by the straight line represents the road, the dotted line represents dividing the road into two lanes, the path indicated by the black arrow represents the optimal path, and the white circle represents the packet forwarding Nodes, black circles S and D represent the source node and destination node respectively, A, B, C, E, F and G represent different data packet forwarding nodes, I ₁ , I ₂ ,..., I ₆ represent different cross intersection, I _i -I _j represent the road section determined by the intersection I _i and the intersection I _j . The source node S wants to forward a data packet to the destination node D, and the destination node D is located on the road section I ₃ -I ₆ determined by the intersection I ₃ and the intersection I ₆ .

Step 1, initiate a routing request.

All nodes in the vehicle ad hoc network obtain their own node information from their own GPS receivers.

All nodes in the vehicle ad hoc network periodically exchange node information with neighbor nodes. After node information exchange, each node can obtain the node information of its neighbor nodes.

According to the acquired node information, the source node initiates a routing request to search for a path to the destination node.

Neighboring nodes refer to any two neighbor nodes whose distance is less than the communication range and the nodes are not blocked by obstacles. The node information of neighbor nodes includes node identification number, speed, direction, link density, link length, geographic location, time stamp and destination node location information. Step 2, query whether there is a destination node in the neighbor nodes.

Step 2, query whether there is a destination node in the neighbor nodes.

The source node queries the obtained neighbor node information, if there is a destination node among the neighbor nodes, go to step 12; otherwise, go to step 3.

Step 3, calculate the connectivity probability of the path.

3a) The source node obtains the location of the source-destination node and the location of the intersection from the GPS receiver, and determines the routing request area according to the coordinates of the two farthest intersections on the road section where the source-destination node is located, and performs a routing request for the intersection located in the request domain. Flooding, find the sequence of intersections that the path to the destination node must pass through.

Determining the request area is done as follows:

In the first step, the abscissa and ordinate of the two farthest intersections on the road section where the source and destination nodes are located are added together and then divided by 2 to obtain the center position coordinates of the request area. Embodiments of the present invention are, with reference to Fig. 1, intersection I ₁ and intersection I ₆ are two intersections farthest apart on the road section where the source destination node is located, and the coordinates of intersection I ₁ are (1,1), The coordinates of the intersection I ₆ are (7, 9), respectively add the abscissa and ordinate of the two coordinates and divide by 2 to obtain the coordinates of the center position of the request area as (4, 5).

In the second step, respectively subtract the abscissa and ordinate of the two farthest intersections on the road section where the source and destination nodes are located, and then divide by 2 to obtain the distance vector of the radius of the requested area. Embodiments of the present invention are, with reference to Fig. 1, divide by 2 after subtracting the abscissa and ordinate of intersection I ₁ and intersection I ₆ , obtain the distance vector of request area radius as (-3,-4).

The third step is to take the modulus of the distance vector of the radius of the request area to obtain the radius of the request area. In an embodiment of the present invention, the distance vector (-3, -4) of the radius of the request area determined in the previous step is modulo taken to obtain a radius of 5 for the request area.

Flood all intersections in the request area to obtain all paths from source node S to destination node D. For the convenience of description, only the two paths in Figure 1 will be described in detail, assuming that the two paths selected are I ₁ -I ₂ -I ₃ -I ₆ and I ₁ -I ₄ -I ₅ -I ₆ -I ₃ .

3b) Using the dynamic density collection method to obtain the number of vehicles on each road section, and calculate the connectivity probability of the path to the destination node.

The number of vehicles on the road segment is calculated according to the following steps:

In the first step, when a node enters a new road segment, the number of neighbor nodes located in front of the current node among the neighbor nodes is obtained from the node position information provided by the neighbor nodes.

In the second step, add 1 to the number of neighbor nodes in front of the current node and store it in the data packet to be forwarded. With the forwarding of data packets on the road segment, the number of new neighbor nodes in front of the data packet forwarding node will be compared with the original Add the number of neighbor nodes in front of the data packet forwarding node, and use the obtained node number to update the number of neighbor nodes in front of the data packet forwarding node in the data packet.

The third step is to repeat the second step until the data packet encounters a new intersection, the number of vehicles on this road section is counted, and the number of neighbor nodes in the data packet located in front of the data packet forwarding node is the number of vehicles on this road section.

The embodiment of the present invention is, referring to Fig. 1, data packet forwarding node A enters a new section I ₄ I ₅ , the neighbor nodes in front of node A are only B and C, so the number of neighbor nodes in front of node A is 2, node A A adds 1 to the number of neighbor nodes and stores it in the data packet to be forwarded, and uses the obtained number of nodes and 3 to update the number of neighbor nodes in front of the data packet forwarding node; then, node C repeats the above steps until the data packet is forwarded Give node E, E is the node at the new intersection _I5 , after E encounters the new intersection, the number of vehicles on the road section _I4I5 is counted, and the number of neighbor nodes in front of the current node in _the data packet is 4. is the number _of vehicles on the road section _I4I5 .

The calculation of the connectivity probability of the path to the destination node is carried out according to the following steps:

In the first step, the road section is divided into 5-meter-long units, and each unit can accommodate at most one car. If there is a car in the unit, it means that the unit is not empty, otherwise it is an empty unit.

In the second step, the connectivity probability of the road segment is calculated according to the following formula:

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; \&Center\; Dot;</span>\underset{\mathrm{<span\; class="notranslate">\; l</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; \&CenterDot;</span>{<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; l</span>}}\frac{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}}{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; c</span>}{<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ]</span>}^{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; k</span>}}}{{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; k</span>}}}<span\; class="notranslate">\; )</span>$

表示空单元分布情况的种类数，表示将n个车辆随机分布在多车道道路上的非空单元时所有情况的种类数，

表示将n辆车随机分布在m个单元中时所有情况的种类数，

表示l个单元在m个单元中随机分布时所有情况的种类数，k表示空单元的个数，∑是求和符号，C是取组合数运算符，m表示路段上划分的单元数目，n表示路段上的车辆数目，b＝(m-k)×q，q表示路段车道数目，l表示路段上单元数目的可能取值，l的取值在范围[0，m]内，i表示空单元的个数，c[i]^s表示空单元的数目为i时，i个车辆同处于一个路段时可能发生的种类数。k的取值在范围[max(m-n，n₀)，max(m-n/q)]内，max表示在两个数中取较大的数，n₀表示空单元数的可能取值，

min表示在两个数中取较小的数，i的取值范围为[k-n₀，min{k，(m-k)·n₀}]，j与i的含义相同，但其取值范围不同，两者属于递推关系，c[i]¹＝1。Among them, P represents the connectivity probability of the link,

the number of species representing the distribution of empty cells, Indicates the number of types of all cases when n vehicles are randomly distributed in non-empty cells on multi-lane roads,

Indicates the number of types of all cases when n vehicles are randomly distributed in m units,

Indicates the number of types of all situations when l units are randomly distributed in m units, k indicates the number of empty units, ∑ is a summation symbol, C is an operator for combining numbers, m indicates the number of units divided on a road section, n Indicates the number of vehicles on the road section, b=(mk)×q, q indicates the number of lanes on the road section, l indicates the possible value of the number of units on the road section, the value of l is in the range [0, m], i indicates the number of empty units number, c[i] ^s represents the number of types that may occur when i vehicles are in the same road section when the number of empty units is i. The value of k is within the range [max(mn, n ₀ ), max(mn/q)], max means the larger number of the two numbers, n ₀ means the possible value of the number of empty cells,

min means to choose the smaller number among the two numbers, the value range of i is [kn ₀ , min{k, (mk) n ₀ }], j has the same meaning as i, but the value range is different, The two belong to the recurrence relation, c[i] ¹ =1.

In an embodiment of the present invention, with reference to Fig. 1, the connection probabilities _of road sections I ₁ -I ₂ , I ₂ -I ₃ and I ₃ -I ₆ in the selected path I ₁ -I 2 -I ₃ -I ₆ are calculated respectively, Then multiply the connectivity probabilities of each road section to obtain the connectivity probability of the path I ₁ -I ₂ -I ₃ -I ₆ is 0.8; the connectivity probability of the path I ₁ -I ₄ -I ₅ -I ₆ -I ₃ is the same method Calculated, its connectivity probability is 0.75.

Step 4, calculating the forwarding delay of the data packet.

The data packet forwarding delay of all road sections included in the path to the destination node is added to obtain the data packet forwarding delay of the path. The data packet forwarding delay of the link is calculated according to the following formula:

T _d =t _e -t _s

Among them, T _d is the forwarding delay of the data packet on the road segment, t _e is the forwarding end time of the data packet on the road segment, and t _s is the forwarding start time of the data packet on the road segment.

Embodiments of the present invention are, referring to Fig. 1, for the section I ₁ -I ₂ in the selected path I ₁ -I ₂ -I ₃ -I ₆ , the forwarding end time of the data packet is 7, and the forwarding start time is 5, Then the data packet forwarding delay on the road section I ₁ -I ₂ is 2, and the data packet forwarding delay on other road sections is calculated in the same way. Add the packet forwarding delays of the selected path I ₁ -I ₂ -I ₃ -I ₆ and the path I ₁ -I ₄ -I ₅ -I ₆ -I ₃ to obtain the path I ₁ - The packet forwarding delays of I ₂ -I ₃ -I ₆ and paths I ₁ -I ₄ -I ₅ -I ₆ -I ₃ are 10 and 8.

Step 5, judging whether the difference in connectivity probability is greater than a preset threshold.

Determine whether the difference between the connectivity probability of the largest path and other paths is greater than the preset threshold, if the difference of the connectivity probability is greater than the preset threshold, select the path with the highest connectivity probability; otherwise, consider the path forwarding delay, in Among the paths whose connection probability difference is smaller than the preset threshold, the path with the smallest data packet forwarding delay is selected.

In the embodiment of the present invention, referring to Fig. 1, the connection probability 0.8 of the selected path I ₁ -I ₂ -I ₃ -I ₆ is the same as the connection probability 0.75 of the path I ₁ -I ₄ -I ₅ -I ₆ -I ₃ If the value is less than 0.05, which is less than the preset threshold 0.1, the forwarding delay of the data packet on the path is considered, and the path I ₁ -I ₄ -I ₅ -I ₆ -I ₃ with the smallest forwarding delay of the data packet is selected. Although the connection probability of the path I ₁ -I ₂ -I ₃ -I ₆ is high, the delay of data packet forwarding on this path is relatively large due to the uneven distribution of vehicles on the road section, which is not the optimal path for data packet forwarding.

Step 6, determine the optimal path.

In each path, the path with higher connectivity probability and smaller packet forwarding delay is selected as the optimal path. After the optimal path is determined, a timer is started, and the path is deleted after the timer expires. In the embodiment of the present invention, referring to Fig. 1, the selected optimal path I ₁ -I ₄ -I ₅ -I ₆ -I ₃ has the minimum time delay under the premise of ensuring path connectivity, which reduces the data The packet forwarding delay increases the success rate of data packet forwarding.

Step 7, query whether there is an intersection node in the neighbor list.

The node that receives the data packet queries the neighbor nodes, if there is an intersection node in the neighbor list, go to step 8, otherwise go to step 9. Among them, the intersection node refers to the node whose distance to a certain intersection in the vehicle ad hoc network is less than a set value, and the node greater than the value does not belong to the intersection node. In an embodiment of the present invention, referring to FIG. 1 , among the neighbor nodes of the data packet forwarding node E located at the intersection _I5 , the intersection node F is included, and step 8 is performed.

Step 8, judging whether the current road section and the road section to be forwarded are in the same direction.

8a) Compare the abscissas of the current intersection, the next intersection to be forwarded, and the node. If the abscissas of the three parameters are the same, execute step 9; otherwise, execute step 10.

8b) Compare the vertical coordinates of the current intersection, the next intersection to be forwarded, and the node. If the vertical coordinates of the three parameters are the same, execute step 9; otherwise, execute step 10.

The embodiment of the present invention is, referring to Fig. 1, for the selected optimal path I ₁ -I ₄ -I ₅ -I ₆ -I ₃ , the current intersection I ₅ , the next intersection I ₆ to be forwarded, the node If the abscissas of the three parameters are the same, then the current road section I ₅ is in the same direction as the road section to be forwarded to I ₆ , and the data packet is forwarded to node E, and step 9 is performed.

Step 9, forward the data packet to the neighbor node.

Use the position prediction method to predict the current position of the neighbor node, forward the data packet to the neighbor node farthest from itself, and execute step 10. The position prediction method is:

(x _c , y _c )=(x _i , y _i )+(s·cosθ, s·sinθ)

Among them, (x _c , y _c ) is the position coordinate of the predicted neighbor node, x _c represents the abscissa of the predicted neighbor node position, y _c represents the ordinate of the predicted neighbor node position, ( _xi , y _i ) represents The position coordinates of the neighbor node, x _i represents the abscissa of the neighbor node position, y _i represents the ordinate of the neighbor node position, s represents the moving distance of the node, s=(t _c -T _b ) speed, t _c represents the current moment , T _b represents the moment when the node information was sent last time, speed represents the moving speed of the node at T _b time, cos represents the cosine symbol, θ represents the moving direction of the node, and sin represents the sine symbol.

In the embodiment of the present invention, referring to Fig. 1, the data packet forwarding node E adopts a position prediction algorithm to predict that among its neighbor nodes, the farthest from itself is node G, and the data packet forwarding node E forwards the data packet to node G , go to the next step. If the data packet forwarding node cannot find a suitable neighbor node, it will carry the data packet in a store-and-forward manner, and forward the data packet when it encounters a suitable neighbor node.

Step 10, forwarding the data packet to the intersection node.

The location prediction method is used to predict the current location of the intersection node in the neighbor nodes, and forward the data packet to the intersection node closest to the next intersection.

Step 11, judging whether the node is the destination node.

The node receiving the data packet compares the destination node identification number in the data packet with its own node identification number, if the two node identification numbers are the same, it is the destination node, and executes step 12; otherwise, executes step 7.

The node receiving the data packet compares the destination node identification number in the received data packet with its own node identification number, if the two node identification numbers are the same, then it is the destination node, and step 12 is performed; otherwise, it is not the destination node, Go to step 7. Embodiments of the present invention are, with reference to Fig. 1, after the data packet is forwarded to node G, G knows that he is not the destination node by comparing the destination node identification number in the received data packet with his own node identification number, and executes the steps 7.

Step 12, the routing ends.

The source node forwards the data packet to the destination node, and the routing ends after the destination node receives the data packet forwarded by the source node. The embodiment of the present invention is that, referring to FIG. 1 , the destination node D on the road section I ₃ -I ₆ receives the data packet forwarded by the source node S, and the route ends. If the destination node D does not receive the data packet forwarded from the source node S, it will re-initiate the routing request and perform the above steps until the destination node D receives the data packet forwarded from the source node S.

Claims (9)

1. the degree of communication perception method for routing of position-based prediction in the car self-organization network, its step comprises as follows:

(1) initiate route requests:

1a) node of all in the car self-organization network obtains the nodal information of self from the GPS receiver that self is equipped with;

2a) node of all in the car self-organization network periodically carries out the nodal information exchange with neighbor node, and after the nodal information exchange, each node can both obtain the nodal information of its neighbor node;

3a) source node is initiated route requests according to the nodal information that obtains, and searches the path that arrives destination node;

(2) whether destination node is arranged in the inquiry neighbor node:

Source node is inquired about the information of neighbor nodes that obtains, if destination node is arranged, execution in step (12) in the neighbor node; Otherwise, execution in step (3);

(3) the connection probability of calculating path:

3a) source node obtains source target node position and position, intersection from the GPS receiver, according on the source destination node highway section of living at a distance of the coordinate of farthest two intersections, determine the route requests zone, the intersection that is positioned at request domain is flooded the intersection sequence that finds the path that arrives destination node to pass through;

3b) adopt the dynamic density acquisition method, obtain the number of vehicles on each highway section, calculate the connection probability in the path that arrives destination node;

(4) the forwarding time delay of calculated data bag:

The packet that arrives all highway sections that comprise in the path of destination node is transmitted the time delay addition, and the packet that obtains the path is transmitted time delay;

(5) whether the difference that judge to be communicated with probability is greater than predetermined threshold value:

Whether the difference that the path of the maximum in the judgement connection probability is communicated with probability with other path is greater than predetermined threshold value, if the difference that is communicated with probability greater than predetermined threshold value, then selects to be communicated with the path of probability maximum; Otherwise, consider path forwarding time delay, in being communicated with the path of probability difference less than predetermined threshold value, select packet to transmit the path of time delay minimum;

(6) determine optimal path:

In each path, select to be communicated with the big and packet of probability transmit time delay less as optimal path;

(7) whether junction node is arranged in the inquiry neighbor node:

Receive that the node of packet inquires about neighbor node, if junction node is arranged in the neighbor node, execution in step (8), otherwise, execution in step (9);

(8) judge current highway section and whether in the same way to intend forwarding place highway section:

8a) current intersection, the next intersection of intend transmitting, the abscissa of three parameters of node are compared, if the abscissa of three parameters is all identical, execution in step (9) then; Otherwise, execution in step (10);

8b) current intersection, the next intersection of intend transmitting, the ordinate of three parameters of node are compared, if the ordinate of three parameters is all identical, execution in step (9) then; Otherwise, execution in step (10);

(9) transmit packet to neighbor node:

Adopt position predicting method, the current location of neighbor node is predicted, packet is forwarded to apart from self neighbor node farthest execution in step (10);

(10) transmit packet to junction node:

Adopt position predicting method, the current location of junction node in the neighbor node is predicted, packet is transmitted to the nearest junction node in the next intersection of distance;

(11) whether decision node is destination node:

The node of receiving packet number compares destination node identification number in the packet and the node identification of self, if two node identifications are number identical, then is destination node, execution in step (12); Otherwise, execution in step (7);

(12) route finishes:

Source node is forwarded to destination node with packet, and after destination node was received the packet of source node forwarding, route finished.

2. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1, it is characterized in that, the described neighbor node of step (1) refers to, any two distances are less than communication range, and do not stopped by barrier between node two neighbours' nodes each other.

3. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1, it is characterized in that the nodal information of the described neighbor node of step (1) comprises node identification number, destination node identification number, speed, direction, highway section number of vehicles, road section length, geographical position, timestamp and target node position information.

4. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1 is characterized in that step 3a) described definite request zone refers to that obtain center and the radius in request zone respectively, concrete steps are as follows:

The first step, respectively with on the source destination node highway section of living at a distance of the abscissa of farthest two intersections and ordinate addition again divided by 2, obtain asking the center position coordinates in zone;

Second step, respectively abscissa and the ordinate at a distance of farthest two intersections on the source destination node highway section of living in subtracted each other the back divided by 2, obtain asking the distance vector of zone radius;

In the 3rd step, to the distance vector delivery of request zone radius, obtain asking the radius in zone.

5. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1 is characterized in that step 3b) described highway section refers to the road between any two adjacent intersections.

6. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1 is characterized in that step 3b) described dynamic density acquisition method refers to:

When the first step, node enter a new highway section, from the node location information that neighbor node provides, obtain the neighbor node number that is positioned at present node the place ahead in the neighbor node;

Second step, the neighbor node number that will be arranged in present node the place ahead adds and stores the packet that will transmit after 1 into, forwarding along with packet on the highway section, to be positioned at new neighbor node number and original neighbor node number addition that is positioned at packet forward node the place ahead in packet forward node the place ahead, with the gained interstitial content and more the new data packets meta in the neighbor node number in packet forward node the place ahead;

The 3rd step repeated for second step, ran into new intersection until packet, and the number of vehicles statistics on this highway section finishes, and the neighbor node number that is positioned at packet forward node the place ahead in the packet is the number of vehicles on this highway section.

7. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1 is characterized in that step 3b) the connection method for calculating probability in described highway section is as follows:

The first step is divided into 5 meters isometric unit with the highway section, and each unit holds a car at the most, has car to represent that this unit is non-dummy cell in the unit, otherwise is dummy cell;

In second step, calculate the connection probability in highway section according to following formula:

$P=1-\underset{k}{\mathrm{\&Sigma;}}{C}_m^k\&CenterDot;\frac{C_b^n}{C_m^n}\&CenterDot;\underset{l}{\mathrm{\&Sigma;}}{C}_m^l\&CenterDot;{(-1)}^l\frac{C_b^n}{C_m^n}\&CenterDot;(1-\frac{\underset{i}{\mathrm{\&Sigma;}}c{\left[i\right]}^{m-k}}{C_m^k})$

Wherein, P represents the connection probability in highway section, and ∑ is the summation symbol, and C gets the number of combinations operator,

The species number of representing the distribution situation of the dummy cell that exists in the unit on the whole highway section, The species number of all situations when the expression vehicle is randomly dispersed in non-dummy cell on the multilane highway section,

The species number of all situations when expression is randomly dispersed in all vehicles on the highway section in the unit on the whole highway section,

The species number of all situations when representing random distribution in the unit of l unit on whole highway section, k represents the number of dummy cell, the k span is at [max (m-n, n ₀), max (m-n/q, n ₀)] in, max is illustrated in and gets bigger number in two numbers, and m represents the number of unit of dividing on the highway section, and n represents number of vehicles total on the highway section, n ₀The maximum number of dummy cell number continuously of expression, q represents the number of lanes on the highway section; L represents the possible value of number of unit on the highway section, and the l span is in [0, m]; B represents the number of non-dummy cell on the multilane highway section, b=(m-k) q; I represents number of vehicles, c[i] ^M-kRepresent when i vehicle is randomly dispersed on b the non-dummy cell may a situation arises species number, the i span is at [k-n ₀, min{k, (m-k) n ₀] in, min is illustrated in and gets less number in two numbers, C[i] ¹=1, j is identical with the implication of i, but the span difference, the j span is at [0, n ₀] in, both belong to recurrence relation.

8. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1 is characterized in that, the described highway section of step (4) packet forwarding time delay is calculated according to following formula:

T _d＝t _e-t _s

Wherein, T _dBe the forwarding time delay of packet on the highway section, t _eBe the forwarding finish time of packet on the highway section, t _sIt is the forwarding zero hour of packet on the highway section.

9. the degree of communication perception method for routing of position-based prediction in the car self-organization network according to claim 1 is characterized in that the described position predicting method of step (9) is as described below:

(x _c，y _c)＝(x _i，y _i)+(s·cosθ，s·sinθ)

Wherein, (x _c, y _c) be the position coordinates of the neighbor node of prediction, x _cThe abscissa of the neighbor node position of expression prediction, y _cThe ordinate of the neighbor node position of expression prediction, (x _i, y _i) expression neighbor node position coordinates, x _iThe abscissa of expression neighbor node position, y _iThe ordinate of expression neighbor node position, s represents the distance of node motion, s=(t _c-T _b) speed, t _cThe expression current time, T _bRepresent the moment of last sending node information, speed represents T _bThe translational speed of moment node, cos represents the cosine symbol, and θ represents the moving direction of node, and sin represents sinusoidal symbol.

Images