无线传感器网络分布式同步协议

王 晶,张 帅,高 丹,王营冠

(中国科学院上海微系统与信息技术研究所无线传感网与通信重点实验室,上海 201899)

无线传感器网络分布式同步协议

王 晶,张 帅,高 丹,王营冠

(中国科学院上海微系统与信息技术研究所无线传感网与通信重点实验室,上海 201899)

针对无线传感器网络同步问题,提出分布式时间同步和分布式数据同步的解决方法.前者要求簇头网络进行局部信息交互,并采用低通滤波技术去除噪声干扰;后者为节点提供网络数据均值,要求簇头网络执行比例一致性算法,簇头在迭代过程中引入簇内节点数量.实验结果表明,分布式时间同步具备抗噪声能力,该算法在前期收敛速度最快.网格状网络和随机网络实验表明,分布式时间同步和分布式数据同步的通信开销非常低,它们的收敛速度均高于普通数据同步.

无线传感器网络;同步;分簇;通信开销;收敛速度

无线传感网(Wireless Sensor Network,WSN)同步问题主要分为时间同步和数据同步两类.时间同步为传感器节点提供绝对或逻辑时钟,从而服务于任务调度、睡眠机制、数据融合、定位跟踪等应用.考虑用Ti(t)代表节点的本地时钟,则时间同步确保节点时钟满足条件:

时间同步的研究对象分为单跳同步和多跳同步两类.目前,单跳同步模型已经基本确立[1],而多跳同步模型包括自顶向下架构和分布式架构两种设计方案.其中,自顶向下时间同步由根节点发起网内同步,或者沿同步树逐层开展同步,或者通过洪泛方式执行同步,此类架构以降低同步开销和提升同步精度为首要目标[2-3].与此相反,分布式时间同步仅要求节点与邻居进行本地时钟同步,通过分布式算法将局部时间信息扩散至全网络,确保节点获取相同的时钟信息,此类架构具备高鲁棒性和强抗毁性特征[4-6].

在传感网中,数据同步是一种重要的数据融合算法[7],主要为节点提供全网络数据的平均值.考虑用xi代表节点i的测量数据,则数据同步确保节点数据满足

数据同步为时间同步提供基础模型[4-5].由式(1)可知,时间同步要求网内节点共享相同的时钟;由式(2)可知,数据同步不仅要求网内节点共享相同的数值,并且要求该数值等于全网络测量值的平均值.由此可知,数据同步在时间同步的基础上增加了限制条件.另外,数据同步也采用分布式架构实现,尤其适用于节点分布式布设的无线传感器网络.综上所述,数据同步与分布式时间同步的实现方法相一致.

目前,基于数据同步实现的时间同步主要包括全局时钟同步和平均时间同步.前者属于异步算法,节点对邻居时钟取平均并将更新量发送给邻居[4];后者要求节点对邻居时间求和并进行低通滤波,可减少单跳同步噪声干扰[5].在数据同步方面,研究者主要以分析算法的收敛速度为目标.研究者提出奥法提-赛博数据同步(Olfati-saber Data Synchronization,ODS),并指出当网络拓扑保持连通时,该模型可实现网络范围内收敛[8].之后,ODS在特殊场景下的收敛条件也被提出,包括:①有向和无向网络[9];②具有通信时延和拓扑变化的网络[10];③采用二阶分布式平均的网络[11].

上述时间同步基于数据同步实现,而数据同步研究则侧重于收敛速度分析.然而,以ODS为代表的数据同步并没有综合考虑传感网的重要特点:节点规模大,节点能量受限,即节点规模大而导致无线传感网执行数据同步收敛速度较慢,这会增加算法迭代次数,进而增大网络通信负担.因此,笔者重点解决在无线传感网中实现分布式同步的收敛时间和通信开销问题.

1　分布式时间同步协议

笔者提出分布式时间同步(Distributed Time Synchronization,DTS)协议.不同于数据同步,时间同步并不要求节点时钟等于全网上电时刻的均值,这是因为节点时钟会随着时间而不断增长,并且节点间只需要实现逻辑时钟一致即可.因此,利用分簇技术对ODS进行改进,确保算法收敛性能的提升,并减少实现网络同步的通信开销.

图1　信息传递示意图

