«Chapter 3 Opportunistic Routing in Wireless Mesh Networks Amir Darehshoorzadeh, Lloren¸ Cerd`-Alabern and Vicent Pla c a Contents 3.1 Introduction ...»
Our numerical results have shown that using any OR algorithm outperforms the traditional uni-path routing. Furthermore, if the maximum number of candidates is not limited, all of the algorithms obtain almost the same expected number of transmissions. Such assumption is not realistic since the algorithms may choose a large number of candidates, which will introduce large signaling overhead and probably duplicate transmissions. When the maximum number of candidates is limited, our results have shown that the expected number of transmissions required by ExOR is larger than that of the other OR algorithms. This is because of the coarse selection of the CSs of ExOR, which relies on ETX. On the other hand, the performance obtained with OAPF has proven to be very close to the optimal algorithms. We have also observed that the variance of the number of transmissions can be substantially reduced by using OR. This result is specially important in networks with real-time requirements.
Regarding the execution times, the fact that EXOR is based on ETX makes this algorithm much faster than the others. For the optimum algorithms, we have observed that MTS outperforms LCOR. However, both algorithms require extremely large execution times to compute the CSs in a dense network (on the order of hours in a modern PC). On the other hand, OAPF is able to run the candidate selection with execution times orders of magnitude lower than the optimum algorithms (on the order of minutes) while a relatively low degradation of performance was observed. Therefore, we conclude that a fast and simple OR candidate selection algorithm such as OAPF may be preferable in dynamic networks, where the CSs are likely to be updated frequently.
Bibliography  The Network Simulator ns-2. 25  Daniel Aguayo, John Bicket, Sanjit Biswas, Glenn Judd, and Robert Morris. Link-level measurements from an 802.11b mesh network. SIGCOMM Comput. Commun. Rev., 34:121–132, August 2004. 13  R. Ahlswede, Ning Cai, S.-Y.R. Li, and R.W. Yeung. Network information ﬂow. Information Theory, IEEE Transactions on, 46(4):1204–1216, July 2000. 9  F. Baccelli, B. Blaszczyszyn, and P. Muhlethaler. On the performance of time-space opportunistic routing in multihop mobile ad hoc networks. In Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks and Workshops, 2008. WiOPT 2008. 6th International Symposium on, pages 307–316, April 2008. 5, 20  S. Biswas and R. Morris. ExOR: opportunistic multi-hop routing for wireless networks.
ACM SIGCOMM Computer Communication Review, 35(4):133–144, 2005. 2, 5, 11, 13  Sanjit Biswas and Robert Morris. Opportunistic routing in multi-hop wireless networks.
ACM SIGCOMM Computer Communication Review, 34(1):69–74, 2004. 5, 8, 11, 12  R. Bruno and M. Nurchis.
Survey on Diversity Based Routing in Wireless Mesh Networks:
Challenges and Solutions. Computer Communications, 33(3):269–282, 2010. 9  A.S. Cacciapuoti, M. Caleﬃ, and L. Paura. Optimal constrained candidate selection for opportunistic routing. In IEEE GLOBECOM, pages 1–5, December 2010. 21  Lloren¸ Cerd`-Alabern, Amir Darehshoorzadeh, and Vicent Pla. On the maximum perc a formance in opportunistic routing. In World of Wireless Mobile and Multimedia Networks (WoWMoM), 2010 IEEE International Symposium on a, pages 1–8, 2010. 5, 21, 27  Lloren¸ Cerd`-Alabern, Vicent Pla, and Amir Darehshoorzadeh. On the performance c a modeling of opportunistic routing. In MobiOpp ’10: Proceedings of the Second International Workshop on Mobile Opportunistic Networking, pages 15–21, New York, NY, USA, 2010. ACM. 7, 21  Szymon Chachulski, Michael Jennings, Sachin Katti, and Dina Katabi. Trading structure for randomness in wireless opportunistic routing. In SIGCOMM ’07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, pages 169–180, New York, NY, USA, 2007. ACM. 5, 9, 18  Amir Darehshoorzadeh and Lloren¸ Cerd`-Alabern. A new multicast opportunistic routc a ing protocol for wireless mesh networks. In Vicente Casares-Giner, Pietro Manzoni, and Ana Pont, editors, NETWORKING 2011 Workshops, volume 6827 of Lecture Notes in Computer Science, pages 62–72. Springer Berlin / Heidelberg, 2011. 5, 20  Amir Darehshoorzadeh, Lloren¸ Cerd`-Alabern, and Vicent Pla. Modeling and comc a parison of candidate selection algorithms in opportunistic routing. Computer Networks, 55(13):2886– 2898, 2011. 5  Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A highthroughput path metric for multi-hop wireless routing. Wireless Networks, 11(4):419– 434, 2005. 6  H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli. Least-cost opportunistic routing.
In Proceedings of 2007 Allerton Conference on Communication, Control, and Computing, 2007. 5, 7, 11, 15  H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli. Valuable detours: Least-cost anypath routing. IEEE/ACM Transactions on Networking, 19(2):333–346, April 2011.
2, 24  D. Fuste-Vilella, J. Garcia-Vidal, and J.D. Morillo-Pozo. Cooperative forwarding in IEEE 802.11-based MANETs. In Wireless Days, 2008. WD ’08. 1st IFIP, pages 1–5, nov. 2008. 2, 5  Che-Jung Hsu, Huey-Ing Liu, and Winston Khoon Guan Seah. Opportunistic routing a review and the challenges ahead. Computer Networks, 55(15):3592–3603, 2011. 3, 9,  Shweta Jain and Samir R. Das. Exploiting path diversity in the link layer in wireless ad hoc networks. Ad Hoc Netw., 6(5):805–825, 2008. 6, 10  Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel M´dard, and Jon e Crowcroft. Xors in the air: practical wireless network coding. In Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM ’06, pages 243–254, New York, NY, USA, 2006. ACM. 5,  Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel M´dard, and Jon e Crowcroft. XORs in the air: practical wireless network coding. IEEE/ACM Trans.
Netw., 16(3):497–510, 2008. 5, 18  D. Koutsonikolas, Y.C. Hu, and Chih-Chun Wang. Paciﬁer: High-throughput, reliable multicast without “crying babies” in wireless mesh networks. In INFOCOM 2009, IEEE, pages 2473–2481, 2009. 5, 20  M. Kurth, A. Zubow, and J.-P. Redlich. Cooperative opportunistic routing using transmit diversity in wireless mesh networks. In IEEE INFOCOM, pages 1310–1318, 2008. 21  Peter Larsson. Selection diversity forwarding in a multihop packet radio network with fading channel and capture. SIGMOBILE Mob. Comput. Commun. Rev., 5(4):47–54, 2001. 2, 8  Peter Larsson. Selection diversity forwarding in a multihop packet radio network with fading channel and capture. SIGMOBILE Mob. Comput. Commun. Rev., 5(4):47–54, 2001. 5  G. Latouche and V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling. ASA-SIAM, 1999. 23  Jilin Le, J. Lui, and Dah Ming Chiu. Dcar: Distributed coding-aware routing in wireless networks. In Distributed Computing Systems, 2008. ICDCS ’08. The 28th International Conference on, pages 462–469, June 2008. 19  Tan Le and Yong Liu. Opportunistic overlay multicast in wireless networks. In GLOBECOM, pages 1–5, 2010. 5, 20  Yanhua Li, Wei Chen, and Zhi-Li Zhang. Optimal forwarder list selection in opportunistic routing. In Mobile Adhoc and Sensor Systems, 2009. MASS ’09. IEEE 6th International Conference on, pages 670–675, October 2009. 5, 7, 11, 16  Yanhua Li and Zhi-Li Zhang. Random walks on digraphs: a theoretical framework for estimating transmission costs in wireless routing. In 29th conference on Information communications, INFOCOM’10, pages 2775–2783. IEEE Press, 2010. 21  Haitao Liu, Baoxian Zhang, H. Mouftah, Xiaojun Shen, and Jian Ma. Opportunistic routing for wireless ad hoc and sensor networks: Present and future directions. Communications Magazine, IEEE, 47(12):103–109, December 2009. 6, 11  Mingming Lu and Jie Wu. Opportunistic routing algebra and its applications. In IEEE INFOCOM, pages 2374–2382, 2009. 7, 21  Chun-Pong Luk, Wing-Cheong Lau, and On-Ching Yue. An analysis of opportunistic routing in wireless mesh network. In Communications, 2008. ICC ’08. IEEE International Conference on, pages 2877–2883, May 2008. 5, 20  R Development Core Team. R: A Language and Environment for Statistical Computing.
R Foundation for Statistical Computing, Vienna, Austria, 2008. ISBN 3-900051-07-0. 26  E. Rozner, J. Seshadri, Y. Mehta, and Lili Qiu. Soar: Simple opportunistic adaptive routing protocol for wireless mesh networks. Mobile Computing, IEEE Transactions on, 8(12):1622–1635, December 2009. 5, 13  R.C. Shah, S. Wietholter, and A. Wolisz. Modeling and analysis of opportunistic routing in low traﬃc scenarios. In Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2005. WIOPT 2005. Third International Symposium on, pages 294–304. IEEE, 2005. 5, 6  S. Ca˝adas-Hurtado Trivi˝o-Cabrera, Alicia. Survey on opportunistic routing in multin n hop wireless networks. IJCNIS, 3(2), 2011. 6  Yang WenZhong, Zhang ZhenYu, Wang Bo, and Wu XiaoHong. A reliable multicast for manets based on opportunistic routing. In Wireless Communications Networking and Mobile Computing (WiCOM), 2010 6th International Conference on, pages 1–4, sept.
2010. 20  Cedric Westphal. Opportunistic routing in dynamic ad hoc networks: the oprah protocol.
In Mobile Adhoc and Sensor Systems (MASS), 2006 IEEE International Conference on, pages 570–573, October 2006. 6  J. Wu, M. Lu, and F. Li. Utility-based opportunistic routing in multi-hop wireless networks. In Distributed Computing Systems, 2008. ICDCS’08. The 28th International Conference on, pages 470–477, 2008. 21  Yunnan Wu, S.M. Das, and R. Chandra. Routing with a markovian metric to promote local mixing. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 2381–2385, May 2007. 19  Y. Yan, B. Zhang, J. Zheng, and J. Ma. Core: a coding-aware opportunistic routing mechanism for wireless mesh networks [accepted from open call]. Wireless Communications, IEEE, 17(3):96–103, June 2010. 5, 19  Yan Yan, Baoxian Zhang, H.T. Mouftah, and Jian Ma. Practical coding-aware mechanism for opportunistic routing in wireless mesh networks. In Communications, 2008.
ICC ’08. IEEE International Conference on, pages 2871–2876, May 2008. 5, 9, 19  Shengbo Yang, Feng Zhong, Chai Kiat Yeo, Bu Sung Lee, and J. Boleng. Position based opportunistic routing for robust data delivery in manets. In Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE, pages 1–6, December 2009. 5, 19  Wei Chen Yanhua Li and Zhi-Li Zhang. Design of forwarder list selection scheme in opportunistic routing protocol. Technical-report, University of Minnesota, Minneapolis, MN, US, 2008. 16  Y. Yuan, H. Yang, S.H.Y. Wong, S. Lu, and W. Arbaugh. ROMER: Resilient opportunistic mesh routing for wireless mesh networks. In IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005. 6  Kai Zeng, Wenjing Lou, Jie Yang, and Donald R. Brown, III. On throughput eﬃciency of geographic opportunistic routing in multihop wireless networks. Mob. Netw. Appl., 12:347–357, December 2007. 5, 19  Bin Zhao, Rohit Iyer Seshadri, Matthew C. Valenti, Harbinger). Like Geraf, and Harbinger Assumes That. Geographic random forwarding with hybrid-arq for ad hoc networks with rapid sleep cycles. In in Proc. IEEE Military Commun. Conf. (MILCOM, 2004. 6  Zifei Zhong, Junling Wang, Srihari Nelakuditi, and Guor-Huar Lu. On selection of candidates for opportunistic anypath forwarding. SIGMOBILE Mob. Comput. Commun.
Rev., 10(4):1–2, 2006. 5, 6, 7, 11, 13, 24  M. Zorzi and R.R. Rao. Geographic random forwarding (geraf) for ad hoc and sensor networks: multihop performance. Mobile Computing, IEEE Transactions on, 2(4):337–