无线传感网络中能耗均衡的混合通信算法研究.doc

第1期刘述钢等：无线传感网络中能耗均衡的混合通信算法研究17无线传感网络中能耗均衡的混合通信算法研究刘述钢，刘宏立，詹杰，王耀南(湖南大学 电气与信息工程学院，湖南 长沙 410082)摘 要：基于经典的低能耗自适应分簇算法(LEACH)，提出了一种能耗均衡的混合通信算法(EEHCA)。由基站根据节点剩余能量和簇头之间的距离选举簇头，节点用单跳模式和多跳模式交替与簇头进行通信且概率分别是p和1p，从而使簇头的分布更均匀，节点的负载更均衡。仿真结果表明该算法有效地平衡了节点的能量消耗，在延长生命周期方面明显好于LEACH。关键词：无线传感网络；分簇；负载均衡；能量有效中图分类号：TN92 文献标识码：A 文章编号：1000-436X(2009)01-0012-06Research of energy-efficient hybrid communication algorithm in wireless sensor networksLIU Shu-gang, LIU Hong-li, ZHAN Jie, WANG Yao-nan(College of Electrical and Information Engineering, Hunan University, Changsha 410082, China)Abstract: An energy-efficient hybrid communication algorithm (EEHCA) based on the classic low energy adaptive clustering algorithm (LEACH) was proposed. The cluster heads were selected in terms of residual energy of nodes and distance between cluster heads by base station. And sensor nodes communicate with cluster heads alternately with single hop mode and multi-hop mode. The probability of single hop mode was p and The probability of multi-hop mode was 1p. The hybrid communication mode obtained a more uniform distribution of cluster heads and balanced load of sensor nodes. The results of simulation show that the algorithm effectively balances the energy consumption of nodes. And the algorithm has been proposed is clearly better than LEACH in prolonging the lifetime of WSN.Key words: wireless sensor network; clustering; load-balanced; energy-efficient1 引言收稿日期：2008-06-21；修回日期：2008-12-10基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2007AA11A121）；国家自然科学基金资助项目（60775047）Foundation Items: The National High Technology Research and Development Program of China(863 Program) (2007AA11A121); The National Natural Science Foundation Program of China (60775047)无线传感器网络(wireless sensor network)是由大量体积小、成本低且具有传感、数据处理和无线通信能力的传感器节点组成。它的主要功能是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。由于其在军事、工业、家居、环境等诸多领域有着广阔的应用前景，WSN引起了各国政府和学者的广泛重视, 已成为最新的研究热点。无线传感器网络中关键技术之一是网络节点能量的节省，目前人们在延长网络的生命周期，降低节点功耗方面做了大量的研究。在文献1中，Heinzelman W R等提出的低功耗自适应分簇LEACH算法是通过随机轮转方式使各个节点选举为簇头，有效地节省了能量消耗，但簇内节点通过一跳通信将数据传送给簇头，簇头也通过一跳通信将聚合后的数据传送给基站，这样那些距离簇头远的节点会很快耗尽自己的能量，造成网络中还有大量的剩余能量没有被利用。文献2的TEEN算法和文献3的HEED算法都是以文献1为基础进行了改进，可是却没有考虑各个传感节点的负载均衡，这样会造成有些节点因负载过重而过早死亡。文献4采用多跳方式，从整个网络的能量消耗为出发点来延长网络的生命周期，文献5分析了节点在PHY层中延迟和协作方法，在系统的复杂性和能量消耗之间得出一个平衡关系。文献6, 7提出了传感节点在多播或单播自身数据的条件下，节约节点功耗的算法。文献8根据节点的能量供应、硬件、成本等物理代价，提出了在多跳无线传感网络中能量有效的组织方法，从而延长整个网络的生命周期。尽管以上文献提出的算法和策略有效地减小了能量的消耗，但是仍然存在一些不足：没有考虑簇头和簇内节点的负载均衡。本文提出一种能耗均衡的混合通信算法(EEHCA)，综合利用节点的剩余能量和簇头之间的距离选举簇头，同时，簇中节点以单跳和多跳模式且概率分别是p和1-p交替与簇头进行通信，单跳模式可以减少离簇头近的节点转发数据的负担，然而多跳模式可以减小离簇头远的节点的长距离通信的负担，这种混合通信模式有效地平衡各节点的能量消耗，最大化整个网络的生命周期。2 系统模型2.1 拓扑模型假设网络近似边长为A的正方形平面区域，是一个数据采集型无线传感网络, 有M个节点随机独立且均匀地分布于平面区域内，同时，节点不具备移动性，基站位于网络区域的中心。以节点剩余能量和节点之间的距离为考量对象进行簇头的选举，选择节点剩余能量较大且相互间距离大于或等于阈值D的m个节点为簇头，簇头与基站之间采用单跳通信而节点与簇头之间采用单跳和多跳混合通信的设计思想。网络中的簇可近似一个圆，其平均半径为a，。若在半径为a的区域内，有且只有一个簇头，既能保证簇的覆盖率，又可平衡簇的负载，图1是一个典型簇的结构，簇区域以通信距离R的厚度等分成n个环, 节点与簇头以概率P单跳通信，因此与簇头多跳通信的概率为1-P，以致簇内节点的能量消耗有效均衡。多跳时，环内的节点为环外节点提供数据转发服务，即第n个环内的节点要为来自第n个环外节点发送给簇头的数据包提供转发服务。为了保证簇的覆盖率和连通性，设，式中Q是常数,是为保证簇头能充分覆盖网络平面区域而设置。图1 典型簇的结构2.2 能量模型假设在每轮的数据采集期间，节点只发送一个自身采集的数据包给自己所在簇的簇头，同时与其他簇中任何节点都不进行数据信息通信。簇头对簇内节点进行管辖，接收簇中节点的采集数据包并对数据包进行有效融合，在一轮数据采集期间簇头节点只发送一个数据包给基站。为了便于计算，根据文献1中的能量损耗模型，作了如下的能量消耗的假设。：节点处理一个发送或接收数据包的能耗；：RF功率放大器及无线信道上所需能耗，为发送节点的功放系数，为发送的距离，为路径损耗因子，一般为24。同时假设每个簇头在进行各自的MAC和路由处理时，不考虑包碰撞和空闲监听时的能量消耗。传感节点发送一个数据包的能量消耗为(1)节点转发一个数据包的能量消耗为：，其中：, 。式(1)说明两节点相距较远时，直接传输数据耗能较大，采用多跳通信，则可节省能量消耗。3 分簇策略与LEACH算法一样，EEHCA算法的执行过程也是周期性的，每轮循环分为两个阶段：簇的建立阶段和稳定的数据通信阶段。为了降低资源开销，稳定阶段的持续时间远大于建立阶段的持续时间。每隔t（常数）轮进行一次簇头的选举，在第一轮选举簇头时，因各节点的初始能量一样，网络内所有节点把自己的位置信息发送给基站，基站把节点均匀分布的整个网络区域等分为个子区域，每个子区域即为一个簇，选举各个子区域的中心节点为簇头。其他轮簇头选举时，网络中各节点在选举轮的前一轮把自己的剩余能量信息发送给基站，基站运行相应的算法选出合适的簇头，其过程如下。1) 把各个簇中节点按剩余能量从大到小的顺序进行排序，即为其中，为簇中节点的个数。2) 选择所有簇中的第一个节点中剩余能量最大的节点为第一个簇头。3) 计算相邻簇中所有节点与已选所有簇头的距离，选择距离都大于或等于阈值且能量较大的节点作为簇头，其他的节点为非簇头节点。4) 重复第3步过程，簇中所有节点都选择完，就终止簇头的选举过程。通过以上过程，基站选择个节点作为簇头，并向网内节点广播一个包含簇与离簇头距离组的消息，节点接收到消息后将自身的ID与消息中包含的ID进行比较，如果相同，则该节点成为簇头。簇头节点发布通告消息告知整个网络，网络中的非簇头节点根据与离簇头距离决定从属的簇，并通知相应的簇头节点，完成簇的建立。簇头为每个簇内节点分配TDMA时间表，在稳定阶段，簇内节点按照TDMA表进行数据传输，簇头将收到的数据进行融合后发送给基站，稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一个循环的簇重构。4 簇内节点的能量均衡为了分析节点采用多跳模式与簇头通信的能量消耗，首先假定簇内节点被分成两部分，然后推广到跳。簇被分成两部分时，在离簇头通信距离的区域内的节点采用单跳，称该区域为临界区域，而靠近环的节点为临界节点，而临界区域外的节点采用多跳。因节点在网路中服从均匀分布，临界区域转发数据包的平均个数为，在一个数据采集周期（轮）内，能得到临界节点多跳时的能量消耗(2)很明显，如果，则，此时簇内节点与簇头直接通信，即为一个单跳簇，消除上式中的，得单跳通信的能量消耗为(3)可见，单跳通信是多跳通信的一种特例。现在分析簇区域中多跳时的能量消耗，如果簇中的节点与簇头直接通信，此时第环中临界节点能量消耗为(4)采用多跳通信时，簇内第环中节点在一轮的采集周期内平均转发的数据包数(5)由上式的第环中的临界节点在一轮的数据采集周期内的转发数据包的平均能量消耗(6)因此，多跳通信时簇中单个节点的平均能量消耗为(7)由式（4）可知，在单跳通信时，节点的能量消耗随单调递增函数，而由式（7）可知节点的能量消耗是随的单调递减的函数，单跳和多跳时的能量消耗见图2。 图2 单跳和多跳的节点平均能量消耗对比图2所示的是一个有25个节点均匀分布的簇，簇区域被等分成5个环且簇半径，很显然，在单跳或多跳模式通信时，节点离簇头距离的不同，消耗的能量有着相当大的差距，节点的能量消耗很不均衡。如果单纯地采用其中的一种模式，节点能量消耗是不均衡的，会造成有些节点过早死亡，从而影响整个网络的性能。综上所述，为了保证簇中节点能量消耗均衡，延长簇的生命周期，以致达到网络生命周期的延长，有必要采取单跳和多跳混合的方法来取得节点的能量消耗平衡。从图2也可以看出，要使节点的能量消耗平衡，只要考虑近端（）和远端（）节点的能量消耗，假设网络的生命周期共有轮数据采集周期，因此采用单跳和多跳混合通信方式时，节点的能量消耗为(8)假设(9)(10)(11)则近端节点的能量消耗(12)远端节点的能量消耗(13)显然，只要保证近端和远端节点的能量消耗无限接近时，簇的中节点的能量消耗才近似达到平衡，所以混合通信中概率p的函数为(14)如：， ，随单调递减，随p单调递增，当时，表示近端和远端节点的能量消耗基本平衡，此时的概率p为最佳(15)图3表示在p为最佳值时单跳、多跳和混合跳节点平均能量消耗对比图，很明显，采用混合跳的通信模式，簇中节点的能量消耗均衡性比单跳或多跳通信模式有了大大的改善，因此在簇头选举时可以适当增加轮数t，可以减小LEACH算法每轮都要进行簇头选举的通信能量，同时，簇的总能量消耗也比单跳模式减小。图3 单跳、多跳和混合跳节点平均能量消耗对比5 仿真与性能分析节点能源的高效使用是无线传感器网络能量有限特点的首要设计目标，因而，最大化网络生命周期是评价一个算法优劣的重要参数。仿真时用Matlab生成随机放在100m100m的范围内的100个节点，所有节点的初始能量是0.5J，每个数据包长2 000bit,节点能量为零时死亡。从簇内节点能耗均衡的分析过程可知，簇中不管采用的跳数为多大的值，都能找到一个最佳的概率p值，从而保证簇内节点的能量平衡，但是跳数增加，势必增加基站的路由控制的能量开销，因此在仿真时选择簇内跳数=3。为了评估混合通信算法，本文比较了在单跳、多跳和混合跳通信模式下的生命周期（以第一个节点的死亡时间作为网络生命周期）。图4是在阈值时的仿真，可以看出，簇头数小于11时，多跳时的生命周期比单跳的生命周期长，然而当簇头数目为12时，单跳与多跳的生命周期基本相当。如果采用混合通信模式，不管簇头数目是多少，生命周期比单跳或多跳模式都有较明显的改善，在簇头数目时，网络的生命周期达到最大。图4 单跳、多跳和混合跳的生命周期对比图5给出了在混合通信模式下阈值D对生命周期的影响，很显然，D=5R/4，生命周期较长。图5 阈值D对生命周期的影响图6中，选取簇头数目m=9，簇间阈值D=5R/4，仿真得到了分别采用EEHCA算法和LEACH算法时死亡节点随时间(轮数)变化的曲线。从两种算法的变化曲线可见，采用EEHCA算法的生命周期明显长于采用LEACH算法的生存时间，主要是因为单跳和多跳的混合通信算法使得节点能量消耗比较平衡，延长了整个网络的生命周期。图6 EEHCA与LEACH的死亡节点随时间变化的对比6 结束语本文针对LEACH等算法的不足，提出了能量有效的混合通信算法，减少单跳通信中离簇头节点远的节点和多跳通信中离簇头近的节点的能量消耗，确保节点能量消耗达到平衡。仿真结果证实EEHCA算法比LEACH算法能更有效地均衡节点能耗，明显延长了网络的生命周期。尽管EEHCA算法需要节点报告自己的剩余能量和位置信息，在一定程度上增加了通信代价，但是克服了LEACH算法每轮都要选举簇头的能量通信代价，总的来说EEHCA算法通信效率更高。参考文献：1HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networksA. Proceedings of the 33rd Annual Hawaii International Conference on System SciencesC. Maui: IEEE Computer Society, 2000. 3005-3014.2MANJESSHWAR A, GRAWAL D P. TEEN: a protocol for enhanced efficiency in wireless sensor networksA. Proc of the 15th Parallel and Distributed Processing SympC. San Francisco: IEEE Computer Society, 2001. 2009-2015.3YOUNIS O, FAHMY S. Heed: a hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks J. IEEE Trans onMobile Computing, 2004, 3(4): 660-669.4QIAN Y, ZHOU J F, CHEN K S. Prolonging the lifetime of wireless sensor network via multihop clusteringA. NEW2AN 2006C. LNCS 4003, 2006. 118-129.5CHEN Z Z, YANG C Y. Energy efficiency of cooperative diversity at PHYLayer in wireless sensor networksA. The 8th International Conference on Signal ProcessingC. 2006. 16-20.6PARK J, SAHNI S. Maximum liftetime broadcasting in wireless networksJ. IEEE Transaction on Computers, 2005, 54(9): 1081-1090.7DAGHER J C, MARCELLIN M W. A theory for maximizing the lifetime of sensor networksJ. IEEE Transaction on Communications, 2007, 55(12):323-332.8JIN Z, PAPAVASSILIOU S. On the energy-efficient organization and the lifetime of multi-hop sensor networksJ. IEEE Communication Letters, 2003, 7(11): 537-539.9LIOYD E L, GUOLIANG X. Relay node placement in wireless sensor networksJ. IEEE transactions on Computers, 2007, 56(1):134-138.作者简介：刘述钢（1978-），男，湖南邵阳人，湖南大学博士生，主要研究方向为新型无线传感网络的能量有效算法、用户检测、快速路由算法。刘宏立（1963-），男，湖南常德人，湖南大学教授、博士生导师，主要研究方向为现代通信理论和无线传感网络新技术，移动通信系统与软件无线电。詹杰（1973-），男，湖南常德人，湖南大学博士生，主要研究方向为新型无线传感网络的能量有效算法、定位算法、快速路由算法。王耀南（1957-），男，江西吉安人，湖南大学电气与信息工程学院教授、博士生导师、院长，主要研究方向为智能控制理论与机器人技术、图像识别理论与机器视觉技术。（上接第11页）9KIM J, KIM G, LEE S, et al. Related-key attacks on reduced rounds of SHACAL-2A. 5th International Conference on Cryptology in IndiaC. Chennai (Madras), India, 2004. 175-190.10LU J, LEE C, KIM G, K