DATA-AWARE ROUTING METHOD AND SYSTEM FOR AD HOC WIRELESS VEHICULAR NETWORK, STORAGE MEDIUM AND DEVICE

Abstract

According to a source node and a destination node of each data packet p in a given data packet set required to be transmitted by the wireless vehicular network, the joint scheduling based wireless vehicular network routing algorithm determines overall transmission performance of the wireless vehicular network and a transmission latency and transmission cost of the data packets, and determines an optimal transmission strategy. A multi-order Markov chain is used to model position change processes of vehicle nodes, and a next moment and several moments in the future are predicted and estimated under the condition that positions at previous several moments are given. On the basis of position actual values and predicted estimated values of the vehicle nodes, the optimal transmission strategy is combined to achieve data routing in the wireless vehicular network. The data-aware routing method is mainly used for data communication of a vehicular ad hoc network.

Claims

1. A data-aware routing method for an ad hoc wireless vehicular network, comprising: for the wireless vehicular network, carrying out data routing in the wireless vehicular network on a basis of a joint scheduling based wireless vehicular network routing algorithm; the joint scheduling based wireless vehicular network routing algorithm comprising: the wireless vehicular network needing to transmit a given data packet set, the given data packet set being recorded as Φ, a source node of each data packet p being recorded as δ(p), and a destination node of each data packet p being recorded as ψ(p); p having no subscript being used for representing the data packet, and p.sub.i( ) having a node subscript being used for representing a geographic position; for a certain data packet p, a copy set of all the data packets in the wireless vehicular network being recorded as θ(p), and θ(p) being called as a data packet group; when the data packets are subjected to one-time wireless transmission, a size of the data packet group being increased by 1; overall transmission performance of the wireless vehicular network being a function of transmission performance of a single data packet, and a transmission success rate ρ.sub.p of the single data packet being as follows:
ρ.sub.p=f.sub.Y(δ(p),ψ(p),{T.sub.n}) (4), {Tn} representing a motion track set of all the nodes, and f.sub.γ(⋅) representing a transmission success rate function; a transmission latency σ.sub.p of the data packet p being as follows:
σ.sub.p(τ)=τ+Γ.sub.γ(δ(p),ψ(p),{T.sub.n}) (5) Γ.sub.γ( ) representing a transmission latency function; transmission cost custom-character of the data packet p being as follows:
=|ϑ(p)| (6) |θ(p)| representing capacity of the data packet group θ(p); an optimal transmission strategy being as follows: maximizing the transmission success rate, minimizing the transmission latency and minimizing network cost:
maxΣ.sub.p∈Φ custom-character [ρ.sub.p] (7)
minΣ.sub.p∈Φ[σ.sub.p] (8)
minΣ.sub.p∈Φ[] (9) [•] representing an expectation; and network transmission efficiency being as follows:
Σ.sub.p∈Φ[ρ.sub.p]/Σ.sub.p∈Φ[] (10) using a multi-order Markov chain to model position change processes of vehicle nodes, and predicting and estimating a next moment and several moments in the future under a condition that positions at previous several moments are given; and on a basis of position actual values and predicted estimated values of the vehicle nodes, combining the optimal transmission strategy to achieve data routing in the wireless vehicular network.

2. The data-aware routing method for the ad hoc wireless vehicular network according to claim 1, wherein a wireless vehicular network model and a crowd sensing model corresponding to the wireless vehicular network are as follows: the wireless vehicular network model is constructed on a basis of an undirected graph; a geographic position of a vehicle node n at a moment τ is represented as p.sub.n(τ), and a motion track of the node from a moment zero to the moment τ is discretized:
T.sub.n= custom-character p.sub.n(0),p.sub.n(1), . . . p.sub.n(τ) τ representing time after discretization; a distance between two nodes i and j at the moment τ is represented as d.sub.ij(τ); all links capable of data transmission in the current wireless vehicular network are represented as
L(τ)={l.sub.i,j|d.sub.i,j(τ)≤R;∀i,j∈N} l.sub.i,j representing a link between the nodes i and j, and R representing a link distance threshold; and the crowd sensing model is constructed: a sensing data function obtained by a vehicle i is as follows: Δ(t,p.sub.i(t),i), pi(t) representing a corresponding geographic position of the vehicle i at a moment t.

3. The data-aware routing method for the ad hoc wireless vehicular network according to claim 2, wherein the wireless vehicular network model and the crowd sensing model corresponding to the wireless vehicular network are as follows: the undirected graph of the wireless vehicular network model is G=(N, E), N being a set of vertices, each vertex representing a vehicle node, E being a set of edges, ∀e∈E, e.sub.n′=((i,j), c(t) and d(t)) being an edge between vertices i and j, and representing communication between the two nodes, c(t) representing contact of the nodes i and j at a moment c(t), and d(t) representing a contact duration.

4. The data-aware routing method for the ad hoc wireless vehicular network according to claim 3, wherein the link distance threshold R is 400 meters.

