分簇算法范文（精选7篇）
分簇算法 第1篇
WCA算法是一种组合的加权分簇算法。在这种算法中, 每个节点分配一个权值来指示该节点适合充当簇头的程度。各节点的权值可以使用一个考虑多种因素的通用公式表示:
式 (1) 中, 权值因子a、b、c、d由应用和网络环境决定, mobility表示节点的速度, degree表示节点度, power表示节点的传输功率, energy_left表示节点剩余的能量。此外, 每个变量需要根据具体的应用选用合适的单位, 并可根据需要增加更多的变量。
该算法综合考虑了节点的传输能力、移动性和电池能量, 但只考虑到了每个节点的累计绝对速度。把每个节点的绝对速度的历史累积作为一个参数, 的确可以看出一个节点的移动性, 但是只能说明这一个节点的稳定性, 不能说明它形成整个簇的稳定性, 也不能说明它作为簇头的稳定性, 在实际应用中, 一个簇内的成员, 往往组成一个小组统一行动。要是考虑移动性最小的成员作为自己组的簇头负责与其它簇的联系, 在组成员都朝一个方向运动的情况下, 簇头因为一些原因拖后, 但是由于它的权值还是比较小, 仍被作为簇头, 其实这时应该有更合适的点作为簇头。显然WCA分簇算法使得网络的分级不够合理, 影响了网络的可扩展性。
2 EWCA分簇算法
从一个簇的稳定性考虑, 希望簇建立以后就不要变化太大, 关键是簇头尽量不要变化。从系统消耗考虑的方面考虑, 由于节点在簇之间移动引入的开销相对较小, 而簇头更新带来的计算和通信开销较大, 对网络的性能影响最大。通过分析, 采用平均相对速度作为移动性的测量的标准, 希望找出的节点在整个网络运动的时候, 能保持作为簇头。而这在实际应用中具有重要的意义。
2.1 权值计算公式
式 (2) 中各个权值参数的意义如下:
V表示节点i的与所有邻居节点的平均相对速度。在EWCA中, 希望得到的是簇头的平均相对速度小的点, 所以用正比来考虑平均相对速度。
D为邻居节点与节点i的平均相对距离。希望得到的簇头到簇成员的距离之和越小越好, 而且希望到每个簇成员节点的距离很平均, 这样可以降低发射功率, 节省电力。所以也用正比来考虑平均相对距离。
P为节点i的发射功率。希望得到的簇头发射功率可以覆盖整个簇, 因为它还要负责簇之间的路由、簇内节点的路由、簇内节点和其它的簇内节点的路由, 所以希望找一个发射功率大的节点。因此用反比来考虑发射功率。
Pe为节点i电池现有的容量。作为Ad hoc网络这种无基站的无线网络的特点, 电池容量是一个很重要的参数, 因为簇头要一直开机, 需要的发射功率也很大。如果一个算法会选择一个电力不足的节点作为簇头, 也就是意味着簇头要频繁的变换, 整个网络的簇体系结构的稳定性就达不到要求。所以用反比来考虑电池容量。
w1、w2、w3、w4是权值因子。
2.2 算法设计具体描述
EWCA算法主要是两个过程, 第一个是簇头的选举过程, 第二个是簇的建立和维护过程。
(1) 簇头的选举过程其步骤如下:
Step1:网络中的每个节点独立的寻找自己的邻居节点, 获取邻居节点的信息。
Step2:计算相对速度, 如式 (3) 所示:
Step3:计算平均相对速度, 如式 (4) 所示:
Step4:计算平均相对距离, 如式 (5) 所示:
Step5:获取电量Pe。
Step6:计算每个节点的权值 (依据公式 (1) ) 。
Step7:选择权值最小的节点作为簇头。簇头的邻居节点都被认定为簇成员节点而不能再被选作为簇头。
Step8:重复2-7直到没有节点被选举为簇头或则没有新节点加入簇。
(2) 簇的建立和维护过程其步骤如下:
Step1:初始基本信息传播。
每个节点刚开始启动时, 它宣称自己在初始状态, 然后向周围节点传播它的ID号、位置信息 (x, y) 、速度信息v、功率值P, 电池能量值Pe、相邻节点个数m, 相邻节点距离D。节点的ID号是随机分配的。节点的位置信息是通过它本身携带的全球定位GPS卡准确给出。
Step2:根据公式 (3) 、 (4) 、 (5) 、 (1) 分别计算速度、距离、权值。
Step3:开始构建簇。
Si表示节点i收到所有节点信息的集合, 在节点集中满足权值Wi最小的节点可被选作簇头。若节点i发现它本身Wi值最小, 则节点i向它的邻居节点宣称自己为簇头;若节点i发现Si集合中, 它的Wi值不是最小, 则节点i向它的邻居节点宣称自己为该簇的簇成员。
Step4:簇的维护和重建。
当发生下列情况时都有可能使簇内成员组成发生变化: (1) 一个新节点进入网络; (2) 一个已存在的节点离开网络; (3) 一个节点进入新的簇头统治域; (4) 一个节点离开现在的簇头统治域。因为簇头与每个节点间定期进行通信, 当簇头确认一个节点离开该簇时, 则将该节点从簇内成员表中删除;当收到新的节点信息且满足所需的条件时, 则加入该节点为簇成员;若不满足条件, 通知该节点继续寻找新的簇头, 若其寻找不到, 则宣称自己为新的簇头, 引发网络簇的重构。当移动的两簇头之间的距离小于等于某一规定要求时, 也要引发重构。
3 EWCA分簇算法仿真试验与性能分析
本次仿真试验使用的是NS软件, 这是一款运行在Linux下的网络仿真软件, 使用的版本是ns-allinone-2.26。
定义仿真的网络区域范围为100m 100m, 仿真实现2 000秒钟的场景。在这个基本的场景中进行一系列的实验。
3.1 测试EWCA的产生簇的稳定性
验证相对速度在簇头选举和维持簇的重要性。在定义的Ad hoc环境中, 先通过场景产生器, 产生一个节点数目n=20的场景文件, 其中挑选3个节点3、9、18, 这3个节点的起始位置, 运动方向, 终止位置大致一样。在仿真运行的第25-27秒内3个节点开始移动, 移动速度为5 m/s, 这次实验主要就是跟踪这3个点, 记录3个点是否在一个簇中、簇头是哪个、移动中簇的成员的变化。
跟踪Node.Cluster_head和Node.cluster_Node[] (簇成员编号) 变量, 发现它第一个周期就成为簇头。
从表1可以看出由于9、3、18节点相对速度很小, 那么在其它的条件差不多的情况下, 他们三个会一直保持在一个簇中, 这样有利于簇的稳定性, 减少簇选举的花费。可以看出由于平均相对速度参数在权值计算中的重要性, 使节点9一直倾向于作为簇头。节点在簇之间移动引入的开销相对较小, 而簇头变化和簇的统治集更新带来的计算和通信开销较大, 对网络的性能影响也最大, 所以节点9一直被选为簇头, 这样就大大的减少了计算和通信开销。
3.2 EWCA与WCA在簇头的变化数目上的比较
比较EWCA和WCA算法在同一场景下簇的稳定性。比较的参数就是簇头变化的次数, 一次簇头的变化就是一次簇的完全重组, 就是一次统治集的变化, 统治集更新带来的计算和通信开销较大, 对网络的性能影响也最大。而好的簇算法应该能尽量维持簇的稳定性, 也就是尽量减少变化。
在定义的Ad hoc环境中, 先通过场景产生器, 产生一个节点数目n=30的场景文件。移动速度为5 m/s, 传输范围10-70m。在实验中, 设置全局变量纪录簇头变化次数。其仿真结果如图1所示:
从图1中可以看出EWCA与WCA的变化规律相同, 在节点传输范围较小时, 没有几个邻居节点, 所有邻居节点平均的相对速度在簇的选举中不那么明显, 这样WCA的稳定性要稍稍好一些。当传播范围在30-50时, 邻居节点的数目增加了, 这时邻居节点平均的相对速度的优点体现了出来, 这样一两个节点的进入和移出簇, 对于簇头选举的影响不那么剧烈, EWCA算法中簇的稳定性要好于WCA算法。当传播范围增加到50以上, 节点移入与移出簇的概率减小, 整个网络的簇的变化率都减少了。
4 结束语
针对WCA分簇算法的不足, 通过考虑节点与邻居的平均相对速度, 改进了权值参数, 设计出一个稳定性高的簇头选举方法EWCA分簇算法。通过模拟实验, 可以看到在所有的分簇算法中节点传播范围为30-50时, 簇头变化频率最高, 这时EWCA具有较高的簇稳定性。
摘要：在Ad hoc网络层次式组播路由协议中, 分簇算法对于协议的性能有着至关重要的作用, 首先详细分析了WCA算法, 然后针对其不足提出了改进的EWCA算法, 最后利用网络仿真软件NS对EWCA算法进行了仿真实验与分析。
关键词：Ad hoc网络,组播,分簇算法,EWCA
参考文献
[1]C.R.Lin, M.Gerla.A distributed architecture for multimedia in dynam-ic wireless networks[C].IEEE Globecom'95, Toronto, Canada, 1995.
[2]S.Basagni.Distributed clustering for Ad hoc networks.InternationalSymposiun on Parallel Architectures, Algorithms and Networks[C], Perth, German, 1999.
[3]M.Gerla, J.T.C.sai.Multicluster, mobile, multimedia radio network[J].Wireless Networks'95, Phoenix, USA, 1995 (3) .
[4]Mainak Chatterjee, Sajal K Das, Damla Turgut.An weighted cluster-ing algorithm (WCA) for Ad hoc networks[A].IEEE Globecom2000[C], Orlando Florida, USA, 2000.
基于LEACH协议的分簇算法设计 第2篇
在层次路由协议中, 无线传感器网络被划分成多个簇, 每个簇由一个簇头节点 (Cluster Head) 及多个簇内成员节点 (Cluster Member) 构成, 多个簇头形成高一级网络。在高一级网络中, 又可以再分簇, 再次形成更高一级网络, 一直到最高级的汇聚节点为止。
层次结构中, 每个簇的形成常常是基于节点能量及与簇头的接近程度。簇头不仅要负责簇内信息的采集及融合处理, 还要负责簇间的数据转发, 它的可靠性和稳定性对于整个网络性能影响较大, 信息的收集和处理也将消耗簇头的大部分能量。
1LEACH协议
LEACH (Low Energy Adaptive Clustering Hierarchy) 是为无线传感器网络设计的一种低功耗自适应的层次路由协议。它的基本思想是以循环方式随机选取簇头, 将网络的能量负载平均的分配到每一个节点之上, 从而降低能耗和延长网络生命周期。主要是通过随机选择簇头节点, 平均的分担转发通信任务来实现。
LEACH算法中通过引入“轮 (Round) ”的概念, 每轮由构建阶段 (Set-up) 以及稳态阶段 (Stead-state) 构成。构建阶段中节点被分成若干簇, 且产生相应簇头;稳态阶段中数据从非簇头节点被发给簇头节点, 在簇头节点上处理后发给汇聚节点。在簇的构建阶段, 簇头节点的选择根据所需的簇头总数以及迄今为止每一个节点已成为簇头的次数来决定。具体选择办法是每一个节点选择0～1之间的一个随机数, 如选的a小于某阈值T (n) , 那这个节点就成为簇头节点。T (n) 的计算公式为:
公式1的p是簇头数与总节点数的百分比;r是当前轮数;G是前r轮中未充当过簇头的节点集合。节点确定自己成为簇头节点之后, 广播自己成为簇头节点的消息, 非簇头节点根据接收信号强度来确定要加入到哪个簇中, 并且通知该簇头节点将成为它的一个成员节点。簇头回复一个TDMA消息给簇内的成员节点。稳态阶段, 各节点在其时隙内把所监测到的数据发给簇头, 簇头节点将接收到的数据融合, 最后把结果发给汇聚节点。
LEACH使用随机选簇头节点方式, 避免了簇头节点消耗过多能量, 采用数据融合方法来有效减少通信量, 因此和一般的多跳路由协议和静态聚类算法相比, 可将网络生命周期延长15%。但LEACH协议是假设所有节点都可以直接与簇头、汇聚节点通信, 采用连续数据发送的模式及单跳路径选择的模式, 所以在大范围监测应用中是不适合的, 即使是在小规模网络中, 距离汇聚节点远的节点由于大功率通信, 也会导致生存时间比较短;并且动态地分簇也带来了拓扑变化和大量广播这样额外的开销, 会耗费过多能量。
此外, LEACH假设簇内成员节点在属于它们的时隙内都有数据发给簇头, 但实际情况有可能是节点只在监测到事件后才会发送。而且, LEACH中簇头节点都是随机的产生的, 并不考虑节点剩余能量, 有可能导致剩余能量少的簇头节点的能量尽早耗尽。
2问题描述
LEACH是在无线传感器网络中最早提出的路由协议, 并且是比较常用的分簇路由协议, LEACH协议可以使得所有节点在一个周期内都担任一次簇头, 均衡的分担能耗, 但簇头节点都是随机产生的, 并不考虑节点地理位置, 无法保证簇头节点均匀分布, 有可能产生的大部分簇头节点集中在某一区域, 或所产生的簇头节点分布在离基站较远的区域的情况, 而与基站距离较远时进行通信, 将消耗过多能量, 簇头可能会快速死亡, 影响传感器网络的生命周期;另外, 协议中簇头的选择没有考虑节点的剩余能量, 有可能导致某些剩余能量小的节点能量提早的耗尽;并且, 由于随机的选举簇头则簇头需负担的簇内节点数不同, 个别簇内节点相对较多的簇头负担会过重, 网络的负载平衡度随之下降。
3助理簇头ASCH算法
许多分簇算法在节能方面都相当有成效, 但是往往存在着簇头节点负担相对过重的问题, 本文是从减轻簇头负担, 以降低能耗这方面考虑, 提出了助理簇头算法ASCH (Assistant Cluster Head) , 此算法以LEACH为基础, 在其基础上进行改进, 算法根据簇头节点的剩余能量, 簇头距离基站的远近以及簇内成员节点数目等因素产生阈值公式, 来确定是否需要在簇内产生助理簇头ASCH, 所选择的助理簇头负责转发本簇簇头的数据给基站, 起到一个转发数据之功能, 以此来分担簇头节点的负担, 均衡能耗;然后, 在需要产生助理簇头的簇内的非簇头节点中选择ASCH的时候, 根据各成员节点发送数据的能耗以及它们自身的剩余能量情况, 选择出合适的节点成为本簇的助理簇头ASCH。
3.1网络类型说明
传感器节点随机的分布于一个正方形区域内, 对该传感器网络假设如下:①每一个节点都有唯一ID, 且节点初始能量相等;②传感器节点部署后, 不会随时间推移而移动;③基站位于离传感器区域较远的地方;④每一个节点都能与网络中其他任一个节点通信, 也能与基站直接通信;⑤节点可根据接收信号强度计算它到发射点的近似距离。
3.2ASCH的产生阈值
在网络的部署阶段, 基站需向网内广播信号, 每一个节点在接收到此信号之后, 由接收信号强度来计算它与基站的近似距离。算法仍采用LEACH算法构建阶段的簇头节点选择及成簇的方式, 先是产生出簇头节点并形成簇, 然后再产生助理簇头。而关键首先考虑的问题是要在哪些簇内产生助理簇头, 那么助理簇头ASCH的产生从3个方面来考虑, 即簇头节点的剩余能量、簇头与基站的距离, 及其簇内成员节点的数目。一般情况下, 在簇头剩余能量较少, 离基站较远, 以及簇内成员节点较多的簇内需产生助理簇头ASCH。由此, 可定义产生助理簇头ASCH的阈值TAS的公式, 其式如下:
其中, 0
3.3簇内产生ASCH
在需要产生助理簇头的簇内的非簇头节点中选择出一个助理簇头, 要考虑的是其接收和发送数据能耗ETx、ERx较少, 而其节点剩余能量Ere较多。
在LEACH 路由算法中使用的能量消耗的公式是一阶无线模型。根据这种模式, 将l位数据发送距离d的发送耗能和接收耗能, 由下面方程表示:
发送能耗:
接收能耗:
undefined
由公式 (3) 可知发送相同比特的数据时, 距离越远所耗的能量越多, 在我们选择ASCH时要求它的剩余能量多, 且接收簇头数据的能耗和发送数据到基站的能耗要少, 而由接收能耗公式 (4) 可知节点接收相同比特数据的能耗是相同的, 所以接收能耗我们就不予考虑了, 这里只考虑节点剩余能量Ere和发送能耗ETx, 由此可以产生如下的公式:
其中:Ere (i) 为节点i的剩余能量;ETx (i, b) 为节点i发送单位比特数据给基站的能耗, 当节点i与基站的距离d
3.4算法描述
采用LEACH算法构建阶段的簇头选择及成簇方式选择出簇头并成簇, 然后根据各簇头的自身情况确定是否需要在簇内产生助理簇头ASCH, 之后在这些需要产生助理簇头的簇内选择出一个合适的节点成为ASCH。在稳态阶段, 簇内节点在各自的时隙内向簇头节点发送数据, 该助理簇头ASCH不参与簇内数据采集等活动, 只负责监听簇头节点的活动, 簇头节点在收到数据后进行数据融合处理, 去除冗余数据信息, 提取关键的信息, 然后将数据转发给此助理簇头ASCH, 由此ASCH再传输给基站。
算法描述如下:
4仿真试验
下面使用MATLAB 2009对LEACH和ASCH进行仿真, 对两者做了比较。假定网络由200个传感器节点组成, 随机的分布在200m200m的范围内, 所有节点都不移动, Eelec=50nJ/bit, εfs=10pJ/bit/m2。
图1是基站位于 (100, 300) 点时, 节点存活个数和网络工作时间 (轮数) 间的关系图, 由图可看出ASCH的节点运行时间要长于LEACH, 且第1个节点和最后一个节点的死亡时间较接近, 第一个节点的死亡时间延长了63%, 提高了网络寿命。
从图2中可看出, 在相同时间内ASCH的能耗要小于LEACH, 这是由于ASCH算法更好的使得每一个节点相对均匀的分担能耗, 更有利于能量的均衡, 节省了整个网络的能量。
图3是基站所处位置不同的时候与网络生存时间间的关系, 从图中可看出, 随着基站距离的增大, ASCH的网络寿命减少地相对较慢, 当基站位置从 (100, 250) 到 (100, 450) 时, ASCH网络寿命从713轮减少到436轮, 减少约39%, 其性能远优于LEACH。
5结束语
助理簇头ASCH算法可动态决定是否需要在簇内产生助理簇头ASCH, 并在需要产生ASCH的簇内选择合适的节点成为ASCH, 以此来减少簇头通信的能耗, 同时也解决了某些簇头与基站通信存在困难的问题。
摘要：基于对LEACH算法的研究, 提出助理簇头ASCH算法。该算法能够在无线传感器网络中, 根据簇头节点所处的地理位置、剩余能量及簇内成员节点数目, 动态决定是否需要在簇内产生助理簇头, 并在需要产生助理簇头的簇内选择合适的节点来减少簇头通信能耗, 同时解决某些簇头与基站通信可能存在困难的问题, 从仿真结果可见此算法能有效均衡及降低网络能耗, 达到延长网络的生存时间的目的。
关键词：无线传感器网络,LEACH算法,分簇算法,助理簇头,通信能耗
参考文献
[1]YOUNIS O, FAHMY S.Heed:A hybrid, energy-efficient, distribu-ted clustering approach for Ad-Hoc sensor networks[J].IEEETrans on Mobile Computing, 2004 (4) .
[2]HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H.An application-specified protocol architecture for wireless Mi-crosensor Networks[J].In:IEEE Transaction on Wireless Commu-nications, 2002 (10) .
[3]HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H.En-ergy-Efficient Communication Protocol for Wireless MicrosensorNetworks[A].IEEE Proceedings of the Hawaii International Con-ference System Sciences’00[C].2000.
[4]S LINDSEY, C S RAGHAVENDRA.PEGASIS:power efficientgathering in sensor information systems[C].In:Proceedings ofIEEE Aerospace Conference, 2002.
[5]韩冬雪, 张瑞华, 刘丹华.基于PSO的无线传感器网络双簇头分簇算法[J].计算机工程, 2010 (10) .
[6]袁辉勇, 李小龙, 戴经国, 等.一种不均衡的无线传感器网络分簇算法[J].计算机工程, 2009 (12) .
[7]任丰原, 黄海宁, 林闯.无线传感器网络[J].软件学报, 2003 (8) .
[8]赵泽, 崔莉.一种基于无线传感器网络的远程医疗监护系统[J].信息与控制, 2006 (2) .
非变换簇的WSN分簇路由算法 第3篇
文献[1]提出了无线传感网拓扑控制典型的低功耗自适应算法LEACH,与平面拓扑算法相比,该协议可以延长网络生命期约30%。但是LEACH算法没有考虑能量不平衡问题,存在很大改进空间。
针对LEACH算法存在的问题,学者们提出一系列改进的算法[2,3,4,5,6,7]。文献[2-4]均提出基于剩余能量的自适应分簇算法,算法选择剩余能量最大的节点作为簇头, 平衡能耗。文献[5]提出了基于节点能量阈值的簇头竞争算法,当簇头节点的剩余能量值降低到特定阈值下时,算法就启动新一轮簇的建立过程。文献[6]利用节点到基站的距离作为簇头选择的权重对LEACH算法进行改进。文献[7]LEACH-EI算法,考虑节点初始能量和当前能量2个因素,利用动态分簇的方式计算能量阈值, 根据能量阈值选择簇头。文献[8]ECRED算法通过引入备选簇头减少簇的重建,用以降低簇头选举的能耗。文献[9]RMCRW算法提出基于环的簇头选举方式,引入权值控制簇头转发路径,达到节能目的。另外也有研究者将已有的一些优化算法如遗传算法、蚁群算法等应用到路由算法的设计中,从而延长网络寿命。
在深入研究无线传感器网络LEACH及其相关改进协议的基础上,本文设计了一种基于能量、距离、节点度的算法(A Cluster Head Make up-Energy-Distance-Densi-ty Algorithm Improved Based on LEACH Algorithm, CMEDD)。
1网络模型
1.1本文采用的节点模型假设如下:
(1)基站距离较远且能量无限,位置不发生改变;
(2)节点同构且初始能量相等,一经部署其位置不再发生改变;
(3)节点发送功率可以进行调整,即具有调节无线收发器工作能耗的控制功能;
(4)节点能够支持多种MAC协议(如TDMA等);
(5)传感器节点具有足够的计算能力,即具有一定的数据融合功能。
1.2能耗模型
节点l位的数据包传送长度为d ,通信模型为[9]:
式中:Eelec为单位bit数据收发能耗;dcrossover为模型划分阈值,d大于dcrossover选择多路衰减模型,其功放能耗为Eamp,d小于dcrossover选择自由空间模型,其功放能耗为Efs。设EDA为簇头节点数据融合能耗;dto BS为簇头到基站的距离;N为节点总数;M为正方形区域边长,一轮工作总能耗为Etotal,则:
2CMEDD算法描述
2.1簇头选择
在分簇结构的无限传感器网络中簇头个数k是影响分簇路由算法网络能耗的一个重要参数。CMEDD算法采用文献[10]中簇头个数k的取值算法。本算法规定首轮成簇及广播工作由基站完成,基站按照最佳簇头个数将网络化分成k个虚拟网格,进而基站在每个网格内随机选取一个节点作为本簇的簇头,同时生成一个邻居列表消息Message_neighbour,并将此信息广播给各自簇 (网格)内成员节点[11]。基站公布本次的信息匹配之前, 所有节点不知道自己所属的簇区域,因此基站发布的Message_neighbour消息覆盖范围要确保网络内所有节点都能接收到。
基站可以从第1轮各簇头发送的数据确定所有节点及基站之间的距离关系,为第2轮及以后的簇头选举提供必要数据。在经过N k轮的工作之后,由于各种随机事件使得簇内节点能量可能差异较大。为了均衡网络能耗并延长其使用周期,在随后的簇头选举中将综合考虑到节点剩余能量、簇内节点平均距离及节点距基站距离、节点度等三方面因素:
(1)节点剩余能量
首先引入节点剩余能量参数E(n) :
式中: En(r) 为节点n在r轮的剩余能量;Eeverage(r) 为r轮时刻簇内平均能量。则:
在每一轮的工作结束时,每个节点查看自身的En(r) 值,并向簇头报告,簇头计算簇内的平均能量值,并向簇内广播。
(2)簇内节点平均距离及节点距基站距离
其次分析节点与簇内其余节点以及与基站之间的距离参数D(n) :
式中:节点n坐标为 (x,y) ;(xi,yi)为簇内其余节点的坐标值;(xto BS,yto BS)为基站的坐标值;D1(n) 为节点n到簇内其余节点的距离之和;D2(n) 为节点n到基站的距离,则:
在网络运行中传感器节点一经部署其位置不会改变,因此每个节点的距离参数只需要计算1次。节点位置信息的传递是在簇建立过程中对能量消息的传递中一起进行的,从而减少了信息交互中的通信损耗。
(3)节点度析节点的度
节点为布尔感知模型[12],即每个节点都具有一个固定的感知半径R ,其感知范围是以节点为圆心,R为半径的圆。簇内处于某节点感知半径内的节点为此节点的一步通信节点。 一步通信节点个数称作节点的度Measure(n) 。一步通信节点较多,即其周围节点分布较为密集,则该节点当选簇头的概率也应随之增大。节点的度调节参数M(n) 的模型及约束条件如下:
各节点根据各项参数调整各自成为簇头的阈值,经过对比阈值较大者成为簇头。
调整后的阈值公式为:
改进后的公式使得当前节点的剩余能量越大、节点到基站以及到其他节点之间的平均距离的关系参数越大,节点的度越大,则阈值T (n) 越大,从而该节点当选为簇头的几率越大,反之当选为簇头的几率越小。
2.2簇间路由
网络中的簇头节点与普通节点一样也有通信模型阈值dcrosscover,当传输距离小于此值时,其能耗与距离平方成线 性关系 。 网络中簇 头选取完 毕则存在G = {V,E} ,V = {v1,v2,⋯,vk},V为簇头集,E为可直接通信的两节点间的通信能耗。则距离基站较远的簇头节点直接向基站发送数据能量会损失较快,不利于网络能量均衡。CMEDD算法在簇头向基站传输数据时,按照代价因子公式寻找下一跳中转接点。
假定在网络中vi,vj均为簇头,则簇头节点vj作为簇头节点vi的下一跳中转节点的代价因子为:
式中:E(i,j)∈ E ;E(vj)为簇头节点vj的当前能量;sij为vi,vj之间距离,且sij dcrosscover;Sj为vj到基站的距离,j = 1,2,⋯,k 。节点vi从属于集合V并且与自身距离小于dcrosscover的节点中找到代价因子最小的节点vj,作为自己的下一跳中转节点。 vj再以同样的方式找到自己的下一跳中转节点,从而形成一条通向基站的通信链路。则vj可作为vi的中转节点,vi向vj发送数据符合自由空间模型,通信链路上的总体能量消耗远小于多路衰减模型。
3算法仿真与性能验证
为了验证CMEDD算法的有 效性 ,对CMEDD, RMCRW和LEACH算法进行对比。仿真实验在Matlab R2014a环境下进行,以随机方式在监测区域内部署传感器节点,假设节点分布在坐标为 (0,0) 到 (100,100) 的区域内。仿真实验使用参数取值分别为:N=100,M=100, 数据包长度l=500,基站的坐标(50,175),Efs=10 p J,Eamp= 0.001 3 p J,节点初始能量E0=2×1010p J,EDA=5×103p J,Eelec=50×103p J。
无线传感器网络的生命周期着重从首节点能量耗尽所用时间进行考虑。基于这一原因实验对网络节点数分别为100,200时三种算法运行期间存活节点数进行仿真,其仿真图分别如图1,图2所示。
如图1所示,模拟环境与初始能量相同,100个节点时LEACH算法运行16轮,第17轮出现节点能量耗尽; RMCRW算法运行20轮,第21轮出现节点能量耗尽;而CMEDD算法运行22轮左右开 始出现能 量耗尽的 节点。CMEDD算法首节点死亡轮数较LEACH算法延长了37.5%、较RMCRW算法延长了10.1%。说明同样的运行时间,CMEDD算法节点能耗更低,并使节点能耗的分布更加均匀,即有效延长了节点的生存时间。由图2可知,在各项参数保持不变的环境下,将节点数增至200,CMEDD,RMCRW和LEACH三种算法的首节点死亡轮数分别为31,28和23,即CMEDD算法首节点死亡轮数较LEACH和RMCRW分别提高了34.8%和10.7%。 说明本算法对网络密度具有较好的适应性。综合分析图1,图2可以看出,CMEDD算法节点生命曲线与LEACH和RMCRW相比较而言坡度较大,说明节点能耗更为均衡。
当网络节点分别为100和200时,CMEDD算法与LEACH和RMCRW算法节点的能量消耗曲线如图3, 图4所示。
分析图3,图4可知,初始阶段三者能耗差别较小, 但随着运行轮数的增加,CMEDD算法的节点存活数目及平均 能量逐渐 高于LEACH和RMCRW算法 ,即CMEDD算法对网络密度具有良好适应性。
4结语
本文提出了基于能量、距离及节点度的非变换分簇的一种能耗均衡的路由算法(CMEDD)。算法给出了分簇方式、簇头选择公式及簇间路由形式,首轮由基站选择簇头,第2轮以后利用基于节点的剩余能量、节点到基站以及到其他节点之间的平均距离和节点的度3项参数的阈值公式选取簇头;数据传输阶段簇头根据代价因子选择中继节点,从而实现单、多跳结合的路由方式, 降低网络能耗。仿真实验及对比表明,CMEDD算法能够有效均衡网络能耗、延长网络生命周期。
CMEDD算法在均衡网络能耗方面有一定优势,但是仍然存在一些问题,如在网络运行中簇头进行数据融合的高效性以及在较大网络中算法的安全性和可扩展性都有待进一步的研究。
摘要：针对LEACH算法簇头选取及能量消耗方面的不足,提出一种基于能量、距离和节点度的分簇路由算法CMEDD,通过均匀分簇减少重建过程,对簇头选举公式进行改进,合理选择簇头,从而均衡节点能耗。采用基于代价因子的单跳和多跳相结合的方式建立最优路径进行数据传输。仿真结果表明,与LEACH算法和RMCRW算法相比,CMEDD算法能够有效均衡节点能耗,可相对延长网络生存周期。
分簇算法 第4篇
无线传感器网络(Wireless Sensor Network,WSN)是传感器技术、无线通信技术计算机技术、嵌入式计算技术结合的产物。利用分布在监测区域中的多个传感器节点,WSN能够感知、监测和采集相关环境或对象的信息。这些信息经过融合之后以多跳中继的方式传递到用户终端,供用户决策使用。WSN改变了人与自然界交互的方式,它在环境监测、军事国防、城市管理、抢险救灾等领域有很高的实用价值。无线传感网络的体系结构如图1所示[1]。
1 Zig Bee网络体系结构
Zig Bee网络是一种无线自组织的网络,网络中的节点之间通过单跳或者多跳的方式进行相互通信,在网络构成上,灵活多变,整个网络支持多种拓扑结构[2],在组网方式上,常见的有三种不同类型的网络,包括星状网、树状网以及网状网。
2 Zig Bee路由协议简介
现有的Zig Bee协议主要采用的泛洪的模式[3]。协调器广播一个消息给网内他所能到达的节点,如图2所示,源节点S如果要向目的节点D发送消息,首先源节点S会想其相邻的节点A、B广播一个消息,当节点A、B收到消息再转发给他们的邻居节点C,由于C是A、B节点共用的邻居节点,根据协议,C节点将抛弃后面所接收到的相同的消息,直到消息传送到目的节点D,当D收到消息后,再按原路径返回给源节点S,当源节点S收到消息后再按Zig Bee协议中规定的路由方式选择最好的路径到目的节点D[4]。
综合上面的分析,发现Zig Bee的泛洪方式虽然实现起来比较简单,不需要去维护路由而消耗很大的能量,但是总体来说也存在一些问题,比如“热点”问题,对数据的丢包率有很大的影响,为了让Zig Bee网络发挥到更大的作用,我们就必须自己设计协议,对Zig Bee的网络按一定的方法进行分簇设计,解决上面提到的问题。一个典型的网络分簇拓扑结构如图3所示。
3 算法设计
3.1 网络模型
本协议规定所有节点都分布在一定规模的区域,然后我们通过一个圆将所有节点包围在里面。该协议的运行前提是在以下四个条件下进行。
1)网络中的所有节点被包含在一个圆形的区域内,并且位置都不变,每个节点通过坐标节点都能计算出自己的位置;
2)节点的发射和接收功率足够的大,可以直接单跳与网络中的所有节点直接通信;
3)每个节点都要具备数据融合的能力;
4)网络中每个节点的初始能量相同。
3.2 簇的具体划分
由于协调器节点的能量是无限的,本协议采用集中式方法对节点进行分簇以及簇头的选取,当网络初始化时,协调器节点集中式的对整个区域根据一定的规则进行簇的划分。大体的划分是规则是:以协调器为中心,建立一个二维坐标轴,并在坐标轴的两端各布置一个参考节点,每个参考节点已知自己在坐标轴上的相对位置,在开始时我们可以对节点位置进行固化,根据监控区域的大小进行设置,圆形区域半径为R,然后通过定位方法得到每个节点的坐标位置,在对节点定位有很多种方案,有直接定位和间接定位,直接定位中可以采用GPRS对节点进行定位,而间接定位主要分为基于距离关系定位、基于信标节点的定位,在本算法中我们采用了基于RSSI测距的三边定位法,在距离的测量中,我们选用了如公式的模型[5]。
则距离发射点的距离d的大小为:
公式(2)中A为发射器发射给1m处的节点的信号强度的大小,其取值范围在45-49之间,n为一个常数,代表信号传输与环境有一定的关系,其取值大小在3.25~4.5之间。通过公式(1)、(2)计算出节点到发射点节点之间的距离后,再根据三边定位算法求出网络中所有节点的坐标值。
在按根据项目的具体需要将网络分为K等分,这样做的目的是为了让整个网络的分簇更加均匀,避免了簇的重叠;使网络拓扑更加均衡,假设将整个网络分成均匀的n等份,即n个簇,则每个簇的扇形角度θ的大小为:
我们定义在y轴上半区域与x轴正半轴夹角为θ的区域为簇1,然后依次划分为簇2,簇3,,簇n,网络中得节点坐标假设为(x,y),则其与x轴的夹角θ',则:
由式(4)可知:
为了定义节点在那个簇,我们在进行簇的比较,即,公式中K表示节点所在的簇的标号,即K的取值为:
具体簇的表示如图4所示,根据此方法可以将整个网络分成具有簇表示符的区域。
3.3 簇头节点选取方法
簇头节点是整个Zig Bee网络分簇中的关键部位,簇头节点的选择算法是整个算法的核心,选择是否合理直接对整个网络有很大的影响,在本算法中,我们采用了节点加权值来确定簇头节点,主要关心以下两个方面。
1)节点的剩余能量;
2)各节点到协调器的距离。
在这里我们定义i表示某个节点,j表示网络划分的某个簇,r表示簇轮换的次数。
关于剩余能量Ei(r)我们可以根据下面的公式(7)求得:
其中,ei(r)为节点i的剩余能量,ei,j(r)_表示节点i所在的第j簇中所有节点的平均能量,的大小为:
Nj(i)表示第j簇中有i个节点。
由于本算法在一段时间后会进行簇的轮转,能量不均对整个网络的影响不是很大,所以,我们在确定代价函数cost(i,j)(r)的公式时,只有代价函数的值越大,当选簇头节点的概率就越大,代价函数cost(i,j)(r)cost的公式如下:
在公式中,必须满足α+β=1,当如果网络中遇到同时有两个节点cost(i,j)(r)值的大小相同时,这时我们再以节点的ID大小来选择簇头节点。节点ID小的当选为簇头节点。
当网络中得簇头节点选择完毕以后,簇头节点将向簇内的每个节点广播一个数据包,在这个数据包中包括了自己已经是簇头节点的消息,其他节点将不在竞争簇头节点。并允许簇中得其他节点加入本簇,并且够建一个簇内节点的邻居表,为了让整个簇内的能耗更少,非簇头节点可以选择定时的休眠唤醒对数据进行采集和传送,这就需要簇头节点给簇内成员分配一个TDMA的序列,簇内的节点根据这个TDMA序列进行数据的传输,没轮到自己传输数据的时候,节点将进行休眠,更加降低簇内节的能耗,让整个簇的生命周期更长。同时为了保证数据传输的准确性,簇内每个节点收到簇头消息的时候,将返回一个ACK对消息进行确认已经收到。
3.4 簇的轮转
当网络中的簇头工作一定时间后其剩余能量较小,这是如果还继续担任簇头节点,不但容易导致簇头节点过快死亡,而且由于簇头节点的能量迅速耗尽,将会对整个网络的稳定性产生一定的影响,许多协议都采用了轮换簇头的方式来解决这一问题[7],但是这些轮换簇头的方法都是在同一个簇内选取剩余节点能量较多的节点来当选簇头节点,并且每个节点只能当选一次簇头,但是由于网络中每个节点都在进行数据的传递,能量都有所消耗,这样一来必定导致每个簇的总体能量都会下降,直到最后每个节点能量都比较少时,不能选出簇头节点,该区域将会成为一个死区,导致网络的稳定性和生命周期,为了解决该问题,我们采取对簇头节点的轮换思想,但唯一不同的时,对整个区域进行重新划分,再对整个簇进行簇头节点的选取。我们采用了根据坐标按相应的规则进行轮转,这样节点位置没有发生变化,但是处于某个簇已经发生该变,具体示意如图5所示。
整个分簇的重新轮转是由协调器发送一个命令进行轮转,这个轮转的时间是随机的,在这里我们设置为T1,轮转时间的值取决于整个网络的生命周期的长短,其值大小将在后面仿真进行取值,当分簇轮转开始时,协调器将发送命令对整个簇进行重新的架构,首先它发送命令给网络中的节点,让网络中的每个节点在现有的角度上加上a度,然后再根据公式(10)判断现在自己属于哪个簇。
注意在簇的轮转中,为了是簇尽量避免轮转后的簇同以前的簇重回,我们设定的轮转角度a不应该与θ的值大小相同,应根据整个网络中布置的节点的数量来设置a的大小。当分簇轮转完成以后,将重复上一节的簇头选择标准进行簇头节点的选取。
4 算法仿真
由于Matlab2007的Trutime工具箱中有完整的物理层以及MAC层的模块,非常方便对于协议栈中的网络层进行仿真,本算法基于MATLAB2007的平台进行仿真,为了评估本算法的优越性,特采用了现有的Zig Bee路由算法AODV以及现有的经典分簇路由算法LEACH与本算法进行仿真比较,由于仿真的模型采用了三种不同的协议,为了实现同等条件下进行比较,我们假定所有的参数都是固定不变的,这其中包括物理层、MAC以及其他的层,在仿真过程中,节点的能耗模型采用了一阶能耗的模型[8],仿真环境的参数如表1所示。
考虑通信模块的工作模式和收发能耗很关键。根据仿真参数设置,通过公式我们可以得到
其中εfs代表无线电路的能量消耗,εamp代表放大器的参数,通过带入表中的数值可以知道d0=87.8,也就是说当簇头节点与协调器节点的距离小于87.8m时,节点的通信模式采用自用空间模型模型,节点的能耗损失最小。
4.1 仿真结果分析
由于评价Zig Bee路由协议的指标相当的多,在这里我们主要从簇的建立时间、每种算法工作一段时间后网络中存活的节点数以及算法在运行过程中整个网络消耗的能量为主要指标来对比分析本算、LEACH算法以及现有的Zig Bee路由协议。通过仿真分析,节点想有机会竞选簇头,至少要满足开始设置的阈值,在本算法仿真中,我们设计节点每隔30ms发送一次数据大小为128bit的数据。在仿真时,我们先确定当α、β的大小,通过仿真分析,当α取0.6时,整个网络的生命周期最长,因此,决定簇头选择标准的权值公式中α=0.6,β=0.4,此后的仿真都采用此数值。
4.2 轮转时间T1的确定
在本算中,我们设计了整个簇不断的轮转来平衡整个网络的能量消耗,但是轮转时间T1的取值不能随意设置,如果这个时间设置过长,有可能网络中某个簇头节点的能量已经消耗的相当多了,而其他簇的能量消耗较少,影响其他簇的节点能量平衡,而当时间设置过短时,有可能整个网络的能量消耗速度加快,因为在本算中,整个网络中簇的重新划分消耗的能量是比较大的,所以在本算法设计中,应该尽可能选择合适的轮转时间周期,以使整个网络的性能更加良好,达到延长网络生命周期的目的。在这里我们选择轮转周期T1的值主要通过仿真来确定,通过设置不同的T1值来观察整个网络中第一个节点的死亡时间,仿真结果如图6所示。
通过图中可知,在后面的仿真过程中,T1的取值为120s时,整个网络的生命周期最长。
4.3 节点存活数情况
由于Zig Bee网络中节点的能量是有限的,因此我们在设计协议时应该以降低网络的能耗以及延长整个网络的生命周期为目标,而节点在工作状态中存活数量的多少直接对整个网络的生命周期有直接的影响,是评价一个路由协议的主要指标[11]如图所示,该图给出了三种算法中,根据网络中节点运行的时间长短,来对整网络中节点的存活数量进行对比,在仿真开始之处,我们设定了节点死亡的定义,如果节点的剩余能力为初始能量的10%时,即认为该节点已经死亡,不在进行数据的采集及传输,仿真结果的曲线如图7所示。
从图中我们可以看见,本算法中节点存活的数量相对其他两种算法,随着时间的推移,当网络运行20s的时候,AODV的路由协议最先出现节点的死亡,这是因为没有对网络分簇,有可能网络中某种节点承担着大量的数据转发,使节点的能耗变大,造成节点的死亡,而本算法第一个节点的死亡时间产生的时间在40s左右而,而LEACH协议的第一个节点的死亡时间在25s左右,这是由于LEACH只在固定区域内对簇投节点的选择进行轮转,而本算采用簇整体轮换的思想,避免了因为某个簇的能量过低而造成节点的大面积死亡,延长了节点的工作时间,在提高了整个网络的负载均衡性,每个节点的能量都得到充分的应用,并使整个网络的生命周期变长,
4.4 网络总能耗分析
在Zig Bee网络中,我们最关心整个网络的总体能耗大小,只有减少了网络整体能耗,才能对延长网络的生命周期有决定性的影响,我们不但要尽可能的减少整个网络的总体能耗,还要使网络中每个节点的能耗均匀分别,仿真结果如图8所示。
从图中我们可以发现,AODV协议的能耗是最高的,这是因为该算法没有对数据进行融合,大量的冗余数据被转发,导致整个网络的能耗增高。而LEACH算法以及本算法都对数据进行了相关的融合,以致整个网络的总体能耗比AODV要低,在网络组建之初,使用AODV协议以及LEACH算法的能耗要低于本算法的能耗,但是随着时间的推移,本算法中的能量消耗呈现缓慢递增的情况,而LEACH算法和AODV协议的能耗都直线上升,这是因为本算法在组网开始阶段,要对每个簇内的簇头选择消耗一定的能量,但是当选择完毕后,网络中的节点负载都比较均衡,能耗降到最低。
5 结束语
分簇算法的设计对网络的性能以及稳定性的提高有很大的意义,如果整个网络使用了分簇算法,不但有利于资源分配,降低数据传输时延,还能够采用混合式的路由,这对网络的扩展性有很大的好处,所有,分簇算法的设计有很广泛的应用,但是分簇协议的设计会带来更多的计算和维护通信的开销,增大网络的能量消耗,因此,为了尽可能的降低分簇算法所带来的一些影响,我们必须提高分簇算法的性能。在未来,分簇算法的研究和设计应该重点注意以下两个方面。
1)应该根据不同的应用环境设置不同的分簇算法,在大规模的网络中,节点一跳到达协调器的几率比较小,这就需要对整个网络进行分层的设计,在每层选择一个簇头,簇头之间组成MESH网络进行通信。因此,在本算法中加入分层思想是下一步的主要研究方向;
2)应充分考虑节点的移动性,节点静止不动适用的范围一般用于定位或者数据的采集方面,但是在某些场合,节点需要移动,这时在设计分簇算法时,应根据节点的移动速度来设计分簇算法。
摘要：ZigBee是一种低功耗、低成本和低速率的无线通信技术,现有的ZigBee路由协议大多采用Cluster-tree+AODVjr的算法,但是此算法容易在网络中形成“热点”效应,导致数据的碰撞并且丢包,同时还会使节点消耗大量的能量,降低网络的生命周期。本文在研究了无线传感网中的经典分簇算法LEACH,并对其进行改进,提出一种将网络划分为大小相同的多个簇,为了均衡整个网络的能耗,将簇的划分随机进行轮转,通过仿真表明,同经典的LEACH算法比较,本算法能较好的解决“热点”问题,并能均衡整个网络的能耗,达到延长网络生命周期的目的。
关键词：ZigBee,能耗,分簇,生命周期
参考文献
[1]孙利民,李建中.无线传感器网络[M].北京:清华大学出版社,2005:156-161.
[2]戚剑超,魏臻.ZigBee树型路由算法的改进[J],合肥工业大学学报(自然科学版)第33卷第4期,2010,4.
[3]王胜平,胥布工,ZigBee网络路由发现广播策略[J],计算机工程,36(11).
[4]周武斌,罗大庸.ZigBee路由协议的研究[J],计算机工程与科学,2009,31(6).
[5]朱明辉,张会清.基于RSSI的室内测距模型的研究[J],传感器与微系统,2010,29(8).
[6]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy efficient communication Protocol for wirelessmicrosensor networks[J],In:Proceedings of the 33rd HawaiiInternational Conference on System Sciences Maui:IEEEComputer Society,2000.3005-3014.
[7]Shu-bo QIU,Yuan XU,Xiu-wei YANG.A Novel ClusterHead Selection Method Using Energy for ZigBee Cluster-Tree Network[J],IEEE International Conference onAutomation and Logistics Chongqing,China,August 2011.
[8]李善仓,张克旺.无线传感器网络原理与应用[M],北京,机械工业出版社,2008:12-20.
[9]Heinzelman W,Chandrakasan A,Balakrishnan H.Energyefficient communication Protocol for wireless microsensornetworks[J],In:Proceedings of the 33rd Hawaii InternationalConference on System Sciences Maui:IEEE ComputerSociety,2000.3005.
[10]黎天人,罗娟,李仁发.基于通信范围约束的传感器网络多层分簇算法[J],计算机工程与应用,2009(4):9.
分簇算法 第5篇
针对上述问题,本文提出一种基于概率触发的负载均衡区域竞选分簇算法。在无线传感器网络初始成簇阶段,利用最大连通度分簇算法所生成簇结构中簇间重叠度较大这一特点,在一次分簇后通过让网关节点根据各邻接簇的负载情况再次选择所属簇来平衡簇间负载。而在簇结构形成之后根据综合考虑剩余能量和发射功率的拓扑维护概率局部竞选簇头节点,有效解决了簇内节点因担任转发功能,能量过早耗尽而失效的问题,最大限度的延长了网络的生命周期。
1 WSN网络模型及问题描述
无线传感器网络拓扑模型可简化为二维平面上的一个有向连通图G(V,E),其中,V表示节点的集合,E表示拓扑链路的集合。采用“本地化”的拓扑控制算法,节点i可获得一个可达邻居子图Gi(Vi,Ei),多个节点的可达邻居子图Gi(Vi,Ei)构成了一个稀疏的网络拓扑。
1.1 网络运行环境
假设传感器网络具有以下特征:(1)节点随机部署在感知区域,且节点具有惟一ID;(2)网络中有一个与有线网络直接相连的sink节点,sink节点有持续供给的能量,其传输范围可覆盖整个传感器网络区域,即sink节点可直接与所有传感器节点进行通信;(3)节点无法自由移动;(4)除sink节点外的其它节点具有相同的处理和通信能力,节点在网络中的地位平等除;(5)除sink节点外的其它节点的传输距离有限,传输距离为R;(6)除sink节点外的其它节点之间连接对称。即如果两个节点V1和V2可以互相通信,则V1发送的消息V2可以收到,同时V2发送的消息V1也可以收到;(7)网络近似区域面积和网络中节点个数在初始和变化时由sink节点直接通知网络中每一个传感器节点。
1.2 能量消耗模型
由于无线传感器节点携带能量有限的电池,并且采用多跳方式将系统采集的数据从源节点传播到汇聚节点。担当数据转发任务的节点,能量消耗除发射功率外还要多消耗一部分接收功率,若节点始终担当转发任务,其生命期会大大缩减。另外,传感器节点的通信功率过高会造成其能量的过快损耗,且加剧节点间的信道干扰并导致通信冲突,而功率过低则会使网络内出现孤岛区域。在无线传感器网络中,通信能耗是节点能量消耗的主要部分,根据文献[5]可知,节点本身产生一个比特流r0(t),接收j个比特流ri,0(t),1
设节点的初始能量为e(0),节点的生命期为l,则有
根据上述理论分析,设每个节点的初始能量为3000个单位的电量,即e(0)=3000,可得到传感器节点担当不同任务时能量消耗的比较图,如图1所示。
由图1中节点的剩余能量分布曲线可以看出无数据转发节点的生命期明显高于数据转发节点和带有数据融合的数据转发节点,且在作为数据转发节点时,经过数据融合后进行转发可节省能量的消耗。
1.3 簇间负载平衡因子LBF[4]
定量刻画簇头负载平衡程度,定义为簇内成员节点数(不包括簇头)的方差的倒数,即
式中:nc簇的数量,xi簇i的成员节点数,网络中每个簇头的平均邻居节点数,N为网络中所有节点的数目。LBF越大,网络负载平衡程度越好。
1.4 簇间链路通信权值函数[6]
其中,ej、ek分别表示传感器节点j和k的剩余可用能量,α、β、γ为预设指数,Ejk表示节点j和k间功耗大小,与节点间Euclid距离成正比,2
1.5 簇间优于关系[6]
设节点j和k是节点u的两个可达邻近节点,即j,k∈NBR(u),称节点j“优于”节点k,当且仅当
1.6 簇内选举概率[6]
设网络中由于簇头节点i能量消耗过快,而发出簇头重新选举的概率Pi可以表示为式(5)的形式。
其中,Ev表示节点i的能量消耗速率,表示在t时刻节点i形成的簇内节点的平均能耗速度,ei表示节点i剩余能量,表示时刻节点i的簇内节点的平均剩余能量,n表示在选举请求未被接受之前的请求次数。由式(6)可知,节点i能耗速率越大,剩余能量越少,发出选举请求的次数越多,新簇选举请求的概率越大。
2 算法描述
2.1 算法设计原则
(1)在延长节点生命期的基础上,应消耗最小的能量保持网络连通;
(2)节点度要尽量不大于6;
(3)在保持网络连通的情况下,应使能量最低的节点不再被选举为簇头;
(4)算法是分布的,节点只需调整发射功率,即可保持网络连通。
2.2 成簇维护
假设节点能感知剩余能量的多少,并且能够调节自己的发射功率。成簇和维护共分为四个阶段:信息请求阶段、簇头形成阶段、信息传递阶段、维护阶段。
1)信息请求阶段
本文把网络中的结点分为三种状态:无簇状态UNCLUSTERED、簇头节点HEAD、成员节点MEN。节点以最大功率发送链路请求,邻居节点收到信息后,更新自己的邻居信息表NBLIST,其中记录信息有:邻节点ID、连通度、节点状态(UNCLUSTERED、HEAD、MEM)、簇头节ID(当邻居状态为MEM时此值有效)。一次广播后,所有节点获得自己所有邻居的ID,计算自己的连通度(邻节点个数)。
2)簇头形成阶段
根据连通度从大到小依次选举出簇头节点将状态改为HEAD,并向一跳邻居广播带有本节点ID的HeadD消息,收到HeadD消息的邻居修改NBList中相应条目,如自身状态为UNCLUSTERED,则将状态置为MEM,并向一跳邻居广播JOIN消息,JOIN消息中带有本节点ID和要加入簇的簇头ID。收到JOIN信息的节点修改NBList中相应条目,如果自己是JOIN信息声明的簇头,则将簇成员个数加一,并根据式(3)计算的成员节点个数以及能量模型(2),调节簇头节点发射功率,使成员节点数量不超过计算值并选举下一簇头,依止下去,直到所有的节点都加入簇。
3)信息传递阶段
在簇结构形成之后,根据多跳和信息融合的原理,依据式(4)计算的权值,由prim算法生成最小生成树,担任数据转发功能,完成信息传递。
4)维护阶段
在一个周期T后,按照式(6)所示的成簇请求概率发出本地簇重选信息,如果此概率值到到阀值,则传播给自己的邻居节点,邻居节点根据各自的剩余能量,以及距离sink节点的距离再次选举簇头节点。使簇内能量消耗平衡。
2.3 算法说明
如图2所示的拓扑算法原理图,图2(a)初始生成的拓扑以最小功率建立,v担当节点u、j、k的数据转发节点,根据上述的功耗分析,节点v的功率要比节点u、j、k消耗快,在一个周期后拓扑v首先发出调整概率Pv,u、j、k收到调整信息后,重新计算本地信息调整拓扑,如图2(b)所示,节点v在进行局部拓扑重构后,发射功率明显降低,这样就实现了节点u、v、j、k功率消耗的均衡。
3 仿真与性能分析
假定有50个传感器节点随机分布在50m50m的二维空间内。周期性观察整个网络中转发两个节点数据、转发一个节点数据、无数据转发、簇头u和簇头v等节点的能量消耗过程,如图3所示,节点u和节点v在算法作用下的能量消耗曲线,可以看出,节点u和节点v的能耗时间相对于始终担当数据转发任务的节点明显延长。
4 结论
该文研究了无线传感器网络分簇算法中担当簇头的传感器节点的能量消耗规律,提出了簇头节点与成员节点的变换机制,通过变换机制,可有效地延长网络的生命周期,并得出如下结论。
(1)将平均分簇引入到分簇算法中,可有效解决簇间成员数不平衡的问题,有效延长网络生命周期。
(2)随着节点能量的消耗,适当调整节点转发链路的数量,或是簇头节点变换成成员节点,可有效地提高网络的生命期。
矿井下无线传感器网络分簇算法研究 第6篇
利用无线传感器网络组建的井下安全监测系统通过使用功能不同的节点,随时掌握井下人员的动态分布。系统中,人员节点借助信标节点将井下人员的位置信息传送到控制台从而了解矿井下的情况。由于在煤矿主巷道、人车、采掘工作面等区域人员较为密集,当多个人员节点同时与信标节点通信会造成信号冲突,甚至导致网络处于瘫痪,通信无法进行。为了避免通信冲突,可采用不让每个人员节点都向信标节点发送信息,而只从中选出一个代表向信标节点发送信息,即采用成簇来解决这一问题。
2 相关工作
近年来,研究人员提出了多种传感器网络的分簇算法,其中W.Heinzelma等人提出的低功耗自适应分簇算法LEACH[1]。LEACH有效的节省了能量消耗,但它没有考虑到节点分布的拓扑结构和节点的能量问题,这种情况下簇内的能量消耗并不是最优值。文献[2]应用粒子群算法解决网络分簇问题,提出均匀分簇的思想以最小化节点能耗。但对于节点分布不均匀的网络,这种分簇方法可能造成各簇数量规模相等。而几何规模差异较大的情况,会造成簇间消耗能量不均。文献[3]提出一种具有能量感知能力的分簇策略,采用PSO算法优化选择分簇方式,既最小化簇内距离,又最优化网络能耗,有效延长网络生存周期。但它没有考虑簇头节点传输信息至基站时的能耗不均,易导致距离基站较远的节点成块死亡,网络能量消耗不均衡。如Thanongsak H.提出通过中继传输来延长网络的生存期,也有少量的文献研究分簇路由中的簇内通信方式,如孙勇等[4]提出了时分混合通信方案,张志东等[5]提出楔形多跳方案减小网络能耗。
本文根据井下分簇的要求,把节点与簇首的位置误差和通信能耗作为优化目标函数的主要指标建立传感器节点成簇的数学模型,通过采用最近邻进行初始成簇并采用粒子群优化算法实现节点重新组簇,尽可能快地得到最优成簇结果。
3 节点成簇目标函数设计
3.1 节点成簇能耗考虑
节点的能量消耗一般由感应、数据处理、节点间的通信三方面构成。而占能量消耗主体的就是节点之间的通信能耗,因此在算法评估时只考虑通信能耗,忽略其他能耗;本文运用无线电通信模型,通信能耗表示为式(1):
节点接收lbit长度数据所消耗能量为:
其中Eelec表示发射电路损耗的能量。若传输距离小于阈值r,则功率放大损耗采用自由空间模型;若传输距离大于等于阈值r,采用多路径衰减模型。εmp、εfs分别为两种模型中功率放大所需的能量。由此可见总能量E主要取决于d,通信能量消耗最小化可以等效为d之和最小化。
而距离的测量,由于受传播环境的影响,电磁波在井下的传播不能用自由空间传播模型来描述,从文献[6]可知,一种对数正态分布模型可对电磁波井下传播与式(3)近似。
式中,RSSI(d)表示节点接收的信号强度,单位为d Bm;PT为传送信号的强度,PT取-45d Bm;d0是相对于人员节点的参考距离,d0取1m;Pr(d0)是该参考点处的信号功率。α则通常是由场地测量得来的经验值。而Xd B服从均值为0,方差为σd B的正态分布,但是在确定环境中的传播路径,则与确定的Xd B相对应。在实验环境中,用两块CC2430模块多次测量不同距离下RSSI值,通过估计得到相应的α与Xd B。
实验中设定d0为1m,测得Pr(d0)=-56d Bm。根据多元回归分析可得α=2.8305,Xd B=40.9388。再通过式(3)可实现RSSI到d的转换。
在矿井人员跟踪过程中,在初始时刻,为保证所有人员节点不丢失,根据实际要求,将接收到相同信标且信号强度最强的节点组成一簇,此时该信标节点相当于一个临时簇首,保证所有人员节点都可以与信标节点进行通信;当然,还要在人员节点中选择一个真正簇首节点。当每个簇选出一个真正簇首时,可以用式(4)描述成簇关系矩阵:
在矩阵A中,行数表示人员节点个数;列数表示簇首节点个数。amn为0-1变量,amn=1表示第n(n=1,2,,N)个节点加入第m个簇中,即加入簇首节点m(m=1,2,,M)所在的簇里,否则amn=0。这里能耗数学模型可以描述为式(5):
其中,要求一个人员节点只能参加一个簇。即
dmn表示第m个簇首节点与第n个人员节点之间的距离,为使得能耗指标最小化,保证簇内所有人员节点至所选簇首节点之间距离之和最小。
3.2 节点位置误差考虑
对于k个固定信标节点B1(x1,y1),B2(x2,y2),,Bk(xk,yk),人员节点M(x,y)至信标节点的距离分别为d1,d2,,dk。这里若只考虑两个信标节点B1,B2,假设两节点的质心在B12,位置为(x12,y12),B12到B1和B2的距离分别为d1,d2。显然可知存在(x12-x1)/d1=(x12-x2)/d2和(y12-y1)/d1=(y12-y2)/d2。得x12=(x1/d1+x2/d2)/(1/d1+1/d2),y12=(y1/d1+y2/d2)/(1/d1+1/d2)。其中,1/di为权值,体现出距离人员节点距离近的信标节点的权重大,其误差比较小;而距离人员节点距离远的信标节点的权重小,其误差比较大,选择加权因子能体现各个信标节点对于人员节点位置的决定权的大小,其约束力符合加权质心算法的要求。若把人员节点接收到RSSI值的范围在-56d Bm～-98d Bm之间的信标节点加入考虑,则得:
在井下信息化管理系统中,为了实时监控井下人员,在大多数情况下,只要求人员节点每隔一个不长时间就与信标节点传递一次确认信息。保证人员节点在一段时间内不丢失,而不需要知道确切位置,簇首在信标节点传输信息时,把簇首节点的位置信息作为全簇节点的位置信息。也就是说,簇首只向信标节点发送簇首的位置信息及全簇成员的ID号即可。但在一些需要知道某个簇成员相对确切位置时,节点相对于簇首的选择就非常重要。
对于簇首的选择,在得到节点位置后,根据文献[7]对通信模型(1)、(2)的研究,单个簇与信标节点通信总能量消耗最小的满足条件,即信标节点、簇首、簇的质心在同一直线上。假设信标节点位置为(0,0),理想簇首位置为(xCH,yCH),簇内节点的位置为(xi,yi),簇内节点总数为n(包括簇首),则有下列等式:
其中,ρ满足下面关系
由(8)、(9)两式可以计算出理想簇首节点的位置(xCH,yCH),那么,距离该点最近的节点应该被选为簇首(xchm,ychm)(m=1,2,,M),m为第m个簇。
则人员节点位置误差可以表示为:
ermn表示第n个人员节点与第m个簇首之间的位置误差。由于一个人员节点只能参加一个簇。因此,基于人员节点位置误差的数学模型设计为:
在完成簇首选择后,根据粒子群算法综合考虑通信能耗和节点位置误差重新成簇。成簇目标函数可以设计为式(11),以保证节点通信能耗与位置误差最小。
4 基于粒子群的分簇算法
粒子群优化是通过个体之间的协作寻找最优解的计算技术。算法数学描述为:假设在一个D维的目标空间中,有N个代表潜在问题解的粒子组成一个群,其中第i个粒子表示为一个D维的向量,Xi=[xi1,xi2,,xiD],i=1,2,,N;第i个粒子在D维搜索空间中的位置是Xi,飞行速度是Vi=[vi1,vi2,,viD];记Pi为第i个粒子迄今为止搜索到的个体最优位置,Pi=[pi1,pi2,,piD];记Pg为粒子群迄今为止搜索到的全局最优值,Pg=[pg1,pg2,,pgD];每次迭代中粒子按照式(12)、(13)更新速度与位置,则:
式中,i=1,2,N;t为迭代次数;w为加权因子,取值在0.1～0.9之间,c1,c2为学习因子,分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长;r1,r2是[0,1]之间的随机数。粒子通过不断学习更新,最后找的Pg就是全局最优解。
然而无线传感器网络成簇问题是一个离散型问题,基本的PSO算法是针对连续问题设计的,要解决成簇问题,需要设计一个求解离散问题的PSO算法。具体算法设计如下。
4.1 粒子群初始化
4.1.1 位置的定义
粒子的位置X代表分簇方案,可以表示为X=(X1,X2,,Xj,,XM),1jM;Xj=(xj1,xj2,,xji,,xjN),1iN。在对粒子的位置进行更新时,粒子的位置X为一个用元素为0或1的位置矩阵。
其中,M表示簇首个数,N表示人员节点个数。其中,xji=1表示第i个人员节点加入第j个簇中,xji=0表示第i个人员节点个数不加入第j个簇中。
4.1.2 速度的定义
离散空间的速度不再是连续空间所说的速度,而是用来计算粒子的位置变化的概率值,粒子的速度用一个矩阵来表示:
vji∈[-vmax,vmax],j∈{1,2,,m},i∈{1,2,,n},由于速度是一个表示粒子的位置变化的概率值,它被限制在[0,1]之间。
4.2 确定适应值函数、个体极值和全局极值
在粒子群算法中,适应值函数作为评价标准必须要能够反映所要求解问题的目标要求以及约束限制。这里将适应值函数取为目标函数。同时,根据无线传感器网络分簇的具体问题,进行条件限制。其次,计算粒子所经历的最好位置pbi(t),也就是粒子所经历过的具有最好适应度的位置,由式(14)确定:
并计算群体中所有粒子经历过最好位置,即全局最好位置,由式(15)确定:
最后,依据粒子群公式对粒子的速度和位置进行进化。算法流程如图1所示:
4.3 算法仿真
仿真过程中,在120m120m监测区域内,实验中将120个传感器随机分布于监测区域内模拟120个井下人员,另外在监测区域上下两侧各安放4个信标节点。设节点的探测半径R=60m。实验中采用一组参数如下:εmp=0.0013p J、εfs=10 pJ,根据计算可得簇首节点位置。采样间隔为1秒;粒子群参数w=1,c1=c2=2,循环次数n=100;仿真结果如下图所示:图中各种相同形状节点表示簇节点,簇首节点用五角星型表示,图2为根据与信标节点的位置,采用最近邻的初始化分簇,从而形成8个簇。图3为基于能耗和位置误差考虑重新成簇的结果。
根据表2可知,在不同分簇算法的能量消耗中,采用最近邻方式进行初始化分簇时总能量消耗用距离表示为2082m,而基于能耗和位置误差考虑的分簇的总能量消耗用距离表示为2128.2m;此能耗与采用最近邻的初始化分簇相比,提高了2.22%。而各个簇的位置误差如表2所示,其中,采用最近邻方式进行初始化分簇,此时总位置误差为495.5887m,而基于能耗和位置误差考虑的成簇的总位置误差为458.3910m;在位置误差上与采用最近邻的初始化分簇相比,提高了8.11%。在煤矿井下非常密集的区域,尤其在上下班的高峰时段,基于能耗和位置误差考虑的分簇算法,在定位精度上更占优势,更有利于煤矿井下人员跟踪定位的要求。
5 结论
本文在无线传感器网络节点能量、存储、带宽资源受限的条件下,重点从通信能耗和位置误差的角度,通过建立无线传感器网络分簇的综合性能指标,利用离散粒子群优化算法,在实现有效的分簇同时,保证定位精度,达到煤矿井下通过传感器节点之间的高效协同实现人员跟踪的目的。
参考文献
[1]Heinzelman W,Chandrakasan A,Balakrishnan H.Anapplication-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.
[2]Tillett J,Rao R,Sahin F.Cluster-head Identification in Ad hoc Sensor Networks Using Particle Swarm Optimization[C]//Proc.Of IEEE International Conf.on Personal Wireless Communications.New Delhi,India:[s.n.],2002.
[3]Latiff N M A,Tsimenidis C C,Sharif B S.Energy-aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization[C]//Proc.of the18th International Symposium on Personal,Indoor and Mobile Radio Communications.Athens,Greece:[s.n.],2007.
[4]孙勇,景博.分簇路由的无线传感器网络通信模式与能量有效性研究[J].电子与信息学报,2007,29(9):2262-2264.
[5]张志东,孙雨耕.无线传感器网络能量模型[J].天津大学学报(自然科学版),2007,40(9):1029-1034.
[6]Chahe Nerguizian,Charles L.Despins.“Radio-Channel Characterization of an Underground Mine at2.4GHz”.IEEE Transactionsons on wireless communications,Vol4,No.5,SEPTEMBER2005:2441-2453.
分簇算法 第7篇
1相关研究
1.1分簇路由算法分析
为了提高整个网络的的生存时间,将功耗均衡的分配到网络中的每个节点,Wendi Rabiner Heinzelman等人提出了一种低功耗的自适应路由协议,LEACH协议(Low-Energy Adaptive Clustering Hierarchy)[5]。在LEACH协议中,每个传感器节点都有机会充当簇首节点,簇首节点的选择主要依据网络中所需要的簇首节点个数与到目前为止每个节点已经充当过簇首节点的次数来判定的。网络中每个节点在0到1之间随机选择一个数,如果选择的数小于规定阀值T(n),则该节点就充当为簇首节点。T(n)的计算如式(1)所示。
undefined
(1)
式(1)中,p表示无线传感器网络中簇首节点所占的百分比,r为当前循环次数,G是在前1/p轮中未充当过簇首节点的集合。LEACH算法通过设置T(n)值,以保证每个节点在1/p轮内都有机会充当一次簇首节点,从而平衡了节点的能量消耗。簇首节点确定之后,簇首节点通过广播告知整个网络自己已经成为簇首节点,簇首节点在广播过程中采用CSMA MAC 协议来避免冲突。这时网络中的非簇首节点可以根据接收到的信号强度来决定自己要从属于哪个簇,选择信号强度最强的源节点作为自己的簇首节点,并告知相关的簇首节点,自己已经成为该簇首节点的簇内组员。
LEACH算法缺点:
1.每个节点成为簇首节点的概率相同,这样可能导致一些高能量节点没有机会成为簇首节点,而一些低能量节点成为簇首节点,一旦低能量节点成为簇首节点,将会很快耗尽其能量。
2.LEACH协议不能保证簇首节点在每个区域都分布均匀,虽然统计上面是均匀的,但是由于簇首产生带有极大的随机性,有些区域簇首节点数目会较多。
3.簇首节点在通信过程中采用单跳与基站通信,这样就会导致较远的簇首节点能量消耗过大,而过早的死亡,影响整个网络的性能。
4.在有些运用场合中,如无线测距网络,传输数据量不多,簇首节点进行数据融合可能消耗的能量会更多。
1.2时间同步算法分析
无线传感器网络中节点因受到成本与功耗的限制,传统的同步方法,如GPS与NTP协议不适合运用在无线传感器网络中[6][7],2002年,Elson等人在HotNets这影响未来网络研究发展方向的国际权威学术会议上首次提出无线传感器网络时间同步的研究课题以来,已有相当多典型的时间同步算法,主要可以分为以下几类,基于发送者接收者的双向同步算法,比较典型的算法如TPSN(Timing-Sync Protocol for Sensor Networks)算法[8]。基于发送者接收者的单向时间同步算法,比较典型的算法如DMTS(Delay Measurement Time Synchronization)算法[9]。基于接收者接收者的同步算法,典型的有RBS(Reference Broadcast Synchronization)算法[10]。
TPSN(Timing-Sync Protocol for Sensor Networks)算法[8],采用的是层次型的网络结构,是基于发送者接收者的双向同步算法。分成两个阶段,第一阶段为层次发现阶段,第二阶段为同步阶段。其算法原理如图1所示。在图1中,T1、T4用来记录同步节点A的本地时间,T2、T3用来记录参考节点B的本地时间。同步节点A在T1时刻向参考节点B发送一个同步请求报文,报文中包含了同步节点的级别和T1,当参考节点B收到报文后,记录下接收时刻T2,并立即向同步节点A回复一个同步应答报文,该报文中包含了参考节点B的级别和T1、T2、回复时刻T3。同步节点A收到参考节点的回复后,记下时刻T4,假设来回报文的传输延迟相同,且其值都为d, m为同步节点在T1时刻两者之间的时偏,且设来回时偏相同,由 T2=T1+m+d , T4=T3-m+d
可得到undefined,undefined
则在T4时刻,若在同步节点A的本地时间增加修正量m,同步节点A就能与参考节点B到达时钟上的同步。
TPSN算法缺点:
从图1中我们可以看出,TPSN算法成对同步一次需要发送两个消息,接收两个消息,能耗较大,TPSN算法采用的是静态分层的拓扑结构,属于集中式同步机制,如果参考节点B在一跳范围内有多个待同步节点的话,则该参考节点必须跟多个节点进行成对同步,我们可想而知参考节点能量将最先耗完。这样就会导致一种现象,就是整个网络中其中一部分节点剩余能量还很多的情况下,一部分节点(参考节点)已经死亡了,这些节点的死亡可能会导致部分节点找不到一跳范围内的上一级节点而失效,大量节点的死亡,必将导致整个网络过早的失效,这样整个网络的功耗就没有得到充分的利用。所以我们应该动态的更换参考节点,以延长整个网络的寿命,提高整个网络的性能。采用分簇的拓扑结构可以有效的减少时间同步包的传输次数、消除多层同步带来的累积误差,提高全网节点的生命周期与同步精度。
1.3节点能量传输模型
节点能量传输模型我们采用公式(2)与(3),式中k为传输信息的比特数,d为节点之间的距离。∈fs为自由空间传送方式下的功率放大参数。式(2)为节点接收数据所消耗的能量,式(3)是发送数据所消耗的能量[5]。
undefined (2)
undefined (3)
2动态分簇时间同步算法(DCTS)的设计
我们针对一些特殊的运用场合,如无线测距网络,传输数据量较少,簇首节点无需进行大量数据融合情况下,对LEACH分簇路由算法进行改进,提出了GLEACH分簇路由算法,并使用GLEACH分簇路由算法将整个网络分成不同的簇,提出了一种动态分簇时间同步协议DCTS算法,新的同步算法以基站与簇首节点为参考节点,采用类似于TPSN双向同步机制,逐级同步,实现全网的时间同步。
2.1LEACH算法的改进GLEACH算法
在图2中,我们假设基站A到节点B、C、D的距离分别为dAB, dAC, dAD,节点B、C到节点D的距离分别为dBD,dCD。针对无线测距网络的特点,传输数据量较少,簇首节点无需进行大量数据融合情况下,对LEACH分簇路由算法进行以下几个改进,改进后的分簇算法我们称之为GLEACH分簇算法。
条件1 如图2左图所示,当dBD>dAD或dAB>dAD时,直接让簇内节点D把数据传输给基站消耗的能量要少于簇内节点D先把数据传给簇首节点B,再转发给基站A消耗的总能量。
证明: 当dBD>dAD时,得到undefinedundefinedelec + kεfs dAD 2
显然我们可以看出当dBD>dAD时,ETxDB>ETxDA,我们知道接收能量是相同的。这样我们就很容易得到当dBD>dAD时,直接让簇内节点D把数据传输给基站消耗的能量要少于簇内节点D先把数据传给簇首节点,再转发给基站消耗的总能量是成立的。同理当dAB>dAD时也是成立的。
条件2:如图2左图所示,当dundefined+dundefined>dundefined时,则直接让簇内节点D把数据传输给基站,比起簇内节点D先把数据传给簇首节点B,在转发给基站A消耗的能量要少。
证明:undefinedundefined
undefined
elec + kεfs dAB 2 ,undefined
则簇内节点D通过簇首节点B转发到基站A消耗的总能量E1为:
E1=ETxDB+ETxBA+2ERx=2kEelec+kεfs(dundefined+dundefined)+2ERx
簇内节点D直接把数据传给基站A所消耗的总能量E2为:
E2=ETxDA+ERx=kEelec+kεfsdundefined+ERx
显然,当dundefined+dundefined>dundefined时,E1远大于E2,证毕。
条件3: 如图2右边所示,假设当dundefined+dundefined>dundefined+dundefined,这时虽然dCD>dBD,我们依然让节点D选择C节点为簇首节点,叠加消耗的能量更小。
证明:同条件2我们可以得到节点D通过节点B消耗的总能量
EDBA为 EDBA=2kEelec+kεfs(dundefined+dundefined)+2ERx
节点D通过节点C消耗的总能量EDCA为EDCA=2kEelec+kεfs(dundefined+dundefined)+2ERx
显然当dundefined+dundefined>dundefined+dundefined,EDBA>EDCA,证毕。采用同样的方法扩展到更多跳数的节点中。
条件4:我们可以根据实际需要指定一个距离d0,当簇首节点与基站的距离超过d0时,不直接与基站通信,而是借助其他簇首节点转发到基站,选择其他簇首节点采用的是最小生成树法,这样就减轻了远离基站的簇首节点负担,也扩展了整个网络的规模。
2.2DCTS算法的设计
根据以上提出的GLEACH算法,结合TPSN算法,我们提出了一种动态分簇时间同步算法,DCTS算法。
(1)首先使用2.1节中提出的GLEACH算法进行层次发现阶段。将整个网络分成多个簇。靠近基站的节点直接传输数据给基站,不需要经过簇首节点,以减少单跳累加对同步精度的影响,远离基站的簇首节点通过多跳传输给基站,因在测距系统中,数据传输量较少,所以簇首节点只起到存储与转发的作用,不进行数据融合作用,以较少不必要的能量浪费。
(2)簇首节点选举结束后,在稳定阶段,经过选举出来的簇首节点、基站作为同步参考节点,在同步阶段首先基站与簇首节点以及一跳内子节点使用TPSN双向同步算法原理同步,待结束后,让簇首节点与其簇内节点以及下一跳簇首节点同步,采用同样的方法逐级同步,最终实现全网的同步。
(3)在下一轮选举簇首节点后,整个网络中参考节点也跟着变换,克服了TPSN算法中参考节点负担过重,而导致这些节点过早的死亡,影响整个网络的生存时间。结合动态分簇路由算法均横了整个网络的功耗,从而延长了整个网络的生存时间。
2.3实验结果分析
根据部分运用场合,簇首节点无需进行数据融合,只起到存储与转发数据的情况下,我们对经典的LEACH分簇算法进行改进,调整了簇内节点加入簇首节点的路径,增加了部分节点直接与基站通信,从仿真图3中,我们可以看出本文改进后的算法GLEACH生存时间要明显优于LEACH算法。由于TPSN算法采用的是集中式层次拓扑结构,我们采用的是动态分簇拓扑结构,采用分簇的拓扑结构可以动态的选择参考节点,避免部分节点负担过重,过早死亡,从而均衡了整个网络的功耗,延长了整个网络节点的生存时间。从仿真图4中,我们可以看出本文提出的DCTS算法整个网络节点的生存时间明显优于TPSN算法。DCTS采用分簇的拓扑结构可以有效的减少时间同步包的传输次数、消除多层同步带来的误差累积,提高全网节点的同步精度。从表1与表2中,我们可以看出,本文提出的DCTS动态分簇同步算法,经过分簇后,增加了部分节点直接与基站的同步个数,减少了TPSN算法层次结构单跳累加对同步精度的影响,虽然在最好情况与最坏情况两种同步算法精度差不多,但是在相同跳数下,DCTS算法的平均同步精度要优于TPSN算法。
3结束语
本文的创新在于提出了GLEACH分簇路由算法,不但减少了整个网络的功耗,而且减少了整个网络的传输跳数,结合TPSN同步算法原理,提出了一种动态分簇时间同步算法,DCTS算法,有效的减少了整个网络的同步误差,动态的选择簇首节点(参考节点),与使用TPSN层次拓扑结构,DCTS算法较大延长了整个网络的生存时间,目前关于无线传感器网络测距技术,普遍采用信号强度与信号差往返时间两种方法来测距,前者在理论上较难实现,一般很难在现实中使用,而后者理论简单,但由于硬件成本的限制,只能采用一般的时钟晶振,这时就对节点之间时间同步提出了较高的要求,在某种程度上,测距的精度就依赖于同步的精度。而采用本文提出的DCTS算法,整个网络时间同步精度高,可以构成一个已知节点坐标的参考体系无线定位网络,完全符合一般情况下节点密度高、规模不大的测距定位系统要求。
参考文献
[1]孙延明,刘志远,蔡春丽等.低功耗无线传感器网络节点的设计[J].微计算机应用,2009,30(2):21-25
[2]乔俊峰,刘三阳,曹祥字.无线传感器网络中基于节点密度的簇算法[J].计算机科学,2009,36(12):46-48
[3]陈乔,张毅坤,杨凯峰等.无线传感器网络中同步补偿机制的研究与应用[J].计算机应用,2010,30(4):892-901
[4]任丰原,董思颖,何滔等.基于锁相环的时间同步机制与算法[J].软件学报,2007,18(2):372-380
[5]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].IN:Proceedings of the 33rd Hawaii International Conference on System Science,Hawaii,USA,2000.3005-3014.
[6]P.Sommer and R.Wattenhofer.Gradient Clock Synchronization in Wireless Sensor Networks.In Proc.8th ACM/IEEE Interna-tional Conference on Information Processing in Sensor Networks(IPSN),San Francisco,USA,April 2009.37-48
[7]C.Lenzen,P.Sommer,and R.Wattenhofer.Optimal Clock Synchronization in Networks.In Proc.7th ACMConference on Em-bedded Networked Sensor Systems(SenSys),USA,2009.
[8]S.Ganeriwal,R.Kumar,andM.B.Srivastava.Timing-sync Protocol for Sensor Networks.in Proceedings of the 1st InternationalConference Embedded Networked Sensor Systems(SenSys’s03),ACM press,USA,November,2003.138-149
[9]Su Ping.Delay measurement time synchronization for wireless sensor networks,Intel Research.Berkeley Lab,2003.
