无线传感器网络随机分布模型及覆盖控制研究

1）位置无关的覆盖算法算法属于不依赖于节点位置信息的分布式覆盖算法。

该算法仅适用于圆形区域感知模型，且节点的传感半径与通信半径相等的情况。

各个节点根据如下信息判断自身的传感任务是否可由邻居节点完成：1-Hop内的邻居节点，以及这些邻居节点的1-Hop邻居节点。

当节点判断自身为冗余节点，就可以关闭自身节点的传感单元进入休眠状态。

优点：①不依赖于节点的位置信息；②关闭冗余节点之后，不降低原有的覆盖率。

缺点：①只适用于圆形区域感知模型，不适用于不规则的节点感知模型；②只适用于节点的传感半径与通信半径相等的情况；③绝大部分的冗余节点都不能满足上述判断条件，因此不能进入休眠状态；④没有考虑网络的连通性。

2）连通的随机调度覆盖算法［2］算法属于一种不依赖于节点位置信息的基于分组的分布式覆盖算法。

算法分4步完成。

第1步，将所有的传感器节点分为K组，每个传感器节点随机取1到K中的某个值i，并将自身分配到第i组。

第2步，每个节点获取到汇聚节点的最小跳数。

汇聚节点首先向邻居节点广播包含了到汇聚节点最小跳数的消息，最小跳数的初始值为0。

所有节点将记录到汇聚节点的最小跳数，同时忽略具有较大跳数的消息。

然后将跳数值加1，并转发给邻居节点。

通过这种方法，传感器网络中的所有节点能够记录下到汇聚节点的最小跳数。

第3步，各个节点向邻居节点广播消息，其中包括自身的ID，到汇聚节点的最小跳数以及组号等信息。

第4步，通过分配一些必要节点到某些组内，使每个节点能够在所属的分组内建立一条到汇聚节点的最短路径来构造连通网络。

分组i内的各个节点（不妨假设为A，它的最小跳数为n）首先判断在自身邻近区域内的下游节点（下游节点是最小跳数为n-1的节点）是否有节点属于分组i，如果没有，则节点A从这些节点中任选一个，并将它同时划分到分组i，以确保节点A从第n跳到第n-1跳是连通的，依此类推，从而建立一条A到汇聚节点的最短路径。

在执行完第4步之后，显然分组i构成的子网络是连通的。

无线传感器网络中的信任模型研究随着物联网时代的到来，无线传感器网络（Wireless Sensor Network，WSN）正成为人们关注的焦点。

无线传感器网络是由大量的低成本、小型化、高可靠的传感器组成的一种分布式系统，它可以实现环境监测、灾害预警、智能交通等多种功能。

然而，由于其开放性和复杂性，传感器网络面临着许多安全和隐私问题，其中最重要的就是信任问题。

本文将就无线传感器网络中的信任模型进行研究和探讨。

一、无线传感器网络的特点和信任模型的研究意义无线传感器网络由多个分布式传感器节点组成，这些节点可以自组成网络，相互配合，以实现一些目标任务。

这种网络有以下几个特点：1. 自组织性：无线传感器网络可以自动组网，无需人为干预。

2. 分布式：每个传感器节点都可以独立工作，并且拥有自己的存储和处理能力。

3. 能量有限：每个传感器节点都是由电池供电，能量有限，因此需要降低功耗，延长电池寿命。

4. 开放性：无线传感器网络是一个开放的环境，其中包含着大量的攻击者，他们可能对网络中的数据、传输过程等方面进行攻击，从而破坏网络的稳定性和安全性。

由于上述特点，无线传感器网络的安全性和稳定性成为了研究者们关注的重点。

信任模型的主要任务就是在传感器网络中建立一个有效的信任机制，以保障网络的安全性和稳定性。

信任模型在无线传感器网络中具有以下研究意义：1. 保障数据的安全性：信任模型可以在传感器网络中建立一个相互信任的机制，从而保障数据的安全性，防止数据造假和篡改。

2. 提高网络的可靠性：建立可信任的网络可以提高网络的可靠性，从而更有效地完成任务。

3. 降低网络的能量消耗：当网络中的节点彼此信任时，它们可以协同工作，充分利用资源，从而降低网络的能量消耗。

二、无线传感器网络中的信任模型在无线传感器网络中，信任模型的建立是非常重要的。

信任模型的建立可以从以下几个方面进行：1. 信任评估在无线传感器网络中，每个节点都需要被信任才能获得相应的权限，因此需要对每个节点进行信任评估。

无线传感器网络论文：无线传感器网络节点定位技术的研究与仿真【中文摘要】随着微电子技术、通信技术的发展, 功耗相对较低而且具有多种应用前景的传感器得以迅速发展, 与此同时, 由传感器组成的无线传感器网络应运而生。

无线传感器网络由大量随机密集部署于待测区域中的传感器节点组成, 是一种分布式、自组织的网络。

它主要应用在一些特定区域内进行数据的收集和处理, 这些特定的区域往往是环境恶劣而人力无法到达的地方, 这个时候无线传感器网络就能派上用场。

