可充电WSNs中基于效用最大化的数据收集方案

胡小平， 杨向萍

(东华大学 机械工程学院，上海 201620)



可充电WSNs中基于效用最大化的数据收集方案

胡小平， 杨向萍

(东华大学 机械工程学院，上海 201620)

利用无人机(UAV)到达传感器集群位置，然后采集数据并对相应集群的传感器充电。定义了数据收集效用函数，将数据收集问题描述为一种以数据收集效用最大化为目标的优化问题，并提出单边偏好匹配算法和基于双边偏好匹配的贪婪算法来解决上述问题。仿真实验表明:利用本文贪婪算法确定的UAV和传感器集群间的匹配关系可生成使数据收集效用最大化的最优解，且可实现传感器数据的高效收集。

无线传感器网络； 数据收集； 效用； 单边匹配； 贪婪算法； 最优解

0 引 言

在过去10年间，无线传感器网络(wireless sensor networks,WSNs)获得了人们的广泛关注[1]。数据处理和计算技术的进步，使传感器可以测量多种领域[2]中的数据(比如温度、压力、光照、湿度及红外线等)。但是电池技术进展缓慢，使电量有限的传感器受到严重的能量约束。此外，人们还希望利用WSNs对广大区域实现无人值守式观察。虽然传感器部署简单，但是使WSNs保持长时间运行，在大面积部署区域尤其是恶劣环境条件(比如高温沙漠、密林、雪山)下实现传感数据的高效收集，难度很大[3]。

为了避免传感器的能量消耗完，人们已经在之前文献中提出了多种能量节约[4]、环境能量利用[5]和增量部署算法[6]。然而，能量节约算法只能延缓能量被消耗的步伐，无法补充能量。对太阳能、风能和振动能等环境能量进行利用时，会受到这些能量可用性的约束，且这些能量的可用性往往不受人力控制。此外，部署的传感器节点可能会污染环境，因此增量部署算法对环境不够友好。

然而，无线能量传输技术在近期取得突破，为WSNs的传感器能量补充提供了一种有力途径。美国国家航空航天局(NASA)的电磁辐射实验[7]证明了能量远距离高效传输的可行性：在Goldstone网络实验中，NASA在1.5 km的距离上传输了34 000 W的能量，效率达到82 %。文献[8]利用一个无人机(unmanned aerial vehicle,UAV)携带充电设备，周期性地访问传感器集群，对传感器实施无线充电，进而使WSNs永久工作。文献[9]设计了一种移动式无线充电车，并通过实验验证了无线充电车在为WSNs补充能量方面的性能。虽然在这些创新性研究中，传感器能量得以补充，但WSNs将数据以多跳方式从数据源向Sink节点传输时仍然浪费了大量能量。此外，对于部署在恶劣环境中的传感器集群，无线充电设备到达这些区域并收集这些感应数据将会消耗大量时间和成本。

针对以上不足，本文利用无人机携带无线充电器，提出一种基于效用最大化的数据收集方案，并通过仿真验证了该方案的有效性。

1 网络模型

(1)

假设UAi及其匹配SCj间的距离为dij，UAi的速度为vi。考虑到UAV在被选传感器集群和Sink节点间的往返行程，UAV航行时间可表示为

(2)

如果一个UAV与多个集群相匹配，本文则假设UAV必须逐个从这些集群中收集数据。从当前集群中收集完数据后，UAV必须回到Sink节点处传输数据，然后再飞往下一个集群。

根据上节所示的网络模型，UAV的效用函数定义为

(3)

为了提高效用，UAV需要考虑UAi和SCj间的距离，SCjSink节点处汇聚的数据量，以及SCj中传感器的剩余能量。另外，设x表示N×M矩阵，该矩阵的第(i,j)个元素为xij={0,1}，表示本文中的匹配关系。如果xij=1，则第i个UAV与第j个集群相匹配;否则，它们不匹配。因为每个集群只能与一个UAV匹配，所以,本文有如下约束

(4)

为了实现感知数据的高效收集，本文试图确定传感器集群和UAV间的最优匹配对，以便使集群到UAV的数据传递速率最大化，同时保证这些集群中的传感器得到能量补充。因此，无线可充电传感器集群的高效数据收集问题可表示如下

(5)

2 本文算法

2.1 匹配定义

