使用GPS动态调整方格流量控制演算法之随意网路.PDF

使用 GPS 動態調整方格流量控制演算法之隨意網路 鍾添曜 陳世偵 李孝治 元智大學資訊工程系 csdchung@.tw, s887428@.tw, s861914@.tw 摘要 行動隨意網路 (Mobile Ad-hoc Network ，MANET) 變數多而且變動迅速 ，因此繞送演算 法的議題一直被廣泛地討論 。位置為基繞送演算法使用衛星定位系統 (Global Position System ，GPS) 使行動主機瞭解彼此的相對位置 ，減少控制封包的氾濫和提升網路頻寬 。 然而 ，位置為基繞送演算法對於遠距離的目的主機 ，依然無法有效解決控制封包過多的 問題 ，因此 ，也有採用方格 (grid) 式繞送或階層式方格繞送以減少控制封包 ，但是跨 方格的封包轉送都要經過叢集管理者 (cluster head) ，造成叢集管理者負載過重 。本篇論 文提出 DGRP (Dynamic Grid Routing Protocol) 繞送演算法 ，動態調整方格大小 ，除維 持路徑選擇的效率 ，也有效地解決叢集管理者負載過重的瓶頸問題 。本論文藉由程式模 擬 DGRP 效能 ，並與固定的方格繞送演算法和隨選式 (on demand) 繞送演算法加以比 較 。 繞送演算法的議題一直被廣泛地討論 。傳統的氾 1. 緒論 濫法 (flooding) 是最快的方法 ，但是也是最沒有 效率的方法 ，它會造成控制封包充斥整個網路 。 不論是桌上型或是可攜式電腦 ，傳統的上網方 對於主機密度高的網路 ，更將嚴重影響網路速度 式是利用有線網路，但是近年來因為架設方便之利 及頻寬 。 用無線網路上網的例子日漸普遍，尤其是可攜式電 其中繞送是否根據位置資訊 ，可以歸納為二 腦搭配無線網路更具備了高行動性的優點。無線網 類 ：拓樸為基 (topology-based) 與位置為基 路又可分為需要基地台 (base station ，BS) 的基礎 (position-based) 。 網路 (infrastructure network) 和沒有基地台的隨 拓樸為基繞送演算法又可分為三類 ：表格驅動 意網路 (ad-hoc network) 。有基地台的基礎網路可 (table driven) 、隨選式 (on demand) 、與混合式 用基地台做路徑的選擇 ，但隨意網路則要靠每一個 (hybrid) 。 行動主機做路徑的選擇。隨意網路主要應用在緊急 表格驅動也稱為主動式 (proactive) ，各行動主 危難時候 ，例如急難救助 、軍事行動 、和臨時性展 機設法偵測其鄰近行動主機的區域繞送資訊 ，並 示場或研討會等，我們無法馬上或因地理因素不適 且週期性與其他行動主機交換區域繞送資訊 ，再 合架設基地台 ，隨意網路就顯得特別的方便 。 根據其他行動主機送來的區域繞送資訊計算出全 域繞送資訊 。維護繞送資訊的成本較高 ，且週期 1.1 相關研究 性交換的控制封包會增加網路負擔 。雖然有些路 徑現在暫時不會被使用 ，但一旦有繞送需求 ，整 MANET 的通訊的方式是使用行動主機 體繞送表可以立即提供繞