Guiyang Luo, Quan Yuan, Haibo Zhou, Nan Cheng, Zhihan Liu,＊, Fangchun Yang, Xuemin (Sherman) Shen

1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications,Beijing 100876, China

2 School of Electronic Science and Engineering, Nanjing University, Nanjing 210093, China

3 Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, N2L 3G1 Canada

Abstract: By leveraging the 5G enabled vehicular ad hoc network (5G-VANET), it is widely recognized that connected vehicles have the potentials to improve road safety,transportation intelligence and provide in-vehicle entertainment experience. However,many enabling applications in 5G-VANET rely on the efficient content sharing among mobile vehicles, which is a very challenging issue due to the extremely large data volume, rapid topology change, and unbalanced traffic. In this paper, we investigate content prefetching and distribution in 5G-VANET.We first introduce an edge computing based hierarchical architecture for efficcient distribution of large-volume vehicular data. We then propose a multi-place multi-factor prefetching scheme to meet the rapid topology change and unbalanced trafficc. The content requests of vehicles can be served by neighbors, which can improve the sharing efficiency and alleviate the burden of networks. Furthermore, we use a graph theory based approach to solve the content distribution by transforming it into a maximum weighted independent set problem.Finally, the proposed scheme is evaluated with a greedy transmission strategy to demonstrate its efficciency.

Keywords: content distribution; 5G-VANET;edge computing; graph theory

I. INTRODUCTION

Connected vehicles are envisioned to bring many benefits to current smart city development and our society, including reduction of traffic collisions, efficient transportation managements and more enjoyable life [1],[2]. However, to achieve these bene fits, a signi ficant volume of data exchange and a large amount of computing power are required.Moreover, the required data for connected vehicles are location-based and latency-constrained contents [3], [4]. For instance, the high definition (HD) map contains three-dimensional location of all crucial aspects of a roadmap (e.g., lane markings, crosswalks,signs, barriers) and dynamic information that facilitates driving (e.g., traffic snarls,road conditions, accidents, lane closures) [5].Therefore, the HD map has to be large volume in order to present highly detailed static and dynamic elements. In addition, before vehicles travel to a region, the local information of HD map needs to be updated periodically in order to keep pace with the changing driving conditions. To efficiently transmit such data, a deep integration among transmission,storage and computing is needed. Traditionally, transmission, storage and computing are separately orchestrated and designed, for the ease of management [3]. Taking the cloud computing as an example, the remote cloud,which has a large amount of computing and storage power, is responsible for computation and storage; meanwhile, the network is solely for data transmission between the cloud and users. These separated resources fail to satisfy the requirements on latency and quality of service of connected vehicles. Edge computing is emerged as a promising paradigm to deeply integrate transmission, storage and computing[4]. With edge computing, the communication,computing, storage and control capabilities are distributed anywhere along the continuum from the cloud to things [5].

In 5G enabled vehicular ad hoc network(VANET), which is referred to 5G-VANET[6], [7], by leveraging the edge computing technology, a signi ficant amount of computing power will be distributed near the vehicles.Therefore, a majority of data will be processed and stored at the edge, which can reduce latency and provide better quality of service for connected vehicles [8]. By utilizing the computing power at the edge, a better and real-time scheduling over the caching and transmission can be achieved. Furthermore,the knowledge learned from various big data help improve the content distribution efficciency. In 5G-VANET, control over the vehicular networks can be realized in order to schedule an efficient content distribution, as the edge has a signi ficant amount of computing power and can be aware of the context information over the nodes within its coverage [9]. Consequently, a deep integration among transmission, storage and computing is supported by 5G-VANET. Nevertheless, connected vehicles,with distinguishing features such as rapid movement, fast changing network topology and low latency, have exponentially increasing demands on data transmission, both for quantity and quality. These requirements pose several challenges to 5G-VANET. The first major challenge is how to enable cooperation among various communication modes, for example, dedicated short range communications(DSRC) and WiFi. These different communication modes have their own advantages and disadvantages and should be orchestrated to improve the network utilization [10]. The second challenge is how to fully utilize the unbalanced road trafficc and heterogeneous social attributes of vehicles. As the trafficc on the road is unbalanced, different areas have different number of vehicles. Therefore, vehicles may undergo a different network load and different quality of service. The content could be prefetched by vehicles in the areas with light traffic, and then, the vehicles obtaining the data in that area could serve as the data source when they enter into an area with heavy traffic.Besides, by cautiously choosing the vehicles which have longer encounter time and higher contact probability with other vehicles as data source [11], a higher data sharing efficiency can be achieved. The third challenge is how to meet requirements on efficciency and latency.

