Cross-layer optimization of wireless networks using nonlinear column generation

We consider the problem of finding the jointly optimal end-to-end communication rates, routing, power allocation and transmission scheduling for wireless networks. In particular, we focus on finding the resource allocation that achieves fair end-to-end communication rates. Using realistic models of several rate and power adaption schemes, we show how this cross-layer optimization problem can be formulated as a nonlinear mathematical program. We develop a specialized solution method, based on a nonlinear column generation technique, and prove that it converges to the globally optimal solution. We present computational results from a large set of networks and discuss the insight that can be gained about the influence of power control, spatial reuse, routing strategies and variable transmission rates on network performance.     

Cross-layer optimization in TCP/IP networks

TCP-AQM can be interpreted as distributed primal-dual algorithms to maximize aggregate utility over source rates. We show that an equilibrium of TCP/IP, if exists, maximizes aggregate utility over both source rates and routes, provided congestion prices are used as link costs. An equilibrium exists if and only if this utility maximization problem and its Lagrangian dual have no duality gap. In this case, TCP/IP incurs no penalty in not splitting traffic across multiple paths. Such an equilibrium, however, can be unstable. It can be stabilized by adding a static component to link cost, but at the expense of a reduced utility in equilibrium. If link capacities are optimally provisioned, however, pure static routing, which is necessarily stable, is sufficient to maximize utility. Moreover single-path routing again achieves the same utility as multipath routing at optimality.     

A tabu search algorithm for routing optimization in mobile ad-hoc networks

In this paper, we propose a routing optimization algorithm to efficiently determine an optimal path from a source to a destination in mobile ad-hoc networks. To determine an optimal path for the nodes is important for transmitting data between nodes in densely deployed networks. In order to efficiently transmit data to its destination, the appropriate routing algorithms must be implemented in mobile ad-hoc networks. The proposed algorithm is designed by using a tabu search mechanism that is a representative meta-heuristic algorithm. The proposed tabu search algorithm carries out two neighborhood generating operations in order to determine an optimal path and minimize algorithm execution time. We compare the proposed tabu search algorithm with other meta-heuristic algorithms, which are the genetic algorithm and the simulated annealing, in terms of the routing cost and algorithm execution time. The comparison results show that the proposed tabu search algorithm outperforms the other algorithms and that it is suitable for adapting the routing optimization problem.     

Cross-layer optimization for end-to-end rate allocation in multi-radio wireless mesh networks

In this paper, we study rate allocation for a set of end-to-end communication sessions in multi-radio wireless mesh networks. We propose cross-layer schemes to solve the joint rate allocation, routing, scheduling, power control and channel assignment problems with the goals of maximizing network throughput and achieving certain fairness. Fairness is addressed using both a simplified max-min fairness model and the well-known proportional fairness model. Our schemes can also offer performance upper bounds such as an upper bound on the maximum throughput. Numerical results show that our proportional fair rate allocation scheme achieves a good tradeoff between throughput and fairness. Jian Tang is an assistant professor in the Department of Computer Science at Montana State University. He received the Ph.D. degree in Computer Science from Arizona State University in 2006. His research interest is in the area of wireless networking and mobile computing. He has served on the technical program committees of multiple international conferences, including ICC, Globecom, IPCCC and QShine. He will also serve as a publicity co-chair of International Conference on Autonomic Computing and Communication Systems (Autonomics’2007). Guoliang Xue is a Full Professor in the Department of Computer Science and Engineering at Arizona State University. He received the Ph.D. degree in Computer Science from the University of Minnesota in 1991 and has held previous positions at the Army High Performance Computing Research Center and the University of Vermont. His research interests include efficient algorithms for optimization problems in networking, with applications to fault tolerance, robustness, and privacy issues in networks ranging from WDM optical networks to wireless ad hoc and sensor networks. He has published over 150 papers in these areas. His research has been continuously supported by federal agencies including NSF and ARO. He is the recipient of an NSF Research Initiation Award in 1994 and an NSF-ITR Award in 2003. He is an Associate Editor of Computer Networks (COMNET), the IEEE Network Magazine, and Journal of Global Optimization. He has served on the executive/program committees of many IEEE conferences, including INFOCOM, SECON, IWQOS, ICC, GLOBECOM and QShine. He is the General Chair of IEEE IPCCC’2005, a TPC co-Chair of IPCCC’2003, HPSR’2004, IEEE Globecom’2006 Symposium on Wireless Ad Hoc and Sensor Networks, IEEE ICC’2007 Symposium on Wireless Ad Hoc and Sensor Networks, and QShine’2007. He is a senior member of IEEE. Weiyi Zhang received the M.E. degree in 1999 from Southeast University, China. Currently he is a Ph.D. student in the Department of Computer Science and Engineering at Arizona State University. His research interests include reliable communication in networking, protection and restoration in WDM networks, and QoS provisioning in communication networks.     

