Publications of the project

Software Tools for the Optimization of Resources in Mobile Systems
Keywords Researchers
Parallel programming, combinatorial optimization, mobile telecommunication, object-oriented design and programming. Dr. Pierre Kuonen (project leader), Dr. Frédéric Guidec, Patrice Calégari (Ph.D. student), Mahmoud El Husseini.
Project period Funding Agency
September 1995 - December 1999. European ACTS project, funded by the European Community and by the Swiss government (OFES grant 95.0203).
Description
STORMS is a project of the 4th European ACTS program:
  • ACTS: Advanced Communication Technologies and Services.
  • Area 4: Mobility and Personal Communication.
  • Task AC414: Mobile Communication Network Design and Engineering.
This project implies 12 partners, including the GRIP and SwissCom. The most qualifying objective of STORMS consists in the definition, implementation and validation of a software tool to be used for automated design and planning of optimal mobile telecommunication networks.
The GRIP is the leader of WorkPackage 7 (Software Integration and Interfaces), whose goal is to define the global architecture of the whole software under construction. This activity notably implies the global design of the application, the identification of the main software components, the specification of the data structures that must be shared by these components, and the collection of testbed data.
The whole application is to be developed using object-oriented techniques. The analysis and design phases are achieved using the Fusion method, while the software components are coded in C++. As the leader of WP7, the GRIP has already produced several reports for the European Community, as well as technical documents intended for STORMS partners.
The GRIP is also strongly implied in the realization of WorkPackage 4 (Radio Engineering). This is the core of the whole application. Combinatorial optimization methods must be developed at this level, permitting the computation of optimal locations for base transceiver stations (BTSs) in urban or inter-urban environment. Combinatorial problems arise from the many possible configurations of BTSs (power, orientation, polarization, height...) as well as from the many criteria to select a good site. The GRIP must develop parallel algorithms to solve this problem efficiently. It has been shown that promising solutions can be found considering stable and dominating set problems in graph theory.
The GRIP also participates in WorkPackage 3 (Propagation Tool), whose objective is to produce software components for predicting the shape of the cells covered by BTSs. More specifically, the GRIP is developing ParFlow++, a parallel object-oriented implementation of the ParFlow method, which permits wave propagation simulation using a digital city map and assuming infinite building height. Because the ParFlow method does not allow for waves propagating through buildings, the original ParFlow algorithm was fully redesigned so that ParFlow++ operates on an irregular data structure that models only the outdoor parts of a city district. By implementing the ParFlow method on a parallel platform, we can speedup wave propagation predictions and make bigger problems tractable. The platforms primarily targeted at in the STORMS project are the Cray T3D supercomputer, and networks of Unix workstations. Yet, ParFlow++ was developed so as to be easily portable on any other MIMD-DM platform. A prototype sequential version of ParFlow++ was delivered to the STORMS project leaders in August 1996. Since then parallel versions of ParFlow++ have been ported and tested successfully on several medium to tightly coupled parallel platforms, including networks and clusters of workstations, as well as EPFL’s MIMD platforms (e.g., Cray T3D, SGI Origin 2000, SCS Swiss-Tx).
The software tools developed jointly by the GRIP, the Trinitiy College of Dublin, and the French company TDF (Télé-Diffusion de France) within the WP3 and WP4 frameworks of the STORMS project cover a wide range of functions, including radio wave propagation simulation, network coverage modelling, transceiver siting optimization, and radio interference prediction. Most of the algorithms used in these tools exhibit a high computational complexity, and require access to huge amounts of data. This is the reason why the GRIP is now in the process of integrating the greediest of these tools in a ‘meta-computing’ heterogeneous parallel platform. This platform shall eventually be available to any user in the STORMS project through a Web interface. It will transparently speed up mobile network planning by using the high computational power offered by tens or hundreds of worsktations, together with one or several MIMD supercomputers (e.g., Cray T3D, SGI Origin 2000, Swiss-Tx).

Publications
Kuonen P., Josselin S. and Wagner D., Ubéda S., Parallel Network Coverage Simulation Application, In Second European PVM Users Group Meeting (EuropPVM'95), Lyon, France, September 1995.
Kuonen P., Josselin S. and Wagner D., Ubéda S., Parallel Computing of Radio Coverage, in IEEE-VTC (Vehicular Technology Conference), Atlanta, May 1996.
Calégari P., Guidec F., and Kuonen P., A Parallel Genetic Approach to Transceiver Placement Optimisation, in Proceedings of the SIPAR Workshop’96: Parallel and Distributed Systems, C.-A. Héritier and B. Chopard, Eds., pp. 21-24, October 1996.
Calégari P., Guidec F., Kuonen P., Chamaret B., Josselin S., Wagner D., and Pizarosso M., Radio Network Planning with Combinatorial Optimization Algorithms, in Proceedings of the 1st ACTS Mobile Telecommunications Summit 96, Chr. Christensen, Ed., vol. 2, pp. 707-713, November 1996.
Guidec F., Kuonen P., and Calégari P., ParFlow++: a C++ Parallel Application for Wave Propagation Simulation, SPEEDUP, Proceedings of the 20th SPEEDUP Meeting, vol. 10, no. 1/2, pp. 68-73, December 1996.
Guidec F., Calégari P., and Kuonen P., Parallel Irregular Software for Wave Propagation Simulation, in High-Performance Computing and Networking (HPCN Europe’97, Vienna), Lecture Notes in Computer Science, Hertzberger and Sloot, Eds. Apr. 1997, vol. 1225 of Lecture Notes in Computer Science, pp. 84-94, Springer Verlag, April 1997.
Calégari P., Kuonen P., Guidec F., and Wagner D., A Genetic Approach to Radio Network Optimization for Mobile Systems, in Proceedings of the IEEE 47th Vehicular Technology Conference (VTC), IEEE, Ed., vol. 2 of Technology in Motion, pp. 755-759, May 1997.
Guidec F., Calégari P., and Kuonen P., Object-Oriented Parallel Software for Radio Wave Propagation Simulation in Urban Environment, in EuroPar’97 Parallel Processing (Third International EuroPar Conference, Passau, Germany, August 1997, Proceedings), S. Lengauer, M. Griebl, and S. Gorlatch, Eds., vol. 1300 of Lecture Notes in Computer Science, pp. 832-839, Springer, September 1997.
Calégari P., Guidec F., and Kuonen P., Urban Radio Network Planning for Mobile Phones, EPFL Supercomputing Review, vol. 9, pp. 4-10, November 1997.
Guidec F., Calégari P., Kuonen P., and Pahud M., ParFlow++: a parallel irregular radio wave propagation simulation code, Technical report 98/260, Swiss Federal institute of Tehcnology (EPFL), Computer Science Department, January 1998.
Guidec F., Kuonen P., and Calégari P., Radio Wave Propagation Simulation on the Cray T3D, in Proceedings of ParCo’97, Bonn. 1998, Parallel Computing: Fundamentals, Applications and New Directions, E.H. D'Hollander, G.R. Joubert, F.J. Peters, and U. Trottenberg, Eds., vol. 12 of Advances in parallel computing, pp. 155-162, Elsevier Science B.V., ISBN 0-444-82882-6, 1998.
Guidec F., Calégari P., and Kuonen P., Parallel irregular software for wave propagation simulation, Future Generation Computer Systems (FGCS), N.H. Elsevier, vol. 13, no. 4-5, pp. 279-289, ISSN 0167-739X, March 1998.
Kuonen P., Guidec F., and Calégari P., Multilevel Parallelism applied to the optimization of mobile networks, in Proceedings of the High-Performance Computing (HPC'98), A.Tentner, Boston, Ed., pp. 277-282, Society for Computer Simulation International, ISBN:1 56555 145 1. April 1998.
Menolascino R., Cullen P., Demestichas P., Josselin S., Kuonen P., Markoulidakis Y., Pizzaroso M., Zeghlache D., A Realistic UMTS Planning Exercise, 3rd ACTS Mobile Communication SUMMIT'98, Vol.1, pp. 157-162, Rhodes, Greece, 8-11, June 1998.
Guidec F., Calégari P., Kuonen P., and Pahud M., Object-Oriented Parallel Software for Parallel Radio Wave Propagation Simulation in Urban Environment, Computers and Artifical Intelligenc, Slovak Academy of Sciences, 1998.