国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

邊緣計(jì)算下面向位置隱私保護(hù)的中繼分流模型

2020-10-21 03:14林文敏劉加邦
關(guān)鍵詞:中繼分流邊緣

林文敏,張 松,劉加邦

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ù)的請求;然后,位置服務(wù)提供商返回給用戶相應(yīng)的結(jié)果.例如用戶在使用美團(tuán)點(diǎn)評時(shí),首先選擇自身的地理位置,然后選擇需要查詢的內(nèi)容,接著將上述信息發(fā)送給美團(tuán)點(diǎn)評服務(wù)提供商后,其服務(wù)器經(jīng)過一系列計(jì)算返回給用戶相應(yīng)的查詢結(jié)果.

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

關(guān)于隱私問題的研究通常包括隱私挖掘和隱私保護(hù)兩個(gè)方面.1)隱私挖掘是指對用戶的請求進(jìn)行數(shù)據(jù)分析,根據(jù)用戶社會屬性的不同可以將隱私挖掘分成兩類:一類是面向具有危害性社會屬性的用戶(如犯罪分子),如在案件偵破過程中需要對用戶隱私進(jìn)行挖掘分析,從而快速地偵破案件.Iqbal等[3]提出了利用數(shù)據(jù)挖掘分析犯罪分子的數(shù)據(jù)請求,從而協(xié)助警方更快地偵破案件.另一類是面向社會中正常生活的用戶,此類隱私挖掘的應(yīng)用通常指通過收集用戶的請求來挖掘用戶隱私信息,進(jìn)而利用用戶的隱私信息進(jìn)行金融詐騙或者勒索敲詐[4].2)隱私保護(hù)是從為用戶提供更好服務(wù)的角度,通過挖掘用戶的位置隱私屬性獲取用戶的個(gè)性化需求,從而提高服務(wù)質(zhì)量.Chatzidimitris 等[5]提出了對用戶歷史請求記錄進(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í)位置只有一定概率被識別,從而保護(hù)用戶的位置隱私信息.本文基于該方法在之前的工作中也做了一些完善工作[16-17].

然而,現(xiàn)有基于假人的方法大多忽略了常規(guī)的云服務(wù)器離用戶距離較遠(yuǎn)的情況,同時(shí)云服務(wù)器也需要傳輸大量數(shù)據(jù)包給用戶,導(dǎo)致用戶得到結(jié)果的時(shí)延可能是傳輸一條真實(shí)數(shù)據(jù)的k倍,這樣會影響用戶的位置服務(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ù)方法存在的不足之處,如在某些情況下會造成用戶的時(shí)延大幅上升.

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

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

1 背景介紹

用戶發(fā)送的位置服務(wù)請求中通常包含多種內(nèi)容:用戶的位置信息、服務(wù)請求內(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ù)途徑。鑒于此,針對上述位置隱私保護(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í),保證用戶請求的低時(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ā)送匿名請求.如圖3所示,當(dāng)邊緣服務(wù)器的用戶過多時(shí)造成服務(wù)器滿載(紅色),其余該區(qū)域的用戶便無法向此邊緣服務(wù)器發(fā)送請求.

圖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ù)的中繼分流模型并對模型中的分流方法進(jìn)行求解.

2 相關(guān)工作

2.1 位置隱私保護(hù)

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

然而,上述方法忽略了對手可能具有側(cè)信息的問題.若這些方法產(chǎn)生的假人位于湖泊或崎嶇的山區(qū),那么攻擊者會直接識別出這些假位置,從而降低假人方法為用戶提供的匿名保護(hù)效果.Niu等[20]則在考慮到對手可能擁有側(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ù)器的請求數(shù)據(jù)量,從而保護(hù)用戶的位置隱私.

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

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

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

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

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

3 建模預(yù)備知識

為了解決第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)用戶的請求.為了獲取邊緣服務(wù)器的服務(wù),目標(biāo)用戶通過中繼將服務(wù)請求發(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ì)算分流問題,即用戶在該過程中的位置不會出現(xiàn)較大的變化.在未來的工作中會進(jìn)一步討論關(guān)于動態(tài)環(huán)境中基于中繼的分流方法在位置隱私保護(hù)中的應(yīng)用問題.

本文中,k表示基于假人方法(下文簡稱假人方法)的匿名度,它表示假人方法為用戶生成了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è)請求,其中kre ?1 個(gè)請求包含的是假位置.基于kre與k的數(shù)量關(guān)系,本文給出如下定義:

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

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

由于不同用戶對匿名度的要求不同,對強(qiáng)、弱數(shù)量請求的劃分標(biāo)準(zhǔn)也不同.本文目標(biāo)用戶需要發(fā)送min(kre,k)個(gè)請求到中繼.考慮到目標(biāo)用戶所持設(shè)備的性能和網(wǎng)絡(luò)狀況,以及被選作中繼的不同用戶,其所持有的終端設(shè)備的請求處理能力也是不同的,因此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),即不能處理任何請求;0 表示終端設(shè)備或者邊緣服務(wù)器僅能處理少量請求,處于該狀態(tài)時(shí)終端設(shè)備或邊緣服務(wù)器僅能發(fā)出或接受弱數(shù)量請求;1則表示終端設(shè)備或服務(wù)器狀態(tài)良好,可以處理高匿名度的請求且能夠發(fā)出或接受強(qiáng)數(shù)量請求.本文目標(biāo)用戶所處區(qū)域的邊緣服務(wù)器一定滿足es ?1.基于上述對目標(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ù)量請求,中繼接收到目標(biāo)用戶的強(qiáng)數(shù)量請求后將其發(fā)送至邊緣服務(wù)器.邊緣服務(wù)器處理完請求后將結(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ù)量請求,中繼接收到目標(biāo)用戶的弱數(shù)量請求后將其發(fā)送至邊緣服務(wù)器.邊緣服務(wù)器處理完請求后將結(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ù)量請求,但中繼可在目標(biāo)設(shè)備發(fā)出請求的基礎(chǔ)上加入新的假位置,進(jìn)而構(gòu)成強(qiáng)數(shù)量請求.之后,中繼會將強(qiáng)數(shù)量請求發(fā)送給邊緣服務(wù)器,邊緣服務(wù)器處理完請求后將結(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)用戶會選中多個(gè)中繼,然后將強(qiáng)數(shù)量請求分成多個(gè)弱數(shù)量請求分別發(fā)送給中繼.中繼接收到目標(biāo)用戶的請求后,會將請求發(fā)送給自己所在區(qū)域的邊緣服務(wù)器.邊緣服務(wù)器處理完請求后,會將結(jié)果按原路徑返回.

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

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

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

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

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

表1 主要符號及其含義Table 1 Key terms and notation

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

1)請求上行

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

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

2)請求下行

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

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

3)請求處理

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

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

4)假位置生成

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

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

5)激勵模塊

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

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

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

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

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

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

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

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

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

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

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

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

5.1 假位置生成方法

信息熵作為信息度量的有效工具,在通信領(lǐng)域已展現(xiàn)出重要的貢獻(xiàn).隱私作為一種信息,可以考慮用熵來量化.本文用熵表示從所有位置中識別出真實(shí)位置的概率,選擇與Niu等[20]相同的熵的定義,將地圖劃分為N ×N個(gè)單元格.每個(gè)單元格都有1 個(gè)歷史查詢概率(稱為查詢概率),用變量qi表示,且對于查詢中包含的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ù)方法為用戶生成的假位置集合的熵最小.首先對每個(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ù)等級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)用戶會先向周圍廣播獲取中繼的請求,接收到請求的設(shè)備會將邊緣服務(wù)狀態(tài)返回給目標(biāo)用戶.目標(biāo)用戶周圍可能分布著多個(gè)可能作為中繼的用戶,所以目標(biāo)用戶會得到一個(gè)邊緣服務(wù)狀態(tài)集合S={s1,s2,···,sn}.

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

得到周圍設(shè)備的邊緣服務(wù)狀態(tài)集合后,目標(biāo)用戶會查詢該集合并從中挑選出待選的中繼集合.具體的算法流程如算法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ù)請求,因此也就不需要中繼用戶.之后,算法會在從目標(biāo)用戶周圍的設(shè)備的邊緣服務(wù)狀態(tài)中篩選掉邊緣服務(wù)狀態(tài)為–1 的設(shè)備.本文稱構(gòu)成邊緣狀態(tài)集合的用戶為待選中繼,SC也稱為待選中繼邊緣服務(wù)狀態(tài)集合.

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

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

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

本文中各種保護(hù)狀態(tài)并沒有優(yōu)先級,目標(biāo)用戶可以依據(jù)式(2)選擇合適的保護(hù)狀態(tài).不同保護(hù)狀態(tài)會造成不同請求數(shù)量和不同中繼數(shù)量.因此,在得到待選中繼的邊緣狀態(tài)集合后,需要依據(jù)目標(biāo)用戶自身狀態(tài)及待選中繼的邊緣狀態(tài)選擇合適的保護(hù)模式.根據(jù)保護(hù)狀態(tài)的定義,可知共可能會出現(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)用戶僅會發(fā)送弱數(shù)量請求,且中繼僅發(fā)送弱數(shù)量請求就可以滿足目標(biāo)用戶的要求.因此僅需一個(gè)中繼就可以完成分流任務(wù),與強(qiáng)保護(hù)類似,中繼不會額外生成假位置,則有

