移動(dòng)邊緣計(jì)算中的無(wú)人機(jī)三維部署和內(nèi)容緩存優(yōu)化方法

摘 要：隨著無(wú)線網(wǎng)絡(luò)中的移動(dòng)數(shù)據(jù)流量爆炸式增長(zhǎng)，支持高速緩存的無(wú)人機(jī)被應(yīng)用于移動(dòng)計(jì)算領(lǐng)域充當(dāng)邊緣服務(wù)器，為網(wǎng)絡(luò)中的用戶提供按需服務(wù)。為了在滿足其他資源約束的條件下，給用戶帶來(lái)更好的體驗(yàn)，通過(guò)聯(lián)合優(yōu)化無(wú)人機(jī)部署、緩存放置和用戶關(guān)聯(lián)以實(shí)現(xiàn)最小化所有用戶的內(nèi)容訪問(wèn)時(shí)延，并為用戶提供質(zhì)量不同的內(nèi)容緩存服務(wù)。針對(duì)多無(wú)人機(jī)和地面基站協(xié)同提供緩存服務(wù)的場(chǎng)景，提出了一種基于迭代優(yōu)化的聯(lián)合優(yōu)化算法。該算法通過(guò)迭代求解由目標(biāo)問(wèn)題分解得到的三個(gè)子問(wèn)題的方式來(lái)獲得具有收斂性保證的次優(yōu)解決方案。首先，采用基于連續(xù)凸近似的算法求解無(wú)人機(jī)部署子問(wèn)題；其次，采用基于貪心的算法求解內(nèi)容緩存子問(wèn)題；然后，利用基于罰函數(shù)的連續(xù)凸近似算法求解用戶關(guān)聯(lián)子問(wèn)題；最后，對(duì)上述過(guò)程重復(fù)迭代，得到目標(biāo)問(wèn)題的一個(gè)次優(yōu)解。多次仿真實(shí)驗(yàn)驗(yàn)證了所提算法的有效性和可行性。仿真結(jié)果表明，與基準(zhǔn)算法相比，所提聯(lián)合優(yōu)化算法在平均內(nèi)容訪問(wèn)時(shí)延、緩存命中率兩方面均具有更好的性能。

關(guān)鍵詞：移動(dòng)邊緣計(jì)算； 無(wú)人機(jī)三維部署； 內(nèi)容緩存； 用戶關(guān)聯(lián)； 凸優(yōu)化

中圖分類(lèi)號(hào)：TP393.0文獻(xiàn)標(biāo)志碼： A文章編號(hào)：1001－3695（2024）04－027－1143－07

doi：10.19734/j.issn.1001－3695.2023.08.0361

UAV 3D deployment and content caching optimization for mobile edge computing

Tang Huanbo1a，1b，2， Chen Xing1a，1b，2， Zhang Jianshan1b，3

Abstract： With the explosive growth of mobile data traffic in wireless networks， cache－enabled unmanned aerial vehicles（UAVs） are being used in mobile computing to serve as edge servers to provide on－demand services to users in the network. To bring better quality of experience to users while satisfying other resource constraints，it jointly optimized UAVs deployment， cache placement and user association to minimize content access latency for all users and provided users with content caching services of varying quality. This paper proposed a joint optimization algorithm based on alternating optimization for the scenario where multiple UAVs and ground base stations collaborate to provide caching services. The algorithm achieved a sub－optimal solution with a convergence guarantee by iteratively solving the three sub－problems obtained from the decomposition of the objective problem. Firstly， a successive convex approximation－based algorithm solved the UAV deployment sub－problem. Secondly，it used a greedy－based algorithm to solve the content caching sub－problem. Then it used a successive convex approximation algorithm based on the penalty function to solve the user access sub－problem. Finally， it repeated the above procedure to obtain a sub－optimal solution to the target problem. Several simulation experiments verified the effectiveness and feasibility of the proposed algorithm. The simulation results show that the proposed joint optimization algorithm performs better regarding average content access latency and cache hit ratio than the benchmark algorithm.

Key words：mobile edge computing; UAV 3D deployment; content caching; user access; convex optimization

0 引言

近年來(lái)， 隨著5G的普及以及各種功能紛繁多樣的應(yīng)用程序的發(fā)展，無(wú)線網(wǎng)絡(luò)中的移動(dòng)數(shù)據(jù)流量呈爆炸式增長(zhǎng)。根據(jù)2022年愛(ài)立信移動(dòng)市場(chǎng)報(bào)告，全球移動(dòng)數(shù)據(jù)流量在2021年第四季度至2022年第四季度期間增長(zhǎng)了40%，達(dá)到了每月118 EB［1］。面對(duì)移動(dòng)數(shù)據(jù)流量如此快的增長(zhǎng)速度，如何盡可能地提高用戶體驗(yàn)質(zhì)量，成為了目前的一大挑戰(zhàn)。

