WSN中基于混合整數(shù)非線性規(guī)劃的功率分配算法*

李 睿,趙保華

(1.阿壩師范學(xué)院網(wǎng)絡(luò)管理中心,四川 汶川 623002;2.阿壩師范學(xué)院圖書(shū)館,四川 汶川 623002)

?

WSN中基于混合整數(shù)非線性規(guī)劃的功率分配算法*

李 睿1*,趙保華2

(1.阿壩師范學(xué)院網(wǎng)絡(luò)管理中心,四川 汶川 623002;2.阿壩師范學(xué)院圖書(shū)館,四川 汶川 623002)

近期協(xié)作路由協(xié)議的研究受到廣泛關(guān)注。然而,現(xiàn)多數(shù)協(xié)作路由協(xié)議是以減少能量消耗為目的,它們并沒(méi)有考慮在協(xié)作路由中的數(shù)據(jù)包碰撞概率最小化問(wèn)題。為此,針對(duì)無(wú)線傳感網(wǎng)WSNs(Wireless Sensor Networks)的協(xié)作路由,提出基于最小化碰撞概率的功率分配CMPA(Collision Minimization-based Power Allocation)算法。首先,推導(dǎo)了碰撞概率數(shù)學(xué)模型,并形成了混合整數(shù)非線性規(guī)劃問(wèn)題。然后,為了降低復(fù)雜度,將功率分配和路由選擇進(jìn)行獨(dú)立處理,同時(shí)利用分支界定空間縮小BBSR(Branch-and-Bound Space Reduced)算法求解。仿真結(jié)果表明,提出的CMPA算法能夠有效地降低碰撞概率和總的傳輸功率。與OKCR算法相比,CMPA算法的碰撞概率下降了近82%,總的傳輸功率下降了0.1 dB。

無(wú)線傳感網(wǎng);協(xié)作路由;碰撞概率;功率分配;分支界定法

協(xié)作通信被認(rèn)為是緩解無(wú)線信道衰落和提高無(wú)線網(wǎng)絡(luò)可靠性的最有前景的技術(shù)[1]。在協(xié)作通信中,節(jié)點(diǎn)利用無(wú)線通信的廣播特性,相互輔助信號(hào)傳輸。圖1描述了一個(gè)簡(jiǎn)單的協(xié)作通信模式。源節(jié)點(diǎn)s和轉(zhuǎn)發(fā)節(jié)點(diǎn)l有共同的目的節(jié)點(diǎn)d。每個(gè)節(jié)點(diǎn)均配備天線。實(shí)際上,節(jié)點(diǎn)可以偷聽(tīng)到其他節(jié)點(diǎn)的信號(hào)。由于兩節(jié)點(diǎn)間路徑衰落為統(tǒng)計(jì)獨(dú)立,可產(chǎn)生空間分集。目的節(jié)點(diǎn)能夠接收來(lái)自不同路徑的信號(hào)復(fù)本,并依據(jù)復(fù)本信號(hào),結(jié)合融合算法,可得到最優(yōu)的信號(hào)值[2-3]。

圖1 協(xié)作通信模型

引入?yún)f(xié)作通信的路由稱為協(xié)作路由。因此,協(xié)作路由是利用網(wǎng)絡(luò)層和物理層的交叉層設(shè)計(jì),通過(guò)協(xié)作鏈路傳輸數(shù)據(jù)包。交叉層的設(shè)計(jì)能夠有效地提高無(wú)線網(wǎng)絡(luò)的路由性能[4]。通常將協(xié)作路由看成協(xié)作傳輸鏈路和直接傳輸鏈路的串聯(lián)。

如圖2所示,節(jié)點(diǎn)ab間構(gòu)成了直接傳輸鏈路,而節(jié)點(diǎn)i、k、j3個(gè)節(jié)點(diǎn)構(gòu)成了協(xié)作傳輸鏈路。在協(xié)作傳輸中,除了發(fā)射節(jié)點(diǎn)與接收節(jié)點(diǎn)間的直接鏈路外,還存在由一個(gè)或多個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)參與協(xié)作鏈路。

圖2 協(xié)作路由

