Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (26): 76-79.DOI: 10.3778/j.issn.1002-8331.2010.26.024

• 网络、通信、安全 • Previous Articles     Next Articles

Barrier coverage based on distributed Delaunay triangulation

SUN Ji-zhong1,MA Yong-qiang1,HU Yan2,KONG Xu1   

  1. 1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031,China
    2.College of Maths,Southwest Jiaotong University,Chengdu 610031,China
  • Received:2009-11-17 Revised:2010-05-20 Online:2010-09-11 Published:2010-09-11
  • Contact: SUN Ji-zhong

分布式Delaunay三角剖分在栅栏覆盖中的应用

孙继忠1,马永强1,胡 艳2,孔 旭1   

  1. 1.西南交通大学 信息科学与技术学院,成都 610031
    2.西南交通大学 数学学院,成都 610031
  • 通讯作者: 孙继忠

Abstract: A Mutual Edge Distributed Delaunay Triangulation algorithm(MEDDEL) is proposed for wireless sensor networks,which can be run only by each node distributively with 1-hop neighborhood information.It builds MEDDEL more efficient and avoids lots of communication cost and energy consumption.Simultaneously,the support weight of MEDDEL is calculated and proved.Owing to the energy model of sensor and MEDDEL topology graph,the best-coverage-path problem is solved by a distributed Shortest travelling distance and Minimum energy consumption of Best-Coverage-Path algorithm(SMBCP) in wireless sensor network.Compared to RNG,GG,PLDEL,UDEL and DEL,the simulation results show that the best-coverage-path with the shortest travelling distance and minimum energy consumption can be found by SMBCP algorithm,in the smallest support weight of path.

Key words: wireless sensor networks, distributed Delaunay triangulation, barrier coverage, topology control

摘要: 提出了一种有效的双向边分布式造构Delaunay三角剖分拓扑图算法(MEDDEL),该算法仅利用一跳邻居节点的信息,高效构造MEDDEL拓扑图,避免了大量通信代价和能量消耗。然后给出了MEDDEL拓扑图下支撑值计算的证明。最后在传感器能量模型和MEDDEL拓扑图下,利用分布式最佳覆盖路下的最短穿越和最小能耗算法(SMBCP)解决无线传感器网络中栅栏覆盖最佳路径的问题。仿真实验结果分析表明,与RNG、GG、PLDEL、UDEL、DEL相比较,在MEDDEL拓扑结构下寻找到路径支撑值最小的情况下,运行SMBCP算法能找到最佳覆盖路径下的最短穿越路径和最小能耗路径。

关键词: 无线传感器网络, 分布式Delaunay三角剖分, 栅栏覆盖, 拓扑控制

CLC Number: