基于动态传输功率的重编程能量均衡算法

周培锋， 韩江洪，2， 卫 星，2

（1.合肥工业大学 计算机与信息学院，安徽 合肥 230009；2.安全关键工业测控技术教育部工程研究中心，安徽 合肥 230009）

0 引 言

随着无线传感网络［1］的普及，成百上千的传感器节点被部署在复杂多变的外界环境中，在无人监守的情况下执行监测任务，而直接深入安装区域，手工维护每个传感器节点是一项几乎不可能完成的工作。尽管如此，人们仍希望能够增加和改变传感器节点的功能和配置以使其能够发挥更大的作用。网络重编程技术［2－3］的产生，有效地解决了上述问题。

在无线传感网络重编程领域，XNP［4］是TinyOS操作系统自带的一个支持最简单的网络重编程服务的分发协议，但它只提供了单跳网络的重编程解决方案；Deluge［5］是一种支持多跳网络的分发协议，采用流水线方式进行代码的传输，提高了传输效率，但数据碰撞及隐藏终端等问题随之出现；文献［6］设计了一种称为 Queen’s Differential（QDiff）的重编程方法，采用克隆检测技术最大限度地保持了新旧代码的相似性，而且用一种新方法组织全局变量以消除变量改变带来的影响，但过于依赖具体的执行环境，通用性不强；文献［7］提出一种增量式代码更新策略，它通过传输新版本代码镜像，与传递整个镜像相比，减小了网络上传输数据的大小，降低了重编程的能量消耗，但只适用于新旧版本程序差别较小的情况；MNP算法［8］的基本思想是源节点以一定功率向外广播探测帧，包含代码镜像及发送节点的ID等信息，若节点需要该镜像则与源节点建立连接并回复请求帧。为了提高能量利用率，选择收到请求帧数目最多的节点作为下一个代码发送节点。但该算法采用固定发送功率进行代码分发，造成能量的浪费，且网络中心位置的节点能量消耗过大，容易过早死亡。

本文在学习借鉴上述协议与算法的基础上，提出一种基于动态传输功率的重编程能量均衡算法，可以实现动态地选取最优传输半径，进一步降低重编程能量消耗，同时考虑传感器节点的剩余能量，在一定程度上提升网络的能量均衡性。

1 系统假设

在本文所提出的基于动态传输功率的重编程能量均衡算法中，假设传感器节点随机分布在一块监测区域内，周期性地采集信息并上传到监控中心，并作如下假设：

（1）网络拓扑结构已知，监控中心保存了整个网络当前的拓扑信息。

（2）所有传感器节点具备同样的功能，包括发送功率的等级划分、初始能量、能耗参数及通信半径等。

（3）传感器节点采用统一能耗模型。

（4）所有传感器节点都受能量限制，监控中心保存所有节点的剩余电量信息。

（5）所有传感器节点都要被重编程。

（6）重编程的代码首先由监控中心发给初始广播节点，再按照一定的路径分发，直至覆盖所有的传感器节点。

2 链路能耗模型

无线传感网络链路能耗主要由无线数据收发产生［9］，传感器节点发送模块能耗ETx包括节点发送电路的电子能耗ETx－elec和信号放大器部分能耗ETx－amp，发送电路的电子能耗固定为kEelec，k为发送的数据量，信号放大器部分的电子能耗大小与发送的距离有关，具体如下：

接收模块的能耗ERx只考虑接收信号时的电子能耗kEelec，具体公式为：

假设发送k比特的数据量，发送的距离大小为di，j，最大通信距离为dmax，收发1bit数据时电路电子能耗为Eelec，信号放大器能耗为εfs，数据损耗系数［10］α∈［2，4］，则传感器节点i传输kbit数据到j所需能耗的计算公式为：

3 算法描述

3.1 算法原理

由于监控中心保存了整个网络的拓扑结构，则可以用一个无向图G（V，E）表示整个无线传感网络，其中，V为无线传感网络中的传感器节点；G（u，v）为节点u和节点v之间的边（即无线链路）；W（u，v）为节点u的权重（即两节点间的距离）；B（v）为节点v的剩余电量；P（i）为传感器节点的第i级传输功率；R（i）为P（i）所对应的传输半径的大小。

