林文敏，張 松，劉加邦

1.杭州師范大學(xué)阿里巴巴商學(xué)院，杭州311121

2.南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，南京210023

隨著無線通信技術(shù)及全球定位系統(tǒng)（global positioning system,GPS）技術(shù)的廣泛應(yīng)用，涌現(xiàn)出較多基于地理位置的服務(wù)（location-based services,LBS）.基于地理位置的服務(wù)執(zhí)行過程一般包括兩個(gè)步驟：首先，用戶向位置服務(wù)提供商（location service provider,LSP）發(fā)送一條包含其自身地理位置和所需服務(wù)的請(qǐng)求；然后，位置服務(wù)提供商返回給用戶相應(yīng)的結(jié)果.例如用戶在使用美團(tuán)點(diǎn)評(píng)時(shí)，首先選擇自身的地理位置，然后選擇需要查詢的內(nèi)容，接著將上述信息發(fā)送給美團(tuán)點(diǎn)評(píng)服務(wù)提供商后，其服務(wù)器經(jīng)過一系列計(jì)算返回給用戶相應(yīng)的查詢結(jié)果.

在實(shí)際應(yīng)用中，基于地理位置的服務(wù)為人們?nèi)粘Ｉ詈凸ぷ魈峁┝藰O大的便利.然而，用戶在享受這種便利的同時(shí)，也面臨著一定程度的隱私泄露風(fēng)險(xiǎn).例如，一些LSP 或研究機(jī)構(gòu)具有對(duì)用戶的地理位置及用戶請(qǐng)求進(jìn)行分析的潛在可能性[1].LSP通過收集用戶的請(qǐng)求，分析用戶請(qǐng)求中的位置屬性及內(nèi)容屬性，可以推測(cè)出用戶的個(gè)人信息、行為偏好、身體狀況[2].例如，某些用戶發(fā)送的服務(wù)請(qǐng)求中經(jīng)常包含某醫(yī)院地點(diǎn)，那么LSP 就可以推測(cè)出用戶的身體狀況.

關(guān)于隱私問題的研究通常包括隱私挖掘和隱私保護(hù)兩個(gè)方面.1）隱私挖掘是指對(duì)用戶的請(qǐng)求進(jìn)行數(shù)據(jù)分析，根據(jù)用戶社會(huì)屬性的不同可以將隱私挖掘分成兩類：一類是面向具有危害性社會(huì)屬性的用戶（如犯罪分子），如在案件偵破過程中需要對(duì)用戶隱私進(jìn)行挖掘分析，從而快速地偵破案件.Iqbal等[3]提出了利用數(shù)據(jù)挖掘分析犯罪分子的數(shù)據(jù)請(qǐng)求，從而協(xié)助警方更快地偵破案件.另一類是面向社會(huì)中正常生活的用戶，此類隱私挖掘的應(yīng)用通常指通過收集用戶的請(qǐng)求來挖掘用戶隱私信息，進(jìn)而利用用戶的隱私信息進(jìn)行金融詐騙或者勒索敲詐[4].2）隱私保護(hù)是從為用戶提供更好服務(wù)的角度，通過挖掘用戶的位置隱私屬性獲取用戶的個(gè)性化需求，從而提高服務(wù)質(zhì)量.Chatzidimitris 等[5]提出了對(duì)用戶歷史請(qǐng)求記錄進(jìn)行挖掘分析獲得用戶的位置隱私屬性，進(jìn)而為用戶提供智能個(gè)性化的推薦.

本文主要考慮正常用戶的位置隱私保護(hù)需求，常見的位置隱私研究工作也是以此為立足點(diǎn).為了解決位置隱私保護(hù)的問題，大量研究工作[6-13]普遍采用引入第三方服務(wù)器的k-匿名方法[14]及一系列基于k-匿名方法的變種.在這些工作中，基于假人的方法是最流行的方法之一[15].該方法通過產(chǎn)生一組虛假的位置且與真實(shí)的位置混合在一起發(fā)送給位置服務(wù)提供商的云服務(wù)器，在云服務(wù)器返回結(jié)果后，用戶本地客戶端篩選出用戶需要的結(jié)果.通過這種方法將用戶的真實(shí)位置藏匿在一組位置數(shù)據(jù)中，因此用戶的真實(shí)位置只有一定概率被識(shí)別，從而保護(hù)用戶的位置隱私信息.本文基于該方法在之前的工作中也做了一些完善工作[16-17].

然而，現(xiàn)有基于假人的方法大多忽略了常規(guī)的云服務(wù)器離用戶距離較遠(yuǎn)的情況，同時(shí)云服務(wù)器也需要傳輸大量數(shù)據(jù)包給用戶，導(dǎo)致用戶得到結(jié)果的時(shí)延可能是傳輸一條真實(shí)數(shù)據(jù)的k倍，這樣會(huì)影響用戶的位置服務(wù)體驗(yàn).新興的邊緣計(jì)算正是為了解決云計(jì)算服務(wù)器離用戶距離過遠(yuǎn)導(dǎo)致的時(shí)延問題，因此我們將以往在云服務(wù)器環(huán)境中使用基于假人的隱私保護(hù)方法遷移到現(xiàn)有的邊緣服務(wù)器環(huán)境中，在滿足用戶位置隱私保護(hù)需求的情況下，盡可能的減少用戶得到結(jié)果的時(shí)延.

本文的主要工作包括以下3 點(diǎn)：

1）分析了云環(huán)境下位置隱私保護(hù)方法存在的不足之處，如在某些情況下會(huì)造成用戶的時(shí)延大幅上升.

2）針對(duì)上述問題，將位置隱私保護(hù)方法從云計(jì)算場(chǎng)景遷移到邊緣計(jì)算場(chǎng)景下進(jìn)行部署，并針對(duì)邊緣計(jì)算的特點(diǎn)：資源有上限、覆蓋范圍有局限性，設(shè)計(jì)了面向位置隱私保護(hù)的中繼分流模型.

3）在真實(shí)數(shù)據(jù)集上對(duì)中繼分流模型中的假位置產(chǎn)生算法與分流算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并與相關(guān)論文中的算法做分析對(duì)比.

1 背景介紹

用戶發(fā)送的位置服務(wù)請(qǐng)求中通常包含多種內(nèi)容：用戶的位置信息、服務(wù)請(qǐng)求內(nèi)容、其他信息（如設(shè)備的IP 地址等），如式(1)所示.

為了達(dá)到保護(hù)位置隱私的目的，現(xiàn)有基于假人的方法是為用戶生成k ?1 個(gè)假位置，并將這k ?1 個(gè)假位置連同用戶的真實(shí)位置信息一同發(fā)送給云服務(wù)器，具體執(zhí)行流程如圖1所示.

圖1 基于假人方法的位置隱私保護(hù)流程（云服務(wù)器）Figure 1 Location privacy protection process of dummy-based method (deployed in cloud servers)

現(xiàn)有方法在理論上可以達(dá)到1/k的保護(hù)效果，但面臨著用戶獲得結(jié)果的高時(shí)延問題.通常情況下用戶距離云服務(wù)器較遠(yuǎn)，當(dāng)使用現(xiàn)有位置隱私保護(hù)方法后，用戶需要給云服務(wù)器發(fā)送大量數(shù)據(jù)，因此用戶獲得結(jié)果的時(shí)延理論上是之前的k倍.

邊緣計(jì)算概念的提出，為解決云服務(wù)器距離用戶較遠(yuǎn)導(dǎo)致的用戶時(shí)延問題提供了可行的技術(shù)途徑。鑒于此，針對(duì)上述位置隱私保護(hù)方法中的用戶時(shí)延問題，提出將現(xiàn)有位置隱私保護(hù)方法遷移到邊緣計(jì)算環(huán)境下進(jìn)行部署的方案，執(zhí)行流程如圖2所示.類似地，用戶首先需要基于假人方法生成k ?1 個(gè)假位置，之后再將這k ?1 個(gè)假位置連同用戶的真實(shí)位置信息一同發(fā)送給邊緣服務(wù)器.

圖2 基于假人方法的位置隱私保護(hù)流程（邊緣服務(wù)器）Figure 2 Location privacy protection process of dummy-based method (deployed in edge servers)

理論上而言，該方案可在為用戶提供k匿名的同時(shí)，保證用戶請(qǐng)求的低時(shí)延.然而，在現(xiàn)實(shí)情況下，不同地區(qū)的用戶分布是不同的，因此不同地區(qū)的邊緣服務(wù)器的負(fù)載也存在很大差異.當(dāng)一個(gè)用戶（稱之為目標(biāo)用戶）所在區(qū)域的邊緣服務(wù)器恰好處在高負(fù)載或滿負(fù)荷運(yùn)行的狀態(tài)難以提供正常的服務(wù)時(shí)，用戶便難以向邊緣服務(wù)器發(fā)送匿名請(qǐng)求.如圖3所示，當(dāng)邊緣服務(wù)器的用戶過多時(shí)造成服務(wù)器滿載（紅色），其余該區(qū)域的用戶便無法向此邊緣服務(wù)器發(fā)送請(qǐng)求.

圖3 邊緣服務(wù)器無法完成基于假人方法的位置隱私保護(hù)的情況示例圖Figure 3 Case where an edge server is unable to complete dummy-based location privacy protection

為了解決上述問題，本文考慮不同邊緣服務(wù)器的負(fù)載情況，在滿足用戶匿名需求的前提下，通過分流技術(shù)實(shí)現(xiàn)邊緣服務(wù)器的負(fù)載均衡，以盡可能降低用戶的時(shí)延.本文構(gòu)建了面向位置隱私保護(hù)的中繼分流模型并對(duì)模型中的分流方法進(jìn)行求解.

2 相關(guān)工作

2.1 位置隱私保護(hù)

近年來，許多研究人員關(guān)注位置隱私保護(hù)問題并提出了一系列解決方法.在這些方法中，基于假位置的方法是最流行的方法之一.早期工作中，Kido 等[18]將假人方法引入位置隱私保護(hù)中，利用隨機(jī)行走模型在用戶端為每個(gè)請(qǐng)求生成一組符合真實(shí)世界請(qǐng)求頻率的假位置，而將上述假位置與真實(shí)位置混合后一起發(fā)送給服務(wù)器.上述真假位置混合的策略使服務(wù)器無法直接識(shí)別用戶的真實(shí)位置.Lu等[19]提出了CirDummy 和GridDummy 兩種虛擬位置生成方案，實(shí)現(xiàn)了考慮隱私區(qū)域的k-匿名.

然而，上述方法忽略了對(duì)手可能具有側(cè)信息的問題.若這些方法產(chǎn)生的假人位于湖泊或崎嶇的山區(qū)，那么攻擊者會(huì)直接識(shí)別出這些假位置，從而降低假人方法為用戶提供的匿名保護(hù)效果.Niu等[20]則在考慮到對(duì)手可能擁有側(cè)信息的情況下謹(jǐn)慎地選擇虛擬位置，該方法根據(jù)熵度量選擇這些假位置，然后使被選擇的假位置分布得盡可能遠(yuǎn).此外，為了進(jìn)一步降低隱私泄露的風(fēng)險(xiǎn)，Niu 等[21]將查詢獲得的服務(wù)數(shù)據(jù)進(jìn)行緩存，并利用緩存的數(shù)據(jù)來應(yīng)答未來的查詢，從而減少發(fā)送到LBS 服務(wù)器的查詢.通過這種方式，減少了發(fā)送到LBS 服務(wù)器的請(qǐng)求數(shù)據(jù)量，從而保護(hù)用戶的位置隱私.

此外，研究人員逐漸開始考慮到用戶移動(dòng)時(shí)的時(shí)間和空間連續(xù)性對(duì)位置隱私保護(hù)的作用.例如，Liu等[9]提出了基于用戶移動(dòng)的時(shí)間和空間連續(xù)性的位置隱私保護(hù)策略，首先使用基礎(chǔ)方案來生成初始假位置候選集合，然后從時(shí)間可達(dá)性、方向相似度、出/入度這三個(gè)方面分析了相鄰位置集之間的時(shí)空相關(guān)性.

2.2 邊緣計(jì)算中的計(jì)算分流

邊緣服務(wù)器的服務(wù)能力與覆蓋范圍有限，計(jì)算分流則是通過將用戶的請(qǐng)求分流至鄰近空閑邊緣服務(wù)器中執(zhí)行，以實(shí)現(xiàn)邊緣服務(wù)器的負(fù)載均衡和用戶請(qǐng)求的及時(shí)響應(yīng).針對(duì)計(jì)算分流問題，研究人員提出了一系列分流策略.基于這些分流策略，移動(dòng)云計(jì)算為移動(dòng)設(shè)備提供了執(zhí)行計(jì)算密集型應(yīng)用程序的環(huán)境支撐.例如，Guo 等[22]提出了一種節(jié)能的動(dòng)態(tài)分流和資源調(diào)度策略，以減少能源消耗和縮短應(yīng)用完成時(shí)間.Chen 等[23]提出了一種高效的三步算法，聯(lián)合優(yōu)化所有用戶任務(wù)的分流決策，最小化所有用戶的總能量、計(jì)算和延遲成本.Wang 等[24]研究了移動(dòng)用戶在未配備強(qiáng)大計(jì)算設(shè)備的遺留車輛中的計(jì)算卸載問題.

上述計(jì)算分流方法適用于靜態(tài)場(chǎng)景下的計(jì)算分流.當(dāng)涉及動(dòng)態(tài)場(chǎng)景時(shí)，在何處運(yùn)行用戶的移動(dòng)請(qǐng)求及如何分配計(jì)算資源的決策也引起了研究人員的關(guān)注.例如，Hu 等[25]設(shè)計(jì)了一個(gè)稱為最大效率優(yōu)先排序算法的任務(wù)分流算法，以實(shí)現(xiàn)接近最優(yōu)的計(jì)算分流效率.Tang 等[26]提出了一種具有截流意識(shí)和成本效益的分流算法，該算法在考慮霧服務(wù)器分布的情況下提高計(jì)算分流效率.Zhang 等[27]提出了將車輛云與基于基礎(chǔ)設(shè)施的云相結(jié)合，擴(kuò)展當(dāng)前可用的資源，用于智能手機(jī)的任務(wù)請(qǐng)求.Josilo 等[28]提出了一種新穎的方法來解決邊緣計(jì)算系統(tǒng)中向一組自主無線設(shè)備分配無線和計(jì)算資源的問題.

在實(shí)際應(yīng)用中，考慮到邊緣計(jì)算環(huán)境下的位置隱私保護(hù)問題時(shí)，還需要考慮每個(gè)邊緣服務(wù)器對(duì)服務(wù)的覆蓋都是有限的，從而會(huì)導(dǎo)致現(xiàn)有的位置隱私保護(hù)算法無法為用戶提供位置隱私保護(hù)的服務(wù).在這種情況下，現(xiàn)有的位置隱私保護(hù)算法的效果可能面臨失效的技術(shù)挑戰(zhàn).

3 建模預(yù)備知識(shí)

為了解決第1 節(jié)背景介紹中描述的問題，本文提出基于中繼的計(jì)算分流方法.具體而言，當(dāng)一個(gè)目標(biāo)用戶所在區(qū)域的邊緣服務(wù)器處于高負(fù)載或滿負(fù)荷運(yùn)行狀態(tài)而難以提供正常的服務(wù)時(shí)，其附近的區(qū)域仍可能存在可以正常提供服務(wù)的邊緣服務(wù)器.本文通過選用處在可用服務(wù)器服務(wù)范圍中的用戶作為中繼，利用近程通信技術(shù)[29]使目標(biāo)用戶可以選用負(fù)載低的邊緣服務(wù)器獲取基于位置的服務(wù).目前，已有相關(guān)研究[30]證實(shí)了這種基于中繼輔助的分流方法的可行性.圖4中通過一個(gè)具體的例子來展示基于中繼的計(jì)算分流方法在位置隱私保護(hù)中的應(yīng)用.紅色邊緣服務(wù)器因服務(wù)范圍內(nèi)用戶眾多而處于滿載狀態(tài)，因此該邊緣服務(wù)器難以處理目標(biāo)用戶的請(qǐng)求.為了獲取邊緣服務(wù)器的服務(wù)，目標(biāo)用戶通過中繼將服務(wù)請(qǐng)求發(fā)送至可以正常運(yùn)行的低負(fù)載邊緣服務(wù)器中進(jìn)行計(jì)算處理.

圖4 基于中繼的分流方法在位置隱私保護(hù)中的應(yīng)用示例Figure 4 Application example of relay-assisted offloading approach in location privacy protection

本文所提出的基于中繼的分流方法適用于準(zhǔn)靜態(tài)環(huán)境中計(jì)算分流問題，即用戶在該過程中的位置不會(huì)出現(xiàn)較大的變化.在未來的工作中會(huì)進(jìn)一步討論關(guān)于動(dòng)態(tài)環(huán)境中基于中繼的分流方法在位置隱私保護(hù)中的應(yīng)用問題.

本文中，k表示基于假人方法（下文簡(jiǎn)稱假人方法）的匿名度，它表示假人方法為用戶生成了k ?1 個(gè)假位置.更高的匿名度意味著更強(qiáng)的隱私保護(hù)能力，當(dāng)用戶需要的匿名度過高時(shí)，受限于接受設(shè)備的處理能力，以及目標(biāo)設(shè)備的網(wǎng)絡(luò)狀況和設(shè)備性能，存在目標(biāo)服務(wù)器服務(wù)能力不匹配的潛在問題.在實(shí)際情況中，假設(shè)接收設(shè)備能接受kre個(gè)請(qǐng)求，其中kre ?1 個(gè)請(qǐng)求包含的是假位置.基于kre與k的數(shù)量關(guān)系，本文給出如下定義：

定義1強(qiáng)數(shù)量請(qǐng)求（Strong Quantity Request）：當(dāng)krek時(shí)，稱終端設(shè)備發(fā)出的請(qǐng)求為強(qiáng)數(shù)量請(qǐng)求，數(shù)量為k.

定義2弱數(shù)量請(qǐng)求（Weak Quantity Request）：當(dāng)kre < k時(shí)，稱終端設(shè)備發(fā)出請(qǐng)求為弱數(shù)量請(qǐng)求，數(shù)量上限為kre.

由于不同用戶對(duì)匿名度的要求不同，對(duì)強(qiáng)、弱數(shù)量請(qǐng)求的劃分標(biāo)準(zhǔn)也不同.本文目標(biāo)用戶需要發(fā)送min(kre,k)個(gè)請(qǐng)求到中繼.考慮到目標(biāo)用戶所持設(shè)備的性能和網(wǎng)絡(luò)狀況，以及被選作中繼的不同用戶，其所持有的終端設(shè)備的請(qǐng)求處理能力也是不同的，因此kre的值也需要發(fā)生相應(yīng)的變化.本文使用us表示目標(biāo)用戶所持設(shè)備的當(dāng)前狀態(tài)，rs表示作為中繼的用戶的所持設(shè)備的狀態(tài)，es表示邊緣服務(wù)器的狀態(tài).假設(shè)這個(gè)3 個(gè)變量的取值集合均為{?1,0,1}.–1表示終端設(shè)備或邊緣服務(wù)器處于宕機(jī)狀態(tài)，即不能處理任何請(qǐng)求；0 表示終端設(shè)備或者邊緣服務(wù)器僅能處理少量請(qǐng)求，處于該狀態(tài)時(shí)終端設(shè)備或邊緣服務(wù)器僅能發(fā)出或接受弱數(shù)量請(qǐng)求；1則表示終端設(shè)備或服務(wù)器狀態(tài)良好，可以處理高匿名度的請(qǐng)求且能夠發(fā)出或接受強(qiáng)數(shù)量請(qǐng)求.本文目標(biāo)用戶所處區(qū)域的邊緣服務(wù)器一定滿足es ?1.基于上述對(duì)目標(biāo)用戶、中繼及邊緣服務(wù)器的狀態(tài)討論，本文給出如下定義：

定義3邊緣服務(wù)狀態(tài)（Edge Service Status）

邊緣服務(wù)狀態(tài)s=min{rs,es}表示中繼及其所在區(qū)域的邊緣服務(wù)器組成的整體所處的狀態(tài).

定義4強(qiáng)保護(hù)狀態(tài)（Strong Protection Status）

目標(biāo)用戶處于強(qiáng)保護(hù)狀態(tài)是指目標(biāo)用戶狀態(tài)滿足us=1，目標(biāo)用戶選擇的中繼與中繼所在區(qū)域的邊緣服務(wù)器的邊緣服務(wù)狀態(tài)滿足s=1.

強(qiáng)保護(hù)狀態(tài)的示意圖如圖5(a)所示.處于強(qiáng)保護(hù)狀態(tài)時(shí)，目標(biāo)用戶可以向外發(fā)出強(qiáng)數(shù)量請(qǐng)求，中繼接收到目標(biāo)用戶的強(qiáng)數(shù)量請(qǐng)求后將其發(fā)送至邊緣服務(wù)器.邊緣服務(wù)器處理完請(qǐng)求后將結(jié)果按原路徑返回.

定義5弱保護(hù)狀態(tài)（Weak Protection Status）

目標(biāo)用戶處于弱保護(hù)狀態(tài)是指目標(biāo)用戶狀態(tài)滿足us=0，目標(biāo)用戶選擇的中繼與中繼所在區(qū)域的邊緣服務(wù)器的邊緣服務(wù)狀態(tài)滿足s≥0.

弱保護(hù)狀態(tài)的示意圖如圖5(b)所示.處于弱保護(hù)狀態(tài)時(shí)，目標(biāo)用戶僅能向外發(fā)出弱數(shù)量請(qǐng)求，中繼接收到目標(biāo)用戶的弱數(shù)量請(qǐng)求后將其發(fā)送至邊緣服務(wù)器.邊緣服務(wù)器處理完請(qǐng)求后將結(jié)果按原路徑返回.

定義6聯(lián)合保護(hù)狀態(tài)（Union Protection Status）

目標(biāo)用戶處于聯(lián)合保護(hù)狀態(tài)是指目標(biāo)用戶狀態(tài)滿足us=0，目標(biāo)用戶選擇的中繼與中繼所在區(qū)域的邊緣服務(wù)器的聯(lián)合服務(wù)狀態(tài)滿足s=1.

聯(lián)合保護(hù)狀態(tài)的示意圖如圖5(c)所示.處于聯(lián)合保護(hù)狀態(tài)時(shí)，目標(biāo)設(shè)備自身僅能發(fā)出弱數(shù)量請(qǐng)求，但中繼可在目標(biāo)設(shè)備發(fā)出請(qǐng)求的基礎(chǔ)上加入新的假位置，進(jìn)而構(gòu)成強(qiáng)數(shù)量請(qǐng)求.之后，中繼會(huì)將強(qiáng)數(shù)量請(qǐng)求發(fā)送給邊緣服務(wù)器，邊緣服務(wù)器處理完請(qǐng)求后將結(jié)果按原路徑返回.

定義7極限保護(hù)狀態(tài)（Limit Protection Status）

