多跳无线可充电传感器网络中谐振中继器部署方法*

吴 渊， 冯 勇， 郭 磊， 杨 心

(昆明理工大学 云南省计算机技术应用重点实验室，云南 昆明 650500)

0 引 言

无线传感器网络中节点受成本、体积等因素的限制，为其配置的电池容量有限[1，2]，能量问题是限制无线传感器网络生存周期和性能的最主要因素。当前发展的无线充电技术被普遍认为是突破无线传感器网络能量限制的最具前景的技术，无线可充电传感器网络(wireless rechargeable sensor networks,WRSN)应运而生，许多卓有成效的方案[3,4]被提出。根据所采用无线充电技术的不同，WRSN能量补充方案可以分为单对单和单对多充电两种类型。单对单充电方案简单灵活，但是一次只能给一个节点充电，存在着充电效率不高、充电距离受限等方面的问题。单对多充电方案[5,6]可以同时给网络中多个节点充电，且利用谐振中继器可以实现多跳充电，可显著延伸充电距离、提高网络的能量补充效率。目前的WRSN单对多充电方案[9～11]中,每个传感器节点上都配备一个谐振中继器，利用移动充电装置(mobile charger,MC)移动到合适的位置(即锚点)以单跳或多跳方式同时给多个传感器节点补充能量。

文献[7]利用相邻的正六边形单元格平等分割网络，传感器节点被覆盖在单元格内，MC周期性移动到单元格中心位置来实现能量的多跳无线传输。文献[8]提出了一

种多跳充电模型，证明能量中继4～5跳可以实现50 %以上的充电效率。文献[9]提出了能量可以同时传输给多个充电请求节点，证明了MC给多个节点充电的总输出效率比给单个节点充电的总输出效率更高。文献[10]针对节点的稀疏部署和密集部署分别提出了不同的解决方案。节点稀疏部署的方案是利用虚拟节点作为无线能量路由器，运用多跳无线充电方式来提高能量的传输效率。在节点密集部署的方案中，传感器节点以瞄准线的方式实现能量的多跳传输。

以上多跳能量补充方法都是以传感器节点作为中继器，受节点部署密度以及MC有效充电距离的限制，网络中能够满足多跳能量传输的节点较为有限[11]，这在一定程度上影响了能量补充效率。为了改善以上问题同时兼顾经济性，本文提出了如何以最少的谐振中继器实现对WRSN中节点的完全多跳充电覆盖这一问题。在此基础上，给出了一种包括两个步骤的谐振中继器位置确定策略(repeaters location determination strategy,TRLDS)。首先使用蜂窝六边形分割网络以保证网络中节点的完全多跳充电覆盖，其次设计了一组规则以减少中继器数量并优化中继器位置，以实现用尽可能少的中继器对网络中所有节点的完全多跳充电覆盖，进而有效改善网络能量补充效率这一目标。

1 网络模型与问题定义

1.1 网络模型

本文将传感器节点(sensor node,SN)随机分布于二维平面区域中，传感器节点的数目为N，每个节点初始能量为Emax，能量阈值标记为Emin。如图1，整个网络由四种类型的成员组成：谐振中继器节点(repeater node,RN)，固定的基站(base station,BS)， MC，传感器节点构成。假设MC装有大容量电池和无线能量发送装置与接收装置，且具有智能通信、计算和移动的能力。MC可以在BS处通过休眠状态补充自身电量。

图1 网络模型

1.2 充电覆盖定义