5. The data-aware routing method for the ad hoc wireless vehicular network according to claim 1, wherein a process of using the multi-order Markov chain to model the position change processes of the vehicle nodes comprises: dividing an entire position space corresponding to the vehicle nodes into Q grids, the entire position space being represented as S:
S={s.sub.0,s.sub.1, . . . ,s.sub.Q−1|s.sub.i″∩s.sub.j″=Ø} (12) s.sub.0, s.sub.1, . . . , s.sub.Q−1 representing position spaces corresponding to the grids in the entire position space, and s.sub.i″ and s.sub.j″ representing position spaces corresponding to the grids in the entire position space respectively; at a certain moment, taking a certain value in S as a position of the vehicle i, and the certain value being recorded as S.sub.i; determining space-time correlation of vehicle motion by entropy and conditional entropy of a position random variable S.sub.i: for the vehicle i, assuming that the position of the vehicle i at L times is observed, a position sequence of the vehicle being represented as: T.sub.i=<s.sub.0, s.sub.1, . . . , s.sub.L□1>; and assuming that the vehicle i appears for o.sub.j″ times at the position s.sub.j″ in the sequence, marginal entropy of Si being as follows: $\begin{matrix} H (S_{i}) = {.Math.}_{j^{″} = 0}^{Q - 1} (o_{j^{″}} / L) \times \log_{2} \frac{1}{o_{j^{″}} / L} & (13) \end{matrix}$ the conditional entropy of S.sub.i under a condition that a position variable S.sub.i.sup.1, at a previous moment is given being as follows:
H(S.sub.i|S.sub.i.sup.1)=H(S.sub.i,S.sub.i.sup.1)−H(S.sub.i) (14), and entropy of a joint position random variable being as follows: $\begin{matrix} H (S_{i}, S_{i}^{1}) = {.Math.}_{j^{″} = 1}^{Q - 1} \frac{o_{j^{″} - 1, j^{″}}}{L - 1} \times \log_{2} \frac{1}{o_{j^{″} - 1, j^{″}} / (L - 1)} & (15) \end{matrix}$ o.sub.j″□1,j″ representing a number of occurrences of the vehicle in positions s.sub.j″□1 and s.sub.j″ in the sequence; on a basis of a same method, obtaining conditional entropy of given position variables at previous K moments:
H(S.sub.i|S.sub.i.sup.1,S.sub.i.sup.2, . . . S.sub.i.sup.K) (16); and predicting and estimating positions of the vehicle nodes on a basis of the multi-order Markov chain.

6. The data-aware routing method for the ad hoc wireless vehicular network according to claim 5, wherein the entire position space corresponding to the vehicle nodes is divided into the Q grids having a grid size of 200 m*200 m.

7. A data-aware routing system for the ad hoc wireless vehicular network, used for executing the data-aware routing method for the ad hoc wireless vehicular network of claim 1.

8. A storage medium, storing at least one instruction, wherein the at least one instruction is loaded and executed by a processor, to implement the data-aware routing method for the ad hoc wireless vehicular network of claim 1.

9. A device, comprising a processor and a memory, wherein the memory stores at least one instruction, and the at least one instruction is loaded and executed by the processor, to implement the data-aware routing method for the ad hoc wireless vehicular network of claim 1.

10. The data-aware routing method for the ad hoc wireless vehicular network according to claim 2, wherein a process of using the multi-order Markov chain to model the position change processes of the vehicle nodes comprises: dividing an entire position space corresponding to the vehicle nodes into Q grids, the entire position space being represented as S:
S={s.sub.0,s.sub.1, . . . ,s.sub.Q−1|s.sub.i″∩s.sub.j″=Ø} (12) s.sub.0, s.sub.1, . . . , s.sub.Q−1 representing position spaces corresponding to the grids in the entire position space, and s.sub.i″ and s.sub.j″ representing position spaces corresponding to the grids in the entire position space respectively; at a certain moment, taking a certain value in S as a position of the vehicle i, and the certain value being recorded as S.sub.i; determining space-time correlation of vehicle motion by entropy and conditional entropy of a position random variable S.sub.i: for the vehicle i, assuming that the position of the vehicle i at L times is observed, a position sequence of the vehicle being represented as: T.sub.i=<s.sub.0, s.sub.1, . . . , s.sub.L□1>; and assuming that the vehicle i appears for o.sub.j″ times at the position s.sub.j″ in the sequence, marginal entropy of Si being as follows: $\begin{matrix} H (S_{i}) = {.Math.}_{j^{″} = 0}^{Q - 1} (o_{j^{″}} / L) \times \log_{2} \frac{1}{o_{j^{″}} / L} & (13) \end{matrix}$ the conditional entropy of S.sub.i under a condition that a position variable S.sub.i.sup.1, at a previous moment is given being as follows:
H(S.sub.i|S.sub.i.sup.1)=H(S.sub.i,S.sub.i.sup.1)−H(S.sub.i) (14), and entropy of a joint position random variable being as follows: $\begin{matrix} H (S_{i}, S_{i}^{1}) = {.Math.}_{j^{″} = 1}^{Q - 1} \frac{o_{j^{″} - 1, j^{″}}}{L - 1} \times \log_{2} \frac{1}{o_{j^{″} - 1, j^{″}} / (L - 1)} & (15) \end{matrix}$ o.sub.j″□1,j″ representing a number of occurrences of the vehicle in positions s.sub.j″□1 and s.sub.j″ in the sequence; on a basis of a same method, obtaining conditional entropy of given position variables at previous K moments:
H(S.sub.i|S.sub.i.sup.1,S.sub.i.sup.2, . . . S.sub.i.sup.K) (16); and predicting and estimating positions of the vehicle nodes on a basis of the multi-order Markov chain.

