图像同构算法 一种改进的同构网络虚拟骨干形成算法与时钟同步应用

　　[摘要]基于连通支配集构造无线传感器网络虚拟骨干,可以简化路由操作,并可提高广播效率。对Stojmenovic等学者提出的连通支配集分布式构造算法进行改进,大幅度降低了支配集尺寸和计算复杂度,并将之应用于DTMS时钟同步算法中,降低广播开销达60%以上。
　　[关键词]无线传感器网络虚拟主干连通支配集时钟同步
　　中图分类号:TN915.05文献标识码:A文章编号:1671-7597(2009)1110044-01
　　
　　一、引言
　　
　　基于连通支配集构造无线传感器网络的虚拟骨干,有助于简化路由操作,并提高广播效率[1.2]。连通支配集构造算法性能指标包括支配集大小、通信开销和计算复杂度等[3]。目前多采用启发式算法构造连通支配集,I Stojmenovic等提出了世界上首个零通信开销的构造算法[2～4],但计算出的支配集尺寸偏大,而且计算复杂度比较高,与网内节点最大度的三次方成正比。本文对其进行了改进,大幅度降低了支配集尺寸和计算复杂度,并将之应用于DTMS时钟同步算法中,降低广播开销60%以上。
　　
　　二、相关研究工作
　　
　　(一)相关定义及说明
　　Key值定义:对网内任意一个节点u,定义key(u)=(degree(u),id(u)),其中degree,id分别为节点的度和编号。对于任两个节点A、B,如果A的度大于B的度或二者的度相同时,A的编号大于B的编号,则称key(A)>key(B)。
　　“覆盖”定义:对于任意一个节点u和一个连通的节点集合S={v1,v2,...,vk},如果有,而且小于S中任意一个节点的key值,则称集合S覆盖了节点u。
　　如图1中节点4的key(4)=(7,4)。节点2被节点4所覆盖,节点集合{4,7,10,11}构成了一个连通支配集,网内任意两个节点都可以通过该集合连通。
　　
　　(二)Stojmenovic算法描述
　　I Stojmenovic等学者提出了世界上首个零通信开销的连通支配集分布式构造算法,其思想在于如果去除一个节点而不影响其邻节点的连通性,则该节点对于连通支配集而言,是一个冗余节点。对于任意一个节点,如果其邻居节点彼此两两连通,去除它不影响网络的连通性;如果其邻居节点都可以通过一个或两个邻居节点连通,去除它也不影响网络的连通性。为避免环回,只去除key值较小的节点,将degree置于key值首位的目的是保存度比较大的节点,最终网络中剩余的节点就是骨干节点[4]。
　　
　　三、连通支配集分布式构造算法
　　
　　Stojmenovic算法计算量太大,在第2次剪枝时计算复杂度正比于节点最大度的3次方;而且连通支配集尺寸偏大。在传感器网络中,一个节点有可能不被两个邻节点覆盖,但却被多个邻节点构成的集合覆盖。例如图1中的节点6不能被集合{4,7}和集合{7,10}覆盖,但可被集合{4,7,10}覆盖。
　　本文提出的算法目的是压缩支配集尺寸并降低算法计算复杂度。出发点是如果一个节点可以被几个邻居节点构成的集合覆盖,则其所有邻居节点都可以通过该集合连通。从网络连通性考虑,该节点不起决定意义,是一个冗余节点。
　　对网内任意一个节点u,用N1(u)代表N(u)中key值比u大的所有节点构成的集合;N2(u)代表N(u)中key值比u小的所有节点构成的集合。如果一个节点有两个不连通的邻节点,则定义其为一个中间节点。
　　判断节点是否被key值较大的邻节点覆盖是构造连通支配集的关键。对于任意一个节点u,如果以下三项之一成立:N1(u)为空、N1(u)不连通、N2(u)中至少有一个节点,其所有邻居节点都不在N1(u)中,则u不被N1(u)覆盖。
　　
　　四、时钟同步应用及性能分析
　　
　　在无线传感器网络中,时钟同步是一项基本要求,目前多采用广播方式实现同步,洪泛广播开销较大,而基于虚拟骨干进行广播,可以显著降低广播开销。笔者将该算法应用于时钟同步算法DTMS进行了对比分析,仿真显示降低广播开销可达60%以上。
　　显然,本算法计算出的连通支配集尺寸小于Stojmenovic算法结果。以下重点分析计算复杂度,设网内节点的最大度为Δ,则对于任意一个节点u,其各步骤的最大计算复杂度正比于O(Δ2)。而Stojmenovic算法复杂度正比于O(Δ3)。
　　
　　参考文献:
　　[1]I F Akyildiz,et al.Wireless Sensor Networks:A Survey[J].IEEE Computer Networks,2002,40(40):102～114.
　　[2]I Stojmenovic,M Seddigh,J Zunic.Dominating Sets and Neighbor Elimination Based Broadcasting Algorithms in Wireless Networks[C].IEEE Trans.on Parallel and Distributed Systems,2002,13(1):14～25.
　　[3]B N Clark,C J Colbourn,D S Johnson. Unit Disk Graphs.Discrea
　　te Mathematics,1990,86:165～177.
　　[4]I Stojmenovic. Comments and Corrections to Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks[J].IEEE Trans.on Parallel and Distributed Systems,2004,15(11):
　　1054～1055.
　　[5]T H Cormen,C E Leiserson,R L Rivest et al. Introduction to Algorithms.Ver.1McGraw Hill,2001:265～270.
　　
　　作者简介:
　　刘萍,女,工程师;黄馨,女,工程师。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文