Sink节点移动的三维无线传感网数据收集算法研究*

赵克华,陈友荣*,万锦昊,任条娟,王章权,周骏华

(1.浙江树人大学信息科技学院,杭州 310015;2.中移(杭州)信息技术有限公司,杭州 311100)

无线传感网(Wireless Sensor Networks,WSNs)中所有传感节点可协同完成信息采集任务,但是目前在危险环境(如火山、放射区、有毒化工区等)监测、灾难搜救、军事领域、水下监测等应用领域中,通常采用传感节点周期性上报数据且节点位置固定不变的静态无线传感网。但是该静态无线传感网一般随机部署传感节点,很容易造成节点分布和能耗的不均匀,很容易形成监测区域的能量空穴问题,缩短了网络生存时间[1-2]。因此考虑Sink节点的移动,解决静态无线传感网的能量空穴问题,从而达到平衡节点能耗、延长网络生存时间和降低数据丢包率的目的。

目前,很多学者侧重于研究二维无线传感网下的Sink移动路径、数据收集等问题。如文献[3]建立Sink节点停留在若干位置上的网络生存时间优化模型,并求解该模型获得最优方案,但是没有考虑Sink节点的移动路径选择。文献[4]将监测区域分成若干个三角形和其外圆,Sink节点停留在圆心,采用贪婪算法获知下一时刻的停留位置,单跳收集传感节点的数据。文献[5]将传感节点分簇,并选择簇头。Sink遍历所有簇头收集数据。但是文献[3-5]侧重于考虑Sink节点的移动路径,只是采用单跳数据采集方法收集数据。文献[6-7]综合考虑Sink节点的移动路径选择和最优化方法,建立Sink节点移动的无线传感网生存时间优化模型,并提出对应方法求解。但是文献[3-7]只考虑二维无线传感网下Sink移动的数据收集问题,即Sink节点在同一个水平面上移动,没有考虑竖轴方向和三维场景,其移动路径选择方法很难适用于三维无线传感网。

目前部分学者侧重于研究三维无线传感网的节点路径规划、数据收集等问题。如文献[8]考虑障碍物的三维结构,根据高度分成多个层,并在每一个层上确定可停留位置。提出近似三维欧几里德最短路径算法寻找到目的地址的最短路径。文献[9]采用模糊聚类方法寻找最小化节点能耗的最优分簇,采用粒子群优化方法寻找最优簇头,从而解决因网络总能量消耗下降而导致的网络分裂问题。文献[10-11]提出了基于偏心率的数据路由算法,该算法将网络划分为三维子空间,在子空间中选择路由质心节点进行数据路由算法,从而降低了选举阶段节点的能耗、内部通信的能耗和数据传输跳数。但是文献[6-11]只是考虑Sink静止的数据收集方法,同样存在能量空穴问题。文献[12]提出一种Sink移动的有效数据收集算法(Efficient Data Gathering in 3D linear underwater wireless sensor networks using Sink mobility,EDG_3D)。EDG_3D考虑移动Sink节点和快递节点的线性移动,建立和求解最大化网络生存时间、最小化数据传输时延和最大化吞吐率的优化模型,尽可能降低节点的通信能耗,但是其线性移动路径较简单。

综上所述,为克服能量空穴问题和提高网络生存时间,考虑Sink节点移动。目前节点分布在同一个平面上的二维无线传感网的Sink节点移动、数据收集等问题研究成果较多,但是没有考虑竖轴方向和三维场景,其算法很难适用于节点分布在立体空间区域中的三维无线传感网。目前三维无线传感网主要侧重于到目的节点的路径规划,静态传感节点的数据收集,较少涉及Sink节点的三维移动路径选择和数据收集问题。由于Sink节点移动方向、Sink节点是否停留、数据收集方法等因素都能影响网络生存时间、数据传输率等网络性能,因此综合考虑多种因素,提出Sink节点移动的三维无线传感网数据收集算法(Data Collection Algorithm of Three-dimensional Wireless Sensor Network with mobile Sink node,DCA_TWSN)。即提出三维环境下的正方体网格划分方法,建立包括Sink移动路径选择约束、数据流量约束、能耗约束、链路约束等约束条件的数据收集优化模型。采用最优化和修正蚁群算法求解该优化模型,获得最优方案,即Sink节点能寻找到较优移动路径,传感节点能寻找到较优数据传输方案,从而提高网络生存时间和数据传输率、降低移动路径长度、平均节点能耗方差和丢包率。

1 算法假设和基本原理

在 DCA_TWSN中,假设:在三维立体监测区域中,存在多个位置静止的传感节点和一个可移动的Sink节点。移动Sink节点可移动到监测区域的任一正方体中心;静态传感节点安装有相同类型的传感器且具有相同的能耗参数,初始能量和通信半径;静态传感节点和Sink节点可通过GPS、北斗等卫星定位模块或其他定位算法,获知自身的位置坐标;静态传感节点的初始能量有限。

图1 正方体网格划分

如图1所示,将三维长方体监测区域分成若干个大小一致的正方体网格,并根据从左到右,从前到后和从上到下的原则对每一个正方体网格进行编码。如Cu(Lv,Hv,Gv)表示从左开始计数的第Hv列中从前到后开始计数的第Lv行中从下到上的第Gv个正方体网格。如图2所示,静态传感节点分布在长方体监测区域内,移动Sink节点随机分布在某一个正方体网格中心,且节点可获知自身的位置。当网络运行后,移动Sink节点根据静态传感节点的信息和正方体网格中心位置,选择移动到下一时刻的邻居网格中心位置上收集静态传感节点的信息。如果静态传感节点能与Sink节点通信,则将数据通过多跳的方式发送给Sink节点,否则将数据存储到缓存中。但是 DCA_TWSN仍需要解决以下二个问题:一是如何考虑Sink节点的移动路径选择和Sink节点与静态传感节点的数据通信,建立包括移动选择约束、数据传输约束、流量最大约束、节点能耗约束等约束条件的Sink节点数据收集优化模型。二是如何采用修正的蚁群算法求解优化模型,获得最优方案。这二个问题的具体解决如下。

图2 算法原理

2 优化模型的建立

网络启动后,Sink节点停留在正方体网格中心间移动收集传感节点数据。传感节点判断自身是否能与Sink节点通信,如果能,则将数据通过多跳方式发送给Sink节点,否则感知数据,并更新缓存空间。根据上述分析,数据收集算法应让Sink节点在最短的移动路径下能全覆盖所有静态传感节点,其数据传输率和网络生存时间尽可能高且移动路径长度尽可能小,即建立以下优化模型。

max(RT/Lpath)

(1)

s.t. CRate==1

(1a)

(1b)

(1c)

(1d)

(1e)

(1f)

(1g)

(1h)

(1j)

(2)

(3)

(4)

式中:Cmax表示传感节点的最大存储容量。约束条件(1g)表示在整个网络生存时间内节点能耗不大于其初始能量。约束条件(1h)表示链路传输的数据总量有限,节点间数据传输值不大于最大链路传输量。

3 算法求解

3.1 Sink节点移动路径的适应度值

假设已知能满足约束条件(1a)-(1e)约束条件的Sink节点移动路径和该Sink节点路径能最大化优化模型(1)的目标函数,且Sink节点是在移动路径上的每一个网格中心停留和收集数据,则将Sink节点沿着该移动路径的数据收集转换成若干个在某一个网格中心位置上停留的优化模型,即当Sink节点停留在位置g上时,以多跳方式接收传感节点的数据。不能与Sink节点通信的传感节点处于休眠状态,自动更新自身的存储数据。此时Sink节点的数据收集应该考虑尽可能让其通信能耗短,网络生存时间最大,即Sink节点停留在位置g上时的数据收集优化模型为:

min(qg=1/Tg)

(5)

(5a)

(5b)

(5c)

(5d)

(6)

(7)

(8)

fitness=RT/Lpath

(9)

3.2 蚁群算法求解

3.1节可获得Sink节点路径已知的所有节点间的数据转发量,即最优数据收集方案。该数据通信方案和已知的Sink节点路径,可构成优化模型(1)的最优解。因此优化模型(1)需解决以下路径优化模型。

(10)

