中文題目：緩存輔助無線網絡中結合索引編碼的下行PD-NOMA傳輸時延優化

論文題目：Delay Minimization for Downlink PD-NOMA Transmission with Index Coding in Cache-Aided Wireless Networks

錄用期刊/會議：EAI CollaborateCom 2024 - 20th EAI International Conference on Collaborative Computing: Networking, Applications and Worksharing (CCF C)

作者列表：

1) 吳    凡 中國石油大學（北京）人工智能學院 博 21

2) 馬建豪 中國石油大學（北京）人工智能學院 計算機科學與技術專業 碩 20

3) 呂振杰 中國石油大學（北京）人工智能學院 計算機科學與技術專業 碩 22

4) 徐朝農 中國石油大學（北京）人工智能學院 計算機系教師

文章簡介:

PD-NOMA作為一種支持多用戶接入并提升頻譜效率的有效技術，已引起了廣泛關注。同時，無線緩存作為一項新興技術，能夠顯著減少網絡流量。我們還受到結合索引編碼的PD-NOMA技術的啟發，旨在進一步降低傳輸時延。因此，本文研究了下行PD-NOMA傳輸中結合索引編碼的時延最小化問題。為此，我們將索引編碼與PD-NOMA的分組調度聯合建模，提出了相應的數學模型。由于該問題屬于復雜的混合整數規劃問題，我們設計了一種兩階段的解決策略。在第一階段，我們用無向圖描述用戶的需求與緩存關系，最少的傳輸數據包數量可以近似等價于該圖的團覆蓋數。通過貪心算法找到最大團覆蓋，對每個團的需求包進行XOR操作，生成索引編碼包。在第二階段，我們采用啟發式策略對待傳輸的數據包進行調度，貪心利用PD-NOMA的傳輸能力，從而實現時延的最小化。

本文的主要內容如下：

（1）我們通過聯合考慮索引編碼和PD-NOMA的分組問題來構建該問題的數學模型。

（2）提供了該問題為NP完全問題的證明。

（3）提出了一種基于需求-緩存圖最大團覆蓋的兩階段啟發式算法。

摘要:

功率域非正交多址接入（PD-NOMA）與索引編碼因其支持大規模移動連接和減少網絡流量的能力，得到了廣泛關注。本文研究了具有緩存功能的下行PD-NOMA無線網絡，并探討了如何通過索引編碼來最小化下行傳輸中的PD-NOMA網絡傳輸時延?？紤]到用戶緩存的內容，我們構建了一個聯合索引編碼與分組調度的優化問題，旨在充分利用PD-NOMA和內容緩存的特性來最小化時延。隨后，我們的原始證明表明，下行PD-NOMA傳輸的時延最小化問題是NP完全的。為此，提出了一個兩階段的啟發式算法來解決該問題。在第一階段，構建圖來描述用戶的需求與緩存關系，最少數據包的數量可以通過該圖的團覆蓋數進行近似。此外，針對每個團，通過對團內需求包進行XOR操作，形成索引編碼包。在第二階段，采用啟發式策略對索引編碼包進行調度，貪心地利用PD-NOMA的下行傳輸能力?；诜抡娼Y果的分析表明，與幾種基線方案相比，所提出的方法在緩存輔助無線網絡中有效減少了傳輸時延。

設計與實現:

1、問題建模

我們考慮一個由單基站（BS）和n個用戶設備（UE）組成的單跳、單信道無線網絡，用戶設備分別為u1, u2, ..., un?；竞陀脩粼O備均配備單天線?；究梢栽L問一個包含q個文件的數據庫。因而，問題可以建模為

2、算法設計

為了解決上面的問題，我們提出了一種兩階段策略，并分別為索引編碼和PD-NOMA中的分組與功率分配問題設計了啟發式策略。

第一階段為基于團覆蓋的編碼策略。顯然，編碼包的數量對傳輸時延有很大影響。通常，數據包越多，時延越大，反之亦然。因此，我們首先考慮如何通過索引編碼減少數據包的數量，同時確保所有文件請求在一個幀內得到滿足。因而算法設計如圖1所示。

 

圖1 基于團覆蓋的啟發式解碼策略

第二階段為PD-NOMA中的分組與功率分配策略。當所有編碼包生成后，基站將基于PD-NOMA對其進行調度并分配傳輸功率。即使在給定待傳輸的數據包的情況下，最小化傳輸時延仍可能是一個困難的問題。因此，我們提出了一種啟發式算法，先對數據包進行分組，然后分配傳輸功率。

圖2 用于編碼包分組的貪心算法

實驗結果及分析:

我們考慮一個下行PD-NOMA無線網絡，該網絡由一個基站（BS）和若干配備k-SIC接收器和緩存的用戶設備（UE）組成。這些UE均勻分布在半徑為500米的圓形小區內。每個UE隨機請求并緩存一定數量的文件。假設所有UE請求的文件都未緩存，并且每個UE請求的文件數量服從參數為λ的泊松分布。相關實驗結果如下圖3，圖4。

圖3與baseline1相比，所提出的算法和baseline2分別將幀長度減少了14.19%和12.60%。

 

 圖3 不同γ和k值下的幀長度

圖4 傳輸時延性能與每個用戶設備平均請求文件數量的關系（n = 40）

圖4，圖5分析了問題規模對系統幀長度的影響。所研究問題的規模取決于基站服務的請求文件數量。與baseline2相比，當問題規模較大時，所提出的算法表現出更好的性能。

當n = 10時，所提出的算法和baseline1相較于baseline2，分別將幀長度減少了5.03%和4.9%。當n = 70時，這一比例分別上升至17.19%和13.91%。

 

圖5 傳輸時延性能與用戶設備數量的關系

結論:

本文研究了下行PD-NOMA傳輸中結合索引編碼的傳輸時延最小化問題。我們通過聯合考慮索引編碼和PD-NOMA的分組調度，對該問題進行了建模。此外，為了深入了解問題結構，我們證明了問題的NP完全性。隨后，我們提出了一個兩階段的啟發式算法來解決該問題。索引編碼包通過基于最大團覆蓋的編碼策略生成，并通過PD-NOMA中的貪心編碼包分組和功率分配進行調度。仿真結果表明，結合索引編碼的PD-NOMA方案具有顯著優勢。我們相信，隨著更多低成本大容量存儲設備的廣泛應用，該方案將在未來得到廣泛使用。

作者簡介:

徐朝農，中國石油大學（北京）人工智能學院教師，主要研究領域為邊緣智能、嵌入式系統、無線網絡。