基于加權(quán)最小二乘的社交網(wǎng)絡(luò)用戶定位方法

時(shí)文旗，羅向陽，郭家山

（1. 網(wǎng)絡(luò)空間態(tài)勢(shì)感知河南省重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001； 2. 數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001；3. 鄭州大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450001）

0 引言

隨著智能移動(dòng)設(shè)備的普及和社交媒體的廣泛流行，社交網(wǎng)絡(luò)中的多媒體數(shù)據(jù)得到爆發(fā)式增長(zhǎng)[1]。位置文本作為多媒體數(shù)據(jù)的一種，廣泛存在于各類社交平臺(tái)。在基于位置的社交網(wǎng)絡(luò)（LBSN，location- based social network）中，這類位置文本往往用于提供基于位置的服務(wù)，如導(dǎo)航、定向廣告、好友發(fā)現(xiàn)等[2-5]，為用戶帶來了巨大便利。然而，位置信息是一種重要的隱私信息，用戶在享受社交平臺(tái)帶來便利的同時(shí)，存在自身位置隱私被社交平臺(tái)泄露的風(fēng)險(xiǎn)。以基于位置的交友服務(wù)為例，該服務(wù)利用用戶的位置信息，為用戶提供基于位置的附近用戶發(fā)現(xiàn)功能，并展示附近用戶的距離文本，如微信“附近的人”服務(wù)。為了保護(hù)用戶位置隱私，社交平臺(tái)往往會(huì)對(duì)距離信息進(jìn)行混淆處理，但展示的距離文本依然存在暴露用戶位置的可能[6-7]。開展社交網(wǎng)絡(luò)用戶定位研究，能夠驗(yàn)證社交平臺(tái)對(duì)用戶位置隱私保護(hù)的有效性，進(jìn)而有助于用戶享受到更安全便捷的服務(wù)，具有重要的現(xiàn)實(shí)意義和研究?jī)r(jià)值。

現(xiàn)有關(guān)于LBSN用戶定位的研究主要分為兩類：基于文本和社交關(guān)系的用戶定位，基于交友服務(wù)的用戶定位。前者利用用戶在社交平臺(tái)中發(fā)布的文本、簽到數(shù)據(jù)、社交關(guān)系等信息推斷用戶的真實(shí)位置[8-10]；后者研究如何利用社交網(wǎng)絡(luò)的位置交友服務(wù)中公開展示的距離文本定位用戶位置，是本文重點(diǎn)討論的問題。

基于位置的交友服務(wù)在展示用戶間距離時(shí)，會(huì)對(duì)其進(jìn)行混淆處理，使惡意用戶難以基于展示的距離直接確定用戶位置，一定限度上起到保護(hù)用戶隱私的作用。然而，現(xiàn)有研究表明，在距離文本被混淆的情況下，基于不同位置獲取的用戶混淆后的距離文本及其統(tǒng)計(jì)特征，依然能夠準(zhǔn)確推斷出用戶的真實(shí)距離范圍。為此，越來越多的社交平臺(tái)逐漸加強(qiáng)對(duì)服務(wù)使用次數(shù)、用戶實(shí)名認(rèn)證等限制，以防止惡意用戶對(duì)服務(wù)的濫用。

為了驗(yàn)證當(dāng)前社交網(wǎng)絡(luò)中基于位置的交友服務(wù)采用的位置隱私保護(hù)機(jī)制的有效性，本文提出基于加權(quán)最小二乘的社交網(wǎng)絡(luò)用戶定位方法。該方法基于區(qū)域覆蓋原則確定目標(biāo)的大致位置，并采用加權(quán)最小二乘法實(shí)現(xiàn)對(duì)目標(biāo)的精確定位；利用微信社交平臺(tái)進(jìn)行了實(shí)際定位實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明所提方法能以很高的效率實(shí)現(xiàn)對(duì)微信用戶的精確定位。

1 相關(guān)工作

1.1 LBSD服務(wù)

隨著移動(dòng)社交網(wǎng)絡(luò)的普及，基于位置的交友（LBSD，location-based social discovery）服務(wù)[11]快速發(fā)展并得以流行，F(xiàn)acebook、Telegram、微信、QQ等全球流行的社交平臺(tái)均提供此類服務(wù)。該服務(wù)通過獲取用戶手機(jī)等移動(dòng)設(shè)備的位置信息，向用戶推薦其自身位置附近的其他用戶，并展示附近用戶的相對(duì)距離（稱為報(bào)告距離）。為了保護(hù)用戶位置隱私，LBSD服務(wù)器會(huì)采用對(duì)報(bào)告距離進(jìn)行混淆處理，起到一定的位置模糊效果。

常見的報(bào)告距離混淆策略有設(shè)置最小粒度、添加隨機(jī)噪聲、次序映射等。通過設(shè)置最小粒度，將用戶間的精確距離向上取整，以防止三邊測(cè)量定位攻擊；通過添加隨機(jī)噪聲，在保證服務(wù)質(zhì)量的前提下，使報(bào)告距離呈現(xiàn)一定的隨機(jī)性，以應(yīng)對(duì)基于統(tǒng)計(jì)特征的定位攻擊；通過隱藏距離信息，并以次序映射的形式體現(xiàn)用戶距離，能夠增加定位用戶位置的成本。

為了避免服務(wù)被惡意用戶濫用，LBSD服務(wù)提供商會(huì)采用檢測(cè)虛擬位置、限制查詢次數(shù)、限定查詢距離范圍、設(shè)置用戶推薦時(shí)間域等方式，對(duì)定位用戶所需的頻繁查詢行為進(jìn)行限制。

1.2 LBSD用戶定位相關(guān)工作

LBSD用戶定位技術(shù)主要基于LBSD服務(wù)公開展示的附近用戶報(bào)告距離、相對(duì)次序等特征，通過部署位置已知的探針在不同位置獲取目標(biāo)用戶被混淆后的報(bào)告距離等信息，進(jìn)而推斷目標(biāo)用戶的位置。

Ding等[12]利用報(bào)告距離的分段特性，采用距離外擴(kuò)的方式確定目標(biāo)用戶相距探針的真實(shí)距離范圍，并基于經(jīng)典的三邊測(cè)量定位方法，實(shí)現(xiàn)對(duì)目標(biāo)用戶的粗粒度定位和追蹤；為了突破最小報(bào)告距離對(duì)定位精度的限制，Li等[13]提出了基于空間劃分的定位（SPBG，space partition-based geolocation）方法，該方法通過對(duì)最小報(bào)告距離對(duì)應(yīng)地理區(qū)間的二分查找，實(shí)現(xiàn)對(duì)微信用戶更高精度的定位，后續(xù)工作進(jìn)一步以更大的開銷實(shí)現(xiàn)了定位精度的提升[14-15]；針對(duì)報(bào)告距離隨機(jī)化問題，Peng等[17]在文獻(xiàn)[16]所提的二維數(shù)論定位方法的基礎(chǔ)上，設(shè)計(jì)了基于啟發(fā)式數(shù)論的定位（HNBG，heuristic number theory-based geolocation）方法，提高了實(shí)際環(huán)境下對(duì)LBSD用戶的定位精度。Polakis等[18]將用戶定位問題進(jìn)行模型化描述，提出了一個(gè)用戶定位框架，并實(shí)現(xiàn)了對(duì)Facebook Messager、Skout等多款社交平臺(tái)用戶的定位。

1.3 問題描述

如上述相關(guān)工作所述，雖然當(dāng)前LBSD服務(wù)采用了多種策略保護(hù)用戶位置隱私，現(xiàn)有方法依然可以通過頻繁獲取目標(biāo)用戶的報(bào)告距離，基于其統(tǒng)計(jì)特征實(shí)現(xiàn)對(duì)目標(biāo)真實(shí)位置的逼近和定位。然而，為了實(shí)現(xiàn)對(duì)目標(biāo)的精確定位，現(xiàn)有方法在定位目標(biāo)過程中均需要部署大量探針，并利用探針在不同位置對(duì)目標(biāo)用戶的報(bào)告距離進(jìn)行頻繁搜集，實(shí)現(xiàn)對(duì)目標(biāo)真實(shí)位置的精確定位。在當(dāng)前LBSD服務(wù)加強(qiáng)對(duì)用戶的實(shí)名認(rèn)證、限制用戶的服務(wù)使用次數(shù)等措施下，現(xiàn)有方法定位目標(biāo)所需的開銷過大，其實(shí)用性有待提高。

2 基于加權(quán)最小二乘的社交用戶定位

本文針對(duì)現(xiàn)有LBSD用戶精確定位方法定位開銷大、定位時(shí)間長(zhǎng)的不足，提出了一種基于加權(quán)最小二乘的社交網(wǎng)絡(luò)用戶高效定位方法。該方法主要分為兩個(gè)部分：距離邊界識(shí)別、目標(biāo)用戶定位。其中，第一部分為定位前的準(zhǔn)備工作，通過搜集大量的真實(shí)LBSD服務(wù)數(shù)據(jù)，識(shí)別不同報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界，為定位目標(biāo)時(shí)提供用戶距離劃定依據(jù)。當(dāng)定位目標(biāo)用戶時(shí)，本文方法首先通過優(yōu)化探針部署方式，并基于區(qū)域覆蓋初步確定目標(biāo)用戶的多個(gè)估計(jì)位置；然后，基于估計(jì)位置對(duì)目標(biāo)用戶的真實(shí)距離邊界進(jìn)行權(quán)值分配；最后，基于分配的權(quán)值構(gòu)建目標(biāo)函數(shù)，利用最小二乘法求目標(biāo)函數(shù)的最優(yōu)解，即目標(biāo)用戶的最終定位結(jié)果。該方法的原理示意如圖1所示，主要步驟如下。

圖1 基于加權(quán)最小二乘的社交網(wǎng)絡(luò)用戶定位方法原理示意Figure 1 Diagram of social network user geolocating method based on weighted least squares

步驟1真實(shí)距離邊界識(shí)別

利用已知位置的社交賬戶，搜集大量真實(shí)環(huán)境下的報(bào)告距離，從而確定不同報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍。通過控制并調(diào)整已知位置的用戶間的真實(shí)距離，記錄不同真實(shí)距離下用戶間的報(bào)告距離，建立包含<真實(shí)距離，報(bào)告距離>數(shù)據(jù)對(duì)的數(shù)據(jù)集；將數(shù)據(jù)集中報(bào)告距離相同的真實(shí)距離進(jìn)行歸類并排序，得到該報(bào)告距離對(duì)應(yīng)的真實(shí)距離序列，序列的首尾值即該報(bào)告距離對(duì)應(yīng)的最遠(yuǎn)真實(shí)距離和最近真實(shí)距離。對(duì)于不同的報(bào)告距離Rdi，其對(duì)應(yīng)的最遠(yuǎn)真實(shí)距離和最近真實(shí)距離分別記為Rd[i]max和Rd[i]min。

步驟2潛在區(qū)域目標(biāo)發(fā)現(xiàn)

在目標(biāo)所處潛在區(qū)域中等距部署探針?biāo)褜つ繕?biāo)用戶，直到目標(biāo)用戶出現(xiàn)在探針的附近用戶列表中，記錄此時(shí)目標(biāo)用戶的報(bào)告距離為Rd1，將發(fā)現(xiàn)目標(biāo)用戶的探針稱為初始探針P1。

步驟3探針位置部署優(yōu)化

探針間位置分布會(huì)對(duì)定位精度及成功率產(chǎn)生重要影響。為了避免不合理探針分布對(duì)定位的影響，本步驟通過判斷目標(biāo)用戶在以初始探針為原點(diǎn)的坐標(biāo)系中所處的象限，優(yōu)化探針的部署。

首先，以初始探針P1為原點(diǎn)建立坐標(biāo)系，如圖2所示。在坐標(biāo)軸上坐標(biāo)為(Rd[1]max, 0)，(?Rd[1]max, 0)，(0, Rd[1]max)和(0, ?Rd[1]max)處分別部署探針；然后，各探針分別查詢附近的人以獲取目標(biāo)用戶的報(bào)告距離；最后，選取探針中獲取的目標(biāo)用戶的報(bào)告距離最小且不在同一坐標(biāo)軸上的探針（記為P2和P3，對(duì)應(yīng)的目標(biāo)用戶的報(bào)告距離為Rd2和Rd3），結(jié)合初始探針P1作為三邊測(cè)量定位的探針。若各探針獲取的目標(biāo)報(bào)告距離相同，為便于處理，選取(Rd[1]max, 0)和(0, Rd[1]max)作為P2和P3，此時(shí)認(rèn)為目標(biāo)用戶在以P1為原點(diǎn)的坐標(biāo)系中，位于P2、P1和P3所對(duì)應(yīng)的象限，如圖2中陰影部分所示，P2′、P和P1′分別對(duì)應(yīng)P2、P1和P3。

圖2 探針部署示意Figure 2 Diagram of probe deployment

步驟4目標(biāo)用戶初步定位

步驟3中確定了定位目標(biāo)所需的探針（P1、P2和P3）及其對(duì)應(yīng)的目標(biāo)用戶的報(bào)告距離（Rd1、Rd2和Rd3），此時(shí)利用步驟1中確定的報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界，分別以各探針位置（P1、P2和P3）為中心做圓環(huán)，圓環(huán)的內(nèi)徑和外徑分別為該探針獲取的目標(biāo)的報(bào)告距離所對(duì)應(yīng)的真實(shí)距離邊界，目標(biāo)用戶的位置就在3個(gè)圓環(huán)的交叉區(qū)域內(nèi)。取圓環(huán)交叉區(qū)域的重心點(diǎn)作為對(duì)目標(biāo)的初步定位結(jié)果L1。

更新探針位置，將所有探針沿坐標(biāo)軸方向平移σ距離，得到的新的探針位置記為P4、P5和P6。采用上述方法得到目標(biāo)用戶的另一個(gè)初步定位結(jié)果L2。

步驟5加權(quán)最小二乘求最優(yōu)解

由于系統(tǒng)噪聲的影響，步驟1中建立的報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界較為寬泛，從而導(dǎo)致步驟4中圓環(huán)的交叉區(qū)域的范圍較大，初步定位結(jié)果很大概率與目標(biāo)真實(shí)位置存在較大的誤差。而若以報(bào)告距離為觀測(cè)數(shù)據(jù)建立誤差目標(biāo)方程，得到的目標(biāo)用戶位置的估計(jì)值與真實(shí)位置偏差較大，進(jìn)而造成定位結(jié)果并不可靠。為此，本文方法以初步定位結(jié)果為參考，通過對(duì)目標(biāo)用戶的真實(shí)距離賦不同權(quán)值，進(jìn)而執(zhí)行對(duì)目標(biāo)用戶的下一輪定位。

計(jì)算L1和L2的中點(diǎn)，記為L(zhǎng)e，計(jì)算Le與探針Pi的真實(shí)距離，記為，設(shè)目標(biāo)用戶的真實(shí)位置為L(zhǎng)T，對(duì)各探針對(duì)應(yīng)的目標(biāo)用戶最遠(yuǎn)真實(shí)距離和最近真實(shí)距離分別賦予不同權(quán)重inwi和ouwi，并構(gòu)建如下目標(biāo)函數(shù)。

其中，m表示用于定位目標(biāo)的探針數(shù)量，Tdis(Pi,X)表示探針Pi與位置X之間的真實(shí)距離，且

利用最小二乘法求使目標(biāo)函數(shù)f最小的最優(yōu)解X，X為對(duì)目標(biāo)用戶位置的最終定位結(jié)果，即

在上述步驟中，步驟3和步驟5是本文方法的關(guān)鍵。

3 基于象限判定優(yōu)化探針部署

三邊測(cè)量定位用戶時(shí)的探針位置分布對(duì)定位結(jié)果有著重要的影響。當(dāng)探針間夾角過大時(shí)，容易導(dǎo)致3個(gè)圓環(huán)之間形成狹長(zhǎng)的交叉區(qū)域，在該交叉區(qū)域內(nèi)取得目標(biāo)定位結(jié)果時(shí)，定位精度難以保證。因此，所提方法通過設(shè)置探針間最大夾角，避免不合理的探針位置分布；同時(shí)通過判定目標(biāo)用戶在坐標(biāo)系中的象限，避免因探針位置與目標(biāo)用戶距離過遠(yuǎn)導(dǎo)致定位誤差增大。

3.1 距離邊界劃定

探針的位置部署依賴于報(bào)告距離Rd1對(duì)應(yīng)的真實(shí)距離邊界，下面介紹真實(shí)距離邊界的劃定方法。

大多數(shù)LBSD服務(wù)以報(bào)告距離的方式展示附近用戶的位置信息，且會(huì)設(shè)置最小報(bào)告距離，如微信、探探以100 m為單位，陌陌以10 m為單位展示附近用戶的距離。在沒有系統(tǒng)混淆的情況下，該報(bào)告距離反映了用戶的真實(shí)距離邊界，即