蚁群算法(Ant Colony Optimization,ACO)是一种受真实蚂蚁觅食行为启发的算法。在ACO中,蚂蚁随机产生,并在构建图上不停行走搜索解决方案。这种搜索行为使得ACO适合于解决旅行商等组合优化问题,且已成功应用于许多工业和科学问题。因此采用修正的蚁群算法求解优化模型(10),寻找Sink节点的移动路径。如图3所示。

图3 DCA_TWSN的收敛图

具体求解步骤如下:

步骤2 初始化蚂蚁m的初始位置,并令初始位置为蚂蚁m的当前位置。

步骤3 蚂蚁m在当前位置上停留,分析所有传感节点是否能以多跳的方式与该位置上的Sink节点通信,如果能,则标记传感节点,表示Sink节点已经覆盖到该传感节点。统计所有传感节点是否全覆盖,如果全覆盖,则m=m+1。如果m>M,则获得符合约束条件(1a)-(1e)的蚂蚁m移动路径,m=1,跳到步骤5,否则跳到步骤2。如果不是全覆盖,则跳到步骤4。

步骤4 记录当前网格,并让当前位置网格覆盖次数加1。根据当前位置,获得邻居网格集合。选择该邻居网格集合中的网格覆盖次数最小的网格,获得可停留的下一时刻网格集合。通过式(11)计算下一时刻网格集合中每一个网格的概率,并计算累计概率。随机选择一个[0,1]的随机数。选择累计概率大于该随机数的网格,并从中选择第一个网格作为下一个时刻的停留网格,令当前位置为该下一个时刻的停留网格,跳到步骤3。

(11)

步骤6 通过式(9),计算蚂蚁m的适应度值。m=m+1。如果m>M,则完成所有蚂蚁移动路径的适应度值计算,跳到步骤7,否则跳到步骤5。

步骤7 根据当前所有蚂蚁的移动路径和适应度值,挥发所有网格的信息素值。且选择当前适应度值最大的蚂蚁,增加该蚂蚁移动路径上的所有网格的信息素。

(12)

式中:fitness(k)表示第k个迭代中最优适应度值,Rho表示挥发因子,Q表示信息素增加因子。

步骤8 如果k

循环执行关键步骤2～步骤8,则可获得优化模型(1)的一个最优解,即当前最优的Sink节点的移动路径和传感节点的数据传输路径,从而达到提高网络生存时间和数据传输率,降低移动路径长度的目的。

4 算法仿真

4.1 仿真参数选择

如表1所示,选择表1中参数进行仿真实验,采用MATLAB软件进行仿真实验,获得Sink节点的移动该路径长度,网络生存时间,传感节点的平均数据传输率,平均节点能耗方差和丢包率等性能参数值。其中网络生存时间,传感节点的数据传输率分别根据式(7)和式(8)计算,Sink节点的移动该路径长度定义为Sink节点经过的网格数量,平均节点能耗方差定义为网络生存时间内,传感节点消耗能量的方差。由于移动传感节点会因自身数据存储容量有限导致自身数据的丢失,则丢弃的数据量定义为:

(13)

(14)

式中:Losstotal表示所有传感节点产生的数据包总量。

表1 仿真参数表

4.2 仿真结果分析

首先分析 DCA_TWSN的收敛性。选择移动传感节点个数100,Sink节点的最大数据收集跳数4和表1中参数,循环200次计算 DCA_TWSN中当前蚂蚁的最优适应度值,获得收敛图3。如图3所示,前期经过多次迭代,每轮最优适应度值不断上升。当到50次迭代以后,每轮最优适应度值一直收敛到114。因此DCA_TWSN是收敛的,可寻找到优化模型(1)的最优解。

4.2.1 Sink节点的最大数据收集跳数变化的仿真结果分析

选择Sink节点的最大数据收集跳数1,2,3,4,5,6,选择移动传感节点个数100,选择表1中的参数,循环计算RAND、GREED[14]、EDG_3D[12]和DCA_TWSN的Sink节点的移动该路径长度、网络生存时间、传感节点的平均数据传输率、平均节点能耗方差和丢包率。其中在RAND中,移动传感节点随机选择和感知未覆盖的网格。在GREED中,移动传感节点在距离最近且未经过的网格集合中随机选择一个,作为下一个时刻的感知位置。在EDG_3D中,根据当前三维网格的数量,选择遍历所有网格的线性移动路径。在RAND、GREED和EDG_3D中,移动传感节点选择下一个时刻的停留网格方法不一致,但是采用相同的Sink节点停留在某一个网格中心的数据收集方法。具体仿真结果内容如下。