在當(dāng)前網(wǎng)絡(luò)環(huán)境中，移動(dòng)數(shù)據(jù)流量快速增長(zhǎng)的主要原因之一是用戶對(duì)一些熱門(mén)內(nèi)容的重復(fù)下載。針對(duì)上述問(wèn)題，可以通過(guò)在無(wú)線網(wǎng)絡(luò)中引入邊緣緩存技術(shù)，將熱門(mén)內(nèi)容文件緩存在地面邊緣節(jié)點(diǎn)上供用戶使用，以緩解核心網(wǎng)絡(luò)的流量負(fù)荷。然而，由于地面邊緣節(jié)點(diǎn)的部署成本過(guò)于高昂且覆蓋范圍通常是有限的，在一些用戶密度高的熱點(diǎn)通信區(qū)域中還會(huì)出現(xiàn)無(wú)法及時(shí) 為用戶設(shè)備提供通信服務(wù)等情況，所以地面邊緣節(jié)點(diǎn)已無(wú)法滿足特定場(chǎng)景中對(duì)于邊緣緩存的需求。由于無(wú)人機(jī)具有成本低、部署靈活和移動(dòng)性高等特性，用其取代傳統(tǒng)地面邊緣節(jié)點(diǎn)成為在特定場(chǎng)景進(jìn)行邊緣緩存的一種可行方案，將無(wú)人機(jī)作為邊緣節(jié)點(diǎn)，能夠有效解決部署成本高和覆蓋范圍有限等問(wèn)題［2］。當(dāng)?shù)孛孢吘壒?jié)點(diǎn)的覆蓋范圍、通信資源等不能滿足用戶通信需求時(shí)，就可以在傳統(tǒng)的蜂窩網(wǎng)絡(luò)中使用支持緩存的無(wú)人機(jī)進(jìn)行輔助通信［3］，從而達(dá)到業(yè)務(wù)分流的目的。具體而言，可以將無(wú)人機(jī)部署在通信高峰區(qū)域（如舉辦大型賽事的體育館等）中作為空中基站，為地面用戶提供緩存服務(wù)，從而達(dá)到緩解通信高峰時(shí)段頻繁數(shù)據(jù)傳輸導(dǎo)致的流量擁塞問(wèn)題并提高用戶體驗(yàn)質(zhì)量的目的［4］。此外，由于無(wú)人機(jī)可以懸停在空中，可以在無(wú)人機(jī)與地面用戶之間建立視距鏈路（line－of－sight，LoS），從而實(shí)現(xiàn)更好的傳輸性能［5，6］。

近年來(lái)，無(wú)人機(jī)部署、內(nèi)容緩存以及用戶關(guān)聯(lián)等優(yōu)化問(wèn)題受到了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注，有許多工作針對(duì)單無(wú)人機(jī)或多無(wú)人機(jī)場(chǎng)景的相關(guān)問(wèn)題展開(kāi)了研究。Yang等人［7］針對(duì)5G網(wǎng)絡(luò)中由于瞬間產(chǎn)生的大量流量而造成擁塞的現(xiàn)象進(jìn)行了研究，并提出了一種主動(dòng)式的無(wú)人機(jī)部署框架。為了衡量系統(tǒng)的感知能力，Zhou等人［8］將探測(cè)概率作為指標(biāo)，旨在通過(guò)聯(lián)合優(yōu)化無(wú)人機(jī)的部署和定向天線方向，使目標(biāo)檢測(cè)概率的總和最大化。Bertizzolo等人［9］提出了一種用于Open－RAN架構(gòu)的低復(fù)雜度閉環(huán)控制系統(tǒng)，該系統(tǒng)聯(lián)合優(yōu)化了無(wú)人機(jī)在空間中的位置及其傳輸方向，以支持視頻流，并最大限度地減少其對(duì)網(wǎng)絡(luò)上行干擾的影響。Wang等人［10］以無(wú)人機(jī)和用戶設(shè)備的發(fā)射功率最小化為目的，研究了無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)中的上行傳輸，并設(shè)計(jì)了一套基于集中式多代理Q－learning算法的無(wú)人機(jī)部署和用戶關(guān)聯(lián)方案。Fan等人［11］設(shè)計(jì)了一種啟發(fā)式無(wú)人機(jī)調(diào)度算法，并提出了一種用戶關(guān)聯(lián)算法，用于迭代地將用戶分配到最優(yōu)基站。Zhong等人［12］研究了將無(wú)人機(jī)作為通信中繼的最優(yōu)部署布局，以最大限度地提高中繼網(wǎng)絡(luò)的容量。目前也有部分工作以提高網(wǎng)絡(luò)性能為目的，針對(duì)無(wú)人機(jī)部署和緩存放置的聯(lián)合問(wèn)題進(jìn)行了研究。Luo等人［13］在支持緩存的無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)模型中研究了內(nèi)容文件流行率未知情況下的無(wú)人機(jī)部署和內(nèi)容緩存的聯(lián)合優(yōu)化問(wèn)題，并以降低內(nèi)容訪問(wèn)時(shí)延為目的，設(shè)計(jì)了一種基于用戶的加權(quán)K－means無(wú)人機(jī)部署優(yōu)化算法，以及使用Q－leaning算法直接學(xué)習(xí)緩存策略的緩存放置優(yōu)化算法。文獻(xiàn)［14］以提升邊緣節(jié)點(diǎn)高速緩存的平均緩存命中率為目的，針對(duì)區(qū)域性無(wú)線網(wǎng)絡(luò)模型中的無(wú)人機(jī)調(diào)度和內(nèi)容緩存策略的聯(lián)合優(yōu)化問(wèn)題提出了一種DC－DRL策略。上述文獻(xiàn)均未考慮對(duì)無(wú)人機(jī)的用戶關(guān)聯(lián)問(wèn)題進(jìn)行優(yōu)化，事實(shí)上，無(wú)人機(jī)部署和緩存放置的網(wǎng)絡(luò)性能受到用戶關(guān)聯(lián)的影響，因此用戶關(guān)聯(lián)也是影響網(wǎng)絡(luò)中給定信道帶寬和發(fā)射功率分配的用戶QoE的一個(gè)重要因素。有部分工作在上述問(wèn)題的基礎(chǔ)上增加了對(duì)用戶關(guān)聯(lián)的研究。Zhang等人［4］研究了在支持高速緩存的多無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)模型中如何提升用戶體驗(yàn)質(zhì)量，提出了一種基于一對(duì)一交換匹配的無(wú)人機(jī)部署算法，并設(shè)計(jì)了一種近似最優(yōu)的緩存策略優(yōu)化算法和用戶關(guān)聯(lián)優(yōu)化算法，通過(guò)提高用戶的平均意見(jiàn)得分來(lái)提高用戶的體驗(yàn)質(zhì)量，但該方法的無(wú)人機(jī)部署范圍會(huì)受到候選點(diǎn)的限制，無(wú)法在空間內(nèi)獲得近似最優(yōu)的無(wú)人機(jī)部署位置。Zeng等人［15］以最小化用戶視頻訪問(wèn)時(shí)延為目標(biāo)，研究了在支持高速緩存的多無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)模型中的一個(gè)分層緩存放置和無(wú)人機(jī)部署，以及用戶關(guān)聯(lián)的聯(lián)合優(yōu)化問(wèn)題，并提出了一種基于凸優(yōu)化的方法，該方法僅能在二維空間內(nèi)獲得無(wú)人機(jī)的最佳二維候選位置。Zeng等人［16］在文獻(xiàn)［15］的基礎(chǔ)上進(jìn)一步研究了使用混合視距鏈路和非視距鏈路（non－line－of－sight，NLoS）的支持高速緩存的多無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)模型，并以最小化用戶視頻訪問(wèn)時(shí)延為目標(biāo)，設(shè)計(jì)了一種DC－LP－SCA的交替迭代算法，該模型雖然針對(duì)無(wú)人機(jī)的高度進(jìn)行了優(yōu)化，但考慮的是盡可能地減小NLoS中由于無(wú)人機(jī)高度帶來(lái)的路徑損耗，并沒(méi)有考慮到用戶之間也存在高度差。此外，上述兩個(gè)文獻(xiàn)都可能出現(xiàn)用時(shí)過(guò)長(zhǎng)的情況。

