# Mobile Data Traffic Offloading through Opportunistic Vehicular Communications

Authors: Liqiang Qiao
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

To cope with an exponentially increasing demand on mobile data traffic in cellular network, proximity-based opportunistic vehicular communications can be exploited as a complementary mean to offload and reduce the load of cellular network. In this paper, we propose a two-phase approach for mobile data traffic offloading, which exploits opportunistic contact and future utility with user mobility. The proposed approach includes one phase of initial source selection and subsequent phase of data forwarding. In phase 1, we build a weighted reachability graph, which is a very useful high-level abstraction for studying vehicular communication over time. Then, we propose an initial source selection algorithm, named VRank, and apply it in the weight reachability graph to identify some influential vehicles to serve as initial sources according to the rank of VRank. In phase 2, we formulate the forwarding schedule problem as a global utility maximization problem, which takes heterogeneous user interest and future utility contribution into consideration. Then, we propose an efficient scheme MGUP to solve the problem by providing a solution that decides which object should be broadcast. The effectiveness of our algorithm is verified through extensive simulation using real vehicular trace.


---

## Body

## 1. Introduction

With the development of wireless communication technologies and the increase in the number of mobile devices such as smartphones, tablets, and cars, cellular communication is facing a critical challenge of explosively increasing traffic demands [1, 2]. According to a recent report from Cisco, mobile data traffic will grow at a compound annual growth rate of 47 percent from 2016 to 2021, reaching 49.0 exabytes per month by 2021 [3]. Although the fourth-generation mobile cellular network is able to provide content downloading with broad coverage and high bandwidth, the immense mobile traffic demand has imposed a heavy burden on current cellular networks. Especially during peak time and in urban central areas, cellular-based communication will face extreme performance hits in terms of low network bandwidth, missed calls, and unreliable coverage [4, 5]. Therefore, it is essential to come up with an efficient and effective method to ease the burden of cellular networks.Recently, an efficient alternative, generally known as mobile data offloading, which delivers mobile data traffic originally planned for transmission over cellular networks to other networks, has attracted much attention in the literature [6–10]. Traffic offloading can be implemented by Wi-Fi [11], femtocells [12], or opportunistic networks [6]. Wi-Fi and femtocells have evolved as mature technologies, but they rely on infrastructures. On the other hand, opportunistic networks allow users without permanent connection to communicate using the low-cost proximity-based connection when they encounter opportunistically. Therefore, opportunistic networks offer a very powerful alternative to relieve part of the mobile traffic from the cellular infrastructure. Vehicular networks [13] are an important class of opportunistic networks because the contacts, or the transmission opportunities, between vehicles happen in a dynamical and unexpected manner. In addition, vehicles are highly mobile and can communicate with each other using the dedicated short-range communication (DSRC) radio, 802.11p, and LTE-V [14]. These features make vehicular networks a suitable candidate for cellular traffic offloading.The offloading process for disseminating content objects to certain interested subscribers (vehicles) can be described as follows: the cellular base station can firstly deliver the content objects to only a small group of users (we use the terms vehicle, user, and subscriber interchangeably), calledseeds or initial sources. After that, the initial sources can propagate the objects to all the subscribers through opportunistic forwarding, and any user that receives the data further forwards the data to others resulting in an information epidemic. As seen, the efficiency of such opportunistic traffic offloading is highly determined by two key factors: (1) initial source selection and (2) opportunistic forwarding strategy. A suitable set of initial sources can quickly distribute content objects over vehicular networks. In addition, different forwarding sequences of a user with multiple objects to transmit can result in different results. Hence, it is essential to address these two key issues in an opportunistic traffic offloading system.In the literature, there have been some existing studies on traffic offloading through opportunistic communication. For the issue of initial source selection, most works choose the initial sources using various centrality metrics [15–17] or according to the features and properties of users’ contact in the historical trace [7, 18]. Although these works are helpful to understand how to select preferable seeds, the main limitation is that they are suitable for static social network where the topology of the network is relatively stable. In addition, it is hard to accurately infer the uses’ future centrality due to the highly dynamic network topology of the vehicular network. For the issue of data forwarding, most existing works mainly focus on forwarding performance in terms of delivery ratio, delay, and network overhead [19–21]. The users’ interests and forwarding scheduling of multiple content objects are seldomly taken into consideration. However, how to schedule the objects to maximally satisfy users’ interest in the limited contact duration should also be addressed.Based on these insights, in this paper, we propose a two-phase approach for mobile data traffic offloading. Especially, phase 1 selects the initial sources based on a weighted reachability graph, which characterizes vehicles’ transmission opportunities via instantaneous communication and opportunistic communication. We apply the proposed algorithm VRank to identify influential users as the initial sources, which lead to quick and wide spreading of content objects. After that, it follows with phase 2 for data forwarding to accommodate heterogeneous users’ preferences to distribute the appropriate objects in short periods of time. As such, objects can be more effectively scheduled to satisfy users’ interests and gained the maximal utility.The major contributions of this paper are as follows:(1)
For the issue of initial source selection, we propose an algorithm, named VRank, which is expected to exploit opportunistic communication with user mobility, and apply it on weighted reachability graph to select some influential users to serve as the initial sources(2)
For the data forwarding, we formulate the problem as global utility maximization, which takes heterogenous users’ interests and future utility into consideration. An optimal solution MGUP is proposed to solve the problem(3)
We conduct extensive simulations with real vehicular trace to evaluate the performance of our proposed approach. The simulation results show that the two-phase approach can effectively improve offloading rate and global utility to satisfy users’ interestsThe rest of the paper is organized as follows: Section2 reviews related work regarding the mobile data traffic offloading. The system scenario and network model are introduced in Section 3. The initial source selection algorithm is given in Section 4. In Section 5, we formulate the forwarding scheduling as the global utility maximization problem and solve it. The effectiveness of our approach is verified using real vehicular trace in Section 6. The last section is for a brief summary.


## 2. Related Work

With the growing popularity of mobile accesses to the cellular, a number of innovative solutions have emerged to offload data traffic and reduce the load of cellular networks. According to [11], the methods roughly fall into three categories: traffic offloading through small cells, traffic offloading through Wi-Fi networks, and traffic offloading through opportunistic networks.


### 2.1. Traffic Offloading through Small Cells

Traffic offloading through small cells is an effective way to reduce traffic load and network energy consumption. Small cells are small cellular base stations typically designed for indoor use, which deliver wireless services to a small coverage area and are most likely to be user-installed. Existing works have shown most of the mobile traffic is generated indoors. The cellular network operators thus have the opportunities to offload heavy data to small cells and provide users with seamless quality of experience. In [22], Wang et al. proposed to use an auction-based algorithm, femto-matching, to achieve both load balancing among base station and fairness among users. The potentials of social and spatial proactive aching in small networks in terms of mobile data traffic were investigated in [23]. The results show that precaching strategic contents at the network edge engenders significant backhaul offloading gains and resource savings.


### 2.2. Traffic Offloading through Wi-Fi Networks

Recent research [11] has shown that Wi-Fi networks have already carried and offloaded a large amount of mobile data traffic. It has been shown that approximately 65% of cellular traffic can be offloaded by merely switching from cellular networks to Wi-Fi when Wi-Fi connectivity is available [12, 24]. Bulut and Szymanski [25] compared different methods of deploying Wi-Fi APs for efficient offloading of mobile data traffic. In order to reduce cellular network congestion and improve the user-perceived network performance, an offloading mobile data offloading scheme by leasing wireless bandwidth and caching space of residential 802.11 (Wi-Fi APs) was proposed in [26]. In addition, Sou and Peng [27] presented an analytical model for multipath Wi-Fi offloading in deriving the aggregate offloading time via an alternative path for the use of multipath offloading.


