侯占偉，楊 鑫，申自浩，王 輝，劉沛騫

（1.河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000；2.河南理工大學(xué) 軟件學(xué)院，河南 焦作 454000）

0 概述

近年來(lái)，隨著第4 代、第5 代通信技術(shù)以及智能移動(dòng)設(shè)備和衛(wèi)星定位技術(shù)的發(fā)展，基于位置的服務(wù)（Location Based Services，LBS）得到了廣泛的應(yīng)用，與之相關(guān)的資源也變得更加豐富［1-2］。LBS 可以在娛樂、商業(yè)、衛(wèi)生、辦公、緊急情況等不同領(lǐng)域提供多種服務(wù)。然而，為了獲得LBS 帶來(lái)的便利，移動(dòng)用戶必須向基于位置的服務(wù)提供商（Location Services Provider，LSP）公開實(shí)際位置。但位置信息不僅可以展示用戶的經(jīng)緯度，也可以被攻擊者用來(lái)進(jìn)行跟蹤和分析進(jìn)而得到關(guān)于用戶的敏感信息，如家庭地址、用戶習(xí)慣、健康狀況以及宗教信仰［3-4］。他們違法收集的信息可能被用于各種非法活動(dòng)，導(dǎo)致用戶聲譽(yù)受損。

為防止位置隱私信息的泄露，國(guó)內(nèi)外眾多該領(lǐng)域的學(xué)者提出了多種位置隱私保護(hù)方法，大致可以分為位置泛化、位置擾動(dòng)和位置加密3 大類。位置泛化［5］利用空間匿名技術(shù)來(lái)實(shí)現(xiàn)，通過(guò)使用該技術(shù)，移動(dòng)用戶的真實(shí)位置將會(huì)隱藏在匿名空間區(qū)域內(nèi)。但是匿名區(qū)域的大小會(huì)成為限制該技術(shù)發(fā)展的瓶頸。當(dāng)生成的匿名區(qū)域面積過(guò)大時(shí)，不僅方案的時(shí)間開銷會(huì)增加，查詢的準(zhǔn)確性也會(huì)大打折扣；而當(dāng)生成的匿名區(qū)域面積過(guò)小時(shí)，隱私保護(hù)的質(zhì)量將會(huì)下降，容易被攻擊者識(shí)破。位置擾動(dòng)［6-7］是利用具有一定偏移量的位置或者假位置來(lái)代替用戶的真實(shí)位置，這樣攻擊者或服務(wù)器就無(wú)法獲得用戶的真實(shí)位置。但是對(duì)于某些攻擊者而言，他們具備一定的背景知識(shí)，通過(guò)推理可以輕易排除掉用戶生成的一些假位置。在這種情況下如何生成隱私保護(hù)度高的假位置成為研究的熱點(diǎn)。位置加密［8-9］是利用各種密碼學(xué)技術(shù)對(duì)移動(dòng)用戶的位置數(shù)據(jù)進(jìn)行加密，在沒有相關(guān)密鑰的情況下無(wú)法獲取用戶的位置信息。盡管使用加密算法在一定程度上提高了用戶的位置隱私保護(hù)效果，但其算法流程大多過(guò)于復(fù)雜且計(jì)算量較大，導(dǎo)致運(yùn)行開銷大幅增加。

以上方法在面對(duì)背景知識(shí)攻擊、語(yǔ)義攻擊等方面存在局限性，而且沒有對(duì)綜合因素進(jìn)行考量，隱私泄露風(fēng)險(xiǎn)較高。為更好地保護(hù)移動(dòng)用戶的位置隱私，本文提出基于多屬性決策模型的匿名集構(gòu)造（Multi-attribute Decision Model-based Anonymous Set Construction，MDMASC）算法。通過(guò)分析個(gè)體用戶和群體用戶軌跡位置點(diǎn)的規(guī)律，在本文提出的語(yǔ)義敏感等級(jí)、位置普遍度、語(yǔ)義跨度等多個(gè)屬性層面進(jìn)行綜合考量。使用層次分析法（Analytic Hierarchy Process，AHP）分析各屬性間的關(guān)系，合理確定權(quán)重。此外，使用多屬性決策方法，經(jīng)綜合決策選出最佳假位置，構(gòu)建具有不可區(qū)分性的安全匿名集。

1 相關(guān)工作

在眾多位置隱私保護(hù)的方案中，大多數(shù)學(xué)者都致力于研究如何生成與真實(shí)位置區(qū)分度高、隱私保護(hù)效果好的假位置。KIDO 等［10］提出使用假位置來(lái)實(shí)現(xiàn)位置隱私保護(hù)，其主要思想是將用戶的真實(shí)位置與眾多假位置組成匿名集一起發(fā)送給LSP。這種方法不需要第3 方匿名服務(wù)器加入，避免了因匿名服務(wù)器的信任問(wèn)題或匿名服務(wù)器遭受攻擊而導(dǎo)致的隱私泄露風(fēng)險(xiǎn)，但由于其沒有考慮查詢概率等因素，因此容易遭到具有背景知識(shí)的邊信息攻擊。

