43 中華民國電子零件認證委員會其中無線網路的架構又分為 : A d Hoc Mode 和 Infrastructure Mode 兩種, 前者是透過主機 ( 傳送 ) 和主機 ( 接收 ) 以點對點的方式傳送和接收, 不須經過基地台和 AP(Access Point), 而電腦週邊機器只需要無線

Size: px

Start display at page:

Download "43 中華民國電子零件認證委員會其中無線網路的架構又分為 : A d Hoc Mode 和 Infrastructure Mode 兩種, 前者是透過主機 ( 傳送 ) 和主機 ( 接收 ) 以點對點的方式傳送和接收, 不須經過基地台和 AP(Access Point), 而電腦週邊機器只需要無線"

饲衣羿
6 years ago
Views:

1 42 中華民國電子零件認證委員會無線網路隨意路由 (Ad Hoc Routing) 協定概論周育德黃召翔前言在今日這資訊發達的世界中, 無線網路 (Wireless Network) 已經變得越來越重要了, 如何才能使想要傳遞的訊息, 又快又準確到達指定的位置, 以下介紹路由的相關資訊無線 ad hoc network 是以無線通訊來構成一個區域網路的架構, 而這項系統的難題大多在 ad hoc network 要如何去選擇傳送的路徑, 因為 ad hoc network 內的每個用戶都是可動式的, 也就是說每個節點都可以任意進入或離開這個 network, 因此在一個不斷改變的 network 中去尋找一個溝通的路徑及適當的 Routing Protocol 是很重要的在隨意網路中, 因為各節點可以任意行動, 因此在封包傳送過程中可能發生接收節點已經離開傳送節點的傳輸範圍, 因而導致封包在傳遞當中遺失當此種情況發生時, 要偵測出封包遺失需要等待一段長時間, 才能重新開始封包傳遞的作業近年來衛星通訊協定蓬勃發展, 在本篇文章中, 將介紹數種可行之路由協定, 其中包含利用 GPS 的裝置, 從接收到全球定位系統資料中可推測出各節點的位置及速度, 藉由這些資訊, 來推測兩節點何時會離開彼此的傳送範圍, 做為路徑選擇時的參考依據但所推測出來路徑何時會失效, 如何在路徑失效之前找到新的路徑, 讓封包傳輸的過程不致於中斷, 可以有效地降低封包的平均傳輸延遲及封包遺失率, 是目前研究無線網路路由最重要的課題介紹路由器廣義的來說就是我們常聽到的 Hub 或是 IP 分享器, 在網路上傳送或者接收到的封包 ( 訊息 ), 可能都不是從發送端直接送到接收端的, 而是經過無數個路由器, 將封包切割成一定的長度, 並且配合網路位址 (IP address), 再經過幾次的轉傳才到達我們的眼前, 這就好像古時候傳遞訊息的驛站, 須經過幾次的傳遞才能到達指定的地點然而, 現今的傳播顯然與以前的方式大有不同, 在透過路由器就可以收到我們想要的資訊消息等, 而且路由器也會自行找出, 最合適和快速的路徑來傳送訊息路由器是位於 OSI 中的第三層 ( 網路層 ), 主要就是將網路上兩台電腦, 甚至是多台電腦想要傳送的訊息連接在一起, 所以我們才能夠做出傳遞消息資料以及網路分享的原因在了解路由器所扮演的角色之後, 在現今的網路世界中, 並不是只有透過網路連接的方式, 因為無線網路的發展迅速, 現在有不少的人在研究無線網路的路由方法, 就路由的原理來說其連線的方法相同, 可透過路由器來傳送和接收, 但就字面意義來說的確是很容易, 可是要如何做到卻是十分困難的, 因為有線連接方法, 只須透過連線以及 IP 位置, 就能穩定的接收和傳送, 反觀無線網路在這方面反而成了致命傷, 雖然能減少線材佈置的問題, 可是卻犧牲掉傳輸品質因此, 無線網路的技術在現階段只能算熱門並不能說成熟, 所以才會有人仍然在做研究

