Browsing by Author "Yi, CW"

Now showing 1 - 4 of 4

Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with Bernoulli nodes
(2006-03-01)
Yi, CW
;
Wan, PJ
;
Li, XY
;
Frieder, O
;
資訊工程學系
Nodes in wireless ad hoc networks may become inactive or unavailable due to, for example, internal breakdown or being in the sleeping state. The inactive nodes cannot take part in routing/relaying, and thus may affect the connectivity. A wireless ad hoc network containing inactive nodes is then said to be connected, if each inactive node is adjacent to at least one active node and all active nodes form a connected network. This paper is the first installment of our probabilistic study of the connectivity of wireless ad hoc networks containing inactive nodes. We assume that the wireless ad hoc network consists of n nodes which are distributed independently and uniformly in a unit-area disk, and are active (or available) independently with probability p for some constant 0 < p <= 1. We show that if all nodes have a maximum transmission radius r(n) = root(1n n + xi)/pi pn for some constant xi, then the total number of isolated nodes is asymptotically Poisson with mean e(-xi), and the total number of isolated active nodes is also asymptotically Poisson with mean pe(-xi).
Coverage by randomly deployed wireless sensor networks
(2006-06-01)
Wan, PJ
;
Yi, CW
;
資訊工程學系
;
Department of Computer Science
One of the main applications of wireless sensor networks is to provide proper coverage of their deployment regions. A wireless sensor network k-covers its deployment region if every point in its deployment region is within the coverage ranges of at least k sensors. In this paper, we assume that the sensors are deployed as either a Poisson point process or a uniform point process in a square or disk region, and study how the probability of the k-coverage changes with the sensing radius or the number of sensors. Our results take the complicated boundary effect into account, rather than avoiding it by assuming the toroidal metric as done in the literature.
Minimum disc cover set construction in mobile ad hoc networks
(2005)
Sun, MT
;
Ma, XL
;
Yi, CW
;
Yang, CK
;
Lai, TH
The minimum disc cover set can be used to construct the dominating set on the fly for energy-efficient communications in mobile ad hoc networks. The approach used to compute the minimum disc cover set proposed in previous study has been considered too expensive. In this paper, we show that the disc cover set problem is in fact a special case of the general a-hull problem. In addition, we prove that the disc cover set problem is not any easier than the a-hull problem by linearly reducing the element uniqueness problem to the disc cover set problem. In addition to the known a-hull approach, we provide an optimal divide-and-conquer algorithm that constructs the minimum disc cover set for arbitrary cases, including the degenerate ones where the traditional alpha-hull algorithm incapable of handling.
On greedy construction of connected dominating sets in wireless networks
(2005-12-01)
Li, YS
;
Thai, MT
;
Wang, F
;
Yi, CW
;
Wan, PJ
Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP-hard. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same. Copyright (c) 2005 John Wiley & Sons, Ltd.