邊緣計(jì)算環(huán)境下自適應(yīng)移動(dòng)路徑感知的用戶分配算法

李 煒,蔣 越,閔江松, 張以文+，王慶人

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230039；2.國家企業(yè)互聯(lián)網(wǎng)服務(wù)支撐軟件工程技術(shù)中心，廣東 深圳 518057)

0 引言

如今移動(dòng)設(shè)備已完全融入人們的生活，智能手機(jī)、便攜電腦等成為人們學(xué)習(xí)、工作、娛樂不可或缺的部分[1]。早在2011年智能手機(jī)的銷量供貨量就已超過傳統(tǒng)電腦[2]。移動(dòng)設(shè)備市場(chǎng)的飛速擴(kuò)大，促進(jìn)了許多桌面應(yīng)用程序的移植以及適合移動(dòng)設(shè)備使用場(chǎng)景(如增強(qiáng)現(xiàn)實(shí)應(yīng)用程序)的移動(dòng)應(yīng)用程序的開發(fā)[3]。盡管現(xiàn)今一些智能手機(jī)的硬件設(shè)施相對(duì)于之前已有巨大提升，但大多移動(dòng)設(shè)備仍具有較低的計(jì)算能力、有限的存儲(chǔ)空間以及過低的能耗，無法支持許多計(jì)算密集型應(yīng)用[4]。為應(yīng)對(duì)此類問題，文獻(xiàn)[5]首先提出將計(jì)算任務(wù)卸載到遠(yuǎn)程云，移動(dòng)云計(jì)算(Mobile Cloud Computing，MCC)提供集中的資源來處理計(jì)算任務(wù)。但MCC無法滿足一些延遲敏感的應(yīng)用程序的需求，將計(jì)算任務(wù)卸載到遠(yuǎn)程云進(jìn)行數(shù)據(jù)交互可能會(huì)涉及較高的延遲[6]。為了減少用戶與服務(wù)器進(jìn)行數(shù)據(jù)交互時(shí)的延遲，文獻(xiàn)[7]提出移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)來解決以上問題。MEC將應(yīng)用程序的部分業(yè)務(wù)邏輯復(fù)制到附近的設(shè)備上進(jìn)行處理,以此來擴(kuò)展移動(dòng)設(shè)備的硬件能力[8]，并提高服務(wù)質(zhì)量(Quality of Service, QoS)[9]。

邊緣服務(wù)器相較于遠(yuǎn)程云服務(wù)器雖然極大地降低了數(shù)據(jù)傳輸?shù)耐ㄐ叛舆t[10]，但在計(jì)算能力、存儲(chǔ)空間等方面有較大差距，資源相對(duì)有限[11]，受此約束，從用戶層面來看，當(dāng)用戶數(shù)量過多時(shí)，邊緣服務(wù)器將會(huì)過載，來自新用戶的請(qǐng)求將無法被接受，并在服務(wù)器中排隊(duì)[12]，損失QoS[13]；從服務(wù)器層面來看，不合理的分配策略會(huì)造成部分服務(wù)器空閑或連接用戶數(shù)較低，產(chǎn)生負(fù)載不足，可能導(dǎo)致資源利用率過低并浪費(fèi)大量的能量支持空閑服務(wù)器的工作。因此，一個(gè)合理的用戶分配策略將對(duì)緩解邊緣服務(wù)器資源緊張發(fā)揮巨大作用。

傳統(tǒng)研究中的分配策略被視作一個(gè)靜態(tài)優(yōu)化問題，沒有考慮到部分設(shè)備(如智能手機(jī)，增強(qiáng)現(xiàn)實(shí)等)與其用戶一樣具有移動(dòng)性；而部分研究的分配策略在考慮到用戶移動(dòng)性時(shí)，僅將用戶預(yù)期移動(dòng)路徑看作一條直線，當(dāng)使用真實(shí)軌跡數(shù)據(jù)集時(shí)該策略可能無法達(dá)到預(yù)期效果。針對(duì)以上問題，本文考慮了用戶的移動(dòng)性，結(jié)合用戶位置信息及其周邊路網(wǎng)信息，對(duì)用戶未來移動(dòng)路徑進(jìn)行預(yù)期計(jì)算，根據(jù)文獻(xiàn)[14]提出的用戶遷移的基本思想，提出了一種自適應(yīng)移動(dòng)路徑感知的用戶分配算法(Adaptive Mobile Path Aware Allocation, AMPA)，將用戶的預(yù)期移動(dòng)路徑作為分配策略中的重要因素，解決了在現(xiàn)實(shí)環(huán)境下用戶具有高移動(dòng)性時(shí)因分配策略不合理而造成用戶覆蓋率較低及資源浪費(fèi)的問題。本文的貢獻(xiàn)包括：