如图4所示,随着Sink节点的最大数据收集跳数增加,RAND和GREED的Sink节点移动路径长度上下起伏,EDG_3D和DCA_TWSN的Sink节点移动路径长度下降,但是DCA_TWSN的Sink节点移动路径长度都远低于RAND、GREED和EDG_3D的Sink节点移动路径长度。这是因为:RAND中移动传感节点从周围邻居网格中心中随机选择一个作为下一跳的停留网格中心,这种选择比较盲目和随机,因此其Sink节点移动路径长度最短。GREED从距离最近的邻居网格中心中随机选择未停留过的网格中心作为下一个停留网格,选择也具有一定的随机性。EDG_3D是寻找遍历所有网格中心的线性移动路径,并从头开始选择能全覆盖传感节点的最小子路径。这三个算法的都没有考虑寻找移动路径长度最优问题,因此其Sink节点的移动路径长度较长。DCA_TWSN在蚂蚁选择路径时将Sink节点的移动路径长度作为该路径适应度值的一个重要参数,并影响路径上网格的信息素更新,经多次迭代后蚂蚁能寻找到较优移动路径,从而降低其移动路径长度。

图4 Sink节点的移动路径长度比较图

如图5所示,随着Sink节点的最大数据收集跳数增加,RAND、GREED、EDG_3D和DCA_TWSN的网络生存时间明显下降,但是 DCA_TWSN的网络生存时间远大于RAND、GREED、EDG_3D的网络生存时间。这是因为:随着Sink节点的最大数据收集跳数增加,与Sink节点通信的传感节点数量变大,处于Sink节点周围的传感节点需要转发更多的其他传感节点的数据,其能耗增加,因此所有算法的网络生存时间降低。但是由于DCA_TWSN将网络生存时间作为适应度函数的重要参数之一,且在蚁群求解过程中蚂蚁根据信息素的结果,尽量向具有较多传感节点的网格移动,降低了这些节点的能耗,从而提高了网络生存时间,RAND、GREED和EDG_3D在移动路径选择时没有考虑网络生存时间,这三个算法的网络生存时间相对较短。

图5 网络生存时间比较图

如图6所示,随着Sink节点的最大数据收集跳数增加,RAND、GREED、EDG_3D和DCA_TWSN的传感节点的平均数据传输率会提高,但是DCA_TWSN的平均数据传输率略高于RAND、GREED、EDG_3D的平均数据传输率。这是因为:随着Sink节点的最大数据收集跳数增加,传感节点有更多的机会与Sink节点通信,上传自身感知和其他传感节点的数据,RAND、GREED、EDG_3D和DCA_TWSN的平均数据传输率相对提高。但是由于 DCA_TWSN能寻找到较优的移动路径,增加了传感节点与Sink节点的通信时间,导致所有传感节点成功发送数据的概率提高,因此其传感节点的平均数据传输率变大。

如图7所示,随着Sink节点的最大数据收集跳数增加,RAND、GREED、EDG_3D和DCA_TWSN的平均节点能耗方差上升,但是DCA_TWSN的平均节点能耗方差低于RAND、GREED、EDG_3D的平均节点能耗方差。这是因为:随着Sink节点的最大数据收集跳数增加,Sink节点在某一个网格中心停留时,其接收的传感节点数量变多,这导致跳数较少的传感节点不仅需要发送自身的数据,还需要承受更多其他传感节点的数据,增加自身能耗,导致传感节点间能量消耗不平衡,平均节点能耗方差上升。但是 DCA_TWSN建立了三维无线网数据收集算法的优化模型,采用蚁群算法求解该模型,获得全覆盖所有传感节点的最优移动路径,让传感节点尽可能出现在Sink节点的附近,平衡了传感节点的能量消耗,降低了平均节点能耗方差。

图7 平均节点能耗比较图

