定位规则

定位规则（精选5篇）

定位规则 篇1

0 引言

随着科技的日益进步, 时代的迅猛发展, 建筑造型也日益的多元化。现在乃至将来我们遇到的平面、立体设计较为复杂的异形结构将会越来越多。例如圆形、椭圆形、不规则弧形等异形建筑。这些建筑外形新颖美观、造型独特、富有动感, 经常用于一些公共建筑如博物馆、体育馆、影剧院等。

不规则弧形建筑的施工测量放线, 施工难度要比一般矩形、圆形等简单几何图形放样复杂的多, 施工现场测量放线人员常常感到非常棘手, 而且每个测量人员存在放线方法各异, 有些方法很复杂繁锁、测量放样精度也很难得以保证。为完美高效的按图纸要求进行精确的现场定位放线, 而不至于影响工程的形象进度。这就要求我们在日常生产中要充分运用新技术、新设备, 不断改进施工方法, 解决施工中的难点和要点, 把高质量的建筑产品交到建设单位手中。下面根据工程实例对天正建筑插件、AutoCAD结合全站仪在快速放线法中的运用作一一阐述。

1 工程简介

本工程地下1 层, 地上4 层, 建筑总高度29. 735 m。结构类型为框架—剪力墙结构, 由于本工程轴线较复杂, 主体结构多为不规则环形, 其余为不规则多圆心圆弧形, 每层内外圈框架梁和部分内梁都是由多圆心弧形轴线控制。弧形轴线测量放线精度直接影响整个工程的施工质量。

2 测量方案的确定

由于工程占地面积较大, 建筑平面形状复杂, 工期紧, 控制圆心多 ( 且主楼圆心部位为空腔) , 弧形线段多, 梁周长长, 并且每一层的外圈造型都不相同, 所以对于施工方来说施工难度较大, 尤其是测量放线这一块更是重中之重, 因为一旦出现失误, 损失将不可弥补, 甚至将推倒重来。在实际施工中施工测量人员应对结构图纸和建筑图纸对照后再进行施工放样。如采用传统的坐标计算方式不但复杂而且不容易掌握更容易出错。但是相对于使用安装天正建筑插件的AutoCAD把坐标点直接标注出来, 然后按照坐标放线和校核将事半功倍。为加快放样效率、提高放样精度, 我项目根据多方案对比筛选后决定采用天正建筑插件配合AutoCAD进行坐标查询, 全站仪进行施测放样的测量方案。

3 测量器具

现场配备的测量仪器有FTS532N全站仪1 台, DZJ3 激光垂准仪1 台, DS3 水准仪, 100 m钢卷尺和5 m钢卷尺等。

4 施测准备

首先认真熟悉图纸, 全面了解本工程设计者的设计意图。测量前组织测量人员学习设计说明、总平面图、本工程特点、周围环境、建筑位置及坐标原点位置。其次确定拟测建筑物与现场测量坐标原始点的相对关系, 水准点和高程的原始位置以及本工程首层 ± 0. 000 的绝对标高。

购置测量器具必须有国家有关部门认证的资料、随机文件、合格证、检测报告等。由专人存档建台账, 工程测量相关的仪器及工具要定期进行校核与检定, 进行施测的人员必须要取得有关部门认定的测量员上岗证书, 保证持证上岗。

5 测量方案具体实施

5.1建立坐标系

在建筑施工中, 施工总平面中标注有坐标点, 这几个坐标点由规划局提供位置, 但是依靠仅仅的几个点是不能施工的, 一般我们采用下面方法来实现施工放样的坐标查询:

打开CAD电子版图纸 ( 一般由设计院提供, 或自己根据原图纸绘制放线图纸) 把需要放线的图留下, 其余的部分不要的就全部删掉, 以免妨碍视线出现错误, 然后把需要放线的图中不必要的部分也删掉, 例如: 填充块、标注线等, 下一步就是查看总平面图的绘制比例和需要放线图的比例, 最简便的方法就是找到两张图上相同的部分进行量取, 然后换算比例。将绘图比例修改一致, 一般以m为单位, 精确至0. 001 m。确定原点位置: 根据所确定的坐标系, 找出拟测工程结构的各个施测点的坐标。利用安装天正建筑插件的AutoCAD的坐标测量命令及自动捕捉功能便可得到建筑物各控制点的坐标数据。

需注意以下两点: 1) 测量前在施工场地内设置3 个以上测量控制桩点, 桩点之间要保证通视。控制桩点要设置在不易破坏, 不受变形影响的部位, 且要便于定位放线; 控制桩点要定期复核, 每1 月~ 2 月检查一次, 做好检查记录。2) 其绝对坐标和相对坐标数据须及时记录、保存。

5. 2 各部位放线方案

弧形轴线可采用矢高等分法分段放出, 首先把该段弧在CAD中以100 cm等距分割, 现场提前放样制作各弧形轴线半径的模型, 用模型分段连接各轴线分段点画出轴线。

集水坑、柱圆心、柱帽位置可直接在CAD中查询出各点坐标进行放样施测。

圆柱外围根据圆心位置制作圆柱半径相同的模板画出圆柱边线及控制线。

5. 3 坐标计算

根据建筑物电子版测量图纸 ( 可由设计单位提供, 也可自己根据施工图纸绘制) , 在图纸上设置坐标系 ( 根据建筑物特点选择设置0, 0 点, 其他位置坐标为相对此点的坐标, 以后每次放线都以0, 0 为基准, 不宜更改, 以免混淆) , 设置时可以使用天正左侧工具栏中符号标注中的坐标标注功能或者命令行输入zbbz设置坐标系, 确定用户测量坐标系, 具体操作方法如下:

在天正CAD下部命令行中输入“zbbz命令”后回车 ( 或直接点击工具中的坐标标注功能) →此时命令行中提示“请点取标注点或设置 ( S) ”→在命令行中输入“S”后回车键确定→此时单击设置坐标系 ( 见图1) →在命令行输入“0, 0”原始点 ( 也可以标注为任意点) 并回车→用鼠标左键选择预定位的0, 0 点→确定拟测点 ( 弧形轴线测量采用矢量等分法1 m等距分割、圆柱圆心、轴线交点) →接着在拟测点上使用zbbz点击出拟测点坐标。这样就基本确定了整个CAD图形的坐标系 ( 见图2) 。

5. 4 坐标复核

放线结束后由专人对测量放样点进行校核, 校核时使用抽查法, 对施测完毕的任意放样点进行抽查, 其中两点距离可以使用钢尺进行校核, 其中两点距离可以通过坐标计算得出, 也可以在Auto CAD中利用“对齐标注”命令得出。

6 测量效果总结及推广前景