(1)結(jié)合地圖數(shù)據(jù)進(jìn)行建模，利用用戶當(dāng)前位置信息，使用直接投影法判斷其移動(dòng)狀態(tài)(是否沿路行進(jìn))并預(yù)期其未來移動(dòng)路徑，基于預(yù)期路徑提出一種新的分配策略，將服務(wù)器信號(hào)范圍內(nèi)用戶的預(yù)期停留時(shí)間作為該用戶分配的適應(yīng)值，對(duì)其進(jìn)行實(shí)時(shí)在線分配，提高了用戶連接的穩(wěn)定性。

(2)基于最佳適應(yīng)算法提出一種分配策略重構(gòu)方法，對(duì)于滿載服務(wù)器，將其中更加適應(yīng)于鄰近服務(wù)器的Top-k個(gè)用戶遷移至臨近空閑服務(wù)器，同時(shí)接受信號(hào)范圍內(nèi)相對(duì)于該滿載服務(wù)器適應(yīng)值的Top-k個(gè)新的用戶的連接請(qǐng)求，提高了范圍內(nèi)用戶承載量及服務(wù)器資源利用率。

(3)通過在用戶真實(shí)軌跡數(shù)據(jù)集以及開源路網(wǎng)數(shù)據(jù)集的基礎(chǔ)上進(jìn)行大量對(duì)比實(shí)驗(yàn)，驗(yàn)證了本文算法的有效性。

1 相關(guān)工作

移動(dòng)應(yīng)用程序的復(fù)雜化使移動(dòng)設(shè)備的存儲(chǔ)、運(yùn)算能力面臨巨大考驗(yàn)，與此同時(shí)各種移動(dòng)設(shè)備的激增產(chǎn)生了大量數(shù)據(jù)，為數(shù)據(jù)傳輸帶來了巨大的壓力。一些研究提出將計(jì)算任務(wù)卸載到遠(yuǎn)程云，由云服務(wù)器處理計(jì)算任務(wù)，并將計(jì)算結(jié)果返回給移動(dòng)設(shè)備，然而通過這種方式處理計(jì)算任務(wù)時(shí)會(huì)帶來較高的延遲[15]，無法滿足一些應(yīng)用程序?qū)崟r(shí)數(shù)據(jù)交互的需求。文獻(xiàn)[16]提出將應(yīng)用程序的計(jì)算任務(wù)發(fā)送到附近的計(jì)算服務(wù)器進(jìn)行處理，從而使計(jì)算能力較弱的設(shè)備能夠滿足應(yīng)用程序的需求。文獻(xiàn)[17]在文獻(xiàn)[16]的基礎(chǔ)上進(jìn)一步提出邊緣計(jì)算模式，它允許移動(dòng)設(shè)備將計(jì)算任務(wù)卸載到附近位于互聯(lián)網(wǎng)邊緣的邊緣服務(wù)器上，以擴(kuò)展移動(dòng)設(shè)備的運(yùn)算能力和硬件配置，從而解決上述問題。

第五代移動(dòng)通信技術(shù)(5G)為用戶提供了極高的傳輸速率，極大提升了用戶的使用體驗(yàn)，也為邊緣計(jì)算環(huán)境下各項(xiàng)操作提供了有利條件。隨著對(duì)邊緣計(jì)算關(guān)注度的提升，任務(wù)卸載和用戶分配問題得到了眾人的研究，XU等[12]對(duì)任務(wù)卸載問題進(jìn)行優(yōu)化，從消耗時(shí)間、消耗能源、負(fù)載均衡3方面將卸載問題建模成一個(gè)多目標(biāo)優(yōu)化問題，并使用非支配排序遺傳算法3(Non-dominated Sorting Genetic Algorithms3,NSGA3)對(duì)該問題進(jìn)行求解。WANG等[18]研究了邊緣服務(wù)器的放置問題，以最小化邊緣云的工作負(fù)載平衡和連接用戶的通信延遲為目標(biāo)，利用k-means算法將相互之間傳輸延遲較低的服務(wù)器聚成一簇，在邊緣服務(wù)器位置確定的情況下使用混合整數(shù)二次規(guī)劃算法對(duì)該放置問題進(jìn)行優(yōu)化。PHU等[19]第一次提出解決邊緣用戶分配問題，將邊緣用戶分配問題視作為一個(gè)可變尺寸裝箱問題，并使用詞典目標(biāo)規(guī)劃技術(shù)[20]進(jìn)行求解，以達(dá)到最大化分配用戶數(shù)量和最小化雇傭邊緣服務(wù)器數(shù)量的優(yōu)化目標(biāo)，但他們是在位置固定不變的用戶數(shù)據(jù)基礎(chǔ)之上得出實(shí)驗(yàn)結(jié)果，未能考慮到用戶的移動(dòng)性。LIN等[21]提出進(jìn)行資源分配操作時(shí)，需要不斷適應(yīng)用戶移動(dòng)的位置，對(duì)用戶未來移動(dòng)位置進(jìn)行預(yù)測(cè)可以保證盡可能做出最佳的分配決定。URGAONKAR等[22]提出隨著用戶位置的變化，用戶在當(dāng)前邊緣云中的服務(wù)應(yīng)當(dāng)進(jìn)行遷移操作，但他們認(rèn)為在動(dòng)態(tài)服務(wù)遷移和工作負(fù)載調(diào)度時(shí)，無法進(jìn)一步了解用戶的移動(dòng)性。而文獻(xiàn)[14]考慮了用戶的移動(dòng)性，提出移動(dòng)感知和遷移的在線邊緣用戶分配算法，將邊緣用戶分配問題視為一個(gè)在線決策以及可變化問題，通過服務(wù)遷移提高了用戶的覆蓋率，然而他們將用戶的移動(dòng)性視作直線行進(jìn)軌跡處理，實(shí)驗(yàn)結(jié)果是基于運(yùn)動(dòng)軌跡為直線的用戶得出的，未能有效利用及處理真實(shí)環(huán)境中用戶的移動(dòng)性。

