# A Privacy-Preserving Incentive Mechanism for Data Offloading in Satellite-Terrestrial Crowdsensing

Authors: Boxiang Zhu; Jiarui Li; Zhongkai Liu; Yang Liu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Data offloading algorithm is the foundation of urban Internet of Things, which has gained attention for its large size of user engagement, low cost, and wide range of data sources, replacing traditional crowdsensing in areas such as intelligent vehicles, spectrum sensing, and environmental surveillance. In data offloading tasks, users’ location information is usually required for optimal task assignment, while some users in remote areas are unable to access base station signals, making them incapable of performing sensing tasks, and at the same time, there are serious concerns about users’ privacy leakage about their locations. Until today, location protection for task assignment in data offloading has not been well explored. In addition, existing privacy protection algorithms and data offloading task assignment mechanisms cannot provide personalized protection for different users’ privacy protection needs. To this end, we propose an algorithm known as differential private long-term privacy-preserving auction with Lyapunov stochastic theory (DP-LAL) for data offloading based on satellite-terrestrial architecture that minimizes the total payment. This not only gives an approximate optimal total payment in polynomial time but also improves the issue of poor signal in remote areas. Meanwhile, satellite-terrestrial data offloading architecture integrates wireless sensor networks and cloud computing to provide real-time data processing. What is more, we have considered long-term privacy protection goals. We employ reverse combinatorial auction and Lyapunov optimization theorem to jointly optimize queue stability and total payment. More importantly, we use Lyapunov optimization theorem to jointly optimize queue stability and total payment. We prove that our algorithm is of high efficiency in computing and has good performance in various economic attributes. For example, our algorithms are personally rational, budget-balanced, and true to the buyer and seller. We use large-scale simulations to evaluate the proposed algorithm, and compare our algorithm with existing algorithms, our algorithm shows higher efficiency and better economic properties.


---

## Body

## 1. Introduction

Advances in network technology and industrial production capabilities have led to a proliferation of mobile devices, e.g., smartphones, smart watches, and tablets, which are embedded with multiple sensors, called user equipments (UEs), e.g., global positioning system (GPS), gyroscopes, and microphones. How to offload data properly and efficiently has become a hot topic. Owing to data offloading platform provide high-quality services, this technology has been maturely applied in various fields, such as intelligent transportation [1], spectrum sensing [2], and environmental monitoring [3].The typical data offloading platform system usually consists of three layers: (1) Sensing Layer, (2) Network Layer, and (3) Cloud Computing Layer, which is shown in Figure1. In Sensing Layer, users use built-in sensors to accomplish the sensing tasks from the platform. These tasks are performed by the sensors built into the terminals, such as the camera of a phone, GPS, Bluetooth, and infrared sensing. In Network Layer, users send the data to the platform, which is composed of a backbone of centralised servers, by means of different networks, such as cellular network, sensor network, and Wi-Fi networks, for sensing. In Cloud Computing Layer, it consists of databases and servers to analyze and process the sensing data returned by users to set up intelligent systems driven by different applications.Figure 1
The typical data offloading platform system.However, there are still some challenges to such a data offloading platform system architecture. First, it requires precise real-time data aggregation across a large number of user terminals. For the sensing platform, participating in real-time data aggregation implies huge consumption, because it not only consumes the power of terminals, users’ time, and system resources, e.g., power and memory, but also requires the platform to encourage users by designing incentives. At the same time, in real-time data aggregation, if the expected benefits are not achieved, it may lead users to quit the system midway, such as closing their accounts, resulting in a decrease in service quality of service (QoS) for providers. Second, people are now more concerned about their privacy, and considering that collecting and uploading sensing data may cause privacy leakage and users may even be maliciously attacked, they will not continue to perform sensing tasks. Third, in typical sensing tasks, we mainly initiate sensing requests to users through cellular networks, Wi-Fi networks, sensor networks, etc. However, in remote areas with weak signals, users cannot use traditional access networks to complete sensing tasks.To overcome the above challenges, we introduce a differential privacy-based satellite-terrestrial architecture to address this problem. We emphasize that the incentives are designed for real-time data aggregation and also need to ensure that each user does not earn less than the expected benefits while also protecting their privacy, thus maintaining long-term user participation [4], while the satellite-terrestrial network allows users in all regions of the globe to be able to complete sensing tasks [5]. In this paper, we quantify users’ location information through differential privacy [6] and precise data aggregation based on satellite-terrestrial networks and propose an auction-based long-term online incentive mechanism to handle location information, sensing task posting, bidding, and task completion involving both buyers and sellers. We also give an effective solution to the strategy coupling problem that arises in the process.The major contributions of this paper are listed below:(i)
We use satellite-terrestrial network architecture, which can well handle the problem of weak signals in remote areas and promote the integration of global sensing networks(ii)
We propose differential privacy single-minded reverse combinatorial auction with heterogeneous cost, which can minimize the total payment. This algorithm means that we cannot only give approximate optimal total payment in polynomial time but also guarantee the approximate ratio to the optimal total payment(iii)
To achieve long-term privacy protection, we propose to use reverse combination auctions to minimize the total long-term payment to the user. Also, we use Lyapunov optimization theorem to jointly optimize queue stability and total payment(iv)
We analyze our proposed algorithm theoretically and use a large number of simulations for evaluating and analyzing our proposed mechanismThe remainder of the paper is organized as follows. The related work is discussed in Section2. Section 3 describes system model in detail. Section 5 designs the DP-LAL mechanisms and proves its feasibility. Section 7 shows simulation results of the DP-LAL mechanism. Section 8 concludes the paper.


## 2. Related Work

### 2.1. Privacy-Preserving in Crowdsensing

There has been so much work made great effort to guarantee privacy in data offloading. Security and privacy are the basic attributes of crowdsensing, which requires security research method and privacy threat analysis to provide strong privacy protection barrier. For example, in location privacy protection, users upload obscure distances and personal privacy levels in a new framework of personalized privacy protection [7]. With multiple levels of agents [8] and protocols, users can finish crowdsensing tasks without any data linkability [9]. For instance, in [10], Cai et al. proposed a knowledge market framework based on crowdsensing data offloading. Likely, SPOON [11] considers task allocation and privacy preservation using the credit of users. They also propose a framework for fog computing [12] that can improve the accuracy of task allocation. A cryptography-based perspective is also one important way to protect privacy. Zhang et al. [13] present RPTD scheme, which consists of the homomorphic Paillier encryption, and superincreasing sequence, one-way hash chain. In [14], Stackelberg game is used in the process of data collection in crowdsensing to preserve privacy.


### 2.2. Incentive Mechanism in Crowdsensing

Incentive mechanism is an essential part of the crowdsensing system, the specific performance of which is either maximize the overall profit of the system or minimize the payment of the users. In crowdsensing, there are different incentive methods. In brief, incentives can be divided into monetary and nonmonetary incentives. Monetary incentives are mainly paid to motivate users to participate. One of the most important monetary incentives is the auction, which selects the subset of participants who pay less to complete a sensing task by making an offer on their sensing data. Monetary payment incentive returns participants’ sensing data, which is the most direct and currently the main incentive method. Stackelberg game is an important method. Nie et al. model a two-stage game [15] and a multiple leaders and multiple followers Stackelberg game approach [16]. IBE [17] consists of participant selection scheme and payment decision scheme, which improve task fulfillment rates, participant utility, and platform benefits. Sun et al. [18] are offering personalized payments to users as compensation for the cost of privacy. They both increase the user’s income to incentivise them. A dynamic demand-driven incentive mechanism [19] is proposed that dynamically varies the reward for each round of sensing tasks in an on-demand way to balance its popularity. Reducing user costs is also an effective incentive approach. Hu et al. also design novel privacy incentives to protect users’ real bid information from the platform [20]. Zhan et al. [21] propose a policy gradient-based approach that efficiently learns optimal pricing policies directly from history. Duan et al. [22] design preference-based auction mechanisms (PreAM) that guarantee at the same time individual reasonableness, budgetary viability, authenticity of preferences, and realism of prices. In vehicular crowdsourcing, Chen et al. [23] propose a time-sensitive incentive mechanism that takes into account the uncertainty of vehicle travel times.


### 2.3. Satellite-Terrestrial Networks

Satellite-terrestrial network has better performance in time delay, QoS, etc. Meanwhile, satellite-terrestrial network is different from the traditional cellular network, which can get rid of the geographical limitation and achieve global network integration. Satellite-terrestrial network for 6G field has a better performance role. For example, Fu et al. [24] propose a tapped water-filling algorithm to solve the problem about the hot air balloons. Jia et al. [25] design a new algorithm that can efficiently allocate SDLSN resources to provide services to the users. Fang et al. [26] design a smart, agile, and safe HSTN for the omnipresent Internet of Things in 6G. A satellite terrestrial network architecture [27] is proposed to integrate superdense LEO and terrestrial networks for efficient data allocation. Meanwhile, Li et al. [28] propose an integral satellite-terrestrial transport solution that offloads base station traffic via broadcast transmissions from satellites, enabling energy-efficient wireless access networks. Ruan et al. [5] focus on how to provide services with different latency QoS requirements in energy-limited systems and propose an efficient power allocation mechanism for satellite-terrestrial networks. Wang et al. [29] study the problem of channel gain and distance between terrestrial users and BSs and propose a user association scheme to provide complete coverage for terrestrial users. Jiang et al. [30] propose a block division algorithm based on density, which divides users into a series different sized blocks based on their density, in order to solve the problem of poor quality due to uneven distribution of users. Huang et al. [31] implement an online scheduling framework that maximizes the volume of data accepted with minimal energy usage when files are downloaded from LEO data centers to satisfy user demand. Li et al. [32] enhance the reach of the hybrid satellite-terrestrial marine telecommunication network by deploying drones. Lin et al. propose a temporal-spatial charging scheduling algorithm [33]. Meanwhile, they introduce linear constraints to improve an energy transfer model [34], focus on fee exclusivity in random event monitoring [35], study of online collaborative charging schedules for multiple WCVs [36], and address the charging of the WRSN in the case of obstructions in order to maximize the charging utilities within a given energy constraint [37]. Also, they focus on the problem of attacks and develop a new attack for WRSN aimed at maximizing disruption [38]. In their research on underwater visible light communication systems, they propose a dedicated coding scheme based on a dual CPL design [39].However, none of the works above uses privacy-preserving auction with Lyapunov to enhance the performance of computing and thus reducing the payment of users, and no one has solved the problem of weak signals from base stations in remote areas. In short, our work incorporates all the strands of the above work in an innovative way. Our previous work [40] is mainly on the building and solving of our model, which includes the definitions of the model and the solution and optimization of the model, as well as a theoretical analysis of the lemmas of our model. In this paper, we summarize related work, including privacy-preserving mechanisms, incentive mechanisms, and satellite-terrestrial networks. Meanwhile, our work gives a more detailed system design model and a more detailed explanation of our model, not only that, but we also give the technical roadmap, which can facilitate the reader to implement our work more easily, and finally provide more convincing simulations to illustrate the advancement of our work.


## 2.1. Privacy-Preserving in Crowdsensing

