Computer Engineering and Applications 计算机工程与应用
2016，52（7）1引言无线传感器网络（Wireless Sensor Networks ，WSN ）是由部署在检测区域内的大量集数据采集、处理及通信功能于一体的微型传感器节点组成的无线网络[1]。WSN 不需要固定基础设施的支持，具有自组织、动态拓扑、快速展开等特点，被广泛应用于军事国防、工业监控、智能家居、精细农业等领域[2-4]。然而，一般情况下，传感器节点计算、存储、通信能力以及能量都十分有限，这使得传统的网络路由协议不能适用于WSN [5]。因此，研究和设计满足无线传感器网络特殊性能要求的通信路由协议一直是WSN 迫切需要解决的问题之一。现有的路由协议主要分为平面路由协议[6]和分簇路由协议[7]。分簇路由协议具有能量利用高效、可扩展性好、数据融合简单等特点，已成为WSN 重点研究的路由技术。
LEACH [7]协议是最早提出的也是最为经典的无线传感器网络分簇路由协议，后来的很多分簇路由协议都是在它的基础上发展而来的，例如HEED 协议、UCS 协议、EEUC 协议等。尽管这些协议都有效地均衡了节点的能量损耗，但同时也存在一定的不足。例如，LEACH 协议簇首选择的随机性，容易造成簇首分布不均匀，簇首采用单跳的方式直接与基站进行通信，加速了远离基站的节点的死亡速度；HEED [8]协议克服了LEACH 协议簇首选择的随机性，在簇首选择时考虑到节点的剩余能量和簇内通信代价，但在建簇时消息迭代次数比较多，由此带来的通信开销也比较大；UCS [9]协议采用簇首与基站多跳通信的方式来降低簇首节点的单跳通信能耗一种能量高效的非均匀分簇算法
张长森，邢娟，赵尚卿
ZHANG Changsen,XING Juan,ZHAO Shangqing
河南理工大学计算机科学与技术学院，河南焦作454000
School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China
ZHANG Changsen,XING Juan,ZHAO Shangqing.Energy-efficient uneven clustering https://www.doczj.com/doc/7116511100.html,puter Engi-neering and Applications,2016,52（7）：106-109.
Abstract ：In order to address the issue of the energy consumption unbalance in wireless sensor networks,an energy-efficient uneven clustering algorithm is proposed.The new algorithm adopts cluster head election strategy based on the residual energy of nodes,and a cluster head employs the thought of unequal clustering to build a cluster.When building the inter-cluster routing tree,cluster heads take into consideration the adjacent cluster heads ’residual energy,the number of cluster members,the relative distance to itself and the relative distance to base station.Simulation results show the algo-rithm can effectively balance the network energy consumption and prolong the lifetime of the network.
Key words ：wireless sensor networks;energy-efficient;uneven clustering;inter-cluster routing tree
摘要：针对无线传感器网络中的能量消耗不均衡问题，提出一种能量高效的非均匀分簇算法——EUCA 。算法采取基于节点剩余能量的簇首选举策略，簇首采用非均匀分簇的思想来构建大小不等的簇，在构建簇间路由树时，综合考虑了邻近簇首的剩余能量、簇成员数目、相对自身的距离和相对基站的距离，以此来均衡簇首能量损耗。仿真结果表明，该算法有效均衡了网络能量损耗，延长了网络的生存周期。
关键词：无线传感器网络；能量高效；非均匀分簇；簇间路由树
文献标志码：A 中图分类号：TP393doi ：10.3778/j.issn.1002-8331.1405-0123
基金项目：国家自然科学基金（No.51174263）；教育部博士点基金（No.20124116120004）；河南省教育厅科学技术研究重点项目
（No.12B510011，No.12A520022）；河南理工大学博士基金（No.B2013-036）。
作者简介：张长森（1969—），男，博士，教授，主要研究方向：矿井监控与通信、无线传感器网络；邢娟（1987—），女，硕士研究生，研
究领域为无线传感器网络，E-mail ：zsxjbtxl@https://www.doczj.com/doc/7116511100.html, ；赵尚卿（1988—），男，硕士研究生，研究领域为无线协作通信。
收稿日期：2014-05-12修回日期：2014-07-04文章编号：1002-8331（2016）07-0106-04
CNKI 网络优先出版：2014-12-11,https://www.doczj.com/doc/7116511100.html,/kcms/detail/11.2127.TP.20141211.1522.015.html
106
基于粒子群优化的非均匀分簇路由算法 摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所 提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。 关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化算法；能量消耗；生存期 中图分类号: tp393.07 文献标志码:a abstract: to deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of wireless sensor network (wsn), the paper designed an uneven clustering routing algorithm based on adaptive particle swarm optimization (pso). firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. then this paper introduced the pso according to the cluster size. the pso was used to select the final cluster heads by
ＩＳＳＮ１０００．９８２５．ＣＯＤＥＮＲＵＸＵＥＷ ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，Ｖ０１．１７，Ｎｏ．７，Ｊｕｌｙ２００６，ＰＰ．１５８８—１６００ ＤＯＩ：１０．１３６０／ｊｏｓｌ７１５８８ ＠２００６ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ．Ａｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ． 无线传感器网络分簇路由协议水 沈波＋，张世永，钟亦平 （复旦大学计算机与信息技术系，上海２００４３３） Ｃｌｕｓｔｅｒ－ＢａｓｅｄＲｏｕｔｉｎｇＰｒｏｔｏｃｏｌｓｆｏｒ ＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋｓ ＳＨＥＮＢｏ＋，ＺＨＡＮＧＳｈｉ—Ｙｏｎｇ，ＺＨＯＮＧＹｉ—Ｐｉｎｇ （ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｉｎｇａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＦｕｄａｎＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００４３３，Ｃｈｉｎａ） ＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｐｈｎ：＋８６—２１—６５６４３２３５，Ｅ—ｍａｉｌ：０４２０２１１６５＠ｆｕｄａｎ．ｅｄｕ．ｃａ，ｈｔｔｐ：／／ｗｗｗ．ｆｕｄａｎ．ｅｄｕ．ｃａ Ｅ－ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｃｎｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃａＴ乩，Ｆａｘ：＋８６．１０—６２５６２５６３ ＳｈｅｎＢ，ＺｈａｎｇＳＹ，ＺｈｏｎｇＹＰ．Ｃｌｕｓｔｅｒ－Ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２００６，１７（７）：１５８８—１６００．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００－９８２５／１７／１５８８．ｈｔｍ Ａｂｓｔｒａｃｔ：Ｒｏｕｔｉｎｇｔｅｃｈｎｏｌｏｇｙａｔｔｈｅｎｅｔｗｏｒｋｌａｙｅｒｉｓｐｉｖｏｔａｌｉｎｔｈｅａｒｃｈｉｔｅｃｔｕｒｅｏｆｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ．Ａｓａｎａｃｔｉｖｅｂｒａｎｃｈｏｆｒｏｕｔｉｎｇｔｅｃｈｎｏｌｏｇｙ，ｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓｅｘｃｅｌｉｎｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｍａｎａｇｅｍｅｎｔ，ｅｎｅｒｇｙｍｉｎｉｍｉｚａｔｉｏｎ，ｄａｔａａｇｇｒｅｇａｔｉｏｎａｎｄＳＯｏｎ．Ｉｎｔｈｉｓｐａｐｅｒ，ｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｍｅｃｈａｎｉｓｍｓｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓａｒｅａｎａｌｙｚｅｄ．Ｃｌｕｓｔｅｒｈｅａｄｓｅｌｅｃｔｉｏｎ，ｃｌｕｓｔｅｒｆｏｒｍａｔｉｏｎａｎｄｄａｔａｔｒａｎｓｍｉｓｓｉｏｎａｒｅｔｈｒｅｅｋｅｙｔｅｃｈｎｉｑｕｅｓｉｎｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓ．Ａｓｖｉｅｗｅｄｆｒｏｍｔｈｅｔｈｒｅｅｔｅｃｈｎｉｑｕｅｓ，ｒｅｃｅｎｔｒｅｐｒｅｓｅｎｔａｔｉｖｅｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌｓａｒｅｐｒｅｓｅｎｔｅｄ，ａｎｄｔｈｅｉｒｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ａｎｄａｐｐｌｉｃａｔｉｏｎａｒｅａｓａｒｅｃｏｍｐａｒｅｄ．Ｆｉｎａｌｌｙ，ｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｉｓｓｕｅｓｉｎｔｈｉｓａｒｅａａｒｅｐｏｉｎｔｅｄｏｕｔ． Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋ；ｃｌｕｓｔｅｒ－ｂａｓｅｄｒｏｕｔｉｎｇｐｒｏｔｏｃｏｌ；ｃｌｕｓｔｅｒ；ｃｌｕｓｔｅｒｈｅａｄ 摘要：在无线传感器网络体系结构中，网络层的路由技术至关重要．分簇路由具有拓扑管理方便、能量利用高效、数据融合简单等优点，成为当前重点研究的路由技术．分析了无线传感器网络分簇路由机制，着重从簇头的产生、簇的形成和簇的路由角度系统地描述了当前典型的分簇路由算法，并比较和分析了这些算法的特点和适用情况．最后结合该领域当前研究现状，指出分簇路由算法未来的研究重点． 关键词：无线传感器网络；分簇路由协议；簇；簇头 中图法分类号：ＴＰ３９３文献标识码：Ａ 作为一种新的信息获取方式和处理模式，无线传感器网络（ｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋ，简称ＷＳＮ）Ⅲ目前已成为国内外备受关注的研究热点． 作为一种典型的普适计算（ｐｅｒｖａｓｉｖｅｃｏｍｐｕｔｉｎｇ）应用，ＷＳＮ通过大量部署在监测区域内的传感器节点，采集网络覆盖区域内感知对象的信息，通过多跳的无线通信方式，将收集、处理后的信息提供给终端用户．ＷＳＮ不需要固定的网络支持，具有快速展开、抗毁性强等特点，可广泛应用于军事侦察、环境监测、医疗监护、农业养殖和其他商业领域，以及空间探索和灾难抢险等特殊领域【２，３】． ?Ｒｅｃｅｉｖｅｄ２００５—１２—２０；Ａｃｃｅｐｔｅｄ２００６—０２—２３
2017，53（10）1引言认知无线电使得未经授权的次用户主动地寻找无线电环境中的空闲频谱资源，并在不对授权的主用户产生干扰的情况下使用这些空闲频谱[1-2]。根据网络的拓扑结构，认知网络可以分为集中式网络和分布式网络。在分布式网络中，由于缺少中心节点的支持，次用户间进行数据传输之前需要使用公共控制信道（Common Control Channel ，CCC ）交换彼此的控制信息[3-5]，之后再切换到协商好的信道上进行数据传输。分布式网络架构简单，但节点间需要额外的开销来协调信道的使用。集中式网络按照一定的准则划分为若干个簇，簇内共享一条信道作为CCC ，中心（簇首）节点控制着网络中所有的节点，并协调网络资源的分配，它的 主要职责包括：功率管理、频率管理和调度控制。 目前已经提出了多种认知网络分簇算法。文献[6]提出了一种机会分簇算法，称为SOC 算法。该算法将 分簇问题看作是一个最大化边缘图的问题，它的分簇算法要求簇内有尽可能多的共同可用信道以应对频谱的浮动变换，尽量保持簇结构的稳定。不足之处在于该算法产生了大量的簇，且簇的规模很小。文献[7]提出了一种分布式的分簇算法，称为CogMesh 算法。该算法描述了邻居节点发现机制、簇的形成机制以及分簇之后的网络拓扑管理。当一个新的节点加入到认知网络中时，该算法仅是简单地让它加入到它所遇到的第一个簇。集中式认知网络分簇算法研究 李晓艳，雷斌，郭锦 LI Xiaoyan,LEI Bin,GUO Jin 西安工业大学电子信息工程学院，西安710021 School of Electronic Information Engineering,Xi ’an Technological University,Xi ’an 710021,China LI Xiaoyan,LEI Bin,GUO Jin.Research on clustering algorithm for centralized cognitive radio https://www.doczj.com/doc/7116511100.html,-puter Engineering and Applications,2017,53（10）：117-123. Abstract ：Following some rules,the Cognitive Radio Networks （CRNs ）can be divided into several clusters,each cluster has a Common Control Channel （CCC ）to exchange control information.The cluster-based CCC is one of the solutions to the problem in spectrum sharing for CRNs.According to the characteristics of idle channel in CRNs,a new clustering algorithm is proposed,with the aim of maximizing the cluster throughput and maintaining the cluster stability,considers three factors:available channels,geographical position and database statistics is proposed.Then,several cluster maintenance issues are discussed.Simulation results reveal that the proposed clustering algorithm generates small number of clusters in the network,and can maintain the stability of network topology by reducing the reclustering times. Key words ：cognitive radio;centralized network;spectrum sharing;clustering 摘要：认知网络按照一定的准则划分为若干个簇，簇内共享一条信道用于交换控制信息，这种以分簇的方式实现按区域共享信道是认知无线电频谱共享问题的解决方法之一。针对认知网络空闲信道的特性，提出了一种考虑可用信道、地理位置以及数据库统计值的新的分簇算法，该算法以最大化簇内吞吐量和维持簇结构稳定为设计目的；讨论了几个关键的簇维护和管理问题。仿真结果表明，提出的分簇算法在产生的簇总数量以及簇的重构次数上可以获得一个较好的综合性能。 关键词：认知无线电；集中式网络；频谱共享；分簇 文献标志码：A 中图分类号：TN929.5doi ：10.3778/j.issn.1002-8331.1608-0419 基金项目：陕西省科技厅资助项目（No.2015GY041）；陕西省教育厅科研计划项目资助（No.15JK1346）；国家自然科学基金面上项目 （No.61271362）。 作者简介：李晓艳（1982—），女，博士，讲师，研究领域为认知无线电频谱共享，E-mail ：lixiao_sky@https://www.doczj.com/doc/7116511100.html, ；雷斌（1966—），男，副 教授，研究领域为自组织网络；郭锦（1980—），女，博士，讲师，研究领域为计算机网络。 收稿日期：2016-08-22修回日期：2016-11-07文章编号：1002-8331（2017）10-0117-07 Computer Engineering and Applications 计算机工程与应用 117 万方数据
基于最小生成树的非均匀分簇路由算法 摘要:发现现有的针对非均匀分簇路由算法没有充分考虑簇首 与基站之间最优路径选择,而导致传输路径上的能量消耗不均衡的问题。为了更好地均衡传输路径上节点能量的消耗,提出了基于最小生成树的非均匀分簇的路由算法。该算法利用节点剩余能量和节点到基站的距离选举簇首,然后通过建立最小生成树搜寻最优传输路径,这样可以减少传输路径上的能量消耗,有效地解决能耗不均 衡问题。理论分析和实验结果均表明,该算法无论在存活节点个数还是在能量消耗上都明显优于eeuc算法和ebca。 关键词: 簇首;非均匀分簇;不均衡;剩余能量;最小生成树 uneven clustering routing algorithm based on minimum spanning tree zhang ming cai*, xue an rong, wang wei ( school of computer science and telecommunication engineering, jiangsu university, zhenjiang jiangsu 212013, china ) abstract:
the existing uneven clustering routing algorithms do not consider the optimal path selection between cluster heads and base station, which leads to unbalanced energy consumption. in order to balance energy consumption of transmission paths, this paper proposed an uneven clustering routing algorithm based on minimum spanning tree. the algorithm utilized residual energy of nodes and the distance between nodes and base station to select cluster heads, and then generated minimum spanning tree to search the optimal transmission paths, which reduced energy consumption on the transmission paths and effectively solved unbalanced energy consumption. the theoretical analysis and experimental results show that the algorithm is better than the existing energy efficient uneven clustering (eeuc) and energy balancing clustering algorithm (ebca) in terms of the number of live nodes and energy consumption. key words: cluster head; uneven clustering; unbalanced; residual energy; minimum spanning tree 0 引言 无线传感器网络(wireless sensor network, wsn)作为新兴的网
第7卷 第3期2010年6月 铁道科学与工程学报 J OURNAL OF RA I LWAY SC I ENCE AND ENG I NEER I NG Vo l 7 No 3 June2010 基于AR MA流量预测的WSN非均匀分簇 双簇头选择算法 李 飞,樊晓平,刘少强,陈志杰 (中南大学信息科学与工程学院,湖南长沙410075) 摘 要:在无线传感器网络中引入双簇头机制可以用副簇头承担数据转发任务,能有效地分担主簇头的负载。但由于簇与簇的中继不同,转发簇头在不同时刻承担的转发任务不同,为此,有针对性地提出一种基于ARM A流量预测的W SN非均匀分簇双簇头选择算法,即AUDC算法,主簇头利用预测机制,根据簇内节点剩余能量选择副簇头。研究结果表明:采用该算法有效地延长了网络的生存周期,实现了网络的负载均衡。 关键词:无线传感器网络;双簇头;流量预测 中图分类号:TP393 文献标志码:A 文章编号:1672-7029(2010)03-0124-05 The algorith m of choosing t he uneven clustering double cluster heads inW S N based on AR MA traffic prediction L I Fe,i FAN X iao p i n g,L IU Shao qiang,C H EN Zh i jie (S chool of In for m ation S ci en ce and E ngi neeri ng,C entral South U nivers it y,Changs h a410075,Ch i na) Abst ract:I n w ireless sensor net w ork,there is an effecti v e l y a l g orithm called double cl u ster heads m echan is m w hich can share the burden ofm a i n cluster by usi n g v ice-c l u ster to take on t h e data s w itching.Because d iffer ent c l u sters have d ifferent relays and trans m itti n g tasks,ai m ed at t h e prob le m,the a l g orithm o f choosi n g the une ven clusteri n g double cl u ster heads inW SN based on AR MA tra ffic pred iction w as proposed.Itm eans t h atm ai n cluster can rep lace the v ice-c l u ster by usi n g forecasting m echanis m according to residua energy of the nodes. The resu lt sho w s t h at the ne w a l g orithm can pr o long t h e net w ork lifecyc le effective ly and ach ieve the load ba lan cing i n the net w o r k. K ey w ords:w ire l e ss sensor net w ork;doub le cluster heads;tra ffi c pred iction 随着微电子技术、嵌入式技术、通信技术和传感器技术的飞速发展,无线传感器网络(W SN)已引起社会极大的关注。随着无线传感器网络的深人研究和广泛应用,无线传感器网络将逐渐深入到人类生活的各个领域[1],例如国防军事、国家安全、环境监测、交通管理、医疗卫生、制造业、反恐抗灾等领域,由于传感器节点往往随机部署在恶劣的环境中,采用电池供电,且不能再次充电,能量消耗成为传感器网络正常运用的一大瓶颈。一个合理有效的路由协议,可以很好地节省传感器节点的能量消耗,而分层路由协议研究也成为当前研究的热点之一。这类协议的主要是通过分簇来实现的,选择簇头[2-3]成为分簇协议的基础,将全网无线传感器节点分成若干个簇,簇内普通节点负责采集用户感兴趣信息,并将数据传递给簇头,簇头节点将数据进行数据融合后发送给基站节点。这样,普通节点只需要负责数据收集,聚合及转发任务由簇头节点承担。分簇路由协议的优点主要有: (1)由于数据的转发均由簇头承担,极大地减少了W SN节点的通信能耗,且能量消耗均匀,有效延长了网络寿命。 (2)网络扩展能力强,鲁棒性能优越,能够适 *收稿日期:2010-04-08 基金项目:国家自然科学基金资助项目(60870010;60776834) 作者简介:李 飞(1984-),男,江苏徐州人,硕士研究生,从事信息与通信工程的研究
———————————— 作者简介作者简介：：李 辉(1976－)，男，副教授，主研方向：无线传感器网络；刘书吉，硕士研究生。 收稿日期收稿日期：：2013-03-04 修回日期修回日期：：2013-04-18 E-mail ：li20042007@https://www.doczj.com/doc/7116511100.html, 基于节点度和距离的WSN 分簇路由算法 李 辉，刘书吉 (河南理工大学电气工程与自动化学院，河南 焦作454000) 摘 要：针对无线传感器网络(WSN)中节点的负载均衡问题，提出一种基于节点度和距离的WSN 非均匀分簇路由算法。该算法在首轮成簇时采用了定时机制的簇头竞争方案，定时的长短取决于节点本身的节点度和距离基站的距离，且节点根据不同的竞争半径形成不同的簇。在首轮成簇结束后，簇的结构不再发生变化，而簇头的轮换则根据簇内节点的剩余能量和距离本簇质心的通信代价在簇内进行动态轮换。采用簇间多跳路由，根据节点的剩余能量、距离基站的距离、节点间通信代价和节点的转发热度来选择中继节点。仿真结果表明，该算法的网络生命周期与LEACH 协议相比延长了2倍以上，与EEUC 协议相比延长了13.97%，且均衡了网络的能量消耗。 关键词关键词：：无线传感器网络；非均匀分簇；节点度；距离；转发热度；动态轮换 Clustering Routing Algorithm Based on Node Degree and Distance for Wireless Sensor Networks LI Hui, LIU Shu-ji (School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo 454000, China) 【Abstract 】Aiming at the problem of unnecessary energy consumption caused by periodic clustering and the load balance problem in the Wireless Sensor Networks(WSN), an Unequal Clustering routing algorithm based on node Degree and Distance for WSN(UCDD) is proposed. UCDD algorithm adopts the time competitive mechanism in the first round of clustering. The length of time depends on the nodes’ node degree and the distance from the base station, and different clusters are formed according to the different radius of competition. After the first round, the clusters’ structure does not change any more. Cluster head dynamically choose next cluster head according to the residual energy and the communication costs. Inter-cluster multihop routing is used in UCDD algorithm, and the relay node is selected according to node residual energy, distance from the base station, communication cost of nodes and relay hot. Simulation results show that the algorithm can prolong the networks lifetime by more than two times compared with LEACH protocol and by 13.97% compared with EEUC protocol. Besides, it balances the energy dissipation of the networks. 【Key words 】Wireless Sensor Networks(WSN); unequal clustering; node degree; distance; relay heat; dynamic rotation DOI: 10.3969/j.issn.1000-3428.2014.03.023 计 算 机 工 程 Computer Engineering 第40卷 第3期 V ol.40 No.3 2014年3月 March 2014 ·移动互联与通信技术移动互联与通信技术·· 文章编号文章编号：：1000-3428(2014)03-0113-07 文献标识码文献标识码：：A 中图分类号中图分类号：：TP391 1 概述 无线传感器网络(Wireless Sensor Networks, WSN)是继互联网之后的又一个对人类生活产生重大影响的IT 技术[1]。由于传感器节点的能量受限，因此基于分层的路由协议备受关注。基于概率的低功耗自适应分簇协议(Low-energy Adaptive Clustering Hierarchy, LEACH)[2]是最早的分簇路由协议，几乎贯穿了后来发展的大多数分簇协议。该协议通过等概率随机循环地选择簇头以此来将整个网络的能量负载平均分配到每个传感器节点上，从而达到降低网络能量耗费、延长网络生命周期的目的[3]。LEACH 协议成簇时簇首选择方法简单，易于实现。但是，LEACH 协议的缺点也非常明显：(1)在簇头选择时没有考虑能量因素，无论节点 的剩余能量多少都有可能成为簇头，从而加速了低能量节点的死亡；(2)簇头分布不均；(3)在数据传输时采用了单跳模式数据传输，当传输相同的数据时距离基站远的簇头的节点能耗较快。文献[4]的HEED 算法在簇头选择时依据主参数能量和次参数簇内通信代价，其分簇速度更快，并且产生的簇头分布比较均匀、网络的拓扑结构也更加合理。但是在成簇时通信开销大。文献[5]提出的最小ID 分簇算法，方法简单易行。但是在成簇时需要相互交换ID 号，带来很大的能量开销，并且选择的簇头分布不太均匀。文献[6]提出的集中式分簇算法(LEACH-C)，每轮结束时将能量信息和位置信息发送给基站，由基站来选择簇头。虽然解决了簇头分布不均问题，但是每轮都要发送能量和位置信息浪费了大量的能量。文献[7]提出的基于竞争的非均匀分簇
Computer Engineering and Applications 计算机工程与应用 2016，52（7）1引言无线传感器网络（Wireless Sensor Networks ，WSN ）是由部署在检测区域内的大量集数据采集、处理及通信功能于一体的微型传感器节点组成的无线网络[1]。WSN 不需要固定基础设施的支持，具有自组织、动态拓扑、快速展开等特点，被广泛应用于军事国防、工业监控、智能家居、精细农业等领域[2-4]。然而，一般情况下，传感器节点计算、存储、通信能力以及能量都十分有限，这使得传统的网络路由协议不能适用于WSN [5]。因此，研究和设计满足无线传感器网络特殊性能要求的通信路由协议一直是WSN 迫切需要解决的问题之一。现有的路由协议主要分为平面路由协议[6]和分簇路由协议[7]。分簇路由协议具有能量利用高效、可扩展性好、数据融合简单等特点，已成为WSN 重点研究的路由技术。 LEACH [7]协议是最早提出的也是最为经典的无线传感器网络分簇路由协议，后来的很多分簇路由协议都是在它的基础上发展而来的，例如HEED 协议、UCS 协议、EEUC 协议等。尽管这些协议都有效地均衡了节点的能量损耗，但同时也存在一定的不足。例如，LEACH 协议簇首选择的随机性，容易造成簇首分布不均匀，簇首采用单跳的方式直接与基站进行通信，加速了远离基站的节点的死亡速度；HEED [8]协议克服了LEACH 协议簇首选择的随机性，在簇首选择时考虑到节点的剩余能量和簇内通信代价，但在建簇时消息迭代次数比较多，由此带来的通信开销也比较大；UCS [9]协议采用簇首与基站多跳通信的方式来降低簇首节点的单跳通信能耗一种能量高效的非均匀分簇算法 张长森，邢娟，赵尚卿 ZHANG Changsen,XING Juan,ZHAO Shangqing 河南理工大学计算机科学与技术学院，河南焦作454000 School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China ZHANG Changsen,XING Juan,ZHAO Shangqing.Energy-efficient uneven clustering https://www.doczj.com/doc/7116511100.html,puter Engi-neering and Applications,2016,52（7）：106-109. Abstract ：In order to address the issue of the energy consumption unbalance in wireless sensor networks,an energy-efficient uneven clustering algorithm is proposed.The new algorithm adopts cluster head election strategy based on the residual energy of nodes,and a cluster head employs the thought of unequal clustering to build a cluster.When building the inter-cluster routing tree,cluster heads take into consideration the adjacent cluster heads ’residual energy,the number of cluster members,the relative distance to itself and the relative distance to base station.Simulation results show the algo-rithm can effectively balance the network energy consumption and prolong the lifetime of the network. Key words ：wireless sensor networks;energy-efficient;uneven clustering;inter-cluster routing tree 摘要：针对无线传感器网络中的能量消耗不均衡问题，提出一种能量高效的非均匀分簇算法——EUCA 。算法采取基于节点剩余能量的簇首选举策略，簇首采用非均匀分簇的思想来构建大小不等的簇，在构建簇间路由树时，综合考虑了邻近簇首的剩余能量、簇成员数目、相对自身的距离和相对基站的距离，以此来均衡簇首能量损耗。仿真结果表明，该算法有效均衡了网络能量损耗，延长了网络的生存周期。 关键词：无线传感器网络；能量高效；非均匀分簇；簇间路由树 文献标志码：A 中图分类号：TP393doi ：10.3778/j.issn.1002-8331.1405-0123 基金项目：国家自然科学基金（No.51174263）；教育部博士点基金（No.20124116120004）；河南省教育厅科学技术研究重点项目 （No.12B510011，No.12A520022）；河南理工大学博士基金（No.B2013-036）。 作者简介：张长森（1969—），男，博士，教授，主要研究方向：矿井监控与通信、无线传感器网络；邢娟（1987—），女，硕士研究生，研 究领域为无线传感器网络，E-mail ：zsxjbtxl@https://www.doczj.com/doc/7116511100.html, ；赵尚卿（1988—），男，硕士研究生，研究领域为无线协作通信。 收稿日期：2014-05-12修回日期：2014-07-04文章编号：1002-8331（2016）07-0106-04 CNKI 网络优先出版：2014-12-11,https://www.doczj.com/doc/7116511100.html,/kcms/detail/11.2127.TP.20141211.1522.015.html 106
总第246期2010年第4期 计算机与数字工程 Computer&Digital Engineering Vol.38No.4 49 基于L EACH的无线传感器网络分簇路由算法3 白凤娥 牟汇慧 姜晓荣 (太原理工大学计算机与软件学院 太原 030024) 摘 要 路由协议是无线传感器网络的重要组成部分之一,而路由算法在路由协议中起着至关重要的作用。文章在L EACH算法基础上,提出一种改进的路由算法,改进后的算法采用相对固定的成簇方式,每隔一轮重新构建簇。利用图论中的prim算法,选择每轮中P ed最大的簇头作为根节点,在簇头节点之间构造树形路由,簇头之间以多跳方式将收集到的数据发送到根节点,然后通过根节点将整个网络收集到的数据发送到基站。仿真结果表明,与L EACH算法相比,改进算法降低了能耗,有效延长了网络生存周期。 关键词 无线传感器网络;L EACH算法;分簇;生命周期 中图分类号 TP393 L EACH2Based Clustering Routing Algorithm for Wireless Sensor Networks Bai Fe ngπe M ou Huihui J ia ng Xiaorong (College of Computer and Software,Taiyuan University of Technology,Taiyuan 030024) Abs t rac t Routing protocol is an important part of wireless sensor network and the routing algorithm plays a crucial role in the routing protocol.Based on L EACH algorithm,this paper presents a novel clustering algorithm in which clusters are relatively fixed and the nodes re2organize themselves into new clusters every other round.It utilizes the Prim algorithm in the graph theory to form tree routing among cluster2head nodes,and selects the cluster2head with the largest P ed as the root node.The cluster heads send data to the root node in a multi2hop manner and the root node then sends the gathered data by the whole network to the base station.Simulation results show that compared with L EACH,the improved algorithm can re2 duce the energy consumption and prolong the lifetime of the network. Ke y Words wireless sensor network,L EACH algorithm,clustering,lifetime Class Nu m ber TP393 1 引言 无线传感器网络(Wireless Sensor Network,简称WSN)是监视远程环境的有力工具之一,它的基本功能是收集并返回传感器节点所在监测区域的信息。由于工作环境和自身构造的限制,传感器节点一般是电池供电,并且节点的更换和充电也较难实现。因此,降低节点能耗,延长网络生命周期是无线传感器网络传输机制的一个主要研究目标[1]。 网络数据传输离不开路由协议,路由协议对网络的整体性能有重要影响,因此,作为无线传感器网络核心技术之一的路由协议一直是研究的热点。路由算法在路由协议中起着至关重要的作用,无线传感器网络中的路由算法从网络逻辑结构角度可以分为平面路由和层次路由。层次路由算法是无线传感器网络路由算法的研究重点,其中,L EAC H 算法[2～3]是比较具有代表性的层次型路由算法。 本文在L EAC H算法的基础上,介绍一种改进的路由算法,改进算法的成簇方式相对固定,减少了构造簇的能量消耗。簇形成之后,在簇头间构造最小生成树,簇间通过多跳方式通信,降低了簇头节点之间长距离通信的能耗。 3收稿日期:2009年11月2日,修回日期:2009年12月5日 作者简介:白凤娥,女,教授,硕士生导师,研究方向:计算机控制与嵌入式系统,无线传感器网络。牟汇慧,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。姜晓荣,女,硕士研究生,研究方向:嵌入式系统与无线自组网络。
51 高精度AOA 分簇定位算法 黄琦1，黄海1,谢冬青2 （1.广州大学数学与信息科学学院，广东广州 510006；2.广州大学计算机科学与教育软件学院，广东广州510006） 摘 要：如今的网络安全主要联系于无线传感网络，定位算法的优劣决定了无线传感网络的 能力，也就决定了网络安全的能力。分簇定位算法具有能量效率高、可扩展性好、简单可行的优点， 但是分簇算法属于一种模糊定位算法，不具有较高的精度。此外，分簇算法的簇首替换如果在 全局范围内进行选择，很容易造成高消耗。AOA(angle of arrival)算法在复杂环境中具有精确的定 位能力。文章通过运用AOA 测距算法，使分簇算法的每个节点具有自探测能力，通过节点相对 夹角，用坐标算法算出相应于簇首的坐标。为了让能量消耗低于普通分簇算法，文章根据完全 图中能量有效原理，让分簇只在初始时进行一次，在每个簇内无簇首或能量低时，对簇首进行 重选举，再将信息发送给总簇。Matlab 仿真实验表明，文章算法实现了range-based 的分簇定位 算法，且保留了快速部署、能量效率高、高精度的优点。根据实验，文章算法适用于不松散部 署的无线传感网络。 关键词：无线传感网络；AOA 算法；分簇算法；定位算法 中图分类号：TP309 文献标识码： A 文章编号：1671-1122（2014）12-0051-05 中文引用格式：黄琦，黄海,谢冬青. 高精度AOA 分簇定位算法 [J].信息网络安全，2014，（12）:51-55. 英文引用格式：HUANG Q, HUANG H, XIE D Q. A Novel AOA Clustering-based Localization Algorithm with High Accuracy [J].Netinfo Security,2014,(12):51-55. A Novel AOA Clustering-based Localization Algorithm with High Accuracy HUANG Qi 1, HUANG Hai 1, XIE Dong-qing 2 (1. Guangzhou University Mathematics and Information Science College,Guangzhou Guangdong 510006,China;2. Guangzhou University Computer Science and Educational Software College,Guangzhou Guangdong 510006,China )Abstract: Nowadays, network security mostly connects to wireless sensor network (WSN), the ability of WSN rests with the quality of the localization algorithm. Clustering localization algorithm is efficient, highly scalable, simple and practical algorithm, but it is also a fuzzy match algorithm which does not have high accuracy. If cluster-head switch of clustering algorithm is done within the global nodes, it will cause large amount of energy waste. The AOA algorithm has good localization ability under complex environment. In this paper, by using the AOA algorithm, every node has the ability of self-detection and can calculate the coordinates relative to cluster-head with coordinate algorithm by using node relative-angle. In order to reduce energy waste, this paper designs a algorithm base upon energy-efficient principle of the complete graph. Separating clusters only runs once in the beginning. A new cluster-head will be elected when there is no cluster-head in a cluster or it is in the situation of low power, and then the information is send to the latest cluster-head. Simulating experiment with Matlab shows that this paper achieves a range-based clustering localization algorithm. The algorithm maintains the advantages of high-speed deploying, high energy-efficient and high accuracy. In addition, the algorithm is adequate to non-loosen wireless sensor network.Key words: wireless sensor network; AOA(angle of arrival) algorithm; clustering algorithm; localization algorithm 收稿日期： 2014-11-13 基金项目： 广东省高等学校科技创新重点项目[cxzd1144] 作者简介： 黄琦（1989-），男，湖北，硕士研究生，主要研究方向：信息安全；黄海（1982-），男，湖南，博士研究生，主要研究方向：信息安全；谢冬青（1965-），男，湖南，教授，博士，主要研究方向：信息安全。 通讯作者： 黄琦 q51249177@https://www.doczj.com/doc/7116511100.html, doi ：10.3969/j.issn.1671-1122.2014.12.011