拓扑控制学习教案

1、会计学1拓扑拓扑(tu p)控制控制第一页，共81页。2.1 概概述述第1页/共80页第二页，共81页。无线传感器节点是体积微小无线传感器节点是体积微小的嵌入式设备，由能量有限的电的嵌入式设备，由能量有限的电池供电，其处理能力、存储能力池供电，其处理能力、存储能力和通信能力相对较弱。除了设计和通信能力相对较弱。除了设计能量高效的链路层协议、路由协能量高效的链路层协议、路由协议和应用层协议外，还要设计优议和应用层协议外，还要设计优化的网络拓扑控制机制。由于传化的网络拓扑控制机制。由于传感器节点数量众多、成本要求低感器节点数量众多、成本要求低廉、分布区域广泛，而且部署区廉、分布区域广泛，而且部署区

2、生成一个高效的数据转发的网络生成一个高效的数据转发的网络拓扑结构。拓扑结构。第2页/共80页第三页，共81页。对于自组织的无线传感器网对于自组织的无线传感器网络而言，拓扑控制对网络的性能络而言，拓扑控制对网络的性能影响非常大。良好的逻辑拓扑结影响非常大。良好的逻辑拓扑结构能够提高路由协议和构能够提高路由协议和MAC协议协议的效率，为数据融合、时间同步的效率，为数据融合、时间同步和目标定位等很多方面奠定基础，和目标定位等很多方面奠定基础，有利于节省节点的能量来延长整有利于节省节点的能量来延长整个网络的生存时间。所以，拓扑个网络的生存时间。所以，拓扑能耗，延长网络生存周期。能耗，延长网络生存周期。

3、第3页/共80页第四页，共81页。(2) 减少节点通信负载，提减少节点通信负载，提高通信效率。传感器节点的分布高通信效率。传感器节点的分布密度一般较大，通过拓扑控制技密度一般较大，通过拓扑控制技术中的功率控制技术，可以选择术中的功率控制技术，可以选择节点的发射功率，合理调节节点节点的发射功率，合理调节节点的通信范围，使得节点在连通性的通信范围，使得节点在连通性和网络通信范围之间取得一个平和网络通信范围之间取得一个平衡点。衡点。(3) 辅助路由协议。在无线辅助路由协议。在无线点这一问题进行研究。点这一问题进行研究。第4页/共80页第五页，共81页。(5) 采用冗余节点。由于传采用冗余节点。由于传

4、感器节点本身所固有的脆弱性，感器节点本身所固有的脆弱性，不能保证节点一直持续正常的工不能保证节点一直持续正常的工作，所以在设计时需要采用冗余作，所以在设计时需要采用冗余技术对网络进行拓扑技术对网络进行拓扑(tu p)控控制，以保证网络的覆盖率和连通制，以保证网络的覆盖率和连通度。度。拓扑拓扑(tu p)控制研究的问控制研究的问题是：在保证一定的网络连通质题是：在保证一定的网络连通质尽，不同的尽，不同的第5页/共80页第六页，共81页。传感器网络应用关心不同的物理传感器网络应用关心不同的物理量，不同的应用背景对传感器网量，不同的应用背景对传感器网络的要求也不同，它的硬件平台、络的要求也不同，它的

5、硬件平台、软件系统和网络协议必然会有很软件系统和网络协议必然会有很大差别。不同的应用对底层网络大差别。不同的应用对底层网络的拓扑控制设计目标的要求也不的拓扑控制设计目标的要求也不尽相同。下面介绍尽相同。下面介绍(jisho)拓扑拓扑控制中一般要考虑的设计目标。控制中一般要考虑的设计目标。(1) 覆盖。覆盖是对传感器覆盖。覆盖是对传感器网络服务质量的度量，即在保证网络服务质量的度量，即在保证盖的要求实现节点的重部署。静盖的要求实现节点的重部署。静态网络覆盖将在后面具体介绍态网络覆盖将在后面具体介绍(jisho)，其中虚拟势场方法是，其中虚拟势场方法是一种重要的部署方法。一种重要的部署方法。第6页

