[發明專利]基于路網預測的長時請求位置隱私保護方法

有效

• 申請號: 201410126020.3
• 申請日: 2014-03-31
• 公開（公告）號: CN103957501B
• 公開（公告）日: 2017-04-19
• 發明（設計）人: 王祥;裴慶祺;姜炎;趙大為
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04W4/02
• 分類號: H04W4/02;H04W12/02
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 田文英,王品華

1.一種基于路網預測的長時請求位置隱私保護方法，包括如下步驟：

(1)建立道路網模型：

(1a)輸入路網預測服務地區的道路數據，將輸入的道路數據存貯于匿名服務器中；

(1b)統計一萬個用戶，在路網中通過同一個路口后選擇不同方向通行的用戶數，計算該路口不同方向的轉移概率，得到轉移概率矩陣，依此逐個得到所有路口的轉移概率矩陣；

(2)目標用戶發送請求：

(2a)目標用戶給匿名服務器發送位置信息、請求內容、匿名需求和回執時限；

(2b)對回執時限，以1分鐘的間隔等分為n個時刻；

(3)計算初始匿名面積：

(3a)提取當前時刻目標用戶以及該目標用戶周圍用戶的位置信息；

(3b)匿名服務器在路網上初始化一個矩形區域，作為匿名用戶群；

(3c)將目標用戶和離該目標用戶最近的一個用戶加入匿名用戶群，按照匿名用戶群面積公式，計算匿名用戶群面積；

(3d)判斷匿名用戶群的用戶數量是否滿足匿名需求，若是，執行步驟(3f)；否則，執行步驟(3e)；

(3e)將使匿名用戶群面積增加最小的用戶，加入到匿名用戶群中，更新匿名用戶群，每次增加一個用戶，直至匿名群滿足匿名需求；

(3f)按照匿名用戶群面積公式，計算匿名用戶群面積，將獲得的匿名用戶群面積作為初始匿名面積，存儲于匿名服務器中；

(4)預測最優時刻：

(4a)采用位置預測方法，預測下一時刻所有用戶的位置信息；

所述位置預測方法的具體步驟如下：

第一步，提取當前時刻待預測用戶的位置信息；

第二步，用待預測用戶位置信息中的速度與1分鐘時間相乘，得到待預測用戶的移動距離；

第三步，比較待預測用戶移動距離與待預測用戶到目的路口距離的大小，若待預測用戶移動距離大于待預測用戶到目的路口距離，則表示待預測用戶穿過路口，執行第四步，否則，認為待預測用戶未穿過路口，執行第六步；

第四步，將待預測用戶位置信息中的當前坐標更新為路口坐標；用待預測用戶移動距離減去待預測用戶到目的路口距離，將該距離差作為新的移動距離；

第五步，按照下式，計算不同方向位置信息中的概率，將求得的概率作為新的位置信息中的概率：

p＝p₀×p_i,j

其中，p表示待預測用戶穿過路口后位置信息中的概率，p₀表示待預測用戶穿過路口前位置信息中的概率，p_i,j表示待預測用戶從道路i走向道路j的概率；

第六步，用待預測用戶移動距離乘以運動方向的單位方向向量，得到待預測用戶的移動坐標向量，用待預測用戶當前時刻位置信息中的當前坐標加上待預測用戶的移動坐標向量，將得到的位置信息作為待預測用戶下一時刻的位置信息；

(4b)匿名服務器在路網上初始化一個新的矩形區域，作為預測匿名群；

(4c)將目標用戶和離該目標用戶最近的一個用戶加入預測匿名群，按照預測匿名群概率公式，計算預測匿名群的概率；

所述的預測匿名群概率公式如下：

其中，表示預測匿名群的概率，N表示預測匿名群總的用戶數，K表示匿名需求的用戶數，p_i，p_j，p_k，p_m分別表示第i，j，k，m個用戶位置信息的概率，∏表示將概率相乘再求和操作；

(4d)按照下式，計算預測匿名群周圍待加入用戶的效用值：

$B=\frac{\mathrm{\Δ}P}{\mathrm{\Δ}S}$

其中，B表示預測匿名群周圍待加入用戶的效用值，ΔP表示預測匿名群增加待加入用戶后預測匿名群概率的增加值，ΔS表示預測匿名群增加待加入用戶進入匿名群后預測匿名群面積的增加值；

(4e)依據預測匿名群周圍待加入用戶效用值的大小，依次選取效用值最小的用戶加入預測匿名群，更新預測匿名群，按照預測匿名群概率公式，計算新預測匿名群的概率；

所述的預測匿名群概率公式如下：

其中，表示預測匿名群的概率，N表示預測匿名群總的用戶數，K表示匿名需求的用戶數，p_i，p_j，p_k，p_m分別表示第i，j，k，m個用戶位置信息的概率，∏表示將概率相乘再求和操作；

(4f)將預測匿名群概率閾值設為0.8，當預測匿名群的概率小于0.8時，執行步驟(4d)；否則，認為該預測匿名群滿足匿名要求，執行步驟(4g)；

(4g)按照匿名用戶群面積公式，計算當前時刻預測匿名群的面積；

(4h)重復執行步驟(4a)至步驟(4g)，計算所有時刻的預測匿名群面積，將預測匿名群面積存儲于匿名服務器中；

(4i)比較初始匿名面積與預測匿名群面積的大小，當初始匿名面積大于任意一個預測匿名群的面積時，將當前時刻更新為下一時刻，執行步驟(3)；當初始匿名面積小于所有預測匿名群的面積時，執行步驟(5)；

(5)計算匿名區域面積：

采用匿名用戶群面積公式，計算當前時刻的匿名用戶群面積；將當前時刻的匿名用戶群所在的矩形區域，作為目標用戶的匿名區域；

(6)上傳信息并返回結果：

(6a)匿名服務器將目標用戶請求和該目標用戶的匿名區域，發送給服務商；

(6b)匿名服務器將從服務商獲得的查詢結果，返回給目標用戶。