Transcription
Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIIMECS 2008, 19-21 March, 2008, Hong KongPerformance of AODV Routing Protocol usingGroup and Entity Mobility Models in WirelessSensor NetworksS H Manjula 1 , C N Abhilash 1 , Shaila K 1 , K R Venugopal 1 , L M Patnaik 2Abstract—Wireless Sensor Network is MultihopSelf-configuring Wireless Network consisting of sensor nodes. The patterns of movement of nodes can beclassified into different mobility models and each ischaracterized by their own distinctive features. Thesignificance of this study is that there has been verylimited investigations of the effect of mobility models on routing protocol performance such as PacketDelivery Ratio, Throughput and Latency in Wireless Sensor Network. In this paper, we have considered the influence of pursue group and randombased entity mobility models on the performance ofAd Hoc On-Demand Distance Vector Routing Protocol (AODV) routing protocol. The simulation results show that Pursue Group Mobility model is better than Random Based Entity model.Keywords: Wireless Sensor Network, Mobility models,AODV, Packet Delivery Ratio, Latency, Throughput.1IntroductionA Wireless Sensor Network (WSN) is multihop self configuring, dynamic routing, distributed autonomous wireless network. It is used for gathering information, performing data-intensive tasks such as habitat monitoring,seismic monitoring, terrain, surveillance etc. It consist ofmany small, light weight sensor nodes (SNs) called motes,deployed on the fly in large numbers to monitor the environment or a system by the measurement of physical parameters such as temperature, pressure or relative humidity. Important characteristics of a WSN are: (i)Mobilityof nodes (ii) Node failures (iii) Scalability (iv) Dynamicnetwork topology (v) Communication failures (vi) Heterogenity of nodes (vii) Large scale of deployment andUnattended operation.Mobility of sensor nodes specifies the dynamic characteristics of node movement and is one of the characteristicof wireless sensor network. Its potential use found in variety of applications ranging from vehicular networks and 1 ,Departmentof Computer Science and Engineering, University Visvesvaraya College of Engineering, Bangalore University,Bangalore 560 001. (e-mail:[email protected])† 2 Microprocessor Applications Laboratory, Indian Institute ofScience, Bangalore.ISBN: 978-988-17012-1-3 †military missions to reconnaissance. The relative movement between nodes creates or breaks wireless connections and changing the network topology. This affectsthe performance of the network and plays a vital role inthe evaluation of sensor networking protocol. The patterns of movement of nodes can be classified into differentmobility models and each is characterised by their owndistinctive features. The traditional mobility models includes (i) Random Walk Model (ii) Random WaypointModel (iii) Random Direction Model which attempt tomimic the movements of mobile objects. Such models aresimple to implement and analyze. On the otherhand, inall these randomized models, nodes choose their velocityand direction independently, with no restrictions. Hence,these models do not capture correlation between nodemovements. Recent work on mobility models attemptsto identify common mobility movements. For example,group mobility may exist in battle fields, disaster relief,or crowd migration. In the case of group mobility, little information is available on how real group mobilitypatterns look like and sometimes patterns are caused byphysical process. The drawbacks of mobility are: it relieson homogeneous velocity and acceleration bounds, whichis not at all realistic. The implications for wireless networks are rather weak, for that, the performance of thenetwork depends very much on the density of the nodesin the underlying mobility pattern.Motivation: The hosts in an Wireless Sensor Networkmove according to various patterns. Realistic models forthe motion patterns are needed in simulation in order toevaluate system and protocol performance. Most of theearlier research on mobility patterns was based on cellular networks. Mobility patterns have been used to derivetraffic and mobility prediction models in the study of various problems in cellular systems, such as hand-off, location management, paging, registration, calling time, traffic load. While in cellular networks, mobility models aremainly focused on individual movements since communications are point-to-point rather than among groups.Contribution: The main objective of this paper is to design an experimental method for explaining the most significant impacts of random based entity and group mobility model in WSN that use reactive AODV routingIMECS 2008
Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIIMECS 2008, 19-21 March, 2008, Hong Kongprotocol. This work evaluates existing entity mobilitymodel namely Random Walk, Random Waypoint, Random Direction and Pursue group mobility models. Existing reactive AODV routing protocol is used to verify theresult.Organization: The rest of the paper is organized as follows. Section II presents the Related Work. An overviewof AODV Routing Protocol, Communication Model andMobility Model is presented in Section III. Algorithmand Performance Evaluation is discussed in Section IV.In Section V, we present conclusions.2Related WorkA brief survey of performance metrics, mobility metricsand routing in WSNs is presented in this section. Ianet al., [1] present a comprehensive survey of design issues and techniques for sensor networks describing thephysical constraints on sensor nodes and the protocolsproposed in all layers of network stack. Taxonomy of thedifferent architectural attributes of sensor networks is developed in [2]. This work gives a high-level descriptionof typical sensor network architecture along with components. Sensor network are classified by considering several architectural factors such as network dynamics andthe data delivery model.Sohrabi et al., [3] have proposed Sequential AssignmentRouting algorithm which performs organization and mobility management in sensor networks. An enhanced version to identify the nodes using Global Positioning System is proposed in order to locate the position of nodes. AQoS routing protocol for sensor networks that providessoft-real time end-to-end guarantees is described in [4].The protocol requires each node to maintain informationabout its neighbors and uses geographic forwarding tofind paths. Ali et al., [5] proposed a Mobility adaptive,collision-free Medium Access Control for sensor networks.It assumes that the sensor nodes are aware of their location. This location information is used to predict themobility pattern of the nodes.Royer et al., [6] proposed Random direction model to address the non-uniform node distribution problem in therandom waypoint model. This model suffers from thesame vanishing average speed problem, the reason behind speed decay also applies random direction modeland it is observed that the average nodes speed underthis model decayed in much the same way as in the Random Waypoint model. Guolong Lin et al., [7] analyzedthe steady state distribution function of the random waypoint model. In addition to confirming the drawbacks ofthe random waypoint model and theoritical solution forthe speed decay problem was determined and provides ageneral framework for analyzing other mobility models.Bai et al., [8] used the metrics of relative motion andISBN: 978-988-17012-1-3average degree of spatial dependence to characterize thedifferent mobility models used in their study. They alsoproposed the connectivity graph metrics as a bridge relating the mobility metrics to the protocol performance.They found that average link duration at the graph levelcould explain this relationship. Broch et al., [9] evaluatesthat on-demand protocol such as Dynamic Source Routing and AODV perform better than table-driven onessuch as Destination Sequenced Distance Vector (DSDV)routing protocol at high mobility rates, while DSDV perform quite well at low mobility rates. C. Perkins [10]evaluated Ad Hoc On-Demand Distance Vector RoutingProtocol is based on the metrics like packet delivery ratioand routing overhead.33.1BackgroundAODVAd Hoc On-Demand Distance Vector Routing Protocol(AODV) is one of the most famous reactive routing protocols. In AODV, a source that intends to reach destinationfloods the whole network with a route request (RREQ)packet to search for all possible routes leading to the destination. Upon receiving the RREQ, each intermediatenode creates a reverse routing entry for the source if itdoes not have a fresh one. The intermediate node alsochecks whether it has an existing entry for the destination. If it has, a route reply (RREP) packet is generatedand unicast back to the source along the reverse route request route. Otherwise, it rebroadcasts the first receivedroute request and suppresses the duplicated ones. Whenthe destination receives the first route request or a routerequest coming from a shorter route, it sends a route replyback to the source. The nodes along the newly discoveredroutes create forward routing entries for the destinationwhen receiving the RREPs. Source and destination sequence numbers are included in the control packets androuting entries to prevent loop problems. When a routeentry is not used for a long time, it is deleted from therouting table to leave space to active entries. This protocol requires all nodes to reserve big enough memoryspaces to store possible routing entries for active sourcesand destinations. As most routes are formed on demand,network latency is quite high.3.2Communication ModelThe wireless protocol stack used by all sensor nodesand sink is explained in this section. This protocolstack combines power and routing awareness, integratesdata with networking protocols, communicates power efficiently through the wireless medium and promotes cooperative efforts of sensor nodes. The protocol stackconsists of the application layer, transport layer, networklayer, data link layer, physical layer, power managementplane, mobility management plane, and task managementplane. Depending on the sensing tasks, different types ofIMECS 2008
Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIIMECS 2008, 19-21 March, 2008, Hong Kongapplication software can be built and used on the application layer. The transport layer helps to maintain the flowof data if the sensor networks application requires it. Thenetwork layer takes care of routing the data supplied bythe transport layer. Since the environment is noisy andsensor nodes can be mobile, the MAC protocol must bepower aware and able to minimize collision with neighbors broadcast. The physical layer addresses the needs ofa simple but robust modulation, transmission and receiving techniques. In addition, the power, mobility, and taskmanagement planes monitor the power, movement, andtask distribution among the sensor nodes. These planeshelp the sensor nodes coordinate the sensing task andlower the overall power consumption.The power management plane manages how a sensor nodeuses its power. For example, the sensor node may turnoff its receiver after receiving a message from one of itsneighbors. This is to avoid getting duplicated messages.Also, when the power level of the sensor node is low, thesensor node broadcasts to its neighbors that it is low inpower and cannot participate in routing messages. Theremaining power is reserved for sensing. The mobilitymanagement plane detects and registers the movement ofsensor nodes, so a route back to the user is always maintained, and sensor nodes can keep track of their neighbor sensor nodes. By knowing the neighboring sensornodes, they can balance their power and task usage. Thetask management plane balances and schedules the sensing tasks given to a specific region. Not all sensor nodesin that region are required to perform the sensing taskat the same time. As a result, some sensor nodes perform the task more than the others depending on theirpower level. These management planes are needed, sothat sensor nodes can work together in a power efficientway, route data in a mobile sensor network, and shareresources between sensor nodes.3.3Mobility ModelMobility models play a key role during the simulation ofWireless Sensor Networks. We discuss (i) Random basedEntity mobility model (ii) Group mobility model, and(iii) Movement model below:(i) Random based M obility M odels: In random basedmobility models, the mobile nodes move randomly andfreely without restrictions. To be more specific, the destination, speed and direction are all chosen randomly andindependently of other nodes. This kind of model hasbeen used in many simulation studies. The different typesare discussed below:(a) Random W alk M obility M odel: In nature, manyentities move in extremely unpredictable ways, the Random Walk model was developed to mimic this erraticmovement. This model was originally proposed to emulate the unpredictable movement of particles in physics.ISBN: 978-988-17012-1-3The Random Walk mobility model is a widely used mobility model and it is sometimes referred to as the BrownianMotion. A mobility node (MN) moves from its currentlocation to a new location by randomly choosing a direction and speed to travel. The new speed and direction are both chosen from pre-defined ranges [speedmin,speedmax] and [2,π] respectively. Each movement in theRandom Walk mobility model occurs in either a constanttime interval t or a constant distance traveled d, at theend of which a new direction and speed are calculated. Ifan MN moving according to this model reaches a boundary area, it bounces off the boundary border with anangle determined by the incoming direction. The MNthen continues along this new path. The Random Walkmobility model is a memoryless mobility pattern becauseit doesnot retain knowledge concerning its past locationsand speed values.(b) Random W ay P oint M obility M odel: The Random Waypoint mobility model includes pause times between changes in direction and/or speed. An MN begins by staying in one location for a certain period oftime(i.e., a pause time). Once this time expires, the MNchooses a random destination in the simulation area anda speed that is uniformly distributed between [minspeed,maxspeed]. The MN then travels toward the newly chosen destination at the selected speed. Upon arrival, theMN pauses for a specified time period before starting theprocess again. The movement pattern of an MN using theRandom Waypoint mobility model is similar to RandomWalk mobility model if pause time is zero.(c) Random Direction M obility M odel: This mobilitymodel was created to overcome density waves in the average number of neighbors produced by the Random WayPoint mobility model. A density wave is the clustering ofnodes in one part of the simulation area. In this model,MNs choose a random direction to travel similar to theRandom Walk mobility model. A MN then travels tothe border of the simulation area in that direction. Oncethe simulation boundary is reached, the MN pauses for aspecified time, and chooses another angular direction [0,2π] and continues the process.(ii) Group M obility M odel: Group mobility model represents multiple MNs whose actions are completely independent of each other. Sanchez et al., [11] proposes a setof mobility models in which mobile nodes travel in cooperative manner and exhibit strong spatial dependency between near by nodes. For example, a group of soldiers in amilitary scenario may be assigned the task of searching aparticular plot of land in order to destroy land mines. Inorder to model such situations, a group mobility model isneeded to simulate this kind of characteristic. The groupmobility models include Column mobility model, Pursuemobility model and Nomadic mobility model. Here weconsider Pursue mobility model for our simulation thatis explained in next section.IMECS 2008
Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIIMECS 2008, 19-21 March, 2008, Hong Kong(iii) M ovement M odel: This model defines a mobilitymetric referred to as mobility. The mobility metric whichis geometric in the sense that the speed of a node in relation to other nodes is measured, while it is independentof any links formed between nodes in the network. Themobility metric describes the mobility of a scenario witha single value M which is a function of the relative motion of the nodes taking part in a scenario. If l(n,t) is theposition of node n at time t, the relative velocity v(x,y,t)between nodes x and y at time t isT (tx, ty)d(l(x, t) l(y, t))(1)dtThe mobility measure Mxy , between any pair (x,y) ofnodes is defined as their absolute relative speed taken asan average over the time, T, the mobility is measured.The formula for obtaining Mxy is given below.Z1Mxy v(x, y, t) dt(2)T t0 t t0 TP (xi, yi)v(x, y, t) Figure 1: Pursue Mobility ModelTable 1: Algorithm for Pursue Mobility ModelIn order to arrive total mobility metric, M, for a scenario,the mobility measure in Equation 2 is averaged over allnode pairs, resulting in the following definitionM 1nXX1 X2Mxy Mxy x, y x,yn(n 1) x 1 y x 14. If distance P (xi , yi ) distance T (tx , ty ).AlgorithmPursue mobility model and its algorithm is presented inthis section. The pursue mobility model attempts torepresent MNs tracking a particular target. For example, this model could represent the scenario where police officers attempt to catch a escaped criminal. ThePursue mobility model consists of an update equationfor the new position of each mobile node: new position old position acceleration(target old position) random vector. The current position of a MN, a randomvector, and an acceleration function are combined tocalculate the next position of the MN. Where acceleration(target old position) is information on the movementof the MN being pursued and random vector is a randomoffset for each MN. The random vector value is obtainedvia an entity mobility model. The amount of randomness for each MN is limited in order to maintain effectivetracking of the MN being pursued. Figure 1 illustratesthe movements of mobility nodes using the pursue mobility model. The white nodes represent the node being pursued and the black nodes represent the pursuingnodes.ISBN: 978-988-17012-1-32. Iterate i 1,2.,n nodes.3. Register the location of pursuing node P (xi , yi ).(3)where x, y is the number of distinct node pairs (x,y)and n is the number of nodes in the scenario. (Notethat the second relation in Equation 3 assumes nodesbeing numbered from 1 to n). The mobility expresses theaverage relative speed between all nodes in the network.Consequently, the mobility for a group of nodes standingstill, or moving in parallel at the same speed, is zero.41. Register the location of target node T (tx , ty ).5. Set the new position of P (xi , yi ) by updating current pursuing node P (xi , yi ) by acceleration and direction of previous target node position and randomoffset value.6. Until P (xi , yi ) catches the target node T (tx , ty ).The main objective of this algorithm is target tracking,that is collection of nodes P (xi , yi ), trying to chase asingle target node T (tx , ty ) as developed and is shownin Table I. Initially, register the location of the targetnode and individual pursuing node. If the distance between target node and pursuing node is more, then newposition of the pursuing node P (xi , yi ) is updated by acceleration and direction of previous target node positionand random offset value until it traces the target node.4.1Performance EvaluationThis section describes the simulation and experimentalresults of impact of mobility models on the performanceof Ad Hoc On-Demand Distance Vector routing protocol.We have selected packet delivery ratio, latency, throughput as metrics during the simulation in order to evaluatethe performance of AODV routing protocol.P acket Delivery Ratio: This is defined as the ratio of thenumber of packets received by the destinations to thosesent by the CBR sources.Latency: This is defined as the delay between the timeat which the data packet was originated at the sourceand the time it reaches the destination. Delays due toIMECS 2008
Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIIMECS 2008, 19-21 March, 2008, Hong Kongroute discovery, queuing, propagation and transfer timeare included in the delay metric.Simulation SetupWe carry out the simulation in the customized eventdriven simulator, OMNET [12], which is an objectmodular network test-bed in C . The mobility scenarios are obtained through mobility framework which is apart of OMNET distribution. The scenario generatorproduces the different mobility patterns such as Pursuegroup mobility model and Random Walk, Random Direction, Random Waypoint entity mobility models. Inall these patterns 25 hosts with 5 enabled nodes deployedin a simulation area of 700m * 700m rectangular regionfor 900s simulation time. For our study, we considereda scenario with three random based (i.e., Random Walk,Random Waypoint, Random Direction) entity mobilitymodel, Pursue group mobility model and AODV routingprotocol.The scenario is chosen in such a way that, each mobilitynode speed is varied from 1m/s to 20m/s. From thisscenario we compare the performance of AODV routingprotocol using entity and group mobility models. TheMAC layer protocol IEEE 802.11 is used in simulationwith the data rate 11Mbps. The data traffic source tobe a Constant Bit Rate (CBR) source. The sending rateis set to three packets per second, the network containsone source and one destination, each message packet sizeof 512 bytes is defined. The Table II provides all thesimulation parameter values.Packet Delivery Ratio DIRPURSUE4321005101520Speed (m/s)Figure 3: Latency and SpeedRWRWPRDIRPURSUE8e 067e 06Throughput700m * te1MB20Figure 2: Packet Delivery Ratio and SpeedTable 2: Summary of the communication parameter values for Simulation scenariosMap SizeChannel BandwidthChannel DelaySimulation TimeNo. of Enabled NodesNumber of HostsPacket RateBurst lengthMessage Packet SizeInput Buffer Size15Speed (m/s)LatencyT hroughput: The throughput data reflects the effectivenetwork capacity. It is defined as the total number of bitssuccessfully delivered at the destination in a given periodof time.16e 065e 064e 063e 062e 0604.3510Speed (m/s)1520Results and AnalysisFrom the simulation results, we compare random basedentity models and pursue group model which significantlyISBN: 978-988-17012-1-3Figure 4: Throughput and SpeedIMECS 2008
Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol IIIMECS 2008, 19-21 March, 2008, Hong Konginfluences the performance metrics such as Packet Delivery Ratio, Latency, and Throughput of AODV reactiverouting protocol. The results obtained from the scenariois discussed below.The scenario is based on speeds of nodes varying from1m/s, 5m/s, 10m/s, 15m/s, 20m/s of mobility models.Figure 2 describes the variation of Packet Delivery Ratio with the speed. As the speed increased from 1m/sto 5m/s Random Waypoint model decreases drasticallybecause of packet loss. By comparing all random basedmobility models, the pursue group mobility model showsconsistent packet delivery ratio as node speed increasedfrom 1m/s to 20m/s.Figure 3 gives the variation of Latency with speed. Random Waypoint model takes 40% more time to transmit packets as the speed increases upto 10m/s. At anode speed 20m/s, Random Direction model and Pursuemobility model shows better performance than RandomWaypoint mobility model. Pursue mobility model experiences 0.1% of consistent time delay as the node speed isincreased from 1m/s to 20m/s. This infers pursue mobility model takes less duration to transmit the data amongall mobility models.Figure 4 shows the variation of Throughput with speed.The throughput of Random Direction model and Random Waypoint mobility model decreases drastically atnode speed 5m/s. It is noticed that, Random Directionmodel and Pursue group mobility model starts convergingas the node speed increases from 10m/s, shows that improvement in Random Direction model in data throughput. From the simulation result, pursue mobility modelresults in consistent data throughput with variation ofspeed.5Conclusions and Future WorkWSN is gaining importance in the real world becauseof its applications. In this paper, the simulation results demonstrates the evaluation of performance ofAODV routing protocol with random based entity mobility model and pursue group mobility model. The performance metrics are Packet Delivery Ratio, Latency, andThroughput. We intend to show that the choice of mobility models makes the difference with respect to networkperformance. We have considered a scenario by varying the speed of the individual nodes. The pursue groupmobility model performs better than random based entity mobility models. Other mobility patterns such asFreeway, Manhattan, Column group mobility model, CitySection models will be used to illustrate realistic situations, in the future works.ISBN: 978-988-17012-1-3References[1] Ian F. Akylidiz, Weilian Su, Yogesh Sankarasubramaniam, and E. Cayirci. “Wireless Sensor Network:A Survey on Sensor Networks,” IEEE Communication Magazine, V40, N8, pp. 102-114 8/02.[2] S. Tilak, Nael B. Abu-Ghazaleh, Wendi Heinzelman. “A Taxonomy of Wireless Microsensor Network Models,” Mobile Computing and Communications Review, V6, N2, pp. 28-36, 2002.[3] K. Sohrabi, J. Gao, V. Ailawadhi and G. J. Pottie. “Protocols for Self-Organization of Wireless Sensor Network,” IEEE Personal Communication Magazine, V7, N5, pp.16-27, 10/00.[4] T. He, John Stankovic, Chenyang Lu, Tarek Abdelzaher. “SPEED: A stateless protocol for RealTime Communication in Sensor Networks,” Proceedings of Int Conf on Distributed Computed Systems,Providence, RI, 5/03.[5] M. Ali, T. Suleman, and Z. A. Uzmi. “MMAC:A Mobility-adaptive, Collision-free MAC Protocolfor Wireless Sensor Networks,” Proceedings of 24thIEEE IPCCC, 2005.[6] E. Royer and P. Melliar-Smith and L. Moser. “AnAnalysis of the Optimum Node Density for Ad hocMobile Networks,” Proceedings of IEEE Int Conf onCommunications (ICC), Helsinki, Finland, 6/01.[7] Guolong Lin, Guevara Noubir, and Rajmohan Rajamaran. “Mobility Models for Ad-hoc Network Simulation,” Proceedings of INFOCOM, 2004.[8] F. Bai, N. Sadagopan, and Ahmed Helmy. “The IMPORTANT Framework for Analyzing the Impact ofMobility on Performance of Routing Protocols forAd hoc Networks,” IEEE Information Communications Conference, INFOCOM, pp. 825-835, 4/03.[9] J. Broch, D. Maltz, D. Johnson, Y. Hu, and J.Jetcheva. “A Performance Comparison of MultiHop Wireless Ad Hoc Netowrk Routing Protocols,”Proceedings of the Fourth Annual ACM/IEEE IntConf on Mobile Computing and Networking (MOBICOM), pp. 85-97, 10/98.[10] C. Perkins. “Ad Hoc on Demand Distance Vector(AODV) Routing IETF,” Internet Draft: draft-ietfmanet-aodv-00.txt, 11/97.[11] san/mobmodel, 2000.URL:[12] Andras Varga. Technical University of Budapest,Department of Telecommunications(BME-HIT). “OMNET Simulator,” URL:http://www.omnetpp.org/tutorial, 2003.IMECS 2008
Group and Entity Mobility Models in Wireless Sensor Networks S H Manjula 1, C N Abhilash 1, Shaila K 1, K R Venugopal 1, L M Patnaik 2 † Abstract—Wireless Sensor Network is Multihop Self-configuring Wireless Network consisting of sen-sor nodes. The patterns of movement of nodes can be classified i
