基于最短路径树的优化生存时间路由算法*

陈友荣，王章权，程菊花，刘耀林

(浙江树人大学信息科技学院，杭州 310015)

在大部分情况下无线传感网的所有节点采用电池供电，被部署在无人看守的恶劣环境中。而且节点分布密集、数量庞大，对电池的更换是非常困难的，因此节点存在严重的能量约束［1－2］。电池不能补充和更换，一旦节点能量耗尽，该节点就会失效，这将影响到网络的运行，甚至导致网络出现分裂而缩短网络生存时间。因此，无线传感网的各个算法都要从节能出发，最大限度地延长整个网络的生存时间［3－4］，节省重新部署无线传感网的巨大开销。

延长网络生存时间的方法很多，主要从两点考虑:减少和平衡节点能耗。减少节点能耗使得节点可用能量持续的时间更长，从而延长网络生存时间；平衡节点能耗，避免网络枢纽节点因自身能量消耗过快而缩短网络生存时间。文献［5］提出PEDAP(power efficient data gathering and aggregation protocol)和PEDAP_PA(power efficient data gathering and aggregation protocol_power aware)，都是基于最小权重树的路由算法。在算法中，定义了基于链路能耗的权值函数，通过Prim算法构建最小权重树，最终所有节点沿着最小权重树将数据发送给Sink节点。但是PEDAP和PEDAP_PA算法在网络生存时间延长方面不是特别理想。文献［6］提出LET(Least En-ergy Tree)算法。它是根据dijkstra算法构建每个节点到Sink节点能耗最小的最短路径树，最终所有节点沿着最短路径树将数据发送给Sink节点。LET算法比PEDAP和PEDAP_PA算法好，这是因为:LET算法利用dijkstra算法，构建以Sink节点为树根的最短路径树。由于dijkstra算法可以得到能耗最小路径，因而每个节点都沿着能耗最小路径传输数据，整个网络的能耗也相对较小［4］。但是LET算法的权值函数中存在着一个缺点:它忽视了节点的剩余能量。往往离Sink节点近的节点中存在一些枢纽节点，只是简单考虑链路通信能耗的权值函数，容易导致这些节点转发太多的数据，过早消耗能量而死亡。于是在LET算法的基础上提出了“比例权值路由算法”(ratio weight routing algorithm，Ratio_w)与“和权值路由算法”(sum weight routing algorithm，Sum_w)［7］，但是这两种算法没有考虑邻居节点的剩余能量，网络生存时间也不是最优的。因此综合考虑上述算法的优缺点，提出了基于最短路径树的优化生存时间路由算法(lifetime optimized routing algorithm based on shortest path tree，LORA_SPT)，延长网络的生存时间。

1 系统假设和链路能耗模型

在提出的路由算法中，假设［8］:①所有传感节点和Sink节点的位置是固定不变或是缓慢变化的，不影响节点间的相互位置和拓扑结构，且Sink节点有整个网络拓扑结构信息；②所有传感节点具有相同的性能(如初始能量、能耗参数、节点最大发送功率、最大通信半径等)；③所有传感节点发送功率可根据通信距离变化；④每个传感节点能量受限，但Sink能量不受限制；⑤网络中所有传感节点都需要感知和发送数据，即同时承担数据采集和中继任务，并通过直接或多跳的方式将数据发送给Sink节点。

典型的无线传感网节点能耗主要由无线数据收发产生［9］。节点发送模块的能耗ETx由发送电路电子能耗和信号放大器部分的电子能耗组成。接收模块的能耗ERx只考虑接收信号时的电路电子能耗。其中，电路电子能耗固定为gEelec，g代表所发送或接收的数据量，Eelec代表收发单位比特数据时电路电子能耗。信号放大器部分的电子能耗与节点发送功率有关。假设节点根据通信距离随时调整发送功率，于是可定义为与通信距离有关。具体的计算公式如下:

