可持续WSN中基于能量采集感知的中继节点部署算法

吕志恒

(永城职业学院信息工程系,河南 永城 476600)

目前,无线传感网络WSNs(Wireless Sensor Networks)已在多类应用中使用,如火灾检测、康复医疗、战场勘测。然而,由于WSNs是由微型的传感节点组成,节点的能量(电池)是有限的[1-2]。一旦节点能量低至一定量时,节点再也无法工作,形成覆盖空洞,这就影响了WSNs性能。

针对WSNs的能量受限问题,研究人员已提出不同的策略[3]。如休眠/唤醒机制、功率控制机制和能耗感知路由协议。休眠/唤醒机制是通过减少节点的工作时间,保存能量。而功率控制机制是通过降低节点发射功率,减少能耗。而能耗感知路由协议是从提高能量利用率角度,构建路由。尽管这些机制能够保存能量,但是它们均是在给定的有限能量基础上,提高能量利用率,并没有从根本上解决能量有限问题。

近期,绿色能源概念已广泛推广,相关的研究也逐渐深入,如电磁波、太阳能,风能等[4-5]。因此,可利用这些绿色能源解决WSNs内节点能量有限问题。即节点从周期环境获取能量,进行能量补给。将这类WSNs称为可持续WSNs。与太阳能、风能相比,利用电磁波给节点补给能量更为稳定。因为太阳能和风能随环境天气变化大,极为不稳定。因此,本文选择通过基站对节点进行无线充电[6-7]。

即使在可持续WSNs,部分节点的能量可能也会提前消耗殆尽。因为不同的节点所采集的能量不同,能量消耗速度也不尽相同。当节点能量消耗殆尽后,需要在其附近部署节点,进而修复覆盖空洞。为此,将类部署节点称为中继节点RNs(Relay Nodes)。

考虑到成本问题,可持续WSNs内的RNs数是有限的,并需确定性部署。部署RNs的目的在于弥补能量消耗殆尽的节点所留下的覆盖空洞,并保持网络连通率。为此,本文的主要工作在于如何部署RNs,进而实现以最小RNs数完成最大的数据包传输率的目的。

针对可持续WSNs,对RNs的部署问题进行研究,并提出基于最小生成树MST(Minimum Spanning Tree)的部署算法EHA-DRN(Minimum Spanning Tree-based Deploying Relay Nodes algorithm)。EHA-DRN算法先依据节点所收集的能量的多少,然后依据节点能量采集率,并结合克鲁斯卡尔(Kruskal)算法构建MST。最后,检测MST内的非叶节点的能量是否能完成数据传输要求,如果不能完成,则称为低能量节点LENs(Low-Energy-Nodes)。这类节点就需要RNs的协助,即在这些节点附近部署RNs,进而维持网络的覆盖率。

本文的创新点之处在于:①依据节点采集能量的能力,计算边权重,然后依据边权重,并利用Kruskal算法构建最小生成树MST;②依据MST部署RNs。检测最小生成树上的非叶节点的能量是否能完成数据传输,如果不能,则在附近部署RNs。

1 约束条件及能量模型

1.1 约束条件

利用无向图G=(V,E)表示网络拓扑[8],其中V为顶点集、而E为边集。若某节点在自己的通信范围内,则它们之间便可形成一条边。本文引用周期流量。所谓周期流量是指节点周期地向基站传输感测数据包,且数据包格式固定,数据包大小为λ比特。

具体而言,节点i在时期T内接收的数据流表示为Reci,其由自己产生的数据包和从支叶节点所接收的数据流组成,定义如式(1)所示:

Reci=λγi

(1)

式中:

(2)

式中:γi为节点i的支叶节点(子节点和孙子节点),而Ci表示直系子节点数[9-10]。

而节点i向基站传输的数据流Tri:

Tri=λ(γi+1)

(3)

1.2 能量模型

本文基于无线充电的能量模型。节点通过无线网络进行充电[11-12],并引用Beamforming技术形成尖利能量束[13],再传递至节点,如图1所示。节点依据功率beacon包获取电能,并由能量管理单元管理所采集的能量,同时将多余能量存储。同时,将传输数据包与充电能量路径分开,这有利于减少彼此的干扰。

图1 节点充电模型

假定节点i在单位时间内采集的能量为hi,即能量采集率。依据文献[13],hi与多个因素有关,其定义如式(4)所示:

(4)

此外,令Ep表示在每个周期内执行感测、计算任务时所消耗的能量。而Et、Er分别表示传输或接收一比特所消耗的能量。因此节点i所消耗的总能量Ei:

Ei=ReciEr+TriEt+Ep

(5)

2 EHA-DRN算法

