基于阿基米德螺旋的WSNs节点部署的能耗均衡算法*

郝小会,申玉霞,赵冬玲

(济源职业技术学院,河南 济源 459000)

无线传感网络WSNs(Wireless Sensor Netorks)[1]已广泛应用于各个领域,如环境、工业。然而WSNs遭受了较多不可避免的问题,如资源受限、随机部署。特别是节点能量受限问题。因此,在设计WSNs时应重点关注网络能量,进而最大化网络寿命[2-3]。

而网络内能量消耗率取决于节点的部署特性,而部署特性主要取决于应用环境。目前,有两类节点部署方案:随机部署和确定性部署[4]。随机部署常应用于物理环境难以接入的区域,如火山,地震区域等,常用直升飞机向这些区域散落节点[4-5]。而确定性部署是常应用于物理空间可接入的环境,如目标跟踪、城区监测。而在这些环境中,常通过人工部署节点[4]。

此外,簇技术被认为是保存能量的有效技术之一。将网络内所有节点划分多个簇,每个簇有一个簇头CH(Cluster Head),而簇内的其他节点称为成员节点MNs(Member Nodes)。MNs感测环境,然后将感测的数据传输至相关的簇头CHs。然后,由CHs融合数据,再向信宿(基站)传输数据。常采用周期地重建簇的策略,通过选择剩余能量较多的节点作为CHs,进而均衡网络能量,使得网络内所有节点能量消耗相近。除了保存能量方面的优势外,簇技术还可以减少信道竞争和数据包丢失率,这有利于提高网络吞吐量。

尽管簇技术在保存能量方面具有一定优势,但是若仅依靠簇技术是难以避免能量空洞问题。一旦发生遭遇能量空洞问题,网络寿命将受到影响。为此,研究人员从节点部署角度入手,并结合簇技术,避免能量空洞问题。

为此,本文首先分析能耗均衡在延长网络寿命方面的性能,并发现每一层的簇数以及簇成员数对网络寿命有重要的影响。然后,再提出基于阿基米德螺旋(Archimedes spiral)的节点部署方案AS-DBEC,通过有效地部署节点,提高了能量利用率,最终延长了网络寿命。实验结果表明,AS-DBEC方案在保存能量和网络寿命方面具有一定的优势。

1 系统模型

1.1 网络模型

考虑a×a方形的网络区域,且其由一系列的电晕覆盖[6-7]构成,如图1所示。假定信宿位于网络区域中心,并由信宿负责从传感节点收集数据。而传感节点以随机方式分布于不同层内。

图1 网络模型

整个网络划分为N层。因此,网络内存在N个簇。据此,离信宿最近的簇位于第1层Layer-1(第1类),而离信宿最远的簇位于第N层Layer-N(第N类)。最后,假定在第i层的节点有j个簇(j>1)。

假定网络为静态的异构网络,同时依据文献[8]将网络内所有节点划分许多簇,其中异构性是指节点的功能和电池容量的不同。所谓功能上的异构是指网络内节点为两类:成员节点MNs(非簇头节点)和簇头CHs。而在电池容量方面,MNs具有有限的电量,而CHs装备了更充足的电量。不失一般性,假定CHs位于它的簇中心[7]。

1.2 感测和通信模型

如果区域内的每个节点至少有一个活动MN覆盖[4],则认为此区域被覆盖。节点MN的感测区域半径为Rs。而通信半径为Rc。假定如果两个节点的欧式距离不超过Rc,则它们能直接交互消息。

1.3 能量模型

考虑文献[9]的一级无线电模型作为能量模型,其中节点能量主要由无线传输和接收方面上进行消耗。因此,忽略其他能耗因素。

在传输范围Rc内,传输n比特数据所消耗的能量etr(n,Rc)可表示为:

(1)

式中:et表示传输一比特数据所消耗的能量。相反,接收n比特数据所消耗的能量ere(n):

ere(n)=eelec×n=er×n

(2)

式中:eelec=er,其表示接收一比特数据所消耗的能量。

最后,融合n比特数据所消耗的能量eda(n)可表示为:

eda(n)=ea×n

(3)

式中:ea表示融合一比特数据所消耗的能量。

1.4 信道传播模型

