可持续无线传感网络的节点能量补给的研究

尚光龙, 吕 争

(信阳职业技术学院数学与计算机科学学院,河南 信阳 464000)

0 引 言

随着电子通信技术的发展及普及，无线传感网络(Wireless Sensor Networks, WSNs)已被广泛使用[1]。但是由于WSNs内节点是微型设备，能量供给有限(一般是小容量的电池)。此外，WSNs网络常部署于野外的恶劣环境，当能量耗尽后，也不便于更换电池。这些特性加剧WSNs的能量问题[2]。目前，研究人员针对WSNs的能量问题提出不同的策略，但是这些策略多数属于能量效率问题，即是基于有限的能量，如何提高能量效率，并没有从根本上解决WSNs的能量问题。

从环境采集能量是解决WSNs问题的有效策略。即补给能量，而不是提高已有能量的效率。环境能量有电磁波、太阳能等[3-4]。基于这些能量供给的WSNs称为可持续WSNs。然而，若整个WSNs内全部采用具有能量采集的节点，增加了部署成本。因此，本文只在部分区域部署这些节点。具体而言，当某些节点原有电能消耗完尽，就在这些节点区域附近部署具有能量采集的节点，将这类节点称为能补节点(Energy-provided Node, EPN)。

换而言之，EPNs节点替换那些能量消耗殆尽的节点。考虑到EPNs的成本问题，在部署EPN时，希望EPNs的数目越少越好。因此，本文要解决的问题就是在保证网络连通的同时，如何部署EPNs。为此，先假定每个节点周期地向基站传输感测数据。同时，每个节点的从环境采集能量的能力不同，所采集的能量也不同。本文引用能量采集率表征节点对环境采集的能量。

为此，本文针对可持续WSNs，提出基于最小生成树的EPN部署算法(Minimum spanning Tree-based deploying ENPs algorithm, MST-DENP)。MST-DENP算法先基于节点的能量信息，计算每个节点权重，然后再结合Kruskal算法构建最小生成树，最后检测最小生成树内的非叶节点的能量，若能量过低，则就在这些节点区域部署ENP。

1 约束条件及能量模型

1.1 约束条件

网络内每个节点知道网络拓扑信息。假定节点周期地向基站传输自己所感测到的数据[5]，并且每个节点的能量采集率不同。此外，假定，每个节点所采集的能量能够完成它的基本任务。在每个周期T内，节点i所接收的数据Reci：

Reci=Biγi

(1)

其中Bi为节点i产生的比特数据，而γi表示节点i的支叶节点数，其定义如式(2)所示：

(2)

其中Ci为直系子节点数[6-7]。

网络内节点除了感测数据外，还得传输数据。节点i传输的数据为Tri，如式(3)所示：

Tri=Bi(γi+1)

(3)

1.2 能量采集模型

假定节点i的能量采集率表示为hi。网络内所有节点的能量采集率并不相同[8-9]。考虑到能量采集的稳定，本文选择利用无线电充电作为能量采集模型。之所以不选择太阳能、风能，原因在这于这些能量受环境变化大，不稳定。如太阳能存在强烈的时间周期性，中午太阳强烈，而午夜就无阳光。因此，引用无线电充电模型，便以控制。

具体而言，网络内节点利用无线信号充电，从基站发送的信号获取电能。文献[10-11]已分析无线充电的可行性。通过Beamforming技术获取能量。基站利用两个独立通道分别传输数据和能量。采用独立的通路，有利于避免数据传输与能量传输间的干扰。

Ehi表示节点i所采集的能量。ηhi表示能量效率，T是采集能量的时间。

Ehi=ηhiPt(di)-βξiT

(4)

其中Pt表示基站传输功率，β为路径衰落指数。而基站与节点i的欧式距离为di。而ξi表示路径衰落信道。

(5)

节点在完成感测、计算数据任务，需消耗自己的电能。假定在一个周期内节点所消耗的能量为Ei，其定义如式(6)：