假设1WRSN区域V=a×b，a，b为区域的边界大小；传感器节点集合定义为S={Si│0≤i

假设2所有谐振中继器节点集合定义为R={Rk│0≤k

假设3Rj的充电覆盖半径为L，传感器节点Si被Sj或中继节点Rk充电覆盖的概率为

(1)

式中Si为网络区域中第i个传感器节点；Um=Rk∪Sj，Rk为第k个中继器节点，Sj为第j个传感器节点，j≠i,d(Um,Si)为Si与Rk或Sj之间的距离。

传感器节点Si被多个中继节点联合覆盖的概率为ρ(R′,Si)=1-∏(1-ρ(Rk,Si))，R′={Rn-k,Rn-k+1,…,Rn-1,Rn}，R′⊆R。传感器节点Si被多个中继节点联合覆盖时，Si属于Rk的充电覆盖下的概率为

(2)

式中mark(i)为节点Si被中继节点Rk覆盖的标记。

完全多跳充电覆盖定义在给定的WRSN中，∃∀Si,Sj∈H，Rk,Rc∈R′，Um=Rk∪Sj。均∃ρ(Um,Si)=1或ρi(R′,Si)=1,ρJt(Rk,Si)=1恒成立，则称WRSN是完全多跳充电覆盖网络。

多跳充电覆盖率定义在WRSN中，∃H′={Si,Si+1,…,St}，H′⊆H。∃∀Sj∈H且Sj∉H′，Rk∈Z，其中i,j∈N，Um=Rk∪Sj,∃ρ(Um,Si)=1，ρJt(Rk,Si)=1成立，则t-i+2与N的比值称为多跳充电覆盖率。

2 谐振中继器位置的确定

2.1 谐振中继器均匀部署

为了在网络中均匀部署RN，需要研究网络中SN之间的连通性。假设RN的最大充电半径为R，网络中无线链路的边可以表示为Γ=(U,Z),U=H∪Z，Γ为传感器网络图，U为网络中节点的个数，H为传感器节点集合，Z为中继器节点集合。

网络中的边Eij满足以下条件

(3)

网络的连通性[12]为

(4)

基于网络的连通性，利用蜂窝六边形和两个SN的中点确定方法来分割网络。通过将RN均匀部署于正六边形的中心位置上，一方面考虑部署的公平性，另一方面考虑传感器网络的完全覆盖。

为了使RN在网络中合理部署，本文给出确定RN位置的证明。在WRSN中，为了计算网络中任意相邻的正六边形的中点坐标，假设存在任意相邻的3个正六边形，如图2所示，3个中点分别为R1=(x1,y1),R2=(x2,y2),R3=(x3,y3)。满足R1,R2,R3∈S，已知节点R2=(x2,y2)，目标是求解中继节点R1,R2的坐标。连接3个顶点可以得到3条边分别为d1,d2,d3∈E，A为3个正六边形的交点，过点R1画边d2的垂线交于点E，连接AR3。

图2 相邻正六边形RN确定

(5)

通过使用相邻蜂窝六边形来分割网络部署RN时，RN的数量较多，增加了网络的物理成本。该方案中存在RN覆盖一个或两个SN的情况，相对RN增加了部署成本的问题。由式(4)得，网络的连通性是确定RN位置的依据，同时决定着RN充电覆盖SN的数量。针对上述问题，本文假设在WRSN中，存在任意两个传感器节点S1和S2，当S1,S2之间的距离d∈[λ,2R](λ为S1,S2距离的阈值)时，由文献[13]，将原先覆盖S1,S2的RN部署在S1,S2的中间位置。该策略可以增加网络的连通性，提高RN的整体充电覆盖率，降低RN的部署成本。

2.2 谐振中继器具体部署过程

在WRSN中，多跳充电效率随着充电距离的增大而衰减，因此多跳充电的距离和跳数是有限的。通过部署RN可降低多跳充电的跳数，延长充电距离，实现网络的充电全覆盖。为了详细地阐述RN的部署过程，给出RN部署规则：

规则一根据多跳充电的有效距离，使用蜂窝单元格分割网络时，将RN部署于相邻单元格的中心位置。

规则二当单元格中仅充电覆盖两个传感器节点且两节点之间的距离在[λ,2R]范围内，由文献[13]，规定将RN位置调整于两个SN的中点位置。

规则三当中继节点Ri仅充电覆盖一个传感器节点Si时，若Si在相邻中继节点Rk的充电覆盖范围则重新标记该SN的mark值并删除冗余中继节点Ri。

规则四当中继节点Ri仅充电覆盖一个传感器节点Si时，若Si与相邻中继节点Rk覆盖的其他传感器节点之间的距离d均小于2R(R为RN的充电覆盖半径)，则重新部署Rk于d最大的两个传感器节点的中点位置并删除冗余的中继节点Ri。

规则五当RN充电覆盖一个SN时，任意两个单元格中SN之间的距离小于2R，则部署其中一个RN于这两个SN的中点位置并删除另一个单元格的中继节点。

规则六当中继节点Ri仅充电覆盖一个传感器节点Si时，若Si到相邻中继节点Rk覆盖的传感器节点Sj(距离Si最近)之间距离小于2R，则调整Ri的位置与Si,Sj的中点位置。

根据上述规则，结合图3给出以下具体RN部署方案。

图3 谐振中继器位置确定

1)判断所有tab=2的RN，根据规则二来调整RN位置。RN调整后的位置如图中五角星点的位置。

2)判断所有tab=1的RN位置，确定距离平面坐标原点最近的Ri(tab=1)。根据规则三来删除冗余的RN并将传感器节点重新标记(图中空心点位置)，否则判断是否满足规则四的调整方案,若是,则依规则四来调整RN位置，反之,依据规则五按照图中所示进行调整RN，若上述调整方案均不能解决RN覆盖一个节点的问题，则根据规则六来调整RN位置。若上述规则均不满足,则对RN的位置不进行任何处理。图3(e)中的RN位置由五角星点和三角形点组成。图3(f)中每个传感器节点都被标记过，空心圆为调整的传感器节点。星点为RN调整之后的位置。图中虚线为多跳充电覆盖连接线。

