移动社交网中基于网格的私密近邻检测算法研究

发布时间：2018-03-09 18:30

本文选题：基于位置的服务　切入点：近邻检测　出处：《北京交通大学》2016年硕士论文　论文类型：学位论文

【摘要】：作为基于位置服务的一种基础服务,近邻检测可以帮助移动用户寻找附近的好友。近年来,它在人们的日常生活中应用得越来越广泛,同时,其隐藏的位置隐私安全问题也逐渐引起人们的关注：用户必须向位置服务提供商提供自身的位置信息才能获得与好友的近邻关系,一旦这些信息被泄露,用户的位置隐私将会受到极大威胁。现有的近邻检测算法大多以消耗大量的CPU和内存为代价来保护用户的位置隐私,忽略了近邻检测的服务质量,降低了近邻检测的可应用性。因此,本文主要研究既能保护用户位置隐私又能保证近邻查询服务质量的,基于网格的近邻检测算法。本文首先结合了网格在近邻检测位置隐私保护中的特点和应用,提出了基于“一度”网格的近邻检测算法—ODG算法。“一度”网格是指地图上任意1经度×1纬度的网格化区域。ODG算法将检测空间缩小到“一度”网格内,把用户的位置信息转换为没有直接关联的网格序列号,再利用哈希函数的不可逆性和集包含运算保护用户的位置隐私,从而实现近邻检测。论文定义了ODG算法的系统模型,详细描述了“一度”网格的建立过程及ODG算法的实现步骤,分析了算法的安全性和有效性,并通过仿真实验将ODG算法与经典网格检测算法VicinityLocator进行比较,仿真结果表明ODG算法的性能优于VicinityLocator。针对ODG算法中,“一度”网格的建立过程繁琐及好友的位置隐私没有得到与查询发起方相同的公平保护两方面的不足,本文进一步提出了基于参考点的近邻检测算法-RefP算法。RefP算法将“一度”网格简化为参考点,省略了网格的建立过程,而且,好友可以根据自己的位置隐私偏好设定检测区域。另外,在RefP算法中,好友不需要进行哈希运算,这大大减少了算法在运行过程中的CPU消耗。本文还通过理论分析和仿真实验比较了ODG和RefP两种算法,验证了RefP算法比ODG算法具有更好的性能。最后,本文在iOS平台上设计了一款基于RefP算法的应用程序,通过对该应用程序的性能分析,进一步验证了RefP算法的有效性和稳定性。
[Abstract]:As a basic service of location-based service, nearest neighbor detection can help mobile users find friends nearby. In recent years, it has been used more and more widely in people's daily life, at the same time, The hidden problem of location privacy security has attracted more and more attention: users must provide their location information to the location service provider in order to obtain the close relationship with their friends, once the information is leaked, The location privacy of users will be greatly threatened. Most of the existing nearest neighbor detection algorithms protect the location privacy of users at the cost of consuming a lot of CPU and memory, and ignore the quality of service of neighbor detection. The applicability of nearest neighbor detection is reduced. Therefore, this paper mainly focuses on how to protect the privacy of user location and ensure the quality of service of nearest neighbor query. Firstly, this paper combines the characteristics and applications of mesh in the privacy protection of nearest neighbor detection. The nearest neighbor detection algorithm-ODG algorithm based on "once" grid is proposed. "once" grid is a gridded area of any 1 longitude 脳 1 latitude on a map. ODG algorithm reduces the detection space to "once" grid. The user's location information is transformed into a grid sequence number without direct correlation, and then the irreversibility of the hash function and the set inclusion operation are used to protect the user's location privacy, thus the nearest neighbor detection is realized. The system model of the ODG algorithm is defined in this paper. The establishment process of "once" mesh and the steps of ODG algorithm are described in detail. The security and effectiveness of the algorithm are analyzed, and the ODG algorithm is compared with the classical grid detection algorithm VicinityLocator through simulation experiments. The simulation results show that the performance of ODG algorithm is better than that of victim Locator. In ODG algorithm, the establishment of "one-time" grid is cumbersome and the privacy of friends' location is not protected as fairly as that of query initiator. In this paper, a reference point based nearest neighbor detection algorithm, RefP algorithm. RefP algorithm is proposed, which simplifies the "once" mesh to a reference point and omits the process of grid establishment. Friends can set detection areas according to their location privacy preferences. In addition, in the RefP algorithm, friends do not need to hashing. This greatly reduces the CPU consumption of the algorithm in the running process. This paper also compares the two algorithms ODG and RefP through theoretical analysis and simulation experiments, and verifies that the RefP algorithm has better performance than the ODG algorithm. In this paper, an application program based on RefP algorithm is designed on iOS platform. The effectiveness and stability of RefP algorithm are further verified by analyzing the performance of the application program.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.08

【相似文献】