### 2.3. Traffic Offloading through Opportunistic Networks

Opportunistic communications have been lately considered as an important way for offloading mobile data traffic [6]. Using opportunistic communications to offload cellular traffic for mobile content dissemination applications is a novel and interesting idea and it has drawn great attention of the researchers. The architecture is actual a hybrid SDVN (Software Defined Vehicular Network). In [28], Zhao et al. investigate the routing-related issues in SDVNs and present a comprehensive overview of the state-of-the-art architectures, protocols, challenges, and potential solutions.A number of studies have been developed to explore the opportunistic mobile network for mobile data traffic offloading. In [6, 29], Han et al. were the first to exploit opportunistic communications to facilitate information dissemination and reduce the amount of mobile data traffic. They studied how to select the target set with k users, such that the mobile data traffic over cellular networks is minimized. Greedy, heuristic, and random algorithms are proposed to solve this problem. The simulation results show the heuristic algorithm can offload mobile data traffic by up to 73.66% for a real-world mobility trace. In order to avoid the information is disseminated in the same community, a community-based algorithm is proposed in [7] to diffuse the information to the entire network as soon as possible. They are taken into both the contact probability and social relationship into account to select the initial seeds belonging to different communities. In [30], Liu et al. proposed a multiple source selection method to find the optimal number of initial sources. In addition, a multilayer-based seed selection approach is designed in [31] to maximally satisfy users’ interest. The results show that multilayer-based seed scheme allows to maximize content utility.With the short contact duration and the large content size taken into consideration, Li et al. [32] developed a contact-duration-aware offloading scheme, named Coff, which adopts the network coding to better utilize the short contacts. In [33], they qualitatively analyzed how the D2D communication can benefit from social features, and quantitatively evaluated the huge potential gains attainable in a practical social aware D2D communication system. Sciancalepore [34] et al. developed a theoretical model to analyze the performance of opportunistic dissemination when data can be selectively injected through a cellular network.


## 2.1. Traffic Offloading through Small Cells

Traffic offloading through small cells is an effective way to reduce traffic load and network energy consumption. Small cells are small cellular base stations typically designed for indoor use, which deliver wireless services to a small coverage area and are most likely to be user-installed. Existing works have shown most of the mobile traffic is generated indoors. The cellular network operators thus have the opportunities to offload heavy data to small cells and provide users with seamless quality of experience. In [22], Wang et al. proposed to use an auction-based algorithm, femto-matching, to achieve both load balancing among base station and fairness among users. The potentials of social and spatial proactive aching in small networks in terms of mobile data traffic were investigated in [23]. The results show that precaching strategic contents at the network edge engenders significant backhaul offloading gains and resource savings.


## 2.2. Traffic Offloading through Wi-Fi Networks

Recent research [11] has shown that Wi-Fi networks have already carried and offloaded a large amount of mobile data traffic. It has been shown that approximately 65% of cellular traffic can be offloaded by merely switching from cellular networks to Wi-Fi when Wi-Fi connectivity is available [12, 24]. Bulut and Szymanski [25] compared different methods of deploying Wi-Fi APs for efficient offloading of mobile data traffic. In order to reduce cellular network congestion and improve the user-perceived network performance, an offloading mobile data offloading scheme by leasing wireless bandwidth and caching space of residential 802.11 (Wi-Fi APs) was proposed in [26]. In addition, Sou and Peng [27] presented an analytical model for multipath Wi-Fi offloading in deriving the aggregate offloading time via an alternative path for the use of multipath offloading.


## 2.3. Traffic Offloading through Opportunistic Networks

Opportunistic communications have been lately considered as an important way for offloading mobile data traffic [6]. Using opportunistic communications to offload cellular traffic for mobile content dissemination applications is a novel and interesting idea and it has drawn great attention of the researchers. The architecture is actual a hybrid SDVN (Software Defined Vehicular Network). In [28], Zhao et al. investigate the routing-related issues in SDVNs and present a comprehensive overview of the state-of-the-art architectures, protocols, challenges, and potential solutions.A number of studies have been developed to explore the opportunistic mobile network for mobile data traffic offloading. In [6, 29], Han et al. were the first to exploit opportunistic communications to facilitate information dissemination and reduce the amount of mobile data traffic. They studied how to select the target set with k users, such that the mobile data traffic over cellular networks is minimized. Greedy, heuristic, and random algorithms are proposed to solve this problem. The simulation results show the heuristic algorithm can offload mobile data traffic by up to 73.66% for a real-world mobility trace. In order to avoid the information is disseminated in the same community, a community-based algorithm is proposed in [7] to diffuse the information to the entire network as soon as possible. They are taken into both the contact probability and social relationship into account to select the initial seeds belonging to different communities. In [30], Liu et al. proposed a multiple source selection method to find the optimal number of initial sources. In addition, a multilayer-based seed selection approach is designed in [31] to maximally satisfy users’ interest. The results show that multilayer-based seed scheme allows to maximize content utility.With the short contact duration and the large content size taken into consideration, Li et al. [32] developed a contact-duration-aware offloading scheme, named Coff, which adopts the network coding to better utilize the short contacts. In [33], they qualitatively analyzed how the D2D communication can benefit from social features, and quantitatively evaluated the huge potential gains attainable in a practical social aware D2D communication system. Sciancalepore [34] et al. developed a theoretical model to analyze the performance of opportunistic dissemination when data can be selectively injected through a cellular network.


## 3. System Model

### 3.1. System Scenario

We consider a mobile traffic offloading scenario as illustrated in Figure1. The network system is composed of base stations and mobile vehicles equipped with two different network interfaces: a cellular interface and a short range communication interface. The former is used to communicate with the base stations and the latter is devoted to the opportunistic communication between vehicles. The base stations of the cellular network are connected to the content servers in the Internet through wired links. Content server has some objects to distribute to a set of users before deadline. The information to be delivered may include weather forecasts, multimedia newspapers, and movie trailer generated by content service providers. Due to the delay-tolerant nature of non-real-time applications, service provider may deliver the objects to a small fraction of selected users, which are referred to initial sources. The initial sources will further disseminate the objects to the corresponding vehicles that request them through opportunistic communication, which occurs when two vehicles move into the communication range of each other. In addition, a vehicle may receive multiple objects, but it can only broadcast a single object at a time. As a result, different forwarding schedules, i.e., the forwarding sequence of the forwarder’s objects, could result in different utilities. Each forwarder should carefully consider when to deliver which content objects. Therefore, the problem considered in this paper has two components: (1) initial source selection, how to identify some important vehicles to be the initial sources to assign the objects and (2) opportunistic forwarding strategy, how to schedule the sequence of objects to achieve the maximum utility.Figure 1
System scenario.


### 3.2. Network Model

Due to the highly dynamic network topology of the vehicular network, the real vehicular networks are actual temporal graph where the existence of links may only last for a short period [35]. Therefore, we represent the vehicular network as a temporal graph G=V,E, where V represents all the vehicles and E represents the links between two vehicles, of which the Euclidean distance is smaller than the wireless communication range R. An undirected edge e∈E is a quadruple u,v,t,λ, where u,v∈V, t is the contact time between u and v, λ is the link duration time to go from u to v (also from v to u) starting at time t, and t+λ is the link ending time. We denote the starting time of e by te and the duration time of e by λe. As a pair of nodes may communicate at multiple time instances, the number of temporal edges between u and v can be large.