引用瑞利衰落信道模型[7]描述CHs间和CH与信宿间的通信信道。假定发射器与接收器间距离为,信道增益可表示为:

h()/0)-ηξ=L(0)(/0)-ηξ

(4)

此外,本文认为:可靠接收信号可表述为Pr{erx≥τ}≥δr,其中erx为接收信号的能量,而τ是预定能量的阈值,δr为所需的链路可靠值。

1.5 网络寿命

本文规定,网络寿命是指从节点部署开始直至失效节点的比例超过一定门限值的时间[10]。当失效节点超过一定比例后,就无法提供网络覆盖和连通。所谓失效节点是指节点剩余能量少于预定值,且不能传输任何数据或接收任何数据。

2 问题描述

平衡能量消耗有利于网络寿命的提高。所谓平衡能量消耗是指网络内所有节点的能耗速度相同或相近。而本节的目的就是通过推导说明:可通过部署节点,平衡节点间的能量消耗。为后续的节点部署策略提供理论依据。

(5)

类似地,Layer-N层的第j个CH所消耗的能量ENj:

(6)

(7)

令eti表示为从Layer-i层第j个CH传输一比特数据 至Layer-(i-1)层第j个CH所消耗的能量,式(6)可以重写:

(8)

依据网络模型,处于Layer-i、Layer-(i-1)的两CH间的距离li:

(9)

接收单比特的能量消耗eri如式(10)所示:

eri=etiL(l0)(li/l0)-ηξ

(10)

此外,对于瑞利衰落信道[11-12],链路可靠要求可表述为:

(11)

依据式(11)可得:

(12)

依据最短路径协议,每条路径含有的最大链路数为N。因此,为了产生对路径可靠性的限制,即最小链路可靠值δp:

(13)

最后,处于Layer-i的第j个CH所消耗的能量为:

(14)

由于我们目的就是减少CH的能量消耗率,可建立式(15)所式的优化问题:

(15)

式中:ε为CH的初始能量。由于所有CHs的初始能量相同,式(15)可写成:

(16)

再利用线性规划问题定义式(16),如式(17)所示。

(18)

式(18)第1个约束项保证簇间流量;第2个约束项限制了在网络内规定时间所有MNs产生的数据是常数。而式(18)的第3个约束项保证了MNs和CHs的数量为非负数。

每一层的簇数以及每个簇的MNs数可通过优化问题进行解决。然而,每一层的单一CHs可能仍保持不平衡,并且这种不平衡也会产生能量空洞问题。消除能量不平衡问题的有效方式之一就是以预定位置部署MN和CH[4]。

文献[13]分析了消除能量空洞问题的研究工作。这些预定节点部署方案显示了在端到端时延、吞吐量、数据包丢失率方面均有重要的提高。

为此,考虑到电晕覆盖的网络模型,提出基于阿基米德螺旋(Archimedes spiral)的预定节点部署策略。电晕覆盖的图形与阿基米德螺旋相似,并且螺线的每条臂的距离相等,进而使得节点部署更趋于均匀化。

3 部署策略AS-DBEC

3.1 部署阶段

3.1.1 基于阿基米德螺旋的节点部署

首先,将螺旋定义为曲线,其从中心点放射,然后围绕此点旋转,并逐渐远离。一个阿基米德螺旋是一阶圆圈CT(Circular Turn)的曲线,且极方程为Rd=θB,其中Rd为半径距离、而θ为极角。B是一个实数,且其值为常数。

两个连续圆圈CT(Circular Turn)的距离可通过B进行计算。阿基米德螺旋的一个显著特点就是两个连续圆圈的距离等于2πB,如图2所示。

图2 基于阿基米德螺旋的节点分布

3.1.2 基于离散的阿基米德螺旋的节点部署

由于阿基米德螺旋是连续曲线,将它作为部署节点的函数。为此,将此连续曲线转换为离散形式,致使节点就部署于这些离散位置上。

首先,利用式(19)和式(20)建立离散曲线。

f(θk)=θkB

(19)

式中:θk∈[2(k-1)π,2kπ],且k=1,…,K。

式(19)中:k表示CT,而θk表示由第k个CT所覆盖的总角度。接下来,在每个CT内位置被指定的范围内,这些离散点需要被识别,进而才能部署传感节点。

