[[alternative]]Energy efficient paths analysis in wireless ad hoc network

碩士[[abstract]]在無線隨意網路中，所有裝置都是倚賴電池來維持動力。當無線裝置傳輸狀態時，耗電量是最大的。傳統無線隨意網路中，選徑協定在有資料要傳輸時尋找一條傳輸路徑，而所找到的傳輸路徑往往是使用最少跳躍次數的路徑。由於傳輸所需電力與距離平方成正比，所以最短路徑可能並不是最省電的路徑。 本研究旨在計算出在整體網路中任意兩節點間的多重傳遞路徑中，最為省電的一條。藉由限制各節點的分支度，並以距離平方和最小為目標，找出一條可能花費較小電力的一條路徑，以減少傳輸狀態時的電力消耗。[[abstract]]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.[[tableofcontents]]目錄 第一章 緒論 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[[note]]學號: 695420439, 學年度: 10