基于虚拟势场和学习自动机的有向传感网覆盖控制

陈　莹, 曹立志

(江南大学轻工控制教育部重点实验室, 江苏 无锡 214122)



基于虚拟势场和学习自动机的有向传感网覆盖控制

陈莹, 曹立志

(江南大学轻工控制教育部重点实验室, 江苏 无锡 214122)

摘要：针对目前有向传感网中覆盖增强和冗余节点休眠调度算法存在的问题,提出虚拟势场结合学习自动机的覆盖控制算法。引入基于质心距离和重复感知率的虚拟力改进模型,综合考虑虚拟向心力和切向力对感知角度调整的影响,建立微观虚拟力与转动角度的关系模型,并根据网络整体覆盖率增长率对节点调整幅度进行宏观控制,合理调整节点感知方向。在此基础上,根据节点重复感知率和能量因素建立学习自动机与环境信息的交互机制,学习最优的冗余节点休眠调度策略。仿真实验结果表明,该算法能够显著增强网络覆盖,并有效地控制网络覆盖冗余。

关键词：有向传感器网络; 虚拟势场; 学习自动机; 覆盖增强; 节点休眠调度

0引言

随着人们对细粒度、精准信息的环境监测应用的迫切需求,由大量有向监测周围环境,且数据信息量较大的多媒体传感器组成的无线多媒体传感器网络(wireless multimedia sensor networks, WMSNs)已越来越受到人们的关注,并被广泛应用于军事侦察、环境监测、医疗护理和交通管理等军事和民用领域[1]。由于传感器节点通常具有电源能量低、二次补充能量难、信息采集能耗大的缺点,因此无线多媒体传感器网络存在严重的能量约束问题。覆盖控制是该网络的一个基础问题,反映着网络所能提供的“感知”服务质量[2]。 而传统基于全向覆盖模型的覆盖控制算法无法直接应用于有向的多媒体传感器网络中,因此设计一种合理的有向传感覆盖控制算法以增强网络覆盖并有效利用网络能量,从而实现网络高效长期覆盖是WMSNs需要解决的突出问题。

文献[3]根据有向传感器特点设计了一种2-D有向感知模型,并首次应用于有向传感器网络中。在此模型的基础上,国内外展开了大量针对无线多媒体传感器网络覆盖的研究工作[4-5]。其中,虚拟势场(potential force,PF)方法可以有效地调整有向传感网节点的感知方向,已广泛应用于多媒体传感器网络覆盖增强问题。文献[6]首次将虚拟势场应用于有向传感器网络中,提出基于虚拟势场的覆盖增强算法(potential field based coverage-enhancing algorithm, PFCEA),创新性的引入感知“质心”概念,根据质心点受虚拟斥力进行扩散运动,进而调整各节点感知方向,将覆盖控制问题转化为质心点均匀分布问题,以达到去除覆盖重叠区和盲区,增强网络覆盖的目的。但该算法采用固定转动调整角度限制了覆盖优化的效果和收敛速度,并且仅采用欧氏距离参数并不能细致的描述具有重复感知区域的网络节点受力情况。其后的改进工作大多从这2方面展开。文献[7]采用配对的切点排斥机制(paired tangent point repulsion mechanism,PTPRM),建立了角度调整量、合力与感知方向夹角这两者的函数模型。但其仅考虑最近2个节点的斥力作用,并没有充分考虑其余邻居节点的影响,因此限制了其覆盖提升效果。文献[8]则根据切向分力的大小调整每次转动角度。文献[9]提出了基于虚拟向心力模型的覆盖增强算法(virtual centripetal force-based coverage enhancing algorithm, VCFCEA),通过建立感知区域网格模型,将感知重叠网格数引入虚拟力计算公式,并且建立了向心力与调整角度的关系模型,根据向心力大小调整转动角度,但由于不同位置网格的面积不尽相同,因此采用网格数目参数无法得到精确的虚拟力,从而影响进一步通过虚拟力调整感知角度。这类单独考虑切向力或向心力作用的模型,并不能全面细致的描述节点受力调整规律,在某些特殊情况,如文献[7]中算法在图1(a)情况、文献[8]在图1(b)情况下,节点甚至无法调整感知方向。

