基于最短路径树的分布式功率控制路由算法*

陈友荣，任条娟，刘半藤，葛灵晓

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

无线传感网通常有一个重要目标——延长网络生存时间。由于大部分情况下所有节点的能量有限，不能补充和更换，一旦节点能量耗尽，该节点就会失效，这将影响到网络的运行，甚至可能导致网络的瘫痪，因此延长网络生存时间可以节省重新部署无线传感网的巨大开销［1］。

目前，无线传感网路由的研究已取得一些成果。文献［2－3］用分布式的线性规划公式表示路由问题，采用对偶分解和次梯度方法求解最优路由方案，最大限度提高网络生存时间，但是用最优化方法研究路由方案的算法复杂，很难在实际硬件环境中实现。文献［4］提出LET(Least Energy Tree)算法。它是根据dijkstra算法构建每个节点到Sink节点能耗最小的最短路径树，最终所有节点沿着最短路径树将数据发送给Sink节点。文献［5］在LET算法的基础上提出了“比例权值路由算法”Ratio_w(Ratio Weight Routing Algorithm)与“和权值路由算法”Sum_w(Sum Weight Routing Algorithm)。文献［6］提出多树路由，在数据发送过程中从多个树路径中选择当前合适的路径，最终平衡节点能耗，提高网络生存时间。上述路由算法都假设Sink节点能获得整个网络拓扑信息或者节点能获知与邻居节点的距离，而且节点可根据与邻居节点的距离自动调整发送功率，从而减少链路能耗。如果Sink节点要得到整个网络拓扑信息或者节点要获知与邻居节点的距离，可通过以下两种方法实现。第1种方法是添加额外硬件模块，如配置GPS模块收集每个节点的位置坐标，或者采用超声波、红外等模块测量节点间距离，通过定位方法计算每个节点的位置坐标。第2种方法是不需要添加额外的硬件模块，根据节点间通信的RSSI值，估计两个节点的距离，通过3边定位等定位算法获得网络节点位置坐标。第1种方法需要添加额外硬件，增加了无线传感网的硬件成本。第2种方法在实际环境中，尤其是在恶劣环境中，RSSI的测量误差非常大，很难准确测量两个节点间距离。

考虑到通过两节点间距离(即通信距离)调整节点发送功率不总是可行的，尤其当节点不增加无线传感网硬件成本而且节点很难获知与邻居节点的距离时，针对此类网络枢纽节点能量消耗过快而过早失效，从而减少网络生存时间的问题，提出基于最短路径树的分布式功率控制路由算法DPCRA_SPT(Distributed Power Control Routing Algorithm Based on Shortest Path Tree)。当节点很难获知节点到邻居节点的距离时，该算法随着节点剩余能量的减少而自动调整节点发送功率，从而调整整个网络的拓扑结构。DPCRA_SPT算法还综合考虑网络中传输数据的能耗、邻居节点的剩余能量，引入分布式算法的权值函数。每个节点利用分布式非同步Bellman-Ford算法构建最短路径树。最终，数据沿着当前网络拓扑结构下的最短路径树汇聚到Sink节点。

1 系统假设

在DPCRA_SPT算法中，假定传感节点(简称节点)随机分布在一个正方形区域内，周期性地采集周围环境信息，并假设如下:

(1)Sink节点和所有传感节点位置固定不变，都是静止的，而且Sink节点不能获知整个网络拓扑结构信息；

(2)所有传感节点具有相同的性能(如初始能量、能耗参数、无线电最大发送功率、最大通信半径等)；

(3)所有传感节点采用统一的能量模型；

(4)所有传感节点都能感知数据，并通过直接或多跳的方式将数据发送给Sink节点；

(5)每个传感节点能量受限，但Sink节点能量不受限制；

(6)所有传感节点没有安装GPS等模块，无法获知自身的位置坐标，也无法获知节点到邻居节点的距离。

2 链路能耗模型

常见的链路传输模型是根据发送节点与接收节点之间距离的Friss自由空间模型和多径衰弱模型。如果发送节点与接收节点之间的距离小于交叉距离dcrossover，则使用Friss自由空间模型(d2衰减)。如果发送节点与接收节点之间的距离大于或等于交叉距离dcrossover，则使用两线地面传播模型(d4衰减)［7］。交叉距离dcrossover的定义如下:

其中Ds≥1，与无线传播的数据丢包率有关，hr与发送节点的天线高度有关，ht与接收节点的天线高度有关，b代表电磁波的波长。采用根据无线通信能量消耗模型部分参数如下:全向天线，ht=hr=1.5，系统丢失率Ds=1［7］，而且无线传感网通常采用2.4GHz的无线信号，b=0.125 m，可得dcrossover=226 m。由于交叉距离已经大于一般无线传感网节点的通信距离，因此链路能耗模型选择Friss自由空间模型，其发送功率和通信距离的关系如下

式中:Pi是发送节点i的发送功率，是接收节点的最小接收功率，是节点i选择发送功率Pi时的最大通信距离。当节点i采用最大发送功率发送数据时，节点j能接收到该数据包，则节点j是节点i的邻居节点，即j∈N(i)，其中N(i)表示节点i的所有邻居节点集合。

典型的无线传感网节点能耗主要由无线数据收发产生［8］。节点发送模块的能耗ETx由发送电路电子能耗ETx-elec和信号放大器部分的电子能耗ETx-amp组成。节点发送模块能耗中的发送电路电子能耗ETx-elec和接收模块中的能耗ERx，固定为gEelec，其中g代表所发送或接收的数据量。信号放大器部分的电子能耗大小与发送功率Pi有关。链路能耗模型计算公式改为:

根据式(3)和式(4)可知:传感节点i与节点j之间传输g比特数据的能耗取为:

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

3 算法的原理

通常把计算从源节点到目的节点的最短路径权值称为单源最短路径问题。目前，解决单源最短路径的方法有很多，分布式非同步Bellman-Ford算法是其中的一种实现简单的分布式算法［9］。

该算法在利用分布式非同步Bellman-Ford算法寻找最短路径问题前需要解决以下两个问题。

第1个问题是链路权值的设定会影响网络的生存时间。考虑到DPCRA_SPT算法是分布式算法，每个节点发送数据前需要根据周围局部信息选择邻居节点，但是节点自身剩余能量不影响邻居节点的选择，因此DPCRA_SPT算法简化链路权值，只考虑链路能耗(式(5)和(6))和邻居节点的剩余能量，路由应该选择邻居节点剩余能量大而且链路能耗小的邻居节点发送数据。以Re(i)表示节点i的剩余能量，以Cij表示链路L(i，j)的能耗，以wij表示链路L(i，j)的权值。在DPCRA_SPT算法中，取

其中α是“能耗因子”，β是“接收剩余能量因子”，而且这两个因子都是正常数。

第2是如何根据当前局部信息，调整节点发送功率，从而改变网络的拓扑结构，其具体算法见下一节功率控制算法。

确定节点的发送功率后，即网络拓扑结构确定，DPCRA_SPT算法采用分布式非同步Bellman-Ford算法找到一颗树根在Sink节点的最短路径树。所有节点沿着最短路径树，将数据传送到Sink节点，从而各个节点均以最小能耗将数据发送到Sink节点。

3.1 功率控制算法

由于节点不能获知与邻居节点的距离，但是节点可获知自身剩余能耗信息，因此DPCRA_SPT算法根据节点剩余能量调整发送功率，改变网络的拓扑结构，避免该节点能量过早消耗而死亡。如图1所示，网络刚开始运行时，1号节点的剩余能量充裕，发送功率大，它可与实线内的所有节点(2～8号节点)通信，与其它节点组成到Sink节点的数据发送路径，较多的参与数据路由；随着节点剩余能量的减少，1号节点为避免能量过快消耗，减少自身发送功率，只能与虚线内的节点(2～5号节点)通信；当1号节点的发送功率降到最小要求功率(能与距离最近的2号节点通信的最低发送功率)时，不再改变其发送功率。如果网络中枢纽节点能量消耗过快，该方法减少发送功率，减少能量消耗，因此能提高网络的生存时间［10］。

