CN111615060A - A regional multicast method based on bus trajectory and positioning information - Google Patents

Abstract

The invention discloses a regional group broadcasting method based on bus track and positioning information. The invention introduces bus track information. In the first stage, a track tree and an encounter model of bus nodes are established first, and then bus nodes are calculated according to the encounter map. For the message forwarding capability _cp of the target area, select a node with higher message forwarding capability to forward the message to the destination area. The second stage uses the stability index to estimate the stability of the two vehicles, establishes a vehicle set on each street in the destination area, and achieves the purpose of multicast by establishing and maintaining the vehicle set. The simulation is carried out on the joint platform of the experimental platform SUMO, OMNET++ and Veins, and the analysis of the experimental results shows that: with the increase of the number of vehicles, the algorithm can reduce the transmission overhead of the entire network while maintaining a high packet delivery rate, and achieve the expected Target.

Description

A regional multicast method based on bus trajectory and positioning information

technical field

The invention belongs to the technical field of vehicle node communication in the Internet of Vehicles, and relates to a regional group broadcasting method based on bus track and positioning information.

Background technique

The Internet of Vehicles is based on the intra-vehicle network, the inter-vehicle network and the in-vehicle mobile Internet. According to the agreed communication protocol and data exchange standard, wireless communication is carried out between the vehicle-X (X: vehicle, road, pedestrian and the Internet, etc.). It is an integrated network that can realize intelligent traffic management, intelligent dynamic information service and intelligent vehicle control, and is a typical application of Internet of Things technology in the field of transportation systems. The Internet of Vehicles is a technology with great challenges, which can support many applications of safety information and entertainment information. With the development of V2X communication, the Internet of Vehicles can realize various functions including automatic driving, traffic information sharing, and vehicle safety. . Compared with 5G and other communication methods, the Internet of Vehicles has huge advantages in hardware deployment and cost. In the Internet of Vehicles, roadside units can also be used to form fog nodes for fog computing, reducing the burden of cloud computing, so the Internet of Vehicles can become a smart city. It is a data exchange platform and plays a huge role in many fields.

In the Internet of Vehicles, geocasting is a special kind of geographical multicast (geocast), which transmits messages from a source point to all nodes in a given target geographical area. This is the basic service content for a variety of in-vehicle network applications. Regional multicast can form regional broadcasts to transmit commercial information, advertisements, etc. related to geographic locations, or to send emergency messages to designated areas. In order to reduce the risk of car accidents Risk and avoid traffic congestion, many applications in the Internet of Vehicles are designed to transmit messages in a specific geographic area through geo-multicasting. Geographic multicast has many applications with entertainment information. It can form regional broadcasts to deliver geographically related commercials, etc., for example, for vehicles arriving in a certain geographical area to send information such as parking lot locations and vacant parking spaces within the range or the distribution of location-based commercials (Starbucks to Send coupons around). In addition, sending emergency messages to designated areas is also an important application, such as sending warning messages to vehicles in the surrounding area in the event of a traffic accident.

Geo-multicasting is well studied in WSN. The regional multicast algorithm of WSN can be divided into protocols based on data transmission, protocols based on route creation and protocols based on geographic location.

However, none of the IoV technologies in the prior art consider the problems of vehicle mobility and vehicle trajectory in the urban IoV, resulting in low vehicle information accuracy, high information transmission cost and low efficiency.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a regional group broadcasting method based on bus trajectory and positioning information, which solves the problem in the prior art that vehicle mobility and vehicle trajectory in the urban Internet of Vehicles are not considered, resulting in low accuracy of vehicle information, and low accuracy of information. The problem of high transmission cost and low efficiency.

The technical scheme adopted by the present invention is a method for regional group broadcasting based on bus track and positioning information, comprising the following steps:

Step 1. Establish an encounter model between buses in urban traffic through the analysis of historical bus trajectories, use the overlap of routes between buses and the probability of encounter between different time periods, and use the trajectory information of vehicles to reduce the variability of vehicle mobility. Deterministic to improve packet delivery;

Step 2. In the first stage of regional multicast, the vehicle trajectories are effectively used according to the local encounters between vehicles, and the data packets are forwarded to the network with higher node forwarding capability through the bus encounter model established in the step 1. vehicle;

Step 3. In the second stage of regional multicast, use the stability index to estimate the stability of the two vehicle nodes, establish a vehicle set on each street in the destination area, and use the establishment and maintenance mechanism of the vehicle set to ensure that the When a vehicle in the destination area needs to deliver a message, it can deliver the message with one hop.

The feature of the present invention also lies in:

E(v)包含两种边，

为单向边，单向边表示车辆a在其轨迹上从顶点

行驶到顶点

双向边e代表可能相遇的车辆a和车辆b之间的轨迹且

假设v已经获得一组车辆轨迹ψ(v)，对于每个T_a∈ψ(v),

