應用在無線感測器網路具能源效率的拓樸控制及路由方法

Abstract

Wireless sensor network是近年來一個十分熱門的研究領域。在sensor network當中，通常會有許多節點共用同一個channel，這會造成channel sharing problem，例如：增加route discovery的複雜度、降低network performance以及因為訊號的干擾而必須重傳封包，這會使得energy consumption增加。為了解決上述的問題，有許多網路拓樸控制的演算法被提出來。其中，最廣為使用的就是backbone機制。到目前為止，大多數的backbone演算法都著重在從整個網路當中挑選出適當的節點作為coordinators以減少backbone size，然而過少的 coordinators用來轉送封包將造成效能不佳等負面影響。所以許多啟發式的演算法被提出來，但是這些演算法並不能夠有效率地將多餘的節點除去，以及在稀疏的網路狀態下，網路傳輸效能會大幅度降低。此論文第一部分的目標是提供一個新穎的backbone演算法稱為SmartBone，我們提出先使用Flow-Bottleneck preprocessing來找出所有的critical nodes，這些節點能夠增加connectivity，以及提出Dynamic Density Cutback來將多餘的節點去除掉。SmartBone同時考慮了網路效能以及能源的消耗。採用SmartBone能夠降低一半的backbone size，並且能夠將能源的節省率從採用傳統方法的25%提升到40%，這將節省了大量的能源消耗。另外，在sensor network中的一些節點因為電源耗盡或故障，使得網路的拓樸變得比較稀疏，在這樣惡劣的網路環境下，我們的SmartBone能夠將packet delivery ratio從採用傳統方法的40%提升到90%。sensor network存在另外一個潛在的問題，就是如何有效率的把封包從single-source傳送至multi-sinks。也就是從一個sensor node把資料收集起來，然後傳給對此資料有興趣的多個clients。要處理這種情況的困難之處在於尋找minimum-cost transmission paths，已經有很多routing algorithm被提出來解決這個問題，但是現存的演算法大部分著重於減少能量的消耗。所以當只考慮能量因素時，顯而易見的是會產生很大的延遲現象。這篇論文的第二部分提出一個新穎的multi-path routing algorithm 使用在無線感測器網路環境下。這裡提供了稱為Hop-Count based Routing (HCR) algorithm，此方法同時考慮了能量消耗與傳送的延遲。我們採用了hop count vector (HCV) 來幫助routing decision。另外，加上pruning vector (PV) 可以更加提昇routing performance。我們提出的演算法也提供了maintenance mechanism以處理failed nodes帶來的影響。一個node的錯誤就會使得HCV不正確。所以需要一個有效率的更正演算法。我們提出Aid-TREE (A-TREE) 的演算法可以很容易地採用restricted flooding，這種更正機制比full-scale flooding來得有效率。最後，我們研究了failed nodes對整個網路拓樸的影響，並且提出一個叫做lazy-grouping的演算法，來增進HCR的穩定度。

Wireless sensor network is a rapidly growing discipline with new technologies emerging, and new applications under development. Wireless sensor nodes deposited in various places can measure light, humidity, temperature, etc. and can therefore be used in applications such as security surveillance, environmental monitoring and wildlife watching. A communication channel is generally shared among many sensor nodes in wireless sensor networks. Such sharing reduces the network performance due to aggravated radio interference. At same time it raises energy consumption since packet retransmission is needed when interference occurs. Moreover, the energy consumption could be skyrocket if we don’t limit number of active sensor nodes for the data relays. Topology control can be utilized to address the above problems. Topology control will remove unnecessary transmission links by shutting down some of redundant nodes. Nevertheless topology control will still guarantee network connectivity in order to deliver data efficiently in a wireless sensor network. This thesis proposes two topology control schemes, namely SmartBone and HCR (Hop Count based Routing) separately, in wireless sensor networks. The first scheme in the thesis, SmartBone, proposes a novel mechanism to construct a backbone. Some nodes are chosen as coordinators (i.e. backbone nodes) in the backbone construction process. All nodes then can directly or indirectly communicate with other nodes via these coordinators. The coordinators form the backbone, and the non-selected nodes can perform sleeping schedule or turn off the radio to save the energy consumption. Another potential application model for a sensor network is transmitting packets efficiently from Single-Source to Multi-Sinks. It is to gather data from a single sensor node and deliver it to multiple clients who are interested in the data. This in wireless sensor network model is called Single-Source to Multi-Sinks (SSMS). The difficulty of handling the model is in how to arrange the minimum-cost transmission path. The second proposed scheme in the thesis, HCR, simultaneously addresses energy-cost and end-to-end delay to solve the above problem.