无线传感器网络路由协议.doc

无线传感器网络的关键技术有路由协议、MAC协议、拓扑控制、定位技术等。
路由协议：
数据包的传送需要通过多跳通信方式到达目的端，因此路由选择算法是网络层设计的一个重要任务。路由协议重要负责将数据分组从源节点通过网络转发到目的节点，它重要涉及两个方面的功能：
1.寻找源节点和目的节点间的优化途径。
2.将数据分组沿着优化途径对的转发。
无线传感器与传统的无线网络协议不同之处，它受到能量消耗的制约，并且只能获取到局部拓扑结构的信息，由于这两个因素，无线传感器的路由协议要可以在局部网络信息的基础上选择合适途径。传感器由于它很强的应用相关性，不同应用中的路由协议差别很大，没有通用的路由协议。无线路由器的路由协议应具有以下特点：
（1） 能量优先。需要考虑到节点的能量消耗以及网络能量均衡使用的问题。
（2） 基于局部拓扑信息。WSN为了节省通信能量，通常采用多跳的通信模式，因此节点如何在只能获取到局部拓扑信息和资源有限的情况下实现简朴高效的路由机制，这是WSN的一个基本问题。
（3） 以数据为中心。传统路由协议通常以地址作为节点的标记和路由的依据，而WSN由于节点的随机分布，所关注的是监测区域的感知数据，而不是具体哪个节点获取的信息，要形成以数据为中心的消息转发途径。
（4） 应用相关。设计者需要针对每一个具体应用的需求，设计与之适应的特定路由机制。

现介绍几种常见的路由协议（平面路由协议、网络分层路由协议、地理定位辅助路由协议）：

一、平面路由协议
平面路由协议中，逻辑结构时平面结构，节点间地位平等，通过局部操作和反馈信息来生成路由。当汇聚点向某些区域发送查询并等待来自于这些区域内传感器所采集的相关数据，其中的数据不能采用全局统一的ID，而是要采用基于属性的命名机制进行描述。平面路由的优点是结构简朴、鲁棒性（即路由机制的容错能力）较好，缺陷是缺少对通信资源的优化管理，对网络动态变化的反映速度较慢。其中典型的平面路由协议有以下几种：

1.1.洪泛式路由（Flooding）：
这是一种传统的网络通信路由协议。这种算法不规定维护网络的拓扑结构和相关路由的计算，仅规定接受到信息的节点以广播形式转发数据包。例如：S节点要传送一段数据给D节点，它需要通过网络将副本传送给它每一个邻居节点，一直到传送到节点D为止或者为该数据所设定的生存期限为零为止。优点在于：实现简朴；不需要为保持网络拓扑信息和实现复杂路由发现算法消耗计算资源；合用于鲁棒性较高的场合。但同时也有相应的缺陷：一个节点也许得到一个数据的多个副本；存在部分重叠，假如相邻节点同时对某件事作出反映，则两个节点的邻居节点将收到两份数据副本；盲目使用资源，无法作出自适应的路由选择。
为克服Flooding算法这些固有的缺陷，S.Hedetniemi等人提出闲聊式（Gossiping）策略这种算法采用随机性原则，即节点发送数据时不再采用广播形式，而是随机选取一个相邻节点转发它接受到的数据副本（避免了消息爆炸的结果）。

图1 洪泛式路由机制 图2 gossiping路由机制

1.2.SPIN路由：
SPIN是一组基于协商并且具有能量自适应功能的信息传播协议。它有如下两个特点：（1）每个节点在发送数据前需要通过协商来拟定其他节点是否需要该数据，同时每个节点通过元数据（meta-data）来拟定接受数据中是否有反复信息的存在。（2）网络中节点必须实时监控本地能源消耗，根据能量等级改变工作模式来延长节点自身和整个网络的运营时间。
SPIN在运营过程中节点使用3种类型的信息进行通信，即ADV、REQ和DATA信息。ADV——用于新数据广播。当一个节点有数据可共享时，它以广播方式向外发送DATA数据包中的元数据。REQ——用于请求发送数据。当一个节点希望接受DATA数据包时，发送REQ数据包。DATA——包含附上元数据头（meta-header）的实际数据包。SPIN协商过程采用3次握手方式。Step1：运营SPIN协议的源节点在传送DATA信息前，一方面向相邻节点广播包含DATA数据描述机制的ADV信息。Step2：需要该DATA信息的邻居节点，向信息源发送REQ请求信息。Step3：源节点根据接受到得REQ信息，有选择地将DATA信息发送给相应的邻居节点，如下图3所示。收到DATA数据的节点可作为信息源敬爱那个DATA信息传播到网络中的其他节点。

图3 SPIN路由机制
该协议除了提供数据传输过程中得协商机制，还引用了基于阖值的能量值适应机制。它规定每个节点都提供对其自身的能量管理功能以便跟踪能源的能耗状况。当节点的剩余能量开始接近低能量阖值，节点便减少在协议中得参与行为。
这种协商机制和能量自适应机制的SPIN协议可以很好地解决传统的Flooding和Gossiping协议所带来的信息爆炸、信息反复和资源浪费等问题。SPIN协议的缺陷是数据广告机制（ADV）不能保证数据的可靠传递，因此对于入侵发现等需要在定期间隔内可靠传递数据的应用系统来说，SPIN并不是一个很好的选择。

1.3.DD路由：
定向扩散模型DD（Directed Diffusion）是一种以数据为中心的信息传播协议,运营DD的传感器节点使用基于属性的命名机制来描述该数据（如图4所示）。
其中，定向扩散算法在运营过程中涉及以下3个基本过程，即途径建立阶段、数据发送阶段和增强途径阶段。
途径建立阶段：汇聚点以广播、多跳的方式向网络中所有节点发布命令信息，命令信息用品有任务类型、数据发送速率、时间戳等参数的爱好描述。每个节点通过记录获取到爱好的相应邻居节点、数据速率和时间戳等来建立梯度。
数据发送阶段：当节点采集到匹配查询的数据时，通过梯度途径发向汇聚点。中间节点运用本地化规则实现数据的融合。
增强途径阶段：汇聚点在收到这些低速率数据后，向数据到达最快的邻居节点发送增强消息，增强消息表达汇聚节点规定高速率发送数据。相应邻居节点按照同样地方式，依次传递增强信息给其邻居节点，直到到达数据源，从而构建数据发送的主途径，数据以后就通过途径发送给汇聚点。
在DD协议的网络中，节点可以运用选取的最优途径的缓存来实现节能的目的。缓存技术可以提高传感器节点间的有效性、鲁棒性和协作的可扩展性，这也就是DD模式的本质。DD算法在WSN路由协议研究中的一个里程碑，其中最大的特点就是引入了网络梯度概念。DD算法的优点是：仿真结果分析说明，网络梯度与本地化算法相结合应用于无线传感器网络的路由，可以很好地满足WSN对节能、鲁棒性以及可扩展性的需求。缺陷是：它不合用于环境监控这类规定连续传递数据的系统；选择与查询相匹配的数据会使传感器节点消耗更多的能量。

图4 DD路由机制
1.4.HREEMR路由：
HREEMR是定向扩散路由机制的基础上提出的，目的是通过维护多条可用途径来提高路由的可靠性。该协议在运营期间采用与DD相同的本地化算法建立源节点和汇聚点间最优途径p，同时为了保障p发生失效时协议仍能正常运营构建多条与p不想交的冗余途径（为了避免主途径失效的现象发生而采用的应急措施）。HREEMR协议提出了不相交多途径和缠绕多途径两种不同的多途径机制。
（1）不相交途径：在汇聚点发送增强消息建立主途径p后，汇聚点发送次优途径增强消息给次节点A，节点A选择最优节点B把次优途径增强消息传递下去。假如B在主途径p上，则B发回否认增强消息给A，A在向此外的次优节点传递次优途径增强信息；相反假如B不在主途径上则继续传递次优途径增强信息。如此往复，就可以构造下一条次优途径（如图5所示）。

图5 HREEMR不相交途径
（2）缠绕多途径：缠绕多途径采用一定策略允许冗余途径通最优途径p部分相交，从而较不相交途径减少了维持的冗余途径数量，节省了能源的消耗。缠绕多途径在建立主途径p后，p上除了源端和靠近源端的节点以外，每一个节点都要发送备用途径增强消息给次优节点A，次有节点寻找最优节点B传播该备用途径增强消息，假如B不在主途径p上，继续向最优节点传播直到与主途径p相交。
总而言之，HREEMR的多途径策略实现了能源有效的故障恢复，解决了DD为了提高协议的鲁棒性，采用周期低速率扩散数据而带来的能源浪费问题。

1.5.SAR路由：
SAR协议是第一个具有QoS（服务质量，是一种网络安全机制，用于解决网络延迟及阻塞问题的一项技术）意识的路由协议。它的特点是路由决策不仅要考虑到每条途径的能源，还要涉及端到端的延迟需求和待发数据包的优先级。
每个树以落在汇聚点有效传输半径内的节点为根向外生长，枝干的选择需满足一定的QoS规定并要有一定的能量储备。节点可以根据每条途径的能源、附加的QoS度量和包的优先级选择某棵树将信息返回给汇聚点。仿真结果显示，与只考虑途径能量消耗的最小能量度量协议相比，SAR能量消耗更少，但缺陷是不适合于大型和拓扑频繁变化的网络。

二、网络分层路由协议
分层路由协议中，网络通常被划分为簇，每个簇由一个簇首和多个簇成员组成，多个簇首形成高一级的网络，在高一级网络中，又可以分簇，再次形成更高级的网络，直至最高级（如图6所示）。
在分层结构中，簇首节点不仅负责所管辖簇内信息的收集和融合解决，还负责簇间数据的转发。分层路由协议中每个簇的形成通常是基于传感器节点的保存能量和与簇首的接近限度，同时为了延长整个网络的生命周期，簇首节点的选择需要周期更新。分层路由的优点是适合大规模的无线传感器网络环境，可扩展性较好。缺陷是簇首节点的可靠性和稳定性对全网性能影响较大，信息的采集和解决也会大量地消耗簇首的能量。
一些典型的分层路由协议有LEACH、PEGASIS、TEEN、APTEEN和具有能量意识的传感器网络分簇路由。

图6 网络分层的路由机制
2.1.LEACH路由：
LEACH的基本思想是以循环的方式随机选择簇首节点，将整个网络的能量负载平均分派到每个传感器节点中，从而达成减少网络能源消耗、提高网络整体生存时间的目的。仿真表白，与一般平面多跳路由和静态分层算法相比，LEACH可以将网络的生命周期延长15%。
LEACH在运营过程中不断地循环执行簇的重构过程。每个簇重构过程可以用“会合（round）”的概念来描述。每个回合可以提成两个阶段：簇的建立阶段和传输数据的稳定阶段。其中，簇的建立过程又可分为四个阶段：簇首节点的选择、簇首节点的广播、簇的建立和调度机制的生成。
簇首节点的选择：依据网络中所需要的簇首节点总数和迄今为止每个节点已成为簇首的次数决定，具体方法如下：每个传感器节点随机选择0~1之间的一个值，假如选定的值小于某一个阖值T(n)，那么这个节点成为簇首节点。其中，T(n)值计算如下：

N为网络中传感器节点总数；k为一个回合网络中簇首节点数；r为已完毕回合数。
簇首节点的广播：选定簇首节点后，通过广播告知整个网络。
簇的建立：网络中其他节点根据接受信息的信号强度决定从属的簇，并告知相应的簇首节点，完毕簇的建立。
调度机制的形成：最后，簇首节采用TDMA（时分多址）方法为簇中每个节点分派向其传送数据的时间片。在稳定阶段中，传感器节点将采集的数据传送到簇首节点。簇首节点对簇中所有节点所采集的数据进行信息融合后再传送给汇聚点，这是一种减小通信业务量的合理工作模式。
稳定阶段连续一段时间后，网络重新进入簇的建立阶段，进行下一回合的簇重构，不断循环。
但该协议还存在以下三个值得探讨的问题：并不是每个节点都可以直接与汇聚点直接通信，因此该协议不适合在大规模无线传感器网络中应用。协议没有说明簇首节点的数目如何分布才干遍及整个网络。有也许某个簇首节点集中于网络某一个区域，而其他区域节点周边没有任何簇首。该协议未能考虑到节点能量不均衡的网络。

2.2.PEGASIS和分层PEGASIS
PEGASIS的基本思想是为了延长网络的生命周期，节点只需要和它们最近的邻居之间进行通信。节点与汇聚点之间的通信过程是轮流进行的，只有当所有节点都与汇聚点通信后，节点才进行新一回合的轮流通信。由于这种轮流通信机制使得能量消耗统一分布到每个节点上，因此减少了整个传输所需消耗的能量。
PEGASIS协议在传感器节点中采用链式结构进行连接。运营PEGASIS协议时每个节点一方面运用信号的强度来衡量其所有邻居节点距离的远近，在拟定最近邻居的同时调整发送信号强弱保证只有邻居节点听的到。另一方面，链中只选择一个节点作为链首向汇聚点传输数据。采集到的数据以点到点的方式传送、融合，并最终被送到汇聚点。
该协议的优点在于：减少了LEACH在簇重构过程中所产生的开销，并且通过数据融合减少了收发过程的次数，从而减少了能量的消耗。

