无线节点定位技术课件.ppt

《无线节点定位技术课件.ppt》由会员分享，可在线阅读，更多相关《无线节点定位技术课件.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、l 节点定位技术概述l 节点定位技术研究现状与发展l 节点定位技术关键问题l 基于测距的定位技术l 无需测距的定位技术l 协作定位技术无线节点定位技术1 ppt 课件无线传感器网络节点定位：依靠网络中少量的位置已知的节点，通过邻居节点间有限的通信和某种定位机制确定网络中所有未知节点的位置。节点定位在实际应用中包含两种含义：自定位 确定节点自身在系统中的位置 目标定位 确定目标节点在系统中的位置l 节点定位技术概述2 ppt 课件 信 标 节 点：已 知 自 身 位 置 信 息 的 节 点，可 通 过GPS定 位 设 备 或 手工 配 置、确 定 部 署 等 方 式 预 先 获 取 位 置 信

2、息，为 其 他 节 点 提 供 参考坐标。未 知 节 点：信 标 节 点 以 外 的 节 点 统 称 为 未 知 节 点，也 有 文 献 称 为盲节点。邻居节点：一个节点通信距离范围内的所有节点的集合。跳数：两个节点之间跳段的总数。跳距：两个节点之间各跳段的距离之和。节点连接度：节点可以探测发现到的邻居节点个数。网 络 连 接 度：所 有 节 点 的 邻 居 个 数 取 平 均 值，可 反 映 传 感 器 配 置的密集程度l 节点定位技术概述一些概念3 ppt 课件传感器网络的定位算法通常需要具备以下特点：自 组 织 性：传 感 器 网 络 的 节 点 随 机 部 署，不 依 赖 于 全 局

3、基 础 设 施 协 助 定位；健 壮 性：传 感 器 节 点 的 硬 件 配 置 低，能 量 有 限，可 靠 性 较 差，定 位 算 法必须能够容忍节点失效和测距误差；节 能 性：尽 可 能 地 减 少 算 法 中 计 算 的 算 法 复 杂 度，减 少 节 点 间 的 通 信 开销，以尽量延长网络的生存周期；分 布 式：无 线 传 感 器 网 络 通 常 是 大 规 模 部 署 网 络，节 点 数 目 多，定 位 任务 将 不 会 是 单 个 节 点 所 能 承 担 的，这 就 需 要 定 位 算 法 具 有 一 定 的 分 布 式，把任务分派到各个节点；可 扩 展 性：无 线 传 感 器

4、网 络 中 的 节 点 数 目 可 能 是 成 千 上 万 甚 至 更 多，为了满足对不同规模的网络的适用性，定位算法必须具有较强的可扩展性。l 节点定位技术概述要求4 ppt 课件 作 为 一 种 全 新 的 技 术，无 线 传 感 器 网 络 具 有 许 多 挑 战 性 的 研 究 课 题，而 定位就是其中之一，定位也是大多数应用的基础和前提 传 感 器 节 点 的 微 型 化 和 有 限 的 电 池 供 电 能 力 使 其 在 节 点 硬 件 的 选 择 上 受 到很 大 的 限 制，低 功 耗 是 其 最 主 要 的 设 计 目 标。必 须 针 对 密 集 性，节 点 的 计 算、存储

5、和通信等能力都有限的特定场合设计有效的低功耗定位算法 近 十 年 来，无 线 传 感 器 网 络 自 身 定 位 问 题 研 究 有 了 许 多 新 颖 的 解 决 方 案 和思 想，但 是 每 种 系 统 和 算 法 都 是 用 来 解 决 不 同 的 问 题 或 支 持 不 同 的 应 用 的，它 们 用 于 定 位 的 物 理 现 象、传 感 器 设 备 的 组 成、能 量 需 求、基 础 设 施 和 时 空的复杂性等许多方面有所不同。对 现 有 的WSN 定 位 研 究 成 果 研 究 比 较 发 现，没 有 一 种 定 位 方 案 能 在 有 效 减少 通 信 开 销、降 低 功 耗

