无线传感器网络中基于同心圆树的路由选择算法

文孟飞，彭军，张晓勇，刘伟荣

（中南大学 信息科学与工程学院，湖南 长沙，410075）

高速公路的交通情况主要受车流的流向和天气气候以及高速公路路况和地形因素的影响，而高速公路的主要任务是减少上述因素对整个交通情况所造成的影响。国内外研究者提出了许多交通系统用于高速公路的监视与控制。这些系统可采集车流量、超速、交通意外和路面状况等各种信息，并依据这些现场信息做出安全预警、出行参考和事故救援等决策[1−2]。无线传感器网络（Wireless sensor network，WSN）作为一种全新的信息获取和处理技术，集成了传感器、计算机网络和无线通信等技术，能很好地实现系统与车的通信，但是，无线传感器节点能量有限，在公路环境下为其补充能量成为难题,因此，亟需高效合理地利用能量以最大化提高整个无线传感器网络的寿命[3−5]。针对无线传感器网络能量利用，研究人员提出相应能量感知路由协议，如：林益等[6]提出了一种最少跳数路由协议，利用蚁群算法来寻找从源节点到目标节点间跳数最少的路径。该方法可快速地构建路由并有效减少能量消耗，但是其数据传送路径过于集中，容易使关键节点能量迅速耗尽，从而减小整个网络的生存周期；能量感知路由协议（EAR）算法在源节点和目的节点间提供了多种路由选择。节点每次发送数据时根据某概率选择路径，该概率由路径节点能耗特征及其剩余能量决定。该协议能够均衡节点数据传输能量消耗，延长整个网络工作时间，但是，该协议中概率计算过程过于复杂，算法收敛速度慢。Lu等[7]提出了一种能量高效多路径路由协议（EEMRP），通过链路代价选择下一跳中继节点，链路代价由节点的剩余能量级别和节点到目的的节点跳数共同决定，但是，该协议通过离目的节点的跳数少而非实际距离来衡量节点间的距离关系，这会使得能量问题的考虑过于片面。总之，无线传感器网络的路由选择协议和分簇算法会影响网络通信能耗、数据量和通信延时，因此，亟需提出延长网络生存周期、提高节点能量利用效率的路由机制。针对此问题，为建立高速公路设施安全监控无线传感器网络模型（WSN-H），本文作者提出一种基于同心圆路由树的路由选择算法（C2TRA）。在该算法中，节点在保证网络健壮性的前提下以最小功率进行路由发现，并采用短距离的多跳数据传输，节省了节点能耗；在选择数据路由时，根据潜在下一跳节点能量状况来选择中级，均衡了网络能耗；引入对簇内节点分级的机制，形成以簇头节点为树根的簇内路由树，加强了数据往目的节点的导向，去除了不必要数据的转发，提高了数据转发效率，降低了整个网络的能耗和通信延迟。

1 网络模型

结合无线传感器网络组网特点和公路基础设施安全监控的实际情况，提出如图1所示的WSN-H系统模型。该系统模型具有如下几个特点：监控区域广泛且分散，目标信息变化较快，目标信息传输距离远且要求实时，监控区域地处偏远。网络模型建立在如下假设基础上：

（1）网络中所有的节点的最大发射功率相同，每个节点有唯一的身份标识符（ID），所采集的数据采用统一的数据格式。

（2）每个节点初始能量一致，发射功率均可快速调整，都可以在最小的发射功率情况下与其他节点建立连接，即不存在孤立节点。

（3）每个节点位置固定，重点部署于路口以及均匀部署于公路沿线；利用GPS或定位算法确定自己的位置及与公路的相对位置。

（4）汇聚节点部署在移动汽车上，有充分能量，数据处理与通信能力较强。

（5）存在时延约束量Δ，各节点间数据传输时延不得超过该约束量。

（6）每个簇的簇头已知。

2 基于同心圆树的路由选择算法（C2TRA）

2.1 算法描述

为了降低节点能耗，无线传感器网络一般采用节点功率控制和多跳路由等技术，但各方法的效率有明显差别。为此，提出一种基于同心圆树的路由选择算法，以提高能量利用效率，延长网络生存时间。

2.1.1 多跳路由

文献[8]给出了无线传感器网络的能耗模型。该模型可计算距离为d的2个节点发送l个比特数据所消耗的能量ETx（l，d）。

其中：l为非负整数，表示节点间发送数据的比特数；Eelec为发射电路能耗。当 d＜d0时，采用自由空间模型；εfs为该模型的功率放大能耗；当 d≥d0时，采用多路径衰减模型；εmp为该模型的功率放大能耗；nlos_d为非视距误差，由于高速公路环境下无线传感器网络分布较为集中，因此，可将此误差视为正的随机噪声。

图1 WSN-H系统模型图Fig.1 Model of WSN-H system

本文按照式（1）分析WSN-H能耗。如图2所示，设A，B和C 3个节点构成1个直角三角形。A向B发送数据时有2条可选路径：A−B和A−C−B。这2条路径在2种模型下各自的能耗分析如下。

节点间距离分别为dAB=5，dAC=4，dBC=3。为了分析简单，假设3个距离都不小于d0，此时为多路径衰减模型，则A−B的通信能耗为：

A−C−B的通信能耗为：

比较式（2）与（3）可知：尽管 A−B的通信距离比A−C−B的通信距离短，但A−C−B路径比A−B路径的通信能耗更低。

图2 3个传感席子点构成的直角三角形Fig.2 Right triangle constituted by three sensor node

若以上3个距离都小于d0，由式（1）计算分析可得出A−B路径比A−C−B路径的通信能耗低。

经上述分析得出结论：当节点间距离较小时，直接通信能耗更低；而当节点间距离较大时，通过其他节点多跳通信能耗更低。下面将动态地根据节点剩余能量、节点间距离、连通性及信道模型等因素来选取单跳或多跳的路由策略。

2.1.2 节点功率控制

Kleinrock等[9]经分析得出网络中节点的平均邻节点数为5.89时，连接较稳定可靠，故本文采用功率控制技术将节点的邻节点数保持在6个左右。节点数量的确认并不是频繁进行的，每隔一定时间更新1次。该方案尽管存在路由开销，但是，保证了路由稳定，总体上对总路由开销影响很小。节点根据其与接受节点或中继节点之间的距离动态地调整发送功率，在保证通信质量的基础上，尽可能节约能量。每个节点会根据邻节点的反馈，建立路由邻居信息表，其中：ID为邻节点的标识符；d为与邻节点间的距离；Er为邻节点的当前剩余能量；level为邻节点在当前簇的路由层级；P 为将数据发送给邻节点所需的最小发射功率；active为状态标识符，表示是否与邻节点建立稳定连接，1表示可以转发数据，0表示不能转发数据。节点根据路由邻居信息表及其当前的工作状态，动态地进行功率控制，如图3所示，其中：图3（a）所示表示未进行功率控制，此时节点发射功率最大，覆盖范围最大，但能耗最大；图3（b）所示表示节点调整功率，保证刚好覆盖到其最远邻节点，若邻节点过多，能耗也较大，该情况一般用于广播；图 3（c）所示表示节点继续调低发射功率，使其邻节点数量保持在6个左右，保证节点的连通稳定性，此时节点处于发送数据前的路由发现阶段；图3（d）所示表示节点确定其下一跳邻节点后，将发射功率调整到能保证它们之间通信稳定的最小值。

图3 普通节点功率控制策略图Fig.3 Power control strategy of normal node

2.1.3 路由层级划分与路由规则

WSN-H系统由多个局部无线传感器网构成，其局部网络覆盖规模较小，节点数量有限，所以，可规定簇内数据传输的跳数不多于3跳。本文根据图论中树的形成机理，提出将簇内进行分层的思想，以保证发射功率尽可能小且跳数不大于3。

假设dmin为簇头节点邻居信息表中最近节点间距离，dmax为其中最远距离，簇头根据这2个距离d将所有节点划分为如下3层：

为提高数据转发效率，提出如下路由规则：

（1）同级节点间无数据转发；

（2）节点只为自己外层节点进行数据转发；

（3）节点可向内跨层转发数据。

该规则可使数据尽快发送给簇头，避免多余的转发，降低能耗和通信时延，保证簇内数据传输的跳数不多于3跳，从而也保证了时延约束量Δ的限制。

2.2 算法实现

