基于移动sink的无线传感器网络数据采集方案

郭剑，孙力娟，许文君，王汝传，肖甫

（1. 南京邮电大学 计算机学院， 江苏 南京210003；2. 南京邮电大学 江苏省无线传感网高技术研究重点实验室，江苏 南京 210003；3. 南京邮电大学 宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003）

1 引言

无线传感器网络[1,2]（WSN, wireless sensor network）是一种具有广泛用途的网络，数据采集是其基本应用之一。人们在工作环境中布置大量的传感器节点，并对需要的各种数据进行采集，如温度、湿度、浓度、图像、声音、视频等。实际应用中，许多业务的数据量都较大，比如图像和视频相关的应用，这就给数据采集方案的设计带来了一定的挑战。传统的处理方法中，所有节点位置固定，采集到数据后，借助于路由协议将信息提交给sink。它的主要问题是：1）漏斗效应，距离 sink越近的节点能量消耗越大，网络会较早地出现分割，大数据量的业务尤其如此；2）通信开销，无论是哪种路由算法，都会有一定的控制开销，需要耗费节点的能量；3）连通约束，网络不连通时必然有部分节点的数据无法提交。

图1 可移动节点

上述缺陷的部分根源在于sink的静止性。随着RacemoteZ[3]、quadcopter[4]等可移动节点的提出（如图 1所示），一些学者提出了基于移动节点的采集方案[5,6]，部分解决了上述问题。此类方法的问题是存在一些时延[7,8]，并且难以确定 sink节点的移动方案。由于大多数数据采集型应用（data-gathering applications）对实时性要求不高，因此sink的移动控制才是关键，目前已有这方面的一些成果发表。随机漫游[9]策略算法简单，但是它不考虑节点的分布状况，会导致节点能耗严重不均衡。AKKAYA等提出了一个启发式移动策略[10]，sink每次向发送数据量最多的节点移动。这个策略比较适合事件驱动型应用（event-driven applications），但不适合数据采集型网络。LUO[11]等提出了沿区域边际移动的Peripheral策略，但Peripheral较为理想化，对MAC层的冲突考虑不够。LMREM[12]方案根据节点的剩余能量来选择移动位置，它的计算开销较大，并且节点还需要保存和转发较多的数据，网络负荷很重时，节点很容易死亡。

针对这些问题，本文提出了一种轨迹固定的数据采集方案（DCSR, data collection scheme with regular track）。DCSR的移动策略包括2个环节：第一，根据节点的分布状况选出一批采集点；第二，找到经过这些点的最短环路。这个环路就作为sink的采集路线，sink沿着它运动和收集数据。根据文献[10]，在网络中寻找最优采集地点是一个 NP问题。而计算最短环路是一个旅行商问题，也属于NP问题。这2个步骤都没有特别好的处理方法，因此本文均进行了简化与近似。选取采集点时，DCSR尽量少选一些采集点，计算最短环路时，DCSR使用了量子遗传算法[13,14]（QGA, quantum genetic algorithm）。对比测试表明，DCSR的性能较好，且能够收集更多的数据。

2 WSN网络模型

本文使用了如下的网络模型。

1) 传感器节点：网络中使用的是同类型的传感器节点，且它们具有相同的初始能量。这些节点被随机部署在一个边长为e的正方形监控区域中，且放置后不可移动。

2) sink节点：sink节点具有充沛的电池能量与较高的存储容量，并有一定的移动能力。sink节点的通信距离与普通节点相同，均为r。

3) 业务类型：周期采集型业务，节点定期从传感器上收集数据。

4) 数据提交模式：被动提交。节点收集到数据后存入自己的缓存；只有当它收到sink节点的通知时，它才提交数据。

在上述假设中，sink节点是较为关键的一个环节，实现时可以采用 RacemoteZ、quadcopter等可移动节点来获得移动性，并通过大容量电池或定期充电等方式来保障能量供应。此外，本文在计算sink的移动路线时，没有考虑现实道路情况对节点移动路径的限制，也就是假设监控场景中地面较为平整，sink可以任意移动。当然，如果 sink采用quadcopter等飞行传感器节点，这个问题就不存在。

3 采集点的确定