6、、节 省 网 络 带 宽 的 同 时 获 得 较 高 的 定 位 精 度。而 且 大部 分 停 留 在 仿 真 和 实 验 阶 段。因 此，该 领 域 还 有 待 更 多 的 人 提 出 更 好 的 方 法，以 求 更 好 地 解 决 定 位 问 题，使 得 无 线 传 感 器 网 络 能 够 真 正 在 实 际 生 活 中 得 到广泛的应用。l 节点定位技术的研究现状和发展5 ppt 课件目前，在节点定位应用中，由于受传感器节点能量有限、可靠性差、网络规模大且节点随机布放、无线模块的通信距离有限等影响，对定位算法和定位技术提出了很高的要求。一般来说我们从定位区域与精确度、实时性和能耗三个方面

7、来衡量节点定位技术的好坏。1 定位区域与精确度定位区域与精确度是传统定位方法和无线传感器网络定位都具有的衡量指标，而且定位区域和精度一般都是互补存在的，定位区域越大，意味着精度越小。2 实时性实时性是定位技术的另外一个关键指标，实时性与位置信息的更新频率密切相关，位置信息更新频率越高，实时性越强3 能耗能耗是无线传感器网络独有的一个衡量指标。在无线传感器网络中，节点的电能靠电池来供应，电池是不可替换的，因此节省能量就成了无线传感器网络中一个重要的问题。另外，还有一些小的方面来衡量无线传感器网络定位技术的好坏，如定位技术的扩展性、鲁棒性和节点带宽的占用等。l 节点定位技术的研究现状和发展6 pp

8、t 课件 利用信标节点的位置，通过测量和估计信标节点与目标节点的距离，我们就能够利用它们之间的关系很容易地算出目标节点的位置。基 于 测 距 的 定 位 技 术 涉 及 几 何 中 的 图 形 问 题，已 知 节点的位置，求另外几个节点的位置，比较常用的方法有：u 三边定位法u 角度定位法 角 度 定 位 需 要 另 外 测 量 接 收 信 号 夹 角，测 量 出 夹 角 后使 用 数 学 几 何 条 件，确 定 节 点 的 位 置。因 为 测 量 的 信 号夹角不可能很精确，所以AOA 的精度不理想。l 节点定位技术基于测距的定位7 ppt 课件1基本思想三 边 定 位 法 如 图 所 示，

9、已 知A、B、C 三 个 节 点 的 坐 标 分 别 为（x1，y1）、（x2，y2）、（x3，y3）。测 得 它 们 到 未 知 节 点D 的 距 离 分 别 为d1、d2、d3。假 设 节 点D 的 坐 标 为（x，y）。以A、B、C 三 点 为 圆 心，d1、d2、d3为半径做圆，三圆的焦点即为节点D 的坐标。l 基于测距的定位技术三边定位法那么，我们可以列出以下公式：8 ppt 课件将第一个方程和第二个方程同时减去第三个方程，得到结果将其写成线性方程的形式，AX=B，其中l 基于测距的定位技术三边定位法由此可以得出节点D 的坐标为9 ppt 课件l 基于测距的定位技术三边定位法 三 边

10、 定 位 技 术 的 计 算 方 法 比 较 简 单，在 已 知 两 点 之 间 距离 的 情 况 下，采 用 单 纯 的 数 学 公 式 就 可 以 计 算 出 来，节点 之 间 距 离 的 测 量 才 是 三 边 定 位 技 术 的 最 难 点，一 般 来说，有三种算法可以测量两个节点之间的距离：u 根据接收信号的强度来计算距离；u 根据信号传播时间或者时间差来计算距离；u 根据接收信号相位差定位。2 主要技术10 ppt 课件1）根据接收信号强度定位，信号衰减模型如下式：式 中，P(d)、P(d0)分 别 表 示 在 距 离 基 站d、d0处 的信 号 强 度，P(d)是 接 收 节 点

11、 实 际 测 得 的 信 号 强 度RSSI，P(d0)一 般 可 以 距 天 线d0米 处 的 路 径 衰 减 来代替。l 基于测距的定位技术三边定位法11 ppt 课件2）根据信号传播时间测距（TOA）该 技 术 是 采 用 信 号 到 达 时 间 来 测 量 距 离 的，是 一 种 基 于 电 波 传 输 时 间的 定 位 技 术。己 知 信 号 传 播 速 度，通 过 测 量 信 号 从 发 射 机 传 播 到 多 个 接收机所消耗的传播时间来确定移动用户的位置TOA 测 距 的 基 本 思 想 是 测 量 移 动 台 发 射 信 号 的 到 达 时 间，并 且 在 发 射信 号 中

12、要 包 含 发 射 时 间 标 记 以 便 接 收 基 站 确 定 发 射 信 号 所 传 播 的 距 离，该方法要求移动台和基站的时间精确同步 为 了 测 量 移 动 台 的 发 射 信 号 的 到 达 时 间，需 要 在 每 个 基 站 处 设 置 一 个位 置 测 量 单 元，为 了 避 免 定 位 点 的 模 糊 性，该 方 法 至 少 需 要 三 个 位 置 测量单元或基站参与测量l 基于测距的定位技术三边定位法12 ppt 课件如 图 所 示，有A、B、C 三 个 基 站，因 为 节 点 间 的 距 离 测 量 都 是 一 样 的，这 里 我 们 就假 定 先 测 量 基 站A 到

13、 目 的 节 点 的 距 离。假 设 基 站A 到 目 的 节 点D 的 距 离 为d，声 波 传播 速 度 为v，在T1时 刻 基 站A 发 射 机 发 射 一 个 声 波 信 号 给 目 的 节 点D，D 节 点 在T2时 刻接 收 到 该 声 波 信 号，经 过 短 暂 的 处 理 之 后，在T3时 刻 目 的 节 点D 回 送 一 个 声 波 测 距信 号 给A 节 点，在T4时 刻A 节 点 接 收 到 该 信 号。由 此 可 以 得 出 声 波 信 号 在 介 质 中 传 播的时间为：l 基于测距的定位技术三边定位法13 ppt 课件在这段时间内，声波传播的距离为2d，我们就可以得

14、到值 得 注 意 的 是，这 里 的T1和T4时 刻 是 由 节 点A 测 得 的，T2和T3时 刻 是 由 目 的 节 点D 测 得 的，由 于 时 钟 漂 移、定 位 误差 等 的 存 在，两 者 的 时 间 会 有 一 定 的 时 间 差，但 是 由 于无 线 采 用 双 向 通 信 的 方 式，两 者 的 时 间 差 相 互 抵 消，对结果没有太大影响l 基于测距的定位技术三边定位法14 ppt 课件3）根据到达时间差测距（Time Difference Of Arrival，TDOA）在 基 于 到 达 时 间 差TDOA 的 定 位 机 制 中，发 射 节 点 同 时 发 射 两

15、种 不 同 传播 速 度 的 无 线 信 号，接 收 节 点 根 据 两 种 信 号 到 达 的 时 间 差 以 及 已 知 这 两种 信 号 的 传 播 速 度，计 算 两 个 节 点 之 闻 的 距 离，再 通 过 已 有 基 本 的 定 位算法计算出节点的位置。l 基于测距的定位技术三边定位法15 ppt 课件如 图 所 示，发 射 节 点 在 时 刻T0同 时 发 射 无 线 射 频 信 号 和 超 声 波 信 号，接 收 节 点记 录 两 种 信 号 到 达 的 时 间T1和T2，己 知 无 线 射 频 信 号 和 超 声 波 的 传 播 速 度 分 别为c1和c2，那么我们可以知道

16、射频信号和超声波信号传播的时间为：TDOA 有 一 些 固 有 的 缺 陷 需 要 考 虑。首 先 利 用TDOA 进 行 定 位 要 求 传 感 节 点 上 必须 附 加 特 殊 的 硬 件（声 波 或 者 超 声 波 的 收 发 器 等），这 会 增 加 传 感 节 点 的 成 本；其 次，声 波 或 者 超 声 波 在 空 气 中 的 传 输 特 性 和 一 般 的 无 线 电 波 并 不 一 样，空 气的 温 度、湿 度 或 者 风 速 都 会 对 声 波 的 传 输 速 度 产 生 很 大 的 影 响，这 就 使 得 距 离的 估 计 可 能 出 现 较 大 偏 差；最 后，TDOA

17、 测 速 的 一 个 很 大 的 假 设 是 发 送 节 点 和接 收 节 点 之 间 是 没 有 障 碍 物 阻 隔 的，在 有 障 碍 物 的 情 况 下 会 出 现 声 波 的 反 射、折 射 和 衍 射，此 时 得 到 的 实 际 传 输 时 间 将 变 大，在 这 种 传 输 时 间 下 估 算 出 来 的距离也将出现较大的误差。l 基于测距的定位技术三边定位法可以得出 即：16 ppt 课件接收信号相位（PDOA）通过测相位差，求出信号往返的传播时间，计算出往返距离 其 中，fc 是 信 号 频 率，是 信 号 的 波 长，是 发 送 信 号 和 反 射信 号 的 相 位 差。由

18、上 式 可 知d的 范 围 是0,。不 同 的 距 离 如果相差 倍，则测量获得的相位相同。l 基于测距的定位技术三边定位法17 ppt 课件 常用的角度定位方法有：已知两个顶点和夹角的射线确定一点，以及已知三点和三个夹角确定一点。1已知两个顶点和夹角的射线确定一点如图所示，测得参考点A(x1,y2)和B(x2,y2)收到的信号夹角分别是和，根据可 以 计 算 出 待 测 节 点N 的 位 置 坐 标(x,y)。这 是 一 种 参 考 节 点A 和B 自 身 在 坐标 系 已 经 矫 正 的 情 形，如 果 参 考 点A 和B 方 向 没 有 校 正，需 要 在 计 算 时 补 偿方向偏差。l

19、 基于测距的定位技术三角定位法18 ppt 课件如 图 所 示，在 测 量 出 角、角 和 角 后，可 以 使 用 三 角 定 位 的 方 法 计 算 出N 点 的位置(x,y)。对 于 参 考 点A(x1,y1)、B(x2,y2)和 夹 角，根 据 圆 的 内 接 四 边 形 对 角 互 补 和 弦 所 对的 圆 周 角 等 于 它 所 对 的 圆 心 角 的 性 质，得 到 弦AB 所 对 应 的 圆 心 角=2 2。可以 由A、B 和N 确 定 一 个 内 接 圆O 的 圆 心C1（xc1,yc1）和 半 径rc1，同 理 由A、C 和N 三点就可以确定O2(xc2,yc2,rc2)，由

20、B、C 和N 三点就可以确定O3(xc3,yc3,rc3)。根据圆O1、O2、O3，再根据如下方程组，就可以确定点D(xD,yD)的坐标。l 基于测距的定位技术三角定位法19 ppt 课件 在 无 线 传 感 器 网 络 中，基 于 测 距 的 定 位 技 术 往 往 具 有 很 大 的 优 势，算 法 比 较 简 单，实现容易，研究人员一般从几个方面来评判这些定位技术的优略。（1）定 位 精 度，即 测 距 误 差，为 测 得 的 距 离 与 实 际 距 离 的 差 值，一 般 来 说 采 用 超 声波的TDOA 协议最小，而采用功率衰减来判别距离的RSSI 测距误差最大。（2）覆 盖 范

21、围。GPS 是 全 球 定 位 系 统，一 次 覆 盖 范 围 最 好，其 次 是 采 用 功 率 衰 减 的RSSI。而TOA 和TDOA 定位技术采用超声波短波，传播距离最短，因此覆盖范围最小。（3）抗 干 扰 能 力。当 有 干 扰 如 电 磁 干 扰，多 径 干 扰 等 存 在 时，节 点 是 否 能 够 正 常 稳定工作成为测距定位技术性能的一个重要指标。（4）实现成本。l 测距定位技术比较20 ppt 课件1基于连通性的定位 连 通 性（Connectivity）是 指 两 个 节 点 是 否 连 通。基 于 连 通 性 的 定 位可以根据一个节点能否成功解调其他节点传来的数据包作

22、为依据。如 果 节 点i 和 节 点j 连 通，则 表 示 节 点i 能 够 通 过 感 知、通 信 等 途 径，确定 节 点j 在 自 己 周 围 的 一 定 范 围 内，但 不 知 道 具 体 的 距 离 和 方 向。确 切地 说，节 点i 和 节 点j 之 间 的 连 通 性 测 量Qij，可 以 依 据 接 收 信 号 强 度 表 示成0或1的二元变量模型，即：式 中，Pij是 节 点i 收 到 的 从 节 点j 发 出 的 信 号 的 强 度，单 位 是dBm；Pi是数据包刚好能被解调所需的最小接收信号阈值强度。l 无需测距的定位技术基于连通性21 ppt 课件2 基于跳数的定位在无

23、线传感器网络中，节点间最基本的通信方式是洪泛，所以很多节点定位机制都是采用两个节点之间的跳数（Hop）来估计节点之间的距离的。跳数原理就是对信标节点信息洪泛的过程进行跳数统计，通过统计未知节点与信标节点之间的跳数，然后根据信标节点之间的距离和跳数估算出全网每一跳的平均距离，二者相乘，即可得到两个节点之间的距离。l 无需测距的定位技术基于跳数22 ppt 课件质心定位算法的核心思想是：全网约定一段时间t 为定位时间。时间t 为式 中，T 为 发 信 号 的 时 间 间 隔；S为t 时 间 内 要 发 送 的 消 息 个 数；为 小 于1、大于0的常数。在 这 段 时 间t 内，信 标 节 点 每

24、 隔 时 间T 向 邻 居 节 点 广 播 一 个 信 标 信 号，信 号 中 包 含 自 身 的 位 置 信 息。未 知 节 点 记 录 从 每 个 发 来 信 号 的 信 标 节点 接 收 到 的 信 标 信 号 数 量。i 时 间 结 束 后，未 知 节 点 计 算 与 各 个 信 标 节点之间的通信成功率指标CMi，即：l 无需测距的定位技术质心定位算法23 ppt 课件假 设 这 些 坐 标 分 别 为（x1，y1）、（x2，y2）、（xk，yk），则未知节点的坐标（xest，yest）可用质心公式计算为：l 无需测距的定位技术质心定位算法24 ppt 课件APIT 定位算法的理论基

25、础是最佳三角形内点测试法PIT。PIT理 论 为 判 断 某 一 点M 是 否 在 三 角 形ABC 内，假 如 存 在 一 个 方向，沿 着 这 个 方 向M 点 会 同 时 远 离 或 接 近 三 角 形ABC 的 三 个 顶点A、B、C，那 么 点M 位 于 三 角 形ABC 外；否 则，点M 位 于 三角形ABC 内。l 无需测距的定位技术APTI定位算法25 ppt 课件 在 图（a）中,位 置 未 知 节 点M 通 过 与 邻 居 节 点1交 换 信 息，得 知 自身 如 果 运 动 至 节 点1，将 远 离 信 标 节 点B 和C，但 会 接 近 信 标 节 点4，与 邻 居 节

26、 点2、3、4的 通 信 和 判 断 过 程 类 似，最 终 确 定 自 身 位 于三角形ABC 中；而 在 图（b）中，当 节 点4可 知 自 身 运 动 至 邻 居 节 点2处，将 同 时 远离信标节点A、B、C，故判断自身不在ABC 中。l 无需测距的定位技术APTI定位算法26 ppt 课件APIT 定位的具体步骤如下：（1）收 集 信 息：未 知 节 点 收 集 邻 近 信 标 节 点 的 信 息，如 位 置、标 识 号、接 收 到的信号强度等，邻居节点之间交换各自接收到的信标节点的信息。（2）APIT 测试：测试未知节点是否在不同的信标节点组合的三角形内部。（3）计算重叠区域：统计

27、包含未知节点的三角形，计算所有三角形的重叠区域。（4）计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。l 无需测距的定位技术APTI定位算法27 ppt 课件DV-Hop 算 法 的 基 本 思 想 是 将 未 知 节 点 到 信 标 节 点 之 间 的 距 离 用 网 络 中 节点 的 平 均 每 跳 距 离 和 两 节 点 之 间 跳 数 的 乘 积 来 表 示，然 后 再 使 用 三 边 测量法或极大似然估计法来获得未知节点的位置信息。DV-Hop 算法的定位过程分为以下三个阶段：1）计算未知节点与每个信标节点的最小跳数首 先 使 用 典 型 的 距 离 矢 量 交 换 协

