第8卷第4期 智能系统学报 Vol.8 No.4 2013年8月 CAAI Transactions on Intelligent Systems Aug.2013 D0I:10.3969/i.issn.1673-4785.201304030 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20130603.1601.003.html 带时延约束的连通目标覆盖最大化生命周期问题 梁俊斌2，刘明2 (1.广西大学计算机与电子信息学院，广西南宁530004：2.中南大学信息科学与工程学院，湖南长沙410083) 摘要：在无线传感器网络中，如何确保网络服务质量（如覆盖、连通）同时最大化网络生命周期是研究的热点和难 点在延时敏感的应用（如火灾、爆炸等灾害监测）中，传感器节点必须在有限的时间内传送它们的数据到汇聚节点. 为了研究这种应用下的连通目标覆盖，提出了一种带时延约束的连通目标覆盖问题(DCCTC).首先，将DCCT℃建模 成为限高的最大覆盖树问题(HLMCT),并证明它是NP-Complete的.然后，设计了一种快速启发式算法HLCWGC求 解HMCT问题.仿真实验和理论证明，HLCWGC在时延约束下获得的网络生命周期比已有的算法要好.具有较高的 应用价值和理论意义. 关键词：无线传感器网络：连通目标覆盖：最大化生命周期：时延约束：能量有效 中图分类号：TP393文献标志码：A文章编号：1673-4785(2013)04-319-08 中文引用格式：梁俊斌，刘明.带时延约束的连通目标覆盖最大化生命周期问题[J].智能系统学报，2013,8(4)：319325. 英文引用格式：LIANG Junbin,LIU Ming.Lifetime maximization for delay constraint connected target coverage[J].CAAI Trans- actions on Intelligent Systems,2013,8(4):319-325. Lifetime maximization for delay constraint connected target coverage LIANG Junbin'2,LIU Ming? (1.School of Computer and Electronic Information,Guangxi University,Nanning 530004,China;2.School of Information Science and Engineering,Central South University,Changsha 410083,China) Abstract:The issue of guarantying the QoS target coverage,network connectivity,etc.),and simultaneously maximizing the lifetime in wireless sensor network is a hot topic,yet difficult subject of study.In some delay-sensi- tive sensor networks,sensors must transmit data to sink-node within a limited time in order to monitor the critical physical environment (fires,explosions,etc.)To study connected target coverage in such delay-sensitive sensor networks,we propose to examine the delay-constraint connected target coverage (DCCTC)problem.The study, specifically,includes of:1)modelling DCCTC problem as a Height Limited Maximum Cover Tree (HLMCT)prob- lem and proving it is NP-complete 2)developping a fast heuristic algorithm,named HLCWGC(height-limited com- munication weighted greedy cover)to solve the HLMCT problem.Simulation results and theoretical researches show that HLCWGC algorithm is better than the existing algorithms in the delay-constraint sensor networks. Keywords:wireless sensor networks;connected target coverage;lifetime maximization;delay constraint;energy ef- ficiency 无线传感器网络(wireless sensor networks, 线传感器网络的部署就是为了使得目标能够尽可能 WSN)是由部署在监测区域内大量的廉价微型传感 长地被持续监测且节点感知的数据有效传送到汇聚 器节点，通过无线通信方式形成的一个多跳的自组 节点，即连通目标覆盖问题.此外，在灾害监测等应 织网络系统]在环境监测、军事等许多应用中，无 用中，如火情监测、化学品监测等，传感器节点必须 在有限的时间内将它们的数据传送到汇聚节点，否 收稿日期：2013-04-15.网络出版日期：2013-06-03 基金项目：国家自然科学基金资助项目(61103245)：广西自然科学基 则将有可能导致网络失效.在这种时延敏感的无线 金资助项目(2012 GXNSFBA053163)」 传感器网络应用中，除了需要考虑目标覆盖和网络 通信作者：刘明.E-mail:258187069@qgq.com 连通之外，还需要考虑数据的时延到目前为止，虽
第 ８ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．４ ２０１３ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０４０３０ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３０６０３．１６０１．００３．ｈｔｍｌ 带时延约束的连通目标覆盖最大化生命周期问题 梁俊斌１，２ ，刘明２ （１． 广西大学 计算机与电子信息学院，广西 南宁 ５３０００４； ２． 中南大学 信息科学与工程学院，湖南 长沙 ４１００８３） 摘 要：在无线传感器网络中，如何确保网络服务质量（如覆盖、连通）同时最大化网络生命周期是研究的热点和难 点．在延时敏感的应用（如火灾、爆炸等灾害监测）中，传感器节点必须在有限的时间内传送它们的数据到汇聚节点． 为了研究这种应用下的连通目标覆盖，提出了一种带时延约束的连通目标覆盖问题（ＤＣＣＴＣ）．首先，将 ＤＣＣＴＣ 建模 成为限高的最大覆盖树问题（ＨＬＭＣＴ），并证明它是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的．然后，设计了一种快速启发式算法 ＨＬＣＷＧＣ 求 解 ＨＬＭＣＴ 问题．仿真实验和理论证明，ＨＬＣＷＧＣ 在时延约束下获得的网络生命周期比已有的算法要好．具有较高的 应用价值和理论意义． 关键词：无线传感器网络；连通目标覆盖；最大化生命周期；时延约束；能量有效 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０４⁃３１９⁃０８ 中文引用格式：梁俊斌，刘明．带时延约束的连通目标覆盖最大化生命周期问题［Ｊ］． 智能系统学报，２０１３， ８（４）：３１９⁃３２５． 英文引用格式：ＬＩＡＮＧ Ｊｕｎｂｉｎ，ＬＩＵ Ｍｉｎｇ． Ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ ｆｏｒ ｄｅｌａｙ ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓ⁃ ａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（４）： ３１９⁃３２５． Ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ ｆｏｒ ｄｅｌａｙ ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ＬＩＡＮＧ Ｊｕｎｂｉｎ １，２ ， ＬＩＵ Ｍｉｎｇ ２ （１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃ Ｉｎｆｏｒｍａｔｉｏｎ， Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｎａｎｎｉｎｇ ５３０００４， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｈａｎｇｓｈａ ４１００８３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ： Ｔｈｅ ｉｓｓｕｅ ｏｆ ｇｕａｒａｎｔｙｉｎｇ ｔｈｅ ＱｏＳ （ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ， ｎｅｔｗｏｒｋ ｃｏｎｎｅｃｔｉｖｉｔｙ， ｅｔｃ．）， ａｎｄ ｓｉｍｕｌｔａｎｅｏｕｓｌｙ ｍａｘｉｍｉｚｉｎｇ ｔｈｅ ｌｉｆｅｔｉｍｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｉｓ ａ ｈｏｔ ｔｏｐｉｃ， ｙｅｔ ｄｉｆｆｉｃｕｌｔ ｓｕｂｊｅｃｔ ｏｆ ｓｔｕｄｙ． Ｉｎ ｓｏｍｅ ｄｅｌａｙ⁃ｓｅｎｓｉ⁃ ｔｉｖｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ， ｓｅｎｓｏｒｓ ｍｕｓｔ ｔｒａｎｓｍｉｔ ｄａｔａ ｔｏ ｓｉｎｋ⁃ｎｏｄｅ ｗｉｔｈｉｎ ａ ｌｉｍｉｔｅｄ ｔｉｍｅ ｉｎ ｏｒｄｅｒ ｔｏ ｍｏｎｉｔｏｒ ｔｈｅ ｃｒｉｔｉｃａｌ ｐｈｙｓｉｃａｌ ｅｎｖｉｒｏｎｍｅｎｔ （ｆｉｒｅｓ， ｅｘｐｌｏｓｉｏｎｓ， ｅｔｃ．）． Ｔｏ ｓｔｕｄｙ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｉｎ ｓｕｃｈ ｄｅｌａｙ⁃ｓｅｎｓｉｔｉｖｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ， ｗｅ ｐｒｏｐｏｓｅ ｔｏ ｅｘａｍｉｎｅ ｔｈｅ ｄｅｌａｙ⁃ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ （ＤＣＣＴＣ） ｐｒｏｂｌｅｍ． Ｔｈｅ ｓｔｕｄｙ， ｓｐｅｃｉｆｉｃａｌｌｙ， ｉｎｃｌｕｄｅｓ ｏｆ： １） ｍｏｄｅｌｌｉｎｇ ＤＣＣＴＣ ｐｒｏｂｌｅｍ ａｓ ａ Ｈｅｉｇｈｔ Ｌｉｍｉｔｅｄ Ｍａｘｉｍｕｍ Ｃｏｖｅｒ Ｔｒｅｅ （ＨＬＭＣＴ） ｐｒｏｂ⁃ ｌｅｍ ａｎｄ ｐｒｏｖｉｎｇ ｉｔ ｉｓ ＮＰ⁃ｃｏｍｐｌｅｔｅ ２） ｄｅｖｅｌｏｐｐｉｎｇ ａ ｆａｓｔ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ， ｎａｍｅｄ ＨＬＣＷＧＣ（ｈｅｉｇｈｔ⁃ｌｉｍｉｔｅｄ ｃｏｍ⁃ ｍｕｎｉｃａｔｉｏｎ ｗｅｉｇｈｔｅｄ ｇｒｅｅｄｙ ｃｏｖｅｒ） ｔｏ ｓｏｌｖｅ ｔｈｅ ＨＬＭＣＴ ｐｒｏｂｌｅｍ． Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ａｎｄ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈｅｓ ｓｈｏｗ ｔｈａｔ ＨＬＣＷＧＣ ａｌｇｏｒｉｔｈｍ ｉｓ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｔｈｅ ｄｅｌａｙ⁃ｃｏｎｓｔｒａｉｎｔ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ． Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ； ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ； ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ； ｄｅｌａｙ ｃｏｎｓｔｒａｉｎｔ； ｅｎｅｒｇｙ ｅｆ⁃ ｆｉｃｉｅｎｃｙ 收稿日期：２０１３⁃０４⁃１５． 网络出版日期：２０１３⁃０６⁃０３． 基金项目：国家自然科学基金资助项目（６１１０３２４５）；广西自然科学基 金资助项目（２０１２ＧＸＮＳＦＢＡ０５３１６３）． 通信作者：刘明． Ｅ⁃ｍａｉｌ：２５８１８７０６９＠ ｑｑ．ｃｏｍ． 无 线 传 感 器 网 络 （ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ， ＷＳＮ）是由部署在监测区域内大量的廉价微型传感 器节点，通过无线通信方式形成的一个多跳的自组 织网络系统［１⁃２］ ．在环境监测、军事等许多应用中，无 线传感器网络的部署就是为了使得目标能够尽可能 长地被持续监测且节点感知的数据有效传送到汇聚 节点，即连通目标覆盖问题．此外，在灾害监测等应 用中，如火情监测、化学品监测等，传感器节点必须 在有限的时间内将它们的数据传送到汇聚节点，否 则将有可能导致网络失效．在这种时延敏感的无线 传感器网络应用中，除了需要考虑目标覆盖和网络 连通之外，还需要考虑数据的时延．到目前为止，虽
·320· 智能系统学报 第8卷 然人们已经在连通目标覆盖问题上做了大量的工 可以分为以下2种：单覆盖要求的连通覆盖问 作，但是都没有考虑到网络中数据的时延。 题[和多覆盖要求的连通覆盖问题[214.综上所 根据网络的连通性要求不同，连通目标覆盖问 述，已有的连通目标覆盖算法都是针对网络覆盖要 题可以分为以下3种：不考虑连通的目标覆盖问题、 求或连通要求展开的相关工作，但是它们在网络时 单连通的目标覆盖问题、多连通的目标覆盖问题 延敏感的实际应用中并不适合，因为它们导致的网 1)不考虑连通的目标覆盖问题是指传感器节 络时延有可能是应用难以接受的因此本文针对网 点只需要保证将所有目标覆盖即可，而传感器节点 络时延敏感的应用，对带时延约束的无线传感器网 感知数据可以通过其他的方式（如分层网络）到达 连通目标覆盖进行研究 汇聚节点.这类问题已经被大量研究[36].Si jepcevic[)提出了一种不考虑网络连通的算法来保 1网络模型及问题定义 证整个区域都被覆盖：M.Cardei等4)将离散目标覆 1.1 网络模型 盖问题建模为NP完全的不相交集合覆盖问题：M 分别用S={s1,s2,…,sw}(IS1=N)和P= Caidei等)扩展了他们在文献[4]中的方案，提出了 {P1,P2,…Pw}(IP|=M)表示网络中的节点集合 一种可相交集合覆盖问题，比如一个节点可以同时 和被监测的目标集合.用R来表示网络中惟一的汇 在多个覆盖集合中：M.Caidei等[6进一步扩展他们 聚节点，即：SikS、P和R就组成了整个网络的拓 的工作，他们假设每个节点有多个感知范围来覆盖 扑关系，网络可以用有向图G=(V,E)进行表示，其 目标 中V=SUPUR,而E由网络中的通信边（由2个节 2)单连通的目标覆盖问题是指传感器节点需 点作为端点的边)和监测边（由一个节点和一个监 要保证将所有目标覆盖的同时，还需要保证传感器 测对象作为端点的边)构成如果Is:-s<R,则(s:, 节点感知数据至少有一条经过传感器节点的路径到 s)∈E;如果Is:-PI<R,则(s:,P)∈E.其中R表示 达汇聚节点L刊考虑了节点具有多感知范围的能 通信半径，R表示监测（感知）半径 量模型，通过建立一个虚拟的网络骨干，使得网络中 用S(r)表示在一段固定的操作时间？内，所 所有节点要么在骨干上，要么是骨干上节点的邻居， 有参与了目标监测的节点的集合；用S,(r)表示在 然后在骨干的基础上考虑目标覆盖.但是在文献[7] 一段固定的操作时间？内，所有参与了数据转发和 中，节点能量模型仅考虑了感知能量，并且建立的面 通信的节点的集合；用S(r)表示在一段固定的操 向整个网络的骨干并不是必需的.Zhao)考虑了节 作时间？内，所有处于工作状态的节点的集合.因 点在进行数据接收和数据发送时的能量消耗，能实 此，有S(r)=S(r)US,(r),S.(r)CS. 现网络内节点能量消耗的整体减少，但是没有考虑 假设网络具有如下特点：1)每个节点在固定操 如何均衡节点的能量消耗.Zhao等[)将连通目标覆 作时间？内，不会改变自己的工作/睡眠状态(Ac 盖(CTC)问题建模成最大覆盖树(MCT)问题，并且 tive/Sleep状态)：2)每个节点的采样频率都相同： 证明了最大覆盖树(MCT)问题是NP完全问题，给 3)数据无法汇聚：4)单跳之间的时延相同，忽略 出了最大覆盖树(MCT)问题解的一个上界.然后，提 MAC层的睡眠等待时间和包之间的冲突等 出一个近似算法App_MCT和一个贪婪算法CWGC 1.2问题定义 来解决MCT问题.在CWGC算法中，网络中的每个 无线传感器网络中，通常把网络中节点感知的 节点和每条边都被赋予一个权值利用贪婪策略，选 数据传送到汇聚节点的最大延时称为该网络的最大 择合适的节点和边构造一棵覆盖整个网络区域的 时延.在不考虑数据包与数据包之间碰撞的前提下， 树.仿真实验的结果表明，App_MCT和CWGC能在 可以简单地用路由跳数来评价路由时延.因此在基 保证覆盖率的条件下有效延长网络生命周期， 于树的路由模型下的连通目标覆盖问题中，可以用 3)多连通的目标覆盖问题是指传感器节点需要 汇聚节点为根的路由树的高度表示成该网络的最大 保证将所有目标覆盖的同时，还需要保证传感器节点 时延 感知数据至少有多条经过传感器节点的路径到达汇 定义1带时延约束的连通目标覆盖问题(de 聚节点Li等1o首先证明k连通的目标覆盖问题是 lay-constraint connected target coverage problem,DC- NP难的，然后提出了2种启发式算法在满足k连通 CTC). 和目标覆盖的前提下选出尽可能少的节点工作， 在网络中，存在M个地理位置已知的监测目标 根据网络的覆盖要求不同，连通目标覆盖问题 和N个传感器节点，而用户要求的延时约束为△，则
然人们已经在连通目标覆盖问题上做了大量的工 作，但是都没有考虑到网络中数据的时延． 根据网络的连通性要求不同，连通目标覆盖问 题可以分为以下 ３ 种：不考虑连通的目标覆盖问题、 单连通的目标覆盖问题、多连通的目标覆盖问题． １）不考虑连通的目标覆盖问题是指传感器节 点只需要保证将所有目标覆盖即可，而传感器节点 感知数据可以通过其他的方式（如分层网络） 到达 汇聚 节 点． 这 类 问 题 已 经 被 大 量 研 究［３⁃６］ ． Ｓｉ⁃ ｊｅｐｃｅｖｉｃ ［３］提出了一种不考虑网络连通的算法来保 证整个区域都被覆盖；Ｍ．Ｃａｒｄｅｉ 等［４］ 将离散目标覆 盖问题建模为 ＮＰ 完全的不相交集合覆盖问题；Ｍ． Ｃａｉｄｅｉ 等［５］扩展了他们在文献［４］中的方案，提出了 一种可相交集合覆盖问题，比如一个节点可以同时 在多个覆盖集合中；Ｍ．Ｃａｉｄｅｉ 等［６］ 进一步扩展他们 的工作，他们假设每个节点有多个感知范围来覆盖 目标． ２）单连通的目标覆盖问题是指传感器节点需 要保证将所有目标覆盖的同时，还需要保证传感器 节点感知数据至少有一条经过传感器节点的路径到 达汇聚节点．Ｌｕ ［７］ 考虑了节点具有多感知范围的能 量模型，通过建立一个虚拟的网络骨干，使得网络中 所有节点要么在骨干上，要么是骨干上节点的邻居， 然后在骨干的基础上考虑目标覆盖．但是在文献［７］ 中，节点能量模型仅考虑了感知能量，并且建立的面 向整个网络的骨干并不是必需的．Ｚｈａｏ ［８］ 考虑了节 点在进行数据接收和数据发送时的能量消耗，能实 现网络内节点能量消耗的整体减少，但是没有考虑 如何均衡节点的能量消耗．Ｚｈａｏ 等［９］ 将连通目标覆 盖（ＣＴＣ）问题建模成最大覆盖树（ＭＣＴ）问题，并且 证明了最大覆盖树（ＭＣＴ）问题是 ＮＰ 完全问题，给 出了最大覆盖树（ＭＣＴ）问题解的一个上界．然后，提 出一个近似算法 Ａｐｐ＿ＭＣＴ 和一个贪婪算法 ＣＷＧＣ 来解决 ＭＣＴ 问题．在 ＣＷＧＣ 算法中，网络中的每个 节点和每条边都被赋予一个权值．利用贪婪策略，选 择合适的节点和边构造一棵覆盖整个网络区域的 树．仿真实验的结果表明，Ａｐｐ＿ＭＣＴ 和 ＣＷＧＣ 能在 保证覆盖率的条件下有效延长网络生命周期． ３）多连通的目标覆盖问题是指传感器节点需要 保证将所有目标覆盖的同时，还需要保证传感器节点 感知数据至少有多条经过传感器节点的路径到达汇 聚节点．Ｌｉ 等［１０］ 首先证明 ｋ 连通的目标覆盖问题是 ＮＰ 难的，然后提出了 ２ 种启发式算法在满足 ｋ 连通 和目标覆盖的前提下选出尽可能少的节点工作． 根据网络的覆盖要求不同，连通目标覆盖问题 可以分为以下 ２ 种： 单覆盖要求的连通覆盖问 题［７⁃１１］和多覆盖要求的连通覆盖问题［１２⁃１４］ ．综上所 述，已有的连通目标覆盖算法都是针对网络覆盖要 求或连通要求展开的相关工作，但是它们在网络时 延敏感的实际应用中并不适合，因为它们导致的网 络时延有可能是应用难以接受的．因此本文针对网 络时延敏感的应用，对带时延约束的无线传感器网 连通目标覆盖进行研究． １ 网络模型及问题定义 １．１ 网络模型 分别用 Ｓ ＝ ｛ ｓ１ ， ｓ２ ，…， ｓＮ ｝ （ ｜ Ｓ ｜ ＝ Ｎ） 和 Ｐ ＝ ｛ ｐ１ ， ｐ２ ，…，ｐＭ ｝（ ｜ Ｐ ｜ ＝ Ｍ）表示网络中的节点集合 和被监测的目标集合．用 Ｒ 来表示网络中惟一的汇 聚节点，即：Ｓｉｎｋ Ｓ、Ｐ 和 Ｒ 就组成了整个网络的拓 扑关系，网络可以用有向图 Ｇ ＝ （Ｖ，Ｅ）进行表示，其 中 Ｖ ＝ Ｓ∪Ｐ∪Ｒ，而 Ｅ 由网络中的通信边（由 ２ 个节 点作为端点的边）和监测边（由一个节点和一个监 测对象作为端点的边）构成．如果 ｜ ｓｉ －ｓｊ ｜ ＜Ｒｃ，则（ ｓｉ， ｓｊ）∈Ｅ；如果｜ｓｉ －ｐｊ ｜ ＜Ｒｓ，则（ ｓｉ，ｐｊ）∈Ｅ．其中 Ｒｃ表示 通信半径，Ｒｓ表示监测（感知）半径． 用 Ｓｓ（τ） 表示在一段固定的操作时间 τ 内，所 有参与了目标监测的节点的集合；用 Ｓｒ（ τ） 表示在 一段固定的操作时间 τ 内，所有参与了数据转发和 通信的节点的集合；用 Ｓａ（ τ）表示在一段固定的操 作时间 τ 内，所有处于工作状态的节点的集合．因 此，有 Ｓａ（τ）＝ Ｓｓ（τ）∪Ｓｒ（τ），Ｓａ（τ）⊆Ｓ． 假设网络具有如下特点：１）每个节点在固定操 作时间 τ 内，不会改变自己的工作／ 睡眠状态（Ａｃ⁃ ｔｉｖｅ ／ Ｓｌｅｅｐ 状态）；２） 每个节点的采样频率都相同； ３）数据无法汇聚；４） 单跳之间的时延相同，忽略 ＭＡＣ 层的睡眠等待时间和包之间的冲突等． １．２ 问题定义 无线传感器网络中，通常把网络中节点感知的 数据传送到汇聚节点的最大延时称为该网络的最大 时延．在不考虑数据包与数据包之间碰撞的前提下， 可以简单地用路由跳数来评价路由时延．因此在基 于树的路由模型下的连通目标覆盖问题中，可以用 汇聚节点为根的路由树的高度表示成该网络的最大 时延． 定义 １ 带时延约束的连通目标覆盖问题（ｄｅ⁃ ｌａｙ⁃ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｐｒｏｂｌｅｍ，ＤＣ⁃ ＣＴＣ）． 在网络中，存在 Ｍ 个地理位置已知的监测目标 和 Ｎ 个传感器节点，而用户要求的延时约束为 Δ，则 ·３２０· 智 能 系 统 学 报 第 ８ 卷
第4期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·321· DCCTC问题就是在保证目标被完全覆盖的前提下， Height(T(r))≤H,1≤i≤x. 如何通过调度节点的工作/睡眠状态，均衡节点的网 定理1 HLMCT问题是NP-Complete的. 络消耗，从而最大化网络生命周期.其中，目标被完 证明因为MCT问题[)是假设限高H=o时 全覆盖指所有的目标均在至少一个节点的感知半径 HLMCT的一个特例，MSC问题)是假设限高H=1 内：延时约束则是目标点的数据通过工作节点的单 时HLMCT的一个特例.根据约束策略1s],因为 跳或者多跳在不超过△时间内送到Sik, MCT问题和MSC问题是NP-Complete的，所以 定义2覆盖树问题(MCT). HLMCT也是NP-Complete的.证毕. 给定一个有向图G=(V,E)和节点的初始能量 E。(s),通过找到一系列的树T(T1),T(T2),, 2时延约束的连通目标覆盖启发式算法 T(T,)和它们的操作时间T1,T2,…,T,使得网络生 本文设计了一个加权通信的限高覆盖树贪婪算 命周期L最大化 height-limited communication weighted greedy 将问题数学化表示为 cover,.HLCWGC)来解决HLMCT问题. 2.1 HLCWGC算法描述 max L HLCWGC只需要输入网络的基本参数S、P、R sL2E(s,T(,)）≤E,(),YseS 和操作时间τ，经过计算即可输出一系列高度受限 =1 的覆盖树T,T2,…,T 用T(r)=(S,(r)US,(r),E(r))表示在操作 为了便于描述，首先定义需要用到的一些符号： 时间τ内构建的高度受限的树.T(τ)的特性如下： S,为存活节点集合，S,为存活节点中能覆盖目标的 1)树根是Sik节点：2)树的叶子是负责采样的节 节点集合，P,为能被节点s覆盖的目标集合，0，为 点：3)每个目标至少与一个叶子节点相连 节点在HLMWCT算法中的路径权值，W(s)为节点s 在T()中，每个节点的能量消耗模型[)为 的贡献，s∈S,R(s,T)为在树T中节点s到Sink R E(s,T(T))= 的路径，R(s,T)=〈s,s1,…,R〉； [e,B(r)+emB(r),s∈S,(r)ands使S,(r): (e +e,)B(T)D(s,T(T)),sS,(T)and s eS,(T); R(s,T)为R(s,T)中除了源点s和终点RHLC e,B(r）+eaB(r）t WGC算法的描述如下： 1)S=S,S,=☑，x=1: (e+e,)B(T)D(s,T(T)),s E S,(T)ns,(T); 2)for eachs∈S; 0,s年S.(）ands主S.(r). 3)E,(s)=E(s): 式中：T(r)代表在操作时间r内构建的一棵树， B(?)代表在操作时间？内节点采集到的数据包的 4)ifP,≠☑，S,=S,U{s};end if; 5)end for 数量：e,和e,分别表示感知和传输1bit数据的能耗， 6)while U,esP,=P and S,≠☑， em表示节点发送能量，eam=e=e,+b·d份，其中节 7)phase 1: 点s:是发送节点，s是接收节点，d是s:和s之间的距 8)for each link(si,s)wj=exEo(s)/E,(s;); 离，a表示路径衰减因子，e,和b是常量；D(s,T(r))》 end for 表示节点s在T(r)中的后代节点数 9)Build a tree with HLSPT algorithm 定义3限高的覆盖树问题(height limited max- 10)phase 2: imum cover tree problem,HLMCT). 11)S=0,P'=☑，T=☑，T.=T; 给定一个有向图G=(V,E)、最大树高H和节 12 while P'≠P, 点的初始能量E。(s),通过找到一系列高度限定为 13)Find a sensor s'with max profit W(s) H的树T(x1),T(r2),,T(r)和它们的操作时间 T1、T2,…,T使得网络的生命周期L最大 14)S.=S.Us,P'=P'UP,.; 问题数学化表示为： l5)for each s∈R(s°，T) maxL=立： 16)0,=w,+(em+e,)B(r）×w,/E,(s) i=1 17)end for st.∑E(s,T(:)≤E(s),HseS: 18)end while 19)phase 3:
ＤＣＣＴＣ 问题就是在保证目标被完全覆盖的前提下， 如何通过调度节点的工作／ 睡眠状态，均衡节点的网 络消耗，从而最大化网络生命周期．其中，目标被完 全覆盖指所有的目标均在至少一个节点的感知半径 内；延时约束则是目标点的数据通过工作节点的单 跳或者多跳在不超过 Δ 时间内送到 Ｓｉｎｋ． 定义 ２ 覆盖树问题［９］ （ＭＣＴ）． 给定一个有向图 Ｇ ＝ （Ｖ，Ｅ）和节点的初始能量 Ｅ０（ ｓ），通过找到一系列的树 Ｔ （ τ１ ）， Ｔ （ τ２ ），．．．， Ｔ（τｘ）和它们的操作时间 τ１ ，τ２ ，…，τｘ 使得网络生 命周期 Ｌ 最大化． 将问题数学化表示为 ｍａｘ Ｌ ＝ ∑ ｘ ｉ ＝ １ τｉ； ｓ．ｔ．∑ ｘ ｉ ＝ １ Ｅ（ｓ，Ｔ（τｉ）） ≤ Ｅ０（ｓ），∀ｓ ∈ Ｓ． 用 Ｔ（τ）＝ （ Ｓｓ（ τ）∪Ｓｒ（ τ），Ｅ（ τ））表示在操作 时间 τ 内构建的高度受限的树．Ｔ（ τ） 的特性如下： １）树根是 Ｓｉｎｋ 节点；２） 树的叶子是负责采样的节 点；３）每个目标至少与一个叶子节点相连． 在 Ｔ（τ）中，每个节点的能量消耗模型［９］为 Ｅ（ｓ，Ｔ（τ）） ＝ ｅｓＢ（τ） ＋ ｅｔｒａｎｓＢ（τ）， ｓ ∈Ｓｓ（τ） ａｎｄ ｓ ∉Ｓｒ（τ）； （ｅｔｒａｎｓ ＋ ｅｒ）Ｂ（τ）Ｄ（ｓ，Ｔ（τ））， ｓ ∉Ｓｓ（τ） ａｎｄ ｓ ∈Ｓｒ（τ）； ｅｓＢ（τ） ＋ ｅｔｒａｎｓＢ（τ） ＋ （ｅｔｒａｎｓ ＋ ｅｒ）Ｂ（τ）Ｄ（ｓ，Ｔ（τ））， ｓ ∈Ｓｓ（τ） ∩Ｓｒ（τ）； ０， ｓ ∉Ｓｓ（τ） ａｎｄ ｓ ∉Ｓｒ（τ）． ì î í ï ï ïï ï ï ï 式中：Ｔ（ τ） 代表在操作时间 τ 内构建的一棵树， Ｂ（τ）代表在操作时间 τ 内节点采集到的数据包的 数量；ｅｓ 和 ｅｒ 分别表示感知和传输１ ｂｉｔ数据的能耗， ｅｔｒａｎｓ表示节点发送能量，ｅｔｒａｎｓ ＝ ｅ ｔ ｉｊ ＝ ｅｔ ＋ｂ·ｄ α ｉｊ，其中节 点 ｓｉ是发送节点，ｓｊ是接收节点，ｄｉｊ是 ｓｉ和 ｓｊ之间的距 离，α 表示路径衰减因子，ｅｔ和 ｂ 是常量；Ｄ（ｓ，Ｔ（τ）） 表示节点 ｓ 在 Ｔ（τ）中的后代节点数． 定义 ３ 限高的覆盖树问题（ｈｅｉｇｈｔ ｌｉｍｉｔｅｄ ｍａｘ⁃ ｉｍｕｍ ｃｏｖｅｒ ｔｒｅｅ ｐｒｏｂｌｅｍ，ＨＬＭＣＴ）． 给定一个有向图 Ｇ ＝ （Ｖ，Ｅ）、最大树高 Ｈ 和节 点的初始能量 Ｅ０ （ ｓ），通过找到一系列高度限定为 Ｈ 的树 Ｔ（τ１ ），Ｔ（ τ２ ），．．．，Ｔ（ τｘ）和它们的操作时间 τ１ 、τ２ ，…，τｘ 使得网络的生命周期 Ｌ 最大． 问题数学化表示为： ｍａｘ Ｌ ＝ ∑ ｘ ｉ ＝ １ τｉ； ｓ．ｔ． ∑ ｘ ｉ ＝ １ Ｅ（ｓ，Ｔ（τｉ）） ≤ Ｅ０（ｓ），∀ｓ ∈ Ｓ； Ｈｅｉｇｈｔ（Ｔ（τｉ）） ≤ Ｈ，１ ≤ ｉ ≤ ｘ． 定理 １ ＨＬＭＣＴ 问题是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的． 证明 因为 ＭＣＴ 问题［９］ 是假设限高 Ｈ ＝ ¥时 ＨＬＭＣＴ 的一个特例，ＭＳＣ 问题［５］ 是假设限高 Ｈ ＝ １ 时 ＨＬＭＣＴ 的一个特例． 根据约束策 略［１ ５ ］ ， 因 为 ＭＣＴ 问 题 和 ＭＳＣ 问 题 是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的， 所 以 ＨＬＭＣＴ 也是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的．证毕． ２ 时延约束的连通目标覆盖启发式算法 本文设计了一个加权通信的限高覆盖树贪婪算 法 （ ｈｅｉｇｈｔ⁃ｌｉｍｉｔｅｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｗｅｉｇｈｔｅｄ ｇｒｅｅｄｙ ｃｏｖｅｒ， ＨＬＣＷＧＣ）来解决 ＨＬＭＣＴ 问题． ２．１ ＨＬＣＷＧＣ 算法描述 ＨＬＣＷＧＣ 只需要输入网络的基本参数 Ｓ、Ｐ、Ｒ 和操作时间 τ，经过计算即可输出一系列高度受限 的覆盖树 Ｔ１ ，Ｔ２ ，…，Ｔｘ ． 为了便于描述，首先定义需要用到的一些符号： Ｓｌ 为存活节点集合，Ｓｓ 为存活节点中能覆盖目标的 节点集合，Ｐｓ 为能被节点 ｓ 覆盖的目标集合，ｗｓ 为 节点在 ＨＬＭＷＣＴ 算法中的路径权值，Ｗ（ｓ）为节点 ｓ 的贡献，ｓ∈Ｓｓ，Ｒ（ｓ，Ｔ）为在树 Ｔ 中节点 ｓ 到 Ｓｉｎｋ Ｒ 的路径，Ｒ（ｓ，Ｔ）＝ 〈ｓ， ｓ１ ，…，Ｒ〉； Ｒ － （ｓ，Ｔ）为 Ｒ（ｓ，Ｔ）中除了源点 ｓ 和终点 Ｒ．ＨＬＣ⁃ ＷＧＣ 算法的描述如下： １）Ｓｌ ＝ Ｓ，Ｓｓ ＝∅，ｘ ＝ １； ２）ｆｏｒ ｅａｃｈ ｓ∈Ｓｌ； ３）Ｅｒ（ｓ）＝ Ｅ０（ｓ）； ４）ｉｆ Ｐｓ≠∅，Ｓｓ ＝ Ｓｓ∪｛ｓ｝；ｅｎｄ ｉｆ； ５）ｅｎｄ ｆｏｒ ６）ｗｈｉｌｅ ∪ｓ∈ＳＰｓ ＝Ｐ ａｎｄ Ｓｌ≠∅， ７）ｐｈａｓｅ １： ８）ｆｏｒ ｅａｃｈ ｌｉｎｋ（ ｓｉ，ｓｊ ） ｗｉｊ ＝ ｅ ｔ ｉｊ ×Ｅ０ （ ｓｉ ） ／ Ｅｒ（ ｓｉ ）； ｅｎｄ ｆｏｒ ９）Ｂｕｉｌｄ ａ ｔｒｅｅ ｗｉｔｈ ＨＬＳＰＴ ａｌｇｏｒｉｔｈｍ １０） ｐｈａｓｅ ２： １１）Ｓ ＇ ｓ ＝∅，Ｐ′＝∅，Ｔｘ ＝∅，τｘ ＝ τ； １２ ｗｈｉｌｅ Ｐ′≠Ｐ， １３）Ｆｉｎｄ ａ ｓｅｎｓｏｒ ｓ ∗ ｗｉｔｈ ｍａｘ ｐｒｏｆｉｔ Ｗ（ｓ ∗ ） １４）Ｓ ＇ ｓ ＝ Ｓ ＇ ｓ∪｛ｓ ∗ ｝， Ｐ ＇ ＝Ｐ ＇∪Ｐｓ∗ ； １５）ｆｏｒ ｅａｃｈ ｓ∈Ｒ － （ｓ ∗ ，Ｔｘ） １６） ｗｓ ＝ｗｓ ＋（ｅｔｒａｎｓ ＋ｅｒ）Ｂ（τ）×ｗｓ ／ Ｅｒ（ｓ） １７）ｅｎｄ ｆｏｒ １８）ｅｎｄ ｗｈｉｌｅ １９）ｐｈａｓｅ ３： 第 ４ 期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·３２１·
·322. 智能系统学报 第8卷 20)for each s∈S,T.=T.UR(s,T.)；end for 8)for each edge(u,v)EG do; E,(s) 9)if Status(u)=“fringe”and Level(v)+l≤H 21)for each seT.T-min(() and W(v)>W(u)+W:(u,v)then 22)for each seT,E,(s)=E,(s)-E(s,T,(T)); 10)Level (u)=Level (v)+1;Status (u)= end for “fringe'”;dad(u)=v;W(v)=W(u)+Wg(u,v); 23)Remove some nodes and edges according to 11)end if Rule 1;x =x+1; l2)if Status(u)=“offtree'”and Level(v)+l≤H 24)end while then 算法1)~5)是初始化过程，算法产生的每一个 13)Level (u)=Level (v)+1;Status (u)= 覆盖树都会工作固定时长τ.把没有能量或者是能量 “fringe'”;dad(u)=v;W(v)=W(u)+W(u,v); 不足以维持系统操作时间τ：的节点叫做低能量节 14)end if 点：把那些虽然能量富裕，但是最小跳数超出H的 15)end for 节点叫做孤远节点.在每个构建新的覆盖树操作时 16)end while 间之前，将所有低能量节点和孤远节点从网络中删 17)Queue Q;Stack S;EnQueue (Q,R); 除后，网络图中仅存在有效的节点。 hops(R)=0;dadl(R)=-1;visisted(R)=1; 算法中每一轮结束的时间为 18)While not Empty(Q) E,(s) 19)v=DeQueue(Q); 2E(,7)7). T&=min(T,min( 20)for each edge(u,v)G do; 算法的每个覆盖树的构建都包含3个阶段，在 21)if visited(u)=0 then 第1个阶段7)~9)一棵连接各个存活节点的能量 22)EnQueue(Q,u);hops(u)=hops(v)+1; 有效的限高树被构造：第2阶段10)~18)行，算法 dadl(u)=v;visited(u)=1; 贪婪的选取节点来覆盖所有的目标：第3阶段19)~ 23)else if W(v)+W(u,v)<W(dadl(v))+ 22)更新节点的能量 Wi(u,dadl(v))and hops(u)>hops(v)then 在第1阶段，算法为网络中每条有向边赋权值， 24)dad1(u)=v; 比如有向边(s:,s〉的权值为 25)end if e写×E(s:) 26)end for 10= E(s:) 27)end while 接下来一棵限高的树被构造，因为在网络中构 28)for each node u such that Status(u)="off- 建一棵最小权值限高树是NP-Complete的.所以提 tree”do 出了一个启发式算法来构造最小权值的限高树，限 29)dad(u)=dad1(u);v=dad1(u);PushStack 高的最小权值树构造算法(HLSPT)的描述如下.算 (S4,u); 法返回了节点在树中的路径权值， 30)while dadl(v)-1 do: Construct a minimum communication weight tree 31)if Level(v)+hops(u)-hops(v)H then 1)for each node s do: 32)break; Level(s)=0;dad(s)=0;dadl(s)=0;hops(s)= 33)else 0;W(s)=0:Status(s)=“offtree”;visited=0; 34)dad(v)=dadl(v);PushStack (S,v);v= 2)for each edge(s,R)EG do; dadl(v); 3)Level(s)=1;dad(s)=s; 35)end if; W(s)=W,(s,u);Status(s)=“fringe”; 36)end while 4)end 37)while not EmptyStack(S) 5)while there is at least one "fringe"status node 38)x=popStack(S)y=dad(x);W(x)= in G do; W(y)+W(x,y) 6)select a fringe node v with the smallest weight 39)end while among all“fringe”nodes; 40)end for 7)Status(v)=“intree'”; 在第2阶段，采用贪婪策略选取相应的节点覆
２０）ｆｏｒ ｅａｃｈ ｓ∈Ｓ ＇ ｓ，Ｔｘ ＝ Ｔｘ∪Ｒ（ｓ，Ｔｘ）； ｅｎｄ ｆｏｒ ２１）ｆｏｒ ｅａｃｈ ｓ∈Ｔｘ，τｘ ＝ｍｉｎ（τｘ， Ｅｒ（ｓ） Ｅｓ（τｘ，Ｔｘ） τｘ） ２２）ｆｏｒ ｅａｃｈ ｓ∈Ｔｘ，Ｅｒ（ｓ）＝ Ｅｒ（ｓ） －Ｅ（ｓ，Ｔｘ（τ））； ｅｎｄ ｆｏｒ ２３） Ｒｅｍｏｖｅ ｓｏｍｅ ｎｏｄｅｓ ａｎｄ ｅｄｇｅｓ ａｃｃｏｒｄｉｎｇ ｔｏ Ｒｕｌｅ １； ｘ ＝ ｘ＋１； ２４）ｅｎｄ ｗｈｉｌｅ 算法 １） ～５）是初始化过程，算法产生的每一个 覆盖树都会工作固定时长 τ．把没有能量或者是能量 不足以维持系统操作时间 τｉ 的节点叫做低能量节 点；把那些虽然能量富裕，但是最小跳数超出 Ｈ 的 节点叫做孤远节点．在每个构建新的覆盖树操作时 间之前，将所有低能量节点和孤远节点从网络中删 除后，网络图中仅存在有效的节点． 算法中每一轮结束的时间为 τｋ ＝ ｍｉｎ（τ，ｍｉｎ ｓ∈Ｔｋ （ Ｅｒ（ｓ） Ｅｓ（τ，Ｔｋ） τ））． 算法的每个覆盖树的构建都包含 ３ 个阶段，在 第 １ 个阶段 ７） ～ ９）一棵连接各个存活节点的能量 有效的限高树被构造；第 ２ 阶段 １０） ～ １８） 行，算法 贪婪的选取节点来覆盖所有的目标；第 ３ 阶段１９） ～ ２２）更新节点的能量． 在第 １ 阶段，算法为网络中每条有向边赋权值， 比如有向边〈ｓｉ，ｓｊ〉的权值为 ｗｉｊ ＝ ｅ ｔ ｉｊ × Ｅ０（ｓｉ） Ｅｒ（ｓｉ） ． 接下来一棵限高的树被构造，因为在网络中构 建一棵最小权值限高树是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的．所以提 出了一个启发式算法来构造最小权值的限高树，限 高的最小权值树构造算法（ＨＬＳＰＴ）的描述如下．算 法返回了节点在树中的路径权值． Ｃｏｎｓｔｒｕｃｔ ａ ｍｉｎｉｍｕｍ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｗｅｉｇｈｔ ｔｒｅｅ １）ｆｏｒ ｅａｃｈ ｎｏｄｅ ｓ ｄｏ： Ｌｅｖｅｌ（ｓ）＝ ０；ｄａｄ（ｓ）＝ ０；ｄａｄ１（ｓ）＝ ０；ｈｏｐｓ（ｓ）＝ ０；Ｗ（ｓ）＝ ０；Ｓｔａｔｕｓ（ｓ）＝ “ｏｆｆｔｒｅｅ”；ｖｉｓｉｔｅｄ ＝ ０； ２）ｆｏｒ ｅａｃｈ ｅｄｇｅ〈ｓ，Ｒ〉∈Ｇ ｄｏ； ３）Ｌｅｖｅｌ（ｓ） ＝ １； ｄａｄ（ｓ）＝ ｓ； Ｗ（ｓ）＝ Ｗｉｊ（ｓ，ｕ）；Ｓｔａｔｕｓ（ｓ）＝ “ｆｒｉｎｇｅ”； ４）ｅｎｄ ５）ｗｈｉｌｅ ｔｈｅｒｅ ｉｓ ａｔ ｌｅａｓｔ ｏｎｅ “ｆｒｉｎｇｅ” ｓｔａｔｕｓ ｎｏｄｅ ｉｎ Ｇ ｄｏ； ６）ｓｅｌｅｃｔ ａ ｆｒｉｎｇｅ ｎｏｄｅ ｖ ｗｉｔｈ ｔｈｅ ｓｍａｌｌｅｓｔ ｗｅｉｇｈｔ ａｍｏｎｇ ａｌｌ “ｆｒｉｎｇｅ” ｎｏｄｅｓ； ７）Ｓｔａｔｕｓ（ｖ） ＝ “ｉｎｔｒｅｅ”； ８）ｆｏｒ ｅａｃｈ ｅｄｇｅ（ｕ，ｖ） ∈Ｇ ｄｏ； ９）ｉｆ Ｓｔａｔｕｓ（ ｕ） ＝ “ ｆｒｉｎｇｅ” ａｎｄ Ｌｅｖｅｌ（ ｖ） ＋１≤Ｈ ａｎｄ Ｗ（ｖ）＞Ｗ（ｕ）＋ Ｗｉｊ（ｕ，ｖ） ｔｈｅｎ １０） Ｌｅｖｅｌ （ ｕ ） ＝ Ｌｅｖｅｌ （ ｖ ） ＋ １； Ｓｔａｔｕｓ （ ｕ ） ＝ “ｆｒｉｎｇｅ”； ｄａｄ（ｕ）＝ ｖ； Ｗ（ｖ）＝ Ｗ（ｕ）＋ Ｗｉｊ（ｕ，ｖ）； １１）ｅｎｄ ｉｆ １２）ｉｆ Ｓｔａｔｕｓ（ｕ）＝ “ｏｆｆｔｒｅｅ” ａｎｄ Ｌｅｖｅｌ（ｖ） ＋１≤Ｈ ｔｈｅｎ １３） Ｌｅｖｅｌ （ ｕ ） ＝ Ｌｅｖｅｌ （ ｖ ） ＋ １； Ｓｔａｔｕｓ （ ｕ ） ＝ “ｆｒｉｎｇｅ”； ｄａｄ（ｕ）＝ ｖ； Ｗ（ｖ）＝ Ｗ（ｕ）＋Ｗｉｊ（ｕ，ｖ）； １４）ｅｎｄ ｉｆ １５）ｅｎｄ ｆｏｒ １６）ｅｎｄ ｗｈｉｌｅ １７ ） Ｑｕｅｕｅ Ｑ； Ｓｔａｃｋ Ｓｋ； ＥｎＱｕｅｕｅ （ Ｑ， Ｒ ）； ｈｏｐｓ（Ｒ）＝ ０；ｄａｄ１（Ｒ）＝ －１； ｖｉｓｉｓｔｅｄ（Ｒ）＝ １； １８）Ｗｈｉｌｅ ｎｏｔ Ｅｍｐｔｙ（Ｑ） １９）ｖ ＝ ＤｅＱｕｅｕｅ（Ｑ）； ２０） ｆｏｒ ｅａｃｈ ｅｄｇｅ（ｕ，ｖ） ∈Ｇ ｄｏ； ２１）ｉｆ ｖｉｓｉｔｅｄ（ｕ）＝ ０ ｔｈｅｎ ２２）ＥｎＱｕｅｕｅ（Ｑ，ｕ）； ｈｏｐｓ（ ｕ） ＝ ｈｏｐｓ（ ｖ） ＋ １； ｄａｄ１（ｕ）＝ ｖ； ｖｉｓｉｔｅｄ（ｕ）＝ １； ２３）ｅｌｓｅ ｉｆ Ｗ（ ｖ） ＋Ｗｉｊ（ ｕ，ｖ） ＜Ｗ（ ｄａｄ１（ ｖ）） ＋ Ｗｉｊ（ｕ，ｄａｄ１（ｖ）） ａｎｄ ｈｏｐｓ（ｕ）＞ｈｏｐｓ（ｖ） ｔｈｅｎ ２４）ｄａｄ１（ｕ）＝ ｖ； ２５）ｅｎｄ ｉｆ ２６）ｅｎｄ ｆｏｒ ２７）ｅｎｄ ｗｈｉｌｅ ２８） ｆｏｒ ｅａｃｈ ｎｏｄｅ ｕ ｓｕｃｈ ｔｈａｔ Ｓｔａｔｕｓ（ ｕ） ＝ “ ｏｆｆ⁃ ｔｒｅｅ” ｄｏ ２９）ｄａｄ（ｕ）＝ ｄａｄ１（ｕ）； ｖ ＝ ｄａｄ１（ｕ）； ＰｕｓｈＳｔａｃｋ （Ｓｋ，ｕ）； ３０）ｗｈｉｌｅ ｄａｄ１（ｖ） ≠－１ ｄｏ； ３１）ｉｆ Ｌｅｖｅｌ（ｖ） ＋ｈｏｐｓ（ｕ）－ｈｏｐｓ（ｖ） ≤Ｈ ｔｈｅｎ ３２）ｂｒｅａｋ； ３３）ｅｌｓｅ ３４）ｄａｄ（ ｖ） ＝ ｄａｄ１（ ｖ）； ＰｕｓｈＳｔａｃｋ （ Ｓｋ，ｖ）； ｖ ＝ ｄａｄ１（ｖ）； ３５）ｅｎｄ ｉｆ； ３６）ｅｎｄ ｗｈｉｌｅ ３７）ｗｈｉｌｅ ｎｏｔ ＥｍｐｔｙＳｔａｃｋ（Ｓｋ） ３８）ｘ ＝ ｐｏｐＳｔａｃｋ（Ｓｋ） ｙ ＝ ｄａｄ（ｘ）； Ｗ（ｘ） ＝ Ｗ（ｙ）＋ Ｗｉｊ（ｘ，ｙ）； ３９）ｅｎｄ ｗｈｉｌｅ ４０）ｅｎｄ ｆｏｒ 在第 ２ 阶段，采用贪婪策略选取相应的节点覆 ·３２２· 智 能 系 统 学 报 第 ８ 卷
第4期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·323· 盖所有的目标.算法首先给每个节点s赋予一个权 Sink的最小跳数. 值Profit(s): 算法28)~40)行，每个在仿Dijkstra算法运行 I P-PO P I 后仍然为“offtree'”状态的节点，启发式地寻找一条 Profit(s)=- 满足限高的最小加权路径到达Sik,并更改相应节 式中：IP.-P∩P1代表处于节点s的感知范围而没 点的路径权值.其中算法29)~36)行，“offtree”状态 有被覆盖的那些目标的集合，心，是节点s的权值，即 的节点寻找一条满足限高的最小加权路径，并将路 R(s,T)中所有边权值之和.然后算法始终选取用于 径上的节点push到一个堆栈中.算法37)~39)行， 最大权值的节点(13)来覆盖目标直到所有的目标 更改新路径上新加进节点的权值」 都已经被覆盖为止.当某个节点s被选中作为采样 节点后，那么R(s,T)上的节点将更新它们的路径权 3仿真实验与结果分析 值（算法16）行). 在仿真实验中，将HLCWGC算法与其他3种算 在第3阶段，算法将选中的叶子节点以及(s, 法CWGC、HLMSC-EWARE、HLMSC-SPT进行比较， T)加入树T中，同时根据能量模型更新这些节点的 CWGC不考虑延时的约束，与HLCWGC算法一样， 能量 采用贪婪策略选取节点，但是生成网络骨干的方法 2.2限高的最小权值树构造算法(HLSPT)描述 算法输入的是经过规则1处理的图G,输出的 与HLCWGC不同.HLMSC_SPT中源节点采样到数 是一棵最小权值树T.其中该树T是以Sik为根，以 据都通过最小路径传输到Sik,但是采取一种贪婪 图G中所有的有效传感器节点作为它的子孙 策略[)选取源节点.HLMSC-EWARE是考虑延时约 算法1)~4)行是算法的初始化过程，对每个节 束后的MSC算法，使用贪婪策略[)选取源节点，但 点u初始化了它在树T中的层次Level(u)、父亲节 是采取HLSPT算法生成的限高加权树传输数据.在 点dad(u)、节点的路径权值W(u)、节点的最小跳 网络最大时延和网络生命周期2个评价标准下评估 数hops(u)、节点在树中的状态Status(u)、节点在最 算法HLCWGC、CWGC、HLMSC-EWARE、HLMSC- 小跳数算法中的父亲dad1(u). SPT R 假设每个节点的能量初始为20J,各种参数设 置为e,=50n/bit、b=100pJ/m、a=4、e,= 150nJ/bit、e,=150nJ/bit;数据的采样频率为 10kB/s6].节点的感知半径为R,=20m,传输半径 为R。=40m.假设网络生命周期上界为Lp,其大小 可以采用枚举的方法来获取.所有节点随机地散布 在100mxl00m的区域内，Sink节点位于区域的中心. 图1限高树的示例 实验1测量HLCWGC算法与r的关系.固定 Fig.I Illustration of a height-limited tree 网络中传感器节点数为60，目标数为20，取r= 算法5)~l6)行仿照Dijkstra算法，构造一棵限 0.1%、0.2%、0.4%、0.6%、0.8%、1%Lp时，设置网络 高的最小权值树，但是这棵树并不是图G的生成 时延上限H为20和10时，得到的结果绘制成图2. 树，因为部分节点虽然在离Sik跳数比较近，但是 8x10 +-H=20 在仿Dijkstra算法中却不会被选中.比如：在图1中， *-H=10 节点d虽然可以两跳路径(d,r,R)到达R,但是它的 路径权值要大于路径〈d,S,…,S,R)的权值，所以 d不会被加入到路径〈d,r,R〉中.由于树高的限制， 可能(d,S,…,S,R)超过了高度限制，所以d也不 0.02 0.040.060.080.10 能加入到(S,…,S,R)构成路径(d,S,…,S,R） tLin 算法17)~27)行使用了一个数据结构队列Q 图2 HLCWGC算法生命周期与x的关系 来对图G进行层遍历，用dad1(u)表示在节点u在 Fig.2 The relationship of HLCWGC algorithm's life time with 层遍历中的父亲节点，hops(u)表示节点u距离
盖所有的目标．算法首先给每个节点 ｓ 赋予一个权 值 Ｐｒｏｆｉｔ（ｓ）： Ｐｒｏｆｉｔ（ｓ） ＝ ｜ Ｐｓ － Ｐｓ ∩ Ｐ ＇ ｜ ｗｓ ． 式中： ｜ Ｐｓ －Ｐｓ∩Ｐ ＇ ｜代表处于节点 ｓ 的感知范围而没 有被覆盖的那些目标的集合，ｗｓ 是节点 ｓ 的权值，即 Ｒ（ｓ，Ｔ）中所有边权值之和．然后算法始终选取用于 最大权值的节点（１３）来覆盖目标直到所有的目标 都已经被覆盖为止．当某个节点 ｓ 被选中作为采样 节点后，那么 Ｒ － （ｓ，Ｔ）上的节点将更新它们的路径权 值（算法 １６）行）． 在第 ３ 阶段，算法将选中的叶子节点以及 Ｒ － （ｓ， Ｔ）加入树 Ｔ 中，同时根据能量模型更新这些节点的 能量． ２．２ 限高的最小权值树构造算法（ＨＬＳＰＴ）描述 算法输入的是经过规则 １ 处理的图 Ｇ，输出的 是一棵最小权值树 Ｔ．其中该树 Ｔ 是以 Ｓｉｎｋ 为根，以 图 Ｇ 中所有的有效传感器节点作为它的子孙． 算法 １） ～４）行是算法的初始化过程，对每个节 点 ｕ 初始化了它在树 Ｔ 中的层次 Ｌｅｖｅｌ（ｕ）、父亲节 点 ｄａｄ（ｕ）、节点的路径权值 Ｗ（ ｕ）、节点的最小跳 数 ｈｏｐｓ（ｕ）、节点在树中的状态 Ｓｔａｔｕｓ（ｕ）、节点在最 小跳数算法中的父亲 ｄａｄ１（ｕ）． 图 １ 限高树的示例 Ｆｉｇ．１ Ｉｌｌｕｓｔｒａｔｉｏｎ ｏｆ ａ ｈｅｉｇｈｔ⁃ｌｉｍｉｔｅｄ ｔｒｅｅ 算法 ５） ～１６）行仿照 Ｄｉｊｋｓｔｒａ 算法，构造一棵限 高的最小权值树，但是这棵树并不是图 Ｇ 的生成 树，因为部分节点虽然在离 Ｓｉｎｋ 跳数比较近，但是 在仿 Ｄｉｊｋｓｔｒａ 算法中却不会被选中．比如：在图 １ 中， 节点 ｄ 虽然可以两跳路径〈ｄ，ｒ，Ｒ〉到达 Ｒ，但是它的 路径权值要大于路径〈ｄ，Ｓｊ，…，Ｓｉ，Ｒ〉的权值，所以 ｄ 不会被加入到路径〈 ｄ，ｒ，Ｒ〉中．由于树高的限制， 可能〈 ｄ ，Ｓｊ，…，Ｓｉ，Ｒ〉超过了高度限制，所以 ｄ 也不 能加入到〈Ｓｊ，…，Ｓｉ，Ｒ〉构成路径〈ｄ，Ｓｊ，…，Ｓｉ，Ｒ 〉． 算法 １７） ～ ２７） 行使用了一个数据结构队列 Ｑ 来对图 Ｇ 进行层遍历，用 ｄａｄ１（ ｕ）表示在节点 ｕ 在 层遍历中的父亲节点， ｈｏｐｓ （ ｕ） 表示节点 ｕ 距离 Ｓｉｎｋ 的最小跳数． 算法 ２８） ～ ４０） 行，每个在仿 Ｄｉｊｋｓｔｒａ 算法运行 后仍然为“ ｏｆｆｔｒｅｅ” 状态的节点，启发式地寻找一条 满足限高的最小加权路径到达 Ｓｉｎｋ，并更改相应节 点的路径权值．其中算法 ２９） ～ ３６）行，“ ｏｆｆｔｒｅｅ”状态 的节点寻找一条满足限高的最小加权路径，并将路 径上的节点 ｐｕｓｈ 到一个堆栈中．算法 ３７） ～ ３９）行， 更改新路径上新加进节点的权值． ３ 仿真实验与结果分析 在仿真实验中，将 ＨＬＣＷＧＣ 算法与其他 ３ 种算 法 ＣＷＧＣ、ＨＬＭＳＣ⁃ＥＷＡＲＥ、ＨＬＭＳＣ⁃ＳＰＴ 进行比较． ＣＷＧＣ 不考虑延时的约束，与 ＨＬＣＷＧＣ 算法一样， 采用贪婪策略选取节点，但是生成网络骨干的方法 与 ＨＬＣＷＧＣ 不同．ＨＬＭＳＣ＿ＳＰＴ 中源节点采样到数 据都通过最小路径传输到 Ｓｉｎｋ，但是采取一种贪婪 策略［５］选取源节点．ＨＬＭＳＣ⁃ＥＷＡＲＥ 是考虑延时约 束后的 ＭＳＣ 算法，使用贪婪策略［５］ 选取源节点，但 是采取 ＨＬＳＰＴ 算法生成的限高加权树传输数据．在 网络最大时延和网络生命周期 ２ 个评价标准下评估 算 法 ＨＬＣＷＧＣ、 ＣＷＧＣ、 ＨＬＭＳＣ⁃ＥＷＡＲＥ、 ＨＬＭＳＣ⁃ ＳＰＴ． 假设每个节点的能量初始为 ２０ Ｊ， 各种参数设 置为 ｅｔ ＝ ５０ ｎＪ／ ｂｉｔ、 ｂ ＝ １００ ｐＪ／ ｍ ４ 、 α ＝ ４、 ｅｒ ＝ １５０ ｎＪ／ ｂｉｔ、 ｅｓ ＝ １５０ ｎＪ／ ｂｉｔ； 数 据 的 采 样 频 率 为 １０ ｋＢ ／ ｓ ［ １６ ］ ．节点的感知半径为 Ｒｓ ＝ ２０ ｍ，传输半径 为 Ｒｃ ＝ ４０ ｍ．假设网络生命周期上界为 ＬＬＰ ，其大小 可以采用枚举的方法来获取．所有节点随机地散布 在 １００ ｍ×１００ ｍ 的区域内，Ｓｉｎｋ 节点位于区域的中心． 实验 １ 测量 ＨＬＣＷＧＣ 算法与 τ 的关系．固定 网络中传感器节点数为 ６０， 目标数为 ２０， 取 τ ＝ ０．１％、０．２％、０．４％、０．６％、０．８％、１％ＬＬＰ时，设置网络 时延上限 Ｈ 为 ２０ 和 １０ 时，得到的结果绘制成图 ２． 图 ２ ＨＬＣＷＧＣ 算法生命周期与 τ 的关系 Ｆｉｇ．２ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｏｆ ＨＬＣＷＧＣ ａｌｇｏｒｉｔｈｍ’ ｓ ｌｉｆｅ⁃ ｔｉｍｅ ｗｉｔｈ τ 第 ４ 期 梁俊斌，等：带时延约束的连通目标覆盖最大化生命周期问题 ·３２３·