International Journal of Innovative Research in Computer and Communication Engineering
MenuISSN ONLINE(2320-9801) PRINT (2320-9798)
ISSN ONLINE(2320-9801) PRINT (2320-9798)
Anwar Ahsan1, U T Nagdeve2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering
We present Ravenous Perimeter Stateless Routing (RPSR), a novelrouting protocol for wireless datagram networks that uses the stateof routers and a packet's target to make packet forwardingdecisions. RPSR makes ravenousforwarding decisions usingonly information about a router's immediate neighbors in thenetwork topology. When a packet reaches a region where ravenous forwarding is unfeasible, the algorithm recovers by routing in the order ofthe perimeter of the region. By keeping state only a propos the localtopology, RPSR scales better in per-router state than shortest-pathand ad-hoc routing protocols as the number of network targetsincreases. Under mobility's frequent topology changes;RPSR canuse local topology information to find correct new routes quickly.We describe the RPSR protocol, and use extensive simulation of portable wireless networks to compare its performance with that ofDynamic Source Routing (DSR). Our simulations demonstrate RPSR'sscalability on densely deployed wireless networks
Keywords |
| ad-hoc Network, wireless routing, Stateless Routing, geographic routing's ,data packets,mobile networksforwarding decisions. |
INTRODUCTION |
| In networks comprised entirely of wireless stations, communicationbetween source and target nodes may require traversalof multiple hops, as radio ranges are finite. A community of ad-hocnetwork researchers has proposed, implemented, and measureda variety of routing algorithms for such networks. The observation hat topology changes more quickly on a mobile, wireless networkthan on wired networks, where the use of Distance Vector(DV), Link State (LS), and Path Vector routing algorithms is wellestablished,motivates this body of work.DV and LS algorithms require continual circulation of a currentmap of the entire network's topology to all routers. DV's Bellman-Ford approach constructs this global picture transitively; each router consist its distance from all network targets in each ofits intermittentbeacons. LS's Dijkstracome up to directly floods announcementsof the change in any link's status to every router in the network. Small inaccuracy in the state at a router under both DVand LS can cause routing loops or detachment. When thetopology is in invariableflux, as beneath mobility, LS generates torrentsof link status change messages, and DV either suffers from out of date state, or generates torrents of triggered updates. |
| The two dominant factors in the scaling of a routing algorithm are: |
| ïÃâ÷ Value of rate of changes of topology. |
| ïÃâ÷ Total number of routers in the routing area. |
| ïÃâ÷ Both factors affect the message complexity of DV and LS routingalgorithms: intuitively, pushing current state globally costs packetsproportional to the product of the rate of state change and numberof targets for the updated state. |
| Hierarchy is the most widely deployed approach to scale routing asthe number of network targets increases. Without hierarchy,Internet routing could not scale to support today's number of Internetleaf networks. An Autonomous System runs an intra-domainrouting protocol inside its borders, and appears as a single entity in the backbone inter-domain routing protocol, BGP. This hierarchyis based on well-defined and rarely changing administrativeand topological boundaries. It is therefore not easily applicable to freely moving ad-hoc wireless networks, where topology has no well-defined AS boundaries, and routers may have no common administrativeauthority. |
| Caching has come to prominence as a strategy for scaling ad-hocrouting protocols. Dynamic Source Routing (DSR), Ad-HocOn-Demand Distance Vector Routing (AODV) , and the Zone Routing Protocol (ZRP) all eschew constantly pushing currenttopology information network-wide. Instead, routers running theseprotocols request topological information in an on-demand fashionas required by their packet forwarding load, and cache it aggressively.When their cached topological information becomes out-of-date,these routers must obtain more current topological informationto continue routing successfully. Caching reduces the routingprotocols' message load in two ways: it avoids pushing topologicalinformation where the forwarding load does not require it (e.g., atidle routers), and it often reduces the number of hops between therouter that has the needed topological information and the routerthat requires it (i.e., a node closer than a changed link may alreadyhave cached the new status of that link).We propose the aggressive use of geography to achieve scalabilityin our wireless routing protocol, Ravenous Perimeter Stateless Routing (RPSR). We aim for scalability under increasing numbers ofnodes in the network, and increasing mobility rate. As these factorsincrease, our measures of scalability are: |
| ïÃâ÷ Routing protocol message cost: How many routing protocol packets does a routing algorithm send? |
| ïÃâ÷ Application packet delivery success rate: What fractions of applications’ packets are delivered successfully by a routing algorithm? |
| ïÃâ÷ Per-node state: How much storage does a routing algorithm require at each node? |
| Networks that push on mobility, number of nodes or both contains: |
| ïÃâ÷ Ad-hoc networks: Perhaps the most investigated category, these mobile networks have no fixed infrastructure, and support applications for military users, post-disaster rescuers, and temporary collaborations among temporary associates. |
| ïÃâ÷ Sensor networks: Comprised of small sensors, these mobile networks can be deployed with very large numbers of nodes, and have very impoverished per-node resources. Minimization of state per node in a network of tens of thousands of memory-poor sensors is crucial. |
| ïÃâ÷ Rooftop. networks: Proposed by Sheppard, these wireless networks are not mobile, but are deployed very densely in metropolitan areas (the name refers to an antenna on each building's roof, for line-of-sight with neighbors) as an alternative to wired networking offered by traditional telecommunicationsproviders. Such a network also provides an alternate infrastructure in the event of failure of the conventionalone, as after a disaster. A routing system that selfconfigures (without a trusted authority to configure a routing hierarchy) for hundreds of thousands of such nodes in a metropolitan area represents a significant scaling challenge. |
| Traditional shortest-path (DV and LS) algorithms require state proportional to the number of reachable targets at each router.On-demand ad-hoc routing algorithms require state at least proportionalto the number of targets a node forwards packetstoward, and often more, as in the case in DSR, in which a node aggressivelycaches all source routes it overhears to reduce the propagationscope of other nodes' flooded route requests. We will show that geographic routing allows routers to be nearlystateless, and requires propagation of topology information for onlya single hop: each node need only know its neighbors' positions.The self-describing nature of position is the key to geography'susefulness in routing. The position of a packet's target andpositions of the candidate next hops are sufficient to make correctforwarding decisions, without any other topological information. We assume in this work that all wireless routers know their ownpositions, either from a GPS device, if outdoors, or through othermeans. Practical solutions contain surveying, for stationary wireless routers; inertial sensors, on vehicles; and acoustic range-finding usingultrasonic .chirps. indoors. We further assume bidirectionalradio reach ability. The widely used IEEE 802.11 wirelessnetwork MAC [11] sends link-level acknowledgements for all unicastpackets, so that all links in an 802.11 network must be bidirectional.We simulate a network that uses 802.11 radios to evaluateour routing protocol. We consider topologies where the wirelessnodes are roughly in a plane. Finally, we assume that packetsources can determine the locations of packet targets, to markpackets they originate with their target's location. Thus, weassume a location registration and lookup service that maps node addresses to locations. Queries to this system use the samegeographic routing system as data packets; the querier geographicallyaddresses his request to a location server. The scope of thispaper is limited to geographic routing. We argue for the eminentpracticality of the location service briefly in Section 3.7. We adopt IP terminology throughout this paper, though RPSR can be applied to any datagram network. In the following sections, we describe the algorithms that comprise RPSR, measure and analyze RPSR's performance and behavior in simulated mobile networks, cite and differentiate related work, identify future research opportunities suggested by RPSR, and conclude by summarizing our findings. |
 |
II. ALGORITHMS AND EXAMPLES |
| We now describe the Ravenous Perimeter Stateless Routing algorithm.The algorithm consists of two methods for forwarding packets:ravenousforwarding, which is used wherever possible, and perimeterforwarding, which is used in the regions ravenous forwarding cannot be. |
II.IRavenous Forwarding |
| As alluded to in the introduction, under RPSR, packets are marked by their originator with their targets' locations. As a result,a forwarding node can make a locally optimal, ravenous choice in choosing a packet's next hop. Specially, if a node knows its radioneighbors' positions, the locally optimal choice of next hopis the neighbor geographically closest to the packet's target.Forwarding in this regime follows successively closer geographic hops, until the target is reached. An example of ravenousnext hop choice appears in Figure 1. Here, x receives a packet destinedfor D. x's radio range is denoted by the dotted circle about x, andthe arc with radius equal to the distance between y and D is shownas the dashed arc about D. x forwards the packet to y, as the distancebetween y and D is less than that between D and any of x'sother neighbors. This ravenous forwarding process repeats, until thepacket reaches D. |
| A simple beaconing algorithm provides all nodes with their neighbors'positions: periodically, each node transmits a beacon to thebroadcast MAC address, containing only its own identifier (e.g., IPaddress) and position. We encode position as two four-byte floatingpointquantities, for x and y coordinate values. To avoid synchronizationof neighbors' beacons, as observed by Floyd and Jacobson, we jitter each beacon's transmission by 50% of the intervalB between beacons, such that the mean inter-beacon transmissioninterval is B, uniformly distributed in [0.5bB, 1.5B] |
| Upon not receiving a beacon from a neighbor for longer than timeout intervalT, a RPSR router assumes that the neighbor has failedor gone out-of-range, and deletes the neighbor from its table. The802.11 MAC layer also gives direct indications of link-level retransmissionfailures to neighbors; we interpret these indicationsidentically. We have used T=4.5B, three times the maximum jitteredbeacon interval, in this work. Ravenous forwarding's great advantage is its reliance only on knowledgeof the forwarding node's immediate neighbors. The state requiredis negligible, and dependent on the density of nodes in thewireless network, not the total number of targets in the network. On networks where multi-hop routing is useful, the numberof neighbors within a node's radio range must be substantially lessthan the total number of nodes in the network.The position a node associates with a neighbor becomes less currentbetween beacons as that neighbor moves. The accuracy of theset of neighbors also decreases; old neighbors may leave and newneighbors may enter radio range. For these reasons, the correctchoice of beaconing interval to keep nodes' neighbor tables currentdepends on the rate of mobility in the network and range of nodes'radios. We show the effect of this interval on RPSR's performance in our simulation results. We note that keeping current topologicalstate for a one-hop radius about a router is the minimum required todo any routing; no useful forwarding decision can be made withoutknowledge of the topology one or more hops away.This beaconing mechanism does represent pro-active routing protocoltraffic, avoided by DSR and AODV. To minimize the cost of beaconing, RPSR piggybacks the local sending node's position onall data packets it forwards, and runs all nodes' network interfacesin promiscuous mode, so that each station receives a copy of allpackets for all stations within radio range. At a small cost in bytes(twelve bytes per packet), this scheme allows all packets to serveas beacons. When any node sends a data packet, it can then resetits inter-beacon timer. This optimization reduces beacon traffic inregions of the network actively forwarding data packets.In fact, we could make RPSR's beacon mechanism fully reactive byhaving nodes solicit beacons with a broadcast .neighbor request.only when they have data traffic to forward. We have not felt it necessaryto take this step, however, as the one-hop beacon overheaddoes not congest our simulated networks.The power of ravenous forwarding to route using only neighbor nodes'positions comes with one attendant drawback: there are topologiesin which the only route to a target requires a packet move temporarilyfarther in geometric distance from the target [7].A simple example of such a topology is shown in Figure 2. Here,xis closer to D than its neighbors w and y. Again, the dashed arc |
 |
| AboutD has a radius equal to the distance between x and D. Althoughtwo paths, . x → y → z → D .and x → w→v → D , exist to D, x will not choose to forward to w or y using ravenous forwarding.xis a local maximum in its proximity to D. Some other mechanismmust be used to forward packets in these situations. |
II.IITheRightHand Rule: Perimeters |
| Motivated by Figure 2, we note that the intersection of x's circularradio range and the circle about D of radius|ïÿýïÿýïÿýïÿý|(that is, of thelength of line segmentxD) is empty of neighbors. We show thisregion clearly in Figure 3. From node x's perspective, we term theshaded region without nodes a void. X seeks to forward a packet totargetD beyond the edge of this void. Intuitively, x seeks toroute around the void; if a path to D exists from x, it doesn't contain nodes located within the void (or x would have forwarded to themgreedily). x → y → z → D The long-known right-hand rule for traversing a graph is depictedin Figure 4. This rule states that when arriving at node x from nodey, the next edge traversed is the next one sequentially counterclockwiseabout x from edge(x, y). It is known that the right-hand ruletraverses the interior of a closed polygonal region (a face) in clockwiseedge order.in this case, the triangle bounded by the edgesbetween nodes x, y, and z, in the order ( y → x → z → y) . The rule traverses an exterior region, in this case, the region outside the sametriangle, in counterclockwise edge order. We seek to exploit these cycle-traversing properties to route aroundvoids. In Figure 3, traversing the cycle x → w→v → D → z → y → x by the righthand rule amounts to navigating around the picturedvoid, specially, to nodes closer to the target than x (in thiscase, including the targetitself, D). We call the sequence of edges traversed by the right-hand rule a perimeter. |
 |
| In earlier work, we propose mapping perimeters by sendingpackets on tours of them, using the right-hand rule. The stateaccumulated in these packets is cached by nodes, which recoverfrom local maxima in ravenous forwarding by routing to a node on acached perimeter closer to the target. This approach requiresa heuristic, the no-crossing heuristic, to force the right-hand ruleto find perimeters that enclose voids in regions where edges of thegraph cross. This heuristic improves reachability results overall,but still leaves a serious liability: the algorithm does not alwaysfind routes when they exist. The no-crossing heuristic blindly removeswhichever edge it encounters second in a pair of crossingedges. The edge it removes, however, may partition the network. Ifit does, the algorithm will not find routes that cross this partition. |
III. RELATED WORK |
| Finn [7] is the earliest we know to propose ravenous routing using thelocations of nodes. He recognizes the small forwarding state ravenousforwarding requires, and observes the failure of ravenousforwarding upon reaching a local maximum. He proposes flooding search fora closer node as a strategy for recovering from local maxima. We first propose ravenous forwarding and perimeter traversal in,as briefly discussed in Section 2.2. This work simulates this olderalgorithm on static networks, in a very idealized (contention less,infinite bandwidth) simulator, and presents the state per node (includingperimeter node lists, notably absent from the current work),message cost from cold start to convergence, and frequency withwhich routes are not found, because of the imperfect no-crossingheuristic. This prior work does not offer any mobile simulationresults, and the earlier algorithm suffers in many ways from itsmaintenance of state beyond neighbor lists at all routers: increasedstate size for perimeter lists at all nodes, periodic pro-active routing protocol traffic that perimeter probes generate, and staleness ofperimeter lists that would occur under mobility. The unreachabilityof even a small fraction of targets on static networks becauseof the failure of the no-crossing heuristic is also problematic; suchrouting failures are permanent, not transitory. |
| Johnson and Maltz [12] propose the Dynamic Source Routing (DSR)protocol. DSR generates routing traffic reactively: a router floodsa route request packet throughout the network. When the requestreaches the target, the target returns a route reply to therequest's originator. Nodes aggressively cache routes that they learn,so that intermediate nodes between a querier and target maysubsequently reply on behalf of the target, and limit the propagation of requests.Broch et al. [4] compare the performance of the DSDV, TORA,DSR, and AODV routing protocols on a simulated mobile IEEE802.11 network. They simulate networks of 50 nodes, under arange of mobility rates and traffic loads. Their measurements showthe effectiveness of DSR's caching in minimizing DSR's routing protocol traffic on these 50-node networks. In the interest of comparabilityof results, we use this work's simulation environment forIEEE 802.11, a tworay ground rejection model, and DSR.Ko and Vaidya describe Location Aided Routing (LAR), anoptimization to DSR in which nodes limit the propagation of routerequest packets to the geographic region where it is most probablethe target is located. LAR uses base DSR to establish firstconnectivity with a target; thereafter, a route querier learns thetarget's location directly from the target node, and usesthis information to mark route requests for propagation only withina region of some size about the target's last known position.Like DSR's caching, LAR is a strategy for limiting the propagationof route requests. When a circuitous path, outside the region LARlimits route request propagation within, becomes the only path toatarget, LAR reverts to DSR's flooding-with-caching basecase. Under LAR, DSR's routes are still end-to-end source routes.Geography is not used for data packet forwarding decisions underLAR; only to scope routing protocol packet propagation.Li et al propose GLS, a scalable and robust location databasethat geographically addresses queries and registrations. Their systemdynamically selects multiple database servers to store eachnode's location, for robustness against server failure. This propertyalso ensures that a cluster of nodes partitioned from the remainderof the network continues to have location database service, providedby nodes inside the cluster. GLS uses a geographic hierarchyto serve queries at a server topologically close to the querier.Bose et al. independently investigated the graph algorithms forrendering a radio network's graph planar. They suggest the GabrielGraph, and analyze the increase in path length over shortest pathswhen traversing a graph using only perimeters. Motivated by thelonger-than-optimal paths perimeter traversal alone finds, they suggestcombining planar graph traversal with ravenous forwarding, and verify that this combination produces path lengths closer to trueshortest paths. They do not present a routing protocol, do not simulatea network at the packet level, and assume that all nodes arestationary and reachable. |
IV. FUTURE WORK |
| One assumption in the use of planar perimeters we would like toinvestigate further is that a node can reach all other nodes within itsradio range. The GG and RNG planarization’s both rely on a node'sability to accurately know if there is a witness w within radio range,when considering elimination of an edge to a known neighbor. Ouruse of the GG and RNG can disconnect a graph with particularpatterns of obstacles between nodes. This disconnection is easilyavoided by forcing the pair of nodes bordering an edge to agree onthe edge's fate, with the rule that both nodes must decide to eliminatethe edge, or neither will do so. However, this modificationto the planarization algorithms will make the RNG and GG planarization’s leave one or more crossing edges in these regions withobstacles. We intend to study these cases further. One promisingapproach in dealing with such obstacles may be to have obstructednodes choose a reachable partner node elsewhere in the network,and route via the partner for targets that are unreachable becauseof local failure of the planarization.While we have shown herein the benefits of geography as a toolfor scalable routing systems, measuring the combined behavior of RPSR and a location database system will reveal more about thecosts of using geography for routing. An efficient distributed locationdatabase would provide a network service useful in many otherlocation-aware computing applications.A comparison of the behavior of RPSR using the RNG and GGplanarization’s would reveal the performance effects of the tradeoffbetween the greater traffic concentration that occurs in perimeterforwarding on the sparser RNG, vs. the increased spatial diversitythat the RNG offers by virtue of its sparsely. Even outside the context ofRPSR, it may be the case that limiting edges used for forwardingin a radio network to those on the RNG or GG may reduce contention and improve efficiency on MAC protocols sensitive tothe number of sending stations in mutual range.We hope to extend RPSR for hosts placed in three-dimensional space, beyond the flat topologies explored in this paper. A promisingapproach is to implement perimeter forwarding for 3-D volumesrather than 2-D faces. |
V. CONCLUSION |
| We have presented Ravenous Perimeter Stateless Routing, RPSR, arousing algorithm that uses geography to achieve small per-node routing state, small routing protocol message complexity, and extremely robust packet delivery on densely deployed wireless networks. Our simulations on mobile networks with up to 200 nodes over a full IEEE 802.11 MAC demonstrate these properties: RPSR consistently delivers upwards of 94% of data packets successfully; it is competitive with DSR in this respect on 50-node networks atoll pause times, and increasingly more successful than DSR as the number of nodes increases, as demonstrated on 112-node and 200-node networks. RPSRgenerates routing protocol traffic in a quantityindependent of the length of the routes through the network,and therefore generates a constant, low volume of routing protocolmessages as mobility increases, yet doesn't suffer from decreased robustness in finding routes. DSR must query longer routes as thenetwork diameter increases, and must do so more often as mobilityincreases, and caching becomes less effective. Thus, DSRgeneratesdrastically more routing protocol traffic in our 200-nodeand 112-node simulations than it does in our 50-node ones. Finally, RPSR keeps state proportional to the number of its neighbors, while both traffic sources and intermediate DSR routers cache state proportional to the product of the number of routes learned and route length in hops. RPSR's benefits all stem from geographic routing's use of only immediate-neighbor information in forwarding decisions. Routingprotocols that rely on end-to-end state concerning the path betweena forwarding router and a packet's target, as do source-routed,DV, and LS algorithms, face a scaling challenge as network diameterin hops and mobility increase because the product of these twofactors determines the rate that end-to-end paths change. Hierarchyand caching have proven successful in scaling these algorithms.Geography, as exemplified in RPSR, represents another powerful lever for scaling routing. |
References |
|