多級(jí)敏感區(qū)域室內(nèi)定位中的隱私保護(hù)算法

摘 要：隨著城市智能化發(fā)展，室內(nèi)定位技術(shù)已成為各類位置服務(wù)的重要應(yīng)用基礎(chǔ)。在一些室內(nèi)應(yīng)用場(chǎng)景中，服務(wù)器端需要在保護(hù)用戶位置隱私的前提下，完成特定區(qū)域的用戶訪問(wèn)統(tǒng)計(jì)。為此，提出了一種基于布隆過(guò)濾器和Paillier同態(tài)加密的多級(jí)敏感區(qū)域室內(nèi)定位算法，旨在保護(hù)用戶位置隱私的同時(shí)服務(wù)器能判斷用戶是否進(jìn)入特定區(qū)域。算法根據(jù)區(qū)域的類別或敏感級(jí)別對(duì)室內(nèi)進(jìn)行劃分，利用Paillier算法對(duì)服務(wù)器端和用戶端的數(shù)據(jù)進(jìn)行加密，設(shè)計(jì)了一種改進(jìn)的基于布隆過(guò)濾器的算法在密文域完成用戶位置的判定，減少了加密運(yùn)算帶來(lái)的巨大通信開銷與計(jì)算開銷。在公共數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與已有的空間布隆過(guò)濾器算法相比，提出的哈希數(shù)組合并算法在同樣的通信和計(jì)算開銷時(shí)具有更低的誤判率，也可擴(kuò)展至其他應(yīng)用中實(shí)現(xiàn)多類數(shù)據(jù)集的編碼。

關(guān)鍵詞： 位置隱私；布隆過(guò)濾器；Paillier同態(tài)加密；誤判率

中圖分類號(hào)： TP391文獻(xiàn)標(biāo)志碼：A 文章編號(hào)： 1001－3695（2024）04－033－1184－07

doi： 10.19734/j.issn.1001－3695.2023.06.0349

Privacy preserving algorithm in indoor localization of multilevel sensitive areas

Song Weiran， Huang Xinyi， Le Yanfen

Abstract：With the development of urban intelligence， indoor positioning has become an important application basis for providing various location－based services. In some indoor application scenarios， the server－side needs to perform user access statistics for specific areas while ensuring the protection of user location privacy. To address this， this paper proposed a multi－level sensitive area indoor positioning algorithm based on Bloom filter and Paillier homomorphic encryption， aiming to protect user location privacy while enabling the server to judge whether a user had entered a sensitive area. The algorithm divided the indoor space based on the sensitivity level or category of areas， encrypted the data on the server－side and user－side using the Paillier algorithm， and designed an improved Bloom filter－based algorithm in the ciphertext domain to accomplish user location determination， thereby reducing the significant communication overhead and computational cost introduced by encryption ope－rations. Experimental results on public data sets show that compared with existing spatial Bloom filter algorithms， the proposed hash array merging algorithm has a lower 1 positive probability with the same communication and computation overhead， and can also be extended to other applications to realize multi－class data set coding. Key words：location privacy; Bloom filter; Paillier homomorphic encryption; 1 positive probability

0 引言

隨著移動(dòng)無(wú)線系統(tǒng)的快速發(fā)展，人們對(duì)基于位置的服務(wù)（LBS）產(chǎn)生了極大的興趣。在室內(nèi)應(yīng)用環(huán)境中，基于Wi－Fi的指紋定位成為L(zhǎng)BS領(lǐng)域的重要支撐技術(shù)。由于Wi－Fi指紋定位方法無(wú)須增加額外的硬件設(shè)施、定位系統(tǒng)布局方便且具有較高的定位精度，所以被廣泛應(yīng)用于室內(nèi)定位［1，2］。

指紋定位技術(shù)通常利用室內(nèi)Wi－Fi信號(hào)信息來(lái)實(shí)現(xiàn)用戶定位［3～5］。該技術(shù)通常涉及服務(wù)器端和客戶端兩個(gè)系統(tǒng)。服務(wù)器端需在定位監(jiān)測(cè)區(qū)域部署大量的參考點(diǎn)（reference point，RP），并在這些RP位置采集各接入點(diǎn)（access point，AP）的接收信號(hào)強(qiáng)度（received signal strength indicator，RSSI）作為離線指紋存儲(chǔ)在數(shù)據(jù)庫(kù)中?？蛻舳送ㄟ^(guò)移動(dòng)終端實(shí)時(shí)采集自身位置處來(lái)自各AP的RSSI指紋信號(hào)，并上傳給服務(wù)器端；后者利用相關(guān)定位算法將客戶端的RSSI信號(hào)與離線指紋數(shù)據(jù)庫(kù)進(jìn)行計(jì)算匹配，從而確定用戶的估計(jì)位置。

