A Study of Network Coding-Based Network Protocols for Next Generation Networks Network coding refers to a scheme with which nodes may send out a coded data in a single transmission with combining several data to be forwarded separately. By using an appropriate network coding scheme, we can improve the network performance in several aspects. Hence, in order to further enhance the performance of the Next Generation Networks (NGNs), e.g., WiMAX and LTE-Advanced, which should provide high data rate services, network coding is considered as one of important candidate techniques that can be incorporated into NGNs. In order to study the applicability of network coding in the emerging 4G networks, in this paper, we survey the previous works for incorporating network coding into various layers in communication networks. Keywords: Network coding, Network protocol, Physical layer, MAC layer, Network layer, Transport layer I
II V e E e c(e)
b s1 s2 t2 t1 t2 r1 (s1acdft2) r2 (s2bcdet1) (CD) {(r 1,r 2 ):0r 1,0r 2,r 1 r 2 b}. (1) C A B D t1 t2 E F D s2 s1 {(r 1,r 2 ):0r 1 b,0r 2 b}. (2) s t1t2 t1 t2 a b a b t1 t2 t1 t2 (ab)
a b a b ab III A(B) k A (k B )x A (x B ) n A (n B ) w A (w B ) m S A (S B ) S R A(B) B(A) A(B)
B(A) A B x A x B x R x A x B x R w R S R x A x B w A w B w R w A w B w R S R A B A B B A n B n A A A A n B n A A r A A r A n A /n B r A n A /n B x A x B k A k B w A w B n A n B w A w B A B
S A S B w A w B w R w A w B w R S R A A A B x R x A x B A h AR B h BR n R h AR S A h BR S B n R S R A R (h AR S A h BR S B n R ) A B ΛΛ 1 (ΛΛ 1 ) Λ Λ 1 R v (Λ) R v (Λ 1 ) R v (Λ) P A w A L A {Λ 1 R v (Λ) B w B L B {Λ 1 R v (Λ)} d A d B A B ys A S B n L(L A L B ) mod Λ L L (αyda d B ) mod Λ =(Lαn(1α)(S A S B )) mod Λ. α E[{αn(1 α)(s A S B )} 2 ] 2P/(2Pσ 2 ) A B L S R A B P R NBC R NAC 2 1 P R NBC R NAC ( log 3 2 2( 1 N 0 )) A B R PNC S A (L A d A ) mod Λ, S B (L B d B ) mod Λ. 1 R PNC (1H(P e )) 2 P e H()
R MAC/BC R AM/FW R LNC 1 2P R MAC/BC log 2( 1 ), 4 N 0 1 β 2 P R AM/FW log 2( 1 ), 4 N 0 β 2 N 0 1 1 P R LNC log 2( 2 2 N 0 ) (P/(2PN 0 ) IV X A O Y B
B A, C, D B P1, P3, P4 AC, D
X U A C Y V P1 P2 N [b 1,b 2,,b N ]
N [c 1,c 2,,c N ] x N xσ c i b i. i1 N N
r NC r RSBS r RSMS r NC min(r RSBS, r RSMS ). s0 d0 r r r N r N N N
N1 V
VI
N N N
VII [1] L. R. Ford and D. R. Fulkerson, ''Maximal flow through a network,'' Canadian Journal of Mathematics, Vol. 8, No. 3, 1956, pp. 399-404. [2] J. Edmonds and R. M. Karp, ''Theoretical improvements in algorithmic efficiency for network flow problems,'' Journal of the Association for Computing Machinery, Vol. 19, No. 2, 1972, pp. 248-264. [3] Y. Wu, P. A. Chou, and S.-Y. Kung, ''Minimumenergy multicast in mobile adhoc networks using network coding,'' IEEE Transactions on Communications, Vol. 53, No. 11, Nov. 2005, pp. 1906-1918. [4] K. Jain, M. Mahdian, and M. R. Salavatipour, ''Packing Steiner trees,'' Proc. of Symposium on Discrete Algorithm, Jan. 2003. [5] J. Edmonds, ''Edge-disjoint branchings,'' Combinatorial Algorithms, Academic Press, 1973, pp. 91-96. [6] C. Schnurr, T. J. Oechtering, and S. Stanczak, ''On coding for the broadcast phase in the two-way relay channel,'' Proc. of CISS, Mar. 2007. [7] I. Byun and K.-S. Kim, ''Practical network-coding scheme for two-way relay channels employing a ratecompatible punctured code,'' IEICE Electronics Express, Vol. 6, No. 21, Nov. 2009, pp. 1522-1527. [8] S. Zhang, S. C. Liew and P. P. Lam, ''Hot topic:
physical-layer network coding,'' Proc. of MobiCom, Sep. 2006. [9] S. Zhang and S.-C. L, ''Channel coding and decoding in a relay system operated with physical-layer network coding,'' IEEE Journal on Selected Area in Communications, Vol. 27, No. 5, Feb. 2010, pp. 788-796. [10] T. J. Oechtering, C. Schnurr, I. Bjelakovic, and H. Boche, ''Achievable rate region of a two phase bidirectional channel,'' Proc. of CISS, Mar. 2007. [11] S. Katti, I. Maric, A. Goldsmith, D. Katabi, and M. Medard, ''Joint relaying and network coding in wireless networks,'' Proc. of ISIT, Jun. 2007. [12] R. H. Y. Louie, Y. Li, and B. Vucetic, ''Practical physical layer network coding for two-way relay channels: performance analysis and comparison,'' IEEE Transactions on Wireless Communications, Vol. 9, No. 2, Feb. 2010, pp. 764-777. [13] F. Xue and S. Sandhu, ''PHY-layer network coding for broadcast channel with side information,'' Proc. of ITW, Sep. 2007. [14] K. Narayanan, M. P. Wilson, and A. Sprintson, ''Joint physical layer coding and network coding for bidirectional relaying,'' IEEE Transactions on Information Theory, Vol. 56, No.11, Nov. 2010, pp. 5641-5654. [15] Y. Hao, D. Goeckel, Z. Ding, D. Towsley, and K. K. Leung, ''Achievable rate for network coding on the exchange channel,'' Proc. of MILCOM, Oct. 2007. [16] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, ''XORs in the air: practical wireless network coding,'' IEEE/ACM Transactions on Networking, Vol. 16, No. 3, Jun. 2008, pp. 497-510. [17] H. Yomo and P. Popovski, ''Opportunistic scheduling for wireless network coding,'' Proc. of IEEE ICC, Jun. 2007. [18] S.-L Gong, B.-G. Kim, and J.-W. Lee, ''Optimal opportunistic scheduling and adaptive modulation policies in wireless ad-hoc networks with network coding,'' IEICE Transactions on Communications, Vol. E92-B, No. 9, Sep. 2009, pp. 2954-2957. [19] J. Zhang, Y. P. Chen, and I. Marsic, ''MAC-layer proactive mixing protocol for network coding in multihop wireless networks,'' Computer Networks, Vol. 54, No. 2, Feb. 2010, pp. 196-207. [20] J. Jin, B. Li, and T. Kong, ''Is random network coding helpful in WiMAX?,'' Proc. of IEEE INFOCOM, Apr. 2008. [21] R. Y. Kim, J. Jin, and B. Li, ''Drizzle: cooperative symbol-level network coding in multi-channel wireless networks,'' IEEE Transactions on Vehicular Technology, Vol. 59, No. 3, Mar. 2010, pp. 1415-1432. [22] M. Nistor, D. E. Lucani, T. T. V. Vinhoza, R. A. Costa, and J. Barros, ''On the delay distribution of random linear network coding,'' IEEE Journal on Selected Areas in Communications, Vol. 29, No. 5, May 2011, pp. 1084-1093. [23] X. Zhang and B. Li, ''Joint network coding and subcarrier assignment in OFDMA-based wvireless networks,'' Proc. of NetCod, Jan. 2008. [24] X. Zhang and B. Li, ''Network coding aware dynamic subcarrier assignment in OFDMA wireless networks,'' Proc. of IEEE ICC, Jul. 2008. [25] Y. Xu, J. C. S. Lui, and D.-M. Chiu, ''Analysis and scheduling of practical network coding in OFDMA relay networks,'' Computer Networks, Vol. 53, No. 12, 2009, pp. 2120-2139. [26] H. Xu and B. Li, ''XOR-assisted cooperative diversity in OFDMA wireless networks: optimization framework and approximation algorithms,'' Proc. of IEEE INFOCOM, Apr. 2009. [27] B.-G. Kim and J.-W. Lee, ''Opportunistic subchannel scheduling for OFDMA networks with network coding at relay stations,'' Proc. of IEEE GLOBECOM, Dec. 2010. [28] C. Peng, Q. Zhang, M. Zhao, and Y. Yao, ''On the performance analysis of networkcoded cooperation in wireless networks,'' Proc. of IEEE INFOCOM, May 2007. [29] S. Sharma, Y. Shi, J. Liu, Y.T. Hou, and S. Kompella, ''Is network coding always good for cooperative communications?,'' Proc. of IEEE INFOCOM, Mar. 2010. [30] S. Sharma, Y. Shi, Y. T. Hou, H. D. Sherali, and S. Kompella, ''Optimizing network-coded cooperative communications via joint session grouping and relay node selection,'' Proc. of IEEE INFOCOM, Apr. 2011. [31] T.-W. Yune, D. Kim, and G.-H. Im, ''Opportunistic network-coded cooperative transmission with demodulate-and-forward protocol in wireless channels,'' IEEE Transactions on Communications, Vol. 59, No. 7, Jul. 2011, pp. 1791-1795. [32] Z. J. Haas and T.-C. Chen, ''Cluster-based cooperative communication with network coding in wireless networks,'' Proc. of MILCOM, Oct. 2010. [33] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, ''Trading structure for randomness in wireless opportunistic routing,'' Proc. of ACM SIGCOMM, Aug. 2007. [34] D. Zeng, S. Guo, V. Leung and J. Hu, ''The exploration
of network coding in IEEE 802.15.4 Networks,'' International Journal of Digital Multimedia Broadcasting, Vol. 2011, Apr. 2011. [35] S. Sengupta, S. Rayanchu, and S. Banerjee, ''An analysis of wireless network coding for unicast sessions: the case for coding-aware routing,'' Proc. of IEEE INFOCOM, May 2007. [36] Y. Gwak, J. Ahn, and Y.-Y. Kim, ''Network codingbased bridge routing in wireless mesh network,'' Proc. of IEEE ICOIN 2011, Jan. 2011. [37] H. Guo, Y. Qian, K. Lu, and N. Moayeri, ''Backbone routing over multihop wireless networks: increased network coding opportunity,'' Proc. of IEEE ICC, May 2010. [38] J. Le, J. C. S. Lui, and D.-M. Chiu, ''DCAR: distributed coding-aware routing in wireless networks,'' IEEE Transactions on Mobile Computing, Vol. 9, No. 4, Apr. 2010, pp. 596-608. [39] J. K. Sundararajan, D. Shah, M. Medard, M. Mitzenmacher, and J. Barros, ''Network coding meets TCP,'' Proc. of IEEE INFOCOM, Apr. 2009. [40] S. Gheorghiu, A. L. Toledo, and P. Rodriguez, ''A network coding scheme for seamless interaction with TCP,'' Proc. of International Symposium on Network Coding, Jul. 2011. [41] L. Scalia, F. Soldo, and M. Gerla, ''PiggyCode: a MAC layer network coding scheme to improve TCP performance over wireless networks,'' Proc. of IEEE GLOBECOM, Nov. 2007. [42] H.-T. Roh and J.-W. Lee, ''Network coding-aware flow control in wireless ad-hoc networks,'' Proc. of IEEE WCNC, Apr. 2009. [43] H. Seferoglu and A. Markopoulou, ''Distributed rate control for video streaming over wireless networks with intersession network coding,'' Proc. of Packet Video Workshop, May 2009.