第15章-物联网通信技术(曾宪武)LXX2014.7

第15章WSN的拓扑控制15.1功率控制15.2层次型拓扑结构控制15.3启发机制本章小结15.1功率控制

15.1.1基于节点度的算法

“度”是图论中的一个概念，是指图中的某个顶点与其相连接的边的个数。WSN可以抽象为一个图，WSN中的节点是所抽象的图的一个顶点。因此，一个节点的度数是指所有距离该节点一跳的邻居节点的数目。基于节点度的算法的核心思想是给定节点度的上限和下

限需求，动态调整节点的发射功率，使得节点的度数落在上限和下限之间。基于节点度的算法利用局部信息来调整相邻节点间的连通性，从而保证整个网络的连通性，同时保证节点间的链路具有一定的冗余性和可扩展性。1.本地平均算法

本地平均算法的步骤如下：

(1)开始时所有节点均具有相同的发射功率TransPower0，每个节点定期广播一个包含自己ID的LifeMsg。

(2)如果节点接收到LifeMsg消息，则发送一个LifeAckMsg应答消息。该消息中包含应答的LifeMsg消息中的节点ID。(3)每个节点在下一次发送LifeMsg时，首先检查已经收到的LifeAckMsg消息，利用这些消息统计出自己的邻居数NodeResp。

(4）如果NodeResp小于邻居数下限NodeMinThresh，那么节点在这次发射时将增大发射功率，但发射功率不能超过初始发射功率的Bmax倍，其发射功率为TransPower={min［Bmax，Ainc×(ModeMinThresh－

NodeResp)］}×TransPower0(15.1.1)

同样，如果NodeResp大于邻居节点的上限NodeMaxThresh，则需要减小发射功率为

TransPower={min［Bmin,Adec×(1-(ModeMaxThresh－NodeResp))］}×TransPower0(15.1.2)

在上两式中，Bmax、Bmin、Adec、Ainc为四个可调参数,它们会影响功率调节的精度和范围。2.本地邻居平均算法

本地邻居平均算法(LMN)与本地平均算法(LMA)类似，唯一的区别是在邻居数NodeResp的计算方法上。在LMN算法中，每个节点发送LifeAckMsg消息时，将自己的邻居数放入消息，发送LifeMsg消息的节点在收集完所有的LifeAckMsg消息后，将所有邻居的邻居数求平均值后作为自己的邻居数。这两种算法通过计算机仿真后，其结果为：两种算法的收敛性和网络的连通性是可以保证的，它们通过少量的局部信息达到了一定程度的优化效果。这两种算法对无线传感

器节点的要求不高，不需要严格的时钟同步。15.1.2基于邻近图的算法

1.邻近图

图可用G=(V,E)来表示。式中，V表示图中顶点的集合，E表示图中边的集合。E中的元素边可表示为l=(u,v)，其中u,v∈V。

由图G=(V,E)导出的邻近图G‘=(V,E’)是指，对于任意

一个顶点v∈V，给定其邻居判别条件q，E中满足q的边l∈E。典型的邻近图模型有RNG(RelativeNeighborGraph)、GG(GabrielGraph)、YG(YaoGraph)以及MST(MinimumSpanningTree)等。基于邻近图的功率控制算法如下：

所有节点都采用最大功率发射时形成的拓扑图为G，按照一定的规则q求出该图的邻近图G′，G′中的每个节点以自己所邻接的最远通信节点来确定发射功率。

这是一种解决功率分配问题的近似解法。考虑到WSN中两个节点形成的边是有向的，为了避免形成单向边，一般在运用邻近图的算法形成网络拓扑之后，还需要对节点之间的边给予增删，以使最后得到的网络拓扑是双向连通的。2.DRNG和DLSS算法

DRNG(DirectedRelativeNeighborGraph)和DLSS(DirectedLocalSpanningSubgraph)算法是基于邻近图的两种算法。它们最早是针对节点发射功率不一致问题而采用的解决方法。这两种算法是以经典邻近图RNG、LMST等理论为基础，全面考虑网络的连通性和双向连通性而提出的。以下先介绍一些基本定义。（1）有向边：边(u,v)和边(v,u)是不同的，它们的方向不同。

（2）节点间的距离及通信半径：用d(u,v)表示节点

u、v之间的距离，用ru表示u的通信半径。

（3）可达邻居集合及可达邻居子图：可达邻居集合

NRu表示节点u以最大通信半径可以到达的节点的集合。由节点u和NRu以及这些节点之间的边构成可达邻居子图GRu。（4）权重函数w(u,v)：节点u和v构成的权重函数w(u,v)满足以下关系:

w(u1,v1)>w(u1,v1)→d(u1,v1)>d(u2,v2)

或者

d(u1,v1)=d(u2,v2)&max{id(u1),id(v1)}>max{id(u2),id(v2)}

或者

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)}(15.1.3)在上述两种算法的执行过程中，节点都需要知道一些必要的信息，因此在拓扑形成之前要有一个信息获得阶段。在该阶段中，每个节点以自己的最大发射功率广播HELLO消息，该消息中至少应包括自己的ID和自己所在的位置。获得信息阶段完成后，每个节点通过接收的HELLO消息确定自己可达的邻居集合NRu。在图15.1.1中，假设u、v满足条件d(u,v)≤ru，且不存在另一个节点p同时满足w(u,p)<w(u,v)，w(p,v)<w(u,v)和d(p,v)≤rp时，节点v将被选择为节点u的邻居节点。因此，DRNG算法为节点u确定了邻居集合。

上述算法意味着当节点p与u的通信半径一定时，如果v到p和u的距离均小于它们各自的通信半径，且在三角形△vpu中，uv边的权最小，则v一定是u的邻居。图15.1.1DRNG算法在DLSS算法中，假设已知节点u以及它的可达邻居子图

GRu，将p到所有可达邻居节点的边以权重w(u,v)为标准按升

序排列，依次取出这些边，直到u与所有可达邻居节点直接相连或通过其他节点相连，最后与u直接相连的节点构成u的邻居节点集合。从图论来看，DLSS算法等价于在GRu基础上进行本地最小生成树的计算。当节点u确定了自己的邻居集合后，将调整发送功率，使其通信半径达到最远的邻居节点。更进一步，可通过对所形成的拓扑进行边的增删，使网络达到双向连通。

DRNG和DLSS算法着重考虑网络的连通性，充分利用邻近图的理论，考虑到传感器网络的特点，它们是同类算法中的典型算法，以原始网络拓扑双向连通为前提，保证优化后的拓扑也是双向连通的。15.2层次型拓扑结构控制

在WSN中，传感器节点的无线通信模块在空闲状态时的能耗与在收发状态时相当，所以只有使节点通信模块休眠才能大幅度地降低无线通信模块的能量开销。考虑依据一定机制选择某些节点作为骨干节点，激活通信模块，并使非骨干节点的通信模块休眠。由骨干节点建立一个连通网络来负责数据的路由转发，这样既能保证原有覆盖范围内的数据通信，也能在很大程度上节省节点的能量。在这种拓扑管理机制下，可将网络中的节点划分为骨干和非骨干节点两类。骨干节点对周围的非骨干节点进行管理。这类将整个网络划分为相连的区域的算法，一般又称为分簇算法。骨干节点是簇头节点，非骨干节点为簇内节点。层次型的拓扑结构具有较多优点：簇头节点负责数据融合，减少了数据通信量；分簇模式的拓扑结构有利于分布式算法的应用，适合大规模部署的网络；由于大部分节点在相当长的时间内使通信模块休眠，所以可显著延长整个网络的生命周期。15.2.1LEACH算法

LEACH(LowEnergyAdaptiveClusteringHierarchy)算法是一种自适应分簇拓扑控制算法，它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶段。LEACH

算法中的工作循环如图15.2.1所示。在簇的建立阶段，相邻节点动态地形成簇，随机产生簇头。图15.2.1LEACH算法中的工作循环1.簇头选举方法

LEACH算法选举簇头的过程如下：