注意,有时簇头与邻居交换时间时需要引入网关,此时,一种较合理的方式是网关成为参考节点,两相邻簇头同时侦听参考节点的广播,记录收到该广播时的本地时间,并通过网关相互转发时间记录.采用此方案可有效地去除发送端时延,其同步精度较高[1].式中ε代表节点与邻居进行同步时引入的噪声误差,该误差以99.8%的置信度符合高斯分布,并且各误差间相互独立分布,因此式(3)中噪声方差会随着迭代次数不断变大.为有效地去除噪声对算法稳定性的影响,采用低通滤波技术对时钟调整量进行滤波,从而去除高频噪声

分布式时间同步主要分为3个阶段.

第1阶段,协议要求进行网络分簇.分簇需满足条件:获取簇头信息,簇头可覆盖全网络,任一普通节点只属于一个簇头.在无线传感网中,簇头网络的规模远小于原始网络,簇头间为1跳或2跳邻居,2跳邻居簇头需通过中间节点实现通信.分簇是传感网的基本调度和路由算法,用于保证节点数据以较低跳数传达至全网络,该技术的引入不会增加额外通信开销[12].

第2阶段,协议要求簇头网络执行分布式同步,并通过多次迭代更新实现簇头网络同步.如图1(b)所示,节点与邻居进行单跳时间同步,并计算相互间的时钟漂移量.具体表现为,在第k次迭代过程中,簇头i以载波监听多路访问(Carrier Sense Multiple Access,CSMA)方式将时间Ti(k)发送给邻居,同时,各节点也接收并存储来自邻居的时钟信息.在此过程中,簇头i利用介质访问控制(Media Access Control,MAC)层时间戳机制记录本地时钟[2],去除发送/接收端随机时延的影响,之后簇头计算时钟调整量:的干扰,即

其中,μ代表低通滤波器的调节因子,可以对滤波器性能进行调整.通过式(3)和(4),节点可以获取时钟调整量,从而进行本地时钟更新,多次迭代过程后簇头网络将拥有相同的时间[8].

第3阶段,协议要求簇头负责簇内节点同步.簇内同步由多个单跳同步子问题组成,每个单跳同步子问题在一个簇内执行.簇头已经成为具有准确时间信息的根节点,它们通过经典单跳同步算法进行簇内普通节点同步.

分布式时间同步利用簇头代替原始网络执行ODS,协议在保持分布式同步的高鲁棒性的前提下,有效地减少了参与同步的节点数量,从而降低了通信开销.另外,由于簇头网络和原始网络拓扑结构类似,而前者的节点规模远小于后者,尤其是在高密网络条件下,所以在前者执行同步的收敛速度远快于后者[8-9].高收敛速度保证簇头网络的迭代次数低于原始网络,这从另一个角度降低了通信开销.

2　分布式数据同步协议

数据同步能够为时间同步提供理论模型,并且数据同步本身也是一种重要的数据融合算法.然而,ODS算法起源于多智能体领域,并没有考虑到无线传感网覆盖范围广、节点数量多、节点能量有限的特性.笔者提出分布式数据同步(Distributed Data Synchronization,DDS),利用簇头代替普通节点执行数据同步,从而降低了同步开销.考虑数据同步的限制条件,提出新型比例一致性算法,确保节点获取网络数据均值.另外,对分布式数据同步的收敛性能进行了证明,并对其收敛速度进行了详细分析.

分布式数据同步协议的信息传递方向如图1所示.在图1(a)中,簇内节点利用计数器获取本地时钟,或利用传感器获取测量数值,簇内节点将带有自身标识符和初始数值的数据包转发给簇头,簇头统计簇内数值之和,其中C代表簇内各节点的集合,数值X(0)成为簇头的初始估计值.由此可见,簇头估计值代表簇内所有节点的估计值之和.此后,如图1(b)所示,簇头与邻居交换当前估计值.注意,初次交换的数据包需要包含簇内节点数量.之后,簇头I利用邻居估计值计算自身的更新量,即

式(5)与式(3)的不同体现了分布式数据同步与分布式时间同步的不同.在分布式时间同步中,虽然由簇头代替簇内节点执行第2阶段同步,但分布式时间同步仅要求节点间时间一致即可,并不要节点的时间信息等于网内初始上电时间的平均.簇头在获取估计值更新量后对估计值进行更新,即

