# Message Relaying and Collaboration Motivating for Mobile Crowdsensing Service: An Edge-Assisted Approach

Authors: Shu Yang; Jinglin Li; Quan Yuan; Zhihan Liu; Fangchun Yang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Group sensing is a kind of crowdsensing service where HD map producers motivate private cars in a local region to collect data from real world. Group sensing needs vehicles to communicate physically and drivers to collaborate strategically in a mobile or edge-assisted environment. First, we consider collaboration module that motivates drivers to be participants; centralized and distributed motivating methods are discussed. Secondly, we consider communication module; two VANET-based methods are proposed to achieve message relaying in edge infrastructure. To accomplish participants’ selection, three combinations of two modules are proposed and simulated based on a flexible framework. The results show that centralized selection could motivate collaboration at a low price but brings heavy communication overhead. Clustered selection requires more incentives and less communication overhead than centralized selection. Distributed selection is usually the first class choice because of its fine performances on both communicating and motivating.


---

## Body

## 1. Introduction

The rise of big data fuels the research of machine learning and data mining algorithms. Besides algorithms, the method of collecting data is also of great importance [1]. Being intellectualized and networked, smart vehicles are able to sense and communicate in urban area as edge infrastructures [2–4]. By means of crowdsensing, their intrinsic mobility can be leveraged to dynamically collect urban data in different time and areas [5].A promising service of crowdsensing is collecting environmental data for building HD (High Definition) map [6]. The HD map producers, such as Here, TomTom, and Baidu, need lidar/camera/IMU data to build a live map for autonomous driving [7, 8]. The huge volume of information as well as fast updating requirement to build a “live” map challenges map producers because their own devices undoubtedly could not meet these requirements. Some researchers therefore proposed crowdsensing, in which private cars are incentivized to accomplish a sensing task and upload data to map producer. The incentives could be either real or virtual money.This paper focuses on how to call up a group of smart vehicles to complete a sensing task in an edge environment, where vehicles and RSUs work together to provide support for reliable mobile services [9]. Map producer launches a task by putting it on a “seed vehicle” and will propagate task information to others in the neighborhood. Then, nearby vehicles communicate with each other by VANET (Vehicular Ad hoc NETworks), forming a group and sensing one segment of road together. We do not concentrate on specific data collecting method (e.g., how to elicit depth from camera data). Instead, we stand in a perspective of crowdsensing mechanism and we are interested in methods that enable vehicles to communicate and collaborate.As Figure1 illustrated, we design a basic system composed of message relaying module and collaboration motivating module to enable vehicles to communicate physically and collaborate strategically.Figure 1
A schematic of group sensing problem. The problem is tackled by two modules.One feature of our system is its assumption where vehicles only communicate by VANET rather than cellular networks. Admittedly, allocating sensing task by cellular networks enables map producers to directly know and control their “sensors” from servers on the cloud. This scheme needs drivers to report their fine-grained trajectories so that map producers could allocate or recommend an appropriate task. However, a majority of drivers are conservative rather than collaborative if it comes to their private trajectories [10]. The cellular network based scheme therefore may not be fully accepted by most drivers. By contrast, our VANET based local participants selection could alleviate this problem by propagating task information from a seed vehicle and allows drivers to choose whether to join the task with no need of reporting fine-grained trajectories.Another feature of our system is its game theory model. Vehicles are actually controlled by drivers whose behaviors are self-interest [11, 12]. The collaboration among drivers is modeled as a threshold-based game. We will see how vehicles’ sensing costs, the numbers of vehicles, and the task incentives influence the collaboration’s equilibrium.Based on the basic system model, we mainly introduce and discuss the two following questions about group sensing:(i)
How does task information propagated via VANET?Message relaying module is designed to consist of two processes, spread process and back process. In spread process, a message that contains basic task information is firstly given out by seed vehicle and subsequently relayed by other vehicles until it arrives at a region border specified by map producers. We call this spread process because it aims to spread task information to all vehicles within the region. Then it comes to back process; the message is modified and relayed back to seed vehicle. During back process, vehicles may add new information to the message.(ii)
How could two modules work together?Collaboration motivating module helps drivers form a sensing group. Collaboration is relying on message relaying module underpinned to achieve information acquiring and propagating. Existing researches usually discuss relaying message and motivating collaboration separately while an integrated framework is discussed in this paper. The aim of module combination is to endow each networked vehicle ability to make appropriate decision. This combination should meet two requirements: first, the vehicle is automatic enough at control or communication level so that one meta-action could be executed fast enough to support high-level collaboration; second, to maintain the high-level collaboration, vehicle should work smoothly with human driver. Upon these requirements, we have actually added human factor to the collaborating process among crowdsensing.This paper tries to answer these questions based upon the following assumptions and simplifications:(i)
We assume that each vehicle is equipped with Dedicated Short Range Communication (DSRC) device so that it could send or receive messages within a certain distance. We also assume that a vehicle could well coordinate with driver by advanced HMI technology, which means that two modules can seamlessly cooperate.(ii)
Each driver is assumed to be rational and self-interest. He makes decision to maximize his profits. For each driver, the cost of participating is assumed to conform normal distribution.(iii)
To concentrate on a perspective of map producers, we slightly oversimplify the physical layer by assuming perfect channel without collision and loss in simulation. This is detailed in Section5.The rest of this paper is organized as follows. The discussion of related work is presented in Section2. Section 3 illustrates a framework of two modules. Section 4 describes how two modules work interactively to achieve local participants’ selection. Section 5 presents simulation results and analysis. The paper ends with discussions in Section 6 and conclusions in Section 7.


## 2. Related Work