在用戶請(qǐng)求定位服務(wù)過(guò)程中，服務(wù)器可以持續(xù)收集用戶的位置信息，包括用戶在特定時(shí)刻所處的位置、曾經(jīng)到過(guò)的地方或頻繁訪問(wèn)的區(qū)域等。通過(guò)對(duì)這些位置信息的深入分析，可進(jìn)一步獲取用戶的行為習(xí)慣、生活模式、社會(huì)關(guān)系甚至健康狀況等隱私。若這些信息被惡意利用，則用戶的隱私可能會(huì)受到侵犯。例如，定位數(shù)據(jù)可能被用來(lái)追蹤用戶的行蹤、收集用戶的興趣偏好或?qū)⑵湮恢眯畔⑴c其他數(shù)據(jù)庫(kù)進(jìn)行關(guān)聯(lián)分析等。因此，需要采取措施保證定位服務(wù)中的位置隱私安全［6］。目前，國(guó)內(nèi)外學(xué)者已提出了許多解決室內(nèi)定位過(guò)程中隱私保護(hù)問(wèn)題的方法，主要可以分為匿名化和脫敏技術(shù)［7～9］、差分隱私［9，10］和加密法［11～13］等。而在其中一些應(yīng)用場(chǎng)景中，用戶已經(jīng)獲得自身位置信息，在不暴露用戶位置隱私的前提下，服務(wù)器要實(shí)現(xiàn)對(duì)特定區(qū)域用戶訪問(wèn)的統(tǒng)計(jì)。例如，在某些室內(nèi)定位場(chǎng)景中（如醫(yī)院、場(chǎng)館、商店等），可能存在一些特定的空間區(qū)域，只允許特定授權(quán)人員進(jìn)入； 或服務(wù)器需要在匿名狀態(tài)下完成對(duì)特定區(qū)域的用戶訪問(wèn)的統(tǒng)計(jì)等。本文將這些區(qū)域定義為敏感區(qū)域。服務(wù)器端可根據(jù)服務(wù)需求設(shè)定敏感區(qū)域。在這些區(qū)域中，定位相關(guān)信息的存儲(chǔ)和計(jì)算等操作都需要采取相應(yīng)的安全措施，使得用戶從服務(wù)器獲得具有隱私保護(hù)定位服務(wù)的同時(shí)，服務(wù)器能對(duì)特定位置的用戶進(jìn)行監(jiān)控。文獻(xiàn)［14～16］提出了一種基于布隆過(guò)濾器的空間數(shù)據(jù)結(jié)構(gòu)（spatial Bloom filter，SBF），與傳統(tǒng)的布隆過(guò)濾器（Bloom filter，BF）不同，SBF在一個(gè)過(guò)濾器中編碼不同的集合并對(duì)其進(jìn)行擴(kuò)展，通過(guò)哈希，每個(gè)集合對(duì)應(yīng)的BF通過(guò)覆蓋合并的形式最終構(gòu)成一個(gè)BF。當(dāng)需要查詢用戶是否在給定的空間范圍時(shí)，根據(jù)用戶的坐標(biāo)確定其所在的單元格，經(jīng)過(guò)哈希處理后可在該BF中檢查是否存在該單元格。該方法可實(shí)現(xiàn)用戶隱私保護(hù)時(shí)的特點(diǎn)區(qū)域查詢，但SBF采用的數(shù)據(jù)覆蓋合并的形式會(huì)使高等級(jí)敏感區(qū)域覆蓋低等級(jí)敏感區(qū)域，從而導(dǎo)致對(duì)低等級(jí)敏感區(qū)域的誤判。為解決此問(wèn)題，本文提出了一種融合Paillier同態(tài)加密與布隆過(guò)濾器的隱私保護(hù)算法，服務(wù)器在不知道用戶位置的情況下，可判定其是否進(jìn)入特定敏感區(qū)域。相較于傳統(tǒng)的利用加密算法實(shí)現(xiàn)用戶位置隱私保護(hù)，本文算法在計(jì)算和通信方面的開銷也有了大幅度降低，且所設(shè)計(jì)的哈希數(shù)組合并算法的誤判率比SBF算法更低。

1 相關(guān)工作

1.1 位置隱私

