Stochastic network analysis for the design of self optimising cellular mobile communications systems
Stochastic network analysis for the design of self optimising cellular mobile communications systems
A project shared by the Universiteit van Amsterdam, department of Operations Research and Management (prof.dr N.M. van Dijk), Vrije Universiteit Amsterdam, department of Econometrics, Eindhoven University of Technology, department of Applied Mathematics (prof.dr.ir O.J. Boxma), and the University of Twente, faculty of Mathematical Sciences (dr R.J. Boucherie), funded by the Technology Foundation STW, applied science division of NWO and the Ministry of Economic affairs, the Netherlands, project manager dr R.J. Boucherie (firstname.lastname@example.org).
Summary of research proposal
The penetration of mobile communications systems, and the number of services (e.g. voice, data, Internet) offered by mobile operators, are increasing at impressive speed. Accommodating these heterogeneous services at sufficient quality of service within the severely limited capacity assigned to mobile networks requires pricing rules, call admission control strategies, and capacity re-allocation protocols, that take into account the intricate relation between mobility of subscribers and the characteristics of the telecommunications network. Performance analysis and modelling yields the deep insight essential for the optimal design of future networks, which requires bridging the gap between distinct methods developed in economical theory, teletraffic engineering, electrical engineering, and road traffic control. Combining this wide range of methods into implementable strategies is of mutual benefit for telecommunications and for road traffic management. The development of third generation wireless networks provides a new technological challenge. The project Stochastic network analysis for the design of self optimising cellular mobile networks aims to extend the performance analysis results for second generation networks towards modelling and analysis of third generation networks, which is of the utmost importance for technological and economical development of future networks.
Telecommunications will affect every facet of our lives and will become a key driver for economic growth and innovation in the next decades. Moreover, with the introduction of new services such as mobile Internet, on-line road traffic information and stock exchange rates, but also advanced technological applications such as remote medical services, mobile and personal communications systems will play a major role in the due to the information technology rapidly changing society.
In contrast with the extreme importance of mobile communications for economic growth, optimisation of network performance is generally not taken into account in the development of new standards. For example, projects evaluating performance of (future) mobile systems are omitted in the European ACTS programme , and in the Telematica Instituut . Exploring and developing operations research techniques may enable a substantial improvement not only of current systems, but most importantly of future systems: design and management of complicated systems accommodating multiple services requires the deep insight into the system at global and detailed level provided by the results and methods highlighted in the present research project. As future systems involve multibillion euro investments and yearly expenses, operations research methods for mobile networks potentially have a huge economical and technological impact.
Stochastic analysis of mobile communications proposed in this project provides a unique opportunity for both incorporating operations research methods in the design of these systems and for communicating the research problems of mobile systems to the operations research community. Although these problems are related to those in the telecommunications area in general, the specific questions arising in cellular mobile open a rich field of extremely challenging research problems. The track record of operations research within telecommunications indicates that results are being widely applied, which will most certainly also hold for results of this project.
2. Mobile network
The rapid growth of mobile communications both from the perspective of the number of subscribers, and services induces a migration from second generation voice oriented GSM (Global System for Mobile communications), where voice and data calls occupy a single channel, via GSM/HSCSD (High-Speed Circuit-Switched Data, in 2000), and GSM/GPRS (General Packet Radio Service, in 2000--2001), where data calls may simultaneously utilise and share multiple channels, to third generation UMTS (Universal Mobile Telecommunications System, expected in 2002--2003) . In contrast with GSM-based networks, where the frequency band is divided into separate frequencies that are time-sliced into channels, in UMTS each transmission utilizes an entire frequency band. Interference is suppressed via pseudo-orthogonal coding of the transmissions. UMTS allows for broadband communications particularly suitable for data applications, and will be implemented on a separate set of frequencies next to GSM.
In clear contrast to this rapid development, capacity (channels or codes) available for mobile networks is severely limited, and increases only at discrete steps (e.g. auctions of bandwidth). Also with additional frequencies, however, capacity is insufficient to accommodate demand. To increase the network capacity, the area covered by a provider is divided into cells served by cell-transceivers transmitting at limited power. Avoiding interference, capacity can then be re-used in multiple cells, which increases network capacity, but imposes important problems for the network performance via call-interruptions. Besides the obvious loss of fresh calls due to a lack of channels at the start of a call, especially the lost handovers due to calls moving to cells that already are fully occupied result in a degradation of the quality of service of the network. In addition, mobility influences the capacity required in the cells: in a traffic jam subscribers use channels of a cell for a longer period, and might more frequently make a call. Evaluation of loss probabilities and related performance measures requires the combined analysis of telecommunications models for channel-availability, and of traffic models for subscriber-mobility.
3. Research project
The aim of the project is the creation of a mobile communications research centre for development, and implementation of models for prediction, and improvement of the quality of service in mobile networks. In cooperation with industrial and academic partners, mobility of subscribers and the telecommunications network will be captured in a unifying framework.
Performance analysis of mobile networks has been carried out in the project `Stochastic network analysis for the design and implementation of self optimising cellular mobile communications systems'. On the one hand, integrating road traffic and queueing models, a formalism has been developed that captures mobility and teletraffic aspects of voice calls , and protocols for capacity to follow peak demand (e.g. due to a traffic jam) are being developed . On the other hand, for single cell models (ignoring mobility) that allow for voice and (multiple priority) data, channel allocation protocols have been developed for GSM/HSCSD , and GSM/GPRS .
Current research has pushed the theory for wireless networks towards the boundary of queueing type models, and has identified key properties of second and third generation networks. The clear distinction between GSM, where the number of calls in a cell is sufficient for performance analysis, and UMTS, where the exact location of all calls within the cells is required, prohibits application of queueing models for performance analysis of UMTS. Moreover, new services not only have different call and mobility characteristics, but also have inhomogeneous capacity and quality of service requirements: data is delay tolerant, video requires a minimal bit-rate, whereas medical services are delay and error intolerant. Dimensioning of UMTS requires a new theoretical and practical framework that takes into account location, mobility, and call characteristics.
The project aims for combining and unifying network characteristics, and has the potential to play an important role in the future development of methods and techniques for advanced GSM and UMTS networks. For the network developments that are foreseen for the next decades, key-items for research include the topics further described below.
3.1. Pricing of services
Mixing services with distinct characteristics and revenue requires pricing and priority rules to accommodate these services at sufficient quality of service (comprised of transmission quality and speed, call acceptance and interruption rate), but also to optimise the revenue for the service provider. As different services result in stochastically distinct call properties, development and analysis of pricing and priority rules cannot be based on queueing models such as available for GSM. For the Internet, pricing rules have been developed based on game-theoretical models that take into account the characteristics of different services . Such models are not directly applicable to mobile networks as interference between transmissions and mobility of subscribers explicitly influences the cell capacity absorbed by a transmission. However, such initial results do provide a starting point for the development of stochastic models and pricing rules that adequately take into account movement of subscribers with different call characteristics.
3.2. Prediction and monitoring of mean subscriber locations
Evaluation and prediction of subscriber-mobility is possible, based on fluid traffic models that describe the average behaviour of traffic . On the one hand, for highways in the Netherlands, monitoring of all vehicles passing detection loops placed at distances of approximately 500 metres enables 10 minutes ahead of time prediction of the average location of traffic, that will (in the near future) be applied to reduce traffic jams. On the other hand, during a call a mobile terminal performs and reports field strength measurements of the surrounding cell-transceivers at 0.48 second intervals, which enables an accurate determination of its location. In a novel approach, combining the inaccurate (observed at long intervals) location information for all subscribers passing detection loops with the accurate location information for the small subset of subscribers making a call, using e.g. statistical methods such as Kalman filtering to smooth the observed data, an improved road traffic prediction system will be investigated that is beneficial for both the road traffic management system and the mobile communications network.
3.3. Stochastic models for user location
Call admission control to discriminate between services, and to protect handovers is based on short-term behaviour (minutes or seconds) that is not determined by the average behaviour obtained via fluid models, but by fluctuations and the precise location of individual subscribers both determined by stochastic processes in the traffic network underlying the cellular network: short term variations in the number of calls may lead to an intolerably large number of handover interruptions. Moreover, in contrast with GSM, where the number of calls determines the remaining capacity of the cells, in UMTS, due to the coding scheme, the exact location of subscribers within the cells is required to determine the remaining capacity. As a consequence, the characteristics of the distribution of subscribers within the cells (e.g. homogeneous or clustered) strongly influences the capacity of the network. Modelling the exact user location while taking into account call characteristics is possible using spatial marked point processes . However, although a description of a static pattern is facilitated by this theory, movement of points in spatial point processes is an important open problem for research.
3.4. Call length models
Observing the mean call length or mean cell-transceiver connection time is a typical feature of mobile networks. In contrast, stochastic models for subscriber location and call behaviour usually require the distribution of the call length or connection time that is not available in mobile networks. For queueing network models of GSM, insensitivity results have been developed under which the relevant performance measures depend on these distributions only through their mean, which enables determining the quality of service through network parameters that can be measured in the current network . Further development of (approximate) insensitivity results for networks that are shared by different services is of the utmost importance for the applicability of stochastic network results to mobile networks.
3.5. Dynamic capacity allocation and call admission control
Allocation of channels or codes to the cells of the network, and to subscribers within the cells is an important aspect of cellular mobile networks. Capacity allocation and call admission control rules clearly must take into account call length characteristics (3.4), pricing rules (3.1), user locations (3.2), and interference constraints (3.3). Different allocation protocols are used. For example, in GSM, fixed channel allocation uses a static assignment of channels to (groups of) cells, whereas dynamic channel allocation assigns channels to cells upon request (within interference restrictions).
With an increasing number of subscribers and services, and growing mobility of users, some areas can be temporarily overloaded. Such areas (hot spots) move around in the network, for example due to busy traffic in rush hours. Optimal allocation of capacity to hot spots following a dynamic strategy requires complete information on the state of the network, which introduces extreme overhead, and results in re-allocation strategies too slow to follow movement of hot spots. For implementable (fast) strategies, the trade-off between clear improvement of network performance while maintaining acceptable overhead can be made on the basis of insight into the network behaviour obtained through projects 3.1 -- 3.4. Design of implementable call admission control rules is of both theoretical and economical interest, and is a driving force of the project.
4. Methods and techniques
Methods for analysis of cellular mobile networks are adopted from the theory of stochastic processes. In particular, a combination of queueing networks , road traffic models , and spatial marked point processes , is required for modelling and analysis of the distribution of subscribers over the network, and of acceptance and delay probabilities. Capacity allocation, pricing, and call admission control rules can be studied using e.g. results and techniques from Markov decision theory and game theory. Statistical and econometrical methods such as Kalman filtering and time series analysis are required to incorporate empirical data.
Computational methods are required for obtaining performance measures. These methods can be developed by analogy with methods for telecommunications and queueing networks. Approximate techniques such as stochastic majorization and error-bounds will be used for obtaining upper and lower bounds on performance measures. Numerical techniques such as approximate mean value analysis available for queueing networks and fixed-point methods available for loss networks can be modified to cope with the cellular network environment. Asymptotical methods such as large deviations techniques will be used to approximate loss probabilities. Simulation will be employed to analyse small network parts in detail.
Technological changes within the mobile network architecture follow each other at impressive speed. For research to remain at the fore front of technological developments, a deep insight into the system is required both at a theoretical level identifying the behaviour of the system, and at a practical level, enabling integration of new services into the network at sufficient quality of service. The project aims for establishing a mobile communications research centre for integrating economical theory, electrical engineering, teletraffic engineering, and road traffic theory to improve the efficiency of mobile networks for accommodating heterogeneous services. The rich field of open problems explored by the project will most certainly lead to theoretical contributions and practically implementable results with the potential to have a huge impact on the way mobile communications networks will function in the near future.
1. Overview of ACTS (Advanced Communications Technologies and Services) is provided at http://www.cordis.lu/acts/home.html.
2. Overview research projects of the Telematica Instituut at the University of Twenty is provided at http://www.telin.nl/Projecten/index.htm.
3. Standardisation documents and information on the `Third Generation Partnership Project' 3GPP are provided at http://www.etsi.org.
4. Bin Ran and D. Boyce . Modeling dynamic transportation networks. (2nd revised ed.) Springer-Verlag.
5. Frey and V. Schmidt . Marked point processes in the plane I, II, a survey with applications to spatial modelling of communications networks. Advances in Performance Analysis 1, 65--110, 2, 171--214.
6. J.M. Holtzman (Editor) . Wireless information networks.; J.M. Holtzman and M. Zorzi (Editors) . Advances in wireless communications. Kluwer Academic Publishers.
7. R.J. Gibbens and F.P. Kelly . Resource pricing and the evolution of congestion control. To appear: Automatica 35 http://www.statslab.cam.ac.uk/~frank/evol.html.
8. J.P.M.G. Linnartz (Editor) . Wireless Communication, the interactive multi-media CD ROM. Baltzer.
9. R. Prasad et al. . Third generation mobile communications systems. Artech House.
10. R. Serfozo . Introduction to stochastic networks. Springer-Verlag.
11. Shwartz and A. Weiss . Large deviations for performance analysis: queues, communications, and computing. Chapman & Hall.
7. Results of the project
12. R.J. Boucherie and N.M. van Dijk . On a queueing network model for cellular mobile communications networks. Operations Research 48, 38-49.
13. R. Litjens and R.J. Boucherie . Evolutie van mobiele cellulaire telecommunicatie netwerken. Proceedings Symposium Wiskunde Toegepast, Universiteit Maastricht, 27 april 2000.
14. S.C. Verwijmeren, M. Mandjes and R.J. Boucherie . Asymptotic evaluation of blocking probabilities in a hierarchical cellular mobile network. Probability in the Engineering and Informational Sciences 14, 81-99.
15. R. Litjens and R.J. Boucherie . Radio resource sharing an a GSM/GPRS network. In: Proceedings ITC Specialists Seminar on Mobile Systems and Mobility, March 22-24, Lillehammer, Norway, P.J. Emstad (Editor) pp. 261--274, 2000.
16. R. Litjens and R.J. Boucherie . Performance analysis of fair
17. channel sharing policies in an integrated GSM/HSCSD network. Report AE 4/99, Institute of Actuarial Sciences & Econometrics, Universiteit van Amsterdam.
18. R.J. Boucherie and O.V. Ivnitski . Error bounds for a redial rate approximation of wireless networks under fixed channel allocation. In: Proceedings of the fifteenth Belarussian winter workshop on queueing theory, 21-25 June 1999, Minsk, Belarus.
19. S.C. Borst, R.J. Boucherie and O.J. Boxma . ERMR: A generalised Equivalent Random Method for overflow systems with Repacking. In: Teletraffic Engineering in a Competitive World, Proceedings of the International Teletraffic Congress -- ITC-16, Edinburgh International Conference Centre, United Kingdom, 7--11 June 1999, P. Key and D. Smith (Editors) pp. 313--323.
20. R.J. Boucherie and M. Mandjes . Estimation of performance measures for product form cellular mobile communications networks. Telecommunication Systems 10, 321-354.
21. R.J. Boucherie . Cellulaire mobiele communicatie vanuit een stochastische invalshoek. In: Van frictie tot wetenschap, jaarboek 1997, Vereniging van Akademie-onderzoekers, pp. 19-23.
22. R.J. Boucherie . Stochastic network analysis of cellular mobile networks. Proceedings Symposium Wiskunde Toegepast, 33e Nederlands Mathematisch Congres, 16 april 1998, Universiteit Twente.
23. R.J. Boucherie . An insensitive queueing model for cellular networks. Dagstuhl proceedings - Modelling of communications networks via stochastic geometry, Schloss Dagstuhl, 25-28 maart 1998.
8. In preparation; current research
23. N. Abdalla and R.J. Boucherie . Blocking probabilities in mobile communications networks with time-varying rates.
24. R.J. Boucherie, N.M. van Dijk and J. van der Wal . Error bounds for a redial rate approximation of wireless networks.
25. R.J. Boucherie, M. Mandjes and S. Verwijmeren . Computational methods for layered cellular mobile communications networks.
26. R. Litjens and R.J. Boucherie . QoS differentiation in an integrated GSM/GPRS network.
27. R. Litjens and R.J. Boucherie . Heavy tailed data connections in mobile networks.
28. R. Litjens and R.J. Boucherie . Call admission control in GPRS networks.
29. Ule and R.J. Boucherie . A note on the distribution of customers in a wireless network with fluid traffic.
30. Ule and R.J. Boucherie . Channel borrowing in GSM networks.