KR101601774B1 - Routing method for vanet - Google Patents

Abstract

A routing method for a VANET environment according to the present invention is characterized in that a node among nodes installed in each of the vehicles exchanges a beacon message with another node and measures link satisfaction between the nodes based on the exchanged beacon message ; And a step of selecting a node maximizing the link satisfaction and transmitting the message to the selected node when any one of nodes installed in the vehicles has received a message to be delivered .
The link satisfaction is determined by considering a link retention time considering distance and speed, direct reliability between nodes, indirect reliability received from neighboring nodes, and a reinforcement learning function that increases the probability that nodes with high route satisfaction are selected. .

Description

Routing Method for VANET Environment {ROUTING METHOD FOR VANET}

The present invention relates to VANET technology, and more particularly, to a routing method in a VANET environment.

Vehicular ad hoc networks are a core technology for ITS (Intelligent Transportation System) as a kind of mobile ad hoc network. The vehicle ad hoc network is provisionally configured through radio communication between vehicles without infrastructure, and the message is propagated through vehicles selected as message relay nodes. However, a vehicle ad hoc network is more likely to change network topology and node density than a mobile ad hoc network. Therefore, effective relay node selection technique is required to rapidly propagate messages through multi-hop broadcast.

VANET (Vehicular Ad-hoc Network), which is emerging as the core technology of Intelligent Transportation System (ITS) for intelligent vehicles, is a type of mobile ad hoc network based on inter-vehicle wireless communication. The VANET constitutes a temporary network through autonomous wireless communication between vehicles without the aid of infrastructure such as base stations around the roads. These VANETs can lead to smooth traffic flow control, driver safety and comfort, and improved fuel economy and performance of the vehicle.

However, the above-described vehicle network has problems such as frequent link disconnection and short link duration due to rapid mobility of the vehicle and frequent topology changes.

Also, there is a problem that the transmission success rate of the message is very low in places where the traffic is congested and the obstacles are large, such as in the city center.

Conventionally, a routing protocol specialized for VANET has been required.

Korean Patent Publication No. 1020090056070 Korean Patent Publication No. 1020110065257

An object of the present invention is to provide a routing method for a VANET environment in which a message is transmitted by selecting a node capable of maximizing link satisfaction through parameters defining a road environment in which a plurality of vehicles exist.

Another object of the present invention is to provide a routing method for a VANET environment in which a reinforcement learning function is updated according to route satisfaction to increase the probability that a vehicle included in a route with a high route satisfaction can be selected at the next routing.

Yet another object of the present invention is to provide a method and system for transmitting a message having a high priority to a message having a low contention window value and a message having a low contention window having a high contention window value when a message collision occurs, To provide a routing method for a VANET environment.

According to another aspect of the present invention, there is provided a probabilistic routing method based on time bounding game in a VANET environment according to the present invention, wherein a routing method for a VANET environment according to the present invention comprises: Exchanging a beacon message with the node, and measuring link satisfaction among the nodes based on the exchanged beacon message; And a step of selecting a node maximizing the link satisfaction and transmitting the message to the selected node when any one of the nodes installed in the vehicles receives the message to be delivered.

The link satisfaction is determined by considering a link retention time considering distance and speed, direct reliability between nodes, indirect reliability received from neighboring nodes, and a reinforcement learning function that increases the probability that nodes with high route satisfaction are selected. .

The present invention has an effect of increasing routing reliability by selecting a node that can maximize link satisfaction through parameters defining a road environment in which a plurality of vehicles exist, and transmitting the message.

The present invention also has the effect of increasing the probability that a vehicle included in a route with a high route satisfaction degree can be selected even in the next routing by updating the reinforcement learning function according to route satisfaction.

In the present invention, when a message collision occurs, a message having a higher priority has a lower contention window value and a message having a lower priority has a higher contention window value, so that a message having a higher priority is transmitted faster have.

1 is a block diagram of a VANET according to the present invention;
2 is a communication procedure diagram of a VANET according to the present invention.
3 is a flow chart of a link satisfaction detection method according to the present invention;
FIG. 4 is a flow chart of a node selection and message transmission method according to the present invention; FIG.
5 is a flow chart of a method for updating a reinforcement learning function according to the present invention.
FIG. 6 is a flow chart of a process according to the present invention. FIG.

The present invention increases the reliability of routing by selecting a node that can maximize link satisfaction through parameters defining the road environment in which a plurality of vehicles exist, and transmitting the message.