下面对分布式数据同步的迭代更新阶段进行分析,并结合图论对分布式数据同步的收敛性能进行具体说明.在式(5)中,由于簇头代替簇内节点执行分布式数据同步,所以簇头拥有簇内所有节点估计值的总和,可知簇内任一节点i的更新量等价于簇头估计值求取簇内平均:

考虑用G=(V,E)代表原始网络,用G′=(V′,E′)代表致密网络,其点集合满足V′=V,其边集合满足E′={(i,j)|i∈CI,j∈CJ,I=J∨I∈NJ},则式(7)等于在致密网络中执行ODS[8].考虑原始网络中任一连接边(i,j)∈E,i∈CI,j∈CJ,则有如下两种情况:①I=J,由E′的定义知(i,j)∈E′;I≠J,因为(i, j)∈E,可知CI与CJ相邻,所以I∈NJ,由E′的定义知(i,j)∈E′.由上述分析可知E⊂E′.因为原始网络为无向连通图,可知致密网络也属于无向连通图,由式(7)可实现网络数据同步[8],所以式(5)可实现网络数据同步.在式(7)实现网络数据同步后,节点估计值更新量近似为零,节点估计值近似相等,可知xi≈xj,近似等于网络初始值均值,所以,发现簇头估计值呈现比例关系,簇头估计值正比于簇内节点数量.簇内节点数量越多,则簇头估计值越大,所以称式(5)为比例一致性算法.另外,原始网络与致密网络节点规模相同,前者的边密度低于后者,可知在原始网络执行ODS的收敛速度慢于在致密网络执行ODS,所以ODS的收敛速度慢于分布式数据同步.最后,式(6)的加权值δ与致密网络的拓扑结构相关联,假设G′的拉普拉斯矩阵为L′,则L′的特征值满足0=λ′1≤λ′2≤…≤λ′n≤2d′max,其中d′max为G′最大度数,可知第二小特征值λ′2为式(7)的收敛速度指数,而2/(λ′2+λ′n)代表理论最优加权值δ*[9].

最后,分布式数据同步通过减少迭代次数,并降低单次迭代过程的信息交互量来减少实现网络同步的通信开销.在原始网络中用N代表算法迭代次数,用E代表单向边个数,用P代表数据包大小,则ODS所需数据通信量为NE P.相应地,分布式数据同步所需数据通信量为N′E′P.由上述分析可知,分布式数据同步可有效地提升收敛速度,由此可知N＞N′.另外,由分簇算法选择出的簇头数目远低于节点数量,由此可知, E≫E′.通过上述两点,可以发现NEP≫N′E′P.综上所述,分布式数据同步能够有效地减少数据通信量,适用于能效要求高的无线传感器网络.

3　实验结果

为验证算法的有效性,通过MATLAB对算法进行仿真实验,实验场景主要包括网格状网络和随机布设网络.

3.1网格状网络理论性能分析

本实验旨在对比网格网络的单向边数和拉普拉斯图特征值,前者等于单次迭代通信包数量,后者代表网络同步收敛速度.

在图2中,采用贪心算法选择簇头[2],簇头网络的单向边数综合考虑簇头直接相连和经过网关节点中转两种情况.如图2(a)所示,原始网络边数量远高于簇头网络,ODS要求原始网络节点与邻居交换数据,分布式时间同步和分布式数据同步要求簇头网络节点与邻居交换数据,因此笔者所提算法具有更低的单次迭代

图2　网格状网络的性能

数据交互量,它们的通信开销非常低.图2(b)显示同步理论收敛速度,该速度由收敛指数λ2和加权值2/ (λ2+λn)的乘积来表示.在相同拓扑结构下,节点规模越大,则λ2越小.所以,3种算法的理论收敛速度整体上均随着网络规模的增大而降低,并且原始网络的理论收敛速度慢于簇头网络的.在相同网络规模下,边密度越大,则λ2越大.由图2(a)可知,原始网络的边密度远小于致密网络的,所以原始网络的理论收敛速度慢于致密网络的.另外,簇头网络执行数据同步的速度略微快于致密网络的.综上所述,在网格状网络中,ODS的理论收敛速度慢于分布式时间同步和分布式数据同步的,而分布式时间同步的收敛速度略微快于分布式数据同步的.

3.2网格状网络噪声干扰分析

