本文選題：基于位置的服務(wù)　切入點(diǎn)：近鄰檢測　出處：《北京交通大學(xué)》2016年碩士論文　論文類型：學(xué)位論文

【摘要】：作為基于位置服務(wù)的一種基礎(chǔ)服務(wù),近鄰檢測可以幫助移動用戶尋找附近的好友。近年來,它在人們的日常生活中應(yīng)用得越來越廣泛,同時,其隱藏的位置隱私安全問題也逐漸引起人們的關(guān)注：用戶必須向位置服務(wù)提供商提供自身的位置信息才能獲得與好友的近鄰關(guān)系,一旦這些信息被泄露,用戶的位置隱私將會受到極大威脅�，F(xiàn)有的近鄰檢測算法大多以消耗大量的CPU和內(nèi)存為代價來保護(hù)用戶的位置隱私,忽略了近鄰檢測的服務(wù)質(zhì)量,降低了近鄰檢測的可應(yīng)用性。因此,本文主要研究既能保護(hù)用戶位置隱私又能保證近鄰查詢服務(wù)質(zhì)量的,基于網(wǎng)格的近鄰檢測算法。本文首先結(jié)合了網(wǎng)格在近鄰檢測位置隱私保護(hù)中的特點(diǎn)和應(yīng)用,提出了基于“一度”網(wǎng)格的近鄰檢測算法—ODG算法�！耙欢取本W(wǎng)格是指地圖上任意1經(jīng)度×1緯度的網(wǎng)格化區(qū)域。ODG算法將檢測空間縮小到“一度”網(wǎng)格內(nèi),把用戶的位置信息轉(zhuǎn)換為沒有直接關(guān)聯(lián)的網(wǎng)格序列號,再利用哈希函數(shù)的不可逆性和集包含運(yùn)算保護(hù)用戶的位置隱私,從而實(shí)現(xiàn)近鄰檢測。論文定義了ODG算法的系統(tǒng)模型,詳細(xì)描述了“一度”網(wǎng)格的建立過程及ODG算法的實(shí)現(xiàn)步驟,分析了算法的安全性和有效性,并通過仿真實(shí)驗(yàn)將ODG算法與經(jīng)典網(wǎng)格檢測算法VicinityLocator進(jìn)行比較,仿真結(jié)果表明ODG算法的性能優(yōu)于VicinityLocator。針對ODG算法中,“一度”網(wǎng)格的建立過程繁瑣及好友的位置隱私?jīng)]有得到與查詢發(fā)起方相同的公平保護(hù)兩方面的不足,本文進(jìn)一步提出了基于參考點(diǎn)的近鄰檢測算法-RefP算法。RefP算法將“一度”網(wǎng)格簡化為參考點(diǎn),省略了網(wǎng)格的建立過程,而且,好友可以根據(jù)自己的位置隱私偏好設(shè)定檢測區(qū)域。另外,在RefP算法中,好友不需要進(jìn)行哈希運(yùn)算,這大大減少了算法在運(yùn)行過程中的CPU消耗。本文還通過理論分析和仿真實(shí)驗(yàn)比較了ODG和RefP兩種算法,驗(yàn)證了RefP算法比ODG算法具有更好的性能。最后,本文在iOS平臺上設(shè)計(jì)了一款基于RefP算法的應(yīng)用程序,通過對該應(yīng)用程序的性能分析,進(jìn)一步驗(yàn)證了RefP算法的有效性和穩(wěn)定性。
[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.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP393.08

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉波;;“算法設(shè)計(jì)與分析”教學(xué)探討[J];高等理科教育;2007年04期

2 肖小克;陳莉;;《算法設(shè)計(jì)與分析》實(shí)踐教學(xué)探討[J];福建電腦;2009年10期

3 穆瑞輝;;計(jì)算機(jī)算法設(shè)計(jì)研究與思考[J];數(shù)字技術(shù)與應(yīng)用;2012年12期

4 潘博;;構(gòu)建“算法設(shè)計(jì)與分析”趣味課堂[J];科教文匯(下旬刊);2013年06期

5 王希常,楊志強(qiáng);一類考場編排算法的設(shè)計(jì)[J];山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年04期

6 龍騰芳,高金文;“分而治之”方法在算法設(shè)計(jì)中的應(yīng)用[J];渤海大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年01期

7 呂國英;;《算法設(shè)計(jì)與分析》教材建設(shè)的實(shí)施[J];計(jì)算機(jī)教育;2007年19期

8 徐子珊;;“算法設(shè)計(jì)與分析”教學(xué)中理論與技術(shù)的平衡[J];計(jì)算機(jī)教育;2008年10期

9 鄭紅;邵志清;符海波;;“算法設(shè)計(jì)與分析”課程教學(xué)改革初探[J];計(jì)算機(jī)教育;2008年14期

10 高尚;;“算法設(shè)計(jì)與分析”課程改革初探[J];計(jì)算機(jī)教育;2008年14期

相關(guān)會議論文 前10條

1 雷詠梅;;橢圓曲線密碼體制的算法設(shè)計(jì)與實(shí)現(xiàn)[A];西部大開發(fā) 科教先行與可持續(xù)發(fā)展——中國科協(xié)2000年學(xué)術(shù)年會文集[C];2000年

2 楊盤洪;朱軍祥;趙建安;楊靜;;機(jī)動目標(biāo)跟蹤的模糊變結(jié)構(gòu)交互多模算法[A];2007'中國儀器儀表與測控技術(shù)交流大會論文集（二）[C];2007年

3 徐子珊;;《算法設(shè)計(jì)與分析》課程中的工程教育[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

4 王輝;劉治昌;;用一種新算法設(shè)計(jì)的安全系統(tǒng)[A];2007年中國智能自動化會議論文集[C];2007年

5 舒輝;柳清峰;杜祝平;周蓓;;實(shí)踐教學(xué)模式在本科專業(yè)課程教學(xué)中的應(yīng)用[A];中國電子教育學(xué)會高教分會2010年論文集[C];2010年

6 彭小宏;陽東升;劉忠;;基于聚類算法的組織協(xié)作網(wǎng)設(shè)計(jì)[A];2006中國控制與決策學(xué)術(shù)年會論文集[C];2006年

7 李皓;羅熊;;云存儲部署優(yōu)化的進(jìn)化算法設(shè)計(jì)[A];2013年中國智能自動化學(xué)術(shù)會議論文集（第三分冊）[C];2013年

8 羅長政;李熙瑩;王鎮(zhèn)波;羅東華;;一種大流量交叉路口的背景提取與更新算法[A];第十五屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集[C];2010年

9 楊利;李霖;昌月樓;陽國貴;;對稱位向量及啟發(fā)式并行散列連接算法[A];數(shù)據(jù)庫研究與進(jìn)展95——第十三屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集[C];1995年

10 張晉;;嵌入式電腦鼠運(yùn)行算法的研究[A];全國第20屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集（上冊）[C];2009年

相關(guān)重要報(bào)紙文章 前1條

1 ;算法設(shè)計(jì)的策略[N];電腦報(bào);2003年

相關(guān)博士學(xué)位論文 前10條

1 谷偉哲;齊次光滑算法及其應(yīng)用[D];天津大學(xué);2010年

2 龍海俠;進(jìn)化算法及其在生物信息中的應(yīng)用[D];江南大學(xué);2010年

3 譚躍;具有混沌局部搜索策略的粒子群優(yōu)化算法研究[D];中南大學(xué);2013年

4 尤海峰;求解隱式目標(biāo)優(yōu)化問題的交互式進(jìn)化算法研究[D];中國科學(xué)技術(shù)大學(xué);2011年

5 張常淳;基于MapReduce的大數(shù)據(jù)連接算法的設(shè)計(jì)與優(yōu)化[D];中國科學(xué)技術(shù)大學(xué);2014年

6 郭崇慧;地區(qū)中長期發(fā)展規(guī)劃若干定量模型、算法及應(yīng)用研究[D];大連理工大學(xué);2002年

7 蔣蔚;粒子濾波改進(jìn)算法研究與應(yīng)用[D];哈爾濱工業(yè)大學(xué);2010年

8 孫賀;算法設(shè)計(jì)中的若干前沿問題[D];復(fù)旦大學(xué);2009年

9 陳寧濤;基于二分技術(shù)的高效算法設(shè)計(jì)及其應(yīng)用[D];華中科技大學(xué);2006年

10 婁曉文;無符號基因組切割再粘貼重組問題的算法研究[D];山東大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 李欣園;基于選擇偏好的組合聚類算法研究與實(shí)現(xiàn)[D];內(nèi)蒙古大學(xué);2015年

2 楊瀟;界約束非線性最小二乘問題的無導(dǎo)數(shù)算法[D];上海交通大學(xué);2015年

3 王曉璐;基于Zynq的LS-SVM算法加速器設(shè)計(jì)[D];哈爾濱工業(yè)大學(xué);2015年

4 樓磊磊;醫(yī)療保險數(shù)據(jù)異常行為檢測算法和系統(tǒng)[D];浙江大學(xué);2015年

5 齊海龍;基于改進(jìn)人工蜂群算法的非線性系統(tǒng)辨識方法研究[D];北京化工大學(xué);2015年

6 蔡平梅;結(jié)構(gòu)化稀疏信號的恢復(fù)算法研究[D];上海大學(xué);2015年

7 趙晨陽;基于蟻群算法的高階圖匹配方法研究[D];西安電子科技大學(xué);2014年

8 茍清松;多目標(biāo)粒子濾波檢測前跟蹤算法研究[D];電子科技大學(xué);2015年

9 李枝勇;蝙蝠算法及其在函數(shù)優(yōu)化中的應(yīng)用研究[D];上海理工大學(xué);2013年

10 李蓮;基于蜂群和粗糙集的聚類算法研究[D];長沙理工大學(xué);2014年

，

本文編號：1589729