一種基於泰森多邊形的相同服務請求位置隱私保護方法與流程

2023-07-05 05:44:06

本發明屬於基於網絡位置的服務及隱私保護技術領域，尤其涉及一種基於泰森多邊形的相同服務請求位置隱私保護方法。

背景技術：

目前，隨著無線通信技術的不斷發展，移動端的生活服務軟體層出不窮，這些軟體在方便了人們的生活和消費的同時，也帶來了無窮的安全隱患。目前有代表性的全球衛星導航定位系統包括美國的GPS、俄羅斯的GLONASS、中國的北鬥系統以及歐洲的伽利略，而定位系統成了這些軟體服務的關鍵功能之一。

基於位置服務LBS(Location Based Service)是指通過電信移動運營商的無線電通訊網絡或外部定位方式，獲取移動終端用戶的位置信息，在GIS(Geographic Information System)平臺的支持下，為用戶提供相應服務的一種增值服務。隨著GPS精確定位功能的普及，LBS也逐漸流行起來。LBS可以看成是由移動通信網絡和計算機網絡相結合，兩者通過網關來實現動態交互。大致流程是移動終端通過移動通信網絡發出用戶請求消息，消息通過網關發送給LBS伺服器，LBS伺服器針對用戶請求消息與用戶當前位置進行查詢，然後將查詢結果通過網關返回給用戶。

隨著信息爆炸，大數據時代的到來，人們對於自身的隱私保護開始了空前的關注。然而想要這些生活服務類軟體提供精準的服務，用戶就必須首先提供自身的位置信息，這就涉及到個人隱私問題。因此，如何在共享數據的同時又能夠保護個人的隱私，是亟待解決的問題。

位置隱私保護領域遇到了很多的挑戰，比如：物聯網中有許多洩漏用戶位置隱私的方式；當所需要的服務質量越高時，造成的用戶隱私洩漏的可能性越大；不同類型的用戶對隱私保護的要求也不一樣。

在位置隱私保護的研究中，採用匿名處理的方法是當前較為流行也是極其有效的，現階段已有許多相當成熟的方法，包括基於啟發式隱私度量的位置隱私保護技術、基於概率推測的位置隱私保護技術以及基於隱私信息檢索的位置隱私保護技術。這些隱私保護方法的不足之處在於要麼未考慮真實路網的位置情況，要麼未考慮用戶的服務質量，其中最重要的一點是計算效率不佳，無法集中處理不同用戶的相同服務請求。

在實際生活中較為通用的是真實路網環境下的位置隱私保護方法。在該方法中，用戶需要請求位置服務時，將用戶所在的二維平面空間劃分為不同的區域，對每個區域中具有相同服務請求的用戶進行並發處理，可以提高服務效率。當然也可以通過添加虛擬用戶信息點來構造匿名區域。由於LBS的存在，做到匿名就需要在用戶與LBS伺服器之間架設一臺匿名伺服器，用來對用戶請求消息進行匿名處理，並對LBS伺服器查詢結果進行匹配。然而如何將多個用戶的相同服務請求(例如多個用戶都查找離自己位置最近的咖啡廳)劃分至同一區域(或匿名簇)中卻是一個較難解決的問題。此外，在匿名區域劃分時也很難做到選擇合適大小的範圍，範圍太大則降低了服務質量，太小又容易暴露用戶的真實位置信息。

如何使用更合理的方法劃分區域，同時匿名處理多個用戶的相同服務請求，從而提升匿名效率與服務質量是一個需要解決的問題。

技術實現要素：

發明目的是提供一種基於泰森多邊形的相同服務請求的位置隱私保護方法，通過泰森多邊形、多個用戶相同服務請求的特點，使用k匿名的思想，用戶可以靈活的掌握隱私保護程度，匿名的效果也將得到進一步提升，並且保護用戶的位置隱私的同時確保服務質量。

為實現上述目的，本發明採用的技術方案是一種基於泰森多邊形的相同服務請求位置隱私保護方法，包括以下步驟：

步驟1、查詢用戶以M＝(Uid,location,info,time,r,k)的六元組形式表示位於某一特定位置的用戶請求消息，其中Uid是發出請求的用戶的id號，location是用戶發出的請求位置在二維平面上的坐標(x,y)，info是表示請求查詢具體信息，time是表示用戶發出請求的時間，r是匿名區域的半徑，k是指匿名參數；

步驟2、匿名伺服器收到用戶的請求消息M以後，將請求消息在所在的泰森多邊形中進行匿名處理，生成請求消息Q，發送給LBS伺服器；

步驟3、根據收到的請求消息Q，LBS伺服器得到查詢結果S，並將其發送給匿名伺服器；

步驟4、匿名伺服器接收到查詢結果S後，對當前服務請求簇中每一個用戶請求查詢，然後依據每個用戶的真實位置篩選出真實結果，將其發送給各個用戶。

進一步，上述步驟1中所述匿名區域的半徑可以動態改變。

步驟2中匿名處理具體包含以下步驟：

步驟2-1、將整體的位置服務區域依據泰森多邊形的原理進行劃分，由此得到多個緊緊相臨的不規則的多邊形Pi(i＝1,2,3……)；

步驟2-2、匿名伺服器根據用戶請求消息M中的info判斷該用戶請求消息應該加入哪個服務請求簇，方法是判斷其所屬的泰森多邊形Pi，並加入到Pi所對應的簇cl[i]中，若能夠成功加入則跳轉至步驟2-5，否則執行步驟2-3；

步驟2-3、若此時要加入的服務請求簇不存在，則需要建立新的簇cl[i]；

步驟2-4、設Tout為最大的允許查詢時間，tnow為當前時間，當tnow-tiri則說明M的位置在簇的範圍外，執行步驟2-7；

步驟2-7、計算用戶請求消息M與當前cl[i]中存在的各個用戶請求消息間距離的最大值Lmax』＝MAX(Lmax,distance(location,location1),distance(location,location2),distance(location,location3),…,distance(location,locationn))，其中Lmax為當前用戶請求消息到來前求得的簇內最大距離，然後更新Lmax＝Lmax』；找到當前用戶請求消息M距離泰森多邊形內切圓最近的兩個切點A(ai,bi)與B(aj,bj)，連接消息M的位置點、兩個切點以及距離M為Lmax的點構成一個不規則的四邊形，作一個儘可能小的圓形域，標記此圓形域的圓心為Oi」(x,y)，半徑為ri」；當剩餘各用戶請求消息位置到Oi」的距離均小於等於ri」，則表示剩餘的請求消息在該圓內，跳轉至步驟2-9，否則跳轉至步驟2-8；

步驟2-8、當有若干用戶請求消息位於簇外，那麼可以依次測量這些用戶請求消息距離步驟2-7中所求四邊形的外接圓圓心Oi」的距離distance(Oi」,locationi)；假設此時用戶請求消息q的位置距離Oi」最遠，則以Oi」為圓心，此最遠距離distance(Oi」,q.location)為半徑rq做圓；設置一個默認的最大匿名區域範圍range，當rq≤range時，則圓心Oi＝Oi」，半徑ri＝rq，然後執行步驟2-9；當rq>range時，則判定超出匿名範圍並提示拒絕為該用戶請求消息服務，結束不再執行後續步驟；

步驟2-9、成功加入當前服務請求簇後，其用戶請求消息個數ni＝ni+1，並計算kmax』＝MAX(kmax,M.k)，當kmax』>ni時，則跳轉至步驟2-2繼續等待新的用戶請求消息的到來，否則該簇已達到匿名要求執行步驟2-10；

步驟2-10、匿名成功後，匿名伺服器發送一條含有匿名域ASR以及請求查詢信息的消息Q給LBS伺服器，等待LBS伺服器返回結果。

又進一步，上述步驟2-3中新簇cl[i]的內容包括：包含所有用戶請求消息所屬的泰森多邊形Pi，匿名域圓心Oi和相應半徑ri，泰森多邊形的最大內切圓的圓心Oi』和相應半徑ri』，匿名參數ki，簇中最大的用戶請求消息距離Lmax，簇中用戶請求消息的個數ni和相應的創建時間ti。

步驟2-7中所述圓形域至少外接這一四邊形的頂點，並且保證四個頂點均在圓形域內或邊界上。

