Graph Based Algorithms for Topology Control in Wireless Sensor Network

摘要

近年来,图算法(graph algorithms)已成为强大的技术用拓扑控制中以解决在无线传感器网络诸多问题。本论文的目标是应用图算法研究无线传感器网络拓扑控制约束问题。
　　本论文提出的技术和理论成果大大降低了无线传感器网络拓扑控制算法所需的其他开销信息和时间复杂度。本文成果也有助于在三维空间和移动无线传感器网络研究拓扑控制算法。以前同类算法明显更多关注拓扑控制能耗,没有注意到时间复杂度,这是使用计算有限的小型设备的应该考虑的关键问题。为了可靠的无线多跳网络,本文提出一个简单的容错局部拓扑控制算法(SFL),它是对LTRT算法的改进,本文方法考虑了不同的拓扑控制设计和无线传感器网络的相关因素之间的平衡。
　　本文的算法对所有限制条件下的拓扑控制进行编码,如:分布式算法,本地信息,位置信息,K-连通,覆盖范围,节点度小,链接双方向性,简单,消息复杂度低,能源效率,测量器,收敛时间和内存消耗。在SFL,每个节点建立自己的SFL,运用LMST k倍达到k-边连通和在本地化的方式维护网络连接,来优化其传输功率。本文讨论了可以使用的几种平滑选项。实验结果表明,SFL在复杂度低的情况下比LTRT具有更好的性能。
　　在论文的最后针对K-顶点连通性问题解决了的网络设计的效率。我们比较几个标准min-cut/max-flow算法的运行时间。用一个典型的图论标准来检查这些算法。在大多数情况下pseudo-flow算法工作比别人快几倍。
　　论文主要工作如下:
　　1.第一部分
　　本文第一个贡献是为可靠的无线多跳网络提出一个简单的容错局部拓扑控制(SFL)算法.一个改进的LTRT算法。在SFL中,每个节点建立自己的SFL,运用LMST k倍,达到k-边连通和在本地化的方式维护网络连接,来优化其传输功率。SFL和LTRT分享所有重要的属性,本文算法优于LTRT,是以时间复杂度为O(km)和较低的开销消息建立K-连接的拓扑结构,仿真结果表明了SFL算法的效率较高。
　　最近,无线网络,特别是无线传感器网络的发展已经吸引了很多的研究人员,因为其实用、低成本和现代技术的灵活性和其广泛的从城市环境到个人网络可用性。相比之下,出现了新的挑战,能源效率,延长网络的寿命和容量是一些已经解决的重大问题。因此,无线传感器网络可以变得更节能的途径之一是通过减少能源使用的拓扑控制。
　　拓扑控制是某些节点参数和操作模式的重组和管理,从时间,以时间来修改网络的拓扑结构,延长其寿命,降低能耗和提高网络容量的目标,同时也维护重要特征,例如网络连通性和传感器覆盖。拓扑控制是由两个主要阶段:建设阶段和维护阶段。其主要目标是修改初始的最大功率拓扑通过使用适当的发射功率,以减少能源消耗,以延长寿命,防止干扰,提高空间复用和减轻了MAC_Level的介质,以提高网络容量,同时保持重要特征,如连通性和覆盖范围。拓扑控制的设计必须考虑到考虑一些要求方面,如:
　　分布式算法:集中式拓扑控制机制需要全球性的信息,因此实施时,非常昂贵。
　　本地信息:节点应该能够使本地拓扑控制决策。这降低了能源成本,使可伸缩的机制。
　　地点信息:需要额外的硬件,如GPS设备,或像本地化协议在美元和能源消耗方面的成本增加的支持机制。
　　K-连通性:必须是K-连接,因此所有活动节点可以互相交换讯息以及与sink节点的K冗余路径。
　　覆盖范围:减少拓扑必须占地面积虽然有许多的兴趣主动节点。
　　一个小节点度:小的节点度是指一个邻居的小数目,这可能会产生较低的碰撞和转播,节约能源。
　　链接双向的方向性:双向联系方便一些媒体访问控制(MAC)层协议适当的操作,如IEEE802.11标准,发送Request-To-Send(RTS)和Clear-To-Send(CTS),并确认在返回路径。
　　简单:拓扑控制算法必须有一个低计算复杂度,所以他们可以在无线传感器设备中运行。
　　低消息复杂度:拓扑控制机制必须与非常低的消息开销工作,所以他们是能源效率和可以运行多次作为拓扑控制周期。
　　能源效率:认为迄今为止的所有因素,并在最后一节讨论的在能源效率的问题,这是必不可少的拓扑控制机制和一般的无线传感器网络的问题。
　　测量器:减少拓扑结构应该是一个测量器的长度和跳数的单位圆盘图。一个子图G0是一个长度为图G(跳数)是否有积极的现实,任何两个节点,在G0最短路径的长度(跳数)最多的是常量X测量器在G中最短路径的长度x次(跳数)被称为常量X长度(跳数)拉伸因子。
　　收敛时间:拓扑结构和维护的过程应该放置尽可能快速地收敛后,数量有限的步骤。
　　内存消耗:无线传感器设备,经常有少量的内存。一些拓扑控制技术,可能需要相当数量的内存,这些存储预先计算的拓扑结构,如:
　　拓扑控制的主要目标是,以尽量减少每个节点的传输功率(以延长网络的寿命,增加空间重用,并减少MAC层干扰),同时保持网络连接。
　　在这本论文的一部分,我们证明了SFL保留了K-连通性和双向的方向性。SFL是改善LIRT,因此,它保持了所有的LTRT的显着特点。SFL保留k-边很容易重复的连接拓扑结构和链路删除阶段。由于LTRT的计算成本已经是很小,SFL较小节点的广播只有两个。因此,SFL,可以适用于各种类型的网络,因为它是计算成本效益,并产生高节能和可靠的传输。
　　我们通过大量的模拟来评估SFL的性能。实验表明,SFL达到相同节能性能与LTRT算法一样,但SFL优于LTRT在一个较低的计算成本和较低的开销。
　　2.第二部分
　　这一部分的目标是提供一个有根据的min-cut/max-flow算法效率的实验比较,K-顶点连通性强于K-边连通性。本论文的第一部分是专注于无线传感器网络拓扑控制,通过相关的工作,相关文献可知,FLSS节能降耗作为最佳的容错拓扑控制算法,但它具有较高的时间复杂性让它不适合小型设备如传感器网络。FLSS作为一个子路由Dinic算法来计算K-顶点的连通,因为它的时间复杂度低n√m。论文的第二个贡献是比较了几个标准k-顶点算法的运行时间。研究stat-of-art max-flow/min-cut算法;'inic','Push-relabel',和'Pseudo-flow'的实验结果表明,'Pseudo-flow'是最好的k-顶点连通性的关系问题。
　　Menger定理是第一个刻画的连通图顶点之间的独立路径数量。Menger定理的顶点连接的声明如下:设G是有限的无向图,s和t两个相邻顶点。然后,定理表明,S和T的最小顶点割的大小等于从s到t的最大数量成对的顶点独立路径。
　　顶点独立路径:如果S和T是图G的顶点,然后S和T之间的路径的集合被称为顶点独立的路径,如果没有他们两人共用一个顶点(S和T本身以外)。
　　Even和Tarjan最早提出最大流基于连通性算法。随后的结果,包括Kleitman的工作,Galil,Esfahanian和Hakimi,ftenzinger和Rao。不计算Tarjian己研究的k的实际价值,确定连接是否超过规定值的问题。
　　提出了许多算法,其中有一些众所周知的K-顶点连通性算法和max-flowmin-cu算法,显示最好的性能。
　　对于K-顶点连通性算法:
　　Gabow算法使用扩展图形需要0((n+min{k5/2,kn3/4})m)Piotr algorithm使用矩阵技术需要0(n1.575+nk2)Yuichi and Hiro algorithm性能测试使用的时间复杂度取决于指数Kmax-flow/min-cut算法性能更好的实验,找到图的连通的k-顶点连接,这是众所周知,标准的最佳此类问题的算法:Dini使用增广路径技术和时间复杂度n√mGoldbereg-style在O(nmlog(n))使用推重新标记方法Pseudo-flow在O(nmlog(n))采用归一树Boykov and Kolmogorov在O(kmn2)采用增广路径,该算法优于所有的max-flow/min-cut算法在一些计算机视觉和模式识别问题。
　　两个顶点{S,T)之间的K-顶点连通性的目的是要知道从V＼{S,T}选择的顶点的数量最少,从图中删除会破坏每一个S和T之间的路径。
　　我们的工作的重要意义在于到现在为止它被广泛接受,Dinic算法是最快的算法,由于其低的时间复杂度在k-顶点的连接问题,但其他算法:push-relabel和pseudo-flow在实践中表现优越。
　　在这一部分,研究表明,pseudo-flow的算法的运行时间是最好的大部分图形问题。
　　论文组织如下:第2章中,定义网络模型和图像上的一些背景知识,第3章中,给出了拓扑控制相关工作的概述,然后阐述SFL和LTRT的性能,在第4章,提出SFL的仿真研究;最后,提出了不同的k-顶点连通性算法的实验比较,在第5章,发现pseudo-flow算法在基准图方法优于其他max-flow/min-cut算法:在第6章说明了一些开放性的问题。