以上研究中，在解決邊緣用戶分配問題時(shí)未能考慮或充分利用用戶的移動(dòng)性，采用較為局限的用戶分配方法，在真實(shí)軌跡數(shù)據(jù)下進(jìn)行實(shí)驗(yàn)可能產(chǎn)生不理想的結(jié)果。本文提出的自適應(yīng)移動(dòng)路徑感知的用戶分配算法，針對(duì)真實(shí)移動(dòng)軌跡數(shù)據(jù)中的移動(dòng)對(duì)象進(jìn)行分析，實(shí)時(shí)預(yù)測(cè)用戶未來移動(dòng)路徑，并通過提出的分配策略重構(gòu)方法，保證用戶覆蓋率的同時(shí)提高了服務(wù)器的資源利用率。

2 研究場(chǎng)景及模型

2.1 移動(dòng)邊緣計(jì)算

移動(dòng)邊緣計(jì)算是近年來備受關(guān)注的重要技術(shù)。隨著移動(dòng)應(yīng)用對(duì)設(shè)備硬件需求的日益增加，同時(shí)出現(xiàn)了部分計(jì)算密集型應(yīng)用以及延遲敏感應(yīng)用，如遠(yuǎn)程游戲控制，虛擬現(xiàn)實(shí)等，移動(dòng)設(shè)備有限的存儲(chǔ)空間與運(yùn)算能力無法滿足應(yīng)用的需求，人們開始在互聯(lián)網(wǎng)邊緣的邊緣服務(wù)器中部署服務(wù)，以實(shí)現(xiàn)在極短時(shí)間內(nèi)響應(yīng)用戶的請(qǐng)求并處理用戶卸載的計(jì)算任務(wù)，在保證低延遲的前提下與用戶進(jìn)行數(shù)據(jù)交互。

在實(shí)驗(yàn)場(chǎng)景中，如圖1所示，邊緣服務(wù)器配備有限的資源，若該服務(wù)器用戶連接數(shù)超出限制，則無法接收新的連接請(qǐng)求。邊緣服務(wù)器覆蓋整個(gè)區(qū)域，區(qū)域內(nèi)的用戶可以連接到信號(hào)范圍內(nèi)未過載的服務(wù)器并請(qǐng)求相關(guān)服務(wù)[23]。若用戶超出服務(wù)器范圍，則會(huì)丟失連接并重新分配至另一范圍內(nèi)未過載服務(wù)器。

2.2 系統(tǒng)模型

本文涉及的符號(hào)表示如表1所示。

2.2.1 用戶信息

表1 符號(hào)表

(1)

(2)

2.2.2 服務(wù)器信息

(3)

2.2.3 路網(wǎng)信息

2.2.4 優(yōu)化目標(biāo)

(4)

(5)

(6)

0≤i≤n,0≤j≤m。

如式(4)所示，優(yōu)化目標(biāo)為最大化用戶覆蓋率和范圍內(nèi)服務(wù)器的平均資源利用率；式(5)表示分配成功的用戶必須位于該服務(wù)器覆蓋范圍之內(nèi)；式(6)表示服務(wù)器最大連接數(shù)不得超過該服務(wù)器總?cè)萘俊?/p>

3 自適應(yīng)移動(dòng)路徑感知的用戶分配算法

