维普资讯 http://www.cqvip.com 总第１６０期 ２００７年第４期 舰船电子工程 Ｓｈｉｐ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖ０１．２７ Ｎｏ．４ ７０ 三维空间中无线传感器网络节点定位算法 郭昀罗志祥贾亚黎 （华中科技大学光电子科学与工程学院武汉４３００７４） 摘要节点定位技术是无线传感器网络的关键技术之一。提出一种距离无关的三维空间节点定位算法。传感器节 点的硬件设计使传感器节点具有可以调节的通信半径。在保证网络连通性的前提下通过改变通信半径来提高定位的精 度，达到减少误差的目的。仿真结果表明，该算法可以达到较高的定位精度，满足应用需要。 关键词无线传感器网络；节点定位；距离无关算法 ＴＰ３０１ 中图分类号１ 引言 无线传感器网络（ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ， ＷＳＮ）就是由部署在监测区域内的大量的廉价微 ＤＶ—ｄｉｓｔａｎｃｅ定位算法，Ｅｕｃｌｉｄｅａｎ定位算法，ＤＶ— ｃｏｏｒｄｉｎａｔｅ定位算法，ＤＶ—Ｂｅａｒｉｎｇ算法和ＤＶ—Ｒａ— ｄｉａｌ算法；Ｃｏｏｐｅｒａｔｉｖｅ ｒａｎｇｉｎｇ和Ｔｗｏ—Ｐｈａｓｅ ｐｏｓｉ— ｔｉｏｎｉｎｇ定位算法，ＡＨＬｏｓ（ａｄ—ｈｏｃ ｌｏｃａｌｉｚａｔｉｏｎ ｓｙｓ— ｔｅｍ）和ｎ—ｈｏｐ ｍｕｌｔｉｌａｔｅｒａｔｉｏｎ ｐｒｉｍｉｔｉｖｅ定位算法； 通用型定位算法，ＭＤＳ—ＭＡＰ定位算法。 型传感器节点组成，通过无线通信方式形成的一个 多跳的自组织的网络系统，其目的是协作地感知、 采集和处理网络覆盖区域中感知对象的信息，并发 送给观察者。无线传感器网络在军事领域和民用 领域都有着广泛的应用。 节点定位技术是无线传感器网络的关键技术 之一。位置信息是传感器网络中不可缺少的部分， 大部分定位算法都是基于二维平面的算法。 在实际应用中，节点的分布往往在三维空间，地形 比较复杂的环境中，二维平面中的算法在应用中会 有很多问题。因此，三维空间中节点定位算法十分 必要。 没有位置信息的数据往往是不具有任何意义的。 许多国家的研究机构都对无线传感器网络的 节点定位算法和系统展开了研究，到目前为止，无 线传感器网络自身定位系统和算法的研究大致经 过了两个阶段。 ２算法理论 在传感器节点定位技术中，根据节点是否已知 自身位置，可以将节点分为信标节点（ｂｅａｃｏｎ ｎｏｄｅ）和未知节点（ｕｎｋｎｏｗｎ ｎｏｄｅ）。信标节点在网 络节点中所占的比例很小，可以通过携带ＧＰＳ定 位设备等手段获得自身的精确位置。信标节点是 未知节点定位的参考点。除了信标节点外，其他传 感器节点就是未知节点，它们通过信标节点的位置 第１阶段主要偏重于紧密耦合型和基于基础 设施的定位系统，代表性的研究成果包括ＲＡＤＡＲ， Ａｃｔｉｖｅ Ｂａｔ，Ａｃｔｉｖｅ Ｂａｄｇｅ，ＲａｄｉｏＣａｍｅｒａ，Ａｃｔｉｖｅ Ｏｆ－ ｉｃｅ，Ｅａｓｙ Ｌｉｒｖｉｎｇ，ＳｐｏｔＯＮ，ＨｉＢａｌｌ Ｔｒａｃｋｅｒ，Ｐａｒｃ ＴＡＢ， Ｓｍａｒｔ Ｆｌｏｏｒ，Ｓｍａｒｔ Ｒｏｏｍｓ，３Ｄ—ｉＤ，ＷｈｅｒｅＮｅｔ等。 对于松散耦合型和无须基础设施的定位技术 的关注和研究可以认为是自身定位系统和算法研 究的第２阶段，目前已经成为ＷＳＮ领域一个不小 的热点。典型的节点自定位算法有以下几种： Ｃｒｉｃｋｅｔ定位系统，ＳＰＡ相对定位算法，凸规划定位 算法，ａｄ ｈｏｃ定位系统，包括：ＤＶ—Ｈｏｐ定位算法， 信息来确定自身的位置。 在整个网络系统中，信标节点占很小的比例， 大部分网络节点是必须凭借其他节点才能定位的 全功能未知节点。带有自定位系统的节点成本高 昂，不能够在网络中大量使用。 在三维坐标系中，假设点有ｎ个信标节点，坐 收稿日期：２００７年２月１ １３，修回日期：２００７年３月１４ １３ 作者简介：郭昀，女，硕士研究生，研究方向：无线通信。罗志祥，男，副教授，研究方向：光电检测（传感）与信息处理。 贾亚黎，女，硕士研究生，研究方向：宽带通信网。 维普资讯 http://www.cqvip.com ２００７年第４期 舰船电子工程 ７１ 标分别为（ｘｌ，Ｙ１，ｚ１），（ｘ２，Ｙ２，ｚ２），（ｘ３，Ｙ３，ｚ３）， ……，（Ｘ ，Ｙ ，ｚ ），有一个未知节点ｘ，坐标为（Ｘ， ｙ，ｚ）。节点Ｘ到各点的距离分别为ｄ 、ｄ 、ｄ 、…… ｄ ，则有以下公式： （ — １） ＋（Ｙ—Ｙ１） ＋（ｚ—ｚ１） ＝ｄ１ （ — ２） ＋（Ｙ—Ｙ２） ＋（ｚ—ｚ２） ＝ｄ２ ￣／（ — ） ＋（Ｙ—Ｙ ） ＋（ｚ—Ｚｎ）。＝ｄ （１） 从第一个方程分别减去最后一个方程得到： ～ 一２（ＸＩ一 ） ＋Ｙｌ 一Ｙ 一２（ＹＩ—Ｙ ）Ｙ＋ Ｉ 一 ｚ ＋２（ｚ１一ｚ ）＝ｄ１ ｄ ｘ 一１ 一ｘ 一２（ｘ 一１一ｘ ）ｘ＋Ｙ 一１ 一Ｙ 一２（Ｙ 一ｌ～ Ｙ ）ｙ＋２ 一１ ～ｚ ＋２（ｚ 一１一ｚ ）＝ｄ 一１ 一ｄ 上面的线性方程表示为：ＡＸ＝ｂ，其中： ｒ ２（ｘ 一 ） ２（Ｙ 一Ｙ ） ２（ｚ 一ｚ ）、 Ａ＝Ｉ ｉ ｉ Ｉ Ｉ２（ 一 ～ ）２（Ｙ 一 －ｙ ）２（ｚ 一 一ｚ ）／Ｉ ｒ， １ 一 ＋ｙ１ 一 ＋ １ 一ｚ ＋ｄ ｄ１ 、 ｂ＝ｌ ｉ ｝， ￣Ｘｎ＿１ ２一一 ＋ 一Ｙｎ 一 一１ Ｙ ＋ ｎ Ｚｎ一 一Ｚ 一１ 十ｎｎ ＋ 一ｄ 一 ｎ＿１１／２／ 使用标准的最小均方差估计方法可以得到节点ｘ 的坐标为 Ｘ＝（ＡｒＡ） Ａｒｂ （２） 上面的方法是最大似然法在三维空问中的推广。 通过上面的方法可以看出，三维空间中的节点 定位最终转化为求未知节点到各个信标节点的距 离。只要距离确定，就可以根据上面推导出的公式 计算出未知节点的坐标。 在ＤＶ—Ｈｏｐ算法中，采用节点之间平均跳段 距离和节点间跳段数来计算未知节点到信标节点 的距离，再通过最大似然法估算未知节点的坐标。 在本算法中，采用与ＤＶ—Ｈｏｐ相似的理论，通 过估算节点之间的距离来计算法未知节点的位置。 不同的是，在本算法中传感器节点可以通过调节发 射功率来调节通信半径，设节点的通信发射能量可 以为Ｅ 、Ｅ 、……Ｅ ，与此对应的通信半径为ｒ 、ｒ 、 ……ｒ ，每个传感器节点都能够向周围空间以 为 半径发射信息。 无线通信的能量消耗与通信距离的关系是： Ｅ＝ｋｄ ‘ 其中，参数ｍ满足关系２＜ｍ＜４。ｍ的取值与很 多因素有关，例如传感器节点部署贴近地面时，障 碍物多，干扰大，ｍ的取值就达；天线质量对信号发 现和质量的影响也很大。考虑诸多因素，通常ｍ 的取值为３，即通信的能耗与距离的三次方成正 比。随着通信距离的增加，能耗急剧增加。因此， 在满足联通度的前提下应尽量减少单跳通信距离。 算法由以下几个步骤组成： （１）确定各个节点到信标节点的跳段数和各 个通信半径。 信标节点首先以最大通信能量Ｅ 向周围发射 信息，周围的节点收到节点发送的信息后，向节点发 送信号，完成一次“握手”，那么信标节点可以知道在 通信半径为１ＴＩ时的邻居节点数目Ｎ 如果Ｎ 过 大，则减少发射能量，通信半径减少到ｒ ，重复上 述过程，一直到邻居节点数目合适，此时的通信半径 为ｒ 。各个信标节点都向邻居节点发射自身信息分 组，包括：节点编号，位置，通信半径，跳数字段。 各个未知节点得到信标节点的信息后，将跳数 加１，并转发给邻居节点。通过不断的转发信息， 所有节点都会获得到信标节点的段数，各个通信半 径。接收节点记录具有到每个信标节点的最小跳 数，忽略来自同一个信标节点的较大跳数的分组。 （２）计算各个信标节点的距离，确定计算公式。 各个信标节点的坐标已知，可以通过坐标来计 算它们之间的实际距离。通过各个信标节点之间 的实际距离和估算距离来估计各个未知节点到各 信标节点的距离。各个节点到信标节点之间的距 离可以由以下公式估算： ｈ＝Ｊｉ｝（ｒＡ１＋ｒＡ２＋…＋ｒ ） （３） 其中，ｈ是节点到信标节点Ａ的距离，ｒ 是到信标 节点Ａ跳段数为ｎ一１的节点向到Ａ的跳段数为ｎ 的节点发射信息的通信半径，ｋ是比例系数。 （３）计算各个未知节点到信标节点之间的距离。 得到比例系数ｋ之后，可以计算未知节点到各 个信标节点之间的距离。 最后，用极大似然法由公式（２）计算各个未知 节点的坐标。 ３算法仿真 将三维空间中分布的节点部署在直角坐标系 的第一象限，部署１００个传感器节点，其中１０％为 （下转第７５页） 维普资讯 http://www.cqvip.com ２００７年第４期 舰船电子工程 技大学出版社，２００４：９６～９７ ７５ 在架设前无法预知，一般情况下天线耦合度数据要 需要测量来获得。因此预测天线之间的耦合度对 ［３］Ｒ．Ｆ．哈林登．计算电磁场的矩量法［Ｍ］．北京：电 实际工程中短波天线布局有重要的指导意义。 参考文献 ［１］陈穷．电子兼容工程设计手册［Ｍ］．北京：国防工 业出版社，１９９３：１０６２～１０６４ ［２］卢万铮．天线理论与技术［Ｍ］．西安：西安电子科 （上接第７１页） 信标节点。节点分布在６００（米）×６００（米）×６０ （米）的空间中。节点的通信半径可以有１００米、 ２００米、３００米、４００米和５００米五个调节值。仿真 流程如下： 步骤一，循环判断各个信标节点的邻居节点， 分别标识。 步骤二，已经标识的各个未知节点再周围邻居 发送信号，使用上一步骤选定的通信半径Ｒ。完成 各个个节点标识位的标注之后，统计每个信标节点 的ｎ跳节点和所有跳段能够连通的节点，如果可以 连通９０％的节点则不改变通信半径，如果有较多 的节点不能够连通到网络中，则增大通信半径。 步骤三，计算公式中的系数ｋ。 步骤四，计算各个未知节点到各信标的距离。 步骤五，用极大似然法计算各个未知节点的 坐标。 ４０ 差２５ 襄翟 桌 一一３Ｏ－——— — Ｏ——一一 ０ ２Ｏ０ ４００ ６００ ８００ 节点覆盖区域宽度（单位：米） 图１仿真结果 ４ 仿真结果 在不同的节点覆盖平面范围下进行仿真，可以 得到不同的定位误差结果。在覆盖范围分别为 ８００（米）×８００（米）×６０（米），７００（米）×７００（米） ｘ６０（米），６００（米）ｘ６００（米）×６０（米），５００（米） 子工业出版社，１９８１：１９～２２ ［４］廖承恩．微波技术基础［Ｍ］．西安：西安电子科技 大学出版社，１９９５：１９７～２１６ ５］Ａ．Ｄｅｍｅｒｙｄ ａｎｄ Ｇ．Ｋｒｉｓｔｅｎｓｓｏｎ．Ｓｉｇｎａｌ ｃｏｒｒｅｌａｔｉｏｎ ｉｎ－ ｃｌｕｄｉｎｇ ａｎｔｅｎｎａ ｃｏｕｐｌｉｎｇ［Ｊ］．Ｅｌｅｃｔｒｏｎｉｃｓ ｌｅａｅｒｓ，２００４，４ｏ（３） ×５００（米）×６０（米）、４００（米）×４００（米）×５０ （米）时进行仿真，可以得到结果定位误差如下图 所示。图中横坐标表示的是覆盖区域的横坐标值， 纵坐标与其相等，Ｚ坐标不变。由结果可知，该算法 可以满足一般的野外环境监测。 ５ 总结 文章详细介绍了三维空间节点定位算法的理 论和仿真，并且通过仿真找到合适的节点密度分 布。结果表明，该算法能够达到一定的精度，满足 实际应用需要。 参考文献 ［１］孙利民，李建中，陈渝等．无线传感器网络［Ｍ］．清 华大学出版社 ［２］王秉曼，石晓军．无线传感器网络基于测距定位算 法的实现［Ｊ］．科技资讯，２００６，２：１４３～１４４ ［３］Ｎｉｃｏｌｅｓｃｕ Ｄ，Ｎａｔｈ Ｂ．Ａｄ—Ｈｏｃ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍｓ （ＡＰＳ）．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ ２００１ ＩＥＥＥ Ｇｌｏｂａｌ Ｔｅｌｅｃｏｍｍｕｎｉｃａ— ｔｉｏｎｓ Ｃｏｎｆ Ｃ］．Ｓａｎ Ａｎｔｏｎｉｏ：ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｏｃｉｅｔｙ， ２００１：２９２６～２９３１ ［４］陈维克，李文峰，首珩等．基于ＲＳＳＩ的无线传感器 网络加权质心定位算法［Ｊ］．武汉理工大学学报，２００６，３０ （２）：２６５～２６８ ［５］Ｓｕｎｄａｒａｍ Ｎ，Ｒａｍａｎａｔｈａｎ Ｐ．Ｃｏｎｎｅｃｔｉｖｉｔｙ ｂａｓｅｄ ｌｏ— ｃａｔｉｏｎ ｅｓｔｉｍａｔｉｏｎ ｓｃｈｅｍｅ ｆｏｒ ｗｉｒｅｌｅｓｓ ａｄ ｈｏｅ ｎｅｔｗｏｒｋｓ［Ｃ］．Ｉｎ： Ｐｒｏｃ．ｏｆ ｔｈｅ ２００２ ＩＥＥＥ Ｇｌｏｂａｌ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｃｏｎｆ．Ｔａｉ． ｐｅｉ：ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｏｃｉｅｔｙ，２００２，１：１４３～１４７ ［６］Ｈｉｇｈｔｏｗｅｒ Ｊ，Ｂｏｒｉｅｌｌｏ Ｇ，Ｗａｎｔ Ｒ．ＳｐｏｔＯＮ：Ａｎ ｉｎ— ｄｏｏｒ ３Ｄ ｌｏｃａｔｉｏｎ ｓｅｎｓｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｂａｓｅｄ ｏｎ ＲＦ ｓｉｇｎａｌ ｓｔｒｅｎｇｔｈ ［Ｒ］．Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏ￣ＵＷ ＣＳＥ ２０００—０２—０２，Ｓｅａｔｔｌｅ：Ｄｅ— ｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｗａｓｈｉｎｇｔｏｎ，２０００
