›› 2013, Vol. 28 ›› Issue (2): 343-356.doi: 10.1007/s11390-013-1335-3

• Computer Network • Previous Articles     Next Articles

Optimal Relay Assignment and Power Allocation for Cooperative Communications

Kun Xie1 (谢鲲), Member, CCF, Jian-Nong Cao2 (曹建农), Senior Member, CCF, IEEE, Member, ACM and Ji-Gang Wen3 (文吉刚)   

  1. 1 School of Information Science and Engineering, Hunan University, Changsha 410082, China;
    2 Department of Computing, Hong Kong Polytechnic University, Kowloon, Hong Kong, China;
    3 Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2012-01-15 Revised:2012-07-12 Online:2013-03-05 Published:2013-03-05
  • Supported by:

    The work is supported by the National Basic Research 973 Program of China under Grant No. 2012CB315801, the National Natural Science Foundation of China under Grant Nos. 61133015, 61003305, 61173167, and the Ph.D. Programs Foundation of Ministry of Education of China under Grant No. 20100161120022.

Cooperative communication for wireless networks has gained a lot of recent interest due to its ability to mitigate fading with exploration of spatial diversity. In this paper, we study a joint optimization problem of jointly considering transmission mode selection, relay assignment and power allocation to maximize the capacity of the network through cooperative wireless communications. This problem is much more challenging than relay assignment considered in literature work which simply targets to maximize the transmission capacity for a single transmission pair. We formulate the problem as a variation of the maximum weight matching problem where the weight is a function over power values which must meet power constraints (VMWMC). Although VMWMC is a non-convex problem whose complexity increases exponentially with the number of relay nodes, we show that the duality gap of VMWMC is virtual zero. Based on this result, we propose a solution using Lagrange dual decomposition to reduce the computation complexity. We do simulations to evaluate the performance of the proposed solution. The results show that our solution can achieve maximum network capacity with much less computation time compared with exhaustive search, and our solution outperforms existing sub-optimal solutions that can only achieve much lower network capacity.

[1] Bletsas A, Khisti A, Reed D P, Lippman A. A simple coope-rative diversity method based on network path selection.IEEE Journal on Selected Areas in Communications, 2006,24(3): 659-672.

[2] Bletsas A, Shin H, Win M Z. Outage optimality of oppor-tunistic amplify-and-forward relaying. IEEE Communica-tions Letters, 2007, 11(3): 261-263.

[3] Ibrahim A S, Sadek A K, Su W, Liu K J R. Cooperativecommunications with relay-selection: When to cooperate andwhom to cooperate with. IEEE Transactions on WirelessCommunications, 2008, 7(7): 2814-2827.

[4] Zhao Y, Adve R, Lim T J. Improving amplify-and-forwardrelay networks: Optimal power allocation versus selection.IEEE Transactions on Wireless Communications, 2007, 6(8):3114-3123.

[5] Ikki S S, Ahmed M H. Performance of multiple-relay coope-rative diversity systems with best relay selection over rayleighfading channels. EURASIP J. Adv. Signal Process, 2008: 1-7.

[6] HasnaMO, AlouiniMS. Optimal power allocation for relayedtransmissions over rayleigh-fading channels. IEEE Transac-tions on Wireless Communications, 2004, 3(6): 1999-2004.

[7] Host-Madsen A, Zhang J. Capacity bounds and power allo-cation for wireless relay channels. IEEE Transactions on In-formation Theory, 2005, 51(6): 2020-2040.

[8] Lee K, Yener A. Iterative power allocation algorithmsfor amplify/estimate/compress-and-forward multi-band relaychannels. In Proc. the 40th Annual Conference on Informa-tion Sciences and Systems, March 2006, pp.1318-1323.

[9] Wang B, Han Z, Liu K J R. Distributed relay selection andpower control for multiuser cooperative communication net-works using buyer/seller game. In Proc. the 26th INFOCOM2007, May 2007, pp.544-552.

[10] Simic L, Berber S M, Sowerby K W. Partner choice and powerallocation for energy efficient cooperation in wireless sensornetworks. In Proc. ICC 2008, May 2008, pp.4255-4260.

[11] Zhou Z, Zhou S L, Cui J H, Cui S G. Energy-efficient coope-rative communication based on power control and selectivesingle-relay in wireless sensor networks. IEEE Transactionson Wireless Communications, 2008, 7(8): 3066-3078.

[12] Li Y F, Wang P, D N, Zhuang W. A dynamic relay selectionscheme for mobile users in wireless relay networks. In Proc.INFOCOM 2011, April 2011, pp.256-260.

[13] Shi Y, Sharma S, Hou Y T, Kompella S. Optimal relay as-signment for cooperative communications. In Proc. the 9thMobiHoc, May 2008, pp.3-12

[14] Sharma S, Shi Y, Hou Y T, Kompella S. An optimal algo-rithm for relay node assignment in cooperative ad hoc net-works. Transactions on Networking, 2011, 19: 879-892.

[15] Zhang P, Xu Z G, Wang F R, Xie X, Tu L. A relay assign-ment algorithm with interference mitigation for cooperativecommunication. In Proc. WCNC 2009, April 2009, pp.1286-1291.

[16] Yang D J, Fang X, Xue G L. OPRA: Optimal relay assign-ment for capacity maximization in cooperative networks. InProc. ICC 2011, June 2011, pp.1-6.

[17] Yang D J, Xi F, Xue G L. HERA: An optimal relay assignmentscheme for cooperative networks. IEEE Journal on SelectedAreas in Communications, 2012, 30(2): 245-253.