考慮攻擊者挖掘用戶的歷史請(qǐng)求信息，NIU等［11］提出了深度學(xué)習(xí)搜索（Deep Learning Search，DLS）算法，該算法根據(jù)地圖上位置單元的歷史查詢信息計(jì)算得到歷史查詢概率，其次使用熵度量安全性，最終選擇符合其要求的假位置構(gòu)造匿名集。由于需要大量計(jì)算匿名集的熵值，致使該算法時(shí)間復(fù)雜度較高，在某些資源受限的通訊設(shè)備上使用時(shí)難以實(shí)現(xiàn) 很好的 隱私保 護(hù)效果。SUN 等［12］在DLS 的基礎(chǔ)上，通過(guò)分析攻擊算法ADLS，提出DLP 算法。該算法在時(shí)間復(fù)雜度和用戶隱私要求之間進(jìn)行了權(quán)衡，在一定程度上具有較好的隱私保護(hù)效果，但是其忽略了山川、湖泊等歷史查詢概率為零的位置單元。楊洋等［13］提出K-DLS 算法，該算法在考慮到位置單元?dú)v史查詢概率為0 的同時(shí)改善了假位置的分布情況，生成的匿名集具有較高的位置熵值，提升了位置隱私保護(hù)的安全性。然而在保護(hù)用戶位置隱私的過(guò)程中，若攻擊者采用語(yǔ)義攻擊等手段時(shí)，僅考慮位置單元的歷史查詢概率顯然是不夠的。

針對(duì)攻擊者掌握移動(dòng)用戶位置點(diǎn)的語(yǔ)義信息，文獻(xiàn)［14］提出的方案考慮了用戶訪問(wèn)地點(diǎn)的語(yǔ)義信息，對(duì)用戶的隱私保護(hù)需求予以滿足，但是其未考慮位置分布對(duì)假位置集的影響，預(yù)期的隱私保護(hù)效果在遭受位置同質(zhì)性攻擊時(shí)往往難以達(dá)到。王潔等［15］提出了MMDS 算法，該算法通過(guò)位置語(yǔ)義樹計(jì)算各位置間的語(yǔ)義差，同時(shí)考慮了假位置的查詢概率和地理分布，根據(jù)以上這3 個(gè)維度生成假位置，在衡量位置間的語(yǔ)義差異性上提供了思路。但是，在興趣點(diǎn)（Point of Interest，POI）類別較少的地區(qū)，語(yǔ)義樹的子節(jié)點(diǎn)較少，而該算法僅通過(guò)位置語(yǔ)義篩選假位置，隱私保護(hù)效果較差。文獻(xiàn)［16］使用了多屬性決策的思想來(lái)選取假位置，根據(jù)歷史查詢概率、物理距離和語(yǔ)義多樣性構(gòu)建匿名集。但其沒有衡量各因素間的相對(duì)重要關(guān)系，同時(shí)考慮因素過(guò)少，未對(duì)綜合因素進(jìn)行考量，用戶的隱私保護(hù)強(qiáng)度不夠高。

針對(duì)同一位置點(diǎn)，不同用戶對(duì)其敏感程度不同。值得一提的是敏感位置的信息大多與用戶身份相關(guān)聯(lián)。當(dāng)攻擊者定位到某一用戶的敏感位置點(diǎn)時(shí)，將極大可能推測(cè)出該用戶的身份。YIN 等［17］提出了一種基于位置敏感度劃分的位置數(shù)據(jù)安全保護(hù)方法。該方法對(duì)位置敏感度級(jí)別進(jìn)行分類，基于此分配隱私預(yù)算，有效地保護(hù)了用戶的位置隱私。LIU 等［18］基于隨機(jī)匿名區(qū)域的概念提出了一種RSABPP 算法，各個(gè)區(qū)域具有不同敏感值，對(duì)手將難以通過(guò)推斷匿名用戶的敏感度去識(shí)別真實(shí)位置。

本文提出MDMASC 算法，綜合考慮用戶真實(shí)位置所具有的背景知識(shí)等信息，使其在不同的場(chǎng)景下具備適應(yīng)性，有效地降低攻擊者在擁有用戶行為規(guī)律、位置語(yǔ)義等背景知識(shí)情況下用戶真實(shí)位置被識(shí)別的風(fēng)險(xiǎn)。

2 預(yù)備知識(shí)

2.1 語(yǔ)義樹

為了從現(xiàn)實(shí)生活中細(xì)化出興趣點(diǎn)類型，根據(jù)目前主流地圖軟件（如百度地圖、高德地圖）和當(dāng)下比較流行的LBS 應(yīng)用程序（如大眾點(diǎn)評(píng)、貓途鷹）去獲取到當(dāng)前地圖中所有位置單元和相關(guān)的POI，并總結(jié)了吃、住、行、玩、游、生活和購(gòu)物這7 種位置類型。根據(jù)獲得的相關(guān)信息建立一棵語(yǔ)義樹（Stree），該樹具有4 層結(jié)構(gòu)，根節(jié)點(diǎn)為本地地圖，第2 層為基本屬性，第3 層為次屬性，葉子節(jié)點(diǎn)為地圖上具有特定POI 的真實(shí)位置，S-tree 的示意圖如圖1所示。