目標(biāo)設(shè)備滿足us=1 且目標(biāo)設(shè)備可以選擇多個(gè)處于不同邊緣服務(wù)器服務(wù)范圍的中繼，這些中繼與其所在區(qū)域的邊緣服務(wù)器的聯(lián)合服務(wù)狀態(tài)均滿足s=0.

圖5 4 種不同保護(hù)狀態(tài)Figure 5 Four different protection status

極限保護(hù)狀態(tài)的示意圖見圖5(d)所示.處于極限保護(hù)狀態(tài)時(shí)，目標(biāo)用戶會(huì)選中多個(gè)中繼，然后將強(qiáng)數(shù)量請(qǐng)求分成多個(gè)弱數(shù)量請(qǐng)求分別發(fā)送給中繼.中繼接收到目標(biāo)用戶的請(qǐng)求后，會(huì)將請(qǐng)求發(fā)送給自己所在區(qū)域的邊緣服務(wù)器.邊緣服務(wù)器處理完請(qǐng)求后，會(huì)將結(jié)果按原路徑返回.

從上述定義可以看出，強(qiáng)保護(hù)狀態(tài)對(duì)目標(biāo)用戶、中繼和邊緣服務(wù)器均有較高的要求，要求三者的狀態(tài)值均為1.聯(lián)合保護(hù)狀態(tài)則允許目標(biāo)設(shè)備在自身能力不足的情況下也可以利用中繼發(fā)出強(qiáng)數(shù)量請(qǐng)求，進(jìn)而獲得較高的安全性.極限保護(hù)狀態(tài)則是在目標(biāo)用戶所持設(shè)備性能充足的前提下，利用多個(gè)中繼發(fā)出強(qiáng)數(shù)量請(qǐng)求.弱保護(hù)狀態(tài)則是一種極為特殊情況，即目標(biāo)用戶自身性能不足且附近沒有可以發(fā)出強(qiáng)數(shù)量請(qǐng)求的中繼.

4 面向位置隱私保護(hù)的中繼分流模型

基于上文中定義的4 種保護(hù)狀態(tài)，建立面向位置隱私保護(hù)的中繼分流模型.需要注意的是，本文不考慮狀態(tài)值us=?1 的情形，是因?yàn)榇藭r(shí)目標(biāo)設(shè)備已經(jīng)處于宕機(jī)狀態(tài)，無法發(fā)出任何請(qǐng)求.圖5展示了上述不同保護(hù)狀態(tài)下目標(biāo)用戶與中繼和邊緣服務(wù)器的交互情況.

假設(shè)每個(gè)目標(biāo)用戶都是理性的，即總是希望找到使得自身獲利最大的分流方法.據(jù)此，建立如下模型：

式(2)為模型的優(yōu)化目標(biāo)，即使目標(biāo)用戶獲得最大效用；式(3)表示在該模型中至少會(huì)使用一個(gè)中繼；式(4)則是對(duì)中繼的約束條件，表示中繼需要既能與目標(biāo)用戶通信獲取目標(biāo)用戶發(fā)出的位置服務(wù)請(qǐng)求，又能與邊緣服務(wù)器通信進(jìn)行數(shù)據(jù)交互.下文對(duì)模型內(nèi)的各部分進(jìn)行詳細(xì)解釋，重要符號(hào)如表1所示.

表1 主要符號(hào)及其含義Table 1 Key terms and notation

在本文中，假設(shè)每條位置服務(wù)請(qǐng)求p的大小為mp；目標(biāo)用戶發(fā)出的請(qǐng)求數(shù)量為，這些請(qǐng)求構(gòu)成的集合為Cu；中繼所持設(shè)備發(fā)出的請(qǐng)求數(shù)量為，請(qǐng)求所構(gòu)成的集合為Cr；中繼所構(gòu)成的集合為Mr；yr表示中繼集合中的待選中繼r是否被選中為中繼，則yr={0,1}.在位置服務(wù)請(qǐng)求的傳輸過程中，中繼用戶所持的設(shè)備會(huì)依據(jù)邊緣服務(wù)狀態(tài)決定是否為目標(biāo)用戶發(fā)出的弱數(shù)量請(qǐng)求生成額外的假位置，因此會(huì)存在且滿足Cu ?Cr.本文考慮如下5 個(gè)原子模塊.

1）請(qǐng)求上行

目標(biāo)用戶的位置服務(wù)請(qǐng)求發(fā)送至邊緣服務(wù)器的整個(gè)過程.位置服務(wù)請(qǐng)求首先由目標(biāo)用戶發(fā)出，在使用中繼的情況下請(qǐng)求會(huì)先到達(dá)中繼，再由中繼發(fā)出到達(dá)邊緣服務(wù)器.整個(gè)過程中，請(qǐng)求上行的時(shí)間tup滿足

式中，d為中繼的傳輸速率，Re為邊緣服務(wù)器e的傳輸速率.

2）請(qǐng)求下行

邊緣服務(wù)器將位置服務(wù)請(qǐng)求處理完成的結(jié)果發(fā)送給目標(biāo)用戶的過程.在使用中繼的情況下，邊緣服務(wù)器返回的結(jié)果會(huì)先到達(dá)中繼，再由中繼將結(jié)果發(fā)送給目標(biāo)用戶.整個(gè)過程中，請(qǐng)求下行的時(shí)間tdown滿足

式中，pr表示來自邊緣服務(wù)器的處理結(jié)果；Cer表示邊緣服務(wù)器發(fā)出的結(jié)果集合；Ceu表示中繼發(fā)出的結(jié)果集合.每個(gè)發(fā)出位置服務(wù)請(qǐng)求的設(shè)備內(nèi)部會(huì)記錄自己所生成的位置服務(wù)請(qǐng)求，當(dāng)中繼接收到來自邊緣服務(wù)器的處理結(jié)果后，若在其中發(fā)現(xiàn)了自己生成的假位置服務(wù)請(qǐng)求則將這些結(jié)果過濾掉，之后再將結(jié)果返回給目標(biāo)用戶.因此，Cer和Ceu之間滿足Cer ?Ceu.

3）請(qǐng)求處理

邊緣服務(wù)器接收到目標(biāo)用戶的請(qǐng)求集合進(jìn)行請(qǐng)求處理的過程.整個(gè)過程中請(qǐng)求處理的時(shí)間te滿足

式中，qe表示邊緣服務(wù)器e的處理能力；fp表示請(qǐng)求p的計(jì)算工作量.

4）假位置生成

目標(biāo)用戶或中繼為位置服務(wù)請(qǐng)求依據(jù)假人方法生成假位置的過程.其中假位置生成所需的時(shí)間滿足

式中，tp表示單個(gè)請(qǐng)求p的生成時(shí)間；C表示生成的請(qǐng)求集合；則表示請(qǐng)求集合C中的所有請(qǐng)求所耗費(fèi)的時(shí)間.

5）激勵(lì)模塊

在實(shí)際應(yīng)用中，服務(wù)請(qǐng)求者需要為其請(qǐng)求的基于位置服務(wù)支付一定的費(fèi)用，以從中繼和邊緣服務(wù)器處獲得更好的服務(wù)，為此本文提出了針對(duì)中繼和邊緣服務(wù)器的激勵(lì)模塊.

為了激勵(lì)更多的用戶自發(fā)充當(dāng)中繼，需要依據(jù)中繼在服務(wù)請(qǐng)求過程中做出的貢獻(xiàn)為中繼用戶付出一定的報(bào)酬.這里，本文使用?up表示在請(qǐng)求上行階段，用戶單位時(shí)間需要為中繼用戶付出的報(bào)酬；?down表示在請(qǐng)求下行階段，用戶單位時(shí)間需要為中繼用戶付出的報(bào)酬.同時(shí)在聯(lián)合保護(hù)狀態(tài)下，中繼需要為用戶額外生成假位置.假設(shè)在此過程中，中繼每生成一條額外的假位置服務(wù)請(qǐng)求，目標(biāo)用戶就需要支付報(bào)酬?，則在位置服務(wù)請(qǐng)求的整個(gè)過程中，中繼所獲得激勵(lì)滿足