其中，K表示報(bào)告距離的變化單位。然而，系統(tǒng)誤差的存在使當(dāng)真實(shí)距離小于Rd?K或大于Rd時(shí)，報(bào)告距離依然可能為Rd，即實(shí)際環(huán)境下的真實(shí)距離邊界會(huì)更為寬泛。

為了尋找實(shí)際環(huán)境下報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界，需要獲取大量的真實(shí)數(shù)據(jù)。通過控制多個(gè)不同賬戶的位置，能夠控制用戶間的真實(shí)距離使之逐漸增大，每次距離變化的增量記為Δd。用戶變化位置后，分別查詢附近其他用戶的報(bào)告距離，從而得到<真實(shí)距離，報(bào)告距離>數(shù)據(jù)對(duì)。通過大量測(cè)試，能夠獲取實(shí)際環(huán)境下的真實(shí)距離邊界數(shù)據(jù)集（BTD，boundary of true distance）。BTD中一輪測(cè)試過程可表示如下。

其中，數(shù)據(jù)集A表示所有可能出現(xiàn)的報(bào)告距離，M表示一輪測(cè)試過程中的測(cè)試次數(shù)，d0表示該輪測(cè)試開始時(shí)用戶間的初始真實(shí)距離，di表示第i次測(cè)試時(shí)用戶間的真實(shí)距離。獲得數(shù)據(jù)集后，依據(jù)報(bào)告距離不同，將數(shù)據(jù)集中數(shù)據(jù)對(duì)分成若干子集。每個(gè)子集的數(shù)據(jù)對(duì)中的真實(shí)距離id表示在某次測(cè)試中，當(dāng)用戶間的真實(shí)距離為id時(shí)，兩者之間的報(bào)告距離為該子集對(duì)應(yīng)的報(bào)告距離。最后，剔除各子集中真實(shí)距離id的異常值，并對(duì)其進(jìn)行排序，取排序后的首位值分別作為該報(bào)告距離對(duì)應(yīng)的最遠(yuǎn)真實(shí)距離和最近真實(shí)距離。需要注意的是，最小報(bào)告距離的存在，使最小報(bào)告距離對(duì)應(yīng)的最小真實(shí)距離為0，此時(shí)需要綜合考慮社交平臺(tái)的位置混淆特性和實(shí)際定位效果，選擇定位過程的觸發(fā)閾值。

由于位置更新時(shí)間、設(shè)備定位誤差等因素的影響，各子集中可能存在一些異常值，異常值最明顯的特征為遠(yuǎn)大于或遠(yuǎn)小于其他真實(shí)距離。這些異常值并不能反映實(shí)際條件下該報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍，且會(huì)導(dǎo)致定位目標(biāo)時(shí)劃定的目標(biāo)距離邊界過大，影響定位精度。因此，需要剔除各子集中的異常值，使確定的真實(shí)距離邊界能夠有效反映實(shí)際條件下LBSD服務(wù)的距離特征，從而為目標(biāo)用戶的準(zhǔn)確定位提供保障。

3.2 探針優(yōu)化部署

三邊測(cè)量定位方法具有很高的效率，也是本文方法的理論基礎(chǔ)[19]。當(dāng)利用三邊測(cè)量定位方法定位目標(biāo)時(shí)，合理的探針分布會(huì)更有利于得到集中的交叉區(qū)域，從而有助于提高定位精度。

在定位目標(biāo)過程中，當(dāng)初始探針發(fā)現(xiàn)目標(biāo)用戶時(shí)，可根據(jù)目標(biāo)用戶的報(bào)告距離（記為Rd1）及其對(duì)應(yīng)的真實(shí)距離邊界，劃定目標(biāo)用戶相較于初始探針的距離范圍，即[Rd[1]min,Rd[]1max]。此時(shí)，在以初始探針位置為中心的坐標(biāo)軸上選擇其余探針的位置時(shí)，其與初始探針的距離對(duì)判定目標(biāo)所處象限的準(zhǔn)確性影響很大。

不失一般性，假設(shè)目標(biāo)用戶位于坐標(biāo)系的第四象限，且P1′至P4′距離初始探針的真實(shí)距離分別為d1′至d4′，以P3'為例進(jìn)行討論，如圖3所示。

圖3 探針間距離關(guān)系示意Figure 3 Diagram of distance relationship between probes

由于dis(P,T)≤Rd[1]max，且∠P3′PT為鈍角，則

由三角形性質(zhì)可知

若探針P3′與初始探針的距離dis(P,P3′)過小，即圖中d3′過小時(shí)，可能存在Rd[1]max> dis(P3′,T)>d3′，此時(shí)，在探針P3'處得到的目標(biāo)用戶的報(bào)告距離依然可能是1Rd，基于報(bào)告距離變化將無法判斷目標(biāo)所處的象限。

本文方法依據(jù)初始探針獲取的目標(biāo)用戶報(bào)告距離的最大真實(shí)距離，來確定其他探針的位置分布。此時(shí)，Rd[1]max。即當(dāng)目標(biāo)用戶位于坐標(biāo)系的第四象限時(shí)，探針P3'得到的目標(biāo)用戶的報(bào)告距離必然大于Rd1，因此，當(dāng)P3′得到的目標(biāo)用戶的報(bào)告距離不大于Rd1時(shí)，目標(biāo)用戶必然不在第四象限。同理，當(dāng)目標(biāo)用戶位于第一象限時(shí)，上述關(guān)系依然存在。

