Sage Journals: Discover world-class research

Abstract

In vehicular ad hoc networks, maximizing the satisfaction level of multimedia services is a significant issue of concern to users. Relying on the vehicle-to-infrastructure communications, how to schedule the disseminations of multiple vehicles for ensuring high efficiency and guarantee users’ quality of service is difficult and challenging, due to the limited channel resource and vehicle sojourn time. In this article, the scheduling problem of multi-vehicle multimedia dissemination in vehicular ad hoc networks is investigated. A utility model is developed to map the throughput (i.e. the amount of received data) to the user satisfaction level. The scheduling problem is formulated as a utility maximization problem of all the users, which is NP-hard. Then it is transformed into a finite-state decision problem and we obtained an optimal solution by the searching algorithm, which is impractical and can serve as the upper bound. To solve the problem in practice, an online admission control and scheduling algorithm is devised, which guarantees the inflexible data requirements of those admitted vehicles and maximize the total utility. Finally, we implement and conduct extensive simulations on the basis of real video trace to evaluate the performance. Simulation results show that our proposed algorithm has better performance than the state-of-the-art and the conventional algorithms. Thus, it can effectively make scheduling decisions to obtain higher total utility and admission probability.

Keywords

Multi-vehicle multimedia dissemination vehicle-to-infrastructure communication utility maximization vehicular ad hoc networks

Introduction

There is an ever-increasing demand of Internet access service recently, and people even want to be able to enjoy services while traveling in vehicles. However, because of the high mobility characteristics, it still has many challenges to provide high-speed and reliable Internet services. In the study of vehicular ad hoc networks (VANETs),^1,2 vehicle-to-infrastructure (V2I) communication is a potential technique to solve the high mobility problem. Roadside units (RSUs) deployed beside the road can play the part of Internet access points (APs). Vehicles can access the Internet through the connection to an RSU, when they pass through the coverage range of the RSU. The system mentioned above, named as drive-thru Internet, has drawn much attention in both academia and industry.^3–5

Multimedia applications in VANETs have grown recently.^6–9 For example, voice and video are suitable multimedia to carry and deliver news and advertisements which could greatly enhance the user experience. In addition, multimedia dissemination can play an important role in enhancing road safety.¹⁰ For example, real-time video transmission about poor road conditions carried by the vehicles ahead can help the vehicles behind pass through the special section of the road safely.¹¹ However, it is quite challenging to complete the dissemination of videos and other multimedia traffic in VANETs. Due to high mobility, the sojourn time of vehicles in the coverage range of an RSU is limited, which restricts the amount of received data. When multiple vehicles are within the coverage range of a single RSU simultaneously, the competition for limited channel resource will also reduce the amount of received data of each vehicle. Consequently, how to make scheduling decisions for multi-vehicle multimedia dissemination in VANETs is an open issue.

In this article, we developed the scheduling problem of multi-vehicle multimedia dissemination (i.e. multiple vehicles access a single RSU simultaneously), aiming to maximize the users’ total utility while satisfying the inflexible data requirements of those admitted users. Especially, we consider video multimedia traffic in this article. Motivated by previous research, the utility model can be considered as a function to make the total throughput (i.e. the amount of received data) map to user satisfaction level (i.e. quality of video).¹² Transmission time can be divided into time slots, and channel bandwidth can be divided into fixed sub-bands. Each user only occupies at most one sub-band for each time slot. Then the scheduling problem can be formulated as a utility maximization problem (UMP) to obtain the maximum total utility of all users. Because the solution of the optimal problem depends on future arrivals, it is difficult to obtain the optimal solution in practice. In addition, the optimal decision cannot be divided into sequent per-slot optimization problems simply. Therefore, we propose an online heuristic algorithm to solve the challenging issue.

The key contributions of this article are listed as follows:

First, from the users’ perspective, we classify the multimedia data requirements of users into inflexible data requirements which need to guarantee the minimum user satisfaction level and flexible data requirements which have no service guarantee.

Second, with the consideration of both vehicle sojourn time and user data requirement for multimedia traffic, we formulate the multi-vehicle scheduling problem as a UMP to maximize user satisfaction level. Under the assumption of having prior knowledge of future arrival information, we convert the optimization problem into a finite-state decision problem. Therefore, we can obtain the optimal solution by a searching algorithm. Since the searching algorithm has a high computational complexity and the assumption above is impractical, we consider the admission control and scheduling (ACS) algorithm to make real-time scheduling decisions.

Finally, we apply the proposed ACS algorithm and conduct simulations using MATLAB to evaluate its performance. The simulation results demonstrate that our proposed ACS algorithm in this article can achieve better performance than the state-of-the-art solution¹² and the conventional solution regarding total utility and admission probability.

The rest of this article is organized as follows. In section “Related works,” the related research is summarized. Section “System model and problem formulation” describes the proposed system model and the process of problem formulation. Besides the optimal upper bound, we present the online ACS algorithm in section “Algorithm design.” Section “Performance evaluation” shows the performance of the proposed algorithm through simulation results, followed by conclusions and further research issues in section “Conclusion.”

Related works

In recent years, many researchers have paid attention to V2I communications and there have been extensive works on studying the drive-thru scenarios.^3,5,13–17 Zhang et al.¹³ proposed a scheduling system considering both data size and service deadline, and then used a single broadcast to improve it in order to serve multiple requests. Man et al.^14,15 considered two problems of finding the optimal transmission policy. One is the optimal transmission strategy with random vehicle arrivals and a single roadside AP, and the other is the optimal transmission strategy with deterministic vehicle arrivals and multiple APs. The problems are formulated as finite-horizon sequential decision problems and can be tackled with dynamic programming (DP). Using Markov reward model, Tan et al.³ derived analytical models to characterize the distribution and the average of the number of bytes downloaded by each vehicle during the sojourn time. Zhuang et al.⁵ proposed an analytical framework to obtain the upload performance of the last-hop drive-thru communication, taking into account vehicle density, the corresponding traveling speed, and the transmission range of the AP. The results showed that each drive-thru vehicle can achieve the maximum throughput with an optimal admission control strategy by the AP. For non-real-time, non-safety data transmission of V2I systems, Alcaraz et al.¹⁶ proposed a novel contention-free poll-based scheduling mechanism at the link layer, in order to minimize the residual backlog for every user.

