Abstract

Recently, the hybrid wireless-optical broadband network integrating optical backbone networks, passive optical networks (PON), and wireless access networks have been proposed to provide the high-bandwidth, low-cost, and ubiquitous communication connections. In this paper, we consider the design of network coding-based multicast applications in such networks with the objective of maximizing the total network utility and minimizing the deployment cost, subject to QoS constraints. The problem is formulated as a mixed integer nonlinear programming problem and the exact solution is prohibitively complex. In order to make the problem more tractable, we develop a two-step optimization procedure that iteratively selects the optical network unit and gateways for the multicast sessions. During each iteration, two subproblems are solved, i.e., a network coding design problem for the optical network, and a user assignment and bandwidth allocation problem for the wireless network. The former is solved in a distributed way based on the Lagrangian-dual decomposition; the latter is solved based on the generalized bender decomposition. Simulation results are provided to illustrate the effectiveness of the proposed solutions.

© 2012 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. W.-T. Shaw, S.-W. Wong, N. Cheng, K. Balasubramanian, X. Zhu, M. Maier, L. G. Kazovsky, "Hybrid architecture and integrated routing in a highly scalable optical-wireless network," J. Lightw. Technol. 25, 3343-3351 (2007).
  2. S. Sarkar, H.-H. Yen, S. Dixit, B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning and setup," IEEE J. Sel. Areas Commun. 26, 12-21 (2008).
  3. I. Filippini, M. Cesana, "Topology optimization for hybrid optical/wireless access networks," Ad Hoc Netw. 8, 614-625 (2010).
  4. B. Lin, P. Ho, X. Shen, F. Su, "Network planning for next-generation metropolitan-area broadband access under EPON-WiMAX integration," presented at the IEEE Global Telecommun. Conf. New OrleansLA (2008).
  5. E. Amaldi, A. Capone, M. Cesana, I. Filippini, F. Malucelli, "Optimization models and methods for planning wireless mesh networks," Comput. Netw. 52, 2159-2171 (2008).
  6. K. Li, X. Wang, "Cross-layer design of wireless mesh networks with network coding," IEEE Trans. Mobile Comput. 7, 1363-1373 (2008).
  7. Y. Yu, S. Murphy, L. Murphy, "Planning base station and relay station locations in IEEE 802.16j multi-hop relay networks," Proc. IEEE Consum. Commun. Netw. Conf. (2008) pp. 922-926.
  8. R. Ahlswede, N. Cai, S. Y. R. Li, R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory 46, 1204-1216 (2000).
  9. M. Xiao, T. Aulin, "Energy-efficient network coding for the noisy channel network," Proc. 2006 IEEE Int. Symp. Inf. Theory (2006).
  10. K. Miller, T. Biermann, H. Woesner, H. Karl, "Network coding in passive optical networks," Proc. IEEE Int. Symp. Netw. Coding (2010) pp. 1-6.
  11. R. Menendez, J. Gannet, "Efficient, fault-tolerant all-optical multicast networks via network coding," Proc. Opt. Fiber Commun./Nat. Fiber Opt. Eng. Conf. (2008) pp. 1-3.
  12. E. D. Manley, J. S. Deogun, L. Xu, "Network coding for optical-layer multicast," Proc. 5th Int. Conf. Broadband Commun. (2008) pp. 452-459.
  13. R. S. Thinniyam, M. Kim, M. Médard, U.-M. O'Reilly, "Network coding in optical networks with O/E/O based wavelength conversion," Proc. Opt. Fiber Commun./National Fiber Opt. Eng. Conf. (2010) pp. 1-3.
  14. J. Du, M. Xiao, M. Skoglund, "Cooperative network coding strategies for wireless relay networks with backhaul," IEEE Trans. Commun. 59, 2502-2514 (2011).
  15. R. Chandra, L. Qiu, K. Jain, M. Mahdian, "Optimizing the placement of integration points in multi-hop wireless networks," Proc. 12th IEEE Int. Conf. Netw. Protocols (2004) pp. 271-282.
  16. B. Aoun, R. Boutaba, Y. Iraqi, G. Kenward, "Gateway placement optimization in wireless mesh networks with QoS constraints," IEEE J. Sel. Areas Commun. 24, 2127-2136 (2006).
  17. Y. Drabu, H. Peyravi, "Gateway placement with QoS constraints in wireless mesh networks," Proc. 7th IEEE Int. Conf. Netw. (2008) pp. 46-51.
  18. E. D. Manley, J. S. Deogun, L. Xu, D. R. Alexander, "All-optical network coding," J. Opt. Commun. Netw. 2, 175-191 (2010).
  19. D. S. Lun, M. Médard, T. Ho, R. Koetter, "Network coding with a cost criterion," Proc. 2004 Int. Symp. Inf. Theory Appl. (2004) pp. 1232-1237.
  20. D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, E. Ahmed, H. Lee, "Achieving minimum-cost multicast: A decentralized approach based on network coding," Proc. Annu. Joint. Conf. IEEE Comput. Commun. Soc. (2005) pp. 1607-1617.
  21. R. Gallager, "A minimum delay routing algorithm using distributed computation," IEEE Trans. Commun. 25, 73-85 (1977).
  22. D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, D. R. Karger, T. Ho, E. Ahmed, F. Zhao, "Minimum-cost multicast over coded packet networks," IEEE Trans. Inf. Theory 52, 2608-2623 (2006).
  23. S.-Y. R. Li, R. W. Yeung, N. Cai, "Linear network coding," IEEE Trans. Inf. Theory 49, 371-381 (2003).
  24. T. Ho, M. Médard, R. Koetter, D. Karger, M. Effros, J. Shi, B. Leong, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory 52, 4413-4430 (2004).
  25. Y. Xi, E. M. Yeh, "Distributed algorithms for minimum cost multicast with network coding," IEEE/ACM Trans. Netw. 18, 379-392 (2010).
  26. M. M. Carvalho, J. J. Garcia-Luna-Aceves, "Delay analysis of the IEEE802.11 in single-hop networks," Proc. 11th IEEE Int. Conf. Netw. Protocols (2003) pp. 146-155.
  27. S. Sarkar, H.-H. Yen, S. Dixit, B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning using Lagrangian relaxation," IEEE/ACM Trans. Netw. 17, 1094-1105 (2009).
  28. A. M. Geoffrion, "Generalized benders decomposition," J. Optimization Theory Appl. 10, 237-260 (1972).
  29. J. Chen, L. Qian, Y. Zhang, "On optimization of joint base station association and power control via benders' decomposition," Proc. IEEE Global Telecommun. (2009) pp. 1-6.
  30. M. P. Mcgarry, M. Reisslein, M. Maier, "Ethernet passive optical network architectures and dynamic bandwidth allocation algorithms," IEEE Commun. Surveys Tuts. 10, 46-60 (2008).
  31. J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems," Numerische Mathematik 4, 238-252 (1962).
  32. J. Mo, J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw. 8, 556-567 (2000).
  33. L. Massoulié, J. Roberts, "Bandwidth sharing: Objectives and algorithms," IEEE/ACM Trans. Netw. 10, 320-328 (2002).
  34. D. P. Palomar, M. Chiang, "Alternative distributed algorithms for network utility maximization: Framework and applications," IEEE Trans. Autom. Control 52, 2254-2269 (2007).
  35. J. Löfberg, "YALMIP: A toolbox for modeling and optimization in MATLAB," Proc. IEEE Int. Conf. Robot. Autom. (2004) pp. 284-289.

2011 (1)

J. Du, M. Xiao, M. Skoglund, "Cooperative network coding strategies for wireless relay networks with backhaul," IEEE Trans. Commun. 59, 2502-2514 (2011).

2010 (3)

I. Filippini, M. Cesana, "Topology optimization for hybrid optical/wireless access networks," Ad Hoc Netw. 8, 614-625 (2010).

E. D. Manley, J. S. Deogun, L. Xu, D. R. Alexander, "All-optical network coding," J. Opt. Commun. Netw. 2, 175-191 (2010).

Y. Xi, E. M. Yeh, "Distributed algorithms for minimum cost multicast with network coding," IEEE/ACM Trans. Netw. 18, 379-392 (2010).

2009 (1)

S. Sarkar, H.-H. Yen, S. Dixit, B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning using Lagrangian relaxation," IEEE/ACM Trans. Netw. 17, 1094-1105 (2009).

2008 (4)

M. P. Mcgarry, M. Reisslein, M. Maier, "Ethernet passive optical network architectures and dynamic bandwidth allocation algorithms," IEEE Commun. Surveys Tuts. 10, 46-60 (2008).

E. Amaldi, A. Capone, M. Cesana, I. Filippini, F. Malucelli, "Optimization models and methods for planning wireless mesh networks," Comput. Netw. 52, 2159-2171 (2008).

K. Li, X. Wang, "Cross-layer design of wireless mesh networks with network coding," IEEE Trans. Mobile Comput. 7, 1363-1373 (2008).