图1　基于切向力、向心力的转动角度模型无法调整角度的情况

另一方面,能量问题一直是无线多媒体传感器网络需要解决的突出问题[10],文献[11]根据节点当前能量值关闭网络节点,但仅考虑节点能量因素,仍无法解决网络覆盖冗余问题,因此实际提升效果并不明显。文献[9]根据节点的感知重复网格数,同时关闭覆盖重复率过高的节点以延长网络覆盖时间。但此类同一时间关闭节点的休眠调度算法在可能造成覆盖同一区域的节点同时关闭,出现覆盖盲区(coverage hole,CH)。针对这一问题,文献[12]采用了基于重复覆盖优先级的策略,优先关闭重复覆盖优先级高的节点,在一定程度上缓解了关闭冗余节点造成的覆盖盲区问题,但关闭处于同一优先级的节点时仍会存在上述问题。同时,作为新型的机器学习算法,学习自动机(learning automata, LA)主要解决具有感知环境能力的自治agent通过与环境交互,对其所选动作奖惩,自适应的学习到最优动作策略。这一特性正适用于WMSNs中节点调度策略的选择。目前已有文献[13-14]将其应用于有向传感网中,并取得较好的效果。

针对有向传感器网络覆盖增强和能耗控制的应用,并综合研究上述各文献存在的问题,本文提出了一种基于虚拟势场结合学习自动机的网络覆盖控制算法。首先,在根据节点距离和感知重复率建立的虚拟力模型的基础上,综合虚拟向心力和切向力对节点角度调整的影响,建立了虚拟力与转动角度的关系模型,并根据网络覆盖率增长率对节点调整幅度做了进一步调整,从而更为合理的调整了节点感知方向。同时,采用基于学习自动机的增强学习机制,根据节点的感知冗余和能量情况,通过学习自动机与环境信息的交互和对选择动作的奖惩,从而学习到最优的休眠调度策略。

1系统模型

1.1网络模型

所采用的网格模型具有以下特点。

(1) 网络中所有节点同构,即所有节点具有相同的感知半径和夹角等参数规格。

(2) 网络节点具有固定的ID,且随机部署,节点均匀分布在监测区域。

(3) 网络节点在部署后位置固定不变,但其感知方向可调。

(4) 网络节点都了解自身位置及传感方向信息,且对自身感知方向可控。

1.2感知模型

不同于普通传感器的全向感知模型,无线多媒体传感器通常具有受限的扇形感知区域。文献[6]采用方向可调的2-D感知模型〈P,R,V(t),α〉。如图2所示,其中P表示节点的位置坐标(x, y);R表示节点的感知半径;单位向量V(t)沿着扇形感知区域的中轴线,表示节点在t时刻的感知方向;2α代表传感区域视角(fieldofview,FOV)。Δφ表示节点转动角度,centroid表示节点覆盖区域的质心点,分布在感知区域的中轴线,与圆心距离为2R·sinα/(3α)。

1.3重复感知区域网格模型

WMSN的节点的扇形感知区域,造成其不规则的覆盖重叠区域,与文献[12]相同,论文采用如图3所示的网格模型来计算这一区域:把感知区域分成M×N块网格(本文设为10×10),即将感知半径R和感知视角FOV分为M和N等份;从而位于第p行q列网格的面积为

(1)

由式(1)可知,网格的面积仅与其所在的列数q有关。

图2　感知模型

图3　重复感知网格模型

基于上述模型,本文定义如下变量。

(1) 邻居节点:节点距离小于2R的两节点互为邻居节点。N(vi)表示节点vi的邻居节点集合。

(2)OSAij:节点vi的感知区域被邻居节点vj重复感知覆盖的面积(overlap-sensearea,OSA),见图4。即

(2)

式中,Cgijpq表示节点vi的感知区域内第p行q列网格是否被邻居节点vj重复覆盖:若该网格被覆盖则Cgijpq=1；否则其值为0。

图4　重复感知区域面积的计算

(3)OSRij:表示节点vi的感知区域被节点vj重复感知覆盖区域与其感知区域的比率为

(3)

(4)OSRi:表示节点vi的感知区域内被其邻居节点N(vi)重复感知的总面积占其感知区域的比例为

(4)

2虚拟势场与学习自动机简介

2.1虚拟势场及传统虚拟力模型

虚拟势场的概念借鉴了物理学电磁场模型。其基本思想是把网络中每个节点感知范围的质心看做一个虚拟电荷,每个质心点都在其邻居质心点的虚拟斥力作用下作扩散运动,并在运动学和动力学的双重约束下趋于平衡,即采用质心点的圆周运动替代节点感知角度的转动调整,从而将基于虚拟势场的有向传感器网络覆盖增强问题抽象为节点质心点之间通过虚拟斥力作用达到质心点均匀分布问题[4]。

根据传统的虚拟力模型,节点vi受到邻居节点vj的虚拟力为

(5)

式中,kR为斥力常数；rij为单位向量;方向由质心点cj指向质心点ci；rij表示质心点间的欧氏距离。

2.2学习自动机简介

学习自动机是一种基于增强学习并在未知的随机环境中完成自适应决策的智能单元[15],LA的学习过程实质上是与随机环境的一组互动:如图5所示,首先LA从其动作集α中选择一个动作αi,并输入到随机环境中;然后,随机环境对该动作进行评估并向自动机反馈一个反映奖励或惩罚响应的增强信号βi；最后,基于这个增强信号和选择的动作,LA根据相应的学习算法T()更新动作选择概率集并依据其进行下一轮动作选择。通过有限次的交互迭代过程,LA逐渐学习到最佳动作。

图5　LA与环境关系模型

3基于虚拟势场与学习自动机的网络覆盖控制算法

本文主要解决网络覆盖增强和冗余节点的关闭2方面问题:先采用基于虚拟势场的覆盖增强改进算法提高网络的覆盖率;然后,采用基于学习自动机的节点休眠调度算法学习到合理的关闭冗余节点的优化策略,从而达到提升网络覆盖率并且高效利用网络能量的目的。

3.1基于虚拟势场的覆盖增强改进算法

虚拟势场算法通过相邻传感器质心点之间的虚拟斥力调整节点的感知方向,达到网络覆盖增强的效果。但传统算法存在2方面问题:首先,虚拟力模型仅考虑质心点的距离参数,而没有考虑节点间冗余覆盖对虚拟力的影响,使得不同重复覆盖率的节点调整幅度相同。另一方面,传统算法采用固定的转动角度调整影响了覆盖优化的收敛速度和精度,这表现在当该转动角度值设置较小时,将会减缓网络覆盖收敛速度,限制了算法的执行效率;而当转动角度值较大时,则会降低网络调整精度,甚至造成网络迟迟不能进入稳定状态。同时，还应根据网络整体覆盖情况动态调整角度:在网络调整初期,需要增大转动角度以迅速提升网络覆盖率;而在网络覆盖趋于收敛时,则需降低节点转动角度以实现快速收敛并增强覆盖精度。

基于以上2个问题,本文在引入考虑节点重复覆盖率的虚拟力改进模型的基础上,根据相邻节点间的虚拟力大小调整节点的感知方向;同时,结合网络覆盖增长率进一步调整转动角度,因而从微观(虚拟力)、整体(网络覆盖率)2个方面共同调整节点感知方向。

3.1.1改进的虚拟力模型

本文综合考虑节点间距离和重复覆盖的情况,在仅考虑质心距离的传统虚拟力模型(式(5))的基础上,根据相邻节点重复覆盖率大小进一步调整虚拟力,其定义如下:

(6)

节点vi所受的虚拟力合力为

(7)

式中,kR, rij,r0ij,N(i)与传统虚拟势场算法定义相同,OSRij表示节点间的重复覆盖率。

