An Efficient Cell Selection in Cellular Network With High Scalability

An Efficient Cell Selection in Cellular Network With High Scalability

M. Amutha Surya* Dr. Sangeetha SenthilKumar

*IInd year ME(CSE) Oxford Engineering College Trichy

Asst.Professor /CSE Department

Abstract This paper mainly focuses about Cell selection process in the Cellular Network. Cell selection is the process of determining the cell, to provide services to every mobile station. The goal is to find a maximum-profit subset of clients that can be fully satisfied by all-or-nothing demand maximization algorithm (AoNDM). Each base station has a capacity c(i), and every mobile client has a profit p(j) and a demand d(j) which is allowed to be simultaneously satisfied by more than one base station. Each base station i has a coverage area represented by a set of mobile stations. The EdmondsKarp algorithm is utilized for computing the maximum flow in a flow network in O(V E2) time. One of the important components of mobility management is the ability of the network to seamlessly re-route existing connections to different parts of the network. An user can utilize multicasting in order to reroute connections. A predictive approach, where a Mcall is pre-established to potential new base stations by setting up a multicast tree with neighbouring base stations as leaf nodes. This approach reduces the latency caused by rerouting to an absolute minimum and improves communication with strict time constraints.

Key Terms: Cellular Networks, Multicasting, Re-Routing, Leaf nodes, Edmonds-Karp algorithm, Predictive approach.

Cell planning is an important step in the design, deployment, and management of cellular networks. Cell planning includes planning a network of base stations that provides a (full or partial) coverage of the service area with respect to current and future traffic requirements, available capacities, interference, and the desired QoS. Cell planning is employed not only when a new network is built but also when a modification to a current network is made.

Such a design problem includes planning a network of base stations providing full coverage of the service area with respect to current and future traffic requirements,

available capabilities, and the desired QoS. Under these constraints, the objective is, in general, to minimize the operator's total system cost. The input for this problem consists of a list of all base station potential locations; each associated with an opening cost, technology dependent parameters such as the possible antenna characteristics (including the corresponding propagation model and propagation matrices), possible interferences, and the traffic demands. Roughly speaking, the geographical distribution of the traffic demand can be forecasted by using demographic data, such as structure of the population, motor vehicle density, distribution of income, telephone density etc., or previous data from existing mobile systems. A typical outcome of this planning process is a set of base stations, a list of antenna in each site,

the coverage of each antenna and where needed, the allocation of frequencies to the different cells.

Cellular Networks

Cell planning is a basic important task in the design of cellular networks. A cellular network or mobile network is a wireless network distributed over land areas called cells, each served by at least one fixed-location transceiver, known as a cell site or base station.

Fig.1Cellular Network

The network is composed out of the following entities: Mobile station (MS) – Device used to communicate over the cellular network. Base station transceiver (BST) – Transmitter/ receiver used to transmit/ receive signals over the radio interface section of the network. Base station controller (BSC) -Controls communication between a group of BST's and a single MSC. Mobile switching centre (MSC) – The heart of the network, sets up and maintains calls made over the network .Public switched telephone network (PSTN) – The land based section of the network. The MSC connects to the

public switched telephone network (PSTN), which switch calls to other mobile stations or land based.

Cell Planning Problems

Given a set I={1,,m} of possible configurations of base stations (abbreviated base stations) and a set J={1,,n} of mobile client locations (or clients). The base station configuration

[11] contains the geographical location and the typical antenna pattern (as well as its adopted model of propagation), tilt, height and any other relevant parameters of a base station antenna that together with the technology used to determine the coverage area and the interference pattern. Each station has a capacity wi and an opening cost of ci, and every client has a demand dj. (note that this is the total demand from this area and not the demand of a single user.) The coverage area of an antenna configuration is represented by a subset of feasible client locations.

A number of special important cases are of interest in the cell planning problem. One special case is, when the planning task is to respond and supply the changes needed in order to adjust existing network to incremental local traffic changes (e.g. a new big mall is built in a dense neighbourhood). In this case one can set the opening cost of the existing base stations to zero, and the motivation is to satisfy the new demands using as few new installations as possible.

Minimum-Cost Cell Planning Problem

The minimum-cost cell planning problem asks for a minimum-cost subset

that satisfies the demands of all the clients. This important problem is one of the most studied on the area of cellular network optimization. A comprehensive survey of various works on minimum-cost cell planning problems appears in [14]. An O(logW)-approximation algorithm for the non-interference version of the minimum- cost cell planning problem is presented in [13][14] .

