行動無線感測網路下的佈建、派遣、與封包排程之議題研究

Abstract

無線感測網路已成為近年來一門新興的科技，能夠改善並豐富我們的日常生活。無線感測網路是由眾多無線裝置所組成，其中每個裝置皆具有從環境收集資訊、並且互相溝通的能力。在本論文中，我們將探討行動無線感測網路下的佈建、派遣、與封包排程三大議題，其中所謂的行動無線感測網路指的是網路中部份或是全部的節點具有移動的能力。特別來講，佈建的議題主要是探討給予一個佈署區域，如何決定最少數量的感測器以及其佈建位置，使得這個區域內任何一點都可 以被感測器所涵蓋到、且形成的網路具有連結性；派遣的議題則是研究如何有效率安排行動感測器拜訪特定的位置去執行某些任務，使得這些行動感測器所剩有的電量能夠儘量被保存；當網路建構完畢後、或是行動感測器到達目的地時，封包排程的議題則是討論如何管理來至感測器數據的回報，使得重要的即時訊息不會被延遲、且其他非即時訊息的傳輸仍然被保障。

針對佈建的議題，我們首先提出一套通用的佈建方案，而這套方案容許佈署區域的形狀任意、且其中可能包含障礙物；我們所提出的佈建方案亦允許感測器的通訊距離和感測距離可以隨意，而這點是被以前的文獻所忽略的。我們的佈建方案先是根據佈署區域的狀況以及感測器的通訊距離與感測距離之關係來計算放置最少數量的感測器之位，然後我們再派遣感測器去這些位置，其中派遣的方式必需滿足某些特定的電源消耗之目標函數；藉由這個方式，我們的佈建方案將可以改善之前文獻的限制並對佈建之議題研究更加的完善。

在本論文中，我們進一步研究如何佈建一個具有多重涵蓋性的感測網路，而這個多重涵蓋性則是許多無線感測網路的應用或協定所必要的假設。針對這個佈建問題，我們亦提出了一套通用的方案能夠允許任意關係的感測器通訊距離與感測距離；我們所提出的佈建方案可以使用較少的感測器，此外，我們也提出了兩套分散式的感測器派遣方法來協助網路的佈建。

針對派遣的議題，我們提出了一個感測器派遣方法可以有效安排行動感測器拜訪不同的事件發生地點，我們所提出的派遣方法可以允許不同數量的行動感測器以及事件地點，這套派遣方法不但可以均衡行動感測器的移動距離，並且能夠儘量保存它們的電量；藉由這個方式，我們將能在行動感測器有限電量的限制下，儘量延長行動感測器的使用期限。

針對封包排程的議題，我們提出兩套無線封包公平排程演算法：TD-FQ與MR-FQ。TD-FQ在排程封包時考量到資料流的特性，它藉由給予即時性資料流較高的優先權以減緩其延遲時間，然而它仍保障全體資料流傳輸的公平性。MR-FQ則考量一個較複雜的無線傳輸環境，其中感測器可以根據目前傳輸頻道的狀況來調整其傳輸速率；MR-FQ可以根據資料流目前的傳輸頻道狀況以及其滯延程度來調整它的傳輸速率；藉由這個方式，MR-FQ可以同時保障資料流傳輸的公平性以及提升整體的系統效能。

在本論文中，我們亦實作了一套稱為iMouse系統的行動感測器平台，這套系統結合了無線感測網路的環境感知能力以及監控系統，以便取得環境中重要資訊並立即通報人們，因此iMouse系統可以改善傳統視訊監控系統的分析負擔；在本論文中，我們將展示iMouse系統在家庭/辦公室安全使用上的應用。

Wireless sensor networks have become one emerging technology that greatly enrich our life. Such a network consists of many tiny, wireless devices that can gather information from the environment and communicate with each other. In this dissertation, we will study the deployment, dispatch, and packet-scheduling issues of a mobile wireless sensor network, in which some or all nodes in the network have a mobile capability. In particular, the deployment issue discusses how to determine the minimum number of sensors and their locations to be placed in the region of interest so that every point in the region can be covered by sensors and the network is connected. The dispatch issue addresses how to efficiently schedule mobile sensors to reach certain locations to perform some missions so that their energies can be conserved as much as possible. After the network is constructed or mobile sensors arrive at their destinations, the packet-scheduling issue considers how to manage the messages reported from sensors so that the delays of important real-time messages can be bounded while other non-real-time messages will not be starved.

For the deployment issue, we first propose a general deployment solution that allows the deployed region to be arbitrary-shaped and possibly contain obstacles. Our solution also allows an arbitrary relationship of sensors' communication distances rc and their sensing distances rs, which is ignored by previous works. Our solution first computes the positions to place the least number of sensors according to the condition of deployed region and the relationship of rc and rs. Then we dispatch sensors to these locations under certain constraints of energy consumptions. In this way, our solution can relax the limitations of previous works and is more complete to the deployment problem.

In this dissertation, we further investigate how to deploy a sensor network for multi-level coverage, which is an essential assumption required by many applications and protocols in wireless sensor networks. For this deployment problem, we also propose a general solution in which the relationship of rc and rs can be arbitrary. Our solution can use fewer sensors compared with other schemes. In addition, we also propose two distributed dispatch schemes to help deploy sensors.

For the dispatch issue, we propose an efficient dispatch method for mobile sensors to visit event locations in a hybrid sensor network. Our dispatch method is general in which the numbers of event locations and mobile sensors can be arbitrary. Our dispatch method can balance the moving distances of mobile sensors while preserve their energies as much as possible during each round of dispatch. In this way, we can maximize the system time for mobile sensors to perform their missions with their limited energies.

For the packet-scheduling issue, we propose two wireless packet fair scheduling algorithms, Traffic-Dependent wireless Fair Queuing (TD-FQ) and Multi-Rate wireless Fair Queuing (MR-FQ). TD-FQ takes traffic types of flows into account when scheduling packets. It gives a higher priority for real-time flows to alleviate their queuing delays, but still guarantees the fairness among all flows. MR-FQ considers a more complicated multi-rate environment in which sensors can adopt different modulation techniques to transmit their packets under different channel conditions. MR-FQ adjusts a flow's transmission rate according to the flow's channel condition and its lagging degree, so that both fairness and system performance can be taken care of.

In this dissertation, we also implement a mobile sensor platform, called the integrated mobile surveillance and wireless sensor (iMouse) system. The iMouse system integrates the context-aware capability of wireless sensor network into surveillance system so that the real critical information in the environment can be retrieved and immediately send to users. In this way, the overheads of traditional visual surveillance systems can be reduced. We demonstrate the iMouse system with a home/office security scenario in this dissertation.