科研動(dòng)態(tài)
緩存輔助無線網(wǎng)絡(luò)中結(jié)合索引編碼的下行PD-NOMA傳輸時(shí)延優(yōu)化
中文題目：緩存輔助無線網(wǎng)絡(luò)中結(jié)合索引編碼的下行PD-NOMA傳輸時(shí)延優(yōu)化
論文題目：Delay Minimization for Downlink PD-NOMA Transmission with Index Coding in Cache-Aided Wireless Networks
錄用期刊/會(huì)議：EAI CollaborateCom 2024 - 20th EAI International Conference on Collaborative Computing: Networking, Applications and Worksharing (CCF C)
作者列表：
1) 吳 凡 中國石油大學(xué)（北京）人工智能學(xué)院 博 21
2) 馬建豪 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) 碩 20
3) 呂振杰 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) 碩 22
4) 徐朝農(nóng) 中國石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)系教師
文章簡介:
PD-NOMA作為一種支持多用戶接入并提升頻譜效率的有效技術(shù)，已引起了廣泛關(guān)注。同時(shí)，無線緩存作為一項(xiàng)新興技術(shù)，能夠顯著減少網(wǎng)絡(luò)流量。我們還受到結(jié)合索引編碼的PD-NOMA技術(shù)的啟發(fā)，旨在進(jìn)一步降低傳輸時(shí)延。因此，本文研究了下行PD-NOMA傳輸中結(jié)合索引編碼的時(shí)延最小化問題。為此，我們將索引編碼與PD-NOMA的分組調(diào)度聯(lián)合建模，提出了相應(yīng)的數(shù)學(xué)模型。由于該問題屬于復(fù)雜的混合整數(shù)規(guī)劃問題，我們?cè)O(shè)計(jì)了一種兩階段的解決策略。在第一階段，我們用無向圖描述用戶的需求與緩存關(guān)系，最少的傳輸數(shù)據(jù)包數(shù)量可以近似等價(jià)于該圖的團(tuán)覆蓋數(shù)。通過貪心算法找到最大團(tuán)覆蓋，對(duì)每個(gè)團(tuán)的需求包進(jìn)行XOR操作，生成索引編碼包。在第二階段，我們采用啟發(fā)式策略對(duì)待傳輸?shù)臄?shù)據(jù)包進(jìn)行調(diào)度，貪心利用PD-NOMA的傳輸能力，從而實(shí)現(xiàn)時(shí)延的最小化。
本文的主要內(nèi)容如下：
（1）我們通過聯(lián)合考慮索引編碼和PD-NOMA的分組問題來構(gòu)建該問題的數(shù)學(xué)模型。
（2）提供了該問題為NP完全問題的證明。
（3）提出了一種基于需求-緩存圖最大團(tuán)覆蓋的兩階段啟發(fā)式算法。
摘要:
功率域非正交多址接入（PD-NOMA）與索引編碼因其支持大規(guī)模移動(dòng)連接和減少網(wǎng)絡(luò)流量的能力，得到了廣泛關(guān)注。本文研究了具有緩存功能的下行PD-NOMA無線網(wǎng)絡(luò)，并探討了如何通過索引編碼來最小化下行傳輸中的PD-NOMA網(wǎng)絡(luò)傳輸時(shí)延。考慮到用戶緩存的內(nèi)容，我們構(gòu)建了一個(gè)聯(lián)合索引編碼與分組調(diào)度的優(yōu)化問題，旨在充分利用PD-NOMA和內(nèi)容緩存的特性來最小化時(shí)延。隨后，我們的原始證明表明，下行PD-NOMA傳輸?shù)臅r(shí)延最小化問題是NP完全的。為此，提出了一個(gè)兩階段的啟發(fā)式算法來解決該問題。在第一階段，構(gòu)建圖來描述用戶的需求與緩存關(guān)系，最少數(shù)據(jù)包的數(shù)量可以通過該圖的團(tuán)覆蓋數(shù)進(jìn)行近似。此外，針對(duì)每個(gè)團(tuán)，通過對(duì)團(tuán)內(nèi)需求包進(jìn)行XOR操作，形成索引編碼包。在第二階段，采用啟發(fā)式策略對(duì)索引編碼包進(jìn)行調(diào)度，貪心地利用PD-NOMA的下行傳輸能力。基于仿真結(jié)果的分析表明，與幾種基線方案相比，所提出的方法在緩存輔助無線網(wǎng)絡(luò)中有效減少了傳輸時(shí)延。
設(shè)計(jì)與實(shí)現(xiàn):
1、問題建模
我們考慮一個(gè)由單基站（BS）和n個(gè)用戶設(shè)備（UE）組成的單跳、單信道無線網(wǎng)絡(luò)，用戶設(shè)備分別為u1, u2, ..., un。基站和用戶設(shè)備均配備單天線。基站可以訪問一個(gè)包含q個(gè)文件的數(shù)據(jù)庫。因而，問題可以建模為
2、算法設(shè)計(jì)
為了解決上面的問題，我們提出了一種兩階段策略，并分別為索引編碼和PD-NOMA中的分組與功率分配問題設(shè)計(jì)了啟發(fā)式策略。
第一階段為基于團(tuán)覆蓋的編碼策略。顯然，編碼包的數(shù)量對(duì)傳輸時(shí)延有很大影響。通常，數(shù)據(jù)包越多，時(shí)延越大，反之亦然。因此，我們首先考慮如何通過索引編碼減少數(shù)據(jù)包的數(shù)量，同時(shí)確保所有文件請(qǐng)求在一個(gè)幀內(nèi)得到滿足。因而算法設(shè)計(jì)如圖1所示。
圖1 基于團(tuán)覆蓋的啟發(fā)式解碼策略
第二階段為PD-NOMA中的分組與功率分配策略。當(dāng)所有編碼包生成后，基站將基于PD-NOMA對(duì)其進(jìn)行調(diào)度并分配傳輸功率。即使在給定待傳輸?shù)臄?shù)據(jù)包的情況下，最小化傳輸時(shí)延仍可能是一個(gè)困難的問題。因此，我們提出了一種啟發(fā)式算法，先對(duì)數(shù)據(jù)包進(jìn)行分組，然后分配傳輸功率。
圖2 用于編碼包分組的貪心算法
實(shí)驗(yàn)結(jié)果及分析:
我們考慮一個(gè)下行PD-NOMA無線網(wǎng)絡(luò)，該網(wǎng)絡(luò)由一個(gè)基站（BS）和若干配備k-SIC接收器和緩存的用戶設(shè)備（UE）組成。這些UE均勻分布在半徑為500米的圓形小區(qū)內(nèi)。每個(gè)UE隨機(jī)請(qǐng)求并緩存一定數(shù)量的文件。假設(shè)所有UE請(qǐng)求的文件都未緩存，并且每個(gè)UE請(qǐng)求的文件數(shù)量服從參數(shù)為λ的泊松分布。相關(guān)實(shí)驗(yàn)結(jié)果如下圖3，圖4。
圖3與baseline1相比，所提出的算法和baseline2分別將幀長度減少了14.19%和12.60%。
圖3 不同γ和k值下的幀長度
圖4 傳輸時(shí)延性能與每個(gè)用戶設(shè)備平均請(qǐng)求文件數(shù)量的關(guān)系（n = 40）
圖4，圖5分析了問題規(guī)模對(duì)系統(tǒng)幀長度的影響。所研究問題的規(guī)模取決于基站服務(wù)的請(qǐng)求文件數(shù)量。與baseline2相比，當(dāng)問題規(guī)模較大時(shí)，所提出的算法表現(xiàn)出更好的性能。
當(dāng)n = 10時(shí)，所提出的算法和baseline1相較于baseline2，分別將幀長度減少了5.03%和4.9%。當(dāng)n = 70時(shí)，這一比例分別上升至17.19%和13.91%。
圖5 傳輸時(shí)延性能與用戶設(shè)備數(shù)量的關(guān)系
結(jié)論:
本文研究了下行PD-NOMA傳輸中結(jié)合索引編碼的傳輸時(shí)延最小化問題。我們通過聯(lián)合考慮索引編碼和PD-NOMA的分組調(diào)度，對(duì)該問題進(jìn)行了建模。此外，為了深入了解問題結(jié)構(gòu)，我們證明了問題的NP完全性。隨后，我們提出了一個(gè)兩階段的啟發(fā)式算法來解決該問題。索引編碼包通過基于最大團(tuán)覆蓋的編碼策略生成，并通過PD-NOMA中的貪心編碼包分組和功率分配進(jìn)行調(diào)度。仿真結(jié)果表明，結(jié)合索引編碼的PD-NOMA方案具有顯著優(yōu)勢(shì)。我們相信，隨著更多低成本大容量存儲(chǔ)設(shè)備的廣泛應(yīng)用，該方案將在未來得到廣泛使用。
作者簡介:
徐朝農(nóng)，中國石油大學(xué)（北京）人工智能學(xué)院教師，主要研究領(lǐng)域?yàn)檫吘壷悄堋⑶度胧较到y(tǒng)、無線網(wǎng)絡(luò)。