There has been so much work made great effort to guarantee privacy in data offloading. Security and privacy are the basic attributes of crowdsensing, which requires security research method and privacy threat analysis to provide strong privacy protection barrier. For example, in location privacy protection, users upload obscure distances and personal privacy levels in a new framework of personalized privacy protection [7]. With multiple levels of agents [8] and protocols, users can finish crowdsensing tasks without any data linkability [9]. For instance, in [10], Cai et al. proposed a knowledge market framework based on crowdsensing data offloading. Likely, SPOON [11] considers task allocation and privacy preservation using the credit of users. They also propose a framework for fog computing [12] that can improve the accuracy of task allocation. A cryptography-based perspective is also one important way to protect privacy. Zhang et al. [13] present RPTD scheme, which consists of the homomorphic Paillier encryption, and superincreasing sequence, one-way hash chain. In [14], Stackelberg game is used in the process of data collection in crowdsensing to preserve privacy.


## 2.2. Incentive Mechanism in Crowdsensing

Incentive mechanism is an essential part of the crowdsensing system, the specific performance of which is either maximize the overall profit of the system or minimize the payment of the users. In crowdsensing, there are different incentive methods. In brief, incentives can be divided into monetary and nonmonetary incentives. Monetary incentives are mainly paid to motivate users to participate. One of the most important monetary incentives is the auction, which selects the subset of participants who pay less to complete a sensing task by making an offer on their sensing data. Monetary payment incentive returns participants’ sensing data, which is the most direct and currently the main incentive method. Stackelberg game is an important method. Nie et al. model a two-stage game [15] and a multiple leaders and multiple followers Stackelberg game approach [16]. IBE [17] consists of participant selection scheme and payment decision scheme, which improve task fulfillment rates, participant utility, and platform benefits. Sun et al. [18] are offering personalized payments to users as compensation for the cost of privacy. They both increase the user’s income to incentivise them. A dynamic demand-driven incentive mechanism [19] is proposed that dynamically varies the reward for each round of sensing tasks in an on-demand way to balance its popularity. Reducing user costs is also an effective incentive approach. Hu et al. also design novel privacy incentives to protect users’ real bid information from the platform [20]. Zhan et al. [21] propose a policy gradient-based approach that efficiently learns optimal pricing policies directly from history. Duan et al. [22] design preference-based auction mechanisms (PreAM) that guarantee at the same time individual reasonableness, budgetary viability, authenticity of preferences, and realism of prices. In vehicular crowdsourcing, Chen et al. [23] propose a time-sensitive incentive mechanism that takes into account the uncertainty of vehicle travel times.


## 2.3. Satellite-Terrestrial Networks

Satellite-terrestrial network has better performance in time delay, QoS, etc. Meanwhile, satellite-terrestrial network is different from the traditional cellular network, which can get rid of the geographical limitation and achieve global network integration. Satellite-terrestrial network for 6G field has a better performance role. For example, Fu et al. [24] propose a tapped water-filling algorithm to solve the problem about the hot air balloons. Jia et al. [25] design a new algorithm that can efficiently allocate SDLSN resources to provide services to the users. Fang et al. [26] design a smart, agile, and safe HSTN for the omnipresent Internet of Things in 6G. A satellite terrestrial network architecture [27] is proposed to integrate superdense LEO and terrestrial networks for efficient data allocation. Meanwhile, Li et al. [28] propose an integral satellite-terrestrial transport solution that offloads base station traffic via broadcast transmissions from satellites, enabling energy-efficient wireless access networks. Ruan et al. [5] focus on how to provide services with different latency QoS requirements in energy-limited systems and propose an efficient power allocation mechanism for satellite-terrestrial networks. Wang et al. [29] study the problem of channel gain and distance between terrestrial users and BSs and propose a user association scheme to provide complete coverage for terrestrial users. Jiang et al. [30] propose a block division algorithm based on density, which divides users into a series different sized blocks based on their density, in order to solve the problem of poor quality due to uneven distribution of users. Huang et al. [31] implement an online scheduling framework that maximizes the volume of data accepted with minimal energy usage when files are downloaded from LEO data centers to satisfy user demand. Li et al. [32] enhance the reach of the hybrid satellite-terrestrial marine telecommunication network by deploying drones. Lin et al. propose a temporal-spatial charging scheduling algorithm [33]. Meanwhile, they introduce linear constraints to improve an energy transfer model [34], focus on fee exclusivity in random event monitoring [35], study of online collaborative charging schedules for multiple WCVs [36], and address the charging of the WRSN in the case of obstructions in order to maximize the charging utilities within a given energy constraint [37]. Also, they focus on the problem of attacks and develop a new attack for WRSN aimed at maximizing disruption [38]. In their research on underwater visible light communication systems, they propose a dedicated coding scheme based on a dual CPL design [39].However, none of the works above uses privacy-preserving auction with Lyapunov to enhance the performance of computing and thus reducing the payment of users, and no one has solved the problem of weak signals from base stations in remote areas. In short, our work incorporates all the strands of the above work in an innovative way. Our previous work [40] is mainly on the building and solving of our model, which includes the definitions of the model and the solution and optimization of the model, as well as a theoretical analysis of the lemmas of our model. In this paper, we summarize related work, including privacy-preserving mechanisms, incentive mechanisms, and satellite-terrestrial networks. Meanwhile, our work gives a more detailed system design model and a more detailed explanation of our model, not only that, but we also give the technical roadmap, which can facilitate the reader to implement our work more easily, and finally provide more convincing simulations to illustrate the advancement of our work.


## 3. System Model

