Advanced River Formation Dynamics for Location Area Management in GSM

Advanced River Formation Dynamics for Location Area Management in GSM

Dixa Dholakiya1,Tapan Doshi2 , Sagar Ghiya3and Prashantkumar Patel 4

1Department of Computer Engineering, Birla VishwakarmaMahavidyalaya,Gujarat, India.

2,3Department of Instrumentation and Control Engineering,Nirma Institute of Technology, Gujarat,India.

4 Department of Computer engineering Vishwakarma Govt. Engineering College Gujarat, India.

Abstract- To handle call delivery for mobile station, itsprobable location should be known to the network. For that location management is required. Location Management has two basic operations: location update and paging.The goal of an efficient location management scheme is to maintain and provide locations of mobile stations at low cost. This paper presents location area based approach proposed by researchers and nature inspired approach proposed by us, to reduce location management cost.However, there is trade off between reduction of location update cost and paging. Simulation Results of a basic location area scheme and nature inspired technique(river formation dynamics) is presented.

Abbreviations:

LA Location Area, LAM Location Area Management, LM Location Management, LU Location Update, RFD River Formation Dynamics

Keywords: Location Management, Location Update, Location Area Management, River Formation Dynamics, Modified Dynamic Approach For RFD

1. INTRODUCTION

   Mobility can be categorized in two areas: a) radio mobility,which mainly consists of the handover process, and

   b) networkmobility, which mainly consists of location management. While handover processes are essentially coping with radio aspects, location management is rather mainly influenced by both user mobilityand call patterns. The focus in this paper is on location management. Location Management is required to track location of mobile station in order to deliver the call.To handle call delivery for mobile station, its probable location should be known to network. The granularity of this tracking has two levels: a) in the time between calls, the tracking is performed by the location update procedure at the location area (LA) granularity and

   1. at call arrival; the tracking is performed inside the location area by the paging procedure at the cell granularity. Location management in cellular network includes signalling in the wire-line portion and the wireless portion. Generally most of the researchers consider signalling in the wireless portion because the radio frequency bandwidth is limited while the bandwidth of the wire-line network is always expandable. Location update involves reverse

      control channels (mobile station to base station) while paging involves forward control (base station to mobile station) channels. There is a trade-off between the location update cost and the paging cost. If a mobile station updates its location more frequently, the network knows the most recent location of the mobile station. When an incoming call arrives for the mobile station, network requires less effort to page the mobile station and hence paging cost will be low. Therefore both location update and paging costs cannot be minimized at the same time. For attaining optimum total cost either location update cost or paging cost can be reduced. The rest of this paper is organized as follows. First we discuss about location area approach used in managing mobile users location. After that we discuss natural heuristic approach, river formation dynamics, for location area management. In the next section advanced and efficient algorithm of RFD is discussed with results and comparison. At the end of this paper we summarize this discussion.

2. RELATED WORK: LOCATION AREA APPROACH FOR LOCATION MANAGEMENT

   Under the aggregate movement behaviour mobility model [10], the update cost is the sum of mobility weights of boundary links. The mobility weight of a boundary link is the sum of mobility weights (at boundary link) of two related (adjacent) cells divided by 6 [10]. The mobility weight for a node is obtained by adding up the mobility weights of its boundary links.) The paging cost for cell i is the query weight Wqi multiplied by the size of location area to which cell i belongs [10].

   The call-to-mobility ratio for each cell is obtained by dividing the query weight to the mobility weight. A cellular network is represented in graph, say G,having number of nodesN, and each node has two weights, mobility weight Wmi and query weight Wqi (1<i<N) [10,17]. In following algorithm, K is used to store nodes in G,and Li is used to store all cells of the location area towhich cell i belongs. This algorithm starts with eachcell as a location area. The algorithm will continuecombining a location area with its neighbouring locationareas if the total cost will be reduced. The Hac and Zhous algorithm [10]finds out location areas from given cellular network.

   Figure 2.1A cellular network with 4 location areas and its graph representation[10]

   Simulation results for 7,10 and 14 cells network is given in section 5.

