Scheduling of Telecommunications Via Satellite
Contents
Problem description
A digital telecommunications system via satellite consists of a satellite and a set of stations on earth which serve as interfaces with the terrestrial network. With SS-TDMA (Satellite-Switch, Time Division Multiple Access) access technology, the satellite divides its time among the stations. Consider for example the transmissions from four transmitter stations in the US to four receiver stations in Europe. The following table gives a possible 4 × 4 traffic matrix. TRAFtr is the quantity of data transmitted from station t to station r. It is expressed in seconds of transmission duration, because all lines have the same constant transmission rate.
Matrix TRAF with its lower bound LB
+----+--+--+--+--+-------+ |TRAF| 1| 2| 3| 4| rowt | +----+--+--+--+--+-------+ | 1 | 0| 7|11|15| 33 | | 2 |15| 8|13| 9| 45 | | 3 |17|12| 6|10| 45 | | 4 | 6|13|15| 4| 38 | +----+--+--+--+--+-------+ |colr|38|40|45|38|LB = 45| +----+--+--+--+--+-------+
The satellite has a switch that allows any permutation between the four transmitters and the four receivers. The figure below gives an example of a permutation connecting the transmitters 1 to 4 to the receivers 3, 4, 1, and 2 respectively. These connections allow routing a part of the traffic matrix, called a mode. A part of a matrix entry transmitted during a mode is a packet of data. A mode is thus a 4 × 4 matrix M with at most one non-zero packet per row and column and such that Mtr <= TRAFtr for all t, r. To every mode corresponds a slice of a schedule as shown in the figure.
+----+--+--+--+--+ +---------+---------------+ |TRAF| 1| 2| 3| 4| |Stations | Packets | +----+--+--+--+--+ +---------+---------------+ | 1 | 0| 0|11| 0| | 1 --> 3 |-----11---> | | 2 | 0| 0| 0| 9| | 2 --> 4 |------9-> | | 3 |15| 0| 0| 0| | 3 --> 1 |-----15------->| | 4 | 0|13| 0| 0| | 4 --> 2 |-----13-----> | +----+--+--+--+--+ +---------+---------------+ |colr|38|40|45|38|LB = 45 +----+--+--+--+--+
Example of a mode and associated schedule
A valid schedule of transmissions defines a sequence of permutations for the on-board switch that routes all the traffic of the matrix TRAF. In other words, this boils down to decomposing TRAF into a sum of mode matrices. An element of TRAF may be fragmented, like TRAF31 that is only partially transmitted in the mode represented in the figure above. A fragmented element will appear in several packets and several modes of the final decomposition. The duration of a mode is the length of its longest packet. The objective is to find a schedule with minimal total duration.
Variables
traffic A matrix describing the traffic
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.2.0$ % Written Oct 7, 2005. Last modified Apr 8, 2009.
Problem setup
PriLev = 1; if PriLev > 0 % if: PriLev > 0 sequence = []; % then: let us catch all x_k pmins = []; end traffic = [ 0 7 11 15;... 15 8 13 9;... 17 12 6 10;... 6 13 15 4]; n1 = size(traffic, 1); rowsum = sum(traffic,1); colsum = sum(traffic,2); LB = max(max([rowsum;colsum'])); q = zeros(n1,n1); for t=1:n1 for r=1:n1 q = min([LB-rowsum(t);LB-colsum(r)]); traffic(r,t) = traffic(r,t) + q; rowsum(t) = rowsum(t) + q; colsum(r) = colsum(r) + q; end end TQBS = traffic; flow = tom('flow',n1,n1,'int'); pmin = tom('pmin',1,1); % Bounds bnds = {0 <= flow <= 1, pmin >= 0}; while sum(sum(TQBS)) > 0.01 temp = TQBS > 0; temp = spones(temp); con1 = {sum(temp.*flow,2) == 1}; con2 = {sum(temp.*flow,1) == 1}; con3 = {sum(temp.*TQBS.*flow,2) >= pmin}; objective = -pmin; constraints = {bnds, con1, con2, con3}; options = struct; options.solver = 'cplex'; options.name = 'Satellite Scheduling'; sol = ezsolve(objective,constraints,[],options); TQBS = TQBS + sol.flow*(subs(objective,sol)); if PriLev > 0 sequence = [sequence sol.flow(:)]; pmins = [pmins sol.pmin]; end end if PriLev > 0 for t = 1:size(sequence,2), disp(['Transmission ' num2str(t) ' transfers ' num2str(pmins(t)) ' packet(s) of data' ]) this = reshape(sequence(1:end,t),n1,n1); this(find(this < 0.5)) = 0; % remove bad zeros for j = 1:n1, disp([' from station ' num2str(j) ' to ' num2str(find(this(j,:))) ]) end end end % MODIFICATION LOG % % 051122 med Created. % 060116 per Added documentation. % 060126 per Moved disp to end % 060131 per cleaned up help text % 071218 ango Multiple CPLEX solutions handled gracefully % 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: Satellite Scheduling f_k -13.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 9
CPU time: 0.015625 sec. Elapsed time: 0.015000 sec.
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -10.999999999999995000
sum(|constr|) 0.000000000000000111
f(x_k) + sum(|constr|) -10.999999999999995000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 13
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -7.000000000000000000
sum(|constr|) 0.000000000000003437
f(x_k) + sum(|constr|) -6.999999999999996400
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 12
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -6.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 9
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -3.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 8
CPU time: 0.015625 sec. Elapsed time: 0.015000 sec.
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -3.000000000000000000
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
FuncEv 4
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -0.999999999999992890
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license 999001. Valid to 2010-02-05
=====================================================================================
Problem: --- 1: Satellite Scheduling f_k -1.000000000000001800
f(x_0) 0.000000000000000000
Solver: CPLEX. EXIT=0. INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found
Transmission 1 transfers 13 packet(s) of data
from station 1 to 4
from station 2 to 3
from station 3 to 1
from station 4 to 2
Transmission 2 transfers 11 packet(s) of data
from station 1 to 3
from station 2 to 1
from station 3 to 2
from station 4 to 4
Transmission 3 transfers 7 packet(s) of data
from station 1 to 1
from station 2 to 2
from station 3 to 4
from station 4 to 3
Transmission 4 transfers 6 packet(s) of data
from station 1 to 2
from station 2 to 4
from station 3 to 3
from station 4 to 1
Transmission 5 transfers 3 packet(s) of data
from station 1 to 2
from station 2 to 1
from station 3 to 4
from station 4 to 3
Transmission 6 transfers 3 packet(s) of data
from station 1 to 2
from station 2 to 4
from station 3 to 1
from station 4 to 3
Transmission 7 transfers 1 packet(s) of data
from station 1 to 4
from station 2 to 2
from station 3 to 1
from station 4 to 3
Transmission 8 transfers 1 packet(s) of data
from station 1 to 4
from station 2 to 1
from station 3 to 2
from station 4 to 3