對(duì)于無(wú)人機(jī)部署優(yōu)化問(wèn)題，大多數(shù)現(xiàn)有工作都沒(méi)有考慮到用戶的高度問(wèn)題。然而在實(shí)際應(yīng)用場(chǎng)景中，大多數(shù)用戶都具有不同的高度（如體育館看臺(tái)以及周邊建筑高樓等），并且用戶的高度對(duì)于其與無(wú)人機(jī)直線的無(wú)線信道質(zhì)量的影響不可忽視。因此無(wú)人機(jī)依據(jù)用戶的三維位置進(jìn)行部署，可以進(jìn)一步提高資源使用效率。在緩存放置優(yōu)化問(wèn)題方面，如果用戶請(qǐng)求的內(nèi)容沒(méi)有被緩存在與其相關(guān)聯(lián)的無(wú)人機(jī)上，那么該無(wú)人機(jī)就需要通過(guò)回程鏈路與地面基站進(jìn)行連接，再通過(guò)回程鏈路從原始內(nèi)容服務(wù)器處獲取所需的內(nèi)容文件。顯然，這會(huì)導(dǎo)致用戶的內(nèi)容訪問(wèn)時(shí)延增加。因此，如何快速獲取接近最優(yōu)的緩存放置策略，對(duì)于用戶的內(nèi)容訪問(wèn)時(shí)延至關(guān)重要。此外，由于用戶關(guān)聯(lián)會(huì)對(duì)無(wú)人機(jī)部署位置優(yōu)化和緩存放置優(yōu)化造成影響，所以對(duì)于用戶關(guān)聯(lián)的優(yōu)化勢(shì)在必行?，F(xiàn)有大多數(shù)工作都未考慮到無(wú)人機(jī)并發(fā)能力是有限的，為了避免單一無(wú)人機(jī)同時(shí)響應(yīng)過(guò)多的用戶請(qǐng)求而造成網(wǎng)絡(luò)擁塞，且其他無(wú)人機(jī)由于請(qǐng)求過(guò)少而長(zhǎng)時(shí)間處于空閑狀態(tài)的問(wèn)題，需要對(duì)無(wú)人機(jī)所能關(guān)聯(lián)的用戶數(shù)量進(jìn)行約束。

基于上述考慮，本文在文獻(xiàn)［17］的基礎(chǔ)上以最小化系統(tǒng)中所有用戶的內(nèi)容訪問(wèn)時(shí)延為目的，研究了一個(gè)在支持高速緩存的多無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)應(yīng)用場(chǎng)景中的無(wú)人機(jī)部署、緩存放置和用戶關(guān)聯(lián)的聯(lián)合優(yōu)化問(wèn)題，并進(jìn)一步提出了一種高效算法，用于解決目標(biāo)問(wèn)題。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

1.2 緩存模型

進(jìn)一步地，假設(shè)每個(gè)用戶請(qǐng)求每種內(nèi)容文件的頻率（即該內(nèi)容文件的流行度）遵循Zipf分布，并假設(shè)內(nèi)容文件的流行度分布在所考慮的時(shí)隙內(nèi)保持不變。假設(shè)用戶對(duì)原始內(nèi)容庫(kù)中不同的內(nèi)容文件都具有不同的請(qǐng)求可能性，且這一可能性取決于每種內(nèi)容文件的流行度。在此基礎(chǔ)上，進(jìn)一步假設(shè)所有用戶都會(huì)依據(jù)請(qǐng)求可能性在一定時(shí)間內(nèi)請(qǐng)求內(nèi)容文件，且在這段時(shí)間內(nèi)所請(qǐng)求的內(nèi)容文件種類(lèi)保持不變。當(dāng)用戶向與其關(guān)聯(lián)的無(wú)人機(jī)發(fā)送請(qǐng)求時(shí)，無(wú)人機(jī)會(huì)首先判斷該內(nèi)容文件是否已經(jīng)緩存在無(wú)人機(jī)上。若當(dāng)前內(nèi)容文件已緩存，則會(huì)通過(guò)下行鏈路直接分發(fā)給用戶，否則會(huì)通過(guò)回程鏈路與基站進(jìn)行通信，并從原始內(nèi)容服務(wù)器上獲取相應(yīng)的內(nèi)容文件，再分發(fā)給與其相關(guān)聯(lián)的用戶。每一份內(nèi)容文件都可以被緩存在不同的無(wú)人機(jī)上，但每一份內(nèi)容文件在同一臺(tái)無(wú)人機(jī)上僅能被緩存一次。此外，每架無(wú)人機(jī)所緩存內(nèi)容文件也會(huì)定期更新。