#### 3.2.1. Time-Ordered Path or Journey

A time-ordered pathP in a temporal graph G is a sequence of vertices P=<v1,v2,⋯,vk,vk+1> where vi,vi+1,ti,λi∈E is the i-th temporal edge on P for 1≤i≤k, and ti+λi≤ti+1 for 1≤i≤k. In the literature [36], the terms “journey” and “time-respecting path” have also been used for time-ordered path. We denote by startP and endP, the starting time t1 and the ending time tk+λk of a time-ordered path P. Time-ordered paths can be thought of as opportunistic communication routes over time from a source to a destination. We also define the temporal distance of P as distP=endP−startP corresponding to the delay of route. Objects or resources can be transmitted through opportunistic communication from node u to node v in vehicular networks only if they are joined by a time-ordered path.


## 3.1. System Scenario

We consider a mobile traffic offloading scenario as illustrated in Figure1. The network system is composed of base stations and mobile vehicles equipped with two different network interfaces: a cellular interface and a short range communication interface. The former is used to communicate with the base stations and the latter is devoted to the opportunistic communication between vehicles. The base stations of the cellular network are connected to the content servers in the Internet through wired links. Content server has some objects to distribute to a set of users before deadline. The information to be delivered may include weather forecasts, multimedia newspapers, and movie trailer generated by content service providers. Due to the delay-tolerant nature of non-real-time applications, service provider may deliver the objects to a small fraction of selected users, which are referred to initial sources. The initial sources will further disseminate the objects to the corresponding vehicles that request them through opportunistic communication, which occurs when two vehicles move into the communication range of each other. In addition, a vehicle may receive multiple objects, but it can only broadcast a single object at a time. As a result, different forwarding schedules, i.e., the forwarding sequence of the forwarder’s objects, could result in different utilities. Each forwarder should carefully consider when to deliver which content objects. Therefore, the problem considered in this paper has two components: (1) initial source selection, how to identify some important vehicles to be the initial sources to assign the objects and (2) opportunistic forwarding strategy, how to schedule the sequence of objects to achieve the maximum utility.Figure 1
System scenario.


## 3.2. Network Model

Due to the highly dynamic network topology of the vehicular network, the real vehicular networks are actual temporal graph where the existence of links may only last for a short period [35]. Therefore, we represent the vehicular network as a temporal graph G=V,E, where V represents all the vehicles and E represents the links between two vehicles, of which the Euclidean distance is smaller than the wireless communication range R. An undirected edge e∈E is a quadruple u,v,t,λ, where u,v∈V, t is the contact time between u and v, λ is the link duration time to go from u to v (also from v to u) starting at time t, and t+λ is the link ending time. We denote the starting time of e by te and the duration time of e by λe. As a pair of nodes may communicate at multiple time instances, the number of temporal edges between u and v can be large.


### 3.2.1. Time-Ordered Path or Journey

A time-ordered pathP in a temporal graph G is a sequence of vertices P=<v1,v2,⋯,vk,vk+1> where vi,vi+1,ti,λi∈E is the i-th temporal edge on P for 1≤i≤k, and ti+λi≤ti+1 for 1≤i≤k. In the literature [36], the terms “journey” and “time-respecting path” have also been used for time-ordered path. We denote by startP and endP, the starting time t1 and the ending time tk+λk of a time-ordered path P. Time-ordered paths can be thought of as opportunistic communication routes over time from a source to a destination. We also define the temporal distance of P as distP=endP−startP corresponding to the delay of route. Objects or resources can be transmitted through opportunistic communication from node u to node v in vehicular networks only if they are joined by a time-ordered path.


## 3.2.1. Time-Ordered Path or Journey

A time-ordered pathP in a temporal graph G is a sequence of vertices P=<v1,v2,⋯,vk,vk+1> where vi,vi+1,ti,λi∈E is the i-th temporal edge on P for 1≤i≤k, and ti+λi≤ti+1 for 1≤i≤k. In the literature [36], the terms “journey” and “time-respecting path” have also been used for time-ordered path. We denote by startP and endP, the starting time t1 and the ending time tk+λk of a time-ordered path P. Time-ordered paths can be thought of as opportunistic communication routes over time from a source to a destination. We also define the temporal distance of P as distP=endP−startP corresponding to the delay of route. Objects or resources can be transmitted through opportunistic communication from node u to node v in vehicular networks only if they are joined by a time-ordered path.


## 4. Phase 1: VRank-Based Initial Source Assignment

In this section, we present how to identify a set of vehicles to be the initial sources to distribute the objects. We propose an algorithm named VRank which can rank the nodes in a directed graph. Reachability graph [37, 38] is a very useful high-level abstraction for studying vehicular communication over time in vehicular networks. Therefore, we firstly introduce the concept of reachability graph and how to construct it. Next, we apply the VRank algorithm in reachability graph to select some influential vehicles to serve as initial sources.


### 4.1. Weighted Reachability Graph

For a given temporal graphG and any time interval t1,tk, we define Ck=Vk,Jk to be the reachability graph of G at time k. The set of nodes Vk is subset of V and represents the set of vehicles that were sampled in the given time interval. The set of arcs Jk represents every available direct link or time-ordered path P in G within tk. In other words, if u,v∈Jk, it means that u is able to communicate with v through instantaneous communication or along the temporal path from u to v. Notice that is not symmetric: the existence of time-ordered path from u to v does not imply there is a path from v to u. The reachability graph of a temporal graph can be obtained by computing the time-ordered paths between any two pairs of nodes, and then adding a link between two nodes u and v of the reachability graph if the temporal distance from u to v is finite or a direct link exists between u and v. Figure 2 illustrates an example of reachability graph which consists of six nodes and twelve directed links. The weight wuv of each edge is the number of direct links and time-ordered paths within a duration between the two nodes.Figure 2
An illustration of the reachability graph and the VRank algorithm.


### 4.2. VRank Algorithm

Identifying a set of influential nodes is a challenging problem in complex networks. A number of centrality metrics have been proposed to address this problem, such as degree centrality, closeness centrality, and between centrality [39, 40]. PageRank [41] is the most famous web page ranking employed by Google to rank web pages. It measures the relative importance of a page within a web graph. LeaderRank [42] has been shown as an effective and efficient method to identify influential spreaders in directed networks, which is a simple variant of PageRank. Motivated by the success of this algorithm, we propose an algorithm named VRank. Instead of considering degree of node only, we also take encounter times between any two vehicles into account to depict the weight. The main idea is that nodes with a higher VRank value will generally be more important vehicles to disseminate the objects, given that popular nodes are more likely to meet other nodes in the networks.Given a weighted directed network consisting ofN nodes and E edges, a ground node is then added by establishing bidirectional edges between it and all the other nodes. Then, the network becomes strongly connected and consists of N+1 nodes and E+2N edges. Initially, each node in the network, except for the ground node, is assigned to one unit of resource, while the ground node is assigned with no resource. And then each node distributes its resource to neighbors along the outgoing edges. Next is to update resource distribution as summing up the resource each node derives from its incoming edges. This process of distribution and updating of resources continues until steady state is attained. The whole process can be described mathematically as follows.Assumingvit is the score of node i at time step t, the initial state can be represented as follows:
(1)vg0=0,wheregisgroundnode,vi0=1,others.And each node can update its score according to the following equation:(2)vit+1=∑j=1N+1wjisumwjvjt,where wji is the weight of the edge j,i and sumwj is the sum of weight of node j. Consider vehicular network where a user i is called a fan of user j if there is a directed link from i to j, namely, i could receive information from j and thus j will receive scores from i (if node’s fans are of high influence, this node will be highly influential as well). Obviously, the number of fans is an important local indicator for a user’s influence in spreading.When the scorevit of all nodes converges to a unique steady state at time tc, the score of the ground node is then evenly distributed to all other nodes, and the final score distribution on node i is as follows:
(3)vi=vitc+vgtcN,wherei∈1,2,⋯,N.To illustrate the ranking process, we provide a simple ranking example in Figure2. After convergence, the final scores of the six nodes are v1=1.5050,v2=1.1835,v3=1.1002,v4=1.0764,v5=1.2014, and v6=0.9335, respectively. Therefore, node 1 is ranked top by the VRank algorithm.


