基于能量有效和多跳的层次型拓扑控制算法

谭军 等

摘要： 拓扑控制是无线传感器网络技术中的一个重要研究方向，良好的拓扑控制机制能够提高路由协议和MAC协议的效率，为数据融合、时间同步和目标定位等很多方面提供基础。本文在提出一种基于能量有效和多跳的层次型拓扑控制算法。算法在簇首选择阶段综合考虑节点剩余能量、节点密度、节点间距离，在非簇首节点加入簇阶段综合考虑节点间剩余能量及距离，数据传输阶段根据临界条件来决定簇内数据传输采用多跳或者单跳的数据传输的机制。通过仿真软件验证发现算法使得网络分簇情况更加均衡，节点的平均功耗更少，更合理，网络的生存时间更长。

Abstract： Topology control is an important research direction of wireless sensor network technology， the good topology control mechanism can improve the efficiency of the routing protocol and MAC protocol， and provide basis for data fusion， time synchronization， and target location. The paper puts forward a hierarchical topology control algorithm based on energy efficient and multihop. The Algorithm overall considers the node residual energy， node density， and distance between nodes in cluster head selection， and considers the node residual energy and distance between nodes when non-cluster head node joining cluster， and at the stage of data transmission， determines the transmission way according to the critical conditions. The algorithm is proved that it makes the network clumps situation more balanced， the average power consumption of node is less， more reasonable， and network life time is longer.

关键词： 能量有效；多跳；无线传感器网络；拓扑控制；仿真

Key words： energy efficient；multihop；wireless sensor network （WSN）；topology control；simulation

中图分类号：TP39 文献标识码：A 文章编号：1006-4311（2013）03-0186-03

0 引言

无线传感器网络集成了传感器技术、嵌入式系统技术、微机电系统技术、分布式信息处理技术以及无线通信技术，有着不可估量的应用前景。无线传感器网络采用的传感器体积小、能量少、节点部署环境较差[1]。对于能量受限的无线传感器网络来说，在确保网络应用的前提下节约能量消耗是一个关键问题。通过拓扑控制技术生成优化的拓扑结构可以实现节约能源消耗。

1 LEACH算法的特点

LEACH算法自适应性好，容错性高，并且能够有效的延长网络的寿命[2]。但是这种算法也存在着自身的缺点：

①簇首节点分布不合理。由于簇首产生的随机性会导致整个网络分簇不均匀，致使部分簇首相距基站远近不一，从加重某些簇首节点的负担，降低网络负载平衡度。

②簇内节点分布不均匀。因为是随机性的产生簇首，所以就可能造成簇首负担的节点不均衡，网络拓扑结构分布不均匀使得簇首节点消耗能耗不一，造成网络能量负载不平衡，减少了网络生存时间。

③簇首选举中没有考虑节点的剩余能量，剩余能量少的节点一旦当选为簇首，会导致该簇失效，甚至网络瘫痪。

④簇内节点Hj直接把数据传输给簇首节点CHi，当两者之间的距离较远时，会加重簇内节点的能源消耗以及簇首节点的能源消耗。

2 系统模型

本文采用文献[3]中的无线通信能量消耗模型，节点发送l bit的数据所消耗的能量为ETx（l，d），由发射电路损耗和功率放大损耗两部分组成，即公式（1）所示：

ETx（l，d）=ETx-elec（l）+ETx-mp（l，d）=l×Eelec+l×ε×dβ （1）

Eelec表示发射电路和接收电路损耗的能量消耗，在该模型中两者取相同值，能量消耗值与消息长度l成正比。功率放大时的能量消耗与发射节点和接收节点之间的传输距离d有关。根据传输距离d与给定阈值d0之间的关系，发送节点选择不同的能量衰减模型计算发送数据所消耗的能量，即当传输距离小于d0时，采用自由空间模型，发送数据的能量消耗与距离的平方成正比关系；否则采用多路径衰减模型，与距离的四次方成正比关系，如公式（2）所示：

E■（l，d）=l·E■+ε■·l·d■，d＜d■l·E■+ε■·l·d■，d？叟d■（2）

其中ε■、ε■分别表示这两种模型功率放大所消耗的能量，d■=4πhrht/λ，ht和hr分别表示发射装置和接收装置的天线长度，λ表示标志信号波长。

接收装置每接收l bit数据的能量消耗为：

ERx（l，d）=ERx-elec（l）=l·Eelec （3）

3 LEACH-EAM算法的实现

LEACH-EAM算法采用LEACH算法中轮次转换的方法，把每轮循环分为簇的建立阶段和稳定的数据通信阶段，如图1所示。