以下对分布式时间同步的抗噪声性能进行验证.实验场景为6×6网格状网络,实验对象包括无噪声干扰条件下执行ODS;-30 dBw噪声干扰条件下执行ODS;-30 d Bw噪声干扰条件下执行分布式时间同步,利用低通滤波器过滤数据更新量.图3曲线代表全网络数据标准差随着迭代次数的变化情况,其中参数设定:迭代步长为3,统计次数为100,噪声功率为-30 dBw,滤波因子为0.1.如图3所示,在无噪声干扰条件下, ODS的结果随着迭代步数的增加而持续降低;在-30 d Bw高斯噪声干扰条件下,ODS和分布式时间同步均在一定迭代次数后出现不继续收敛现象,这是由于高斯噪声干扰的叠加效果引发的.然而,当存在噪声干扰时, ODS的收敛精度始终低于分布式时间同步,这说明后者具备抵抗噪声的能力.另外,考虑迭代次数低于13的情况,发现分布式时间同步的收敛精度在3类场景中最高,这说明该算法在前期收敛速度最快,在同步精度要求不高的无噪声干扰场景中可以代替ODS.

图3　噪声干扰条件下的协议性能

3.3随机布设网络实验

本实验在随机网络中执行,网络大小为(100,100),节点数量为301,节点通信半径为20,网内节点含有随机分配的0～1之间的数值.

图4(a)为随机网络节点分布图.由图可知,网络中所有节点均为随机分布,分布式贪心算法选择出的簇头均匀分布在网络中,簇头网络可覆盖所有网内节点.图4(b)为网络标准差跟随迭代次数的变化情况,通过图中曲线可知,3种算法均可保证网络标准差不断减少,能够实现网络数据同步.

图4　随机网络实验结果

图5为簇头数据跟随迭代次数的变化统计,直观展示了网络数据同步现象.通过3幅子图可知,3种算法均可保证网络数据不断趋于同步.

图5　簇头节点随迭代次数变化情况

需要注意的是,图4(b)结果显示,分布式时间同步的收敛性能优于ODS的,而分布式数据同步的收敛性能优于分布式时间同步的,这与图2(b)的理论收敛速度结果不完全一致.这是因为,一方面如图4(b)和图5所示,ODS和分布式时间同步的初始状态相同,其初始状态代表簇头的初始分配值,而分布式数据同步的初始状态更加集中,其初始状态代表簇内数据均值;另一方面,分布式数据同步等价于在致密网络中执行ODS,分布式数据同步尤其适用于大规模多跳无线传感网.另外,图5(a)中有一个明显的锯齿波形,该波形由图4(a)中大黑点产生,该簇头的特点是它位于网络中间区域,此类节点更多地负责网内数据流动和平均化,其波动体现了网络数据的不均衡特性和数据流动性特征.更进一步,在实验过程中发现理论最优权值并非最优,对3种算法来说,其最优权值分别为ODS中,分布式时间同步中,分布式数据同步中,其中和分别代表原始网络、簇头网络和致密网络理论最优权值.表1所示为原始网络和簇头网络连接边数量对比,由表可知,图4(a)随机网络包含4 784条边,每次迭代过程需要发送9 568个数据包.在簇头网络中,直接相连的簇头间有10条边,通过网关节点中转的簇头间有24条边,簇头网络中边的数量为10+24×2=58,每次迭代过程需要发送116个数据包.通过数据可以看出,分布式时间同步和分布式数据同步能够大幅度地降低数据通信开销.

表1　不同网络边数量统计

4　结束语

笔者提出分布式时间同步和分布式数据同步协议,以降低算法通信开销和提升算法收敛速度为目标.网格状网络实验表明,分布式时间同步和分布式数据同步利用簇头网络代替原始网络执行分布式同步,前者的边密度远小于后者的,因此分布式时间同步和分布式数据同步可大幅度地降低网络负载.分布式时间同步在簇头网络执行普通数据同步ODS,簇头网络节点规模远低于原始网络的,分布式时间同步的理论收敛速度快于ODS的.分布式数据同步在簇头网络执行比例一致性算法,等价于在致密网络执行ODS,致密网络边密度远高于原始网络的,分布式数据同步的理论收敛速度快于ODS的.另外,噪声干扰环境实验表明,分布式时间同步具备抗噪声能力,该算法在前期收敛速度很快.最后,随机网络实验表明,分布式数据同步的收敛速度快于ODS和分布式时间同步算法的,其原因在于分布式数据同步利用簇头进行簇内数据求和,等价于一次簇内数据平均化.

