第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 连通之外，还需要考虑数据的时延到目前为止，虽第 ８ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．４ ２０１３ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０４０３０ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３０６０３．１６０１．００３．ｈｔｍｌ 带时延约束的连通目标覆盖最大化生命周期问题 梁俊斌１，２ ，刘明２ （１． 广西大学 计算机与电子信息学院，广西 南宁 ５３０００４； ２． 中南大学 信息科学与工程学院，湖南 长沙 ４１００８３） 摘 要：在无线传感器网络中，如何确保网络服务质量（如覆盖、连通）同时最大化网络生命周期是研究的热点和难 点．在延时敏感的应用（如火灾、爆炸等灾害监测）中，传感器节点必须在有限的时间内传送它们的数据到汇聚节点． 为了研究这种应用下的连通目标覆盖，提出了一种带时延约束的连通目标覆盖问题（ＤＣＣＴＣ）．首先，将 ＤＣＣＴＣ 建模 成为限高的最大覆盖树问题（ＨＬＭＣＴ），并证明它是 ＮＰ⁃Ｃｏｍｐｌｅｔｅ 的．然后，设计了一种快速启发式算法 ＨＬＣＷＧＣ 求 解 ＨＬＭＣＴ 问题．仿真实验和理论证明，ＨＬＣＷＧＣ 在时延约束下获得的网络生命周期比已有的算法要好．具有较高的 应用价值和理论意义． 关键词：无线传感器网络；连通目标覆盖；最大化生命周期；时延约束；能量有效 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０４⁃３１９⁃０８ 中文引用格式：梁俊斌，刘明．带时延约束的连通目标覆盖最大化生命周期问题［Ｊ］． 智能系统学报，２０１３， ８（４）：３１９⁃３２５． 英文引用格式：ＬＩＡＮＧ Ｊｕｎｂｉｎ，ＬＩＵ Ｍｉｎｇ． Ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ ｆｏｒ ｄｅｌａｙ ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓ⁃ ａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（４）： ３１９⁃３２５． Ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ ｆｏｒ ｄｅｌａｙ ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ＬＩＡＮＧ Ｊｕｎｂｉｎ １，２ ， ＬＩＵ Ｍｉｎｇ ２ （１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃ Ｉｎｆｏｒｍａｔｉｏｎ， Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｎａｎｎｉｎｇ ５３０００４， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｈａｎｇｓｈａ ４１００８３， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ： Ｔｈｅ ｉｓｓｕｅ ｏｆ ｇｕａｒａｎｔｙｉｎｇ ｔｈｅ ＱｏＳ （ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ， ｎｅｔｗｏｒｋ ｃｏｎｎｅｃｔｉｖｉｔｙ， ｅｔｃ．）， ａｎｄ ｓｉｍｕｌｔａｎｅｏｕｓｌｙ ｍａｘｉｍｉｚｉｎｇ ｔｈｅ ｌｉｆｅｔｉｍｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｉｓ ａ ｈｏｔ ｔｏｐｉｃ， ｙｅｔ ｄｉｆｆｉｃｕｌｔ ｓｕｂｊｅｃｔ ｏｆ ｓｔｕｄｙ． Ｉｎ ｓｏｍｅ ｄｅｌａｙ⁃ｓｅｎｓｉ⁃ ｔｉｖｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ， ｓｅｎｓｏｒｓ ｍｕｓｔ ｔｒａｎｓｍｉｔ ｄａｔａ ｔｏ ｓｉｎｋ⁃ｎｏｄｅ ｗｉｔｈｉｎ ａ ｌｉｍｉｔｅｄ ｔｉｍｅ ｉｎ ｏｒｄｅｒ ｔｏ ｍｏｎｉｔｏｒ ｔｈｅ ｃｒｉｔｉｃａｌ ｐｈｙｓｉｃａｌ ｅｎｖｉｒｏｎｍｅｎｔ （ｆｉｒｅｓ， ｅｘｐｌｏｓｉｏｎｓ， ｅｔｃ．）． Ｔｏ ｓｔｕｄｙ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ ｉｎ ｓｕｃｈ ｄｅｌａｙ⁃ｓｅｎｓｉｔｉｖｅ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ， ｗｅ ｐｒｏｐｏｓｅ ｔｏ ｅｘａｍｉｎｅ ｔｈｅ ｄｅｌａｙ⁃ｃｏｎｓｔｒａｉｎｔ ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ （ＤＣＣＴＣ） ｐｒｏｂｌｅｍ． Ｔｈｅ ｓｔｕｄｙ， ｓｐｅｃｉｆｉｃａｌｌｙ， ｉｎｃｌｕｄｅｓ ｏｆ： １） ｍｏｄｅｌｌｉｎｇ ＤＣＣＴＣ ｐｒｏｂｌｅｍ ａｓ ａ Ｈｅｉｇｈｔ Ｌｉｍｉｔｅｄ Ｍａｘｉｍｕｍ Ｃｏｖｅｒ Ｔｒｅｅ （ＨＬＭＣＴ） ｐｒｏｂ⁃ ｌｅｍ ａｎｄ ｐｒｏｖｉｎｇ ｉｔ ｉｓ ＮＰ⁃ｃｏｍｐｌｅｔｅ ２） ｄｅｖｅｌｏｐｐｉｎｇ ａ ｆａｓｔ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ， ｎａｍｅｄ ＨＬＣＷＧＣ（ｈｅｉｇｈｔ⁃ｌｉｍｉｔｅｄ ｃｏｍ⁃ ｍｕｎｉｃａｔｉｏｎ ｗｅｉｇｈｔｅｄ ｇｒｅｅｄｙ ｃｏｖｅｒ） ｔｏ ｓｏｌｖｅ ｔｈｅ ＨＬＭＣＴ ｐｒｏｂｌｅｍ． Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ａｎｄ ｔｈｅｏｒｅｔｉｃａｌ ｒｅｓｅａｒｃｈｅｓ ｓｈｏｗ ｔｈａｔ ＨＬＣＷＧＣ ａｌｇｏｒｉｔｈｍ ｉｓ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｉｎ ｔｈｅ ｄｅｌａｙ⁃ｃｏｎｓｔｒａｉｎｔ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ． Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ； ｃｏｎｎｅｃｔｅｄ ｔａｒｇｅｔ ｃｏｖｅｒａｇｅ； ｌｉｆｅｔｉｍｅ ｍａｘｉｍｉｚａｔｉｏｎ； ｄｅｌａｙ ｃｏｎｓｔｒａｉｎｔ； ｅｎｅｒｇｙ ｅｆ⁃ ｆｉｃｉｅｎｃｙ 收稿日期：２０１３⁃０４⁃１５． 网络出版日期：２０１３⁃０６⁃０３． 基金项目：国家自然科学基金资助项目（６１１０３２４５）；广西自然科学基 金资助项目（２０１２ＧＸＮＳＦＢＡ０５３１６３）． 通信作者：刘明． Ｅ⁃ｍａｉｌ：２５８１８７０６９＠ ｑｑ．ｃｏｍ． 无 线 传 感 器 网 络 （ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ， ＷＳＮ）是由部署在监测区域内大量的廉价微型传感 器节点，通过无线通信方式形成的一个多跳的自组 织网络系统［１⁃２］ ．在环境监测、军事等许多应用中，无 线传感器网络的部署就是为了使得目标能够尽可能 长地被持续监测且节点感知的数据有效传送到汇聚 节点，即连通目标覆盖问题．此外，在灾害监测等应 用中，如火情监测、化学品监测等，传感器节点必须 在有限的时间内将它们的数据传送到汇聚节点，否 则将有可能导致网络失效．在这种时延敏感的无线 传感器网络应用中，除了需要考虑目标覆盖和网络 连通之外，还需要考虑数据的时延．到目前为止，虽