Maxmin fair scheduling in wireless ad hoc networks

We investigate from an algorithmic perspective the maxmin fair allocation of bandwidth in wireless ad hoc networks. We formalize the maxmin fair objective under wireless scheduling constraints, and present a necessary and sufficient condition for maxmin fairness of a bandwidth allocation. We propose an algorithm that assigns weights to the sessions dynamically such that the weights depend on the congestion in the neighborhood, and schedules the sessions that constitute a maximum weighted matching. We prove that this algorithm attains the maxmin fair rates, even though it does not use any information about the statistics of the packet arrival process.     

Minimum power energy spanners in wireless ad hoc networks

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The energy of a transmission path from node u to node v is the sum of the squares of the distances between adjacent nodes along the path. For a constant t > 1, an energy t-spanner is a graph G′, such that for any two nodes u and v, there exists a path from u to v in G′, whose energy is at most t times the energy of a minimum-energy path from u to v in the complete Euclidean graph. In this paper, we study the problem of finding a power assignment, such that (1) its induced communication graph is a ‘good’ energy spanner, and (2) its cost is ‘low’. We show that for any constant t > 1, one can find a power assignment, such that its induced communication graph is an energy t-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph). This is a significant improvement over the previous result due to Shpungin and Segal in Proceedings of 28th IEEE INFOCOM, pp 163–171, (2009).     

Joint scheduling and power control for wireless ad hoc networks

In this paper, we introduce a cross-layer design framework to the multiple access problem in contention-based wireless ad hoc networks. The motivation for this study is twofold, limiting multiuser interference to increase single-hop throughput and reducing power consumption to prolong battery life. We focus on next neighbor transmissions where nodes are required to send information packets to their respective receivers subject to a constraint on the signal-to-interference-and-noise ratio. The multiple access problem is solved via two alternating phases, namely scheduling and power control. The scheduling algorithm is essential to coordinate the transmissions of independent users in order to eliminate strong levels of interference (e.g., self-interference) that cannot be overcome by power control. On the other hand, power control is executed in a distributed fashion to determine the admissible power vector, if one exists, that can be used by the scheduled users to satisfy their single-hop transmission requirements. This is done for two types of networks, namely time-division multiple-access (TDMA) and TDMA/code-division multiple-access wireless ad hoc networks.     

Energy efficient broadcast routing in static ad hoc wireless networks

In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.     

Localized energy efficient routing in mobile ad hoc networks

We consider the problem of localized energy aware routing in mobile ad hoc networks. In localized routing algorithms, each node forwards a message based on the position of itself, its neighbors and the destination. The objective of energy aware routing algorithms is to minimize the total power for routing a message from source to destination or to maximize the total number of routing tasks that a node can perform before its battery power depletes. In this paper we propose new localized energy aware routing algorithms called OLEAR. The algorithms have very high packet delivery rate with low packet forwarding and battery power consumption. In addition, they ensure good energy distribution among the nodes. Finally, packets reach the destination using smaller number of hops. All these properties make our algorithm suitable for routing in any energy constrained environment. We compare the performance of our algorithms with other existing energy and non‐energy aware localized algorithms. Simulation experiments show that our algorithms present comparable energy consumption and distribution to other energy aware algorithms and better packet delivery rate. Copyright © 2006 John Wiley & Sons, Ltd.     

Flow rank based probabilistic fair scheduling for wireless ad hoc networks

Fair scheduling is an ideal candidate for fair bandwidth sharing and thereby achieving fairness among the contending flows in a network. It is particularly challenging for ad hoc networks due to infrastructure free operation and location dependent contentions. As there is no entity to serve coordination among nodes, we need a mechanism to overcome inherent unreliability of the network to provide reduced collision and thereby higher throughput and adequate fair allocation of the shared medium among different contending flows. This paper proposes a flow rank based probabilistic fair scheduling technique. The main focus is to reduce the collision probability among the contending flows while maintaining the prioritized medium access for those flows, which ensures a weighted medium access control mechanism based on probabilistic round robin scheduling. Each flow maintains a flow-table upon which the rank is calculated and backoff value is assigned according to the rank of the flow, i.e., lower backoff interval to lower ranked flow. However, flow-table instability due to joining of a new flow, partially backlogged flow, hidden terminal and partially overlapped region exhibits a challenging problem that needs to be mitigated for our mechanism to work properly. We take appropriate measures to make the flow-table stabilized under such scenarios. Results show that our mechanism achieves better throughput and fairness compared to IEEE 802.11 MAC and existing ones.     

Joint scheduling and power control supporting multicasting in wireless ad hoc networks

This paper addresses the problem of power control in a multihop wireless network supporting multicast traffic. We face the problem of forwarding packet traffic to multicast group members while meeting constraints on the signal-to-interference-plus-noise ratio (SINR) at the intended receivers. First, we present a distributed algorithm which, given the set of multicast senders and their corresponding receivers, provides an optimal solution when it exists, which minimizes the total transmit power. When no optimal solution can be found for the given set of multicast senders and receivers, we introduce a distributed, joint scheduling and power control algorithm which eliminates the weak connections and tries to maximize the number of successful multicast transmissions. The algorithm allows the other senders to solve the power control problem and minimize the total transmit power. We show that our distributed algorithm converges to the optimal solution when it exists, and performs close to centralized, heuristic algorithms that have been proposed to address the joint scheduling and power control problem.     

QoS-aware minimum energy multicast tree construction in wireless ad hoc networks

Energy conservation is a critical issue in wireless ad hoc networks since batteries are the only limited-life energy source to power the nodes. One major metric for energy conservation is to route a communication session along the routes which require the lowest total energy consumption. Most recent algorithms for the MEM (Minimum Energy Multicast) problem considered energy efficiency as the ultimate objective in order to increase longevity of such networks. However, the introduction of real-time applications has posed additional challenges. Transmission of video and imaging data requires both energy and QoS-aware routing in order to ensure efficient usage of the networks. In this paper, we only consider “bandwidth” as the QoS in TDMA-based wireless ad hoc networks that use omni-directional antennas and have limited energy resources. We present a constraint formulation model for the QoS-MEM (QoS-aware Minimum Energy Multicast) problem in terms of mixed integer linear programming (MILP), which can be used for an optimal solution of the QoS-MEM problem. Experiment results show that in a typical static ad hoc network with 20 nodes, the optimal solutions can always be solved in a timely manner.     

An efficient reliable broadcasting protocol for wireless mobile ad hoc networks

The mobile ad hoc network (MANET) has recently been recognized as an attractive network architecture for wireless communication. Reliable broadcast is an important operation in MANET (e.g., giving orders, searching routes, and notifying important signals). However, using a naive flooding to achieve reliable broadcasting may be very costly, causing a lot of contention, collision, and congestion, to which we refer as the broadcast storm problem. This paper proposes an efficient reliable broadcasting protocol by taking care of the potential broadcast storm problem that could occur in the medium-access level. Existing protocols are either unreliable, or reliable but based on a too costly approach. Our protocol differs from existing protocols by adopting a low-cost broadcast, which does not guarantee reliability, as a basic operation. The reliability is ensured by additional acknowledgement and handshaking. Simulation results do justify the efficiency of the proposed protocol.     

QoS routing in ad hoc wireless networks

The emergence of nomadic applications have generated much interest in wireless network infrastructures that support real-time communications. We propose a bandwidth routing protocol for quality-of-service (QoS) support in a multihop mobile network. The QoS routing feature is important for a mobile network to interconnect wired networks with QoS support (e.g., ATM, Internet, etc.). The QoS routing protocol can also work in a stand-alone multihop mobile network for real-time applications. This QoS routing protocol contains end-to-end bandwidth calculation and bandwidth allocation. Under such a routing protocol, the source (or the ATM gateway) is informed of the bandwidth and QoS available to any destination in the mobile network. This knowledge enables the establishment of QoS connections within the mobile network and the efficient support of real-time applications. In addition, it enables more efficient call admission control. In the case of ATM interconnection, the bandwidth information can be used to carry out intelligent handoff between ATM gateways and/or to extend the ATM virtual circuit (VC) service to the mobile network with possible renegotiation of QoS parameters at the gateway. We examine the system performance in various QoS traffic flows and mobility environments via simulation. Simulation results suggest distinct performance advantages of our protocol that calculates the bandwidth information. It is particularly useful in call admission control. Furthermore, “standby” routing enhances the performance in the mobile environment. Simulation experiments show this improvement     

Lifetime evaluation in energy‐efficient rectangular ad hoc wireless networks

Ad hoc wireless network nodes are typically battery‐powered, therefore energy limit is one of the critical constraints of ad hoc wireless networks' development. This paper evaluates the network lifetime of a rectangular network model that achieves energy efficiency by optimizing the node radio range based on the geographical adaptive fidelity (GAF) topology management protocol (Proceedings of ACMMobil'01, July 2001; 70–84). We derive the optimal transmission range of nodes and analyze both static and dynamic traffic scenarios in both equal‐grid and adjustable‐grid rectangular GAF models, where the results show that the adjustable‐grid model saves 78.1% energy in comparison with the minimum energy consumption of equal‐grid model. The impact of node density on both equal‐grid and adjustable‐grid models is investigated to achieve grid‐lifetime balance among all grids to optimize the entire network lifetime. The lifetime estimation results show that without node density control the adjustable‐grid model prolongs the entire network lifetime by a factor of 4.2 compared with the equal‐grid model. Furthermore, the adjustable‐grid model with node density control is able to prolong the entire network lifetime by a factor of 6 compared with the equal‐grid model. Copyright © 2010 John Wiley & Sons, Ltd.     

Routing security in wireless ad hoc networks

A mobile ad hoc network consists of a collection of wireless mobile nodes that are capable of communicating with each other without the use of a network infrastructure or any centralized administration. MANET is an emerging research area with practical applications. However, wireless MANET is particularly vulnerable due to its fundamental characteristics, such as open medium, dynamic topology, distributed cooperation, and constrained capability. Routing plays an important role in the security of the entire network. In general, routing security in wireless MANETs appears to be a problem that is not trivial to solve. In this article we study the routing security issues of MANETs, and analyze in detail one type of attack-the "black hole" problem-that can easily be employed against the MANETs. We also propose a solution for the black hole problem for ad hoc on-demand distance vector routing protocol.     

Intrusion detection in wireless ad hoc networks

Intrusion detection has, over the last few years, assumed paramount importance within the broad realm of network security, more so in the case of wireless ad hoc networks. These are networks that do not have an underlying infrastructure; the network topology is constantly changing. The inherently vulnerable characteristics of wireless ad hoc networks make them susceptible to attacks, and it may be too late before any counter action can take effect. Second, with so much advancement in hacking, if attackers try hard enough they will eventually succeed in infiltrating the system. This makes it important to constantly (or at least periodically) monitor what is taking place on a system and look for suspicious behavior. Intrusion detection systems (IDSs) do just that: monitor audit data, look for intrusions to the system, and initiate a proper response (e.g., email the systems administrator, start an automatic retaliation). As such, there is a need to complement traditional security mechanisms with efficient intrusion detection and response. In this article we present a survey on the work that has been done in the area of intrusion detection in mobile ad hoc networks.     

QoS issues in ad hoc wireless networks

Ad hoc wireless networks consist of mobile nodes interconnected by multihop communication paths. Unlike conventional wireless networks, ad hoc networks have no fixed network infrastructure or administrative support. The topology of the network changes dynamically as mobile nodes join or depart the network or radio links between nodes become unusable. This article addresses some of the quality of service issues for ad hoc networks which have started to receive increasing attention in the literature. The focus is on QoS routing. This is a complex and difficult issue because of the dynamic nature of the network topology and generally imprecise network state information. We present the basic concepts and discuss some of the results. The article concludes with some observations on the open areas for further investigation     

一种高效的无线自组网全网可靠广播协议

现有大部分的无线自组网广播协议采用最小虚拟骨干子网进行全网广播,能最小化广播的总发送次数。但是,由于未考虑无线链路的不可靠性,这些协议在实际网络中的广播效率并不高。为此,提出了一种高效的全网可靠广播协议（ENWRB）,该协议采用网络编码技术减少单跳广播的重传次数,并通过一种基于链路感知的虚拟骨干网选择算法产生更高效的广播骨干网。仿真结果表明,在确保所有节点成功接收广播消息的相同前提下,ENWRB协议的效率显著高于HCA(Hierarchical CDS-based Algorithm)协议。     

Power efficient routing trees for ad hoc wireless networks using directional antenna

In ad hoc wireless networks, nodes are typically powered by batteries. Therefore saving energy has become a very important objective, and different algorithms have been proposed to achieve power efficiency during the routing process. Directional antenna has been used to further decrease transmission energy as well as to reduce interference. In this paper, we discuss five algorithms for routing tree construction that take advantage of directional antenna, i.e., Reverse-Cone-Pairwise (RCP), Simple-Linear (SL), Linear-Insertion (LI), Linear-Insertion-Pairwise (LIP), and a traditional approximation algorithm for the travelling salesman problem (TSP). Their performances are compared through a simulation study.     

Capacity regions for wireless ad hoc networks

We define and study capacity regions for wireless ad hoc networks with an arbitrary number of nodes and topology. These regions describe the set of achievable rate combinations between all source-destination pairs in the network under various transmission strategies, such as variable-rate transmission, single-hop or multihop routing, power control, and successive interference cancellation (SIC). Multihop cellular networks and networks with energy constraints are studied as special cases. With slight modifications, the developed formulation can handle node mobility and time-varying flat-fading channels. Numerical results indicate that multihop routing, the ability for concurrent transmissions, and SIC significantly increase the capacity of ad hoc and multihop cellular networks. On the other hand, gains from power control are significant only when variable-rate transmission is not used. Also, time-varying flat-fading and node mobility actually improve the capacity. Finally, multihop routing greatly improves the performance of energy-constraint networks.