整个EHA-DRN算法由两个阶段构成:①构建最小生成树;②部署RNs。如图2所示。在构建最小生成树阶段,利用节点的能量采集率,计算节点权重,然后再计算边权重,最后构建最小生成树。而在部署RNs阶段,先检测低能量节点LENs,再部署RNs。

图2 EHA-DRN算法框图

2.1 权重

ωi=(hmax-hi)/hmax

(6)

EHA-DRN算法先引用节点能量采集率计算节点权重。节点i的权重ωi如式(7)所示:

ωi=(hmax-hi)/hmax

(7)

再依据节点权重,计算边重。每条边权重等于这边条的两个端节点的权重之和,如式(8)所示:

图3 基于边权重的网络拓扑图

(8)

式中:Wu,υ表示节点u、υ间所构成的边权重。

依据各边的权重,便形成基于边权重的网络拓扑图。图3显示了构建基于边权重的网络拓扑图过程。如图3所示,图3(a)表示网络拓扑图,数字表示节点的能量采集率h。例如,节点5的能量采集容量h5=20。依据式(6),可计算每个节点权重,其中hmax=30,如图3(b)所示。例如,节点5的权值ω5=(30-20)/30=0.33。

结合图3(c),并依据式(8)计算各边权重,如图3所示。例如,由节点5和节点9构成的边的权值就等于0.49=0.33+0.16。

2.2 最小生成树

依据基于边权重的网络拓扑图,结合Kruskal算法产生最小生成树。

Kruskal算法是构建最小生成树的常用算法,其是通过边权重产生最小连通图Γ。其思路简述如下:先从E中选择权重最小的边,若该边的顶点在Γ中不同的连通分量上,则该边加入Γ中,否则丢弃。然后,再从E中选择权重最小的边,依次类推,直到所有顶点均连通在同一个拓扑图内。

仍以图3为例,描述构建最小生成树的原理。先从找到最小权重的边,从图3(c)可知,边权重最小值为0。具有0权重的边有多边,随机从中选择一边,假定选择了是节点2连通基站的边。然后,再从中选择最小权重的边,再把节点1、节点3分别连接基站的边加入,依据类推,便形成如图4所示的最小生成树。

2.3 基于MST的LENs检测

构建了最小生成树后,再检测LENs节点。假定γi表示节点i的支叶节点数,如果γi=0,则表示γi最低层叶节点(无子节点),否则为有子节点。

基于MST的LENs检测过程如下:

①对于节点i∈NMST,如果节点γi=0,则i+1,再执行①;否则执行②;其中NMST表示最小生成树的节点集。

②如果γi≠0,则检测是否满足式(9)。如果满足则跳到步骤①,否则就将节点i加入R。其中R表示LENs的节点。

hiT≥Ei,∀i∈NMST

(9)

最后,依据R部署RNs节点,并由RNs负责数据包的传输,减少LENs节点的任务,进而保存它们的能量。

图5 EHA-DRN算法的伪代码

整个算法的伪代码如图5所示。先依据节点能量采集率计算节点权重和边权重,再形成边权重矩阵W′。再将E、V和W′作为Kruskal算法的输入,输出为以基站为根节点的MST树。再检测MST树内的有子节点,并判断是否满足式(9),如果不满足,就将加入R。其中|R|表示需要部署RNs的节点数,|R|越少,成本越低。

3 仿真分析

3.1 仿真参数

引用NS3[14]网络仿真器建立仿真平台。在仿真中,N个随机在分布于100 m×100 m区域。同时,引用文献[12]的能量模型参数。节点周期性地向基站传输数据包,数据包大小为32 byte。选择部署成本和数据包传输成功率作为性能指标。其中,部署成本为部署RNs的节点数,节点数越多,说明成本越高。

此外,为了对比分析,选择文献[15]的MRA算法和文献[2]基于ILP推导成本下限作为参照。每次实验数据独立重复20次,取平均值作为最终实验数据。

图6 成本随节点数的变化曲线

3.2 数据分析

先分析网络内节点数对部署成本的影响。成本随节点数的变化曲线如图6所示。

从图6可知,节点数的增加提高部署成本。这主要是因为:网络内节点数越多,出现低能量节点的概率越大,需要部署更多的中继节点。此外,同MBA算法相比,提出的EHA-DRN算法的部署成本得到有效地控制。这说明,利用最小生成树搜索低能量节点,可减少部署成本。当然,将EHA-DRN与LB-ILP算法进行比较不难发现,EHA-DRN算法的部署成本仍有一定的下降空间。

接下来,分析网络密度对部署成本的影响,实验数据如图7所示。其中,网络密度是指网络内节点所连接的平均边数。