For effectively addressing the three main challenges, in this paper, we investigate the research challenges for content scheduling in 5G-VANET from the perspective of network operator. At first, a hierarchical architecture is proposed based on edge computing for efficient distribution of large-volume vehicular data in 5G-VANET. The proposed architecture consists of two tiers. In the upper tier, the city wide controller schedules the data caching from the view of the network wide and coordinates the resources of several marco base stations, thus handling the unbalanced trafficc.In the lower tier, each marco base station supports efficcient cooperation among various communication modes, which also enables the content requests of vehicles being served by neighbors. This cooperation can improve the sharing efficciency and alleviate the burden of networks. By carefully orchestrating the two tiers, we then propose a multi-place multi-factor prefetching scheme to meet the rapid topology change and unbalanced trafficc. In our proposed prefetching scheme, content can be prefetched into both fixed infrastructures and mobile nodes, considering social centrality and routes of mobile nodes. Furthermore,we adopt a graph theory based approach to solve the content distribution. We construct a neighbor graph by aggregating the information from vehicles, then, this neighbor graph is transformed into a matched graph, which can reduce the complexity. To further decrease the computation overhead, the match graph is divided into multiple subgraphs. The content distribution is transformed into a maximum weighted independent set (MWIS) problem based on each subgraph and this problem is addressed by a balanced greedy algorithm.

The remainder of this paper is organized as follows. The recent literature on content prefetching and distribution is reviewed in Section II. Then, an edge-assisted content sharing architecture in 5G-VANET is proposed in Section III. The details of research challenges are discussed in Section IV, followed by potential solutions and their application in Section V. Finally, the work is concluded and future research directions are discussed in Section VI.

II. LITERATURE REVIEW

Edge caching has been proposed recently to achieve backhaul of floading and improve the quality of services. Liet al. [12] utilized collaborative hierarchical caching to effectively improve the capacity of mobile networks.Tianet al. [13] investigated the problem that how the greediness and selfishness of individual nodes impact cooperation dynamics in VANETs. They proposed a decentralized self-organized relay selection algorithm based on a stochastic learning approach. Poularakiset al. [14] designed a mobility aware aching policy for hyper-dense small-cell networks,where the contact duration between users and small-cell base stations is quite limited. In addition, Mauriet al. [15] proposed to prefetch content at network nodes which can maximize the probability that a vehicle retrieves the desired content. Jiet al. [16] proposed a scheme that randomly caches popular contents on mobile devices and exploits device-to-device(D2D) communications to share cached contents. Chenget al. [17] studied vehicular D2D(V-D2D) communication and analyzed the potential of VD2D in content distribution. Our previous work [18], [19] proposed a software defined network (SDN) inspired MAC (sdn-MAC) protocol to manage vehicular network resources. sdnMAC can adapt to the topology change and varying density of vehicles. However, due to the sparse deployment and communication coverage of roadside units (RSU),these centralized algorithms suffer from poor scalability.

Besides, these data sharing schemes are of low efficiency, as they cannot make most of the advantages of different communication modes in the heterogeneous 5G-VANET.Besides, there also exist works that complement the VANET by other spectrum. Abboudet al. [20] surveyed potential DSRC and cellular interworking solutions for efficient V2X communications and reviewed potential DSRC-cellular hybrid architectures. Tianet al. [21] investigated a robust energy efficcient solution for multiple-input multiple-output(MIMO) transmissions in cognitive vehicular networks. They designed an optimal MIMO beamforming for secondary users, considering imperfect interference channel-state information. Zhouet al. [22] exploited TV white space in heterogeneous connected vehicular communication networks, and discussed white space channel availability and characteristics for vehicular communications. On the other hand, some recent studies have investigated the content delivery problem in heterogeneous vehicular networks. Chenet al. [23] adopted fog computing paradigm to implement software de fined vehicular networks. They developed a dynamic vehicular connection management approach to achieve quality of service guarantee. Considering the location-dependent content delivery, Yuanet al. [24] relied on the selected in fluential vehicles to effectively migrate cellular trafficc to vehicular networks.Guet al. [25] developed a content sharing approach in D2D based LTE-V2X networks.They jointly consider the data diversity and link quality when scheduling the V2V and V2I link. Liuet al. [26] proposed a cooperative data scheduling method in hybrid vehicular networks by solving a MWIS problem. Zhouet al. [27] proposed a cooperative data downloading schemes, by properly selecting the appropriate vehicles to form a linear cluster on the highway.

