无线传感网络高能效路由算法的研究与实现

V无线传感网络高能路由算法的研究与实现摘要无线传感网络是由大量分布式传感器节点组成的网络，用于采集、处理和传输环境中的各种信息。通过进行高能路由算法的设计可以有效地减少传感器节点之间的能量消耗，延长网络的寿命。通过合理地选择传输路径、降低传输功率和优化节点的活动策略，可以最大限度地减少能量消耗，提高网络的能效性能。在本文中通过使用基于贪心策略的dijtstra算法与基于动态规划策略的floyd算法，bellman-ford算法，实验结合多个影响因素建立了新的评价指标S&Cbalance。对无限传感网络高能路由的课题进行了研究，同时进行了对dijtstra算法的优化，完成了在不同算法下对无线传感网络能耗分析模型的实现。在模型中完成了随即状态下路由节点的生成，通过范围感知函数实现了基于圆形感测半径下节点连通性的自动感测连接，通过邻接矩阵与结构体对节点联通信息进行了存储，将应用于最短路径领域的dijtstra，bellman-ford,floyd算法通过能量消耗公式应用于最少能耗问题的分析。通过算法模型的搭建，完成了不同算法在无限传感网络中的性能比较，同时通过对dijtstra算法的优化，结合S&Cbalance的反映，成功提升了原有算法的性能，分析了不同算法在无限传感网络中的表现，对算法的稳定性进行了探究。结合实验结果对不同算法进行了可视化，全方位详细分析了不同算法的区别与优化前后的对比，同时对后续的深度探讨提出了建议。关键词：无线传感网络，dijtstra，bellman-ford，floyd，wsns能耗，节点寿命优化ResearchandImplementationofHighEnergyRoutingAlgorithmforWirelessSensorNetworksAbstractWirelesssensornetworkisanetworkconsistingofalargenumberofdistributedsensornodesforcollecting,processingandtransmittingvariousinformationfromtheenvironment.Thedesignofhighenergyroutingalgorithmcanbecarriedouttoeffectivelyreducetheenergyconsumptionamongsensornodesandextendthelifetimeofthenetwork.Theenergyconsumptioncanbeminimizedandtheenergyefficientperformanceofthenetworkcanbeimprovedbychoosingthetransmissionpathsrationally,reducingthetransmissionpowerandoptimizingtheactivitystrategyofthenodes.Inthispaperbyusingthedijtstraalgorithmbasedongreedystrategyandfloydalgorithmbasedondynamicplanningstrategy,bellman-fordalgorithm,experimentscombinedwithanumberofinfluencingfactorstoestablishanewevaluationindexS&Cbalance.thesubjectofhigh-energyroutingofinfinitesensingnetworkshasbeenresearched,andatthesametimetheoptimizationofthedijtstraalgorithmhasbeencarriedout,andtheimplementationofamodelforanalyzingtheenergyconsumptionofwirelesssensornetworksunderdifferentalgorithmshasbeencompleted.Theimplementationoftheenergyconsumptionanalysismodelofwirelesssensornetworksunderdifferentalgorithmsiscompleted.Inthemodel,thegenerationofroutingnodesintheimmediatestateisaccomplished,theautomaticsensingofnodeconnectivitybasedoncircularsensingradiusisrealizedbyrange-awarefunction,thenodeconnectivityinformationisstoredbyadjacencymatrixandstructure,andthealgorithmsofdijtstra,bellman-ford,andfloyd,whichareappliedinthefieldofshortestpaths,areappliedtotheanalysisoftheleastenergyconsumptionproblembyusingenergyconsumptionformulas.energyconsumptionproblemanalysis.Throughtheconstructionofthealgorithmmodel,theperformancecomparisonofdifferentalgorithmsintheinfinitesensingnetworkiscompleted,andatthesametime,throughtheoptimizationofthedijtstraalgorithm,combinedwiththereflectionoftheS&Cbalance,itsuccessfullyimprovestheperformanceoftheoriginalalgorithm,analyzestheperformanceofdifferentalgorithmsintheinfinitesensingnetwork,andexploresthestabilityofthealgorithm.Combinedwiththeexperimentalresultsofthedifferentalgorithmsarevisualized,thedifferencesbetweenthedifferentalgorithmsandthecomparisonbeforeandafteroptimizationareanalyzedindetailinanall-roundway,andsuggestionsarealsomadeforthesubsequentin-depthexploration.Keywords:dijtstra，bellman-ford，floyd，Nodelifetimeoptimization,Energyconsumptionanalysis目录TOC\o"1-3"\u摘要 IAbstract II第1章绪论 11.1 课题背景 11.2目的与意义 21.3论文研究主要内容 21.4国内外研究现状 3第2章算法基本原理介绍 42.1问题提出 42.2算法描述 42.2.1dijtstra算法描述 42.2.2bellman-ford算法描述 52.2.3floyd算法描述 62.3算法流程图 72.3.1dijtstra算法流程图 72.3.2bellman-ford算法流程图 82.3.3floyd算法描流程图 92.4本章小节 10第3章最短路径算法在无线传感网络中的应用及改进策略 113.1问题提出 113.2算法应用场景改进 113.2.1节点调整优化策略 113.2.2算法调整优化策略 123.2.3评价指标改进 123.3算法优化策略 123.4本章总结 13第4章算法模型概述 154.1路由节点及sink节点的生成与连通性感知 154.1.1node_generation节点生成模块 154.1.2range_detection节点自动感测模块 154.2算法核心部分概述 164.2.1dijtstra算法的实现 164.2.2bellman-ford算法的实现 174.2.3bellman-ford算法的实现 184.2.4dijtstra_new算法的实现（优化模块） 194.3路径路径存储及能量转化 204.3.1putout函数（floyd最优路径存储） 204.3.2printf_path函数与print函数 21第5章评价指标构建 225.1生存能耗平衡性指标的创建思路（Survivalenergyconsumptionbalanceindex） 225.2先遣评价指标的归一化处理 225.2.1线性归一化的优势 225.2.2线性归一化的应用 235.3通过层次分析法对归一化后的指标进行权重分配 235.3.1层次分析法的介绍 235.3.2成对比较矩阵的构建 235.3.3层次分析法运行结果与一致性检验 245.3.4S&Cbalance的构建 25第6章实验分析 266.1数据准备 266.2不同实验的数据对比 286.2.1FDT时刻不同算法能耗对比 286.2.2FDT时刻不同算法节点平均剩余能量对比 286.2.3不同算法出现FDT轮次对比 296.3算法优化前后对比实验 296.3.1算法优化的初步对比 296.4算法优化性能的深度分析 316.4.1评价指标归一化 316.4.2S&Cbalance的计算与实验对比 32第7章结论 35参考文献 36致谢 38PAGE5第1章绪论课题背景无线传感网络（WirelessSensorNetworks，WSN）是由大量分布在监测区域内的无线传感器节点组成的网络，用于实时监测、控制和数据采集。这些传感器节点通常由有限的能源供应，因此能耗问题一直是无线传感网络研究的一个关键挑战，无线传感网络的能耗问题主要源自以下几个方面：1.能源限制：传感器节点通常由电池供电，电池容量有限，难以更换或充电，因此能耗必须得到严格控制，以确保网络长时间稳定运行。2.传输能耗：传感器节点需要将采集到的数据传输到基站或其他节点，无线通信会消耗大量能量，尤其是在长距离传输或频繁通信的情况下。3.数据处理能耗：传感器节点需要对采集到的数据进行处理和分析，这也会消耗能量，尤其是在需要进行复杂计算或数据挖掘的情况下。4.网络拓扑结构：不同的网络拓扑结构会影响传感器节点之间的通信方式和能耗，如星型、网状、树形等结构都会对能耗产生影响。针对无线传感网络能耗问题，研究者们提出了各种解决方案和优化策略，包括但不限于：1.节点休眠和唤醒机制：通过让节点在空闲状态休眠以降低能耗，并在需要时唤醒进行工作，从而延长节点寿命。2.数据聚合和压缩：将传感器节点采集到的数据进行聚合和压缩，减少+数据传输量，降低通信能耗。3.能源有效利用：采用能量收集技术、能量传输技术或低功耗硬件设计等手段，提高能源的有效利用率。4.路由优化：设计高效的路由协议和算法，减少数据传输路径中的能耗消耗，提高网络整体能效。5.节点硬件和软件优化：优化传感器节点的硬件设计和软件算法，降低节点的功耗，提高整体网络的能效。综上所述，无线传感网络能耗问题一直是研究者们关注的焦点之一，通过不断研究和创新，可以有效解决能耗问题，推动无线传感网络在各个领域的应用和发展。1.2目的与意义无线传感网络能耗问题的研究具有重要的目的和意义，主要体现在以下几个方面：1.延长网络寿命：无线传感网络中的传感器节点通常由有限的能源供应，有效解决能耗问题可以延长网络的寿命，保证网络长时间稳定运行，提高网络的可靠性和持久性。2.降低维护成本：有效控制能耗可以减少传感器节点的能源消耗，降低网络维护成本。通过优化能耗问题，可以减少节点更换、充电等维护操作，降低网络运行的总体成本。3.提高网络性能：解决能耗问题可以提高无线传感网络的性能表现，如提高数据传输速率、降低数据传输延迟、提高数据传输稳定性等，从而提升网络的整体性能。4.推动网络应用发展：能耗问题的解决将促进无线传感网络在各个应用场景的广泛应用，如环境监测、智能交通、智能家居等领域。通过提高网络的能效，可以更好地满足各种应用场景对网络性能的要求，推动网络应用的发展和普及。5.促进技术创新：能耗问题的研究驱动了相关技术的创新和发展，包括节能算法、能源管理策略、能量收集技术等方面的研究。这些技术创新不仅可以解决能耗问题，还可以为无线传感网络的其他方面带来新的突破和进步。无线传感网络能耗问题的研究具有重要的目的和意义，通过解决能耗问题可以提高网络的性能和可靠性，降低维护成本，推动网络应用的发展，促进技术创新，为无线传感网络的发展和应用提供坚实的基础和支持。1.3论文研究主要内容本文无线传感网络能耗研究的主要内容包括以下几个方面：1.节能算法：设计和实现高效的节能算法是无线传感网络能耗研究的核心内容之一。通过优化数据传输、节点休眠/唤醒、路由选择等算法，减少节点能耗，延长网络寿命。2.能源管理策略：研究如何合理管理传感器节点的能源，包括能源的存储、利用和分配等方面。通过制定有效的能源管理策略，提高网络的能效性。3.路由优化：设计高效的路由协议和算法，减少数据传输过程中的能耗。优化路由选择和数据传输路径，降低网络的能耗消耗。综上所述，无线传感网络能耗研究的主要内容涵盖节能算法、能源管理策略、节点设计与优化、能量收集技术、路由优化和网络拓扑控制等多个方面。通过综合研究和优化这些内容，可以有效解决无线传感网络的能耗问题，提高网络的性能和可靠性。1.4国内外研究现状无线传感网络能耗是一个重要的研究方向，在国内外都引起了广泛的关注。以下是国内外关于无线传感网络能耗研究的一些现状：国内研究现状：1.中国的高校和科研机构在无线传感网络能耗方面展开了许多研究工作，涉及节能算法、能源管理、节点设计优化等方面。2.针对农业、环境监测、智能交通等领域的无线传感网络能耗研究也得到了广泛关注，为实际应用提供了有效的技术支持。国外研究现状：1.在国外，许多知名大学和研究机构也在无线传感网络能耗领域进行深入研究，提出了许多创新的节能算法和能源管理策略。2.针对智能城市、健康监测、工业物联网等领域的无线传感网络能耗研究也备受关注，为推动智能化和可持续发展提供了重要支持。总体来说，国内外对无线传感网络能耗的研究都在不断深化和拓展，为提高网络性能、延长节点寿命和推动智能物联网的发展做出了重要贡献。第2章算法基本原理介绍2.1问题提出在无限传感网络中，路由节点数量众多，如何将其传输到sink节点有着非常多的路径选择，如何选择高效，合理的策略进行路径选取是本文探讨的核心问题。目前已有的相关方向算法例如LEACH算法，它利用簇头的随机轮换在网络中的传感器之间均匀地分配能量负载。LEACH使用局部协调来实现动态网络的可伸缩性和健壮性，并将数据融合纳入路由协议中，以减少必须传输到基站的信息量。这种是基于无线传感网络方向的一个专有研究算法。而本文中我采用的是应用于多种情景下的最短路径算法，它可以解决例如导航中对于路径规划的实际问题。通过调研发现在无限传感网络中能量的消耗与距离存在着正相关的关系，所以可以对传统的相关最短路径算法如dijtstra算法，bellman-ford算法，floyd算法进行改进，使其应用于wsns中关于能量消耗探究的相关领域中，实现最优能耗的探索与研究。2.2算法描述2.2.1dijtstra算法描述Dijkstra算法是一种用于解决带权图的单源最短路径问题的算法。该算法由荷兰计算机科学家EdsgerW.Dijkstra于1956年提出。Dijkstra算法的目标是找到从起点到所有其他节点的最短路径。它的具体运行过程如下：初始化：创建一个空的最短路径集合S，将起始节点加入其中。同时，创建一个距离数组dist[]，用于记录每个节点到起始节点的最短距离。将起始节点的距离设置为0，其余节点的距离设置为无穷大。遍历：从未加入到最短路径集合S中的节点中选择距禇起始节点最近的节点u，加入到S中。更新距离：对于节点u的每个相邻节点v，如果通过节点u到节点v的距离比当前记录的距离更短，则更新节点v的距离为通过节点u到节点v的距离。即如果dist[u]+weight(u,v)<dist[v]，则更新dist[v]=dist[u]+weight(u,v)。重复步骤2和步骤3，直到所有节点都加入到最短路径集合S中。最终结果：当所有节点都加入到最短路径集合S中后，dist数组中记录的即为起始节点到每个节点的最短距离。Dijkstra算法是一种贪心算法，每次选择距离起始节点最近的节点加入最短路径集合中，但这并不一定能得到全局最优解。在本文中通过dijtstra算法求得的最优路径与距离，通过能量公式算得最优路径下所需的总能量，得到情形下的最优能耗。2.2.2bellman-ford算法描述美国应用数学家RichardBellman(理查德.贝尔曼,动态规划的提出者)于1958年发表了该算法。此外LesterFord在1956年也发表了该算法。因此这个算法叫做Bellman-Ford算法。其实EdwardF.Moore在1957年也发表了同样的算法，所以这个算法也称为Bellman-Ford-Moore算法。Bellman-ford算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。缺点是时间复杂度过高，为O(VE),V为顶点数，E为边数。其主要思想：对所有的边进行n-1轮松弛操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。换句话说，第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离；第3轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离。其具体流程为：初始化：将起点的距离设置为0，其余节点的距离设置为无穷大。迭代：重复以下步骤N-1次，其中N为节点的数量：对于图中的每条边(u,v)，如果从起点到节点v的距离大于从起点到节点u再从u到v的距离，则更新节点v的距离为从起点到节点u再从u到v的距离。检测负权环：如果在第N-1次迭代后，仍然存在可以松弛的边，则说明图中存在负权环。最终检查：检查是否存在负权环。对于第N次迭代，如果还有节点的距离可以被更新，则说明存在负权环。2.2.3floyd算法描述floyd算法，又称为Floyd-Warshall算法，是一种用于解决带有负权边的图的所有节点对之间的最短路径问题的算法。该算法的时间复杂度为O(n^3)，适用于所有有向图或无向图，但不适用于含有负权环的图。Floyd算法的基本思想是动态规划。假设给定一个n个节点的图，Floyd算法通过一个n*n的矩阵D来记录任意两个节点之间的最短路径长度。矩阵D的初始值为图中各个节点之间的边的权值，如果两个节点之间没有边相连，则将其距离设为无穷大。通过三重循环，Floyd算法逐个遍历每个节点，计算任意两个节点之间通过当前节点的最短路径长度，并将其更新到矩阵D中。具体步骤如下：初始化矩阵D。对于任意两个节点i和j，如果i和j之间有边相连，则将D[i][j]的值设为边的权值，否则设为无穷大。三重循环：对于图中的每个节点k，遍历所有的节点i和j，更新D[i][j]的值，如果D[i][j]的值大于D[i][k]+D[k][j]的值，则将其更新为D[i][k]+D[k][j]的值。返回矩阵D。矩阵D中D[i][j]的值表示节点i和节点j之间的最短路径长度。Floyd算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。需要注意的是，Floyd算法适用于所有有向图或无向图，但不适用于含有负权环的图。如果存在负权环，则无法求得最短路径长度。2.3算法流程图2.3.1dijtstra算法流程图2.3.2bellman-ford算法流程图2.3.3floyd算法描流程图2.4本章小节本章介绍了dijtstra算法，bellman-ford算法，floyd算法的运行原理与改进方向，论述了文章中所需要用到的算法原理。第3章最短路径算法在无线传感网络中的应用及改进策略3.1问题提出最短路径领域算法是一类成熟的且运用方面多样的优秀算法，在本文中选取了dijtstra算法，bellman-ford算法，floyd算法作为研究对象。在无限传感网络中求能量消耗最少的问题本质上也是求一种最优解的问题，而传统的最短路径算法恰好可以通过能量公式作为纽带进行跨领域问题的研究。在无线传感网络中，节点通常由电池供电，因此节点的能量消耗是一个非常重要的问题。其中，最少能量消耗问题旨在找到一种最优的数据传输路由策略，以最小化网络中节点的能量消耗，从而延长整个网络的生命周期。具体来说，最少能量消耗问题可以描述为在给定无线传感网络拓扑结构和节点能量消耗模型的情况下，寻找一种节点之间的数据传输路由策略，使得数据从源节点传输到目标节点的过程中，整个路由路径上节点的能量消耗最小。这个问题可以通过动态规划、贪心算法、遗传算法等方法来解决。解决最少能量消耗问题具有重要的意义，可以有效延长整个无线传感网络的生命周期，提高网络的稳定性和可靠性。因此，研究如何设计高效的能量节约策略和路由算法对于无线传感网络的发展至关重要。3.2算法应用场景改进3.2.1节点调整优化策略在最短路算法中，往往会给出已有的节点及连通情况，以及连通的距离数值，最后通过算法得到最优的路径总长。而无线传感网络中处于一个模拟的状态并没有给出确定的数值，所以需要进行随机生成。在实现中采用了srand函数随机生成了100个x坐标与100个y坐标，模拟了100个随机生成且不重复的路由节点，并且将100号节点作为接收（sink）节点，需要将所有路由节点的信息传递到sink节点。由于第一步仅给出了节点生成条件并没有给出节点间的连通信息，所以需要设计一个范围感知函数用以检测并对感知范围内的节点自动连接通路，于是设计了range_detection感知函数，将路由节点间距离小于40的节点通过邻接矩阵以及结构体存储的方式进行了节点连接与数据保存，实现了100个节点的节点自动生成以及通路。3.2.2算法调整优化策略1.由于dijtstra算法与bellman-ford算法是用以解决单源的最短路径算法，而本文需要解决的是多源的各个节点到sink节点的能耗分析，所以在原来的基础上加了一层节点数个数的循环，用以从不同的节点作为起点实现了无限传感网络中求解多源问题的情形。2.由于最短路算法中解决的是路径最优解的问题，而本文探讨的是最优能耗的问题，所以需要将能耗公式加入算法中，并加入一个二维的能耗矩阵用于记录路由节点在不同时刻剩余的能量情况。同时由于最短路径算法只需要求得最终的最优解即可，而能量的计算需要考虑各个中继路由节点的情况，所以对于用以对比的三个算法，分别设计了显示经由路径的函数用以完成能量消耗的计算，并将整个无限传感网络的状态保存在一个随时更新的二维矩阵中，可以随时观测各个节点的剩余能量情况。3.2.3评价指标改进在最短路径中，评价指标即是完成起点到终点所经由的最短路径，对应到无线传感网络中，就是整个过程总消耗能量大小，所以总耗能作为一个对于本文的评价指标。但是不同于最短路径的情景应用，无线传感网络中的节点可以多次应用并完成信息传输，所以本文增加了一层独立的epoch，对模型进行重复的使用与验证，直至第一次出现死亡节点，已验证不同算法对于节点能耗分配的合理性，死亡节点的轮次作为另一个评价指标，死亡节点的epoch越靠后，对于算法模型的可持续应用效果则越好。3.3算法优化策略在最短路径问题中，所需要解决的核心问题是起点到目标节点的最短路径问题，由于无线传感网路中能量的消耗问题与最短路径问题有异曲同工之妙，所以将最短路径相关算法应用在了wsns中。但是wsns所需要考虑的因素不仅仅只有能量消耗的方面，每一个节点在初始条件下附带着固定的能量，当能量消耗殆尽后节点就会出现死亡，如何延后节点的死亡轮次以保证网络节点的生命周期也是一个需要考虑的因素。在模型中，设立了多个评价指标，例如节点死亡轮次，FDT总能耗，FDT剩余能耗，节点平均剩余能量等。其中在无线传感网络中，节点的死亡轮次是无线传感网络高能路由算法的重要组成部分。所以优化部分的侧重点就是推迟FDT出现的轮次，从而提升节点的整体寿命。在本文中，选用dijtstra算法做为优化算法的基础架构，常规的dijtstra思想是基于贪心算法的，每次遍历距离当前节点最近的连通节点，这样可以保证求得最短的路径。但是如果一直使用这些最短的路径节点，会给节点带来较大的负荷，FDT的出现也会不可避免的加快，所以本文提出了一种优化思想：为了保证节点能耗的节能性，在开始阶段保留dijtstra算法的运行模式，当某个节点的剩余能量小于一个参考值时，调整策略。当节点的剩余能量较少时，设立一个状态记录数组，将该节点标记，被标记的节点将在模型中被暂停使用，同时设立一个计数器，记录当前被标记的节点个数。设立一个经验值，作为允许节点被标记个数的最大值，当节点超过该经验值时，模型节点传递的路径将会受到影响，所以当计数器到达该经验值时，清除状态数组中被标记的节点，允许这些节点继续进行工作。沿用dijtstra的思想，继续进行模型的运行，直至结束。通过以上的策略调整优化，在损失较小的能耗情况下，可以显著提升模型出现死亡节点的轮次，达到延后FDT出现的轮次，从而提升节点寿命。3.4本章总结对无线传感网络节点耗能问题进行优化时，可以利用Dijkstra算法、Bellman-Ford算法和Floyd算法来寻找最优的数据传输路由策略，从而最小化节点的能量消耗。这些算法可以在不同情况下提供不同的优化方案。Dijkstra算法：Dijkstra算法适用于单源最短路径问题（在本文改进为多源算法）用于计算从一个节点到其他所有节点的最短路径。在无线传感网络中，可以使用Dijkstra算法来找到从源节点到其他所有节点的最短路径，并选择能量消耗最小的路径作为数据传输路由策略。通过选择最短路径，可以减少节点之间的数据传输距离，从而降低节点的能量消耗。Bellman-Ford算法：Bellman-Ford算法适用于带有负权边的图的最短路径问题，可以处理含有负权边的情况。在无线传感网络中，如果存在负能量边或者节点的能量消耗不是固定值，可以使用Bellman-Ford算法来找到从源节点到其他所有节点的最短路径，并选择能量消耗最小的路径作为数据传输路由策略。Floyd算法：Floyd算法适用于计算所有节点对之间的最短路径，可以用于寻找任意两个节点之间的最短路径。在无线传感网络中，可以使用Floyd算法来计算所有节点之间的最短路径，并选择能量消耗最小的路径作为数据传输路由策略。通过对整个网络进行全局优化，可以有效降低整个网络节点的能量消耗。 Dijtstra优化算法： 通过对dijtstra算法进行优化，可以明显的延后节点死亡轮次综合利用这些算法可以在不同情况下找到最佳的数据传输路由策略，从而最小化无线传感网络节点的能量消耗，延长网络的生命周期并提高网络的性能。第4章算法模型概述4.1路由节点及sink节点的生成与连通性感知4.1.1node_generation节点生成模块voidnode_generation(){srand(time(0)); for(inti=0;i<101;i++) { label[i].x=-1; }for(inti=0;i<101;i++) {inta=getRand(1,100);intb=getRand(1,100);label[i].x=a;label[i].y=b;label[i].name=i; } cout<<"sink节点生成坐标为："; printf("(%d,%d)",label[100].x,label[100].y); cout<<endl;}在节点生成模块中，使用srand函数生成100组范围在(1,100)内的整数，作为路由节点与sink的x,y坐标，其中1-99号默认为路由节点，100号定义为基站节点。在存储方法中，定义了一个label结构体数组作为存储方式通过label存储了每个节点的坐标与编号，通过编号的存储可以实现节点调用的降维，不需要调用两个坐标，仅需调用name即可完成调用4.1.2range_detection节点自动感测模块voidrange_detection(){ total=0; for(inti=0;i<100;i++) { for(intj=i+1;j<101;j++) { if(label[i].x!=-1&&label[j].x!=-1) { intcx=pow(label[j].x-label[i].x,2); intcy=pow(label[j].y-label[i].y,2); doubledistance=sqrt(cx+cy); if(distance<=radius) { inta=label[i].name; //pos_x=a; intb=label[j].name; Map[a][b]=min(Map[a][b],distance); Map[b][a]=Map[a][b]; floy[a][b]=min(floy[a][b],distance); floy[b][a]=floy[a][b]; path[a][b]=b; path[b][a]=a; edges[total].a1=a; edges[total].b1=b; edges[total].c1=distance; total++; } } } }在range_detection函数中，首先用两层循环依次遍历node_detection中生成的所有节点，其中为了防止遍历到同一节点，内层循环j从i+1开始遍历，在本文中节点的检测形态为圆形，半径为30。通过每个节点的遍历，通过每个点的(x,y)坐标，计算出节点间距离小于30的所以情形，并将所有距离小于监测半径radius的通过邻接矩阵map进行连通，将map中不连通的矩阵点设为无穷大（inf）。在本文中使用了三种算法进行了节点能耗与节点生存性探究，其中dijtstra算法使用map邻接矩阵进行了存储，bellman-ford算法使用了edges结构体存储了所有边的连通性情形，floyd算法使用了floy邻接矩阵对连通性进行了存储，并为后续floyd算法的计算做了前置工作。4.2算法核心部分概述4.2.1dijtstra算法的实现voiddijkstra(){ memset(dist_path,-1,sizeof(dist_path)); intU[110],mmin; memset(U,0,sizeof(U)); for(inti=1;i<=100;i++){dist_path[i]=Map[start][i];if(Map[start][i]<inf)dist_path[i]=start;} dist_cnt=0;visit[start]=0;dist[start]=0;while(start!=target){Min=inf;for(inti=0;i<101;i++){if(Map[start][label[i].name]!=inf){ if(Map[start][label[i].name]+dist[start]<dist[i]){ dist[i]=Map[start][label[i].name]+dist[start]; dist_path[i]=start; }}if(visit[label[i].name]&&dist[i]<Min){nex=i;Min=dist[i];}}if(Min==inf)break;start=nex;visit[start]=0;}cout<<endl;if(dist[target]==inf)cout<<"-1";elsecout<<"最短距离为"<<dist[target]<<endl;}Dijistra算法是基于贪心思想的策略，在本文中首先设立了一个dist_path数组，通过后续的函数调用输出存储的路径，使用visit数组存储节点状态，判断有没有经过该节点，使用dist数组做状态更新，通过while循环，不断对起始节点到各个节点的最优距离进行更新与松弛，使用dist数组存储start节点到各个节点的最短距离，后续再通过能量公式转化为消耗的总能量。通过while循环的不断松弛，中间阶段的start与nex会动态更新，基于贪心算法每次会选择当前最优的最短路程，通过反复的迭代，最终达成当前算法的贪心效果。4.2.2bellman-ford算法的实现voidbellman_ford(intstart){ for(inti=0;i<101;i++)pre[i]=i; for(inti=0;i<101;i++)dist_bel[i]=inf;//memset(dist_bel,0x3f,sizeofdist_bel); dist_bel[start]=0;for(inti=0;i<101;i++){ for(intk=0;k<101;k++) { last[k]=dist_bel[k]; } //memcpy(last,dist_bel,sizeofdist_bel);for(intj=0;j<total;j++){EDGe=edges[j];//dist_bel[e.b1]=min(dist_bel[e.b1],last[e.a1]+e.c1);if(dist_bel[e.b1]>last[e.a1]+e.c1) { dist_bel[e.b1]=last[e.a1]+e.c1; pre[e.b1]=e.a1; } }}/}Bellman-ford算法是一种基于松弛原则的算法，在本文中创，建了一个edges结构体用于bellman-ford算法的存储，edges存储了所有连通边的起点，终点与联通距离。Bellman-ford的运算方式区别于dijtstra，会在内层循环中遍历所有的边数，同时需要对数组做一个备份，存储上一次循环的dist_bell的状态，用于完成松弛的迭代操作。在bellman-ford算法中，定义了一个pre数组，用来存储每次更新迭代的前驱情况，为后续对路径转化为能量消耗做了铺垫。Bellman-ford的外层循环为所有的点数，内层循环遍历了所有的边数，内存保证了可以对所有的连通边全部进行松弛操作，外层通过点数的重复，确保了内存的最终松弛可以找到最优解，实现对最短路径的寻求，本文即最低能耗的计算。4.2.3bellman-ford算法的实现voidfloyd(){ for(intk=1;k<=100;k++) { for(inti=1;i<=100;i++) { for(intj=1;j<=100;j++) { if(floy[i][k]+floy[k][j]<floy[i][j]){ floy[i][j]=floy[i][k]+floy[k][j]; path[i][j]=path[i][k]; } } }Floyd算法是基于动态规划思想的算法，在本文中使用floy矩阵作为存储的邻接矩阵，通过状态转移方程floy[i][j]=min(floy[i][j],floy[i][k]+floy[k][j]),不断更新邻接矩阵floy[N][N],通过三重循环的不断更新，floy即存储了各个点间的最短距离，完成了对多源最短路问题的更新。4.2.4dijtstra_new算法的实现（优化模块）voiddijtstra_new(){ dist_cnt_new=0; memset(dist_path_new,-1,sizeof(dist_path_new)); for(inti=1;i<=100;i++){dist_path_new[i]=Map[start][i];if(Map[start][i]<inf)dist_path_new[i]=start;} dist_cnt_new=0;visit_new[start]=0;dist_new[start]=0;while(start!=target){Min=inf;for(inti=0;i<101;i++){if(Map[start][label[i].name]!=inf){ if(dist_judge[label[i].name]==1) { continue; } if(Map[start][label[i].name]+dist_new[start]<dist_new[i]) { dist_new[i]=Map[start][label[i].name]+dist_new[start]; dist_path_new[i]=start; }}if(visit_new[label[i].name]&&dist_new[i]<Min){nex=i;Min=dist_new[i];}}if(Min==inf)break;start=nex;visit_new[start]=0;}Dijtstra_new代码模块中添加了一个对当前节点状态判定的语句，结合main函数中的状态更新，可以控制算法是否需要调整策略，当判断数组dist_judge中的值等于0时，按照正常的算法流程进行，如果dist_judge判断为1时，增加计数器dist_judge_cnt的值，如果dist_judge_cnt大于一个经验值时，将判断标志dist_judge_flag赋值为true，更新dist_judge中所有的值为0，之后沿用原算法的运行思路即可。4.3路径路径存储及能量转化本文的探究主题是各种算法在无线传感网络中的表现情况，以及如何实现节点死亡轮次的延迟以实现对无限传感网络高能路由算法的探究。若想实现路径与能量的转化，首先需要引入能量计算公式，当相邻节点在感知半径（radius）内，使用自由空间传播（freespacecommunication）模型Etx(k,d)=Eelec*k+Efs*k*d*dErx(k)=Eelec*k由于最短路径算法求得的都是总的最短路径，并没有经过节点的信息，所以首先需要解决最优路径的生成问题，用以解决后续的通过公式进行能量转化，在本文中，分别定义创建了putout，print，printf_path函数解决了floyd，bellman-ford，dijtstra算法的路径存储问题。4.3.1putout函数（floyd最优路径存储）voidputout(intv1,intv2){ intz;z=path[v1][v2];floy_path[floy_cnt]=v1; floy_cnt++;while(z!=v2){ floy_path[floy_cnt]=z; floy_cnt++; z=path[z][v2]; } floy_path[floy_cnt]=v2; floy_cnt++;}本文定义了putout函数用来保存和输出floyd函数的经过路径，为了实现打印路径的功能，首先需要在floyd功能函数中对每一步动态规划的前驱进行存储记录，本文中创建了path数组进行了前驱的存储，在每次符合条件执行状态转移方程时，记录每一步的前驱数组路径。再结合putout函数的功能，通过while循环当v1!=v2时（起点未遍历到终点）,会返回当前存储在path数组中的前驱，直到v1=v2时，即完成了路径的查找。在每次的前驱查找中，定义了floy_path数组进行了路径的存储，floy_cnt作为计量floy_path长度的计数器，通过此函数实现了函数路径的存储。在整个算法完整进行后，通过对floy_path中中间节点的遍历，选取每次的起始与途径节点，对传递节点与接收节点套用能量消耗公式，每次对floy_energy(记录floyd算法节点剩余能量的存储数组)进行实时更新，通过定义tmp_floy(记录总能量消耗指标)可以得到floyd算法完整运行所消耗的总能量。4.3.2printf_path函数与print函数在dijtstra算法与bellman-ford算法中，记录路径所用到的思想与4.3.1中floyd算法类似，在dijtstra算法中，在每次通过贪心思想对当前节点到下一个连通节点与直达距离的更新迭代中。定义了dist_path数组对每一次更新的前驱进行了记录，再通过printf_path函数进行迭代，使dist_path数组完成了对dijtstra算法路径的存储。最后结合能量公式对dist_energy，dijtstra算法中每个节点的剩余能量情况进行了实时更新。Bellman-ford算法的前置存储步骤与前文提到的两种算法类似，使用了pre数组记录了更新过程中每一步的前驱，区别在于Bellman-ford算法对路径查找(print函数)使用了递归的方法，递归出口为start=end（成功递归了完整路径），如果起始节点不等于目标节点，则重复递归直到满足递归出口的条件，结果存储在bell_path数组中，再结合能量消耗公式完成能量的相关计算。第5章评价指标构建5.1生存能耗平衡性指标的创建思路（Survivalenergyconsumptionbalanceindex）由于最短路径的算法模块是对最短路径(本文即能量消耗)的探究，而对于模型的评判不仅需要考虑能量的消耗方面，节点的可持续应用，避免出现节点死亡等问题同样需要考虑在内，所以单一的指标无法完成对算法模型的评测，所以本文创立了一个新的评价指标生存能耗平衡性指标（Survivalenergyconsumptionbalanceindex），以下简称S&Cbalance，用以综合分析模型的运行效果。S&Cbalance将结合以下的因素综合判断算法模型的性能：算法模型首次出现死亡节点的轮次算法模型首次出现死亡节点时分别的总能量消耗算法模型首次出现死亡节点时的节点平均剩余能量S&Cbalance将综合以上实验结果综合评价模型的优劣。5.2先遣评价指标的归一化处理5.2.1线性归一化的优势线性归一化是一种常见的数据处理方法，用于将数据缩放到指定的范围内，通常是[0,1]或者[-1,1]。它的基本思想是通过线性变换将原始数据映射到目标范围内。线性归一化的优点包括：1. 保留数据结构：线性归一化仅对数据进行线性变换，不改变数据的分布和结构，保留了原始数据的特征。2. 简单易懂：线性归一化的计算方法简单直观，易于理解和实现。3. 消除量纲影响：将数据缩放到相同的范围内，消除了不同特征之间由于量纲不同而产生的影响。4. 提高算法收敛速度：对输入数据进行归一化可以加快很多机器学习算法的收敛速度，提高训练效率。5. 提高模型稳定性：归一化后的数据范围固定，有助于提高模型的稳定性和可靠性。线性归一化适用于各种需要将数据缩放到特定范围内的场景，如机器学习中的特征缩放、数据可视化等。5.2.2线性归一化的应用在5.1中已经介绍S&Cbalance会结合3个先遣评价指标进行评价，而不同评价指标的计量方法与单位也有所差别，所以首先需要将不同的指标拟合到一个相同的区间，进行归一化处理，以方便对S&Cbalance做合并操作。在本文中，对于归一化的方法选用了线性归一化的策略,归一化公式为：Xnorm=X–Xmin/XMAX–Xmin通过归一化的运算，可以将指标的范围控制在0-1内，为后续指标的合成做了前期准备。通过线性化归一公式将节点死亡轮次，FDT平均节点剩余能量，FDT算法总耗能统一归一化到区间0-1内。5.3通过层次分析法对归一化后的指标进行权重分配5.3.1层次分析法的介绍层次分析法（AnalyticHierarchyProcess，AHP）是一种用于决策问题的多准则决策方法，由美国学者托马斯·L·赛蒂（ThomasL.Saaty）在20世纪70年代提出。它是一种基于对问题进行层次划分和对比评价的方法，适用于复杂的决策问题，尤其是那些涉及多个目标和多个标准的问题。AHP的基本思想是将一个复杂的决策问题分解为若干个层次，从目标层到最底层的方案层，形成一个层次结构。然后，通过构建层次结构，确定每个层次的因素之间的两两比较矩阵，以便对不同因素之间的重要性进行定量化。接下来，通过对比较矩阵进行一致性检验和特征值分析，确定各因素的权重，最终得出综合评价结果，辅助决策者做出最优决策。5.3.2成对比较矩阵的构建在5.1中已经提到所需要应用到的三个评价指标：算法模型首次出现死亡节点的轮次，算法模型首次出现死亡节点时分别的总能量消耗，算法模型首次出现死亡节点时的节点平均剩余能量，将其在成对比较矩阵中命名为C1，C2，C3，结合Santy1-9成对比较矩阵标度表（图5.1）构建如下成对比较矩阵C标度含义1表示两个因素相比，具有同样重要性3表示两个因素相比，一个因素比另一个因素稍微重要5表示两个因素相比，一个因素比另一个因素明显重要7表示两个因素相比，一个因素比另一个因素强烈重要9表示两个因素相比，一个因素比另一个因素极端重要2，4，6，8上述两相邻判断的中值倒数与上述相符，重要反转为不重要表5.1santy1-9成对比较矩阵标度表5.3.3层次分析法运行结果与一致性检验 将5.3.2中构建的成对比较矩阵通过层次分析法代码进行验证图5.1层次分析法运行结果所以构建的成对比较矩阵通过了一致性检验，符合规范，同时程序给出了权重比例AHP权重占比C10.6870C20.1865C30.1265表5.2层次分析法运行结果通过分析得出了在模型中不同参考指标的权重占比5.3.4S&Cbalance的构建通过5.3.3层次分析法的结论，可以构建S&Cbalance的评价公式1.令α为算法模型首次出现死亡节点的轮次的权重2.令β为算法模型首次出现死亡节点时分别的总能量消耗的权重3.令γ为算法模型首次出现死亡节点时的节点平均剩余能量的权重4.令首次出现死亡节点的轮次(deadepoch)为de5.令首次出现死亡节点时分别的总能量消耗(deadconsumption)为dc6.令首次出现死亡节点时的节点平均剩余能量(averageremainingenergy)为are综上所述，构建S&Cbalance为S&Cbalance=α其中：α+β+到此即完成了评价指标S&Cbalance的构建第6章实验分析6.1数据准备为了保证实验结果具有普适性，实验的数据以10组为基准，对比试验与优化实验等都将选取10次的实验结果进行整体对照，其中我们使用节点自带为0.001J的能量进行实验。首先数据的生成采用的是随机生成的方法，使用node_generation随机生成节点，编号为1到100号，其中第100号节点作为基站节点。节点生成结束后，会通过range_detection函数对节点进行连通与感测，生成连通路径。以下为随机进行10次实验结果的数据死亡轮次（de）能量消耗（dc）平均剩余能耗(are)实验轮次使用算法DeDcAre1dijtstra760.01604350.0008771851bellman-ford1070.008136950.000931931floyd760.01604350.0008771851dijtstra_new2040.01610750.0008765452dijtstra560.01551840.0008725362bellman-ford620.01140190.0009064212floyd560.01535040.0008742162dijtstra_new1390.01550240.0008726963dijtstra660.007572360.0009386313bellman-ford290.006383290.0009458823floyd660.007543380.0009389213dijtstra_new1420.007572360.0009386314dijtstra530.01086990.0009175364bellman-ford1070.008987670.0009305284floyd530.01092290.0009170064dijtstra_new2020.01083090.0009179265dijtstra880.01539640.0008861315bellman-ford810.01353310.0008982845floyd880.01539640.0008861315dijtstra_new2520.01539640.0008861316dijtstra500.007776110.0009365946bellman-ford290.005643330.0009500926floyd500.007776110.0009365946dijtstra_new1350.007776110.0009365947dijtstra880.01283930.0009022977bellman-ford620.01007980.0009230727floyd880.01283930.0009022977dijtstra_new1900.01283930.0009022978dijtstra880.01945680.0008489928bellman-ford880.01593610.0008753998floyd880.01945680.0008489928dijtstra_new1900.01944280.0008491329dijtstra760.01573910.0008802299bellman-ford810.01243220.0009049389floyd760.01573910.0008802299dijtstra_new2280.01572010.00088041910dijtstra530.01072980.00091200710bellman-ford390.008154910.00093151610floyd530.01041790.00091512610dijtstra_new690.01072980.000912007通过以上图表记录了10次随机试验的运行结果，包括dijtstra算法，floyd算法bellman-ford算法，以及dijtstra_new算法。评价指标包括节点死亡轮次，平均节点剩余能量，算法模型FDL总能耗。6.2不同实验的数据对比6.2.1FDT时刻不同算法能耗对比通过以上结果图可以发现bellman-ford算法在第一次出现FDT时能耗较少，但bellman-ford算法的成功率约在％90，相对其他算法的稳定性较差。Dijtstra算法与floyd算法能耗相近，但dijtstra算法能耗略高于floyd算法。6.2.2FDT时刻不同算法节点平均剩余能量对比 当节点首次出现FDT时，bellman-ford平均节点剩余的能量相对另外两种较多，但是算法的稳定性较差，floyd和dijtstra算法节点平均剩余能量相近，floyd算法的剩余能量略高于dijtstra算法的结果。6.2.3不同算法出现FDT轮次对比通过对比的实验结果图可以看出，bellman-ford算法的FDL时刻波动很大，结果很不稳定，dijtstra和floyd算法的FDL轮次基本可以保证一致，但在多次的实验中偶尔也会存在差异，通过实验可以看出dijtstra和floyd的死亡轮次在50-90间波动，bellman-ford的死亡轮次波动在20-110轮次，稳定性相对较差。6.3算法优化前后对比实验6.3.1算法优化的初步对比从优化后的初步对比结果可以看出，算法中首次出现FDT时，不同算法的能量消耗与平均剩余能量，dijtstra_new与dijtstra和floyd算法保持了基本一致的性能，但是节点FDT的轮次相对于其他三种算法表现出了显著的提升，由于实验的因素较多，难以直观反馈算法特性，所以下面将进行S&Cbalance指标合一的综合性对比。6.4算法优化性能的深度分析6.4.1评价指标归一化为了使数据参照有个清晰直观的体验，使用线性归一化的方法，将所有数据映射到0-1的范围内，同时考虑到De和Are是正向指标，而Dc是负向指标，所以在归一化后将Dc转化为正向指标便于对比研究，数据处理结果如下实验轮次使用算法DeDcAre1dijtstra0.2107620.2470990.2788631bellman-ford0.3497760.8194790.8203561floyd0.2107620.2470990.2788631dijtstra_new0.7847530.2424660.2725322dijtstra0.1210760.2851130.2328782bellman-ford0.1479820.5831190.5680422floyd0.1210760.2972750.2494962dijtstra_new0.4932740.2862710.2344613dijtstra0.1659190.8603520.8866373bellman-ford00.9464320.9583583floyd0.1659190.8624490.8895053dijtstra_new0.5067260.8603520.8866374dijtstra0.1076230.6216320.6779824bellman-ford0.3497760.7578930.8064894floyd0.1076230.6177960.672744dijtstra_new0.7757850.6244560.681845dijtstra0.2645740.2939450.3673495bellman-ford0.2331840.4288350.4875575floyd0.2645740.2939450.3673495dijtstra_new10.2939450.3673496dijtstra0.09417040.8456010.8664896bellman-ford0116floyd0.09417040.8456010.8664896dijtstra_new0.4753360.8456010.8664897dijtstra0.2645740.4790610.527257bellman-ford0.1479820.678830.732747floyd0.2645740.4790610.527257dijtstra_new0.7219730.4790610.527258dijtstra0.264574008bellman-ford0.2645740.2548740.2611978floyd0.264574008dijtstra_new0.7219730.00101350.001384779dijtstra0.2107620.2691360.3089719bellman-ford0.6666670.5085330.5533739floyd0.2331840.2691360.3089719dijtstra_new0.8923770.2705110.31085110dijtstra0.1076230.6317750.62329410bellman-ford0.0448430.8181790.81626110floyd0.1076230.6543540.65414410dijtstra_new0.1793720.6317750.6232946.4.2S&Cbalance的计算与实验对比在5.3.4中已经阐述了S&Cbalance指标的构建方式，通过层次分析法给出各个影响因素的占比，可以结合评价因素综合判断模型的效果，通过公式S&Cbalance=αα+β+其中：α可以得出各个算法的S&Cbalance值并进行比较，下面是各个算法S&Cbalance的计算结果。轮次应用算法S&Cbalance轮次应用算法S&Cbalance1dijtstra0.22615401floyd0.2248891bellman-ford0.4969041dijtstra_new0.6188212dijtstra0.1658122floyd0.1701822bellman-ford0.2822362dijtstra_new0.4219283dijtstra0.3866023floyd0.3873563bellman-ford0.2977423dijtstra_new0.6207364dijtstra0.2756364floyd0.2742584bell