應用於無線傳感器網路之二步著色

Abstract

無線感測網路可廣泛的應用在環境監控。一個可以允許感測器與外界溝通的有效方法，是利用一個或多個反應節點作為從無線感測網路中所取得資料的接收者。一個無線傳感器網路是由多個隨機佈署的感測器以及少量的反應節點所組成，而反應節點會組織感測器進而形成一個以其為中心的同心圓形狀網路。定位、路由以及防止碰撞為三個主要的無線傳感器網路問題。本篇論文的主要貢獻為：提出一個新的虛擬結構來做定位以解決防止碰撞問題，同時對於我們所提出的虛擬結構的連接圖給出最佳的(在某些情況下是接近最佳的)二步著色。

Wireless sensor networks (WSNs) have a wide array of applications in environment and infrastructure monitoring. An efficient solution to allow sensors to communicate with the outside world is making use of one or several actors as the receiver of the data harvested by the WSNs. A wireless sensor and actor network (WSAN) consists of many randomly deployed sensors and a few actors that organize the sensors in their vicinity into an actor-centric network. Localization, routing, and collision avoidance are three fundamental problems in WSANs. The main contribution of this thesis is to solve the collision avoidance problem by proposing a new virtual infrastructure for the localization, and give optimal (in some cases, near-optimal) distance-two colorings for the adjacency graph of our virtual infrastructure.