Further, the present invention updates the reinforcement learning function according to route satisfaction to increase the probability that a vehicle included in a route with a high route satisfaction can be selected even in the next routing.

In addition, the present invention includes a contention window control function for adjusting a contention window value, which is a time until a message is retransmitted in order to reduce a message collision rate. That is, the message has a basic contention window value for each priority, and when a message collision occurs, a message having a high priority according to the present invention has a low contention window value and a message having a low priority has a high contention window value Thereby allowing a message with a higher priority to be transmitted more quickly.

The routing method in the VANET environment according to the preferred embodiment of the present invention will be described in detail.

<Configuration of VANET>

First, a configuration example of a VANET applicable to a preferred embodiment of the present invention will be described with reference to FIG.

The VANET is composed of nodes (S, A, B, C, D) installed in each of a plurality of vehicles on the road. The plurality of nodes (S, A, B, C, D) perform communication with nodes of neighboring vehicles. In particular, when a node generates a message to be transmitted to a destination node as a source node, it transmits the message to a destination node through a linear path formed through the nodes of the adjacent vehicle.

In transmitting the message from the source node to the destination node, the plurality of nodes S, A, B, C, and D may transmit various linear paths S0-> S1-> ~ - SN or E1-> E2 ), And each node selects the next node to forward the message to form these linear paths.

In selecting a next node, the node selects a node that maximizes link satisfaction among its neighbor nodes and transmits a message. This link satisfaction is determined by taking into account the link maintenance time considering distance and speed, direct reliability between nodes, indirect reliability received from neighboring nodes, and reinforcement learning function which increases the probability of selecting a good path.

Each of the nodes S, A, B, C, and D calculates path satisfaction for the one or more paths when the message is received through one or more paths, The reinforcement learning function is updated so as to be weighted.

Each of the plurality of nodes S, A, B, C, and D analyzes priority of a collided message every time a message collides, and adjusts a contention window value do.

A routing method for a VANET environment according to a preferred embodiment of the present invention will be described in detail with reference to the flowcharts of FIGS. 2 to 6. FIG.

<Overall Data Transmission and Reception Process>

A data transmission / reception process according to a preferred embodiment of the present invention suitable for the VANET environment will be described with reference to FIG.

The nodes S, A, B, C, and D installed in each of the plurality of vehicles periodically exchange beacon messages with neighboring nodes while data transmission / reception is not performed, detect link satisfaction with the nodes, do.

The first node S which is one of the nodes S, A, B, C and D sends a message to the fifth node D through the second to fourth nodes A, B, The second to fourth nodes A, B, and C perform a process according to whether a message collision occurs when a message is received, select a next node according to the link satisfaction with neighboring nodes, And transmits the message and route information to the selected node (steps 100 to 112). The path information may include identification information on nodes to which the corresponding message is transmitted.

The fifth node D receiving the message from the first node S through the second to fourth nodes A, B and C receives and processes the message, The enhanced learning function is updated so as to increase the weight for the nodes belonging to the path with the highest path satisfaction, and the enhanced learning function update information is returned to the nodes belonging to the corresponding path in step 116.

The nodes receiving the enhanced learning function update information update the enhanced learning function accordingly (steps 118 to 124). The reinforcement learning function is utilized when link satisfaction is detected, which increases the probability that each node selects a node of the corresponding route at the next node selection.

<Link satisfaction calculation>

Now, a method of calculating link satisfaction according to a preferred embodiment of the present invention will be described with reference to FIG.

Each of the plurality of nodes S, A, B, C, and D installed in each of the plurality of vehicles is installed in neighboring vehicles existing within its wireless communication coverage every time a predetermined period arrives (step 200) In step 202, a beacon message is transmitted to the nodes and a beacon message is received from the nodes installed in the neighboring vehicles. Each of the plurality of nodes S, A, B, C, and D installed in the plurality of vehicles calculates and stores the link satisfaction based on the beacon message from the neighboring vehicle nodes in operation 204.

The link satisfaction calculation is based on Equation (1).

는 노드 i와 노드 j 사이의 링크 만족도이고,

는 두 차량의 상대속도이며,

는 노드 i와 노드 j 사이의 링크유지시간이고,

는 노드 i와 노드 j 사이의 최종 신뢰도이고,

는 노드 i와 노드 j 사이의 강화학습함수이다.
In Equation (1), i is an identification number for a node of one vehicle, j is identification information for a node of another vehicle,

Is the link satisfaction between node i and node j ,

Is the relative speed of the two vehicles,

Is the link retention time between node i and node j ,

Is the final confidence between node i and node j ,

Is a reinforcement learning function between node i and node j .

는 수학식 2에 따른다. The reinforcement learning function

Lt; / RTI &gt;

는 학습함수이고,

는 시점

에서의 학습함수이다. 또한

는 학습팩터이고,

는 차량 i와 j의 링크를 의미하며,

는 목적지까지 모든 차량의 링크 집합을 나타낸다.In Equation (2)

Is a learning function,

Point

Is a learning function. Also

Is a learning factor,

Denotes a link between vehicles i and j ,

Represents the set of links of all vehicles to the destination.

내에 존재하면

만큼 가중치를 부여함을 의미한다. Equation (2) is for updating the path satisfaction,

If present in

Of the weighted value.

는 수학식 3에 따라 산출된다. And the final reliability

Is calculated according to Equation (3).

상기 수학식 3에서,

는 직접 신뢰도에 대한 가중치이고,

는 측정시점이며,

는 측정시간이다.

는 차량 i와 차량 j간의 시점

에서 측정시간

동안 측정한 직접 신뢰도이고, 수학식 4에 따라 산출된다.

In Equation (3)

Is a weight for direct reliability,

Is the measurement point,

Is the measurement time.

Time point between the vehicle i and the vehicle j

Measurement time at

&Lt; / RTI &gt; and is calculated according to equation (4).

delete

는 과거 직접 신뢰도에 대한 가중치 값을 나타낸다.

는 신뢰도가 측정된 이산 시간의 수를 의미하며, l은 몇 번째 이산 시간인지를 나타낸다. 이러한 신뢰도 정보는 시간간격

동안 계산되고 이웃 차량들에게 주기적으로 전송하는 비콘에 포함되어 전파된다.

는 i가 j와 이산시간

동안 연결된 총 횟수를 나타내고

는 i가 j와 이산시간

동안 성공적으로 연결된 횟수를 나타낸다.

는 차량 i가 직전까지 j에 대해 측정한 과거 신뢰도를 나타낸다.In Equation (4)

Represents a weight value for past direct reliability.

Denotes the number of discrete time periods in which the reliability is measured, and l denotes the number of discrete time periods. Such reliability information may include time intervals

And is included in a beacon periodically transmitted to neighboring vehicles.

Where i is j and discrete time

Represents the total number of connections during

Where i is j and discrete time

The number of successful connections.

Represents the past reliability measured for j until just before the vehicle i .

는 차량 i와 차량 j간의 시점

에서 측정시간

동안 측정한 간접 신뢰도이며, 수학식 5에 따라 산출된다.remind

Time point between the vehicle i and the vehicle j

Measurement time at

, And is calculated according to Equation (5).

는 시점

에 시간 간격

동안 이웃 차량들

이 차량 j에 대해 경험한 직접신뢰도 값이며, 과거 직접 신뢰도에 대한 가중치 값을 나타내며,

는 차량 i가

에 대해 시점

에

동안 경험한 직접 신뢰도 값을 나타낸다. 또한

는 차량 i가

에 부여한 중요도를 나타내며,

로 구해진다.

는 차량 i가 차량 k에 대해 측정한 직접 신뢰도이다. 따라서

은 차량 i의 전체 이웃 차량에 대해 측정한 직접 신뢰도의 총 합 대비 차량 n의 직접 신뢰도가 차지하는 비율을 나타낸다.In Equation (5)

Point

Time interval

While neighboring vehicles

Is a direct reliability value experienced for vehicle j , and represents a weight value for past direct reliability,

The vehicle i

For point

on

And the direct reliability value experienced during. Also

The vehicle i

, &Lt; / RTI &gt;

.

Is the direct reliability measured by vehicle i for vehicle k . therefore

Represents the ratio of the direct reliability of the vehicle n to the total sum of the direct reliability measured for the entire neighbor vehicle of the vehicle i .

Here, the value of the weight according to the present invention is heuristically set through experiments.

은 수학식 6에 따라 산출된다. Then,

Is calculated according to Equation (6).

은 차량의 최대 전송범위이고,

은 어느 한 차량에 설치된 노드 i와 다른 차량에 설치된 다른 노드 j의 시점

에서의 거리이고,

및

는 어느 한 차량에 설치된 노드 i와 다른 차량에 설치된 다른 노드 j의 시점

에서의 상대속도이다. In Equation (6)

Is the maximum transmission range of the vehicle,

Node i installed in one vehicle and another node j installed in another vehicle

Lt; / RTI &gt;

And

Node i installed in one vehicle and another node j installed in another vehicle

Is the relative speed at.

The maximum transmission range is a predetermined distance, and the relative speed is a denominator of the equation for obtaining the link holding time.

<Routing>

As described above, the nodes of the vehicles that have periodically updated the link satisfaction, when a message to be delivered is received from a node, selects a next node for delivering the message to the destination node, and transmits the message to the selected node This process will be described with reference to FIG.

When any one of a plurality of nodes S, A, B, C, and D installed in a plurality of vehicles receives a message to be delivered from an external device in step 300, The node selecting the node that can maximize the link satisfaction, and combining the message with the path information including the nodes participating in the message transmission and the identification information of the selected node, and transmitting the message.

This message delivery process continues until the destination node notifies receipt of the message (step 304).

When the destination node notifies the message reception, the enhanced learning function is updated according to the enhanced learning function update information transmitted at the time of the notification (step 306).

In particular, the selection of a node that maximizes the link satisfaction among the neighbor nodes installed in the nearby vehicles is given by Equation (7).

는 차량에 설치된 노드 i까지의 경로 만족도 값을 의미한다.

는

에 속한 이웃 차량에 설치된 노드를 의미한다.

는 이웃 차량에 설치된 노드가 전송한 경로 만족도이고,

는

와

의 링크 만족도이다.

는 송신 차량에 설치된 노드부터 릴레이 차량에 설치된 노드 k까지 선택된 링크들의 집합이다.In Equation (7)

Means the path satisfaction value up to the node i installed in the vehicle.

The

Quot; node &quot;

Is the route satisfaction rate transmitted by the node installed in the neighboring vehicle,

The

Wow

Link satisfaction.

Is a set of links selected from a node installed in the transmission vehicle to a node k installed in the relay vehicle.

Here, the nodes installed in the vehicles calculate the link satisfaction with the node installed in the neighboring vehicle through the periodical beacon and transmit the route satisfaction which is the sum of the link satisfaction when the routing is started. That is, when the data is routed, the route satisfaction is transmitted to the node installed in the next routing vehicle.

Finally, the most suitable path is determined by Timed Nash Bargaining, which is shown in Equation (6).

는 링크 만족도의 총 합이 가장 높은 경로를 의미한다.

는 송신 차량으로부터 목적지 차량까지의 경로 중 i번째 경로이고,

는 설립된 라우팅 경로의 집합이다.

와

는 메시지 포워딩의 시작 시각과 종료 시각이다.In Equation (8)

Means the path with the highest total sum of link satisfaction.

Is the i- th path from the transmission vehicle to the destination vehicle,

Is a set of established routing paths.

Wow

Is the start time and end time of message forwarding.

Here, the nodes installed in the neighboring vehicles from the nodes installed in the transmission vehicle to the nodes installed in the destination vehicle confirm the mutual information through the periodical beacon. Therefore, when a routing path is formed through a beacon from a node installed in a transmission vehicle to a node installed in a destination vehicle, it is possible to know a route through which a message is forwarded through a beacon. The message forwarding start time and ending time are defined as constants in the experiment.

<Update the reinforcement learning function according to path satisfaction>

As described above, the node receiving the data updates the reinforcement learning function according to the path satisfaction, and this will be described with reference to FIG.

Each of the plurality of nodes S, A, B, C, and D installed in the plurality of vehicles receives a packet through one or more paths (step 400), calculates path satisfaction for one or more paths, Equation 7 is followed (step 402). If the path satisfaction for the one or more paths is calculated, the path with the highest path satisfaction is selected to update the reinforcement learning function.

<Competition Window Control>

The method of adjusting the contention window will now be described with reference to FIG.

If any one of the nodes S, A, B, C, and D installed in a plurality of vehicles has a packet collision (step 500), the priority of the collided packet is analyzed (502).

When the priority of the collided packet is analyzed, the node adjusts the contention window value in consideration of the packet priority sustain factor (step 504).

The contention window control scheme according to the present invention adjusts according to the priority of the message, which is given by Equation (9).

