Search

In this paper, we consider a set of n mobile wireless nodes, which have no information about each other. The only information a single node holds is its current location and future mobility plan. We develop a two-phase distributed self-stabilizing scheme for producing a bounded hop-diameter communication graph. In the first phase, nodes construct a temporary underlying topology and disseminate their current location and mobility plans. This is followed by a second phase, in which nodes construct the desired topology under two modes: static and dynamic. The static mode provides a fixed topology which does not change in spite of node movements; the dynamic mode allows the topology to change; however, the hop-diameter remains the same. We provide an O(\lambda,\lambda^2)-bicriteria approximation (in terms of total energy consumption and network lifetime, respectively) algorithm in the static mode: for an input parameter \lambda, we construct a static h-bounded hop communication graph, where h=n/\lambda + \log \lambda. In the dynamic mode, given a parameter h, we construct an optimal (in terms of network lifetime) h-bounded hop communication graph when every node moves with constant speed in a single direction along a straight line during each time interval. Our results are validated through extensive simulations. [ABSTRACT FROM PUBLISHER]

Graph theory is a traditional mathematical method to analyze computer networks, including intelligent wireless networks, such as ad hoc networks, sensor networks, and wireless mesh networks. Because of the variety of the network nodes and wireless links, conventional graph theory and set theory used to describe the element of the network (node and link) are not suitable to model the modern complex wireless networks. Recent research in weighted graph and random graph theories that place a weight on the links and a probability to decide the existence of the link or not is a further step to model the wireless network in a near real-life scenario. However, it lacks the ability to describe the properties of the network node. In this paper, a new mathematical tool, polychromatic sets (PS-sets), is introduced in modeling the complex wireless networks. PS-sets have the ability to describe the property of each element, which we believe will be a perfect tool to describe the network nodes and links of wireless networks. This paper demonstrates a scalable network modeling using PS-sets theory and a routing scheme based on this model. Evaluation results show that it is simple and scalable, and its performance is superior to other conventional routing schemes. The PS-sets theory could become a new tool in studying modern complex wireless networks. [ABSTRACT FROM PUBLISHER]

In this paper, we consider non-orthogonal multiple access (NOMA) for wireless ad hoc networks over block fading channels where the performance is limited by interference and fading. In order to provide a reasonable performance, we can use re-transmission and interference cancellation techniques. Re-transmission techniques can provide a diversity gain over fading channels, while the successive interference cancellation (SIC) can improve the signal to interference ratio (SIR). Using the information outage probability, we show that the NOMA approach with re-transmissions can perform better than the orthogonal multiple access (OMA) approach with re-transmissions when the signal to noise ratio (SNR) is low. It is also shown that the outage probability of the NOMA with SIC is lower than that of OMA when the rate is sufficiently low where SIC can be facilitated. [ABSTRACT FROM AUTHOR]

We consider a large distributed MIMO system where wireless users with single transmit and receive antenna cooperate in clusters to form distributed transmit and receive antenna arrays. We characterize how the capacity of the distributed MIMO transmission scales with the number of cooperating users, the area of the clusters and the separation between them, in a line-of-sight propagation environment. We use this result to answer the following question: can distributed MIMO provide significant capacity gain over traditional multi-hop in large adhoc networks with n source-destination pairs randomly distributed over an area A? Two diametrically opposite answers and have emerged in the current literature. We show that neither of these two results are universal and their validity depends on the relation between the number of users n and \sqrtA/λ, which we identify as the spatial degrees of freedom in the network. λ is the carrier wavelength. When \sqrtA/λ≥ n, there are n degrees of freedom in the network and distributed MIMO with hierarchical cooperation can achieve a capacity scaling linearly in n as in , while capacity of multihop scales only as \sqrtn. On the other hand, when \sqrtA/λ≤ \sqrtn as in , there are only \sqrtn degrees of freedom in the network and they can be readily achieved by multihop. Our results also reveal a third regime where \sqrtn≤\sqrtA/λ≤ n. Here, the number of degrees of freedom are smaller than n but larger than what can be achieved by multi-hop. We construct scaling optimal architectures for this intermediate regime. [ABSTRACT FROM PUBLISHER]

Wireless ad hoc networks are in general characterized by dynamic topologies that do not have a fixed infrastructure. In addition, connectivity is maintained in a decentralized fashion through a form of multi-hop radio network. To this effect, wireless ad hoc networks with asymmetric link costs have been advocated as more realistic ones from a network modeling perspective. In this paper, we propose an Efficient Optimum Branching-based Distributed Broadcast Routing (EOBDBR) protocol for wireless ad hoc networks with asymmetric link costs, which makes use of local information exchange only. The proposed protocol contrasts with centralized routing protocols, in which link state and other relevant information are kept in the routing table of each node. It involves setting up link states, finding minimum in-edge, detecting cycles, re-weighting and breaking cycles. Through extensive simulations, our protocol is compared against four distributed broadcast routing protocols chosen as benchmarks. The performance metrics used are message overhead, total energy consumption, number of rebroadcasting nodes, network lifetime, and broadcast time. The superiority of EOBDBR against the studied benchmark protocols is established with respect to the above-mentioned metrics. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we present a packet-centric approach for distributed coding in decentralized wireless ad hoc networks, for applications in distributed data storage, data persistence and efficient data gathering. We study the setting where each of N network nodes generates an information packet and the goal is to efficiently encode information packets and disseminate produced encoded packets across the network in such fashion that gathering of any subset of slightly more than N encoded packets allows for retrieval of the original information. The process of distributed encoding is performed using packets that randomly walk over the network and sample information packets from network nodes, producing the encoded packets in a simple, elegant, fully decentralized and stateless way. The proposed scheme maintains properties of centralized codes in terms of performance parameters, offering at the same time advantage of robustness to node failures and changes in network topology. We specialize the proposed scheme for several important classes of low-complexity encodable/decodable sparse-graph codes – LDGM, LDPC (IRA), LT, and Raptor codes, evaluating its performance via simulation for various data-gathering scenarios. [Copyright &y& Elsevier]

