無線感測網路之節能最佳化路由選徑

無線感測網路的存活時間受限於電池壽命、能源使用效率等因素，此外由於感測網路往往不具同步化的機制，封包重傳所消耗的電力不可忽視。本篇論文中，我們強調路由選徑演算法對於網路存活時間的影響力，同時考慮封包重傳因子，用數學模型闡述封包重傳次數的期望值，以一個應變於各節點累積流量的凸性函數表示之。我們應用最佳化技術規劃這個無線感測網路上的節能最佳化路由問題，雖然該問題具有最小最大化目標式、非線性等特性造成數學解題上的難度所在，應用拉格朗日鬆弛法可以求出該凸性規劃問題的最佳解，基於拉格朗日鬆弛法，本文中提出兩種演算法：分別最佳化解決拉格朗日鬆弛後的對應問題，以及直接處理原始規劃問題的最佳化演算法。兩種方法各有其效率上的優缺點，將於內文中分析之。透過上述兩種方法的合併使用，我們得出一組最佳的路由選徑值，使得感測網路的存活時間最大化。經過實驗，其他以最短路徑為基礎的演算法相對於我們的最佳化演算法，存活時間只有最佳解的百分之四十八，證明我們的方法於解題品質上的優越性。

關鍵字

能源效率；最佳繞路框架；拉格朗日鬆弛法；最佳化；感測網路；網路存活時間

並列摘要

The network lifetime for wireless sensor network plays an important role to survivability. It is constraint to battery capacity and energy-efficiency. Besides, being lack of synchronization mechanism in sensor network, the retransmission for each packet is non-neglected. In this thesis, we indicate the importance of routing protocol to network lifetime, and model the expected retransmission time as a convex function with respect to aggregate flow on each sensor node. Thus we formulate the optimal energy-efficient routing as a non-linear min-max programming problem with convex product form, which can be optimally solved by optimal routing framework. Based on the optimal routing framework, we propose Lagrangean-based algorithm and primal optimal algorithm. By the combination of these two algorithms, we can optimally and efficiently get the routing assignment to maximize the network life in the sensor network. From experiments, we observe that when the optimal network lifetime increases as the number of sensor nodes increase. While the shortest path-based heuristic algorithm can only achieve about 48% network lifetime compared with our solution approach.

並列關鍵字

sensor networks ； energy-efficient ； optimization ； network lifetime ； optimal routing framework ； lagrangean relaxation

參考文獻

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Network Flows: Theory, Algorithms, and Applications,” Prentice Hall, 1993.b

[3] E. Biagioni and K. Bridges, “The Application of Remote Sensor Technology to Assist the Recovery of Rare and Endangered Species,” Special issue on Distributed Sensor Networks for the International Journal of High Performance Computing Applications, vol.16, no.3, 2002.

[4] G. Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,” IEEE J. Select. Areas Comm., vol.18, pp.318-320, 2000.

[6] R. L. Cruz, and A. V. Santhanam, “Optimal Routing, Link Scheduling and Power Control in Multi-hop Wireless Networks”, IEEE INFOCOM 2003.

[7] T. V. Dam, and K. Langendoen, “An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks”, The First ACM Conference on Embedded Networked Sensor Systems, November, 2003.

國際替代計量

無線感測網路之節能最佳化路由選徑

全文下載

主題瀏覽