图7 PEGASIS的链式结构
分层PEGASIS协议是对PEGASIS的扩展，该协议的目的是减少数据包到汇聚点传送过程中所引起的延迟。为此，协议采用了数据并行传输的机制，并提出了两种方法来避免传感器间的冲突和也许存在的信号干扰。第一种方法结合了信号编码方式，如码分多址CDMA；第二种方法只允许空间上分隔的节点可以同时传输数据。
基于CDMA的分层PEGSIS协议采用树状分层结构的方式，每一层选择的节点向更高一级的节点传送数据。协议规定在每个回合的数据采集过程中，给定层的节点都向附加的邻居发送数据，所有接受数据的节点被提高为上一层的节点。依次类推，最后顶层只有一个节点被保存下来并成为链首节点。举例说明该协议每个回合途径选择的过程，如下图所示：
图8 基于CDMA的分层PEGASIS协议的数据采集
节点C3在第三个回合被指定为链首，假设节点C0在链中得位置为0，节点C3的位置为3，为奇数，那么所有处在偶数位置的节点都向右边的邻居发送数据，接受到数据的节点C1、C3、C5、C7成为第二层节点。在第二层节点中由于C3仍处在奇数位置1，因此所有偶数位置的节点再次融合他们接受到得数据和自身采集到的数据，并将融合后的数据发送给他们右边的邻居；在第三层中节点C3不是奇数位置，为了保证C3作为链首，节点C7融合接受到得数据和自身数据并将其传给C3，节点C3将当前数据和从C7中接受到得数据融合起来并最终传递给汇聚点。这种分层方式保证了数据的并行传输并有效地减少了传输时延。

2.3.TEEN和APTEEN
按照应用模式的不同，无线传感器网络可以分为积极式和反映式两种类型。积极式无线传感器网络连续监测周边的物质现象，并以恒定速率发送监测数据；而反映式无线传感器网络只是在被观测变量发生冲突时才传送数据。
TEEN协议就是为反映式无线传感器网络而设计的路由策略，它具有实时性，可以突发事件作出快速反映。TEEN与LEACH采用相同的多簇结构和运营方式，不同的是在簇的建立过程中，随着簇首节点的选定，簇首除了通过TDMA方式实现数据的调度，还向簇内成员广播有关数据的硬阖值和软阖值两个参数。硬阖值是被监测数据所不能逾越的阖值，软阖值则规定被监测数据的变动范围。在簇的稳定阶段，节点通过传感器不断地感知其周边环境。当节点初次监测到数据到达硬阖值，便打开收发器进行数据传送，同时将该检测值存入节点内部变量SV中。节点如需再次传送需要两个条件：1当前检测值大于硬阖值；2当前检测值与SV的差异大于等于软阖值。只要节点发送数据，变量SV变置为当前的检测值。在簇重构的过程中，假如新一回合的簇首已经拟定，该簇首将重新设定和发布以上两个参数。如下图所示：

图9 （a）TEEN协议操作 （b）APTEEN协议操作
APTEEN协议是TEEN协议的扩展，是一种混合协议，可以根据用户需要和应用类型来改变TEEN协议的周期性和相关阖值的设定，既能周期性地采集数据又可以对突发事件作出快速反映。其特点如下：
（1）随着簇首节点的拟定，簇首向簇内所有成员广播以下参数：属性，阖值，调度，计数时间。
（2）在发送数据时会采用与TEEN相同的数据发送机制，但是为了克服TEEN不能周期性数据传送的缺陷，协议规定假如节点在计数时间CT内没有发送任何数据，便逼迫节点监测和向汇聚点传送数据。
（3）为了更好地实现协议在混合网络系统中得应用，APTEEN采用了修改后的TDMA调度方法。
（4）支持3种不同的查询类型，涉及分析过去数据的历史性查询、快速浏览网页的一次性查询和一段时间内连续监控某一时间的连续查询。
仿真结果表白，在能量分布和网络生存时间的指标上，TEEN和APTEEN的性能要优于LEACH协议，而APTEEN的性能位于TEEN和LEACH之间。

