SpringerLink
Log in

Network Coding Techniques for Wireless and Sensor Networks

  • Chapter
  • First Online:
The Art of Wireless Sensor Networks

Part of the book series: Signals and Communication Technology ((SCT))

Abstract

Network coding is a technique where relay nodes mix packets using mathematical operations, which can increase the throughput. Network coding was first proposed for wired networks to solve the bottleneck in a single multicast session problem and to increase the throughput. However, the broadcast nature of wireless networks and the diversity of the links make network coding more attractive in wireless networks. Network coding can be classified as either inter or intra-session. Inter-session network coding allows the packets from different sessions (sources) to be mixed to increase the throughput. In contrast, intra-session network coding, which can be used to address the packet loss problem, uses the diversity of the wireless links and mixes packets from the same sessions. In this chapter, we survey the recent works on network coding in both general wireless networks and wireless sensor networks. We present various network coding techniques, their assumptions, applications, as well as an overview of the proposed methods.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. C. Cordeiro, H. Gossain, R. Ashok, D. Agrawal, The Last Mile: Wireless Technologies for Broadband and Home Networks, in Tutorial Presented in the 21th Brazilian Symposium on, Computer Networks, 2003

    Google Scholar 

  2. S. Cherry, The wireless last mile. IEEE Spectrum 40(9), 18–22 (2003)

    Google Scholar 

  3. I. Akyildiz, X. Wang, A survey on wireless mesh networks. Commun. Mag. IEEE 43(9), S23–S30 (2005)

    Article  Google Scholar 

  4. I. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Raptor codes. IEEE Commun. mag. 40(8), 102–114 (2002)

    Article  Google Scholar 

  5. D. Aguayo, J. Bicket, S. Biswas, G. Judd, R. Morris, Link-Level Measurements from an 802.11 b Mesh Network, in ACM SIGCOMM, 2004, pp. 121–132

    Google Scholar 

  6. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, J. Crowcroft, XORs in the air: Practical wireless network coding. ACM SIGCOMM Comput. Commun. Rev. 36(4), 243–254 (2006)

    Article  Google Scholar 

  7. S. Biswas, R. Morris, ExOR: Opportunistic multi-hop routing for wireless networks. ACM SIGCOMM Comput. Commun. Rev. 35(4), 133–144 (2005)

    Article  Google Scholar 

  8. S. Chachulski, M. Jennings, S. Katti, D. Katabi, Trading Structure for Randomness in Wireless Opportunistic Routing, in ACM SIGCOMM, 2007

    Google Scholar 

  9. L. Keller, E. Atsan, K. Argyraki, C. Fragouli, SenseCode: Network Coding for Reliable Sensor Networks, in EPFL Technical, Report, 2009

    Google Scholar 

  10. I. Hou, Y. Tsai, T. Abdelzaher, I. Gupta, AdapCode: Adaptive Network Coding for Code Updates in Wireless Sensor Networks, in IEEE INFOCOM, 2008

    Google Scholar 

  11. P. Maymounkov, Online Codes, in Technical Report TR2002-833, New York University, 2002

    Google Scholar 

  12. M. Luby, Lt Codes, in The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 271–280

    Google Scholar 

  13. A. Shokrollahi, Raptor codes. IEEE Trans. Inform. Theor. 52(6), 2551–2567 (2006)

    Article  MathSciNet  Google Scholar 

  14. S. Sengupta, S. Rayanchu, S. Banerjee, An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing, in IEEE INFOCOM, 2007, pp. 1028–1036

    Google Scholar 

  15. T. Cui, L. Chen, T. Ho, Energy Efficient Opportunistic Network Coding for Wireless Networks, in IEEE INFOCOM, 2008, pp. 361–365

    Google Scholar 

  16. H. Seferoglu and A. Markopoulou, Network Coding-Aware Queue Management for Unicast Flows Over Coded Wireless Networks, in NetCod, 2010, pp. 1–6

    Google Scholar 

  17. J. Le, J. Lui, D. Chiu, How Many Packets Can We Encode?-An Analysis of Practical Wireless Network Coding, in IEEE INFOCOM, 2008, pp. 371–375

    Google Scholar 

  18. S. Rayanchu, S. Sen, J. Wu, S. Banerjee, S. Sengupta, Loss-aware network coding for unicast wireless sessions: Design, implementation, and performance evaluation. SACM SIGMETRICS Perform. Eval. Rev. 36(1), 85–96 (2008)

    Article  Google Scholar 

  19. A. Khreishah, J. Wu, P. Ostovari, and I. Khalil, Flow Based Xor Network Coding for Lossy Wireless Networks, in IEEE GLOBECOM, 2011

    Google Scholar 

  20. A. Khreishah, I. Khalil, P. Ostovari, J. Wu, Flow-based xor network coding for lossy wireless networks. IEEE Trans. Wireless Commun. 11(6), 2321–2329 (2012)

    Article  Google Scholar 

  21. S. Zhang, S. Liew, P. Lam, Hot Topic: Physical-Layer Network Coding, in MobiCom, 2006, pp. 358–365

    Google Scholar 

  22. I. Jawhar, N. Mohamed, D.P. Agrawal, Linear wireless sensor networks: Classification and applications. J. Network Comput. Appl. 34(5), 1671–1682 (2011)

    Article  Google Scholar 

  23. X. Zhang, B. Li, Optimized multipath network coding in lossy wireless networks. IEEE J. Selected Areas Commun. 27(5), 622–634 (2009)

    Article  Google Scholar 

  24. X. Zhang, B. Li, Dice: A Game Theoretic Framework for Wireless Multipath Network Coding, in ACM MobiHoc, 2008

    Google Scholar 

  25. Y. Lin, B. Li, B. Liang, Codeor: Opportunistic Routing in Wireless Mesh Networks with Segmented Network Coding, in IEEE ICNP, 2008

    Google Scholar 

  26. L. Brakmo, L. Peterson, TCP vegas: End to end congestion avoidance on a global internet. IEEE J. Selected Areas Commun. 13(8), 1465–1480 (1995)

    Article  Google Scholar 

  27. B. Radunović, C. Gkantsidis, P. Key, P. Rodriguez, Toward practical opportunistic routing with intra-session network coding for mesh networks. IEEE/ACM Trans. Network. 18(2), 420–433 (2010)

    Article  Google Scholar 

  28. D. Koutsonikolas, C. Wang, Y. Hu, CCACK: Efficient Network Coding Based Opportunistic Routing Through Cumulative Coded Acknowledgments, in IEEE INFOCOM, 2010, pp. 1–9

    Google Scholar 

  29. K. Srinivasan, M. Jain, J. Choi, T. Azim, E. Kim, P. Levis, B. Krishnamachari, The \(\kappa \) Factor: Inferring Protocol Performance Using Inter-Link Reception Correlation, in ACM MobiCom, 2010, pp. 7317–328

    Google Scholar 

  30. A. Khreishah, I. Khalil, J. Wu, Universal Opportunistic Routing Scheme Using Network Coding, in IEEE SECON, 2012

    Google Scholar 

  31. S. Katti, D. Katabi, H. Balakrishnan, M. Medard, Symbol-level network coding for wireless mesh networks. ACM SIGCOMM Comput. Commun. Rev. 38(4), 401–412 (2008)

    Article  Google Scholar 

  32. È. Gabidulin, Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985)

    MathSciNet  Google Scholar 

  33. M. Li, Z. Yang, W. Lou, Codeon: Cooperative popular content distribution for vehicular networks using symbol level network coding. IEEE J. Selected Areas Commun. 29(1), 223–235 (2011)

    Article  Google Scholar 

  34. Z. Yang, M. Li, W. Lou, CodePlay: Live multimedia streaming in vanets using symbol-level network coding. IEEE Trans. Wireless Commun. 11(8), 3006–3013 (2012)

    Google Scholar 

  35. C. Qin, Y. **an, C. Gray, N. Santhapuri, S. Nelakuditi, \(I^2\)MIX: Integration of Intra-Flow and Inter-Flow Wireless Network Coding, in IEEE SECON Workshops, 2008, pp. 1–6

    Google Scholar 

  36. H. Seferoglu, A. Markopoulou, K. Ramakrishnan, I2NC: Intra-and Inter-Session Network Coding for Unicast Flows in Wireless Networks, in IEEE INFOCOM, 2011, pp. 1035–1043

    Google Scholar 

  37. C. Wang, A. Khreishah, N. Shroff, Cross-Layer Optimizations for Intersession Network Coding on Practical 2-Hop Relay Networks, in Asilomar, vol. 41, 2009, pp. 771–775

    Google Scholar 

  38. A. Khreishah, I. Khalil, J. Wu, Polynomial Time and Provably Efficient Network Coding Scheme for Lossy Wireless Networks, in IEEE MASS, 2011

    Google Scholar 

  39. A. Khreishah, I. Khalil,, J. Wu, Low Complexity and Provably Efficient Algorithm for Joint Inter and Intrasession Network Coding in Wireless Networks, in IEEE Transactions on Parallel and Distributed Systems, 2012

    Google Scholar 

  40. H. Holbrook, S. Singhal, D. Cheriton, P. fan and c. zhi and c. wei and k. ben letaief. ACM SIGCOMM Comput. Commun. Rev. 25(4), 328–341 (2005)

    Google Scholar 

  41. D. Koutsonikolas, Y. Hu, C. Wang, Pacifier: High-Throughput, Reliable Multicast without Crying Babies, in Wireless Mesh Networks, in IEEE INFOCOM, 2009, pp. 2473–2481

    Google Scholar 

  42. A. Khreishah, I. Khalil, J. Wu, Distributed Network Coding-Based Opportunistic Routing for Multicast, in MobiHoc, 2012, pp. 115–124

    Google Scholar 

  43. L. Li, R. Ramjee, M. Buddhikot, S. Miller, Network Coding-Based Broadcast in Mobile Ad-Hoc Networks, in IEEE INFOCOM, May 2007, pp. 1739–1747

    Google Scholar 

  44. W. Lou, J. Wu, On reducing broadcast redundancy in ad hoc wireless networks. IEEE Trans. Mobile Comput., 1(2), 111–122 (2002)

    Google Scholar 

  45. S. Yang, J. Wu, Efficient broadcasting using network coding and directional antennas in MANETs. IEEE Trans. Parallel Distrib. Syst. 21(2), 148–161 (Feb 2010)

    Google Scholar 

  46. S. Yang, J. Wu, F. Dai, Efficient Backbone Construction Methods in Manets Using Directional Antennas, in ICDCS, 2007

    Google Scholar 

  47. Z. Dong, C. Zhan, Y. Xu, Delay Aware Broadcast Scheduling in Wireless Networks Using Network Coding, in IEEE NSWCTC, 2010, pp. 214–217

    Google Scholar 

  48. C. Zhan, Y. Xu, Broadcast Scheduling Based on Network Coding in Time Critical Wireless Networks, in IEEE International Symposium on Network Coding, June 2010

    Google Scholar 

  49. P. Ostovari, J. Wu, A. Khreishah, Deadline-Aware Broadcasting in Wireless Networks with Local Network Coding, in IEEE ICNC, Jan 2012

    Google Scholar 

  50. P. Ostovari, A. Khreishahand, J. Wu, Deadline-Aware Broadcasting in Wireless Networks with Network Coding, in IEEE GLOBECOM, Dec 2012

    Google Scholar 

  51. C. Fragouli, J. Widmer, J.L. Boudec, A Network Coding Approach to Energy Efficient Broadcasting: From Theory to Practice, in IEEE INFOCOM, 2006, pp. 1–11

    Google Scholar 

  52. C. Fragouli, J. Widmer, J.L. Boudec, Efficient broadcasting using network coding. IEEE/ACM Trans. Network. 16(2), 450–463 (2008)

    Google Scholar 

  53. D. Nguyen, T. Tran, T. Nguyen, B. Bose, Wireless broadcast using network coding. IEEE Trans. Vehicular Technol. 58(2), 914–925 (2009)

    Article  Google Scholar 

  54. L. Lu, M. **ao, M. Skoglund, L. Rasmussen, G. Wu, S. Li, Efficient Network Coding for Wireless Broadcasting, in IEEE WCNC, 2010, pp. 1–6

    Google Scholar 

  55. W. Fang, F. Liu, Z. Liu, L. Shu, S. Nishio, Reliable Broadcast Transmission in Wireless Networks Based on Network Coding”, in IEEE INFOCOM Workshops (INFOCOM WKSHPS), 2011, pp. 555–559

    Google Scholar 

  56. D. Welsh, M. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10(1), 85–86 (1967)

    Article  MATH  Google Scholar 

  57. D. Koutsonikolas, Y. Hu, C. Wang, M. Comer, A. Mohamed, Efficient Online WiFi Delivery of Layered-Coding Media Using Inter-Layer Network Coding, in ICDCS, 2011, pp. 237–247

    Google Scholar 

  58. U. Horn, K. Stuhlmüller, M. Link, B. Girod, Robust internet video transmission based on scalable coding and unequal error protection. Sig. Process. Image Commun. 15(1), 77–94 (1999)

    Article  Google Scholar 

  59. D. Wu, Y. Hou, Y. Zhang, Scalable video coding and transport over broadband wireless networks. Proc. IEEE 89(1), 6–20 (2001)

    Article  Google Scholar 

  60. A. Majumda, D. Sachs, I. Kozintsev, K. Ramchandran, M. Yeung, Multicast and unicast real-time video streaming over wireless lans. IEEE Trans. Circuits Syst. Video Technol. 12(6), 524–534 (2002)

    Article  Google Scholar 

  61. D. Koutsonikolas, Y. Hu, C. Wang, M. Comer, A. Mohamed, On the Performance of Network Coding in Multi-Resolution Wireless Video Streaming, in NetCod, 2010, pp. 1–6

    Google Scholar 

  62. M. Halloush, H. Radha, Practical Network Coding for Scalable Video in Error Prone Networks, in PCS, 2009, pp. 1–4

    Google Scholar 

  63. L. Lu, M. **ao, L. Rasmussen, Relay-Aided Broadcasting with Instantaneously Decodable Binary Network Codes, in ICCCN, 2011, pp. 1–5

    Google Scholar 

  64. H. Shwe, F. Adachi, Power Efficient Adaptive Network Coding in Wireless Sensor Networks, in IEEE ICC, 2011, pp. 1–5

    Google Scholar 

  65. Z. Yang, M. Li, W. Lou, R-code: Network Coding Based Reliable Broadcast in Wireless Mesh Networks with Unreliable Links, in IEEE GLOBECOM, 2009

    Google Scholar 

  66. R. Chandanala, R. Stoleru, Network Coding in Duty-Cycled Sensor Networks, in INSS, 2010, pp. 203–210

    Google Scholar 

  67. S. Sorour, S. Valaee, Minimum Broadcast Decoding Delay for Generalized Instantly Decodable Network Coding, in IEEE GLOBECOM, 2010, pp. 1–5

    Google Scholar 

Download references

Acknowledgments

This research was supported in part by NSF grants ECCS 1231461, ECCS 1128209, CNS 1138963, CNS 1065444, and CCF 1028167.

Author information

Authors and Affiliations

  1. Department of Computer and Information Sciences, Temple University, Philadelphia, PA, 19122, USA

    Pouya Ostovari & Jie Wu

  2. Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, 07102, USA

    Abdallah Khreishah

Authors
  1. Pouya Ostovari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jie Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Abdallah Khreishah
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jie Wu .

Editor information

Editors and Affiliations

  1. College of Engineering and Computer Science, Department of Computer and Information Science, University of Michigan-Dearborn, Dearborn, Michigan, USA

    Habib M. Ammari

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Ostovari, P., Wu, J., Khreishah, A. (2014). Network Coding Techniques for Wireless and Sensor Networks. In: Ammari, H. (eds) The Art of Wireless Sensor Networks. Signals and Communication Technology. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40009-4_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-40009-4_5

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-40008-7

  • Online ISBN: 978-3-642-40009-4

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation