Browsing by Author "Chen, Chiuyuan"

Now showing 1 - 15 of 15

A 4n-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
(2014-10-01)
Chiu, Well Y.
;
Chen, Chiuyuan
;
Tsai, Shih-Yu
;
應用數學系
;
Department of Applied Mathematics
A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [9]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm. (C) 2014 Elsevier B.V. All rights reserved.
A Suggestion of a New Measure of Importance of Nodes in Disease-propagation Graphs
(2018-01-01)
Liu, Siyu
;
Chen, Chiuyuan
;
Lin, Wu-Hsiung
;
應用數學系
;
Department of Applied Mathematics
One of the most effective ways to protect people from being infected by infectious diseases is through vaccination. However, due to the limitation of vaccine supply, it is usually impractical to vaccinate all of the people in a community. Therefore, how to smartly select a small group of people for targeted vaccination becomes an important issue. Recently, reference [3] deploys a wireless sensor system in a high school in China to collect contacts between students happened within a disease transmission distance. Reference [3] constructs a graph model for disease propagation and presents a measure of importance of nodes, called connectivity centrality, so that targeted vaccination can be performed effectively. We find that although connectivity centrality does provide a nice measure of how a node affects the other nodes during disease propagation, it overemphasizes the contact frequency between nodes and overlooks the number of neighbors of a node. Therefore, in this paper, we suggest a new measure of importance of nodes in disease-propagation graphs. and we show that there exist an infinite number of disease-propagation graphs such that the node selected by our measure is better than that selected by [3].
All-to-All Personalized Exchange Algorithms in Generalized Shuffle-exchange Networks
(2009)
Chou, Well Y.
;
Chen, Richard B.
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
All-to-all personalized exchange (ATAPE) occurs in many parallel applications. Previous ATAPE algorithms were mainly developed for hypercube, mesh, and torus networks. Recently; Yang and Wang [8] and also Massini [4] proposed an alternative approach to ATAPE by using multistage interconnection. networks (MINs); they proposed new ATAPE algorithms for a class of unique-path,.self-routable MINs (for example, baseline, shuffle-exchange (or omega), banyan network, and the reverse networks of these networks). However, the algorithms in [4] and [8] require that the given. MIN must have unique-path property and satisfy N = 2(n), in which N is the number of inputs (outputs) and n is the number of stages in the MIN. In [5], Padmanabhan proposed the generalized shuffle-exchange network (GSEN), which allows N to be any every number. Since the GSEN is not a unique-path MIN, the algorithms in [4] and [8] do not work on it. The purpose of this paper is to consider ATAPE in MINs without unique-path property. To our knowledge, no one has studied ATAPE in this type of MINs. We prove that under stage control technique, ATAPE algorithms for GSENs require at least 2(n) rounds. We propose an algorithm. which uses a variation, of stage control and works for all N equivalent to 2 (mod 4). We will prove that our algorithm takes N rounds and therefore is optimal.
All-to-all personalized exchange in generalized shuffle-exchange networks
(2010-03-28)
Chou, Well Y.
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
An all-to-all communication algorithm is said to be optimal if it has the smallest communication delay. Previous all-to-all personalized exchange algorithms are mainly for hypercube, mesh, and torus. In Yang and Wang (2000) [13], Yang and Wang proved that a multistage interconnection network (MIN) is a better choice for implementing all-to-all personalized exchange and they proposed optimal all-to-all personalized exchange algorithms for MINs. In Massini (2003)[9], Massini proposed a new optimal algorithm for MINs, which is independent of the network topology. Do notice that the algorithms in [9] and [13] work only for MINs with the unique path property (meaning that there is a unique path between each pair of source and destination) and satisfying N = 2(n), in which N is the number of processors, 2 means all the switches are of size 2 x 2, and n is the number of stages. In Padmanabhan (1991) [10], Padmanabhan proposed the generalized shuffle-exchange network (GSEN), which is a generalization of the shuffle-exchange network. Since a GSEN does not have the unique path property, the algorithms in [9] and [13] cannot be used. The purpose of this paper is to consider the all-to-all personalized exchange problem in GSENs. An optimal algorithm and several bounds will be proposed. (C) 2010 Published by Elsevier B.V.
An Effective Sensor Deployment Scheme that Ensures Multilevel Coverage of Wireless Sensor Networks with Uncertain Properties
(2020-04-01)
Chen, Yu-Ning
;
Lin, Wu-Hsiung
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
The coverage problem is a fundamental problem for almost all applications in wireless sensor networks (WSNs). Many applications even impose the requirement of multilevel (k) coverage of the region of interest (ROI). In this paper, we consider WSNs with uncertain properties. More precisely, we consider WSNs under the probabilistic sensing model, in which the detection probability of a sensor node decays as the distance between the target and the sensor node increases. The difficulty we encountered is that there is no unified definition of k-coverage under the probabilistic sensing model. We overcome this difficulty by proposing a "reasonable" definition of k-coverage under such a model. We propose a sensor deployment scheme that uses less number of deployed sensor nodes while ensuring good coverage qualities so that (i) the resultant WSN is connected and (ii) the detection probability satisfies a predefined threshold p(th), where 0 < p(th) < 1. Our scheme uses a novel "zone 1 and zone 1-2" strategy, where zone 1 and zone 2 are a sensor node's sensing regions that have the highest and the second highest detection probability, respectively, and zone 1-2 is the union of zones 1 and 2. The experimental results demonstrate the effectiveness of our scheme.
An efficient algorithm to find a double-loop network that realizes a given L-shape
(2006-08-14)
Chen, Chiuyuan
;
Lan, James K.
;
Tang, Wen-Shiang
;
應用數學系
;
電信工程研究所
Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer N, it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with N nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F Aguilo, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15-29, R.C. Chan, C.Y. Chen, ZX Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61-72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977-979, P. Esque, F Aguilo, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147-157] and it has been open for a long time whether this problem can be solved in O(log N) time. In this paper, we will provide a simple and efficient 0 (log N)-time algorithm for solving this problem. (C) 2006 Elsevier B.V. All rights reserved.
Constructing independent spanning trees for hypercubes and locally twisted cubes
(2009)
Liu, Yi-Jiun
;
Chou, Well Y.
;
Lan, James K.
;
Chen, Chiuyuan
;
應用數學系
Multiple independent spanning trees (ISTs) have applications to fault-tolerant and data broadcasting in interconnections. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. There are two versions of the n ISTs conjecture. The vertex (edge,) conjecture is that any n-connected (n-edge-connected) graph has n vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex r. Note that the vertex conjecture implies the edge conjecture. Recently, Hsieh and Tu proposed an algorithm to construct n edge-ISTs rooted at vertex 0 for the n-dimensional locally twisted cube (LTQ(n)), which is a variant of the n-dimensional hypercube (Q(n)). Since LTQ(n) is not vertex-transitive, Hsieh and Tu's result does not solve the edge conjecture for LTQ(n). In the paper we confirm the vertex conjecture (and hence also the edge conjecture) for LTQ(n) by proposing an algorithm to construct n vertex-ISTs rooted at any vertex. We also confirm the vertex (and also the edge) conjecture for Q(n). To the best of our knowledge, our algorithm is the first algorithm that can construct n vertex-ISTs rooted at any vertex for both LTQ(n) and Q(n).
Constructing independent spanning trees for locally twisted cubes
(2011-05-13)
Liu, Yi-Jiun
;
Lan, James K.
;
Chou, Well Y.
;
Chen, Chiuyuan
;
應用數學系
The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any n-connected/n-edge-connected graph has n vertex-ISTs/edge-ISTs rooted at an arbitrary vertex r. It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the n-dimensional locally twisted cube LTQ(n). The very recent algorithm proposed by Hsieh and Tu (2009) [12] is designed to construct n edge-ISTs rooted at vertex 0 for LTQ(n). However, we find out that LTQ(n) is not vertex-transitive when n >= 4; therefore Hsieh and Tu's result does not solve the Edge Conjecture for LTQ(n),,. In this paper, we propose an algorithm for constructing n vertex-ISTs for LTQ(n); consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for LTQ(n),. (C) 2011 Elsevier B.V. All rights reserved.
Fault-tolerance and Minimum Cost Placement of Bistatic Radar Sensors forBelt Barrier Coverage
(2016-01-01)
Chang, Hsin-Yun
;
Kao, Louis
;
Chang, Kai-Po
;
Chen, Chiuyuan
;
應用數學系
Barrier coverage is an important problem in wireless sensor networks and is used to guarantee the detection of an intruder that tries to cross a protected region. Most of previous studies on barrier coverage are based on the disk coverage model or sector coverage model. Recently, barrier coverage based on the bistatic radar sensor model has received more attention. The coverage area of abistatic radar is different from that of the disk and sector coverage and is dependent on the distance between the transmitter and the receiver. In particular, in [8], Wang et al. studied belt barrier coverage in bistatic radar sensor model and proposed algorithms that minimize the total placement cost spent in constructing the barrier. Note that belt barrier is a line barrier with the breadth not smaller than a predefined threshold so that the coverage quality can be improved. The purpose of this paper is to study belt barrier coverage in bistatic radar sensor model. We first propose a new deployment method that further reduces the total placement cost of [8]. We then study the fault-tolerance issue and the energy-saving issue. To the best of our knowledge, our work is the first paper that studies these two issues in belt barrier coverage in bistatic radar sensor model.
Improved upper and lower bounds on the optimization of mixed chordal ring networks
(2009-06-15)
Lan, James K.
;
Liu, Victor W.
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
Recently, Chen, Hwang and Liu [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] introduced the mixed chordal ring network as a topology for interconnection networks. In particular, they showed that the amount of hardware and the network structure of the mixed chordal ring network are very comparable to the (directed) double-loop network, yet the mixed chordal ring network can achieve a better diameter than the double-loop network. More the mixed chordal ring network can achieve diameter about root 2N as compared precisely, to root 3N for the (directed) double-loop network, where N is the number of nodes in the network. One of the most important questions in interconnection networks is, for a given number of nodes, how to find an optimal network (a network with the smallest diameter) and give the construction of such a network. Chen et al. [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] gave upper and lower bounds for such an optimization problem oil the mixed chordal ring network. In this paper, we improve the upper and lower bounds as 2[root N/2] +1 and [root 2N - 3/2], respectively. In addition, we correct some deficient contexts in [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16]. (C) 2009 Elsevier B.V. All rights reserved.
Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs
(2019-04-30)
Chu, Kuan-Ting
;
Lin, Wu-Hsiung
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
This paper studies a variation of domination in graphs called (F, B, R)-domination. Let G = (V, E) be a graph and V be the disjoint union of F, B, and R, where F consists of free vertices, B consists of bound vertices, and R consists of required vertices. An (F, B, R)-dominating set of G is a subset D subset of V such that R subset of D and each vertex in B - D is adjacent to some vertex in D. An (F, B, R)-2-stable set of G is a subset S subset of B such that S boolean AND N(R) = empty set and every two distinct vertices x and y in S have distance d(x, y) > 2. We prove that if G is strongly chordal, then alpha(F,B,R,2) (G) = gamma(F,B,R)(G)-vertical bar R vertical bar, where gamma(F,B,R)(G) is the minimum cardinality of an (F, B, R)-dominating set of G and alpha(F,B,R,2) (G) is the maximum cardinality of an (F, B, R)-2-stable set of G. Let D-1 ->* D-2 denote D1 being transferable to D-2. We prove that if G is a connected strongly chordal graph in which D-1 and D-2 are two (F, B, R)-dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 ->* D-2. We also prove that if G is a cactus graph in which D-1 and D-2 are two (F, B, R) -dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 boolean OR {1.extra} ->* D-2 boolean OR{1.extra}, where boolean OR{1.extra} means adding one extra element. (C) 2019 Elsevier B.V. All rights reserved.
Node-pancyclicity and edge-pancyclicity of hypercube variants
(2007-04-15)
Hu, Ken S.
;
Yeoh, Shyun-Shyun
;
Chen, Chiuyuan
;
Hsu, Lih-Hsing
;
應用數學系
Twisted cubes, crossed cubes, Mobius cubes, and locally twisted cubes are some of the widely studied hypercube variants. The 4-pancyclicity of twisted cubes, crossed cubes, Mobius cubes, locally twisted cubes and the 4-edge-pancyclicity of twisted cubes, crossed cubes, Mobius cubes are proven in [C.P. Chang, J.N. Wang, L.H. Hsu, Topological properties of twisted cube, Inform. Sci. 113 (1999) 147-167; C.P. Chang, T.Y. Sung, L.H. Hsu, Edge congestion and topological properties of crossed cubes, IEEE Trans. Parall. Distr. 11 (1) (2000) 64-80; J. Fan, Hamilton-connectivity and cycle embedding of the Mobius cubes, Inform. Process. Lett. 82 (2002) 113-117; X. Yang, G.M. Megson, D.J. Evans, Locally twisted cubes are 4-pancyclic, Appl. Math. Lett. 17 (2004) 919-925; J. Fan, N. Yu, X. Jia, X. Lin, Embedding of cycles in twisted cubes with edge-pancyclic, Algorithmica, submitted for publication; J. Fan, X. Lin, X. Jia, Node-pancyclic and edge-pancyclic of crossed cubes, Inform. Process. Lett. 93 (2005) 133-138; M. Xu, J.M. Xu, Edge-pancyclicity of Mobius cubes, Inform. Process. Lett. 96 (2005) 136-140], respectively. It should be noted that 4-edge-pancyclicity implies 4-node-pancyclicity which further implies 4-pancyclicity. In this paper, we outline an approach to prove the 4-edge-pancyclicity of some hypercube variants and we prove in particular that Mobius cubes and locally twisted cubes are 4-edge-pancyclic. (c) 2006 Elsevier B.V. All rights reserved.
Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks
(2007-10-01)
Liu, Victor W.
;
Chen, Chiuyuan
;
Chen, Richard B.
;
應用數學系
;
Department of Applied Mathematics
All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261-274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2x2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435-446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261-274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435-446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini's algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini's algorithm to be applicable to d-nary (each switch is of size dxd) banyan multistage interconnection networks.
Optimal coloring for data collection in tree-based wireless sensor networks
(2017-11-14)
Lo, Shih-Ming
;
Lin, Wu-Hsiung
;
Chen, Chiuyuan
;
Tseng, Yu-Ghee
;
應用數學系
Data collection is an important operation in a wireless sensor network (WSN). During data collection, the interference among nodes cannot be ignored. In a multi-hop WSN, one conventional way of defining interference neighbors is to prohibit a node from using the same time slot as those of its 1-hop and 2-hop neighbors. Recently, it is proved that for data collection in a WSN, since the set of communication nodes is limited and the transmission directions are toward the sink, a less strict set of interference neighbors can be defined [16]. The interference problem in a duty-cycle WSN (DC-WSN) with a corona structure is studied in [7]. In this paper, we solve the same problem by using the relaxed interference set defined in [16]. In particular, we give a complete classification of non-interference sets in 2-hop neighbors. We also propose a distributed 6-coloring algorithm. We prove a lower bound of six colors that every tree-based data collection algorithm requires in a dense DC-WSN, which proves our algorithm to be optimal. (C) 2017 Elsevier B.V. All rights reserved.
Sensor Deployment under Probabilistic Sensing Model
(2018-01-01)
Chen, Yu-Ning
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
In recent years, with the rapid development of wireless sensor networks (WSNs), sensors are widely used to monitor a region of interests (ROI). Therefore sensor deployment becomes one of the important issues that need to be solved because it determines the cost of constructing the WSN and affects how well the ROI is monitored. Sensors can be deployed in a pre-planned manner or in an ad-hoc manner. Moreover, the sensing model of a WSN can be binary disk model or probabilistic sensing model. Most of previous researches focus on binary disk model, which assumes that sensors can accurately detect targets within their sensing ranges. Recently, probabilistic sensing model has been proposed; in this model, the probability for a sensor to detect a target decays with the distance between the sensor and the target. Probabilistic sensing model is therefore more realistic than the binary disk model. In [2], the sensor deployment problem in a pre-planned manner under probabilistic sensing model is solved by using a transformation from probabilistic sensing model to binary disk model. We find that such a transformation wastes too many sensors, and it can be avoided. In this paper, we solve the same problem (i.e., pre-planned deployment under probabilistic sensing model) by using a "direct" method. We show that even under a simplified probabilistic sensing model, there are examples such that more than 86% of sensors used in [2] can be saved.