## 4.1. Weighted Reachability Graph

For a given temporal graphG and any time interval t1,tk, we define Ck=Vk,Jk to be the reachability graph of G at time k. The set of nodes Vk is subset of V and represents the set of vehicles that were sampled in the given time interval. The set of arcs Jk represents every available direct link or time-ordered path P in G within tk. In other words, if u,v∈Jk, it means that u is able to communicate with v through instantaneous communication or along the temporal path from u to v. Notice that is not symmetric: the existence of time-ordered path from u to v does not imply there is a path from v to u. The reachability graph of a temporal graph can be obtained by computing the time-ordered paths between any two pairs of nodes, and then adding a link between two nodes u and v of the reachability graph if the temporal distance from u to v is finite or a direct link exists between u and v. Figure 2 illustrates an example of reachability graph which consists of six nodes and twelve directed links. The weight wuv of each edge is the number of direct links and time-ordered paths within a duration between the two nodes.Figure 2
An illustration of the reachability graph and the VRank algorithm.


## 4.2. VRank Algorithm

Identifying a set of influential nodes is a challenging problem in complex networks. A number of centrality metrics have been proposed to address this problem, such as degree centrality, closeness centrality, and between centrality [39, 40]. PageRank [41] is the most famous web page ranking employed by Google to rank web pages. It measures the relative importance of a page within a web graph. LeaderRank [42] has been shown as an effective and efficient method to identify influential spreaders in directed networks, which is a simple variant of PageRank. Motivated by the success of this algorithm, we propose an algorithm named VRank. Instead of considering degree of node only, we also take encounter times between any two vehicles into account to depict the weight. The main idea is that nodes with a higher VRank value will generally be more important vehicles to disseminate the objects, given that popular nodes are more likely to meet other nodes in the networks.Given a weighted directed network consisting ofN nodes and E edges, a ground node is then added by establishing bidirectional edges between it and all the other nodes. Then, the network becomes strongly connected and consists of N+1 nodes and E+2N edges. Initially, each node in the network, except for the ground node, is assigned to one unit of resource, while the ground node is assigned with no resource. And then each node distributes its resource to neighbors along the outgoing edges. Next is to update resource distribution as summing up the resource each node derives from its incoming edges. This process of distribution and updating of resources continues until steady state is attained. The whole process can be described mathematically as follows.Assumingvit is the score of node i at time step t, the initial state can be represented as follows:
(1)vg0=0,wheregisgroundnode,vi0=1,others.And each node can update its score according to the following equation:(2)vit+1=∑j=1N+1wjisumwjvjt,where wji is the weight of the edge j,i and sumwj is the sum of weight of node j. Consider vehicular network where a user i is called a fan of user j if there is a directed link from i to j, namely, i could receive information from j and thus j will receive scores from i (if node’s fans are of high influence, this node will be highly influential as well). Obviously, the number of fans is an important local indicator for a user’s influence in spreading.When the scorevit of all nodes converges to a unique steady state at time tc, the score of the ground node is then evenly distributed to all other nodes, and the final score distribution on node i is as follows:
(3)vi=vitc+vgtcN,wherei∈1,2,⋯,N.To illustrate the ranking process, we provide a simple ranking example in Figure2. After convergence, the final scores of the six nodes are v1=1.5050,v2=1.1835,v3=1.1002,v4=1.0764,v5=1.2014, and v6=0.9335, respectively. Therefore, node 1 is ranked top by the VRank algorithm.


## 5. Phase 2: Opportunistic Forwarding Strategy

After phase 1, initial sources receive the assign objects via cellular communication; they can disseminate those objects to other vehicles through opportunistic communication. How to schedule those objects to maximally satisfy users’ interests is addressed in this section. We first introduce the user interest and utility model. Next, we formulate the forwarding scheduling as a global utility maximization problem and design an effective scheme to solve it.


### 5.1. Interest Model

In a system with multiple content objects, a user will have different interests in different objects. Some objects are popular that are interested by many subscribers, whereas some other objects are not popular data, which may only be interest to a small number of subscribers. Keyword set is a set of keywords selected to depict the object and user interest. LetK=K1,K2,⋯,KM be a keyword set, where each Ki denotes one topic that can be rated. For any object, o∈O is described by a subset of keywords, which is denoted by Kc, and weight vkc, which indicates the importance of keyword kc∈Kc. An object is described by a M×1 vector D=d1,d2,⋯,dM, where dkc=vkc, and all the other elements are 0. We assumed each vkc is normalized, i.e., ∑i=1Kcvkc=1.In order to model the interest of different subscribers to different objects, aM×1 vector Ps=Ps1,Ps2,⋯,PsM is to represent the interest profile of subscriber s, where each Psi denotes the degree of how subscriber s is interested in keyword Ki. In practice, Psi is used to compare the subscriber’s interest in different keywords. Hence, without loss of generality, we define ∑j=1MPsj=1. Finally, the interest probability of subscriber s for object o is computed:
(4)ps,o=PsDT=∑Kc∈KcvkcPsKc,where ·T indicates matrix transpose.


### 5.2. Utility Model

When a subscribers receives an object o regarding a subset of keywords Kc, the partial interest of s can be met. We define us,o to represent the local utility of subscriber s and the value of us,o=ps,o.Once a vehicle obtains an object from base station or any other forwarder, it will become a forwarder. LetOfτ denote the set of objects owned by the forwarder f at instant τ. When the forwarder f meets a group of neighboring vehicles Vfτ in time slot τ, each vehicle is required to explicitly provide its interest in different predefined topics K. The forwarder f can know the local utility of each neighbor vehicle and broadcast any object oj∈Ofτ to all its neighbors. Each vehicle i∈Vfτ who does not own object oj can then obtain the utility ui,oj. The local utility that the forwarder f can produce to its neighbors for the object oj at time τ is computed as follows:
(5)ωf,oj,τl=∑i∈Vfτui,oj.However, solely considering the local utility is not enough due to the lack of consideration of the utility contribution by vehiclei∈Vfτ to their future contacts. Let Ui,oj,τ denote the future utility of vehicle i if it gets the object oj in time slot τ. Thus, the global utility that the forwarder f can produce to its neighbors for the object oj at time τ is computed as follows:
(6)ωf,oj,τg=∑i∈VfτUi,oj,τ.


### 5.3. Problem Formulation

