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

Amin Mohajer, Mohammad Yousefvand, Ehsan Noori Ghalenoo, Parviz Mirzaei, Ali Zamani

IETE Journal of Research · 2014 · 17 citations · 19 references

Concepts

Abstract

ABSTRACTIn 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 networksNetwork codingQuality of serviceColumn generation ACKNOWLEDGEMENTSThis work was supported by Iran Telecommunication Research Center (ITRC) and Islamic Azad University Shahre Rey branch.Additional informationNotes on contributorsAmin MohajerAmin 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. Display full size Mohammad YousefvandMohammad 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. Display full size Ehsan Noori GhalenooEhsan 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. Display full size Parviz MirzaeiParviz 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. Display full size Ali ZamaniAli 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. Display full size

References

19