据此,将θk分解为m个离散位置,再在每个离散位置上部署节点。θk的分解如式(20)所示。

θk(m)=[2(k-1)π+mφk]

(20)

式中:k=1,…,K。且对于每个k,m=1,…,2π/φk。

式(20)中:φk代表在第k个CT内两个相邻节点的角度差,如图3所示。在每个CT的m个离散位置部署节点时,可以从m=2π/φk位置开始,在m=1位置结束。

AS-DBEC算法的目的就是将阿基米德螺旋作为节点部署函数,致使它能近似地代表分层的网络区域(如图1所示)。为了实现这个目的,将分层的网络区域的Layer-i分解为多个子区域ωi×ωi,其中ωi=ri-ri-1。

AS-DBEC算法将每个螺旋作为一个簇,且这个螺旋的初始点为CH,而在每个CT的离散位置上部署MNs。

图3 部署CHs和MNs示意图

3.2 簇建立阶段

由于一层有多个簇,而任意层内的MNs数以及部署位置均为已知,因此,无需单独算法去产生CH。

依据阿基米德螺旋部署方案,部署了CH和MNs节点后,就形成了簇。形成簇的伪代码如表1所示。

表1 部署节点的伪代码

图3显示了大型网络区域由多个圆区域构成示意图。在每个子区域内,就依据式(12)和式(13)部署MN和CH。

许多现实生活应用,如火山监测和精细农业。这些应用都是利用直升飞机[5]或空中机器人按预定位置部署节点。考虑这些因素,提出的基于Archimedes spiral 部署节点算法是可行的,也具有一定的应用前景。

3.3 数据传输过程

假定每个MN的数据产生率为n bit/s。一旦部署节点后,每个MN就向它的簇头传输数据。然后由簇头融合数据,再向信宿(基站)传输数据。

显然,相比MN,CH承担了更多的数据压力。因此,CH的能量消耗速度更快。此外,CH在维护网络连通方面的角色比MN更重要。为此,本文着力关注CHs的能耗。

假定CH以最短路径向信宿传输数据。具体而言,处于Layer-i的CH从处于Layer-(i-1)层选择下一跳节点。为了保证最短路径,就选择离自己最近的节点作为转发节点。同样,处于Layer-(i-1)层的CH再从Layer-(i-2)层选择下一跳转发节点。此过程一重复,直到将数据传输至信宿。

4 性能仿真

4.1 仿真环境

本节利用MATLAB 7.0.1仿真软件建立仿真平台。同时考虑两个网络尺寸:5层和10层,且a=100 m。每层的节点数由式(20)的离散点决定。在仿真过程中,假定运行接收器/接收器无线电路所消耗能量eelec=50 nJ/bit,而获取可接收的信噪比(30 dB)的放大器eamp=10 pJ/(bit/m2)。其他的网络仿真参数如表2所示。

表2 仿真参数

从能量均衡和网络寿命方面分析AS-DBEC算法。选择每CH所消耗的能量ECR per CH(Energy Consumption Rate per CH)表述能量均衡。

为了分析AS-DBEC算法在延长网络寿命方面上的性能,选择基于能量均衡的簇算法EBCA(Energy-Balanced Clustering Approach)[7]和基于静态簇头的簇算法SHCS(Static-Head Clustering Strategy)[8]进行比较。

在仿真中,在实施EBCA时,与文献[7]类似,考虑均匀的圆形簇,且簇头部署于簇内中心,而MNs围绕簇头随机分布,仿真过程中,在5层内随机部署30个节点;在10层内,随机部署65个节点。而在部署SHCS方案时,考虑均匀的方形簇,且簇头位于方形区域中心,而MNs围绕CH,并按确定性部署,且形成网格拓扑,总。此外,AS-DBEC、EBCA和SHCS算法所考虑的网络模型为基于Corona的网络模型,如图1所示。

图4 能量均衡

4.2 数据分析

首先分析算法的能量均衡性能,实验数据如图4所示,其中图4(a)为5层网络结构、4(b)为10层网络结构。