In this paper, we consider cooperative context aware networking in edge computing assisted 5G-VANET. Such a heterogeneous network, with different communication modes(cellular and DSRC), different caching ability and different computing resources within each nodes, they should cooperate to enable efficient data sharing. We decouple the context information sensing and the data dissemination,by adopting SDN concept. The cellular link is applied to collect context information while the DSRC is used to disseminate data among neighbors. This paper analyzes the characteristics of cooperative data sharing in such scenario, and designs a robust and efficcient approach for context aware networking, enabling effective cooperation.

III. THE ARCHITECTURE OF EDGE COMPUTING ASSISTED 5G-VANET

Currently, most computing infrastructure and software models are in a fully centralized manner, where the shared pools of configurable resources (e.g., computer networks, servers,storage, applications and services) are centrally operated, for the convenience of management, coherence and economy of scale. This fully centralized manner can hardly meet the requirements on latency, massive connections and massive transmissions. Decentralization is needed for these shared resources, which are distributed along the continuum from the cloud to things, that is the edge computing.Although the edge computing is a system-level horizontal architecture, it cannot be fully distributed. Decentralization is needed but centralization is also in demand, as decentralization can provide lower latency, higher capacity and scalability, while centralization can support better efficciency and flexibility.

Fig. 1. A hierarchical architecture of edge computing assisted vehicular content sharing.

Based on above considerations, we propose a hierarchical architecture of edge computing assisted vehicular content sharing, as shown in figure 1. As the resources of computing,communication, storage and control are distributed anywhere along the continuum from the cloud to things, the resources distribute over all nodes under this architecture. However, the nodes are heterogeneous and have different capabilities of storage, computing and networking. These nodes should cooperate with each other to make full use of resources and improve the data sharing performance.In addition, cooperation is also needed for optimally choosing different communication modes in heterogeneous VANETs. To enable efficcient cooperation and content sharing, the proposed architecture has two control and management tiers for coordinating the network resources and, in each layer, the control node can be SDN enabled. This two-tier control architecture which enables efficcient cooperation among various communication modes, can fully utilize the attributes of unbalanced trafficc and social interconnection, and can improve the data sharing performance.

For specific, the lower tier is macro base station (MBS), which has a comparatively smaller area. The MBS manage the small-cell base station, RSU, vehicles and WiFi nodes within its coverage. This tier supports efficcient cooperation among various communication modes, for example, the cellular link can be used to collect and transmit control information (similar to control plane in SDN), as this information has the characteristics such as wide coverage and unicast. Meanwhile, the DSRC and WiFi are better for content transmission, which are scheduled by the MBS. Actually, this is the efficcient cooperation among the MBS, RSU and vehicles. The MBS, which has global network information over relatively broader area and large computing power, is the best place for algorithm execution. Whereas the RSU and vehicle, which enjoy a high data rate connection with neighbors, can be best used to serve neighbors’ content requests. In the higher tier, a citywide controller (CWC)schedules the data caching from the view of the network-wide and coordinates the resources of several marco stations. For each MBS,the real-time traffic can be easily collected through the cellular communication. Consequently, the CWC can easily get the real-time trafficc and data requests, by aggregating the information from these MBSs. Furthermore, the history traffic traces, social connection data,and trafficc management data can be utilized to assist the caching. Using the knowledge mined from these big volume and multi-dimensional data, the network operator could predict the network congestion status and vehicle social centrality. Based on this information, the CWC could make more comprehensive decision on data prefetching.

The proposed architecture elaborately orchestrates the data prefetching and cooperative data sharing, which are two effective ways to alleviate the burden of the networks.In the proposed architecture, the data will be pre-fetched to the RSU or the vehicles with higher social centrality. After the prefetching,the RSU and these selected vehicles can act as the source of the data. The content download request can be served by neighbors, not necessary by base station (BS). The data dissemination takes place among RSU and vehicles and is scheduled by the MBS, which alleviates the burden of cellular networks, both for core networks and access networks.

IV. KEY RESEARCH CHALLENGES

5G enabled vehicular applications rely on the efficcient content sharing among mobile vehicles. However, it is very challenge to achieve efficcient content sharing due to the extremely large data volume, rapid topology change, and unbalanced traffic. In this following, we will discuss in detail the content prefetching and content distribution challenges in edge computing assisted 5G-VANET, respectively.

4.1 Content prefetching in edge computing assisted 5G-VANET