其中dij是发送的距离，dmax是最大通信距离，εfs是放大单位比特信号时所需要的电子能耗。根据式(1)和(2)可知:传感节点i与节点j之间传输g比特数据的能耗取为:

传感节点i与Sink节点之间传输g比特数据的能耗取为:

2 算法的原理

LET、Ratio_w和Sum_w算法的链路权值函数只考虑自身能量的大小，而邻居节点的剩余能量在链路选择时同样有利于避免剩余能量小的节点过早失效，因此考虑邻居节点的剩余能量是有必要的。同时为了避免网络枢纽节点能耗过快损耗，根据剩余能量将节点划分成标准节点和警告节点两种不同类型的节点［10］。权值函数中，不同类型的节点剩余能量权重因子是不一样的。具体说明如下:①标准节点:如果节点剩余能量值大于Ewarning，则是标准节点。网络中偏向于选择这些节点参与数据的转发。标准节点周围的链路权值不考虑类型权重因子，即是1。②警告节点:如果节点剩余能量值小于Ewarning，则是警告节点。在传输数据的时候尽量避开该类型的节点。此时警告节点周围的链路权值需要考虑类型权重因子，提高链路权值。

假设节点的初始能量为Einital，Ewarning的设定如下:

其中特定正常数δ的作用是确定Ewarning的值。f(x)是一个关于x的函数，x是网络参数，其设定如下:

其中|V|指网络中总节点数，x初始值是1，其具体计算方法如下:统计传感节点剩余能量值低于当前Ewarning值的节点数和警告节点在整个网络中所占的比例Yc。设定一个阈值Ys(0＜Ys＜1)，如果Yc＞Ys时，则表示x=x+1，更新Ewarning值。从式(6)可以看出，f(x)函数为递增函数，f(x)值随x的增大而增大，且f(x)的增加幅度也随x的增大而增大，当x趋近于|V|时，f(x)无穷大。因此，可以推断出当x增大时，Ewarning随之减小，而且当Ewarning减少到一定值时，某些警告节点又重新变成标准节点，继续参与数据的路由。当x趋近于|V|时，Ewarning趋近于零，把低于Ewarning的节点认为是能量耗尽的失效节点。Ewarning的递减规律符合传感节点能量的实际情况，开始节点能量比较充足，Ewarning的递减速度相对较快，但当节点能量普遍较低的情况，Ewarning递减的幅度就变慢。

综上所述，考虑邻居节点的剩余能量和节点剩余能量，引入节点分类概念，建立新的链路权值函数，提出了LORA_SPT算法。Re(i)表示节点i的剩余能量，Re(j)表示节点j的剩余能量，wij表示链路(i，j)的权值，Cij(g，d)表示传感节点i与节点j之间传输g比特数据的能量消耗，dij表示节点i与节点j的距离。在LORA_SPT算法中，取

其中，α是能耗因子，θ是发送节点剩余能量因子，β是接收节点剩余能量因子，ηi是节点i类型权重因子，而且这四个因子都是正常数。

在完成此轮网络权值的更新后，利用最短路径树中典型dijkstra算法求源节点到目标节点的最短路径，输出算法生成的最优树。节点一般选择链路能耗小且经过标准节点的路径发送数据，从而避免警告节点成为枢纽节点，平衡节点能耗，延长网络生存时间。

3 算法的实现

提出的LORA_SPT是一种集中式路由算法。算法实现主要在Sink节点上完成，其具体的实现步骤如下:

第一步:网络开始时，每个节点初始化自身的信息。

第二步:Sink节点开始收集算法所需要的节点信息。Sink节点以洪泛方式向周围所有的邻居节点发送信息查询分组。

第三步:邻居节点接收到Sink节点的查询分组后，将自己的剩余能量Re(i)、所要发送的数据量、位置坐标等信息发送给Sink节点。Sink节点收集所有节点信息(节点位置坐标、剩余能量等)后，启动LORA_SPT算法。

第四步:根据当前的网络参数x值，计算f(x)和Ewarning，确定标准节点和警告节点的数量，判断警告节点数量比例是否大于Ys。大于则x=x+1。