其中：RM表示無(wú)人機(jī)的傳輸功率;σ2表示通信鏈路中的高斯白噪聲功率。由于無(wú)人機(jī)的服務(wù)范圍有限且主要服務(wù)于體育場(chǎng)及周邊地區(qū)，遮擋較少，故為了便于計(jì)算，考慮忽略建筑遮擋對(duì)于無(wú)人機(jī)傳輸速率的影響。

1.4 問(wèn)題定義

本文主要研究了一個(gè)在支持緩存的多無(wú)人機(jī)輔助蜂窩網(wǎng)絡(luò)中以最小化所有用戶的內(nèi)容文件訪問(wèn)時(shí)延為目標(biāo)的優(yōu)化問(wèn)題，該問(wèn)題旨在聯(lián)合優(yōu)化無(wú)人機(jī)部署、緩存放置和用戶關(guān)聯(lián)，可具體表述為

2 最小內(nèi)容訪問(wèn)時(shí)延算法

目標(biāo)優(yōu)化問(wèn)題設(shè)計(jì)無(wú)人機(jī)部署、緩存放置和用戶關(guān)聯(lián)的聯(lián)合優(yōu)化，是一個(gè)NP難問(wèn)題，故無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解。該優(yōu)化問(wèn)題中的變量均為0－1離散變量。如果使用蠻力搜索算法，算法的復(fù)雜度將是不可接受的。為了有效地解決目標(biāo)問(wèn)題，將其分解為三個(gè)子問(wèn)題，并提出了相應(yīng)的解決方法，具體包括：用于解決無(wú)人機(jī)部署子問(wèn)題的基于連續(xù)凸近似的無(wú)人機(jī)部署優(yōu)化算法;用于解決緩存放置子問(wèn)題的基于貪心的緩存放置優(yōu)化算法;用于解決用戶關(guān)聯(lián)子問(wèn)題的基于罰函數(shù)的逐次凸逼近用戶關(guān)聯(lián)優(yōu)化算法。

2.1 基于連續(xù)凸近似的無(wú)人機(jī)部署優(yōu)化算法

為了優(yōu)化多個(gè)無(wú)人機(jī)的部署位置，通?？梢钥紤]對(duì)無(wú)人機(jī)部署子問(wèn)題應(yīng)用凸優(yōu)化算法。目標(biāo)優(yōu)化問(wèn)題的無(wú)人機(jī)部署子問(wèn)題可以表述為

由于所有凸函數(shù)在任意點(diǎn)上的一階泰勒展開(kāi)式都具有全局下界［19］，所以可以采用連續(xù)凸近似算法來(lái)對(duì)該非凸問(wèn)題進(jìn)行優(yōu)化處理，即在每次迭代中，可以使用該非凸函數(shù)的凹下界在給定的局部點(diǎn)處進(jìn)行替代。定義了luav，im作為第i次迭代中獲得的無(wú)人機(jī)位置，則在給定的局部點(diǎn)處可以得到用于替代的下界表示如下：

在經(jīng)過(guò)上述處理之后，在每一次迭代中都可以將Ωi，lbm，n替代Ωm，n，使得原非凸函數(shù)轉(zhuǎn)變?yōu)橐粋€(gè)相對(duì)于luavm的凸函數(shù)。從而，原問(wèn)題也轉(zhuǎn)變?yōu)橐粋€(gè)凸問(wèn)題，故可采用專(zhuān)門(mén)求解凸優(yōu)化問(wèn)題的CVX工具包對(duì)其進(jìn)行直接求解。具體算法步驟如下所示。

其中：式（10d）表示緩存決策cm，f是一個(gè)0－1變量;式（10g）表示每臺(tái)無(wú)人機(jī)緩存容量具有上限。

貪心算法的核心思想是在解決問(wèn)題時(shí)盡可能地作出在當(dāng)前看來(lái)最好的選擇。因此，貪心算法一般用于求解局部最優(yōu)問(wèn)題，且效果也會(huì)相對(duì)不錯(cuò)。在緩存放置子問(wèn)題中，如何求解每臺(tái)無(wú)人機(jī)的最優(yōu)緩存策略正好是一個(gè)局部最優(yōu)問(wèn)題，所以采用了貪心算法進(jìn)行求解，既是否將一個(gè)內(nèi)容文件緩存在無(wú)人機(jī)上，主要取決于該內(nèi)容文件可以帶來(lái)的增益大小。

2.3 基于罰函數(shù)的連續(xù)凸近似用戶關(guān)聯(lián)優(yōu)化算法

在優(yōu)化了無(wú)人機(jī)部署和緩存放置這兩個(gè)子問(wèn)題之后，還需要對(duì)用戶關(guān)聯(lián)問(wèn)題進(jìn)行優(yōu)化。由于無(wú)人機(jī)的關(guān)聯(lián)數(shù)量具有上限，且每個(gè)用戶只能關(guān)聯(lián)一臺(tái)無(wú)人機(jī)，所以無(wú)人機(jī)的關(guān)聯(lián)策略將會(huì)對(duì)整個(gè)優(yōu)化問(wèn)題有著十分重要的影響?？蓪⒂脩絷P(guān)聯(lián)子問(wèn)題表述如下：

其中：式（10e）表示關(guān)聯(lián)決策am，n是一個(gè)0－1變量;式（10f）表示每個(gè)用戶都只能關(guān)聯(lián)一臺(tái)無(wú)人機(jī);式（10h）表示每臺(tái)無(wú)人機(jī)可關(guān)聯(lián)用戶數(shù)量具有上限。

由于約束條件中具有0－1變量，所以該問(wèn)題實(shí)質(zhì)上是一個(gè)非凸問(wèn)題，難以直接求解?？梢圆捎梦墨I(xiàn)［20］對(duì)其進(jìn)行連續(xù)凸逼近處理，將原問(wèn)題轉(zhuǎn)變?yōu)榱艘粋€(gè)近似凸問(wèn)題，從而可以使用凸優(yōu)化的方法來(lái)進(jìn)行直接求解。

首先對(duì)含有0－1變量的式（10e）進(jìn)行處理，將其等價(jià)轉(zhuǎn)換為以下兩個(gè)約束式：

顯然，式（18）是一個(gè)凸約束，但由于式（19）含有凸變量a2m，n，該約束依然是一個(gè)非凸約束，需要對(duì)其進(jìn)行進(jìn)一步凸近似處理?？紤]到凸函數(shù)的一階泰勒展開(kāi)式是有下界的，故使用一階泰勒近似法來(lái)處理該非凸約束。首先，假設(shè)該非凸約束給定的可行點(diǎn)為 m，n，則可以通過(guò)在該可行點(diǎn)處應(yīng)用一階泰勒近似法，將a2m，n替換為 2m，n從而將非凸約束轉(zhuǎn)換為凸約束。然而，由于式（18）（19）是聯(lián)合存在的［21］，如果直接進(jìn)行替換，該問(wèn)題將有可能在迭代中出現(xiàn)不可行的情況。為了避免這一缺陷，可以參考文獻(xiàn)［21，22］，通過(guò)在目標(biāo)函數(shù)中引入一個(gè)懲罰函數(shù)θ來(lái)對(duì)式（19）進(jìn)行松弛，則可得

該子問(wèn)題經(jīng)過(guò)基于罰函數(shù)的逐次凸逼近處理之后，已經(jīng)從難以直接求解的非凸問(wèn)題轉(zhuǎn)換成了便于求解的凸問(wèn)題，采用CVX工具包可以對(duì)其進(jìn)行直接求解。具體優(yōu)化算法表述如下：

算法3 基于罰函數(shù)的連續(xù)凸近似用戶關(guān)聯(lián)優(yōu)化算法

輸入：用戶位置集合；無(wú)人機(jī)部署位置集合；緩存放置矩陣。

輸出：用戶關(guān)聯(lián)矩陣。

初始化解集矩陣 a ←，罰因子φ=1，迭代步長(zhǎng)δ=0.01;

repeat

使用CVX工具包求解式（23），得到解集矩陣 a ;

if用戶關(guān)聯(lián)矩陣元素不收斂 then

φ=δφ;

end if

until直到用戶關(guān)聯(lián)矩陣元素收斂

a←a ;

2.4 內(nèi)容訪問(wèn)時(shí)延優(yōu)化算法

由于聯(lián)合優(yōu)化問(wèn)題可以分解為三個(gè)子問(wèn)題進(jìn)行求解，故在上述算法的基礎(chǔ)上，可以對(duì)內(nèi)容訪問(wèn)時(shí)延進(jìn)行優(yōu)化，算法4描述了所提內(nèi)容訪問(wèn)時(shí)延優(yōu)化算法。

算法4 內(nèi)容訪問(wèn)時(shí)延優(yōu)化算法

輸入：用戶位置集合，用戶請(qǐng)求矩陣。

輸出：內(nèi)容訪問(wèn)時(shí)延。

初始化無(wú)人機(jī)部署位置集合 l 、緩存放置矩陣 c 、用戶關(guān)聯(lián)矩陣 a ;

repeat

通過(guò)算法1更新無(wú)人機(jī)部署位置集合 l ;

通過(guò)算法2更新緩存放置矩陣 c ;

通過(guò)算法3更新用戶關(guān)聯(lián)矩陣 a ;

通過(guò)式（10）計(jì)算得到的內(nèi)容訪問(wèn)時(shí)延;

until內(nèi)容訪問(wèn)時(shí)延矩陣元素均收斂至ε

算法4主要基于塊坐標(biāo)下降技術(shù)，在每次迭代中都可以使得目標(biāo)值下降，并且在幾次迭代之后收斂。此外，在每次迭代過(guò)程中，先求解無(wú)人機(jī)部署凸優(yōu)化子問(wèn)題，接著將解集代入緩存放置子問(wèn)題，通過(guò)貪心算法進(jìn)行優(yōu)化，并將優(yōu)化結(jié)果代入用戶關(guān)聯(lián)凸優(yōu)化子問(wèn)題進(jìn)行求解。算法4的時(shí)間復(fù)雜度可以表示為O（MNFlog（1/ε）），其中ε表示收斂閾值。

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

3.1 參數(shù)設(shè)置

在一個(gè)800×800 m2的實(shí)驗(yàn)區(qū)域內(nèi)，隨機(jī)分布N=100個(gè)用戶。地面宏基站部署在實(shí)驗(yàn)區(qū)域外，其三維坐標(biāo)設(shè)置為{1 000，1 000，0}。此外，共有M臺(tái)支持高速緩存的無(wú)人機(jī)部署在熱點(diǎn)區(qū)域內(nèi)以進(jìn)行輔助通信，其高度設(shè)置為［20，80］，內(nèi)容文件共有F個(gè)，所有內(nèi)容文件的流行度均服從Zipf分布，并按流行度的高低進(jìn)行降序排序，用戶依據(jù)內(nèi)容文件流行度請(qǐng)求r個(gè)內(nèi)容文件。無(wú)人機(jī)或用戶等相關(guān)的其他參數(shù)設(shè)置參考自3GPP［23］，其余參數(shù)的詳細(xì)設(shè)置由表1給出。

3.2 對(duì)比算法及性能評(píng)估指標(biāo)設(shè)置

