English  |  正體中文  |  简体中文  |  Items with full text/Total items : 70585/70585 (100%)
Visitors : 23066114      Online Users : 577
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/48512


    Title: 將感測網路切割成貪婪區塊的分散式演算法;Localized GRR Decomposition for Wireless Sensor Networks
    Authors: 黃彥宸;YEN-CHEN HUANG
    Contributors: 資訊工程研究所
    Keywords: 無線感測網路;路由;Routing;Wireless Sensor Networks
    Date: 2011-08-23
    Issue Date: 2012-01-05 14:56:48 (UTC+8)
    Abstract: 在地理性路由(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.
    Appears in Collections:[資訊工程研究所] 博碩士論文

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML446View/Open


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback  - 隱私權政策聲明