28、 议，使 网 络 中 所 有 节 点 获 得 与 信 标 节 点之 间 的 跳 数。在 算 法 开 始 的 时 候，每 个 信 标 节 点 都 发 出 一 个 包 括 自 己 位置 信 息、地 址 和 跳 数 值 为0的 位 置 信 息 包，它 们 周 围 所 有 跳 数 为1的 邻 居都 收 到 这 样 的 信 息，将 信 标 节 点 的 位 置 信 息 和 跳 数 记 录 下 来，并 将 收 到信 息 包 的 跳 数 值 加1，再 向 自 己 的 邻 居 节 点 广 播。这 个 过 程 一 直 持 续 下 去，直 到 网 络 中 每 个 节 点 都 获 得 每 个 信 标 节 点 的 位

29、置 信 息 和 相 应 的 跳 数 值 为止。l 无需测距的定位技术DV-Hop定位算法28 ppt 课件2）计算未知节点与信标节点的平均每跳距离 在 第 二 阶 段，每 个 信 标 节 点 根 据 第 一 阶 段 获 得 的 其 他 信 标 节 点 位 置 和 相隔跳数之后，根据下式计算网络平均每跳距离HopSize。式 中，（xi，xj）、（yi，yj）是 信 标 节 点i 和j 的 坐 标，hji是 信 标 节 点i 和j（ij）之 间 的 跳 段 数。在 实 验 中，我 们 发 现，当 总 跳 数 大 于 一 定 的 值 之后，每个节点所计算的平均每跳距离基本一样。l 无需测距的定位技

30、术DV-Hop定位算法29 ppt 课件3）利用三边测量法计算自身位置 在 未 知 节 点 获 得 与3个 或3个 以 上 信 标 节 点 的 距 离 后，执行三边测量定位。该 算 法 只 需 要 较 少 的 信 标 节 点，计 算 和 通 信 开 销 适中，不 需 要 节 点 具 备 测 距 能 力，是 一 个 可 扩 展 的 算 法，但 是 该 算 法 对 信 标 节 点 的 密 度 要 求 较 高，对 于 各 向 同性 的 密 集 网 络，才 可 以 得 到 合 理 的 平 均 每 跳 距 离，从而能够达到适当的定位精度。l 无需测距的定位技术DV-Hop定位算法30 ppt 课件 将

31、节 点 间 点 到 点 的 通 信 连 接 视 为 节 点位 置 的 几 何 约 束，把 整 个 网 络 模 型 化为 一 个 凸 集，从 而 将 节 点 定 位 问 题 转化 为 凸 约 束 优 化 问 题，然 后 使 用 线 性矩 阵 不 等 式、半 判 定 规 划 或 线 性 规 划方 法 得 到 一 个 全 局 优 化 的 解 决 方 案，确 定 节 点 位 置。同 时 也 给 出 了 一 种 计算 未 知 节 点 有 可 能 存 在 的 矩 形 空 间 的方法。l 无需测距的定位技术凸优化方法第八章 无线传感器网络节点定位技术31 ppt 课件 无 线 传 感 器 网 络 自 身 定

32、 位 算 法 的 性 能 对 其 可 用 性 有 直 接 的 影 响，如 何 评价 定 位 算 法 是 一 个 需 要 研 究 的 问 题。可 从 是 否 需 要 信 标 节 点、信 标 节 点 布置 方 式、计 算 模 式、定 位 原 理 和 节 点 外 加 设 备 等 角 度 对 上 述 无 须 测 距 节 点定位技术进行了分析和比较，如下表所示。l 无需测距的定位技术分析比较32 ppt 课件刚性体理论概述刚性，即在不考虑物质特性的理想条件下任何两个连接点之间的欧氏距离不随其运动状态改变的特性。普通刚性理论是一种定义在光滑轨道上的运动特性。当图沿着光滑轨道运 动 时，任 意 两 个 节