出于比較的目的，選取了四種基準(zhǔn)算法，通過(guò)對(duì)這些算法進(jìn)行了一定的處理，使其適應(yīng)系統(tǒng)模型并作為對(duì)比算法來(lái)驗(yàn)證所提算法的有效性：a） K－means聚類(lèi)算法+凸優(yōu)化算法，該方法（下文簡(jiǎn)稱為KM－C算法）參考自文獻(xiàn)［17］，其中無(wú)人機(jī)部署問(wèn)題和用戶關(guān)聯(lián)問(wèn)題采用K－means聚類(lèi)的方式進(jìn)行優(yōu)化處理，緩存放置問(wèn)題則采用凸優(yōu)化的方法進(jìn)行放置；b）PSO－GAG雙層迭代嵌套優(yōu)化，該方法（下文簡(jiǎn)稱為PG－G算法）參考自文獻(xiàn)［24］，主要采用PSO－GA算法作為上層，針對(duì)無(wú)人機(jī)部署問(wèn)題進(jìn)行優(yōu)化，下層采用貪心算法對(duì)緩存放置策略及用戶關(guān)聯(lián)策略進(jìn)行優(yōu)化，在PG－G算法中，采用重復(fù)迭代1 000次后的結(jié)果作為該算法的最終結(jié)果；c）經(jīng)典算法，該算法參考自文獻(xiàn)［4］，其中無(wú)人機(jī)部署位置采用在區(qū)域內(nèi)均勻部署的方式，緩存放置策略采用最大流行度放置策略，用戶關(guān)聯(lián)策略采用最大C/I調(diào)度算法；d）隨機(jī)算法，該算法是指將無(wú)人機(jī)部署位置、緩存放置策略和用戶關(guān)聯(lián)策略均采用隨機(jī)的方式進(jìn)行處理。

主要性能評(píng)估指標(biāo)選用系統(tǒng)中所有用戶的平均內(nèi)容訪問(wèn)時(shí)延，具體計(jì)算公式如下：

3.3 實(shí)驗(yàn)評(píng)估

本文首先驗(yàn)證了算法在小規(guī)模場(chǎng)景中的收斂情況和有效性。在該場(chǎng)景中，用戶數(shù)量設(shè)置為N=50，無(wú)人機(jī)數(shù)量設(shè)置為M=4，每臺(tái)無(wú)人機(jī)的緩存容量上限設(shè)置為K=100 Mbps，內(nèi)容文件數(shù)量設(shè)置為F=100，最大可關(guān)聯(lián)用戶數(shù)量設(shè)置為Nmax=30，用戶的偏好程度設(shè)置為γ=0.6，用戶請(qǐng)求數(shù)量設(shè)置 為1個(gè)。由于算法中三個(gè)子問(wèn)題的初始矩陣設(shè)置可能會(huì)對(duì)三個(gè)子問(wèn)題的近似最優(yōu)解造成影響。所以，為了盡可能地減少這種影響，首先使用隨機(jī)算法直接生成100種矩陣集合，接著通過(guò)計(jì)算得到每個(gè)矩陣集合對(duì)應(yīng)的用戶平均內(nèi)容訪問(wèn)時(shí)延，最后使用用戶平均內(nèi)容訪問(wèn)時(shí)延最小的矩陣集合作為三個(gè)問(wèn)題的初始矩陣。本文算法在10次迭代中的收斂情況如圖2所示。

從圖2可以看到，本文算法在經(jīng)過(guò)四次迭代之后就已經(jīng)收斂。為了更直觀地驗(yàn)證本文算法在該場(chǎng)景中的有效性，增加了算法執(zhí)行時(shí)間和參考文獻(xiàn)［25］的緩存命中率和作為性能指標(biāo)，并在四種基準(zhǔn)算法的基礎(chǔ)上進(jìn)一步增加了兩種算法進(jìn)行對(duì)比驗(yàn)證，具體實(shí)驗(yàn)結(jié)果如圖3和表2所示。

其中凸優(yōu)化算法參考自文獻(xiàn)［15］，該算法使用凸優(yōu)化的方法對(duì)三個(gè)子問(wèn)題進(jìn)行了迭代優(yōu)化;KM－G算法是基于KM－C算法進(jìn)行的改寫(xiě)，該算法的無(wú)人機(jī)部署和用戶關(guān)聯(lián)策略采用K－means算法進(jìn)行聚類(lèi)，緩存放置算法則采用本文貪心算法。從圖3和表2中可以觀察到，本文算法在執(zhí)行時(shí)間上明顯優(yōu)于凸優(yōu)化算法，且在效果上也優(yōu)于其他五種算法，并取得了接近最優(yōu)的結(jié)果。此外還可以觀察到，本文算法的無(wú)人機(jī)部署算法和用戶關(guān)聯(lián)算法上明顯優(yōu)于PSO－GA算法、K－means聚類(lèi)算法和經(jīng)典算法，而緩存放置算法的優(yōu)化效果雖然和凸優(yōu)化算法幾乎相同，但在執(zhí)行時(shí)間上明顯優(yōu)于凸優(yōu)化算法。

為了進(jìn)一步驗(yàn)證本文算法的有效性和整體優(yōu)化效果，本文還設(shè)置了其他幾種實(shí)驗(yàn)場(chǎng)景。在圖4中，用戶數(shù)量設(shè)置為N=100，內(nèi)容文件數(shù)量設(shè)置為F=200，無(wú)人機(jī)數(shù)量分別設(shè)置為2、4、6，對(duì)應(yīng)的最大可關(guān)聯(lián)用戶數(shù)量分別設(shè)置為60、30、20，其余參數(shù)不變，實(shí)驗(yàn)情況如圖4所示。

顯然，所有算法得到的用戶平均內(nèi)容訪問(wèn)時(shí)延都隨著無(wú)人機(jī)數(shù)量的增加而減少，這是因?yàn)殡S著無(wú)人機(jī)密度的增大，用戶與無(wú)人機(jī)之間的距離會(huì)變得更近，從而使得用戶獲取內(nèi)容文件的時(shí)延變短。在無(wú)人機(jī)數(shù)量增加到6時(shí)，本文算法的用戶平均內(nèi)容訪問(wèn)時(shí)延已趨近于最優(yōu)，且在不同數(shù)量的無(wú)人機(jī)中，該算法均優(yōu)于所有基準(zhǔn)算法。

