物件追蹤感測網路中與位置管理相關的通訊協定

Abstract

無線通訊與感測技術的快速發展使得無線感測網路成為一門新興的科技，無線感測網路的應用也因此被廣泛地討論。在無線感測網路中物件追蹤是一個重要的議題，它包含了許多的應用，例如軍事上入侵者的偵測、野生動物棲息地的監控等。物件追蹤包含了幾個重要的步驟，例如事件的偵測、目標物的辨識、位置的估算等，在無線感測網路中，當物件的位置被估算出來之後，為了能讓使用者去查詢物件的位置，或者為了能讓感測到物件的感測器做回報，一個位置管理機制是需要的。本論文的主題即討論無線感測網路上位置管理相關的通訊協定。我們所提出的位置管理機制利用了無線感測網路的網路內資料處理的能力，以分散式的方式去執行物件位置的更新與查詢。我們更考量了在多資料匯集端的網路下的位置管理機制，在這樣的環境下我們假設使用者可在任一個地方發出位置的查詢。而由於感測資料的不精確是感測網路先天上特有的特性，我們也考慮了在使用者可容忍一些誤差的網路環境下，位置管理機制該如何達成的問題。而不管在哪一種網路環境下，位置管理機制的目的都是為了要降低位置更新與位置查詢所產生的通訊成本。此外，我們觀察到網路底層封包的遺失與碰撞可能導致物件追蹤網路中產生不正確的位置資訊，而物件追蹤網路是一種以事件驅動為主的網路，因此我們也針對以事件驅動為主的感測網路提出了一個鏈結層通訊協定來降低封包碰撞的問題。

物件追蹤通常包含了兩個基本的操作：位置更新與位置查詢。一般而言，位置更新是在當一個物件從一個感測區域移動到另一個感測區域時發生，而位置查詢則是當使用者有需要知道物件的位置而發生查詢。無線感測網路處理位置更新與查詢的方法有很多，一個處理更新與查詢最簡單的做法是將使用者的查詢送給網路上的每一個感測節點，而偵測到物件的感測器在收到查詢後就會回覆物件的位置給資料匯集端，我們可以發現在這個方法中，感測器不需要主動地做位置的更新，然而，很顯然這個方法在網路規模很大或者是查詢頻率很高時會非常地沒有效率，因為使用者的查詢必須被廣播到整個網路上。第二種處理更新與查詢的方法則是要求感測器偵測到物件時就必須主動地將物件的新位置傳送給資料匯集端，如此資料匯集端就隨時有物件的位置資訊，因此資料匯集端本身就可以馬上回覆使用者的查詢，而不再需要將查詢送到感測網路上，然而這方法在物件移動相當頻繁時會產生許多的位置更新訊息，因此我們可以很明顯地看出上述兩個方法是各有利弊。在這篇論文中，我們首先針對單一資料匯集端的網路環境提出一個樹狀的位置管理機制，在建樹的過程中，我們考量了網路實際上的拓樸對通訊代價產生的影響。建樹的程序主要分成兩個階段，在第一個階段我們主要目的是降低位置更新所產生的通訊代價，我們利用了避免偏向(deviation-avoidance)與高移動頻率優先(high-weight-first)這個特性去降低通訊代價。而在第二個階段，我們則是以第一階段所產生的樹再加上位置查詢的考量而去做調整。

接著，我們則考慮了一個多資料匯集端的感測網路。擁有多重資料匯集端的一個好處是可降低位置查詢的回應時間，除此之外也能降低資料匯集端附近網路流量擁塞的問題，亦即可達到較好的負載平衡。為了要支援多資料匯集端的環境，我們可考慮將單一資料匯集端的方法做延申，也就是每個資料匯集端都建構一個樹，然而這也就意謂著更新多個樹是需要的，因此如何去降低更新多個樹所產生的通訊代價便是我們要去解決的問題。在這篇論文中，為了解決此問題，我們利用了資料匯集的概念提出了有效率的位置更新機制。有了這個機制，我們發現在多重資料匯集端的環境下，位置更新的通訊代價只會增加少許。此外，我們也根據前述的更新機制推導出更新代價的公式，並以此公式設計出兩個分散式的建樹演算法。

在物件移動的環境中要維持物件正確的位置資訊幾乎是不可能的，原因除了定位技術本身就不是很準確，物件的移動與資料傳送的延遲也都使得查詢者得到的位置資訊並不精確。然而幸運的是在物件追蹤的應用中，不精確的位置資訊通常是能夠被容忍的，例如生物科學家為了要追蹤某動物時，生物學家可能只需要知道大概的移動方向即可而不需要知道正確的位置，除此之外，當科學家只是為了要觀察動物的日常作息時，幾個小時前的位置資訊對科學家們仍是有用的資訊。因此我們也提出了一個位置管理機制去支援能夠容忍不精確位置資訊的物件追蹤感測網路。我們認為這個位置管理機制應該要能達成兩個目標，第一，位置查詢的通訊代價應該跟精確程度成正比，第二，多精確程度的支援。我們觀察到樹狀架構的位置管理機制可以很容易地達成這兩個目標，因此我們也提出了一個建樹的演算法。

藉著實驗的模擬我們觀察到封包的碰撞與遺失會導致使用者得到不正確的物件位置資訊，因此我們也提出了一個鏈結層協定來減輕碰撞的問題。無線感測網路一般可分成兩類，一是事件驅動另一則是時間驅動。在事件驅動的感測網路中，感測器會在偵測到事件時做回報的動作，而這樣的回報可能造成事件發生區域的感測器遭受到較高的傳輸競爭。在這篇論文中，我們結合了兩個議題來解決這個問題，一是利用感測資料的空間相關性，另一則是設計一個新的媒介存取協定。我們提出了一個結合TDMA(Time Division Multiple Access)與CSMA(Carrier Sense Multiple Access)的鏈結層協定，它與傳統以TDMA為基礎的協定有幾個不同的特色。第一，在TDMA的部份我們只需要較寬鬆的時間同步且是經由事件的驅動而啟動TDMA，而CSMA則在非事件發生區域被採用以達到低傳送延遲。第二，時槽分配策略考量了感測資料的空間相關性，我們發現藉著允許一個感測器可使用和其鄰居相同的時槽，可使得整個網路所需要的時槽數大幅地降低。第三，藉著拉長一個時槽的長度，我們可在封包離開事件區域後能像水流一樣依序地前進，每個封包會相隔一定的距離以避免干擾。除此之外，利用TDMA的特性及感測資料的空間相關性，我們也提出了一個降低回報量的機制。而為了達到省電的目的，我們也討論如何將LPL (Low Power Listening)的技術結合到我們的方法。

The rapid progress of wireless communication and embedded micro-sensing MEMS technologies has made wireless sensor networks (WSNs) possible. Applications of WSNs have been studied widely. Object tracking is one of the important issues of WSNs, which has applications in such as military intrusion detection and habitat monitoring. The key steps involved in object tracking include event detection, target classification, and location estimation. In a WSN, when the locations of objects are successfully determined, a location management scheme for reporting objects' locations and disseminating users' queries is required. The main theme of this dissertation is location management. The proposed location management schemes explore the in-network data processing capability of WSNs by executing distributed location updates and queries inside the network. We further consider the multi-sink system, in which a user can issue queries from anywhere in a WSN. Since inaccuracy of sensing data is inherent for WSNs, we also consider the scenarios where users can tolerate a certain degree of imprecision in their query results. The goal of location management schemes is to reduce the communication cost. Besides, we observe that packet collision can lead to incorrect location information. Thus, we also propose a link-layer protocol to relieve the collision problem for event-driven WSNs.

