# Software-Defined Collaborative Offloading for Heterogeneous Vehicular Networks

Authors: Wei Quan; Kai Wang; Yana Liu; Nan Cheng; Hongke Zhang; Xuemin (Sherman) Shen
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Vehicle-assisted data offloading is envisioned to significantly alleviate the problem of explosive growth of mobile data traffic. However, due to the high mobility of vehicles and the frequent disruption of communication links, it is very challenging to efficiently optimize collaborative offloading from a group of vehicles. In this paper, we leverage the concept of Software-Defined Networking (SDN) and propose a software-defined collaborative offloading (SDCO) solution for heterogeneous vehicular networks. In particular, SDCO can efficiently manage the offloading nodes and paths based on a centralized offloading controller. The offloading controller is equipped with two specific functions: the hybrid awareness path collaboration (HPC) and the graph-based source collaboration (GSC). HPC is in charge of selecting the suitable paths based on the round-trip time, packet loss rate, and path bandwidth, while GSC optimizes the offloading nodes according to the minimum vertex cover for effective offloading. Simulation results are provided to demonstrate that SDCO can achieve better offloading efficiency compared to the state-of-the-art solutions.


---

## Body

## 1. Introduction

With the significant advance of automobile technologies, the Internet of vehicles (IoV) is becoming a standard feature in the near future, where vehicles are equipped with advanced communication devices, and exchange data and information through vehicle-to-everything (V2X) communications [1, 2]. Enabled by IoV technologies, a myriad of emerging vehicular applications occur to enrich the transport ecosystem, such as real-time high-definition navigation, multimedia services on wheels, and self-driving system [3, 4]. However, these applications and services require an exponential escalation of mobile data, which should be efficiently supported by the vehicular networks.Many wireless communications technologies are developed to support the potential vehicular scenarios. For instance, the Dedicated Short-Range Communication (DSRC) enables efficient real-time information exchange among vehicles [5]. Wireless Access for Vehicular Environment (WAVE) has been applied to the Vehicle-to-Infrastructure (V2I) communications [6]. The Long-Term Evolution (LTE) has the ability to support vehicular communications in a wide range [7, 8]. Not surprisingly, cellular network technologies play a vital role in providing ubiquitous and reliable Internet access for mobile vehicles. However, the LTE network nowadays is straining to meet the current mobile data demand. With the explosive growth of vehicular data, LTE networks are easily overloaded and degrade the experience of both nonvehicular and vehicular users.Therefore, simply using the single type of access technologies is far from enough to satisfy all the requirements of vehicular services. Researchers have considered solutions to offload traffic from the core network to other wireless networks [9, 10]. This solution can effectively reduce the congestion of transmission paths in the core network. Figure 1 describes three typical offloading scenarios in a heterogeneous vehicular network, where the traffic is offloaded from macro base station via small cell base stations, ad hoc networks (no base station), and WiFi access points, respectively. For example, WiFi offloading can alleviate the congestion in cellular networks by delivering data through WiFi access instead of the cellular base station [11]. Statistics show that more than 60 percent of the cellular traffic can be offloaded by WiFi networks.Figure 1
Offloading scenarios in heterogeneous vehicular networks.Recently, the fifth generation (5G) mobile communications system is also designed to integrate networking, computing, and storage resources into one programmable and unified infrastructure. It is not only an evolution of mobile broadband networks but also a collaborative ecosystem of heterogeneous communications technologies. Therefore, the data offloading via various communications technologies has been considered in the 5G deployment. With this feature, 5G has a great potential of providing massive access, high reliability, global coverage, and very low latency for challenging situations like vehicular networks.However, efficiently offloading the vehicular data is a challenging issue. In the vehicular environment, data offloading is opportunistic due to the limited coverage of heterogeneous wireless technologies and high mobility of vehicles [12]. The connection time between a vehicle and an offloading point (e.g., WiFi access points and small cell base stations) might be very short; therefore the content sources and transmission paths will be highly dynamic. Therefore, with such dynamics, the quality of service (QoS) requirements are difficult to guarantee.Software-defined networking (SDN) provides a promising and referable approach due to the features of centralized controlling, global decision, and high execution power. Our previous work has investigated a new networking paradigm named Smart Identifier NETworking (SINET) and proposed a SINET customized solution for software-defined vehicular networks (SINET-V) [13, 14]. Based on such a SINET-V architecture, in this paper, we propose a software-defined collaborative offloading (SDCO) solution, which employs a centralized software-defined controller to globally distribute offloading policies to vehicular nodes in heterogeneous vehicular networks. Specifically, the hybrid awareness path collaboration (HPC) and the graph-based source collaboration (GSC) are considered in the offloading controller. HPC is in charge of selecting the suitable paths based on the round-trip time, packet loss rate, and path bandwidth, while GSC optimizes the offloading nodes according to the minimum vertex cover for effective offloading. These specific functions are detailed in the following sections.The remainder of this paper is organized as follows. In Section2, we analyze the related works on offloading management. In Section 3, we describe the proposed SDCO solution and the optimization model. In Sections 4 and 5, we detail the specific functions for collaborative offloading: hybrid-awareness path collaboration and graph-based source collaboration. Simulation results validate the performance of SDCO in Section 6. Finally, we conclude the paper and discuss the future works in Section 7.