2 43 中華民國電子零件認證委員會其中無線網路的架構又分為 : A d Hoc Mode 和 Infrastructure Mode 兩種, 前者是透過主機 ( 傳送 ) 和主機 ( 接收 ) 以點對點的方式傳送和接收, 不須經過基地台和 AP(Access Point), 而電腦週邊機器只需要無線網路卡即可做到, 但後者則必須經過無線基地台, 並且必須加上 AP 才能連上無線網路的環境, 因此在學校以及企業較常使用這種方式本文中, 將以 LABAR (Location Area Base Ad Hoc Routing) 和 ABRP(Ad Hoc Backup Node Setup Routing Protocol) 兩種 Routing Protocol 做介紹及比較 Ad hoc 的基本架構 Ad hoc 的 Routing Protocol 可分為三大類, 如下表所示表 1. Ad hoc Routing Protocol 1. Proactive Protocol Proactive Protocol ( 也稱為 Table driven protocol), 每個節點會週期性地傳送或交換 routing information, 並藉由收到的 routing information 來更新 routing table, 當要傳送資料時節點會從 routing table 找出一條傳送路徑 Destination Sequenced Distance Vector Routing (DSDV) Cluster-Head Gateway Switch Routing (CGSR) 和 Wireless Routing Protocol (WRP) 屬於這種 Protocol 因為當節點有封包要傳送時, 可以從 routing table 得知要到達目的地所要走的路徑, 可省去搜尋路徑的時間, 但因為每個節點會週期性的廣播交換訊息, 以來確認 routing table 的正確性, 相對而言會浪費網路的頻寬和電力如果只是為了要拉長交換訊息的週期, 這又會使得 routing table 的正確性下降, 所以 Proactive Protocol 的重要課題, 是如何確保 routing table 的正確性 2. Reactive Protocol Reactive protocol ( 也稱為 source initiation on-demand protocol), 當節點要傳送封包時才會開始去尋找到達目的地的路徑節點會先不斷的廣播 route discovery 的訊息, 一直到找到一條或找到可以用的 r o u t e 後才會停止廣播的動作 Ad hoc On-Demand Distance Vector Routing (AODV) Dynamic Source Routing (DSR) Temporally Ordered Routing Algorithm(TORA) Associativity Based Reuting(ABR) Single Stability Routing(SSR) 就屬於這種 Protocol Reactive Protocol 其優點就是佔用的頻寬資源很小, 只有當行節點要送封包時, 卻找不到路徑的時候才開始, 但要克服的難題是如何減少搜尋路徑的時間 3. Hybrid Protocol: Hybird Protocol 是結合了 Proactive Protocol 和 Reactive Protocol 優點的混合式 Protocol Zone Routing Protocol (ZRP) Zone-Based Hierarchical Link State Routing Dynamic Group Routing Protocol (DGRP) 就屬於這種 Protocol 所有的節點會形成一個區域, 而區域的大小和節點數與設定的區域半徑有關, 所以在區域內是使用 Proactive Protocol, 而區域外是使用 Reactive Protocol 但是

