摘 要
无线传感网络在国民经济和日常生活中得到深入广泛的应用，承担着数据采 集、状态测量、设备定位等众多功能。无线传感网络由大量节点通过无线自组织 方式连接而成，各个节点独立釆集数据，按照设定的路由协议传输数据到中央服 务器。针对无线传感网络在不同领域的应用特点，发展出多种路由协议。这些路 由协议在节点能耗、数据延迟、拥塞控制等方面性能各有侧重。基于地理位置的 路由协议是其中比较重要的一种，其在路由决策时主要利用节点的地理位置信息, 因而能有效控制节点能耗和快速应对网络拓扑变化。基于地理位置的路由协议的 基础是节点位置信息，而基于无线信号指纹的定位算法具有成本低，定位精度高 的特点，适用于无线传感网络中的节点定位。本文针对无线传感网络中拥塞控制、 网络能效、节点定位三个方面开展研究，并提出了相应的解决方案。本文的主要 工作内容如下：
无线传感网络中监控区域的异常事件产生的突发数据流会引发网络拥塞，导 致数据包延迟增加、节点能耗增加，严重影响网络的服务质量。针对能量受限传 感网络的拥塞问题，提出了一种基于引力竞争的拥塞控制路由算法。根据邻居节 点间的距离位置关系和节点缓存状态定义传输引力与能量引力。传输引力从数据 包到达率、缓存队列长度及数据包处理能力三方面描述节点的拥塞状态。能量引 力采用物理距离估算节点剩余能量，并考虑下游节点的能量分布。根据物理学中 功的原理，引入引力竞争强度表示位移，节点引力和引力竞争强度相乘为功，选 择功最大的节点为下一跳节点。针对具备能量补充功能的无线传感网络的拥塞问 题，提岀了一种基于虚拟力的流量感知路由算法。算法依据源节点、邻居节点以 及目的节点之间的距离关系定义虚拟内力，以构建数据包的最长单跳距离。定义 虚拟外力以感知前向区域数据流量，沿着空闲或低负载节点构建路由。虚拟外力 和虚拟内力融合成虚拟合力，从而驱动数据包避开拥塞区域，并尽快传输到目的 节点。
对于能量受限的传感器节点，提高能效能够延长无线传感网络生命周期，提 升网络可用性。基于地理位置的路由可以根据节点距离选择最佳传输功耗，由此 提出一种多参数融合能效路由算法。算法定义了五个路由评估参数，包括节点剩 余能量、有效转发率、单跳传输比、缓存队列指数和能量均衡度。每个参数从不 同角度反映网络及节点的状态。引入可信度系数评估各个参数在路由决策中的可 信程度，参数贡献度反映各个参数之间的重要性差异。对于网络中的随机干扰引 起的距离测算误差引入模糊贡献度表示。参数贡献度和模糊贡献度合并为融合贡 献度，选择最大融合贡献度的节点作为下一跳节点。
地理位置路由决策需要节点位置信息，此外在物流和医疗等领域的无线传感 网络应用中也需要对节点进行精确定位。诸多定位算法中，免测距的指纹定位算 法对节点功能要求低、定位时间短、精度高、部署成本低，近些年获得学术和产 业界的很大关注。指纹定位包括两个阶段，离线测量阶段建立定位区域无线信号 指纹与位置坐标关系数据库；在线査询阶段根据特定算法估计未知节点坐标。本 文提出了两种指纹定位算法，分别针对单区域和多区域节点定位。针对单区域节 点定位，提出一种基于高斯分布的指纹定位算法。首先用利用模糊方法融合未知 节点指纹与数据库指纹形成模糊决策矩阵。算法以锚节点数量为维度建立多维高 斯分布模型，利用马氏距离估算未知节点偏差，选择偏差最小的K个参考节点 利用质心法估计未知节点坐标。针对多区域复杂环境定位，依据知识决策理论， 提出一种基于模糊决策的指纹定位算法。将定位过程分为三个阶段：知识积累阶 段，采用模糊融合形成定位决策矩阵；知识融合阶段，应用拉格朗日优化算法求 得不同区域中锚节点的隶属度权重；知识扩展阶段执行定位决策，计算参考点匹 配度，将匹配度最高的参考点坐标作为未知节点的位置估算值。
本文工作围绕无线传感网络的拥塞控制、能效优化和节点定位展开，以节点 间物理距离为出发点，有针对性地提出了路由算法和指纹定位算法，并通过理论 分析和软件仿真验证了所提算法的有效性。
关键词：无线传感网络地理位置路由拥塞控制能效指纹定位
目录
摘 要 I
ABSTRACT Ill
第1章绪论 1
1.1研究背景及意义 1
1.2无线传感网络路由研究现状 2
1.2.1无线传感网络路由特点 3
1.2.2WSN拥塞控制研究现状 5
1.2.3WSN能效路由研究现状 6
1.2.4WSN地理位置路由研究现状 8
1.3无线传感网络节点定位研究现状 9
1.3.1无线传感网络节点定位 10
1.3.2WSN指纹定位研究现状 16
1.4本文的主要研究内容及贡献 19
1.5本文的组织结构 20
第2章 基于地理位置的WSN拥塞控制路由 22
2.1引言 22
2.2基于引力竞争的拥塞控制路由 23
2.2.1系统模型 23
2.2.2节点的引力场描述 24
2.2.3拥塞控制路由策略 28
2.2.4仿真结果与分析 31
2.3基于虚拟力的流量感知路由 35
2.3.1系统模型 36
2.3.2虚拟力流量感知路由 36
2.3.3仿真结果与分析 40
2.4本章小结 45
第3章 基于地理位置的WSN能效路由 46
3.1引言 46
3.2系统模型 46
3.3路由评价参数 47
VI
3.3.1能量均衡度 48
3.3.2单跳传输比 49
3.3.3有效转发率 50
3.3.4缓存队列指数 51
3.3.5剩余能量因子 51
3.4基于多参数融合的能效路由算法 52
3.4.1路由决策过程 52
3.4.2路由选择策略 53
3.5仿真结果与分析 55
3.5.1调整因子的影响 56
3.5.2算法对比分析 57
3.6 本章小结 60
第4章 基于高斯分布的单区域节点定位 62
4.1引言 62
4.2定位算法基本概念 62
4.2.1基本术语 62
4.2.2信号传播模型 63
4.3构建指纹数据库 64
4.3.1指纹数据预处理 64
4.3.2RSS模糊融合与分析 65
4.4多维高斯分布定位算法 67
4.4.1多维高斯分布模型 67
4.4.2理想点与参考节点的距离偏差 68
4.4.3未知节点坐标估计 69
4.5仿真结果与分析 69
4.5.1定位精度评价 69
4.5.2仿真数据性能分析 70
4.5.3真实数据集测试 73
4.6本章小结 75
第5章 基于模糊决策的多区域节点定位 76
5.1引言 76
5.2知识决策理论 76
5.3模糊决策定位算法 77
5.3.1知识积累 78
VII
XI
第1章绪论
1.1研究背景及意义
近年来，海量的智能终端已连接成一个庞大的物联网。物联网使用诸如智能 感知、模式识别和普适计算之类的通信感知技术以实现物理世界和网络空间的全 面集成⑴。随着5G的普及，各种设备通过物联网进行连接访问将大大增加。根 据IDC的报告，到2025年全球的物联网设备数量将达到416亿台，产生的数据 将达到79.4ZB【2］。物联网将成为数据驱动型经济的基础和支柱。
作为物联网的底层基础接口⑶，无线传感网络(Wireless Sensor Network, WSN)具有功耗低、体积小、成本低、分布式和自组织的特点〔4】。许多物联网应 用(例如环境监控⑸、智能小区［6］、能源管理［7】、智能家居［8］等)都基于WSN构 建。在数据收集、传输和处理过程中，WSN使用无线传输并将数据以单跳或多 跳的方式发送到宿节点(sink节点)或基站【9］。但传感器节点有其自身的能量限 制，这会影响无线传感网络的寿命。因此，降低传感节点的能耗、提升数据传输 效率和扩展网络生命周期是无线传感网络领域的重要研究内容。
无线传感网络路由算法的主要功能是从源节点到sink节点之间规划一条最 优路径，数据包沿着该路径准确、高效、快速地到达sink节点。路由算法设计策 略和优化方法对无线传感网络的性能具有极其显著的影响。根据路由算法设计中 使用的辅助信息，将WSN路由算法分为两类：基于拓扑结构的路由算法和基于 地理位置的路由算法。基于拓扑结构的路由算法需要每个节点维护一张路由信息 表，因此节点路由决策快，在网络稳定时能确保数据包的服务质量稳定可靠。但 需要要定期更新路由表以适应无线传感网络拓扑的动态变化，从而产生更多的路 由开销。
在基于地理位置的路由算法中，节点无需存储全局路由信息，存储和处理开 销较低，易于实现，具有良好的可扩展性。此类算法在进行路由决策时主要依据 使用节点的位置信息，每个节点维护一张包含邻居节点位置信息的信息表，并定 期更新该表。基于地理位置的路由算法可以有效快速响应动态变化的网络拓扑。 但是，仅使用地理信息进行贪婪的数据转发会对整个网络的能源效率产生负面影 响。因此，以便在能源效率约束下实现更好的网络性能。
无线传感网络节点定位指在确定传感器节点在某个绝对或相对坐标参照系 中的位置的过程。在基于位置服务(Location Based Services, LBS)的WSN应用 中卩°】，比如地下矿井的矿工定位⑴］、医疗护理〔⑵等，节点位置信息对其功能的
有效运行至关重要。基于地理位置的WSN路由和数据聚合也严重依赖定位机制。 对于许多需要定位功能的系统或应用，卫星导航定位系统(GPS、北斗等)通常 能够满足要求。然而，基于卫星导航的定位方法有两个缺点卩3〕。首先，卫星导航 定位系统的定位机制要求WSN节点与多颗导航卫星满足视距通信，但大多数 WSN部署在对无线信号有遮挡的环境，例如，高层建筑内部、室内、水下、森 林或山区，导致无法接收到有效的卫星定位信号。其次，卫星导航定位装置价格 昂贵，会增加WSN部署成本。因此，WSN节点定位的研究重点是节点自定位技 术卩4〕。
无线传感网络的节点定位算法分为两类：基于测距的定位算法和免测距定位 算法卩4】。测距类算法使用专用部件测量距离或角度，再依据简单的几何关系确定 节点位置。专用测量硬件，增加了传感网部署成本。免测距定位算法具有成本优 势。而且随着通信技术的急速发展，近年涌现出许多基于RSS (Received Signal Strength)指纹的定位算法研究。RSS指纹定位过程分为离线测量和在线査询两 个阶段卩5〕。离线阶段将参考节点上收到的RSS信息进行统计和处理，建立指纹 数据库；在线阶段，将未知节点的RSS信息与指纹数据进行比对，从而估算未 知节点的位置。但由于WSN部署环境存储各种干扰，导致RSS测量误差较大且 不稳定，影响了节点定位精度。实现干扰环境下未知节点与参考节点间的地理坐 标相似度的准确衡量，维持定位精度的稳定性需要进一步的研究与探讨。
1.2无线传感网络路由研究现状
无线传感网络由大量传感器节点以自组织方式组网而成，用于信息收集和全 面综合监测。每个节点都具有感知、通信和计算功能。它们通过无线信号以多跳 和自组织的方式相互通信。在目前的发展形势下，无线传感网络在智慧生活卩J”］、 工农业生产卩8-21］、能源领域【22-23］、灾害预防和控制【24-25］、军事应用【26］等领域得到 了广泛的研究和应用。特别是物联网的不断发展，加速了无线传感网络技术的发 展和部署，并逐渐促进现代生活向着数字化和智能化方向演进。
无线传感网络中，节点之间以无线方式通信，按照自组织方式进行数据传输。 无线传感网络路由算法的功能是将源节点的数据包逐跳传输到目的节点，主要包 括两个任务：一是规划源节点和目的节点之间的最优单跳或者多跳路径；二是该 优化路径上的节点依次转发数据。由于任一节点既可以感知环境、采集数据，也 可以转发、中继数据。每个节点都具备恢复链路连接、位置定位、拓扑发现和路 由决策能力。因此，无线传感网络中的路由算法是分布式的、路由策略可以是单 跳路由、多跳路由和全路径路由。
能量受限的传感器网络中，传感器节点由电池提供能量，大多数节点没有外
部能源补充，因此路由算法需要考虑能量效率。同时传感器节点由于计算能力和 存储容量的限制，无法承担复杂的路由计算，也难以保存全网路由信息表。此外， 由于传感器节点数量多且节点通信范围有限，节点通常只保存局部拓扑信息。因 此，有线和无线网络的常规路由算法并不适用于无线传感网络。无线传感网络路 由算法所要考虑的因素也相对较多，如能量、局部拓扑信息、可扩展性、复杂度 和路由更新策略等。
1.2.1无线传感网络路由特点
无线传感网络路由于受能量、功能和通信能力的限制，源节点和sink节点 之间通常无法直接通信。数据包从源节点，通过中间节点逐条或多跳转发，传送 至sink节点。因此，无线传感网络的路由算法具有不同于传统网络的显著特点【3- 52刀，主要体现在以下五个方面：
（1） 节点性能受限
由于传感器节点成本低、体积小，其运算处理能力、数据存储能力和网络连 接能力都受到限制。能量受限的传感网络节点，常用小型电池供电、能量无法补 充。因此其路由算法的主要目标是提升节点能效，以延长网络生命周期。路由算 法不仅考虑单个节点的能耗，还需要考虑邻近区域，甚至整个网络能耗。能量管 理机制是路由算法的重要组成部分。对于具备能量补充功能的无线传感网络，能 效不是路由算法的主要目标，算法更注重网络吞吐率、端到端延迟等网络QoS性 能。
（2） 网络信息有限
传感器节点体积小，存储和计算能力弱，无法存储大量路由信息并执行复杂 的路由计算。节点只能存储自身周围邻近区域的局部拓扑信息，以及少量的全局 路由信息。节点需要根据有限的局部拓扑信息找到一条到目的节点的有效传输路 径，这是设计传感网络路由算法时要考虑的基本问题。这条路径还需要满足能效 以及QoS要求。
（3） 以数据为中心
无线传感网络通常只关注监视区域中具体的物理观测值，而不关心获取此观 测信息的节点，形成以数据为中心的转发路径。无线传感网络中的源节点根据应 用层业务需求感知环境和获取数据，将数据以逐跳方式传输到指定的目标节点。 此过程无需在任何两个节点之间建立固定路径，因此路由效率是设计路由算法要 考虑的问题之一。
（4） 网络拓扑
由于传感器节点损坏、电源耗尽或信号干扰等因素影响，无线传感网络的拓
扑结构处于动态变化之中，会随部署时间延长产生显著变化，且变化方式难以预 测，这要求路由算法具有一定的可扩展性，能适应网络拓扑结构的动态变化。
(5)应用相关
无线传感网络的应用场景有非常显著的差异性，路由算法的设计要针对具有 应用场景具体需求进行优化。因此很难设计一种统一的、全场景路由算法。在实 际应用中，通常根据具体应用场景的特点和需求，设计与之匹配的路由算法。
1.2.1.1,无线传感网络路由分类
无线传感网络路由算法的功能是给出一系列规则，数据包按照这些规则在网 络中进行传输。典型路由算法可归类为数据中心路由、层次路由、地理位置、机 会路由和QoS感知路由。每种路由算法简要介绍如下：
(1)数据中心路由
在大规模无线传感网络中，大量的节点随机部署。由于位于同一区域的感知 节点可能会感知到相同事件，导致这些感知节点的数据包含大量冗余信息。若直 接发往sink节点，传输冗余信息会耗费大量能量，能量有效利用率低。数据中心 路由算法利用属性命名聚合数据，以消除数据冗余，因此能降低能耗［28】。典型的 数据中心路由算法主要有泛洪路由、Gossiping路由、rumo路由、定向传播路由 和SPIN路由等。
(2)层次路由
层次路由又称簇路由。将若干传感节点划分为簇，每个簇按照某个规则选择 一个节点作为簇头。簇头执行数据聚合、路由决策和数据转发等功能，而簇内的 其他节点执行环境感知和数据釆集任务。层次路由算法的优点是扩展性好，且层 次拓扑结构也能获得较高能效〔29］。典型的层次路由算法有LEACH〔3。］和TEEN【31］ 等。
(3)地理位置路由
地理位置路由使用节点间地理位置信息进行路由决策，其基础是计算两个节 点之间地理距离，并估算数据传输的能量需求，从而实现较高的能量效率和较低 的端到端传输延退。节点间距离可以通过接收信号强度确定，也可以使用GPS (Global Positioning System)等定位设备进行定位。典型的地理位置路由算法有 GEAR132】、GPSRD3］和 GAF【34〕等。
(4)机会路由
传统路由算法是选择下一跳节点，然后向其转发数据。新节点再选择下一跳 直到到达sink。这些算法本质上是一种确定性方法，每次只选择一个节点，然后 必须将数据转发到该节点。如果数据传输过程中，节点死亡，会导致数据丢失。
机会路由是从其邻居节点中选择一组节点，然后按照某种规则从这组中选择一个 节点尝试发送数据，如果发送成功则继续下一跳。如果不成功，则选择组内的另 一个节点发送，直到数据成功传输或者达到最大发送次数。机会路由提高了数据 传输的可靠性的。典型的机会路由算法有ExOR［36］、EEOR［37］和EDOR［38］等。
(5)QoS感知路由
上述路由算法也具有一定的QoS感知能力，其路由决策目标包括能效最优， 延迟最低等，但并没有对这些指标设定具体值。QoS感知路由对网络QoS指标 有具体的量化值需求，比如端到端网络延迟，数据包优先级等。基于量化QoS指 标去设计和优化路由〔39］,可以获得更好的传输质量，满足特点领域的路由QoS 需求。SPEED®是经典的QoS感知路由算法。也有一些QoS感知路由对QoS没 有具体值，以最大或最小某个指标为优化目标，比如最大生存期的能量路由，最 大生存期数据汇集路由、最低转发成本路由等。
1.2.2 WSN拥塞控制研究现状
WSN路由算法的一个主要设计目标是最大程度节省各节点能耗、实现网络 能量均衡，从而最大限度延长网络生存时间。但在WSN中，当许多传感器同时 发送数据时，很可能会造成数据包拥塞；或者当某个传感器连续不停地发送数据 包时，也有可能发生拥塞。拥塞发生时，网络的数据包丢失率会增加，网络整体 传输效率将受到影响。无线传感网络中的拥塞问题与传统网络中的拥塞问题完全 不同。当前大多数拥塞控制算法试图通过降低源节点发送数据的速率以缓解拥塞。 但是，这种流量控制方案总是降低吞吐量。因此，拥塞控制成为WSN路由算法 设计的一个关键挑战。
(1)基于负载均衡的拥塞控制
这类算法通过监测并控制各个节点的缓存队列以达到节点间负载均衡的目 的，从而缓解网络拥塞状态。文献［41］提出了一种流量感知动态路由算法TADR, 利用势能场概念，以节点数和节点缓冲容量建立混合虚拟势能场，充分利用空闲 或负载不足的节点，使数据包避开拥塞，最终转发到sink。算法提升了网络吞吐 量，降低了路由开销。文献［42］提出了一种基于队列利用率的QU-RPL算法，依 据相邻节点的队列利用率和到边界路由器的跳数选择路由，实现了负载均衡并提 高了端到端的数据包交付性能。
(2)基于预测的拥塞控制
这类算法根据节点队列状态和其他信息预测拥塞的产生，根据预测结果调整 路由策略。文献［43］提出的DPCC是一种分布式预测性拥塞控制算法，利用节点 的队列占用率和信道估计器(可预测信道质量)预测拥塞，并利用节点的逐跳反
馈信息进行拥塞控制，自适应地为数据包选择传输路径，从而缓解网络拥塞。文 献［44］构建一个排队网络模型预测节点的拥塞程度，并借助水力学中的流量原理， 提出了 一种基于拥塞控制的优化路由算法CCOR。算法根据节点位置和数据包服 务速率构造网络排队模型，根据链路流量分配每条路径的路由选择概率，从而降 低了丢包率。文献［45］针对认知无线网络中的拥塞控制，提岀了一种的主动队列 管理算法MAQ,目标是动态变化的网络中基于多模型预测控制策略使节点TCP 队列保持稳定。文献［46］考虑多个因素，例如跳数、剩余能量、缓冲区占用率和 转发率，使用模糊逻辑确定因素权重，最后使用指数平滑法进行拥塞预测。所提 算法具有高吞吐量、低丢包率，延长了网络寿命。文献［47］提出了一种支持向量 机SVM和人工神经网络ANN结合的拥塞检测和预测算法，具有较高的准确度。 文献［48］提出的MOPC协议预测节点拥塞程度，依据节点的拥塞预知度、剩余能 量和最小跳数确定节点的转发满意度，进而建立路径满意度模型并选择最优路径， 降低了拥塞发生概率。
(3)基于流量感知的拥塞控制
此类算法主动感知节点流量，针对不同的流量状态采用不同的转发策略，从 而提升网络吞吐量，降低丢包率。文献［49］针对无线传感网中的可变流量模式， 提岀了一种混合CSMA/TDMA的拥塞控制算法iQueue-MAC。算法使用基于竞 争的CSMA机制，提供低延迟和分散传输。当流量增加时，iQueue-MAC更改为 无竞争TDMA机制。iQueue-MAC减轻了数据包缓冲并减少了数据包延退。文献 ［50］根据无线传感器网络中的数据传输与水管中的水流之间的相似性，提出了一 种流量感知路由算法TER。算法根据节点物理距离和流量负载构建管道模型，强 制数据包避开拥塞区域。所提算法在全局能耗、时效性和可靠性方面具有更好的 性能。文献［51］提出了一种主动队列管理算法AQM,结合随机早检测与模糊比 例积分控制器以感知网络流量。当拥塞发生时，算法控制目标缓冲队列，估计和 调整每个节点的发送速率，降低了数据丢包率和端到端延迟。文献［52］提出了一 种基于优先级的流量控制机制，将流量分为高优先级实时流量与低优先级非实时 流量，并根据优先级区分服务，保证了高优先级的延迟要求。
1.2.3 WSN能效路由研究现状
无线传感网络的QoS服务质量取决数据包的传递效率，传感器节点采集的 数据需要快速、可靠、安全地传递到目的节点(sink节点或网关)。为了解决这一 问题，许多学者研究出了多种路由算法，多数路由算法只强化了某一方面的指标， 比如追求最小能耗、最大网络寿命或最小延迟时间，无法实现多个指标的良好的 平衡。对于在复杂、危险区域部署的无线传感器网络，其节点通常采用一次性电
池供电，并且难以更换。针对此类能量受限的WSN,为了延长网络的服务时间， 需要合适的路由策略以避免个别节点由于转发大量数据而能量耗尽。因此能效成 为无线传感网络路由算法中的重要考虑因素。
WSN在不同的应用领域对数据传输的QoS要求不同，在能效约束前提下， 针对不同的目标釆用不同的方式进行优化。文献［53］针对节点睡眠/唤醒模式时隙 调度问题，提出了一种能效多属性时隙调度算法MATSS,对，基于距离最短和 能效最长选择路由，以最大限度地延长网络寿命和最大化吞吐量比。文献［54］以 最小的路由开销为目标，提出了一种基于三角模糊的谱聚类路由算法TF-SCR= 算法基于节点剩余能量和接收信号强度对节点应用谱聚类分组，然后应用三角模 糊隶属函数选择具有最高剩余能量和信号强度的节点作为簇头。所提算法提高 WSN的网络寿命和可靠性。文献［55］针对汇聚节点能量消耗过快的问题，提出了 一种基于移动节点的分布式环形路由协议，可以实现负载平衡，并在全网络中实 现能源消耗均衡。文献［56］提出了一种新的路由协议ECFP,利用节点与Sink节 点的最短跳数建立簇首竞争半径，选择剩余能量较高、链路质量较好的节点为簇 首，然后基于虚拟力模型进行非均匀分簇，在能耗均衡性和网络生存时长都具有 较好的性能。文献［57］针对WSN中对时延的要求，提出了基于多路径代价函数 的能效地理路由算法M-EEGR,综合考虑节点间能量的统计参数、路径能耗、网 络总能量和路由跳数，并通过DATF优化算法使路径上节点个数最小化，满足时 延需求，保证网络QoS的同时，实现了网络能量消耗的均衡。
路由决策过程中考虑节点的剩余能量，并尝试使用高能量节点转发数据以延 长网络寿命。同时，引入距离因素可以在一定程度上避免能耗过高和较长的传输 路径。文献［58］提出了一种自适应动态多约束路由方法，基于多属性决策方法进 行动态路由选择，通过延长高连接节点的生命周期和优化数据传输提高网络生命 周期。文献［59］针对关键节点能耗过快的问题，提出了一种基于下一跳节点剩余 能量动态调整前向角度的蚁群路由算法DAFARE。算法将剩余能量和节点距离 引入蚁群算法概率转移函数，根据前向角度范围内节点剩余能量情况剩动态调整 前向角度大小，避免了关键节点过早死亡。文献［60］设计了一种基于剩余能量和 通信代价的路由算法。该算法依据剩余能量选择簇首，然后依据最小通信代价和 最大剩余能量选择下一跳，实现了各节点能耗均衡。文献［61］提出了一种基于 LEACH的能效分簇路由策略。此策略根据两种能量级别分簇；选择能量较低的 普通节点作为簇成员，选择更多剩余能量的节点作为簇头。同时，该策略以到达 sink的最小距离作为路由标准。在文献［62］中，作者提出了基于剩余能量级别的 分簇协议CPREL,可以有效地平衡所有节点的能量消耗并延长网络寿命。文献 ［63］提出了基于非线性权重粒子群优化路由算法NWPSO,同时考虑能量效率和 传输距离，从而延长网络生命周期。文献［64］提出了基于改进蚁群算法的路由算 法，分析节点距离、传输方向和剩余能量，计算出源与目标之间的最佳路径，从 而降低网络能耗，延长网络生命周期。
上述研究都是基于数据传输的能效优化展开，通过均衡流量负载和减少控制 消息的传输能间接降低WSN的能耗。文献［65］提出了一种基于树的随机切换算 法RaSMaLai,将一些传感器节点从其原始路径随机切换到其他负载较低的路径， 以实现全网节点的负载均衡，进而达到延退WSN生命周期的目的。文献［66］针 对无线传感网络中的邻居发现服务，提出了一种TMLL模型，设计了 Nihao邻 居发现协议。协议通过控制信标减少邻居发现协议中的空闲侦听，降低控制信标 的信道占用率，降低了节点控制消息的能量开销。
文献［67-69］表明实施能量平衡路由也是延长网络寿命的有效手段。文献［67］ 提出了一种基于博弈论的分布式路由算法。算法通过平衡区域间和区域内节点通 信负载，延长了网络寿命。文献［68］将监测区域建模为以sink为中心的同心区域， 并提出消除能量孔的机制。此机制平衡了环中总节点的能量损失，并延长了网络 寿命。为了有效地减少和保持网络能量平衡，文献［69］针对条状WSN提出了一 种基于精确距离的传输方案，旨在实现不同区域的最佳传输距离，从而使网络寿 命达到最大值。
1.2.4 WSN地理位置路由研究现状
在WSN路由算法中，地理位置路由由于其良好的可扩展性和高效率，在无 线传感网络路由算法中获得广泛关注。传统地理位置路由算法采用贪婪策略转发 数据卩。」，利用本地位置信息而非全局拓扑信息建立路由，选择最接近目的节点的 邻居作为下一跳节点。贪婪路由策略完全依据邻居节点和目的节点间的地理距离。
然而，在基于地理位置路由在数据传输中，由于节点间的无线链路可靠性较 差，简单贪婪转发导致丢包率比较高。在能量受限的WSN中，简单贪婪转发导 致传感器能量无效消耗，造成节点过早死亡，形成路由空洞PH,导致网络生存期 缩短。因此，提高能效、实现负载平衡和延长网络寿命是无线传感网络地理路由 的重要考虑因素。此外，地理位置路由设计中还需要避免路由回路，防止数据包 反向传递，造成能量损耗和延时增加。
路由空洞是指节点收到信息后，无法再将其转发到目的节点附近。贪婪路由 策略选择最近的邻居节点转发数据，往往会导致造成路由空洞。针对路由空洞问 题，文献［71］提出了一种REACT地理路由算法，利用sink节点的通信距离和 RSSI,通过在每一步自选下一跳，同时执行数据聚合和构建路由。所提算法实现 了有效的数据传输，克服了贪婪转发的不足。文献［72］提出了一种能量感知双路
8
径地理路由协议EDGR, EDGR利用节点地理位置信息、剩余能量和能耗特性自 适应地进行路由决策，并实现了节点间负载均衡，有效地解决了资源受限WSN 中的路由空洞。
能效是能量受限的WSN中的一个关键问题，地理位置路由同样也需要关注 能量的有效利用。文献［73］提出了一种节能的多播地理路由协议EMGR。EMGR 按照预先设定的能量指标选择一组目的节点和源节点组成能量感知组播树，以引 导组播消息传递，并自适应地选择最接近能量最优中继位置的节点作为下一跳。 提出协议在低能耗、控制开销、计算复杂度和高数据包交付率方面实现了提升。 文献［74］设计了基于分簇的地理路由算法GRCS,引入了分簇机制，实现了动态 优化路由，定期选出的新簇头会选择最近的节点用作转发数据，从而使能源消耗 更加均衡。
在能量无限的WSN中，路由算法的目标提高数据传输质量，即降低丢包率 和端到端延迟，提高数据交付率等。文献［75］提出了一种基于位置辅助的定向缓 存代理路由协议D-CALAR,其组合了位置和地理辅助多播(Geocast),提高了 数据包的传递率，降低了平均延迟。
地理位置路由的基础是节点要掌握邻居节点的位置或距离信息，路由决策首 先要确定节点间的距离关系。文献［76］提出了一种节点坐标恢复方法，在节点部 署时将所有节点的地理坐标编码后保存在每个节点中，每个节点根据保存的坐标 以贪婪路由方式传输数据，克服了贪婪路由易陷入局部最小的特点。文献［77］针 对贪婪路由应用中的节点坐标构建问题，提出了一种贪婪距离向量路由协议 GDV和虚拟定位协议VPoD。VPoD为每个节点分配一个虚拟空间位置，GDV根 据节点间的虚拟欧式距离选择路由，所提算法对动态网络具有很好的适应性。文 献［78］针对WSN中距离估计问题，提出了一种InPhase方案，通过IEEE 802.15.4 芯片的相位测量并结合功率谱密度，推算节点之间的距离。
1.3无线传感网络节点定位研究现状
无线传感网络广泛应用于各行各业，承担着直接感知客观世界的功能。在有 些无线传感网络应用中，传感器节点位置信息对于感知数据非常重要，比如军事 应用、山火监控、医疗护理等。节点位置信息和感知数据紧密耦合，缺少位置信 息的数据会毫无意义。比如突然事件检测，只要知道事件的具体位置，才能根据 采集的数据做出正确的决策。山火监控中，传感器节点釆集的数据必须知道确切 的位置，才能在及时确定山火的区域和位置坐标。在基于地理位置的路由中，路 由决策的前提是节点知道邻居节点的位置或者是与邻居节点距离，根据这些位置 或距离信息选择最佳路由。路由的效率和能耗取决于节点坐标和位置的精确性。
确定节点位置最简单的方式是在部署无线传感网络的时候，测量节点位置。 但这种方式不适合通常无线传感网络的随机部署。给节点配备卫星导航模块，依 靠卫星导航精确定位节点坐标。但卫星导航模块价格昂贵且能耗过高，不适用于 于微小型、廉价传感网络使用。而且在地下、室内等恶劣环境中，根本无法接收 卫星导航信号。因此，低成本、高精度的无线传感网络节点定位研究称为无线传 感网络的一个研究热点。
通常的无线传感网络定位算法是在定位区域部署少量位置精确、功能强大的 信标节点，信标节点的信号发射范围覆盖整个定位区域。未知节点测量信标节点 的信号指标，在结合其他几何或者概率算法从而推算未知节点坐标。算法的区别 在于测量的指标和推算算法不同，导致不同的定位精度。定位算法还要考虑无线 信号传播时的不确定性以及定位环境干扰对定位精度的影响。
1.3.1无线传感网络节点定位
无线传感网络节点定位算法通常可分为两类：基于测距的定位算法(Range- Based)和免测距定位算法(Range-Free)。基于测距的算法通过测量未知节点与 信号发射节点之间的无线信号角度或传播时间，利用几何关系推算节点未知。测 量的信息包括接收信号强度RSS (Received Signal Strength).信号到达时间(Time of Arrival, To A)㈣、信号到达时差(Time Difference of Arrival, TDo A )网以及 信号到达角度(Angle of Arrival, AoA)団〕。这些算法通常需要部署特殊部件获取 这些变量，并通过多次测量以提高定位精度，导致产生较高的部署成本。相比之 下，免测距定位算法只需锚节点和网络连接的信息，因此在部署上成本更低，无 需额外的硬件支持，但定位精度有限。
指纹定位算法属于免测距定位算法，需要在定位区域预先布设若干位置固定 的锚节点和参考节点，锚节点以额定功率持续发射无线信号，在每个参考节点位 置测量各个锚节点的信号RSS。单个参考节点位置和其测量的RSS组成位置指 纹，简称指纹。未知节点也测量各个锚节点的RSS,并于己有的指纹进行模式匹 配，从而确定节点位置。指纹定位算法不仅部署成本低，而且在复杂多变的传播 环境中，如多径和NLOS (Non-line of Sight)环境，具有更准确的定位性能，因 此近些年得到广泛研究和应用。
1.3.1.1.基于测距的定位算法
测量定位算法的定位过程分两个步骤：一是未知节点进行距离/角度测量， 二是将测量结果整合并计算节点位置。
(1)信号测量
测量方式对基于测距的定位算法性能有着重要影响。常用的信号测量技术包 括以下四种性 信号强度指示RSS、到达时间ToA、到达时差TDoA和到达角度 AoAo
•信号强度指示RSS
RSS表征节点接收到的信号强度的大小，单位是dB。某点的无线信号强度 与该点到信号源距离的平方成正比，这种关系构成了 RSS定位的基础。若已知 发射节点的信号功率，接收节点通过接收信号强度估算其与发射节点间的距离。 信号强度指示的优点是不需要专用硬件，传感器自身的无线收发设备自带RSS 测量功能。而在实际应用中，定位环境中的物理障碍（如墙壁、人体等）会吸收 和反射无线信号，而不同的环境对无线信号的传播有不同的影响。因此，在真实 环境中，RSS测量容易受到噪声干扰，导致实际RSS与距离关系很少与理论一 致。
•到达时间TO A
TOA表示无线信号在两个节点之间传播所用的时间。测量TOA需要发射节 点和接收节点具备同步时钟。发射节点发出的定位信号中包含了发射时间，当信 号到达接收节点时，它会记录到达的时间，并计算出信号的传输时间，结合光速 估计两个节点之间的距离。TOA测量的主要缺点包括：需要精确时钟同步；多径 效应导致记录接收时间比较困难；在定位信号中加入发射时间，增加了通信开销。
•到达时间差TDOA
TDOA指两种速度不同的信号或者两个发射节点发出的信号到达同一节点 的时间差值。TDOA不必测量无线信号传播的绝对时间，因此无需节点间的时间 同步。根据无线信号到达时间与第二个信号（通常为音频信号）之间的差异计算 两个节点间的距离。如果采用两种信号计算时间差，则需要为每个节点装备音频 接收装置。发射节点发送无线定位信号，等待间隔，后发送声波信号。接收节点 在收到无线定位信号时，同时开启音频接收装置以检测传入的音频信号。基于 TDoA的定位有较高的准确度，但音频装置提高了成本。
•到达角度（AOA）
AOA表示接收节点收到信号的方向与某一水平线（包含发射节点的水平线） 间的夹角度数，也称为信号方向相对于接收节点的到达角。当节点接收定位信号 时，根据不同位置的接收装置收到信号的不同相位，计算处信号到达角度，确定 信号发射节点的位置。测量信号的不同相位，需要配备多个信号接收阵列单元。 接收阵列单元的数量、单元间距以及SNR （Signal-to-NoiseRatio）都会影响定位 性能。但WSN小巧的节点也无法设置多单元接收阵列，因此AOA技术面临的主要挑战是昂贵的硬件成本。
(2)节点位置计算方法
根据测量的信号角度、到达时间和信号强度，利用特定方法就能确定节点位 置坐标。最常用的方法是三角测量法、三边测量法和概率法。计算过程中，锚节 点的坐标和间距是已知量。三角测量法使用节点方位角进行定位，而三边测量法 使用节点间的距离定位节点。最常用的概率法是极大似然估计MLE (Maximum Likelihood Estimation)和贝叶斯推理。
• 三角测量法(triangulation)AoA测量获得未知节点相对于锚节点的方位角a和0,如图1-1所示。根 据公式(1-1)计算未知节点的垂距d,就可以推算岀未知节点坐标。
式中，Z为锚节点1和锚节点2间的距离。
• 三边测量法(trilateration) 三边测量法如图1・2所示，未知节点根据获取的锚节点RS，值，换算为距
离节点之间的距离凡，根据公式(1-2)确定自己的坐标。
(x-x^ +(y-y^ =Rf z = 1,2,3
•概率法
概率法使用无线信号概率模型表示系统状态和测量数据间的关系。在极大似 然估计MLE中，系统状态参数通过最大化测量数据似然度得到。MLE用于对没 有先验信息的模型参数进行估计。贝叶斯推理系统使用先验息和测量数据进行估 计，然后应用贝叶斯定义反复迭代得到未知节点坐标。
12
图1・2三边测量法示意图
Fig. 1-2 Illustration of trilateration
1.3.1.2.免测距的定位算法
相比基于测距的定位算法，免测距定位算法无需配备昂贵的测量装置，降低 了定位成本。免测距定位算法可概括为三类，即基于锚节点近似算法、基于连接 的算法和事件驱动的算法。
(1)基于锚节点近似算法
此类算法在定位区域布设若干锚节点和参考节点，锚节点具有发射信号(无 线信号、红外或声音)功能。首先根据某种模式大致确定出未知节点周围的锚节 点数量。然后再利用其他方法确定节点位置。最常用、最简单的方法是质心法。 设网络中布设了 〃个位置已知的锚节点，锚节点坐标为3双)通常将锚 节点排列为规则的网状拓扑，比如矩形网状拓扑。未知节点根据某种模式选择岀 周围的若干锚节点，这些锚节点连接成一个多边形，多边形的质心就是未知节点 位置。为了最大限度地减少定位错误，该方法需要密集的锚节点网络。为了降低 定位成本，可以使用虚拟节点代替部分锚节点，虚拟节点不发射信号，只代表该 点的坐标和信号测量值。
(2)墓于连接的算法
此类算法利用全网的连接信息做岀定位决策。其中最著名的一个算法是DV- hop。该算法以距离矢量路由为核心，每个锚节点广播包含其位置坐标的信标消 息。信标中的跳数初值为1,每经过一个节点加1。当多个锚节点的信标在网络 中传输时，传输路径上的每个节点都会记录各个锚节点的最小跳数。在各向同性 的传感网中，信号的单跳物理距离在各方向上大致相同。未知节点根据跳数估算 到各个锚节点的距离。但在复杂网络中，由于存在干扰等因素，导致各个方向单 跳距离差异较大，难以实现精确定位。
(3)事件驱动的算法
此类算法中，不属于无线传感网络的设备提供定位信号，传感网络不传输定
位数据。传感器节点不参与定位活动。比如灯塔算法㈤］根据节点停留在外部定位 设备生成的平行旋转光束中的持续时间对节点进行定位。聚光灯算法基本上遵循 与灯塔方法相同的机制，区别在于，它在聚光灯设备上完成定位算法所需的资源 密集型运算，而非在传感器节点上运行，从而降低了传感器功耗和成本。
1.3.13.指纹定位算法
指纹定位是免测距定位算法中获得较多关注的一种定位算法卩4】。在定位区 域布设一定数量的锚节点，锚节点位置固定，坐标已知，具有信号发射功能。传 感器节点测量各个锚节点无线信号强度RSS。测量的RSS值和该节点的位置坐 标称为该位置的信号指纹。指纹定位方式不依据RSS与距离公式推算节点位置， 而是融合RSS与锚节点近似算法推算传感器节点位置。指纹定位算法需要在定 位空间建立指纹数据库，即将空间各点的位置坐标与该位置处不同锚节点的RSS 信息建立联系。指纹定位过程就是根据指纹数据库的指纹和位置关系信息，将未 知节点接收到的RSS信息转化为位置信息。将RSS转化为目标位置的过程即为 指纹匹配及指纹定位。指纹定位也能描述为一个多重假设检验问题，根据预先获 得的观察结果（即指纹）推导出最佳假设（目标的位置）。指纹定位过程也可认 为是一个决策过程，根据己有信息（指纹数据库）和未知节点测量的RSS,决策 目标为未知节点位置。
指纹定位算法需要两个阶段：离线测量阶段和在线定位阶段。图1-3为指纹 定位的基本流程。在离线测量阶段，首先在当前定位环境中布设一定数量参考节 点，并记录所有参考点的位置坐标。通常参考节点按网格状布设，参考节点可以 为物理节点，也可以为虚拟节点。然后在所有参考节点处按某种方式测量、收集 各个锚节点的RSS值，称为原始观测数据，或称为样本。由于定位区域不可避 免存在信号干扰，RSS的测量值存在误差，需要采用一定的方法对样本进行预处 理。预处理后的RSS数据和参考节点的坐标建立对应关系，形成指纹数据库。
在线定位阶段，目标节点在自己位置测量各个锚节点的RSS值，并发到后 台定位服务。定位算法将此RSS值与指纹数据库所有样本按照设定的算法进行 匹配，找出一个或多个匹配度最高的参考节点。最后将这些参考点位置坐标按照 特点算法转换为目标节点所对应的位置，即目标节点的位置估计。
