Yuanzhi Ni, Lin Cai＊, Yuming Bo

1 School of Automation, Nanjing University of Science and Technology, Nanjing, 210094, China

2 Department of Electrical & Computer Engineering, University of Victoria, Victoria, BC, V8W 3P6, Canada

Abstract: Vehicular beaconing plays an important role to facilitate various applications in the paradigm of Internet of Vehicles (IoV).Due to high dynamic and resource limitation in IoV, how to schedule the vehicular beacon broadcast is challenging, especially in dense scenarios. In this paper, we investigate the beacon broadcast scheduling problem considering the Age of Information (AoI). We first propose an algorithm minimizing the expected sum of AoI considering the limited communication resource and vehicle mobility. Then the performance of the proposed algorithm is analyzed. With the proposed algorithm, the optimal solution can be obtained under certain conditions. Extensive simulations are conducted to verify the efficiency, effectiveness and fairness of the proposed solution.

Keywords: internet of vehicles; beacon broadcast; age of information

I. INTRODUCTION

The emerging connected-vehicle paradigm is expected to provide both safety-related and infotainment services and facilitate the Intelligent Transportation System (ITS) [1] [2]. A vehicular beacon typically includes the driving status, communication condition, connectivity,etc [3][4]. They are critical to fully realize the benefits of ITS. As a time-sensitive application, the beacon broadcasting requires low latency and high reliability, which is usually challenging for highly mobile vehicular communication networks, especially in high-density scenarios.

How to properly allocate communication resources according to the trafficc and communication status is a critical problem. With the development of the Cellular-Vehicle-to-Everything (C-V2X) technology, the vehicles can use the forthcoming 5G systems to connect to the base station and neighboring vehicles to support their beacon message broadcast.In the latest 3GPP specification [6], the eNB scheduling for resource allocation and interference management for V2V services have been included. However, the scheduling of multiple-vehicle broadcasting has not been speci fied in the existing standards. The broadcasting without proper management may lead to severe resource waste and unreliable transmission, which is undesirable for ITS services.

The various applications supported by beacons such as trafficc control, collision warning,and driving platoon, are sensitive to the timeliness of the information. Improper scheduling of the beacons will in fluence the value of the information, and therefore lead to the degradation of the network performance in various aspects. The Age of Information (AoI), a newly proposed metric indicating the freshness of the information, is believed to be an effective performance metric for the beacon broadcasting of vehicular networks [7][8][9]. Keeping the AoI low is important because the network performance is highly dependent on the timely update of neighborhood information. Different from the traditional metrics, the AoI-based scheduling neither aims to maximize the utilization of the communication resource nor ensure the minimum delay. Instead, it aims to maintain the freshness of the information to better facilitate the relevant applications.There are great efforts devoted to investigating the message dissemination taking AoI into account [5] [10] [11]. However, most of the existing work only focused on the static network or the unicast case.

The challenges of the vehicular beacon broadcast scheduling problem are threefold.First, vehicular beacon broadcast suffers from the shortage of the communication resource,especially in the dense scenario. It is impossible to ensure that all beacons can be broadcast reliably. How to schedule the beacon transmissions is challenging. Second, how to select the most suitable vehicles to transmit the beacons and facilitate the related applications is an open issue. The time-varying topology and dynamic states of information make it even more difficult to evaluate the importance of each vehicle, which requires a comprehensive model. Finally, the performance of the scheduling algorithm is important while hard to analyze.How to design an efficcient and effective algorithm and provide the theoretical performance guarantee is of great interests.

As motivated, in this work, we investigate the beacon broadcasting problem from the transmitter’s perspective and focus on minimizing the AoI of the vehicle in the vehicular networks. The main contributions of this paper are three-fold. First, we propose an AoI-based evaluation framework. Second, based on the formulated the problem, a greedy online scheduling algorithm is proposed to minimize the expected sum AoI. Finally, the performance of the proposed algorithm is analyzed and evaluated by the simulation in comparison with the benchmark method.

