On the fundamental performance limits of peer-to-peer data replication in wireless ad hoc networks

Wireless ad hoc networks are drawing increasing attention from the research community because of their potential applications. However, the fundamental capacity limits of these networks pose various technological challenges to designers of network protocols. In this paper, we attempt to capture the inherent constraints on information dissemination in a mobile wireless environment, with the emphasis on peer-to-peer (P2P) communications. More specifically, we introduce the notion of "replication-induced gain" to quantify the impact of data replication under the paradigm of P2P query-response mechanisms. Our major contribution lies in presenting several preliminary results with respect to the complexities and trade-offs involved in enhancing data availability. To the best of our knowledge, the data replication problems that arise because of scarce system resources in wireless ad hoc networks have not been investigated from this perspective. We believe that our results could provide additional insights and practical implications for P2P system designers     

Smart antenna based broadcasting in wireless ad hoc networks

Smart antennas have the advantage over traditional omnidirectional antennas of being able to orientate radio signals into the concerned directions in either transmission mode or in reception mode. Since the omnidirectional antenna use in broadcasting over the whole network is the source of an excessive redundancy of broadcast packet receptions within each node, we suggest using smart antennas to improve the medium usage in the case of broadcasting. We propose to adapt a current broadcast protocol to smart antenna applications and present two smart antenna broadcast approaches. We also present a comparative performance study between omnidirectional and smart antennas when broadcasting. We show that we can improve battery power utilisation and bandwidth usage with smart antennas.     

Minimum energy mobile wireless networks

We describe a distributed position-based network protocol optimized for minimum energy consumption in mobile wireless networks that support peer-to-peer communications. Given any number of randomly deployed nodes over an area, we illustrate that a simple local optimization scheme executed at each node guarantees strong connectivity of the entire network and attains the global minimum energy solution for stationary networks. Due to its localized nature, this protocol proves to be self-reconfiguring and stays close to the minimum energy solution when applied to mobile networks. Simulation results are used to verify the performance of the protocol     

On broadcasting with cooperative diversity in multi-hop wireless networks

Cooperative diversity facilitates spatio-temporal communications without requiring the deployment of physical antenna arrays. While physical layer studies on cooperative diversity have been extensive, higher layer protocols which translate the achievable reduction in the SNR per bit for a given target BER, into system wide performance enhancements are yet to mature. The challenge is that appropriate higher layer functions are needed in order to enable cooperative diversity at the physical layer. We focus on network-wide broadcasting with the use of cooperative diversity in ad hoc networks. We design a novel distributed network-wide broadcasting protocol that takes into account the physical layer dependencies that arise with cooperative diversity. We perform extensive simulations that show that our protocol can outperform the best of the noncooperative broadcasting protocols by: (a) achieving up to a threefold increase in network coverage and, (b) by decreasing the latency incurred during the broadcast by about 50%. We also construct an analytical model that captures the behavior of our protocol. Furthermore, we show that computing the optimal solution to the cooperative broadcast problem is NP-complete and construct centralized approximation algorithms. Specifically, we construct an O(N ^epsi)-approximation algorithm with a computational complexity of O(N4/epsi); we also construct a simpler greedy algorithm.. The costs incurred with these algorithms serve as benchmarks with which one can compare that achieved by any distributed protocol     

Performance analysis of broadcasting schemes in mobile ad hoc networks

Numerous broadcasting schemes have been proposed to alleviate the broadcast storm problem in high-density ad hoc networks. Little work has been done to model and analyze these schemes. We consider the popular counter-based and distance-based schemes in a unit-disk network model. Through the rigorous theoretic analysis, we achieve statistic results that reveal the relations between network parameters and the performance of these schemes. We also expect these results to be further useful to the development of mathematical models for other ad hoc broadcasting schemes.     

Tracking mobile users in wireless communications networks

Tracking strategies for mobile wireless networks are studied. A cellular architecture in which base stations that are interconnected by a wired network communicate with mobile units via wireless links is assumed. The cost of utilizing the wireless links for the actual tracking of mobile users is considered. A tracking strategy in which a subset of all base stations is selected and designed as reporting centers is proposed. Mobile users transmit update messages only upon entering cells of reporting centers, while every search for a mobile user is restricted to the vicinity of the reporting center to which the user last reported. It is shown that, for an arbitrary topology of the cellular network (represented by the mobility graph), finding an optimal set of reporting centers is an NP-complete problem. Optimal and near-optimal solutions for important special cases of the mobility graph are presented     

无线传感器网络中移动节点接入的实现