針對(duì)協(xié)作路由,研究人員提出許多不同的算法[5-7]。文獻(xiàn)[8]提出CAN-L算法,最小化總的傳輸功率。CAN-L算法首先尋找非協(xié)作最短路徑,然后將沿著非協(xié)作最短路徑的最近的L個(gè)節(jié)點(diǎn)進(jìn)行協(xié)作傳輸。而文獻(xiàn)[9]提出k條最短路徑的協(xié)作路由OKCR算法。OKCR算法先執(zhí)行k條非協(xié)作最短路徑,然后在每條非協(xié)作路徑的鏈路中,選擇具有最低中斷概率的轉(zhuǎn)發(fā)節(jié)點(diǎn)。

此外,文獻(xiàn)[10]提出了最小功率協(xié)作路由MPCR(Minimum Power Cooperative Routing)算法。該算法尋找具有最小總的傳輸功率路由。同時(shí),MPCR算法是假定每條鏈路均可獲取協(xié)作傳輸為前提的,在此前提條件下進(jìn)行路由決策。文獻(xiàn)[11]提出了EP-H1算法。該算法采用兩步策略,搜索具有最小化能量的路由。第一步:源節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播消息;第二步,能夠成功解碼消息的節(jié)點(diǎn)與源節(jié)點(diǎn)進(jìn)行聯(lián)合,形成協(xié)作傳輸集。協(xié)作傳輸集內(nèi)節(jié)點(diǎn)以協(xié)作方式,并以同功率向接收節(jié)點(diǎn)傳輸消息。文獻(xiàn)[12]通過(guò)估計(jì)信道質(zhì)量,然后再分配節(jié)點(diǎn)的發(fā)射功率。該算法先建立樹(shù)型拓?fù)浣Y(jié)構(gòu),再通過(guò)RSSI和LQI估計(jì)信道質(zhì)量。此外,文獻(xiàn)[13]也提出了基于自適應(yīng)模糊理論進(jìn)行功率分配,通過(guò)模糊理論應(yīng)對(duì)網(wǎng)絡(luò)的動(dòng)態(tài)變化。

上述的協(xié)作路由是以最優(yōu)化路由算法為目的,在保證一定QoS條件下,最小化傳輸功率。然而,它們?cè)趨f(xié)作路由中并沒(méi)有考慮數(shù)據(jù)包碰撞概率最小化問(wèn)題。為此,本文首先推導(dǎo)了協(xié)作路由的碰撞概率表達(dá)式,然后利用分支界定空間縮小BBSR(Branch-and-Bound Space Reduced)算法選擇路由,再依據(jù)拉格朗日乘子算法優(yōu)化功率分配。仿真結(jié)果表明,提出的CMPA算法能夠有效地降低碰撞概率,并減少了總的傳輸功率。

1 系統(tǒng)模型

考慮一個(gè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)間以協(xié)作路由方式實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)臒o(wú)線網(wǎng)絡(luò),如圖1所示。選擇文獻(xiàn)[10]所述的服從指數(shù)γ的路徑衰落模型。在直接傳輸中,源節(jié)點(diǎn)s直接向目的節(jié)點(diǎn)d傳輸信號(hào),則節(jié)點(diǎn)d接收了來(lái)自節(jié)點(diǎn)s的信號(hào)為ysd:

(1)

(2)

式中:N0為噪聲功率。

2 路由中斷概率

假定整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)集為N,這些節(jié)點(diǎn)分為3類:①源節(jié)點(diǎn)集Ns={s1,s2,…,sNs};②目的節(jié)點(diǎn)集Nd={d1,d2,…,dNd};③其他節(jié)點(diǎn),這些節(jié)點(diǎn)扮演成轉(zhuǎn)發(fā)節(jié)點(diǎn)。此外,令兩節(jié)點(diǎn)(假定節(jié)點(diǎn)i、j)間的距離rij。如果rij≥Rd,節(jié)點(diǎn)i、j間鏈接不成功,即Coni,j=0,其中Con為鏈接成功指標(biāo)。反之rij

圖3 傳輸碰撞示例

(3)

(4)

式中:Ei,n為二值變量,定義如式(5)所示:

(5)

(6)

而Prtx(n)表示節(jié)點(diǎn)n表示發(fā)射信號(hào)概率,即Prtx(n)=Δt(n)Tp,其中Tp表示數(shù)據(jù)包的有效時(shí)期,而Δt(n)表示節(jié)點(diǎn)n的總的數(shù)據(jù)包傳輸率,其定義如式(7)所示:

