尚光龙, 吕 争
(信阳职业技术学院数学与计算机科学学院,河南 信阳 464000)
随着电子通信技术的发展及普及,无线传感网络(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。
网络内每个节点知道网络拓扑信息。假定节点周期地向基站传输自己所感测到的数据[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)
假定节点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表示节点所采集的能量。
MST-DENP算法利用Kruskal算法构建最小生成树,然后再检测最小生成树中非叶节点的所采集的能量是否满足式(7)所示。若不满足,则就在这些节点附近部署ENPs节点。MST-DENP算法的框架如图1所示。
图1 MST-DENP算法的框架
先依据节点所采集的能量给节点定义节点权益值。节点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 基于边权值的网络拓扑图
通过3.1节获取了各边权益值后,再利用Kruskal算法构建最小生成树。Kruskal算法将最小权益值的边加入最小生成树,然后在保持网络连通的前提下,再选择具有最小权益值的边加入,重复此过程,直到网络内所有节点均在树内,并保持网络连通。
图4 最小生成树
以图3为例,节点5共参与三条边,其中与节点2所构成的边的权益值最小,因此,节点5就向节点2传输数据。最终形成如图4所示的最小生成树。
本节分析如何依据最小生成树,寻找不满足式(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的过程
本小节利用NS3[13]仿真软件建立仿真平台,分析MST-DENP算法的性能。同时,选择文献[14]的MRA算法和文献[2]利用ILP推导的成本下限(记为ILP)作为参照,并进行比较。其中成本是指部署ENPs的节点数。部署的节点数越低,成本低少,性能越好。
仿真区域大小为100 m×100 m,节点数为N,并且从中随机一个节点为基站。节点初始能量为Einit=10 J。传感节点周期地产生数据包,并向基站传输,数据包大小为32 bytes。
首先分析数据包传递率随节点数的变化情况,实验数据如图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算法有效地控制部署成本。
针对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.