To XOR or Not to XOR at Relays: Vandermonde Relay-Assisted Network Coding

由於無線網路的傳輸是不可靠的，所以既有的ARQ (Automatic Repeat reQuest)方法雖然達成可靠傳輸的目的，但每成功收到封包就必須回應一個ACK封包以告知成功傳輸，以及ACK封包遺失時將會重傳重複的封包，都是沒有效率行為。為了提供可靠且有效率的無線網路傳輸，我們結合網路編碼(network coding)與增加中繼傳播點(relay node)幫忙傳輸兩種技術，提出了兩種方法—VC (Vandermonde Coding) 與 XOR Fibo。網路編碼改善“成功收到一個封包要回應一個ACK”的機制，變成“成功解回多個封包時回應一個ACK”的機制，以減少ACK的數量。增加中繼傳播點幫忙傳輸可以提高封包抵達目的地的成功數量，不過為了降低中繼點傳輸無用的封包(redundant packet)，中繼點也採用網路編碼，使得編碼後的封包包含更多資訊。VC採用Vandermonde matrix產生編碼的係數，使得產生後的係數彼此比較不容易形成線性相依(linearly dependent)的組合，優於會因為隨機選取係數而有較高的機會產生線性相依之組合的既有技術RNC (Random Network Coding)；此外，RNC需要額外的資源紀錄每個被編碼封包所對應的係數，而VC可以藉由索引值來產生Vandermonde matrix中所對應的行，以減少紀錄所需的資源。比起傳輸點採用VC網路編碼但中繼點使用其他既有網路編碼方式(如：RNC、XOR)，傳輸點與中繼點都採用VC網路編碼可以達到較高的效能與減少無用封包的數量。但是VC會增加中繼點的計算量。因此，我們改良了XOR的編碼方式，提出XOR Fibo，提供中繼點另一種可行的方式。XOR Fibo依據費伯納西數列(Fibonacci sequence)，對不連續的封包進行編碼，改善XOR網路編碼會因為連續對封包進行編碼而容易產生無用的封包。中繼點採用XOR Fibo所達到的效能與採用VC所達到的效能相差在1%以內。

關鍵字

網路編碼；范德蒙矩陣；費波那西數列

並列摘要

For providing the reliable and effective wireless transmission in a relay-assisted network coding system, we propose Vandermonde Coding (VC), a novel network coding scheme with little overhead for both source and relay. VC uses the feature of Vandermonde matrix for guaranteeing linearly independent coding coefficient set. Comparing to random network coding (RNC), which needs extra overhead to record the coding coefficient, VC has little overhead because the generating index of Vandermonde matrix can be related to other information in the packet, like sequence number. For comparison purpose, we propose a theoretically optimal but yet impractical scheme—Max matching, using the idea from graph theory. In our simulation, VC performs equally to Max matching. But the existing popular coding schemes at relay, such as forwarding, RNC and XOR, do not perform well. To our surprise, XOR coding scheme will produce self-redundant packet, which contains coding coefficient that is linearly dependent with the set composed by the packets the relay sent. Although VC has great performance, it increases the computing complexity at relay. Thus, we also propose a lightweight coding scheme, XOR Fibo, which is a novel modification of XOR coding scheme. To avoid generating self-redundant packets, XOR Fibo XORs a subset of received packets, according to the Fibonacci sequence. In our simulation, XOR Fibo has a performance close to VC.

並列關鍵字

network coding ； Vandermonde matrix ； Fibonacci sequence

參考文獻

[4] R. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of Linear Coding in Network Information Flow,” IEEE Transactions on Information Theory, Vol. 51, No. 8, pp.2745-2759, August 2005.

[5] S. Chachulski, M. Jennings, S. Katti, and D. katabi, “Trading Structure for Randomness n Wireless Opportunistic Routing,” in Proc. of ACM SIGOCOMM, 2007.

[8] J. Heide, M. V. Pedersen, F. H. P. Fitzek, and M. Medard, “On Code Parameters and Coding Vector Representation for Practical RLNC,” IEEE International Conference on Communication (ICC), pp.1-5, June 2011.

[9] D. E. Lucani, M. Medard, and M.Stojanovic, “Random Linear Network Coding for Time Division Duplexing: Field Size Considerations,” GLOBECOM, pp.1-6, Dec. 2009.

[10] J. Jin, B. Li, and T. Kong, “Is Random Network Coding Helpful in WiMAX?,” in Proc. of IEEE INFOCOM, pp.2162-2170, Apr. 2008.

國際替代計量

To XOR or Not to XOR at Relays: Vandermonde Relay-Assisted Network Coding

全文下載

主題瀏覽