論文目錄 | |
Abstract | 第1-6頁 |
摘要 | 第6-12頁 |
LIST OF FIGURES | 第12-14頁 |
LIST OF TABLES | 第14-15頁 |
CHAPTER 1 INTRODUCTION | 第15-19頁 |
1.1 Wireless Sensor Networks | 第15-16頁 |
1.2 Topology Control | 第16-17頁 |
1.3 Contributions and prior publications | 第17-18頁 |
1.4 Outline | 第18-19頁 |
CHAPTER 2 BACKGROUND ON GRAPHS AND NETWORK MODEL | 第19-23頁 |
2.1 Background on Graphs | 第19-21頁 |
2.1.1 K-vertex connectivity | 第20頁 |
2.1.2 K-edge connectivity | 第20-21頁 |
2.2 Network model | 第21-23頁 |
CHAPTER 3 RELATED WORKS ON TOPOLOGY CONTROL IN WIRELESS SENSOR NETWORKS | 第23-31頁 |
3.1 Yaop,k algorithm | 第23-24頁 |
3.2 CBTC(α)algorithm | 第24-26頁 |
3.3 LMST algorithm | 第26-27頁 |
3.4 K-UPVCS algorithm | 第27-28頁 |
3.5 TRT algorithm | 第28-29頁 |
3.6 FLSSk algorithm | 第29頁 |
3.7 LTRT algorithm | 第29-31頁 |
CHAPTER 4 SFL:simple Fault-tolerant Local Topology Control Algorithm | 第31-43頁 |
4.1 LTRT:Local Tree-Based Reliable | 第31-32頁 |
4.1.1 LTRT algorithm | 第31-32頁 |
4.2 SFL:Simple Fault-Tolerant Local Topology Control Algorithm | 第32-33頁 |
4.2.1 SFL algorithm | 第33頁 |
4.3 Complexity analysis | 第33-34頁 |
4.4 k-edge connectivity | 第34-35頁 |
4.5 Maintenance phase | 第35頁 |
4.6 Performance evaluation | 第35-42頁 |
4.6.1 Simulation environment | 第35-37頁 |
4.6.2 Simulation results and analysis | 第37-42頁 |
4.7 Conclusion and future work | 第42-43頁 |
CHAPTER 5 Comparison of Max-flow algorithm for k-vertex problem | 第43-63頁 |
5.1 Related Works and Backgrounds for Max-flow algorithms | 第43-45頁 |
5.1.1 For the k-vertex connectivity algorithms | 第43-44頁 |
5.1.2 The max-flow/min-cut algorithms | 第44-45頁 |
5.2 Description of Max-flow/Min-cut algorithms | 第45-51頁 |
5.2.1 Dinic algorithm | 第45-47頁 |
5.2.2 Goldbereg-style algorithm | 第47-50頁 |
5.2.3 Pseudo-flow algorithm | 第50-51頁 |
5.3 Applications of Max-Flow/Min-cut | 第51-55頁 |
5.3.1 Edge-Disjoint Paths | 第51-52頁 |
5.3.2 Vertex Capacities and Vertex-Disjoint Paths | 第52頁 |
5.3.3 Maximum Matching in Bipartite Graphs | 第52-53頁 |
5.3.4 Binary Assignment Problems | 第53-54頁 |
5.3.5 Other applications | 第54-55頁 |
5.4 Adaptation of max-flow algorithms to solve k-vertex connectivity problem | 第55-56頁 |
5.4.1 Adaptation of max-flow algorithms | 第55-56頁 |
5.5 Experimental Tests on k-vertex connectivity | 第56-62頁 |
5.5.1 Implementation | 第56頁 |
5.5.2 Computing Environment | 第56頁 |
5.5.3 Problem Classes | 第56-57頁 |
5.5.4 Testing Methodology | 第57頁 |
5.5.5 Results and Analysis | 第57-62頁 |
5.6 Conclusion and future work | 第62-63頁 |
Conclusions | 第63-65頁 |
Contributions | 第63頁 |
Open Questions and future work | 第63-65頁 |
REFERENCES | 第65-70頁 |
ACKNOWLEDGEMENTS | 第70頁 |