UTokyo Repository 東京大学

UTokyo Repository >
113 工学系研究科・工学部 >
22 電気系工学専攻 >
1132225 修士論文(電気系工学専攻) >

このページ(論文)をリンクする場合は次のURLを使用してください: http://hdl.handle.net/2261/49879

タイトル: Pro-Reactive Route Recovery and Automatic Route Shortening in Wireless Ad Hoc Networks
その他のタイトル: 無線アドホックネットワークにおけるプロ・リアクティブ型ルート回復と自動ルート短縮
著者: Liang, Zilu
著者(別言語): リャン, ジールー
発行日: 2011年9月27日
抄録: This thesis mainly addresses two problems in wireless ad hoc routing: route failure and route redundancy. Route failures occur frequently in ad hoc networks due to their highly dynamic topology as well as their unstable wireless communication medium. Existing route recovery methods lead to long latency and large control overhead. We proposed a novel relay recovery route maintenance protocol RELREC for ad hoc networks to combine the benefits of both proactive and reactive routing protocols and to minimize their drawbacks. In our proposal, one or more substitute routes usually become ready for the recovery of every link in a route before its break, while the route recovery process actually starts only when the upstream node of a link confirms that the link really breaks. Since this scheme does not broadcast any control packet, it can effectively recover a broken link without heavy control overhead traffic. Also, it helps reduce the time delay due to the recovery, since substitute routes are already available when the upstream node initiates the route recovery process. However, the route recovered by RELREC is usually longer than the original one. In fact, route redundancy occurs frequently in ad hoc networks due to highly dynamic topologies. In order to improve the integrated performance of an ad hoc network, we proposed two automatic route shortening strategies to optimize the route length in the network: relay route shortening and active route shortening. While relay shortening can only be initiated by the Relay Nodes in pro-reactive relay recovery processes, active shortening can be launched by any node whenever it overhears a shorter route from its neighbors. Note that the information in Relay Tables is only utilized in route recovery process in RELREC. In order to utilize the Relay Table information to the possible extent to further reduce the control overhead, we extended the usage of Relay Table to route discovery process by incorporating Relay Table information into gossip algorithm, and proposed Relay Gossip Routing (RGR). In RGR, only Relay Nodes are allowed to rebroadcast under a gossiping probability, which differs from existing gossip methods. The simulation study in ns-2 simulator has demonstrated clearly that our proposed RELREC scheme effectively reduces the average end-to-end time delay by up to 49% and 31%, and the normalized control overhead by up to 17% and 28% compared with the previous algorithms AODV and DRRS respectively in the best cases. According to the simulation results, the data delivery ratio by our proposed scheme is close to DRRS and AODV. The simulation results confirm that our proposal can provide quick and low-cost route recovery without degrading the packet delivery ratio, while it is adaptive to node mobility and traffic load. When it comes to the automatic route shortening algorithms, active shortening works more effectively than relay shortening does, leading to by far the shortest average route length and the smallest end-to-end time delay among all the algorithms in the simulation. However, the slightly larger control overhead traffic and relatively lower packet delivery ratio harms the performance of active route shortening. In the evaluation of RGR, in order to find the appropriate gossiping value for the Relay Nodes, we firstly studied the relation between packet delivery ratio and gossiping probability p. It is shown that the packet delivery ratio equals or is even higher than that of p = 1 when the value of p is larger than a certain point lying between 0.35 and 0.45; at the same time the total control overhead is smaller than that of p = 1. Accordingly, the gossiping probability is set to 0.5 in the performance evaluation of RGR. Simulation results confirm that RGR successfully reduces the normalized control overhead by up to 17% in the best case compared to RELREC, and ensures a similar performance to RELREC in terms of the packet delivery ratio. Although the basic gossip routing yields the lowest normalized control overhead, it yields the worst performance in terms of the packet delivery ratio. It is conspicuous that RGR strikes a better balance between control overhead and packet delivery ratio than basic gossip routing does. Besides, RGR also outperforms basic gossip routing in terms of average time-to-time end delay and average route length.
内容記述: 報告番号: ; 学位授与年月日: 2011-09-27 ; 学位の種別: 修士 ; 学位の種類: 修士(工学) ; 学位記番号: ; 研究科・専攻: 工学系研究科電気系工学専攻
URI: http://hdl.handle.net/2261/49879
出現カテゴリ:1132225 修士論文(電気系工学専攻)
025 修士論文


ファイル 記述 サイズフォーマット
37096967.pdf2.41 MBAdobe PDF見る/開く



Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - ご意見をお寄せください