摘 要: 基于图论中最小生成树的思想对LEACH协议进行了改进,构建了一种降低能耗的Prim分簇算法。其算法采用将普里姆的思想用到分簇中,将能量大或近似大的传感器节点,根据其在网络中的位置,将一条最小距离的边加入树中。通过多跳结构,减少节点在传输数据中的能量消耗,从而延长网络的寿命。对改进的算法经验证表明能有效降低能量消耗,提高网络的生存期。
关键词: 无线传感器网络;动态分簇;Prim算法;能量有效
无线传感器网络(WSN)是较新的研究领域,由于其广阔的应用前景,近年来受到越来越多的关注,各种面向具体应用的WSN路由协议应运而生。WSN通常依赖电池供电,而电池能量有限,因此如何延长网络的生命周期是WSN中十分重要的问题[1]。
1 基于能量有效网络节点动态分簇
1.1 动态分簇基本思想
分簇思想是采用层次型拓扑结构,根据概率随机确定高级节点即簇头节点和普通节点。根据规则确定普通节点子簇归属并建立子簇。簇头负责簇内数据融合并协调簇内节点工作,在簇头间运用Prim算法搜寻簇头节点到汇聚节点的多跳最优路径,采用多跳接力方式将簇头融合数据发送至汇聚节点,以进行数据采集传输或动态分簇及路径寻优,实现无线传感器网络节点能量均衡管理[2]。本算法是将普里姆的思想用到分簇中,将能量大的传感器节点,根据其在网络中的位置,将一条最小距离的边加入树中。通过多跳结构,减少节点在传输数据中的能量消耗,从而延长网络的寿命[3]。
④在循环中选为高级节点的无线发射模块,可根据节点能耗情况和距离远近控制发送功率大小,发送数据的能耗取决于数据大小和传输距离,接收数据的能耗只取决于数据大小。
(3)根据概率随机选取节点作为高级节点,其余节点为普通节点。汇聚节点广播消息并接收各节点的返回数据,让汇聚节点知道网络基本情况。
(4)根据节点位置信息、距离启发因子和簇成员节点数量限制,计算普通节点与相邻簇头节点距离,判定普通节点归属。普通节点与簇节点通信并确认关系,由此子簇建立。
(5)根据汇聚节点广播消息,子簇内各节点的数据传输到簇头,并进行数据融合。根据BWAS算法,搜寻最优路径,将簇头融合后的数据以多跳接力方式传输到汇聚节点。
(6)根据一定规则调整簇头传输功率或簇内根据剩余能量高低选取新的簇头节点等。根据汇聚节点广播要求,循环步骤(2)~步骤(5)到最大迭代次数或死亡节点接近于最初设定值[4]。
2 基于能量有效的动态分簇算法
改进的Prim分簇算法考虑了节点的剩余能量,由于节点内部均有数据采集和数据融合的功能,则从簇首节点采集的数据已经在一定基础上进行优化,然后由簇首传递给数据汇集点。这样在数据汇集点得到的数据基本上均为最优化数据,最后数据汇集点再向基站传输,减少了无效数据的传输,节约了节点的能量[5-6]。
2.1 算法模型化及定义
prim分簇算法是在单层分簇的基础上遵循从底至上的方式继续分簇。假设从第1层到第h层节点被选为簇首的概率分别为p1,p2,p3,p4。以第1层簇首的选择为例,以概率选择出自愿的簇首,在其规定的k1跳范围内发送广播消息,收到广播消息的节点,根据其接收到信号的强度,选择准备要加入的簇首;没有接收到任何广播消息的节点将成为强迫的簇首。在第1层构造簇首的基础上以概率选出第2层的簇首,然后依次进行下去,直到第h层簇首的选出,就完成了多层分簇的体系。
2.2 算法设计思路
(1)簇首的选择,选择簇首节点的个数为5,此5个簇首为算法的一级簇首,二级簇首在选完一级簇首之后,在剩余节点中再进行选择。由于本文选择的节点个数为100个,因而节点数量不大,分为二级即可,在选择完二级节点之后剩余节点为成员节点。
(2)簇首选择完成之后,再根据分簇算法将成员节点分簇。在网络G=(V,E)中的节点均可传送和接收来自其邻居节点的信息。每个节点v都有一个确定的ID(v),能量值越大,此ID值越大。运用普里姆算法的思想选择ID值大且到簇首跳数少的节点就近相连,以减少节点在传输路径上能量的消耗。
(3)重复思路(2)直至所有节点均发送过分簇消息。完成节点分簇,此时完成一轮分簇算法,按照以上步骤重复直至节点能量殆尽。
2.3 算法流程
通过算法的描述如图1所示,节点生成的随机数小于阈值的节点将自动升为簇首并向外发送簇首信息;小于阈值的节点将重新生成随机数,根据产生的随机数和阈值的关系确定为簇首或普通节点,和LEACH算法一样根据自己的节点属性发送簇首信息或加入簇请求。
3 评价与分析
分簇算法采用Matlab仿真工具,设定节点区域大小为[100,100],节点坐标为(100,100),随机生成网络节点数为200。首先要对网中的节点的能量初始化赋值,算出每个节点的ID值,根据算法确定一级簇首(☆)和二级簇首(*),成员节点用点状表示。
初始化节点之后,可以使用Prim算法开始本轮的分簇,如图2所示。分簇之后,得到簇是多跳的,使得离簇首较远的节点通过二级簇首节点传给簇首,使簇首的能量耗损减小。
分簇之后再对分簇前后能量进行比较,其结果如图3所示。从剩余能量看出,所消耗能量与原有能量相差不大。为了明显看出本算法在能量上的优越性,将两种算法结果进行分析,如图4所示。剩余总能量和它们到达能量殆尽时比较可看出,改进后的Prim算法在分簇到700轮时能量耗尽,而LEACH算法在500轮时就已耗尽,这说明改进的分簇算法确实延长了网络的寿命,仿真结果也表明这种方法是可行的。
研究证明WSN分簇的结构存在最优的簇首个数,使网络能耗最优。LEACH协议每轮选举出的簇首个数的均值是最优值k,采用随机方法分析指出簇首个数的均值并不是常数k,而是函数。通过实验表明,基于改进Prim算法较LEACH算法不仅延长了系统生存时间,而且基站能够接收更多的数据,实现了低能量开销的目的。
参考文献
[1] 阎新芳,安娜.无线传感器网络中分级簇的维护和更新算法[J].传感技术学报,2007,14(7):33-35.
[2] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy efficient communication protocol for wireless microsensor networks[C]. in proceeding of the 33rd Hawaii international conference on system sciences. 2000:3005-3014.
[3] 刘俊锋.基于网格的无线传感器网络分簇方法[J].计算机工程与设计,2007(5):55-60.
[4] 张德跃,杨峰,展中华,等.传感器网络的一种能量感知分簇路由算法[J].计算机技术与发展,2007,17(1):42-45.
[5] 刘云璐,柴乔林,赵晋.无线传感器网络方向性分区路由算法[J].计算机应用,2006,26(1):66-70.
[6] BASU P, KHAN N, LITFLE T D C. A Mobility based metrie for clustering in mobile ad hoc networks[C]. Phoenix, AZ, April2001, 413-418.