## 2. Related Works

Currently, many research efforts have begun towards realizing efficient heterogeneous vehicular communications in a cooperative manner. In our previous work, a collaborative vehicular edge computing framework named as CVEC is introduced to support more scalable vehicular services and applications [15]. Chen et al. presented a novel architecture of software-defined Internet of vehicles (SD-IoV) and developed a centralized vehicular connection management approach to guarantee the QoS [16]. Zheng et al. presented a multilayer and soft-defined HetVNET with a far more flexible configuration capability [17]. Dong et al. analyzed the issues of energy-efficient cluster management in heterogeneous vehicular networks [18]. Zhang et al. proposed a software-defined space-air-ground integrated network architecture for supporting diverse vehicular services [19]. However, the above newest research mainly concentrated on the general architecture designs for heterogeneous vehicular networks yet failed to analyze the specific offloading mechanisms.In the aspect of offloading management, Liu et al. proposed an incentive mechanism for computation offloading by using edge computing to deliver computation to the edge of pervasive networks nearby mobile users [20]. Cheng et al. discussed data offloading technologies for big data driven vehicular network [21]. Aijaz et al. made a survey on mobile data offloading from both technical and business views [22]. Zhuo et al. proposed an incentive framework to motivate users to offload cellular traffic with minimal cost [23]. To minimize the incentive cost, sources with large offloading potential and delay tolerance are preferred in their solution. Lee et al. focused on a quantitative study on the performance of mobile data offloading through WiFi access [24]. Singh et al. built a general and tractable model to analyze data offloading in heterogeneous networks [25]. Besides, Cheng et al. used a queueing model to analyze the opportunistic WiFi offloading in vehicular networks [26]. Rebecchi et al. made a complete survey on the data offloading techniques in cellular networks, including classification of mobile data offloading, nondelayed offloading, delayed offloading, assessing mobile data offloading, and open challenges [9]. However, there are few works on how to collaborate among different offloading schemes in heterogeneous network scenarios.Thanks to these efforts, some progress has been made on understanding the collaborative offloading in vehicular networks. However, there are still several challenges waiting to be overcome due to the intractable characteristics in vehicular environment. This paper leverages the advantages of SDN and proposes a SDN-based collaborative offloading for heterogeneous vehicular networks, which can globally and efficiently distribute offloading policies to vehicular nodes.


## 3. System Modelling and Problem Formulation

### 3.1. System Modelling

The typical offloading is to use local communication to offload the opportunistic traffic of the base station. Neighboring peers can communicate with each other without using a network infrastructure and can retrieve the expected content from the peer. It can support to dynamically adjust the access mode for the user equipment and then offloads the data traffic of the macro base station to the small base station.In SDCO, we employ a centralized software-defined controller to globally distribute offloading policies to vehicular nodes. This design aims to guarantee the transmission reliability by avoiding a large delay in distributed negotiation. It can also improve the overall network throughput and alleviate the problem of mobile data traffic congestion. Figure2 shows the SDCO system architecture. Based on this architecture, we will focus on how the controller makes optimization for efficient offloading policies.Figure 2
The SDCO system architecture.