设有一个实例I表示一组UAVN={UA1,…,UAn}及一组传感器集群M={SC1,…,SCm}。实例I中的主体是M∪N中的UAV和传感器集群。可接受的UAV—SC匹配对为集合ε⊆N×M。每个UAVUAi∈N有一组可接受的传感器集群A(UAi)，其中A(UAi)={SCj∈M:(UAi,SCj)∈ε}。类似地，每个集群SCj∈M有一个可接受的申请人A(SCj)，其中,A(SCj)={UAi∈N:(UAi,SCj)∈ε}。本文将UAi和SCj的匹配关系定义如下：

定义1 匹配关系Φ为如下函数：Φ(UAi)∈M∪{∅}，且|Φ(UAi)|∈{0,1,…};Φ(SCj)∈N∪{∅},|Φ(SCj)|∈{0,1}，其中,Φ(UAi)=SCj且Φ(SCj)=UAi(i∈N,j∈M)。

在匹配理论中，本文中的主体(即UAV和SC)，需要一个偏好列表才能开始匹配过程。因此，本文在选择传感器集群进行能量补充和数据收集前，要求每个UAi根据自己相对所有集群的效用，形成一个降序排列的偏好列表。

2.2 单边偏好匹配算法

单边偏好匹配算法分为两步:1)计算UAV的效用函数;然后，构建降序排列的偏好列表UALISTi;同时构建一组未匹配的传感器集群UNMATCH。2)根据偏好列表UALISTi构建匹配关系。UAi向UALIST中层次最高的未匹配集群SCj做出申请，并将SCj从UNMATCH中移除。如果UNMATCH≠∅，则算法回到第2步开始时。算法不断进行匹配过程的迭代，直到UNMATCH为空集。

算法1：单边匹配算法

1)初始化

构建未被匹配的传感器集群列表UNMATCH;

2)匹配

for eachUAi,i∈Ndo

向之前从未拒绝过自己的最高等级SCj提出申请；

ifSCj∈UNMATCHthen

保存匹配对(SCj,UAj)；

将SCj从UNMATCH中删除；

else

拒绝做出申请的UAi;

end if

end for

ifUNMATCH≠∅ then

跳到第2步；

else

跳到第3步；

end if

3)算法结束

2.3 贪婪算法：双边偏好匹配

(6)

传感器集群也可以构建它们自己的偏好列表。然后，每个UAi∈N或每个SCi∈M均有一个按严格次序排列且互不相同的偏好列表。文献[10]提出一种可以始终找到稳定性匹配关系Gale—Shapley算法。本文以该算法为基础提出一种基于双边偏好匹配的贪婪算法，如算法2所示。

算法2：贪婪算法(双边偏好匹配)

1)初始化

构建未被匹配的集群组成的集合UNMATCH;

2)匹配

for eachUAi,i∈Ndo

向之前从未拒绝过自己的最高等级SCj做出申请；

ifSCj∈UNMATCHthen

保留匹配对(SCj,UAi);

将SCj从UNMATCH列表中删除；

else

比较新UAi′的等级Rank(i′)和SCLISTj中指定UAi的等级Rank(i)；

ifRank(i)>Rank(i′)then

拒绝新申请的UAi′;

else

保留新的匹配对(SCj,UAi′);

拒绝先前做出申请的UAi;

end if

end if

end for

ifUNMATCH≠∅ then

跳到第2步；

end of

ifUNMATCH=∅且部分UAi没有结束对所有集群的申请then

跳到第2步；

end if

3)算法结束

3 性能评估

3.1 仿真配置

3.2 结果和分析

图1给出了UAV数量固定时的仿真结果，此时传感器集群数量为25～40个，传感器集群分别部署于网格拓扑和随机拓扑结构上。从图1中可以发现，本文提出的贪婪算法的性能和最优匹配的性能一样，而单边匹配算法的性能远优于UAi(i∈N)和SCj(j∈M)的随机匹配算法。因为单边匹配算法考虑了UAV的偏好列表，每个UAi(i∈N)有机会向其UALISTi偏好列表中的最高级别SCj做出申请，所以,单边匹配算法的性能优于随机匹配算法。此外，贪婪算法的性能优于单边算法。在贪婪算法中，集群在构建偏好列表时的效用函数与UAV进行决策时的效用函数相同。SCj可拒绝向其做出申请的UAi，选择可显著提升系统效用的更为合适的UAV。