圖1 S-tree 示意圖Fig.1 Schematic diagram of S-tree

2.2 相關(guān)定義

定義1隱私要求：移動(dòng)用戶個(gè)性化的隱私需求，表示為req(k,q1,q2)，其中k是匿名度，q1，q2分別是用戶事先設(shè)定的假位置距真實(shí)位置的最小距離和最大距離。

定義2邊信息：地圖上不同的位置點(diǎn)都具有邊信息，攻擊者擁有邊信息有助于推斷移動(dòng)用戶的真實(shí)位置［19］。本文中的邊信息是指位置單元的歷史查詢概率、POI 類型等信息。顯然，用戶具有這樣的信息，有助于其選擇最優(yōu)假位置。

定義3歷史查詢概率pi：將地圖劃分成網(wǎng)格，不同網(wǎng)格代表不同的位置單元，歷史查詢概率由用戶過(guò)去訪問(wèn)該位置單元的概率表示。查詢概率的計(jì)算式如下：

其中：Ni表示網(wǎng)格劃分后位置單元i的歷史查詢次數(shù)表示所有位置單元的歷史查詢次數(shù)之和。

定義4位置地理距離d：本文采用Haversine 公式來(lái)計(jì)算兩位置點(diǎn)間的地理距離。本文計(jì)算地理距離只是用來(lái)在構(gòu)建匿名集時(shí)使用，所得出的結(jié)果不涉及到更深層次的應(yīng)用，使用Haversine 公式能在保證精度足夠使用的前提下減少時(shí)間開銷。Haversine公式如下：

由式（2）化簡(jiǎn)可得：

定義5POI 評(píng)分Si：在LBS 的應(yīng)用程序中，例如yelp！和大眾點(diǎn)評(píng)，每個(gè)POI 的打分值基于歷史用戶對(duì)該P(yáng)OI 的打分和評(píng)判，故而每個(gè)POI 的分值影響著用戶的選擇意愿。

定義6語(yǔ)義敏感等級(jí)Li：表示用戶根據(jù)位置語(yǔ)義信息所定義的不同敏感度級(jí)別。其用來(lái)判別位置敏感程度，分為一級(jí)、二級(jí)、三級(jí)和四級(jí)，敏感程度隨等級(jí)的升高而增強(qiáng)。語(yǔ)義敏感等級(jí)由用戶事先設(shè)定，它是選取假位置的重要依據(jù)。

定義7位置普遍度Di：如果單個(gè)位置在某一特定用戶軌跡數(shù)據(jù)集中出現(xiàn)的頻率較高，而在其他用戶的軌跡數(shù)據(jù)集中很少出現(xiàn)，那么對(duì)于攻擊者而言，該位置具有很好的類別區(qū)分能力，根據(jù)該位置極易推測(cè)出用戶的身份。根據(jù)TF-IDF 技術(shù)［20］定義位置普遍度，位置li的位置普遍度可以表示為：

定義8語(yǔ)義跨度語(yǔ)義跨度是S-tree 中l(wèi)i和lj兩個(gè)位置對(duì)應(yīng)的葉子節(jié)點(diǎn)之間需要經(jīng)歷的跳數(shù)［21］。語(yǔ)義跨度是衡量候選假位置優(yōu)劣的重要指標(biāo)，其大小通過(guò)S-tree 計(jì)算。

3 基于多屬性決策模型的匿名集構(gòu)建算法

假位置的選擇過(guò)程具有多維度、多屬性的特點(diǎn)，屬于多屬性決策的范疇。假位置的選擇需要從多方面考慮，最終構(gòu)建不可區(qū)分性高、位置熵大的匿名集，盡最大可能降低用戶真實(shí)位置被識(shí)別的概率。在多屬性決策理論中，層次分析法在信息安全領(lǐng)域已被用于社交媒體隱私安全量化評(píng)估研究、構(gòu)建泄露數(shù)據(jù)價(jià)值評(píng)估模型等實(shí)際工作，具有良好的效果。因此本文采用多屬性決策模型對(duì)假位置選擇問(wèn)題進(jìn)行研究，且其中用到了層次分析法來(lái)計(jì)算各評(píng)價(jià)指標(biāo)的屬性權(quán)重。

3.1 系統(tǒng)架構(gòu)

本文提出的基于多屬性決策模型的假位置集構(gòu)建算法是基于用戶移動(dòng)終端，采用分布式的系統(tǒng)架構(gòu)，如圖2 所示。因?yàn)樵摷軜?gòu)沒有第3 方服務(wù)器參與，所以有效避免了單點(diǎn)泄露等問(wèn)題的出現(xiàn)。本文系統(tǒng)架構(gòu)主要由3 個(gè)實(shí)體組成，即移動(dòng)終端、通信基站和LBS 服務(wù)器，具體介紹如下：

圖2 系統(tǒng)架構(gòu)Fig.2 System architecture

1）移動(dòng)終端。移動(dòng)終端用來(lái)執(zhí)行本文提出的多屬性決策方法，接著發(fā)送安全匿名集進(jìn)行查詢，最后在查詢結(jié)果集中選擇自己所需結(jié)果。各位置點(diǎn)的坐標(biāo)由移動(dòng)終端設(shè)備通過(guò)覆蓋全球的衛(wèi)星定位系統(tǒng)獲取。

2）通信基站。通信基站為移動(dòng)終端設(shè)備提供網(wǎng)絡(luò)通信服務(wù)，同時(shí)對(duì)其覆蓋范圍內(nèi)所有位置的歷史查詢概率進(jìn)行計(jì)算并存儲(chǔ)。如今通信基站不僅信號(hào)覆蓋面廣，而且其計(jì)算和存儲(chǔ)信息的能力也較強(qiáng)，故可以實(shí)現(xiàn)本文所需功能。

3）LBS 服務(wù)器。LBS 服務(wù)器用于接收用戶的位置服務(wù)請(qǐng)求，并返回查詢結(jié)果，為用戶提供位置服務(wù)。

3.2 多屬性決策模型的構(gòu)建與求解

多屬性決策也稱有限方案多目標(biāo)決策，即綜合考慮多種屬性來(lái)選擇最優(yōu)備選方案，在當(dāng)今決策科學(xué)中占據(jù)重要地位［22］。移動(dòng)用戶向LBS 服務(wù)器提交不同查詢內(nèi)容的假位置以及用戶的真實(shí)位置，并請(qǐng)求獲取相關(guān)服務(wù)信息。S-tree 為本文方案建立了基本的前提。這里采用基于加權(quán)算術(shù)平均（WAA）算子的多屬性決策方法來(lái)進(jìn)行假位置的選取。

3.2.1 基于WAA 算子的多屬性決策方法

WAA 算子對(duì)決策矩陣每行中的各個(gè)數(shù)據(jù)按照權(quán)重值進(jìn)行集結(jié)，以此來(lái)評(píng)估方案的優(yōu)劣。其定義如下：

設(shè)WAA：Rn→R，若存在WAAw(α1,α2,…,αn)=其 中，w=(w1,w2,…,wn)是(α1,α2,…,αn)的加權(quán)向量，則稱WAA 是加權(quán)算術(shù)平均算子。

明確WAA 算子的定義后，下面給出決策步驟：

步驟1確定本文所提方法的決策目標(biāo)，明確方案集與指標(biāo)屬性集。本文的決策目標(biāo)為選擇符合用戶隱私保護(hù)要求的最佳假位置來(lái)構(gòu)建安全匿名集。設(shè)CLS 和U 分別為方案集和指標(biāo)屬性集。CLS=(l1,l2,…,ln)是候選假位置集，w=(w1,w2,w3,w4,w5)為決策者對(duì)5 個(gè)屬性給出的屬性權(quán)重。

步驟2對(duì)于任一位置li，根據(jù)不同屬性的類型計(jì)算相應(yīng)的屬性值aij，從而構(gòu)建決策矩陣A=(aij)n×m。由于各屬性間量綱不同，因此需要對(duì)矩陣A進(jìn)行歸一化處理。歸一化矩陣A后得到A'=

步驟3確定本文定義的各屬性之間的優(yōu)先級(jí)，利用層次分析法賦予與之對(duì)應(yīng)的權(quán)重。

步驟4候選假位置集中各位置點(diǎn)在各目標(biāo)下屬性值已知時(shí)，通過(guò)WAA 算子對(duì)規(guī)范化矩陣A'中的第i行(i=1,2,…,m)數(shù)據(jù)進(jìn)行計(jì)算，得到假位置的li綜合屬性值

3.2.2 決策矩陣的建立及歸一化處理

多屬性決策解決特定問(wèn)題中重要的一環(huán)就是建立決策矩陣，在本文選擇假位置問(wèn)題上有m個(gè)備選假位置l1,l2,…,lm，5 個(gè)影響匿名集安全性的因素，包括屬性POI 評(píng)分、地理距離、語(yǔ)義敏感等級(jí)、語(yǔ)義跨度、位置普遍度。利用查詢概率初次篩選后得到的假位置集，根據(jù)假位置li對(duì)各屬性的取值建立決策矩陣A，如表1 所示。

表1 決策矩陣Table 1 Decision matrix

多屬性決策的前提是決策需要根據(jù)多個(gè)屬性值來(lái)進(jìn)行，這其中屬性的類型一般有效益型、成本型、固定型、偏離型、區(qū)間型等，各類型的計(jì)算方法具體如下。

