Please use this identifier to cite or link to this item:
標題: Ad Hoc無線網路中利用ID重置技術建構最小省電Connected Dominating Set的區域演算法
A Localized Algorithm Using ID-Reassignment Technique to Construct Power-Aware Minimum Connected Dominating Set for Ad Hoc Network
作者: 陳俊榮 
Chen, Jyun-Rong 
關鍵字: Ad Hoc network;Ad Hoc無線網路;Routing;Connected Dominating Set;Power-Aware;繞徑;Connected Dominating Set;省電
出版社: 資訊科學系所
引用: [1] T. Acharya and R. Roy, “Distributed Algorithm for Power Aware Minimum Connected Dominating Set for Routing in Wireless Ad Hoc Network,” in Proc. International Conference on Parallel Processing Workshops (ICPPW’05), pp. 387-394, 2005. [2] K. M. Alzoubi, P. J. Wan, and O. Frieder, “New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks,” in Proc. 35th Hawaii International Conference on System Sciences, pp. 1-7, 2002. [3] S. Basagni, “Distributed Clustering for Ad Hoc Networks,” in Proc. of International Symposium on Parallel Architectures, Algorithms, and Networks, pp. 310-315, 1999. [4] J. Broch, D.Johnson, and D.Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks,” IETF, Internet Draft,, 1988. [5] I. Cidon and O.Mokryn, “Propagation and Leader Election in Multihop Broadcast Environment,” in Proc. 12th International Symposium on Distributed Computing (DISC98), pp.104-119, 1998. [6] F. Dai and J. Wu, “Distributed Dominant Pruning in Ad Hoc Wireless Networks,” in Proc. IEEE International Conference on Communications (ICC), pp.353-357, 2003. [7] B. Das and V. Bhargavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets,” in Proc. IEEE International Conference on Communications (ICC ''97), pp.376-380, 1997. [8] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1997. [9] M. Gerla and J. Tsai, “Multicluster, Mobile, Multimedia Radio Network,” ACM/Baltzer Journal of Wireless Networks, vol. 1. no. 3, pp.255-265, 1995 [10] B. Han, H. Fu, L. Lin, and W. Jia, “Efficient Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” in Proc. IEEE International Conference on Mobile Ad-hoc and Sensor Systems, pp.570-572, 2004. [11] C. Hedrick, “Routing Information Protocol,” Internet Request for Comments (RFC) 1058,, 1988. [12] W. K. Liao, Y.C. Tseng, and J.P. Sheu, “GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks,” Telecommunication Systems, A Special Issue on Wireless Networks, vol. 18. no. 1, pp.37-60, 2001. [13] C. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, vol. 15. no. 7, pp.1265-1275, 1997. [14] T. Lin, S. Midiff, and J. Park, “Minimal Connected Dominating Set Algorithms and Application for a MANET Routing Protocol,” in Proc. IEEE International Performance, Computing, and Communications Conference, pp.157-164, 2003. [15] J. McQuillan, I. Richer, and E. Rosen, “The New Routing Algorithm for ARPANET,” IEEE Trans. Commun., vol. 28. no 5, pp. 711-719, 1980. [16] J. McQuillan and D. Walden, “The ARPA Network Design Decisions,” Computer Networks, vol. 1, no. 5, pp. 243-289 , 1977. [17] J. Moy, “OSPF Version 2,” Internet Request For Comments RFC 1247, http://www.faqs. org/rfcs/rfc1247.html, 1991. [18] C. Perkins and E. Royer, “Ad Hoc on Demand Distance Vector Routing,” in Proc. 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp. 90-100, 1999. [19] C. Perkins and E. Royer, “Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers,” in Proc. ACM Specical Interest Group on comm.. (SIGCOMM ’94), pp.234-244, 1994. [20] T. S. Rappaport, Wireless Communications: Principles & Practice, Prentice Hall, 2002. [21] P. Sheu and Y. Lee, “On Calculating Stable Connected Dominating Sets Base on Battery Power for Mobile Ad Hoc Networks,” in Proc. International symposium on Communications, 2003. [22] I. Stojmenovic, M. Seddigh, and J. Xunic, “Dominating Sets and Neighbor Elimination Based Broadcasting Algorithms in Wireless Networks, ” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 1, pp.14-25, 2002. [23] P. Wan, K. Alzoubi, and O. Frieder, “Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” Journal of Mobile Networks and Applications, vol. 9, no. 2, pp.141-149, 2004. [24] J. Wu and H. Li, “On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks,” in Proc. 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7-14, 1999. [25] J. Wu, M. Gao, and I. Stojmenovic, “On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks,” Journal of Communications and Networks, vol. 5, no. 2, pp.169-178, 2002. [26] 賈坤芳, 江茂綸, 陳俊榮, “利用區域演算法將ad hoc無線網路下之Connected Dominating Set 最小化,” 全國計算機會議, 2005.
在ad hoc無線網路的一個重要議題就是如何在一群行動裝置中,作最有效率的繞徑。而以connected dominating set (CDS)為基礎的繞徑方式,被認為是非常好的方法,其主要的優點就是可以把CDS當作一個virtual backbone,便能迅速地適應網路拓樸(network topology)的改變,且非CDS的成員亦可進入省電模式,減少無謂的耗電。一般來說,CDS的成員除了要儲存繞徑資訊外,還要處理資料傳輸,所以會損耗較多的電量。所以當CDS的成員電力耗盡時,會造成網路生命週期隨之中止。先前研究以求得較少的gateway數,去建立一個精簡的virtual backbone;亦有考慮電力條件建構CDS來延長網路生命週期,但卻無法同時得到較佳的結果。本研究提出一個區域演算法,將電力用於id重新分配(id reassignment)技術中,求得一個gateway個數較少的CDS。由於這些gateway具有高電量的特性,所以生命週期也較長。此外,本文還提出復原(recovery)方法,針對網路上的各種狀況作應變。經由實驗顯示我們提出的新方法,不但找到較其它方法小的CDS,亦得到較長的生命週期。
其他識別: U0005-1107200616123200
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.