Thek4k-Budgeted Cell Planning Problem

BCPP which is general enough to cover all interesting practical cases. In order to do that, we use the fact that in general, the number of base stations in cellular networks is much smaller than the number of clients. Notice that when planning cellular networks, the notion of

clients sometimes means mobile-clients and sometimes it represents the total traffic demand created by many mobile-clients at a given location. Moreover, when there is a relatively large cluster of antennas in a given location, this cluster is usually addressed to meet the traffic requirements of a high-density area of clients. Thus for both interpretations of clients the number of satisfied clients is always much bigger than the number of base stations [2][13] .

CLMS convergence algorithm

It is well known that an array of weights has N-1 L degree of freedom for adaptive beamforming [12][15]. This means that with an array of weights, one

can generates pattern nulls and a beam maximum in desired directions. To null all of these interferes; one would have to have weights, which is not practical. So, we focus only on the paths of the desired user.

Thus, the minimum number of the antenna array weights is where, typically, varies from 2 to 6 [16]. we use the CLMS adaptive beamforming algorithm. This algorithm is a gradient based algorithm to minimize the total processor output power, based on the look direction constraint.

Congestion-aware Steiner trees

The major goal of congestion- aware Steiner tree routing is to find a tree that connects the required set of nodes (referred to as terminals) while avoiding congested areas with a minimum penalty in terms of the total ire length. In addition, the running time of the algorithm must scale well with the growing number of nets [21]. This poses several challenges in terms of the algorithm design. The first challenge is to select a suitable cost function that adequately captures the local congestion conditions on the edges of the routing graph.

Budgeted Facility Location

The budgeted version of the (uncapacitated) facility location problem is also closely related to BCPP. In the traditional (uncapacitated) facility location problem wish to find optimal locations in which to build facilities, from a given set I, to serve a given set J of clients, where building a facility in location i incurs a cost of fi. Each client j must be assigned to one facility, thereby incurring a cost of cij (without assuming the triangle inequality). The budgeted facility location problem is to find a subset I such that the total cost of opening facilities and connecting clients to open facilities does not exceed a given budget B, and the total no of clients are maximized[2].

Cell selection has received much attention in recent years [2], [3], [4], [5] where research focused mainly on multiple-access techniques, as well as on power control schemes and handoff protocols. In [2], a cell selection algorithm is presented where the goal is to determine the power allocations to the various users, as well as a cover-by-one allocation, so as to satisfy per-user SNR constraints. Combinatorial algorithms, and more specifically local ratio and primal dual algorithms, which only allow an item to be packed in a single bin, have been considered for some of the above mentioned related problems[10]. A greedy algorithm that iteratively assigns users to base stations using the best approximation scheme for the Knapsack problem was proved to produce an approximation [9].

A Cover-by-One (1-r)/

(2-r) -Approximation Algorithm

Start with Algorithm CBO-MC. Note that there are at hand cover-by-one algorithms that ensure an approximation ratio better than algorithm [7] [8]. Our algorithm, on the other hand, is strictly combinatorial. Roughly speaking, under CBO-MC, given a specific ordering of the clients, and given an existing cover plan x, a client is added greedily by finding a CBO extension of x, if such an extension exists. Otherwise, the client is discarded.

A Cover-by-Many (1 r)Approximation Algorithm

CBMMC, which achieves an approximation ratio of (1 r) using the

cover-by-many paradigm[1]. Under CBM- MC, a client is added by first trying to exhaust the capacities of base stations which cannot contribute to uncovered clients, and then using the capacity of the remaining base stations in order to complete the cover. If such a cover cannot be produced, then the client is discarded. There exist mobile clients with demands that are relatively close to the capacity of the servicing cell (eg. in cases of picocells) allowing satisfaction of a client by more than one base station.

Hard rerouting

Hard rerouting is the easiest scheme [20]. There is only a single connection end point per mobile at the same time. Since no data are duplicated, the data overhead is minimized. Two drawbacks can be identified: a) The duration of service interruption is relatively long, because the service is interrupted until the old base station is dropped and the new base station added and b) there is a gap between the drop- and the add-end point-operation and data might get lost. The response message contains the end points and connections with its QoS attributes of the MCALL.

Soft rerouting

The soft rerouting scheme changes the sequence of drop-end point and add- end point-operation from hard rerouting. Therefore for a limited time at least more than two base stations belong to the MCALL. The mobile host has connectivity at least to the old and to the new base stations simultaneously and the radio cells of the base stations overlap. The main benefit of the scheme is that the handover

