An optimal multiple stopping rule–based cooperative downloading scheme in vehicular cyber-physical systems

Abstract

In vehicular cyber-physical systems, vehicular users are the edge nodes which are far away from the network core. Content accessing and downloading for vehicular users are expected to heavily rely on the deployment of RoadSide Units in vehicular cyber-physical systems. Although vehicular users can obtain a good content downloading service in the coverage of RoadSide Units, user experience will get worse in highway scenarios, where RoadSide Units are sparsely deployed at service areas or gas stations. In other words, the download process has a property of intermittent connectivity because many no-signal areas (dark areas) exist on the road. In this article, we try to address such shortcomings by exploiting other edge nodes (vehicles) to download contents for clients in dark areas. Considering the cooperation intention of vehicles, we first propose an incentive mechanism to stimulate vehicles to participate in cooperative downloading. Next, with an objective of maximizing the utilization of benefits, we formulate the cooperative vehicle selection problem as an optimal multiple stopping problem and derive the optimal multiple stopping rule for cooperative downloading. Finally, an extensive simulation study has been performed to investigate the effectiveness of our scheme. The results reveal the impact of different parameters on system requirements and demonstrate that the proposed scheme can maximize the throughput of content downloading in dark areas.

Keywords

Vehicular cyber-physical systems cooperative downloading optimal multiple stopping incentive mechanism

Introduction

Cyber-physical systems (CPS) are complex networks of embedded systems, aiming to transit the physical world into the cyber world.^1,2 Vehicular cyber-physical systems (VCPS)³ are typical CPS applied to the Internet of Things (IoT). They have been proved to hold great potentials in enhancing vehicle safety⁴ and improving traffic efficiency.^5–7 In addition, some large data services onboard should not be ignored either (e.g. local maps downloading or multimedia files downloading). Therefore, for vehicular users, with an increasing demand for downloading contents from the Internet, VCPS have further been envisioned for making a contribution to passengers comfort by providing content downloading services.^8–11

Normally, in VCPS, vehicular users are the edge nodes which are far away from the network core (i.e. cloud computing servers). They can download contents from the Internet via the edge of the cloud, RoadSide Units (RSUs). A good user experience can be achieved within the coverage of RSUs which is about 300–1300 m.¹² However, in highway scenarios, RSUs are mainly deployed at service areas or gas stations which are 8–16 km apart. It is impossible to expect a high number of well-deployed RSUs due to cost restrictions and high maintenance overhead. Therefore, many dark areas exist out of the RSUs’ coverage range which may cause intermittent connectivity for vehicular users. In other words, if a vehicular client leaves the coverage of a RSU without finishing downloading contents, it may waste much time to wait for contacting the next RSU.

Previous work on content downloading in VCPS proposes cooperative downloading methods to utilize edge nodes (i.e. other vehicular users) and reduce the effect on intermittent connectivity in dark areas.^13,14 It means when a vehicular client drives in a dark area without finishing the whole downloading, these unfinished contents are then delegated to cooperative vehicles and further transmitted to clients by a carry-and-forward mechanism¹⁵ in dark areas. However, those works ignore the cooperative intention of vehicles and the optimization of the whole cooperative downloading process. In order to fill such a gap and further develop the tremendous potential of edge nodes, two questions should be taken into consideration: (1) How to motivate vehicles to participate in cooperative downloading? (2) How to maximize the downloading throughput in dark areas?

To answer these two questions, we first model the process of cooperative downloading as a transaction, where clients should supply some benefits for cooperative downloading services and cooperative vehicles can acquire a certain amount of rewards by transmitting contents for clients. This mechanism can arise vehicles’ motivation to cooperative downloading. Moreover, considering the limited benefits supplied by clients, we focus on maximizing the downloading throughput and reducing the cooperative vehicle selection duration by optimizing the process of vehicle selection. To be more specific, we formulate the cooperative vehicle selection problem as an optimal multiple stopping problem, with an objective of maximizing the utilization of the benefits supplied by clients.

The main contributions of this article can be summarized as follows:

We propose a cooperative downloading scheme in medium access control (MAC) layer to develop the tremendous potential of edge nodes and achieve the content downloading service in dark areas.

We formulate the cooperative vehicle selection problem as a multiple stopping problem and address the challenge via our derived optimal multiple stopping rule.

For the purpose of keeping the system’s fairness and encouraging vehicles to participate in cooperative downloading, we explore an incentive mechanism based on a benefits transaction strategy.

The rest of the article is organized as follows. The related work is reviewed in section “Related work.” We present our system model in section “System model.” Section “Efficient incentive mechanism for cooperative downloading” discusses the incentive mechanism we proposed. Our optimal multiple stopping rule–based cooperative downloading scheme is detailed in section “Optimal multiple stopping rule for cooperative downloading.” Section “Performance evaluation” evaluates the performance of the proposed scheme through a simulation study. Finally, section “Conclusion” concludes this article.

Related work

Content downloading in VCPS has attracted extensive research attention. There are mainly two schemes for achieving the content downloading service in VCPS: no-cooperative downloading and cooperative downloading. Some researchers focused on no-cooperative schemes.^16,17 Eriksson et al.¹⁶ improved the downloading performance by optimizing both the connection establishment procedure (QuickWiFi) and the cabernet transport protocol (CTP). In the work by Zhang et al.,¹⁷ the authors studied data scheduling issues for content downloading. However, these no-cooperative schemes ignore the tremendous downloading potential of edge nodes on the network. Taking this situation into consideration, cooperative downloading schemes were proposed by Chen and Chan¹³ and Trullols-Cruces et al.¹⁴ Chen and Chan¹³ proposed a method of combining WiFi with wireless wide area network (WWAN) to achieve the cooperative downloading. Trullols-Cruces et al.¹⁴ addressed the cooperative downloading issue by introducing a delay-cooperative Automatic Repeat reQuest (ARQ) mechanism and a vehicular route predictability–based carry-and-forward mechanism. Nevertheless, these schemes just proposed a framework for cooperative downloading in different environments but did not give a detail algorithm for cooperative downloading.

