| Abstract | 第5页 |
| 摘要 | 第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页 |
