探索能量最优化的传感网络路由算法及部署方案

崔宇等

摘 要：传感器在区域内对数据的采集、传递都需要消耗大量的能量，而传感网络的寿命长短传感器的能量又取决于传感器的能量是否耗尽，某项目中，当传感网络中20%的传感器能量耗尽时，该传感网络就失去作用，根据传感器能量消耗公式，在传感器传递数据包时将数据传输均分到整个网络中便可以将能量的损耗平均到每个传感器中，相比较于仅将数据包通过一个传感器传至基站的情况，该方法不仅大大提高了传递效率并且大大延长了传感网络的寿命。基于路由算法的思想，对于区域内所有传感器的排布情况，首先考虑对网络进行按“跳数”（数据传递至基站的传递次数）进行划分，将有相同跳数的传感器作为一层；分层后，通过经典的LEACH算法，在每轮中选取出各层中的簇头进行数据传递，提高了数据传递的效率，并且在每轮中担任簇头的节点在下轮中不会担任簇头，因此也使得能量的损耗均匀到各层的每个节点中，不会出现数据集中在某个节点的情况，延长了传感网络的寿命。根据以往所做的三种（矩形，蜂窝1，蜂窝2）排布情况，文章利用设计的算法对三种情况进行仿真，检验出三种排布方式中较优的一种。

关键词：传感网络部署；能量优化；LEACH算法；分层路由算法

中图分类号：TP212.9 文献标识码：A 文章编号：1006-8937（2013）17-0005-03

随着信息技术的飞速发展，信息网络对于信息的传输显得日益重要，现今很多研究者针对于定向传感器、全向传感器的覆盖问题已经做了大量的研究，但相对于传感网络能量方面的研究并不是很多，所以现在越来越多的研究关注于传感网络的能量问题。

在传感器采集、传递数据和接收其它传感器所传递的数据包时都对传感器的能量有一定的损耗，当某传感器的能量消耗尽时便无法采集及传输数据，某项目中，当整个传感网络中20%的传感器能量耗尽时，该片区域内的传感网络便无法正常工作，可认为项目终结，因此，在合理排布传感器位置的基础上，如何延长传感网络的使用寿命是本文所研究的关键问题。

1 假 设

基站位于左边界上端，r为通信距离，传感器相同且有一样的初始能量，通信信号稳定，按蜂窝式分布。

2 模型、算法及符号说明

2.1 传感器能量消耗

通过查阅相关文献及资料，传感器节点的剩余能量Energy可以表示为：

Energy=e0-e1t-e2m

其中，e0为初始能量，er为单次采集能耗，ep为节点传输能耗，t为时间，m为数据包总数。

2.2 网络寿命

①当节点耗尽能量（Energy变为负数）后，该节点无法继续采集或传输数据。定义项目的生存周期为传感网络从开始运行到超过20%节点耗尽能量所经历的时间。

②显然距离基站最近的一层，即第一层，由于转发数据包的数量是最大的，所以节点损耗的能量也是最大的一层。若第一层的能量消耗完全的时候，网络就无法传输数据包。

2.3 路由算法

路由算法是提高路由协议功能，尽量减少路由时所带来开销的算法。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由器使用路由算法来找到到达目的地的最佳路由。当说“最佳路由”时，考虑的参数包括诸如跳跃数（分组数据包在网络中从一个路由器或中间节点到另外的节点的行程）、延時以及分组数据包传输通信耗时。

对于本文来说，在基于某区域传感器排布位置已知的情况下，我们考虑对该片区域内的传感网络进行分层然后在层与层之间的数据传递（能量消耗）方面进行优化，在提高数据传递效率的同时也延长了传感网络的寿命，算法具体流程如图1所示。

2.4 LEACH算法及改进

LEACH（Low2Energy Adaptive ClusteringHierarchy）算法是由MIT的Heinzelman等人提出的一种低功耗自适应分簇算法。其基本思想是以循环的方式随机选择簇头节点，将整个网络的能量负载均匀分配到网络中的每个传感器节点，从而达到降低网络能耗，提高网络生存周期的目的。

LEACH算法在执行过程被分为一个个小的轮，而在每轮中又分为建立阶段和稳定阶段。

2.4.1 建立阶段

一个节点在新的一轮中能否成为簇头节点取决于两个因素，一是网络中假定的簇头节点所占的百分比，二是最近1/p轮中是否成为过簇头节点。在新的一轮中，节点通过由自身产生的随机数与阈值进行比较，小于阈值则成为簇头节点：

阈值T（n）为：

节点在成为簇头节点之后，设置已成为簇头节点的标志，即设置自己不属于最近1/p轮中没有当选簇头节点的节点集合，则相应的阈值T（n）将为0。

簇头产生后，将自己的信息进行广播，没有成为簇头的节点根据收到广播信号的强弱可以选择是否加入该簇头，簇头节点则根据收到的所有的加入信息，生成一个为本簇内的节点分配发送信息的TDMA时隙信息，为本簇内的节点分配发送信息的时隙，并发送广播信息给本簇内所有节点。簇头的选择随机进行，所有节点轮流担当簇头，可避免簇头节点能耗太大。

2.4.2 稳定阶段

在该阶段中，如图2所示，簇成员节点先将感知到信息经处理后在自己的TDMA时隙内发送给簇头节点，簇头节点在收到本簇内所有节点发送过来的数据之后，对接收的数据进行融合和压缩，并监听信道，空闲时将融合压缩后的数据发送给Sink节点。

2.5 改进LEACH算法

3 算法仿真及实验结果

本文针对于某一矩形区域（200×100 m2）内三种不同的传感器位置分布方式对上述算法进行检验，确定排布方式中网络寿命较长的一个，矩阵排布如图3及表1所示，蜂窝排布1如图4及表2所示，蜂窝排布2如图5及表3所示。

4 结 论

通过对该算法对实际排布中的仿真测试，可以看出该算法可以将传感网络的能量较平均地分到每一层中，而对于每一层中的节点能耗方面，也尽可能的避免单一节点的能量大量消耗，使得每一层消耗的能量均匀分到每一个节点上，从而大大延长了该传感网络的寿命。但对于靠近数据中心的传感器的能量消耗依然比较大，因此在实际应用过程中可以考虑在靠近数据中心排布时增加备用节点以更好地延长网络寿命。

参考文献：

[1] 陈光亭，裘哲勇数学建模[M].北京：高等教育出版社，2010.

[2] 田铁红，程赓，毛松，等.面向环境保护的物联网发展探讨[J].信息通信技术，2010，（5）.

[3] 杨云，田浩澄，顾沈君，等.无线传感器网络分层聚类路由算法[J].计算机研究与发展，2011，（S2）.