传感网中的动态Delauanay三角剖分算法

摘要

几何路由协议受益于局部Delaunay三角剖分,因为Delaunay三角剖分可以保证消息转发的可达性和限制路由长度的界.本文提出一种构造无线传感网中Delaunay三角剖分的局部算法.此算法不但考虑了静态情况,而且考虑了允许节点动态地加入和退出网络的动态情况.在静态情况和动态情况下,算法的通信开销都是O(nlogn)位.因此,此算法可以应用于节点可以动态加入和退出的无线传感网.本文还证明了算法的正确性.