While network coding is well known for its efficiency and usefulness in wireless sensor networks, the excessive costs associated with decoding computation and complexity still hinder its adoption into practical use. On the other hand, high-performance microprocessors with heterogeneous multi-cores would be used as processing nodes of the wireless sensor networks in the near future. To this end, this paper introduces an efficient network coding algorithm developed for the heterogenous multi-core processors. The proposed idea is fully tested on one of the currently available heterogeneous multi-core processors referred to as the Cell Broadband Engine.
References
[1]
Ahlswede, R; Ning, C; Li, S-YR; Yeung, RW. Network information flow. IEEE Trans. Inf. Theory 2000, 46, 1204–1216, doi:10.1109/18.850663.
[2]
Sanchez-Avila, C; Sanchez-Reillol, R. The Rijndael Block Cipher (AES proposal): A comparison with DES. Proceedings of 2001 IEEE the 35th International Carnahan Conference on Security Technology, London, UK, 16–19 October 2001; pp. 229–234.
[3]
Li, B; Wu, Y. Network coding. Proc. IEEE 2011, 99, 363–365, doi:10.1109/JPROC.2010.2096251.
[4]
Gkantsidis, C; Miller, J; Rodriguez, P. Comprehensive view of a live network coding P2P system. Proceedings of the 6th ACM SIGCOMM Conference on Internet Measurement, IMC ’06, Rio de Janeiro, Brazil, October 2006; pp. 177–188.
[5]
Widmer, J; Le Boudec, JY. Network coding for efficient communication in extreme networks. Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking, WDTN ’05, Philidelphia, PA, USA, August 2005; pp. 284–291.
[6]
Al-Kofahi, OM; Kamal, AE. Network coding-based protection of many-to-one wireless flows. IEEE J. Sel. Areas Commun 2009, 27, 797–813, doi:10.1109/JSAC.2009.090619.
[7]
Woldegebreal, DH; Karl, H. Network-coding-based cooperative transmission in wireless sensor networks: Diversity-multiplexing tradeoff and coverage area extension. Proceedings of the 5th European Conference on Wireless Sensor Networks, EWSN’08, Bologna, Italy, 30 January– 1 February 2008; pp. 141–155.
[8]
Platz, D; Woldegebreal, DH; Karl, H. Random network coding in wireless sensor networks: Energy efficiency via cross-layer approach. Proceedings of 2008 IEEE the 10th International Symposium on Spread Spectrum Techniques and Applications, ISSSTA ’08, Bologna, Italy, 25–28 August 2008; pp. 654–660.
[9]
Hou, IH; Tsai, YE; Abdelzaher, T; Gupta, I. AdapCode: Adaptive network coding for code updates in wireless sensor networks. Proceedings of the IEEE 27th Conference on Computer Communications, INFOCOM 2008, Phoenix, AZ, USA, 13–18 April 2008; pp. 1517–1525.
[10]
Egbogah, EE; Fapojuwo, AO. A survey of system architecture requirements for health care-based wireless sensor networks. Sensors 2011, 11, 4875–4898, doi:10.3390/s110504875. 22163881
[11]
Wu, Y; Chou, PA; Kung, SY. Information Exchange in Wireless Networks with Network Coding and Physical-Layer Broadcast. Technical Report MSR-TR-2004-78;; Microsoft Research: Cambridge, UK, 2004.
[12]
Widmer, J; Fragouli, C; LeBoude, JY. Energy efficient broadcasting in wireless ad hoc networks. Proceedings of First Workshop on Network Coding, Theory, and Applications, NetCod ’05, Riva del Garda, Italy, 7 April 2005.
[13]
Fragouli, C; Widmer, J; Le Boudec, JY. A network coding approach to energy efficient broadcasting: From theory to practice. Proceedings the 25th IEEE International Conference on Computer Communications, INFOCOM 2006, Barcelona, Spain, April 2006.
[14]
Cai, N; Yeung, R. Secure network coding. Proceedings of 2002 IEEE International Symposium on Information Theory, Lausanne, Switzerland, 30 June–5 July 2002; p. 323.
[15]
Cai, N; Yeung, R. Secure network coding on a wiretap network. IEEE Trans. Inf. Theory 2011, 57, 424–435, doi:10.1109/TIT.2010.2090197.
[16]
Liu, Z; Wu, C; Li, B; Zhao, S. UUSee: Large-Scale operational on-demand streaming with random network coding. Proceedings of IEEE INFOCOM, San Diego, CA, USA, 14–19 March 2010; pp. 1–9.
[17]
Geer, D. Chip makers turn to multicore processors. Computer 2005, 38, 11–13.
[18]
Ohara, S; Suzuki, M; Saruwatari, S; Morikawa, H. A prototype of a multi-core wireless sensor node for reducing power consumption. Proceedings of the 2008 International Symposium on Applications and the Internet, Washington, DC, USA, 28 July–1 August 2008; pp. 369–372.
[19]
Spies, C; Indrusiak, L; Glesner, M. Comparative analysis of multitask scheduling algorithms for reconfigurable computing regarding context switches and configuration cache usage. Proceedings of the 3rd Southern Conference on Programmable Logic, SPL ’07, Mar del Plata, Argentina, 26–28 Feburary 2007; pp. 239–242.
[20]
Akyildiz, IF; Melodia, T; Chowdhury, KR. Wireless multimedia sensor Networks: Applications and testbeds. Proc. IEEE 2008, 96, 1588–1605, doi:10.1109/JPROC.2008.928756.
[21]
Bharadwaj, V; Robertazzi, TG; Ghose, D. Scheduling Divisible Loads in Parallel and Distributed Systems; IEEE Computer Society Press: Los Alamitos, CA, USA, 1996.
[22]
Bharadwaj, V; Ghose, D. Divisibleload theory: A new paradigm for load scheduling in distributed systems. Clust. Comput 2003, 6, 7–17, doi:10.1023/A:1020958815308.
[23]
Drozdowski, M. Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems. Technical Report 321;; Politechnika Poznanńska: Pozńan, Poland, 1997.
[24]
Intel Microprocessor Export Compliance Metrics. Available online: http://www.intel.com/support/processors/sb/cs-023143.htm (accessed on 3 July 2011).
[25]
Kahle, JA; Day, MN; Hofstee, HP; Johns, CR; Maeurer, TR; Shippy, D. Introduction to the cell multiprocessor. IBM J. Res. Dev 2005, 49, 589–604, doi:10.1147/rd.494.0589.
[26]
Pham, D; Aipperspach, T; Boerstler, D; Bolliger, M; Chaudhry, R; Cox, D; Harvey, P; Harvey, P; Hofstee, H; Johns, C; Kahle, J; Kameyama, A; Keaty, J; Masubuchi, Y; Pham, M; Pille, J; Posluszny, S; Riley, M; Stasiak, D; Suzuoki, M; Takahashi, O; Warnock, J; Weitzel, S; Wendel, D; Yazawa, K. Overview of the architecture, circuit design, and physical implementation of a first-generation cell processor. IEEE J. Solid-State Circuits 2006, 41, 179–196, doi:10.1109/JSSC.2005.859896.
[27]
Chou, PA; Wu, Y; Jain, K. Practical network coding. Proceedings of Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 20 October 2003.
[28]
Shojania, H; Li, B. Parallelized progressive network coding with hardware acceleration. Proceedings of 2007 the 15th IEEE International Workshop on Quality of Service, Evanston, IL, USA, 21–22 June 2007; pp. 47–55.
[29]
Bisseling, RH; van de Vorst, JGG. Parallel LU decomposition on a transputer network. Proceedings of the Shell Conference on Parallel Computing, Amsterdam, The Netherlands, 1–2 June 1988; pp. 61–77.
[30]
Melab, N; Talbi, EG; Petiton, S. A parallel adaptive Gauss-Jordan algorithm. J. Supercomput 2000, 17, 167–185, doi:10.1023/A:1008182404262.
[31]
Park, K; Park, JS; Ro, WW. On improving parallelized network coding with dynamic partitioning. IEEE Trans. Parallel Distrib. Syst 2010, 21, 1547–1560, doi:10.1109/TPDS.2010.40.
[32]
Arevalo, A; Matinata, RM; Pandian, MR; Peri, E; Ruby, K; Thomas, F; Almond, C. Programming the Cell Broadband Engine Architecture: Examples and Best Practices; Vervante: Springville, UT, USA, 2008.
[33]
PPU & SPU C/C++ Language Extension Specification. Available online: https://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/30B3520C93F437AB87257060006FFE5E (accessed on 3 July 2011).
[34]
Shojania, H; Li, B; Wang, X. Nuclei: GPU-Accelerated many-core network coding. Proceedings of IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 19–25 April 2009; pp. 459–467.
[35]
AltiVec Technology Programming Interface Manual. Available online: http://www.freescale.com/files/32bit/doc/refmanual/ALTIVECPIM.pdf (accessed on 3 July 2011).
[36]
Intel(R) 64 and IA-32 Architectures Optimization Reference Manual; Intel Corporation: Santa Clara, CA, USA, 2010.
[37]
Roth, R. Introduction to Coding Theory, 1st ed ed.; Cambridge University Press: Cambridge, UK, 2006.
[38]
Trenholme, S. AES’ Galois field. Available online: http://www.samiam.org/galois.html (accessed on 3 July 2011).
[39]
Koetter, R; Médard, M. An algebraic approach to network coding. IEEE/ACM Trans. Netw 2003, 11, 782–795, doi:10.1109/TNET.2003.818197.
[40]
Ho, T; Medard, M; Koetter, R; Karger, D; Effros, M; Shi, J; Leong, B. A random linear network coding approach to multicast. IEEE Trans. Inf. Theory 2006, 52, 4413–4430, doi:10.1109/TIT.2006.881746.
[41]
Lun, D; Ratnakar, N; Medard, M; Koetter, R; Karger, D; Ho, T; Ahmed, E; Zhao, F. Minimum-cost multicast over coded packet networks. IEEE Trans. Inf. Theory 2006, 52, 2608–2623, doi:10.1109/TIT.2006.874523.
[42]
Katti, S; Rahul, H; Hu, W; Katabi, D; Medard, M; Crowcroft, J. XORs in the air: Practical wireless network coding. IEEE/ACM Trans. Netw 2008, 16, 497–510, doi:10.1109/TNET.2008.923722.
[43]
Park, JS; Gerla, M; Lun, D; Yi, Y; Medard, M. Codecast: A network-coding-based ad hoc multicast protocol. IEEE Wirel. Commun 2006, 13, 76–81, doi:10.1109/WC-M.2006.250362.
[44]
Gkantsidis, C; Rodriguez, P. Network coding for large scale content distribution. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2005, Miami, FL, USA, 13–17 March 2005; 4, pp. 2235–2245.
[45]
Wang, M; Li, B. Lava: A reality check of network coding in peer-to-peer live streaming. Proceedings of the 26th IEEE International Conference on Computer Communications, INFOCOM 2007, Anchorage, AK, USA, 6–12 May 2007; pp. 1082–1090.
[46]
Kang, M; Kang, DI; Crago, SP; Park, GL; Lee, J. Design and development of a run-time monitor for multi-core architectures in cloud computing. Sensors 2011, 11, 3595–3610, doi:10.3390/s110403595. 22163811
[47]
Lee, U; Park, JS; Yeh, J; Pau, G; Gerla, M. Code torrent: Content distribution using network coding in VANET. Proceedings of the 1st International Workshop on Decentralized Resource Sharing in Mobile Computing and Networking, MobiShare ’06, Los Angeles, CA, USA, September 2006; pp. 1–5.
[48]
Shojania, H; Li, B. Random network coding on the iPhone: Fact or fiction? Proceedings of the 18th International Workshop on Network and Operating Systems Support for Digital Audio and Video, NOSSDAV ’09, Braunschweig, Germany, May 2009; pp. 37–42.
[49]
Lee, U; Park, JS; Yeh, J; Pau, G; Gerla, M. A content distribution system based on sparse linear network coding. Proceedings of the 3rd Workshop on Network Coding, Theory, and Applications, NetCod ’07, San Diego, CA, USA, January 2007; pp. 1–6.
[50]
Maymounkov, P; Harvey, NJA. Methods for efficient network coding. Proceedings of the 44th Annual Allerton Conference on Communication, Control, and Computing, Urbana, IL, USA, 27 September–29 September 2006.
[51]
Park, K; Park, JS; Ro, WW. Efficient parallelized network coding for P2P file sharing applications. Proceedings of the 4th International Conference on Advances in Grid and Pervasive Computing, GPC ’09, Geneva, Switzerland, 4–8 May 2009; pp. 353–363.
[52]
Csanky, L. Fast parallel matrix inversion algorithms. Proceedings of the 16th Annual Symposium on Foundations of Computer Science, SFCS ’75, Berkeley, CA, USA, 13–15 October 1975; pp. 11–12.
[53]
Drozdowski, M; Lawenda, M. Multi-installment divisible load processing in heterogeneous distributed systems: Research articles. Concurr. Comput. Pract. Exp 2007, 19, 2237–2253, doi:10.1002/cpe.1180.
[54]
Cari？o, RL; Banicescu, I. Dynamic load balancing with adaptive factoring methods in scientific applications. J. Supercomput 2008, 44, 41–63, doi:10.1007/s11227-007-0148-y.
[55]
Chu, X; Zhao, K; Wang, M. Accelerating network coding on many-core GPUs and multi-core CPUs. J. Commun 2009, 4, 902–909.
