无线传感器网络中移动sink节点的路径规划

柏 琪，朱晓娟

(安徽理工大学 计算机科学与工程学院，安徽 淮南 232001)

0 引言

无线传感器网络中通过多跳路由汇聚到sink节点是传统的数据收集方法。离sink节点很近的传感器节点或簇头，被视为sink节点的中介，需要转发远处传感器节点的数据包，这会导致能量有限的传感器节点快速消耗掉自身的能量，从而死亡，这被称为热点或能量空洞问题[1-4]。为了避免这种情况，使用移动sink节点来解决这一问题，将sink节点安装在一些车辆上，围绕网络区域移动进行数据收集。使用移动sink进行数据收集有以下优点：

① 传感器节点将数据转发到移动sink节点的跳数相对较小，这会减少拥塞和数据包丢失的概率[5]；

② 移动sink节点的存储和计算资源较充分；

③ 使用移动sink节点，在很大程度上减少某些传感器节点数据转发负载，可以更好地利用传感器的能量，从而延长了整个网络的寿命。

目前，sink节点移动的轨迹选择主要有3种类型：随机移动、固定移动和可控移动[6]。

在基于随机移动的方法中，sink节点的移动轨迹不是预先设定的。例如，节点放在动物身上，动物的移动轨迹是随机的，虽然这个方案很容易实现，它的优点是保证移动sink节点到每个节点进行收集数据的概率是相等的，但其性能是不确定的，因为它可能会产生很长的路径，造成链路断开，产生额外的能量损耗。

在固定移动中，移动sink节点将移动sink访问一些预先指定的位置，并从传感器节点组中收集数据，它需要只访问有限数量的节点，但不会根据无线传感器网络节点的能量情况进行路线改变，缺乏灵活性。

在可控移动中，可以根据路径反馈的信息进行路径规划。因此，它能够在指定延迟限制内进行数据收集，可以很好地平衡网络寿命与延迟的问题。

1 相关工作

近年来，为了解决能量空洞问题，提高无线传感器网络的生命周期，许多算法已被提议用于移动sink节点的路径规划。周晖等人[7]提出移动多sink 生物启发式路径规划算法，采用蚁群优化作为上层算子，根据网络运行过程中的变化，即节点数量和能量变化，实时优选下层算子集，选中的下层算子集规划各移动sink节点的路径。黄冰倩等人[8]首先利用图论知识，把无线传感器网络看成一个连通的无向图，将传感器节点转化成图的顶点，并选取虚拟信标节点，利用蚁群算法对选取的节点进行遍历，从而获得移动路径。俸皓等人[9]提出了一种新的基于萤火虫群的路径规划方法。首先依据问题的特性对可行解空间进行了压缩；然后为提高算法在高维解空间的搜索效率，对离群萤火虫粒子设计了变异操作并设计了个体逐维移动的方式，提高了算法的求解精度并加快了算法的收敛速度。文献[7-9]运用生物智能的路径规划算法，这类算法没有考虑现实中的适用性，数据的处理和成本太高。陈友荣等人[10]提出了一种高效的距离感知路由算法,通过无线传感器网络的移动汇聚，汇聚节点以一定的速度沿网络边界采集监控数据。但是该算法中提到的障碍物和移动sink节点的移动感知问题没有得到解决，且过于复杂导致数据传输速率受到影响。

与以上算法相比，结合实际情况，本文考虑合理规划移动sink节点的路径，最大限度延长网络寿命。首先将移动sink节点通信范围内的传感器节点的剩余能量信息传达给移动sink节点,然后通过能量密度与移动路径选择算法选择出移动sink的最佳转向点，得到sink节点移动的最优路径。对于能量密度和具体的移动路径选择算法会在后面进行详细介绍。

2 网络模型

2.1 问题描述

无线传感器网络是使用同构的传感器节点随机部署在H×W的长方形区域内，其中每个传感器节点都有有限电源和相同的通信半径，并且移动sink节点能量不受限制。本文为了避免移动sink节点进行不必要的移动，规定检测区域内的节点都为簇首，该网络为骨干网络[11]。

在监测区域内，假设传感器节点呈现正态分布，四周的节点分布较稀疏，中间部分比较集中。移动sink节点从矩形区域的左边中点出发，根据规划的路径进行匀速移动，在通信范围内进行数据的收集，直到区域右边中点，看做完成一轮采集。本文将矩形区域划分成若干个子区域，以便更准确进行转向点选择。以下是一些假设。

① 每个传感器节点在部署后保持静止并具有唯一识别号码；

② 假定在每个转向点位置，移动sink节点的逗留时间可以忽略不计；

③ 所有通信都通过共享无线电建立；

④ 网络生命周期定义为直到第一个节点死亡为止；

⑤ 假设从传感器节点到移动sink节点没有重传数据，移动sink节点负责将收集到的数据传到信息处理中心，且移动sink节点运动速度恒定不变。

2.2 能耗模型

本文提出相应的能量模型，其中单个传感器节点在发送或接收k比特数据所需的能量为：

E1=Eeleck。

(1)

在信号放大器件上消耗的能量为：

E2=Eampd2k，

(2)

式中，Eamp为单位功率放大器的能量消耗，d为两个节点之间的距离。所以接收消息时只存在第一步的能量消耗；发送数据所消耗的能量为两步的和，即：

ET=E1+E2。

(3)

2.3 能量密度

本文提出的能量密度是指单位区域内传感器节点的能量。它在一定程度上反映了传感器网络负载是否平衡，对于移动sink节点的转向点也有很大影响。使用二分法划分区域，在能量密度较高的区域会尽可能多地划分子区域，增加转向点的数量，避免因某个节点承载过多的转发任务而造成能量耗尽、节点死亡的后果，达到传感器网络的能量平衡。能量密度的计算公式如下：

ED=RE/N，

(4)

式中，ED为能量密度，RE代表子区域内传感器节点的剩余能量总和，N为子区域内无线传感器节点的数量。

对于一个区域内能量密度大小，以整个网络的能量密度T为标准，如果ED>T，则说明该子区域能量密度大，需要考虑增加转向点；相反，如果ED

3 转向点选择与子区域划分

首先对移动sink节点路径规划的必要性进行研究，如图1所示。移动sink节点从A移动到B，经过整个传感器网络区域，这个路径是一条固定的直线，靠近该路径的节点可以把数据直接传送给移动sink节点，但是由于传感器节点的能量有限，远离该路径的节点想要发送数据必须经过多跳转发才能成功。由此可以看出，这样的路径影响整个网络的生命周期。

为了解决该问题，本文提出了转向点的概念，如图2所示。移动sink节点同样是从A移动到B，但在移动过程中，它不是一条固定的直线路径，而是经过多次转折，转折的目的是为了尽可能保证分布在路径两边的传感器节点传送数据到移动sink节点需要转发的次数比较少，也就是跳数减少，这样大大均衡了网络的能量负载，提高生命周期。

图1 直线移动Fig.1 straight line movement

图2 规划路径移动Fig.2 Planning path movement

图3 k为4时转折点结果Fig.3 K is the result of turning point at 4

图4 k为2时转折点结果Fig.4 K is the result of turning point at 2

4 簇首到移动sink的最短路径

本文在设计移动sink的移动路径有一个重要前提，在数据传输阶段，如果传输数据距离移动sink较远，不在其通信范围内，此时通过另外簇首节点进行数据转发，要保证传输数据路径是最短路径，以跳数来判断传输路径是否为最短路径。具体步骤用Dijkstra算法[14-16]来求解。

① 给定两个集合：已求出最短路径节点集合S(初始时，在S中添加一个源节点V1)和未求出最短路径的所有节点的集合U。

② 从U中选取一个距离V1最小的顶点K加入到S中(选定的距离就是V1到K的最短路径)。且只有当该距离小于传感器节点的一跳范围时，才能加入S，如果两个节点不能通过一跳到达，距离就为∞，排除该节点。

③ 以K为新考虑的中间点，修改U中各节点的距离。若从源节点V经过顶点到节点U的路径距离比原来不经过节点K的路径距离短，则修改V1到U的距离。

④ 重复步骤②、③直到sink节点加入到S中，就能知道源点V1到sink节点进行数据传输的最短路径。

5 路径规划算法

通过以上子区域的划分、转向点的选择和传输数据的最短路径可以得出最终的路径规划算法。算法思想为：将传感器网络划分为合适数量的子区域，找出移动sink节点的转向点，在转向点中选择最优的，依次连接所有最优转向点，最后得到移动sink节点的最佳路径。具体算法如下。

步骤1：以中轴线将传感器网络区域一分为二，分为左右两个子区域，并进一步划分多个子区域，选择候选转向点。

输入：整个区域簇首的剩余能量：R1.R2...Rm...Rn

左子区域内各个簇首的剩余能量：R1.R2...Rm

右子区域内各个簇首的剩余能量：Rm...Rn

整个区域内簇首节点数量：n

左区域内簇首的数量：m

右区域内簇首的数量：n-m

过程：

1：forR1 toRm

EDL=(R1+…+Rm)/m∥计算左子区域的能量密度

2：forRmtoRn

EDR=(Rm+…+Rn)/(n-m) ∥计算右子区域的能量密度

3：forR1 toRn

T=(R1+…+Rn)/n∥计算整个区域的能量密度

4：ifEDL

利用第3提到的子区域划分方法进行区域划分

5：else

该区域不再进行子区域划分

