Communications
Volume 3, Issue 4, July 2015, Pages: 77-80

Multicast Algorithms over Wireless Networks Using Network Coding: A Review

Emmanuel Adewale Adedokun*, Joseph Stephen Soja, Abdoulie.S Tekanyi

Department of Electrical and Computer Engineering, Faculty of Engineering. Ahmadu Bello University Zaria, Nigeria

Email address:

(E. A. Adedokun)

To cite this article:

Emmanuel Adewale Adedokun, Joseph Stephen Soja, Abdoulie.S Tekanyi. Multicast Algorithms over Wireless Networks Using Network Coding: A Review.Communications.Vol.3, No. 4, 2015, pp. 77-80. doi: 10.11648/j.com.20150304.12


Abstract: Multicasting over wireless network has been an area of intensive research and many researchers have employed the use of algorithms for addressing multicast problems. With the fast development in technology and the use of multimedia applications, efficient multicasting over the internet is taking the center stage. For this back drop, the review of some multicast algorithms over wireless network becomes compulsory with the aim of addressing some of the challenges encountered and seeing the possibilities of implementing these algorithms in real time situations. In this paper, we have reviewed some multicast algorithms developed based on network coding based multicast with the view of recognizing some of their strengths and weakness in order to open wide areas for future research and applications.

Keywords: Network Coding, Multicast Algorithm, Multicasting, Wireless Networks, Performance Metrics


1. Introduction

Multicast application over wireless networks has become an area of intensive research as messages are simultaneously delivered within the multicast group. It finds applications in multi-media applications such as video conferencing, audio conferencing, Internet Protocol Television (IPTV), and group communication in social networks which also include online shopping, online gaming system, electronic learning and so on [1]. However, the erroneous nature of noise within the channels such as high packet loss rate, packet delay, rejection, congestion, interference e.t.c of wireless channels make wireless multicast very challenging. All this impairments are critical and they necessitate the design of reliable wireless multicast techniques.

Many techniques have been proposed in the literature to battle these impairments over wireless multicast networks, example, Network Coding [2,3], retransmissions, error-correcting codes and cooperation among terminals [4]. Most multicast problems are NP-complete and various heuristics algorithms have been proposed aimed at achieving smooth data transmission over wireless networks [5-11].

The aim of this paper is to review some few algorithms that apply network coding technique with a view of highlighting some of the problems addressed, their limitations and contribution to the existing body of knowledge.

We consider the basic introduction in section 1. Section 2 explains network coding and the techniques involved and a review of related works are presented in section 3. Finally, Section 4 concludes the paper.

2. Network Coding Technique

Figure 1. Network Coding Based Multicast (Ajibesin, et. al., 2013).

The idea of network coding has its origin in the work of [2]. It is a technique that allows nodes to perform arbitrary operations on packets received and generate new output packets. It offers many advantages such as achieving maximum-flow minimum-cut bound on the multicast capacity, maximizing throughput and ensuring security of message exchange.

It maximizes throughput by sending more packets within a limited period of time as compared to other network such as MANET and Ad-hoc. There are two types of network coding techniques available in literatures [12].

     i.        Random Linear network coding (RLNC): RLNC is implemented by combining packet with independent, random and non-zero coefficient. Finite amount of information is generated at the source and multicast to other nodes on the network and every node can pass on any of its received data to other nodes. At each non-source node which serves as a sink, the complete information generated at the source is recovered. Linear network coding is aimed at how fast each sink node can receive the complete information and how a node can assist its neighbor by sending a coded packet including packets of its own and its neighbor [13].

   ii.        Opportunistic network coding [14]: In ONC, packets are code at different session and each node uses knowledge of what its neighbors have overheard such that each encoded packet can be decoded immediately at the next stage [15]. Packets combinations are selected according to the received and lost packet state of each link where nodes often opportunistically overhear packets that are not designated to them [16].

3. Review of Some Multicast Algorithm

