臺灣博碩士論文加值系統

近年來，隨著無線傳感器網路（WSN）廣泛傳播。在這樣的情況下，我們期望通過多跳躍傳送來擴展生命週期。能量是電池供電的無線傳感器網路（wireless sensor networks）極其重要的資源。大多數現有的路由平衡演算法總是用最小能量來轉發數據封包到匯聚點(sink)以減少能源消耗，這導致殘餘能量不平衡地分佈在傳感器節點之間，最終導致網路隔離，尤其在匯聚點周遭的節點(Sink Connectivity Area， SCA)會產生負載不平衡的嚴重問題，從而使路由平衡設計成為一個關鍵的挑戰性問題。
在本文中，我們提出三種策略來解決SCA負載不平衡的問題，此方法包含多路徑路由平衡演算法、分散式能量平衡法以及動態半徑計算法。多路徑路由平衡演算法以平衡SCA節點的封包傳送數量，最終能夠使SCA負載平衡。分散式能量平衡法找出兩條獨立的最短路徑來交替傳送資訊，藉此達到分散式的SCA負載平衡效果。最後我們結合動態半徑計算策略，來找出每個節點的最佳傳送距離，藉此降低整體無線網路之功率消耗速率。

In recent years, as wireless sensor networks (WSNs) are widely deployed. In such a situation, network lifetime is expected to be extended by multiple hop transmission. Energy is an extremely critical resource for limited battery-powered wireless sensor networks (WSN). Most of the existing balanced routing algorithm always forward packets along the minimum energy path to the sink to merely minimize energy consumption, which causes an unbalanced distribution of residual energy among sensor nodes, and eventually results in a network isolation phenomenon. In particular, the sensor nodes of Sink Connectivity Area (SCA) will cause a serious problem of load imbalance, thus making balanced routing design a key challenge research issue.

In this paper, we propose three strategies to solve the problem of SCA load imbalance, including Multi-Path Balanced Routing Algorithm, Distribution Energy Balanced method and Dynamical Radius Calculation method. Numbers of SCA delivered packets have been balanced by Multi-Path Balanced Routing Algorithm and ultimately to balance the traffic load of SCA; Distribution Energy Balanced method will ultimately find two independent paths for each node to transmit packets so that to achieve a distribution energy balanced effect. Finally, the Dynamical Radius Calculation strategy is combined with the previous two presented methods to find the optimal transmission distance between each node, thus lowering power consumption rate in whole wireless networks.

摘 要 i
ABSTRACT ii
致謝 iii
目錄 iv
表目錄 vi
圖目錄 viii
第一章 緒論 1
1.1前言 1
1.2研究動機 2
1.3研究目的 3
1.4論文架構 3
第二章 演算法路徑建構方式 4
2.1 Dijkstra演算法 4
2.1.1 Dijkstra基本介紹 4
2.1.2 Dijkstra 架構 5
2.2多條最短路徑 15
2.2.1 Dijkstra修改多條最短路徑之架構 15
2.2.2 Dijkstra修改多條最短路徑之方法 16
第三章 路由平衡演算法 18
3.1多路徑路由平衡演算法 20
3.2分散式能量平衡法 30
3.3動態半徑計算法 32
第四章 模擬數據分析 35
4.1電腦模擬環境設定 35
4.2三種策略之模擬 36
4.2.1 功率消耗速率 36
4.2.2 電池平均剩餘電量 40
4.2.3 網路生命週期 44
4.2.4 時間計算複雜度 45
4.2.5 模擬結果統計 46
第五章 結論與未來展望 46
參考文獻 47

[1] 王志坚, 韩伟一, and 李一军. "具有多条最短路径的最短路问题." 哈尔滨工业大学学报 9 (2010): pp.1428-1431.
[2] J. Y. Yen,”Finding the K shortest loopless paths in a network,” Management Science, 17 (1971), pp. 712-716.
[3] Wu, Dapeng, et al. "A hierarchical packet forwarding mechanism for energy harvesting wireless sensor networks." IEEE Communications Magazine, 53.8, 2015, pp. 92-98.
[4] Abdulla, Ahmed EAA, et al. "Hymn: A novel hybrid multi-hop routing algorithm to improve the longevity of WSNs." IEEE Transactions on Wireless Communications 11.7, 2012, pp.2531-2541.
[5] NOSHITA K. “A theorem on the expected comp1exity of Dijkstra's shortest paths a1gorithm,” Journa1 of A1gorithms, 1985, 6(3): p. 400-408.
[6] PETTIE S, RAMACHANDRAN V. “Computing shortest paths with comparisons and additions,” Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete A1gorithms. Phi1ade1phia: Society for Industria1 and Applied Mathematics, 2002: pp. 267-276.
[7] J. Hershberger, S. Suri, and A. Bhosle. “On the difficulty of some shortest path problems,” In Proc.20th Sympos. Theoret. Aspects Comput. Sci., Lecture Notes Comput. Sci. Springer-Verlag, 2003.
[8] N. Katoh, T. Ibaraki, and H. Mine. “An efficient algorithm for k shortest simple paths,” Networks, 12, pp.411–427, 1982.
[9] E. L. Lawler. “A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem,” Management Science, 18:401–405, 1972.
[10] E. Martins and M. Pascoal. “A new implementation of Yen’s ranking loopless paths algorithm,” Submitted for publication, Universidade de Coimbra, Portugal, 2000.
[11] E. Martins, M. Pascoal, and J. Santos. “A new algorithm for ranking loopless paths,” Technical report, Universidade de Coimbra, Portugal, 1997.
[12] C. Ho and R. Zhang, “Optimal Energy Allocation for Wireless Communications with Energy Harvesting Constraints,” IEEE Trans. Signal Processing, vol. 60, no. 9, May 2012, pp. 4808–18.
[13] D. Wei et al., “An Energy-Efficient Clustering Solution for Wireless Sensor Networks,” IEEE Trans. Wireless Commun., vol. 10, no. 11, Sept. 2011, pp. 3973–83.
[14] J. Meng, X. Zhang and Y. Dong, et al. “Adaptive Energy-Harvesting Aware Clustering Routing Protocol for Wireless Sensor Networks,” IEEE CHINACOM, Kunming, China, Aug 2012, pp. 742–47.
[15] R. Vullers et al., “Energy Harvesting for Autonomous Wireless Sensor Networks,” IEEE Solid-State Circuits Mag., vol. 2, no. 2, Spring 2010, pp. 29–38.
[16] Bouabdallah, Fatma, Nizar Bouabdallah, and Raouf Boutaba. "On balancing energy consumption in wireless sensor networks." IEEE Transactions on Vehicular Technology, 58.6 (2009): pp. 2909-2924.
[17] M. Miller and N. Vaidya, “A MAC protocol to reduce sensor network energy consumption using a wake-up radio,” IEEE Trans. Mobile Comput., vol. 4, no. 3, pp. 228–242, May/Jun. 2005.
[18] H. Kwon, T. H. Kim, S. Choi, and B. G. Lee, “A cross-layer strategy for energy-efficient reliable delivery in wireless sensor networks,” IEEE Trans. Wireless Commun., vol. 5, no. 12, pp. 3689–3699, Dec. 2006.
[19] R. C. Shah and H. M. Rabaey, “Energy aware routing for low energy ad hoc sensor networks,” in Proc. IEEE WCNC. Orlando, FL, Mar. 2002, pp. 350–355.