1）效益型。屬性值越大越好，計(jì)算式如式（5）所示：

2）成本型。屬性值越小越好，計(jì)算式如式（6）所示：

3）固定型。屬性值與設(shè)定的固定值α間的差值越小越好，計(jì)算式如式（7）所示：

4）偏離型。屬性值與設(shè)定的固定值β間的差值越大越好，計(jì)算式如式（8）所示：

5）區(qū)間型。屬性值越接近設(shè)定的區(qū)間[q1,q2]越好，計(jì)算式如式（9）所示：

根據(jù)位置隱私保護(hù)的需要，將前面2.2 節(jié)定義的各種屬性的類型進(jìn)行分類。選取的假位置的POI 評(píng)分越高越具有真實(shí)性，較高的評(píng)分能達(dá)到更好的保護(hù)效果，故將POI 評(píng)分歸類為效益型；根據(jù)用戶在隱私需求中設(shè)定的假位置距真實(shí)位置的最小距離和最大距離，將地理距離歸類為區(qū)間型；為了抵制基于位置語(yǔ)義等信息的語(yǔ)義攻擊，選取的假位置與真實(shí)位置的語(yǔ)義應(yīng)盡量不同，即語(yǔ)義跨度的值越大越具有迷惑性，能達(dá)到更好的保護(hù)效果，故將語(yǔ)義跨度歸類為效益型；對(duì)于語(yǔ)義敏感等級(jí)較高的位置點(diǎn)，用戶顯然是不想暴露給他人的，而對(duì)于等級(jí)較低的位置點(diǎn)用戶是不敏感的，所以將語(yǔ)義敏感等級(jí)歸類為成本型；對(duì)于各位置點(diǎn)，在大眾數(shù)據(jù)集中出現(xiàn)越多，位置普遍度越低，反之位置普遍度越高，應(yīng)該選擇相對(duì)普遍的位置來(lái)構(gòu)造安全匿名集，所以將位置普遍度歸類為成本型。

在確定各屬性的類型后對(duì)決策矩陣A進(jìn)行歸一化，歸一化處理后的決策矩陣如表2 所示。

表2 歸一化處理后的決策矩陣Table 2 The normalized decision matrix

使用假位置生成技術(shù)構(gòu)建匿名集的傳統(tǒng)方法大多只考慮單個(gè)或少數(shù)指標(biāo)屬性對(duì)匿名集安全性的影響，未實(shí)現(xiàn)綜合因素的考量，在不同程度上具有局限性，無(wú)法應(yīng)對(duì)多種攻擊手段?；诖?，本文定義了多個(gè)指標(biāo)屬性，根據(jù)歷史查詢概率過(guò)濾掉與真實(shí)位置概率不相似的位置，有效避免了遭受基于背景知識(shí)的邊信息攻擊。在決策的指標(biāo)屬性集中加入地理距離改善位置分布，避免遭受位置同質(zhì)攻擊。定義語(yǔ)義跨度實(shí)現(xiàn)匿名集中假位置所包含語(yǔ)義信息的多樣性，降低在遭受語(yǔ)義攻擊時(shí)隱私泄露的風(fēng)險(xiǎn)。本文方案也考慮了各候選假位置的語(yǔ)義敏感等級(jí)、POI評(píng)分和位置普遍度，這三者在提高安全匿名集中各假位置真實(shí)性的同時(shí)增強(qiáng)了其與真實(shí)位置的不可區(qū)分性。綜上所述，本文方法實(shí)現(xiàn)了綜合因素的考量，在保護(hù)用戶的位置隱私方面具有完備性。

3.2.3 層次分析法計(jì)算屬性權(quán)重

層次分析法［23］通過(guò)分析每?jī)蓚€(gè)屬性之間的關(guān)系構(gòu)建成對(duì)比較矩陣，根據(jù)要實(shí)現(xiàn)的目標(biāo)把問(wèn)題分解成不同層次，經(jīng)過(guò)比較和計(jì)算，從而較為合理地確定各屬性的權(quán)重。在本文基于AHP 的位置隱私評(píng)價(jià)體系的構(gòu)建中，主要有以下4 個(gè)步驟：

步驟1層次分析法首先對(duì)問(wèn)題進(jìn)行層次化處理，依據(jù)問(wèn)題的本質(zhì)及要實(shí)現(xiàn)的總目標(biāo)將問(wèn)題分解成不同的組成要素，按要素之間從屬關(guān)系和相互間的聯(lián)系形成多層次分析結(jié)構(gòu)模型。本文將語(yǔ)義跨度、位置普遍度、語(yǔ)義敏感等級(jí)、地理距離和POI 評(píng)分這5 個(gè)影響匿名集安全性的因素作為選取假位置的主要依據(jù)。圖3 給出了本文提到的多種屬性的層次結(jié)構(gòu)模型，該圖建立了3 個(gè)層次結(jié)構(gòu)，分別是目標(biāo)層、準(zhǔn)則層和方案層。