Ei=ReciEr+TriEt+Ep

(6)

其中Ep为感测数据和计算数据任务所消耗的能量，而Er、Et分别表示接收、传输单比特数据所消耗的能量。

当节点消耗的能量小于所采集的能量时，节点就可以存活更长时间，如式(7)所示。若不满足式(7)，则表明节点能量处于快速消耗期，应需对其补给。

hiT≥Ei

(7)

其中hiT表示节点所采集的能量。

2 MST-DENP算法

MST-DENP算法利用Kruskal算法构建最小生成树，然后再检测最小生成树中非叶节点的所采集的能量是否满足式(7)所示。若不满足，则就在这些节点附近部署ENPs节点。MST-DENP算法的框架如图1所示。

图1 MST-DENP算法的框架

2.1 权益值

先依据节点所采集的能量给节点定义节点权益值。节点i的归一化权益值为：

ωi=(hmax-hi)/hmax

(8)

依据式(8)便可估算节点的权益值，且权益值越大，节点采集能量越少。此外，通过所有节点的权益值，可建立基于权益值的拓扑图(Vertex Weighted Graph, VWG)。

获取各点的权益值后，便可计算各边的权益值。每条边的权益值等于两端点权益值之和。假定节点υ和节点u所构成的边的权益值表示为Wu,υ：

Wu,υ=ωu+ωυ

(9)

为了更好地理解节点权益值和边权益值，进行示例分析。考虑图2(a)所示的网络结构，图中标识的数字表示该节点所采集的能量，如节点1所采集的能量h1=10。

然后，依据式(8)计算各节点的权益值，例如节点1的权益值ω1=(30-10)/30=0.66。图2(b)标出了各节点的权益值。

图2 具有节点值的网络拓扑图

再依据节点的权益值，计算各边的权益值。图3显示了各边的权益值。例如，节点1和节点5所构成的边的权益值等于0.66+0.33=0.99。

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

2.2 最小生成树

通过3.1节获取了各边权益值后，再利用Kruskal算法构建最小生成树。Kruskal算法将最小权益值的边加入最小生成树，然后在保持网络连通的前提下，再选择具有最小权益值的边加入，重复此过程，直到网络内所有节点均在树内，并保持网络连通。

图4 最小生成树

以图3为例，节点5共参与三条边，其中与节点2所构成的边的权益值最小，因此，节点5就向节点2传输数据。最终形成如图4所示的最小生成树。

2.3 部署EPN

本节分析如何依据最小生成树，寻找不满足式(7)的节点，进而在这些节点附近部署EPNs节点。换而言之，部署EPNs节点等于搜索不满足式(7)的节点，搜索过程如图5所示。假定R为满足式(7)的节点集，其初始值为空。

用无向图G=(V,E)表示网络拓扑图，其中V为节点集，而E为边集。假定3.1节构建的最小生成树表示为MST,并且以基站BS为根的最小生成树为(V,ε,BS),其中ε为支叶节点。

具体而言，先依式(8)计算各节点权益值，然后再计算各边权益值，并形成边权益值矩阵W′。随后，构成最小生成树。若节点的所采集能量不满足式(7)，则就加入R。|R|表示需要部署的EPNs节点数。MST-DENP算法的目的就是在维持网络连通的前提下，最小化|R|。

图5 基于MST的构建R的过程

3 性能仿真

3.1 仿真参数

本小节利用NS3[13]仿真软件建立仿真平台，分析MST-DENP算法的性能。同时，选择文献[14]的MRA算法和文献[2]利用ILP推导的成本下限(记为ILP)作为参照，并进行比较。其中成本是指部署ENPs的节点数。部署的节点数越低，成本低少，性能越好。

仿真区域大小为100 m×100 m，节点数为N，并且从中随机一个节点为基站。节点初始能量为Einit=10 J。传感节点周期地产生数据包，并向基站传输，数据包大小为32 bytes。