綜上，本文方法基于探針獲取的目標(biāo)用戶的報(bào)告距離大小來判斷目標(biāo)用戶所處的象限，從而選定三邊測(cè)量定位的探針位置，有助于確定更合理的探針位置分布。

4 基于估計(jì)位置確定距離邊界權(quán)值

通過設(shè)置不同社交賬號(hào)的位置，能夠利用LBSD服務(wù)獲取不同真實(shí)距離下的報(bào)告距離，從而獲得不同報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍。假設(shè)報(bào)告距離Rd對(duì)應(yīng)的真實(shí)距離邊界為[150 m，350 m]，則當(dāng)兩個(gè)用戶間的真實(shí)距離在此范圍內(nèi)時(shí)，其查詢服務(wù)可能得到對(duì)方的報(bào)告距離為Rd。需要說明的是，由于系統(tǒng)誤差的影響，不同報(bào)告距離的真實(shí)距離邊界存在重疊部分，即用戶在某個(gè)真實(shí)距離條件下，其能夠得到的對(duì)方的報(bào)告距離可能不止一種。

最小二乘法作為一種數(shù)學(xué)優(yōu)化方法，通過對(duì)真實(shí)數(shù)據(jù)與多組觀測(cè)數(shù)據(jù)的誤差（即目標(biāo)函數(shù)）進(jìn)行最小化，來估計(jì)真實(shí)數(shù)據(jù)[20-21]。該方法應(yīng)用于LBSD目標(biāo)用戶定位時(shí)，如何選取觀測(cè)數(shù)據(jù)及如何建立目標(biāo)函數(shù)對(duì)于估計(jì)結(jié)果的準(zhǔn)確性至關(guān)重要。

4.1 觀測(cè)數(shù)據(jù)選取

在定位目標(biāo)過程中，探針能夠獲取目標(biāo)用戶的報(bào)告距離。然而，位置混淆的存在導(dǎo)致報(bào)告距離并不準(zhǔn)確，目標(biāo)用戶的真實(shí)距離可能遠(yuǎn)大于或遠(yuǎn)小于該報(bào)告距離。如圖4所示，目標(biāo)用戶的報(bào)告距離為Rd，且Rd的真實(shí)距離邊界分別為Rdmax和Rdmin。在定位目標(biāo)用戶時(shí)，探針僅能獲取目標(biāo)用戶被混淆后的報(bào)告距離Rd，若Rdmax與Rd差距較大，且目標(biāo)用戶的真實(shí)距離略小于Rdmax時(shí)，此時(shí)目標(biāo)的真實(shí)距離與Rd之間存在較大的差距，以Rd作為觀測(cè)數(shù)據(jù)無法準(zhǔn)確反映目標(biāo)用戶相對(duì)于探針的真實(shí)距離狀態(tài)。以Rd為觀測(cè)數(shù)據(jù)構(gòu)建目標(biāo)函數(shù)，并利用最小二乘法估算與其誤差最小的目標(biāo)用戶位置時(shí)，定位結(jié)果并不可靠。

圖4 目標(biāo)用戶真實(shí)距離與距離邊界的關(guān)系示意Figure 4 Diagram of relationship between real distance and distance boundary

在定位目標(biāo)時(shí)，基于探針獲取的目標(biāo)用戶的報(bào)告距離可以劃定目標(biāo)用戶的真實(shí)距離范圍，這個(gè)距離范圍可以認(rèn)為是準(zhǔn)確的，即當(dāng)目標(biāo)用戶的報(bào)告距離為Rd時(shí)，其相對(duì)于探針位置的真實(shí)距離必然在Rdmax和Rdmin之間。因此，本文方法選擇報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界作為觀測(cè)數(shù)據(jù)，并利用其構(gòu)建目標(biāo)函數(shù)，能夠較為準(zhǔn)確地反映目標(biāo)用戶的真實(shí)距離狀態(tài)。

4.2 目標(biāo)函數(shù)構(gòu)建

目標(biāo)函數(shù)應(yīng)相對(duì)準(zhǔn)確地反映目標(biāo)用戶的真實(shí)距離狀態(tài)。本文方法選擇報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界作為觀測(cè)數(shù)據(jù)，然而，由于觀測(cè)數(shù)據(jù)包含兩個(gè)值（最遠(yuǎn)真實(shí)距離和最近真實(shí)距離），在構(gòu)建目標(biāo)函數(shù)時(shí)，需要對(duì)兩個(gè)距離邊界賦予不同的權(quán)重。

基于直觀的想法，在以探針為圓心、以最遠(yuǎn)真實(shí)距離和最近真實(shí)距離分別作為外徑和內(nèi)徑的環(huán)形區(qū)域中，當(dāng)目標(biāo)用戶更靠近內(nèi)徑時(shí)，說明目標(biāo)的真實(shí)距離與最近真實(shí)距離之差更小，此時(shí)最近真實(shí)距離應(yīng)獲得更高的權(quán)重；否則，最遠(yuǎn)真實(shí)距離應(yīng)獲得更高的權(quán)重。因此，所提方法采用式(2)和式(3)所述方式，確定最近真實(shí)距離和最遠(yuǎn)真實(shí)距離的權(quán)值。