在朔州市科学技术馆工程的施工测量放线中, 由于本工程结构形式为不规则弧形结构, 如采用传统计算方法存在人工计算量大、繁锁、易出错、不易校核且圆心部位为空腔不在同一平面等特点, 每条弧形轴线采用矢量等分法分段绘制, 使用AutoCAD天正插件坐标可以直接在拟测点点位上标注, 不用计算、不易出错, 校核复查方便。不仅高效、精确, 而且可以快速完成困难、复杂的测量计算, 提高了测量放线的工作效率; 误差控制在 ± 2. 5 mm以内, 从而顺利实现了预期测量目标。此种测量放线方法在各种异形、不规则弧形建筑的施工放线、测量放线施工中将会有很好的推广前景。

摘要：以朔州市科学技术馆工程施工测量为例, 通过分析比选, 采用天正建筑插件配合AutoCAD进行坐标查询, 全站仪进行施测放样的测量方案, 介绍了施工测量前的准备工作, 探讨了AutoCAD天正插件在异形结构施工定位放样中的应用方法和技术要点, 保证了测量放线的施工效率。

关键词：异形建筑,定位放线,AutoCAD,测量方案

参考文献

[1]GB 50026—2007, 工程测量规范[S].

[2]《建筑施工手册》编写组.建筑施工手册[M].第5版.北京:中国建筑工业出版社, 2008.

定位规则 篇2

关键词：关联规则,多故障定位,提高定位效率,聚类方法

0 引言

