基于單調(diào)優(yōu)化框架的凸松弛分支定界算法求解非凸多信道聯(lián)合感知問(wèn)題

夏巧橋 田 茂 汪鼎文 陳 曦

?

基于單調(diào)優(yōu)化框架的凸松弛分支定界算法求解非凸多信道聯(lián)合感知問(wèn)題

夏巧橋①田 茂①汪鼎文*②陳 曦②

①(武漢大學(xué)電子信息學(xué)院 武漢 430072)②(武漢大學(xué)微電子與信息技術(shù)研究院 武漢 430072)

認(rèn)知無(wú)線電；頻譜感知；分枝定界；凸松弛；多信道聯(lián)合感知

1 引言

本文首次嘗試用確定性優(yōu)化方法求解非凸MJD問(wèn)題，首先，將該問(wèn)題建模為一單調(diào)優(yōu)化問(wèn)題，然后，根據(jù)該問(wèn)題的特性在文獻(xiàn)[9]的基礎(chǔ)上提出了一種基于單調(diào)優(yōu)化框架的凸松弛分支定界算法(Branch Reduce and Bound with Convex Relaxation, BRBCR)。BRBCR將原問(wèn)題近似為一系列凸優(yōu)化子問(wèn)題進(jìn)行求解，從而得到一系列較緊的上下界，進(jìn)而加速原問(wèn)題收斂。最后，通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證了本文算法的有效性和優(yōu)越性。

2 認(rèn)知無(wú)線電多信道聯(lián)合感知建模

3 基于單調(diào)優(yōu)化框架的BRBCR算法求解多信道聯(lián)合感知問(wèn)題全局最優(yōu)

3.1 定界

如何得到更緊的上下界成為了解決問(wèn)題的關(guān)鍵。對(duì)于更緊的上界，凸松弛是一個(gè)較好的方法，其將原問(wèn)題近似為如式(2)所示的凸優(yōu)化問(wèn)題：

3.2 分枝

3.3 剪枝

其中

和可由二分法求得。式(6)將中的區(qū)域去除，因?yàn)榇藚^(qū)域并不包含更優(yōu)的下界，式(7)將中的區(qū)域去除，因?yàn)榇藚^(qū)域并不包含可行解。相應(yīng)的剪枝示意圖參見(jiàn)圖1(b)。

3.4 算法收斂性證明

最終的BRBCR算法如表1所示。

表1 BRBCR算法

4 仿真結(jié)果及分析

圖2 不同漏警、虛警概率上限時(shí)的系統(tǒng)吞吐率與干擾代價(jià)關(guān)系

圖3 PA, BRB以及本文算法收斂速度對(duì)比

圖4 本文算法在不同信道數(shù)目下的時(shí)間復(fù)雜度

表2 本文算法在不同精度下的平均收斂時(shí)間以及平均迭代次數(shù)

表3應(yīng)用本文算法評(píng)估GA以及ICSA性能(%)

5 結(jié)束語(yǔ)

本文首次嘗試用確定性全局優(yōu)化方法(BRBCR)對(duì)非凸多信道聯(lián)合感知問(wèn)題進(jìn)行求解，并證明了該方法對(duì)于給定的精度總可以在有限次迭代后收斂。仿真結(jié)果表明，本文算法較傳統(tǒng)的凸優(yōu)化方法可大幅度提升系統(tǒng)性能，且可對(duì)系統(tǒng)在各條件下的性能進(jìn)行分析；本文算法的收斂速度較PA以及傳統(tǒng)的BRB算法提高了2個(gè)數(shù)量級(jí)，且算法收斂時(shí)間并不隨信道數(shù)目增加和收斂精度的提高而顯著變化，因此本文算法可應(yīng)用于大規(guī)模、高精度MJD問(wèn)題的實(shí)時(shí)求解中。另外，由于本文算法可獲得問(wèn)題的全局最優(yōu)解，本文算法還可為其它簡(jiǎn)單算法或快速算法提供基準(zhǔn)，對(duì)這些算法性能進(jìn)行評(píng)估。

