隨意型無線網路(Ad Hoc Networks)是一種無基礎建設的架構，提供使用者行動資訊服務，每一個移動主機扮演了一個路由器的功能,並且將封包的傳送朝向到目的地的主機,由於無線網路有高移動率的特性，如何保持連線的穩定性成為研究的重點。
本研究提出一個利用灰預測模型GM(1，1)的預先繞徑機制，在這個方法中，我們利用兩個鄰近主機互相的頻繁通訊可以偵測了解它們互相的彼此距離，對於其鄰近點的離去或關機或者是穩固的連結狀態，都可以由其有週期的連結作記錄。隨者這些記錄，我們可以利用灰預測模型去產生一個以Shortest-Path(AODV or DSR)或以Signal-Base (SSA or SOR)的預先繞徑路由選擇,使整個連線能提早反應網路品質的變化，增加封包到達率(Packet Delivery Ratio)與傳輸的通透率(Throughput)。先前的研究以Shortest-Path為灰預測序列參數，基於Shortest-Path 繞徑的缺點另外提出一個結合Shortest-Path與Signal-Base 的方法SOR，加以比較，我們可以在不同的傳輸需求上以不同的參數作為路由選擇的依據。以Shortest-Path為路由選擇參數可以減少封包傳送延遲時間，而以Signal-Base為路由選擇參數可以增加連線的穩定性。
根據模擬的結果指出，以Signal-Base 為路由選擇參數並加入灰預測雖然會增加少許平均的延遲時間與路由封包，卻可以明顯減少斷線的次數，增加連線的時間，使整個連線更加穩定。
另外，我們也提出了在群播(multicast)上的灰預測預先繞徑機制。我們使用兩個典型的群播協定：MAODV 與 ODMRP，並加入灰預測預先繞徑，設計(1)以Tree為結構處理群播的MAODV與(2)以Mesh為結構處理群播的ODRMP兩種機制。根據模擬的結果顯示，在Tree或Mesh的結構處理無線群播上加入預先繞徑，也可以提前反應網路的變化提升連線效能。

Mobile Ad Hoc Networks (MANET) is infrastructure-less, providing the user to act the information services. Each host assumes the role of a router and relays packets toward final destinations. MANET has characteristic which high mobility. How to keep link stability is our concerning.
This thesis proposes an utilize grey prediction model, GM (1,1) prerouting mechanism. It has to sense and understand the transmitter range, distance and signal stability of being predictive by two neighbor nodes as frequently communicating with each other. From departing, closing or stable situation of two nodes about each link, each node can record a period of linking stabilities about neighbor. Then, utilizing grey-prediction model to select the best path about requested on-demand route. The previous research indicates that shortest-path routing within grey-prediction. In this thesis due to avoid drawback of shortest-path routing join the signal-base (it also call minimum-cost) method and propose a signal-strength on-demand routing, SOR, to combine their advantages to get better performance. Finally, to take into the comparison, the different routing parameter can be considered with the different requirements of transmission according the selective basis. As applying the routing parameter, shortest path reduces the latency time and minimum cost increase the stability; however, the combined method has the advantages to get fewer latency time and stability.
Besides, in this thesis, we also present two mechanisms to solve multicast prerouting within grey-prediction. It uses two classical multicast protocols, MAODV regarding tree-base as the multicast prerouting structural and ODRMP regarding mesh-base as the multicast prerouting structure. By joining grey-prediction process, and according the simulation results, the two wireless tree-based or mesh-based multicast prerouting mechanisms can also quickly respond the change of the network and promote pre-routing capability.

摘要............................................I
Abstract......................................III
誌謝 (Acknowledgments)..........................V
Contents.......................................VI
List of Figures..............................VIII
Chapter 1. Introduction.........................1
1.1 Background..................................1
1.2 Outline of the Thesis.......................6
Chapter 2 Ad Hoc Wireless Protocols.............7
2.1 Ad Hoc Unicasting...........................7
2.1.1 Table-Driven Routing Protocols............8
2.1.1.1 Destination-Sequenced Distance-Vector Routing (DSDV)..................................8
2.1.1.2 Clusterhead Gateway Switch Routing (CGSR)..........................................8
2.1.1.3 The Wireless Routing Protocol (WRP)....10
2.1.2 Source-Initiated On-Demand Routing.......11
2.1.2.1 Ad Hoc On-Demand Distance Vector Routing (AODV).........................................12
2.1.2.2 Dynamic Source Routing (DSR)...........14
2.1.2.3 Temporally Ordered Routing Algorithm (TORA).........................................16
2.1.2.4 Associatively-Based Routing (ABR)......19
2.1.2.5 Signal Stability-Based Adaptive Routing (SSA...........................................21
2.2 Ad Hoc Multicasting........................23
2.2.1 Ad Hoc Multicast Routing Protocol (AMRoute)......................................26
2.2.2 Multicast Ad Hoc On-Demand distance Vector Protocol (MAODV)...............................28
2.2.3 On-Demand Multicast Routing Protocol (ODMR).........................................30
2.2.4 Core-Assisted Mesh Protocol (CAMP).......31
Chapter 3. Signal Strength On Demand Routing...33
3.1 Drawback of Signal Stability-Based Adaptive Routing (SSA)..................................35
3.2 Signal-strength On-demand Routing Algorithm (SOR)..........................................37
3.3 Distance-Power Relationship................40
Chapter 4 Prerouting Mechanism.................43
4.1 Prediction Schemes.........................43
4.1.1 Principles of Grey Theory................43
4.1.2 Relating the Preemptive Range to Signal Power..........................................45
4.2 Unicast Prerouting.........................46
4.2.1 Failure Detection Phase..................47
4.2.1 Route-Search Phase.......................48
4.2.1 Connection Phase.........................48
4.3 Multicast Prerouting.......................50
4.3.1 State Diagram of Multicast Host..........50
4.3.2 Multicast Prerouting Phase...............51
Chapter 5. Simulation and Results analysis.....58
5.1 Simulation Environment.....................58
5.2 Evaluation Method..........................59
5.3 Unicast Simulation Results.................60
Chapter 6 Conclusion...........................74
Reference ......................................76

[1] D. Johnson and D. Maltz, “Dynamic Source Routing in Ad-Hoc Wireless Networks,” Proceedings of SIGCIIM 96, pp. 153-181, Aug. 1996.

[2] E.M Royer and C.K. Toh, “A review of current routing protocols for ad hoc mobile wireless networks” IEEE Personal Communications, vol. 6,no. 2, pp. 46 -55, Apr 1999.

[3] C.E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computer,” Comp. Commun. Rev., pp. 234-44, Oct. 1994.

[4] L.R. Ford Jr. and D.R. Fulkerson, Flows in Networks, Princeton Univ. Press, 1962.

[5] C.C. Chiang, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proc. IEEE Sicon ’97, pp. 197-211, Apr. 1997.

[6] S. Murthy and J.J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks, “ACM Mobile Networks and App. J., Special Issue on Routing in Mobile Communication Networks, pp.183-97, Oct. 1996.

[7] C.E. Perkins and E.M. Royer. “Ad-hoc On-Demand Distance Vector Routing”, Proc. 2nd IEEE Workshop. Mobile Comp. Sys. and Apps, pp. 90-100, Feb. 1999.

[8] D.B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad-Hoc Wireless Networks,” Mobile Computing, pp. 153-81, 1996.

[9] J. Deng, “Essential Topics on Grey System Theory and Application,” Beijing, China: China Ocean Press, 1988.

[10] J. Jubin and J. Tornow, “The DARPA Packet Radio Network Protocols,” Proc. IEEE, Vol 75, no. 1, pp. 21-32, 1987.

[11] S.J. Lee, M. Gerla, C.C. Chiang, ”On-demand multicast routing protocol.”, In Proceedings of IEEE Wireless Communications and Networking Conference 1999 (WCNC ’99), pp. 1298-1302, Sept. 1999.
[12] E. Bommaiah, M. Liu, A. McAuley and R. Talpade,” AMRoute: Ad-hoc Multicast Routing Protocol.”, Internet-draft，draft-talpade-manet-amroute-00.txt, Aug. 1998.

[13] E.M. Royer, C.E. Perkins, ”Multicast ad hoc on demand distance vector (MAODV) routing.”, IETF Internet draft，draft-ietf-manet-maodv-00.txt, July 2000.

[14] J.J. Garcia-Luna-Aceves and E.L. Madruga, ”The Core-Assisted Mesh Protocol”, IEEE Journal on Selected Areas in Communications, Special Issue on Ad-Hoc Network, Vol. 17, No. 8, Aug. 1998.

[15] S.L. Su, Y.C. Su, and J.F. Huang, “Grey-Based Power Control for DS-CDMA Cellular Mobile Systems”, IEEE Transactions on Vehicular Technology, Vol. 49, No. 6, pp.2081-2088, Nov. 2000.

[16] W. Su, S.J. Lee, M. Gerla, “Mobility Prediction in Wireless Networks”, IEEE, pp.491-495, 2000.

[17] T. Goff, N. B. Abu-Ghazaleh, D. S. Phatak and R. Kahvecioglu, ”Preemptive Routing in Ad Hoc Networks”, ACM SIGMOBILE 7/01 Rome, Italy, pp.43-51, 2000.

[18] Yih-Fuh Wang, Hsien-Wen Chen, ”Grey Pre-Routing-Based Restoration on Wireless Ad Hoc Networks,”, 第四屆電子化企業經營管理理論暨實務研討會論文集, 2003.

[19] K.H.Wang and B. Li, “Group mobility and partition prediction in wireless ad-hoc networks,” IEEE International Conference on Communications, Vol. 2, pp. 1017 -1021, 2002.

[20] S.T. Sheu, C.C. Wu, “Using grey prediction theory to reduce handoff overhead in cellular communication systems,”, International Symposium on Indoor and Mobile Radio Communications, Vol. 2, pp. 782 –786, 2000.

[21] Yih-Fuh Wang, Chun-Tsung Chou,”Grey-Prediction Preemptive Routing in Ad Hoc Networks,”,第五屆電子化企業經營管理理論暨實務研討會論文集, 2004.

[22] K. Pahlavan, A. H. Levesque, “Wireless Information Networks,” pp. 37-83, 2003.

[23] M.S. Corson and A. Ephremdies, “A Distributed Routing Algorithm for Mobile Wireless Networks,” ACM/Baltzer Wireless Networks J., Vol. 1, no. 1, pp. 61-91, Feb. 1995.

[24] C.K. Toh, “A Novel Distributed Routing Protocol To Support Ad-Hoc Mobile Computing,” Proc 1996 IEEE 15th Annual Int’l. Phodnix Conf. Comp, and Commun, pp. 480-86, Mar. 1996.

[25] R. Dube , “Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks,” IEEE Pers. Commun., Vol. 4, no. 2, pp.1-36, Mar, 1997.

[26] E. M. Royer and C. E. Perkins, “Multicast operation of the ad-hoc on-demand distance vector routing protocol,” Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 207–218, Aug. 1999.

[27] E. Pagani and G. P. Rossi, ”An On-Demand Shared Tree with Hybrid State for Multicast Routing in Ad Hoc Mobile Wireless Networks”, 1999 International Workshops on Parallel Processing, pp. 4-9, Sep. 1999.