随着软件产品的发展，软件规模以及软件复杂度的不断增大使得软件调试过程越发困难。软件故障定位是调试过程中成本最高同时耗时最长的一项[1]。在软件自动化调试领域，出现了许多相应的方法，Jones和Har rold提出了Tarantula[2]方法，该方法通过对比程序实体在失败测试用例和成功测试用例之间的差别，计算程序实体的怀疑度实现故障定位。C.Liu提出了SOBER[3]方法，该方法使用谓词在测试用例中取值为真对程序故障出现的影响实现故障定位。其他还有一些定位方法[4-6比如CBI、NNQ、SBI等。这些方法大多使用程序实体的覆盖信息来计算每一个程序实体的可疑度，然后通过可疑度排名列表去发现软件故障。这些方法虽然在单故障的情况下取得了很好的效果，但是在多故障的情况下，效果都不是很理想。他们大多都采用one-bug-at-a time的方式实现多故障的定位，但是这种方式弊端明显：时间效率低，同时需要重复测试。

Jones和Harrold提出了一种并行调试技术[7]，通过对可能导致同一个故障的测试用例进行分类，然后结合成功执行的测试用例构造用以测试每个故障的测试用例子集，来同时定位不同的软件故障。但现有的基于覆盖率的错误定位（Coverage Based Fault Localization,CBFL）方法只是统计代码语句或代码基本块的覆盖率，并没有考虑程序执行的数据依赖和控制依赖，因此会出现定位不准确的情况。结合以上两点，本文将在并行的基础上使用关联规则挖掘软件故障。

1 相关工作

许多该领域的学者提出了不同的软件故障定位技术。这些技术大多通过收集语句或者谓词等程序实体的覆盖信息，然后对收集到的信息利用相应的怀疑度公式计算每条语句的怀疑度，据此找出软件中的故障。本文也使用这种方式，同时，结合关联规则的思想来提高软件的多故障定位效率。

1.1 基于交叉表的故障定位技术

W.Eric提出了一种基于交叉表的技术进行软件故障定位的方法[4,8]。该方法的主要思路是：针对每个测试用例的每一条语句构造一个交叉表，通过该交叉表收集语句的覆盖信息和执行结果。然后，利用每条语句的统计信息计算该语句的怀疑度（Suspiciousness）。通过这种方式，所有的语句都可以根据计算出的怀疑度来降序排名。语句的怀疑度越高，该语句越会被优先检查，可以通过排名依次检查语句，直至发现软件的故障。

该技术通过引用一个名为Chi-square test的假设测试来检查测试用例执行结果和语句覆盖信息之间的依赖关系。Chi-square的数据通过交叉表中的数据计算而来，同时与Chi-square中的关键值进行对比，决定这个假设（即执行结果独立于与语句的覆盖信息）被接受还是被抛弃，然后，通过计算语句的怀疑度数值ζ进行故障定位。ζ的数值越大表示语句的怀疑度越高，怀疑度越高则会被优先检查。基于交叉表的软件故障定位技术通过计算语句的怀疑度来预测语句包含故障的可能性。其实验结果表明基于交叉表的软件故障定位技术相比于绝大多数的软件故障定位技术，如Tarantula、Liblit05、SOBER等方法，效果更好。

1.2 并行调试

通常状况下，一个软件出现失效状况下，软件中会包含多个故障，同时软件调试的人员也会不止一个，因此可以通过并行的方式实现软件故障的定位工作，相比于one-bug-at-a-time的方式，并行故障定位会更加高效，通过构造并行工作流，不同的工作人员可以专注于不同的软件故障。要实现并行的软件故障定位，最重要的问题是如何对任务进行划分和分派，这就需要一种可以把错误的测试用例集从新分配成多个小的与特定故障相关的错误测试用例子集的技术。Jones和Harrold提出了一种并行调试的技术[7]用以实现解决这个问题。这种技术会自动把失败的测试用例集分割为针对不同软件故障的测试用例子集。通过使用测试用例动态运行获取执行结果的行为模型和信息，该技术可以生成一个针对不同错误的失败测试用例子集。通过把失败测试用例子集和成功的测试用例结合，就得到了一个专注于特定单错误的测试用例集。这些单错误测试用例集的个数就是对程序中故障个数的预测。

2 关联规则在软件故障定位中的应用

在基于覆盖的软件故障定位技术中，现有技术通过收集测试用例执行的覆盖信息计算语句可疑度，进而定位软件故障。在现有的技术中，往往没有考虑语句间的数据依赖和控制依赖关系，不同语句的覆盖统计是相互独立的，这导致定位的不准确，CBFL方法经常能定位到程序失效时的执行代码，而这些失效时的执行代码多数情况下并不是错误代码[9]，文献[9]表明，基于覆盖的软件故障定位计算可疑度得出的高可疑度语句主要分一下几种情况：

(1）该语句基本块本身就是故障语句，并且该基本块出现在错误测试用例的概率高于出现在成功测试用例的概率。

(2）该语句基本块本身不是故障语句，但是该基本块的执行会导致故障语句的执行，进而发生故障。这表明高可疑语句块或者是故障或者会导致故障，因此考虑通过关联规则挖掘高可疑代码与软件故障的关系，提高故障定位的效率。

测试用例的执行路径能够反映出故障代码与高可疑代码之间的关联，即高可疑代码的执行导致故障语句的执行，进而出现故障。故障语句与高可疑语句表现出了在执行路径上覆盖信息的一致性，然而执行轨迹的路径表示十分复杂和耗时[10]，因此采用相对轻量级的覆盖向量来近似表示路径的覆盖信息。

2.1 路径覆盖向量的表示

定义1：中间不存在控制跳转的连续代码语句构成一个代码基本块，简称为基本块。

定义2：覆盖向量值指代码基本快在每次执行中的覆盖信息构成的向量pathi=(b1,b2,⋯,bn)。其中：path表示覆盖向量；bi表示程序中代码基本块，bi=0表示该代码基本块没有被覆盖，bi=1表示该代码基本块被覆盖。

定义3：一个函数在测试用例集下的执行轨迹符号化表示为EXEM(fi)={B,T,PATH}。其中：B表示函数的基本块集合；T表示测试用例集的所有测试用例集合，PATH={path0,path1,⋯,pathm}表示针对每个测试用例的覆盖向量集合。根据程序执行的结果可以将执行轨迹分为成功执行和失败执行，即EXEMp和EXEMf。

2.2 求解频繁集

根据故障语句与高可疑代码之间表现出的覆盖一致性，可以求解故障语句的“频繁集”来表现这种关联[11,12]，软件故障或者存在于高可疑代码中，或者存在于高可疑代码的频繁集中，因此通过频繁集来提高软件故障定位的效率。只需求出与高可疑代码保持覆盖一致的分量对应的基本块，即可通过频繁集提高故障定位的效率。

求解频繁集的算法如下：

算法中：bk代表目标代码；fg(bk)表示与bk保持频繁一致性的分量集，即求解出的以bk为目标的频繁集。算法过程为：遍历bk不等于0的分量进行与操作，即得到所有的bk的频繁集。通过计算每一条语句块的可疑度，按照可疑度降序检查发现错误，若语句块中不存在错误则检查语句块的频繁集（依据可疑度排序）查找错误，这种方式可提高定位效率。

3 基于交叉表的软件多故障定位技术

下面对基于交叉表的软件多故障定位技术进行具体介绍。

图1为程序实例展示，该程序用于求取输入的是三参数中间值。

图1的程序中包含两个错误，分别是语句行6和语句行9，使用在测试用例集中10组参数组合分别为T1～T10。图中“√”代表了每条测试用例的语句覆盖信息；在最后一行给出了每个测试用例的执行结果：P代表成功，F代表失败。

由图1可知，导致失败的测试用例往往具有相同或者相似的语句覆盖信息。因此可以通过聚类方法将测试用例进行分类，将错误测试用例中语句覆盖路径相同或者相似的路径分为一类，这些被分为不同类的失败测试用例子集就是专注于不同错误的测试用例集。在mid函数中，测试用例7～10失败了。而且，测试用例7,8有相同的覆盖信息，这意味着测试用例7,8可能会导致同样的软件故障。同时，测试用例9,10也具有相同的覆盖信息，同理，它们也可能导致同样的软件故障。通过上述分类原理和观察到的现象，下面把失败的测试用例分为两组针对不同错误的失败测试用例子集。然后通过使用Jones和Harrold的并行调试的方法，将失败的测试用例子集分别与成功测试用例结合，形成两组不同的测试用例子集。两组测试用例子集如图2和图3所示。

针对不同语句构造一个用于计算语句怀疑度的交叉表，语句交叉表模板如图4所示。

图4所示交叉表是一个表示测试用例执行情况和测试用例是否被覆盖的二维表。表中各个变量的含义分别是：w代表程序中的一条语句；NCS(w)代表覆盖w的成功的测试用例数；NUS(w)代表没有覆盖w的成功测试用例数；NS代表成功的测试用例数；NCF(w)代表覆盖了语句w的失败测试用例数；NUF(w)代表没有覆盖语句w的失败测试用例数；NF代表失败的测试用例数；NC(w)代表覆盖了的测试w用例总数；NU(w)代表没有覆盖w的测试用例数；N代表总的测试用例数。

使用图4提供的模板和文献[4]中提供的公式计算每条语句的怀疑度。针对图2和图3两个测试用例集分别计算怀疑度，给出怀疑度列表降序排名如表1所示。

表1中，语句9的怀疑度最高，会最先被检测。在表2中语句6的怀疑度最高，会最先被检测。这表明通过构造针对不同错误的测试用例子集并行的进行故障定位是可以实现的，这将有利于提高软件故障定位的效率。在此计算验证了通过并行的方式进行软件故障定位的有效性。进行并行的故障定位有一个前提就是构造针对不同错误的测试用例。通过使用二分法构造针对不同的测试用例，针对不同的待测函数，可以根据函数的输入集合和函数的功能创造出不同的二分法条件。在上面例子中，mid函数是用作求取输入的3个数的中间值的函数，因此中间的参数最有可能导致软件故障。所以中间的参数作为分类条件，在mid函数中使用“中间的参数是不是在第一个出现”作为分类的条件，如果一个失败测试用例满足这个条件则把它放在一个类别中，不满足则放在另一个类别，同样以图1的测试用例为例，发现T9和T10满足这个条件，所以把他们分为一类，T7和T8分为另一类，这样即可进行并行软件故障定位。

同时，给出一个终止条件，用于判断分类是否完成，即针对不同错误的测试用例是否已经被分配到了各自相应的类别下。聚类的相似性系数可以提供判断不同对象之间相似程度的度量，因此可以使用相似系数来判断每个类别中的对象是否足够相似，不同类别间的对象是否足够相异来判断分类是否完成。相关系数公式如下：

式中：Xi为第i条语句在失败测试用例X中的覆盖情况，Xi为1代表覆盖，0代表未覆盖；Xˉ表示失败测试用例Xi的覆盖比例；相应的Y的含义和X相同。利用图1中的例子可以将失败的测试用例集分类。给定一个相关性系数的值，比如0.8，当两个失败测试用例的关联系数小于0.8时说明它们关联性不大，即它们针对不同的错误。计算r78=1，这表明T7和T8关联性非常大，针对相同的错误，对T9和T10计算结果也是1，说明它们应该分为一组。通过循环计算每两个测试用例之间的相关系数，直到类别内任意两个测试用例的相关系数大于0.8时，就说明分类完成。本文给出的上述方法虽然能够对针对不同错误的测试用例进行分类，但需要对每两个错误测试用例进行计算，所以这个过程相当耗时，开销也是很大。

4 实验及结果分析

下面使用本文给出的基于关联规则的软件多故障定位技术和Tarantula方法进行对比来验证本文方法的定位效果。在此使用Siemens程序集来进行试验的对比工作。程序集中tacas程序包含的故障版本数最多，同时可执行的语句数最少，这意味着tacas程序有可能包含多故障，因此选用该程序验证本文的方法。对文献[4]中的EXAM度量进行扩展，将针对每个故障的EXAM相加，形成EXAMtotal作为度量的标准。

基于关联规则的软件多故障定位方法与Tarantula方法的对比如图5所示。

图5分别给出了在不同的故障版本比例下两种方法的EXAMtotal得分。其中“1”代表20%的故障，“2”代表40%的故障，“3”代表60%的故障，“4”代表80%的故障。可以看到在故障比例较低的环境下，本文的方法效率明显优于Tarantula方法。

5 结语

本文提出了基于关联规则的软件多故障定位方法，并且与Tarantula方法进行了对比，结果表明本文的方法效率较高。不过本文提出的方法也存在一些不足，并没有考虑把测试用例划分为针对不同故障的测试用例的效率，同时也没有考虑失败测试用例分类的效果进行验证。在Siemens测试集上通过实验验证了基于关联规则的软件多故障定位的效率，结果证明本文的方法能有效地发现软件的故障。

参考文献

[1]JONES J A.Semi-automatic fault localization[D].USA:Geor-gia Institute of Technology,2008.

[2]JONES J A.HARROLD M J.Empirical evaluation of the Ta-rantula automatic fault-localization technique[C]//Proceedingsof the 20^thIEEE/ACM international Conference on AutomatedSoftware Engineering.Long Beach,CA,USA:IEEE,2005:273-282.

[3]LIU C,FEI L,YAN X,et al.Statistical debugging:A hypothe-sis testing-based approach[J].IEEE Transactions on SoftwareEngineering,2006,32(10):831-848.

[4]RENIERES M,REISS S P.Fault localization with nearestneighbor queries[C]//Proceedings of the 18^thIEEE/ACM Inter-national Conference on Automated Software Engineering.Mon-treal,Canada:IEEE,2003:30-39.

[5]LIBLIT B,NAIK M,ZHENG A X.Scalable statistical bug iso-lation[C]//Proceedings of the 2005 ACM SIGPLAN Conferenceon Programming Language Design and Implementation.2005:15-16.

[6]HAO D,ZHANG L,PAN Y,et al.On similarity-awarenessin testing-based fault localization[J].Automated SoftwareEngineering,2008,15(2):207-249.

[7]JONES J A,BOWRING J F,HARROLD M J.Debugging inParallel[D].London,UK:Georgia Institute of Technology,2007.

[8]WONG E,WEI T,QI Y,et al.Crosstab-based statisticalmethod for effective fault localization[C]//Proceedings of the2008 International Conference on Software Testing,Verifica-tion,and Validation.Lillehammer,Norway,2008:42-51.

[9]ZHANG Z,CHAN W K,TSE T H.Capturing propagation ofinfected program states[C]//Proceedings of the 17^thInterna-tional Conference on Foundation of Software Engineering.Am-sterdam,Netherl:[s.n.],2009:43-52.

[10]BALL T,LARUS J R.Efficient path profiling[C]//Proceedingsof the International Symposium on Microarchitecture.Paris,France:[s.n.],1996:46-57.

[11]WONG E,QI Y.Effiective program debugging based onexecution slices and inter-block data dependency[J].Jour-nal of Systems and Software,2006,79(2):891-903.

定位规则 篇3

柔性电路板简称FPC, 具有轻、薄、软等特点, 随着消费性电子趋向于灵巧化, 柔性印刷电路板的应用也越来越多。图1所示为一种FPC的生产工艺流程, 其中有多次完成PSA (压敏胶) 的粘贴工艺, 并且形状各种不同, 如图2所示, 实际生产中多为人工贴附, 为了提高生产效率, 保证加工质量, 如何使用基于机器视觉的自动化设备完成贴胶工艺成了迫切需求, 贴胶片形状各不相同, 如果通过简单的灰度处理只能得到PSA的质心坐标, 而姿态角度等却无法获得, 这就需要研究其他算法, 以实现其精确定位。

1 基于区域特征方法理论

视觉中, 最简单的区域特征是区域的面积, 可由公式 (1) 获得, 所得区域的面积a就是区域内的点数。如果区域是用一幅二值图像表示的, 那么此式中的第一个求和等式计算区域的面积;如果区域是用行程编码表示的, 那么用此式中的第二个求和等式计算区域的面积。其中使用行程表示法可以使区域面积的计算速度快很多, 这个特点几乎所有的区域特征都适用。

面积是被称为区域的矩的广义特征中的一个特例。定义为:

其中, mp, q就是区域的面积, 与计算面积相似, 基于行程表示法可以高效地计算矩, 式 (2) 的矩依然依赖于区域的尺寸。在实践中, 人们会期望有一些特征可以不随物体尺寸的变化而变化, 为获取这样的特征, 当p+q≥1时, 矩除以区域的面积就得到了归一化的矩:

从归一化的矩中推导得到的最令人感兴趣的特征就是区域的重心。即 (n1, 0, n0, 1) , 它能被用来描述区域的位置。尽管重心是从像素精度的数据计算得到的, 但它是亚像素精度特征。归一化的矩是由图像中的位置决定。通常, 使特征不随图像中的区域变化而变化是很有用的, 这可以通过计算相对于区域重心的矩来实现。这些中心距是在 (p+q≥2) 时由下式计算得到的:

这些中心矩也是归一化处理后的。二阶中心矩尤其重要, 他们可以用来定义区域的方位和区域的范围。这是通过假设从一个椭圆上获得区域的一阶矩和二阶矩而实现的。然后, 从这五个矩推导出椭圆的五个几何参数。图3显示了椭圆的参数。椭圆的中心与区域的重心是一致的。椭圆的长轴r1和短轴r2以及相对于横轴的夹角可由下式计算得到:

椭圆的这些参数在确定区域的方位和尺寸时极其有用, 例如角能被用来对经过旋转的文本或形状进行纠正。还有要用到的特征是基于为区域找到一个外接几何基元。图3显示的是某个区域的最小平行轴外接矩形, 此矩形也被称为区域的边框, 它可基于区域横纵坐标的最大值和最小值计算得到。基于矩形的参数, 可计算出其他有用的特征量, 如区域的宽度、高度、宽高比。当要快速判断两个区域是否存在相交的可能性时, 边框的参数是非常有用的。因为最小平行轴外接矩形有时并不是非常紧地围绕在区域外, 所以也需要定义最小外接矩形, 如图4所示。一个任意方位的矩形与椭圆有同样的参数, 所以, 它也能被定义区域的位置、尺寸和方位, 与椭圆参数相比, 它的好处是可以返回正方形的方向。下文基于最小外接矩形的处理方法就是基于矩形和椭圆的这种特征来获得PSA的角度, 然后获得各PSA与标准位置的角度差。

2 基于模板的形状特征的匹配

由于PSA主要是形状各不相同, 所以其形状就是很重要的区别特征, 这样我们常会想到利用形状匹配来获得匹配度很高的位置和方位。当然在照明恒定时且只识别同一种PSA使用灰度匹配也可以, 这里简单阐述稳定性更高的形状匹配。

形状描述是通过一些方法生成数值的描述子来描述形状, 描述子应在尽可能区别不同目标的基础上对目标的平移、旋转和尺度变化不敏感。形状匹配是描述图像内容一个重要特征。形状匹配就是根据物体的形状来创建模板, 然后通过一定的度量准则来衡量形状间的相似性, 最终在同一幅图像的其他位置或者在其他图像中找到匹配物体, 常用于物体的识别与定位、完整性检查和部件监视等。

形状匹配在应用中主要针对两个问题:一个是怎样去匹配物体;一个是如何界定两者的相似性。前一个是关注物体与物体之间的匹配程序, 后一个是关注一个物体与所搜索物体类似的问题。尽管这两个方面会经常联系在一起, 但高效相似性测量的定义引起了越来越多的关注, 这也归功于像基于内容的图像检索与恢复这样的应用。就相似性而言, 传统的方法有Minskouski、Euclidean和Mahalanobis。最近提出了基于模糊逻辑的相似性策略, 这些方法都是基于距离的变换, Chamfer匹配和Hausdorff距离是当前在这个领域的代表方法, 而且在复杂图像失真的呈现中有很好的性能。

3 基于Halcon的两种方法识别对比分析

图5为一种PSA的原始拍照图像, 使用灰点200万相机和0.7~4倍moritex远心镜头漫射光低角度拍摄。

3.1 基于最小外接矩形获得位姿

经过图像预处理、阈值分割和形态学特征选取 (流程如图6所示) 后最终结果如图7所示, 利用区域特征可得到PSA的位置为 (896.27, 514.378) , 角度偏移为0.131315°。多个PSA的处理结果如图8所示。

3.2 基于模板的形状匹配方法

创建模板的流程如图9所示, 基于HDevelop的形状匹配算法是根据指定感兴趣物体分割出小区域, 然后通过提取ROI (region of interest) 轮廓来创建模板, 最终实现匹配。可根据实际应用设定匹配参数, 对各参数进行优化调节, 不但可以提高匹配精度, 而且还可以大大提高匹配速度。其中图11为多个PSA的匹配结果。

第一步:创建一个合适的模板。

第二步:提取指定区域中ROI的轮廓, 即得到所要识别物体的形状, 如图10所示。

第三步:搜索形状模板。

4 两种算法的比较分析

在精度方面, 虽然使用了不同的算法, 但是两者的精度都能达到需求, 在照明光线较好的情况下, 位置误差能达到一个像素左右, 角度误差在0.001度以内, 然而第一种算法对光线的稳定性和一致性等方面要求较高, 在阈值分割时, 不同的阈值结果也会对精度产生一定的影响, 若产生遮掩则会产生严重的误差, 而第二种方法则可以避免这种情况;在处理速度方面, 两者均能达到40ms/张, 满足实际生产的需求;在适用性和稳定性方面, 第二种方法不受光线和阈值的影响, 更为稳定, 适用面也更广, 但是在要同时得到许多不同形状的PSA位姿时, 第一种方法更为方便, 因为方法二需要为各种PSA (或字符) 建立模板, 匹配模板时也要考虑各个模板匹配顺序和结果。

5 结束语

本文主要阐述了两种获得不同形状PSA的位姿的方法, 并在Vc6.0平台下调用Halcon内部算子进行实现和验证, 并对其精度、速度、鲁棒性和适用性方面进行了对比分析, 在算法进行进一步改进和完善后即可投入现场使用。

参考文献

[1]H.Schweitzer, J.W.Bell, F.Wu.Very fast template matching.ECCV2002, LNCS2353 2002

[2]Luigi Di Stefano, StefanoMattoccia.Fast template machineusing bounded partial correlation.Machine Vision andApplication.2003

[3]丁险峰, 吴洪, 等.形状匹配综述[J].自动化学报.2001, 27 (5) :678-694.

[4]张素文, 杨富森.基于HDevelop的形状匹配算法参数的优化研究[EB/OZ].中国科技论文在线.

[5]张铮等.数字图像处理与机器视觉—Vc++与Matlab实现[M].人民邮电出版社, 2011.

[6]Milan Sonka, vaclavHlavac, Roger Boyle.图像处理分析与机器视觉[M].清华大学出版社, 2011.

定位规则 篇4

目前关于文本定位主要分为基于纹理特征［2－4］和基于连通分量［5－8］的方法,基于纹理的方法认为文本区域具有特殊的纹理,通过滑动窗口对其提取纹理特征,最后利用分类器分类确认文字块。基于连通分量的方法则是利用同一区域的文字具有颜色和亮度的一致性,并与背景有着较大的区别,以此来分割图像提取连通分量,再利用几何约束关系对连通分量分析从而得到文本区域。

上述方法中,由于基于纹理特征的方法往往需要对图像采用多尺度处理［9］的方法,这导致了文本定位的速度过慢。而基于连通分量的方法,在对英文等检测时取得较好的效果,这是因为英文都是由26 个字母组成的,同时字母本身作为一个连通分量结构又较为简单,而由于汉字数量巨大,构成汉字的连通分量也是各不相同,因此连通分量的方法在中文文字检测中并不多见。

针对于此,本文提出了一种新的基于连通分量的中文文字检测方法,在连通分量提取与剪枝时采用了新的结合文字纹理特征的方法,接下来的连通分量分类中又根据汉字的特点,通过对其骨架化提出了一种新的规则度特征,并使得分类和最后的定位取得了较好的结果,有效地改善了基于连通分量的方法在中文文字检测时的效果。

1 本文实现方法

本文在传统的基于MSER［10］检测的基础上,结合文字平滑度特征对MSERs树进行剪枝,并对连通分量进行一般性特征和新的结合汉字结构特点的规则度特征提取,通过分类器去除掉大量明显的非文字连通分量,再对剩下的分量进行结合汉字结构的合并和文本排布的启发式规则进行最终的分类和精确定位。整体流程图如图1 所示。

1. 1 基于平滑度与MSER的连通分量提取

1. 1. 1 最大稳定极值区域

最大稳定极值区域( Maximally Stable Extremal Regions,MSERs) 是一种图像结构,不仅是在平移和旋转后,即便经历相似和仿射变换仍可被重复检测出来。MSERs检测可以解释如下［11］: 考虑1 幅灰度图I所有可能的阈值,比如常见的[0,…,255],低于阈值的为黑色像素,高于阈值的为白色像素。当阈值从小到大不断的过程中,白色像素所组成的连通分量的面积会随之发生改变,可以观察到,在特定区域大范围的阈值内,局部二值化很稳定,即有的区域面积变化率很小或者没有变化,则这些区域称为最大稳定极值区域。实际检测中,选取那些在强度阈值为 Δ 时具有面积变化率极小值的连通分量作为最大稳定极值区。在文本检测中,由于文字本身就是由连通区域组成的,故本文采用基于MSER的候选区域检测。

1. 1. 2 结合平滑度的MSERs树的剪枝

图像中的MSERs受到阈值 Δ 影响,其提取数目也会因此而不同,本文为了保证文字的最大稳定极值区域尽可能完整地都被提取出来,需要使用尽量小的 Δ,这又导致了会产生大量重复的嵌套MSERs,最常见的情况就是根结点处的MSER包含过多叶子结点,具体而言就是检测结果有可能会将若干个文字及诸多无关区域作为一个大的MSER检测出来,特别是在自然场景中受到光照、污渍等干扰时较为明显。若将检测到的区域二值化,则如图2 所示。

为了解决这种干扰,通过考察MSER树状结构发现,在每个包含有文字的树状结构中,忽略那些孤立点及面积较小的区域,由于文字区域一般不会包含有别的连通分量( 也不被包含) ,以及MSER的嵌套关系,考虑文字区域本身和与相邻文字之间的平滑性,那么文字区域应为树状结构中平滑性较好( 甚至是最好) 的。本文采用的方法是,对一个树状结构中所有的MSER求出平滑性最好的极值区域,然后对树状结构中的所有MSER求平滑度,考虑文字之间的纹理一致性,若存在一些MSER与最平滑区域有较为一致的平滑度,则认为这个区域也是文字候选区域,记平滑度为R,δ2为二阶距,则

本文通过对树状结构进行适用于文字区域的平滑度处理,同时过滤掉那些面积过大和过小的区域,这样不仅去除了大量的非文本区域,并且在对受污渍、光照等干扰造成的不同文字间连通分量相连的情况有效地分离。

1. 2 基于新的规则度等特征的连通分量分类

在上一节进行剪枝处理之后剩下的区域中仍有相当多的非文本区域,需要进一步进行处理。一般而言,汉字作为一个连通分量不会存在于别的连通分量之中,因此,首先去除那些包含在另一个连通分量的区域,这样同时也会去除有的汉字例如“回”等内部结构,但去除了汉字内部的小的结构其实并不影响接下来对文字检测。

1. 2. 1 连通分量一般性特征

对连通分量通过提取特征来进一步区分字符与非字符,首先是一些基本特征［12］,包括占空比、长宽比、笔画宽度和紧致度等。

长宽比: 连通分量外接矩形框长宽之比。

占空比: 连通分量面积Acc与外接矩形框面积Abox之比。

笔画宽度: 文字笔画宽度Sw不能太宽,且笔画中梯度方向相反的像素对的数目Np要占边缘像素个数Nedge一定大的比例,即Np/ Nedge要大于某一常数。

紧致度: N2edge/ Acc,欧氏空间最紧致的是圆,而文字区域一般紧致度不太高。

1. 2. 2 骨架化与新的规则度特征

相比于英文字符中常用而又有效地的欧拉数特征,由于汉字的连通分量的复杂性,欧拉数特征并不能有效地区分字符与非字符分量。然而通过仔细观察汉字连通分量时发现汉字连通分量都是由横竖折所组成,这一点明显不同于英文字符的曲线结构,故本文利用这一特点对汉字连通分量进行特征提取。算法步骤为:

1) 对连通分量进行骨架化处理( 如图3 所示) 。

2) 对提取的骨架进行规则性特征描述,汉字中最常见的结构( 如图4a、图4b所示) 加以0 权值,较为常见的( 如图4c、如图4d所示) 加较小权值,不常见的( 如图4e、图4f) 则权值较大,用加权后的结果除以骨架像素点个数进行归一化,所得归一化结果即是连通分量的规则度特征。

3) 文字的笔画为线条性的,故用连通分量的骨架像素数Nskel与边缘像素数Nedge之比作为特征,字符这一特征具有一致性,而非字符则不具有一致性。