从式(6)可以看出当2个节点重复覆盖率较大时,其虚拟力也应相应增大,有利于提高了角度调整的幅度,加快了网络覆盖调整速度。并且不同于文献[9],本文虚拟力模型采用基于面积的网络重复覆盖率取代重复覆盖的网格数目,从而可以为进一步调整感知角度提供更为准确的虚拟力数值。

3.1.2转动角度的计算

本文主要从微观虚拟力和网络整体覆盖增长率2个方面对转动角度进行调整。

(1) 基于虚拟力调整转动角度

从动力学角度分析,节点转动角度由虚拟力F的向心分力Fc提供的角速度wc和切向分力Ft提供的线加速度αt共同决定。本文假设在Δt时间内,Fc和Ft保持不变。

1) 在切向方向上

由动力学可知,切向力提供切向加速度,即

式中，km为比例系数;θ为合力方向与向心方向的夹角;αt为切向加速度。

由运动学可知,加速度αt在Δt时间内转过弧长为

故切向力提供的角度变化为

(8)

2) 在向心方向上

当θ∈[0,90°]时,合力的向心分量指向节点,表现为向心力,大小为‖F‖·cosθ。

当θ∈[90°,180°]时,虚拟力的向心分量背离节点,但质心并未做离心运动,因此设定该离心方向力与系统保持圆周运动所提供的力抵消,大小为0。

因此向心力定义为

由物理学圆周运动知识得

从而向心力提供的角度变化为

为了简化计算,本文设定相应阈值对合力归一化处理;在式(8)和式(9)中,由于Δt,km,R均为常数,从而令knorm=(Δt)2/(km·R)为归一化系数,归一化合力定义为Fnorm=min(Knorm·F, 1)。

综合式(8)和式(9),根据虚拟力的转动角度调整为

(10)

式中，kφ为角度调整系数,由式(10)可知,转动角度ΔφF仅与虚拟力Fnorm和夹角θ的取值有关,其关系模型如图6所示,其中转动角度ΔφF随虚拟力Fnorm的递增而逐渐增大,且转动角度ΔφF随着夹角θ的变化反映了切向力和向心力对转动角度不同的影响关系。

图6　转动角度与归一化虚拟力与夹角θ的关系模型

(2) 根据网络覆盖的增长率的模型

转动角度除了受微观虚拟力决定之外,还应从宏观上根据网络整体覆盖增长率动态调整:在覆盖增长率较大时(如网络调整初期),需要增大转动角度以迅速提升网络覆盖率;而在网络覆盖趋于收敛时,此时覆盖增长率较小,则需要降低节点转动角度以实现快速收敛并提高覆盖效果。从而进一步调整节点转动角度如下:

(11)

式中,ΔφF如式(10)所示；θmax为转动角度的上限值；θmin为转动角度的下限值;Vp为网络覆盖增长率；Vinit为网络初始覆盖率。

根据对算法的反复实现和分析,节点在初始的10次调整过程覆盖增长变化较快,因此在此过程设定转动角度取较大的转动角度;而在覆盖增长率较低时(远低于平均),近似认为此时节点进入稳定状态调整过程,因此需要降低角度调整的幅度;从而在提高网络覆盖调整效率的同时,进一步提升了网络覆盖效果。

本文节点调整方向为:当切向力方向大于0时,此时节点沿着切向力方向旋转Δφi角度;而当切向力方向为0时,则规定节点沿着顺时针方向调整Δφi角度。

3.1.3改进算法描述

算法输入:节点vi及其邻居节点的位置和感知方向。

算法输出:节点vi的最终感知方向，具体算法描述如下。

(1) 初始化计数步长t←0。

(2) 初始化各节点停止调整标志flag(i)←0。

(3) 计算节点vi对应的质心ci初始位置Pci(t)。

(4) 计算监测区域初始覆盖率Vinit。

(5) 计算节点vi邻居节点集合N(vi),及邻居节点数目M。

(6) 令t←t+1,Fi(t)←0,计算当前网络覆盖率和覆盖增长率Vp,并根据式(6)计算质心点cj对ci的虚拟斥力Fij(t),其中vj∈N(vi)。

(7) 计算Fi(t)←Fi(t)+Fij(t),将Fi(t)带入式(10),计算出虚拟力调整的旋转角度ΔφF。若 ΔφF≥ε,则根据下述规则进行节点角度和位置调整。

1) 根据式(11)调整节点转动角度Δφi。

2) 质心点ci沿规定方向转动角度Δφi。

3) 调整质心点ci到新位置Pci(t)。

4) 计算节点vi指向当前质心点ci向量并单位化,从而得到传感方向V(t)。

(8) 返回描述(6),直至算法收敛。

3.2基于学习自动机的节点休眠调度算法

通过上述网络节点感知方向调整后,网络覆盖得到了显著的增强(如图7(c)),但网络中仍存在覆盖冗余节点,并且随着部署节点数目的增加,覆盖冗余问题也越严重。而针对网络冗余覆盖存在2个相互矛盾的问题,即关闭冗余节点可以有效提高能量利用效率,延长网络存活时间;但同时也会造成网络覆盖率会在一定程度降低。传统算法采用在同一时间关闭所有覆盖率高的节点,虽然可以降低网络覆盖冗余,容易造成网络中覆盖同一区域的节点同时关闭,出现网络覆盖盲区问题(如图7(b))。

为了解决这一问题,本文采用基于学习自动机的节点休眠调度方法,针对覆盖重复率高于一定阈值OSRthr的特定节点,根据其覆盖区域内的重复覆盖率和自身能量,通过其学习自动机与邻居节点进行覆盖信息的交互和动作概率的奖惩,从而网络选择出最优动作策略。基本过程如下:

(1) 在初始阶段,节点si中的学习自动机从其动作集(工作(a0)或休眠(a1))中随机的选择一个动作,并向周围邻居节点发送内容为是否为特定节点,选择动作、感知范围、自身能量等信息的广播包,从而网络中的特定节点都建立了周围邻居的信息表。

(2) 接着,在以后各轮动作选择过程中,节点si以接受到的邻居节点信息作为随机环境,计算出相应的奖惩性反馈信号βi反馈到节点si。其中βi定义如下。

1) 当si选择的动作为工作时

当节点感知区域被工作的邻居节点重复覆盖超过特定阈值时,环境惩罚这一动作,βi=1;否则,环境奖励这一动作,返回信号βi=0。

2) 当si选择的动作为关闭时

当节点的感知区域被工作的邻居节点重复覆盖超过特定阈值时,环境奖励这一动作,βi=1;否则,环境惩罚这一动作,返回信号βi=0。

(3)最后,根据环境的反馈信号βi,学习自动机采用不同学习算法更新下一轮动作概率。

(12)

(13)

式中,式(12)、式(13)分别表示有利响应和不利响应下动作更新概率的表达式；a(n)，b(n)分别是奖励和惩罚函数,且随迭代次数n而时变,其定义如下:

(14)

(15)

其中

(16)

网络节点调度学习过程的终止条件为:网络学习过程次数超过特定的次数MAX_ITERATION; 特定的节点都确定自身状态(休眠或工作)。特定网络节点选择休眠状态条件为其选择休眠动作概率超过特定的阈值,否则节点则选择处于工作状态的动作。

4仿真实验与结果分析

本文采用Matlab进行仿真实验。为了评估网络覆盖提升效率和冗余节点休眠调度情况。本文首先通过一个实例直观的展示算法的运行效果,然后分别对节点覆盖增强和冗余节点控制2个算法的收敛效果进行验证;最后,针对不同参数的网络,将本文算法与VCFCEA在网络覆盖增强和冗余节点关闭2方面进行性能比较和分析。实验涉及到的其余参数值如表1所示,其中φ, ρ参数值为实验经验值。

表1　网络环境及参数

4.1实例效果

