李 睿,趙保華

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

?

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

李 睿1*,趙保華2

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

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

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

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

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

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

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

圖2 協(xié)作路由

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

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

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

1 系統(tǒng)模型

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

(1)

(2)

式中:N0為噪聲功率。

2 路由中斷概率

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

圖3 傳輸碰撞示例

(3)

(4)

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

(5)

(6)

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

(7)

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

(8)

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

(9)

(10)

因此,整個路由碰撞概率為

(11)

(12)

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

(13)

3 目標函數(shù)

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

(14)

(15a)

(15b)

(15c)

(15d)

(15e)

(16)

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

4 基于BBSR的求解算法

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

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

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

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

Step1:Ps←0dBm,pl←0dBm

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

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

圖4 基于BBSR算法的偽代碼

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

(17)

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

(18)

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

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

(19)

(20)

(21)

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

(22)

(23)

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

5 數(shù)值分析

5.1 仿真場景

表1 真參數(shù)

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

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

圖5 撞概率

5.2.1 碰撞概率

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

5.2.2 總的傳輸功率

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

圖6 的傳輸功率

6 總結(jié)

針對無線傳感網(wǎng)的協(xié)作路由,提出基于最小化碰撞概率的功率分配CMPA算法。傳統(tǒng)的協(xié)作路由只強調(diào)最小化傳輸功率,并沒有考慮因協(xié)作傳輸而引發(fā)的數(shù)據(jù)包碰撞,忽略了鏈路中斷問題。為了解決此問題,CMPA算法首先推導了中斷概率數(shù)學模型,然后構(gòu)建目標函數(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] 王亞聰,趙柏秦,吳南健,等. 動態(tài)路由機制下無線傳感器網(wǎng)絡的拓撲控制方法[J]. 儀表技術(shù)與傳感器,2016,106(11):110.

[13] 邵奇可,馮淑娜,毛科技. 面向WSN的自適應模糊功率控制算法研究[J]. 傳感技術(shù)學報,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-),男,四川省宜賓市人,碩士,阿壩師范學院教育信息技術(shù)中心副研究員,主要研究領(lǐng)域為計算機網(wǎng)絡,通信和信號處理,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

項目來源:國家863計劃項目(2013AA040302);四川省教育廳重點項目(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