6：end

输出：划分区域线上的点为候选转向点

步骤2：选择最优转向点。

输入：候选点A(X1,Y1),B(X2,Y2)…(Xn,Yn)，其中X1=X2= …=Xn,Y1=k1Δy,Y2=k2Δy…Yn=knΔy(k为常数,Δy为固定网格格数)

各个簇首到sink节点的跳数h1,h2…hn

过程：

1：forh1 tohn∥选择A作为转向点，遍历所有簇首节点到sink节点的跳数

RA=(h1+h2+…hn)/n∥ 选择A作为转向点传输数据所需要的平均跳数

2：forh1 tohn∥选择B作为转向点，更新步骤1中簇首节点到sink节点的跳数

RB=(h1+h2+…hn)/n∥ 选择B作为转向点传输数据所需要的平均跳数

3：ifRA

takeA intoS[i][j] ∥S为最优转向点的集合

4：else

take B intoS[i][j]

5：循环操作到所有转向点比较完成

6：end

输出：最优转向点的集合S

步骤3：sink节点以匀速依次经过最优转向点，该路径就是sink节点的移动路径。

图5～图8分别为移动sink节点在不同迭代操作次数下，移动路径的改变。

图5 初始状态Fig.5 Initial state

图6 第1次迭代Fig.6 First iteration

图7 第2次迭代Fig.7 Second iteration

图8 第3次迭代Fig.8 Third iteration

从图中可以看出，初始状态有些簇首需要将数据包转发4～6次，随着不同时期下路径的改变，传感器节点需要转发的数据包越来越少，迭代3次后传感器节点最多只要转发2次，能量消耗也趋于平衡，生命周期也会大幅度延长。

6 仿真实验

采用Matlab进行仿真，在实验中，假设在监测区域为300 m*400 m的范围，300个传感器节点随机分布，传感器节点的传输半径为40 m，普通节点的起始能量为1 J，节点发送单位字节数据的能耗为100 nJ，接收单位字节数据的能耗为20 nJ，sink节点沿着规划路径匀速运动，每个周期产生的平均数据为1000 B，规定从区域左边边界移动到右边边界为一个周期，完成一个周期的数据收集为一轮。仿真实验的约束条件为：① 传感器节点静止不动，移动sink节点没有能量约束；② 在一个周期内，无数据传输的节点不参与路径规划。

为了验证本文提出路径规划算法的有效性，将其与文献[5]中提出的sink节点固定转向移动算法进行对比。固定转向移动算法在转向点的选择上不考虑网络的剩余能量，在sink节点移动之前已经确定了转向点，固定在监测区域的水平边界上，sink节点在转向点之间直接进行移动。仿真实验将从每轮存活节点百分比、节点的平均剩余能量、网络平均跳数三个方面进行判断，比较两种算法的网络生命周期。

图9是在收集数据的不同轮数下，传感器节点存活的百分比。从图中可以看出，与文献[5]中的sink节点固定转向算法相比，sink节点固定转向算法在2 500轮时就出现了节点死亡，本文算法在3 500轮后才出现节点死亡，到6 000轮时，存活节点还剩60%，而sink节点固定转向算法只存活了一半，这说明了本文提出的算法能有效延长网络的生命周期。

图9 每轮存活节点百分比Fig.9 Percentage of surviving nodes in each round

图10为传感器网络中两种算法节点平均剩余能量的曲线对比图。由图10可知，本文设计的移动sink节点路径规划算法与sink节点固定转向算法在工作的前25 s，能量消耗的差距并不大，但是随着时间的进行，sink节点固定转向算法的能耗问题就显现出来，能量消耗明显加快，由此可以判断，本文提出的算法很大程度上解决了能耗问题，延长了网络生命周期。

图10 节点平均剩余能量Fig.10 Average residual energy of nodes

图11为网络平均跳数对比图。对于sink节点固定转向算法，在前50 s没有传感器节点死亡，网络平均跳数保持平衡，本文算法平均跳数略有下降，随着网络运行时间的增加，两种算法下传感器网络的平均跳数都出现明显下降。但是，本文算法对应的网络平均跳数始终低于sink节点固定转向算法，有效降低了数据丢包的概率与传感器节点能耗，从而达到延长网络生命周期的目的。

图11 网络平均跳数Fig.11 Network average hops

7 结束语

针对无线传感器网络中的能量空洞问题，提出了移动sink节点路径规划的算法，该算法使用二分法划分区域，基于传感器节点的能量密度选择转向点的位置。仿真结果表明，本文所提出的方案可以减少能量空洞问题，从而延长网络寿命。与现有算法比较后，显示出它在延长网络生命周期方面的优越性。下一步工作的重点是分析不同数量移动sink节点的路径规划以及它们之间如何协调收集数据问题。