一种复杂环境中WSN锚节点的布置算法研究

1、假设：假设一：在二维空间下，每个无线传感器节点其探测范围 为一个半径为 R 的圆，面积为 。假设二：每个障碍物吸收的功率恒定的，即每个障碍物阻碍的探测距离是一定的，假设为 D, 且 D<R;假设三：障碍物为矩形平面，障碍物于临近节点之间的距 离为 L，且 L<R；假设四：三个相邻节点所覆盖的区域相交于一点，且三个节点组成一个等边三角形，该节点铺设方法在文献已经被证明 为在没有障碍物的理想情况下是使用节点数目最少的。由以上假设可知，障碍物把被测空间分隔成一个个的理想 空间。在障碍物的阻隔情况下，一些临近障碍物的节点的覆盖 范围将减少，故会出现节点覆盖不到的盲区。如图一所示的阴影区。3

2、 节点布置模型描述3.1 模型分类 在有障碍物的情况下，一个节点被障碍物阻隔后，它的覆盖范围就不是一个严格意义上的圆了：在不经过障碍物的地方，它覆盖的仍然是一个以它本来的覆盖半径 R 为半径的圆的 一部分，但经过障碍物的阻隔以后，由于障碍物吸收功率从而 阻碍探测距离，会导致节点覆盖范围的减小，它所覆盖的范围 仍然是一个圆形，只是半径减小为 ，其中 D 为障碍物阻碍 的探测距离;在节点覆盖半径一定的情况下，覆盖盲区只和障碍 物距离邻近节点的距离 L，障碍物阻碍的探测距离 D 相关。故按照节点覆盖半径 R，障碍物距离邻近节点的距离 L 和 障碍物阻碍的探测距离 D 之间的关系，建立模型。在节点覆盖

3、半径一定的情况下，可以建立四个模型：第一：;第二：；一种复杂环境中锚节点的布置算法研究WSNResearch of A WSN Anchor Points Deployment Algorithm in The Complex Enviroment(1.中国科学院研究生院;2.中国科学院沈阳计算技术研究所) 蒲宝明 2李爱华 1，2 王金英 2 李清 1，2PU Bao-ming LI Ai-hua WANG Jin-ying LI Qing摘要: 在 无线传感器网络的定位研究中 , 现有的节点布置算法都是在不考虑障碍物存在的理想情况下提出的 。 本 文 构 建 出 存在 障碍物的二维空间模型

4、 , 并提出一种无线传感器 网络锚节点布置算法 DABTG (Deployment of Anchor -points Based BarrierdTriangle Grid) 。 该算法在三角形网格的基础上 , 有 序 增 加 节 点 数 量 ,DABTG 在有障碍物存在的情况下可达到被测区域的完全覆盖 。关键词: 无线传感器网络; 锚节点; 三角形网格; 覆盖; 障碍物在节点覆盖区域的交点处放置节点 。仿 真 表 明 ,算 法中图分类号: TP393.09文献标识码: AAbstract: In researching position of wireless sensor network

5、, the existing anchor points deployment algorithm takes no account of theobstacles and this is ideal condition. The paper constructs a model with the existence of obstacles in a 2 -D space and states a new anchor points deployment algorithm DABTG (Deployment of Anchor -point Based Barrierd Triangle

6、Grid). Based on the triangular grid, This algorithm increases the anchor point orderly and puts it at the intersection of the anchor point coverage field .Proved bysimulation ,the algorithm DABTG can make the measured region completely covered even under the obstacle circumstance .Key words: Wirless

7、 SensorNetworks(WSN); Anchor Point; Triangulated network; Coverage; Barrier引言1无线传感器网络（Wirless Sensor Networks,WSN），是近几年来计算机领域研究的热点之一。它的研究内容有很多，在利用 无线传感器网络定位的应用中，锚节点布局是其中很重要的一 部分。随着技术的发展，锚节点布局上也有很多的研究成果文献中从理论上给出了一个在没有考虑障碍物存在的理 想状况下，实现完全无缝连接和覆盖的传感器区域内最少需要 多少节点的解析表达式。文献中提出了一种能够保持网络覆盖质量的分布式节点调度机制 CPNSS

8、- 通过减少任意时刻网络 中的活跃节点数来降低网络覆盖冗余，有效减少冗余数据传输导致的能量消耗，延长无线传感器网络的生存时间。文献根据 三角形网中相邻三角形之间的拓扑关系以及交线的连续性，提 出了一种基于拓扑搜索的三角形求交算法。文献基于三角形折 叠的方法，对误差矩阵的计算和误差控制方法进行了改进，并 且提出了几何及属性边界三角形的概念，给出了一种保留原始模型边界及属性信息的简化算法。纵观以上的文献研究，不难看出覆盖是无线传感器网络中 一个比较重要的问题，节点的铺设方法是覆盖中不可回避的问 题。现有的研究偏重于没有任何障碍物的理想情况下，但在实 际应用中，这种理想情况是很少有甚或是不存在的，这

