[1]梁俊斌,刘明.带时延约束的连通目标覆盖最大化生命周期问题[J].智能系统学报,2013,8(04):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(04):319-326.[doi:10.3969/j.issn.1673-4785.201304030]
点击复制

带时延约束的连通目标覆盖最大化生命周期问题(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第8卷
期数:
2013年04期
页码:
319-326
栏目:
出版日期:
2013-08-25

文章信息/Info

Title:
Lifetime maximization for delay constraint connected target coverage
文章编号:
1673-4785(2013)04-319-08
作者:
梁俊斌12刘明2
1. 广西大学 计算机与电子信息学院,广西 南宁 530004; 2. 中南大学 信息科学与工程学院,湖南 长沙 410083
Author(s):
LIANG Junbin12 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(01):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(04):67.
[2]陈珍焰,刘贵喜.移动节点的LEACH改进型算法[J].智能系统学报,2008,3(02):140.
 CHEN Zhen-yan,LIU Gui-xi.An improved LEACH algorithm based on mobile sensor nodes[J].CAAI Transactions on Intelligent Systems,2008,3(04):140.
[3]海 丹,李 勇,张 辉,等.无线传感器网络环境下基于粒子滤波的移动机器人SLAM算法[J].智能系统学报,2010,5(05):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(04):425.[doi:10.3969/j.issn.1673-4785.2010.05.008]
[4]何敏,赵东风,保利勇,等.一种能量有效的无线传感器网络轮询接入控制协议[J].智能系统学报,2012,7(03):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(04):265.
[5]叶玲,李太华,代学武.无线传感器网络环境下基于卡尔曼滤波的PTP协议[J].智能系统学报,2012,7(06):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(04):518.
[6]余华平,郭梅.面向管道系统的无线传感器网络三维节点部署算法[J].智能系统学报,2013,8(04):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(04):333.[doi:10.3969/j.issn.1673-4785.201304025]
[7]程磊,周明达,吴怀宇,等.无线传感器环境下粒子群优化的多机器人协同定位研究[J].智能系统学报,2015,10(01):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(04):138.[doi:10.3969/j.issn.1673-4785.201310067]
[8]杨玉景,黄艺文,李太华,等.多跳无线传感器网络下基于KF优化的PTP协议[J].智能系统学报,2014,9(02):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(04):174.[doi:10.3969/j.issn.1673-4785.201310025]
[9]官铮,邹丹,丁洪伟,等.并行调度两级轮询控制传感器网络MAC协议分析[J].智能系统学报,2014,9(04):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(04):438.[doi:10.3969/j.issn.1673-4785.201304023]
[10]武加文,李光辉.基于GABP-KF的WSN数据漂移盲校准算法[J].智能系统学报,2019,14(02):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(04):254.[doi:10.11992/tis.201712003]

备注/Memo

备注/Memo:
收稿日期:2013-04-15.     网络出版日期:2013-06-03. 
基金项目:国家自然科学基金资助项目(61103245);广西自然科学基金资助项目(2012GXNSFBA053163).
通信作者:刘明. E-mail:258187069@qq.com.
作者简介:
梁俊斌,男,1979年生,副教授,主要研究方向为无线传感器网络.
刘明,男,1985年生,硕士,主要研究方向为无线传感器网络.
更新日期/Last Update: 2013-09-25