分簇算法在传感器网络中的应用

分簇算法在传感器网络中的应用

1基于空间相关性的网络结构无线传感器网络（无线传感器网络）是由许多传感器节点以自组织的方式创建的无线网络。目标是相互信任地感知、收集和处理网络覆盖区域内感知对象的信息，并将其传输给用户。它是集数据采集、数据处理、数据传输于一体的复杂系统。传感器网络与传统无线网络相比,具有节点电池能量、通信能力、计算和存储能力有限等特点。因此,WSN路由协议必须以节约能源和提高网络生存时间为目标。移动代理平面路由算法LCF要求移动代理遍历感知区域内所有节点,消耗了大量的能量,所以基于数据相关性的分簇路由算法相对平面路由算法具有更好的适应性和节能性。基于地理信息的GAF分簇算法根据节点的位置信息和通信半径,把监测区域划分成若干虚拟单元格。但虚拟单元格的划分并未考虑WSN节点关于位置信息的感知数据空间相关性。文献基于用户查询误差门限,提出的CAG算法通过比较簇头与其邻居节点感知数据值的大小进行分簇。但簇的建立过程需要相邻节点互相通信,增加了通信开销和时延。数据相关性马尔可夫(Markovian)模型中某节点的感知数据值可按不同概率由其它相邻节点的感知数据值得到,但模型只针对规则拓扑结构,非规则拓扑结构未能涉及。本文在文献的基础上提出了一种新的基于空间相关性的事件驱动传感器网络分簇算法(Event-DrivenClusteringAlgorithm,EDCA)。当一个事件被触发,汇聚节点(Sink)无需知道感知区域内节点的感知数据值,即可由用户查询误差门限及数据相关性马尔可夫模型将感知区域划分成虚拟极坐标等价层。每个等价层根据层内节点当前剩余能量选出簇头;由汇聚节点派出的移动代理只需收集满足用户要求的少量有意义的簇头感知信息,从而减少了网络的大量冗余感知数据的传输,节省了能量开销。本文安排如下:第2节讨论空间相关性模型;第3节给出了基于空间相关性的事件驱动传感器网络分簇算法;第4节给出了仿真结果和性能分析;第5节为结束语。2相关模型的空间相关性2.1极坐标中同向随机变量的估计统计学利用变量图(variogram)作数据相关性分析。假设位于(x,y)、(xr,yr)的节点S(x,y),,其感知数据值为V(x,y),V(xr,yr),则变量图为其中(x-xr)2+(y-yr)2=r2。特别地,若V(xi,yi)(i=1,2,…,m(r))为一组节点的感知数据,则γ(r)的估计值为:其中(x-xi)2+(y-yi)2=r2。因γ(r)为同向随机变量,于是在极坐标中定义节点S(r,θ)的数据值为V(r,θ),且其分布密度函数为fV(v);显然V(r,θ)也为同向随机变量。不失一般性,假设事件触发点位于(0,0),其数据值为V(0,0),则由图1有:其中U=H表示V(0,0)由相邻节点的感知数据值获得,其概率为1-β;U=T表示V(0,0)由随机变量Y获得,其概率为β;随机变量Y和Z与V互相独立,且Z∼N(0,σZ2),方差zσ可由式(2)统计计算求得;随机变量R的分布密度函数为;随机变量Θ的分布密度函于是选取θ1=0,θ2=2π,事件感知半径L区域内的节点可分布为以事件触发点为中心,相应于不同感知精度和γ(r)的一系列虚拟同心圆,如图2。图2中在相同圆上的节点具有相同的感知精度,于是数据相关性马尔可夫模型为其中Vkri(1≤k≤N(ri),0<ri<rmax)为与S(0,0)距离ri的节点集中的第k个节点的数据值。3基于相关空间的事件驱动传感器网络的分割算法3.1节点性估计模型图2给出了事件感知区域内传感器节点随感知精度变化的规则拓扑结构,但实际问题通常为非规则拓扑结构,如图3。基于CAG算法,不妨假设事件触发点(0,0)为虚拟簇头S0r1,其读数为,则图3第1个虚拟同心圆内第k个节点Skr1(1≤k≤N(r1))的读数Vkr1(rk,θk)满足:|Vkr1(rk,θk)-V0r1(r1)|<µ,其中µ是用户查询误差门限;而第1个虚拟同心圆上节点S0r2的读数满足:|V0r2(r2)-V0r1(r1)|≤µ,于是:其中C(σz,µ)是σz,µ的函数,。通常γ(r)有多种估计模型,本文由文献选取γ(r)=c(1-e-λr2),参数c和λ可由节点历史数据按式(2)计算求得。于是综上,第i(1≤i≤n)个虚拟圆环内第k个节点Skri(1≤k≤N(ri))的读数Vkri(rk,θk)满足:|Vkri(rk,θk)-V0ir(ri)|<µ,|Vkri(rk,θk)-V0r1(r1)|<iµ;而第i个虚拟同心圆上虚拟簇头S0ir的读数V0ir(ri)满足:|V0ir(ri)-V0r1(r1)|≤(i-1)µ,于是:,其中取使得上式为实数的最大值。若,则rn+1=rmax;反之,则;由此构成半径序列。3.2sisk网络效应步骤1Sink由事件触发点和相关性模型(4)确定事件驱动半径L,即节点感知区域。步骤2Sink由节点位置和半径序列{ir},将节点感知区域划分成虚拟等价层。步骤3Sink选出虚拟等价层中剩余能量最大的节点作为簇头。步骤4Sink派出移动代理访问各簇头,收集、融合数据,并将融合后的信息带回Sink,再由Sink发送给用户。4网络参数的确定利用MATLAB仿真平台测试本文新算法EDCA的性能。假设在500m×500m的区域内随机抛撒600个无线传感器节点,每个节点产生一个100字节的数据包,并随机给每个节点赋予不同的初始能量;根据相关性模型式(4)给每个节点赋值;随机生成事件触发点和Sink。图4(a)中当用户查询误差门限µ确定时,随着相关性参数σz的增加,则EDCA的虚拟等价层的数目相应减少,移动代理访问的簇头数目也相应减少,从而EDCA比LCF减少了大量冗余数据的传输。例如固定µ=1.5,EDCA数据传输能量比LCF最多减少了89.15%。图4(b)固定σz=2.7,随着用户查询误差门限µ的增大,移动代理访问的簇头数目也相应减少,从而EDCA的数据传输能量比LCF最多减少了89.75%,提高了能量效率。通常移动代理访问的相关性节点越多,收集的感知信息越精确,但能量开销也会大大增加,不利于节能;而EDCA中移动代理访问较少相关性节点也能满足用户精度要求,如图5。图5(a)中当感知区域内的节点相关性确定时,EDCA中移动代理访问较少簇头时(如图5(b)),其精度与LCF和CAG非常接近,也能满足用户要求。图5(c)中当σz=2.3时,随着用户查询误差门限µ的增大,EDCA的误差只比CAG最大多0.2858%,而图5(d)中簇头数目比CAG最小少30%。因此EDCA中移动代理收集的相关性数据的精度接近于CAG,但减少了大量冗余数据的传输,达到节能目的。5提升网络能量效率本文在无线传感器网络节点数据相关性马尔可夫模型的基础上,根据用户查询误差门限将事件驱动的感知区域划分成虚拟极坐标等价层,构造了一种新的分簇算法:EDCA。算法不仅可收集满足用户不同要求的感知信息,而且大大减少了传输数据量,提高了网络能量效率。仿真结果显示EDCA的节能性能优于遍历所有感知节点的LCF和根据感知数据进行分簇的CAG。数为,且假设不妨假设为虚拟簇头,则第2个虚拟圆环内第k个节点的读数满足:;而第2个虚拟同心圆上虚拟簇头的读数满足:。EDCA的性能可由(1)数据传输能量减少率,其中TE为数据传输能量;(2)事件触发点的真实值(