11. The data-aware routing method for the ad hoc wireless vehicular network according to claim 3, wherein a process of using the multi-order Markov chain to model the position change processes of the vehicle nodes comprises: dividing an entire position space corresponding to the vehicle nodes into Q grids, the entire position space being represented as S:
S={s.sub.0,s.sub.1, . . . ,s.sub.Q−1|s.sub.i″∩s.sub.j″=Ø} (12) s.sub.0, s.sub.1, . . . , s.sub.Q−1 representing position spaces corresponding to the grids in the entire position space, and s.sub.i″ and s.sub.j″ representing position spaces corresponding to the grids in the entire position space respectively; at a certain moment, taking a certain value in S as a position of the vehicle i, and the certain value being recorded as S.sub.i; determining space-time correlation of vehicle motion by entropy and conditional entropy of a position random variable S.sub.i: for the vehicle i, assuming that the position of the vehicle i at L times is observed, a position sequence of the vehicle being represented as: T.sub.i=<s.sub.0, s.sub.1, . . . , s.sub.L□1>; and assuming that the vehicle i appears for o.sub.j″ times at the position s.sub.j″ in the sequence, marginal entropy of Si being as follows: $\begin{matrix} H (S_{i}) = {.Math.}_{j^{″} = 0}^{Q - 1} (o_{j^{″}} / L) \times \log_{2} \frac{1}{o_{j^{″}} / L} & (13) \end{matrix}$ the conditional entropy of S.sub.i under a condition that a position variable S.sub.i.sup.1, at a previous moment is given being as follows:
H(S.sub.i|S.sub.i.sup.1)=H(S.sub.i,S.sub.i.sup.1)−H(S.sub.i) (14), and entropy of a joint position random variable being as follows: $\begin{matrix} H (S_{i}, S_{i}^{1}) = {.Math.}_{j^{″} = 1}^{Q - 1} \frac{o_{j^{″} - 1, j^{″}}}{L - 1} \times \log_{2} \frac{1}{o_{j^{″} - 1, j^{″}} / (L - 1)} & (15) \end{matrix}$ o.sub.j″□1,j″ representing a number of occurrences of the vehicle in positions s.sub.j″□1 and s.sub.j″ in the sequence; on a basis of a same method, obtaining conditional entropy of given position variables at previous K moments:
H(S.sub.i|S.sub.i.sup.1,S.sub.i.sup.2, . . . S.sub.i.sup.K) (16); and predicting and estimating positions of the vehicle nodes on a basis of the multi-order Markov chain.

12. The data-aware routing method for the ad hoc wireless vehicular network according to claim 4, wherein a process of using the multi-order Markov chain to model the position change processes of the vehicle nodes comprises: dividing an entire position space corresponding to the vehicle nodes into Q grids, the entire position space being represented as S:
S={s.sub.0,s.sub.1, . . . ,s.sub.Q−1|s.sub.i″∩s.sub.j″=Ø} (12), s.sub.0, s.sub.1, . . . , s.sub.Q−1 representing position spaces corresponding to the grids in the entire position space, and s.sub.i″ and s.sub.j″ representing position spaces corresponding to the grids in the entire position space respectively; at a certain moment, taking a certain value in S as a position of the vehicle i, and the certain value being recorded as S.sub.i; determining space-time correlation of vehicle motion by entropy and conditional entropy of a position random variable S.sub.i: for the vehicle i, assuming that the position of the vehicle i at L times is observed, a position sequence of the vehicle being represented as: T.sub.i=<s.sub.0, s.sub.1, . . . , s.sub.L□1>; and assuming that the vehicle i appears for o.sub.j″ times at the position s.sub.j″ in the sequence, marginal entropy of Si being as follows: $\begin{matrix} H (S_{i}) = {.Math.}_{j^{″} = 0}^{Q - 1} (o_{j^{″}} / L) \times \log_{2} \frac{1}{o_{j^{″}} / L} & (13) \end{matrix}$ the conditional entropy of S.sub.i under a condition that a position variable S.sub.i.sup.1, at a previous moment is given being as follows:
H(S.sub.i|S.sub.i.sup.1)=H(S.sub.i,S.sub.i.sup.1)−H(S.sub.i) (14), and entropy of a joint position random variable being as follows: $\begin{matrix} H (S_{i}, S_{i}^{1}) = {.Math.}_{j^{″} = 1}^{Q - 1} \frac{o_{j^{″} - 1, j^{″}}}{L - 1} \times \log_{2} \frac{1}{o_{j^{″} - 1, j^{″}} / (L - 1)} & (15) \end{matrix}$ o.sub.j″□1,j″ representing a number of occurrences of the vehicle in positions s.sub.j″□1 and s.sub.j″ in the sequence; on a basis of a same method, obtaining conditional entropy of given position variables at previous K moments:
H(S.sub.i|S.sub.i.sup.1,S.sub.i.sup.2, . . . S.sub.i.sup.K) (16); and predicting and estimating positions of the vehicle nodes on a basis of the multi-order Markov chain.