33、点qi(t)和qj(t)间 的 欧 氏 距 离 不 随 时 间 函 数 变 化，则qi(t)和qj(t)具 有 普 通 刚 性 特 性。用 数 学 描 述，即 当 几 何 图 沿 着 轨 道q(0,)做 刚 性 运 动 时，则 任 意 时 刻 的 节 点 集qi(t)和qj(t)是 全 等 的。可 用 数学公式表示为式中，R(q)是一个mn型的矩阵，称为刚体矩阵。l 协作定位技术33 ppt 课件定 理 1：在 二 维 的 平 面 空 间 中，图 形G=(v,L)拥 有n个 顶 点，如 果L（L 为 图 形 的 边集）存 在 一 个 有2n3条 边 的 子 集E，且 对 任 意 一 个 非 空

34、 边 集E 中 有n 个 顶 点 且E中元素数量不超过2n3，那么图形G=(V,L)在二维平面空间中具有普通刚性。定 理 2：在 一 个 二 维 平 面 空 间 中 图G 内 包 含n4个 定 点，如 果 图G 中 某 个 点 具 有3-连 接（3-Connected）结 构 且 该 图 形 是 冗 余 刚 性 的，那 么 图G 就 是 全 局 刚 性 结构。l 协作定位技术34 ppt 课件协作体的定义 将 刚 性 理 论 引 入 网 络 结 构 拓 扑 中 是 无 线 传 感 器 网 络 中 基 于 协 作 模 式 节 点定位的第一步，用图形结构的方式描述网络拓扑结构。定 义 1：在 网

35、络 图 形GN=(V,EN)中，存 在 节 点u和v G(V)，R(u,v)或R(v,u)表 示 节 点u和v 之 间 的 几 何 距 离，设r 是 网 络 中 节 点 的 最 大 无 限 传 输 距 离，当R(u,v)r 时，u和v 之 间 可 以 无 线 连 通，则 称u和v 为 直 接 相 邻 节 点 或 邻 居节点。定 理 322：在 二 维 空 间 的 无 线 传 感 器 网 络N 中 的 节 点 以 随 机 的 形 式 分 布，当 网 络 中 存 在m3个 非 共 线 导 标 节 点，且 网 络N 所 对 应 的 结 构GN=(V,EN)是全局刚性，则网络N 中的节点可以被定位。l

36、 协作定位技术35 ppt 课件定 义 2：无 线 传 感 器 网 络 中 的 一 组 连 通 的 节 点C 组 成 的 局 部 网 络 拓 扑N，若N中 所 对 应 节 点 之 间 的 连 接 特 性 及 导 标 节 点 的 物 理 位 置 的 约 束 可 以 唯 一 确 定N中位置节点的位置信息，那么，称局部网络拓扑N 为定位协作体定义3：（单元定位协作体）对某一定为协作体，若不存在定位协作体 满 足，则 称 定 位 协 作 体Lu为 单 元 定 位 协 作 体。包 含n（n=1,2,3）个 两 两 相连 的 未 知 节 点 及m（m=3）个 导 标 节 点，且 不 含 任 何 冗 余 边

37、 的LCS 成 为 最 简 单的定位协作体或最简定位协作体，如图8.12所示。l 协作定位技术36 ppt 课件定 理 4：设L1和L2为 两 个 定 位 协 作 体，它 们 所 对 应 的 节 点 集 分 别 为V1和V2，且 两个 集 合 没 有 共 同 元 素，若 存 在 一 个 导 标 节 点v1bL1及v2bL3且v1b与L2中 未 知 节点 的 连 接 度 为1，去 掉 导 标 节 点v1b和v2b，并 合 并v1b和v2b与 未 知 节 点 的 连 接 形 成新 的 连 接lb，使L1和L2合 并 构 建 成 新 网 络 拓 扑 结 构L，则L 为 定 位 协 作 体，如 图 所示。定 理 5：设 一 个 定 位 协 作 体L，将L 中 的 所 有 节 点 看 做 导 标 节 点，若m 个 不 属 于L的 位 置 节 点 组 成 的 集 合Su与L 中 的 部 分 或 全 部 节 点 元 素 构 成 的 网 络 拓 扑 可 以 形 成新的定位协作体，则位置节点集SuL 所形成的拓扑结构为定位协作体。l 协作定位技术37 ppt 课件