6、/共80页第七页，共81页。(2) 连通。传感器网络的规连通。传感器网络的规模一般很大，所以传感器节点感模一般很大，所以传感器节点感知到的数据一般要以多跳的方式知到的数据一般要以多跳的方式传送到汇聚节点，这就要求拓扑传送到汇聚节点，这就要求拓扑控制必须保证网络的连通性。有控制必须保证网络的连通性。有些应用可能要求网络配置达到指些应用可能要求网络配置达到指定的连通度，有时也讨论渐近意定的连通度，有时也讨论渐近意义下的连通，即当部署的区域趋义下的连通，即当部署的区域趋于无穷大时，网络连通的可能性于无穷大时，网络连通的可能性直是拓扑控制研究直是拓扑控制研究(ynji)的主要的主要目标。目标。第7页/

7、共80页第八页，共81页。(4) 吞吐能力。设目标区域吞吐能力。设目标区域是一个凸区域，每个节点的吞吐是一个凸区域，每个节点的吞吐率为率为b/s，在理想情况下，则有，在理想情况下，则有下面的关系式：下面的关系式：其中，其中，A是目标区域的面积，是目标区域的面积，W2161AW Lnr(2-1)第8页/共80页第九页，共81页。(5) 干扰和竞争。减小通信干扰和竞争。减小通信干扰、减少干扰、减少MAC层的竞争和延长层的竞争和延长网络的生命期，这三者的意义基网络的生命期，这三者的意义基本是一致的。对于本是一致的。对于(duy)功率控功率控制而言，网络无线信道竞争区域制而言，网络无线信道竞争区域的大

8、小与节点的发射半径的大小与节点的发射半径r成正成正比，所以减小比，所以减小r就可以减少竞争；就可以减少竞争；第9页/共80页第十页，共81页。(7) 拓扑性质。对于网络拓扑性质。对于网络(wnglu)拓扑的优劣，很难给拓扑的优劣，很难给出定量的度量。因此，在设计拓出定量的度量。因此，在设计拓扑控制策略时，往往只是使网络扑控制策略时，往往只是使网络第10页/共80页第十一页，共81页。2.2 功功 率率 控控 制制传感器网络中，节点发射功率的控制传感器网络中，节点发射功率的控制(kngzh)也称功率分也称功率分配问题。节点通过设置或动态调整节点的发射功率，在保证网配问题。节点通过设置或动态调整节

9、点的发射功率，在保证网第11页/共80页第十二页，共81页。2.2.1 基于节点度的功率控制基于节点度的功率控制基于节点度的算法是传感器基于节点度的算法是传感器网络拓扑控制中功率控制方面的网络拓扑控制中功率控制方面的问题。一个问题。一个(y )节点的度数是节点的度数是指所有距离该节点一跳的邻居节指所有距离该节点一跳的邻居节点的数目。基于节点度算法的核点的数目。基于节点度算法的核心思想是给定节点度的上限和下心思想是给定节点度的上限和下限需求，动态调整节点的发射功限需求，动态调整节点的发射功率，使得节点的度数落在上限和率，使得节点的度数落在上限和计算节点度的策略不同。计算节点度的策略不同。第12页

