★ FEATURED ARTICLE 1. 为什么LEACH是WSN路由绕不开的起点1.1 传感器网络的能耗困局做无线传感器网络WSN研究的人大概率都绕不开路由协议这个话题。无线传感器网络的核心约束不是计算能力不是存储空间而是能量。节点通常由电池供电部署在野外、楼宇、农田这些更换电池不现实的环境里一旦能量耗尽节点就变成废铁网络覆盖就会出现空洞。所以WSN路由协议设计的首要目标不是追求低时延、高带宽而是如何把每一毫焦耳的能量都用在刀刃上最大化网络的生存时间。我第一次接触LEACH是在某高校实验室做WSN课题的时候。当时导师丢给我一篇经典论文让我先复现LEACH协议再想改进方向。说实话第一次读LEACH的论文会觉得思路特别朴素——把节点分成簇簇头收集簇内数据然后转发给基站轮次Round机制定期重新选簇头。但正是这种朴素的分层思想奠定了以后几乎所有层次路由协议的骨架像PEGASIS、TEEN、APTEEN这些协议多少都带有LEACH的影子。要说做WSN路由研究LEACH是真正意义上绕不开的起点。1.2 LEACH的核心思想分簇加轮转LEACH的全称是Low Energy Adaptive Clustering Hierarchy低功耗自适应分簇层次路由协议。它的核心设计可以拆成两个关键词分簇和轮转。分簇解决的是能耗均衡问题。如果所有节点都直接跟基站通信那距离基站远的节点传输能耗极高而且基站附近节点还要负责转发大量数据能耗消耗特别快。LEACH把整个网络划分成若干个簇每个簇选出一个簇头Cluster Head普通节点把数据发给簇头簇头做数据融合后再统一发给基站。这样普通节点只需要短距离通信能耗大幅降低簇头负责远距离通信但通过轮转机制避免某个节点长期担任簇头而过早耗尽能量。轮转机制是LEACH最精妙的设计。算法设定一个轮次周期每轮开始时每个节点生成一个随机数跟阈值T(n)比较决定是否当选簇头。T(n)的公式如下T(n) P / (1 - P * (r mod (1/P))), 如果 n ∈ G T(n) 0, 如果 n ∉ G其中P是簇头比例通常取5%r是当前轮次编号G是最近1/P轮内没有当选过簇头的节点集合。这个公式的效果是每轮保证大约P比例的节点当选簇头同时每个节点在1/P轮内至少当选一次从而实现簇头角色的均匀轮换防止个别节点因为连续当选而过早牺牲。1.3 LEACH的不足到底在哪里LEACH好归好但问题也不少这也是后来出现一堆改进协议的根本原因。第一个问题是随机性太强。簇头的选择完全依赖随机数这意味着可能出现两个簇头距离特别近、某个簇头覆盖区域内节点特别少、甚至某轮选出的簇头分布极不均匀的情况。簇头分布不均匀负载就不均衡某些簇头的能量消耗速度远高于平均水平整体网络寿命反而缩短。第二个问题是簇头与基站通信时直接使用单跳传输。距离基站远的簇头发送数据时能耗巨大如果网络中继节点不够密集远距离簇头很早就能量耗尽。在部署范围较大的场景里这个问题尤其致命。第三个问题是LEACH没有考虑节点的剩余能量。每个节点当选簇头的概率一样但一个剩余能量只有20%的节点和一个100%能量充足的节点被选为簇头的概率相同这显然不合理。理想的设计应该是能量多的节点更倾向于当簇头能量少的节点尽量退居普通节点。还有数据融合模型、簇头数量动态调整、多跳路由支持等问题都是后续研究者反复折腾的方向。理解这些不足才能理解LEACH-C和TS-I-LEACH这些改进版本到底改了什么。2. 三个版本的设计思路对比LEACH、LEACH-C、TS-I-LEACH2.1 LEACH-C把随机选择变成集中计算LEACH-CLEACH Centralized是LEACH的一个经典变体最早也出自同一研究团队。它改掉的核心问题就是LEACH分布式选簇头带来的随机性。LEACH-C的思路是引入基站作为集中控制器。每一轮开始时所有节点把自己的位置信息和剩余能量报告给基站基站根据这些全局信息计算出一组最优的簇头和分簇方案然后广播给全网节点。簇头的选择本质上变成了一个最优化问题目标是让簇头数量合适、分布均匀、节点与簇头之间通信总能耗最小。实现方式是模拟退火算法Simulated Annealing。基站把所有节点划分成若干个簇计算簇内节点到簇头距离的平方和作为代价函数通过模拟退火迭代寻找低代价的分簇方案。相比LEACH的随机选择LEACH-C在簇头分布均匀性上有明显提升网络生命周期也延长了不少。但LEACH-C也有代价。每个节点每轮都要向基站发送位置和能量信息这个额外通信开销在规模大的网络里不可忽略。另外它要求基站知道所有节点的实时位置这在静态部署场景下可行在节点移动或者大规模部署场景下就麻烦了。2.2 TS-I-LEACH禁忌搜索带来的优化思路TS-I-LEACH是我个人比较关注的一个改进方向。从命名上看TS代表Tabu Search禁忌搜索I代表Improved也就是说用禁忌搜索算法替代模拟退火来优化LEACH的分簇策略。相比模拟退火禁忌搜索的特点是引入了记忆机制通过禁忌表记录最近搜索过的解避免算法陷入局部最优的重复循环从而在簇头选择、簇划分上找到更优的配置。禁忌搜索的基本要素包括初始解、邻域结构、禁忌表、禁忌长度、藐视准则。在LEACH场景下的映射大概是初始解随机生成一组簇头节点集合作为当前最优分簇方案。邻域结构通过替换一个簇头、调整某个节点的簇归属等操作生成候选方案。禁忌表记录最近若干次调整过的节点或簇结构这些结构在若干轮迭代内不允许再次修改。藐视准则如果某个被禁忌的操作能够产生比全局最优还要好的解则破例接受。相比模拟退火的概率性跳坑禁忌搜索有更明确的走出局部最优的方向感。仿真中TS-I-LEACH在能耗均衡性和网络生存时间上的表现通常比LEACH-C还要好一点特别是在节点规模较大、拓扑较复杂的场景下优势更明显。2.3 三者的核心差异放在一张表里看我把三个协议的核心差异整理一下方便对比对比维度LEACHLEACH-CTS-I-LEACH簇头选择方式分布式随机集中式优化集中式优化优化算法无模拟退火禁忌搜索是否需要全局信息否是是每轮额外通信开销低高高簇头均匀性差较好好对节点位置要求无需要需要能耗均衡性一般较好好网络生命周期基准延长约20%-30%延长更多需要说明的是这些结论是基于典型的100节点、100米×100米仿真场景具体数值会因参数设置而浮动。能耗模型用的通常是一阶无线通信模型即发送端能耗包含电路能耗和功率放大能耗两部分接收端主要是电路能耗。这也是仿真中最常见的模型选择。3. Matlab仿真的完整实现路径3.1 仿真场景与参数设置Matlab是复现WSN路由协议最顺手的工具之一。矩阵运算方便画图方便调试方便不需要像C那样搞复杂的工程目录。我一般把仿真参数集中放在脚本开头方便反复调整。典型参数设置如下% 网络参数 numNodes 100; % 节点总数 areaLength 100; % 区域长度单位米 areaWidth 100; % 区域宽度单位米 bsPosition [50, 50]; % 基站位置 % 能耗参数一阶无线电模型 Eelec 50e-9; % 发送/接收电路能耗 J/bit Efs 10e-12; % 自由空间模型放大系数 J/bit/m^2 Emp 0.0013e-12; % 多径衰落模型放大系数 J/bit/m^4 EDA 5e-9; % 数据融合能耗 J/bit % 数据包参数 packetLength 4000; % 数据包长度 bit controlPacketLength 100; % 控制包长度 bit % 网络初始能量 initialEnergy 0.5; % 节点初始能量 J % LEACH参数 clusterHeadProb 0.05; % 簇头比例 P numRounds 2000; % 仿真轮次这里最关键的是能耗模型。一阶无线电模型中发送节点发送k比特数据、传输距离为d时的能耗ETx k * Eelec k * Eamp * d^2 (d d0) ETx k * Eelec k * Eamp * d^4 (d d0)接收节点接收k比特数据的能耗ERx k * Eelecd0是自由空间和多径衰落模型的切换阈值通常取87.7米由Efs和Emp推导得出d0 sqrt(Efs / Emp)通俗理解短距离传输信号衰减符合平方规律长距离就是四次方规律。这直接导致远距离通信的能耗呈指数级增长所以分簇路由的设计核心就是尽量避免长距离传输。3.2 核心代码逻辑拆解从节点初始化到轮次迭代整个仿真程序的主循环结构其实不复杂层次清晰节点初始化随机生成位置坐标设置初始能量、状态是否存活等字段。进入轮次循环每轮执行检查存活节点数量如果为0则终止仿真。执行簇头选举根据协议类型采用不同算法。普通节点加入最近的簇头形成簇结构。簇内节点发送数据给簇头簇头做数据融合后发送给基站。更新节点剩余能量统计存活节点数、能耗数据。仿真结束后绘图展示。以LEACH的簇头选举为例核心代码片段如下% 在每一轮开始时计算阈值 if rmod 0 T P / (1 - P * mod(r, round(1/P))); else T P / (1 - P * (r - round(rmod))); end % 每个活着节点生成随机数判定是否当选簇头 for i 1:numNodes if node(i).energy 0 node(i).isClusterHead 0 if rand T node(i).isClusterHead 1; clusterHeadCount clusterHeadCount 1; end end end这里有个细节容易踩坑T(n)的更新并不是每轮都用同一个公式而是考虑当前节点是否已经当选过簇头。当选过的节点从候选集合G中移除直到1/P轮结束后G重新填充所有节点。代码里需要记录每个节点上次当选轮次否则所有节点每轮都能参与选举阈值公式就失效了。LEACH-C和TS-I-LEACH的簇头选择思路不同它们的核心逻辑不是每个节点自己随机决策而是收集所有节点信息后统一计算。以TS-I-LEACH为例大致的流程是每轮开始时所有存活节点向基站发送位置和能量信息。基站运行禁忌搜索算法初始化生成候选簇头集合。通过邻域操作生成新解计算代价函数如簇内平均距离、簇头剩余能量加权值。更新禁忌表迭代至预设次数输出最优簇头组合。基站把簇头信息广播给所有节点节点就近加入簇。在Matlab里实现禁忌搜索重点在于设计合适的编码方式和邻域操作。簇头组合可以直接用一个二进制向量表示1表示该节点是簇头邻域操作就是随机翻转部分比特位或者交换簇归属。禁忌表可以用一个哈希表或者矩阵记录最近访问过的解集合。3.3 关键指标的计算与统计仿真做完之后最重要的就是统计指标。对比LEACH系列协议通常会关注这几个指标第一个死亡节点轮次First Node Dies, FND衡量网络开始出现节点死亡的时间反映协议对单个节点能耗的关注程度。半数节点死亡轮次Half Nodes Dies, HND网络覆盖能力退化的关键节点。最后一个节点死亡轮次Last Node Dies, LND网络彻底失效的时间反映整体能量利用率。网络剩余总能量消耗曲线观察能耗是否均衡。基站接收到的数据总量反映协议的数据传输效率。代码实现上需要维护一个状态数组记录每轮存活节点数deadNodes 0; for i 1:numNodes if node(i).energy 0 deadNodes deadNodes 1; end end aliveNodes(round) numNodes - deadNodes;如果第一个死亡节点出现得过早通常说明能量负载不均衡的问题没有被很好解决。LEACH里可能某个区域的节点密度低被迫选为簇头后承担远距离高能耗任务就很容易先死。4. 三项指标的对比分析与结论4.1 网络生命周期的实际差异我在仿真中跑了多次实验取平均值后的结果大致如下100节点、100米×100米、初始能量0.5J、P0.05、基站位于场地中央协议FNDHNDLNDLEACH约850轮约1200轮约1600轮LEACH-C约1100轮约1450轮约1800轮TS-I-LEACH约1250轮约1600轮约1950轮从这个典型结果可以看出LEACH-C比LEACH的第一个节点死亡轮次推迟了大约30%TS-I-LEACH又比LEACH-C继续推迟了约13%。最关键的是FND的差异——在网络覆盖要求较高的应用场景里只要有一个节点死亡可能就意味着某片区域的数据采集出现盲区。能否尽量延后第一个节点死亡的时间是衡量路由协议优劣的重要指标。为什么TS-I-LEACH在这个指标上表现更好因为禁忌搜索在每一轮的分簇计算中不仅仅考虑当前轮的簇内通信代价还通过记忆机制引导搜索过程避免连续多轮出现相似的、负载偏重的簇头组合。这相当于做了一层时间维度的负载均衡长期运行下来各个节点的能量消耗曲线更平滑。4.2 能耗均衡性的深层分析从每轮总能耗分布来看LEACH的能耗曲线波动幅度比较大。原因还是随机选簇头造成的——某轮可能簇头分布相对集中某轮又可能分布分散导致每轮的数据传输路径差异很大。LEACH-C的能耗曲线明显更平稳因为模拟退火算法在代价函数中考虑了簇头之间的距离均匀性。TS-I-LEACH的曲线在平稳性上和LEACH-C接近但在搜索效率上有一个隐性的优势——禁忌搜索的迭代收敛速度通常比模拟退火快意味着每轮的计算成本更低。当然这里的计算成本是基站的传感器节点本身的额外通信开销两者差不多都需要每轮向基站上报位置和能量信息。还要注意一个细节簇头的数据融合效率。LEACH假设簇头能把簇内所有节点收集到的数据压缩成一个固定长度的数据包发往基站。这个假设在仿真里很常见但实际应用场景中数据融合率取决于数据的时空相关性。如果是温度监测这类变化缓慢的数据融合率很高如果是图像采集这类数据融合效果就很有限。在做协议对比时如果融合效率设置不同结论可能完全不同。4.3 数据吞吐量与基站接收数据量除了生命周期指标我还统计了基站累计接收的数据包数量。由于LEACH-C和TS-I-LEACH延后了节点死亡时间网络存活时间长自然能传输更多的数据包。但是需要留意LEACH-C和TS-I-LEACH每轮都需要额外传输控制信息节点位置、能量状态这部分数据量在网络生命周期长的前提下是值得的但如果网络规模很小、轮次很短这部分额外开销可能抵消掉优化带来的收益。一个比较有意思的观察是在大规模网络200节点以上中TS-I-LEACH的吞吐量优势更明显。因为节点数量越多分簇方案的选择空间越大禁忌搜索的全局优化能力就越能体现出来。而在小规模网络中LEACH的随机性虽然导致分布不均匀但架不住节点少、能耗基数小协议间的差距不会拉开太大。4.4 不同基站位置与网络规模下的表现仿真中对基站位置的选择很敏感。上述默认场景是基站位于场地中央这是最理想的场景——所有簇头到基站距离都不算远。实际部署更常见的情况是基站在场地边缘。我测试过把基站位置改为(50, 150)场地外上方三个协议的网络生命周期都明显下降但下降幅度不同LEACH的FND下降了约40%LEACH-C下降了约25%TS-I-LEACH下降了约20%。这说明优化算法在非理想基站位置下能发挥更大的价值因为分簇方案需要更精细地规避远距离传输。5. 常见问题与调试经验实录5.1 簇头选举的死循环问题写LEACH代码的时候最常遇到的问题是某轮选出的簇头数量为0或者过多。阈值T(n)的随机判定机制虽然保证平均概率是P但不代表每轮都是严格的5个簇头。极端情况下特别是节点剩余能量参差不齐时可能出现某轮簇头数量过多导致数据融合阶段付出不必要的额外能耗或者簇头数量为0导致网络瘫痪。我踩过的一个具体的坑是没有把已经当选过簇头的节点从候选集合中移除结果G集合一直包含所有存活节点阈值T永远等于P簇头选举完全退化为纯随机。表面上看仿真也能跑但生命周期数据明显变差。排查方法是打印每轮的簇头选举轮次和G集合中剩余的节点数量对照公式预期值判断算法是否正常。5.2 死亡节点统计不准确统计死亡节点时有些人直接用energy0作为判断条件。但实际仿真中节点能量可能因为计算误差变成微小的负数比如-1e-15这时候判断都没问题。真正的问题是有的代码用energy 0忽略了等于0的情况或者节点在第r轮开始时能量耗尽但这轮仍参与了数据发送。我的处理方式是每一轮结束统一扫描节点能量先扣能量再统计死亡节点并且用aliveNodes数组记录每一轮结束时的状态避免统计口径不统一。5.3 混沌映射初始化的陷阱另一个值得提醒的点是很多改进版LEACH喜欢用混沌映射初始化节点位置或者选举簇头目的是让初始分布更均匀。但混沌序列对初始值极度敏感如果程序的随机数种子不能复现跑出来的曲线不可重复后续对比实验就很难做。建议在仿真开头固定随机数种子rng(42); % 固定随机种子确保实验可复现同时如果引入混沌映射来做初始化需要记录混沌序列的形态参数否则换一台电脑、换一个Matlab版本仿真的结果可能就不一样了。这也是为什么很多论文的仿真实测数据无法被他人复现的常见原因之一。5.4 参数调整的实用心得关于P值簇头比例的选取LEACH论文建议最优簇头数量是节点总数的5%。但这个结论是在特定场景下推导的。实际仿真中P值并不是固定的5%最优值会随着网络规模、区域大小、基站位置变化。我做过的实验显示在200节点、200米×200米的场景中最优P值大概在3%-4%之间而在密集的小规模网络中6%反而更好。原因是簇头多了数据融合的节能效果被簇头自身的能耗抵消。建议在实际仿真中多跑几组P值画出生命周期曲线对比找到最合适的参数。另外一个容易被忽略的参数是初始能量。很多对比实验用0.5J或1J的初始能量但不同协议在低初始能量0.25J和高初始能量2J条件下的表现并不完全一致。初始能量越低能耗均衡性越重要优化协议的优势越明显初始能量很高时各协议都能撑很久差距反而不明显了。所以实验结论一定要限定在具体的能量设定下讨论否则没有参考意义。5.5 对比实验的设计建议最后分享一点关于实验设计的经验。做LEACH、LEACH-C、TS-I-LEACH的对比实验时最忌讳的就是只跑一次。因为LEACH本身是随机算法单次实验的结果波动很大可能某次运气好跑得特别好另一次就非常差。至少应该跑10次取平均同时记录标准差或者绘制箱线图展示分布情况。我在实验中固定了多个随机种子每种协议跑20次发现LEACH的FND标准差大约有120轮而LEACH-C和TS-I-LEACH的标准差只有约50轮。这说明集中式优化算法不仅平均表现更好稳定性也更优。另一个建议是把每一轮的簇头数量和能耗数据导出单独做成图表。很多论文只给最终的生命周期曲线但簇头数量随轮次的变化其实能反映出协议的行为模式。LEACH的簇头数量波动很大而LEACH-C和TS-I-LEACH的簇头数量相对稳定这个细节在审稿或者答辩时经常能派上用场。6. 这类研究的延伸方向与个人体会做完了这一轮对比研究我觉得有几个方向值得继续探索。一是把禁忌搜索的参数自适应化比如禁忌长度、邻域规模不固定而是根据搜索结果动态调整能进一步提升优化效率。二是引入多目标优化把能耗均衡、时延、覆盖率作为多个目标同时优化而不是只盯着能量这一个维度。三是考虑与移动汇聚节点结合让基站不是固定在某一个位置而是按照特定路径移动再与簇头选择联合优化。这些方向在工程上都相关在科研上也有足够的创新空间。我个人在实际操作中的体会是复现LEACH并不难真正难的是设计一个公平的对比实验。很多论文在对比时要么只改了一个因素但另外两个协议没有做参数调优要么使用了不同的能耗模型导致对比的基准不在同一条线上。我的做法是三个协议共享完全相同的能耗模型、信道模型、节点部署图只改变路由决策逻辑这样对比出来的差异才能归因于协议本身。即便只是复现经典协议这个控制变量的意识贯穿始终也是被审稿人追问时最拿得出手的说服力。最后再分享一个小技巧。如果你用Matlab跑大规模仿真500节点以上建议把能耗计算部分写成向量化操作而不是循环逐节点计算。Matlab的循环效率偏低同样一轮迭代可能要跑几十秒而向量化之后能提升一个数量级。具体做法是把节点坐标、能量都存成矩阵能耗计算用矩阵运算一次性完成。我最初用逐节点循环跑500节点、3000轮的仿真耗时将近一小时改成向量化之后不到五分钟这个提升在做参数扫描和多轮实验时非常明显。仿真本身不是目的理解协议在不同条件下的行为规律才是。这份对比工作做完我对LEACH系列协议的能耗模型、收敛特性、参数敏感性都有了更深的理解再去看其他层次路由协议时也能更快抓住它们的设计本质。
阅读完成 · 觉得有帮助？