目录

文摘

英文文摘

论文说明:LIST OF FIGURES、LIST OF TABLES

CHAPTER 1 INTRODUCTION

1.1 Wireless Sensor Networks

1.2 Topology Control

1.3 Contributions and prior publications

1.4 Outline

CHAPTER 2 BACKGROUND ON GRAPHS AND NETWORK MODEL

2.1 Background on Graphs

2.1.1 k-vertex connectivity

2.1.2 k-edge connectivity

2.2 Network model

CHAPTER 3 RELATED WORKS ON TOPOLOGY CONTROL IN WIRELESS SENSOR NETWORKS

3.1 Yaop,k algorithm

3.2 CBTC (α)algorithm

3.3 LMST algorithm

3.4 K-UPVCS algorithm

3.5 TRT algorithm

3.6 FLSSk algorithm

3.7 LTRT algorithm

CHAPTER 4 SFL:simple Fault-tolerant Local Topology Control Algorithm

4.1 LTRT:Local Tree-Based Reliable

4.1.1 LTRT algorithm

4.2 SFL:Simple Fault-Tolerant Local Topology Control Algorithm

4.2.1 SFL algorithm

4.3 Complexity analysis

4.4 k-edge connectivity

4.5 Maintenance phase

4.6 Performance evaluation

4.6.1 Simulation environment