10、/共80页第十三页，共81页。2.2.2 基于方向的功率控制基于方向的功率控制微软亚洲研究院的微软亚洲研究院的Wattenhofer和康奈尔大学的和康奈尔大学的Li等等人提出了一种能够保证网络连通人提出了一种能够保证网络连通性的基于方向的性的基于方向的CBTC算法。其算法。其基本思想是：节点选择基本思想是：节点选择(xunz)最小功率最小功率Pu, ，使得在任何以，使得在任何以u第13页/共80页第十四页，共81页。2.2.3 基于邻近图的功率控制基于邻近图的功率控制伊利诺斯大学的伊利诺斯大学的Li和和Hou提提出的出的DRNG(Directed Relative Neighborhood G

11、raph)和和DLMST(Directed Local Minimum Spanning Tree)是两个是两个具有代表性的基于临近图理论的具有代表性的基于临近图理论的功率控制算法。基于临近图的功功率控制算法。基于临近图的功率控制算法的基本思想是，设所率控制算法的基本思想是，设所扑以后，扑以后，第14页/共80页第十五页，共81页。还需要进行节点之间边的增删，还需要进行节点之间边的增删，以使最后得到的网络拓扑是双向以使最后得到的网络拓扑是双向连通的。在无线传感器网络中，连通的。在无线传感器网络中，基于基于(jy)临近图功率控制算法的临近图功率控制算法的作用是使节点确定自己的邻居集作用是使节点确

12、定自己的邻居集合，调整适当的发射功率，从而合，调整适当的发射功率，从而在建立一个连通网络的同时使得在建立一个连通网络的同时使得能量消耗最低。经典的临近图模能量消耗最低。经典的临近图模型有型有RNG(Relative Neighborhood Graph)、DRNG算法和算法和DLSS(Directed Local Spanning Subgraph)算法。算法。第15页/共80页第十六页，共81页。DRNG算法和算法和DLSS算法是算法是两种从临近图观点考虑拓扑问题两种从临近图观点考虑拓扑问题的算法，是一种较早提出的功率的算法，是一种较早提出的功率控制算法，两者均以经典的临近控制算法，两者均以

13、经典的临近图图RNG和和LMST等理论为基础，等理论为基础，全面考虑了连通性和双向连通性全面考虑了连通性和双向连通性问题。问题。RuNRuNRuG第16页/共80页第十七页，共81页。1122112211221122112211221122(,)(,)(,)(,)(,)(,)max(),( )max(),()(,)(,)max(),( )max(),()min(),( )min(),()w u vw u vd u vd u vd u vd u vid uid vid uid vd u vd u vid uid vid uid vid uid vid uid v或者且或者且且第17页/共80页第

14、十八页，共81页。在在DRNG算法和算法和DLSS算法算法中，节点都需要知道其他一些节中，节点都需要知道其他一些节点的必要信息，因此需要一个信点的必要信息，因此需要一个信息收集阶段：每个节点以最大的息收集阶段：每个节点以最大的发射功率广播发射功率广播“HELLO”消息，消息，该消息至少包括自身的身份该消息至少包括自身的身份(shn fen)标识号标识号(ID)和自身位置，和自身位置，RuN第18页/共80页第十九页，共81页。在在DLSS算法中，假设节点算法中，假设节点u及其可达邻居集合，将及其可达邻居集合，将p到所有到所有可达邻居节点的边以权重为标准可达邻居节点的边以权重为标准按升序排列；依

15、次按升序排列；依次(yc)取出这些取出这些边，直到边，直到u与所有可达邻居节点与所有可达邻居节点相连通或者通过其他节点连通；相连通或者通过其他节点连通；第19页/共80页第二十页，共81页。第20页/共80页第二十一页，共81页。DRNG算法和算法和DLSS算法着算法着重考虑了网络的连通性，充分利重考虑了网络的连通性，充分利用了邻居用了邻居(ln j)图理论，是无线图理论，是无线传感器网络中的经典算法，二者传感器网络中的经典算法，二者以原始网络拓扑双向连通为前提，以原始网络拓扑双向连通为前提，保证优化后的拓扑也是双向连通保证优化后的拓扑也是双向连通第21页/共80页第二十二页，共81页。2.2

