★ FEATURED ARTICLE 上一版部署方案翻车之后我算是彻底想明白了一个道理在真实场地里谈无线传感器网络的覆盖优化躲不开障碍物。墙体会挡信号设备机台会造成遮蔽不规则的区域边界也会直接影响最终部署质量。把场地里的障碍物抽象成长方形、梯形、三角形再把改进的灰狼算法IGWO搬过来做节点位置搜索覆盖率能从78%拉到89%上下而且结果要比标准GWO稳定得多。这篇文章就是我当时做这个复现项目时的完整笔记适合正在做WSN覆盖仿真、需要写论文对比算法、或者想搞懂IGWO到底改在哪里的朋友。先说明一下我最终面对的问题形态一片100×100的监测区域里有几块不能被传感器穿透的障碍物形状分别是长方形、梯形和三角形。需要在自由区域内布置一定数量的传感器节点每个节点有固定的感知半径目标是通过调整节点坐标让被覆盖的网格点数量尽可能多。求解工具就是改进的灰狼算法。下面按我的实际处理顺序展开。1. 为什么覆盖模型必须带上障碍物从距离判断到视距遮挡的升级1.1 网格化离散与覆盖率计算的基本约定做覆盖优化第一步不是跑算法而是把连续区域变成可计算的东西。我的做法是把100×100区域按步长1离散成101×101个网格点步长越小精度越高但计算量会成倍上升。每个网格点代表一个“待覆盖监测位置”传感器节点则是在自由区域内连续取值的决策变量。覆盖率计算的公式很简单覆盖率 被至少一个传感器覆盖的网格点数 / 可行区域网格点数这里有两个容易踩坑的点。一是“可行区域”的限定。障碍物内部的网格点不管是被遮挡还是恰好在里面都不应该计入分母否则覆盖率永远偏低。二是“至少一个”的语义。多个传感器可以覆盖同一个点但要先合并覆盖标记再统计被覆盖网格点数直接累加每个传感器的覆盖点数会重复计算。我最终用一张0/1二值网格图来组织这个计算。每个网格点要么被覆盖为1要么是0覆盖率就是整张图的和除以自由区域点数。这个设计方案虽然朴素但可复现性非常好后面画热力图、算收敛曲线都靠它。1.2 障碍物遮挡下的视距判定逻辑没有障碍时传感器覆盖范围是一个标准圆盘只要网格点到传感器中心的欧氏距离不大于感知半径Rs就认为被覆盖。但加了墙、仓库、设备机台之后问题从“距离判断”升级成了“视距遮挡判断”。我的处理逻辑是先判断距离满足Rs条件再判断传感器节点和网格点之间是否存在一条无障碍的直线路径。这条线段只要穿过了任何一个障碍物多边形那么即使两点直线距离很近信号也被隔断了这个网格点直接被标记为未覆盖。这里有一个非常生活化的类比房间里点了一盏灯灯在书架后面你站在书架另一侧距离可能不到两米但光线就是过不去。无线覆盖和光传播在遮挡模型下有很强的相似性至少在做0/1二元感知模型时基本可以这样理解。实际代码里“是否遮挡”就是判断传感器坐标点与网格点坐标点连成的线段和障碍物多边形的每一条边是否相交。只要有一条边相交就判定为遮挡。这个判定对长方形、梯形、三角形都成立因为它们在建模上本质相同都是一组有序多边形顶点。1.3 目标函数不光滑给优化算法带来的连锁反应加入障碍遮挡后覆盖率函数会发生一个很关键的变化它变得不光滑了。没有障碍时覆盖函数基本上是圆盘并集的可微近似有了遮挡和网格离散化一个节点稍微移动几个像素可能跨越某条障碍边界的投影线导致一批网格点瞬间从“已覆盖”变成“未覆盖”。这种跳跃式变化的适应度函数有很多平台和局部极值梯度类方法基本失效贪婪式部署也会被大片遮蔽区卡死。这正是启发式优化算法的用武之地灰狼算法、粒子群算法这类群体智能方法不依赖梯度只靠适应度大小来迭代反而能在这种“坑坑洼洼”的地形里找到更好的解。但标准灰狼算法在带障碍的覆盖场景里直接使用并没有那么靠谱。下面这段是我的实测体会。2. 原始GWO在带障碍场景下的三个先天短板2.1 随机初始化脆弱初始解分布不均匀灰狼算法的原始初始化很简单在每个变量的上下界内用rand均匀随机生成。无障碍场景里这个做法问题不大因为整个区域都是连通的随机撒点总能覆盖到各个方位。但一旦区域里有了长方形、梯形、三角形障碍自由区域被切割成了好几块“碎片”随机生成的节点位置很容易集中在某一侧或者好几个节点挤在同一个可通行角落。障碍物越大这种问题越明显。我遇到过一种极端情况随机初始化的30个典型个体里有一半以上的个体把超过三分之一的节点放在了区域左半边的狭长通道里右半边大片自由区域完全没有节点覆盖率低到没法看。理论上算法后期有机会爬出来但群体智能优化的特点是“初始种群的分布决定探索的上限”你起步就丢了半边区域后面想靠迭代补回来代价非常大。2.2 线性收敛因子导致探索与开发失衡标准灰狼算法的收敛因子a是从2线性递减到0对应的系数A在[-a,a]之间波动。前一半迭代让狼群大范围跑动后一半迭代收敛到局部精细搜索。线性递减看起来公平但对带障碍的覆盖场景来说有个实际问题前半段探索确实够了可是等收敛因子降到很小的值时种群已经基本锁死在某个局部结构附近。覆盖率函数因为遮挡出现的大量平台会让狼群在平台边缘来回徘徊很难跨过障碍造成的搜索屏障跳到另一片高覆盖区域。我在对比实验里观察到的现象很清楚标准GWO在带两个长方形障碍的场景里60次迭代后覆盖率曲线就基本走平了后面140次迭代几乎在0.5%的范围内抖动。这不是它不想走而是线性递减的收敛因子让它失去了跳出局部的能力。2.3 位置更新缺少“历史记忆”好解一旦丢失就找不回来标准GWO的位置更新只依赖当前种群的alpha、beta、delta三头狼。每一轮迭代alpha狼如果被另一只个体超越原本的位置信息就被丢掉了整个狼群的搜索方向也随之彻底改变。这带来的问题是某只狼在迭代过程中可能偶然拼凑出一个局部很不错的部署方案比如几个节点正好绕过障碍把某条狭窄覆盖带补满。这个方案虽然没有达到全局最优但价值很高。可是下一轮平均化更新之后这只狼的位置被拉向当前三头狼的质心那个偶然的好方案直接被“覆盖”掉再也回不来了。粒子群算法有pbest会保留个体历史最优标准GWO没有这个机制。在普通连续函数上这不算致命但在很多局部极值的障碍遮挡场景里这种“失忆”会让收敛过程产生明显震荡最终结果随机性很大。3. IGWO的三处针对性改进与选型依据3.1 反向学习初始化让第一代狼群就铺满可行区针对随机初始化脆弱的问题我采用反向学习初始化作为第一个改进。反向学习的核心思想一句话对一个随机生成的解X同时构造它的反向解X。如果X的适应度更好就用X进入初始种群否则保留X。反向解的计算方式在二维位置向量上很直观把每一维变量都映射到其取值区间的对称位置。比如某个节点的初始x坐标是15区域范围是[0,100]那反向解里该节点的x坐标就取85。对整个2n维的节点部署向量做同样操作得到一整套相反布局。每对随机解和反向解保留适应度更高的那一个组成初始狼群。实测下来这个操作让初始种群的平均覆盖率提高了3到4个百分点更重要的是初始个体的空间分布更均匀了。因为不管随机个体偏向哪一侧反向个体都会把另一侧补上。障碍物把区域切得越碎反向学习的收益越明显。3.2 余弦型非线性收敛因子把探索资源花在刀刃上第二个改进是把收敛因子a从线性递减改成余弦型非线性衰减。我采用的公式是a 2 * cos(0.5 * pi * t / MaxIt)这里t是当前迭代次数MaxIt是最大迭代次数。迭代初期收敛因子下降速度非常慢狼群的探索范围更大到了中后期收敛因子快速下降种群迅速转入精细开发阶段。选择余弦型而不是指数型主要是从控制和调参的角度考虑。它的两个端点和标准GWO完全一致初始为2结束时为0中间曲线平滑不需要增加额外超参数直接替换原公式即可。对于覆盖率这种多峰地形前期多花一些迭代去确认不同障碍区域之间的覆盖空隙后期再精准填补是收益更高的策略。我在同样场景下跑过对比线性GWO到140代开始走平IGWO到160代还能看到覆盖率上升说明余弦衰减确实延长了有效探索窗口同时后段的收敛速度也没有拖后腿。3.3 差分扰动变异给最差个体一个“跳出去”的机会第三个改进是针对全局最优丢失和后期早熟的原理非常简单每一代找出适应度最差的个体尝试用一个差分变异公式产生候选新解。候选解的计算方式借用了差分进化算法的思想X_new X_alpha F * (X_r1 - X_r2)X_alpha是当前全局最优个体的位置向量X_r1和X_r2是随机抽取的两个其他个体位置F是缩放因子我固定取0.5。这个候选解相当于在全局最优附近又进行了一次跳跃性试探。如果X_new的适应度比原最差个体更好就替换掉它。这个改进思路很直接既然最差的个体对种群贡献有限不如把它当作“探路先锋”每代都向全局最优附近随机探索一次。带障碍场景下很多局部最优和全局最优之间存在明显的“跳跃距离”差分变异这种大跳步操作正好可能一次跳过障碍造成的搜索屏障让种群有机会进入另一片覆盖山谷。3.4 为什么这三处组合在一起而不是引入更多机制做改进最忌讳堆砌。看到很多同类论文又是混沌映射又是高斯变异又是自适应权重改出一大堆计算流程。但工程上每一步改进都应该对应一个确定的问题这样才能定位效果来源。我这套IGWO的组合逻辑非常清晰反向学习解决初始解分布差余弦收敛因子解决探索开发失衡差分扰动解决后期早熟和失去历史好解。三个改进分别针对三个具体短板每一项都可以独立开关。如果读者想验证完全可以只做其中一两项不会出现“全改上了但不知道谁起效”的问题。在实现复杂度上这三处改动加起来大概只增加了三十几行代码计算开销增加不到10%但覆盖率和稳定性提升非常可观属于性价比很高的改进组合。4. 长方形、梯形、三角形障碍的几何建模方法与MATLAB实现4.1 多边形顶点统一约定处理这三种障碍物最关键的是把它们的几何表达统一起来。不管是什么形状我都用一组有序顶点表示格式是一个k×2的矩阵每一行是一个顶点的x、y坐标。长方形顺时针取四个角点梯形取四个顶点三角形取三个顶点。所有障碍物放在一个结构体数组里obs(1).vertices [25 20; 45 20; 45 45; 25 45]; % 长方形仓库 obs(2).vertices [65 15; 88 12; 92 30; 70 42]; % 梯形机台 obs(3).vertices [15 65; 35 72; 20 90]; % 三角形隔断顶点顺序不要求严格但保持一致可以省掉很多调试时间。为了直观检查我把每个障碍物用patch画出来确认没有顶点坐标填错、形状翻转的问题再进主程序。4.2 线段-多边形相交判定的核心函数遮挡判定的基础是两条线段是否相交。这里用向量叉积实现判断速度快也没有角度计算稳定可靠。function inter segIntersect(p1, p2, p3, p4) % 线段 p1p2 与 p3p4 是否相交含端点接触 d1 cross2(p3 - p1, p2 - p1); d2 cross2(p4 - p1, p2 - p1); d3 cross2(p1 - p3, p4 - p3); d4 cross2(p2 - p3, p4 - p3); inter (d1 * d2 1e-10) (d3 * d4 1e-10); end function c cross2(a, b) c a(1) * b(2) - a(2) * b(1); end有了这条基础函数判断传感器到网格点是否被某个障碍物遮挡就简单了把传感器坐标和网格坐标连成一条线段再和障碍物多边形的每条边依次做相交判断任意一条边相交就判定为遮挡。function blocked isBlocked(sensorPos, gridPos, obs) blocked false; for k 1:length(obs) v obs(k).vertices; m size(v, 1); for j 1:m p3 v(j, :); p4 v(mod(j, m) 1, :); if segIntersect(sensorPos, gridPos, p3, p4) blocked true; return; end end end end注意这个函数默认传感器和网格点都不在障碍物内部。实际工程中传感器位置通过约束处理保证合法网格点则提前用inpolygon把障碍物内部的点排除掉所以不会出现“线段整个待在障碍物内部但恰好不穿边界”的漏判情况。4.3 三种障碍物叠加时的判定顺序场景里同时有长方形、梯形、三角形时对每个候选网格点都需要遍历所有障碍物。因为三种障碍物统一成了多边形顶点数组这段代码对三种形状一视同仁不需要为长方形写一套、梯形再写一套。不过在多个障碍物离得很近时要特别留意“连续遮挡”的场景。比如传感器在左边网格点在右边中间依次穿过了一个长方形和一个三角形。只要线段和第一个障碍物相交就被判定遮挡直接返回不会继续判断后面的障碍物这样既节省时间也符合逻辑穿过任意一个就不行不需要知道它穿过了几个。4.4 边界与擦边情况的处理选择线段恰好擦过障碍物顶点或者沿着边界走算不算遮挡我在实现里选择了严格相交擦过也算遮挡。因为0/1覆盖模型本身是离散化的网格点步长1的情况下这种擦边情况影响的范围很小而且偏保守的判定不会产生“透过墙角看到信号”这种违反直觉的结果。同样的规则也适用于点在多边形边界上的情况。inpolygon函数默认将边界点归为多边形内部这意味着障碍物边沿的网格点会被直接从可行区域里剔除。我的处理是从众的边界点一律按不可用处理。如果某些场景允许传感器贴在障碍物边缘部署可以在代码里给边界点单独开一条容差分支但我的实验里不需要这种精细边界所以没有加。5. 覆盖率评估与代码向量化复现性能的关键5.1 直接双重循环为什么跑不动很多第一次做这类复现的朋友会把覆盖率评估写成三重循环遍历种群个体、遍历节点、遍历网格点。这在网格点数少时尚可忍受但放到100×100区域、30个节点、30个种群个体、200代迭代的场景里计算量就完全失控了。我做过一次粗略统计30个个体、每个个体30个节点、每个节点要算101×101个网格点的距离和遮挡单是一代的计算量就有数千万次几何判断。如果不做任何加速一次实验跑十几分钟甚至更久完全没法调参。所以覆盖率部分的代码必须围绕“减少几何判断次数”来设计。核心思路是先粗筛、后精判。5.2 第一层加速距离矩阵快筛对每个个体先把节点坐标拆出来用向量化方式同时计算所有节点到所有网格点的距离function [covRate, covMap] calcCoverage(individual, model) gx model.gx; % 所有网格点x坐标 gy model.gy; % 所有网格点y坐标 mask model.freeMask; % 可行区域掩码 sensPos reshape(individual, model.nSensors, 2); covMap false(size(gx)); for i 1:model.nSensors dist2 (gx - sensPos(i, 1)).^2 (gy - sensPos(i, 2)).^2; candidate (dist2 model.Rs^2) mask; idx find(candidate); for j 1:length(idx) if ~isBlocked(sensPos(i, :), [gx(idx(j)), gy(idx(j))], model.obs) covMap(idx(j)) true; end end end covRate sum(covMap) / sum(mask);这一步最关键的优化是距离计算全部向量化不再用双层循环。而真正的遮挡检测只对距离小于等于Rs的候选点进行。在Rs12、节点密度适中的场景里每个节点需要做遮挡检测的候选点数量只有几百个比直接对全部一万个网格点做几何判断省了十几倍计算量。5.3 第二层加速候选点遮挡检测的批处理思路候选点遮挡检测仍然还有循环但已经小到可以接受。有一个可选的进一步加速思路把某个节点的所有候选点坐标都组装成数组一次性计算它们与传感器坐标的向量再利用矩阵运算对多个网格点同时做叉积判断。不过我实测下来在100×100网格规模下现有方案已经能在合理时间内完成实验。继续往深做批量向量化代码可读性会变差而且如果网格步长进一步缩小到0.5性能瓶颈会转移到inpolygon和内存占用上单纯优化遮挡检测意义不大。工程实现讲究够用就好没必要为极限性能牺牲可维护性。5.4 主流程与可视化主程序流程是初始化参数、构造障碍物结构体、生成网格和可行区域掩码、初始化种群并评估、进入IGWO迭代、记录每一代最优覆盖率、绘制部署图和覆盖热力图。热力图绘制我推荐用imagesc配合适当的colormapimagesc(model.X, model.Y, covMap); hold on; plot(sensPos(:,1), sensPos(:,2), r^, MarkerSize, 8); axis equal tight;把所有传感器节点画成红色三角标记叠在覆盖热力图上面看一眼就知道节点有没有分散到障碍物周围的空隙区域。这个可视化是整个复现最直观的调试工具覆盖率数字只是结果热力图能告诉你算法做得好不好。6. 实验设计与结果解读IGWO到底强在哪里6.1 场景设计与参数配置我的模拟实验固定区域为100×100网格步长1传感器节点数30感知半径Rs12种群规模30迭代上限200每个条件独立运行20次取统计结果。三个场景设计如下场景A两个长方形障碍分别模拟仓库和厂房隔断场景B一个长方形、一个梯形障碍模拟仓库加上不规则设备区场景C长方形、梯形、三角形各一个模拟混杂遮挡的复杂部署环境6.2 覆盖率统计结果对比20次独立运行的平均覆盖率数据如下场景GWO平均GWO最优IGWO平均IGWO最优平均提升场景A86.3%89.7%93.1%95.2%6.8%场景B82.7%86.4%91.4%94.0%8.7%场景C78.9%83.5%89.6%93.1%10.7%场景越复杂、障碍物种类越多IGWO相对标准GWO的提升越大。这个趋势很符合预期因为障碍物越多目标函数中的局部最优就越多初始化质量和跳出局部的能力就越重要。6.3 收敛曲线与稳定性分析看收敛曲线能发现另一个有意思的细节标准GWO在场景C里往往前40代冲得很快一度和IGWO差距很小但到了80代以后就几乎完全停滞最终稳定在低位。IGWO虽然早期略慢但中段有一个持续的爬升过程曲线更平滑没有明显回退。这正好对应前面说的三个改进点的分工。反向学习让IGWO的开局不一定比GWO高很多但分布更合理余弦收敛因子让中段搜索持续更久差分变异让最差个体持续贡献扰动帮助种群跳出局部极值。标准差数据上IGWO在20次运行中的覆盖率标准差约为1.2到1.8个百分点标准GWO则在2.5到4个百分点之间。这说明IGWO不只“偶尔跑得好”而是整体更稳定这对部署方案复现来说非常关键因为现场工程不可能反复跑几十次取运气最好的那次结果。6.4 一个容易被忽略的提醒无障碍场景下IGWO优势没那么大我也在完全无障碍的空白区域里跑过同样的对比结果IGWO平均只比GWO高2个百分点左右。这说明改进算法不是免费的“全场景通用提升器”它是针对带障碍覆盖问题的特殊地形做了针对性设计。如果读者用无障碍场景验证IGWO很可能得出“改进效果不明显”的结论。我会建议在实验设计里明确区分场景最好用带障碍场景展示算法优势再补一组无障碍场景说明算法没有明显退化这样结论才严谨。7. 复现过程中最值得注意的六个坑7.1 覆盖率分母口径不统一我最早的一个版本把障碍物内部的网格点也计入分母导致所有算法的覆盖率都比别人论文里的数值低不少。后来才反应过来不同文献对“覆盖率”的分母定义并不一致有的用全部网格点有的用可行区域网格点。这不是小事。同一个部署方案两种口径下覆盖率可能差十个百分点以上。写文章、做表格之前先明确自己的分母口径并且在对比实验里保持完全一致。7.2 位置更新后节点落进障碍物内部灰狼算法的位置更新是连续向量运算更新后的节点坐标可能直接落在障碍物内部。如果不加处理直接用这个节点会被当成“放置在障碍物里”后续遮挡检测的结果完全失真。我的做法是在位置更新之后增加一个修复函数用inpolygon检查每个节点是否落入任意障碍物内一旦发现问题就把它重新随机生成到可行区域内。这个随机重生成虽然会丢失一点位置信息但单个节点的问题对整体个体影响有限简单可靠优先。7.3 感知半径和通信半径混着用有些人会把传感器节点的通信半径当成覆盖半径做优化逻辑是“节点互相连起来了不就覆盖了吗”。但覆盖优化关注的是感知覆盖通信半径是网络连通性问题。两者满足Rs≤Rc是基本前提但优化目标应该严格用感知半径Rs计算覆盖范围。混用半径的结果是覆盖率虚高部署可视化看起来一片红实际感知空洞根本没被填上。这个坑特别隐蔽因为数值上能跑通也不报错但结论毫无意义。7.4 随机种子与统计次数不够灰狼算法和反向学习初始化都依赖随机数。只跑一次实验覆盖率可能比平均值高五个点或者低五个点差异巨大。我的习惯是每组实验固定同一个随机种子集合跑20次以上记录平均值、标准差、最优值三项指标。对比算法时使用相同的初始种子虽然不能完全消除随机性但能显著降低不公平性。7.5 inpolygon边界归属带来的边缘效应MATLAB的inpolygon判断点在多边形内时默认边界上的点算作内部。这会导致障碍物边沿的网格点被排除形成一圈“不可用的边界带”。网格步长越小这个边界带越细影响越小。如果场景要求传感器可以贴着障碍物部署就要考虑把边界点单独处理或者给inpolygon设置一个合理容差。我的实验中不需要这种贴墙部署所以直接排除了边界点但这一定要在文章方法部分写明白否则审稿人会揪着不放。7.6 网格步长1并不适用于所有场景网格步长1在100×100区域、Rs12的配置下精度和速度是平衡的。但如果感知半径很小比如Rs只有3步长1就会造成严重的离散化误差覆盖率计算结果和连续解相差巨大。遇到小半径场景建议把网格步长缩到0.2到0.5或者直接增大感知半径再调参。覆盖率仿真的本质是用离散采样逼近连续问题步长选择应该让每个感知圆盘内至少有几十个网格采样点这个底线不能破。我自己做这个复现项目时最深的体会是模板化的覆盖优化看起来简单真正难的是把几何判定、算法改进和工程加速三件事拧在一起。如果以后你要在类似场景里做优化我建议把节点部署和路线规划类问题区分开前者本质是连续坐标搜索后者是组合优化两者的算法评价标准完全不一样。上面这些经验希望帮你少踩几次遮挡判定和覆盖率口径的坑。
阅读完成 · 觉得有帮助？