Recent research works^18–21 paid more attention on optimized algorithms about every process of cooperative downloading. The authors in the works by Ota et al.¹⁸ and Yang et al.,¹⁹ respectively, focused on the data flow scheduling problem and cross-layer designs but how to select cooperative vehicles was not discussed. A cooperative vehicle selection method was proposed by Trullols-Cruces et al.²⁰ This approach selected the cooperative vehicle by utilizing history records to predict the route and the meeting time between clients and cooperative vehicles. Our work differs from this approach in that we focus on highway scenarios. These scenarios were also considered by the authors in the work by Liu et al.,²¹ and they scheduled the dark areas out of the coverage of RSUs and utilized the passing vehicles running in dark areas to help the downloading. Note that all the works mentioned above did not consider the vehicles’ willingness of participating in cooperative downloading, which might cause the selfish behavior. In this article, considering the selfish behavior of vehicular users, we propose an incentive mechanism for cooperative downloading. Moreover, our approach can maximize the downloading throughput by formulating the cooperative vehicle selection problem as an optimal multiple stopping problem.

System model

As depicted in Figure 1, we consider a straight dual carriageway scenario with multi-lane and sparsely deployed RSUs. Each RSU gets a certain coverage range in which vehicular users can obtain content downloading services. Because of the limitation of the RSUs’ coverage, many no-signal areas (i.e. dark areas) exist on the road. Thus, the download process has an intermittent connectivity. We consider two kinds of traffic forward mechanisms in our system: connected forward (i.e. traffic transmitting through a connected multi-hop path) and carry-and-forward (i.e. traffic transmitting through vehicles that store and carry the data before delivering them to the target client). As described by Malandrino et al.,²² connected forwarding and carry-and-forward are limited to two hops from RSUs since this already yields nearly optimal performance. For this reason, we only consider the two-hop situation in this article. Meanwhile, nodes in our system share the channel bandwidth allocated for service applications following the IEEE 802.11p standard.²³ Note that the time delay of communication, calculation, and contents searching are ignored in this article because the time delay is short enough when compared with the duration of cooperative downloading.

Figure 1.

System model.

The components of our system are detailed as follow:

Vehicles are the edge nodes which are far away from the network core. Each vehicle has a certain amount of resource (e.g. bandwidth and storage space). They can obtain the location information at any time with equipped global positioning system (GPS) devices. We assume that vehicles travel nearly at a constant velocity, and the routes of vehicles can be predicted (similar to the assumptions made in the works by Chen and Chan,¹³ Trullols-Cruces et al.,¹⁴ and Liu et al.²¹). Two kinds of vehicles exist in our system: clients (i.e. vehicles that require help to download contents from the Internet) and cooperative vehicles (i.e. vehicles that willing to offer their bandwidth to download contents for clients). Vehicles communicate with each other by vehicle-to-infrastructure communications (V2I) or vehicle-to-vehicle communications (V2V). Once a vehicle moves into the coverage of a RSU, it would initiatively upload the basic information to the RSU. In addition, energy consumption during the communication is neglected in our system owing to sufficient power supplied by vehicles.

RSUs are the edge of the cloud. They are connected via backbones and obtaining contents via the Internet. Here, we assume that any downloading request from clients to RSUs is available. Meanwhile, each RSU attaches to background servers and shares the basic transportation information with them. Besides, the bandwidth of RSUs is much larger than vehicles; RSUs enable to transfer data packets to multiple vehicles simultaneously.

RSUs have two main functions: (1) collecting the basic information of vehicles in their coverage and uploading them to background servers and (2) searching the relevant contents on the Internet and delegating these contents to clients and selected cooperative vehicles. The set of cooperative vehicles are denoted as $O = {(i d_{1}, t_{1}, v_{1}, B_{1}, E_{1}, C B_{1}, C E_{1}), \dots, (i d_{i}, t_{i}, v_{i}, B_{i}, E_{i}, C B_{i}, C E_{i})}$ . These items, respectively, represent the ID of the ith vehicle, its register time, velocity, the time it meets the client, the time it leaves the communication range of the client, the beginning time of the cooperative downloading, and the end time of the cooperative downloading. The relevant calculation of these items would be described in section “Optimal multiple stopping rule for cooperative downloading.”

Servers are deployed on backbones. They are the cloud computing servers which provide security and calculation services. For the security services in our system, servers act as a trusted third party which are similar to a bank. Servers are directly involved in any transaction and provide a real-time security guarantee to vehicular users. To identify vehicles in our system, we assume that each vehicle has a certificate issued by servers such as those proposed in the works by Dahshan and Irvine²⁴ and Zhong et al.²⁵ However, for calculation services, servers act as a central processor. Thus, the relevant optimal selection algorithm is efficiently orchestrated on servers.

Efficient incentive mechanism for cooperative downloading

In typical VCPS, vehicles are constrained by their limited bandwidth and storage space. Some vehicular users are not willing to help the client to cooperatively transfer data when considering their own benefits. In order to avoid the vehicular users’ selfish behavior, we propose an incentive mechanism base on a benefits transaction strategy. In this section, we intend to define our benefits transaction strategy and discuss how to transact between vehicles via this strategy.

Designs of transaction strategy

In this article, the system would allocate a certain number of benefits (e.g. bandwidth resource credentials) to every vehicular user at the beginning stage. Vehicles can use them to get high-speed content services within the coverage of RSUs. Normally, clients would consume some benefits to achieve the cooperative downloading service. Besides, cooperative vehicles can acquire benefits by helping to cooperatively download contents in dark areas. Once the benefits are used up, a vehicular user cannot enjoy the cooperative downloading service any more. There are two ways for a vehicular user to get more benefits. First, a vehicular user can buy more benefits by using some real money. However, the preferred and dominant way to get more benefits is by acting as a cooperative vehicle and forwarding others’ contents. Generally, this mechanism can motivate idle vehicles to participate in cooperative downloading because these vehicles have a lot of idle resources (e.g. storage space) for earning more benefits. Under these circumstances, we assume vehicles in the system are all willing to cooperatively download contents for others to earn more benefits.