16、.4 XTC算法算法XTC算法的基本思想是用接算法的基本思想是用接收信号的强度作为收信号的强度作为RNG中的距离中的距离度量，度量，XTC算法可分为如下三步。算法可分为如下三步。(1) 邻居排序：节点邻居排序：节点u对其所对其所uuuuvu第22页/共80页第二十三页，共81页。(3) 链路选择：节点按顺序链路选择：节点按顺序遍历，先考虑好邻居，再考遍历，先考虑好邻居，再考虑坏邻居。对于虑坏邻居。对于u的邻居的邻居v，如果，如果(rgu)节点节点u没有更好的邻居没有更好的邻居，使得，使得，那么，那么u就和就和vuuv第23页/共80页第二十四页，共81页。2.3 层次型拓扑结构控制层次型拓扑结

17、构控制在传感器网络中，传感器节点的无线通信模块在空闲状在传感器网络中，传感器节点的无线通信模块在空闲状态时的能量消耗与在首发状态时的相当，所以只有关闭节点态时的能量消耗与在首发状态时的相当，所以只有关闭节点第24页/共80页第二十五页，共81页。算法。骨干网节点是簇头节点，算法。骨干网节点是簇头节点，普通节点是簇内节点。由于普通节点是簇内节点。由于(yuy)簇头节点需要协调簇内节簇头节点需要协调簇内节点的工作，负责数据的融合和转点的工作，负责数据的融合和转发，能量消耗相对较大，所以分发，能量消耗相对较大，所以分簇算法通常采用周期性地选择簇簇算法通常采用周期性地选择簇第25页/共80页第二十六页

18、，共81页。2.3.1 LEACH算法算法LEACH(Low Energy Adaptive Clustering Hierarchy)算算法是一种自适应分簇拓扑算法，法是一种自适应分簇拓扑算法，它的执行过程是周期性的，每轮它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的循环分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段，数据通信阶段。在簇的建立阶段，第26页/共80页第二十七页，共81页。LEACH算法选举簇头的过算法选举簇头的过程如下：节点产生程如下：节点产生01之间的随之间的随机数，如果这个数小于阈值机数，如果这个数小于阈值T(n)，则发布自己是簇头的消息。在每则发布自己是

19、簇头的消息。在每轮循环中，如果节点已经当选过轮循环中，如果节点已经当选过簇头，则把簇头，则把T(n)设置设置(shzh)为为0， ,1 mod(1/)( )0,PnGPrPT n其他(2-2) 第27页/共80页第二十八页，共81页。Pr第28页/共80页第二十九页，共81页。经过一轮选举过程，我们可经过一轮选举过程，我们可以看到如图以看到如图2-2所示的簇的分布，所示的簇的分布，第29页/共80页第三十页，共81页。第30页/共80页第三十一页，共81页。2.3.2 TopDisc算法算法TopDisc(Topology Discovery)算法是基于最小支配算法是基于最小支配集理论的经典算

20、法。它首先由初集理论的经典算法。它首先由初始节点发出拓扑发现请求，通过始节点发出拓扑发现请求，通过广播该消息来确定网络中的骨干广播该消息来确定网络中的骨干节点节点(distinguished nodes)，并结，并结第31页/共80页第三十二页，共81页。在三色法中，节点可以处于在三色法中，节点可以处于三种不同的状态。在三种不同的状态。在TopDisc算算法法(sun f)中，分别用白色、黑中，分别用白色、黑色、灰色表示三种节点：色、灰色表示三种节点：(1) 白白色表示尚未被发现的节点，或者色表示尚未被发现的节点，或者说是没有接收到任何拓扑发现请说是没有接收到任何拓扑发现请求的节点；求的节点；

21、(2) 黑色表示骨干节黑色表示骨干节第32页/共80页第三十三页，共81页。TopDisc采用两种启发方法采用两种启发方法来使得每个新的黑色节点都尽可来使得每个新的黑色节点都尽可能多地覆盖还没有被覆盖的节点：能多地覆盖还没有被覆盖的节点：一种是节点颜色一种是节点颜色(yns)标记方法；标记方法；另一种是节点转发拓扑发现请求另一种是节点转发拓扑发现请求时，将会故意延时一段时间，延时，将会故意延时一段时间，延时时间的长度反比于该节点与发时时间的长度反比于该节点与发第33页/共80页第三十四页，共81页。(3) 当白色节点收到来自灰当白色节点收到来自灰色节点的拓扑发现请求时，将在色节点的拓扑发现请求

