無人機(jī)接替場(chǎng)景中相似度感知的邊緣計(jì)算緩存算法*

王峻偉，范建華，王彥剛，王統(tǒng)祥，胡永揚(yáng)

（1.陸軍工程大學(xué)研究生院，江蘇 南京 210007；2.國(guó)防科技大學(xué)第六十三研究所，江蘇 南京 210007；3.軍事科學(xué)院系統(tǒng)工程研究院，北京 100000）

0 引言

移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）通過將計(jì)算和存儲(chǔ)資源下沉到網(wǎng)絡(luò)邊緣，為移動(dòng)用戶提供高性能、低延遲與高帶寬的服務(wù)環(huán)境。此外，得益于成本低、機(jī)動(dòng)靈活、快速部署等優(yōu)勢(shì)，在災(zāi)難救援和應(yīng)急響應(yīng)等特殊環(huán)境中，將無人機(jī)平臺(tái)充當(dāng)邊緣計(jì)算節(jié)點(diǎn)的技術(shù)得到了廣泛關(guān)注。在此類無人機(jī)邊緣計(jì)算場(chǎng)景中，無人機(jī)具有一定的感知、通信、計(jì)算和存儲(chǔ)能力，能夠緩存熱門內(nèi)容（如地圖數(shù)據(jù)、導(dǎo)航數(shù)據(jù)、災(zāi)難評(píng)估數(shù)據(jù)以及氣象水文數(shù)據(jù)等），并根據(jù)地面設(shè)備發(fā)送的內(nèi)容請(qǐng)求，將緩存內(nèi)容直接傳輸給地面設(shè)備，無需從遠(yuǎn)端云服務(wù)器下載，大幅降低了內(nèi)容傳輸時(shí)延。

與此同時(shí)，該技術(shù)也面臨著許多挑戰(zhàn)。一方面，無人機(jī)的快速移動(dòng)性可能導(dǎo)致服務(wù)中斷或連接丟失，使得單個(gè)無人機(jī)節(jié)點(diǎn)無法在動(dòng)態(tài)環(huán)境中為地面設(shè)備提供持續(xù)穩(wěn)定服務(wù)[1]；另一方面，無人機(jī)緩存能力有限，緩存內(nèi)容需要頻繁更新，導(dǎo)致了額外的數(shù)據(jù)傳輸延遲和能量消耗[2]。因此，迫切需要在無人機(jī)接替場(chǎng)景中設(shè)計(jì)一種高效簡(jiǎn)便的緩存算法，使得接替無人機(jī)上的緩存內(nèi)容能盡可能地滿足地面設(shè)備的需求。

本文重點(diǎn)關(guān)注無人機(jī)接替場(chǎng)景中邊緣計(jì)算緩存算法設(shè)計(jì)，針對(duì)執(zhí)行接替的無人機(jī)節(jié)點(diǎn)，提出了相似度感知緩存算法（Similarity-Aware Caching，SAC）。該算法綜合考慮接替無人機(jī)上緩存內(nèi)容的相似性、內(nèi)容流行度和接替距離，進(jìn)而選擇所緩存的內(nèi)容，從而在無人機(jī)緩存容量有限的約束下，提升接替緩存服務(wù)的質(zhì)量。

結(jié)構(gòu)如下：第1 節(jié)介紹相關(guān)工作，第2 節(jié)給出無人機(jī)邊緣計(jì)算動(dòng)態(tài)緩存場(chǎng)景；第3 節(jié)提出相似度感知緩存算法；第4 節(jié)對(duì)SAC 算法進(jìn)行實(shí)驗(yàn)仿真，驗(yàn)證該算法的有效性；第5 節(jié)對(duì)全文進(jìn)行總結(jié)。

1 相關(guān)工作

現(xiàn)有移動(dòng)邊緣計(jì)算的緩存算法大致可以分為3 類：傳統(tǒng)緩存算法、用戶偏好算法和機(jī)器學(xué)習(xí)算法[3]。傳統(tǒng)緩存算法包括最不常用、先進(jìn)先出和最近最少使用等簡(jiǎn)單的內(nèi)容替換算法，在簡(jiǎn)單的網(wǎng)絡(luò)架構(gòu)中具有良好的應(yīng)用效果；用戶偏好算法是將用戶偏好作為考量的高效緩存策略，一種典型方案是基于移動(dòng)視頻流行度算法（Most Frequency Used，MFU），根據(jù)現(xiàn)有視頻流行度的分布緩存流行度高的內(nèi)容，但是由于移動(dòng)網(wǎng)絡(luò)的緩存大小有限，使得MFU 算法在移動(dòng)網(wǎng)絡(luò)環(huán)境中緩存命中率過低[4]；機(jī)器學(xué)習(xí)算法通過跟蹤請(qǐng)求內(nèi)容的歷史記錄，預(yù)測(cè)內(nèi)容被請(qǐng)求的概率。He 等人提出了一種基于強(qiáng)化學(xué)習(xí)的邊緣緩存算法，通過編碼緩存的方法將緩存問題簡(jiǎn)化為與網(wǎng)絡(luò)連接性相關(guān)的線性規(guī)劃問題，解決了移動(dòng)邊緣網(wǎng)絡(luò)中的分布式緩存問題[5]。Hou 等人提出了一種基于學(xué)習(xí)的協(xié)同緩存（Learning-based Collaborative Caching，LECC）的主動(dòng)緩存算法，利用基于遷移學(xué)習(xí)的方法估計(jì)內(nèi)容的受歡迎程度，制定主動(dòng)緩存優(yōu)化模型，并采用貪心算法解決緩存內(nèi)容的布局問題，在提高用戶質(zhì)量的同時(shí)降低傳輸成本[6]。

然而，上述的研究關(guān)注于緩存算法本身，缺乏針對(duì)無人機(jī)場(chǎng)景下的邊緣計(jì)算緩存管理分析。具體來說，現(xiàn)有的緩存算法大多僅考慮靜態(tài)模型即內(nèi)容請(qǐng)求的數(shù)量是一個(gè)固定值，不考慮有新內(nèi)容請(qǐng)求的情況。同時(shí)，由于MEC 場(chǎng)景具有地面設(shè)備和無線傳輸環(huán)境動(dòng)態(tài)變化的特性，無人機(jī)節(jié)點(diǎn)之間的服務(wù)接替容易使得預(yù)先訓(xùn)練好的模型失效，而面對(duì)接替過程中大量指向新生內(nèi)容的請(qǐng)求，邊緣緩存需要額外的時(shí)間積累內(nèi)容請(qǐng)求歷史，導(dǎo)致服務(wù)啟動(dòng)緩慢，極大地削弱MEC 技術(shù)在時(shí)延和能耗方面的優(yōu)勢(shì)[7-9]。

2 無人機(jī)邊緣計(jì)算動(dòng)態(tài)緩存場(chǎng)景

2.1 邊緣計(jì)算場(chǎng)景架構(gòu)

典型的無人邊緣計(jì)算場(chǎng)景如圖1 所示，其中包含云數(shù)據(jù)中心、多個(gè)無人機(jī)節(jié)點(diǎn)和地面移動(dòng)設(shè)備。云數(shù)據(jù)中心維持一個(gè)完整內(nèi)容清單，且具有足夠存儲(chǔ)空間存儲(chǔ)所有的內(nèi)容。無人機(jī)節(jié)點(diǎn)具有有限的存儲(chǔ)空間，但其可以連接到云數(shù)據(jù)中心請(qǐng)求特定內(nèi)容。它主要由4 個(gè)模塊組成，分別是無線接口模塊、計(jì)算模塊、存儲(chǔ)模塊和網(wǎng)絡(luò)回程連接模塊。典型無線接口模塊采用的無線網(wǎng)絡(luò)通信協(xié)議是IEEE 802.11標(biāo)準(zhǔn)，具有實(shí)時(shí)調(diào)整無線鏈路上下行調(diào)制速率的功能，可以較好地適應(yīng)動(dòng)態(tài)條件下邊緣計(jì)算范式中的異構(gòu)環(huán)境。存儲(chǔ)模塊根據(jù)緩存策略有選擇地存儲(chǔ)流行度高的內(nèi)容。計(jì)算模塊用于處理用戶請(qǐng)求和感知無人機(jī)節(jié)點(diǎn)間的狀態(tài)信息。網(wǎng)絡(luò)回程連接模塊用于提供到云數(shù)據(jù)中心和其他無人機(jī)節(jié)點(diǎn)間的高速連接。