首先,在500×500 m2的目标区域内随机部署200个传感半径R=60 m,感知视角2α=90°的节点,如图7(a)所示,此时网络初始覆盖率为 86.37%,并且存在着大量的覆盖冗余。图7(b)为同一时间关闭覆盖冗余度较高的节点,虽然降低了网络覆盖冗余;但由于关闭较多有效覆盖节点(工作节点数为113),造成大量的覆盖盲区,大大降低了网络的覆盖率(77.92%)。图7(c)表示经过本文基于虚拟势场的网络节点调整,在第27轮网络达到稳定,其覆盖率为 96.28%,但网络仍存在覆盖冗余节点。图7(d)表示经过本文基于学习自动机的节点休眠调度策略后网络覆盖情况,可以看出网络冗余覆盖率得到显著的降低,但由于保留大量有效覆盖节点(工作节点数为137),网络整体覆盖率无太大影响,仍保持在 95.83%。

4.2收敛效果分析

本文分别考虑改进的虚拟势场算法和学习自动机节点调度算法的收敛性。

图7　网络覆盖的实例效果

(1) 改进的虚拟势场算法

由于文献[6]已经对虚拟势场算法的收敛性进行过验证,本部分主要从收敛速度兼顾覆盖效果2方面将本文算法与PFCEA、VCFCEA中虚拟势场算法进行比较,节点的传感半径R=50 m其余实验参数与相同。

从图8可以看出, PFCEA、VCFCEA和本文改进的虚拟势场收敛次数分别为25、31和37,并且在覆盖率方面本文算法也优于PFCEA、VCFCEA算法。本文算法和VCFCEA在这2方面优于PFCEA的原因是:前2种算法均采用考虑网络覆盖的虚拟力模型,根据虚拟力动态调整节点转动角度,因此在收敛速度和覆盖率方面相对PFCEA都有提升。同时,本文算法优于VCFCEA是因为本文采用了改进的虚拟力覆盖模型,并综合考虑虚拟力的向心和切向分力对转动角度的作用,进一步结合网络覆盖率变化对转动角度调整,从而提高网络覆盖率的同时,加快了网络收敛速度。并且从图8中可以看出,由于本文算法根据网络覆盖率变化自适应调整转动角度,因此在覆盖初期网络可以快速调整,并且在覆盖收敛时网络调整的幅度也相应降低,有利于网络快速达到稳定状态。

图8　PFCEA、VCFCEA和本文中虚拟势场算法比较

(2) 基于学习自动机的节点休眠调度算法

为了讨论该算法的收敛性,本文针对4种不同节点规模的网络(100, 150, 200, 250,300)分别随机生成网络拓扑,首先采用基于虚拟势场的节点感知方向调整算法得到调整后的网络覆盖率p0,在其基础上采用本文节点休眠调度算法得到网络最终覆盖率p1，每种网络分别执行50次,并统计对应的收敛次数平均值。实验结果如表2所示。

表2　基于学习自动机的节点休眠调度算法收敛性分析

由表2可知,基于学习自动机的节点调度算法在各种规模网络的收敛次数一般维持在20次左右，而在近于饱和的网络中(如网络节点为300),学习迭代次数也只有27次,因此该算法具有良好的收敛性。同时,经过节点休眠调度后各的网络覆盖率也没有受到明显的影响(仅降低0.01左右)。需要注意的是:本文采用学习自动机学习休眠控制策略看似增加了算法的复杂度,但一方面,仅有部分特定节点参与学习过程;另一方面，学习自动机中算法相对于虚拟力调整过程的运算复杂度较低,从而并不影响算法高效执行。 因此这种算法可以在有限次学习过程内完成冗余节点的休眠调度控制,并缓解了关闭冗余节点带来的网络覆盖盲区问题。

4.3网络参数分析

本节主要讨论网络中3个主要参数对本文算法性能的影响,其分别为:网络节点规模N、节点感知半径R和感知视角2α。针对这3个参数,本节将本文算法和VCFCEA算法在网络覆盖增强和关闭冗余覆盖情况进行综合比较和分析。

图9表示针对不同节点数目的网络覆盖率和冗余节点关闭数目。从图9(a)中可以看出,2种算法网络节点数较低时,网络初始覆盖率较低,并且经节点感知角度调整后覆盖冗余也较小,因此关闭的节点较少。在网络节点数超过100时,本文算法的网络覆盖率较VCFCEA有了显著提升，并且随着节点数目增多,网络覆盖提升差值Δp呈逐渐增大趋势,当节点数目为150时,该值达到最大。此后随着节点数目进一步增多,2种算法都保持在较高的覆盖率,而本文算法的网络覆盖率始终领先于VCFCEA。同时,随着网络节点的增加,网络中关闭的重复冗余覆盖节点也不断增加。需要注意的是:本文算法关闭的网络节点数目始终低于VCFCEA,这是由于VCFCEA在同一时间关闭所有覆盖冗余度高的节点,因此关闭了更多节点,但这样容易产生网络覆盖盲点,造成网络覆盖率降低(如图9(a))。本文则采用学习自动机,通过相邻节点间交互信息,不断对所选动作进行奖惩,从而逐渐选择更为合理的节点调度策略,缓解覆盖盲点问题的同时保留更多有效节点,提升了网络覆盖率。综合图9(a)和图9(b)可以看出,不论稀或疏密集的网络,本文算法都能取得更高的覆盖率和更优的网络节点休眠调度策略。

图9　节点规模N的影响,R=60 m, 2α=90

图10和图11分别表示在不同感知半径、感知视角2个参数下算法的实际效果,从图中不难看出这2个参数具有和节点数目类似对算法的影响效果。当感知半径或感知视角逐渐增大时, 2种算法的网络覆盖率均得到提升,并且本文算法相对于VCFCEA网络覆盖增强幅度更大,而当网络参数增大到一定值时,网络覆盖率维持在较高的覆盖率。在此过程中,网络中休眠节点也在不断增加,本文算法能够更为合理的关闭冗余节点,使得网络有更多有效节点用以感知环境信息提高覆盖质量。

图10　感知视角2α的影响, R=60 m, N=200

图11　传感半径R的影响, N=200, 2α=90°

5结论

针对传统虚拟势场方法采用固定角度调整感知方向的问题,本文采用基于距离和网络重复覆盖率的虚拟力改进模型,根据虚拟力的向心和切向分力综合控制感知方向的改变,并根据网络覆盖率变化速率进一步调整节点的转动角度,从而达到自适应调整网络节点感知方向的目的。针对同时关闭冗余节点造成的网络覆盖盲点问题,本文引入学习自动机,根据其与周围环境的交互、自身动作的奖惩等增强学习机制,经过有限次学习过程学习到更为合理的冗余节点调度策略。仿真实验表明,相对于PFCEA、VCFCEA算法,本文能够高效的提升网络覆盖率和覆盖调整速度,并学习到更为合理的冗余节点休眠调度策略,从而实现了增强网络覆盖的同时均衡能耗的目的。

参考文献：

[1] Akyildiz I F, Melodia T, Chowdury K R. Wireless multimedia sensor networks:a survey[J].IEEEWirelessCommunications, 2007, 14(6):32-39.

[2] Ren Y, Zhang S D, Zhang H K. Theories and algorithms of coverage control for wireless sensor networks[J].JournalofSoftware, 2006, 17(3):422-433.(任彦, 张思东, 张宏科. 无线传感器网络中覆盖控制理论与算法[J].软件学报, 2006, 17(3):422-433.)

[3] Ai J, Abouzeid A A. Coverage by directional sensors in randomly deployed wireless sensor networks[J].JournalofCombinatorialOptimization, 2006, 11(1):21-41.

[4] Tao D, Ma H D. Coverage control algorithms for directional sensor networks[J].JournalofSoftware, 2011, 22(10):2317-2334.(陶丹, 马华东. 有向传感器网络覆盖控制算法[J]. 软件学报, 2011, 22(10):2317-2334.)

[5] Guvensan M A, Yavuz A G. On coverage issues in directional sensor networks:a survey[J].AdHocNetworks, 2011, 9(7):1238-1255.

[6] Tao D, Ma H D, Liu L. A virtual potential field based coverage-enhancing algorithm for directional sensor networks[J].JournalofSoftware, 2007, 18(5):1152-1163.(陶丹, 马华东. 基于虚拟势场的有向传感器网络覆盖增强算法[J]. 软件学报, 2007, 18(5):1152-1163.)

