无线传感网络中的充电节点选取策略研究

曹先波

（四川大学计算机学院，成都 610065）

0 引言

近年来，无线传感器网络（Wireless Sensor Net⁃works，WSNs）受到了世界各国的广泛关注，特别是随着微电子机械系统（MEMS）技术的进步，促进了智能传感器的发展。这些传感器节点可以感知、测量和收集来自环境的信息，然后，基于某种局部决策过程，将感测到的数据发送给用户。由于应用场景不同，传感器也因此种类繁多，针对不同的感知信息，可以使用不同类别的传感器。感知的信息主要包括：湿度、温度、压力、强度等等信息。多数传感器主要是由传感器模块、处理器模块、能量供应模块和无线通信模块组成。传感器模块感知周围环境信息，处理器模块协调各个模块之间的工作关系，控制各模块工作模式。能量供应模块为传感器提供能量，保证传感器的正常运行。无线通信模块负责与其他传感器之间的通信工作，接收从其他传感器传输过来的数据，处理后发送给其他的传感器或基站。

无线传感器网络通常由多个传感器节点组成，共同监视一个区域，以获取有关环境的数据。无线传感器网络一般可分为两种类型：结构化和非结构化。在非结构化无线传感器网络中，传感器节点随机部署在需要监视的区域。部署以后，网络将以无人看管的方式执行监视和报告的任务。这种非结构化类型的无线传感器网络由于节点太多，网络维护（如连接管理和故障检测）会非常困难。在结构化无线传感器中，所有或部分传感器节点都是以预先计划的方式部署的。这使得结构化类型的无线传感器网络可以部署更少的节点，降低网络维护和管理成本。

在应用方面，无线传感器网络应用于军事目标跟踪和监视，自然灾害救济，生物医学健康监测、危险环境探索以及地震感应等多个领域。在军事目标跟踪和监视中，无线传感器网络可以协助进行入侵检测和识别。具体示例包括与空间相关且协调的部队和坦克运动。对于自然灾害，传感器节点可以感知并检测环境，以在灾害发生之前进行预测。在生物医学应用中，传感器的外科植入物可以帮助监测患者的健康状况。对于地震感应，沿着火山区域临时部署传感器可以收集地震和爆发的数据。

然而，目前无线传感器网络通过电池进行供电，电池能量有限这一特点使得网络的运行寿命受到限制。部分研究者[1-2]提出从环境中采集能量供传感器使用，例如：太阳能、风能等，以延长传感器的寿命。然而这种方式具有很大的不确定性，受到周围环境的严重影响。例如，使用太阳能为传感器供电将不得不受到天气的影响，太阳能的能量收集效率在雨天会比晴天达到数十倍差距。另外，随着无线能量传输技术的发展[3]，利用携带无线充电设备的移动充电小车为传感器节点补充能量，延长无线传感器网络的寿命的充电研究，吸引了很多学者。这种方式更加可控、高效且对环境的依赖性更低。本文针对小规模的无线传感器网络，提出两种移动充电小车的充电节点选取算法。

1 网络模型

在一个给定的二维平面上，随机部署N个传感器节点，这些传感器节点表示为s={s1,s2,…,sn} ，基站表示为s0。每个传感器节点si∈S都是由能量为bi的电池供电，i=1,2,…,N。传感器节点通过感应、接收和发送数据消耗能量，假定传感器si的能量消耗速率和剩余能量分别表示为eci和rei。传感器节点si和sj之间的距离为di,j，移动充电小车每移动一单元距离消耗c的能量。如图1所示，在一个充电周期中，移动充电小车从基站s0出发，沿着充电路径为传感器节点补充能量，最后回到基站s0为下一个周期做准备。过程中，移动充电小车的移动速度为v。本文研究了在小规模的无线传感网络中，传感器节点的选择问题，找到移动充电小车的充电路径C。

为了便于表述问题，本文将充电的网络模型构建成一个网络图G=(S,E,D)，其中，S是网络中的传感器集合，E是网络中传感器之间的边的集合，D是代表E的权重，即传感器之间的欧几里得距离。

图1

2 充电模型

在无线可充电传感器网络中，传感器装配能量有限且可以进行无线能量传输的电池，完成数据感应、数据收集和数据发送工作。为了能够保持网络正常且长时间的运行，需要及时为传感器补充能量，一种常用的做法是在网络中加入携带无线充电设备的移动充电小车为传感器进行无线能量传输。本文中，移动充电小车从基站出发，以恒定的速率移动到选取的传感器附近，通过无线能量传输为传感器补充能量。

移动充电小车离开基站，经过（s1,s2,…,sn），最后回到基站，于是移动充电小车的总行驶距离可以表示为：

3 能耗模型

传感器在网络中的能量消耗主要集中在数据感应、数据接收和数据发送方面，因此传感器si的能量消耗可以表示为：

其中，us是传感器感应一单位数据需要消耗的能量，ri是传感器si感应数据的速率。传感器si的数据发送消耗的能量表示为：

其中，N(si)表示在网络G中，传感器si的邻居传感器集合，是传感器si发送一单位数据给传感器sj所消耗的能量，fij是传感器si到传感器sj传输的数据量。对于传感器的数据接收的能量消耗可以表示为：

其中，ur是传感器接收一单位数据所需要消耗的能量，fji是传感器si接收来自传感器sj的数据量。

4 问题描述

本文研究了一个具有N个传感器的无线传感器网络中的传感器选取问题，最终得到移动充电小车的闭合充电回路C。为了提高移动充电小车所携带的电池能量，减少网络中的传感器节点因为能量耗尽而死亡，影响网络的性能。针对这两个方面的内容，本文提出了两个算法来进行讨论。

5 算法描述

在算法一（Sensor Selection Algorithm based on Ant Colony Optimization，SSAACO）中，为了尽可能提高移动充电消息的能量利用效率，需要减少移动充电小车的行驶距离，即式（1）所示。于是本文将充电小车的传感器选取问题转化为经典的TSP旅行商问题，构造最短的哈密尔顿环作为移动充电小车的行驶路径，以使路径最短，提高小车的能量利用效率。然而寻找到最短的哈密尔顿回路是NP难问题，所有可能的路径数量是n!，计算的时间复杂度非常高，无法在多项式时间内得到最优解。随着传感器的数量增多，基本上已经无法完成最优解的计算。为了在可接受的时间内找到结果，本文利用蚁群算法的优点，通过迭代的方式得到移动充电小车的最佳行驶路径。

在算法二中（Least Energy Sensor Selection Greedy Algorithm，LESSGA），文章考虑到有些传感器的能量比较少，需要及时补充能量。为了满足传感器的急迫性需求，本文利用贪心策略，当移动充电小车选取下一个传感器的时候，计算当前环境中所有传感器的能量状态信息，将能量最少的传感器作为下一个待充电传感器。传感器si的剩余能量可以表示为：

其中，rei是传感器si的剩余能量，tci是传感器si上次补充能量的时间，ti是移动充电小车到达传感器si的时间。ti可以表示为：

其中，μ是移动充电小车的能量传输效率，v是移动充电小车的移动速度。通过贪心策略，每次选取的传感器加入C中，最后得到移动充电小车的充电回路路径。

6 实验结果与分析

本文在这一小节利用仿真实验进行算法验证。10-30个传感器节点随机部署在50m×50m的二维空间，移动充电小车的移动速率是5m/s，能量传输效率是5W。每个传感器由3.7V/450mAh的碱性可充电电池供电，因此，传感器的最大电池容量为3,7V×0.45A×3600sec=6kJ，传感器的能量消耗随机分布在0.1J/s-1J/s之间。

图2

图3

仿真实验结果如图2和图3所示，对比了文章提出的SSAACO算法、LESSGA算法以及没有使用调度算法的None。如图2所示，随着传感器节点数量的增加，移动充电小车的路径相应增加。SSAACO算法能够为充电小车得到最短的行驶路径，且明显小于LESS⁃GA算法和None。在移动充电小车传输给传感器的能量方面，LESSGA算法每次寻找能量最少的传感器，使得整个充电周期时长最长，传输给传感器的能量也最多。

7 结语

本文介绍了在可充电无线传感器网络中，如何调度移动充电小车为传感器补充能量，传感器的选取问题。本文在针对希望减少移动充电小车的行驶路径方面和满足传感器的急迫性需求方面提出了两种算法，并最后通过模拟实验证明了算法的有效性。