在無線隨意網路中，所有裝置都是倚賴電池來維持動力。當無線裝置傳輸狀態時，耗電量是最大的。傳統無線隨意網路中，選徑協定在有資料要傳輸時尋找一條傳輸路徑，而所找到的傳輸路徑往往是使用最少跳躍次數的路徑。由於傳輸所需電力與距離平方成正比，所以最短路徑可能並不是最省電的路徑。
本研究旨在計算出在整體網路中任意兩節點間的多重傳遞路徑中，最為省電的一條。藉由限制各節點的分支度，並以距離平方和最小為目標，找出一條可能花費較小電力的一條路徑，以減少傳輸狀態時的電力消耗。

Energy Conservation has been the focus in the ad hoc wireless network study. As the capacity of battery is limited, node will lose its function once its energy is exhausted. This thesis is aiming to calculate among the multiple transmission paths and find out a path which consumes the least energy. Previous studies are focused on finding the minimum hop path in transmission. In this study we propose to use the square of the distance between nodes as a proxy to the power consumption as the transmission power is proportional to the square of the distance between the nodes. 
We simulate the node transmission by limiting node out-degree in broadcasting and calculate the minimum sum of the square of distance between nodes in the path to find a path which has the least energy consumption.

目錄
第一章 緒論	1
1.1 研究背景	1
1.2 研究動機	2
1.3 研究目的	4
1.4 論文結構	5
第二章 背景知識與相關研究	6
2.1 背景知識	6
2.1.1 無線主機的通訊架構	7
2.2 無線隨意網路選徑	11
2.2.1 主動式選徑協定	11
2.2.2 回應式選徑協定	14
2.2.3 混合式選徑協定	17
2.2.4 選徑協定比較	19
2.3 網路特性	19
2.3.1 網路	19
2.3.2 有向圖與無向圖	20
2.3.3 分支度	20
2.3.4 連通性	21
2.3.5 叢聚度     21
第三章 省電選徑模擬	23
3.1 傳輸電力與多點跳躍的關係	23
3.2 傳輸耗電計算與模擬	26
3.3 模擬環境	30
3.3.1 限制外分支度1的網路分析	31
3.3.2 限制外分支度2的網路分析	33
3.3.3 限制外分支度3的網路分析	34
3.3.4 限制外分支度4~5的網路分析	37
3.3.5 外分支度鄰近節點數，最小電力和跳躍數之關係	39
3.3.6 叢聚度對最小電力之影響	40
3.4 模擬結果分析	41
第四章 結論	43
參考文獻	44
附錄－英文論文	46

圖目錄
圖一     無線隨意網路示意圖	2
圖二     通訊範圍內與通訊範圍外的路徑	3
圖三     在同範圍內做單點與多點跳躍的路徑	4
圖四     多重路徑示意圖	5
圖五     主機的四種狀態	7
圖六     節點內收發架構	7
圖七     傳送封包的電力消耗	8
圖八     接收端的電力消耗	9
圖九     n個點成線形排列	10
圖十     DSDV 範例圖	13
圖十一   主動式選徑協定的規則	15
圖十二   RREQ與RREP流程	16
圖十三   AODV選徑協定	17
圖十四   節點A的N-hop的區域範圍圖	18
圖十五   具有5個點5個邊的網路圖	20
圖十六   有向圖	20
圖十七   連通性	21
圖十八   節點A與節點B與節點C的距離	24
圖十九   節點A到節點C的兩條不同距離的路徑	25
圖二十   節點A與最鄰近的節點B，兩點間距離|dAB|	26
圖二十一 限制廣播條件為1選徑示意圖	27
圖二十二 節點C與最鄰近的節點E、F，距離|dCE|、|dCF|	28
圖二十三 限制廣播二選徑示意圖	28
圖二十四 限制廣播三選徑示意圖	29
圖二十五 限制廣播四選徑示意圖	30
圖二十六 限制外分支度1的有向圖	31
圖二十七 每個節點的傳輸範圍內只有一個節點	31
圖二十八 1點或2點形成的孤立點拓樸	32
圖二十九 3點形成的線型拓樸	32
圖三十   各節點的最鄰近點皆不同的連通圖	32
圖三十一 限制外分支度2的有向圖	33
圖三十二 迴圈拓樸	34
圖三十三 蝌蚪拓樸	34
圖三十四 限制外分度3的有向圖	35
圖三十五 限制外分支度3，最小電力選擇的路徑圖	36
圖三十六 最小電力選徑與最短路徑比較圖	36
圖三十七 限制外分支度4，最小電力選徑與最短路徑比較圖	37
圖三十八 限制外分支度5，最小電力選徑與最短路徑比較圖	38
圖三十九 最小電力選徑與最短路徑之消耗電力比較	38
圖四十   最小電力選徑與最短路徑之跳躍數之比較	39
圖四十一 叢聚度與外分支度的關係	40