图1 发送功率调整示意图

由上述内容可知，DPCAOL_SPT算法调整节点的发送功率，改变网络拓扑结构，以下给出具体的发送功率衰减模型。图2是节点发送功率随着剩余能量变化的线性功率衰减曲线图。定义［0－1］区间的两个参数 γl1和 γl2，如图 2所示，F点位置是(γl1Emax，γl2(Pmax－Pmin(i))+Pmin(i))，功率衰减曲线主要是经过F点的两条线段组成。每个节点根据剩余能量和衰减曲线，改变节点发送功率。

图2 线性功率衰减曲线

从式(8)可知，线性衰减可出现3种情况。当γl1=0时，F点在x=0的纵坐标上，该节点衰减的曲线是经过(Emax，Pmax)和F点的线段。当γl1=1时，F点在x=Emax的纵坐标上，该节点衰减曲线是经过(0，Pmin(i))和F点的线段。当0＜γl1＜1时，该节点衰减曲线由两条线段组成，分别是经过(Emax，Pmax)和F点的线段和经过(0，Pmin(i))和F点的线段。

4 算法的实现

提出的DPCRA_SPT是一种分布式功率控制算法。每个节点根据剩余能量调整发送功率，接收邻居节点信息，采用分布式Bellman-Ford算法找到到Sink节点的最优路径，具体的实现步骤如下:

第1步 网络启动时，节点为了获知与邻居节点通信的最低发送功率，其发送功率从0 W开始递增发送Hello信号。邻居节点第一次收到该节点的Hello数据包，则反馈一个Ack包。

第2步 该节点接收到邻居节点的Ack包后，添加该邻居节点通信的最低要求功率到节点邻居信息表中。

第3步 当节点将发送功率递增到最大发送功率后，对邻居节点发送路径预测信息分组(包括节点ID，到Sink节点的最短路径权值预测值Di、节点剩余能量E(i))。邻居节点收到这些信息后添加到邻居信息表中。

第4步 节点根据当前剩余能量，执行相应的公式计算当前的发送功率Pi。节点采用发送功率Pi发送数据。

第5步 如果发送功率变换，更新相应的链路权值。节点根据邻居信息表中信息，执行Bellman-Ford公式计算其最短路径权值Dij。如果最短路径权值发生变化，向邻居节点发送路径预测信息分组(包括节点ID，到Sink节点的最短路径权值预测值Di、节点剩余能量E(i))。

第6步 根据邻居节点的信息，节点选择通信的最低发送功率小于当前发送功率且在最小权值路径上的邻居节点发送数据。

第7步 发送完若干比特数据后，跳到第4步，更新当前的发送功率。

经过上述步骤的循环，直到网络死亡，即出现一个节点能量耗尽或数据不能到达Sink节点。在实现过程中，节点不时向其所有邻居节点发送最新预测信息分组。邻居节点获得信息分组，更新邻居信息表，执行Bellman-Ford公式，选择最小路径权值的节点发送数据。如果一段时间内，没有接收到邻居节点的最新预测信息分组或发送数据后没有接收到反馈分组，则认为该链路出现故障，在邻居信息表中删去该邻居信息。

节点i的伪代码如下:

分析DPCRA_SPT算法的时间复杂性，假设节点发送预测信息分组的频率是Hi。考虑最好的情况即所有邻居节点Dj不变化，此时它的时间复杂度Θ(N(i))。考虑最坏的情况，即所有邻居节点Dj都变化，每次变化都需要重新计算到Sink节点的最短路径权值，此时它的时间复杂度是Θ(HiN(i))。

