Novel Approach to Sub-graph Selection over Coded Wireless Networks with QoS Constraints

ABSTRACT

In this paper, we study the problem of minimum-cost multicast with network coding, while the maximum end-to-end weight, such as delay, throughput, and security, along paths from the source to each destination is bounded by a constant. We propose a path-based mixed integer programming model for the problem and show that the problem is non-deterministic polynomial (NP)-hard. We apply a column-generation approach to solve this model, where the problem is decomposed into a master linear programming problem and several integer programming sub-problems. We also introduce an approach to get a lower bound of optimal solution. Simulation results demonstrate that using of column-generation approach in combination with network coding to solve this problem can enhance the efficiency of final solution, no matter of the size of underlying network.

Keywords:

• Communication networks
• Network coding
• Quality of service
• Column generation

ACKNOWLEDGEMENTS

This work was supported by Iran Telecommunication Research Center (ITRC) and Islamic Azad University Shahre Rey branch.

Additional information

Notes on contributors

Amin Mohajer

Amin Mohajer received the BS degree in electronics and electrical engineering from Shahed University, Tehran, Iran, in 2009. He is working toward the MS degree in electrical and secure communication engineering with Mobile Ad-Hoc Networking Laboratory, School of Information and Communication Technology, Malek Ashtar University of Technology, Tehran, Iran. His areas of research include mobile ad hoc networks, network coding, optical communications, cognitive radio, and cryptography.

Mohammad Yousefvand

Mohammad Yousefvand received his BSc degree in information technology from University of Tabriz, Tabriz, Iran, in 2009. He received his MSc degree in computer engineering from Tehran Polytechnic University, Tehran, Iran, in 2012. He served as a research scholar at Iran Telecommunication Research Center (ITRC), a most prominent research centre in the area of telecommunications and networking in Iran from 2009 to 2012. He is currently a consultant engineer in High Speed Networks (HSN) Lab at Tehran Polytechnic University. His current research interests include spectrum management in cognitive radio networks, QoS assurance in heterogeneous wireless networks and cloud computing environments.

Ehsan Noori Ghalenoo

Ehsan Noori Ghalenoo received the BS degree in electronics and electrical engineering from Islamic Azad University, Karaj, Iran, in 2010. He is working toward the MS degree in electrical engineering – communications systems with School of Information and Communication Technology, Shahre Rey Azad University, Tehran, Iran. His areas of research include wireless networking, mobile ad hoc networks, wireless sensor networks, and cognitive radio.

Parviz Mirzaei

Parviz Mirzaei received the BS degree in electrical engineering communications system from Sattari Aerial University, Tehran, Iran. He is working toward the MS degree in electrical and communication engineering with Mobile Ad-Hoc Networking Laboratory, School of Information and Communication Technology, Shahre Rey University, Tehran, Iran. His areas of research include global system for mobile communications (GSM), mobile ad hoc networks, and digital communications.

Ali Zamani

Ali Zamani received the BS degree in electronics and electrical engineering from Malek Ashtar University, Isfahan, Iran. He is working toward the MS degree in electrical and communications system engineering with Mobile Ad-Hoc Networking Laboratory, School of Information and Communication Technology, Shahre Rey University, Tehran, Iran. His areas of research include Mobile Adhoc NETworks (MANET), GSM, distributed wireless networks, digital communications, and cognitive radio networks.