图1 不同算法的性能比较Fig 1 Performance comparison of different algorithms

图2给出了系统效用随网络规模的变化关系。当网络规模增加时，系统效用增加。此外，当网络规模增加时，贪婪算法与单边算法及随机匹配算法间的性能差异增加。这表明，当UAV的数量和位置固定时，相比于单边匹配算法和随机算法，本文贪婪算法更适用于大规模WSNs。

图2 系统效用随网络规模的变化情况Fig 2 System utilities varies with network scale

4 结束语

本文研究了如何使用UAV来高效收集部署于恶劣环境中的无线可充电传感器集群的感应数据。通过考虑无线能量传输的特点，将高效数据收集问题描述为多种约束条件下的优化问题。为了使上述问题中的系统效用最大，文中提出两种基于匹配理论的分布式算法。仿真实验结果表明:本文算法可实现感应数据的高效收集，同时可对恶劣环境中的传感器集群充电。

[1] 彭珍瑞,李 辉,董海棠,等.基于和声搜索的低延迟和低能耗无线传感器网络[J].传感器与微系统,2015,34(1):36-39.

[2] 吴腾飞,熊庆国,李文翔,等.方格拓扑无线传感器网络源路由策略的能耗分析[J].传感器与微系统,2014,33(10):36-39.

[3]ZhaoM,LiJ,YangY.Aframeworkofjointmobileenergyreple-nishmentanddatagatheringinwirelessrechargeablesensornetworks[J].IEEETransactionsonMobileComputing,2014,13(12):2689-2705.

[4]BouabdallahF,BouabdallahN,BoutabaR.Cross-layerdesignforenergyconservationinwirelesssensornetworks[C]∥IEEEInternationalConferenceonCommunications(ICC),Dresden,Germany:IEEE,2009:1-6.

[5]ParkC,ChouPH.Ambimax:Autonomousenergyharvestingplatformformulti-supplywirelesssensornodes[C]∥2012 9thAn-nualIEEECommunicationsSocietyonSensorandAdHocCommunicationsandNetworks(SECON),Seoul,Korea:IEEE,2012:168-177.

[6]PengY,LiZ,ZhangW,etal.Prolongingsensornetworklifetimethroughwirelesscharging[C]∥2010IEEE31stReal-TimeSystemsSymposium(RTSS),Rome,Italy:IEEE,2010:129-139.

[7]WangR,YeD,DongS,etal.Optimalmatchedrectifyingsurfaceforspacesolarpowersatelliteapplications[J].IEEETransactionsonMicrowaveTheoryandTechniques,2014,62(4):1080-1089.

[8]XieL,ShiY,HouYT,etal.Makingsensornetworksimmortal:Anenergy-renewalapproachwithwirelesspowertransfer[J].IEEE/ACMTransactionsonNetworking(TON),2012,20(6):1748-1761.

[9]ShiY,XieL,HouYT,etal.Onrenewablesensornetworkswithwirelessenergytransfer[C]∥2011ProceedingsoftheIEEEINFOCOM,Shanghai,China:IEEE,2011:1350-1358.

[10]GaleD,ShapleyLS.Collegeadmissionsandthestabilityofmarriage[J].TheAmericanMathematicalMonthly,2013,120(5):386-391.

Data gathering scheme based on utility maximization in rechargeable WSNs

HU Xiao-ping, YANG Xiang-ping

(School of Mechanical Engineering,Donghua University,Shanghai 201620,China)

Unmanned aerial vehicles(UAV) is employed to travel to the sites of sensor clusters,collect data,and recharge the sensors in corresponding clusters.Define utility function of data collection,formulate the data collection problem into optimization problem with objective of maximizing data collection utility,and one side p

matching algorithm and greedy algorithm based on two-side preferences matching are proposed to solve the above problems.Simulation experiments show that the matching between UAVs and SCs by the proposed greedy algorithm can yield the optimal solution in terms of data collection utility,and the data of sensor can be efficiently collected.

wireless sensor networks(WSNs); data gathering; utility; one side matching; greedy algorithm; optimal solution

2015—11—09

10.13873/J.1000—9787(2016)10—0052—04

TP 393

A

1000—9787(2016)10—0052—04

胡小平(1989-)，男，四川泸州人，硕士研究生,主要研究方向为无线传感网、机电一体化。