当无线传感器网络引入移动节点时,将会大大拓宽网络的功能。窃听登记EAR算法是基于MAC层的,即实现移动节点从进入网络到维持网络连接,最后离开网络这一过程。本文基于EAR算法,在实现该算法的基础上就EAR存在的不足做出改进,通过仿真验证改进后的方案在减少网络能量损耗的同时可以提高移动节点与网络的连接质量。     

Approximation algorithms for broadcasting in duty cycled wireless sensor networks

Broadcast is a fundamental operation in wireless sensor networks (WSNs). Given a source node with a packet to broadcast, the aim is to propagate the packet to all nodes in a collision free manner whilst incurring minimum latency. This problem, called minimum latency broadcast scheduling (MLBS), has been studied extensively in wireless ad-hoc networks whereby nodes remain on all the time, and has been shown to be NP-hard. However, only a few studies have addressed this problem in the context of duty-cycled WSNs. In these WSNs, nodes do not wake-up simultaneously, and hence, not all neighbors of a transmitting node will receive a broadcast packet at the same time. Unfortunately, the problem remains NP-hard and multiple transmissions may be necessary due to different wake-up times. Henceforth, this paper considers MLBS in duty cycled WSNs and presents two approximation algorithms, BS-1 and BS-2, that produce a maximum latency of at most \((\Delta -1) TH\) and \(13TH\) respectively. Here, \(\Delta\) is the maximum degree of nodes, \(T\) denotes the number of time slots in a scheduling period, and \(H\) is the broadcast latency lower bound obtained from the shortest path algorithm. We evaluated our algorithms under different network configurations and confirmed that the latencies achieved by our algorithms are much lower than existing schemes. In particular, compared to OTAB, the best broadcast scheduling algorithm to date, the broadcast latency and transmission times achieved by BS-1 is at least \(\frac{1}{17}\) and \(\frac{2}{5}\) that of OTAB respectively.     

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.     

Efficient broadcasting with guaranteed coverage in mobile ad hoc networks

We study an efficient broadcast scheme in mobile ad hoc networks (MANETs). The objective is to determine a small set of forward nodes to ensure full coverage. We first study several methods that guarantee coverage when the local view of each node on its neighborhood information is updated in a timely manner. Then we consider a general case where nodes move even during the broadcast process, making it impractical to maintain up-to-date and consistent local views. A formal framework is used to model inaccurate local views in MANETs, where full coverage is guaranteed if three sufficient conditions, connectivity, link availability, and consistency, are met. Three solutions are proposed to satisfy those conditions. First, we give a minimal transmission range that maintains the connectivity of the virtual network constructed from local views. Then, we use two transmission ranges, one for neighborhood information collection and the other for actual data transmission, to form a buffer zone that guarantees the availability of logical links in the physical network. Finally, we propose a mechanism called aggregated local view to ensure consistent local views. By these, we extend Wu and Dai's coverage condition for broadcasting in a network with mobile nodes. The effectiveness of the proposed scheme is confirmed via both performance analysis and simulation study.     

Adaptive clustering for mobile wireless networks

This paper describes a self-organizing, multihop, mobile radio network which relies on a code-division access scheme for multimedia support. In the proposed network architecture, nodes are organized into nonoverlapping clusters. The clusters are independently controlled, and are dynamically reconfigured as the nodes move. This network architecture has three main advantages. First, it provides spatial reuse of the bandwidth due to node clustering. Second, bandwidth can be shared or reserved in a controlled fashion in each cluster. Finally, the cluster algorithm is robust in the face of topological changes caused by node motion, node failure, and node insertion/removal. Simulation shows that this architecture provides an efficient, stable infrastructure for the integration of different types of traffic in a dynamic radio network     

Analysis of link lifetime in wireless mobile networks

Link lifetime (LL) analysis is crucially important in designing and evaluating wireless mobile network protocols. Although a considerable amount of research has been conducted on this issue, the current paper studies several aspects of link lifetime for the first time, e.g. a closed form expression for the probability distribution of the residual link lifetime (RLL) for the constant velocity mobility model is obtained, which facilitates marginal studies on the behavior of link lifetime. As a case, using a tail analysis of LL and RLL distributions, we analytically prove that they are heavy-tailed. Using this outcome, a self-similar behavior in the traffic pattern of a sample delay tolerant network is justified analytically. To extend the model, the effect of stationary nodes, the effect of buffer zone, and the effect of link establishment policies between different node categories on the link lifetime are investigated. Extensive simulation experiments are performed to validate the obtained analytical results and derivations precisely. Moreover, simulation results confirm that the analytic results can also be used for two well known mobility models (random waypoint and random direction) with a negligible error.     

Fuzzy-logic based routing for dense wireless sensor networks

The task of routing data from a source to the sink is a critical issue in ad hoc and wireless sensor networks. In this paper, the use of fuzzy logic to perform role assignment during route establishment and maintenance is proposed. An incremental approach is presented and compared with similar existing routing protocols. Efficient routing approaches provide network load balance to extend network lifetime, efficiency improvements, and data loss avoidance. Experiments show promising results for our proposals and its suitability for operating with dense networks, obtaining quick route creation as well as energy efficiency.     

Improving cell broadcasting scheme to support multi-lingual service in wireless networks

In this paper we propose a new problem named energy-efficient multi-lingual cell broadcasting(EEML-CB) to support multi-lingual service in cell broadcasting system. We prove that the problem is NP-hard and then propose ILP model as well as a greedy algorithm named smart multi-lingual cell broadcasting (SMCB). We evaluated our heuristic by simulations.     

Timer-based broadcasting for power-aware routing in power-controlled wireless ad hoc networks

We propose a new cross-layer design method for minimizing the total consumed power in power-controlled wireless ad hoc networks. In contrast to previous research, we consider not only a power-aware routing algorithm, but also a MAC layer algorithm that is adequate to optimize its performance. Computer simulations show that the proposed scheme outperforms the conventional schemes with respect to the average total consumed power, while maintaining a similar average success rate. Moreover, the proposed scheme approximates the optimal solution calculated by CPLEX, and is scalable, since each node operates in a distributed manner.     

Efficient broadcasting in multi-hop wireless networks with a realistic physical layer

Almost all existing broadcasting algorithms assume an ideal physical layer, in which a successful transmission is guaranteed if the distance between communicating nodes is less than a certain threshold, e.g., a transmission range. However, wireless communication links normally suffer from the characteristics of realistic physical layer, which significantly reduce the reliability of broadcasting among the nodes. This work addresses the minimal broadcasting problem in multi-hop wireless networks with a realistic physical layer. Given a probability p^*, the problem is to design a distributed broadcasting algorithm such that each node in the network receives the broadcasting packet with probability no less than p^* and the number of retransmissions is minimized. We show that this problem is NP-hard and propose a distributed greedy algorithm which maximizes the gain cost ratio at each node. We prove that the proposed algorithm guarantees that each node receives the broadcasting packet with probability no less than p^*, and analyze upper bound on the number of total retransmissions in the network. Simulation results show that our algorithm can provide near 100% coverage to the wireless network with a realistic physical layer, and reduce the number of retransmissions compared with modified traditional flooding schemes k-Flooding (pure flooding with multiple times) and ACK-Flooding (pure flooding with acknowledgement). We believe our algorithmic solution is efficient and practical for general existing multi-hop wireless networks.     

Secure routing in mobile wireless ad hoc networks

We discuss several well known contemporary protocols aimed at securing routing in mobile wireless ad hoc networks. We analyze each of these protocols against requirements of ad hoc routing and in some cases identify fallibilities and make recommendations to overcome these problems so as to improve the overall efficacy of these protocols in securing ad hoc routing, without adding any significant computational or communication overhead.     

Evaluation and design of beaconing in mobile wireless networks

One of the intrinsic problems of mobility in wireless networks is the discovery of mobile nodes. A widely used solution for this problem is to use different variations of beacons, such as hello packets. Although a poorly designed beaconing scheme may lead to unnecessary energy usage or poor throughput, a systematic approach to analyze and select beaconing parameters is not provided in the literature. Here, we propose a model to study the beaconing efficiency using some measures such as the link lifetime, the probability of link establishment, and the delay to discover a new neighbor. The model is general and does not adhere to any particular mobility model; the only input from the mobility is the distribution of physical link durations, which not only abstracts away the mobility details but also all effects that contribute to the link stability such as non-perfectly omni-directional antennas and the path loss exponents. Among our results, we prove that the periodic beaconing (which is widely used owing to its simplicity) is the best in terms of beacon hits; we compare one-way and two-way beaconing schemes and study beaconing energy optimization. Finally, the model is applied to three cases of ad hoc, delay-tolerant, and sensor networks, and a simple rule of thumb is proposed to efficiently adjust the beacon interval.     

Improving performance of TCP over mobile wireless networks

Mobile IP is a network layer protocol for handling mobility of hosts in the Internet. However, mobile IP handoff causes degradation of TCP performance. Hence, there is a need for improving performance of TCP over mobile IP in wireless mobile networks. We propose an approach which handles losses due to both wireless link errors and host mobility. To handle losses due to host mobility, a method for seamless handoff is proposed. Empirical results show that the scheme provides substantial improvement of performance.