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