Hybrid wireless-optical broadband access network (WOBAN): network planning using Lagrangean relaxation

ABSTRACT

The concept of a hybrid wireless-optical broadband access network (WOBAN) is a very attractive one. This is because it may be costly in several situations to run fiber to every home (or equivalent end-user premises) from the telecom central office (CO); also, providing wireless access from the CO to every end user may not be possible because of limited spectrum. Thus, running fiber as far as possible from the CO toward the end user and then having wireless access technologies take over may be an excellent compromise. How far should fiber penetrate before wireless takes over is an interesting engineering design and optimization problem, which we address in this paper. We propose and investigate the characteristics of an analytical model for network planning, namely optimum placements of base stations (BSs) and optical network units (ONUs) in aWOBAN (called the primal model, or PM). We develop several constraints to be satisfied: BS and ONU installation constraints, user assignment constraints, channel assignment constraints, capacity constraints, and signal-quality and interference constraints. To solve this PM with reasonable accuracy, we use "Lagrangean relaxation" to obtain the corresponding "Lagrangean dual" model. We solve this dual problem to obtain a lower bound (LB) of the primal problem. We also develop an algorithm (called the primal algorithm) to solve the PM to obtain an upper bound (UB). Via simulation, we compare this PM to a placement heuristic (called the cellular heuristic) and verify that the placement problem is quite sensitive to a set of chosen metrics.

REFERENCES

• 1: S. Sarkar, B. Mukherjee, and S. Dixit, "Optimum placement of multiple optical network units (ONUs) in optical-wireless hybrid access networks," in Proc. OFC'06, Anaheim, CA, Mar. 2006.
• 2: S. Sarkar, B. Mukherjee, and S. Dixit, "Towards global optization of multiple ONUs placment in hybrid optical-wireless broadband access networks," in Proc. COIN'06, Jeju, South Korea, Jul. 2006.
• 3: S. Sarkar, S. Dixit, and B. Mukherjee, "Hybrid wireless-optical broad-band access network (WOBAN): A review of relevant challenges," J. Lightw. Technol., vol. 25, no. 11, pp. 3329-3340, Nov. 2007, Invited Paper.
• 4: H. Sherali, C. Pendyala, and T. Rappaport, "Optimal location of transmitters for micro-cellular radio communication system design," IEEE J. Sel. Areas Commun., vol. 14, no. 4, pp. 662-673, May 1996.
• 5: M. Wright, "Optimization methods for base station placement in wireless applications," in Proc. VTC'98, Ottawa, Canada, May 1998, vol. 1, pp. 387-391.
• 6: A. Molina, G. Athanasiadou, and A. Nix, "The automatic location of base-stations for optimised cellular coverage: A new combinatorial approach," in Proc. VTC'99, Houston, TX, May 1999, vol. 1, pp. 606-610.
• 7: S. Hurley, "Automatic base station selection and configuration in mobile networks," in Proc. VTC'00, Boston, MA, Sep. 2000, vol. 6, pp. 2585-2592.
• 8: L. Nagy and L. Farkas, "Indoor base station location optimization using genetic algorithms," in Proc. PIMRC 2000, London, U.K., Sep. 2000, vol. 2, pp. 843-846.
• 9: A. Hills, "Large scale wireless LAN design," IEEE Commun. Mag., vol. 39, no. 11, pp. 98-107, Nov. 2001.
• 10: Y. Chen and H.Kobayashi, "Signal strength based indoor geolocation," in Proc. ICC, New York, Apr. 2002, pp. 436-439.
• 11: M. Kamenetskym and M. Unbehaun, "Coverage planning for outdoor wireless LAN systems," in Proc. Int. Zurich Seminar on Broadband Commun., Access, Transmission, Netw.'02, Zurich, Switzerland, Feb. 2002, pp. 49-1-49-6.
• 12: R. Battiti, M. Brunato, and A. Delai, "Optimal wireless access point placement for location-dependent services," Univ. of Trento, Italy, Technical Report, Oct. 2003.
• 13: P. Lin, T. Wang, J. Hu, Y. Suemura, S. Nakamura, and C. Qiao, "Optical-to-wireless-integration cost modeling," in Proc. HPSR'07, Brooklyn, NY, May 2007, pp. 1-6.
• 14: R. K. Martin, Large Scale Linear and Integer Optimization: A Unified Approach. Norwell, MA: Kluwer, 1999.
• 15: A. M. Geoffrion, "Lagrangean relaxation and its uses in integer programming," Math. Programming Study, vol. 2, pp. 82-114, 1974.
• 16: M. L. Fisher, "The Lagrangean relaxation method for solving integer programming problems," Manage. Sci., vol. 27, no. 1, pp. 1-18, Jan. 1981.
• 17: M. L. Fisher, W. D. Northup, and J. F. Shapiro, "Using duality to solve discrete optimization problems: Theory and computational experience," Math. Programming Study, vol. 3, pp. 56-94, 1975.
• 18: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 19: WiMax Forum [Online]. Available: http://www.wimaxforum.org
• 20: "WiMAX's technology for LOS and NLOS environments," [Online]. Available: http://www.wimaxforum.org/technology/downloads/WiMAXNLOSgeneral-versionaug04.pdf
• 21: "Aprisa XE report," [Online]. Available: http://www.4rf.com
• 22: S. Churchill, "WiMAX 802.16m: 1Gbps," Feb. 20, 2007 [Online]. Available: http://www.dailywireless.org/2007/02/20/wimax-80216m-100-mbps/
• 23: D. Parsons, "GPON vs. EPON: A cost comparison," Sep. 2005 [Online]. Available: http://lw.pennnet.com/articles/article_display.cfm?ar-ticle_id=238749
• 24: "Wireless Net DesignLine," [Online]. Available: http://www.wirelessnetdesignline.com
• 25: H. A. Willebrand and B. S. Ghuman, "Fiber optics without fiber," [Online]. Available: http://www.freespaceoptic.com/fiber_op-tics_without_fiber.htm
• 26: D. Jones, "WiMax: How far? How fast?," Jul. 8., 2004 [Online]. Available: http://www.unstrung.com/document.asp?doc_id=55856&site=unstrung
• 27: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 28: S. Sarkar, H.-H. Yen, S. Dixit, and B. Mukherjee, "Hybrid wireless-optical broadband access network (WOBAN): Network planning and setup," IEEE J. Sel. Areas Commun., vol. 26, no. 6, pp. 12-21, Aug. 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies

General Terms:
Design, Management, Performance

Keywords:
Lagrangean relaxation, broadband access, duality gap, network planning, optical network, primal model (PM), wireless network