WSN中基于混合整數非線性規劃的功率分配算法*

李 睿,趙保華

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

?

WSN中基于混合整數非線性規劃的功率分配算法*

李 睿1*,趙保華2

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

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

無線傳感網;協作路由;碰撞概率;功率分配;分支界定法

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

圖1 協作通信模型

引入協作通信的路由稱為協作路由。因此,協作路由是利用網絡層和物理層的交叉層設計,通過協作鏈路傳輸數據包。交叉層的設計能夠有效地提高無線網絡的路由性能[4]。通常將協作路由看成協作傳輸鏈路和直接傳輸鏈路的串聯。

如圖2所示,節點ab間構成了直接傳輸鏈路,而節點i、k、j3個節點構成了協作傳輸鏈路。在協作傳輸中,除了發射節點與接收節點間的直接鏈路外,還存在由一個或多個轉發節點參與協作鏈路。

圖2 協作路由

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

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

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

1 系統模型

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

(1)

(2)

式中:N0為噪聲功率。

2 路由中斷概率

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

圖3 傳輸碰撞示例

(3)

(4)

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

(5)

(6)

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

(7)

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

(8)

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

(9)

(10)

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

(11)

(12)

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

(13)

3 目標函數

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

(14)

(15a)

(15b)

(15c)

(15d)

(15e)

(16)

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

4 基于BBSR的求解算法

為了降低計算復雜度,首先將每條鏈路的源節點、轉發節點的傳輸功率進行獨立優化,然后再進行最優功率分配。

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

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

輸入:傳感節點集N、源節點集Ns、目的節點D

Step1:Ps←0dBm,pl←0dBm

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

輸出:優化的功率分配

圖4 基于BBSR算法的偽代碼

對于每條所選擇的協作鏈路的約束優化問題可表述為:

(17)

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

(18)

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

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

(19)

(20)

(21)

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

(22)

(23)

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

5 數值分析

5.1 仿真場景

表1 真參數

5.2 仿真結果及分析

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

圖5 撞概率

5.2.1 碰撞概率

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

5.2.2 總的傳輸功率

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

圖6 的傳輸功率

6 總結

針對無線傳感網的協作路由,提出基于最小化碰撞概率的功率分配CMPA算法。傳統的協作路由只強調最小化傳輸功率,并沒有考慮因協作傳輸而引發的數據包碰撞,忽略了鏈路中斷問題。為了解決此問題,CMPA算法首先推導了中斷概率數學模型,然后構建目標函數,再利用BBSR算法求解,并結合拉格朗日乘子算法求解最優的功率分配。仿真結果表明,提出的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] 王亞聰,趙柏秦,吳南健,等. 動態路由機制下無線傳感器網絡的拓撲控制方法[J]. 儀表技術與傳感器,2016,106(11):110.

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