13. The data-aware routing system for the ad hoc wireless vehicular network according to claim 7, wherein a wireless vehicular network model and a crowd sensing model corresponding to the wireless vehicular network are as follows: the wireless vehicular network model is constructed on a basis of an undirected graph; a geographic position of a vehicle node n at a moment τ is represented as p.sub.n(τ), and a motion track of the node from a moment zero to the moment τ is discretized:
T.sub.n= custom-character p.sub.n(0),p.sub.n(1), . . . p.sub.n(τ) τ representing time after discretization; a distance between two nodes i and j at the moment τ is represented as d.sub.ij(τ), all links capable of data transmission in the current wireless vehicular network are represented as
L(τ)={l.sub.i,j|d.sub.i,j(τ)≤R;∀i,j∈N} l.sub.i,j representing a link between the nodes i and j, and R representing a link distance threshold; and the crowd sensing model is constructed: a sensing data function obtained by a vehicle i is as follows: Δ(t,p.sub.i(t),i), pi(t) representing a corresponding geographic position of the vehicle i at a moment t.

14. The data-aware routing system for the ad hoc wireless vehicular network according to claim 13, wherein the wireless vehicular network model and the crowd sensing model corresponding to the wireless vehicular network are as follows: the undirected graph of the wireless vehicular network model is G=(N, E), N being a set of vertices, each vertex representing a vehicle node, E being a set of edges, ∀e∈E, e.sub.n′=((i,j), c(t) and d(t)) being an edge between vertices i and j, and representing communication between the two nodes, c(t) representing contact of the nodes i and j at a moment c(t), and d(t) representing a contact duration.

15. The data-aware routing method for the ad hoc wireless vehicular network according to claim 14, wherein the link distance threshold R is 400 meters.

16. The data-aware routing method for the ad hoc wireless vehicular network according to claim 7, wherein a process of using the multi-order Markov chain to model the position change processes of the vehicle nodes comprises: dividing an entire position space corresponding to the vehicle nodes into Q grids, the entire position space being represented as S:
S={s.sub.0,s.sub.1, . . . ,s.sub.Q−1|s.sub.i″∩s.sub.j″=Ø} (12) s.sub.0, s.sub.1, . . . , s.sub.Q−1 representing position spaces corresponding to the grids in the entire position space, and s.sub.i″ and s.sub.j″ representing position spaces corresponding to the grids in the entire position space respectively; at a certain moment, taking a certain value in S as a position of the vehicle i, and the certain value being recorded as S.sub.i; determining space-time correlation of vehicle motion by entropy and conditional entropy of a position random variable S.sub.i: for the vehicle i, assuming that the position of the vehicle i at L times is observed, a position sequence of the vehicle being represented as: T.sub.i=<s.sub.0, s.sub.1, . . . , s.sub.L□1>; and assuming that the vehicle i appears for o.sub.j″ times at the position s.sub.j″ in the sequence, marginal entropy of Si being as follows: $\begin{matrix} H (S_{i}) = {.Math.}_{j^{″} = 0}^{Q - 1} (o_{j^{″}} / L) \times \log_{2} \frac{1}{o_{j^{″}} / L} & (13) \end{matrix}$ the conditional entropy of S.sub.i under a condition that a position variable S.sub.i.sup.1, at a previous moment is given being as follows:
H(S.sub.i|S.sub.i.sup.1)=H(S.sub.i,S.sub.i.sup.1)−H(S.sub.i) (14), and entropy of a joint position random variable being as follows: $\begin{matrix} H (S_{i}, S_{i}^{1}) = {.Math.}_{j^{″} = 1}^{Q - 1} \frac{o_{j^{″} - 1, j^{″}}}{L - 1} \times \log_{2} \frac{1}{o_{j^{″} - 1, j^{″}} / (L - 1)} & (15) \end{matrix}$ o.sub.j″□1,j″ representing a number of occurrences of the vehicle in positions s.sub.j″□1 and s.sub.j″ in the sequence; on a basis of a same method, obtaining conditional entropy of given position variables at previous K moments:
H(S.sub.i|S.sub.i.sup.1,S.sub.i.sup.2, . . . S.sub.i.sup.K) (16); and predicting and estimating positions of the vehicle nodes on a basis of the multi-order Markov chain.

17. The data-aware routing method for the ad hoc wireless vehicular network according to claim 16, wherein the entire position space corresponding to the vehicle nodes is divided into the Q grids having a grid size of 200 m*200 m.