圖1 典型的無人機(jī)邊緣計(jì)算場(chǎng)景

基于以上功能，無人機(jī)可以有效實(shí)現(xiàn)對(duì)地面設(shè)備的服務(wù)接替。例如，圖1 中的無人機(jī)A 即將中斷對(duì)現(xiàn)有區(qū)域的服務(wù)時(shí)，向接替無人機(jī)B 發(fā)出服務(wù)接替請(qǐng)求。無人機(jī)B 在接收到目標(biāo)無人機(jī)A 的接替請(qǐng)求后，立即在飛行約束下飛向無人機(jī)A 的服務(wù)區(qū)域，以保障對(duì)地面設(shè)備服務(wù)的連續(xù)性[2]。此時(shí)，根據(jù)目標(biāo)服務(wù)區(qū)域的地面節(jié)點(diǎn)的狀態(tài)信息，接替無人機(jī)的飛行方向可轉(zhuǎn)化為對(duì)目標(biāo)服務(wù)區(qū)域最優(yōu)位置的約束優(yōu)化問題。

假設(shè)無人機(jī)的飛行高度固定，在t時(shí)刻，接替無人機(jī)的平面坐標(biāo)為SUAV(t)，目標(biāo)服務(wù)區(qū)域地面設(shè)備平面坐標(biāo)為Sc(t) 且數(shù)量為 C(t)，(xstart,xfinish)、(ystart,yfinish)分別為接替前服務(wù)區(qū)域和目標(biāo)服務(wù)區(qū)域的邊界，Zc(t)是目標(biāo)服務(wù)區(qū)域內(nèi)地面設(shè)備的服務(wù)請(qǐng)求權(quán)重，來源于接替無人機(jī)對(duì)狀態(tài)信息感知后的分配[10]。通過對(duì)式（1）求導(dǎo)得到的目標(biāo)服務(wù)區(qū)域最優(yōu)位置，可以獲取接替無人機(jī)的實(shí)時(shí)飛行方向。此外，在實(shí)際無人機(jī)運(yùn)動(dòng)中，需要考慮無人機(jī)的能耗、速度以及加速度等影響因素。本文采用文獻(xiàn)[11]中無人機(jī)節(jié)能飛行的設(shè)定，固定高度下的無人機(jī)飛行能量消耗只取決于速度和加速度，在此基礎(chǔ)上定義了接替無人機(jī)的飛行約束。無人機(jī)接替流程如圖2所示。

對(duì)于地面設(shè)備，假設(shè)它在請(qǐng)求服務(wù)時(shí)位置保持不變，并從一個(gè)與其保持通信連接的無人機(jī)節(jié)點(diǎn)處獲得服務(wù)。當(dāng)所連接無人機(jī)服務(wù)中斷時(shí)，地面設(shè)備可以在下一個(gè)時(shí)隙向服務(wù)范圍內(nèi)的其他無人機(jī)節(jié)點(diǎn)發(fā)起請(qǐng)求并獲得服務(wù)。

2.2 緩存管理過程

無人機(jī)節(jié)點(diǎn)接收到地面設(shè)備的內(nèi)容請(qǐng)求后，如果請(qǐng)求的內(nèi)容已存儲(chǔ)在緩存中，則無人機(jī)直接為地面設(shè)備提供服務(wù)；否則，需要通過主干鏈路從云數(shù)據(jù)中心請(qǐng)求內(nèi)容。此外，無人機(jī)記錄內(nèi)容請(qǐng)求的歷史記錄，用于計(jì)算內(nèi)容流行度。