는 차량에 설치된 노드 i가 전송하는 메시지의 경쟁 윈도우이고,

는 가장 최근의 경쟁 윈도우 값을 의미하며,

는 경쟁 윈도우의 최대값을 나타낸다.

는 각 메시지의 우선순위에 따른 지속성 계수이다.
In Equation (9)

Is a contention window of a message transmitted by a node i installed in the vehicle,

Lt; / RTI &gt; means the most recent contention window value,

Represents the maximum value of the contention window.

Is the persistence factor according to the priority of each message.

S, A, B, C, D: nodes installed in each of the vehicles

Claims (7)

A routing method for a VANET environment,
Exchanging a beacon message with any one of nodes installed in each of the vehicles and measuring link satisfaction among the nodes based on the exchanged beacon message;
Selecting a node maximizing the link satisfaction and transmitting the message to the selected node when a message to be delivered is received; And
One of the nodes installed in each of the vehicles analyzes the priority of the collided data when data collision occurs and updates the contention window value in consideration of the priority constant of the data In addition,
Wherein the calculation of the contention window value is according to &lt; RTI ID = 0.0 &gt; (18). &Lt; / RTI &gt;
Equation 18

In Equation 18,

Is a contention window of a message transmitted by a node i installed in the vehicle,

Lt; / RTI &gt; means the most recent contention window value,

Represents the maximum value of the contention window.

Is the persistence factor according to the priority of each message. delete delete delete The method according to claim 1,
Wherein the link satisfaction between the nodes is calculated according to Equation (10) to Equation (15).
Equation 10
Link satisfaction

In Equation (10), i is an identification number for a node of one vehicle, j is identification information for a node of another vehicle,

Is the link satisfaction between node i and node j ,

Is the relative speed of the two vehicles,

Is the link retention time between node i and node j ,

Is the final confidence between node i and node j ,

Is a reinforcement learning function between node i and node j .
Equation 11
Reinforcement learning function

In Equation (11)

Is a learning function,

Point

Lt; RTI ID = 0.0 &gt;

Is a learning factor,

Denotes a link between vehicles i and j ,

Represents the set of links of all vehicles to the destination.
Equation 12
Final confidence

In Equation (3)

Is a weight for direct reliability,

Is the measurement point,

Is the measurement time,

Time point between the vehicle i and the vehicle j

Measurement time at

.
Equation 13
Direct reliability

In Equation (4)

Represents a weight value for past direct reliability,

Represents the number of discrete time periods for which the reliability is measured, l represents the number of discrete time periods,

Where i is j and discrete time

Represents the total number of connections during

Where i is j and discrete time

&Lt; / RTI &gt; represents the number of successfully connected &lt;

Represents the past reliability measured for j until immediately before vehicle i .
Equation 14
Indirect reliability

In Equation (14)

Point

Time interval

While neighboring vehicles

Is a direct reliability value experienced for vehicle j , and represents a weight value for past direct reliability,

The vehicle i

For point

on

, &Lt; / RTI &gt; and &lt; RTI ID =

The vehicle i

, &Lt; / RTI &gt;

Lt; / RTI &gt;

Is the direct reliability measured by vehicle i for vehicle k ,

Represents the ratio of the direct reliability of the vehicle n to the total sum of the direct reliability measured for the entire neighbor vehicle of the vehicle i .
Equation 15
Link Retention Time

In Equation (15)

Is the maximum transmission range of the vehicle,

Node i installed in one vehicle and another node j installed in another vehicle

Lt; / RTI &gt;

And

Node i installed in one vehicle and another node j installed in another vehicle

The relative speed is. 6. The method of claim 5,
Wherein the selection of a node that maximizes the link satisfaction is according to Equation (16) and Equation (17).
Equation 16

In Equation (16)

Denotes the path satisfaction value up to the node i installed in the vehicle,

The

Quot; node &quot; means a node installed in a neighboring vehicle belonging to &quot;

Is the route satisfaction rate transmitted by the node installed in the neighboring vehicle,

The

Wow

Link satisfaction,

Is a set of links selected from a node installed in a transmission vehicle to a node k installed in a relay vehicle.
Equation 17

In Equation 17,

Is the path with the highest total sum of link satisfaction,

Is the i- th path from the transmission vehicle to the destination vehicle,

Is a set of established routing paths,

Wow

Is the start time and end time of message forwarding. delete

Images