孙泽宇,徐 琛,苏艳超,李传锋,聂雅琳
1.洛阳理工学院 计算机与信息工程学院,河南 洛阳471023
2.上海应用技术大学 计算机科学与信息工程学院,上海201418
3.河南省高技术创业服务中心 信息技术部,郑州450008
传感网中路由协议主要负责将数据报文按照路由链表某种指定路径将数据报文从源节点发送至目的节点过程[1-3]。其研究主要问题可分为:(1)如何确定最优化路径,将数据报文从源节点发送至目的节点;(2)能量问题直接影响整个传感网生存周期。对于一个鲁棒性健壮的传感网来说,能量有效可以以较长的时间来延长整个网络。在数据传递过程中,传感器节点在接收与转发数据时均要消耗其本身能量[4-6]。因此,网络能量不仅是传感网中研究的重点课题,也是传感网研究领域的热点问题。
传感网中传统的路由协议是以感知层为主的底层路由协议。其缺点是,网络中可控节点数量较少,对网络资源配置与优化计算能力较弱,算法复杂不易实现[7]。在数据传输过程往往采用牺牲节点能量为代价完成数据通信任务;数据在传输过程中跳数较多,对网络动态变化反映速度较慢。与底层路由相比,传感网中的分簇路由的特点如下:
(1)分簇路由可以提供更好的数据融合机制。簇内节点相对集中部署在某一监测区域内,采集到的数据具有很高的相似性和冗余度,经过簇首节点的数据融合操作,能够得到较高的数据融合效果。通常情况下,簇成员节点总是直接将数据发送给簇首节点,减少了数据延时,提高了传输的效率。
(2)分簇网络中,簇成员节点的功能相对简单,无需维护复杂的路由信息。这样,网络中路由控制消息的开销减小很多,节省了能量[8-9]。同时,簇成员节点在不工作的情况下,可以关闭发送和接收模块,使之处于休眠状态,也在很大程度上节省了能量的开销。
(3)分簇结构中,簇首节点充当管理节点角色,便于管理网络拓扑结构,可以对整个系统变体做出快速反应,具有较好的可扩展性,适用于大规模传感网系统。
(4)分簇路由机制在一对多、多对一的通信中非常有效,分簇路由更容易克服由于传感器节点加入、移动和失效带来的网络拓扑结构变化问题。但是,由于传感器节点自身体积较小,携带电量有限且无法充电,其通信能力、计算能力和存储能力有限,导致分簇路由所执行时间较长、错误性较高、数据融合效果不佳等原因。
本文借助于雾计算理论知识提出了A Cross-layersensing Cluster Routing Protocol Based on Fog Computer(CCRP)。该算法利用感知事件驱动机制将雾节点映射该算法通过跨层映射原理,利用感知事件驱动机制将雾节点映射到传感层,将传感网分簇路由协议的控制过程上传至雾层,通过雾计算实现事件域节点分布式成簇路由汇聚中心。在路由协议优化阶段,本文借助于粒子群优化算法(Particle Swarm Optimization,PSO)采用无竞争开销方式选举一组最佳节点担任簇首,能有效地均衡全网能量的开销,抑制传感器节点能量的快速消耗,延长了网络生存周期。
本文的主要贡献主要集中在以下四点:
首先对相关工作进行了认真地分析,结合路由算法实现数据有效传输的不足,本文给出了网络模型。针对该模型提出了雾层分簇路由结构,设定了边界参考阈值,给出了跨层分簇网络中通信节点的能耗计算模型。
为了更好地抑制节点能量消耗,本文引入了粒子群优化(Particle Swarm Optimization,PSO)。由雾节点(Fog Node,FN)计算节点的平均能量,节点能量大于或等于平均能量的节点成为候选簇首节点,簇首节点在候选簇首中产生。让每一个粒子代表一种可能的分簇方式,用目标函数评价其性能,从中寻找最优解,使目标函数取得最小值。
基于上述两点,本文以候选簇首为研究对象,缩减簇首节点的选择范围,通过能量顺序链表确保候选节点具有较高能量。同时也给出了完成传感网底层到雾层分簇路由的最优簇的数量和单跳距离d1-hop=dopt+Δd的能耗增量小于单跳距离为d1-hop=dopt-Δd 能耗增量计算方法。
为了更好地验证本文算法,本文给出了在不同时刻下节点状态分布情况和不同参数下节点剩余能量以及网络生存周期的对比过程,以验证本文算法的有效性和稳定性。
网络分簇包括簇的形成和簇头选择两个方面,其关键问题是如何在节点剩余能量随网络运行时间不断减少时,动态快速有产地寻找一组最佳节点担任簇首节点,使形成的网络分簇既能减少簇内成员节点的能耗,又能使整个网络能量消耗均衡。这是一个NP 难问题。基于智能群集随机选择的进化算法可以有效地解决上述问题,通过智能群集算法可以有效地避免陷入过早陷入最优解,找到全局最优解。
文献[10]给出了一种基于分区能耗、均衡的非均匀分簇算法。其根本思想是,将传感网进行分区,在距离汇聚节点较近的区域内分簇数量较多,各簇内成员节点数量相对较少;而远离汇聚节点的分簇数量较少,各簇内成员节点数量相对较多,从而保证承担数据中继转发任务书的簇首能减少自身的簇内通信开销,以达到节省能量开销的目的。文献[11]提出了一种基于分簇的数据汇聚传送协议。该协议通过均衡能耗的分簇方法及数据预测传送机制,可以有效地抑制节点能量的快速消耗,从而达到延长网络生存周期的目的。文献[12]利用簇内转换传输机制给出传感器节点在不同时间内不同状态转换过程。通过传感器节点不同的状态特性,完成数据传输最优路径的选择方法,最终完成数据在源节点与目的节点之间的传输。文献[13]提出Distributed and Morphological Operation-based Data Collection Algorithm(DMOA)。该算法利用分簇网络模型计算每个节点的邻居具体位置信息,同时生成一个邻居节点为中心监测区域,并计算邻居节点的剩余能量,将其按照权值的大小存储在链表当中。下一周期初始时刻,从链表中取得能量较高的节点作为簇首节点直至链表中所有节点的能量均小于阈值。文献[14]给出了一种具有能量感知能力的分簇策略。该策略采用概率模型优化选择分簇方式,既能最小化簇内距离,又能最优化网络能量。该策略采用的是轮回机制,每一轮包括两个阶段:即簇内建立和稳定阶段。簇的建立阶段采用集中控制策略,在基站完成,然后基站将分簇信息广播至每个节点,簇内和簇间路由均采用单跳方式。文献[15]提了A Trust-Based Secure Routing(TBSR)算法。其基本思想是,利用概率模型,记录路由链表中标记下一节点所接收数据的动态转换关系。当任意节点受到攻击或误传时,网络将采用回溯的方法来定位和清除恶意节点,以确保安全。链表中所标记的概率越高,则数据包在路由路径上传输的概率就越大。文献[16]在基于能量均衡的基础上,提出Mobile Data Collectors(MDCs)算法。首先,该算法从可移动基站开始进行周期性计算,将采用到的数据传输到基站,并记录其数据传输过程中所经历过的节点,构成网络图谱。其次,利用Warshall-Floyd算法构造一个完整的图,通过启发式旅游规划算法,实现整个网络路由优化过程。
上述文献的路由算法均可以实现数据有效传输,但也存在一定不足。例如:算法复杂度过高,模型过于简单,某些算法并未考虑能量问题。基于上述分析,本文主要从能量着手,以雾节点所映射到感知层的虚拟节点将传感网所采集的数据上传至雾层,并由功能强大的雾层节点对底层路由进行有效计算,从而节省整个网络能量的开销,延长了网络生存周期。
为了更好地研究CCRP协议,本文基于以下假设:
(1)所有传感器节点具有唯一ID,均匀分布在监测区域内。
(2)所有传感器节点均处于静态。基站可移动,能量不受限。
(3)初始时刻,所有传感器节点均具有相同能量,并且地位平等。
(4)传感器节点通信功率可控,即传感器节点可以根据距离来调整发射功率的大小。
(5)节点具有感知能力、计算能力和数据融合能力。
定义1(能量效率)对于跨层分簇而言,在Δt 时间内完成特定任务的能量效率为e 。也就是说,在t 时刻,单位能耗完成的任务数量为:
其中,n(Δt)表示为Δt 时间内完成同样任务数目,N 是簇内所有节点数量,Ei(t)表示t 时刻节点i 的能量值。
定义2(能量均衡)在Δt 时刻,整个跨层分簇的能量均衡可以用能量均值函数ME(Δt)和能量方差函数DE(Δt) 来衡量网络的能量均衡性,ME(Δt) 越大且DE(Δt)越小,则表示跨层分簇在Δt 时刻网络能量均衡性越好。
定义3(网络生存周期)从网络开始运行至不能网络无法正常工作为止,所持续的时间。也可以指从网络部署之后到有所有节点死亡的时间。
定义4(数据汇聚时延)数据汇聚时延包括数据融合,跨层数据传输以及跨层路由转发数据的时间的总和。
在分簇路由协议中,将监测区域内所有传感器节点划分为多个簇。每一个簇可以充当整网的一个子网,每个簇包括一个簇首节点(Cluster Head,CH)和多个簇成员节点(Cluster Member,CM)。簇成员通常是以直接方式将采用到的数据传送给族首节点;当簇的规模较大时,簇成员也可以通过多跳方式将数据传送给簇首节点。簇首节点通过多跳或单跳方式与基站进行通信。簇首节点起到网关节点的作用,负责管理和控制簇内成员节点,负责收集簇内成员节点的感知数据,根据需要进行融合并转发给基站。
当底层传感器节点所采集数据较大时,借助于雾层来实现分簇路由协议。图1给出了雾层分簇路由结构,借助于雾层节点映射到传感网中所形成的虚拟节点构成传感网的簇首节点完成路由协议选择过程。雾层分簇是传感网的一种新型分簇网络结构,这种结构的设计思想是根据所要求采集数据量的大小达到的雾层,由雾节点加以融合与计算。在传感网底层分簇的基础上,利用由底层至上的原则继续进行分簇。雾层的雾节点通过映射到传感网底层所形成的虚拟节点构成底层的簇首节点。以底层的簇首节点为中心,将簇内成员所采集的数据传至簇首节点,而后,通过虚拟节点所形成的簇首节点将数据继续上传到雾层,这样就形成了跨层传输数据的具体过程。
图1 基于雾层分簇路由结构
传感网传输能耗模型,在理想信噪比情况下传输k bit 的数据,能耗由两部分构成:发送k bit 长度数据的能量消耗和功率放大电路的能量消耗,根据传输距离的不同,发送数据能量消耗为:
其中,ETx(k,d)为传输距离(单位:m)为d 时传输k bit数据所消耗的能量,Eelec是传输或者接收单位数据的能耗;εfs和εmp分别为自由空间和多径衰落模型中单位比特数据传输单位距离时放大器的能量损耗,d0是距离边界阈值;若传输距离d ≤d0,选择εfs,如果d >d0,即选择εmp。
传感网中,节点的能量主要用于通信和执行指令。跨层分簇网络中节点的通信可以分为3 种:簇内通信、跨层报告和跨层数据转发。簇内通信主要完成簇内成员节点与簇首节点之间的数据传输;跨层报告可以采用直接或间接传输方式把簇首节点融合后数据报告上传至雾层;跨层数据转发主要完成在传感层与雾层之间距离汇聚节点较近的簇头转发距离较远的簇首节点的数据。三者之间的关联关系为:
其中,ETot表示节点的总通信能耗,Ein表示节点的簇内通信能耗,ERep_lay表示跨层报告能耗;EFor_lay表示跨层节点的数据转发能耗。在传感层进行数据采集时,ERep_lay=0,EFor_lay=0,当簇内通信量较大或通信距离较远时,ETot能量值较高,说明消耗网络能量较大。
假设在一个D 维的目标搜索空间中,群体规模为m ,群体中每一个粒子i(1 ≤i ≤m)有如下属性:第t 步迭代时,在D 维空间中的位置为Xi(xi1,xi2,…,xid),飞行速度为Vi=(vi1,vi2,…,vid),经历过的最优位置记为Pi=(pi1,pi2,…,pid)。在整个群体中,所有粒子经历过的最优位置为Pg=(pg1,pg2,…,pgd)。在t 迭代的粒子根据下面公式更新自己的速度和位置:
其中,w 为惯性权重,c1和c2为加速因子,r1和r2是[0,1]之间的随机数。在更新过程中,粒子每一维的位置和速度都被在允许范围之内。假设第d(1 ≤d ≤D)维的位置变化范围为[-xdmax,xdmax] ,速度变化范围为[-vdmax,vdmax],迭代中如果位置和速度超过边界范围取边界值。vdmax的选择取值范围为[0.1,0.3]之间。如果vdmax太大,粒子运动轨迹可能失去规律性,甚至越过最优解所在区域;如果太小,可能降低粒子的全局搜索能力,算法可能陷入局部最优解。
为了避免陷入局部最优解,本文CCRP算法采用加速因子双重迭代过程增强局部搜索与全局搜索能力;其次,在本过程实施阶段,为了提高收敛速度,本文CCRP算法采用降低c1因子数值的同时提高c2因子数值,其迭代公式如下:
其中,k 代表CCRP 算法当前迭代次数;cn为迭代结束前最后一次迭代数值;Tmax为最大迭代次数。
其主要目的在于:粒子群优化算法是寻找全局最优解的智能算法。本文采用双因子相制约思想,即:当c1减少的同时增加c2,可以更好地平衡簇内收敛过快,而产生过早陷入最优解的不足;经过一轮或多轮周期后,该簇内的所有成员节点位置信息均处于平衡状态;如果单纯地增加惯性权重w 的数值,虽然可以获得较为理想的新位置信息的同时也可以避免“早熟”现象,但是其算法的收敛速度将会变慢,不利用于全局优化。对于整个监测区域而言,本文利用上述过程,采用多次重复上述操作完成对整个监测区域的位置的优化,从而达到了全局优化的目的。
传感网底层应用PSO算法实现网络分簇。首先,基于所有节点的能量信息,由雾节点(Fog Node,FN)计算节点的平均能量且大于或等于全网的平均能量时,该节点将成为候选簇首节点,这样可以有效地缩减簇首节点的选择范围同时保证了候选簇首节点具有较大的能量。
假设网络包含N 个节点,预先定义分为K 个簇,候选簇首数量为M ,且M >K,则可能的分簇方式有C种,在其中确定最佳的分簇方式是一种最优化问题。应用PSO算法解决这个问题,使每一个粒子代表一种可能的分簇方式,用目标函数评价其性能,设置m 个粒子组成群体在C种可能的分簇方式中寻找最优解,使目标函数取得最小值。该目标函数定义如下:
其中,f1为分簇紧凑性评价因子,等于节点至雾点映射到传感网底层的虚拟节点最大平均欧氏距离。d(ni,CH(p,k))是节点ni到映射雾节点(Map Fog Node,MFN)的欧氏距离,|C(p,k)|是粒子p 中簇Ck的节点数量;f2为簇头能量评价因子,等于网络中所有节点ni,i=1,2,…,N当前能量之和簇首当前能量之和的商;β 为各评价因子的权重系数。
定理1在面积为L2正方形区域中,完成传感网底层到雾层分簇路由的最优簇的数量为:
其中,dacr为数据压缩率,为簇首节点到雾节点距离,为簇首节点到映射雾节点距离,N 是传感器节点数量。
证明网络的最优分簇数,可以通过计算网络每轮消耗的能量来求解。PSO 分簇算法和映射雾节点的确定可以雾层中完成,不消耗节点能量。通过映射雾节点确定最优簇首组合和簇内节点数量。假设控制报文发送消息长度为k,网络节点数量为N ,则该时刻网络消耗的能量为:
在网络稳定阶段,K 个簇首接收各自成员节点发送的k bit数据包,将这些数据和自身的数据事例为k bit数据包后发给映射节点。数据融合的能量开销为ED,则该阶段所有簇首消耗的能量为:
簇内每个成员节点发送k bit 数据包至簇首节点所消耗的能量为:
其中,CNi表示第i 个簇节点数量。由于簇的规模一般来说比较小,成员节点至簇头的距离通常小于d0,每个簇所占二维区域的面积为:
簇内成员节点的数量为N/K 。一般情况下,这是一个节点颁布密度ρ(x,y)的任意形状区域。假设簇首位于簇区域的中心,则:
为了计算方法,把簇形区域近似看作为圆形区域,其半径为:
由于数据压缩和数据融合所消耗的传感器节点能量较小,因此dacr×Eelec+ED值近似为0,公式(27)化简可得:
簇首节点利用PSO算法在其邻居簇首集合中,选择其中继节点RNi,中继节点RNi在所有的候选节点中上具有最小的代价函数,定义如下:
其中,Ene(si)表示簇首si的邻居簇首剩余能量均值,Ecu(sj)表示簇首sj的剩余能量均值;NCH(sj)表示簇首sj的成员节点数量;NCH(si)表示簇首si的邻居簇首成员节点数量的均值;d|si-sj|表示簇首si到簇首sj的距离;d|sj-sFN|表示簇首到雾节点之间的距离。α1、α2、α3为权重系数,且α1+α2+α3=1 。因此,Cost(RNi)=min{Cost(i,j)}。如果簇首si的中继节点是本身,则直接发送数据至映射雾节点;否则,簇首si发送数据至中继节点RNi。
在跨层分簇结构中,映射雾节点完成一次任务,即接收其成员节点和下层簇首节点的数据并完成数据融合,并向上层雾节点或基站转发融合后的数据。如果映射雾节点中成员太多,则可能导致该映射雾节点在一次任务中能量消耗过尽,而无法完成本次任务,这会造成网络传输数据的失败。同时,如果簇中成员太少,导致映射雾节点主要完成转发来自其他簇首的数据,使其在网络失效时存在大量的剩余能量,从而使其能量没有充分利用。因此,合理地控制簇的规模对于网络性能来说至关重要。
设n个节点为均匀分布在簇成员节点和雾节点之间,相邻节点间的距离为单跳d1-hop,节点的线性表示形式为图2所示。
图2 节点线性数据传输结构
定理2能量衰减系数为2,其单跳距离d1-hop=dopt+Δd的能耗增量小于单跳距离为d1-hop=dopt-Δd能耗增量。其中,dopt为最低目标最优单跳距离。
证明以图2 为例,设线性节点分簇数量为1,传输数据为kbit,根据公式(7)可得:
本文CCRP 算法的核心思想是综合考虑传感网层与雾层之间的节点度和与映射区域中心距离两个因素,通过时间片轮转更换簇头节点,以均衡簇头节点的能量消耗,以解决无线传感器网络分簇中的“热区”问题。算法步骤如下:
步骤1初始化Q个粒子,每个粒子包含K个候选簇首节点,每个候选簇首节点代表一种分簇的可能。
步骤2计算每个粒子p的适用值。
(1)对每个节点ni(i=1,2,…,N)和所有簇首CH的距离d(ni,CH)。分配节点ni给距离最近的簇首节点,即:
(2)利用公式(12)~(14)、(30)、(31)分别计算粒子适应值,并保存在链表中。
步骤3通过定理1 计算最优K值的取值范围,并确定每个粒子的个体最优解和种群的最优解。
步骤4利用公式(8)、(9)更新粒子速度与位置。
步骤5根据距离最近的候选簇首位置调整粒子位置。
步骤6重复步骤2至步骤5,直到定理2成立。
假设N=T×M个节点成为候选簇首节点而参与竞选,共广播T×M条消息。然后,竞选成功的候选簇首节点广播一条消息,其邻居节点收到消息后直接退出竞选。假设共选出K个簇首节点,则它们广播K条发送消息和K条接收消息,而M-K个簇成员广播MK条成簇消息。因此,该阶段网络中总的消息开销为:
所以本文CCRP算法的复杂度为O(N)。
为了进一步验证本文CCRP 算法的有效性和实效性,本文采用MATLAB 8.0 作为仿真实验平台,并与文献[13]和文献[15]以及文献[16]在网络节点存活数量、剩余能量、网络生存周期等属性上进行比对实验。本文采用800个传感器节点随机部署500 m×500 m正方形监测区域,数据总长度为1 000 bit,数据包头为50 bit,簇的数量设定为总传感器节点数量的2%至5%以内,即K∈[16,40],传感器节点感知半径R=10 m。PSO算法设定为种群Q=20,c1=2,c2=3,惯性权重参数w∈[0.4,0.9],评价因子α1∈[0.1,0.4],α2∈[0.1,0.4],α3∈[0.2,0.8],且α1+α2+α3=1,节点初始能量为5 J。
图3 t=0时,500 m×500 m网络节点分布示意图
图4 t=500 s时,500 m×500 m网络节点分布示意图
图5 t=1 000 s时,500 m×500 m网络节点分布示意图
图6 t=1 500 s时,500 m×500 m网络节点分布示意图
图7 t=2 000 s时,500 m×500 m网络节点分布示意图
图3至图7给出了不同t时刻下,网络节点分布示意图。采用的参数为w=0.6,α1=0.1,α2=0.3,α3=0.6。从图中可以看出,随着时间t的推移,出现了部分节点死亡现象。当t=500 s 时,死亡节点数量为8;当t=1 000 s时,死亡节点数量为47;当t=1 500 s时,死亡节点数量为66;当t=2 000 s 时,死亡节点数量为73。当t=1 500 s和t=2 000 s时,死亡节点趋于一种稳定状态,其网络系统节点存活率为91.75%和90.88%。其主要原因在于本文CCRP 协议采用PSO 算法与雾计算相结合方法实现节点能量快速消耗。CCRP 协议有效地平衡了靠近映射雾节点的簇和远离映射雾节点的簇之间的数据传输能耗。CCRP 协议的死亡节点较均匀地分布在整个网络,可以有效地避免了“能量空洞”的出现。
图8至图11给出了不同参数下的四种算法剩余能量对比示意图。从图中可以看出,随着时间的推移,四种算法节点剩余能量均有所消耗,但本文CCRP协议的能量消耗速度明显低于其他三种算法。本文算法在图8和图9中能量消耗速度较快,但整个网络的总体能量还是高于其他三种算法。其主要原因在于其他三种算法均采用非连续单跳方式连续地将数据传输给基站,当基站距离传感网较远时,将会导致簇首节点向基站传输数据的能耗较大,不利于抑制节点节能作用;而本文CCRP协议利用映射雾节点完成簇间多跳路由数据传输。通过改变参数可以有效地抑制节点能量的快速消耗。当映射雾节点距离网络较远时,可以通过改变权重参数提升PSO算法遍历速度,已达到快速完成数据传输效果;通过适应函数和代价函数提升PSO算法对整个网络全局搜索效果,最终达到了快速与低能相结合的数据传输目的。
图8 不同参数下四种算法剩余能量对比
图9 不同参数下四种算法剩余能量对比
图10 不同参数下四种算法剩余能量对比
图11 不同参数下四种算法剩余能量对比
图12 不同参数下四种算法网络生存周期对比
图13 不同参数下四种算法网络生存周期对比
图12至图15给出的是不同参数下四种算法网络生存周期对比示意图。在图12 和图13 是以低密度节点100至400变化作为网络生存周期研究的变量。从图中可以看出,随着传感器节点数量的增加,四种算法的网络生存周期均有明显的提升,但本文CCRP协议提升的速度较快。图14 和图15 给出的高密度节点从450 至800 变化的网络生存周期对比示意图。从图中可以看出,当传感器节点数量为500时,本文CCRP协议基本上趋于平稳,变化的幅度较小,而其他三种算法虽然有上升趋势,但并未超过本文CCRP 协议,从而验证了本文算法的网络生存周期优于其他三种算法。主要原因在于,本文利用映射雾节点完成了对数据融合和传输等任务,分担了部分簇首的工作量,抑制了簇首节点能量的快速消耗;同时,在数据融合和传输中,映射雾节点充当了控制节点的作用,对簇首节点和簇内成员节点进行统一的调节与分配,从而节省了簇内能量的开销,延长了网络生存周期。
图14 不同参数下四种算法网络生存周期对比
图15 不同参数下四种算法网络生存周期对比
本文借助雾计算理论的同时引入粒子群优化算法,提出了一种基于雾计算跨层感知分簇路由协议(CCRP)。该协议首先通过雾计算理论构建网络模型,通过跨层映射原理,利用感知事件驱动机制将雾节点映射到传感层;其次,给出了以边长为L正方形区域的最优簇建立的方法和计算过程;再次,分析了簇的形成以及跨层分簇结构数据融合过程,从而建立以映射雾节点为中心的优化数据聚合路由,取代传感网底层路由中的数据,进一步平衡并减少网络负载。本文最后通过仿真实验验证本文协议的有效性和实效性。未来的主要工作集中在连续性分簇路由优化以及非线性的连续覆盖。