The remainder of this paper is organized as follows. The related work is presented in Section II. Section III introduces the system model followed by the algorithm design and analysis in Section IV. Performance evaluation is provided in Section V. Section VI concludes this paper and discusses the future issues.

II. RELATED WORK

The vehicular beacon broadcast problem has been studied in the literature from different perspectives such as theoretical modeling and analysis, strategy and algorithm design, aiming at optimizing the resource allocation and improving the performance metrics.

A number of efforts are devoted to the theoretical modeling and analysis [12] [13] [14].For the broadcasting of safety message in vehicular networks, [12] investigated the reception ratio and the packet delivery delay under the Dedicated Short Range Communication(DSRC) environment considering the impact of medium access, the channel characteristics and the vehicle mobility. Several suggestions are provided to enhance the broadcast performance. [13] investigated the optimal beacon rate maximizing the utility considering the reliability of the safety message and the accuracy of information. It is presented that both the vehicle density and the requirements of the packet delivery ratio and the information accuracy affect the optimal beacon rate. In [14], the adaption of the transmission probabilities was applied to maximize the utility of transmitting safety-related packets over wireless channels.A decomposed distributed algorithm requiring a limited amount of message was proposed and analyzed.

Many strategies and algorithms are proposed to achieve the trade-off between improving the performance and utilizing the limited resource [15][16][17][18][19][20][21]. Based on the time slot occupancy status,[15] proposed a distributed time slot sharing MAC protocol to avoid the safety information broadcast collision and maximize the channel utility simultaneously. The performance of the solution is analyzed and verified by simulation. [16] proposed ADHOC-MAC, a distributed MAC protocol based on a slotted channel structure. The dynamic TDMA mechanism is implemented on the top of Reliable R-ALOHA protocol considering the hidden and exposed terminal problems. Based on the network and trafficc conditions and the relationship between the channel occupancy and controllable parameter of the cooperative vehicle safety system, [17] proposed a closed-loop congestion control strategy relying on the feedback from the channel occupancy. [18] proposed a low-complexity centralized scheduling strategy based on the channel prediction built upon the recursive least squares algorithm. The trade-off between the communication overhead and data dissemination performance are found favorable based on the simulation results. In [19], both the device-to-device (D2D)and IEEE 802.11p-based communications are applied in the hybrid vehicular communication system, where the network delay performance is optimized by selecting the proper receiver vehicles. To facilitate the inter-vehicle communications in platooning, a subchannel allocation and power control mechanism was proposed over the cellular based technology[20].The evolved multimedia broadcast multicast services (eMBMS) and D2D multicast communications were combined to achieve the trade-off between the required cellular resources and the imposed delay. [21] considered a joint scheduling and power allocation problem in the downlink cellular system where both real-time (RT) and non-real-time (NRT)users coexist. To maximize the sum-rate while satisfying the constraints, the Lambert-power policy and the water-filling policy were proposed for the RT and NRT users, respectively.

III. SYSTEM MODEL

We consider the beacon broadcasting scenario where the network is consisting ofMvehicles and a cellular base station as illustrated in figure 1. All vehicles are equipped with the Global Positioning System (GPS) to obtain the real-time position and velocity. The cellular base station exchanges the signaling with the vehicles in its coverage periodically. The communication between the base station and the vehicles are assumed to be reliable.

Fig. 1. The beacon broadcasting scenario.

Fig. 2. The slotted time structure and evolution of AoI.

The time of a dedicated channel for beacon broadcast is slotted and labeled as shown in figure 2. The frame duration is the period of the beacon information generation, which typically lasts several hundred milliseconds and does not depend on the number of vehicles nearby. The slot duration is the time needed for each beacon transmission, which depends on the packet size, transmission rate, etc. A frame includes a number of slots, so a num-ber of vehicles can broadcast their beacons without collision using the scheduled channel resource. At the beginning of each frame, a short time period will be used for the vehicles within the coverage of the base station to update the basic information including their positions and AoIs as shown in figure 2. These information updates can be included in the cellular signaling exchanges between the base stations and the vehicles. Multiple orthogonal channels in addition to the one dedicated to beacon broadcasting are used and coordinated by the base station. Thus, the information update duration in each frame does not increase with the number of vehicles and the efficciency of the beacon broadcast scheduling is guaranteed. At the beginning of each frame, each vehicle generates a beacon to be broadcasted to the neighbors to assist the various applications in IoV. A vehicle can finish the beacon broadcasting to the neighboring vehicles over a lossy channel within a slot. At the beginning of each frame, the base station transmits the decision of which vehicles will be authorized with communication resource to broadcast their beacon information in the following time slots of this frame. Denoteas the neighbor set of vehicleiwithin framek. The distance between vehicleiandis less than a given thresholdR, i.e., the beacon broadcast range.is assumed stable during frameksince the relative movement is almost unnoticeable within a short period of time.

To evaluate the broadcasting performance from the network perspective, the expected sum AoI (ESAoI) is de fined as follows.

whereTis the total number of frames. To achieve efficcient data dissemination and avoid collisions, the following basic steps are taken through the beacon broadcasting period.

1) Vehicles update the position and AoI to the base station at the beginning of each frame.

2) Based on the collected information, the base station makes the scheduling decision for the time slots of the following frame.

3) The scheduled vehicles broadcast their latest beacons during the assigned time slots of the frame. The vehicles who receives the beacons will update the AoI at the beginning of the next frame.

In the next section, we will introduce a greedy algorithm that minimizes the ESAoI in details.

IV. ALGORITHM DESIGN

In this section, we first introduce the proposed algorithm minimizing the ESAoI in details.Then, the performance of the proposed scheduling algorithm is analyzed under certain conditions. In the existing work about AoI, the network topology is fixed. However, in the vehicular network, the topology is time-varying considering the vehicle movement. The differences in scheduling in each frame and scheduling of static network lie in the following two aspects. First, the scheduling of static network does not consider the position changes between different periods, while in vehicular networks, the topology in each frame is assumed static, so the scheduling still needs to consider the impacts of vehicle movement to the delivery success ratio. Second, since the neighbor set changes between frames, the AoIs of vehicles should also be processed in each frame to adapt to the leaving and entering of neighbors,which is a necessary operation not required in the static network scheduling.

4.1 Scheduling algorithm

To minimize the objective presented in (2),we need to comprehensively consider the impact of both the AoI status of each vehicle and the relationship between the transmitters and their neighbors. The following scheduling algorithm is adopted based on the information collected at the beginning of each frame.

1) At the beginning of framek, the vehicles within the coverage of the base station update the basic information including the position and AoI to the base station. Then the base station generates the neighbor setcompares withandand

2) Based on the location relationship,is estimated using the similar method in [18].

3) The base station sends the updated neighbor sets and the scheduling decision assigning the slots in the following frame to the vehicles with the highestfollowing the descending order.

4) The scheduled vehicles broadcast beacons at the assigned slots.

5) The neighbors who successfully receive the beacons update the AoI at the beginning of the next frame.

The novelty of the proposed algorithm mainly lies in the following aspects. First, it focuses on optimizing the freshness of the information in the network which is directly related to the quality of the service. Second,the algorithm takes the dynamics of the vehicular network into account and schedules the broadcasting coherently based on the real-time information and geographical relationship.

4.2 Algorithm analysis

Here, we analyze the performance of the proposed algorithm with a similar approach to that in [5]. Theorem 1 shows that the proposed algorithm minimizes ESAoI under the condition that the vehicles have the same number of neighbors and the identical channel reliability. Although the conditions may not be strictly satis fied in actual circumstances, it is still worthwhile to investigate such case which basically reflects the characteristics of the practical situation. This is because the scenario where the proposed scheduling algorithm is applied is usually dense, and the difference of channel reliability and the neighbor size between vehicles are therefore less noticeable.

Theorem 1.Consider a network with all vehicles having the same number of neighbors and the identical channel reliabilityThe proposed algorithm achieves the minimum ESAoI.