位置隱私概念由Beresford等人［6］于2003年提出后，相關(guān)的隱私保護(hù)技術(shù)逐漸成為信息技術(shù)領(lǐng)域的熱門研究課題。匿名化和脫敏技術(shù)在處理用戶的位置數(shù)據(jù)時(shí)，通過(guò)刪除或替換敏感數(shù)據(jù)防止指紋定位與具體用戶的身份相關(guān)聯(lián)。文獻(xiàn)［7］對(duì)用戶的經(jīng)緯度坐標(biāo)位置泛化為一個(gè)區(qū)間區(qū)域，并使用Geohash算法編碼；篩選多余位置時(shí)兼顧歷史查詢概率，再附上k-1個(gè)偽查詢以混淆用戶的真實(shí)查詢內(nèi)容，最終實(shí)現(xiàn)k匿名位置隱私保護(hù)。差分隱私通過(guò)在發(fā)布的數(shù)據(jù)中引入一定的噪聲，以防止惡意用戶從中推斷出個(gè)體的敏感信息，其代價(jià)則是數(shù)據(jù)失真帶來(lái)的定位性能的部分下降。文獻(xiàn)［10］針對(duì)當(dāng)用戶在發(fā)起位置查詢請(qǐng)求時(shí)可能會(huì)泄露當(dāng)前的精確位置這一問(wèn)題，提出了一種基于位置熵的差分隱私保護(hù)方法，并對(duì)查詢結(jié)果進(jìn)行優(yōu)化處理；另外針對(duì)數(shù)據(jù)分布不均勻、查詢范圍較小的情況，提出了基于差分隱私和K－means的位置數(shù)據(jù)發(fā)布方法。加密法通過(guò)對(duì)位置數(shù)據(jù)使用加密技術(shù)來(lái)保護(hù)數(shù)據(jù)。文獻(xiàn)［12］使用Paillier同態(tài)加密對(duì)服務(wù)器和用戶的RSSI指紋信號(hào)進(jìn)行加密，利用其同態(tài)特性對(duì)其密文數(shù)據(jù)進(jìn)行數(shù)據(jù)的處理和傳送，可保護(hù)敏感數(shù)據(jù)的機(jī)密性和完整性，防止未經(jīng)授權(quán)的訪問(wèn)和竄改定位指紋。但加密算法通常會(huì)增加計(jì)算和處理的復(fù)雜性，特別是在大規(guī)模數(shù)據(jù)場(chǎng)景中，無(wú)法保證應(yīng)用的實(shí)時(shí)性。上述相關(guān)研究工作涉及的位置隱私，其主要應(yīng)用場(chǎng)景為用戶不知曉自身所在位置，需向服務(wù)器端請(qǐng)求定位服務(wù)。在此過(guò)程中，用戶要保證不泄露自身位置相關(guān)信息，同時(shí)服務(wù)器端也會(huì)盡力保護(hù)數(shù)據(jù)庫(kù)信息。本文工作的應(yīng)用場(chǎng)景為用戶已經(jīng)通過(guò)上述研究方法獲得自身位置，服務(wù)器端需判斷用戶是否進(jìn)入特定敏感區(qū)域。為達(dá)到位置隱私，這一過(guò)程中服務(wù)器需在隱私狀態(tài)下完成對(duì)用戶的位置查詢，即當(dāng)用戶進(jìn)入特定敏感區(qū)域時(shí)，服務(wù)器能完成對(duì)該用戶的訪問(wèn)統(tǒng)計(jì)，而當(dāng)用戶不在這些區(qū)域，此過(guò)程不會(huì)泄露用戶的任何位置信息，且用戶也無(wú)法獲知服務(wù)器對(duì)敏感區(qū)域的設(shè)定。 本文也利用了Paillier算法的同態(tài)特性，完成用戶位置與敏感區(qū)域的隱私匹配，在不泄露兩者數(shù)據(jù)信息的前提下，服務(wù)器端可判斷用戶是否進(jìn)入敏感區(qū)域。但是這種方法一般需要進(jìn)行大數(shù)運(yùn)算，計(jì)算開銷大，對(duì)用戶終端硬件設(shè)備的要求也較高。 為解決上述問(wèn)題，本文采用BF對(duì)數(shù)據(jù)進(jìn)行處理，以減少加密過(guò)程需要的計(jì)算開銷和數(shù)據(jù)傳輸時(shí)的通信開銷。同時(shí)通過(guò)對(duì)SBF進(jìn)一步改進(jìn)，消除了其高級(jí)敏感區(qū)域覆蓋低級(jí)敏感區(qū)域而產(chǎn)生對(duì)低級(jí)敏感區(qū)域誤判的弊端，誤判率也得到了進(jìn)一步降低。

1.2 布隆過(guò)濾器（BF）

布隆過(guò)濾器是一種基于哈希函數(shù)的數(shù)據(jù)結(jié)構(gòu)，可以快速判斷一個(gè)元素是否屬于某個(gè)集合，常用于大規(guī)模數(shù)據(jù)集的去重、緩存預(yù)熱等場(chǎng)景。通常布隆過(guò)濾器會(huì)使用多個(gè)哈希函數(shù)對(duì)集合中的元素進(jìn)行哈希，并在一個(gè)m位數(shù)組中用1標(biāo)記這些哈希值對(duì)應(yīng)的位置。在查詢時(shí)，如果數(shù)組中一個(gè)元素的所有哈希值對(duì)應(yīng)的位都被標(biāo)記為1，則該元素可能存在于集合中；如果有任意一個(gè)哈希值對(duì)應(yīng)的位為0，則該元素一定不存在于集合中［14～16］。

布隆過(guò)濾器在緩存、安全和網(wǎng)絡(luò)協(xié)議等領(lǐng)域得到廣泛應(yīng)用，本文將BF生成數(shù)據(jù)結(jié)構(gòu)的方法應(yīng)用于多級(jí)敏感區(qū)域室內(nèi)定位，不僅滿足隱私保護(hù)還可以減少計(jì)算開銷和通信開銷。

1.3 Paillier半同態(tài)加密

同態(tài)加密是一種滿足密文同態(tài)運(yùn)算性質(zhì)的加密算法，即在明文數(shù)據(jù)中要進(jìn)行的計(jì)算，可在通過(guò)同態(tài)加密后的密文數(shù)據(jù)中運(yùn)算實(shí)現(xiàn)。本文使用的加密算法為Paillier半同態(tài)加密算法，具有加同態(tài)和標(biāo)量積同態(tài)特性，能夠在不解密的情況下完成數(shù)據(jù)的加運(yùn)算和數(shù)乘運(yùn)算，具體可表示為

2.3 多級(jí)敏感區(qū)域室內(nèi)定位方案服務(wù)器端解密

用戶將密文數(shù)據(jù)［ ［X·Y］］傳給服務(wù)器端，服務(wù)器解密后若X·Y數(shù)值為0，表示用戶不屬于任何敏感區(qū)域；數(shù)值為g，則表示用戶位于第g級(jí)敏感區(qū)域，解密的數(shù)值指示了用戶所處的敏感區(qū)域級(jí)別；而當(dāng)用戶不在這些敏感區(qū)域時(shí)，解密后的值為0，服務(wù)器未獲得有關(guān)用戶位置的任何信息。