[7] Huang H, Sun L, Wang R, et al. A novel coverage enhancement algorithm for image sensor networks[J].InternationalJournalofDistributedSensorNetworks, 2012,32(1):1-11.

[8] Huang S, Cheng L L. A low redundancy coverage-enhancing algorithm for directional sensor network based on fictitious force[J].ChineseJournalofSensorsandActuators, 2011, 24(3):418-422.(黄帅,程良伦. 一种基于虚拟力的有向传感器网络低冗余覆盖增强算法[J]. 传感技术学报, 2011, 24(3):418-422.)

[9] Zhao J, Zeng J C. A virtual centripetal force-based coverage-enhancing algorithm for wireless multi-media sensor networks[J].IEEESensorsJournal, 2010, 10(8):1328-1334.

[10] Akyildiz I F, Melodia T, Chowdhury K R. Wireless multimedia sensor networks:applications and testbeds[J].ProceedingsoftheIEEE, 2008, 96(10):1588-1605.

[11] Pescaru D, Istin C, Curiac D, et al. Energy saving strategy for video-based wireless sensor networks under field coverage preservation[C]∥ProcoftheIEEEInternationalConferenceonAutomation,QualityandTesting, 2008:289-294.

[12] Chen J, Zhang L, Kuo Y H. Coverage-enhancing algorithm based on overlap-sense ratio in wireless multimedia sensor networks[J].IEEESensorsJournal, 2013, 13(6):2077-2083.

[13] Mohamadi H, Ismail A S, Salleh S, et al. Learning automata-based algorithms for solving the target coverage problem in directional sensor networks[J].WirelessPersonalCommunications, 2013, 73(3):1309-1330.

[14] Mohamadi H, Ismail A S, Salleh S. Utilizing distributed learning automata to solve the connected target coverage problem in directional sensor networks[J].SensorsandActuatorsA:Physical, 2013, 198(1):21-30.

[15] Nicopolitidis P, Papadimitriou G I, Pomportsis A S, et al. Adaptive wireless networks using learning automata[J].IEEEWirelessCommunications, 2011, 18(2):75-81.

陈莹(1976-),女,副教授,博士,主要研究方向为多媒体传感器网络、计算机视觉。

E-mail:chenying@jiangnan.edu.cn

曹立志(1987-),男,硕士研究生,主要研究方向为无线传感器网络。

E-mail:coleadge@qq.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141120.1831.003.html

Virtual potential field and learning automata based coverage control

algorithm for directional sensor networks

CHEN Ying, CAO Li-zhi

(KeyLaboratoryofAdvancedProcessControlforLightIndustry,MinistryofEducation,

JiangnanUniversity,Wuxi214122,China)

Abstract:Aiming at solving the problems of network coverage enhancement and redundant node scheduling, a coverage control protocol based on virtual potential field and learning automata is presented. An improved virtual force model based on both the distance and the overlapping sensing rate is proposed, which considers the effect of virtual centripetal and tangential force on the perceived angle adjustment. By establishing the relational model between the micro virtual force and the rotational angle, the algorithm macroscopically controls the adjustment of the node angle according to the coverage rate of the overall network, and adjusts the node sensing direction reasonably. Furthermore, a coverage strategy based on learning automata(LA)is presented, in which the LAis designed for information exchange with the surrounding environment according to the overlapping sensing rate and energy level of nodes. It learns to choose the optimal scheduling scheme for redundant nodes in the network. Simulations show that the algorithm can significantly enhance the network coverage, and effectively control the network coverage redundancy.

Keywords:directional sensor network; virtual potential field; learning automata; coverage enhancement; node scheduling

作者简介：

中图分类号：TP 391

文献标志码：ADOI:10.3969/j.issn.1001-506X.2015.05.31

基金项目：国家自然科学基金(61104213)资助课题

收稿日期：2013-12-18；修回日期：2014-10-12；网络优先出版日期：2014-11-20。