Leveraging vehicles or sensor networks for environmental sensing has been a hot topic in the recent years. Zhu [13] proposed PUS (Pervasive Urban Sensing) framework and used probe cars to sense traffic density. The authors designed a compressive sensing algorithm to tackle sparsity of data. Chen [14] considered the distributed estimation problem over relay-assisted wireless sensor networks. Kalman filtering and consensus estimation are leveraged to improve the estimation efficiency and accuracy in large monitoring system. Yuan [15] observed that the distribution of probe vehicles is uneven over space and time. He therefore proposed an adaptive and compressive data gathering scheme based on matrix completion theory. The scheme could largely improve sensing efficiency and quality. Likewise, Du [16] employed matrix completion to estimate unsampled urban data. Besides data processing, there are some works focusing on optimal participants’ selection of crowdsensing. Song [17] aims to select the most appropriate participants with different budget constraints. Considering different incentive requirements, associated sensing capabilities, and uncontrollable mobility, a multitask-oriented QoI (Quality of Information) optimization problem is discussed and converted to a nonlinear knapsack problem. Zhang [18, 19] proposed an event-driven QoI-aware participatory sensing framework with energy and budget constraints, where the main method is boundary detection. He [20] devised an efficient local ratio based algorithm and designed a motivating mechanism that decides the fair prices of sensing tasks. In most papers, multitask crowdsensing is modeled as a global optimization problem with need for participants’ fine-grained trajectories. By contrast, our paper tries to call up plenty of participants for a single task in a specified region without reporting participants’ trajectories.The application of VANET has been wildly discussed. Papers in research community simply fall into two categories: safety-oriented and non-safety-oriented. The safety-oriented applications intend to avoid collision by broadcasting beacons. Taha [21] proposed a novel protocol for reliable broadcasting of life safety messages in VANET. In case of any dramatic change of speed or moving direction, the vehicle is regarded abnormal and hence it transmits an emergency warning message over the control channel of DSRC. Kumar [22] proposed CarSpeak, a communication system for autonomous driving modified from VANET. By changing the MAC protocol in a content-centric approach, CarSpeak scales the amount of data with the available bandwidth and improves safety of autonomous driving. The non-safety-oriented applications try to relay traffic or other non-real-time information to improve traffic efficiency or driving entertainment. To support high throughput in vehicular networks, Zhou [23] used a geolocation database assisted approach to jointly utilize DSRC and TVWS spectrum. It not only satisfied the dynamic vehicular access requirements but also has adaptive data piping performance. Yuan [24] used VANET for detecting traffic congestion on urban expressways. The scheme develops a spatiotemporal effectiveness model based on the potential energy theory to control the dissemination area and survival time of the congestion information. Similarly, Luo [25, 26] used a SDN-inspired approach to improve network capacity. Wang [27], Zhou [28], Cheng [29], and Yuan [30] use “hard” or “soft” method to expand the communication capacity of Internet of vehicles, respectively.To improve trustworthiness of VANET information, Chen [31] presented a trust-based message propagation and evaluation framework in VANET, where peers share information regarding road condition or safety and others provide opinions about whether the information can be trusted. Chang [32] proposed a Sybil attack detection mechanism, where footprint of vehicle is employed. Vehicles can generate location-hidden trajectory for location-privacy-preserved identification. PTRS [33] is a robust trust-based relay scheme with an objective to distinguish trust levels of the vehicles.Our work is also related to MAS (Multiagent System). Supported by today’s advancing cloud computing technology, the vehicle could be represented by its virtual agent [34] in Cyber-Physical System. One goal of MAS is to find algorithms to allocate tasks and to design mechanisms to motivate collaboration among rational agents. Based on Stackelberg game, Duan [35] analyzed and compared different incentives mechanisms for a master to motivate the collaboration of smartphone users on both data acquisition and distributed computing applications. More specifically, he proposed a reward-based collaboration mechanism, where the master announces a total reward to be shared among collaborators, and the collaboration is successful if there are enough users wanting to collaborate. The mechanism is novel and practical in many cases including participants’ selection of group sensing. Walid [36] proposed a game theoretical approach to tackle the problem of distributed formation of the uplink tree structure among the relay stations in a WiMAX network. From a MAS perspective, the authors modeled the problem as a network formation game, where each relay station aims to maximize its utility from cooperation. Using the proposed dynamics, the relay stations can self-organize into the tree structure. Talal [37] proposed an algorithm enabling multiagent cooperative calculation. Each agent is assigned some part of the calculation such that the agents’ shares are exhaustive and disjoint. The algorithm is decentralized and requires no communication between the agents. Jiang [38] considered task allocation and load balance in social networked MAS, where agents always need to negotiate with other agents about their resources. In the presented task allocation model, while a task comes to the system, it is first assigned to a principal agent that has high contextual enrichment factor for the required resources. Then the principal agent will negotiate with its contextual agents to execute the assigned task. The authors also considered load balancing to avoid overconvergence of tasks at certain agents that are rich in contextual resources. Motivated by above papers, this paper has discussed smart vehicle collaboration from a MAS perspective.


## 3. Framework

Group sensing aims to collect data in a specified region, thus focusing on local participants’ selection. The participants’ selection of group sensing involves two modules. Collaboration motivating module aims to motivate plenty of collaborators to form a sensing group. The math of motivating mechanism will be illustrated. Another module, namely, message relaying module, provides VANET-based media to execute motivating mechanism.


### 3.1. Collaboration Motivating Module

HD map data need to be batch-processed to reduce noise and correct error. One single vehicle’s data are less valued than a batch of data from a sensing group. Therefore, a sensing group usually consists of many vehicles that share a similar traverse in both space and time. Map producers prefer to harvest a batch of data by calling up a group of vehicles.Based on above facts, the essence of group sensing is threshold based game [35]. Map producers are only willing to give incentives when a certain number of vehicles (or drivers), denoted as n0, participate in the sensing task. Consider that a set of N vehicles N={1,2,…,N} have been notified of the task and each vehicle knows N and n0. vehiclei(i∈N) has a collaboration cost Ci, if it collaborates (i.e., joins the sensing group). We assume that all collaboration costs conform normal distribution, known as C~N(μ,σ).Since map producers need a sensing group, the sensing task will not be approved unless at leastn0 of N vehicles become participants. Moreover, each driver decides whether to participate by predicting others’ decisions. These facts make a threshold-based game, which consists of two phases. In phase 1, seed vehicle gives out task information (R,n0). R are total incentives given by map producers. In phase 2, after (R,n0) is propagated and known by N vehicles, each driver decides whether to participate. If the number of participants, denoted by n, is bigger than n0, then the task is approved; otherwise the task is abandoned by map producer. If the task is approved, incentives R are distributed equally to participants because each participant works in the similar road segment and time. As a result, participating vehiclei(i∈N) undertakes cost Ci and gets incentives of R/n, with its overall profits being(1)Rn-CiPosn≥n0wherePos{X} is the indicator function (equals 1 when event X is true and equals 0 when event X is false). One could make negative profits even though he joins the collaboration, if R/n is smaller than Ci. If collaboration is not approved, profit is 0.It is actually the driver who decides whether the vehicle collaborates or not. Driver is self-interest and makes own decision with limited information. All drivers’ rational behaviors make a threshold-based game. The result of this game is subtle; for example, when n (n≫n0) drivers decide to collaborate, they may even gain a negative profit because R/n is so small that it even could not meet sensing cost. On the other hand, if only n (n≪n0) drivers collaborate, it is hard to persuade map producers to approve such task because the map producers could not harvest enough data. Therefore, how to motivate an appropriate number of drivers to collaborate is a critical problem in group sensing.


