无线传感器网络的路由协议PPT.pptVIP

贪心算法： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解 　　贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问 题他能产生整体最优解或者是整体最优解的近似解。 　 贪心算法的基本思路如下： 　　1.建立数学模型来描述问题。 　　2.把求解的问题分成若干个子问题。 　　3.对每一子问题求解，得到子问题的局部最优解。 　　4.把子问题的解局部最优解合成原来解问题的一个解。 　　 实现该算法的过程： 　　从问题的某一初始解出发； 　　while 能朝给定总目标前进一步 do 　　求出可行解的一个解元素； 　　由所有解元素组合成问题的一个可行解； 附录： 拓扑控制的概念与意义 概念 拓扑控制（topology control）是一种协调节点间各自传输范围的技术，可以减少节点的能耗或增加网络的传输能力。 意义 (1)影响整个网络的生存时间。 (2)减小节点间通信干扰，提高网络通信效率。 (3)为路由协议提供基础。 (4)影响数据融合。 (5)弥补节点失效的影响。 拓扑控制的研究方向 WSN中拓扑控制可以分为两个研究方向：功率控制和层次拓扑结构控制。 功率控制机制调整网络中每个节点的发射功率，保证网络连通，在均衡节点中直接邻居数目(单跳可达邻居数目)的同时，降低节点之间的通信干扰。 层次拓扑控制是利用分簇思想，使网络中的部分节点处于激活状态，成为簇头节点。由这些簇头节点构建一个连通的网络来处理和传输网络中的数据，并定期或不定期地重新选择簇头节点，以均衡网络中节点的能量消耗。 拓扑控制的评价指标 连通性 在没有拓扑算法前，两个节点之间存在k条路径，那么使用拓扑算法后，这两个节点中也应该存在k条路径。 覆盖性 覆盖问题中，最重要的因素是网络对物理世界的感知能力。 吞吐量 化简后的网络拓扑结构应该能够支持与原始网络相似的通信量。 扩展性（网络容量） 减少数据传输节点所能影响的邻居节点的数量,减少节点通信的传输范围,可以有效减小网络中的冲突域,从而降低通信冲突的概率。 拓扑控制的应用效果 实现拓扑控制的手段 1、在保证网络的连通性与覆盖性的情况下，控制节点的发射距离，减少发射功耗，同时减少分组冲突的可能性，减少不必要的开销； 2、尽可能让多的节点进行休眠，降低功耗； 3、数据融合，减少分组的冗余。 拓扑控制的表现 1、网络寿命：尽量降低网络能耗，延长网络生存周期； 2、减小节点通信负载，提高通信效率：传感器节点分布密度一般比较大，通过拓扑控制技术中的功率控制技术可以通过选择节点的发射功率合理调整节点的通信范围，使得节点在连通性与覆盖性得到一个平衡点。 3、辅助路由协议：只有活动的节点才能进行数据转发，而拓扑控制可以确定由哪些节点作为转发节点，同时确定节点之间的邻居关系。 4、数据融合策略的选择； 5、节点冗余：由于传感器节点本身固有的脆弱性不能保证节点一直持续正常工作。 拓扑控制的分类 基于位置的拓扑控制算法-邻近图 基本思想 设所有节点都使用最大发射功率发射时形成的拓扑图G，按照一定的邻居判别条件q求出该图的邻近图G，最后G中的每个节点以自己所邻近的最远通信节点来确定发射功率。 经典的邻近图算法 RNG、GG、DG、YG、MST、DRNG、DLMST、DLSS DRNG与DLSS算法 第一步: 每个节点以最大的发射功率广播HELLO信息，该信息至少包括：节点ID号、最大的发射功率、自身的位置。节点在收到HELLO信息后，确定了自己可以达到的邻居集合。 第二步： DRNG与DLSS以各自的邻居算法确定邻居集合，DRNG以与它节点最近的邻居节点选择优先；而DLSS最小化了图中所有边的最大能量消耗, 并取单跳距离的节点作为其邻居节点。 第三步 确定邻居节点后，将发射半径调整到最远邻居节点的距离，进一步通过对拓扑图的边进行增删，使网络达到双向连通。 邻近图算法仿真结果对比 * 智能交通的WSN中用三种模式混合的例子 * *  WSN中的路由协议和拓扑控制 主要内容 1.WSN的体系结构 2.路由协议的定义 3.WSN的特点及对路由设计的影响 4.路由协议的关键问题分析 5.路由协议的分类 6.典型路由协议及其比较 7.拓扑控制 WSN的体系结构 Node有四个基本组件构成 sensing unit processing unit Transceiver unit power unit 可能有的取决于应用程序需要的组件 location finding system：许多路由技术