為便于分析，將無人機(jī)提供服務(wù)的時(shí)段離散化為等長(zhǎng)的T個(gè)時(shí)隙 T={1,2,…,t,…,T}，設(shè)邊緣緩存網(wǎng)絡(luò)中時(shí)隙t的請(qǐng)求設(shè)備為 C(t)={1,2,3,…,c,…,C}。接替無人機(jī)節(jié)點(diǎn)B 上所緩存的內(nèi)容集合為，所有內(nèi)容請(qǐng)求都屬于內(nèi)容集合J={1,2,3,…,j,…,J}。無人機(jī)B 上關(guān)于內(nèi)容j的請(qǐng)求數(shù)量為，其中：

JB的數(shù)量受到無人機(jī)緩存容量的限制。當(dāng)無人機(jī)上的緩存空間已滿時(shí)，通過緩存算法優(yōu)先選取流行度高的內(nèi)容請(qǐng)求進(jìn)行緩存，替代原有緩存中流行度低的內(nèi)容。

3 相似度感知緩存算法SAC

為了提高接替無人機(jī)節(jié)點(diǎn)的服務(wù)質(zhì)量，避免服務(wù)中的“慢啟動(dòng)”，在對(duì)緩存管理過程分析的基礎(chǔ)上，設(shè)計(jì)了一種相似度感知緩存算法，綜合考慮緩存內(nèi)容相似性、接替距離與內(nèi)容流行度，分別計(jì)算已有內(nèi)容和新生內(nèi)容的流行度，確定接替無人機(jī)的緩存內(nèi)容。

3.1 已有內(nèi)容流行度計(jì)算

當(dāng)無人機(jī)實(shí)現(xiàn)接替后，會(huì)接收到所接替服務(wù)范圍內(nèi)地面設(shè)備的內(nèi)容請(qǐng)求，這些請(qǐng)求內(nèi)容已存在于接替無人機(jī)的歷史緩存記錄中，稱之為已有內(nèi)容。已有內(nèi)容中新近產(chǎn)生的內(nèi)容在未來被請(qǐng)求的概率仍然較高，因此將內(nèi)容的逗留時(shí)間表示為Δts=|tcurrenttgenerate|，其中tcurrent表示當(dāng)前時(shí)間，tgenerate表示為內(nèi)容生成時(shí)間。將內(nèi)容的新鮮度表示為Δtr=|tcurrenttrecent|，其中trecent表示最近被請(qǐng)求的時(shí)間。若內(nèi)容剛剛被訪問，則內(nèi)容的新鮮度較大，內(nèi)容流行度越高。綜合以上兩點(diǎn)考慮，已有內(nèi)容Jold的流行度表示為：

其中MJold,t表示已有內(nèi)容Jold從時(shí)隙0 到時(shí)隙t的被請(qǐng)求頻次。

3.2 新生內(nèi)容流行度計(jì)算

當(dāng)接替無人機(jī)接收到不存在于其歷史緩存記錄中的內(nèi)容請(qǐng)求時(shí)，式（5）中定義的流行度指標(biāo)將不適用于這些新生內(nèi)容。為了確定是否該緩存新內(nèi)容，可以利用一個(gè)觀察結(jié)論，即在一定的服務(wù)范圍內(nèi)，具有相同屬性的內(nèi)容往往具有類似的流行度[12]。例如，主角相同的視頻比主角不同的視頻更容易被同一設(shè)備請(qǐng)求。因此，對(duì)于固定服務(wù)范圍內(nèi)地面設(shè)備請(qǐng)求的新生內(nèi)容，如果它與接替無人機(jī)上已緩存的內(nèi)容有很高的相似性，那么它的內(nèi)容流行度就高；否則，它被地面設(shè)備請(qǐng)求的概率就低。同時(shí)，位于相鄰地理位置的地面設(shè)備往往感興趣的內(nèi)容相似，如當(dāng)?shù)氐奶鞖饣蛲话l(fā)事件，因此新生內(nèi)容的相似性需要考慮接替距離的影響。如果接替距離較短，與已緩存的內(nèi)容相似性的可信度就高；如果接替距離過長(zhǎng)，即使與接替無人機(jī)上已緩存的內(nèi)容有較高的相似性，也不足以成為其緩存的依據(jù)。另外，接替距離的影響會(huì)隨著接替無人機(jī)的服務(wù)時(shí)間衰減，即當(dāng)接替無人機(jī)的緩存已充分滿足接替服務(wù)范圍內(nèi)地面設(shè)備的需要后，其緩存更多考慮相似性指標(biāo)本身。

