（应用数学专业论文）基于计算几何图的拓扑控制算法.pdf

摘要 无线传感器网络是近年来得到迅速发展和高度重视的新型网络技术 网络中 的节点为体积微小的嵌入式设备 采用能量有限的电池供电 由于环境等因素的 影响 更换电池基本上不可能 所以 节能是无线传感器网络面临的首要任务 减少节点能量消耗是拓扑控制算法的首要设计目标 因此拓扑控制算法成为无线 传感器网络研究中的核心问题之一 并且良好的拓扑结构可以提高m a c 协议和路 由协议的效率 延长网络生存时间 减少通信干扰 考虑到传感器节点的能量消耗主要集中在无线通信模块 且能量消耗与通信 距离的刀次方成正比 2 l 4 本文提出了一种平面拓扑控制算法 由于计算几何 中的d e l a u n a y 图具有良好的性质 所以在无线传感器节点问建立一张d e l a u n a y 图 根据能量消耗与通信距离的关系来简化该图 保留最小能耗路 并与网络模型中 的m g 模型结合 从而得到m e d e l 算法 该算法具有对称性和平均度有界等优点 分簇算法的效率高于平面拓扑控制算法 本文针对l e a c h 算法的不足 提出 了一种分簇算法一e c r 算法 该算法以改善簇的均匀性和簇内结构为出发点 在 基于剩余能量的前提下进行分簇 从而延长了网络生命期 均衡了簇首的分布 并且改善了簇内的结构 关键词 无线传感器网络拓扑控制算法m e d e l 算法e c r 算法 a bs t r a c t i i lr e c e n ty e a r s w i r e l e s ss e n s o rn e 铆o r k s an e wn e t o r kt e c h n o l o g y h a sb e e n d e v e l o p e dr 印i d l y 觚dp a i d 伊e a ta t t e n t i o nt o t h es e n s o rn o d ei nw i r e l e s s s e n s o r n e t w o r k si sm es i z eo fs m a ue i l l b e d d e dd e v i c e u s i n gt h el i m i t e db a t t e 妒p o w e r e d e n e r g y i ti si m p o s s i b l et or 印l a c em eb a t t e r yb e c a u s eo fm ee n v i r o m e n t s oe n e r g y s a v i n gb e c o m e st h ep r i m a r t a s ko ft h ew i r e l e s ss e n s o rn e t l o r k s r e d u c i n gn o d ee n e r g y c o n s u m p t i o ni sm em a i nd e s i 印p u 印o s eo ft h et o p 0 1 0 9 yc o n t r o la l g o r i t h m h e n c e t h e r e s e a r c ho ft o p o l o g yc o n t r o la l g o r i t h m sb e c o m e so n eo ft h ec e n t r a lp r o b l 哪si nt h e s t u d yo fw i r e l e s ss e n s o rn e t w o r k s aw e l lt o p o l o g ys t r u c t l l r ec a ni m p r o v et h ee 衔c i e l l c y o fm a c p r o t o c 0 1a i l dr o u t e rp r o t o c 0 1 p r o l o n gt h e1 i f e t i m eo ft h en c t w o r k a i l dr e d u c e t h ei n t e f e r e n c eo fc o m m u n i c a t i o n c o n s i d e r i n gt h a t t h ee n e r g yc o n s u m p t i o no ft h es e n s o rn o d ei sm a i n l yi n c o m m u n i c a t i o nm o d u l ea i l de i l e 唱yc o n s u m p t i o ni sp r o p o r t i o nt ot h en mp o w e ro ft h e c o m m u n i c a t i o nd i s t a n c e t h i sp a p e rp r e s e n t sap l a i nt o p o l o g yc o n t r o la l g o r i t h m d u et o t h eg o o dp r o p e r t i e so ft h ed e l a u n a y 黟a p hi nc o m p u t a t i o n a lg e o m e t r y w ec o n s t m c ta d e l a u n a y 黟a p h 锄o n gt h es e n s o rn o d e sa 1 1 ds i m p l i 黟t h e 蓼a p ha c c o r d i n gt o m e r e l a t i o n s h i po ft h ee n e r g yc o n s u m p t i o na i l dc o m m u n i c a t i o nd i s t a n c e b yp r e s e r v i n gt h e o p t i m a le n e r g yc o n s u n l p t i o np a ma i l dc o m b i n i n gw i t ht h em gm o d e l w eo b t a i nt h e m e d e la l g o r i t h m t h i sa l g o n t h mh a st h ea d v a n t a g e so fs y m m e t r ya n db o u n d e da v e r a g e n o d ed e 目 e e c 1 u s t 硎n ga l g o r i t h mi sm o r ee 位c i e n tm a nt h ef l a tt o p o l o g yc o n t r o la 1 9 0 r i t t l i l l 1 1 1 v i e wo ft h ed e 6 c i 蜘c yo fl e a c hc l u s t 舐n ga l g o r i t h m w ep r o p o s eac l u s t e n n g a l g o r i t h m e c ra l g o r i t h m t h ea l g o r i t h ma i m s a ti m p r o v i n gt h ed i s t r i b u t i o no ft h e c l u s t e rh e a d sa n dt h es t n l c t u r co fm ec l u s t b a s e do nt h er e s i d u a le n e r g y 1 1 1 u sm e a l g o r i t h mc a np r o l o n gm e l i f e t i m eo fn e 俩o r k b a l a n c et h ed i s t 曲u t i o no ft h eh e a d sa i l d i m p r o v em es t m c t l l r eo ft h em e l l l b e r so f t h ec l u s t 既 k e y w o r d w i r e l e s ss e n s o rn e 铆o r k st o p o l o 影c o n t r o la l g o r i t h l n m e d e l a l g o r i t h m e c r a l g o r i t h m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果 尽我所知 除了文中特别加以标注和致谢中所罗列的内容以外 论文中不 包含其他人已经发表或撰写过的研究成果 也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意 申请学位论文与资料若有不实之处 本人承担一切相关责任 本人签名 峭日期掣叫 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定 即 研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学 本人保证毕 业离校后 发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学 学校有权保留送交论文的复印件 允许查阅和借阅论文 学校可以公布论文的全 部或部分内容 可以允许采用影印 缩印或其它复制手段保存论文 保密的论文 在解密后遵守此规定 本人签名 导师签名 第一章绪论 第一章绪论 本章首先介绍了无线传感器网络产生的历史背景及其结构 其次介绍了拓扑 控制算法的分类 意义以及目前的研究现状 最后列出了本文的内容安排 1 1 引言 无线传感器网络 w i r e l e s ss e n s o rn e m o r k s w s n 技术起源于美国 根源可追溯 到1 9 7 8 年由美国国防部高级研究计划署 d a r p a 在卡内基 梅隆大学发起的分布 式传感器研讨会 后来 该技术被一些重要机构预测为将改变世界的重要新技术 以及高科技产业 并被美国 技术评论 列为十大新兴技术之首 近年来 国内 一些研究机构也开始了无线传感器网络技术及其应用的研究 其中包括中国科学 技术大学 清华大学 中科院计算所等机构 无线传感器网络技术是当前在国际上备受关注的 涉及多学科的 知识高度 集成的前沿研究领域 它综合了嵌入式计算技术 现代网络及无线通信技术 分 布式信息处理技术等 无线传感器网络有着广阔的应用前景 2 在国家安全 环境 监测 工农业控制 生物医疗 交通管理 空间探索等领域具有重要的应用价值 其发展和应用 将会给人类的生产和生活带来深远的影响 因而引起了军界 工 业界和学术界的高度关注 1 2 无线传感器网络简介 无线传感器网络由部署在监测区域内的传感器节点组成 节点间通过自组织 的无线通信方式形成一个网络系统 其目的是协作地感知 采集和处理网络覆盖 区域中感知对象的信息 并发送给观察者 其中传感器 感知对象 观察者构成 了无线传感器网络的三要素 1 2 1 传感器节点结构 传感器节点一般由控制器 存储器 传感器和执行器 通信 电源五个主要 部分组成 如图1 1 所示 控制器处理相关数据 并执行任意代码 存储器用来存 储数据和中间代码 传感器和执行器是与外围设备的接口 无线传感器网络的节 点控制靠执行器 通信设备是为了将节点接入网络 电源为传感器节点提供运行 2 基于计算几何图的拓扑控制算法 所需的能量 电源 图1 1 传感器节点主要硬件组成 对于传感器节点而言 电源是系统的关键部分 设计电源时主要从以下两个 方面考虑 一方面 按照要求的方式储能和供电 另一方面 尽量随时从节点外 部的能源获取能量 以补充消耗的能量 1 2 2 传感器网络结构 无线传感器网络的体系结构是建立在大量研究成果的基础上的 科研人员已 经做了许多与自组织移动a dh o c 网络相关的工作 4 2 因此 无线传感器网络与普 通网络既有相似又有不同之处 传感器网络系统通常包括传感器节点 s e n s o rn o d e 汇聚节点 s i l l l n o d e 和管 理节点 如图1 2 所示 传感器节点随机部署在监测区域 s e n s o rf i e l d 内部或附近 通过自组织无线通信方式构成网络 节点采集数据并经过多跳后路由到汇聚节点 即通过各节点间的协作而完成特定的任务 最后通过互联网或卫星达到管理节点 用户可通过管理节点对传感器网络进行配置 管理以及下达任务 点 用户 图1 2 传感器网络体系结构 无线传感器网络及其网络体系结构有多种类型 在大多数的应用中 多跳通 信是关键技术 多跳网络很适合无线传感器网络 因为传感器节点自身可担当中 继节点 而不需要其它器件的介入 多跳技术可以有效地克服通信距离长或障碍 第一章绪论 3 物阻挡所造成的通信困难 传感器网络协议栈包括物理层 数据链路层 网络层 传输层和应用层 如 图1 3 所示 另外 协议栈还包括能量管理平台 移动管理平台和任务管理平台 这些管理平台的主要功能是使传感器节点能够按照能源高效的方式协同工作 在 节点可移动的传感器网络中转发数据等 各层协议的功能和研究状况为 物理层提供信号调制和无线收发技术 主要关心的是数字化数据的调制与解 调问题 目前 物理层协议的研究主要为传输介质 频段的选择 无线电收发器 的设计等 核心问题是能量的高效性 数据链路层负责数据成帧 帧检测和差错控制等 对相邻节点之间的通信进 行管理 形成可靠的高效率的数据传输 数据链路层的研究主要是媒体接入控制 协议 m a c 协议 的研究 无线传感器网络m a c 协议的主要目的是为能量有限的 大量传感器节点建立具有自组织能力的通信链路 实现资源共享 处理数据包间 碰撞 网络层主要负责路由查找和数据包传送 网络层路由协议的研究可分为5 类 基于地理位置的路由协议 基于聚簇的路由协议 能量感知路由协议 以数据为 中心的路由协议和容错路由协议 传输层负责数据流的控制与传输 在保证数据传输的可靠性上起到了重要作 用 从而提高服务质量 当无线传感器网络与i n t e m e t 或其它网络相连接时 传输 层协议起到了主导作用 4 7 然而 由于传感器网络自身的特点使得其传输控制很 困难 这就需要使用特殊的技术和方法实现互联 传输协议的主要任务为流量控 制 拥塞控制 网络提取和可靠数据传输 应用层包括一系列基于检测任务的应用软件 管理平台的主要功能表现在以下三个方面 能量管理平台管理传感器节点如何优化使用能源 即在各个协议层上考虑降 低能耗 移动管理平台检测并记录传感器节点的移动 使得传感器节点能够动态跟踪 其邻居节点的位置 任务管理平台在一个特定的区域内平衡和调度检测任务 4 基于计算几何图的拓扑控制算法 图1 3 无线传感器网络协议栈结构 1 2 3 传感器网络的特点及其面临的挑战 传感器网络具有如下特点 1 大规模网络 为了获取准确和较多的信息 在监测范围内通常部署大量的传感器节点 其 数量可能达到成千上万 甚至更多 传感器网络的大规模性一方面是指传感器节 点分布在很大的区域内 另一方面指传感器节点部署很密集 即在一个面积不是 很大的空间内 密集部署了大量的传感器节点 2 自组织网络 传感器网络由大量传感器节点组成 传感器的节点不用经过工程处理 或预 先定位 可以随机放置在不可达的地形或灾难区域 这就意味着传感器网络的协 议和算法应该具有自组织特性 自组织特性使得传感器节点间可以互相协作 为 完成任务而自发组织起来 进行通信和信息处理 3 动态性网络 环境因素和电能耗尽等影响都会造成节点出现故障或失效 这就需要传感器 感知对象和观察者这三要素都可能具有动态性 为了适应传感器网络系统的这种 变化 要求传感器网络具有动态的系统可重构性 4 可靠性网络 网络的可靠性是指数据向目的地传送的可靠度 传送方式又分定向传送和广 播式发送 可靠性与传送的质量 速率有关 传感器网络有不同的应用和目的 所以对于不同的传感器网络而言 其可靠性要求也不一样 但较高的可靠性必定 会提高数据准确率的 5 应用性相关的网络 传感器网络用来获取监测目标的信息 不同的传感器网络应用关心不同的监 第一章绪论 5 测目标 不同的应用背景对传感器网络的要求也不同 无论硬件平台 软件系统 或者网络协议都会有很大差别 针对不同的应用来研究无线传感器网络技术 这 是传感器网络设计不同于普通网络的一个特征 6 以数据为中心的网络 传感器网络是一个任务型的无线网络 脱离网络讨论节点没有任何意义 传 感器网络中的节点采用编号标识 编号是否需要全网唯一则取决于通信协议的设 计 由于传感器节点随机部署 所以构成的传感器与节点编号之间的关系是完全 动态的 即节点编号与节点位置没有必然联系 用户查询事件时 直接将所关心 的事件通告给网络 而并不是通告给某个具体编号的节点 网络在获得指定事件 的信息后再反馈给用户 这种以数据作为查询或者传输线索的思想更接近于自然 语言交流的习惯 所以通常说传感器网络是一个以数据为中心的网络 无线传感器网络与无线网络的区别主要表现为 传感器网络集成了监测 控 制以及无线通信的网络系统 节点数目多 分布密集 并且因环境和能量的耗尽 容易出现故障 不同于传统无线网络的高服务质量和高效的带宽的利用 节能是 无线传感器网络设计的首要目标 节点的限制包括电池能量有限 通信能力有限以及计算和存储能力有限 在 实际应用中 由于环境恶劣或者传感器节点放置在人类难以触及的区域时 能量 的有限性显得更为突出 因此降低能量消耗 延长节点以及网络的寿命成为最关 键的问题 无线传感器网络的能耗主要集中在无线通信模块 无线通信的能量消 耗与通信距离的关系为e 材 2 z 4 其中e 是能耗 后是系统常量 d 是通信距离 z 的取值与很多因素有关 例如传感器节点部署贴近地面时 障碍物多干扰大 z 取值就大 反之则 z 取值就相对小 考虑诸多因素 通常取刀 3 此时随着通信 距离的增加 能耗将急剧增加 一般而言 传感器节点的通信半径在1 0 0 m 以内比 较合适 利用某个传感器网络实现所有应用几乎是不可能的 但可利用一些共性 特 别是关于系统的特性和必要的机制等 利用新机制实现不同的应用是当前传感器 网络面临的主要挑战 各种应用实例的共有特性有 服务类型 服务质量 容错性 寿命 可观测 性 较宽的密度变化范围 可编程性 可维护性等 为了满足以上要求 建立通信网络的新机制 新结构和新协议是必须的 因 此 这样一种机制是符合要求的 一方面 它能够针对某个具体应用的具体特性 支持相应的服务性能 维护要求和工作寿命等 另一方面 这些机制应该能够扩 展以适应其它应用 主要机制包括 多跳无线通信 节能操作 自动配置 协作 和网内处理 以数据为中心 局部性等 6 基于计算几何图的拓扑控制算法 1 2 4 传感器节点的节能 传感器节点对能量的需求很大 但电池容量有限 而且通过能量获取为其充 电又是复杂不稳定或者不可行的 因此 必须严格控制传感器节点的能量消耗 可以从下面几个方面考虑节能 微控制器的节能 如采取动态电压调整策略 存储器节能 如选择闪存代替 片外r a m 节点上闪存的读取和写入操作的能耗也不同 如读取数据消耗1 1 1 n a h 写入数据消耗8 3 3 3 n a h 无线收发机的能量控制 根据发射和接收过程的能耗模 型决定 计算与通信的选择 一般情况下 通信能耗大于计算能耗 但有关计算 的能耗不能简单省略 基于该结论 提出了许多有关无线传感器网络组网结构的 方法和设计策略 核心思想是在保证可靠通信的前提下 致力于网内计算的研究 即网内处理和聚合 传感器与执行器的功率消耗 由于器件的多样性 这部分的 能量消耗基本上不能建立准则 1 3 无线传感器网络拓扑控制 无线传感器网络的一个典型特征是在一个很小的区域里部署大量节点 例如 使网络覆盖率足够高或利用节点冗余防止节点失效 尽管这些都是密集型网络部 署的优点 但其也有缺点 如在拥挤的网络中 邻节点数目众多 许多节点互相 干扰 路由方式多 节点可能使用较大的发射功率与较远的节点直接通信 其中 的某些问题可以通过拓扑控制技术来解决 由于传感器节点具有体积小 能量有限 处理能力低等特点 因此充分利用 有限的能量提高网络生命期是传感器网络面临的首要任务 而网络拓扑作为路由 层协议和m a c 层协议的重要平台 因此对其进行控制是实现这一目标的主要技术 手段和支撑基础 通过以上所述知 拓扑控制对于传感器网络是至关重要的 拓扑控制的思想是根据一定的规则限制给定节点的邻节点数目 通过拓扑控 制可以有效降低发射功率 减少干扰 从而可以降低节点能量消耗 充分利用有 限的能量 这对于无线传感器网络是至关重要的 良好的拓扑结构还可以提高路 由协议和m a c 协议的效率 从而实现w s n 首要设计目标 拓扑结构的控制还与 网络整体性能的优化存在着密切的联系 为时间同步 数据融合及目标定位技术 提供支撑基础 综上所述 研究拓扑控制对w s n 具有重要意义 其目标概括为 保障节点间的可达性 降低节点的能量消耗 提高网络吞吐量 减小信道干扰等 拓扑控制的方法主要为两种 一种是减少活动节点的数量 例如可以周期性 地关闭剩余能量少的节点 激活其它节点来代替被关闭的节点 另一种为控制活 第一章绪论 7 动链路集 邻节点集 如不需使用网络中的所有链路 则可以根据某种规则剔除一 些链路 把通信限制在重要链路中 1 4 拓扑控制算法分类及研究现状 根据网络拓扑结构可将w s n 拓扑控制算法划分为功率控制算法 平面算法 和分簇算法 7 1 有人将功率控制简化为发射范围分配问题f l0 1 简称r a r a n g e a s s i 盟m e n t 问题 在功率控制算法 3 0 中 各节点地位相同 通过功率控制简化网络拓扑结构 从而减少冲突和干扰 达到节能的目的 典型的功率控制算法有c o m p o w 5 1 l m a 和l m n 6 1 c b t c 算法 1 2 x t c 算法 1 3 和邻近图算法等 经典的邻近图算法有 d r n g d l m s t 9 1 g g 1 1 1 y g f l 2 等 c o m p o w c o m m o np o w 神算法基本思想是所有节点采用相同的传输功率 且 该功率是能确保整个网络连通的最小功率 功率的统一性确保了双向连通性 而 功率的最小化则在降低传输能耗的同时提高了网络的吞吐能力 因此c o m p o w 算 法具有延长网络生命期 提高网络容量 降低冲突等多种优势 然而 它需要保 留所有潜在邻节点的路由表 这一点使得它基本上不适合无线传感器网络 l m a 和l m n 算法根据节点度值的上下限 动态调整发射功率使得节点度数落 于上限和下限之间 节点度的上下限选取需保证拓扑具有一定程度的可扩展性和 冗余性 该算法一般难以保证网络的连通性 c b t c 算法是基于方向的功率控制算法 该算法可以保证网络的连通性 节点 选择最小发射功率只 使得在以 为中心的角度为缈的锥形区域内至少有一个节 点存在 作者证明了当妒s5 么时 网络是连通的 为了得到可靠的方向信息 节 点需要配置多个有向天线 x t c 算法用接收信号的强度作为距离的度量 节点根据反映链路的全序对其 邻居排序 排在越前面的节点与当前节点问的链路质量越好 各节点广播自己的 全序集 节点按顺序遍历自己的全序集 优先考虑好邻居 并建立链路 d i 必g 算法和d l m s t 算法是两个基于邻近图的具有代表性的算法 基于邻 近图的功率控制算法的基本思想是 假设所有的节点使用最大发射功率发射时形 成的拓扑图是g 根据邻近图判别条件求出该图的邻近图g 每个节点以自己所 邻接的最远节点来确定发射功率 d r n g 和d l m s t 算法可确保网络的连通性 在功率控制研究中 一般认为网络中的所有节点都具有相同的最大发射功率 然而事实上 即使网络中所有的传感器节点使用相同的发射功率 由于天线质量 地形 环境等多方面的差异 各个节点所形成的发射范围也是各不相同的 且研 8 基丁计算几何图的拓扑控制算法 究人员已经发现这种差别很大 8 1 分簇算法是无线传感器网络节省能量 延长网络生命期的有效方法 所谓簇 是指网络中的一些节点被认为具有特殊的功能 例如 控制其邻节点 融合接收 到的数据 压缩通信量等 在这种情况下 就形成了节点簇 其中 控制者 通 常被称作簇头 其它节点则成为簇成员 节点分簇的主要思想是根据某种规则选 择出一些节点成为簇首 在剩余节点中继续按某种规则选择节点加入簇首 形成 簇 典型的分簇算法有l e a c h 算法 1 1 g a f 算法f 1 4 t o p d i s c 算法 1 5 1 h e e d 算 法 3 等 l e a c h 算法中所有节点轮流充当簇首 网络周期性的进行簇首选举 每个周 期称为一轮 r o u n d 在每轮中 各节点独立运行公式产生一个数 再对每个节点 生成一个随机数 通过两个数的比较来判断节点是否当选簇首 在每轮中 所有 簇首选举后 则进入稳定工作阶段 g a f 算法是基于地理位置的拓扑算法 所以每个节点都知道自己的位置 该 算法把区域分成非常小的矩形 使每个矩形中的节点都能与相邻矩形中的节点直 接通信 并将节点集划分成等价的子集进行休眠模式的确定 t o p d i s c 算法是基于图论中的最小支配集而提出的 最小连通支配集可以很好 的描述分簇方法 在密集型网络中 该算法可以快速的形成分簇结构 并在簇头 间建立树形结构 该算法属于层次型拓扑控制 但其仅考虑在保证网络覆盖度的 前提下 使整个网络所形成的簇的个数尽量少 而没有考虑到节点的剩余能量和 网络的鲁棒性等问题 h e e d 算法根据两个因素周期性迭代进行分簇 第一个因素为剩余能量 其次 为簇内通信代价 某个节点被选为簇头时的簇内通信代价用最小平均可达功率 a m r p 度量 a m i 强是指一个簇内所有其他节点与簇头通信所需的最小功率的平 均值 该算法首先根据节点的剩余能量算出其成为临时簇首的概率 然后根据簇 内通信代价进一步确定簇首 h e e d 综合地考虑了生存时间 可扩展性和负载均 衡 对节点的分布等没有特殊的要求 尽管h e e d 的执行不依赖于同步 但是不 同步却会严重影响分簇的质量 1 5 本文主要研究内容 本文的核心部分是第三 四章 分别从无线传感器网络的功率控制和分簇两 个方向研究了拓扑控制算法 在第二章中 我们介绍了计算几何中的部分知识 这为研究第三章和第四章 的算法奠定了基础 第一章绪论 9 在第三章中 我们根据计算几何中的知识研究了功率控制算法中的邻近图算 法 提出了基于d e l a u n a y 图的拓扑控制算法并进行了仿真 由理论分析和仿真结 果得出该算法降低了网络能量消耗 延长了网络生命期和降低了通信干扰 该算 法求出的拓扑控制图包含最小能耗路 并且具有节点平均度有界 强连通等良好 的性质 在第四章中 我们考虑到分簇控制可以更有效的延长网络生命期 所以研究 了分簇算法 通过对l e a c h 算法的研究 提出了基于最大剩余能量和最小邻近簇 半径的分簇算法 该算法将剩余能量和相邻簇半径作为当选簇首的依据 以v o r o n o i 单元为簇的划分 并针对文献中给出的能量模型进一步改进 通过仿真实验和 l e a c h 算法进行对比 该算法有效提高了网络生命期 平均消耗了网络节点的能 量 最后对全文进行了总结 第二章计算几何知识 第二章计算几何知识 本章主要介绍了计算几何中关于v o r o n o i 图 d e l a u n a y 图的基本概念及性质 这为本文中的部分算法奠定了基础 2 1 1v b r o n o i 图 2 1 相关知识 1 基本概念 v o r o n o i 图有时也被称为t h i e s s e n 多边形 d i r i c h r i t 网格或w i 鲈e r s e i t z 区域 等 v o r o n o i 图的基本定义和算法可见于许多计算几何教科书 2 1 2 2 1 本文采用文献 1 6 中的定义 如下 任意两点p 和g 之间的欧氏距离 记作沈订 g 对于二维平面有 挑f p g 段一吼 2 b g y 2 2 1 设p a p 为平面上任意胛个互异的点 这些点通常称为基点 所谓尸对应 的v o r o n o i 图 就是平面的一个子区域划分 整个平面因此被划分为聆个单元 它们 具有如下性质 任一点g 位于点只所对应的单元中 当且仅当对于任何的 p p f 都有 挑f 够p 挑f g p 2 2 将与尸对应的v o r o n o i 图记作砌 p 与a f l 刀 对应的区域称为v o r o n o i 单元 由上面的定义可知 a 待l 刀 对应的v o r o n o i 单元由节点只 扛l 刀 和各 个相邻节点的垂直平分线组成 故v o r o n o i 单元必为凸多边形 1 8 2 基本性质 下面给出了v o r o n o i 图的相关性质 定理2 1 16 给定平面上任意刀个点构成的集合p 若所有的点都共线 则 场 p 由珂 l 条平行直线构成 否则 砌 p 将是连通的 即边和顶点构成了连通 1 2 基于计算几何图的拓扑控制算法 集 且其中的边不是线段就是半直线 证明 若 1 个点共线 则这刀个点之间存在 l l 条线段 取刀 1 条线段的垂直 平分线 则将平面分成 1 个区域 由定义知 场厂 p 由这刀 1 条平行的垂直平分 线构成 若刀个点不共线时 首先证明场r p 中的边都是线段或者半直线 因为场 p 中的边是位于每一对基点之间的某条平分线的一部分 假设场 p 存在一条完整 的直线p 设其来自于v 0 r o n o i 单元v 易 和v p 的共同边界 任取不与p 和p 共 线的见 p 则p p 的平分线p 不可能与p 平行 则必与p 相交 然而e 落在8 所分割的仇所在的半平面部分 不可能为1 p 的边界 因为这一段上的任何点到 p 的距离都比到p i 的距离小 所以假设不成立 下证 p 连通 假设场 p 不连通 则存在某个v o r o n o i 单元1 b 将整个 平面分成两个互不相交部分 因为v 0 r o n o i 单元都是凸集 所以 融 边界只可能 是两条完整平行直线 则与上述所证矛盾 证毕 定理2 2 1 6 若对于任一点集尸所对应的v o r o n o i 图场r p 则下列命题成立 1 点g 是场 p 的一个顶点 当且仅当在其最大空圆c g 的边界上 至少有三 个基点 2 p 和p 间的平分线确定了场 p 的一条边 当且仅当在这条线上存在一个点 g c g 的边界经过p 和p 但不经过其它基点 证明 1 假设存在某个点g c g 的边界至少经过3 个基点 设p f p 和 风为其中的三个基点 因为c g 内部是空的 所以g 同时落在 只 1 p 和 v n 的边界上 因此g 肯定是肠 p 的一个顶点 反之 砌 p 中的每个顶点都与至少三条边相关联 因此也至少与三个 v o r o n o i 单元相关联 不妨设这三个单元分别为1 奶 1 p 和1 见 顶点g 到 v 乃 v p 和v 见 的距离分别相等 且到其它各基点的距离都不可能更近 否 则v b 1 p 和v 既 就不可能相交于g 于是 边界由p f p 和n 确定的这 个圆 内部不可能包含任何基点 2 假设存在某个点g 具有定理所述的性质 既然c g 的内部不包含任何基 点 而且p 和p 落在其边界上 故对任何的1 尼 靠 都应有 如f g b 如f g p 如f g 既 于是g 必然落在场 p 的某条边或者某个顶 点上 由 1 知 g 不可能是场 p 的一个顶点 因此 g 只能落在场厂 p 的某条 边上 且这条边是p 和p 之间的平分线上的一段 反之 假设p 和p 之间的平分线确定了一条v o r o n o i 边 来自这条边内部的 任何一个点g 其对应的最大空圆边界必然经过p 和p 但不经过其它基点 3 应用 在w s n 中 v o r o n o i 图常被用于网络覆盖的研究 2 5 1 网络覆盖可以看成是对 第二章计算几何知识 1 3 传感器网络服务质量的一个度量 在覆盖问题中 最关键的因素是网络对物理世 界的感知能力f 2 0 v o r o n o i 图在几十年前就开始被用来分析物质的微观结构 2 4 1 在 分析物质的微观结构时 用来生成v o r o n o i 图的站点通常是原子 离子或分子 它 们的位置通常通过计算或测量得到 在机器人运动规划中 机器人运动规划问题 就是已知平面上或空间中的若干障碍物 给出机器人从一个位置到另一个位置的 安全或最优路径 如果障碍物可以近似成质点 那么机器人沿着障碍物的v 0 r o n o i 图的边行走是最安全的 1 6 另外 在计算机图形学 图像处理与模式识别等领域 中 v 0 r o n o i 图都有着广泛的应用 2 3 1 2 1 2d e l a u n a y 三角剖分 1 基本概念 1 6 1 d e l a u n a y 三角剖分是v o r o n o i 图的对偶图 连接v o r o n o i 图中有公共边的相邻的 两个基点即得到d e l a u n a y 三角剖分 图2 1 是v o r o n o i 图与其对应的d e l a u n a y 三角剖 分 v 0 r o n o i 边 一d e l a u n a y 边 图2 1v o r o n o i 图和d e l a u n a y 图 2 基本性质 1 最大化最小角原则 17 设尸为任一平面点集 则在p 的所有三角剖分中 d e l a u n a y 三角剖分使最小角达到最大 该性质由l a w s o n 于1 9 7 2 年提出 并对最 大最小角原则作了简明的解释 2 个相邻三角形构成的凸四边形的对角线在相互交 换后 6 个内角的最小角不再增大 如图2 2 所示 将对角线肋换为彳c 则易 见最小角变大 即任一三角剖分在变成d e l 姗a y 三角剖分时 最小角变大 a 非d e l a 吼a y 三角剖分 图2 2 三角剖分 b d e l a u l l a y 三角剖分 1 4 基于计算几何图的拓扑控制算法 2 空圆特性 设尸为平面上的任一点集 而 为尸的任一三角剖分 则 是 尸的d e l a u n a y 三角剖分 当且仅当在 中每个三角形的外接圆的内部 都不包含 尸中的任何点 对于四个点构成的点集 根据空圆性质 剖分是否为d e l a u n a y 三角剖分 如图2 3 a 一一 我们可以很容易确定点集尸的三角 2 3 b 所示 一一 a 三角剖分 b d e l a l l i l a y 三角剖分 图2 3 三角剖分与d e l a u n a y 三角剖分 定理2 3 设p 为平面上 1 个点组成的一个集合 则由其得出的欧几里得最小 支撑树 e u c l i d e a nm i n i m 啪s p a n n i n gt r e e e m s t 是其d e l a u n a y 三角剖分的子图 证明 假设e m s t 不是点集p 对应的d e l a u n a y 三角剖分 不妨记为d e 改d 的 子图 则在e m s t 中至少存在一条边y v 盛d p 尸 不妨先设玎 4 如图2 4 所示 最小生成树由边彳曰 么c 彳d 组成 d e 尸 由边彳曰 么d c 8 c d 和肋组成 则有边彳c 仨d p 尸 且彳c e m s r 作么d 的垂直平分线d p 交彳c 于d 下面分两种情况来讨论 1 d 在线段彳c 内 图2 4 a 所示 则有彳d 国o 则彳c 叫阱d c d d d c 加c 同理可证么d 哂c 所以图中所示最小生成树的权值并非是所有树中最小的 即其 不是最小生成树 所以么c 可由包含于d p 必p 的边d c 或b c 取代 所以假设不成 立 即e m s t 是d p p 的子图 2 d 在线段彳c 外 如图2 4 b 所示 可证此时边么c 为d e l a u n a y 边 事实 上 此时取彳b 垂直平分线交尸d 与d 点 则d 必在线段d c 右侧 即有三角形 彳肋的外接圆内包含有点c 则知肋不是d e l a u n a y 边 所以彳c 为d e l a u n a y 边 则有e m s t 是d p p 的子图 当刀 4 时 若存在不属于d e f 尸 的边 可找到四个点的d e l a u n a y 图 由上述 证明知 可将所有不属于d e 的边均用d e 改尸 中的边代替 即 z 4 时结论亦成 立 综上所述 点集p 对应的欧几里得最小支撑树e m s t 是其d e l a u n a y 三角剖分 的子图 证毕 第二章计算几何知识 a o 点在内部 b o 点在外部 图2 4d e l a u n a y 三角剖分与e m s t 对于任意一个三角剖分有如下性质 定理2 4 16 设尸为平面上不全部共线的任意力个点组成的一个集合 落在尸 的凸包边界上点的个数记作后 则尸的任何一个三角剖分必然由2 n 2 死个三角形组 成 而且共有3 z 3 后条边 证明 任取p 的一个三角剖分 记 中的三角形数目为 l 该三角剖分中 所含的面数记作行 则甩 聊 l 无界的面由忌条边围成 因为每条边与两张面 关联 所以 中所含边的总数为 z 3 m 后 2 又由欧拉公式得 刀一刀p 聆厂 2 将 与以 代人上式得m 2 以一2 一七 从而 z 3 z 一3 一后 证毕 d e l a u n a v 三角剖分还有其它一些良好的性质 如下 1 最接近性 以最近邻的三点形成三角形 且各线段 三角形的边 皆不相交 2 唯一性 不论从区域何处开始构建 最终都将得到一致的结果 3 区域性 新增 删除 移动某一个顶点时只会影响邻近的三角形 4 具有凸多边形的外壳 三角网最外层的边界形成一个凸多边形的外壳 3 应用 d e l a u n a y 三角剖分同v 0 r o n o i 图一样在诸多领域中都有着重要的应用 二维 d e l a u n a y 三角剖分是计算几何中的重要研究对象 有着广泛的应用背景 如 d e l a u n a y 三角剖分在数值分析 比如有限元分析 以及图形学等领域中有着非常重 要的应用 在高度插值方面 二维 三维或者高维的d e l a u n a y 三角剖分可以更精 1 6 基于计算几何图的拓扑控制算法 确的进行插值 另外 无线传感器网络中可应用局部的d e l a u n a y 图来生成拓扑结 构 1 或者将d e l a u n a y 图与其它网络模型结合可以得到一些具有良好性质的新拓 扑结构 2 2 本章小结 本章介绍了v 0 r o n o i 图和d e l a u n a y 三角剖分的定义及其性质 它们在计算几 何中被广泛的研究 由于它们互为对偶且都具有一些良好的性质 所以在许多领 域都有着重要的应用 在无线传感器网络领域 已经有一些文献 2 5 j 9 1 将它们应用于 网络的覆盖研究和拓扑控制 第三章基于d e l a u n a y 图的拓扑控制算法 1 7 第三章基于d e l a u n a y 图的拓扑控制算法 3 1 1 基本概念 3 1 基本知识 1 无线通信的能量消耗与通信距离的关系 传感器节点的能量消耗模块包括传感器模块 处理器模块和无线通信模块 然而 随着集成电路工艺的进步 处理器模块和传感器模块的能耗变得很低 因 此 绝大部分的能量消耗在无线通信模块上 无线通信的能量消耗e 与通信距离d 的关系为 e 材一 其中参数刀满足 2 z 如f 以 c 和 d 括f 口 6 如f 6 c 已知能量消耗公式为e 材 2 咒 4 c b 图3 1 任一三角形 若如f 口 6 如f 口 c d 衙 6 c 则称边如为口到6 或6 到口 的最优 能耗路 否则称口c c 6 为口到6 或6 到口 的最优能耗路 3 强连通 对于有向图d 中的任意两个顶点 和 d 中既存在 1 路 也存在 y 甜 路 则称d 图为强连通图 易知 若有向图d 是强连通的 则d 是连通的 反之则不 一定成立 1 8 基丁计算几何图的拓扑控制算法 4 对称性 双向连通 在无线传感器网络拓扑结构中的任意节点 保持一个链接 1 那么v 也维持 一个链接 即 1 之间可以双向通信 显然 若网络具有对称性 则必具有强 连通性 反之 则不正确 如图3 2 所示 ww a 对称性 b 强连通非对称 图3 2 对称性与强连通 5 平均节点度 对于一个以节点 l 条边的拓扑模型 其平均节点度是指节点所连的平均边 数 即2 m l 节点度对于拓扑控制有着重要的意义 文献 2 6 研究了平均度约束 的拓扑控制 6 无线网络模型 同质网络 h o m o g e n o u sn e t 在无线传感器网络中 假设存在刀个传感器节点 m 屹 且所有节点都有相同的最大发射半径 则称该类型网络为同质网络 如图3 3 所示 图3 3 同质网络 异质网络 h e t e r o g e n e o u sn e t 网络中的每个节点吩 扛l 2 z 都有自己的最 大发射半径 称该类型网络为异质网络 如图3 4 所示 异质网络更符合实际应 用 当然实现起来也就更有困难 7 一 f 图3 4 异质网络 u d g 模型 两个节点可以通信 如果他们之间的欧氏距离不大于一个阈值 显然u d g 模型可应用于同质网络 但不适用于异质网络 很多文献将u d g 模型 与d e l a u n a y 图结合 可得到u d e l 图 即在d e l a u n a y 图中将大于某一给定阀值的边 删掉而得到的图 该图具有很多良好的性质 m g 模型 两个节点可以相互通信 只有当他们位于彼此的发射范围内 即 节点 1 之间的欧氏距离满足如f 1 m 砌 匕 其中屹 分别为节点 v 的发射半径 m g 模型不依赖于h o m o g e n o u sn e t 的假设 而适用于更一般的网络 即不同节点具有不同的最大发射范围 因而更适合实际应用 显然 u d g 模型为 m g 模型的特例 7 相对邻近图 r e l a t i v en e i g h b o r h o o dg r a p h r n g 对于任意的平面点集尸 其相对邻近图定义如下 两个点p 和g 为相对邻近 图贡献一条边 当且仅当 d p g 如f 口 c 如f 6 c 3 2 则删除路径口6 否则保留路径如 2 算法设计思想 在基于邻近图的拓扑控制算法中 多数算法都是以某种规则建立路径 如基 于m s