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

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

2 研究場景及模型

2.1 移動邊緣計算

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

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

2.2 系統(tǒng)模型

本文涉及的符號表示如表1所示。

2.2.1 用戶信息

表1 符號表

(1)

(2)

2.2.2 服務(wù)器信息

(3)

2.2.3 路網(wǎng)信息

2.2.4 優(yōu)化目標

(4)

(5)

(6)

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

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

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

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

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

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

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

算法1自適應(yī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í)行移動路徑感知的用戶分配算法(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 道路匹配

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

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

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

考慮到復(fù)雜的路況，用戶將很難沿著當前行進方向的延長線一直行進，但也正因為道路的限制，人們在一定時間內(nèi)只能沿著當前道路行進，因此本文考慮將當前道路作為短期內(nèi)預(yù)期的用戶未來行動軌跡。

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

(7)

3.2 用戶分配

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

(8)

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

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

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

(9)

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

(10)

式中：point表示當前用戶行進方向的延長線與服務(wù)器信號范圍邊界的交點坐標，用戶行進方向可通過GPS獲得。

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

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

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

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

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

算法2移動路徑感知的用戶分配算法。

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

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

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

2.得到信號覆蓋當前用戶的服務(wù)器列表server_list

3.FOR server_tmp IN server_list

5.得到用戶行進方向上下一個路段點

6. 根據(jù)式(9)計算預(yù)期行進長度

7. ELSE

8. 根據(jù)式(10)計算預(yù)期行進長度

9. END IF

10. IF server_tmp未滿載

11.根據(jù)式(8)計算適應(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)計算適應(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. 對服務(wù)器server_adjust執(zhí)行分配策略重構(gòu)算法(Users,server,Servers,Roads)

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

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

30.END IF

31.DONE

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

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

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

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

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

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

輸出：用戶分配策略。

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

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

3.FOR user IN online_users

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

5. FOR server_tmp IN server_cover

6. IF server_tmp未滿載

7. 將當前用戶user加入至可遷移列表allocateable_user

8. END IF

9. END FOR

10.END FOR

11.FOR user IN unallocate_user

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

13.END FOR

14.FOR user IN allocateable_user

15. 得到信號覆蓋當前用戶的服務(wù)器列表server_list

16. FOR server_tmp IN server_list

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

18. 根據(jù)式(8)計算該用戶相對于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分配給當前服務(wù)器server

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

30.END FOR

31.DONE

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

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

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

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

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

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

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

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

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

4 實驗評估

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

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

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

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

4.2 有效性評估

本文實驗使用以下3個指標來評估算法的效果：

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

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

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

4.3 比較方法

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

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

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

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

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

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

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

4.4 實驗結(jié)果分析

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

圖7和表2顯示了15 min內(nèi)區(qū)域內(nèi)用戶的覆蓋率，其中圖7橫坐標為時間，縱坐標為每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ù)器資源之比相對降低，故相同算法的資源利用率呈下降趨勢。

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

以上實驗結(jié)果中，4個傳統(tǒng)算法中在資源利用率這一指標上，Bestfit表現(xiàn)最佳，因為該算法總是將新連接分配至剩余容量最小的服務(wù)器，減少了空

表3 資源利用率比較 %

表4 總連接時間比較 s

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

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

5 結(jié)束語

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

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