### 3.2. Message Relaying Module

Message relaying module executes two physical processes: spread process and back process. Map producers have owned a few seed vehicles. Reporting their fine-grained trajectories, seed vehicles are well connected with servers and controlled by map producer. Server monitors seed vehicles’ states and launch a task package to one specific seed vehicle. As Table1 shows, the package contains four kinds of information: (1) The first kind is sensing segment. Participants only need to collect data within a specified region. The region is the sensing segment of task. (2) The second kind is preparing segment. Before entering sensing segment, task information is propagated and some participants are generated from normal vehicles. Such process, including message relaying and collaboration motivating, takes place on preparing segment. As shown in Figure 2, preparing segment should be upstream of sensing segment because vehicles would have already traversed a length of road segment when preparing work is done. Since our topic is communicating and collaborating mechanism rather than sensing techniques, this paper concentrates on preparing segment. (3) The third kind is incentive. Map producer is willing to pay incentives R if he approves the task. (4) The fourth kind is threshold of participants. The task is successfully approved only when number of participants n meets the threshold n0.Table 1
Content of task/collaboration message.
Task message Collaboration message  Current relaying vehicle’s location(x,y)  Seed vehicle’s location(x0,y0)  Potential participants listL  RewardR Participants listL′  Threshold of participants’number n0 /  Sensing segment:a rectangle by (x1s,y1s), (x2s,y2s) /  Preparing segment:a rectangle by (x1p,y1p), (x2p,y2p) /Figure 2
Illustration of spread process and back process.Figure2 also illustrates spread process and back process. Spread process starts with a TM (task message) broadcast by seed vehicle. A TM is relayed one-by-one until it reaches the border of preparing segment; thus all vehicles in preparing segment are notified of the task. The border guard, a vehicle located at the border, modifies TM to CM (collaboration message). He also starts back process by reversing relaying direction and sending CM back to seed vehicle. During back process, the vehicle that receives CM decides whether to join the group sensing and adds its decisions to CM. Seed vehicle receives the final CM and knows how many participants it has motivated. The server then could decide if the task is approved.Note that, in our threshold-based game, all drivers make decisions by predicting others’ decisions. To give participants listP to seed vehicle, decisions are recorded in P, which is relayed by vehicles. This means that some vehicles could “peep” decisions of former vehicles, which could lead to more complex models (e.g., social learning [39]) and fails our threshold-based game model. To prevent this cheating, seed and normal vehicles can use public-key cryptography [40] to tackle this problem. Normal vehicles encrypt their decisions with public key, while only seed vehicle can decipher the decisions with private key.


### 3.3. Combining Modules with Flexibility

Participants’ selection needs two modules, namely, message relaying module and collaboration motivating module, to work together. The former module is in charge of propagating information among vehicles, and the latter module is responsible for coordinating drivers’ behaviors.In VANET, messages could be propagated by contention-based relaying.That is, only the periodical winner of contention could be relaying node. Another relaying method is built upon cluster structure, which helps vehicles reduce transmission data volume and improve communication efficiency. Supported by message relaying module, group formation still needs a mechanism to motivate and select appropriate participants. The motivating method could be realized in either a centralized or distributed way. Overall, our participants’ selection framework is composed of two modules, and there are two alternative methods for each module, respectively.Decoupling participants’ selection into two modules endows the system flexibility, enabling map producers to choose optimal combination from several alternatives according to service requirements. We will discuss three combinations: centralized selection, distributed selection, and clustered selection. See Figure3 for understanding how the combination of different modules can make three distinct participants’ selection schemes.Figure 3
Three participants’ selection schemes. Each scheme is a combination of two modules. Each module includes two methods.


## 3.1. Collaboration Motivating Module

HD map data need to be batch-processed to reduce noise and correct error. One single vehicle’s data are less valued than a batch of data from a sensing group. Therefore, a sensing group usually consists of many vehicles that share a similar traverse in both space and time. Map producers prefer to harvest a batch of data by calling up a group of vehicles.Based on above facts, the essence of group sensing is threshold based game [35]. Map producers are only willing to give incentives when a certain number of vehicles (or drivers), denoted as n0, participate in the sensing task. Consider that a set of N vehicles N={1,2,…,N} have been notified of the task and each vehicle knows N and n0. vehiclei(i∈N) has a collaboration cost Ci, if it collaborates (i.e., joins the sensing group). We assume that all collaboration costs conform normal distribution, known as C~N(μ,σ).Since map producers need a sensing group, the sensing task will not be approved unless at leastn0 of N vehicles become participants. Moreover, each driver decides whether to participate by predicting others’ decisions. These facts make a threshold-based game, which consists of two phases. In phase 1, seed vehicle gives out task information (R,n0). R are total incentives given by map producers. In phase 2, after (R,n0) is propagated and known by N vehicles, each driver decides whether to participate. If the number of participants, denoted by n, is bigger than n0, then the task is approved; otherwise the task is abandoned by map producer. If the task is approved, incentives R are distributed equally to participants because each participant works in the similar road segment and time. As a result, participating vehiclei(i∈N) undertakes cost Ci and gets incentives of R/n, with its overall profits being(1)Rn-CiPosn≥n0wherePos{X} is the indicator function (equals 1 when event X is true and equals 0 when event X is false). One could make negative profits even though he joins the collaboration, if R/n is smaller than Ci. If collaboration is not approved, profit is 0.It is actually the driver who decides whether the vehicle collaborates or not. Driver is self-interest and makes own decision with limited information. All drivers’ rational behaviors make a threshold-based game. The result of this game is subtle; for example, when n (n≫n0) drivers decide to collaborate, they may even gain a negative profit because R/n is so small that it even could not meet sensing cost. On the other hand, if only n (n≪n0) drivers collaborate, it is hard to persuade map producers to approve such task because the map producers could not harvest enough data. Therefore, how to motivate an appropriate number of drivers to collaborate is a critical problem in group sensing.