Proof:To examine the performance of the proposed algorithm, we need to compare the dynamic of the objective function (2) under the proposed algorithm G and an arbitrary strategyπ. Letthe random variable indicating the value ofunderπand G,respectively. We further de fine the random variableindicating the sum ofat framekin (3) and (4), respectively, as follows.

Here we apply a stochastic dominance argument [22] for the comparison. Letbe the stochastic process and its sample path, respectively.SGandsπare defined in a similar way. Denote the space of allsπas D and the set of measurable functionsf:D→?+, as F, wherewhich satisfy

Sincef(Sπ) is positive, ifSG≤Sπ, thenIt is natural to find thatis a function satisfies the conditions in F. Thus, it is sufficcient to confirm thatSGis stochastically smaller thanSπ, ?π∈Π. According to the results from [22], to verifySG≤Sπ, the sufficient condition is that there exist two stochastic processesandsuch that

(i)andhave the same probability distribution;

(ii)andare on a common probability distribution;

(iii)SGandhave the same probability distribution;(iv), with probability 1, ?k.

Then, we take the following steps to selectfor the establishment of stochastic dominance with stochastic coupling.

Stochastic couplingis a method utilized for the comparison between stochastic processes by imposing a common underlying probability space. Here, it is used to constructbased onSGandSπ, respectively.

First,is identical toSπ. Second,is constructed with the same probability space asSG. Thus,are coupled by dynamically connecting the channel state of G to that ofπas follows. Suppose in frame k, strategy G schedules clientiwhile strategyπschedules clientl,then for the duration of that slot, we assign

It is noted that such assignment is possible because the channel states of all vehicles are i.i.d.

With the above operations, the conditions(i), (ii), and (iii) are satis fied. For the last condition, during any slot with the channel stateis updated to befor all vehicles. However, for the channel state 1, strategy G leads to the smallest sumby scheduling the vehicles with the highest sum AoI while other strategyπcannot achieve better results obviously. Thus,condition (iv) is also con firmed and the proof is completed as it is.

It is shown in Theorem 1 that the proposed algorithm achieves the optimality for the network with the same size of the neighbor set and the equal channel reliability. For a general network where vehicles may have various parameters, the proposed algorithm may not be optimal. To investigate the neighbor set sizes and their difference, some simulations were conducted. The mean and standard deviation of the size of the neighbor sets under different vehicle densities are presented in figure 3. It is illustrated that with the increase of vehicle density, the average size of the neighbor set increases. The standard deviation increases when the vehicle density increases from 10 vehicles per kilometer to 250 vehicles per kilometer.However, when the density keeps increasing,the standard deviation decreases signi ficantly.Thus, in the dense scenario, the difference between the neighbor size is less noticeable.Considering the proposed algorithm mainly focuses on the dense scenario scheduling, the assumption is still reasonable. The simulation results in Sections V verifies that even when the condition of Theorem 1 is not satis fied, the proposed algorithm still achieved a better performance than the benchmark methods.

V. PERFORMANCE EVALUATION

To comprehensively evaluate the performance of the proposed algorithm, NS-3 simulations are conducted under various conditions including different vehicle densities, different numbers of neighbors, and unidentical channel reliability. The proposed algorithm is compared with the round-robin scheduling method and IEEE 802.11p based broadcasting method.In each simulation, the vehicle inter-distance is a random variable following the exponential distribution according to the vehicle densities.The vehicle movement speed changes over time within the given range. The Friis propagation loss model is applied in the simulation.The simulations of each group are repeated 100 times to calculate the average value. The simulation parameter setting is given in table 1.

We first examine the average AoI of the neighbors of all vehicles over the entire simulation period. The relationship between the average AoI and vehicle density is presented in figure 4. The average AoI increases with the vehicle density under the proposed algorithm and the benchmark methods. This is because the vehicles must share the communication resource with more vehicles in the high-density scenario. The average AoI under the proposed algorithm is always lower than that under the benchmark solution since we render the broadcasting priority to the vehicle with the highest sum AoI. The IEEE 802.11p based broadcasting method achieves lower average AoI than round-robin method in the sparse scenario.Figure 5 depicts the peak AoI which is de fined as the maximum AoI of all vehicles during the simulation. The proposed algorithm also maintains a lower value of the peak AoI and achieves only half of it in comparison with the benchmark methods.