通過初步定位過程，能夠得到不同圓環(huán)的交叉區(qū)域，該交叉區(qū)域?yàn)橐粋€(gè)不規(guī)則曲邊圖形。由于目標(biāo)的真實(shí)距離會(huì)影響報(bào)告距離，直接影響圓環(huán)的內(nèi)徑和外徑，進(jìn)而對(duì)交叉區(qū)域的形狀產(chǎn)生影響。因目標(biāo)的真實(shí)距離范圍由圓環(huán)嚴(yán)格限定，確定目標(biāo)的初步定位結(jié)果時(shí)要保證定位結(jié)果在交叉區(qū)域內(nèi)，本文方法選擇重心作為初步定位結(jié)果。通過計(jì)算該交叉區(qū)域的重心，能近似推斷目標(biāo)用戶相較于探針的真實(shí)距離。此時(shí)，如不更新探針位置，將無法構(gòu)建有效的目標(biāo)函數(shù)實(shí)現(xiàn)對(duì)目標(biāo)用戶更高精度的定位。因此，得到初步定位結(jié)果后，更新探針位置是必要的。通過對(duì)探針位置進(jìn)行更新，得到的新的探針位置依然滿足步驟2中對(duì)目標(biāo)用戶的象限判定。此時(shí)依據(jù)初步定位結(jié)果，能夠確定構(gòu)建目標(biāo)函數(shù)時(shí)最遠(yuǎn)距離和最近距離的權(quán)重。

交叉區(qū)域重心位置的確定方法如圖5所示。首先，計(jì)算多個(gè)圓環(huán)交叉區(qū)域的頂點(diǎn)坐標(biāo)，為了便于計(jì)算，基于這些頂點(diǎn)坐標(biāo)做凸多邊形，設(shè)凸多邊形的邊數(shù)為n，將該n多邊形的重心作為不規(guī)則交叉區(qū)域的重心；然后，從凸多邊形的一個(gè)頂點(diǎn)出發(fā)，連接與其不相鄰的其余n?3個(gè)頂點(diǎn)，將圖形分割成n?2個(gè)三角形；接著，分別求各三角形的重心和面積，記為L(zhǎng)和S。

圖5 交叉區(qū)域重心位置示意Figure 5 Diagram of center of gravity position in intersection area

最后，根據(jù)各三角形面積占多邊形總面積的比重，確定該三角形重心坐標(biāo)的權(quán)值，將各重心的加權(quán)平均值作為該交叉區(qū)域的重心L′。設(shè)L′=(x,y)，則

上述過程能夠求得交叉區(qū)域的重心，將其作為中間定位結(jié)果，該結(jié)果一定限度上能夠反映出目標(biāo)用戶在圓環(huán)中的大致位置。因此，在構(gòu)建目標(biāo)函數(shù)時(shí)，基于中間定位結(jié)果確定最遠(yuǎn)距離和最近距離的權(quán)重，相比對(duì)其設(shè)置同等權(quán)重，更具合理性，更有助于提高真實(shí)環(huán)境下的定位精度。

5 時(shí)間復(fù)雜度分析

現(xiàn)有方法在定位目標(biāo)用戶時(shí)往往需要對(duì)LBSD服務(wù)進(jìn)行頻繁訪問，以尋找報(bào)告距離的統(tǒng)計(jì)特征。由于社交平臺(tái)加強(qiáng)對(duì)服務(wù)查詢次數(shù)的限制，現(xiàn)有方法的效率和實(shí)用性受到了極大制約。而本文方法在確定報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界時(shí)，受服務(wù)查詢次數(shù)限制的影響較小。實(shí)際上，現(xiàn)有方法大多存在這種數(shù)據(jù)預(yù)處理過程。例如，現(xiàn)有SPBG方法在定位開始前需要首先進(jìn)行大量測(cè)試以確定報(bào)告距離的真實(shí)距離邊界。因此，本文以定位目標(biāo)過程中所需的探針對(duì)LBSD服務(wù)的訪問次數(shù)為指標(biāo)，對(duì)比所提方法與現(xiàn)有典型代表性定位方法的時(shí)間復(fù)雜度。

現(xiàn)有SPBG方法首先通過查詢目標(biāo)的報(bào)告距離，來確定目標(biāo)對(duì)應(yīng)的真實(shí)距離范圍，并通過對(duì)目標(biāo)所位于的空間區(qū)域進(jìn)行二分判斷實(shí)現(xiàn)目標(biāo)定位，其整體時(shí)間復(fù)雜度為O(logN)。HNBG方法首先通過在所構(gòu)建的坐標(biāo)系的坐標(biāo)軸上等距部署大量探針，推斷初始估計(jì)坐標(biāo)，然后分別沿著初始估計(jì)坐標(biāo)執(zhí)行一維定位方法得到最終定位結(jié)果，其整體時(shí)間復(fù)雜度為O(N)。

與現(xiàn)有方法相比，本文提出的基于加權(quán)最小二乘的社交用戶高效定位方法采用了相同的目標(biāo)發(fā)現(xiàn)策略，但區(qū)別在于所提方法在定位目標(biāo)之前，基于大量的實(shí)際測(cè)試，建立了各報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍，從而避免了確定目標(biāo)距離范圍過程中，對(duì)目標(biāo)用戶報(bào)告距離的頻繁迭代查詢或校驗(yàn)。在定位目標(biāo)過程中，僅需要對(duì)目標(biāo)報(bào)告距離的數(shù)次查詢，即可利用最小二乘法推斷目標(biāo)位置，給出定位結(jié)果，其時(shí)間復(fù)雜度為O(1)。

綜上，本文所提方法在時(shí)間復(fù)雜度方面，相比現(xiàn)有典型的代表性方法具有明顯優(yōu)勢(shì)。

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

為了驗(yàn)證所提方法在實(shí)際環(huán)境下的定位效率及定位精度，本節(jié)基于微信社交平臺(tái)，設(shè)計(jì)并實(shí)施了用戶定位實(shí)驗(yàn)。微信作為一款流行的社交軟件，截至2021年年底，在全球范圍內(nèi)的月活躍用戶超12.6億，且微信“附近的人”是一類典型的基于位置的交友服務(wù)[22]。微信以100 m為單位展示附近用戶的距離，當(dāng)報(bào)告距離大于1 km時(shí)，其變化粒度發(fā)生變化（1 km為單位）。本文實(shí)驗(yàn)僅考慮報(bào)告距離小于1 km時(shí)的用戶定位。實(shí)驗(yàn)結(jié)果與現(xiàn)有典型方法HNBG[17]、SPBG[13]和RRABG（relation between reported and actual distance based geolocation）[15]做對(duì)比。