In reference [10], Minimum cost of multicast over coded packet networks has been presented for the first time. They provided an overview of minimizing the total cost of energy consumption for multicast packets in both wired and wireless networks. It was shown that the solution of this problem can be disintegrated into two parts: the first part is finding the minimum cost subgraph, and the second part is determining a code to use over the optimal subgraph. To solve the first part of the problem, they proposed a linear optimization formulation and presented a distributed algorithm using the dual subgradient method to obtain an optimal subgraph. A distributed solution for the second part was provided in [17]. They achieved reduction in the problem of multicast programming. However, some of their limitations were the stability of their decentralized algorithm under changing conditions and exploring a specific approximation method for use in the formulation of dynamic multicast.

In the same vein reference [18] considered the problem of finding a minimum cost multicast subgraph based on network coding, where delay values associated with each link is the only performance metrics taken into consideration, inadequate buffer-size of intermediate nodes and link capacity variations were taken into account. The decentralized algorithm proposed uses an auxiliary time-expanded network.

Reference [19] worked on a single source minimum cost problem which was framed as a convex optimization problem with the use of network coding and convex increasing edge cost. The cost for the scenario where each of the multicast receivers routed its flows was critically examined. They constructed a selfish flow steering algorithms for each receiver and the edge cost at each edge was allocated. However, encoding /sending of packet to different sink were restricted because the algorithm was constructed at each receiver.

Reference [9] studied minimum cost optimization problem during multicast over wireless networks. The research focused on an information model that differentiated intermediate nodes in a multicast network with network coding, routing or replicating of nodes. They developed a means of solving the minimum energy cost multicast problem in wireless networks by optimizing transmission energy, the number of network coding nodes as node classification and the number of packets undergoing network coding. The simulations results showed that the proposed method was good at achieving a minimum cost but very complicated for many multimedia applications.

Reference [20] used genetic algorithm to minimize coding nodes in wireless networks by considering single source and single destination. They proved that Network coding with genetic algorithm improved the throughput for wired and wireless network. The simulation results also showed that the average end to end delay of the network after minimizing coding nodes was less than the normal network. However, there was complexity of packets management and increased delay for the coding nodes.

Reference [21] studied congestion control for Multicast Flows with network coding. The problem was formulated as an optimization based model for network resource allocation base on two sets of decentralized controllers as source and intermediate nodes for congestion control. They presented two models for congestion control, one for networks with given coding sub-graphs and the other sub-graphs are found dynamically. The aim of the research was to carry out congestion control by adjusting the flow rate on each tree. Each source node adjusts its sending rate according to the local congestion price to avoid communication overhead for congestion control within the network. However, the stability of their controller under propagation delay was a great challenge.

Also reference [22] studied the performance of multicast algorithms over coded packet wireless network by using Network Coding Algorithm (NCA) and Multicast Incremental Power Algorithm (MIPA). They were particularly interested in showing the performance of network coding on multicast network when the network arcs were weighted. The result showed that network coding based-algorithm out-performed multicast incremental power algorithm in terms of bandwidth utilization. However, the NCA was developed using linear programming framework and they considered only packet delay as a performance metric that affected multicast (constraint) where as there are other performance metrics that are equally important.

In the same manner reference [23]worked on cost-efficient multicast over coded packet wireless networks using Data Envelopment Analysis (DEA) by first demonstrating the fundamental differences between Network Coding Algorithm (NCA) and Multicast Incremental Power algorithm (MIPA). The (DEA) is operational research tool widely used to determine the effectiveness and efficiency of any organizations or algorithms in terms of cost, performance and service delivery. It consists of entities called the Decision making units (DMUs) for evaluating the performances of the two algorithms. This was followed by the analysis of the statistical mean of the multicast cost to determine the cost-effectiveness and cost-efficiency of the two algorithms. Their findings showed that NCA outperformed MIPA for both cost-effective and cost-efficient multicast.

Reference [24] studied the convergence of decentralized min-cost subgraph algorithm for multicast in coded networks. They developed an algorithm that generates a feasible solution after each iteration to take care of the dual subgradient method proposed by [10]. They completely decentralized the system as there is no iteration between the nodes and each node only knows the cost of its incoming and outgoing links. However, the algorithm did not take care of interference within the wireless network and hence the need to extend the algorithm to interference-limited wireless network is a great step toward achieving efficient result.

Reference [25] studied the problem of data exchange which is a problem of reconciling multiple users having parts of its data while minimizing the cost in terms of the total number of bits exchange. This is one area in which multicast finds applications (peer- to- peer file sharing). They used deterministic polynomial time algorithm which find an optimal communication scheme in such a way that the communication cost is minimized. The whole problem was further simplified by proposing a simple randomized algorithm motivated by the deterministic algorithm which is based on random network coding scheme. But it cannot be applicable to larger users within the network.

Reference [7] Proposed a path based power efficient approach that minimizes energy consumption by optimizing the transmission ranges of all nodes using langrangain relaxation approach. They investigated the problem of energy efficient multicasting in wireless network with a view of minimizing the total energy consumption for multicast messages in static wireless network. A decentralized algorithm was developed to solve the problem and the result was compared with three different heuristics algorithms namely, Minimum Shortest Path Tree (MSPT) algorithm, Prim’s Minimum Spanning Tree (PMST) algorithm and Broadcast Incremental Power (BIP) algorithm. The proposed model outperformed all the three algorithms by 30%, 10% and 5% respectively. However, the developed algorithm was only compared in terms of energy efficiency.

Reference [26] studied secure multicasting using symmetric algorithm where the sender and the receivers uses the same key for encryption and decryption of the data exchange. Before the data is to be transmitted, it is converted into cyphers text generated with the help of a key. The aim was to secure and provide much needed security for all data exchange within the multicast group. The proposed algorithm was compared with three encryption algorithms, DES (Data encryption standard), 3DES (Triple DES) and AES. The proposed algorithm performs better in terms of security against unauthorized attack and speed. But, the proposed algorithms was only compared to symmetric algorithms whereas there other asymmetric algorithms or cryptographic scheme that can be compared.

Lastly, reference [27] improved the performance of Network Coding Algorithm by considering more performance metrics. As more metrics such as delay, loss and rejection of packet are collectively considered, the cost of bandwidth decreases. Their work depends largely on Shannon Hartley channel capacity theorem. Simulation result showed that the cost of bandwidth decreases as more performance metrics are considered. Similarly, the cost of bandwidth presented under estimated the channel. However, not all the performance metrics that affect multicast are considered.

4. Conclusion

So far the review of some few multicast algorithms over wireless networks using network coding techniques has been studied. The literatures reviewed addressed most of the performance metrics such as throughput, delay, loss, rejection and congestion of packets during multicast which is a great limitation toward achieving efficient multicast. Very often, algorithms were developed to minimize the cost (bandwidth reduction or energy consumption) of multicast.


References

  1. S. Lakshminarayana and A. Eryilmaz, "Multirate multicasting with intralayer network coding," IEEE/ACM Transactions on Networking (TON), vol. 21, pp. 1256-1269, 2013.
  2. R. Ahlswede, N. Cai, S. Y. R. Li, and , and R. W. Yeung, "Network information flow. Information Theory," Theory, IEEE Transactions on, vol. 46, pp. 1204-1216, 2000.
  3. C. Fragouli, J. Widmer, and J.-Y. Le Boudec, "A network coding approach to energy efficient broadcasting: from theory to practice," 2005.
  4. B. Niu, H. Jiang, and H. V. Zhao, "A cooperative multicast strategy in wireless networks," Vehicular Technology, IEEE Transactions on, vol. 59, pp. 3136-3143, 2010.
  5. P. Sanders, S. Egner, and L. Tolhuizen, "Polynomial time algorithms for network information flow," in Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, 2003, pp. 286-294.
  6. L. Tan, H. Tang, Z. Zhang, and K. Hu, "An Energy-Efficient Clustering algorithm Based on Cross-Monotonic Cost Sharing Game," 2012.
  7. Y.-F. Wen and W. Liao, "Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach," Wireless Networks, vol. 17, pp. 1401-1421, 2010.
  8. Y. Xi and E. M. Yeh, "Distributed algorithms for minimum cost multicast with network coding in wireless networks," in Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006 4th International Symposium on, 2006, pp. 1-9.
  9. Y. Xi and E. M. Yeh, "Distributed algorithms for minimum cost multicast with network coding," Networking, IEEE/ACM Transactions on, vol. 18, pp. 379-392, 2010.
  10. D. S. Lun, N. Ratnakar, M. Médard, R. Koetter, D. R. Karger, T. Ho, et al., "Minimum-cost multicast over coded packet networks," Information Theory, IEEE Transactions on, vol. 52, pp. 2608-2623, 2006.
  11. G. Tan, X. Ni, X. Liu, C. Qu, and L. Tang, "Real-time multicast with network coding in mobile ad-hoc networks," Intelligent Automation & Soft Computing, vol. 18, pp. 783-794, 2012.
  12. S. Y. Li, Q. T. Sun, and Z. Shao, "Linear network coding: Theory and algorithms," Proceedings of the IEEE, vol. 99, pp. 372-387, 2011.
  13. L. Ma, Z. Lin, Z. Zhang, G. Mao, and B. Vucetic, "Improving reliability in lossy wireless networks using network coding," in Communications Workshops (ICC), 2013 IEEE International Conference on, 2013, pp. 312-316.
  14. Y. Shin, M. Choi, J. Koo, and S. Choi, "Video multicast over WLANs: Power saving and reliability perspectives," Network, IEEE, vol. 27, pp. 40-46, 2013.
  15. T. Cui, L. Chen, and T. Ho, "Energy efficient opportunistic network coding for wireless networks," in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008.
  16. W. Chen, K. B. Letaief, and Z. Cao, "Opportunistic network coding for wireless networks," in Communications, 2007. ICC'07. IEEE International Conference on, 2007, pp. 4634-4639.
  17. T. K. Ho, R. Medard, M. Effros, and a. K. M. Shi, J., "A random linear network coding approach to multicast. ," IEEE Trans. On Inform. Theory, vol. 52, 2006.
  18. H. Ghasvari, M. A. Raayatpanah, B. Khalaj, and H. Bakhshi, "Optimal subgraph Selection over Coded Networks with Delay and Limited-Size Buffering," IETCommunications Surveys & Tutorials, IEEE,vol. 5, pp. 1497-1505, 2011.
  19. S. Bhadra, S. Shakkottai, and P. Gupta, "Min-cost selfish multicast with network coding," Information Theory, IEEE Transactions on, vol. 52, pp. 5077-5087, 2006.
  20. E. S. Tan, Z. W. Siew, K. Y. Chin, K. C. S. Lye, and K. T. K. Teo, "Minimizing network coding Nodes in Multicast Tree construction via Genetic Algorithm," Computer society, 2012.
  21. L. Chen, T. Ho, M. Chiang, S. H. Low, and J. C. Doyle, "Congestion control for multicast flows with network coding," Information Theory, IEEE Transactions on, vol. 58, pp. 5908-5921, 2012.
  22. A. A. Ajibesin, N. Ventura, H. A. Chan, A. Murgu, and O. K. Egunsola, "Performance of Multicast Algorithms Over Coded Packet Wireless Networks," in Computer Modelling and Simulation (UKSim), 2012 UKSim 14th International Conference on, 2012, pp. 596-600.
  23. A. A. Ajibesin, N. Ventura, A. Murgu, and H. A. Chan, "Cost-efficient multicast over coded packet wireless networks using data envelopment analysis," in Consumer Communications and Networking Conference (CCNC), 2013 IEEE, 2013, pp. 546-551.
  24. F. Zhao, M. Médard, A. Ozdaglar, and D. Lun, "Convergence Study of Decentralized Min-Cost Subgraph Algorithms for Multicast in Coded Networks," Information Theory, IEEE Transactions on, vol. 60, pp. 410-421, 2014.
  25. N. Milosavljevic, S. Pawar, S. E. Rouayheb, M. Gastpar, and K. Ramchandran, "Efficient Algorithms for the Data Exchange Problem," arXiv preprint arXiv:1502.06149, 2015.
  26. V. Jose, C. Divya, and M. P. Scholar, "Secure Multicasting using Blowfish Algorithm," International Journal of Advanced Information and Communication Technology, ISSN, pp. 2348-9928, 2014.
  27. S. J. Soja, S. Muhammed Sani, A. M. S Tekanyi, and S. Garba, "Improvement of Multicast Network Coding Algorithm for Bandwidth Utilization over Coded Packet Wireless Network," vol. Unpublished Thesis, pp. 1-6, 2015.

Article Tools
  Abstract
  PDF(314K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931