张克柱,杨 忆,张 勇
1.宿州职业技术学院 计算机信息系,安徽 宿州 234101
2.淮北师范大学 计算机学院,安徽 淮北 235000
不确定性网络连续高斯协同局部聚类更新方法*
张克柱1+,杨 忆2,张 勇1
1.宿州职业技术学院 计算机信息系,安徽 宿州 234101
2.淮北师范大学 计算机学院,安徽 淮北 235000
Abstract:In order to improve the sensing accuracy of the local evolution of the risk boundary of uncertain wireless sensor network(WSN)model,this paper conducts a Gauss collaborative local clustering updating of continuous frontier for uncertainty WSN.Firstly,this paper presents the distance uncertainty model and velocity uncertainty model,and also gives the closed form of the continuous Bayesian local front velocity update model,which considers the limited processing power of WSN node and energy constraints.Secondly,the local clustering update algorithm is used to update the master node,the list and the auxiliary list for WSN,which realizes the real-time update of the continuous local front of the danger,and also realizes the distributed accurate prediction of the complicated risk evolution.Finally,the experimental results show that the proposed method is robust to sensor node failures and communication link failures.
Key words:uncertainty model;wireless sensor network;continuous front;local clustering;cooperative update
为提高不确定性无线传感器网络(wireless sensor network,WSN)模型的危险边界局部演化特性感知精度,提出了一种基于局部聚类的不确定性WSN模型网络局部前沿协同更新算法。首先,给出基于高斯的WSN感知距离不确定性模型和速度不确定性模型,并给出封闭形式的考虑WSN节点有限处理能力和能量约束的连续贝叶斯局部前沿速度更新模型;其次,基于局部聚类更新算法对WSN网络主节点、列表、辅助列表进行更新,实现危险连续局部前沿的实时更新,实现复杂危险演变特征的分布式准确预测;最后,通过实验对比,所提方法对于传感器节点故障和通信链路故障具有强大的鲁棒性。
不确定性模型;无线传感器网络;连续前沿;局部聚类;协同更新
目标跟踪是监控、航空、军事等领域的基本问题[1-2]。除了确定目标轨迹,更为重要的是实时地估计其运动特性,如方向和速度,因为这些信息可用来预测其未来位置,并了解其整体时空行为,特别是在危险边界演化跟踪预测领域,例如野火和油污的边界扩散预测中[3]。连续危险前沿可近似为一个分段线性曲线。此曲线(被称为局部前沿)的每一部分,可利用局部参数集进行表征,即该段的方向角和传播速度。文献[4]已证明局部前沿的时空演化可修正为二维高斯函数,并可通过模型参数更新进行分布式处理,解决了交叉熵最小化跟踪问题。
无线传感器网络已成功应用于单目标和多目标跟踪问题,但是传统的目标跟踪算法不能应用于连续目标跟踪,因为这两个问题是从根本上不同的。连续对象(如野火、溢油、生化物质扩散等)往往占据较大的面积,其大小和形状不断变化。为了能够跟踪危险边界,需要大量传感器节点协同执行,这增加了边界跟踪问题的难度。最近,一些文献提出用于检测危险边界扩散的无线传感器网络(wireless sensor network,WSN)模型:文献[5]提出基于无线传感器网络的网格连续目标跟踪的选择性传感器节点唤醒规则;文献[6]提出基于静态库和应用地理信息系统(geographic information system,GIS)的无线传感器网络的泥石流预警机制;文献[7]提出利用概率连续异常模型来描述连续异常值的线性表示模型,实现线性表示的视觉跟踪;文献[8]提出一种传感器节点休眠/唤醒机制的连续对象跟踪算法,提高WSN的能源利用效率,实现传感器状态的有效调度;文献[9]提出基于混合静态/动态聚类技术无线传感器网络的连续移动的物体目标检测与跟踪;文献[10]比较连续的对象定位和边界检测方案的复杂性、能源消耗和估计精度,设计一种准确的边界估计方法,实现气体泄漏源检测和边界跟踪;文献[11]提出一种基于卡尔曼滤波算法的时间估计技术,可对轨迹的边界变化进行空间的不定期更新估计,实现了轨迹边界的动态跟踪;文献[12]提出连续的能量最小化的多目标跟踪算法,实现不同维度的搜索空间的有效连续目标跟踪,等。
上述文献在进行危险边界跟踪预测时,需要构建边界探测的传感器集群,这需要大量的传感器部署,并对监测区域内的传感器密度有要求,这在实际应用中会大量增加区域传感器部署的成本。一般是采取人为划定受扩散危险影响区域方式进行,比如探测区域的可能坐标和可能半径值。但即便划定了小型区域内的连续边界检测,所需的传感器部署数量也是巨大的。为解决该问题,本文提出了能够准确估计边界的新分布式算法,采用动态形成的集群协作传感器节点,实现连续对象局部特征演化。
假定传感器节点可检测的事件位于半径Rd的圆形区域内。当前最流行概率感知模型如下[13-14]:
其中,检测概率是在检测范围[Rs,Rd]内随距离x变化的指数递减函数,如果事件发生在半径为Rs的内圆内,则传感器节点可检测到该事件。式(1)中的参数γ和λ控制感知概率的下降速率,其与传感器物理特性有关。
引入变化的概率感知模型,除考虑检测距离的不确定性,还考虑在恶劣环境中传感器节点可能发生故障的概率。如图1所示,节点的感知距离Si假定为半径是Rd的圆形区域,其以传感器Li所处位置为中心。设定期望探测距离为αRd/2,其中0≤α≤1。将待检测距离假定为正态随机分布变量,Di~N(μd,),其中:
假设在距离大于Rd的情况下,传感器检测的概率扩散现象可忽略不计。在范围[0,αRd/2]内,检测概率降低。高斯分布已成功用于描述传感器节点检测概率的距离依赖性,并可简单表征参数不确定性。
Fig.1 Gauss perception model图1 高斯感知模型
如图2所示,3个传感器节点集群系统。当主节点接收到两个检测消息(DM),{,h∈{j,k}},则开始更新其现有的模型。利用其协同坐标Lh=(xh,yh)及其局部前沿的投影点坐标{pih=(xih,yih),h∈{j,k}},主节点可计算欧氏距离{dih,h∈{j,k}}如下:
令Dih是节点Si处的局部前沿,其保持巡游状态,直到被协同节点检测到:
因为Dh服从正态分布,Dih也服从正态分布,且参数为:
其中,dih可基于式(3)计算,h∈{j,k}。基于式(5)可对参数μih进行更新,主节点可计算两个协同投影点速度pij和pik,其在时间间隔tij和tik内移动距离分别为Dij和Dik。因为Dij和Dik服从正态分布,则两投影点速度Uij和Uik也服从正态分布Uih~N(uih,),可计算如下:
Fig.2 Local front model updating图2 局部前沿模型更新
基于连续贝叶斯过程更新速度模型,需考虑WSN节点的有限处理能力和能量约束。由于可观测数据量非常小(仅两个),利用速度观测值(Uih)和不确定信息技术(sih)提高速度似然估计精度。
利用主节点SMi计算高斯混合模型的权重{ωih,h∈{j,k}},如图3所示,计算如下:
其中,wij=1/(1+C),wik=C/(1+C),C=Sij|ui-uij|/(Sik|ui-uik|)。
直接使用高斯混合似然估计和贝叶斯规则进行计算的成本很高,因封闭形式表达式的解析解无法获得,为获得后验分布参数的封闭形式模型,这里采用变分法和正态分布高斯混合模型进行近似。为此,通过最小化混合高斯的最小Kullback-Leibler散度参数,实现正态分布参数估计:
在本文研究对象中,可简化为:
在计算得到混合权重后,主节点根据式(8)~(9)计算正态分布参数和,进而可得参数的封闭计算形式:
Fig.3 Velocity model updating procedure图3 速度模型更新程序
令K1(K2)是被pij(pik)替换的点,其将在时间间隔tik沿局部前沿进化方向以速度uij(uik)进行移动。K1和K2的坐标分别为(x1,y1)和(x2,y2),可通过求解线性二次方程获得。则主节点可更新局部前沿模型的取向参数如下:
为更新方向参数,见图2,主节点可通过点K1(x1,y1)和K2(x2,y2)对函数(x)进行线性化:
如前所述,在进行危险边界跟踪预测时,如果不对边界进行预处理,会造成传感器部署数量的大幅度增加,不利于组网成本的降低和探测精度的提高,对此提出了能够准确估计边界的新分布式算法,实现连续对象局部特征演化。首先对危险边界进行局部聚类预处理,步骤如下。
步骤1(网络假设)假设进化前沿部分刚刚进入WSN部署区域时,没有节点能够检测到。所有节点都用相同的先验模型进行初始化,即mi={ϕi,δi,ui,Si},δi=0。
步骤2(检测程序)如图4(a)所示,当进化前沿到达节点Si的感知范围,则启动如下检测程序:
(2.1)节点Si启动局部计时器,检测状态标志DSFi=0→1,然后检测状态变量SSi。
(2.2)如果SSi=0(Si为静态节点),节点进行状态转换,。
(2.3)如果SSi=2(Si为从属节点),节点广播检测消息DM(IDi)。每个邻居节点Sm∈Ni,m={j,k,l},根据接收到的信息更新其邻域节点列表的局部时间属性tmi和状态属性DSFmi。
步骤3(必要条件检测)节点查询其列表中尚未检测到前沿的邻居子集,即,过程为:
步骤4(辅助列表创建)节点检查mi中前向演化方向参数δi的值。
(4.1)如果δi=+1(局部前沿演化为正半平面),节点查询其邻域列表中属于正邻域半平面,但未检测到前沿的邻域子集()。如果,计算邻居节点的局部前沿投影坐标,如图4(a)中的点pij、pik和pil。然后,节点计算所有可能投影对的欧氏距离,并与预先指定阈值进行比较。
(4.2)如果δi=-1(局部前沿演化为负半平面),节点查询其邻域列表中属于负邻域半平面,但未检测到前沿的邻域子集()。
(4.3)如果δi=0(局部前沿演化方向未知),节点查询其邻域列表中属于其邻域内,但未检测到前沿的邻域子集()。然后节点根据局部前沿线fi(x)将其划分为两个半平面。然后,对两个子集和分别执行上述步骤(4.1)~(4.2)。
Fig.4 Local front model updating process图4 局部前沿模型更新过程
步骤5(主节点声明)节点检测其辅助表。如果=∅ ,不是主节点,→,并广播信息DM(IDi)。接收的邻域节点{Sm∈Ni}更新其列表中的属性tmi和DSFmi。如果≠∅,即至少有一个辅助表,则节点转换为主节点,→,然后检测其进化方向参数δi:
(5.1)若δi≠ 0,主节点广播类型1主声明信息MDM1(IDi,PMi)。每个邻域节点{Sm∈Ni},根据接收到的MDM1(IDi,PMi),更新其中的行属性tmi和DSFmi。此外,每个Sm∈基于主节点初始模型导出局部前沿方程fi(x)。如果sgn(fi(xm))=sgn(δi),Sm变为从属节点,Sm→,并在主列表中为增加属性{ID←IDi,UM←null},并发送主声明确认消息MDMA(IDm)回节点。否则Sm保持状态不变。
(5.2)若δi=0,主节点广播类型2主声明信息MDM2(IDi,PMi)。每个邻域节点{Sm∈Ni},根据接收到的MDM2(IDi,PMi),更新其中的行属性tmi和DSFmi。此外,如果{Sm∈},则Sm变为从属节点Sm→,并在主列表中为增加属性{ID←IDi,UM←null},然后发送主声明确认消息MDMA(IDm)至主节点。
步骤6(主邻域重定义)主节点等待从其从属节点获得信息MDMAs。检查是否在其从属IDs中至少接收到一个合法辅助对(存储于)。
(6.1)如满足,则保持状态不变,并等待直到收到两个检测消息DMs,然后更新模型参数。
(6.2)若不满足,则广播其自由从属节点信息FSM(IDi),并改变其状态→。当从属节点∈Ni接收到FSM信息后,将其从中移除主节点的有关信息,并将其状态返回→。
假定主节点从中接收的信息是无损的,见图4(c)所示,当从辅助对中获得信息DMs后,开始邻域列表更新。
步骤8(模型传播)广播更新先验消息UPM(IDi,UMi),接收到该信息的节点∈Ni更新其列表的信息。同时,更新列表中属性UMi←。此外,发送主提供消息MOM(IDi)到目标最近从属节点,并询问其是否成为新主节点。这个节点成为暂时的候选主节点→,并利用更新模型参数,以初始化必要条件检查程序,见步骤3。
如果满足成为新节点条件,其接受建议→,并向发送接受主节点消息AMOM(IDk)。当接收到该信息,其广播自由的从属节点信息FSM(IDi),并改变其状态为默认值(→),见图4(d)。每个从属节点在其列表中删除信息,并将其状态更改为静止状态,→。
上述网络协同算法中,包含局部聚类构建和模型更新传播两个主要过程。
在局部聚类构建过程中,共分为6个子步骤:步骤2在全部节点循环中,存在一个二分列表查询,则其计算复杂度为O(nlbn);步骤3包含一个二分判断,则其计算复杂度为O(nlbn);步骤4包含一个二分判断,则其计算复杂度为O(nlbn);步骤5包含一个二分判断,则其计算复杂度为O(nlbn);步骤6包含一个二分判断,则其计算复杂度为O(nlbn)。
在模型更新传播过程中,共分为2个子步骤:步骤7包含一重循环,则其计算复杂度为O(n);步骤8包含一重循环,则其计算复杂度为O(n)。
由此可得,所提算法的计算复杂度为5O(nlbn)+2O(n),则其计算复杂度可简化为O(nlbn)。
基于Matlab平台对算法进行验证,节点部署区域面积为300 m×300 m,传感器节点数量为n个。设定传感器节点故障概率为p。以传感器节点作为中心,设定其感知区域半径为R,该区域内节点数量均值是网络密度。参数n增加会直接导致网络密度增大,具体见表1所示。
Table 1 Relationship between network density andnunder random distribution表1 随机分布下网络密度与n的关系
假设节点仅收集一类属性,并选取相同设定参数下的文献[15]作为对比算法。在对比过程中,传感器节点均收集100组不同时刻属性,在时刻t=30随机设定故障事件。假定正常节点在正常区域内符合正态分布规律N(μ1,),正常节点在事件区域符合正态分布规律N(μ2,),μ1、μ2、σ1、σ2取值任意设定,仅满足|μ1-μ2|相比σ1,σ2较大即可。文献[15]参数:故障传感节点采集故障数据量为50,且有μ1=10,μ2=30,σ1=σ2=1,R=30,r=15。
对于随机节点分布网络中存在事件时,文献[15]若要实现高边界检测率(≥85%)和低故障误判率(≤5%),在故障概率p和阈值θ设定下,最低网络密度阈值见表2。
Table 2 Threshold and value of failure probability and density表2 阈值在不同故障概率和节点密度下的取值
由表2数据可知,阈值θ合理取值与网络密度和故障率p取值有关。一般p增大,θ取值要单调降低;文献[15]提出基于关键线的无线传感器网络边界监控策略,本质上是一种依赖于部署区域传感器节点密度的边界检测算法,其对于因传感器故障产生的传感器节点密度的降低非常敏感,采取阈值调整方式,无法达到更高检测精度。而本文算法在进行边界检测过程中,采取网络协同算法进行局部聚类构建,其对于传感器故障的敏感性具有较强的鲁棒性。图5所示为本文算法与选取的文献[15]对比算法在节点数量是500与200,网络节点密度为d=18,阈值θ=1.59时,故障边界检测精度与故障概率对比数据。
从图5中可知,随机分布时随网络规模增大,两种算法的边界检测率均呈现下降趋势,但是在下降幅度上文献[15]下降显著,而本文算法检测率略有下降趋势,但是仍可保持于85%以上。虽然对于较低节点故障率,文献[15]具有相对较好的边界检测性能,但故障率升高时,边界检测精度急剧降低,而本文算法的总体边界检测精度要明显优于文献[15]算法。
Fig.5 Relationship between fault detection accuracy and failure rate图5 故障边界检测准确度与故障率的关系
图6所示为节点在随机分布下危险边界检测示意图,其中“■”为检出的危险边界节点,“●”表示检出的故障节点,虚线表示检测出的危险边界曲线。
根据图6可知,本文算法可准确实现故障节点的检测,且不存在故障节点误判问题。图6给出了利用本文算法检测出的危险边界拟合曲线。该曲线同真实的危险边界曲线吻合度很高,表明本文算法可以非常准确地对危险区域的位置和大小进行判断和检测,体现了本文算法的有效性。
Fig.6 Results of hazard boundary detection图6 危险边界检测结果示意
图7所示为均匀分布节点情况下,危险边界检测精度同总节点数量的关系对比情况。根据图7可知,两种对比算法对于危险边界的检测精度均在85%以上。在参数nx=250以上时,节点数量继续增大,对危险边界检测精度影响很小。对于监测区域固定情形,存在最合理的网络密度取值,在保证危险边界检测精度同时,降低网络部署成本和降低算法计算复杂度。
Fig.7 Influence of the number of nodes on detection accuracy of dangerous boundary图7 节点数量对危险边界检测精度影响
本文选取危险边界的检测精度、检测时间作为对比指标,对比算法仍然选取文献[15]算法。根据表1参数设定方式,选取节点密度d=12情况下的3组参数设定方式。设定1:故障概率参数选取p=0.05,阈值θ=1.67;设定2:故障概率参数选取p=0.10,阈值θ=1.21;设定3:故障概率参数选取p=0.15,阈值θ=1.03。其余参数设置见4.1节所示,仿真对比结果见表3所示。
Table 3 Comparison of algorithm performance表3 算法综合性能对比
根据表3数据可知,在文献[15]算法均选取最佳参数设定情况下,文献[15]算法的危险边界检测精度仍然由95.5%下降至91.7%。而本文算法在与文献[15]算法参数设置相同情况下,危险边界检测精度仅由96.3%下降至95.1%,降低幅度远小于文献[15]。而在计算时间指标上,文献[15]算法的危险边界检测计算时间由6.2 s增加至9.4 s,而本文算法的计算时间增加幅度为16.7%,低于文献[15]算法。这表明本文算法对于故障概率参数敏感性要弱于文献[15]算法,综合检测性能要优于文献[15]算法。
本文提出了一种基于局部聚类的不确定性WSN模型网络局部前沿协同更新算法,给出了封闭形式的考虑WSN节点有限处理能力和能量约束的连续贝叶斯局部前沿速度更新模型,并基于局部聚类更新算法对危险连续局部前沿进行实时更新,实验对比结果验证了本文方法有效性。下一步研究重点是,对于非线性特征的传感器模型进行系统描述,并实现非线性模型异常值有效检测,以确定事件产生位置和区域大小。
[1]Zhang Bang,Wang Xingwei,Huang Min.Optimal distance routing algorithm based on cell clustering for three dimensional WSN[J].Journal of Frontiers of Computer Science and Technology,2015,9(10):1219-1228.
[2]Liu Xiaoyang.Node accuracy positioning algorithm of sensor network in heterogeneous environment[J].Journal of Frontiers of Computer Science and Technology,2015,9(4):475-481.
[3]Tomasi R,Sottile F,Pastrone C,et al.Leveraging BIM interoperability for UWB-based WSN planning[J].IEEE Sensors Journal,2015,15(10):5988-5996.
[4]Zhang Yuan,Sun Limin,Song Houbing.Ubiquitous WSN for healthcare:recent advances and future prospects[J].IEEE Internet of Things Journal,2014,1(4):311-318.
[5]Park H,Oh S,Lee E,et al.Selective wakeup discipline for continuous object tracking in grid-based wireless sensor networks[C]//Proceedings of the 2012 Wireless Communications and Networking Conference,Shanghai,Apr 1-4,2012.Piscataway,USA:IEEE,2012:2179-2184.
[6]Yang Chengyue,Li Qingquan,Liu Jianming.A multisinkbased continuous object tracking in wireless sensor networks by GIS[C]//Proceedings of the 14th International Conference on Advanced Communication Technology,PyeongChang,Korea,Feb 19-22,2012.Piscataway,USA:IEEE,2012:7-11.
[7]Wang Dong,Lu Huchuan,Bo Chunjuan.Fast and robust object tracking via probability continuous outlier model[J].IEEE Transactions on Image Processing,2015,24(12):5166-5176.
[8]Hong S W,Noh S K,Lee E,et al.Energy-efficient predictive tracking for continuous objects in wireless sensor networks[C]//Proceedings of the 21st International Symposium on Personal,Indoor and Mobile Radio Communications,Instanbul,Turkey,Sep 26-30,2010.Piscataway,USA:IEEE,2011:2179-2184.
[9]Chang Wangrong,Lin Huitang,Cheng Zongzhi.CODA:a continuous object detection and tracking algorithm for wireless ad hoc sensor networks[C]//Proceedings of the 5th Consumer Communications and Networking Conference,Las Vegas,USA,Jan 10-12.Piscataway,USA:IEEE,2008:168-174.
[10]Shu Lei,Mukherjee M,Xu Xiaoling,et al.A survey on gas leakage source detection and boundary tracking with wireless sensor networks[J].IEEE Access,2016,10(4):1700-1715.
[11]Duttagupta S,Ramamritham K,Kulkarni P.Tracking dynamic boundaries using sensor network[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(10):1766-1774.
[12]MilanA,Roth S,Schindler K.Continuous energy minimization for multitarget tracking[J].IEEE Transactions on PatternAnalysis and Machine Intelligence,2013,36(1):58-72.
[13]Le T N,Pegatoquet A,Huy T L.Improving energy efficiency of mobile WSN using reconfigurable directional antennas[J].IEEE Communications Letters,2016,20(6):1243-1246.
[14]Chen Liangyin,Wang Jinlei,Zhang Jingyu,et al.A node sleep scheduling algorithm in the low duty cycle WSN[J].Journal of Software,2014,25(3):631-641.
[15]Xiao Yang,Zhang Yanping.A critical line based boundary surveillance strategy in wireless sensor networks[J].Tele-communication Systems,2013,52(2):423-434.
附中文参考文献:
[1]张榜,王兴伟,黄敏.三维WSN中细胞分簇最优距离路由算法[J].计算机科学与探索,2015,9(10):1219-1228.
[2]刘小洋.非均匀环境下传感器网络节点精确定位算法[J].计算机科学与探索,2015,9(4):475-481.
[14]陈良银,王金磊,张靖宇,等.低占空比WSN中一种节点休眠调度算法[J].软件学报,2014,25(3):631-641.
Gauss Collaborative Local Clustering Updating Method of Continuous Frontier for Uncertainty Network*
ZHANG Kezhu1+,YANG Yi2,ZHANG Yong1
1.Department of Computer Information,Suzhou Vocational Technical College,Suzhou,Anhui 234101,China
2.College of Computer Science,Huaibei Normal University,Huaibei,Anhui 235000,China
A
TP301.6
+Corresponding author:E-mail:zhagkezh@qq.com
ZHANG Kezhu,YANG Yi,ZHANG Yong.Gauss collaborative local clustering updating method of continuous frontier for uncertainty network.Journal of Frontiers of Computer Science and Technology,2017,11(10):1672-1680.
ISSN 1673-9418 CODEN JKYTA8
Journal of Frontiers of Computer Science and Technology
1673-9418/2017/11(10)-1672-09
10.3778/j.issn.1673-9418.1607049
E-mail:fcst@vip.163.com
http://www.ceaj.org
Tel:+86-10-89056056
*The National Natural Science Foundation of China under Grant No.61102117(国家自然科学基金);the Key Project of Natural Science Research ofAnhui University under Grant No.KJ2016A782(安徽高校自然科学研究重点项目).
Received 2016-07,Accepted 2016-12.
CNKI网络优先出版:2016-12-19,http://www.cnki.net/kcms/detail/11.5602.TP.20161219.1613.002.html
ZHANG Kezhu was born in 1979.He received the M.S.degree in computer science from China University of Mining and Technology.Now he is an associate professor at Suzhou Vocational Technical College.His research interests include computer network and data mining,etc.
张克柱(1979—),男,安徽庐江人,中国矿业大学硕士,宿州职业技术学院副教授,主要研究领域为计算机网络技术,数据挖掘等。
YANG Yi was born in 1980.He is a lecturer at Huaibei Normal University.His research interests include data mining,machine learning and recommender system,etc.
杨忆(1980—),男,安徽凤阳人,博士研究生,淮北师范大学讲师,主要研究领域为数据挖掘,机器学习,推荐系统等。
ZHANG Yong was born in 1977.He received the M.S.degree in computer science from University of Electronic Science and Technology of China.Now he is an associate professor at Suzhou Vocational Technical College.His research interest is computer image processing.
张勇(1977—),男,安徽宿州人,电子科技大学硕士,宿州职业技术学院副教授,主要研究领域为计算机图像处理。