3 44 中華民國電子零件認證委員會 Hybird Protocol 也會面臨著很多困難, 例如區域的選擇和維護以及 Proactive Protocol 和 Reactive Protocol 的合理選擇等問題 LABAR 的架構在 LABAR 裡, 節點會被 GPS 系統歸類為 G-nodes,G-nodes 的功能是在 virtual backbone 中, 可以能互相連絡和提昇在區域網路內的有效率, 並藉由交換訊息來建立 IP 地址清單因此 Virtual backbone routing protocol 的優點, 在 mobile net- work 內只管理某一個區域的集合, 而這些 network 可集合組成一個樹狀結構並藉由 Virtual backbone 來傳遞, 因此 routing information 可以不必將大量的資料傳送到 network 上, 而是只有在 backbone 的連結中傳遞因此 LABAR 是結合了 proactive protocol 與 reactive protocol, 而 Virtual backbone 提供封包使用 directional routing 方式傳到 directional zone 的目的地時, 可使用 G-nodes proactive 的方式傳遞訊息和更新 location information 圖 1. LABAR 的 Virtual backbone 架構 LABAR 的路由架構第一步 LABAR 和 zone 會決定 S-node 屬於那個 G-node,G-node 在建立 zone 時, 會去搜尋還沒被其他 zone 使用的 S- node 來加入自己的 zone, 如果 S-node 已經有所屬的 zone 時,S-node 會拒絕其他 zone 的邀請在 zone 裡的 S-node 會告知附近還沒有 zone 的 S-node, 主動找一個 zone 因此 zone 可由數個 S-node 和一個 G-node 來構成, 而 G-node 會知道 zone 內 S-node 的 ID 第二步是建立一個方便管理的 Virtual backbone 傳遞節點的位置訊息 G-node 在 Virtual backbone 扮演的角色, 是處理區域內的 IP address 當 zone 連接上 Virtual backbone 時, G - n o d e 會從 b a c k b o n e 叫出 r o o t, 而 r o o t 會傳送連結訊息給附近的 z o n e 如果有 zone 還未加入其他系統時, 則會主動邀請這個 zone 加入 Virtual backbone 的系統如果 zone 已加入其他的 backbone, 則會忽略這個訊息最後的 Virtual backbone 系統, 使 G-node 再交換 control information 時比較容易管理在 direction routing 方面, 封包內含有目的地節點的 zone, 而 IP 地址的區域 location 清單是由 G-node 所提供來源端的節點會詢問 Source G-node 來找到目的地的位置,G-node 也會決定到目的地端的 location 位置, 而路徑的決定是由附近的 zone 找到適合的傳送路徑在決定 zone 之後, 當封包傳到中繼 zone 時, 節點會詢問 G-node 來找出附近適合的 zone, 將封包傳送到下一個中繼 zone( 或是最後一個 zone) 當傳送路徑中有一個節點無法 work 時, 來源端會得到這一個錯誤訊息, 此時來源端會找出其他適合的 Virtual backbone, 繼續把封包傳送到目的地

4 45 中華民國電子零件認證委員會在 ad hoc routing 中, 路徑的選擇是重要的一環, 使用 Monte-Carloe 法則來找來源端到目的地的最短距離 LABAR 會以 routing 的平均距離, 和最理想的捷短路徑作比較, 找出最適合的路徑來傳送資料 ABRP 的架構 ABRP 是以 Dynamic Source Routing ( D S R ) 為基礎, A B R P 的 n o - d e m a n d r o u t i n g p r o t o c o l 是以 D S R 為基礎, D S R 不會要求 R o u t i n g t a b l e 和來源端到目的地的路由清單, 但 A B R P 允許中繼的節點從來源端重複地接收傳送 r e q u e s t 封包, 與不斷建立 b a c k u p n o d e s 的資料 A B R P 分成三個部分, Routing Discover Backup Node Setup 及 Route Maintenance, 另外還有三個緩衝區分別為 Fresh Routes cache RD-request cache 和 Backup Routes( 圖 3) ABRP 的路由方法圖 3. ABRP 的結構第一步來源端由 S 送資料到目的地端 D ( 圖四 ), 在 S 會進入 R o u t i n g Discover 從 Fresh Routes cache 尋找, 是否有可以到目的地端 D 的路徑如果有找到 S 便會進入 Route Confirm Process 反之, 沒有找到 S 將會進入 New Routing Discover Process 狀態, 來搜尋找到 D 路徑圖 4. ABRP 路由流程圖在 New Routing Discover Process 中, S 會以廣播 RD-request 的訊息給附近的節點尋找路徑在 R D - r e q u e s t 裡會以 sequence number 來區分 Routing Discover Process, 其所送來的資訊 (S 到 D 的路徑 ) 並會被存入 route content, 而節點也會把 RD-request 的位置存入 route content, 並以廣播 RD-request 的 sequence number 和位置給附近的節點當節點收到由 X 傳來的同一個 sequence number, 節點會先檢查 route content 內是否有這個位置, 如果有的話會清除這個 RD-request 反之, 沒有時會把這位置存入 RD-request 內接著節點會檢查 X 是否有在 RD-request, 有的話會把 X 從 RD-request cache 清除, 並再一次傳送 RD-request 給附近節點的 RD request cache, 沒有 X 時會傳送 RD-request 給附近節點的 RD-request cache 然而 ABRP 和 DSR 是有所不同, 在採用 ABRP 的方式時,route content 在有節點的位置, 與沒有節點的位置可以傳的兩種情況下, 都會先把重覆 RD-request 清