(7)

式中:Δ0(n)表示節(jié)點(diǎn)n的數(shù)據(jù)包產(chǎn)生率。SNRmn表示節(jié)點(diǎn)m和n間鏈路的信噪比SNR值。

(8)

式中:Pr(NSTs)表示不在源節(jié)點(diǎn)s的感測(cè)范圍內(nèi)的平均概率,其定義如式(9)所示:

(9)

(10)

因此,整個(gè)路由碰撞概率為

(11)

(12)

端到端路由的中斷概率被定義為:H跳路由中某一跳發(fā)生中斷的概率:

(13)

3 目標(biāo)函數(shù)

算法的目的就是:在滿足端到端中斷概率限制條件下,通過(guò)最小化碰撞概率,尋找從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路由。因此,優(yōu)化問(wèn)題可利用式(14)的目標(biāo)函數(shù)表述:

(14)

(15a)

(15b)

(15c)

(15d)

(15e)

(16)

式中:Pr(Collrouter)為路由r所產(chǎn)生的總的碰撞概率。

4 基于BBSR的求解算法

為了降低計(jì)算復(fù)雜度,首先將每條鏈路的源節(jié)點(diǎn)、轉(zhuǎn)發(fā)節(jié)點(diǎn)的傳輸功率進(jìn)行獨(dú)立優(yōu)化,然后再進(jìn)行最優(yōu)功率分配。

假定在目標(biāo)函數(shù)CollT中采用相同的、固定傳輸功率和限制條件。依據(jù)IEEE802.15.4標(biāo)準(zhǔn)[14],目標(biāo)函數(shù)中的傳輸功率設(shè)定為0dBm。即目標(biāo)函數(shù)CollT的成本函數(shù)為:CollT|ps=pl=0 dBm。

首先利用分支界定空間縮小BBSR(Branch-and-BoundSpaceReduced)算法[14-18],進(jìn)行路徑選擇優(yōu)化;然后再利用拉格朗日乘子算法求解約束的優(yōu)化問(wèn)題,最終得到優(yōu)化功率分配?；贐BSR算法的偽代碼如圖4所示。

輸入:傳感節(jié)點(diǎn)集N、源節(jié)點(diǎn)集Ns、目的節(jié)點(diǎn)D

Step1:Ps←0dBm,pl←0dBm

Step5:Obtainoptimalpowerallocationfortransmitterandrelaynodefromequations(24),(25),(26)

輸出:優(yōu)化的功率分配

圖4 基于BBSR算法的偽代碼

對(duì)于每條所選擇的協(xié)作鏈路的約束優(yōu)化問(wèn)題可表述為:

(17)

在協(xié)作傳輸鏈路中,利用利用拉格朗日乘子算法解決約束的優(yōu)化問(wèn)題,如式(18)所示:

(18)

式中:λ表示拉格朗日乘子。

將式(10)～式(13)代入式(18),可得式(19)～式(21):

(19)

(20)

(21)

式中:φ(p,n)、θ(p,n)定義如下:

(22)

(23)

通過(guò)式(19)、式(20)和式(21)可同步求解ps和pl。

5 數(shù)值分析

5.1 仿真場(chǎng)景

表1 真參數(shù)

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

為了更充分地考查CMPA算法的性能,選擇CAN-L[8]、OKCR[9]、MPCR[10]、EP-H1[11]、TCM[12]協(xié)作路由協(xié)議進(jìn)行比較。它們均是典型的協(xié)作路由算法。OKCR、EP-H1、MPCR、CAN-L算法的目的就是最小化協(xié)作路由的總的傳輸功率。為此,分析了它們的碰撞概率和總的傳輸功率隨節(jié)點(diǎn)數(shù)的變化情況,結(jié)果如圖5、圖6所示。

圖5 撞概率

5.2.1 碰撞概率

