带无线能量补充设备的无线传感器网络基站部署策略

王丁玎,丁 煦,赵 冲,石 雷,韩江洪

(合肥工业大学 a.工业与装备技术研究院; b.计算机与信息学院,合肥 230009)

0 概述

随着无线通信技术和传感器制造技术的快速发展,无线传感器网络(Wireless Sensor Network,WSN)应用受到越来越多的关注[1]。然而WSN中每个传感器节点的能量有限且不能轻易地进行能量补充,进而存在网络寿命问题,其解决方案分为两类。第1类方案是能量智能消耗,相关研究有能量感知数据路由协议[2-4]、MAC控制协议[5]、占空比机制和跨层协议[6]及各种以节省能量为目的的路由算法[7-8]。文献[4]采用基于太阳能补充能量的无线传感器网络,将节点能量补充与节能路由相结合,在分簇网络的基础上利用神经网络模型预测太阳能。该路由协议使得链路上能量剩余消耗较多及预测太阳能的收集能力较强的节点成为簇头节点。文献[7]提出一种非均匀分簇路由算法来提高网络的连接性,降低能量损耗。文献[8]提出一种分布式的链式路由方案,为平衡节点之间的距离,将网络整个区域划分为相等大小的子区域。使用与最小生成树算法相似的算法将每个子区域中的节点连接到一条链中,包含链的子网通过网桥节点连接,使得节点之间最大距离缩短,网络寿命也相应提高。第2类方案是从环境中获取能量[9-10]。研究人员设计了不同的辅助设备,帮助传感器节点从太阳、风、潮汐、地震波和环境无线电中获取能量。文献[11]使用能量收集源和中继节点为两跳网络的稳定区域提供了内边界和外边界。然而,由于天气条件的波动,从环境中收集的能量并不稳定。

近年来,通过无线能量传输设备补充传感器节点能量为解决传感器节点能量受限问题提供了新的思路。无线能量传输技术在过去的几十年得到快速发展。许多日常家用电器如电动牙刷和清扫机器人采用归纳方法获得能量。能量传递的传统归纳方法需要线圈之间的距离尽可能接近,并且为了确定特定的位置,线圈之间的对齐也很严格。文献[12]通过强耦合磁场实现了无线能量传输。该远程传输能量的方法[13]具有相同磁共振频率的传输者和接收者之间的能量转移效率非常高,能量转移可以在中等距离下实现,可通过安装中继器进一步扩展传输范围,且能量转移没有辐射却有很强的方向性。这些特性为传感器节点的长距离供电提供了保障。文献[14]开发了一个数据遥测装置,可以通过无线能量传输技术实现远程充电。然而,无线能量传输技术也出现了新的挑战。文献[15]研究带无线能量传输设备的无线传感器网络处理方法。文献[16]提出一种移动式能量补充策略,移动节点可以在为传感器节点补充能量的同时收集数据,有效提高充电效率和网络生存期。

本文主要研究带有远程能量补充设备的无线传感器网络基站部署策略及其对网络协议的影响。在大型传感器网络中的基站部署也是优化网络性能的关键因素,不同的基站部署策略将影响传感器节点的寿命、数据路由方案等。本文通过聚类传感器节点并计算每个区域中传感器节点的通信量来确定基站位置坐标,并以最大化无线能量补充设备的驻站时间比为目标建立跨层优化问题。通过求解优化问题实现兼容的通信协议,得到传感器节点和远程能量补充设备的最佳配置策略。

1 带无线能量补充设备的WSN工作场景

本文研究部署在二维空间的传感器网络。在区域F中放置了N个传感器节点。假设所有传感器节点都是同类的,这意味着每个传感器节点能够收集信息并转发播收集到的数据返回至基站。无线能量补充设备在传感区域F中漫游时,会对每个传感器节点补充一定的能量。设备给传感器节点的能量补充保证不会因为能源供应不足而发生故障。在完成充电任务后,设备将在服务站S接受维修,例如机械检验等。