We describe the data offloading in satellite-terrestrial architecture as Figure2. There are still many unsolved problems in the typical data offloading platform system. We need a network that can cover the world, especially remote areas, to achieve global data offloading integration. Satellite-terrestrial network is a great way to achieve global network integration. In general, a satellite network consists of several satellites, ground stations (GS), and a Network Operations Control Centre (NOCC), providing services for navigation, emergency relief, communication/relay, global resources, and geographic information management. Depending on their altitude, satellites can be categorized as low earth orbit (LEO), medium earth orbit (MEO), or geostationary orbit (GSO).Figure 2
System architecture for data offloading in satellite-terrestrial crowdsensing.Users use sensors built into mobile terminals, such as the phone’s camera, GPS, Bluetooth, and infrared, to finish the tasks allocated by the platform. Urban users send data to the platform via cellular networks and remote users via satellite-terrestrial network. The backbone network transmits the data to the SDN controller center [41], which consists of databases and servers for analyzing and processing the sensing data returned by users to set up smart sensing systems powered by different applications.Meanwhile, it requires precise real-time data aggregation across a large number of user terminals, and the sensing platform continuously collects sensing data from users to provide real-time services. For the sensing platform, participating in real-time data aggregation implies a huge consumption, because it not only consumes the power of terminals, users’ time, and system resources (e.g., power and memory) but also requires the platform to encourage users by designing incentives. At the same time, in real-time data aggregation, if the expected revenue is not achieved, it may lead users to quit the system midway, such as closing their accounts or even uninstalling mobile applications, resulting in a decrease in service quality of service providers. Therefore, we emphasize that the incentive mechanism design for real-time data aggregation needs to make sure that each user’s income is not lower than expected, thus maintaining its long-term participation.Auctions are an effective way to design incentive mechanisms. In the data offloading auction mechanism, user’s private information is often included in their bids, and this part is usually private. Therefore, in order to make sure the user’s bid privacy is not being disclosed, this project intends to protect the privacy of users by submitting bid data with differential privacy noise and design a near-real, individual-reasonable, computationally effective long-term incentive mechanism that satisfies differential privacy. We suppose that all of the users are connected to a satellite-terrestrial network. Our goal is to ensure that the total payment of the data offloading platform is minimized, that is, to maximize the utility of the data offloading platform. We list the notations in Table1.Table 1
The notations in this paper.
NThe set of usersKThe amount of sensing tasks from the platformμkThe amount of subtasks of taskktk,jThejth subtasks of task kTkAllμk subtasks of task kTThe set of all of the subtasksnkThe amount of users for taskkiA specific userbiThe bid of useriLiA subset ofT, which represents the subtasks user i is interested inCiThe cost useri claimed of finishing task set LiWThe winner set of usersLiuiThe profit of usericiThe true value of the cost of useri needs to finish his task set LiSuppose there are a set ofN users ℕ=1,⋯,N. The set of access points (APs) is M=1,⋯,M. The sensing platform issues K tasks. Each task k∈1,K contains μk≥1 sensing locations and therefore contains μk subtasks. We use tk,j represents the jth subtask of task k, all μk subtasks of task k are represented by Tk=tk,j∣j∈1,μk, and all subtasks are represented by T=tk,j∣k∈1,k,j∈1,μk. But for a single sensing task, all of its subtasks are required to be completed within the same time slot. Therefore, we require each user to bid for a maximum of one subtask per sensing task at a time.


## 4. Problem Formulation

The APs are essential in the network, and each user must be linked to only one AP. We denoteai,m as
(1)ai,m=1,useriisassociatedwithAPm0,otherwise.We assume the power and bandwidth of each AP isPm and Bm, m∈M, and the lost during transmission including rayleigh fading and path loss, etc., as Lm. The power of interference received at user i is Ii, and we use a constant η0 to represent the zero mean and unit variance additive white Gaussian noise (AWGN) power. Thus, we have the signal to interference plus noise ratio (SINR) of the channel between user i and AP m and the service rate Si,m as:
(2)SINRi,m=PmLmIi+η0.According to the Shannons formula, the service rateSi,m for each user i that is associated with AP m can be described as:
(3)Si,m=Bmlog21+SINRi,m.We also suppose the bidding data of each user isAi. Actually, the amount of data ∑i∈ℕAi is constrained by the capacity of backhual. We suppose the system is strong enough to carry that much of data. The delay ti,m between user i and the corresponding AP m is
(4)ti,m=AiSi,m.What is more, we have to ensure that each user is associated with only one AP, and the delay is less than a constantTc as described in the following two constraints.
(5)∑m∈Mai,m=1,∀i∈ℕ,(6)ti,m<Tc,∀i∈ℕ,∀m∈M.The sensing platform is aimed at selectingnk,k∈1,k user equipments(UEs) for each sensing task. Since users have to compete for the sensing tasks in exchange for reward, we intend to model the user selection in the data offloading task as a reverse auction; the sensing platform plays a role of auctioneer in the auction of sensing task; every user i∈1,N serves as a tenderer for the sensing task. The sensing platform broadcasts a list which include subtasks called τ, and each potential user i who was interested will give a bid bi=Li,Ci, Li⊂T, where Ci is the cost he claimed of finishing sensing subtask set Li. xi=1 indicates that the user i wins the subtask set Li. We, respectively, assume that Ci are limited in the range of Cmin,Cmax where Cmax and Cmin represent the maximum and minimum sensing cost. Each user needs to follow two rules during the bidding. First, for a sensing task, the user can only bid for at most one of the subtasks. Second, the user may bid for several different sensing tasks at the same time. The first rule is to protect users from using strategies to control bids. For instance, there are two users A and B who bid subtasks t1,1 and t1,2. If this is the real bid, A will be assigned t1,1, and B will be assigned t1,2. But A may find out that if he had t1,2, he could get more reward. Therefore, A may misrepresent the cost of t1,1 and give the chance to B. Thus, A deliberately misrepresents the cost in order to win another subtask and get more awards. The first rule can effectively block solve the problem. The second rule is intended to reduce the cost of performing a sensing task, that is, allowing a single user to simultaneously perform multiple sensing tasks that do not interfere with each other in the same time slot.The sensing platform selects the winner setW in order to execute all subtasks in τ. User i maintains a true value of the cost of subtask set Li represented by ci.Definition 1 (user’s utility).
If the sensing platform accepts user’s bidbi, then the utility of the user is defined as
(7)ui=pixi−ci,where pi is the reward received from the platform. If the user i is not the winner, we will set ui to 0. Each user knows the allocation algorithm and payment method before bidding and actively uses their own strategies to maximize profits. Therefore, the cost Ci he claimed by users may be unequal to each participant’s ci.Different users have different sensing costs regarding the same sensing task. As each user determines his own subtask set, we have to design a new mechanism in case he lies about his costCi.Definition 2 (authenticity).
The auction is authentic if and only if for any useri, the utility when he bids the real valueci is no less than any other bid Ci, i.e.,
(8)uici,C−i≥uiCi,C−i,where c−i represents the cost vector of all users except user i.Now, we suppose that each user’s costCi equals the real cost ci. The sensing cost comes from both finishing the sensing tasks and power and traffic of UE and AP used during the process. We use bipt to represent the privacy and power and traffic cost of UE i at time slot t, and the cost of sensing tasks is biLit. We have cit, i.e.,
(9)cit=bipt+biLit.Definition 3 (long-term participation).
An auction meets long-term participation constraint if and only if the user’s choice probability is(10)1T∑t∈Txit≥D,∀i∈ℕ,
whereD is the threshold for the time the user was selected. In practice, we can conduct a questionnaire to determine the minimum threshold to maintain long-term user participation.Our goal is to maximize user’s long-term total profit. The power cost is relevant to the power of AP connected to the user, i.e.,(11)max∑i∈ℕuit,(12)s.t.⋃i∈N∩Tk=μk,∀k∈1,k,(13)1T∑t∈Txit≥D,∀i∈ℕ,(14)∑m∈Mai,m=1,∀i∈ℕ,(15)ti,m<Tc,∀i∈ℕ,∀m∈M,ai,m=1.The first constraint states that allK tasks will be executed by users in the winner set. The second constraint limits that in a sensing task, each user can bid up to at most one subtask. The third constraint limits the number of sensing tasks that the user performs in each round of bidding, where γ is a constant decided by the sensing platform. The fourth constraint is to ensure long-term user participation. The last two constraints ensures the user can get stable connection to AP and low latency. Our overall goal is to select the user set which has the lowest sensing cost under the above constraints. In addition, our mechanism should also satisfy the authenticity and individual rationality.The formulated problem is NP hard. We intend to solve this problem by using heuristic algorithms. Firstly, the winner set will be initialized to an empty set, after that the users who can make the greatest contribution to the selected set of sensing tasks will be able to join the winner set. If there are several users contributing the same, we will randomly select one. When all tasks are selected, this process ends.


