第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，若激活状态的持续时间超过Ta，则转入发现状态。当节点处于睡眠状态后，启动一个睡眠状态计时器，设置一个时间参数Ts，一旦睡眠状态持续时间超过Ts，节点就转入

发现状态。处于激活状态的节点在Ta超时之前，定时向外广播消息通告自己处于活动状态，以使其他节点中处于发现状态的节点不要进入激活状态。GAF算法在执行中分为两个阶段：虚拟单元格的划分和虚拟单元格中簇头的选择。在虚拟单元格的划分阶段，依据WSN节点的位置信息和通信覆盖范围，将节点的部署区域划分为若干个虚拟单元格，划分中要保证相邻虚拟单元格中的所有节点都能够相互及直接通信。对于WSN中的一个成员节点，已知整个监测区域的位置信息和自身的位置信息，就可以根据这些信息通过计算来确定自己处于哪一个虚拟单元格中。假设所有的节点通信半径是R，虚拟单元格是边长为r的正方形区域，要使相邻的两个虚拟单元格内任意两个节点之间能够直接通信，必须满足以下关系：(15.2.3)每个虚拟单元格产生一个保持激活状态的节点。如图15.2.4所示，图中有三个虚拟单元格，每个单元格内分布有若干个WSN节点。在虚拟单元格中的簇头选择阶段，刚开始的时候，所有的节点都处于发现状态，通过彼此发送包含自身的ID、位置信息的消息，同一虚拟单元格中的所有节点都彼此知道对方的信息，然后依照上述算法顺序地进行激活、睡眠和发现状态运行。图15.2.4虚拟单元格的划分（黑色节点表示处于激活态）在GAF算法的执行过程中，簇头的能量消耗越大，在本轮簇头竞争中继续成为簇头节点的概率就越低。通过仿真实验证明：GAF算法可以延长网络的生命周期，节点密度越大，即虚拟单元格中的平均节点数越大，延长网络生命周期的效果越显著。15.3启发机制

15.3.1STEM算法

STEM(SparseTopologyandEnergyManagement)算法是较早提出的节点唤醒算法。在STEM算法中，节点需要采用一种简单而迅速的唤醒方式，保证网络通信的畅通和较小的时延。STEM算法有STEM-B(STEM-Beacon)和STEM-T(STEM-Tone)两种不同的机制。1.STEM-B算法

当一个节点要给另一个节点发送数据时，它作为主动节点先发送一串beacon包。目标节点在收到beacon包后，发送应答信号并自动进入数据接收状态。主动节点接收到应答信号后，进入数据发送阶段。为了避免唤醒信号和数据通信的冲突，STEM-B算法采用了侦听信道与数据传输信道两个分离信道。如图15.3.1所示的是节点A在一段时间内通信能量的消耗过程。节点A使用f1和f2两个信道，f1信道为侦听信道，f2为数据传输信道。节点A在侦听信道周期性的侦听，在t1到t5时间内，A分别与B和C通信。在t1时刻，节点A需要和相邻节点B通信。于是，A节点首先在f1信道上发送一串beacon数据包，直到t2时刻收到来自节点B的响应为止；然后，节点A在t2~t3时段内通过f2信道发送数据给节点B，当完成通信后，暂时关闭f2信道。图15.3.1STEM-B算法示意图在t4时刻，节点A在f1信道上侦听到节点C发送的beacon数据包，于是在t4~t5时段内通过f2信道接收节点C发送的数据，在t5之后，节点A关闭f2信道，并继续保持在f1信道上的周期性侦听，这样便可以节省大量的能量。2.STEM-T算法

在STEM-T算法中，节点周期性地进行侦听，探测相邻节点是否有数据要发送。当一个节点想与某个相邻节点进行通信时，首先发送一连串的唤醒数据包，发送唤醒数据包的时间长度必须大于侦听的时间间隔，以确保相邻节点能够收到唤醒包,然后节点直接发送数据包，所有邻居节点都能够接收到唤醒包并进入接收状态。如果在一定时间内没有收到发送给自己的数据包，就自动进入睡眠状态。STEM算法使节点在整个生命周期中多数时间内处于睡眠状态，适用于类似环境监测或者突发事件监测等应用，这类应用均由事件触发，不要求节点时刻保持在激活状态。目前STEM算法可以与很多分簇类型的拓扑算法结合使用，如GAF算法等。值得注意的是，在STEM算法中，节点的睡眠周期、部署密度以及网络的传输延迟之间有着密切的关系，针对具体的应用要求应进行调整。15.3.2ASCENT算法

ASENT(AdaptiveSelfConfiguringSensorNetworksTopologies)算法属于节点唤醒机制算法，它着重于均衡网络中骨干节点的数量，以保证数据通信路由的畅通。当节

点接收数据时后，发现丢包严重，就向数据源方向的相邻节点发出求助消息，节点探测到周围的通信节点丢包率很高或者收到相邻节点发出的帮助请求时将被唤醒，并主动成为激活节点，以帮助相邻节点转发数据包。ASCENT算法包括触发、建立和稳定三个阶段。如图15.3.2所示，在触发阶段，汇聚节点与数据源节点不能正常

通信，此时，汇聚节点向它的相邻节点发出求助信息。图15.3.2ASCENT算法的三个阶段在建立阶段，节点收到相邻节点的求助消息，通过一定的算法决定自己是否为激活节点，如果成为激活节点，则向相邻节点发送通告消息，同时这个消息也是相邻节点判断自己是否成为激活节点的因素之一。

在稳定阶段，当数据源节点和汇聚节点间的通信恢复正常时，网络中激活节点的个数保持稳定。稳定阶段保持一定时间后，由于个别节点的能量耗尽或外界干扰等因素，网络中会出现通信不畅问题，又需要进入触发阶段。在ASCENT算法中，节点处于四种状态：①睡眠状态，节点关闭通信模块，能量消耗最小；②侦听状态，节点只对信息进行侦听，不进行数据包的转发；③测试状态，这是一个暂态,参与数据包的转发，并且进行一定的运算，判断自己是否需要变为激活状态；④激活状态，节点负责数据包的转发，能量消耗最大。这四种状态之间的转换关系如图15.3.3所示，其中NT表示节点的邻居数上限，LT表示丢包上限，Ts表示睡眠态定时器，Tp表示侦听态定时器，Tt表示测试态定时器，neighbors代表邻居数，loss代表丢包率，help代表求助消息。状态间转换关系如下：

（1）睡眠状态与侦听状态：处于睡眠态的节点设置定

时器Ts，当定时器超时后，节点由睡眠状态进入侦听状态；处于侦听态的节点设置定时器Tp，当定时器超时后，节点由侦听态进入睡眠状态。（2）侦听状态与测试状态：处于侦听状态的节点侦听信道，如果发现当邻居数小于邻居上限，并且信道的平均丢包率大于丢包上限，则节点进入测试状态；或者当平均丢包率小于丢包上限，但接收到来自