Recently, utility-based time division multiple access (TDMA) scheduling method has been used in most of the research.^12,18–22 Bethanabhotla et al.¹⁸ considered the jointly optimal design of admission control and transmission scheduling for adaptive video streaming over small cell networks, which can be formulated as a dynamic network UMP. Zhou et al.¹⁹ investigated a multimedia scheduling issue over heterogeneous wireless networks and designed an original distributed availability-aware adaptive rate allocation scheme to maximize the utility that jointly considers quality of service, reliability, and availability. On the basis of the network utility maximization framework, Chen et al.²⁰ formulated a flow control optimization problem with link interference and lifetime constraint for wireless sensor networks. Hwang and Lee²¹ proposed an effective scheme about video multicast over wireless mesh networks, in which each multicast receiver has its own quality demand. However, these works do not consider the mobility of nodes and we cannot apply the given solutions easily to support multimedia services in VANETs. Xing and Cai²² proposed an adaptive video streaming policy for video services in a highway VANET scenario. A vehicle could download video data via a direct or a multi-hop link to the RSUs, with the help of cooperative relay among vehicles. In addition, Xing et al.¹² investigated the scheduling of multimedia transmissions over drive-thru Internet, aiming to maximize the user satisfaction level. To obtain a desirable solution in real time, an online heuristic algorithm on the basis of the concept of utility potential was proposed. Nevertheless, it is assumed that only one vehicle will be allocated to transmit for each time slot rather than multiple vehicles. Wang et al.²³ proposed two scheduling algorithms for file transmission considering transmission times and due times, respectively. If we consider the two constraints above simultaneously, how to design the scheduling algorithm?

In this article, we consider the multi-vehicle scheduling problem with the consideration of both the sojourn time of vehicles and the requirement of users for multimedia traffic. Then we formulate it as a UMP to maximize user satisfaction level. Under the assumption of having prior knowledge of future arrival information, we can obtain the optimal solution by a searching algorithm. For a more practical situation, we propose the ACS algorithm to make real-time scheduling decisions, which can achieve better performance than the state-of-the-art solution and the conventional solution.

System model and problem formulation

In this article, as shown in Figure 1, we consider the problem of how to schedule multiple vehicles to disseminate multimedia data in a highway VANET scenario. In this scenario, vehicles could download multimedia data from RSUs or upload data to RSUs via V2I communication. The RSUs are all deployed beside the road with certain communication range R. Due to high deployment cost, deploying enough RSUs to cover the whole road without gaps is quite impossible. Therefore, when a vehicle moving on the highway passes an RSU, from which it can receive multimedia data.

Figure 1.

System model.

Vehicle mobility model

On the basis of the traffic flow model and previous research,^5,24 the vehicle arrival process for each lane can be regarded as a Poisson process. The aggregated arrival still follows a Poisson distribution process with multiple lanes in the same directions. To simplify the problem description, we assume that all vehicles are in a single lane with the arrival rate $λ$ .

Considering the speed limit in a highway scenario, we assume that the speed of vehicles follows a uniform distribution between $v_{\min}$ and $v_{\max}$ , which is reasonable.

Data transmission model

Assume that each vehicle is equipped with an on-board unit (OBU), which can communicate with RSU through dedicated short range communications (DSRC) radio. What is more, we assume that each vehicle is equipped with a GPS device. Therefore, each vehicle could upload its own location, speed, and other information to RSU through DSRC radio.

The total data transmission time could be divided into several time slots with the duration of $Δ t$ . With the consideration of limited channel resource, we assume that there are at most M vehicles which can access a single RSU in each time slot. For all vehicles in the coverage of the RSU, they have the same transmission rate w.

Assume the $i th$ vehicle arrives into the coverage of an RSU at time $t_{i}^{a}$ with speed $v_{i}$ . According to equation (1), we can calculate the departure time $t_{i}^{d}$ of the $i th$ vehicle. We assume that all users have the same inflexible data requirements $D_{\min}$ to satisfy the minimum video quality (user satisfaction level) for video decoding. Given the constant transmission rate, each vehicle’s data requirements can be converted into a lot of time slots, which can simplify the analysis. Only the vehicles during their allocated time slots are allowed to transmit data. When the multimedia data are transmitted successfully, they no longer request wireless network access. We also allow the data transmission to be interrupted during the transmission process, and thus a vehicle can receive data in non-consecutive slots.

t_{i}^{d} = t_{i}^{a} + \frac{2 R}{v_{i}}

(1)

Utility model

Peak signal-to-noise ratio (PSNR) is a widely accepted video quality metric to represent the value of utility.^25,26 We use the utility function $F_{u}$ making the amount of accumulated video data D map to the video quality U, which can be expressed as

U = F_{u} (D)

(2)

In this article, we consider the compressed sensing (CS)-based encoding technique. For CS-based codec, the video can always be decoded with different video quality according to different amounts of received video data. Thus, the utility function can be written as a quadratic function^12,26

F_{u} = a D^{b} + c

(3)

where a, b, and c are the parameters determined by the encoder, as shown in Figure 2.

Figure 2.

Utility model.

Problem formulation

Let $N_{t}$ be the total number of vehicles in the coverage of an RSU at the $t th$ time slot. As the channel resource is limited, there will be at most M vehicles which can access the RSU at each time slot. For the $t th$ time slot, the decision for all $N_{t}$ vehicles can be given by

