無人機輔助蜂窩網絡中的無人機與用戶協同緩存算法

張天魁，陳超，王子端，楊鼎成

（1.北京郵電大學通信與信息工程學院，北京 100876；2.南昌大學信息工程學院，江西 南昌 330031）

1 引言

憑借靈活的飛行特性以及良好的信道特征，無人機（UAV,unmanned aerial vehicle）可作為空中基站提供通信服務。將無人機引入蜂窩網絡，可有效擴展系統容量，緩解地面基站負載，有望在通信恢復、熱點覆蓋等場景發揮重要作用[1]。在無人機輔助蜂窩網絡中，面對大量重復數據傳輸帶來的流量擁塞，主動緩存技術將流行度較高的熱點內容提前存儲在無人機等離用戶更近的邊緣節點上，可有效緩解網絡負載壓力，改善用戶內容獲取性能[2]。因此，結合邊緣緩存的無人機輔助蜂窩網絡成為當前的熱點研究方向之一。

然而，面對網絡中的海量多媒體內容，如何在有限的存儲空間內緩存最合適的內容是需要解決的關鍵問題。文獻[3]針對無人機具有緩存能力的場景采用基于預測的主動緩存方法，使用機器學習框架來預測用戶請求分布模式，繼而根據預測結果決定無人機緩存的內容。文獻[4]分析了無人機輔助蜂窩網絡的典型架構，并針對地面基站和無人機基站同時具備緩存能力的場景提出了一種基于內容分片協作傳輸的分布式緩存方法。文獻[5]將無人機網絡與設備間（D2D,device-to-device）通信結合實現內容分發。文獻[6-7]研究了D2D緩存網絡中的資源分配和緩存放置問題。文獻[7]在無人機網絡中引入D2D緩存，提出了一種緩解無人機能量受限問題的方法，該方法由無人機將熱點內容發送給用戶進行緩存，然后用戶間通過D2D通信進行內容共享，以減少無人機與用戶之間重復數據傳輸帶來的無人機能量消耗。上述文獻僅在無人機輔助蜂窩網絡中研究基站與無人機協同緩存、無人機緩存以及用戶緩存問題。

本文在無人機輔助蜂窩網絡中同時在無人機以及用戶設備上部署緩存，提出了基于邊緣緩存的無人機與用戶設備協同緩存網絡模型。一方面，提供通信服務的無人機可以攜帶緩存資源進行內容存儲，當用戶請求到達時，無人機直接從緩存中將內容發送給用戶，不僅讓用戶更快速地獲取內容，也能減少無線回程鏈路數據傳輸帶來的資源與能量消耗；另一方面，引入D2D通信和用戶緩存，用戶存儲的內容通過D2D通信更快捷地傳輸給附近用戶，不僅有效擴展網絡的覆蓋范圍，同時提升了系統的緩存容量，緩解無人機緩存空間受限和能量受限的問題，當無人機電量耗盡通信中斷時，內容也能通過D2D通信在用戶間分享、傳輸。針對無人機與用戶設備同時具備緩存能力的場景，本文以最小化用戶的內容獲取時延為目標建立無人機與用戶緩存聯合優化問題，并提出了一種無人機與用戶協同緩存算法，該算法首先基于交替方向乘子法（ADMM,alternating direction method of multiplier）和全局貪婪算法分別對無人機緩存子問題和用戶緩存子問題進行求解，然后采用迭代的方式聯合優化無人機與用戶的緩存內容，實現協同緩存。仿真結果表明，所提算法可有效降低用戶的內容獲取時延。

2 系統模型

圖1 無人機輔助蜂窩網絡系統模型

無人機輔助蜂窩網絡系統模型如圖1所示，由一個宏基站（MBS,macro base station）、多個UAV基站和多個用戶構成。b表示MBS，K={1,2,…,K}表示K個UAV，H表示高度，N={1,2,…,N}表示系統內請求數據內容服務的N個用戶設備（UE,user equipment）。宏基站通過提供高速數據傳輸的有線光纖線路連接到移動核心網。為了提供UAV與移動核心網之間的數據傳輸，UAV與MBS之間通過容量受限的無線回程鏈路連接，當UAV需要獲取用戶請求但未緩存的內容時，可通過回程鏈路與MBS建立連接，然后向核心網請求內容。

2.1 通信模型

接下來，給出無人機地對空通信模型、宏基站與用戶間通信模型以及用戶間D2D通信模型。

定義無人機與用戶間通信頻段為WK，基站與用戶間通信頻段為WB，無人機與基站間回程鏈路帶寬為WE，為了減少干擾，各頻段相互正交。由于無人機部署在不同位置，為了提高頻譜利用率，K個無人機重用頻段WK。假設D2D通信使用帶內復用模式，復用宏基站的上行頻帶資源，通信頻段為WN，不同D2D通信間帶寬相互正交，不存在干擾，但仍會受到使用該頻段的蜂窩用戶上行信號的干擾。

由于飛行和高度特性，無人機與地面用戶和基站之間的通信具有視距（LoS,line of sight）傳輸和非視距（NLoS,no line of sight）傳輸2種情況，因此，本文使用概率傳輸模型來模擬無人機地對空通信間的平均路徑損耗[8]。通過選取不同的信道參數，該模型可以模擬不同地理環境下不同中心頻率的地對空通信模型。

無人機k與用戶n之間的LoS路徑損耗以及NLoS路徑損耗（單位都為dB）為

其中，X和Y是取決于地理環境（鄉村、城鎮、密集城鎮等）的常參數，是無人機k與用戶n之間的仰角。無人機k與用戶n之間的平均路徑損耗為

當無人機k與用戶n進行通信時，下行鏈路傳輸速率為

其中，Wk,n為無人機k分配給用戶n的下行頻帶資源，PUAV為無人機的發送功率，σ2為噪聲功率。無人機k的回程鏈路傳輸速率為

其中，zk,n為接入無人機k的用戶n所分到的回程鏈路帶寬，PBS為宏基站的發送功率。

針對地面基站，根據3GPP標準[9]，宏基站b與用戶n之間的路徑損耗（單位為dB）為

其中，db,n為宏基站b與用戶n的距離。當宏基站b與用戶n進行通信時，下行鏈路傳輸速率為

其中，Wb,n為宏基站b分配給用戶n的下行頻帶資源。

用戶可與通信范圍內的其他用戶建立D2D鏈路進行內容傳輸。假設用戶最大通信范圍為L，用戶n與n′之間的路徑損耗（單位為dB）為

當用戶n與n′進行通信時，傳輸速率為

其中，Wn,n′為用戶n與n′的可用帶寬，n′為與n共享頻帶的蜂窩上行用戶，PUE為用戶發送功率。

2.2 用戶偏好模型

設網絡中有M個內容，分別用M={1,2,…,M}表示。不失一般性地，本文假設所有內容大小相同，用S表示，此假設可以通過將具有各種大小的內容劃分或組合為具有統一大小的內容數據分組得到。網絡中的用戶對于不同內容往往具有不同的偏好，例如，有些用戶喜歡體育、娛樂類內容，有些用戶喜歡時政類內容等。因此，本文使用用戶偏好模型來模擬用戶的內容請求分布[10]。

設網絡中有A個主題的內容屬性，例如體育、娛樂等，用集合A={ε1,ε2,…,εA}表示。g(m,εa)為內容屬性指示，g(m,εa)=1表示內容m具有主題εa的屬性，g(m,εa)=0則表示沒有，不同用戶具有不同的主題偏好，用戶n對主題εa的偏好可表示為

其中，Vj表示用戶n的歷史內容請求，X(εh)表示所有內容中具有主題εa的內容的隨機變量，p(X(εa))表示所有內容中具有主題εa的內容的概率，P(X(εa)|Vj)表示用戶歷史內容請求中具有主題εa的內容的概率。因此，用戶n對內容m的偏好為

其中，0≤cn,m≤1，g(m,εa)和ω(n,εa)越接近，則用戶n越喜歡內容m。

3 無人機與用戶協同緩存算法

3.1 問題建模

為了緩解網絡峰值流量期間的負載壓力，降低用戶獲取內容的時延，無人機預先緩存部分熱點內容，當用戶發來已緩存的內容請求時，直接將內容副本發送給用戶。每個用戶設備具有一定容量的緩存塊進行內容存儲，一方面，滿足自身的內容請求；另一方面，通過D2D通信將內容傳輸給附近用戶進行共享，以緩解無人機緩存空間受限的問題，進一步降低用戶獲取內容的時延。

yn,m為用戶設備緩存指示，用戶n緩存內容m，則yn,m=1；否則yn,m=0，矩陣y=[yn,m]表示所有用戶的緩存情況。xk,m為無人機緩存指示，無人機k緩存內容m，則xk,m=1；否則xk,m=0，矩陣x=[xk,m]表示無人機的緩存情況?？紤]到無人機的負載限制以及用戶的空間限制，無人機和用戶緩存空間均是有限的。不失一般性地，假設每個無人機以及用戶的緩存容量都是相同的，分別用QK和QN表示，則且QK≤M，QN≤M。