## 3.2. Message Relaying Module

Message relaying module executes two physical processes: spread process and back process. Map producers have owned a few seed vehicles. Reporting their fine-grained trajectories, seed vehicles are well connected with servers and controlled by map producer. Server monitors seed vehicles’ states and launch a task package to one specific seed vehicle. As Table1 shows, the package contains four kinds of information: (1) The first kind is sensing segment. Participants only need to collect data within a specified region. The region is the sensing segment of task. (2) The second kind is preparing segment. Before entering sensing segment, task information is propagated and some participants are generated from normal vehicles. Such process, including message relaying and collaboration motivating, takes place on preparing segment. As shown in Figure 2, preparing segment should be upstream of sensing segment because vehicles would have already traversed a length of road segment when preparing work is done. Since our topic is communicating and collaborating mechanism rather than sensing techniques, this paper concentrates on preparing segment. (3) The third kind is incentive. Map producer is willing to pay incentives R if he approves the task. (4) The fourth kind is threshold of participants. The task is successfully approved only when number of participants n meets the threshold n0.Table 1
Content of task/collaboration message.
Task message Collaboration message  Current relaying vehicle’s location(x,y)  Seed vehicle’s location(x0,y0)  Potential participants listL  RewardR Participants listL′  Threshold of participants’number n0 /  Sensing segment:a rectangle by (x1s,y1s), (x2s,y2s) /  Preparing segment:a rectangle by (x1p,y1p), (x2p,y2p) /Figure 2
Illustration of spread process and back process.Figure2 also illustrates spread process and back process. Spread process starts with a TM (task message) broadcast by seed vehicle. A TM is relayed one-by-one until it reaches the border of preparing segment; thus all vehicles in preparing segment are notified of the task. The border guard, a vehicle located at the border, modifies TM to CM (collaboration message). He also starts back process by reversing relaying direction and sending CM back to seed vehicle. During back process, the vehicle that receives CM decides whether to join the group sensing and adds its decisions to CM. Seed vehicle receives the final CM and knows how many participants it has motivated. The server then could decide if the task is approved.Note that, in our threshold-based game, all drivers make decisions by predicting others’ decisions. To give participants listP to seed vehicle, decisions are recorded in P, which is relayed by vehicles. This means that some vehicles could “peep” decisions of former vehicles, which could lead to more complex models (e.g., social learning [39]) and fails our threshold-based game model. To prevent this cheating, seed and normal vehicles can use public-key cryptography [40] to tackle this problem. Normal vehicles encrypt their decisions with public key, while only seed vehicle can decipher the decisions with private key.


## 3.3. Combining Modules with Flexibility

Participants’ selection needs two modules, namely, message relaying module and collaboration motivating module, to work together. The former module is in charge of propagating information among vehicles, and the latter module is responsible for coordinating drivers’ behaviors.In VANET, messages could be propagated by contention-based relaying.That is, only the periodical winner of contention could be relaying node. Another relaying method is built upon cluster structure, which helps vehicles reduce transmission data volume and improve communication efficiency. Supported by message relaying module, group formation still needs a mechanism to motivate and select appropriate participants. The motivating method could be realized in either a centralized or distributed way. Overall, our participants’ selection framework is composed of two modules, and there are two alternative methods for each module, respectively.Decoupling participants’ selection into two modules endows the system flexibility, enabling map producers to choose optimal combination from several alternatives according to service requirements. We will discuss three combinations: centralized selection, distributed selection, and clustered selection. See Figure3 for understanding how the combination of different modules can make three distinct participants’ selection schemes.Figure 3
Three participants’ selection schemes. Each scheme is a combination of two modules. Each module includes two methods.


## 4. Participants’ Selection of Group Sensing

This section presents participants’ selection schemes derived from one framework. Before diving into three schemes, some preliminaries on relaying methods should be introduced.We only consider message relaying in “simple road condition." Simple road condition is referred to(1) the road being straight or having small curvature so that relaying method would not fail by extreme road shapes, such as zigzag or circle, and (2) neglecting intersection in preparing segment. In this way, we could simplify simulation by leaving out the situations where lots of vehicles join and leave. Furthermore, we could simplify simulation by decomposing complex road condition (zigzag, circle, etc.) into several simple road conditions. This divide-and-conquer strategy enables our proposed method to be adjustable in most transportation situations. Two examples of simple road condition are in Figure 4.Figure 4
Simple road condition. Left: straight road. Right: road with small curvature. Both examples do not consider intersections.Contention-based relaying is motivated by geocasting [41], where message is relayed from original location P0 to Pn+1 by a node chain. As described in Figure 5(a), seed vehicle is located at P0(x0,y0), previous relaying node’s location is Pn(xn,yn), and current receiver’s location is Pn+1(xn+1,yn+1). Then we have L0,n=P0Pn and Ln,n+1=PnPn+1. The angle θ=∠P0PnPn+1 is calculated by the following equation:(2)cos⁡θ=L0,n2+Ln,n+12-L0,n+122L0,nLn,n+1Figure 5
Message relaying methods. (a) Node chain. (b) Contention-based relay. (c) Cluster-based relay.
(a) (b) (c)It indicates that message is relayed away from original nodeP0 if cos⁡θ<0. The next relaying node is generated by downstream nodes’ contention. The projection of Ln,n+1 on L0,n is L′=Ln,n+1×cos⁡β. Each downstream node calculates its back off time tnotifying by [42](3)tnotifying=Tmax·1-L′LmaxwhereTmax and Lmax are predefined values and cos⁡β could be calculated in a similar way to cos⁡θ. According to (3), the most downstream node has the minimum tnotifying, thus having the highest priority to be next relaying node. Figure 5(b) illustrates how messages are delivered by winners of contention. Usually, a message could reach the destination by several hops.Another prevailing relaying method is cluster-based relaying. A virtual network infrastructure should be created through the clustering of nodes in order to provide stability and scalability. See Figure5(c) for an illustration of cluster-based relaying. Each cluster has a cluster head, which is responsible for intra- and intercluster coordination in the network management functions. Nodes inside a cluster communicate by direct links.


### 4.1. Distributed Selection