圖5、6在無(wú)人機(jī)數(shù)量設(shè)置為M=4，最大可關(guān)聯(lián)用戶數(shù)量設(shè)置為Nmax=30，其余參數(shù)不變的情況下，分別比較了在不同緩存容量和不同請(qǐng)求數(shù)量下的用戶平均內(nèi)容訪問(wèn)時(shí)延。

如圖5所示，平均內(nèi)容訪問(wèn)時(shí)延會(huì)隨著無(wú)人機(jī)緩存容量的增加而減小。這是因?yàn)闊o(wú)人機(jī)緩存容量增加，無(wú)人機(jī)可以直接滿足更多用戶發(fā)送的內(nèi)容請(qǐng)求。如圖6所示，由于每個(gè)用戶所請(qǐng)求的內(nèi)容文件數(shù)量逐漸增加而無(wú)人機(jī)緩存容量不變，這會(huì)使得用戶越來(lái)越難以在無(wú)人機(jī)上獲取所需的所有內(nèi)容文件，從而導(dǎo)致無(wú)人機(jī)頻繁地訪問(wèn)原始內(nèi)容服務(wù)器，使得用戶的平均內(nèi)容訪問(wèn)時(shí)延逐漸增加。因此，良好的緩存策略在該場(chǎng)景中可以避免更多由于頻繁地訪問(wèn)原始內(nèi)容服務(wù)器而產(chǎn)生的不必要的時(shí)間。從圖5可以看出，本文算法的優(yōu)化效果相比其他算法也更具優(yōu)勢(shì)，并且隨著用戶請(qǐng)求數(shù)量的增加，該算法與其余基準(zhǔn)算法的差距越來(lái)越大，驗(yàn)證了本文算法的有效性。

4 結(jié)束語(yǔ)

本文主要研究了一個(gè)在使用支持高速緩存的無(wú)人機(jī)進(jìn)行輔助通信的蜂窩網(wǎng)絡(luò)應(yīng)用場(chǎng)景中的聯(lián)合無(wú)人機(jī)部署、緩存放置及用戶關(guān)聯(lián)的優(yōu)化問(wèn)題，其優(yōu)化目的是最小化網(wǎng)絡(luò)系統(tǒng)中所有用戶的內(nèi)容訪問(wèn)時(shí)延。為了解決這樣一個(gè)NP難的問(wèn)題，將該問(wèn)題劃分成了無(wú)人機(jī)部署、緩存放置以及用戶關(guān)聯(lián)三個(gè)子問(wèn)題。對(duì)于無(wú)人機(jī)部署問(wèn)題，提出了一種基于連續(xù)凸近似的優(yōu)化算法，該算法聯(lián)合考慮了無(wú)人機(jī)部署范圍和飛行高度。對(duì)于緩存放置問(wèn)題，提出了一種基于貪心的優(yōu)化算法，以盡可能地得到較優(yōu)的緩存策略。此外，還設(shè)計(jì)了一種基于罰函數(shù)的連續(xù)凸近似用戶關(guān)聯(lián)優(yōu)化算法，通過(guò)考慮無(wú)人機(jī)的關(guān)聯(lián)數(shù)量上限，來(lái)獲得比較貼合實(shí)際應(yīng)用場(chǎng)景的用戶關(guān)聯(lián)策略。本文將上述三種算法進(jìn)行聯(lián)合迭代，以達(dá)到最小化用戶總內(nèi)容訪問(wèn)時(shí)延的目的。仿真實(shí)驗(yàn)表明，本文算法可以在較少迭代次數(shù)內(nèi)收斂，通過(guò)分析多個(gè)場(chǎng)景的實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文算法的有效性。與基準(zhǔn)算法相比，本文算法具備更好的系統(tǒng)性能和優(yōu)化效果。在未來(lái)的工作中，本文將考慮在當(dāng)前網(wǎng)絡(luò)場(chǎng)景中引入衛(wèi)星通信，并對(duì)空天地一體化的移動(dòng)邊緣緩存系統(tǒng)進(jìn)行研究，以進(jìn)一步完善本文模型。

參考文獻(xiàn)：

［1］Ericsson. Ericsson mobility report November 2022［EB/OL］. （2022）. ［2023－07－17］. https：//www.ericsson.com/en/reports－and－papers/ mobility－report/reports/november－2022.

［2］Gupta L，Jain R，Vaszkun G. Survey of important issues in UAV communication networks［J］.IEEE Communications Surveys amp; Tuto－rials ，2015， 18 （2）： 1123－1152.

［3］Chen Mingzhe，Saad W，Yin Changchuan. Liquid state machine lear－ning for resource and cache management in LTE－U unmanned aerial vehicle（UAV） networks［J］.IEEE Trans on Wireless Communications ，2019， 18 （3）： 1504－1517.

［4］Zhang Tiankui，Wang Yi，Liu Yuanwei， et al.Cache－enabling UAV communications： network deployment and resource allocation［J］.IEEE Trans on Wireless Communications ，2020， 19 （11）： 7470－7483.

［5］Zhan Cheng，Zeng Yong. Aerial－ground cost tradeoff for multi－UAV－enabled data collection in wireless sensor networks［J］.IEEE Trans on Communications ，2019， 68 （3）： 1937－1950.

［6］Ning Zhaolong，Dong Peiran，Wen Miaowen， et al.5G－enabled UAV－to－community offloading： joint trajectory design and task scheduling［J］.IEEE Journal on Selected Areas in Communications ，202 39 （11）： 3306－3320.

［7］Yang Peng，Cao Xianbin，Yin Chao， et al.Proactive drone－cell deployment： overload relief for a cellular network under flash crowd traffic［J］.IEEE Trans on Intelligent Transportation Systems ，2017， 18 （10）： 2877－2892.

［8］Zhou Lingyun，Pu Wenqiang，You Mingyi， et al.Joint optimization of UAV deployment and directional antenna orientation for multi－UAV cooperative sensing［C］//Proc of IEEE Wireless Communications and Networking Conference. Piscataway，NJ： IEEE Press，2023： 1－5.

