拓扑控制
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
拓扑控制 1 拓扑控制的意义 无线网络一般具有环境复杂、节点资源受限、网络拓扑不稳定的特点. 不同于有线网络,无线网络可以通过改变各个网络节点传输功率以改变网络的拓扑结构，这就是拓扑控制的实现技术基础。由节点的位置和其无线传输范围所确定的网络拓扑结构对网络的性能有着重大的影响. 如果拓扑结构过于松散,就容易产生网络分区以及增大端到端的时延;相反的,非常密集的拓扑不利于空间重利用,从而减小网络的容量[2]。拓扑管理和控制主要研究如何为节点分配功率以获得具有某种性质的拓扑结构和优化一些网络目标函数,其目的就是提高网络的性能, 降低通信干扰和延长网络的生存时间。 拓扑控制技术是无线网络中最重要的技术之一。在由无线传感器网络生成的网络拓扑中，可以直接通信的两个结点之间存在一条拓扑边。如果没有拓扑控制，所有结点都会以最大无线传输功率工作。在这种情况下，一方面，结点有限的能量将被通信部件快速消耗，降低了网络的生命周期。同时，网络中每个结点的无线信号将覆盖大量其他结点，造成无线信号冲突频繁，影响结点的无线通信质量，降低网络的吞吐率。另一方面，在生成的网络拓扑中将存在大量的边，从而导致网络拓扑信息量大，路由计算复杂，浪费了宝贵的计算资源。因此，需要研究无线传感器网络中的拓扑控制问题，在维持拓扑的某些全局性质的前提下，通过调整结点的发送功率来延长网络生命周期，提高网络吞吐量，降低网络干扰，节约结点资源。 拓扑控制主要研究如何在保证网络连通性的前提下，设计高效的算法为节点分配功率以获得具有某种性质的拓扑结构和优化一些网络目标函数，其目的就是节约节点的发射功率，延长网络的生存时间，提高网络的性能。拓扑控制是无线网络设计和规划的重要组成部分。 拓扑控制技术保证覆盖质量和连通质量，能够降低通信干扰、节省能量，提高MAC(media access control)协议和路由协议的效率。进一步，也可为网络融合提供拓扑基础；此外,拓扑控制还能够提高网络的可靠性、可扩展性等其他性能.总之，拓扑控制对网络性能具有重大的影响，因而对它的研究具有十分重要的意义。 无线网络的特点使拓扑控制成为挑战性研究课题,同时,这些特点也决定了拓扑控制在无线网络研究中的重要性。 2 拓扑控制算法 拓扑控制算法是实现拓扑控制的计算方法，良好的拓扑控制算法将获得计算时间、空间和通讯需求的优势。文献中提出一种基于邻近图MST模型的LMST(Local Minimum Spanning Tree) 节点功率控制算法。文献中定义MST如下: 图G(V，E)的子图E'为一棵包含了G所有顶点的树。E'的所有边的权值的和称为E'的权值，则最小权值树称作图G的最小生成树(Minimum Spanning Tree，MST)。 在LMST算法中，任意一个节点u在发送半径范围R内探测确定自身的邻居节点集合NuR，节点。及其邻居节点集合NuR之间的连线构成邻居子图GuR。图GuR中边的权值是以边的长度，即边的两个端点之间的欧氏距离来确定的。因为无线通信中，能量消耗E和距离d的关系满足式E=kdn,其中，参数n的取值范围为2n4。这意味着随着通信距离的增加，能耗急剧增大。E严格随d增大而增大，因此可以使用d作为边的权值。对节点(u1，v1)，(u2，v2)通过以下的公式确定唯一的权值d': d'(u1,v1)d'(u2,v2)d(u1,v1)d(u2,v2) Or (d(u1,v1)d(u2,v2)&&max{id(u1),id(v1)}max{id(u2),id(v2)} Or (d(u1,v1)d(u2,v2)&&max{id(u1),id(v1)}max{id(u2),id(v2)} &&min{id(u1),id(v1)}min{id(u2),id(v2)} 这样以d'作为权值，在GuR范围内进行最小生成树算法得到本地最小生成树Tu。GuR中各节点将生成的最小生成树Tu上与自身距离为一跳的节点设为邻居节点，并调整发射功率为达到最远邻居节点的功率，减少网络中不必要的链路，从而形成网络拓扑。 在LMST算法中，假设每一个节点都有一个唯一的ID，并且知道自身的位置，具有全向天线。假设信道是对称的，无线信号在传播中无障碍。LMST算法中网络拓扑的建立主要分为三个阶段: ①信息交换：信息需要通过每个节点u在拓扑结构处理中的所有在NuR中的信息，这可以获得每个节点用其最大功率来传播的周期性Hello消息最大传输功率。至少应当包括节点ID和节点位置。这些定期的信息可以发送任何数据信道或在一个单独的控制信道 .传输hello信息的两个时间间隔决定节点移动水平,将取决于网络模型. ②拓扑结构：可见邻近NuR的信息获取之后，每个节点u独立地用prim算法在图GuR中获取它的本地最小生成树Tu(v(Tu),E(Tu))，prim算法的时间复杂度为 本文来源：https://www.wddqw.com/doc/ce6c18b4df3383c4bb4cf7ec4afe04a1b071b078.html