無線感測網路中低延遲和省電之資料收集方法

Abstract

在無線感測網路中，資料收集是一個很重要的任務。設計一個資料收集機制時，兩個重要的議題，低延遲和省電，必需被考慮。前者是要盡快的收集感測資料，後者是節省感測器的電量達到延長網路生命。本論文針對不同通訊協定層，設計感測網路資料收集機制達到以上兩個目標。本論文包含三個資料收集機制之研究。第一個研究中，我們針對MAC通訊協定層，設計資料收集機制。透過充分利用可以控制的移動式節點，第二個研究針對一個連通的無線感測網路，設計一個分散式佈建移動式節點之通訊協定來協助收集感測器資料；第三個研究考慮一個不連通的無線感測網路，利用移動式節點協助資料收集。

在第一個研究中，我們提出一個新的通訊干擾模型，並另利用此模型設計一個相容於ZigBee的MAC通訊協定。在一個多點跳躍的無線網路中，傳統定義通訊干擾的模型是避免一個節點和其兩個跳躍內的鄰近節點使用相同的通訊時間槽。然而，因為感測網路中資料收集時，通訊的方向只限於由感測節點傳送到資料收集中心，我們因此可以重新定義一個精確的通訊干擾模型。基於這樣的觀察，我們利用此較精確的通訊干擾模型，設計一個有效的分散式之通訊排程機制來達到資料收集之低延遲和省電的目標。

隨著感測資料是經由一個靜態感測網路收集，感測網路會遭遇電量消耗不均衡的問題，即越靠近資料收集中心的感測器之電量會消耗較快。為了減輕此問題，第二個研究考慮一個雙層的感測網路，其中一組電量充沛的移動式節點被用來佈建一個主幹網路協助靜態的感測器傳遞資料到資料中心。此種雙層的感測網路優點是利於大規模佈建，且可以有效降低傳統多點跳躍通訊時感測器所消耗的電量。然而，佈建移動式節點使其具網路連通和佈建均衡之特性是相當挑戰的，尤其當無法得知網路節點之位置資訊的情形下。網路連通是確保移動式節點彼此可以互相通訊，佈建均衡是確保每個移動式節點收集等量的感測資料。在本研究中，我們將此問題建模成一個具連通性且佈建均衡之移動式節點位置重置之最佳化問題，並證明此問題為NP-complete。為了達連通性和佈建均衡之目標，到我們提出了一套分散式的雙模移動式節點位置重置通訊協定，其中主要特點是移動式節點位置重置不需使用位置資訊。經由下層感測網路之拓撲結構和區域性的資訊(稱為covering cell)，本通訊協定允許每個移動式節點可以自主決定其移動的位置。透過大規模的網路模擬結果顯示本研究設計之機制以較少的移動距離和通訊成本同時達到連通性且佈建均衡之目標。

有鑒於現存大部分的研究焦點與設計皆針對一個連通的無線感測網路，第三個研究考慮的是一個空間上分割的無線感測網路，其中包含數個彼此距離甚遠且不連通的孤立子網路。我們處理利用移動式節點(稱為資料收集器)進行感測資料收集之議題。在此種不連通的環境中，資料收集的延遲和網路生命是相當重要的議題。我們針對此問題進行建模為一個具電量限制之資料收集器移動路徑問題，稱為energy-constrained mule traveling salesman problem (EM-TSP)，其目標是找到一條資料收集器之最短移動路徑使得每個孤立的子網路至少被資料收集器拜訪一次且感測器之最大電量消耗不會超過一個預設的門檻值。值得注意的是本研究建模的問題是一個典型NP-hard問題traveling salesman problem (TSP)的更一般化的模型。以幾何性質為基礎，我們提出有效的機制來解決EM-TSP問題。此外，本研究亦將此設計延伸到多個資料收集器的環境中。大規模的實驗顯示直接套用現存TSP近似演算法處理EM-TSP問題是無法達到好的網路效能，而我們的機制是可以有效改善網路效能。

Data collection is an important mission in a wireless sensor networks (WSNs). Two critical issues, low latency and power saving, must be take into consideration while designing a data collection mechanism. The former is to collect sensing data as soon as possible, while the later is to conserve energy of sensors to prolong network lifetime. In this thesis, we consider different protocol layers to design data collection mechanisms for a WSN to achieve the both goals. This thesis is composed of three work. In the first work, we pay attention to the design of communication protocols in MAC layer. By exploiting controllable mobile nodes, the second work designs a distributed relocation protocol of mobile nodes to facilitate data relaying in a connected WSN, while the last work adopts mobile nodes to facilitate data collection in a disconnected WSN.

In the first work, we promote a novel interference model to design a ZigBee-compatible data collection MAC protocol. In a multi-hop wireless network, a conventional way of defining interference neighbors is to prohibit a node from using the same slot/code as those of its 1-hop and 2-hop neighbors. However, for data collection in a wireless sensor network, since the set of communication nodes is limited and the transmission directions are toward the sink, we show that a less strict set of interference neighbors can be defined. Based on this observation, we develop an efficient distributed wake-up scheduling scheme for data collection in a sensor network that achieves both low reporting latency and energy conservation.

As the sensing data is collected via a static WSN, an unbalanced energy consumption problem arises, where sensors closer to the sink are more likely to exhaust their energy faster than other nodes. To mitigate this problem, the second work considers a two-tiered wireless sensor and actor network (WSAN), where a set of resource-rich mobile nodes (termed actors) form a connected backbone to relay sensing data from static sensors to the sink. Such a two-tiered WSAN facilitates scalability and can efficiently reduce the energy consumption and latency incurred by conventional hop-by-hop relaying via only sensors. However, relocating actors from an initial random deployment to achieve both connectivity and load balance is a challenge, especially when there exists no location information of the nodes. Connectivity ensures that the actors are connected, while load balance ensures that actors collect and originate a similar amount of sensory data from the sensors. In this work, we formulate the Connected and Balanced Mobile Actor Relocation (CBMAR) optimization problem to address both connectivity and load balance and prove that the problem is NP-complete. We propose a dual-mode distributed actor relocation protocol that does not rely on any location information of actors or sensor nodes to relocate actors to meet the goals of connectivity and load balance. By maintaining a local view (termed covering cell), the protocol allows each actor to locally determine where it should move by using the lower-tiered topology of the sensors. Simulation results show that the protocol can achieve both objectives of connectivity and load balance with low moving and communication overheads.

While most research efforts focus on a connected WSN, the third work considers a spatially separated wireless sensor network (SS-WSN), which consists of a number of isolated subnetworks that could be far away from each other in distance. We address the issue of using mobile mules to collect data from these sensor nodes. In such an environment, both data collection latency and network lifetime are critical issues. We model this problem as a bi-objective problem, called energy-constrained mule traveling salesman problem (EM-TSP), which aims at minimizing the traversal paths of mobile mules such that at least one node in each subnetwork is visited by a mule and the maximum energy consumption among all sensor nodes does not exceed a pre-defined threshold. Interestingly, the traversal problem turns out to be a generalization of the classical traveling salesman problem (TSP), an NP-hard problem. Based on some geometrical properties of the network, we propose some efficient heuristics for EM-TSP. We then extend our heuristics to multiple mobile mules. Extensive simulation results are conducted to show that directly applying an efficient TSP approximation to EM-TSP does not guarantee good performance, while our proposed solutions give better performance.