表目錄
表一 節點四種狀態所耗電力	9
表二 參數解釋	10
表三 無線隨意網路選徑協定分類	11
表四 DSDV選徑格式	12
表五 DSDV節點1的選徑表	14
表六 選徑協定比較	19
表七 節點數為100個到500個時的電力比較	39

[1]	I. F. Akyildiz , W.Su, Y. Sankarasubramaniam et al.,        “Wireless Sensor Networks:A Survey,” in Computer Networks, vol. 38, pp. 393-422, 2002.
[2]	C. E. Perkins, Ed., Ad Hoc Networking, Addison Wesley, 2001
[3]	Q. Wang, “Zygmunt J. Haas, BASS: an Adaptive Sleeping Scheme for Wireless Sensor Network with Bursty Arrival, ” in IWCMC,2006
[4]	W. Ye, J. Heidemann, and D.Estrin,“An energy-efficient MAC protocol for wireless sensor networks,” in INFOCOM. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies vol. 3, pp. 1567-1576, 2002.
[5]	A. Sankar, and Z. Liu, “Maximum lifetime routing in wireless ad-hoc networks ” in INFOCOM, Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 1089-1097, 2004.
[6]	I. F. Akyildiz, and M. C. Vuran, Wireless sensor network, 2010.
[7]	L. M. Feeney, and M. Nilsson, “Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment,” in INFOCOM 2001, vol. 3, pp. 1548-1557, 2001.
[8]	W. R. Heinzelman, A. Chandrakasan, and H. Balakrishna, “Energy-Efficient Communication Protocol forWireless Microsensor Networks,” Proceedings of the 33rd Annual Hawaii International Conference , vol. 2, pp. 10, 2000.
[9]	C. Sergiou, and V. Vassiliou, “Performance Evaluation of the DAlPaS Congestion Control Algorithm in Wireless Sensor Networks,” in Distributed Computing in Sensor Systems and Workshops (DCOSS), 2011 International Conference pp.1-7, 2011.
[10]	E. M. Royer, and C.-K. Toh, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks,” in IEEE Personal Communications, vol. 62, pp. 46-55, 1999.
[11]	C. E. Perkins, and P. Bhagwat, “Highly Dynamic   Destination-Sequenced Distance-Vector Routing(DSDV) for Moblie Computers,” in Computer Communications Review, vol. 24, pp. 234-244, 1994.
[12]	C.-C. Chiang, “Routing in Clustered Multihop, Mobile Wireless   Networks with Fading Channel,” in Proc. IEEE SICON, pp.197-211, 1997
[13]	S. Murthy, and J. J. Garcia-Luna-Aceves, “An efficient routing     protocol for wireless networks,” in Mobile Networks and Applications - Special issue: routing in mobile communications networks, vol. 1, pp. 183-197, 1996
[14]	C. E. Perkins, and E. M. Royer, “Ad-hoc on-demand distance vector (AODV)routing,” in proceedings of the 2nd IEEE workshop on mobile computing systems and applications, 90-100, 1999.
[15]	Y.-B. Ko and N. H. Vaidya, “Location-aided Routing(LAR) in Mobile Ad Hoc Networks, ”in ACM/IEEE Int’l. Conf. Mobile Comp, pp. 66–75, 1998
[16]	C.-K. Toh, “Associativity-Based Routing for Ad Hoc Mobile Networks,” in Wireless Personal Communications, vol. 4, pp.1-36, 1997. (ABR)
[17]	D. B. Johnson, and D. A. Maltz, “Dynamic Source Routing(DSR) in Ad Hoc Wireless Networks,” in Mobile Computing, vol. 353, pp. 153-181, 1996.
[18]	V. D. Park, M. J.P., and C. M.S., “Applicability of the temporally-ordered routing algorithm (TORA)for use in mobile tactical networks ” in Military Communications conference, vol. 2, pp. 426-430, 1998. 
[19]	R. Dube, C. D.RAIS, K.-Y. WANG et al., “Signal stability-based adaptive routing (SSA) for ad hoc mobile networks ”, vol. 4, pp.   36-45, 1997. 
[20]	Z. J. Haas and M. R. Pearlman, “The Performance of Query Control    Schemes for the Zone Routing Protocol(ZRP), ”in  ACM/IEEE Trans. Net., vol. 9, pp. 427–438,2001