[1]梁俊斌,刘明.带时延约束的连通目标覆盖最大化生命周期问题[J].智能系统学报,2013,8(4):319-326.[doi:10.3969/j.issn.1673-4785.201304030]
　LIANG Junbin,LIU Ming.Lifetime maximization for delay constraint connected target coverage[J].CAAI Transactions on Intelligent Systems,2013,8(4):319-326.[doi:10.3969/j.issn.1673-4785.201304030]
点击复制

带时延约束的连通目标覆盖最大化生命周期问题

《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷: 8 期数: 2013年第4期 页码: 319-326 栏目: 学术论文—人工智能基础 出版日期: 2013-08-25
Title:
Lifetime maximization for delay constraint connected target coverage
文章编号:
1673-4785(2013)04-319-08
作者:
梁俊斌1,2，刘明2
1. 广西大学 计算机与电子信息学院，广西 南宁 530004； 2. 中南大学 信息科学与工程学院，湖南 长沙 410083
Author(s):
LIANG Junbin1,2， LIU Ming2
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
关键词:
无线传感器网络; 连通目标覆盖; 最大化生命周期; 时延约束; 能量有效
Keywords:
wireless sensor networks;  connected target coverage;  lifetime maximization;  delay constraint;  energy efficiency
分类号:
TP393
DOI:
10.3969/j.issn.1673-4785.201304030
文献标志码:
A
摘要:
在无线传感器网络中，如何确保网络服务质量（如覆盖、连通）同时最大化网络生命周期是研究的热点和难点.在延时敏感的应用（如火灾、爆炸等灾害监测）中，传感器节点必须在有限的时间内传送它们的数据到汇聚节点.为了研究这种应用下的连通目标覆盖，提出了一种带时延约束的连通目标覆盖问题(DCCTC).首先，将DCCTC建模成为限高的最大覆盖树问题(HLMCT)，并证明它是NP-Complete的.然后，设计了一种快速启发式算法HLCWGC求解HLMCT问题.仿真实验和理论证明，HLCWGC在时延约束下获得的网络生命周期比已有的算法要好.具有较高的应用价值和理论意义.
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-sensitive 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) problem and proving it is NP-complete 2) developping a fast heuristic algorithm, named HLCWGC(height-limited communication 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.
参考文献/References:
［1］任丰原，黄海宁，林闯. 无线传感器网络［J］. 软件学报，2003，14(7): 1282-1291.
????????? REN Fengyuan, HUANG Haining, LIN Chuang. Wireless sensor networks［J］. Journal of Software, 2003，14(7): 1282-1291.
［2］崔莉，鞠海玲，苗勇，等. 无线传感器网络研究进展［J］. 计算机研究与发展， 2005, 42 (1): 163-174.
????????? CUI Li, JU Hailing, MIAO Yong, et al. Overview of wireless sensor networks［J］. Journal of Computer Research and Development, 2005, 42 (1): 163-174.
［3］SLIJEPCEVIC S, POTKONJAK M. Power efficient organization of wireless sensor networks［C］//IEEE International Conference of Communications(ICC). Beijing， China, 2001: 472-476.
［4］CARDEI M, DU Dingzhu. Improving wireless sensor network lifetime through power aware organization［J］. Wireless Networks, 2005, 11(3): 333-340.
［5］CARDEI M, THAI M T, LI Yingshu, et al. Energy-efficient target coverage in wireless sensor networks［C］//24th IEEE International Conference on Computer Communications(INFOCOM). Miami, USA, 2005: 1976-1984.
［6］CARDEI M, WU Jie, LU Mingming, et al. Maximum network lifetime in wireless sensor networks with adjustable sensing ranges［C］//IEEE International Conference of Wireless and Mobile Computing, Networking and Communications (WiMob). Montreal, Canada, 2005: 1-5.
［7］LU Mingming, WU Jie, CARDEI M, et al. Energy-efficient connected coverage of discrete targets in wireless sensor netorks［C］//International Conference of Computer Networks and Mobile Computing (ICCNMC). Zhangjiajie, China, 2005: 137-147.
［8］ZHAO Qun, GURUSAMY M. Lifetime maximization using observation time scheduling in multi-hop sensor networks［C］//IEEE/CreateNet International Workshop on Broadband Advanced Sensor Networks(BroadNets). Boston, USA, 2005: 1-5.
［9］ZHAO Qun, GURUSAMY M. Lifetime maximization for connected target coverage in wireless sensor networks［J］. IEEE/ACM Transactions on Networking, 2008, 16(6): 1378-1391.
［10］LI Deying, CAO Jiannong, LIU Ming, et al. K-connected target coverage problem in wireless sensor networks［J］. Lecture Notes in Computer Science, 2007, 46(1): 20-31.
［11］WU Lidong, DU Hongwei, WU Weili, et al. Approximations for minimum connected sensor cover［C］//32nd IEEE International Conference on Computer Communications(INFOCOM). Turin, Italy, 2013: 1424-1432.
［12］GU Yu, LIU Hengchang, ZHAO Baohua. Target coverage with QoS requirements in wireless sensor networks［C］//IEEE International Conference on Intelligent Pervasive Computing(IPC). Jeju Island, Korea, 2007: 35-38.
［13］BOUKERCHE A, PAZZI R, ARAUJO R. A fast and reliable protocol for wireless sensor networks in critical conditions monitoring applications［C］//7th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM). Venice, Italy, 2004: 157-164.
［14］YU Zuoming, TENG Jin, LI Xinfeng. On wireless network coverage in bounded areas［C］//32nd IEEE International Conference on Computer Communications(INFOCOM). Turin, Italy, 2013: 1752-1760.
［15］AREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-Completeness［M］. New York: W.H.Freeman, 1979: 210-216.
［16］CHANG J H, TASSIULAS L. Maximum lifetime routing in wireless sensor networks［J］. IEEE/ACM Transactions on Networking, 2004, 12(4): 609-619.
相似文献/References:
[1]毕晓君,张艳双.基于免疫算法的无线传感器网络路由算法[J].智能系统学报,2009,4(1):67.
　BI Xiao-jun,ZHANG Yan-shuang.A routing algorithm for wireless sensor networks based on an immune algorithm[J].CAAI Transactions on Intelligent Systems,2009,4():67.
[2]陈珍焰,刘贵喜.移动节点的LEACH改进型算法[J].智能系统学报,2008,3(2):140.
　CHEN Zhen-yan,LIU Gui-xi.An improved LEACH algorithm based on mobile sensor nodes[J].CAAI Transactions on Intelligent Systems,2008,3():140.
[3]海 丹,李 勇,张 辉,等.无线传感器网络环境下基于粒子滤波的移动机器人SLAM算法[J].智能系统学报,2010,5(5):425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
　HAI Dan,LI Yong,ZHANG Hui,et al.Simultaneous localization and mapping of a mobile robot in wireless sensor networks based on particle filtering[J].CAAI Transactions on Intelligent Systems,2010,5():425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
[4]何敏,赵东风,保利勇,等.一种能量有效的无线传感器网络轮询接入控制协议[J].智能系统学报,2012,7(3):265.
　HE Min,ZHAO Dongfeng,BAO Liyong,et al.An energyefficiency polling access control protocol for wireless sensor networks[J].CAAI Transactions on Intelligent Systems,2012,7():265.
[5]叶玲,李太华,代学武.无线传感器网络环境下基于卡尔曼滤波的PTP协议[J].智能系统学报,2012,7(6):518.
　YE Ling,LI Taihua,DAI Xuewu.Kalman filtering based precision time protocol (PTP) in wireless sensor networks[J].CAAI Transactions on Intelligent Systems,2012,7():518.
[6]余华平,郭梅.面向管道系统的无线传感器网络三维节点部署算法[J].智能系统学报,2013,8(4):333.[doi:10.3969/j.issn.1673-4785.201304025]
　YU Huaping,GUO Mei.The research of three-dimensional node deployment of wireless sensor network for pipeline systems[J].CAAI Transactions on Intelligent Systems,2013,8():333.[doi:10.3969/j.issn.1673-4785.201304025]
[7]程磊,周明达,吴怀宇,等.无线传感器环境下粒子群优化的多机器人协同定位研究[J].智能系统学报,2015,10(1):138.[doi:10.3969/j.issn.1673-4785.201310067]
　CHENG Lei,ZHOU Mingda,WU Huaiyu,et al.Cooperative multi-robot localization based on particle swarm optimization in the environment of wireless sensor[J].CAAI Transactions on Intelligent Systems,2015,10():138.[doi:10.3969/j.issn.1673-4785.201310067]
[8]杨玉景,黄艺文,李太华,等.多跳无线传感器网络下基于KF优化的PTP协议[J].智能系统学报,2014,9(2):174.[doi:10.3969/j.issn.1673-4785.201310025]
　YANG Yujing,HUANG Yiwen,LI Taihua,et al.Precision time protocol (PTP) on the basis of Kalman filtering in the multi-hop wireless sensor network[J].CAAI Transactions on Intelligent Systems,2014,9():174.[doi:10.3969/j.issn.1673-4785.201310025]
[9]官铮,邹丹,丁洪伟,等.并行调度两级轮询控制传感器网络MAC协议分析[J].智能系统学报,2014,9(4):438.[doi:10.3969/j.issn.1673-4785.201304023]
　GUAN Zheng,ZOU Dan,DING Hongwei,et al.Study on parallel two-level polling control based MAC protocol for Wireless sensor networks[J].CAAI Transactions on Intelligent Systems,2014,9():438.[doi:10.3969/j.issn.1673-4785.201304023]
[10]武加文,李光辉.基于GABP-KF的WSN数据漂移盲校准算法[J].智能系统学报,2019,14(2):254.[doi:10.11992/tis.201712003]
　WU Jiawen,LI Guanghui.GABP-KF-based blind calibration algorithm of data drift in wireless sensor networks[J].CAAI Transactions on Intelligent Systems,2019,14():254.[doi:10.11992/tis.201712003]

备注/Memo

收稿日期：2013-04-15.???? 网络出版日期：2013-06-03. 
基金项目：国家自然科学基金资助项目（61103245）；广西自然科学基金资助项目（2012GXNSFBA053163）.
通信作者：刘明. E-mail：258187069@qq.com.
作者简介：
梁俊斌，男，1979年生，副教授，主要研究方向为无线传感器网络.
刘明，男，1985年生，硕士，主要研究方向为无线传感器网络.

更新日期/Last Update: 2013-09-25
Copyright © 《 智能系统学报》 编辑部
地址：（150001）黑龙江省哈尔滨市南岗区南通大街145-1号楼 电话：0451- 82534001、82518134　邮箱：tis@vip.sina.com