基于栅格的传感网多移动Sink数据收集方案

杨 瑞，沙 超，卞 遥，朱毅凯，王汝传

(1.南京邮电大学 计算机学院、软件学院、网络空间安全学院，江苏 南京 210003；2.南京大学 网络信息中心，江苏 南京 210023)

0 引 言

在传统无线传感网(wireless sensor networks，WSNs)中，Sink周围的节点不仅需要感知其所覆盖的区域，还要负责全网的数据传输，故生命期较短，易形成能量空洞[1]。“能量空洞现象”指的是由于部分节点失效而导致网络原有覆盖区域缺失或数据无法送达Sink的现象[2]。Lian等[3]指出，分布在Sink一跳范围内的节点更易过早地耗尽自身能量，而在此情况下，网络约有90%的初始能量还未被使用。因此，如何均衡节点的通信能耗，从而延长网络生命期，成为该领域研究者面对的首要问题[4-5]。

路由优化机制是缓解无线传感网能量空洞现象的主要方法[6]，但却未能从根本上解决静态Sink附近的节点负载过重的问题。而引入移动Sink，不仅可均衡节点能耗，也缩短了数据上传的距离，降低了全网通信开销[7]并可有效延长网络生命期[8]。文献[9]提出了面向能耗均衡的传感网单移动Sink数据收集方法，利用网络完全覆盖模型，确定了Sink的各遍历点坐标，并由此构建了其定长移动数据收集轨迹。Khan等[10]则设计了一种基于栅格的数据传播机制-VGDD(virtual grid based data dissemination)，将网络划分成若干规模一致的栅格，并在各栅格中根据节点到栅格中心的距离选出一个簇头。

在数据收集过程中，Sink以固定速度在以矩形网络内切椭圆为轨迹的线路上移动，而全网节点则通过其簇头及若干中继，将数据多跳上传至Sink。由于Sink的位置不断变化，故在VGDD中，每个节点需实时获取Sink的坐标，并由此重建数据上传路径。文献[11]提出了一种基于虚拟节点优先级的移动Sink路径选择优化算法，以满足时延约束和最小化网络整体能耗为优化目标展开设计；而在早期的工作中[12]，提出了一种基于虚拟区域的数据采集方法-VRDG(virtual region based data gathering)，将网络划分为若干个由三个数据收集单元组成的虚拟片区，并在各片区中根据节点剩余能量及其与区域中心的距离选出遍历点。

移动Sink以恒定速度访问各遍历点，而片区内的节点则构建了基于“最大前进距离”的数据上传路径，有效提升了数据收集效率。文献[13]提出了一种基于多移动Sink的高效数据收集协议-EPBM(efficient data collection protocol based on multiple Sinks)，将网络分为4个面积相等的子域，根据各子域内节点的覆盖率及死亡率依次确定子域内Sink的移动轨迹和运动状态。在数据收集过程中，仅有簇头向移动Sink上传数据，从而延长了网络的生命期。

在上述研究的基础上，文中设计并实现了一种基于栅格的无线传感网数据收集方案-GBDG(grid based data gathering)。多个移动Sink在各栅格间分布式地开展数据收集，并根据各邻居栅格当前状态(节点数据收集总量、是否有数据溢出、栅格内节点剩余能量等)决定下一个遍历点。不仅确保了数据收集的公平性和节点能耗的均衡性，同时也有效降低了数据收集时延。

1 网络模型

不失一般性，令网络为一个M×M的矩形区域，N个不可移动的节点在网络中随机部署。除移动Sink外，所有节点的初始能量均为E0。同文献[10]类似，将网络划分为若干面积相等的栅格，如图1所示。栅格总数Cnum由N决定，见式1。

Cnum=⎣N/50」2

(1)

故各栅格的边长Cl可表示为：

(2)

图1 划分栅格及确定逗留点

由文献[14]可知，当Sink位于网络的中心位置时，网络的通信总能耗最小。故令每个栅格的中心位置为移动Sink的逗留点，命名为C。在图1中，逗留点间的虚线是移动Sink可能的移动轨迹。在后续数据收集过程中，各移动Sink将以恒定速度沿此虚线在栅格间移动。

目前，仍普遍采用经典的Heinzelman模型[15]作为无线传感网的通信能耗计算依据，如式3～5所示。

(3)

Er=Eelec

(4)

(5)

其中，εfs为自由空间模型的功率放大能耗；εamp为功率放大电路的放大系数；Et和Er分别为发送和接收1比特数据包的能耗；d为节点间距；d0为参考距离。

于是，在簇树状的无线传感网中，任一节点Si的生命期Lnode(Si)可由式6求得。

Lnode(Si)=

(6)

其中，E(Si)为Si的剩余能量；k为节点单位时间内产生的数据量；sub(Si)为Si子孙节点的数目。

2 算法描述

2.1 栅格内数据上传路径的构建

在GBDG中，栅格内的节点将数据上传至移动Sink的方式，是决定其数据收集效率的关键。在各栅格内，以C点为根，分别建立数据收集树，如图2所示。首先，将C点一跳通信范围内的所有节点作为其直接子节点(由于Sink仅在C点开展数据收集，故这些直接子节点也就是Sub_Sink节点)，即数据收集树的第一层节点，如图2中的S1、S2、S3。

图2 数据收集树的构建

栅格中，当前位于第k层的节点，将其邻居中尚不在树中的节点作为树的第k+1层节点。第k+1层的节点，分别将距离自己最近的一个第k层节点作为父节点(图2中节点S7选择了距离其更近的S2作为父节点，而非S3)，随后，继续找寻第k+2层节点，直至栅格内的所有节点都加入数据收集树为止。

2.2 相邻栅格间中继节点的选择

当数据收集树构建完成后，处于各栅格中的Sink便移动至其逗留点C，作为树的根节点，开始数据收集。GBDG规定，在网络开始运行时，多个Sink随机部署在网络中，但不允许同一栅格中同时存在一个以上的Sink。当Sink完成当前栅格的数据收集后，将移动至其所在栅格的邻居栅格，继续开展数据收集。邻居栅格是指与当前栅格有共同边的栅格。然而，对于一个栅格，其邻居栅格不止一个，且各栅格的状态(如当前是否有节点数据溢出、是否有移动Sink正在该栅格收集数据、栅格内的节点产生的数据量多少等)也不完全相同。故Sink需根据各邻居栅格的状态来决定在下一时刻向哪个栅格移动。为方便将邻居栅格的状态信息发送给移动Sink，需要为每个栅格选一个簇头，该簇头为距离逗留点最近的节点。然而，由于相邻栅格间两个逗留点的直线距离大于节点通信半径，故需要在Sink和其相邻栅格的簇头间找寻适量的中继节点，发送栅格的状态信息。这里以图1中的栅格A0和A1为例来说明该过程。

1．对于栅格A0和A1的所有节点，若其通信范围与连接栅格A0和A1逗留点的虚线相交，则被选为准中继节点。

2．在栅格A0和A1中，离逗留点最近的准中继节点被选为该栅格内的第1个中继节点。

3．对于栅格A0中所选出的第i个中继节点Si，若有准中继节点同时满足以下两个条件，则其成为第i+1个中继节点。

(1)该准中继节点在Si的通信范围内。

(2)该准中继节点到栅格A1的逗留点的直线距离小于Si到该逗留点的直线距离。

若满足上述条件的准中继节点不止一个，则按照式7计算其各自p值。p值最小者即为第i+1个中继节点。

p=d(Si,Si-1)×vd(Si)

(7)

其中，d(Si,Si-1)指的是Si到Si-1的距离；vd(Si)指的是节点Si到虚线的垂直距离，如图3所示。

图3 中继节点的选择

栅格A0和A1同时执行上述操作，若两边的中继节点能互相通信时，中继节点选择完毕。而当有中继节点死亡时，也将按此方式重新选择中继。

2.3 栅格状态的设定与邻居栅格的选择

当中继节点选出后，收集完数据的移动Sink便开始通过这些中继向其邻居栅格的簇头发送查询消息。收到查询消息的簇头，将其所在栅格的信息反馈给发出查询的Sink。这些信息包括：

(1)该栅格内所有节点目前尚未上传的数据总量；

(2)该栅格内是否有节点的缓存已经溢出；

(3)该栅格内是否有移动Sink；

(4)是否有其他移动Sink正准备向该栅格移动。

收到反馈的移动Sink根据以上信息确定邻居栅格的状态，具体方法为：