3 仿真与性能评估

本文通过仿真对比TRLDS与Cellular[7]来说明本文所提方案的有效性。本文主要工作是谐振中继器的位置部署以及优化工作，因此从以下指标评估本文所提方法的有效性。默认的仿真参数为：仿真区域为30 m ×30 m，传感器节点数量N为[25,200]，节点的初始能量E为10 000 units，工作状态的能耗Ew为10 units/s，休眠状态的能耗Es为1 unit/s，传感器范围为3 m，MC移动速度为3 m/s，目标节点速度1～ 5 m/s，仿真时间36 000 s，充电速率200 units/s。

3.1 多跳充电覆盖率

根据定义可知，若ρ(Um,S)=1成立，那么RN覆盖的节点数量是不同的。如图4(a)表示RN在数量不同下的多跳充电覆盖率的变化情况。当RN的充电覆盖半径为2 m时，可以看出RN数量在0～14之间变化，多跳充电覆盖率呈递增趋势。当RN数量为11时，TRLDS的多跳充电覆盖率达到1，而Cellular的多跳充电覆盖率为0.62。因此，在RN数量一定条件下，TRLDS的多跳充电覆盖率更高。如图4(b)表示RN不同充电覆盖范围下的多跳充电覆盖率的变化情况。当RN数量为8时，可以看出随着RN充电覆盖范围的变大，多跳充电覆盖率相继增大。在相同的条件下，可明显看出TRLDS的多跳充电覆盖率更高。

图4 不同条件下多跳充电覆盖率的性能对比

3.2 充电性能评估

在WRSN中部署RN条件下，图5(a)中充电成本表示MC为实现节点能量补充的总移动距离。从图中看出当节点数量小于125时，充电成本呈递增趋势，节点数量大于125时，充电成本呈递减趋势，这是因为随着节点数量的增多，节点死亡率变大，MC来不及给网络中请求充电节点充电导致移动成本降低。从图中可以看出TRLDS的充电成本更小。图5(b)中网络生存时间表示无线可充电传感器网络从开始运行到停止运行的时间间隔。从图中看出节点数量从25增加到200时，网络的生存时间呈递减趋势，这是因为随着节点数量的增多，MC来不及给目标节点充电而导致网络停止。通过对比说明，TRLDS在充电性能方面具有明显优势。

图5 布置算法在不同条件下的充电性能对比

4 结 论

本文探讨了在WRSN中合理部署谐振中继器以提高网络的充电效率问题。由于多跳无线充电效率受网络中RN位置和数量的影响，本文研究了RN部署问题，提出了一种包括两个步骤的RN位置确定策略—TRLDS，显著地延伸了移动充电装置的充电距离，从整体上提高充电效率。仿真结果表明该策略能够以一种较低成本的方式有效解决无线传感器网络中节点的能量受限问题，实现网络的可持续性运行。