基于自组织特征映射的移动传感器网络控制

赵晓萌, 王朝立

(上海理工大学光电信息与计算机工程学院,上海 200093)

基于自组织特征映射的移动传感器网络控制

赵晓萌, 王朝立

(上海理工大学光电信息与计算机工程学院,上海 200093)

针对概率型感知模型的移动传感器网络中覆盖区域为时变的情况,提出了一种基于自组织特征映射的实时覆盖算法.其中自组织特征映射依据实时采样的样本点来对覆盖目标区域进行拓扑映射,并依据多智能体系统中的一致性控制算法使移动传感器载体形成预定编队,完成覆盖任务.最后通过实验仿真验证了该算法的优良性能.

移动传感器网络;自组织特征映射;编队控制;时变覆盖区域

移动传感器网络(mobile sensing networks)是由多个移动传感器载体构成的整个网络拓扑,载体之间可有部分的信息交换,即系统具有通讯拓扑结构.这样通过传感器获得的数据以及载体之间的信息交互达成最大化利用传感器检测到的信息来完成预定任务.传感器覆盖问题则体现了整个网络监测水准[1],是在网络节点数目、网络计算能力等约束下使得无线传感器网络的资源得到合理分配.对于传统的静态覆盖问题,文献[2-7]通过提出不同的目标函数和约束条件来建立优化问题,应用粒子群算法、遗传算法、模拟退火算法、蚁群算法及鱼群算法等启发式随机搜索算法来解决这一问题.但对于动态覆盖问题,启发式搜索算法由于算法的复杂度过高使得网络不能满足很好的实时性要求.文献[8]研究了移动传感器网络的覆盖问题,提出了质心泰森多边形分区(centroidal voronoi partitions)的方法,并从理论上证明了算法的可行性.文献[9-10]通过采用不同的优化目标来改进算法,分别是异同的感知半径与能量消耗优化两个方面.文献[11-12]则从群集控制的角度来研究覆盖算法.文献[11]引入了信息函数来测量传感器的传感质量,通过群集算法使得整个网络保持连通且使传感器覆盖范围最大.文献[12]则采用连续的一致性卡尔曼滤波器(Kalman-consensus filtering)使得移动传感器网络能够估计出带覆盖区域位置信息.文献[13]建立了一种基于梯度法且保持网络连通的分布式覆盖算法,并研究了覆盖区域中存在多边形障碍的情况.

本文假设所有传感器检测范围相等,故单个传感器覆盖区域是一半径为传感器最大检测距离的圆形区域,这样对于多传感器覆盖问题,即是在使得指定区域覆盖面积最大且重复覆盖区域面积最小的目标下,寻找最优的传感器节点部署位置.但事实上,对于传感器检测半径全部相等的情况,区域覆盖问题中节点部署最优解的部署形态基本是类似的,即形如正三角形这种子结构.这种子结构的特点是可以无盲区地进行拼接,通常覆盖区域远远大于单个传感器覆盖范围,所以,对于已经指定的区域,按子结构依次拼接直到覆盖指定区域即可,这样盲区只会在覆盖边界产生.同时,对于移动传感器网络,指定覆盖区域可以是移动的,甚至是随着时间变化的,采用传统的启发式搜索算法由于算法的复杂度过高使得网络不能满足很好的实时性要求,因此,有必要寻找一种快速的适用于动态覆盖区域的自适应算法来实时地求得传感器部署位置.

1 系统模型

1.1 探测区域模型

考虑待测监测区域为n维空间内一个闭合连通域Ω⊆瓗n,在实际应用中,n取2或3对应平面及立体覆盖区域.为了能够方便算法映射出传感器部署期望位置,将Ω离散化,在区域内按离散步长τ平行于坐标轴方向依次从区域Ω内提取覆盖热点,考虑到覆盖区域可能是平移移动的,则从热点中随机选择一个热点为目标热点位置矢量c0∈瓗n,作为绑定在该区域上的移动坐标系原点.设一个连通域集合珚Ω={Ω1,Ω2,…,ΩM},并假设覆盖区域具有切换时刻t1,t2,…,tM.

1.2 载体模型

有N个标号为1～N自治移动载体,每个移动载体搭载1个传感器,并假设载体质心位置与传感器质心位置重合.载体模型为=ui,i=1,2,…, N,xi∈瓗n,xi为载体i的位置矢量,ui∈瓗n,ui为载体i的控制矢量.假设其中仅有部分载体能够获得待监测覆盖区域中的目标热点的相对自身位置,并假设此目标热点具有模型=f0,f0∈瓗n,f0为目标热点虚拟速度矢量控制项.其余热点在目标热点移动时与目标热点距离始终是有界的,即存在以有限半径为R的球域,使得下式成立:

ci(t)-c0(t)≤R,i=1,2,…,p-1,∀t＞0(1)式中,ci(t)为覆盖区域内热点位置矢量,p为区域内热点总数.

1.3 感知模型

传统的感知模型分为两种:第一种为确定性感知模型,即认为传感器感知半径为硬性边界,小于等于该感知半径的热点即被认为以概率1检测到,而大于该感知半径的热点认为检测不到;第二种为概率性感知模型,即不再是以概率1检测到热点,而是服从一定的概率分布.

本文采用第2种传感器感知模型,假设所有传感器感知模型一致,并定义为高斯概率型,具体形式为

假设单个热点被每个传感器感知是相互独立的,则单个节点被整个传感器网络感知的概率为

当σ→0时,概率性感知模型将转变为确定性感知模型,即可认为确定性模型为概率性模型的一种形式.

2 自组织特征映射

自组织特征映射(self-organizing feature map,简称SOFM)是一种无监督竞争学习神经网络,可以通过神经元之间的竞争实现大脑神经系统中的近兴奋远抑制功能,并具有将高维输入向量映射到低维向量的能力.与普通竞争神经网络不同,SOFM具备模拟输入向量拓扑结构的特性,即输入拓扑映射的功能,因此,本文使用SOFM对覆盖区域进行拓扑映射以确定传感器空间部署位置.

依据覆盖区域的维数n,制定相应的神经元权重向量wi∈瓗n,i=1,2,…,N,即神经元数目与传感器数目一致.则覆盖区域内热点作为SOFM的输入样本,逐次输入到SOFM中,神经元之间展开竞争,竞争的目的是寻找与当前输入cj最为匹配的神经元权值wi,输入与权值间的匹配规则采用欧氏距离度量,即寻找满足下式的神经元:

按照此邻域函数,设计神经元l的权系数更新策略为

3 算法设计

借助于SOFM的实时映射能力,现介绍设计步骤.

步骤1 获取初始覆盖区域Ω⊆瓗n,将区域离散化,取得热点集C=[c|c∈Ω],并任意选取一个热点作为目标热点c0.

步骤2 如果t=tk,tk为覆盖区域拓扑切换时刻,则重新获取覆盖区域热点集C并随机选择目标热点c0;否则,转步骤3.

步骤3 将热点集C以目标热点c0作坐标平移变换,将变换后的热点集合作为SOFM的输入训练SOFM,具体流程如下:

式中,m为反馈系数,m＞0;Ni(t)表示t时刻载体i的邻接载体集合;hi表示载体i是否能够获取目标热点的相对位置信息,即hi＞0,表示能够获取目标热点信息.

步骤5 对各个传感器载体施加控制,转步骤2.

从上述算法可以看出,整个动态覆盖控制策略大致分为两步:第1步由SOFM确定出传感器部署位置;第2步由控制器来使传感器载体跟踪到预定部署位置.

式(8)中出现w·i并不是说在覆盖区域未切换时SOFM权值还在更新,而是为了描述在切换拓扑时刻间的热点的连续线性变换(如热点的旋转、放缩及翻转等).事实上,这里的wi即表示了SOFM中神经元的权值向量,又表示了由SOFM映射出的预定部署位置向量.

上述算法没有确定出传感器数目N,在实际应用中,考虑到覆盖区域的时变特性,N的数目是无法确定的.但若已知连通域集合珚Ω内各个覆盖区域的面积,则可依据下式给出确定的传感器数目[14]:

a.按照正三角形的拼接子结构来构成竞争层神经元权值拓扑初值,迭代步数k′=0;

b.从离散化的覆盖区域中随机选择热点cj作为SOFM输入;

c.根据式(5)确定获胜神经元i,并依据式(7)来更新所有神经元的权值及邻域函数和学习率;

式中,N为节点数量;Ra为监控区域面积;Rs为节点感知半径(确定性模型).

在感知模型为概率型时,为确保网络的覆盖率,可取Rs=μ-3σ.

4 理论分析

考虑一有向连通图G=(V,E),其中,V={ν1, ν2,…,νn}为节点集合,E⊆{(i,j):νi,νj∈V}为边集合.用图G来表示传感器载体的通讯拓扑,即节点来表示载体,而边则表示载体间通讯是否建立.本文假设通讯拓扑为固定有向的且强连通,定义载体i的邻接载体集合为Ni={j∈V:(i,j)∈瓗},且有向图G的邻接矩阵A=[aij],其中

5 仿真研究

在实际应用中,很少载体能够满足一阶积分模型,不过大多数载体可简化为如下模型:

式中,xi,yi分别为载体i的位置和朝向角度;vi, θi分别为载体i的速度和角速度.

若假设载体为一差动驱动小车,则上述变换实质上是将载体模型的质点位置由载体两轮轮距中点位置移动到了垂直于车轴前方距离b的A点,如图1(a)所示,因此,可假设传感器位置安装在图中A点处,那么,前述算法完全适用于此类型的载体.

仿真设置待覆盖区域为圆形、三角形和正方形这3种形状的闭区域Ω1,Ω2和Ω3,切换时间设定为t1=10 s,t2=20 s.取区域中心为目标热点c0,且有=[cos t,sin t]T,c0(0)=[4,0].Ω1和Ω2为平移区域,即只作平移变换,而Ω3既作平移变换又作旋转变换,3个区域均为时变区域.通讯拓扑图为有向圈,如图1(b)所示,即满足强连通条件.设置传感器载体数目为25,初值在[-3,3]×[-3,3]区域以均匀分布随机生成,迭代步长为0.02 s.