[1] Axell E, Leus G, Larsson E G,.. Spectrum sensing for cognitive radio: state-of-the-art and recent advances[J]., 2012, 29(3): 101-116.

[2] Quan Z, Cui S, Sayed A H,.. Optimal multiband joint detection for spectrum sensing in cognitive radio networks [J]., 2009, 57(3): 1128-1140.

[3] Tariq S, Ghafoor A, and Farooq S Z. Analysis of joint multiband sensing-time M-QAM signal detection in cognitive radios[J]., 2012, 34(6): 892-899.

[4] Paysarvi-Hoseini Pedram and Beaulieu N C. Optimal wideband spectrum sensing framework for cognitive radio systems[J]., 2011, 59(3): 1170-1182.

[5] Hossain K, Champagne B, and Assra A. Cooperative multiband joint detection with correlated spectral occupancy in cognitive radio networks[J]., 2012, 60(5): 2682-2687.

[6] Sanna M and Murroni M. Optimization of non-convex multiband cooperative sensing with genetic algorithms[J]., 2011, 5(1): 87-96.

[7] 夏巧橋, 田茂, 汪鼎文, 等.基于免疫克隆算法的認(rèn)知無(wú)線電多信道聯(lián)合感知方法[J]. 電子與信息學(xué)報(bào), 2014, 36(1): 55-60.

Xia Qiao-qiao, Tian Mao, Wang Ding-wen,.. Immune clone algorithm based multiband joint detection for cognitive radio[J].&, 2014, 36(1): 55-60.

[8] Tuy H. Monotonic optimization: problems and solution approaches[J]., 2000, 11(2): 464-494.

[9] Tuy H, Al-Khayyal F, and Thach P T. Monotonic Optimization: Branch and Cut Methods[M]. Essays and Surveys in Global Optimization, Springer US, 2005: 39-78.

[10] Qian L P, Zhang Y J, and Huang J. MAPEL: achieving global optimality for a non-convex wireless power control problem[J]., 2009, 8(3): 1553-1563.

[11] Jorswieck E A and Larsson E G. Monotonic optimization framework for the two-user MISO interference channel[J]., 2010, 58(7): 2159-2168.

[12] Qian L P and Zhang Y J. S-MAPEL: monotonic optimization for non-convex joint power control and scheduling problems [J]., 2010, 9(5): 1708-1719.

[13] Liu L, Zhang R, and Chua K C. Achieving global optimality for weighted sum-rate maximization in the k-user gaussian interference channel with multiple antennas[J]., 2012, 11(5): 1933-1945.

[14] Utschick W and Brehmer J. Monotonic optimization framework for coordinated beamforming in multicell networks[J]., 2012, 60(4): 1899-1909.

[15] Bjornson Emil, Zheng G, Bengtsson M,.. Robust monotonic optimization framework for multicell MISO systems[J]., 2012, 60(5): 2508-2523.

[16] Zhang Qian, Chen He, and Jiang Ling-ge. Achieving maximum weighted sum-rate in multicell downlink MISO systems[J]., 2012, 16(11): 1808-1811.

夏巧橋： 男，1987年生，博士生，研究方向?yàn)檎J(rèn)知無(wú)線電、優(yōu)化算法.

田 茂： 男，1957年生，教授，博士生導(dǎo)師，研究方向?yàn)橐苿?dòng)通信、探地雷達(dá).

汪鼎文： 男，1981年生，副教授，研究方向?yàn)橹悄苡?jì)算、圖像處理.

Optimization of Non-convex Multiband Joint Detection UsingBranch Reduce and Bound Algorithm with Convex RelaxationBased on Monotonic Optimization Framework

Xia Qiao-qiao①Tian Mao①Wang Ding-wen②Chen Xi②

①(,,430072,)②(,,430072,)

Cognitive Radio (CR); Spectrum sensing; Branch Reduce and Bound (BRB); Convex Relaxation (CR); Multiband Joint Detection (MJD)

TN92

A

1009-5896(2014)06-1428-07

10.3724/SP.J.1146.2013.01279

汪鼎文 wangdw@whu.edu.cn

2013-08-22收到，2013-12-11改回

國(guó)家自然科學(xué)基金(61072135)資助課題