基于Dubins曲线的无线传感网聚类移动数据采集算法*

张美燕,蔡文郁

(1.浙江水利水电学院电气工程系,杭州 310018;2.杭州电子科技大学电子信息学院,杭州 310018)

对于能量敏感的无线传感器网络而言,数据收集过程的低能耗性以及能量均衡性要求更加重要。基于固定Sink节点的静止数据采集方式容易造成网络节点能量消耗不均衡,从而使得整体网络过早地失效,基于移动Sink节点的移动数据采集方式可以用移动Sink的有序巡航采集来弥补传感器节点的能量消耗[1-3]。因此利用类车型Sink节点实现无线传感器网络的移动数据采集,可以提高网络的能耗均衡性,从而有效延长网络生命周期。

近几年来,无线传感器网络移动Sink数据采集方式得到了研究[4-8]。陈友荣等人[4]提出了移动无线传感网的Sink节点移动路径选择算法:Sink节点采用分布式最短路径树算法收集k+1跳通信范围内传感节点的相关信息和感知数据,根据停留次数、合力大小和方向等信息计算当前网格中心的停留时间和下一个停留网格中心。陈友荣等人提出一种移动传感网的Sink节点移动路径规划算法[5]:将Sink节点的数据收集范围分解成多个圆环,将监测区域分解成多个网格,根据Sink节点的停留位置和多跳通信方式建立Sink节点移动的网络生存时间优化模型。常捷等人[6]提出了基于最优路径的移动Sink数据收集方案,根据最小权值启发式算法得到汇聚节点的集合,然后求出移动Sink的最佳驻留点集合。Kenneth等人[7]提出了MULE和SENMA两种方法来实现单跳和多跳方式的移动数据采集,并对传感器节点构成簇的划分机制进行了研究。我们前期研究提出了一种基于Bezier连续曲线的移动Sink节点避障路径规划算法,主要针对障碍物躲避技术领域的研究。文献[9-10]将连续的Dubins曲线规划应用于水下传感器网络中,针对水下传感器网络三维立体部署的特点,将二维Dubins曲线扩展到三维立体空间。

由于无线传感器网络的节点规模一般都比较大,如果只考虑由某个或某几个移动Sink节点实现对所有传感器节点的巡航数据采集,那么规划的路线会非常复杂。而且,类车型移动Sink节点的运动特征受到Kinematic约束的限制,普通的直线型路径无法满足高效移动数据采集的实际需求。

针对以上问题,本文提出了一种基于聚类间Dubins曲线的移动数据采集算法:整个无线传感器网络被划分为多个聚类区间,聚类内采用最小生成树路由方法进行无线多跳传输,聚类间按序规划Dubins曲线进行移动数据采集,从而兼顾移动数据采集路径的平滑性与能耗优化性。

1 问题描述

本文研究的无线传感器网络处于一个长宽为L×W的矩形监测区域,N个同质传感器节点SN(Sensor Node)随机部署。数据采集点DCP(Data Collection Point)根据自身位置与剩余能量从传感器节点集中选举出。普通传感器节点将数据传输到该聚类区域内的数据采集点,移动Sink节点沿着特定的数据采集路径从一个数据采集点到另一个数据采集点进行传感数据的收集。

如图1所示,无线传感器网络被分为K=5个聚类区域,第k(k=1,…,K)个聚类区域内有1个数据采集点DCPk和Nk-1个传感器节点。以数据采集点为树根,众多传感器节点通过最小生成树构造传感数据多跳传输路径,将各个传感器节点的数据传输到数据采集点进行缓存。当移动Sink节点靠近数据采集点时,通过无线方式接收数据采集点缓存的聚类区域内所有传感器节点数据,从而实现整个无线传感器网络的移动数据采集。本文定义移动Sink节点在数据采集点DCPk和DCPj之间的移动曲线为Ckj,移动曲线Ckj的长度为L(Ckj),则移动Sink节点巡航整个无线传感器网络所有节点所行驶的路径为:

(1)

图1 无线传感器网络移动数据采集框架

本文假设移动Sink节点相对整个无线传感器网络而言,具有较为充足的能量,因此移动数据采集算法设计的焦点主要在于降低无线传感器网络中所有传感器节点的能耗,同时提高网络能耗的均衡性。

图2 类车型移动Sink节点运动模型

在直角坐标系下,类车型移动Sink节点的运动模型如图2所示,假设Sink节点的位置为q(x,y,θ),前向速度为u,最小转弯半径为ρ,则类车型移动Sink节点的运动方程[11]为:

(2)

类车型移动Sink节点在一个周期T内的运动轨迹长度为:

(3)

考虑到上述Kinematic约束[11],类车型移动Sink节点必须沿着连续且平滑的轨迹进行数据采集。Dubins路径[11]考虑了类车型移动Sink节点的转弯半径对Sink节点运动的影响,使用几何方法讨论了运动初始状态和终止状态之间的最短曲线问题。典型Dubins曲线的6种规划场景(LSL,RSR,RSL,LSR,RLR,LRL),其中L代表左转,R代表右转,S代表直线,如图3所示。

图3 Dubins曲线的6种场景(LSL/RSR/RSL/LSR/RLR/LRL)

2 基于Dubins曲线的移动数据采集算法

本文提出的基于Dubins曲线的移动数据采集算法主要包括以下几个步骤:①借鉴LEACH(Low Energy Adaptive Clustering Hierarchy)分簇算法[12-13]的聚类思想将整个无线传感器网络划分成多个聚类空间,但是采集数据点的选择并没有依据LEACH算法的簇头选择方案;②每个聚类空间根据近似质心算法选取数据采集点,其他传感器节点作为普通节点;③利用最小生成树MST(Minimum Spanning Tree)[14]方法进行聚类内传感数据收集;④各个聚类间按序规划基于Dubins曲线的移动数据采集路径;⑤移动Sink节点沿着规划路径进行移动数据采集。本文综合选取了LEACH和MST等算法,主要是考虑到这些算法的通用性与鲁棒性,就本文算法而言,也可以兼容其他更加复杂的分簇方法和数据多跳传输方法。

2.1 LEACH聚类划分与数据采集点选取方法

图4 LEACH聚类范围内数据采集点选取

2.2 基于最小生成树的聚类内节点传感数据收集机制

根据最小生成树建立的网络拓扑结构是这些网络节点之间成本最低的通信网络结构。聚类区间内的传感器节点间数据采集按照最小生成树路由方式进行数据传输,最小生成树采用Prim算法[14]构造,从而保证聚类内多传感器节点的最优数据采集路径。数据采集点收集聚类内所有传感器节点的数据后,先进行缓存处理,直到移动Sink节点寻访到该数据采集点时将缓存数据进行无线传输。采用MST方法构建聚类内的数据收集路径,可以保证多跳数据传输的能量优化。

具有N=20个节点的无线传感器网络聚类内采用MST构造数据传输路径,仿真结果如图5所示。

图5 基于最小生成树的聚类内数据传输路径

2.3 基于二维Dubins曲线的聚类间移动数据采集方法

无线传感器网络分成多个聚类区间后,聚类内的数据采集点作为接收和缓存聚类内所有传感器节点的汇聚节点,需要移动Sink节点对它进行数据采集。因此聚类间的移动数据采集问题其实就是构建一系列不同数据采集点之间的平滑Dubins曲线。

如图6所示,RSL型Dubins曲线主要包括三段:

R、S、L,其中各种类型曲线的计算方式[11]如式(4)所示:

(4)

式中:Lγ,Rγ,Sγ分别为L、R、S3种曲线的运算方式,γ为Dubins曲线中距离值为γ的区段。

图6 Dubins曲线长度计算

从图6可以计算得到RSL三段曲线的长度|L|、|R|、|S|,如式(5)所示,从而得到整个Dubins曲线的长度∮LRS=|L|+|R|+|S|[11]。移动Sink节点沿着簇间数据采集点之间构成的Dubins曲线,按序采集每个聚类区间内的传感器数据。

(5)

从上面的数学公式可知,Dubins曲线能够满足类车型移动Sink节点的Kinematic约束。对于确定的聚类数量K以及聚类巡航数据采集顺序,Dubins曲线的段数已经确定,数据采集点的次序采用遗传算法(GA)求解旅行商问题TSP(Traveling Salesman Problem)[15]的方法解决,Dubins曲线的出入角度可以根据文献[11]的最优方式组合进行选取,从而尽量降低移动Sink节点的巡航路径消耗,提高数据采集的实时性。

4 仿真结果

4.1 仿真场景设置

图7 Dubins曲线有限角度集(φ=λπ/3,λ=0,1,…,5)