此外，用戶還需要為從邊緣服務(wù)器獲取的資源付費(fèi).ρe表示單位時(shí)間內(nèi)使用邊緣服務(wù)器e所需支付的費(fèi)用.則邊緣服務(wù)器所獲得的激勵(lì)滿足

當(dāng)目標(biāo)用戶向邊緣服務(wù)器發(fā)出位置服務(wù)請(qǐng)求時(shí)，具體的執(zhí)行過程可以分為兩個(gè)部分.一是假位置生成部分，二是請(qǐng)求傳輸和處理部分.

具體的假位置生成算法見下文5.1 節(jié)算法1，該算法可能在兩個(gè)環(huán)節(jié)運(yùn)行：一是基于目標(biāo)用戶的位置信息，在目標(biāo)用戶的設(shè)備上生成假位置的過程；二是在聯(lián)合保護(hù)狀態(tài)時(shí)，中繼設(shè)備還會(huì)為用戶生成一次假位置.則假位置生成所耗費(fèi)的時(shí)間tdum滿足

式中，表示目標(biāo)設(shè)備生成請(qǐng)求所耗費(fèi)的時(shí)間，表示中繼生成請(qǐng)求所耗費(fèi)的時(shí)間.

在請(qǐng)求傳輸和處理部分涉及請(qǐng)求上行模塊、請(qǐng)求處理模塊以及請(qǐng)求下行模塊.該過程所耗費(fèi)的時(shí)間tc滿足

根據(jù)以上模型的原子部分，組成式(2)中表示的面向位置隱私保護(hù)的中繼分流模型.

5 基于中繼的服務(wù)請(qǐng)求分流方法

第4 節(jié)提出了面向位置隱私保護(hù)的中繼分流模型，本節(jié)將給出基于中繼的服務(wù)請(qǐng)求分流方法.首先，針對(duì)上述問題，圖6中給出了問題求解的執(zhí)行流程圖.

圖6 面向位置隱私保護(hù)的中繼分流方法執(zhí)行流程圖Figure 6 Flowchart of the relay-assisted offloading method for location privacy protection

目標(biāo)用戶需要請(qǐng)求基于位置的服務(wù)時(shí)，會(huì)將自己的位置信息和請(qǐng)求內(nèi)容作為輸入交給假人方法.假人方法根據(jù)用戶的位置信息生成若干個(gè)假位置構(gòu)成請(qǐng)求集合.為了讓用戶體驗(yàn)更好的服務(wù)，需要將請(qǐng)求集合上傳到邊緣服務(wù)器.在本文的場(chǎng)景下，目標(biāo)用戶需要先選擇合適的中繼，將請(qǐng)求集合通過中繼上傳到邊緣服務(wù)器進(jìn)行處理，最后得到請(qǐng)求結(jié)果.

5.1 假位置生成方法

信息熵作為信息度量的有效工具，在通信領(lǐng)域已展現(xiàn)出重要的貢獻(xiàn).隱私作為一種信息，可以考慮用熵來量化.本文用熵表示從所有位置中識(shí)別出真實(shí)位置的概率，選擇與Niu等[20]相同的熵的定義，將地圖劃分為N ×N個(gè)單元格.每個(gè)單元格都有1 個(gè)歷史查詢概率（稱為查詢概率），用變量qi表示，且對(duì)于查詢中包含的k個(gè)位置（即單元格），其中包含一個(gè)真實(shí)位置和k ?1 個(gè)假位置，每個(gè)位置都有一個(gè)成為實(shí)際位置的條件概率.設(shè)pi(i=1,2,···,k)表示第i個(gè)位置為真實(shí)位置的概率，則基于上述分析，得出熵H的定義為

算法1 描述了基于k-匿名的假位置生成算法，其目標(biāo)是使本文提出的位置隱私保護(hù)方法為用戶生成的假位置集合的熵最小.首先對(duì)每個(gè)單元格被查詢概率按照從大到小的順序進(jìn)行排序，接著在屬于時(shí)間段T的多個(gè)區(qū)間RT中選擇前2k/SIZE(RT)（SIZE (RT)為區(qū)間的個(gè)數(shù)）個(gè)單元格構(gòu)成候選區(qū)間集合CellT；然后在CellT中隨機(jī)挑選k個(gè)單元格計(jì)算由這k個(gè)單元格組成的假位置集合的熵，重復(fù)多次選擇熵最小的集合.

算法1基于k-匿名的假位置生成算法

輸入：每個(gè)區(qū)間的查詢概率qi，真實(shí)位置lreal，保護(hù)等級(jí)k，用戶歷史查詢區(qū)間Regionhistory迭代次數(shù)β

輸出：一組最優(yōu)的假位置集合Dummies

5.2 中繼選擇方法

目標(biāo)用戶所持設(shè)備的通信范圍內(nèi)的設(shè)備集合為cov(u)，邊緣服務(wù)器的通信范圍內(nèi)的設(shè)備集合為cov(e).作為中繼，r必須滿足r ∈cov(u)∩cov(e).滿足此條件的中繼用戶可以同時(shí)和目標(biāo)用戶與邊緣服務(wù)器通信.為了選擇適合的中繼，首先需要確定目標(biāo)用戶狀態(tài)和邊緣服務(wù)狀態(tài).目標(biāo)用戶可以依據(jù)自身的運(yùn)行情況獲得自身狀態(tài).為了獲得周圍設(shè)備的狀態(tài)，目標(biāo)用戶會(huì)先向周圍廣播獲取中繼的請(qǐng)求，接收到請(qǐng)求的設(shè)備會(huì)將邊緣服務(wù)狀態(tài)返回給目標(biāo)用戶.目標(biāo)用戶周圍可能分布著多個(gè)可能作為中繼的用戶，所以目標(biāo)用戶會(huì)得到一個(gè)邊緣服務(wù)狀態(tài)集合S={s1,s2,···,sn}.

同時(shí)，在邊緣計(jì)算環(huán)境中邊緣服務(wù)器大多采用密集部署，因此一個(gè)用戶可連接到多個(gè)邊緣服務(wù)器.假設(shè)用戶總是選擇狀態(tài)最佳的邊緣服務(wù)器，那么對(duì)于任意的si ∈S，si=min(rs,max()).這里，表示可以與用戶i的設(shè)備通信的邊緣服務(wù)器的服務(wù)狀態(tài).

得到周圍設(shè)備的邊緣服務(wù)狀態(tài)集合后，目標(biāo)用戶會(huì)查詢?cè)摷喜闹刑暨x出待選的中繼集合.具體的算法流程如算法2 所示.

算法2中繼選擇算法

輸入：目標(biāo)用戶的周圍設(shè)備的邊緣服務(wù)狀態(tài)集合S，目標(biāo)用戶服務(wù)狀態(tài)us

輸出：可作為中繼的用戶的邊緣狀態(tài)集合SC

算法2 給出了中繼設(shè)備的初步篩選方法.首先查詢目標(biāo)用戶狀態(tài)，若目標(biāo)用戶自身狀態(tài)不佳，則難以發(fā)出基于位置的服務(wù)請(qǐng)求，因此也就不需要中繼用戶.之后，算法會(huì)在從目標(biāo)用戶周圍的設(shè)備的邊緣服務(wù)狀態(tài)中篩選掉邊緣服務(wù)狀態(tài)為–1 的設(shè)備.本文稱構(gòu)成邊緣狀態(tài)集合的用戶為待選中繼，SC也稱為待選中繼邊緣服務(wù)狀態(tài)集合.

5.3 基于中繼的服務(wù)請(qǐng)求分流方法

