# Fair and optimal resource allocation for LTE multicast (eMBMS): Group partitioning and dynamics

## Paper detail
J. Chen, M. Chiang, J. Erman, G. Li, K. K. Ramakrishnan and R. K. Sinha, "Fair and optimal resource allocation for LTE multicast (eMBMS): Group partitioning and dynamics," 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2015, pp. 1266-1274, doi: 10.1109/INFOCOM.2015.7218502.

## Paper Introduction
### Introduction
  3GPP 標準指定了透過 LTE 網路進行多播的Evolved Multimedia Broadcast Multicast Service (eMBMS)。當傳播內容具有顯著的空間和時間局部性時，eMBMS 特別有效，像是當用戶要收看或收聽直播和音樂以及流行的點播內容（包括新聞、廣告和軟體分發）以及影片。

  目前多播還有一些問題要解決，大致分為這兩類：
1. 網路營運商必須決定向每個 eNB 上的每個單播用戶和多播群組分配多少資源。 為多播分配更多資源可能會降低單播用戶的體驗品質 (QoE)，而為單播分配更多資源會降低無線頻譜的利用效率。
2. 網路業者必須決定提供多少個多播群組，以及哪些對多播內容感興趣的使用者應該聯合起來形成一個群組。 將通道條件不同的使用者分到一個組播群組中，對於通道條件好的使用者來說是不公平的，因為所有群組成員都會受到群組中最差使用者的可接收速率的限制（以確保所有使用者以高機率接收到傳輸的資料） ）。 將潛在的多播用戶分成大量單獨的群組與單播類似，並且無法利用 eMBMS。

  圖二這個範例很好的講述了上面的問題，大家可以參考。使用者的速率由RB的數量（變數）、她自己的編碼方案（固定，基於她的通道條件）、使用者分組（變數）和群組編碼方案（變數）來決定。 為了兼顧用戶費率的公平性和系統的效率，我們選擇比例公平度量[5]來衡量全局效用，其定義為用戶長期 rate 的對數總和。 我們考慮一組對存取特定多播內容感興趣的多播用戶。 我們共同優化組播資源和使用者分組，以最大化 eMBMS 服務區域內多個小區的組播和單播用戶的比例公平效用。 對於單一 cell，我們也分析了全局最優解與試圖最大化自己速率的貪婪用戶的局部偏好之間的差異。

### Background and Problem Formulation

#### A Background
  在 4G 中無線電資源通常都是指 OFDMA 的 frame，這個 frame 是由頻率和時間所組成的資源塊（RB），也是這裡的最小單位資源。eNodeB（LTE 基地台，以下簡稱 eNB）的工作會為單播用戶。由於使用者有不同的通道狀況，eNB根據測量到的每個使用者不同的通道狀況，為每個使用者端選擇合適的 module and coding scheme(MCS)。 MCS 決定每個資源區塊可以傳輸多少位元。 訊號強度好的使用者可以使用更有效率的MCS，反之亦然。 如果 eNB 選擇的 MCS 高於客戶端通道可支援的 MCS，則用戶端將無法解碼數據，並且會因過高的錯誤率而遭受資料遺失。

  在eMBMS中，每個多播組使用以相同 MCS 編碼的資源區塊。 特定群組中的所有使用者接收相同的資料傳輸。 多播資源分配與 MCS 由下圖所示的multi-cell/multicast coordinating entity （MCE）決定[1]。 典型設想的 eMBMS 部署覆蓋多個相鄰 eNB，稱為 multicast-broadcast single-frequency network (MBSFN)，以便利用跨足夠數量接收者的多播並改善小區邊緣的 QoE。 MCE向其控制下的eNB提供多播資源分配。 每個eNB為多播流保留這些資源，並利用剩餘資源來調度自己的單播用戶。 因此，每個eNB的資源區塊分配將根據單播使用者而不同，但多播資源區塊分配在所有eNB上將是相同的。