在第1个阶段中，DCSR需要从监控区域中选出一批采集点。采集点的数量应该尽可能少，这样可以减轻第2个阶段的计算量，并且计算出的最短环路也相对更短。由于sink在每个采集点的通信范围可以看成一个以采集点位置为圆心的圆盘，因此，第1个阶段的任务就是找到一组坐标集合，并满足如下条件：

1) 坐标的数量尽可能少；

2) 以这些坐标为圆心，r为半径的一组圆盘能够覆盖监控区域。

3.1 圆盘位置的确定

在部署圆盘时，为了避免空隙，相邻圆盘必然相互重叠。如图2所示，圆盘A与B相邻，它们相互重叠，而它们下方的空隙又由圆盘C来覆盖，因此圆盘C也和它们相交。为了减少圆盘数，重叠的部分应越小越好。因此C的边界应恰好覆盖A与B的交点O。否则，它们之间或者产生三重重叠，或者出现空洞。此时就有了定理1。

图2 相互重叠的3个圆盘

定理1 当两两重叠的3个圆盘圆心组成等边三角形时，它们的重叠面积最小[15]。

证明 假设圆盘 A、B、C重叠的面积分别为SAB、SBC、SAC，则重叠的总面积S为

由于AXCYBZ是一个六边形，因此有

2α+(π-α)+2β+(π-β)+2γ+(π-γ) = 4π

即

这里就是要求解满足式(2)条件下的式(1)的极值。根据拉格朗日乘数法，可求得当 α= β= γ = π/3时，S的值最小。此时3个圆盘的圆心组成等边三角形，且三角形的边长为 3r。

满足定理1的圆盘位置集合有多组，其中一组如式（3）所示，图3为其分布示意。

图3 圆盘分布示意

其中，m1、m2、m3、m4皆为非负整数，且满足

3.2 采集点的选取

确定完所有的圆盘后，DCSR将在每个圆盘中选择一个采集点。确定这个位置时，DCSR主要考虑了能耗的因素。

根据文献[16]，当传感器节点向外发送数据时，遵循式(4)。

其中，Gr、Gt分别表示接收端和发送端的天线增益，Pr、Pt分别表示接收端和发送端的天线功率，d为源节点与目标节点间的距离，L表示系统损耗因子，λ表示载波波长，通常Gr、Gt、L、λ都是常量。对于某一个具体的网络来说，如果节点同质且干扰抑制较为理想，则Pr也可以认为是一个常量。因此式(4)可以简写为式(5)。

假定一个圆盘中有n个节点，则每次数据采集过程中，n个节点的总发射功率P为

其中，（xi，yi）表示第 i个节点的位置，(xs，ys)表示采集点的位置。

从式（6）可以看出，要使总发射功率最小，就应该选择合理的采集点位置，使所有节点到它的距离平方和最小。

定理2 假定半径为r的圆域中有n个点，每个点的坐标为（xi，yi），1≤i≤n。欲在该圆中找到一点，使得它到所有节点距离的平方和最小，则该点坐标是

证明 假设圆心的坐标为（xc，yc），该点坐标为（xs，ys），每个点到它的距离为di，1≤i≤n，则所有距离的平方和fs为

式(7)受式(8)的约束，

根据拉格朗日乘数法，可求得

定理2指出了sink节点的理想位置。但是，定理2不保证每个节点到该位置的距离di≤r。因此如果sink节点选择该位置，部分节点的信息有可能会收集不到。此时就有了定理3。

定理 3 假设圆盘中最大、最小横纵坐标分别为 xmax、xmin、ymax、ymin，(xs，ys)是所有节点坐标的平均值，则当式(10)成立时，圆盘内节点到（xs，ys）的距离均小于r。

因此，（xs，ys）到任一节点的距离

定理3说明，当圆盘内的节点分布符合式(10)时，可以采用式(9)计算采集点的位置。

进一步对节点分布进行分析。由于圆盘的半径为r，易知

即(xs，ys)的范围不会超出一个矩形区域，如图4所示。假设该矩形的边长分别为l1、l2。则有

图4 采集点位置的坐标范围

由式（11）可以看出，当圆盘中节点较为集中时，l1、l2相对较大，矩形面积SR也较大；反之当节点较为分散时，SR较小。由此可以得到定理4。

