Anonymity level adaptation algorithm to meet resource constraint of K-anonymity service in LBS

A limitation in current design of K-anonymity services for location based services (LBS) is that they only provide a given minimum level of anonymity as QoS guarantee and can't improve the anonymity level for users when service resources are capable. The anonymous query result size was proposed as a new QoS target in order to measure and constrain resource consumption on the K-anonymity service and LBS per user query. Then appropriate anonymity level can be selected under such constraint. Theoretical analysis was performed to find mathematical relation between anonymous query result size and anonymity level, leading to the construction of anonymity level adaptation algorithm. The simulation results accorded well with the theoretical relation. The anonymity level adaptation algorithm can control anonymous query result size to stay around the specified QoS target.