We know that the contacts between forwarderf and its neighbors occur only during a short period, allowing them to exchange a limited volume of data. Therefore, the neighbors of f can only receive part of interested objects. Which objects to forward and how to schedule these objects to maximally satisfy user interests is required to be addressed when the forwarder f has multiple objects to broadcast.Intuitively, the forwarderf can schedule those objects to maximize the global utility for the current slot. However, such a greedy approach can not guarantee the long-term highest level of user satisfaction. Consider such a scenario shown in Figure 3, where the forwarder f owns three objects (o1,o2,o3) and has contact with u1 and u2 at time slot τ. The contact durations with u1 and u2 are four and two time slots, respectively. Each vehicle uii∈1,2 has the future utility Uui,oj,τ for object ojj∈1,2,3 as shown in Figure 3. We use Uui,oj,τ to approximate Uui,oj,τ+1 in this example. According to the greedy strategy, the forwarder f distributes those objects in the following order: [o3,o1,o2], since the utility that can be obtained is 0.13,0.12,0.11, respectively. The link between f and u2 is maintained for two time slots, such that u2 can only receive two objects. The cumulative utility obtained after the broadcast of all the objects of the forwarder f is 0.270.13+0.12+0,02. However, if we consider consecutive time slots, the object o2 is more important to u2 than object o1. The forwarder f can send the objects in the following order o3,o2,o1 and the utility obtained is 0.310.13+0.11+0.07. Therefore, the greedy algorithm that results in immediate optimum cannot guarantee the long-term optimum.Figure 3
Example of utility contribution.From the above example, we observe that the forwarderf should consider more consecutive time slots if it can exactly know the contact duration dfi for all neighbors i∈Vfτ. We define a set of available time slots T=τ,τ+1,⋯,τmax, where τmax=maxi∈Vfττ+dfi. The transmission scheduling decision for each time slot can be represented by a vector:
(7)At=a1t,a2t,⋯,aOfτt,t∈T,where
(8)ait=1objectoiisbroadcastintimeslott,0others.There is a constraint∑i=1∣Ofτ∣ait≤1 for the vector At, which means that, at most, one object will be scheduled to broadcast for slot t.With multiple slots to be considered, the problem is formulated as finding the best time slot allocationA=Aτ,Aτ+1,⋯,Aτmax for a total time period τmax to schedule the transmission, such that the global utility is maximized. Therefore, we formulate the global utility maximization problem (GUMP) as follows:
(9)U=maxA∑t=ττmax∑i=1∣Ofτ∣Ui,oj,t.Subject to(10)∑l=1Ofτalt≤1,t∈T,(11)ajt=0,1,j∈Ofτ,t∈T,i∈Vfτ.The objective is hence to find the optimal forwarding schedule for alloj∈Oft and t∈T, such that forwarder f can contribute the maximal total global utility.


### 5.4. Prediction of the Future Utility

We assume that the random variableNijt denotes the cumulative number of contacts between nodes i and j at time t and any two contacts between them are independent from each other. Thus, Nijt can be modeled as a homogeneous Poisson process with rate λij. Assuming the length of a time slot is Δt, the number of contacts Nijt+Δt−Nijt between nodes i and j within time Δt follows the Poisson distribution, which can be expressed as follows:
(12)PNijt+Δt−Nijt=k=λijΔtkexp−λijΔtk!.Then, the contact probability between nodesi and j within time Δt can be expressed as follows:
(13)qij=1−exp−λijΔt.The value ofUi,o,t can be determined by two factors: (1) the probability that forwarder i can meet other contacts who have not owned object o after time slot t and (2) the utility of i′s contact on object o. Now, we first derive the probability that a contact j∈V has not received object o in time slot t′ from any contacts k∈V, denoted by Φj,ot′. In [18], they considered that user j will not able to download object o from user k before time slot t if and only if the two following events occur: (1) j and k never met before time slot t, i.e., Njkt−1=0 or (2) the last contact between j and k was in time slot z<t, but k did not have object o in time slot z. Therefore, the probability ϕj,k,ot that j cannot download object o from k before time slot t can be computed by the following:
(14)ϕj,k,ot=1−qjkt−1+∑z=1t−1qjk1−qjkt−1−zΦk,oz.Then, the probabilityΦj,oz that user j has not downloaded object o until time slot t equals the probability that j cannot download object o from any user k before t.
(15)Φj,ot=∏j≠kϕj,k,ot.Since only the data sources have objecto in the initial time slot 1, we have Φj,o1=0 if j is a data source of object o and Φj,o1=1 otherwise. Given the initial value of Φj,o1, we can compute the value of Φj,oz for each time slot z=2,3,⋯,t−1 iteratively for all users.Thus, the expected utility thati can contribute to contact j between t and Tomax for object o is as follows:
(16)κi,j,ot=pj,o∑z=tTomax−1qij1−qijTomax−1−zΦj,oz,where Tomax is the expiration time of object o. Last, the future utility of user i can be approximated by the following:
(17)Ui,o,t≈∑j∈Viκi,j,ot.


### 5.5. Optimal Solution

The global utility maximization problem can be solved by searching all the states. Obviously, the computational complexity is very high. Here, we design a simple yet effective algorithm to achieve the maximum global utility.The total number of time slots that each vehiclei∈Vfτ will stay with the forwarder f can be calculated as follows:
(18)nsi=dfiΔt.As described earlier, more consecutive time slots should be considered in the optimal problem. The maximum possible global utility achieved for each objectoj∈Ofτ can be estimated if the object can always be transmitted. The average global utility potential of object oj in the next successive n slots Un is defined as the total amount of global utility obtained during the next successive n slots over n, which is computed as follows:
(19)Un=∑i=1nωf,oj,τ+ign.The computation of average global utility potential can be considered to find the object that can bring the highest utility in the following couple of slots. Therefore, the maximum average global utility potentialmaxU1,U2,⋯,Un should be computed for the scheduling, which is shown in Algorithm 1. With the average global utility potential computed, all the objects will be sorted according the global utility potential. The object with the highest global utility potential will be selected to transmit during the current time slot.Algorithm 1: Max global utility potential (MGUP) algorithm.
Input: the contact time τ and the contact duration dfi of each vehicle i∈Vfτ
Output: the maximum global utility potential of object oj
1: Compute the total number of time slots that the vehiclei∈Vfτ will stay with forwarder f: nsi←dfi/Δt
2: Vehiclei∈Vfτ reports its future utility Ui,oj,t in each time slot
3: The maximum available time slotτmax=τ+maxnsi
4:fort=τ to τmaxdo
5:ωf,oj,tg=∑i∈VfτUi,oj,t
6:end for
7: Initialize themaxutility←−1
8:fori=1 to maxnsido
9:utility←∑i=1maxnsiωf,oj,τ+ig/i
10:ifutility>maxutilitythen
11:maxutility←utility
12:end if
13:end for
14:returnmaxutility


## 5.1. Interest Model

In a system with multiple content objects, a user will have different interests in different objects. Some objects are popular that are interested by many subscribers, whereas some other objects are not popular data, which may only be interest to a small number of subscribers. Keyword set is a set of keywords selected to depict the object and user interest. LetK=K1,K2,⋯,KM be a keyword set, where each Ki denotes one topic that can be rated. For any object, o∈O is described by a subset of keywords, which is denoted by Kc, and weight vkc, which indicates the importance of keyword kc∈Kc. An object is described by a M×1 vector D=d1,d2,⋯,dM, where dkc=vkc, and all the other elements are 0. We assumed each vkc is normalized, i.e., ∑i=1Kcvkc=1.In order to model the interest of different subscribers to different objects, aM×1 vector Ps=Ps1,Ps2,⋯,PsM is to represent the interest profile of subscriber s, where each Psi denotes the degree of how subscriber s is interested in keyword Ki. In practice, Psi is used to compare the subscriber’s interest in different keywords. Hence, without loss of generality, we define ∑j=1MPsj=1. Finally, the interest probability of subscriber s for object o is computed:
(4)ps,o=PsDT=∑Kc∈KcvkcPsKc,where ·T indicates matrix transpose.


