以最小區域圓覆蓋集合為基礎用於異質無線隨意網路之廣播

Abstract

在無線隨意網路中，廣播是其中一個最基礎的網路操作方法。他被廣泛使用在發現網路拓蹼、傳輸路徑與監視網路的完整性。而其中一個簡單的機制，稱為氾濫式演算法，它的方法是當節點收到第一份訊息時，這個節點會傳送這個訊息給它所有的鄰居。儘管它很簡單，氾濫式演算法傾向去產生大量多餘的重傳。因此氾濫式演算法可能會引起廣播風暴問題，而且在電源和頻寬上也沒有效率。為了減輕廣播風暴問題，當某個節點需要廣播時，這個節點只選擇部分的鄰居，稱為前傳集合來幫它重送訊息，而不是所有鄰居都來傳送訊息。在前傳集合內的所有節點會覆蓋住所有2-hop鄰居，所以可以確定所有網路上的節點都會收到這廣播訊息。

在同質性網路中，根據1-hop鄰居的覆蓋範圍，可以計算出前傳集合。這個節點的前傳集合的覆蓋範圍跟所有鄰居的覆蓋範圍是一樣的。而被提出的演算法是區域性且分散式的演算法，而且具有最佳的時間複雜度。

在這篇論文中，我們提出一個機制以最小區域圓覆蓋集作為前傳集合在異質性網路中(各個節點有不同的傳輸半徑)。對每個節點來說，如果它的鄰居的子集合有最少的個數而且它們的覆蓋範圍和所有鄰居的覆蓋範圍是一樣的，則這個子集合稱作最小區域圓覆蓋集合。首先我們證明找它的最小區域性的圓盤覆蓋集合與找它的輪廓線集合是相等的。我們提出一個各個擊破的演算法來局部地計算此輪廓線集合，而證明它有最佳的時間複雜度O(nlogn)。

In wireless ad hoc networks, broadcasting is one of the fundamental networking operations. It is widely and frequently used to explore the network topology, find routing paths, and monitor network integrity. A simple broadcasting mechanism, known as flooding, is to let every node relay messages to all its 1-hop neighbors when it receives the messages the first time. Despite its simplicity, flooding tends to generate too many redundant retransmissions. It may cause the broadcast storm problem and is neither power nor bandwidth efficient. To relieve the problem, when a node does broadcasting, it selects a subset of neighbors called forwarding set to relay messages instead of all neighbors. Nodes in the forwarding set of a node would cover all its 2-hop neighbors, so it ensures that messages can reach all nodes in the network. In homogeneous networks, it has been proposed computing the forwarding set based on the coverage area of 1-hop neighbors. The nodes in the forwarding set of a node can cover the same area as its all 1-hop neighbors. The proposed algorithm is localized, distributed, and with the optimal time complexity O(nlogn). In this paper, we propose to use the minimum local disk cover set as forwarding set in heterogeneous networks, where nodes may have different transmission radii. A minimum local disk cover set of a node is a subset of 1-hop neighbors and the number of set is smallest. The nodes in the minimum local disk cover set cover the same area of all 1-hop neighbors. We show that the minimum local disk cover set of a node is equivalent to its skyline set. We propose a divide-and-conquer algorithm with the optimal time complexity O(nlogn) to compute the skyline set locally.