EVALUATION AND IMPROVEMENTS TO MOTION GENERATION IN NS2 FOR WIRELESS MOBILE NETWORK SIMULATION

International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) Evaluation and Improvements to Motion Generation in ns2 for Wireless Mobile Network Simulation Raid Alghamdi, John DeDourek, Przemyslaw Pochec Faculty of Computer Science University of New Brunswick Fredericton, Canada E-mail: r.alghamdi, dedourek, pochec@unb.ca ABSTRACT Simulation of mobile networks requires reliable movement generation. Evaluation of the performance of the existing random movement generator used in ns2 shows a bias for placing the mobile nodes in the center of the experimental area. Applying the quadrat count and the VMR tests confirms the tendency for clustering of nodes. To remedy this problem we propose, and implement a different method for random movement generation for use with the ns2 simulator, and show that our movement generator improves the randomness of the node distribution during the simulation. Keywords Movement generator; network simulation; setdest utility; MANET; VMR; Quadrats Count. 1 INTRODUCTION Communication networks in general divide into to two main categories: wired and wireless. Wired networks exist between a number of devices connected to each other using connecting media, such as cables and routers. Wired networks can be applied within an area limited by the cables and routers that allow for sending and receiving of data. Wireless networks, on the other hand, are free of such space limitations, and are more easily able to connect different devices to each other. Wireless nodes can play the roles of both hosts and routers, which forward the packets to neighboring nodes. The mobile ad hoc network (MANET) is a subcategory of ad hoc networks. “With the advent of newer technologies, mobile ad hoc networks are becoming an integral part of next- generation networks because of its flexibility, autoconfiguration capability and lack of infrastructure, ease of maintenance, selfadministration capabilities, and costeffectiveness” [1]. A MANET contains mobile nodes that can be connected wirelessly to each other, for example through either Wi-Fi or Bluetooth. Nodes can be connected over wireless links in ad hoc fashion without central control; this is one of the main advantages of MANETs. In addition, MANET is dynamic and does not rely on fixed or static structure. Consequently, the frequent changes that occur in network topology play a very important role in mobile ad hoc network protocols’ performance [1]. MANET consist of mobile nodes, and these nodes move in the space following a pattern based on user preferences, or are by following an algorithm that can be for example: random or uniform. There are many mobility models for ad hoc networks. The structure of this paper is as follows. In Section 3 we discus different movement models for MANETs, including the setdest utility used in ns2. In Section 4 we introduce performance measures for evaluating a movement generator. In Section 5 we present a new movement generator, performance of the new generator is in Section 6. 2 APPROACHES TO INVESTIGATING NETWORK PERFORMANCE Each new network has to be investigated and evaluated before the network can be opened for regular use. By evaluating network 84 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) performance, the errors in network operation can be detected and corrected before the network is put to use. There are three approaches that can be followed to investigate the network performance: empirical study, analytical modeling, and simulation. In an empirical study, the actual network is used under a controlled environment. Test users that behave like real users are needed. Performance is measured by observing the actual network in use. The main inconvenience of this approach is that the entire network or a significant portion thereof must be built, which can be both difficult and expensive. In an empirical study, the actual network is used under a controlled environment. Test users that behave like real users are needed. Performance is measured by observing the actual network in use. The main inconvenience of this approach is that the entire network or a significant portion thereof must be built, which can be both difficult and expensive. Analytical modeling is a tool that uses analytical techniques to predict network performance. Using mathematical formulae to calculate interactions that might happen between different network entities allows us to predict network performance. Analytical models help to detect errors that might occur while the network is operational so that they can be solved before the actual network is constructed. Analytical modeling should be done using onedimensional and two-dimensional tests with both static and dynamic situations for topology. Simulation is testing using a computer program to track the behaviour of a network. Simulation includes protocol simulation, movement simulation, and traffic generators. Network simulation helps determine how a real network would function and helps predict the networks behaviour. Several programming languages and simulators are used for network simulation, such as Java, C, or ns2; in this report, however, we focus on ns2 and Java only. 3 MOVEMENT TYPES USED IN MANETS The mobility models for MANETs can be grouped into two categories: random movement models (which will be discussed late in this paper) and uniform movement models. The uniform movement models contain four well known models Boundless Simulation Area Mobility Model, Gauss-Markov Mobility Model, A Probabilistic Version of the Random Walk Mobility Model, and City Section Mobility Model [8]. First, a boundless simulation area model is based on the velocity of the mobile node of the current direction and the previous direction [3]. This model has a feature of handling the boundaries of the simulation where some of the other models are stopping or bouncing off once the simulation get to the boundary [8]. A Gauss-Markov Mobility Model looks like a random model but in fact it is not because it follows a pattern that could be expected [8]. The Gauss-Markov model is calculating two main parameters of each mobile node which are speed and direction at a certain instance based on last instance’s update [8, 17, 18]. The Probabilistic Version of the Random Walk Mobility Model is a model uses the probability to determine the next position by knowing number of states of each position [8, 19]. The probability of the Probabilistic model is going higher once the mobile node keeps following the previous direction but not if the direction changed [8]. Finally, City Section Mobility Model is a realistic movement model that show as a grid of a columns and rows streets to represent the streets using limited velocity for each particular area on the grid to move around these areas using the streets. In City Section Mobility model the mobile nodes start moving from some defined points in the grid and then moving to some chosen destinations randomly [8, 7]. Random Movement The Random mobility models used in MANETs differ in the way the nodes move. These different movement types are: Random 85 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) Walk, Random Waypoint and Random Direction. Each mobile node in Random Walk has a randomly generated starting position. The nodes travel from their starting position to a randomly generated new location by generating random direction and velocity. The velocity has to be bounded by minspeed and maxspeed values and the direction also has to be in range between 0 and 2π [8]. A node changes direction and speed either at the end of a time interval t or if it traveled a distance d. In Random Waypoint, the movement is not constant whereas pause times are introduced. The nodes start at randomly chosen positions, then "pause" for some time and then start moving in a uniformly distributed velocity between minspeed and maxspeed towards a chosen destination. The nodes in this model have to "pause" for some time before they change direction or speed [8]. The drawback in Random Waypoint is clustering near the center (i.e. having the nodes near each other near the center of the experimental area). Random Direction Mobility model was introduced to overcome this drawback in the Random Waypoint model. In Random Direction model, a node travels at a chosen velocity in a chosen direction until it reaches the boundaries of the area rather that until it reaches a randomly chosen location. Once a node hits the boundaries it pauses for a time t and chooses a new direction and starts moving in this new direction again, and so on [6]. ns2 Setdest Utility Setdest is a tool used to generate nodes’ movements for the mobile nodes in the network simulation ns2 by positioning network nodes in a bounded area and setting the movement in a random direction [9, 10]. Setdest tool uses the random waypoint mobility model algorithm to create the random movements for the mobile nodes [11, 9, 20, 10]. There are two versions of setdest tool can be used in the ns2 known as –v 1 and –v 2 where version 2 is the latest[21]. Setdest version v1 is using the parameters, number of nodes, pause time, maximum speed of the movement, simulation time, x coordinate, and y coordinate. This version is used in the study that is shown in this paper (the version v2 uses slightly different parameters than the version v1 which are: number of nodes, maximum speed, minimum speed, speed type, pause time type, simulation time, x coordinate, and y coordinate) [21, 14]. 4 INVESTIGATING MOVEMENT GENERATOR PERFORMANCE The movement generator will be tested in two ways: by evaluating the randomness of the position of mobile node at different times in the course of simulation, and by comparing delivery ratio in a MANET in different regions of the simulated experimental area. Randomness Performance For testing the randomness performance we will use the Quadrats Count methodology and the Variance to Mean Ratio (VMR). The Quadrats Counts methodology is an established technique used for analyzing the spatial point patterns that there is an area by dividing this area into a certain number of sub-areas and then counting the number of points in each sub-area independently [15] The Variance to Mean Ratio is a statistical test that describes the spatial distribution. We calculate the mean x , and the variance s 2 , of the number of points (network nodes) in each subarea in the Quadrats Count method. The closer the ratio is to 1 the more the points are randomly distributed. Delivery Ratio We tested the boundary effect (i.e. changes in nodes density along the edges of experimental area) by using a random movement to set up the simulation and transmitting the packets through the center and also transmitting the packets along the edges. We used a CBR (constant bit rate) traffic over UDP, using AODV routing, 86 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) and counted the total number of bytes delivered at the destination node. The higher the delivery ratio for transmission along the edges, the better the movement generator. 5 CUSTOM JAVA MOVEMENT GENERATOR The setdest utility uses the random waypoint mobility model algorithm. The waypoint algorithm is known to have the border effect, which creates a kind of clustering at the center of the simulation area [6]. The border effect problem can be avoided by following a different algorithm called the boundless simulation area mobility model. The main idea of the boundless model is to allow going over the edges thus avoiding the influence of the simulation area’s edges. Moreover, going over the edges in the boundless simulation means that once the mobile node reaches the boundary from any side of the simulation area, it does not bounce the same as in the other models, but it disappears from the side and appears from the other side continuing with the same direction, which makes the simulation area look more like a tube than a plane. Figure 1 shows the simulation area that looks like this. Figure 1. Simulation area of Boundless Simulation Area Mobility Model shown as a tube. In our random generator, we used this method to avoid the border effect without affecting the randomness of node movement. Since the ns2 tool is based on TCL object oriented programming language, we decided to use the Java programming language to build the new random generator. The new random generator we built generates a file readable by ns2 that has all the movements of all the nodes during the simulation time. The Java code firstly generates the initial random positions of the nodes giving them a random value for the x Coordinate between zero and xMax, a random value for the y Coordinate between zero and yMax, and z Coordinate equal to zero at all times for all nodes, where xMax and yMax are entered by the user along with the simulation time. These initial coordinates of x, y, and z have to follow a specific format that allows ns2 to read it correctly. The following is an example of the initial random position of one node in ns2 TCL format: $node_(0) set X_ 323.81544267544473 $node_(0) set Y_ 576.9394231828528 $node_(0) set Z_ 0.000000000000 After setting the initial positions of the nodes randomly, it is the time to create the nodes’ movements considering four main parameters which are xEdgeMax, yEdgeMax, the simulation time and the maximum value of the interval Max_Movement. The node movements’ commands can be in one of two main formats. The first format is used for the node that does not reach the boundary and uses the setdest statement to specify the time, node number, xCoordinate, yCoordinate and speed. For the nodes that jump from one side to the other we used the “setpos” instead of “setdest”. Moreover, in this format there is no speed because the node disappears from one side and shows up on the other side at the same time and before it starts moving again to the new destination. The time parameter in setdest command is chosen randomly between 0.0 and simulation time for each node for all. Moreover, the time for each move for a single node is depending on the time for the move right before it and for the same node. First, the initial time for each node has a unique interval which is a random value between the 0.0 and 5.0 to keep the initial pause of the movement as small as possible. The following equation is showing how the initial node time calculated: 87 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) Second, for all the other moves, the time is increases with a random value interval between 0.0 and 15.0, and the only difference between the second move and the rest of moves is that the time for the second move will be added to the initial time. The following equation is showing just how the second move of a node that had an initial time calculated: Third, for all the movements from the third move on, time will follow the following equation: Time is not the only random dynamic parameter in the movement commands; the new position which includes the xCoordinate and yCoordinate is also a random dynamic parameter. Generating new positions for the nodes is based on two parameters the angle and the random interval. Firstly, before generating a new position for a node, a random angle between 0 and 360 degrees has to be chosen based on the current position of the node using the following equation: the previous equations: coordinates following the The speed in the custom generator is calculated based on four main parameters which are xCurrent, yCurrent, xOld, yOld, CurrentT and NewMovementT. Since we have these parameters we can calculate the time for the current movement to reach the new position at exactly the specified time with the calculated speed using the equation: The pseudocode shown in Algorithm 1 describes in details the operation of our new custom movement generator. Finally, as described before, the movements’ commands can be for either a node that does not cross the border(s) or a node that does cross the border. The nodes that do not go across the border(s) will have just one generated movement command as in the following example: $ns_ at 63.9044770629 "$node_(0) setdest 118.0254566085 271.9530117172 9.0480031906" Once the angle is chosen, using the maximum value of the interval from the user input, we can calculate the new xMax and yMax which are the end coordinates of the interval using the following equations: After determining the xMax and yMax now we can calculate the new destination for a node that based on three main things which are the angle degree, Max_Movement and xMax and yMax by adding the new x and y coordinates to On the other hand, the nodes that go across the border(s) will have three movement commands. The first line represents the movement from the current position to the border, the second line represents the jump from one border to the opposite border and the last line represents the movement from the border after the jumping to the destination. 88 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) ___________________________________________________________________________________ Algorithm 1 Pseudocode (Custom Generator) __________________________________________________________________________________________ (maxX, maxY) = simulation area dimensions maxTime = max duration of node’s movement maxMovement = max distance of node’s movement currentTime = 0 (currentX, currentY) = random position while Simulating do angle = rand(0..1) * 360_ destX = rand(0..1) * cos(angle) * maxMovement //set the movement destination destY = rand(0..1) * sin(angle) * maxMovement MovementTime = rand(0..1) * maxTime speed = geometric distance (currentX, currentY) to (destX, destY)/movementTime if path does not cross the boundary then writeMovement ($ns at current Time ”$nodeX setdest destX, destY, speed”) else if path crosses the boundary then (interceptX, interceptY) = boundary intercept distToBound = geometric distance to the boundary in the direction of the movement path writeMovement ($ns at currentTime ”$nodeX setdest interceptX, interceptY, speed”) timeAtBoundary = currentTime + distToBound/speed writeMovement ($ns at timeAtBoundary ”$nodeX setpos interceptX, interceptY”) destX = destX % maxX destY = destX % maxY writeMovement ($ns at timeAtBoundary ”$nodeX setdest destX, destY, speed”) (currentX, currentY) = (destX, destY) currentTime = currentTime + movementTime end if end if end while ___________________________________________________________________________________ The following is an example of the generated three commands by the custom random generator which represent the movement that has a jump from one border to the other through the movement. movement to be exactly the same before the jump and after it. Figure 2 is showing the three movements that happen once the node across the border(s) generated by the custom random generator. $ns_ at 102.7793520501 "$node_(0) setdest 247.5787955052 0.0000000001 12.2737968543" $ns_ at 113.2993853283 "$node_(0) setpos 247.5787955052 999.9999999999 " $ns_ at 113.2993853283 "$node_(0) setdest 247.9845265892 998.3574128920 12.2737968543" This custom random movement generator is built in Java and its output is compatible with the ns2 to generate the node movements. Also, the custom movement generator generates a trace file that has the following parameters: The speed of movement is the same in the first and the third line which are making the 89 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X)  Movement type either Regular Movement (M) or Jump (J)  Node Number  Time  Difference in time between the two movements.  Speed of the movement.  Current xCoordinate  Current yCoordinate  Next xCoordinate  Next yCoordinate Figure 2. Three steps those nodes have to follow once they reach boundary 6 RESULTS In this paper, we have investigated the randomness performance and the packets transmission of both generators the setdest utility and the custom generator. The randomness performance of both generators is shown in the Figure 3. In this figure, the VMR values represent the randomness in the distribution of mobile nodes at different times in the simulation. The results obtained with the custom generator are closer to the VMR value of one than the values obtained from using the setdest utility. Taking in to account the main deficiency of the setdest utility, which is the tendency of placing the mobile nodes in the center of the simulation area we investigated the packet transmissions in a simulated mobile networks controlled by both generators in two ways: we measured transmitting the packets through the center and along the edges of the simulated area. Once the packets were transmitted through the center, there was no significant difference between the movement generators while using the 60 nodes, but with the 30 and 20 nodes there were significant differences with the setdest utility allowing for more packets to be delivered suggesting some clustering of nodes in the center (Table 1).Transmitting the packets along the edges (results are shown in Table 2), we observed a significant difference between the two generators the in the experiments with 30 and 60 nodes. For example, in the transmitting through the centre experiments with 30 nodes we observed on average 7453 packets delivered in the scenarios generated with setdest utility vs 5600 packets in the case when our custom generator was used. For the same scenarios, transmissions along the edges gave 716 vs 2031 packets received. This shows a strong bias for packet delivery in the centre of the experimental area for the setdest utility: 7543 in the center vs 716 along the edges, almost 10 to 1 ratio. Similar comparison for the new generator gives only 2 to 1 ratio (5600 vs 2031). Figure 3. Comparison of the 101 means (of five VMR runs) of the setdest utility and the custom generator. 90 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) Table 1. The confidence interval result of the delivery ratio through the center for both generators Setdest Utility Custom Generator 60 Nodes 9459.907005 TO 9731.892885 9371.082322 TO 9610.517678 30 Nodes 6724.788306 TO 8182.211694 5150.647877 TO 6050.352123 20 Nodes 2945.226379 TO 4811.973621 1325.714676 TO 2448.285324 Table 2. The confidence interval result of the delivery ratio along the edges for both generators Setdest Utility Custom Generator 60 Nodes 3664.285794 TO 4802.914206 7933.676792 TO 8238.223208 30 Nodes 478.0674426 TO 955.5325574 1712.377421 TO 2351.922579 20 Nodes 193.966817 TO 576.433183 197.3408355 TO 468.9591645 Overall the simulation with the custom generator delivered packets better and more uniformly than the setdest utility as illustrated in Figure 4 and 5. Figure 5: Snapshot of the Setdest Utility at second 26. 7 CONCLUSION We investigated the performance of the popular setdest utility used in the ns2 network simulator. The movement generated with setdest utility tends to cluster the mobile nodes in the center of the experimental area. This has an effect on the VMR coefficient used to measure randomness of the positions of points in the simulation. We proposed and demonstrated the advantage of new random motion generator for use in ns2 simulator. Testing the new generator shows a marked advantage over the standard setdest utility. ACKNOWLEDGEMENT This work is sponsored and funded by the Ministry of Higher Education of Saudi Arabia through the Saudi Arabian Cultural Bureau in Canada. 8 REFERENCES 1. Figure 4: Snapshot of the Custom Generator at second 26. 2. 3. R. Suprio, “Realistic mobility for MANET simulation,” Master’s thesis, The University of British Columbia, 2003. Wikipedia, the free encyclopedia (November 2009), Basic Station, http://en.wikipedia.org/wiki/Base_station (accessed May 2011) Z. J. Haas, "A new routing protocol for the reconfigurable wireless networks," in Universal 91 International Journal of Digital Information and Wireless Communications (IJDIWC) 2(4): 84-92 The Society of Digital Information and Wireless Communications, 2012 (ISSN: 2225-658X) 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Personal Communications Record, 1997. Conference Record. 1997 IEEE 6th International Conference on 12-16 Oct 1997, vol.2, pp. 562-566. Wikipedia, the free encyclopedia (November 2010), Wireless Ad-hoc Network, http://en.wikipedia.org/wiki/Wireless_adhoc_network (accessed Nov 2011) N. S. Dalton and R. C. Dalton, “The theory of natural movement and its application to the simulation of mobile ad hoc networks (MANET),” in Proc. the Fifth Annual Conference on Communication Networks and Services Research, 2007, pp. 359–363. Y. Zhang and W. Li, “An integrated environment for testing mobile ad-hoc networks”, in Proc.the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '02), Lausanne, Switzerland, June 2002, pp. 104-111. V. Davies, “Evaluating Mobility Models Within an Ad Hoc Network,” Master’s thesis, Colorado School of Mines, Colorado, 2000. T. Camp, J. Boleng, and V. Davies, “A survey of mobility models for ad hoc network research,” Wireless Communications & Mobile Computing, Special Issue on Mobile Ad Hoc Networking: Research,Trends and Applications, vol. 2, no. 5, pp. 483–502, 2002. B. J. Culpepper and H. C. Tseng, “Sinkhole intrusion indicators in DSR MANETs”, in Proc. First International Conference on Broad band Networks, 2004, pp. 681 – 688. N. Frangiadakis, M. Kyriakakos, S. Hadjiefthymiades, and L. Merakos, "Realistic mobility pattern generator: design and application in path prediction algorithm evaluation," in Proc. Personal, Indoor and Mobile Radio Communications, 2002. The 13th IEEE International Symposium on 15-18 Sept. 2002, vol.2, pp. 765- 769. P. Caballero-Gil, C. Caballero-Gil, J. Molina-Gil, and C. Hernandez-Goya, “A simulation study of new security schemes in mobile Ad-hoc NETworks,” in EUROCAST 2007. LNCS, vol. 4739, R. Moreno D´ıaz, F. Pichler, A. Quesada Arencibia, Ed., Heidelberg: Springer, 2007, pp. 73–81. J. Hu and R. Marculescu, “DyAD: smart routing for networks-on-chip,” in Proc. the 41st annual conference on Design automation, San Diego, CA, USA, June 07-11, 2004, pp. 260-263. A. L. Cavilla, “MANET extensions to ns2”. Available: http://www.cs.toronto.edu/∼andreslc/software/MAN ET extensions.tgz. B. Carbone, “Routing Protocols for Interconnecting Cellular and Ad Hoc Networks”, Master’s thesis, 15. 16. 17. 18. 19. 20. 21. Universite Libre De Bruxeles , Faculte des Sciences, Department ‘d Informatique, 2006. J. Illian, A. Penttinen, H. Stoyan, and D. Stoyan, Statistical analysis and modelling of spatial point patterns. West Sussex, England: John Wiley & Sons Ltd, 2011. R. R. Roy, “Handbook of mobile ad hoc networks for mobility models (1st Ed.)”. New York, NY: Springer Science Business Media, 2011. J. Ariyakhajorn, P. Wannawilai, and C. Sathitwiriyawong, "A Comparative Study of Random Waypoint and Gauss-Markov Mobility Models in the Performance Evaluation of MANET," Communications and Information Technologies, 2006. ISCIT '06. International Symposium on , vol., no., pp.894-899, Oct. 18 2006-Sept. 20 2006, pp. 894-899. B. Liang and Z. J. Haas, "Predictive distance-based mobility management for PCS networks," INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , vol.3, no., pp.13771384 vol.3, 21-25 Mar 1999, vol.3, pp. 1377-1384. C. Chiang, “Wireless Network Multicasting”. Ph.D. thesis, University of California, Los Angeles, 1998. F. Bai and A. Helmy, “A Survey of Mobility Models in Wireless Ad hoc Networks”, in Wireless Ad Hoc and Sensor Networks, Chapter 1, Kluwer Academic Publishers, June 2004, pp. 1-29. M. Pascoe, J. Gomez, V. Rangel, and M. LopezGuerrero, Route duration modeling for mobile adhoc networks. ACM Wireless Networks Journal (WiNet), 16(3), pp. 743–757, 2010, pp. 743-757. 92