## 5.2. Utility Model

When a subscribers receives an object o regarding a subset of keywords Kc, the partial interest of s can be met. We define us,o to represent the local utility of subscriber s and the value of us,o=ps,o.Once a vehicle obtains an object from base station or any other forwarder, it will become a forwarder. LetOfτ denote the set of objects owned by the forwarder f at instant τ. When the forwarder f meets a group of neighboring vehicles Vfτ in time slot τ, each vehicle is required to explicitly provide its interest in different predefined topics K. The forwarder f can know the local utility of each neighbor vehicle and broadcast any object oj∈Ofτ to all its neighbors. Each vehicle i∈Vfτ who does not own object oj can then obtain the utility ui,oj. The local utility that the forwarder f can produce to its neighbors for the object oj at time τ is computed as follows:
(5)ωf,oj,τl=∑i∈Vfτui,oj.However, solely considering the local utility is not enough due to the lack of consideration of the utility contribution by vehiclei∈Vfτ to their future contacts. Let Ui,oj,τ denote the future utility of vehicle i if it gets the object oj in time slot τ. Thus, the global utility that the forwarder f can produce to its neighbors for the object oj at time τ is computed as follows:
(6)ωf,oj,τg=∑i∈VfτUi,oj,τ.


## 5.3. Problem Formulation

We know that the contacts between forwarderf and its neighbors occur only during a short period, allowing them to exchange a limited volume of data. Therefore, the neighbors of f can only receive part of interested objects. Which objects to forward and how to schedule these objects to maximally satisfy user interests is required to be addressed when the forwarder f has multiple objects to broadcast.Intuitively, the forwarderf can schedule those objects to maximize the global utility for the current slot. However, such a greedy approach can not guarantee the long-term highest level of user satisfaction. Consider such a scenario shown in Figure 3, where the forwarder f owns three objects (o1,o2,o3) and has contact with u1 and u2 at time slot τ. The contact durations with u1 and u2 are four and two time slots, respectively. Each vehicle uii∈1,2 has the future utility Uui,oj,τ for object ojj∈1,2,3 as shown in Figure 3. We use Uui,oj,τ to approximate Uui,oj,τ+1 in this example. According to the greedy strategy, the forwarder f distributes those objects in the following order: [o3,o1,o2], since the utility that can be obtained is 0.13,0.12,0.11, respectively. The link between f and u2 is maintained for two time slots, such that u2 can only receive two objects. The cumulative utility obtained after the broadcast of all the objects of the forwarder f is 0.270.13+0.12+0,02. However, if we consider consecutive time slots, the object o2 is more important to u2 than object o1. The forwarder f can send the objects in the following order o3,o2,o1 and the utility obtained is 0.310.13+0.11+0.07. Therefore, the greedy algorithm that results in immediate optimum cannot guarantee the long-term optimum.Figure 3
Example of utility contribution.From the above example, we observe that the forwarderf should consider more consecutive time slots if it can exactly know the contact duration dfi for all neighbors i∈Vfτ. We define a set of available time slots T=τ,τ+1,⋯,τmax, where τmax=maxi∈Vfττ+dfi. The transmission scheduling decision for each time slot can be represented by a vector:
(7)At=a1t,a2t,⋯,aOfτt,t∈T,where
(8)ait=1objectoiisbroadcastintimeslott,0others.There is a constraint∑i=1∣Ofτ∣ait≤1 for the vector At, which means that, at most, one object will be scheduled to broadcast for slot t.With multiple slots to be considered, the problem is formulated as finding the best time slot allocationA=Aτ,Aτ+1,⋯,Aτmax for a total time period τmax to schedule the transmission, such that the global utility is maximized. Therefore, we formulate the global utility maximization problem (GUMP) as follows:
(9)U=maxA∑t=ττmax∑i=1∣Ofτ∣Ui,oj,t.Subject to(10)∑l=1Ofτalt≤1,t∈T,(11)ajt=0,1,j∈Ofτ,t∈T,i∈Vfτ.The objective is hence to find the optimal forwarding schedule for alloj∈Oft and t∈T, such that forwarder f can contribute the maximal total global utility.


## 5.4. Prediction of the Future Utility

We assume that the random variableNijt denotes the cumulative number of contacts between nodes i and j at time t and any two contacts between them are independent from each other. Thus, Nijt can be modeled as a homogeneous Poisson process with rate λij. Assuming the length of a time slot is Δt, the number of contacts Nijt+Δt−Nijt between nodes i and j within time Δt follows the Poisson distribution, which can be expressed as follows:
(12)PNijt+Δt−Nijt=k=λijΔtkexp−λijΔtk!.Then, the contact probability between nodesi and j within time Δt can be expressed as follows:
(13)qij=1−exp−λijΔt.The value ofUi,o,t can be determined by two factors: (1) the probability that forwarder i can meet other contacts who have not owned object o after time slot t and (2) the utility of i′s contact on object o. Now, we first derive the probability that a contact j∈V has not received object o in time slot t′ from any contacts k∈V, denoted by Φj,ot′. In [18], they considered that user j will not able to download object o from user k before time slot t if and only if the two following events occur: (1) j and k never met before time slot t, i.e., Njkt−1=0 or (2) the last contact between j and k was in time slot z<t, but k did not have object o in time slot z. Therefore, the probability ϕj,k,ot that j cannot download object o from k before time slot t can be computed by the following:
(14)ϕj,k,ot=1−qjkt−1+∑z=1t−1qjk1−qjkt−1−zΦk,oz.Then, the probabilityΦj,oz that user j has not downloaded object o until time slot t equals the probability that j cannot download object o from any user k before t.
(15)Φj,ot=∏j≠kϕj,k,ot.Since only the data sources have objecto in the initial time slot 1, we have Φj,o1=0 if j is a data source of object o and Φj,o1=1 otherwise. Given the initial value of Φj,o1, we can compute the value of Φj,oz for each time slot z=2,3,⋯,t−1 iteratively for all users.Thus, the expected utility thati can contribute to contact j between t and Tomax for object o is as follows:
(16)κi,j,ot=pj,o∑z=tTomax−1qij1−qijTomax−1−zΦj,oz,where Tomax is the expiration time of object o. Last, the future utility of user i can be approximated by the following:
(17)Ui,o,t≈∑j∈Viκi,j,ot.


## 5.5. Optimal Solution

The global utility maximization problem can be solved by searching all the states. Obviously, the computational complexity is very high. Here, we design a simple yet effective algorithm to achieve the maximum global utility.The total number of time slots that each vehiclei∈Vfτ will stay with the forwarder f can be calculated as follows:
(18)nsi=dfiΔt.As described earlier, more consecutive time slots should be considered in the optimal problem. The maximum possible global utility achieved for each objectoj∈Ofτ can be estimated if the object can always be transmitted. The average global utility potential of object oj in the next successive n slots Un is defined as the total amount of global utility obtained during the next successive n slots over n, which is computed as follows:
(19)Un=∑i=1nωf,oj,τ+ign.The computation of average global utility potential can be considered to find the object that can bring the highest utility in the following couple of slots. Therefore, the maximum average global utility potentialmaxU1,U2,⋯,Un should be computed for the scheduling, which is shown in Algorithm 1. With the average global utility potential computed, all the objects will be sorted according the global utility potential. The object with the highest global utility potential will be selected to transmit during the current time slot.Algorithm 1: Max global utility potential (MGUP) algorithm.
Input: the contact time τ and the contact duration dfi of each vehicle i∈Vfτ
Output: the maximum global utility potential of object oj
1: Compute the total number of time slots that the vehiclei∈Vfτ will stay with forwarder f: nsi←dfi/Δt
2: Vehiclei∈Vfτ reports its future utility Ui,oj,t in each time slot
3: The maximum available time slotτmax=τ+maxnsi
4:fort=τ to τmaxdo
5:ωf,oj,tg=∑i∈VfτUi,oj,t
6:end for
7: Initialize themaxutility←−1
8:fori=1 to maxnsido
9:utility←∑i=1maxnsiωf,oj,τ+ig/i
10:ifutility>maxutilitythen
11:maxutility←utility
12:end if
13:end for
14:returnmaxutility


