节点部署算法范文（精选7篇）
节点部署算法 第1篇
关键词：粒子群优化算法,无线传感网络,节点部署
0 引言
粒子群优化算法(Particle Swarm Optimization,简称PSO)[1,2]是1995年由Kennedy J和Eberhart R在受鸟群觅食行为的启发下提出的。由于PSO算法具有易于实现、参数变化少、不包含梯度信息等优点,且能够有效地优化各种函数,逐渐吸引了众多学者的关注,趋于完善和成熟中。
无线传感网络(Wireless Sensor Networks,简称WSN)[3]是由大量集成了传感器、数据采集、处理和无线通信能力的小体积、低成本的传感节点构成的无线自组织网络。节点部署[4,5]问题作为无线传感需要解决的关键技术之一,已受到众多研究者的关注。
本文从群智能算法角度提出对于粒子群优化算法的无线传感节点部署方法探讨。在综合考虑网络节点的覆盖和连接问题的情况下,建立传感节点部署优化模型,以覆盖率为优化目标,可以利用粒子群优化算法求解该部署模型。
1 粒子群优化算法
1.1 算法原理
粒子群优化算法来源于对鸟群社会模式的研究和行为的模拟,鸟群在天空中飞行,每只鸟被抽象成没有质量和体积的粒子。这些粒子具有两个属性:位置和速度。粒子在飞行过程中是受到两个极值的作用来调整速度和位置的。这两个极值中,一个是粒子个体历史最优经验pbest,另一个是群体历史最优经验gbest。全体粒子通过迭代进化,逐步向优秀的个体接近,找出优化问题的解。
假设在一个D维的搜索空间中,有N个粒子组成的群体,其中第i个粒子的两个属性分别可表示为:位置xi=(xi1,xi2,…,xi D),速度vi=(vi1,vi2,…,vi D);粒子个体历史最优pbest位置Pi=(pi1,pi2,…,pi D),群体历史最优gbest位置Pg=(pg1,pg2,…,pg D)。寻优时,每个粒子两个属性值的更新(速度和位置)按如下公式进行迭代进化:
式(1)、(2)中,i=(1,2,…,N),d=(1,2,…,N);c1和c2为加速常数(也称加速因子或学习因子),加速常数可调整个体自身经验和群体经验对粒子运动影响的大小;ω为惯性权重,对算法全局搜索和局部搜索有平衡作用;r1、r2为相互独立的随机数,服从(0,1)上的均匀分布;vtid为粒子i迭代至第t代时的速度,vidt+1为粒子i迭代至第t+1代时的速度;xtid为粒子i迭代至第t代时的位置,xidt+1为粒子迭代至第t+1代时的位置。
粒子速度的迭代更新是按公式(1)进行,从社会角度来看,其中的第一部分表示粒子当前速度是下一时刻速度的进化基础;第二部分为粒子与自身最优位置间的距离,表示粒子的自身经验的影响,称为认知部分;第三部分为粒子与全群最好位置之间的距离,表示群体粒子间的信息共享和合作,称为社会部分。由此可知,粒子在飞向最优位置的运动过程中,不仅受粒子个体曾经经历过的最优位置影响,也受群体粒子中曾经经历过的最优位置的影响,通过这两个作用力,导引全体粒子飞向全局最优位置。
公式(2)是粒子位置的更新方程,表示粒子迭代进化至t+1代时的位置是在第t代位置xtid的基础上加上粒子迭代一次飞行的距离vidt+1*1。
1.2 算法流程
PSO算法在对问题优化求解时,群体中的粒子是通过迭代逐步飞向问题的解的,算法的流程简单。其流程为:
STEP1:初始化粒子群,对算法各参数做好初始化设置,所有粒子的个体最优pbest设为粒子初始位置,比较找出群体最优gbest。
STEP2:根据适应度函数和每个粒子的位置,计算出各粒子的适应度值。
STEP3:将各粒子当前适应度值与粒子个体历史最优适应度值比较,若个体当前适应度值比个体历史最优适应度值更优,则替换个体历史最优pbest。
STEP4:将各粒子个体历史最优pbest的适应度值与当前群体历史最优gbest比较,如果优于则替换之pbest。
STEP5:各粒子的速度更新按公式(1)进行,各粒子的位置更新按公式(2)进行。
STEP6:判断算法是否终止迭代(一般为找到了满意解或者最大迭代次数之后),如果满足终止迭代条件,则输出最优解;否则转向STEP2继续执行。
PSO算法具体流程如图一所示。
2 无线传感节点部署
2.1 节点部署问题描述
无线传感节点部署[6]是运用合适的算法部署监测区域中传感节点位置,优化现有的网络资源,使得网络在未来的应用中获得最大利用率或单个任务的最少消耗量。在节点部署过程中,一些感知目标不能被任意的一个传感节点有效覆盖,即会出现“覆盖盲区”现象,如图二所示。此时,对于目标监测信息会有所遗漏。另外,感知目标也有可能会被多个节点同时覆盖,即出现“覆盖冗余”的情况。当覆盖冗余发生时,传感器节点会消耗过多的能量,将导致节点失效或者效率降低,进而致使整个传感网络服务质量下降,这两种情况是节点部署所要避免的。从网络应用的时间周期角度,可将节点部署分为静态部署和动态部署。静态部署是指节点部署在监测区域的指定位置之后不能移动,其部署方案先于网络启动之前,不考虑网络的动态变化,独立于网络的状态并贯穿于整个网络生命周期。然而在实际应用中,动态节点部署显得尤为重要。在一些沙漠或者湿地等较复杂地区播撒节点,这些节点大多数采用飞机或者导弹随机播撒到监测区域。由于随机播撒节点易出现覆盖盲区,网络节点也会因供电、计算、存储、通信有限而导致失效,这时网络需具备自组织能力。当网络额外加入新节点,网络需要重新部署。针对这些实际情况,需要网络动态部署。动态部署是指传感节点布置在监测区域之后,由于节点失效等情况,网络出现覆盖盲区,为了减少网络覆盖盲区,利用传感节点的移动能力,应用算法自适应调整网络覆盖,在传感节点移动能耗最小的情况下,使得覆盖监测区域最大化。本文研究的是动态节点部署方案。
在此,节点部署问题可以描述为:对于给定的监测区域大小、节点数目,如何在节点失效的情况下,利用节点的移动能力,对网络进行自适应调整,尽量减少覆盖盲区和覆盖冗余情况,使得网络覆盖达到最大。其实质是根据节点的位置信息建立节点部署优化模型,进而寻求求解该模型方法的一个优化问题。
2.2 节点部署相关概念及评价指标
为了更好地理解节点部署内容,先介绍一些节点部署方面的相关概念,有感知范围、邻居节点、连通性、感知模型等。评价一个部署方法有效性必须依赖于一套节点部署评价指标,覆盖率和移动有效距离为两个重要的评价标准。
(1)感知范围:是指节点所能够感知目标信息的最大探测范围。感知范围由每个节点自身硬件特性所决定。节点感知范围越大,所能够探测目标感知信息能力越强。在无线传感中,感知范围的取定与节点感知模型有关。
(2)邻居节点:是指在某个节点感知范围之内的点。在无线传感节点部署时,节点与其邻居节点的覆盖范围应该适当相交。相交不能太多,否则会出现覆盖冗余现象;也不能相离,否则会出现覆盖盲区现象。
(3)连通性:传感节点之间可以采用无线多跳等方式进行通信,以便协同地完成数据采集、处理工作。有效的连通则可以保证网络的感知、采集、处理、融合的有效进行。在节点部署时,覆盖和连通需要同时保证。如果不能连通,节点之间的信息不能被传送;如果不能覆盖,连通也便失去了意义。
(4)感知模型:感知模型将节点的物理位置和空间位置的几何关系建立起来[7],决定了无线传感网络的覆盖范围和监测能力。常见的概率感知模型有很多,例如二元感知模型、随机模型、统计模型、障碍模型、概率模型等。
下面介绍本章将用到的覆盖和移动有效距离两个评价指标。
(5)移动有效距离(简称MP)[8]:表征的是所有节点初始位置与最终位置距离之和,它一定程度上反应了整个节点部署能量消耗。假设节点Tk在部署之前的位置为PTk=(xk,yk),Tk节点在部署完之后的最终位置为PTk1=(xkt,ykt),则节点Tk移动的距离为:
(6)覆盖:覆盖考虑的是节点能否有效覆盖监测区域,尽量使得监测区域的感知信息能够被完全监测,不出现过多的覆盖盲区。特别考虑在动态调整节点位置时,网络能否自适应调整以满足实际覆盖过程。
2.3 节点部署优化模型的建立及假设
假定在一个二维平面检测区域z2={(x,y),0≤x≤a,0≤y≤a}随机播撒n个传感节点,节点集合ω={T1,T2,…,Tk,…,Tn);传感节点Tk的位置PTk=(xk,yk),;效感知半径为r,即每个节点的覆盖模型是以节点坐标为圆心,r为半径的圆;目标位置P=(x,y),目标P与节点Tk的距离为:
在实际应用中,由于检测环境和噪声的干扰,传感器节点感知模型呈一定的概率指数分布[9],即节点PTk对目标P的覆盖度Cxv(Tk)为:
式(5)中,α1=d(PTk,P)+re-r,α2=re+r-d(PTk,P),re(re
则扩展到n个节点联合检测,目标P覆盖度为:
定义cth为每个目标点覆盖的最小阀值,即:
为了更好地评价网络覆盖率,把二维平面划分成网格,如图三所示。网格之间的距离称为粒度,记为cth。粒度越小,求解精度越高。计算所有节点对网格的联合检测覆盖度,满足公式(6)的网格占整个网格的比例即为网络有效覆盖率。
为了简化模型,根据传感节点部署特点作如下假设:
(1)网络包含一个中心处理节点,有较强的计算能力。
(2)所有传感节点可以自由移动,具有相同的发射功耗,通信半径为R=2r。
(3)网络中所有节点时钟同步[10],节点位置信息可以通过GPS等定位技术获取。
3 基于粒子群算法的无线传感节点部署探讨
3.1 节点位置与粒子个体位置的映射
粒子群优化算法中,适应度函数用来评价节点位置的好坏,粒子适应度函数为对应的有效覆盖率。为了将节点位置转化为粒子个体的位置,需建立粒子个体位置与节点位置的关系,将节点的部署转变为找粒子群中的最优粒子。
3.2 节点位置调整机制
考虑到实际应用中存在节点失效的情况,提出一种节点位置调节机制:设失效节点为Tk,离它最近的一个节点为Th,当Tk节点失效的话,节点Th将驱动到节点Tk附近,从而使得粒子群优化算法在原有网络节点布局基础上进行优化求解,达到更高效的优化效果。节点Th按照以下公式(9)、(10)进行移动。
式(9)、(10)中PDh、PDk分别表示节点Th、Tk的位置,λ∈[0,1]的随机数。同时,为了防止节点越过检测边界区域太多,造成无效覆盖,限制节点位置为(1/4)r≤xk≤a-(1/4)r、(1/4)r≤yk≤a-(1/4)r。
4 结束语
粒子群优化算法是一种新颖的群体智能算法,无线传感移动节点部署是无线传感需要解决的几大关键技术之一。本文对于粒子群优化算法应用于无线传感移动节点部署进行了探讨。利用粒子群优化算法可以有效优化节点部署,提高网络覆盖率和降低节点移动所带来的能耗损失;开拓了粒子群优化算法的应用研究范围,同时为传感节点部署提供了一种新的思路和解决方案。
参考文献
[1]Kennedy J,Eberhart R C.Particle swarm opti-mization[C].Proceedings of IEEE International Con-ference on Neural Networks.Piscataway:IEEE Press,1995:1492-1498.
[2]Eberhart R C,Kennedy J.A new optimizer us-ing particle swarm theory[C].Proceedings of the6th International Symposium on Micro Machine and Hu-man Science.Piscataway:IEEE Press,1995:39-43.
[3]孙利民,李建中.无线传感器网络[M].北京:清华大学出版社,2006.
[4]任彦,张思东,张宏科.无线传感器网络中覆盖控制理论与算法[J].软件学报,2006,17(03):422-433.
[5]Wang G,Cao G,PORTA T L,Zhang W.Sen-sor relocation in mobile sensor networks In:Proceed-ings of the24th International Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM)Miami,FL,March2005.
[6]谢洁锐,刘才兴,胡月明,等.无线传感器网络的部署[J].传感器与微系统,2007,26(01):4-7.
[7]邹冈,薛锋,刘忠.大面积随机无线传感器网络的覆盖问题研究[J].舰船电子工程,2007,27(03):5-7,50.
[8]史斌彬.无线传感器网络节点部署算法研究[D].无锡:江南大学,2008.
[9]Gallais A,Carle J,Simplot D.Localized Sensor Area Coverage with Low Communication Overhead[C].//Proc of the Fourth Annual IEEE Int’l Conf on Pervasive Computing and Communications,2006:328-337.
节点部署算法 第2篇
无线传感器覆盖问题直接影响网络的成本及感知质量, 因此如何在极大网络覆盖率的同时减少部署节点的数目成为最基本和重要的部分。国内外对WSN节点部署算法已经有很多研究:文献[4]中针对异构传感器网络节点的高密度部署和监测目标非均匀分布的情况, 提出基于模拟退火算法的成本最优部署方法。文献[5]提出了一种高效能的遗传算法, 利用Monte Carlo方法设计一个高效的评价函数, 从少量的随机样本开始, 逐步增加后代的数目, 在不降低解决方案质量的情况下降低了计算时间。文献[6]对已有的监测点位进行筛选, 去除冗余监测点, 得到最佳的监测点。文献[7]通过研究具有混合杂交和间歇变异的改进遗传算法, 解决高密度部署的无线传感器节点集的选择问题。文献[8]通过提出一种最大覆盖集节点部署算法, 以最大覆盖为优化目标进行节点部署。
本文主要研究WSN机场噪声监测系统的节点部署性能, 以机场噪声预测模型为基础, 提出一种适用于机场噪声监测系统的WSN节点部署算法, 即在单个飞机噪声事件驱动下, 利用改进遗传算法的优化部署算法 (Genetic Algorithm Optimize Deployment Algorithm based on Single Aircraft Noise Event, SANE-GAODA) , 有效降低了成本、提高了网络覆盖率。
1 问题建模
1.1 飞机噪声事件模型定义
机场噪声监测系统用来监测飞机噪声数据, 需了解机场内各点实际发生噪声数据, 对于没有设立监测点的机场, 无法已知其噪声数据, 本文利用噪声预测软件INM[8], 通过输入机场、飞机、航班、天气等信息, 可以模拟计算得到机场目标区域内各点的噪声值。根据文献[9]建议的声暴露级LSE来衡量单个飞机噪声事件, LSE是指飞机飞行一架次时某一地点经受的全部噪声换算到1 s的A声级, 考虑噪声强度和持续时间, 适用于噪声监测系统。文献给出了建议LSE噪声限值标准, 如表1所示。
一般监测点在室外, 由表1可知, 当LSE值超过80 d B时就会影响交谈、思考等正常社会活动, 因此对于噪声值超过80 d B的区域就需要设监测点来监测噪声及其变化情况。
设ASE为INM软件在目标监测区域内监测到的所有飞机噪声事件的集合;V为其关联矩阵, 其元素Vik的值表示网格点i是否监测到飞机噪声事件ek (ek∈ASE) , 若监测到, 则为1, 否则为0;设E_LSE为各网格点在每个噪声事件发生时的噪声值矩阵, 其元素即是LSEik表示飞机噪声事件ek发生时, 利用INM软件预测网格点i处的LSE噪声值。
假设Si表示网格点i是否需要被WSN覆盖到。根据飞机噪声事件集合ASE及其关联矩阵, 得到每个网格点i监测到的飞机噪声事件总数, 若网格点i监测事件总数为0, 则Si值为0, 否则为1。
1.2 问题模型
假设目标区域A为矩形区域, 将A网格化, 划分成大小相等的n个网格点, 连续网格点之间的距离根据需要设置的传感器精度确定。根据飞机噪声事件模型, 利用INM软件计算目标区域内能监测到噪声事件的点集合, 飞机噪声事件集合ASE及其关联矩阵, 确定需要监测的m个点集合 (r1, r2, …, rj, …, rm) 。
定义1给定n个传感器节点 (S1, S2, …, Sn) :节点Si的感知范围是以Si为圆心, Rs为半径的圆形区域, 表示为ci={p∈A d (p, si) ≤Rs}, 其中d表示欧式距离, 则整个网络的感知范围可表示为C=∪i∈[1, n]Ci;节点Si的通信范围是以Si为圆心, Rc为半径的圆形区域, 当d (si, sj) ≤Rc时, 则传感器节点si与节点sj能直接通信, 一般节点的通信半径大于感知半径。
定义2给定传感器节点集合S和目标点集合R, 则R中每个目标点都能被传感器网络覆盖感知可等效于目标点集中任意一点至少被S集合中一个节点所覆盖感知。
定义3给定传感器节点集合S, 由S中全部节点构成的网络Gc= (Vc, Ec) 是一个无向图, 其中Vc=S, si, sj∈S, L (Si, Sj) ∈Ec且d (si, sj) ≤Rc。若由S导出通信图Gc中任意两个节点之间都存在一条通信路径, 则称该通信图是连通的;给定目标点集合R, 如果R内的每一个节点至少被集合S内的一个节点覆盖, 则称S为R的覆盖集;若集合S导出的通信图是连通的, 则集合S是R的连通覆盖集。
本文的目的是在目标区域R上部署一个传感器网络S, 即选择S的最小子集, 使得S'完全覆盖R, 并且由S'导出的通信图Gc'连通, 即求最小连通覆盖集。
2 基于改进遗传算法的优化部署算法
遗传算法求解过程始于种群, 种群中每一个解为一个个体。个体解的优劣通过适应度值来评估衡量, 适值高的个体具有较高的生存概率。子代种群由父代通过交叉、变异等遗传运算和适值评估选择产生, 如此反复直至找到全局最优解。为使算法更好地应用于机场噪声监测系统的节点部署, 对算法初始种群产生、选择和交叉算子进行改进。
2.1 基于飞机噪声事件的遗传算法
2.1.1 编码
根据前面介绍的模型得知, 最小集合覆盖问题定义如下:从初始部署的节点中选取一组传感器节点, 要求选取的传感器节点能够完全覆盖目标点, 同时节点集是个连通集, 并且最小化目标函数。因此本文应用二进制编码来实现, 若该传感器被选中, 则二进制取值1, 否则为0, 即将问题可能解φt的染色体编码为φt={s1, s2, …, sn}, sk∈{0, 1}式中, n表示所有候选网格点的数目;sk是决策变量, 表示位置k处是否放置传感器节点, sk=1表示放置, sk=0表示不放置。该编码方式可以将染色体位串划分为多个子串分别优化, 采取并行方式加快解题速度。最后根据最优个体解中编码为1的位置, 得到节点部署的最佳位置。
2.1.2 初始化种群
根据INM软件计算的飞机噪声事件确定目标监测点, 则在初始化时, 假设目标监测点中每个节点处放置一个传感器节点。即初始群体中每个染色体是根据目标监测点来设置的, 假设有m个目标监测点, 则在每个染色体中根据目标监测点位置选择m个基因放置传感器节点, 其值为1, 而其他的基因位值为0。
2.1.3 目标优化函数
本文提出的连通覆盖集问题的优化目标是要保证部署的节点能够覆盖R中的每一个目标, 即R中每个目标至少被一个传感器节点覆盖, 同时满足子集是一个连通集。
令G= (g1, g2, …, gn) 表示网络中节点的连通状态, 其中gi= (gi1, …, gij, …, gin) 且gij∈{0, 1}, gij=1表示节点i与节点j可通信, 反之则不能通信。即
令C=∪i∈[1, n]Ci表示网络中节点的覆盖状态, 其中覆盖向量为Ci= (c1i, …, cji, …, cmi) 1×m且cji∈{0, 1}, 其中cji=1表示目标j处于节点i的感知范围内。即
根据约束条件的意义:保证传感器子集能够覆盖全部目标点, 保证子集是一个连通集。设xi∈{0, 1}, 为解向量第i元素的值
为应用遗传算法求解约束优化问题, 需要将约束优化问题转化为无约束优化问题。根据算法目标是利用最少的节点满足目标覆盖要求, 本文根据约束函数, 考虑在最小化问题中, 适应度值越小, 解的质量就越好。设计适应度函数如下
2.1.4 遗传算子设计
(1) 复制算子。在算法初始阶段要淘汰一些明显不合理的解空间, 以缩小搜索空间, 降低优化速度。本文采用一种回放式随机采样方法, 基本思想是:个体被选中的概率与适应度大小成正比, 设种群数目为K, 个体i的适应度为Fi, 则个体i被选中的概率为。个体累积概率为。
(2) 交叉算子。交叉算子是通过把父代个体的部分结构互换重组, 产生新的子代个体操作。本文采用一致交叉来实现, 通过随机产生与父代染色体长度相同的序列, 并作为屏蔽字来决定子代中哪些需要继承父代个体对应的基因。实现如下:两个父代个体T1和T2, 若屏蔽第i位Mi=0, 则对应的第i位值不发生交叉;反之, 若屏蔽字中第i位Mi=1, 则对应的第i位值发生交叉。
(3) 变异算子。变异算子的设计包括确定变异点的位置和变异位置处的码位替换方法两方面, 即通过将个体染色体编码串上的某些基因值与其他等位基因值替换, 得到新的个体。为提高遗传算法的局部搜索能量, 本文采用均匀设计方法进行变异, 按照变异概率pc对染色体中某些基因位进行变异, 即0和1值互换, 变异位数由变异概率pc及种群数目、个体长度确定。
2.1.5 精英保留操作
本文算法选择操作采用精英方法, 即选择一定数量、适应度最好的个体直接复制到下一代中, 这样在进化过程中某一代的最优解可不被交叉和变异操作所破坏。而精英选择概率的选取也对算法的速度及优化结果有很大的关联, 设α为精英选择概率, 为提高优化速度, α取值不能过小;为使种群保持多样性, α取值也不能过大。
2.2 SANE-GAODA优化过程
本文所提出的算法流程如图1所示。
算法寻优的基本过程如下: (1) 采用二进制编码对初始种群进行编码, 1表示部署节点;0表示不部署节点;个体长度用N位表示;根据飞机噪声事件模型确定目标点集合, 并根据此集合对初始化种群进行优化。 (2) 计算种群内个体适应值, 并将个体按适应度值进行排序。 (3) 检验算法的优化结果是否最优, 如满足最优, 则转入8, 否则转入4。 (4) 记录父代精英个体, 将父代精英个体以概率α直接复制到子代种群中。 (5) 利用一致交叉法对种群进行交叉计算。 (6) 以概率pc对种群进行变异计算。 (7) 将新产生的个体作为代入下一代种群个体, 转入步骤2。 (8) 输出最优部署节点集合。
3 仿真实验
3.1 仿真参数设置
本文用Matlab7.0来评估算法的性能。实验模拟某机场一天50个航班信息, 每次飞行都产生一次噪声事件。取机场内部600 m×600 m的地区进行部署, 首先将该区域划分为12×12的网格, 利用INM软件, 输入机场基础信息及其气候因素、机型组合及航班信息、航迹信息、机场周围地形信息、机场周围网格点位置, 即可预测到每个网格点在噪声事件发生时, 所预测到的噪声值 (E_LSEij表示网格点i在第j个噪声事件发生时所得到的噪声值, 单位d B)
根据式 (1) 得到关联矩阵V
由式 (2) 得到需要被覆盖到的目标点集合R= (18, 19, 20, 21, …, 66, 67, …) 共100个, 且目标点均集中在机场跑道附近区域。
本文目的是求最小连通覆盖集, 为保证初始部署节点能完全覆盖目标区域并形成连通通信网络, 在目标区域内每个网格点的中心部署节点, 则当Rc≥50 m, Rs≥36 m时, 位于网格内所有节点能覆盖所有的目标区域, 形成初始连通覆盖集。遗传优化算法中的各个参数为:种群规模为30, 精英选择概率α=0.1, 变异概率pc=0.4。
3.2 结果及分析
从节点数目进行比较, 设Rs=50 m, Rc=100 m, 种群规模为30, 精英选择概率α=0.1, 变异概率pc=0.4。则文中所提的算法SANE-GAODA (图2中方法1) , 与随机覆盖算法 (图2中方法2) 及均匀覆盖算法 (图2中方法3) 进行了对比, 由此得到本文所提算法能用尽可能少的节点覆盖所有的目标区域, 节约了成本。
再考察节点的感知半径Rs及通信半径Rc对算法性能的影响。由此得知, 计算得到的连通覆盖集的大小与比值Rc/Rs有关。
另外从能量有效性和网络生存期方面比较算法性能。设Rs=36 m, Rc=72 m, 利用本文所设计的算法与贪婪算法作比较。
4 结束语
本文在机场噪声监测环境下以噪声事件覆盖率和部署节点数目构成优化目标, 研究了机场噪声监测系统的WSN节点部署问题, 提出了一种单个飞机噪声事件下的基于改进遗传算法的优化部署方案。仿真分析和实验结果表明, 该算法设计了基于飞机噪声事件的概率感知模型从而降低种群规模, 采用精英保留机制来提高优化速度, 通过引入均匀设计法构造变异算子增强了局部搜索能力, 有效降低了成本、提高了监测噪声数据的精确性, 适合在基于物联网的机场噪声监测系统中应用。
摘要：针对监测系统低成本、高监测精度的需求, 提出一种适用于机场噪声监测系统的WSN节点部署算法:单个飞机噪声事件下基于改进遗传算法的优化部署算法, 设计了基于飞机噪声事件的覆盖连通集模型, 规范了遗传约束函数, 并采用精英保留机制, 提高优化速度, 引入均匀设计法构造变异算子, 增强了局部搜索能力。仿真实验表明, 该算法能快速有效地实现部署节点数目少、飞机噪声事件覆盖率高的优化部署, 同时有效降低了成本、提高了监测噪声数据的准确性。
关键词：无线传感器网络,机场噪声监测,飞机噪声事件,遗传算法,节点部署
参考文献
[1]GIOVANNI N, JOHN A B.A critical examination of an airport noise mitigation scheme and an aircraft noise charge[J].Transportation Research Part D, 2000 (5) :433-461.
[2]XAVIER P, VICEN P, JOSEBA Q.A multi-objective optimization strategy for designing aircraft noise abatement procedures:Case study at Girona airport[J].Transportation Research Part D, 2011 (16) :31-41.
[3]TEO C R, JULES G S.Noise metrics comparison and its use on urban zoning in airport surveys:A Brazilian case study[J].Journal of Air Transport Management, 2008 (14) :304-307.
[4]LI Ming, SHI Weiren.Optimal sensor deployment scheme based on simulated annealing approach in heterogeneous wireless sensor net-works[J].Chinese Journal of Sensors and Actuators, 2010, 23 (6) :855-858.
[5]YOURIM Y, YONG H K.An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks[J].IEEE Transactions on Cybernetics, 2013, 43 (5) :1473-1483.
[6]ASENSIO C, RECUERO M, RUIZ M, et al.Self-adaptive grids for noise mapping refinement[J].Applied Acoustics, 2011, 72 (3) :599-610.
[7]QU Wei, WANG Jinkuan, ZHAO Xu.Optimal coverage strategy based on genetic algorithm in wireless sensor networks[J].Systems Engineering and Electronics, 2010, 32 (11) :2476-2479.
[8]HE X, YANG H, GUI X.The maximum coverage set calculated algorithm for WSN area coverage[J].Journal of Network, 2010, 5 (6) :650-657.
[9]WANG Wei.A quantitative relation between the airport noise metric used in China and the airport noise impact[J].Engineering Acoustics, 2004, 23 (1) :8-11.
节点部署算法 第3篇
关键词：IPTV,anycast RP,BFP,multicast
1 IPTV组网架构
随着信息科技技术在广播、电影、电视行业的广泛应用,画面、声音、文字等的有效结合增加了广播电视节目的感染力。
与其他行业相同,计算机网络技术对传统的广播电视行业的发展起到了积极的促进作用。其与广播内容的有机整合,使用广播电视的性能更加完善,使电视传媒给观众们提供了更加丰富、多元的内容和按需所取的方式,满足了信息时候,大众用户的大部分需求。笔者对提供该能力的平台网络进行简单的探讨。
IPTV基于IP网络提供服务,因此需要考虑网络区域的独立性和稳定性。随着运营商集约化、业务的集中式部署思路。同时又要考虑到网络的复杂性,节约省集中设备资源的前提下,目前运营商的IPTV组网主要采用二级组播、独立组播域的方式部署。
在省集中层面,全省每个地市部署一套系统(以下简称区域中心)接收省中心通过组播下推的视频流,所有地址部署平台配置相同的RP和相同的组播IP地址。
地市区域中心以允当组播接收者的角色接收到省中心码流后,同时又以组播提供者的角色面向城域网用户提供组播服务。具体组网如图1所示:
2 二级组播部署的方式
IPTV的内容下推部署有三种方式类型。
方式一:省中心向地市区域中心推直播节目内容时,采用单播的方式,再由地市区域中心以组播的方式向城域网用户提供节目码流,此种方式主要是如果省内地市太多,就需要省中心提供多套面向地市提供服务的省中心节目码流服务器,同时由于又要考虑平台设备的冗余性,平台部署的设备服务器要新增加两倍的数量,但对于省到地节目流下推,可以通过控制单播路由的方式,做到省到地节目内容承载冗余链路的负载均衡。
方式二:省中心向地市区域中心推直播节目内容,采用组播的方式。地市区域中心向城域网用户推流时同样也将采用组播,由于省中心的组播流只在地市区域中心进行终结,同时又为了每个地市城域网内部只采用本区域内的RP,所以将采取在地市区域中心网络设备上配置两个RP地址,并采用RP加ACL的方式,使每个RP只对特定的组播地址进行注册。同时又降低了全省所有地市由于RPF所带来的组播故障风险。将PIM邻居终结在每个城域网A类与D类路由器的三层接口。具体部署方式如图2所示:
方式三:省中心一套组播流直接向全省所有用户提供直播节目流服务。此种组网虽然简化了地市区域中心节点的组播服务器的部署,但由于全省需要共用同一个RP地址,但各地市城域网设备的RPF检测环境的复杂度有所增加,同时故障时影响用户的范围面较大。
针对以上三种组网方式的权衡利弊,目前运营商大部分采用第二种二级组播下推直接节目流的方式。
3 设备和链路冗余
目前运营商重要平台都将采用主备冗余和负载均衡冗余的方式。
3.1 IPTV环境中的设备冗余
1)在IPTV环境中的省到地区域中心组播推流的RP设备方面,由于区域中心基本都是直接与服务器对接,为了解决端口密度和三层网络中多台主机在同一网段的通信问题,一般采用交换机部署,目前国内几家大的厂家都对虚拟化技术比较成熟。所以一般都采用两台三层交换机设备进行虚拟化来解决省中心和区域中心组播RP的设备冗余问题。
2)在IPTV环境中的区域中心到用户侧推流的RP设备方面,根据pim-sm组播的工作机制,RP只承担组播源和接收者的注册功能,只需要三层路由可达的路径满足RPF检测机制即可满足需求。所以一般采用城域网的SR或者CR路由器承当RP的工作。而且国内外主流厂家的路由器一般都支持anycast RP带来的冗余场景。具体部署方式如图3所示:
3.2 IPTV环境中的链路冗余
由于以太网技术的发展,目前运营商对于长途远距离的传输,一般采用波分,通过网络设备的GE端口进行流量承载。
由于各个地市城域网以通过A类与D类路由器运行BGP的方式,实现各地市之间的163公网之间的互联互通。但每个地市城域网的区域中心都需要向IPTV省中心获取组播码流。具体如图二,在这种场景下,由于在IPTV的组网中,各地市之间并不需要相互通,即只和省中心通信即可,为了减轻网络的复杂度,一般IPTV的省到地链路都采用静态路由进行精确控制目标流量的转发。
由于中间经过了传输波分设备,对于一条省到地的链路,如果省中心的设备板卡故障,地市区域中心设备端口肯定不能检测到,那么区域中心指向省中心的静态路由就不会消失,这样就将出现数据转发过程中被丢弃的情况。在这种环境下,静态路由的链路冗余环境一般只有两种,分别的VRRP和BFD路由链动。但笔者建议在组播环境中尽量不要使用VRRP。由于IPTV数据中心的网络规模一般比较大,网络结构比较复杂,网络应用比较多,收敛速度慢,再加上VRRP协议本身需要组播来维持,因此,使用VRRP协议的网络组播流量一般远大于同等规模的网络,这些组播流如果不加以控制,容易形成组播风暴,造成整个网络的瘫痪。网络内部也有一些依赖广播和组播而实现的功能,如NTP、ARP等。这些组播的存在,可能会在某一时刻造成局部的网络“塞车”,演变成滚雪球的效应,甚至成为形成组播风暴的诱因。对各类组播包的控制复杂,不易维护。因此,笔者不建议采用此种方式。笔者在实施部署时就碰到过组播风暴的情况,导致IPTV业务组播报文不能正常被转发接收。BFD双向链路转发检查技术,主要为了解决网络中链路中断时在动态和静态路由环境中加快路由收敛的问题。但此技术主要考虑的问题是异厂家设备之间的对接运行有一定的难度。所以在IPTV的组网环境中,对于平台的网络设备尽量采用同一厂家相同类型的网络设备。具体部署方式如图4所示:
4 结束语
节点部署算法 第4篇
关键词：煤矿监测,无线传感器网络,监测盲区,节点部署,覆盖模型,完全覆盖,可存盲区
0引言
工矿突发事故是危害煤矿人身和财产安全的主要因素之一。井下安全实时监测是预测和及时应对井下突发事故的有效手段。随着传感器、无线通信等技术的发展,无线传感器网络(Wireless Sensor Networks, WSN)因其传感器节点体积小、成本低、低功耗和自组织等特点而在工矿安全监测等领域得到了广泛应用[1]。WSN通过部署在相应监测区域的传感器节点实现温湿度、瓦斯体积分数等的实时监测和信息上传。节点部署是WSN正常工作的基础,关系到整个WSN监测信息的完整性、准确性和实时性[2]。目前对井下WSN的研究主要集中在节点定位、组网和低功耗问题上,对覆盖模型和节点部署的研究相对较少。本文在分析现有节点部署方案和覆盖模型及其弊端的基础上,提出一种新的可存盲区的井下WSN覆盖模型和节点部署方案,并比较了完全覆盖与可存盲区覆盖这2种情况下相同数量的节点的覆盖面积和相同监测面积所需的节点数量。
1常用的WSN节点部署方案
节点部署是指通过适当的方法在监测区域内布置WSN节点,以满足某种特定的监测需求。常用的WSN节点部署方案主要有计划部署和随机部署2类[3]。计划部署的节点是按事先计划进行布设的,一般情况下监测环境已知,网络相对固定,位置确定或移动较小[4]。计划部署的优点是可以根据需要部署和调整节点,在很多情况下可以减少节点数,简化通信协议,网络部署成本低且易于维护,适用于小区域监测。网格部署(将监测区按一定面积分成网格状,在网格交点上布设节点)就是一种常见的计划部署,如图1(a)所示[5]。计划部署的经典算法有Dhillon 等[6]提出的最大平均覆盖(MAX AVG COV) 和最大最小覆盖算法(MAX MIN COV),屈玉贵等[7]提出的整体局部覆盖算法,SanjayShkakottai 等[8]提出的基于方形网格的部署方法,汪学清[9]针对确定性的区域提出的菱形网格节点部署方案,Zou 等[10]提出的基于Miss 迭代部署策略等。上述方法各有优缺点。随机部署方案中节点随机部署在监测区域,一般节点的密度比较大且具有随机性,对于通信协议的设计和节点定位有很大挑战,一般适用于较大区域和人员难以到达的区域监测。模拟随机部署如图1(b)所示。参考文献[11]介绍了简单扩散、固定分布和R随机分布3种随机部署方法。
图1 常用的WSN节点部署方案
2覆盖理论与经典覆盖模型
WSN覆盖问题是WSN的主要研究内容之一。研究覆盖的目的是通过合理地部署WSN节点,在保证一定的网络服务质量下,达到最大的网络覆盖范围。通过研究WSN覆盖可了解被监测区域的网络覆盖情况,掌控监测区域是否存在监测和通信盲区,从而为更好地部署节点提供依据[12]。网络覆盖性的指标主要有覆盖程度、覆盖时间和覆盖盲区。本文主要讨论覆盖盲区。对于给定的监测区域和传感器节点集合,若该区域内的任意一点都被k个节点覆盖,则该监测区域无覆盖盲区,也称对该区域实现了k重完全覆盖。当k=1时,称为单重完全覆盖[13]。
常见的WSN覆盖模型有区域覆盖模型、点覆盖模型和栅栏覆盖模型。区域覆盖是最为常见的,它考虑的是在WSN能够覆盖的目标区域中的每一点都至少在1个传感器节点的探测范围内,图2(a)为WSN对给定的长方形监测区域进行覆盖的示例;点覆盖关注的是覆盖监测区域的一些点,它只需对监测区域内有限个离散点进行监测,同时确定覆盖这些点所需的最少节点数以及相应节点的位置,图2(b)显示的是对监测区域中的4个离散点进行覆盖;栅栏覆盖主要用于监测移动目标,目的是使监测目标通过监测区域时被监测到的概率最大,图2(c)为栅栏覆盖的示例[12]。
3可存盲区的井下WSN节点部署方案
完全覆盖在大多数应用中不仅难以实现,而且系统成本高,节点冗余严重,影响整个系统的服务质量。对于不同的监测对象,节点的部署方案和覆盖会有所不同。但对于大多数应用,可以用小区域中某一个或几个点的监测信息代替整个小区域的情况。也就是说,在很多情况下,监测区域并不需要完全覆盖,允许存在监测盲区,最终的整体监测结果几乎不受影响,对于一些重点的需要实时监测的对象才考虑完全覆盖。比如井下温湿度、一氧化碳体积分数和瓦斯体积分数等参量的监测,在一定区域范围内的温湿度、一氧化碳体积分数和瓦斯体积分数无明显差异,在该区域内只需采集区域边界或区域内的1个点即可估算该区域的环境状况,而无需在该区域布设多个监测节点。结合前文提到的区域覆盖,提出一种新的可存盲区的井下WSN覆盖模型和节点部署方案,根据监测对象的具体情况设定盲区,然后按需要进行节点部署以实现监测。
传感器节点间的感应范围是可以交错的,当采用完全覆盖模型(无覆盖盲区)时,根据参考文献[12]提到的节点协作理论,在目标监控区域的半径远远大于覆盖半径R的前提下, 为了实现完全覆盖,节点的最优部署方案是用任意3点构成一个等边三角形, 并且三角形的边长等于undefined,如图3所示;在图3中,undefined表示欧式距离),当undefined时,图3所示的完全覆盖将出现监测盲区,如图4所示。对于不同的应用对象,盲区的形状和大小会有所不同,可以是圆形、方形,也可以是以某一点为中心的立体空间。图5给出了以规则的方形和圆形为监测盲区的示意图。
4可存盲区的WSN覆盖模型在井下的应用分析
本文以目前正在研究的课题项目为基础,给出可存盲区的WSN节点部署方案在井下监测中的具体应用,并对完全覆盖和可存盲区覆盖的节点部署的覆盖面积和节点个数进行比较。应用中相关条件如下:
(1) 井下监测区域面积为A,每3个节点组成的覆盖区域面积为单位覆盖面积。
(2) 盲区为边长为a的正方形区域,a称为盲区度。
(3) 节点的有效通信距离为R,节点覆盖范围为半径为R的圆域。
(4) 节点按最大覆盖域进行布设,即节点覆盖域刚好与盲区边界相切,如图5(a)所示。
4.1 单位覆盖面积比较
参考文献[14]中的完全覆盖模型采用最常用的六边形蜂窝式覆盖模型,此时3个节点的覆盖面积undefined,如图6所示。将边长为a的正方形域内的环境状况视为相同,按最大盲区部署节点,如图7所示。
当按最大监测盲区覆盖时,undefined。由于‖P1P2‖=‖P0P2‖<‖P1P0‖,根据六边形蜂窝式覆盖模型,取较小边组成六边形,此时覆盖面积undefined可存监测盲区和无监测盲区的覆盖面积之差undefined即可存盲区的单位覆盖面积大于完全覆盖的单位覆盖面积。由undefined得出undefined,在布设节点时可以根据节点的通信半径和节点的距离确定a的值.
4.2 相同覆盖面积下2种覆盖模型的节点数量
假设N1为采用完全覆盖时监测区域中部署的节点个数,N2为采用可存盲区时监测区域中部署的节点个数。3个节点可以组成一个单位覆盖域,经计算得监测区域节点个数N(≥3个)与单位覆盖域个数M的关系为M=N-2。对于面积为A的监测区域,当使用完全覆盖时,A=(N1-2)S1,此时可得到N1=A/S1+2,同理得N2=A/S2+2。将S1和S2分别代入上式得undefined很显然N2
5结语
节点部署算法 第5篇
水果蔬菜经过一段时间的贮藏后, 品质均会不同程度的下降, 如水分流失、苹果出现炭疽病等。为了充分满足人们对果蔬的日常需求, 需要对果蔬进行长期且高质量的贮藏, 采用气调保鲜冷藏是目前最为有效的途径。气调冷藏技术是目前最先进的果蔬冷藏技术, 它通过调节贮藏环境的温湿度和气体组成, 为保鲜食品创造一个最佳环境, 降低果蔬贮藏期间的损耗, 获得较好贮藏效果。如果能集中建立大型的气调冷藏库, 将散户种植的果蔬产品进行集中贮藏, 不但能保证果蔬的品质, 提供日常供给, 而且产品售价相对较高, 有利于增加农户收入。
无线传感器网络是一种低成本、高可靠性的信息获取技术, 它是利用传感器节点, 实时采集监测对象的各种信息, 使用户随时随地获得真实可靠的数据。在气调冷藏库中采用无线传感器网络, 可以准确地收集冷藏库内温度、湿度和O2、CO2浓度等环境信息;对接收到的数据进行处理, 可以实现对气调库内环境的自动化控制, 使果蔬贮藏环境接近理想状态。
应用无线传感器网络的第一步是进行节点部署, 它是传感器网络监测系统实现的基础, 合理的部署方案能够保证信息获取的准确性和完整性, 并减小时延。进行节点部署应考虑节点的覆盖度、连通度、部署成本和部署质量等因素, 结合气调库内确定的部署环境, 即库内密封, 大部分空间被贮藏物品填满、空气不流通, 提出面向气调冷藏库信息采集的节点部署方案。为了避免在室内环境下库内物品对节点之间的数据传输产生阻碍, 满足感知区域的完全覆盖和节点间通信链路的连通, 可以采用如下部署方案。
1 随机部署
随机部署即将传感器节点随机地放置在气调冷藏库内。随机部署简单方便, 但可能不符合实际情况, 而且很难找到一个合适的随机部署策略和算法来量化所有相关的度量, 如网络的覆盖率、连通率和网络寿命等, 一般很少采用。而确定性部署可以去除冗余节点, 精简网络拓扑结构, 并降低部署成本。同时, 在确定性部署中, 网络设计可以更有针对性, 如针对不同的精度要求设置合适的节点密度和节点结构分布, 提高服务质量, 而且有多种确定性的算法可以采用。根据气调库的实际情况进行节点部署才能更好地发挥传感器网络本身的优势。
2 确定性部署
确定性部署指节点在气调冷藏库内按照一定规则放置。确定性部署是比较合理的部署方案, 根据气调冷藏库的结构不同, 部署方式也有所不同。除了星形、树形和网络三种标准的网络拓扑结构之外, 还可以根据气调库不同的设计特点, 进行不同条件下信息采集的节点部署策略研究, 以期实现网络的最佳覆盖率和最长生存周期。
2.1 节点的线性部署
节点的线性部署即所有的节点近似分布在一条直线上。这是最简单的人工部署方式, 适合在面积较小或矩形的气调库中进行数据采集。节点采集的数据通过无线通信传输给基站时, 离基站距离较近时, 消耗的能量较少, 离基站的距离越远, 消耗的能量越多。为了使各节点的能耗保持平衡, 有效延长无线传感器网络的寿命, 同时考虑系统的成本, 当气调库面积较小时, 采用均匀部署的方式即可, 如图一所示, 在直线上每隔合适的距离放置一个节点, 每个节点监测到的数据各自传输到基站, 进行进一步的数据处理。当需要节点数目较多时, 为了进一步降低成本, 大量节点选择的是只具有单向通信功能的终端节点, 它们监测的数据只能传输给路由节点, 然后每隔若干个终端节点选取一个路由节点, 这些节点除了用于监测数据之外, 还要完成终端节点数据的中继转发, 将数据传输到基站, 如图二所示。一般线性部署的节点路径比较单一, 时延较少, 部署方便。
2.2 节点的平面部署
节点的平面部署即所有的节点近似分布在一个平面上, 适用于面积较大的气调冷藏库。这一结构比较复杂, 可采用虚拟的三角形、四边形或六边形等顶点方式, 也可以依托虚拟的方形、菱形或六边形等二维网络格点, 每个网格用其中心的网格点表示, 在气调库的内部结构和边界已知的情况下, 根据测量精度的要求, 需要求解合适的网格单元边长。这时将节点部署在虚拟的顶点 (如图三所示) 或者中心网格点, 或者节点能够覆盖所有的顶点或网格点就可以, 尽可能保证传感器网络的覆盖性和连通性。
首先考虑系统的成本, 多数节点选取只能进行单向通信的终端节点, 大体上采取均匀分布的方式, 它们只负责监测, 监测结果传输给路由节点进行转发。同时考虑网络的有效寿命, 在平面空间内根据节点的有效覆盖距离和有效数据传输距离部署路由节点, 它们除了监测之外将很大一部分能量消耗在数据的中继转发上, 在远离基站的地方, 传输数据需要的能耗要高, 其部署密度稍大一些, 在离基站较近的地方, 传输消耗的能量稍小, 其部署密度也可以稍小一些。节点的平面部署传输路径较多, 会产生冗余数据, 需要进一步对数据进行处理。
2.3 节点的立体空间部署
节点的立体空间部署即所有的节点分布在整个立体空间内, 结构复杂, 适合应用在超大规模的气调冷藏库中。近年来, 节点的三维立体优化部署成为行业研究热点, 围绕着三维空间内的节点部署问题和规划, 提出了一系列有效构建三维网络拓扑结构的规则, 开发出多个针对三维部署的算法。如王军等人将监测区域分为多个以传感器节点的传感半径为外接球直径的多面体, 然后将传感器节点放置在多面体的顶点或是外接球重叠区域中, 最后理论分析出同构节点分布的最佳位置[1]。
比较简单的立体空间部署是将空间分为两层 (如图四所示) 或多层, 每层都可看作是平面网络, 将三维空间的节点部署问题转化为二维空间部署来实现, 不同层之间的信号干扰忽略不计。也可以使用虚拟的三维网格将整个立体空间进行划分, 如图五所示, 相邻网格点间的距离由期望的测量精度决定, 选择在每个网格点配置传感器节点或能覆盖所有的网格点的方式布置节点, 实现对气调库内空间的全连通和全覆盖。或者将气调冷藏库的内部空间映射为水平和垂直两个相互垂直的二维平面, 分别分析其节点部署的优化方案。节点的立体空间部署传输路径非常多, 同时产生大量的冗余数据, 数据处理非常复杂。
2.4 节点的混合式部署
节点的混合部署即所有节点包含线性、平面和立体空间网络结构, 或者根据气调库的结构特点和需要贮存的果蔬对贮藏环境的要求, 选择线性、平面、立体、星形或树形网络结构的任意组合, 构成结构更加复杂的混合型节点部署模式。
2.5 节点的边缘部署
节点的边缘部署即在固定空间内或者有固定边缘的室内或有限区域内, 根据被监测区域的形状和尺寸, 节点只部署在被监控区域的边缘或者指定位置, 形成边缘部署, 如猪舍环境监测系统将传感器节点部署在猪舍的四周或是屋顶。边缘部署的节点除了进行监测获得监测数据之外, 还可以实现节点的定位及跟踪, 如Chun-Han Lin等人研究了用边缘部署来跟踪泥石流前进路径, 先把可移动节点投入泥石流中, 然后在泥石流两岸部署位置固定的节点, 当随泥石流移动的节点发生移动时, 与固定节点间的距离发生变化, 获得相应的监测数据, 通过合适的算法就可以估计出泥石流的流速、流量等。
气调冷藏库是一个密闭的室内结构, 大多数有规则的内部空间都可以采用边缘部署。所有节点全部部署在气调库的内部边缘, 而冷藏库内一般填满了果蔬等物品, 受到障碍物的干扰, 全覆盖和全连通的实现比较困难。这个时候只要实现实际情况下的覆盖率达到一定程度即可, 这取决于要达到的监测精度要求。边缘部署的成本相对来说较低, 可采用的确定的算法也较多, 数据传输的路径较简单, 是一种比较简单的部署模式。
3 动态部署
气调冷藏库中部署的节点位置固定, 一旦放置后就不再改动, 属于静态部署。但传感器节点可使用的能量有限, 一旦能量耗尽或发生故障节点失效时节点就会退出网络, 剩余的节点会自动组网, 传感器网络的拓扑结构随之发生变化。为了保证传感器网络的覆盖率和联通率, 需要对网络重新进行部署, 为了适应传感器网络的这种变化, 需要进行传感器网络的动态部署。采用什么样的规则进行节点的重新部署是我们应该考虑的问题。
一种方式是当有节点因故退出网络时, 及时补充新的节点, 这种方式基于节点的时间同步, 尽量保证节点的及时更新, 整个网络的结构基本没有变化。另一种方式是当传感器节点由于各种原因停止工作时, 系统会识别来自其他监测区域的节点进行替代, 直接重新自动组网, 这会导致网络的拓扑结构发生变化, 在进行气调冷藏库的节点部署时要考虑到能够适应这种变化。
将无线传感器网络应用于果蔬产品的气调冷藏中, 可以有效提高产品的贮藏质量, 而且无线传感器网络的耗能低、成本少等优势也为提高农户收入提供了可靠的途径。根据气调冷藏库的具体结构确定合适的节点部署方案, 能够对气调库内温度、湿度和O2、CO2浓度等贮藏环境相关信息进行更准确的测量, 从而更精确的控制贮藏环境, 使果蔬的贮藏时间更长、贮藏质量更高, 在提高果蔬储运质量的同时满足人们日常生活对果蔬的需求。
参考文献
[1]王军, 孙小玲, 程勇.三维无线传感器网络K重覆盖机制研究[J].电子技术应用, 2015, 41 (11) :144-148.
[2]王学军.一种改进的无线传感器网络节点部署方案[J].计算机工程, 2012, 38 (19) :82-84.
[3]陈龙, 刘莉平, 赵明, 等.无线传感器网络分簇和节点休眠综合性策略研究[J].计算机与现代化, 2015, (04) :1-5.
[4]孙玉文, 沈明霞, 周良, 等.农田无线传感器网络的节点部署仿真与实现[J].农业工程学报, 2010, 26 (08) :211-215.
基于节点编码的最小生成树算法 第6篇
关键词：遗传算法,最小生成树,节点编码,Prufer数
1 概述
树是图论中的一个重要概念, 也是图论中结构简单, 用途广泛的一种连通图。在许多工程问题中, 如通讯网络设计、电力、煤气和排水管道系统设计等, 通常都可以转化为求最小生成树问题。
对于一个给定的带权无向连通图G来说, 应用图论中的传统算法, 如:Kruskal算法、prim算法、Sollin算法、Dijkstra算法等求解最小生成树。但采用这类算法一般只能得到唯一的一棵最小生成树, 而在实际应用中, 不同形式的最小生成树代表不同的设计方案, 有时权值次小的生成树, 也可能是实际问题的一个较好的设计方案。如果仅选其中一个, 可能会丢失或忽略更优的方案。因此, 在实际应用中希望能够同时获得若干个权最小或次小的生成树作为待选方案。
遗传算法求最小树的常见编码方法有边编码、节点编码。采用二进制的边编码方式表示最小生成树, 其生成树的概率较低。因此, 提出基于节点整数编码来求最小生成树。
2 基于节点编码的遗传算法
图论计算中的一个经典定理是Cayley定理, 即在一个有n个顶点的完全图中, 有nn-2个不同的树。这些树和n-2个数字的所有排列的集合是一一对应关系。这表明可以仅用n-2个数字的排列来唯一地表达一棵树, 其中每个数字都是1到n之间的整数。这个排列通常称为Prufer数。基于这种现象, 可以很容易地构造如下节点编码方法 (得到一个Prufer数) :
2.1 令节点i是标定树T上的标号最小的叶子节点。
2.2 令唯一与i相连的节点j作为编码的第一个数字。编码顺序从左到右。
2.3 删除节点i及i到j的边, 于是得到一棵n-1个节点的树。重复上述运算, 直到只剩下一条边。于是得到一个Prufer数或一个n-2个1和n之间的数字的排列。
3 算法设计
3.1 编码设计
设某一无向图中共有N个顶点、N (N-1) /2条边, 对图中的节点进行编号。以图中的节点编号为编码变量, 各个编码变量的取值范围是1~N之间的整数, 则以N-2个整数为Prufer数可以唯一表示一棵树。N-2个Prufer数是就是树中的枝节点, 其大小在1~N之间;而不在Prufer数中的整数是树的叶子节点。例如, 图1 (a) 所示的无向图最多可以有7!条边, 图1 (b) 是该图的一个生成树, 由7条边组成。生成该树的Prufer数是{5 2 5 2 6 2}。
3.2 遗传算子的设计
3.2.1 交叉算子Pc
本文采用单点交叉方式, 首先将群体中的M个个体以随机的方式组成[M/2]对配对个体组, 然后在每对个体组中随机设置一个交叉点, 在该点相互交换两个配对个体的基因值。
单点交叉的示意图如下:
交叉算子的的设计和实现与所研究的问题密切相关, 一般要求它既不要太多地破坏个体编码串中表示优良性状的优良模式, 又要能够有效地产出出一些较好的新个体模式。
3.2.2 变异算子Pm
本文采用基本位变异操作, 具体思路是:对个体编码串中以变异概率Pm随机指定的某一位或某几位基因座上的基因值作变异运算。具体执行过程是:
a.对个体的每一个基因座, 依变异概率Pm指定其为变异点。
b.对每一个指定的变异点, 对其基因值用[1, N]范围内的一个随机数去替换。
基本位变异的示意图如下所示:
3.3 算法的相关参数及流程图
最小生成树的算法流程图如下:
4 实例应用
如下图所示的一个网络图, 图中连线上的数据表示各边的权值。应用单亲遗传算法求该网络图的最小值。
解:该网络图的权矩阵如下:
运行可知, 当Pc=0.6, Pt=0.1, Pm=0.05;Popsize=100;Maxgen=20时, 可得最小树长87。此时Prufer=[1 8 6 7 1 7]。对应的树枝是:2-1, 3-8, 4-6, 5-7, 6-1, 1-7, 7-8。
5 结论
采用基于节点编码的遗传算法求最小生成树可用于不同类型的最小树问题研究, 能够在较短的时间内以较高的概率获得一批最小树或次最小树, 为进行实际工程的方案评价和决策提供更多的选择依据。
参考文献
[1]周明, 孙树栋.遗传算法原理及应用[M].北京:国防工业出版社, 1998, 12.
节点部署算法 第7篇
定位技术是WSN的核心技术之一。WSN的定位算法,可以根据实际应用中所需定位机制的不同,分成基于测距算法( Range-based) 和无需测距算法( Range-free) 两大类。其中,基于测距的定位机制需要利用未知节点至信标点之间的距离或角度信息,采用三角测量法、三边测量法或最大似然估计法,计算未知节点位置。而无需测距的定位机制则不需要预先知道未知节点至信标点之间的距离和角度信息,只需要通过网络中节点间邻近关系或节点的连通性等信息实现节点定位。如质心、APIT( Approximate Point-in -triangulation Test) 定位、DV -Hop ( Distance Vector-Hop) 定位、Amorphous和MSD-MAP。由于无线传感器网络硬件设备的限制,无需测距的定位算法得到广大学者的关注。
DV-Hop算法的“无需测距定位法”是研究人员关注较多的算法之一。学者们针对其定位精度较低的缺点,提出了许多改进方法,但尚未达到理想效果。文献[1]采用的算法,虽然具有较高的定位精度,但通信开销和计算量都较大。如果将RSSI引入DV-Hop算法,虽然可以提高定位精度,但增加了节点的硬件开销。文献[2]采用遗传算法和模拟退火算法对DV-Hop算法进行改进,虽然降低了定位误差,但是算法复杂,能源消耗多。文献[3]提出采用粒子群优化的方法,但是该改进算法需要测量信号的方向,从而需要添加相应硬件设备,增加了节点的硬件成本。文献[4]先获得网络中信标节点之间的平均跳距,再计算每个信标节点的平均跳距,进而获得这两个平均跳距之间的误差,从而修正全网的平均跳距。文献[5]针对DV-Hop定位算法在不规则网络中的定位精度进行改进,考虑了未知节点与信标节点之间的路径可能与信标节点间的路径重合这一特性,对平均跳距进行修正,在一定程度上提高了定位精度,但是由于考虑的因素较少,所以定位精度提高的不是太明显。
本文在对DV-Hop定位算法进行研究分析的基础上,通过总结大量改进算法的优缺点之后,提出了基于邻居节点相似度的DV-Hop改进算法。通过仿真分析,结果表明: 算法可在无需增加节点硬件以及通信开销的基础上,提高节点的定位精度。
1 DV-Hop定位算法
1. 1 DV-Hop算法描述
DV-Hop算法的核心思想为将未知节点与信标节点之间的距离用信标节点间平均跳距和未知节点与信标节点之间的最小跳数的乘积来表示。然后通过三边测量法或者最大似然估计法求出未知节点的坐标。定位的过程主要分为以下3 个阶段[6]:
1) 测量未知节点与信标节点之间的最少跳数。采用经典的距离交换协议,使监测区域中所有未知节点获取与信标节点间的跳数信息。
2) 计算未知节点到信标节点的估计距离。每个信标节点获得自身到其他信标节点的跳数以及其他信标节点的坐标后,计算信标节点i平均每跳的距离,称为平均跳距di,计算公式为
式中: xi,yi为信标节点i的坐标; hij为信标节点i和j之间的最少跳数。
然后,信标节点将计算获得的平均跳距di以广播的形式通知网络中的其他节点。
3) 估计未知节点位置。未知节点利用到各个信标节点之间的最少跳数和平均跳距,求自身的估计坐标。假设( x ,y ) 是未知节点N的坐标,( xi,yi) 是第i个信标节点的坐标。未知节点N与信标节点i之间的估计距离为di,并且将未知节点N和网络中所有信标节点的估计距离表达式整合成方程组,则有
将上述n个二元二次方程,转化为AX = b的形式。其中
方程AX = b用标准最小二乘法求解得位置节点坐标为
1. 2 DV - Hop算法的不足
1) DV - Hop算法中,平均跳距是通过信标节点之间的最小跳数和信标节点之间的距离获得。实际中,信标节点之间的距离为直线距离,最小跳数的每跳不一定在同一直线上,且每跳的跳距是不同的。如图1 所示。DV - Hop算法将信标节点之间的距离和最小跳数之商作为平均跳距。这一平均跳距会由于网络中的节点稀疏程度和连通度的不同而出现不同程度的误差。
2) 用信标节点间的平均跳距与未知节点和信标节点之间的最小跳数的乘积,代替未知节点与信标节点之间的实际距离。其中未知节点和信标节点之间的最小跳数的通信路径并非呈直线分布,且节点间跳距不同。所以通过此步骤获得距离也会引入误差。
2 DV - Hop改进定位算法
2. 1 相关定义
1) 邻居节点: 在无线传感器网络中,节点都有一定的通信半径,处于此范围之内的节点称为该节点的邻居节点。
2) 邻居节点相似度: 无线传感器网络中的节点可以通过信息交换,获取自身的邻居节点ID号列表,并且和其他节点的邻居节点列表作比较,节点间的邻居节点列表中的节点ID号相同的数目越大,邻居节点的相似度越大,其值为
式中: δ 可以改变节点间邻居列表中ID号相同的节点数目对邻居节点相似度的影响; Numcom指的是节点间邻居列表中ID号相同的节点数目; Numi和Numj分别指未知节点i和j的邻居节点数目。
2. 2 改进算法要点
2. 2. 1 单跳节点处理
无线传感器网络中可以通过单跳直接和信标节点通信的未知节点。在DV - Hop中全部采用网络中邻近信标节点的平均跳距作为距离,实际中,网络中较多的未知节点可以和信标节点直接通信,如图2 所示。未知节点和信标节点的距离也不尽相同。使用平均跳距作为这些节点与信标节点的距离,从而导致信标节点的邻居节点区分度单一,而引入较大的误差。所以,本论文在此处引入修正方法。
本文提出邻居节点相似度的概念,通过网络信息交换获取节点的邻居节点列表后,根据式( 7) 可以求出节点i与节点j的邻居节点相似度 εij。
对单跳节点进行修正后的距离为
2. 2. 2 多跳节点处理
余弦定理: 已知三角形两边之长及其夹角,可以求得第三边的长度。
根据余弦定理,在节点ABC组成的三角形中,如图3所示。本文假设知道AB和BC的长度,以及∠ABC的度数 θ 。就可以根据余弦定理,求出AC的长度,这样就将节点A到节点C之间的折线通信路径转化为求直线AC的长,表达式为
未知节点间单跳跳距的修正方法,采用单跳节点处理方式,根据未知节点ABC的邻居节点列表和式( 7) 、式( 8) 求出节点A到节点B和节点B到节点C的距离。
节点间的距离越近则邻居节点的相似度越高,而节点距离越远,邻居节点的相似度越低。所以,本文将通过节点间邻居节点的相似度来调整夹角θ的度数。如图4所示,节点i和节点j恰好处于彼此的通信半径之外时,节点k通过多跳模式传递信息,当节点k距离节点i和节点j距离最远时,此时∠ikj的度数最小,且近似等于π/3。
如图5 所示,节点i,j恰好位于各自通信半径边缘处,且节点k位于此交集处。此时,节点i,k,j组成一条直线,通信夹角最大,近似为 π。节点i,j的距离最远。
则节点间的通信夹角取值范围是[π/3,π]。根据邻居节点的相似度,可以求得网络通信链路中的通信夹角θ为
式中: εij通过式( 7) 获得; γ 为邻居节点相似度所占权重值,改变其大小可以改变 γ 在通信夹角中的影响程度,γ值大小根据具体网络连通情况和节点的疏密程度而定。
无线传感器网络中的任意三个通信节点ABC,如图3所示。通过式( 8) 获得AB和BC的长度,再通过式( 10) 获取AB和BC的夹角。根据余弦定理,带入式( 9) ,方可将实际中的折线通信距离转化为求直线距离,减少了由于折线通信带来的误差。
2. 3 改进算法实现
1) 计算全网节点间的最小跳数
信标节点向邻居节点以广播的形式发送一个信标,包括位置信息字段和邻居节点列表字段。其中位置信息字段包括自身坐标、ID号和跳数值,跳数值初始化为0。邻居节点列表字段包括通信半径内的所有节点的ID和邻居节点的数目,初始化为NULL。
节点收到其他节点发来的信息后,位置信息字段更新坐标和ID号,同时跳数值加1; 邻居节点列表字段将接收到的位置信息中的ID号取出,存入邻居节点列表中,邻居节点数目加1,并继续向其他邻居节点广播,通过这种泛洪方式向整个网络传播数据。若节点收到来自同一个节点的多个信息,则比较其跳数值,只保留最小跳数值的信息,这样就保证了所得到的跳数值是到网络中所有节点的最短路径。
经过此阶段,网络中的所有节点都获得各个信标节点的坐标,以及邻近节点的ID号和个数。以及它到各节点的最小跳数。
2) 计算未知节点和信标节点的实际跳距
每个信标节点根据第一步中获取的到其他信标节点的位置信息和跳数,利用式( 1) 估计平均跳距di。
信标节点的邻居节点中的未知节点根据式( 7) 求出未知节点和信标节点的相似度 εi。并且将 εi带入到式( 8) 中修正di为d'i。
通过多跳间接和信标节点通信未知节点,距离修正处理如下:
对于和信标节点通信的节点采用两跳通信的未知节点。首先,采用式( 7) 和式( 8) 修正未知节点i与信标节点的前驱节点j之间的单跳距离d'ij,然后结合信标节点的前驱节点j和信标节点B( 即信标节点的邻居节点) 之间的修正距离d'j B。再根据式( 10) 求出未知节点i和信标节点B通过节点j通信的夹角 θi B,带入到式( 9) 中得到两跳通信修正距离d'i B。表达式为
对于通过三跳或三跳以上和信标节点通信的节点采用和两跳距离修正同样的方法,先求出两跳路径后,再相互结合,直到获取源节点到信标节点距离。通过此修正方法,使全网中的未知节点获得到各个信标节点的修正距离。
3) 计算未知节点坐标
将2) 获取的未知节点到各信标节点的修正距离,代入到式( 2) 中,使用最小二乘法,求得未知节点的坐标。
3 仿真结果极其分析
检测区的范围是100 m × 100 m的正方形区域,随机播撒100 个节点。网络中节点的通信半径为R 。δ 和 γ 根据监测区域节点分布的疏密程度和连通度分别设置为0. 9和1。未知节点坐标与实际坐标之间的相对定位误差表示为
式中: erri代表每个未知节点的误差; UN代表未知节点的个数。
通过对DV - Hop、参考文献[5]算法、参考文献[7]算法、本文算法进行仿真,并对实验结果进行比较。从而证明了本文算法的有效性与可行性,图6 ~ 图9 给出了网络中的节点通信半径不同时,随着网络中信标节点比例变化,三种算法的定位误差比较结果。
从图中可以看出在相同的通信半径下,本文改进算法和文献[5]、文献[7]的算法的定位误差距均低于DV - Hop定位算法。通信半径为30 m时,本文的改进算法比DV - Hop定位算法在相对定位误差上降低了33. 34% ~ 35. 35% 。比文献[5]、文献[7]定位算法降低了10. 06% ~ 21. 41% 。且各个算法的定位误差随着信标节点比例的增加,定位误差都不断减小,且趋于平稳。当网络中的信标节点数目一定时,随着节点的通信半径减小,节点的定位误差也随之减小。如当信标节点的比例为10% ,节点的通信半径分别为30 m时,DV - Hop定位算法获得的未知节点的相对定位误差为92. 22%[5],文献[5]定位算法获得结果为76. 26% ,文献[7]定位算法获得结果为78. 14% ,本文改进定位算法结果为58. 48% ; 在不同的通信半经中,信标节点比例小于10% 时,改进算法较DV - Hop定位算法的定位误差降低了约32% ~ 35% ,且与文献[5]和文献[7]的定位算法获得的定位误差降低了约18% ~20% 。
算法复杂度分析: 文献[1]将RSSI引入DV - Hop算法,在复杂度上增加了节点关于RSSI强度值计算的相关部分,并且算法需要额外的硬件成本。而文献[2]和文献[3]虽然采用了经典的遗传算法、模拟退火算法和粒子群优化的方法对DV - Hop算法进行改进,这样极大地增加了算法的复杂度,同时能源消耗多。同时文献[3]还需要添加硬件设备,增加了硬件成本。文献[5]主要针对未知节点与信标节点之间的路径可能与信标节点间的路径重合这一点进行修正,一定程度上提高定位精度,算法复杂度较低,但是由于考虑的因素较少,所以定位精度提高的不是太明显。本文算法通过邻居节点列表的比较,获取邻居节点相似度,并在此基础上对节点的跳距进行修正,在此处略加大算法复杂度。但是节点定位精度却得到较大的提高。
综上所述,本文的改进定位算法,无论是相当于传统的DV - Hop定位算法还是文献[5]的定位算法,均在节点的相对定位误差上都有了较大幅度的降低。
4 结论
本文针对DV - Hop定位算法在单跳通信中,处理信标节点的邻居节点距离没有区分度,统一采用平均跳数与单跳之积的形式表示,以及多跳通信中该算法没有考虑折线通信,依然采用同样的方式处理,从而导致该算法的定位精度较低的情况。同时,这一点也是文献[5]没有考虑到的。本文提出了邻居节点相似度的概念,并应用此概念分别对单跳节点( 邻居节点) 的距离进行修正,克服了DV - Hop定位算法在处理单跳节点时,采用同样的距离表示距离信标节点的距离; 在多跳通信中,结合余弦定理将DV - Hop和文献[5]中的折线距离代替实际中的直线距离,转化为求直线距离的运算,同时修正了多跳通信中每一跳的距离。使得本算法在定位过程中增加了节点跳距区分度,克服了DV - Hop定位算法和文献[5]定位算法较单一的计算。由于本算法中的邻居节点相似度综合考虑了网络的连通度和节点的疏密程度等因素,且可根据实际情况作出相应的调整。所以本算法的实际应用价值较高且具有较好的鲁棒性。