2.4.具有能量意识的传感器网络分簇路由
网络运营前由汇聚点将传感器节点划提成簇，传感器节点可以以活动方式和备用的低能耗两种方式运营。节点内部的感知电路、数据解决电路和无线收发器可以独立的启动和关闭，簇内节点可以采用以下4种工作方式之一：感知、转发、感知并转发、休眠。与上述路由协议不同的是簇首不受能量的限制，它可以监控簇内节点的能量变化，决定并维护传感器的四种状态，采用TDMA机制为采集到得感知数据设立多跳路由。协议依据两节点间的能量消耗、延迟最优化等性能指标计算途径代价函数。簇首节点运用代价函数作为链路成本，选择成本最小的途径作为节点与其通信的最优途径。

三、地理定位辅助路由协议
无线传感器网络的许多路由协议都需要传感器节点的定位信息。由于WSN没有类似IP地址的访问机制，并且分布在某个特定区域，它们可以运用地址信息使数据以某种节能的方式进行传输。因此假如已知被感应的区域，运用传感器的位置，查询信息就会只发布到被感知的区域，减少了数据传输的次数。

3.1.MECN和SNECN
MECN协议和SMECN协议都运用低功耗的GPS定位系统，通过计算和构建能源有效地子网实现节能目的。
MECN协议为每个节点设立了转发区域（relay region）。转发区域可以表达为一组节点集，发送节点通过转发区域内的节点发送数据，这种方式需要的能量较少。MECN的重要设计思想是构建子网，规定子网内部所含节点的数目较少并且任意两个节点间传输的数据都消耗更少的能量。这样不必考虑网络中所有的节点，就可以发现全局最小能量的途径。这对于每个考虑到自身转发区域的节点来说，运用本地搜索就可以实现到达目的节点的最小能量途径。
MECN的运营分为两阶段完毕。第一阶段：获取二维平面的位置信息，并构建包含所有发送节点外围的外围图。外围图的构建由节点内部的本地计算来完毕。第二阶段：在外围图中搜索出最优链路，搜索过程采用以能量消耗作为代价度量的分布式Belman-Ford最短途径算法来实现。
MECN协议最大的特点是具有自动重配置的特点，因此可以动态地适应节点的实效和网络的分布。但这种协议是在假定网络中每两个节点可以直接通信的前提下提出的，在实际环境中并不容易做到。
SMECN协议是MECN协议的扩展。它在原先MECN的基础上又考虑到了任意两种节点间不能直接通信的情况。SMECN协议的重要思想也是通过计算和构建子网，使得对于原网络中得仍以节点对（u，v）来说，都存在子网内最低能量消耗途径。最大的优点在于构造了满足最小能量转发的子网要小于MECN所构造的子网，但同时付出的代价也比SMECN高。

3.2.GEAR
GEAR协议运用地理信息将查询分布到合适的区域。GEAR运用能量和地理信息作为启发式选择途径向目的区域传送数据。它是下DD的基础上提出的，但由于GEAR只向特定的区域发送，因此GEAR相对于DD更加节省能量。
GEAR协议规定每个节点维护一个预估费用（estimated cost）和一个通过邻居节点到达目的节点的学习费用（learning cost）。预估费用是节点剩余能量与到目的节点距离的综合的结果。学习费用则是对描述网络中围绕在洞周边路由所需预估费用的改善。所谓洞（hole）现象是指某个节点的周边没有任何邻居节点比它自身更接近目的区域。假如没有洞现象的发生，那么预估费用等于学习费用。每当一个数据包成功到达目的地，该节点的学习费用就要被传播到上一跳。
协议包含了两个阶段：
（1向目的区域传递数据包：当节点收到数据包时一方面检查是否有邻居节点比它更接近目的区域。假如有，就选择离目的区域最近的节点作为数据传递的下一跳节点。假如相对于该节点而言，所有邻居节点都比它更远离目的区域，就意味着该节点存在洞现象。在这种情况下，运用学习费用函数选择其中的一个邻居节点来传递数据。
（2）传递已在目的区域内的数据包。假如数据包已经到达目的区域，可以运用递归的地理传递方式和受限的Flooding方式发布该数据。当传感器节点分布不太紧密时，受限的Flooding方式是较好的选择。而在高密度的无线传感器网络内，递归的地理传递方式相对受限的Flooding方式更加节能。递归的地理传递模式如下图所示，将目的区域分为四个部分，数据包也相应地被复制了4次，这种分割和数据传递过程不断反复，直到区域内只剩下一个节点为止。

图10 递归的地理传递方式
GEAR协议不仅减少了路由建立过程中得能量消耗，并且在数据传递过程中表现出优于GPSR（减少了节点所需维护状态的数量，但它规定维护与节点统一标志ID和节点位置相匹配的位置服务）的性能。