response message (HO_RESP) can be sent to the mobile when the new end point (new base station) is added to the MCALL. The steps of the soft rerouting scheme are very similar to the hard rerouting scheme, except that adding the new end point (ADD_EP_REQ, ADD_EP_RESP) and

dropping the old end point [21].

Global Cell selection

Consider a set I = {1, 2, . . . ,m} of base stations and a set J = {1, 2, . . . , n} of mobile clients. Each base station has a capacity c(i), and every mobile client has a profit p(j) and a demand d(j) which is allowed to be simultaneously satisfied by more than one base station. Each base station has a coverage area represented by a set Si subset of J of mobile clients admissible to be served by it [1]. The goal is to find a maximum-profit subset of J of clients that can be fully satisfied by I. This problem is as hard to approximate as the maximum-size independent set problem. It present an approximation algorithms which guarantees to produce a solution which carries at least a (1 1/k) fraction of the optimal profit. This algorithm is based on a much simpler and faster approximation algorithm with an approximation ratio[1],[14] .Derive the appropriate number of microcells and picocells.The locations for each type of basestation was uniformly and randomly selected over the grid and clients were associated.Satisfication of data clients is credicted as profit proportional to demand.

Fig 3 Global cell selection

As AoNDM is NP-hard, the maximum possible profit is hard to calculate, and we consider the total profit of all connected clients as an upper bound on the optimal solution.

The Edmonds/Karp Algorithm

Shortest paths algorithms use edge costs and their running time depends only on the parameters , Such an algorithm is called strongly polynomial. The path in tree with the minimum number of edges can be found in O(m) time standing assumption that every vertex of the graph has at least one incident edge. Once path P is discovered, it takes only O(n) time to travel from source to destination which supports to maximum flow. Recalling that every edge of P goes from level i to i + 1, for some i < j, Since the distance from s to v never decreases, this means that v remains in level Li+1 or higher deals with the capacity of the base station.

Re-Routing

The key mobility support function in mobile networks is the path rerouting[18],[19],[20] process that is

required when a mobile terminal moves from one access point to another or any failure condition However, we believe that, in the future, a large proportion of users will become mobile users who will share the same fixed network with the existing fixed users. Thus, studying the impact of handoff or any failure situation(overloading) path rerouting on these fixed networks is very important for the optimum design of the network. It describes the mechanism that transfers the association of a mobile end system from one base station – which is presently active

– to a new base station. The rerouting of connections in a broadband mobile cellular networks address networks with a connection-oriented backbone, which supports quality-of-service (QoS).

Predictive rerouting

The predictive rerouting scheme adopts some ideas from [20], [21]. In this scheme base stations, which are potential candidates for handover of mobile hosts, form a set of base stations. When a MCALL is set up to a base station, the end points of the base stations, belonging to the set, will also be added to the MCALL. The actual base station is called active, the other base stations inactive. When a handover occurs, the new base station becomes active and serves the mobile host. The set of base stations is updated by the new base station. The main advantage of the predictive rerouting scheme is, that the new handover segment is already established ,latency is minimized. The steps for the predictive rerouting scheme are mainly an extension of the soft rerouting scheme. The end points of a potentialbase station (BS_POT) is added

to the MCALL and the end point of the old base station (BS_OLD) is dropped.

In this paper, we utilized the mechanism All-or-Nothing Demand Maximization (AoNDM) that determines the assignments of mobile clients to base stations in a service oriented cellular environment, simultaneously satisfied by more than one base station. A maximum- profit of clients that can be fully satisfied is possible. The path which supports to the maximum flow, between source and destination. Through the iteration concept, capacity of the base station can be analysed. Thus Edmonds-Karp implies, increase in scalability. Augmenting path selection is done by predictive re-routing. The potential new base stations (which form a set) are added to the MCALL. If the old base station get dropped, which will be responded by the new base station. The results presented in this paper show that a theoretical approach based on algorithms can handle capacities, demands, and interference, which provide better solution for cell planning problems and provide more scalability. This is the significant step towards focused planning of 4G networks.

The forthcoming 4G cellular networks are planned to provide a wide variety of new services. Services from high-quality voice and high-definition video to high-data-rate wireless channels such as HDTV, video conferencing. The major feature of the 4G system capability should be its ultra high speed IP packet transmission with reduced delay to meet a

variety of requirements derived from information media world. The local and international standardization activities indicate a global strong support toward this 4G direction.

REFERENCES

1. David Amzallag, Reuven Bar-Yehuda, Danny Raz, and Gabriel Scalosub Cell Selection in 4G Cellular Networks IEEE transactions on mobile computing, vol. 12, no. 7, july( 2013).