重编程的代码首先由监控中心发给初始广播节点，根据本算法的传输半径选取原则计算出选择最佳的传输半径R（i），即最佳传输功率P（i）。然后从W（i，v）中筛选小于或等于最佳传输半径R（i）的节点，即可得到被覆盖（重编程）的节点集合。再根据本算法的广播节点选择原则，从被覆盖的节点集合中选择合适的节点作为下一个广播节点。如此执行下去，直到所有的传感器节点都被重编程为止。在该过程中，每个发送节点都会有能量消耗，本算法要优化的目标就是重编程过程中所消耗的总能量，即

其中，n为选中的发送节点数；Ri为选择的发送节点的发送半径。

3.2 传输半径的选取

由于传感器节点随机分布，且传播范围以圆的形式覆盖，所以有：

其中，ni为半径Ri所能覆盖的传感器个数。

信号放大器能耗为：

当α＝2，Ri增大为2Ri时，有：

其中，θ为比例系数。

当传输半径增大2倍时，能量增大为原来的4倍，覆盖的节点数也相应增大为原来的4倍。当α＞2时，假设α＝3，半径增大为2Ri时，则有：

由（13）式可见，α＞2时，节点数目不随半径增大同比例增大，所以尽量选择小的功率进行覆盖，但是不能小于两点之间的最短距离。

现以Texas Instruments研发的一款低功耗无线单片机CC2430F128为例，它的发送功率从－25.2～0.4dBm依次增大，共10个等级，分别对应R1～R10，本文根据实际情况，从10个半径中选择合适的3～4个作为可选传输半径集合。广播节点依次选用集合中的传输半径进行覆盖，并记录每次覆盖耗费的能量与覆盖的传感器节点数量，为了选取最优传输半径，引入：

其中，分子为广播节点选用某个半径进行覆盖所耗费的能量；分母则为覆盖的传感器节点数量；Ei为覆盖一个传感器节点所需的能量。显而易见，Ei越小，本次覆盖的能量利用率就越高。因此，Ei最小时所对应的Ri即为最优传输半径。若ni为0，则认为Ei无限大，不可选用此时对应的半径进行传输。

3.3 广播节点的选择

广播节点也是普通传感器节点，在初始广播节点以最优传输半径完成第1次代码分发后，需要从已被覆盖的传感器节点中选择下一个广播节点，将重编程的代码继续分发下去，直至所有的传感器节点都被重编程。鉴于广播节点完成一次代码分发需要耗费较多的能量，而传感器节点的能量受限，为避免某个传感器节点过早的死亡，在选取广播节点时，本算法首先考虑传感器节点的剩余能量，具体原则如下：

其中，B（i）为第i个传感器节点的剩余能量；n为整个网络的传感器节点数；β为可调参数；β∈（0，1］，β越小，对传感器节点的剩余能量要求越高。重编程完成后，全网节点的能量趋于均衡。

在根据需求设置了合适的β值后，本算法根据（15）式筛选被覆盖的所有传感器节点，根据（14）式计算出每个传感器节点对应的Ei值。选取最小的Ei值所对应的传感器节点作为一个广播节点。

3.4 算法实现

本文提出的算法由监控中心运行，其具体实现可以分为6个步骤。

（1）部署传感器节点。在一个N×N的区域内，随机生成m个点，即生成一个m×2的矩阵，第1列为传感器节点的X轴坐标，第2列为传感器节点的Y轴坐标。

（2）初始化传感器节点的覆盖情况。生成一个1×m的矩阵，即传感器节点覆盖矩阵，第1个元素为1，其余元素全部为0。以1表示已被覆盖（重编程），0表示未被覆盖。

（3）计算传感器节点之间的距离。根据传感器节点的坐标矩阵，计算出每个传感器节点与其他传感器节点距离，即生成一个m×m的距离矩阵。

（4）选取最佳传输半径。初始广播节点根据（14）式从可选传输半径集合中选出最佳传输半径，在完成第1次覆盖后，更新传感器节点覆盖矩阵，并记录本次广播节点的坐标、最佳传输半径以及所有被覆盖的传感器节点的坐标。

（5）选择下一个广播节点。根据传感器节点的覆盖矩阵与（14）式、（15）式，选择下一个广播节点及其最佳传输半径，完成覆盖后更新传感器节点覆盖矩阵，并记录本次广播节点的坐标、最佳传输半径以及所有被覆盖的传感器节点的坐标。

（6）生成传播路径树。按照上述原则依次执行，直到传感器节点覆盖矩阵中的元素全部为1，即所有传感器节点都被覆盖。根据每次覆盖后记录的信息，生成重编程代码的传播路径树。

伪代码如下：

4 仿真结果与分析

仿真时仅考虑传感器节点的无线通信能耗，不考虑无线传感网络路由建立和维护时的能耗以及数据碰撞、超时重发所消耗的能量。本算法是一种由监控中心运行的集中式算法，也不考虑计算能耗，仿真参数如下：收发数据时电子能耗为50nJ／bit；放 大 数 据 信 号 消 耗 能 量εfs为100pJ／（bit·m－2）；放大因子α为2；节点通信半径dmax为150m；网络区域为400m×400m；节点初始能量E为1 000J；可调因子β为0.25；重编程代码的数据量k为1Mb。

为便于数据处理，采用Matlab仿真时在一个100×100的坐标区域内进行，采用随机函数生成n个节点，并把第1个节点设为初始广播节点。分别运行MNP算法与本算法，生成传播路径树如图1所示。MNP算法以固定传输半径50进行覆盖，而本算法根据节点分布状况动态调整传输半径，从30、40与50中选择一个最优传输半径进行覆盖。

以MNP算法进行重编程，各个节点的能耗如图2a所示，采用本文算法时各个节点的能耗分布情况如图2b所示。由图2可以看出，MNP算法没有考虑剩余电池能量问题，网络中间位置的节点会过早地消耗掉自己的能量，从而降低整个网络的寿命。

图1 运行不同算法生成的传播路径树

图2 不同算法中各个节点的能耗

在仿真区域内随机分布不同数量节点的情况下，运行MNP算法和本文算法所消耗总能量的折线图如图3所示，显而易见，本算法消耗的总能量始终较少。

图3 不同节点数目下2种算法的总能耗

5 结束语

本文提出一种基于动态传输功率的重编程能量均衡算法，该算法应用于当前拓扑网络和节点剩余能量已知情况下的无线传感网，在保证能量利用效率的同时，兼顾节点的剩余能量，避免剩余能量较低的节点被选作代码分发节点，造成节点能量过早耗尽。在Matlab中对MNP算法与本算法进行仿真，结果表明，该算法消耗的总能量始终比MNP算法少，且整个网络能量更均衡。

.

［1］ 刘士兴，孟召晶，石 波，等.基于嵌入式Linux的无线传感器网络汇聚节点［J］.合肥工业大学学报：自然科学版，2012，35（4）：499－502.

［2］ Mazumder B，Hallstrom J O.An efficient code update solution for wireless sensor network reprogramming［C］／／Proceedings of the Eleventh ACM International Conference on Embedded Software.IEEE Press，2013：1－4.

［3］ He Daojing，Chen Chun，Chan S，et al.SDRP：a secure and distributed reprogramming protocol for wireless sensor networks［J］.IEEE Transactions on Industrial Electronics，2012，59（11）：4155－4163.

［4］ Jeong J，Kim S，Broad A.Network reprogramming［EB／OL］.［2013－08－12］.http／／：www.tinyos.net／dist－1.1.0／snapshot－1.1.3Dec2003cvs／doc／NetworkRe programming.pdf.

［5］ Kallitsis M G，Ning P.Vulnerabilities of the deluge data dissemination protocol［EB／OL］.［2013－12－30］.http／／：www.yellowdocuments.com.

［6］ Hui J W，Culler D.The dynamic behavior of a data dissemination protocol for network programming at scale［C］／／Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.ACM，2004：81－94.

［7］ Bin Shafi N，Ali K，Hassanein H S.No－reboot and zero－flash over－the－air programming for wireless sensor networks［C］／／Sensor，Mesh and Ad Hoc Communications and Networks（SECON），2012 9th Annual IEEE Communications Society Conference on.IEEE，2012：371－379.

［8］ Kulkarni S，Wang L.Energy－efficient multihop reprogramming for sensor networks［J］.ACM Transactions on Sensor Networks，2009，5（2）：1－16.

［9］ Anastasi G，Conti M，Di Francesco M，et al.Energy conservation in wireless sensor networks：a survey［J］.Ad Hoc Networks，2009，7（3）：537－568.

［10］ 路 由，陈友荣，俞 立，等.基于蚁群的无线传感网最大化生 存 时 间 路 由 ［J］.计 算 机 应 用，2011，31（11）：2898－2901.