In this paper, we study multicast capacity for cognitive networks. We consider the cognitive network model consisting of two overlapping ad hoc networks, called the primary ad hoc network (PaN) and secondary ad hoc network (SaN), respectively. PaN and SaN operate on the same space and spectrum. For PaN (or SaN, respectively), we assume that primary (or secondary, respectively) nodes are placed according to a Poisson point process of intensity n (or m, respectively) over a unit square region. We randomly choose n_s (or m_s, respectively) nodes as the sources of multicast sessions in PaN (or SaN, respectively), and for each primary source v^p (or secondary source v^s, respectively), we pick uniformly at random n_d primary nodes (or m_d secondary nodes, respectively) as the destinations of v^p (or v^s, respectively). Above all, we assume that PaN can adopt the optimal protocol in terms of the throughput. Our main work is to design the multicast strategy for SaN by which the optimal throughput can be achieved, without any negative impact on the throughput for PaN in order sense. Depending on n_d and n, we choose the optimal one for PaN from two strategies called percolation strategy and connectivity strategy, respectively. Subsequently, we design the corresponding throughput-optimal strategy for SaN. We derive the regimes in terms of n, n_d, m, and m_d in which the upper bounds on multicast capacities for PaN and SaN can be achieved simultaneously. Unicast and broadcast capacities for the cognitive network can be derived by our results as the special cases by letting n_d=1 (or m_d=1) and n_d=n-1 (or m_d=m-1), respectively, which enhances the generality of this work. [ABSTRACT FROM AUTHOR]

Distributed network protocols operate similar to periodic state machines, utilizing internal states and timers for network coordination, which creates opportunities for carefully engineered radio jamming to target the protocol operating periods and disrupt network communications. Such periodic attacks targeting specific protocol period/frequency of operation is referred to as Null Frequency Jamming (NFJ). Our hypothesis is that NFJ is a pervasive phenomenon in dynamic systems, including wireless ad-hoc networks. This paper aims to test the hypothesis by investigating NFJ targeted at the on-demand routing protocols for ad-hoc networks. Our mathematical analysis and simulation results show substantial degradation in end-to-end network throughput at certain null periods/frequencies, where the jamming periodicity self-synchronizes with the route-recovery cycle. We also study an effective countermeasure, randomized route-recovery periods, for eliminating the presence of predictable null frequencies and mitigating the impact of NFJ. Our analytical model and simulation results validate the effectiveness of randomized route recovery with appropriately chosen randomization ranges. [ABSTRACT FROM PUBLISHER]

Particle swarm optimization (PSO) is one of the most important biological swarm intelligence paradigms. However, the standard PSO algorithm can easily get trapped in the local optima when solving complex multimodal problems. In this paper, an improved adaptive particle swarm optimization (IAPSO) is presented. Based on IAPSO, a joint opportunistic power and rate allocation (JOPRA) algorithm is proposed to maximize the sum of source utilities while minimize power allocation for all links in wireless ad hoc networks. It is shown that the proposed JOPRA algorithm can converge fast to the optimum and reach larger total data rate and utility while less total power is consumed by comparison with the original APSO. This thanks to the dynamic change of the maximum movement velocity of the particles, the use of the modified replacement procedure in constraint handling, and the consideration of the state of the optimization run and the population diversity in stopping criteria. Numerical simulations further verify that our algorithm with the IAPSO outperforms that with the original APSO. [ABSTRACT FROM AUTHOR]

Cooperative techniques have been shown to significantly improve the performance of wireless networks. Despite being a mature technology in single communication link scenarios, their implementation in wider, and practical, networks poses several challenges which have not been fully identified and understood so far. In this paper, the implementation of cooperative communications in non-centralized ad hoc networks with sensing-based channel access is extensively discussed. Both analysis and simulation are employed to provide a clear understanding of the mutual influence between the link layer contention mechanism and relaying protocols. Results show that sensing-based channel access significantly hampers the effectiveness of cooperation by biasing the spatial distribution of available relays, and by inducing a level of spatial and temporal correlation of interference that diminishes the diversity improvement on which cooperative gains are founded. Moreover, the efficiency reduction entailed by several practical protocol issues related to carrier sense multiple access which are typically neglected in the literature is thoroughly investigated. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper, multiple description coding (MD coding or MDC) coupled with multipath transport is considered to provide robust video streaming in error-prone wireless ad hoc networks. Two problems are investigated for multi-description multipath (MDMP) video streaming in the unicast setting. The first one addresses multipath selection for balanced two-description coded video streaming. An interference-aware MDMP routing is formulated for single-radio networks by employing a time-division link scheduling method to eliminate interference, based on which an optimal path selection associated with the minimum reconstruction distortion of received video may be obtained with high complexity. A heuristic solution of low complexity is developed for the interference-aware multipath routing, by introducing a path metric taking into account intra-flow interference, inter-flow interference, link bandwidth and link “up” probability. The second problem touches on unbalanced-path based joint MD video coding and packet allocation for multiple paths of varying bandwidth and loss probabilities. An unbalanced-path based joint two-description video coding and description packet allocation utilizing redundant slices is proposed, which allocates slices in each description to two paths with varying bandwidth and optimally selects the amount of inserted redundancy according to different loss rates. Simulation results demonstrate the effectiveness of both the proposed MDMP routing scheme and the unbalanced-path based joint MD video coding and packet allocation approach in the wireless ad hoc networks. [Copyright &y& Elsevier]