图7 成本随网络密度的变化曲线

从图7可知,网络密度的增加,降低了部署成本。这主要是因为:网络密度越大,节点所连接的边数越多,那么节点拥有更多边去传输数据,换而言之,由更的边分担了数据传输任务,最终降低了节点的能耗,使得低能量节点数越少。与MBA算法相比,提出的EHA-DRN算法的部署成本得到控制,但仍与LB-ILP的所推导的成本下限有差异。

最后,分析MBA和EHA-DRN算法的数据包传递率,实验数据如图8所示。

由图8可知,EHA-DRN算法的数据包传递率得到有效地提高,数据包传递率不低于0.9。这主要是因为:EHA-DRN算法通过节点能量采集率建立最小生成树,并由最小生成树传输数据包,缩短了数据传输路径,也降低了低能量节点参与数据传输的概率。

图8 数据包传递率随节点数的变化情况

4 总结

基于可持续WSNs,提出基于能量采集感知的中继节点部署EHA-DRN算法。EHA-DRN算法从节点能量采集率构建边权重,然后再利用Kruskal算法产生最小生成树。最后,依据最小生成树,检测低能量节点,并在这些低能量节点附近部署中继节点。实验数据表明,提出的EHA-DRN算法降低了部署成本,也提高了数据包传输成功率。

后期,将进一步优化EHA-DRN算法,降低部署成本,使其逼近基于LB-ILP所推导的成本下限。这是后期的工作方向。

参考文献:

[1] Yang D,Misra S,Fang X,et al. Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks:Computational Complexity and Efficient Approximations[J]. IEEE Trans Mob Comput,2012,11(8):1399-1411.

[2] 陈东海,李长庚. 基于簇头功能分化的无线传感器网络成簇算法[J]. 传感技术学报,2015,28(2):244-248.

[3] Wang F,Wang D,Liu J. Traffic-Aware Relay Node Deployment:Maximizing Lifetime for Data Collection Wireless Sensor Networks[J]. IEEE Trans Parallel Distrib Syst,2011,22(8):1415-1423.

[4] Zheng Z,Cai L X,Zhang R,et al. Rnp-sa:Joint Relay Placement and Sub-Carrier Allocation in Wireless Communication Networks with Sustainable Energy[J]. IEEE Trans Wireless Commun,2012,11(10):3818-3828.

[5] Chelli A,Bagaa M,Djenouri D,et al. One-Step Approach for Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks[J]. IEEE Wireless Commun Letters,2016,5(4):448-451.

[6] Zhang P,Xiao G,Tan H P. Clustering Algorithms for Maximizing the Lifetime of Wireless Sensor Networks with Energy-Harvesting Sensors[J]. Computer Networks,2013,57(14):2689-2704.

[7] Misra S,Majd N E,Huang H. Approximation Algorithms for Constrained Relay Node Placement in Energy Harvesting Wireless Sensor Networks[J]. IEEE Trans Computers,2014,63(12):23-33.

[8] Prasad R V,Devasenapathy S,Rao V S,et al. Reincarnation in the Ambiance:Devices and Networks with Energy Harvesting[J]. IEEE Commun Surveys and Tutorials,2014,16(1):195-213.

[9] Castagnetti A,Pegatoquet A,Le T N,et al. A Joint Duty-Cycle and Transmission Power Management for Energy Harvesting Wsn[J]. IEEE Trans Industrial Informatics,2014,10(2):928-936.

[10] Michelusi N,Zorzi M. Optimal Adaptive Random Multi-Access in Energy Harvesting Wireless Sensor Networks[J]. IEEE Transactions on Communications,2015,63(4):1355-1372.

[11] Huang K,Lau V K N. Enabling Wireless Power Transfer in Cellular Networks:Architecture,Modeling and Deployment[J]. IEEE Transactions on Wireless Communications,2014,13(2):902-912.

[12] Huang K,Zhou X. Cutting the Last Wires for Mobile Communications by Microwave Power Transfer[J]. IEEE Communications Magazine,2015,53(6):86-93.

[13] Xia M,A?ssa S. On the Efficiency of Far-Field Wireless Power Transfer[J]. IEEE Trans Signal Processing,2015,63(11):2835-2847.

[14] Kim B,Lee D,Choi T. Performance Evaluation for Modbus/TCP Using Network Simulator NS3[C]//2015 IEEE Region 10 Conference,2015:1-6.

[15] Djenouri D,Bagaa M. Energy Harvesting Aware Relay Node Addition for Power-Efficient Coverage in Wireless Sensor Networks[C]//IEEE International Conference on Communications,ICC,London,UK,2015:86-91.