Object tracking typically involves two basic operations: update and query. In general, updates of an object's location are initiated when the object moves from one sensor to another. A query is invoked each time when there is a need to find the location of an interested object. Location updates and queries may be done in various ways. A naive way for delivering a query is to flood the whole network. The sensor whose sensing range contains the queried object will reply to the query. Clearly, this approach is inefficient because a considerable amount of energy will be consumed when the network scale is large or when the query rate is high. Alternatively, if all location information is stored at a specific sensor (e.g., the sink), no flooding is needed. But whenever a movement is detected, update messages have to be sent. One drawback is that when objects move frequently, abundant update messages will be generated. The cost is not justified when the query rate is low. Clearly, these are tradeoffs. In this dissertation, we first propose a tree-based location management scheme for single-sink WSNs. We develop several tree structures for in-network object tracking which take the physical topology of the sensor network into consideration. The optimization process has two stages. The first stage tries to reduce the location update cost based on a deviation-avoidance principle and a highest-weight-first principle. The second stage further adjusts the tree obtained in the first stage to reduce the query cost.

We then explore the possibility of having multiple sinks in the network. One advantage of having multiple sinks is to reduce the response time of queries. In addition, using multiple sinks can also relieve the traffic congestion problem associated with a single-sink system (i.e., using multiple sinks can achieve load balance more easily). In order to support location management in a multi-sink WSN, we can extend the tree structure used in the single-sink system by constructing a logical tree for each sink. However, this implies that updating multiple trees is required when a movement event is detected. It is desirable to further reduce the update cost when multiple trees coexist in the network. In this dissertation, by exploring the concept of data aggregation, we propose an algorithm to efficiently update multiple trees. With proper design, we show that the update cost increases slightly when the number of trees (i.e., the number of sinks) increases. Based on the foregoing update algorithm, we formulate the update cost that gives us hints to develop efficient tree-construction algorithms. Two distributed multi-tree construction algorithms are also presented.

In moving object environments, maintaining the exact locations of objects anytime is almost infeasible. Not only the positioning results are error-prone, but also the data transfer delay and object mobility make the locations of objects inaccurate. Fortunately, imprecision is tolerable in many object tracking applications. For example, when life scientists intend to track an animal, it may be sufficient to know its moving direction rather than its exact location. In addition, the location information recorded several hours ago, instead of at the current time, may be still available for the life scientists to understand the animal's daily life. Therefore, we also we propose an in-network location management scheme to support imprecision-tolerant queries for object tracking sensor networks. We argue that an imprecision-tolerant location management solution should achieve two desirable goals. First, the query cost should be proportional to the precision level. Second, multiple precision levels should be provided. We observe that the tree-based location management schemes could achieve these two goals inherently. Thus, we also propose a tree construction algorithm for imprecision-tolerant location management model.

By simulation, we observe that packet collision can lead to incorrect location information in object tracking sensor networks. Thus, we also propose a link-layer protocol to relieve the collision problem for event-driven WSNs. Wireless sensor networks (WSNs) can generally be classified into two categories: time-driven and event-driven. In an event-driven WSN, sensors report their readings only when they detect events. In such behavior, sensors in the event area may suffer from higher contention. In this dissertation, we solve this problem by jointly considering two subissues. One is exploiting the spatial correlation of data reported by sensors in the event area and the other is designing a specific MAC protocol. We propose a novel hybrid TDMA/CSMA protocol with the following interesting features that differentiate itself from conventional TDMA-based protocols. First, the TDMA part is based on very loose time synchronization and is triggered by the appearance of events. On the other hand, the CSMA part is adopted in the non-event area to achieve low latency transmission. Second, the slot assignment strategy associated with the TDMA part takes the spatial correlation of sensor data into consideration and thus allows less strict slot allocation than conventional TDMA schemes. Interestingly, by intentionally allowing one-hop neighbors to share the same time slot, the number of slots required per frame is significantly reduced. Third, by enlarging the slot size on purpose, our scheme enforces packets, after leaving the event area, to form a pipeline in such a way that packets flow like streams, each of which is separated sufficiently in distance to avoid interference. In addition, by exploiting TDMA's features and the spatial correlation of sensor data, we show how to reduce redundant reports. We also discuss how to combine our protocol with the LPL (Low Power Listening) technique to achieve energy efficiency.