對密集感知網路所設計之高效率直行演算法

Straight Routing Algorithm for Dense Sensor Networks

蘇家樟(Chia-Chang Su)

指導教授 ： 周承復

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.01942

摘要

無線感知網路主要由一大群體積微小且搭載著記憶、運算、以及短距離無線通訊能力的感應器所組成。然而這些感應器受限於體積的大小及成本上的考量，因此當灑感應器後下，要再回收重複使用是不可行的。多半透過電池供應能源，且不具備GPS衛星定位功能。於是如何有效率的使用sensor network的能源，是一大議題。
解決有效率的使用電力的問題，可於Application Layer採資料壓縮，資料聚合，降低傳輸的資料量，進而減少能源消耗。在這篇論文裡，我們於Network Layer提出一個高效率路由演算法---『直行演算法』，不但能大大減少能源消耗，更提供高品質的路徑，僅需短暫的反應時間，不論直行演算法是否成功搜尋到路徑。『直行演算法』改善Rumor-routing[5]最主要的兩部分：
1. Define Candidate Region
2. Choose Candidate from Candidate Region
使得搜尋路徑能夠大為縮短，因此能有節省大幅度的能源消耗，提高所搜尋到的路徑品質。最後透過實驗與Flooding以及Rumor比較，『直行演算法』確實能達到所預期的目的。

關鍵字

演算法 ； 路由協定 ； 無線感知網路

並列摘要

Sensor networks are large-scale distributed sensing networks comprised of many small sensing devices equipped with memory, processors, and short-range wireless communication radio. In order to constrain communication overhead, dense sensor networks call for new and highly efficient methods for distributing queries to nodes that have observed interesting events in the network. A highly efficient data-centric routing mechanism will offer significant power cost reductions, and improve network longevity. In this paper we present an alternative energy efficient routing protocol, which is called Straight Routing Algorithm (SRA), for dense wireless sensor network.
According to the previous works [5], the probability of two lines would be intersected on the plane is high. Both Rumor Routing and SRA are based on this fact to create paths. In this way, when a query is generated it can be sent in the form of the random walk until the path is found; instead of flooding this query throughout the network. Hence, the main contribution of SRA is providing a scheme to construct the path Straightly. If the lines generated from source and destination are both straight, more energy will be saved, path quality will be improved and response time will be reduced.
We compare the performance of Straight Routing Algorithm, Rumor Routing and a well-known protocol, AODV. According to the simulation results, they indicate that SRA not only can achieve more energy saving than Rumor routing but also can reduce the response time. Moreover, it also can provide better path quality.

並列關鍵字

routing ； protocols ； sensor network ； algorithm

參考文獻

[1] Connected Sensor Cover: Self-Organization of Sensor Networks for Efficient Query Execution

[2] SHARP: A Hybrid Adaptive Routing protocol for Mobile Ad Hoc

[4] Data-Centric Storage in Sensornets (Sigcomm’02)

[5] Rumor Routing Algorithm for Sensor Networks

[6] D. Subramanian, D. Peter, C. Johnny. Ants and Reinforcement Learning: A Case Study in Routing in Dynamic Networks