第五步:计算网络链路的权值，通过dijkstra算法计算每个节点的数据发送最短路径。

第六步:LORA_SPT算法计算完成后，Sink节点以洪泛方式通知网络中所有节点此时网络的最短路径树。所有节点根据接收到的最短路径树，寻找自身到Sink节点的最短路径，并沿着此路径发送数据。

第七步:当数据发送一段时间后，重新跳到第二步，Sink节点重新收集各个节点信息，更新网络链路权值。

上述的步骤循环执行，直到传感节点能量耗尽死亡。具体见如下的LORA_SPT算法伪代码。

分析LORA_SPT算法的时间复杂性。LORA_SPT算法主要由标准节点和警告节点的确定，链路权值的计算和最短路径的建立三个部分组成。第一部分只需要对所有节点进行判断，即标准节点和警告节点确定的时间复杂度是Θ(|V|)。第二部分是二层循环计算每个链路的权值，即链路权值计算的时间复杂度是Θ(|V|2)。第三部分是dijkstra算法，即最短路径建立的时间复杂度是Θ(|V|2)［11］。总之，LORA_SPT算法的时间复杂度是Θ(|V|2)，和最短路径dijkstra算法一致。

4 算法的仿真

4.1 仿真参数选择

由于一般情况下通信能耗远远大于其它一些能耗，因此在仿真时，不考虑计算、数据融合、信息查询分组收发等能耗，也不考虑数据传输过程中超时重发、出错等能耗，只考虑数据无线通信能耗［12］。选择500×500 m2网络仿真区域，在该区域内随机产生均匀分布的30、40、50、60、70、80、90、100 个无线传感网节点(包括一个Sink节点和其它传感节点)的位置分布，其中Sink节点固定坐标(250，250)。为了验证算法的有效性，针对每个固定节点数量的无线传感网，随机产生10个不同的节点位置(即不同网络拓扑结构)，根据表1的仿真参数分别计算这10个网络拓扑结构不同的无线传感网生存时间、节点平均能耗和节点平均时延，最后取其平均值作为该节点数量的无线传感网性能参数的仿真结果值。

表1 仿真参数表

其中，网络生存时间定义为网络开始运行到任意一个节点能量耗尽时Sink节点完成的数据收集周期个数(data gathering cycle，DGC)。一个DGC是指网络中所有节点感知1 000g比特数据，并将数据发送给Sink节点所需要的时间。

节点平均能耗=当一个节点能量耗尽时所有节点的总能耗/(节点数×DGC数)。

节点平均时延=当一个节点能量耗尽时所有节点将数据发送给Sink节点的总跳数/(节点数×DGC数)。

4.2 算法的关键参数研究

权值函数中的节点类型权重因子η是区分标准节点和警告节点的周围链路权值。警告节点的周围链路权值大，路径选择时优先考虑选择标准节点。但是η值也不宜取的过小，否则导致节点能量在权值函数中的影响过大，因此定义标准节点的η值是1，警告节点的η值是0.25。以下主要是研究α、θ和β取值对网络生存时间和节点能耗的影响。由于式(7)中存在多个参数，在参数研究过程中采用穷举法来获得仿真数据。选择30、40、50、60、70、80、90、100 个无线传感节点，3 个参数分别选择{0.1，0.4，0.7，1，3，5}集合中的值，三层循环获得所有可能的仿真数据。分析仿真数据可知:当研究LORA_SPT算法中的任一参数时，其它2个参数可选择{0.1，0.4，0.7，1，3，5}集合中的任意值进行仿真，仿真结果能显示该参数的取值规律。为了方便说明，以其中一种典型数据为例分析参数取值规律，具体分析如下。

伟人毛泽东，在政治家、军事家、思想家、哲学家外，还有诗人、杂文家之称！“兼得”如此多，仍可用“三杂”来诠释：学识杂、文体杂自不必说，阅历杂亦毋庸赘言。

4.2.1 α 值的选择

分析仿真数据可知(以θ=1、β=1为例，如图1和图2):当α≥1时，α值越大，节点平均能耗越大，网络生存时间越小。这是因为:在α≥1时，α值越大，权值函数(7)越加强通信能耗的作用，从而降低其它二个参数(节点剩余能量和邻居剩余能量)的作用，路径选择时会选择链路能耗小但邻居节点剩余能量也小的链路，从而降低了网络生存时间，也增加了平均能耗。当α＜1时，α值越小，网络生存时间越小，网络平均能耗越大。这是因为:当α＜1时，α值越小，权值函数(7)越削弱通信能耗的作用，相应加强其它两个参数的作用，从而导致链路的能耗被忽视，使一些节点直接往剩余能量大但链路能耗也大的邻居节点发送数据，这样增大了平均能耗，降低了网络生存时间。

图1 α对网络生存时间(DGC)的影响

图2 α对节点平均能耗的影响

综上所述，在LORA_SPT算法中，选择适当的α可以延长网络生存时间。

4.2.2 θ值的选择

分析仿真数据可知(以参数α=1、β=1为例，如图3和图4):当θ＜1时，θ越接近于1，网络生存时间越大，但平均能耗也越大。这是因为:当θ＜1时，θ越小，权值函数(7)越削弱节点剩余能量的作用。此时网络过少考虑节点剩余能量导致部分枢纽节点(树中主干节点)过多的参与数据的转发，能量消耗过快而失效，网络生存时间越小。由于只是部分节点消耗过多的能量，其它节点能量消耗不大，因此θ越小，节点平均能耗也越小。当θ≥1时，θ对网络生存时间影响不大，但能耗随着θ的增大而增大。这是因为:当θ≥1时，节点剩余能量对权值函数(7)的影响足够大，权值函数中节点剩余能量占主要因素，于是网络生存时间基本已达到顶峰。但是在最短路径树的建立过程中，部分节点会选择剩余能量大但是链路通信能耗也大的邻居节点作为父节点，导致节点平均能耗随着θ的增大而增大。

图3 θ对网络生存时间(DGC)的影响

图4 θ对节点平均能耗的影响

综上所述，在LORA_SPT算法中，选择适当的θ可以延长网络生存时间。

4.2.3 β 值的选择

综上所述，在LORA_SPT算法中，选择适当的β可以延长网络生存时间。

图5 β对网络生存时间(DGC)的影响

图6 β对节点平均能耗的影响

4.3 算法仿真结果比较

根据4.2部分的参数研究，得出生存时间延长效果较好的参数如 α=1，θ=1，β=0.7时。将 LORA_SPT算法的链路权值公式改为:

为了反映算法的有效性，将LET、PEDAP_PA、Ratio_w、Sum_w和LORA_SPT等算法进行比较。

图7比较了各算法的网络生存时间，从图中可知:LORA_SPT算法的网络生存时间(DGC个数)比LET、PEDAP_PA、Ratio_w和 Sum_w算法更大，是最优的，其次是Ratio_w算法。这是因为该算法综合考虑链路能耗，自身节点能耗和邻居节点能耗，同时引入类型权重因子，避免剩余能量较小的节点(警告节点)过多参与数据的路由而过早死亡，因此在网络生存时间方面，LORA_SPT延长了网络生存时间。

图7 各算法的网络生存时间比较图

图8比较了各算法的节点平均能耗。从图中可知:LORA_SPT、LET、Sum_w和Ratio_w算法的节点平均能耗相差不大，但是这四个算法的平均能耗远低于PEDAP_PA算法。这是因为要避免枢纽节点过早能量耗尽而死亡，LORA_SPT算法在一些路径选择上避免该枢纽节点而选择能耗相对较大的路径，因此，在能耗方面，LORA_SPT算法在一定程度上将能耗保持在较低的水平。

图8 各算法的平均节点能耗比较图