6.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)包括兩個(gè)部分：真實(shí)距離邊界識(shí)別實(shí)驗(yàn)及微信用戶定位實(shí)驗(yàn)。實(shí)驗(yàn)設(shè)置如表1所示。

表1 實(shí)驗(yàn)設(shè)置Table 1 Experiment Settings

本文利用多個(gè)微信賬號(hào)，實(shí)施真實(shí)距離邊界確定實(shí)驗(yàn)，為了便于闡述該過程，僅以用戶A和用戶B來表示該過程。首先，將微信用戶A位置固定，作為查詢者；用戶B作為附近用戶。用戶B的初始位置與A相同，之后調(diào)整其位置使其與用戶A的距離以5 m為單位逐漸增大。每次用戶B的位置變化后，用戶A查詢附近用戶并記錄用戶B在該距離下的報(bào)告距離，直到用戶B的報(bào)告距離出現(xiàn)1 km。上述過程稱為一輪測(cè)試，共計(jì)進(jìn)行了50輪測(cè)試?；诘玫降臏y(cè)試結(jié)果，劃定9種不同報(bào)告距離（100 m至900 m，以100 m為單位變化）的真實(shí)距離邊界。

目標(biāo)用戶定位實(shí)驗(yàn)部分，選取鄭州市市區(qū)5 km×5 km的區(qū)域作為實(shí)驗(yàn)區(qū)域，利用安卓模擬器將多個(gè)微信賬號(hào)的位置隨機(jī)設(shè)置在實(shí)驗(yàn)區(qū)域中，將其作為待定位的目標(biāo)用戶。利用其他微信賬號(hào)作為探針，探針在實(shí)驗(yàn)區(qū)域內(nèi)每隔400 m查詢一次附近用戶，直到目標(biāo)用戶出現(xiàn)在探針的附近的人列表中，然后對(duì)其執(zhí)行定位。成功定位所有目標(biāo)后，重新按照上述方法更新目標(biāo)的位置，直至得到500個(gè)定位結(jié)果。

所對(duì)比的HNBG、SPBG和RRABG方法采用文獻(xiàn)[17]、文獻(xiàn)[13]和文獻(xiàn)[15]的實(shí)驗(yàn)設(shè)置。

6.2 真實(shí)距離邊界識(shí)別

基于上述實(shí)驗(yàn)設(shè)置，共計(jì)得到11 724條<真實(shí)距離，報(bào)告距離>記錄，按照2.1節(jié)中介紹的距離邊界判定方法，得到的報(bào)告距離（100 m至900 m）對(duì)應(yīng)的真實(shí)距離范圍如表2所示。

表2 報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍Table 2 True distance range of the reported distance單位：m

由表2可知，微信的報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍較大，且該距離范圍與報(bào)告距離大致呈正相關(guān)。隨著用戶間真實(shí)距離增大，報(bào)告距離的不確定性也會(huì)增大。由于用戶更期望與附近的用戶建立社交關(guān)系，因此這種位置混淆策略是合理的?；讷@得的真實(shí)距離邊界，利用所提方法對(duì)微信目標(biāo)用戶進(jìn)行實(shí)際定位。

6.3 定位結(jié)果對(duì)比與分析

本文從定位精度和定位效率兩個(gè)方面對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析與對(duì)比。通過計(jì)算各方法的定位結(jié)果（經(jīng)緯度）與目標(biāo)真實(shí)位置之間的偏差來計(jì)算定位誤差；以在發(fā)現(xiàn)和定位目標(biāo)用戶的過程中，各探針對(duì)目標(biāo)用戶報(bào)告距離的查詢次數(shù)為指標(biāo)，對(duì)比各方法的定位效率。

（1）定位精度對(duì)比與分析

通過對(duì)500個(gè)微信目標(biāo)用戶的定位，分別計(jì)算所提方法和對(duì)比方法的定位誤差，其結(jié)果如圖6所示。

圖6展示了所提方法與對(duì)比方法的平均定位誤差和最小誤差。由圖6可知，在微信“附近的人”加強(qiáng)用戶位置混淆的前提下，所提方法依然能夠有效地定位微信用戶，最小誤差達(dá)到13.6 m，平均誤差為53.7 m。與現(xiàn)有典型微信用戶定位方法相比，平均定位誤差分別降低了23.6%、20.3%和10.2%。

圖6 定位誤差對(duì)比Figure 6 Comparison of geolocation error

各方法的定位誤差分布情況如圖7所示，圖中橫坐標(biāo)表示定位誤差的分布區(qū)間，縱坐標(biāo)表示不同定位誤差分布區(qū)間內(nèi)的定位結(jié)果在全部定位結(jié)果中所占的比例。由圖7可知，所提方法能夠?qū)?7%左右（0.059+0.213）的目標(biāo)定位在50 m以內(nèi)，將超過70%（0.059+0.213+0.452）的目標(biāo)定位在80 m以內(nèi)，高于對(duì)比方法。其中，所提方法的初步定位結(jié)果與目標(biāo)真實(shí)位置的誤差較大，這是由于微信的位置混淆機(jī)制使報(bào)告距離對(duì)應(yīng)的真實(shí)距離范圍較大，基于該距離范圍的三邊測(cè)量定位方法得到的交叉區(qū)域也較大，難以實(shí)現(xiàn)對(duì)目標(biāo)的高精度定位。而本文方法在對(duì)目標(biāo)實(shí)施兩輪三邊測(cè)量定位的基礎(chǔ)上，通過采用加權(quán)最小二乘法求目標(biāo)位置的最優(yōu)解，能夠進(jìn)一步提高定位精度。