对每一个骨架像素点考虑其3 × 3 邻域: 图4a、图4b表示文字中的横竖折基本结构,汉字中最常见; 图4c为骨架化不理想或者“折”的角度过大过小时的结构,图4d为笔画相交时的结构; 图4e、图4f为文字中不常见的结构; 而上述结构在非文字中特别是不规则区域都较为常见。图示结构为基本结构的一部分,可以改变位置和方向。

1. 2. 3 Adaboost分类

本文利用新提出的规则度特征和占空比、笔画宽度和紧致度等特征采用Adaboost［13］算法对连通分量进行分类。Adaboost算法核心思想是针对同一个训练集训练不同的弱分类器,然后把这些弱分类器集合起来构造一个强分类器。

设给定N个训练样本( x1,x2,…,xN) ,用fm( x) ∈{- 1,+ 1}(m = 1,2,…,M)表示M个弱分类器在样本x上的输出,算法如下:

1) 对训练样本初始化权值wi

2) 对m = 1,2,…,M,重复以下过程:

( 1) 利用{ wi} 进行加权后的训练样本构造弱分类器fm( x) ∈{ - 1,+ 1} ;

( 2) 计算加权后的分类错误率em,并记

( 3) 更新样本权值

并归一化使

式中: h( yi≠fm( xi) ) 表示当yi≠fm( xi) 时取1,否则取0。

