Optimal and Distributed Protocols for Cross-Layer Design of Physical and Transport Layers in MANETs

We seek distributed protocols that attain the global optimum allocation of link transmitter powers and source rates in a cross-layer design of a mobile ad hoc network. Although the underlying network utility maximization is nonconvex, convexity plays a major role in our development. We provide new convexity results surrounding the Shannon capacity formula, allowing us to abandon suboptimal high-SIR approximations that have almost become entrenched in the literature. More broadly, these new results can be back-substituted into many existing problems for similar benefit.      

Maximizing multicast lifetime in unreliable wireless ad hoc network

Multicast is an efficient method for transmitting the same packets to a group of destinations. In energy-constrained wireless ad hoc networks where nodes are powered by batteries, one of the challenging issues is how to prolong the multicast lifetime. Most of existing work mainly focuses on multicast lifetime maximization problem in wireless packet loss-free networks. However, this may not be the case in reality. In this paper, we are concerned with the multicast lifetime maximization problem in unreliable wireless ad hoc networks. To solve this problem, we first define the multicast lifetime as the number of packets transmitted along the multicast tree successfully. Then we develop a novel lifetime maximization genetic algorithm to construct the multicast tree consisting of high reliability links subject to the source and destination nodes. Simulation results demonstrate the efficiency and effectiveness of the proposed algorithm.     

Ad hoc网络中的功率控制算法研究

功率控制对于有效地使用和管理无线频谱资源也有着举足轻重的作用。通过对Ad hoc网络的分析,提出了一种基于博弈论的分布式功率控制算法,并证明了所设计的博弈功率效用函数的纳什均衡存在且唯一,同时给出了获得纳什均衡的功率调整方法。仿真结果表明,所提出的算法具有很快的收敛速度,同时通过适当调整代价函数因子,可以区分不同用户等级,实现不同等级用户的的通信要求。     

Optimal resource allocation in wireless ad hoc networks: a price-based approach

The shared-medium multihop nature of wireless ad hoc networks poses fundamental challenges to the design of effective resource allocation algorithms that are optimal with respect to resource utilization and fair across different network flows. None of the existing resource allocation algorithms in wireless ad hoc networks have realistically considered end-to-end flows spanning multiple hops. Moreover, strategies proposed in wireline networks are not applicable in the context of wireless ad hoc networks, due to their unique characteristics of location-dependent contention. In this paper, we propose a new price-based resource allocation framework in wireless ad hoc networks to achieve optimal resource utilization and fairness among competing end-to-end flows. We build our pricing framework on the notion of maximal cliques in wireless ad hoc networks, as compared to individual links in traditional wide-area wireline networks. Based on such a price-based theoretical framework, we present a two-tier iterative algorithm. Distributed across wireless nodes, the algorithm converges to a global network optimum with respect to resource allocations. We further improve the algorithm toward asynchronous network settings and prove its convergence. Extensive simulations under a variety of network environments have been conducted to validate our theoretical claims.     

Optimal rate allocation for energy-efficient multipath routing in wireless ad hoc networks

In this paper, we address the problem of energy efficiency in wireless ad hoc networks. We consider an ad hoc network comprising a set of sources, communicating with their destinations using multiple routes. Each source is associated with a utility function which increases with the total traffic flowing over the available source-destination routes. The network lifetime is defined as the time until the first node in the network runs out of energy. We formulate the problem as one of maximizing the sum of the source utilities subject to a required constraint on the network lifetime. We present a primal formulation of the problem, which uses penalty functions to take into account the system constraints, and we introduce a new methodology for solving the problem. The proposed approach leads to a flow control algorithm, which provides the optimal source rates and can be easily implemented in a distributed manner. When compared with the minimum transmission energy routing scheme, the proposed algorithm gives significantly higher source rates for the same network lifetime guarantee.     

Utility‐optimal cross‐layer resource allocation in distributed wireless cooperative networks