5 算法的仿真

5.1 仿真参数选择

由于无线传感网是应用相关的网络，即不同的应用背景对无线传感网的要求不同，所以研究者没有统一网络生存时间的度量方法。如果网络中一个节点能量耗尽就会影响到网络的正常运行，甚至导致网络出现分裂，此时网络生存时间的度量方法可定义为网络开始运行到任意一个节点能量耗尽时的这一段时间，也可定义为网络开始运行到网络中任意一个节点数据不能达到Sink节点时的这一段时间［11］。它也可以定义为当某个网络参数指标(如生存节点占总节点数量的比例、存活数据流占总数据流的比例、数据包到达率，或覆盖度等)达到某一预先设定的阀值时，判断网络生存时间终止。但是对于不同的应用，甚至同一类应用的不同实例，网络参数指标很难做出定量的判断，过多地强调参数指标，反而使得网络生存时间缺乏统一标准［12］。因此在仿真中，生存时间的度量值采用网络开始到网络中出现任意一个节点能量耗尽或节点数据不能达到Sink节点的这一段时间。

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

定义网络生存时间的值为网络开始运行到任意一个节点能量耗尽时Sink节点完成的数据收集周期个数DGC(Data Gathering Cycle)。一个DGC是指网络中所有节点感知1 000g比特数据，并将数据发送给Sink节点所需要的时间。节点平均能耗=当一个节点能量耗尽时所有节点的总能耗/(节点数×DGC数)。节点平均时延=当一个节点能量耗尽时所有节点将数据发送给Sink节点的总跳数/(节点数×DGC数)。

表1 仿真参数表

5.2 算法的关键参数研究

算法的关键参数是影响链路权值的α和β值，影响衰减模型的参数γl1，γl2，以下就是各个参数的选择。

5.2.1 α 和 β值的选择

研究式(7)中α和β值参数，在参数研究过程中采用穷举法获得仿真数据。选择30、40、50、60、70、80、90、100个节点的无线传感网，采用线性衰减模型，α 和 β 参数分别选择{0.1，0.4，0.7，1，3，5}集合中的值，循环获得所有可能的网络生存时间和平均节点能耗。分析仿真数据可知:当DPCRA_SPT算法中的某个参数固定，另一参数可选择{0.1，0.4，0.7，1，3，5}集合中的任意值进行仿真，仿真结果能显示该参数的取值规律。为了方便说明，以其中一种典型数据为例分析参数取值规律，具体分析如下。

分析仿真数据可知(以 β=1，γl1=0.5，γl2=0.5为例，如图3和图4):在节点数给定后，当α≥1时，如果α偏向于5，网络过多地考虑链路能耗在权值函数式(7)中的作用，着重考虑链路能耗，忽略了节点剩余能量参数，节点直接选择链路能耗最小的路径。由于此时容易产生枢纽节点导致能量消耗过快，因此网络生存时间随着α的增大而减小。当α≤1时，α 4种不同取值的网络生存时间差别不大，但是从具体数据分析，当α=0.7时，网络生存时间相对较大。虽然α≤1时网络平均能耗变化不明显，但是当α≥1时网络平均能耗随着α的增大而降低。这是因为当α≥1时，过多地忽略了节点剩余能量则导致当前发送路径不理想，网络生存时间下降明显。由于计算平均能耗时需除以网络生存时间，因此节点平均能耗也增加。

图3 α因子对网络生存时间的影响

图4 α因子对节点平均能耗的影响

总之，在DPCRA_SPT算法中，选择适当的α可以延长网络生存时间。

