WSN中层次路由算法研究与.ppt

WSN中层次路由算法研究与仿真实现 导师 刘玉华教授学生 贾永灿 2020 2 9 1 目录 WSN概述及层次路由协议研究现状新算法的模型背景新的多层分簇路由方案的提出多层簇结构的动态生成基于退避算法的最小转发代价场仿真结果分析结论与展望参考文献 2020 2 9 2 WSN概述 1 体系结构 2020 2 9 3 图1无线传感器网络体系结构 WSN概述 2 传感器节点的能耗分布 2020 2 9 4 图2节点能耗 E trans E rece E idle E sleep E sens E cpu 减少通信流量采用多跳通信方式增加休眠时间 层次路由研究现状 2020 2 9 5 网络通常被划分为簇 cluster 簇首 clusterhead 和簇成员 clustermember 图3层次路由体系结构 1 HierarchicalTopology 层次路由研究现状 2020 2 9 6 成员节点大部分时间可以关闭通信模块 由簇头构成一个更上一层的连通网络来负责数据的长距离路由转发 这样既保证了原有覆盖范围内的数据通信 也在很大程度上节省了网络能量 2 簇头融合了成员节点的数据之后再进行转发 减少了数据通信量 从而节省了网络能量 3 成员节点的功能比较简单 无须维护复杂的路由信息 这大大减少了网络中路由控制信息的数量 减少了通信量 4 分簇拓扑结构便于管理 有利于分布式算法的应用 可以对系统变化做出快速反应 具有较好的可扩展性 适合大规模网络 5 与平面路由相比 更容易克服传感器节点移动带来的问题 2 分簇路由机制优点 层次路由之LEACH协议探讨 2020 2 9 7 LEACH Architecture 层次路由之LEACH协议探讨 2020 2 9 8 将基于TDMA的MAC协议与聚类协议和一个简单的 路由 协议集成在一起 层次路由之LEACH协议探讨 2020 2 9 9 将稳定通信阶段的时间轴划分成固定长度的时间桢 Frame 每个时间桢在进一步划分成固定数量的时隙某个节点可以在该时隙中周期性地在每个时间桢中发送数据 新算法的模型背景 1 假设 2020 2 9 10 l 所有节点都是同构的 并且节点能量有限 2 传感器节点位置固定 且距离目标检测区域较远 3 节点在其他节点的直接通信范围内 并且可以直接和sink通信 4 节点随机分布在一个兴趣区域内 周期性地感知环境并且通常每轮都有数据传输 将其所有收到的数据和自己感知的数据进行融合 产生一个新数据包 5 网络是时钟驱动的 感知信息的传送是在规定的时间间隔内进行的 传感器节点均由本地时钟来跟踪公共时间 以实现时钟的同步 新算法的模型背景 2 信道传输和能耗模型 2020 2 9 11 发送 接收 融合 新的多层分簇路由方案的提出 2020 2 9 12 1 传统的多层次分簇示意 各簇头节点重复担任各级簇首的角色 在实际通信中很容易因过快成为网络中的 热点 导致局部网络瘫痪 新的多层分簇路由方案的提出 2020 2 9 13 2 NHCR分簇示意 本算法中 新的簇首始终从网络中的当前非簇头节点中产生 即 下一层簇头不在上一层簇头集合中产生 本层簇头只负责处理本层的数据收集和融合 多层簇结构的动态生成 2020 2 9 14 1 成簇过程中节点自我当选时的概率公式 其中rs表示节点连续未当选簇头的轮次 一旦当选了簇头 rs重置为零 针对leach中T n 计算公式的不足 将能量因素考虑进来 综合考虑了节点能量和门限值大小对簇头选取的影响 2020 2 9 15 多层簇结构的动态生成 2 生成算法伪代码主要部分 2020 2 9 16 多层簇结构的动态生成 3 补充说明 需要强调的是 当第k层簇形成后 那些可能在第k 1层簇形成阶段成为簇头的节点 需要在广播当选消息中通告网络中的节点 自己所处簇的层次以及自己的状态 这样 网络中的第k层簇头节点就可以解除与这些新当选节点的包含关系 1 8行 非簇头节点依随机数与根据公式T n 计算所得概率值比较结果决定是否成为簇头 9 12行 各节点收到簇头生成消息后 首先检查该消息对应的簇头所属层数是否是自己的直接上层 如果不是将不作任何响应直接丢弃 否则 保留该节点信息至候选簇头列表 13 22行 节点计算候选簇头对应的加入标准 依据上文提到的两种情形选择相应的簇头节点直接发送加入消息 2020 2 9 17 基于退避算法的最小转发代价场 1 最小代价场的生成 节点并不会急于将每次修改后的代价广播出去 而是等待延迟时间到了以后再响应 每个节点仅向周围节点广播包含最小转发代价的信息 而丢弃那些不是最优信息的数据包 每个节点仅仅通过一次广播就可以建立最小转发代价 2020 2 9 18 基于退避算法的最小转发代价场 2 最小代价场的工作过程 数据包所携带的总的预算值为200 这个就是允许从源节点到sink能够消耗的能量大小 该值是数据包从源节点送出时指定的 当数据包已经发送至A点时 已经消耗的代价为110 包括了A广播数据包的代价值 在节点B C收到由A广播来的数据包时 首先将自身的最小代价值和A进行比较 如果小于A则说明其离sink比A近 如果大于A则放弃发送数据包 假设B和C都小于A 此时它们将计算剩下的代价预算值为200 110 90 然后由于节点B的代价为90 因此B将决定继续转发该数据包 而对于C而言 100 90 这意味着剩下的预算值不够C转发数据包到达接收发送器 即沿着C的方向不是从源发节点到sink的最优路径 因此C将放弃转发该数据包 2020 2 9 19 仿真结果分析 1 实验中参数取值列表 对于无线传感器网络 目前并没有统一的标准来评测不同的路由协议 提高能量利用率和延长网络生命周期是进行仿真的主要目标 这里本文引入网络生存期的标准 FND FirstNodeDies LND LastNodeDies 即网络中第一个节点与最后一个节点死亡的时刻 2020 2 9 仿真结果分析 2 网络中节点存活的数目 1 新算法中第一个节点死亡的时刻算法所运行过的轮数要远远高于其余三种路由方案 即新算法在网络生存时间上要明显优于Direct LEACH DCHS 其次 基站的远近对Direct算法的网络生存时间影响巨大的 这是因为绝大部分节点直接传送时要面对多路径损耗模型 能量消耗严重 而且Direct算法中不存在数据融合 这样导致网路中的 热点 频现 另外 leach和DCHS算法的网络生存时间也受到一定影响 这是因为这两种路由方案中每个簇首节点都要向sink节点直接发送融合后的数据 要面对多路径衰减的能耗 2020 2 9 仿真结果分析 3 网络中节点存活的数目 2 基站坐标不同时 对不同路由方案下网络生存时间的影响是有很大不同的 Direct算法在三种坐标下的存活时间差别非常大 相反 NHCR算法几乎不受任何影响 这是因为 NHCR算法在顶层簇首节点之间建立最小代价场 是顶层簇首之间的数据传送的能耗遵循自由空间衰减模型 此外底层簇内的传送也是遵循此类衰减模型 这样使整体上大大减少了单个节点的能耗 很大程度上降低了网络中 热点 出现的概率 从而提高了网络的生存时间 2020 2 9 仿真结果分析 4 存活节点在每一轮算法运行过程中的平均能耗 1 不论基站处于什么位置 运行Direct算法所产生的平均能耗要远远高于其它路由方案 而且波动很大 正如前文所说 这都是因为数据传输中多路径衰减的信道模型以及节点之间的相关数据缺乏融合所导致的 可以很清晰地看到 NHCR算法的平均能耗基本恒定 且平均能耗的值也是几种不同方案的最小者 这再一次地证明了采用多跳传输 数据融合 尤其是簇内通过不同节点分担传输和融合任务带来能耗均衡的重要性 2020 2 9 仿真结果分析 5 存活节点在每一轮算法运行过程中的平均能耗 2 不同基站坐标下不同路由方案的平均能耗自行比较的结果 不难看出 NHCR的平均能耗表现出了良好的稳定性 这说明本文所提出的算法具有很多的能耗均衡性 2020 2 9 仿真结果分析 6 仿真结果小结 通过顶层簇首节点之间的最小代价场的建立和底层簇首内实现不同节点分担数据融合与传输任务使网络中的数据处理量可以尽可能地被分布到不同节点 而且不论是底层通信还是顶层通信都做到尽量减少多路径衰减信道模型的出现 这样整个网络取得良好的能耗均衡性 有效延迟了第一个节点死亡出现的时刻 有效缓解网络了 热点问题 的出现 从而很大程度上延长了网络生存时间 结论与展望 1 1 分析无线传感器网络路由协议数据传输离不开网络路由协议 无线传感器网络中的路由协议必须紧紧围绕如何延长网络的生命周期这一核心问题 通过对现有路由协议的分析 发现现有多级分簇算法从能量节省方面优于现有的其它的路由协议 它能够大大延长网络的生命周期 但也存在一些缺点 2 提出解决方案针对现有多级分簇算法容易产生大量 热点 的缺点 提出了自己的解决方案 基于单一节点不重复担任多层簇首角色的底层簇首构建算法和顶层簇首之间建立最小代价场 在实现过程中考虑到 簇头节点到基站的距离 簇内节点到其相应簇头节点的距离以及各个节点剩余能量因素 从而 改进了原有的层次聚类路由协议 延长了网络的生命周期 结论与展望 2 3 在上述工作的基础上 通过详细的算法分析和设计 通过在计算机上进行仿真对改进的路由协议进行了验证 结果表明 改进算法节省了能量消耗 延长了网络的生命周期 它优于已有算法 本文介绍了一些无线传感器网络路由设计的性能指标 但仍然缺乏统一的评价参数 所以论文中一般根据实际情况 以存活节点数 网络所消耗的能量 网络的生命周期来衡量路由算法的效果 选择合适而客观的评价指标是需要进一步完善的工作 继续关注大规模无线传感器网络的通用协议的研究 但是最好能在此基础结合具体应用 提出实用 特定环境下的无线传感器网络的路由协议 并将网络的安全性考虑进来 参考文献 01 HeinzelmanW ChandrakasanA BalakrishnanH Energy efficientcommunicationprotocolforwirelessmicrosensornetworks In Proc ofthe33rdAnnualHawaiiInt lConf onSystemSciences Maui IEEEComputerSociety 2000 3005 3014 02 ManjeshwarA AgrawalDP TEEN Aprotocolforenhancedefficiencyinwirelesssensornetworks In Int lProc ofthe15thParallelandDistributedProcessingSymp SanFrancisco IEEEComputerSociety 2001 2009 2015 03 YounisO FahmyS HEED Ahybrid energy efficient distributedclusteringapproachforAdhocsensornetworks IEEETransactionsonMobileComputing 2004 3 4 660 669 04 LindseyS RaghavendraCS PEGASIS Power efficientgatheringinsensorinformationsystems In Proc oftheIEEEAerospaceConf Montana IEEEAerospaceandElectronicSystemsSociety 2002 1125 1130 05 ChanH PerrigA ACE Anemergentalgorithmforhighlyuniformclusterformation In Proc ofthe1stEuropeanWorkshoponWirelessSensorNetworks LNCS2920 Berlin Springer Verlag 2004 154 171 06 YeM LiCF ChenGH WuJ Anenergyefficientclusteringschemeinwirelesssensornetworks InternationalJour2nalofAdHoc SensorWirelessNetworks 2007 3 2 99 119 07 LiCF YeM ChenGH WuJ Anenergy efficientunequalclusteringmechanismforwirelesssensornetworks Proceedingsofthe2ndIEEEInternationalConferenceonMobileAdhocandSensorSystems MASS WashingtonDC 2005 08 S Bandyopadhyay et al AnEnergy EfficientHierarchicalClusteringAlgorithmforWirelessSensorNetworks inIEEEINFOCOM 03 09 沈波 张世永 钟亦平 无线传感器网络分簇路由协议 软件学报 July2006 17 3 1588 1600 10 HeinzelmanW ChandraksanA BalakrishnanH AnApplication specificprotocolarchitectureforwirelesssensornetworks IEEETransactiononWirelessCommunications 2002 1 4 660 670 11 吴小兵 陈贵海 无线传感器网络中节点非均匀分布的能量空洞问题 计算机学报 Feb2008 31 2 12 李莉 董树松 何培舟 温向明 无线传感器网络中路由协议的能量有效性设计 计算机与信息技术July2006 15 3 13 SoroS HeinzelmanW Prolongingthelifetimeofwirelesssensornetworksviaunequalclustering Proceedingsofthe5thInternationalWorkshoponAlgorithmforWireless Mobile AdHocandSensorNetworks Denver CO 2005 14 MarkA Perillo ZhaoCheng andWendiBethHeinzelman Ananalysisofstrategiesformitigatingthesensornetworkhotspotproblem InMobiQuitous pages474 478 2005 15 LianJ NaikK AgnewG Datacapacityimprovementofwirelesssensornetworksusingnon uniformsensordistribution InternationalJournalofDistributedSensorNetworks 2006 2 2 121 145 16 LianJ ChenL NaikK OtzuT AgnewG Modelingandenhancingthedatacapacityofwirelesssensornetworks IEEEMonographonSensorNetworkOperations IEEEPress 2004 91 183 17 OlariuS StojmenovicI Designguidelinesformaximizinglifetimeandavoidingenergyholesinsensornetworkswithuniformdistributionanduniformreporting ProceedingsoftheIEEEINFOCOM Barcelona Spain 2006 1 12 参考文献 18 OlariuS StojmenovicI Datacentricprotocolsforwirelesssensornetworks StojmenovicI HandbookofSensorNetworks AlgorithmsandArchitectures Wiley 2005 417 456 19 PerilloM ChengZ HeinzelmanW Ontheproblemofunbalancedloaddistributioninwirelesssensornetworks ProceedingsoftheIEEEGLOBECOMWorkshopsonWirelessAdHocandSensorNetworks Dallas TX 2004 74 79 20 KrishnamachariB EstrinD WickerS Modelingdatacentricroutinginwirelesssensornetworks In Proc ofIEEEINFOCOM 2002 21 HandyMJ HaaseM TimmermannD Lowenergyadaptiveclusteringhierarchywithdeterministiccluster headselection In Proc ofthe4thIEEEConf onMobileandWirelessCommunicationsNetworks Stockholm IEEECommunicationsSociety 2002 368 372 22 FanYeChen A SongwuLu et al Ascalablesolutiontominimumcostforwardinginlargesensornetworks ComputerCommunicationand