Parallel simulation of mobile radio network using multiprocessing system, involves programming network elements such that each network element repeats interaction cycle consecutively during simulation

The invention concerns a method for parallel simulation of mobile networks according to the Preamble of claim 1. The method allows parallel simulations on commercial Computers and is capable of parallel simulations means of discrete events in individual apply partitions.

The rapidly increasing demands for a higher and more diverse traffic load in Mobile networks compels operators and system designers to optimize existing networks and completely new solutions for mobile communication systems to develop.

is through the complexity and versatile dynamism inherent in a cellular network However, the design and optimization of these networks is a problem not analytically can be solved.

This applies to future mobile networks in particular. features future Mobile networks can for its topology, the allocation of its resources to individual superior services, thus the superposition of radio signals in the situation change transmission channel in a very dynamic way.

The assessment of quality and capacity of mobile networks is based on a Analysis of mutual superposition of radio signals in the transmission channel. The Radio signals are sent and received from network elements. Use these radio signals the same, characterized by frequency and time, physical resource, so they can superimpose.

A simulative analysis of these overlays of radio signals are the target dynamic Simulations of the radio network level of mobile networks. On the basis of which, the Quality and capacity of a mobile network can be estimated.

Dynamic simulation of the radio network level of mobile networks are thus able to all low-capacity and quality-related aspects of a mobile network in their complexity and the dynamic time course examined.

A simulation is an executable computer program that the under examination system modeled in a sufficient for the purpose of the investigation abstractness.

The generally accepted prior art to control large computer programs the object-oriented principle. Object-oriented programs consist of objects which communicate with each other.