為了便于計(jì)算不同內(nèi)容的相似度，將內(nèi)容的概要描述為一個(gè)屬性向量。該向量由其數(shù)據(jù)類型、數(shù)據(jù)量、主題以及上下文信息等特征組成。具體來說，內(nèi)容j被表示為一個(gè)L維向量。新舊內(nèi)容Jold和Jnew的相似性τJold,Jnew為二者間的歐氏距離[13]：

其中，ω為屬性的特征權(quán)重，。

新生內(nèi)容在t時(shí)隙的流行度可以定義為：

其中，K為接替無人機(jī)上已有內(nèi)容數(shù)量，α為相似度系數(shù)，d為接替距離，t為無人機(jī)完成接替后的服務(wù)時(shí)長(zhǎng)，值始終大于0。當(dāng)無人機(jī)在接替任務(wù)開始前，使用式（7）表示當(dāng)前新生內(nèi)容的流行度。當(dāng)對(duì)接替范圍內(nèi)地面設(shè)備的服務(wù)開始后，需要考慮接替距離和服務(wù)時(shí)長(zhǎng)的影響，使用式（8）表示當(dāng)前新生內(nèi)容的流行度。當(dāng)服務(wù)時(shí)長(zhǎng)趨近于無窮時(shí)，趨向于1，即表示此時(shí)的相似度可信度高，可以忽略接替距離的影響。

3.3 無人機(jī)接替距離感知

無人機(jī)接替距離對(duì)于新生內(nèi)容流行度有著重要影響，在接替無人機(jī)上對(duì)服務(wù)區(qū)域的地面設(shè)備內(nèi)容請(qǐng)求進(jìn)行流行度計(jì)算時(shí)，必須要考慮到目標(biāo)狀態(tài)的動(dòng)態(tài)變化對(duì)無人機(jī)接替距離感知的影響。因此，SAC 算法采用卡爾曼濾波對(duì)接替的無人機(jī)感知的位置信息進(jìn)行處理，以得到相對(duì)準(zhǔn)確的接替距離[13]。

以圖1 中設(shè)計(jì)的場(chǎng)景為例，假設(shè)接替無人機(jī)B在t-1 時(shí)刻收到目標(biāo)無人機(jī)A 的接替請(qǐng)求，獲取無人機(jī)A 的狀態(tài)信息，執(zhí)行卡爾曼濾波預(yù)測(cè)接替時(shí)刻t的無人機(jī)A 位置。

3.3.1 狀態(tài)空間模型建立

采用CV 動(dòng)力學(xué)運(yùn)動(dòng)模型[14]對(duì)無人機(jī)A 飛行狀態(tài)建模，其x和y方向的加速度模擬為高斯白噪聲，無人機(jī)A 的狀態(tài)方程s(t)和觀測(cè)方程u(t)定義為：

其中，狀態(tài)方程s(t)=(x(t),y(t),vx(t),vy(t))，包括位置分量和速度分量。式（9）表示目標(biāo)無人機(jī)狀態(tài)的改變是由前一時(shí)刻狀態(tài)和當(dāng)前激勵(lì)噪聲決定的；式（10）表示觀測(cè)的數(shù)據(jù)是由當(dāng)前狀態(tài)和觀測(cè)噪聲決定的。

3.3.2 預(yù)測(cè)過程

步驟一：在t-1 時(shí)刻，接替無人機(jī)B 根據(jù)無人機(jī)A 的狀態(tài)信息，預(yù)測(cè)t時(shí)刻無人機(jī)A 的位置。

步驟二：計(jì)算最小均方誤差P(t|t-1)和卡爾曼增益矩陣G(t)。

其中R和Q定義為式（9）和式（10）中v(t)和w(t)的協(xié)方差矩陣。

步驟三：在t時(shí)刻，根據(jù)觀測(cè)方程u(t)修正狀態(tài)向量。

3.4 SAC 算法偽代碼

算法1 說明了相似度感知緩存（SAC）算法。首先，輸入每架接替無人機(jī)上的內(nèi)容相似度矩陣和目標(biāo)無人機(jī)的狀態(tài)信息，通過卡爾曼濾波進(jìn)行數(shù)據(jù)處理。從步驟4 到步驟9，在每個(gè)時(shí)隙中，如果請(qǐng)求內(nèi)容是舊內(nèi)容，算法使用式（5）計(jì)算內(nèi)容的流行度值；當(dāng)內(nèi)容是新生內(nèi)容時(shí)，若無人機(jī)處于未接替狀態(tài)，使用式（7）計(jì)算內(nèi)容的流行度值；在接替完成后，使用式（8）計(jì)算內(nèi)容的流行度值。步驟11 到步驟13 根據(jù)流行度值的大小在接替無人機(jī)上緩存內(nèi)容。

算法1：相似度感知緩存（SAC）算法

輸入：內(nèi)容相似度矩陣，目標(biāo)無人機(jī)狀態(tài)信息，地面設(shè)備請(qǐng)求內(nèi)容矩陣Q（其中行表示地面設(shè)備，列表示內(nèi)容）

輸出：接替無人機(jī)節(jié)點(diǎn)緩存矩陣X

4 仿真實(shí)驗(yàn)

為了評(píng)估相似度感知緩存算法的性能，設(shè)置了一個(gè)典型的無人機(jī)接替場(chǎng)景。在半徑為2 km 的服務(wù)范圍包括一個(gè)云數(shù)據(jù)中心、N架無人機(jī)和多個(gè)地面設(shè)備。同時(shí)，下一組的N架接替無人機(jī)在服務(wù)地面設(shè)備的同時(shí)，保持對(duì)目標(biāo)無人機(jī)的跟蹤并準(zhǔn)備接替。每架無人機(jī)的高度固定為200 m，飛行時(shí)速為5 m/s，最大加速度為4 m/s2且最大轉(zhuǎn)彎角度為30°，數(shù)據(jù)傳輸速率由無人機(jī)的發(fā)送功率決定，每架無人機(jī)的緩存容量為600 MB。

仿真周期分為若干個(gè)時(shí)隙，在初始時(shí)隙中，服務(wù)范圍內(nèi)均勻分布有50 個(gè)地面設(shè)備，內(nèi)容數(shù)量為100 且每個(gè)內(nèi)容大小為z。在每個(gè)時(shí)隙中，地面設(shè)備向無人機(jī)節(jié)點(diǎn)隨機(jī)請(qǐng)求內(nèi)容，當(dāng)?shù)孛嬖O(shè)備未向無人機(jī)節(jié)點(diǎn)請(qǐng)求時(shí)，被視為設(shè)備離開，地面設(shè)備的到達(dá)離開服從泊松分布。同時(shí)，對(duì)于舊內(nèi)容的請(qǐng)求分布考慮實(shí)際情況，內(nèi)容生成時(shí)間間隔越短、越新的內(nèi)容，有較大概率被用戶請(qǐng)求；對(duì)于新生內(nèi)容的分布通常建模為參數(shù)為γ的Zipf 分布[15]。當(dāng)接收到內(nèi)容請(qǐng)求后，無人機(jī)節(jié)點(diǎn)執(zhí)行SAC 緩存算法并更新其緩存的內(nèi)容，然后將請(qǐng)求的內(nèi)容傳輸?shù)皆O(shè)備。

相關(guān)仿真參數(shù)設(shè)置如表1 所示。

表1 實(shí)驗(yàn)仿真參數(shù)

4.1 性能指標(biāo)

4.1.1 緩存命中率

當(dāng)內(nèi)容請(qǐng)求到達(dá)時(shí)，如果請(qǐng)求的內(nèi)容存儲(chǔ)在服務(wù)的無人機(jī)節(jié)點(diǎn)，稱為緩存命中。如果內(nèi)容并沒有存儲(chǔ)在無人機(jī)節(jié)點(diǎn)，而無人機(jī)節(jié)點(diǎn)通過骨干網(wǎng)絡(luò)將請(qǐng)求轉(zhuǎn)發(fā)給云數(shù)據(jù)中心，即緩存丟失。因此，緩存命中率被定義為：其中R為每個(gè)時(shí)隙中邊緣節(jié)點(diǎn)接收到的請(qǐng)求總數(shù)，M為緩存未命中的次數(shù)。

4.1.2 接替后服務(wù)時(shí)延

在上述服務(wù)用戶過程中，用戶請(qǐng)求由無人機(jī)節(jié)點(diǎn)或者通過云數(shù)據(jù)中心進(jìn)行處理。這個(gè)過程涉及到兩個(gè)傳輸過程，即地面設(shè)備到無人機(jī)節(jié)點(diǎn)間的請(qǐng)求傳輸過程和無人機(jī)節(jié)點(diǎn)到云數(shù)據(jù)中心的內(nèi)容傳輸過程[15]。為了使分析過程簡(jiǎn)明清楚，假設(shè)地面設(shè)備和無人機(jī)傳輸過程中時(shí)延為EAC，將無人機(jī)節(jié)點(diǎn)和云數(shù)據(jù)中心之間傳輸?shù)臅r(shí)延定義為EAD，而無人機(jī)節(jié)點(diǎn)上的任務(wù)處理時(shí)延為OA，云中心上任務(wù)處理時(shí)延為OD，服務(wù)過程中總的時(shí)延可表示為：

其中，式（16）忽略了實(shí)際任務(wù)執(zhí)行中的排隊(duì)時(shí)延，將傳輸時(shí)延簡(jiǎn)化為內(nèi)容量與傳輸數(shù)率的比值，即：

其中，Xj用來表示請(qǐng)求內(nèi)容j已緩存在接替無人機(jī)節(jié)點(diǎn)上的概率，r表示傳輸速率。

4.1.3 接替成功率

當(dāng)無人機(jī)離開服務(wù)范圍時(shí)，所服務(wù)的地面設(shè)備可以通過通信范圍內(nèi)的其他無人機(jī)進(jìn)行內(nèi)容請(qǐng)求。比較這種任務(wù)遷移所產(chǎn)生的時(shí)延與地面設(shè)備的時(shí)延容忍度Tr，當(dāng)系統(tǒng)中接替后地面設(shè)備獲取內(nèi)容的總時(shí)延低于時(shí)延容忍度Tr，則表明接替成功；否則，定義為接替失敗。對(duì)于時(shí)延容忍度Tr，定義為所有地面設(shè)備在接替前平均接收時(shí)延的加權(quán)值，則接替成功率?Tr可以表示為：

其中，CTr為獲取內(nèi)容時(shí)延低于Tr的地面設(shè)備數(shù)量，C為時(shí)隙中向接替無人機(jī)請(qǐng)求服務(wù)的地面設(shè)備數(shù)量。

4.2 實(shí)驗(yàn)結(jié)果

圖3 反映了接替無人機(jī)節(jié)點(diǎn)上緩存命中率隨接替時(shí)間變化的情況。為了更好地體現(xiàn)SAC 緩存算法的優(yōu)勢(shì)，與3 種緩存算法進(jìn)行比較，分別是隨機(jī)替換（Random，RR）、非負(fù)矩陣分解機(jī)器學(xué)習(xí)算法（Nonnegative Matrix Factor，NMF）和基于流行度的緩存算法（Most Frequency Used，MFU）。RR 算法使用隨機(jī)決策查找要替換的內(nèi)容項(xiàng)。NMF 算法利用過去請(qǐng)求中出現(xiàn)的時(shí)間局部性預(yù)測(cè)未來的內(nèi)容請(qǐng)求[16]。在MFU 算法中，邊緣節(jié)點(diǎn)都主動(dòng)緩存當(dāng)前最常請(qǐng)求的內(nèi)容項(xiàng)，直到緩存內(nèi)存滿為止。由圖3 可以看出，RR 算法的緩存命中率在40%左右，是4 種算法中最低的。相比之下，SAC 算法在各個(gè)時(shí)間段的性能都優(yōu)于其他3 種算法，緩存命中率比MFU、NMF 和RR 高17%～23%。這是因?yàn)樵趧?dòng)態(tài)環(huán)境下，SAC 算法綜合考慮內(nèi)容的流行性和相似性，可以更好地適應(yīng)無人機(jī)接替場(chǎng)景中的服務(wù)需要。