[18] Xu H L, Huang L S, Wang G, Xu T, Liu G. Joint relay assign-ment and power allocation for cooperative communications.Wireless Networks, 2010, 16(8): 2209-2219.

[19] Cai J, Shen X M, Mark J W, Alfa A S. Semi-distributeduser relaying algorithm for amplify-and-forward wireless relaynetworks. IEEE Transactions on Wireless Communications,2008, 7(4): 1348-1357.

[20] Ng T C Y, Yu W. Joint optimization of relay strategies andresource allocations in cooperative cellular networks. IEEEJournal on Selected Areas in Communications, 2007, 25(2):328-339.

[21] Kadloor S, Adve R. Relay selection and power allocation incooperative cellular networks. IEEE Transactions on Wire-less Communications, 2010, 9(5): 1676-1685.

[22] Ma K, Liu Z X, Guan X P. Joint relay selection and power al-location for cooperative cellular networks. Wireless PersonalCommunications, 2012, 64(2): 305-321.

[23] Phan K T, Nguyen D H N, Le-Ngoc T. Joint power allocationand relay selection in cooperative networks. In Proc. the 28thGLOBECOM, November 2009, pp.1-5.

[24] Xu H L, Huang L S, Wang G, Liu G, Huang H. Joint powerallocation and relay assignment for max-min fairness in coope-rative networks. In Proc. 2010 IEEE Symposium on Com-puters and Communications, June 2010, pp.123-126.

[25] Laneman J N, Tse D N C, Wornell G W. Cooperative di-versity in wireless networks: Efficient protocols and outagebehavior. IEEE Transactions on Information Theory, 2004,50(12): 3062-3080.

[26] Kao M Y, Lam T W, Sung W K, Ting H F. A decompositiontheorem for maximum weight bipartite matchings. SIAM J.Computing, 2001, 31(1): 18-26.

[27] Palomar D P, Chiang M. A tutorial on decomposition meth-ods for network utility maximization. IEEE Journal on Se-lected Areas in Communications, 2006, 24(8): 1439-1451.

[28] Chiang M, Zhang S, Hande P. Distributed rate allocation forinelastic 皁ws: Optimization frameworks, optimality condi-tions, and optimal algorithms. In Proc. INFOCOM 2005,March 2005, pp.2679-2690.

[29] Wei Y, Lui R. Dual methods for nonconvex spectrum op-timization of multicarrier systems. IEEE Transactions onCommunications, 2006, 54(7): 1310-1322.

[30] Seong K, Mohseni M, Cioffi J M. Optimal resource alloca-tion for OFDMA downlink systems. In Proc. 2006 IEEEInternational Symposium on Information Theory, July 2006,pp.1394-1398.

[31] Kuhn H W. The Hungarian method for the assignment prob-lem. Naval Research Logistics Quarterly, 1955, 2(1/2): 83-97.

[32] Munkres J. Algorithms for the assignment and transportationproblems. Journal of the Society for Industrial and AppliedMathematics, 1957, 5(1): 32-38.

[33] Yu W, Cioffi J M. Sum capacity of Gaussian vector broadcastchannels. IEEE Transactions on Information Theory, 2004,50(9): 1875-1892.
No related articles found!
Full text



[1] Peter M. Haverty, Zhi-Ping Weng, and Ulla Hansen. Transcriptional Regulatory Networks Activated by PI3K and ERK Transduced Growth Signals in Human Glioblastoma Cells[J]. , 2005, 20(4): 439 -445 .
[2] Xue-Jun Yang, Yong Dou, and Qing-Feng Hu. Progress and Challenges in High Performance Computer Technology[J]. , 2006, 21(5): 674 -681 .
[3] Wei Wang, Ming Liu, and Andrew Hsu. Hybrid Nanoelectronics: Future of Computer Technology[J]. , 2006, 21(6): 871 -886 .
[4] Jie Wu and Shu-Hui Yang. Small World Model-Based Polylogarithmic Routing Using Mobile Nodes[J]. , 2008, 23(3): 327 -342 .
[5] Amin Nikanjam and Adel Rahmani. Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm[J]. , 2012, 27(5): 1077 -1090 .
[6] Liang-Jun Zang, Cong Cao, Ya-Nan Cao, Yu-Ming Wu, and Cun-Gen Cao. A Survey of Commonsense Knowledge Acquisition[J]. , 2013, 28(4): 689 -719 .
[7] Cun-Chao Tu, Zhi-Yuan Liu, Mao-Song Sun. Tag Correspondence Model for User Tag Suggestion[J]. , 2015, 30(5): 1063 -1072 .
[8] Wen-Min Li, Xue-Lei Li, Qiao-Yan Wen, Shuo Zhang, Hua Zhang. Flexible CP-ABE Based Access Control on Encrypted Data for Mobile Users in Hybrid Cloud System[J]. , 2017, 32(5): 974 -990 .
[9] Tao Xie, Yuanfang Cai, Xuanzhe Liu, Xiaoyin Wang, Mithun P. Acharya, Marcelo d'Amorim, Xiaoxing Ma. Preface[J]. , 2017, 32(6): 1057 -1059 .
[10] Fa-Qiang Sun, Gui-Hai Yan, Xin He, Hua-Wei Li, Yin-He Han. CPicker: Leveraging Performance-Equivalent Configurations to Improve Data Center Energy Efficiency[J]. , 2018, 33(1): 131 -144 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved