摘 要

目前無線行動網路(Wireless Network)是新穎而且非常實用的網路通訊系統，在無線行動網路上的每一個節點都可以自由的任意移動也可以自由的交談或是傳輸封包，所以無線行動網路會比傳統固定式的網路或是有線網路，面臨到更多連結失敗或錯誤的可能性。
一般傳統的無線行動網路都是利用固定基地台的模式來完成兩個移動端點之間的傳輸資料與連結。而無線特殊網路(Wireless Ad Hoc Network)是無線行動網路之中的一個傳輸協定，無線特殊網路(Wireless Ad Hoc Network)與一般的無線網路最大的不同點是在於它不需要固定的基地台設備，而是在其通訊範圍內的行動節點中選出某幾個為其中的行動基地台。
無線特殊網路(Wireless Ad Hoc Network)之中又以其選徑方式分為路由表驅動法(Table Driven)與需求驅動法(On-demand Driven)，而table driven的方式中有常見的Destination-Sequence Distance-Vector Routing(DSDV)、Cluster Switch Gateway Routing(CSGR)，而另一個On-demand Driven的方式中有常見的Dynamic Source Routing(DSR)、Ad hoc On-Demand Distance Vector Routing(AODV)等，本文依Table Driven的方式中的Cluster Switch Gateway Routing ( CSGR )來探討cluster head遺失的問題與選出方式。CSGR則是利用多個端點群聚成一個群，並由這個群中選擇出一個端點為Cluster Head當這個群組全部節點要傳送資料與接收資料的群組路由器，並且用它來跟其他群組連結。
在此，發現其中的問題點是當其Cluster Head因為走動而離開本身的群組時，並無任何演算法能夠及時的傳達群組內的行動節點Cluster Head已經離開，而是等節點傳送出封包時，才發現Cluster head已經離線導致本身的行動節點無法送達其Cluster Head。原本封包送回到此行動節點或收到錯誤訊息時才發現問題，而發生問題後就其區域內存在的節點使用廣播的方式選出新的Cluster Head，但其廣播會發生廣播風暴的問題所以不符合效率。因此這個論文中，本實驗深入討論這個問題並提出一個預防Cluster Head遺失的Cluster Head取代策略演算法。演算法是透過全球衛星定位系統( GPS )的輔助來了解知道群組內每一個行動節點的座標後，在以本文所提出的Cluster取代策略演算法修改其原本Cluster Switch Gateway Routing ( CSGR )協定，將使得群組內的Cluster Head能在離開自己範圍前預先重新選出新的Cluster Head或在當Cluster Head無預警的關機後重新選則出新的Cluster Head。

Abstract

Currently, wireless Network is something new and highly effective in Internet Network System. Every mobile device in wireless network is free to move and communicate. In addition, it also allows packet transmission. However, for those factors above, Wireless Network has higher possibility to failure in connecting with the Internet than which in Traditional Fixed Network or Wire network.
Normally, in conventional Wireless Network, data transmission and linking between two nodes need to use a standard fixed base operation station, i.e., access point (AP). Wireless Ad Hoc network is part of transmission protocols in Wireless Network. The most remarkable distinction in Wireless Ad Hoc other than Wireless Network is that it designates several nodes within the communication range as the mobile base operation station instead of using paraphernalia such as standard fixed base operation station.
The Routing Methods of Wireless Ad Hoc Network can be categorized into two ways, i.e.: Table-Driven and On-Demand-Driven. In Table-Driven method, DSDV and CSGR are the most frequently used; whereas in On-Demand-Driven method, DSR and AODV are the most often used.
This thesis will study the Ad Hoc routing algorithm, Cluster Switch Gateway Routing (CSGR) of the Table-Driven method, particularly focusing in the failure of the Cluster Head and the solution to the problems.
CSGR uses nodes that group into a cluster, from which a node is selected as the cluster head to facilitate data transmission. On top of that, the function of the cluster head is to connect one group with the others.
However, one limitation from this Cluster Head is that when it moves out of the group, there are no algorithms to notify the other nodes within the Cluster. Because of that, other nodes will not be able to do data transmission and error message will be shown.
When this malfunction occurs, that group of nodes will reveal a new cluster head. However this action will lead to the commotion of broadcasting, as well as causing inefficiency.
Therefore, in this thesis we will discuss this issue and find an alternative solution to tackle this problem.

With our algorithm, GPS recognizes the coordination of each mobile node that belongs to the group mentioned above.

The substitution strategy on this thesis will revise the original CSGR protocol, which can select the new cluster head before it move out from its group or when the computer shutdown without warning.

目 錄 頁次
中文摘要..……………………………………………………………………………….……..Ⅰ
Abstract……………………………………………………………………………………..III
誌 謝…………………………………………………………………………………………….V
目 錄……………………………………………………………………………...........VI
圖目錄……………………………………………………………………………………....VIII
表目錄………………………………………………………………………………….........X
第一章 緒論………………………...........................................1
1.1 研究背景與動機………………………………………………………………..…….....1
1.1.1 Ad Hoc網路的概念………………………………………………………….........1
1.2 Ad Hoc網路的特點……………………………….............................3
1.2.1 Ad hoc網路的獨立性……………………………………..………………….......4
1.2.2 行動節點動態變化的網路拓撲架構…………………….…………….……........4
1.2.3 有限的無線通信帶寬……………………………………..…………………........5
1.2.4 有限的主機能源……………………………………..………………………........5
1.2.5 網路的分佈式特性……………………………………..……………………........6
1.2.6 生存週期短………………………………………..…………………………........7
1.2.7 有限的物理安全……………………………………..………………………........7
1.3 Ad Hoc網路的應用需求……………………………………………………………......7
1.4與其他移動通信系統的比較………………………………………………………........9
1.4.1 蜂窩系統………………………………………………………………..……........9
1.4.2 集群系統………………………………………………………………….….........9
1.4.3 衛星通訊系統…………………………………………………………….….........9
1.5 Ad Hoc網路常見的選徑方式…………………………………………………….......10
1.6 常見的Ad Hoc routing問題….………………………………………………….....12
1.7 論文架構……………………………………................................13
第二章 Cluster Switch Gateway Rousting(CSGR) ……………………….…….…14
2.1 Cluster………………………………...................................14
2.2 通訊架構………………………………………………………………………….......15
2.2.1 Cluster結構………………………….…………………....................16
2.2.2 Routing結構…………………………….………………………….............19
2.2.2.1 Intra-Cluster Routing…………………………………….…………......20
2.2.2.2 Inter-Cluster Routing…………………………………….…………......20
2.2.2.3 Cluster & Internet Routing…………………….……………………....21
2.3 Cluster Head的問題與LCC演算法...…………….…………………...........23
第三章 以GPS為基礎的Cluster Head選擇方式……………………….………………….24
3.1 Cluster Head的選擇方式……………………………….…………………………...24
3.2 Cluster Head的遺失偵測與演算法……………………….……………..........27
3.3 Cluster Head取代策略演算法……………………………………………………....29
第四章 模擬軟體與實驗分析……………………….…………………................33
4.1 實驗模擬模型………………….………………………........................33
4.1.1 Cluster Switch Gateway routing的模型建立…………………..........33
4.1.2 Cluster取代策略的加入……………………….………………….............35
4.2 實驗的評估方式………………….…………………..........................38
4.3 實驗的模擬軟體說明………………….…………………......................39
4.4 實驗結果與分析………………….…………………..........................41
第五章 結論……………………….………………….............................54
參考文獻……………………….…………………...............................57
作者簡介………………………...…………………………………………………………….60

參考文獻
[1]D. Johnson, D.A. Maltz, and J. Broch, 2002, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks , in MANETWorking Group. IETF, Internet Draft.
[2]C.-C. Chiang, "Routing in Clustered Multihop, Mobile Wireless Networks withFading Channel" Proc. IEEE SICON'97, Apr.1997
[3]J. Jubin and J.D. Tornow. The DARPA packet radio network protocols. Proceedings of the IEEE, 1987.
[4]David A. Beyer. Accomplishments of the DARPA Survivable Adaptive Networks SURAN Program. In Proceedings of the IEEE MILCOM Conference, 1990.
[5]Barry M. Leiner, Robert Ruth, and Ambatipudi R. Sastry. Goals and Challenges of the DARPA GloMo Program. IEEE Personal Communications, Vol.3, No.6, 1996.
[6]J.Broch, D.A. Maltz, D.B. Johnson,Y-C. Hu, and J. Jetcheva, A Performance comparison of multi-hop wireless Ad Hoc network protocols, Proceeding of the MobiCom’98, 1998.
[7]A.K. Salkintzis and C. Chamzas, "Mobile Packet Data Technology: An Insight into MOBITEX Architecture," IEEE Personal Communications Magazine, February 1997.
[8]K.C. Chen, "Medium Access Control of Wireless LANs for Mobile Computing," IEEE Network, September/October 1994.
[9]William A. Arbaugh,Narendar Shankar,and Y.C. Justin Wan, "Your 802.11 Wireless Network has No Clothes"Department of Computer ScienceUniversity of Maryland College Park, Maryland 20742,2001.
[10]B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: an Energy-E_cient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. In Proc. 7th ACM MOBICOM, Rome, Italy, Jul. 2001.
[11]S. Singh, M. Woo, and C. S. Raghavendra, “Power aware routing in mobile ad hoc networks,” in Proceedings of ACM MOBICOM, 1998.
[12]陳偉文, “行動特殊網路移動性評估之隨選式路徑選擇演算法”, 國立東華大學資訊工程研究所, 2001.
[13]張順傑,”安全多點傳輸在隨意網路下之實作”, 國立成功大學電機學系, 2004.
[14]Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols. In Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom'98), October 1998.
[15]王及德, ”用於蜂巢式無線區域網路之擬亂碼與通道聯合指派” , 國立清華大學電機工程學系,1996.
[16]王馥昶, ”無基礎架構的無線網路下減少隱藏主機效應之加強型媒體存取控制協定”, 國立交通大學資訊科學系,2000.
[17]唐敏聰, ” 衛星通訊實驗課程之設計”, 國立高雄應用科技大學電子與資訊工程研究所, 2004.
[18]Woo-Jin Choi,Sirin Tekinay,"An Efficient Table Driven Routing Algorithm For Wireless Ad Hoc networks", New Jersey Center for Wireless Telecommunications New Jersey Institute of Technology Newark, NJ, USA, 1982.
[19]Jyoti Raju and J.J. Garcia-Luna-Aceves, "A Comparison of On-Demand and Table Driven Routing for Ad-Hoc Wireless Networks", Baskin School of Engineering University of California, 2000.
[20]C.E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers", Comp. Comm. Rev., Oct. 1994.
[21]C.-C. Chiang, "Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel" Proc. IEEE SICON'97, Apr.1997.
[22]C.-C. Chiang, "Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel" Proc. IEEE SICON'97, Apr.1997.
[23]David B. Johnson, Davis A. Maltz, "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks" October 1999.
[24]Charles E. Perkins, Elizabeth M. Royer, Samir R. Das, "Ad Hoc On-demand Distance Vector Routing", October 99 IETF.
[25]T. Clausen, Ed. and P. Jacquet, Ed., “ Optimized Link State Routing Protocol (OLSR)”, Project Hipercom, INRIA, October 2003.
[26]Richard Ogier, Fred Templin, Bhargav Bellur and Mark Lewis, "Topology Broadcast Based on Reverse-Path Forwarding (TBRPF)", IETF MANET WG Meeting, 2002
[27]Yih-Chun Hu, David B. Johnson, “Caching Strategies in On-Demand Roiting Protocols for Wireless Ad Hoc Networks”, computer science department Carnegie Mellon University,2000.
[28]李龍盛,王偉讚, “Clustering in Mobile IP for Mobile Ad Hoc Network”, 國立嘉義大學資訊工程研究所, 2003.
[29]Xiaoyan Hong, Kaixin Xu, and Mario Gerla, "Scalable Routing Protocols for Mobile Ad Hoc Networks", at UCLA, 1999.
[30]官淑芬, ”在隨意無線網路中的位置估測方法”, 中華大學資訊工程學系, 2003.
[31]黃億祥, ”在隨意網路中具服務品質保證的分散式多重路徑繞徑之研究”, 國立中山大學資訊工程學系研究所, 2001.
[32]University of California Los Angeles Computer Science Department Parallel Computing Laboratory and Wireless Adaptive Mobility Laboratory, GloMoSim : A Scalable Simulation Environment for Wireless and Wired Network Systems, http://pc1.cs.ucla.edu/projects/glomsim/