## 6. Performance Evaluation

We now evaluate the performance of VRank-based initial source scheme and the forward schedule strategy using the realistic vehicular traces from the city of Beijing, which gathered from 12:00 am to 11:59 pm on Jan. 05, 2009, in the local time [43]. The number of subject taxis is 2927 and we assume all vehicles are subscribers.The experiments could be divided into two parts: (1) performance comparison with other seed selection methods and (2) global utility gain of the proposed forward strategy.


### 6.1. Performance Comparison with Other Seed Selection Methods

In this section, the proposed VRank initial source selection algorithm and some other alternative methods were implemented in the experiments. The alternative methods include LeaderRank [42], PageRank [41], and POST [16]. In LeaderRank strategy, the initial sources are selected based on the ranking of the algorithm, where the probability that a random walker at a vehicle goes to other in the next step is mainly determined by the vehicle’s out-degree. PageRank is also used to choose the initial sources with damping factor α=0.9. The POST method is based on inferring the future centrality of vehicle and ranking all vehicles according to their predicted centrality values.(1) Offloading Ratio versus the Number of the Initial Sources. To evaluate the performance of our solution and those alternative methods, we use offloading ratio as the metric, which refers to the ratio of the number of successfully received vehicles to the total number of vehicles in the network. We select an observation interval from 7:30 am to 9:30 am to analyze the performance of different algorithms. The first half of the trace is used as the warm-up period for the vehicles to accumulate the necessary network information and construct the reachability graph.Table1 shows the top 8 vehicles’ IDs ranked by the four approaches. From Table 1, we can see that the initial source sets are different from each other.Table 1
The top 8 vehicles’ ID ranked by different algorithms.
Algorithm
No. 1
No. 2
No. 3
No. 4
No. 5
No. 6
No. 7
No. 8
VRank
5079
11788
28496
18292
8407
18102
11722
11009
PageRank
5447
11009
20415
6187
5079
25351
29143
5678
LeaderRank
28522
8154
11301
18687
20406
5644
28841
19695
POST
17682
31260
6348
28489
6725
19613
28162
17921Figure4 plots the average offloading ratio as a function of the number of the initial sources. It can be seen that the VRank scheme outperforms other algorithms in all conditions. Especially, the offloading rate of VRank can achieve 45%, while that of LeaderRank, PageRank, and POST is around 33% when the number of the initial sources is 20. Similarly, the VRank also has a higher offloading rate than other strategies when the number of the initial sources arises from 40 to 200. We also notice that offloading rate increases as the number of the initial sources increases. In VRank, the offloading rate increases from 43% to 54% as the number of the initial sources increases from 20 to 120. It is obvious that the more initial sources the BS selects to distribute the objects, the more mobile vehicles can obtain the objects opportunistically. However, we observe that offloading rate reveals a trend of a slow increase when the number of the initial sources exceeds a certain value. The first 120 seeds can achieve offloading rate about 53%, but adding another 80 seeds can only bring an extra 1% offloading rate in VRank. The similar phenomenon is also observed in other schemes. This is due to the fact that as the number of seed vehicles increases, the probability of two selected vehicles having similar network positions also increases, which means they are redundant and therefore choosing both of them may not be able to gain as large coverage as possible.Figure 4
Offloading ratio versus the number of the initial sources with Beijing taxi data set.(2) Offloading Ratio versus Time Scale. We future examine the impact of time scale on the performance of VRank. We set the number of the initial sources to 100 and run all methods using the mobility trace and get the average.The performance of average offloading ratio as a function of time scale for the four schemes is shown in Figure5. We can see the similar results that VRank outperforms the rest of other schemes. As the time scale increases, VRank always achieves the best performance. Particularly, the offloading ratio of VRank is up to 34.28% comparing with LeaderRank and POST are up to 22.20% and 20.95%, respectively. Meanwhile, we notice the performances of LeaderRank and the POST are very close both in Figures 4 and 5. That is because those two schemes both take the degree of vehicle into consideration to select the initial sources.Figure 5
Offloading ratio versus the time scale with Beijing taxi data set.


### 6.2. Global Utility Gain of the Proposed Forward Strategy

(1) User Interest Profile in Different Keywords. The user interest profiles are generated based on a key set K with M=20 and we assume that keyword Kj∈K is the j-th popular keyword in the network.According to the interest model, the user interest profile in each keywordKj is randomly drawn from a normal distribution with Pj as the mean value. We exploit various distributions for generating Pj of different keywords.
(i)
Zipf distribution with exponents:Pj=1/js/∑i=1M1/is(ii)
Exponential distribution:Pj=exp−j/∑i=1Mexp−i(iii)
Uniform distribution:Pj=1/MP
j with different distributions are shown in Figure 6.Figure 6
User interest profile in different keywords.(2) Average User Interest Probability in Different Objects. We assume there are 15 objects to be disseminated in our system. Each object oj is described by 5 keywords with equal weights. To ensure that different objects have different popularity, the keyword indices of object oj are j,⋯,j+4. Thus, we can computerize the interest probability of each user for object oj according to Equation (4). Figure 7 shows the average user interest probability in different objects. It is easy to be seen that when Pj is generated exponentially or Zipf with exponent s=2, most of the user interests concentrate on popular objects. For Zipf with exponent s=1, such concentration on popular objects decreases. Therefore, Figure 7 actually represents different object interest patterns of mobile users in our system.Figure 7
Average interest probability in different objects.(3) Global Utility Gain versus the Time Scale. We evaluate the global utility gain of proposed algorithm MGUP with greedy, local utility maximum, and random schemes. We let all the schemes select a fixed number (20 in our experiment) of initial sources with VRank. The user interest probabilities are generated by following the Zipf distribution with exponent s=2. In Figure 8, the global utility gain as a function of time scale is shown. We can see that global utility of all the schemes increases with the time scale increases. Meanwhile, we notice that MGUP can produce 13.65 and 23.48 percent higher global utility than greedy and local utility maximum, respectively, until 45minutes later. The improvements are mainly because each forwarder in MGUP considers the future utility contribution of its members and more consecutive time slots in the scheduling process. Especially, the future utility of neighbor i in MGUP not only considers different user interests in different objects but also predicts how many users can gain utility by obtaining object oj from neighbori. Therefore, the forwarder f can select the object that benefits all users in the system. The figure also shows both MGUP and greedy have higher global utility than local utility maximum and random. This further indicates the future utility has a great impact on the performance.Figure 8
Global utility gain versus the time scale with Beijing taxi data set under15 objects.(4) Global Utility Gain versus the Different Numbers of Objects. We future evaluate the impact of the number of objects on the performance of comparison schemes. We vary the number from 5 to 60. Figure 9 plots the global utility gain under the different numbers of objects. It is obvious that global utility increases as the number of objects increases in all schemes. This is because more objects can meet users’ different interests in different objects and produce a higher global utility.Figure 9
Global utility gain versus the number of objects.