To offer a consumption guidance to clients, once a RSU receives the downloading request from a client, it would estimate the expense C of the cooperative downloading service and then send it to the client for offering a reference. The reference expense is an interval, where the minimum and the maximum expenses can, respectively, be formulated as

Cos t_{\min} = \frac{M ε}{\frac{L w_{rv}}{v_{\min}}} = \frac{M ε v_{\min}}{L w_{rv}}

(1)

Cos t_{\max} = \frac{M ε}{\frac{L w_{rv}}{v_{\max}}} = \frac{M ε v_{\max}}{L w_{rv}}

(2)

where $w_{rv} = W_{rv} \cdot (1 - q)$ denotes the real transmission rate between RSUs and vehicles. $W_{rv}$ and q, respectively, denote the theoretical transfer rate and packet loss rate. L is the RSUs’ coverage. M is the size of the cooperative downloading contents. $ε$ is the unit benefit of the cooperative downloading service (i.e. reward which a cooperative vehicle helps to transmit contents). Meanwhile, as the velocity of vehicles is limited in highway scenarios, $v_{\min}$ and $v_{\max}$ are known for us.

Next, the system would identify the number of cooperative vehicles N which should be selected. It can be calculated by

N = \frac{C}{ε}

(3)

Then, RSUs work together with servers and select N cooperative vehicles which can achieve the maximum cooperative downloading throughput in the dark area by the optimal selection algorithm.

The whole efficient incentive mechanism for cooperative downloading is presented in Algorithm 1.

Algorithm 1 The efficient incentive mechanism.
Initialization:
Allocate a certain number of benefits to every vehicular user;
1: while Receive a downloading request do
2: Estimate the expenses $[Cos t_{\min}, Cos t_{\max}]$ ;
3: Inquire the intention of cooperative downloading;
4: if Intention = Truethen
5: Collect the benefits supplied by the client;
6: Identify the number of cooperative vehicles N;
7: else
8: Break;
9: end if
10: Go to Algorithm 2 to select N cooperative vehicles;
11: Allocate the relevant benefits to selected cooperative vehicles;
12: end while

Exceptional cases

Case 1

If the movement state and the transmission condition are invariant, our optimal selection algorithm runs smoothly in the whole process. This ideal situation can achieve the maximum cooperative downloading throughput. However, vehicles’ states are influenced by many factors, such as weather conditions and driving behaviors. In this condition, if the system allocates the benefits to a cooperative vehicle that does not transmit corresponding contents to the client for some reason, it would damage the benefits of clients. In order to ensure the fairness of the system, the relevant benefits supplied by clients would be temporarily stored in servers until the client contacts the next RSU. By then, the client would tell the RSU which packets it has received in the dark area. The system can judge which vehicles really help cooperative downloading and further allocate the relevant benefits to them. In the worst, the cooperative vehicle cannot acquire any reward due to the specified cooperative downloading task is unfinished. Obviously, some contents may certainly fail to be downloaded during one dark area. The unfinished part of contents should continually be downloaded when the client enters the next RSU’s coverage.

Case 2

If the size of the required contents is big enough that cannot be completely downloaded in the following dark area (i.e. the number of required cooperative vehicles is large enough), RSUs would tell the client this situation and further inquire the intention of cooperative downloading. This judgment process can be given by $Cos t_{\min} / α \geq (T_{dur} + T_{c}) / μ = (L_{da} + L) / v_{0} μ$ , where $T_{dur}$ is the duration that a client travels in the dark area and $T_{c}$ is the duration that a client travels in one RSU’s coverage. $L_{da}$ denotes the length of a dark area, $v_{0}$ is the client’s velocity, and $μ$ represents the traffic density. Obviously, more expenses mean more contents can be obtained in one dark area. However, with no need for wasting more benefits, clients only need to pay for the cooperative downloading service according to their own circumstances. For example, if the required contents are video streaming²⁶ and the time duration of the downloading video is longer than the traveling time in the dark area, there is no need for the client completes the whole downloading process in one dark area.

Optimal multiple stopping rule for cooperative downloading

With the limited benefits supplied by clients, in order to select a certain number of cooperative vehicles and ensure the relevant throughput is maximum, we formulate the cooperative vehicle selection problem as an optimal multiple stopping problem. In this section, we intend to detail our optimal multiple stopping rule for cooperative downloading.

Problem description

We assume synchronous timers are equipped on RSUs and background servers. Meanwhile, we use RSU1 to denote the RSU which a client sends the content downloading request to. And RSU2 denotes the next RSU which the client would pass by. Once RSU1 receives a downloading request from a client, the system begins to undertake timing. As the road has two directions, whether vehicles travel in the same direction with the client or not, they both can be the candidates of cooperative vehicles. Thus, we, respectively, denote the time duration of the same direction cooperative downloading and the opposite direction cooperative downloading as $T_{S}$ and $T_{O}$ . When the client’s velocity is known, the upper bounds of $T_{S}$ and $T_{O}$ are existent, and we can formulate them as follows

T_{Omax} = \frac{L + L_{da}}{v_{0}} - \frac{L - d}{v_{\max}}

(4)

T_{Smax} = \frac{L + L_{da}}{v_{0}} - \frac{L + L_{da} - d}{v_{\max}}

(5)

where $0 < T_{Smax} < T_{Omax}$ and d is the communication range between two vehicles.

As illustrated in Figure 2, it is assumed that the cooperative vehicle selection is performed in every time slot. RSU1 and RSU2 are, respectively, in charge of the same direction cooperative downloading and the opposite direction cooperative downloading. We divide the cooperative downloading duration ( $T_{Smax}$ and $T_{Omax}$ ) into several components. Let $τ$ be the minimum unit of time slots which equals 0.1 s. RSU1 and RSU2 would calculate the corresponding reward of every time slot and send them to background servers in real time. Meanwhile, servers would integrate the reward of every time slot and maintain a new time slot list in order to process the optimal selection algorithm to select cooperative vehicles.

Figure 2.

An illustration of time slots.

Note that the time difference is certainly existing when two vehicles successively arrive in our system, and every time slot is short enough. Therefore, we assume that at most one vehicle exists in a time slot. In other words, we map the vehicles into the time slots and find high-reward cooperative vehicles by observing a series of time slots.

Problem formulation

With the limited benefits supplied by clients, the system should select N cooperative vehicles for cooperative downloading. The question is how to maximize the download throughput of N selected vehicles. The most intuitive way is to calculate the download throughput of each vehicle and select N vehicles with the maximum download throughput. Nevertheless, it is impossible to simultaneously calculate the download throughput of whole vehicles on the road because of the limited coverage of RSUs and the mobility of vehicles. In that case, we cannot utilize the intuitive method to select cooperative vehicles. Furthermore, since vehicles will arrive in the coverage of RSUs successively on the highway scenarios, the system needs to decide whether to select the vehicles as cooperative ones. Thus, the cooperative vehicle selection problem can be summarized as a sequential decision problem which can be solved by the stopping theory. For the traditional stop theory,⁶ there is always only one solution for the optimization objective. In this article, however, we intend to obtain several cooperative vehicles (also called as multiple solutions) to achieve the goal of our system. Here, we formulate the cooperative vehicle selection problem as a multiple stopping problem. Furthermore, in our scheme, system observes candidate vehicles one by one based on an observation time slots sequence. After observing a time slot, the system decides whether to stop and select the vehicle in the current time slot as a cooperative vehicle or not. The observation comes to the end once the system finishes selecting N cooperative vehicles.

When the system makes a decision, it focuses on how to maximize the sum reward of the whole selection. We assume the system has selected l cooperative vehicles before observing the ith time slot. If it selects the vehicle in the current time slot, it can acquire the reward denoted by $y_{i} + V_{i}^{N - l - 1}$ , where $y_{i}$ represents the instantaneous reward of the ith time slot and $V_{i}^{N - l - 1}$ represents the expected reward of $(N - l - 1)$ cooperative vehicles to be selected from the remaining time slots. If the system does not select the vehicle in the current time slot, it can acquire an expected reward $V_{i}^{N - l}$ . When the reward with selecting the vehicle in the current time slot is larger than the one without selecting it, the system makes a stop, and vice versa. Therefore, the multiple vehicles selection problem can be further formulated as a sequential decision problem which can be solved by optimal multiple stopping rules.

Obviously, the reward of every time slot is an important parameter. In order to further investigate it, we first focus on the vehicle information that RSUs have collected. In our model, the velocity of vehicles is nearly constant. However, in real environment, because of many kinds of factors (e.g. road conditions), the velocity may change slightly. Therefore, we divide the velocity into U intervals to discretize it, where $U = v_{\max} - v_{\min}$ , and the velocity thresholds are represented by $V = {v_{1} = 60 km / h, v_{2} = 61 km / h, \dots, v_{u} = 120 km / h}$ . If an instantaneous velocity v is in $[v_{i}, v_{i + 1})$ , the velocity of the vehicle is said to be in state i. Moreover, the probability of the vehicle velocity being in state i can be given by $p_{i} = 1 / (v_{\max} - v_{\min})$ .

Generally, once a client launches the cooperative downloading, RSUs first calculate the duration that the client travels in their coverage $T_{c}$ and the communication duration between the client and every cooperative vehicle $C D_{i}$ , which can be formulated as

C D_{i} = \frac{w_{rv}}{w_{vv}} \times \frac{L}{v_{i}}

(6)

where $w_{vv} = W_{vv} \cdot (1 - q)$ denotes the real transmission rate between two vehicles. $W_{vv}$ and q, respectively, denote the theoretical transfer rate and the packet loss rate. Then, the system begins to observe time slots. Here, we use $s_{i}$ to denote the ith time slot the system observes. To derive the reward of the vehicle in $s_{i}$ , we should consider two different situations.

Same direction cooperative downloading

RSU1 is responsible for same direction cooperative downloading. It collects the vehicle’s basic information in real time. Because the cooperative downloading can only occur in dark areas, when RSU1 observes the vehicle in the current time slot $s_{i}$ at $t_{i}$ , the formula of $B_{i}$ and $E_{i}$ would vary since different $v_{i}$ and $t_{i}$ . We can formulate them as follows

