隨意式無線網路（Ad Hoc Wireless Network），是由一群行動節點所組成的無基地台式（Infrastructureless）無線網路架構。在隨意式無線網路中的節點通常使用電池來運作，是以「如何有效降低電量消耗且延長網路節點存活時間來提升整體網路的生命」為目前許多研究者所鑽研的重要項目之一。
　　本篇論文是以『適用於隨意型無線網路上繞送之省電虛擬網格基礎（以下簡稱PVGI）』為架構，使用Pattern來產生節點的等待（waiting）與休眠（sleeping）狀態,以及Round-Rubin的方式將節點配置到Pattern中，同時加入「排程」使節點能在適當的時間進入等待及休眠狀態；其次，運用Threshold機制避免過度使用電量較少的節點，藉以達到延長網路生命之目的。此外，也針對PVGI在傳送與接收RREQ時所發生「來源端找不到轉送節點」、「目的端節點處於休眠狀態」的問題進行修正，提高路徑建立的成功率。
　　經由筆者以所撰寫的模擬系統進行測試及統計數據後，印證了使用Pattern、Round-Rubin與排程的機制的確能使節點能在適當的時間進入等待及休眠狀態，另外啟用Threshold機制的同時的確可以達到延長整體網路壽命的目標。

　　Ad Hoc Wireless Network consists of the Wireless Network structure of Infrastructureless from a group of the mobile nodes. The nodes of Ad Hoc Wireless Network usually work by battery, mainly based on how to effectively reduce the consumption of electric force and prolong the note’ｓduration to enhance the life of the whole Network. Besides, this is one of the most significant items that many current researchers would like to explore.
　　This thesis is based on “Power-saving Virtual Grid Infrastructure for wireless ad hoc network routing,which utilizes both Pattern to create the waiting and sleeping states of the node,and Round-Rubin approach to dispose nodes to Pattern, together with adding schedule which enables the entrance of waiting and sleeping state. Secondly, we manipulate the Threshold mechanism to prevent the node with less electric from being excessively used for the purpose of reaching Network’s life. More than that,we also focus on RREQ problem in the face of PVGI transmission and reception, from which it results the issues of “Seeking the transmit node in the source side“ and ”The destination side which lies in sleeping situation”to revise and enhance the successful rate of path construction. of problem the problematic revision from which Routing means of PVGI results enables the further reduction of the electric consumption in Network nodes.
　　Through the trial and statistic data of the simulator system,it proves the usages of Pattern and Round-Rubin,together with the mechanism and schedule which enable node to get in the waiting and sleeping circumstance in proper time. Furthermore, it indeed can reach the objective of prolonging the Network duration.

第一章　緒論 …………………………………………………………………1
1.1.研究背景 …………………………………………………………………1
1.2.研究動機與目的 …………………………………………………………2
第二章　相關研究 ……………………………………………………………4
2.1.路徑繞送演算法 …………………………………………………………4
2.2.電源與排程的管理 ………………………………………………………6
2.3.PVGI的介紹 ………………………………………………………………6
2.3.1建置grid ………………………………………………………………7
2.3.2與節點相關的時間資訊…………………………………………………7
2.3.3 Server的選舉演算法 ………………………………………………7
2.3.4節點各種狀態的運作……………………………………………………8
第三章　研究方法 ………………………………………………………10
3.1.Pattern的使用 …………………………………………………………10
3.2.Pattern的配置 ……………………………………………………13
3.3.節點數量、休眠時間與週期長度的調節 ……………………………15
3.4.Threshold的運用 …………………………………………………… 18
3.5.EPVGI演算法 ……………………………………………………………20
3.5.1.EPVGI演算法 …………………………………………………………20
3.5.2.Routing機制的修正 …………………………………………………23
第四章　模擬與分析 ……………………………………………………… 26
第五章　結論 ………………………………………………………………35
參考文獻………………………………………………………………………36