### 3.2. Problem Formulation

Typical offloading allows users to relay data through other users within the network coverage, indirectly accessing the base station for data resources. In addition, the offloading scheme allows UEs with certain QoS requirements, in particular, to guarantee UEs with high-speed mobility to access the macro base station so as to avoid frequent handovers. We transferred this problem as a 0-1 linear programming problem, by which to determine the best source and preferred access mode for each user, for example, to select the base station or relay nodes. The objective is to maximize the amount of access users by offloading some users to the small base station so that the system can serve more UEs. Based on the above considerations, the optimization model is defined as follows:(1)maxx,y,zN=∑k=1K∑j=1Jyjk+∑m=1Mzmk,(2)∑j=1Jxmj+∑k=1Kzmk≤Cm,(3)∑m=1Mzmk+∑j=1Jyjk≤1,(4)∑k=1Kyjk≤∑m=1Mxmj≤1,(5)xmj≤1-∑k=1Kyjkgmkemj,∀j∀m>0.xmjdenotes the binary variable characterizing the connection status between base station (bm) and relay node (rj), 0 for without connection and 1 with connection.yjk denotes the binary variable characterizing the connection status of user dk and rj, 0 for without connection and 1 for with connection.zmk denotes the binary variable characterizing the connection state between dk and bm, 0 for without connection and 1 for with connection. In formula (1), ∑k=1K∑m=0Mzmkindicates the number of users connected to the network through the relay node. Formulas (2)–(5) are constraints. Wherein, formula (2) indicates that the maximum number of users and relay nodes which the base station can connect with is Cm, that is, the capacity of the base station. Formulas (3) and (4) indicate that each user node can only be connected with one base station or relay node at most at any time.If a user node needs to connect to a base station through a relay node, the user must be out of coverage of the base station, so it is limited by formula (5). gmk indicates whether dkis within the coverage ofbm, 1 means it is within its range, and 0 means it is not. emj indicates whetherrjis within the coverage of bm, 1 means it is within its range, and 0 means it is not.To resolve this optimization problem, a greedy search can be used to achieve the optimized solution for the offloading problem. However, it might be a time-consuming task to achieve a globally optimized solution, especially for a large-scale scenario. In practical operations, the controller can aware more information, like the dynamic topology, mobility trace, connection relationship, and so on. Therefore, in this work, we proposed two mechanisms to assist the controller to make offloading decisions. One is the hybrid awareness path collaboration (HPC) function, and the other one is the graph-based source collaboration (GSC) function. Both of them will be detailed in the following sections.


## 3.1. System Modelling

The typical offloading is to use local communication to offload the opportunistic traffic of the base station. Neighboring peers can communicate with each other without using a network infrastructure and can retrieve the expected content from the peer. It can support to dynamically adjust the access mode for the user equipment and then offloads the data traffic of the macro base station to the small base station.In SDCO, we employ a centralized software-defined controller to globally distribute offloading policies to vehicular nodes. This design aims to guarantee the transmission reliability by avoiding a large delay in distributed negotiation. It can also improve the overall network throughput and alleviate the problem of mobile data traffic congestion. Figure2 shows the SDCO system architecture. Based on this architecture, we will focus on how the controller makes optimization for efficient offloading policies.Figure 2
The SDCO system architecture.


## 3.2. Problem Formulation

Typical offloading allows users to relay data through other users within the network coverage, indirectly accessing the base station for data resources. In addition, the offloading scheme allows UEs with certain QoS requirements, in particular, to guarantee UEs with high-speed mobility to access the macro base station so as to avoid frequent handovers. We transferred this problem as a 0-1 linear programming problem, by which to determine the best source and preferred access mode for each user, for example, to select the base station or relay nodes. The objective is to maximize the amount of access users by offloading some users to the small base station so that the system can serve more UEs. Based on the above considerations, the optimization model is defined as follows:(1)maxx,y,zN=∑k=1K∑j=1Jyjk+∑m=1Mzmk,(2)∑j=1Jxmj+∑k=1Kzmk≤Cm,(3)∑m=1Mzmk+∑j=1Jyjk≤1,(4)∑k=1Kyjk≤∑m=1Mxmj≤1,(5)xmj≤1-∑k=1Kyjkgmkemj,∀j∀m>0.xmjdenotes the binary variable characterizing the connection status between base station (bm) and relay node (rj), 0 for without connection and 1 with connection.yjk denotes the binary variable characterizing the connection status of user dk and rj, 0 for without connection and 1 for with connection.zmk denotes the binary variable characterizing the connection state between dk and bm, 0 for without connection and 1 for with connection. In formula (1), ∑k=1K∑m=0Mzmkindicates the number of users connected to the network through the relay node. Formulas (2)–(5) are constraints. Wherein, formula (2) indicates that the maximum number of users and relay nodes which the base station can connect with is Cm, that is, the capacity of the base station. Formulas (3) and (4) indicate that each user node can only be connected with one base station or relay node at most at any time.If a user node needs to connect to a base station through a relay node, the user must be out of coverage of the base station, so it is limited by formula (5). gmk indicates whether dkis within the coverage ofbm, 1 means it is within its range, and 0 means it is not. emj indicates whetherrjis within the coverage of bm, 1 means it is within its range, and 0 means it is not.To resolve this optimization problem, a greedy search can be used to achieve the optimized solution for the offloading problem. However, it might be a time-consuming task to achieve a globally optimized solution, especially for a large-scale scenario. In practical operations, the controller can aware more information, like the dynamic topology, mobility trace, connection relationship, and so on. Therefore, in this work, we proposed two mechanisms to assist the controller to make offloading decisions. One is the hybrid awareness path collaboration (HPC) function, and the other one is the graph-based source collaboration (GSC) function. Both of them will be detailed in the following sections.


## 4. Hybrid Awareness Path Collaboration Function

The controller with global network information will promote the path collaboration more efficiently. SDCO adopts the HPC mechanism to address the path collaboration issue. Different from other existing solutions, the HPC mechanism is based on a new hybrid path metric, termed asQ. This path metric is able to synthetically depict the path status by considering three different parameters: Round-Trip Time (RTT), the packet loss rate (LOSS), and the path bandwidth (BWT). In the initial phase, the controller can obtain the real-time path status Qi for the path i through sensing and notification from the nodes. Then, the controller will check whether the path status Qi is bigger than a threshold τ to determine whether to add the path into the path scheduling list (PSL). Besides, the controller will monitor the variation of the status of each path in the PSL and then trigger an update to maintain the list. If the variation exceeds a threshold ω, this path will be updated in the PSL. Figure 3 illustrates the process of the HPC mechanism. In the following, we introduce the hybrid awareness path collaboration in detail.Figure 3
The process of the HPC mechanism.


### 4.1. Path Metric Calculation

In this section, we define a new path metric to synthetically depict the path quality. The metric of each path relies on three link parameters: RTT, LOSS, and BWT.To be general, both RTT and LOSS need to be considered to evaluate link quality. Based on this, we make a further revision. We believe that there is a close relation between the path bandwidth and the path quality. The path bandwidth reflects the maximum throughput that the link can achieve within a unit time. Therefore, it is necessary to correctly reflect the actual situation of the paths by considering the above factors comprehensively.(6)PATH=P1,P2,…,Pi,…,Pn,n≥2.In the following, we take PATH as a group of available paths between the vehicular users and the services providers, as shown in formula (6). We define Qi as the path metric of Pi, as shown in formulas (7), (8), and (9). It is easily to see that the better the path quality is, the bigger the metric value Qi is.(7)Qi=α·1RTTi+β·BWTi+θ·1LOSSi,(8)α+β+θ=1,(9)0≤α,β,θ≤1.In the formula (7), RTTi represents the RTT value of Pi, BWTi is the path bandwidth of Pi, and LOSSi is the packet loss rate of Pi. In addition, α, β, and θ are all positive constants less than 1 determined by the weight of each parameter. For example, if the RTT of each path affects the path quality more than the other two parameters, α will be accounted for the largest proportion compared with β and θ. The following gives a method to calculate the value of α, β, and θ in this paper.(10)X^t=Xt-XminXmax-Xmin,X∈RTT,BWT,LOSS,(11)εX=σX^μX^.We introduce the definition of fluctuation intensity, which reflects the influence coefficient of a path parameter. If a path parameter has a big fluctuation intensity, it means this path parameter affects the path greatly. In this paper, we calculate the value ofα, β, and θ by using the jitter intensity of each path parameter. Firstly, three parameters are normalized by min-max normalization as shown in formula (10). Then, the standard deviation factor ε is used to indicate the fluctuation intensity as shown in formula (11); σ represents the standard deviation of the parameter and μ is defined as the mean value. Finally, formula (12) shows the calculation method of α, β, and θ.(12)α=εRTTεRTT+εBWT+εLOSS,β=εBWTεRTT+εBWT+εLOSS,θ=εLOSSεRTT+εBWT+εLOSS.With the above knowledge, the path metric for each path can be obtained by formula (7). Besides, the offloading controller will constantly monitor and update the path metric for each path. If there are packets needed to be sent, available paths will be scheduled according to the path metric. In the following, the detailed scheduling policy will be presented.


### 4.2. Path Collaboration Policy

The offloading controller will guide each vehicle user to select suitable paths according to the path management. The information includes the sequence of available paths and the path metric of these paths. The quality of pathPi is calculated based on formula (7). After that, available paths list S can be obtained. We take S={S1,S2,…,Sj,…,Sm} as a group of available paths and sort them by the path metric. The Qi value of Si is bigger than Si+1. The better the path quality is, the bigger the path metric value is.In the HPC mechanism, the parameterτ is proposed as the path selection threshold. On the one hand, paths with Qi≥τ can be treated as available paths. In other words, paths with Qi≥τ will be abandoned temporarily to ensure that packets are able to be sent first via the better paths. On the other hand, Qit is dynamic with the time t. When Qit-Qit-1≥ω, the path scheduling list S updates, where the parameter ω works as the switching threshold. If the link quality varies slightly (Qit-Qit-1<ω), path scheduling sequence will not update. This design is able to minimize the number of link switching and ensure the stability of path scheduling.It should be noted thatτ and ω can be obtained by the experience of a number of experiments. Before the data sending, the path scheduling policy will select the paths according to the order of the array S. The first one in the array will be the best path. Here, an efficient lookup method can be used to match the delivery path [27]. The controller can select a best path based on its integral link quality and can avoid the blind roll polling in Round Robin mechanism.The specific path scheduling is shown in Algorithm1.Algorithm 1:Hybrid awareness path collaboration.
Initialization: Path array S=ϕ; getSD() is the function of calculating standard deviation factor; getC() is the function of calculating weight coefficient α, β and θ; getPW() is the function of calculating path metric value Qi; Sort ( Ω , Q i ) is to sort the members in Ω based on Qi in ascending. void HPCFunctionPATH=P1,P2,…,Pi,…,Pn,n≥2 for each  Pi ∈ PATH  do ε R T T = getSD(Pi, RTT); ε B W T = getSD(Pi, BWT); ε L o s s = getSD(Pi, LOSS); α = getC(εRTT); β = getC(εBWT); θ = getC(εLOSS); Q i = getPW(α,β,θ); if  Qi≥τ; S.append(Pi); end end S = S o r t ( S , Q i ); for each  Pi∈S  do if  Qit-Qit-1≥ω; S = S o r t ( S ,  Q i ); end end deliver packets based on the S sequence. endThe above HPC function guides the controller to select the optimal paths to balance the traffic load for vehicle users. Afterwards, we will further consider how to determine the number of offloading nodes and select them in an optimal manner.


## 4.1. Path Metric Calculation