2. S.V. Hanly, An Algorithm for Combined Cell-Site Selection and Power Control to Maximize Cellular Spread Spectrum Capacity,IEEE J. Selected Areas in Comm., vol. 13, no. 7, pp. 1332- 1340, Sept. 1995.

3. R. Mathar and M. Schmeink,

   Integrated Optimzal Cell Site Selection and Frequency Allocation for Cellular Radio Networks,Telecomm. Systems, vol. 21, pp. 339-347, 2002.

4. A. Sang, X. Wang, M. Madihian, and

   R.D. Gitlin, A Load-Aware Handoff and Cell-Site Selection Scheme in Multi-Cell Packet Data Systems. Proc. 47th IEEE Global Comm. Conf. (GlobeCom), vol. 6, pp. 3931-3936, 2004.

5. A. Sang, X. Wang, M. Madihian, and

   R.D. Gitlin, Coordinated Load Balancing, Handoff/Cell-Site Selection, and Scheduling in Multi-Cell Packet Data Systems, Wireless Networks, vol. 14, no. 1, pp. 103-120, 2008.

6. L. Fleischer, M.X. Goemans, V.S. Mirrokni, and M. Sviridenko, Tight Approximation Algorithms for Maximum General Assignment Problems, Proc. 17th ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 611-620, 2006.

7. D. Shmoys and E. Tardos, An Approximation Algorithm for the Generalized Assignment Problem, Math. Programming, vol. 62,no. 3, pp. 461-474, 1993.

8. C. Chekuri and S. Khanna, A Polynomial Time Approximation Scheme

   for the Multiple Knapsack Problem, SIAM J. Computing,vol. 35, no. 3, pp. 713-728, 2005.

9. R. Cohen, L. Katzir, and D. Raz, An Efficient Approximation for the Generalized Assignment Problem, Information Processing Letters, vol. 100, no. 4, pp. 162-166, 2006.

10. Z. Nutov, I. Binyaminy, and R. Yuster, An Approximation Algorithm for the Generalized Assignment Problem,Operations Research Letters, vol. 34, no. 3, pp. 283-288, 2006.

11. R. Mathar and T. Niessen. Optimum positioning of base stations for cellular networks, Wireless Networks, 6, pp. 421- 428, (2000).

12. Mohamad Dosaranian Moghadam1, Hamidreza Bakhshi2, Gholamreza DadashzadepInterference Management for DS-CDMA Systems through Closed- Loop Power Control, Base Station Assignment, and Beamforming Wireless Sensor Network, 2, 472-482,(2010).

13. D. Amzallag, R. Engelberg, J. Naor, and D. Raz. Approximation algorithms for cell planning problems. Manuscript, 2006.

14. David Amzallag, Joseph (Seffi) Naor, and Danny Razcoping with interference: From maximum coverage to planning cellular network The 4th workshop on approximation and online algorithms [WAOA](2006).

15. N. A. Mohamed and J. G. Dunham,

    A Low-Complexity Combined Antenna Array and Interference Cancellation DS- CDMA Receiver in Multipath Fading Channels, IEEE Journal on Selected Areas in Communications, Vol. 20, No. 2, 2002, pp. 248-256.

16. F. Rashid-Farrokhi, L. Tassiulas and

    K. J. Ray-Liu, Joint Optimal Power Control and Beamforming in Wireless Networks Using Antenna Arrays, IEEE Transactions on Communications, Vol. 46, No. 10, 1998, pp. 1313-1324.

17. J. Litva and T. Kwok-Yeung, Digital Beamforming in Wireless Communications, Artech House, Boston, 1996.

18. Acampora, et al.: An Architecture and Methodology for Mobile-Executed Handoff in Cellular ATM Networks, IEEE Journal on Selected Areas in Communication, Oct. 1994.

19. B. Akoyl and D. Cox, Reroutihg for handoff in a wireless ATM network, IEEE Personal Commun., vol. 3, Oct. 1996.

20. J. Li, R. Yates, and D. Raychaudhuri,

    Unified handoff control protocol for dynamic path rerouting in mobile ATMnetworks, in Proc. 9th IEEE Int. Symp. Personal Indoor and Mobile Radio Communications, Boston, MA, Sept. 1998.

21. C. K. Toh, et al.: A Unifying Methodology for Handovers of Heterogeneous Connections in

Wireless ATM Networks. Computer Communication Review, Vol. 27, No. 1,

1997.