3) 对于待分类样本x,分类器的输出

式中: m表示第m个弱分类器; M为总共迭代次数,即弱分类器个数,本文弱分类器采用简单的桩分类器,最终将这些连通分量通过组合的分类器实现文字与非文字连通分量的分类。

1. 3 文字结构合并与最终定位

至此,绝大多数非文本连通分量已经被去除掉,同时也有效地保留了文本候选区域,接下来的文字结构合并工作将变得相对简单。汉字可以分为独体字和合体字,独体字本身就是一个连通分量,而合体字却包含着若干个连通分量,这就需要通过合理地合并算法将这些分量组合成一个新的文字区域。合体字有着较多的结构,但绝大多数本质上是由上下与左右结构相组成的,对于包围结构,只考虑其最外围的分量即可确定文字位置即可,本文给出如下合并算法。

对于任意两个连通分量u,v,记( x,y,w,h) 分别为其外接矩形框的左上坐标、宽和高,s为平均笔画宽度。则算法步骤为:

1) 若u和v满足式( 7) 则转2) ,满足式( 8) 则转3) ,否则终止。

2) 若us,vs满足式( 9) ,且式( 10) 成立,则将u和v进行水平方向的结构合并,合并后的结构更新为一个新的分量u,而v为其他的任意一个连通分量,并转1) ; 否则终止。