第2章的場(chǎng)景中，硬件能力不足的設(shè)備主要以移動(dòng)便攜設(shè)備為主，而此類設(shè)備通常具有很高的移動(dòng)性。在此情況下，使用傳統(tǒng)的裝箱算法并不是最佳的選擇，因?yàn)檫@類算法將用戶分配視作靜態(tài)優(yōu)化問題；使用算法[14]同樣不是最佳的選擇，盡管該算法考慮了用戶的移動(dòng)性，但該算法中將用戶未來移動(dòng)路徑看做一條直線，不適用于現(xiàn)實(shí)世界中復(fù)雜的用戶移動(dòng)軌跡。針對(duì)上述情況，本文設(shè)計(jì)了一種自適應(yīng)移動(dòng)路徑感知的分配算法，以提高用戶覆蓋率與總體用戶連接時(shí)間，如算法1所示。該算法主要主要步驟如下：

(1)道路匹配。根據(jù)用戶位置信息計(jì)算該用戶相對(duì)于各個(gè)路段的距離度量值，獲取距離度量值最小的路段信息(如算法1第3～第9行所示)。

(2)用戶分配。根據(jù)基于用戶移動(dòng)性構(gòu)建的適應(yīng)度函數(shù)，將未連接的用戶分配至信號(hào)范圍內(nèi)未過載的服務(wù)器(如算法1第10行所示)，提高用戶連接穩(wěn)定性的同時(shí)提高分配策略的合理性，減少因用戶超出信號(hào)范圍的連接丟失。

(3)重構(gòu)分配策略。遍歷區(qū)域內(nèi)所有滿載服務(wù)器，執(zhí)行基于最佳適應(yīng)算法的分配策略重構(gòu)算法(如算法1第13～第15行所示)，以提高范圍內(nèi)服務(wù)器的用戶承載能力及服務(wù)器資源利用率。

算法1自適應(yīng)移動(dòng)路徑感知的用戶分配算法。

輸入：用戶(Users)，各服務(wù)器數(shù)據(jù)(Servers)，路網(wǎng)數(shù)據(jù)(Roads);

輸出：用戶分配策略。

1.初始化距離度量暫存值tmp并得到未分配用戶列表unallocate_users

2.FOR user IN unallocate_users

3.FORroad_tmp IN Roads

7. user.road=road_tmp

8. END IF

9. END FOR

10.執(zhí)行移動(dòng)路徑感知的用戶分配算法(Users,

Servers,Roads)

11.END FOR

12.得到滿載服務(wù)器列表overload_servers

13.FORserver IN overload_servers

14.執(zhí)行分配策略重構(gòu)算法(Users,server,Servers,Roads)

15.END FOR

16.DONE

3.1 道路匹配

在考慮具有移動(dòng)性的對(duì)象時(shí)，分配問題并不能看作靜態(tài)優(yōu)化問題。

如圖2所示，當(dāng)圖中用戶沿著黑色虛線行進(jìn)時(shí)，若將用戶分配至服務(wù)器1，則在短時(shí)間內(nèi)用戶將面臨因超出信號(hào)范圍而造成的連接中斷，損失QoS，于此同時(shí)范圍內(nèi)丟失一位用戶，在接收新的連接請(qǐng)求前，用戶覆蓋率與資源利用率相對(duì)降低；若將用戶分配至服務(wù)器2，則可為用戶提供更久的穩(wěn)定連接，從而減少連接中斷。

解決上述場(chǎng)景中問題，優(yōu)化分配策略的關(guān)鍵在于了解用戶未來行進(jìn)軌跡。

考慮到復(fù)雜的路況，用戶將很難沿著當(dāng)前行進(jìn)方向的延長(zhǎng)線一直行進(jìn)，但也正因?yàn)榈缆返南拗?，人們?cè)谝欢〞r(shí)間內(nèi)只能沿著當(dāng)前道路行進(jìn)，因此本文考慮將當(dāng)前道路作為短期內(nèi)預(yù)期的用戶未來行動(dòng)軌跡。

假設(shè)用戶所處情形如圖3所示，進(jìn)行預(yù)期行進(jìn)路徑計(jì)算前需要為用戶進(jìn)行道路匹配。本文采用直接投影法計(jì)算用戶相對(duì)每條道路的距離度量值[24]，該值越低則表明用戶與該路段匹配度越高。時(shí)刻t時(shí)用戶i與第q條路的距離度量值計(jì)算如下：

(7)

3.2 用戶分配

用戶分配環(huán)節(jié)中，將首先基于用戶移動(dòng)性計(jì)算用戶分配適應(yīng)值。文獻(xiàn)[14]提出將用戶停留在某個(gè)邊緣服務(wù)器范圍內(nèi)的預(yù)期持續(xù)時(shí)間作為該用戶相對(duì)服務(wù)器的適應(yīng)值，以達(dá)到減少影響用戶感知QoS的服務(wù)中斷的目標(biāo)，本文在此基礎(chǔ)上提出結(jié)合用戶未來的預(yù)期路徑計(jì)算出范圍內(nèi)各服務(wù)器的適應(yīng)值，基于適應(yīng)值決策分配策略，提高用戶連接的穩(wěn)定性，減少因連接中斷帶來的分配策略變更。適應(yīng)值的計(jì)算如下：