3. NATURAL HEURISTIC APPROACH: LOCATION AREA MANAGEMENT USING RIVER FORMATION DYNAMICS

   River Formation Dynamics (RFD) [16] is an Evolutionary Computation method. RFD can be seen as a gradient- oriented version of ACO. This approach is based on copying how the water forms rivers in nature. The water transforms the environment by eroding the ground when it falls through a high decreasing slope, and it deposits carried sediments when a flatter ground is reached. Basic algorithm and expressions for river formation dynamics are shown in [16,18,19].

   From the beginningof the execution of RFD, any path from the origin point to the target pointhas a gradient that, considering this path as a whole (i.e. from the origin to thetarget), must be decreasing.

   We have applied this technique [20] to solve location management problem for optimizing total location management cost. Following table relates parameters of location management with parameters of river formation dynamics.

   River Formation Dynamic	LocationArea Management
   Number of Drops : D	>=Number of Location areas
   Number of Nodes : N	Number of Cells
   Altitude : Ai	Call-to-mobility ratio(initially)
   Distance between two nodes : Dij	Total cost after merging celli and j

   Table 4.1 Relates parameters for RFD with LM[20]

   Here this pseudo code points upstep of the algorithm for river formation dynamics to optimize total location management cost.

   RFD Algorithm for LM

   Step 1

   • Initialize N with all cells in C

   • Assign Altitude value Ai to each nodes in N

   • For each node i (1 i N),calculate distance

     Dij (j {neighbors of i }

     Step 2

     For D(number of drops) iteration

   • While N is not empty

     • Let x = starting node in N

     • For neighbouring cell of x , Calculate decreasing gradient DG

     • Find total cost C for the node pair

       {x,v}(v{neighbour of x }) which have positive DG value

     • Enter {x, v} with its total cost C to temp_list

     • N = N-1

       End While

   • Select {x, v} ,having least cost C from temp_list, x and V will be one Location Area

   • If C<C,

     • Calculate erosion at x,

     • Calculate sedimentatin at v

   End For Step 3

   Return resultant Location Areas from temp_list

   There is difficulty with thisheuristic algorithm for LAM. Drops may be stuck to local optima [21]. LocationArea is one of the popular Location Management scheme and it has shown to be NP-complete problem with high complexity. In the next section advanced approach is to be discussed causes optimal location areas configuration of a mobile network using, which will overcome above difficulties.

4. ADVANCED RIVER FORMATION DYNAMICS ALGORITHM FOR LOCATION MANAGEMENT

   In this approach, RFD is made efficient by preparing set of optimal selection. Out of all optimal solutions most preferable pairs of cells is chose for location area.

   Step 1

   • Convert cellular architecture into graph, G

   • Initialize all N nodes in graph G

     • Weight of node: Altitude Ai

     • Weight of edge: Distance

   • Assign Altitude value Ai to each nodes in N

   • For each node i (1 i N),calculate distance

     Dij (j {neighborsof i })

   • Initially each node in G acting as individual Location Area

     • Calculate initial total cost C with location areas ,Li (1 i N),

   • Create tree node [pair,cost] <- [0,C], and make it as root node of tree

   • Cur_parent<- [0,C] Step 2

   • From G, based on Altitude value, generate pairs with possible combinations of neighbouring nodes

   • Calculate total LAM cost for each pair, if it will act as a location area

     Step 3

   • For all pairs

   End if End For

   • If total LAM cost > cost(Cur_parent)

     • Discard pair

       • If pairs are remaining

         • Arrange remaining pairs in ascending order based on total cost

         • Select First (at max)four pairs from ordered list

         • Create tree nodes[pair, cost] for selected pairs

         • Enter tree nodes as children of Cur_parent

       • Else

         • Cur_parent<- parent(Cur_parent)

           Step 4

       • If Cur_parent has unprocessed child node

         • Cur_parent<- next unprocessed child

         • Mark Cur_parent<- Processed

         • Calculate Erosion Sedimentation For Cur_parent

         • Goto step 2

       • Else if Cur_parent has unprocessed sibling node

         • Cur_parent<- unprocessed sibling

         • Mark Cur_parent<- Processed

         • Calculate Erosion Sedimentation For Cur_parent

         • Goto step 2

       • Else if pair( parent( Cur_parent)) != 0

         • Cur_parent<- parent(Cur_parent)

         • Goto step 4

           Figure 5.1Cellular network topology for 7, 10,and 14 cells

           LA Based Scheme[20]	RFD[20]	Advanced RFD
           1	1	1
           2	2	2
           3,4	3,4	3,6
           5	5	4,5
           6,7	6,7	7
           Totalcost:375.33	Totalcost:375.33	Totalcost:345.00

           Results are shown below with column value represents location areas formed by different techniques and total cost is mentioned at last raw.

       • Else

       Step 5

   • Exit

   • Find tree node having [pair, minimum(cost)]

   • Return the path of tree node[pair, minimum(cost)] from root node[0,C]

     • All pair of node in path will be location area

     • Total LAM cost will be minimum(cost)

   The advanced RFD for LAM is complex in development, however it produces preferable results.

5. SIMULATION RESULTS

   Mobility weights and Query Weights values from [17] are taken as input to the algorithm.

   We use a two-dimensional cellular network with 7, 10 and 14 cells for performance comparison under different number of cells based on call-to-mobility ratio. The mobility rate and the query rate for a node are obtained by adding up the corresponding weights of its boundary links.

   Following figure shows cellular network topology for seven, ten and fourteen nodes, which are taken as a input to both the algorithms.

   Table 5.1 Results for Cellular Network with 7 cells

   LA Based Scheme[20]	RFD[20]	Advanced RFD
   1	1	1
   2	2	2
   3,6	3,7	3,7
   4,8	4,5	4,5
   5,9	6,9	6,9
   7	8	8
   10	10	10
   Totalcost:675.50	Totalcost:637.33	Totalcost:637.33

   Table 5.2 Results for Cellular Network with 10 cells

   LA Based Scheme[20]	RFD[20]	Advanced RFD
   1	1	1
   2	2	2
   3,7	3,4	3,6
   4,5	5,8	4,7
   6,10	6,10	5,9
   8,9	7,11	8,11
   11,12	9	10
   13,14	12	12,14
   Total Cost :1486.77	13	13
   	14	Totalcost: 1029.33
   	Totalcost:1260.80

   The graph in Figure 5.2 compares various techniques for same number of cells.

   1600

   1400

   1200

   1000

   800

   600

   400

   200

   0

   7 Cells 10 Cells

   12

   Cells

   Always Update

   LA based Scheme RFD

   Advanced RFD

   Table 5.3 Results for Cellular Network with 14 cells

   Here, in this section, the results of Always Update scheme with the Location Areas Scheme calculated from the algorithm with RFD and without RFD (basic) approach is compared. Two proposed RFD approach with basic LAM approach is also compared.

   1600

   1400

   1200

   1000

   Figure 5.2 Comparison of location area techniques based on number of cells in service area

   As number of cell in service area increases total location management cost also increases. It is seems that in always update case its impact is more than other techniques. RFD technique gives small difference in result for less number of cells. As the number of cell increases RFD gives better result among other technique, where as in large number of cell it gives higher difference in results compare to LA and AU technique. From this we conclude that it is more effective large number of cells.

   800

   600

   400

   200

   0

   7 Cells

   10 Cells

   12 Cells

6. CONCLUSION

   In this paper the various methodologies shows to minimize the total cost of location update and paging. With the Location Area scheme, the location update is done when a mobile user crosses location area. Location management consists of two operations: Location update and Paging. Thus, to reduce location management cost, we have to keep the balance between location update cost and paging cost.Different location management scheme have beenstudied by us. Such as location management cost using

   Figure 5.1 Grph Showing Cost Comparison for Cellular Network

   With RFD approach we found that total cost has been reduced compared to LA and AU approach. The algorithm, which we have proposed for RFD, will be enhanced to improve its current result. The graph in Figure 5.1 shows impact of total number of cells in service area to related technique.

   location area based approach, River Formation Dynamics for reducing location management cost. Andcertainly, the total location management cost isreduced as compared to always update approach. All the techniques have their advantages and can beused under different scenarios. We conclude from these results, though advanced RFD is complex in implementation with compared to LA and AU and RFD scheme.Advanced RFD is more effective for large number of cells in location management problem.

7. REFERENCES

1. A. Bar-Noy, I. Kessler and M. Sidi, Mobile users: To update or not to update? Wireless Networks, 1 (1995) 175-185.

2. BhaskarKrishnamachari and Stephen Wicker, A simple analysis of dynamic location management schemes in cellular wireless networks

3. S. Ramanathan and M. Steenstrup, A survey of routing techniques for mobile communication networks, Mobile Networks and Applications, 1 (1996) 89-104.

4. J. Jannink et ol., "Efficient and Flexible Location Management Techniques for Wireless Communication Systems," ACM/Ba/tzer J. Wireless Networks, vol.

5. Christopher Rose and Roy Yates, Minimizing the average cost of paging under delay constraints", Wireless Networks, vol. 1, no. 2, pp. 211-219, 1995.

6. EIA/TIA, Cellular radio telecommunications intersystem operations", Technical report, July 1991.

7. S. K. Sen, A. Bhattacharya, and S. K. Das, "A Selective Location Update Strategy for PCS Users," ACM/Baltzer J. Wireless Networks, vol. 5, no. 5, Sept.1999, pp. 31 3-26.

8. Foziahanif khan, nasiruddin khan, syedinayatullah and shaikhtajuddinnizami, Solving tsp problem by using genetic algorithm, International Journal of Basic & Applied Sciences IJBAS vol. 9 , no. 10,pp. 79-88.

9. A. Bar-Noy and I. Kessler, Tracking Mobile Users in Wireless Communications Networks, IEEE Transactions on Information Theory, vol. 39, no. 6, November 1993, pp. 1877- 1886.

10. Huanjing Wang and Jingyuan Zhang, Performance Comparison of Location Areas and Reporting Centers under Individualized Mobility Models

11. G. Fan and J. Zhang, Virtual Cellular Networks for Non- Uniformly Distributed Base Stations, submitted for publication.

12. S. Tabbane, An Alternative Strategy for Location Tracking, IEEE Journal onSelected Areas in Communications, vol. 13, no. 5, June 1995, pp. 880-892.

13. A. Hac and X. Zhou, Locating Strategies for Personal Communication Networks:A Novel Tracking Strategy, IEEE Journal on Selected Areas in Communications,vol. 15, no. 8, October 1997, pp. 1425-1436.

14. Vijendra Singh Bhadauria, Sanjeev Sharma and Ravindra Patel, A Comparative Study of Location Management Schemes: Challenges and Guidelines, IJCSE Vol. 3 No. 7 July 2011

15. F. G. Nocetti, I. Stojmenovic, and J. Zhang, Addressing and routing in hexagonal networks with applications for location update and connection rerouting in cellular networks, submitted for publication.

16. Pablo Rabanal, Ismael Rodríguez, and Fernando Rubio, Applying RFD to Construct Optimal Quality-Investment Trees, Journal of Universal Computer Science, vol. 16, no. 14 (2010), 1882-1901

17. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., 1979

18. Pablo Rabanal, Ismael Rodríguez, and Fernando Rubio, Solving Dynamic TSP by using River Formation Dynamics, Fourth International Conference on Natural Computation

    ,pp.246-250

19. P. Rabanal, I. Rodríguez, and F. Rubio (2013) "Testing restorable systems: formal definition and heuristic solution based on river formation dynamics". Formal Aspects of Computing, Springer, Volume 25, Number 5, pp. 743768.

20. DholakiyaDixa , prof. Prashant B. Swadas and Bharat Chawda, Location Area Management In GSM Using River

    Formation Dynamics, Sub: Gujarat Technical University

    ,International Journal of Mobile and AdHoc Network, Vol 4. Issue 2,June 2014.

21. Pablo Rabanal, Ismael Rodríguez, and Fernando Rubio, Applying River Formation Dynamics to Solve NP-Complete Problems