（计算机软件与理论专业论文）无线传感器网络子集划分研究和位置验证研究.pdf

a b s t r a l c t a b s t r a c t w i r c l e s s n s o rn e t 、o r k s ，w h i c hi sas e l f b 唱a n i z e dd is c r i b u t e dn e t w o r ks y s t 伽 c o n s i s t i n go fal a 曙en u m b e ro ft i n ys e n s o r sw 油s c n s i n g ，c o m m u n i c a t i n ga h l d c o m p u t i n ga b i l i t i e s ，c 醐如l f i l lt h es 1 ) e c i f i cs e n s i n gt a s k w i 1t h e 蠡s td e v e l o p m e n t o fw l e s s n s o rn e t 、】v o r k sw h i c hh a v eg r e a tp o t e l l t i a l si nm i l i 切r y 印p l i c a t i o n ， e n v 的n m 锄ta p p i i c a t i o 鸭a i l dh e a l t ha p p j i c a t i o n 粕ds 0o 毡t l ew a yt h a lh u m a n 佗c o g n i z e 锄dc o m m u n i c a ：t cw 硫t h e n a t i l r eh 勰b e e nc h a n g i n g u s u a i l yt i l e s e n s o r sa r ed e p i o y e di n 觚a r e ar a l l d o m l yw i mt h ea c c e s s o r i a l d e v i c eb c c 卸t t l en u m b e ro f l e n s o r si sb i g 锄dt i l ee n v i r o n m e n to f l ea r e ai s p 0 0 r s om e n s o r sa 代d 印1 0 y e d 岫i f o n i l l yi l lt h ea m b a d 饥t i l ed e e p l y r e s e a r c ho nm ew i r e i e s s n s o rn e t 0 i ( sw 讹i l s o r sr a n d o m l y1 0 c a t e di n 觚a r 髓 t i l eo p t i m a is u b s e tp a n i t i o na 1 9 0 r i t h m 锄d1 0 c a t i o nv e r i f i c a t i o nu s i n gh o p _ d i s t 硼c e r c l a t i o n s h i pa r ep r o p o s c di nt h i sp a p e r t h eo p t i m a ls u b s e tp a r t i t i o na l g o r i 廿i mi sr e l 锄c dw i t l lm ec o v e r a g eq u a l i 够a n d n e 铆。呔l o n g e v i t yw h i c ha r e 加，ob a s i cp m b l 锄sj nw i r e j c s s 鼹n s o rn e l w o r k s a n d t h ef o l l o w i n gr e s u l t sh a v eb c e no b t a i n e dd u r i i l gt h er e s e 鲫c h n ei n f i u e n c e sw h i c ht l i es u b s e tc o u n t sl l a v eo nc o v c 随g cq 峪l 时a n d n e t w o r kl o n g e v 时h a v eb e e nd i s c o v c r e da n dc o v e r a g ei n t e n s 时a n d p a r t i t i o nu n i 内册i 妙 h a v eb np r o p o s e dt 0m e 嚣u r e砌ei | 1 f l u e n c e r e s p e c t i v e l y t h ec a l c u l a t e de x p r c s s i o no f l eo p t i n l a ls u b s e tp a n i t i c o u n th a sb n p r e s e n t e d t h ea p p r o a c ho f1 1 0 wt 0c a l c u la ：t et h eq 啪t 时o f n s o r sn e e d c dt 0b c d e p l o y c di 1 1 锄a r e a h a s b e p r o p 0 s e d l o c a t i o nv e r i f i c a t i o nu s i n gh o p d i s t a n c er e l a t i o n s h i pi sas u b p r o b l e mo ft h e a c c e s sc o n 仃0 lm e c h a n i s mi nw i r e l e 豁s e n s o rn 啪r k s a n dt l l e 凡l l o w i n gr 弱u j t s h a v eb c e i lo b t a i n e dd u r i n gt l l er e s e a r c h t h e 陀l a t i o i l s h i p so fm 啪锄dv a r i 觚c eb e t w e e nm u l t i p l eh o pd i s t a l 蛾锄d i i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：翅耋兰丝 僦年6 窍g 日 ，( b j 绪论 第1 章绪论 近年来，随着微机电系统、无线通信、信息网络与集成电路等技术的迅速 发展，无线传感器网络应运而生( a k y i l d i zi f ，s a l l l ( a 粥u b 栅锄i 锄y ，c a y i r c ie ， 2 0 0 7 ) 。这些由许多大大小小功能相同或不同的无线通信节点组成的网络，能够 探测周边环境中的温度、湿度、速度和方向等信息，并通过无线链路将探测到 的信息发送给用户。这种将逻辑上的信息世界与真实的物理世界融合在一起新 技术，将会深刻改变人与自然的交互方式。 1 1 研究背景 近年来，随着微机电系统、无线通信、信息网络与集成电路等技术的迅速 发展，无线传感器网络应运而生。并且作为一种新型的信息获取和处理技术日 益受到国内外的高度重视，美国 ：商业周刊认为无线传感器网络是全球未来 四大高技术产业之一，m i t 新技术评论认为无线传感器网络是改变世界的十 大新技术之一。 无线传感器网络的三个组成要素包括传感器节点、汇聚节点和用户。传感 器节点具有通信和计算能力，能够感知所在周边环境中的热、红外、声纳、雷 达和地震波等信号，从而探测包括温度、湿度、噪声、光强度、压力、土壤成 分、移动物体的大小、速度和方向等众多物理现象。大量的传感器节点协作感 知、采集和处理监测对象的信息，然后将探测到的信息通过无线单跳或多跳链 路发送汇聚节点。信息经过汇聚节点的初步处理，最后通过网关发送给用户。 如果说i n t e r n e t 构成了逻辑上的信息世界，改变了人与人之间的沟通方式，那 么无线传感器网络就是将逻辑上的信息世界与客观上的物理世界融合在一起， 改变了人类与自然界的交互方式。无线传感器网络以其自组织性、微型性和灵 活性等特点，使其在军事应用、空间探索和医疗卫生应用等领域具有广阔的应 用前景。 到目前为止，传感器网络的研究大致经历了两个阶段。第一阶段主要偏重 于利用微机电系统技术设计小型化的节点设备，代表性的研究项目有 绪论 w i n s ( p 叫i egj ，k a i s e rw j ，2 0 0 0 ) 和s m a nd u s t 。对于网络本身问题的关注和 研究可以认为是传感器网络研究的第_ 阶段，目前正成为无线传感器网络研究 的热点。 1 2 论文研究内容 本文通过对节点随机部署的无线传感器网络的深入研究，提出了子集划分 最优解算法和位置验证算法。 子集划分最优解算法的研究过程中，首先采用概率模型对随机调度算法中 的子集划分数量的影响进行分析，发现子集划分数量对网络的覆盖质量和生存 时间都存在影响，为了对这些影响进行量化，文中提出了覆盖强度和划分均匀 度的概念。在覆盖强度和划分均匀度的约束下，本文提出了子集划分数量最优 解算法，然后推导出了部署的传感器数量计算方法。理论分析表明，当子集划 分数量取得最优解时，划分均匀度和覆盖强度大于等于l l p ，网络的覆盖程 度和覆盖效率大于等于l l p ，并且当网络的通信半径是感应半径的两倍时， 网络的平均连通度约等于4 。最后通过实验仿真对该算法进行了验证。 在位置验证算法中，首先基于前入的研究成果，即线性网络中经过固定跳 数的数据包传输的距离满足高斯分布，本文推导出线性网络中k 跳距离均值为 单跳距离均值的k 倍和k 跳距离的方差为单跳距离方差的k 倍。为了在二维网 络中应用上述结果，本文约束二维网络中数据包的传输区域为带状区域，也就 是采用二维网络中带状区域去近似线性网络。研究发现二维网络中带状区域内 多跳距离的均值小于线性网络中多跳距离的均值，但是二维网络中带状区域内 多跳距离的方差等于线性网络中多跳距离的方差，因此可以将线性网络中的多 跳距离的方差应用到二维网络中。然后本文提出使用假设检验的办法去验证节 点宣称的位置信息。最后通过实验仿真对该算法进行了验证。 1 3 论文组织结构 论文全文共五章，内容组织如下： 第一章为绪论，介绍了论文选题的研究背景、研究内容和文章的结构安排。 第二章为无线传感器网络覆盖简介，首先从整体上对无线传感器网络进行 2 无线传感器网络简介 第2 章无线传感器网络简介 无线传感器网络是由大量形体较小、能源受限并且配置有计算和无线通信 能力的传感器节点组成的自组织网络，其目的是感知、采集和转发网络覆盖的 地理区域中感知对象的各种信息，最后通过无线多跳的形式将感知信息发送给 用户。本章首先简要介绍无线传感器网络整体结构和应用前景，然后分别介绍 无线传感器网络中覆盖问题、调度问题和安全问题。 2 1 无线传感器网络概述 2 1 1 网络结构 无线传感器网络是由许多大大小小功能相同或不同的传感器节点组成的自 组织网络，每个传感器节点具备数据处理和通信能力。下面分别从无线传感器 网络组成、节点结构和网络结构对无线传感器网络进行详细介绍。 1 无线传感器网络组成要素 一个典型的无线传感器网络是“由大量同构的、微小的、资源受限的、基 本不动的传感器节点随机分布在被测量区域，形成的大规模的、自组织的、多 跳的、未分割的网络”m e r k ，m a t t e mf 2 0 0 4 ) 。无线传感器网络通常由三个 部分组成：传感器节点、汇聚节点和用户，如图2 1 所示。 传感器节点具有感知、运算和通信等功能，每个节点能够采集环境数据( 如 温度、湿度、光强、震动、磁场等) ，并根据应用和系统需求对采集的数据进行 初步处理。它们既是信息包的发起者，也是信息包的转发者。节点由于受到体 积、价格和电源供给等因素的限制，通信距离较短，只能与自己通信范围内的 邻居节点通信，要访问通信范围以外的节点，必须使用多跳路由。为了保证网 络内大多数节点都可以与汇聚节点建立无线连接，节点的分布要相当的密集。 汇聚节点收集传感器节点传送的信息，然后通过特定网络将数据发送给用 户，这种网络可以由多种方式构成，如i n 姗e t 、卫星或游弋在监测区上空的无 人飞机等等。汇聚节点可以是普通的传感器节点，也可以是具有特殊功能的节 4 无线传感器网络简介 点。 用户是感知信息的最终接收者和应用者。用户可以主动地查询特定区域内 的特定信息，也可以被动地接收传感器网络发布的信息。 传感器节点 监测 图2 1 无线传感器网络结构 息 m 示器 毯 用户 2 无线传感器节点结构 传感器节点是一个具备感知能力、计算能力和通信能力的微型嵌入式系统。 在不同的应用中，传感器节点设计各不相同，但是它们的基本结构是一样的， 节点的典型硬件结构如图2 2 所示，主要包括电源及电源管理电路、传感器、 a d 转换器件、存储器、微处理器和射频模块等。此外根据不同的应用背景， 传感器节点可能还具有一些额外部件完成特定任务，如位置发现设备和移动设 备。 图2 2 无线传感器节点结构 5 无线传感器网络简介 电源和电源管理电路共同负责节点的能源供应。由于节点体积限制，电源 通常采用微型电池或者5 号电池，所以节点的能量供应非常的有限。电源管理 电路负责电源和节点之间的电压转换。 传感器主要职责是感知环境，将外部环境中的物理信号转化成电信号。传 感器可以感知的信号包括热、红外、声纳、雷达和地震波等，并且可以将探测 到的信号转化成温度、湿度、噪声、光强度和压力等信息。 a d 转换器负责将传感器提供的模拟信号转化成微处理器能够处理的数字信 号。 微处理器负责整个节点的信息处理和控制任务。通常微处理器的功率很低， 如b e r k e l e y 的m i c a z m o t e 系统采用的删e g a l l 2 8 l 微处理器的功耗只有 1 6 8 i n w 。 存储器负责节点信息的存储。 射频模块负责节点之间的通信。它是节点消耗能量最多的模块。 3 无线传感器网络结构 根据传感器节点同汇聚节点之间通信组织方式的不同，无线传感器网络的 结构形式分为以下两类，平面结构和层次结构，如图2 3 和图2 4 所示。 传感器节点 图2 3 平面结构 在平面结构网络中，所有的传感器节点地位平等，每个节点既是数据的发 起者也是数据的转发者。传感器节点与汇聚节点的通信可以是单跳通信也可以 是多跳通信。单跳通信中传感器节点同汇聚节点直接通信，路由组织简单，网 络架构简单，节点通信能量消耗主要由节点与汇聚节点的距离决定。多跳通信 6 无线传感器网络简介 是指传感器的感应信息通过中继节点发送给汇聚节点，由于传感器一般分布密 集，所以节点之间的通信能量消耗比单跳通信小，多跳通信主要涉及路由的选 择问题。在无线传感器网络中大多采用多跳通信方式。 图2 4 两层的层次结构 在层次结构网络中，所有节点的地位不再完全平等，而是存在一些特殊的 节点负责特定区域内节点的管理工作。层次结构类型包括两级结构和多级结构 两种类型。簇结构是层次结构中的典型代表。在基于簇的网络中，节点分为两 种：簇首节点和簇成员节点。每一个簇首节点都有一个作用域同其对应，该作 用域可以根据能量算法来确定，也可以通过通信距离来确定。在这个作用域中 的簇成员节点均从属于这个簇，簇成员节点同簇首节点之问通常采用单跳方式 通信，簇成员节点同汇聚节点之间的通信，均由簇首节点转发，而簇首节点同 汇聚节点的通信，通常采用多跳方式通信。 2 1 2 网络特点 无线传感器网络除了具有无线网络的移动性和断接性等共同特征以外，还 具有很多其它鲜明的特点( 刘丽萍，2 0 0 6 ，a g r ej ，c l a r el ，2 0 0 0 ，d c b 0 嘣le s 仃i n ， 黜哪e s hg 0 v i n d a i l j 0 l i nh e i d e m 锄e ta 1 ，1 9 9 9 ) ，这些特点包括：电源能量有限、 硬件资源有限、节点数量众多、网络自组织、动态拓扑和多跳路由。 1 电源能量有限 传感器节点一般由电池供电，由于节点体积限制，电池的容量也受到限制。 7 无线传感器网络简介 同时无线传感器网络通常运行在人无法接近的恶劣甚至危险的环境中，不能人 为给电池充电或更换电池。一旦节点电池能量用完，这个节点也就失效。因此 电源效率是设计无线传感器网络协议首要考虑的关键因素。 2 硬件资源有限 传感器节点由于受价格、体积和功耗的限制，其计算能力、程序空间和内 存空间非常有限。 3 节点数量众多 传感器节点的数量可能达到成千上万，甚至更多。传感器网络的超大规模 包含两方面的含义：一方面是传感器节点分布在很大的地理区域范围内，如森 林火灾监护和环境监测等；另一方面是指节点部署密集，并且存在大量的冗余 节点，以期获得精确的监测效果。 4 网络自组织 无线传感器网络的布设和展开无需依赖于任何辅助的网络设施，传感器节 点通过网络协议和分布式算法协调各自的行为。因此节点启动后就可以快速、 自动地组成一个独立的网络。 5 动态拓扑 在无线传感器网络中一些节点可以随处移动；一些节点可能会因为电池能 量耗尽、环境因素或其他故障而失效，退出网络；一些节点也可能由于工作的 需要而被添加到网络中，以上原因都会使网络的拓扑结构随时发生变化。 6 多跳路由。2 网络中节点通信距离有限，一般在几百米范围内，节点只能与它的邻居直 接通信。如果希望与其通信范围之外的节点进行通信，则需要通过中间节点进 行路由。 2 1 3 应用前景 无线传感器网络作为一种新的信息获取和处理技术，在各种领域，有着传 统技术不可比拟的优势。同时随着人类需求的提高和技术的发展。也必将存在 更加广阔的应用前景。就目前而言，无线传感器网络的应用前景主要包括以下 几方面( 刘丽萍，2 0 0 6 ，任丰原，黄海宁，林闯，2 0 0 3 ) ：军事应用、空间探索、 医疗卫生应用、智能家居和商业应用。 8 无线传感器网络简介 1 军事应用 军事应用是无线传感器网络技术的主要应用领域，由于其特有的无需架设 网络设施、可快速展开和抗毁性强等特点，是数字人战场无线数据通信的首选 技术，是军队在敌对区域中获取情报的重要技术手段。 2 空间探索 探索外部星球一直是人类梦寐以求的理想，借助于航天器布撒的传感器网 络节点实现对星球表面长时间的监测，是一种经济可行的方案。 3 医疗卫生应用 无线传感器网络在医疗卫生方面的应用包括：综合式患者监测、诊断；医 院药物管理；监视病虫或其它小动物的运动；生理数据的远程监视等等。内置 的无线传感器节点一方面可以收集和长期存储用于医学研究的生理数据，另一 方面允许监视对象有更大的运动自由度。 4 智能家居 嵌入在家具和家电中的传感器节点与i n t c m e t 连接在一起将会为人们提供 更加舒适、方便居住环境，从而实现家庭自动化和居住环境智能化。 5 商业应用 商业方亟的应用包括：监测材料疲劳；管理库存；监测产品质量；构建智 能办公室空间；办公大楼的环境控制；自动化制造环境的机器人控制和导航等 等。拿办公大楼环境控制为例：现在大多数办公大楼的空调和供暖是采用中央 控制方式，但是由于只有一个室内控制器和中央系统的气流不均匀，所以室内 温度可能稍有不同，一边或许比另一边暖，如果在办公大楼内布置无线传感器 网络就可以实现对不同区域温度监测和气流的控制。 综上所述，无线传感器网络无论是在军事领域还是在民用领域都具有广阔 的应用前景，其必将对2 1 世纪人类的生产和生活产生重大的影响。因此，研究 无线传感器网络的意义重大而深远。 2 2 无线传感器网络覆盖 无线传感器网络覆盖问题是指通过传感器节点的空间位置分布实现对被监 测区域或目标对象物理信息的感知，作为无线传感器网络中的一个基本问题， 从根本上反映了网络的感知服务质量。 9 无线传感器网络简介 2 2 1 传感器节点的感知模型 在对无线传感器网络覆盖问题进行研究时，研究者将无线传感器节点的覆 盖问题进行了相应的抽象化和模型化。本节介绍理论研究中经常用到的几种模 型：0 一l 模型、指数模型、统计模型和障碍模型。 1 - 0 一l 模型 o l 模型是节点感知模型中最简单的模型，它忽略了一些外界因素的影响， 使得问题更为简化，便于对问题更深一步的研究。在0 一l 模型中，节点的感知 范围是以节点为圆心，以感知距离为半径的圆：监测区域中的某点只存在两种 状态：被覆盖或者没有被覆盖。o - 1 模型的数学表达式为： 。 钆= ：； d 2 意 亿1 ) 其中，假设在被监测区域的某个节点t 的坐标为( 鼍，乃) ，节点的感应半径 为，：，目标位置j 的坐标为q ，乃) ，则节点岛与目标点j 的距离 砖，= ( t 一) 2 + ( 只一乃) 2 。用c f 表示节点墨对位置j 的感知质量，当被关注 事件e ，发生在位置j ，并且位置j 处在以节点置为圆心，以感知距离为半径 的圆内。则认为节点j 对事件e ，的感知质量为l ，否则位置j 处在以节点岛为 圆心，以感知距离为半径圆外，节点墨对事件e ，的感知质量为0 。 2 指数模型 在实际中人们发现传感器节点感知质量不是沪l 模型中的二进制形式，而 是感知信息的精确度与节点到目标位置的距离存在一个渐变的关系，即节点越 靠近目标位置其采集的信息越精确，节点越远离目标位置其采集的信息越粗糙。 因此很多文献修改了以往很多应用中常用的o l 模型，提出了感知质量随节点 和目标距离逐渐衰减的指数感知模型，其数学表达式如下所示： q ，= p 嘶。 ( 2 2 ) 其中，口为衰减情况参数，反映了节点对于目标位置的感知度随两者之阅 的距离变化情况，碣，为传感器节点到目标位置的距离。 3 统计模型 统计模型引入了传感器本身和物理环境的影响，节点的感应范围是种不 规则的图形。整体上，节点的感应范围依然与距离相关，离节点近的地方，节 1 0 无线传感器嘲络简介 钆韶鬻鬻 距；i 妻萼 ；翼；i 蠢i 磊篓莲螫雾鬻嚣 一： 主。鋈! 蓄霪藿栗蠹亨羹蘸篓 鳍萎雾艰鑫鋈藓雾萋涌粥夔羹羹錾匿霉堑雾塑薹璺羹；塞陌簿彗萋联妯羹囊 弼委蛳鳓囊| 誉豁薪i 篓槿玮涑缓羹瘘雾酲i ie 锍娄；美藉，丰二主囊譬萎li 篓 墼墅雪曼露坷囊糯墓到传鏖羹一列薰蓁渭狰泰，粤雾毯冀錾堡器兰& 瞻j 耄贱蓁錾囊慰畹 ；!霎雾堕鋈 蚕拦冀鬻淄璧蕊蓄器羹节点的距离在，- 一乞到，+ 范围内，节点对于被 监测 点的感知质量为两点间距离的指数函数；被监测点到传感器节点的距离大于 ，+ 兀，节点的感知质量为o 。统计模型的数学表达式为： q 2 0 ， s 西，j p 一缸，r - i ：z ，+ ( 2 3 ) l ， 一喀 其中也 ，如果传感器量属于子集c ， 那么传感器西就在时间片f ，处于工作状态，并在该周期的其余的时间片处于休 眠状态，以减少传感器能量消耗。子集选择采用随机数发生器实现，传感器在 每个周期t 开始以前随机生成1 至k 的整数，如果传感器量生成随机数j ，那么 传感器置属于子集c ，在时间片f ，处于工作状态。所有的节点在生命周期内依 照上述过程工作循环工作( 刘永生，周颢，赵保华，2 0 0 8 ) 。 随机调度算法的覆盖模型如图3 1 所示( l i uc h o n g ，x i a 0 g ，2 0 0 6 ) ，区域 a 中有8 个传感器s = “，) ，所有传感器划分成两个子集c = c l ，c 2 ) ，同 时一个周期被划分成两个时间片r = 以，岛 。在某个监测周期开始时，假设传感 器焉，岛，岛和生成随机数l ，传感器墨，岛和& 生成随机数2 ，这样所有的传 感器被划分成了两个子集c l = 岛，是，岛，& 和乞= s ，s ， ，在时间片子集 g 的传感器处于工作状态，子集岛的传感器处于休眠状态，此时传感器覆盖的 区域为图3 1 中实线圆包围的区域；在时间片如子集c 2 的传感器处于工作状态， 子集q 的传感器处于休眠状态，此时传感器覆盖的区域为图3 1 中虚线的圆包 随机调度算法子集划分研究 和延长网络生存时间。 3 1 3 假设条件 在对问题分析以前，首先给出随机调度算法覆盖模型的假设条件，随机调 度算法的研究大多数都是基于如下假设展开的。 1 二维平面区域彳是一个大尺度的区域，即区域a 的边界尺度远远大于传感 器的感应半径。 2 所有的传感器节点同构，即所有传感器的感应半径相同、通信半径相同， 并且在传感器工作过程中保持不变；所有传感器在开始工作以前具有相同 的能量，在工作状态单位时间内消耗相同的能量。 3 传感器的时钟一直保持同步。 4 传感器节点部署以后不再移动，节点自身没有移动的功能。 假设条件l 表示监测区域是一个大尺度区域，在这样的区域分析覆盖问题 不需要考虑传感器覆盖的边界效果，即理论上认为处于监测区域边界的节点和 监测区域中心的节点具有相同的感应的面积，忽略由于监测区域的边界所引入 的节点覆 x 随机调度算法子集划分研究 表3 1 本章中用到的数学符号 符号 含义 矗 传感器网络监测的区域 a 区域a 的总面积 q 点p 处于传感器感应范围内的概率 n 部署的传感器数量 岛 第i 个传感器节点 t t 周期t 内第i 个时间片 k 随机调度算法中子集数量 传感器的感应半径 传感器的通信半径 l 区域a 的覆盖强度 传感器的寿命 f c 区域a 需要传感器监测的总时间 d t | 节点墨与位置j 的距离 以 子集划分均匀度 3 2 子集划分最优解算法 3 ，2 1 节点惑知模型 根据2 2 1 节的分析可知，无线传感器网络的节点感知模型有o - i 模型、 指数模型、统计模型和障碍模型，本章的研究内容采用0 l 模型，该模型被广 泛的应用到无线传感器网络的研究中。 随机调度算法子集划分研究 尸c 。= d l 一，= ( ：) g 彳c t g ，”一d c 3 4 ， 由此可见，n 个传感器均匀分布在二维有界区域a 内，位置j 处的事件被 感知的概率为服从参数为( 胛，n ) 的二项分布。这也就是本章所采用的网络感知 模型公式。 3 2 3 算法描述 在二维平面区域内布撤n 个传感器节点，传感器节点在区域内均匀分布， 在区域a 内随机选择位置点j ，坐标为( x ，y ，) ，由上节的节点感知模型和网 络感知模型可知，d 个节点共同覆盖位置j 的概率为： p ( d ：d l ) ：f ：1 9 j ( 1 一留) 一j ( 3 5 ) 口 其中，p ，= 万彳口为一个传感器节点覆盖位置j 的概率，艺为传感器的感 应半径，a 为区域a 的面积。 由随机调度算法的数学描述可知，在每个周期开始所有的传感器生成随机 数以决定在某个时间片处于工作状态，任何一个传感器属于子集q 的概率为 1 七，假设有b 个传感器属于q ，那么子集q 覆盖位置j 的概率为： 酬 l | 肛剡枷一柚妻印刮力 = 喜( ：) 唼，6 c z 一柚。一c 一g ，6 ， c 3 6 ， = l 一( 1 一却” 子集中至少含有一个传感器，表示在时间片t 能够保证位置j 能够被传感 器监测到。k 个子集中非空的子集数量用k 表示，由以上分析可知，k 服从参数 为( 七，户( f q 陋ll 歹) ) 的二项分布，所以k 个子集中m 个子集覆盖位置j 的概率为： 尸( k ：所l _ ，) ：f 七1 ( 尸( 1c f 譬1 ) ) m ( 1 一尸( i q 巨l ”扣- ( 3 7 ) 尸( k = 所l _ ，) = ii ( 尸( 1c f 譬1 ) ) ”( 1 一尸( i q 巨l ”卜。 ( 3 7 ) 册 在求得了m 个子集覆盖位置j 的时间片数量以后，就可以计算一个周期内 覆盖位置j 的时间片数量，然后计算一个周期内覆盖区域a 的时间片数量。引 3 0 随机调度算法子集划分研究 理3 1 给出了一个周期内能够覆盖区域a 的时问片数量。 引理3 1 ：区域a 内n 个传感器服从均匀分布，采用随机调度算法对传感 器进行调度，一个周期内传感器覆盖p 点的平均时问片数量为 e ( 死) = 露( 1 一( 1 一”) ( 3 8 ) 咒 证明：因为k 个子集中m 个子集非空的概率为尸( 足= 历i ) ，所以一个周期 内覆盖位置j 的时间片数量为： 互( ll 歹) = 御( k = m l j f ) = 毫研( ( 吲 1 | 缈( 1 叫吲 l i 动h = 七尸( i c ，巨l i _ ，) ：七( 1 一( 1 一孚) 一 位置j 为随机选取，即位置j 的概率密度为六( x ，j ，) = l 口， 周期内覆盖区域a 的平均时间片数量。 e ( l ) = e ( 乃l _ ，) 尸( 歹) ( 3 9 ) 由此得到一个 = 昱( 乃i 川工乃( x ，y ) 蚴 ( 3 l o ) ：七( 1 一( 1 一旦) ”) 证明完毕。 由公式( 3 8 ) 可知，每个周期区域a 被覆盖的时间片数量与部署的传感器数 量n 、划分的子集数量k 、监测区域的面积和传感器的感应半径有关，通常情况 下监测区域的面积和传感器的感应半径都是已知的，不能随意更改。下面讨论 部署的传感器数量n 和子集划分数量k 对e ( l ) 的影响。 因为层( l ) 对n 可导，公式( 3 1 1 ) 为一阶导数。 挈“( 1 一争( 1 一 ( 3 1 1 ) 仂z 庀 丘 因为n 为传感器的数量，所以疗 0 ，在假设条件中假设监测区域的边界尺 度远远大于传感器感应半径，所以g l ，那么0 l g 七 l l p 。节点数量取值n = 5 0 0 0 0 。整个仿真程序的流程图 如图3 5 所示。 l 输觜最 i fk _ 3 i 采样点初始化 节点初始化 点 计算能够覆盖采样 一 点的节点 壬 0 对节点进行调度 采祥点的覆盖n t 问 片数罩= _、 j0 计算子集划分均匀 度 + 曩m e 铲= l i | n 嚣专l f 结果取姜蓉后写入 i ix q + 3 l 图3 5 划分均匀度仿真程序流程图 划分的子集数量k 取值最小3 ，依次增大3 ，最大为9 9 。对于k 的每个取值， 首先根据公式( 3 1 9 ) 计算理论值，以便与仿真结果进行对比。然后进行5 0 次模 拟，模拟结束时将5 0 次仿真结果取平均。 每次计算子集划分均匀度的过程如下：首先采样点初始化，在二维平面区 域随机选择一个采样点，因为在假设条件中忽略了覆盖问题中的边晃效应，所 以采样点不在监测区域的边界位置选择；节点初始化主要是将节点均匀分布在 监测区域，节点位置确定以后网络的拓扑图就形成了：根据采样点的位置和节 点的位置信息计算能够覆盖采样点的节点；对能够覆盖采样点的节点采用随机 4 5 随机调度算法子集划分研究 调度算法进行调度，同时记录一个周期内覆盖采样点的时问片数量，最后根据 子集划分均匀度的定义计算子集划分均匀度。 2 覆盖强度 主要分析l 随n 值的变化情况和l 随k 值的变化情况。同时检验当子集划分 最优解为七= 唧时，覆盖强度满足l l l p 。整个仿真程序的流程图如图3 6 所示。 n = l o o 由 图3 6 覆盖强度仿真程序流程图 随机调度算法子集划分研究 划分的子集数量k 取值最小3 ，依次增大3 ，最大为9 9 。对于k 的每个取值， 传感器数最n 最小值取l 0 0 0 0 ，依次增大1 0 0 0 0 ，最大为1 0 0 0 0 0 。对于每一组k 和n 值，首先根据公式，。= l 一( 1 一g 七) ”计算覆盖强度理论值，以便与仿真结果进行 对比。然后进行5 0 次模拟，模拟结束时将5 0 次仿真结果取平均。 每次计算覆盖强度的过程如下：首先采样点初始化，在二维平面区域随机 选择一个采样点，因为在假设条件中忽略了覆盖问题中的边界效应，所以采样 点不在监测区域的边界位置选择；节点初始化主要是将节点均匀分布在监测区 域，节点位置确定以后网络的拓扑图就形成了；根据采样点的位置和节点的位 置信息计算能够覆盖采样点的节点；对能够覆盖采样点的节点采用随机调度算 法进行调度，同时记录一个周期内覆盖采样点的时间片数量，最后根据覆盖强 度定义计算覆盖强度。 3 子集划分最优解 主要分析在划分均匀度和覆盖强度条件的约束下，子集划分取得最优解， 同时比较仿真最优解与理论最优解。仿真过程中数据采用划分均匀度和覆盖强 度仿真过程中生成的数据。 4 覆盖程度 主要分析覆盖程度c 足随传感器数量n 的变化情况和随子集数量k 的变化情 况，同时检验当子集划分最优解为七= w 时，覆盖程度满足c r l l e 。整个仿 真程序的流程图如图3 7 所示。 进行仿真以前确定采样点，综合考虑计算复杂度和结果的精确度，每1 0 木1 0 的区域内设置一个采样点。划分的子集数量k 取值最小3 ，依次增大3 ，最大为9 9 。 对于k 的每个取值，传感器数量n 最小值取l 0 0 0 0 ，依次增大l o 0 0 0 ，最大为1 0 0 0 0 0 。 对于每一组k 和n 的取值，进行5 0 次模拟，模拟结束时将5 0 次仿真结果取平均。 每次计算覆盖程度的过程如下：首先节点初始化，模拟将节点随机部署在 监测区域内，节点位置确定以后网络的拓扑图就形成了；对所有节点采用随机 调度算法进行调度，同时遍历所有采样点计算能够被覆盖的采样点数量，用被 覆盖的采样点数量除以总的采样点数量得到这个时间片的覆盖程度。 5 覆盖效率 主要分析覆盖效率c 引箍传感器数量n 的变化情况和随子集数量k 的变化情 况，同时检验当子集划分最优解为七= 叼时，覆盖效率满足c e l l p 。整个 仿真程序的流程图与覆盖程度仿真流程图相似，区别之处在于计算覆盖效率时 4 7 随机调度算法子集划分研究 用被覆盖的采样点数量除以所有节点覆盖面积之和所能包含的采样点数量。 是 结果取中均值q 入 文件 + n 鼍时。0 0 0 0 是 图3 7 覆盖程度仿真程序流程图 6 网络连通性 主要分析网络连通度随传感器数量n 的变化情况和随子集数量k 的变化情 况，同时检验当子集划分最优解为七= w 时，网络连通度满足e ( d ) = 4 ( 1 一g ) ， 在仿真过程中节点通信半径为感应半径的两倍。整个仿真程序的流程图如图3 8 所示。 划分的子集数量k 取值最小3 ，依次增大3 ，最大为9 9 。对于k 的每个取值， 传感器数量n 最小值取1 0 0 0 0 ，依次增大l 0 0 0 0 ，最大为1 0 0 0 0 0 。对于每一组k 和n 值，首先根据公式e ( d ) = ( 刀一1 ) 吼计算连通度理论值，以便与仿真结果进行对比。 然后进行5 0 次模拟，模拟结束时将5 0 次仿真结果取平均。 每次计算连通度的过程如下：首先节点初始化，模拟将节点随机部署在监 测区域内，节点位置确定以后网络的拓扑图就形成了；对所有节点采用随机调 4 8 随机调度算法子集划分研究 度算法进行调度，同时遍历所有节点计算每个节点的连通度，所有节点连通度 求和除以节点数量得到网络连通度。 是 3 5 3 仿真结果 i k - 3 n = l d 啪 l计算理论值 + t i m 嚣= l 是 - i 一l 结果取平均值写入 文件 + - i ：i h t o o 节点初始化 对节点进行调度 计算每个节点的连 通度 计算网络连通度 + t i m 岱q i m e s + i 图3 8 网络连通度仿真程序流程图 是 根据3 5 2 节描述的每一仿真项，本节给出相应的仿真结果，同时对相应的 仿真结果进行说明。 1