3) 若us,vs满足式( 9) ,且式( 11) 成立,则将u和v进行竖直方向的结构合并,合并后的结构更新为一个新的分量u,而v为其他的任意一个连通分量,并转1) ; 否则终止。

式中: ux,uy,uw和uh分别表示连通分量u的横坐标、纵坐标、外接框的宽和高; us表示u的平均笔画宽度; 连通分量v同理,k,k1,k2和k3为待确定的常数。

本文通过实验发现k = 5,k1= 1,k2= 0. 55,k3= 2 时取得较好的效果,经过结构合并得到的每个区域都看做候选文字( 结构不完整的依然保留了其基本的文字外层结构部分) ,由于汉字的长宽比较为规整,文字中心近似在同一直线上,最后利用这些启发式规则做出最后的定位。

2 实验结果

本文对自然场景中的文字进行检测,其中包括不同字体、光照条件及复杂背景下获取的图片,采用ICDAR2005 年鲁棒测评［5］中定义的准确率和召回率来评价文本区域定位的性能,分别记为P和R。定义为

式中: C为场景图像中检测到的文本域的个数; E为场景图像中检测到的非文本区域个数; T是场景图像中未被检测到的文本区域的个数。本文对各种环境下的场景图像进行中文文字检测,检测流程如图5 所示。

