Combination of intra-flow network coding and opportunistic routing: reliable communications over wireless mesh networks

ABSTRACT

Opportunistic routing has recently appeared as a technique aimed to increase the performance of wireless mesh networks, by taking advantage of the broadcast nature of the wireless medium. Despite the remarkable attention the research community has paid to it, there are still some issues that need to be addressed; one of the most relevant ones is the unnecessary forwarding of the same packet by a number of nodes. Since Random Linear Coding (RLC) mechanisms randomly mix packets before forwarding them, they can be exploited to avoid (or at least to minimize) the aforementioned problem. In a previous work we introduced a flexible Network Coding (NC) entity that we integrated within the ns-3 framework. We extend herewith its functionalities, by integrating an opportunistic routing module that enables it to be used over random topologies. In addition, we assess the performance of using different external algebraical libraries to carry out the coding/recoding/decoding operations (i.e. matrix inverse and rank calculation).

References

1. S. Biswas and R. Morris, "Opportunistic routing in multi-hop wireless networks," SIGCOMM Comput. Commun. Rev., vol. 34, no. 1, pp. 69--74, Jan. 2004. {Online}. Available: http://doi.acm.org/10.1145/972374.972387
2. D. Gómez, R. Rodríguez, E. Agüero, and L. Muñnoz, "Reliable Communications over Wireless Mesh Networks with Inter and Intra-Flow Network Coding," in Workshop on NS3 (WNS3), Atlanta, USA, 2014.
3. S. Chachulski, M. Jennings, S. Katti, and D. Katabi, "Trading structure for randomness in wireless opportunistic routing," SIGCOMM Comput. Commun. Rev., vol. 37, no. 4, pp. 169--180, Aug. 2007. {Online}. Available: http://doi.acm.org/10.1145/1282427.1282400
4. F. Lefevre and G. Vivier, "Understanding tcp's behavior over wireless links," in Communications and Vehicular Technology, 2000. SCVT-200. Symposium on. IEEE, 2000, pp. 123--130.
5. M. Zorzi, A. Chockalingam, and R. R. Rao, "Throughput analysis of tcp on channels with memory," Selected Areas in Communications, IEEE Journal on, vol. 18, no. 7, pp. 1289--1300, 2000.
6. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, and J. Crowcroft, "Xors in the air: Practical wireless network coding," SIGCOMM Comput. Commun. Rev., vol. 36, no. 4, pp. 243--254, Aug. 2006. {Online}. Available: http://doi.acm.org/10.1145/1151659.1159942
7. A. Boukerche and A. Darehshoorzadeh, "Opportunistic routing in wireless networks: Models, algorithms, and classifications," ACM Comput. Surv., vol. 47, no. 2, pp. 22:1--22:36, Nov. 2014. {Online}. Available: http://doi.acm.org/10.1145/2635675
8. D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris, "A high-throughput path metric for multi-hop wireless routing," Wirel. Netw., vol. 11, no. 4, pp. 419--434, Jul. 2005. {Online}. Available: http://dx.doi.org/10.1007/s11276-005-1766-z
9. M. Zorzi and R. Rao, "Geographic random forwarding (geraf) for ad hoc and sensor networks: multihop performance," Mobile Computing, IEEE Transactions on, vol. 2, no. 4, pp. 337--348, Oct 2003.
10. A. Darehshoorzadeh and L. Cerda-Alabern, "Distance progress based opportunistic routing for wireless mesh networks," in Wireless Communications and Mobile Computing Conference (IWCMC), 2012 8th International, Aug 2012, pp. 179--184.
11. R. Ahlswede, N. Cai, S.-Y. Li, and R. Yeung, "Network information flow," Information Theory, IEEE Transactions on, vol. 46, no. 4, pp. 1204--1216, Jul 2000.
12. Y. Lin, B. Li, and B. Liang, "Codeor: Opportunistic routing in wireless mesh networks with segmented network coding," in Network Protocols, 2008. ICNP 2008. IEEE International Conference on, Oct 2008, pp. 13--22.
13. 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, vol. 17, no. 3, pp. 96--103, June 2010.
14. E. W. Dijkstra, "A note on two problems in connexion with graphs," NUMERISCHE MATHEMATIK, vol. 1, no. 1, pp. 269--271, 1959.
15. "FFLAS-FFPACK. Finite Field Linear Algebra subroutines package," http://www-ljk.imag.fr/membres/Jean-Guillaume.Dumas/FFLAS/index.html.
16. "IT++ Mathematical library," http://itpp.sourceforge.net/.
17. M. Albrecht, The M4RIE Library -- Version 20120613, The M4RIE Team, 2012. {Online}. Available: http://m4ri.sagemath.org
18. S. Skiena, "Dijkstra's algorithm," Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Reading, MA: Addison-Wesley, pp. 225--227, 1990.
19. D. Gómez, P. Garrido, and R. Agüero, "Network coding architecture source code and documentation (ns-3)," https://github.com/pgarridounican/ns-3.20-OpportunisticRouting-.git.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Information systems

  • Information systems applications

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software selection and adaptation

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Empirical software validation

  • Software organization and properties

    • Extra-functional properties

      • Software performance

    • Software functional properties

      • Formal methods