In this paper, we propose a novel trust management scheme for improving routing reliability in wireless ad hoc networks. It is grounded on two classic autoregression models, namely Autoregressive (AR) model and Autoregressive with exogenous inputs (ARX) model. According to this scheme, a node periodically measures the packet forwarding ratio of its every neighbor as the trust observation about that neighbor. These measurements constitute a time series of data. The node has such a time series for each neighbor. By applying an autoregression model to these time series, it predicts the neighbors future packet forwarding ratios as their trust estimates, which in turn facilitate it to make intelligent routing decisions. With an AR model being applied, the node only uses its own observations for prediction; with an ARX model, it will also take into account recommendations from other neighbors. We evaluate the performance of the scheme when AR, ARX or a previously proposed Bayesian model is used. Simulation results indicate that the ARX model is the best choice in terms of accuracy. [ABSTRACT FROM AUTHOR]

We investigate the mean degree and the isolation probability of a network node sustaining intrasystem interference and intersystem interference from multiple coexisting wireless ad hoc networks. Under general fading of the desired signal and interfering signals, a closed-form upper bound on the mean node degree and a lower bound on the node isolation probability are obtained by thoroughly considering dominating interferers and second-order interferers. A closed-form lower bound on the mean node degree is further computed. The ratio between the upper bound and lower bound is bounded, and they are asymptotically tight as the path-loss exponent approaches infinity. Moreover, a nearly closed-form expression for the mean node degree is derived in terms of inverse Laplace transform of the fading distribution of the desired signal. Our derived local network quantities could find application in the approximate study of a number of metrics related to connectivity and delay of information propagation in wireless ad hoc networks. [ABSTRACT FROM PUBLISHER]

This paper first highlights common evaluation techniques used in wireless ad hoc networks. Specifically, it focuses on the discrete-event simulations. The paper further reviews methods that are used during the analysis of the generated results from discrete-event simulations. Steady-state detection, simulation time, and confidence intervals are considered. [ABSTRACT FROM AUTHOR]

In this paper, we characterize the information-theoretic capacity scaling of wireless ad hoc networks with n randomly distributed nodes. By using an exact channel model from Maxwell's equations, we successfully resolve the conflict in the literature between the linear capacity scaling by Özgür and the degrees of freedom limit given as the ratio of the network diameter and the wavelength \lambda by Franceschetti In dense networks where the network area is fixed, the capacity scaling is given as the minimum of n and the degrees of freedom limit \lambda^-1 to within an arbitrarily small exponent. In extended networks where the network area is linear in n, the capacity scaling is given as the minimum of n and the degrees of freedom limit \sqrtn\lambda^-1 to within an arbitrarily small exponent. Hence, we recover the linear capacity scaling by Özgür if \lambda=O(n^-1) in dense networks and if \lambda=O(n^-1/2) in extended networks. Otherwise, the capacity scaling is given as the degrees of freedom limit characterized by Franceschetti For achievability, a modified hierarchical cooperation is proposed based on a lower bound on the capacity of multiple-input multiple-output channel between two node clusters using our channel model. [ABSTRACT FROM AUTHOR]

A distributed adaptive opportunistic routing scheme for multihop wireless ad hoc networks is proposed. The proposed scheme utilizes a reinforcement learning framework to opportunistically route the packets even in the absence of reliable knowledge about channel statistics and network model. This scheme is shown to be optimal with respect to an expected average per-packet reward criterion. The proposed routing scheme jointly addresses the issues of learning and routing in an opportunistic context, where the network structure is characterized by the transmission success probabilities. In particular, this learning framework leads to a stochastic routing scheme that optimally “explores” and “exploits” the opportunities in the network. [ABSTRACT FROM PUBLISHER]

Abstract: Directional antennas offer many potential advantages for wireless networks such as increased network capacity, extended transmission range and reduced energy consumption. Exploiting these advantages requires new protocols and mechanisms at various communication layers to intelligently control the directional antenna system. With directional antennas, many trivial mechanisms, such as neighbor discovery, become challenging since communicating parties must agree on where and when to point their directional beams to communicate. In this paper, we propose a fully directional neighbor discovery protocol called Sectored-Antenna Neighbor Discovery (SAND) protocol. SAND is designed for sectored-antennas, a low-cost and simple realization of directional antennas, that utilize multiple limited beamwidth antennas. Unlike many proposed directional neighbor discovery protocols, SAND depends neither on omnidirectional antennas nor on time synchronization. SAND performs neighbor discovery in a serialized fashion allowing individual nodes to discover all potential neighbors within a predetermined time. SAND guarantees the discovery of the best sector combination at both ends of a link, resulting in more robust and higher quality links between nodes. Finally, SAND reliably gathers the neighborhood information in a centralized location, if needed, to be used by centralized networking protocols. The effectiveness of SAND has been assessed via simulation studies and real hardware implementation. [Copyright &y& Elsevier]

Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased algorithms, the relation between the independence number α and the connected domination number γ of a unit-disk graph plays the key role. The best-known relation between them is $\alpha\leq3\frac{2}{3}\gamma_{c}+1$. In this paper, we prove that α≤3.4306 γ+4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature. [ABSTRACT FROM AUTHOR]

Several analytical models of different wireless networking schemes such as wireless LANs and meshes have been reported in the literature. To the best of our knowledge, all these models fail to address the accurate end-to-end delay analysis of multi-hop wireless networks under unsaturated traffic condition considering the hidden and exposed terminal situation. In an effort to gain deep understanding of delay, this paper firstly proposes a new analytical model to predict accurate media access delay by obtaining its distribution function in a single wireless node. The interesting point of having the media access delay distribution is its generality that not only enables us to derive the average delay which has been reported in almost most of the previous studies as a special case but also facilitates obtaining higher moments of delay such as variance and skewness to capture the QoS parameters such as jitters in recently popular multimedia applications. Secondly, using the obtained single node media access delay distribution, we extend our modeling approach to investigate the delay in multi-hop networks. Moreover, probabilities of collisions in both hidden and exposed terminal conditions have been calculated. The validity of the model is demonstrated by comparing results predicted by the analytical model against those obtained through simulation experiments. [ABSTRACT FROM AUTHOR]

