小规模无线传感器网络的充电节点选取贪心策略

张青

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

0 引言

如今无线传感器网络应用于诸多领域，工业控制、智能家居、军事监测、恶劣环境监控以及健康监测等诸多领域，为大众提供了一种快捷而精确的监控环境。无线传感器网络是一种分布式的传感网络，通过部署的传感器节点感知外部的参数变化，节点之间以无线方式进行通信，同时还与互联网进行有线或无线方式的连接，从而形成了一个多跳自组织的网络。无线传感器网络的部署具有较高的可靠性、易于扩展、价格实惠等特点。纵观现有的无线传感器网络的应用，可以粗略划分为大规模无线传感器网络和小规模无线传感器网络两种。

在大规模无线传感器网络中，需要部署大量的无线传感器节点来监测很大的地理空间，因此，需要充电的无线传感器节点也较多，充电车数量也相应会增加。大规模无线传感器网络的充电调度变得更为复杂。本文针对大规模无线传感器网络的特点，考虑到大规模无线传感器网络通常会由区域划分的方式转化为小规模无线传感器网络，因此，本文着重考虑小规模无线传感器网络。本文将提出两种效率较为高效的节点选取贪心算法。

1 网络模型

出于对小规模无线传感器网络的考虑，本文从一个部署了30个传感器节点的无线传感器网络着手分析。假设该30个无线传感器节点随机部署在一个50m×50m的二维平面空间上，同时，为了保证传感器数据可以被较为便捷地传递到基站，本文考虑将基站部署在二维平面空间的中间位置。

图1为无线传感器网络图，通常，当一个传感器节点的剩余生命时间到了一定的阈值，例如，剩余电池容量的10%，该传感器节点便被称为待充电传感器节点。

为了便于对无线传感器网络进行研究，本文构建一个网络图G=( )V,E,h,l，其中，V是n个待充电传感器节点集合，E是待充电传感器节点的所有边，h(v)表示待充电传感器节点v需要被充的电量，l(u,v)表示待充电传感器节点u和v之间的欧几里得距离。

2 问题描述

本文研究的问题是基于小规模无线传感器网络中充电传感器节点的选取问题，并找到充电车的充电回路C。

为了提高传感器网络的充电效率，尽可能地充分利用充电车的电池电量，尽量减少网络中因能量耗尽而死亡的传感器节点，需要综合考虑传感器充电紧迫性、充电车在充电回路的行走距离L以及为充电车所充电量Q这三个因素。针对是否考虑传感器节点充电紧迫性这个因素，本文分别提出两个算法。

3 算法描述

传感器节点能力耗尽的话，将会无法工作，从而导致无法上传感应和传递信息。如上节所述，鉴于本文研究的是小规模无线传感器网络中传感器节点充电选取问题，因此，可以假定一辆充电车便可以满足一趟充电回路的需求。

为了充分考虑待充电传感器节点的剩余生命时间T和充电车的行走距离L，保证尽可能多的传感器节点处于工作状态。

如图2所示，本文考虑采用贪心算法来求该问题的最优解。假设在时刻t的待充电传感器节点为V(t)。

算法一考虑了传感器节点充电紧迫性这个因素，其参数模型为：

sum(Q)为充电车为待充电传感器节点所充的电量之和，即：

而sum(L)为充电车在行走途中的行走距离之和，

当充电回路C从0个节点开始，遍历未充电的传感器节点，找到使：

最大的节点v，加入充电回路C。

算法二则考虑充电车的行走距离L这个因素，

ratio=L

每次将加入距离上一次加入C中传感器最近的其他传感器节点加入充电回路C。

图1 无线传感器网络图

图2 充电车回路C节点选取

4 调度流程

两个调度算法的伪代码如下：

算法一基于紧迫性的充电节点选取贪心算法Sensor Selection Greedy Algorithm based on Urgence(SSGAU)

Input:网络模型G=(V ,E,h,l)

Output:充电回路C及耗费电量等

//每隔一段时间t进行一次待充电传感器节点V(t)的监测

算法二基于邻近算法的充电节点选取贪心算法Nearest Neighbor Sensor Selection Greedy Algorithm(NNSSGA)

算法一的主要过程在于遍历V(t)的过程中，实现贪心算法，即，找到ratio值最大的节点v作为下一个被充电的传感器节点，而算法二则是距离最邻近算法的扩展。

5 实验结果及分析

下面，本文采用仿真模拟实验进行验证。30个无线传感器节点随机部署在一个50m×50m的二维平面空间上，其他实验环境参数参考文献[1,2,3]中的随机模拟环境。

如图3和图4所示，在相同的实验环境中，对比本文提出的SSGAU算法、NNSSGA算法以及未采用调度算法的情况下的算法NONE、SSGAU算法和NNSSGA算法在充电车行走距离和充电回路耗费电量上均比算法NONE小。因此，本文所提出的这两种算法在充电传感器节点的选取问题上，效率更高。

图3 充电车行走距离

图4 充电车耗费电量

6 结语

本文提出了两种在小规模无线传感器网络中进行传感器节点的贪心选取的算法，并找到充电车的充电回路C，并通过模拟实验验证了该算法的有效性。

参考文献：

[1]W.Liang,W.Xu,X.Ren,X.Jia，X.Lin.Maintaining large-Scale Rechargeable Sensor Networks Perpetually Via Multiple Mobile Charging Vehicles[J].ACM Trans.Sensor Netw.(TOSN),vol.12,no.2,article no.14,May.2016.

[2]A.Kurs,A.Karalis,R.Moatt,J.D.Joannopoulos,P.Fisher，M.Soljacic.Wireless Power Transfer Via Strongly Coupled Magnetic Resonances[J].Sci.,vol.317,no.5834：83-86,Jul.2007

[3]Y.Shi,L.Xie,Y.T.Hou，H.D.Sherali.On Renewable Sensor Networks with Wireless Energy Transfer[M].in Proc.30th IEEE Int.Conf.Comput.Comm.(INFOCOM),2011：1350-1358.