(8)

(1)用戶沿著附近道路行進(jìn)，如圖4a所示。

(2)用戶所處位置以及行進(jìn)方向均大幅偏離周邊道路，則當(dāng)前用戶可能未沿道路行進(jìn)，如圖4b所示。

若計(jì)算出的當(dāng)前用戶相對(duì)周邊道路的距離度量值小于預(yù)設(shè)閾值，則歸為情況(1)處理，將服務(wù)器信號(hào)范圍內(nèi)的道路長(zhǎng)度作為預(yù)期移動(dòng)距離；若路段盡頭仍在服務(wù)器范圍內(nèi)，則將路段末端作延長(zhǎng)線繼續(xù)計(jì)算預(yù)期移動(dòng)距離，如下式所示：

(9)

若計(jì)算出的距離度量值大于預(yù)設(shè)閾值，則將用戶視為情況(2)處理，如下式計(jì)算預(yù)期移動(dòng)距離：

(10)

式中：point表示當(dāng)前用戶行進(jìn)方向的延長(zhǎng)線與服務(wù)器信號(hào)范圍邊界的交點(diǎn)坐標(biāo)，用戶行進(jìn)方向可通過GPS獲得。

使用上述計(jì)算方法作為分配策略的適應(yīng)值，將增加用戶連接的穩(wěn)定性，減少了范圍內(nèi)因丟失用戶連接帶來的分配策略變動(dòng)，從而提升用戶覆蓋率并降低范圍內(nèi)服務(wù)器的空閑時(shí)間，保證算法的有效性。

用戶分配如算法2所示，具體算法流程如下：

(1)計(jì)算預(yù)期移動(dòng)距離(如算法2第4～第9行所示)。

(2)分別計(jì)算當(dāng)前用戶相對(duì)于尚有剩余用量服務(wù)器的適應(yīng)值(如算法2第10～第15行所示)與可遷移用戶的滿載服務(wù)器的適應(yīng)值(如算法2第17～第23行所示)。其中第17行將在3.3節(jié)給出詳細(xì)解釋。

(3)將用戶分配給適應(yīng)值最高的服務(wù)器(如算法2第26～第30行所示)。

算法2移動(dòng)路徑感知的用戶分配算法。

輸入：未連接用戶(user)，各服務(wù)器數(shù)據(jù)(Servers)，路網(wǎng)數(shù)據(jù)(Roads);

輸出：用戶分配服務(wù)器信息。

1.初始化距離度量值暫存變量length_tmp，各個(gè)用戶匹配的路段user.road，道路匹配閾值m，令適應(yīng)值adapt=-1，可調(diào)整分配策略服務(wù)器的適應(yīng)值adapt_adjust=-1。

2.得到信號(hào)覆蓋當(dāng)前用戶的服務(wù)器列表server_list

3.FOR server_tmp IN server_list

5.得到用戶行進(jìn)方向上下一個(gè)路段點(diǎn)

6. 根據(jù)式(9)計(jì)算預(yù)期行進(jìn)長(zhǎng)度

7. ELSE

8. 根據(jù)式(10)計(jì)算預(yù)期行進(jìn)長(zhǎng)度

9. END IF

10. IF server_tmp未滿載

11.根據(jù)式(8)計(jì)算適應(yīng)值adapt_tmp

12.IF adapt_tmp>adapt

13. adapt=adapt_tmp

14. server=server_tmp

15. END IF

16. ELSE

17. IF該服務(wù)器可遷移用戶

18. 根據(jù)式(8)計(jì)算適應(yīng)值adapt_adjust_tmp

19. IF adapt_adjust_tmp>adapt_adjust

20. adapt_adjust=adapt_adjust_tmp

21. server_adjust=server_tmp

22. END IF

23. END IF

24. END IF

25.END FOR

26.IF adapt_adjust!=-1 AND adapt

27. 對(duì)服務(wù)器server_adjust執(zhí)行分配策略重構(gòu)算法(Users,server,Servers,Roads)

28.IF adapt>adapt_adjust OR (執(zhí)行分配策略重構(gòu)算法并未分配成功 AND adapt!=-1)

29.將當(dāng)前用戶分配給服務(wù)器server

30.END IF

31.DONE

3.3 重構(gòu)分配策略

進(jìn)行用戶分配時(shí)，當(dāng)服務(wù)器滿載時(shí)，如圖5a所示，服務(wù)器1滿載，服務(wù)器2仍有剩余容量，若將服務(wù)器1、2公共區(qū)域的用戶4遷移至有剩余容量的服務(wù)器2，則此時(shí)服務(wù)器1騰出一個(gè)剩余空間，區(qū)域內(nèi)可再覆蓋一名用戶，此時(shí)稱服務(wù)器1為可遷移用戶的服務(wù)器。