Content prefetching is a performance optimization tactic in which the content that might be accessed by the vehicles is downloaded in advance. Therefore, content prefetching can reduce the network resources consumed as well as the access latency perceived by vehicles. Content prefetching in VANET has its unique features and challenges. Vehicles are highly mobile and their trace are constrained by the road topology [28], which may deteriorate the unbalanced trafficc, resulting the unbalanced network resources utilization. Besides,there exist various perfect places for content prefetching. Speci fically, the performance may be in fluenced by many factors, which further complicate the prefetching.

A flexible and network-wide strategy is needed for content prefetching. Vehicles are fast moving, reaching the speed of 200 km/h.Therefore, vehicles may rapidly switch among many different BSs and the dwell time on each BS may vary dramatically. The dwell time is in fluenced by many factors, such as, the road attribute (road capacity, speed limits, traffic lights), trafficc congestion, and so forth. Another problem is unbalanced trafficc. Various factors have in fluence on trafficc, i.e., peak hours,traffic accidents, traffic controls. The unbalanced trafficc leads to unbalanced network resources utilization, where the network may be congested or even paralyzed in a dense trafficc scenario and the network is idle under a light traffic scenario. Therefore, the unbalanced traffic and the different dwell time deserve a flexible and network-wide content prefetching strategy.

A multi-place multi-factor strategy is required for content prefetching. The 5G-VANET is heterogeneous, one reason is that nodes have different capacity of storage and computing power. Furthermore, each node has its own social attribute and journey preference. Therefore, the fixed infrastructure such as RSU, WiFi and the vehicles have a high social centrality or have a suitable travel route can be selected as the place for prefetching.When we choose the places for prefetching,a lot of factors should be taken into consideration, for example, the point of interest (e.g.,petrol station, restaurant), where the vehicle may have longer dwell duration, road topology, and the variation of traffic. Therefore,the network operator needs a multi-place multi-factor strategy for content prefetching.

Although various prefetching strategies have been proposed, for example, least recently used, least frequently used, and the most popular, they are of low performance and can not meet the requirements on latency and real-time of data distribution.

4.2 Content distribution in edge computing assisted 5G-VANET

Once the content is prefetched at the selected nodes, the MBS should schedule the content distribution according to requests of vehicles.Each vehicle will request a lot of data, and these requested data can be transmitted by utilizing several communication modes, i.e.,cellular, DSRC and WiFi. From the perspective of network operator, it should try its best to meet all the requests by properly scheduling the content sharing through various communication modes. For each vehicle, the request can be satisfied by cellular link, DSRC, or WiFi channel. Therefore, these communication modes should cooperate with each other for better utilization of network resources.In most content sharing strategies, each link can transmit only one data item at a time for simpleness. As the capacity of different links is different, many data items can be disseminated by a high capacity link at a time. Therefore, taking the difference in link capacity into consideration, vehicles can disseminate multiple items at a time to improve the efficiency. On the other hand, the consideration of link capacity would increase the scheduling complexity, because the content needs to be divided into more items and multiple combinations of items can be disseminated by each vehicle. This complexity in computing and the improvement on efficiency should reach a matching point. Another way to decrease the scheduling complexity for the MBS is to split the region into multiple segments. As the number of nodes in each segment is small, the scheduling complexity will be greatly reduced.In [29], the road is divided into segments geographically and the algorithm is processed in each segment. However, such geographic split over the region would bring interference to other segments. Actually, a smarter segmentation scheme should be adopted to split the region, which will decrease the computing complexity without degrading degrade the performance.

V. POTENTIAL SOLUTIONS AND APPLICATION

In this section, we first present potential solutions to the above-mentioned research challenges, which include the content prefetching and the content distribution through vehicular networks. Then, we evaluate the proposed solutions in NS3 and Simulation of Urban Mobility (SUMO).

5.1 Content prefetching based on machine learning in edge computing assisted 5G-VANET

A network-wide multi-place multi-factor strategy is needed for content prefetching. We first need to predict the network wide trafficc variation, then decide prefetching places, considering multiple in fluencing factors.

In future VANETs, the trace of each vehicle can be collected. By mining the historical trace data, we could obtain the preference of the driver. Using driver preference, combined with road topology and navigation information, we can predict or obtain the travel journey of vehicles. Then, based on the real-time speed and position, the trafficc distribution can be predicted. Machine learning is very promising for the task of prediction both for the trace and for traffic situation. Therefore, we know the set of vehicles that will pass through each MBS, then, we can prefetch the corresponding data for these vehicles in advance. Furthermore, the network operator would of fload the content to a less congested BS, to alleviate the burden of congested BS. For example, a BS is predicted to be congested when a vehicle passes through it, then, the content for that vehicle can be prefetched in the previously associated uncongested BS. Thus, the vehicle can obtain the content before it enters the coverage of the congested BS.

The content can also be prefetched into moving nodes. For example, in the above example, a vehicle will pass through a congested BS. Actually, we could prefetch part of data into the vehicle, when it enters the congested area, the vehicle can serve some content requests through the DSRC. Therefore, the vehicles whose routes have a wider coverage over the road should be selected as the place for prefetching. The reason is that the vehicle whose route covers a wider coverage can serve the data requests of more nodes. To better improve the efficciency, the social connection of vehicles should be taken into consideration.The vehicles which have higher social centrality should be selected, where the social means a direct communication by DSRC or WiFi. A higher social centrality means a higher contact possibility with other nodes, which can dramatically improve the dissemination speed.

Fig. 2. The graph based content sharing for MBS.

Fig. 3. Prefetch popular content to macro base stations based on machine learning.

We could prefetch popular content to macro base stations (MBS) based on real-time predicted trafficc flow, which is shown in figure 3.The procedures are as follows: 1) Data crowdsensing. At first, a large number of sensors,e.g., the various sensors mounted on vehicles,the camera at the roadsides, the inductive loops, the hands-on devices of passengers,etc., will participate in sensing the traffic.These sensors will generate large-volume and heterogeneous data. 2) Data process at mobile edge server (MES). Transmitting these data into remote cloud for processing would congest the backhaul network and induce longer latency. As a consequence, these data will be processed and analyzed at the MES and only the necessary results will be transmitted into remote cloud. 3) Predict the traffic situation and schedule the load balancing at the remote cloud. We need to realtime construct the traffic situation, which requires the sensed trafficc information from all over the city. Therefore,each MES is required to upload the processed results to the remote cloud, then, the traffic situation can be real-time obtained and updated in remote cloud. Consequently, we could predict the traffic situation. Afterward,the remote cloud balance the large scale load based the predicted situation. 4) Data caching at the MES. MESs cache the data based on the predicted traffic situation. Consequently,

target vehicles can download the required data in a less congested network since their interested data are cached in advance. Based on the predicted trafficc, we could balance the load for MESs. As shown in figure 3, there exist two adjacent MESs, MES1 and MES2.Based on the predicted trafficc situation, MES2 will experience a higher load as there will be a large number of vehicles accumulated within the coverage of MES2. These vehicles could request more data transmission, which might exceed the overload and lead to a poor quality of service (QoS). The target vehicles that will passing from MES1 to MES2, can choose to download the interested data in MES1, experiencing a better QoS. A part of vehicles have already obtained their interested data when they arrive at MES2. Consequently, other vehicles in MES2 also experience a better QoS.Therefore, we need to pre-cache the interested data for the target vehicles in MES1 in advance.

5.2 Content distribution based on graph theory in edge computing assisted 5G-VANET

After the content is prefetched, the MBS should efficiently schedule cooperative content sharing. We consider the V2V and V2I are proceeded in the same service channel. The reason of such consideration is that the service coverage of RSUs is small, which is due to the expensive deployment of RSUs and the small communication range (300 - 1000 m) [30].Therefore, it would be of low efficciency for allocating a sole channel to V2I communication.The cellular link is mostly unicast and very expensive, while the DSRC communication is short range and specially for services in VANETs. Based on above considerations, we propose a three-phase content sharing scheduling mechanism, which is achieved by efficcient cooperation between cellular and DSRC [19],efficient cooperation between V2V and V2I,and efficient cooperation between computing and communication. This three-phase mechanism is introduced as follows:

Phase I:All the nodes are set to the DSRC mode and broadcast their beacons, so that each node is able to identify the list of its neighbors. A node can recognize the set of nodes with which it can transceive content and the corresponding channel capacity, by measuring the signal-to-noise ratio of the beacons [31].

Phase II:All the on-board units (OBU)communicate with MBS through the cellular link. Specifically, each vehicle informs the MBS with its updated information, including the list of its current neighbors, the channel capacity of each neighbor’s link and the identi fiers of the cached data items and un-cached data items. After all the OBUs update their information to MBS, these requests will be scheduled in an centralized manner. Based on the scheduling algorithm, the decisions are announced via the cellular link. This information is transmitted through the cellular link due to following reasons. On the one hand, RSUs have a shorter communication range and cannot cover entire roads, while the cellular link has a wider coverage. The data dissemination can be processed even without involvement of RSUs if transmitted by cellular links, which means that all OBUs should inform the MBS with their updated information and the scheduling decisions should be delivered to all related OBUs. On the other hand, this updated information is unicast, which is quite fit for cellular links.

Phase III:Each node obtains the requested content items from their neighbors by V2I or V2V communication based on the scheduling decisions. Multiple instances of content dissemination may take place simultaneously in this phase.

Based on the three-phase mechanism, we propose a graph based approach to efficciently schedule the data dissemination. To give an overview, we first present the basic idea of the proposed graph theory based content distribution. An undirected neighbor graph will be obtained by aggregating the received information at the MBS. Then, this neighbor graph is transformed into a directed matched graph.This matched graph is further divided into multiple subgraphs. We construct a conflict graph for each subgraph. The content sharing is formulated as finding the MWIS problem in the constructed conflict graph. Finally, a greedy algorithm is proposed to solve this problem.

The content is divided intolitems denotedthat are all of the same lengthC0. We suppose the channel is symmetric. The channel capacity can be calculated by:

whereWis bandwidth andSINRi,jis the signal-to-noise ratio (SINR) between nodeNiis the set of nodes on the roads.

To further improve the efficciency, multiple items can be transmitted on each link at each scheduling period. Therefore, the maximum number of data items that can be transmitted betweenNiandNjis denoted byMi,jin the scheduled periodT0, which can be calculated by:

1) Directed matched graph: For each senderNi, we denote the set of possible transmitted data items byImti. Each transmitted itemsshould be mathched withβjandMi,j. As illustrated by figure 2(a), for linkthis link is futile, as no valid data items can be transmitted, which is due to the unmatching betweenimtiandβj.

Therefore, a directed matched graphGdcan be constructed.

2) Graph split: By transforming theGuintoGd, a lot of impractical transmissions can be removed. The larger size of the neighbors graph, the higher complexity of the data sharing problem. Therefore, to further reduce the scheduling complexity, the matched graph can be divided into multiple subgraphs. This partition divides the graphGdinto multiple subgraphs, such that the subgraphs are of about the same size and there are few weighted connections between the subgraphs [32]. As illustrated by figure 2 (c), the graphGdis divided into two subgraphs, subgraph 1 and subgraph 2. These two subgraphs have nearly the same size and the total weight of connections between these two subgraphs are very small.Compared to the geographic split [29], this split is of higher efficciency. The reason is that this graph based split takes the data requests into consideration and can make the number of nodes for each subgraph more balanced.

3) Con flict graph: Based on this re fined directed matched graph, we further transform it into a con flict graphwhere the interference and communication constraints are indicated by the edge. For a nodeNiin the graphG, the set of neighbors is denoted bywhich can be calculated by:

whereWEi,jis the weight for the edgefor the graphshould satisfy the following conditions:

For eachimti(∈Imti), only the set of neighbors whose channel capacity are greater than or equal tocould successfully receive the transmitted data items. This set of neighbors is denoted byRS(imti), which is calculated by

As shown in figure 2(c), forN2, the neighbors areandfore,Forcan successfully receive the transmitted data items, that is,bothN3andN4can successfully receive the transmitted data items, that is

A tentative transmission (TT) consists of three indispensable parts: a sender nodeNi,transmitted data itemsimti(∈Imti) and a receiver nodewhich can be denoted by

Different TTs may be in con flict with each other due to the following constraints on data dissemination: each node can broadcast only one data items at a time (Constraint 1); a node cannot be both the sender and the receiver in the scheduling period (Constraint 2); data should not collide at receivers (Constraint 3).The corresponding three rules for identifying conflicting TTs, which are introduced as fol-lows:

Constraint 1:Two TTsand, this means thatNibroadcasts two different data items simultaneously, which is impossible to come true. For example,are in con flict with each other.

Constraint 2:Two TTs, this means that the nodeacts as both the sender and the receiver simultaneously. For example,are in con flict with each other.

Constraint 3:Two TTsthese two TTs are in con flict with each other because data collision happens at one of the receivers. For example,are in con flict with each other.

Based on each subgraphGs, we could construct a conflict graphGc. The constructing procedures are as follows: 1) For each nodeNiinGs, find theImtiby (5) and all the receiversby (6) for eachimti. The TTs forare. Create a vertex for each TT. 2) Set the weight of each vertexany two con flicting TTs, add an edge between the two corresponding vertexes. Through the above three procedures, the corresponding undirected conflict graph can be constructed fromGs. The con flict graph of Subgraph 1 is illustrated in figure 4.

4) Content sharing scheduling

Based on the constructed undirected conflict graph (Gc), we could reformulate the cooperative data sharing problem as a MWIS problem. For the constructed weighted graphwhereVcis the set of vertexes andEcis the set of edges. Each vertex is associated with a weight, which isThe MBS node needs to improve content sharing efficciency, maximizing the total number of valid items can be received. This is equivalent to find the MWISon the conflict graphwhereF(X) is the total weight for the vertex setX.