圖3 接替無人機(jī)節(jié)點(diǎn)緩存命中率

圖4 給出了接替無人機(jī)節(jié)點(diǎn)對(duì)地面設(shè)備的平均服務(wù)時(shí)延。可以看出，RR 算法的平均服務(wù)時(shí)延最長(zhǎng)，而SAC 算法有著較低的服務(wù)時(shí)延，這是因?yàn)镾AC算法有著較好的緩存命中率，使得地面設(shè)備的內(nèi)容請(qǐng)求能夠直接被無人機(jī)節(jié)點(diǎn)處理，而無需向遠(yuǎn)距離的云數(shù)據(jù)中心轉(zhuǎn)發(fā)內(nèi)容請(qǐng)求，大大降低了數(shù)據(jù)的傳輸時(shí)延，也更加體現(xiàn)出MEC 的優(yōu)勢(shì)。

圖4 接替無人機(jī)對(duì)地面設(shè)備的平均服務(wù)時(shí)延

圖5 給出了新生內(nèi)容相似度系數(shù)α對(duì)于SAC緩存算法的影響。α=0.6 是本環(huán)境設(shè)置的最優(yōu)值。隨著α的增長(zhǎng)，接替無人機(jī)節(jié)點(diǎn)的平均緩存命中率從0.6 增加到0.75；當(dāng)α達(dá)到0.6 時(shí)，緩存命中率開始下降。這意味著在計(jì)算新生內(nèi)容的流行度時(shí)，相似性作為重要的指標(biāo)具有一定的參考意義。

圖5 不同的相似系數(shù)下的SAC 算法的緩存命中率

圖6 反映了N架無人機(jī)節(jié)點(diǎn)在系統(tǒng)中通過SAC算法后的接替成功率變化。選取不同的內(nèi)容大小反應(yīng)無人機(jī)節(jié)點(diǎn)在處理不同任務(wù)量上的變化，同時(shí)給出了一個(gè)對(duì)比方案，即選取服務(wù)范圍內(nèi)離地面設(shè)備最近的無人機(jī)執(zhí)行服務(wù)接替。可以看出，經(jīng)通過SAC 算法后的無人機(jī)接替成功率要大于對(duì)比方案。同時(shí)，隨著內(nèi)容數(shù)據(jù)量的增大，兩種接替方案在接替成功率上均有降低，而通過增加服務(wù)范圍內(nèi)的無人機(jī)數(shù)量可以有效提高接替的成功率，反映了SAC算法在多無人機(jī)接替場(chǎng)景中的有效性。

圖6 接替成功率

5 結(jié)語

無人機(jī)邊緣計(jì)算平臺(tái)由于有限的緩存容量和能量供應(yīng)，需要高效的緩存算法滿足地面設(shè)備的內(nèi)容請(qǐng)求。本文首先描述動(dòng)態(tài)環(huán)境下的移動(dòng)邊緣計(jì)算場(chǎng)景，分析無人機(jī)接替中的緩存管理；其次，提出了相似度感知緩存算法，給出了針對(duì)于接替無人機(jī)節(jié)點(diǎn)上新生內(nèi)容和已有內(nèi)容的流行度計(jì)算方法；最后，通過一系列模擬試驗(yàn)對(duì)比了SAC 算法與傳統(tǒng)緩存方法的緩存性能，證明了所提出方法的有效性。下一步將緩存能耗與無人機(jī)節(jié)點(diǎn)之間的協(xié)作緩存進(jìn)行分析評(píng)估，采用最優(yōu)化方法給出無人機(jī)協(xié)作緩存的理論解，并分析多個(gè)無人機(jī)相互協(xié)作服務(wù)于某個(gè)特定區(qū)域的部署。