Distributed selection is a combination of contention-based relaying and distributed decision-making. As Process1 illustrated, TM is propagated by contention-based relaying to avoid broadcast storm and ensures that all drivers in assigned local region receive TM.Process 1:Contention-based relaying.
(1) Seed vehicle broadcasts TM. (2) After receiving TM, vehiclei calculates cos⁡θ. Ifcos⁡θ>0, goto (6). (3) vehiclei calculates L′, then contends to be relaying node. If fails to be, goto(6). (4) vehiclei claims himself the new relaying node. (5) If vehiclei is not on the border, it relays TM to downstream. (6) end.Then TM is modified to CM by border guard; all drivers decide whether to be participants in a distributed manner; the process of distributed decision-making is a game, where all players have the following equilibrium:(i)
No collaboration: ifR<n0μ, the reward is not enough to satisfy driver’s expectation. No driver is willing to join collaboration(ii)
Mix strategy equilibrium): ifn0μ≤R≤Nμ, each driver joins collaboration by probability p∗, where p∗ is the unique solution of(4)EmRm+1-μPosm+1≥n0=0m follows binomial distribution B(N-1,p). Equation (4) indicates that p∗ is an equilibrium where each driver has an expected payoff of 0.Furthermore, we also consider the scenario where each player knows his own costci. Then there exists a stronger constraint than (5); a driver will only collaborate when Ci≤γ∗(R). γ∗(R) is unique solution of the equation(5)EmRm+1-γPosm+1≥n0=0m follows binomial distribution B(N-1,F(γ)). Note that F(γ)=P(Ci≤γ). We can learn that all members have the same information and estimation about others. Therefore, all members have the same γ∗(R). However, different members will still make different decisions according to their private cost.Finally, if a driver decides to collaborate, he sends a decision message to seed vehicle by contention-based relaying again.


### 4.2. Centralized Selection

Centralized selection is composed of contention-based relaying and centralized decision-making. It means that all potential participants send their messages into seed vehicle that collects all messages and selects participants in a centralized manner.First, task message is propagated by process1. After that, willing driver simply sends a message that includes his private cost and other information to seed vehicle.Seed vehicle makes decisions for all drivers, since it knows all drivers cost setC={Ci1,Ci2,…,CiN}, which could be contained in P. Let us just assume that there is no same cost value among cost set. Then costs could be sorted in ascending order in C′={C1,C2,…,CN}. Seed vehicle will choose 1st to n0th smallest cost in C′ to be participants. The collaboration has optimal result under centralized decision-making:(i)
Optimal collaboration: each driver withCi≤Cn0 will be chosen and afterwards receives Cn0 incentives. The remaining N-n0 drivers do not collaborate.Each selected participant will receiveCn0 incentives, since we distribute incentives equally. By centralized selection, no driver needs to send his decision, since seed vehicle has already known the collaboration results.


### 4.3. Clustered Selection

Clustered selection scheme has a different relaying method from above two schemes. As Figure3 illustrates, the main difference between clustered selection and the other two lies in the question of how messages are relayed. Clustered selection maintains a hierarchical structure, including cluster head and cluster members. Cluster head takes responsibility for intercluster communication, thus reducing message collision and improving network efficiency.In this case, decision-making is still distributed. The integral scheme is described in process2. The formation of cluster has been wildly researched [43] and thus is not discussed in this paper.Process 2:Cluster-based relaying.
(1) Seed vehicle broadcasts TM. (2) After receiving TM, cluster head vehiclei informs cluster members the TM. It also calculatescos⁡θ. If cos⁡θ>0, goto (4). (3) If cluster head vehiclei is not on the border, it relays TM to a cluster head of downstream. (4) end.Finally, all members are informed of task information. Being similar to Section4.1, distributed decision-making is leveraged to select appropriate participants. The results of decisions are sent back to seed vehicle by cluster-based relaying again.


## 4.1. Distributed Selection

Distributed selection is a combination of contention-based relaying and distributed decision-making. As Process1 illustrated, TM is propagated by contention-based relaying to avoid broadcast storm and ensures that all drivers in assigned local region receive TM.Process 1:Contention-based relaying.
(1) Seed vehicle broadcasts TM. (2) After receiving TM, vehiclei calculates cos⁡θ. Ifcos⁡θ>0, goto (6). (3) vehiclei calculates L′, then contends to be relaying node. If fails to be, goto(6). (4) vehiclei claims himself the new relaying node. (5) If vehiclei is not on the border, it relays TM to downstream. (6) end.Then TM is modified to CM by border guard; all drivers decide whether to be participants in a distributed manner; the process of distributed decision-making is a game, where all players have the following equilibrium:(i)
No collaboration: ifR<n0μ, the reward is not enough to satisfy driver’s expectation. No driver is willing to join collaboration(ii)
Mix strategy equilibrium): ifn0μ≤R≤Nμ, each driver joins collaboration by probability p∗, where p∗ is the unique solution of(4)EmRm+1-μPosm+1≥n0=0m follows binomial distribution B(N-1,p). Equation (4) indicates that p∗ is an equilibrium where each driver has an expected payoff of 0.Furthermore, we also consider the scenario where each player knows his own costci. Then there exists a stronger constraint than (5); a driver will only collaborate when Ci≤γ∗(R). γ∗(R) is unique solution of the equation(5)EmRm+1-γPosm+1≥n0=0m follows binomial distribution B(N-1,F(γ)). Note that F(γ)=P(Ci≤γ). We can learn that all members have the same information and estimation about others. Therefore, all members have the same γ∗(R). However, different members will still make different decisions according to their private cost.Finally, if a driver decides to collaborate, he sends a decision message to seed vehicle by contention-based relaying again.


## 4.2. Centralized Selection

Centralized selection is composed of contention-based relaying and centralized decision-making. It means that all potential participants send their messages into seed vehicle that collects all messages and selects participants in a centralized manner.First, task message is propagated by process1. After that, willing driver simply sends a message that includes his private cost and other information to seed vehicle.Seed vehicle makes decisions for all drivers, since it knows all drivers cost setC={Ci1,Ci2,…,CiN}, which could be contained in P. Let us just assume that there is no same cost value among cost set. Then costs could be sorted in ascending order in C′={C1,C2,…,CN}. Seed vehicle will choose 1st to n0th smallest cost in C′ to be participants. The collaboration has optimal result under centralized decision-making:(i)
Optimal collaboration: each driver withCi≤Cn0 will be chosen and afterwards receives Cn0 incentives. The remaining N-n0 drivers do not collaborate.Each selected participant will receiveCn0 incentives, since we distribute incentives equally. By centralized selection, no driver needs to send his decision, since seed vehicle has already known the collaboration results.


