传感器节点部署(精选7篇)
传感器节点部署 第1篇
关键词:煤矿监测,无线传感器网络,监测盲区,节点部署,覆盖模型,完全覆盖,可存盲区
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结语
传感器节点部署 第2篇
无线传感器网络, 是由部署在观测环境附近的大量微型低功耗的传感器节点组成的多跳自组织网络系统, 目的是实时检测、感知和采集各种对象的信息, WSN广泛应用在军事国防、环境监测、危险区域等监测和办公建筑的环境控制等领域。网络覆盖是其基本问题之一, 直接影响着监测结果的准确性和全面性。
按照无线传感网节点不同配置方式, 可以将WSN的覆盖问题分为确定性覆盖、随机覆盖。文献[1]设计了一种判断传感器节点周边覆盖的算法, 用于计算确定的区域是否能被K个传感器节点覆盖.李明等[2]针对异构传感器网络节点的高密度部署和监测目标非均匀分布的情况, 提出了一种基于模拟退火算法的成本最优化部署方法。目前的覆盖技术研究多数集中在区域覆盖的随机部署、穿越覆盖以及目标覆盖的随机部署等方面;而针对有约束条件的区域覆盖问题却很少涉及。在实际应用中, 有些区域或某些部分很重要或者不能部署传感器, 如火山测中的火山口附近, 战场上的指挥中心等, 为获得较高的可信度, 防止节点失效和信息传输失败以及由于周围噪音的干扰导致信息的不准确, 形成中心多重覆盖周围单覆盖。通信中心不能在其内部布置有干扰的传感器, 仅在其周围一定范围内布置, 从而形成环形的监测区。有约束条件的遗传覆盖机制, 就是针对以上问题提出。
2. 系统模型和问题表述
2.1 系统模型
本文研究的无线传感网系统模型基于如下假设:
(1) 节点的感知模型采用二元感知0/1模型, 即:节点以概率1监测以其为中心、以r为半径的圆形监测区域 (不包括圆上的点) (2) 无线传感器节点为同构节点, 探测区域所有传感器节点都具有相同的发射功率, 即所有节点的探测半径r均相等。 (3) 探测区域所有传感器节点都在同一个平面内。 (4) 假设节点通信半径Rc为传感半径Rs的两倍 (即Rc≥2Rs) 。 (5) 用感知半径为r的圆, 以它的内接正六边形对区域进行覆盖, 可得到重复覆盖最少的无漏洞覆盖[3]。文献[3]中研究表明, 对于部署在监测区域内部的节点, 每一个节点的感知圆域内接正六边形面积S2与感知圆域面积S2之比为82.7%, 也就是相邻两个圆的公共面积为5.77%。本文中区域覆盖采用远的内接正六边形覆盖, 即约束了相邻两个圆的公共面积不小于大圆面积的5%。由于单独点和分散点都可以被一个圆覆盖, 所以本文将重点监测点 (不覆盖点) 归纳为圆区域问题。本文主要以总监测区域 (正方形) 中一个椭圆形区域不覆盖传感器为例进行研究。
2.2 问题表述
本文中问题可归结为一个最优化问题, 即:目标:对目标区域覆盖所用的圆个数最少
约束1:相邻两个圆的公共面积不小于大圆面积的5%
约束2:地面被圆完全覆盖
约束3:节点不能存在于椭圆形中
设G为待覆盖区域 (其面积为10001000) , 椭圆形所覆盖的区域为H, di为处于每个圆的圆心或相邻圆公共部分中心的节点, m为节点个数, g为平面上任一点, B{b1, b2, , bn}为平面上圆的集合, k表示相邻两个圆的公共圆的公共面积占一个圆面积比例的下限, 本文中k=0.05, n为将区域A全部覆盖所需最少圆的个数, Sc表示有效面积, r表示圆的半径 (本文传感器的探测半径为100) , 则本问题表述如下:
(xi, yi) 为圆bi的圆心坐标, 1xi1000, 1yi1000, 则在此范围内, 存在集合{ (x1, y1) , (x2, y2) , (xm, ym) }使得所有圆之和最小。
3. 基于遗传算法的确定性区域优化覆盖
受实际部署条件差异、网络资源有限和覆盖目标特性等多方面的影响, WSN覆盖控制成为一个NP难问题。遗传算法具有并行搜索、群体寻优的特点, 已广泛用于解决NP难问题。
3.1 遗传算法
借鉴生物进化论, 遗传算法将要解决的问题模拟成一个生物进化的过程, 通过复制、交叉、突变等操作产生下一代的解, 并逐步淘汰掉适应度函数值低的解, 增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。
3.2 具体计算过程
3.2.1 编码方案
设Ng为基因长度, Nv为基因有效长度, G为种群中一个个体基因, Vi是种群中的个体, Pc是交叉发生概率, Pm是变异发生概率, M是种群规模, E是终止进化代数, Tf遗传算法最大迭代次数。覆盖在平面区域W-H的圆的个数在演化过程中不是定值, 我们取其上界Ng作为基因的长度。则种群中G是一长度为Ng的串, 其中每一个结点G[i]是个二元组 (xi, yi) , 1xi1000, 1yi1000。Ng的求取办法为:对平面区域W进行边长为75的正六边形镶嵌, 由这种镶嵌得到的圆覆盖个数Ng即为的取值。
编码时, 从G[0]开始依次将区域W-H中的圆的信息编入G, 设此时区域W-H中的圆的个数为Nv, 则G中只有G[0]G[Nv1]范围内的节点表达有效信息, 因此定义Nv为基因G的有效长度。
3.2.2 初始种群的选取
首先将待覆盖区按照六边形覆盖方法进行全区覆盖, 得出方案, 然后在W上添加H。显然, 圆心处于椭圆中的圆是无效的, 我们先除去这类圆。将此种圆分布方案编码, 作为种群中的第一个个体V0。种群规模为Sa, 对种群中的个体交替应用变异策略和繁殖策略, 并对新个体应用相应的约束处理, 直道个体总数达到Sa。
3.2.3 个体的适应度
个体的适应度用目标函数定义, 则适应度函数为f=-。在此过程中对于不可行个体, 即适应度为-个体, 保持其适应度f=-, 不重新计算。
3.2.4 选择策略
在一次迭代中, 对种群中所有个体按照其适应度排序, 取位于前50%的个体作为下一次迭代的父代个体, 从种群中去除后50%的个体。
3.2.5 繁殖策略
在一次繁殖中, 个体Vi完全复制其自身, 生成一个与其完全相同的个体Vj。全部个体繁殖完成之后, 每个个体随机选择一个与其基因不相同的个体与其配对, 也就是说Vi不可以选择Vi, 进而进行杂交。
3.2.6 杂交策略
针对本题的特点, 杂交后各个圆的位置不应当有太大的变化, 因此采用交换杂交策略。个体Vi和个体Vj进行杂交时, 从中Gi随机选择一些结点, 则在Gi和Gj的有效长度之内, 将这些结点与Gj中与其下标相同的结点互换。例如Gi随机选择的结果是:3, 8, 15, 则将和Gi[3]和Gj[3]互换, Gi[8]和Gj[8]互换, Gi[15]和Gj[15]互换。随机选择的概率为Pc。
3.2.7 变异策略
在一次迭代中, 对每一个体, 要在其基因中随机选择若干结点, 改变该点的取值, 这个概率即为个体的变异概率, 为Pm。改变某结点 (xi, yi) 的取值的方法是:取一个上的[1, 1000]随机数且xi, 取一个上的[1, 1000]随机数且yi, 用 (, ) 替代 (xi, yi) 。
3.2.8 约束处理
不满足约束条件的个体称为不可行个体。对于不可行个体, 对其在一定范围内进行修补, 如果修补后的个体满足约束, 则用修补后的个体替换原个体。如果修补失败, 将其适应度调整为-, 则该个体将在选择过程中被淘汰。
3.2.9 终止条件
本算法采取如下两条终止条件:迭代次数限制:迭代次数超过Tf, 则算法终止。适应度饱和:如果最近E次的迭代的最优适应度梯度之和小于某一阈值h, 则算法终止。即h时, 算法终止
3.2.1 0 控制参数选择及结果
本问题的控制参数为:Sa=100, P c=0.3, Pm=0.005, Tf=10000, h=10-5, 在此组控制参数下得到的分布方案如图所示:
4. 结语
本文研究了有约束条件的无线传感器网络区域优化覆盖问题, 提出了基于遗传算法的确定性优化覆盖机制, 给出了实验结果.结果表明, 本文提出的机制能够解决提出的问题。本文不足, 只研究了传感器数量较小, 覆盖区域内有单个约束区的情况, 其他情况还需进一步研究。
摘要:随着传感器技术大量应用于安防、监测等领域, 覆盖成为了无线传感器网络的一个基本问题, 反映了网络监测和实现目标跟踪的质量效果。本文主要针对传感器节点初始覆盖有约束条件的情况, 研究了确定性区域传感器覆盖问题。提出了基于约束遗传算法的覆盖机制。仿真结果表明该算法能快速收敛于最优解, 完成有约束条件的传感器初始覆盖, 从而实现传感器网络的快速优化覆盖。
关键词:遗传算法,确定性区域覆盖,传感器节点部署
参考文献
[1]Yuri B Shtessel, McDuffie J。Sliding mode control of the X-33 vehicle in launch and re-entry mode[R].Boston:Marshall Space Flight Center, 1998
[2]李明, 石为人.异构无线传感器网络中基于模拟退火算法的成本最优部署机制[J].传感技术学报, 2010, 23 (6) :855-858.
传感器节点部署 第3篇
关键词:粒子群优化算法,无线传感网络,节点部署
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.
传感器节点部署 第4篇
水果蔬菜经过一段时间的贮藏后, 品质均会不同程度的下降, 如水分流失、苹果出现炭疽病等。为了充分满足人们对果蔬的日常需求, 需要对果蔬进行长期且高质量的贮藏, 采用气调保鲜冷藏是目前最为有效的途径。气调冷藏技术是目前最先进的果蔬冷藏技术, 它通过调节贮藏环境的温湿度和气体组成, 为保鲜食品创造一个最佳环境, 降低果蔬贮藏期间的损耗, 获得较好贮藏效果。如果能集中建立大型的气调冷藏库, 将散户种植的果蔬产品进行集中贮藏, 不但能保证果蔬的品质, 提供日常供给, 而且产品售价相对较高, 有利于增加农户收入。
无线传感器网络是一种低成本、高可靠性的信息获取技术, 它是利用传感器节点, 实时采集监测对象的各种信息, 使用户随时随地获得真实可靠的数据。在气调冷藏库中采用无线传感器网络, 可以准确地收集冷藏库内温度、湿度和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.
传感器节点部署 第5篇
无线传感器覆盖问题直接影响网络的成本及感知质量, 因此如何在极大网络覆盖率的同时减少部署节点的数目成为最基本和重要的部分。国内外对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.
无线传感器网络节点设计综述 第6篇
关键词:无线传感器网络,节点,能耗
引言
无线传感器网络 (Wireless Sensor Network, WSN) 是当前国际上备受关注的、由多学科高度交叉的新兴前沿研究热点。无线传感器网络包括传感器节点 (node) 、汇聚节点 (Sink node) 、外部网络和用户界面。大量传感器节点随机部署在感知区域, 通过自组织方式构成网络, 传感器节点将采集到的数据沿着其他传感器节点逐跳进行传输, 经过多跳路由后到汇聚节点, 再由汇聚节点通过外部网络把数据传送到处理中心进行集中处理。
1 无线传感器网络节点概述
1.1 节点组成
无线传感器网络节点是一个微型嵌入式系统。节点硬件由传感器模块、微处理器模块、无线通信模块和电源模块组成, 其结构如图1所示。微处理器模块是节点的核心, 用来进行节点设备控制、任务调度等;无线通信模块用来完成节点间无线通信传输;传感器模块用于采集节点所处地域的温度、湿度等信息;电源模块用来为节点的正常工作、空闲、休眠等提供电能。
1.2 节点组成部分介绍
1.2.1 微处理器模块
处理器模块是无线传感器节点的核心, 应具有较高的集成度、尽可能低的能源消耗、尽量快的运行速度、尽可能多的I/O和扩展接口和尽可能低的成本。可作为Zigbee节点的微处理器有Atmega128L (Atmel公司) 、MSP430 (TI公司) 、PIC18F (Microchip公司) 、HCS08 (Motorola公司) 等。在选择处理器时应该首先考虑系统对处理能力的需要, 然后再考虑功耗问题。
1.2.2 通信技术
常用的无线通信技术有:802.1lb、802.15.4 (Zigbee) 、Bluetooth、UWB等, Zigbee是一种近距离、低复杂度、低功耗、低数据速率及低成本的双向无线通信技术, 同时支持地理定位功能, 非常适合应用在无线传感器网络中[1]。Bluetooth工作在2.4 G H z频段, 传输速率可达1 0 M b p s;缺点是传输距离只有1 0 m左右, 多用于家庭个人无线局域网。8 0 2.11b因为功耗高而应用不多。激光功耗比用电磁波低, 更安全, 但是只能直线传输, 易受大气状况影响。U W B具有发射信号功率谱密度低、系统复杂度低、安全性好、数据传输率高、能提供数厘米的定位精度等优点;缺点是传输距离只有1 0 m左右, 隔墙穿透力不好。
1.2.3 射频芯片
从性能、成本和功耗方面考虑, RFM公司的TR1000和Chipcon公司的CC1000是理想的选择。这2种芯片各有所长, TR1000功耗低一些, CC1000灵敏度高一些, 传输距离更远。还有一类无线芯片本身集成了处理器, 如CC2430是在CC2420的基础上集成了5 1内核的单片机[2];CC1010是在CC1000的基础上集成了51内核的单片机, 使得芯片的集成度进一步提高。常见的无线芯片还有Nordic公司的nRF905和nRF2401等系列芯片, 因为功耗较高, 接收灵敏度比较低, 开发难度较大, 在实际的无线传感器网络中应用较少。
1.2.4 电源模块
电源模块作为整个无线传感器节点的基础模块, 是节点正常顺利工作的保证。由于是无线网络, 所以无法采用普通的工业电能, 只能使用自己存储的能源或者是自然界的给予。自然界可利用的能量有太阳能、电磁能、振动能及核能等。因此, 采用什么能源, 采取什么样的供电方式显得尤为重要, 本模块中必须解决好能源消耗与网络运行可靠性的关系。
2 节点设计中的关键问题
2.1 降低能耗
2.1.1 休眠机制
因为节点长期处于无人值守的状况下, 有效的能耗策略必不可少。目前最常使用的策略是休眠机制, 即在节点空闲时, 使其处于休眠状态, 此时其能耗降到最低。但是休眠的节点在转回正常状态的时候, 往往会消耗大量的能量, 因此寻找合理的状态转换策略是确保休眠机制成功的关键。
2.1.2 数据融合
数据融合是另一项节能技术。多个邻近节点经常会采集同样的信息, 发送这些冗余信息就给系统增加了不必要的负担。因此, 通过本地计算和筛选, 确保发送出最有效的信息就是数据融合的任务。
2.1.3 减少不必要的功能, 突出专用性
在功能上, 无线传感器网络大都是为某一专用目的而设计的, 去掉不必要的功能, 可以节省能量, 延长节点的生存时间。因此, 在设计无线传感器网络时需要考虑:延长网络工作时间、减少不必要的功能, 突出专用性。
2.1.4 应用能提高传感器网络能量效率的协议
设计专门的提高传感器网络能量效率的协议, 这些协议涉及网络的各个层次, 如物理层可以采用超宽带无线通信技术, M A C层可以采用适合节点在休眠和工作状态间切换的接入协议, 网络层可以以节点能量作为路由度量等。L E A C H协议考虑到了传感器网络节点的能量问题, 该协议作为一种分层路由协议, 通过簇头节点与信息收集节点通信, 减少了其它节点的能量消耗。门限敏感能量有效协议 (TEEN) 通过设定两个门限值, 来减少传输节点所采集、传输的数据, 从而节省能量消耗。信道自适应能量管理 (CAEM) 协议是一种结合物理层和MAC层的跨层自适应能量管理协议。仿真表明该协议有效地减少了能量的消耗[3]。
2.2 计算和存储能力有限
传感器节点是一种微型嵌入式设备, 要求它价格低功耗小, 这些限制必然导致处理器能力比较弱, 存储器容量比较小。为了完成各种任务, 传感器节点需要完成检测数据的采集和转换、数据的管理和处理、应答汇聚节点的任务请求和节点控制等工作。如何利用有限的计算和存储资源完成诸多协同任务成为传感器网络设计的挑战。
2.3 抗干扰
传感器节点有些会设置在屋内, 也有许多会设置在户外, 由于会在各种环境下布建及设置节点, 所以节点必须具备现场环境的因应能力。现场环境可能极寒冷、极炎热、极干或极湿、或有大量沙尘, 或经常晃震 (设置在汽车内或桥梁上) , 这些都不能对节点的感测产生影响, 也不能对节点内的电路运作产生影响, 同时也不能对感测后的信息传递产生影响。因此节点设计, 不仅要考虑节点的机构 (外壳) 设计、内部电路的设计, 还要考虑通讯传递的设计, 在无线通讯的协议设计上就要格外用心[4]。
3 结束语
针对不同的应用, 目前国内外存在很多无线传感器网络节点。本文对节点的微处理器模块、通信技术、射频芯片和能量供应模块进行了分析。针对节点设计中的能耗问题, 着重讨论了降低能耗的方法。随着技术的发展, 相信无线传感器网络最终会广泛应用于人们生活的方方面面。
参考文献
[1]Akyildiz I F, Su weilian, Sankarasubramaniam Y, et a1.ErdalCayirci.Wireless sensor networks:a survey[J].Computer Networks, 2002, 38 (4) :393-422
[2]马永强等.基于ZigBee技术的射频芯片CC2430[J].新器件新技术.2006 (3) 45 ̄47
[3]无线传感器网络综述[OL]http://wenku.baidu.com/view/2e93a0eb6294dd88d0d26b45.html, 2010.5
无线传感器网络节点定位技术综述 第7篇
无线传感器网络(WSN, Wireless Sensor Network)是由部署在监测区域内大量微型传感器节点相互协作构成的一个多跳自组织网络,其目的是协作的感知、采集和处理网络覆盖区域内被监测对象的信息,如温度、湿度、压力、移动物体的速度等,并发送给观察者[1]。WSN具有传感器节点数量大、分布广、网络动态性强、感知数据流大、单个节点成本低廉等特点。WSN技术的出现使人们获得了一种可以持续实时监测环境的新途径,是一种“无处不在”的传感技术,可以广泛应用在环境检测、医疗健康、反恐防灾等场合。
在WSN中,位置信息对传感器网络的监测活动至关重要,确定事件发生的位置或获取消息的节点位置是传感器网络基本的功能之一,对传感器网络的有效性起着关键作用。定位信息除了用于报告事件发生的地点之外,还可用于其他用途。例如,目标实时跟踪——实时监视目标行动路线,预测目标前进的轨迹;协助路由——直接利用节点位置信息建立数据传递的地理路由协议,可以避免信息在整个网络中的扩散,并可实现定向信息查询;网络管理——利用传感器节点传回的位置信息构建网络拓扑结构,并实时统计网络覆盖情况,对节点密度低的区域及时采取必要措施;定点、定时传播——用户可在指定时间将信息传递至特定区域。总之,了解节点的位置信息,可使WSN工作的目的性更强,效率更高。
从1992年AT & T[2] Laboratories Cambridge开发出室内定位系统Active Badge至今,研究者一直致力于这一领域的研究。微软研制的RADAR2[3]系统,是基于IEEE802.11无线局域网标准,可以在楼层内实现节点的定位。加利福尼亚大学构建的AHLos(Ad-Hoc Localization System)[4]系统中,未定位节点根据周围已知位置节点的分布情况,利用迭代算法进行定位。麻省理工大学开发的Cricket系统[5]可以对位于大楼内的移动或静止节点进行定位。在试验环境较为理想的条件下,上述系统能够正常工作并为节点获得定位。但是实际应用中难以避免节点测量存在误差、实际环境(如地形、温度湿度等)对测量值影响的不确定性等问题,导致节点的定位效果大受影响,目前,学术界对无线传感器网络应用于实际环境的研究尚不完善,需提出更健壮、高效的算法,促进无线传感器网络的进一步普及。
1 节点定位的基本原理
无线传感器网络中包含大量传感器节点,通常节点的放置采用随机撒布放置方式,如果依靠人工标定来确定每个节点的位置,其工作量巨大,难以完成。另一种可直接获得节点位置的方法是为每个节点配备全球定位系统(GPS),但由于节点数目众多,考虑到价格、体积、功耗等因素的限制,通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置或为它们配备定位系统(如GPS),这些节点通常称为锚节点。目前节点定位的研究热点集中于如何利用这些锚节点提供的位置信息与节点间的协作,来计算非锚节点的位置。
无线传感器网络定位问题的一般前提假设是:
(1) 网络具有较高的密度;
(2) 网络内每一个节点具有全网唯一的ID;
(3) 在没有特别说明的情况下,所有节点具有相同的最大通信距离;
(4) 在定位过程中,假设节点相对位置不变。
2 节点定位的方法
2.1 无线信号测量方法
节点定位的计算通常需要一些表征几何特征的原始数据,这些信息可以通过对无线信号的某些特征进行测量来获取。以下介绍几种常用的无线信号测量方法。
测量信号到达时间(TOA. Time of Arrival)[6]——已知信号的传播速度,根据传播时间来计算距离,得到的结果精度高,但要求节点保持精确时间同步,对节点硬件和功耗提出了较高要求。
测量不同信号到达时间差(TDOA. Time Difference of Arrival)[7]——由两节点同时发送信号,待定位节点根据两信号的到达时间差来计算距离。这种技术对硬件的要求较高,但是测距误差小。使用TDOA方法发送信号易受干扰,不适合于大规模的传感器网络。
测量接收信号到达角(AOA. Angle of Arrival)[8]——通过天线阵列或多个超声波接收器感知发射节点信号的到达方向,由此获得接收节点和发射节点之间的相对方位或角度。这种技术对接收硬件要求较高。
测量节点的信号强度(RSSI. Received Signal Strength Indicator)[9]——利用信号在传递过程中的衰减特性进行距离估计。已知发射节点的发射信号强度,接收节点根据收到的信号强度,计算出信号的传播损耗,基于理论和经验的信号衰减模型将传输损耗转化为距离。该方法符合低功率、低成本的要求,但信号强度易受环境的影响。
测量节点是否在发射信号的接收范围内[10]——使用已知发射功率的信号,或者使用定向天线改变发射信号方向来检测接收节点是否在信号覆盖区域内,通过覆盖区域的重叠面积计算来确定节点的位置范围。
2.2 节点定位的计算方法
获得了检测量后,利于如下方法得到节点的定位。
三边(多边)计算法:已知平面上(空间上)三(多)点的位置A,B,C,以及D点到A,B,C的距离,利用几何方法可求出D点的坐标。
三角(多角)计算法:已知平面上(空间上)三(多)点的位置A,B,C,以及D点为角顶点,角边的端点为A,B,C的角度,可求出D点的坐标。
极大似然估计法:已知很多节点D的相邻节点坐标以及它们到节点D的距离或方位,使用最小均方差估计方法得到节点D的坐标。
利用范围重叠计算:
(1) 重叠区域质心算法[11,12]:定位算法首先确定包含未知节点的区域,计算这个区域的质心,并将其作为未知节点的位置。
(2) 凸规划算法[13]:将节点的定位问题转化为凸约束优化问题,然后使用半定规划和线性规划方法得到一个全局优化的解决方案。
(3) 跳数距离估算法[14]:计算节点之间的跳数,利用估算或者直接使用节点的通信半径得到平均每跳,再结合跳数估算距离。
(4) 变覆盖范围定位算法[10]:利用移动的锚节点周期性广播其当前位置,未知节点根据这些信息计算其位置(包括ID,位置,时间戳),该算法的理论基础是圆的任意两条不同弦的垂直平分线的交点即为圆的中心。或者通过锚节点的发送功率和定向天线的方向来产生多个覆盖区域。
(5) 模板匹配算法[3]:通过比较数据库中训练模板与接收信号模板实现定位,该方法被称为“指纹识别”,该方法中使用随机概率的方法对信号强度进行建模。
2.3 定位算法的分类
根据不同分类原则,可以将无线传感器网络中的定位算法做如下划分:
(1)集中式计算与分布式计算
集中式计算是指将需要的信息传送到某个中心节点进行定位计算。典型的集中式算法有凸规划[13],质心定位算法[11],MDS-MAP算法[10],APIT算法[12]等。
分布式计算是指依赖节点间的信息交换和协调,由节点自行计算的定位方式,典型的算法有Bounding Box1[15],DV-Hop[14],Robust Position1[16]等。
(2)基于测距技术的定位和无需测距技术的定位
基于测距技术通过得到节点间的距离或角度信息,使用三边测量、三角测量、极大似然估计等方法计算节点位置。无需测距定位,不需要距离和角度信息,仅根据网络连通范围等信息实现定位。典型的基于测距定位有AHLos,不需要测距的算法有质心定位算法,MDS-MAP算法,APIT算法等。
(3)绝对定位与相对定位
绝对定位的定位结果是一个标准的坐标位置,如经纬度。目前大部分WSN系统采用这种表示方式。相对定位通常以网络中部分节点为参考,建立整个网络的相对坐标系统。典型的相对定位算法有SPA[11](self-position algorithm)。而MDS-MAP定位算法可以根据网络配置的不同分别实现两种定位。
(4)细粒度定位(fine-grained)和粗粒度(coarse-grained)定位
根据接收信号强弱、时间、方向和信号模式匹配等完成定位的称为“细”,根据节点接近度进行定位的称为“粗”。高精度的定位技术往往要求较高的器件水平和能耗,在有些场合下,为了满足传感器网络节点的低成本、低能耗的要求,需要根据任务和需求选择适度“粗”的算法。细粒度的典型算法有质心算法、Active Badge[2]、凸规划等。粗粒度的典型算法有跳数距离估算法等。
(5)循环求精和一次计算
大部分定位算法都采用一次计算得到节点的位置。循环求精是在起始阶段得到节点位置的粗略估计,在循环阶段每个节点向其邻居节点广播它的位置估计,并根据从邻居节点接收的位置信息和节点间的测距结果重新计算自身位置,直至两次计算得到的位置估值之差小于一定的域值。典型的循环求精算法有Cooperative ranging[17]和Two-Phase Positioning[16]。
3 性能方法的评价标准
目前,文献中对WSN定位算法评价标准的研究尚不完善,以下介绍几种常用的评价标准。
(1)定位精度:
一般用误差值与节点的无线电测距射程的比例表示,例如定位精度为20%表示误差是射程范围的20%。
(2)锚节点的密度:
因为锚节点通常依赖人工部署或安装GPS等定位设备,使用成本较高。锚节点的使用数量是限制WSN规模、影响WSN成本的重要指标之一。
(3)功耗:
由于传感器节点的能量有限,控制功耗是WSN的一项重要工作。因此定位算法所需要的计算复杂度、时间复杂度、通信开销、存储开销等成为影响功耗的重要因素。
(4)规模:
不同的定位系统或算法所能定位目标的数量是一个重要的评价指标。节点数量增加带来了网络通信干扰、结构复杂度和通信复杂度的增加。规模的扩大对算法的适应性提出了考验。
(5)容错性和适应性:
实际应用场合存在着多种不确定性,例如多径传播、通信盲点,节点能量耗尽、损坏等。这要求定位系统和算法有较强的容错性和适应能力,能自动调整,减小不确定因素带来的错误和误差。
4 节点定位技术的发展方向
为了适应目前的器件水平,无线但感器网络还需要更低能耗、更高效的节点定位技术。目前,有关该领域的研究主要集中在以下方向:
(1) 低成本、高能效、高精度的距离或角度测量技术。
(2) 为尽量延长网络生存周期的低复杂度、低开销、低能耗的节点定位算法。
(3) 适用于大规模或超大规模无线传感器网络的低成本节点定位技术。
另外,已提出的节点定位算法研究成果大部分是基于静态网络的,对移动节点定位技术研究相对较少,适用于网络拓扑结构处于动态变化时的节点的定位技术还有待研究。