A (t) = {a_{1} (t), a_{2} (t), \dots, a_{N_{t}} (t)}

(4)

where

a_{i} (t) = {\begin{matrix} 1, the i th vehicle is assigned \\ 0, the i th vehicle is not assigned \end{matrix}

(5)

There is a constraint

\sum_{i = 1}^{N_{t}} a_{i} (t) ⩽ M

(6)

for $A (t)$ , which means that at most M vehicles could be assigned to transmit simultaneously for the time slot t.

A vital problem to be considered is how to guarantee video quality for users, that is, the inflexible data requirements must be satisfied before user’s departure deadline, while maximizing the number of users served with the video transmission. Therefore, an admission control algorithm is proposed to deal with this issue. Once a vehicle is assigned to transmit, both its inflexible data requirements and deadline limit must be guaranteed; otherwise, the vehicle must be declined.

For the $i th$ vehicle, once it is admitted, it will be allocated several time slots to transmit data before its departure time. During its total sojourn time in the coverage of RSU, the decision with it can be expressed as

A_{i} (t) = {a_{i} (t_{i}^{a}), \dots, a_{i} (t)}, t_{i}^{a} ⩽ t ⩽ t_{i}^{d}

(7)

Accordingly, the accumulated video data for the $i th$ vehicle at the $t th$ time slot can be represented as

D_{i} (t) = \sum_{k = t_{i}^{a}}^{t} a_{i} (k)

(8)

The aim of this article is to find an optimal allocation of T time slots to schedule the transmission. Thus, we formulate the UMP as follows

\max \sum_{i = 1}^{λ T} F_{u} (D_{i} (t_{i}^{d}))

(9)

s . t . a_{i} (t) \in {0, 1}

(10)

\sum_{i = 1}^{N_{t}} a_{i} (t) ⩽ M

(11)

D_{i} (t_{i}^{d}) ⩾ D_{\min}

(12)

Obviously, the UMP above is an integer programming problem. In addition, the UMP can be a 0–1 programming problem, which is NP-hard, because the variable $a_{i} (t)$ must be chosen between 0 and 1. With the consideration of the deadline constraints, the optimal scheduling decision at each time slot t needs to know fully the future arrival information of vehicles until the $T th$ time slot. For each time slot, we assume that there are on average $N_{v}$ vehicles within the RSU’s transmission range. $N_{v}$ can be obtained by $N_{v} = 2 ρ R$ , $ρ = λ / \bar{v}$ , $\bar{v} = (v_{\min} + v_{\max}) / 2$ , where $ρ$ is the vehicle density and $\bar{v}$ is the expected value of v. Because the variable $a_{i} (t)$ must be determined sequentially, the future decisions can be affected by the decision at the current time slot. As the scheduling process lasts T time slots totally, the computational complexity can be represented as $O ((N_{v})^{T})$ .

However, it is almost impossible to know the future arrival information in practice, which makes achieving the optimal solution quite more difficult. Thus, in the next section, we will first think about how to achieve the optimal solution under the assumption that the future arrivals have already been known, and the results can serve as a benchmark. Then, we will consider how to design an online heuristic algorithm that can be only on the basis of the current vehicles’ arrivals to obtain maximum total utility.

Algorithm design

Optimal solution

Under the assumption that the RSU has known the future arrival information, the UMP above could be transformed into a finite-state sequential problem.

In the formulated problem, our aim is to achieve the maximum total utility for future T time slots. For the $t th$ time slot, we define $S_{t}$ to denote the current states of $N_{t}$ vehicles in the RSU’s transmission range, that is

S_{t} = (V_{1}, V_{2}, \dots, V_{N_{t}})

(13)

where $V_{i}$ is the $i th$ vehicle’s information set in the RSU’s coverage and is defined as

V_{i} = {I_{i}, v_{i}, D_{i}}

(14)

which includes the vehicle ID $I_{i}$ , its traveling speed $v_{i}$ , and the amount of received multimedia data $D_{i}$ in equation (8).

For each time slot, what we should do is only to determine which vehicles are allocated to transmit data. Therefore, the action is given by

A_{t} = (a_{1}, a_{2}, \dots, a_{M}), a_{i} \in [1, 2, \dots, N_{t}]

(15)

For each assigned vehicle, the amount of multimedia data transmitted in each time slot can be expressed as

Δ D = w Δ t

(16)

Given the amount of video data transmitted in the current time slot, we can update the amount of received video data in the next time slot $D_{i}^{+}$ as

D_{i}^{+} = D_{i} + Δ D

(17)

For $(N_{t} - M)$ vehicles that have no opportunity to transmit, their amounts of received video data remain unchanged. As the vehicles can travel with distance $v_{i} Δ t$ in the current time slot according to their own speed $v_{i}$ , each vehicle’s status information in the next time slot $V_{i}^{+}$ should be updated, respectively. As we mentioned above, only M vehicles that are allocated to transmit data in the current time slot need to update the amount of received data. Considering the vehicle status information in the next time slot, $S_{t}^{+}$ can be expressed as

S_{t}^{+} = (V_{1}^{+}, V_{2}^{+}, \dots, V_{N_{t}}^{+})

(18)

To evaluate how much improvement the decision making can achieve, we define $R_{t}$ to represent the reward for each scheduling operation at each time slot t. Because the target of our scheduling algorithm is to obtain the maximum total utility, we can use the reward to represent the utility which can be achieved by the current $N_{t}$ vehicles in the current time slot. Thus, the value of $R_{t}$ is calculated as

R_{t} = \sum_{i = 1}^{N_{t}} [F_{u} (D_{i}^{+}) - F_{u} (D_{i})]

(19)

Accordingly, the total value of reward obtained for the whole time slots is the sum of the reward of each time slot. Hence, the problem could be represented as long-term reward maximization in the total time period T, that is

\max \sum_{t = 1}^{T} R_{t}

(20)

s . t . A_{t} \subseteq [1, N_{t}]

(21)

| A_{t} | ⩽ M

(22)

In this article, |·| means the operation that obtains the length of an array. For each time slot, we notice that when using a greedy approach (i.e. perform the scheduling operation that can achieve the highest reward in the current slot), there is a high possibility that the amount of accumulated data D is less than the inflexible data requirements $D_{\min}$ when the vehicle density is large. It is necessary to satisfy the inflexible data requirements for each vehicle which is admitted.

The optimal solution for the given reward maximization problem can be obtained through the searching approach, that is, searching all the possible states. Obviously, the computational complexity is $O ((N_{v})^{T})$ as mentioned in the last section, which is extremely high. In addition, because prior knowledge of future arrival information is must, the solution cannot be achieved in practical applications. Therefore, we can only regard it as the upper bound of performance and the offline benchmark.

ACS algorithm

With the consideration of the high mobility and the randomness of vehicle arrival, it is quite difficult and impractical to obtain future vehicle arrival information. Therefore, it is required to design an online heuristic algorithm without prior knowledge of future arrival information. Here, on the basis of the current arrival information, we propose a both simple and useful algorithm, named ACS algorithm, to achieve high utility. The ACS algorithm includes two parts: admission control algorithm and transmission scheduling algorithm.

Admission control algorithm

The least laxity first (LLF) scheduling algorithm considered both the unsatisfied requirement and the time urgency.²⁷ Therefore, it can ensure that the most urgent tasks of all can be first processed.

Definition 1 (throughput state)

Let t denote the current time slot as mentioned beore and $D_{i} (t)$ denote the accumulated video data in equation (8). $T h_{i} (t)$ can be defined as the throughput state of the vehicle i at the $t th$ time slot, which can be expressed as

T h_{i} (t) = D_{\min} - D_{i} (t)

(23)

Definition 2 (flexibility)

The difference between the amount of remaining time to complete data transmission and the ratio of vehicle’s throughput state to transmission rate can be defined as flexibility, which can be expressed as

ϕ_{i} (t) = t_{i}^{d} - t - \frac{T h_{i} (t)}{w}

(24)

As we mentioned above, the flexibility takes into account the influence of both unsatisfied data requirements and time urgency. In the LLF algorithm, a vehicle with a smaller value of flexibility will be given a higher priority to schedule.

The admission control process of the LLF algorithm can be considered as follows. We add each new arrival vehicle to the existing urgent set $S_{u}$ . Then all vehicles in $S_{u}$ can be scheduled by the LLF algorithm, and we can obtain each vehicle’s estimated finish time. If any vehicle’s finish time exceeds its departure time, the new arrival vehicle should be declined directly. The decision-making of each time slot can be given by

I^{a} (t) = \underset{i \in 1, \dots, N_{t}}{\arg min} ϕ_{i} (t)

(25)

where $I^{a} (t)$ represents the vehicle index which is assigned to transmit at the $t th$ time slot.

Algorithm 1 shows the detailed admission control algorithm below. Lines 6–20 describe the process of virtually assigning vehicles to transmit on the basis of their flexibilities. And the process of decision is shown in lines 21–25. If the new arrival has no impact on the inflexible data transmission of exiting vehicles, it will be admitted. In the admission control algorithm, the inflexible data requirements of those admitted vehicles must be guaranteed before their departure time. All the admitted vehicles can be added to an urgent set $S_{u}$ to be scheduled for data transmission. We will introduce the detailed transmission scheduling algorithm as follows.

Algorithm 1 Admission control algorithm (ACA)
1: Input: Accumulated video data $D_{i}$ and speed $v_{i}$ of new vehiclei, urgent set $S_{u}$ , current time slot index t.2: Output: Decision (admit or decline the new vehicle).3: procedure ACA ( $D_{i}$ , $v_{i}$ , $S_{u}$ , t)4: Add the new vehicle to the exiting urgent set $S_{u}$ .5: Get the maximum deadline $t_{\max}^{d}$ for all vehicles in $S_{u}$ .6: for $k = t$ to $t_{\max}^{d}$ do7: Compute flexibility $ϕ_{j} (k)$ for each vehicle $j \in S_{u}$ .8: Get the $M th$ minimum flexibility $ϕ_{M}^{\min}$ .9: for Each vehicle $j \in S_{u}$ do10: if $ϕ_{j} (k) ⩽ ϕ_{M}^{\min}$ then11: Update $D_{j} (k + 1) \leftarrow D_{j} (k) + w Δ t$ .12: if $D_{j} (k + 1) = = D_{\min}$ then13: Remove vehicle j from set $S_{u}$ .14: Set finish time $t_{j}^{f} = k$ for vehicle j.15: end if16: else17: $D_{j} (k + 1) \leftarrow D_{j} (k)$ .18: end if19: end for20: end for21: for Each vehicle j in the set $S_{u}$ do22: if $t_{j}^{f} > t_{j}^{d}$ then23: return Decline the new vehicle.24: end if25: end for26: return Accept the new vehicle.27: end procedure

Algorithm 1 Admission control algorithm (ACA)

1: Input: Accumulated video data

D_{i}

and speed

v_{i}

of new vehiclei, urgent set

S_{u}

, current time slot index t.2: Output: Decision (admit or decline the new vehicle).3: procedure ACA (

D_{i}

v_{i}

S_{u}

, t)4: Add the new vehicle to the exiting urgent set

S_{u}

.5: Get the maximum deadline

t_{\max}^{d}

for all vehicles in

S_{u}

.6: for

k = t

t_{\max}^{d}

do7: Compute flexibility

ϕ_{j} (k)

for each vehicle

j \in S_{u}

.8: Get the

M th

minimum flexibility

ϕ_{M}^{\min}

.9: for Each vehicle

j \in S_{u}

do10: if

ϕ_{j} (k) ⩽ ϕ_{M}^{\min}

then11: Update

D_{j} (k + 1) \leftarrow D_{j} (k) + w Δ t

.12: if

D_{j} (k + 1) = = D_{\min}

then13: Remove vehicle j from set

S_{u}

.14: Set finish time

t_{j}^{f} = k

for vehicle j.15: end if16: else17:

D_{j} (k + 1) \leftarrow D_{j} (k)

.18: end if19: end for20: end for21: for Each vehicle j in the set

S_{u}

do22: if

t_{j}^{f} > t_{j}^{d}

then23: return Decline the new vehicle.24: end if25: end for26: return Accept the new vehicle.27: end procedure

Transmission scheduling algorithm

As we mentioned above, after the admission control process, all the vehicles in the urgent set $S_{u}$ will be scheduled for data transmission. First of all, the urgent vehicles, the inflexible data requirements of which have not been satisfied, should be scheduled with a higher priority. If the number of urgent vehicles is less than M, the vehicles with flexible data requirements can be scheduled in the light of their utilities. The decision at each time slot is made as follows

I^{s} (t) = \underset{i \in 1, \dots, N_{t}}{\arg max} Δ U_{i} (t)

(26)

where $I^{s} (t)$ denotes the vehicle index which is assigned to transmit at the time slot t and $Δ U_{i} (t)$ denotes the obtained utility of the user i at the time slot t.

From the utility model, we can know that the speed of utility growth slows down with the increase of the amount of video data. Consequently, if the number of urgent vehicles is less than M, the vehicles in $S_{f}$ with less video data $D_{i}$ could be chosen to transmit data. $S_{f}$ means the flexible set in which all vehicles have satisfied the inflexible data requirements $D_{\min}$ . Therefore, equation (26) can also be expressed as

I^{s} (t) = \underset{i \in 1, \dots, N_{t}}{\arg min} D_{i} (t)

(27)

Algorithm 2 describes the detailed transmission scheduling algorithm below. Lines 5–8 show the process of scheduling the urgent vehicles. And the process of scheduling the urgent and flexible vehicles is shown in lines 9–14. The urgent set $S_{u}$ includes those vehicles admitted, yet the inflexible data requirements of which have not been satisfied. Those vehicles for which inflexible data requirements have been satisfied should be added to the flexible set $S_{f}$ .

Algorithm2 Transmission scheduling algorithm (TSA)
1: Input: Urgent set $S_{u}$ , flexible set $S_{f}$ , number of wirelesschannels M, current time slot index t.2: Output: Allocated urgent transmission set $A_{u}$ andflexible transmission set $A_{f}$ .3: procedure TSA ( $S_{u}$ , $S_{f}$ , M, t)4: Set $N \leftarrow M - \| S_{u} \|$ .5: if $N ⩽ 0$ then6: Compute flexibility $ϕ_{j} (t)$ for each vehicle $j \in S_{u}$ .7: Get the M smallest flexibility vehicles and add to $A_{u}$ .8: UpdateUrgentAllocation(A_u).9: else10: Add all vehicles in $S_{u}$ to $A_{u}$ .11: Get the accumulated amount of data $D_{j} (t)$ for each vehicle $j \in S_{f}$ .12: Add the N vehicles with least video data to $A_{f}$ .13: UpdateUrgentAllocation(A_u).14: UpdateFlexibleAllocation(A_f).15: end if16: end procedure17:18: function UpdateUrgentAllocation(A_u)19: for Each vehicle $j \in A_{u}$ do20: Update $D_{j} (t + 1) \leftarrow D_{j} (t) + w Δ t$ .21: if $D_{j} (t + 1) = = D_{\min}$ then22: Remove vehicle j from $S_{u}$ .23: if $t + 1 < t_{j}^{d}$ then24: Add vehicle j to $S_{f}$ .25: end if26: end if27: end for28: end function29:30: function UpdateFlexibleAllocation(A_f)31: for Each vehicle $j \in A_{f}$ do32: Update $D_{j} (t + 1) \leftarrow D_{j} (t) + w Δ t$ .33: if $t + 1 = = t_{j}^{d}$ then34: Remove vehicle j from $S_{f}$ .35: end if36: end for37: end function

Algorithm2 Transmission scheduling algorithm (TSA)

1: Input: Urgent set

S_{u}

, flexible set

S_{f}

, number of wirelesschannels M, current time slot index t.2: Output: Allocated urgent transmission set

A_{u}

andflexible transmission set

A_{f}

.3: procedure TSA (

S_{u}

S_{f}

, M, t)4: Set

N \leftarrow M - | S_{u} |

.5: if

N ⩽ 0

then6: Compute flexibility

ϕ_{j} (t)

for each vehicle

j \in S_{u}

.7: Get the M smallest flexibility vehicles and add to

A_{u}

.8: UpdateUrgentAllocation(A_u).9: else10: Add all vehicles in

S_{u}

A_{u}

.11: Get the accumulated amount of data

D_{j} (t)

for each vehicle

j \in S_{f}

.12: Add the N vehicles with least video data to

A_{f}

.13: UpdateUrgentAllocation(A_u).14: UpdateFlexibleAllocation(A_f).15: end if16: end procedure17:18: function UpdateUrgentAllocation(A_u)19: for Each vehicle

j \in A_{u}

do20: Update

D_{j} (t + 1) \leftarrow D_{j} (t) + w Δ t

.21: if

D_{j} (t + 1) = = D_{\min}

then22: Remove vehicle j from

S_{u}

.23: if

t + 1 < t_{j}^{d}

then24: Add vehicle j to

S_{f}

.25: end if26: end if27: end for28: end function29:30: function UpdateFlexibleAllocation(A_f)31: for Each vehicle

j \in A_{f}

do32: Update

D_{j} (t + 1) \leftarrow D_{j} (t) + w Δ t

.33: if

t + 1 = = t_{j}^{d}

then34: Remove vehicle j from

S_{f}

.35: end if36: end for37: end function

From the ACS algorithm above, it can be noticed that we consider the average $2 R / \bar{v}$ time slots for the utility calculation of each vehicle. For each time slot, there will be on average $N_{v}$ vehicles to be considered for the utility calculation. Therefore, the computational complexity is given by $O (2 R N_{v} / \bar{v})$ , which is quite simple for real-time processing and achieved in practice.

Performance evaluation

In this section, we conducted extensive simulations to evaluate the performance of the proposed ACS algorithm. To better understand the performance superiority, we compare the results with the utility potential algorithm¹² and a conventional scheduling algorithm. The utility potential algorithm can be regarded as selecting the vehicle that could obtain the highest ratio of utility to throughput in the following several time slots until it runs out of the RSU’s coverage. In the conventional algorithm, the video data are continuously transmitted. When it satisfies $| A_{u} | < M$ and $t_{i}^{d} - t_{i}^{a} ⩾ D_{\min}$ , the vehicle i could be admitted and one vehicle in $A_{f}$ could be declined. All the reported results are simulated and averaged 500 rounds using Monte-Carlo method in MATLAB.

Simulation setting

The simulation parameters in this article are listed in Table 1. In our simulation, the transmission time is divided into time slots with the duration of $Δ t = 1 s$ , and each simulation will last 500 time slots. The arrival rate of vehicles $λ$ (vehicles per time slot) ranges from 0.1 to 1.5. The transmission range of an RSU is 200 m, and the speed of vehicles in the highway scenario ranges from 20 to 35 m/s. It is assumed that there are $M = 5$ sub-bands, considering the coverage range of the RSU and the density of vehicles in the highway. The data transmission rate is set to 1 MB/s in each sub-band.

Table 1.

Simulation parameters.

Parameters	Values
Each time slot (s)	1
Simulation times (s)	500
Vehicle arrival rate (vehicles/s)	[0.1, 1.5]
RSU transmission radius (m)	200
Vehicle speed (m/s)	[20, 35]
Number of sub-bands	5
Data rate in each sub-band (MB/s)	1

RSU: roadside unit.

We use a real video trace Foreman¹² encoded with CS-based technique as a multimedia example in our simulation. The utility function for the video trace Foreman is given by

F_{u} = 2 D^{0.38} + 8.51

(28)

Evaluation metrics

In this article, we use the following metrics to evaluate the performance:

Total utility is defined as the total utility achieved by all vehicles during the total time slots;

Admission probability is defined as the number of vehicles admitted to transmit data over the number of all vehicles during the total time slots;

Flexible utility is defined as the total utility achieved by all vehicles’ flexible multimedia data.

Simulation results

First of all, we perform the evaluation to the performance gap between the solution of the proposed ACS algorithm and the optimal solution. As mentioned earlier, the optimal solution has a very high computational complexity. To reduce the computational cost, we set the total time slots to be $T = 12 s$ . The values of other parameters are correspondingly reduced (the transmission radius of RSU $R = 50 m$ , the number of sub-bands $M = 3$ , and the inflexible data requirements $D_{\min} = 4$ ).

The results are shown in Figure 3. Obviously, the optimal solution can always achieve the best performance, which searches all the possible scheduling operations to find the best solution. Although the ACS algorithm obtains less total utility than the optimal solution, it can achieve more total utility than the other algorithms. Note that, from all the algorithms, the total utility increases with the increment of the arrival rate, the reason of which is that there are more opportunities to select ideal vehicles to transmit data with the increase of arrival rate. When the arrival rate is small, all algorithms almost have the same total utility. It is because the small arrival rate leads to low vehicle density and then there is no competition for channel resource between vehicles.

Figure 3.

The total utility gap between the ACS solution and the optimal solution, with $T = 12 s$ , $R = 50 m$ , $M = 3$ , and $D_{\min} = 4$ .

We then conduct simulations with more time slots. In the rest of the simulations, we adopt the simulation settings in Table 1. The optimal solution cannot be compared with, because when the amount of total time slots is large enough, the computational load could exceed our computational capacity.

Figure 4 shows the influence of arrival rate on the total utility. We can see that the total utility increases gradually with the increase of arrival rate. The ACS algorithm can obtain more total utility with a large arrival rate, and the total utility converges gradually as the arrival rate reaches a certain value. The reason is that the sub-bands could be fully occupied with the high arrival rate. Therefore, it cannot serve more vehicles and increase the total utility.

Figure 4.

The influence of arrival rate on the total utility, with $T = 500 s$ , $R = 250 m$ , $M = 5$ , and $D_{\min} = 15$ .

Figure 5 shows the influence of arrival rate on the admission probability. It can be seen that with the increase of arrival rate, the admission probability of vehicles decreases gradually. It is because the number of sub-bands M constrains the number of admitted vehicles. In addition, Figure 5 shows the performance of our admission control algorithm. Compared with the utility potential and conventional algorithm, our proposed algorithm has a higher admission probability for vehicles.

Figure 5.

The influence of arrival rate on the admission probability, with $T = 500 s$ , $R = 250 m$ , $M = 5$ , and $D_{\min} = 15$ .

Figure 6 shows the influence of arrival rate on the flexible utility. Different from total utility, the curve of flexible utility first increases and then decreases. With a low arrival rate, while the arrival rate is increasing, the value of flexible utility increases, because it can serve more number of vehicles for their flexible requirements. However, when the arrival rate exceeds a certain value, the sub-bands can be almost fully occupied by the vehicles in the urgent set $S_{u}$ , and fewer vehicles in the flexible set $S_{f}$ with flexible data requirements will obtain the opportunities to be served. Therefore, the flexible utility decreases gradually. Note that the flexible utility of the ACS algorithm is less than that of the other two algorithms, because more throughput is to serve inflexible requirements for the ACS algorithm. For the same amount of throughput, serving inflexible requirements can provide more utility than flexible requirements. In addition, since the amount of flexible utility is small, the inflexible utility has the main contribution to the total utility. And there is no direct relationship between the values of total utility and flexible utility.

Figure 6.

The influence of arrival rate on the flexible utility, with $T = 500 s$ , $R = 250 m$ , $M = 5$ , and $D_{\min} = 15$ .

In Figures 7 –9, we consider the influence of inflexible data requirements $D_{\min}$ on the total utility, admission probability, and flexible utility with the ACS algorithm, respectively. It can be seen from Figure 7 that the total utility decreases with the increase of $D_{\min}$ . It is because that the larger the value of $D_{\min}$ is, the more the data needed to transmit to satisfy the inflexible requirements. However, for each vehicle, the conversion ratio of unit throughput to utility decreases gradually with the increment of total throughput. Therefore, under the premise of satisfying the inflexible requirements, the total throughput for each vehicle is as small as possible. It can be seen from Figure 8 that the admission probability also decreases with the increase of $D_{\min}$ . The reason is that the admitted vehicles will occupy more time slots to transmit data with the increase of $D_{\min}$ , leaving less opportunities to other vehicles for accessing the RSU. When the arrival rate is 0.1, the total utility and admission probability with $D_{\min} = 15$ are less than those with the other two values of $D_{\min}$ , which is because the sojourn time of the vehicles with a large speed cannot satisfy the large inflexible requirements $(D_{\min} = 15)$ . Thus, the vehicles with a large speed can be declined directly, which has an influence on the total utility and admission probability. Figure 9 shows the influence of $D_{\min}$ on the flexible utility with the ACS algorithm. Due to the same reasons as above, the admitted vehicles with the smaller $D_{\min}$ can occupy less time slots to satisfy the inflexible requirements and have more opportunities to transmit flexible data.

Figure 7.

The influence of $D_{\min}$ on the total utility with the ACS algorithm, with $T = 500 s$ , $R = 250 m$ , and $M = 5$ .

Figure 8.

The influence of $D_{\min}$ on the admission probability with the ACS algorithm, with $T = 500 s$ , $R = 250 m$ , and $M = 5$ .

Figure 9.

The influence of $D_{\min}$ on the flexible utility with the ACS algorithm, with $T = 500 s$ , $R = 250 m$ , and $M = 5$ .

In Figures 10 –12, we consider the influence of vehicle speed v on the total utility, admission probability, and flexible utility with the ACS algorithm. We divide the speed (m/s) into three intervals, that is, [16, 20], [21, 25], and [26, 30]. The smaller the speed is, the longer the sojourn time is. Thus, we can see that the small speed has better performance of total utility and admission probability from Figure 10 and Figure 11. Note that the speed intervals [16, 20] and [21, 25] have the similar performance influence on the total utility and admission probability, which are highly different from the speed interval [26, 30]. It is because the speed in the interval [26, 30] is large enough, so that the sojourn time of many vehicles cannot satisfy the inflexible requirements. The influence of small speed (i.e. [16, 20] and [21, 25]) on the total utility and admission probability can be adjusted through the ACS algorithm. It can be seen from Figure 12 that the flexible utility decreases with the increase of vehicle speed. The reason is that with the increase of speed the sojourn time decreases gradually, which leads to less opportunities to transmit flexible data.

Figure 10.

The influence of speed on the total utility with the ACS algorithm, with $T = 500 s$ , $R = 250 m$ , $M = 5$ , and $D_{\min} = 15$ .

Figure 11.

The influence of speed on the admission probability with the ACS algorithm, with $T = 500 s$ , $R = 250 m$ , $M = 5$ , and $D_{\min} = 15$ .

Figure 12.

The influence of speed on the flexible utilitywith the ACS algorithm, with $T = 500 s$ , $R = 250 m$ , $M = 5$ , and $D_{\min} = 15$ .

Conclusion

In this article, the scheduling problem of multi-vehicle multimedia dissemination in VANETs has been studied. We adopt a utility model to map the amount of video data to user satisfaction level. At first, the scheduling problem was modeled as a UMP of all the users, which is NP-hard. Then it is transformed into a finite-state decision problem and we obtained an optimal solution by the searching algorithm, which is impractical and can only be regarded as the upper bound. To solve the problem in practice, we proposed an online ACS algorithm taking into account both vehicle sojourn time and data requirement of users. Finally, we conducted extensive simulations on the basis of real video trace to evaluate the performance of our proposed algorithm and the metrics we used were the total utility, admission probability, and flexible utility. Although the ACS algorithm obtains less total utility than the optimal solution, it can achieve more total utility than the other algorithms. In addition, the ACS algorithm can achieve a larger admission probability, which guarantees more users to obtain the multimedia service. Note that, different from the other two metrics which are monotonic functions of the arrival rate, the curve of flexible utility first increases and then decreases. Therefore, there is no direct relationship between the values of total utility and flexible utility. We also investigated the impact of other parameters (i.e. inflexible data requirements and vehicle speed) on the three metrics.

In the future, there are still many research issues to be investigated. First of all, the data transmission model can consider the wireless channel conditions to obtain a more practical solution, for example, channel fading and channel shadowing. Second, the video may have different utility functions for different video encoding techniques, for example, H.264 and scalable video coding (SVC) technique. Last but not least, in this article, we only consider the V2I communication, and therefore how to combine V2I with V2V communication to schedule the transmission needs to be investigated.

Footnotes

Handling Editor: Razi Iqbal

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 State Key Laboratory of Rail Traffic Control and Safety under Grant No. RCS2016ZT015, the National High Technology Research and Development Program of China (863 Program) under Grant No. 2015AA016005, the Fundamental Research Funds for the Central Universities under Grant No. 2017JBM312, and the National Natural Science Foundation of China—Outstanding Youth Foundation under Grant No. 61725101.

References

Liang

Zhang

et al . Vehicular ad hoc networks: architectures, research issues, methodologies, challenges and trends. Int J Distrib Sens N. Epub ahead of print 31 August 2015. DOI: 10.1155/2015/745303.

Jeong

Survey on protocols and applications for vehicular sensor networks. Int J Distrib Sens N. Epub ahead of print 22 August 2016. DOI: 10.1177/1550147716662948.

Tan

Lau

Yue

et al . Analytical models and performance evaluation of drive-thru internet systems. IEEE J Sel Area Commun 2011; 29(1): 207–222.

Luan

Ling

Shen

MAC in motion: impact of mobility on the MAC of drive-thru internet. IEEE T Mobile Comput 2011; 11(2): 305–319.

Zhuang

Pan

Viswanathan

et al . On the uplink MAC performance of a drive-thru internet. IEEE T Veh Technol 2012; 61(4): 1925–1935.

Soldo

Casetti

Chiasserini

et al . Video streaming distribution in VANETs. IEEE T Parall Distr 2011; 22(7): 1085–1091.

Asefi

Mark

Shen

XS.

A mobility-aware and quality-driven retransmission limit adaptation scheme for video streaming over VANETs. IEEE T Wirel Commun 2012; 11(5): 1817–1827.

Torres

Calafate

Cano

et al . Evaluation of flooding schemes for real-time video transmission in VANETs. Ad hoc Netw 2015; 24(Part B): 3–20.

Naeimipoor

Boukerche

. A hybrid video dissemination protocol for VANETs. In: Proceedings of the IEEE international conference on communications, Sydney, NSW, Australia, 10–14 June 2014, pp.112–117. New York: IEEE.

10.

Park

Lee

et al . Emergency related video streaming in VANET using network coding. In: Proceedings of the 3rd international workshop on vehicular ad hoc networks, Los Angeles, CA, 29 September 2006, pp.102–103. New York: ACM.

11.

Vinel

Belyaev

Egiazarian

et al . An overtaking assistance system based on joint beaconing and real-time video transmission. IEEE T Veh Technol 2012; 61(5): 2319–2329.

12.

Xing

Cai

Maximum-utility scheduling for multimedia transmission in drive-thru internet. IEEE T Veh Technol 2016; 65(4): 2649–2658.

13.

Zhang

Zhao

Cao

Service scheduling of vehicle-roadside data access. Mobile Netw Appli 2010; 15(1): 83–96.

14.

Man

Hou

Wong

VWS

et al . Dora: dynamic optimal random access for vehicle-to-roadside communications. IEEE J Sel Area Commun 2012; 30(4): 792–803.

15.

Man

Hou

Wong

VWS

et al . Dynamic optimal random access for vehicle-to-roadside communications. In: Proceedings of the IEEE international conference on communications, Kyoto, Japan, 5–9 June 2011, pp.1–6. New York: IEEE.

16.

Alcaraz

Vales-Alonso

Garcia-Haro

Link-layer scheduling in vehicle to infrastructure networks: an optimal control approach. IEEE J Sel Area Commun 2011; 29(1): 103–112.

17.

Cheng

Zhang

et al . Vehicular WiFi offloading: challenges and solutions. Veh Commun 2014; 1(1): 13–21.

18.

Bethanabhotla

Caire

Neely

. Utility optimal scheduling and admission control for adaptive video streaming in small cell networks. In: Proceedings of the IEEE international symposium on information theory proceedings, Istanbul, Turkey, 7–12 July 2013, pp.1944–1948. New York: IEEE.

19.

Zhou

Wang

Lian

et al . Availability-aware multimedia scheduling in heterogeneous wireless networks. IEEE T Veh Technol 2011; 60(3): 1161–1170.

20.

Chen

et al . Utility-based asynchronous flow control algorithm for wireless sensor networks. IEEE J Sel Area Commun 2010; 28(7): 1116–1126.

21.

Hwang

Lee

CY.

Effective video multicast using SVC with heterogeneous user demands over TDMA-based wireless mesh networks. IEEE T Mobile Comput 2013; 12(5): 984–994.

22.

Xing

Cai

. Adaptive video streaming with inter-vehicle relay for highway VANET scenario. In: Proceedings of the IEEE international conference on communications, Ottawa, ON, Canada, 10–15 June 2012, pp.5168–5172. New York: IEEE.

23.

Wang

Larson

Chen

et al . Schedule algorithms for file transmission in vehicular ad hoc networks. In: Proceedings of the international conference on wireless algorithms, systems, and applications, Harbin, China, 23–25 June 2014, pp.126–137. Cham: Springer International Publishing.

24.

Wisitpongphan

Bai

Mudalige

et al . Routing in sparse vehicular ad hoc wireless networks. IEEE J Sel Area Commun 2007; 25(8): 1538–1556.

25.

Lin

Shen

Hsu

et al . Quality-differentiated video multicast in multirate wireless networks. IEEE T Mobile Comput 2013; 12(1): 21–34.

26.

Xiang

Cai

Transmission control for compressive sensing video over wireless channel. IEEE T Wirel Commun 2013; 12(3): 1429–1437.

27.

Chen

Tong

Optimal deadline scheduling with commitment. In: Proceedings of the 49th annual Allerton conference on communication, control, and computing, Monticello, IL, 28–30 September 2011, pp.111–118. New York: IEEE.

Utility maximization for multi-vehicle multimedia dissemination in vehicular ad hoc networks

Abstract

Keywords

Introduction

Related works

System model and problem formulation

Vehicle mobility model

Data transmission model

Utility model

Problem formulation

Algorithm design

Optimal solution

ACS algorithm

Admission control algorithm

Definition 1 (throughput state)

Definition 2 (flexibility)

Transmission scheduling algorithm

Performance evaluation

Simulation setting

Evaluation metrics

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References