摘 要： 为了在传感器网络中收集时间敏感性的数据，引入了移动设备来收集数据。提出了两种启发式算法，一种是基于货郎担问题的解法，将原问题分割成较小集合，然后逐步求解小问题，该算法适用于数据敏感性要求相对较低的应用；而当数据敏感性要求较高时，提出的贪婪式算法逐步建立移动设备的移动路径，即从基站（Sink）开始迭代选择代价值最小的节点，直到不能再添加节点进移动路径中。理论分析和模拟结果表明，提出的算法可以减少数据收集过程中所需要的移动设备的数目，而且大大节省了数据收集的总时间，从而可以应用在大规模网络中。
关键词： 传感器网络；数据时新型；移动设备
近几年来，国内外传感器的硬件技术、数字芯片技术以及无线通信技术的飞速发展使得应用大规模无线传感器网络WSN（Wireless Sensor Network）成为可能[1-2]。世界主要国家都在积极地研究无线传感器网络的热点技术，特别是最近兴起的物联网，更是把无线传感器网络的应用推向高潮，无线传感器网络已经应用或即将应用到人们工作和生活的方方面面。
在传统无线传感器网络的应用中，传感器节点采集数据，然后通过节点之间的多跳无线传输，最终建立路由把采集的数据传输到基站（sink）进行处理。这样的传输方式类似于传统因特网的路由，但是无线通信不同于因特网的有线通信，这样带来的最大问题是，普通传感器节点需要消耗大量的能量，因为每个传感器节点都要帮助别的节点转发数据，尤其是靠近基站的节点，一般都是最先耗尽能量的。而另一方面，传感器节点通常一经部署，需要连续工作几个月甚至几年，能量的过快消耗将导致传感器网络的瘫痪。因此，传感器网络研究的一个热点方向就是如何高效地收集数据。近年来，为了节省传感器网络中的能量消耗，部分研究者将移动设备引入到网络中来[3-4]。例如，参考文献[5]用移动数据收集器来收集数据，因为移动设备的能量比传感器节点充足，并且由于可以移动，它们可以移动到可以补充能量的地方。通过移动设备的辅助，可以大大地减少普通传感器节点的能量，从而延长网络生存时间。
在某些应用中，收集的数据必须在限定时间内送到基站以保证数据的时新性。例如，对于森林温度的监测，sink可以要求各传感器节点在20 min内将采集的温度数据传送一次，以连续不断地完成对温度的监测[2]。本文把该最大数据延迟时间（Maximum Latency Requirements）称为传输时间约束，其取决于具体实际应用对数据敏感性的需求程度。本文着重研究移动设备ME（Mobile Element）的路径规划问题，即如何规划ME的移动路径，使得收集数据在满足时间约束的前提下，传感器网络中节点的能量消耗得最少。
1 移动设备调度问题
本文研究的问题可描述如下：在一个传感器网络中，已知有一组数据采集节点的物理位置和数据传输的时间约束。ME可以在任意2个节点之间自由地匀速直线移动，本文假设ME的能量相对于传感器节点的能量是无穷的，因为ME可以移动到可以充电的地点。显然，传输时间约束可转化为ME移动路径的长度约束。问题的目标是规划1个ME的路径，使得每个ME从sink节点出发，依次访问传感器节点收集数据，最后回到sink节点，所有节点的数据都应满足规定的传输时间约束，而目标是ME移动的路径总长度（即数据传输时间）最小化。本文将该问题称为数据敏感性环境下的移动设备调度问题DFMES （Data Freshness Mobile Elements Scheduling）。
DFMES问题的目标是找到一个路径集合，满足4点：（1）sink节点vs是所有路径的起止节点；（2）每个顶点（除sink节点）属于且仅属于一条路径；（3）如果某条路径包括顶点v，则该路径数据收集时间（或路径长度）小于pv；（4）所有路径长度总和最小化。
2 算法描述
本文提出两种算法来解决DFMES问题。第一种方法适应于实时性要求相对较低的应用，即基于货郎担问题的解法，将原问题分割成较小集合，然后逐步求解小问题。第二种适应于数据敏感性要求较高的应用，以贪婪式算法逐步建立移动设备的移动路径，即从sink开始迭代选择代价值最小的节点，直到不能再添加节点进移动路径中。本文将前者简称为TR式（Tour Reduction）算法，后者简称为TE（Tour Expand）式算法。
2.1 TR算法
TR启发式算法始于一个简单的包含所有节点的TSP路径（本文使用Christofides算法[6]来计算初始TSP路径），然后递归得出子路径，过程描述如下（其中T代表初始TSP路径解集，t表示当前子路径）：
每次都选取当前根据式（2）计算出的最小代价vi，添加到ME的移动路径中，然后对剩余节点重新计算代价函数，再选出新的节点vi，直到当前的ME不能再添加任何节点进去，再添加1个新的ME，重复以上过程，直到所有的节点都被包含进来，这是贪心算法的主要内容。
3 分析与讨论
TR算法是基于一条完整的初始TSP路径，然后逐步选取节点生成子路径，并使得所有子路径集满足条件约束。由于该算法是对原始路径进行修改而得来的，因此计算出的子路径保留了原始TSP解集的大部分结构，对初始TSP路径的依赖较大，在最终解路径数量相对较少的情况下，能最大程度利用初始路径，算法性能较好，适合于数据敏感性要求较低的环境中。而TE算法是以贪婪的方式建立全新的移动路径，逐步添加节点，该算法适合于数据敏感性要求较高的环境中，本文将会以模拟实验来进行进一步的对比分析。
从两种算法的时间复杂度看，TR启发式算法的复杂度主要取决于构造初始TSP所需要的时间，例如，当使用Christofides算法[6]构造最初TSP解时，如时间复杂度为O（n3），则最终的时间复杂度为O（n3）。而TE启发式算法中，每次迭代都需重新计算代价函数，判断节点能否添加到路径中耗时O（n），总的时间复杂度为O（n2）。因此，一般来说TE算法的运算速度要快于TR算法。
4 模拟研究
为了证明本文所提算法的性能，用C++编程来实现对两种算法的模拟，并与已有算法进行对比。在模拟场景中，300个传感器节点随机部署在400 m×400 m的矩形区域中。节点的时间约束在一个[L，H]的范围中随机取值。
本文主要用两个指标来衡量算法的性能：（1）算法生成的子路径条数，即所需ME个数；（2）路径的总长度（总数据收集时间）。第1个指标反映了移动设备收集数据所需要的成本，不难理解，完成同样的功能，所需要的ME个数越少，则成本越低。而第2个指标反映了ME移动路径的优良与否，移动总路径越短，说明ME的移动路线规划得越好，即能够用较短的移动路线收集到所有的数据。
为了说明所提算法的性能，本文将提出的算法与VRPTW（Vehicle Routing Problem With Time Windows）问题的算法[5，7]（本文简称为VR1算法与VR2算法）进行比较。在VR1算法与VR2算法中，ME必须在每个节点预定的时间范围内访问并收集数据，当第一个访问节点确定后，算法反复添加最优节点至路径并且满足时间窗约束。VR1算法与VR2算法的区别在于它们添加节点至路径的标准不同：VR1算法考虑引入节点对当前部分路径的影响，而VR2算法考虑能最小化当前路径总时间的节点加入路径中。
图1所示为4种算法在不同的时间约束条件下移动设备的数目变化情况。从图1可以看出，当约束时间增大时，即对数据传送的敏感性要求较低时，4种算法的趋势都是一致的，即随着约束时间的增大其所需要的移动设备数量下降。这是因为，单个移动设备可以有更多的时间去完成数据的收集，从而可以不需要那么多的移动设备就可以完成预定的任务。此外，从图1可以看出，TR和TE算法都比VR1和VR2好，在最好的情况下，完成同样的数据收集，本文提出的算法可以只需要近1/3的ME，这充分说明了本文提出算法的有效性。
图2所示为4种算法分别在不同的时间约束条件下数据收集的总时间的情况。与上面的分析类似，不难理解，数据收集的总时间随着时间约束的放松而呈下降趋势。从图2也可以看出，TE算法的性能比其他算法要优，因为TE算法在代价函数中考虑了传输约束和节点之间的距离，并且平衡了两者的影响。相对于其他3种算法，在最好情况下能提升约3倍的性能。而TR算法虽然在开始的时候不及VR2和VR1，但是随着时间约束值的放松，性能越来越好，说明TR算法比较适合于对数据敏感性要求不太高的应用中。
为了最大程度地节省传感器节点的能量，从而能够满足传感器网络对时间敏感性数据的收集，本文引入移动基站来收集数据，并主要提出了两种启发式算法，其一是基于货郎担问题的解法，将原问题分割成较小集合，然后逐步求解小问题，该算法适用于数据敏感性要求相对较低的应用；而当数据敏感性要求较高时，提出的贪婪式算法逐步建立移动设备的移动路径，即从sink开始迭代选择代价值最小的节点，直到不能再添加节点进移动路径中。理论分析和模拟结果表明，与已有算法相比，本文提出的算法可以减少数据收集过程中所需的移动设备的数量，而且大大节省了数据收集的总时间，从而可以应用在大规模网络中。
在未来的工作中，将进一步考虑数据融合的场景。数据融合可以将多份数据融合为一份数据，因此，传感器节点可以预先进行小范围的协商，从而选举部分节点作为数据融合汇集点，其他的节点将采集的数据发送给该汇集点，而移动基站则只需要访问这些选定的汇集点，从而可以更加节省移动所需要的总长度，从而能够更快、更节省地帮助传感器网络收集数据。此外，在大规模的传感器网络环境下，往往会采用多个sink协同处理、收集数据，因此，考虑多个sink存在的场景，也是另外一个值得研究的方向。
参考文献
[1] 任丰原，黄海宁，林闯．无线传感器网络[J]．软件学报，2003，14（7）：1282-1291．
[2] Wang Tian， Wang Guojun， Guo Minyi， et al. Hash-area-based data dissemination protocol in wireless sensor networks [J]. Journal of Central South University of Technology， 2008， 15（3）： 392-398.
[3] HAMIDA E B， CHELIUS G. Strategies for data dissemination to mobile sinks in wireless sensor networks[J]. IEEE Wireless Communications， 2008，15（6）：31-37.
[4] MARTA M， CARDEI M. Improved sensor network lifetime with multiple mobile sinks[J]. Pervasive and Mobile Computing， 2009， 5（6）：542–555.
[5] XING G， WANG T， XIE Z， et al. Rendezvous planning in wireless sensor networks with mobile elements[J]. IEEE Transactions on Mobile Computing， 2008， 7（12）： 1430-1443.
[6] CHRISTOFIDES N. Worst-case analysis of a new heuristic for the traveling salesman problem[C]. Graduate School of Industrial Administration， Carnegie-Mellon University， Technical Report 388， 1976.
[7] ALMI′ANI K， SELVADURAI S， VIGLAS A. Periodic mobile multi gateway scheduling[C]. Ninth International Conference on Parallel and Distributed Computing， Applications and Technologies （PDCAT）， New Zealand， 2008：195-202.