基于移动小车的无线传感器网络数据采集算法

张淳

摘要：数据采集是无线传感器网络中的重要技术之一。多跳传输算法是传统的数据传输算法，但是传感器需要耗费大量能量将数据发送给基站。因此一种应用多个移动小车在被监测范围内采集数据的算法被提出。首先，被监测范围被划分为多个区域，其次，对最小化移动小车数量的问题进行建模，然后，提出了一种多移动小车的调度算法。仿真实验显示，这种算法能够有效降低数据延迟。

关键词：无线传感器网络；数据采集；数据延迟

中图分类号： TP393 文献标识码： A 文章编号：1009-3044（2018）15-0055-03

A Data Collection Algorithm in Wireless Sensor Networks Based on Mobile Collectors

ZHANG Chun

（School of Computer Science and Technology， Nanjing University of Posts and Telecommunications， Nanjing210023， China）

Abstract：Data collection is one of the key technology of wireless sensor networks. The multi-hop routing algorithm is the traditional transmission algorithm， but sensors consume much energy sending data to the sink. Therefore， a data collection algorithm using multiple mobile data collectors is proposed. First， the monitoring area is divided into multiple regions. Second， the data collection problem is modeled as minimizing the number of data collectors. Third， a dispatching algorithm for data collectors is proposed. Simulations shows that this algorithm can reduce the data delay effectively.

Key words： wireless sensor networks； data collection； data delay

1 引言

在目标跟踪应用中，无线传感器网络中的节点要把目标信息传递给基站，基站根据接收到的信息计算目标的运动轨迹，并将对节点的建议和用户需求及时通告给节点，因此，数据采集是目标跟踪中用到的一项关键技术[1]。多跳传输是无线传感器网络中常用的一种路由算法，节点监测到事件的发生并产生数据包后，需要耗费大量能量将数据发送回基站（sink），即控制中心。由于节点依靠携带的电池供电，在很多应用环境中，電池无法更换，则当节点电量耗尽后，无线传感器网络将会面临很多问题，如产生通信空洞、覆盖空洞等；另外，越靠近sink的节点，能量消耗越多，这就造成了网络内能耗不均衡，因此，在无线传感器网络中引入移动小车是十分必要的；应用移动小车还可以提高数据传输的质量，数据包的接收率会受到无线信道的拥塞程度和传输路径长短的影响，无线信道越繁忙、数据传输路径越长，产生碰撞的概率越高，数据包丢包概率越高，因此，应用移动小车还可以降低丢包概率。虽然应用移动小车有很多优点，但是会产生数据延迟。

因此，本文需要解决的问题是：引入多个移动小车在被监测区域中采集数据，降低无线传感器网络中的数据延迟。数据延迟指的是，传感器节点产生数据包的时间和基站接收到数据包之间的时间差。

近年来，越来越多的文献中引入移动的概念来解决数据采集问题。文献[2]提出了移动基站的几种移动方式，由于移动基站不停地在运动，因此它的一跳邻居节点也不断在变化，避免了一部分传感器消耗能量过多，一部分传感器空闲时间多的问题。文献[3]假设每个传感器以一定的速率产生数据，且移动小车需要运动到每个传感器附近去采集数据，目标是为每个移动小车规划一条路径，这条路径需要经过网络内的所有传感器。文献[4]将移动小车的移动问题建模成旅行商问题。文献[5]对移动小车的各种问题进行了综述，指出了应用移动小车的优点和缺点。

2 多移动小车数据采集方法

2.1 移动小车的数量最小化问题

因为被监测范围较大，因此首先把被监测范围划分成几个区域。在很多文献[6，7，8]中已对分簇算法进行了研究，因此分簇算法不是本文研究的重点。本文中应用文献[6]中提出的分簇算法，将被监测范围划分成若干个区域，每个区域由二级簇首、一级簇首和普通簇成员构成。

传感器节点的存储能力是有限的，传感器节点能够缓存数据的时间长度[tst]取决于节点的存储能力和数据采集速率，假设节点能够存储[tst]秒内收集的数据，为了避免节点采集到的数据包丢失，当sink接收到节点发送的请求信息后，移动小车要在[tst]秒内将节点的数据包取走。当无线传感器网络内节点的数目较多时，sink可能在短时间内收到很多节点的请求信息，单个移动小车的运动速度有限，需要很长时间才能访问完所有需要访问的节点，这个时间长度可能已经远远大于节点能够缓存数据的时间长度，为了避免数据溢出，只有同时应用多个移动小车才能保证节点采集到的数据不会因为数据溢出而丢失。以下给出几个定义。