Sustainable simultaneous communications in ad-hoc networks using smart antenna systems

This article proposes an analytical model for evaluating the number of simultaneous communications that can be sustained by an ad-hoc network in which the nodes are equipped with fully adaptive smart antennas. The presented mathematical framework adopts realistic models for the antenna radiation pattern and the channel behavior, and is able to take into account the network topology and the characteristics of the medium access control (MAC) protocol in the spatial domain. The model is employed to investigate the impact of the spatial channel model and of the angular spread on network performance. Additionally, this article examines the influence of the transmission policy of the control and data packets of the MAC layer on the number of simultaneous communications.     

Cross-layer optimization for wireless multihop networks with pairwise intersession network coding

For wireless multi-hop networks with unicast sessions, most coding opportunities involve only two or three sessions as coding across many sessions requires greater transmission power to broadcast the coded symbol to many receivers, which enhances interference. This work shows that with a new flow-based characterization of pairwise intersession network coding (coding across two unicast sessions), an optimal joint coding, scheduling, and rate-control scheme can be devised and implemented using only the binary XOR operation. The new scheduling/rate-control scheme demonstrates provably graceful throughput degradation with imperfect scheduling, which facilitates the design tradeoff between the throughput optimality and computational complexity of different scheduling schemes. Our results show that pairwise intersession network coding improves the throughput of non-coding solutions regardless of whether perfect/imperfect scheduling is used. Both the deterministic and stochastic packet arrivals and departures are considered. This work shows a striking resemblance between pairwise intersession network coding and non-coded solutions, and thus advocates extensions of non-coding wisdoms to their network coding counterpart.     

自组网的密钥管理

本文介绍了自组网安全两临的威胁,对于自组网安全关键技术--密钥管理,提出了一套综合的衡量指标,概述了国内外自组网密钥管理的研究现状,并用本文的指标进行了分析。最后,提出了自组网密钥管理尚需解决的问题。     

Self-adaptive query-broadcast in wireless ad-hoc networks using fuzzy best worst method

Wireless Networks - Various broadcasting schemes have been proposed for a unified routing approach in Wireless Adhoc Networks. In their efforts, the researchers mostly aim to minimize the...     

Self-configurable fault monitoring in ad-hoc networks

While fault monitoring is a well-known issue in fixed wired networks, ad-hoc networks provide new challenges with respect to this issue: in particular, the monitoring task may be hindered at any time by the impossibility to observe a given node. This paper proposes a fault monitoring approach for ad-hoc networks which takes into account this constraint. Our approach is based on an information theory measure suitable to the intermittence of ad-hoc nodes and capable to detect network failures by inference. We define a distributed monitoring scheme with several collaborative detection methods, and we detail a self-configuration mechanism based on the K-means classification algorithm. We show how this solution can be integrated into a management architecture and evaluate its performance based an extensive set of simulations.     

Cross-layer routing in clustered optical networks

Physical layer impairment aware routing algorithms have been proposed for optical transparent networks in order to calculate the feasibility of dynamically establishing an optical path when no regeneration is used. The benefit of node clustering in optical networks, regarding routing with physical layer impairment awareness, is investigated under the CANON network architecture where regenerators are conveniently placed and routing is confined among a small subset of nodes. The CANON architecture exhibits enhanced blocking performance, high resource utilisation and adequate physical performance; hence, it can serve Quality of Service.     

Directed information dissemination in vehicular ad-hoc networks

In this article, we utilize the idea of multipoint relays (MPRs) found in literature (Jacquet et al. in Proceedings of IEEE INMIC, 2001), to propagate accident information in a restricted way (e.g., only backwards). We devise an algorithm to identify MPRs that are geographically situated behind a particular node using only its neighbor table, and speed information of the neighboring vehicles. With the identification of the backward MPRs, it is possible to restrict the information dissemination to vehicles behind a particular vehicular ad-hoc network (VANET) node only. This might benefit the approaching vehicles so that the driver could take preventive measures in real-time since he/she will have an indication of the severity of road conditions ahead. We assume that there exists an inter vehicular network using optimized link state routing (OLSR) where accident information can be propagated to all nodes using on-going OLSR control packets. We envision our application will run on top of existing routing protocols (e.g., OLSR), thereby resulting in very little integration effort, and retaining OLSR’s reduced network traffic advantage through the use of MPRs. We analyze our back MPR identification algorithm in a detailed manner. We also show that by using our approach the location of the accident alert instigator node could be pinpointed if a subset of the nodes in the same VANET know their geographical positions. We use VANET mobility models generated by SUMO into NS-3 for our simulations, and also perform preliminary experiments to verify the algorithm’s effectiveness. Our analysis and experiments show favorable results.     