图1(c)为SOFM对圆形覆盖区域的映射结果,可以看出图中的近似正三角形的组态子结构.图1(d),1(e),1(f)分别为不同时刻不同形状覆盖区域的覆盖结果,由图中SOFM可灵活地映射出不同形状的区域,且传感器载体可精确地跟踪到指定覆盖地点完成区域覆盖工作.

图1 仿真结果Fig.1 Simulation results

6 结 论

首先对带覆盖区域进行离散化,并定义热点与目标热点的概念,然后通过对覆盖区域的离散点采样来训练SOFM的参数,使得SOFM的权值能够映射出带覆盖区域的形态,再由SOFM的权值信息通过一致性算法解决移动传感器网络对时变覆盖区域的实时覆盖问题.仿真结果表明了该算法的可靠性及高效性.

[1] Meguerdichian S,Koushanfar F,Potkonjak M,et al. Coverage problems in wireless ad-hoc sensor networks [C]∥Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies.Anchorage,AK:IEEE,2001:1380-1387.

[2] Kulkarni R V,Venayagamoorthy G K.Particle swarm optimization in wireless-sensor networks:a brief survey[J].IEEE Transactions on Systems,Man,andCybernetics,Part C:Applications and Reviews,2011, 41(2):262-267.

[3] Jin SY,Zhou M,Wu AS.Sensor network optimization using a genetic algorithm[C]∥Proceedings of the 7th World Multiconference on Systemics,Cybernetics and Informatics,2003:109-116.

[4] Kannan A A,Mao G O,Vucetic B.Simulated annealing based localization in wireless sensor network[C]∥The IEEE Conference on Local Computer Networks, 2005:513-514.

[5] Zou M,Ping Z,Zheng S J,et al.A novel energy efficient converage control in WSNs based on ant colony optimization[C]∥International Symposium on Computer Communication Control and Automation, 2010:523-527.

[6] 刘丽丽,陈玮.基于高斯优化的精英鱼群算法研究[J].上海理工大学学报,2014,36(3):295-298.

[7] 袁光辉,樊重俊,张惠珍,等.一种新的粒子群算法与人工鱼群算法的混合算法[J].上海理工大学学报, 2014,36(3):223-226,238.

[8] Cortes J,Martinez S,Karatas T,et al.Coverage control for mobile sensing networks[J].IEEE Transactions on Robotics and Automation,2004,20 (2):243-255.

[9] Baghdad Abad H M,Moezzi K,Aghdam AG,et al.Selfdeployment algorithms for field coverage in a network of nonidentical mobile sensors[C]∥2011 IEEE International Conference on Communications,2011: 1-6.

[10] Mahboubi H,Momeni A,Aghdam A G,et al.Optimal target tracking strategy with controlled node mobility in mobile sensor networks[C]∥American Control Conference,2010:2921-2928.

[11] Jalalkamali P,Olfati-Saber R.Information-driven selfdeployment and dynamic sensor coverage for mobile sensor networks[C]∥American Control Conference, 2012:4933-4938.

[12] Olfati-Saber R,Jalalkamali P.Coupled distributed estimation and control for mobile sensor networks[J]. IEEE Transactions on Automatic Control,2012,57 (10):2609-2614.

[13] Zhong M,Cassandras C G.Distributed coverage control and data collection with mobile sensor networks[J].IEEE Transactions on Automatic Control,2011,56(10):2445-2455.

[14] Williams R.The geometrical foundation of natural structure:a source book of design[M].New York: Dover Publications Mineola,1979.

[15] Godsil C D,Royle G,Godsil C D.Algebraic graph theory[M].New York:Springer,2001.

[16] Qu Z.Cooperative control of dynamical systems: applications to autonomous vehicles[M].London: Springer,2009.

[17] Das A,Lewis F L.Distributed adaptive control for synchronization of unknown nonlinear networked systems[J].Automatica,2010,46(12):2014-2021.

(编辑:石 瑛)

Mobile Sensor Networ ks Control Using Self-organizing Feature Map

ZHAOXiaomeng, WANGChaoli
(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

Focusing on the time-varying coverage region for mobile sensor networks of probabilistic model of perception,a real-time coverage algorithm was proposed based on the self-organizing feature map which is used for mapping the target coverage region in the light of real-time sampling points.Based on the consensus control algorithm in multi-agent system,the coverage algorithm drives the networks to form a predetermined formation to coverage task region.The simulation experiments verify the excellent performance of the algorithm.

mobile sensing networks;self-organizing feature map;formation control; time-varying coverage region

TP 24

A

1007-6735(2015)03-0251-06

10.13255/j.cnki.jusst.2015.03.009

2014-01-10

国家自然科学基金资助项目(61374040);上海市教委科技创新项目(13ZZ115);上海市研究生创新项目(5413302102);上海市重点学科建设资助项目(S30501)

赵晓萌(1988-),男,硕士研究生.研究方向:多智能体系统、神经网络控制.E-mail:zxiaomzxm@163.com

王朝立(1965-),男,教授.研究方向:非线性控制、鲁棒控制、机器人动力学控制.E-mail:clclwang@126.com