An Optimization Problem in Cellular Network Design Formulation via Integer Linear Program In cellular networks the coverage area is divided into cells Each cell is served by base station to which the mobile units connect wirelessly The base stations are connected to switching centers through a wired network Whenever a mobile unit moves to another cell a handoff procedure has to be carried out There are two types of handoffs Intra switch handoff the mobile moves between two cells that are connected to the same switch Inter switch handoff the mobile moves between two cells that are connected to different switching centers 1 An Optimization Problem in Cellular Network Design The two different types of handoff procedures have different costs for example in terms of processing time The goal of the optimization which is part of the cellular network planning process in this case study is to decide which base station will be connected to which switching center such that the total cost is minimized The total cost takes into account the cost of the different handoff procedures based on traffic volume data as well as the cabling cost among base stations and switching centers In addition the traffic processing capacity of the switching centers is bounded which has to be factored into the optimization 2 Case Study solution Note that the handoff cost between two cells depends on the traffic volume amount of handoffs between them Furthermore it also depends on whether they are assigned to the same switch or not since that assignment decides whether intra switch or inter switch handoff is needed The assignment between cells and switches however is not given in advance it is obtained from the optimization On the other hand the optimization in turn depends on the handoff costs This circular dependence makes the first formulation of the problem nonlinear Then we can linearize it with the trick that was used in earlier exercises to linearize a product of variables 3 Case Study solution contd Generally a single switch may be connected to multiple cells Thus there are two types of handoffs In one a mobile moves from one cell to an adjacent cell both of which are under the control of the same switch This is relatively a simple handoff in as much as it involves only one switch and no location updates In the second type of handoff a mobile moves from one cell to an adjacent cell each of which are conntected to different switches This leads to complications in terms of the need to update location databases a complex protocol between the two switches and the continued routing of the call through the first switch for billing This optimzation problem was solved Merchant and Sengupta their approach is followed closely below 4 Case Study solution contd In this optimization problem there an N cells and M switches The basic problem is to assign cells to switches so as to minimize a cost function The following vriables will be defined hij cost per unit of the handoffs from cell i to j This is proportional to the volume of handoffs between cell i and cell j cik The cost per time of cabling between cell i and switch k This cost could be adjusted for amortization cost of money etc i number of calls processed by cell i in unit time Mk call processing capacity of switch k 5 Case Study solution contd 6 Case Study solution contd 7 Case Study solution contd 8 Case Study solution contd 9 Case Study solution contd 10 Case Study solution contd A probem with the formulation above pointed out by the authors is that the constraint of equation 2 99 is not linear The program can be converted into integer linear program by using the following constraints in place o equation 2 99 zijk xik zijk xjk zijk xik xjk 1 2 104 2 105 2 106 11 Example 1 Capital Budgeting A telecommunication company wants to build switching centers at certain given sites The sites should be selected so that the total profit is maximized under the constraint that the total cost remains within the available budget The following information is available to formulate the problem There are N available sites The cost of building a switching center at site i is ci If a center is built at site i then it generates a profit pi say per year The total available budget that can be used for building the centers is C Objective select which of the N sites will be used for building switching centers so that the total profit is maximized while keeping the total cost within the budget Any number of sites can be selected out of the N 12 13 14 15 Comment Though we have not mentioned it one can easily recognize that this problem is exactly identical to the well known Knapsack Problem 16 How can we find a solution It is well known from the study of algorithms that the Knapsack Problem is NP complete so we cannot reasonably hope to find the exact optimum for a large problem via an efficient algorithm A good approximation however is still possible Principle of the heuristics Sort the sites according to their profit cost ratio Clearly a higher profit cost ratio is more preferable Select the sites one by one in this order thus always trying the most preferable first among the yet unselected ones Preference profit cost If the considered site still fits in the remaining budget then select it otherwise proceed to the next one in the preference order This is a natural variant of the so called Greedy Algorithm 17 Trying the sites according to the profit cost preference order is so natural that one may wonder why it does not guarantee an optimum solution Exercise to test your understanding for yourself Find a specific example when the above greedy algorithm does not yield the optimum Example in the following slide 18 Solution to the exercise Consider the following data p1 90 c1 10 p2 20 c2 2 p3 8 c3 1 Budget C 11 Then the profit cost ratios are P1 c1 9 p2 c2 10 p3 c3 8 The Greedy Algorithm would select i 2 first since p2 c2 is the largest This choice uses c2 2 units from the budget The next largest ratio is p1 c1 but c1 10 already does not fit in the remaining budget of 11 2 9 So the algorithm proceeds to i 3 which still fits in the budget Thus the Greedy Algorithm selects sites 2 and 3 achieving a total profit of 20 8 28 On the other hand if we select sites 1 and 3 then we can achieve a profit of 90 8 98 while the cost still fits in the budget 19 Comment As we have seen the Greedy Algorithm does not necessarily find the optimum for this problem A natural question is How far is it from the
View Full Document
Unlocking...