定义1 请求序列集：传感器节点为事件触发型，节点监测到事件的发生后，产生一个事件数据包，然后发送给簇头节点，簇头收到事件数据包后，会发送一个请求信息给sink节点，请求sink派遣移动小车来采集数据包，请求信息中包含了监测到事件的时间[T]，由于网络内节点数量较多，sink在短时间内可能接收到很多簇头节点发送来的请求信息，这些请求信息构成了一个集合[request]，[request=ΨT1，ΨT2，...，ΨTk]，其中[ΨTk]代表了储存有时间[Tk]监测到的事件数据包的簇头的集合，且[T1

定义2 移动小车的数据采集周期：当sink接收到簇头发送的请求信息后，这些请求信息形成一个请求序列集，sink查询请求序列集，根据事件数据包产生的时间和位置这两个因素，调度多个移动小车去采集数据。用[A=A1，A2，...，An]表示移动小车的集合，[KnT]表示在[T]时刻sink分配给[An]的需要去访问的簇头集合，[KnT?Ψl]或[KnT?（Ψ'l?...?Ψ'm）]，其中[Ψ'l?Ψl]，[Ψ'm?Ψm]，[l]、[m]表示不同的时间值，[An]当前所在位置作为它的出发点。则[An]从出发点出发，访问完[KnT]内的节点后，将采集到的数据包发送给sink，这个过程称为[An]的一个数据采集周期；然后，[An]进入“等待”状态，当接收到sink发送过来的任务后，进入下一个数据采集周期。

定义3 采集路径：移动小车的采集路径是指，对于任意一个移动小车[An]，设在一个数据采集周期内需要访问的簇头集合为[KnT]，[KnT=Si，Sj，...，Sl，Sm]，[Si]、[Sj]、…、[Sl]、[Sm]为 [An]需要依次访问的节点序列，[P=pi，pj，...，pl，pm]为[An]对[KnT]的访问点序列，[pst]为[An]的出发点，则依次连接[pst]和[P]集合内访问点的直线被称为[An]在一个数据采集周期的采集路径。

由于在同一时间，网络中可能有多个节点同时监测到事件的发生，因此sink在短时间内可能收集到多个请求信息，设sink每隔一段时间[t]查询一次请求序列[request]，然后派遣移动小车去访问请求序列中的节点，其中[t

[request=rga，rgb，...，rge] （1）

[RG1?RG2?...?RGi=rga，rgb，...，rge] （2） [RG1?RG2?...?RGi=?] （3）

Object [MinimizeRG]

S.t. [Dj

2.2 移动小车的分配问题

根据1.1节中给被监测范围进行分区的方法，将被监测范围划分为多个区域。本节将给出为移动小车分配区域去采集数据的方法。

初始时刻，设为[t1]，经过一段时间[t]后，sink查询[[t1，t1+t]]时间段内的请求序列[request（t1，t1+t）]，用式（5）表示，其中[rgTn]表示在[T]时刻标识号为[n]的小区域内有需要被采集的节点，因为节点的数据包都发送给一级簇头，因此[rgTn]保存的节点均为一级簇头。

[request（t1，t1+t）=Ψth，Ψtk，...，Ψtm=rgtha，rgthc，...，rgthe，rgtkd，rgtkk，...，rgtkf，...，rgtmh，rgtmj，...，rgtmm] （5）

设[t1]时刻多个移动小车都位于sink附近，首先考虑[th]时刻监测到事件的节点，包括以下两种情况：

（1）[th]时刻仅标识号为[a]的区域内的节点监测到事件

对于任意一个空闲的移动小车（简称为[MDC]），假设为[MDCa]，sink计算[MDCa]访问[rgtha]中的一级簇头要行进的距离[Dtha]，考虑以下三种不同的情况：

1）[Dtha

寻找[rgtkd，rgtkk，...，rgtkf]内距离[rga]最近的区域（定义任意两个区域[rgn]、[rgm]之间的距离为[rgn]和[rgm]的二级簇头之间的距离），假设为[rgd]，计算[Dtkd]，如果满足式（6），其中[d（a，d）]为[MDCa]从[rga]移动到[rgd]要经过的距离，则[RG1={rgtha}]，其中[RG1]为sink得到的派遣[MDCa]去访问的节点集合；如果满足式（7），则[RG1={rgtha，rgtkd}]；如果满足式（8），则按照事件发生的先后顺序，继续寻找和当前区域[rgd]距离最近的区域，作为下一步要访问的区域，并计算[MDCa]的行进要经过的距离，重复此过程，直到行进距离[D>vtst]，然后把[D>vtst]之前计算得到的[MDCa]要經过的区域放入[RG1]中；

[Dtha+Dtkd+d（a，d）>vtst] （6）

[Dtha+Dtkd+d（a，d）=vtst] （7）

[Dtha+Dtkd+d（a，d）

2）[Dtha=vtst]

在这种情况下，[RG1={rgtha}]；

3）[Dtha>vtst]

这种情况说明[MDCa]访问[rgtha]内所有节点经过的距离大于[vtst]，则根据路径规划得到的访问[rgtha]内节点的顺序，计算[MDCa]访问这些节点行进的距离[D]，直到[D>vtst]，然后将[D>vtst]之前[MDCa]访问的区域放入[RG1]中；

（2）[th]時刻监测到事件的节点分布在多个区域内

sink对节点的数据采集采用由近及远的方式，首先寻找[{rgtha，rgthc，...，rgthe}]内距离[MDCa]最近的区域（本节中，定义sink和任意区域[rgn]的距离为sink和[rgn]中二级簇头的距离），假设为[rgc]，sink计算[MDCa]访问[rgthc]中的一级簇头要行进的距离[Dthc]，然后根据[Dthc]和[vtst]之间的关系，根据第（1）种情况中所采取的方法，依次类推，计算得到[RG1]；

通过以上步骤，得到了一条访问路径[RG1]，sink派遣[MDCa]去访问[RG1]中的节点；然后，sink查询[request（t1，t1+t）]，如果除了[RG1]中的节点外，还有未被访问的节点，则sink为当前空闲的任意移动小车，假设为[MDCb]，应用以上计算[RG1]的方法，计算得到第二条访问路径[RG2]，派遣[MDCb]去访问；再次查询[request（t1，t1+t）]，直到[request（t1，t1+t）]中的节点全部被移动小车访问。

移动小车采集完网络内的数据后，要及时把数据发送给sink进行分析、处理，小车移动的位移矢量用[d→=（d，θ）]表示，小车将采集到的数据发送给sink后，就进入“等待”状态，等待sink再次发出任务指令。

[d→=（（dms-Rm），θ）ifdms>Rm0ifdms≤Rm] （9）

其中，[d]表示移动的长度，[θ]表示移动的角度，为小车和sink之间的连线与水平坐标之间的夹角，[dms]为小车的当前位置与sink之间的距离，[Rm]表示小车的通信距离。

3 仿真实验

在本节的仿真实验中，100个传感器节点随机地分布在一个正方形区域中，sink的射频带宽为1Mbps，节点的感知距离为20米，移动小车的通信范围为35米，移动小车的速度为5米/秒，事件数据包大小为100bytes。本文提出的算法被命名为MDDC，文献[9]中的算法被命名为OMET算法，被用来与本文的算法进行比较。

图1显示的是数据延迟和移动小车的数量的关系图。从图中可以看出，MDDC算法的数据延迟小于OMET的数据延迟，且随着移动小车数量的增加，MDDC算法的曲线下降趋势比OMET明显。这是由于，MDDC算法中，多个区域中的数据包由多个移动小车进行采集，所以随着小车数量的增加，数据延迟明显降低。

图2显示的是小车平均移动路径长度和小车数量的关系图。从图中可以看出，应用MDDC算法，移动小车的移动距离要小于OMET算法。且随着小车数量的增加，小车的平均移动距离呈下降趋势。

图3显示的是小车平均移动路径长度和小车数量的关系图。从图中可以看出，随着被监测范围的增大，MDDC算法和OMET算法的平均数据延迟增加，且两种算法之间的差距呈增大趋势。

4 结束语

本文提出了以区域为单位为多个移动小车分配采集任务的思路，并以节点的最大存储量作为约束条件，对移动小车数量最小化的问题进行建模，从而提出一种启发式的移动小车调度算法；通过仿真实验证明，应用这种数据采集方法，能有效降低无线传感器网络中的数据延迟。

参考文献：

[1] 党小超， 杨冬冬， 郝占军. 基于虚拟力的传感器网络三维覆盖算法[J]. 计算机应用， 2015， 35（11）， 3021–3025.

[2] Chatzigiannakis I， Kinalis A， Nikoletseas S. Sink Mobility Protocols for Data Collection in Wireless Sensor Networks [C]//Proceedings of the International Workshop on Mobility Management and Wireless Access： Torremolinos， Malaga， Spain， October 2006： 52-59.

[3] Somasundara A A， Ramamoorthy A and Srivastava M B. Mobile Element Scheduling with Dynamic Deadlines [J]. IEEE Trans. Mobile Computing， 2007， 6（4）： 395-410.

[4] Kumar A K， Sivalingam K M. Energy-Efficient Mobile Data Collection in Wireless Sensor Networks with Delay Reduction Using Wireless Communication [C]//Proceedings of the 2th International Conference on COMSNETS， Bangalore， Jan 2010： 1-10.

[5] Xu L， Amiya N， Lvan S. Exploiting Actuator Mobility for Energy-Efficient Data Collection in Delay-Tolerant Wireless Sensor Networks [C]// Proceedings of the 5th International Conference on Network and Services， Valencia， April 2009： 216-221.

[6] Lung C H， Zhou C J. Using hierarchical agglomerative clustering in wireless sensor networks： An energy-efficient and flexible approach[J]. Ad Hoc Networks， 2010， 8： 328-344.

[7] Yu J， Chong P. A survey of clustering schemes for mobile Ad hoc Networks[J]. IEEE Communications Surveys， 2005， 7（1）： 32-48.

[8] Israr N， Awan I. Coverage based inter cluster communication for load balancing in heterogeneous wireless sensor networks[J]. Telecommunication Systems， 2008， 38： 121-132.

[9] He Liang， Xu Jingdong， Yu Yuntao. Optimize multiple mobile elements touring in wireless sensor networks[C] //Proceedings of the IEEE International Symposium on Parallel and Distributed Processing with Applications， Chengdu， August 10-12， 2009： 317-323.