Fig. 4. Undirected con flict graph of subgraph 1.

Fig. 5. Simulation map.

A greedy method presented in [33] is adopted to approximately solve MWIS, which is Greedy-MWIS. This greedy algorithm operates as follows. First, it computes the value offor each vertextiinrepresents the degree ofti.Second, it selects the vertextselectedwith the maximum value ofit updatesGcby removing the set of vertex-containstselectedand all of its adjacent vertexes. Fourth,it repeats the above operations until there is no vertex remaining inGc. These selected vertexes make up a feasible independent set. Proposition.1 gives the lower bound of Greedy-MWIS [33], which proves the feasibility of this algorithm.

Proposition 1G r e e d y-M W I S o u tputs an independent set of weight at least

We denote the weight of a maximum independent set of graphGbyα(G). For an independent set algorithmA,A(G) is the weight of the solution obtained byAon graphG. The performance ratioρ(A) ofAis defined by:

whereinf{a} is the in fimum overa.

The performance ratio indicates the efficiency of an algorithm. The efficiency of Greedy-MWIS can be ensured by Proposition 2 [32].

Proposition 2whereis the maximum degree of graph

The requested popular content is of large size, and, with the mobility of vehicles, each vehicle will request new popular content. For example, when each vehicle arrives at a new location, it may need the parking information and the high de finition map for that area.Therefore, the scheduling algorithm should be executed periodically. The scheduling decision in current time slot may have in fluence on future scheduling. For example, if cached data items between nodeNiand its neighbors are the same, then no data can be shared among these nodes. The reason is that the distribution of data items is unbalanced.The balanced rate for the set of vehiclesacaching the set of itemsμis defined asf(a,)μ, which can be denoted by:

After the Greedy-MWIS has decided the set of sender nodes and corresponding transmitted itemswe should replace the transmitted itemswith the set of data itemsthat has a higher balanced rate, which can be denoted by:

At the same time, this set of data items can not reduce the number of valid data items can be received, i.e.,. For example,the RSU cached all the data items, while the vehicles cached very small number of data items. At the beginning of the scheduling, the RSU may have a lot of data items to be disseminated into vehicles. Themay not be unique, whileis the set of data items that has the highest balanced rate. This algorithm is termed as BMWIS, which can improve the solution obtained by Greedy-MWIS. The pseudo code of BMWIS is shown in Alg.1.

After the independent setXofVcis derived, we could easily get: 1) The set of sender nodes isThe set of data items that will be transmitted for sender nodeNiisimti′. This content sharing algorithm should be executed periodically by the CWC node to support efficcient and sustained cooperative data dissemination.

The proposed scheduling algorithm, which is called CDEC, for cooperative data dissemination in edge computing assisted 5G-VANET.CDEC maximizes the total number of received valid data items, enabling cooperative data dissemination between RSUs and OBUs,cooperation between cellular communication and DSRC communication, and cooperation among communication and computing. CDEC is proceeded with the following steps:

Step 1:Construct the undirected neighbor graphGu. By integrating the updated context information, including the list of current neighbors, the channel capacity of each neighbor’s link and the identi fiers of the cached and un-cached data items,Gucan be constructed in the MBS.

Step 2:Construct the directed matched graphGd. By matching theimtiwithβjandMi,jfor each linkinGu,Gdcan be constructed.

Step 3:Partition theGdinto multiple subgraphs (Gs).

Step 4:Construct the undirected conflict graphGcbased on each subgraphGs. For each nodeNiinGd, obtain all TTsImtiand the weight of each TTAdd an edge if two TTs are in con flict with each other, according to the constraints.

Step 5:Solve the MWIS problem on the constructed conflict graph. Then, it selects a subset of TTsXbased on BMWIS.

Step 6:Construct scheduling results from the selected subsetX. The RSU and OBU disseminate the data according to the scheduled results.

5.3 Performance analysis

To verify the performance of the proposed algorithm, the simulation is conduct on SUMO and NS3. We make realistic assumptions on the channel model for the cellular links. As for the DSRC communication, the communication quality is highly affected by severe shadowing in VANETs [34]. Therefore, we assume the communication link exists only between vehicles with a LOS, or equivalently between“neighbors” [31]. In the scheduling period,we adopt the Rician model for small-scale fading with the propagation loss factorn=4.

Fig. 6. Ratio of possessed items.

Fig. 7. Average delay.

The channel capacity between any two nodesat the scheduling period, is then given by