S. Sarkar, H.-H. Yen, S. Dixit, B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning and setup," IEEE J. Sel. Areas Commun. 26, 12-21 (2008).

2007 (2)

W.-T. Shaw, S.-W. Wong, N. Cheng, K. Balasubramanian, X. Zhu, M. Maier, L. G. Kazovsky, "Hybrid architecture and integrated routing in a highly scalable optical-wireless network," J. Lightw. Technol. 25, 3343-3351 (2007).

D. P. Palomar, M. Chiang, "Alternative distributed algorithms for network utility maximization: Framework and applications," IEEE Trans. Autom. Control 52, 2254-2269 (2007).

2006 (2)

B. Aoun, R. Boutaba, Y. Iraqi, G. Kenward, "Gateway placement optimization in wireless mesh networks with QoS constraints," IEEE J. Sel. Areas Commun. 24, 2127-2136 (2006).

D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, D. R. Karger, T. Ho, E. Ahmed, F. Zhao, "Minimum-cost multicast over coded packet networks," IEEE Trans. Inf. Theory 52, 2608-2623 (2006).

2004 (1)

T. Ho, M. Médard, R. Koetter, D. Karger, M. Effros, J. Shi, B. Leong, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory 52, 4413-4430 (2004).

2003 (1)

S.-Y. R. Li, R. W. Yeung, N. Cai, "Linear network coding," IEEE Trans. Inf. Theory 49, 371-381 (2003).

2002 (1)

L. Massoulié, J. Roberts, "Bandwidth sharing: Objectives and algorithms," IEEE/ACM Trans. Netw. 10, 320-328 (2002).

2000 (2)

J. Mo, J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw. 8, 556-567 (2000).

R. Ahlswede, N. Cai, S. Y. R. Li, R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory 46, 1204-1216 (2000).

1977 (1)

R. Gallager, "A minimum delay routing algorithm using distributed computation," IEEE Trans. Commun. 25, 73-85 (1977).

1972 (1)

A. M. Geoffrion, "Generalized benders decomposition," J. Optimization Theory Appl. 10, 237-260 (1972).

1962 (1)

J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems," Numerische Mathematik 4, 238-252 (1962).

Ad Hoc Netw. (1)

I. Filippini, M. Cesana, "Topology optimization for hybrid optical/wireless access networks," Ad Hoc Netw. 8, 614-625 (2010).

Comput. Netw. (1)

E. Amaldi, A. Capone, M. Cesana, I. Filippini, F. Malucelli, "Optimization models and methods for planning wireless mesh networks," Comput. Netw. 52, 2159-2171 (2008).

IEEE Commun. Surveys Tuts. (1)

M. P. Mcgarry, M. Reisslein, M. Maier, "Ethernet passive optical network architectures and dynamic bandwidth allocation algorithms," IEEE Commun. Surveys Tuts. 10, 46-60 (2008).

IEEE J. Sel. Areas Commun. (1)

S. Sarkar, H.-H. Yen, S. Dixit, B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning and setup," IEEE J. Sel. Areas Commun. 26, 12-21 (2008).

IEEE Trans. Commun. (1)

J. Du, M. Xiao, M. Skoglund, "Cooperative network coding strategies for wireless relay networks with backhaul," IEEE Trans. Commun. 59, 2502-2514 (2011).

IEEE J. Sel. Areas Commun. (1)

B. Aoun, R. Boutaba, Y. Iraqi, G. Kenward, "Gateway placement optimization in wireless mesh networks with QoS constraints," IEEE J. Sel. Areas Commun. 24, 2127-2136 (2006).

IEEE Trans. Commun. (1)

R. Gallager, "A minimum delay routing algorithm using distributed computation," IEEE Trans. Commun. 25, 73-85 (1977).

IEEE Trans. Autom. Control (1)

D. P. Palomar, M. Chiang, "Alternative distributed algorithms for network utility maximization: Framework and applications," IEEE Trans. Autom. Control 52, 2254-2269 (2007).

IEEE Trans. Inf. Theory (4)

D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, D. R. Karger, T. Ho, E. Ahmed, F. Zhao, "Minimum-cost multicast over coded packet networks," IEEE Trans. Inf. Theory 52, 2608-2623 (2006).

S.-Y. R. Li, R. W. Yeung, N. Cai, "Linear network coding," IEEE Trans. Inf. Theory 49, 371-381 (2003).

T. Ho, M. Médard, R. Koetter, D. Karger, M. Effros, J. Shi, B. Leong, "A random linear network coding approach to multicast," IEEE Trans. Inf. Theory 52, 4413-4430 (2004).

R. Ahlswede, N. Cai, S. Y. R. Li, R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory 46, 1204-1216 (2000).

IEEE Trans. Mobile Comput. (1)

K. Li, X. Wang, "Cross-layer design of wireless mesh networks with network coding," IEEE Trans. Mobile Comput. 7, 1363-1373 (2008).

IEEE/ACM Trans. Netw. (1)

Y. Xi, E. M. Yeh, "Distributed algorithms for minimum cost multicast with network coding," IEEE/ACM Trans. Netw. 18, 379-392 (2010).

IEEE/ACM Trans. Netw. (3)

S. Sarkar, H.-H. Yen, S. Dixit, B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning using Lagrangian relaxation," IEEE/ACM Trans. Netw. 17, 1094-1105 (2009).

J. Mo, J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw. 8, 556-567 (2000).

L. Massoulié, J. Roberts, "Bandwidth sharing: Objectives and algorithms," IEEE/ACM Trans. Netw. 10, 320-328 (2002).

J. Lightw. Technol. (1)

W.-T. Shaw, S.-W. Wong, N. Cheng, K. Balasubramanian, X. Zhu, M. Maier, L. G. Kazovsky, "Hybrid architecture and integrated routing in a highly scalable optical-wireless network," J. Lightw. Technol. 25, 3343-3351 (2007).

J. Opt. Commun. Netw. (1)

J. Optimization Theory Appl. (1)

A. M. Geoffrion, "Generalized benders decomposition," J. Optimization Theory Appl. 10, 237-260 (1972).

Numerische Mathematik (1)

J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems," Numerische Mathematik 4, 238-252 (1962).

Other (14)

J. Chen, L. Qian, Y. Zhang, "On optimization of joint base station association and power control via benders' decomposition," Proc. IEEE Global Telecommun. (2009) pp. 1-6.

M. M. Carvalho, J. J. Garcia-Luna-Aceves, "Delay analysis of the IEEE802.11 in single-hop networks," Proc. 11th IEEE Int. Conf. Netw. Protocols (2003) pp. 146-155.

J. Löfberg, "YALMIP: A toolbox for modeling and optimization in MATLAB," Proc. IEEE Int. Conf. Robot. Autom. (2004) pp. 284-289.

D. S. Lun, M. Médard, T. Ho, R. Koetter, "Network coding with a cost criterion," Proc. 2004 Int. Symp. Inf. Theory Appl. (2004) pp. 1232-1237.

D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, E. Ahmed, H. Lee, "Achieving minimum-cost multicast: A decentralized approach based on network coding," Proc. Annu. Joint. Conf. IEEE Comput. Commun. Soc. (2005) pp. 1607-1617.

Y. Drabu, H. Peyravi, "Gateway placement with QoS constraints in wireless mesh networks," Proc. 7th IEEE Int. Conf. Netw. (2008) pp. 46-51.

Y. Yu, S. Murphy, L. Murphy, "Planning base station and relay station locations in IEEE 802.16j multi-hop relay networks," Proc. IEEE Consum. Commun. Netw. Conf. (2008) pp. 922-926.

R. Chandra, L. Qiu, K. Jain, M. Mahdian, "Optimizing the placement of integration points in multi-hop wireless networks," Proc. 12th IEEE Int. Conf. Netw. Protocols (2004) pp. 271-282.

B. Lin, P. Ho, X. Shen, F. Su, "Network planning for next-generation metropolitan-area broadband access under EPON-WiMAX integration," presented at the IEEE Global Telecommun. Conf. New OrleansLA (2008).

M. Xiao, T. Aulin, "Energy-efficient network coding for the noisy channel network," Proc. 2006 IEEE Int. Symp. Inf. Theory (2006).

K. Miller, T. Biermann, H. Woesner, H. Karl, "Network coding in passive optical networks," Proc. IEEE Int. Symp. Netw. Coding (2010) pp. 1-6.

R. Menendez, J. Gannet, "Efficient, fault-tolerant all-optical multicast networks via network coding," Proc. Opt. Fiber Commun./Nat. Fiber Opt. Eng. Conf. (2008) pp. 1-3.

E. D. Manley, J. S. Deogun, L. Xu, "Network coding for optical-layer multicast," Proc. 5th Int. Conf. Broadband Commun. (2008) pp. 452-459.

R. S. Thinniyam, M. Kim, M. Médard, U.-M. O'Reilly, "Network coding in optical networks with O/E/O based wavelength conversion," Proc. Opt. Fiber Commun./National Fiber Opt. Eng. Conf. (2010) pp. 1-3.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.