移動社交網中基于網格的私密近鄰檢測算法研究.pdf

1、作為基于位置服務的一種基礎服務，近鄰檢測可以幫助移動用戶尋找附近的好友。近年來，它在人們的日常生活中應用得越來越廣泛，同時，其隱藏的位置隱私安全問題也逐漸引起人們的關注:用戶必須向位置服務提供商提供自身的位置信息才能獲得與好友的近鄰關系，一旦這些信息被泄露，用戶的位置隱私將會受到極大威脅?，F有的近鄰檢測算法大多以消耗大量的CPU和內存為代價來保護用戶的位置隱私，忽略了近鄰檢測的服務質量，降低了近鄰檢測的可應用性。因此，本文主要研究既能保

2、護用戶位置隱私又能保證近鄰查詢服務質量的，基于網格的近鄰檢測算法。
　　本文首先結合了網格在近鄰檢測位置隱私保護中的特點和應用，提出了基于“一度”網格的近鄰檢測算法—ODG算法。“一度”網格是指地圖上任意1經度×1緯度的網格化區(qū)域。ODG算法將檢測空間縮小到“一度”網格內，把用戶的位置信息轉換為沒有直接關聯(lián)的網格序列號，再利用哈希函數的不可逆性和集包含運算保護用戶的位置隱私，從而實現近鄰檢測。論文定義了ODG算法的系統(tǒng)模型，詳細描

3、述了“一度”網格的建立過程及ODG算法的實現步驟，分析了算法的安全性和有效性，并通過仿真實驗將ODG算法與經典網格檢測算法VicinityLocator進行比較，仿真結果表明ODG算法的性能優(yōu)于VicinityLocator。
　　針對ODG算法中，“一度”網格的建立過程繁瑣及好友的位置隱私沒有得到與查詢發(fā)起方相同的公平保護兩方面的不足，本文進一步提出了基于參考點的近鄰檢測算法—RefP算法。RefP算法將“一度”網格簡化為參考點