基于无线传感器网络技术和水声通信技术的水声传感器网络已经成为当前的研究热点[1-2]。但由于水声传感器网络在介质空间、信号传输载体、噪声来源等方面与陆上无线电通信有着巨大的差异,水声通信信道明显区别于无线电通信信道,在传输性能上具有其特异性[3],一些适用于陆地无线传感器网络的一些技术或协议,不能直接应用到水声传感器网络中[4],需要针对水下通信环境设计相应的传感器网络通信协议。LEACH以及其演进算法是一组广泛应用的传感器网络分簇算法协议簇,基本思想是以周期、循环、随机的方式来选择簇头节点,使整体网络的能量消耗均匀地分摊到每个传感器节点上[5]。该协议在网络系统寿命、延时及应用等方面达到较好的性能。但是LEACH也存在着簇头数目不稳定,分布不均匀等问题。一些演进算法通过引入集中式控制算法,增加地理位置信息等方法来解决上述问题,但是水声传感器网络节点间通信代价远远大于陆上传感器网络节点间通信,这使得上述演进算法不能应用于水声传感器网络。本文以LEACH算法为基础,结合水声通信环境,提出了一种新的分布式簇头选举算法,提高簇头数目稳定性和分布均匀性,优化网络性能。
1 水声传感器网络随着硬件和水声通信技术的发展,传感器节点已具备水下作业能力,已经实现了水下环境的传感器节点协同组网并以声通信方式形成了水声传感器网络( underwate acoustic sensor networks,UASN)[6]。由于水介质的特殊性和复杂性,UASN只能采用声波通信方式,因此信号传输时延大,传播距离受限,通信带宽窄且误码率高,报文发送能耗远高于报文接收能耗,随着通信距离的增加,其能耗指数级增长[7]。文献[8]对于水声传感器节点发送及接收数据的能量消耗模型描述如下:
式中:Et表示发射能量;Er表示接收能量;l表示传输数据bit量;E表示节点处理单位bit数消耗能量;Tb表示单位bit传输时长;C为基于声呐方程推导出的当发射器处于最小发射功率时的系数,取值为2π×(0.67)×10-9;H表示节点下放深度;d为传输距离;f为水声信号传输频率;α(f)为频率吸收系数:
2 LEACH算法分析 2.1 LEACH算法概述LEACH协议以节能为目的,采用分簇思想,将网络监测区域内的节点划分为若干虚拟簇,每个簇内只有一个簇头节点,簇头节点不但要负责对数据的采集,还要负责接收簇内节点发送来的数据,并且在进行数据转发之前,要对所有数据进行聚合处理,最后才将数据直接传送至汇聚节点,所以簇头节点要比普通节点消耗更多的能量。为了均衡节点的能量消耗,LEACH协议采用随机轮换选举簇头的方式使每个节点都有担任簇头的机会,以达到均衡节点能耗的目的。LEACH协议以“轮”为周期,每一轮包括簇的建立阶段和数据传输阶段2部分,流程图如图 1所示。
2.2 LEACH协议簇头选举阶段在簇的建立阶段,节点通过自主竞争随机成为簇头节点,每个节点随机产生一个介于0~1的随机数,如果该随机数小于阈值T(r),则此节点在全网内发送一个成为簇头节点的消息,否则该节点等待加入最近的簇头节点。其中阈值表达式为
式中:r代表当前运行的轮数,p代表普通节点成为簇头节点的概率,G代表在前轮中还未成为簇头节点的节点集合。当节点在第r轮成为簇头节点,则该节点在接下来的
数据传输阶段,为防止簇内节点在数据传输时产生碰撞,影响数据传输,簇头节点根据时分多址(TDMA)技术给簇内节点分配时隙,每个节点只有在自己的时隙内才向簇头节点传输消息,在其他时隙内则关闭收发器。这样,减少了节点由于空闲侦听而浪费的能量。簇内节点与簇头节点的数据通信釆用自由空间模型,即一跳传输。簇头节点收到来自簇内节点发送来的数据后,首先对数据进行聚合、压缩,这样减少了簇头节点不必要的数据传输,节约了能量。簇头节点与汇聚节点的通信也采用一跳传输模式,等待数据传输一段时间后,开始新一轮的循环。
3 簇头选举算法改进 3.1 簇头选举算法分析水声传感器网络是一种特殊的传感器网络,除了需要面对一些传感器网络共性问题,还需要面对水下通信环境带来的一些挑战。
由于LEACH协议采用分布式簇头选取方式,因此簇头选举随机性很强,可能会出现簇头集中在某一个区域的现象,造成簇头分布不均匀、簇头数目不稳定。为解决上述问题,大量应用于陆地传感器网络的LEACH演进算法被提出,这些演进算法的主要思想是通过采用集中式控制算法、增加节点间信息交互、获取节点位置能量等信息的方式来优化簇头节点选举方式,降低簇头节点数目的自由度,提高分布均匀性。文献[9]给出了2种传感器节点不同状态下的功率消耗。
如表 1所示,由于水下通信环境的特殊性,缺乏基础通信设施建设,水声传感器节点发送接收功耗远大于陆地无限传感器节点,这使得采用集中式控制增加节点间信息交互量实现优化的演进算法并不适用于水声传感器网络,因此需要对适用于水声传感器网络的分布式簇头选举算法进行改进,实现网络性能优化。
3.2 簇头选举算法优化
水声传感器网络簇头选举采用分布式选举算法,监测区域内均匀分布N个传感器节点,分布服从二维泊松分布[7],在每轮中传感器节点以概率p(0≤p≤1)当选为簇头节点且选举相互独立,因此符合二项分布概率模型,每轮中簇头节点数目的期望方差为
在均值一定的情况下,方差越大,簇头当选数目自由度越高,单次选举簇头数目越多,簇头集中概率越大。
为提高每轮中簇头数目稳定性和分布均匀性,在每轮簇头选举过程中,簇头选举分为2次完成。
如图 2所示,首次选举以概率p(1)(p(1)<p)选举簇头节点,节点随机产生一个介于0~1的随机数,如果该随机数小于阈值T(1)(r)(T(1)(r)<T(r)),则节点当选为簇头节点,同时发布簇头当选信息,阈值T(1)(r)表达式为
首次选举产生的簇头节点数目期望为E(CH(1))=Np(1),为了保证簇头节点数与标记节点数目比值为p,防止2次选举的簇头间距过小,最佳覆盖范围内Np(1)/p个邻居节点被标记为成员节点[10]。
首次选举结束后,未被标记的节点再次进行簇头选举,参与选举的节点再次随机产生一个介于0~1的随机数,如果该随机数小于阈值T(n),则此节点发送当选为簇头节点的消息,将邻居节点标记成为簇成员节点。每轮当选簇头节点的数目期望为
簇头数目方差与参加次轮选举的未标记节点数目N(2)有关,满足下式:
因此在不需采用集中控制和增加节点间通信量的情况下,提高了每轮簇头数目的稳定性和分布均匀性,避免了簇头间距过小簇头冗余造成的能量浪费,延长了网络寿命。
4 算法仿真与分析本文采用MATLAB平台对LEACH算法与本文改进算法进行仿真,在25.6 km×25.6 km水下通信区域随机布放256个通信节点,仿真参数如表 2所示。
参数 | 值 |
节点数目 | 256 |
网络区域/km2 | 25.6×25.6 |
基站位置/km | (12.8,12.8) |
数据长度/bit | 4 000 |
控制数据长度/bit | 100 |
初始节点能量/J | 0.5 |
簇头当选概率 | 0.04 |
如图 3所示,当簇头选举概率p=0.04时,可以获得最优的网络生存时间。
由于实验中节点分布具有随机性,并考虑其他相关因素的影响,本文取1 000次实验结果作为统计样本求取均值方差。仿真结果如图 4、5所示,与LEACH算法相比,本文算法在具有相同的簇头节点数目均值的情况下具有更小的簇头节点数目方差,每轮选举的簇头节点数目更加稳定,有效避免了由于簇头数目不稳定引起的能量浪费。
由图 6仿真结果可知,本文算法有效提高了网络生存时间,延迟了首节点死亡时间,与LEACH算法相比较,本文算法的生存曲线更加陡峭,有效均衡节点能量消耗,避免部分节点过早消亡造成网络空洞,优化了水声传感器网络性能。
5 结论根据LEACH算法,结合水下通信环境,本文提出了一种有限增加算法复杂度,避免大量节点间信息交互,有效适用于水下通信环境的LEACH演进算法。通过仿真实验与LEACH算法进行对比,验证改机算法性能:
1)将簇头选举增加到2次,在首次选举簇头节点数目占网络中本轮簇头节点节点数目80%的情况下,网络簇头节点数目稳定性最高,验证了算法可有效提高网络中簇头节点数目的稳定性。
2)在网络簇头数目期望满足最佳簇覆盖范围的情况下,本文所提出的LEACH演进算法与LEACH算法存活节点数目进行相比较,有效延缓了节点死亡时间,改进算法有效延长了网络的生存时间。
3)LEACH演进算法有效延长了网络寿命,优化网络能耗负载,实现了网络性能的优化。
[1] | HAMIDZADEH M, FORGHANI N, MOVAGHAR A. A new hierarchal and scalable architecture for performance enhancement of large scale underwater sensor networks[C]//Proceedings of IEEE Symposium on Computers & Informatics. Kuala Lumpur, Malaysia, 2011:520-525. |
[2] | FAN Guangyu, CHEN Huifang, XIE Lei, et al. An improved CDMA-based MAC protocol for underwater acoustic wireless sensor networks[C]//Proceedings of the 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM). Wuhan, China, 2011:1-4. |
[3] | SOMMER N, FEDER M, SHALVI O. Low-density lattice codes[J]. IEEE transactions on information theory,2008, 54 (4) : 1561 –1585. |
[4] | XING Funing, CAI Shaobin, GAO Zhengguo, et al. A network coding based protocol for reliable data transfer in underwater acoustic sensor networks[C]//Proceedings of the Sixth ACM International Workshop on Underwater Networks. New York, USA, 2011:1176-1177. |
[5] | KURKOSKI B, DAUWELS J. Reduced-memory decoding of low-density lattice codes[J]. IEEE communications letters,2010, 14 (7) : 659 –661. |
[6] | 李永翠. 水声传感器网络分簇协议的研究[D]. 大连:大连海事大学, 2014. |
[7] | HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE transactions on wireless communications,2002, 1 (4) : 660 –670. |
[8] | 孙力娟, 刘林峰, 杜晓玉, 等. 水声传感器网络拓扑控制技术综述[J]. 南京邮电大学学报:自然科学版,2012, 32 (5) : 20 –25. |
[9] | ZHAO Liang, LIANG Qilian. Optimum cluster size for underwater acoustic sensor networks[C]//Proceedings of IEEE Military Communications Conference MILCOM. Washington DC, USA, 2006:1-5. |
[10] | 卞金洪, 徐新洲, 魏昕, 等. 水声通信网层次路由算法[J]. 哈尔滨工程大学学报,2013, 34 (3) : 275 –279. |
[11] | 钟永信, 黄建国, 韩晶. 一种用于格型拓扑的水声传感器网络TDMA协议[J]. 电子与信息学报,2010, 32 (7) : 1774 –1778. |
[12] | 陈树, 徐圆. 基于分簇和覆盖优化的改进LEACH协议[J]. 计算机工程,2014, 40 (11) : 97 –100. |