［9］Bertizzolo L，Tran T X，Buczek J， et al.Streaming from the air： enabling drone－sourced video streaming applications on 5G open－RAN architectures［J］.IEEE Trans on Mobile Computing ，2023， 22 （5）： 3004－3016.

［10］Wang Leiyu，Zhang Haixia，Guo Shuaishuai， et al.Deployment and association of multiple UAVs in UAV－assisted cellular networks with the knowledge of statistical user position［J］.IEEE Trans on Wireless Communications ，2022， 21 （8）： 6553－6567.

［11］Fan Qiang，Ansari N. Towards traffic load balancing in drone－assisted communications for IoT［J］.IEEE Internet of Things Journal ，2018， 6 （2）： 3633－3640.

［12］Zhong Xijian，Guo Yan，Li Ning， et al.Deployment optimization of UAV relay for malfunctioning base station： model－free approaches［J］.IEEE Trans on Vehicular Technology ，2019， 68 （12）： 11971－11984.

［13］Luo Jingjing，Song Jialun，Zheng Fuchun， et al.User－centric UAV deployment and content placement in cache－enabled multi－UAV networks［J］.IEEE Trans on Vehicular Technology ，2022， 71 （5）： 5656－5660.

［14］紀(jì)洪運(yùn)，沈航，白光偉. 無(wú)人機(jī)基站輔助的內(nèi)容緩存多目標(biāo)優(yōu)化策略［J］. 小型微型計(jì)算機(jī)系統(tǒng)，2023， 44 （5）： 1102－1107. （Ji Hongyun，Shen Hang，Bai Guangwei. Muti－objective optimization strategy of content cache assisted by drone base station［J］.Journal of Chinese Computer Systems ，2023， 44 （5）： 1102－1107.）

［15］Zeng Bin，Zhan Cheng，Yang Yang， et al.Access delay minimization for scalable videos in cache－enabled multi－UAV networks［C］//Proc of IEEE Global Communications Conference. Piscataway，NJ： IEEE Press，2022： 389－394.

［16］Zeng Bin，Zhan Cheng，Xu Changyuan， et al.Caching and 3D deployment strategy for scalable videos in cache－enabled multi－UAV networks［J］.IEEE Trans on Vehicular Technology ，2023， 72 （11）： 14875－14888.

［17］唐煥博，鄭鴻強(qiáng)，沈啟航，等. 基于QoE的無(wú)人機(jī)網(wǎng)絡(luò)部署和緩存策略優(yōu)化方法［J］. 計(jì)算機(jī)應(yīng)用研究，2023， 40 （5）： 1473－1479. （Tang Huanbo，Zheng Hongqiang，Shen Qihang， et al.QoE－based optimization method for UAV network deployment and cache strategy［J］.Application Research of Computers ，2023， 40 （5）： 1473－1479.）

［18］Guo Hongzhi，Liu Jiajia. UAV－enhanced intelligent offloading for Internet of Things at the edge［J］.IEEE Trans on Industrial Informatics ，2019， 16 （4）： 2737－2746.

［19］Boyd S P，Vandenberghe L. Convex optimization［M］. Cambridge： Cambridge University Press，2004.

［20］Lu Jinhui，Wang Yuntian，Liu Tingting， et al.UAV－enabled uplink non－orthogonal multiple access system：joint deployment and power control［J］.IEEE Trans on Vehicular Technology ，2020， 69 （9）： 10090－10102.

［21］Vu Q D，Nguyen K G，Juntti M. Max－min fairness for multicast multigroup multicell transmission under backhaul constraints［C］//Proc of IEEE Global Communications Conference. Piscataway，NJ： IEEE Press，2016： 1－6.

［22］Nguyen T M，Ajib W，Assi C. A novel cooperative NOMA for designing UAV－assisted wireless backhaul networks［J］.IEEE Journal on Selected Areas in Communications ，2018， 36 （11）： 2497－2507.

［23］3GPP. RP－171050， Study on enhanced LTE support for aerial vehicles［S］. Dubrovnik，HR： 3GPP Press，2017： 33－46.

［24］劉漳輝，鄭鴻強(qiáng)，張建山，等. 多無(wú)人機(jī)使能移動(dòng)邊緣計(jì)算系統(tǒng)中的計(jì)算卸載與部署優(yōu)化［J］. 計(jì)算機(jī)科學(xué)，2022， 49 （6A）： 619－627. （Liu Zhanghui，Zheng Hongqiang，Zhang Jianshan， et al.Computation offloading and deployment optimization in multi－UAV－enabled mobile edge computing systems［J］.Computer Science ，2022， 49 （6A）： 619－627.）

［25］Atiqur R，Liton A M，Wu Guangfu. Content caching strategy at small base station in 5G networks with mobile edge computing［J］.International Journal of Science and Business ，2020， 4 （4）：104－112.

收稿日期：2023－08－14；修回日期：2023－10－07基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62072108）；福建省自然科學(xué)基金杰青項(xiàng)目（2020J06014）；中央引導(dǎo)地方科技發(fā)展資金資助項(xiàng)目（2022L3004）；福廈泉國(guó)家自主創(chuàng)新示范區(qū)協(xié)同創(chuàng)新平臺(tái)項(xiàng)目（2022FX5）；福建省科技經(jīng)濟(jì)融合服務(wù)平臺(tái)項(xiàng)目（2023XRH001）

作者簡(jiǎn)介：唐煥博（1998—），男，福建福州人，碩士研究生，CCF會(huì)員，主要研究方向?yàn)檫吘壘彺妗⑼箖?yōu)化；陳星（1985—），男，福建永春人，教授，博導(dǎo)，博士，主要研究方向?yàn)檐浖こ獭?"""" 云計(jì)算和軟件自適應(yīng)；張建山（1995—），男（通信作者），福建莆田人，博士，主要研究方向?yàn)樵?邊緣計(jì)算、智能計(jì)算（jszhang@mju.edu.cn）．