假设每个传感器节点的初始能量用Emax表示,维持适当功能的传感器节点的最低能量用Emin表示。数据路由方案用{Rij(t),RiB(t)}表示。Ri*(t)表示传感器节点在时隙t的数据传输速率,*代表基站B或其他传感器节点。pi(t)表示传感器节点i在时隙t的使用电量。用于远程充电传感器节点的电量表示为U,充电传感器节点i所花费的时间表示为τi。当完成充电任务时,充电设备将在服务站S驻留一段时间τS。假设充电设备的速度为V,单位为m/s,沿着路径遍历所花费的时间表示为τP,P是充电设备的遍历路径。πS表示服务站S的位置,πi表示沿着遍历路径的第i个传感器节点的位置。

2 基站部署

基站位置会影响整个网络的数据流和传感器节点通信能量的使用,甚至无线传感器网络的性能。在处理基站位置问题时,应考虑传感器节点的几何分布和数据传输速率。

2.1 最小封闭磁盘和基站的预部署

一般来说,基站可以放置在区域F的任何位置。然而,从节能角度来看,很难找到建立基站的合适位置。因此,候选区域可缩小到相对较小的区域,即为覆盖了区域F中所有传感器节点的最小封闭磁盘。

定理1无线传感器网络的基站应放置在覆盖所有传感器节点的最低封闭磁盘中,从而使向基站传输数据的整体用电量最小化。

由于要减少整体用电量,基站不应选择在最小封闭磁盘外,因此本文选择磁盘中心作为基站默认位置。

2.2 基站位置部署

基站位置部署问题可以进一步划分为两个子问题。第1个子问题是将传感器节点划分为多个区域。在一般情况下,传感器节点通常被认为是均匀分布在传感区域中。均匀分布反映了在传感区域的任何位置有“相等的利益”。然而,实际上传感器节点不可能在整个传感区域均匀分布。与二八定律相似,更多的注意力要放在相对小的区域和不稳定的设备上,如火山地区和易燃的货物,这些将导致传感器节点分布的不平衡。因此,基站位置应根据传感器节点的分布状况做相应调整。

2.2.1 基于混合高斯模型的传感器节点聚类

解决该极大似然估计问题的算法具体如下:

1)对于每个i和j,令:

2)计算下面参数:

2.2.2 基站位置确定

(1)

3 带无线能量补充设备的WSN基站部署

3.1 跨层优化问题建模

本文构建一个带充电设备的无线传感器网络跨层模型。该模型同时考虑物理层通信用电和网络层数据路由。对于数据路由问题:

(2)

对于通信用电问题:

(3)

每个传感器节点的能量应不低于保证不出故障的Emin,而且应不超过Emax。

Emin≤ei(t)≤Emax

(4)

其中,ei(t)是在时隙t时传感器节点i的剩余能量。本文中整个无线传感器网络的工作过程是由一系列的工作周期组成,每个周期的长度用τ表示,传感器节点i的剩余能量在每个周期的开始和结束时应该相等。

(5)

其中,τi是充电传感器节点i所花费的时间。式(2)～式(5)代表无线传感器网络的能量消耗与补充模型。在一个充电周期内,充电装置的运动时间可以通过下式进行描述:

(6)

其中,P是充电设备的遍历路径,DP是遍历路径的长度,V是移动速度,τP是沿着遍历路径漫游所消耗的时间。每个周期的长度τ可计算为:

(7)

其中,τS是充电装置在服务站接收维修的驻留时间。

3.2 OPT-1线性化

本节将把OPT-1问题转化为线性规划问题。

属性1在每个充电周期内,当充电设备完成充电任务时,每个传感器节点的剩余能量达到高峰;当充电设备停止时,剩余能量落在底部。

属性2如果充电设备在每一个充电周期内对每个传感器节点进行完全充电,则OPT-1保持最优。