## 4.3. Clustered Selection

Clustered selection scheme has a different relaying method from above two schemes. As Figure3 illustrates, the main difference between clustered selection and the other two lies in the question of how messages are relayed. Clustered selection maintains a hierarchical structure, including cluster head and cluster members. Cluster head takes responsibility for intercluster communication, thus reducing message collision and improving network efficiency.In this case, decision-making is still distributed. The integral scheme is described in process2. The formation of cluster has been wildly researched [43] and thus is not discussed in this paper.Process 2:Cluster-based relaying.
(1) Seed vehicle broadcasts TM. (2) After receiving TM, cluster head vehiclei informs cluster members the TM. It also calculatescos⁡θ. If cos⁡θ>0, goto (4). (3) If cluster head vehiclei is not on the border, it relays TM to a cluster head of downstream. (4) end.Finally, all members are informed of task information. Being similar to Section4.1, distributed decision-making is leveraged to select appropriate participants. The results of decisions are sent back to seed vehicle by cluster-based relaying again.


## 5. Simulation and Analysis

We simulate the framework with TransModeler, a transportation simulating environment. Figure6 is an illustration of our simulator. Based on its API, we achieve logical communication framework over vehicles to support network layer simulation. Additionally, we assume that each relaying consumes the same time slot and assume perfect channel without collision and loss in simulation. With such framework, we could simulate network layer of VANET communication in a virtual transportation scenario. Since the framework that integrates message relaying and collaboration motivating has been little discussed previously, no previous work could be compared with it. However, we still make comparison among our self-proposed methods and try to make this paper self-contained.Figure 6
TransModeler provides a virtual transportation scenario.


### 5.1. Effect Analysis of Motivating

We first analyze two motivating methods separately. Parameters are explained in Table2 and the simulation results are demonstrated in Figure 7.Table 2
Parameters in motivating simulation.
R Reward or incentive  N The number of potential participants  μ Mean of all potential participants’ cost  σ Std. of potential participants’ cost  n0 Threshold of participants’ number  M The number of final participantsFigure 7
Parameters and their influences on motivating effect.
(a)
N=70, μ=0.5, σ=0.1, and n0=40 (b)
N=70, R=20, σ=0.1, and n0=40 (c)
N=70, μ=0.5, σ=0.1, and n0=40 (d)
N=70, R=20, σ=0.1, and n0=40 (e)
N=70, R=20, μ=0.5, and n0=40 (f)
N=70, R=20,μ=0.5, σ=0.1, and n0=40


#### 5.1.1. Result of Distributed Decision-Making

Figure7(a) shows R-ρ∗ diagram depicting how driver’s collaboration probability reacts with reward. When R<20, reward is smaller than n0μ; no driver collaborates. When 20≤R<35, reward is enough to motivate part of drivers. And it shows that the larger reward is, the higher probability is that drivers will collaborate. When R≥35,that is,R≥Nμ, all drivers will collaborate; thus p∗=1. Similarly, Figure 7(b) shows that larger μ leads to lower collaboration probability. It means that, given the same reward R, fewer drivers will collaborate if the mean of costs goes higher. These findings in two figures are consistent with human intuition.


#### 5.1.2. Result of Centralized Decision-Making

Figure7(c) describes R’s influence on M. As R increases, M also increases. More reward could motivate more participants. In Figure 7(d), we could see that higher μ leads to smaller M. Figure 7(e) shows that larger σ (which means that the costs values are more dispersed) leads to smaller M. In the case in Figure 7(e), n0=40>N/2, so it needs to motivate more than N/2 drivers. With the increase of σ, n0th(n0>N/2) smallest cost Cn0(Cn0-μ>0) becomes bigger, and the value of R/Cn0 gets smaller; thus participants’ number ⌊R/Cn0⌋ decreases.


#### 5.1.3. Comparison of Two Motivating Methods

We setN=70, n0=40, R=20, μ=0.5, and σ=0.1 and use M as indicator of motivating effect. The simulation is repeated for 20 times. Figure 7(f) shows that centralized decision-making achieves larger M than distributed decision-making.It should be mentioned that a task is approved by map producer only whenM≥n0=40. However, as Figure 7(f) shows, no method could achieve M≥n0. For centralized decision-making, map producer should prepare R′=22~23 (while the planned reward is R=20) to successfully motivate n0=40 collaborators. Distributed decision-making could only motivate 3/4 participants of centralized method. To conclude, map producers should always give “extra reward” besides planned reward to reach expected M.In this section, only two basic motivating methods are discussed. We did not discuss three participants’ selection schemes, because motivating effect is only depending on the collaboration motivating module and is irrelevant to message relaying module. However, in Section5.2, we will find that the communication overhead is influenced by both modules; we therefore need to compare three integral schemes.


### 5.2. Communication Overhead of Message Relaying

The communication simulation scenario is 1000-meter road (in Figure4). DSRC range is set as 150 m. Final results are averaged by 20 simulations. Performance analysis is based on three indicators. (1) First indicator isSlots Duration. We assume that each relay consumes one time slot. During whole process, the counted number of slots is slots duration. (2) Second indicator isTotal Transmission bytes. The total bytes are gross of all messages bytes. (3) Third indicator isTotal Relaying Times. It shows how many times of relay for all vehicles have taken place during the process.


#### 5.2.1. Communication Overhead on Straight Road

Figure8 shows communication performance of three schemes on straight road (in Figure 4 (left)). Figure 8(a) shows that, for three schemes, total transmission bytes go up with vehicle density. The reason is intuitive; more vehicles cause more transmitted content. Centralized selection has the largest bytes because all vehicles send messages to seed vehicle.Figure 8
Communication overhead of three participants’ selection. (a) Centralized selection has the largest bytes overhead because each vehicle sends its information to seed vehicle. (b) Clustered selection has the longest slots duration because of its stable structure. (c) Centralized selection consumes the largest total relaying times for the same reason as (a).
(a) (b) (c)In Figure8(b), slots duration of each scheme is a constant regardless of vehicle density. Clustered selection consumes more slots than centralized and distributed selection because it spares slots on cluster maintenance.In Figure8(c), centralized selection has the largest total relaying times. Because each potential participant generates a message and sends it to seed vehicle, centralized selection has larger total relaying times than the other two.


#### 5.2.2. Communication Overhead on Curve Road

Robustness of scheme is reflected on communication performance in Figure9. A robust scheme is able to work well on both straight (in Figure 4 (left)) and curve roads (in Figure 4 (right)). In all three schemes, the indicator in straight road is lower than that in curve road. The performance difference between two road conditions is at most 20%. This figure shows that, for each local participants’ selection scheme, communication overhead on curve road is a little higher than straight road, demonstrating that these schemes could still work fine on roads with small curvature.Figure 9
Communication overhead of straight and curve road: (a) comparison of total transmission bytes between straight and curve. (b) Comparison of slots duration between straight and curve. (c) Comparison of total relaying times between straight and curve. Three schemes still work fine in road with small curvature.
(a) (b) (c)


## 5.1. Effect Analysis of Motivating

We first analyze two motivating methods separately. Parameters are explained in Table2 and the simulation results are demonstrated in Figure 7.Table 2
Parameters in motivating simulation.
R Reward or incentive  N The number of potential participants  μ Mean of all potential participants’ cost  σ Std. of potential participants’ cost  n0 Threshold of participants’ number  M The number of final participantsFigure 7
Parameters and their influences on motivating effect.
(a)
N=70, μ=0.5, σ=0.1, and n0=40 (b)
N=70, R=20, σ=0.1, and n0=40 (c)
N=70, μ=0.5, σ=0.1, and n0=40 (d)
N=70, R=20, σ=0.1, and n0=40 (e)
N=70, R=20, μ=0.5, and n0=40 (f)
N=70, R=20,μ=0.5, σ=0.1, and n0=40


### 5.1.1. Result of Distributed Decision-Making

Figure7(a) shows R-ρ∗ diagram depicting how driver’s collaboration probability reacts with reward. When R<20, reward is smaller than n0μ; no driver collaborates. When 20≤R<35, reward is enough to motivate part of drivers. And it shows that the larger reward is, the higher probability is that drivers will collaborate. When R≥35,that is,R≥Nμ, all drivers will collaborate; thus p∗=1. Similarly, Figure 7(b) shows that larger μ leads to lower collaboration probability. It means that, given the same reward R, fewer drivers will collaborate if the mean of costs goes higher. These findings in two figures are consistent with human intuition.


### 5.1.2. Result of Centralized Decision-Making

Figure7(c) describes R’s influence on M. As R increases, M also increases. More reward could motivate more participants. In Figure 7(d), we could see that higher μ leads to smaller M. Figure 7(e) shows that larger σ (which means that the costs values are more dispersed) leads to smaller M. In the case in Figure 7(e), n0=40>N/2, so it needs to motivate more than N/2 drivers. With the increase of σ, n0th(n0>N/2) smallest cost Cn0(Cn0-μ>0) becomes bigger, and the value of R/Cn0 gets smaller; thus participants’ number ⌊R/Cn0⌋ decreases.


### 5.1.3. Comparison of Two Motivating Methods

We setN=70, n0=40, R=20, μ=0.5, and σ=0.1 and use M as indicator of motivating effect. The simulation is repeated for 20 times. Figure 7(f) shows that centralized decision-making achieves larger M than distributed decision-making.It should be mentioned that a task is approved by map producer only whenM≥n0=40. However, as Figure 7(f) shows, no method could achieve M≥n0. For centralized decision-making, map producer should prepare R′=22~23 (while the planned reward is R=20) to successfully motivate n0=40 collaborators. Distributed decision-making could only motivate 3/4 participants of centralized method. To conclude, map producers should always give “extra reward” besides planned reward to reach expected M.In this section, only two basic motivating methods are discussed. We did not discuss three participants’ selection schemes, because motivating effect is only depending on the collaboration motivating module and is irrelevant to message relaying module. However, in Section5.2, we will find that the communication overhead is influenced by both modules; we therefore need to compare three integral schemes.


## 5.1.1. Result of Distributed Decision-Making

Figure7(a) shows R-ρ∗ diagram depicting how driver’s collaboration probability reacts with reward. When R<20, reward is smaller than n0μ; no driver collaborates. When 20≤R<35, reward is enough to motivate part of drivers. And it shows that the larger reward is, the higher probability is that drivers will collaborate. When R≥35,that is,R≥Nμ, all drivers will collaborate; thus p∗=1. Similarly, Figure 7(b) shows that larger μ leads to lower collaboration probability. It means that, given the same reward R, fewer drivers will collaborate if the mean of costs goes higher. These findings in two figures are consistent with human intuition.


## 5.1.2. Result of Centralized Decision-Making

Figure7(c) describes R’s influence on M. As R increases, M also increases. More reward could motivate more participants. In Figure 7(d), we could see that higher μ leads to smaller M. Figure 7(e) shows that larger σ (which means that the costs values are more dispersed) leads to smaller M. In the case in Figure 7(e), n0=40>N/2, so it needs to motivate more than N/2 drivers. With the increase of σ, n0th(n0>N/2) smallest cost Cn0(Cn0-μ>0) becomes bigger, and the value of R/Cn0 gets smaller; thus participants’ number ⌊R/Cn0⌋ decreases.


## 5.1.3. Comparison of Two Motivating Methods

We setN=70, n0=40, R=20, μ=0.5, and σ=0.1 and use M as indicator of motivating effect. The simulation is repeated for 20 times. Figure 7(f) shows that centralized decision-making achieves larger M than distributed decision-making.It should be mentioned that a task is approved by map producer only whenM≥n0=40. However, as Figure 7(f) shows, no method could achieve M≥n0. For centralized decision-making, map producer should prepare R′=22~23 (while the planned reward is R=20) to successfully motivate n0=40 collaborators. Distributed decision-making could only motivate 3/4 participants of centralized method. To conclude, map producers should always give “extra reward” besides planned reward to reach expected M.In this section, only two basic motivating methods are discussed. We did not discuss three participants’ selection schemes, because motivating effect is only depending on the collaboration motivating module and is irrelevant to message relaying module. However, in Section5.2, we will find that the communication overhead is influenced by both modules; we therefore need to compare three integral schemes.


## 5.2. Communication Overhead of Message Relaying

The communication simulation scenario is 1000-meter road (in Figure4). DSRC range is set as 150 m. Final results are averaged by 20 simulations. Performance analysis is based on three indicators. (1) First indicator isSlots Duration. We assume that each relay consumes one time slot. During whole process, the counted number of slots is slots duration. (2) Second indicator isTotal Transmission bytes. The total bytes are gross of all messages bytes. (3) Third indicator isTotal Relaying Times. It shows how many times of relay for all vehicles have taken place during the process.


### 5.2.1. Communication Overhead on Straight Road

Figure8 shows communication performance of three schemes on straight road (in Figure 4 (left)). Figure 8(a) shows that, for three schemes, total transmission bytes go up with vehicle density. The reason is intuitive; more vehicles cause more transmitted content. Centralized selection has the largest bytes because all vehicles send messages to seed vehicle.Figure 8
Communication overhead of three participants’ selection. (a) Centralized selection has the largest bytes overhead because each vehicle sends its information to seed vehicle. (b) Clustered selection has the longest slots duration because of its stable structure. (c) Centralized selection consumes the largest total relaying times for the same reason as (a).
(a) (b) (c)In Figure8(b), slots duration of each scheme is a constant regardless of vehicle density. Clustered selection consumes more slots than centralized and distributed selection because it spares slots on cluster maintenance.In Figure8(c), centralized selection has the largest total relaying times. Because each potential participant generates a message and sends it to seed vehicle, centralized selection has larger total relaying times than the other two.


### 5.2.2. Communication Overhead on Curve Road

Robustness of scheme is reflected on communication performance in Figure9. A robust scheme is able to work well on both straight (in Figure 4 (left)) and curve roads (in Figure 4 (right)). In all three schemes, the indicator in straight road is lower than that in curve road. The performance difference between two road conditions is at most 20%. This figure shows that, for each local participants’ selection scheme, communication overhead on curve road is a little higher than straight road, demonstrating that these schemes could still work fine on roads with small curvature.Figure 9
Communication overhead of straight and curve road: (a) comparison of total transmission bytes between straight and curve. (b) Comparison of slots duration between straight and curve. (c) Comparison of total relaying times between straight and curve. Three schemes still work fine in road with small curvature.
(a) (b) (c)


## 5.2.1. Communication Overhead on Straight Road

Figure8 shows communication performance of three schemes on straight road (in Figure 4 (left)). Figure 8(a) shows that, for three schemes, total transmission bytes go up with vehicle density. The reason is intuitive; more vehicles cause more transmitted content. Centralized selection has the largest bytes because all vehicles send messages to seed vehicle.Figure 8
Communication overhead of three participants’ selection. (a) Centralized selection has the largest bytes overhead because each vehicle sends its information to seed vehicle. (b) Clustered selection has the longest slots duration because of its stable structure. (c) Centralized selection consumes the largest total relaying times for the same reason as (a).
(a) (b) (c)In Figure8(b), slots duration of each scheme is a constant regardless of vehicle density. Clustered selection consumes more slots than centralized and distributed selection because it spares slots on cluster maintenance.In Figure8(c), centralized selection has the largest total relaying times. Because each potential participant generates a message and sends it to seed vehicle, centralized selection has larger total relaying times than the other two.


## 5.2.2. Communication Overhead on Curve Road

Robustness of scheme is reflected on communication performance in Figure9. A robust scheme is able to work well on both straight (in Figure 4 (left)) and curve roads (in Figure 4 (right)). In all three schemes, the indicator in straight road is lower than that in curve road. The performance difference between two road conditions is at most 20%. This figure shows that, for each local participants’ selection scheme, communication overhead on curve road is a little higher than straight road, demonstrating that these schemes could still work fine on roads with small curvature.Figure 9
Communication overhead of straight and curve road: (a) comparison of total transmission bytes between straight and curve. (b) Comparison of slots duration between straight and curve. (c) Comparison of total relaying times between straight and curve. Three schemes still work fine in road with small curvature.
(a) (b) (c)


## 6. Discussion

Given the same reward, centralized decision-making could motivate more participants than distributed decision-making. The reason is that distributed decision-making is executed by each potential participant who lacks a global view of all information. Derived from distributed decision-making, clustered selection scheme and distributed selection have the same performance on motivating. Centralized selection is better than the other two if only motivating effect is considered.Besides motivating effect, communication overhead also deserves attention. If communication overhead is considered alone, distributed selection should be the first choice, since it performs well in three indicators. Centralized selection and clustered selection are second-class citizens and are only suitable for particular scenarios. For example, if a map producer hopes the participants’ selection to be finished as soon as possible, then he would like to use centralized selection. Despite its shortcomings in total transmission bytes and total relaying times, centralized selection has the shortest slots duration.In Table3, we give a comprehensive comparison of motivating performance and communication performance. Centralized selection has a good performance in motivating but has a heavy communication overhead. Clustered selection requires more incentives and less communication overhead than centralized method. Distributed selection seems to be the first-class choice because it works fine in both motivating and communicating. It should be noted that all three selection schemes could be realized from one single framework with few modifications of two modules. The flexibility of design framework enables map producers to select participants adaptively according to scenario requirements.Table 3
Comprehensive comparison of three schemes.
∖ Centralizedselection Distributedselection Clusteredselection moti.perf. Good Normal Normal  comm.perf. Limited Good Normal


## 7. Conclusions

This paper has discussed local participants’ selection of crowdsensing. We have proposed a flexible framework that could support three kinds of selection schemes with respect to different service requirements. The framework is consisted of two modules. For collaboration motivating module, we introduced two motivating methods: centralized decision-making and distributed decision-making. For message relaying module, we introduced two methods: contention-based relaying and cluster-based relaying. Three combinations of two modules are discussed and simulated. The result shows that distributed selection is usually the first-class choice because of its fine performances on communicating and motivating. Our research analyzed group sensing problem from both communication and collaboration perspectives, providing a primary but integrated reference for data service providers or crowdsensing operators, especially for map producers.In the future, we will integrate ns-2 [44] into our framework to enable accurate time-simulation. We will also try to refine spread process and back process into “one-shot process.”



---

*Source: 1287969-2018-07-29.xml*