4.6.2 Simulation results and analysis

4.7 Conclusion and future work

CHAPTER 5 Comparison of Max-flow algorithm for k-vertex problem

5.1 Related Works and Backgrounds for Max-flow algorithms

5.1.1 For the k-vertex connectivity algorithms

5.1.2 The max-flow/rain-cut algorithms

5.2 Description of Max-flow/Min-cut algorithms

5.2.1 Dinic algorithm

5.2.2 Goldbereg-style algorithm

5.2.3 Pseudo-flow algorithm

5.3 Applications of Max-Flow/Min-cut

5.3.1 Edge-Disjoint Paths

5.3.2 Vertex Capacities and Vertex-Disjoint Paths

5.3.3 Maximum Matching in Bipartite Graphs

5.3.4 Binary Assignment Problems

5.3.5 Other applications

5.4 Adaptation of max-flow algorithms to solve k-vertex connectivity problem

5.4.1 Adaptation of max-flow algorithms

5.5 Experimental Tests on k-vertex connectivity

5.5.1 Implementation

5.5.2 Computing Environment

5.5.3 Problem Classes

5.5.4 Testing Methodology

5.5.5 Results and Analysis

5.6 Conclusion and future work

Conclusions

Contributions

Open Questions and future work

REFERENCES

ACKNOWLEDGEMENTS