A Bidding Algorithm for Optimized Utility-Based Resource Allocation in Ad Hoc Networks:
Abstract—This paper proposes a scheme for bandwidth allocation in wireless ad hoc networks. The quality-of-service (QoS) levels for each end-to-end flow are expressed using a resource-utility function, and our algorithms aim to maximize aggregated utility. The shared channel is modeled as a bandwidth resource defined by maximal cliques of mutual interfering links. We propose a novel resource allocation algorithm that employs an auction mechanism in which flows are bidding for resources. The bids depend both on the flow’s utility function and the intrinsically derived shadow prices. We then combine the admission control scheme with a utility- aware on-demand shortest path routing algorithm where shadow prices are used as a natural distance metric. As a baseline for evaluation, we show that the problem can be formulated as a linear programming (LP) problem. Thus, we can compare the performance of our distributed scheme to the centralized LP solution, registering results very close to the optimum. Next, we isolate the performance of price-based routing and show its advantages in hotspot scenarios, and also propose an asynchronous version that is more feasible for ad hoc environments. Further experimental evaluation compares our scheme with the state of the art derived from Kelly’s utility maximization framework and shows that our approach exhibits superior performance for networks with increased mobility or less frequent allocations.
INTRODUCTION
MOBILE ad hoc networks are formed by wireless nodes that move freely and have no fixed infrastructure.
Each node in the network may act as a router for other nodes, and flows follow a multihop path from source to destination. The infrastructure-less flexibility makes ad hoc networks a strong complement to cellular networks, and ideal for many novel scenarios such as cooperative information sharing, defense applications, and disaster management. Mobile ad hoc networks will support a wide range of services in which soft real-time (multimedia) and high-priority critical data seamlessly integrate. As society becomes dependable on the provision of such services, their availability under overloads becomes a critical issue.
In comparison to wireline networks, wireless multihop networks will always be more resource constrained due to several fundamental differences. The first major issue is the limited spectrum of the locally shared communication channel. Neighboring nodes can interfere and cannot transmit independently. The second major difference is the mobility of the nodes and its effect on the established paths. That is, paths are constantly created and destroyed, requiring flow rerouting in the latter case. Network resources such as bandwidth and power have to be dealt with in fundamentally different ways compared to wireline or centralized cellular networks. Resource availability can quickly change, and therefore, continuous resource reallocation is needed to provide graceful degradation during overloads, or quality-of-service (QoS) improvements when more resources become available.
.
.
.
.
.
.
RELATED WORK
Work in resource allocation for ad hoc wireless networks has been addressed either at the MAC level, as an extension to routing, or at an optimization policy level.
Bandwidth availability in ad hoc networks can be either precomputed [3], [4], [6] or measured at MAC level [3]. Xue and Ganz [6] compute the available bandwidth at a node as the channel bandwidth minus the bandwidth consumed by the traffic at all neighbors. While easy to implement, this is too pessimistic, and better models can be created when interference structures are built based on link interference [3], [4]. In this work, we use the contention model based on maximal cliques of contending links [3]. If no global optimization is sought, resource allocation can be attempted
independently at every node by appropriate MAC layer design. Luo et al. [4] present a packet scheduling approach to ensure a minimum weighted-fair scheduling combined with maximizing spatial reuse of channel.
In several earlier works, resource allocation/reservation is treated as an extension of the routing protocol. For instance, Chen and Nahrstedt [7] propose an on-demand distributed routing algorithm that aims to avoid flooding the network.
They consider delay and bandwidth constrained least cost problems. The feature of the “bandwidth routing” [8] protocol is that link-layer scheduling is directly considered in the protocol. Al-Karaki and Kamal provide a survey on QoS routing problems [9]. QoS routing is usually not directly aimed at optimal resource allocation but at finding either the shortest path that satisfies at least some minimum QoS requirements, or the path that gives the largest margins for a QoS constraint. In our work, however, the routing algorithm is part of the global allocation optimization scheme.
PROBLEM FORMULATION
In this section, we first outline our utility and network model, followed by the LP formulation of the allocation problem. We then present the notion of shadow prices and highlight some properties of the optimal solution that will be used as a guideline when constructing the distributed algorithm.
3.1 Utility Functions
Many types of mobile applications support different QoS levels. For example, multimedia services can decrease audio or picture quality to meet some bandwidth or delay restrictions, while applications like e-mail or file sharing can usually adapt to anything available. The changes in application utility depend on the amount of allocated resource and can be captured by an associated utility function. By using utility functions in the allocation process, a clear quantitative differentiation can be made among competing applications. Thus, the system can optimize QoS by lowering the allocation for the least efficient applications during overload periods and increasing the allocation of the most efficient ones when resources become available.
Moreover, online negotiations are not needed as they are intrinsically built in the utility functions.
DISTRIBUTED RESOURCE (RE)ALLOCATION
The ad hoc network considered in this work is an open dynamic system where resource request and availability are always changing. Therefore, our scheme employs periodic reallocations to keep the resource usage optimized. As end to-end connections span several nodes and clique resources, it is important that (re)allocations are well coordinated along the path. Moreover, reallocations imply a “mode” change for applications so their number should be strictly controlled. In this section, we present an algorithm that uses allocation rounds that are synchronized for all clique resources. The use of periodic, synchronized allocation rounds guarantees that flows will enjoy a fixed allocation for at least one period. It also puts a bound on the reallocation rate in the system, even if the rate of events (traffic and topology changes) is much higher. Later, in Section 4.6, we propose a new version of the algorithm that works also when the allocation rounds are not synchronized among the clique resources. Choosing an appropriate period size implies a trade-off. The shorter the period, the better the system is at keeping the utility optimized but the larger the computation and signaling overhead.
4.4 Mobility and Clique Construction
Due to mobility, a node might enter or exit the communication range of another one, thus creating a newwireless link, or alternatively breaking one. Discovery of topology changes can be implemented either event-based (using MAC feedback) or periodically (local broadcast of hello messages).
As mentioned previously, only local information is needed to construct the maximal cliques. We know that only links adjacent to nodes that are at most three hops away might contend with each other (see Section 3.2). Thus,if all nodes send their neighborhood list three hops away, every node will be able to identify all the cliques containing any adjacent link [3].
DOWNLOAD LINK:
CLICK ME
Abstract—This paper proposes a scheme for bandwidth allocation in wireless ad hoc networks. The quality-of-service (QoS) levels for each end-to-end flow are expressed using a resource-utility function, and our algorithms aim to maximize aggregated utility. The shared channel is modeled as a bandwidth resource defined by maximal cliques of mutual interfering links. We propose a novel resource allocation algorithm that employs an auction mechanism in which flows are bidding for resources. The bids depend both on the flow’s utility function and the intrinsically derived shadow prices. We then combine the admission control scheme with a utility- aware on-demand shortest path routing algorithm where shadow prices are used as a natural distance metric. As a baseline for evaluation, we show that the problem can be formulated as a linear programming (LP) problem. Thus, we can compare the performance of our distributed scheme to the centralized LP solution, registering results very close to the optimum. Next, we isolate the performance of price-based routing and show its advantages in hotspot scenarios, and also propose an asynchronous version that is more feasible for ad hoc environments. Further experimental evaluation compares our scheme with the state of the art derived from Kelly’s utility maximization framework and shows that our approach exhibits superior performance for networks with increased mobility or less frequent allocations.
INTRODUCTION
MOBILE ad hoc networks are formed by wireless nodes that move freely and have no fixed infrastructure.
Each node in the network may act as a router for other nodes, and flows follow a multihop path from source to destination. The infrastructure-less flexibility makes ad hoc networks a strong complement to cellular networks, and ideal for many novel scenarios such as cooperative information sharing, defense applications, and disaster management. Mobile ad hoc networks will support a wide range of services in which soft real-time (multimedia) and high-priority critical data seamlessly integrate. As society becomes dependable on the provision of such services, their availability under overloads becomes a critical issue.
In comparison to wireline networks, wireless multihop networks will always be more resource constrained due to several fundamental differences. The first major issue is the limited spectrum of the locally shared communication channel. Neighboring nodes can interfere and cannot transmit independently. The second major difference is the mobility of the nodes and its effect on the established paths. That is, paths are constantly created and destroyed, requiring flow rerouting in the latter case. Network resources such as bandwidth and power have to be dealt with in fundamentally different ways compared to wireline or centralized cellular networks. Resource availability can quickly change, and therefore, continuous resource reallocation is needed to provide graceful degradation during overloads, or quality-of-service (QoS) improvements when more resources become available.
.
.
.
.
.
.
RELATED WORK
Work in resource allocation for ad hoc wireless networks has been addressed either at the MAC level, as an extension to routing, or at an optimization policy level.
Bandwidth availability in ad hoc networks can be either precomputed [3], [4], [6] or measured at MAC level [3]. Xue and Ganz [6] compute the available bandwidth at a node as the channel bandwidth minus the bandwidth consumed by the traffic at all neighbors. While easy to implement, this is too pessimistic, and better models can be created when interference structures are built based on link interference [3], [4]. In this work, we use the contention model based on maximal cliques of contending links [3]. If no global optimization is sought, resource allocation can be attempted
independently at every node by appropriate MAC layer design. Luo et al. [4] present a packet scheduling approach to ensure a minimum weighted-fair scheduling combined with maximizing spatial reuse of channel.
In several earlier works, resource allocation/reservation is treated as an extension of the routing protocol. For instance, Chen and Nahrstedt [7] propose an on-demand distributed routing algorithm that aims to avoid flooding the network.
They consider delay and bandwidth constrained least cost problems. The feature of the “bandwidth routing” [8] protocol is that link-layer scheduling is directly considered in the protocol. Al-Karaki and Kamal provide a survey on QoS routing problems [9]. QoS routing is usually not directly aimed at optimal resource allocation but at finding either the shortest path that satisfies at least some minimum QoS requirements, or the path that gives the largest margins for a QoS constraint. In our work, however, the routing algorithm is part of the global allocation optimization scheme.
PROBLEM FORMULATION
In this section, we first outline our utility and network model, followed by the LP formulation of the allocation problem. We then present the notion of shadow prices and highlight some properties of the optimal solution that will be used as a guideline when constructing the distributed algorithm.
3.1 Utility Functions
Many types of mobile applications support different QoS levels. For example, multimedia services can decrease audio or picture quality to meet some bandwidth or delay restrictions, while applications like e-mail or file sharing can usually adapt to anything available. The changes in application utility depend on the amount of allocated resource and can be captured by an associated utility function. By using utility functions in the allocation process, a clear quantitative differentiation can be made among competing applications. Thus, the system can optimize QoS by lowering the allocation for the least efficient applications during overload periods and increasing the allocation of the most efficient ones when resources become available.
Moreover, online negotiations are not needed as they are intrinsically built in the utility functions.
DISTRIBUTED RESOURCE (RE)ALLOCATION
The ad hoc network considered in this work is an open dynamic system where resource request and availability are always changing. Therefore, our scheme employs periodic reallocations to keep the resource usage optimized. As end to-end connections span several nodes and clique resources, it is important that (re)allocations are well coordinated along the path. Moreover, reallocations imply a “mode” change for applications so their number should be strictly controlled. In this section, we present an algorithm that uses allocation rounds that are synchronized for all clique resources. The use of periodic, synchronized allocation rounds guarantees that flows will enjoy a fixed allocation for at least one period. It also puts a bound on the reallocation rate in the system, even if the rate of events (traffic and topology changes) is much higher. Later, in Section 4.6, we propose a new version of the algorithm that works also when the allocation rounds are not synchronized among the clique resources. Choosing an appropriate period size implies a trade-off. The shorter the period, the better the system is at keeping the utility optimized but the larger the computation and signaling overhead.
4.4 Mobility and Clique Construction
Due to mobility, a node might enter or exit the communication range of another one, thus creating a newwireless link, or alternatively breaking one. Discovery of topology changes can be implemented either event-based (using MAC feedback) or periodically (local broadcast of hello messages).
As mentioned previously, only local information is needed to construct the maximal cliques. We know that only links adjacent to nodes that are at most three hops away might contend with each other (see Section 3.2). Thus,if all nodes send their neighborhood list three hops away, every node will be able to identify all the cliques containing any adjacent link [3].
DOWNLOAD LINK:
CLICK ME
No comments:
Post a Comment