22、时，将在等待时间等待时间TWG后标记为黑色，但后标记为黑色，但如果在等待周期又收到来自黑色如果在等待周期又收到来自黑色节点的拓扑发现请求则先优先标节点的拓扑发现请求则先优先标第34页/共80页第三十五页，共81页。为了使得每个新的黑色节点为了使得每个新的黑色节点都尽可能多地覆盖还没有被覆盖都尽可能多地覆盖还没有被覆盖的节点，的节点，TopDisc采用了反比于采用了反比于节点之间距离的转发延时机制。节点之间距离的转发延时机制。其合理性简单地解释为：理想情其合理性简单地解释为：理想情况下，节点的覆盖范围是半径为况下，节点的覆盖范围是半径为无线电发射半径的圆。于是，单无线电发射半径的圆。于是，单个的

23、节点所能覆盖的节点数目正个的节点所能覆盖的节点数目正比于其覆盖面积和局部比于其覆盖面积和局部(jb)的的发现请求。发现请求。第35页/共80页第三十六页，共81页。假设节点假设节点b比节点比节点c距离节点距离节点a更更远，即节点远，即节点b的等待时间更短，的等待时间更短，于是节点于是节点b先广播拓扑发现请求。先广播拓扑发现请求。节点节点d和节点和节点e收到来自节点收到来自节点b的的拓扑发现请求，根据步骤拓扑发现请求，根据步骤(3)各自各自等待一段时间，节点等待一段时间，节点a已经被标已经被标记为黑色，根据步骤记为黑色，根据步骤(4)它会忽略它会忽略第36页/共80页第三十七页，共81页。第37

24、页/共80页第三十八页，共81页。可以看出，三色法所形成的可以看出，三色法所形成的簇之间存在重叠区域。为了增大簇之间存在重叠区域。为了增大簇之间的间隔，减少重叠区域，簇之间的间隔，减少重叠区域，TopDisc算法同时也提出了四色算法同时也提出了四色法。顾名思义，节点可以处于法。顾名思义，节点可以处于(chy)四种不同的状态，分别四种不同的状态，分别用白色、黑色、灰色和深灰色表用白色、黑色、灰色和深灰色表示。前三种颜色代表的含义跟三示。前三种颜色代表的含义跟三第38页/共80页第三十九页，共81页。(1) 初始节点被标记为黑色，初始节点被标记为黑色，并向网络广播拓扑发现请求。并向网络广播拓扑发现

25、请求。(2) 当白色节点收到来自黑当白色节点收到来自黑色节点的拓扑发现请求时，将被色节点的拓扑发现请求时，将被标记为灰色，并在延时时间标记为灰色，并在延时时间TWB后继续广播拓扑发现请求。后继续广播拓扑发现请求。TWB第39页/共80页第四十页，共81页。(4) 当白色节点收到来自深当白色节点收到来自深灰色节点的拓扑发现请求时，等灰色节点的拓扑发现请求时，等待一段时间待一段时间(同样与距离成反比同样与距离成反比)。第40页/共80页第四十一页，共81页。如图如图2-4所示，假设节点所示，假设节点a是是初始节点，根据步骤初始节点，根据步骤(1)它被标记它被标记为黑色，并广播为黑色，并广播(gun

26、gb)拓扑拓扑发现请求。节点发现请求。节点b收到来自节点收到来自节点a的拓扑发现请求，根据步骤的拓扑发现请求，根据步骤(2)被被标记为灰色，并各自等待一段时标记为灰色，并各自等待一段时间后广播间后广播(gungb)拓扑发现请拓扑发现请求。节点求。节点c和节点和节点e都接收到来自都接收到来自节点节点b的拓扑发现请求，根据步的拓扑发现请求，根据步骤骤(3)，被标记为深灰色，继续广，被标记为深灰色，继续广任何来自标记为黑色节点的拓扑任何来自标记为黑色节点的拓扑发现请求，则被标记为黑色。发现请求，则被标记为黑色。第41页/共80页第四十二页，共81页。第42页/共80页第四十三页，共81页。与三色法相