## 6.1. Performance Comparison with Other Seed Selection Methods

In this section, the proposed VRank initial source selection algorithm and some other alternative methods were implemented in the experiments. The alternative methods include LeaderRank [42], PageRank [41], and POST [16]. In LeaderRank strategy, the initial sources are selected based on the ranking of the algorithm, where the probability that a random walker at a vehicle goes to other in the next step is mainly determined by the vehicle’s out-degree. PageRank is also used to choose the initial sources with damping factor α=0.9. The POST method is based on inferring the future centrality of vehicle and ranking all vehicles according to their predicted centrality values.(1) Offloading Ratio versus the Number of the Initial Sources. To evaluate the performance of our solution and those alternative methods, we use offloading ratio as the metric, which refers to the ratio of the number of successfully received vehicles to the total number of vehicles in the network. We select an observation interval from 7:30 am to 9:30 am to analyze the performance of different algorithms. The first half of the trace is used as the warm-up period for the vehicles to accumulate the necessary network information and construct the reachability graph.Table1 shows the top 8 vehicles’ IDs ranked by the four approaches. From Table 1, we can see that the initial source sets are different from each other.Table 1
The top 8 vehicles’ ID ranked by different algorithms.
Algorithm
No. 1
No. 2
No. 3
No. 4
No. 5
No. 6
No. 7
No. 8
VRank
5079
11788
28496
18292
8407
18102
11722
11009
PageRank
5447
11009
20415
6187
5079
25351
29143
5678
LeaderRank
28522
8154
11301
18687
20406
5644
28841
19695
POST
17682
31260
6348
28489
6725
19613
28162
17921Figure4 plots the average offloading ratio as a function of the number of the initial sources. It can be seen that the VRank scheme outperforms other algorithms in all conditions. Especially, the offloading rate of VRank can achieve 45%, while that of LeaderRank, PageRank, and POST is around 33% when the number of the initial sources is 20. Similarly, the VRank also has a higher offloading rate than other strategies when the number of the initial sources arises from 40 to 200. We also notice that offloading rate increases as the number of the initial sources increases. In VRank, the offloading rate increases from 43% to 54% as the number of the initial sources increases from 20 to 120. It is obvious that the more initial sources the BS selects to distribute the objects, the more mobile vehicles can obtain the objects opportunistically. However, we observe that offloading rate reveals a trend of a slow increase when the number of the initial sources exceeds a certain value. The first 120 seeds can achieve offloading rate about 53%, but adding another 80 seeds can only bring an extra 1% offloading rate in VRank. The similar phenomenon is also observed in other schemes. This is due to the fact that as the number of seed vehicles increases, the probability of two selected vehicles having similar network positions also increases, which means they are redundant and therefore choosing both of them may not be able to gain as large coverage as possible.Figure 4
Offloading ratio versus the number of the initial sources with Beijing taxi data set.(2) Offloading Ratio versus Time Scale. We future examine the impact of time scale on the performance of VRank. We set the number of the initial sources to 100 and run all methods using the mobility trace and get the average.The performance of average offloading ratio as a function of time scale for the four schemes is shown in Figure5. We can see the similar results that VRank outperforms the rest of other schemes. As the time scale increases, VRank always achieves the best performance. Particularly, the offloading ratio of VRank is up to 34.28% comparing with LeaderRank and POST are up to 22.20% and 20.95%, respectively. Meanwhile, we notice the performances of LeaderRank and the POST are very close both in Figures 4 and 5. That is because those two schemes both take the degree of vehicle into consideration to select the initial sources.Figure 5
Offloading ratio versus the time scale with Beijing taxi data set.


## 6.2. Global Utility Gain of the Proposed Forward Strategy

(1) User Interest Profile in Different Keywords. The user interest profiles are generated based on a key set K with M=20 and we assume that keyword Kj∈K is the j-th popular keyword in the network.According to the interest model, the user interest profile in each keywordKj is randomly drawn from a normal distribution with Pj as the mean value. We exploit various distributions for generating Pj of different keywords.
(i)
Zipf distribution with exponents:Pj=1/js/∑i=1M1/is(ii)
Exponential distribution:Pj=exp−j/∑i=1Mexp−i(iii)
Uniform distribution:Pj=1/MP
j with different distributions are shown in Figure 6.Figure 6
User interest profile in different keywords.(2) Average User Interest Probability in Different Objects. We assume there are 15 objects to be disseminated in our system. Each object oj is described by 5 keywords with equal weights. To ensure that different objects have different popularity, the keyword indices of object oj are j,⋯,j+4. Thus, we can computerize the interest probability of each user for object oj according to Equation (4). Figure 7 shows the average user interest probability in different objects. It is easy to be seen that when Pj is generated exponentially or Zipf with exponent s=2, most of the user interests concentrate on popular objects. For Zipf with exponent s=1, such concentration on popular objects decreases. Therefore, Figure 7 actually represents different object interest patterns of mobile users in our system.Figure 7
Average interest probability in different objects.(3) Global Utility Gain versus the Time Scale. We evaluate the global utility gain of proposed algorithm MGUP with greedy, local utility maximum, and random schemes. We let all the schemes select a fixed number (20 in our experiment) of initial sources with VRank. The user interest probabilities are generated by following the Zipf distribution with exponent s=2. In Figure 8, the global utility gain as a function of time scale is shown. We can see that global utility of all the schemes increases with the time scale increases. Meanwhile, we notice that MGUP can produce 13.65 and 23.48 percent higher global utility than greedy and local utility maximum, respectively, until 45minutes later. The improvements are mainly because each forwarder in MGUP considers the future utility contribution of its members and more consecutive time slots in the scheduling process. Especially, the future utility of neighbor i in MGUP not only considers different user interests in different objects but also predicts how many users can gain utility by obtaining object oj from neighbori. Therefore, the forwarder f can select the object that benefits all users in the system. The figure also shows both MGUP and greedy have higher global utility than local utility maximum and random. This further indicates the future utility has a great impact on the performance.Figure 8
Global utility gain versus the time scale with Beijing taxi data set under15 objects.(4) Global Utility Gain versus the Different Numbers of Objects. We future evaluate the impact of the number of objects on the performance of comparison schemes. We vary the number from 5 to 60. Figure 9 plots the global utility gain under the different numbers of objects. It is obvious that global utility increases as the number of objects increases in all schemes. This is because more objects can meet users’ different interests in different objects and produce a higher global utility.Figure 9
Global utility gain versus the number of objects.


## 7. Conclusion

As the increasing popularity of mobile devices and user demands, the amount of mobile data traffic in cellular networks grows explosively. Users will face extreme performance hits in terms of low or even no network bandwidth, missed calls, and unreliable coverage. It is an urgent agenda for cellular provider to offer quick and promising solutions. Therefore, proximity-based opportunistic communication as a mean to offload and reduce the load of cellular network attracts the attention of service providers. In this paper, we study how to exploit opportunistic vehicular communications to offload mobile data traffic. We propose a two-phase approach, which includes one phase of initial source selection and subsequent phase of data forwarding. For the issue of initial source selection, we propose an algorithm named VRank to identify some influential vehicles to server as initial sources, which lead to quick and wide spreading of content objects. For the issue of data forwarding, we formulate the problem as the global utility maximization, which takes into heterogenous users’ interests and future utility consideration. An optimal solution MGUP is proposed to solve the problem. The effectiveness of our approach is verified through extensive simulation using real vehicular trace.



---

*Source: 3093581-2020-12-23.xml*