{\begin{matrix} B_{i} = t_{i}, E_{i} = B_{i} + \frac{d - t_{i} v_{0}}{v_{0} - v_{i}} if v_{i} < v_{0} and t_{i} v_{0} < d \\ B_{i} = t_{i}, E_{i} = B_{i} + \frac{2 d - t_{i} v_{0}}{v_{i} - v_{0}} if v_{i} > v_{0} and t_{i} v_{0} < d \\ B_{i} = t_{i} + \frac{t_{i} v_{0} - d}{v_{i} - v_{0}}, E_{i} = B_{i} + \frac{2 d}{v_{i} - v_{0}} if v_{i} > v_{0} and t_{i} v_{0} \geq d \end{matrix}

(7)

Note that if $v_{i} = v_{0}$ and $t_{i} v_{0} \leq d$ , the cooperative vehicle is always in the communication range of the client and then all carried contents can be transferred to the client. For the rest cases, such as $v_{i} < v_{0}$ and $t_{i} v_{0} \geq d$ or $v_{i} = v_{0}$ and $t_{i} v_{0} > d$ , the vehicle in the current time slot cannot communicate with the client in the following dark area, and thus, the reward of $s_{i}$ equal 0.

Now, we can further derive $C B_{i}$ and $C E_{i}$ of same direction vehicles in $s_{i}$ as follows

\begin{matrix} C B_{i} = Max {T_{c}, B_{i}} \\ C E_{i} = Min {E_{i}, C B_{i} + C D_{i}, \frac{L + L_{da}}{v_{0}}} \end{matrix}

(8)

Opposite direction cooperative downloading

RSU2 is responsible for opposite direction cooperative downloading. Because every opposite direction vehicle has an opportunity to meet the client, we can simplify the $B_{i}$ and $E_{i}$ of opposite direction vehicles as follows

\begin{matrix} B_{i} = t_{i} + \frac{L_{da} + 2 L - d - t_{i} v_{0}}{v_{0} + v_{i}} \\ E_{i} = B_{i} + \frac{2 d}{v_{0} + v_{i}} \end{matrix}

(9)

Thus, we further have

\begin{matrix} C B_{i} = B_{i} \\ C E_{i} = Min {E_{i}, C B_{i} + C D_{i}, \frac{L + L_{da}}{v_{0}}} \end{matrix}

(10)

After deriving the contact time between cooperative vehicles and the client, the cooperative downloading throughput of the vehicle in $s_{i}$ can be calculated by

D_{i} = (C E_{i} - C B_{i}) w_{vv}

(11)

Then, we deduce the instantaneous reward function $Y_{i}$ , which is basing on the valid downloading throughput and two observing factors: the ID of the current time slot i and the number of stopping times l. First, we denote $e (i, l)$ as the observing function which can be formulated as

e (i, l) = 1 - \frac{i (N - l)}{Q}

(12)

where Q is a variable parameter according to clients’ requests. From equation (13), we know that $e (i, l)$ is a decreasing function of i and an increasing function of l. In other words, a larger number of observed time slots mean lower efficiency of the cooperative download process. More selected cooperative vehicles mean less times of stop left and the relevant efficiency of cooperative downloading becomes higher. Therefore the reward after the ith observation can be given by

Y_{i} = e_{i} D_{i}

(13)

To sum up, we generalize the optimal multiple stopping problem for cooperative downloading as follows: when the system receives the reward $Y_{i}$ after the ith observation, it makes a decision on whether to make a stop and select the vehicle in the current time slot or not. The system finally stops the observation till N cooperative vehicles are all selected. Note that recall is not allowed since the mobility of vehicles in VCPS.

Optimal multiple stopping rule

In this subsection, we first solve the multiple stopping problem by deriving the optimal stopping rule that decides when to stop. Then, we prove the proposed rule is better than the random stopping rule.

We denote $F_{i}$ as the probability distribution function of the instantaneous reward $Y_{i}$ after the ith observation. According to the description in last subsection, the finite reward sequence $Y_{1}, \dots, Y_{k}$ are independent of each other. Here, we let $V_{i}^{N}$ represent the expected reward of N cooperative vehicles should be selected from remaining time slots after ith observation. For $i = 0, 1, \dots, k - N$ , we first define the formulas by

V_{i}^{0} : = 0

(14)

V_{k - N + 1}^{N} : = - \infty

(15)

V_{i}^{N} : = E [(Y_{i + 1} + V_{i + 1}^{N - 1}) \lor V_{i + 1}^{N} | F_{i}]

(16)

where ∨ represents taking the maximum. Obviously, when $N = 0$ , no cooperative vehicles need to be selected any more, and thus, the expected reward equals 0 which is described in equation (14). When the number of remaining time slots is less than the number of unselected vehicles, it is impossible to select enough cooperative vehicles; thus, it is the worst situation which is described in formula (15). According to formula (16), we know that $V_{i + 1}^{N - 1}$ and $V_{i}^{N}$ can be calculated by backward induction. However, if we want to calculate the value of $V_{i}^{N}$ , we should first know the expected instantaneous reward $E (Y_{i} | F_{i})$ of the vehicle in $s_{i}$ . It can be described as follows

E (Y_{i} | F_{i}) = P_{i} E (Y_{i})

(17)

where $P_{i}$ is the probability of a vehicle appearing within $s_{i}$ and $E (Y_{i})$ represents the expected reward of the vehicle in $s_{i}$ . Here, we assume that vehicle inter-arrival time is an exponential distribution with a mean $1 / μ$ and a density function $f_{I} (t) = μ e^{- μ t}, t \geq 0$ . Therefore, $P_{i}$ is approximately summarized as follows

\begin{matrix} P_{1} = p (τ) \\ P_{2} = p (2 τ) - p (τ) + P_{1} P_{1} \\ P_{3} = p (3 τ) - p (2 τ) + P_{1} P_{2} + P_{2} P_{1} \\ ⋮ \\ P_{i} = p (i τ) - p [(i - 1) τ] + \sum_{j = 1}^{i - 1} P_{j} P_{i - j} \end{matrix}

(18)

where $p (i τ) = 1 - e^{- μ i τ}$ , which represents the probability of a vehicle appears within $i τ$ .

For $E (Y_{i})$ , according to the traffic model, we first assume the probabilities of a vehicle appear in the same direction lane and the opposite direction lane are both 0.5. Then, we have

\begin{matrix} E (Y_{i}) = \frac{1}{2} E_{S} (Y_{i}) + \frac{1}{2} E_{O} (Y_{i}) \\ = \frac{1}{2} e_{i} E_{S} (D_{i}) + \frac{1}{2} e_{i} E_{O} (D_{i}) \\ = \frac{1}{2} e_{i} [\sum_{γ} (D_{Si . γ} \cdot p_{γ}) + \sum_{γ} (D_{Oi . γ} \cdot p_{γ})] \end{matrix}

(19)

where $p_{γ}$ is the probability of the vehicle velocity being in state $γ$ , $γ \in {v | v = 1, 2, 3, \dots, U}$ . From equations (18) and (19), the expected instantaneous reward $E (Y_{i} | F_{i})$ of $s_{i}$ can be summarized. Moreover, according to equations (17)–(19), we calculate the expected reward $V_{i}^{m}$ as follows

\begin{matrix} V_{i}^{N} = E [(Y_{i + 1} + V_{i + 1}^{N - 1}) \lor V_{i + 1}^{N} | F_{i}] \\ = E [(e_{i} D_{i + 1} + V_{i + 1}^{N - 1}) \lor V_{i + 1}^{N} | F_{i}] \\ = \sum_{α} [e_{i} (\frac{1}{2} D_{S (i + 1)} + \frac{1}{2} D_{O (i + 1)}) + V_{i + 1}^{N - 1}] p_{α} \\ + \sum_{β} (V_{i + 1}^{N}) p_{β} \end{matrix}

(20)

where $α \in {v | y_{(i + 1) . v} + V_{i + 1}^{N - 1} \geq V_{i + 1}^{N}, v = 1, 2, 3, \dots, U}$ , $β \in {v | y_{(i + 1) . v} + V_{i + 1}^{N - 1} < V_{i + 1}^{N}, v = 1, 2, 3, \dots, U}$ , subject to: $0 \leq α \leq U, 0 \leq β \leq U, α + β = U$ .

To prove our multiple stopping rule is optimal, we introduce $T_{l}^{N} (n)$ to denote the lth stopping time when the system observes the time slots sequence. Here, we define the relevant stopping time thresholds by

T_{1}^{N} (n) : = \min {n < i \leq k - N + 1 | Y_{i} + V_{i}^{N - 1} \geq V_{i}^{N}}

(21)

\begin{matrix} T_{l}^{N} (n) : = \min {T_{l - 1}^{N} (n) < i \leq k - N + l | Y_{i} + V_{i}^{N - 1} \geq V_{i}^{N - l + 1}} \end{matrix}

(22)

where $1 \leq N \leq k, 0 \leq n \leq k - N$ . It means the lth stop occurs in $T_{l}^{N} (n)$ .

Proposition 1. For multiple stopping problems, ${T_{l}^{N} (n)}$ are optimal N-stopping times in the sense that for arbitrary stopping times $n < T_{1} < \dots < T_{N} \leq k$ . They hold that

E [\sum_{l = 1}^{N} Y_{T_{l}^{N} (n)} | F] \geq E [\sum_{l = 1}^{N} Y_{T_{l}} | F]

(23)

Proof. This proposition is proved by mathematical induction in N. As described above, $Y_{i}$ are independent of each other. When $N = 1$ , we have

\begin{matrix} E [Y_{T_{1}^{1} (n)} | F] = V_{n}^{1} \\ = E [(Y_{n + 1} + V_{n + 1}^{0}) \lor V_{n}^{1} | F] \\ = E {Y_{n + 1} \lor \dots E [(Y_{k - 1}) \lor E (Y_{n}) | F]} \\ \geq (k - n) \cdot \frac{1}{k - n} E [Y_{i} | F] = E [Y_{T_{1}} | F] \end{matrix}

(24)

For the induction step $N \to N + 1$ , according to the induction hypothesis, we acquire that

\begin{matrix} E [Y_{T_{1}} + \dots + Y_{T_{N + 1}} | F] \\ = E [Y_{T_{1}} | F] + E {[Y_{T_{2}} + \dots + Y_{T_{N + 1}} | Y_{T_{1}}] | F} \\ \leq E [Y_{T_{1}^{N + 1} (n)} | F] + E [Y_{T_{1}^{N} (T_{1})} + \dots + Y_{T_{N}^{N} (T_{1})} | F] \\ = E [\sum_{l = 1}^{N + 1} Y_{T_{l}^{N + 1} (n)} | F] \end{matrix}

(25)

Here, Proposition 1 has been proved.

Finally, in order to better understand the process of the optimal multiple stopping rule for cooperative downloading, we define $Z_{i}^{l}$ to be the reward when the system makes a stop and selects the vehicle in the current time slot. That is

Z_{i}^{l} = Y_{i} + V_{i}^{N - l - 1}

(26)

When the system observes the time slot $s_{i}$ , it acquires the reward $Z_{i}^{l}$ and the expected reward $V_{i}^{N - l}$ . Then, it compares the reward $Z_{i}^{l}$ and the expected reward $V_{i}^{N - l}$ . If $Z_{i}^{l} \geq V_{i}^{N - l}$ , it would stop and select the vehicle in the current time slot. Otherwise, it continues observing the next time slot. The basic information of the selected vehicles would be stored in set $S_{a}$ . When N cooperative vehicles have been selected, the whole observation process would be ended. Note that if the system observes the $(k - N + l)$ th time slot with l selected cooperative vehicles, it has to select the vehicles in remaining time slots as the cooperative vehicle regardless of the value of the reward. The whole optimal multiple stopping rule for cooperative downloading is presented in Algorithm 2.

Algorithm 2 The optimal multiple stopping rule.
Initialization:
N Number of cooperative vehicles should be selected;
$l \leftarrow 0$ Number of cooperative vehicles has been selected;
$S = {s_{1}, s_{2}, \dots, s_{k}}$ Observation sequence;
$S_{a}$ Set has been selected.
1: for $i = 1$ to $i = k - N$ do
2: if $N - l = k - i + 1$ then
3: Select the vehicles in $S_{a} \cup {s_{i}, s_{i + 1}, \dots, s_{k}}$ ;
4: Break;
5: else
6: Calculate the instantaneous reward $Y_{i}$ by observing the ith time slot;
7: Calculate the reward $Z_{i}^{l}$ ;
8: Calculate the expected reward $V_{i}^{N - l}$ ;
9: if $Z_{i}^{l} \geq V_{i}^{N - l}$ then
10: Stop at the current time slot and select the vehicle in the current time slot as the cooperative vehicle;
11: Set $S_{a} \leftarrow S_{a} \cup s_{i}, l \leftarrow l + 1;$
12: else
13: Continue;
14: if $l < N$ then
15: Continue;
16: else
17: Break;
18: end if
19: end if
20: end if
21: end for

After selecting N cooperative vehicles, we can obtain the sum reward Y of cooperative downloading, which can be described as

Y = \sum_{i = 1}^{N} Y_{v_{i}}, v_{i} \subseteq S_{a}

(27)

Performance evaluation

In this section, we evaluate the performance of the proposed optimal multiple stopping rule–based cooperative downloading scheme by conducting extensive simulation studies. We first detail the simulation settings which are used to derive our performance result. Then, we investigate the performance comparison between different schemes and analyze the impact of different parameters.

Settings

We set up a large-scale simulation to validate the effectiveness of the proposed scheme. In particular, we consider a straight dual carriageway scenario with multi-lane and sparsely deployed RSUs. It is set that the coverage of RSUs is 800 m and the communication radius of vehicles is 250 m.¹² In accordance with the actual deployment of RSUs at highway service areas or gas stations, the dark area between two RSUs is set to be 8 km. Vehicle inter-arrival times are exponential distribution with the mean $1 / μ$ and vehicle velocities range from 60 to 120 km/h randomly. Considering the impact of the relative velocity, according to the IEEE 802.11p standard, we set 300 kB/s to be the transmission rate between RSUs and clients, 350 and 150 kB/s to be the transmission rates of same direction and opposite direction vehicles, respectively.

Without loss of generally, we set the velocity of the client to be 90 km/h, the corresponding request contents from the client is 80 MB, and the unit price of the cooperative downloading service $ε$ is set to be 1. Thus, the client can further obtain the reference expense ranges from 5 to 11. To explicate the performance of MAC layer scheme, we only conduct the MAC layer simulation and focus on the link-level bit streams rather than the higher layer packets. Note that the numerical results reported in the following subsection are averaged over 200 independent simulations.

Results and analysis

In this subsection, we first evaluate and compare the performance of the proposed scheme, DSRelay²¹ scheme, and the no-cooperative scheme. Then, we investigate the performance evolution of cooperative downloading in different impact parameters.

First, considering a client pays 11 benefits for the cooperative downloading service in the dark area, we compare the amount of data that the client obtained in different schemes. The download process is simulated with the global time going on. As shown in Figure 3, the no-cooperative downloading scheme can only obtain data when the client enters the coverage of RSUs. Obviously, when cooperative downloading schemes are used, more data would be downloaded in the dark area. Compared with using the DSRelay, we can see that the amount of data obtained in the dark area in our scheme is lager. This is because our scheme focuses on selecting the optimal reward of vehicles, while the DSRelay selects the vehicles which are faster than the client. Therefore, DSRelay may lead to the selected vehicle cannot catch up with the client before it enters the next RSU’s coverage.

Figure 3.

The amount of data obtained versus time in different schemes.

Setting the packet loss rate q to 0.05, Figure 4 illustrates a comparison of the completion rates between the proposed scheme and DSRelay. As shown in the bar graph, the completion rate generally decreases with the traffic flow getting sparse. This is reasonable because of the lower probability of finding a high-reward vehicle in sparse traffic flow environments. However, even in different traffic environments, the completion rate in our scheme is still higher than DSRelay. Note that even using the proposed scheme, it is difficult to complete the whole downloading in the dark area between two RSUs. This is because we mainly focus on maximizing the throughput of content downloading in dark areas with the limited benefits supplied by clients.

Figure 4.

The average completion rate versus traffic flow density $μ$ .

Figure 5 reports the effect of the traffic flow density on the amount of data a client obtained in the dark area. As presented in the graph, during 32–352 s, the client travels in the dark area. It can download about 29 MB in the dark area when $μ$ equals 7. If $μ$ is set to 5 and 3, the amount of obtained data, respectively, grows to 34 and 48 MB. Obviously, throughput benefits from higher traffic density since more candidate vehicles can be selected by our optimal multiple stopping rule. Here, we should point out the flat area on the figure. This is because a selected vehicle needs to run a period of time to catch up with the client.

Figure 5.

The amount of data obtained versus time in different traffic flow densities.

Client velocity is an important effect parameter of the throughput. Figure 6 presents the amount of data obtained at different client velocities with the global time going on. Faster velocities mean the client would meet opposite direction cooperative vehicles earlier. However, it also causes that same direction cooperative vehicles have a lower probability to catch up with the client. As described in section “Optimal multiple stopping rule for cooperative downloading,” same direction cooperative vehicles can supply more throughput than opposite ones because of more contact time and higher transmission rate. Therefore, according to the illustration in Figure 6, the velocity of the client is inversely proportional to the total amount of data a client obtained in the dark area.

Figure 6.

The amount of data obtained versus time in different client velocities.

Figure 7 shows the relationship between the selection time and the traffic flow density. According to the graph, the completion time increases with the traffic flow getting sparse. This situation can be interpreted as the system needs more time to wait for a high-reward vehicle in sparse traffic flow environments. At the same time, the expense supplied by clients is another important effect parameter of the completion time. Obviously, more expenses mean more vehicles should be selected by the system. In other words, the system may spend more time to finish selecting cooperative vehicles.

Figure 7.

The average completion time of selections versus traffic flow densities $μ$ .

A comparison of the average reward obtained at different packet loss rates and client’s expenses is presented in Figure 8. We can see that the reward is a decreasing function of the packet loss rate and an increasing function of the client’s expenses. This result indicates that a client would obtain less data in a worse wireless environment and more data if more vehicles help to cooperatively download contents. Note that it is meaningless for a client to supply much more benefits than the reference expense. Because the reward has an upper bound in a dark area which has been described in section “Exceptional cases”.

Figure 8.

The average reward obtained versus packet loss rates q.

From these simulation results, we can see that our cooperative downloading scheme can achieve a good performance in dark areas. If a client wants to achieve better downloading throughput, a higher traffic density and a better communication environment are needed. At the same time, it can also try control its velocity and supply more benefits to achieve the same goal.

Conclusion

In this article, we have proposed an optimal multiple stopping rule–based cooperative downloading scheme in the MAC layer of the VCPS to utilize the edge nodes on the network and further achieve the content downloading service in dark areas. To maximize the downloading throughput and reduce the cooperative vehicle selection duration, we have formulated the problem of cooperative vehicle selection as an optimal multiple stopping problem and derived the optimal multiple stopping rule for cooperative downloading. Focusing on the cooperation intention of vehicles, an efficient incentive mechanism is proposed to stimulate vehicles to participate in cooperative downloading. Through theoretical analysis and extensive simulation, our scheme is demonstrated to be able to maximize the utilization of benefits in the dark area.

In future, we intend to introduce the proposed cooperative downloading scheme into the cross-layer design to improve the system overall throughput. In that case, we also exploit the systematic simulator to evaluate the completed design.

Footnotes

Acknowledgements

The authors thank all reviewers who have helped in improving the quality of this paper.

Academic Editor: Miguel A Zamora

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (Grant No. 61571010) and the Fundamental Research Funds for the Central Universities (Grant No. 2015JBM016).

References

Lee

. Cyber physical systems: design challenges. In: Proceedings of the IEEE international symposium on object and component-oriented real-time distributed computing (ISORC), Orlando, FL, 5–7 May 2008.

Shi

Wan

Yan

. A survey of cyber-physical systems. In: Proceedings of the international conference on wireless communications and signal processing (WCSP), Nanjing, China, 9–11 November 2011.

Wan

Zhang

Zhao

. Context-aware vehicular cyber-physical systems with cloud support: architecture, challenges and solutions. IEEE Commun Mag 2014; 52(8): 106–113.

Lin

Sun

. GSIS: a secure and privacy-preserving protocol for vehicular communications. IEEE T Veh Technol 2007; 56(6): 3442–3456.

Xiong

Zhu

Liu

. Cyber-physical-social system in intelligent transportation. IEEE/CAA J Autom Sin 2015; 2(3): 320–333.

Qian

Jing

Huo

. A next-hop selection scheme providing long path lifetime in VANETs. In: Proceedings of the IEEE annual international symposium on personal, indoor, and mobile radio communications (PIMRC), Hong Kong, China, 30 August–2 September 2015.

Liu

Wan

Wang

. A survey on position-based routing for vehicular ad hoc networks, telecommunication systems. Telecommun Syst 2016; 62(1): 15–30.

Malandrino

Casetti

Chiasserini

. Optimal content downloading in vehicular networks. IEEE T Mobile Comput 2013; 12(7): 1377–1391.

Zhioua

GEM

Labiod

Tabbane

. Cellular content download through a vehicular network: I2V link estimation. In: Proceedings of the IEEE vehicular technology conference (VTC), Glasgow, 11–14 May 2015.

10.

Yoon

Ngo

. MoPADS: a mobility profile aided file downloading service in vehicular networks. IEEE T Veh Technol 2009; 58(9): 5235–5246.

11.

Liu

Niu

. Roadside units deployment for content downloading in vehicular networks. In: Proceedings of the IEEE international conference on communications (ICC), Budapest, 9–13 June 2013.

12.

Ott

Kutscher

. Drive-thru Internet: IEEE 802.11b for automobile users. In: Proceedings of the IEEE international conference on computer communications (INFOCOM), Hong Kong, China, 7–11 March 2004.

13.

Chen

Chan

. MobTorrent: a framework for mobile internet access from vehicles. In: Proceedings of the IEEE international conference on computer communications (INFOCOM), Rio de Janeiro, Brazil, 19–25 April 2009.

14.

Trullols-Cruces

Morillo-Pozo

Barcelo

. A cooperative vehicular network framework. In: Proceedings of the IEEE international conference on communications (ICC), Dresden, 14–18 June 2009.

15.

Zhao

Cao

VADD: vehicle-assisted data delivery in vehicular ad hoc networks. IEEE T Veh Technol 2008; 57(3): 1910–1922.

16.

Eriksson

Balakrishnan

Madden

Cabernet: vehicular content delivery using WiFi. In: Proceedings of the ACM annual international conference on mobile computing and networking (MobiCom), San Francisco, CA, 14–19 September 2008.

17.

Zhang

Zhao

Cao

. On scheduling vehicle-roadside data access. In: Proceedings of the ACM international workshop on vehicular ad hoc networks (VANET), Montreal, QC, Canada, 10 September 2007.

18.

Ota

Dong

Chang

. MMCD: cooperative downloading for highway vanets. IEEE T Emerg Top Comput 2015; 3(1): 34–43.

19.

Yang

Yeo

Lee

BS.

MaxCD: efficient multi-flow scheduling and cooperative downloading for improved highway drive-thru internet systems. Comput Netw 2013; 57(8): 1805–1820.

20.

Trullols-Cruces

Fiore

Barcelo-Ordinas

Cooperative download in vehicular environments. IEEE T Mobile Comput 2012; 11(4): 663–678.

21.

Liu

Bian

. DSRelay: a scheme of cooperative downloading based on dynamic slot. In: Proceedings of the IEEE international conference on communications (ICC), Ottawa, ON, Canada, 10–15 June 2012.

22.

Malandrino

Casetti

Chiasserini

. Content downloading in vehicular networks: what really matters. In: Proceedings of the IEEE international conference on computer communications (INFOCOM), Shanghai, China, 10–15 April 2011.

23.

IEEE Standard 802.11p-2010: IEEE standard for information technology–local and metropolitan area networks–specific requirements–part 11: wireless LAN medium access control (MAC) and physical layer (PHY) specifications amendment 6: wireless access in vehicular environments (pp.1–51, July 2010).

24.

Dahshan

Irvine

. An elliptic curve distributed key management for mobile ad hoc networks. In: Proceedings of the IEEE vehicular technology conference (VTC), Ottawa, ON, Canada, 6–9 September 2010.

25.

Zhong

Chen

Yang

. Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks. In: Proceedings of the IEEE international conference on computer communications (INFOCOM), San Francisco, CA, 30 March–3 April 2003.

26.

Qiao

. Joint video delivery with roadside access points for on-road infotainment. In: Proceedings of the IEEE global telecommunications conference (GLOBECOM), Houston, TX, 5–9 December 2011.