定理 4 当矩形面积 SR满足式(12)时，式(10)成立。

证明 将式(12)展开并整理，即可得式(10)。

定理4说明，当矩形面积较大，满足式(12)时，可采用所有节点的坐标均值作为采集点位置。

而当矩形的面积较小时，定理2不再适用。DCSR进行了近似处理，在水平方向和垂直方向上分别用 l条直线对这个矩形区域进行等分。等分之后，包括边界在内，相交得到了(l+2)2个点。DCSR依次对这些点进行尝试，找出距离之和最小的位置作为采集点。l值的大小跟求解精度相关，本文中取值40。

综合以上各种情况，DCSR采用如下方法来计算采集点位置。

对于任一圆盘，设其中有n个节点，(xs，ys)为待求的采集点位置：

① 如果n=0，该圆盘内不设采集点；

② 如果 n=1，采集点位置即为唯一的节点坐标；

③ 如果n=2，取两节点连线的中点作为采集点；

④ 如果n＞2，计算(xs，ys)所在的矩形区域：当该矩形区域面积较大，满足式(12)时，计算所有节点坐标的平均值作为采集点，否则采用划分网格的方法求近似点。

4 移动路径的计算

得到了采集点之后，DCSR采用QGA来寻找经过这些点的最短环路。QGA是在遗传算法的基础上发展起来的一种算法。它引入了量子计算的概念，具有快速的收敛速度和较强的并行搜索能力，被广泛运用于求解各种优化问题。在QGA中，组成种群的基本单位是量子染色体。每个量子染色体由多个量子比特组成。一条典型的量子染色体如式(13)所示。

其中，αij、βij∈C，且满足i∈[1, n]，j∈[1, k]。n为染色体中的基因数，k为基因中的量子比特个数。

量子染色体向传统染色体的转换通过量子观测操作实现，量子染色体的更新通过量子旋转门实现。应用QGA的主要问题是染色体的编码和适应度的计算。下面分别进行说明。

1) 染色体的编码

DCSR采用了对采集点可选链路进行编码的方法，在这种编码策略中，染色体的每个基因对应一个采集点，基因的值就是在该采集点选中的链路编号。图5给出了一个监控区域的实例，在图5中共有A～G 7个采集点，连线表示可选的链路（过长的已剔除）。表1给出了这些链路的编号。图6给出了一条染色体示例，它代表环路A-B-C-E-F-G-D-A。

图5 采集点分布示意

表1 各采集点的链路编号

图6 染色体示例

2) 适应度的计算

适应度主要考查2个因素：第一，染色体包含的链路中所构成的最长路径是多少跳；第二，该最长路径的长度是多少。适应度的计算如式(14)所示。

其中，f是计算出的适应度值，h是染色体中的链路所形成的最长路径的跳数，l是该最长路径的长度，α是调节系数，根据具体网络决定。

5 DCSR方案

5.1 DCSR的具体步骤

DCSR的具体步骤如下。

1) 初始化：各节点向 sink节点汇报自己的位置信息。

2) 路径计算：sink根据各节点的位置分布，依次采用第3节和第4节的方法分别计算出本网络所需要的采集点以及经过这些采集点的最短回路。

3) 数据收集：sink沿计算好的路线移动，每到达一个采集点便广播一条收集通知。附近的节点收到通知后，将保存的数据提交。为减少信道冲突，每个节点回复数据前需要随机等待一段时间。

5.2 DCSR方案的性能分析

1) 时间复杂度

DCSR的路径规划包含2个步骤：计算采集点和计算路径。

计算采集点时，由第3节可知，对于边长为e的区域，其中至多有个圆盘，每个圆盘在最坏情况下尝试(l+2)2个点，因此这一步骤的时间复杂度为

计算路径采用了QGA。QGA的复杂性分析较难，学术界还没有精确的理论成果发表，此处仅作近似分析。根据第4节的编码方式，每个染色体有个基因，每个基因最多有个量子比特，因此每条染色体最多有个量子比特。假设QGA一共有m个染色体，算法一共迭代n次，每次迭代中要进行染色体的观测、适应度的计算、染色体的更新和最优染色体的选择4个操作，其时间复杂度分别为、O(m)。因此计算路径的时间复杂度应为

