兩個基於寬鬆干擾集概念的用於以收集端為中心的感測器網路的衝突避免分散式著色策略

Abstract

無線感測器網路在現實世界中有許多的應用。由於硬體上的限制，如何提升能源利用效益以及如何避免通信干擾，是無線感測器網路最重要的問題其中兩個。工作週期(duty-cycle)常被用於降低能源消耗，並提高無線感測器網路的能源利用效益。在一個使用工作週期的無線感測器網路中，感測器只會在它所被分配到的時槽傳遞訊息，之後它便進入休眠狀態以節省能源。然而，在一個使用工作週期的無線感測器網路中，兩個感測器同時發送訊息可能造成干擾問題。Wu 和Tseng在文獻[10]中指出，用於資料收集的無線感測器網路的干擾鄰居的定義可以被寬鬆。Navarra等人在文獻[4]中提出一個建立在「使用工作週期的以收集端為中心的感測器網路」的虛擬基礎架構，它非常適合用於資料收集；Navarra等人將虛擬基礎架構對應至鄰接圖 ，將虛擬基礎架構的「干擾問題」視為鄰接圖 的「著色問題」，並提出了鄰接圖 的二步著色策略。本論文的目的在於：將文獻[10]的寬鬆干擾鄰居的概念應用在鄰接圖 上，我們成功的提出了鄰接圖 的兩個基於寬鬆干擾集概念的分散式6-著色策略，這兩個策略一個是針對 ( 為偶數)，另一個則是針對 ( 為奇數)。值得一提的是，文獻[4]的二步著色策略會將 , , , 和 分別著 , , , 和 色。

Wireless sensor network (WSNs) have a lot of applications in real world. Due to the physical limit of hardware, how to improve energy efficiency and how to avoid communication interference are two of the most important problems of WSNs. Duty-cycle is often used to reduce the energy consumption and can improve the energy efficiency of WSNs. In a duty-cycle WSN, a sensor transmits messages in the time slot assigned to it. Then, it goes to sleep to save energy. In a duty-cycle WSN, two sensors simultaneously transmit messages may cause interference problem. Wu and Tseng [10] pointed out that the denition of interference neighbors can be relaxed if the WSN is used for data collection. In [4], Navarra et al. purposed a virtual infrastructure of a duty-cycle sink-centric network, which is suitable for data collection. Navarra et al. regarded the interference problem as a coloring problem of the associated adjacency graph Gℓ of the given duty-cycle sink-centric network, and they proposed a distance-two coloring strategy for Gℓ. The purpose of this thesis to to apply the relaxed denition of interference neighbors to G_ℓ. In particular, we will purpose two distributed 6-coloring strategies for G_ℓ (ℓ even) and Gℓ (ℓ odd). Do notice that the distance-two coloring proposed in [4] will color G4, G5, G_4i (i≥2), and G_ℓ (ℓ≥7) by 7, 7, 8, and 9 colors, respectively.