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

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/48512

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/48512

题名:	將感測網路切割成貪婪區塊的分散式演算法;Localized GRR Decomposition for Wireless Sensor Networks
作者:	黃彥宸;YEN-CHEN HUANG
贡献者:	資訊工程研究所
关键词:	無線感測網路;路由;Routing;Wireless Sensor Networks
日期:	2011-08-23
上传时间:	2012-01-05 14:56:48 (UTC+8)
摘要:	在地理性路由(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.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	578	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....