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

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

0 引言

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

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

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

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

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

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

1 相關工作

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

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

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

2 研究場景及模型

2.1 移動邊緣計算

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

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

2.2 系統(tǒng)模型

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

2.2.1 用戶信息

表1 符號表

(1)

(2)

2.2.2 服務器信息

(3)

2.2.3 路網信息

2.2.4 優(yōu)化目標

(4)

(5)

(6)

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

如式(4)所示，優(yōu)化目標為最大化用戶覆蓋率和范圍內服務器的平均資源利用率；式(5)表示分配成功的用戶必須位于該服務器覆蓋范圍之內；式(6)表示服務器最大連接數不得超過該服務器總容量。

3 自適應移動路徑感知的用戶分配算法

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

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

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

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

算法1自適應移動路徑感知的用戶分配算法。

輸入：用戶(Users)，各服務器數據(Servers)，路網數據(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.得到滿載服務器列表overload_servers

13.FORserver IN overload_servers

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

15.END FOR

16.DONE

3.1 道路匹配

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

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

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

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

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

(7)

3.2 用戶分配

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

(8)

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

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

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

(9)

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

(10)

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

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

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

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

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

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

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

輸入：未連接用戶(user)，各服務器數據(Servers)，路網數據(Roads);

輸出：用戶分配服務器信息。

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

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

3.FOR server_tmp IN server_list

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

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

7. ELSE

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

9. END IF

10. IF server_tmp未滿載

11.根據式(8)計算適應值adapt_tmp

12.IF adapt_tmp>adapt

13. adapt=adapt_tmp

14. server=server_tmp

15. END IF

16. ELSE

17. IF該服務器可遷移用戶

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

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

29.將當前用戶分配給服務器server

30.END IF

31.DONE

3.3 重構分配策略

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

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

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

算法3分配策略重構算法。

輸入：用戶(Users)，當前服務器數據(server),區(qū)域內所有服務器數據(Servers)，路網數據(Roads);

輸出：用戶分配策略。

1.得到服務器server信號范圍內未分配用戶列表unallocate_user

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

3.FOR user IN online_users

4. 得到除當前服務器外信號覆蓋user的服務器列表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.根據式(8)計算該用戶相對于server適應值user.adapt

13.END FOR

14.FOR user IN allocateable_user

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

16. FOR server_tmp IN server_list

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

18. 根據式(8)計算該用戶相對于server_tmp適應值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按適應值降序排序

26.將allocateable_user按適應值降序排序

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

28.將unallocate_user分配給當前服務器server

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

30.END FOR

31.DONE

服務器的分配策略重構方法主要步驟如下：

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

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

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

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

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

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

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

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

4 實驗評估

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

4.1 數據集描述

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

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

4.2 有效性評估

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

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

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

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

4.3 比較方法

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

(1)移動感知和遷移的分配算法(MobMig)[14]?；诜掌餍盘柗秶鷥鹊挠脩舢斍靶羞M方向的延長線的長度，將用戶在服務器范圍內的停留時間作為分配算法的適應值，使用用戶遷移方法來覆蓋更多的用戶。

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

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

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

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

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

4.4 實驗結果分析

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

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

表2 用戶覆蓋率比較 %

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

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

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

表3 資源利用率比較 %

表4 總連接時間比較 s

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

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

5 結束語

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

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