Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks

Feng WEI; Wei-xia ZOU

doi:10.1631/FITEE.1700020

Your Location：

Home >

Browse articles >

Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks

Regular Papers | Updated：2022-05-19

- Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks
- 5G最小代价多播网络中的次优编码子图算法
- Frontiers of Information Technology & Electronic Engineering Vol. 19, Issue 5, Pages: 662-673(2018)
- Affiliations：
  
  MOE Key Lab of Universal Wireless Communications, Beijing University of Posts and Telecommunications, Beijing 100876, China
  State Key Lab of Millimeter Waves, Southeast University, Nanjing 210096, China
- Author bio：
  
  Feng WEI, E-mail: weifeng_luck@163.com
- Funds：
- DOI：10.1631/FITEE.1700020
  CLC： TN92
- Received：08 January 2017，
  
  Revised：2018-;5-10，
  
  Published：2018-05
- Accepted：
Scan QR Code
Feng WEI, Wei-xia ZOU. Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(5): 662-673.
DOI：

Feng WEI, Wei-xia ZOU. Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(5): 662-673. DOI： 10.1631/FITEE.1700020.

摘要

为降低具有控制-数据分离架构的5G网络中多播的传输代价，本文关注无线网络中两多播共存时的功率代价最小网络编码子图形成问题。提出两个基于Steiner树的扩展次优算法：当两个具有相同吞吐量的多播组共存时，C1CPE算法通过复用拓扑中已经占用链路的方式寻找可行的最小代价方案，并采用节点涂色的方式保证网络编码方案可解码。另外，针对两多播组的源点和目的点相同的特殊情况，在C1CPE算法基础上提出E-SCTF算法。此算法精简了涂色方案，通过理论分析可知此算法复杂度比C1CPE算法低。仿真结果表明，两个算法在功率代价上都有良好表现，在密集部署下性能仍可进一步提升。

Abstract

To reduce the transmission cost in 5G multicast networks that have separate control and data planes

we focus on the minimum-power-cost network-coding subgraph problem for the coexistence of two multicasts in wireless networks. We propose two suboptimal algorithms as extensions of the Steiner tree multicast. The critical 1-cut path eliminating (C1CPE) algorithm attempts to find the minimum-cost solution for the coexistence of two multicast trees with the same throughput by reusing the links in the topology

and keeps the solution decodable by a coloring process. For the special case in which the two multicast trees share the same source and destinations

we propose the extended selective closest terminal first (E-SCTF) algorithm out of the C1CPE algorithm. Theoretically the complexity of the E-SCTF algorithm is lower than that of the C1CPE algorithm. Simulation results show that both algorithms have superior performance in terms of power cost and that the advantage is more evident in networks with ultra-densification.

关键词

Keywords

references

PK Agyapong , , , M Iwamura , , , D Staehle , , , 等 . . Design considerations for a 5G network architecture . . IEEE Commun Mag , , 2014 . . 52 ( ( 11 ): ): 65 - - 75 . . DOI: 10.1109/MCOM.2014.6957145 http://doi.org/10.1109/MCOM.2014.6957145 . .

IF Akyildiz , , , S Nie , , , SC Lin , , , 等 . . 5G roadmap: 10 key enabling technologies . . Comput Netw , , 2016 . . 106 17 - - 48 . . DOI: 10.1016/j.comnet.2016.06.010 http://doi.org/10.1016/j.comnet.2016.06.010 . .

E Ali , , , M Ismail , , , R Nordin , , , 等 . . Beamforming techniques for massive MIMO systems in 5G: overview, classification, and trends for future research . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 6 ): ): 753 - - 772 . . DOI: 10.1631/FITEE.1601817 http://doi.org/10.1631/FITEE.1601817 . .

JG Andrews , , , S Buzzi , , , W Choi , , , 等 . . What will 5G be . . IEEE J Sel Areas Commun , , 2014 . . 32 ( ( 6 ): ): 1065 - - 1082 . . DOI: 10.1109/JSAC.2014.2328098 http://doi.org/10.1109/JSAC.2014.2328098 . .

R Baldemair , , , T Irnich , , , K Balachandran , , , 等 . . Ultra- dense networks in millimeter-wave frequencies . . IEEE Commun Mag , , 2015 . . 53 ( ( 1 ): ): 202 - - 208 . . DOI: 10.1109/MCOM.2015.7010535 http://doi.org/10.1109/MCOM.2015.7010535 . .

SZ Chen , , , SL Kang . . A tutorial on 5G and the progress in China . . Front Inform Technol Electron Eng , , 2018 . . 19 ( ( 3 ): ): 309 - - 321 . . DOI: 10.1631/FITEE.1800070 http://doi.org/10.1631/FITEE.1800070 . .

SZ Chen , , , F Qin , , , B Hu , , , 等 . . User-centric ultra-dense networks for 5G: challenges, methodologies, and directions . . IEEE Wirel Commun , , 2016 . . 23 ( ( 2 ): ): 78 - - 85 . . DOI: 10.1109/MWC.2016.7462488 http://doi.org/10.1109/MWC.2016.7462488 . .