“按行消元，逐行規(guī)格化”的計(jì)算過(guò)程決定了其不適合應(yīng)用對(duì)角元以右元素與對(duì)角元以下元素的對(duì)稱性進(jìn)行計(jì)算，因?yàn)樵谶@種計(jì)算方式下，對(duì)第i行元素進(jìn)行消元，要通過(guò)賦值分別或者一次性地得到其對(duì)角元以左的第1～i-1個(gè)元素就顯得極為不便。因此這種計(jì)算方式對(duì)A陣元素的前代過(guò)程有大量的多余計(jì)算，從而導(dǎo)致計(jì)算效率不高。如果僅計(jì)算包括對(duì)角元素的上三角元素或包括對(duì)角元素的下三角元素，而通過(guò)對(duì)稱性來(lái)獲得另一半元素，則由于上下三角元素的不等，在對(duì)A陣或F陣元素的前代過(guò)程中會(huì)出現(xiàn)大量乘或除對(duì)角元素的重復(fù)計(jì)算，同樣影響計(jì)算效率。

圖3 層次結(jié)構(gòu)圖Fig.3 Hierarchy diagram

步驟2層次分析法要求使用者在每?jī)蓚€(gè)指標(biāo)間比較兩者的相對(duì)重要程度，根據(jù)其重要性的量化值，進(jìn)而構(gòu)造出成對(duì)比較矩陣。本文采用表3 所示的1-9 標(biāo)度來(lái)評(píng)估每?jī)蓚€(gè)屬性間的相對(duì)重要性。

表3 指標(biāo)相對(duì)重要性等級(jí)Table 3 Index relative importance level

根據(jù)表3 對(duì)5 個(gè)屬性構(gòu)建成對(duì)比較矩陣B5×5，B5×5=aij(i,j=1,2,3,4,5)，其 中aij為屬性i相比于屬性j的重要程度。

步驟3為了確保最終結(jié)果的科學(xué)性和可靠性，需要對(duì)該矩陣進(jìn)行一致性檢驗(yàn)。一致性檢驗(yàn)的標(biāo)準(zhǔn)為當(dāng)CR<0.1 時(shí)，說(shuō)明成對(duì)比較矩陣通過(guò)了一致性檢驗(yàn)。CR的計(jì)算式如式（10）所示：

其中：CI指標(biāo)的計(jì)算如式（11）所示，RI為與n對(duì)應(yīng)的平均隨機(jī)一致性取值。

其中：λmax為成對(duì)比較矩陣的最大特征根；n為矩陣的階數(shù)。λmax的計(jì)算式如式（12）所示：

由式（12）計(jì)算可得到成對(duì)比較矩陣B的最大特征根λmax，進(jìn)而求得CI。根據(jù)表4 得出當(dāng)n=5 時(shí)RI=1.12。當(dāng)CR<0.1 時(shí)，說(shuō)明該矩陣通過(guò)了一致性檢驗(yàn)。

表4 隨機(jī)一致性指標(biāo)RI 的數(shù)值Table 4 Value of stochastic consistency indicator RI

步驟4在矩陣通過(guò)一致性檢驗(yàn)之后，根據(jù)成對(duì)比較矩陣計(jì)算出w1到w5的屬性權(quán)重。本文為了獲取較為理想的權(quán)重準(zhǔn)確度，根據(jù)對(duì)位置隱私的了解和參與程度，選取該領(lǐng)域多名教授組成專家組，對(duì)其進(jìn)行問(wèn)卷調(diào)查后得到各指標(biāo)之間的相對(duì)重要程度，并分別構(gòu)建成對(duì)比較矩陣。接著依據(jù)群決策數(shù)據(jù)集結(jié)方式中的結(jié)果權(quán)重加權(quán)算術(shù)平均法得到地理距離、語(yǔ)義跨度、POI 評(píng)分、位置普遍度、語(yǔ)義敏感等級(jí)的屬性權(quán)重依次為0.068 8、0.324 5、0.048 3、0.315 4、0.242 9。

值得一提的是，權(quán)重值越大的指標(biāo)，說(shuō)明其對(duì)匿名集安全性的影響越強(qiáng)，與其他屬性的差異也越大。某候選假位置在這些屬性值高的情況下，經(jīng)多屬性決策被選為最優(yōu)假位置的可能性也較高。

3.3 算法描述

本文提出MDMASC 算法，該算法充分考慮了多個(gè)維度的影響因素對(duì)假位置安全性的影響，最后構(gòu)造出一組包含用戶真實(shí)位置且大小為k的安全匿名集SAS。該算法的主要流程如圖4 所示。

圖4 MDMASC 算法的流程Fig.4 Procedure of MDMASC algorithm

下面給出了本文算法的偽代碼表示。

算法1MDMASC 算法

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

本文使用真實(shí)數(shù)據(jù)集GeoLife［24］來(lái)進(jìn)行實(shí)驗(yàn)仿真。該數(shù)據(jù)集包含了不同用戶大量的軌跡數(shù)據(jù)，其中不僅包括上下班通勤、購(gòu)物等日常生活常規(guī)的生活軌跡，還包括餐飲、就醫(yī)、健身、登山等遍及不同領(lǐng)域的戶外活動(dòng)軌跡。數(shù)據(jù)集中大部分軌跡都是在中國(guó)北京市創(chuàng)建的，市區(qū)已經(jīng)被通信基站全面覆蓋且擁有大批的移動(dòng)用戶，各用戶的軌跡數(shù)據(jù)集中都包含不同位置點(diǎn)的緯度、經(jīng)度，使用這些位置點(diǎn)信息作為用戶的歷史信息來(lái)計(jì)算歷史查詢概率。

實(shí)驗(yàn)選用數(shù)據(jù)集中北京市中心城區(qū)10 km×10 km 矩形區(qū)域內(nèi)位置地理信息，將樣本空間均勻劃分為100×100 個(gè)位置單元。將得到的樣本軌跡點(diǎn)作為歷史數(shù)據(jù)，基于此來(lái)計(jì)算網(wǎng)格劃分后各位置單元的歷史查詢概率。為了得到S-tree 中的各個(gè)節(jié)點(diǎn)，從谷歌地圖API 和大眾點(diǎn)評(píng)中收集，得到7 548 個(gè)葉子節(jié)點(diǎn)。

實(shí)驗(yàn)運(yùn)行的環(huán)境是Intel?CoreTMi5-9300H 2.40 GHz 處理器，16 G 內(nèi)存的Windows10 操作系統(tǒng)。實(shí)驗(yàn)參數(shù)如表5 所示。

表5 實(shí)驗(yàn)參數(shù)Table 5 Experimental parameters

4.2 結(jié)果分析

實(shí)驗(yàn)從匿名集生成時(shí)間、語(yǔ)義多樣性、攻擊算法識(shí)別概率以及位置熵這4 個(gè)方面評(píng)估本文算法，并將其與同樣使用假位置生成技術(shù)的DLP 算法［12］、MMDS 算法［15］、K-DLS 算法［13］進(jìn)行比較。

4.2.1 匿名集生成時(shí)間

構(gòu)建匿名集的一個(gè)重要指標(biāo)就是匿名集的生成時(shí)間，本文算法的時(shí)間開銷主要集中在多個(gè)指標(biāo)值的計(jì)算上。圖5 為本文算法與DLP 算法、MMDS 算法和K-DLS 算法的實(shí)驗(yàn)結(jié)果對(duì)比，其中圖5（a）為不同算法生成匿名集的平均時(shí)間對(duì)比。由圖5（a）可以看出，4 種算法構(gòu)建匿名集所需要的時(shí)間均隨著匿名度k的增加而增多。當(dāng)k較小時(shí)，幾種算法假位置生成時(shí)間相差無(wú)幾。隨著匿名度k的增加，DLP 算法假位置生成時(shí)間最少，MDMASC 算法次之，另外兩種算法所需時(shí)間高于本文算法，MDMASC 算法相對(duì)于MMDS 算法降低了約10.3%的時(shí)間開銷。由于DLP算法在構(gòu)建匿名集時(shí)沒有考慮到語(yǔ)義信息，故運(yùn)行時(shí)間最少，而本文算法在考慮各位置單元查詢概率的同時(shí)還要進(jìn)行語(yǔ)義跨度、語(yǔ)義敏感等級(jí)等多種屬性的決策過(guò)程，需要消耗一定的時(shí)間，因此其匿名集生成時(shí)間略高于DLP 算法。

圖5 不同算法的實(shí)驗(yàn)結(jié)果對(duì)比Fig.5 Comparison of experimental results of different algorithms

4.2.2 語(yǔ)義多樣性比較

采用文獻(xiàn)［15］提出的θ-安全值評(píng)估算法提交匿名集的語(yǔ)義多樣性，θ-安全值越大表示構(gòu)建的匿名集中各假位置所屬的語(yǔ)義信息越豐富，攻擊者越難確定用戶的真實(shí)位置。圖5（b）為本文算法與DLP算法、MMDS 算法和K-DLS 算法的語(yǔ)義多樣性對(duì)比。

由圖5（b）可以看出，隨著匿名度k的增加，MMDS 算法的θ值變化幅度最小且維持在較高的水平。本文算法的θ值也能維持在相對(duì)較高水平，可以滿足語(yǔ)義多樣性的要求。但本文算法略低于MMDS 算法，這是因?yàn)镸MDS 只關(guān)注了位置語(yǔ)義對(duì)匿名集的影響，而本文算法在構(gòu)建安全匿名集時(shí)雖然也考慮了位置語(yǔ)義，但是語(yǔ)義信息并不是構(gòu)建安全匿名集的唯一標(biāo)準(zhǔn)，在現(xiàn)實(shí)生活中的不同場(chǎng)景下顯然本文算法更具實(shí)用性。DLP 算法和K-DLS 算法的θ值均處于相對(duì)較低水平，這是因?yàn)樗鼈冊(cè)跇?gòu)建匿名集時(shí)只關(guān)注了查詢概率，沒有注意到選取的假位置可能與用戶真實(shí)位置具有相同語(yǔ)義信息的情況。