集合Fn表示用戶n緩存的所有內容，即集合Fk表示無人機k緩存的所有內容，即Fk={m|xk,m=1,m∈M}。當用戶n請求內容m時，n首先查看自身是否已緩存m，若已緩存，則直接通過自身緩存獲??；若未緩存，則向通信范圍內的其他用戶廣播內容請求。若附近有用戶緩存內容m，則n與該用戶建立D2D鏈路獲取該內容；如附近無用戶緩存內容m，則n根據最大信噪比方式接入無人機或宏基站。若接入的無人機已緩存m，則無人機直接將m傳輸給n；若無人機未緩存m，則需通過無線回程鏈路由宏基站轉發用戶請求并回傳給n。若用戶接入宏基站，則宏基站需向移動核心網請求內容m，再傳輸給用戶n。由于宏基站通過高容量光纖鏈路連接到移動核心網，本文不考慮基站與移動核心網之間傳輸內容的時延。因此，當用戶n請求內容m時，根據用戶以及無人機的緩存情況，用戶n獲取內容m的時延Dn,m可細分為下述5種情況。

1)當用戶n通過自身緩存獲取內容m時，m∈Fn，則用戶n可以無時延地獲取所需內容，即Dn,m=0。

2)當用戶n通過附近用戶n′緩存獲取內容m時，yn′,m=1}，則n與n′建立D2D連接，然后由n′將內容m發送給n，即

3)當用戶n通過無人機k的緩存獲取內容m時，則k直接從緩存將m通過下行鏈路發送給n，即

4)當用戶n由無人機通過回程鏈路接入核心網獲取內容m時，即m?Fn∩m?Fn′∩m?Fk，則k首先通過回程鏈路從核心網獲得內容m，然后通過下行鏈路傳輸給用戶，時延包括回程鏈路傳輸時延和下行鏈路傳輸時延，即

5)當用戶n通過宏基站b獲取內容m時，即則b向核心網請求m后通過下行鏈路將m傳輸給用戶，即

根據上述分析，當用戶進行內容請求時，不同的內容服務情況下用戶獲取內容的時延不同，使用用戶接入指示un,i表示用戶獲取內容服務的來源，其中用戶n與i建立通信鏈路，則un,i=1；否則un,i=0。因此，用戶的內容獲取時延可表示為

為了提升用戶的服務質量，降低內容獲取時延，本文以最小化全網用戶平均內容獲取時延為目標建立無人機與用戶緩存聯合優化問題P1。

顯然，P1為組合優化問題。

3.2 問題求解

為了更好地解決上述最優化問題，在較低復雜度情況下實現較高的優化性能，本文將問題進一步分解為2個子問題，即無人機緩存子問題和用戶緩存子問題。

在已知的用戶內容緩存y下，原優化問題P1可轉化為關于無人機緩存的子問題P2。

將無人機緩存變量進行松弛，轉化為[0,1]取值的連續變量，即xk,m∈[0,1],?k∈K,m∈M，則P2可轉化為凸集上的凸優化問題，然后采用ADMM分布式優化各無人機緩存的內容。

P2的增廣拉格朗日函數為

基于ADMM[11]，在每個迭代周期t，無人機k順序優化其每一個緩存變量xk,m，然后更新拉格朗日乘子，如式(17)所示，直到用戶內容獲取時延D不再變化，得到k最終的緩存內容xk。

對于式(17)中每個xk,m的最小化問題，由于此時L為包含約束條件的增廣拉格朗日函數，該問題是一個無約束優化問題。對于無約束優化問題，本文采用梯度下降法對ADMM迭代過程中xk,m最小化問題進行求解。任意xk,m的最小化問題可表示為

式(18)的梯度為

因此，基于ADMM的無人機緩存過程包含兩層迭代。外層迭代t-1～t為ADMM交替方向求解過程，該過程順序更新所有優化變量xk以及拉格朗日乘子λk；在每一個外層迭代t中，均有M個內層迭代p用于求解xk的每個優化變量xk,m。需要注意的是，由于xk,m∈[0,1]，所有內層迭代結束后，需將xk,m固定為0～1。同時，所有外層迭代結束后，需要在無人機緩存空間限制下進行去松弛，將取值為0～1的xk,m轉化為0或1。求解流程如算法1所示。

該0-1整數規劃問題屬于復雜背包問題，本文采用全局貪婪算法[12]求解。在每一次貪婪決策中，計算每個用戶緩存每個內容減少的時延，然后找出減小程度最大的用戶和內容進行緩存，該過程不斷迭代，直到所有用戶緩存空間已滿，最終得到網絡中每個用戶最優的緩存內容。用戶n緩存內容m將減小的時延可表示為

3.3 算法流程

根據上述2個子問題的分析，本文提出了一種無人機與用戶設備協同緩存算法，如算法3所示。

算法3中，首先，根據系統的輸入參數進行優化變量的初始化。然后，在每一次迭代周期內依次更新無人機緩存和用戶緩存：無人機根據上一迭代周期得到的無人機與用戶緩存結果通過算法1得到此時最佳的緩存內容，繼而用戶根據更新的無人機緩存結果通過算法2得到此時最佳的緩存內容。該過程不斷迭代，直到優化目標全網用戶平均內容獲取時延不再降低。迭代結束后，輸出最終的無人機與用戶緩存的結果。

本文所提算法在實際應用中需要無人機基站以及用戶設備部署具有線速存取能力的存儲設備。目前，TB量級的存儲設備質量為200 g左右，適合部署在無人機中。片上存儲芯片每平方厘米容量可達百兆字節量級，適合集成在用戶設備中。

需要指出的是，本文所提算法可進一步推廣到更一般的蜂窩網絡場景，應用廣泛。在無人機移動場景中，可以對不同位置無人機部署下的用戶平均內容獲取時延進行平均，然后用于無人機和用戶的協同緩存優化。在不同蜂窩網絡場景中，用戶內容獲取時延影響因素不同，相應地，通過修改式(13)的表達式，可以將本文所提算法擴展到不同蜂窩網絡場景中。

4 仿真結果與分析

仿真基于半徑500 m的蜂窩小區，無人機飛行高度為300 m，D2D通信范圍為50 m，宏基站、無人機與用戶發送功率分別為43 dBm、30 dBm、23 dBm，噪聲功率譜密度為-174 dBm/Hz，宏基站、無人機、D2D以及回程鏈路帶寬分別為10 MHz、20 MHz、20 MHz、20 MHz，網絡中的內容大小為10 Mbit/s。

為了驗證所提算法的有效性，本文采用以下2種算法進行對比分析。1)隨機緩存：每個無人機或者用戶隨機選擇緩存內容，直到緩存空間已滿。2)最大流行度緩存：每個無人機或者用戶緩存網絡中內容流行度最高的內容，直到緩存空間已滿。

4.1 所提算法的收斂性及最優性分析

為了驗證所提算法的收斂性與最優性，圖2給出了小規模網絡場景下所提算法迭代次數與時延的關系。無人機數量K=1，用戶數量N=5，內容數量M=8，無人機緩存空間QK=4，用戶緩存空間QN=1?？梢钥闯?，在小規模場景下，所提算法在迭代10次以內可以達到收斂。當迭代10次時，所提算法得到的結果（0.022 66）非常接近遍歷搜索得到的全局最優解（0.022 42），差距約為1.07%。這表明所提算法可在較低復雜度情況下得到具有較小差距的近似最優解，實現較高的優化性能。

圖2 小規模網絡場景下所提算法迭代次數與時延的關系

4.2 無人機與用戶協同算法有效性分析

圖3展示了K=3、M=80場景下無人機與用戶均無緩存、無人機有緩存、無人機與用戶均有緩存這3種情況下的時延性能。與無人機與用戶均無緩存（QK=QN=0）相比，無人機有緩存（QK=40）在N=60情況下可降低約18%的用戶時延，這表明在無人機上部署緩存，可有效降低用戶時延；通過無人機與用戶協同緩存（QK=40，QN=5），可繼續降低約30%的用戶時延，這說明在用戶設備上進行緩存，與無人機緩存相互配合，可大幅提升系統時延性能。當用戶緩存空間增加至QN=10時，時延性能增益進一步增加。因此，通過上述不同緩存情況下的時延性能對比可以看出，本文提出的無人機與用戶協同緩存算法可有效提升系統的時延性能。

圖3 時延性能分析

4.3 緩存空間對時延性能的影響分析

圖4和圖5給出了不同無人機和用戶緩存空間下所提算法、隨機緩存算法以及最大流行度算法的時延性能對比結果，其中K=3、M=80。圖4為不同無人機緩存空間下時延性能隨著用戶數目變化曲線?？梢钥闯?，無人機緩存空間由20增加至40后，緩存內容也隨之增加，3種算法的用戶平均內容獲取時延均下降，所提算法的時延最小。圖5為不同用戶緩存空間下時延性能隨著用戶數目變化曲線?？梢钥闯?，相對于隨機緩存與最大流行度緩存，所提算法在QN=5以及QN=10時的時延均處于最低水平。圖4和圖5的仿真結果表明，隨著用戶數量的增加，所有算法的時延均有所上升，但所提算法時延一直小于對比算法，且隨著網絡規模的增大，所提算法的時延性能優勢更加明顯。

圖4 無人機緩存空間對時延性能的影響（QN=5）

圖5 用戶緩存空間對時延性能的影響（QK=40）

5 結束語

本文提出了一種無人機輔助蜂窩網絡中的無人機與用戶協同緩存算法，通過在無人機與用戶設備上同時部署緩存來降低用戶獲取內容的時延。所提算法通過無人機緩存決策與用戶緩存決策的優化迭代，實現了無人機與用戶的協同緩存優化。在每一迭代周期內，分別基于ADMM與全局貪婪算法得到當前無人機與用戶緩存的內容。仿真結果表明，所提算法可以有效降低用戶獲取內容的時延。