9、就给 WSN 在实际中的应用造成了一定的困难。本文研究的主要问题 就是：确定一个锚节点定位算法以保证在有障碍物存在时被测 区域的完全覆盖并使得所需节点个数最少。问题描述2在利用节点定位时，对存在障碍物的环境进行以下理论蒲宝明: 硕士生导师 研究员第三：； 第四：。S 的存在就代表了覆盖的盲点。这个覆盖盲点的问题该如考虑到实际中二，三，四三种模型中，覆盖盲区比较小，本何解决？这就是本文研究的重点，也是在实际应用中我们最为 文主要研究第一种情况下的覆盖盲区的覆盖问题。第一种情况关注的一点。下节点布置情况如图 1 所示。3.3 问题求解DABTG 算法 由假设可知，每个节点的覆盖范围都是一个半径为

10、R 的圆，面积为 ,且每个节点的覆盖范围都一样大。所以提出 DABTG 算法：在临近障碍物的三节点覆盖区域交点处，放置一 颗同样的节点，该节点的覆盖半径依然为 R，下面来证明这个节点的覆盖范围可以覆盖住因障碍物而造成的覆盖盲区。还是以图 1 为例：解决覆盖盲区的办法就是在点 J 处再放 置一个节点，该节点的覆盖范围为,故只需证明该覆盖范图 1 第一类模型中锚节点铺设情况围包括点 A 和点 B 即可。Fig.1 Deployment of anchor-point in the first model因为三个圆的圆心 O1,O2,O3 是一个等边三角形的 三个定点，因此有对称性知道：线段 JA

11、的长度 线段 JB 的长度 图 1 中线段 JC1 的长度 ×2；由于是一个等边三角形，C1 是边 O1O2 的中点，J是三角形的重心。所以故线段 JC1 的长度为 R/2;图 2 存在障碍物的情况下锚节点铺设情况因此以 J 为圆心，以 R 为半径的圆可以覆盖原来的覆盖盲Fig.2 Deployment of anchor points in the filed with barried区 S。3.2 覆盖盲区面积下面主要计算图 1 所示的阴影部分的面积。4 DABTG 算法仿真测试由文献我们知道，圆 O1 和圆 O2 相交部分的面积为:假设被测区域为 100m*50m 的矩形，每一

12、个节点的覆盖范围是半径为 10m 的圆，区域内有一个障碍物，障碍物把该区域阴影部分中 ACFIJ 的面积就为：分成两个区域，在 Matlab 上进行仿真。扇形 AJIO1 的面积圆 O1 和圆 O3 相交部分的面首先在不考虑障碍物的情况下，遵循三角定位算法，进行积扇形 CO1F 的面积三角形 FIO1 的面积；节点的铺设，节点铺设情况如图 2 所示，其中的阴影部分就是其中：覆盖盲区。由问题描述中可以得到图二中阴影部分的面积 Q1）若令，则（3-1） 当 R 一定为 10，L 一定为 3 时，此时阴影部分的面积与 D2）的关系如图 3 中实线所示；当 R 一定为 10，D 一定为 5 时，此时3

13、）若令角 CO1F，则阴影部分的面积与 L 的关系如图 3 中虚线所示。这两种情况下，(3-2)即使遵循三角定位算法增加节点，也不能保证被测范围的完全4）三角形 FIO1 的面积等于三角形 EO1I 的面积覆盖，此时覆盖盲区的比例最大将分别达到 9.758和 8.72。减去三角形 EO1F 的面积；其中：故（3-3） 由（3-1），(3-2)，（3-3）可知：（3-4）由图 1 可以看出，阴影部分的面积为 S1/2 减去 MNPI 的面图 3 覆盖盲区的面积于 L，D 的关系积，MNPI 类似于矩形，它的面积：Fig.3 Relationship between regionuncovered

14、 and L/D（3-5） 所以，总的阴影部分 ACFIHDBJ 的面积 S:（3-6） 把(3-6)化简得：（3-7） 图 4 DABTG 算法中锚节点铺设此时。Fig 4. Deployment of anchor points using algorithm DABTG传 感 器 与 仪 器 仪 表邮局订阅号：82-946 360 元 / 年 - 149 -PLC 技术应用 200 例您的论文得到两院院士关注结论节点的布置情况如图 4 所示。由图 4 可以看出，图 2 中的阴影部分被完全覆盖。这就意味着被测区域被完全覆盖，不存在覆 盖盲区。由图 2 和图 4 的比较可知，DABTG 算法