27、比，四色法形成与三色法相比，四色法形成的簇数目更少，簇与簇之间的重的簇数目更少，簇与簇之间的重叠区域也更小。但是可能形成一叠区域也更小。但是可能形成一些孤立的标记为黑色的节点些孤立的标记为黑色的节点(如如图图2-4中的节点中的节点e)，不覆盖任何灰，不覆盖任何灰色节点。虽然三色法和四色法所色节点。虽然三色法和四色法所形成的黑色节点数目相当，但四形成的黑色节点数目相当，但四第43页/共80页第四十四页，共81页。2.3.3 GAT算法算法GAT算法是一种算法是一种(y zhn)依据节点的地理位置进行分簇，依据节点的地理位置进行分簇，并对簇内的节点选择性地进行休并对簇内的节点选择性地进行休眠的路由

28、算法。其核心思想是：眠的路由算法。其核心思想是：在各数据源到数据目的地之间存在各数据源到数据目的地之间存在有效通路的前提下，尽量减少在有效通路的前提下，尽量减少第44页/共80页第四十五页，共81页。GAT算法通常分为两个阶段：算法通常分为两个阶段：第一阶段为虚拟单元格的划第一阶段为虚拟单元格的划分。节点根据其位置信息和通信分。节点根据其位置信息和通信半径将网络区域划分为若干个虚半径将网络区域划分为若干个虚拟单元格，并保证相邻单元格中拟单元格，并保证相邻单元格中的任意两个节点都可以直接通信，的任意两个节点都可以直接通信，假设节点已知整个监测区域的位假设节点已知整个监测区域的位置信息和本身的位置

29、信息，节点置信息和本身的位置信息，节点节点通过发送节点通过发送第45页/共80页第四十六页，共81页。广播消息通告广播消息通告(tnggo)自己的位自己的位置和置和ID等信息，然后每个节点将等信息，然后每个节点将自身的定时器设置为某个区间内自身的定时器设置为某个区间内的随机值的随机值Td，一旦定时器超时，一旦定时器超时，节点发送消息声明其进入活动状节点发送消息声明其进入活动状态，成为簇头。节点如果在定时态，成为簇头。节点如果在定时器超时前收到来自同一单元格内器超时前收到来自同一单元格内其他节点成为簇头的声明，则说其他节点成为簇头的声明，则说状态。状态。第46页/共80页第四十七页，共81页。由

30、于节点处于侦听状态时也由于节点处于侦听状态时也会消耗很多热量，所以让节点处会消耗很多热量，所以让节点处于休眠状态成为传感器拓扑控制于休眠状态成为传感器拓扑控制算法中常见的方法，算法中常见的方法，GAF算法的算法的优点是在节点密集型分布的网络优点是在节点密集型分布的网络第47页/共80页第四十八页，共81页。2.4 启启 发发 机机 制制传感器网络通常是面向应用事件驱动的网络，骨干网节点在没有检测到事件传感器网络通常是面向应用事件驱动的网络，骨干网节点在没有检测到事件第48页/共80页第四十九页，共81页。2.4.1 STEM算法算法STEM(Sparse Topology and Energy

31、 Management)算法是一种算法是一种低占空比的节点唤醒机制。该算低占空比的节点唤醒机制。该算法采用双信道，即监听信道和数法采用双信道，即监听信道和数据通信信道。具体地讲，据通信信道。具体地讲，STEM算法又分为算法又分为STEM-B(STEM-第49页/共80页第五十页，共81页。在在STEM-T算法中，节点周算法中，节点周期性地进入侦听期性地进入侦听(zhn tn)阶段，阶段，探测是否有邻居节点要发送数据；探测是否有邻居节点要发送数据；当一个节点想要与某个邻居节点当一个节点想要与某个邻居节点进行通信时，它就发送一连串的进行通信时，它就发送一连串的唤醒包，发送唤醒包的时间长度唤醒包，发

32、送唤醒包的时间长度必须大于侦听必须大于侦听(zhn tn)的时间的时间间隔，以确保邻居节点能够收到间隔，以确保邻居节点能够收到第50页/共80页第五十一页，共81页。2.4.2 ASCENT算法算法ASCENT(Adaptive Self-Configuring sEnsor Networks Topologies)算法着重于均衡网络算法着重于均衡网络中骨干节点的数量中骨干节点的数量(shling)，并，并第51页/共80页第五十二页，共81页。运行运行ASCENT算法的网络包算法的网络包括触发、建立和稳定三个主要阶括触发、建立和稳定三个主要阶段。触发阶段如图段。触发阶段如图2-5(a)所示，

33、所示，在汇聚节点与数据源节点不能正在汇聚节点与数据源节点不能正常通信时，汇聚节点向它的邻居常通信时，汇聚节点向它的邻居节点发出求助信息；建立阶段如节点发出求助信息；建立阶段如图图2-5(b)所示，当节点收到邻居所示，当节点收到邻居第52页/共80页第五十三页，共81页。第53页/共80页第五十四页，共81页。ASCENT算法使得网络可以算法使得网络可以随具体应用要求而动态地改变拓随具体应用要求而动态地改变拓扑结构，并且节点只根据本地的扑结构，并且节点只根据本地的第54页/共80页第五十五页，共81页。2.5 传感器网络的覆盖控制传感器网络的覆盖控制覆盖是对传感器网络服务质量的度量，即在保证一定

34、的服务覆盖是对传感器网络服务质量的度量，即在保证一定的服务质量条件下，使得网络覆盖范围最大化，提供可靠的区域监测和质量条件下，使得网络覆盖范围最大化，提供可靠的区域监测和第55页/共80页第五十六页，共81页。2.5.1 基于虚拟势场力的传感器基于虚拟势场力的传感器网络区域覆盖控制网络区域覆盖控制虚拟势场力是把网络中每一虚拟势场力是把网络中每一个移动节点看做一个虚拟的带电个移动节点看做一个虚拟的带电粒子，相邻粒子，相邻(xin ln)节点之间节点之间同时存在排斥力和吸引力两种相同时存在排斥力和吸引力两种相互作用力。由于受势场斥力的作互作用力。由于受势场斥力的作第56页/共80页第五十七页，共8

35、1页。在无线传感器网络布局在无线传感器网络布局(bj)优化过程中，各无线传感器节点优化过程中，各无线传感器节点根据其所受合力的大小和方向移根据其所受合力的大小和方向移动相应距离，直至达到受力平衡动相应距离，直至达到受力平衡iFijFiRFiAF1, kiijiRiAjj iFFFF(2-3)第57页/共80页第五十八页，共81页。式中为无线传感器节点间的式中为无线传感器节点间的相互作用力，既有引力，也有斥相互作用力，既有引力，也有斥力。虚拟势场力算法采用距离阈力。虚拟势场力算法采用距离阈ijFththththth0,(), ),0,11, ,ijAijijijijijRijijijdCkddC

36、ddddFkdddd(2-4) 第58页/共80页第五十九页，共81页。式中为传感器节点式中为传感器节点si、sj之之间的虚拟势场力；间的虚拟势场力；kA、kR分别分别ijFij第59页/共80页第六十页，共81页。考虑到节点从受力到运动为考虑到节点从受力到运动为一个加速过程，故节点受力后在一个加速过程，故节点受力后在x轴和轴和y轴上的位移分别为轴上的位移分别为max2max,1,2xxxxxxxxvtvvsvtatvv max2max,1,2yyyyyyyyvtvvsvtatvv (2-5) (2-6) 第60页/共80页第六十一页，共81页。根据公式根据公式(2-5)、公式、公式(2-6)

