[ Pobierz całość w formacie PDF ]
.Neighbor list of a node contains the list of its neighbors (here all nodes that can be heardby a node are assumed to be its neighbors).For each destination node, the Topology tablecontains the link state information as reported by the destination and the timestamp of theinformation.For each destination, the Next Hop table contains the next hop to which thepackets for this destination must be forwarded.The Distance table contains the shortestdistance to each destination node.The routing messages are generated on a link change as in link state protocols.Onreceiving a routing message, the node updates it s Topology table if the sequence numberof the message is newer than the sequence number stored in the table.After this, the nodereconstructs its RT and broadcasts the information to its neighbors.9.1.4 Fisheye state routingFisheye State Routing (FSR) is an improvement of GSR.The large size of update messagesin GSR wastes a considerable amount of network bandwidth.In FSR, each update messagedoes not contain information about all nodes.Instead, it exchanges information aboutcloser nodes more frequently than it does about farther nodes, thus reducing the updatemessage size.Each node receives accurate information about neighbors, and the detailand accuracy of information decreases as the distance from the node increases.The scopeis defined in terms of the nodes that can be reached in a certain number of hops.Thecenter node has the most accurate information about the other nodes.Even though a nodedoes not have accurate information about distant nodes, the packets are routed correctlybecause the route information becomes more and more accurate as the packet movescloser to the destination.FSR scales well to large networks as the overhead is controlledin this scheme.9.1.5 Hierarchical state routingThe characteristic feature of Hierarchical State Routing (HSR) is multilevel clusteringand logical partitioning of mobile nodes.The network is partitioned into clusters anda cluster head elected as in a cluster-based algorithm.In HSR, the cluster heads againorganize themselves into clusters and so on.The nodes of a physical cluster broadcasttheir link information to each other.The cluster head summarizes its cluster s informationand sends it to the neighboring cluster heads via the gateway.These cluster heads aremembers of the cluster on a level higher and they exchange their link information as wellas the summarized lower-level information among themselves and so on.A node at eachlevel floods to its lower level the information that it obtains after the algorithm has runat that level.The lower level has a hierarchical topology information.Each node has ahierarchical address.One way to assign hierarchical address is to use the cluster numberson the way from the root to the node.A gateway can be reached from the root via morethan one path; thus, a gateway can have more than one hierarchical address.A hierarchicaladdress is enough to ensure delivery from anywhere in the network to the host.In addition, nodes are also partitioned into logical subnetworks and each node isassigned a logical address.Each subnetwork has a Location Manage-ment Server (LMS).All the nodes of that subnet register their logical address with the168 ROUTING PROTOCOLS IN MOBILE AND WIRELESS NETWORKSLMS.The LMS advertise their hierarchical address to the top levels and the informationis sent down to all LMS too.The transport layer sends a packet to the network layer withthe logical address of the destination.The network layer finds the destination s LMS fromits LMS and then sends the packet to it.The destination s LMS forwards the packet tothe destination.Once the source and destination know each other s hierarchical addresses,they can bypass the LMS and communicate directly.Since logical address/hierarchicaladdress is used for routing, it is adaptable to network changes.9.1.6 Zone-based hierarchical link state routing protocolIn Zone-based Hierarchical Link State Routing Protocol (ZHLS), the network is dividedinto nonoverlapping zones.Unlike other hierarchical protocols, there is no zone-head.ZHLS defines two levels of topologies  node level and zone level.A node level topologytells how nodes of a zone are connected to each other physically.A virtual link betweentwo zones exists if at least one node of a zone is physically connected to some node ofthe other zone.Zone level topology tells how zones are connected together.There aretwo types of Link State Packets (LSP) as well  node LSP and zone LSP.A node LSP ofa node contains its neighbor node information and is propagated with the zone, whereasa zone LSP contains the zone information and is propagated globally.Each node hasfull node connectivity knowledge about the nodes in its zone and only zone connectivityinformation about other zones in the network.Given the zone id and the node id of adestination, the packet is routed on the basis of the zone id till it reaches the correct zone.Then in that zone, it is routed on the basis of the node id.A of thedestination is sufficient for routing, so it is adaptable to changing topologies.9.1.7 Cluster-head gateway switch routing protocolCluster-head Gateway Switch Routing (CGSR) uses as basis the DSDV Routing algorithm.The mobile nodes are aggregated into clusters and a cluster head is elected.All nodesthat are in the communication range of the cluster head belong to its cluster.A gatewaynode is a node that is in the communication range of two or more cluster heads.Ina dynamic network, a cluster-head scheme can cause performance degradation due tofrequent cluster-head elections, so CGSR uses a Least Cluster Change (LCC) algorithm.In LCC, cluster-head change occurs only if a change in network causes two cluster heads tocome into one cluster, or one of the nodes moves out of the range of all the cluster heads.The general algorithm works in the following manner: the source of the packet transmitsthe packet to its cluster head.From this cluster head, the packet is sent to the gatewaynode that connects this cluster head and the next cluster head along the route to thedestination.The gateway sends it to that cluster head and so on till the destination clusterhead is reached in this way.The destination cluster head then transmits the packet to thedestination.Each node maintains a cluster member table that has mapping from each node toits respective cluster head.Each node broadcasts its cluster member table periodicallyand updates its table after receiving other node s broadcasts using the DSDV algorithm.ON-DEMAND ROUTING PROTOCOLS 169In addition, each node also maintains an RT that determines the next hop to reach thedestination cluster.On receiving a packet, a node finds the nearest cluster head along the route to thedestination according to the cluster member table and the RT.Then it consults its RT tofind the next hop in order to reach the cluster head selected in step one and transmits thepacket to that node.9.2 ON-DEMAND ROUTING PROTOCOLSIn contrast to table-driven routing protocols, all up-to-date routes are not maintained atevery node; instead, the routes are created as and when they are required.When sourcewants to send a packet to destination, it invokes the route discovery mechanisms to findthe path to the destination.The route remains valid till the destination is reachable oruntil the route is no longer needed.9.2 [ Pobierz całość w formacie PDF ]