M Chiang , , , SH Low , , , AR Calderbank , , , 等 . . Layering as optimization decomposition: a mathematical theory of network architectures . . Proc IEEE , , 2007 . . 95 ( ( 1 ): ): 255 - - 312 . . DOI: 10.1109/JPROC.2006.887322 http://doi.org/10.1109/JPROC.2006.887322 . .

J Choi . . Iterative methods for physical-layer multicast beamforming . . IEEE Trans Wirel Commun , , 2015 . . 14 ( ( 9 ): ): 5185 - - 5196 . . DOI: 10.1109/TWC.2015.2434374 http://doi.org/10.1109/TWC.2015.2434374 . .

SW He , , , YM Huang , , , HM Wang , , , 等 . . Leakage-aware energy-efficient beamforming for heterogeneous multicell multiuser systems . . IEEE J Sel Areas Commun , , 2014 . . 32 ( ( 6 ): ): 1268 - - 1281 . . DOI: 10.1109/JSAC.2014.2328142 http://doi.org/10.1109/JSAC.2014.2328142 . .

M Heindlmaier , , , DS Lun , , , D Traskov , , , 等 . . Wireless inter-session network coding—an approach using virtual multicasts . . IEEE Int Conf on Communications , , 2011 . . p.1 - - 5 . . DOI: 10.1109/icc.2011.5963472 http://doi.org/10.1109/icc.2011.5963472 . .

T Ho , , , M Medard , , , R Koetter , , , 等 . . A random linear network coding approach to multicast . . IEEE Trans Inform Theory , , 2006 . . 52 ( ( 10 ): ): 4413 - - 4430 . . DOI: 10.1109/TIT.2006.881746 http://doi.org/10.1109/TIT.2006.881746 . .

DD Jiang , , , ZZ Xu , , , WP Li , , , 等 . . Network coding-based energy-efficient multicast routing algorithm for multi-hop wireless networks . . J Syst Softw , , 2015 . . 104 152 - - 165 . . DOI: 10.1016/j.jss.2015.03.006 http://doi.org/10.1016/j.jss.2015.03.006 . .

V Kotronis , , , X Dimitropoulos , , , B Ager . . Outsourcing the routing control logic: better Internet routing based on SDN principles . . Proc 11 th ACM Workshop on Hot Topics in Networks , , 2012 . . p.55 - - 60 . . DOI: 10.1145/2390231.2390241 http://doi.org/10.1145/2390231.2390241 . .

MN Kulkarni , , , A Ghosh , , , JG Andrews . . A comparison of MIMO techniques in downlink millimeter wave cellular networks with hybrid beamforming . . IEEE Trans Commun , , 2016 . . 64 ( ( 5 ): ): 1952 - - 1967 . . DOI: 10.1109/TCOMM.2016.2542825 http://doi.org/10.1109/TCOMM.2016.2542825 . .

JZ Li , , , B Ai , , , RS He , , , 等 . . Indoor massive multiple-input multiple-output channel characterization and performance evaluation . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 6 ): ): 773 - - 787 . . DOI: 10.1631/FITEE.1700021 http://doi.org/10.1631/FITEE.1700021 . .

SY Li , , , W Sun , , , CC Hua . . Optimal resource allocation for heterogeneous traffic in multipath networks . . Int J Commun Syst , , 2016 . . 29 ( ( 1 ): ): 84 - - 98 . . DOI: 10.1002/dac.2800 http://doi.org/10.1002/dac.2800 . .

DS Lun , , , N Ratnakar , , , R Koetter , , , 等 . . Achieving minimum-cost multicast: a decentralized approach based on network coding . . Proc IEEE 24 th Annual Joint Conf of IEEE Computer and Communications Societies , , 2005 . . p.1607 - - 1617 . . DOI: 10.1109/INFCOM.2005.1498443 http://doi.org/10.1109/INFCOM.2005.1498443 . .

Z Ma , , , ZQ Zhang , , , ZG Ding , , , 等 . . Key techniques for 5G wireless communications: network architecture, physical layer, and MAC layer perspectives . . Sci China Inform Sci , , 2015 . . 58 ( ( 4 ): ): 1 - - 20 . . DOI: 10.1007/s11432-015-5293-y http://doi.org/10.1007/s11432-015-5293-y . .

K Rajawat , , , N Gatsis , , , GB Giannakis . . Cross-layer designs in coded wireless fading networks with multicast . . IEEE/ACM Trans Netw , , 2011 . . 19 ( ( 5 ): ): 1276 - - 1289 . . DOI: 10.1109/TNET.2011.2109010 http://doi.org/10.1109/TNET.2011.2109010 . .

S Ramanathan . . Multicast tree generation in networks with asymmetric links . . IEEE/ACM Trans Netw , , 1996 . . 4 ( ( 4 ): ): 558 - - 568 . . DOI: 10.1109/90.532865 http://doi.org/10.1109/90.532865 . .

TS Rappaport , , , JN Murdock , , , F Gutierrez . . State of the art in 60-GHz integrated circuits and systems for wireless communications . . Proc IEEE , , 2011 . . 99 ( ( 8 ): ): 1390 - - 1436 . . DOI: 10.1109/JPROC.2011.2143650 http://doi.org/10.1109/JPROC.2011.2143650 . .

TS Rappaport , , , S Sun , , , R Mayzus , , , 等 . . Millimeter wave mobile communications for 5G cellular: it will work . . IEEE Access , , 2013 . . 1 335 - - 349 . . DOI: 10.1109/ACCESS.2013.2260813 http://doi.org/10.1109/ACCESS.2013.2260813 . .

A Ribeiro , , , G B Giannakis . . Separation principles in wireless networking . . IEEE Trans Inform Theory , , 2010 . . 56 ( ( 9 ): ): 4488 - - 4505 . . DOI: 10.1109/TIT.2010.2053897 http://doi.org/10.1109/TIT.2010.2053897 . .

M Riemensberger , , , W Utschick . . A polymatroid flow model for network coded multicast in wireless networks . . IEEE Trans Inform Theory , , 2014 . . 60 ( ( 1 ): ): 443 - - 460 . . DOI: 10.1109/TIT.2013.2287498 http://doi.org/10.1109/TIT.2013.2287498 . .

F Rusek , , , D Persson , , , BK Lau , , , 等 . . Scaling up MIMO: opportunities and challenges with very large arrays . . IEEE Signal Process Mag , , 2013 . . 30 ( ( 1 ): ): 40 - - 60 . . DOI: 10.1109/MSP.2011.2178495 http://doi.org/10.1109/MSP.2011.2178495 . .

H Shokri-Ghadikolaei , , , C Fischione . . The transitional behavior of interference in millimeter wave networks and its impact on medium access control . . IEEE Trans Commun , , 2016 . . 64 ( ( 2 ): ): 723 - - 740 . . DOI: 10.1109/TCOMM.2015.2509073 http://doi.org/10.1109/TCOMM.2015.2509073 . .

E Stai , , , M Loulakis , , , S Papavassiliou . . Cross-layer design of wireless multihop networks over stochastic channels with time-varying statistics . . IEEE Trans Wirel Commun , , 2015 . . 14 ( ( 12 ): ): 6967 - - 6980 . . DOI: 10.1109/TWC.2015.2462845 http://doi.org/10.1109/TWC.2015.2462845 . .

LY Su , , , CY Yang , , , I Chih-Lin . . Energy and spectral efficient frequency reuse of ultra dense networks . . IEEE Trans Wirel Commun , , 2016 . . 15 ( ( 8 ): ): 5384 - - 5398 . . DOI: 10.1109/TWC.2016.2557790 http://doi.org/10.1109/TWC.2016.2557790 . .

D Szabó , , , F Németh , , , B Sonkoly , , , 等 . . Towards the 5G revolution: a software defined network architecture exploiting network coding as a service . . Proc ACM Conf on Special Interest Group on Data Communication , , 2015 . . p.105 - - 106 . . . .

C Wang , , , ST Guo , , , YY Yang , , , 等 . . An optimization framework for mobile data collection in energy- harvesting wireless sensor networks . . IEEE Trans Mobile Comput , , 2016 . . 15 ( ( 12 ): ): 2969 - - 2986 . . DOI: 10.1109/TMC.2016.2533390 http://doi.org/10.1109/TMC.2016.2533390 . .

CC Wang , , , NB Shroff . . Pairwise intersession network coding on directed networks . . IEEE Trans Inform Theory , , 2010 . . 56 ( ( 8 ): ): 3879 - - 3900 . . DOI: 10.1109/TIT.2010.2050932 http://doi.org/10.1109/TIT.2010.2050932 . .

J Wang , , , Y Li , , , XM Wang . . Network coding based multicast in Internet . . Int Conf on Parallel Processing Workshops , , 2007 . . p.44 DOI: 10.1109/ICPPW.2007.58 http://doi.org/10.1109/ICPPW.2007.58 . .

F Wei , , , WX Zou . . Steiner-tree-based 2-cut-set network coding subgraph algorithm in wireless multicast network . . Proc Int Conf in Communications, Signal Processing, and Systems , , 2017 . . p.373 - - 381 . . DOI: 10.1007/978-981-10-3229-5_40 http://doi.org/10.1007/978-981-10-3229-5_40 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Indoor massive multiple-input multiple-output channel characterization and performance evaluation

Related Author

Jian-zhi LI

Bo AI

Rui-si HE

Qi WANG

Mi YANG

Bei ZHANG

Ke GUAN

Dan-ping HE

Related Institution

State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University

Engineering University of Armed Police Force, Telecommunication Engineering Department

Key Laboratory of Wireless Sensor Network and Communication, Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences

ZTE Corporation

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