隨意行動無線網路是由一種不需要經由基礎建設的設備所形成的網路。在隨意無線網路中的行動節點可以在彼此之間做封包交換。由於目前的擇路演算法只考慮到中繼節點的數量多寡，而忽略到電池能量限制與移動模式等的影響。在考慮網路存活時間情況下，這篇論文將介紹提升存活時間之適應性擇路演算法（Lifetime-Enhanced Adaptive Routing Protocol，LEAR），當擇路表單內有多條到目的節點的路徑時，資料的傳送可以選擇避開能量不足的中繼節點，提供單一多路徑資料傳輸的可靠性。當行動運算節點的能量低於設定臨界值時，會發送一個低能量通知的控制封包給上一個傳送資料的行動節點。當行動運算節的收到此控制封包，會更新擇路路表單的剩餘路徑能量，透過此機制以提升整個網路的存活時間及減少行動節點電池耗盡的數量。

The mobile nodes (MNs) in the Mobile Ad hoc NETwork (MANET) can exchange their data packets directly without the existence of network infrastructure. In recent research work, hop counts within the transmission route are considered for routing decision. However, the influence from the receiving power and remaining energy of the MNs are not fully investigated. This may results in degraded network lifetime within the MANET to successfully transmit the data packets. In this thesis, a Lifetime-Enhanced Adaptive Routing (LEAR) protocol is proposed for unicast multipath routing of data packets. As there are more than two routing paths existed within the routing table, the proposed LEAR algorithm will avoid adopting the low-energy intermediate node in the decision of the transmitting path. The reliability for packet transmission can therefore be preserved. When the remaining energy of the intermediate MN is less than a predetermined threshold, a control packet will be delivered to its previous hop node for noticing the status of low energy. The routing path will therefore be reselected based on the updated energy status. From the simulation results, it can be observed that the proposed LEAR protocol increases the network life-time by reducing the total number of death nodes within the network topology.

摘要 .................................................. i
ABSTRACT ............................................. ii
誌謝 ................................................ iii
目錄 ................................................. iv
表目錄 ............................................... vi
圖目錄 .............................................. vii
一、 導論 ............................................. 1
1.1 概論 .............................................. 1
1.2 研究動機 .......................................... 3
1.3 論文架構 .......................................... 3
二、 背景知識及相關研究 ............................... 5
2.1 媒體存取控制層（Media Access Control Layer - MAC）. 6
2.2 網路通訊層（Network Layer）........................ 9
2.2.1 單一（Unicast）擇路協定 ........................ 10
2.2.2 單一多路徑擇路協定 ............................. 16
2.2.3 能量相關的擇路演算法 ........................ 20
三、 提升存活時間之適應性擇路演算法(Lifetime-Enhanced Adaptive Routing Protocol - LEAR) .................... 24
3.1 設計考量 ......................................... 24
3.2 提升存活時間之適應性擇路演算法設計 ............... 25
3.2.1 LEAR演算法擇路表單設計 ......................... 26
3.2.2 LEAR演算法的運作原理 ........................... 26
3.2.3 資料傳送的過程 ................................. 33
四、 模擬結果及分析 .................................. 38
4.1 模擬平台-網路模擬器 .............................. 38
4.2 模擬環境參數設定 ................................. 39
4.3 數據分析 ......................................... 40
4.3.1 資料封包的到達率 ............................... 40
4.3.2 資料封包平均延遲 ............................... 40
4.3.3 網路負載 ....................................... 40
4.3.4 網路存活時間 ................................... 40
4.3.5 行動節點電池耗盡的數量 ......................... 41
4.4 模擬結果 ......................................... 41
五、 結論 ............................................ 49
參考文獻 ............................................. 50