15、具有有效提高提 高覆盖范围的作用。该仿真也很好得验证了算法 DABTG。5为了方便开发具有自主知识产权的 GPS 软件接收机，我们基于 SuperstarII 的 Marconi 二进制数据格式开发了 GPS 数据采 集软件。本软件可提供用于进行卫星位置计算、轨道拟合、误差修正、定位解算、测速及授时等算法研究的原始数据；可利用误差放大因子、定位测速结果等最终数据进行 GPS 数据采集时段 选择，以获得较高质量的定位数据；生成定位结果及性能的动 态文件，可供在 MATLAB 和 C 语言平台上进行算法优化处理。 本文设计的方法已应用在速度 8Km/s，加速度 8g，加加速度为1g/s2，位置精度

16、 17m 的 GPS 软件接收机中。本文创新点:1、在掌握 Marconi 二进制数据格式的基础上， 实现了 ID20、ID21、ID22、ID23 和 ID75 模块相关参数的解调，并基此完成了数据解调软件。2、基于解调的结果，实现了卫星 位置计算、误差修正等功能，验证了数据解调软件的正确性。参考文献1GPS -ICD -200 StandardOperation& Technical manual ofAshtech GPS S20032SUPERSTAR II User Manual S. Canda. 2005 3李洪涛等GPS 应用程序设计M北京：科学出版社，1999， 4程

17、义军.基于 IGS 精密星历的 GPS 卫星轨道分析D.武汉：武 汉大学.20055胡 辉.高动态数字化 GPS 接收机的研制R. 哈尔滨：哈尔滨 工业大学. 20026顾必良.基于 VC+的 GPS 数据采集和处理J.微计算机信息,2008.05-1：203-204作者简介： 胡 辉（1970-），男（汉族），江西南昌人，华东交通大 学信息工程学院副教授，上海航天技术研究院博士后，主要研究方向：卫星导航定位，并行算法与并行处理，机器视觉。叶鑫华（1979-），男（汉族），华东交通大学通信与信息系统专业硕士 研究生，研究方向为卫星导航定位。Biography: HU Hui (1970 - )

18、,Male (Han Nationality),the Jiangxi结论5本文构建 2D 模型并提出 DABTG 算法：在临近障碍物的节点覆盖区域相交处再放置一枚同样的节点，以避免出现覆盖盲 区。DABTG 算法可以很好地避免覆盖盲区的出现，达到了完全覆盖的效果，提高了实际中的可行性，同时还使得所需节点个数相对最少，降低了应用成本，这将在实际应用中发挥更大的 作用。本文创新点:提出一种 DABTG 算法，很好地解决了在有障 碍物存在的情况下无线传感器网络中节点布置算法中的覆盖 盲区问题。同时使得所用锚节点数量最少，降低了覆盖成本，并 提高了覆盖效率。参考文献1蒋 杰. 无线传感器网络覆盖控制

19、研究D，长沙：国防科学技 术大学，2005.2沈旭昆，赵学伟，齐 越，蔡 苏.一种保留几何及属性边界的网 格简化方法 J，北京航空航天大学学报.2006.32 （12）：14851489.3罗 卫,陶 洋.WSN 中基于网格的覆盖控制与群优化研究J,微 计算机信息,2008,1-1：126-127.作者简介: 蒲宝明（1966），男（汉族），中科院沈阳计算技术研 究所硕士生导师，研究员，主要研究方向：无线传感器网络、嵌入式系统结构与操作系统;李爱华（1982），女（汉族），中科院沈 阳计算技术研究所硕士研究生，主要研究方向为无线传感器网络、嵌入式系统结构与操作系统;王金英（1978），女（汉族

20、），中 科院沈阳计算技术研究所，助理研究员，主要方向：无线传感器网络、嵌入式系统结构与操作系统。李 清（1983-）女（满族），中 科院沈阳计算技术研究所硕士研究生，主要研究方向为无线传感器网络、嵌入式系统结构与操作系统。Biography: PU Bao - ming ，male ，born in 1966 ，Master's Tutor ， researcher of Shenyang Institute of Computing Technology ，Major research direction: Wirless sensor networks,Embedded system ar- chitecture and operating systemNanchang,AssociateProfessorof SchoolofInformationEngineering, East China Jiao Tong Un