wheredi,jis the distance between nodeiand nodej,ηis the SINR at transmitters,Wis the channel bandwidth, andhis the Rician channel gain.

We assume that the content is prefetched into the RSU or vehicles. This graph based scheduling is compared with a greedy non-cooperative approach (Random-greedy)and Greedy-WMIS, in which each nodeNibroadcasts the data items which ensure that maximum of valid data items can be delivered as long as the channel is detected to be unoccupied. The simulation map is illustrated by figure 5, which is generated by SUMO. We adopt the line of sight channel model [29] for DSRC links and make realistic assumptions on the channel model for the cellular links,the capacity for each link is calculated by (1).The content has size of 100 M. The maximum communication range for DSRC is 100m.

Figure 6 shows the ratio of total possessed items when the number of nodes is 200, whichin each scheduling period.

Fig. 8. Number of transmissions in each scheduling period.

The proposed scheduling algorithm BMWIS enjoys the highest speed in disseminating all the data items, as the requests can be satis fied quickly. As for the Random-greedy algorithm,transmitting all the requested data items cannot be fully accomplished at the end of the simulation. This is due to the fact that heavy interference among neighboring transmission.Because of lacking of coordination among neighboring transmissions, the exposed terminal and hidden terminal problem would further degrade the performance, which is of low efficiency and a waste of network resources.BMWIS shares a higher speed than Greedy-MWIS algorithm in data sharing. The reason behind this is that BMWIS can improve the solutions obtained by Greedy-MWIS, which is achieved by disseminating the set of data items which have the highest balanced rate.This more balanced distribution of data items makes sure that the distribution of data is more balanced, resulting that each data request has a higher possibility of being serving by their neighbors. Consequently, BMWIS shares a higher dissemination speed over Greedy-MWIS.

Figure 7 shows the average delay under different number of nodes. As illustrated by this figure, BMWIS can make sure the data items be disseminated at the fastest speed,thus enjoying the lowest average delay, while Random-greedy has the highest average delay.With the number of nodes increases, there exist more neighbors for each node. As a result, each request has a higher probability to be served. What’s more, each transmission can disseminate multiple items and multiple receivers can receive these items, as the broadcast nature of DSRC. This can be figured out in figure 7, with the increasing number of nodes, the average delay is decreasing.

Figure 8 and figure 9 present the number of served nodes and number of transmissions in each scheduling period. The number of served nodes in each scheduling period is amount of nodes which can successful receive a packet.As can be illustrated by these two figures, BMWIS and Greedy-MWIS have nearly the same number of transmissions in each scheduling period, while many nodes for Random-greedy are selected as the senders. Meanwhile, BM-WIS and Greedy-MWIS make sure that more nodes will be served, which will make sure that more data items will be delivered successfully. However, Random-greedy can only serve a small number of nodes, in spite of the fact that it has the largest number of transmissions in each scheduling period.

VI. CONCLUSION AND FUTURE DIRECTIONS

In this paper, we have studied several key issues on cooperative sharing of large volume of vehicular data in edge computing assisted 5G-VANET. First, a hierarchical architecture has been proposed to support efficcient content prefetching and data distribution at the edge.Second, to efficciently schedule vehicular content distribution, a graph theory based scheduling scheme has been developed. Simulation results have been provided to demonstrate the superior of the scheme. To fully leverage the power of edge computing assisted 5G-VANET,some future research issues are provided as follows.

Data aggregation and data mining in edge computing assisted 5G-VANET— In 5G-VANET, things such as vehicles, RSU,small cell, macro base station, and users, can generate a lot of data. If these data are properly utilized, useful knowledge can be mined from these data, which can improve the efficiency of data sharing and the intelligence of nodes.

Security and privacy in edge computing assisted 5G-VANET— The CWC and MBS,with global information and large computing power, can coordinate and control the network, and can ensure security and privacy for 5G-VANET.

Computing cooperation in edge computing assisted 5G-VANET— In 5G-VANET,each node has resources of computing. These computing resources can be shared to maximize the utilization. The base station can offload the computing tasks to vehicles, and the vehicle can also of fload the computing tasks to the BS.

Fig. 9. Number of served nodes in each scheduling period.

ACKNOWLEDGMENT

The authors acknowledge the support of National Science and Technology Major Project of the Ministry of Science and Technology of China under Grant No. 2016ZX03001025-003, the Natural Science Foundation of Beijing under Grant No. 4181002, the Natural Science Foundation of China under Grant No.91638204, BUPT Excellent Ph.D. Students Foundation under Grant No. CX2018210, and Natural Sciences and Engineering Research Council (NSERC), Canada.