The process of establishing the bus encounter model in step 1 is: summarize all bus node encounters into a geographic encounter graph G(v)={X(v), E(v)}, which is maintained by the vehicle node v. , where X(v) represents the vertex set and E(v) represents the edge set, and the geographic encounter graph maintains all trajectories known to vehicle node v and all possible encounters between geographic locations on those trajectories; where, define a vehicle v The absolute moment to reach a given position I is

E(v) contains two kinds of edges,

is a one-way edge, and a one-way edge means that vehicle a moves from the vertex on its trajectory

drive to the top

Bidirectional edge e represents the trajectory between vehicle a and vehicle b that may meet and

Assuming that v has obtained a set of vehicle trajectories ψ(v), for each T _a ∈ ψ(v),

When analyzing the encounter pattern of vehicles, each track records the ID number of the intersection and the time when the vehicle node passes. In order to solve the time deviation problem of bus operation, it is assumed that the time for a bus to pass through a certain intersection is within a certain range. Fluctuate up and down, and this time fluctuation conforms to the normal distribution, assuming that the time for the bus to arrive at the intersection I is t, and the upper and lower limits of t are respectively set to t _l , t _h , so t∈[t _l , t _h ], a variable Following a normal distribution, then the probability density function is:

In the formula: μ—is the expectation of the normal distribution function,

σ—is the variance of the normal distribution function

For two vehicles whose trajectories intersect each other, the probability of encounter is judged by the proximity of their arrival times to the intersection of the trajectories. The encounter between buses is divided into the following three situations:

C到达路口服从

则相遇概率In the first case, two vehicles are on the same road section and traveling in the same direction. For example, bus A and bus C meet on the _r2 road section, assuming that A arrives at the intersection and obeys the

C arrive at the intersection and obey

the probability of encounter

In the formula: δ—is the time threshold, which is determined by the speed of the bus and the communication range

μ _A ,σ _A — is the expectation and variance of the time when bus A arrives at the intersection obeying a normal distribution

μ _B ,σ _B — is the expectation and variance of the time when bus B arrives at the intersection obeying a normal distribution;

到达2路口时刻为

公交车B到达1路口时刻为

到达2路口时刻为

其中

将另外两个时刻设置为到达的预期时刻，

和

的密度函数为：In the second case, the two vehicles are traveling in different directions on the same road section. For example, bus A and bus B meet on the _r4 road section, and the moment when bus A arrives at intersection 1 is:

The time to arrive at intersection 2 is

The time when bus B arrives at intersection 1 is

The time to arrive at intersection 2 is

in

Set the other two moments to the expected moments of arrival,

and

The density function of is:

服从正态分布的期望与方差，μ₂,σ₂—为公交车B到达该2路口时间

服从正态分布的期望与方差，In the formula: μ ₁ , σ ₁ — is the time when bus A arrives at the intersection 1

The expectation and variance obeying the normal distribution, μ ₂ ,σ ₂ — is the time for bus B to arrive at the 2 intersections

The expectation and variance of the normal distribution,

So the probability of encounter is:

服从正态分布的期望与方差，μ₂,σ₂—为公交车B到达该2路口时间

服从正态分布的期望与方差；In the formula: μ ₁ , σ ₁ — is the time when bus A arrives at the intersection 1

The expectation and variance obeying the normal distribution, μ ₂ ,σ ₂ — is the time for bus B to arrive at the 2 intersections

The expectation and variance of the normal distribution;

In the third case, two cars in different directions meet at the intersection, such as bus B and bus C meet at intersection I2, the probability of encounter is:

服从正态分布的期望与方差，μ_B,σ_B—为公交车B到达该2路口时间

服从正态分布的期望与方差。In the formula: δ—is the time threshold, which is determined by the speed of the bus and the communication range, and is smaller than the first case, μ _C , σ _C — is the time when the bus C arrives at the 2 intersections

Expectation and variance obeying normal distribution, μ _B , σ _B — is the time when bus B arrives at the 2 intersections

Expectations and variances from a normal distribution.

Step 2 specifically includes the following steps:

Step 2.1, first initialize the map and vehicle trajectory;

Step 2.2. Determine whether there is a bus node in the neighbor nodes of the source node. If so, establish a geographic encounter model according to step 1, and calculate the message forwarding capability of each node. If not, rely on ordinary vehicles to forward messages. The node selects the common vehicle node that is closest to the center of the destination area among the neighbor vehicle nodes;

Step 2.3: Calculate the message forwarding capability of the node, and select the node with the strongest message forwarding capability, that is, the maximum value of _cp to forward the message;

Step 2.4: Determine whether a node has reached the destination area, if yes, end the process, if not, continue to execute the step 2.2.

The process of calculating the message forwarding capability _cp of each node in step 2.2 is as follows:

