Browsing by Author "Wan, Peng-Jun"

Now showing 1 - 9 of 9

Asymptotic Critical Transmission Radii for Greedy Forward Routing in Wireless Ad Hoc Networks
(2009-05-01)
Wan, Peng-Jun
;
Yi, Chih-Wei
;
Wang, Lixin
;
Yao, Frances
;
Jia, Xiaohua
In wireless ad hoe networks, greedy forward routing is a localized geographic routing algorithm in which one node discards a packet if none of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination. If all nodes have the same transmission radii, the critical transmission radius for greedy forward routing is the smallest transmission radius which ensures packets can be delivered by greedy forward routing through any source-destination pair. In this paper, we study asymptotic critical transmission radii of randomly deployed wireless ad hoc networks. Assume network nodes are represented by a Poisson point process of density n over a unit-area convex compact region whose boundary curvature is bounded. We show that the ratio of critical transmission radii to root ln n/pi n is asymptotically almost surely equal to root 1/(2/3 - root 3/2 pi) approximate to 1.6.
Asymptotic Critical Transmission Radius for k-Connectivity in Wireless Ad Hoc Networks
(2010-06-01)
Wan, Peng-Jun
;
Yi, Chih-Wei
;
Wang, Lixin
;
資訊工程學系
;
Department of Computer Science
A range assignment to the nodes in a wireless ad hoc network induces a topology in which there is an edge between two nodes if and only if both of them are within each other's transmission range. The critical transmission radius for k-connectivity is the smallest r such that if all nodes have the transmission radius r, the induced topology is k-connected. In this paper, we study the asymptotic critical transmission radius for k-connectivity in a wireless ad hoc network whose nodes are uniformly and independently distributed in a unit-area square or disk. We provide a precise asymptotic distribution of the critical transmission radius for k-connectivity. In addition, the critical neighbor number for k-connectivity is the smallest integer r such that if every node sets its transmission radius equal to the distance between itself and its l-th nearest neighbor, the induced (symmetric) topology is k-connected. Applying the critical transmission radius for k-connectivity, we can obtain an asymptotic almost sure upper bound on the critical neighbor number for k-connectivity.
Asymptotic Distribution of The Number of Isolated Nodes in Wireless Ad Hoc Networks with Unreliable Nodes and Links
(2006)
Yi, Chih-Wei
;
Wan, Peng-Jun
;
Lin, Kuo-Wei
;
Huang, Chih-Hao
;
資訊工程學系
In randomly-deployed wireless ad hoc networks with reliable nodes and links, vanishment of isolated nodes asymptotically implies connectivity of networks. However, in a realistic system, nodes may become inactive, and links may become down. The inactive nodes and down links cannot take part in routing/relaying and thus may affect the connectivity. In this paper, we study the connectivity of a wireless ad hoc network that is composed of unreliable nodes and links by investigating the distribution of the number of isolated nodes in the network. We assume that the wireless ad hoc network consists of n nodes which are distributed independently and uniformly in a unit-area disk or square. Nodes are active independently with probability 0 < p(1) <= 1, and links are up independently with probability 0 < p(2) <= 1. A node is said to be isolated if it doesn't have an up link to an active node. We show that if all nodes have a maximum transmission radius r(n) = root ln n broken vertical bar xi/pi p(1)p2(n) 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 p(1)e(-xi). In addition, the work can be extended for secure wireless networks which adopt m-composite key predistribution schemes in which a node is said to be isolated if it doesn't have a secure link. Let p denote the probability of the event that two neighbor nodes have a secure link. We show that if all nodes have a maximum transmission radius r(n) = root ln n+xi/pi pn for some constant., then the total number of isolated nodes is asymptotically Poisson with mean
Maximizing lifetime of sensor surveillance systems
(2007-04-01)
Liu, Hai
;
Jia, Xiaohua
;
Wan, Peng-Jun
;
Yi, Chih-Wei
;
Makki, S. Kami
This paper addresses the maximal lifetime scheduling problem in sensor surveillance systems. Given a set of sensors and targets in an area, a sensor can watch only one target at a time, our task is to schedule sensors to watch targets and forward the sensed data to the base station, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched and all active sensors are connected to the base station. We propose an optimal solution to find the target-watching schedule for sensors that achieves the maximal lifetime. Our solution consists of three steps: 1) computing the maximal lifetime of the surveillance system and a workload matrix by using the linear programming technique; 2) decomposing the workload matrix into a sequence of schedule matrices that can achieve the maximal lifetime; and 3) determining the sensor surveillance trees based on the above obtained schedule matrices, which specify the active sensors and the routes to pass sensed data to the base station. This is the first time in the literature that the problem of maximizing lifetime of sensor surveillance systems has been formulated and the optimal solution has been found.
On the longest edge of Gabriel graphs in wireless ad hoc networks
(2007-01-01)
Wan, Peng-Jun
;
Yi, Chih-Wei
;
資訊工程學系
;
Department of Computer Science
In wireless ad hoc networks, without fixed infrastructures, virtual backbones are constructed and maintained to efficiently operate such networks. The Gabriel graph (GG) is one of widely used geometric structures for topology control in wireless ad hoc networks. If all nodes have the same maximal transmission radii, the length of the longest edge of the GG is the critical transmission radius such that the GG can be constructed by localized and distributed algorithms using only 1-hop neighbor information. In this paper, we assume a wireless ad hoc network is represented by a Poisson point process with mean n on a unit-area disk, and nodes have the same maximal transmission radii. We give three asymptotic results on the length of the longest edge of the GG. First, we show that the ratio of the length of the longest edge to root ln n+xi/pi n is asymptotically equal to 2e(-xi). This implies that xi --> infinity is an asymptotically almost sure sufficient condition for constructing the G by 1-hop information. Last, we prove that the number of long edges is asymptotically Poisson with mean 2e-xi. Therefore, the probability of the event that the length of the longest edge is less than 2 root ln + xi/pi n is asymptotically equal to exp(-2e(-xi)).
On The Longest RNG Edge of Wireless Ad Hoc Networks
(2008)
Wan, Peng-Jun
;
Wang, Lixin
;
Yao, Frances
;
Yi, Chih-Wei
;
資訊工程學系
Relative neighborhood graph (RNG) has been widely used in topology control and geographic routing in wireless ad hoc networks. Its maximum edge length is the minimum requirement on the maximum transmission radius by those applications of RNG. In this paper, we derive the precise asymptotic probability distribution of the maximum edge length of the RNG on a Poisson point process over a unit-area disk. Since the maximum RNG edge length is a lower bound on the critical transmission radius for greedy forward routing, our result also leads to an improved asymptotic almost sure lower bound on the critical transmission radius for greedy forward routing.
Sharp Thresholds for Relative Neighborhood Graphs in Wireless Ad Hoc Networks
(2010-02-01)
Yi, Chih-Wei
;
Wan, Peng-Jun
;
Wang, Lixin
;
Su, Chao-Min
;
資訊工程學系
In wireless ad hoc networks, relative neighborhood graphs (RNGs) are widely used for topology control. If every node has the same transmission radius, then an RNG can be locally constructed by using only one hop information if the transmission radius is set no less than the largest edge length of the RNG. The largest RNG edge length is called the critical transmission radius for the RNG. In this paper, we consider the RNG over a Poisson point process with mean density n in a unit-area disk. Let. beta(0) = root 1/(2/3 - root 3/2 pi) approximate to 1.6. We show that the largest RNG edge length is asymptotically almost surely at most beta root ln n/pi n for any fixed beta > beta(0) and at least beta root ln n/pi n for any fixed beta > beta(0). This implies that the threshold width of the critical transmission radius is o(root ln n/n). In addition, we also prove that for any constant xi, the expected number of RNG edges whose lengths are not less than beta(0)root ln n+xi/pi n is asymptotically equal to beta(2)(0)/2 e(-xi).
The Critical Grid Size and Transmission Radius for Local-Minimum-Free Grid Routing in Wireless Ad Hoc and Sensor Networks
(2010-12-01)
Yi, Chih-Wei
;
Wan, Peng-Jun
;
Su, Chao-Min
;
Huang, Chen-Wei
;
資訊工程學系
In grid routing, the plane is tessellated into equal-sized square cells. Two cells are called neighbor cells if they share a common edge, and two nodes are called routing neighbors if they are in neighbor cells and within each other's transmission range. If communication parties are in the same cell, packets can be transmitted directly; otherwise, packets are forwarded to routing neighbors that are in cells closer to destination cells. As a greedy strategy, grid routing suffers the existence of local minima at which no neighbor nodes exist for relaying packets. To guarantee deliverability, in this paper, we investigate two vital parameters of grid routing, called the grid size and the transmission radius. Assume that nodes are represented by a Poisson point process with rate n over a unit-area square, and let l denote the grid size and r the transmission radius. First, we show that if l = root beta ln n/n for some constant beta and r = root 5l, then beta = 1 is the threshold for deliverability. In other words, there almost surely do not exist local minima if beta > 1 and there almost surely exist local minima if beta < 1. Next, for any given beta > 1, we give sufficient and necessary conditions to determine the critical transmission radius (CTR) for deliverability. Then, we show that as beta congruent to 1.092, the CTR r congruent to 2.09 root ln n/nis the minimum over all beta > 1. Simulation results are given to validate this theoretical work.
The Number of Isolated Nodes in a Wireless Network with a Generic Probabilistic Channel Model
(2013-02-01)
Su, Chao-Min
;
Yi, Chih-Wei
;
Wan, Peng-Jun
;
資訊工程學系
;
Department of Computer Science
A wireless node is called isolated if it has no links to other nodes. The number of isolated nodes in a wireless network is an important connectivity index. However, most previous works on analytically determining the number of isolated nodes were not based on practical channel models. In this work, we study this problem using a generic probabilistic channel model that can capture the behaviors of the most widely used channel models, including the disk graph model, the Bernoulli link model, the Gaussian white noise model, the Rayleigh fading model, and the Nakagami fading model. We derive the expected number of isolated nodes and further prove that their distribution asymptotically follows a Poisson distribution. We also conjecture that the nonexistence of isolated nodes asymptotically implies the connectivity of the network, and that the probability of connectivity follows the Gumbel function.