在基于位置的服務(wù)請(qǐng)求中，用戶設(shè)備需要將所有請(qǐng)求上傳到邊緣服務(wù)器，交由邊緣服務(wù)器處理，邊緣服務(wù)器處理完請(qǐng)求后將請(qǐng)求結(jié)果返回給目標(biāo)用戶.在整個(gè)過程中，目標(biāo)用戶只需生成假位置信息，再將所有請(qǐng)求上傳至邊緣服務(wù)器.

目標(biāo)用戶設(shè)備將請(qǐng)求上傳至邊緣服務(wù)器之前需要先選擇中繼.執(zhí)行完算法2 后，目標(biāo)用戶會(huì)得到邊緣服務(wù)狀態(tài)集合.集合中的邊緣服務(wù)狀態(tài)所關(guān)聯(lián)的用戶均可充當(dāng)中繼，但選擇不同的中繼可能會(huì)使目標(biāo)用戶處于不同的保護(hù)狀態(tài)中.

本文中各種保護(hù)狀態(tài)并沒有優(yōu)先級(jí)，目標(biāo)用戶可以依據(jù)式(2)選擇合適的保護(hù)狀態(tài).不同保護(hù)狀態(tài)會(huì)造成不同請(qǐng)求數(shù)量和不同中繼數(shù)量.因此，在得到待選中繼的邊緣狀態(tài)集合后，需要依據(jù)目標(biāo)用戶自身狀態(tài)及待選中繼的邊緣狀態(tài)選擇合適的保護(hù)模式.根據(jù)保護(hù)狀態(tài)的定義，可知共可能會(huì)出現(xiàn)以下4 種情況：

情形1（強(qiáng)保護(hù)） 目標(biāo)用戶處于強(qiáng)保護(hù)狀態(tài)時(shí)，目標(biāo)用戶狀態(tài)us=1 且邊緣狀態(tài)集合滿足存在si ∈SC，且si=1.

情形2（弱保護(hù)） 目標(biāo)用戶處于弱保護(hù)狀態(tài)時(shí)，目標(biāo)用戶狀態(tài)us=0 且邊緣狀態(tài)集合滿足存在si ∈SC，且si=0.

選中弱保護(hù)狀態(tài)后，目標(biāo)用戶僅會(huì)發(fā)送弱數(shù)量請(qǐng)求，且中繼僅發(fā)送弱數(shù)量請(qǐng)求就可以滿足目標(biāo)用戶的要求.因此僅需一個(gè)中繼就可以完成分流任務(wù)，與強(qiáng)保護(hù)類似，中繼不會(huì)額外生成假位置，則有

情形3（聯(lián)合保護(hù)） 目標(biāo)用戶處于聯(lián)合保護(hù)狀態(tài)時(shí)，目標(biāo)用戶狀態(tài)us=0，邊緣狀態(tài)集合滿足存在si ∈SC，且si=1.

處于聯(lián)合保護(hù)狀態(tài)時(shí)，目標(biāo)用戶發(fā)出弱數(shù)量請(qǐng)求后，中繼需要為目標(biāo)用戶生成額外的假位置.此時(shí)

情形4（極限保護(hù)） 目標(biāo)用戶處于極限保護(hù)狀態(tài)時(shí)，目標(biāo)用戶狀態(tài)us=1，滿足邊緣狀態(tài)集合，存在n個(gè)邊緣狀態(tài)s ∈SC，對(duì)于每個(gè)s，滿足s=0.

在極限保護(hù)狀態(tài)時(shí)，需要多個(gè)只能發(fā)出弱數(shù)量請(qǐng)求的中繼來分擔(dān)目標(biāo)用戶的強(qiáng)數(shù)量請(qǐng)求.因此由于在傳輸?shù)倪^程中，中繼并不會(huì)為目標(biāo)用戶生成額外的假位置，因此仍有

上述4 種情形是在實(shí)際的情形中可能遇到的情況.實(shí)際應(yīng)用中需要依據(jù)實(shí)際過程中得到的邊緣狀態(tài)集合、用戶狀態(tài)、式(2)選擇合適的保護(hù)狀態(tài).基于上述4 種情形，可以得到對(duì)應(yīng)的分流方法，如算法3 所示.算法3 描述了基于中繼的服務(wù)請(qǐng)求分流的過程.該算法先執(zhí)行算法1 生成服務(wù)請(qǐng)求集合，再執(zhí)行算法2 得到待選中繼的邊緣狀態(tài)集合.之后，依據(jù)自身的狀態(tài)及邊緣狀態(tài)集合中的各待選中繼的情況，找到使式(2)最大的中繼SR及請(qǐng)求的發(fā)送數(shù)量kr.

算法3基于中繼的服務(wù)請(qǐng)求分流算法

輸入：目標(biāo)用戶的周圍設(shè)備的邊緣服務(wù)狀態(tài)集合S，目標(biāo)用戶服務(wù)狀態(tài)us，α，匿名度k

輸出：實(shí)際發(fā)送請(qǐng)求數(shù)量kr，中繼集合SR

1 執(zhí)行算法1 得到包含k ?1 個(gè)假位置的服務(wù)請(qǐng)求集合

2 執(zhí)行算法2 得到待選中繼的邊緣狀態(tài)集合SC

3ifus=1then

4 遍歷集合SC，找到邊緣狀態(tài)s=1 的中繼，計(jì)算出情形1 時(shí)，式(2)的最大值，以及對(duì)應(yīng)的請(qǐng)求發(fā)送數(shù)量kr，中繼集合SR

5 遍歷集合SC，找到邊緣狀態(tài)s=0 的中繼，計(jì)算出情形4 時(shí)，式(2)的最大值，以及對(duì)應(yīng)的請(qǐng)求發(fā)送數(shù)量k，中繼集合SR

6ifus=0then

7 遍歷集合SC，找到邊緣狀態(tài)s=0 的中繼，計(jì)算出情形2 時(shí)，式(2)的最大值，以及對(duì)應(yīng)的請(qǐng)求發(fā)送數(shù)量k，中繼集合SR

8 遍歷集合SC，找到邊緣狀態(tài)s=1 的中繼，計(jì)算出情形3 時(shí)，式(2)的最大值，以及對(duì)應(yīng)的請(qǐng)求發(fā)送數(shù)量kr，中繼集合SR

9 找到使得式(11)最大的情形，得到對(duì)應(yīng)的k，SR；

10returnk，SR

在實(shí)際應(yīng)用場(chǎng)景中，邊緣服務(wù)器通常無法提供云服務(wù)器完全等價(jià)的功能.邊緣服務(wù)器通常僅擁有其所屬片區(qū)的數(shù)據(jù)或緩存而無法擁有全量的數(shù)據(jù)庫，一般情況下每一個(gè)邊緣服務(wù)器只能服務(wù)特定的片區(qū).在引入中繼之后，可能會(huì)出現(xiàn)用戶請(qǐng)求超出了邊緣服務(wù)器所屬片區(qū)的情形.本文對(duì)該情況做如下假設(shè)：當(dāng)用戶查詢請(qǐng)求超出邊緣服務(wù)器所屬片區(qū)時(shí)，需要將用戶請(qǐng)求轉(zhuǎn)發(fā)至擁有中央數(shù)據(jù)庫的云服務(wù)器進(jìn)行處理.

6 性能分析

如第5 節(jié)所述，基于中繼的服務(wù)請(qǐng)求分流方法主要包括3 個(gè)步驟：基于假人的位置選擇、中繼選擇、服務(wù)請(qǐng)求分流.下面將從計(jì)算復(fù)雜度的角度結(jié)合上述3 個(gè)步驟對(duì)本文所提出的基于中繼的服務(wù)請(qǐng)求分流方法進(jìn)行性能分析.