In this paper, we propose a distributed cross‐layer resource allocation algorithm for wireless cooperative networks based on a network utility maximization framework. The algorithm provides solutions to relay selections, flow pass probabilities, transmit rate, and power levels jointly with optimal congestion control and power control through balancing link and physical layers such that the network‐wide utility is optimized. Via dual decomposition and subgradient method, we solve the utility‐optimal resource allocation problem by subproblems in different layers of the protocol stack. Furthermore, by introducing a concept of pseudochannel gain, we model both the primal direct logical link and its corresponding cooperative transmission link as a single virtual direct logical link to simplify our network utility framework. Eventually, the algorithm determines its primal resource allocation levels by employing reverse‐engineering of the pseudochannel gain model. Numerical experiments show that the convergence of the proposed algorithm can be obtained and the performance of the optimized network can be improved significantly. Copyright © 2012 John Wiley & Sons, Ltd.     

Power Management in MIMO Ad Hoc Networks: A Game-Theoretic Approach

This paper considers interference characterization and management in wireless ad hoc networks using MIMO techniques. The power allocation in each link is built into a non-cooperative game where a utility function is identified and maximized. Due to poor channel conditions, some links have very low data transmission rates even though their transmit powers are high. Therefore, a mechanism for shutting down links is proposed in order to reduce cochannel interference and improve energy efficiency. The multiuser water-filling and the gradient projection methods are compared with the proposed game theoretic approach in terms of system capacity and energy efficiency. It is shown that using the proposed method with the link shut-down mechanism allows the MIMO ad hoc network to achieve the highest energy efficiency and the highest system capacity     

Maximum lifetime broadcast communications in cooperative multihop wireless ad hoc networks: Centralized and distributed approaches

We investigate the problem of broadcast routing in energy constrained stationary wireless ad hoc networks with an aim to maximizing the network lifetime measured as the number of successive broadcast sessions that can be supported. We propose an energy-aware spanning tree construction scheme supporting a broadcast request, considering three different signal transmission schemes in the physical layer: (a) point-to-point, (b) point-to-multipoint, and (c) multipoint-to-point. First we present a centralized algorithm that requires global topology information. Next, we extend this to design an approximate distributed algorithm, assuming the availability of k-hop neighborhood information at each node, with k as a parameter. We prove that the centralized scheme has time complexity polynomial in the number of nodes and the distributed scheme has a message complexity that is linear in the number of nodes. Results of numerical experiments demonstrate significant improvement in network lifetime following our centralized scheme compared to existing prominent non-cooperative broadcasting schemes proposed to solve the same lifetime maximization problem in wireless ad hoc networks. Due to lack of global topology information, the distributed solution does not produce as much advantage as the centralized solution. However, we demonstrate that with increasing value of k, the performance of the distributed scheme also improves significantly.     

An End-to-End Bandwidth Allocation Algorithm for Ad Hoc Networks

Bandwidth-guaranteed QoS service in ad hoc networks is a challenging task due to several factors such as the absence of the central control, the dynamic network topology, the hidden terminal problem and the multihop routing property. An end-to-end bandwidth allocation algorithm was proposed in [Lin and Liu, 15] to support the QoS service in ad hoc networks. However, without exploring the global resource information along the route, the performance of that algorithm is quite limited. In addition, it also incurs significant control overhead. We develop a new algorithm for end-to-end bandwidth calculation and assignment in ad hoc networks which utilizes the global resource information along the route to determine the available end-to-end bandwidth. Our method also employs the topology-transparent scheduling technology to reduce the control overhead. The proposed algorithm can be efficiently utilized in a distributed manner. Both theoretical analysis and simulation results show that our end-to-end bandwidth allocation scheme can significantly improve the network capacity compared with the existing method.     

Experimental investigation of wireless link layer for multi-hop oceanographic-sensor networks

A wireless link layer designed for a spatially distributed, ad hoc multi-hop wireless sensor network for use in oceanography is described.     

无线多跳网络快速跨层资源优化分配算法

