CENIIT Project 02.09

Optimal Design and Management of Telecommunications Systems

(Optimal Design och Effektiv Planering av Telekommunikationssystem)

Patrik Björklund, Iana Siomina, Peter Värbrand, and Di Yuan

Communications and Transportation Systems, Department of Science and Technology
Linköping Institute of Technology, Sweden

Background and Motivation

The core of this research program is to apply mathematical programming techniques, in particular optimization models and methods, in order to design, analyze, and utilize telecommunications systems efficiently. A simple but fundamental motivation to this research program can be initialized by the question: How can we meet future demand in our telecommunications systems? One possibility is to invest in additional infrastructure and to expand existing ones. A second option is to utilize the existing infrastructure more efficiently by, for example, optimizing the assignment of resources to users. Infrastructure design and resource management involve many decision problems, such as network topology design, capacity dimensioning, facility location, bandwidth allocation, etc. Optimization models and methods provides us with a tool for approaching solutions to these decision problems.

People
  • Patrik Björklund (patbj@itn.liu.se), PhD candidate.
  • Iana Siomina (iansi@itn.liu.se), PhD candidate.
  • Peter Värbrand (petva@itn.liu.se), Professor.
  • Di Yuan (diyua@itn.liu.se), Senior lecturer.


    • Current Topics
    The focus of our current research is  resource management in wireless communication networks. At present, the research topics are
     
  • Pilot power management in UMTS networks
  • Dynamic bandwidth allocation in cellular networks
  • Resource management in ad hoc networks using STDMA
  • Energy-efficient ad hoc networking


    • Pilot Power Management in UMTS Networks (Iana Siomina, Peter Värbrand, Di Yuan)
    Description: In a WCDMA network, a common pilot channel is associated with each cell. This pilot signal is used to provide channel estimation to the mobile terminals. A mobile terminal selects cell by measuring the quality of the pilot signals from the base stations. The problem of choosing the power levels of the pilot signals involves the trade-off between full coverage and power consumption. Increasing the pilot power yields better coverage. However, this would reduce the power available for user traffic. With equally-spread base stations and a uniform traffic distribution, a uniform power level for the pilot signals is adequate. In a networks with a mixture of rural and downtown areas, however, a uniform level of pilot power is not a good solution. The aim of this project is to use optimization methods for planning the levels of the pilot power, with the objectives of maximizing coverage and traffic throughput.
    Research collaboration: Ericsson Research, Linköping, Sweden.
    Contact person: Iana Siomina.

    Dynamic Bandwidth Allocation in WCDMA Networks (Patrik Björklund, Peter Värbrand, Di Yuan.)
    Description: Bandwidth allocation is a key component in real-time management of radio resources. The traffic characteristics in WCDMA networks are very different from those in the second generation mobile networks. Because of the variable-rate nature of the user demands in a WCDMA network, flexible bandwidth allocation is necessary. Moreover, the control system must have the intelligence to perform bandwidth allocation for multiple traffic classes. In recently years, research of resource management in next-generation mobile networks is becoming more intensive. Here, resource management consists of a number of issues, such as queuing and scheduling, admission control, and bandwidth allocation. We consider bandwidth allocation in the context of WCDMA power control. The initial focus lies on the downlink direction, which is expected to support higher rates than the uplink. The project aims to develop effective on-line algorithms that can be used for dynamically allocating the power resource to the mobile users. The criteria for evaluating the algorithms include  resource utilization and user fairness.
    Research collaboration: Ericsson Research, Linköping, Sweden.
    Contact person: Patrik Björklund.

    Resource Management in Ad Hoc Networks using STDMA (Peter Värbrand, Di Yuan.)
    Description: Ad hoc networks is an attractive alternative when it is impractical to provide coverage using fixed infrastructure (e.g., military command and control systems). In ad hoc networks, a link is established between two radio units whenever the signal strength is sufficiently high. Not all pairs of nodes can establish direct links, therefore traffic between two units may have to be relayed through some other units (the multi-hop functionality). We study resource allocation in ad hoc networks where the access control uses Spatial Time Division Multiple Access (STDMA). STDMA improves TDMA by reusing the time slots spatially. In this project, we intend to investigate the potential of STDMA in terms of spatial reuse of the radio resource, and to construct algorithms that are suitable for distributed implementations.
    Research collaboration: The Swedish Defense Research Agency, Linköping, Sweden.
    Contact person: Di Yuan.

    Energy-Efficient Ad Hoc Networking (Peter Värbrand, Di Yuan)
    Description: Wireless networking environments pose new design problems in determining network topology and operation. In ad hoc networks, energy efficiency is a crucial issue for topology management and routing. This research topic is further justified by the fundamental difference between wired and wireless transmission - the latter has an inherent broadcast nature, that is, when omnidirectional antennas are used, transmission of a node can be received simultaneously by all nodes within a certain range. As a consequence, a single transmission is sufficient to reach a group of nodes. At present, most algorithms for topology management and routing are based on wired networking environments. In this project, we develop algorithms that are tailored for wireless ad hoc networks. At the moment, the research focus is energy-efficient broadcasting and multicasting in ad hoc networks.
    Research collaboration: Dipartimento di Elettronica e Informazione, Politechnico di Milano, Italy.
    Contact person: Peter Värbrand.

    Previous Topics
    Frequency Assignment in Frequency-Hopping Cellular Networks
    Description: Due to the limited available frequency spectrum of GSM networks, the performance of a network is greatly dependent on how well the spectrum is utilized. In the classical frequency assignment problem,  radio frequencies (or channels) are assigned to transceivers with the objective of either minimizing the number of frequencies, or the total interference. We generalize the classical frequency assignment for frequency-hopping systems, and develop meta-heuristics for finding high-quality assignment solutions.

    Topology Design and Wavelength Assignment in Optical Networks
    Description: We consider the planning of optical networks in the context of Dense Wave Division Multiplexing (DWDM) technologies. The planning issues include topology design, capacity dimensioning, traffic routing, wavelength assignment, and locations of optical cross-connects (OXCs). We apply integer programming models for the problem of making these decision with the objective of minimizing the total cost. Our solution approach combines a cutting plane method with a rounding heuristic. (This research was carried out jointly by Linköping University and Politecnico of Milan.)

    Publications
    (As of April 2004)

    Journal Articles
     

  • P. Björklund, P. Värbrand, and D. Yuan, "A Column Generation Method for Spatial TDMA Scheduling in Ad Hoc Networks," Ad Hoc Networks. (In press.)
  • P. Björklund, P. Värbrand, and D. Yuan, "Optimal Frequency Planning in Mobile Networks with Frequency Hopping," Computers and Operations Research. (In press.)
  • L. Brunetta, F. Malucelli, P. Värbrand, and D Yuan, "Joint Optical Network Design, Routing, and Wavelength Assignment by Integer Programming," Telecommunication Systems. (In press.)


    • Chapter in Book
     

  • P. Värbrand, and D. Yuan, "Resource Allocation of Spatial Time Division Multiple Access in Multi-hop Radio Networks," In: Resource Management in Wireless Networking, M. Cardei, I. Cardei, and D.-Z. Zhu, (Eds.) Kluwer Academic Publishers, 2004.


    • Conference Articles
     

  • I.Siomina and D. Yuan, "Load Balancing in WCDMA Networks by Adapting Pilot Power to Traffic Intensity," Proceedings of the International Conference on Computing, Communications and Control Technologies (CCCT 2004), 2004. (To appear in August 2004.)
  • I. Siomina, P. Värbrand, and D. Yuan, "Two Mathematical Programming Approaches for Pilot Power Optimization in WCDMA Networks," Proceedings of 8th World Multi-Conference on Systemic, Cybernetics and Informatices (SCI 2004), 2004. (To appear in July 2004.)
  • J. Grönkvist, J. Nilsson, and D. Yuan, "Throughput of Optimal Spatial Reuse TDMA for Wireless Ad-Hoc Networks," Proceedings of IEEE Vehicular Technology Conference (VTC Spring 2004), 2004. (To appear in May 2004.)
  • P. Björklund, P. Värbrand, and D. Yuan, "A Dynamic Programming Technique for Downlink Bandwidth Allocation in WCDMA Networks," Proceedings of IEEE Vehicular Technology Conference (VTC Spring 2004), 2004. (To appear in May 2004.)
  • I. Siomina, P. Värbrand, and D. Yuan, "Pilot Power Optimization in WCDMA Networks," Proceedings of WiOpt ‘04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, pp. 191-199, 2004.
  • P. Värbrand and D. Yuan, "A Mathematical Programming Approach for Pilot Power Optimization in WCDMA Networks," Proceedings of 2003 Australian Telecommunications, Networks and Applications Conference (ATNAC), 2003.
  • P. Värbrand and D. Yuan, "Throughput Optimization of STDMA in Ad Hoc Networks," Proceedings of the 10th Symposium on Communications and Vehicular Technology in the Benelux (SCVT 2003), 2003.
  • P. Björklund, P. Värbrand, and D. Yuan, "A Simulated Annealing Algorithm for Frequency Assignment in Frequency Hopping GSM Networks," Proceedings of Joint Meeting of the International Conference on Communications and Control Technologies (CCCT '03) and the 9th International Conference on Information Systems Analysis and Synthesis (ISAS '03), pp. 155-160. 2003.
  • P. Björklund, P. Värbrand, and D. Yuan, "Resource Optimization of Spatial TDMA in Ad Hoc Radio Networks: A Column Generation Approach," Proceedings of IEEE INFOCOM 2003, pp. 818-824, 2003.


    • Thesis
     

  • P. Björklund. Two Resource Optimization Applications in Wireless Networks, Licentiate Thesis, Linköping Studies in Science and Technology, Licentiate thesis No 943, 2002.


    • Conference Presentations
  • I. Siomina, "Pilot Power Optimization in WCDMA Networks," WiOpt ‘04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Cambridge, UK, March 2004.
  • I. Siomina, "A Mathematical Programming Approach for Pilot Power Optimization in WCDMA Networks," Australian Telecommunications, Networks and Applications Conference (ATNAC 2003). December 2003.
  • D. Yuan, "Minimum-energy Broadcasting and Multicasting in Ad Hoc Networks: Some Integer Programming Formulations and Computational Experiences," The 3rd Workshop of Italian research projet “Optimization and Simulation in Telecommunications Networks”, Rome, Italy, November 2003.
  • D. Yuan, "Throughput Optimization of STDMA in Ad Hoc Networks," The 10th Symposium on Communications and Vehicular Technology in the Benelux (SCVT '03), Eindhoven, The Netherlands, November 2003.
  • P. Värbrand, "Optimization of Pilot Power in WCDMA Networks,"  The 18th International Symposium on Mathematical Programming, Copenhagen, Denmark, August 2003.
  • D. Yuan, "Scheduling of Spatial Time Division Multiple Access in Multi-hop Radio Networks," The 18th International Symposium on Mathematical Programming, Copenhagen, Denmark, August 2003.
  • P. Björklund, "A Simulated Annealing Algorithm for Frequency Assignment in Frequency Hopping GSM Networks," Joint Meeting of the International Conference on Communications and Control Technologies (CCCT '03) and the 9th International Conference on Information Systems Analysis and Synthesis (ISAS '03), Orlando, Florida, USA, July 2003.
  • P. Värbrand, "Computational Optimization of Pilot Power in UMTS Networks,"  1st International Conference on "Computational Management Science", Chania, Greece, May 2003.
  • D. Yuan, "Maximal Throughput of Spatial TDMA in Ad Hoc Networks," The 3rd Scandinavian Workshop on Wireless Ad-hoc Networks, Stockholm, Sweden, May 2003.
  • D. Yuan, "Resource Optimization of Spatial TDMA in Ad Hoc Radio Networks: A Column Generation Approch," IEEE INFOCOM 2003, San Francisco, California, USA, April 2003.
  • D. Yuan, "An Optimization Approach for Resource Management in Multihop Radio Networks," The sixteenth triennial conference of the International Federation of Operational Research Societies, Edinburgh, UK, July 2002.
  • D. Yuan, "Joint Optical Network Design, Routing and Wavelength Assignment by Integer Programming," The Seventh Meeting of the Nordic Section of the Mathematical Programming Society, Copenhagen, Denmark, November 2001.
  • D. Yuan, "Optimization in Cellular Communication Network Planning with Frequency Hopping," INFORMS Fifth Telecommunications Conference, Boca Raton, Florida, USA, March 2000.
  • D. Yuan, "Optimization in Cellular Mobile Systems: Planning Frequency Hopping GSM Networks," The Third Alio-Euro Workshop on Applied Combinatorial Optimization, Erice, Italy, November 1999.

    •