而在圖5b中，若服務(wù)器2滿載，服務(wù)器3、4仍有剩余容量，但服務(wù)器2可通過將服務(wù)器2與服務(wù)器3之間的用戶6遷移至服務(wù)器3，此時(shí)服務(wù)器2可再容納一名用戶，則服務(wù)器1、2、4公共區(qū)域的用戶4可以遷移至服務(wù)器2、4兩者中適應(yīng)值最高的服務(wù)器，以此提高用戶連接的穩(wěn)定性。

通過以上場(chǎng)景不難發(fā)現(xiàn)，當(dāng)服務(wù)器滿載時(shí)，若該服務(wù)器周邊存在覆蓋該服務(wù)器中部分用戶的未滿載服務(wù)器，則可通過遷移一部分用戶至未滿載服務(wù)器，間接提高區(qū)域內(nèi)用戶承載容量，從而有效提高用戶覆蓋率。但在容納更多用戶的同時(shí)，保證用戶更穩(wěn)定的連接卻是一個(gè)較為困難的挑戰(zhàn)。針對(duì)該問題；本文提出一種基于最佳適應(yīng)算法的分配策略重構(gòu)方法，該方法總是將適合遷移的用戶填充至附近空閑或有剩余空間的服務(wù)器，從而盡可能增加區(qū)域內(nèi)用戶容量，如算法3所示。

算法3分配策略重構(gòu)算法。

輸入：用戶(Users)，當(dāng)前服務(wù)器數(shù)據(jù)(server),區(qū)域內(nèi)所有服務(wù)器數(shù)據(jù)(Servers)，路網(wǎng)數(shù)據(jù)(Roads);

輸出：用戶分配策略。

1.得到服務(wù)器server信號(hào)范圍內(nèi)未分配用戶列表unallocate_user

2.得到當(dāng)前服務(wù)器server已連接的用戶online_users

3.FOR user IN online_users

4. 得到除當(dāng)前服務(wù)器外信號(hào)覆蓋user的服務(wù)器列表server_cover

5. FOR server_tmp IN server_cover

6. IF server_tmp未滿載

7. 將當(dāng)前用戶user加入至可遷移列表allocateable_user

8. END IF

9. END FOR

10.END FOR

11.FOR user IN unallocate_user

12.根據(jù)式(8)計(jì)算該用戶相對(duì)于server適應(yīng)值user.adapt

13.END FOR

14.FOR user IN allocateable_user

15. 得到信號(hào)覆蓋當(dāng)前用戶的服務(wù)器列表server_list

16. FOR server_tmp IN server_list

17. IF該服務(wù)器未滿載或滿載但可遷移用戶

18. 根據(jù)式(8)計(jì)算該用戶相對(duì)于server_tmp適應(yīng)值user.adapt_tmp

19. IF user.adapt_tmp>user.adapt

20. user.adapt=user.adapt_tmp

21. END IF

22. END IF

23.END FOR

24.END FOR

25.將unallocate_user按適應(yīng)值降序排序

26.將allocateable_user按適應(yīng)值降序排序

27.FOR user IN min(len(unallocate_user),len(allocateable_user))

28.將unallocate_user分配給當(dāng)前服務(wù)器server

29.對(duì)allocateable_user執(zhí)行移動(dòng)路徑感知的用戶分配算法(Users,Servers,Roads)

30.END FOR

31.DONE

服務(wù)器的分配策略重構(gòu)方法主要步驟如下：

(1)尋找范圍內(nèi)未連接的用戶列表(如算法3第1行所示)以及當(dāng)前服務(wù)器下可被遷移至其他服務(wù)器的用戶(如算法3第2～第10行所示)列表。

(2)計(jì)算未連接用戶列表unallocate_user中各用戶相對(duì)于當(dāng)前服務(wù)器的適應(yīng)度(如算法3第11～第13行所示)。

(3)計(jì)算可遷移用戶列表allocateable_user中各用戶相對(duì)于可遷入服務(wù)器服務(wù)器的的適應(yīng)度(如算法3第14～第24行所示)。

(4)對(duì)兩個(gè)列表中的用戶按適應(yīng)值進(jìn)行降序排序(如算法3第25～第26行所示)。

(5)分別為兩個(gè)列表中的用戶分配服務(wù)器(如算法3第27～第30行及圖6所示)。

其中步驟(2)、步驟(3)，列表unallocate_user與allocateable_user分別相對(duì)不同服務(wù)器的適應(yīng)值排序，保證了將更適合鄰近服務(wù)器的用戶遷移至該服務(wù)器，將更加適合當(dāng)前服務(wù)器的用戶優(yōu)先分配給當(dāng)前服務(wù)器。