[1]HEIDARIAN F,SCHMALTZ J,VAANDRAGER F.Analysis of a Clock Synchronization Protocol for Wireless Sensor Networks[J].Theoretical Computer Science,2012,413(1):87-105.

[2]WANG J,ZHANG S,GAO D,et al.Two-hop Time Synchronization Protocol for Sensor Networks[J].EURASIP Journal on Wireless Communications and Networking,2014,2014(1):39.

[3]王晶,张帅,高丹,等.无线传感器网络扩张型时间同步协议[J].西安电子科技大学学报,2015,42(2):133-139. WANG Jing,ZHANG Shuai,GAO Dan,et al.Expansive Time Synchronization Protocol for Wireless Sensor Networks [J].Journal of Xidian University,2015,42(2):133-139.

[4]LI Q,RUS D.Global Clock Synchronization in Sensor Networks[J].IEEE Transactions on Computers,2006,55(2): 214-226.

[5]SCHENATO L,FIORENTIN F.Average TimeSynch:A Consensus-based Protocol for Clock Synchronization in Wireless Sensor Networks[J].Automatica,2011,47(9):1878-1886.

[6]师超,仇洪冰,陈东华,等.一种简单的分布式无线传感器网络时间同步方案[J].西安电子科技大学学报,2013,40 (1):93-99. SHI Chao,QIU Hongbing,CHEN Donghua,et al.Simple Distributed Time Synchronization Scheme for Wireless Sensor Networks[J].Journal of Xidian University,2013,40(1):93-99.

[7]XIAO L,BOYD S,LALL S.A Scheme for Robust Distributed Sensor Fusion Based on Average Consensus[C]//Fourth International Symposium on Information Processing in Sensor Networks.Piscataway:IEEE,2005:63-70.

[8]OLFATI-SABER R,FAX J A,MURRAY R M.Consensus and Cooperation in Networked Multi-agent Systems[J]. Proceedings of the IEEE,2007,95(1):215-233.

[9]OLFATI-SABER R,MURRAY R M.Consensus Problems in Networks of Agents with Switching Topology and Timedelays[J].IEEE Transactions on Automatic Control,2004,49(9):1520-1533.

[10]WANG X,SABERI A,STOORVOGEL A A,et al.Consensus in the Network with Uniform Constant Communication Delay[J].Automatica,2013,49(8):2461-2467.

[11]WEN G,HU G,YU W,et al.Consensus Tracking for Higher-order Multi-agent Systems with Switching Directed Topologies and Occasionally Missing Control Inputs[J].Systems&Control Letters,2013,62(12):1151-1158.

[12]YU J,QI Y,WANG G,et al.A Cluster-based Routing Protocol for Wireless Sensor Networks with Nonuniform Node Distribution[J].AEU-International Journal of Electronics and Communications,2012,66(1):54-61.

(编辑:郭 华)

Distributed synchronization protocol for wireless sensor networks

WANG Jing,ZH ANG Shuai,GAO Dan,WANG Yingguan
(Key Lab.of Wireless Sensor Network and Communication,Shanghai Institute of Microsystem and Information Technology,Chinese Academy of Sciences,Shanghai 201899,China)

Distributed time synchronization and distributed data synchronization are proposed for the synchronization problem in wireless sensor networks.The former requires the cluster head network to execute local information exchange,and it adopts low-pass filtering to remove the noise interference.The latter provides network-wide data mean to nodes,and it requires the cluster head network to execute the proportion consistency algorithm,in which the number of nodes within a cluster is introduced during the iterative process.Experimental results show that the distributed time synchronization maintains anti-noise performance,and that the algorithm converges fast in the earlier stage.Grid-like network and random network experiments show that distributed time synchronization and distributed data synchronization have a low communication overhead,and their convergence rates are faster than that of general data synchronization.

wireless sensor networks;synchronization;clustering;communication cost;convergence speed

TP393

A

1001-2400(2016)04-0105-06

10.3969/j.issn.1001-2400.2016.04.019

2015-04-13 网络出版时间：2015-10-21

中国科学院战略性先导专项资助项目(XDA06020300);上海市科委资助项目(12DZ0500100)

王 晶(1988-),男,中国科学院上海微系统与信息技术研究所博士研究生,E-mail:wangjingchn@163.com.

网络出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.038.html