Infrastructure-based MAC in wireless mobile ad-hoc networks

The IEEE 802.11 standard is the most popular Medium Access Control (MAC) protocol for wireless local area networks. However, in an ad-hoc environment, the Point Coordination Function (PCF), defined in the standard, cannot be readily used. This is due to the fact that there is no central authority to act as a Point Coordinator (PC). Peer-to-peer ad-hoc mode in the IEEE 802.11 standard only implements the Distributed Coordination Function (DCF). In this paper, an efficient and on-the-fly infrastructure is created using our proposed Mobile Point Coordinator (MPC) protocol. Based on this protocol, we also develop an efficient MAC protocol, namely MPC–MAC. Our MAC protocol extends the IEEE 802.11 standard for use in multi-hop wireless ad-hoc networks implementing both the DCF and PCF modes of operation. The goal, and also the challenge, is to achieve QoS delivery and priority access for real-time traffic in ad-hoc wireless environments while maintaining backward compatibility with the IEEE 802.11 standard. The performance of MPC–MAC is compared to the IEEE 802.11 DCF-based MAC without MPC. Simulation experiments show that in all cases the use of PCF benefits real-time packets by decreasing the average delay and the discard ratio. However, this may come at the expense of increasing the average delay for non-real-time data. On the other hand, the discard ratio for both real-time and non-real-time packets improves with the use of PCF. Therefore, our MPC–MAC outperforms the standard DCF IEEE 802.11 MAC protocol in multi-hop ad-hoc environments.     

Cross-layer optimization for SVC video delivery over the IEEE 802.11e wireless networks

The Scalable Video Coding (SVC) standard extends the H.264/AVC with scalability support and is effective to adapt bitrate to the time-varying wireless channel bandwidth. In this paper, we propose a cross-layer optimization scheme, which includes packet prioritization and QoS mapping, for the delivery of SVC over the IEEE 802.11e wireless networks. The proposed structure enables interaction among different network layers, providing differentiated services for video packets. Our cross-layer optimization performs with the following information: (i) SVC packet prioritization at the application layer, (ii) service differentiation at the MAC layer, and (iii) interface queue (IFQ) occupation status at the link layer. We formulate the QoS mapping problem as a joint optimization of access category (AC) assignment and IFQ control. A novel and efficient solution is proposed to reduce the computational complexity of the joint optimization problem. Simulation results show that the proposed approach achieves notable improvement when compared to conventional methods.     

Bandwidth-satisfied multicast trees in large-scale ad-hoc networks

The purpose of this paper is to construct bandwidth-satisfied multicast trees for QoS applications in large-scale ad-hoc networks (MANETs). Recent routing protocols and multicast protocols in large-scale MANETs adopt two-tier infrastructures to avoid the inefficiency of the flooding. Hosts with a maximal number of neighbors are often chosen as backbone hosts (BHs) to forward packets. Most likely, these BHs will be traffic concentrations/bottlenecks of the network. In addition, since host mobility is not taken into consideration in BH selection, these two-tier schemes will suffer from more lost packets if highly mobile hosts are selected as BHs. In this paper, a new multicast protocol is proposed for partitioning large-scale MANET into two-tier infrastructures. In the proposed two-tier multicast protocol, hosts with fewer hops and longer remaining connection time to the other hosts will be selected as BHs. The objective is not only to obtain short and stable multicast routes, but also to construct a stable two-tier infrastructure with fewer lost packets. Further, previous MANET quality-of-service (QoS) routing/multicasting protocols determined bandwidth-satisfied routes for QoS applications. Some are implemented as a probing scheme, but the scheme is inefficient due to high overhead and slow response. On the contrary, the others are implemented by taking advantage of routing and link information to reduce the inefficiency. However, the latter scheme suffers from two bandwidth-violation problems. In this paper, a novel algorithm is proposed to avoid the two problems, and it is integrated with the proposed two-tier multicast protocol to construct bandwidth-satisfied multicast trees for QoS applications in large-scale MANETs. The proposed algorithm aims to achieve better network performance by minimizing the number of forwarders in a tree.     

使用对偶分解的MU-CoMP-JT联合资源分配

在MU-Co MP-JT(Multi-User Coordinated Multiple-Points Joint Transmission)联合资源分配问题中,传统的迫零预编码矩阵会使得每根天线发送功率互不相同,当Co MP节点发射功率仅满足总功率约束时性能损失不明显,而当Co MP节点分布在不同的地理位置时将受到单节点功率约束,这势必会降低系统功率利用率。为了进一步提升系统吞吐量,基于对偶分解理论提出了一种联合预编码优化的资源分配算法。该算法以最大化用户权重速率为目标,将原优化问题分解成若干个优化的子问题,不同子问题对应不同接收天线数的联合优化问题。当子信道的发送天线数大于接收天线数时,通过多次迭代计算得到预编码矩阵,并且预编码矩阵会随着拉格朗日因子的变化而变化。仿真结果表明所提联合预编码优化的联合资源分配算法能够明显提升系统吞吐量,且提高天线功率利用效率。     

