Browsing by Author "Sun, Min-Te"

Now showing 1 - 2 of 2

An optimal algorithm for the minimum disc cover problem
(2008-01-01)
Sun, Min-Te
;
Yi, Chih-Wei
;
Yang, Chuan-Kai
;
Lai, Ten-Hwang
;
資訊工程學系
The minimum disc cover can be used to construct a dominating set on the fly for energy-efficient communications in mobile ad hoc networks, but the approach used to compute the minimum disc cover proposed in previous studies is computationally relatively expensive. In this paper, we show that the disc cover problem is in fact a special case of the general alpha-hull problem. In spite of being a special case, the disc cover problem is not easier than the general alpha-hull problem. In addition to applying the existing alpha-hull algorithm to solve the disc cover problem, we present a simple, yet optimal divide-and-conquer algorithm that constructs the minimum disc cover for arbitrary cases, including those degenerate cases where the alpha-hull approach would fail.
MINIMUM LOCAL DISK COVER SETS FOR BROADCASTING IN HETEROGENEOUS MULTIHOP WIRELESS NETWORKS
(2012-08-01)
Chen, Guaning
;
Yi, Chih-Wei
;
Sun, Min-Te
;
Liu, Fang-Chu
;
Lan, Wei-Chi
The concept of forwarding sets is widely adopted in many broadcast protocols for wireless multihop networks to alleviate the broadcast storm problem. In these protocols, after receiving a broadcast message, each node that is requested to relay the message instructs a subset of its 1-hop neighbors, a.k.a. the forwarding set, to further relay it. In this paper, we propose to use the Minimum Local Disk Cover Set (MLDCS) as the forwarding set in heterogeneous multihop wireless networks, where nodes may have different transmission ranges. We show that the minimum local disk cover set of a node in heterogeneous networks is equivalent to its skyline set, and then we propose a divide-and-conquer algorithm with the optimal time complexity to compute the skyline set locally and statelessly. Moreover, unlike other forwarding heuristics, the proposed algorithm requires only 1-hop neighbor information. This helps to reduce the forwarding set formation latency and thus will be more suitable for environments with a frequently changed network topology, such as vehicular ad hoc networks.