Latest Multi-Hop Wireless Networks projects 2012-2013 |Free Download|

Download Project Paper|Documents Distributed Scheduling in Multihop Wireless Networks with Maxmin Fairness Provisioning

ABSTRACT

Fair allocation of resources is an important consideration in the design of wireless networks. In this paper, we consider the setting of multihop wireless networks with multiple routing paths and develop an online flow control and scheduling algorithm for packet admission and link activation that achieves high aggregate throughput while providing different data flows with a fair share of network capacity. For fairness provisioning, we seek to maximize the minimum throughput provided to flows in the network. To cope with different degrees of data reliability among the different links in the network, we use different channel code rates as appropriate. While we expect performance improvement using channel coding and multipath routing, the main contribution of our work is a joint treatment of network stability, multipath routing and link-level reliability in meeting the overarching goal of maxmin fairness. We develop a decentralized, and hence practical, scheduling policy that addresses various concerns and demonstrate, via simulations, that it is competitive with respect to an optimal centralized rate allocator. We also evaluate the fairness provisioning under the proposed algorithm and show that channel coding improves the performance of the network significantly. Finally, we show through simulations that the proposed algorithm outperforms a class of existing approaches on fairness provisioning, which are developed based on utility maximization.

Delay Analysis and Optimality of Scheduling Policies for Multi-Hop Wireless Networks

 Abstract

We analyze the delay performance of a multi-hop wireless network in which the routes between source-destination pairs are fixed. We develop a new queue grouping technique to handle the complex correlations of the service process resulting from the multi-hop nature of the flows and their mutual sharing of the wireless medium. A general set based interference model is assumed that imposes constraints on links that can be served simultaneously at any given time. These interference constraints are used to obtain a fundamental lower bound on the delay performance of any scheduling policy for the system. We present a systematic methodology to derive such lower bounds. For a special wireless system, namely the clique, we design a policy that is sample path delay optimal. For the tandem queue network, where the delay optimal policy is known, the expected delay of the optimal policy numerically coincides with the lower bound. The lower bound analysis provides useful insights into the design and analysis of optimal or nearly optimal scheduling policies.

Existing System

 A large number of studies on multi-hop wireless networks have been devoted to system stability while maximizing metrics like throughput or utility. These metrics measure the performance of a system over a long time-scale. For a large class of applications such as video or voice over IP, embedded network control and for system design; metrics like delay are of prime importance. The delay performance of wireless networks, however, has largely been an open problem. This problem is notoriously difficult even in the context of wireline networks, primarily because of the complex interactions in the network (e.g., superposition, routing, departure, etc.) that make its analysis amenable only in very special cases like the product form networks. The problem is further exacerbated by the mutual interference inherent in wireless networks which, complicates both the scheduling mechanisms and their analysis. Some novel analytical techniques to compute useful lower bound and delay estimates for wireless networks with singlehop traffic were developed in. However, the analysis is not directly applicable to multi-hop wireless network with multihop flows, due to the difficulty in characterizing the departure process at intermediate links. The metric of interest in this paper is the system-wide average delay of a packet from the source to its corresponding destination. We present a new, systematic methodology to obtain a fundamental lower bound on the average packet delay in the system under any scheduling policy. Furthermore, we re-engineer well known scheduling policies to achieve good delay performance viz-a-viz the lower bound.

Proposed System

We analyze a multi-hop wireless network with multiple source-destination pairs, given routing and traffic information. Each source injects packets in the network, which traverses through the network until it reaches the destination. For example, a multi-hop wireless network with three flows is shown in Fig. 1. The exogenous arrival processes AI (t), AII (t) and AIII (t) correspond to the number of packets injected in the system at time t. A packet is queued at each node in its path where it waits for an opportunity to be transmitted. Since the transmission medium is shared, concurrent transmissions can interfere with each others’ transmissions. The set of links that do not cause interference with each other can be scheduled simultaneously, and we call them activation vectors(matchings). We do not impose any a priori restriction on the set of allowed activation vectors, i.e., they can characterize any combinatorial interference model. For example, in a K-hop interference model, the links scheduled simultaneously are separated by at least K hops. In the example show in Fig. 1, each link has unit capacity; i.e., at most one packet can be transmitted in a slot. For the above example, we assume a 1-hop interference model.

Ranking Spatial Data by Quality Preferences

Abstract:

A spatial preference query ranks objects based on the qualities of features in their spatial neighborhood. For example, using a real estate agency database of flats for lease, a customer may want to rank the flats with respect to the appropriateness of their location, defined after aggregating the qualities of other features (e.g., restaurants, cafes, hospital, market, etc.) within their spatial neighborhood. Such a neighborhood concept can be specified by the user via different functions. It can be an explicit circular region within a given distance from the flat. Another intuitive definition is to assign higher weights to the features based on their proximity to the flat. In this paper, we formally define spatial preference queries and propose appropriate indexing techniques and search algorithms for them. Extensive evaluation of our methods on both real and synthetic data reveals that an optimized branch-and-bound solution is efficient and robust with respect to different parameters.

Existing System:

To our knowledge, there is no existing efficient solution for processing the top-k spatial preference query.Object ranking is a popular retrieval task in various applications. In relational databases, we rank tuples using an aggregate score function on their attribute values. For example, a real estate agency maintains a database that contains information of flats available for rent. A potential customer wishes to view the top-10 flats with the largest sizes and lowest prices. In this case, the score of each flat is expressed by the sum of two qualities: size and price, after normalization to the domain (e.g., 1 means the largest size and the lowest price). In spatial databases, ranking is often associated to nearest neighbor (NN) retrieval. Given a query location, we are interested in retrieving the set of nearest objects to it that qualify a condition (e.g., restaurants). Assuming that the set of interesting objects is indexed by an R-tree , we can apply distance bounds and traverse the index in a branch-and-bound fashion to obtain the answer.

Proposed System:

We Propose (i) spatial ranking, which orders the objects according to their distance from a reference point, and (ii) non-spatial ranking, which orders the objects by an aggregate function on their non-spatial values. Our top- k spatial preference query integrates these two types of ranking in an intuitive way. As indicated by our examples, this new query has a wide range of applications in service recommendation and decision support systems. To our knowledge, there is no existing efficient solution for processing the top-k spatial preference query. A brute-force approach (to be elaborated in Section 3.2) for evaluating it is to compute the scores of all objects in D and select the top-k ones. This method, however, is expected to be very expensive for large input datasets.

Module Description:

1. Spatial Ranking
2. Non-Spatial ranking
3. Neighbor (NN) Retrieval
4. Spatial Query Evaluation on R-trees

Spatial Ranking

spatial ranking, which orders the objects according to their distance from a reference point.

Non-Spatial Ranking:

Non-spatial ranking, which orders the objects by an aggregate function on their non-spatial values. Our top- k spatial preference query integrates these two types of ranking in an intuitive way. As indicated by our examples, this new query has a wide range of applications in service recommendation and decision support systems. To our knowledge, there is no existing efficient solution for processing the top-k spatial preference query.