首先,将图4(a)和图4(b)相比发现,网络层数的增加,提高了能量消耗。例如,在5层网络结构内,AS-DBEC算法的ECR per CH为62.48 μJ/s,而当网络结构达到10层时,AS-DBEC算法的ECR per CH为84.29 μJ/s。原因在于:网络尺寸的增加,提高了数据流量,导致了能耗的增加。

然后,在给定网络层次环境下,AS-DBEC算法的ECR per CH 随层数接收直线。这说明簇技术能够有效地均衡能量。而EBCA和SHCS算法的ECR per CH随层次数的增加,呈下降趋势。注意到,在Layer-1时,ECR per CH最大。这也说明离信宿最近的CH承担了更多数据转发任务。与EBCA和SHCS算法,提出的AS-DBEC算法的ECR per CH得到有效控制,且曲线平稳,这说明AS-DBEC算法在均衡CH的能耗具有较大的优势。

接下来,分析AS-DBEC算法的网络寿命,实验数据如图5所示,其中图5(a)为5层网络结构、图5(b)为10层网络结构。

图5 网络寿命

从图5(a)可知,与EBCA和SHCS算法相比,提出的AS-DBEC算法的网络寿命分别提高了28.57%和18.73%。原因在于:EBCA和SHCS算法遭受能量空洞问题。此外,AS-DBEC算法的网络寿命随层数变化曲线更为平坦,这也再一次说明,AS-DBEC算法的能耗更为更为均衡。

5 总结

本文针对无线传感网络的能耗问题,先分析了均衡能耗对网络寿命的影响,然后提出阿基米德螺旋的节点部署策略AS-DBEC。将阿基米德螺旋作为部署函数,并进行离散化,最后通过这些离散位置部署节点。实验结果表明,与同类算法相比,提出的AS-DBEC算法能够均衡簇头间的能耗,延长网络寿命。

[1] Chi Q,Yan H,Zhang C,et al. A Reconfigurable Smart Sensor Interface for Industrial WSN in Io T Environment[J]. IEEE Trans Ind Inf,2014,10(2):1417-1425.

[2] 范敏,谢思佳. 基于空洞模型的地理位置路由改进算法研究[J]. 传感技术学报,2012,25(11):1556-1561.

[3] Stine J A. Exploiting Smart Antennas in Wireless Mesh Networks Using Contention Access[J]. IEEE Wireless Commun,2016,13(2):38-49.

[4] Halder S,Ghosal A,Das Bit S. A Pre-Determined Node Deployment Strategy to Prolong Network Lifetime in Wireless Sensor Network[J]. Comput Commun,2011,34(11):1294-1306.

[5] Huang R,Song W Z,Xu M,et al. Real-World Sensor Network for Long-Term Volcano Monitoring:Design and Findings[J]. IEEE Trans Parallel Distrib Syst,2011,23(2):321-329.

[6] Shu T,Krunz M,Vrudhula S. Power Balanced Coverage-Time Optimization for Clustered Wireless Sensor Networks[C]//Proc ACM Mobi Hoc,2015:111-120.

[7] Shu T,Krunz M. Coverage-Time Optimization for Clustered Wireless Sensor Networks:A Power-Balancing Approach[J]. IEEE/ACM Trans Netw,2012,18(1):202-215.

[8] Darabkh K A. Performance Evaluation of Selective and Adaptive Heads Clustering Algorithms over Wireless Sensor Networks[J]. J Netw Comput Appl,2014,35(6):2068-2080.

[9] Li H. COCA:Constructing Optimal Clustering Architecture to Maximize Sensor Network Lifetime[J]. Comput Commun,2013,36(3):256-268.

[10] Stine J A. Exploiting Smart Antennas in Wireless Mesh Networks Using Contention Access[J]. IEEE Wireless Communication Mag,2016,13(2):38-49.

[11] Wang X,Tan M. A Load-Balancing Routing Algorithm for Multichannel Wireless Mesh Networks[J]. IJSNet,2015,17(4):249-255.

[12] Diab R. Chalhoub G,Misson M. Enhanced Multi-Channel MAC Protocol for Multi-Hop Wireless Sensor Networks[J]. IEEE Wireless Days,2014,5(6):34-41.

[13] Halder S,Das BitC S. Enhancement of Wireless Sensor Network Lifetime by Deploying Heterogeneous Nodes[J]. J Netw Comput Appl,2014,38(2):106-124.