CN103052082A - Optimal arrangement method of roadside base station under condition of time-delay boundary in VANET (vehicle ad hoc network) - Google Patents

Abstract

The invention provides an optimal arrangement method of a roadside base station under the condition of a time-delay boundary in VANET (vehicle ad hoc network). The method comprises the following steps of: converting a roadside base station wire arrangement problem into a bigraph minimum point cover class problem by defining a road map and a time-delay boundary diagram; and converting a roadside base station wireless arrangement problem into a linear programming problem by defining a full-coverage roadside base station. The optimal arrangement method proves that the optimal roadside base station problem is an NP (network processor) difficult problem, so that an approximation algorithm of the roadside base station wire arrangement and the roadside base station wireless arrangement can be given out. The optimal arrangement method is simple in method, high in execution efficiency, and suitable for the base station arrangement in a vehicle networking network, so that the messages receiving probability by a vehicle can be effectively improved.

Description

Base station, roadside optimal deployment method among the VANET under the time-delay terminal conditions

Technical field

The present invention relates to the wireless network communication technique field, particularly relate to base station, the roadside optimal deployment method under the time-delay terminal conditions among a kind of VANET.

Background technology

VANET(Vehicular Ad-hoc NETwork, vehicle self-organizing network) quality of roadside base station deployment is on larger with the impact of vehicle-mounted net performance in.If the base station, roadside of disposing is less, emergency message is other vehicle node in the informing network timely; In contrast, if the base station, roadside of disposing is too much, the cost of system also increases thereupon.Spreadability about node deployment problem and network has a lot of research in wireless sensor network.

List of references: H.Liu, P.jun Wan, and X.Jia, On optimal placement of relaynodes for reliable connectivity in wireless sensor networks, Journal of Combinatorial Optimization, vol.11, no.2, pp.249 – 260,2006; Liu Ming, Cao Jiannong, Zheng Yuan etc., Analysis for Multi-Coverage Problem in Wireless Sensor Networks, Journal of Software, 2007.18 (01): p.127-136; Huang Xiao, Cheng Hongbing, Yang Geng, wireless sensor network cover connective research. communication journal, 2009.30 (02): p.129-135.

But in VANET with wireless sensor network in node deployment be different.(1) the potential extensive property of VANET.The space of general wireless sensor network disposition is smaller, and VANET deployment scope can be a city or a plurality of city.(2) node deployment need to carry out all standing to all surveyed areas that needs in the general sensor network, and the situation that perhaps reliability requirement is higher requires all standing with service quality.Potential extensive decision of VANET can not all standing.Vehicle node can be used as communication node among the VANET simultaneously, allows to have certain blind area, can be by mode access service node mobile, that multi-hop is transmitted between the vehicle node.In VANET, the people such as Pan Li have proposed a kind of deployment scheme of gateway node.VANET is by gateway accessing Internet for the article hypothesis, and a plurality of access points (AP, Access Point) are set on the network.There is communication line to link to each other between access point and the gateway.In fact jumping figure optimal problem between access point and the gateway discussed in article.Service node deployment issue in the peacekeeping bidimensional vehicular ad hoc network discussed in article.The people such as Farahmand F have proposed a kind of deployment scheme of VANET via node.Bus or the subway system crossover location of different running routes are a via node position candidate.Packet is produced by source node, consigns to bus or subway system.Can not communicate by letter between the document hypothesis vehicle, communication only occurs over just between vehicle and the via node.Vehicle carries packet, runs into suitable via node, gives via node package forward, and via node is transmitted to the vehicle on the other public bus network again, and last vehicle carries packet and consigns to destination node.For the heuritic approach that proposes relaying node deployment scheme under a kind of bandwidth and the buffer memory capacity limit condition in the above-mentioned scene literary composition.Yet this algorithm plans do not have generality for having fixedly the vehicle of running route.

List of references: Pan Li, X.H., Yuguang Fang, and Phone Lin, Optimal placement of gateways in Vehicular Networks.IEEE Transactions on Vehicular Technology, 2007; Farahmand F., et al.Relay Node Placement in Vehicular Delay-Tolerant Networks.IEEE GLOBECOM2008.2008.

For urban environment, the people such as Junghoon Lee consider how to place the base station, roadside, so that the roadside number of base stations of placing is minimum, the people such as Youchen Bao consider how to carry out better the Data Collection of vehicle, thereby optimally carry out the deployment of via node.Article has proved that certainty and uncertainty via node deployment issue are NP-Hard problem (nondeterministic polynomial difficult problems), then in conjunction with the space-time rule of vehicle movement, propose certainty and uncertainty via node Deployment Algorithm, and analyzed the time complexity of algorithm.For highway environment, the people such as Aslam B. consider along base station, highway optimal placement roadside problem, target be how can minimum time-delay ground with vehicle collection to emergency event message be delivered to nearest base station, roadside, article transfers this problem to and is the ballooning problem, distance is then readjusted on the border that touches other balloons when the balloon that expands, until all balloons can not expand.The final position of this process balloon then is the position that place base station, optimum roadside.It is all fairly simple that yet the mobility model that article is considered and candidate place interstitial content, do not have versatility.

List of references: Junghoon Lee, C.M.K., A Roadside Unit Placement Scheme for Vehicular Vehicular Telematics Networks, LNCS, 2010; Youchen Bao, Y.Z.On Optimal Relay Placement for Urban Vehicular Networks, IEEE International Conference on Communications (ICC), 2011; Aslam B., Z.C.C.Optimal roadside units placement along highways, in Consumer Communications and Networking Conference (CCNC), 2011IEEE.2011.

Summary of the invention

For the problems referred to above, the objective of the invention is to find a kind of roadside base station deployment method of optimum, guarantee that message propagates into all vehicles in the time-delay boundary under the time.

Technical scheme of the present invention is base station, the roadside optimal deployment method under the time-delay terminal conditions among a kind of VANET, may further comprise the steps:

One, at first objective definition is given time-delay boundary T, and how optimum base station, deployment roadside guarantees emergency message all nodes in the car networking that T propagated in the time;

Two, definition mileage chart G=(V, E), the figure Point Set is V={v₁, v₂..., v_m, v_iThe both candidate nodes that represents all deployment, quantity are m, and the value of i is 1,2 ... m; The limit integrates as E={e₁, e₂..., e_n, e_jThe set of expression road, quantity is n, the value of j is 1,2 ... n, wherein the weights e (v on every limit_i, v_j) be the time-delay d that message is propagated at this road_Ij

Three, definition D_IjBe broadcast to the propagation time under the worst case of other vehicle node for the roadside base-station node that message is disposed from any two candidates;

Four, the expansion vertex covering set of definition base station, roadside is ECV_T(v_x), T is given when the time-delay boundary, and message is from roadside base station v_xPropagate into other base station, roadside, satisfy following formula,

${\mathrm{ECV}}_T\left(v_x\right)=\left\{v_i\right|D_{\mathrm{xi}}\≤T;{\∀v}_i\∈V\}$

Wherein, D_XiThat message is from base station, roadside v_xPropagate into other base station, roadside v_iPropagation time; If the propagation time is less than time-delay boundary T, then base station, roadside v_iBe base station, roadside v_xExpansion vertex covering set ECV_T(v_x) in an element;

Five, definition base station, roadside v_xThe expansion limit cover and to integrate as ECE_T(v_x), satisfy following formula,

${\mathrm{ECE}}_T\left(v_x\right)=\left\{e(v_i,v_j)\right|\begin{array}{c}{v}_i\∈{\mathrm{ECV}}_T\left(v_x\right)^v_j\∈{\mathrm{ECE}}_T\left(v_x\right)^e(v_i,v_j)\∈E;\\ \∀v_i,v_j\∈V\end{array}\}$

Wherein, base station, roadside v_iAnd v_jBase station, roadside v_xExpansion vertex covering set ECV_T(v_x) in two elements, and limit e (v_i, v_j) in the limit collection of mileage chart E (G), limit e (v then_i, v_j) be base station, roadside v_xThe expansion limit cover and to integrate as ECE_T(v_x) in an element;

Six, definition time-delay boundary figure is undirected bigraph (bipartite graph) G '=(V ', E '), and its Point Set is V '=V ∪ V2, and point set V disposes the point set of base station, i.e. V={v for all candidates₁, v₂..., v_m, point set V2={v_E1, v_E2... v_EnThe point set that consists of for all limits of mileage chart; Limit e ' (v among the collection E ' of limit_i, v_EjIf) represent to satisfy under time-delay boundary T vertex v_iCan cover limit e_j, satisfy following formula,

$E^{\′}=\left\{e^{\′}(v_i,v_j)\right|e_j\∈{\mathrm{ECV}}_T\left(i\right);{\∀v}_i\∈V,v_{e_j}\∈V2\}$

Wherein, if limit e_jBase station, roadside v_iThe expansion limit cover collection ECE_T(i) element in, then limit e ' (v_i, v_Ej) be an element among the collection E ' of limit;

Seven, definition all standing roadside collection of base stations is for the situation of roadside base station radio connection, for set R'={v₁, v₂, ..., v_kIn any roadside base station v_iAnd v_j, satisfy following formula,

$D_{\mathrm{ij}}\≤T,{\∀v}_i,v_j\∈R^{\′}$

Wherein, any two roadsides base station v among all standing roadside collection of base stations R'_iAnd v_jSatisfy message from base station, roadside v_iPropagate into other base station, roadside v_jPropagation time D_IjLess than time-delay boundary T;

Eight, for base station, roadside wired connection situation, adopt approximate data, try to achieve the optimum roadside collection of base stations of disposing; Connect for the roadside base station radio, propose the roadside base station radio and connect Deployment Algorithm, try to achieve the optimum roadside collection of base stations of disposing;

The described approximate data implementation procedure that adopts for base station, roadside wired connection situation is as follows,

R is used for recording candidate roadside collection of base stations, and T is the time-delay boundary, and R ' is the base station deployment set of optimum roadside, carries out following substep,

Step 1, input candidate roadside collection of base stations R, time-delay boundary T forwardsstep 2 to;

Step 2 is calculated base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij,forward step 3 to;

Step 3 is judged base station, roadside v_iWhether belong to candidate roadside collection of base stations R, if so, then calculate v_iExpansion vertex covering set ECV_T(v_i) and expansion limit covering collection ECE_T(v_i), turnstep 4; Otherwise, forward step 5 to;

Step 4 is i+1 with the i assignment, turnsstep 3;

Step 5, the optimum roadside of initialization base station deployment set R ' is empty, forwards step 6 to;

Step 6 judges that candidate roadside collection of base stations R whether not for empty, if be not empty, then calculates the optimum node v that disposes_Best=max{ECE_T(v_i), the optimum of selecting is disposed node v_BestAdd among the optimum roadside base station deployment set R ', i.e. R '=R ' ∪ { v_Best; Then, from the collection of base stations R of candidate roadside, take out v_BestThe node that covers of extension point, namely R=R ECV_T(v_Best), until candidate roadside collection of base stations R is empty; If candidate roadside collection of base stations R is empty, export optimum roadside base station deployment set R ', finish;

Connect the roadside base station radio connection Deployment Algorithm that proposes for the roadside base station radio and comprise the 1st stage flow process and the 2nd stage flow process,

The 1st stage flow process implementation procedure is as follows,

R is used for recording candidate roadside collection of base stations, and T is the time-delay boundary, and R ' ' is the base station deployment set of sub optimum roadside, and Ω is the set of sub optimum roadside base station deployment set, carries out following substep,

Step 1, input candidate roadside collection of base stations R, time-delay boundary T forwardsstep 2 to;

Step 2 is calculated base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij,forward step 3 to;

Step 3 is judged base station, roadside v_iWhether belong to candidate roadside collection of base stations R, if so, then calculate v_iExpansion vertex covering set ECV_T(v_i) and expansion limit covering collection ECE_T(v_i),forward step 4 to; Otherwise, forward step 5 to;

Step 4 is i+1 with the i assignment, turnsstep 3;

Step 5, the content of initialization set omega are empty, namely

The content of initialization set Ψ is candidate roadside collection of base stations R, and namely Ψ=R forwards step 6 to;

Step 6 judges whether set Ψ is not equal to sky, and if so, then the optimum roadside of initial beggar base station deployment set R ' ' is empty, forwards step 7 to; Otherwise, export the set omega of optimum roadside base station deployment set, algorithm finishes;

Step 7 judges that candidate roadside collection of base stations R whether not for empty, if be not empty, then calculates the optimum node v that disposes_Best=max{ECE_T(v_i), the optimum of selecting is disposed node v_BestAdd among the sub optimum roadside base station deployment set R ' ', i.e. R ' '=R ' ' ∪ { v_Best; Then, from the collection of base stations R of candidate roadside, take out v_BestThe node that covers of extension point, namely R=R ECV_T(v_Best), until candidate roadside collection of base stations R is empty; If candidate roadside collection of base stations R is empty,forward step 8 to;

Step 8 is disposed node v with the optimum of selecting_BestRemove the Ψ from set, namely Ψ=Ψ v_Best, the optimum roadside of son base station deployment set R ' ' is added in the set omega, namely Ω=Ω ∪ R ' ' forwards step 6 to;

The 2nd stage flow process implementation procedure is as follows,

Ω is the set of sub optimum roadside base station deployment set, and T is the time-delay boundary, and R ' ' is the base station deployment set of sub optimum roadside, R_OptBe the optimum deployment set of wireless connections Deployment Algorithm, carry out following substep,

Step 1 is inputted the set omega that sub optimum roadside base station deployment is gathered, and time-delay boundary T forwardsstep 2 to;

Step 2 judges that whether sub optimum roadside base station deployment set R ' ' belongs to set omega, if so, then forwardsstep 3 to; Otherwise, forward step 7 to;

Step 3 is judged base station, roadside v_iAnd v_jThe no sub optimum roadside base station deployment set R ' ' that belongs to if so, forwardsstep 4 to; Otherwise,forward step 2 to;

Step 4 is calculated base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward step 5 to;

Step 5 is judged D_IjWhether less than time-delay boundary T, if so, forward step 6 to; Otherwise,forward step 3 to;

Step 6 is taken out the optimum roadside of son base station deployment set R ' ' from set omega, namely Ω=Ω R ' ', thenforward step 2 to;

Step 7, intiating radio connects the optimum deployment set R of Deployment Algorithm_Opt, with R_OptAssignment is sub optimum roadside base station deployment set R ' ', i.e. R_Opt=R ' ' forwardsstep 8 to;

Step 8 judges that whether sub optimum roadside base station deployment set R ' ' belongs to set omega, if so, turns step 9; Otherwise, output R_Opt, algorithm finishes;

Step 9 judges that whether the interstitial content of sub optimum roadside base station deployment set R ' ' is less than or equal to optimum deployment set R_OptInterstitial content, namely | R''|＜=| R_Opt|, if so, with optimum deployment set R_OptAssignment is sub optimum roadside base station deployment set R ' ', i.e. R_Opt=R ' ' forwardsstep 8 to, if otherwise directly forwardstep 8 to.

Characteristics of the present invention: by mileage chart and time-delay boundary graphic definition, the wired deployment issue in base station, roadside is converted into the minimum vertices covering level problem of bigraph (bipartite graph); By the definition of base station, all standing roadside, not that problem is converted into linear programming problem with the roadside base station radio; Prove that base station, optimum roadside problem is np hard problem, thereby provide the approximate data of the wired deployment in base station, roadside and the deployment of roadside base station radio.The inventive method is simple, execution efficient is high, be applicable to the base station deployment in the car networked environment, thereby the Effective Raise vehicle is received the probability of message.

Description of drawings

Fig. 1 is the mileage chart example of the embodiment of the invention.

Fig. 2 is that the actual measurement request of the embodiment of the invention connects the graph of a relation with the response time, and Fig. 2 a is infinite time-delay boundary figure for the time-delay boundary, and Fig. 2 b is 4 time-delay boundary figure for the time-delay boundary, and Fig. 2 c is 2 time-delay boundary figure for the time-delay boundary.

Fig. 3 is that the wired connection of the embodiment of the invention is disposed (ORP-L) algorithm flow chart.

Fig. 4 is that (ORP-W)stage 1 specific algorithm flow chart is disposed in the wireless connections of the embodiment of the invention.

Fig. 5 is that (ORP-W) stages 2 algorithm flow chart is disposed in the wireless connections of the embodiment of the invention.

Embodiment

Technical solution of the present invention can adopt the computer software flow process to realize automatically operation in the specific implementation.Describe technical solution of the present invention in detail below in conjunction with drawings and Examples.

Base station, roadside optimal deployment method in the VANET environment that the embodiment of the invention provides under the time-delay terminal conditions may further comprise the steps:

One, at first objective definition is given time-delay boundary T, and how optimum base station, deployment roadside guarantees emergency message all nodes in the car networking that T propagated in the time;

Two, definition mileage chart G=(V, E), the figure Point Set is V={v₁, v₂..., v_m, v_iThe both candidate nodes that represents all deployment, quantity are m, and the value of i is 1,2 ... m; The limit integrates as E={e₁, e₂..., e_n, e_jThe set of expression road, quantity is n, the value of j is 1,2 ... n, wherein the weights e (v on every limit_i, v_j) be the time-delay d that message is propagated at this road_Ij

Three, definition D_IjBe broadcast to the propagation time under the worst case of other vehicle node for the roadside base-station node that message is disposed from any two candidates;

Four, the expansion vertex covering set of definition base station, roadside is ECV_T(v_x), T is given when the time-delay boundary, and message is from roadside base station v_xPropagate into other base station, roadside, satisfy:

${\mathrm{ECV}}_T\left(v_x\right)=\left\{v_i\right|D_{\mathrm{xi}}\≤T;{\∀v}_i\∈V\}$

Wherein, D_XiThat message is from base station, roadside v_xPropagate into other base station, roadside v_iPropagation time; If the propagation time is less than time-delay boundary T, then base station, roadside v_iBe base station, roadside v_xExpansion vertex covering set ECV_T(v_x) in an element.

Five, definition base station, roadside v_xThe expansion limit cover and to integrate as ECE_T(v_x), satisfy:

${\mathrm{ECE}}_T\left(v_x\right)=\left\{e(v_i,v_j)\right|\begin{array}{c}{v}_i\∈{\mathrm{ECV}}_T\left(v_x\right)^v_j\∈{\mathrm{ECE}}_T\left(v_x\right)^e(v_i,v_j)\∈E;\\ \∀v_i,v_j\∈V\end{array}\}$

Wherein, base station, roadside v_iAnd v_jBase station, roadside v_xExpansion vertex covering set ECV_T(v_x) in two elements, and limit e (v_i, v_j) in the limit collection of mileage chart E (G), limit e (v then_i, v_j) be base station, roadside v_xThe expansion limit cover collection ECE_T(v_x) in an element.

Six, definition time-delay boundary figure is undirected bigraph (bipartite graph) G '=(V ', E '), and its Point Set is V '=V ∪ V2, and point set V disposes the point set of base station, i.e. V={v for all candidates₁, v₂..., v_m, point set V2={v_E1, v_E2... v_EnThe point set that consists of for all limits of mileage chart; Limit e ' (v among the collection E ' of limit_i, v_EjIf) represent to satisfy under time-delay boundary T vertex v_iCan cover limit e_j, satisfy:

$E^{\′}=\left\{e^{\′}(v_i,v_j)\right|e_j\∈{\mathrm{ECV}}_T\left(i\right);{\∀v}_i\∈V,v_{e_j}\∈V2\}$

Wherein, if limit e_jBase station, roadside v_iThe expansion limit cover collection ECE_T(i) element in, then limit e ' (v_i, v_Ej) be an element among the collection E ' of limit.

Seven, definition all standing roadside collection of base stations is for the situation of roadside base station radio connection, for set R'={v₁, v₂, ..., v_kIn any roadside base station v_iAnd v_j, satisfy:

$D_{\mathrm{ij}}\≤T,{\∀v}_i,v_j\∈R^{\′}$

Wherein, any two roadsides base station v among all standing roadside collection of base stations R'_iAnd v_jSatisfy message from base station, roadside v_iPropagate into other base station, roadside v_jPropagation time D_IjLess than time-delay boundary T.

Eight, base station, roadside optimal deployment method is decomposed into the wired deployment of the wired deployment in base station, roadside (ORP-L) and base station, roadside (ORP-W) method;

For base station, roadside wired connection situation, adopt approximate data, try to achieve the optimum roadside collection of base stations of disposing;

Connect for the roadside base station radio, propose the roadside base station radio and connect deployment (ORP-W) algorithm.Algorithm at first need to find all standing roadside collection of base stations Ω=R '₁, R '₂... R '₁, each element of this set is the optimum roadside collection of base stations of disposing of son; Then find an optimal solution R ' in this set₁, it is minimum that this optimal solution satisfies the roadside number of base stations of disposing.

Base station, roadside of the present invention optimal deployment method comprises following two parts:

(1) optimum of base station, roadside wired connection is disposed.

(2) optimum of roadside base station radio connection is disposed.

(1) in, the whole wired connections in base station, roadside, we are translated into the vertex cover problem of undirected bigraph (bipartite graph), then provide approximate data.(2) in, the whole wireless connections in base station, roadside, we are translated into linear programming problem, and provide approximate data stage by stage.Provide respectively embodiment to realize in detail being described as follows:

(1) optimum of base station, roadside wired connection is disposed

According to the definition ofstep 2, mileage chart G=(V, E), figure Point Set are V={v₁, v₂..., v_m, v_iThe both candidate nodes that represents all deployment, quantity are m, and the value of i is 1,2 ... m; The limit integrates as E={e₁, e₂..., e_n, e_jThe set of expression road, quantity is n, the value of j is 1,2 ... n, wherein the weights e (v on every limit_i, v_j) be the time-delay d that message is propagated at this road_IjDefinition D_IjBe the roadside base-station node v that message is disposed from two candidates_i, v_jBe broadcast to other vehicle node v_kWorst case under propagation time, have:

Wherein, N (i) expression node v_iNeighbor node set.Mileage chart example such as accompanying drawing 1 comprise node A, B, C, D, and limit 1,2,3,4 is arranged.

So, T is given when the time-delay boundary, and information is from roadside base station v_xPropagate into other base station, roadside, the expansion vertex covering set of this base station, roadside is ECV_T(v_x), satisfy:

${\mathrm{ECV}}_T\left(v_x\right)=\left\{v_i\right|D_{\mathrm{xi}}\≤T;{\∀v}_i\∈V\}$

In like manner, the expansion limit of this base station, roadside covers and integrates as ECE_T(v_x), satisfy:

${\mathrm{ECE}}_T\left(v_x\right)=\left\{e(v_i,v_j)\right|\begin{array}{c}{v}_i\∈{\mathrm{ECV}}_T\left(v_x\right)^v_j\∈{\mathrm{ECE}}_T\left(v_x\right)^e(v_i,v_j)\∈E;\\ \∀v_i,v_j\∈V\end{array}\}$

Definition time-delay boundary figure is undirected bigraph (bipartite graph) G '=(V ', E '), and its Point Set is V '=V ∪ V2, and point set V disposes the point set of base station, i.e. V={v for all candidates₁, v₂..., v_m, point set V2={v_E1, v_E2... v_EnThe point set that consists of for all limits of mileage chart; Limit e ' (v among the collection E ' of limit_i, v_EjIf) represent to satisfy under time-delay boundary T vertex v_iCan cover limit e_j, satisfy:

$E^{\′}=\left\{e^{\′}(v_i,v_j)\right|e_j\∈{\mathrm{ECV}}_T\left(i\right);{\∀v}_i\∈V,v_{e_j}\∈V2\}$

The G ' of the corresponding delay boundary figure of accompanying drawing 1_∞, G '₄, G '₂As shown in Figure 2.Wherein, G '_∞Expression time-delay boundary is infinite time-delay boundary figure, such as accompanying drawing 2a; G '₄Expression time-delay boundary is 4 time-delay boundary figure, such as accompanying drawing 2b; G '₂Expression time-delay boundary is 2 time-delay boundary figure, such as accompanying drawing 2c.In Fig. 1,4 roadside base-station nodes are arranged, be respectively A, B, C and D.4 roads are arranged, and are respectively limit e (A, B), limit e (B, C), limit e (C, D) and limit e (D, A).It is 1 that message propagates into Node B from node A, and then the weights of limit e (A, B) are 1.Limit e (B, C) in like manner, the weights of limit e (C, D) and limit e (D, A) are respectively 2,3 and 4.In accompanying drawing 2, point set is made of two parts, and a part is the point set V of accompanying drawing 1, namely puts A, B, C and D; Another part is the point set V2 that the limit collection of accompanying drawing 1 consists of, and namely puts V_{E (A, B)}, V_{E (B, C)}, V_{E (C, D)}And V_{E (D, A)}In accompanying drawing 2a, because the time-delay boundary is infinitely great, then under infinitely-great time-delay boundary, message can propagate into limit e (A, B) all the figure from node A, e (B, C), and e (C, D) and e (D, A), therefore, node A and node V_{E (A, B)}, V_{E (B, C)}, V_{E (C, D)}And V_{E (D, A)}There is a limit to link to each other.In like manner, Node B, C and D also with node V_{E (A, B)}, V_{E (B, C)}, V_{E (C, D)}And V_{E (D, A)}There is a limit to link to each other, therefore finally can gets the time-delay boundary figure of accompanying drawing 2a.Be 4 and 2 o'clock for the time-delay boundary, in like manner can obtain respectively the time-delay boundary figure of accompanying drawing 2b and accompanying drawing 2c.

For the situation of base station, roadside wired connection, propose base station, roadside wired connection and dispose (ORP-L) algorithm, the specific algorithm flow chart is as shown in Figure 3.

What Fig. 3 provided is the flow chart that wired connection is disposed (ORP-L) algorithm, and R is used for recording candidate roadside collection of base stations, and T is the time-delay boundary, and R ' is the base station deployment set of optimum roadside, and arthmetic statement is as follows:

Step1: input candidate roadside collection of base stations R, time-delay boundary T forwards Step2 to;

Step2: calculate base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward Step3 to;

Step3: judge base station, roadside v_iWhether belong to candidate roadside collection of base stations R, if so, then calculate v_iExpansion vertex covering set ECV_T(v_i) and expansion limit covering collection ECE_T(v_i), turn Step4; Otherwise, forward Step5 to;

Step4: be i+1 with the i assignment, turn Step3;

Step5: the optimum roadside of initialization base station deployment set R ' is empty, forwards Step6 to;

Step6: judge whether candidate roadside collection of base stations R (is not designated as among the figure for empty

), if be not empty, then calculate the optimum node v that disposes_Best=max{ECE_T(v_i), the optimum of selecting is disposed node v_BestAdd among the optimum roadside base station deployment set R ', i.e. R '=R ' ∪ { v_Best.Then, from the collection of base stations R of candidate roadside, take out v_BestThe node that covers of extension point, namely R=R ECV_T(v_Best), until candidate roadside collection of base stations R is empty;

If candidate roadside collection of base stations R is empty, export optimum roadside base station deployment set R ', finish.

(2) optimum of roadside base station radio connection is disposed

For the situation of roadside base station radio connection, for set R'={v₁, v₂, ..., v_kAny roadside base station v in (herein, k is the total number of base of set among the R ')_iAnd v_j, satisfy:

$D_{\mathrm{ij}}\≤T,{\∀v}_i,v_j\∈R^{\′}$

Then we claim this set to be all standing roadside collection of base stations.Obviously, for roadside base station radio connection, at first need to find all standing roadside collection of base stations Ω=R '₁, R '₂... R '₁, l is all standing roadside total number of base; Each element of this set is the optimum roadside collection of base stations of disposing of son; Then find an optimal solution R ' in this set₁, it is minimum that this optimal solution satisfies the roadside number of base stations of disposing.Because this problem can be converted into a following linear programming problem:

$\min \underset{i=1}{\overset{m}{\mathrm{\Σ}}}{X}_i$

$s.t.\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{m}{\mathrm{\Σ}}}{D}_{\mathrm{ij}}\×X_i\×X_j\≤T$

Wherein, m represents to dispose the number of both candidate nodes, X_i, X_jRepresent whether i and j both candidate nodes dispose the base station, roadside.

Because this problem is the NP-hard problem, propose the roadside base station radio and connect and dispose (ORP-W) algorithm, be divided into two stages, be respectively ORP-W stage 1 algorithm and ORP-W stages 2 algorithm is successively carried out.Wherein, wireless connections are disposed (ORP-W)stage 1 specific algorithm flow chart as shown in Figure 4.

In Fig. 4, R is used for recording candidate roadside collection of base stations, and T is the time-delay boundary, R ' ' is the base station deployment set of sub optimum roadside, Ω is the set of sub optimum roadside base station deployment set, and each element R ' ' wherein is the optimum roadside base station deployment set of son, and arthmetic statement is as follows:

Step1: input candidate roadside collection of base stations R, time-delay boundary T forwards Step2 to;

Step2: calculate base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward Step3 to;

Step3: judge base station, roadside v_iWhether belong to candidate roadside collection of base stations R, if so, then calculate v_iExpansion vertex covering set ECV_T(v_i) and expansion limit covering collection ECE_T(v_i), forward Step4 to; Otherwise, forward Step5 to;

Step4: be i+1 with the i assignment, turn Step3;

Step5: the content of initialization set omega is empty, namely

The content of initialization set Ψ is candidate roadside collection of base stations R, and namely Ψ=R forwards Step6 to;

Step6: judge whether set Ψ is not equal to sky and (is designated as among the figure

), if so, then the optimum roadside of initial beggar base station deployment set R ' ' is empty, forwards Step7 to; Otherwise, export the set omega of optimum roadside base station deployment set, algorithm finishes.

Step7: judge whether candidate roadside collection of base stations R (is not designated as among the figure for empty

), if be not empty, then calculate the optimum node v that disposes_Best=max{ECE_T(v_i), the optimum of selecting is disposed node v_BestAdd among the sub optimum roadside base station deployment set R ' ', i.e. R ' '=R ' ' ∪ { v_Best.Then, from the collection of base stations R of candidate roadside, take out v_BestThe node that covers of extension point, namely R=R ECV_T(v_Best), until candidate roadside collection of base stations R is empty; If candidate roadside collection of base stations R is empty, forward Step8 to;

Step8: the optimum that will select is disposed node v_BestRemove the Ψ from set, namely Ψ=Ψ v_Best, the optimum roadside of son base station deployment set R ' ' is added in the set omega, namely Ω=Ω ∪ R ' ' forwards Step6 to.

Wireless connections are disposed (ORP-W) stages 2 specific algorithm flow chart as shown in Figure 5.

In Fig. 5, Ω is the set of sub optimum roadside base station deployment set, and T is the time-delay boundary, and R ' ' is the base station deployment set of sub optimum roadside, R_OptBe the optimum deployment set of wireless connections Deployment Algorithm, arthmetic statement is as follows:

Step1: input the set omega of sub optimum roadside base station deployment set, time-delay boundary T forwards Step2 to;

Step2: judge that whether sub optimum roadside base station deployment set R ' ' belongs to set omega, if so, then forwards Step3 to; Otherwise, forward Step7 to;

Step3: judge base station, roadside v_iAnd v_jThe no sub optimum roadside base station deployment set R ' ' that belongs to if so, forwards Step4 to; Otherwise, forward Step2 to;

Step4: calculate base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward Step5 to;

Step5: judge D_IjWhether less than time-delay boundary T, if so, forward Step6 to; Otherwise, forward Step3 to.

Step6: the optimum roadside of son base station deployment set R ' ' is taken out from set omega, namely Ω=Ω R ' ', then forward Step2 to;

Step7: intiating radio connects the optimum deployment set R of Deployment Algorithm_Opt, with R_OptAssignment is sub optimum roadside base station deployment set R ' ', i.e. R_Opt=R ' ' forwards Step8 to;

Step8: judge that whether sub optimum roadside base station deployment set R ' ' belongs to set omega, if so, turns Step9; Otherwise, output R_Opt, algorithm finishes;

Step9: judge that whether the interstitial content of sub optimum roadside base station deployment set R ' ' is less than or equal to optimum deployment set R_OptInterstitial content, namely | R''|＜=| R_Opt|, if so, with optimum deployment set R_OptAssignment is sub optimum roadside base station deployment set R ' ', i.e. R_Opt=R ' ' forwards Step8 to, if otherwise directly forward Step8 to.

Specific embodiment described herein only is to the explanation for example of the present invention's spirit.Those skilled in the art can make various modifications or replenish or adopt similar mode to substitute described specific embodiment, but can't depart from spirit of the present invention or surmount the defined scope of appended claims.

Claims (1)

1. base station, the roadside optimal deployment method under the time-delay terminal conditions among the VANET is characterized in that, may further comprise the steps:

One, at first objective definition is given time-delay boundary T, and how optimum base station, deployment roadside guarantees emergency message all nodes in the car networking that T propagated in the time;

Two, definition mileage chart G=(V, E), the figure Point Set is V={v₁, v₂..., v_m, v_iThe both candidate nodes that represents all deployment, quantity are m, and the value of i is 1,2 ... m; The limit integrates as E={e₁, e₂..., e_n, e_jThe set of expression road, quantity is n, the value of j is 1,2 ... n, wherein the weights e (v on every limit_i, v_j) be the time-delay d that message is propagated at this road_Ij

Three, definition D_IjBe broadcast to the propagation time under the worst case of other vehicle node for the roadside base-station node that message is disposed from any two candidates;

Four, the expansion vertex covering set of definition base station, roadside is ECV_T(v_x), T is given when the time-delay boundary, and message is from roadside base station v_xPropagate into other base station, roadside, satisfy following formula,

${\mathrm{ECV}}_T\left(v_x\right)=\left\{v_i\right|D_{\mathrm{xi}}\≤T;{\∀v}_i\∈V\}$

Wherein, D_XiThat message is from base station, roadside v_xPropagate into other base station, roadside v_iPropagation time; If the propagation time is less than time-delay boundary T, then base station, roadside v_iBe base station, roadside v_xExpansion vertex covering set ECV_T(v_x) in an element;

Five, definition base station, roadside v_xThe expansion limit cover and to integrate as ECE_T(v_x), satisfy following formula,

${\mathrm{ECE}}_T\left(v_x\right)=\left\{e(v_i,v_j)\right|\begin{array}{c}{v}_i\∈{\mathrm{ECV}}_T\left(v_x\right)^v_j\∈{\mathrm{ECE}}_T\left(v_x\right)^e(v_i,v_j)\∈E;\\ \∀v_i,v_j\∈V\end{array}\}$

Wherein, base station, roadside v_iAnd v_jBase station, roadside v_xExpansion vertex covering set ECV_T(v_x) in two elements, and limit e (v_i, v_j) in the limit collection of mileage chart E (G), limit e (v then_i, v_j) be base station, roadside v_xThe expansion limit cover and to integrate as ECE_T(v_x) in an element;

Six, definition time-delay boundary figure is undirected bigraph (bipartite graph) G '=(V ', E '), and its Point Set is V '=V ∪ V2, and point set V disposes the point set of base station, i.e. V={v for all candidates₁, v₂..., v_m, point set V2={v_E1, v_E2... v_EnThe point set that consists of for all limits of mileage chart; Limit e ' (v among the collection E ' of limit_i, v_EjIf) represent to satisfy under time-delay boundary T vertex v_iCan cover limit e_j, satisfy following formula,

$E^{\′}=\left\{e^{\′}(v_i,v_j)\right|e_j\∈{\mathrm{ECV}}_T\left(i\right);{\∀v}_i\∈V,v_{e_j}\∈V2\}$

Wherein, if limit e_jBase station, roadside v_iThe expansion limit cover collection ECE_T(i) element in, then limit e ' (v_i, v_Ej) be an element among the collection E ' of limit;

Seven, definition all standing roadside collection of base stations is for the situation of roadside base station radio connection, for set R'={v₁, v₂, ..., v_kIn any roadside base station v_iAnd v_j, satisfy following formula,

$D_{\mathrm{ij}}\≤T,{\∀v}_i,v_j\∈R^{\′}$

Wherein, any two roadsides base station v among all standing roadside collection of base stations R'_iAnd v_jSatisfy message from base station, roadside v_iPropagate into other base station, roadside v_jPropagation time D_IjLess than time-delay boundary T;

Eight, for base station, roadside wired connection situation, adopt approximate data, try to achieve the optimum roadside collection of base stations of disposing; Connect for the roadside base station radio, propose the roadside base station radio and connect Deployment Algorithm, try to achieve the optimum roadside collection of base stations of disposing;

The described approximate data implementation procedure that adopts for base station, roadside wired connection situation is as follows,

R is used for recording candidate roadside collection of base stations, and T is the time-delay boundary, and R ' is the base station deployment set of optimum roadside, carries out following substep,

Step 1, input candidate roadside collection of base stations R, time-delay boundary T forwards step 2 to;

Step 2 is calculated base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward step 3 to;

Step 3 is judged base station, roadside v_iWhether belong to candidate roadside collection of base stations R, if so, then calculate v_iExpansion vertex covering set ECV_T(v_i) and expansion limit covering collection ECE_T(v_i), turn step 4; Otherwise, forward step 5 to;

Step 4 is i+1 with the i assignment, turns step 3;

Step 5, the optimum roadside of initialization base station deployment set R ' is empty, forwards step 6 to;

Step 6 judges that candidate roadside collection of base stations R whether not for empty, if be not empty, then calculates the optimum node v that disposes_Best=max{ECE_T(v_i), the optimum of selecting is disposed node v_BestAdd among the optimum roadside base station deployment set R ', i.e. R '=R ' ∪ { v_Best; Then, from the collection of base stations R of candidate roadside, take out v_BestThe node that covers of extension point, namely R=R ECV_T(v_Best), until candidate roadside collection of base stations R is empty; If candidate roadside collection of base stations R is empty, export optimum roadside base station deployment set R ', finish;

Connect the roadside base station radio connection Deployment Algorithm that proposes for the roadside base station radio and comprise the 1st stage flow process and the 2nd stage flow process,

The 1st stage flow process implementation procedure is as follows,

R is used for recording candidate roadside collection of base stations, and T is the time-delay boundary, and R ' ' is the base station deployment set of sub optimum roadside, and Ω is the set of sub optimum roadside base station deployment set, carries out following substep,

Step 1, input candidate roadside collection of base stations R, time-delay boundary T forwards step 2 to;

Step 2 is calculated base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward step 3 to;

Step 3 is judged base station, roadside v_iWhether belong to candidate roadside collection of base stations R, if so, then calculate v_iExpansion vertex covering set ECV_T(v_i) and expansion limit covering collection ECE_T(v_i), forward step 4 to; Otherwise, forward step 5 to;

Step 4 is i+1 with the i assignment, turns step 3;

Step 5, the content of initialization set omega are empty, namely

The content of initialization set Ψ is candidate roadside collection of base stations R, and namely Ψ=R forwards step 6 to;

Step 6 judges whether set Ψ is not equal to sky, and if so, then the optimum roadside of initial beggar base station deployment set R ' ' is empty, forwards step 7 to; Otherwise, export the set omega of optimum roadside base station deployment set, algorithm finishes;

Step 7 judges that candidate roadside collection of base stations R whether not for empty, if be not empty, then calculates the optimum node v that disposes_Best=max{ECE_T(v_i), the optimum of selecting is disposed node v_BestAdd among the sub optimum roadside base station deployment set R ' ', i.e. R ' '=R ' ' ∪ { v_Best; Then, from the collection of base stations R of candidate roadside, take out v_BestThe node that covers of extension point, namely R=R ECV_T(v_Best), until candidate roadside collection of base stations R is empty; If candidate roadside collection of base stations R is empty, forward step 8 to;

Step 8 is disposed node v with the optimum of selecting_BestRemove the Ψ from set, namely Ψ=Ψ v_Best, the optimum roadside of son base station deployment set R ' ' is added in the set omega, namely Ω=Ω ∪ R ' ' forwards step 6 to;

The 2nd stage flow process implementation procedure is as follows,

Ω is the set of sub optimum roadside base station deployment set, and T is the time-delay boundary, and R ' ' is the base station deployment set of sub optimum roadside, R_OptBe the optimum deployment set of wireless connections Deployment Algorithm, carry out following substep,

Step 1 is inputted the set omega that sub optimum roadside base station deployment is gathered, and time-delay boundary T forwards step 2 to;

Step 2 judges that whether sub optimum roadside base station deployment set R ' ' belongs to set omega, if so, then forwards step 3 to; Otherwise, forward step 7 to;

Step 3 is judged base station, roadside v_iAnd v_jThe no sub optimum roadside base station deployment set R ' ' that belongs to if so, forwards step 4 to; Otherwise, forward step 2 to;

Step 4 is calculated base station, roadside i to the Information Communication time-delay D of base station, roadside j_Ij, forward step 5 to;

Step 5 is judged D_IjWhether less than time-delay boundary T, if so, forward step 6 to; Otherwise, forward step 3 to;

Step 6 is taken out the optimum roadside of son base station deployment set R ' ' from set omega, namely Ω=Ω R ' ', then forward step 2 to;

Step 7, intiating radio connects the optimum deployment set R of Deployment Algorithm_Opt, with R_OptAssignment is sub optimum roadside base station deployment set R ' ', i.e. R_Opt=R ' ' forwards step 8 to;

Step 8 judges that whether sub optimum roadside base station deployment set R ' ' belongs to set omega, if so, turns step 9; Otherwise, output R_Opt, algorithm finishes;

Step 9 judges that whether the interstitial content of sub optimum roadside base station deployment set R ' ' is less than or equal to optimum deployment set R_OptInterstitial content, namely | R''|＜=| R_Opt|, if so, with optimum deployment set R_OptAssignment is sub optimum roadside base station deployment set R ' ', i.e. R_Opt=R ' ' forwards step 8 to, if otherwise directly forward step 8 to.

Images