节点产生一个0~1之间的随机数，若这个随机数小于阈值T(n)，则发布自己是簇头的公告消息。在每轮循环中，如果节点已经当选过簇头，则将T(n)设置为0，这样该节点不会再

次当选为簇头。对于未当选过簇头的节点，将以T(n)的概率当选；随着当选过簇头的节点的数量的增多，剩余节点当选簇头的阈值T(n)也随之增大，节点产生小于T(n)的随机数的概率随之增大，所以节点当选为簇头的概率也增大，当只剩余一个节点未当选时，T(n)=1，表示这个节点一定当选。T(n)可表示为（15.2.1)式中，P是簇头在所有节点中占的百分比，r是当选轮数，rmod（1/P）表示这一轮循环中当选过簇头的节点个数，G是这轮循环中未当选过簇头的节点的集合。节点当选簇头后，发布通告消息告知其他节点自己是新簇头。非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并告知该簇头。当簇头接收到所有的加入信息后，就产生一个TDMA定时消息，通知该簇内所有节点。为了避免附近簇的信号干扰，簇头可以决定本簇中所有节点所用的CDMA编码。这个用于当前阶段的CDMA编码连同TDMA定时一同发送。当簇内节点收到此消息后，就会在各自的时隙内发送数据。经过一段时间的数据传输，簇头收齐簇内节点发送的数据后，运行数据融合算法来处理数据，并将结果直接发送给汇聚节点。如图15.2.2所示，经过一轮选举过程，可以看到整个网络覆盖区域被划分成5个簇，图中黑色节点代表簇头。可以明显地看出经LEACH算法选举出的簇头的分布并不均匀，这是需要改进的一个方面。图15.2.2LEACH算法中的簇的划分2.LEACH改进算法

WSN是由大量节点组成的大规模传感器网络，离汇聚节点很远的簇头能量消耗很快，这样将影响网络的覆盖范围和生命周期。另外，LEACH提出的簇头选举机制没有考虑节

点的具体地理位置，不能保证簇头均匀地分布在整个网络中。尽管LEACH算法存在一些问题，但是它仍然是一种经典分簇算法用来作为分簇算法的基础。HEED(HybridEnergy-EfficientDistributedClustering)算法针对LEACH算法簇头分布不均匀的问题进行了改进，它以簇内平均可达能量(AverageMinimumReachabilityPower,AMRP)作为衡量簇内通信成本的标准。节点以不同的初始概率发送竞争消息，节点的初始化概率CHprob为(15.2.2)式中，CHprob和pmin是整个网络统一的参量，它们影响算法

的收敛速度，通常取pmin=10－4,Cprob=5%,

表示节点剩余能量与初始化能量的百分比。簇头竞选成功后，其他节点根据在竞争阶段搜集的信息选择加入的簇。15.2.2GAF算法

GAF(GeographicalAdaptiveFidelity)算法是用地理位置为依据来进行分簇的算法。它将监测区域划分为虚拟单元格，将节点按照位置信息划归相应的单元格。在每个单元格中定

期选举出一个簇头节点，若簇头节点保持激活状态，其他节点则进入睡眠状态。GAF算法中，节点的状态标记为三种状态：睡眠、发现和激活。传感器网络的初始状态是：所有的节点都处于发现状态。处于发现状态下的节点之间交换Discover消息，获取

同一个虚拟单元格内其他节点的信息。Discover消息包括以下几个部分的信息：节点自身的ID、所在虚拟单元格的ID、节点状态、节点激活时间的估值等。节点状态的转换如图15.2.3所示。只要是节点处于发现状态，都会对应一个发现状态计时器。如果节点处于发现状态的时间超过设定值Td，该节点就广播发送Discover消息，并转换到激活状态。在没有超过发现状态计时器的设定值Td之前，如果收到了另外的节点已经成为簇头节点的消息后，发现状态计时器将关闭，无线通信发射模块也关闭，节点进入

睡眠状态。图15.2.3结点状态转换图当节点进入激活状态后，激活状态计时器启动计时，设置一个Ta，若激活状态的持续时间超过