The arrival of the vehicle trajectory to the destination area is divided into direct arrival and indirect arrival. Direct arrival means that the vehicle trajectory directly enters the destination area; indirect arrival means that the vehicle meets other vehicles, and the trajectory of other vehicles reaches the target area; vehicle v ₁ The message forwarding capability on the destination area is defined as the probability that the coverage of its extended vehicle trajectory overlaps with the destination area, the vehicle v ₁ has multiple possible extended paths to reach the destination area, β _i represents within the destination area The i paths of , p(β _i ) is the probability that β _i is included in the reach of v ₁ , and the calculation formula of c _p is:

To calculate c _p , it is necessary to obtain the extended set of all paths that can reach the destination area Ω _v ={η _i |i=1,2...n}, where η _i represents each reachable extended path set, through the path η _i ∈Ω _v Calculate the probability p(β _i ) that β _i is included in the coverage of v ₁ .

Step 3 is implemented according to the following steps:

Step 3.1. Calculate the stability index of the street vehicle in the destination area, establish and maintain the vehicle set on the street;

Step 3.2: The vehicle in the vehicle concentration sends a regional broadcast packet message to other vehicles in the destination area.

Assuming in step 3.1 that vehicle j is a neighbor node of vehicle i and they are on the same street, the estimated stability index between vehicles j and i is calculated as follows:

In the formula: D _i,j — is the link maintenance distance between the two vehicles

—车辆i,j的矢量速度

—Vector velocity of vehicles i, j

If the vehicles are driving close, there are two cases where vehicles i and j are driving towards each other; vehicles i and j are driving in the same direction and the vehicle behind is faster, in both cases the link maintenance distance between the vehicles is :

D _i,j =R+d _i,j (8)

In the formula: R—is the communication range of the vehicle

d _i,j — is the distance between vehicles i,j

If the vehicles are driving separately, there are two cases, vehicles i and j are far away from each other; vehicles i and j are driving in the same direction, the vehicle ahead is faster, and the link maintenance distance between the vehicles is:

D _i,j =Rd _i,j (9)

In the formula: R—is the communication range of the vehicle

d _i,j — is the distance between vehicles i,j.

The specific process in step 3.2 is: in the Internet of Vehicles, due to the limitation of the street width, the broadcast only needs to select a neighbor node as the next relay node along the broadcast direction, assuming that _vi is successfully received in the street segment. The first vehicle of the message, _vi calculates the stability estimate index of each neighbor vehicle and selects the neighbor vehicle with the highest stability estimate index as the next vehicle set vehicle; then _vi forwards the message containing the selected neighbor node ID and the value to be sent broadcast message and set a waiting timer, if the selected neighbor node successfully receives the information, it repeats the selection process and forwards the message to the next selected vehicle set vehicle; if v _i does not receive its selected neighbor message from the node, it means that the neighbor has not successfully forwarded the message. When the waiting timer of vi _expires , vi _recalculates the stability estimation index, and re-selects the vehicle in the next vehicle set; if a vehicle in the vehicle set The node detects through the beacon message that a neighbor node in the set has left its communication range, and the link between the two vehicle nodes is broken, then the vehicle reselects the vehicle node with the highest stability in this direction to join the vehicle set, and then Send a message to notify newly added vehicles.

The beneficial effects of the present invention are as follows: the present invention introduces the trajectory information of the bus. In the first stage, the trajectory tree and the encounter model of the bus node are first established, and then the message forwarding ability of the bus node to the target area is calculated according to the encounter diagram, and the selection has higher The node with message forwarding capability forwards the message to the destination area; the second stage uses the stability index to estimate the stability of the two vehicles, and establishes a vehicle set on each street in the destination area. The purpose is to solve the problems existing in the prior art that the vehicle mobility and vehicle trajectory in the urban vehicle networking are not considered, resulting in low vehicle information accuracy, high information transmission cost and low efficiency.

Description of drawings

Fig. 1 is a kind of calculation diagram of node forwarding capability in a regional multicast method based on bus track and positioning information of the present invention;

Fig. 2 is a kind of encounter pattern diagram between vehicles in a regional group broadcasting method based on bus track and positioning information of the present invention;

Fig. 3 is a kind of bus encounter diagram in the regional group broadcasting method based on bus track and positioning information of the present invention

4 is a flow chart of a first-stage algorithm in a method for regional group broadcasting based on bus track and positioning information of the present invention;

Fig. 5 is a flow chart of vehicle set setting in a regional group broadcasting method based on bus track and positioning information of the present invention;

Fig. 6 is a vehicle set maintenance diagram in a regional multicast method based on bus track and positioning information of the present invention;

Fig. 7 is a kind of regional group broadcasting method based on bus track and positioning information of the present invention and the delivery rate comparison diagram of different vehicle numbers of other two algorithms;

8 is a comparison diagram of the transmission overhead of a regional group broadcasting method based on the bus track and positioning information of the present invention and the other two algorithms with different numbers of vehicles;

Fig. 9 is a kind of regional group broadcasting method based on bus track and positioning information of the present invention and the delivery rate comparison diagram of other two algorithms with different message generation rates;

10 is a comparison diagram of the transmission overhead of a regional multicast method based on the bus track and positioning information of the present invention and other two algorithms with different message generation rates;

FIG. 11 is a comparison diagram of the data packet transmission rate of a regional multicast method based on the bus trajectory and positioning information of the present invention and the other two algorithms with different vehicle numbers.

Detailed ways

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

A method for regional group broadcasting based on bus track and positioning information of the present invention comprises the following steps:

Step 1. Establish a bus encounter model: establish an encounter model between buses in urban traffic based on the historical trajectories of buses, and use the overlap of routes between buses and the probability of encounter between different time periods, which can be divided into weekly mode and Intra-week mode, which uses the vehicle's trajectory information to reduce the uncertainty of vehicle mobility to improve packet delivery;

Step 2. In the first stage of regional multicast, the vehicle trajectories are effectively used according to the local encounters between vehicles, and the data packets are forwarded to the network with higher node forwarding capability through the bus encounter model established in the step 1. vehicle;

Step 3. In the second stage of regional multicast, use the stability index to estimate the stability of the two vehicle nodes, establish a vehicle set on each street in the destination area, and use the establishment and maintenance mechanism of the vehicle set to ensure that the When a vehicle in the destination area needs to deliver a message, it can deliver the message with one hop.

E(v)包含两种边，

为单向边，单向边表示车辆a在其轨迹上从顶点

行驶到顶点

双向边e代表可能相遇的车辆a和车辆b之间的轨迹且

假设v已经获得一组车辆轨迹ψ(v)，对于每个T_a∈ψ(v),

The process of establishing the bus encounter model in step 1 is: summarize all bus node encounters into a geographic encounter graph G(v)={X(v), E(v)}, which is maintained by the vehicle node v. , where X(v) represents the vertex set and E(v) represents the edge set, and the geographic encounter graph maintains all trajectories known to vehicle node v and all possible encounters between geographic locations on those trajectories; where, define a vehicle v The absolute moment to reach a given position I is

E(v) contains two kinds of edges,

is a one-way edge, and a one-way edge means that vehicle a moves from the vertex on its trajectory

drive to the top

Bidirectional edge e represents the trajectory between vehicle a and vehicle b that may meet and

Assuming that v has obtained a set of vehicle trajectories ψ(v), for each T _a ∈ ψ(v),

When analyzing the encounter patterns of vehicles, each trajectory records the ID number of the intersection and the time when the vehicle node passes through, due to the driver's habits and other factors. Assuming that vehicle v has 3 tracks between <7:00-8:00>, it can be recorded as <T2, T4, T6>, T2=<(I1,7:00),(I2,7:15 )>,T4=<(I2,7:15),(I3,7:50)>,T6=<(I3,7:50),(I4,8:00)>, so that the trajectory tree of the node can be established . In order to solve the problem of time deviation of bus operation, it is assumed that the time of a bus passing through a certain intersection fluctuates up and down within a certain range, and this time fluctuation conforms to a normal distribution. The upper and lower limits of t are respectively set to t _l , t _h , so t∈[t _l , t _h ], a variable obeys the normal distribution, then the probability density function is:

In the formula: μ—is the expectation of the normal distribution function,

σ—is the variance of the normal distribution function

For two vehicles whose trajectories intersect each other, the probability of encounter is judged by the proximity of their arrival times to the intersection of the trajectories. The encounter between buses is divided into the following three situations:

C到达路口服从

则相遇概率In the first case, two vehicles are on the same road section and driving in the same direction, as shown in Figure 2. For example, bus A and bus C meet on the _r2 road section, assuming that A arrives at the intersection and obeys the

C arrive at the intersection and obey

the probability of encounter

In the formula: δ—is the time threshold, which is determined by the speed of the bus and the communication range

μ _A ,σ _A — is the expectation and variance of the time when bus A arrives at the intersection obeying a normal distribution

μ _B ,σ _B — is the expectation and variance of the time when bus B arrives at the intersection obeying a normal distribution;

到达2路口时刻为

公交车B到达1路口时刻为

到达2路口时刻为

其中

将另外两个时刻设置为到达的预期时刻，

和

的密度函数为：In the second case, two vehicles are traveling in different directions on the same road section. For example, bus A and bus B meet on the _r4 road section. As shown in Figure 3, the moment when bus A arrives at intersection 1 is:

The time to arrive at intersection 2 is

The time when bus B arrives at intersection 1 is

The time to arrive at intersection 2 is

in

Set the other two moments to the expected moments of arrival,

and

The density function of is:

服从正态分布的期望与方差，μ₂,σ₂—为公交车B到达该2路口时间

服从正态分布的期望与方差，In the formula: μ ₁ , σ ₁ — is the time when bus A arrives at the intersection 1

The expectation and variance obeying the normal distribution, μ ₂ ,σ ₂ — is the time for bus B to arrive at the 2 intersections

The expectation and variance of the normal distribution,

So the probability of encounter is:

服从正态分布的期望与方差，μ₂,σ₂—为公交车B到达该2路口时间

服从正态分布的期望与方差；In the formula: μ ₁ , σ ₁ — is the time when bus A arrives at the intersection 1

The expectation and variance obeying the normal distribution, μ ₂ ,σ ₂ — is the time for bus B to arrive at the 2 intersections

The expectation and variance of the normal distribution;

In the third case, two cars in different directions meet at the intersection, such as bus B and bus C meet at intersection I2, the probability of encounter is:

服从正态分布的期望与方差，μ_B,σ_B—为公交车B到达该2路口时间

服从正态分布的期望与方差。In the formula: δ—is the time threshold, which is determined by the speed of the bus and the communication range, and is smaller than the first case, μ _C , σ _C — is the time when the bus C arrives at the 2 intersections

Expectation and variance obeying normal distribution, μ _B , σ _B — is the time when bus B arrives at the 2 intersections

Expectations and variances from a normal distribution.

Step 2 specifically includes the following steps:

Step 2.1, first initialize the map and vehicle trajectory;

Step 2.2. Determine whether there is a bus node in the neighbor nodes of the source node. If so, establish a geographic encounter model according to step 1, and calculate the message forwarding capability of each node. If not, rely on ordinary vehicles to forward messages. The node selects the common vehicle node that is closest to the center of the destination area among the neighbor vehicle nodes;

Step 2.3: Calculate the message forwarding capability of the node, and select the node with the strongest message forwarding capability, that is, the maximum value of _cp to forward the message;

Step 2.4: Determine whether a node has reached the destination area, if yes, end the process, if not, continue to execute the step 2.2.

As shown in Figure 4, the process of calculating the message forwarding capability _cp of each node in step 2.2 is as follows:

The arrival of the vehicle trajectory to the destination area is divided into direct arrival and indirect arrival. Direct arrival means that the vehicle trajectory directly enters the destination area; indirect arrival means that the vehicle meets other vehicles, and the trajectory of other vehicles reaches the target area; vehicle v ₁ The message forwarding capability on the destination area is defined as the probability that the coverage of its extended vehicle trajectory overlaps with the destination area, the vehicle v ₁ has multiple possible extended paths to reach the destination area, β _i represents within the destination area The i paths of , p(β _i ) is the probability that β _i is included in the reach of v ₁ , and the calculation formula of c _p is:

To calculate c _p , it is necessary to obtain the extended set of all paths that can reach the destination area Ω _v ={η _i |i=1,2...n}, where η _i represents each reachable extended path set, through the path η _i ∈Ω _v Calculate the probability p(β _i ) that β _i is included in the coverage of v ₁ .

As shown in Figure ₁ , vehicle v1 has three possible extended paths to reach its destination area. We use β ₁ , β ₂ , and β ₃ to represent the three paths in the destination area, respectively. It is probabilistic whether or not part _βi is included in the reach _of v1. Let this probability be p(β _i ). Then, c _p can be calculated as:

Step 3 is implemented according to the following steps:

Step 3.1. Calculate the stability index of the street vehicle in the destination area, establish and maintain the vehicle set on the street;

Step 3.2: The vehicle in the vehicle concentration sends a regional broadcast packet message to other vehicles in the destination area.

Assuming in step 3.1 that vehicle j is a neighbor node of vehicle i and they are on the same street, the estimated stability index between vehicles j and i is calculated as follows:

In the formula: D _i,j — is the link maintenance distance between the two vehicles

—车辆i,j的矢量速度

—Vector velocity of vehicles i, j

The vehicle node stability indicator is used to measure the link stability between two vehicles, taking into account the duration of the link.

If the vehicles are driving close, there are two cases where vehicles i and j are driving towards each other; vehicles i and j are driving in the same direction and the vehicle behind is faster, in both cases the link maintenance distance between the vehicles is :

D _i,j =R+d _i,j (8)

In the formula: R—is the communication range of the vehicle

d _i,j — is the distance between vehicles i,j

If the vehicles are driving separately, there are two cases, vehicles i and j are far away from each other; vehicles i and j are driving in the same direction, the vehicle ahead is faster, and the link maintenance distance between the vehicles is:

D _i,j =Rd _i,j (9)

In the formula: R—is the communication range of the vehicle

d _i,j — is the distance between vehicles i,j.

As shown in Figure 5, the specific process in step 3.2 is: in the Internet of Vehicles, due to the limitation of the street width, the broadcast only needs to select a neighbor node as the next relay node along the broadcast direction, assuming that _vi is on the street The first vehicle in the segment that successfully receives the broadcast message, v _i calculates the stability estimation index of each neighbor vehicle and selects the neighbor vehicle with the highest stability estimation index as the next vehicle set vehicle; then v _i forwards the vehicle containing the selected Neighbor node ID and broadcast message to be sent and set a waiting timer, if the selected neighbor node successfully receives the message, it repeats the selection process and forwards the message to the next selected vehicle set vehicle; if v _i If the message of selecting a neighbor node is not received, it means that the neighbor has not successfully forwarded the message. When the waiting timer of vi _expires , vi _recalculates the stability estimation index and re-selects the vehicle of the next vehicle set; If a vehicle node in a vehicle set detects through a beacon message that a neighbor node in the set has left its communication range and the link between the two vehicle nodes is broken, the vehicle reselects the vehicle with the highest stability in that direction The node joins the vehicle set and then sends a message to notify the newly joined vehicle.