[1]顏鴻傑, 劉如生, 何應魁,“適用於隨意型無線網路上繞送資省電型 虛擬網格基礎架構” ,2003全國計算機會議,December,2003,pp.114
[2]PalChaudhuri, S.; Johnson, D.B.,“Power mode scheduling for ad hoc networks,”Network Protocols,2002.Proceedings.10th IEEE International Conference on, 12-15 Nov. 2002.
[3]C.E. Perkins and P. Bhagwat,”Highly Dynamic Destination-Sequenced Distance-Vector Routing（DSDV）for Mobile Computers,.”Comp. Commun. Rev. Oct 1994,pp.234-44
[4]C.E. Perkins and E.M. Royer, Ad-Hoc On-Demand Distance Bector Routing.”Proc.2nd IEEE Wksp.Mobile Comp.Sys. And Apps., Feb. 1999.
[5]J. Broch, D. B. Johnson,and D. A. Maltz,“The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks.”IETF internet draft, draft- ieft-manet-dsr-01.txt，Dec. 1998
[6]C.-C. Chiang,“Routing in Clustered Multihop, Mobile Wireless Networks With Fading Channel.” Proc. IEEE SICON ’97, Apr. 1997.
[7]Y.-B. Ko and N. H. Vaidya, “Location-aided Routing（LAR） in Mobile Ad Hoc Networks,”ACM/IEEE Int’l.Conf. Mobile Comp. Net. ,1998, pp. 66—75.
[8]W.-L. Liao, Y.-C. Tseng, and J.-P. Sheu. GRID,“A Fully Location-Aware　Routing Protocol for Mobile Ad Hoc Networks”Telecom Systems, Sep. 2001.
[9]Y.-C. Tseng, T.-Y. Hsieh, “Fully power-aware and location-aware protocols for wireless multi-hop ad hoc networks," Proceedings 11th International Conference on,2002.
[10]Suresh Singh，C.S. Raghavendra,“PAMAS─ power aware multi-access　protocol with signalling for ad hoc networks," ACM SIGCOMM Computer Communication Review July 1998, Volume 28 Issue 3
[11]M. Stemm and R. H. Katz,“Measuring and reducing energy consumption of network interfaces in hand-held devices," IEICE Trans. on Commun. SpecialIssue on Mobile Computing, vol. E80-B, No. 8, 1997.
[12]Y Xu, J. Heidemann, and D. Estrin,“Georaphy-informed Energy Conservation for Ad Hoc Routing," ACM MOBICOM, 2001,pages 70—84.
[13]M.R. Pearlman, J. Deng, B. Liang, Z. J. Haas, “Elective Participation in Ad Hoc Networks Based on Energy Consumption," IEEE GLOBECOM 2002.
[14]B.Chen, K. Jamieson, H. Balakrshnan, and R. Morris,“Span: an energy efficient coordination algorithm for topology maintenance in ad hoc wirelessnetworks,” Proc. ACM MobiCom, July 2001.
[15]Royer, EM.；Chai-Keong Toh,”A review of current routing protocol for ad hoc mobile wireless network, ”IEEE Personal Communication, Volume ：6 Issue 2 ,April 1999.
[16]Xiaoyan Hong, Kaixin Xu, and Mario Gerla,”Scalable Routing Protocols for Mobile Ad Hoc Networks”IEEE Network Magazine, July-Aug,2002.
[17]C. E.Perkins, E. M. Belding-Royer, and S. Das, “Ad hoc on demand distance vector (AODV) routing,”IETF Internet Draft, 2002.
[18]S. Xu and T. Saadawi,”Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc network?,”IEEE Commun. Mag., vol.39, pp.130-137,June 2001.
[19]C.Hedrick.Routing Information Protocol.Internet Request For Comments RFC 1058 , June 1988.
[20]J. Moy. OSPF version 2. Internet Request For Comments RFC1247,July 1997.