Browsing by Author "Wang, Lixin"

Now showing 1 - 5 of 5

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.
Improved Asymptotic Bounds on Critical Transmission Radius for Greedy Forward Routing in Wireless Ad Hoc Networks
(2008)
Wang, Lixin
;
Yi, Chih Wei
;
Yao, Frances
;
資訊工程學系
;
Department of Computer Science
Consider a random wireless ad hoc network represented by a Poisson point process over a unit-area disk with mean n. Let sigma(n) denote its critical transmission radius for greedy forward routing, and beta(0) = 1/(2/3 - root 3/2 pi) approximate to 1.6(2). It was recently proved that for any constant epsilon > 0, it is asymptotically almost sure that (1 - epsilon) root beta(0) 1n n/pi n <= sigma(n) <= (1 + epsilon) root beta(0) 1n n/pi n. In this paper, we obtain tighter asymptotic bounds on sigma(n). Specifically, we prove that for any constant c, the asymptotic probability of sigma(n) <= root beta(0) ln n+c/pi n is at least 1-(1/1/beta(0)-1/3-beta(0)/2)e(-c) and at most e(-beta 0/2e-c) Consequently, for any positive sequence (xi(n) : n >= 1) with xi(n) = o(ln n) and xi(n) -> proportional to, it is asymptotically almost sure that root beta(0) ln n-xi(n)/pi n <= sigma(n) <= root beta(0) ln n+xi(n)/pi n We also conjecture that for any constant c, the asymptotic probability of sigma(n) <= root beta(0) ln n+c/pi n is exactly exp (-(1/1/beta(0)-1/3 - beta(0)/2)e(-c)).
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).