Ad Hoc network :Ad Hoc network - applications - protocols


Introduce :Chenjuan Zhou 2 Introduce mobile ad-hoc network (MANET) is a self-configuring network of mobile routers (and associated hosts) connected by wireless links—the union of which form an arbitrary topology Uninfrastructure network


Technical challenges :Chenjuan Zhou 3 Technical challenges No service guarantee Increased energy consumption (fast battery draining) Increased transmit power (in CDMA) Additional hardware and functionality (higher terminal cost) Security issues Frequent hand-offs (especially in the presence of high mobility)


Ad hoc applications :Chenjuan Zhou 4 Ad hoc applications Bluetooth-pure Ad hoc network technology WiFi-mesh mode WiMax-mesh topology (New) Current application: D-star DSRC Location-based services


Ad hoc routing protocols :Chenjuan Zhou 5 Ad hoc routing protocols OLSR-Optimized Link State Routing DSR-Dynamic Source Routing ZRP-Zone Routing Protocol


Ad hoc routing protocols :Chenjuan Zhou 6 Ad hoc routing protocols Proactive approach(Table-driven)-OLSR -Nodes are actively engaged in route discovery and maintenance even though there is no traffic to deliver -Generate more control traffic in lightly loaded networks -Packet experience less latency Reactive approach(On-demand)-DSR -Discovery and maintenance of routes is delayed until necessary -Generate less control traffic in lightly loaded networks -Packet may experience higher latency Hybrid approach-ZRP


OLSR-Optimized Link State Routing :Chenjuan Zhou 7 OLSR-Optimized Link State Routing RFC standardized and adapted by industries Approach: proactive-always ready, Layer: Network+UDP+Application process(simple to implement in current OS with little change) Structure: FLAT Assumption on link: symmetric


OLSR :Chenjuan Zhou 8 OLSR Routing: hop-by-hop One node has a routing table Use shortest Path to determine the next hop address Applied to small scale networks Use UDP to exchange the control messages


OLSR- Routing Table :Chenjuan Zhou 9 OLSR- Routing Table Routing entries are indexed by destination node Need to be updated whenever the new topology information is acquired


OLSR control message format :Chenjuan Zhou 10 OLSR control message format A single UDP Datagram may actually embed several OSLR message …


OLSR :Chenjuan Zhou 11 OLSR Hello message Topology control message


OLSR -Hello message :Chenjuan Zhou 12 OLSR -Hello message Periodically sends hello messages Inform its one-hop neighborhood and selected multipoint relays Not be forwarded With the information acquired from hello message, every node learn about its two-hop neighborhood


OLSR -Topology control messages :Chenjuan Zhou 13 OLSR -Topology control messages Inform the other nodes about the multipoint relays It is forwarded over the whole network only by MPR When forwarded, using broadcast on all interfaces Each topology control message contains the addresses of the neighbors for which the originator is a multipoint


Topology control messages :Chenjuan Zhou 14 Topology control messages Multipoint relays


DSR-Dynamic Source Routing :Chenjuan Zhou 15 DSR-Dynamic Source Routing Draft of RFC Approach:reactive- quiet until any requirement need to be done Layer: network Structure:FLAT Routing: source Assumption on link: asymmetric


DSR :Chenjuan Zhou 16 DSR Source Routing Asymmetric links Data packet with a source route option


DSR- Route Request :Chenjuan Zhou 17 DSR- Route Request Data packet with a route request option


DSR- Route reply :Chenjuan Zhou 18 DSR- Route reply Data packet with a route reply option


ZRP- Zone Routing Protocol :Chenjuan Zhou 19 ZRP- Zone Routing Protocol ZRP is designed under the hypothesis that in ad hoc networks a large portion of the traffic is between nodes that are geographically closed NDP -Neighbor Discovery Protocol LARP-Intrazone Routing Protocol IERP-Interzone Routing Protocol


ZRP-Zone Routing Protocol :Chenjuan Zhou 20 ZRP-Zone Routing Protocol Not draft yet Approach: Hybrid approach. Proactive with close neighbors and reactive with distance nodes. Structure: hierarchical Routing: source and hop-by-hop Assumption on link: Symmetric


NDP-Neighbor Discovery Protocol :Chenjuan Zhou 21 NDP-Neighbor Discovery Protocol Keeps tracks of states of links to (direct) neighbors. update the routing table Each node repeatedly sends using broadcast a hello beacon The time between broadcasts is chosen at random.


Parameters :Chenjuan Zhou 22 Parameters Arrival (models a recent reception of a hello beacon): •True: when a hello beacon has just been received. False: at the end of an iteration of the routing table update algorithm. Lat recorded (models the logical age of the most recent hello beacon received from the neighbor): • -1: when a hello beacon is received for the first time from a neighbor. • 0, 1, 2, …: at the end of an iteration of the routing table update algorithm.


Reception of a hello beacon :Chenjuan Zhou 23 Reception of a hello beacon


Slide 24:Chenjuan Zhou 24


Update of neighbor table :Chenjuan Zhou 25 Update of neighbor table


Update of neighbor table :Chenjuan Zhou 26 Update of neighbor table A maximum (of Max) updates of the neighbor table has been performed while no hello beacon has been received from the neighbor. The Neighbor Lost signal is sent to IARP. The Neighbor Found signal is sent to IARP.


IARP-IntrAzone Routing Protocol :Chenjuan Zhou 27 IARP-IntrAzone Routing Protocol Proactive protocol Support route discovery and route maintenance Derived from Open Shortest Path First (OSPF)


Slide 28:Chenjuan Zhou 28


Handling of Link-State updates :Chenjuan Zhou 29 Handling of Link-State updates Store in routing table a spanning tree using the information from the link-state table. Prune branches that extend outside the extended routing zone (length greater that two times the zone radius). Remove form the link-state table links leading to nodes outside the extended routing zone Send to neighbors new information in link-state table (TTL is set to 2 times the zone radius minus one).


IERP-IntErzone Routing Protocol :Chenjuan Zhou 30 IERP-IntErzone Routing Protocol Reactive routing protocol Route request-reply based Bordercasting: messages are directed to peripherals (implemented as a series of unicasts or a multicast)


Detected Queries Table :Chenjuan Zhou 31 Detected Queries Table


Route discovery process :Chenjuan Zhou 32 Route discovery process Determined by lookups in routing tables. Assigns a unique query ID.


Slide 33:Chenjuan Zhou 33 1. The information is stored in the detected queries table when the query is received for the first time. If the source address and query Id are present, the RREQ is ignored. 2. Determined by a lookup in IARP’s routing table. 3. The path is collected in the Previous hop address field in the Detected queries table from hop to hop.


Slide 34:Chenjuan Zhou 34 1. The visited node is a peripheral. 2. The VN is a Peripheral non-covered. 3. The VN is a Peripheral in a previously queried zone. 4. The VN is an interior node.


Continue…… :Chenjuan Zhou 35 Continue…… The following algorithm is applied: insert := false for each neighbor N of the visited node if bordercast_downstream(N, depth+1) // there is a candidate in this subtree insert := true if the visited node is the current node add N to downstream_neighbors return insert