Reliability is an important issue for safety-critical broadcast services in vehicular ad hoc networks (VANETs). So far, most investigations of such broadcast networks focus on multihop connectivity, taking all one-hop links for granted. In this paper, four reliability metrics for one-hop broadcast communication in VANETs, including the packet reception rate (PRR), the packet delivery ratio (PDR), the node successful packet delivery probability (PDP), and the effective range (ER), are introduced and evaluated analytically and by simulations. Expressions of these reliability metrics for one-hop broadcast in IEEE-802.11-based 1-D VANETs are derived with consideration of the IEEE 802.11 distributed coordination function (DCF), the hidden terminal problem, and collisions caused by concurrent transmissions. The impacts of network parameters such as distinct transmission, carrier sensing, and interference ranges; the density of nodes in the networks; the distances of receivers to the senders; the message generation rates; the backoff window sizes; and the channel data rates on the reliability of the broadcast communication in VANETs are investigated and discussed. As an example, the proposed model is applied to the evaluation of the dedicated short-range communication (DSRC) safety-critical message propagation in a highway setting. As a result, some important observations to the design and analysis of such communication systems are provided. [ABSTRACT FROM PUBLISHER]

Wireless ad hoc networks have played an increasingly important role in a wide range of applications. A key challenge in such networks is to achieve maximum lifetime for battery-powered mobile devices with dynamic energy-efficient algorithms. Recent studies in battery technology have revealed that the behavior of battery discharging is more complex than we used to know. Battery-powered devices might waste a huge amount of energy if their battery discharging is not carefully scheduled and budgeted. In this paper, we introduce a novel energy model for batteries and study the effect of battery behavior on routing in wireless ad hoc networks. We first propose an online computable discrete-time mathematical model to capture battery discharging behavior. The model has low computational complexity and data storage requirement. It is therefore suitable for online battery capacity computation in routing. Our evaluations indicate that the model can accurately capture the behavior of battery discharging. Based on this battery model, we then propose a battery-aware routing (BAR) scheme for wireless ad hoc networks. BAR is a generic scheme that implements battery awareness in routing protocols and is independent of any specific routing protocol. By dynamically choosing the devices with well-recovered batteries as routers and leaving the “fatigue” batteries for recovery, the BAR scheme can effectively recover the device's battery capacity to achieve higher energy efficiency. Our simulation results demonstrate that, by adopting the BAR scheme, network lifetime and data throughput can be increased by up to 28% and 24%, respectively. The results also show that BAR achieves good performance in various networks composed of different devices, batteries, and node densities. Finally, we also propose an enhanced prioritized BAR (PBAR) scheme for time-sensitive applications in wireless ad hoc networks. Our simulation results illustrate that PBAR achieves good performance in terms of end-to-end delay and data throughput. [ABSTRACT FROM PUBLISHER]

Copyright of Journal of the Suzhou University (Engineering Science) / Suzhou Daxue Xuebao is the property of Soochow University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this paper, we present matrix game-theoretic models for joint routing, network coding, and scheduling problems. First, routing and network coding are modeled by using a new approach based on a compressed topology matrix that takes into account the inherent multicast gain of the network. Scheduling is optimized by a new approach called network graph soft coloring. Soft graph coloring is designed by switching between different components of a wireless network graph, which we refer to as graph fractals, with appropriate usage rates. The network components, which are represented by graph fractals, are a new paradigm in network graph partitioning that enables modeling of the network optimization problem by using the matrix game framework. In the proposed game, which is a nonlinear cubic game, the strategy sets of the players are links, paths, and network components. The outputs of this game model are mixed strategy vectors of the second and third players at equilibrium. The strategy vector of the second player specifies the optimum multipath routing and network coding solution, whereas the mixed strategy vector of the third player indicates the optimum switching rate among different network components or membership probabilities for an optimal soft-scheduling approach. Optimum throughput is the value of the proposed nonlinear cubic game at equilibrium. The proposed nonlinear cubic game is solved by extending a fictitious playing method. Numerical and simulation results prove the superior performance of the proposed techniques compared with the conventional schemes using hard graph coloring. [ABSTRACT FROM PUBLISHER]

Energy efficiency is crucial to the implementation of broadcast and multicast services in wireless ad hoc and sensor networks. This paper proposes a path-based power-efficient approach that minimizes energy consumption in the network by optimizing the transmission ranges of all nodes. Unlike existing link-based and node-based solutions, the proposed approach, which is applicable to both static and mobile wireless networks, constructs minimum-power broadcast trees. This study uses Lagrangian Relaxation (LR) to decompose the tree-construction problem, which is NP-complete, into multiple independently solvable sub-problems. The resulting Lagrange dual solution ensures a lower bound on the objective function value. The proposed approximation heuristic solves the primal problem by obtaining the upper bound of the objective value based on the information from the set of Lagrange multipliers. This study develops a decentralized, near-optimal algorithm to solve the problem. Simulation results show that in randomly generated networks, the proposed method outperforms the existing Minimum Shortest Path Tree (MSPT) algorithm, Prim's Minimum Spanning Tree (PMST) algorithm, and the Broadcast Incremental Power (BIP) algorithm by 30, 10, and 5%, respectively. [ABSTRACT FROM AUTHOR]

Recently, broadcast communications in mobile ad hoc networks (MANETs) have been deployed in many mission-critical applications. So far, most investigations of such broadcast networks focus on multi-hop connectivity taking all one-hop links for granted. In this paper, the reliability and performance of real-time one-hop broadcast services in IEEE 802.11 based MANETs are investigated analytically and by simulation. Having specified possible applications and the features of IEEE 802.11 broadcast communication in dynamically self-organized networks under harsh communication environment, analyses are conducted to derive closed form expressions of the reliability and performance indices for both one-dimensional (1-D) and two-dimensional (2-D) broadcast MANETs: packet reception rate ( PRR) and packet transmission delay. The proposed analytical models account for the impact of broadcast hidden terminal problem, message arrival interval, backoff counter process, space distributions of nodes, and fading transmission channel on the reliability and performance of the broadcast MANETs. As an example, the proposed models are applied to the evaluation of safety-related inter-vehicle communication on a highway. From the obtained numerical results under various offered traffic and network parameters, new observations and effective enhancement suggestions are given. [ABSTRACT FROM AUTHOR]