2.4 多級(jí)敏感區(qū)域室內(nèi)定位方案缺點(diǎn)及改進(jìn)方案

值得一提的是，當(dāng)服務(wù)器端數(shù)據(jù)庫(kù)中RP數(shù)量較多時(shí)，服務(wù)器端與用戶端之間的計(jì)算和通信開銷會(huì)非常大。對(duì)于需要精確室內(nèi)定位的場(chǎng)景（如醫(yī)院、機(jī)場(chǎng)等），這些數(shù)據(jù)庫(kù)往往采集大量的RP數(shù)據(jù)，導(dǎo)致敏感區(qū)域數(shù)組X長(zhǎng)度增加，使得服務(wù)器需要更多的計(jì)算開銷完成對(duì)數(shù)組的加密，同時(shí)把［ ［X］］傳遞給用戶端需要更多的通信成本。雖然大量RP可以提高定位精度，但是方案的可行性應(yīng)綜合考慮計(jì)算和通信開銷因素。

通過(guò)將若干數(shù)據(jù)庫(kù)RP形成RP塊，再對(duì)RP塊進(jìn)行敏感區(qū)域劃分構(gòu)建X的方法可以顯著減少服務(wù)器端生成密文數(shù)組的長(zhǎng)度，從而降低計(jì)算和通信開銷。圖2給出了數(shù)據(jù)庫(kù)劃分RP塊判定用戶是否進(jìn)入敏感區(qū)域的方案。從方案的實(shí)施過(guò)程可發(fā)現(xiàn)，這種基于PR塊的判定方式存在一個(gè)缺點(diǎn)，即服務(wù)器端需要向用戶傳遞RP塊分布信息，以便用戶根據(jù)自身的估計(jì)位置確定所處的RP塊。雖然用戶端無(wú)法了解RP塊中的具體信息，但這仍然會(huì)泄露一部分信息給用戶端，從而對(duì)室內(nèi)定位的隱私保護(hù)造成影響。

為了解決大量RP計(jì)算和通信開銷大的問(wèn)題，可以采用文獻(xiàn)［14～16］所提的SBF方法，對(duì)處于不同敏感區(qū)域的RP進(jìn)行相同的哈希，由一個(gè)對(duì)應(yīng)各RP的b數(shù)組來(lái)表征處于不同敏感區(qū)域的RP。該方案采用高級(jí)覆蓋低級(jí)敏感區(qū)域的方式，可減小b數(shù)組的總體長(zhǎng)度，由此降低計(jì)算開銷和通信開銷。但該方案會(huì)使服務(wù)器誤判用戶所處的敏感區(qū)域等級(jí)，同時(shí)也存在一定的誤判率，把未處于任何敏感區(qū)域的用戶判定為進(jìn)入一高等級(jí)敏感區(qū)域。

針對(duì)這些問(wèn)題，本文提出了一種改進(jìn)方案。該方案在具有較低計(jì)算和通信開銷的同時(shí)，不會(huì)產(chǎn)生不同敏感區(qū)域混淆誤判，并降低了用戶進(jìn)入敏感區(qū)域的誤判率。

3 改進(jìn)方案

改進(jìn)方案利用BF僅對(duì)敏感區(qū)域中的RP信息建立映射關(guān)系，因此服務(wù)器端生成的數(shù)組長(zhǎng)度會(huì)大大減小，從而可以減少加密的計(jì)算開銷和服務(wù)器到用戶的通信開銷； 同時(shí)提出了一種新穎的哈希數(shù)組合并的方式來(lái)解決多級(jí)敏感區(qū)域的誤判問(wèn)題。改進(jìn)方案（novel Bloom filter based scheme，NBF）流程如圖3所示。

3.1 基于NBF的多級(jí)敏感區(qū)域室內(nèi)定位服務(wù)器端

服務(wù)提供商按照不同級(jí)別敏感區(qū)域劃分?jǐn)?shù)據(jù)庫(kù)中RP，對(duì)每個(gè)敏感區(qū)域內(nèi)的所有RP通過(guò)BF生成一個(gè)哈希數(shù)組Xg。Xg的長(zhǎng)度為m′，初始化為0。設(shè)RP i是第g級(jí)敏感區(qū)域RP集合Δg中的元素，該RP i通過(guò)哈希后獲得k個(gè)哈希值，則數(shù)組Xg的這k個(gè)哈希值對(duì)應(yīng)的位置元素置為敏感區(qū)域級(jí)別g；對(duì)Δg內(nèi)的所有RP元素進(jìn)行類似操作，可獲得哈希數(shù)組Xg ={x1，g，…，xm′，g}。

若定位服務(wù)區(qū)內(nèi)存在G個(gè)等級(jí)的敏感區(qū)域，則對(duì)每個(gè)等級(jí)敏感區(qū)域的RP集合完成BF后，服務(wù)器端生成G個(gè)哈希數(shù)組X …， XG。其中哈希數(shù)組Xg中第i個(gè)值為

其中：g為敏感區(qū)域等級(jí)；Δg為第g級(jí)敏感區(qū)域RP集合；B（Δg）是對(duì)應(yīng)RP集合Δg的布隆過(guò)濾器。

為保留每級(jí)敏感區(qū)域內(nèi)各RP的信息，同時(shí)又不增加加密的數(shù)據(jù)量，本文提出了一種哈希數(shù)組合并的方式。