3.2 数据分析

首先分析数据包传递率随节点数的变化情况，实验数据如图6所示。从图6可知，提出的MST-DENP算法的数据传递率高于MBA算法，且在节点数变化区间，保持90%的数据包传递率。原因在于：MST-DENP算法利用最小生成树部署ENPs，以最小成本，构建网络连通图，提高了数据包传递率。

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

接下来，分析成本随节点数N的变化情况，如图7所示。从图7可知，节点数的增加，提高了成本。原因在于节点数越多，出现低能量的节点数也就越多，部署成本自然也越高。相比于MBA算法，MST-DENP算法控制了部署成本。然而，与ILP相比，MST-DENP算法仍有改进的空间。

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

最后，分析网络密度对部署成本的影响，实验数据如图8所示。此处引用的网络密度是指节点参与平均边数。

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

从图8可知，网络密度的增加，降低了部署成本。这主要是因为网络密度越大，网络路径越多，数据传输路径可选择性越高，能量消耗也就越平均，这就降低低能量节点，最终控制了部署成本。与MBA算法相比，提出的MST-DENP算法有效地控制部署成本。

4 结 语

针对WSNs的能量问题，分析了可持续WSNs网络。利用无线电对低能量节点进行补给。依据节点能量采集计算各边权益值，并利用Kruskal算法构建最小生成树，最后利用最小生成树部署能量补给节点。实验数据表明，提出的MST-DENP算法降低了成本，并提出了数据包传递率。后期，将优化MST-DENP算法，进一步减少部署成本，使其性能逼近ILP性能。

：

[1] D. Yang, S. Misra, X. Fang, G. Xue, and J. Zhang.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] Z. Zheng, L. X. Cai, R. Zhang, and X. S. Shen.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.

[4] A. Chelli, M. Bagaa, D. Djenouri, I. Balasingham, and T. Taleb.One-step approach for two-tiered constrained relay node placement in wireless sensor networks[J]. IEEE Wireless Commun. Letters, 2016,5(4): 448-451.

[5] R. V. Prasad, S. Devasenapathy, V. S. Rao, and J. Vazifehdan. Reincarnation in the ambiance: Devices and networks with energy harvesting[J].IEEE Commun. Surveys and Tutorials, 2014,16(1): 195-213.

[6] A. Castagnetti, A. Pegatoquet, T. N. Le, and M. Auguin. A joint duty-cycle and transmission power management for energy harvesting wsn[J].IEEE Trans. Industrial Informatics,2014,10(2): 928-936.

[7] N. Michelusi and M. Zorzi. Optimal adaptive random multi-access in energy harvesting wireless sensor networks[J]. IEEE Transactions on Communications, 2015,63(4): 1355-1372.

[8] P. Zhang, G. Xiao, and H.-P. Tan. Clustering algorithms for maximizing the lifetime of wireless sensor networks with energy-harvesting sensors[J].Computer Networks,2013,57(14): 2689-2704.

[9] S. Misra, N. E. Majd, and H. Huang. Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks[J]. IEEE Trans. Computers,2014,63(12):23-33.

[10] K. Huang and V. K. N. Lau. Enabling wireless power transfer in cellular networks: Architecture, modeling and deployment[J].IEEE Transactions on Wireless Communications, 2014,13(2):902-912.

[11] K. Huang and X. Zhou. Cutting the last wires for mobile communications by microwave power transfer[J].IEEE Communications Magazine,2015,53(6): 86-93.

[12] M. Xia and S. A¨ssa. On the efficiency of far-field wireless power transfer[J].IEEE Trans. Signal Processing, 2015,63(11): 2835-2847.

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

[14] D. Djenouri and M. Bagaa. Energy harvesting aware relay node addition for power-efficient coverage in wireless sensor networks[C].in IEEE International Conference on Communications, ICC, London, UK, 2015: 86-91.