270863
Study of distance vector routing protocols for mobile ad hoc networks
We investigate the performance issues of destination-sequenced distance vector (DSDV) and ad-hoc on-demand distance vector (AODV) routing protocols for mobile ad hoc networks. Four performance metrics are measured by varying the maximum speed of mobile hosts, the number of connections, and the network size. The correlation between network topology change and mobility is investigated by using linear regression analysis. The simulation results indicate that AODV outperforms DSDV in less stressful situations, while DSDV is more scalable with respect to the network size. It is observed that network congestion is the dominant reason for packet drop for both protocols. We propose a new routing protocol, congestion-aware distance vector (CADV), to address the congestion issues. CADV outperforms AODV in delivery ratio by about 5%, while introduces less protocol load. The result demonstrates that integrating congestion avoidance mechanisms with proactive routing protocols is a promising way to improve performance.
1177051
Visualization assisted detection of sybil attacks in wireless networks
In wireless networks,the authenticity and uniqueness of node identities are essential to the fundamental operations such as routing, resource allocation, and intrusion detection. In this paper, we investigate Sybil attack, an attack in which a malicious node illegitimately acquires multiple identities and performs as these nodes simultaneously. We propose an effective approach to monitoring and detecting such attacks by integrating network security and visualization methods. The security component explores the time-varying network topology and its statistical and geometry information to detect the existence of Sybil attacks. The visualization component incorporates the detection results and provides an effective mechanism to illustrate abnormal topology patterns and locate fake identities. These two components are integrated into a practical system that takes advantage of both interactive visualization and intelligent security methods. Experimental studies are conducted to investigate the impacts of the network parameters such as node connectivity on the detection capability of the proposed mechanism.
47778
Key distribution and update for secure inter-group multicast communication
Group communication has become an important component in wireless networks. In this paper, we focus on the environments in which multiple groups coexist in the system, and both intra and inter group multicast traffic must be protected by secret keys. We propose a mechanism that integrates polynomials with flat tables to achieve personal key share distribution and efficient key refreshment during group changes. The proposed mechanism distributes keys via true broadcast. The contributions of the research include: (1) By switching from asymmetric algorithms to symmetric encryption methods, the proposed mechanism avoids heavy computation, and improves the processing efficiency of multicast traffic and the power usage at the wireless nodes. The group managers do not have to generate public-private key pairs when the group member changes. (2) It becomes more difficult for an attacker to impersonate another node since personal key shares are adopted. The additional storage overhead at the wireless nodes and the increased broadcast traffic during key refreshment are justified. In addition, we describe techniques to improve the robustness of the proposed mechanism under the complicated scenarios such as collusive attacks and batch group member changes.
5599627
Choosability and edge choosability of planar graphs without five cycles
Abstract It is proved that a planar graph G without five cycles is three degenerate, hence, four choosable, and it is also edge-( Δ ( G ) + 1)-choosable.
205873026
Control point adjustment for B-spline curve approximation
Pottmann et al. propose an iterative optimization scheme for approximating a target curve with a B-spline curve based on square distance minimization, or SDM. The main advantage of SDM is that it does not need a parameterization of data points on the target curve. Starting with an initial B-spline curve, this scheme makes an active B-spline curve converge faster towards the target curve and produces a better approximating B-spline curve than existing methods relying on data point parameterization. However, SDM is sensitive to the initial B-spline curve due to its local nature of optimization. To address this, we integrate SDM with procedures for automatically adjusting both the number and locations of the control points of the active spline curve. This leads to a method that is more robust and applicable than SDM used alone. Furthermore, it is observed that the most time consuming part of SDM is the repeated computation of the foot-point on the target curve of a sample point on the active B-spline curve. In our implementation, we speed up the foot-point computation by pre-computing the distance field of the target curve using the Fast Marching Method. Experimental examples are presented to demonstrate the effectiveness of our method. Problems for further research are discussed. q 2003 Elsevier Ltd. All rights reserved.
15045713
Visual Specification and Optimization of XQuery Using VXQ
As the popularity of XML increases, the need for querying collections of XML data from various systems becomes imperative. Proposed by W3C, XQuery is becoming a standard for querying such systems. However, the complexity of XQuery prevents its usage by broad audience. This paper proposes a visual XQuery specification language called VXQ to address this issue. By intuitive abstractions of XML and XQuery, the proposed system can generate XQueries for users that have little knowledge about the language. We show that our visual language is more expressive than previous proposals. Finally, we extend our proposed visual XQuery to support query rewriting and optimization for multiple XQuery systems.
16100691
Design multicast protocols for non-cooperative networks
Conventionally, most network protocols assume that the network entities that participate in the network activities will always behave as instructed. However, in practice, most network entities will try to maximize their own benefits instead of altruistically contribute to the network by following the prescribed protocols, which is known as selfish. Thus, new protocols should be designed for the non-cooperative network, which is composed of selfish entities. In this paper, we specifically show how to design strategyproof multicast protocols for non-cooperative networks such that these selfish entities will follow the protocols out of their own interests. By assuming that a group of receivers is willing to pay to receive the multicast service, we specifically give a general framework to decide whether it is possible, and how if possible to transform an existing multicast protocol to a strategyproof multicast protocol. We then show how the payments to those relay entities are shared fairly among all receivers so that it encourages collaboration among receivers. As a running example, we show how to design the strategyproof multicast protocol for the currently used core-based multicast structure. We also conduct extensive simulations to study the relations between payment and cost of the multicast structure.
9657581
k-anycast game in selfish networks
Conventionally, the majority of network routing protocols assume that every network terminal or link forwards data for others without any deviation. However, this may not be true when the terminals or links are owned by individual selfish users, who always tries to maximize their own benefits instead of faithfully following a prescribed protocol. In this paper, we propose a new routing protocol, called k-anycast routing, that works well even if network links (or terminals or both) are selfish. In our protocol, the source node first finds a tree that spans k receivers out of a set of possible receivers and pay the relay links to compensate their costs. We prove that every relay link follows the routing protocol: it maximizes its profit when it declares its actual cost