圖5描述了OKCR、EP-H1、MPCR、CAN-3和CMPA算法的碰撞概率隨節(jié)點(diǎn)數(shù)的變化曲線。由圖5可知,提出的CMPA的碰撞概率優(yōu)于OKCR、EP-H1、MPCR、TCM、CAN-L具有最低的碰撞概率。當(dāng)傳感節(jié)點(diǎn)數(shù)N=49時(shí),CMPA協(xié)議的碰撞概率分別比OKCR、EP-H1、MPCR、CAN-L和TCM降低了約82%、78%、56%、93%和32%。這主要?dú)w功于:①CMPA協(xié)議采用了INLP算法選擇協(xié)作路由;②在路由選擇期間,將碰撞概率看作成本函數(shù),并最小化碰撞概率;③同時(shí)分配每一跳的功率,進(jìn)而最小化碰撞概率。通過(guò)這些策略,使得CMPA協(xié)議能夠避免選擇高碰撞概率節(jié)點(diǎn)或者是多數(shù)鄰居節(jié)點(diǎn)的碰撞概率很高的節(jié)點(diǎn)為轉(zhuǎn)發(fā)節(jié)點(diǎn),最終降低了碰撞概率。

5.2.2 總的傳輸功率

圖6描述了5類算法的總的傳輸功率隨節(jié)點(diǎn)數(shù)的變化情況所示。從圖6可知,總的傳輸功率隨節(jié)點(diǎn)數(shù)的增加而上升,原因在于節(jié)點(diǎn)數(shù)增加加大了源節(jié)點(diǎn)與信宿節(jié)點(diǎn)間的距離。此外,CAN-L所所消耗的總的傳輸功率最多,原因在于:CAN-L算法先構(gòu)建最短路徑,然后將最新的3(L=3)條鏈路進(jìn)行協(xié)作傳輸。因此CAN3只限定部分節(jié)點(diǎn)進(jìn)行協(xié)作傳輸,而其他算法考慮任何節(jié)點(diǎn)都可進(jìn)行協(xié)作傳輸。這就使得CAN-L算法的總的傳輸節(jié)點(diǎn)高于其他算法。與MPCR和TCM算法相比,提出的CMPA算法的總的傳輸功率并無(wú)優(yōu)勢(shì),這主要是因?yàn)镸PCR算法是以降低總的傳輸功率為根本目的,并沒(méi)有兼顧碰撞概率的性能。從圖5可知,MPCR算法的碰撞概率是高于CMPA算法。

圖6 的傳輸功率

6 總結(jié)

針對(duì)無(wú)線傳感網(wǎng)的協(xié)作路由,提出基于最小化碰撞概率的功率分配CMPA算法。傳統(tǒng)的協(xié)作路由只強(qiáng)調(diào)最小化傳輸功率,并沒(méi)有考慮因協(xié)作傳輸而引發(fā)的數(shù)據(jù)包碰撞,忽略了鏈路中斷問(wèn)題。為了解決此問(wèn)題,CMPA算法首先推導(dǎo)了中斷概率數(shù)學(xué)模型,然后構(gòu)建目標(biāo)函數(shù),再利用BBSR算法求解,并結(jié)合拉格朗日乘子算法求解最優(yōu)的功率分配。仿真結(jié)果表明,提出的CMPA算法能夠有效地降低碰撞概率和總的傳輸功率。

[1] Laneman J N,Tse D N C,Wornell G W. Cooperative Diversity in Wireless Networks:Efficient Protocols and Outage Behavior[J]. IEEE Trans Inf Theory,2014,50(12):3062-3080.

[2] Madan R,Mehta N B,Molisch A F,et al. Energy-Efficient Decentralized Cooperative Routing in Wireless Networks[J]. IEEE Trans Autom Control,2009,54(3):512-527.

[3] Zhuang W,Ismail M. Cooperation in Wireless Communication Networks[J]. IEEE Wireless Commun,2012,19(2):10-20.

[4] Nosratinia A,Hunter T E,Hedaya A. Cooperative Communication in Wireless Networks[J]. IEEE Commun Mag,2014,42(10):74-80.

[5] Zhang J,Zhang Q. Cooperative Routing in Multi-Source Multi-Destination Multi-Hop Wireless Networks[C]//Proc IEEE 27th Conf Comput Commun(INFOCOM),2008:306-310.

[6] Han B,Li J,Su J,et al. Self-Supported Cooperative Networking for Emergency Services in Multi-Hop Wireless Networks[J]. IEEE J Sel Areas Commun,2012,30(2):450-457.

[7] Mansourkiaie F,Ahmed M H. Joint Cooperative Routing and Power Allocation for Collision Minimization in Wireless Sensor Networks with Multiple Flows[J]. IEEE Wireless Commun Lett,2015,4(1):6-9.

