Dimensioning of a Mobile Phone Network
Contents
Problem description
The figure below represents the typical architecture of a mobile phone network. Every elementary geographical zone or cell is served by a transmitter-receiver called a relay. The calls originating from a mobile phone first pass through these relays. Every relay is connected by cable or electro-magnetic waves to a transit node (hub). One of the hubs controls the network, this is the MTSO (Mobile Telephone Switching Office). A very reliable ring of fiber optic cable connects the hubs and the MTSO with high capacity links. It is capable of re-establishing itself in the case of a breakdown (self-healing ring) and there is no need to replicate it.
At the present state of technology, there are no dynamic connections between the relays and the MTSO. The connections are fixed during the design phase, so it is necessary to choose the nodes of the ring that a relay should be connected to. The number of links between a cell c and the ring is called the diversity of the cell c, denoted by CNCTc. A diversity larger than 1 is recommended for making the system more reliable.
The traffic in this kind of system is entirely digitized, expressed in values equivalent to bidirectional circuits at 64kbps (kilobit per second). This capacity corresponds to the number of simultaneous calls during peak periods. The ring has edges of known capacity CAP. The traffic TRAFc from a cell c is divided into equal parts (TRAFc / CNCTc) among the connections to the ring. This traffic is transmitted via the ring to the MTSO, that then routes it to another cell or to a hub that serves as the interface to the fixed-line telephone network. A relay may be connected directly to the MTSO that also has the functions of an ordinary hub.
We consider a network of 10 cells and a ring of 5 nodes with a capacity of CAP = 48 circuits. The MTSO is at node 5. The following table indicates the traffic, the required number of connections and the cost per connection in thousand $ per cell. For example, cell 1 is connectable with node 1 for a cost of $15,000. Its diversity is 2, which means it must be connected to at least two nodes of the ring. Its traffic capacity is of 22 simultaneous circuits. The objective is to define the connections of the cells to the ring that minimize the connection costs whilst remaining within the capacity limits and satisfying the constraints on the number of connections.
Structure of a mobile phone network
Cell 1 2 connections
Relay ---------\
\
| \
| \
| |
V V hub2 ============ hub3 <-- Relay
cell 2
|| || 1 connection
|| ||
|| ||hub1 === MTSO === hub4
Connection costs, traffic and number of connections per cell
+------------+--+--+--+--+--+--+--+--+--+--+ |Cell | 1| 2| 3| 4| 5| 6| 7| 8| 9|10| +------------+--+--+--+--+--+--+--+--+--+--+ |Hub 1 |15| 9|12|17| 8| 7|19|20|21|25| |Hub 2 | 8|11| 6| 5|22|25|25| 9|22|24| |Hub 3 | 7| 8| 7| 9|21|15|21|15|14|13| |Hub 4 |11| 5|15|18|19| 9|20|18|16| 4| |Hub 5 (MTSO)|10|14|15|24| 6|17|22|25|20|11| +------------+--+--+--+--+--+--+--+--+--+--+ |Traffic |22|12|20|12|15|25|15|14| 8|22| +------------+--+--+--+--+--+--+--+--+--+--+ |Connections | 2| 2| 2| 2| 3| 1| 3| 2| 2| 2| +------------+--+--+--+--+--+--+--+--+--+--+
Variables
hub_mat Matrix describing the hubs traffic Traffic from cells connections Possible connections per cell capacity Capacity
Reference
Applications of optimization... Gueret, Prins, Seveaux
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com % Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.1.0$ % Written Oct 7, 2005. Last modified Mar 8, 2009.
Problem setup
hub_mat = [15 9 12 17 8 7 19 20 21 25;... 8 11 6 5 22 25 25 9 22 24;... 7 8 7 9 21 15 21 15 14 13;... 11 5 15 18 19 9 20 18 16 4;... 10 14 15 24 6 17 22 25 20 11]*1000; traffic = [22 12 20 12 15 25 15 14 8 22]'; connections = [ 2 2 2 2 3 1 3 2 2 2]'; capacity = 48; c = size(hub_mat,2); % Cells n = size(hub_mat,1); % Nodes connect = tom('connect',c,n,'int'); % All variables are binary. bnds = {0 <= connect <= 1}; % Cells connected to minimum nodes con1 = {sum(connect,2) == connections}; % Limits of the ring con2 = {sum((traffic./connections)'*connect(:,1:end-1)) <= 2*capacity}; % Objective objective = sum(sum(hub_mat'.*connect)); constraints = {bnds, con1, con2}; options = struct; options.solver = 'cplex'; options.name = 'Dimensioning of a Mobile Phone Network'; sol = ezsolve(objective,constraints,[],options); PriLev = 1; if PriLev > 0 temp = sol.connect; for ce = 1:c, idx = find(temp(ce,:)); disp(['cell ' num2str(ce) ' connects to hub(s) ' num2str(idx)]) end end % MODIFICATION LOG % % 051108 med Created. % 060116 per Added documentation. % 060126 per Moved disp to end % 090308 med Converted to tomSym
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Dimensioning of a Mobile Phone Network f_k 249000.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 15
cell 1 connects to hub(s) 3 5
cell 2 connects to hub(s) 3 4
cell 3 connects to hub(s) 2 5
cell 4 connects to hub(s) 2 3
cell 5 connects to hub(s) 1 4 5
cell 6 connects to hub(s) 5
cell 7 connects to hub(s) 1 4 5
cell 8 connects to hub(s) 2 3
cell 9 connects to hub(s) 3 5
cell 10 connects to hub(s) 4 5