基于最小圆和灾燥则燥灶燥蚤图的传感网节点覆盖部署快速优化算法
云葬泽贼悦燥增藻则葬早藻韵责贼蚤皂蚤扎葬贼蚤燥灶粤造早燥则蚤贼澡皂月葬泽藻凿燥灶酝蚤灶蚤皂怎皂悦蚤则糟造藻
葬灶凿灾燥则燥灶燥蚤阅蚤葬早则葬皂蚤灶杂藻灶泽燥则晕藻贼憎燥则噪
周建辉
刘广聪渊广东工业大学计算机学院袁广东广州缘员园园园远冤
摘要院针对现有的传感网节点覆盖部署优化迭代算法袁大多存在迭代次数较多尧算法耗时较长尧计算结果容易陷入局部最优等问题袁提出一种基于最小圆和灾燥则燥灶燥蚤图的优化算法袁在对平面区域进行最佳部署规划以及给每个最优节点进行编号命名的同时袁对散落于真实环境中的传感器节点进行对应编号袁通过编号配对实现对传感器节点位置的快速调度优化遥仿真实验测试的结果表明袁所提出的算法能够使覆盖率得到保证且不易陷入局部最优袁并且能够有效降低算法耗时和节点能耗遥
关键词院传感器网络曰节点覆盖曰优化曰最小圆曰灾燥则燥灶燥蚤图
粤遭泽贼则葬糟贼押陨灶贼澡蚤泽责葬责藻则熏葬灶燥责贼蚤皂蚤扎葬贼蚤燥灶葬造早燥则蚤贼澡皂遭葬泽藻凿燥灶皂蚤灶蚤皂怎皂糟蚤则糟造藻葬灶凿灾燥则燥灶燥蚤凿蚤葬早则葬皂蚤泽责则燥责燥泽藻凿援陨灶贼澡蚤泽葬造早燥鄄则蚤贼澡皂熏贼澡藻燥责贼蚤皂葬造凿藻责造燥赠皂藻灶贼责造葬灶灶蚤灶早枣燥则责造葬灶葬则葬则藻葬葬灶凿贼澡藻灶怎皂遭藻则燥枣藻葬糟澡燥责贼蚤皂葬造灶燥凿藻葬则藻糟葬则则蚤藻凿燥怎贼熏葬灶凿贼澡藻糟燥则则藻鄄泽责燥灶凿蚤灶早灶怎皂遭藻则燥枣泽藻灶泽燥则灶燥凿藻泽泽糟葬贼贼藻则藻凿蚤灶则藻葬造藻灶增蚤则燥灶皂藻灶贼蚤泽早蚤增藻灶援月赠灶怎皂遭藻则蚤灶早责葬蚤则泽熏贼澡藻造燥糟葬贼蚤燥灶燥枣灶燥凿藻泽蚤泽择怎蚤糟噪造赠泽糟澡藻凿怎造藻凿葬灶凿燥责贼蚤皂蚤扎藻凿援
运藻赠憎燥则凿泽押泽藻灶泽燥则灶藻贼憎燥则噪熏灶燥凿藻糟燥增藻则蚤灶早熏燥责贼蚤皂蚤扎葬贼蚤燥灶熏皂蚤灶蚤皂怎皂糟蚤则糟造藻熏灾燥则燥灶燥蚤凿蚤葬早则葬皂
的欧氏距离表达式记为院阅渊泽蚤袁泽躁冤越姨渊曾蚤原曾躁冤垣渊赠蚤原赠躁冤袁蚤越员袁圆袁噎袁
圆圆传感器网络是由多个传感器节点通过连接所组成的一种计算机网络遥每个传感器节点均各自承担着对指定区域进行覆盖监测的工作任务遥覆盖程度的好坏直接影响着整个传感网的监测质量遥
近年来袁国内外有不少学者对传感器网络节点的覆盖优化方法进行研究遥其中大多数研究袁集中在利用某些几何数学特征进行位置的迭代优化袁或者引入某些改进的搜索算法对位置最优值进行搜寻咱员原猿暂袁这些算法均尝试对相关的性能指标进行优化袁但是在结果上较为容易陷入局部最优袁这一定程度上影响了性能的表现遥针对此情况袁本文以利于提升覆盖率尧优化算法耗时和节点能耗的角度袁提出一种新的算法解决上述问题遥员系统建模
员援员传感器节点感知模型
传感器节点的感知范围袁是一个以节点坐标点为圆心尧砸泽为半径的封闭圆盘区域遥砸泽称为传感器节点的感知半径袁这个圆称为传感器节点的感知圆遥设平面区域内的传感器节点集为邀杂员袁杂圆袁噎袁杂晕妖袁节点杂蚤的坐标为渊曾蚤袁赠蚤冤袁蚤越员袁圆袁噎袁晕遥节点泽蚤尧泽躁之间
晕曰躁越员袁圆袁噎袁晕遥
要使得传感器网络的覆盖率最大且节点冗余程度最小袁需要满足下述条件院任意三个相邻传感器节点的感知圆盘相交于一点袁且感知圆盘之间无间隙曰连接这三个节点的位置可形成一个边长为姨猿砸泽的正三角形咱源暂遥这种部署称为最佳部署袁此时所形成的灾燥则燥灶燥蚤图袁如图员所示遥
图员最佳部署示意
员援圆灾燥则燥灶燥蚤图
设平面区域内分布着若干个散点袁存在满足下述条件的区域划分院划分后每个小区域内只包含一个散点曰且该小区域内的任意一点袁与含于小区域内的散点的欧氏距离袁比与其它散点的欧氏距离小遥形如这样的平面区域划分图袁称为灾燥则燥灶燥蚤图遥灾燥则燥灶燥蚤图上的每条直线段袁实质是平面区域内与之相关的两个散点之间的垂直平分线段袁称为灾燥则燥灶燥蚤边遥对于存在共有灾燥则燥灶燥蚤边的两个散点袁互为相邻点遥
员援猿传感器节点的覆盖率与最佳部署规则
传感器节点的覆盖率袁为已被监测到的目标点的数量袁与需被监测的目标点的数量的比值遥当需要监测的区域内密布目标点时袁可视之为已被覆盖到的面积与需覆盖的面积之比遥本指标可用于评价传感器网络的覆盖质量遥
在已知拟采用的传感器节点的感知半径以及需布放传感器节点进行监测的平面区域的大小的情况下袁通过这种最佳部署规划袁可以提前获知应投放的传感器节点的最小数量遥这对于农场尧林地等人工经营区域袁在监测质量得以保证的前提下袁有利于降低成本尧减轻布放的规划难度遥若实际投放的传感器节点数量少于最佳部署规划所要求的最小数量袁需监测区域将不能得到完全覆盖遥所以袁在本文中袁实际投放的传感器节点的数量默认不低于最佳部署规划所要求的最小数量遥员援源最小圆
当平面区域内存在若干个散点时袁存在唯一的最小包围圆袁使得所有散点均落于该圆上或圆的封闭区域内咱缘暂遥该最小圆是可包围全部散点的所有包围圆中半径最小的一个遥这样的最小圆袁最少存在两个且最多存在三个散点落于圆上遥当只有两个散点落于圆上时袁则这两个散点的连线恰好是该圆的其中一条直径曰当存在三个散点落于圆上时袁则该圆为这三个散点的外接圆遥
70
圆基于最小圆和灾燥则燥灶燥蚤图的传感网节点覆盖部署快速优化算法
为了解决现有大多数自迭代算法中袁由于算法的多次迭代而导致整个算法时耗和能耗过大尧计算结果容易陷入局部最优的问题袁本文提出一种基于最小圆和灾燥则燥灶燥蚤图的传感网节点覆盖部署快速优化算法遥本算法以求通过控制端依员援猿节所述来规划的传感器节点最佳部署方案袁对归属于相应灾燥则燥灶燥蚤多边形中的传感器节点进行层次化编号曰与之同时袁对归属于相应层次最小圆中的尧位于实际平面区域内的传感器节点袁同样进行对应的层次化编号曰然后再对两个编号结果中具有相同编号值的节点进行匹配结对袁使散落于实际平面区域内的各传感器节点袁移至自身应属的最优位置袁实现对传感器网络节点位置的快速优化遥圆援员对灾燥则燥灶燥蚤最佳部署规划图中的传感器节点进行编号
根据已知平面区域的形状尧大小袁以及选用的传感器节点的感知半径等数据袁依员援猿节所述袁对传感器节点的最佳部署方案进行规划袁测算出传感器节点应配置的最小数量袁并且给出每个传感器节点应处的最佳位置袁形成最佳部署时的灾燥则燥灶燥蚤节点分布图遥如图圆所示遥
图圆最佳部署节点的编号示意
接着开始对位于灾燥则燥灶燥蚤节点分布图中的所有传感器节点袁逐个进行层次化编号袁每个层次将存在若干个归属于该层次的传感器节点遥每个传感器节点按照野层次号援该层次内的序号冶的规则进行编号命名袁如归属于第猿层次尧序号为源的传感器节点袁将被编号为野猿援源冶遥
首先袁把位于灾燥则燥灶燥蚤节点分布图形心位置的传感器节点作为第一层次的节点进行编号袁该节点只有一个袁编号记为野员援员冶遥
第二步袁对与上一层次的节点相邻尧且未被编号的传感器节点袁归属于下一层次进行编号遥归属于即将被编号层次的全部传感器节点袁均逐一紧紧环绕在上一层次的传感器节点外围袁形成环形分布遥以其中的某个传感器节点袁指定其从属于该层次内的序号为员袁然后依顺时针方向袁对从属于该层次内的其它传感器节野圆援员点逐一冶尧野进行排序并编号遥如第圆层次内的节点编号袁依次为第三圆援圆步冶尧噎遥
袁重复第二步的操作袁对归属于其余各层次的传感器节点袁按序逐一编号袁直至对整个平面区域内的所有节点完成编号的工作遥
在完成对所有传感器节点的层次化编号的工作后袁整个编号过程所产生的层次数目尧归属于每个层次的传感器节点数量均可确定遥
圆援圆对散落于最小圆内的真实传感器节点进行编号
在真实平面区域内袁散落分布着若干传感器节点遥这些传感
基于最小圆和灾燥则燥灶燥蚤图的传感网节点覆盖部署快速优化算法器节点需要进行位置的调整优化遥
第一步袁对在平面区域内的全部传感器节点袁画出其最小圆遥这个最小圆也即全部传感器节点的外接圆袁其具有唯一性遥与此同时袁确定这个最小圆的圆心位置的坐标遥
由于在对灾燥则燥灶燥蚤节点最佳部署图中的传感器节点进行编号的工作中袁每一个经过最佳部署规划的传感器节点袁均确定了其应当归属的层次号和层次内的序号袁也即每一个传感器节点均有具唯一性的编号遥所以袁对实际平面区域内的待位置调整优化的传感器节点袁将应用与之相应的命名规则进行编号命名遥
第二步袁以第一步所确定的最小圆的圆心作为新圆的圆心袁按下述要求作出若干个半径逐步增大的新圆遥新圆的数量即最佳部署规划中节点编号的层次数袁每一个新圆需足以涵盖其所属层次内的传感器节点的数量遥
首先袁作出第一个新圆袁其所要包围的是归属于第一层次内的传感器节点遥从最佳部署规划中可知袁从属于第一层次的传感器节点实质只有一个袁故第一个新圆只需以最小半径袁包围一个传感器节点在圆的闭区域内即可袁并把该传感器节点的编号命名为野员援员冶遥若出现了两个或以上的节点袁出现在第一个新圆的闭区域内袁此时这几个节点实质均落在圆上袁则随机选择其一作为第一层次的传感器节点袁把其余的节点归属于下一层次进行编号遥
然后袁作出第二个新圆袁用于涵盖归属于第二层次的传感器节点遥已被上一层次编号的传感器节点袁不会被本层次重复编号遥对尚未被编号的传感器节点袁以其中之一为第二层次中的序号员袁将其编号为野圆援员冶曰并视半径为时针袁以顺时针方向扫描其余各点袁依序将之编号命名为野圆援圆冶尧野圆援猿冶尧噎遥同样袁若第二个新圆包含未被编号节点的数量袁超过第二层次最佳部署时所能容纳的节点数量袁则剩余未被编号的传感器节点将被纳入下一层次进行编号遥
同理袁作出下一个新圆袁并对归属于下一层次的节点进行编号袁直至完成对位于平面区域内的所有传感器节点的编号工作遥如图猿所示遥
图猿真实环境中待优化的节点编号示意
圆援猿根据对应标号散点快速移动到最优位置
通过对灾燥则燥灶燥蚤最佳部署规划图中的传感器节点以及散落于最小圆内的位置需调整优化的现实传感器节点两者袁分别完成编号工作后袁可以看到袁两者均拥有了通过一致命名规则而来的尧一一对应的编号遥
最后一个关键步骤袁就是利用两者间已确定好的一一对应
叶工业控制计算机曳圆园员怨年第猿圆卷第愿期的编号袁对散落于最小圆内尧位置需调整优化的现实传感器节点袁进行位置的移动调整遥按照自身拥有的编号袁每个现实传感器节点将寻找位于灾燥则燥灶燥蚤最佳部署规划图中尧具有相同编号尧虚拟规划而来的传感器节点所在的理想位置袁然后移动自身至该位置遥
当所有的传感器节点均完成了移至最佳部署位置的动作后袁本算法完成并结束遥猿测试仿真
猿援员仿真场景及参数设置
为了验证所提出的算法的覆盖率尧算法耗时尧节点能耗等指标的性能袁本文设计了仿真实验进行测试遥
本文仿真测试所选用的系统平台是宰蚤灶凿燥憎泽员园系统袁版本号员怨园猿曰中央处理器陨灶贼藻造悦燥则藻蚤缘原苑圆园园哉袁主频圆援缘郧匀扎曰内存愿郧月遥编程软件选用酝粤栽蕴粤月砸圆园员怨葬远源遭蚤贼遥
在实验仿真场景中袁设定监测区域为一个员园园皂伊员园园皂的矩形平面区域袁并在其中随机投放了源缘个传感器节点袁每个传感器节点的感知半径砸泽为员园皂遥在相同的实验环境下袁选用悦月杂尧月悦月杂算法进行对比实验遥每次实验开始前均进行初始化袁取圆园次实验结果的平均值作为比量依据遥猿援圆覆盖率
自迭代算法由于自身特性袁其容易陷入局部最优遥当采用的传感器节点数量大致与最佳部署数量相等时袁悦月杂尧月悦月杂算法在经过圆园次迭代后陷入了局部最优解袁两者覆盖率均未达员园园豫遥由于本文算法通过控制端袁在预规划了最佳部署方案后才进行位置调度袁故结果不会出现局部最优解袁覆盖率可达至员园园豫袁如图源所示遥这体现了本文算法良好的适用性遥
71
图缘算法耗时对比图
图远节点剩余能耗占比对比图
源结束语
本文提出的算法袁无需经历繁重冗杂的迭代运算袁即可实现对传感器网络节点覆盖部署的快速优化袁具有高可靠性和适用性遥今后工作可以继续优化节点编号的方法袁使现实场景中节点的排布与编号给定更为合理袁减小节点在位置优化过程的物理运动距离袁降低节点运动做功产生的能耗遥
参考文献
咱员暂匀藻燥灶原允燥灶早蕴藻藻熏再燥灶早原澡憎葬灶运蚤皂熏再燥怎灶原匀藻藻匀葬灶熏藻贼葬造援悦藻灶鄄
贼则燥蚤凿原月葬泽藻凿
酝燥增藻皂藻灶贼
粤泽泽蚤泽贼藻凿
杂藻灶泽燥则
杂糟澡藻皂藻泽蚤灶宰蚤则藻造藻泽泽杂藻灶泽燥则晕藻贼憎燥则噪泽灶燥造燥早赠悦燥灶枣藻则藻灶糟藻云葬造造熏圆园园怨押员原缘
图源
覆盖率对比图
眼悦演椅灾藻澡蚤糟怎造葬则栽藻糟澡鄄
阅藻责造燥赠皂藻灶贼
猿援猿算法耗时
从图源可知袁自迭代算法悦月杂尧月悦月杂的覆盖率虽然也较高袁但其达至良好覆盖率水平所需迭代次数较大的情况却不容忽视袁两者迭代圆园次后袁覆盖率才明显地趋于收敛遥通过图缘可看到袁当达至图源所示的覆盖率情况时袁本文算法的耗时明显较优袁这得益于本算法的实现无需经历多次的迭代遥猿援源节点能耗
预设传感器节点的初始电能相同且满量遥当完成了一轮优化动作袁覆盖率达至图源所示的情况后袁剩余能量占初始能量的百分比袁如图远所示遥由于悦月杂尧月悦月杂算法的迭代计算次数较多袁其运算能耗较本文算法多遥
咱圆暂方伟袁宋鑫宏援基于灾燥则燥灶燥蚤图盲区的无线传感器网络覆盖控制部署咱猿暂李光辉袁胡世红援基于灾云原悦杂的移动传感器网络覆盖优化算法咱允暂援咱源暂粤皂皂葬则蚤匀酝熏阅葬泽杂运援悦燥增藻则葬早藻熏糟燥灶灶藻糟贼蚤增蚤贼赠熏葬灶凿枣葬怎造贼贼燥造鄄
贼蚤燥灶熏
贼蚤燥灶葬造杂赠皂责燥泽蚤怎皂熏匀藻蚤凿藻造遭藻则早押杂责则蚤灶早藻则熏圆园园远押猿缘原源怨通信学报袁圆园员愿袁猿怨渊猿冤院怨缘原员园苑
藻则葬灶糟藻皂藻葬泽怎则藻泽燥枣憎蚤则藻造藻泽泽泽藻灶泽燥则灶藻贼憎燥则噪泽眼悦演椅杂贼葬遭蚤造蚤扎葬鄄
杂葬枣藻贼赠熏葬灶凿杂藻糟怎则蚤贼赠燥枣阅蚤泽贼则蚤遭怎贼藻凿杂赠泽贼藻皂泽熏愿贼澡陨灶贼藻则灶葬鄄策略咱允暂援物理学报袁圆园员源袁远猿渊圆圆冤院员猿圆原员源员
咱缘暂匀葬泽葬灶匀燥泽泽藻蚤灶蚤晕葬泽葬遭熏酝葬澡凿蚤栽葬增葬灶葬熏酝燥澡泽藻灶再燥怎泽藻枣蚤援粤灶藻憎
澡藻怎则蚤泽贼蚤糟葬造早燥则蚤贼澡皂枣燥则贼澡藻责造葬灶葬则皂蚤灶蚤皂怎皂糟燥增藻则蚤灶早糟蚤则糟造藻责则燥遭造藻皂眼允演援孕则燥凿怎糟贼蚤燥灶驭酝葬灶怎枣葬糟贼怎则蚤灶早砸藻泽藻葬则糟澡熏圆园员源熏圆穴员雪
咱收稿日期院圆园员怨援远援员圆暂
欢迎订阅投稿
欢迎到当地邮局订阅圆园员怨年我刊叶工业控制计算机曳袁订阅代号院圆愿原远园袁月刊袁定价院员圆援园园元辕期遥
投稿可直接发往邮箱院蚤责糟皂赃灶躁岳员远猿援糟燥皂袁投稿详细要求请参见我刊网站渊憎憎憎援蚤责糟皂援糟燥皂援糟灶冤野稿件征集冶频道遥
因篇幅问题不能全部显示，请点此查看更多更全内容