定理2如果使充电设备在每个充电周期尽可能长时间地驻留在服务站,则充电设备最好的遍历路径是连接所有的传感器节点和服务站的最短回路。

定理3如果将整个充电周期分成N+ 1个阶段并保持传感器节点在每个阶段的配置策略不变,则仍可以计算得出最优解。

属性和定理的详细证明过程见文献[12]。

根据属性1和属性2,约束式(4)可被重写为:

(8)

其中,ti表示到达传感器节点i的时间。

根据定理2和定理3,约束式(2)可被重写为:

m=0,1,…,N

(9)

约束式(3)可被重写为:

m=0,1,…,N

(10)

约束式(5)和式(7)可被重写为:

(11)

(12)

对于约束式(8):

Emax-Emin≥Uτi-pi[i]τi

(13)

约束进一步转换为:

m=0,1,…,N

(14)

(15)

(16)

(17)

4 仿真结果与分析

4.1 50个传感器节点的仿真结果

如图1(a)所示,本节仿真基于含有50个传感器节点的传感器网络。所有传感器节点的最小封闭磁盘如图1(b)所示,圆心坐标为(963 m,909 m)。默认基站位置由一个带十字的圆表示。连接所有传感器节点和坐落在(500 m,500 m)的服务站S的最短回路问题可以使用由加拿大滑铁卢大学开发的Concorde软件进行处理。每个节点的位置和数据传输速率如表1所示。最短回路如图2(a)所示。经过混合高斯算法运行后,传感器节点聚类成三部分。在不同部分的传感器节点利用不同符号表示,并通过不同方法得到不同区域的中心,由图2(b)中的空心圆表示,基站最终的位置由图中★符号表示,坐标为(923 m,929 m)。

图1 传感器节点位置分布及其最小封闭磁盘1Fig.1 Distribution of sensor nodes and its smallest enclosed disk 1

表1 传感器节点位置和数据传输速率1Table 1 Location of sensor nodes and data transmission rate 1

图2 能量补充设备的充电路径及传感器节点分类结果1Fig.2 Charging path of the energy replenishing device and classification result of sensor nodes 1

当基站的最终位置为(923 m,929 m)时,通过求解线性最优化问题OPT-2得到目标值ζs为57%,与基站默认位置(963 m,909 m)时得到的49%的结果相比有了较大提升。在这两种情况下的充电周期分别为16 432 s和16 242 s。基站位于(963 m,909 m)和(923 m,929 m)时的充电时间如表2、表3所示。另外,可以通过R变量的输出获得不同时段的路由信息。

表2 基站位于(963 m,909 m)时传感器节点充电时间Table 2 Charging time of the sensor node when the base station is located at (963 m, 909 m) s

表3 基站位于(923 m,929 m)时传感器节点充电时间Table 3 Charging time of the sensor node when the base station is located at (923 m, 929 m) s

传感器节点在时段1和时段2的路由策略分别如图3(a)和图3(b)所示,其中,小圆代表节点,直线代表传输链路,大圆表示路由不同。因为基站位置是由传感器节点的分类情况决定,所以不同的分类情况将导致不同的基站位置,进而影响传感器网络优化结果。下文将讨论不同分类方法和分类数目对优化结果的影响。机器学习中的聚类算法有很多,包括混合高斯聚类、K-means聚类等,使用不同聚类算法对传感器节点进行聚类可能产生不同的结果。使用K-means算法对上述传感器节点进行聚类的结果如图4所示,根据基站位置策略得到最终基站位置为(849 m,970 m),如图中★符号所示。

图3 传感器节点在时段1和时段2的路由策略Fig.3 Routing strategies of sensor nodes in period 1 and period 2

图4 K-means聚类算法的传感器节点分类与基站最终位置

Fig.4 Classification result of sensor nodes and the final position of the base station obtained by K-means clustering algorithm