步驟2-7中所述圓形域的計算方法為：連接該四邊形的兩條對角線，任意三個頂點構成了一個三角形，共四種三角形，選取其中外接圓半徑較小且包含三角形各頂點的那個圓，假設篩選出的三個頂點坐標分別為U(xu,yu)，V(xv,yv)，W(xw,yw)，則令a＝distance(U.location,V.location)，b＝distance(U.location,W.location)，c＝distance(V.location,W.location)，由海倫公式可以計算選中的三角形面積而該三角形外接圓的半徑由於(x-xu)2+(y-yu)2＝(x-xv)2+(y-yv)2＝(x-xw)2+(y-yw)2，所以可得到2(xv-xu)x+2(yv-yu)y＝-xu2+xv2-yu2+yv2，2(xw-xu)x+2(yw-yu)y＝-xu2+xw2-yu2+yw2，聯立二式可以得到外接圓圓心坐標

與現有技術相比，本發明的有益效果：

1，採用本發明的方法，在同一個泰森多邊形劃分的區域中，匿名伺服器將不同用戶的相同服務請求放入同一個簇中一併處理，從而提高了匿名處理的效率。

2，本發明不僅保護了用戶位置隱私，也針對匿名區域的劃分提出了全新的方案，在不降低服務質量的前提下，保證了計算出最優大小的匿名區域來實現隱私保護。

附圖說明

圖1為匿名處理的系統架構圖。

圖2為泰森多邊形形成圖。

圖3為規劃匿名域的生成圖。

圖4為基於泰森多邊形的針對相同服務請求位置隱私保護的匿名流程圖。

具體實施方式

現在結合附圖對本發明做進一步詳細的說明。

本發明包括如下步驟：

步驟1、查詢用戶以M＝(Uid,location,info,time,r,k)的六元組形式表示位於某一特定位置的用戶請求消息，其中Uid是發出請求的用戶的id號，location是用戶發出的請求位置在二維平面上的坐標(x,y)，info是表示請求查詢具體信息，time是表示用戶發出請求的時間，r是匿名區域的半徑(可動態改變)，k是指匿名參數。

步驟2、匿名伺服器收到用戶的請求消息M以後，將請求消息在所在的泰森多邊形中進行匿名處理，由此生成請求消息Q發送給LBS伺服器。

步驟3、根據收到的請求消息Q，LBS伺服器得到查詢結果S，並將其發送給匿名伺服器。

步驟4、匿名伺服器接收到查詢結果S後，對當前服務請求簇中每一個用戶請求查詢，然後依據每個用戶的真實位置篩選出真實結果，將其發送給各個用戶。

步驟2中的匿名處理涉及的匿名處理的系統架構圖如圖1所示，匿名處理的過程如圖4所示，包含以下具體步驟：

步驟2-1、將整體的位置服務區域依據泰森多邊形的原理進行劃分，由此得到多個緊緊相臨的不規則的多邊形Pi(i＝1,2,3……)。

步驟2-2、匿名伺服器根據用戶請求消息M中的info判斷該用戶請求消息應該加入哪個服務請求簇(同一服務請求簇中的用戶具有相同的服務請求)，方法是判斷其所屬的泰森多邊形Pi，並加入到Pi所對應的簇cl[i]中，若能夠成功加入則跳轉至步驟2-5，否則執行步驟2-3。

步驟2-3、若此時要加入的服務請求簇並不存在，則需要建立新的簇cl[i]，簇中的內容包括：包含所有用戶請求消息所屬的泰森多邊形Pi，匿名域圓心Oi(初始坐標為Oi』的坐標)和相應半徑ri(初始值為ri』)，泰森多邊形的最大內切圓的圓心Oi』和相應半徑ri』(作為初始的匿名域)，匿名參數ki，簇中最大的用戶請求消息距離Lmax，簇中用戶請求消息的個數ni(初始值為1)和相應的創建時間ti；

步驟2-4、設Tout為最大的允許查詢時間，tnow為當前時間，當tnow-tiri則說明M的位置在簇的範圍外，執行步驟2-7；

步驟2-7、計算用戶請求消息M與當前cl[i]中存在的各個用戶請求消息間距離的最大值Lmax』＝MAX(Lmax,distance(location,location1),distance(location,location2),distance(location,location3),…,distance(location,locationn))，其中Lmax為當前用戶請求消息到來前求得的簇內最大距離，然後更新Lmax＝Lmax』；找到當前用戶請求消息M距離泰森多邊形內切圓最近的兩個切點A(ai,bi)與B(aj,bj)，連接消息M的位置點、兩個切點以及距離M為Lmax的點構成一個不規則的四邊形，作一個儘可能小的圓形域(至少外接這一四邊形的頂點，並且保證四個頂點均在圓形域內或邊界上)，標記此圓形域的圓心為Oi」(x,y)，半徑為ri」。具體計算該圓形域的方法為：連接該四邊形的兩條對角線，任意三個頂點構成了一個三角形，共四種三角形，選取其中外接圓半徑較小且包含三角形各頂點的那個圓，假設篩選出的三個頂點坐標分別為U(xu,yu)，V(xv,yv)，W(xw,yw)，則令a＝distance(U.location,V.location)，b＝distance(U.location,W.location)，c＝distance(V.location,W.location)，由海倫公式可以計算選中的三角形面積而該三角形外接圓的半徑由於(x-xu)2+(y-yu)2＝(x-xv)2+(y-yv)2＝(x-xw)2+(y-yw)2，所以可得到2(xv-xu)x+2(yv-yu)y＝-xu2+xv2-yu2+yv2，2(xw-xu)x+2(yw-yu)y＝-xu2+xw2-yu2+yw2，聯立二式可以得到外接圓圓心坐標當剩餘各用戶請求消息位置到Oi」的距離均小於等於ri」，則表示剩餘的請求消息在該圓內，跳轉至步驟2-9，否則跳轉至步驟2-8；

步驟2-8、當有若干用戶請求消息位於簇外，那麼可以依次測量這些用戶請求消息距離步驟2-7中所求四邊形的外接圓圓心Oi」的距離distance(Oi」,locationi)；假設此時用戶請求消息q的位置(用q.location表示)距離Oi」最遠，則以Oi」為圓心，此最遠距離distance(Oi」,q.location)為半徑rq做圓；這裡設置一個默認的最大匿名區域範圍range，當rq≤range時，則圓心Oi＝Oi」，半徑ri＝rq，然後執行步驟2-9；當rq>range時，則判定超出匿名範圍並提示拒絕為該用戶請求消息服務，結束不再執行後續步驟；

步驟2-9、成功加入當前服務請求簇後，其用戶請求消息個數ni＝ni+1，並計算kmax』＝MAX(kmax,M.k)，當kmax』>ni時，則跳轉至步驟2-2繼續等待新的用戶請求消息的到來，否則該簇已達到匿名要求執行步驟2-10；

步驟2-10、匿名成功後，匿名伺服器發送一條含有匿名域ASR以及請求查詢信息的消息Q給LBS伺服器，等待LBS伺服器返回結果。

為便於本領域的技術人員進一步理解本發明的構思，現提供一個實施例。

小劉是某大學的一名在校大學生，這正逢周末，準備去周圍的咖啡廳小憩一下，於是在上午九點的時候在教一發出服務請求。假設這裡Uid是小劉的id號004，location為南京郵電大學仙林校區教一樓(以下簡稱「南郵教一」)，提出請求內容info為咖啡廳，提出請求時間time為9點，初始半徑r為50米，參數k為4。

因此，小劉以M＝(004,南郵教一,咖啡廳,9:00:00,50,4)的六元組形式表示其用戶請求消息，南郵教一在二維平面上的坐標為(x,y)。

步驟1、用戶發送用戶請求消息

小劉使用移動端查詢附近的咖啡廳，此時LBS伺服器需要知道小劉的位置信息在南郵教一，為了隱藏用戶的真實位置信息，將上述形式的用戶請求消息M發送給匿名伺服器。

步驟2、匿名伺服器對用戶請求消息M進行匿名處理，具體如下：

步驟2-1、匿名伺服器對於小劉發出請求的用戶位置和用戶查詢信息，確定合適的泰森多邊形區域，如圖2所示，P1為南師大，P2為金鷹商場與大成名店，P9為南財，P10為南郵，另外還有一些為周邊相關區域。選擇P10在此基礎上並進一步規劃恰當的匿名區域。

步驟2-2、在用戶請求消息M中的info參數為「咖啡廳」，提示了匿名伺服器該消息應歸屬的服務請求簇，再根據location參數確定所在的泰森多邊形P10及其初始匿名區域。當關鍵詞「咖啡廳」的服務請求簇cl[i]存在，假設此時匿名域圓心為Oi，其相應半徑為ri，另外有附近的小趙、小錢、小孫也發出同樣找尋咖啡廳的請求，此時在服務請求簇中請求消息的個數ni＝3，匿名參數k＝4，假設三人的用戶請求消息分別為M1＝(001,南郵圖書館,咖啡廳,8:59:55,50,2)，M2＝(002,南郵北操場,咖啡廳,8:59:57,50,4)，M3＝(003,南郵南三食堂,咖啡廳,8:59:51,50,3)。此時條件滿足，小劉的用戶請求消息M加入到該服務請求簇cl[i]中，跳過步驟2-3和步驟2-4，直接執行步驟2-5。