算法的一個(gè)實(shí)例如圖4所示。圖中服務(wù)器端將敏感區(qū)域由低到高分為三級(jí)，相應(yīng)的RP集分別是Δ1、Δ2、Δ3，其中Δ1為圖中的9個(gè)藍(lán)色區(qū)域，Δ2為圖中的4個(gè)橘色區(qū)域，Δ3為圖中的1個(gè)紅色區(qū)域（見電子版）。對(duì)各級(jí)敏感區(qū)域中RP集合經(jīng)過(guò)BF（哈希函數(shù)個(gè)數(shù)k=3）生成三個(gè)哈希數(shù)組，分別是

在SBF中，通過(guò)哈希值覆蓋合并的方式，服務(wù)器端最終得到的X=［1，2，3，3，1，2，3，1，0，1，…］， 此時(shí)因?yàn)槊舾袇^(qū)域等級(jí)中3級(jí)最高，1級(jí)最低，數(shù)組中相應(yīng)位置發(fā)生碰撞時(shí)優(yōu)先存儲(chǔ)最高值，覆蓋較低值，這樣除了BF本身具有的誤判性，即把不在敏感區(qū)域的用戶誤判在敏感區(qū)，同時(shí)還會(huì)造成用戶位于較低優(yōu)先級(jí)敏感區(qū)域時(shí)被誤判到高優(yōu)先級(jí)敏感區(qū)域。

本文則采用了數(shù)組對(duì)應(yīng)位置元素進(jìn)行合并的方式，最終獲得X=［001，020，300，321，001，020，300，001，000，001，…］。由于Paillier加密的密鑰長(zhǎng)度通常為1 024 bit，甚至更長(zhǎng)，所以合并后的元素仍可以正常加密。

其中：Y為用戶端哈希數(shù)組；1fk表示數(shù)組中位置fk的元素設(shè)為1。

用戶端通過(guò)算法1和式（10）進(jìn)行密文域點(diǎn)積運(yùn)算：

其中：g為敏感區(qū)域級(jí)別；Eg為當(dāng)敏感區(qū)域?yàn)間時(shí)在明文數(shù)據(jù)X·Y中按位分裂獲得的數(shù)據(jù)；k為哈希函數(shù)個(gè)數(shù)。

當(dāng)滿足式（21）時(shí)，可判斷用戶已經(jīng)進(jìn)入敏感區(qū)域g，當(dāng)?shù)仁讲怀闪r(shí)，則可判斷用戶不在敏感區(qū)域內(nèi)。

對(duì)上述算法過(guò)程進(jìn)行實(shí)例化，如圖5所示。圖中服務(wù)器端敏感區(qū)域G=4，對(duì)應(yīng)哈希數(shù)組為4個(gè)（從低到高敏感區(qū)域?qū)?yīng)的哈希數(shù)組分別是藍(lán)色、黃色、紫色、紅色，參見電子版），BF中哈希函數(shù) k=6。根據(jù)式（14）得出，當(dāng)合并數(shù)組X時(shí)，各敏感區(qū)域數(shù)組中元素各占用X中元素的2個(gè)十進(jìn)制位數(shù)（W=2），合并數(shù)組中各元素需要8個(gè)十進(jìn)制位數(shù)（WX=8）。當(dāng)用戶根據(jù)自己所處的位置獲得的哈希數(shù)組Y中不為0元素位置下標(biāo)為 2， 5， 6， 7， 9時(shí)，根據(jù)式（20）對(duì)合并數(shù)組X中相應(yīng)位置下標(biāo)中元素進(jìn)行模乘運(yùn)算，獲得［ ［X·Y］］，并傳遞給服務(wù)器端；服務(wù)器端解密后利用式（21）進(jìn)行判斷，最終紫色區(qū)域（3級(jí)敏感區(qū)域）中數(shù)值為18，滿足式（21），可以判斷出用戶處于第3級(jí)敏感區(qū)域內(nèi)。

4 改進(jìn)方案性能分析

4.1 誤判率分析

本實(shí)驗(yàn)中多級(jí)敏感區(qū)域?qū)?yīng)的RP集合使用相同的k個(gè)哈希數(shù)組，各級(jí)敏感區(qū)域哈希數(shù)組的誤判率公式與SBF［14～16］中的計(jì)算公式并不相同。本文中各級(jí)敏感區(qū)域生成的哈希數(shù)組誤判率為

通過(guò)采用BF對(duì)敏感區(qū)域中RP信息進(jìn)行映射，結(jié)合哈希數(shù)組合并，使得原本需要加密和傳輸?shù)臄?shù)據(jù)量從整個(gè)監(jiān)控區(qū)域內(nèi)參考點(diǎn)數(shù)量m減少到敏感區(qū)域內(nèi)各級(jí)的RP映射后的向量長(zhǎng)度m′。這個(gè)長(zhǎng)度由誤判率決定，通常情況下m′遠(yuǎn)小于m。例如，在本文的后續(xù)實(shí)驗(yàn)中，將數(shù)組長(zhǎng)度從397減少到200，極大地降低了計(jì)算和通信開銷，同時(shí)也確保了數(shù)據(jù)隱私得到有效保護(hù)。

4.2 安全性分析

4.2.1 用戶端隱私安全

