基于能量和传输路径的时间同步算法优化
时间：2022-12-04 17:55:02 来源：柠檬阅读网 本文已影响 人 
王 军， 易柏言， 芦 贺
(沈阳化工大学 计算机科学与技术学院, 辽宁 沈阳 110142)
时间同步技术是当前所有的分布式系统中都需要面临解决的问题，因此对其研究已经十分的深入，有许多成熟的方法被用于解决这一问题.当前，有两个相对成熟的时间同步技术，分别是GPS全球定位系统和网络时间协议.但是由于无线传感器节点能量有限、体积微型，并不适用于此种高功率类型的设备[1]，再加上无线传感器网络节点部署的复杂性和特殊性，GPS无法实现更好的应用.所以，对于无线传感器网络有专家提出了特殊的时间同步算法，例如由MIT的Heinzelman等提出的低功耗自适应分簇算法LEACH[2].其分簇过程主要分为两个阶段：第一阶段是对传感器节点进行分簇；
第二阶段是分簇之后进行簇内与簇间的信息交换.具体过程为：簇首节点的选择根据无线传感器对簇首节点的期望数值和到目前为止节点未成为簇首节点的轮数决定，先给每个节点随机分布一个0到1之间的数值，若该数值小于阈值T(n),那么该节点成为本轮的簇首节点，然后剩下的节点根据簇头节点广播的讯息选择加入对应的簇，形成一个完整的簇群[3-4].对节点进行分簇之后，每个簇中所有的子节点都需要发送各自的时钟讯息给簇首节点，再由簇首节点向外进行通讯.在其基础上改进的DEEC算法，在能量异构的无线传感器网络(wireless sensor network with heterogneous energy)中，每个节点都有一个初始的能量值，但每个节点的能量值都不同，在节点进行传输数据的时候都消耗能量，在能量消耗完全之后节点死亡，这时候要补充新的节点.其在进行分簇的时候，是根据节点当前轮数剩余能量和网络平均能量的比值来定义节点成为簇头的概率[5].
对于LEACH算法，其存在的问题是虽然采用了周期性轮巡的机制来选举簇头，使节点都有可能成为簇首节点，但是没有考虑到节点剩余能量和簇首产生数目不稳定的情况；
DEEC算法是在LEACH算法的基础上增加了节点剩余能量与平均能量的比值来限定成为簇首节点的概率，但是其没有考虑到网络能量消耗并不是均匀的，与实际的情况不符合.而且LEACH算法和DEEC算法在进行时间同步的时候都是根据节点广播其时钟讯息的方式进行同步，在节点广播的时候其是和节点网络中所有的节点进行通讯，这就使得距离越远的节点其通讯的时间越长，导致时间同步的精度降低.本文针对节点能量消耗以及通讯路径的问题，提出一种改进算法.因为节点的发送频率和传输距离与其损失能量有关，所以计算出一个相对值，可以让其在最优距离内发送信息，这样既降低了节点的能量消耗，同时使总体网络所需要进行时间同步的时间缩短.
1.1 时间同步相关理论
时间同步技术是无线传感器网络各类应用运行的重要条件之一，其时间同步精度关乎着应用的功能质量.而保持一个全球性的时间同步时钟对无线传感器网络在军事防控、控制工业、检测环境、医用治疗等诸多方面的应用起着至关重要的作用.
基于接收者-接收者机制的时间同步算法[6]：全面考虑无线链路层广播信道自身的特点，利用一个节点发送广播的分组信息，与该节点所处同一个广播域的其他节点同时接收广播的分组信息，并利用各自本身的本地时钟记录所收到的广播分组信息时间，并将彼此各自记录的时间交换，通过分析比较和设计达到时间同步，即实现每一个节点间的时间同步.基于成对同步的双向时间同步算法：发送者发出同步请求信息，接收者回复应答信息，发送者依据分组中的时间信息估算同步的参量差并调成统一的本地时钟，完成节点的同步.基于发送者-接收者的单向时间同步算法：首先由发送节点发出一个包含自身的本地时间信息的时间同步分组，接收节点用本地时间记录接收到此包含自身本地时间信息的分组后分析提取同步分组的时间戳，然后调整自身的本地时钟与发送节点的时钟达到一致，实现时间同步.
1.2 时间同步性能指标
(1)能量效率：时间同步算法要求标准的时钟源需要在周期内向网络发送同步信息，而同步的周期越长，需要发送的信息数量就越少，消耗的能量也就越少.所以时间同步算法应该尽最大可能减少信息的延迟问题，提高每一次瞬间的时间同步精度，并且在非同步周期时对时钟发生偏移进行补偿，并在误差标准范围内延长同步周期[7].
(2)可扩展性：无线传感器网络中节点的密度会影响时间同步的效率，设计一种能够适应无线传感器网络节点密度变化问题的算法具有实际价值和现实意义.
(3)同步精度：在无线传感器网络应用中，对时间同步的精度要求不同，有的要求达到高程度精度上的时间同步，有的要求达到普通程度精度上的时间同步[8].
(4)鲁棒性：无线传感器网络节点经常需要布置在环境复杂或者人迹稀少的地方，并且常常受到恶意攻击，如果时间同步算法不具备一定的安全性措施，节点受到攻击之后所采集的信息无法保证准确，直接影响人们对当地情况的判断和预测.
(5)同步周期：同步周期是指在误差标准范围内，无线传感器网络节点保持时间同步的时间长短.当对此方面要求不高时，可以选择在需要同步的时候进行时间同步；
如果对时间同步需求很高，需要实时性采集信息，则需要节点时刻都保持时间同步.因此，同步周期根据环境的不同而改变.
(6)同步范围：根据无线传感器网络应用在不同环境的情况，有的需要全部网络上实现时间同步，有的需要局部区域上的时间同步.
对传统分簇时间同步算法存在的问题进行改进与优化，提出一种基于能量选择和最优传输距离的分簇时间同步算法CSET(clustering time synchronization algorithm for energy selection and transmission path).此算法考虑到节点的初始能量和在进行数据传输时所消耗的能量，并且根据最优的传输路径算法进行簇间同步，具体步骤如下：
(1) 因为所有散布的节点属性不同，所以需要对其各个属性(功耗、频率、电压)的单位进行统一，划分为不同的类别方便计算.
(2) 对随机散布的无线传感器节点进行初始能量统计，集合为U，并对集合内所有节点的能量进行统计，计算所有节点能量的平均值：
(1)
(4) 对于处于P集合内的节点，根据LEACH算法进行分簇，分簇之后进行簇间同步.因为节点的发送频率不同，所以需要损耗的能量也不同，根据节点发送频率和损失能量的关系可以算出最优的传输距离，根据这个传输距离使得节点在这个范围内进行同步，如公式(2)所示.
Ei损=20 lgF+20 lgD+32.4.
(2)
其中：F为节点的频率;D为节点之间的距离.
(5) 计算节点之间的欧式距离：
D=minDi，j.
(3)
其中：Di,j表示节点之间的欧氏距离;x表示节点的横坐标;y表示节点的纵坐标;z表示节点的垂直坐标;D表示节点间距离的最小值.
(6) 根据步骤(4)和步骤(5)可以选择节点之间传输数据的最优路径.如图1所示，A、B、C、D、E为簇首节点.传统的算法是通过广播的形式进行讯息交流，A簇首节点如果发送讯息，与其通讯距离越远的节点接收信息所消耗的时间越长，这样就使得总体网络的时间同步变慢.而通过对节点发送频率以及传输距离的计算，规定其一个最优的传输距离，即A与B、C节点通讯，再通过B节点与D节点和D节点与E节点通讯，通过这样的路径进行讯息交流，就可以缩短同步所需要的时间.
图1 簇首节点最优路径Fig.1 Optimal path of cluster head node
Ei剩=Ei初-Ei损.
(4)
传统的分簇式时间同步算法，是对每个节点随机分配一个0到1之间的数，然后通过概率选举的方式选举簇首节点[9].但是，这种随机概率的选举方式会使某一节点的能量过度消耗，而其他节点却没有当选簇首节点，导致节点的冗余，造成整个节点网络的浪费.基于能量选择和最优路径的CSET算法，增加能量选择公式，其可以根据节点的能量来限制当选簇首节点的范围.节点能量高于平均值则可以当选为簇首节点；
节点能量低于平均值则不可以当选为簇首节点.该算法进一步地使得节点网络中各个节点的能耗达到平均，并且根据最优路径选择公式，计算簇首节点之间进行通讯的路径，降低因路径过远而造成的节点能量的损耗和缩短同步整体网络所需要的时间.
通过能量选择和最优路径进行时间同步的优化和改进，并且通过对该算法进行仿真，验证了该算法的性能.对在范围为200 m×200 m的区域中随机散布的400个基于IEEE802.15.4的节点进行研究，此400个节点可以有效去除所有可能发生的偶然性，如图2所示.
图2 区域内节点分布Fig.2 Node distribution in the selected area
通过对LEACH算法、DEEC算法、CSET算法的节点能量消耗做仿真，发现CSET算法比其他两种算法在控制节点能量消耗造成节点死亡的方面可以做到有效控制，延缓整个节点网络瘫痪的过程.由图3可知：LEACH算法在进行第600轮簇首选举之后有节点开始死亡，DEEC算法在第700轮簇首选举之后有节点开始死亡，而CSET算法虽然在节点死亡的起始阶段与DEEC算法相差不大，但是提高了节点存活的时间，使得整个节点网络的寿命得到增加.
图3 存活节点数与轮数的关系Fig.3 The relationship between the number of surviving nodes and the number of rounds
通过对LEACH算法、DEEC算法和CSET算法的能耗进行对比可知:在初始的时候3种算法节点消耗的能量大致相同，但是在1500轮选举之后，CSET算法明显可以更加节约节点能量，使得网络寿命更长，如图4所示.
图4 能量消耗与轮数的关系Fig.4 The relationship between energy consumption and the number of rounds
通过对LEACH算法、DEEC算法和CSET算法的同步误差做对比可知:DEEC算法因为在LEACH算法中加入了能量对比的计算，使得节点的运算量增大，造成时间同步的误差加大.而CSET算法也因为运算量增多，所以，在300节点数之前同步误差大于LEACH算法和DEEC算法.但是在300节点数之后，因为节点的分布范围变大，节点之间的通讯距离变大，使得LEACH算法和DEEC算法在簇间同步的时候同步误差加大；
而CSET算法因为增加了最优距离筛选的方式，使得节点之间的通讯更加快速，所以，在350节点数之后的同步误差小于LEACH算法和DEEC算法.节点数与同步误差的关系见图5.
图5 节点数与同步误差的关系Fig.5 The relationship between number of nodes and synchronization error
无线传感器网络技术是在21世纪兴起的一门重要技术，而时间同步则是其中最重要的组成部分，它是保障节点通讯、网络协同的关键.无线传感器可以应用到各个方面，而时间同步越准确、越节约能耗，其应用范围就越广，所以，在今后无线传感器网络技术会更加普及.
初步介绍无线传感器网络技术，而其中最主要的是时间同步技术.虽然随着无线传感器网络技术的发展，研究时间同步的人越来越多，但是时间同步技术仍然存在着很大发展空间.时间同步是传感器节点之间协调工作、信息传输的基础，只有基础牢固顶层才会发展得更好.本文主要通过对LEACH算法、DEEC算法和CSET算法进行对比，发现基于能量选择和最优路径的CSET算法可以在节点能量消耗、节点网络寿命和节点网络时间同步方面起到优化作用，延长了节点网络存在的时间，降低节点的能量消耗，并且使时间同步更加快捷.但是还存在着一些缺点，例如：如果节点的初始能量本就很少，那么该节点当选为簇首节点的概率就会很低，会使得节点网络中的部分节点处于冗余状态，造成节点的浪费[10].
猜你喜欢 能量消耗节点无线 分区域的树型多链的无线传感器网络路由算法现代电子技术(2022年4期)2022-02-21基于点权的混合K-shell关键节点识别方法华东师范大学学报（自然科学版）(2019年3期)2019-06-24无线追踪3小猕猴智力画刊(2019年3期)2019-04-19无线追踪小猕猴智力画刊(2017年6期)2017-07-03无线充电我最全汽车之友(2016年14期)2016-07-14热拌沥青混合料生产和施工全过程能耗与排放评价筑路机械与施工机械化(2016年2期)2016-03-12无线充电器中国经济信息(2015年21期)2015-11-12移动基站无线传感器网络优化研究软件导刊(2015年6期)2015-06-24浅谈基于P2P的网络教学系统节点信息收集算法职业·下旬(2009年7期)2009-01-20