## 5. Mechanism Design

The above heuristic algorithm does not protect user’s location privacy. We intend to protect the privacy of users by using differential privacy. Differential privacy is an excellent tool which provides a statistical guarantee of privacy leaks caused by the release of sensitive input datasets. Differential privacy’s basic idea is when the two input data sets are basically the same, the output of the two sets is almost the same under this mechanism.Definition 4 (differential privacy private).
For a random functionM, if there is only one different input between any two data sets D1 and D2 and for any output set O⊆RangeM, M is of differential privacy, i.e.,
(16)PrMD1∈S≤expε×PrMD2∈S.Random functionM corresponds to our mechanism, and RangeM is the result space of the mechanism. Approximate differential privacy allows users to have a small privacy budget ε, i.e.,
(17)PrMD1∈S≤expε×PrMD2∈S+δ.For the above heuristic algorithm, we intend to randomise the price choice result in the algorithm by using the exponential mechanism. Firstly, we define a ranking index that applies to every useri∈1,N and use this index to indicate the platform’s preference for the user.
(18)ri=CiT−Tw∩Li.The collectionTw represents the currently winning bid subtask set, i.e., Tw=∪i∈NLi. The basic principle of the above definition is that the platform always prefers to select those users that are not yet included in the set Tw and those claimed the lowest cost of the subtask. In each iteration, we calculate the user’s preference ranking. For those excluded from the winning bid list, we will use the indexing mechanism shown below to calculate the quality score.
(19)qCi,xi=−rCi.In the above formula, we use the negative sign to point to the index mechanism in the reverse auction model. Obviously, the smallerrCi the higher quality score of user i. The probability that a user is selected as the winner in the index mechanism is
(20)Prxi=1∝exp−ε′rCi,where ε′=ε/Δ·elne/δ and Δ means the maximum input difference of Ci, which is equal to Cmax−Cmin. As for ε and δ, these two parameters are used to balance privacy leakage and social cost. We randomly determine the winner from the remaining users based on the probability in the iteration. Then, we remove the user’s bid from the original set and add it to the winner set. The model diagram for this system is shown in Figure 3. The user bid data will be protected by differential privacy, and this data is then added with noise, after which it enters the sensing platform. Finally, the winner is decided based on the evaluation index.Figure 3
System design model.Note that our algorithm is subject to time average, where the current strategy is coupled to future strategies. However, a user’s bid in the future is unknown, making the selection in the user’s current time slot challengeable. In order to solve this challenge, we intend to transform the long-term participation requirements into queue stability requirements and use Lyapunov optimization theorem [42] to jointly optimize the queue stability and platform benefits.We use leverage Lyapunov optimization theorem and transform the long-term participation constraint into queue stability requirements. Assume there is a virtual request queueQ with arrival rate D. When xit=1, a virtual request leaves the queue. We can describe the backlog of the queue as follows:
(21)Qit+1=maxQit−xit,0+D.Then, we consider the Lyapunov function and the Lyapunov drift:(22)Lt≜12∑i∈ℕqit2,(23)Δt≜Lt+1−Lt.Through the Lyapunov drift theorem, by stabilizing the virtual queueQ, we can satisfy the long-term participation requirements. However, another goal of us is to maximize user’s long-term total profit, which includes the sensing cost and the power cost during bidding data transmission. The power cost is relevant to the power of satellite connected to the user, i.e.,
(24)max∑i∈ℕuit.We can jointly stabilize the queue and minimize the long-term total payments by minimizing the following drift-plus-penalty function, i.e.,(25)Δt+V∑i∈Nuit,where V is a tradeoff parameter to balance the importance of queue stability and total payments. Note that Δt has a upper bound as follows:
(26)Δt=Lt+1−Lt,(27)=12∑i∈Nmaxqit−xit,0+D2−12∑i∈Nqit2,(28)≤12∑i∈Nqit2+xit2+2qitD−xit−∑i∈Nqit2,(29)≤∑i∈ND2+12+∑i∈NqitD−∑i∈Nqitxit.In (28), we omit the item−2Dxit, thus scaling the inequality, and we have (29) because xit∈0,1.Considering that the first two items in (29) are constants, if we want to minimize the drift-plus-penalty function, we can minimize the following function instead.(30)max∑i∈NVuit−qitxit.Since the algorithm we designed involves the NP-hard problem of the total payment minimization (TPM) problem and gives the specified price in time, we cannot calculate the winner set with the smallest total payment amount in polynomial time. In the case whereP is not equal to NP, we are unable to find the group with the best price and make a payment based on the aggregated price collection and ensure that the selected payment method and expenditure ratio are optimal. In addition, in order to defend user’s privacy information unrelated to the auction during bidding process and to maintain the long-term participation of the user, we consider Lyapunov stochastic optimization to ensure the stability of the queue. Finally, according to the technical roadmap shown in Figure 4 and model diagram, we obtain the DP-LAL auction algorithm shown in Algorithm 1. As for the input, N is set as the number of users, T indicates the list of tasks and Tw shows the subtask lists, C shows the cost when users perform this task, i shows the index mechanism ranking value, bn implies workers’ bid profile, Γi is the matrix, and Q means vector.Algorithm 1: DP-LAL auction with Lyapunov stability.
Input:N,T,Tw,C,i,Γi,γ;Output:W,p1: Sort all users by bid from high to low,b1≥b2≥⋯≥bnminb∈b1⋯bn2: Ranking index mechanism:3:i=Ci/∣T−Tw∩Γi∣;4:argmaxi:bmin≤p⟶bmin;5:imin,imin+1,⋯,N⟶I;6: Add the constantδ as an appendix to C;7:δ+C⟶bN+1;8: Fill up the winner set;9:fori∈Ido10:W′⟶0,Q⟶Q′,sk∣bk≤bi⟶N′;11:end for12:while∑Tj∈TQ′≠0do13:argmaxi:sk∈N′sumU:TM∈TW;14:Wi∪Skmax⟶Wi;15:N′/Skmax⟶N′;16:end while17:forj∈Tjdo18:doQj′−minQj′,Γimax,j;19:end for20:forb∈C∩bi,bi+1do21:Wi⟶Wp;22:end for23: Pick a bid calledp from p=x=exp−∂x∣Wx/2NCmax/∑y∈bnexp−∂x∣Wx/2NCmax,∀x∈bnWp⟶W;24:returnW,p;Figure 4
Partial technical roadmap for long-term incentives for group-aware users with bid privacy protection.


