(19)國家知識產(chǎn)權局(12)發(fā)明專利地址224000江蘇省鹽城市鹽南高新區(qū)大數(shù)據(jù)產(chǎn)業(yè)園創(chuàng)新大廈南樓15層公司32224專利代理師母秋松審查員張華晶一種基于時序圖和圖匹配理論的任務卸載本發(fā)明公開了一種基于時序圖和圖匹配理維度表示了用戶移動過程中動態(tài)變化的基站集基于圖匹配理論中的A*算法對任務卸載策略進發(fā)將任務卸載問題建模為圖同態(tài)問題并基于A*算法為移動場景下的依賴任務的卸載問題提出購購tstatsT2totstotio21.一種基于時序圖和圖匹配理論的任務卸載方法，其特征在于：包括如下步驟：步驟S1:獲取應用圖GA中的子任務的集合VA,并按照每個子任務的時延容忍值對所有的子任務進行升序排序以確定每個子任務的排名，子任務v的排名記為Rank(v);其中，待卸載的計算密集型應用用應用圖GA=(VA,EA)表示，VA是應用中子任務的集合，εA表示子任務之間的依賴關系；待卸載的計算密集型應用由多個存在依賴關系的子任務組成；步驟S2:確定子任務v;在應用圖GA拓撲中的位置；如果子任務v;是應用的入口子任務v?則跳轉到步驟S3,如果子任務v;是應用的出口子任務v則跳轉到步驟S4,否則子任務v;為應用的中間子任務則跳轉到步驟S5;步驟S3:將子任務v?的卸載節(jié)點確定為用戶終端即x?,n=BS?,將子任務v。從OpenList中OpenList用來存放待確定卸載方式的已經(jīng)準備好的子任務集合，其初始值為應用的起始子任務v?;CloseList用來存放已經(jīng)確定好的匹配對，其初始值為空集；BS?為用戶終端；其中，表示對子任務進行本地處理的用戶終端；當n≠0時，BS,表示對子任務進行邊緣計算的基步驟S4:將子任務v?的卸載節(jié)點確定為用戶終端即x,n=BS?,將子任務v從OpenList中步驟S5:為中間子任務v;確定相應的卸載節(jié)點，并形成匹配對(v;,BS。),將匹配對放入步驟S5-1:確定時間戳ts下的卸載節(jié)點集合CandidateSet以及準備好的子任務集合步驟S5-2:對OpenList中的每個子任務進行標記，確定進行延遲卸載的子任務，進行串行處理的子任務以及進行普通卸載的子任務；步驟S5-3:根據(jù)OpenList中每個子任務的標記更新其候選的卸載節(jié)點集合；在時間戳ts下，如果子任務v的標記為status(v;)=1即延遲卸載，則其候選的卸載節(jié)點集合擴大為當前時間戳以及下個時間戳下卸載節(jié)點集合的并集即CandidateSet={BS(ts)UBS(ts+1)UBS?};如果子任務v;的標記為status(v;)=2即串行處理，則其候選節(jié)點集合擴大為當前時間戳下候選節(jié)點的集合以及其前序子任務的卸載節(jié)點即CandidateSet={BS(ts)UBS?Uxi,m},其中子任務v是子任務v的直接前序子任務；如果子任務v;的標記為status(v;)=0即普通卸載，則候選節(jié)點集合不進行更新而使用初始值即CandidateSet={BS(ts)UBS?};BS(ts)為時間戳ts下基站節(jié)點，BS(ts+1)為時間戳ts+1下基站節(jié)點；x;,為時間戳ts-1下的子任務v;所確定的卸載節(jié)點；步驟S5-4:按照OpenList中每個子任務的排名順序Rank(v;),依次為每個子任務計算CandidateSet集合中每個卸載節(jié)點的啟發(fā)函數(shù)值，將啟發(fā)函數(shù)值f(n)最小的卸載節(jié)點作為步驟S6:對CloseList從最后一個匹配對(v,BS。)開始逐步追蹤其前面的匹配對，直到起始的匹配對(v?,BS。),返回找到的結果路徑，算法結束。2.根據(jù)權利要求1所述的一種基于時序圖和圖匹配理論的任務卸載方法，其特征在于：3當子任務v的時延容忍值大于下個時間戳即LST(v;)>ts+1時，將子任務v;判定為延遲子任務v;的直接前序子任務為v,當子任務v有多個直接后序子任務v;即succ(v;)>2當子任務v;不滿足延遲卸載和串行處理時，則將子任務v判定為普通卸載并將其標記VertexTrans(v;)=μ;/f。所述EdgeTrans(v;,v)計算公式如下：其中：pred(v;)表示子任務v;的直接前序子任務集合，∈,是子任務v;和子任務v;之間h(n)=(sm,n-am,)-(am,n-48.一種計算機可讀存儲介質(zhì)，其特征在于：其上存儲有計算機程序，該計算機程序被處理器執(zhí)行時，實現(xiàn)如權利要求1-7中任一所述的一種基于時序圖和圖匹配理論的任務卸載方法。9.一種計算機設備，包括：存儲器，用于存儲指令；處理器，用于執(zhí)行所述指令，使得所述計算機設備執(zhí)行如權利要求1-7中任一所述的一種基于時序圖和圖匹配理論的任務卸載方法的操作。5一種基于時序圖和圖匹配理論的任務卸載方法、設備及介質(zhì)技術領域[0001]本發(fā)明涉及一種基于時序圖和圖匹配理論的任務卸載方法、設備及介質(zhì)，屬于無線通信技術領域。背景技術[0002]隨著5G網(wǎng)絡部署的順利進行，國內(nèi)外對6G展開了深入的研究。從典型場景看，全球基本上形成了五大場景共識，即沉浸式通信/超級無線寬帶、超大規(guī)模連接、極端/關鍵性通信/極其可靠通信、通信感知融合、人工智能和通信的融合。從業(yè)務用浸化應用將成為6G核心業(yè)務之一。[0003]6G時代的很多應用比如XR(ExtendedReality)、AI等都是計算密集型的，這些應用對終端提出的要求也是越來越高的，但是終端在算力、電量等方面的能力是有限的，所以需要在網(wǎng)絡側給用戶提供額外的算力，比如通過邊緣計算的方式。[0004]在邊緣計算的方式下，網(wǎng)絡既需要提供實時的計算服務，還需要保障計算任務的QoS(比如時延)。對此，現(xiàn)有國內(nèi)廠家提出未來的6G網(wǎng)絡功能架構將是以用戶為中心的。在以用戶為中心的網(wǎng)絡架構中，網(wǎng)絡會根據(jù)用戶的行為(比如服務需求以及用戶的移動性等)動態(tài)地為網(wǎng)絡提供算力服務。[0005]以沉浸式XR應用為例，網(wǎng)絡側如何根據(jù)用戶的移動性特征以及應用所需的計算資源為用戶動態(tài)地提供算力服務，即在本地處理以及邊緣卸載這兩種計算卸載方式下如何在用戶的移動過程中為單個應用中的每個子任務選擇合適的卸載節(jié)點以減少應用的實際計算時延是一個需要研究的問題。發(fā)明內(nèi)容[0006]目的：為了克服現(xiàn)有技術中存在的不足，本發(fā)明提供一種基于時序圖和圖匹配理[0009]步驟S1:獲取應用圖9A中的子任務的集合VA,并按照每個子任務的時延容忍值對所有的子任務進行升序排序以確定每個子任務的排名，子任務v的排名記為Rank(v;)。[0010]步驟S2:確定子任務v;在應用圖9A拓撲中的位置。如果子任務v;是應用的入口子任務v?則跳轉到步驟S3,如果子任務v;是應用的出口子任務v?則跳轉到步驟S4,否則子任務v;為應用的中間子任務則跳轉到步驟S5。[0011]步驟S3:將子任務v?的卸載節(jié)點確定為用戶終端即xo,n=BS。,將子任務v?從OpenList中刪除，將匹配對(v?,BS。)放入CloseList中，將子任務v?的直接后序子任務加入OpenList中。OpenList用來存放待確定卸載方式的已經(jīng)準備好的子任務集合，其初始值為應用的起始子任務v?CloseList用來存放已經(jīng)確定好的匹配對，其初始值為空集。BS為用戶終端。6[0012]步驟S4:將子任務v?的卸載節(jié)點確定為用戶終端即x,n=BS。,將子任務v?從[0013]步驟S5:為中間子任務v;確定相應的卸載節(jié)點，并形成匹配對(v;,BS),將匹配對[0014]步驟S5-1:確定時間戳ts下的卸載節(jié)點集合CandidateSet以及準備好的子任務集[0015]步驟S5-2:對OpenList中的每個子任務進行標記，確定進行延遲卸載的子任務，進行串行處理的子任務以及進行普通卸載的子任務。[0016]步驟S5-3:根據(jù)OpenList中每個子任務的標記更新其候選的卸載節(jié)點集合。在時間戳ts下，如果子任務v;的標記為status(v)=1即延遲卸載，則其候選的卸載節(jié)點集合擴如果子任務v;的標記為status(v;)=2即串行處理，則其候選節(jié)點集合擴大為當前時間戳下候選節(jié)點的集合以及其前序子任務的卸載節(jié)點即CandidateSet={BS(ts)UBS?Uxi,m},其中子任務v是子任務v的直接前序子任務；如果子任務v;的標記為status(v;)=0即普通卸載，則候選節(jié)點集合不進行更新而使用初始值即CandidateSet={BS(ts)UBS?}。BS(ts)為時間戳ts下基站節(jié)點，BS(ts+1)為時間戳ts+1下基站節(jié)點。x;,為時間戳ts-1下的子任務v.所確定的卸載節(jié)點。[0017]步驟S5-4:按照OpenList中每個子任務的排名順序Rank(v),依次為每個子任務計算CandidateSet集合中每個卸載節(jié)點的啟發(fā)函數(shù)值，將啟發(fā)函數(shù)值f(n)最小的卸載節(jié)點作為子任務的卸載節(jié)點，并形成匹配對，將[0018]步驟S6:對CloseList從最后一個匹配對(v?,BS。)開始逐步追蹤其前面的匹配對，直到起始的匹配對(v?,BS?),返回找到的結果路徑，算法結束。確定的每個匹配對都是結果路徑中的每個點，則應用效用最大化(即應用完成時延的最小化)被轉化成路徑最短問題。[0019]作為優(yōu)選方案，當子任務v;的時延容忍值大于下個時間戳即LST(v;)>ts+1時，將子任務v判定為延遲卸載并將其標記為status(v;)=1。[0020]作為優(yōu)選方案，子任務v的直接前序子任務為v,當子任務v有多個直接后序子任務v;即succ(v;)>2時，將子任務v;判定為串行處理并將其標記為status(v;)=2。succ[0021]作為優(yōu)選方案，當子任務v;不滿足延遲卸載和串行處理時，則將子任務v;判定為普通卸載并將其標記為status(v;)=0。[0022]作為優(yōu)選方案，所述啟發(fā)函數(shù)值f(n),計算公式如下：[0024]其中：g(n)是當前匹配對(v,,BS)距離起始匹配對(v?,BS)的代價，h(n)是當前匹配對(v;,BS)距離最后一個匹配對(v?,BS。)的預計代價，即g(n)表示為完成應用已經(jīng)用的時長，h(n)表示為完成應用還需的時長。[0025]作為優(yōu)選方案，所述g(n)計算公式如下：[0027]其中：VertexTrans(v;)表示轉換節(jié)點操作的代價，即將子任務v;映射成卸載節(jié)點7BS的代價。EdgeTrans(v,,v;)[0033]其中：pred(v)表示子任務v的直接前序子任務集合，∈,是子任務v和子任務BS和卸載節(jié)點BS。之間連邊的結束時刻，am,表示卸載節(jié)結束時刻，則(sm,n-am,)表示用戶等待接入的時長，(am,n-sm,)表示用戶接入后的可用時[0037]第二方面，一種計算機可讀存儲介質(zhì)，其上存儲有計算機程序，該計算機程序被處理器執(zhí)行時，實現(xiàn)如第一方面中任一所述的一種基于時序圖和圖匹配理論的任務卸載方配理論出發(fā)將任務卸載問題建模為圖同態(tài)問題并基于A*算法為移動場景下的依賴任務的附圖說明8具體實施方式[0046]下面結合具體實施例對本發(fā)明作更進一步的說明。[0047]第一種實施例一種基于時序圖和圖匹配理論的任務卸載方法，包括如下步驟：[0049]定義OpenList,用來存放待確定卸載方式的已經(jīng)準備好的子任務集合，其初始值為應用的起始子任務v。卸載方式共兩種，即子任務在用戶終端處進行本地卸載以及子任務卸載到基站所連接的邊緣服務器上進行邊緣卸載。為了表述簡潔，將基站所連接的邊緣服務器指代為基站節(jié)點，并且將用戶節(jié)點和基站節(jié)點統(tǒng)稱為卸載節(jié)點。[0050]定義StatusList,用來存放還沒有準備好的子任務集合，其初始值為應用中所有需要確定卸載策略的子任務集合。還沒有準備好的含義是該子任務的前序子任務沒有全部被處理完。假設子任務v和子任務v;之間存在依賴關系，則子任務的計算結果v將作為子任務v;的輸入數(shù)據(jù)，因此當子任務v;的前序子任務v,還沒有完成的情況下是無法開始處理子[0051]定義CloseList,用來存放已經(jīng)確定好的匹配對，其初始值為空集。確定好的匹配對即為(v?,xj,),第一個元素v,表示子任務，第二個元素x,n表示為子任務v?所確定的卸載節(jié)點，xj,n的取值為卸載節(jié)點的序號。特殊地，卸載節(jié)點的序號為0表示用戶的終端設備。當所有子任務的匹配對都確定的時候，該應用中所有子任務的卸載策略也就隨之確定了，即實現(xiàn)了對問題的求解。[0052]定義CandidateSet,用來存放每個子任務候選的卸載節(jié)點集合，其初始值為0時刻下覆蓋用戶的基站節(jié)點集合以及用戶的終端，即CandidateSet={BS(0)UBS?}。因為用戶是在移動狀態(tài)下進行的任務卸載，那么隨著用戶位置的變動，覆蓋用戶的基站節(jié)點是動態(tài)變化的，所以在不同的時刻下卸載子任務，子任務可選擇的基站節(jié)點也是不同的。[0053]定義succ(·),用來表示子任務的直接后序子任務的集合。子任務v可能有多個直接后序子任務(比如子任務v?的直接后序是子任務v;?和子任務v;2),而子任務之間是存在依賴關系的即兩個相關的子任務之間有一定的數(shù)據(jù)量要轉移。如果子任務v;1和子任務v;2選擇相同的卸載節(jié)點，則子任務v原本需要轉移數(shù)據(jù)量兩次變成轉移數(shù)據(jù)量一次，這在一定程度上減少了應用的完成時延。[0055]在本地處理以及邊緣卸載這兩種卸載方式并存的情況下，如何為應用中的每個子任務設計合理的任務卸載策略以使應用的實際完成時延最小化。考慮到邊緣服務器的計算能力遠強于用戶終端，那么相同的子任務選擇邊緣卸載方式而不是本地處理方式將獲得更少的應用時延。因此，為了盡量減少應用的完成時延，定義了子任務效用u;來衡量任務卸載策略在時延方面可以給子任務帶來多少提升，子任務效用的定義公式如下：[0057]其中：t;表示子任務v,在本地處理方式下的預計完成時間，t;表示子任務v選擇合理的卸載節(jié)點后的實際完成時間。因為應用是由多個子任務構成的，所以將應用效用u定9[0059]其中：I表示應用所包含的子任務數(shù)量。[0060]任務卸載問題的總體優(yōu)化目標為應用效用最大，即選擇合適的任務卸載策略以盡量減少應用的完成時延，優(yōu)化目標的公式如下：[0062]其中：x表示應用中所有子任務的卸載策略，子任務[0063]在求解該問題的過程中，主要面臨以下兩個方面的挑戰(zhàn)。[0064]挑戰(zhàn)之一在于用戶的移動性。由于用戶處于移動狀態(tài)，其地理位置是變動的，那么在不同的時刻下覆蓋用戶的基站是不同的，即用戶可卸載的邊緣服務器是動態(tài)變化的，而不同的邊緣服務器所能提供的計算資源也是不同的。當用戶在移動過程中進行任務卸載，移動性所帶來的不利影響在于用戶可能因為切換基站而導致服務基站不能在用戶離開覆蓋范圍之前將正在處理的子任務的計算結果及時返回給用戶而造成任務卸載的中斷甚至失敗?？紤]到這個不利因素，在設計任務卸載策略時將基站節(jié)點的可接入時長作為考慮因素之一。[0065]挑戰(zhàn)之二在于子任務之間的依賴性。一個應用是由多個子任務構成的，并且子任務之間存在依賴性即子任務需要有前序子任務的計算結果來作為自身在卸載節(jié)點處執(zhí)行過程的輸入，因此子任務需要等待其前序子任務全部處理完成后才能開始卸載。這說明了子任務的完成時延既包括了自身在卸載節(jié)點處運算的執(zhí)行時延，還包括了將前序子任務的計算結果傳輸?shù)较鄳遁d節(jié)點的轉移時延?？紤]到這個不利因素，為了減少子任務的完成時延，除了選擇計算資源多的卸載節(jié)點以減少執(zhí)行時延，還應根據(jù)子任務之間的依賴關系考慮是否將存在依賴關系的兩個子任務卸載到相同的卸載節(jié)點以減少轉移時延。[0066]為了求解該問題，我們將任務卸載問題轉化成圖同態(tài)問題，從而求解最大的應用效用即求解應用最小的完成時延被轉化成了求解最短的路徑。由于子任務之間存在依賴性，前序子任務的完成時刻才是其直接后序子任務的開始時刻，因此存在依賴關系的子任務之間會在不同的時刻下選擇合適的卸載節(jié)點并進行卸載，而不同時刻下的候選節(jié)點的集合由于用戶的移動性該候選節(jié)點的集合是動態(tài)變化的。對此，子任務在不同的時刻下從不同的候選的卸載節(jié)點的集合中選擇合適的卸載節(jié)點所形成的匹配對將作為最短路徑上的節(jié)點，因此算法最終輸出的最短路徑即為應用中每個子任務及其實際卸載節(jié)點。[0069]輸出結果：子任務和卸載節(jié)點的匹配關系CloseList。[0070]上述參數(shù)的含義解釋如下。VA是應用中子任務的集合，EA三VA×VA×LA表示子任務之間的依賴關系，邊的標簽L是兩個子任務之間要轉移的數(shù)據(jù)量；Vs是卸載節(jié)點集合(卸載節(jié)點包括邊緣卸載的基站節(jié)點以及本地處理的用戶節(jié)點),EsSVs×Vs×Ls是邊的集合，每條邊表示基站-用戶-基站的2跳鏈路，標簽Ls表示基站對于用戶的可用時段，可用時段參數(shù)由平滑轉彎移動模型(smooth-turnmobilitymodel)給出。[0071]步驟4:設計OASA(OptimizedA_starAlgorithm)[0072]步驟S1:獲取應用圖GA中的子任務的集合VA,并按照每個子任務的時延容忍值對務v?則跳轉到步驟S3,如果子任務v;是應用的出口子任務v?則跳轉到步驟S4,否則子任務v;[0074]步驟S3:將子任務v?的卸載節(jié)點確定為用戶終端即xo,n=BS。,將子任務v?從[0076]步驟S4:將子任務v?的卸載節(jié)點確定為用戶終端即x,n=BS。,將子任務v?從[0079]步驟S5-1:確定時間戳ts下的卸載節(jié)點集合CandidateSet以及準備好的子任務集遲卸載并將其標記為status(v;)=1;子任務v;的直接前序子任務為v,當子任務v有多個直接后序子任務v;即succ(v;)>2時，將子任務v;判定為串行處理并將=2;當子任務v;不滿足上述兩種情況時，則將子任務v;判定為普通卸載并將其標記為[0082]進行延遲卸載的子任務將有機會接入卸載條件更好的基站節(jié)點(卸載條件包括基站所提供的計算資源以及用戶接入基站后的可用時長),這一點充分利用了用戶移動性所刻覆蓋用戶的基站具有不良好的卸載條件(比如用戶可接入的時長較短，當用戶選擇接入后將很快發(fā)生切換),則用戶可以選擇接入下個時刻下的基站以期接入卸載條件更佳的基[0083]進行串行處理的子任務將有可能選擇和其前序子任務的其他后序子任務相同的[0084]進行普通卸載的子任務是沒有采取上述延遲卸載以及串行處理兩種方式的子任務，這種類型的子任務將從當下時刻覆蓋用戶的基站集合中選擇卸載條件最好的卸載節(jié)候選節(jié)點的集合以及其前序子任務的卸載節(jié)點即其[0086]步驟S5-4:按照OpenList中每個子任務的排名順序Rank(v),依次為每個子任務[0087]啟發(fā)函數(shù)值f(n)是由兩項構成的即f(n)=g(n)+h(n),其中g(n)是當前匹配對即子任務的匹配代價cost(v;,)作為g(n),用卸載節(jié)點BS,提供給用戶的可用時長以及等待∈εA映射成卸載節(jié)點之間的連邊(BS,BS?)∈ε的代價，其代價值為子任務v將計算結果傳[0095]其中：pred(v)表示子任務v的直接前序子任務集合，∈,是子任務v和子任務BS和卸載節(jié)點BS,之間連邊的結束時刻，am,表示卸載節(jié)點BS和卸載節(jié)點BS,之間連邊的結束時刻，則(sm,n-am,)表示用戶等待接入的時長，(am,n-sm,)表示用戶接入后的可用時[0101]處理器，用于執(zhí)行所述指令，使得所述計算機設備執(zhí)行如第一種實施例中任一所述的一種基于時序圖和圖匹配理論的任務卸載方法的操作。[0103]A*算法將問題的解表示成狀態(tài)以描述問題在某個時刻的進展情況，考慮到求解卸載策略本質(zhì)上是求解子任務和卸載節(jié)點之間一對多的映射關系即圖同態(tài)問題，可以借助A*算法中狀態(tài)這個概念來表示特定時刻下的任務卸載策略。此外，由于子任務之間存在依賴關系，比如對于串行處理的子任務來說，其卸載節(jié)點可能與其前序子任務的卸載節(jié)點相關聯(lián)，因此子任務之間的卸載方式存在一定的關聯(lián)，而A*算法將問題的全部解表示成狀態(tài)的序列，這個特點可以用來表征子任務之間卸載方式的關聯(lián)性?？紤]到A*算法在上述兩個關鍵方面的貼合，基于A*算法對移動場景下依賴任務的卸載問題進行求解。[0104]A*算法在本質(zhì)上也是一種尋找最短路徑的算法，用OpenList表示周圍可到達的節(jié)點集合，用CloseList表示已經(jīng)確定的在最短路徑上的節(jié)點，每次從OpenList中選擇一個點作為新的起點，將這個新的起點周圍可到達的節(jié)點集合重新定為OpenList并從OpenList中選擇一個點作為新的起點直至到達終點。從OpenList中選擇新的起點是通過計算啟發(fā)函數(shù)值f(n)來實現(xiàn)的，將啟發(fā)函數(shù)值最小的節(jié)點作為新的起點。由于求解的是任務的卸載策略，因此A*算法中最短路徑上的節(jié)點等價于所求解的匹配對。[0105]任務卸載的場景如圖1所示，系統(tǒng)中有7個基站和1個處于移動狀態(tài)的用戶，每個基站都配備了相應的MEC服務器。用戶需要將一個截止時間為D即需要在(0,D)時段內(nèi)完成的計算密集型應用卸載給基站或其自身的終端設備，對此僅考慮(0,D)時段內(nèi)的用戶位置以及覆蓋用戶的基站。在用戶移動的過程中，用戶的地理位置不斷變更，覆蓋用戶的基站也在基站作為可卸載的基站集合，而不必考慮每個時刻下覆蓋用戶的基站集合，將這些離散的時刻記作時間戳即T={Ti,T?,…Tu}。在T?時間戳下，覆蓋用戶的基站為BS?和BS?,用戶接入并將某些子任務卸載給了BS?,由于下次的卸載過程發(fā)生在T?時間戳下，因此當用戶選擇BS?作為卸載節(jié)點時，用戶可用的時段即dwelltime為(0,t?),不可用的時段即movingtime為(t?,T?)。因此從該場景可以分析得出，隨著用戶地理位置的變更，覆蓋用戶的基站是動態(tài)變化的，即用戶的切換頻率較靜態(tài)用戶而言相對較高，當用戶離開某個基站的覆蓋范圍則該基站對于用戶來說是不可用的，因此用戶接入某個基站后的可用時長是具有一定限制的，這也意味著任務卸載過程需要發(fā)生在可用時段內(nèi)從而保證卸載過程的正常進行。[0106]為了對動態(tài)變化的卸載節(jié)點進行表征，采用了時序圖進行了建模。將用戶移動過程中可卸載節(jié)點的集合表示成有向時序圖Gs=(Vs,Es,D),其中Vs是卸載節(jié)點集合，(卸載節(jié)點包括邊緣卸載的基站節(jié)點以及本地處理的用戶節(jié)點);EsSVs×Vs×Ls是邊的集合，每條邊表示基站-用戶-基站的2跳鏈路，標簽Ls用來表示基站對于用戶的可用時段，由平滑轉彎移動模型(smooth-turnmobilitymodel)給出。[0107]以圖1所示的研究場景為例解釋時序圖模型(如圖2所示)。對完整的卸載過程進行了三次采樣即將(0,D)時段用三個時間戳進行了標記，這表示用戶通過三次卸載過程在(0,D)時段內(nèi)完成計算密集型應用。第一個采樣時刻T?是用戶開始任務卸載的時刻，該時刻下用戶可卸載的基站集合為BS(T?)=BS?UBS?,第二個采樣時刻T?下用戶可卸載的基站集合為BS(T?)=BS?UBS?UBSs,第三個采樣時刻T?下用戶可卸載的基站集合為BS(T?)=BS?UBS?,因此整個任務卸載過程中用戶可接入的基站集合為BS=BS(T?)UBS(T?)UBS(T?),整個過程中可卸載節(jié)點的集合為Vs=BSU{BS?},其中BS。是用戶的終端設備以表示本地處理的計算卸載方式。對于基站節(jié)點BS和基站節(jié)點BS,之間鏈路的標簽，用Lm=(sm,n,am,)來表示用戶離開基站BS之后在基站BS范圍內(nèi)的可用時段。以T?時間戳下的基站3為例，基站1和基站3連邊上的時間戳為(t?,t?),在t?時刻用戶已經(jīng)離開BS?的覆蓋范圍并且進入了BS?的覆蓋范圍，在t?時刻離開BS?的覆蓋范圍；基站2和基站3連邊上的時間戳為(t3,t?),在t?時刻離開BS?的覆蓋范圍而此時用戶已經(jīng)在BS?的覆蓋范圍，所以連邊的開始時刻為t?,在t?時刻離開BS?的覆蓋范圍。[0108]待卸載的計算密集型應用是由多個存在依賴關系的子任務組成的，所以用應用圖(如圖3)來表示，即GA=(VA,EA),其中VA是子任務集合，邊的集合EASVA×VA×LA用來表示子任務之間的依賴關系，其中邊的標簽L是兩個子任務之間要轉移的數(shù)據(jù)量。如果子任務Vj∈V的輸入需要有子任務Vi∈V的輸出結果，則稱這兩個子任務之間存在依賴關系，子任務v,是子任務v的直接前序子任務，子任務v;是子任務v的直接后序子任務，則其依賴關系為(v,,v;)∈εA應用的時延限制為D(單位：秒),子任務的數(shù)量為I=IVAI,子任務下標子任務的輸入數(shù)據(jù)大小(單位：bit),μ;表示子任務所需的計算資源(單位：cycles),d,表示子任務的時延容忍值(latencytolerance)(單位：秒),子任務v;和子任務v;之間需要轉移的數(shù)據(jù)量記作C:,。[0109]在面臨子任務依賴性以及用戶移動性挑戰(zhàn)的情況下，為了求解任務卸載策略，將任務卸載問題抽象成圖同態(tài)問題，以建立卸載節(jié)點和子任務之間一對多的映射關系，這使得可以考慮應用圖中節(jié)點和邊的映射，實現(xiàn)對子任務的執(zhí)行計算時間以及數(shù)據(jù)轉移時間的同時優(yōu)化。對于圖同態(tài)問題的解決，采用圖編輯距離(GraphEditDistance,GED)作為圖相似性的指標，先確定編輯操作的集合，并且為每種編輯操作定義相應的成本，然后再定義相似性指標，最后用改進后的A*算法即所提供的OASA算法來求解圖編輯序列即任務卸載策[0110]將子任務v映射成卸載節(jié)點BS的操作作為轉換節(jié)點操作，記作VertexTrans(·)。卸載節(jié)點有兩種，第一種是用戶節(jié)點，第二種是基站節(jié)點，因此節(jié)點轉換操作有兩種成本。如果子任務被映射成用戶節(jié)點，則轉換節(jié)點操作的成本為該子任務本地計算的時間，即VerTrans(v)=μ;/f。。如果子任務被映射成基站節(jié)點，則節(jié)點轉換操作的成本為該子任務在邊緣卸載方式下的執(zhí)行時間，即VertexTrans(v;)=μ;/f。其中f。是用戶終端的CPU頻率，[0111]假設子任務v的卸載節(jié)點為BS,子任務v;的卸載節(jié)點為BS,則將子任務節(jié)點之間的連邊(v,,v)映射成卸載節(jié)點(BS,BS)之間的連邊的操作稱為轉換連邊操作，該操作的成本記作EdgeTrans(v,,v;)。子任務之間有連邊說明這兩