情形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ù)量請求后,中繼需要為目標(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,對于每個(gè)s,滿足s=0.

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

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

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

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

輸出:實(shí)際發(fā)送請求數(shù)量kr,中繼集合SR

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

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

3ifus=1then

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

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

6ifus=0then

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

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

9 找到使得式(11)最大的情形,得到對應(yīng)的k,SR;

10returnk,SR

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

6 性能分析

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

基于假人的位置選擇步驟中,首先需要對地圖中的N ×N個(gè)單元格按照其被查詢概率進(jìn)行排序.本文擬采用快速排序的方法對上述N2個(gè)單元格進(jìn)行排序,因此該操作需要的平均計(jì)算復(fù)雜度為O(N2lbN2).針對某一個(gè)特定查詢請求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ù)請求分流步驟則是用戶在上述基于假人的位置選擇和中繼選擇的基礎(chǔ)上,根據(jù)其自身狀態(tài)及待選中繼的邊緣狀態(tài)選擇合適的保護(hù)模式,并選擇使式(2)效用值最大的中繼SR和請求數(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ù)請求分流.x的取值范圍為[2,n],因此在極限保護(hù)狀態(tài)下,計(jì)算復(fù)雜度為

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

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

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

7.1 對比方法

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

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

2)邊-邊-云執(zhí)行:目標(biāo)用戶生成假位置后,將位置服務(wù)請求傳送給與其直連的邊緣服務(wù)器進(jìn)行執(zhí)行,若直連的邊緣服務(wù)器難以支持服務(wù)請求的計(jì)算,則將該請求轉(zhuǎn)發(fā)給鄰近的邊緣服務(wù)器.在鄰近的邊緣服務(wù)器也無法執(zhí)行時(shí),將請求轉(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)作為測試數(shù)據(jù)集的方法,用來模擬邊緣服務(wù)器的真實(shí)位置和用戶分布.

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

依據(jù)以往工作中的實(shí)驗(yàn)設(shè)置[26],本文設(shè)置μ=500,用戶對于不同匿名度的收益參數(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ù)請求上傳至云端執(zhí)行所耗費(fèi)的時(shí)間.此外,實(shí)驗(yàn)中將云服務(wù)器的響應(yīng)時(shí)間設(shè)置為1 s,將邊緣服務(wù)器的響應(yīng)時(shí)間設(shè)置為0.3 s.為驗(yàn)證本文提出的基于中繼的分流模型能夠有效縮短用戶請求的執(zhí)行時(shí)延,本文假設(shè)廣播獲得中繼的時(shí)間與邊緣服務(wù)器響應(yīng)時(shí)間一致,均為0.3 s.

7.2.3 度量指標(biāo)

本文設(shè)置了3 個(gè)度量指標(biāo):1)在接收用戶相同請求任務(wù)條件下,任務(wù)的平均完成時(shí)間,該值越低越好;2)在期望時(shí)間tD之前完成的任務(wù)占總的任務(wù)個(gè)數(shù)的比例,該值越高越好;3)用戶實(shí)際發(fā)送的服務(wù)請求個(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)分別對本文提出的方法及兩個(gè)基準(zhǔn)方法進(jìn)行驗(yàn)證與對比分析,3 組實(shí)驗(yàn)的設(shè)置均采用控制變量法觀察匿名需求k和活躍邊緣服務(wù)器比例p對任務(wù)完成時(shí)間、任務(wù)完成比例、用戶實(shí)際發(fā)送請求數(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ā)送的請求數(shù)目.當(dāng)目標(biāo)用戶狀態(tài)us=1時(shí),目標(biāo)用戶發(fā)出的實(shí)際請求數(shù)目kr=k.否則,目標(biāo)用戶會隨機(jī)生成kr個(gè)請求,且kr

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

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

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

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

8 結(jié) 語

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

猜你喜歡
中繼分流邊緣
基于4G和5G上下行分流策略研究
涉罪未成年人分流與觀護(hù)制度比較及完善
NSA架構(gòu)分流模式
自適應(yīng)多中繼選擇系統(tǒng)性能分析
瑞利信道下全雙工中繼系統(tǒng)性能研究
一張圖看懂邊緣計(jì)算
一種鋁型材上模整體鑲嵌式分流模結(jié)構(gòu)
一種基于無線蜂窩網(wǎng)絡(luò)的共享中繼模型
中繼測控鏈路動態(tài)分析與計(jì)算方法研究
在邊緣尋找自我
六安市| 周至县| 临潭县| 拉孜县| 龙岩市| 吉木乃县| 龙陵县| 灵寿县| 寿光市| 乌苏市| 北辰区| 浦城县| 十堰市| 武定县| 台东市| 满洲里市| 长岛县| 明溪县| 盖州市| 定州市| 棋牌| 望谟县| 灵川县| 休宁县| 曲阳县| 河北省| 百色市| 东海县| 贡山| 呈贡县| 吕梁市| 眉山市| 灵寿县| 庆元县| 格尔木市| 岱山县| 缙云县| 赞皇县| 灵台县| 中方县| 繁峙县|