算法3第29行對(duì)可遷移用戶執(zhí)行遷移操作時(shí)，涉及到算法2與算法3之間的相互調(diào)用關(guān)系，注意到算法3第5～第9行對(duì)可遷移用戶列表的約束條件，即當(dāng)信號(hào)范圍覆蓋該用戶的服務(wù)器中存在未滿載服務(wù)器時(shí)，該用戶才被定義為可遷移用戶，該約束保證了可遷移用戶在擁有至少一個(gè)候選空閑服務(wù)器的情形下再考慮下一層可調(diào)整分配策略的滿載服務(wù)器，從而做到在不丟失用戶的情況下擴(kuò)大區(qū)域內(nèi)服務(wù)器的容量，并減少周圍服務(wù)器的空閑時(shí)間，保證了算法的收斂性。

綜上所述，當(dāng)存在不合理的用戶分配策略時(shí)，本文采用分配策略重構(gòu)方法來優(yōu)化分配策略以覆蓋更多的用戶并減少區(qū)域內(nèi)服務(wù)器的空閑時(shí)間，提高區(qū)域內(nèi)服務(wù)器資源利用率。

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

本文使用Python實(shí)現(xiàn)了算法，基于北京區(qū)域用戶軌跡數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。

4.1 數(shù)據(jù)集描述

實(shí)驗(yàn)數(shù)據(jù)集包含3個(gè)部分：第一部分是用戶軌跡數(shù)據(jù)集，該數(shù)據(jù)來源于微軟亞洲研究院的Geolife項(xiàng)目中的GPS軌跡數(shù)據(jù)集[25-27]；第二部分是來源于OpenStreetMap的開源路網(wǎng)數(shù)據(jù)集；第三部分是模擬生成的邊緣服務(wù)器數(shù)據(jù)集。

其中，第一部分是在該數(shù)據(jù)集中選取北京大學(xué)及其周邊3 km×3 km的區(qū)域內(nèi)共512條用戶軌跡，90%以上的軌跡以5 s內(nèi)或10 m內(nèi)的間隔記錄，包含開車、坐公交車、騎自行車和步行這幾種出行方式，數(shù)據(jù)集內(nèi)包括時(shí)間、經(jīng)緯度等信息；第二部分為在該路網(wǎng)數(shù)據(jù)集中選取區(qū)域內(nèi)共2 209條路段，數(shù)據(jù)中包括各個(gè)路段中各記錄點(diǎn)的經(jīng)緯度信息；第三部分是在區(qū)域內(nèi)生成的126個(gè)服務(wù)器，信號(hào)覆蓋全區(qū)域范圍。

4.2 有效性評(píng)估

本文實(shí)驗(yàn)使用以下3個(gè)指標(biāo)來評(píng)估算法的效果：

(1)在服務(wù)器各項(xiàng)參數(shù)一致及使用相同的軌跡數(shù)據(jù)的環(huán)境下，區(qū)域內(nèi)用戶覆蓋率越高則算法表現(xiàn)越佳。

(2)在服務(wù)器各項(xiàng)參數(shù)一致及使用相同的軌跡數(shù)據(jù)的環(huán)境下，區(qū)域內(nèi)所有服務(wù)器的平均資源利用率越高則算法表現(xiàn)越佳。

(3)在配備同樣資源的服務(wù)器環(huán)境下，相同時(shí)間段內(nèi)若區(qū)域內(nèi)所有成功分配的用戶連接至服務(wù)器的累計(jì)時(shí)間越長(zhǎng)，則服務(wù)器發(fā)揮效用越大，算法表現(xiàn)越佳。

4.3 比較方法

本文實(shí)驗(yàn)將自適應(yīng)移動(dòng)路徑感知的用戶分配算法與以下6種不同分配算法進(jìn)行對(duì)比：

(1)移動(dòng)感知和遷移的分配算法(MobMig)[14]?；诜?wù)器信號(hào)范圍內(nèi)的用戶當(dāng)前行進(jìn)方向的延長(zhǎng)線的長(zhǎng)度，將用戶在服務(wù)器范圍內(nèi)的停留時(shí)間作為分配算法的適應(yīng)值，使用用戶遷移方法來覆蓋更多的用戶。

(2)隨機(jī)(Random)。將未分配的用戶隨機(jī)分配給信號(hào)覆蓋該用戶且未滿載的服務(wù)器。

(3)貪心(Greedy)。將未分配的用戶分配給信號(hào)范圍內(nèi)距離最近的未滿載的服務(wù)器。

(4)首次適應(yīng)(Firstfit)。將未分配的用戶分配給信號(hào)范圍內(nèi)，未滿載的服務(wù)器列表中的第一個(gè)服務(wù)器。

(5)最佳適應(yīng)(Bestfit)。將未分配的用戶分配給信號(hào)范圍內(nèi)的未滿載的服務(wù)器列表中剩余容量最小的服務(wù)器。