如图8所示,随着Sink节点的最大数据收集跳数增加,RAND、GREED、EDG_3D和DCA_TWSN的丢包率下降,但是DCA_TWSN的丢包率低于RAND、GREED和EDG_3D的丢包率。这是因为:随着Sink节点的最大数据收集跳数增加,能与Sink节点通信的传感节点数量变大,导致传感节点有更多的机会和时间与Sink节点通信,从而提高了自身的数据传输率,降低了丢包率。同时 DCA_TWSN找到了能全覆盖传感节点的移动路径,让所有传感节点都能与Sink节点的通信,发送自身的数据,因此其丢包率最低,当Sink节点的最大数据收集跳数为5和6时,其丢包率接近于0。

图8 丢包率比较图

总之,不管Sink节点的最大数据收集跳数如何变化,DCA_TWSN都能寻找到较优的Sink节点移动路径,从而提高网络生存时间和传感节点的平均数据传输率、降低移动路径长度、平均节点能耗方差和丢包率。

4.2.2 传感节点数量变化的仿真结果分析

选择Sink节点的最大数据收集跳数4,选择移动传感节点个数100,120,140,160,180,200和选择表1中的参数,循环计算RAND、GREED、EDG_3D和DCA_TWSN的Sink节点的移动该路径长度,网络生存时间,传感节点的平均数据传输率,平均节点能耗和平均丢包率。具体仿真结果如下:

如图9所示,DCA_TWSN的移动路径长度远低于RAND、GREED和EDG_3D的移动路径长度,且其移动路径长度不受传感节点数量的影响。这是因为:不管传感节点数量多少,DCA_TWSN都能通过求解优化模型(1),寻找到权衡网络生存时间、移动路径长度和传感节点数据传输率的Sink节点移动路径,降低了其移动长度。而RAND、GREED和EDG_3D在移动过程中,没有考虑传感节点与Sink节点的通信问题,其移动长度较长。

图9 移动路径长度比较图

如图10所示,DCA_TWSN不受监测区域内传感节点数量的影响,各个传感节点数量下的网络生存时间相差不大,且远高于RAND、GREED、EDG_3D的网络生存时间。这是因为:DCA_TWSN可根据传感节点数量和位置,通过蚁群算法自动寻找较优的Sink节点路径方案,让所有传感节点都能与Sink节点通信,较好完成了Sink节点的数据收集,而其他算法都存在一定的局限性,因此DCA_TWSN的网络生存时间最高。

图10 网络生存时间比较图

如图11所示,DCA_TWSN充分利用传感节点的信息,评估每个蚂蚁的适应度值,实现传感节点数据的有效上报,其数据传输率最高。RAND、GREED和EDG_3D在Sink节点路径寻找过程中没有考虑数据传输率,传感节点的数据通信路径较差,其数据传输率较低。传感节点数量变化的各个算法的平均节点能耗方差和丢包率的仿真结果和具体原因与4.2.1节中Sink节点的最大数据收集跳数变化下的仿真结果和具体原因基本一致,本文不再重复说明,可参考4.2.1节。

图11 传感节点的平均数据传输率比较图

5 总结

本文提出一种Sink节点移动的三维无线传感网数据收集算法(DCA_TWSN)。首先,提出算法假设、三维环境下的正方体网格划分方法和基本原理。其次,用数学公式建立包括Sink移动路径选择约束,数据流量约束、能耗约束、链路约束等约束条件的数据收集优化模型。接着,提出了Sink节点移动路径的适应度值计算方法,即采用最优化方法求解已知Sink节点移动路径的数据收集优化问题。采用修正的蚁群算法求解Sink节点的移动路径问题,获得最优方案。最后给出算法的仿真参数,仿真比较DCA_TWSN、RAND、GREED和EDG_3D的性能。

总之,不管Sink节点的最大数据收集跳数和传感节点数量如何变化,DCA_TWSN都能寻找到较优的移动路径和数据传输方案,从而提高网络生存时间和传感节点的平均数据传输率、降低移动路径长度、平均节点能耗方差和丢包率。但是DCA_TWSN 算法采用次梯度算法求解优化模型(6),采用修正的蚁群算法求解优化模型(10),其算法的时间复杂度相对较高,因此下一个阶段目标是通过Sink节点和传感节点的相互通信,获知周围传感节点的信息,分布式计算Sink节点的移动路径和传感节点的通信方案,从而降低算法的时间复杂度。