RWSNs中基于效用最大化的数据收集方案研究

摘 要： 无线传感器网络在恶劣环境下的各种应用受到传感器电池的约束，且在数据收集方面存在多种困难。这里提出利用无线能量传输技术来补充传感器集群的能量，同时针对部署于恶劣环境下的无线可充电传感器集群提出一种高效的数据收集方案。面对恶劣环境，该方案利用无人机（UAV）到达传感器集群位置，然后采集数据并对相应集群的传感器充电。定义了数据收集效用函数，将数据收集问题描述为一种以数据收集效用最大化为目标的优化问题，并提出单边偏好匹配算法和基于双边偏好匹配的贪婪算法解决上述问题。理论分析和仿真实验表明，利用贪婪算法确定的UAV和传感器集群间的匹配关系可生成使数据收集效用最大化的最优解，且可实现传感器数据的高效收集。

关键词： 无线传感器网络； 数据收集； 单边匹配； 贪婪算法； 最优解

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）15?0008?06

Abstract： The various applications of wireless sensor networks （WSNs） are restrained by the sensor′ battery in severe environment， and the WSNs face various difficulties in data collection， so the wireless energy transfer technology used to replenish the energy of sensor cluster is proposed. Aiming at the wireless rechargeable senor cluster deployed in severe environment， an efficient data collection scheme is proposed. In the scheme， the unmanned aerial vehicle （UAV） is used to arrive at the site of the sensor cluster in severe environment， after that the data is collected， and the sensors corresponding to the cluster are charged. In this paper， the utility function of data collection is defined to describe the data collection problem as an optimal problem taking utility maximization of data collection as the target， and the greedy algorithm based on bilateral preference matching and unilateral preference matching algorithm are proposed to solve the above problems. The theoretical analysis and simulation experiment results show that the matching relation of UAV and sensor cluster determined with the proposed greedy algorithm can generate the optimal solution of making data collection utility maximum， and can realize the efficient collection of sensor data.

Keywords： wireless sensor network； data collection； unilateral matching； greedy algorithm； optimal solution

0 引 言

在过去10年间，无线传感器网络（Wireless Sensor Network，WSN）获得了人们的广泛关注[1?2]。究其原因，一方面是因为WSN部署简单，另一方面是因为在战场侦察、环境监测、生物观察等领域具有巨大的应用潜力[3?4]。数据处理和计算技术的进步，使传感器可以测量多种领域中的数据（比如温度、压力、光照、湿度及红外线等）。但是电池技术进展缓慢，使电量有限的传感器受到严重的能量约束。此外，人们还希望利用WSN对广大区域实现无人值守式观察。虽然传感器部署简单（比如通过飞机散播在广大区域上），但是使WSN保持长时间运行，在大面积部署区域尤其是恶劣环境条件下实现传感数据的高效收集（比如高温沙漠、密林、雪山），难度很大[5]。

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

无线能量传输技术在近期取得突破[10]，为WSN的传感器能量补充提供了一种有力途径。具体来说，文献[11]中提出了3种无线能量传输技术，即：感应耦合技术、电磁辐射技术及磁共振耦合技术，同时介绍了这些技术在WSN中的应用。美国国家航空航天局（NASA）的电磁辐射实验[12]证明了能量远距离高效传输的可行性：在Goldstone网络实验中，NASA在1.5 km的距离上传输了34 000 W的能量，效率达到82%。另外，无人机（Unmanned Aerial Vehicle，UAV）技术越来越成熟，成本也不断下降。在此背景下，文献[13]利用一个无人机携带充电设备，周期性地访问传感器集群，对传感器实施无线充电，进而使WSN永久工作。文献[14]设计了一种移动式无线充电车，并通过实验验证了无线充电车在为WSN补充能量方面的性能。虽然在这些创新性研究中传感器能量得以补充，但WSN将数据以多跳方式从数据源向Sink节点传输时仍然浪费了大量能量。此外，对于部署在恶劣环境中的传感器集群，无线充电设备到达这些区域并收集这些感应数据将会消耗大量时间和成本。针对以上不足，本文并不是使用无线充电车，而是提出使用无人机携带无线充电器（如图1所示），同时利用UAV选择传感器集群，飞往被选择的传感器集群，并对集群中的传感器进行充电，同时将这些集群中的感应数据传输给Sink节点。本文的主要工作如下：

（1） 提出利用携带无线充电传输设备的UAV收集部署于恶劣环境下的传感器集群的感应数据，同时对相应集群中的传感器补充能量。具体而言，本文根据UAV到传感器集群间的距离、从传感器集群收集到的数据以及集群内传感器的剩余能量，定义了数据收集效用函数，并将数据收集问题描述为以数据收集效用函数最大化为目标的优化问题。

（2） 提出单边匹配算法和基于双边偏好匹配的贪婪算法解决上述问题，并通过理论分析和仿真实验验证了利用本文贪婪算法确定UAV和传感器集群间的匹配关系可生成使数据收集效用最大化的最优解，且可实现传感器数据的高效收集。

1 网络模型

假设在感应/监测应用中，多个传感器集群部署于恶劣环境中。每个集群包括一个中央Sink节点和一组传感器，其中传感器将其感应到的数据周期性地发往Sink节点。为了补充传感器的能量损耗、收集传感器的感应数据，利用一个或多个UAV飞往传感器集群，对集群中的传感器进行充电，通过相应集群中的Sink节点收集传感器感应数据。网络模型如图2所示。

2 本文算法

下面以匹配理论为基础，提出两种分布式算法来获得上述问题的最优解。首先给出单边偏好匹配算法，然后根据文献[15]中的Gale?Shapley算法将单边偏好匹配算法扩展为基于双边偏好匹配的贪婪算法。最后通过理论分析证明了算法的正确性。

2.1 匹配定义

匹配理论主要是解决如何将一组不可分的物品分配给一组申请人。每个申请人可能有多种偏好。以上述匹配概念为基础，可将本文研究的数据收集问题阐述如下：

设有一个实例[I]表示一组UAV[N=UA1，UA2，…，UAn]及一组传感器集群[?=SC1，SC2，…，SCm]。实例[I]中的主体是[??N]中的UAV和传感器集群。可接受的UAV?SC匹配对为集合[ε?N×?]。每个UAV[UAi∈N]有一组可接受的传感器集群[AUAi，]其中[AUAi=][SCj∈?：UAi，SCj∈ε]。类似地，每个集群[SCj∈?]有一个可接受的申请人[ASCj，]其中[ASCj=][UAi∈N ：UAi，SCj∈ε]。本文将[UAi]和[SCj]的匹配关系定义如下：

定义1 匹配关系[Φ]为如下函数：

[ΦUAi∈???，]且[ΦUAi∈0，1，…；ΦSCj∈][N ??，][ΦSCj∈0，1，]其中[ΦUAi=SCj]且[ΦSCj=][UAii∈N， j∈?]。

该定义表明，如果函数的输入是[SCj，]则[Φ]是一个单对单匹配。另一方面，如果函数的输入是[UAi，]则[Φ]是一个多对单匹配。在匹配理论中，本文中的主体（即UAV和SC）需要一个偏好列表才能开始匹配过程。因此，本文在选择传感器集群进行能量补充和数据收集前，要求每个[UAi]根据自己相对所有集群的效用形成一个降序排列的偏好列表。

2.2 单边偏好匹配算法

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

3. 算法结束

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

第2.2节从UAV角度给出了单边偏好匹配算法。为了进一步提升系统效用，本文进行双边偏好匹配，即从UAV和传感器集群两个角度进行匹配。

传感器集群也可以构建它们自己的偏好列表。然后，每个[UAi∈N]或每个[SCj∈?]均有一个按严格次序排列且互不相同的偏好列表。

文献[15]提出一种可以始终找到稳定性匹配关系的Gale?Shapley算法。本文以该算法为基础提出一种贪婪算法。在第一阶段，它计算UAV和传感器集群的效用函数。然后，构建按降序排列的偏好列表[UALISTi]和[SCLISTj]。它还构建未匹配传感器集群组成的集合UNMATCH。根据偏好列表[UALISTi，][UAi]向[UALISTi]列表中之前从未拒绝过自己且层次最高的集群[SCj]做出申请。如果[SCj]还未被匹配，则保留配对[UAi，SCj]。如果[SCj]已经被匹配，则[SCj]检察新采用的[UAi]和上一次迭代时的[UAi]的等级。[SCj]与其[SCLISTi]列表中等级较高者匹配，排除另外一个。被拒绝的[SCj]添加到UNMATCH中，等待下一轮匹配过程。如果[UNMATCH≠?，]则算法回到第2步。即使[UNMATCH=?，]但[UAi]还没有结束对所有[SCj（j∈?）]的申请，则算法仍然回到步骤2。只有[UNMATCH=?]且每个UAV均申请过所有[SCj（j∈?）]时，算法才终止。

3.算法结束

2.4 理论分析

为了便于分析，下面首先给出了“最优匹配”的定义。

定义2 最优匹配：如果在约束条件[j∈?xij≤1]下，对匹配关系[Φ，]式[i∈Nj∈?UUAji]被最大化，则认为[Φ]为最优匹配。

以该最优匹配定义为基础，有如下理论：

定理1 贪婪算法获得的匹配关系[Φg]为最优匹配。

证明：如果对匹配关系[Φ，]在约束[j∈?xij≤1]下，式[i∈Nj∈?UUAji]最大化，则每个[SCj]必与其偏好列表中层次最高的[UAi]相匹配，现将其表示为[UAjf]。

假设[Φ]最优，但是至少有一个[SCj]不与其[UAjf]匹配。根据贪婪算法，在第一轮中，[SCj]与向其申请且等级最高的[UAi]匹配，现将其表示为[UAjrh]。在下一轮中，如果新申请的[UAjrh]级别高于[UAjrh，]则[SCj]将会与[UAjrh]匹配且[UAjrh]被拒绝。因此，发现[SCj]总是与UAV中级别最高且向[SCj]做出申请的UAV相匹配。每个[UAi]有一个偏好列表包括所有的[SCjj∈?]，这说明所有的UAV将会向各个[SCj]做出申请。于是，每个[SCj]均与其[UAjf]匹配，与至少有一个[SCj]不与其[UAjf]相匹配的结论相矛盾。所以，贪婪算法获得的匹配关系[Φg]是最优匹配。证毕。

3 性能评估

3.1 仿真配置

本文利用部署在10 km[×]10 km区域上的UAV和传感器集群进行仿真实验。电池容量为[emax=70 J，][SCj]中传感器节点的剩余能量为[ejk∈60，65 J]。每个集群中的传感器数量为[SCj∈50，100]。发射功率为[Si=1.2 W，]UAV的速度为120 km/h。对于其他参数，传感器的数据率从[1，10] Kb/s中随机生成。在网格拓扑和随机拓扑结构上分别进行了仿真实验，取20次仿真结果的平均值作为最终的实验结果。

3.2 结果和分析

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

图4给出了系统效用随网络规模的变化关系。当网络规模增加时，系统效用增加。此外，当网络规模增加时，贪婪算法与单边算法及随机匹配算法间的性能差异增加。这表明，当UAV的数量和位置固定时，相比于单边匹配算法和随机算法，本文贪婪算法更适用于大规模WSN。当网络规模增加时，受欢迎传感器集群的数量也在增加（在所有UAV偏好列表中均有较高等级的集群定义为受欢迎集群）。无论在单边匹配算法还是随机匹配算法，受欢迎集群均无法拥有其偏好列表。因此，传感器集群很可能做出非最优决策，降低系统效用。