当基站的最终位置为(849 m,970 m)时,通过求解线性最优化问题OPT-2可以得到目标值ζs为60%。由于传感器节点的分类数量也会影响基站的位置部署,进而影响整个优化结果,因此本文选取分类数量为3～5。上文已讨论过传感器节点分成3类时的情况,下面将分析传感器节点分成4类和5类时的情况并将结果作对比。通过混合高斯聚类算法将传感器节点分为4类和5类的结果如图5(a)和图5(b)所示,得到最终的基站位置分别为(875 m,974 m)和(891 m,1 003 m),如图中★符号所示。

图5 混合高斯聚类算法的传感器节点分类与基站最终位置

Fig.5 Classification result of sensor nodes and the final position of the base station obtained by hybrid Gaussian clustering algorithm

当基站的最终位置为(875 m,974 m)时,通过解决线性最优化问题OPT-2可以得到目标值ζs为62%,比按传感器节点分为3类来确定基站位置时的结果有所提升。当基站的最终位置为(891 m,1 003 m)时,通过求解线性最优化问题OPT-2可以得到目标值ζs为64%,比按传感器节点分为4类来确定基站位置时的结果又有所提升。仿真结果可初步证明适当增加传感器节点的分类数目对优化基站部署位置有重要作用。

4.2 100个传感器节点的仿真结果

如图6(a)所示,本节仿真基于含有100个传感器节点的传感器网络。所有传感器节点的最小封闭磁盘如图6(b)所示,其圆心坐标为(1 050 m,1 068 m)。默认的基站位置由带十字的圆表示。每个节点的位置和数据速率如表4所示。最短回路如图7(a)所示。当应用混合高斯聚类算法后,将传感器节点聚类成4个部分,通过不同符号表示。这些传感器节点的主要方向与4个矩形的相邻边平行。通过本文方法得到的不同区域的中心,由图7(b)中的空心点表示,基站最终的位置如图中★符号所示,坐标为(1 143 m,943 m)。通过解决线性最优化问题OPT-2可以得到目标值ζS为46%,这与通过文献[15]得到的26%的结果相比约提升了75%。在这两种情况下的充电周期分别为19 000 s和14 871 s,充电时间如表5和表6所示。

图6 传感器节点位置分布及其最小封闭磁盘2Fig.6 Distribution of sensor nodes and its smallest enclosed disk 2

表4 传感器节点位置和数据传输速率2
Table 4 Location of sensor nodes and data transmission rate 2

编号位置/mRi/(kb·s-1)编号位置/mRi/(kb·s-1)1(76,1 098)4168(833,717)3712(662,257)946︙︙︙3(641,274)88996(537,1 611)5244(1 585,572)59597(1 817,1 436)1535(1 690,859)66098(744,504)7146(871,760)62899(1 589,1 518)1387(1 750,760)287100(811,401)164

图7 能量补充设备的充电路径及传感器节点分类结果2Fig.7 Charging path of the energy replenishing device and classification result of sensor nodes 2

表5 文献[15]传感器节点充电时间

Table 5 Charging time of sensor nodes in Literature [15]s

编号充电时间编号充电时间10.1780.1820.17︙︙30.399610.4040.13970.97511.709855.6660.45990.2470.101001.10

表6 本文传感器节点充电时间

Table 6 Charging time of sensor nodes in this papers

编号充电时间编号充电时间10.0780.0720.21︙︙30.269613.5840.12970.1254.229871.6161.98990.0371.131001.31

5 结束语

本文设计带有无线能量补充设备的无线传感器网络基站部署策略。利用混合高斯聚类算法将传感器节点划分为不同区域,根据聚类中心和区域内传感器数据密度确定基站部署位置,使基站偏向于数据传输速率较大的区域。同时,针对基于无线能量补充设备驻站时间比的优化问题,在采用最短Hamilton回路遍历传感器网络中所有节点的前提下,通过线性化方法将原优化问题转化为具有等优性的线性规划问题进行求解。仿真结果验证了本文基站部署策略的有效性。后续将研究高效节能的多移动基站数据收集算法,进一步优化无线传感器网络性能。