无线传感器网络中目标连通覆盖算法
- 格式：pdf
- 大小：4.51 MB
- 文档页数：9
第41卷第3期 2017年6月南京理工大学学报Journal of Nanjing University of Science and TechnologyVol.41 No.3Jun.2017无线传感器网络中目标连通覆盖算法王槐元，丁旭，王力立，黄成，吴晓蓓(南京理工大学自动化学院，江苏南京210094)摘要：为了同时保障无线传感器网络的连通性和覆盖率，提出了目标连通覆盖（TCC)算法。
在充分考虑网络延时和负载均衡的情况下，通过部署最少量的中继节点保证目标位置与汇聚节点连通。
将部署在各目标位置周围的有向感知节点组成多个满足要求的覆盖集，保证各目标位置都被某个覆盖集覆盖，进而达到连通覆盖的目的。
仿真结果表明，该算法中各目标位置到汇聚节点的最大和平均路彳圣跳数优于已有算法，并且使得网络生命周期较长。
关键词：无线传感器网络；目标覆盖;连通覆盖；有向感知节点；覆盖集中图分类号:TP393.02 文章编号：1005-9830(2017)03-0285-09D O I：10.14177/ki.32-1397n.2017.41.03.003Target connected coverage algorithm for wireless sensor networks Wang Huaiyuan,Ding Xu,W ang Lili,Huang Cheng,Wu Xiaobei (School of Automation,Nanjing University of Science and Technology,Nanjing210094 ,China) Abstract：A target connected coverage (TCC )algorithm is proposed to ensure the networkconnectivity and coverage of wireless sensor networks.The TCC algorithm minimizes the communication delay and balances the path load by deploying the minimum number of relays to connect the targets and the sink node.The directional sensor nodes deployed around each target are from some cover sets to cover the target,and each target is covered by a cover set during the network duration,and the connected coverage is achieved.The simulation results demonstrate that the maximum and average routing hops between the targets and the sink node in the TCC are smaller than those in other algorithms,and the lifetime of the TCC is optimized.Key words：wireless sensor networks;target coverage;connected coverage;directional sensor nodes; cover sets收稿日期:2016-09-12 修回日期:2016-10-21基金项目：江苏省高校优势学科建设工程二期基金项目作者简介:王槐元（1989-)，男，博士生，主要研究方向:无线传感器网络容错拓扑，E-mail:why5841031@163.c〇m;通讯作者:吴晓蓓（1958-)，女，教授，博士生导师，主要研究方向:无线传感器网络、智能控制，E-mmI:wuxb@ njust. edu. cn〇引文格式:王槐元，丁旭，王力立，等.无线传感器网络中目标连通覆盖算法[J].南京理工大学学报，2017,41 (3): 285-293.投稿网址：http://zrxuebao. njust. edu. cn286南京理工大学学报第41卷第3期无线传感器网络由大量传感器节点通过自组 织的形式构成网络，从而实时监测目标区域的环 境以及相关事件。
为了保证网络的有效性，节点 之间的连通以及网络对于整个目标区域的覆盖显 得尤为重要，因此也成为了近年来主要的研究课 题之一。
覆盖基本可以分为区域覆盖、目标覆盖 以及栅栏覆盖[1]。
区域覆盖是比较常见的1种覆 盖方式，它要求区域内的每个点至少被1个感知 节点的感知区域覆盖；目标覆盖需要区域中的某 些目标位置至少在1个感知节点的覆盖范围内；栅栏覆盖则是注重于构建1个栅栏边界来检测人 侵或者为某些覆盖特性找到1条穿过相应部署区 域的渗透路径。
目前已经有较多针对区域覆盖问题的研究，主要可以分为节点优化部署[M]和覆盖空洞修 复[M]。
文献[2]基于概率感知模型提出了特征 点集的概念，然后根据计算得到的特征点集坐标 以及部署区域的栅格划分，采用改进的粒子群算 法得到各个区域节点最佳的部署位置，从而使得 整个部署区域满足一定的感知概率。
文献[3]提 出了1种在节点感知半径异构的网络中的覆盖面 积优化策略，以特定的采样直线扫描部署区域，从 而使节点按照相应的策略移动，使得覆盖重叠最 少。
文献[6-9]检测和确定覆盖空洞的边界节 点，然后按照各自的解决策略移动邻近节点或者 部署新节点，使得空洞得到覆盖，从而达到网络要 求。
也有不少专注于目标覆盖问题的研究[1°43]。
文献[10]将网络部署区域进行等边六角形划分，六角形的每个顶点以及中心视为目标覆盖位置，算法通过从各个目标位置附近选择最合适的节点 移动到相应位置来保证覆盖。
针对有向网络的目 标位置连通覆盖问题，文献[11 ]利用感知和通信 有向的节点自组织成簇来完成目标点的覆盖，提 出了分布式分簇目标覆盖算法（Target coverage algorithm through distributed clustering mechanism, TCDC)来规范相应的节点分簇规则，从而优化节 点成簇，并且在保证各个簇内目标位置覆盖的前 提下进行簇间的连通，从而在保证网络连通覆盖 的前提下优化网络的生命周期。
文献[13]在有 向感知网络中通过优化感知节点的感知角度来最 大化目标覆盖率。
由于目标覆盖只需要保证目标 位置的覆盖，因此在网络中大范围地随机布撒感 知节点使得节点的利用率不高，而且无法保证连 通覆盖。
栅栏覆盖由于其应用特殊性，也有不少研究文献[14，15]。
相比于区域的完全覆盖，目标覆盖在可行性 方面有更大的优势，使得其在交通路口路况监测、火灾报警以及人侵监测方面都有广泛应用。
因此，本文提出了感知有向的目标连通覆盖（Target connected coverage，TCC)算法:综合考虑最小生成 树和斯坦纳树方法，在部署最少数量中继节点保 证各个目标位置与汇聚（Sink)节点连通的同时，使得网络负载均衡，减少传输时延;在最初的节点 部署中充分考虑目标位置连通覆盖的基本特性，把 有向感知节点部署在各个目标位置附近，从而使得 更多的节点可以用于感知收集数据;基于概率感知 模型，在满足相应联合覆盖率的前提下，各个目标 位置周围的感知节点选择各自的感知方向形成多 个覆盖集;组成网络之后，没有感知任务的节点进 人休眠模式，有感知任务的覆盖集则轮流覆盖目标 位置，使得网络的生命周期得到很大提高。
1网络模型及问题假设问题1在二维区域内有M个目标位置，通 过咅卩署W个感知方向可变的感知节点（Sensor node)以及一定数量的中继节点（Relay node)，最 大化网络的生命周期，使得所有目标位置都能被 覆盖而且从目标位置收集到的数据可以通过中继 节点传输到sink节点。
假设各个目标位置的坐标（<，f)已知，W/ M个感知节点随机均匀地部署在每个目标位置 周围，每个感知节点S,有唯一的ID并且有固定 的已知坐标（^，7,)。
所有感知节点都有相同数 量的感知扇区（Sensing sector)[16]、感知半径_R s、通信半径足以及初始的能量感知节点可以处于激活或者睡眠模式。
中继节点只负责把感知 节点感知的数据传递到sink节点，而且所有中继 节点的通信半径杧也是相同的。
所有节点的通 信模型采用传统的圆盘模型，即彼此距离小于等 于通信半径时，认为2点可以互相通信。
感知节 点利用概率感知模型来感知区域内的目标位置。
由于每个感知节点都有相同数量的感知扇 区，每个感知扇区可以用以下参数表示：(1) 感知节点的最大感知角度0，〇<0<2tt;(2) 感知扇区的中心线是用来表示感知方向的矢量；(3) 用判断任意1点P是否位于节点S ,总第214期王槐元丁旭王力立黄成吴晓蓓无线传感器网络中目标连通覆盖算法287的第《个感知扇区的感知角度内，若位于感知角 度内则q p)=i，否则为0;(4)任意1点p被节点S,的第《个感知扇区覆盖的概率/^，p)[17]Un_rl q i>p)=l d(i,P)^R-Rac^=l R_R^d(i j p)^R s0 d(i,p)>Rs(1)式中:&是反应节点感知可靠性的参数，〇«矣K i，p)是节点到点p的距离，a和/3是与节 点本身相关的参数。
因此，多个感知节点同时检 测点P的联合覆盖率为pc,x<p,p)=i- n (!-^))^=i e<P\i\y s,,c i=i\(2)定义i点覆盖:对于区域内任意i个目标 位置P，如果P点的联合覆盖率满足匕…(少，P)為心则认为p被覆盖，否则未被覆盖，其中s是覆盖 阈值。
通过以上假设以及分析，问题1可以被表示 成整数线性方程式（3)，通过部署数量最少的中 继节点把各个目标位置连通起来，则感知节点就 可以把感知的数据通过中继节点传送到sink节 点（K多RC^R J。
Max rmSubject to Z C"；p)^1\/p eMy i<E N’M p e M\/i e N,C n(l p)= 11 (3)式中：7：表示所有M个目标位置被覆盖的时间，少表示所有能够感知到点P的节点集合。
第1个 限制保证所有的目标位置都至少被1个节点所感 知，第2个限制使得各个目标位置的联合覆盖率 达到预定的值“2目标连通覆盖算法TCC算法分为2部分：中继节点部署算法 (Relay node deployment algorithm，RDA)和有向感 知分配（Directional sensing distribution，DSD)算 法。
