Polynomial time algorithms for multirate anypath
For further details contact: N.RAJASEKARAN B.E M.S 9841091117,9840103301. IMPULSE TECHNOLOGIES, Old No 251, New No 304, 2nd Floor, Arcot road , Vadapalani , Chennai-26.
Published on: Mar 4, 2016
Transcripts - Polynomial time algorithms for multirate anypath
Polynomial-Time Algorithms for Multirate Anypath Routing in Wireless Multihop NetworksAbstract—In this paper, we present a new routing paradigm that generalizes opportunisticrouting for wireless multihop networks. In multirate anypath routing, each nodeuses both a set of next-hops and a selected transmission rate to reach a destination.Using this rate, a packet is broadcast to the nodes in the set, and one of themforwards the packet on to the destination. To date, there is no theory capable ofjointly optimizing both the set of next-hops and the transmission rate used by eachnode. We solve this by introducing two polynomial-time routing algorithms andprovide the proof of their optimality. The proposed algorithms have roughly thesame running time as regular shortest-path algorithms and are therefore suitable fordeployment in routing protocols.Existing system :ROUTING in wireless multihop networks is challenging due to the high loss rateand dynamic quality of wireless links –. Anypath routing1 has been recentlyproposed as a way to circumvent these shortcomings by using multiple next-hopsfor each destination –. Each packet is broadcast to a forwarding set composedof several neighbors, and the packet is lost only if none of these neighbors receiveit. Therefore, while the link to a given neighbor is down or performing poorly,another nearby neighbor may receive the packet and forward it on.Demerits :First, loss probabilities increase with higher transmission rates, so a higher bit ratedoes not always improve throughput. Second, we must find not only the
forwarding set, but also the transmission rate at each hop that jointly minimizes itscost to a destination. For instance, assuming that links , , and achieve their highestthroughput at 2, 5.5, and 11 Mbps, respectively, which subset of neighbors shouldnode use to reach the destination, and at which rate should the packet betransmitted? Finally, higher rates have a shorter transmission range, and thereforewe have a different connectivity graph for each rate. Lower rates have moreneighbors available for inclusion in the forwarding set (i.e., more spatial diversity)and fewer hops between nodes. Higher rates have fewer neighbors available for theforwarding set (i.e., less spatial diversity) and longer routesproposed system :We introduce two polynomial-time routing algorithms to the shortest multirateanypath problem and present a proof of their optimality. Our solution generalizesDijkstra’s and Bellman–Ford algorithms for the multirate anypath case and areapplicable to both link-state and distance-vector routing protocols, respectively.One would expect the running time of such algorithms to be exponential since,with neighbors, we can have up to forwarding sets. However, we show that theproposed algorithms have roughly the same polynomial time as the correspondingshortest-path algorithms and are suitable for implementation at current wirelessrouters. We also show that our algorithms are optimal even if packet losses atdifferent receivers are not independent .