基于假人的位置選擇步驟中，首先需要對(duì)地圖中的N ×N個(gè)單元格按照其被查詢概率進(jìn)行排序.本文擬采用快速排序的方法對(duì)上述N2個(gè)單元格進(jìn)行排序，因此該操作需要的平均計(jì)算復(fù)雜度為O(N2lbN2).針對(duì)某一個(gè)特定查詢請(qǐng)求Q，需要基于歷史查詢記錄分別從與Q處在同一時(shí)間段T的查詢區(qū)間RT中選擇出前2k/SIZE(RT)個(gè)候選單元格.在上步操作中，各個(gè)單元格已按其被查詢概率進(jìn)行排序，因此該操作需要的平均計(jì)算復(fù)雜度為O(1)；進(jìn)一步地，從上述2k個(gè)候選單元格中隨機(jī)選擇k個(gè)單元格并進(jìn)行熵計(jì)算，計(jì)算復(fù)雜度為O(k)；同時(shí)，與目前的最大熵值進(jìn)行比較從而得到最優(yōu)位置集合Dummies，其計(jì)算復(fù)雜度為O(1).上述位置選擇過程需要重復(fù)β次，因此基于假人的位置選擇方法所需要的計(jì)算復(fù)雜度為O(N2lbN2+β×k)=O(N2lbN2)+β×(O(1)+O(k)+O(1)).

在中繼選擇步驟中，用戶需要在其所處區(qū)域邊緣服務(wù)器集合S中過濾掉服務(wù)狀態(tài)為–1 的設(shè)備，生成候選中繼邊緣服務(wù)器集合SC，因此該步驟需要的計(jì)算復(fù)雜度為O(n)=O(|S|).

服務(wù)請(qǐng)求分流步驟則是用戶在上述基于假人的位置選擇和中繼選擇的基礎(chǔ)上，根據(jù)其自身狀態(tài)及待選中繼的邊緣狀態(tài)選擇合適的保護(hù)模式，并選擇使式(2)效用值最大的中繼SR和請(qǐng)求數(shù)目kr.根據(jù)用戶選擇保護(hù)模式的不同，該步驟所需的計(jì)算復(fù)雜度也有所不同.具體而言，在強(qiáng)保護(hù)、弱保護(hù)和聯(lián)合保護(hù)模式下，目標(biāo)用戶僅需從候選集合中選擇一個(gè)中繼.因此，為使式(2)取得最大效用值，所需的計(jì)算復(fù)雜度為O(n)=O(|SC|).而在極限保護(hù)狀態(tài)下，目標(biāo)用戶則需要選擇x個(gè)（x>1）中繼來實(shí)現(xiàn)服務(wù)請(qǐng)求分流.x的取值范圍為[2,n]，因此在極限保護(hù)狀態(tài)下，計(jì)算復(fù)雜度為

綜上所述，在強(qiáng)保護(hù)、弱保護(hù)和聯(lián)合保護(hù)模式下，本文提出的基于中繼的服務(wù)請(qǐng)求分流方法的計(jì)算復(fù)雜度為O(N2lbN2+β×k+n).而在極限保護(hù)模式下，上述基于中繼的服務(wù)請(qǐng)求分流方法的計(jì)算復(fù)雜度為O(N2lbN2+β×k+2n).

7 實(shí)驗(yàn)評(píng)估

本節(jié)將介紹兩種基準(zhǔn)方法并通過大量實(shí)驗(yàn)對(duì)這兩種方法與本文提出的方法進(jìn)行對(duì)比分析，以驗(yàn)證本文提出方法的性能.所有實(shí)驗(yàn)均在配備Intel Core i5-8265U 處理器(8CPUs,1.60 GHz)，8GB RAM 的Windows 機(jī)器上進(jìn)行.

7.1 對(duì)比方法

本文首先提出了基于k-匿名的假人方法，在基于假人的方法中提出了基于中繼的服務(wù)請(qǐng)求分流方法.為了證明該方法的性能，本文將基于中繼的服務(wù)請(qǐng)求分流方法與以下兩種方法進(jìn)行對(duì)比，以證明基于中繼的服務(wù)請(qǐng)求方法的性能.

1）邊-云執(zhí)行：目標(biāo)用戶生成假位置后，將位置服務(wù)請(qǐng)求傳送給與其直連的邊緣服務(wù)器進(jìn)行執(zhí)行.若直連的邊緣服務(wù)器無法處理目標(biāo)用戶的請(qǐng)求，則將請(qǐng)求轉(zhuǎn)發(fā)至云端進(jìn)行處理.

2）邊-邊-云執(zhí)行：目標(biāo)用戶生成假位置后，將位置服務(wù)請(qǐng)求傳送給與其直連的邊緣服務(wù)器進(jìn)行執(zhí)行，若直連的邊緣服務(wù)器難以支持服務(wù)請(qǐng)求的計(jì)算，則將該請(qǐng)求轉(zhuǎn)發(fā)給鄰近的邊緣服務(wù)器.在鄰近的邊緣服務(wù)器也無法執(zhí)行時(shí)，將請(qǐng)求轉(zhuǎn)發(fā)至云端進(jìn)行處理.

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

7.2.1 實(shí)驗(yàn)數(shù)據(jù)