In this paper, we study the issues of medium access control (MAC) for multihop wireless networks with directional antennas. Existing solutions to directional antenna MAC problems rarely account for the impact of minor lobes and typically assume that the neighboring nodes' locations are known a priori. As a result, they are not applicable to practical systems or mobile nodes. In this paper, we propose a reservation-based directional medium access control (RDMAC) protocol for multihop wireless networks based on the IEEE 802.11 distributed coordination function. The design objective of RDMAC is to increase the network throughput by reducing interference among neighboring nodes. We then develop an analytical model for RDMAC to investigate the throughput performance of RDMAC under arbitrary node density. The analytical model provides insights into RDMAC parameter settings. We also evaluate the performance of the proposed RDMAC through ns-2 simulations. The results validate the accuracy of our analytical model and show that our mechanism outperforms existing solutions, in terms of higher throughput. [ABSTRACT FROM PUBLISHER]

Abstract: Wireless ad hoc networks support rapid on-demand and adaptive communication among the nodes due to their self-configurable and autonomous nature and lack of fixed infrastructure. Security is a crucial factor for such systems. Since ad hoc networks rely on the collaboration principle, the issue of key distribution and efficient group key management in such networks represents two of the most important problems. We describe hybrid solutions to the problem of key distribution and key management by reflecting ad hoc networks in a topology composed of a set of clusters. To date no security proofs exist for these types of protocols. We present two dynamically efficient schemes. We show that both our hybrid schemes are provably secure in the standard model under Decision Diffie–Hellman (DDH) assumption. The proposed protocols avoid the use of a trusted third party (TTP) or a central authority, eliminating a single point of attack. We analyse the complexity of the schemes and differentiate between the two approaches based on performance in a wireless setting. In comparison with the existing cluster-based hybrid key agreement protocols, our proposed approaches individually provide better performance in terms of both communication and computation, handle dynamic events efficiently, and are supported by sound security analysis in formal security models under standard cryptographic assumptions. [Copyright &y& Elsevier]

This paper presents an analytical approach to model the bi-directional multi-channel IEEE 802.11 MAC protocols (Bi-MCMAC) for ad hoc networks. Extensive simulation work has been done for the performance evaluation of IEEE 802.11 MAC protocols. Since simulation has several limitations, this work is primarily based on the analytical approach. The objective of this paper is to show analytically the performance advantages of Bi-MCMAC protocol over the classical IEEE 802.11 MAC protocol. The distributed coordination function (DCF) mode of medium access control (MAC) is considered in the modeling. Two different channel scheduling strategies, namely, random channel selection and fastest channel first selection strategy are also presented in the presence of multiple channels with different transmission rates. M/G/1 queue is used to model the protocols, and stochastic reward nets (SRNs) are employed as a modeling technique as it readily captures the synchronization between events in the DCF mode of access. The average system throughput, mean delay, and server utilization of each MAC protocol are evaluated using the SRN formalism. We also validate our analytical model by comparison with simulation results. The results obtained through the analytical modeling approach illustrate the performance advantages of Bi-MCMAC protocols with the fastest channel first scheduling strategy over the classical IEEE 802.11 protocol for TCP traffic in wireless ad hoc networks. Copyright © 2010 John Wiley & Sons, Ltd. This paper presents an analytical approach to model the bi-directional multi-channel IEEE 802.11 MAC (Bi-MCMAC) protocols for ad hoc networks via stochastic reward nets. The objective is to show the performance advantages of Bi-MCMAC protocol over the classical IEEE 802.11 MAC protocol. Two different channel scheduling strategies are also presented in the presence of multiple channels with different transmission rates. The average system throughput, mean delay, and server utilization of each MAC protocol are evaluated using the SRN formalism. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Social system networks with high data rates and limited storage will discard data if the system cannot connect and upload the data to a central server. We address the challenge of limited storage capacity in mobile health systems during network partitions with a heuristic that achieves efficiency in storage capacity by modifying the granularity of the medical data during long intercontact periods. Patterns in the connectivity, reception rate, distance, and location are extracted from the social system network and leveraged in the global algorithm and online heuristic. In the global algorithm, the stochastic nature of the data is modeled with maximum likelihood estimation based on the distribution of the reception rates. In the online heuristic, the correlation between system position and the reception rate is combined with patterns in human mobility to estimate the intracontact and intercontact time. The online heuristic performs well with a low data loss of 2.1%–6.1%. [ABSTRACT FROM AUTHOR]

Abstract: We consider a distributed joint random access and power control scheme for interference management in wireless ad hoc networks. To derive decentralized solutions that do not require any cooperation among the users, we formulate this problem as noncooperative joint random access and power control game, in which each user minimizes its average transmission cost with a given rate constraint. Using supermodular game theory, the existence and uniqueness of Nash equilibrium are established. Furthermore, we present an asynchronous distributed algorithm to compute the solution of the game based on myopic best response updates, which converges to Nash equilibrium globally. Finally, a link admission algorithm is carried out to guarantee the reliability of the active users. Performance evaluations via simulations show that the game-theoretical based cross-layer design achieves high performance in terms of energy consumption and network stability. [ABSTRACT FROM AUTHOR]

Abstract: Upper bounds on the service carrying capacity of a multi-hop, wireless, SSMA-based ad hoc network are considered herein. The network has a single radio band for transmission and reception. Each node can transmit to, or receive from, multiple nodes simultaneously. We formulate the scheduling of transmissions and control of transmit powers as a joint, mixed-integer, nonlinear optimization problem that yields maximum return at minimum power subject to SINR constraints. We present an efficient tabu search-based heuristic algorithm to solve the optimization problem and rigorously assess the quality of the results. Through analysis and simulation, we establish upper bounds on the VoIP call carrying capacity of the network as function of various parameters. We discuss the pros and cons of using SSMA as a spectrum sharing technique in wireless ad hoc networks. [ABSTRACT FROM AUTHOR]

In wireless ad hoc networks cooperation among nodes cannot always be assumed since nodes with limited resources and different owners are capable of making independent decisions. Cooperation problems in topology control and packet forwarding tasks have been mostly studied separately but these two tasks are not independent. Considering a joint cooperation problem by taking into account dependencies between tasks will result in more reliable and efficient networks. In this paper topology control definition is extended to cover cooperation problem in both packet forwarding and topology control in a single problem. In this definition nodes have to adjust their transmission power and decide on their relay role. This paper models the interactions of nodes as a potential game with two-dimensional utility function. The presented model, named TCFORCE (Topology Control packet FORwarding Cooperation Enforcement), preserves the network connectivity and reduces the energy consumption by providing cooperative paths between all pairs of nodes in the network. [ABSTRACT FROM AUTHOR]

Abstract: Given a wireless ad hoc network with a specified source node that has to broadcast messages to all other nodes in the network, the minimum energy broadcast (MEB) problem seeks a broadcast scheme for this network with minimum energy consumption. The MEB problem is NP-Hard. This paper describes a hybrid approach to the MEB problem combining a genetic algorithm with a local search heuristic. We have compared our hybrid approach against the best heuristic approaches known for this problem. Our approach outperformed all these approaches and emerged as the best. [Copyright &y& Elsevier]

In grid routing, the plane is tessellated into equal-sized square cells. Two cells are called neighbor cells if they share a common edge, and two nodes are called routing neighbors if they are in neighbor cells and within each other's transmission range. If communication parties are in the same cell, packets can be transmitted directly; otherwise, packets are forwarded to routing neighbors that are in cells closer to destination cells. As a greedy strategy, grid routing suffers the existence of local minima at which no neighbor nodes exist for relaying packets. To guarantee deliverability, in this paper, we investigate two vital parameters of grid routing, called the grid size and the transmission radius. Assume that nodes are represented by a Poisson point process with rate n over a unit-area square, and let l denote the grid size and r the transmission radius. First, we show that if for some constant β and r = √5l, then β = 1 is the threshold for deliverability. In other words, there almost surely do not exist local minima if β > 1 and there almost surely exist local minima if β < 1. Next, for any given β > 1, we give sufficient and necessary conditions to determine the critical transmission radius (CTR) for deliverability. Then, we show that as β ≅ 1.092, the CTR is the minimum over all β > 1. Simulation results are given to validate this theoretical work. [ABSTRACT FROM AUTHOR]

We consider the problem of two wireless networks operating on the same (presumably unlicensed) frequency band. Pairs within a given network cooperate to schedule transmissions, but between networks there is competition for spectrum. To make the problem tractable, we assume transmissions are scheduled according to a random access protocol where each network chooses an access probability for its users. A game between the two networks is defined. We characterize the Nash Equilibrium behavior of the system. Three regimes are identified: one in which both networks simultaneously schedule all transmissions, one in which the denser network schedules all transmissions and the sparser only schedules a fraction, and one in which both networks schedule only a fraction of their transmissions. The regime of operation depends on the path loss exponent \alpha , the latter regime being desirable but attainable only for \alpha > 4. This suggests that in certain environments, rival wireless networks may end up naturally cooperating. To substantiate our analytical results, we simulate a system where networks iteratively optimize their access probabilities in a greedy manner. We also discuss a distributed scheduling protocol that employs carrier sensing and demonstrate via simulations that again a near cooperative equilibrium exists for sufficiently large \alpha . [ABSTRACT FROM PUBLISHER]

Quorums are a basic construct in solving many fundamental distributed computing problems. One of the known ways of making quorums scalable and efficient is by weakening their intersection guarantee to being probabilistic. This article explores several access strategies for implementing probabilistic quorums in ad hoc networks. In particular, we present the first detailed study of asymmetric probabilistic biquorum systems, that allow to mix different access strategies and different quorums sizes, while guaranteeing the desired intersection probability. We show the advantages of asymmetric probabilistic biquorum systems in ad hoc networks. Such an asymmetric construction is also useful for other types of networks with nonuniform access costs (e.g, peer-to-peer networks). The article includes a formal analysis of these approaches backed up by an extensive simulation-based study. The study explores the impact of various parameters such as network size, network density, mobility speed, and churn. In particular, we show that one of the strategies that uses random walks exhibits the smallest communication overhead, thus being very attractive for ad hoc networks. [ABSTRACT FROM AUTHOR]

We study the multicast capacity of large-scale random extended multihop wireless networks, where a number of wireless nodes are randomly located in a square region with side length a = √n, by use of Poisson distribution with density 1. All nodes transmit at a constant power P, and the power decays with attenuation exponent α > 2. The data rate of a transmission is determined by the SINR as B log(1 + SINR), where B is the bandwidth. There are ns randomly and independently chosen multicast sessions. Each multicast session has k randomly chosen terminals. We show that when k ≤ θ1n/(log n)2α+6 and ns ≥ θ2n½+β, the capacity that each multicast session can achieve, with high probability, is at least c8 √n/ns√k, where θ1, θ2, and c8 are some special constants and β > O is any positive real number. We also show that for k = O(n/log²n), the per-flow multicast capacity under Gaussian channel is at most O(√n/ns√k) when we have at least n2 = Ω(log n) random multicast flows. Our result generalizes the unicast capacity for random networks using percolation theory. [ABSTRACT FROM AUTHOR]

As mobile applications become more widespread, programming paradigms and middleware architectures designed to support their development are becoming increasingly important. The event-based programming paradigm is a strong candidate for the development of mobile applications due to its inherent support for the loose coupling between components required by mobile applications. However, existing middleware that supports the event-based programming paradigm is not well suited to supporting location-aware mobile applications in which highly mobile components come together dynamically to collaborate at some location. This paper presents a number of techniques including location-independent announcement and subscription coupled with location-dependent filtering and event delivery that can be used by event-based middleware to support such collaboration. We describe how these techniques have been implemented in STEAM, an event-based middleware with a fully decentralized architecture, which is particularly well suited to deployment in ad hoc network environments. The cost of such location-based event dissemination and the benefits of distributed event filtering are evaluated. [ABSTRACT FROM AUTHOR]

The advanced technique of multiple beam antennas is recently considered in wireless networks to improve the system throughput by increasing spatial reuse, reducing collisions, and avoiding co-channel interference. The usage of multiple beam antennas is similar to the concept of Space Division Multiple Access (SDMA), while each beam can be treated as a data channel. Wireless networks can increase the total throughput and decrease the transmission latency if the physical layer of a mobile node can support multirate capability. Multirate wireless networks incurs the anomaly problem, because low data rate hosts may influence the original performance of high data rate hosts. In this work, each node fits out multiple beam antennas with multirate capability, and a node can either simultaneously transmit or receive multiple data on multiple beams. Observe that the transmitting or receiving operation does not happen at the same time. In this paper, we propose a multiple relay-based medium access control (MAC) protocol to improve the throughput for low data rate hosts. Our MAC protocol exploits multiple relay nodes and helps the source and the destination to create more than one data channel to significantly reduce the transmission latency. Observe that low data rate links with long-distance transmission latencies are distributed by multiple relay nodes, hence the anomaly problem can be significantly alleviated. In addition, the ACK synchronization problem is solved to avoid the condition that source nodes do not receive ACKs from destination nodes. An adjustment operation is presented to reduce unnecessary relay nodes during the fragment burst period. Finally, simulation results illustrate that our multiple relay-based MAC protocol can achieve high throughput and low transmission latency. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Abstract: In Ad Hoc networks, the performance is significantly degraded as the size of the network grows. The network clustering by which the nodes are hierarchically organized on the basis of the proximity relieves this performance degradation. Finding the weakly connected dominating set (WCDS) is a promising approach for clustering the wireless Ad Hoc networks. Finding the minimum WCDS in the unit disk graph is an NP-Hard problem, and a host of approximation algorithms has been proposed. In this article, we first proposed a centralized approximation algorithm called DLA-CC based on distributed learning automata (DLA) for finding a near optimal solution to the minimum WCDS problem. Then, we propose a DLA-based clustering algorithm called DLA-DC for clustering the wireless Ad Hoc networks. The proposed cluster formation algorithm is a distributed implementation of DLA-CC, in which the dominator nodes and their closed neighbors assume the role of the cluster-heads and cluster members, respectively. In this article, we compute the worst case running time and message complexity of the clustering algorithm for finding a near optimal cluster-head set. We argue that by a proper choice of the learning rate of the clustering algorithm, a trade-off between the running time and message complexity of algorithm with the cluster-head set size (clustering optimality) can be made. The simulation results show the superiority of the proposed algorithms over the existing methods. [Copyright &y& Elsevier]

The task of estimating path available bandwidth is difficult but paramount for QoS routing in supporting bandwidth-demanding traffic in multirate and multihop wireless ad hoc networks. The multirate capability and the impact of background traffic has not been carefully studied for the problem of estimating path available bandwidth in prior works. In this paper, we develop a theoretical model for estimating the available bandwidth of a path by considering interference from both background traffic and traffic along the path. We show that the clique constraint widely used to construct upper bounds does not hold any more when links are allowed to use different rates at different time. In our proposed model, traditional clique is coupled with rate vector to more properly characterize the conflicting relationships among links in wireless ad hoc networks where time-varying link adaption is used. Based on this model, we also investigate the problem of joint optimization of QoS routing and link scheduling. Several routing metrics and a heuristic algorithm are proposed. The newly proposed conservative clique constraint performs the best among the studied metrics in estimating available bandwidth of flows with background traffic. [ABSTRACT FROM AUTHOR]

In wireless ad hoc networks, routing needs cooperation of nodes. Since nodes often belong to different users, it is highly important to provide incentives for them to cooperate. However, most existing studies of the incentive-compatible routing problem focus on individual nodes' incentives, assuming that no subset of them would collude. Clearly, this assumption is not always valid. In this paper, we present a systematic study of collusion-resistant routing in noncooperative wireless ad hoc networks. In particular, we consider two standard solution concepts for collusion resistance in game theory, namely Group Strategyproofness and Strong Nash Equilibrium. We show that achieving Group Strategyproofness is impossible, while achieving Strong Nash Equilibrium is possible. More specifically, we design a scheme that is guaranteed to converge to a Strong Nash Equilibrium and prove that the total payment needed is bounded. In addition, we propose a cryptographic method that prevents profit transfer among colluding nodes, as long as they do not fully trust each other unconditionally. This method makes our scheme widely applicable in practice. Experiments show that our solution is collusion-resistant and has good performance. [ABSTRACT FROM AUTHOR]

Using directional antennas to conserve bandwidth and energy consumption in ad hoc wireless networks has attracted much attention from the research community in recent years. However, very little research has focused on applying directional antennas to broadcasting. In this paper, we propose a virtual link reduction (VLR)-based broadcasting protocol for ad hoc wireless networks using directional antennas. Based on two-hop neighborhood information, VLR relies on no location nor angle-of-arrival (AOA) information. VLR is a localized or distributed protocol, and it achieves full delivery. VLR operates on top of any existing broadcast routing protocols. In VLR, no node rebroadcasts a given packet more than once. No physical link is actually reduced, but if a packet has already been forwarded to the end node of the current link, the packet is no longer forwarded, that is, this link is virtually reduced. To evaluate the performance of the proposed VLR-based protocol, we conduct extensive simulation, for simplicity, assuming that there is no packet collision, no channel contention, and no mobility. Simulation results show that VLR outperforms most existing omnidirectional and directional broadcasting schemes in the sense that its normalized transmission cost and redundancy are significantly reduced. Based on the results, we conclude that VLR is more bandwidth and energy efficient. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we investigate the low coverage problem of efficient broadcast protocols in wireless ad hoc networks with realistic physical layer models. To minimize energy consumption, efficient protocols aim to select small set of forward nodes and minimum transmission radii. In ideal physical layer model, nodes within forward nodes’ transmission ranges can definitely receive packets; therefore energy efficient protocols can guarantee full coverage for broadcasting. However, in networks with a realistic physical layer, nodes can only receive packets with probability. We present an analytical model to show that the transmission radii used for nodes can be used to establish a tradeoff between minimizing energy consumption and ensuring network coverage. We then propose a mechanism called redundant radius, which involves using two transmission radii, to form a buffer zone that guarantees the availability of logical links in the physical network, one for broadcast tree calculation and the other for actual data transmission. With this mechanism, we extend well-known centralized protocols, BIP and DBIP, and corresponding localized protocols, LBIP and LDBIP. The effectiveness of the proposed scheme in improving network coverage is validated analytically and by simulation. [Copyright &y& Elsevier]

The open literature contains numerous studies of capacity bounds for an N-node wireless ad-hoc network but the number of cooperating nodes has generally been limited to two. In this paper, we present a simple time-share lower bound for such a network, but with two or more cooperating nodes. These results are then compared against our previous information theoretic upper bounds with hop-by-hop routing, frequency reuse, and no cooperation. While simulations show that our simple time-share lower bound with cooperation does not outperform our previous upper bound without cooperation, we do note a significant increase in achievable capacity relative to time-share results without cooperation. Also, our results indicate that there is no significant improvement when more than two nodes cooperate. [ABSTRACT FROM AUTHOR]

In this paper, we consider the issue of efficient broadcasting in mobile ad hoc networks (MANET5) using network coding and directional antennas. Network coding-based broadcasting focuses on reducing the number of transmissions each forwarding node performs in the multiple source/multiple message broadcast application, where each forwarding node combines some of the received messages for transmission. With the help of network coding, the total number of transmissions can be reduced compared to broadcasting using the same forwarding nodes without coding. We exploit the usage of directional antennas to network coding-based broadcasting to further reduce energy consumption. A node equipped with directional antennas can divide the omnidirectional transmission range into several sectors and turn some of them on for transmission. In the proposed scheme using a directional antenna, forwarding nodes selected locally only need to transmit broadcast messages, original or coded, to restricted sectors. We also study two extensions. The first extension applies network coding to both dynamic and static forwarding node selection approaches. In the second extension, we design two approaches for the single source/single message issue in the network coding-based broadcast application. Performance analysis via simulations on the proposed algorithms using a custom simulator and ns2 is presented. [ABSTRACT FROM AUTHOR]

With the growing abundance of portable wireless communication devices, a challenging question that arises is whether one can efficiently harness the collective communication and computation power of these devices. In this paper, we investigate this question by studying a streaming application. Consider a network of N wireless nodes, each of power P, in which one or more nodes are interested in receiving a data stream from a fixed server node S. We ask whether distributed communication mechanisms exist to route media packets from S to the arbitrary but fixed receiver, such that 1) the average communication delay L is short, 2) the load is balanced, i.e., all nodes in the ensemble spend roughly the same amount of average power, and, more importantly, 3) power resources of all nodes are optimally shared, i.e., the lifetime of the network is comparable to an optimally designed network with L nodes whose total power is N × P. We develop a theoretical framework for incorporation of random long range routes into wireless ad hoc networking protocols that can achieve such performance. Surprisingly, we show that wireless ad hoc routing algorithms, based on this framework, exist that can deliver this performance. The proposed solution is a randomized network structuring and packet routing framework whose communication latency is only L = O(log² Al) hops, on average, compared to O(√N) in nearest neighbor communications while distributing the power requirement almost equally over all nodes. Interestingly, all network formation and routing algorithms are completely decentralized, and the packets arriving at a node are routed randomly and independently, based only on the source and destination locations. The distributed nature of the algorithm allows it to be implemented within standard wireless ad hoc communication protocols and makes the proposed framework a compelling candidate for harnessing collective network resources in a truly large-scale wireless ad hoc networking environment. [ABSTRACT FROM AUTHOR]

Secure Routing is a fundamental networking function in every communication system, and multi-hop wireless networks are no exceptions. Attacking the routing service, achallenger can easily paralyses the operation of an entire network. The problem of traditional routing schemes relies on the possibility that the network is connected, that is, there is an end-to-end path between any source and any destination. Over the past, Secure Routing in Multi-hop Wireless Ad-hoc Networks techniques have been illustrated in this research. Itaims to present a surveyon secure routing protocol techniques in physical layer security, Secure routing with the default decode and forward strategy and cost of physical layer security in decentralized wireless networks. The researchwork also discuss about the relaying strategies in wireless ad hoc networks, secure connection path between the source and destination through the intermediate relay nodes and also about how the intermediate relay selection is been made and what algorithm and protocols are been implemented in order to achieve secure connection path. The secure connection path is said to be secured or unsecured only after analyzing about both the colluding eavesdroppers and non-colluding eavesdroppers. Hence, the research work also discuss about both type of eavesdroppers. The research presents a survey of the most significant opportunistic routing protocols for multi-hop wireless networks. [ABSTRACT FROM AUTHOR]