3.1 簇的建立阶段 簇的建立阶段由簇首确定和簇的形成两个阶段组成。

3.1.1 簇首确定 在簇首选举上，算法采用基于节点密度争先的簇首选举以及允许已经充当过簇首的节点继续参加选举的方法。同时，引入节点当选簇首次数限制F（i）和能量限制Et（i）两个指标，避免节点频繁当选簇首或者剩余能量少节点当选簇首，造成节点加快死忙的问题。

簇首选举时节点生成介于0-1的随机数a，用a与簇首选举阀值T（Ni）进行比较（T（Ni）由公式（4）定义），a比T（Ni）小就具备当选簇首的先决条件。

T（Ni）=■×1-D■（Ni），Ni∈G （4）

在公式中：P是一个0-1间的实数，为网络中每轮节点成为簇首占所有节点的比例；r是当前轮数；G是在前r-1轮内未死忙节点集合，D（Ni）是节点密集度参数（由公式（5）定义）。

D（Ni）=■ （5）

Nd（i）为节点i的存活邻居节点数。

公式（5）由LEACH算法公式修改而来，它与LEACH算法不同的是：（1） LEACH算法中禁止当选过簇首的节点再次参选，会从另一方面造成簇首节点分布在网络边缘，网络分簇不均匀，所以本算法的簇首选举阀值把限制当选过簇首的限制条件去掉，允许节点多次单选簇首；（2）增加密度集参数，由1-D2（Ni）可以看出，随着节点周围存活的节点数越多，1-D2（Ni）的值也就越大，节点当选簇首的概率也就会越高，节点周围存活的节点数越少，节点当选簇首的概率也就会越低。而且每个节点密度集也会随着时间的变化而发生改变。

算法在簇首选举的过程中还要衡量节点当选簇首次数限制F（i）和能量限制Et（i）两个指标，定义以下变量C（i），ei，Eavr。C（i）是节点在生命期内中当选簇首节点的统计次数，由节点通过累加得到，ei为节点剩余能量，由节点自己能量消耗情况得出，Eavr为全网存活节点的平均剩余能量，由Sink节点返回得出。其中

F（i）=■ （6）

Et（i）=■ （7）

R■为系统设定的最大选举轮数，参数P为系统设定的最优簇首比例。节点只有在指标F（i），Et（i）都比实数1小的时候才具备当选簇首的前提条件。通过指标F（i）可以保证节点当选簇首的次数控制在一定的范围内，避免节点过早死忙。通过能量限制Et（i）保证当选簇首的节点剩余能量必须比全网存活节点的剩余能量大，避免剩余能量较少的节点担任簇首。

在簇首选举的过程中从节点密度集、节点当选簇首次数限制和能量限制等三个方面对LEACH算法进行改进，簇首的选举不再是单个节点的事情，而是周围节点的联合考虑。簇首选举流程图如图2所示。

3.1.2 簇的形成 一个节点成为候选簇首节点后，就向其邻居R范围内广播成为获胜簇首的消息，该消息包括节点的ID，剩余能量ei和坐标，等待节点的加入。非候选簇首节点收到簇首的广播消息后，则计算与每个候选簇首之间能量距离综合权值参数wji（wji由公式（8）给出），选择wji值大的簇首加入，如果存在与多个候选簇首节点的wji值相等，则选择距离短的簇首加入，并向该簇首发回确认消息，确认消息包含节点的ID，剩余能量ei和坐标[4]。

w■=■/d（j，i） （8）

其中e■为非簇首节点的剩余能量，d（j，i）为非簇首节点Hj与簇首CHi之间的距离。

节点在簇首选举时间内如果没有收到来自候选簇首的消息，则该节点宣布成为簇首，并向其邻居R范围内广播当选簇首的消息，该消息包括节点的ID，剩余能量ei和自身的地理位置，等待节点的加入，只有与该节点相同的没有收到获胜簇首消息的节点才需要对这条消息响应，通过前面的能量距离综合权值参数wji方法选出剩余的簇首。

3.2 稳定的数据通信阶段 LEACH-EAM算法在稳定的数据通信阶段簇内数据传输采用多跳和单跳结合的方法。LEACH-EAM需要根据当前条件是否满足临界条件来决定簇内节点进行多跳或者多跳的数据传输。

3.2.1 临界条件 临界条件的确定参考文献[5]得出，在文献中通过参数Q■（公式（9））确定临界条件。

Q■=■ （9）

Q■为每个簇平均所占的面积。簇所覆盖面积大小决定了该分簇是采用多跳或者单跳的传输方式。当簇所占的面积满足大于Q■时，采用多跳的传输方式，反之则采用单跳。

3.2.2 多跳的实现方法 在实现多跳的数据传输过程中，簇首CHi先根据簇内成员节点的位置信息，采用最短路径算法Dijkstra计算连接边的权重意义上的最短路径得到CHi出发到所有簇内节点的路由路径树。根据公式（2）可计算连接边的权重Eelec+εfriss-ampd2，因为簇结构中传输距离较短的特性，所以衰减因子选择2。当最短路径计算完毕后，簇首CHi将路径树打包成消息广播给簇内节点[5]。簇内节点Hj接收到路径消息后，可从消息中得出自己的上一跳集合和下一跳集合。

4 算法仿真

4.1 仿真系统配置 仿真系统配置如下：传感器网络布置区域为100m×100m，随机分布的节点数为100个，基站位置固定在坐标（50，50）处，节点的传输距离为10m—50m，节点初始能量为2J，节点接收和发送电路消耗的能量Eelec为50Nj/bit，信号放大器的放大倍数为0.0013pJ/bit/m4，增量Δ为2，EDA为0.009J/bit/signal，节点充当簇首时间为100s[6]。

4.2 性能分析 为了评价算法对网络性能的影响，为了更好地衡量网络寿命、能量利用率和簇规模等几个指标，本仿真实验中测定了四个指标，分别为：簇规模、网络寿命、簇内节点分布、平均功耗。

4.2.1 簇规模 簇规模指标用来评价各簇节点数的平衡度。为比较LEACH-EAM算法在平衡各簇规模的作用，随机抽取了算法在运行过程中的分簇，如图3所示。可以看出LEACH-EAM结合节点剩余能量和节点密度选择簇首，相比LEACH算法和DBPC算法簇首节点分布比较均匀，而且都分别位于各簇的中央地带，较好地避免了簇首节点聚集或处于网络边缘的问题。

4.2.2 不同簇首比例网络寿命 图4为簇首比例P分别取0.04、0.05、0.1时，四种算法对网络寿命的影响。可以看出在3种不同簇首比例P下，因为LEACH—EAM算法在簇首选举阶段引入能量限制指标，避免剩余能量少节点当选簇首，在簇的形成阶段，非簇首节点计算与每个候选簇首之间能量、距离综合权值，并加入选择综合权值大的簇，簇内节点采用多跳与单跳相结合的方式进行数据传输，所以网络寿命最长，OBCP次之，LEACH的网络寿命最短。而且当P=0.04时，LEACH-EAM的网络存活时间最长。

4.2.3 簇内节点分布 簇内节点分布性能指标反映网络分簇情况是否均衡。如图5所示，可以看出LEACH-EAM各簇包含的节点数相对于LEACH、DBCP更加集中，从而进一步证明通过结合节点密度选举簇首可以更有效平衡各个簇的规模。

4.2.4 不同网络直径下的网络寿命、节点平均功耗 图6和图7分别表示在不同网络直径下的网络寿命和节点平均功耗的对比情况。从图中可以看出，随着网络直径的增加，簇内通信距离增大，造成簇内消耗的能量也增大， LEACH-EAM相对LEACH算法、DBCP算法节点平均功耗是最少，网络寿命最长。

5 结束语

本文LEACH算法进行深入研究，提出了LEACH-EMA算法。通过簇首的确定、簇的形成两个阶段，簇内数据传输方式实现了改进算法，具备网络分簇情况均衡，节点的平均功耗少；网络的生存时间长的特点。

参考文献：

[1]孙利民，李建中，陈渝等.无线传感器[C].网络清华大学出版社，2005．5，89．107.

[2]乔俊峰，刘三阳，曹祥宇.无线传感器网络中基于节点密度的簇算法[J].计算机科学，2009，36（12）：46-49.

[3]Heinzelman W， Chandrakasan A， Balakrishnan H. Energy-efficient communication protocol for wireless micro-sensor networks[C]. Proceedings of t he 33rd Annual Hawaii International Conference on System Sciences， Maui， 2007.3005-30l4.

[4]郝晓辰，翟明，刘彬，张增仁.负载均衡的无线传感器网络拓扑控制算法[J].计算机工程，2009，35（05）：84-86.

[5]汤强.无线传感器网络层次拓扑控制算法研究.华中科技大学博士学位论文.2010.6.1.

[6]Younis O， Fahmy S. Heed： A Hybrid， Energy-efficient， Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2004，3（4）： 660-669.