分析仿真数据可知(以 α=0.7，γl1=0.5，γl2=0.5为例，如图5和图6):当β≥1时，β≥3的网络生存时间比β=1时略微增加。这是因为:在β≥3时，权值函数式(7)中邻居节点剩余能量对权值函数的影响已经足够大，这导致节点直接选择剩余能量大的邻居节点转发数据，此时β值的变化基本不影响最短路径选择，从而使网络生存时间相差很小。由于只是选择剩余能量大的邻居节点，基本上不考虑节点的链路能耗。当β≥1时，随着β的数量增大，节点平均能耗增大。当β≤1时，在节点数给定后，β越接近于1，网络生存时间越大。这是因为:β越小，权值函数过少地考虑节点剩余能量作用，权值函数偏向于链路能耗，因此网络生存时间变小。由于几个主干节点(即枢纽节点)转发过多的数据，过早消耗能量而失效，但是其它节点能量消耗不大。因此当0.3≤β≤1时，网络平均能耗相差不大。由于当β=0.1时，网络生存时间下降太快，此时平均能耗偏大。

图5 β因子对网络生存时间的影响

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

总之，在DPCRA_SPT算法中，选择适当的β可以延长网络生存时间。

综上所述，在DPCRA_SPT算法中，选择适当的参数如α=0.7、β=1可以延长网络生存时间、保持平均能耗在较低水平。

5.2.2 γl1和 γl2值的选择

研究式(8)中γl1和γl2两个参数，在参数研究过程中采用穷举法来获得仿真数据。在参数研究过程中选择100节点的线性功率衰减模型，α=0.7，β=1，γl1和 γl2分别取值 0，0.1，0.2，…，1，二层循环得到网络生存时间的仿真数据，获得三维图7。分析图中网络生存时间可知，当γl1固定值，刚开始网络生存时间随着γl2的增加而增加。当γl1和γl2两个参数差不多时，网络生存时间达到峰值，此后随着γl2的增加而减少。

图7 γl1和γl2对网络生存时间的影响

总之，选择适当的γl1和γl2值，DPCRA_SPT算法可以较好地反映网络生存时间。

5.3 仿真结果和分析

根据5.2节的参数研究，得出能较好延长网络生存时间的参数如 α=0.7，β=1，γl1=0.5 和 γl2=0.5，将DPCRA_SPT算法的链路权值公式改为:

为了反映算法的有效性，选择采用固定最大发送功率的Ratio_w算法(记为Ratio_w_FTP)，采用固定最大发送功率的 Bellman-Ford算法(记为BFFTP)，采用阶梯衰减模型的Bellman-Ford算法(记为 BFSAM)［13］，采用 γn阶二项式衰减模型的Bellman-Ford 算法(记为 BFPAM)［13］进行比较。

图8比较了各算法的网络生存时间。如图可知:当节点数量是30时，由于网络节点分布比较稀疏，一般节点通信需要最大发送功率，此时功率衰减模型反而降低了网络生存时间，因此 BFSAM、BFPAM和DPCRA_SPT 3个算法的网络生存时间比Ratio_w_FTP和BFFTP低，但是从数据上看BFFTP比Ratio_w_FTP略高。当节点数量大于30时，DPCRA_SPT的网络生存时间最高，BFPAM次之，BFSAM第三，但这3个算法的网络生存时间比Ratio_w_FTP和BFFTP高。这是因为当节点数量大于30时，随着节点数量的增加，节点分布相对密集，此时节点不需要太大的发送功率，功率衰减模型体现出其价值，调整网络的拓扑结构，从而延长网络生存时间。节点分布越密集，延长网络生存时间的效果越明显。总之，当节点分布密集时，DPCRA_SPT算法，能延长网络生存时间。

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

图9比较了各算法的节点平均能耗。如图可知:BFSAM的能耗最低，DPCRA_SPT算法次之，BFPAM算法第三，但是这3个算法都比Ratio_w_FTP和BFFTP算法低，而BFFTP算法和Ratio_w_FTP算法平均能耗基本一样。这是因为:BFSAM、BFPAM和DPCRA_SPT这3个算法根据节点剩余能量的变化随时改变自身的发送功率，调整网络的拓扑结构，从而降低了节点的能耗。总之，DPCRA_SPT降低了节点的平均能耗，将能耗保持在较低的水平。

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

