CS 8803 HW Spring 2008

DUE: MARCH 13 -- by 11:59pm.

IMPORTANT: This homework to be done individually. No collaboration is allowed.

If you have any questions please check with the instructor.

Question 0 (10 points): Explain the following two problems that arise in a MANET.

a) The Hidden Terminal Problem

b) The Exposed Terminal Problem

What solutions (if any) does 802.11 provide for these problems?

Question 1 (10 points): Explain briefly why the location-aided routing algorithm (LAR) may not find a route between a source-destination pair, but the original DSR might be able to find a route. Describe a specific scenario where this can happen.

Question 2 (10 points): Explain why the ZRP's approach to route finding can have more overhead than flooding. Describe what the ZRP paper proposes as a solution.

Question 3 (40 points): Nodes in an ad hoc network maintain the following routing tables. For simplicity, we identify nodes by the last byte in their IP addresses (rather than the full IP address).

a) Draw the topology of the network

b) Node 6 generates a packet with destination address node 1. What route will the packet follow?

c) Suppose OLSR is adopted as the routing protocol. Complete the table below with the optimal Multipoint Relay Set (MPR) and the optimal Multipoint Relay Selector Set (MS) for each node. (Note: Whenever there is a tie, assume that the node with the higher ID is chosen as a multipoint relay.)

d) Node 2 detects a new link to node 7 and generates a new topology control (TC) message, which it sends to its neighbors. Which of these neighbors will forward the TC message?

e) Give one reason why a protocol such as OSPF, used for intra-domain routing in wired networks, would not be a good choice for a MANET.

Question 4 (30 points):

a) What is the difference between GAF-ma and GAF-b? Under what conditions is GAF-ma better than GAF-b? Make sure you refer to evidence of your answer in the GAF paper.

b) Both BECA and GAF are meant to operate in a layer below a routing protocol like AODV. Do either of them require specific tuning of the routing protocol parameters? If so explain what kind of tuning is required and why?

c) Explain the difference between how a Dominating Set of nodes is selected in the Span approach and the Wu and Li approach in the paper On Calculating Dominating Set for Efficient Routing in Ad Hoc Wireless Networks.