针对背压路由算法容易造成大量队列积压和收敛速度慢的缺陷,该文研究了无线多跳网络中节点功率受限情况下的联合拥塞控制、路由和功率分配的跨层优化问题。以最大化网络效用为目标,以流平衡条件、功率等为约束条件建模,基于牛顿法提出了一种具有超线性收敛性能的算法,并运用矩阵分裂技术使该算法能够分布式实施。仿真结果表明,该算法在实现网络效用最大化的同时,能够有效提高网络中的能量效用,且能将网络中的队列长度稳定在一个较低水平,降低包传输延时。     

Jointly Optimal Congestion and Power Control for Rayleigh-Faded Channels with Outage Constraints

We address the problem of joint congestion control and power control with link outage constraints in Rayleigh fast-fading and multihop wireless networks. Because of packet loss caused by the fast-fading-induced link outage, the data rate received successfully at the destination node (the effective rate) is much lower than the transmission rate at the source node (the injection rate). In this paper, a novel model, i.e., effective network utility maximization with power control (ENUMP), is designed to formulate this scenario. In ENUMP, the network utility is associated with the effective rate, and an effective network utility maximization formulation with link outage constraints is used. Although the original problem is non-convex and non-separable, we can still construct a distributed algorithm by applying appropriate transformations. Since in our model we sufficiently take into account the statistical variations of the signal-to-interference ratio, the power updates do not follow the instantaneous state of the fast-fading channel. Simulation results show that the optimal solution of our algorithm is close to the globally optimal solution. Besides, simulation results also verify that ENUMP achieves significant gains of the effective rate, the network utility, and the network congestion control over an existing famous model.     

Cross‐Layer Resource Allocation in Multi‐interface Multi‐channel Wireless Multi‐hop Networks

In this paper, an analytical framework is proposed for the optimization of network performance through joint congestion control, channel allocation, rate allocation, power control, scheduling, and routing with the consideration of fairness in multi‐channel wireless multi‐hop networks. More specifically, the framework models the network by a generalized network utility maximization (NUM) problem under an elastic link data rate and power constraints. Using the dual decomposition technique, the NUM problem is decomposed into four subproblems — flow control; next‐hop routing; rate allocation and scheduling; power control; and channel allocation — and finally solved by a low‐complexity distributed method. Simulation results show that the proposed distributed algorithm significantly improves the network throughput and energy efficiency compared with previous algorithms.     

Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks

A maximum likelihood (ML) acoustic source location estimation method is presented for the application in a wireless ad hoc sensor network. This method uses acoustic signal energy measurements taken at individual sensors of an ad hoc wireless sensor network to estimate the locations of multiple acoustic sources. Compared to the existing acoustic energy based source localization methods, this proposed ML method delivers more accurate results and offers the enhanced capability of multiple source localization. A multiresolution search algorithm and an expectation-maximization (EM) like iterative algorithm are proposed to expedite the computation of source locations. The Crame/spl acute/r-Rao Bound (CRB) of the ML source location estimate has been derived. The CRB is used to analyze the impacts of sensor placement to the accuracy of location estimates for single target scenario. Extensive simulations have been conducted. It is observed that the proposed ML method consistently outperforms existing acoustic energy based source localization methods. An example applying this method to track military vehicles using real world experiment data also demonstrates the performance advantage of this proposed method over a previously proposed acoustic energy source localization method.     

Stable routing algorithm for mobile ad hoc networks using mobile agent

Wireless ad hoc networks are growing important because of their mobility, versatility, and ability to work with fewer infrastructures. The mobile ad hoc network is an autonomous system consisting of mobile nodes connected with wireless links. Establishing a path between two nodes is a complex task in wireless networks. It is still more complex in the wireless mobile ad hoc network because every node is no longer as an end node and an intermediate node. In this paper, it focuses on design of connectionless routing protocol for the wireless ad hoc networks based on the mobile agent concept. The proposed model tries to discover the best path taking into consideration some concerns like bandwidth, reliability, and congestion of the link. The proposed model has been simulated and tested under various wireless ad hoc network environments with the help of a different number of nodes. The results demonstrate that the proposed model is more feasible for providing reliable paths between the source and destination with the minimum control message packets over the network. It has delivered more number of packets to the destination over the network. Copyright © 2012 John Wiley & Sons, Ltd.     