图5给出了匹配决策和航行时间之间的关系。为便于讨论，这里只给出包含两架UAV的情况。采用贪婪算法确定UAV和集群间的匹配。星星表示UAV飞到每个集群处的时间，方形表示飞到与[UAi]相匹配的[SCj]处的航行时间，圆圈表示飞到未被匹配[SCj]处的航行时间，该时间至少比一个被匹配的[SCj]短。在图5中发现虽然部分集群与UAV较近，但它们未与任何UAV相匹配，这是因为匹配决策不仅与航行时间有关，还与充电时间和传感器集群的数据量有关。匹配关系并不只存在于相距最近的UAV和传感器集群间。此外，在图3中还发现最优算法的曲线与贪婪算法的曲线相吻合。仿真实验证明了贪婪算法确定的匹配关系是最优匹配这一结论。

4 结 语

本文研究了如何使用UAV高效收集部署于恶劣环境中的无线可充电传感器集群的感应数据。通过考虑无线能量传输的特点，将高效数据收集问题描述为多种约束条件（即UAV和集群间的距离，集群中Sink节点处汇集的数据量以及集群中传感器的剩余能量）下的优化问题。为了使上述问题中的系统效用最大，提出两种基于匹配理论的分布式算法，单边匹配算法和贪婪算法，同时证明贪婪算法最优。仿真实验验证了本文的理论分析结果，证明本文算法可实现感应数据的高效收集，同时可对恶劣环境中的传感器集群充电。在下一步工作中，将分析移动Sink条件下传感器节点无线充电与数据收集质量的关系，研究面向高效数据收集的移动Sink路径规划算法。

参考文献

[1] 李建中，高宏.无线传感器网络的研究进展[J].计算机研究与发展，2008，45（1）：1?15.

[2] 郭忠文，罗汉江，洪锋，等.水下无线传感器网络的研究进展[J].计算机研究与发展，2010，47（3）：377?389.

[3] 张豫鹤，黄希，崔莉.面向交通信息收集的无线传感器网络节点[J].计算机研究与发展，2008，45（1）：110?118.

[4] GUO S， HE L， GU Y， et al. Opportunistic flooding in low?duty?cycle wireless sensor networks with unreliable links [J]. IEEE transactions on computers， 2014， 63（11）： 2787?2802.

[5] ZHAO M， LI J， YANG Y Y. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks [J]. IEEE transactions on mobile computing， 2014， 13（12）： 2689?2705.

[6] BOUABDALLAH F， BOUABDALLAH N， BOUTABA R. Cross?layer design for energy conservation in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Communications. Dresden： IEEE， 2009： 1?6.

[7] PARK C， CHOU P H. AmbiMax： autonomous energy harves?ting platform for multi?supply wireless sensor nodes [C]// Proceedings of 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston： IEEE， 2006： 168?177.

[8] FAN K W， ZHENG Z， SINHA P. Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks [C]// Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems. Raleigh： ACM， 2008： 239?252.

[9] PENG Y， LI Z， ZHANG W， et al. Prolonging sensor network lifetime through wireless charging [C]// Proceedings of 2010 31st IEEE Real?Time Systems Symposium. San Diego： IEEE， 2010： 129?139.

[10] BEH T C， KATO M， IMURA T， et al. Automated impedance matching system for robust wireless power transfer via magnetic resonance coupling [J]. IEEE transactions on industrial electronics， 2013， 60（9）： 3689?3698.

[11] XIE L， SHI Y， HOU Y T， et al. Wireless power transfer and applications to sensor networks [J]. IEEE wireless communications， 2013， 20（4）： 140?145.

[12] WANG R， YE D， DONG S， et al. Optimal matched rectifying surface for space solar power satellite applications [J]. IEEE transactions on microwave theory and techniques， 2014， 62（4）： 1080?1089.

[13] XIE L， SHI Y， HOU Y T， et al. Making sensor networks immortal： an energy?renewal approach with wireless power transfer [J]. IEEE/ACM transactions on networking （TON）， 2012， 20（6）： 1748?1761.

[14] SHI Y， XIE L， HOU Y T， et al. On renewable sensor networks with wireless energy transfer [C]// Proceedings of 2011 IEEE INFOCOM. Shanghai， China： IEEE， 2011： 1350?1358.

[15] GALE D， SHAPLEY L S. College admissions and the stability of marriage [J]. The American mathematical monthly， 2013， 120（5）： 386?391.