基于遗传算法的空间网格划分匿名算法

Anonymous algorithm for spatial mesh generation based on genetic algorithm

隐私泄露问题已经成为阻碍基于位置的服务(location-based services,LBS)进一步发展的原因。针对当LBS用户发送查询时,用户的个人隐私可能会泄露给攻击者的问题,提出了基于遗传算法的空间网格划分的隐私保护算法(GAGP)。算法包括两个方法,即地图分割算法和假名生成法。地图分割算法利用遗传算法给每个网格赋权值,再通过使用邻接网格扩展的方法,保证每个划分区域的查询频率基本相等。假名生成法是用户在每次发送查询时使用假名来应对长期统计的攻击方式。通过实验证明所提算法与其他三种算法相比结果较好,所以提出的方案能够有效地保护用户的隐私。

Privacy breaches have become an obstacle to the further development of LBS.Concerns that when an LBS user sends a query,the user’s personal privacy may be disclosed to an attacker.This paper proposed a scheme called grid-based genetic privacy protection algorithm(GAGP)that based on the conception of weighted optimal genetic algorithm.This scheme involved two basic procedures:map segmentation and pseudonym generation.Map segmentation algorithm used genetic algorithm to assign values to each grid,and then used the method of adjacent grid expansion to ensure that the query frequency of each partition area was basically equal.Kana generation was a way for users to use a pseudonym each time they sent a query in response to a long-term statistical attack.The experimental results show that the proposed algorithm is better than the other three algorithms,so the proposed scheme can effectively protect the privacy of users.