We consider the extrema estimation problem in large-scale radio-frequency identification(RFID)systems,where there are thousands of tags and each tag contains a finite value.The objective is to design an extrema estima...We consider the extrema estimation problem in large-scale radio-frequency identification(RFID)systems,where there are thousands of tags and each tag contains a finite value.The objective is to design an extrema estimation protocol with the minimum execution time.Because the standard binary search protocol wastes much time due to inter-frame overhead,we propose a parameterized protocol and treat the number of slots in a frame as an unknown parameter.We formulate the problem and show how to find the best parameter to minimize the worst-case execution time.Finally,we propose two rules to further reduce the execution time.The first is to find and remove redundant frames.The second is to concatenate a frame from minimum value estimation with a frame from maximum value estimation to reduce the total number of frames.Simulations show that,in a typical scenario,the proposed protocol reduces execution time by 79%compared with the standard binary search protocol.展开更多
Mobile crowdsensing has become an efficient paradigm for performing large-scale sensing tasks. An incentive mechanism is important for a mobile crowdsensing system to stimulate participants and to achieve good service...Mobile crowdsensing has become an efficient paradigm for performing large-scale sensing tasks. An incentive mechanism is important for a mobile crowdsensing system to stimulate participants and to achieve good service quality. In this paper, we explore truthful incentive mechanisms that focus on minimizing the total payment for a novel scenario, where the platform needs the complete sensing data in a requested time window (RTW). We model this scenario as a reverse auction and design FIMI, a constant frugal incentive mechanism for time window coverage. FIMI consists of two phases, the candidate selection phase and the winner selection phase. In the candidate selection phase, it selects two most competitive disjoint feasible user sets. Afterwards, in the winner selection phase, it finds all the interchangeable user sets through a graph-theoretic approach. For every pair of such user sets, FIMI chooses one of them by the weighted cost. Further, we extend FIMI to the scenario where the RTW needs to be covered more than once. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve the properties of RTW feasibility (or RTW multi-coverage), computation efficiency, individual rationality, truthfulness, and constant frugality.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.61972199,61672283,61502232,and 61502251the Jiangsu Key Laboratory of Big Data Security Intelligent Processing,Nanjing University of Posts and Telecommunications under Grant No.BDSIP1907,China Postdoctoral Science Foundation under Grant No.2016M601859the Post-Doctoral Fund of Jiangsu Province of China under Grant No.1701047A.
文摘We consider the extrema estimation problem in large-scale radio-frequency identification(RFID)systems,where there are thousands of tags and each tag contains a finite value.The objective is to design an extrema estimation protocol with the minimum execution time.Because the standard binary search protocol wastes much time due to inter-frame overhead,we propose a parameterized protocol and treat the number of slots in a frame as an unknown parameter.We formulate the problem and show how to find the best parameter to minimize the worst-case execution time.Finally,we propose two rules to further reduce the execution time.The first is to find and remove redundant frames.The second is to concatenate a frame from minimum value estimation with a frame from maximum value estimation to reduce the total number of frames.Simulations show that,in a typical scenario,the proposed protocol reduces execution time by 79%compared with the standard binary search protocol.
文摘Mobile crowdsensing has become an efficient paradigm for performing large-scale sensing tasks. An incentive mechanism is important for a mobile crowdsensing system to stimulate participants and to achieve good service quality. In this paper, we explore truthful incentive mechanisms that focus on minimizing the total payment for a novel scenario, where the platform needs the complete sensing data in a requested time window (RTW). We model this scenario as a reverse auction and design FIMI, a constant frugal incentive mechanism for time window coverage. FIMI consists of two phases, the candidate selection phase and the winner selection phase. In the candidate selection phase, it selects two most competitive disjoint feasible user sets. Afterwards, in the winner selection phase, it finds all the interchangeable user sets through a graph-theoretic approach. For every pair of such user sets, FIMI chooses one of them by the weighted cost. Further, we extend FIMI to the scenario where the RTW needs to be covered more than once. Through both rigorous theoretical analysis and extensive simulations, we demonstrate that the proposed mechanisms achieve the properties of RTW feasibility (or RTW multi-coverage), computation efficiency, individual rationality, truthfulness, and constant frugality.