图10比较了各个算法的节点平均时延(跳数)。如图可知:BFSAM、BFPAM和DPCRA_SPT三个算法的网络平均时延(跳数)波动很大，而且比BFFTP算法和Ratio_w_FTP算法高。这是因为，随着节点剩余能量的减少，节点相对应减少了发送功率，可通信的范围变小，此时数据到达Sink节点的跳数，即网络平均时延增加。总之，BFSAM、BFPAM和DPCRA_SPT算法不能降低网络平均时延(跳数)。

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

综上所述，当节点分布密集时，DPCRA_SPT算法可以延长网络生存时间，将能耗保持在较低的水平，比 Ratio_w_FTP、BFFTP、BFSAM、BFPAM 算法更优。

6 总结

如果节点不能测量到邻居节点的距离，通过两节点间距离调整发送功率就不可行，因此提出根据节点剩余能量改变自身发送功率的DPCRA_SPT算法。首先，详细阐述链路能耗模型和系统假设。其次，考虑网络中链路通信的能耗和邻居节点的剩余能量，引入新的权值函数和功率线性衰减模型。运用分布式非同步Bellman-Ford算法构建最短路径树，所有节点沿着最短路径树将数据汇聚到Sink节点。最后，仿真分析权值函数式(7)和线性衰减模型中相关参数对网络生存时间和平均能耗的影响，仿真比较DPCRA_SPT算法对网络生存时间、平均能耗和平均时延的影响。

DPCRA_SPT算法适用于节点密集分布的无线传感网，而且只是根据自身的剩余能量信息修改发送功率，当节点发送功率降低一定程度时容易造成网络的分裂。因此下一步研究的工作是节点如何根据邻居节点的信息，确定当前拓扑下的全局最优发送功率。

［1］朱艺华，杨晨曦，吴万登，等.无线传感器网络权衡生存时间与数据分组跳数的分流路由算法［J］.传感技术学报，2009，22(2):273－279.

［2］Manan R，Lall S.Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Network［J］.IEEE Transactions on Wireless Communications，2006，5(8):2185－2193.

［3］He Y F，Lee I，Guan L.Distributed Algorithms for Network Lifetime Maximization in Wireless Visual Sensor Networks［J］.IEEE Transactions on Circuits and System for Video Technology，2009，19(5):704－718.

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

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

［6］Fariborzi H，Moghavvemi M.EAMTR:Energy Aware Multi-Tree Routing for Wireless Sensor Networks［J］.Special Issue on Wireless Ad-Hoc Networks，2009，3(5):733－739.

［7］Wendi B H.Application-Specific Protocol Architectures for Wireless Networks［D］.Boston:Massachusetts Institute of Technology，2000.

［8］Gatzianas M A，Georgiadis L G.A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink［J］.IEEE Transactions on Wireless Communications，2007，7(3):984－994.

［9］Bertsekas D，Gallager R.数据网络(第二版)［M］.卢刚，王康，译.北京:人民邮电出版社，2004.

［10］Minhas R M，Gopalakrishnan S，Leung V C M.An Online Multipath Routing Algorithm for Maximizing Lifetime in Wireless Sensor Networks［C］//2009 Sixth International Conference on Information Technology.New Generations，2009:581－586.

［11］陈友荣，刘半藤，程菊花，等.无线传感网优化生存时间的分布式功率控制［J］.传感技术学报，2011，24(12):1787－1793.

［12］潘晏涛.传感器网络生存时间优化问题研究［D］.国防科学技术大学，2006.

［13］Chen Y R，Lu Y W，Cheng J H，et al.L.Distributed Power Control Algorithms for Wireless Sensor Networks［J］.Lecture Notes in E-lectrical Engineering，2011，98(2):319－326(EI).