(1)当栅格中有节点缓存溢出时，将此栅格标记为黑色；

(2)当栅格中有节点所缓存的数据量大于dv时，将其标记为灰色，否则，将其标记为白色。dv的计算见式8。

(8)

其中，U为该栅格内所有节点组成的集合；cache(Si)为节点Si所能存储数据量的最大值；v为Sink的移动速度。

于是，移动Sink将根据当前邻居栅格状态，来决定下一次移往的栅格。

(1)定义所有邻居栅格组成的集合为Une，所有黑色状态的邻居栅格组成的集合为Bne，所有灰色状态的邻居栅格组成的集合为Gne，所有白色状态的邻居栅格组成的集合为Wne。

(2)若邻居栅格中存在其他Sink或已有其他移动Sink正在向其移动时，则该邻居栅格不作为目标栅格的考量。设这样的栅格组成的集合为Nne。

(3)令target=Bne∩(Une-Nne)，若size(target)>0，转步骤6。

(4)令target=Gne∩(Une-Nne)，若size(target)>0，转步骤6。

(5)令target=Wne∩(Une-Nne)。

(6)若size(target)=1，则集合target内所包含的那个栅格作为Sink的下一个移动栅格；否则，对于集合target内每一个栅格Aj，计算其Pj值，Pj值最大的栅格作为下一个移动栅格。

(9)

其中，size(target)表示集合target中元素的个数；Ti表示当前时间与节点i上次传输数据给Sink的时间差；ds(i)表示节点i当前缓存的数据量。

3 实验结果与分析

为了验证GBDG的性能，分别在网络生命期、平均通信能耗、数据收集延迟、数据传输成功率等方面与VRDG、VGDD进行比较。如无特殊说明，网内节点总数和节点通信半径，将分别设为200个和20 m，网络规模为200 m×200 m，移动Sink的移动速度为5 m/s。

图4是三种算法在数据收集延迟方面的性能对比。这里将数据收集延迟定义为移动Sink完成一轮数据收集的时间。在VRDG中，Sink的移动轨迹是固定的，由所有片区的簇头连接而成。移动Sink需遍历完所有簇头，才能完成一次数据收集，故其数据收集延迟要高于GBDG。而在VGDD中，Sink的移动轨迹是矩形的内切椭圆，其长度同样是定值，故其数据收集延迟仅与网络规模有关。在该实验中，网络边长为200 m，因此，VGDD的移动轨迹长度长于GBDG，即其数据收集延迟高于GBDG。此外，由于GBDG利用了多个移动Sink开展数据收集，且每个栅格在一轮数据收集过程中，最多只会被一个Sink访问，从而大大降低了数据收集节点等待上传的时间。

图4 数据收集延迟

图5是数据传输成功率的实验结果。

图5 数据传输成功率

与GBDG相比，VGDD在数据传输成功率方面具备一定优势。因为其片区中的簇头无需长时间缓存数据，只要确定了移动Sink的位置，栅格便可通过网络内的其他簇头，建立到达移动Sink的多跳数据上传路径。然而，这样将增大网络的通信开销。而在VRDG中，片区数量较多，且Sink必须按序移动至各片区开展数据收集，易造成部分节点因等待Sink的时间过长而产生缓存溢出。因此，其数据传输成功率较低。

图6是三种算法的网络生命期对比。

图6 网络生命期

GBDG由于采用了多个移动Sink开展数据收集，且充分考虑了邻居栅格的状态，故其能耗均衡性较好，网络生命期最长。此外，与VGDD和VRDG不同，GBDG的网络生命期并非随节点的通信半径的增大而降低。这是由于随着节点通信半径的增大，GBDG中与移动Sink直接通信的节点数量也随之增加，使得每个节点的子孙节点的数量减少，各节点的平均负载也因此降低，从而延长了网络生命期。

4 结束语

利用多个移动Sink分布式地在各栅格间开展数据收集。重点实现了基于不同栅格状态的多Sink移动方案的设计。不仅提升了无线传感网的数据收集效率，也有效降低了延迟，延长了网络生命期。

然而，在实际应用中，移动Sink自身的能量和存储空间并非无限。如何在该约束下，进一步优化多Sink的移动路径以及更好地实现多Sink间的协同，将是下一步的研究方向。