由于l值不需要取很大，通常有mn＞ l2，因此，综合这 2个步骤可知 DCSR的时间复杂度为

2) 通信代价及效率

采集数据时，DCSR在每个采集点仅广播一条通知。整个监控区域至多有个圆盘，因此DCSR的通信代价是。

假设传感器网络由k个节点组成。在每一轮的数据采集中，sink节点至多广播条通知，至少收到k个数据分组，因此，通信效率应不小于

6 仿真及测试

6.1 场景设置及测试指标

本文在NS 2.34环境下实现了DCSR 协议。为了验证其性能，本文将它与静止sink（stationary）方式、随机（random）漫游策略和 Peripheral协议进行了对比测试。在这4个策略中，DCSR、Random采用了被动提交模式，节点收集到数据后将其保存在本地，收到通知后才发送给sink节点，Stationary、Peripheral采用了主动提交模式，节点收集到任何数据都主动向sink节点发送，因此需要借助于路由协议。其他实验参数的设置如表2所示。

表2 实验参数设置

在测试时，本文主要考察了如下6个指标。

1) 采集数据量：到达 sink节点的有效数据分组的数量。所谓有效数据分组是指含有采集数据的数据分组。

2) 吞吐量：网络中所有数据分组的总数与网络工作时间之比。网络中的所有数据分组包括发送的数据分组、冲突重发的数据分组、节点转发的数据分组、路由探询分组和路由控制分组等。

3) 效率：sink收到的有效数据分组总数与网络中所有数据分组的总数之比。

4) 剩余能量：网络不能正常工作，即 sink采集不到数据时，网络中所有节点的剩余能量。

5) 能量利用率：sink收集到的数据总量与网络的总耗能之比。

6) 平均时延：到达 sink节点的有效数据分组的时延平均值。

6.2 实验结果

1) 采集数据量

4种协议的采集数据量对比如图7所示。其中，图7(a) sink以5m/s的速度移动，图7(b)sink以25m/s的速度移动，Stationary的sink节点均静止不动，下同。从图中可以发现，由于节点的增多和移动速度的加快，网络中的冲突增加，因此所有方案收集的数据量均有所下降。DCSR由于节点不需要转发数据，所以能耗较轻，工作时间相对较长，采集到的数据最多。Random由于路线不够合理，会出现部分节点过早死亡和部分节点访问不到的情况，因此收集的数据量要少一些。Stationary由于网络很早就中断，因此收集数据最少。

图7 采集的数据量

2) 效率

4种协议的采集效率比较如图 8所示。由于DCSR没有路由开销，且节点不需要转发数据，因此采集效率较高。

3) 吞吐量

4种协议的网络吞吐量（单位：分组数/s）比较如图9所示。网络吞吐量是衡量网络性能的重要指标之一。从图中可以看出，被动提交模式网络的吞吐量要高于主动提交模式的网络。这是因为节点没有转发数据的负担，因此可以一直工作，不会过早死亡。而主动提交模式的网络，大量节点很早就死亡，个别节点的数据sink节点又不易采集，因此网络的吞吐量较低。DCSR由于路线比Random合理，数据采集更稳定，吞吐量更高。

图8 网络效率

图9 吞吐量

4) 剩余能量

4种协议的网络剩余能量比较如图10所示。从图中可以看出，在Stationary策略中，sink静止不动导致周围节点很快死亡，网络很早中断，所以剩余能量较多，这实际上也是能量的浪费。在使用移动sink的3种策略中，DCSR的路线最为合理，且节点不承担转发任务，能量消耗较为均衡，因此网络工作结束时，能量几乎全部消耗完，且全部用在提交数据上。

图10 剩余能量

5) 能量利用率

4种协议的能量利用率比较如图11所示。它的实际意义是网络每消耗1J能量，sink所能采集到的有效数据量。从图中可以看出，DCSR能量的利用率比其他3个协议都高。

图11 能量利用率

6) 平均时延

