群播環境下的雙層網路編碼

Abstract

Erasure Codes提供使用者在封包抹除通道(packet erasure channel)擁有可靠的通訊能力，但是在群播網路中存在使用者為了少數需要的編碼區塊而持續等待，產生Coupon Collection Problem問題。網路編碼(Network Coding)利用中繼點的編碼，減少使用者收到資料所需時間。本論文針對one hop wireless network的downlink群播問題提出Two-Layer Network Code，利用Random Linear Code編碼傳送Reed-Solomon Code編碼區塊，並且發送端依據完全訊息(perfect information) 挑選編碼區塊做線性組合，減少使用者接收資料造成的檔案解碼延遲(file decoding time)。 我們提出兩種使用完全訊息依據選取編碼區塊的方法，分別是從候選集合(candidate set)中uniform隨機選取，與依據提出的不等選擇權重選取。在模擬實驗中，我們比較了Reed-Solomon Code、Random Linear Code與提出的Two-Layer Network Code三種編碼在群播環境下所有使用者接收完整資料所花費的時間。模擬結果顯示，雙層網路編碼在較短的最大線性組合degree threshold時，比其他兩種編碼有較好的效能，減少檔案解碼延遲，並且隨著使用者數量增加而有明顯改善。Without proper coding to counter frequent transmission loss over time-varying fading channel, opportunistic multicast in one-hop wireless forward-link still suffers the famous Coupon Collection Problem which incurs a significant amount of delay for some users to receive the last required packet. This issue can be alleviated by viewing the fading channel as an erasure channel and using erasure code over the channel. However, it is unclear how best a coding approach could achieve if there is perfect feedback on channel state. The thesis presents a two-layer network code for use in the multicast scenario and studies its performance. This code is essentially a concatenation of Reed-Solomon code and Random Linear code. The proposed random linear code utilizes channel state and the history of packet reception by each group user to generate coded packets for transmission. Here we use the pair of information on channel state and reception history to create a candidate set. One way is to randomly choose those components in the candidate set. The other is to randomly choose those components with some designed weight. In our simulation, there are three codes used for data transmission: Reed-Solomon Code, Random Linear Code, and proposed two-layer network code. Simulations show that two-layer network code with shorter linear combination degree has better performance than the other two codes. Meanwhile, the decoding delay is reduced. Furthermore, the multicast network with larger group size is more suitable for 2-layer network code.