2.2.1 路由发起

在路由开始阶段，节点查询其路由邻居信息表中存储的发送给邻节点所需的最小发射功率Pt，选取合适的Pt，调整发射功率，使其通信范围能覆盖6个左右邻节点。然后，节点广播路由请求信息（Routing link request,RLR），如图4（a）所示。RLR中包含了该节点的标识信息、簇信息和层级信息。邻节点收到RLR信息后根据RR判断是否应答，若应答，则反馈路由连接应答信息（Routing link answer,RLA），RLA中包含了应答节点的标识信息、层级与剩余能量信息。节点根据收到的 RLA 更新路由邻居信息表中的 Er，level和active信息，然后，根据如图4所示的中继选择原则选择下一跳邻节点。

图4 路由发起示意图Fig.4 Route initiation schematic

如图 4（b）所示，节点接收到多个邻节点的反馈RLA信息，即都满足RR规则，均可作为下一跳节点。但需要按照中继选择原则选择唯一的下一跳邻节点。本文的中继选择原则为：假设节点O接收到n条RLA信息，其相应邻节点的剩余能量分别为Er1，Er2，…，Ern，可计算出n个邻节点的平均剩余能量：

从所有满足式（6）的节点中选择距离最近的节点作为下一跳。从路由邻居信息表中查询向该下一跳邻节点发送数据所需的最小发射功率。

该路由选择方案既减轻了剩余能量少的节点的负载，又能保证每个节点都以最合适发射功率发送数据，从而提高能量利用率。

2.2.2 路由回复

节点收到源节点的路由请求信息 RLR后，根据RLR中包含的信息和该节点本身的状态，按照RR来决定是否应答源节点的请求。节点只应答本簇内外层节点发来的RLR信息；此外，节点决定是否应答时应充分考虑自身剩余能量，避免能量低的节点过早死亡。

假设节点A经节点B转发将l比特数据给节点C，A与B的距离为d1，B与C的距离为d2，由于相互层级之间距离一般较小，可认为是式（1）中的自由空间模型，则节点B将数据转发给节点C所需的能量为：

考虑到节点接收数据也要消耗一定的能量，文献[9]提出了接受数据的能耗模型，节点接收l比特数据所需能耗ERx（l）为：

故节点B在转发l比特数据的过程中的总消耗为：

且仅当节点B的剩余能量Er＞E时，才应答节点A发来的RLA信息，以表示其能提供路由。经过节点间不断的路由请求和应答，整个网络最终会形成如图5所示的同心圆路由树。

图5 簇内节点通信同心圆路由树Fig.5 Concentric routing tree of communication between cluster members

3 仿真与性能分析

利用OPNET工具对EEMRP，EAR和C2TRA进行仿真。这3种多跳的算法网络生存时间如图6所示，分别为684，715和747 s，而簇内节点与簇头直接一跳通信的EECA网络生存时间为648 s，由此可知短距离多跳通信的能量利用效率比远距离多跳通信的高。网络生存时间是衡量算法综合性能的 1个指标，C2TRA这方面表现最优，主要是因为其采取了多跳路由、功率控制及低能量节点保护等机制，均衡网络能耗，提高了网络能量利用率。

图6 网络剩余节点个数与网络生存时间关系Fig.6 Relationship between numbers of nodes and network sunvival time

3种算法网络失效前能耗与发送数据包之间的关系如图 7所示。当发送相同数量的数据分组时，C2TRA，EEMRP和EAR消耗的能量依次增大，发送单位数据包平均能耗依次减小。C2TRA算法能够控制数据发送时的转发次数，增强对数据发送方向的导向，避免不必要数据的转发，从而减少额外能耗；同时，网络失效时C2TRA可使节点平均剩余能量最小。由此可知：C2TRA算法能量利用率较高，而EAR能量利用率最低。这主要是其路由中继选取时需要考虑过多网络状态信息，且进行迭代计算，复杂度较高，从而消耗过多额外能量。