5 46 中華民國電子零件認證委員會除, 因此 ABRP 可以防止永無止境的傳送在目的地端 D 接收到 RD-request 時, 會回覆第一個 RD-request 給來源端 S, 然後在 tolerable time 內等待 RD-request, 然後進入 Backup Node Setup 如果從 Fresh Routes Cache 可以找到目的地端 D 的路徑, 則 S 將會把這個路徑加到 RC-request 中, 然後由這個路徑傳送 RC-request 在傳送 RC-request 時所經過的節點會檢查, 從 Fresh Routes Cache 到 D 的路徑是否比這個路徑好, 如果自己的路徑比較好, 則用自己的路徑傳 ; 如果對方的路徑比較好, 則會把這個路徑存入 RC-request, 並以這個路徑傳下去當 D 收到 RC-request 時, RD-reply 將送回訊息來確定是 S 要建立這個路徑在找到幾個路徑後, 將把這些路徑作比較找出相同的部分, 而這節點將被設定為 Backup Node( 在 S 到 D 的路徑中 ), 這些節點也會被歸入 BS-Packet 中, 目的地端 D 可以用 BS-Packet 來組合出幾條個別的路徑 (Backup Route Cache) 當連結發生錯誤, 在路徑中有個節點不能傳送, 而這個節點也會傳送錯誤訊息給前一個節點, 當 backup node 得知有連結錯誤時, 會從 Backup Route Cache 找出其他的替代的路徑, 並通知 S 更換傳送路徑 Backup Route Cache 會將這個出錯的節點從 backup node 刪除, 如果無法從 Backup Route Cache 找到可替代的路徑, 則 S 也會收到連結失敗的訊息, 並重新回到 Route Discovery 來建立新的路徑所以說 S 無法傳資料到 D 時,S 會把先前所建立的有用路徑存入 Fresh Routes cache, 然後送出 RE-request 的訊息, 當 backup node 收到這個訊息後, 會 Backup Route Cache 內的路徑存入 Fresh Routes cache LABAR 和 ABRP 的差異性 LABAR 是以 proactive protocol 和 reactive protocol 的方式來建立路徑, 而 ABRP 是以 reactive protocol 的方式來建立路徑, 所以 proactive protocol 的優點是會週期性的更新 routing information, 因此當有某個節點無法工作時,proactive protocol 可以快速的得知並更新路徑, 雖然 ABRP 有 Backup Route 的功能, 但如果沒有其他可以替代的路徑時, 必須重新尋找路徑而浪費了不少時間因此 proactive protocol 必須不斷的更新, 所以當網路的規模變大時, 相對的 proactive 所需的頻寬也會變大而 L A B A R 為了解決這個問題, 所使用 Hybrid 和 geographical routing protocol, 但 Hybrid protocol 是結合 proactive protocol 和 reactive protocol,proactive protocol 則是用在區域網路, 因為區域網路的規模不會很大所以解決了頻寬的問題,reactive protocol 是用在遠端的傳送然而 geographical routing protocol 主要是用來找節點的路徑或傳送訊息, 但 geographical routing protocol 必須靠 GPS 來實現, 而 GPS 的價格昂貴和耗電大如果網路規模不大和經濟的考量下, ABRP 會比 LABAR 適合, 如果要解決 ABRP 找不到路徑的問題, 可以在區域間建立幾個固定的節點, 而且 ABRP 有 Backup 的功能, 如果至少有一條固定且故障率低的路徑, 則可以減少找不到路徑的風險結論在本文開始提到了關於有線和無線網路的架構和路由方法在有關 Ad Hoc Routing Protocol 的兩種介紹和比較, 以及其優缺點的說明在本文中不斷強調的就是如何快速且正確的接收傳送訊息, 除了基本的路由條件和架構上的問題, 還有必需要克服網路管理, 防毒及網路安全性等的幾項問題