In this section, we define a new path metric to synthetically depict the path quality. The metric of each path relies on three link parameters: RTT, LOSS, and BWT.To be general, both RTT and LOSS need to be considered to evaluate link quality. Based on this, we make a further revision. We believe that there is a close relation between the path bandwidth and the path quality. The path bandwidth reflects the maximum throughput that the link can achieve within a unit time. Therefore, it is necessary to correctly reflect the actual situation of the paths by considering the above factors comprehensively.(6)PATH=P1,P2,…,Pi,…,Pn,n≥2.In the following, we take PATH as a group of available paths between the vehicular users and the services providers, as shown in formula (6). We define Qi as the path metric of Pi, as shown in formulas (7), (8), and (9). It is easily to see that the better the path quality is, the bigger the metric value Qi is.(7)Qi=α·1RTTi+β·BWTi+θ·1LOSSi,(8)α+β+θ=1,(9)0≤α,β,θ≤1.In the formula (7), RTTi represents the RTT value of Pi, BWTi is the path bandwidth of Pi, and LOSSi is the packet loss rate of Pi. In addition, α, β, and θ are all positive constants less than 1 determined by the weight of each parameter. For example, if the RTT of each path affects the path quality more than the other two parameters, α will be accounted for the largest proportion compared with β and θ. The following gives a method to calculate the value of α, β, and θ in this paper.(10)X^t=Xt-XminXmax-Xmin,X∈RTT,BWT,LOSS,(11)εX=σX^μX^.We introduce the definition of fluctuation intensity, which reflects the influence coefficient of a path parameter. If a path parameter has a big fluctuation intensity, it means this path parameter affects the path greatly. In this paper, we calculate the value ofα, β, and θ by using the jitter intensity of each path parameter. Firstly, three parameters are normalized by min-max normalization as shown in formula (10). Then, the standard deviation factor ε is used to indicate the fluctuation intensity as shown in formula (11); σ represents the standard deviation of the parameter and μ is defined as the mean value. Finally, formula (12) shows the calculation method of α, β, and θ.(12)α=εRTTεRTT+εBWT+εLOSS,β=εBWTεRTT+εBWT+εLOSS,θ=εLOSSεRTT+εBWT+εLOSS.With the above knowledge, the path metric for each path can be obtained by formula (7). Besides, the offloading controller will constantly monitor and update the path metric for each path. If there are packets needed to be sent, available paths will be scheduled according to the path metric. In the following, the detailed scheduling policy will be presented.


## 4.2. Path Collaboration Policy

The offloading controller will guide each vehicle user to select suitable paths according to the path management. The information includes the sequence of available paths and the path metric of these paths. The quality of pathPi is calculated based on formula (7). After that, available paths list S can be obtained. We take S={S1,S2,…,Sj,…,Sm} as a group of available paths and sort them by the path metric. The Qi value of Si is bigger than Si+1. The better the path quality is, the bigger the path metric value is.In the HPC mechanism, the parameterτ is proposed as the path selection threshold. On the one hand, paths with Qi≥τ can be treated as available paths. In other words, paths with Qi≥τ will be abandoned temporarily to ensure that packets are able to be sent first via the better paths. On the other hand, Qit is dynamic with the time t. When Qit-Qit-1≥ω, the path scheduling list S updates, where the parameter ω works as the switching threshold. If the link quality varies slightly (Qit-Qit-1<ω), path scheduling sequence will not update. This design is able to minimize the number of link switching and ensure the stability of path scheduling.It should be noted thatτ and ω can be obtained by the experience of a number of experiments. Before the data sending, the path scheduling policy will select the paths according to the order of the array S. The first one in the array will be the best path. Here, an efficient lookup method can be used to match the delivery path [27]. The controller can select a best path based on its integral link quality and can avoid the blind roll polling in Round Robin mechanism.The specific path scheduling is shown in Algorithm1.Algorithm 1:Hybrid awareness path collaboration.
Initialization: Path array S=ϕ; getSD() is the function of calculating standard deviation factor; getC() is the function of calculating weight coefficient α, β and θ; getPW() is the function of calculating path metric value Qi; Sort ( Ω , Q i ) is to sort the members in Ω based on Qi in ascending. void HPCFunctionPATH=P1,P2,…,Pi,…,Pn,n≥2 for each  Pi ∈ PATH  do ε R T T = getSD(Pi, RTT); ε B W T = getSD(Pi, BWT); ε L o s s = getSD(Pi, LOSS); α = getC(εRTT); β = getC(εBWT); θ = getC(εLOSS); Q i = getPW(α,β,θ); if  Qi≥τ; S.append(Pi); end end S = S o r t ( S , Q i ); for each  Pi∈S  do if  Qit-Qit-1≥ω; S = S o r t ( S ,  Q i ); end end deliver packets based on the S sequence. endThe above HPC function guides the controller to select the optimal paths to balance the traffic load for vehicle users. Afterwards, we will further consider how to determine the number of offloading nodes and select them in an optimal manner.


## 5. Graph-Based Source Collaboration Function

Efficient offloading relies on a set of suitable offloading sources that can quickly distribute data content to subscribing nodes via an ad hoc network. An intuitive idea is to choose the nodes with high probability of connecting other users as the offloading sources.We consider the source collaboration to minimalize the number of offloading nodes to serve all vehicular nodes in a targeted region. Therefore, source selection strategy can utilize the idea of the minimum vertex cover set in graph theory. It means that we choose the minimum vertex cover set as the offloading sources to connect all the nodes of the network. In order to solve the offloading source selection problem by using the minimum vertex cover set, we first need to convert the network topology into a bipartite graph. The process of bipartite graph transformation divides the vertices in a vertex set into two sets of disjoint sets. The division is based on the fact that two vertices with side relations do not exist in one set. Therefore, the network topology can be transformed into a bipartite graph.To formulate this problem, we letG=(V,E) be an undirected graph. The vertex V can be divided into two disjoint subsets (A,B) and each edge (i,j) in the graph is associated with two vertexes i and j belonging to these two different vertex sets (i in A, j in B). Then, the graph G is transferred as a bipartite graph.Theorem 1.
It is necessary and sufficient to judge that the undirected graphG is a bipartite graph, that G has at least two vertices, and that all loops have an even length.
LetG be the bipartite graph X,E,Y. X and Y represent two subsets in G. Both X and Y are not empty, so G has at least two vertices. If C is any one of the loops in G, let C=(v0,v1,v2,…,vi,v0=vi), where vi must appear in either X or Y. For example:(13)v0,v2,v4,…,vl=v0∈X,(14)v1,v3,v5,…,vl-1=v1∈Y.
Let all loops ofG have an even length, and let G be a connected graph. Without loss of generality, if G is not connected, we can discuss the following conditions for each connected branch of G. Let the vertices of G be V and the set of edges be E, so that X, Y will be constructed and X,E,Y=G. Take v0∈V and set X=v∣v=v0 or the path from v to v0 have an even length. Since Y=V-X, X is obviously not empty. Now we should prove Y is not empty, and neither end of the two edges is in X or in Y. Since V≥2 and G is a connected graph, v0 must have adjacent vertices; take v1 as an example; then v1∈Y; therefore Y is not empty.
On the other hand, suppose that there are edges(u,v), u∈X,v∈Y. Then, the path from v0 to u has an even length, or u=v0; otherwise, the path from v0 to v has an even length, or v=v0. In either case, there always is an odd length closed path from v0 to v0 which contradicts with the supposition. Therefore, it is impossible to have edges (u,v) to make both u and v be in X.Based on the above analysis, once we get the knowledge of a certain network topology, we can consider converting the network topology into a bipartite graph.If there are multiple offloading sources to assist the transmission of data content, the vertex cover problem is to find a vertex cover of minimum size in a given undirected graph. This problem is an NP-complete decision problem. It may be very difficult to find an optimal vertex cover in a graphG. Therefore, we can use a heuristic algorithm to find a near-optimal vertex cover, which is the set of collaborative sources. This process is conducted in a software-defined controller.Figure4 introduces the flow chart of source selection, which mainly includes four steps in a controller:Figure 4
Flowchart of source selection.(1) At the starting timet=0, the controller determines the connectivity of each network node according to the collected network node information and divides the entire network into multiple subsets.(2) According to the subdivision result, the controller selects the initial source randomly in each subset. The initial source nodes are characterized by the fact that each node in the subset can communicate with the source.(3) There may be many different initial source nodes according to the former steps. In this case, an optimal offloading source needs to be selected in each subset according to the restricted condition. The optimal offloading source should guarantee the delivery of data froms to v in a short time.(4) Repeat step (3) until the selected offloading source nodes keep the same as the last iteration, and exit the program. In this case, the total offloading source number should be a fixed valueK.


## 6. Simulation Results

We conduct a group of simulations to verify the feasibility and efficiency of SDCO under the NS-3 open source network simulator. In our experiments, we used the Routes Mobility Model to simulate the vehicular networks. The Routes Mobility Model can generate realistic mobility traces by querying the Google maps directions API. The information, obtained from the Google maps services, allows the simulator to generate realistic mobility traces based on real-world locations and road networks.We assess the performance of the proposed SDCO solution by comparing with the state-of-the-art solutions, the typical (TYP) offloading mechanism, and the RSRP/RSRQ offloading mechanism [28]. The offloading sources selected are all user nodes, which are endpoint nodes in this experiment. We compare the offloading performance of the three solutions in terms of the offloading source number and the offloading efficiency. The experimental results are shown in Figures 5, 6, and 7.Figure 5
Number of offloading sources analysis.Figure 6
Offloading efficiency analysis (10–100).Figure 7
Offloading efficiency analysis (100–600).As shown in Figure5, the number of offloading sources is obviously reduced compared with the TYP mechanism. The number of offloading sources for SDCO is always the lowest, and TYP is always the highest. The RSRP/RSRQ mechanism has a moderate performance and it is a bit better than the one of TYP. In this figure, when the number of vehicle nodes is less than or equal to 10, the offloading sources of TYP and SDCO are almost the same. When the number of vehicle nodes increases more than 10, the number of offloading sources in SDCO becomes significantly different from the other two mechanisms. That is because SDCO adopts the GSC method to guarantee the delivery quality with the least offloading sources.Figures6 and 7 show the offloading efficiency of the three offloading mechanisms with a different number of vehicle nodes. Offloading efficiency is the ratio of offloaded traffic to the total traffic. In Figure 6, we can see the overall trend that the offloading efficiency rises as the number of vehicle nodes increases in all three offloading mechanisms. When the number of nodes is less than 100, the difference between TYP and RSRP/RSRQ is not obvious, but SDCO is much better than both of them. When the number of nodes is more than 100, the advantages of SDCO become more prominent. Compared with the RSRP/RSRQ mechanism, SDCO achieves an average improvement by 18% on the offloading efficiency. The reason is that the TYP mechanism transfers more vehicle node requests to the relay nodes (wireless access points) than the RSRP/RSRQ mechanism. The SDCO mechanism can promote the communications between nodes and the communications between the vehicle nodes and the offloading sources.When the number of nodes adds to 600, the offloading efficiency keeps at 57% in all three mechanisms. Figure7 shows there is a saturation status for the offloading efficiency, where the three offloading mechanisms have little difference. That is because there are too many nodes, which result in a high density for the network. Therefore, any one of the three solutions can work well for offloading, and the collaborative operations play a small effect on the performance. It is noted that when some traffic is offloaded from the base station to other relay nodes, the base station will have more resource to process the high-priority requests to further improve the experience of users.


## 7. Conclusion and Future Work

This paper has proposed a software-defined collaborative offloading solution for heterogeneous vehicular networks, named SDCO. Specifically, SDCO adopts a centralized software-defined controller to globally manage offloading policies to vehicular nodes. In addition, the hybrid awareness path collaboration and the graph-based source collaboration are further introduced to optimize the transmission path and offloading sources selection. Simulation results have been provided to demonstrate that SDCO can achieve better improvement in terms of number of offloading sources and offloading efficiency. In the future works, more efficient offloading control functions should be designed based on the collaboration of vehicular nodes, such as the social-based collaboration.



---

*Source: 3810350-2018-04-24.xml*