Impact of interference on multi-hop wireless network performance

ABSTRACT

In this paper, we address the following question: given a specific placement of wireless nodes in physical space and a specific traffic workload, what is the maximum throughput that can be supported by the resulting network? Unlike previous work that has focused on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, we work with any given network and workload specified as inputs.A key issue impacting performance is wireless interference between neighboring nodes. We model such interference using a conflict graph, and present methods for computing upper and lower bounds on the optimal throughput for the given network and workload. To compute these bounds, we assume that packet transmissions at the individual nodes can be finely controlled and carefully scheduled by an omniscient and omnipotent central entity, which is unrealistic. Nevertheless, using ns-2 simulations, we show that the routes derived from our analysis often yield noticeably better throughput than the default shortest path routes even in the presence of uncoordinated packet transmissions and MAC contention. This suggests that there is opportunity for achieving throughput gains by employing an interference-aware routing protocol.

REFERENCES

• 1: Abramson, N. THE ALOHA SYSTEM --- Another Alternative for Computer Communications". Proc. AFIPS Fall Joint Computer Conference (1970), 281--285.
• 2: Bay area wireless users group. http://www.bawug.org/.
• 3: Berkelaar, M. lp_solve: linear programming code. ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.
• 4: ChavtaL, V. Linear Programming. W. H. Freeman and Compnay, 1983.
• 5: Couto, D. S. J. D., Aguayo, D., Chambers, B. A., and Morris, R. Performance of multihop wireless networks: Shortest path is not enough. In 1st Workshop on Hot Topics in Networks (Oct. 2002).
• 6: Ilog cplex suite, 2003. http://www.ilog.com/products/cplex/.
• 7: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Gastpar, M., and Vetterli, M. On the capacity of wireless networks: the relay case. In IEEE INFOCOM (Jun. 2002).
• 10: Grossglauser, M., and Tse, D. Mobility increases the capacity of ad-hoc wireless networks. In IEEE INFOCOM (Apr. 2001).
• 11: Grotschel, M., Lovasz, L., and Schrijver, A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981), 169--197.
• 12: Grotschel, M., Lovasz, L., and Schrijver, A. Geometric Methods in Combinatorial Optimization. Academic Press, 1984.
• 13: Gupta, P., and Kumar, P. R. The capacity of wireless networks. IEEE Transactions on Information Theory 46, 2 (Mar. 2000).
• 14: Gupta, P., and Kumar, P. R. The capacity of wireless networks. IEEE Transactions on Information Theory 46, 2 (Mar. 2000), 388--404.
• 15: Johnson, D. B., and Maltz, D. A. Dynamic source routing in ad-hoc wireless networks. In Mobile Computing (1996), T. Imielinski and H. Korth, Eds., Kluwer Academic Publishers.
• 16: Khachiyan, L. G. A polynomial algorithm in linear programming. Soviet Mathematics Doklady 20 (1979), 191--194.
• 17: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 18: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 19: Matlab version 6.1. http://www.matlab.com/.
• 20: M.Chudnovsky, Robertson, N., P.D.Seymour, and R.Thomas. The Strong Perfect Graph Theorem. Submitted for publication., February 2003.
• 21: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 22: Ns-2 (network simulator), 1995. http://www-mash.cs.berkeley.edu/ns/.
• 23: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 24: 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
• 25: 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
• 26: Seattle wireless. http://www.seattlewireless.net/.
• 27: Xue Yang , Nitin H. Vaidya, Priority scheduling in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513809]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Performance

Keywords:
interference, multi-hop, performance, wireless