在本文方案中，服務(wù)器經(jīng)解密后獲得的是用戶自身位置經(jīng)哈希后的哈希數(shù)組Y與服務(wù)器端的哈希數(shù)組X的點(diǎn)積，其實(shí)際是服務(wù)器端哈希數(shù)組中k個(gè)元素值的和。由這個(gè)點(diǎn)積并不能夠確定用戶端在哈希數(shù)組中具體的不為0數(shù)據(jù)所在的位置。若用戶沒(méi)有進(jìn)入敏感區(qū)域，則更無(wú)法建立非敏感區(qū)域位置與內(nèi)積和的對(duì)應(yīng)關(guān)系。只有當(dāng)用戶進(jìn)入敏感區(qū)域時(shí)，按照算法的設(shè)計(jì)，服務(wù)器端才能產(chǎn)生正確響應(yīng)；另外，即使用戶進(jìn)入敏感區(qū)域，服務(wù)器端也只能獲得用戶處于敏感區(qū)域的類別，并不知道用戶處于敏感區(qū)域的確切位置。因此，用戶端的個(gè)人位置隱私是安全的。

4.2.2 服務(wù)器端隱私安全

在進(jìn)行用戶訪問(wèn)統(tǒng)計(jì)時(shí)，服務(wù)器端會(huì)將合并后的哈希數(shù)組加密后傳輸給用戶，采用Paillier加密算法可保證用戶在沒(méi)有相應(yīng)的密鑰時(shí)，無(wú)法破譯密文獲得各敏感區(qū)域?qū)?yīng)的合并哈希數(shù)組，僅僅只有將獲得的密文數(shù)據(jù)和自身數(shù)據(jù)進(jìn)行密文域運(yùn)算的權(quán)力。因此，服務(wù)器端的數(shù)據(jù)庫(kù)隱私是安全的。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 實(shí)驗(yàn)環(huán)境建立

為了驗(yàn)證本文提出的基于隱私保護(hù)的敏感區(qū)域室內(nèi)定位算法的有效性和可行性，在實(shí)驗(yàn)中使用了公共數(shù)據(jù)集數(shù)據(jù)［18］，其面積約為44 m×15 m，用于驗(yàn)證算法的可行性。實(shí)驗(yàn)場(chǎng)景布局如圖6所示。在圖6中，藍(lán)色圓點(diǎn)代表RP的位置，紅色三角形代表測(cè)試點(diǎn)即用戶的位置（見電子版）。在公共數(shù)據(jù)集中，共有397個(gè)RP和34個(gè)用戶測(cè)試點(diǎn)。

對(duì)公共數(shù)據(jù)集的敏感區(qū)域進(jìn)行了劃分，如圖7所示。

5.2 NBF與SBF誤判率比較

在本實(shí)驗(yàn)中，公共數(shù)據(jù)集1～3級(jí)敏感區(qū)域RP集合Δ1～Δ3中元素個(gè)數(shù)分別為24、16、8。根據(jù)式（5）可知，數(shù)組長(zhǎng)度m′增大可以降低誤判率，但m′增大同時(shí)意味著服務(wù)器需要傳遞更多加密數(shù)據(jù)到用戶端，這會(huì)增大通信和計(jì)算開銷；哈希函數(shù)個(gè)數(shù)k增大到最佳值的過(guò)程中，誤判率逐漸降低，當(dāng)k值從最佳值再次增加時(shí)，誤判率又會(huì)逐漸升高，而服務(wù)器端和用戶端因k增大導(dǎo)致產(chǎn)生的哈希值個(gè)數(shù)增多同樣會(huì)導(dǎo)致計(jì)算開銷略微增大。根據(jù)實(shí)驗(yàn)中的敏感區(qū)域元素個(gè)數(shù)，圖8給出了數(shù)組X取不同長(zhǎng)度和不同哈希函數(shù)個(gè)數(shù)k時(shí)NBF和SBF的誤判率。當(dāng)哈希函數(shù)個(gè)數(shù)k分別為3、5、7、9時(shí)，從圖中的誤判率曲線可知，當(dāng)數(shù)組長(zhǎng)度越大，誤判率越低。綜合考慮算法的性能，在本實(shí)驗(yàn)中選取數(shù)組長(zhǎng)度m′為200，此時(shí)NBF誤判率為0.001 4～0.027 6，而SBF誤判率為0.135 2～0.386 4。

圖9、10給出了X長(zhǎng)度m′為200，哈希函數(shù)個(gè)數(shù)k的取值為1～20時(shí)，NBF與SBF算法的誤判率變化。圖中p1誤判率指的是將不在Δ1的用戶誤判為處于Δ1的概率，因?yàn)槊舾袇^(qū)域優(yōu)先級(jí)覆蓋的原因，SBF算法中p1誤判率還包括在Δ1的元素誤判為Δ2、Δ3的概率。p2和p3依此類推。

由圖9、10可知，當(dāng)k=1時(shí)，SBF誤判率約為0.213 4，此時(shí)NBF誤判率約為0.113 1；當(dāng)k=3時(shí)，SBF誤判率達(dá)到最低，約為0.135 2，此時(shí)NBF誤判率約為0.027 6；當(dāng)k=6時(shí)，NBF誤判率達(dá)到最低， 約為0.019 74，此時(shí)SBF誤判率約為0.018 28； 當(dāng)數(shù)組長(zhǎng)度固定時(shí)，不同 k值時(shí)的NBF誤判率都低于SBF?？紤]到k增大，需要進(jìn)行更多次的哈希運(yùn)算而引入較多的計(jì)算開銷，因此在本實(shí)驗(yàn)中選取哈希函數(shù)個(gè)數(shù)為3。

