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

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

2、ntrol 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

3、 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 clust

4、er, and at the st age of data tran smissi on, determines the transmission way according to the critical conditions. the algorithm is proved that it makes the network clumps situation more balaneed, the average power consumption of node is less ， more reasonable, and network life time is longer.关键词：能

5、量有效；多跳；无线传感器网络；拓扑控 制；仿真key words： energy efficient； multihop； wireless sensor network (wsn)； topology control； simulation 中图分类号:tp39文献标识码：a文章编号:1006-4311 (2013) 03-0186-030引言无线传感器网络集成了传感器技术、嵌入式系统技术、 微机电系统技术、分布式信息处理技术以及无线通信技术， 有着不可估量的应用前景。无线传感器网络采用的传感器体 积小、能量少、节点部署环境较差1。对于能量受限的无 线传感器网络来说，在确保网络应用的前提下节

6、约能量消耗 是一个关键问题。通过拓扑控制技术生成优化的拓扑结构可 以实现节约能源消耗。1 leach算法的特点leach算法自适应性好，容错性高，并且能够有效的延 长网络的寿命2。但是这种算法也存在着自身的缺点： 簇首节点分布不合理。由于簇首产生的随机性会导致 整个网络分簇不均匀，致使部分簇首相距基站远近不一，从 加重某些簇首节点的负担，降低网络负载平衡度。 簇内节点分布不均匀。因为是随机性的产生簇首，所 以就可能造成簇首负担的节点不均衡，网络拓扑结构分布不 均匀使得簇首节点消耗能耗不一，造成网络能量负载不平 衡，减少了网络生存时间。 簇首选举中没有考虑节点的剩余能量，剩余能量少的 节点一旦当

7、选为簇首，会导致该簇失效，甚至网络瘫痪。 簇内节点hj直接把数据传输给簇首节点chi,当两者 之间的距离较远时，会加重簇内节点的能源消耗以及簇首节 点的能源消耗。2系统模型本文采用文献3中的无线通信能量消耗模型，节点发 送1 bit的数据所消耗的能量为etx (1, d),由发射电路损 耗和功率放大损耗两部分组成，即公式(1)所示：etx ( 1 , d )二etx-elec ( 1 ) +etxmp ( 1 , d ) =lxeelec+lx e xdb (1)eelec表示发射电路和接收电路损耗的能量消耗，在该 模型中两者取相同值，能量消耗值与消息长度1成正比。功 率放大时的能量消耗与发射

8、节点和接收节点之间的传输距 离d有关。根据传输距离d与给定阈值do之间的关系，发 送节点选择不同的能量衰减模型计算发送数据所消耗的能 量，即当传输距离小于do时，采用自由空间模型，发送数 据的能量消耗与距离的平方成正比关系；否则采用多路径衰 减模型，与距离的四次方成正比关系，如公式(2)所示：e (1 , d )=1 e+ £ 1 ，d <dll e+ £ 1 (!, d?叟(! (2)其中£、£ 分别表示这两种模型功率放大所消耗的 能量，d=4 n hrht/入，ht和hr分别表示发射装置和接收 装置的天线长度，x表示标志信号波长。接收装置每接收

9、1 bit数据的能量消耗为：erx (1, d)二erx-elec (1) =1 eelec (3)3leach-eam算法的实现leach-eam算法采用leach算法中轮次转换的方法，把 每轮循环分为簇的建立阶段和稳定的数据通信阶段，如图1 所示。3. 1簇的建立阶段簇的建立阶段由簇首确定和簇的形 成两个阶段组成。3. 1. 1簇首确定在簇首选举上，算法采用基于节点密 度争先的簇首选举以及允许已经充当过簇首的节点继续参 加选举的方法。同时，引入节点当选簇首次数限制f (i)和 能量限制et (i)两个指标，避免节点频繁当选簇首或者剩 余能量少节点当选簇首，造成节点加快死忙的问题。簇首选举时

10、节点生成介于0t的随机数a,用a与簇首 选举阀值t (ni)进行比较(t (ni)由公式(4)定义)，a 比t (ni)小就具备当选簇首的先决条件。t (ni)二x1-d(ni), nieg (4)在公式中：p是一个0-1间的实数，为网络中每轮节点 成为簇首占所有节点的比例；r是当前轮数；g是在前r-1 轮内未死忙节点集合，d (ni)是节点密集度参数(由公式 (5)定义)。d (ni) =(5)nd (i)为节点i的存活邻居节点数。公式(5)由leach算法公式修改而来，它与leach算 法不同的是：(1) leach算法中禁止当选过簇首的节点再次 参选，会从另一方面造成簇首节点分布在网络边

11、缘，网络分 簇不均匀，所以本算法的簇首选举阀值把限制当选过簇首的 限制条件去掉，允许节点多次单选簇首；(2)增加密度集参 数，由1-d2 (ni)可以看出，随着节点周围存活的节点数越 多，1-d2 (ni)的值也就越大，节点当选簇首的概率也就会 越高，节点周围存活的节点数越少，节点当选簇首的概率也 就会越低。而且每个节点密度集也会随着时间的变化而发生 改变。算法在簇首选举的过程中还要衡量节点当选簇首次数 限制f (i)和能量限制et (i)两个指标，定义以下变量c(i) , ei, eavro c (i)是节点在生命期内中当选簇首节点 的统计次数，由节点通过累加得到，ei为节点剩余能量，由 节

12、点自己能量消耗情况得出，eavr为全网存活节点的平均剩 余能量，由sink节点返回得出。其中f (i) =(6)et (i) =(7)r为系统设定的最大选举轮数，参数p为系统设定的 最优簇首比例。节点只有在指标f (i), et (i)都比实数1 小的时候才具备当选簇首的前提条件。通过指标f (i)可以 保证节点当选簇首的次数控制在一定的范围内，避免节点过 早死忙。通过能量限制et (i)保证当选簇首的节点剩余能 量必须比全网存活节点的剩余能量大，避免剩余能量较少的 节点担任簇首。在簇首选举的过程中从节点密度集、节点当选簇首次数 限制和能量限制等三个方面对leach算法进行改进，簇首的 选举不

13、再是单个节点的事情，而是周围节点的联合考虑。簇 首选举流程图如图2所示。3. 1. 2簇的形成一个节点成为候选簇首节点后，就向 其邻居r范围内广播成为获胜簇首的消息，该消息包括节点 的id,剩余能量ei和坐标，等待节点的加入。非候选簇首 节点收到簇首的广播消息后，则计算与每个候选簇首之间能 量距离综合权值参数wji (wji由公式(8)给出)，选择wji 值大的簇首加入，如果存在与多个候选簇首节点的wji值相 等，则选择距离短的簇首加入，并向该簇首发回确认消息， 确认消息包含节点的id,剩余能量ei和坐标4。w二/(! (j, i)(8)其中e为非簇首节点的剩余能量，d (j, i)为非簇首

14、节点hj与簇首chi之间的距离。节点在簇首选举时间内如果没有收到来自候选簇首的 消息，则该节点宣布成为簇首，并向其邻居r范围内广播当 选簇首的消息，该消息包括节点的id,剩余能量ei和自身 的地理位置，等待节点的加入，只有与该节点相同的没有收 到获胜簇首消息的节点才需要对这条消息响应，通过前面的 能量距离综合权值参数wji方法选出剩余的簇首。3.2稳定的数据通信阶段leach-eam算法在稳定的数 据通信阶段簇内数据传输采用多跳和单跳结合的方法。 leach-eam需要根据当前条件是否满足临界条件来决定簇内 节点进行多跳或者多跳的数据传输。3. 2. 1临界条件临界条件的确定参考文献5得出，在

15、 文献中通过参数(2(公式(9)确定临界条件。q为每个簇平均所占的面积。簇所覆盖面积大小决定 了该分簇是采用多跳或者单跳的传输方式。当簇所占的面积 满足大于q时，采用多跳的传输方式，反之则采用单跳。3.2.2多跳的实现方法在实现多跳的数据传输过程 中，簇首chi先根据簇内成员节点的位置信息，采用最短路 径算法dijkstra计算连接边的权重意义上的最短路径得到 chi出发到所有簇内节点的路由路径树。根据公式(2)可计 算连接边的权重eelec+ £ friss-ampd2,因为簇结构中传输 距离较短的特性，所以衰减因子选择2。当最短路径计算完 毕后，簇首chi将路径树打包成消息广播给

16、簇内节点5。 簇内节点hj接收到路径消息后，可从消息中得出自己的上 一跳集合和下一跳集合。4算法仿真4.1仿真系统配置仿真系统配置如下：传感器网络布 置区域为100mx 100m，随机分布的节点数为100个，基站位 置固定在坐标(50, 50)处，节点的传输距离为10m50m, 节点初始能量为2j,节点接收和发送电路消耗的能量eelec 为50nj/bit,信号放大器的放大倍数为0. 0013pj/bit/m4, 增量为2, eda为0. 009j/bit/signal,节点充当簇首时 间为 100s 6 o4.2性能分析为了评价算法对网络性能的影响，为了 更好地衡量网络寿命、能量利用率和簇规

17、模等几个指标，本 仿真实验中测定了四个指标，分别为：簇规模、网络寿命、 簇内节点分布、平均功耗。 4. 2. 1簇规模簇规模指标 用来评价各簇节点数的平衡度。为比较leach-eam算法在平 衡各簇规模的作用，随机抽取了算法在运行过程中的分簇， 如图3所示。可以看出leach-eam结合节点剩余能量和节点 密度选择簇首，相比leach算法和dbpc算法簇首节点分布 比较均匀，而且都分别位于各簇的中央地带，较好地避免了 簇首节点聚集或处于网络边缘的问题。4. 2.2不同簇首比例网络寿命图4为簇首比例p分别 取0.04、0.05、0.1时，四种算法对网络寿命的影响。可以 看出在3种不同簇首比例p下

18、，因为leach-eam算法在簇 首选举阶段引入能量限制指标，避免剩余能量少节点当选簇 首，在簇的形成阶段，非簇首节点计算与每个候选簇首之间 能量、距离综合权值，并加入选择综合权值大的簇，簇内节 点采用多跳与单跳相结合的方式进行数据传输，所以网络寿 命最长，0bcp次之，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算法。 通过簇首的确定、簇的形成两个阶段，簇内数据传输方式实 现了改进算法，具备网络分簇情况均衡，节点的平均功耗少; 网络的生存时间长的特点。参考文