本文用一個(gè)開源的實(shí)驗(yàn)數(shù)據(jù)集來證明所提出方法的有效性.澳大利亞通信和媒體管理局（ACMA）發(fā)布的無線通信許可證數(shù)據(jù)集包含了澳大利亞所有的蜂窩基站的地理位置(即邊緣服務(wù)器部署的位置).本文用墨爾本蜂窩基站的位置數(shù)據(jù)EUA-dataset(https://github.com/swinedge/eua-dataset)作為測(cè)試數(shù)據(jù)集的方法，用來模擬邊緣服務(wù)器的真實(shí)位置和用戶分布.

7.2.2 實(shí)驗(yàn)參數(shù)

依據(jù)以往工作中的實(shí)驗(yàn)設(shè)置[26]，本文設(shè)置μ=500，用戶對(duì)于不同匿名度的收益參數(shù)設(shè)置為T=500，將每個(gè)邊緣服務(wù)器的使用價(jià)格區(qū)間設(shè)置為[10,40]，每個(gè)中繼的價(jià)格區(qū)間設(shè)置為[3,10].在實(shí)際的實(shí)驗(yàn)過程中，假設(shè)用戶期望時(shí)間tD=0.8×tcloud，這里tcloud表示服務(wù)請(qǐng)求上傳至云端執(zhí)行所耗費(fèi)的時(shí)間.此外，實(shí)驗(yàn)中將云服務(wù)器的響應(yīng)時(shí)間設(shè)置為1 s，將邊緣服務(wù)器的響應(yīng)時(shí)間設(shè)置為0.3 s.為驗(yàn)證本文提出的基于中繼的分流模型能夠有效縮短用戶請(qǐng)求的執(zhí)行時(shí)延，本文假設(shè)廣播獲得中繼的時(shí)間與邊緣服務(wù)器響應(yīng)時(shí)間一致，均為0.3 s.

7.2.3 度量指標(biāo)

本文設(shè)置了3 個(gè)度量指標(biāo)：1）在接收用戶相同請(qǐng)求任務(wù)條件下，任務(wù)的平均完成時(shí)間，該值越低越好；2）在期望時(shí)間tD之前完成的任務(wù)占總的任務(wù)個(gè)數(shù)的比例，該值越高越好；3）用戶實(shí)際發(fā)送的服務(wù)請(qǐng)求個(gè)數(shù)kr，該值越高越好.

本節(jié)通過控制兩個(gè)可能影響實(shí)驗(yàn)性能的變量來觀察本文提出方法的性能變化情況.

1）匿名需求k

k反映了用戶的匿名需求，k值越高說明隱私保護(hù)能力越好.實(shí)驗(yàn)中k的取值設(shè)置為：k=5,10,15,20,25,30,35,40,45,50.

2）活躍邊緣服務(wù)器比例p

p反映了當(dāng)前區(qū)域可以正常工作的邊緣服務(wù)器占總的邊緣服務(wù)器個(gè)數(shù)的比例.這些正常工作的邊緣服務(wù)器的狀態(tài)包括{0,1}.本實(shí)驗(yàn)中p的取值設(shè)置為：p ∈{0.55,0.60,0.65,0.70,0.75,0.80,0.85,0.90,0.95,1}.

基于上述實(shí)驗(yàn)配置，本節(jié)通過3 組實(shí)驗(yàn)分別對(duì)本文提出的方法及兩個(gè)基準(zhǔn)方法進(jìn)行驗(yàn)證與對(duì)比分析，3 組實(shí)驗(yàn)的設(shè)置均采用控制變量法觀察匿名需求k和活躍邊緣服務(wù)器比例p對(duì)任務(wù)完成時(shí)間、任務(wù)完成比例、用戶實(shí)際發(fā)送請(qǐng)求數(shù)目的影響，具體設(shè)置如表2所示.

表2 實(shí)驗(yàn)設(shè)置Table 2 Experimental setting

7.3 實(shí)驗(yàn)結(jié)果

在實(shí)際實(shí)驗(yàn)中，目標(biāo)用戶需要依據(jù)自身狀態(tài)決定發(fā)送的請(qǐng)求數(shù)目.當(dāng)目標(biāo)用戶狀態(tài)us=1時(shí)，目標(biāo)用戶發(fā)出的實(shí)際請(qǐng)求數(shù)目kr=k.否則，目標(biāo)用戶會(huì)隨機(jī)生成kr個(gè)請(qǐng)求，且kr

圖7 匿名需求k及邊緣服務(wù)器狀態(tài)對(duì)任務(wù)平均完成時(shí)間的影響Figure 7 Effect of anonymity requirement k and edge server state on task’s average time cost

第一組實(shí)驗(yàn)從任務(wù)平均完成時(shí)間的角度比較了3 種算法的性能.圖7中的縱坐標(biāo)展示了任務(wù)的平均完成時(shí)間.從圖7(a)中可以看出，隨著匿名需求k的數(shù)目增加，3 種算法的任務(wù)平均完成時(shí)間均在增加.但基于中繼的服務(wù)請(qǐng)求分流方法的任務(wù)完成平均時(shí)間一直是最優(yōu)的.圖7(b)則展示了隨著可用邊緣服務(wù)器數(shù)量的增加，3 種算法對(duì)應(yīng)的任務(wù)平均完成時(shí)間均有所下降，且基于中繼的服務(wù)請(qǐng)求分流方法一直保持著更好的性能.上述結(jié)果的原因分析如下：對(duì)于邊-邊-云執(zhí)行方法，目標(biāo)用戶的服務(wù)請(qǐng)求只能利用其直連邊緣服務(wù)器，或直連服務(wù)器的鄰居服務(wù)器進(jìn)行服務(wù)請(qǐng)求的響應(yīng).在匿名需求高或可用邊緣服務(wù)器數(shù)量較少的場(chǎng)合，人員密集區(qū)域的邊緣服務(wù)器的負(fù)載較大，易造成大量用戶的服務(wù)難以在邊緣進(jìn)行，因此需要頻繁將用戶請(qǐng)求上傳至云端處理.而對(duì)于邊-云的執(zhí)行方式更是如此.但基于中繼的服務(wù)請(qǐng)求分流方法卻可以利用中繼將任務(wù)分散給多個(gè)邊緣服務(wù)器執(zhí)行，因而性能最優(yōu).

第二組實(shí)驗(yàn)從期望時(shí)間之前任務(wù)完成比例的角度比較了3 種算法的性能.圖8中的縱坐標(biāo)展示了在期望時(shí)間之前完成的任務(wù)所占總?cè)蝿?wù)的比例.從圖8(a)中可以看出，隨著匿名需求的數(shù)目增加，3 種算法在期望時(shí)間之前完成的任務(wù)比例都在下降.但基于中繼的服務(wù)請(qǐng)求分流方法的性能一直是最優(yōu)的.圖8(b)中展示了隨著可用邊緣服務(wù)器的數(shù)量的增加，3 種算法在期望時(shí)間之前完成的任務(wù)比例都在上升.可以看出基于中繼的服務(wù)請(qǐng)求分流方法總能保持較好的性能.上述結(jié)果的原因與第一組實(shí)驗(yàn)的分析過程相似：對(duì)于邊-邊-云執(zhí)行方法，在匿名需求高或可用邊緣服務(wù)器數(shù)量較少的場(chǎng)合，邊緣服務(wù)器的負(fù)載較大，需要上傳至云端處理.對(duì)于邊-云的執(zhí)行方式更是如此.但基于中繼的服務(wù)請(qǐng)求分流方法卻可以利用中繼將任務(wù)分散給多個(gè)邊緣服務(wù)器執(zhí)行，因而性能最優(yōu).

圖8 匿名需求k及邊緣服務(wù)器狀態(tài)對(duì)完成的任務(wù)百分比的影響Figure 8 Effect of anonymity requirement k and edge server state on task completion percentage

圖9 匿名需求k及邊緣服務(wù)器狀態(tài)對(duì)請(qǐng)求數(shù)目的影響Figure 9 Effect of anonymity requirement k and edge server state on the number of requests

第三組實(shí)驗(yàn)主要從實(shí)際的請(qǐng)求發(fā)送數(shù)的角度比較3 種算法的性能.從圖9(a)中可以看出，隨著匿名需求的提升，3 種算法的實(shí)際發(fā)送的請(qǐng)求數(shù)都在上升，但基于中繼的服務(wù)請(qǐng)求分流方法的實(shí)際發(fā)送請(qǐng)求數(shù)總是最多的.在圖9(b)中，隨著正常工作的邊緣服務(wù)服務(wù)器的數(shù)量增長(zhǎng)，3種算法的實(shí)際發(fā)送請(qǐng)求數(shù)也都在上升.但基于中繼的服務(wù)請(qǐng)求分流方法的性能總是最優(yōu)的.這是因?yàn)?，目?biāo)用戶會(huì)依據(jù)自身的狀態(tài)和邊緣服務(wù)狀態(tài)來確定實(shí)際發(fā)送的請(qǐng)求數(shù)量.而在邊-邊-云執(zhí)行和邊-云執(zhí)行的情形下，實(shí)際發(fā)送的請(qǐng)求數(shù)量會(huì)受到目標(biāo)用戶狀態(tài)和邊緣服務(wù)器的狀態(tài)的制約，二者只要有一個(gè)狀態(tài)值小于1，則目標(biāo)用戶只能發(fā)送出弱數(shù)量請(qǐng)求.但基于中繼的服務(wù)請(qǐng)求分流方法可以利用多個(gè)中繼實(shí)現(xiàn)極限保護(hù)，依然可以發(fā)出強(qiáng)數(shù)量請(qǐng)求.因此，基于中繼的服務(wù)請(qǐng)求分流方法總是可以獲得最優(yōu)的性能.

8 結(jié) 語

本文針對(duì)云計(jì)算環(huán)境下，基于假人的位置隱私保護(hù)方法會(huì)造成用戶獲取結(jié)果的時(shí)延過高問題，提出將位置隱私保護(hù)方法遷移到邊緣計(jì)算環(huán)境下的解決方案.針對(duì)邊緣服務(wù)器的服務(wù)能力與覆蓋范圍具有上限的特點(diǎn)，本文提出了面向位置隱私保護(hù)的中繼分流模型，實(shí)現(xiàn)了其中的分流方法，并在真實(shí)數(shù)據(jù)集中驗(yàn)證了本文所提出的方法.今后的研究工作將主要關(guān)注如何改善假位置的生成方法，在降低假位置生成算法的時(shí)間復(fù)雜度的同時(shí)提升匿名效果.