圖11、12是哈希函數(shù)個(gè)數(shù)k為3，數(shù)組長(zhǎng)度m′為100～400時(shí)，NBF與SBF算法的誤判率變化。隨著數(shù)組長(zhǎng)度m′逐漸增大，無(wú)論是SBF還是NBF的誤判率都呈下降趨勢(shì)。

結(jié)合圖9～12可知，當(dāng)數(shù)組長(zhǎng)度m′和哈希函數(shù)個(gè)數(shù)k處于同一條件時(shí)，算法涉及的計(jì)算和通信開銷一致，NBF比SBF具有更低的誤判率。

5.3 通信開銷和計(jì)算開銷

在本文實(shí)驗(yàn)中，設(shè)服務(wù)器端數(shù)據(jù)庫(kù)RP總數(shù)為m，敏感區(qū)域元素個(gè)數(shù)為n，哈希數(shù)組長(zhǎng)度為m′，哈希函數(shù)個(gè)數(shù)為k，為保證方案的安全性， Paillier加密算法中密鑰為1 024 bit。在方案中，計(jì)算開銷主要涉及哈希函數(shù)、1 024 bit模冪、1 024 bit模乘，依次表示為h、exp、mul。通信開銷指用戶接收和發(fā)送的數(shù)據(jù)，以bit為單位。各方案的通信和計(jì)算開銷數(shù)據(jù)如表1所示。

根據(jù)圖7中的信息，公共數(shù)據(jù)集中1～3級(jí)敏感區(qū)域RP集合Δ1～Δ3中元素個(gè)數(shù)分別為24、16、8。實(shí)驗(yàn)設(shè)定哈希數(shù)組長(zhǎng)度m′為200，哈希函數(shù)個(gè)數(shù)k=3。通過(guò)實(shí)驗(yàn)計(jì)算通信開銷和計(jì)算開銷，如表2所示。

表1、2中的數(shù)據(jù)表明，本文改進(jìn)方案與基礎(chǔ)方案相比，通信開銷大幅度減少，同時(shí)服務(wù)器端數(shù)據(jù)加密時(shí)計(jì)算開銷大幅度降低，數(shù)據(jù)解密時(shí)計(jì)算開銷不會(huì)產(chǎn)生變化，不過(guò)因?yàn)槭褂枚鄠€(gè)哈希函數(shù)，用戶端在計(jì)算過(guò)程中產(chǎn)生的非零數(shù)值數(shù)量增多導(dǎo)致計(jì)算開銷增加。而改進(jìn)方案與SBF數(shù)據(jù)對(duì)比，兩者的計(jì)算開銷和通信開銷都大致相同，但改進(jìn)方案中NBF比SBF擁有更優(yōu)的誤判率。值得注意之處在于，改進(jìn)方案的通信和計(jì)算開銷只與敏感區(qū)域中的RP個(gè)數(shù)有關(guān)，與服務(wù)器端數(shù)據(jù)庫(kù)中RP總數(shù)無(wú)關(guān)。當(dāng)服務(wù)器端數(shù)據(jù)庫(kù)中RP數(shù)量巨大或者實(shí)驗(yàn)分布區(qū)域廣泛導(dǎo)致RP塊分布過(guò)多時(shí)，改進(jìn)方案的通信和計(jì)算開銷優(yōu)化效果將會(huì)更加明顯。

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

針對(duì)隱私定位服務(wù)中，服務(wù)器需要監(jiān)控特定敏感區(qū)域的情況，本文提出了一種基于隱私保護(hù)的敏感區(qū)域室內(nèi)定位算法，其目的是在不泄露用戶定位信息的前提下，準(zhǔn)確判斷用戶是否進(jìn)入特定的敏感區(qū)域。該算法針對(duì)服務(wù)器端數(shù)據(jù)庫(kù)中RP數(shù)量眾多使得加密數(shù)據(jù)量大、通信開銷大的問(wèn)題，采用BF結(jié)合一種新穎的哈希數(shù)組合并方式，對(duì)各RP進(jìn)行映射，大幅度減少服務(wù)器端數(shù)組長(zhǎng)度，從而降低計(jì)算和通信開銷。所提的基于哈希數(shù)組合并的方式可替代SBF，適用于其他應(yīng)用中多類數(shù)據(jù)集的BF濾波編碼，在設(shè)定的濾波參數(shù)相同時(shí)，本文的NBF具有更低的誤判率。

同時(shí)，服務(wù)器端通過(guò)本文算法只能夠判斷用戶是否進(jìn)入多級(jí)敏感區(qū)域，不在這些區(qū)域的用戶在此過(guò)程中不會(huì)泄露其位置信息。需要注意的是，在當(dāng)前技術(shù)水平下，室內(nèi)定位仍然存在一定誤差。因此，為確保算法的可靠性，服務(wù)器端應(yīng)將原始敏感區(qū)域劃分為更大的區(qū)域，以確保用戶即使位于區(qū)域的邊緣或存在定位誤差時(shí)，服務(wù)器端仍能夠準(zhǔn)確判斷處于敏感區(qū)域的用戶。這可以通過(guò)增加敏感區(qū)域的邊界范圍來(lái)實(shí)現(xiàn)，以提高算法的魯棒性和精確度。

參考文獻(xiàn)：

［1］Li Shuyu，Welsen S，Brusic V. Multi－AP and test point accuracy of the results in WiFi indoor localization ［J］.Sensors ，2022， 22 （10）： 3709.