本文采用类似于参考文献[5]的场景设置,假设N=100无线传感器网络节点部署在长宽为L×W= 120×120 单元的正方形监测区域,节点通信半径为r=20 单元,类车型移动Sink节点的最小转弯半径为10个单元。根据以上的场景设置,通过Monte Carlo数值仿真,可以统计出节点平均度数的分布在7～9左右,属于连通性与覆盖性较好的网络节点分布。关于聚类数量的选择,需要同时兼顾移动Sink节点的路径计算复杂度与聚类内数据采集路径的有效性。本文算法选取了聚类数量K=4和K=5两种典型情况作为仿真比较,这两种情况下的聚类内节点平均数量大概为20～25,可以很好地兼顾以上两个方面的因素。Dubins曲线的出入角度分为如图7所示情况,为了降低迭代计算量,只选取了6种情况的可选择角度。若大规模传感器网络监测区域尺寸远大于转弯半径,可以忽略非直线段数据采集曲线,本文算法从而退化为基于TSP模型的移动Sink数据采集方法。与基于TSP模型的移动Sink数据采集方法相比,本文方法在路径的最短性上并不是最优的,但是却能保证类车型移动Sink节点的Kinematic约束,这一点满足了高效移动数据采集的实际需求。

假设本文所研究的无线传感器网络中节点的初始能量设置为0.1 J,其能耗模型[16]定义如下:

(6)

(7)

为了简单起见,传感器节点能耗只考虑发送的能耗,忽略数据接收所产生的能耗。仿真采用周期轮数进行时间维度上的表征,随着仿真周期轮数的增长,传感器节点的剩余能量会逐渐下降,直到某些传感器节点因为能量耗尽而失效。

3.2 仿真结果

利用LEACH聚类思想实现的不同聚类仿真结果(通过限定整体网络的簇头比例达到K=4和K=5的两种不同聚类数量)如图8所示,归属于同一个聚类的传感器节点形状相同,聚类中的数据采集点与其他传感器节点用更大的相同形状来区分。从图8所示,聚类节点范围分布较为均匀,区域空间聚类性明显。聚类内构造MST路径结果如图9所示,基于 Dubins 曲线的类车型移动Sink节点数据采集路径如图10所示,可见移动Sink节点的数据采集路径满足类车型移动Sink节点的Kinematic约束。

图10 移动Dubins曲线数据采集轨迹

图8 无线传感器网络不同聚类结果

图9 聚类内MST构造路径结果

一般模型中假设Sink节点具有充足的能量[4-5],因此移动Sink节点的能耗不计入网络整体能耗。目前的移动Sink节点数据收集方法一般都只考虑路径长度、移动速度等方面的最优化,而本文算法保证了类车型移动Sink节点的Kinematic约束。网络能耗大小和能耗均衡性均与固定Sink节点方式进行比较,传感器节点通过MST生成树将数据多跳传输至固定Sink节点。固定Sink节点放置于无线传感器网络的中心区域,坐标为(60,60)。每轮仿真中随机选取50%的传感节点传输500 byte的数据到移动Sink节点,仿真采用多次运行取结果平均值的方式进行。网络能耗大小表征如下:随着仿真轮数的增长网络所有传感器节点的剩余能量平均值,剩余能量平均值曲线下降越平缓,说明无线传感器网络能耗性能越好。能量均衡性表征为500轮仿真之后网络所有传感器节点剩余能量的均方根值,剩余能量的均方值越小,说明无线传感器网络能耗均衡性越好。仿真结果比较分别如图11(a)和11(b)所示。从图11可以发现,两种场景下,K=5比K=4本文算法的能耗特性提升更为明显,这是因为聚类范围越小,聚类内数据传输所经过的路径越短,由此所消耗的能量也越小。因此,本文设计的移动数据采集算法与簇内星型拓扑传输和簇间星型拓扑传输的数据采集方式相比较,网络能耗明显下降了,网络能耗均衡性也得到了提高。

图11 网络数据采集能耗大小与均衡性比较

4 结语

论文提出了一种基于Dubins曲线的移动数据采集算法,采用LEACH分簇将整个无线传感器网络划分为多个聚类区间,聚类内采用最小生成树方法数据收集,聚类间按序规划基于Dubins曲线的移动数据采集路径。仿真结果表明本文提出的算法可以在保证类车型移动Sink节点路径平滑连续的基础上,降低传感器节点的能耗,延长网络生命寿命。后续工作将扩展到多个移动Sink节点条件下的优化数据采集,同时考虑多种不同场景下的性能验证。