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

A distance-two coloring with applications to wireless sensor and actor networks

趙彥丞(Yen-Cheng Chao)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00110

摘要

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

關鍵字

無線傳感器網路 ； 粗質定位 ； 二步著色 ； 防止碰撞

並列摘要

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.

並列關鍵字

Wireless sensor and actor network ； Coarse-grain localization ； Distance-two coloring ； Collision avoidance

參考文獻

[1] I.F. Akyildiz and I.H. Kasimoglu, Wireless sensor and actor networks: Research challenges, Ad Hoc Networks 2 (2004) 351-367.

Ravelomanana, Ecient location training protocols for heterogeneous sensor and

actor networks, IEEE Transactions on Mobile Computing 10 (2011) 377-391.

chronous corona training protocols in wireless sensor and actor networks, IEEE

[4] A.A. Bertossi, S. Olariu and C.M. Pinotti, Ecient corona training protocols for sensor networks, Theoretical Computer Science 402 (2008) 2-15.