图9比较了网络某一个节点能量耗尽时其它节点的平均剩余能量。从图中可知:LORA_SPT算法平均剩余能量最低、Ratio_w和PEDAP次之，但这三个算法高于LET和Sum_w。这是因为LORA_SPT算法把节点分成两类节点(标准节点和警告节点)。警告节点的类型权重因子小，周围链路权值变大。在路径选择时就尽量避免选择警告节点，从而每个节点根据剩余能量选择性参与网络路由，均衡能量消耗。因此，在能耗方面，LORA_SPT算法均衡了网络各个节点的能耗。

图9 各算法的平均节点剩余能量比较图

图10比较了各算法的网络平均时延(跳数)。从图中可知:LORA_SPT算法的网络平均时延最小，LET、Sum_w和 Ratio_w算法的网络平均时延比LORA_SPT算法较大，但这四个算法的平均时延远低于PEDAP_PA。这是因为LORA_SPT算法考虑了新的权值函数，优化的网络生存时间，在路径选择上节点选择比较优化的路径，从一定程序上减低了节点到Sink节点的平均跳数。因此在网络时延方面，LORA_SPT算法降低了网络的时延。

图10 各算法的网络平均时延(跳数)比较图

总之，LORA_SPT算法降低了网络平均时延(跳数)，将节点平均能耗保持在较低的水平，均衡了网络各个节点的能耗，提高了延长网络生存时间，比LET、PEDAP_PA、Sum_w和Ratio_w算法更优。

5 总结

LORA_SPT算法构造了基于能耗因子、自身节点剩余能量因子、邻居节点剩余能量因子和类型权重因子等因子的权值函数，针对不同类型的节点采用不同的权重因子，最后利用dijkstra算法完成最短路径树。

LORA_SPT算法是集中式路由算法，需要节点把自身信息汇聚到Sink节点，Sink节点处理完再通知其它节点网络拓扑结构。集中式路由算法能够被应用在静态网络中，但是不能很好地适应具有动态拓扑特性的无线传感网。于是下一步工作的重点是研究动态拓扑的无线传感网分布式路由算法。

［1］Akyildiz I F，Su W L，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40(10):2－116.

［2］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［3］Wu X Y，Cassandras C G.A Maximum Time Optimal Control Approach to Routing in Sensor Networks［A］.Proceedings of the 44th IEEE Conference on Decision and Control，and the European Control Conference［C］//Spain:IEEE Computer Press，2005:1137－1142.

［4］刘铁流，巫咏群.基于能量优化的无线传感器网络分簇路由算法研究［J］.传感技术学报，2011，24(5):764－770.

［5］Tan H O，Korpeoglu I.Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks［J］.SIGMD Record，2003，32(4):66－71.

［6］Zhu Y H，Wu W D，Victor C M，et al.Energy-Efficient Tree-Based Message Ferrying Routing Schemes for Wireless Sensor Networks［A］.Thirteen International Conference on Communications and Networking in China［C］//Hangzhou，China，2008:25－28.

［7］朱艺华，沈丹丹，吴万登，等.无线传感器网络优化生存时间的动态路由算法［J］.电子学报，2009，37(5):1041－1045.

［8］陈友荣，俞立，董齐芬，等.基于近邻算法的无线传感器网络功率控制［J］.浙江大学学报(工学版)，2010，44(7):1321－1326.

［9］董齐芬，俞立，陈友荣，等.移动无线传感网中的迭代蒙特卡罗定位算法研究［J］.传感技术学报，2010，23(12):1803－1809.

［10］班艳丽.基于能量有效的ZigBee网络路由算法研究［D］.山东大学，硕士学位论文，2009.

［11］Dimitri Bertsekas，Robert Gallager.卢刚，王康，译.数据网络(第二版)［M］.北京:人民邮电出版社，2004－06.

［12］Chen Y R，Yu L，Dong Q F，et al.Distributed Lifetime Optimized Routing Algorithm for Wireless Sensor Networks［J］.Applied Mechanics and Materials，2011，40－41:448－452.