## 6. Theoretical Analysis

We prove that DP-LAL meets the four attributes required for a general auction. That is, DP-LAL is computationally efficient, with individual rationality, budget balance, and authenticity for both sellers and buyers.Lemma 5.
DP-LAL is computationally efficient.Proof.
We assume that all buyers are sorted in a nonincremental order for display, and for all sellers, we sort them in a nondecreasing order according to their requirements. It takesØnlogn+mlogm time to sort the buyers and sellers, and the rest of the DP-LAL takes time to be linear. The sum of the two is the total time spent on implementing DP-LAL, which is Ønlogn+mlogm.☐Lemma 6.
DP-LAL is individually rational.Proof.
We assume that each winning buyeri pays bi. When he bids truthfully, his profit is ui=pixi−ci>=0. As for seller k, when he charges truthfully his utility which is uk=puxu−cu>=0, where p represents income, x represents user’s index, and v represents the estimated cost of user. It shows that both sellers and buyers are individually rational in DP-LAL.☐Lemma 7.
DP-LAL is budget-balanced.Proof.
If the auctioneer does not select any user as the winner, he need not have to pay any sellers. Ifn≥k+1, all the winning buyers’ payment is pb=n−1bn≥0. The profit in the auction is nonnegative because there is no winner. When n<k+1, the overall payment paid by the winning buyers is still pb=n−1bn. The all income earned by the winning sellers is ps=k−n+1ak−n+2. The auctioneer’s profit is pb−ps≥0.☐Lemma 8.
DP-LAL is authentic only when the buyers bid truthfully.Proof.
We assume thatbi and ui are the payment and profit for user i, when the bids are truthfully, i.e., bi=ci. If the user lies during budding, we have bi′≠ci′. When the tie-breaking occurs, we suppose that i is at the forefront of all users. We prove that ui′≥ui′ for any bi≠ci. Consider the following case: if a buyer wins, we have pi as its minimum value and ui=pixi−ci≥0 by Lemma 6. We know that by bidding bi>ci, the outcome of the auction will not be changed, and it results in ui′=ci−pi′=ci−pi=ui. When the user loses in the auction using his truthful bid, his profit ui=0. It is obvious that bidding bi<ci will not influence the result of the auction. By bidding bi>bmin, i becomes a winner. However, his utility becomes ui′=ci−pi=ci−bmin=ui. Based on the case, we obtain that if and only if bids are truthful, the users can earn maximum utility.☐Lemma 9.
DP-LAL is truthful for the sellers.Proof.
For every sellers, we suppose that ps and Us are the payment and profit, when he charges truthfully, i.e., as=cs. Let ps′ and us′ be his payment and profit, when he lies, i.e., as≠cs. In the proof, to simplify the description, we assume that S ranks ahead of the others after the tie-break. We prove that us≥us′ for any as≠cs. If seller wins, we have ps as its minmum value and us=psxs−vs≥0 by Lemma 6. We know that the bs>vs will not influence the result of the auction, and it results in us′=vs−ps′=vs−ps=us. If he loses by bidding truthfully, his utility is us=0. It is obvious that bidding bs<vs will not influence the result of auction. By bidding bs>bmin, s becomes a winner. However, its utility becomes us′=vs−ps=vs−bmin<0=us. Therefore U maximizes his profit by charging truthfully. From the proof of Lemmas 5–9, we obtain that DP-LAL is computationally valid, personally justifiable, budget-balanced, and realistic.☐


## 7. Simulation

In this section, we perform a wide range of simulations to simulations to show the effectiveness of our DP-LAL mechanism.


### 7.1. Simulation Setup

The following are the initial parameters we set:(i)
The initial differential privacy of each user is 0(ii)
The threshold of maintaining user’s long-term participation is 10(iii)
The number of buyers is 10(iv)
The number of sellers is 1000(v)
The bid of the buyer user is controlled within the range of [5000, 10000](vi)
The seller’s bid is controlled within the range of [1, 50](vii)
The simulated auction was conducted for a total of 500 rounds(viii)
The adjustment threshold between the long-term and efficiency values of the system is 1After the setting up the parameters, we initialize the buyer and seller variables. The seller queue is initialized to0, and each seller’s bid is set to a random number. We initialize the buyer parameter as a random number within the threshold. The buyer groups the sellers according to differential privacy, and each group of sellers is sorted by their bids, and the sellers with the highest bids in all groups are sorted using index mechanism. After that, the sensing platform looks for seller groups that offer the largest profit by traversing the bids of all sellers. If there is no group that satisfies this condition, then this group is set to −1. Then, the sensing platform charges the seller with the highest bid and searches for the highest price for the seller from the remaining buyers as the winning group for the winning group analysis:
(1)
Whether the number of winning sellers meets the seller’s demand(2)
Whether the buyer can pay the seller’s total cost based on the above two principlesAt last, the sensing platform completes the collection of buyers’ fees and pays the sellers’ profit. The remaining expenses are used as sensing platform’s profit.


### 7.2. Performance Evaluation

Firstly, we introduce a baseline to demonstrate the effectiveness of the differential private long-term privacy-preserving auction with Lyapunov (DP-LAL). The baseline is static auction without long-term participation constraints; platform is only aimed at minimizing its total payment at current slot. In the static auction, platform chooses the winner users by their accuracy bidding ratio and pay them with their critical payments at each time slot.We use the matplotlib to simulate the auction results and compare the simulation results we obtained with those obtained by traditional auction algorithms. The comparison results are shown in the figures below.We perform100 simulated auctions and gather the simulation results. However, we find out that there is a sudden drop of user number after 10 auctions in Figure 5(a), which means that most of the users left without winning a single auction and most auctions are failed. We can verify it by Figure 5(b), which shows the profit of the system, and we can see that there are only a few successful auctions. Then, we set buyers to 20, as shown in Figures 6(a) and 6(b); it is obvious that the system works stabler but not stable enough, and more buyers will make it easier for users to win in an auction and thus maintaining the stability of the system.Figure 5
System performance when the number of buyers is 10.
(a)
Active user(b)
System profitFigure 6
System performance when the number of buyers is 20.
(a)
Active user(b)
System profitNow we set buyers to 20 to make sure the system is stable. Then, we consider parameterd to estimate user’s long-term participation in our algorithm and how it will affect the stability of the system. We run the auction 500 times this time and change the value of d several times. At first, we set d to 15, which means a user can lose at most 15 auctions before he quit participating in an auction; we can see from Figure 7(a) that all of the users leave when the number of simulations reaches about 250 times. Obviously, the impact of parameter d is deeper than the number of buyers. Then, we add d to 20; as shown in Figure 8(a), half of the users leave when it reaches 500 times, but the situation is better since there are still users left in the system after 500 auctions. But comparing to Figure 7(b), we can learn from Figure 8(b) that when d is 20, the system makes almost twice the profit when d is 15. Figure 9(a) shows that only about 200 users leave after 500 auctions when d is 25; we perform more auctions and less than 50 users will leave if d is up to 30. When d is larger than 30, nobody will quit the system. We also draw the conclusion from Figures 8(b) and 9(b) that, the larger d, the faster the system makes profit. It is obviously that we can guarantee user’s long-term participation, which means no user will quit the system, with a winning rate of proximately 93.5%.Figure 7
System performance whend is 15.
(a)
Active user(b)
System profitFigure 8
System performance whend is 20.
(a)
Active user(b)
System profitFigure 9
System performance whend is 25.
(a)
Active user(b)
System profitThe comparison results are shown in Figure10. Figure 10(a) simulates the amount of active users after multiple auctions. Figure 10(b) simulates the profit of the system. With the growing of number of simulations, the number of users leave in our system is much more than those in a static auction; the system profit is also increasing at a faster rate. This proves that our algorithm guarantees a better return for users after multiple auctions.Figure 10
Comparing to static auction algorithm.
(a)
Active user(b)
System profitSince our algorithms need to consider long-term participation, real bidding, tie-breaking, and individual rationality, there is no guarantee that the DP-LAL algorithm will achieve the theoretical maximum benefit. However, according to our analysis, our algorithm can maintain the advantage of the number of users compared to the static algorithm after multiple auctions and can choose higher bids and better yield among more users.We can draw a conclusion that the static algorithm does not take into account the long-term involvement of users, and many users will quit the system after they have not been selected as winners for a long time. On the whole, our algorithm better solves the problem of maintaining long-term user participation.


## 7.1. Simulation Setup

The following are the initial parameters we set:(i)
The initial differential privacy of each user is 0(ii)
The threshold of maintaining user’s long-term participation is 10(iii)
The number of buyers is 10(iv)
The number of sellers is 1000(v)
The bid of the buyer user is controlled within the range of [5000, 10000](vi)
The seller’s bid is controlled within the range of [1, 50](vii)
The simulated auction was conducted for a total of 500 rounds(viii)
The adjustment threshold between the long-term and efficiency values of the system is 1After the setting up the parameters, we initialize the buyer and seller variables. The seller queue is initialized to0, and each seller’s bid is set to a random number. We initialize the buyer parameter as a random number within the threshold. The buyer groups the sellers according to differential privacy, and each group of sellers is sorted by their bids, and the sellers with the highest bids in all groups are sorted using index mechanism. After that, the sensing platform looks for seller groups that offer the largest profit by traversing the bids of all sellers. If there is no group that satisfies this condition, then this group is set to −1. Then, the sensing platform charges the seller with the highest bid and searches for the highest price for the seller from the remaining buyers as the winning group for the winning group analysis:
(1)
Whether the number of winning sellers meets the seller’s demand(2)
Whether the buyer can pay the seller’s total cost based on the above two principlesAt last, the sensing platform completes the collection of buyers’ fees and pays the sellers’ profit. The remaining expenses are used as sensing platform’s profit.


## 7.2. Performance Evaluation

Firstly, we introduce a baseline to demonstrate the effectiveness of the differential private long-term privacy-preserving auction with Lyapunov (DP-LAL). The baseline is static auction without long-term participation constraints; platform is only aimed at minimizing its total payment at current slot. In the static auction, platform chooses the winner users by their accuracy bidding ratio and pay them with their critical payments at each time slot.We use the matplotlib to simulate the auction results and compare the simulation results we obtained with those obtained by traditional auction algorithms. The comparison results are shown in the figures below.We perform100 simulated auctions and gather the simulation results. However, we find out that there is a sudden drop of user number after 10 auctions in Figure 5(a), which means that most of the users left without winning a single auction and most auctions are failed. We can verify it by Figure 5(b), which shows the profit of the system, and we can see that there are only a few successful auctions. Then, we set buyers to 20, as shown in Figures 6(a) and 6(b); it is obvious that the system works stabler but not stable enough, and more buyers will make it easier for users to win in an auction and thus maintaining the stability of the system.Figure 5
System performance when the number of buyers is 10.
(a)
Active user(b)
System profitFigure 6
System performance when the number of buyers is 20.
(a)
Active user(b)
System profitNow we set buyers to 20 to make sure the system is stable. Then, we consider parameterd to estimate user’s long-term participation in our algorithm and how it will affect the stability of the system. We run the auction 500 times this time and change the value of d several times. At first, we set d to 15, which means a user can lose at most 15 auctions before he quit participating in an auction; we can see from Figure 7(a) that all of the users leave when the number of simulations reaches about 250 times. Obviously, the impact of parameter d is deeper than the number of buyers. Then, we add d to 20; as shown in Figure 8(a), half of the users leave when it reaches 500 times, but the situation is better since there are still users left in the system after 500 auctions. But comparing to Figure 7(b), we can learn from Figure 8(b) that when d is 20, the system makes almost twice the profit when d is 15. Figure 9(a) shows that only about 200 users leave after 500 auctions when d is 25; we perform more auctions and less than 50 users will leave if d is up to 30. When d is larger than 30, nobody will quit the system. We also draw the conclusion from Figures 8(b) and 9(b) that, the larger d, the faster the system makes profit. It is obviously that we can guarantee user’s long-term participation, which means no user will quit the system, with a winning rate of proximately 93.5%.Figure 7
System performance whend is 15.
(a)
Active user(b)
System profitFigure 8
System performance whend is 20.
(a)
Active user(b)
System profitFigure 9
System performance whend is 25.
(a)
Active user(b)
System profitThe comparison results are shown in Figure10. Figure 10(a) simulates the amount of active users after multiple auctions. Figure 10(b) simulates the profit of the system. With the growing of number of simulations, the number of users leave in our system is much more than those in a static auction; the system profit is also increasing at a faster rate. This proves that our algorithm guarantees a better return for users after multiple auctions.Figure 10
Comparing to static auction algorithm.
(a)
Active user(b)
System profitSince our algorithms need to consider long-term participation, real bidding, tie-breaking, and individual rationality, there is no guarantee that the DP-LAL algorithm will achieve the theoretical maximum benefit. However, according to our analysis, our algorithm can maintain the advantage of the number of users compared to the static algorithm after multiple auctions and can choose higher bids and better yield among more users.We can draw a conclusion that the static algorithm does not take into account the long-term involvement of users, and many users will quit the system after they have not been selected as winners for a long time. On the whole, our algorithm better solves the problem of maintaining long-term user participation.


## 8. Conclusion

In this paper, we design a differential private long-term privacy preserving auction with Lyapunov (DP-LAL) auction, which is used to perform sensing task release, auction, and task completion. Our algorithm considers long-term participation constraints and user differential privacy, which is essential for motivating participation in real-time data aggregation. Due to the combination of the user’s strategic behavior and task nature, we propose a computational efficiency mechanism with near-optimal performance to jointly optimize the participation of users’ payment and sensing platforms and ensure that users are encouraged to participate for a long time. In addition, we ensure that the proposed auction meets other desirable attributes, including authenticity and truthfulness. The validity of the proposed auction is verified by theoretical analysis and extensive simulation. At present, our algorithm has been able to guarantee the user’s motivation to participate in the auction for a long time, and to ensure that after multiple rounds of auction, the average profit of the user is much larger than an existing algorithm.



---

*Source: 1951095-2021-12-31.xml*