作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (1): 111-115. doi: 10.3969/j.issn.1000-3428.2013.01.024

• 网络与通信 • 上一篇    下一篇

无线传感器网络中目标覆盖图的分解

张红武 1a,张 聪 1a,丰洪才 1a,杨博斐 2,刘昌华 1a,袁 操 1a,夏祥胜 1a,管 华 1b   

  1. (1. 武汉工业学院 a. 数学与计算机学院;b. 现代教育技术中心,武汉 430023   2. 浙江大学信息与电子工程系,杭州 310058)

  • 收稿日期:2012-02-29 修回日期:2012-06-08 出版日期:2013-01-15 发布日期:2013-01-13
  • 作者简介:张红武(1973-),男,讲师、博士,主研方向:无线传感器网络,无线通信与网络;张 聪、丰洪才,教授、博士;杨博斐,本科生;刘昌华,副教授、博士;袁 操、夏祥胜,讲师、博士;管 华,讲师、博士研究生
  • 基金资助:
    湖北省自然科学基金资助项目“流控制传输协议的拥塞控制新型计算模型研究”(09ABA007, 2009chb008);湖北省教育厅科研基金资助项目“视频传输自适应可用带宽算法的研究与应用”(D20101703)

Decomposition of Target-coverage Graph in Wireless Sensor Network

ZHANG Hong-wu 1a, ZHANG Cong 1a, FENG Hong-cai 1a, YANG Bo-fei 2, LIU Chang-hua 1a, YUAN Cao 1a, XIA Xiang-sheng 1a, GUAN Hua 1b   

  1. (1a. School of Mathematic & Computer Science; 1b. Center of Modern Educational Technology, Wuhan Polytechnic University, Wuhan 430023, China; 2. Department of Information Science & Electronic Engineering, Zhejiang University, Hangzhou 310058, China)
  • Received:2012-02-29 Revised:2012-06-08 Online:2013-01-15 Published:2013-01-13

摘要: 在无线传感器网络中,为降低目标覆盖问题的复杂度,给出3种减小网络规模的方法,即删除冗余节点、删除冗余目标、将目标覆盖图分解成多个独立子图。分别证明这3种方法的正确性,并提出构造独立子图算法。仿真结果表明,该算法可以减少30%的网络规模,并降低目标覆盖问题的算法复杂度。

关键词: 分解, 冗余节点, 冗余目标, 独立子图, 网络规模

Abstract: In order to reduce the algorithm complexity of the target coverage problem in Wireless Sensor Network(WSN), three approaches are designed to decrease the network scale. Of the three approaches, one is deleting the redundant sensor nodes, another is removing the redundant targets, and the third is decomposing the target-coverage graph into independent sub-graphs. It proves that the three approaches are correct, and presents the Construct Independent Sub Graph Algorithm(CISGA) to divide target- coverage graph. Measurement results show that CISGA can reduce 30% of network scale and greatly reduce the algorithm complexity of target coverage problem.

Key words: decomposition, redundant node, redundant target, independent sub-graph, network scale

中图分类号: