以分散式雜湊機制設計無線隨意網路之需求遶徑協定

Distributed Hashing Mechanisms for On-demand Routing Protocol in Wireless Ad Hoc Networks

張兆村(Chao-Tsun Chang)

《修平學報》 22期 (2011/03) Pp. 105-124

https://doi.org/10.29548/BGYY.201103.0007

摘要

在無線的Ad Hoc Network中，需求遶徑協定(On-demand Routing Protocols)是一種利用封包達到即時尋找及建立通訊路徑的協定。在先前以DSR為基礎的相關研究[1][2][5][8][9]中，遶徑找尋(Route Discovery)通常會為探知網路的現況而產生大量的需求封包，但也因此完成有用資訊的收集，以做為未來遶徑決策（如最短路徑計算）的依據。然而，通信裝置上的大量遶徑快取(Routing Cache)需求，將因此大幅增加空間需求及遶徑計算的複雜度。本篇論文將提出一個新的分散式雜湊遶徑協定(Disributed Hashing Routing Protocol; DHRP)，此協定藉由雜湊式快取(Hashing Cache)方式以降低主機快取需求量及遶徑計算的複雜度。經實驗效能之結果顯示，所提出的協定相較於相關研究，具有明顯地降低快取儲存體之需求量、遶徑計算之複雜度、重新遶徑所產生的控制封包之負擔、及平均遶徑長度等的優點。

關鍵字

雜湊 ； 雜湊式遶徑 ； 需求遶徑 ； 無線隨意網路

並列摘要

In wireless ad hoc network, on-demand routing protocols are proposed for discovering and establishing a route only when a source host originates a data packet addressed to the destination host. In the DSR-based study [1][2][5][8][9], route discovery usually raises a large number of request packets for exploring the current state of the network, but it also performs the collection of useful information for the future routing decisions, such as the computations for the shortest path. However, large routing caches in devices will increase the spatial and routing complexities. This paper presents a novel distributed hashing routing protocol (DHRP) by applying the hashing cache scheme to reduce the cache size of the hosts and the routing complexity. Performance results reveal that the proposed protocol significantly reduces the required size of cache storage, increases routing complexity and reduces the control packet overhead for rerouting and the average route length.

並列關鍵字

hash ； hash-based routing ； on-demand routing ； ad hoc network

參考文獻

D. Johnson and D. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks”, Computer Communications Review Proceedings of SIGCOMM 96’, Aug. 1996.

Yi-Chun Hu and David B. Johnson, “Caching Strategies in On-Demand Routing Protocols For Wireless Ad Hoc Networks”, Proceedings of the 5th International Conference on Mobile Computing and Networking (MobiCom）, pp.231-242, 2000.

Koji Nakano, Stephan Olariu, “Randomized Initialization Protocols for Ad Hoc Networks”, IEEE Transactions on Parallel and Distributed Systems, Vol.11, No.7, pp. 749-759, 2000

Vincent D. Park and M. Scott Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks”, Proceedings of INFCOM, pp.1405-1413, April 1997.

Marcelo Spohn and J. J. Garcia-Luna-Aceves, “Neighborhood Aware Source Routing”, Proceedings of the 6th International Conference on Mobile Computing and Networking (MobiCom）, pp.11-21, 2001.