伊利诺伊大学的li和hou提出的drng和dlmst是两个具有代表性的基于临近图理论的功率控制算法。接近开关传感器基于临近图的功率控制算法的基本思想是:设所有节点都使用最大发射功率发射时形成的拓扑图G,按照一定的邻居判别条件Q求出该图的临近图G,最后G中的每个节点以自己所临近的最远通信结点来确定发射功率。这是一种解决接近开关功率分配问题的近似解法,考虑到无线传感器网络中两个节点形成的边是有向的,为了避免形成单向边,一般运用基于临近图的功率控制算法形成网络拓扑以后,还要进行节点之间的增册,以使最后得到的网络拓扑是双向连通的。在无线传感器网络中,基于临近图功率控制算法的作用是使节点确定自己的邻居集合,调整适当的发射功率,从而在建立起一个连通网络的同时使得能量消耗最低。经典的临近图模形有RNG、CG、DC、YC和MST等。DRNC是基于有向RNC的,DLMST是基于有向局部MST的。DRNC和DLMST能够保证网络的连通性,在接近开关平均功率和节点度等方面具有较好的性能。基于临近图的功率控制一般需要精确地位置信息,下面简单介绍DRNC算法和DLSS算法。
光电开关传感器的DRNC算法和DLSS算法是两种从临近图观点考虑拓扑问题的算法,是一种提出比较早的功率控制算法,两者均以经典的临近图RNC和LMST等理论为基础,全面考虑了连通性和双向连通性问题。
在DLSS算法中,假设节点U及其可达邻居集合G,将P到所有可达邻居节点的边以权重为标准按升序排列;依次取出这些边,直到U与所有可达邻居节点相连通或者通过其他节连通;最后,与U直接连通的节点构成U的邻居集合,从接近开关图论的观点看,DLSS算法等价于G基础上的本地最小生成树的计算。经过DRNG或DLSS算法后,节点U确定了自己的邻居集合,然后将发射半径调整为最远邻居节点的距离,进一步通过对拓扑图的边进行增删,使得网络达到双向连通。
DRNG算法和DLSS算法着重考虑了网络的连通性,充分利用了邻居图理论,是无线传感器网络中的经典算法,以原始网络拓扑双向连通为前提,保证优化后的拓扑也是双向连通的。
此外,微软亚洲研究院的wattenhofer等人提出了XTC算法对接近开关传感器节点没有太高的要求,对部署环境也没有过强的假设,提供了一个面向简单、使用的研究方向。XTC代表了功率控制的发展趋势。 |