18. The storage medium according to claim 8, wherein a wireless vehicular network model and a crowd sensing model corresponding to the wireless vehicular network are as follows: the wireless vehicular network model is constructed on a basis of an undirected graph; a geographic position of a vehicle node n at a moment τ is represented as p.sub.n(τ), and a motion track of the node from a moment zero to the moment τ is discretized:
T.sub.n= custom-character p.sub.n(0),p.sub.n(1), . . . p.sub.n(τ) τ representing time after discretization; a distance between two nodes i and j at the moment τ is represented as d.sub.ij(τ); all links capable of data transmission in the current wireless vehicular network are represented as
L(τ)={l.sub.i,j|d.sub.i,j(τ)≤R;∀i,j∈N} l.sub.i,j representing a link between the nodes i and j, and R representing a link distance threshold; and the crowd sensing model is constructed: a sensing data function obtained by a vehicle i is as follows: Δ(t,p.sub.i(t),i), pi(t) representing a corresponding geographic position of the vehicle i at a moment t.

19. The storage medium according to claim 18, wherein the wireless vehicular network model and the crowd sensing model corresponding to the wireless vehicular network are as follows: the undirected graph of the wireless vehicular network model is G=(N, E), N being a set of vertices, each vertex representing a vehicle node, E being a set of edges, ∀e∈E, e.sub.n′=((i,j), c(t) and d(t)) being an edge between vertices i and j, and representing communication between the two nodes, c(t) representing contact of the nodes i and j at a moment c(t), and d(t) representing a contact duration.

20. The storage medium according to claim 19, wherein the link distance threshold R is 400 meters.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0059] FIG. 1 is a distribution graph of a cumulative distribution function (CDF) graph of a vehicle speed;

[0060] FIG. 2 is a distribution graph of vehicle meeting time;

[0061] FIG. 3 is a schematic diagram of an abstract model of a wireless vehicular network; and

[0062] FIG. 4 is a schematic diagram of link scheduling and data packet scheduling.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Embodiment I

[0063] This embodiment is a data-aware routing method for an ad hoc wireless vehicular network. The data-aware routing method includes:

[0064] S1, collect large-scale real vehicle operation data and construct a network and sensing model:

[0065] the data used in this embodiment is real operation data of more than 10,000 taxis and more than 3,000 buses in Shenzhen, i.e., vehicle fine-grained position tracking data and vehicle real-time orientation and speed sensing data, from January, 2015 to December, 2016.

[0066] A global positioning system (GPS) position and speed sensing device is mounted on a vehicle node, to obtain position information, operation direction and instantaneous motion speed of the node in real time, and a passenger carrying condition (i.e., no-load or heavy-load) of the vehicle node may further be obtained by a taxi vehicle node. A data structure of the sensing data of the vehicle node is described as follows:

TABLE-US-00001 Vehicle Longitude Latitude Speed Angle Timestamp Status ID

[0067] Vehicle ID is a unique identification of the vehicle, Longitude and Latitude are instantaneous latitude and longitude information of the node respectively, Speed is the instantaneous speed of the vehicle, Angle is the instantaneous operation direction of the vehicle node, Timestamp is a moment of sensing data recording, and Status represents state information of the vehicle, and for a taxi, represents a passenger carrying condition of the vehicle. An operation range of the vehicle node covers a whole Shenzhen urban area, and a coverage area reaches 400 or more of square kilometers. The vehicle node generate sensing data once every 10 seconds to several minutes and transmit the sensing data back to a data center by means of a GPRS wireless data channel, and specific interval time is different due to different vehicles and has large non-uniformity. In addition, sensing data may be lost during transmission due to unreliability of a wireless data channel. The real operation data contributed by these vehicles is large in scale, and the scale of compressed data reaches 112 GB.

[0068] In an urban environment, due to the influence of tall buildings such as tall buildings and viaducts, GRS positioning data may have large errors, and the errors vary from several meters to several hundred meters. According to road information of an electronic map of Shenzhen and continuity of vehicle node motion, a dislocation position is corrected (Map-Matching).

[0069] By analyzing the operation data of the vehicle in Shenzhen on a large scale, a wide range of uniqueness of the wireless vehicular network, including poor network connectivity, non-uniform node distribution and non-uniform taxi distribution, may be found and verified; a topology of the network is closely related to a wireless communication distance (R) of the node and the total number of the nodes of the network, under the condition that the number of the vehicle nodes is 1000 and a communication distance is 200 meters, the topology of the network is discrete, and for any pair of nodes, there is basically no connected path; and when the communication distance is increased to 400 meters, the connectivity of the network is greatly improved, and a plurality of clusters having excellent connectivity may be seen.

[0070] When the communication distance is kept unchanged and the total number of nodes of the network is increased, the connectivity of the network may also be improved, and the plurality of clusters having excellent connectivity may also be obviously seen. However, even under excellent conditions having the number of the network nodes of 2000 and the communication distance of 400 meters, there are a wide range of non-connected sub-networks within the vehicular network, that is, network non-connectivity is a normal state in the vehicular network.

[0071] In the wireless vehicular network, current vehicle ability to communicate with other vehicles is related to a plurality of factors, including vehicle speed, vehicle distribution density, vehicle meeting time distribution, etc. and the vehicle distribution density and the vehicle meeting time distribution are shown in FIGS. 1 and 2. By means of analysis of data of taxies in Shenzhen, two time periods of Oct. 13, 2007 are selected, and are 8:00-9:00 in the morning of a peak period and 3:00-4:00 in the afternoon of a non-peak period respectively, the operation speed of 95% of vehicles in the peak period is 40 km/h or below, and the speed of 65% of vehicles in the non-peak period is 40 km/h or below. Under the condition that the communication distance is 100 meters, meeting time between 60% of vehicles is less than 10 s in the non-peak period, and meeting time between 65% of vehicles is less than 20 s in the peak period.

[0072] Firstly, a wireless vehicular network model and a crowd sensing model are established, and have an vital effect of designing and developing the wireless vehicular network and an upper-layer crowd sensing application.

[0073] The network connectivity performance of the wireless vehicular network is between a mobile ad hoc network (MANET) and a delay tolerant network (DTN). It is generally considered that the connectivity of the MANET is excellent, and a connected path exists between two nodes at any moment. In the DTN network, the network connectivity is poor, most of time nodes are isolated and not connected, and the nodes occasionally contact to form a wireless communication opportunity.

[0074] On the basis of such recognition, the present disclosure provides the following abstract model of the wireless vehicular network: a network abstract model of the wireless vehicular network in a time interval (0, T) may be defined as an undirected graph G=(N, E), where N is a set of vertices, each vertex representing a vehicle node, E is a set of edges, ∀e∈E, e.sub.n′=((i,j), c(t) and d(t)) is an edge between vertices i and j, and represent communication between the two nodes. As shown in FIG. 3, c(t) represents contact of i and j at a moment c(t), and a contact duration is d(t). d(t) determines communication capacity of the nodes i and j in the current contact, and the larger the value is, the larger transmission capacity of the two nodes in the current contact is.

[0075] A single vehicle node n travels in an urban road network at time (0, T). In a simplified case, a geographic position p.sub.n(t) of the single vehicle node is a continuous curve on a two-dimensional plane, and possible values of p.sub.n(t) are a road and possible parking places on a two-dimensional plane, which reflects that motion of the vehicle node is limited by the road network and the node motion has no randomicity.

[0076] When discretized time is used, the vehicle node n is represented as p.sub.n(τ) at time τ. A motion track of this node from the moment zero to the moment τ may be represented as:

T.sub.n=<p.sub.n(0),p.sub.n(1), . . . p.sub.n(τ) (1),

[0077] where τ represents time after the discretized time; and

[0078] a distance between two nodes i and j at the moment τ is represented as d.sub.ij(τ). All transmissible links in the current wireless vehicular network are represented as L(τ):

L(τ)={l.sub.i,j|d.sub.i,j(τ)≤R;∀i,j∈N} (2),

[0079] where l.sub.i j represents a link between the nodes i and j, and R represents a distance threshold of the transmissible link; and

[0080] establishment of the crowd sensing model is a basis of high-level crowd sensing application optimization design. The present disclosure provides the following crowd sensing model. The sensing data obtained by the vehicle i is a function, which is as shown as follows:

Δ(t,pi(t),i) (3),

[0081] where p.sub.i(t) represents the corresponding geographic position of the vehicle i at the moment t; and

[0082] the collected sensing data is related to time at which the data is generated, the position of the node, and the vehicle.

[0083] S2, construct a joint scheduling based wireless vehicular network routing algorithm:

[0084] an efficient routing algorithm in the wireless vehicular network has a basic effect, and determines data transmission performance between vehicle nodes, and routing performance indexes include a transmission success rate, a transmission latency, a network throughput, data transmission efficiency, etc. Various wireless vehicular network based high-level applications are established on the basis of the efficient routing algorithm, such that design of the efficient routing algorithm has a key effect in the wireless vehicular network.

[0085] However, design of the efficient routing algorithm for the wireless vehicular network faces numerous challenges. Firstly, the vehicular network of the traditional MANET has poor connectivity, and at a certain moment, there may not be a connected path between the source node and the destination node. Secondly, due to non-uniformity of node distribution in the vehicular network, different from the DTN, although the topology of the vehicular network is not connected, the local network has excellent connectivity, and even a plurality of wireless links which compete with one another exist. Finally, a moving speed of the vehicle node is high and may reach 30 m/s or above, node motion has great randomness, and a future motion track of the node has great uncertainty.

[0086] In order to study the optimal routing algorithm for the wireless vehicular network, a routing system model may be established as follows:

[0087] the wireless vehicular network needs to transmit a given data packet set which is recorded as Φ, a source node of each data packet p is recorded as δ(p), and a destination node of each data packet p is recorded as ψ(p). p and p.sub.i( ) are parameters having different meanings, p having not subscript is used for representing a data packet, and p.sub.i( ) having a node subscript is used for representing a geographic position; and

[0088] when a data packet is forwarded over a certain wireless link, it may be considered that the data packet is copied from one node to another node (considering large storage capacity of the vehicle node). For a certain data packet p, a copy set of all the data packets in the network is recorded as θ(p) and is called as a data packet group. When the data packet is subjected to one-time wireless transmission, a size of the data packet group is increased by 1.

[0089] Overall transmission performance of the wireless vehicular network is a function of transmission performance of the single data packet, the transmission performance of the single data packet may be considered firstly, and the transmission performance of the network is further studied.

[0090] The transmission success rate ρ.sub.p of the single data packet is determined by a plurality of factors, including a routing policy and a motion track of all nodes:

ρ.sub.p=f.sub.γ(δ(p),ψ(p),{T.sub.n}) (4),

[0091] where {T.sub.n} represents a motion track set of all the nodes; and f.sub.γ(⋅) represents a transmission success rate function; and

[0092] the success rate may be determined at the beginning when the motion track and the transmission strategy of the node are given. However, in reality, the future motion track of the node is agnostic, such that the transmission success rate may be considered as a random variable.

[0093] The transmission latency σ.sub.p of the data packet p is the sum of all the intra-network transmission times, the time may be divided into two parts, i.e., one part that has been already determined and the other part that needs to be used in the future and is not yet determined. Similar to analysis of the transmission success rate,

σ.sub.p(τ)=τ+Γ.sub.γ(δ(p),ψ(p),{T.sub.n}) (5) may be obtained,

[0094] where Γγ(⋅) represents a transmission latency function; and

[0095] transmission cost custom-character of the data packet p is the sum of transmission times generated during transmission of the data packet. Since the size of the data packet set θ(p) is increased by 1 each time, a final size of the data packet set θ(p) is also transmission cost of p:

custom-character =|ϑ(p)| (6)

[0096] where |θ(p)| represents the capacity of the data packet group θ(p); and

[0097] a design objective of an optimal transmission strategy is as follows: maximizing a transmission success rate, minimizing a transmission latency, and minimizing network cost:

maxΣ.sub.p∈Φ custom-character [ρ.sub.p] (7),

minΣ.sub.p∈Φ custom-character [σ.sub.p] (8), and

minΣ.sub.p∈Φ custom-character [] (9),

[0098] where custom-character [•] represents an expectation.

[0099] The network transmission efficiency is as follows:

custom-character Σ.sub.p∈Φ[ρ.sub.p]/Σ.sub.p∈Φ[] (10).

[0100] With maximizing the transmission success rate as an example, the optimization objective may be written as:

maxΣ.sub.p∈Φ custom-character [f.sub.T(δ(p),ψ(p),{T.sub.n})] (11).

[0101] If a transmission strategy needs to be determined, motion tracks of all the nodes need to be determined.

[0102] In the MANET, the core problem of data transmission is a link scheduling problem, that is, which wireless links in the network may perform wireless communication us determined, and since wireless conflicts exist between different links, an excellent routing algorithm needs to reduce conflicts to achieve maximum throughput data transmission in the network. In the DTN, nodes are not connected most of the time, and only when two nodes contact, the two nodes have the opportunity to achieve data communication. The core problem of data transmission of the DTN is the problem of data packet scheduling. That is, under the condition that node resources are limited, which data packets are exchanged when two nodes contact is decided.

[0103] The core problem of point-to-point data transmission and routing in the wireless vehicular network is link scheduling and data packet scheduling. The schematic diagram of link scheduling and data packet scheduling is shown in FIG. 4, dashed lines in FIG. 4 represent all possible wireless links, and a result of link scheduling is that bc links are activated and communicate wirelessly. In this case, the plurality of data packets to be transmitted exist on the node b, the task of data packet scheduling is to select data packets from the data packets to be transmitted, and transmit the data packets on the link bc, and since communication time between the node b and the node c is likely to be short, only the limited number of data packets may be transmitted.

[0104] The present disclosure provides an optimal routing algorithm for joint scheduling, which jointly considers link scheduling and data packet scheduling. In the optimal joint scheduling design, the motion tracks of the nodes are the key of optimal design. However, under actual conditions, the future tracks of the nodes are not predictable, which becomes a difficulty of joint scheduling design. However, through analysis of large-scale operation data of vehicles in Shenzhen, the present disclosure finds that the motion track of the vehicles in an urban environment has strong regularity. On the basis of the regularity, the future motion track of the vehicle node may be accurately predicted, such that important support is provided for joint scheduling and routing decision making.

[0105] The present disclosure analyzes track data of the taxi in Shenzhen to show that motion of the vehicle nodes has strong space-time correlation. For simplicity, the entire position space is divided into Q grids, such that the position space may be represented as S:

S={s.sub.0,s.sub.1, . . . ,s.sub.Q−1|s.sub.i″∩s.sub.j″=Ø} (12),

[0106] where s.sub.0, s.sub.1, . . . , s.sub.Q−1 represent position spaces corresponding to the grids in the entire position space, and s.sub.i″ and s.sub.j″ represent the position spaces corresponding to the grids in the entire position space respectively; and

[0107] at a certain moment, a certain value in S is taken as the position of a vehicle i and is recorded as S.sub.i; and the present disclosure recognizes the space-time correlation of the vehicle motion by analyzing entropy and conditional entropy of the position random variable S.sub.i.

[0108] For the vehicle i, it is assumed that the position of the vehicle i at L moments is observed, and a position sequence of the vehicle is represented as: T.sub.i=<s.sub.0, s.sub.1, . . . , s.sub.L−1>. It is assumed that the vehicle i appears for o.sub.j″ times at the position s.sub.j″ in the sequence, such that marginal entropy of S.sub.i is computed as follows:

[00003] $\begin{matrix} H (S_{i}) = {.Math.}_{j^{″} = 0}^{Q - 1} (o_{j^{″}} / L) \times \log_{2} \frac{1}{o_{j^{″}} / L} . & (13) \end{matrix}$

[0109] The conditional entropy of S.sub.i under the condition that the position variable S.sub.i.sup.1, at the previous moment is given is as follows:

H(S.sub.i|S.sub.i.sup.1)=H(S.sub.i,S.sub.i.sup.1)−H(S.sub.i) (14), and

[0110] where the entropy of a joint position random variable is as follows:

[00004] $\begin{matrix} H (S_{i}, S_{i}^{1}) = {.Math.}_{j^{″} = 1}^{Q - 1} \frac{o_{j^{″} - 1, j^{″}}}{L - 1} \times \log_{2} \frac{1}{o_{j^{″} - 1, j^{″}} / (L - 1)}, & (15) \end{matrix}$

[0111] where o.sub.j″−1,j″ represents the number of occurrences of positions s.sub.j″−1 and s.sub.j″ of the vehicle in the sequence; and

[0112] On the basis of the same method, the conditional entropy given the position variable at the previous K moments may further be computed:

H(S.sub.i|S.sub.i.sup.1,S.sub.i.sup.2, . . . S.sub.i.sup.K) (16).

[0113] Cumulative distribution functions (CDF) of the marginal entropy and the conditional entropy of the vehicle position random variable are determined, and in this embodiment, the size of the grids is configured to be 200 m*200 m, and the number of nodes is controlled to be 500.

[0114] It may be determined that the conditional entropy is much less than the marginal entropy, which means that uncertainty of the position variable is small, which indicates that the uncertainty of the position variable at the current moment is greatly reduced under the condition that the position at the previous moment is given. It may further be observed that the conditional entropy is further reduced under the condition that the positions at the previous moments are given, which indicates that the uncertainty of the positions at the current moment may be reduced by giving previous several moments. However, it may also be seen that the degree of decreasing trend of the conditional entropy slows down rapidly, which indicates that given position information at previous moments may not be much helpful to determine the position at the current moment.

[0115] On the basis of the above analysis, multi-order Markov chains are used for modeling a position change process of the vehicle nodes, and a next moment and several moments in the future are predicted and estimated under the condition that the positions of the previous several moments are given.

[0116] On the basis of position actual values and predicted estimated values of the vehicle nodes, the optimal transmission strategy is combined to achieve data routing in the wireless vehicular network.

[0117] The routing method of the present disclosure is utilized, such that communication between a base station arranged on a roadside and the vehicle node and between the base stations may be achieved, a road condition may further be sensed, and a traffic condition may further be predicted.

Embodiment II

[0118] This implementation is a data-aware routing system for an ad hoc wireless vehicular network. The system is used for executing the data-aware routing method for an ad hoc wireless vehicular network.

Embodiment III

[0119] This implementation is a storage medium. The storage medium stores at least one instruction, where the at least one instruction is loaded and executed by a processor, to implement the data-aware routing method for an ad hoc wireless vehicular network.

[0120] The storage medium of this implementation includes, but not limited to, an independent memory, a memory arranged inside a computer, etc.

Embodiment IIII

[0121] This implementation is a device. The device includes a processor and a memory, where the memory stores at least one instruction, and the at least one instruction is loaded and executed by the processor, to implement the data-aware routing method for an ad hoc wireless vehicular network.

[0122] The device of this implementation includes, but not limited to, a personal computer (PC), a server, a mobile device, a specially developed single chip microcomputer, etc.

[0123] The present disclosure may have various other embodiments, without departing from the spirit and essence of the present disclosure, those skilled in the art would have been able to make various corresponding changes and modifications in accordance with the present disclosure, and these corresponding changes and modifications all fall within the scope of protection of the appended claims of the present disclosure.

DATA-AWARE ROUTING METHOD AND SYSTEM FOR AD HOC WIRELESS VEHICULAR NETWORK, STORAGE MEDIUM AND DEVICE

Assignee

Inventors

Cpc classification

Classification Explorer

H04W40/026

ELECTRICITY

Classification Explorer

H04W40/18

ELECTRICITY

Classification Explorer

H04W40/12

ELECTRICITY

Classification Explorer

H04W40/20

ELECTRICITY

Classification Explorer

Y02D30/70

GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

International classification

Classification Explorer

H04W40/20

ELECTRICITY

Classification Explorer

H04W40/12

ELECTRICITY

Abstract

Claims

Description