微信服务号

微信订阅号

2025-4-15- 4
Home > Archive>Volume 20, Issue 5, 2009 >1349-1361
PDF HTML XML Export Cite reminder
Research on the Optimization Problems in Network Coding
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [41]
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    This paper briefly reviews the theoretical researches on network coding, from which the significance of research on optimization problems is revealed. Based on the network information flow model, it makes a survey on the formulation, characteristics and algorithms of optimization problems with the latest results. According to the goal of optimization, the typical optimization problems in network coding are classified into four categories: minimum-cost multicast, throughput maximization in undirected networks, minimum number of coding nodes and links, topology design of network coding-based multicast networks. The general approaches to deal with these problems are categorized. For (linear or convex) programming problems, the solutions are summarized; for NP complete problems, the latest heuristic algorithms and their difficulties are analyzed. The perspectives on future work are also discussed.

    Reference
    [1] Ahlswede R, Cai N, Li SYR, Yeung RW. Network information flow. IEEE Trans. on Information Theory, 2000,46(4):1204?1216.
    [2] Jain K, Mahdian M, Salavatipour MR. Packing Steiner trees. In: Proc. of the 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA). New York: ACM Press, 2003. 266?274.
    [3] Chen S, Gunluk O, Yener B. The multicast packing problem. IEEE/ACM Transactions on Networking, 2000,8(3):311?318.
    [4] Li SYR, Yeung RW, Cai N. Linear network coding. IEEE Trans. on Information Theory, 2003,49(2):371?381.
    [5] Koetter R, Medard M. An algebraic approach to network coding. IEEE/ACM Trans. on Networking, 2003,11(5):782?795.
    [6] Jaggi S, Sanders P, Chou PA, Effros M, Egner S, Jain K, Tolhuizen L. Polynomial time algorithms for multicast network code construction. IEEE Trans. on Information Theory, 2005,51(6):1973?1982.
    [7] Ho T, Medard M, Koetter R, Shi J, Effros M, Karger D. On randomized network coding. In: Proc. of the 41st Annual Allerton Conf. on Communication, Control, and Computing. 2003.
    [8] Gkantsidis C, Miller J, Rodriguez P. Anatomy of a P2P content distribution system with network coding. In: Proc. of the 5th Int’l Workshop on Peer-to-peer Systems (IPTPS 2006). 2006.
    [9] Wang M, Li B. How practical is network coding. In: Proc. of the 14th IEEE Int’l Workshop on Quality of Service (IWQoS 2006). 2006. 274?278.
    [10] Lun DS, Medard M, Ho T, Koetter R. Network coding with a cost criterion. In: Proc. of the 2004 Int’l Symp. on Information Theory and its Applications (ISITA 2004). 2004. 1232?1237.
    [11] Ahluwalia A, Modiano E, Shu L. On the complexity and distributed construction of energy-efficient broadcast trees in static ad hoc wireless networks. IEEE Trans. on Wireless Communication, 2005,4(5):2136?2147.
    [12] Zosin L, Khuller S. On directed Steiner trees. In: Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2002). San Francisco: ACM Press, 2002. 59?63.
    [13] Lun DS, Ratnakar N, Koetter R, Medard M, Ahmed E, Lee H. Achieving minimum-cost multicast: A decentralized approach based on network coding. In: Proc. of the IEEE INFOCOM 2005. Miami: IEEE Computer Society, 2005. 1607?1617.
    [14] Lun DS, Ratnakar N, Medard M, Koetter R, Karger DR, Ho T, Ahmed E, Zhao F. Minimum-Cost multicast over coded packet networks. IEEE Trans. on Information Theory, 2006,52(6):2608?2623.
    [15] Wu Y, Kung SY. Distributed utility maximization for network coding based multicasting: A shortest path approach. IEEE Journal on Selected Areas in Communications, 2006,24(8):1475?1488.
    [16] Wu Y, Chiang M, Kung SY. Distributed utility maximization for network coding based multicasting: A critical cut approach. In: Proc. of the 4th Int’l Symp. on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. 2006. 1?6.
    [17] Katti S, Rahul H, Katabi D, Hu W, Katabi D, Medard M, Crowcroft J. XORs in the Air: Practical wireless network coding. IEEE/ACM Trans. on Networking, 2008,16(3):497?510.
    [18] Katti S, Gollakota S, Katabi D. Embracing wireless interference: Analog network coding. In: Proc. of the ACM/SIGCOMM. Kyoto: ACM Press, 2007. 397?408.
    [19] Jamieson K, Balakrishnan H. PPR: Partial packet recovery for wireless networks. In: Proc. of the ACM SIGCOMM. Kyoto: ACM Press, 2007. 409?420.
    [20] Liang W. Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proc. of the 3rd ACM Int’l Symp. on Mobile Ad Hoc Networking & Computering (MOBIHOC 2002). Lausanne: ACM Press, 2002. 112?122.
    [21] Lun DS, Medard M, Koetter R. Efficient operation of wireless packet networks using network coding. In: Proc. of the Int’l Workshop on Convergent Technologies (IWCT). 2005.
    [22] Lun DS, Medard M, Effros M. On coding for reliable communication over packet networks. In: Proc. of the 42nd Annual Allerton Conf. on Communication, Control and Computing. 2004.
    [23] Lun DS, Medard M, Koetter R, Effros M. Further results on coding for reliable communication over packet networks. In: Proc. of the 2005 IEEE Int’l Symp. on Information Theory (ISIT 2005). Adelaide: IEEE Computer Society, 2005. 1848?1852.
    [24] Wu Y, Chou PA, Kung SY. Minimum-energy multicast in mobile ad hoc networks using network coding. IEEE Trans. on Communications, 2005,56(11):1906?1918.
    [25] Sanders P, Egner S, Tolhuizen L. Polynomial time algorithms for network information flow. In: Proc. of the 15th ACM Symp. on Parallelism in algorithms and architectures. San Diego: ACM Press, 2003. 286?294.
    [26] Li Z, Li B, Jiang D, Lau L.C. On achieving optimal throughput with network coding. In: Proc. of the IEEE INFOCOM 2005. Miami: IEEE Computer Society, 2005. 2184?2194.
    [27] Li Z, Li B. Network coding in undirected networks. In: Proc. of the 38th Annual Conf. on Information Sciences and Systems (CISS). 2004. 257?262.
    [28] Li Z, Li B. Efficient and distributed computation of maximum multicast rates. In: Proc. of the IEEE INFOCOM 2005. Miami: IEEE Computer Society, 2005. 1618?1628.
    [29] Fragouli C, Solijanin E. Information flow decomposition for network coding. IEEE Trans. on Information Theory, 2006,52(3): 829?848.
    [30] Langberg M, Sprintson A, Bruck J. The encoding complexity of network coding. IEEE Trans. on Information Theory, 2006,52(6): 2386?2397.
    [31] Bhattad K, Ratnakar N, Koetter R, Narayanan K.R. Minimal network coding for multicast. In: Proc. of the IEEE ISIT. Adelaide: IEEE Computer Society, 2005. 1730?1734.
    [32] Kim M, Ahn CW, Medard M, Effros M. On minimizing network coding resources: An evolutionary approach. In: Proc. of the NetCod. 2006.
    [33] Kim M, Medard M, Aggarwal V, O’Reilly UM, Kim W, Ahn CW, Effros M. Evolutionary approaches to minimizing network coding resources. In: Proc. of the IEEE INFOCOM 2007. Anchorage: IEEE Computer Society, 2007. 1991?1999.
    [34] Kim M, Aggarwal V, O’Reilly UM, Medard M, Kim W. Genetic representations for evolutionary minimization of network coding resources. In: Proc. of the 4th European Workshop on the Application of Nature-Inspired Techniques to Telecommunication Networks and Other Connected Systems (EvoCOMNET 2007). Valencia: Springer-Verlag, 2007.
    [35] Kim M, Aggarwal V, O’Reilly UM, Medard M. A doubly distributed genetic algorithm for network coding. In: Proc. of the 9th Annual Conf. on Genetic and Evolutionary Computation, GECCO 2007. New York: ACM Press, 2007. 1272?1279.
    [36] Kim M, Medard M, Aggarwal V, O’Reilly UM. On the coding-link cost tradeoff in multicast network coding. In: Proc. of the 2007 Military Communications Conf. (MILCOM 2007). 2007. 1?7.
    [37] Chi K, Jiang X, Horiguchi S, Guo M. Topology design of network-coding-based multicast networks. IEEE Trans. on Mobile Computing, 2008,7(4):627?640.
    [38] Chi K, Jiang X, Horiguchi S. An improved topology design algorithm for network coding-based multicast networks. In: Proc. of the ICC 2007. Glasgow: IEEE Computer Society, 2007. 6111?6116.
    [39] Xi Y, Yeh EM. Distributed algorithms for minimum cost multicast with network coding in wireless networks. In: Proc. of the 4th Int’l Symp. on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. Boston: IEEE Computer Society, 2006. 1?9.
    [40] Cui Y, Xue Y, Nahrstedt K. Optimal distributed multicast routing using network coding: Theory and applications. ACM SIGMETRICS Performance Evaluation Review, 2004,32(2):47?49.
    [41] Elbaum R, Sidi M. Topological design of local-area networks using genetic algorithms. IEEE/ACM Trans. on Networking, 1996, 4(5):766?778.
    Related
    Cited by
Get Citation

黄政,王新.网络编码中的优化问题研究.软件学报,2009,20(5):1349-1361

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 24,2008
  • Revised:October 17,2008
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2035075Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063