A heuristic approach to satellite link capacity planning applied in mobile networks

Taking into account the continuous increase of traffic demands, it is necessary to increase satellite link capacity rationally. An efficient algorithm for sizing of N satellite links in mobile networks during exploitation is being developed, minimizing the total expansion cost. Capacity shortages are allowed so the problem is denoted as CEPS (Capacity Expansion Problem with Shortages). Using a network flow approach, the paper develops all possible expansion solutions for SPEP (Single Period Expansion Problem) and properties of extreme point solution are identified. The extreme flow theory enables separation of these extreme flows which can be a part of an optimal expansion solution from those which cannot. Such a heuristic approach enables the optimal result, using significantly less effort in programming and algorithm development. Our heuristic algorithm is compared with an algorithm based on an exact approach through many numerical examples. It is obvious that it is very effective, providing an optimal result with reasonable effort. The algorithm can be applied to short- or medium-term satellite network planning with a finite number of discrete time periods.