Fig. 3. The mean and standard deviation of the size of neighbor sets.

Table I. Simulation setting.

Fig. 4. The average AoI vs vehicle density.

Fig. 5. The peak AoI vs vehicle density.

Fig. 6. The average number of effective neighbors vs vehicle density.

Fig. 7. The fairness vs vehicle density.

To compare the dissemination efficiency,we investigate the number of effective neighbors of each vehicle, which is defined as the number of the neighboring vehicles successfully receive the beacons from the transmitter.Figure 6 shows the relationship between the average number of effective neighbors and the vehicle density. The number of effective neighbors increases almost linearly with the vehicle density. This is because a fixed neighborhood radius is applied to all vehicle densities. The proposed solution covers more vehicles on average since we take the number of neighbors as a part of the scheduling principle, especially in the high-density cases. Compared with figure 3, the number of effective neighbors is less than that of the geographical neighbors due to communication failures.

To evaluate the fairness of the proposed algorithm, the Jain’s fairness index is applied and de fined as follows.

wherexkis the total number of successfully received beacons of the k-th vehicle during the entire simulation. It is easy to conclude that the higher Jain’s index indicates a fairer scheduling algorithm. As shown in figure 7, the Jain’s fairness index increases with the vehicle density since the neighbor sets and the channel reliability of vehicles in the sparse scenario have a more diverse situation, especially when the density is as low as 10 vehicles per kilometer. Since the round-robin scheduling and IEEE 802.11p based broadcasting treat every vehicle equally, the Jain’s indexes are relatively stable when the density is greater than 50 vehicles per kilometer. The Jain’s index of AoI-based algorithm keeps increasing with the density and even exceeds that of round-robin and IEEE 802.11p based methods when the density is greater than 300 vehicles per kilometer. This is because that the AoI-based solution coherently takes the neighbors size and the channel reliability into account. Thus,the scheduling algorithm is able to accurately evaluate the importance of the vehicles in dense scenarios.

In the above results, it is found that the proposed algorithm has better performance in terms of the average AoI, peak AoI, and the effective number of neighbors. First, the average AoI and peak AoI indicating the freshness of information used in the vehicular networks are important to various time-sensitive applications such collision avoidance, path planning,etc. The lower AoI achieved makes the vehicle driving more reliable and safer. Second, the effective number of neighbors represents the successfully delivered copies of each beacon,which re flects the efficciency of the scheduling.Overall, the proposed algorithm achieves a more effective and efficcient beacon broadcasting scheduling.

Overall, based on the results presented above, the proposed algorithm achieves a satisfactory performance by maintaining a low total AoI, covering more vehicles and ensuring a certain level of scheduling fairness.

VI. CONCLUSION AND DISCUSSION

In this paper, we investigated the vehicular beacon broadcasting scheduling problem considering the Age of Information. To mitigate the collision and improve the data dissemination performance, a low-complexity greedy algorithm minimizing the expected sum AoI has been proposed for the broadcast scheduling.The proposed algorithm is theoretically proved to be optimal under the condition that the vehicles have the same number of neighbors and identical channel reliability which is close to the high-density scenario in reality. Extensive simulations are conducted to verify the superior performance of the proposed solution in terms of the efficiency, effectiveness and fairness. There are many issues worth further exploration. For instance, how to extend the work considering different channel reliability and vehicle distribution, how to incorporate the multiple channel operation to further improve the resource utilization are challenging issues beckoning more research.

ACKNOWLEDGMENT

The authors would like to thank the editor and the anonymous reviewers for their helpful and constructive comments, which have helped them improve the manuscript significantly.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC), and China Scholarship Council (CSC).