圖7 誤差分布對(duì)比Figure 7 Comparison of error distribution

以探針在測(cè)試區(qū)域內(nèi)發(fā)現(xiàn)目標(biāo)用戶并開始定位時(shí)，目標(biāo)用戶的報(bào)告距離為依據(jù)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分類討論，分別計(jì)算各初始報(bào)告距離對(duì)應(yīng)的平均定位誤差，其結(jié)果如圖8所示。由圖8可知，目標(biāo)用戶的初始報(bào)告距離越近，其定位平均誤差相對(duì)越小。當(dāng)目標(biāo)用戶的初始報(bào)告距離大于700 m時(shí)，所提方法對(duì)其的定位誤差顯著增大。這是由于此時(shí)報(bào)告距離對(duì)應(yīng)的真實(shí)距離會(huì)更加離散，且變化幅度更大，因此所提方法在對(duì)目標(biāo)進(jìn)行初步定位和精確定位時(shí)均會(huì)存在較大的誤差。在實(shí)際定位過程中，通過在目標(biāo)用戶發(fā)現(xiàn)階段設(shè)置對(duì)目標(biāo)用戶報(bào)告距離的限制，如當(dāng)探針發(fā)現(xiàn)目標(biāo)用戶且目標(biāo)的報(bào)告距離小于600 m時(shí)執(zhí)行定位，將進(jìn)一步提高對(duì)目標(biāo)的定位精度，但會(huì)帶來更大的定位開銷。

圖8 目標(biāo)不同初始報(bào)告距離下的定位平均誤差Figure 8 Average geolocating error of target under different initial reporting distances

（2）定位效率對(duì)比與分析

所提方法和對(duì)比方法對(duì)目標(biāo)用戶報(bào)告距離的平均查詢次數(shù)如圖9所示。RRABG方法是在SPBG方法的基礎(chǔ)上，通過多探針協(xié)作判定，提高空間劃分的成功率，其所需查詢次數(shù)大于SPBG，因此本節(jié)選擇效率更高的SPBG方法作為對(duì)比方法之一。圖9中AQT-F表示方法在目標(biāo)發(fā)現(xiàn)過程中的平均查詢次數(shù)（average query times of target finding），AQT-G表示在目標(biāo)定位過程中的平均查詢次數(shù)（average query times of target geolocating），AQT-T表示兩者之和。由于HNBG方法討論1 km×1 km范圍內(nèi)的目標(biāo)定位，因此本文將測(cè)試區(qū)域分為25個(gè)1 km×1 km區(qū)域，并分別利用HNBG方法對(duì)各區(qū)域內(nèi)的目標(biāo)進(jìn)行定位，計(jì)算AQT-G。

圖9 各方法定位效率對(duì)比Figure 9 Comparison of geolocating efficiency

由圖9可知，所提方法在完整定位目標(biāo)過程中對(duì)目標(biāo)用戶報(bào)告距離的平均查詢次數(shù)為23.7次，遠(yuǎn)低于對(duì)比方法，具有更高的效率。SPBG方法在目標(biāo)發(fā)現(xiàn)過程中，除了使目標(biāo)出現(xiàn)在探針附近用戶列表中，還需限制目標(biāo)用戶的報(bào)告距離，從而需要更多的查詢次數(shù)。HNBG方法不存在目標(biāo)發(fā)現(xiàn)過程，因此其AQT-F為0，但其需要沿區(qū)域邊界部署大量探針以確定目標(biāo)用戶的初始坐標(biāo)，并在應(yīng)用一維數(shù)論方法精確定位目標(biāo)時(shí)，依然需要對(duì)目標(biāo)用戶報(bào)告距離進(jìn)行頻繁查詢，所需查詢次數(shù)最多。

綜上，相比現(xiàn)有典型的微信用戶位置推斷方法，本文所提方法具有更好的定位精度，且定位效率遠(yuǎn)高于現(xiàn)有方法。實(shí)驗(yàn)結(jié)果表明，當(dāng)前微信社交平臺(tái)對(duì)于用戶距離文本的隱私保護(hù)并不能有效防止用戶準(zhǔn)確距離的泄露，對(duì)報(bào)告距離文本的混淆有待進(jìn)一步加強(qiáng)。

7 結(jié)束語

為了驗(yàn)證當(dāng)前社交網(wǎng)絡(luò)對(duì)于用戶位置隱私保護(hù)的有效性，本文提出了一種基于加權(quán)最小二乘的社交網(wǎng)絡(luò)用戶定位方法。利用該方法對(duì)微信用戶開展了實(shí)際定位，結(jié)果表明，微信現(xiàn)有位置隱私保護(hù)機(jī)制不能有效防止用戶位置隱私泄露，仍需在保證服務(wù)質(zhì)量的前提下進(jìn)一步加強(qiáng)對(duì)距離文本的混淆強(qiáng)度。本文工作期望能加強(qiáng)社交平臺(tái)對(duì)于用戶位置隱私保護(hù)的重視。為了抵御本文提出的定位方法，一種可行的方案是服務(wù)提供商對(duì)報(bào)告距離對(duì)應(yīng)的真實(shí)距離邊界進(jìn)行定時(shí)更新，從而縮短定位參數(shù)的有效時(shí)間域，增大定位用戶所需的代價(jià)。此外，基于差分隱私等的隱私增強(qiáng)方法[23-24]的盡快應(yīng)用將進(jìn)一步提升用戶位置隱私的安全性。