6 47 中華民國電子零件認證委員會名詞說明 1.S-node: 在 ad hoc 中節點分為 G-node 和 S-node 兩種,S-node 和 G-node 的差異為 G- node 把知道的 location 提供 S-node 知道, 也就是說 S-node 必須從 G-node 取得地址清單 2.Zone: 每個 S-node 都有一個所屬的 location area 或在 G-node 的 zone 內,zone 是由一個 G-node 和數個 S-node 所組成的 3.adjacent zone:zone 藉由 S-node 或 G - n o d e 連結到附近的 z o n e, a d j a c e n t zone 是由所有 G-node 所組成的 zone 之清單,adjacent zone 也包括 location 4.N ni zj:n 是指用戶端的節點, ni 是表示 i 的節點,zj 是表示 j 的節點 5.Source G-node:Source G-node 是指 G-node 所在的來源端,zone formation process 的區域是由 G-node 和 S-node 所構成的 6.Route Discovery Request (RDrequest): 從來源端到目的地尋找路徑並記錄在 route content 7.Route Confirm Request (RCrequest): 由 Fresh Routes cache 重新建立來源端到目的地的路徑 8.Route Discovery Reply (RD-reply): 由目的地端回覆 route content 給來源端 9.backup setup Packet (BS- Packet): 目的地端傳送 backup 的訊息來備分節點以建立 backup routes 10.Route Erasure Request (RErequest): 由來源端來決定清除沒有用的路由訊息參考文獻 1. E.M. Royer, and C-K. Toh, A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks, IEEE Personal Communications, pp , April X. Cheng, and D-Z. Du, Virtual Backbone-Based Routing in Multihop Ad Hoc Wireless, submitted to IEEE Transactions on Parallel and Distributed Systems, C. E. Perkins and P. Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, Comp. Commun. Rev., Oct. 1994, pp S. Basagni, I. Chlamtac, and V.R. Syrotiuk, A Distance routing Effect Algorithm for Mobility (DREAM), ACM/ IEEE International Conference on Mobile Computing and Networking (MobiCom 98), pp , October T. Camp, J. Boleng, B. Williams, L. Wilcox, and W. Navidi, Performance Comparison of Two Location based Routing Protocols for Ad hoc Networks, Proceedings of INFOCOM 2002, pp , June B. Liang, and Z.J. Haas, Virtual Backbone Generation and Maintenance in Ad Hoc Network Mobility Management, Proceedings of Infocom 2000, pp , March 2000.

计算机网络概论

计算机网络概论 1 repeater bridge router gateway V.S OSI Repeater(Hub) 1 Repeater 2 3 ( Hub 4 Bridge 1 Bridge 2 N N DL1 DL1 DL2 DL2 Ph1 Ph1 Ph2 Ph2 1 2 Bridge 3 MAC Ethernet FDDI MAC MAC Bridge 4 5 6 7 50873EA6, 00123456

43 中華民國電子零件認證委員會 其中無線網路的架構又分為 : A d Hoc Mode 和 Infrastructure Mode 兩種, 前者是透過主機 ( 傳送 ) 和主機 ( 接收 ) 以點對點的方式傳送和接收, 不須經過基地台和 AP(Access Point), 而電腦週邊機器只需要無線

43 中華民國電子零件認證委員會其中無線網路的架構又分為 : A d Hoc Mode 和 Infrastructure Mode 兩種, 前者是透過主機 ( 傳送 ) 和主機 ( 接收 ) 以點對點的方式傳送和接收, 不須經過基地台和 AP(Access Point), 而電腦週邊機器只需要無線