![](https://csdnimg.cn/release/download_crawler_static/15782861/bg4.jpg)
922 J. Comput. Sci. & Technol., Sept. 2017, Vol.32, No.5
payment they will receive. In [25], they further ext-
ended the user-centric model to three cases: single re-
quester with single bid, single requester with multiple
bids, and multiple requesters with multiple bids. Xu
et al. designed the incentive mechanisms, which con-
sider the issue of stimulating the bia sed requesters in
the competing crowdsourcing market
[26]
. Koutsop ou-
los designed an optimal reverse auction
[27]
, considering
the data qua lity as user participation level. However,
the quality indicato r, which es sentially measures the
relevance or usefulness of information, is empirical and
relies on users’ historical information. It is not rea-
sonable to assume that the historical info rmation ca n
be obtained in advance. In [12], Feng et al. formu-
lated the location-aware collaborative sensing problem
as the winning bids de termination problem, and pr e-
sented a truthful auction using the proportiona l sha re
allocation rule proposed in [15]. However the mecha-
nism is only effective to perform location-aware tasks.
In [13], Zhao et al. investigated the online crowdsourc-
ing sce nario wher e the users submit their profiles to the
crowdsourcer when they arrive. The objective is select-
ing a subset of users for maximizing the value of the
crowdsourcer under the budget constraint. They de-
signed two online mechanisms, online mechanism un-
der zero arrival-departure interval mode l (OMZ) and
online mechanism under general arrival-departure in-
terval model (O MG) for different user models. Xu et
al. also tackled the mobile cr owdsensing with strong re-
quirement of data integrity
[28-29]
. However, [28] focuses
on optimizing the social cost, and [29] focuses on maxi-
mizing the value of platform under budget constraint.
A theory of frugality has been developed with the
goal of providing mechanisms that admit minimal pay-
ment. In [16], Archer and Tardos proposed the frugality
problem in path auction, and analyzed the overpay-
ment of VCG mechanism. As observed by Talwar
[30]
,
the class of instances for which VCG never overpays is
a natura l generaliz ation of matroids. Moreover, some
sufficient conditio ns to uppe r bound and lower bound
of the overpayment in non-matroids cases were g iven
in [30]. The benchmark of payment for any truthful
mechanism and the concept of frugality ratio were pro-
posed in [17]. Kempe et al. studied truthful mecha-
nisms for hiring a team of agents in three classes of set
systems: vertex cover auctions, k-flow auctions and cut
auctions, demonstr ating the truthful mechanisms for all
three set systems are constant-competitive
[31]
. Elkind
et al. proposed a modified definition of frugality and
a truthful polynomial-time auction for the vertex cover
problem
[32]
. Chen et al. proposed a uniform scheme
for designing frugal truthful mechanisms for general se t
systems, a nd applied the scheme to vertex cover sys-
tems and k-path systems
[33]
.
Overall, there is no efficient method to solve the
payment minimizing problem in mobile crowdsensing
when the dis tribution of cost is unknown. Designing
incentive mechanisms, which achieve truthfulness and
constant frugality simultaneously, is an open problem
that none of the proposals has solved.
3 System Model and Problem Formulation
As illustrated in Fig.2, we consider a mobile crowd-
sensing system c onsisting of a platform and a set of
smartphone users U = {1, 2,..., n}. The pla tform pub-
licizes a required time window (RTW) W = [T
S
, T
E
],
where T
S
and T
E
are the start time and the end time,
respectively. The platform requests the sensing data
in the p eriod from T
S
to T
E
. We denote the length
of RTW, i.e., the number of time unit, as |W|. The
time unit, which is closely related to the application
scenario, is determined by the sampling frequency of
sensing data in practice. Each user i responds with a
bid B
i
= ([s
i
, e
i
], b
i
), where [s
i
, e
i
] is the user time win-
dow (UTW) within which use r i ca n perform. Each
UTW [s
i
, e
i
] is associated with cost c
i
. The start time
s
i
and the end time e
i
(s
i
6 e
i
) can be any point-in-
time. However, any s
i
< T
S
or e
i
> T
E
cannot bring
extra benefit for user i in our mechanism. b
i
is the
claimed cost which is the bid price that user i wants to
charge for performing [s
i
, e
i
]. For any subset of users
S ⊆ U , let c(S) =
P
i∈S
b
i
. We consider the real cost c
i
is private and unk nown to other users and the platform.
Platform
(1) RTW
(2) Bids
(3) Notify
Winners
(4) Data
(5) Payment
Smartphones
Fig.2. Illustration of a mobile crowdsensing system. The num-
ber represents the sequence of the interactions between the plat-
form and users.