Dynamic Rate and Power Allocation in Wireless Ad Hoc Networks with Elastic and Inelastic Traffic

In this paper, we focus on the problem of dynamic rate and power allocation in wireless ad hoc networks with slow-fading channels, where a mixture of elastic and inelastic traffic is supported. A stochastic optimization problem incorporating the quality of service requirements of the two types of traffic is formulated, which aims to maximize the network performance by allocating the power for each link and controlling the service rates of all flows in the network. Since the utility functions of inelastic flows may be non-concave, which are difficult to be readily transformed to be concave, the proposed original problem is non-convex. However, despite the existing difficulty, a dynamic rate and power allocation algorithm (named DRPAA), is proposed to solve the original optimization problem. In DRPAA, both the stochastic duality theory and the particle swarm optimization approach are used, and this dynamic algorithm provides a good approximation to the optimal solution when the variation of the channel condition of each link gets larger. By using DRPAA, flow rates and link powers are dynamically allocated in each network state without the need for the distribution of the network states. Simulation results show that DRPAA has a good convergence speed and can efficiently utilize network resources to improve the network performance.     

Efficient Opportunistic Routing in Utility-Based Ad Hoc Networks

Due to resource scarcity, a paramount concern in ad hoc networks is utilizing limited resources efficiently. The self-organized nature of ad hoc networks makes the network utility-based approach an efficient way to allocate limited resources. However, the effect of link instability has not yet been adequately addressed in literature. To efficiently address the routing problem in ad hoc networks, we integrate the cost and stability into a network utility metric, and adopt the metric to evaluate the routing optimality in a unified, opportunistic routing model. Based on this model, an efficient algorithm is designed, both centralized and distributed implementations are presented, and extensive simulations on NS-2 are conducted to verify our results.     

Joint data rate and power allocation for lifetime maximization in interference limited ad hoc networks

In this paper, we consider the following problem in the wireless ad hoc network: Given a set of paths between source and destination, how to divide the data flow among the paths and how to control the transmission rates, times, and powers of the individual links in order to maximize the operation time of the worst network node. If all nodes are of equal importance, the operation time of the worst node is also the lifetime of the network. By solving the problem, our aim is to investigate how the network lifetime is affected by link conditions such as the maximum transmission power of a node and the peak data rate of a link. For the purpose, we start from a system model that incorporates the carrier to interference ratio (CIR) into a variable data rate of a link. With this, we can develop an iterative algorithm for the lifetime maximization, which resembles to the distributed power control in cellular systems. Numerical examples on the iterative algorithm are included to illustrate the network lifetime as a function of the maximum transmission power and the peak data rate.     

Balancing transport and physical Layers in wireless multihop networks: jointly optimal congestion control and power control

In a wireless network with multihop transmissions and interference-limited link rates, can we balance power control in the physical layer and congestion control in the transport layer to enhance the overall network performance while maintaining the architectural modularity between the layers? We answer this question by presenting a distributed power control algorithm that couples with existing transmission control protocols (TCPs) to increase end-to-end throughput and energy efficiency of the network. Under the rigorous framework of nonlinearly constrained utility maximization, we prove the convergence of this coupled algorithm to the global optimum of joint power control and congestion control, for both synchronized and asynchronous implementations. The rate of convergence is geometric and a desirable modularity between the transport and physical layers is maintained. In particular, when congestion control uses TCP Vegas, a simple utilization in the physical layer of the queueing delay information suffices to achieve the joint optimum. Analytic results and simulations illustrate other desirable properties of the proposed algorithm, including robustness to channel outage and to path loss estimation errors, and flexibility in trading off performance optimality for implementation simplicity. This work presents a step toward a systematic understanding of "layering" as "optimization decomposition," where the overall communication network is modeled by a generalized network utility maximization problem, each layer corresponds to a decomposed subproblem, and the interfaces among layers are quantified as the optimization variables coordinating the subproblems. In the case of the transport and physical layers, link congestion prices turn out to be the optimal "layering prices.".     

Minimum-energy all-to-all multicasting in wireless ad hoc networks

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-Complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.