基于最小生成树的非均匀分簇路由算法
摘要:发现现有的针对非均匀分簇路由算法没有充分考虑簇首
与基站之间最优路径选择,而导致传输路径上的能量消耗不均衡的问题。为了更好地均衡传输路径上节点能量的消耗,提出了基于最小生成树的非均匀分簇的路由算法。该算法利用节点剩余能量和节点到基站的距离选举簇首,然后通过建立最小生成树搜寻最优传输路径,这样可以减少传输路径上的能量消耗,有效地解决能耗不均
衡问题。理论分析和实验结果均表明,该算法无论在存活节点个数还是在能量消耗上都明显优于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)作为新兴的网络测控技术,能够自主进行数据采集、融合和传输。由于节点与基站的距离较远,节点之间一般都采用多跳的形式进行数据传输。在这种“多对一”的数据传输模式中,导致靠近基站的节点会因转发过多的能量而死亡,出现能量消耗不均衡现象。因此,如何均衡各个节点之间能量消耗是wsn研究的热点。
为了减少冗余数据开销,heinzelman等 [1] 提出了自适应的分簇路由算法,方便了节点管理和控制信道的接入,减少开销,提高资源的利用效率,有效地降低节点能量消耗,延长网络的生命周期,但在分簇传感器网络中,由于簇首到基站的距离比较远,簇首与基站之间需要通过多跳路由的方式进行传输和转发数据,这样进行数据传输时,将会造成离基站近的簇首因过多地转发数据而消耗大量的能量,导致能量消耗的不均衡问题；文献[2]提出了一种能量有效的非均匀分簇(energy efficient uneven clustering, eeuc)算法,虽然同时考虑簇内和簇间的能量均衡问题,但是eeuc需要周期性地随机竞选簇首,而且竞选簇首时只考虑了节点的剩余能量；文献[3]提供了一种有效的部署模式,将部署问题转化为多背包问题,利用蚁群优化的方法解决这一问题,能够延长网络的生命周期,但是对于一些环境恶劣的地区很难实现人工部署；在文献[4]提出了一种负载均衡的无线传感器网络自适应分簇算法,该算法使用簇半径、
节点剩余能量和簇首间距作为参数选取簇首,簇首与基站节点采用多跳的方式进行通信；文献[5]提出的改进的非均匀分簇算法考虑邻居节点剩余能量,文献[6]算法根据剩余能量选举簇首,同时限制簇内成员的数量和多跳路由的方式控制能量的消耗,都不能有效均衡节点的能量；文献[7]通过分析无线传感器网络中数据传输的动态连接优化问题,提出了一种利用代价模型、自适应学习和自协调启发式方法进行实时变量值的筛选方法,主要是集中于簇内连接计算,然后对成对主成分进行优化,实验结果表明可以应用于大规模
的标准数据集上；文献[8]提出的一种能量均衡的路由算法(energy balancing clustering algorithm, ebca),在非均匀部署的情况下,利用平衡网格设置节点的能量阈值来选取簇首,虽然在一定程度上能有效地降低网络的能量消耗,均衡网络中节点的能耗,但是没有
涉及到最优路径的选择问题；文献[9]提出了一种能量高效非均匀分簇算法(uneven clustering algorithm, uca),通过簇首之间协调传输数据减少基站附近簇首的负担,但是没有涉及到最优路径的选择问题；文献[10]提出自适应分布式再分簇算法,通过节点的剩余能量和每个簇的平均能量来选择簇首和下一跳,但未考虑节点到基站的距离；文献[11]针对无线传感器网络节点负载不平衡性,在综合考虑节点信息感知和信息传递能耗基础上对圆形区域节点能
耗进行分析,使网络结束后,节点的剩余能量基本相同,仅仅考虑圆形区域,不具普遍性；文献[12]通过分析网络中不同半径下能量消
耗情况,提出了不等簇半径轮转工作的能量空洞避免策略,对簇首
之间的传输问题未进一步优化；文献[13]采用基于优先级的簇首选择策略,避免能量低的节点成为簇首,在一定程度上可以有效缓解
能量洞问题；文献[14]针对基站附近的节点由于要转发数据而消耗过多的能量,导致能量洞的形成,提出了剩余能量启发合作传输避
免能量空洞,通过合作阈值来进行数据传输,但是没有考虑到节点
到基站的传输路径。
为此，本文提出了基于最小生成树的非均匀分簇路由算法(uneven clustering routing algorithm based on minimum spanning tree, ucramst),很好地解决了能量消耗不均匀的问题,有效延长整个网
络的生命周期。
1 模型与问题描述
1.1 前提假设
传感器网络性质如下:基站节点具有较强的计算和存储能力,且满足对能量的需要;所有的传感器节点一旦部署之后是固定不动的,
具有相同的通信能力和初始能量,另外还具备一定的数据融合功能;所有的节点根据接收的信号强度指示(received signal strength indication, rssi)可以获知自己的位置信息,根据接收者的距离远近,自动地调节其发送功率,以减少节点能量的消耗。
1.2 能量模型
在描述算法之前,分析传感器网络的发送能量消耗,采用文献[15]中定义的能量模型:
e trans (s i,s i+1 )=e 0+ε(d(s i,s i+1 )) α(1)
其中:e 0为发射电路的耗损能量,ε表示模型中功率放大所需的能量,d(s i, s i+1 )表示两个节点之间的距离,e trans (s i,s i+1 )表示节点s i将单位数据传输给s i+1 所消耗的传输能量,α取2或4。
传感器节点接收k比特数据消耗的能量e rece (k)为:
e rece (k)=k*e 0(2)
假设s i选择s j作为其数据转发节点,其中每个节点在固定的时间t内产生k比特的数据,s i所在的簇内节点的个数为n i,s j所在的簇内节点的个数为n j。为了简化问题分析,假设通信采用自由空间模型,并假设s i将数据传输至s j,s j 将数据直接传输至基站,则传输k比特的数据至基站,s i消耗的能量e i为
e i=n i ke 0+n i ke trans (s i,s j)= n i k(2e 0+εd 2(s i,s j))(3)
s j消耗的能量主要有3部分:s j所在的簇内节点收集数据消耗的能量为n j*ke 0,接收s i的传输数据所消耗的能量
为n i*ke 0,发送s i和s j这两部分数据消耗的能量。则s j消耗的能量e j为:
e j=n j ke 0+n i ke 0+(n i+n j) ke trans (s j,bs)=
(n i+n j) k(2e 0+εd 2(s j,bs))(4)
则s i→s j→基站这条路径上消耗的能量e com 为:
e com =e i+e j=
(4n i+2n j)ke 0+n ikεd 2(s i,s j)+
(n i+n j)kεd 2(s j,bs)(5)
由式(5)可知,d 2(s i,s j)+d 2(s j,bs)将决定网络能量消耗的高低,因此优化传输路径可以降低网络中能量的消耗。
2 基于最小生成树的非均匀分簇路由算法
ucramst分3部分:根据节点的剩余能量和节点到基站的距离进行非均匀分簇和簇首的选择;对簇首之间的传输路径进行搜索,通过建立最小生成树来寻找最优的传输路径;进行数据传输和转发并根据剩余能量和距离进行簇内调整和路由更新。
2.1 非均匀分簇和簇首选举
无线传感器网络所有的节点参与簇首的竞选,簇首选举采用非均匀分布竞选方式,网络中的所有节点都参与竞选,并将节点的剩余
能量和节点到基站的距离作为簇首选择的评价标准,每进行一段时间的数据传输之后,簇内节点把自己的能量信息发送给簇首,在簇内所有节点中选取一个剩余能量最大的且离基站较近的节点取代簇首。通过簇首轮转的方式可以有效地均衡簇内各节点的能量消耗。
规则1 在竞选过程中,如果节点s k竞选成功,则在s k的竞选半径r k之内的所有的节点均不能成为簇首并且退出竞选的过程。选举时计算竞选广播半径方法如下:
r k=1-cd max -d(s k,bs)d max -d min r 0; c∈(0,1)(6)
其中:r 0是根据节点到基站的距离信息计算出来的竞选半径的最大值,r k是节点s k的竞选半径,d max 和d min 分别是节点到基站距离的最大值和最小值,c是用于控制竞选半径取值范围的参数,d(s k, bs)表示节点s k到基站的距离。由式(6)可知,随着节点到基站距离的减小,其竞选半径随之也减小,即靠近基站的传感器节点的竞选半径较小。
选举非均匀簇首的算法步骤:
第1步各节点计算自己的竞选半径并在竞选半径r k/2范围内广播竞选的消息msg1,该消息包含节点的 id、 节点到基站距离d(s k, bs)和剩余能量e resi 。
第2步各节点收到其他节点的竞选消息msg1,把满足条件的节点
添加到竞选节点的列表table中。条件:d(s k, s j)p j,则节点s k就成为新的簇首;否则s j就成为新的簇首,并将这一信息广播给簇内各个节点和相邻的簇首,同时修改路由表信息, 包括id、相关的能耗信息和剩余能量。
簇内调整后,将更改后的簇首信息添加到路由表中,如果路由表中有原簇首的信息,则将其删除掉,并将新簇首的id、剩余能量和相关的能耗信息添加到路由表中,并将这一信息广播,使传感器网络中的所有簇首都能获得这一信息,更改其他簇首节点中存在的原簇首的信息。
2.4 算法性能分析
假设无线传感器网络中节点数量为 n,簇首的数量为n head 。下面讨论基于最小生成树的非均匀分簇动态路由算法的时间复杂度。
对于非均匀簇和簇首选择部分,首先要对所有的传感器节点计算竞选簇首的广播半径,时间复杂度为o(n);每个传感器节点在添加到竞选列表时都要计算各节点之间的距离,对应的时间复杂度o(n 2);根据每个节点的竞选列表,通过比较剩余能量和节点与基站的距离来决定簇首的选择,对应的时间复杂度是o(n 2);从整体上看,整个非均匀分簇和簇首选举算法的时间复杂度是o(n+ n 2+ n 2)，即o(n 2)。对于基于最小生成树的方法搜索最优路径的部分,首先构造一个带权连通图,构造带权的连通图的时间复杂度
是o(n 2 head );根据 rssi 距离对簇首进行等级划分的复杂度是o(n head );当搜索簇首节点到基
基于粒子群优化的非均匀分簇路由算法 摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与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
基于最小生成树的非均匀分簇路由算法 摘要:发现现有的针对非均匀分簇路由算法没有充分考虑簇首 与基站之间最优路径选择,而导致传输路径上的能量消耗不均衡的问题。为了更好地均衡传输路径上节点能量的消耗,提出了基于最小生成树的非均匀分簇的路由算法。该算法利用节点剩余能量和节点到基站的距离选举簇首,然后通过建立最小生成树搜寻最优传输路径,这样可以减少传输路径上的能量消耗,有效地解决能耗不均 衡问题。理论分析和实验结果均表明,该算法无论在存活节点个数还是在能量消耗上都明显优于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)作为新兴的网
算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日
题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
第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-),男,江苏徐州人,硕士研究生,从事信息与通信工程的研究
最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。
例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）
———————————— 作者简介作者简介：：李 辉(1976－)，男，副教授，主研方向：无线传感器网络；刘书吉，硕士研究生。 收稿日期收稿日期：：2013-03-04 修回日期修回日期：：2013-04-18 E-mail ：li20042007@https://www.doczj.com/doc/b6966062.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]提出的基于竞争的非均匀分簇
#include
{ printf("请输入有边的2个顶点\n"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求请重新输入:\n"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("请输入%d与%d之间的权值:\n", n, m); scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } void sort(edge edges[],MGraph *G)//对权值进行排序{ int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); for (i = 1; i < G->arcnum; i++) {
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/b6966062.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/b6966062.html, ；赵尚卿（1988—），男，硕士研究生，研究领域为无线协作通信。 收稿日期：2014-05-12修回日期：2014-07-04文章编号：1002-8331（2016）07-0106-04 CNKI 网络优先出版：2014-12-11,https://www.doczj.com/doc/b6966062.html,/kcms/detail/11.2127.TP.20141211.1522.015.html 106
最小生成树的两种经典算法的分析及实现 摘要：数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM和KRUSKAL的两种经典算法的算法思想，对两者进行了详细的比较，最后用这两种经典算法实现了最小生成树的生成。 关键词：连通图，赋权图，最小生成树，算法，实现 1 前言 假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n （n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。 2图的概念 2.1 定义 无序积 在无序积中， 无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。 有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。 有时，泛指有向图或无向图。 2.2 图的表示法
有向图，无向图的顶点都用小圆圈表示。 无向边——连接顶点的线段。 有向边——以为始点，以为终点的有向线段。 2.3 概念 (1)有限图——都是有限集的图。 阶图——的图。 零图——的图。特别，若又有，称平凡图。 (2)关联 (边与点关系)——设边(或)，则称与(或)关联。 无环 孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。 (3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。 2.4 完全图 设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则 称为阶无向完全图，记作。 若有向图的任一对顶点，既有有向边，又有有向边，则 称为有向完全图。 例如：
基于粒子群优化的非均匀分簇路由算法摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所 提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。 关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化 算法；能量消耗；生存期 中图分类号: 文献标志码: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
一、树及生成树的基本概念 树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述： (1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。 例如：已知有六个城市，它们之间要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。这样，六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话，这个图 必须是连通图，且这个图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图，代表了一个电话线网。 生成树（支撑树） 定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理：一个图G有生成树的条件是G是连通图。 证明:必要性显然； 充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子 图G K，且不含圈，从而G K是一个生成树。 寻找连通图生成树的方法： 破圈法：从图中任取一个圈，去掉一条边。再对剩下的图 重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图 中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3） 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7， 这样，剩下的图不含圈，于是得到一个支撑树，如图所示。 避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。
基于博弈论的无线传感器网络非均匀分簇路由算法 推荐到首页 -------------------------------------------------------------------------------- □衷柳生程良伦《计算机应用研究》2009年第05期 1/6页12 3 (6) (广东工业大学自动化学院广州510006) 摘要:为了有效解决无线传感器网络路由节能问题,引入了博弈理论思想,提出了一种基于博弈论的无线传感器网络非均匀分簇节能路由算法UCEER。仿真实验结果表明,该算法解决了节点能耗分布不均的难题,体现出了其自适应调整簇首、调节节点负荷、延长网络平均寿命的能力,保证了路径的可靠度。 关键词:无线传感器网络;博弈论;路由;非均匀分簇;节能 中图分类号:TP393文献标志码:A 文章编号:1001-3695(2009)05-1865-03 Unequal clustering energy economical routing algorithm based on game theory for WSN ZHONG Liu sheng CHENG Liang lun (Facaulty of Automation Guangdong University of Technology Guangzhou 510006 China) Abstract:In order to efficiently solve the problem of rooting,this paper introduced the thinking of game theory and presented UCEER algorithm for wireless sensor networks. Simulation results show that the routing algorithm efficiently balances the energy consumption of nodes in wireless sensor networks prolongs the network lifetime and guarantees the path reliability. Key words:wireless sensor networks; game theory; routing; unequal clustering; energy economical 0 引言 随着传感器技术和通信技术的发展,无线传感器网络技术开始提出,并因其应用的广泛性而得到越来越多的重视。无线传感器网络是由一组传感器节点通过无线介质连接构成的无线网络它采用Ad hoc方式配置大量微型的智能传感节点通过节点的协同工作来采集和处理网络覆盖区域中的目标信息[1]。该网络功耗低、成本低、体积小;集数据采集、处理、传输于一体具有自组织特性和高抗毁能力在地理环境监测、灾害预报、医疗保健、工业生产过程监测、恶劣环境监测、军事侦察等方面具有广阔的应用前景[2]。无线传感器网络中传感器节点的能量资源、计算能力和带宽均非常有限,且节点十分密集,设计有效的策略延长网络的生命周期成为无线传感器网络的首要问题。路由协议是网络节点相互通信的基础,无线传感器网络路由协议负责寻找一条传输路径将数据分组从数据源节点通过网络多跳转发至目标节点[3]。设计合理的路由协议对降低及平衡网络中节点的能耗,延长网络的存活时间有着重要意义。 本文引入博弈理论思想,设计了一种非均匀分簇节能路由协议。尽管针对基于博弈论的路由协议已经有了一定的研究,然而大部分路由协议,如文献[4,5]均针对平面型网络而设计;
实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法； 2、掌握最小生成树算法，如Prim、Kruskal算法； 3、基本掌握贪心算法的一般设计方法； 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法； 2、设计Kruskal算法实验程序。 有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点U={}
不属于最小生成树的顶点V={1，2，3，4，5，6} 2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树 的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}
3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5} 4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}
5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5} 6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成