步驟2-5、由於此時簇中多於2個消息，所以直接執行步驟2-6；

步驟2-6、小劉的位置「南郵教一」到當前匿名域圓心Oi(xi,yi)的距離distance(南郵教一,假設distance(南郵教一,Oi)>ri，則表示小劉的位置在用戶請求簇外。

步驟2-7、計算小劉的請求消息M與cl[i]中小趙、小錢、小孫的請求消息間距離的最大值Lmax』＝MAX(Lmax,distance(南郵教一,南郵圖書館),distance(南郵教一,南郵北操場),distance(南郵教一,南郵南三食堂))，其中Lmax為當前用戶請求消息到來前求得的最大距離；假設Lmax』＝distance(南郵教一,南郵南三食堂)，即與消息M3所在位置的距離最近，然後更新Lmax＝Lmax』；如圖3所示，找到小劉的請求消息M距離泰森多邊形P10內切圓最近的兩個切點A(ai,bi)與B(aj,bj)，連接消息M的位置點、兩個切點以及M3構成一個不規則的四邊形AMBM3，作一個儘可能小的圓形域(至少外接這一四邊形的頂點，並且保證四個頂點均在圓形域內或邊界上)，標記此圓形域的圓心為Oi」(x,y)，半徑為ri」，具體計算該圓形域的方法為：連接該四邊形的兩條對角線，任意三個頂點構成了一個三角形，共四種三角形，選取其中外接圓半徑較小且包含各頂點的圓；假設篩選出的三個頂點坐標分別為小劉的位置點M(xm,ym)，切點B(xb,yb)與小孫位置點M3(xm3,ym3)，則令a＝distance(南郵教一,切點B)，b＝distance(切點B,南郵南三食堂)，c＝distance(南郵教一,南郵南三食堂)，假設a＝350m，b＝200m，c＝450m，由海倫公式可以計算選中的三角形面積而該三角形外接圓的半徑由於(x–xm)2+(y–ym)2＝(x–xb)2+(y–yb)2＝(x–xm3)2+(y–ym3)2，所以可得到2(xb–xm)x+2(yb–ym)y＝-xm2+xb2–ym2+yb2，2(xm3–xm)x+2(ym3–ym)y＝-xm2+xm32-ym2+ym32，聯立二式可以得到外接圓圓心坐標假設小趙用戶消息M1與小孫用戶消息M3到Oi」的距離小於234.79m，小錢用戶消息M2到Oi」的距離大於234.79m；

步驟2-8、由於M1與M3在圓內，M2在圓外，假設M2到Oi」的距離distance(Oi」,南郵北操場)＝236m，假設range＝250m，則以此236m為半徑做圓；

步驟2-9、此時服務請求簇中的用戶請求消息個數ni＝4，計算kmax』＝MAX(kmax,M.k)＝4，已達到匿名參數要求。

步驟2-10、匿名成功後，匿名伺服器發送一條含有匿名域ASR以及請求查詢信息的消息Q給LBS伺服器，等待LBS伺服器返回結果。

步驟3、匿名伺服器與LBS伺服器之間的交互通信

匿名伺服器將包含匿名域的消息Q與info發送給LBS伺服器，而LBS伺服器將查詢到的「仙林地區某些咖啡廳」的結果S返還給匿名伺服器。

步驟4、匿名伺服器分析真實查詢結果返回給用戶

匿名伺服器接收到查詢結果S之後，根據S對小劉的用戶請求消息M、小趙的用戶請求消息M1、小錢的用戶請求消息M2和小孫的用戶請求消息M3進行查詢，將真實結果分別返還給他們，由此四人均達到查詢目的。

應當理解，此處所描述的具體實例僅用以解釋本發明而不限定本發明，對於本領域的普通技術人員來說，在不脫離本發明原理的前提下，還可以做出若干變化，也應視為屬於本發明的保護範圍。