[8] Khandani A E,Abounadi J,Modiano E,et al. Cooperative routing in Static Wireless Networks[J]. IEEE Trans Commun,2012,55(11):. 2185-2192.

[9] Ahmadi P,Jabbari B. An Outage-Aware Power Saving Cooperative Routing Algorithm in Wireless Networks[C]//Proc Wireless Telecommun Symp(WTS),2013:1-5.

[10] Ibrahim A,Han Z,Liu K J R. Distributed Energy-Efficient Cooperative Routing in Wireless Network[J]. IEEE Trans Wireless Commun,2013,7(10):3930-3941.

[11] Dehghan M,Ghaderi M,Goeckel D. Minimum-Energy Cooperative Routing in Wireless Networks with Channel Variations[J]. IEEE Trans Wireless Commun,2011,10(11):3813-3823.

[12] 王亞聰,趙柏秦,吳南健,等. 動(dòng)態(tài)路由機(jī)制下無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂品椒╗J]. 儀表技術(shù)與傳感器,2016,106(11):110.

[13] 邵奇可,馮淑娜,毛科技. 面向WSN的自適應(yīng)模糊功率控制算法研究[J]. 傳感技術(shù)學(xué)報(bào),2015,28(4):563-572.

[14] Wireless Medium Access Control(MAC)and Physical Layer(PHY)Specications for Low-Rate Wireless Personal Area Networks(WPANs),IEEE Standard 802.15.4,2011.

[15] Mansourkiaie F,Md Hossam Ahmed. Optimal and Near-Optimal Cooperative Routing and Power Allocation for Collision Minimization in Wireless Sensor Networks[J]. IEEE Sensors Journal,2016,16(5):1398-1412.

[16] Huang R,Chen Z,Xu G. Energy-Aware Routing Algorithm in wsn Using Predication-Mode[C]//2010 International Conference on Communications,Circuits and Systems,2010:103-107.

[17] M F,Li Tongtao,Jia Tinggang,et al. Time Delay Characteristic of Industrial Wireless Networks Based on IEEE 802.15.4a[J]. International Journal of Automation and Computing,2011,8(2):170-179.

[18] Rezvani M,Ignjatovic A,Bertino E,et al. Secure Data Aggregation Technique for Wireless Sensor Networks in the Presence of Collusion Attacks[J]. School Comput Sci and Eng,Univ. New South Wales,Kensington,NSW,Australia,Tech Rep,2013,34(6):23-31.

李 睿(1982-),男,四川省宜賓市人,碩士,阿壩師范學(xué)院教育信息技術(shù)中心副研究員,主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò),通信和信號(hào)處理,20271699@qq.com。

Mixed Integer Non-Linear Programming Problem-BasedPower Allocation Algorithm in WSNs*

LI Rui1*,ZHAO Baohua2

(1.Network Management Center,ABa Teacher’s College,Wenchuan Sichuan 623002,China;2.Library,ABa Teacher’s College,Wenchuan Sichuan 623002,China)

Recently,cooperative routing has

widespread attention. Most of the existing cooperative routing algorithms are designed to reduce the energy consumption;however,packet collision minimization using cooperative routing has not yet been addressed. Collision Minimization-based power allocation(CMPA)algorithm for cooperative routing in wireless sensor networks(WSNs)is proposed in this paper. In CMPA algorithm,we introduce a mathematical mode,and firstly formulate the problem as a large-scale mixed integer non-linear programming problem. Then the branch-and-bound space reduced method(BBSR)is used to solve the problem.The simulation results reveal that the presented algorithms can significantly reduce the collision probability and total transmission power compared with the existing schemes. Compared with OKCR algorithm,Collision probability of CMPA algorithm is reduced by 82%,total transmission power is reduced by 0.1 dB.

wireless sensor networks;cooperative routing;collision probability;power allocation;branch-and-bound

項(xiàng)目來(lái)源:國(guó)家863計(jì)劃項(xiàng)目(2013AA040302);四川省教育廳重點(diǎn)項(xiàng)目(15ZA0338)

2016-09-26 修改日期:2017-03-27

TPT393

A

1004-1699(2017)07-1119-06

C:7230

10.3969/j.issn.1004-1699.2017.07.025