Since the vehicles in the vehicle network have high moving directions, the positions of the vehicles in the vehicle carrier set are constantly changing. As the vehicles move, the links between the vehicles in the carrier set may be disconnected. At this time, new vehicles need to be added to the carrier set. Typically, a vehicle in a vehicle carrier set has two neighbor nodes in the group and in different directions. If a vehicle node in the vehicle carrier set detects through a beacon message that a neighbor node in the set has left its communication range, the vehicle reselects the vehicle node with the highest stability in that direction to join the vehicle carrier set, and then sends a message Notify newly added vehicles. As shown in Figure 6, at the beginning, v _i and v _j are in the same vehicle carrier set, as time goes on, v _j is far away from the communication range of v _i , the link between the two nodes is broken, and v _i recalculates its Stability metrics of neighbor nodes and select a new vehicle v _k as the vehicle of the vehicle carrier set.

In order to verify the correctness and feasibility of the algorithm, the performance of the proposed method is simulated and verified by OMNeT++ and SUMO simulation software. SUMO software is open source and easy to import into the road network. This experiment selects the map of Xi'an area, a total of 5736 There are 2722 road intersections and 1200 vehicle nodes at most. Other simulation parameters are shown in Table 1.

Table 1 Movement trajectory parameters of bus vehicle nodes

content Numerical value Simulation area 4000*4000m Simulation time 43200s Vehicle Node Type Car,Bus Number of vehicle nodes 200-1200 vehicle speed 0m/s～30m/s Scene update time 0.1s Node cache 300M Communication range 200m network bandwidth 2M/s

In this simulation, each vehicle has the ability to generate messages, and the target area of the message is square and randomly selected on the entire road network. 100 simulations were performed for each parameter configuration and averaged. The comparison algorithm used in the first stage is the Epidemic routing algorithm. Whenever it encounters other vehicles that have not received the message, the vehicle will blindly forward the message. The main disadvantage of this algorithm is the high transmission overhead. NTR algorithm, NTR first builds its trajectory tree according to the trajectory data of each vehicle node. Using this trajectory tree, the future position of each vehicle is predicted and its contact probability with all other vehicles is derived. The contrasting algorithm used in the second stage is the LINGER algorithm, which distributes messages in the vehicle network while minimizing the protocol overhead. In the first stage of the algorithm, this paper evaluates the algorithm from two aspects: delivery rate: the ratio of the data packets received by the destination node to the number of data packets sent by the source node; transmission overhead: information in the network transmission process Network energy consumed for data and switching and packet forwarding. In the second stage of the algorithm we use the packet delivery rate as the main performance indicator. The packet transmission rate is defined as the ratio of the number of vehicles in the target area that received the message to the number of vehicles passing through the target area.

Figure 7 depicts the comparison chart of the data packet delivery rate of three different algorithms when the number of vehicles increases. Generally speaking, with the increase of the number of vehicles, the algorithms BTGR and NTR proposed in this paper both show higher delivery rates. However, the Epidemic routing algorithm shows a decreasing trend. This is because after the number of vehicle nodes increases, the flooding leads to a sharp increase in the number of data packets, and the data cache of each vehicle is a fixed 300M, which leads to network congestion and data cannot be forwarded. , the delivery rate dropped. In the case of less than 400 nodes, due to too few nodes, there will be fewer encounters between buses, resulting in fewer reachable links, so the delivery rate is slightly smaller than NTR.

Figure 8 depicts the relationship between the total routing overhead of network transmission and the number of vehicle nodes. In this figure, Epidemic's overhead increases explosively due to the infection method, which is much different from the other two methods. The method proposed by the present invention has a good effect in saving routing overhead, because the message is only broadcast in the target area, so the transmission overhead is reduced.

Figure 9 depicts the effect of different message generation rates on the delivery rate (the number of vehicles is 800), and it can be found that BTGR outperforms other methods when the message arrival rate is greater than two messages per hour. Epidemic has the best performance when network traffic is relatively slow (less than two messages per hour). This is because Epidemic actively replicates messages and fully utilizes network capacity, but as traffic continues to increase, Epidemic transmits less efficiently as network capacity is always limited.

Figure 10 describes the impact of different message generation rates on the transmission overhead, and it can be found that the transmission overhead of BTGR is always lower than other algorithms. As the message generation rate increases, the transmission overhead of all algorithms decreases. The main reasons are as follows, when the number of vehicles is stable, the nodes in total contact also remain stable. As more messages are generated, they compete for the limited resources of contact nodes. Unnecessary transfers are reduced, so the average transfer overhead is also reduced.

Figure 11 depicts the effect of different vehicle numbers on the data packet transmission rate in the second stage. When the vehicle passes through the street in the destination area, even if the first vehicle member in the vehicle set fails to send the message in time, members of other vehicle sets can Messages are passed to it as other vehicles drive on the street, increasing the packet transmission rate.

The present invention is a regional group broadcasting method based on bus trajectories and positioning information. Nodes with higher message forwarding capabilities forward messages to the destination area; in the second stage of regional multicast, the stability index is used to estimate the stability of the two vehicles, and a vehicle set is established on each street in the destination area. . Through the vehicle set, the vehicle passing through the destination area can deliver the message through one hop when it needs to deliver the message, thus avoiding the significant overhead caused by multi-hop broadcasting. Messages can be received from the set of subsequent vehicles it encounters, thus increasing the message reception rate. The algorithm can reduce the transmission overhead of the entire network while maintaining a high packet delivery rate and achieve the desired goal.

Claims (7)

1. A regional multicast method based on bus tracks and positioning information is characterized by comprising the following steps:

step 1, establishing an encounter model between buses in urban traffic through bus historical track analysis, and improving packet transfer by reducing uncertainty of vehicle mobility by using track information of the vehicles and by using line coincidence between the buses and encounter probability between different time periods;

step 2, in the first stage of the regional multicast, according to the local encounter between vehicles, effectively using vehicle tracks, and forwarding the data packet to the vehicle with higher node forwarding capability through the bus encounter model established in the step 1;

and 3, in the second stage of the regional multicast, estimating the stability of the two vehicle nodes by using the stability index, establishing a vehicle set on each street of the target region, and using a vehicle set establishing and maintaining mechanism to ensure that the vehicle passing through the target region can deliver the message by one hop when the message needs to be transmitted.

2. The regional multicast method based on the bus track and the positioning information as claimed in claim 1, wherein the process of establishing the bus encounter model in step 1 is as follows:generalizing all bus node encounters into a geographical encounter graph g (v) { x (v), e (v) }, maintained by vehicle nodes v, where x (v) represents a set of vertices, e (v) represents a set of edges, the geographical encounter graph maintains all trajectories known to vehicle nodes v and all possible encounters between geographical locations on those trajectories; wherein an absolute time at which a vehicle v arrives at a given location I is defined as

E (v) comprises two types of edges,

is a one-way edge, which means that the vehicle a is on its trajectory from the vertex

Travel to the top

The bidirectional edge e represents the trajectory between the vehicles a and b that may meet and r_i ^a∈T_a,

Assume that v has obtained a set of vehicle trajectories ψ (v), for each T_a∈ψ(v),

When the meeting mode of the vehicles is analyzed, each track records the ID number of an intersection and the passing time of vehicle nodes, in order to solve the time deviation problem of bus running, the time of a bus passing a certain intersection is assumed to fluctuate up and down within a certain range, the time fluctuation condition accords with normal distribution, the time of the bus reaching the intersection I is assumed to be t, and the upper limit and the lower limit of the t are respectively set as t_l,t_hTherefore t ∈ [ t_l,t_h]And one variable follows a normal distribution, then the probability density function is:

in the formula: μ -is the expectation of a normal distribution function,

σ -variance as a Normal distribution function

For two vehicles with mutually intersected tracks, the meeting probability is judged by the approaching degree of arrival time when the vehicles arrive at the track intersection, and the meeting between buses is divided into the following 3 cases:

in the first case, two vehicles are on the same road segment and travel in the same direction, e.g., bus A and bus C at r₂Meet on road segment, assume A arrives at crossing obeys

C compliance to crossing

Then the probability of encounter

In the formula: -as time threshold, determined by bus speed and communication range

μ_A,σ_AExpectation and variance obeying normal distribution for time of bus A reaching the intersection

μ_B,σ_B-expectations and variances obeying a normal distribution for the time of arrival of bus B at the intersection;

in the second case, two vehicles travel in different directions on the same road section, e.g. bus A and bus B at r₄Meet on the road section, the time when the bus A reaches the intersection 1 is

The time when the road reaches the intersection 2 is

The time when the bus B reaches the intersection 1 is

The time when the road reaches the intersection 2 is

Wherein

The other two times are set as the expected times of arrival,

and

the density function of (a) is:

in the formula: mu.s₁,σ₁Time for bus A to reach the 1 intersection

Expectation and variance, μ, obeying a normal distribution₂,σ₂Time for bus B to reach the 2-intersection

Subject to the expectation and variance of a normal distribution,

therefore, the encounter probability is:

in the formula: mu.s₁,σ₁Time for bus A to reach the 1 intersection

Expectation and variance, μ, obeying a normal distribution₂,σ₂Time for bus B to reach the 2-intersection

Expectation and variance obeying a normal distribution;

in the third case, two vehicles in different directions meet at the intersection, for example, the bus B and the bus C meet at the intersection I2, and the meeting probability is:

in the formula: -a time threshold, determined by the bus speed and the communication range, smaller than in the first case, mu_C,σ_CTime for bus C to reach the 2 crossing

Expectation and variance, μ, obeying a normal distribution_B,σ_BTime for bus B to reach the 2-intersection

Obeying the expectation and variance of a normal distribution.

3. The regional multicast method based on the bus track and the positioning information as claimed in claim 2, wherein the step 2 specifically comprises the following steps:

step 2.1, firstly initializing a map and a vehicle track;

step 2.2, judging whether a bus node exists in the neighbor nodes of the source node, if so, establishing a geographical encounter model according to the step 1, calculating the message forwarding capacity of each node, if not, forwarding the message by virtue of a common vehicle, and if so, selecting the common vehicle node closest to the target area center in the neighbor vehicle nodes;

step 2.3, calculating the message forwarding capability of the nodes, and selecting the node with the strongest message forwarding capability, namely c_pForwards the message;

and 2.4, judging whether a node reaches a target area, if so, ending the process, and if not, continuing to execute the step 2.2.

4. The regional multicast method based on bus track and positioning information as claimed in claim 3, wherein the message forwarding capability c of each node is calculated in step 2.2_pThe process comprises the following steps:

the arrival conditions of the vehicle track to the target area are divided into direct arrival and indirect arrival, wherein the direct arrival means that the vehicle track directly drives into the target area; the indirect arrival means that the vehicle passes through the meeting with other vehicles, and the tracks of the other vehicles arrive at the target area; vehicle v₁The message forwarding capability at the destination area is defined as the probability that its extended vehicle trajectory's coverage area overlaps with the destination area, vehicle v₁Having multiple possible extended paths to reach its destination area, β_iIndicating i paths, p (β), within the destination area_i) To be β_iIs contained in v₁Probability of in-reach of c_pThe calculation formula of (2) is as follows:

calculation of c_pIt is necessary to obtain a path expansion set omega for all possible destination areas_v＝{η_i1,2 … n, wherein η_iRepresents the set of extended paths that each can reach, via path η_i∈Ω_vCalculation β_iIs contained in v₁Is within the coverage of (β)_i)。

5. The regional multicast method based on the bus track and the positioning information as claimed in claim 1, wherein the step 3 is implemented according to the following steps:

step 3.1, calculating the stability index of the vehicles on the street of the target area, and establishing and maintaining a vehicle set on the street;

and 3.2, the vehicles in the vehicle set send regional broadcast grouping messages to other vehicles in the target area.

6. The regional multicast method based on bus track and location information as claimed in claim 5, wherein in step 3.1, it is assumed that the vehicle j is a neighbor node of the vehicle i and they are on the same street, and the stability estimation index between the vehicles j and i is calculated according to the following formula:

in the formula: d_i,j-maintaining a distance for a link between two vehicles

-vector velocity of vehicle i, j

If the vehicle is approaching, there are two situations, vehicle i and j are traveling towards each other; vehicles i and j travel in the same direction, with the rear vehicle at a faster speed, in both cases the link maintenance distance between the vehicles is:

D_i,j＝R+d_i,j(8)

in the formula: r-is the communication range of the vehicle

d_i,jAs distance between vehicles i, j

If the vehicles are driven separately, there are two situations where vehicles i and j are far away from each other; the vehicles i and j travel in the same direction, the vehicle in front is faster, and the link between the vehicles maintains the distance:

D_i,j＝R-d_i,j(9)

in the formula: r-is the communication range of the vehicle

d_i,jIs the distance between the vehicles i, j.

7. The regional multicast method based on the bus track and the positioning information as claimed in claim 5, wherein the specific process in the step 3.2 is as follows: in the internet of vehicles, due to the limitation of street width, the broadcast only needs to select one neighbor node as the next relay node in the broadcast direction, assuming v_iIs the first vehicle in the street segment that successfully receives the broadcast message, v_iCalculating a stability estimation index of each neighbor vehicle and selecting the neighbor vehicle with the highest stability estimation index as a next vehicle set vehicle; then v_iForwarding a broadcast message containing the selected neighbor node ID and to be sent and setting a wait timer, if the selected neighbor node successfully receives the message, it repeats the selection process and forwards the message to the next selected vehicle set vehicle; if v is_iIf the message of selecting the neighbor node is not received, the neighbor node is indicated to unsuccessfully forward the message, and when v is_iV after the wait timer of_iRecalculating the stability estimation index, and reselecting the vehicle of the next vehicle set; if one vehicle node in the vehicle set detects that one neighbor node in the set has left the communication range of the vehicle node through the beacon message, the link between the two vehicle nodes is broken, the vehicle reselects the vehicle node with the highest stability in the direction to join the vehicle set, and then sends a message to inform the newly joined vehicle.

Images