[1] C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proceedings of the ACM SIGCOMM ’94 Conference, Aug. 1994, pp. 234-244.
[2] S. Murthy and J. J. Garcia-Luna-Aceves, “An efficient routing protocol for wireless networks,” ACM Mobile Networks and Appl. J., Special Issue on Routing in Mobile Communication Networks, Oct. 1996, pp. 183-197.
[3] C. E. Perkins and E. M. Royer, “Ad Hoc On-Demand Distance Vector Routing,” Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Appl., Feb. 1999, pp. 90-100.
[4] D. B. Johnson, D. A. Maltz, and J. Broch, “DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks,” Ad Hoc Networking, edited by C. E. Perkins, Addison-Wesley, 2001.
[5] V. D. Park and M. S. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” Proceedings of IEEE Infocom ’97, Apr. 1997, pp. 1405-1413.
[6] V. D. Park, M. S. Corson, “Temporally-Ordered Routing Algorithm (TORA) Version 1 Functional Specification,” Internet-Draft, draft-ietfmanet-tora-spec-04.txt, Jul. 2001.
[7] IEEE Std 802.11-1997 Supplement to IEEE standard for information technology telecommunications and information exchange between systems - local and metropolitan area networks - specific requirements-part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications.
[8] IEEE Std 802.11a-1999 Supplement to IEEE standard for information technology telecommunications and information exchange between systems - local and metropolitan area networks - specific requirements. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: high-speed physical layer in the 5 GHz band.
[9] IEEE Std 802.11b-1999 Supplement to IEEE standard for information technology telecommunications and information exchange between systems - local and metropolitan area networks - specific requirements. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment 2: higher-speed physical lyaer (PHY) extension in the 2.4 GHz band.
[10] IEEE Std 802.11g-2003 Supplement to IEEE standard for information technology telecommunications and information exchange between systems - local and metropolitan area networks - specific requirements. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment 4: Further Higher Data Rate Extension in the 2.4 GHz band.
[11] Draft Std 802.11n, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Amendment: Enhancements for Higher Throughput, IEEE Draft Std P802.11n/D2.00, Feb. 2007.
[12] C.-K. Toh, “A Novel Distributed Routing Protocol To Support Ad-Hoc Mobile Computing,” Proceedings of 15th IEEE Annual International Phoenix Conference Computers and Communications, Mar. 1996, pp. 480-486.
[13] R. Dube, C. D. Rais, K-Y. Wang, and S. K. Tripathi, “Signal Stability-Based Adaptive Routing (SSA) for Ad Hoc Mobile Networks,” IEEE Personal Communications, Feb. 1997, pp. 36-45.
[14] Z. J. Haas, M. R. Pearlman, “The Performance of Query Control Schemes for the Zone Routing Protocol,” IEEE/ACM Transactions on Networking (TON), vol. 9, no. 4, Aug. 2001, pp. 427-438.
[15] P. Samar, M. R. Pearlman, Z. J. Haas, “Hybrid Routing: The Pursuit of an Adaptable and Scalable Routing Framework for Ad Hoc Networks,” The Handbook of Ad Hoc Wireless Networks, Boca Raton, FL: CRC Press, 2003.
[16] C.C. Chiang, H. K. Wu, W. Liu, and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proceedings of IEEE SICON ’97, Apr. 1997, pp. 197-211.
[17] A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, “Scalable Routing Strategies for Ad hoc Wireless Networks,” IEEE Journal on Selected Areas in Communication, vol. 17, no. 8, Aug. 1999, pp. 1369-1379.
[18] R. Sivahumar, P. Sinha, and V. Bharghavan, “CEDAR: a Core-Extraction Distributed Ad hoc Routing algorithm,” IEEE Journal on Selected Areas in Communication, vol. 17, no. 8, Aug. 1999, pp. 1454–1465.
[19] J. Broch, D. Maltz, D. Johnson, Y.-C. Hu, and J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proceeding of the ACM/IEEE International Conference on Mobile Computing and Networking, Oct. 1998, pp. 25-30.
[20] P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark, “Scenario-based Performance Analysis of Routing Protocols for Mobile Ad-hoc Networks,” Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, Aug. 1999, pp. 195-206.
[21] E. M. Royer and C.-K.Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communication Magazine, Apr. 1999, pp. 46-55.
[22] S. R. Das, R. Castaneda, J. Yan, and R. Sengupta, “Comparative Performance Evaluation of Routing Protocols for Mobile, Ad hoc Networks,” Proceedings of the International Conference on Computer Communications and Networks (ICCCN), Oct. 1998, pp. 153–161.
[23] B. W. Parkinson and S. W. Gilbert, “NAVSTAR: Global Positioning System - Ten Years Later,” Proceedings of IEEE, Oct. 1983, pp. 1177-1186.
[24] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, “A Distance Routing Effect Algorithm for Mobility (DREAM),” Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, Oct. 1998, pp. 76-84.
[25] Y.-B. Ko and N. H. Vaidya, “Location-Aided Routing (LAR) in mobile ad hoc networks,” ACM Wireless Networks Journal, vol. 6, no.4, 2000, pp. 307-321.
[26] R. Jain, A. Puri, and R. Sengupta, “Geographical Routing Using Partial Information for Wireless Ad Hoc Networks,” IEEE Personal Communications, vol. 8, no. 1, Feb. 2001, pp. 48-57.
[27] B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, Aug. 2000, pp. 243-254.
[28] K.-T. Feng and T.-E. Lu, “Velocity and Location Aided Routing for Mobile Ad Hoc Networks,” Proceedings of IEEE Vehicular Technology Conference (VTC) Fall, Sep. 2004, pp. 2789-2793.
[29] T.-E. Lu. and K.-T Feng, “Predictive Mobility and Location-Aware Routing Protocol in Mobile Ad Hoc Networks,” Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), Dec. 2005, pp. 899-903
[30] K.-T. Feng, C.-H. Chen, and T.-E. Lu, “Velocity-Assisted Predictive Mobility and Location-Aware Protocols for Mobile Ad Hoc Networks,” accepted and to appear in IEEE Trans. on Vehicular Technology, 2008.
[31] J. Li, J. Jannotti, D. S. J. D. Couto, D. R. Karger, and R. Morris, “A Scalable Location Service for Geographic Ad Hoc Routing,” Proceedings of the ACM/IEEE Mobile Computing and Networking (MobiCom), Aug. 2000, pp. 120-130.
[32] R. Morris, J. Jannotti, F. Kaashoek, J. Li, and D. Decouto, “CarNet: A Scalable Ad Hoc Wireless Network System,” Proceedings of the 9th ACM SIGOPS, Sep. 2000, pp. 61–65.
[33] D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” T. Imielinski and H. Korth, Eds. Mobile Computing, 1996, Ch. 5.
[34] S. J. Lee and M. Gerla, “AODV-BR: Backup Routing in Ad hoc Networks,” Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Sep. 2000, pages 1311–1316.
[35] M. K. Marina and S. R. Das, “On-demand Multipath Distance Vector Routing in Ad Hoc Networks,” Proceedings of the 9th IEEE International Conference on Network Protocols, Nov. 2001, pp. 14-23.
[36] J.-C. Cano and D. Kim, “Investigating Performance of Power-aware Routing Protocols for Mobile Ad Hoc Networks,” Proceedings of the International Mobility and Wireless Access Workshop, Oct. 2002, pp. 80-86.
[37] J.-C. Cano and P. Manzoni, “A Performance Comparison of Energy Consumption for Mobile Ad Hoc Network Routing Protocols,” Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Sep. 2000, pp. 57-64.
[38] S. Singh, M. Woo, and C. S. Raghavendra, “Power-Aware Routing in Mobile Ad Hoc Networks,” Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Oct. 1998, pp. 181-190.
[39] M. Stemm and R. H. Katz, “Measuring and Reducing Energy Consumption of Network Interfaces in Hand-Held Devices,” IEICE Transactions on Communications, vol. E80-B, no. 8, Aug. 1997, pp. 1125-1131.
[40] C.-K. Toh, H. Cobb, and D. A. Scott, “Performance Evaluation of Battery-LifeAware Routing Schemes for Wireless Ad Hoc Networks,” IEEE International Conference on Communications, vol. 9, 2001, pp. 2824-2829.
[41] X. Jin, W. Cai, and Y. Zhang, “A RED Based Minimum Energy Routing Algorithm for Wireless Ad-Hoc Networks,” Wireless Communications, Networking and Mobile Computing, vol. 2, 23-26, Sep. 2005, pp. 757-761.
[42] W.-H. Cheng, “Energy-Aware Routing Protocols for Mobile Ad Hoc Network,” National Chiao Tung University, thesis, Jun. 2006.
[43] http://www.isi.edu/nsnam/ns/ns-documentation.html
[44] T. Camp, J. Boleng, V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Communication and Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, vol. 2, no. 5, 2002, pp. 483-502.