16383417
Interference-aware routing in multihop wireless networks using directional antennas
Recent research has shown that interference can make a significant impact on the performance of multihop wireless networks. Researchers have studied interference-aware topology control recently [M. Burkhart et al., 2004]. In this paper, we study routing problems in a multihop wireless network using directional antennas with dynamic traffic. We present new definitions of link and path interference that are suitable for designing better routing algorithms. We then formulate and optimally solve two power constrained minimum interference single path routing problems. Routing along paths found by our interference-aware algorithms tends to have less channel collisions and higher network throughput. Our simulation results show that, compared with the minimum power path routing algorithm, our algorithms can reduce average path interference by 40% or more at the cost of a minor power increase. We also extend our work towards survivable routing by formulating and solving the power constrained minimum interference node-disjoint path routing problem.
13492639
Relay node placement in large scale wireless sensor networks
Scalability and extended lifetime are two critical design goals of any large scale wireless sensor network. A two-tiered network model has been proposed recently for this purpose. This is a cluster-based network model composed of relay and sensor nodes. Relay nodes are placed in the playing field to serve as cluster heads and to form a connected network topology for information dissemination at the higher tier. The relay nodes are capable of aggregating data packets from the sensor nodes in their clusters and transmitting them to the sink node via wireless multi-hop paths. In this paper, we study the relay node placement problem in large scale wireless sensor networks. Our objective is to place the fewest number of relay nodes in the playing field of a sensor network such that (1) each sensor node can communicate with at least one relay node and (2) the network of relay nodes is connected. However, placement strategies realizing goals (1) and (2) do not provide any fault-tolerance as the network may lose functionality after failure of some of the relay nodes. In order to incorporate fault-tolerance in such a network, we ensure that every sensor node is able to communicate with at least two relay nodes and the induced network topology is 2-connected. This strategy will ensure survivability of the network in the event of single fault, in lieu of higher relay node placement cost. We formulate the relay node placement in wireless sensor networks as two optimization problems: (i) Connected Relay Node Single Cover (CRNSC) problem and (ii) 2-Connected Relay Node Double Cover (2CRNDC) problem. We present two polynomial time approximation algorithms to solve the CRNSC problem. We prove that the ratio of the number of relay nodes needed by the approximation algorithm to the number of relay nodes needed by the optimal algorithm is bounded by 8 for the first algorithm and 4.5 for the second. In addition, for the 2CRNDC problem we provide two approximation algorithms with performance bounds 6 and 4.5, respectively.
207188648
Reliable Ad Hoc Routing Based on Mobility Prediction
Reliability is a very important issue in Mobile Ad hoc NETworks (MANETs). Shortest paths are usually used to route packets in MANETs. However, a shortest path may fail quickly, because some of the wireless links along a shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes may result in substantial data loss and message exchange overhead. In this paper, we study reliable ad hoc routing in the urban environment. Specifically, we formulate and study two optimization problems. In the minimum Cost Duration-bounded Path (CDP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the maximum Duration Cost-bounded Path (DCP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given threshold. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the duration prediction table. We also present a heuristic algorithm for the DCP routing problem. In addition, we show that the proposed prediction and routing schemes can be easily applied for designing reliable ad hoc routing protocols. Simulation results show that our mobility prediction based routing algorithms lead to higher network throughput and longer average path duration, compared with the shortest path routing.
79892
Resource Allocation and Quality of Service Evaluation for Wireless Communication Systems Using Fluid Models
Wireless systems offer a unique mixture of connectivity, flexibility, and freedom. It is therefore not surprising that wireless technology is being embraced with increasing vigor. For real-time applications, user satisfaction is closely linked to quantities such as queue length, packet loss probability, and delay. System performance is therefore related to, not only Shannon capacity, but also quality of service (QoS) requirements. This work studies the problem of resource allocation in the context of stringent QoS constraints. The joint impact of spectral bandwidth, power, and code rate is considered. Analytical expressions for the probability of buffer overflow, its associated exponential decay rate, and the effective capacity are obtained. Fundamental performance limits for Markov wireless channel models are identified. It is found that, even with an unlimited power and spectral bandwidth budget, only a finite arrival rate can be supported for a QoS constraint defined in terms of exponential decay rate
4300632
Keyword Extraction Using Support Vector Machine
This paper is concerned with keyword extraction. By keyword extraction, we mean extracting a subset of words/phrases from a document that can describe the ‘meaning' of the document. Keywords are of benefit to many text mining applications. However, a large number of documents do not have keywords and thus it is necessary to assign keywords before enjoying the benefit from it. Several research efforts have been done on keyword extraction. These methods make use of the ‘global context information', which makes the performance of extraction restricted. A thorough and systematic investigation on the issue is thus needed. In this paper, we propose to make use of not only ‘global context information', but also ‘local context information' for extracting keywords from documents. As far as we know, utilizing both ‘global context information' and ‘local context information' in keyword extraction has not been sufficiently investigated previously. Methods for performing the tasks on the basis of Support Vector Machines have also been proposed in this paper. Features in the model have been defined. Experimental results indicate that the proposed SVM based method can significantly outperform the baseline methods for keyword extraction. The proposed method has been applied to document classification, a typical text mining processing. Experimental results show that the accuracy of document classification can be significantly improved by using the keyword extraction method.
6797006
Exploring web browser history comparisons
This work explores how comparing web navigation histories between two people and presenting the results to them might allow them to gain insight about each other. We developed a prototype that presents web matches sorted according to frequency, recency, and web site. Interviews with users of the prototype suggest that common interests and preferences can be inferred from these comparisons.
15896075
Effective bandwidth-based QoS provisioning for real-time audio/video streaming over MIMO-OFDM wireless networks
We propose a cross-layer design scheme to support the real-time quality of service (QoS) guarantees for heterogeneous mobile users over downlink MIMO-OFDM wireless networks. Inspired by the effective bandwidth theory originally established for wired networks, we develop the approach to apply the theory into wireless networks. Based on MIMO-OFDM infrastructure employed at the physical (PHY)-layer, we analytically derive the medium access control (MAC)-layer admission-control and time-slot allocation algorithms to guarantee the statistical delay-bound for different real-time users. Simulation results show that the proposed scheme can efficiently support the wireless QoS requirement for diverse real-time mobile users.
1484935
Improving genome rearrangement phylogeny using sequence-style parsimony
The study of genome rearrangements, the evolutionary events that change the order and strandedness of genes within genomes, presents new opportunities for discoveries about deep evolutionary events. The best software so far, GRAPPA, solves breakpoint and inversion phylogenies by scoring each tree topology through iterative improvements of internal node gene orders. We find that the greedy hill-climbing approach means the accuracy is limited because of multiple local optima. To address this problem, we propose integration GRAPPA with MPME, a string encoding of gene adjacency relationships whose optimal internal node assignments can be determined globally in polynomial time, to provide better initializations for GRAPPA. In simulation studies, the new algorithm yields shorter tree lengths and better accuracy in phylogeny reconstruction.