We propose a novel approach for sparse topology generation in wireless ad hoc networks based on a graph structure known as beta-skeletons. Two efficient algorithms are presented in this paper for creating a connected ...
详细信息
ISBN:
(纸本)0780389913
We propose a novel approach for sparse topology generation in wireless ad hoc networks based on a graph structure known as beta-skeletons. Two efficient algorithms are presented in this paper for creating a connected topology from an underlying beta-skeleton. One algorithm is a localized algorithm that uses two-hop neighborhood information to generate a connected topology, with a running time of O(n). The other is a distributed algorithm that runs on each component of the beta-skeleton creating a connected structure from the disconnected beta-skeleton graph, the running time is O(nlogn). Simulations show consistent decrease in node degree in the resulting topology. The observed decrease is greater than 33% in comparison to the Relative Neighborhod Graph (RNG) and greater than 50% in comparison to other topology structures such as, the Gabriel Graph (GG) and the Yao construction on GG.
We propose a novel approach for sparse topology generation in wireless ad hoc networks based on a graph structure known as beta-skeletons. Two efficient algorithms are presented in this paper for creating a connected ...
详细信息
ISBN:
(纸本)0780389247
We propose a novel approach for sparse topology generation in wireless ad hoc networks based on a graph structure known as beta-skeletons. Two efficient algorithms are presented in this paper for creating a connected topology from an underlying beta-skeleton. One algorithm is a distributed algorithm that runs on each component of the beta-skeleton. It creates a connected structure from the disconnected beta-skeleton graph using a distributed leader election algorithm. The running time of this algorithm is 0 (n log n). The other is a localized algorithm that uses two-hop neighborhood information to generate a connected topology, with a running time of 0(n). Simulations show consistent decrease in node degree in the resulting topology. The observed decrease is greater than 33% in comparison to the Relative Neighborhod Graph (RNG) and greater than 50% in comparison to other topology structures such as, the Gabriel Graph (GG) and the Yao construction on GG.
Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent chan...
详细信息
Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicate's the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose Maximize-Local-Minimum Fair Queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers;self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose Enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.
Given a set V of n points in a two-dimensional plane, we give an O(n log n)-time centralized algorithm that constructs a planar t-spanner for V, for t = rho(alpha) max{pi/2, pi sin alpha/2 + 1}C-.(del), such that the ...
详细信息
Given a set V of n points in a two-dimensional plane, we give an O(n log n)-time centralized algorithm that constructs a planar t-spanner for V, for t = rho(alpha) max{pi/2, pi sin alpha/2 + 1}C-.(del), such that the degree of each node is bounded from above by 19 + [2pi/alpha], where 0 < alpha < pi/2 is an adjustable parameter. Here C-del is the spanning ratio of the Delaunay triangulation, which is at most (4root3)/(9)pi. We also show, by applying the greedy method in Ref. [14], how to construct a low weighted bounded degree planar spanner with spanning ratio rho(alpha)(2)(1 + epsilon) and the same degree bound, where epsilon is any positive real constant. Here, a structure is called low weighted if its total edge length is proportional to the total edge length of the Euclidean minimum spanning tree of V. Moreover, we show that our method can be extended to construct a planar bounded degree spanner for unit disk graphs with the adjustable parameter alpha satisfying 0 < alpha < pi/3. Previously, only centralized method(6) of constructing bounded degree planar spanner is known, with degree bound 27 and spanning ratio t similar or equal to 10.02. The distributed implementation of this centralized method takes O(n(2)) communications in the worst case, Our method can be converted to a localized algorithm where the total number of messages sent by all nodes is at most O(n).
We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a bac...
详细信息
We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance.
Advances in sensor technology and wireless communications have made networked microsensors possible, where each sensor individually senses the environment but collaboratively achieves complex information gathering and...
详细信息
Advances in sensor technology and wireless communications have made networked microsensors possible, where each sensor individually senses the environment but collaboratively achieves complex information gathering and dissemination tasks. These networked sensors, however, possess several characteristics that have challenged many aspects of traditional computer network design, such as the scalability issue caused by the sheer amount of sensor nodes, the infrastructureless network, and the stringent resource onboard the sensors. These new features call for a re-design of overall structure of applications and services. It has been widely accepted that practical localized algorithms is probably the best solution to wireless sensor networks. In this article, we discuss recent research results on localized algorithms design in supporting services and applications in sensor networks.
暂无评论