从图5e看出,尽管通过分类器对连通分量进行分类,结果仍然有少量的分类错误,仅利用连通分量的特征难以确定其是否为字符,然而利用文字结构特性及文字间的排布规则可以进行最终的确认和定位。同时注意到骨架化对一些单独的凸起像素点或点洞较为敏感,故在骨架化前进行简单的像素点填充和去除预处理,当图像分辨率过低时可能会造成微小失真( 如图5e中文字少许缺损) ,但实验表明对最终定位结果几乎没有影响。

由于目前没有自然场景中文的文本检测标准数据库,故本文所用的场景图片为亲自采集,其中训练样本图片80 张,所提取的字符连通分量为1 012 个,非字符连通分量1 258个,测试样本图片120 张。首先本文算法与Yi［14］的算法在最终文本定位效果上进行比较,如表1 所示。

%

从表1 中可以看出本文方法在整体性能上都比Yi的方法有一定程度的提高,这是因为Yi的方法在提取候选区之后主要依靠字符之间的结构特征进行合并,而本文在合并之前充分考察连通分量的特征及进行分类,从而取得了较好的效果。

本文与文献[12]进行对比分析,如表2 所示。

%

从表2 可以看出,本文算法的定位性能比文献[12]有所提高。这是由于规则度特征充分结合了汉字的结构特征,使文本与非文本连通分量分类效果较为出色,并利用字符与文本的结构特征进行结构合并,从而改善了最终定位的效果。

3 结束语

定位规则 篇5

定位系统的安全性与能源有效性和定位精度被认为是评估传感器网络定位设计的三个主要指标。其中,安全性作为定位系统的一个关键指标仅仅是近期才得到广泛关注,相关研究成果还很少并且这些方法都是在硬件成本、算法复杂度与通信、计算开销和节点部署要求上各有取舍。为了有效解决节点自定位系统的安全性问题,文中基于节点间的距离和连通性信息,提出了一种复杂度和通信、计算开销都较低且不需要任何附加硬件需求和节点部署知识的安全定位算法,称为距离连通性校验机制(DCVM)。

本文接下来介绍了安全定位问题的背景和本文的基本假设条件,在此基础上提出了DCVM安全定位算法,并对算法中攻击点探测阶段进行了理论分析,最后通过仿真与性能评估验证了该算法的有效性。

1 问题背景和基本假设

安全定位即使无线传感器网络在恶意攻击存在条件下,仍能安全、有效地确定节点的位置。为了简化分析,考虑定位算法使用MDS且假设网络模型如下。

1.1 网络模型假设

设一组传感器节点随机部署且均匀分布在静止的2维空间,基点绝对安全、具有高处理能力且装载一个AAA。基点通过指定波束方向和波束宽度选择希望校验方向区域内的节点(如图1所示)。同时,假设每个节点具有相同的通信半径r。假设恶意节点能够鉴别、获得节点密钥并侵入整个网络,每个节点都具有全局唯一标识符且攻击者可能发起串谋攻击。

1.2 安全定位定义

假设在网络内存在一定数量的恶意攻击节点并且攻击者的主要目标是使节点通过MDS算法得到的估计位置与实际位置具有较大偏差,而不是使节点无法完成定位过程,因此,DOS等很容易被发现的攻击和对其他网络协议的攻击,文中不进行分析。设网络中任意节点i的真实坐标和估计坐标分别为(xi,yi)和,则安全定位问题可表示为E,存在虫孔、女巫、泛洪、注入错误位置信息和监听位置信息等恶意攻击时,式(1)表示的最优化问题。

2 DCVM算法描述

DCVM算法中,将安全定位过程分为三个阶段。(1)定位阶段,待定位节点通过定位算法初步确定自己的位置。(2)校验阶段,基点验证待定位节点通过第一步获得的位置信息是否有效。(3)攻击点探测阶段,获得攻击点的具体信息并将攻击点从网络中删除后重复第一步。

2.1 定位阶段

文中假设T=[tj[]2×n表示2维空间中n个节点的真实位置坐标,dij(T)表示节点i和j之间的距离,则有

通过等式(4)计算得到节点i和j之间距离表示为,从而由MDS算法得到每个节点的估计坐标值。

2.2 校验阶段

根据图1所示的网络模型,设节点i的坐标为Xi[xi1,xi2],则可以通过公式(5)在基点内计算出每个节点相对于自己的角度。

基点位置信息的加密:全部基点传输的信号都通过密钥分发技术[12]建立基点与每个节点间唯一一对随机成对密钥ksi,并用密钥ksi对全部基点传输的信号进行加密。设基点与节点i的公共密钥空间为Dc,则节点i与基点的成对密钥为:

将任意节点i的坐标(xi1,xi2)与角度γi和成对密钥ksi作为4元组(dxi1,xi2),γi,ksid存储于基点内。随后,基点根据实际精度要求和网络部署情况,通过AAA适当地选择校验波束的角度α和宽度Δ对覆盖区域进行扫描,并按照公式(7)确定激化节点相对于基点的角度范围。

其中,αi和αi-1分别表示波束第i次和第i-1次变换的波束角度。节点收到基点信息后响应并将响应信息用成对密钥加密后传回基点,最后,基点由式(8)对比角度误差判断是否有攻击,若满足式(8),则接受定位信息,否则进入第三阶段。

其中,表示第i个节点所在的角度范围。

2.3 攻击点探测阶段

现有的安全定位相关算法都是仅能探测到是否存在某种恶意攻击,无法具体确定哪些节点为发起攻击的恶意节点。观察可知,对通过距离信息进行定位方法发起的恶意攻击必然会在其距离矩阵D和连通性关系矩阵o内留有痕迹,结合WSN特征对这种痕迹分析,能够找到攻击节点位置和抵御攻击的方法。

3 DCVM算法中攻击点探测的理论分析

3.1 攻击痕迹分析

设如图1所示的传感器网络受到多种恶意攻击:节点2和节点10处发起虫孔攻击;节点2同时假冒节点1的ID进行女巫攻击;根据各种攻击的特点,可知节点11、12、5、6和9直接受到虫孔和女巫攻击的影响,使:D(6,2)=D(6,10),D(11,2)=D(11,10)=D(11,1),D(12,2)=D(12,10)=D(12,1),D(9,2)=D(9,10)=D(9,1),D(5,2)=D(5,10)=D(5,1)。可以发现,攻击使间距大于2r的两节点可以一跳通信,且出现了多个节点到2个不同节点间距离相等的情况。根据上述现象,可以得到如下攻击点判定规则。

3.2 攻击点判定规则

定义(连通度):设n节点传感器网络中与某节点s可以直接通信的节点数量为Cs,则称节点s的连通度为Cs。设C=,则称C为网络平均连通度。

引理1(连通度关系):在传感器网络中n个节点均匀分布,则一定不存在可以使Ci=C,i=1,2,3,…,n的节点i。节点任意分布的传感器网络中,若存在虫孔类攻击且与虫孔攻击点A和B通信的节点集合分别为LHw1和LHw2,则能与LHw1(LHw2)内所有节点都两跳通信的节点集合一定为LHw2(LHw1)。

证明:在均匀分布n节点传感器网络中,设节点密度为ρ,则对于网络中任意节点t,有Ct=ρπr2。由于网络固有的随机性,使各处的密度不完全相同,但网络均匀部署,可以认为各处密度差距不大。因此,网络中不存在满足

的节点t。

对于任意分布传感器网络,由于LHw2内任意节点都可以和B直接通信,即可以和A直接通信,因此,LHw2内所有节点都可以与LHw1内任意节点两跳通信。假设存在一个节点k可以与LHw1中所以节点都两跳通信且不在LHw2内。即对于Ai,i∈LHw1和Aj,j∈LHw1,有r<||k-i||≤2r且r<||k-j||≤2r。当k∈LHw1时,明显存在节点i使||k-i||r,∴||k-j||=||k-A||+||j-A||>2r。因此不存在满足假设条件的节点k,所以k∈LHw2。同理可证,与LHw2内所有节点都两跳通信的节点集合一定为LHw1。

引理2:到三个不同节点距离相等的节点具有唯一性,到两个不同节点距离相等的所有节点毕竟共线。

证明:假设存在两个不同的节点i,j到三个不同节点A,B,C距离相同,即存在两不同节点i和j使||i-A||=||i-B||=||i-C||且||j-A||=||j-B||=||j-C||。由定理可知,若节点A,B,C不共线,则由A,B,C可确定唯一的一个圆,所以满足条件的节点i和j必为圆的圆心且圆心是唯一的,因此i和j必为同一个节点。若节点A,B,C共线,则节点i必须在线段的中垂线上,由于节点A,B,C共线,则的中垂线必平行、无交点,所以,满足条件的节点i不存在。因此,可知到三个不同节点距离相等的节点具有唯一性。设不同节点到不同的节点E和F满足||k-E||=||k-F||且||l-E||=||l-F||,可知节点E,F必在线段的中垂线上且由于的中垂线是唯一的,因此,可知到两个不同节点距离相等的所有节点毕竟共线。

推论1(虫孔、泛洪和女巫类攻击判断规则):均匀随机分布的传感器网络内,用于位置估计的网络连通性关系矩阵中连通度明显大于网络平均连通度的节点即为网络中的虫孔和泛洪攻击点;若网络中存在连通度特别大的节点,则认为是泛洪攻击点;若网络中存在到不同节点距离相同的多个节点,则可确定为女巫攻击点。

证明:通过分析攻击形式,发现各种攻击方法中仅虫孔和泛洪类攻击会改变网络中受攻击点的连通度,而其他攻击形式虽改变了受攻击点的连通性关系,却未改变连通度。因此,若传感器网络中n节点随机均匀分布,设用于位置估计的网络连通性关系矩阵为o1,根据引理2可知,满足

(w根据网络部署情况选择)的所有节点k集合即为虫孔和泛洪恶意攻击点。若虫孔攻击者同时使用女巫攻击,则女巫攻击点必然具有多个不同节点(锚点)的ID,因而,会出现多个不同节点到与女巫攻击者通信范围内所有节点的距离相等,设女巫攻击者为节点i并冒充节点(锚点)i1,i2,i3,…,in,与节点i通信的所有节点集合为LHS,则Aj,j∈LHS有||ji1||=||ji2||=||ji3||=…=||jin||,||||表示两点间距离。则根据引理3可知,当LHS内节点多于3个时,节点i为女巫攻击点;当LHS内节点为2个时,如n小于3且i1,i2,i3,…,in位置不在LHS内2个节点的中垂线上,或n≥3则节点i为女巫攻击点;当LHS内节点为1个时且节点i1,i2,i3,…,in不共圆,则节点i为女巫攻击点。

4 仿真与性能评估

为了仿真提出的DCVM算法,文中假设N=28个节点均匀分布在单位圆内,假设所有节点的通信范围均为0.5。同时为了评估各种攻击对定位性能的破坏程度,假设M=10个锚点中,锚点2(ID2)和节点10(ID10)发起虫孔攻击,并且锚点2(ID2)同时发起女巫攻击;锚点4(ID4)发起泛洪攻击。当网络同时受到上述攻击时,对比分析了未受恶意攻击的MDS定位性能、受到上述恶意攻击时MDS定位性能和加入DCVM算法后同样受到上述恶意攻击时的MDS定位性能。同时,为了分析不同环境下DCVM算法攻击点探测的有效性,对锚点中恶意锚点的不同比例、节点不同通信半径、不同连通度阀值K等情况下的探测率(DR)与误探测率(FR)进行了仿真分析。

仿真结果如图2、图3所示。图2、图3表明,对于节点随机部署均匀分布的静态传感器网络,提出的DCVM算法通过选择合适的参数,对攻击点能够获得高于98%的探测率且误探测率低于6%。

5 结束语

文中提出一种适用于安全定位设计的高效安全定位算法,并分析了存在恶意攻击时,采用该算法下的MDS设计定位性能。由于DCVM建立的主要基础是节点间的距离和连通性关系。因此,该策略对各种定位算法具有极好的普适性。同时,该策略非常简单,嵌入到定位算法中引起的通信、计算过载和复杂度都很低。仿真结果表明,对于随机部署均匀分布的传感器网络,文中提出的DCVM有效地改善了恶意攻击条件下,MDS设计的定位性能。

参考文献

[1]Hill J L.System Architecture for Wireless Sensor Networks.Berkeley:UC Berkeley,2003

[2]Akyildiz I F,Sankarasubramaniam S Y,Cayirci E.Wireless sensor networks:a survey.Computer Networks,2001,38(12):393～422

[3]Cui J H,Kong J J,Mario G,Zhou S L.The challenges of building scalable mobile underwater wireless sensor networks for aquatic appli-cations.IEEE Network,2006,20(3):12～18

[4]Hideki O,Patrick M,Vincent P H,Vahid T.Collaborative beamforming for distributed wireless ad hoc sensor networks.IEEE Trans Signal Process,2005,53(11):4110～4124

[5]Yip L.Array Signal Processing for Source DOA Estimation and Source Localization in a Distributed Sensor Network.Los Angeles:Uni-versity of California at Los Angeles,2004

[6]Loukas L,Radha P.HiRLoc:High-resolution robust localization for wireless sensor networks.IEEE J Sel Areas Commun,2006,24(2):233～246