For object-oriented simulation of the radio network level of mobile networks was in J. Deissner, GP Fettweis, J. Fischer, D. Hunold, J. Voigt, R. Lehnert, M. Schweigel and J. Wagner: "Object-Oriented Modeling of a Generic Mobile Radio System for Dynamic Simulation," in Summer Computer Simulation Conference / Symposium on Performance Evaluation of Computer and Telecommunication Systems (SCSC / SPECTS '99), (Chicago, IL, USA), pp. 240-247, 11th-15th July 1999, the object-oriented model of the radio network level of a general cellular network presented.

As important components of a mobile network were analyzed there:

<ul><li>1. The network element.</li><li>2. The transmission channel.</li><li>3. The network element activation.</li></ul>

This said major components of a mobile network are each as an object in a computer program modeled. These objects communicate using Network element external events. communicating objects within a network element by network element-internal events.

From the network element component, it is generally several independent giving properties. The independence of the various network elements modeled objects is justified by the fact that the network element-internal interactions within a Network element completely independent of the network element-internal interactions in another are network element.

The control of cycle of dynamic simulations, however, is not a task of Objects, which on the basis of in J. Deissner, GP Fettweis, J. Fischer, D. Hunold, J. Voigt, R. Lehnert, M. Schweigel and J. Wagner: "Object-Oriented Modeling of a Generic Mobile Radio System for Dynamic Simulation, "in Summer Computer Simulation Conference / Symposium on Performance Evaluation of Computer and Telecommunication System (SCSC / SPECTS '99), (Chicago, IL, USA), pp. 240-247, 11th-15th July 1999 featured object-oriented analysis of the system to be examined in the simulation participate. Therefore has any simulation of (at least), there are two main parts: the simulation controller, which implements one or several simulation methods and a part, which covers implements functionality to be examined Systemes.

Known object-oriented simulators for mobile networks generally operate with a Simulation control means of discrete events. The communication between objects is treated here by events. Events will benefit the actually between the objects Information exchanged a time stamp by which value them in order are rated.

Implementations of this simulation method either work sequentially and are slow or they work in parallel and are then very complex and often require Supercomputer as computer platform.

In a simulation by discrete events corresponding to the <b>Illustration</b> 1 is further disadvantageous in that they require a central event memory, which all in the simulation bring occurring events in a global order relationship.

Other property operating in parallel programs must be partitioned to all distribute computations during simulation on the available number of processors can. The goal of partitioning is a balanced CPU load on all of the Calculations participating processors (the calculations in a single partition be on its own processor running) and low Inter-partition communication traffic.

Known partitioning strategies for simulation programs for mobile networks are to M. and R. Liljenstam Ayani, "Partitioning PCS for Parallel Simulation", in MASCOT ('97) In 1997, the partitioning by geographical area or the partitioning by groups of physical resources in the transmission channel.

In two partitioning strategies is disadvantageous that the model of the transmission channel must be respectively divided. The fact of the existing by the division only once Transmission channel resulting objects must communicate with each other if necessary. This generates additional inter-partition communication traffic.

In the geographical partitioning by <b>Illustration</b> 2 are all network elements of a specific cutout of the simulated region united in a partition.

Disadvantages of this partitioning strategy are:

<ul><li>1. When a movement of the individual network elements is modeled, then here a high Inter-partition communication traffic (a broadcast of the moving Network element modeling object are expected in another partition) when Network elements of a section of the area to be simulated in a different Moving segment.</li><li>2. This partitioning strategy can no longer or only at a very high inter-partition communication traffic (communication between objects, which parts of the transmission channel model) to be applied when the Study area is smaller than the radius propagation of electromagnetic waves.</li></ul>

by When partitioning strategy of separation for resources <b>Illustration</b> 3 are all Network elements in a partition together, which have the same physical resource (or a allocated physical resource which belongs to a defined set of resources) was prepared as a time slot or a frequency.

A disadvantage of this partitioning strategy are:

<ul><li>1. One possible by several causes in the course of operation of the mobile network Reassigning resources causes an inter-partition communication traffic by the transfer of the property to another partition, which comprises a new Resource assigned modeled bekomm network element.</li><li>2. Partitioning by physical resources can no longer be applied, if all network elements send the same physical resource and received. This is in mobile radio standards which code division multiple access as Multiple access scheme using (z. B. UMTS), the case.</li></ul>

The object of the invention is to provide a method of the type mentioned, whereby the control of the sequence of communication of objects as models of Network elements and the transmission channel of a cellular mobile communication system can be efficiently simulated and partitioned into parallel parts.

According to the invention the object is achieved by a method in conjunction with the preamble of claim 1 mentioned features achieved in that the individual network elements of the Mobile network in particular by sending and receiving interaction cycle be programmed and communicate with the transmission channel, wherein a plurality of Send network elements simultaneously independently and receive each Network element the interaction cycle sequentially during simulation repeated the Transmission channel between the sending and receiving states programmed switchable is and switching between the two states on the basis of a comparison of a known number of network elements and the number of the previous sent or information received from a current state takes place in the next state. It is not a central event memory with a global order relationship of all in the Simulation requires occurring events more.

Advantageous variants of the method are the subject of subclaims.

All network elements of a mobile network have access to a common Transmission channel. These requests follow a multiple access scheme, in at a time which is generally more than one network element to access the Transmission channel required. This access scheme limited channel access for Transmissions of a particular network element to one or more of frequency and time marked physical resources.

It has been found that in this case a consecutive repetition of the access to the Network elements takes place on the transmission channel. This behavior in the time domain is present in all digital mobile networks regardless of their multiple access scheme valid. The reason for the architectures of the protocol stack of digital broadcasting in all From cellular networks of the second generation. The fact of the digital transmission is one of the main distinguishing features of the second generation of their predecessors. data be here in shock and further transmitted in time slots. These time slots are in Frame fitted, which are then successively repeated.

The interactions between the objects transmission channel and network elements be modeled advantageous as follows. Network elements have the availability and the release of notify the transmission channel allocated physical resources. These Interactions correspond to the sending of a network element in the real system. Of the Transmission channel then calculates the propagation of radio waves. Then he answers the network element through return all allocations of physical resources and the Signal strength, which received at the current position of the inquiring network element can be and what, z. B. in the case of co-channel interference analysis, the same use physical resources.

Since the interactions for channel access network elements (the network element-external repeat interactions) successively, there is a cycle in the interactions between the transmission channel and the network elements with the points and receiving Send as shown in <b>Illustration</b> . 4

In a variant of the method of transmission channel is strictly passive in the sense that only write network elements to him or receive anything from him. The transmission channel treated these interactions immediately. But he will never with network elements from another Basic interact when responding to interactions of them.

The interactions between the objects transmission channel and network elements in the case a passive object transmission channel modeled as follows. Network elements have the Occupation and the release of allocated physical resources to the notify transmission channel. These interactions correspond to sending a Network element in the real system. In contrast, when a network element information from wishes to receive the transmission channel, it must be due to the passivity of Transmission channel, sending first a reception request to the transmission channel. Of the Transmission channel then calculates the propagation of radio waves. Then he answers to the reception request of the network element through return all assignments physical resources, and the signal strength, which at the current position of requesting network element can be received and which, for. example, in the case of Co-channel interference analysis, use the same physical resources.

Since the interactions for channel access network elements (the network element-external repeat interactions) successively, there is a cycle in the interactions between the transmission channel and the network elements with the points Receive requests, receive responses and send as shown in <b>Illustration</b> . 5

These points of interaction cycle mark time points in the simulation time. By Independence of the network elements is the order of the communication between the different objects network element at a time of the interaction cycle indefinitely. In plain language this means that sending of many network elements first or receiving, is undetermined. Determines is only the order of the points in the cycle of interaction (receiving - Send or receive request - reception response - sending). By indeterminacy the sequence of communication between different objects network element at a time the interaction cycle has no global definition relation of all communications in the Simulation are respected. In contrast, compliance is a global Order relation as in simulations using discrete events prior Technology a overspecification the model.

The interaction cycle repeats with each frame or super-frame of about examined mobile radio system. The simulation time can then be measured by by only the number of cycles counted and interaction with the length of the selected Frame duration is multiplied.

Through the interaction cycle found the sequence of communications between the objects network element and transmission channel now known in advance (Succession of instants of the interaction cycle or sequence of individual Interaction cycles) or partially undefined (different network elements to a Time). This has no global definition relation by an event memory be respected.

According to the invention has, in contrast exactly one object in the executable model of the new Domain for scheduling a special task. In the case of an executable model of the Radio network layer of a mobile network, the object that the transmission channel modeled, assume the following reasons the sequencer. It is then the only Object which:

<ul><li>- Working with the global time,</li><li>- Has only a single instance of the model and</li><li>- Participates in each cycle of interaction.</li></ul>

It is proposed as inventive partitioning strategy, all network elements of the same type, regardless of their current location and regardless of the assigned to unite physical resource in a partition (partitioning on the type of Network element). As an immediate advantage of this never occurs inter-partition communication traffic upon movement of a network element or reallocation of a physical resource on. The advantage of this partitioning strategy remains that they also in geographical Simulation territories, which are smaller than the dispersion area of ​​the radio waves as well as Mobile networks with only one physical resource partitioning of the entire Simulation model in the first place allow.

In a partition so multiple objects network element are united. The communication of this Objects within the partition, and the network element-internal communications may by the prior art are controlled by means of discrete events.

In a further variant of the method, the activation of the network elements and Services initiated during the simulation run of random functions, which also Timing and length of life of a network element or service determined. The Network element activation generates interarrival and service times which time the and determine the lifetime of a network element in the executable model. In plain language they are the information from, when and for how long a network element of a particular type is part of the model topology. The interactions between the network element and activation the network elements have a fine relationship with the interactions between the Network elements and the transmission channel. They must therefore with the same Order relationship are treated. They have, however, in contrast to successive channel access, a random behavior.

It is in this case to ensure that the interactions of the interaction during the cycle in correct sequence to be performed. Here are in particular the randomly occurring Configuration events which are issued by the network element activation, in a Fine relationship with the interactions between the transmission channel and the classify network elements.

These can be found that an interaction cycle is complete when all Network elements the assignments of resources for the next cycle of interaction in point Send have announced the transmission channel. Only then can the transmission channel start the calculations for receiving replies or new receiving requests accept. Would receiving responses are calculated, if not all Interactions in point sending have been processed, then is a causality in Resource availability can not be guaranteed and the receiving answers would not exact Overlay situation of radio signals in the transmission channel at the time of the current Interaction cycle reflect. Therefore, must be guaranteed in the execution that the first is only then output exactly reception response from the transmission channel, if all Interactions in point sending been processed in the transmission channel and all Receive requests were sent from all network elements. The otherwise independent apart running simulations in the objects transmission channel and network elements must meet exactly at this point. On the other hand, the network elements interactions transmitted to the transmitting and receiving points requirement at any point in the cycle, after receiving the reception response. The sequencing of the simulation itself ensure that these interactions are processed in the correct order.

The invention is explained in more detail with reference to working examples. In the associated drawings:

<b>Illustration</b> 1 is a diagram illustrating of discrete events,

<b>Illustration</b> 2 is a diagram illustrating geographical partitioning,

<b>Illustration</b> 3 is a diagram illustrating partitioning according to the resources,

<b>Illustration</b> 4 is an illustration for illustrating the method according to the invention,

<b>Illustration</b> 5 is an illustration of the process in passivity of the transmission channel,

<b>Illustration</b> 6 is an illustration of a partitioning of the invention,

<b>Illustration</b> 7 is an illustration of passivity of the transmission channel with Activation events,

<b>Illustration</b> 8 is an illustration of the saving of computation time when using the Simulation method according to the invention on a multiprocessor computer.

The <b>Illustration</b> 1 to 3 are illustrative of the prior art and there are have already been explained in more detail.

As an exemplary example of the interaction cycle, in the GSM system, eight time slots the duration 0.577 ms transferred 4,615 ms in a frame of time. It now depends on the desired time resolution of the simulation of the radio network level from which period as Basic element of the interaction cycle is used. When implemented in a Simulator for the GSM radio network layer is the frame duration of 4.615 ms as a basic element used. This use has the advantage that each active network element on each Interaction cycle participates because each active network element of the eight timeslots must be assigned.

As embodiment for implementing the invention is a self in the flow described controlling variation of the simulation of the radio network layer of a mobile network will.

A good way to describe a model of a system, whose parts act in parallel, but must interact with each other, is to use the notations of process calculi, z. B. the Communicating Sequential Processes (CSP), the Calculus of Communicating Systems (CCS). Process calculi are formal algebra for describing only interacting Parts of a system. These parts are generally called processes. Everything happens within a process, is not seen from the outside and not considered.

CSP uses interactions from Rendezvous style, or, in other words, considering all Interactions than synchronously. That is, an interaction between processes can only take place, when all participating objects (transmitter and receiver) are ready. When one of the Objects is not ready to interact, then all other objects have to wait (the objects be blocked).

In contrast, the sender of a message in an asynchronous interaction must not Wait until the receiver is ready to receive the message because the message is from buffered interaction until the receiver is ready. This means, however, whenever a Receiver wants to receive something, but the station is not ready for interaction, then the receiver must wait (the receiving object is blocked).

Synchronous and asynchronous rendezvous interactions can be used now to the Communications between objects transmission channel, the network elements and the to describe network element activation.

The first step in the description of a system with the use of process-calculus Notation is the definition of an interaction alphabet. Since all internal calculations of Object are completely hidden inside, an object is fully through his interaction Alphabet described. The interactions in the radio network layer of a mobile network can be used in two Groups are divided:

<ul><li>1. The points of interaction cycle.</li><li>2. The interaction of the network element activation randomly occurring.</li></ul>

The communications between the said objects can now utilizing the be implemented knowledge of the sequence of the cycle of interaction as follows.

It is assumed that each J (z) network elements are active in the interaction cycle z. Then the following communications are possible:

<ul><li>1. For the first J (z) - 1 network elements for all points of interaction cycle (Communications reception request - reception response - sending and receiving - Send): asynchronous rendezvous interactions. Reason: The network elements are independently, to the order of their interactions with the transmission channel a time of interaction cycle is undetermined.</li><li>2. For the network element J (z) for all listed points of interaction cycle: synchronous Rendezvous interactions. Justification: According to the order of points must the interaction cycle are respected. For this purpose, each per cycle of interaction a Information required if the per point last network element its communication has performed. This information may, for. Example by internal counter in the expiry controlling object transmission channel are supplied.</li><li>3. by the interactions of the network element activation break <b>Illustration</b> 7 in the Interaction cycle. These breakpoints need from the object Transmission channel are planned, since this object according to the invention the end of the Simulation controls.</li></ul>

As embodiment for implementing the invention was Simulation control implemented on the basis of PtolemyII 0.3 UC Berkeley. PtolemyII is a library for heterogeneous concurrent modeling and design, which written entirely in the Java programming language and released to the public has been. It provides a general program of infrastructure that can be used to executable models of heterogeneous systems under the use of a variety of to implement simulation methods. The semantics of a specific simulation method is in a so-called domain implemented, which is capable of a model of a perform system under the use of this particular simulation method. Furthermore, the program PtolemyII infrastructure allows hierarchical models composed of a System, the execution of which different domains and thus simulation methods includes.

To implement the simulation of control of the invention, a new domain has been created for PtolemyII. This domain allows synchronous and asynchronous and Breakpoint-based interactions Objects, which are referred to in the terminology of PtolemyII as actuators.

This simulation control was used to the simulation of a mobile radio network with a to control UMTS UTRA / FDD air interface.

In the following tests the new domain as a simulation control for used network element external communications, while a sequential Simulation control means of discrete events for the network element-internal Communications and for communications within the partitions used. This total hierarchical simulation control is a consistently sequential Simulation control means of discrete events on different computer platforms tested.

The performance of both simulation controls on a computer with two processors compared:A SunOS 5.6 sun4u sparc SUNW, Ultra-2 computer with 300 MHz clock rate and Solaris VM JDK1.2.1.02, native threads, sunwjit benutzend. The results are in<b>Illustration</b> shown. 8

In this multi-processor computer, the heterogeneous simulation control results in faster Simulations.