基于能量的水声传感器网络分簇算法优化
2017-03-14赵旦峰陈通
赵旦峰, 陈通,2
(1.哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001; 2.北京长城电子装备有限责任公司，北京 100082)
基于能量的水声传感器网络分簇算法优化
赵旦峰1, 陈通1,2
(1.哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001; 2.北京长城电子装备有限责任公司，北京 100082)
针对分簇水声传感器网络中簇头分布不均和水声信道时变特性等原因导致的节点能量分布不均的问题，以LEACH(low energy adaptive clustering hierarchy protocol )算法为基础，提出了一种基于网络能量状态估计的分布式算法进行簇头选举，有效均衡网络能耗。通过改进分布式簇头选举机制，每轮中簇头选举由一次选举改为多次选举，在不需要中心控制节点和增加节点间通信量的情况下，首次选举通过设置能量阀值选举出高能量节点担任簇头，通过第二次选举保证每轮簇头数目稳定。仿真结果表明，该改进算法能够解决分簇水声传感器网络时变信道条件下能量消耗不均衡的问题，均衡网络能耗，延缓网络首节点死亡时间。
水声传感器网络；LEACH；分布式；簇头；能量均衡
水声传感器网络(underwater acoustic sensor networks, UASNs)是集数据采集、处理和传输为一体的综合信息处理系统，可以对海洋信息进行有效监测[1-5]。在无人值守的情况下对海洋信息进行长时间监测需要消耗大量能量，然而UASNs的节点能量储备有限且难以进行补给[6-8]，因此能够延长水声传感器网络生命周期的分簇拓扑控制技术成为了当前的研究热点[9-13]。
LEACH[13](low energy adaptive clustering hierarchy)协议是麻省理工大学Heinzelman等[14]提出的一种自适应分簇拓扑控制协议，基本思想是通过周期、循环、随机的方式来选择簇头节点，可以使整体网络旳能量消耗均匀地分摊到每个传感器节点上。与一般的平面拓扑控制协议相比，可以将网络生命周期延长15%[15-16]。以陆上传感器网络LEACH协议研究为基础，近年来陆续提出了一些可以应用于水声传感器网络的LEACH改进协议。文献[17]指出在水声传感器网络监测区域确定的情况下，网络中能量消耗的期望是关于簇覆盖范围的函数，可以通过调整网络中簇的覆盖范围来降低网络能耗。文献[18]中提出了一种以节点与基站之间距离为主要参考指标的水声传感器网络层次拓扑控制方法，簇头节点距离sink节点越近，节点当选簇头的概率越大，以此来均衡网络能耗，降低簇头节点和sink节点通信的能量损失，从而提高网络的能量效率，延长网络寿命。文献[19]中对应用于水声传感器网络的LEACH协议中簇结构建立阶段广播簇头当选消息碰撞问题进行了分析，提出了降低广播簇头当选消息碰撞概率的改进协议，改进协议通过时隙划分的方式有效降低了播簇头消息的碰撞概率，避免了因为信息重传造成的能量浪费。但上述研究没有考虑水声信道时变特性对网络每轮能量消耗的影响。由于网络中每轮能耗存在差异，节点周期性当选簇头节点的轮换方法不能有效均衡网络能耗。
针对水声传感器网络每轮能量消耗不均衡的问题，本文提出了一种基于能量的水声传感器网络分簇算法LEACH-ET。优化算法通过增加簇头选举过程中高能量节点簇头当选概率均衡网络能耗，通过增加每轮簇头选举次数保证网络簇头节点数目稳定。优化算法通过均衡网络能耗，稳定簇头节点数目，有效推迟了网络首节点死亡时间，延长了网络寿命。
1 水声传感器网络能量模型
陆上传感器网络信号传输损耗与信号传输距离d相关，但由于水声传感器网络情况特殊，信号传输损耗不仅与信号传输距离相关，同时还与信号频率等传输条件相关。
根据Urick的数据和公式，Jurdak等人推导出下列模型：
SL=TL+85
(1)
式中：SL为声源级,TL为传输损耗。式中物理量均以dB为单位，参考值1 μPa的量值为0.67×10-22W/cm2，由于水声传感器节点通常布放在海底，可以采用柱状波传输损耗模型，信号传输损耗：
(2)
式中：d为声信号发射机与接收机间的距离；α为与频率相关的吸收系数。为了表示α与频率之间的函数关系，可以将α写成α(f)，通常情况下水声传感器网络采用Thorp给出的水声信号低频段吸收损耗经验公式[20]：
(3)
式中f表示信号的传输频率。
为了得到在参考距离1m处的强度It，则水声信号发射功率Pt：
(4)
式中H表示当前水深，It与SL关系：
(5)
则可以由式(1)～(5)可以导出声信号发射功率Pt满足：
pt=CHdeα(f)d
(6)
C为基于声呐方程推导出的发射器处于最小发射功率时的系数，取值为2π×(0.67)×10-9；H表示节点下放深度；d为传输距离；f为水声信号传输频率；α(f)为频率吸收系数。
因此水声传感器节点发送数据消耗能量Etx及接收数据消耗能量Erx的通用模型可以描述为
(7)
式中：l表示传输数据bit量，Eelec表示节点处理单位bit数据消耗能量，Tb表示单位bit数据传输时长。
2 LEACH-ET算法
由于水声传感器网络中缺少中心控制节点，节点通信能力受限，水声通信环境中难以通过中心控制或节点间大量信息交互的方式获取全局网络能量信息，只能采用分布式簇头选举算法，每轮簇头节点数目存在差异，同时水声信道时变特性将导致网络能量消耗不均，部分节点可能过早死亡。为了均衡网络能量分布，改进算法通过设定能量阀值Eth，规定只有能量高于Eth的节点才可以参加簇头选举，提高高能量节点担任簇头的概率。但是由于节点难以获取全局网络能量信息，难以使能量大于Eth的节点数目保持稳定，因此无法保证每轮簇头节点数目的稳定性。为了保证簇头节点数目的稳定性，每轮进行两次簇头选举，首次选举出部分高能量节点担任簇头，通过第二次选举提高每轮簇头节点数目稳定性。
首次簇头选举只有高能量节点参加，以概率ph当选为簇头节点，高能量节点数目Nh应当满足：
Nhph (8) 式中：E(CH)为本轮簇头数目期望，首次簇头选举中当选的节点在选举结束后完成簇建立；剩余未加入簇的节点进行第二次簇头选举，节点以概率p当选簇头节点，通过第二次选举保证簇头数目的稳定性。每轮簇头节点数目期望可以表达为 (9) 阀值Eth的设定决定了参加首次选举节点的数目Nh，在ph为定值情况下，Nhph的值是只与Nh有关的函数，因此能量阀值Eth的设定决定了协议性能。为了保证Nhph 水声传感网络中节点难以通过节点间信息交互或集中控制方式获取高能量节点数目Nh的准确值，但每轮簇头节点选举过程中，簇头节点会广播当选信息，因此可以通过首次选举中簇头节点数目和第二次选举中簇头节点数目对Nh进行估计。在首次簇头选举中，高能量节点以概率ph当选簇头节点，高能量节点是否当选簇头节点满足独立同分布条件，则簇头节点数目满足二项分布条件, 则可以通过矩估计方法对Nh的值进行估计，表示为 (10) (11) 每一轮中簇头节点数目并不是一个固定的值，而是在期望值附近波动，可以通过二项分布均值方差来衡量簇头节点数目稳定性。在均值一定时，簇头节点数目方差越小，簇头节点数目越稳定。根据上述网络模型，在N=256，p=0.1，ph从0.05～0.5变化的条件下进行了十次仿真实验，每次实验分别对500轮仿真实验中簇头节点数目均值与方差进行统计。由图1和图2可知，改进算法中ph较小的情况簇头数目均值与LEACH算法基本相同，但随着ph的增加，导致Nhph>E(CH)，簇头数目均值不断增加。 图1 簇头节点数目均值Fig.1 Mean of cluster head node number 改进算法簇头数目方差也随着ph变化，ph较小时，首次选举簇头数目较少，二次选举簇头数目较多时簇头数目方差与LEACH算法相近，随着ph增加且满足Nhph 图2 簇头节点数目方差Fig.2 Variance of cluster head node number 根据水声传感器网络模型对改进算法与LEACH、LEACH-E算法进行比较，规定簇成员节点只能与簇头节点通信，簇成员节点与簇头通信采用TDMA协议，成员在规定时间内向簇头传输数据，簇内通信不会产生干扰；簇头节点在收集数据完成后直接传给sink节点，sink节点与簇头通信采用CDMA协议，簇头与sink节点通信过程中不会干扰其它簇头节点与sink节点通信，且簇内通信也不会对其他簇的任何通信产生干扰。仿真参数设置如表1所示[21]。 表1 仿真参数 为了验证改进算法性能，模拟分簇水声传感器网络中簇头分布不均和信道时变特性等原因导致的节点能量异构，节点初始能量均匀的分布在0.5～0.35 J，在N=256，p=0.1的条件下验证不同ph值对网络性能影响，仿真如图3所示。 图3对不同ph值下网络存活节点数目进行统计，在ph=0.05时，首次选举簇头节点数目过小，无法有效均衡网络能耗；随着ph的增加到0.25时，网络能量均衡效果得到了有效改善，延迟了首节点死亡时间，在首节点死亡过后，其余节点均在短时间内死亡；但随着ph增加至大于0.5时，由于首次选举簇头数目增加导致Nhph>E(CH)，本轮簇头均为高能量簇头节点，但网络中簇头节点数目大于本轮簇头数目期望且方差不断增加，这导致网络能量均衡效果减弱，首节死亡时间比ph=0.25要早，且首节点死亡时间随着ph的进一步增加而提前。 为了验证改进算法的性能，在ph=0.25时对网络中节点能量分布和存活节点数目进行统计，并与LEACH、LEACH-E两种算法进行对比，仿真实验结果如图4～6所示。 图3 ph对存活节点数目的影响Fig.3 Number of nodes alive of different ph 图4 LEACH节点能量分布Fig.4 Node energy distribution of LEACH 图5 LEACH-E节点能量分布Fig.5 Node energy distribution of LEACH-E 图6 改进算法节点能量分布Fig.6 Node energy distribution of optimization algorithm 为了验证算法能量均衡效果，分别对网络第1轮，第200轮，第400轮和第600轮节点能量分布进行统计，将0～0.5J均匀分成20个能量区间，对能量处于相应区间的节点数目进行统计，在网络运行过中，全部节点能量分布区间越小，分布范围越集中，网络能量均衡效果约好。 在水声传感器网络中节点初始能量均匀分布在0.5～0.35J，LEACH算法在簇头选举过程中未考虑节点能量，在网络运行过程中节点能量分布区间具有扩大趋势，200轮时，节能量分布在0.15～0.4J，400轮时开始出现节点死亡，能量在0～0.3J，直至节点开始出现因能量耗尽死亡，节点能量分布区间变小，600轮时存活节点能量分布在0～0.225J，在水声时变信道情况下仅通过节点周期性当选簇头节点的轮换方法不能起到良好的网络能耗均衡效果；由于LEACH-E算法以节点能量为参考选举簇头节点，因此与LEACH算法相比提高了节点能量分布集中程度，200轮时节点能量分布在0.175～0.4J，400轮时节点能量分布在0.05～0.3J，600轮时存活节点能量分布在0～0.125J，在相同时间内节点能量分布区间均小于LEACH算法，能量均衡效果得到了提升，同时避免了节点因能量耗尽而过早死亡；改进算法中节点能量分布集中程度优于上述两种算法，在第200轮70%以上的节点分布在0.275～0.3J，第400轮75%以上的节点能量分布在0.125～0.15J，第600轮90%以上存活节点能量分布在0～0.025J，这证明改进算法在信道时变的水声传感器网络中，通过提高高能量节点簇头当选概率的方法可以有效的均衡网络能耗。 图7对三种算法存活节点数目进行了统计。LEACH算法最先出现节点死亡的情况，随后节点开始缓慢死亡，LEACH算法在簇头选举过程中没能考虑节点能量，簇头节点能量消耗远大于簇成员节点，在水声通信环境中，水声信道时变特性导致网络每轮能量消耗存在差异，LEACH算法中节点通过周期性当选簇头节点的轮换方法不能很好的均衡网络能耗，部分节点能量消耗过快，死亡时间较早，节点死亡时间差异较大，影响网络性能，网络能量均衡效果较差；LEACH-E算法在簇头选举中考虑能量因素，由于水声时变信道特性，每轮节点能量消耗存在差异，LEACH-E算法通过降低低能量节点簇头当选概率来均衡网络能耗，因此可以有效降低网络首节点死亡时间，能量均衡效果优于LEACH算法，但簇头选举中低能量节点仍然有较大机会当选簇头，节点间死亡时间差异也比较大，且需要收集网络中全体节点能量信息，算法在水声环境下实现难度较大；改进算法首节点死亡时间最晚，且网络中节点死亡时间差异最小，由于改进算法每轮簇头选举分为两次完成，首次簇头选举通过设置能量阀值，避免了低能量节点当选簇头，可以有效均衡网络能耗，为了避免每轮节点能量变化，能量阀值调整导致每轮网络簇头节点数目变化过大，通过第二次选举使每轮簇头数目保持稳定，低能量节点簇头当选概率远远小于上述两种算法，因此在信道时变的水声传感器网络中改进算法首节点死亡时间最晚，存活节点数目曲线最陡峭，证明改进算法具有良好的能量均衡效果。 图7 存活节点数目Fig.7 Number of nodes alive 针对水声信道时变特性导致网络每轮能量消耗存在差异的问题，本文提出了一种基于能量的簇头选举算法，每轮簇头选举分为两次完成，通过首次簇头节点选举中高能量簇头数目可以有效估计网络能量状况，并合理设置首次簇头选举能量阀值，避免了低能量节点当选簇头，通过第二次选举保证了每轮选举簇头数目的稳定。通过仿真实验与LEACH和LEACH-E算法进行对比，验证了算法性能： 1) 在不增加节点间通信量和中心控制节点的情况下通过改进簇头节点选举策略，合理设置能量阀值Eth和高能量节点簇头当选概率ph可以提高高能量节点簇头当选概率和每轮簇头节点数目的稳定性； 2) 在时变水声通信环境下，改进算法有效的延缓了首节点死亡时间，提高了水声传感器网络能量均衡效果。 水声通信环境复杂多变，水声传感器网络自适应设置高能量节点簇头当选概率ph是下一步的研究重点。 [1]VERMA S. Communication architecture for underwater wireless sensor network[J]. Communication architecture for underwater wireless sensor network, 2015, 7(6): 67-74. [2]AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks: research challenges[J]. Ad Hoc network, 2005, 3(3): 257-79. [3]GUANGYU F, HUIFANG C. An Improved CDMA-based MAC protocol for underwater acoustic wireless sensor networks[C]. Wireless Communications, Networking and Mobile Computing (WiCOM), Chengdu, China, 2011: 1-6. [4]VERMA S. Communication architecture for underwater wireless sensor network[J]. Communication architecture for underwater wireless sensor network, 2015, 6: 67-74. [5]孙力娟, 刘林峰, 杜晓玉, 等. 水声传感器网络拓扑控制技术综述[J]. 南京邮电大学学报: 自然科学版, 2012, 32(5): 20-25. SUN Lijuan, LIU Linfeng, DU Xiaoyu, et al. Overview of topology control techniques in underwater acoustic sensor networks[J]. Journal of Nanjing university of posts and telecommunications: natural science, 2012, 32(5): 20-25. [6]WANG Yu, LIU Yingjian, GUO Zhongwen. Three-dimensional ocean sensor networks: a survey[J]. Journal of ocean university of China, 2012, 11(4): 436-450. [7]WAHID A, KIM D. An energy efficient localization-free routing protocol for underwater wireless sensor networks[J]. International journal of distributed sensor networks, 2012, 8(4): 307246. [8]PARTAN J, KUROSE J, LEVINE B N. A survey of practical issues in underwater networks[J]. Proc Acm Wuwnet, 2006, 11: 23-33. [9]AZIZ A A, SEKERCIOGLU Y A, FITZPATRICK P, et al. A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks[J]. IEEE communications surveys & tutorials, 2013, 15(1): 121-144. [10]OVALIADIS K, SAVAGE N. Cluster protocols in underwater sensor networks: a research review[J]. Journal of engineering science and technology review, 2014, 7(3): 171-175. [11]PUROHIT R, SIDHU N. Wireless sensor network: Routing protocols and attacks- a survey[C]. 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom), 2015. [12]OVALIADIS K, SAVAGE N. Cluster protocols in underwater sensor networks: a research review[J]. Journal of engineering science and technology review, 2014, 7(3): 171-175. [13]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. [14]刘壮, 冯欣, 王雁龙, 等. 基于双簇头聚类分簇和数据融合的无线传感器网络路由算法[J]. 吉林大学学报: 理学版, 2015, 53(5): 1013-1017. LIU Zhuang, FENG Xin, WANG Yanlong, et al. An improved clustering routing algorithm based on double-CH clustering and data fusion in WSN[J]. Journal of Jilin university: science edition, 2015, 53(5): 1013-1017. [15]LIN Hongzhi, WEI Wei, ZHAO Ping, et al. Energy-efficient compressed data aggregation in underwater acoustic sensor networks[J]. Wireless networks, 2016, 22(6): 1985-1997. [16]张瑞华, 程合友, 贾智平. 基于能量效率的无线传感器网络分簇算法[J]. 吉林大学学报: 工学版, 2010, 40(6): 1663-1667. ZHANG Ruihua, CHENG Heyou, JIA Zhiping. Energy-efficient clustering algorithm for wireless sensor net works[J]. Journal of Jilin university: engineering and technology edition, 2010, 40(6): 1663-1667. [17]ZHAO Liang, LIANG Qilian. Optimum cluster size for underwater acoustic sensor networks[C]//Proceedings of IEEE Military Communications Conference. Washington, DC: IEEE, 2006: 1-5. [18]YANG Guangsong, XIAO Mingbo, CHENG En, et al. A cluster-head selection scheme for underwater acoustic sensor networks[C]//Proceedings of 2010 International Conference on Communications and Mobile Computing. Shenzhen: IEEE, 2010: 188-191. [19]LI Yongcui, WANG Ying, JU Yang, et al. Energy efficient cluster formulation protocols in clustered underwater acoustic sensor networks[C]//Proceedings of the 7th International Conference on Biomedical Engineering and Informatics (BMEI). Dalian: IEEE, 2014: 923-928 [20]JIANG Peng, LIU Jun, WU Feng. Node non-uniform deployment based on clustering algorithm for underwater sensor networks[J]. Sensors, 2015, 15(12): 29997-30010. [21]卞金洪, 徐新洲, 魏昕, 等. 水声通信网层次路由算法[J]. 哈尔滨工程大学学报, 2013, 34(3): 275-279. BIAN Jinhong, XU Xinzhou, WEI Xin, et al. Research on hierarchical routing algorithm for underwater acoustic communication networks[J]. Journal of Harbin engineering university, 2013, 34(3): 275-279. Optimization of the cluster-head selection algorithm of an energy-based underwater acoustic sensor network ZHAO Danfeng1,CHEN Tong1,2 ( 1.College of Information and Communication Engineering, Harbin Engineering University,Harbin 150001,China; 2.Beijing Great Wall Electronic Equipment Co.,Ltd,Beijing 100082,China) To solve the uneven energy consumption problem caused by the time-varying characteristics of underwater acoustic channels and non-uniform distribution of cluster heads in underwater acoustic sensor networks (UASNs), a novel distributed low-energy adaptive clustering hierarchy (LEACH) algorithm was developed. The number of elections was increased in each round, and an energy threshold for the first cluster-head elections was set. If the node energy is higher than the energy threshold, the former can take part in the first cycle of cluster-head election, and the second cycle of cluster-head election can maintain the stability of the cluster-head number. Simulation results showed that the improved algorithm can eliminate the problem of unbalanced energy consumption under the time-varying channel conditions of the clustered acoustic sensor network. It can also balance the energy consumption of the network and prolong the survival period of the network′s first node. underwater acoustic sensor network; LEACH; cluster-head; distribution; energy consumption 2016-03-15. 日期：2016-11-16. 国家自然科学基金项目(61371099). 赵旦峰(1961-), 男, 教授,博士生导师. 赵旦峰,E-mail：zhaodanfeng@hrbeu.edu.cn. 10.11990/jheu.201603047 http://www.cnki.net/kcms/detail/23.1390.u.20161116.1613.008.html TN929.3 A 1006-7043(2017)02-0282-06 赵旦峰, 陈通. 基于能量的水声传感器网络分簇算法优化[J]. 哈尔滨工程大学学报， 2017, 38(2): 282-287. ZHAO Danfeng, CHEN Tong. Optimization of the cluster-head selection algorithm of an energy-based underwater acoustic sensor network[J]. Journal of Harbin Engineering University, 2017, 38(2): 282-287.
3 算法仿真与分析
4 结论