图8所示为网络失效前数据发送量与路由开销的关系。由于 EAR根据路径节点能耗特征及其剩余能量，按照一定概率选取源节点到目的节点多条路由，故发送数据中路由开销很大，且多数路由开销都是无效的。EEMRP通过链路代价选择下一跳，链路代价由节点的剩余能量级别和节点到目的的节点跳数共同决定，这导致节点每次发送数据都要不断地试探周围，增加了不必要的开销。本文提出的C2TRA在保证链路稳定的条件下，限制了节点邻节点数量，使得数据传输时，路由链路相对稳定，从而一定程度上比EEMRP进一步降低了路由开销。

图7 网络失效前数据发送量与网络能耗的关系Fig.7 Relationship between amount of data sent and energy consumption of network

图8 网络失效前数据发送量与路由开销能耗的关系Fig.8 Relationship between amount of data sent and energy consumption of routing overhead

图9所示为网络发送数据包与簇头成功接收数据包之间的关系。图中曲线反映的是数据成功投递率。由图9可见：在失效节点出现前，这3种算法数据传送成功率都较固定，其中 EAR成功率较低，C2TRA成功率较高。这主要是因为C2TRA限制了路由中多跳传输的跳数。本文仿真场景中，节点覆盖密度较大，节点间距离较小，若路由中继选择时不限制路由跳数，仅考虑剩余能量，则数据路由次数会明显增加，数据丢失率会加大，从而降低数据传输成功率。因此，在簇的覆盖范围不是很大如高速公路路口的面积一般不大时，WSN-H中的簇就不用覆盖太远，限制数据转发跳数，能大幅地减少数据丢失，同时降低网络的通信延迟。

以上仿真结果表明：C2TRA算法能够有效延长网络生存时间，提高网络能量利用率。

图9 网络发送的数据包与成功到达簇头的数据包关系Fig.9 Relationship between number of package sent and nember of package received by cluster head

4 结论

（1）将 WSN技术引进了高速公路安全监控领域，根据该领域的背景需求和WSN的组网特征，搭建了高速公路安全监控无线传感器网络WSN-H网络系统结构。

（2）针对无线传感器网络的网络生存时间与能量问题，提出了一种基于同心圆路由树的路由选择协议C2TRA，以降低节点能量消耗，均衡整个网络能耗，从而提高了WSN-H中了点能量的利用效率，并延长了该网络的生存寿命。仿真结果表明所提出的算法是有效的。

[1]Li L J,Li X,Cheng C J.Research collaboration and ITS topic evolution:10 years at T-ITS[J].IEEE Transactions on Intelligent Transportation Systems,2010,11（3）:517−523.

[2]Yan E,Ding Y.Topics in Dyanmic research communities:A exploratory study for the field of information retrieval[J].Journal of Informatrics,2012,6（1）:140−153.

[3]Tao M,Lu D.An adaptive energy-aware multi-path routing protocol with load balance for wireless sensor networks[J].Wireless Personal Communication,2010,6（2）:1−24.

[4]尚凤军,任东海.无线传感器网络中分布式多跳路由算法研究[J].传感技术学报,2012,25（4）:529−535.SHANG Feng-jun,REN Dong-hai.A distributed multi-hop routing algorthm in wirdess sensor networks[J].Chinese Journal of Sensors and Actuators,2012,25（4）:529−535.

[5]Zhao G,Liu X.Energy-efficient geographic routing with virtual anchors based on projection distance[J].Computer Communications,2008,31（10）:2195−2204.

[6]林益,杨靖.无线传感器网络中路由选择算法的研究[J].计算机测量与控制,2009,17（1）:252−254.LIN Yi,YANG Jin.Research on routing selection algorithm for wireless sensor networks[J].Computer Measurement and Control,2009,17（1）:252−254.

[7]Lu Y,Wong V.An energy efficiency multipath routing protocol for wireless sensor networks[J].International Journal of Communication Systems,2007,20（7）:1−5.

[8]曾志文,陈志刚,刘安丰.无线传感器网络中基于可调发射功率的能量空洞避免[J].计算机学报,2010,33（1）:13−14.ZHENG Zi-wen,CHEN Zhi-gang,LIU An-feng.Energy-hole avoidance for WSN based on adjust transmission power[J].Chinese Journal of Computer,2010,33（1）:13−14.

[9]Kleinrock L,Silvester J A.Optimum transmission radii in packet radio networks or why six is a magic number[C]//Proceedings of the IEEE National Telecommunications Conference.Birmingham,1978:431−443.