Routing in Wireless Ad Hoc Networks

Routing Protocol Routing in Wireless Ad Hoc Networks The performance of Ad hoc protocols largely depends on the efficiency of the routingprotocol used. In wireless ad hoc networks, stations are free to move around. Togetherwith fact that the transmission range of mobile terminals is fixed results in adynamically changing network topology. As stations move around some network linksare destroyed while the possibility of new links being established arises. It is obviousthat such an environment cannot be served efficiently by routing protocols developedfor wired networks. This is due to the fact that in such networks the assumption ofstatic topology is made. Thus new routing protocols are needed for the dynamicallychanging ad hoc wireless environment. In these protocols, it is assured that all stations of the network have identicalcapabilities and employ the capability to perform routing related tasks such as routediscovery /establishment to other nodes in the network and route maintenance. Therouting protocols presented fall into two families table driven and on demand. Table driven routing protocols aim to maintain consistent up to date routinginformation from each node to all other nodes of the network, thus each network nodemaintains one or more routing table which is used to store the route from this node toall other network nodes. This knowledge regarding every possible route needs to bepresent in every node irrespective of the fact that some of these routes may not beused by network connections. When topological changes occur, the relatinginformation nodes up to date routing information. On demand routing protocols follow a different approach: route is established onlywhen required for a network connection. Thus when a source node A needs to connectto a destination node B, then A invokes a routing discovery protocol to find a routeconnecting it to B. Upon route establishment nodes A and B as well as intermediatenodes store the information regarding the route from A to B in their routing tables.The route is maintained until the destination is unreachable or the route is no longerneeded. Table-driven routing protocols obviously have the advantage or end to end delay since upon generation of a network connection request the route is alreadyestablished. However, their disadvantage is the fact that routing information isdisseminated to all network nodes leading to increased signaling however end to endconnection delay is increased, since upon generation of a connection request betweentwo nodes, the connection needs to wait some time for the link between the nodes tobe established. Table-driven Routing Protocols Destination Sequenced Distance-Vector (DSDV) Routing Protocol The DSDV routing protocol is an extension of the classical Bellman Ford routingalgorithm. The extensions incorporated in DSDV target freedom from loops in routing

tables. In DSDV, each node maintains a routing table that contains informationregarding all possible routes within the network the number of hops of each route andthe sequence number of each route. The latter is a number assigned by thedestination of the route and shows how old the route is. The lower the sequencenumber the older the route. When a node A needs to select a route to node Bit checksits routing table. If more than one such route is found the newer one is used. If morethan one route shares the same sequence number, then the shortest one is chosen.Network nodes periodically broadcast their routing tables in order to propagatetopology knowledge throughout the network. Apart from these periodic transmissionsa station can select to broadcast its routing table when significant topology changeshave occurred. The propagation of routing tables obviously results in large overhead.In an effort to alleviate this problem two types of updates are defined: full dumpupdates and incremental updates. In full dump updates, stations transmit their entirerouting table. Since routing tables are mostly quite large, a full update typicallyinvolves more than one packet broadcast. This obviously consumes resources so fulldumps are transmitted infrequently. Incremental updates are transmitted between fulldumps and convey only that information which has carried over a single packet. Therelative frequency of full-dump and incremental updates depends on the nature oftopological changes. In a network of a slowly changing topology, full dumps are rarelyused since incremental dumps are able to convey the slow topological changes. On theother hand, in a network of fast changing topology. Dynamic Source Routing (DSR) It is a protocol for routing in ad hoc networks that uses dynamic source routing. Theprotocol adapts quickly to routing changes when host movement is frequent, yetrequires little or no overhead during periods in which hosts move less frequently.Based on results from a packet-level simulation of mobile hosts operating in an ad hocnetwork, the protocol performs well over a variety of environmental conditions such ashost density and movement rates. For all but the highest rates of host movementsimulated. the overhead of the protocol is quite low, falling to just 1% of total datapackets transmitted for moderate movement rates in a network of 24 mobile hosts. Inall cases, the difference in length between the routes used and the optimal routelengths is negligible, and in most cases, route lengths are on average within a factor of1.01 of optimal. This topic describes the design and performance of a routing protocolfor ad hoc networks that instead uses dynamic source routing of packets betweenhosts. that want to communicate. Source routing is a routing technique in which thesender of a packet determines the complete sequence of nodes through which toforward the packet; the sender explicitly lists this route in the packet's header,identifying each forwarding" hop" by the address of the next node to which to transmitthe packet on its way to the destination host. Source routing has been used in anumber of contexts for routing in wired networks, using either statically defined ordynamically constructed source routes, and has been used with statically configuredroutes in the Tucson Amateur Packet Radio (TAPR) work for routing in a wirelessnetwork. The protocol presented here is explicitly designed for use in the wirelessenvironment of an ad hoc network. There are no periodic router advertisements in the

protocol. Instead, when a host needs a route to another host, it dynamicallydetermines one based on cached information and on the results of a route discoveryprotocol. Global State Routing In an ad-hoc environment with no wired communication infrastructure, it is necessarythat mobile hosts operate as routers in order to maintain the information aboutconnectivity. However, with the presence of high mobility and low signal/interferenceratio (SIR), traditional routing schemes for wired networks are not appropriate, as theyeither lack the ability to quickly reflect the hanging topology, or may cause excessiveoverhead, which degrades network performance. Considering these restrictions, wepropose a new scheme especially designed for routing in ad-hoc wirelessenvironments. We call this scheme "Global State Routing" (GSR), where nodesexchange vectors of link states among their neighbors during routing informationexchange. Based on the link state vectors, nodes maintain a global knowledge of thenetwork topology and optimize their routing decisions locally. Our goal is to design a routing scheme that is MAC efficient in ad-hoc wireless radionetworks. That is, the control packet size should be able to achieve optimized MACthroughput, and the number of control packet should be controllable. We prefer tomaintain the knowledge of full network topology as in link state routing, but wish toavoid the inefficient flooding mechanism.