(6)Noniterate-AMPA。此版本算法不再考慮圖5b中的情形，即只將有剩余容量的服務(wù)器加入到調(diào)整分配策略中，不再考慮下一層可調(diào)整分配策略的滿載服務(wù)器。

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

本文在實(shí)驗(yàn)中將512條用戶軌跡視作同一時(shí)間段內(nèi)512個(gè)用戶的移動(dòng)軌跡數(shù)據(jù)信息。實(shí)驗(yàn)記錄15 min內(nèi)該區(qū)域內(nèi)用戶的分配情況來檢驗(yàn)算法的有效性，本文將邊緣服務(wù)器的容量設(shè)置為50%，100%，150%的用戶連接負(fù)載，實(shí)驗(yàn)結(jié)果如圖7～圖8、表2～表4所示。

圖7和表2顯示了15 min內(nèi)區(qū)域內(nèi)用戶的覆蓋率，其中圖7橫坐標(biāo)為時(shí)間，縱坐標(biāo)為每30秒間隔內(nèi)的平均用戶覆蓋率。綜合圖表可知，本文的AMPA算法的覆蓋率在3類容量的情況下都優(yōu)于其他5種算法，同樣也優(yōu)于算法Noniterate-AMPA，這表明了考慮圖5b情形的優(yōu)越性。

表2 用戶覆蓋率比較 %

圖8以及表3顯示了15 min內(nèi)區(qū)域內(nèi)服務(wù)器的平均資源利用率。其中圖8顯示了每分鐘服務(wù)器的平均資源利用率。顯然，在3類服務(wù)器容量下，本文的AMPA算法表現(xiàn)出了更高的資源利用率。隨著服務(wù)器容量的增加，用戶數(shù)與服務(wù)器資源之比相對(duì)降低，故相同算法的資源利用率呈下降趨勢(shì)。

表4顯示出3類容量下使用相同的服務(wù)器配置，AMPA實(shí)現(xiàn)了更高的累計(jì)用戶連接時(shí)間，即更好地發(fā)揮了區(qū)域內(nèi)服務(wù)器的效用。

以上實(shí)驗(yàn)結(jié)果中，4個(gè)傳統(tǒng)算法中在資源利用率這一指標(biāo)上，Bestfit表現(xiàn)最佳，因?yàn)樵撍惴偸菍⑿逻B接分配至剩余容量最小的服務(wù)器，減少了空

表3 資源利用率比較 %

表4 總連接時(shí)間比較 s

閑服務(wù)器的比例從而提升了資源利用率；在用戶覆蓋率和總連接時(shí)間指標(biāo)上，Greedy算法表現(xiàn)出較好的效果，其原因在于Greedy總是先分配距離服務(wù)器最近的用戶，這種情況下保證了分配成功的用戶能夠相對(duì)更長(zhǎng)時(shí)間地處于覆蓋其的服務(wù)器信號(hào)范圍內(nèi)，間接的考慮了用戶的移動(dòng)性，從而獲得較好的表現(xiàn)。MobMig雖然考慮了用戶的移動(dòng)性，但因?yàn)閺?fù)雜的路況以及相對(duì)局限的用戶遷移策略使其分配策略并未達(dá)到最佳效果。

綜上所述，本文AMPA算法的表現(xiàn)明顯優(yōu)于其他基準(zhǔn)算法，有效地提高了邊緣計(jì)算環(huán)境下的服務(wù)器對(duì)用戶的覆蓋率以及資源利用率。

5 結(jié)束語

在邊緣計(jì)算環(huán)境中，為了使配備有限資源的邊緣服務(wù)器服務(wù)更多的用戶，并且進(jìn)一步提升邊緣服務(wù)器的資源利用率，提出了自適應(yīng)移動(dòng)路徑感知的用戶分配算法。本文提出的算法與其他邊緣用戶分配算法不同，在考慮用戶的移動(dòng)性時(shí)利用用戶當(dāng)前移動(dòng)信息，分析用戶行進(jìn)狀態(tài)，結(jié)合路網(wǎng)數(shù)據(jù)對(duì)未來路徑進(jìn)行預(yù)期計(jì)算，從而減少因用戶超出服務(wù)器信號(hào)范圍的連接中斷；與此同時(shí)提出了一種新的分配策略重構(gòu)算法，實(shí)時(shí)調(diào)整分配策略，從而進(jìn)一步提高了服務(wù)器的資源利用率以及對(duì)用戶的覆蓋率，解決了邊緣服務(wù)器資源短缺的問題。

未來計(jì)劃在用戶分配時(shí)考慮更多的情形，在算法時(shí)間復(fù)雜度和用戶覆蓋率之間作進(jìn)一步的優(yōu)化，同時(shí)在預(yù)期路徑計(jì)算中引入更多的因素，提升用戶未來軌跡的預(yù)測(cè)精度。