拓扑控制
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内探测确定自身的邻
居节点集合RuN，节点。及其邻居节点集合RuN之间的连线构成邻居子图RuG。图
R
u
G
中边的权值是以边的长度，即边的两个端点之间的欧氏距离来确定的。因为
无线通信中，能量消耗E和距离d的关系满足式E=knd,其中，参数n的取值范
围为24n。这意味着随着通信距离的增加，能耗急剧增大。E严格随d增大
而增大，因此可以使用d作为边的权值。对节点(1u，1v)，(2u，2v)通过以下的
公式确定唯一的权值'd:
''
11221122
(,)(,)(,)(,)duvduvduvduv
Or 11221122((,)(,)&&max{(),()}max{(),()}duvduviduidviduidv
Or 11221122((,)(,)&&max{(),()}max{(),()}duvduviduidviduidv
&
1122
&min{(),()}min{(),()}iduidviduidv
这样以'd作为权值，在RuG范围内进行最小生成树算法得到本地最小生成树
uT。RuG中各节点将生成的最小生成树u
T
上与自身距离为一跳的节点设为邻居节
点，并调整发射功率为达到最远邻居节点的功率，减少网络中不必要的链路，从
而形成网络拓扑。
在LMST算法中，假设每一个节点都有一个唯一的ID，并且知道自身的位
置，具有全向天线。假设信道是对称的，无线信号在传播中无障碍。LMST算法
中网络拓扑的建立主要分为三个阶段:
①信息交换：信息需要通过每个节点u在拓扑结构处理中的所有在RuN中的
信息，这可以获得每个节点用其最大功率来传播的周期性Hello消息最大传输功
率。至少应当包括节点ID和节点位置。这些定期的信息可以发送任何数据信道
或在一个单独的控制信道 .传输hello信息的两个时间间隔决定节点移动水平,将
取决于网络模型.
②拓扑结构：可见邻近RuN的信息获取之后，每个节点u独立地用prim算法
在图RuG中获取它的本地最小生成树((),())uuuTvTET，prim算法的时间复杂度为
(loglog)(log)OnnenOen
，在图uG中n是节点数，e是边数。
③传输功率的决定：假设所有节点的最大传输功率是已知且相同。通过测量
接收Hello信息的功率可以确定节点到达邻近节点的功率
算法特点总结：在LMST算法中，每个节点根据其本地拓扑结构（由一跳
邻居节点形式的拓扑），计算最小生成树，然后使其直接的一跳内的节点成为其
邻居，最后把节点的传输半径设为到达其邻居最远的一跳邻节点所需距离。
LMST算法的缺点：LMST算法导出的拓扑维护了网络的连通性。节点的平
均传输半径小并且每个节点的节点度（degree）一般不超过6。虽然LMST算法
建立的拓扑具有较高的功率有效性但维护困难。每个节点需要定期地运行该算法
以保障网络的连通性。
无线网络拓扑控制研究的发展趋势是以实际应用为背景，多种机制相互融合，强
调网络拓扑控制的自适应性和鲁棒性,在保证网络的连通性和覆盖度的前提下，
提高网络的通信效率,最大限度地节省能量，延长整个网络的生存时间，提高网
络性能。