4种协议的平均时延比较如图12所示。从图中可以发现，被动提交模式的时延比主动提交模式的时延要高，这是因为数据的转发速度要高于sink的移动速度。而Random的时延又要远高于DCSR，这是由于DCSR尽量寻找最短的路径，路线较为合理，因此时间较少。需要说明的是，大多数数据采集型应用，尤其是非实时业务，其时延要求并不高，DCSR还是比较适用的。

图12 平均时延

7 结束语

在数据采集型应用中采用移动sink节点能够带来多方面的好处。它可以提升网络的吞吐量，均衡节点的能量消耗，提高数据的采集效率，并且当网络出现分割时也能正常工作。本文设计的DCSR协议，较好地体现了这些优势。受到节点移动速度的限制，DCSR协议在收集数据时会产生一定的时延。因此，对于数据量较大、时限要求不高的采集型业务，DCSR协议具有较好的应用前景。下一步的研究内容是在传感器节点上引入数据融合机制，将它与DCSR协议结合后，网络的性能应该会更好。

[1] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[2] POTDAR V, SHARIF A, CHANG E. Wireless sensor networks: a survey[A]. Proceedings of International Conference on Advanced Information Networking and Applications[C]. Bradford, 2009. 636-641.

[3] SONG G M, ZHOU Y X, DING F, et al. A mobile sensor network system for monitoring of unfriendly environments[J]. Sensors, 2008, 8:7259-7274.

[4] ACHTELIK M, ZHANG T G, KUHNLENZ K, et al. Visual tracking and control of a quadcopter using a stereo camera system and inertial sensors[A]. Proceedings of the International Conference on Mechatronics and Automation[C]. Changchun, China, 2009. 2863-2869.

[5] WANG W, SRINIVASAN V, CHAING K C. Using mobile relays to prolong the lifetime of wireless sensor networks[A]. Proceedings of the 11th Annual International Conference on Mobile Computing and Networking[C]. Cologne, 2005. 270-283.

[6] BI Y Z, SUN L M, MA J, et al. HUMS: an autonomous moving strategy for mobile sinks in data-gathering sensor networks[J]. EURASIP Journal on Wireless Communications and Networking, 2007: 1-15.

[7] XING G L, WANG T, XIE Z H, et al. Rendezvous planning in wireless sensor networks with mobile elements[J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1430-1442.

[8] 郜帅, 张宏科, 徐怀松. Sink 轨迹固定传感器网络的高效数据采集机制[J]. 软件学报, 2010, 21(1): 147-162.GAO S, ZHANG H K, XU H S. Efficient data gathering approach in sensor networks with path-fixed sinks[J]. Journal of Software, 2010,21(1): 147-162.

[9] JAIN S, SHAH R C, BORRIELLO G. Exploiting mobility for energy efficient data collection in sensor networks[J]. Mobile Networks and Applications, 2006, 11(3): 327-339.

[10] AKKAYA K, YOUNIS M, BANGAD M. Sink repositioning for enhanced performance in wireless sensor networks[J]. Computer Networks, 2005, 49(4): 512-534.

[11] LUO J, HUBAUX J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[A]. Proceedings of the 24th Annual Conf of the IEEE Computer and Communications Societies[C]. Miami,2005. 1735-1746.

[12] TAN C G, XU K, WANG J X, et al. A sink moving scheme based on local residual energy of nodes in wireless sensor networks[J]. Journal of Central South University of Technology, 2009, 16(2): 265-268.

[13] XIAO J, YAN YP, ZHANG J, et al. A quantum-inspired genetic algorithm for k-means clustering[J]. Expert Systems with Applications,2010, 37(7): 4966-4973.

[14] GU J W, GU M Z, CAO C W, et al. A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem[J]. Computers & Operations Research, 2010,37(5): 927-937.

[15] ZHANG H H, HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Ad Hoc & Sensor Wireless Networks, 2005, 1(1-2): 89-124.

[16] PAOLO S. Topology Control in Wireless Ad Hoc and Sensor Networks[M]. Chichester: John Wiley & Sons Ltd, 2005.

[17] SETHI S, ROUT A, MOHANTA D. Hybrid activities of AODV for wireless ad hoc sensor network[A]. Proceedings of International Conference on Recent Trends in Business Administration and Information[C]. Trivandrum, 2010. 39-44.