Report

Frequency assignment for satellite communication systems Kata KIATMANAROJ Supervisors: Christian ARTIGUES, Laurent HOUSSIN 1 Contents • • • • Problem definition Current state of the art Contributions Conclusions and perspectives 2 Problem definition 3 Problem definition • To assign a limited number of frequencies to as many users as possible within a service area 4 Problem definition • To assign a limited number of frequencies to as many users as possible within a service area • Frequency is a limited resource! – Frequency reuse -> co-channel interference – Intra-system interference 5 Problem definition • Simplified beam • SDMA: Spatial Division Multiple Access j i k 6 Problem definition • To assign a limited number of frequencies to as many users as possible within a service area • Frequency is a limited resource! – Frequency reuse -> co-channel interference – Intra-system interference • Graph coloring problem – NP-hard 7 Problem definition • Interference constraints Binary interference Cumulative interference i i j j k Acceptable interference threshold Interference coefficients 8 Problem definition • Assignment – – – – Logical boxes (superframes) Demand = |F|x|T| No overlapping within the superframe Overlapping between superframes (simultaneous) may create interference 1 2 0 ≤ oij ≤ 1 9 Problem definition • Superframe structure 10 Problem definition • Frames and satellite beams 11 Problem definition 12 Current state of the art 13 Current state of the art - FAP • Distance FAPs – – – – Maximum Service FAP Minimum Order FAP Minimum Span FAP Minimum Interference FAP • Solving methods – Exact method – Heuristics and metaheuristics 14 Current state of the art – satellite FAP • Two branches – Inter-system interference – Intra-system interference • Inter-system interference – Two or more adjacent satellites – Minimize co-channel interference (multiple carriers) • Intra-system interference – Multi-spot beams – Geographical zones assuming the same propagation condition 15 Contributions 16 Contributions • Part 1: Single carrier models • Part 2: Multiple carrier models • Part 3: Industrial application 17 Single carrier models • K. Kiatmanaroj, C. Artigues, L. Houssin, and F. Messine, Frequency assignment in a SDMA satellite communication system with beam decentring feature, submitted to Computational Optimization and Applications (COA) • K. Kiatmanaroj, C. Artigues, L. Houssin, and F. Messine, Frequency allocation in a SDMA satellite communication system with beam moving, IEEE International Conference on Communications (ICC), 2012 • K. Kiatmanaroj, C. Artigues, L. Houssin, and F. Messine, Hybrid discrete-continuous optimization for the frequency assignment problem in satellite communication system, IFAC symposium on Information Control in Manufacturing (INCOM), 2012 18 Single carrier models • 1 frequency over the total duration • Same frequency + located too close -> Interference • 3 models (supplied by Thales Alenia Space) 19 Single carrier models • Model 1 (fixed-beam binary interference) – – – – 40 fixed-beams 2 frequencies / beam even no user Interference matrix (binary interference) Graph coloring: DSAT algorithm -> 4 colors 8 frequencies in total 20 Single carrier models • Model 2 (fixed-beam varying frequency) – – – – 40 fixed-beams 8 frequencies (different within the same beam) Cumulative interference Greedy vs. ILP 21 Single carrier models • Model 3 (SDMA-beam varying frequency) – – – – SDMA (beam-centered) 8 frequencies (different within the same beam) Cumulative interference Greedy vs. ILP 22 Single carrier models • Greedy algorithms – User selection rules – Frequency selection rules 23 Single carrier models • Greedy algorithms – User selection rules – Frequency selection rules 24 Single carrier models • Integer Linear Programming (ILP) 25 Single carrier models • Performance comparison 180 Model 1 Number of acceped users 160 Model 2 Greedy 140 Model 2 ILP 120 Model 3 Greedy Model 3 ILP 100 80 60 40 20 0 20 40 60 80 100 120 140 160 180 200 Number of users ILP 60 sec 26 Single carrier models • ILP performances 27 Continuous optimization * Collaboration with Frédéric Mezzine, IRIT, Toulouse 28 Continuous optimization • Beam moving algorithm – For each unassigned user • Continuously move the interferers’ beams from their center positions • Non-linear antenna gain • Minimize the move • Not violating interference constraints 29 Continuous optimization • Matlab’s solver fmincon User i Gain αi Δix i x k j i Δix + j Δjx + k Δkx + x 0 - 30 Continuous optimization • Matlab’s solver fmincon User i Gain αi Δix ↓ ↓ ↓ i x j i ↓+ j k k x - 31 Continuous optimization • Matlab’s solver fmincon User i Gain αi Δix ↓ ↓ ↓ i x j i ↓ j k k x - 32 Continuous optimization • Matlab’s solver fmincon User i Gain αi Δix ↓ ↓ ↓ i x j i ↓- j k k x - 33 Continuous optimization • Matlab’s solver fmincon User i Gain αi Δix i ↓ ↓ ↓ ↓ j ↓ ↓ ↓ ↓ k ↓ ↓ ↓ ↓ i x k j x + 34 Continuous optimization • Matlab’s solver fmincon • k: number of beams to be moved • MAXINEG: margin from the interference threshold • UTVAR: whether to include user x to the move 35 Continuous optimization • Matlab’s solver fmincon • Parameters: k, MAXINEG, UTVAR 180 6.0 160 140 5.0 120 4.0 100 3.0 80 60 2.0 40 1.0 20 0.0 0 3 4 5 6 7 8 9 10 k (Number of Interferers) 7.0 160 6.0 140 5.0 120 100 4.0 80 3.0 60 2.0 40 1.0 20 0.0 0 3 4 5 6 7 8 9 10 k (Number of Interferers) Users (MAXINEG = 1) Users (MAGINEG = 2) Users (MAXINEG = 1) Users (MAGINEG = 2) Time (MAXINEG = 1) Time (MAXINEG = 2) Time (MAXINEG = 1) Time (MAXINEG = 2) 36 Cal. Time / Resggined User (s) 7.0 Number of Reassigned Users Beam Decentring with UTVAR = 1 Cal. Time / Resggined User (s) Number of Reassigned Users Beam Decentring with UTVAR = 0 Continuous optimization 180 180 160 160 140 140 Number of accepted users Number of accepted users • Beam moving results with k-MAXINEG-UTVAR = 7-2-0 120 100 80 60 Greedy 40 ILP (60s) Greedy + Beam Decentring 20 ILP + Beam Decentring 0 20 40 60 80 100 120 140 Number of users 160 180 200 120 100 80 60 Greedy 40 ILP (180s) 20 Greedy + Beam Decentring ILP + Beam Decentring 0 20 40 60 80 100 120 140 Number of users 160 180 200 37 Continuous optimization • Beam moving results with k-MAXINEG-UTVAR = 7-2-0 38 Continuous optimization • Closed-loop implementation 39 Conclusions and further study – Part 1 • Greedy algorithm: efficient and fast • ILP: optimal but long calculation time • Beam moving: performance improvement • Column generation for ILP • Fast heuristics for continuous problem • Non-linear integer programming 40 Multiple carrier models 41 Multiple carrier models • Binary interference • Cumulative interference 42 Multiple carrier models • Binary interference – LF: loading factor 43 Multiple carrier models • Binary interference – A user as a task or an operation – User demand (frequencies) as processing time – Interference pairs as non-overlapping constraints – Disjunctive scheduling problem without precedence constraints – Max. number of scheduled tasks with a common deadline 44 Multiple carrier models • Binary interference – Disjunctive graph and clique – {1,2}, {2,3}, {2,4}, {3,5}, {4,5,6} vs. 7 interference pairs – CP optimizer 45 Multiple carrier models • Binary interference 46 Multiple carrier models • Binary interference 47 Multiple carrier models • Binary interference 48 Multiple carrier models • Cumulative interference – Overlapping duration should be considered fi d i fi fj d j fj fi d i fi fj fj d j o ij f i d i f j o ij d j 49 Multiple carrier models • Cumulative interference: ILP1 50 Multiple carrier models • Cumulative interference: ILP2 51 Multiple carrier models • Cumulative interference: ILP3 52 Multiple carrier models • Scheduling (CP) vs. ILP (CPLEX) 53 Multiple carrier models • Cumulative interference vs. binary interference 54 Multiple carrier models • Cumulative interference vs. binary interference 55 Conclusions and further study – Part 2 • FAP as scheduling problem • Outperform ILP • Cumulative -> Binary interference • Pattern-based ILP with column generation • Heuristics based on interval graph coloring • Local search technique 56 Industrial application • K. Kiatmanaroj, C. Artigues, L. Houssin, and E. Corbel, Greedy algorithms for time-frequency allocation in a SDMA satellite communication system, International conference on Modeling, Optimization and Simulation (MOSIM), 2012 57 Industrial application • Terminal types – 50 dBW, 45 dBW – Max. 24 Mbps, 10 Mbps • Traffic types – Guaranteed, Non-guaranteed • User priority level and handling 58 Industrial application • Symbol rate - Modulation - Coding scheme (RsModCod) – 16 ModCod – 4 symbol rates (Rs) corr. to 5, 10, 15 and 20 MHz – Support bitrate (Mbps) – Different acceptable interference thresholds (alpha) 59 Industrial application • Beam positioning methods – Fixed-beam – SDMA beams 60 Greedy algorithms 61 Greedy algorithms • Fast • Flexible • Extensive hierarchical search • MI (Minimum Interference) • MB (Minimum Bandwidth) • No performance guarantee 62 Greedy algorithms: MI • Minimum Interference (MI) New superframe when the old one is utilized. MI Superframe 1 Superframe 2 63 Greedy algorithms • Minimum Bandwidth (MB) New superframe before increasing bandwidth 64 Experimental results 65 Computational experiments • Test instances 66 Experimental results • Assignment time (seconds) BC longer time than FB BC30 longer than BC25 MI about the same time as MB 67 Experimental results • Number of rejected users Largely depended on demand / BW 68 Conclusions and further study – Part 3 • Highly complex problem and fast calculation time requirement • ILP impractical • MI: least interference • MB: least bandwidth • Lower bounds on the number of rejected users • Local search heuristics 69 Conclusions and further study 70 Conclusions and further study • Solved FAP in a satellite communication system • Binary and cumulative interference • Single, multiple carrier, realistic models • Greedy algorithm, ILP, scheduling • • • • Hyper-heuristics Non-linear integer programming Column generation Local search: math-heuristics 71 Thank you 72