Routing performance in the presence of unidirectional links in multihop wireless networks

ABSTRACT

We examine two aspects concerning the influence of unidirectional links on routing performance in multihop wireless networks. In the first part of the paper we evaluate the benefit from utilizing unidirectional links for routing as opposed to using only bidirectional links. Our evaluations are based on three transmit power assignment models that reflect some realistic network scenarios with unidirectional links. Our results indicate that the marginal benefit of using a high-overhead routing protocol to utilize unidirectional links is questionable.Most common routing protocols however simply assume that all network links are bidirectional and thus may need additional protocol actions to remove unidirectional links from route computations. In the second part of the paper we investigate this issue using a well known on-demand routing protocol Ad hoc On-demand Distance Vector (AODV) as a case study. We study the performance of three techniques for AODV for efficient operation in presence of unidirectional links viz. BlackListing Hello and ReversePathSearch. While BlackListing and Hello techniques explicitly eliminate unidirectional links the ReversePathSearch technique exploits the greater network connectivity offered by the existence of multiple paths between nodes. Performance results using ns-2 simulations under varying number of unidirectional links and node speeds show that all three techniques improve performance by avoiding unidirectional links the ReversePathSearch technique being the most effective.

REFERENCES

• 1: Yehuda Afek , Eli Gafni, Distributed Algorithms for Unidirectional Networks, SIAM Journal on Computing, v.23 n.6, p.1152-1178, Dec. 1994 [doi>10.1137/S009753979223277X]
• 2: L.Bao and J.J. Garcia-Luna-Aceves. Link-state Routing in Networks with Unidirectional Links. In Proceedings of International Conference on Computer Communications and Networks (IC3N) pages 358--363 1999.
• 3: Lichun Bao , J. J. Garcia-Luna-Aceves, Channel access scheduling in Ad Hoc networks with unidirectional links, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.9-18, July 2001, Rome, Italy [doi>10.1145/381448.381450]
• 4: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 5: T.Clausen etal. Optimized Link State Routing Protocol. http://www.ietf.org/internet-drafts/draft-ietf-manet-olsr-06.txt Mar 2002. IETF Internet Draft (work in progress).
• 6: Samir R. Das , Robert Castañeda , Jiangtao Yan, Simulation-based performance evaluation of routing protocols for mobile ad hoc networks, Mobile Networks and Applications, v.5 n.3, p.179-189, Sept. 2000 [doi>10.1023/A:1019108612308]
• 7: E.Duros, W.Dabbous H.Izumiyama N.Fujii and Y.Zhang. A Link-Layer Tunneling Mechanism for Unidirectional Links. RFC 3077 2001.
• 8: K.Fall and K.Varadhan(Eds.). The ns Manual. http://www.isi.edu/nsnam/ns/ns-documentation.html 2002.
• 9: M.Gerla, X.Hong and G.Pei. Fisheye State Routing Protocol (FSR) for Ad Hoc Networks. http://www.ietf.org/internet-drafts/draft-ietf-manet-fsr-02.txt Dec 2001. IETF Internet Draft (work in progress).
• 10: M.Gerla, L.Kleinrock and Y.Afek. A Distributed Routing Algorithm for Unidirectional Networks. In Proceedings of IEEE GLOBECOM 1983.
• 11: Z.J. Haas, M.R. Pearlman and P.Samar. The Interzone Routing Protocol (IERP) for Ad Hoc Networks. http://www.ietf.org/internet-drafts/draft-ietf-manet-zone-ierp-01.txt June 2001. IETF Internet Draft (work in progress).
• 12: Z.J. Haas, M.R. Pearlman and P.Samar. The Intrazone Routing Protocol (IARP) for Ad Hoc Networks. http://www.ietf.org/internet-drafts/draft-ietf-manet-zone-iarp-01.txt June 2001. IETF Internet Draft (work in progress).
• 13: L.Hu. Topology Control for Multihop Packet Radio Networks. IEEE Transactions on Communications 41(10):1474--1481 1993.
• 14: IEEE Standards Department. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications IEEE standard 802.11--1997.
• 15: D.B. Johnson, D.A. Maltz Y.Hu and J.G. Jetcheva. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR). http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-07.txt Feb 2002. IETF Internet Draft (work in progress).
• 16: D.Kim, C.K. Toh and Y.Choi. On supporting Link Asymmetry in Mobile Ad Hoc Networks. In Proceedings of IEEE GLOBECOM pages 2798--2803 2001.
• 17: Gregory S. Lauer, Packet-radio routing, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 18: J.Macker and S.Corson. Mobile Ad hoc Networks (MANET). http://www.ietf.org/html.charters/manet-charter.html 1997. IETF Working Group Charter.
• 19: On-Demand Multi Path Distance Vector Routing in Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.14, November 11-14, 2001
• 20: J.P. Monks, V.Bharghavan and W.W. Hwu. A Power Controlled Multiple Access Protocol for Wireless Packet Networks. In Proceedings of IEEE INFOCOM pages 219--228 2001.
• 21: J.Moy. OSPF version 2. RFC 1247 1991.
• 22: S.Narayanaswamy, V.Kawadia, R.S. Sreenivas and P.R. Kumar. Power Control in Ad-Hoc Networks: Theory Architecture Algorithm and Implementation of the COMPOW Protocol. In Proceedings of European Wireless Conference pages 156--162 2002.
• 23: S.Nesargi and R.Prakash. A Tunneling Approach to Routing with Unidirectional Links in Mobile Ad-Hoc Networks. In Proceedings of International Conference on Computer Communications and Networks (IC3N) pages 522--527 2000.
• 24: R.Ogier, F.L. Templin, B.Bellur and M.G. Lewis. Topology Broadcast Based on Reverse-Path Forwarding (TBRPF). http://www.ietf.org/internet-drafts/draft-ietf-manet-tbrpf-05.txt Mar 2002. IETF Internet Draft (work in progress).
• 25: V.Park and S.Corson. Temporally-ordered routing algorithm (TORA) version 1 functional specification. http://www.ietf.org/internet-drafts/draft-ietf-manet-tora-spec-04.txt July 2001. IETF Internet Draft (work in progress).
• 26: M.R. Pearlman, Z.J. Haas and B.P. Manvell. Using Multi-Hop Acknowledgements to Discover and Reliably Communicate over Unidirectional Links in Ad Hoc Networks. In Proceedings of Wireless Communications and Networking Conference (WCNC) pages 532--537 2000.
• 27: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 28: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 29: C.E. Perkins, E.M. Royer and S.R. Das. Ad hoc On-Demand Distance Vector (AODV) Routing. http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-10.txt Jan 2002. IETF Internet Draft (work in progress).
• 30: C.E. Perkins, E.M. Royer S.R. Das and M.K. Marina. Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks. IEEE Personal Communications 8(1):16--28 2001.
• 31: C.Pomalaza-Raez. A Distributed Routing Algorithm for Multihop Packet Radio Networks with Uni- and Bi-Directional Links. IEEE Transactions on Vehicular Technology 44(3):579--585 1995.
• 32: N.Poojary, S.V. Krishnamurthy and S.Dao. Medium Access Control in a Network of Ad Hoc Nodes with Heterogeneous Power Capabilities. In Proceedings of IEEE ICC pages 872--877 2001.
• 33: Ravi Prakash, A routing algorithm for wireless ad hoc networks with unidirectional links, Wireless Networks, v.7 n.6, p.617-625, November 2001 [doi>10.1023/A:1012371402221]
• 34: R.Ramanathan and R.Rosales-Hain. Topology Control of Multihop Wireless Networks using Transmit Power Adjustment. In Proceedings of IEEE INFOCOM pages 404--413 2000.
• 35: S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, v.5 n.2, p.81-94, March 1999 [doi>10.1023/A:1019126406181]
• 36: V.Ramasubramanian, R.Chandra and D.Mosse. Providing a Bidirectional Abstraction for Unidirectional Ad Hoc Networks. In Proceedings of IEEE INFOCOM 2002. To appear.
• 37: V.Rodoplu and T.Meng. Minimum Energy Mobile Wireless Networks. IEEE Journal on Selected Areas in Communications Special Issue on Ad Hoc Networks 17(8):1333--1344 Aug 1999.
• 38: P.Sinha, S.V. Krishnamurthy and S.Dao. Scalable Unidirectional Routing with Zone Routing Protocol (ZRP) Extensions for Mobile Ad-hoc Networks. In Proceedings of Wireless Communications and Networking Conference (WCNC) pages 1329--1339 2000.
• 39: Gerard Tel, Directed Network Protocols, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.13-29, July 08-10, 1987
• 40: R.Wattenhofer, L.Li P.Bahl and Y.Wang. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proceedings of IEEE INFOCOM pages 1388--1397 2001.
• 41: J.E. Wieselthier, G.D. Nguyen and A.Ephremides. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In Proceedings of IEEE INFOCOM pages 585--594 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Performance

Keywords:
ad hoc networks, asymmetric links, multihop wireless networks, multipath routing, on-demand routing, routing, unidirectional links