1110384
Priority scheduling in wireless ad hoc networks
Ad hoc networks formed without the aid of any established infrastructure are typically multi-hop networks. Location dependent contention and "hidden terminal" problem make priority scheduling in multi-hop networks significantly different from that in wireless LANs. Most of the prior work related to priority scheduling addresses issues in wireless LANs. In this paper, priority scheduling in multi-hop networks is discussed. We propose a scheme using two narrow-band busy tone signals to ensure medium access for high priority source stations. The simulation results demonstrate the effectiveness of the proposed scheme.
18115243
A wireless MAC protocol using implicit pipelining
In distributed multiple access control protocols, two categories of overhead are usually associated with contention resolution. One is channel idle overhead, where all contending stations are waiting to transmit. Another is collision overhead, which occurs when multiple contending stations attempt to transmit simultaneously. Either idle overhead or collision overhead being large, contention resolution algorithm would be inefficient. Prior research work tries to minimize both the idle and the collision overheads using various methods. In this paper, we propose to apply "pipelining" techniques to the design of multiple access control protocol so that channel idle overhead could be (partially) hidden and the collision overhead could be reduced. While the concept of pipelined scheduling can be applied to various MAC protocol designs in general, in this paper, we focus on its application to IEEE 802.11 DCF. In particular, an implicitly pipelined dual-stage contention resolution MAC protocol (named DSCR) is proposed. With IEEE 802.11, the efficiency of contention resolution degrades dramatically with the increasing load due to high probability of collision. Using the implicit pipelining technique, DSCR hides the majority of channel idle time and reduces the collision probability, hence, improves channel utilization, average access delay, and access energy cost over 802.11 significantly both in wireless LANs and in multihop networks. The simulation results, as well as some analysis, are presented to demonstrate the effectiveness of DSCR.
206479687
A vehicle-to-vehicle communication protocol for cooperative collision warning
This paper proposes a vehicle-to-vehicle communication protocol for cooperative collision warning. Emerging wireless technologies for vehicle-to-vehicle (V2V) and vehicle-to-roadside (V2R) communications such as DSRC are promising to dramatically reduce the number of fatal roadway accidents by providing early warnings. One major technical challenge addressed in this paper is to achieve low-latency in delivering emergency warnings in various road situations. Based on a careful analysis of application requirements, we design an effective protocol, comprising congestion control policies, service differentiation mechanisms and methods for emergency warning dissemination. Simulation results demonstrate that the proposed protocol achieves low latency in delivering emergency warnings and efficient bandwidth usage in stressful road scenarios.
3074931
Using directional antennas for medium access control in ad hoc networks
Previous research in wireless ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to stay silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, depending on the directions of transmission. This can increase spatial reuse of the wireless channel. In addition, the higher gain of directional antennas allows a node to communicate with other nodes located far away, implying that messages could be delivered to the destination in fewer hops. In this paper, we propose a MAC protocol that exploits the characteristics of directional antennas. Our design focuses on using multi-hop RTSs to establish links between distant nodes, and then transmit CTS, DATA and ACK over a single hop. Results show that our directional MAC protocol can perform better than IEEE 802.11, although we find that the performance is dependent on the topology configuration and the flow patterns in the system.
16121262
On physical carrier sensing in wireless ad hoc networks
The aggregate throughput of a wireless ad hoc network depends on the channel capacity, channel utilization (i.e., the fraction of channel capacity used for generating good put), and the concurrent transmissions allowed in the network. While channel utilization is determined by MAC overhead, physical carrier sense has been used as an effective way to avoid interference and exploit spatial reuse. Prior research has attempted to identify the optimal carrier sense range that can maximize the aggregate throughput. However, the impact of MAC overhead has been ignored. In this paper, we use both an analytical model and simulation results to show that MAC overhead has significant impact on the choice of optimal carrier sense range. If MAC overhead is not taken into account properly in determining the optimal carrier sense range, the aggregate throughput can suffer a significant loss.
31254944
Priority Scheduling in Wireless Ad Hoc Networks
Ad hoc networks formed without the aid of any established infrastructure are typically multi-hop networks. Location dependent contention and hidden terminal problem make priority scheduling in multi-hop networks significantly different from that in wireless LANs. Most of the prior work related to priority scheduling addresses issues in wireless LANs. In this paper, priority scheduling in multi-hop networks is discussed. We propose a scheme using two narrow-band busy tone signals to ensure medium access for high priority source stations. The simulation results demonstrate the effectiveness of the proposed scheme.
14514560
Cone spline approximation via fat conic spline fitting
Fat conic section and fat conic spline are defined. With well established properties of fat conic splines, the problem of approximating a ruled surface by a tangent smooth cone spline can then be changed as the problem of fitting a plane fat curve by a fat conic spline. Moreover, the fitting error between the ruled surface and the cone spline can be estimated explicitly via fat conic spline fitting. An efficient fitting algorithm is also proposed for fat conic spline fitting with controllable tolerances. Several examples about approximation of general developable surfaces or other types of ruled surfaces by cone spline surfaces are presented.
51886808
Kernel-Based Pronoun Resolution with Structured Syntactic Knowledge
Syntactic knowledge is important for pronoun resolution. Traditionally, the syntactic information for pronoun resolution is represented in terms of features that have to be selected and defined heuristically. In the paper, we propose a kernel-based method that can automatically mine the syntactic information from the parse trees for pronoun resolution. Specifically, we utilize the parse trees directly as a structured feature and apply kernel functions to this feature, as well as other normal features, to learn the resolution classifier. In this way, our approach avoids the efforts of decoding the parse trees into the set of flat syntactic features. The experimental results show that our approach can bring significant performance improvement and is reliably effective for the pronoun resolution task.
13366253
Efficient circular arc interpolation based on active tolerance control
In this paper, we present an efficient sub-optimal algorithm for fitting smooth planar parametric curves by G1 arc splines. To fit a parametric curve by an arc spline within a prescribed tolerance, we first sample a set of points and tangents on the curve adaptively as well as with enough density, so that an interpolation biarc spline curve can be with any desired high accuracy. Then, we construct new biarc curves interpolating local triarc spirals explicitly based on the control of permitted tolerances. To reduce the segment number of fitting arc spline as much as possible, we replace the corresponding parts of the spline by the new biarc curves and compute active tolerances for new interpolation steps. By applying the local biarc curve interpolation procedure recursively and sequentially, the result circular arcs with no radius extreme are minimax-like approximation to the original curve while the arcs with radius extreme approximate the curve parts with curvature extreme well too, and we obtain a near optimal fitting arc spline in the end. Even more, the fitting arc spline has the same end points and end tangents with the original curve, and the arcs will be jointed smoothly if the original curve is composed of several smooth connected pieces. The algorithm is easy to be implemented and generally applicable to circular arc interpolation problem of all kinds of smooth parametric curves. The method can be used in wide fields such as geometric modeling, tool path generation for NC machining and robot path planning, etc. Several numerical examples are given to show the effectiveness and efficiency of the method.
5734078
A DoS-limiting network architecture
We present the design and evaluation of TVA, a network architecture that limits the impact of Denial of Service (DoS) floods from the outset. Our work builds on earlier work on capabilities in which senders obtain short-term authorizations from receivers that they stamp on their packets. We address the full range of possible attacks against communication between pairs of hosts, including spoofed packet floods, network and host bottlenecks, and router state exhaustion. We use simulation to show that attack traffic can only degrade legitimate traffic to a limited extent, significantly outperforming previously proposed DoS solutions. We use a modified Linux kernel implementation to argue that our design can run on gigabit links using only inexpensive off-the-shelf hardware. Our design is also suitable for transition into practice, providing incremental benefit for incremental deployment.
3643118
Skeleton-driven 2D distance field metamorphosis using intrinsic shape parameters
In this article a novel algorithm is presented for 2D shape interpolation using the intrinsic shape parameters of a piecewise linear curve. The skeletons of two given shapes are computed and the smooth transformation of distance fields is driven by metamorphosis from the skeleton of the source object to that of the target one. We introduce feature graphs, linear forms of skeletons, to guide the construction of intermediate skeleton. If the topologies of the source object and the target one are different, their feature graphs will be automatically extended with equivalent topologies. Then we apply the technique of intrinsic shape parameters to the smooth transition of the extended feature graphs, which will guide the metamorphosis of the skeletons. Not only can the new approach be capable of morphing between objects with different topological genus, but also the topologies and the shapes of the intermediate objects can be controlled efficiently.