［2］Wilford A，Pu Qiaolin，Zhou Mu，et al. RSSI fingerprint height based empirical model prediction for smart indoor localization ［J］.Sensors ，2022， 22 （23）： 9054 .

［3］Han Zhaoyang，Wang Ziyue，Huang Huakun，et al. WiFi－based indoor positioning and communication： empirical model and theoretical ana－lysis ［J］.Wireless Communications and Mobile Computing ，2022， 2022 ： article ID 2364803.

［4］Zhang Liye，Meng Xiaoliang，F(xiàn)ang Chao. Linear regression algorithm against device diversity for the WLAN indoor localization system ［J］.Wireless Communications and Mobile Computing ，202 2021 ： article ID 5530396.

［5］Feng Xu，Nguyen K A，Luo Zhiyuan. A survey of deep learning approaches for WiFi－based indoor positioning ［J］.Journal of Information and Telecommunication ，2022， 6 （2）： 163－216.

［6］Beresford A R，Stajano F. Location privacy in pervasive computing ［J］.IEEE Pervasive Computing ，2003， 2 （1）： 46－55.

［7］殷鳳梅，陳鴻. Geohash編碼的k匿名位置隱私保護(hù)方案 ［J］. 武漢大學(xué)學(xué)報(bào)： 理學(xué)版，2022， 68 （1）： 73－82. （Yin Fengmei，Chen Hong. k anonymous location privacy preservation scheme based on Geohash coding ［J］.Journal of Wuhan University： Natural Science Edition ，2022， 68 （1）： 73－82.）

［8］劉振鵬，苗德威，劉倩楠，等. k－匿名下通過(guò)本地差分隱私實(shí)現(xiàn)位置隱私保護(hù) ［J］. 計(jì)算機(jī)應(yīng)用研究，2022， 39 （8）： 2469－2473. （Liu Zhenpeng，Miao Dewei，Liu Qiannan，et al. Location privacy protection through local differential privacy under k－anonymity ［J］.Application Research of Computers ，2022， 39 （8）： 2469－2473.）

［9］宋成，程道晨，倪水平. 個(gè)性化差分隱私的k匿名軌跡隱私保護(hù)方案 ［J］. 北京郵電大學(xué)學(xué)報(bào)，2023， 46 （3）：109－114. （Song Cheng，Cheng Daochen，Ni Shuiping. k anonymous trajectory privacy protection scheme of personalized differential privacy ［J］.Journal of Beijing University of Posts and Telecommunications ，2023， 46 （3）：109－114.）

［10］郭萍. 基于差分隱私的位置隱私保護(hù)模型研究 ［D］. 貴陽(yáng)： 貴州大學(xué)，2022. （Guo Ping. Research on location privacy protection model based ondifferential privacy［D］. Guiyang： Guizhou University， 2022.）

［11］Yang Zheng，Jrvinen K. The death and rebirth of privacy－preserving WiFi fingerprint localization with Paillier encryption ［C］// Proc of IEEE INFOCOM－IEEE Conference on Computer Communications. Piscataway，NJ： IEEE Press，2018： 1223－1231.

［12］Li Hong，Sun Limin，Zhu Haojin，et al. Achieving privacy preservation in WiFi fingerprint－based localization ［C］// Proc of IEEE INFOCOM－ IEEE Conference on Computer Communications. Piscataway，NJ： IEEE Press，2014： 2337－2345.

［13］Li Shujun，Li Hong，Sun Limin. Privacy－preserving crowdsourced site survey in WiFi fingerprint－based localization ［J］.EURASIP Journal on Wireless Communications and Networking ，2016， 2016 （1）： 1－9.

［14］Palmieri P，Calderoni L，Maio D. Spatial Bloom filters： enabling privacy in location－aware applications ［C］// Proc of the 10th International Conference on Information Security and Cryptology. Berlin： Springer，2015： 16－36.

［15］Calderoni L，Palmieri P，Maio D. Location privacy without mutual trust： the spatial Bloom filter ［J］.Computer Communications ，2015， 68 ： 4－16.

［16］Calderoni L，Palmieri P，Maio D. Probabilistic properties of the spatial Bloom filters and their relevance to cryptographic protocols ［J］.IEEE Trans on Information Forensics and Security ，2018， 13 （7）： 1710－1721.

［17］Zeilemaker N，Erkin Z，Palmieri P，et al.Building a privacy－preservingsemantic overlay for peer－to－peer networks ［C］// Proc of IEEE InternationalWorkshop on Information Forensics and Security. Piscata－ way，NJ： IEEE Press，2013： 79－84.

［18］Tóth Z，Tamás J. Miskolc IIS hybrid IPS： dataset for hybrid indoor positioning ［C］// Proc of the 26th International Conference Radio－elektronika. Piscataway，NJ： IEEE Press，2016： 408－412.

收稿日期：2023－06－13；修回日期：2023－08－11 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62172281）

作者簡(jiǎn)介：宋威燃（1998—），男，安徽宿州人，碩士研究生，主要研究方向?yàn)槭覂?nèi)定位和隱私保護(hù)；黃芯怡（2002—），女，上海人，本科生，主要研究方向?yàn)槭覂?nèi)定位和隱私保護(hù)；樂(lè)燕芬（1978—），女（通信作者），浙江寧波人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)槭覂?nèi)定位和信息隱藏（leyanfen@usst.edu.cn）.