將感測網路切割成貪婪區塊的分散式演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：18.190.152.38

姓名

黃彥宸(YEN-CHEN HUANG) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

將感測網路切割成貪婪區塊的分散式演算法
(Localized GRR Decomposition for Wireless Sensor Networks)

相關論文

★ Dynamic Overlay Construction for Mobile Target Detection in Wireless Sensor Networks	★ 車輛導航的簡易繞路策略
★ 使用傳送端電壓改善定位	★ 利用車輛分類建構車載網路上的虛擬骨幹
★ Why Topology-based Broadcast Algorithms Do Not Work Well in Heterogeneous Wireless Networks?	★ 針對移動性目標物的有效率無線感測網路
★ 適用於無線隨意網路中以關節點為基礎的分散式拓樸控制方法	★ A Review of Existing Web Frameworks
★ 無線網路上Range-free的距離測量	★ Inferring Floor Plan from Trajectories
★ An Indoor Collaborative Pedestrian Dead Reckoning System	★ Dynamic Content Adjustment In Mobile Ad Hoc Networks
★ 以影像為基礎的定位系統	★ 大範圍無線感測網路下分散式資料壓縮收集演算法
★ 車用WiFi網路中的碰撞分析	★ Exploring Spatial-Temporal Cloaking Against Correlation Attacks for Location-based Services

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在地理性路由(geographic routing)中，每個節點(node)都選擇鄰居之中離目的節點(destination)最近的作為轉送的下一個節點。這種轉送(forwarding)的方式稱之為貪婪轉送(greedy forwarding)，同時此種方法在成功實施的情況下也被證明為會近似最短路徑。然而貪婪轉送遇到局部極小(local minima)的情況時，會因為死路(dead end)的發生而無法繼續進行傳送。此問題可透過將整個網路分割成可單獨執行貪婪轉送的區塊來改善。以往的網路分割演算法大多為集中式，而集中式的演算法會存在傳輸訊息壅塞以及單點故障(single point of failure)的問題。在本論文，我們設計一個分散式的演算法Localized GRR Decomposition (LGD)來對整個網路進行貪婪區塊(Greedily Routable Region)的切割。在亂數產生網路中，我們的演算法與已知的演算法比較可產生更少的貪婪區塊。此外，LGD演算法也會因為分散式演算法的特性，使得分割所需的溝通負擔(overhead)減少。

摘要(英)

In geographic routing, a node selects the neighbor closest to the destination to forward the packet. This scheme is known as the greedy forwarding, and has been shown to produce sub-optimal route when it works. However, the greedy forwarding may fail if the packet is forwarded to a local minimum. One way to solve this issue is to partition the network into a number of pieces. Within each piece, the greedy forwarding scheme is guaranteed to work. The network partition algorithms proposed in the past are centralized, which naturally suffer from message congestion and the single point of failure. In this thesis, we propose a distributed algorithm, namely Localized GRR Decomposition (LGD), to partition the network into a number of greedily routable regions. Using randomly generated sensor networks, we show that our algorithm is able to produce a lower number of GRRs when compared with the best known result. Additionally, the communication overhead of our LGD algorithm is lower due to its distributed nature.

關鍵字(中)

★ 無線感測網路
★ 路由

關鍵字(英)

★ Routing
★ Wireless Sensor Networks

論文目次

中文摘要 i
英文摘要 ii
一、介紹 1
二、相關文獻 3
三、Localized GRR Decomposition (LGD) 11
3.1 Cutpoint-Discovery 11
3.2 Network-Decomposition 14
3.3演算法的正確性 20
四、效能評估 23
4.1隨機產生網路 23
4.2環境複雜度 24
4.3效能評估 24
五、結論與未來展望 35
參考文獻 36

參考文獻

[1] R. Szewczyk, A. Mainwaring, J. Anderson, and D. Culler, “An analysis of a large scale habit monitoring applicarion,” in Proc. ACM SenSys, 2004.
[2] T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, and et al., “An energy-efficient surveillance system using wireless sensor networks,” in Proc. ACM MobiSys, 2004.
[3] S. Kumar, T. H. Lai, and A. Arora, “Barrier Coverage with Wireless Sensors,” in Proc. ACM MobiCom, 2005.
[4] C. E. Perkins and E. Bhagwat, “Highly dynamic destination-sequenced distance-vextor routin(DSDV) for mobile computer,” in Proc. ACM SIGCOMM, 1994.
[5] T. Clausen et al, “Optimized link state routing protocol,” IETF Internet Draft , 2003.
[6] D. Johnson and D. Maltz, “Dynamic source routing in ad hoc wireless networks,” in Proc. ACM Mobicom, 1996.
[7] C. Perkins and E. M. Royer, “ad hoc on-demand distance vector routing,” in Proc. IEEE WMCSA, 1999.
[8] V. D. Park and M. S. Corson, “A highly adaptive distributed routing algorithm for mobile wireless networks,” in Proc. IEEE INFOCOM, 1997.
[9] P. Bahl and V. N. Padmanabhan, “RADAR: An In-Building RF-Based User Location and Tracking System,” in Proc. IEEE INFOCOM, 2000.
[10] T. He, C. Huang, B. M. Blum, J. A. Stankovic, T. Abdelzaher, “Range-Free Localization Schemes for Large Scale Sensor Networks,” in Proc. ACM MobiCom, 2003.
[11] A. Harter, A. Hopper and P. Steggles, “A. Ward and P.Webster, The anatomy of a context-aware application, ” in Proc. ACM MobiCom, 1999.
[12] B. Karp and H. T. Kung, “GPSR : Greedy perimeter stateless routing for wireless networks,” in Proc. ACM Mobicom, 2000.
[13] A. Rao, S. Ratnasamy, C. Papadimitriou, S. Shenker, and I. Stoica, “Geographic routing without location information,” in Proc. ACM MobiCom, 2003.
[14] J. Bruck, J. Gao, A. Jiang, “MAP:Medial Axis Based Geometric Routing in Sensor Networks,” in Proc. ACM Mobicom, 2005.
[15] Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang, “GLIDER: Gradient landmark-based distributed routing for sensor networks,” in Proc. IEEE INFOCOM, 2005.
[16] G. Tan, M. Bertier and A-M. Kermarrec, “Visibility-Graph-based Shortest-Path Geographic Routing in Sensor Networks,” in Proc. IEEE INFOCOM, 2009.
[17] G. Tan, M. Bertier and A-M. Kermarrec, “Convex Partition of Sensor Networks and Its Use in Virtual Coordinate Geographic Routing,” in Proc. IEEE INFOCOM, 2009.
[18] X. Zhu, R. Sarkar, and J. Gao, “Shape segmentation and applications in sensor networks,” in Proc. IEEE INFOCOM, 2008.
[19] G. Tan and A-M. Kermarrec, “Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach,” in Proc. ACM Mobihoc, 2010.
[20] C. Zhang, Y. Zhang and Y. Fang, “Localized algorithms for coverage boundary detection in wireless sensor networks,” Wireless Networks, 2007.
[21] L. P. Chew and R. L. Drysdale, “Voronoi diagrams based on convex distance functions,” in Proc. ACM Sympos.Comput. Geom., 1985.
[22] D. T. Lee and F. P. Preparata, “Location of a point in a planar subdivision and its applications,” SIAM Journal on Computing, vol. 6, pp. 594–606, 1977.
[23] K. Mulmuley, “A fast planar partition algorithm,” Journal of Symbolic Computation, vol. 10, pp. 253–280, 1990.
[24] D. Lichtenstein, “Planar Formulae and Their Uses,” SIAM Journal on Computing, vol. 11, pp. 329-343, 1982.
[25] A-M Kermarrec and G. Tan, “Greedy Geographic Routing in Large-Scale Sensor Networks: A Minimum Network Decomposition Approach,” Technical report of INRIA-Rennes, July, 2010.
http://hal.archives-ouvertes.fr/inria-00493387/en/
[26] S.-Y. Ni, Y.-C. Tseng, Y.-S Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proc. ACM Mobicom, 1999.
[27] Y-B Ko, and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms,” in Proc. IEEE MCSA, 1999.

指導教授

孫敏德(Min-Te Sun)

審核日期

2011-8-23

推文