#### B Problem Formulation

  我們的問題是一個由兩部分組成的混合整數最佳化問題。 問題 1 是針對組播和單播用戶的全域 rate 最佳化。 問題 2 是每個eNB 對於單播用戶的eNB資源分配。 這兩個問題是相關的，因為全域最佳化要考慮組播資源分配對單播使用者的影響。 然而，eMBMS架構不提供修改單播調度的靈活性，因此我們無法直接控制單播資源分配。 相反，透過了解多播資源分配如何影響單播調度，我們可以針對兩組使用者進行最佳化。

  控制點在於 (a) 決定對特定多播內容感興趣的用戶中的哪些用戶應放入同一個多播群組中，以及 (b) 提供多少資源給每個多播群組和其餘單播用戶，來最大化所有使用者的比例公平 rate。 問題 1給出了完整的最佳化問題。


符號解釋如下圖


  限制中比較特殊的是 constraint (4)，可以從下圖選擇其中一式來當成調製多播用戶的資源分配形式，使其更類似於單播或多播。


  實際上，MCE無法控制單播RB，這是問題 1 中的變數。相反，eMBMS服務區中的每個eNB為其小區中的單播用戶調度RB。 問題 1 的任何解決方案都應該考慮 eNB 調度程序的行為，該行為基於標準比例公平調度程序 [7]：

  unicast user 的 MCS 和資源配置則是由基地台決定，可以寫為


### Solutions for Resource Allocation & Group Partitioning
  問題 1 的解方有兩個步驟：（步驟 1），一個外循環，給定一些資訊，並找到最佳使用者分組，如第 III-B 所述；（步驟 2），一個內循環，對於剛剛最佳的使用者分組，求出最佳的資源分配和效用，如 III-A 節所述。

#### A. Resource Allocation

  我們在將求解資源分配和效用分成兩個問題，分別為剛剛的問題 2 和如下的問題 3 ： MCE 去執行 multicast user 的 MCS 和資源分配


請記得在求解這個問題時要考慮到單播的資源分配。問題 3 跟問題 1 很像，除了變數 y。

現在他們提出問題 2 的公平解為


這意味著通道狀況好的使用者接收到的速率較高，而通道狀況較差的使用者接收到的速率較低。解出之後問題 3 也可以解得出來，而此時他們可以證明問題 1 最佳解如下，


#### B. Group Membership Assignment

  而此時還有分群問題尚未解決，他們用一個我尚未看懂的特殊分群方法去分群。總之在配合之前的解，可以寫成演算法 1。

### Users' Selfish Switching Behaviors
  在§III中，網路營運商將頻譜資源分配給用戶，以實現全球公平、高效的費率分配。 然而，這忽略了一個重要的實際考慮：單一用戶可能會自私地透過在多播和單播之間切換來最大化其速率，這偏離了運營商期望的解決方案。 例如，如果多播組中的用戶被其多播組中最差的成員強迫使用低編碼方案，則她可能會離開她的多播組以獲得更好的單播速率。 類似地，對已置於單播中的多播內容感興趣的用戶可能會看到分組在一起的其他多播用戶正在接收更多RB，並嘗試加入該群組。 如果使用者切換，MCE 會根據切換建立的新使用者群組重新分配資源，使切換行為變得更加複雜。 蜂窩運營商應確保全域最優方案下的用戶速率足夠高，使得用戶不想從組播切換到單播，反之亦然。

  我們假設多媒體內容可透過多播和常規單播資料通道取得，並且使用者可以在它們之間自由選擇（可能透過專用多播行動應用程式）。 我們的分析表明，在四個場景中，只有"使用者從 multicast group 切換到 unicast 最有可能會發生，且這種行為對效能影響比較嚴重"，會導致使用者偏離全局最優解決方案，所以我們建議限制表現出這種不良行為的使用者數量。

### Performance Evaluation

  由於這算是一篇正規解最佳化問題的論文，因此模擬我就留給大家自行閱讀。

# Comment
  這篇算是比較早在做多組多播的論文了，他考慮了多播和單播使用者聯合最佳化，這是一般論文比較少見的了。整體來說這篇寫中規中矩。

  比較可惜的是多播技術到現在也沒什麼被網路營運商採用（至少世界大多數國家，包括台灣都沒有用），主要原因是目前大家使用習慣改變，不像以前哪個時段有什麼電影就看什麼，而是回家累了打開 NetFlix 挑一部自己想看的。