目前的研究主要集中在定位算法及路由协议, 物理测量技术(即硬件的实现上。

对于具体的应用来说, 没有位置信息的数据是没有任何意义的, 由于无线传感器网络的特殊应用, 使得一些传感器节点通常是通过飞机随机撒放在特定的区域, 这样就不可能直接得到这些节点的具体位置信息, 因此在应用之前先要对无线传感器网络进行节点定位。

但是由于无线传感器节点往往体积小、质量小, 能量特别有限, 定位系统在这种环境下的设计面临诸多挑战。

首先需要解决的是定位精度问题, 尽量在已有的距离测量模型上得到较准确的距离, 如何在现有模型下进一步提高定位算法的精度是亟待解决的问题；其次, 要考虑所设计的定位算法是否符合无线传感器网络特性, 如尽量让定位系统有效运行, 减少节点能耗等。

很多算法在进行定位时...【英文摘要】As the development of micro-electronics andcommunication technology, sensors with low power dissipation and multiple application prospects has mushroom growth, as a result, wireless sensor networks consisting of sensors emerge at the right moment.Wireless sensor networks(WSN consists of large amount of sensor nodes randomly and intensively distributed in areas to-be detected, which is a distributed and self-organized network, mainly used to collect and process data in certain locations, where people c...【关键词】无线传感器网络节点定位锚节点定位精度 DV-HOP算法【英文关键词】Wireless sensor network node positioning anchor node Positioning accuracy DV-HOP algorithm【目录】无线传感器网络节点定位技术的研究与仿真摘要4-6Abstract 6-7第1章绪论10-161.1 研究背景10-121.2 国内外研究现状12-131.3 课题研究目的和意义13-141.4 本文的研究内容及结构安排14-16第2章无线传感器网络概述16-222.1 无线传感器网络特点和结构16-172.2 无线传感器网络的应用领域17-192.3 无线传感器网络的研究热点192.4 无线传感器网络的性能评价指标19-212.5 本文的主要工作与章节安排21-22第3章无线传感器网络的定位技术22-383.1 传感器节点的定位问题22-233.2 传感器网络节点的硬件组成233.3 无线传感器网络定位的基本思想23-243.3.1 无线传感器网络节点定位的一些基本概念术语243.4 节点测距的基本方法24-273.5 无线传感器网络节点定位基本原理27-313.6 几种典型的定位算法31-333.6.1 质心定位算法31-323.6.2 凸规划定位算法323.6.3 MDS-MAP算法323.6.4 APIT定位算法32-333.7 定位算法的分类33-353.8 定位算法的评价标准35-363.9 无线网络中的集中典型定位系统36-373.10 本章小结37-38第4章 DV-HOP定位算法38-444.1 DV-HOP定位算法的介绍38-404.2 相关问题讨论分析40-434.2.1 不良节点的问题40-424.2.2 对拓扑变化的适应能力42-434.3 本章小结43-44第5章 DV-HOP算法改进44-495.1 参与三边测距的锚节点选择44-465.1.1 锚节点的拓扑形状对定位的影响44-465.1.2 共线度465.2 改进算法46-485.2.1 具体的算法实现过程46-475.2.2 改进算法理论分析47-485.3 本章小结48-49第6章仿真工具49-586.1 OMNET++介绍49-516.2 NS2简介51-526.3 NS2与OMNET++的对比52-536.4 仿真环境设置53-576.5 本章小结57-58第7章总结和展望58-607.1 全文总结587.2 展望58-60致谢60-61参考文献61-65攻读硕士学位期间发表的论文及参与的科研项目65。

无线传感网络的设计与优化第一章：引言无线传感网络（Wireless Sensor Network，WSN）是一种由多个分布在空间中的传感器节点组成的自组织网络。

由于其具有低成本、低功耗、易于部署等特点，无线传感网络在环境监测、物联网等领域具有广泛的应用前景。

本文将探讨无线传感网络的设计与优化，包括传感器节点的布局、通信协议的选择以及能量管理等关键技术。

第二章：传感器节点布局无线传感网络的设计首先需要考虑传感器节点的布局问题。

传感器节点的密度和分布对网络性能有着重要影响。

合理地选择传感器节点的布局可以提高网络的覆盖范围和数据采集的准确性。

2.1 节点密度与网络覆盖传感器节点的密度取决于具体应用场景和需求。

对于需要高分辨率的应用，如火灾监测，传感器节点的密度应适当增加，以提高覆盖效果和传感数据的准确性。

而对于一些较大范围的应用，如农业环境监测，传感器节点的密度可以适当减少，以降低成本和能量消耗。

2.2 节点分布策略传感器节点的分布策略是保证网络性能的关键。

常用的节点分布策略有随机分布、均匀分布和优化分布。

随机分布可以快速部署传感器节点，但往往导致传感器节点的冗余和覆盖不均等问题。

均匀分布能够保证传感器节点的覆盖均匀性，但节点之间可能存在较长的通信距离。

优化分布则是通过数学模型和算法来确定传感器节点的最佳位置，以达到最优的网络性能。

第三章：通信协议的选择无线传感网络的通信协议选择直接影响着网络的能效和可靠性。

合适的通信协议能够在保证数据传输的同时尽量降低能量消耗。

3.1 能耗分析传感器节点在数据传输过程中的能耗主要包括发射能耗、接收能耗和待机能耗。

对于不同的传感器节点，其能耗分布可能有所差异。

针对不同的节点类型和应用场景，需要进行能耗分析，以便选择合适的通信协议。

3.2 通信协议选择常用的无线传感网络通信协议有LEACH、TEEN、PEGASIS等。

LEACH协议是一种典型的分簇路由协议，能够有效地降低能量消耗。

无线传感器网络分簇路由算法的研究与改进的开题报告一、研究背景随着无线传感器网络技术的广泛应用，网络规模逐步增大，网络带宽和能量资源的限制也变得更加紧迫。

由于传感器节点的能量有限，因此如何有效地利用节点资源，延长网络寿命，成为无线传感器网络研究的关键问题之一。

在无线传感器网络中，簇路由是一种有效的能量管理和数据聚集方式。

簇头节点负责收集周围的数据，并将其汇聚到基站。

簇头节点和普通节点组成一个簇，其中簇头节点由其他节点选举。

然而现有的簇路由算法存在一些问题，比如算法复杂度高、能量分配不均等问题，这些问题会严重影响网络的性能和寿命。

因此，本人计划研究无线传感器网络分簇路由算法，通过改进现有的算法，提高算法的效率和能量利用率，降低节点能量消耗，延长网络寿命，在无线传感器网络应用中具有重要的理论研究价值和实际应用价值。

二、研究目的本次研究的目的是改进无线传感器网络分簇路由算法，提高算法性能和能量利用率，降低节点能量消耗，延长网络寿命。

具体目标如下：1. 综合现有簇路由算法的优势和不足，提出一种新的分簇路由算法，并证明其正确性和有效性。

2. 实现新算法的原型系统，并进行仿真实验，验证算法性能和能量利用率。

3. 与已有的分簇路由算法进行比较，评价改进算法与原算法的性能差异，证明优化算法的有效性和可行性。

三、研究内容1. 理论研究：综合分析现有分簇路由算法的优缺点，提出新的分簇路由算法，并证明其正确性和有效性。

2. 系统实现：基于新算法的设计思路和理论分析，实现原型系统，包括簇头节点的选举和能量分配、数据聚集和传输等功能。

3. 仿真实验：构建仿真实验平台，在不同的网络条件下，对新算法和比较算法进行仿真实验，比较性能和能量利用率。

4. 总结评估：评价改进算法与原算法的性能差异，总结实验结果，证明优化算法的有效性和可行性。

四、研究方法1. 理论分析：通过对现有分簇路由算法的综合研究，提出新的算法，分析其优势和不足，通过理论论证证明新算法的正确性和有效性。

无线通信的随机过程建模分析随着现代通信技术的不断发展，无线通信成为人们生活中不可或缺的一部分。

在无线通信中，随机过程建模分析具有重要的作用。

本文将从无线信道的随机过程、无线网络的随机过程和无线传感器网络的随机过程三个方面来进行探讨。

一、无线信道的随机过程无线信道是无线通信中最基本的环节，它的传输特性具有随机性。

无线信道的随机过程建模分析是研究无线信道传输的重要手段之一。

首先，我们可以将无线信道的传输过程建模为一个随机过程。

其中，随机过程的状态表示信道的各种状态，如信道的衰落、干扰等。

通过建立数学模型，可以分析信道容量、误码率等指标，并对无线通信系统的性能进行评估。

其次，无线信道的随机过程建模还可以应用于多址接入技术的分析。

在多址接入中，多个用户同时使用同一信道进行通信，因此信道中的信号相互干扰。

通过建立随机过程模型，可以对多址接入的性能进行分析，如系统的吞吐量、用户的时延等。

二、无线网络的随机过程无线网络是由多个无线设备组成的通信网络，其中设备之间的通信具有随机性。

无线网络的随机过程建模分析是研究无线网络性能的关键方法之一。

首先，我们可以将无线网络的拓扑结构视为一个随机图。

通过研究图的结构和连接方式，可以建立起无线网络的随机过程模型。

这种模型可以用于分析网络的覆盖率、连通性等性能指标，并为网络规划和优化提供理论支持。

其次，无线网络中的数据传输也可以建立为一个随机过程。

通过对数据传输的随机分布进行建模，可以研究网络的传输容量、传输速率等性能指标，并对网络资源进行优化配置。

三、无线传感器网络的随机过程无线传感器网络是由大量分布在空间中的传感器节点组成的网络，节点之间通过无线通信进行数据传输。

无线传感器网络的随机过程建模分析是研究传感器网络性能的重要方法之一。

首先，我们可以将传感器节点的分布视为一个随机过程。

通过建立节点的空间分布模型，可以研究网络的覆盖范围、能量消耗等性能指标，并对传感器节点的部署进行优化。

无线网络覆盖问题建模与求解方法研究无线网络覆盖是指在特定区域内，无线设备可以接收到网络信号的范围。

随着无线通信的普及和发展，人们对无线网络覆盖的需求也越来越高。

然而，由于地形、建筑物、电磁干扰等因素的存在，无线网络覆盖会遇到一系列问题，如信号弱、盲点等。

为了解决这些问题，需要对无线网络覆盖进行建模与求解，以提供更好的网络服务质量。

无线网络覆盖问题建模是指将实际的无线通信环境抽象成数学模型，通过对模型的分析和求解，得到网络的覆盖情况和性能指标。

建模是研究无线网络覆盖问题的第一步，它可以帮助我们更好地理解问题的本质，并为后续的求解提供指导。

在无线网络覆盖问题建模中，需要考虑以下几个方面：1. 地理环境：地理环境包括地形、建筑物、植被等因素，它们对信号的传播会产生影响。

可以利用地理信息系统（Geographic Information System, GIS）来获取相关数据，并将其作为建模的输入。

2. 信号传播模型：信号在空间中的传播过程可以用信号传播模型来描述。

常用的传播模型有自由空间模型、衰减模型、射线追踪模型等。

根据具体的应用场景和需求，选取合适的传播模型进行建模。

3. 站点部署：站点部署是指在特定区域内选择合适的无线基站位置。

根据地理环境和传播模型，可以通过数学优化方法来确定最佳的基站部署方案，使得覆盖范围最大化，同时满足用户的需求。

4. 频谱分配：频谱是有限资源，需要合理分配给不同的用户。

频谱分配问题可以通过整数规划、图论等方法进行建模和求解，以达到最大化频谱利用率和降低互相干扰的目的。

在建模的基础上，可以利用各种优化算法进行求解。

常用的求解方法包括数学规划、遗传算法、粒子群算法等。

这些算法可以在考虑问题约束条件的前提下，寻找最优的解决方案。

除了建模与求解方法，还可以利用仿真技术对无线网络覆盖问题进行评估和优化。

通过在计算机上构建模拟环境，可以模拟不同方案的性能，并通过比较得到最佳的解决方案。

无线传感器网络中的覆盖优化算法研究陶洋;林艳芬;黄宏程【摘要】针对无线传感器网络中经典的覆盖保持节点调度算法(CPNSS)查找冗余节点效率不高的问题,考虑实际传感器网络中节点感应半径不相同的情况,提出一种推广的高效覆盖优化算法(GECPNSS).建立扩展节点网络模型,分析多种节点位置关系,对中心角计算法进行扩展改进,并从括动节点数、平均覆盖度方面比较算法的性能.仿真实验结果表明,在保持初始覆盖的前提下,GECPNSS能更有效地提高冗余节点判定效率、扩展算法适应面.%Aiming at the problems of low efficiency to find redundant nodes in classical Coverage-Preserving Node Scheduling Scbeme(CPNSS) of the Wireless Sensor Network(WSN), this paper considers the situation that nodes have different sensing ranges in actual network and proposes a Generalized Efficient Coverage-Preserving Node Scheduling Scheme(GECPNSS). The algorithm builds extended node network model, analyzes different cases that how the nodes and their neighbors are located and improves the central angle calculation. The performances of these algorithms are compared in terms of number of active nodes and average cover degree. Simulation experimental results show that this improved algorithm enhances the efficiency of redundant nodes determine more effectively and better adapts to the complexity of the network, while maintaining the initial coverage.【期刊名称】《计算机工程》【年(卷),期】2011(037)001【总页数】4页(P119-121,124)【关键词】无线传感器网络;覆盖;冗余;感应半径【作者】陶洋;林艳芬;黄宏程【作者单位】重庆邮电大学软件技术中心,重庆400065;重庆邮电大学软件技术中心,重庆400065;重庆邮电大学软件技术中心,重庆400065【正文语种】中文【中图分类】TP3931 概述无线传感器网络(Wireless Sensor Network,WSN)的覆盖控制问题，即在保证一定服务质量(QoS)条件下，达到网络覆盖范围最大化，保证无线传感器节点有效地覆盖被监测的区域或目标。

无线传感器网络定位算法及其应用研究一、概述无线传感器网络（Wireless Sensor Networks, WSNs）是由一组能够自组织形成网络的低功耗、多功能、微型传感器节点组成，这些节点通过无线通信方式相互连接，实现对环境信息的实时监测和数据采集。

WSNs的出现，为物联网、智能城市、工业自动化、环境监测、军事侦察等领域带来了革命性的变革。

无线传感器网络中的节点往往因为能量、通信距离和成本等因素的限制，导致网络中的节点位置信息难以获取，从而影响了网络性能和应用效果。

研究无线传感器网络定位算法，对于提高网络性能、扩展应用范围具有重要意义。

无线传感器网络定位算法是指通过一定的数学方法和计算模型，利用网络中节点的距离、角度等信息，实现对节点位置的精确估计和计算。

随着无线传感器网络技术的不断发展，定位算法的研究也日益深入，出现了多种不同的定位算法，如基于测距的定位算法、无需测距的定位算法等。

这些算法各有优缺点，适用于不同的应用场景和网络环境。

本文旨在探讨无线传感器网络定位算法的基本原理、分类、优缺点以及在实际应用中的表现。

将对无线传感器网络定位算法的发展历程进行简要回顾，介绍各种经典算法的基本原理和实现方法。

结合实际应用场景，分析不同定位算法的适用性和性能表现，探讨其在实际应用中的优缺点。

展望未来无线传感器网络定位算法的发展趋势和研究方向，为相关领域的研究和应用提供参考和借鉴。

1. 无线传感器网络的定义与发展概述无线传感器网络（Wireless Sensor Networks，WSN）是一种分布式传感网络，其末梢是数以万计的微小传感器节点。

这些传感器节点通过无线方式通信，形成一个多跳自组织网络，具有灵活的网络设置和可变的设备位置。

WSN不仅可以通过传感器节点采集和监测环境信息，还能通过通信模块将信息传送到决策中心，实现对环境的感知、监测和控制。

无线传感器网络的发展始于20世纪80年代，随着计算机和通信技术的不断进步，其应用领域逐渐扩大。

第!"卷第#期重庆邮电学院学报!自然科学版"$%&’!"!(%’# #))*年+月,%-./0&%123%/456/47/689.:6;<%1=%:;:0/>?9&9@%A A-/6@0;6%/:!(0;-.0&B@69/@9"C D.’#))*文章编号#!""#$%&’#!(""&""($"!%%$"#!!无线传感器网络中覆盖度和连通度问题的研究"刘尧!盛敏!李建东!吕卓!西安电子科技大学信息科学研究所"陕西西安)!"")!#摘!要#对无线传感器网络中的覆盖度和连通度问题进行了研究#传统的求解覆盖度和连通度问题的整数规划算法对于大型的无线传感器网络$其整数规划算法的求解时间复杂度过高$导致算法效率偏低$通过对**+$,-.的研究$提出了一种新型的求解**+$,-.的盲覆盖区增强算法$该算法采用启发式的策略$大大降低了求解的时间复杂度$并且能够求出网络的近似最优解$非常适合于分布式应用#关键词#无线传感器网络!.-."%覆盖度%连通度%盲覆盖区增强算法中图分类号#/.’!%0")!!文献标识码#1)!引!言无线传感器网络!2345657775879485:294;" ,-.#是一种新型的1<=9>网络"由于其广泛的应用和发展潜力"引起了越来越多的关注$与传统的1<=9>网络不同",-.节点往往电量有限"并且不容易甚至无法更换电池"为了延长整个网络的生存期"需要使用大量的冗余节点"并令它们依次工作$从而引出了,-.的覆盖度和连通度问题"即**+$ ,-.!>9?54@A5@8<>9885>:3?3:B C49D65E38 ,-.#"这是,-.所面临的一个重要的问题$ **+$,-.主要解决的问题有%!在节能上如何使尽可能少的节点处于工作状态&"在网络覆盖上如何确保每个待观测点都至少在一个传感器节点的感知范围内&#在连通性上如何使工作的节点集合和738;节点连通$**+$,-.的解决能够使整个传感器网络以最小的能量代价来监测给定目标"从而达到延长网络生存期的目的$近年来的研究提出了一些解决**+$,-.的方法"F0+0G H38:@9等人提出了关于**+$,-.的整数规划数学模型"并且利用遗传算法进行求解’!(&-I5A H54<3>=3@8等人利用计算几何学中的J949893图来寻找网络中的节点覆盖密集区域和稀疏区域’((&K3L9H和M0*=@;4@D@4:B等人证明了**+$ ,-.是一个.+问题并且提出了求解覆盖问题的一种分布式算法’N($我们通过对**+$,-.的研究和分析"提出了一种新型的求解**+$,-.的盲覆盖区增强算法"该算法的时间复杂度远低于线性规划算法"并且能够求出网络的近似最优解"适用于分布式应用$!!22=E F B(的数学模型和分析$#%%&参考F0+0G H38:@9等人在文献’!(中对**+$ ,-.阐述和分析思路"我们对**+$,-.的数学描述和分析如下%给定传感器网络的覆盖区域!"所有待监测目标节点集合""传感器节点集合#"和738;节点$"**+$,-.包括%!使#中的一个子集覆盖"集合中的所有元素&"该子集和738;节点$之间存在通路$它是个混合整数规划问题"其数学模型表达如下$参数与变量%#%)!"("*"&+%传感器节点集合&"%)!"("*"$+%待监测目标节点集合&’%传感器节点的感知半径&(%覆盖精度"它决定了一个待监测的目标点被多少传感器节点所覆盖&)*%第*个传感器节点工作的代价&+,*%当第*个传感器节点能够覆盖第,个待监测点时"+,*为!&否则为""*##",#"&&,%当第,个待监测点没有被覆盖到时"&,为!&否则为"",#"&!-%传感器节点之间链路的集合&!.%传感器节点和其可覆盖到的待监测点之间的边的集合&!$%传感器节点和738;节点之间的链路的集合/0,*$1,"%*##"%0#!#2*#"%,*#!!-&!$#&3.!!#%边!,"*#的集合"终点为*"!,"*##!." *#"&"收稿日期#(""%$!"$(#!!修订日期#(""&$"!$!!基金项目#国家自然科学基金资助项目!&"%)(!#&"作者简介#刘尧!!’O!$"$女$陕西人$硕士研究生$研究方向为无线传感器网络&1<=9>网络$P$E@36’B63H$C>80Q3<3@80 5<H0>8%盛敏$副教授$博士$研究方向为无线传感器网络&1<=9>网络#3-!!#%边!,"*#的集合"终点为*"!,"*##!-&!."*##&4-!!#%边!,"*#的集合"起点为,"!,"*##!-&!$",##$决策变量%1,%当第*个传感器节点处于工作状态时"1,为!&否则为""*##$/0,*%当边!,"*#在传感器节点0和$之间的路径上时"/0,*为!&否则为""!,"*##!-$目标函数%I 383E 3R 5!!’*)*1*5’,&,-H D S 5>::9!!’*+,*1*((!!%,#"!!#1*%""!!!!%*##!(#’,*#3-*!!-#/0,*2’*(#4-*!!-&!$#/0,(%""%*#!#&$20#"%0##!N#’*(#4-*!!-&!$#/0,(%10"*%0"%0##!##/0,*$1,"%,##"%0#!#2*#"%,*#!!-&!$#!%#/0,*$1*"%*##"%0#!#2*#"%,*#!!-&!$#!&#在上面的目标函数方程中约束条件!!#确保了所有的待监测目标点都被传感器网络所覆盖到"并且覆盖精度为("约束条件!(#限定了决策变量的值为布尔类型"约束条件!N #"!##"!%#"!&#与连通度问题有关"它们保证了工作的节点集合和738;节点相连通$通过求解这个数学模型的解"可以得到一个工作节点的最优集合"该集合是#的一个子集"它以尽可能少的传感器节点覆盖所有待监测点"**+$,-.数学模型的解中也包括了最优集合与738;节点之间的路径$#!求解22=E F B (的盲覆盖区增强算法的提出和分析#6!!盲覆盖区增强算法简介盲覆盖区增强算法首先采用分治法的策略"将求解**+$,-.分成(个子问题"即覆盖度问题和连通度问题"然后对这(个子问题分别进行求解"以降低计算的复杂性"最后合并覆盖度问题和连通度问题的解从而得到**+$,-.的一个近似最优解"算法在求解覆盖度问题时采用了启发式的思想"在求解连通度问题上采用了T 3S ;7:4@最短路径搜索的思想$#6#!盲覆盖区增强算法的数学描述给定传感器节点集合#和所有待监测目标点集合""假设共有&个传感器节点"$个待观测目标点$首先根据文献’&(引出如下N 个定义$定义!#工作节点向量$布尔类型向量是任意一个传感器节点工作与否的布尔描述"即若第,个传感器节点处于工作状态"则相应的第,个向量元素为!"否则为"$定义##覆盖向量$布尔类型向量是任意一个待监测目标点是否被第,个传感器节点所覆盖到的布尔描述"即若第*个待观测点被第,个传感器节点所覆盖到"则相应的第*个向量元素为!"否则为"$定义G #覆盖矩阵$由所有传感器节点的覆盖向量所构成的矩阵"是对整个网络覆盖状态的布尔描述"其第,行第*列元素表示第,个传感器节点是否覆盖到了第*个待监测目标点$以下分别是这N 个定义的具体例子%若工作节点向量为’"""!"!!("则说明该网络共有)个传感器"并且第#"第&"第)个传感器节点处于工作状态"即该传感器网络的工作节点集合为’#"&")("其他节点处于休眠或停机状态$若第,个传感器节点的覆盖向量为’!"!"!("则说明待监测的目标节点共有%个"并且传感器节点,能够覆盖到待监测节点!"N "%$若覆盖矩阵为!"""’("!!!"则说明该,-.共有(个传感器节点"#个待监测目标节点"第(行第N 列的元素为!"说明第N 个待监测目标点被第(个传感器节点所覆盖到"其他类似$设!为,-.的工作节点向量""为,-.的覆盖矩阵"则!,"表示每个待监测点的覆盖精度"即能够覆盖到同一个待监测目标点的传感器的个数"令#$!,"$如果#向量中的每个元素都大于""则所有的待监测目标点都被覆盖到$例如%工作节点向量!$’!!"(",-.的覆盖矩阵为"$!""!"!!")*+,"!!!"那么#U !,"%!!!"#,!""!"!!")*+,"!!!%!!!!!#"#向量中的每个元素都对应一个待监测目标点"可以看出,-.中的第!和第(个传感器可以覆盖到所有待监测目标节点"并且每个目标节点的覆盖精度都为!$因此"覆盖度问题可以归结为%已知布尔型覆盖矩阵""如何寻找出工作节点向量!"使之与"的矩阵乘积#向量中的每个元素都大于""并且使得向量!的!%范数最小"要解决这个问题可以用穷举法来搜索出向量!"但是对于大规模的,-.并不可行"因为穷举法虽然算法简单并能够得到最优解"但是,(,!!!!!!!重庆邮电学院学报!自然科学版#!!!!!!!!!!!!!!!第!O 卷时间复杂度为4!(&#"过高的时间复杂度使之在大型,-.中无法应用$盲覆盖区增强算法采用了启发式的策略搜索解集"首先找出覆盖精度为"的待监测目标点"其次选择出能够覆盖到该待监测目标点的传感器节点"并将其加入到工作节点集合中"这样经过若干次迭代"所有的待监测目标点都被覆盖到"该算法具有多项式时间复杂度"并得到一个近似最优解"下面是算法迭代步骤%第!步%初始化向量!为全""生成网络覆盖矩阵"&第(步%计算#$!,"&第N 步%扫描#向量"找出第一个值为"的向量元素"并记下元素位置"令其为*&第#步%将!向量相应位置置为!"使之与矩阵"的乘积#&中第*元素的值为!&第%步&扫描#向量"如果所有向量元素都大于""则转第&步"否则转第(步&第&步%计算从738;节点到!向量所选中的节点集合的最短路径"如果该路径上的节点不在!向量所选中的工作集合内"则选中该向量$将对应于路径上的节点的!向量元素置!算法的步骤!首先初始化向量!为全""即令所有的传感器节点都处于休眠状态"然后计算出,-.的覆盖矩阵"步骤(和步骤N 得到未被覆盖到的待观测目标点*"步骤#中选中一个传感器节点"使其能够覆盖到目标点*"步骤%判断是否所有的目标点都被覆盖到了"如果所有的目标点都被覆盖到了"那么转步骤&计算出738;节点和已经选好的工作节点集合的最短路径并将最短路径上的节点添加到工作节点集合中"否则"算法回到步骤("继续寻找盲点"并对其进行增强$易得该算法在最坏情况下的时间复杂度为4!$,!$5&5$,&##"这是一个多项式时间复杂度$G !盲覆盖区增强算法的性能评估为了评估盲覆盖区增强算法的性能"我们一共随机生成了#个场景"在这#个场景中传感器节点的感知半径为!%E "待监测目标点的个数为((%个"同文献’)(和文献’O(的仿真场景设置相同"本文中的仿真也令所有的待监测目标点呈格型分布"738;节点在场景的中间$场景!为%"EV %"E 的区域"共配置了%"个传感器节点"场景(为)%EV)%E 的区域"共配置了)%个传感器节点"场景N 和场景#均为!""EV !""E 的区域"但是场景N 配置了!""个传感器节点"而场景#配置了(""个传感器节点$为便于验证"我们同时在I1/W 1X )0"上运行求解这#个场景**+$,-.的整数规划算法$算法程序调用了I1/W 1X )0"自带的整数规划函数D 38:C 49A"该函数经I1/W 1X 内核优化"代码执行效率高"并将其结果与盲覆盖区增强算法的结果相比较"其比较结果如表!所示$在这#个场景中"盲覆盖区增强算法都达到了!""Y 的覆盖度"即所有的待监测目标点都被覆盖到了"并且能够求出整个传感器网络的近似最优解"这些解与整数规划算法所得到的最优解的误差小于N Y "其计算时间远低于整数规划算法的计算时间$这是因为盲覆盖区增强算法没有整数规划算法执行过程中可能会出现大量的回溯"节省了处理机的计算时间$图!对算法的收敛性进行了验证"横轴表示工作节点数目占总的传感器节点数目的百分比"纵轴表示,-.的覆盖度"可以看出随着工作节点数目的增多"网络的覆盖度也迅速增加"两者近似线性关系$图!覆盖度与工作节点数目的关系图F 3A 0!Z 56@:3987=3C D 5:2558>9?54@A5@8<@>:3?589<58H E D 54表!!整数规划算法和盲覆盖区增强算法计算结果/@D 0!*9E C @43798D 5:255838:5A 546385@4C 49A 4@E E 38A @8<D 45@;$@45@$58=@8>5<@6A943:=E 场景工作节点数盲覆盖区增强算法整数规划算法覆盖度盲覆盖区增强算法!Y #整数规划算法!Y #算法执行时间-7盲覆盖区增强算法整数规划算法误差!Y #!)&!""!"""0"!N N 0O "(0"(!#!(!""!"""0"!N 0)N (0)N !’!&!""!"""0"!!(0(O N 0"#!’!&!""!"""0"N(!0O O!0%!!,N ,第(期!!!!!!!!!!!!刘尧"等%无线传感器网络中覆盖度和连通度问题的研究+!结!论在本文中"我们提出了一种求解**+$,-.的新型算法"算法通过在每次迭代中对覆盖盲点进行增强"来提高搜索效率"该算法具有多项式时间复杂度"对算法的测试结果显示出算法能够在较短时间内求出网络的近似最优解"并且具有较好的收敛性"适应于求解大型网络的**+$,-.$参考文献#(!)!G [\./1]F+$.1M 1I[Z 1F^$I1/P $[-^Z01=B D 43<@C C 49@>=:9796?5:=5>9?$54@A 5@8<>9885>:3?3:B C49D 65E 382345657775879485:294;7(P X *]W )0!(""#$"O $!("((""%$"O $(N )0=::C ’**25D =97:0H @0@>0D 5*5H E 5*294;7=9C 7*=B D 43<*1"(&Z 5?375<0C<_0(()!I P ^[P Z T \*‘\1.-$M ][-‘1.F 1Z F $+]/M ].a 1M I0*9?54@A5C 49D 65E 738234565771<=9>75879485:294;7(a )0\P P P /4@87@>:398798I 9D 365*9E C H :38A$(""%$%#!!"’O #$’(0(N )!L][K 3$*‘1M Z 1X 1Z /K M01<37:43D H $:5<>9?54@A 5@8<>9885>:3?3:B $>58:43>:5>=$83b H 5_947565>:38A @>:3?589<57382345657775879485:294;7(a )0\P P P /4@870*9E CH :$547$(""%$%#!O "’’)O $’’!0(#)!T1-M \.I @4;-0T @7;380.5:294;@8<T 37$>45:5W 9>@:398I 9<567$16A 943:=E 7$@8<1C$C63>@:3987(I )0.52K 94;’a ]‘.,\W P Kc -].-$\.*$!’’%0(%)!李红刚$鲜思东0有限图的约化及其连通性(a )0重庆邮电学院学报!自然科学版"$(""%$!)!N "’N )&$N )O 0(&)*‘1M Z 1X 1Z /K M $\K P .^1Z--0*9<$38A :=594B _4@E 5294;_94:@4A5:69>@:39838<37:43D H :5<75879485:294;7(P X *]W )0!(""!$"’$(!"((""%$"O $!()0=::C ’**>7<!(0>9E C H :$54094A *C 547@A 58*T W 1D 7/9>0S 7C+4579H 4>5$+@:=U *<!*C 49>55<38A 7*c :9>U >9E C *C 49$>55<38A7*3:>>*(""!*!"&(*""*!"&(:9>0Q E !cT ]\U !"0!!"’*\/**0())*‘1MZ 1X 1Z /K M $\K P .^1Z --0^43<>9?54@A 5_947H 4?5366@8>5@8<:@4A5:69>@:39838<37:43D H :5<75879485:294;7(a )0\P P P/4@87@>:398798*9E CH :547$(""($%!!!("’!##O $!#%N 0(O )T ‘\W W ].--$*‘1M Z 1X 1Z /K M0-58794C 6@>5E 58:_945__5>:3?5>9?54@A5@8<7H 4?536$6@8>538<37:43D H :5<75879485:294;7(P X*]W )0!(""N $!"$()"((""%$"O $!()0=::C ’**355$5Q C 694503555094A*35!%*O %#&*()"N "*"!(""&()0C<_+@48H E D 54U !(""&()0!责任编辑’刘勇"H 9:90.@3%1@%89.0490/>@%//9@;686;<D.%I &9A :6/J 6.9&9:::9/:%./9;J %.K :W \[K @9$-‘P .^I 38$W \a 3@8$<98A$W [L =H 9!3&)7’$+8,7&#9,:&9:3&-8,8;8:$<,.,+&=&,>:’-,8?$<,d !&)!"")!$@6A 6B C ,&+"C I :;.0@;’/=5*9?54@A 5@8<*9885>:3?3:B +49D 65E !**+"38,3456577-58794.5:294;7!,-."377:H <35<38:=37C @C 54@8<@89?56@6A 943:=E>@665<X 45@;145@P 8=@8>5<16A 943:=E37C 49C975<:9796?5:=5**+016:=9H A =\8:5A 54W 385@4+49A 4@E E 38A !\W +">@8@679D 5H 75<:9>9C 523:=:=5**+$3:E @B 65@<:9>9E C 65Q >9E C H :@:3985__94:7386@4A 5,-.0X 45@;145@P 8=@8>5<16A 943:=E 5E C 69B 7@=5H 437:3>7:4@:5A B 2=3>=>@845<H >5:=5>9E C H :@:398@6:3E 5A 45@:6B 0-3E H 6@:398457H 6:77=92:=@::=5X 45@;145@P 8=@8>5<16A 943:=E C 54_94E 72566386@4A5,-.0L 9<J%.>:’2345657775879485:294;%>9?54@A 5%>9885>:3?3:B %D 45@;@45@58=@8>5<@6A 943:=E ,#,!!!!!!!重庆邮电学院学报!自然科学版#!!!!!!!!!!!!!!!第!O 卷,%,第(期!!!!!!!!!!!!刘尧"等%无线传感器网络中覆盖度和连通度问题的研究。

无线传感器网络优化覆盖研究【摘要】随着微机电技术、嵌入式计算机技术、分布式信息处理、无线电通信、传感器技术等关键技术的发展与成熟，无线传感器网络技术得到极大发展，无线传感器具有低耗能、体积小、支持短距离通信、价格便宜等特点，能够进行数据收集、数据通信、数据处理等处理。

无线传感器网络具有较强的环境适应能力，尤其在资源少、环境恶劣的无人区域具有较好的应用前景。

该系统广泛应用与城市管理、军事国防、抗震救灾、消防反恐、环境监测、危险区域监测等诸多的区域。

然而单个节点感知能力有限，很多情况下需要多特殊节点进行多重覆盖，提高对该节点的信息感知能力，因此，优化无线传感器网络覆盖显得至关重要。

本文主要介绍现行无线传感器网络优化覆盖的虚拟力算法和多重覆盖算法，以期与对无线传感器网络性能的提高。

【关键词】无线传感器网络；优化；覆盖0 引言无线传感器网络是结合微机电技术、嵌入式计算机技术、分布式信息处理、无线电通信、传感器技术等诸多技术上发展起来的一门多学科交叉的新兴信息感知处理技术。

无线传感器具有低耗能、体积小、支持短距离通信、价格便宜等特点，能够进行数据收集、数据通信、数据处理等处理。

无线传感器网络部署方便、灵活能够实时监测、感知和收集目标区域的相关信息，并通过无线网络上传终端实现信息的自动收集。

利用各网络节点的收集、传输、处理能力，感知目标区域的热能、音频、可见光和电磁波等信号，进而得到目标区域的温度、湿度、压力、光感强度、噪声等信息。

传感器节点在整个网络中不仅只有收集和反射数据的功能，同时还承担数据路由的角色，将收集到的数据上传到网关。

无线传感器网络极大的延伸了人们的信息收集能力，为人们提供真实直接有效的目标信息。

无线传感器网络具有较强的环境适应能力，尤其在资源少、环境恶劣的无人区域具有较好的应用前景。

该系统广泛应用与城市管理、军事国防、抗震救灾、消防反恐、环境监测、危险区域监测等诸多的区域。

无线传感器网络与传统网络相比较，传统网络主要是提供优质的服务和高效的带宽利用。