37、可可得节点在得节点在x、y轴的迁移位置分别轴的迁移位置分别为为oldthnewoldth,xyxxyxFFxxsFFoldthnewoldth,xyyxyyFFyysFF(2-7) (2-8) 第61页/共80页第六十二页，共81页。图图2-6(a)和图和图2-6(b)分别为利分别为利用虚拟力对用虚拟力对10个和个和70个传感器节个传感器节点进行覆盖控制的仿真图，从仿点进行覆盖控制的仿真图，从仿真图可以看出，节点很好地部署真图可以看出，节点很好地部署在监测区域中，使得网络在监测区域中，使得网络(wnglu)覆盖率的增大最大化。覆盖率的增大最大化。值得注意的是，最终覆盖率除了值得注意的是，最终覆

38、盖率除了第62页/共80页第六十三页，共81页。第63页/共80页第六十四页，共81页。2.5.2 基于市场竞争行为的无线基于市场竞争行为的无线传感器网络连接与覆盖算法传感器网络连接与覆盖算法节点部署受环境影响，有时节点部署受环境影响，有时因为节点部署不慎，可能导致部因为节点部署不慎，可能导致部分节点丧失行动能力，而它的传分节点丧失行动能力，而它的传感与通信功能仍然保持正常。在感与通信功能仍然保持正常。在自组织的时候，如果不考虑这些自组织的时候，如果不考虑这些节点，显然会造成浪费；如果考节点，显然会造成浪费；如果考虑这些节点，则只能采用带约束虑这些节点，则只能采用带约束中间的未覆盖区域。中间的

39、未覆盖区域。第64页/共80页第六十五页，共81页。第65页/共80页第六十六页，共81页。基于市场竞争行为的无线传基于市场竞争行为的无线传感器网络连接与覆盖算法就是通感器网络连接与覆盖算法就是通过过(tnggu)研究人类社会的市场研究人类社会的市场竞争行为，提出地用于无线传感竞争行为，提出地用于无线传感器网络连接与覆盖问题的控制算器网络连接与覆盖问题的控制算法。该方法把传感器网络中的节法。该方法把传感器网络中的节点类比为市场竞争中的经济主体，点类比为市场竞争中的经济主体，第66页/共80页第六十七页，共81页。网络采用簇结构，簇内任意网络采用簇结构，簇内任意两个节点均可以通过多跳的方式两个节

40、点均可以通过多跳的方式进行通信，而簇间不能通信。对进行通信，而簇间不能通信。对于每一个独立的簇，其配置过程于每一个独立的簇，其配置过程可分为三步进行：可分为三步进行：(1) 实现动、静态的分离。实现动、静态的分离。静态传感器虽然不能移动，但其静态传感器虽然不能移动，但其用于感测与通信的能量高于动态用于感测与通信的能量高于动态。第67页/共80页第六十八页，共81页。(2) 簇的内部调整。我们知簇的内部调整。我们知道在资源有限的情况下，大型企道在资源有限的情况下，大型企业依靠其规模优势，总是能够优业依靠其规模优势，总是能够优先占有部分资源，其不能占有的先占有部分资源，其不能占有的资源将在小型企业间通过竞争得资源将在小型企业间通过竞争得第68页/共80页第六十九页，共81页。图图2-8(a)演示了这样一个过演示了这样一个过程，程，S1、S2、S3、S4、S5、S6表表示静态传感器，它们的感测范围示静态传感器，它们的感测范围用实线的圆表示，用实线的圆表示，M1、M2、M3、M4、M5、M6表示可移动传感器，表示可移动传感器，它们的感测范围用虚线的圆表示。它们的感测范围用虚线的圆表示。M1被优化配置到被优化配置到M1，其感测范，其感测范第69页/共80页第七十页，共81页。第70页/共8