Interference power statistics in ad-hoc and sensor networks

There exist accurate calculation methods for estimation of interference power sum statistics in fixed-topology wireless networks based on the log-normal shadowing radio model. Here we publish essential additions to these estimation methods to expand their use to sensor networks and ad-hoc networks with changing topology. In our calculations we take into account radio propagation conditions, density of nodes, size of the network, traffic load per node and MAC protocol characteristics. The accuracy of our calculation method is verified by simulations. We highlight the influence of MAC protocols on interference and show that an increase in network size or in node density does not necessarily lead into higher interference values. Our results can be deployed to estimate the network capacity. Ramin Hekmat received M.Sc. degree in electrical engineering from Delft University of Technology (TU Delft) in the Netherlands in 1990. He worked since then for several telecommunication companies in the Netherlands and the United States in Research and Development as well as managerial positions. In September 2005 he obtained Ph.D. degree for his work related to Ad-hoc Networks form TU Delft. Currently he is working as assistant professor in the faculty of Electrical Engineering, Mathematics and Computer Science of TU Delft. His prime research interest includes multi-user communication systems, wireless communications and peer-to-peer networks. Email: r.hekmat@ewi.tudelft.nl Mailing address: Delft University of Technology Electrical Engineering, Mathematics and Computer Science P.O. Box 5031 2600 GA Delft The Netherlands. Piet Van Mieghem has obtained the Master and Ph. D. in Electrical Engineering from the K.U.Leuven (Belgium) in 1987 and 1991, respectively. He has joined the Interuniversity Micro Electronic Center (IMEC) from 1987-1991. He was a visiting scientist at MIT, department of electrical engineering from 1992-1993. From 1993 to 1998, he was working in Alcatel Corporate Research Center in Antwerp where he has gained experience in performance analysis of ATM systems and network architectural concepts of both ATM networks (PNNI) and the Internet. Currently, he is full professor at Delft University of Technology with a chair in telecommunication networks. The main theme of the research is evolution of the Internet architecture towards a broadband and QoS-aware network. Email: p.vanmieghem@ewi.tudelft.nl Mailing address: Delft University of Technology Electrical Engineering, Mathematics and Computer Science P.O. Box 5031 2600 GA Delft The Netherlands.     

The non-responsive receiver problem in mobile ad-hoc networks

IEEE 802.11 MAC based Mobile Ad-hoc Networks (MANETs) are known to experience serious unfairness problems particularly for TCP connections. The unfairness is caused by a number of factors and to date, no solution has completely addressed all the factors, so that the unfairness is never completely solved. The work presented here identifies the common factors that lead to the unfairness, and from a consideration of these, a novel solution based on carrier sensing is developed, that can completely solve the serious unfairness problem in MANETs. Simulation results are presented which show the effectiveness of our solution.     

Throughput maximization of ad-hoc wireless networks using adaptive cooperative diversity and truncated ARQ

We propose a cross-layer design which combines truncated ARQ at the link layer and cooperative diversity at the physical layer. In this scheme, both the source node and the relay nodes utilize an orthogonal space-time block code for packet retransmission. In contrast to previous cooperative diversity protocols, here cooperative diversity is invoked only if the destination node receives an erroneous packet from the source node. In addition, the relay nodes are not fixed and are selected according to the channel conditions using CRC. It will be shown that this combination of adaptive cooperative diversity and truncated ARQ can greatly improve the system throughput compared to the conventional truncated ARQ scheme and fixed cooperative diversity protocols. We further maximize the throughput by optimizing the packet length and modulation level and will show that substantial gains can be achieved by this joint optimization. Since both the packet length and modulation level are usually discrete in practice, a computationally efficient algorithm is further proposed to obtain the discrete optimal packet length and modulation level.     

Cross-layer congestion control in ad hoc wireless networks

The paper presents the problem of performance degradation of transport layer protocols due to congestion of wireless local area networks. Following the analysis of available solutions to this problem, a cross-layer congestion avoidance scheme (C³TCP) is presented, able to obtain higher performance by gathering capacity information such as bandwidth and delay at the link layer. The method requires the introduction of an additional module within the protocol stack of the mobile node, able to adjust the outgoing data stream based on capacity measurements. Moreover, a proposal to provide optional field support to existing IEEE 802.11 protocol, in order to support the presented congestion control solution as well as many other similar approaches, is presented. Achieved results underline good agreement with design considerations and high utilization of the available resources.