Energy-efficient Routing Schemes for Wireless Sensor Networks

無線感測網路是一種運作於有限資源下的特殊網路，它可提供多方面的網路應用，例如：移動物體的追蹤及監測環境資料等等。因為運算資源有限，為了延長無線感測網路的壽命，如何節省整體網路的電源消耗以及如何設計有效率的繞徑協定為當中兩個重要議題：尤其，在某些無線感測網路的應用環境中，感測節點必須需要傳遞監測資料到任意移動的監測人員。然而，在此動態網路拓樸的情境下，之前已經建立好的最佳傳遞路徑可能不再是最佳，甚至可能斷裂而需需要重新修護。 針對這些議題，此篇論文提出基於虛構網格的繞路演算法，研究在動態網路拓樸的感測網路中，如何有效率的傳遞資料並且減少網路的電量耗損。首先，我們提出EAGER繞路演算法，針對移動的監測人員情境設計一套新的繞路演算法，並且引入時段排程的機制控制閒置節點的能源耗損，達到可減少重新繞路頻率並降低網路節點的能源耗損。其次，我們提出TARS繞路演算法，針對移動的監測人員及監測目標的動態拓樸情境設計繞路機制，TARS融入追蹤目標的觀念使繞路更有彈性及效率；此外，TARS導入尋找捷徑的演算法以對傳遞路徑做最佳化，減少資料在路徑傳遞時所產生的能量消耗並達成有效率的資料傳遞；最後，TARS也使用時段排程方法來控制閒置節點的無線電波設備之使用，進一步節省更多電力。最後，藉由實驗模擬，相較於其他基於虛構網格的繞路演算法，本論文所設計的兩種繞路演算法不僅可以適用於移動的監測者，也可以適用在移動監測目標。並且也達到省電的目的，比其他類似的機制更有效率。Wireless sensor networks (WSNs), which are operated with strict resources, offer promise for surveillance technology including target tracking and environmental monitoring. Saving the energy resource and designing efficient routing scheme are two challenges of the operation of prolonging the life of networks. Moreover, in some sensor network applications, aggregating and delivering sensing data from targets to mobile sinks is necessary. Nevertheless, such mobility can cause the established routes non-optimal and even broken and require repeated route recovery procedures. To address this issue, we proposed relevant works based on virtual grid structure to achieve an efficient routing with mobility context. Firstly, we developed a re-routing scheme, named EAGER, with a radio-off scheduling method to achieve energy-efficient. Secondly, we presented an improved scheme, named TARS, to avoid the need of frequent rerouting. This enhanced scheme is a grid-based routing scheme dealing with the sensor networks consisting of multiple mobile targets and observers. TARS adopts the concept of tracking technology to increase the efficiency of routing procedures in the context of dynamic topology. This scheme also proposes a lightweight shortcutting approach to decrease redundant messages, so as to increase the efficiency of routing procedures and to optimize the routing paths in the context of dynamic topology. Moreover, TARS introduces a radio-off time-scheduling method to control the radio of idle nodes for saving further energy. For evaluating performance, the extensive simulations are developed to allow for the comparison of those two works with other related schemes that has been proposed, respectively. The relevant simulation results show that the two schemes are not only able to accommodate the disseminating challenges posed by mobile sinks or by mobile sinks and targets, but are also able to conserve energy more effectively than previous proposed works.Chapter 1 Introduction..... 1 1.1 Background.....1 1.2 Related Applications and Issues.....2 1.3 Contributions.....4 1.4 Organization.....5 Chapter 2 Related Work.....6 2.1 TTDD.....7 2.2 GMDQP .....7 2.3 CODE.....9 2.4 EADA.....10 2.4 Tracking Methods.....11 Chapter 3 Virtual Grid-based Structure.....13 3.1 Construction of the Virtual-Grid Structure.....13 3.2 Election of the Grid Head.....14 Chapter 4 EAGER Scheme.....17 4.1 Motivation of EAGER.....17 4.2 Architecture of EAGER.....17 4.2.1 Time-scheduling Method for the Grid Head.....17 4.2.2 Determining the exponent n of the time-scheduling equation.....20 4.2.3 Establishing an Initial Routing Path.....20 4.2.4 Handling Sink Mobility.....22 4.4 Simulation Results.....27 4.4.1 Simulation Parameters and Performance Metrics.....28 4.4.2 Total energy consumption.....29 4.4.3 Average delivery latency.....30 4.4.4 Delivery ratio.....31 4.4.5 Rerouting overheads.....32 4.5 Comparison.....33 4.5.1 Total energy consumption.....34 4.5.2 Average delivery latency.....35 4.5.3 Delivery ratio.....36 4.5 Summary.....37 Chapter 5. TARS Scheme.....40 5.1 Motivation.....40 5.2 Architecture of TARS.....42 5.2.1 Radio-Off Time-Scheduling Method.....44 5.2.2 Initial Path Setup Scheme.....47 5.2.3 Trace-announcing Routing Scheme.....49 5.2.4 Shortcutting Scheme.....55 5.2.5 Discussions.....62 5.3 Simulation Results.....65 5.3.1 Impact of the Numbers of Sinks and Sources.....66 5.3.2 Impact of Mobility .....69 5.3.3 Comparison of Shortcutting.....71 5.4 Comparison.....74 5.5 Summary.....79 Chapter 7 Conclusion and Future Work .....84 7.1 Conclusion.....84 7.2 Future work.....85 Bibliography.....8