4.2.3 攻擊算法識(shí)別概率

盡管用戶提交了匿名集，但是仍存在被攻擊算法識(shí)別的可能，用戶的真實(shí)位置被攻擊算法識(shí)別的概率Q的計(jì)算式如下：

其中：C是根據(jù)假位置生成算法得到的匿名集，C={l1,l2,…,lk}，|Cnum|=k。

為了對(duì)比考慮位置語(yǔ)義信息、語(yǔ)義敏感度等屬性對(duì)用戶真實(shí)位置保護(hù)的優(yōu)勢(shì)，采用式（13）度量匿名集的安全性，將本文算法與DLP 算法、MMDS 算法和K-DLS 算法在語(yǔ)義攻擊下被識(shí)別的概率進(jìn)行對(duì)比，結(jié)果如圖5（c）所示。

由圖5（c）可以看出，隨著匿名度k逐漸增大，各算法被攻擊算法識(shí)別的概率逐漸降低，這是由于匿名集擴(kuò)大導(dǎo)致其中各假位置間的語(yǔ)義差異性逐漸減小，攻擊者使用語(yǔ)義攻擊的成功率更高。DLP 算法和K-DLS 算法在選取假位置時(shí)未考慮位置語(yǔ)義信息對(duì)匿名集安全性的影響，所以隱私保護(hù)效果較差，在攻擊算法下的位置識(shí)別率高于另外兩種算法。盡管MMDS 算法關(guān)注了位置語(yǔ)義信息，但其對(duì)位置敏感程度等屬性未做分析，衡量結(jié)果不夠精確。

本文算法的被識(shí)別概率要略低于其他3 種算法，比MMDS 算法和K-DLS 算法分別降低了14.9%和25.5%。這是因?yàn)橛脩粼跇?gòu)建安全匿名集時(shí)，不僅考慮了歷史查詢概率，也考慮到了位置普遍程度、語(yǔ)義信息以及各用戶設(shè)定的不同敏感等級(jí)等屬性對(duì)其安全性的影響。攻擊者在進(jìn)行語(yǔ)義攻擊的同時(shí)即使具備邊信息也難以提高推測(cè)概率，同時(shí)本文算法對(duì)不同用戶在位置敏感等級(jí)的設(shè)定上滿足了個(gè)人需求，體現(xiàn)了一定的個(gè)性化。

4.2.4 位置熵

應(yīng)用文獻(xiàn)［25］中的位置熵度量位置隱私保護(hù)的有效性。位置熵值與匿名化程度呈正相關(guān)，兩者的變化具有同向性，熵值越大，匿名化程度越高。圖5（d）為本文 方法與DLP 算 法、MMDS 算法和K-DLS 算法在不同匿名度下生成匿名集的位置熵對(duì)比。

由圖5（d）可以看出，隨著匿名度k的增加，各算法的位置熵值都在增大。但是不難發(fā)現(xiàn)本文算法的位置熵提升幅度要高于另外3 種算法，這是因?yàn)樵跇?gòu)建安全匿名集時(shí)本文算法綜合考慮了假位置的位置語(yǔ)義、位置普遍度、位置敏感程度等多種屬性值可能對(duì)匿名安全性造成的影響，增強(qiáng)了用戶真實(shí)位置的不確定性，匿名集的安全性得到了保障，有利于用戶位置隱私的保護(hù)。

5 結(jié)束語(yǔ)

本文提出的MDMASC 算法綜合考慮位置所具有的多種因素來(lái)構(gòu)建安全匿名集所需的假位置。通過(guò)歷史查詢概率判斷得到構(gòu)建候選假位置集，對(duì)定義的5 個(gè)屬性值進(jìn)行數(shù)據(jù)預(yù)處理，通過(guò)分析屬性間的關(guān)系確定屬性權(quán)重，最終進(jìn)行綜合決策以篩選出最優(yōu)假位置。實(shí)驗(yàn)分別從匿名集生成時(shí)間、語(yǔ)義多樣性、攻擊算法識(shí)別概率、位置熵等4 個(gè)方面將本文算法與DLP 算 法、MMDS 算 法、K-DLS 算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果顯示，使用本文MDMASC 算法構(gòu)建的安全匿名集位置熵值更高，能夠生成區(qū)分度高、合理性強(qiáng)的安全匿名集。然而本文只是在單位置點(diǎn)上研究了隱私保護(hù)，未考慮位置隨時(shí)間的變化問(wèn)題，而在短時(shí)間內(nèi)用戶位置大多以軌跡呈現(xiàn)，因此下一步將通過(guò)研究用戶軌跡的隱私保護(hù)，從而完善隱私保護(hù)方案。