论文部分内容阅读
摘 要 以分簇技术为基础的路由协议对无线传感器网络扩展性的提升有非常重要的意义,数据在簇首向数据汇据点进行多跳通信传输的过程中,因为同汇聚点距离较近的簇首负荷相对较大,致使能量消耗完毕,从而无法发挥作用,最终出现网络分割的后果。本文主要阐述了相关研究工作及无线传感器网络路由的问题描述,对基于非均匀分簇的路由机制、EEUC进行分析,并进行实验分析和总结,以期延长网络存活时间,平衡簇首能量消耗问题。
关键词 非均匀分簇;无线传感器网络;能量消耗
中图分类号:TP393 文献标识码:A 文章编号:1671-7597(2015)03-0050-02
传感器网络本质上可看作是一种无线网络,是在一定的观测环境下,以无线通信的途径将分布的各个微型传感器节点进行整合而成的。传感器节点能量的高效利用是网络协议的核心设计任务,从而使网络存活时间进一步延长。通过对建立在能量高效的非均匀分簇算法基础上的基于非均匀分簇的传感器网络路由协议研究,加深人们对非均匀分簇算法的认识,为相关研究提供参考意见。
1 传感器网络的分簇协议相关研究工作
在传感器网络分簇协议方面,众多学者已经展开了大量的研究,取得了一定的研究成果。其中,Lindsey等学者在研究中论述了PEGASIS算法,要求掌握各个节点对应的位置信息,并通过链状的方式将节点联系起来,链状传输数据的过程中还具备一定的处理功能,完成向汇聚点传输数据的任务[1]。就研究内容来看,在簇成员节点间能量消耗平衡方面的研究非常多,但缺乏对平衡簇首间能量消耗问题的研究。传感器网络多跳路由的“热区”问题是由Soro等学者首次提出的,在其研究过程中开创了非均匀簇这一解决方式的范例,为专业人士的深层次研究指明了方向[2]。
从应用场景的角度来看,移动自组网络同传感器网络大不相同,后者需要优化的路由协议的支持。定向扩散路由协议在Intanagonwiwat等研制下,使得路由机制具备查询功能,查询消息由汇聚点发出后,沿逆向梯度对数据进行传输[3]。
2 基于非均匀分簇的无线传感器网络路由的问题描述
2.1 网络模型
选取网络中传感器节点总数为N,随机部署在周期性数据收集场景中,第i个节点通过si体现,则节点集合可表示为{s1,s2…sN}=S,其中N=|S|。
若:1)在观测区域A(方形)外中存在数据汇聚点,确定汇聚点DS、传感器节点的位置后不能进行改变;2)各个节点具有相应的ID,节点构造均相同,可以对数据进行整合处理;3)链路具有对称性,接收信号的发射功率已知的情况下,节点依据强度RSSI计算自身同发射点的大致间距。
在通过无线通信能量消耗模型进行分析时,节点向间距为d处发送l比特数据,功率放大损耗、发射电路损耗(Eelec)之和为总能量消耗。表示如下:
lEelec+lEfsd2, d ETx(l,d)= (1)
lEelec+lEmpd4, dEdo
假设传输距离≥d。,利用多路径衰减模型表示功率放大损耗,需要的功率放大能量为Emp;而传输距离在阈值d。以内时,利用自由空间模型表示,需要的功率放大能量为Efs。在接收数据(l比特)时,节点耗能表示如下:
ERx(l)=lEelec (2)
2.2 能量消耗不均衡问题
多跳路由的骨干网由多个簇首节点构成,簇成员间及内部处理是簇首能量消耗的两大方面,传统的算法忽略了距离汇聚点较近的簇首转发能量消耗问题。在均匀分簇方式下必然会加快节点能量消耗,提前出现失效现象[4]。将簇首周期性选取的方式和节点剩余能量选择方式有机的整合起来,集中了不同技术的优势,以簇首为重点,主动对网络中节点能量消耗进行均衡。
3 基于非均匀分簇的路由机制
3.1 EEUC算法
EEUC算法的根本在于对节点余下的能量进行对比,从而形成的分布竞争算法,簇首作为传感器网路的关键节点,具有协调数据传输、管理簇成员、向汇聚点发送数据及处理收集数据的功能,任务量较大,负载过重。EEUC以数据收集周期为单位,在重新收集的过程中会对簇进行重构,簇首节点的剩余能量相对较高。
3.2 簇首间多跳路由协议
数据在由簇首向汇聚点传输的过程中,簇成员收集的数据会在簇首的作用下整合并通过多跳通信途径继续传输。“多对一”是网络传感器在数据传输方面最显著的特征,但针对本研究中算法仍未研制出相应的路由协议。
若将数据冗余度限制在一定范围,簇成员间的数据不能整合处理,中继节点发挥的功能仅限于数据转发。设定TD_MAX为阈值,汇聚点同簇首间距如果比该阈值小,簇首即可直接通过通信的方式连接汇聚点;反之会通过多跳通信途径进行传输。采用路由算法,全网中的各个簇首在固定功率下会发出NODE_STATE_MSG消息,sj簇首发出的消息被si接收后,即大致可算出二者的间距。
4 EEUC的分析
性质1:网络中EEUC算法的消息复杂度为O(N)。
该性质表明EEUC算法能量高效,大大降低了消息的开销。EEUC同HEED分簇算法相比,二者虽然都为消息驱动,Niter@N指的是最大消息交换次数,其中消息迭代次数表示为Niter。EEUC消息开销优于HEED的原因在于,其不存在消息迭代。
应用EEUC算法时,若将取值范围限制参数设置为c,候选簇首最大竞争半径设置为R。在研究网络存活时间受二者大小影响的过程中,c确定了簇成员间的非均匀程度,在c增大的过程中,R的大小变化越大,使得簇成员数目变化增大。若R0c不变,c逐渐变大会导致各个候选簇首竞争半径变小,EEUC算法生成簇首数目增多;若c不变,R0c逐渐变大会导致各个候选簇首竞争半径变大,EEUC算法生成簇首数目减少。网络节点能量消耗的减少可以通过优化c及R0c取值的方式实现,但对于非均匀分簇算法下的参数优化理论仍需不断探索。 5 实验结果与分析
5.1 簇首的特征
在应用EEUC分簇算法时,参数c及R0c影响着簇首数目的选取,当参数c在不同取值的情况下,R0c同簇首数目相应的关系,表明随着竞争半径的减小,EEUC分簇算法得出的簇首数目越多。
5.2 能量效率
整个网络中主要的能量消耗就是簇首耗能,这就需要在一个轮次下,对不同协议产生的所有簇首总消耗能量进行对比分析。结果表明:簇首能量消耗最高的为以单跳通信途经传输的LEACH-E及LEACH,二者生成的簇首数量较多且不稳定,通信次数和能量消耗相继增大,也存在波动大的特点;而簇首能量消耗最低的要属簇首数据传输途径均为多跳通信途径的HEED-M及EEUC,相差不大,能量消耗明显低于其他协议。
6 结论及工作展望
以EEUC为基础的非均匀分簇的无线传感器网络路由协议具有显著的优势,弥补了原有几个分簇协议的不足,达到网络能量消耗的最优化效果,还可以发挥延长网络存活时间的作用。但在测量节点之间距离的问题上,通过接收信号强度的方式可以减少费用,并降低功率,然而由于电磁波存在很大的不稳定性,不可避免的会出现误差,干扰距离测量的结果。本研究主要满足了路由协议设计能量高效的要求,但并未对参数在算法中的优化取值进行深入的分析,因此还需要加大研究力度,展开进一步的探索,逐步对测距途径进行创新和改进。
参考文献
[1]Lindsey S, Raghavendra C, Sivalingam K M. Data gathering algorithms in sensor networks using energy metrics. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(9): 924-935.
[2]Soro S, Heinzelman W. Prolonging the lifetime of wireless sensor networks via unequal clustering//Proceedings of the 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, Denver, CO,2005.
[3]Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks//Proceedings of the ACM Mobile Computing and Networking (MobiCom), Boston, MA, 2000:56-67.
[4]周四望,林亚平,聂雅琳,等.无线传感器网络中基于数据融合的移动代理曲线动态路由算法研究[J].计算机学报,2007(06).
关键词 非均匀分簇;无线传感器网络;能量消耗
中图分类号:TP393 文献标识码:A 文章编号:1671-7597(2015)03-0050-02
传感器网络本质上可看作是一种无线网络,是在一定的观测环境下,以无线通信的途径将分布的各个微型传感器节点进行整合而成的。传感器节点能量的高效利用是网络协议的核心设计任务,从而使网络存活时间进一步延长。通过对建立在能量高效的非均匀分簇算法基础上的基于非均匀分簇的传感器网络路由协议研究,加深人们对非均匀分簇算法的认识,为相关研究提供参考意见。
1 传感器网络的分簇协议相关研究工作
在传感器网络分簇协议方面,众多学者已经展开了大量的研究,取得了一定的研究成果。其中,Lindsey等学者在研究中论述了PEGASIS算法,要求掌握各个节点对应的位置信息,并通过链状的方式将节点联系起来,链状传输数据的过程中还具备一定的处理功能,完成向汇聚点传输数据的任务[1]。就研究内容来看,在簇成员节点间能量消耗平衡方面的研究非常多,但缺乏对平衡簇首间能量消耗问题的研究。传感器网络多跳路由的“热区”问题是由Soro等学者首次提出的,在其研究过程中开创了非均匀簇这一解决方式的范例,为专业人士的深层次研究指明了方向[2]。
从应用场景的角度来看,移动自组网络同传感器网络大不相同,后者需要优化的路由协议的支持。定向扩散路由协议在Intanagonwiwat等研制下,使得路由机制具备查询功能,查询消息由汇聚点发出后,沿逆向梯度对数据进行传输[3]。
2 基于非均匀分簇的无线传感器网络路由的问题描述
2.1 网络模型
选取网络中传感器节点总数为N,随机部署在周期性数据收集场景中,第i个节点通过si体现,则节点集合可表示为{s1,s2…sN}=S,其中N=|S|。
若:1)在观测区域A(方形)外中存在数据汇聚点,确定汇聚点DS、传感器节点的位置后不能进行改变;2)各个节点具有相应的ID,节点构造均相同,可以对数据进行整合处理;3)链路具有对称性,接收信号的发射功率已知的情况下,节点依据强度RSSI计算自身同发射点的大致间距。
在通过无线通信能量消耗模型进行分析时,节点向间距为d处发送l比特数据,功率放大损耗、发射电路损耗(Eelec)之和为总能量消耗。表示如下:
lEelec+lEfsd2, d
lEelec+lEmpd4, dEdo
假设传输距离≥d。,利用多路径衰减模型表示功率放大损耗,需要的功率放大能量为Emp;而传输距离在阈值d。以内时,利用自由空间模型表示,需要的功率放大能量为Efs。在接收数据(l比特)时,节点耗能表示如下:
ERx(l)=lEelec (2)
2.2 能量消耗不均衡问题
多跳路由的骨干网由多个簇首节点构成,簇成员间及内部处理是簇首能量消耗的两大方面,传统的算法忽略了距离汇聚点较近的簇首转发能量消耗问题。在均匀分簇方式下必然会加快节点能量消耗,提前出现失效现象[4]。将簇首周期性选取的方式和节点剩余能量选择方式有机的整合起来,集中了不同技术的优势,以簇首为重点,主动对网络中节点能量消耗进行均衡。
3 基于非均匀分簇的路由机制
3.1 EEUC算法
EEUC算法的根本在于对节点余下的能量进行对比,从而形成的分布竞争算法,簇首作为传感器网路的关键节点,具有协调数据传输、管理簇成员、向汇聚点发送数据及处理收集数据的功能,任务量较大,负载过重。EEUC以数据收集周期为单位,在重新收集的过程中会对簇进行重构,簇首节点的剩余能量相对较高。
3.2 簇首间多跳路由协议
数据在由簇首向汇聚点传输的过程中,簇成员收集的数据会在簇首的作用下整合并通过多跳通信途径继续传输。“多对一”是网络传感器在数据传输方面最显著的特征,但针对本研究中算法仍未研制出相应的路由协议。
若将数据冗余度限制在一定范围,簇成员间的数据不能整合处理,中继节点发挥的功能仅限于数据转发。设定TD_MAX为阈值,汇聚点同簇首间距如果比该阈值小,簇首即可直接通过通信的方式连接汇聚点;反之会通过多跳通信途径进行传输。采用路由算法,全网中的各个簇首在固定功率下会发出NODE_STATE_MSG消息,sj簇首发出的消息被si接收后,即大致可算出二者的间距。
4 EEUC的分析
性质1:网络中EEUC算法的消息复杂度为O(N)。
该性质表明EEUC算法能量高效,大大降低了消息的开销。EEUC同HEED分簇算法相比,二者虽然都为消息驱动,Niter@N指的是最大消息交换次数,其中消息迭代次数表示为Niter。EEUC消息开销优于HEED的原因在于,其不存在消息迭代。
应用EEUC算法时,若将取值范围限制参数设置为c,候选簇首最大竞争半径设置为R。在研究网络存活时间受二者大小影响的过程中,c确定了簇成员间的非均匀程度,在c增大的过程中,R的大小变化越大,使得簇成员数目变化增大。若R0c不变,c逐渐变大会导致各个候选簇首竞争半径变小,EEUC算法生成簇首数目增多;若c不变,R0c逐渐变大会导致各个候选簇首竞争半径变大,EEUC算法生成簇首数目减少。网络节点能量消耗的减少可以通过优化c及R0c取值的方式实现,但对于非均匀分簇算法下的参数优化理论仍需不断探索。 5 实验结果与分析
5.1 簇首的特征
在应用EEUC分簇算法时,参数c及R0c影响着簇首数目的选取,当参数c在不同取值的情况下,R0c同簇首数目相应的关系,表明随着竞争半径的减小,EEUC分簇算法得出的簇首数目越多。
5.2 能量效率
整个网络中主要的能量消耗就是簇首耗能,这就需要在一个轮次下,对不同协议产生的所有簇首总消耗能量进行对比分析。结果表明:簇首能量消耗最高的为以单跳通信途经传输的LEACH-E及LEACH,二者生成的簇首数量较多且不稳定,通信次数和能量消耗相继增大,也存在波动大的特点;而簇首能量消耗最低的要属簇首数据传输途径均为多跳通信途径的HEED-M及EEUC,相差不大,能量消耗明显低于其他协议。
6 结论及工作展望
以EEUC为基础的非均匀分簇的无线传感器网络路由协议具有显著的优势,弥补了原有几个分簇协议的不足,达到网络能量消耗的最优化效果,还可以发挥延长网络存活时间的作用。但在测量节点之间距离的问题上,通过接收信号强度的方式可以减少费用,并降低功率,然而由于电磁波存在很大的不稳定性,不可避免的会出现误差,干扰距离测量的结果。本研究主要满足了路由协议设计能量高效的要求,但并未对参数在算法中的优化取值进行深入的分析,因此还需要加大研究力度,展开进一步的探索,逐步对测距途径进行创新和改进。
参考文献
[1]Lindsey S, Raghavendra C, Sivalingam K M. Data gathering algorithms in sensor networks using energy metrics. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(9): 924-935.
[2]Soro S, Heinzelman W. Prolonging the lifetime of wireless sensor networks via unequal clustering//Proceedings of the 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, Denver, CO,2005.
[3]Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks//Proceedings of the ACM Mobile Computing and Networking (MobiCom), Boston, MA, 2000:56-67.
[4]周四望,林亚平,聂雅琳,等.无线传感器网络中基于数据融合的移动代理曲线动态路由算法研究[J].计算机学报,2007(06).