How to correctly use the protocol interference model for multi-hop wireless networks

ABSTRACT

This paper tries to reconcile the tension between physical model and protocol model that have been used to characterize interference relationship in a multi-hop wireless network. The physical model (a.k.a. SINR model) is widely considered as a reference model for physical layer behavior but its application in multi-hop wireless networks is limited by its complexity. On the other hand, the protocol model (a.k.a. unified disk graph model) is simple but there have been doubts on its validity. This paper explores the following fundamental question: How to correctly use the protocol interference model? We show that in general, solutions obtained under the protocol model may be infeasible in practice and thus, results based on blind use of protocol model can be misleading. We propose a novel concept called "reality check" and present a method of using protocol model with reality check for wireless networks. Subsequently, we show that by appropriate setting of the interference range in the protocol model, it is possible to narrow the solution gap between the two models. Our simulation results confirm that this gap is indeed small (or even negligible). Thus, our methodology of joint reality check and interference range setting retains the protocol model as a viable approach to analyze multi-hop wireless networks.

REFERENCES

• 1: R. Ahlswede. Multi-way communication channels. In International Symposium on Information Theory Proceedings, pages 23--52.Tsahkadsor, Armenian S.S.R., 1971.
• 2: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 3: P. Bergmans. Random coding theorem for broadcast channels with degraded components. IEEE Trans. on Information Theory, 19(2):197--207, March 1973.
• 4: R. Bhatia and M. Kodialam. On power efficient communication over multi-hop wireless networks: joint routing, scheduling and power control. In IEEE Infocom Proceedings, pages 1457--1466. Hong Kong, China, March 7-11, 2004.
• 5: C.C. Chen and D.S. Lee. A joint design of distributed QoS scheduling and power control for wireless networks. In IEEE Infocom Proceedings, 12 pages. Barcelona, Catalunya, Spain, April 23-29, 2006.
• 6: M. Costa. Writing on dirty paper. IEEE Trans. on Information Theory, 29(3):439--441, May 1983.
• 7: T.M. Cover. Broadcast channels. IEEE Trans. on Information Theory, 18(1):2--14, Jan. 1972.
• 8: R.L. Cruz and A.V. Santhanam. Optimal routing, link scheduling and power control in multi-hop wireless networks. In IEEE Infocom Proceedings, pages 702--711. San Francisco, CA, March 30--April 3, 2003.
• 9: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 10: T. Elbatt and A. Ephremides. Joint scheduling and power control for wireless ad-hoc networks. In IEEE Infocom Proceedings, pages 976--984. New York, NY, June 23-27, 2002.
• 11: 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
• 12: A.J. Goldsmith and S.-G. Chua. Adaptive coded modulation for fading channels. IEEE Trans. on Communications, 46(5):595--602, May 1998.
• 13: P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE Trans. on Information Theory, 46(2):388--404, March 2000.
• 14: Alireza Keshavarz-Haddad , Rudolf H. Riedi, Bounds for the capacity of wireless multihop networks imposed by topology and demand, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288142]
• 15: Y.T. Hou, Y. Shi, and H.D. Sherali. Optimal spectrum sharing for multi-hop software defined radio networks. In IEEE Infocom Proceedings, pages 1--9. Anchorage, AL, May 6-12, 2007.
• 16: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 17: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080837]
• 18: Pradeep Kyasanur , Nitin H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080835]
• 19: X. Qiu and K. Chawla. On the performance of adaptive modulation in cellular systems. IEEE Trans. on Communications, 47(6):884--895, May 1999.
• 20: K. Ramachandran, E. Belding-Royer, K. Almeroth, and M. Buddhikot. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom Proceedings, 12 pages. Barcelona, Catalunya, Spain, April 23-29, 2006.
• 21: A. Raniwala and T. Chiueh. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network. In IEEE Infocom Proceedings, pages 2223--2234. Miami, FL, March 13-17, 2005.
• 22: Y. Shi and Y.T. Hou. Optimal power control for multi-hop software defined radio networks. In IEEE Infocom Proceedings, pages 1694--1702. Anchorage, AL, May 6-12, 2007.
• 23: J. Tang, G. Xue, C. Chandler, and W. Zhang. Interference-aware routing in multihop wireless networks using directional antennas. In IEEE Infocom Proceedings, pages 751--760. Miami, FL, March 13-17, 2005.
• 24: Weizhao Wang , Yu Wang , Xiang-Yang Li , Wen-Zhan Song , Ophir Frieder, Efficient interference-aware TDMA link scheduling for static wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161119]
• 25: Yuan Yuan , Paramvir Bahl , Ranveer Chandra , Thomas Moscibroda , Yunnan Wu, Allocating dynamic time-spectrum blocks in cognitive radio networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288125]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Performance, Theory

Keywords:
cross-layer optimization, interference modeling, multi-hop wireless network, physical model, protocol model